混合P2P网络资源搜索机制研究

刘海芹

（聊城大学东昌学院 数学与信息工程系，山东 聊城 252000）

现在基于P2P技术的各种应用已经以势不可挡的趋势融入了人们的工作、学习和生活，从QQ 等即时通信类软件系统到Napster等文件共享类软件系统等，都体现出了P2P技术在互联网技术中的重要地位和作用.无论是哪一种P2P应用都会涉及资源搜索的问题，而且搜索的效率和准确性将直接影响应用的流行程度，因此资源的高效搜索机制就成为了研究热点.每种搜索算法都是基于某种网络拓扑结构的.集中式P2P网络的资源搜索技术相对简单，但对中心服务器过于依赖；单纯的结构化P2P网络资源搜索技术准确性高，但维护难度较大；单纯的非结构化P2P网络资源搜索技术造成网络冗余信息过多，搜索准确率较低.因此，本文基于一种混合P2P网络拓扑结构，提出将改进的Chord算法和基于超级节点的搜索算法结合应用的一种方法，并探讨了簇中超级节点失效的应对策略问题.

目前，基于结构化P2P 网络的资源搜索算法较多，其中比较流行的是基于分布式哈希表（DHT）的Chord算法.文献［1］中设置的proximity list表记录了在1个生存周期内某节点所搜集到的其邻居节点的标识，Proximity表和finger表共同决定了该节点下一步的去向.这种改进策略有效提高了网络路由效率，但在处理节点的加入和退出时，该策略具有一定局限性，收敛较慢，效率较低.文献［2］采用基于信任值的转发方式减少消息冗余，在随机漫步算法的基础上，对源节点的请求算法和中继节点的转发、响应算法进行了改进.IPv6的地址是一种层次结构，利用这种特性，文献［3］提出Chord6算法，使得同一个域中每个节点的标识更相近，降低了平均路径长度，但是由于Hash 函数固有特性的原因，基于Chord6的网络中，分别处于2个相邻域内的节点的实际距离可能会比较远.随机漫步算法是非结构化网络中较为重要的搜索算法.文献［4］对典型的随机漫步算法做出改进，利用度最高的节点的存储能力来提高资源搜索的效率和准确性，在Gnuetella系统中对该算法的有效性进行了验证，但是该算法有可能导致整个P2P 网络崩溃，因为系统中只有少量度最高的节点，而其却承载着整个网络中全部节点的查询请求，容易致使最高度节点过载，最终使得整个网络崩溃.一种概率广播算法由文献［5］提出，在文件索引数量超过一个临界值时就可以使得搜索效率达到一个很高的水准，该临界值是由渗流理论所确定的，但是这种算法在提高搜索效率的同时，所耗费的网络资源也是非常多的.

因此本文提出一种基于混合网络的搜索算法，基于节点物理位置相邻情况划分节点簇，在节点簇内选出超级节点，使用基于超级节点的算法，来提高簇内资源搜索效率，降低资源传递和存储代价.将节点簇中的超级节点看成Chord环上的节点，各个簇间以面向结构化网络的Chord算法互联并进行资源查询.

1 混合网络拓扑结构

网络主体结构采用Chord环结构，在节点簇中选出综合性能较高的超级节点，环上节点由每个节点簇的超级节点充当.

图1 混合网络拓扑结构Fig.1 Hybrid network topology

每个节点簇具有一个簇标识符，按照标识符的大小顺序，所有簇顺时针分布于Chord环上，如图1所示，簇中的超级节点P1，P2，P3，…，P10互相连接，构成一个Chord环系统.

利用哈希函数SHA－1对Chord环上的每一个超级节点的IP地址进行哈希，得到的值作为对应节点的ID 标识，该标识具有全系统唯一性.通过哈希资源的关键字，得到资源的ID.通常使用m 位二进制来表示ID 标识，将ID 的位数设置的足够大，目的是为了使得分配的ID 值尽量不发生重复.文中将超级节点ID 记为n，资源ID 记为k.超级节点ID 和资源ID 都是按从小到大的顺序顺时针分布于Chord环之上的.k 的后继记为Succ（k），指的是节点的ID 大于或等于资源ID（即k）的且离资源k最近的超级节点.

2 资源搜索算法

2.1 簇内搜索算法

节点簇是指物理距离在一定范围内的节点的集合.根据节点的计算性能、存储性能、可用带宽、在线时长、活跃程度等综合性能，选定若干节点为超级节点.簇内普通节点将自己的资源信息发送给本簇超级节点存储.超级节点除了负责维护其所在簇内所有终端节点的资源索引目录文件，还负责监视Free－Riding节点的自私行为.

