基于节点兴趣的非结构化P2P网络资源搜索算法
1 引言
P2P网络中最关键的问题是如何高效地搜索资源。当节点在自身找不到想要的资源时，就会发出搜索请求，搜索过程涉及消息形式、请求转发方式、转发节点选择、节点局部索引等方面。
不同网络结构可能会采用不同的搜索方法。当前的P2P网络可以分成两大类：结构化和非结构化。非结构化网络因其简单和健壮性获得广泛应用，Gnutella是其中的典型模型。
2 改进的搜索算法
一个节点需要的资源，更可能在 跟自己兴趣相似的节点中搜索到。如果在某个节点成功搜索到需要的资源，说明两节点兴趣相似，下次该节点成功搜索的可能性会也提高。基于这个思想，在Gnutella的搜索模型上，提出了基于节点兴趣和搜索经验的资源搜索算法。
2.1 相关概念
定义1元数据：对一个资源的描述，通常包括资源的唯一标识（通常为资源的Hash值）、属性（如标题，作者，创建时间，关键字等）以及资源的存储位置。在搜索算法中，对资源的搜索转化为对元数据相关数据的搜索。
定义3邻居节点：如果一个peer Pi和另一个peer Pj直接相连，那么它们互称为邻居节点。
定义4 朋友节点：如果一个peer Pi和另一个peer Pj有相似的兴趣，那么它们互称为朋友节点。
定义5 兴趣相似系数用来描述节点间的相似性。系数越高，节点相似性越高。定义为：
（1）
其中≤1）
（2）对任意节点Pi和Pj，S（Pi，Pj）= S（Pj，Pi） 。
定义6 捷径节点：如果一个peer Pi和另一个peer Pj既是邻居节点优势朋友节点，那么它们互称为捷径节点
2.2 分组策略
改进的搜索算法，根据节点间网络拓扑和兴趣相似度的关系，将节点分组为邻居节点、朋友节点以及捷径节点。
2.2 .1建立邻居节点
邻居节点的划分采用了底层搜索机制来发现邻居节点。这里的邻居节点直接连接并非指应用层的路由，而是实际网络层中的路由距离，可以避免应用层中路由的一跳在实际网络层相距较远的情况出现，也更加接近实际网络拓扑结构，能获得更加有效的路由。
建立邻居节点步骤：
（2）Pi根据网络的规模选择一个合适的TTL值发出Ping命令，主动探测与自己相通的节点；
（3）收到该消息的节点Pj，Pk……Pm将返回应答消息。应答消息包含返回消息经过的跳数Hop和返回消息的节点IP，以及返回消息节点的本地资源信息表；
（4）节点Pi将根据收到的应答消息中的Hop和收到消息的时间进行排序。Hop越小则说明应答节点与Pi越接近。根据网络规模Pi选择一定数量Hop较小（一般取Hop=1）的节点作为邻居节点。
（5）节点Pi向选择的邻居节点发送消息。邻居节点根据收到消息的时延等因素决定是否将其作为邻居节点。
2.2 .2 建立朋友节点
在保证消息的转发是在沿着实际距离位置上尽可能短的距离上进行的基础上，消息应该尽可能转发给最有可能存储查询资源的节点，因此查询消息要转发给兴趣最相似的节点。
建立朋友节点的步骤：
（1）如果节点Pi是新加入的节点，在建立邻居节点时，根据其他节点返回的本地信息表，可以计算出其他节点与Pi的兴趣相似度。根据兴趣相似度将节点排序，根据网络规模取一定数量的相似度较高的节点作为朋友节点。
（2）节点Pi将与其他节点的兴趣相似度发给对应的节点。其他节点根据其相似度决定是否将Pi作为自己的朋友节点。
（3）将所有的朋友节点按照兴趣相似度和查询历史排序。当有新的节点加入时则将排在最后面的节点删除，再加入新的朋友节点。
2.2 .3 建立捷径节点
节点的捷径节点就是那些与节点距离最近、兴趣相似的节点，即邻居节点集和朋友节点集的交集。
2.3 搜索机制
节点进行资源搜索的过程就是查询消息在网络中进行路由的过程。进行搜索的依据就是节点维护的路由信息和采用的路由策略。节点按照分组不同收集和保留一定的路由信息，使得路由尽量选择距离最近且兴趣最相似的节点。
2.3 .1 节点路由信息
（1）节点Pi加入系统后，建立邻居节点、朋友节点和捷径节点，然后建立相应的邻居节点、朋友节点和捷径节点的索引表。
（2）在节点进行查询时和节点共享资源更新时动态地维护索引表。
当有节点Pj退出系统时，本地节点Pi如果在Pj的索引表内，会收到Pj退出系统的消息，然后把Pi的索引表内Pj相关信息删除。如果Pi不在Pj的索引表内，虽然不能收到退出消息，但由于此链接不存在经过几次查询的正反馈，将会从索引表中删除。
当有搜索成功消息从节点Pj返回节点Pi时，Pi就根据公式（2）对相对Pj的兴趣相似度Sˊ进行更新
其中Sˊ的初始值根据公式
（1）为 ；ρ为信息量的挥发率，通常0<ρ<1避免信息量无限累加；Δδ为信息增量，是该搜索成功消息留在Pj的信息量，即表征了此次成功搜索对下次搜索的影响，计算公式为：Δδ-·TTLΔδ·TTL（3）
其中n为一个常量系数；TTL为搜索成功消息到达Pi节点的存活时间，因此离目标越近，其信息量越大。
Pi修改了与Pj的兴趣相似度Sˊ后，如果Pj不在Pi的朋友节点索引表中，将Sˊ与朋友节点索引表中最小兴趣相似度S”比较。若Sˊ>S”，则删除S”的相应节点，将Pj节点加入朋友节点索引表。最后根据兴趣相似度排序朋友节点索引表，重新确定捷径节点索引表。
根据当返回一条搜索成功的消息时，需要沿途修改各节点的路由信息表。在Pj中找到Pi需要的资源，中间经过Pm，Pn……Pl等节点，成功消息返回Pi时也要修改Pm中相对Pj的兴趣相似度、Pn中相对Pj的兴趣相似度……Pl中相对Pj的兴趣相似度。
（3）当节点离开系统时，给自己索引表中的节点发送一个离开系统的消息，索引表中的节点收到该信息，则将发送离开消息的节点从自己的索引表中删除。
2.3 .2 搜索策略
（1）当一个节点发起搜索请求后，首先判断该节点是否有索引表。如果没有，说明节点是新加入节点，采用底层搜索机制进行搜索。
（2）如果节点已经有了索引表，则将查询请求转发给所有的捷径节点。捷径节点查询本地资源表，如果查询成功则返回查询结果，如果没有获得查询结果则将查询请求转发给自己的捷径节点。
（3）如果通过捷径节点没有获得查询结果，则将查询请求转发给朋友节点。朋友节点查询本地资源表，如果查询成功则返回查询结果，如果没有获得查询结果则将查询请求转发给自己的朋友节点。
（4）如果通过朋友节点没有获得查询结果，则将查询请求转发给朋友节点。邻居节点查询本地资源表，如果查询成功则返回查询结果，如果没有获得查询结果则将查询请求转发给自己的邻居节点。
（5）如果依然没有搜索到需要的资源，则采用底层的搜索机制进行搜索。
3 实验结果分析
为了评价本文的资源搜索算法是否有效，建立了仿真程序来模拟P2P环境，与泛洪算法和随机漫步算法进行了比较，试验结果充分证明了本文算法相对泛洪算法和随机漫步算法的优势。
本文提出一种基于兴趣和搜索经验的搜索算法，该算法通过将节点分组为邻居节点、朋友节点和捷径节点，用节点间兴趣相似度和之前的搜索结果来指导节点进行资源搜索。实验结果表明，本算法能有效地减少查询带来的网络流量，提高资源搜索的成功率。
