基于节点兴趣的非结构化P2P网络资源搜索算法

1、基于节点兴趣的非构造化P2P网络资源搜索算法基于节点兴趣的非构造化P2P网络资源搜索算法1 引言P2P网络中最关键的问题是如何高效地搜索资源。当节点在自身找不到想要的资源时，就会发出搜索恳求，搜索过程涉及消息形式、恳求转发方式、转发节点选择、节点局部索引等方面。不同网络构造可能会采用不同的搜索方法。当前的P2P网络可以分成两大类：构造化和非构造化。非构造化网络因其简单和强健性获得广泛应用，Gnutella是其中的典型模型。2 改进的搜索算法一个节点需要的资源，更可能在 跟自己兴趣相似的节点中搜索到。假设在某个节点成功搜索到需要的资源，说明两节点兴趣相似，下次该节点成功搜索的可能性会也进步。基于

2、这个思想，在Gnutella的搜索模型上，提出了基于节点兴趣和搜索经历的资源搜索算法。2.1 相关概念定义1元数据：对一个资源的描绘，通常包括资源的唯一标识通常为资源的Hash值、属性如标题，作者，创立时间，关键字等以及资源的存储位置。在搜索算法中，对资源的搜索转化为对元数据相关数据的搜索。定义3邻居节点：假设一个peer Pi和另一个peer Pj直接相连，那么它们互称为邻居节点。定义4 朋友节点：假设一个peer Pi和另一个peer Pj有相似的兴趣，那么它们互称为朋友节点。定义5 兴趣相似系数用来描绘节点间的相似性。系数越高，节点相似性越高。定义为：1其中le;12对任意节点Pi和Pj

3、，SPi，Pj= SPj，Pi 。定义6 捷径节点：假设一个peer Pi和另一个peer Pj既是邻居节点优势朋友节点，那么它们互称为捷径节点2.2 分组策略改进的搜索算法，根据节点间网络拓扑和兴趣相似度的关系，将节点分组为邻居节点、朋友节点以及捷径节点。2.2 .1建立邻居节点邻居节点的划分采用了底层搜索机制来发现邻居节点。这里的邻居节点直接连接并非指应用层的路由，而是实际网络层中的路由间隔 ，可以防止应用层中路由的一跳在实际网络层相距较远的情况出现，也更加接近实际网络拓扑构造，能获得更加有效的路由。建立邻居节点步骤：2Pi根据网络的规模选择一个适宜的TTL值发出Ping命令，主动探测与自

4、己相通的节点；3收到该消息的节点Pj，PkPm将返回应答消息。应答消息包含返回消息经过的跳数Hop和返回消息的节点IP，以及返回消息节点的本地资源信息表；4节点Pi将根据收到的应答消息中的Hop和收到消息的时间进展排序。Hop越小那么说明应答节点与Pi越接近。根据网络规模Pi选择一定数量Hop较小一般取Hop=1的节点作为邻居节点。5节点Pi向选择的邻居节点发送消息。邻居节点根据收到消息的时延等因素决定是否将其作为邻居节点。2.2 .2 建立朋友节点在保证消息的转发是在沿着实际间隔 位置上尽可能短的间隔 上进展的根底上，消息应该尽可能转发给最有可能存储查询资源的节点，因此查询消息要转发给兴趣最

5、相似的节点。建立朋友节点的步骤：1假设节点Pi是新参加的节点，在建立邻居节点时，根据其他节点返回的本地信息表，可以计算出其他节点与Pi的兴趣相似度。根据兴趣相似度将节点排序，根据网络规模取一定数量的相似度较高的节点作为朋友节点。2节点Pi将与其他节点的兴趣相似度发给对应的节点。其他节点根据其相似度决定是否将Pi作为自己的朋友节点。3将所有的朋友节点按照兴趣相似度和查询历史排序。当有新的节点参加时那么将排在最后面的节点删除，再参加新的朋友节点。2.2 .3 建立捷径节点节点的捷径节点就是那些与节点间隔 最近、兴趣相似的节点，即邻居节点集和朋友节点集的交集。2.3 搜索机制节点进展资源搜索的过程就

6、是查询消息在网络中进展路由的过程。进展搜索的根据就是节点维护的路由信息和采用的路由策略。节点按照分组不同搜集和保存一定的路由信息，使得路由尽量选择间隔 最近且兴趣最相似的节点。2.3 .1 节点路由信息1节点Pi参加系统后，建立邻居节点、朋友节点和捷径节点，然后建立相应的邻居节点、朋友节点和捷径节点的索引表。2在节点进展查询时和节点共享资源更新时动态地维护索引表。当有节点Pj退出系统时，本地节点Pi假设在Pj的索引表内，会收到Pj退出系统的消息，然后把Pi的索引表内Pj相关信息删除。假设Pi不在Pj的索引表内，虽然不能收到退出消息，但由于此链接不存在经过几次查询的正反响，将会从索引表中删除。1

7、为 ；rho;为信息量的挥发率，通常0rho;1防止信息量无限累加；Delta;delta;为信息增量，是该搜索成功消息留在Pj的信息量，即表征了此次成功搜索对下次搜索的影响，计算公式为：Delta;delta;-middot;TTLDelta;delta;middot;TTL3其中n为一个常量系数；TTL为搜索成功消息到达Pi节点的存活时间，因此离目的越近，其信息量越大。根据当返回一条搜索成功的消息时，需要沿途修改各节点的路由信息表。在Pj中找到Pi需要的资源，中间经过Pm，PnPl等节点，成功消息返回Pi时也要修改Pm中相对Pj的兴趣相似度、Pn中相对Pj的兴趣相似度Pl中相对Pj的兴趣相

8、似度。3当节点分开系统时，给自己索引表中的节点发送一个分开系统的消息，索引表中的节点收到该信息，那么将发送分开消息的节点从自己的索引表中删除。2.3 .2 搜索策略1当一个节点发起搜索恳求后，首先判断该节点是否有索引表。假设没有，说明节点是新参加节点，采用底层搜索机制进展搜索。2假设节点已经有了索引表，那么将查询恳求转发给所有的捷径节点。捷径节点查询本地资源表，假设查询成功那么返回查询结果，假设没有获得查询结果那么将查询恳求转发给自己的捷径节点。3假设通过捷径节点没有获得查询结果，那么将查询恳求转发给朋友节点。朋友节点查询本地资源表，假设查询成功那么返回查询结果，假设没有获得查询结果那么将查询恳求转发给自己的朋友节点。4假设通过朋友节点没有获得查询结果，那么将查询恳求转发给朋友节点。邻居节点查询本地资源表，假设查询成功那么返回查询结果，假设没有获得查询结果那么将查询恳求转发给自己的邻居节点。5假设仍然没有搜索到需要的资源，那么采用底层的搜索机制进展搜索。3 实验结果分析为了评价本文的资源搜索算法是否有效，建立了仿真程序来模拟P2P环境，与泛洪算法和随机漫步算法进展了比较，试验结果充分证明了本文算法相对泛洪算法和随机漫步算法的优势。本文提出一种基于兴趣和搜索经历的搜索算法，该算法通过将