《基于节点兴趣的非结构化p2p网络资源搜索算法》由会员分享，可在线阅读，更多相关《基于节点兴趣的非结构化p2p网络资源搜索算法（7页珍藏版）》请在金锄头文库上搜索。
1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果基于节点兴趣的非结构化P2P网络资源搜索算法1 引言P2P网络中最关键的问题是如何高效地搜索资源。当节点在自身找不到想要的资源时，就会发出搜索请求，搜索过程涉及消息形式、请求转发方式、转发节点选择、节点局部索引等方面。不同网络结构可能会采用不同的搜索方法。当前的P2P网络可以分成两大类：结构化和非结构化。非结构化网络因其简单和健壮性获得广泛应用，Gnutella是其中的典型模型。改进的搜索算法一个节点需要的资源，更可能在联盟跟自己兴趣相似的节点中搜索到。如果在某
2、个节点成功搜索到需要的资源，说明两节点兴趣相似，下次该节点成功搜索的可能性会也提高。基于这个思想，在Gnutella的搜索模型上，提出了基于节点兴趣和搜索经验的资源搜索算法。 相关概念定义1元数据：对一个资源的描述，通常包括资源的唯一标识、属性以及资源的存储位置。在搜索算法中，对资源的搜索转化为对元数据相关数据的搜索。定义2假设P2P系统中包括n个节点，记为P1，P2，Pn，N=P1，P2，Pn定义3邻居节点：如果一个peer Pi和另一个peer Pj直接相连，那么它们互称为邻居节点。定义朋友节点：如果一个peer Pi和另一个peer Pj有相似的兴趣，那么它们互称为朋友节点。定义兴趣相似
3、系数用来描述节点间的相似性。系数越高，节点相似性越高。定义为：其中Wij为Pi和Pj的相同元数据个数；Wi为Pi的元数据个数，Wj为Pj的元数据个数。当且仅当Pi=Pj时，S =1 。对任意节点Pi和Pj，S= S 。定义捷径节点：如果一个peer Pi和另一个peer Pj既是邻居节点优势朋友节点，那么它们互称为捷径节点2.分组策略改进的搜索算法，根据节点间网络拓扑和兴趣相似度的关系，将节点分组为邻居节点、朋友节点以及捷径节点。2.1建立邻居节点邻居节点的划分采用了底层搜索机制来发现邻居节点。这里的邻居节点直接连接并非指应用层的路由，而是实际网络层中的路由距离，可以避免应用层中路由的一跳在实
4、际网络层相距较远的情况出现，也更加接近实际网络拓扑结构，能获得更加有效的路由。建立邻居节点步骤：当节点Pi加入P2P系统时，它不存在关于其他邻居节点的任何消息，而其他邻居节点也不了解它的共享资源，因此Pi首先根据自己的共享资源建立本地信息表，并且当本地共享资源有变化时要对本地信息表进行更新。Pi根据网络的规模选择一个合适的TTL值发出Ping命令，主动探测与自己相通的节点；收到该消息的节点Pj，PkPm将返回应答消息。应答消息包含返回消息经过的跳数Hop和返回消息的节点IP，以及返回消息节点的本地资源信息表；节点Pi将根据收到的应答消息中的Hop和收到消息的时间进行排序。Hop越小则说明应答节
5、点与Pi越接近。根据网络规模Pi选择一定数量Hop较小的节点作为邻居节点。节点Pi向选择的邻居节点发送消息。邻居节点根据收到消息的时延等因素决定是否将其作为邻居节点。2.建立朋友节点在保证消息的转发是在沿着实际距离位置上尽可能短的距离上进行的基础上，消息应该尽可能转发给最有可能存储查询资源的节点，因此查询消息要转发给兴趣最相似的节点。建立朋友节点的步骤：如果节点Pi是新加入的节点，在建立邻居节点时，根据其他节点返回的本地信息表，可以计算出其他节点与Pi的兴趣相似度。根据兴趣相似度将节点排序，根据网络规模取一定数量的相似度较高的节点作为朋友节点。节点Pi将与其他节点的兴趣相似度发给对应的节点。其
6、他节点根据其相似度决定是否将Pi作为自己的朋友节点。将所有的朋友节点按照兴趣相似度和查询历史排序。当有新的节点加入时则将排在最后面的节点删除，再加入新的朋友节点。2.建立捷径节点节点的捷径节点就是那些与节点距离最近、兴趣相似的节点，即邻居节点集和朋友节点集的交集。2.搜索机制节点进行资源搜索的过程就是查询消息在网络中进行路由的过程。进行搜索的依据就是节点维护的路由信息和采用的路由策略。节点按照分组不同收集和保留一定的路由信息，使得路由尽量选择距离最近且兴趣最相似的节点。2.1 节点路由信息节点Pi加入系统后，建立邻居节点、朋友节点和捷径节点，然后建立相应的邻居节点、朋友节点和捷径节点的索引表。
7、在节点进行查询时和节点共享资源更新时动态地维护索引表。邻居节点、朋友节点和捷径节点的索引表都有相应的大小L1、L2和L3，而随着时间推移，节点间相互关系也会有相应的变化。除了两节点的兴趣相似度，我们主要考虑查询历史对于兴趣相似关系的影响，进而对朋友节点和捷径节点的索引表的影响。 当有新节点Pj加入时，本地节点Pi会收到新节点发送的Ping命令，根据新节点的Hop距离考虑是否加入邻居节点，并根据返回的初始兴趣相似度考虑是否加入自己的朋友节点。当有节点Pj退出系统时，本地节点Pi如果在Pj的索引表内，会收到Pj退出系统的消息，然后把Pi的索引表内Pj相关信息删除。如果Pi不在Pj的索引表内，虽然不
8、能收到退出消息，但由于此链接不存在经过几次查询的正反馈，将会从索引表中删除。当有搜索成功消息从节点Pj返回节点Pi时，Pi就根据公式对相对Pj的兴趣相似度S进行更新SS+其中S的初始值根据公式为 ；为信息量的挥发率，通常0S”，则删除S”的相应节点，将Pj节点加入朋友节点索引表。最后根据兴趣相似度排序朋友节点索引表，重新确定捷径节点索引表。根据当返回一条搜索成功的消息时，需要沿途修改各节点的路由信息表。在Pj中找到Pi需要的资源，中间经过Pm，PnPl等节点，成功消息返回Pi时也要修改Pm中相对Pj的兴趣相似度、Pn中相对Pj的兴趣相似度Pl中相对Pj的兴趣相似度。当节点离开系统时，给自己索引
9、表中的节点发送一个离开系统的消息，索引表中的节点收到该信息，则将发送离开消息的节点从自己的索引表中删除。2.搜索策略当一个节点发起搜索请求后，首先判断该节点是否有索引表。如果没有，说明节点是新加入节点，采用底层搜索机制进行搜索。如果节点已经有了索引表，则将查询请求转发给所有的捷径节点。捷径节点查询本地资源表，如果查询成功则返回查询结果，如果没有获得查询结果则将查询请求转发给自己的捷径节点。如果通过捷径节点没有获得查询结果，则将查询请求转发给朋友节点。朋友节点查询本地资源表，如果查询成功则返回查询结果，如果没有获得查询结果则将查询请求转发给自己的朋友节点。如果通过朋友节点没有获得查询结果，则将查
10、询请求转发给朋友节点。邻居节点查询本地资源表，如果查询成功则返回查询结果，如果没有获得查询结果则将查询请求转发给自己的邻居节点。如果依然没有搜索到需要的资源，则采用底层的搜索机制进行搜索。实验结果分析为了评价本文的资源搜索算法是否有效，建立了仿真程序来模拟P2P环境，与泛洪算法和随机漫步算法进行了比较，试验结果充分证明了本文算法相对泛洪算法和随机漫步算法的优势。本文提出一种基于兴趣和搜索经验的搜索算法，该算法通过将节点分组为邻居节点、朋友节点和捷径节点，用节点间兴趣相似度和之前的搜索结果来指导节点进行资源搜索。实验结果表明，本算法能有效地减少查询带来的网络流量，提高资源搜索的成功率。课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。