簇内搜索算法描述如下：

1）节点发起资源查询请求给超级节点；

2）超级节点查询自己存储的簇内节点资源索引列表；

3）如果在本地找到资源目标节点，则超级节点向目标节点转发资源请求节点的查询请求；在资源查询节点和资源目标节点之间建立连接，并进行资源传递；

4）如果超级节点在本地索引列表中没有找到所需资源，则向Chord环上发送该资源查询请求；

5）查找成功，则在资源请求节点和目标节点间建立连接，进行文件传输.否则报查找失败.

2.2 簇间搜索算法

在如图1所示的混合网络中，每个聚簇中的超级节点构成1个Chord环，每个超级节点中保存1个由超级节点的直接前驱节点、直接后继节点、F列表、后继节点列表及后继节点存储空间信息所组成的路由表，其结构如表1所示.

表1 超级节点中的路由表Tab.1 Routing table in super nodes

设置后继节点列表的目的，是为了在某个后继节点发生故障时，用列表中的某个节点进行替换.存储后继节点的存储空间信息，可以使得路由过程中的跳数有效减少［6］.

簇间搜索算法描述如下：

簇间搜索算法是指在超级节点间，遵循Chord算法规则进行搜索路由.

第1步，为获取资源S，节点P 发出资源请求信息；

第2步，确定资源的标识K，利用一致性哈希函数进行确定；

第3步，获取节点P 及其后继节点的存储空间标识，查看资源标识是否在节点P 及其后继节点的存储空间标识范围内，即P.n＜K＜Succ（P）.n.如果满足这个条件，说明节点Succ（P）中存有要查询的资源S，节点P 与节点Succ（P）建立连接进行资源获取.否则，进入下一步；

第4步，对节点P 的F表进行查询，如果能够发现小于K 而且与K 的距离最小的节点P'，则将P'作为新的P 节点重新执行步骤3；

第5步，如果搜索对整个环进行了1圈也没有发现所要搜索的资源，则搜索不成功.

2.3 全局资源搜索算法描述

超级节点间查找资源，按照2.2所述簇间搜索算法进行.

节点簇内普通节点搜索资源，按照2.1所述簇内搜索算法进行.普通节点首先查询所在簇的超级节点，如果存有所需资源，则进行资源传递，搜索成功，否则超级节点再次按照簇间搜索算法进行搜索，如果查找成功，超级节点传输资源给请求资源的节点，否则对资源请求节点返回查找失败信息.

2.4 超级节点失效问题

簇在划分时即考虑节点物理位置的邻近情况，选择物理位置在一定范围内的节点组成一个簇，所以尽管时有节点加入和离开，但总体来看，簇中节点基本不变.因此，可以在簇中选出若干整体性能较强的节点来充当超级节点，将选出的超级节点列表（按整体性能排序）存储于簇内所有节点之中.一旦当前超级节点失效，从超级节点列表的第1个记录（性能最强的超级节点标识）开始查找可用的超级节点.如果表中所有超级节点都已失效，重新运行超级节点选取机制选出1个超级节点加入列表，并充当当前的超级节点.每次更换超级节点，都通知失效超级节点在Chord环中的前驱和后继节点.

3 仿真实验

实验使用Peersim 仿真系统，它支持2种仿真模式，即Cycle－based模式和传统的event－based模式.Cycle－based模型是一个简化的模型，拥有更好的伸缩性及性能.本文采用Cycle－based模式进行仿真.

实验对本文的混合查询算法和传统的Chord查询算法分别进行了模拟.设置整个网络节点数为1 000，针对簇的大小为10，15，20，25，30，35，40个节点的情况分别进行实验，平均每个节点10个资源.

实际上传统Chord算法相当于将整个网看成一个簇，所以图2中传统的Chord算法随着簇规模的变化平均跳数并没有变化.本文的资源搜索算法，由于将环上节点分簇，跳数指在簇间的跳数，所以能使得平均跳数随着节点簇规模的增大而逐渐减小，进而整体上提高了资源搜索效率.

搜索成功率代表查询算法的工作效率和有效性，搜索成功率越高，说明查询算法设计的越合理.考虑到实际应用中，簇规模太大会给簇内超级节点造成太大压力，选择簇内30个节点进行实验，针对不同的资源查询次数对搜索成功率进行了统计，实验结果如图3所示.

图2 平均跳数变化趋势Fig.2 Average hop trend chart

图3 搜索成功率随查询次数变化曲线Fig.3 Graph search success rate with the query number change

本文算法因为在簇内使用了资源索引列表，所以在簇内的资源搜索比较精准，而簇间搜索率与传统Chord模型近似，因此在整网中的搜索成功率要高于传统Chord模型.

4 结论

综合考量结构化搜索算法和非结构化搜索算法的优缺点，本文提出将基于超级节点的搜索算法和改进的基于结构P2P网络的Chord算法有机结合起来的算法.由物理距离相近的节点组成一个簇，根据节点综合性能，选出超级节点，负责本簇资源索引列表管理等职责.簇内采用基于超级节点的搜索算法，簇间使用改进的Chord算法.实验表明，本文的资源搜索算法能有效提高查询成功率，减少平均查询跳数.但也存在一些缺点，网络中的节点互相之间具有异构性，本文算法未考虑到这一点，可以作为进一步研究的课题.

［1］ FENG Hong，LI Minglu.PChord：Improvement on chord to achieve better routing efficiency by exploiting proximity［Z］The 25th IEEE International Conference on Distributed Computing Systems Workshops，Columbus Ohio USA，2005.

［2］ 范会波，张新有.一种基于信任模型的P2P快速搜索算法－SAT［J］.计算机应用研究，2011，28（10）：3861－3864.FAN Huibo，ZHANG Xinyou.New P2Psearching algorithm based on trust model－SAT＊［J］.Application Research of Computers，2011，28（10）：3861－3864.

［3］ XIONG JipingZHANG YouweiHONG Peilinet al.Chord6IPv6based topology－aware chordZ.The Joint International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Services，Papeete，Tahiti，2005.

［4］ ADAMIC L，LUKOSE R，PUNIYANI A，et al.Search in powerlaw networks［J］.Phys Rev E，2001，64（4）：046135.

［5］ SARSHAR N，BOYKIN P O，ROYCHOWDHURY V P，et al.Percolation search in power law networks：making unstructured peer－to－peer networks scalable［Z］.Proceedings of the 4th IEEE International Conference on Peer－to－Peer Computing，Zurich，2004.

［6］ 叶培顺.非结构化P2P 网络的一种改进搜索算法［J］.计算机与现代化，2013，12：44－47.YE Peishun.Improved search algorithm for unstructured P2Pnetwork［J］.Computer and Modernization，2013，12：44－47.

［7］ 张建伟.基于蚁群优化算法的Chord 模型［J］.计算机工程，2012，38（4）：100－103.ZHANG Jianwei.Chord model based on ant colony optimization algorithm［J］.Computer Engineering，2012，38（4）：100－103.

［8］ 冯劲潇，陈贵海.基于分层象限空间的P2P超级节点查找技术［J］.计算机科学，2010，37（3）：50－55.FENG Jinxiao，CHEN Guihai.P2Psuper－peer search techniques based on hierarchical quadrant space［J］.Computer Science，2010，37（3）：50－55.

［9］ 王雷，王培.基于P2P 的多机通信机制及负载平衡的设计［J］.河北大学学报：自然科学版，2007，27（1）：107－112.WANG Lei，WANG Pei.Communication mechanism and load balancing design on peer－to－peer structure［J］.Journal of Hebei University：Natural Science Edition，2007，27（1）：107－112.

［10］ 胡玉琦，高吉敏.基于chord 的混合式网络模型研究［J］.计算机工程与设计，2011，32（6）：1877－1879.HU Yuqi，GAO Jimin.Research on hybrid network model based on chord［J］.Computer Engineering and Design，2011，32（6）：1877－1879.

［11］ 赵堃，牛振东.基于节点簇的P2P 随机漫步搜索［J］.华南理工大学学报：自然科学版，2010，38（7）：14－19.ZHAO Kun，NIU Zhendong.Node cluster－based random walk search in peer－to－peer network［J］.Journal of South China University of Technology：Natural Science Edition，2010，38（7）：14－19.

［12］ 王学龙，张璟.P2P关键技术研究综述［J］.计算机应用研究，2010，27（3）：801－805.WANG Xuelong，ZHANG Jing.Survey on peer－to－peer key technologies［J］.Application Research of Computers，2010，27（3）：801－805.

［13］ 程澜，缑锦，周峰.基于感知位置与择优连接的P2P网络搜索方法［J］.小型微型计算机系统，2012，33（6）：1257－1260.CHENG Lan，GOU Jin，ZHOU Feng.Peer to peer network search algorithm based on apperceiving location and preferential attachment［J］.Journal of Chinese Computer Systems，2012，33（6）：1257－1260.

［14］ 李瑞兴.P2P模式下的资源定位技术探究［J］.太原师范学院学报：自然科学版，2012，11（3）：77－81.LI Ruixing.The research to resource positioning technology of P2P mode［J］.Journal of Taiyuan Normal University：Natural Science Edition，2012，11（3）：77－81.