一种基于社会行为的非结构化P2P搜索算法

朱国晖，张武强，鲁春兰

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

一种基于社会行为的非结构化P2P搜索算法

朱国晖，张武强，鲁春兰

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

摘要:针对非结构化对等网络(P2P)中信息资源搜索效率低的问题，给出一种基于社会行为的单跳算法。为网络中每个节点引入朋友列表和查询记录列表，记录过去的搜索经验，用于同伴选择和路线查询，之后排列节点价值，更新列表。利用基于推荐节点搜索、基于有用的朋友节点搜索和基于邻居节点搜索3种机制，搜索所需资源。仿真结果表明，所给算法可减少搜索跳数，提高搜索成功率，减少冗余消息，节省内存空间。

关键词:P2P网络；社会行为；节点关系；单跳算法

P2P网络[1]是一种节点高度自治的分布式结构网络，相互连接的各个节点之间可以实现实时通信，已经广泛应用在资源共享、搜索引擎、即时通讯和协同工作等各个方面[2]。P2P网络分为结构化和非结构化两种模式[3]，结构化P2P网络以哈希函数实现节点和文件的映射，能够在确定的跳数内定位内容，但很难有效地支持模糊搜索。然而，非结构化P2P网络中节点之间不存在相互约束关系，资源在网络中随机存贮，具有较强的容错能力，使用户能够快速准确的搜索到所需资源，提高了网络资源的利用率。洪泛算法[4]是一种最基本的随机搜索算法，消息覆盖率高，算法适应性好，但存在冗余消息过多，严重浪费网络带宽和计算能力等缺点，限制了网络的可扩展性。随机漫步算法[5]是对洪泛算法的改进，将消息随机转发给某些邻居节点，减少了冗余消息，但是搜索成功率不高。

社会行为模式[6]依赖于社会关系网中人们的背景、友谊关系、共同利益和共享经历，等同于非结构化P2P网络中节点的名称、兴趣、所需资源和搜索历史，基于人们的记忆能力，节点之间相互联系，学习过去的搜索经验和历史，建立朋友关系并分享相似的兴趣，从而形成索引列表来记忆和修改自己在网络搜索中获得的信息。同时，通过资源索引信息来区分与其他节点的联系。基于兴趣域的搜索算法[7]，与相似兴趣的节点相互分享所需资源，从而提高搜索效率，减少网络流量；基于社会行为的搜索算法[8]，引入社会网理论，模拟人与人之间的共同利益、友谊和记忆能力，建立节点之间的联系，学习过去的搜索经验和历史，从而形成索引列表来提高搜索效率；两跳算法[9]是基于社会行为模式，与邻居节点建立朋友关系，相互学习，并存储查询记录，从而快速搜索到所需资源。但是，上述3种算法在搜索跳数、网络存储空间和网络可伸缩性等方面还有待于提高。

本文拟基于社会行为模式，对两跳算法加以改进，提出一种单跳算法。在每个节点引入朋友列表和查询记录列表，通过记录过去的搜索经验选择同伴和查询路线，使节点之间建立联系，并排列节点的价值更新列表，以期节省内存空间。

1单跳算法模型

1.1单跳算法思想

网络节点在一次成功搜索后，会在自己的朋友列表中记录此次搜索资源信息，同时被搜索节点也会在查询记录列表中记录此次搜索信息，主动节点和被动节点在多次搜索过程中形成朋友列表和查询记录列表两张路由表。节点的新一次搜索就可根据查询记录列表信息直接确定目标资源节点，从而实现一跳锁定资源，这就是单跳算法的基本原理。与此同时，节点在每次搜索中会评价朋友对自己的重要程度，删除一些列表里面无用的节点信息，从而节省内存空间。

当查询节点发起查询时，先使用基于推荐节点搜索[10](RecommendedNodeBasedSearch，RBS)开始搜索，如果有推荐节点查询记录，就直接连接推荐节点获得所需资源。如果没有推荐节点的查询记录，使用基于有用的朋友搜索[11](UsefulFriendBasedSearch，UBS)连接朋友节点。如果节点既没有推荐节点也没有朋友节点，将查询发送到n个(转发节点个数)邻居节点，使用基于邻居搜索[12](NeighbourBasedSearch，NBS)，否则认定搜索失败。设3种搜索机制的成功次数分别为R、U、N，总搜索次数为T，则搜索的平均成功率可表示为[9]

1.2节点列表的形成

网络中节点通过模仿社会行为中人们的记忆能力，建立索引列表来记录和修改自己在网络搜索中获得的信息，并引入两张列表记录过去的搜索经验选择同伴和查询路线，同时排列节点的价值更新列表，节省内存空间。

如图1所示，Ni代表节点名称，Ri代表节点所拥有资源名称。初始状态下，有用的朋友列表和每个节点的查询记录列表是空的。

设置转发节点个数为2，发出3次搜索请求。

第1次搜索，节点N1发出请求搜索资源R8，N1把请求消息分别转发给N2和N3，从N2获得资源R8，这时N1更新自己的资源信息拥有R1和R8，并更新朋友列表，把N2记为自己的朋友，价值+1。同时，在N3中没有找到资源R8，这时N3更新自己的被查询列表，记录N1查找过R8。

第2次搜索，节点N4搜索资源R8，此时N4有3个邻居节点。假设N4向N3和N5发出搜索请求，从N5获得资源R8，这时N4更新自己的资源信息拥有R2和R8，并更新朋友列表，把N5记为自己的朋友，价值+1，同时N4向N3发出请求时，发现N1曾经向N3发出过同样的请求，因此N4直接跟N1建立联系，获得R8，并更新朋友列表，把N1记为自己的朋友，价值+1，这样从逻辑上来说直接跳过N3，通过一跳找到N1中的资源R8。

第3次搜索，节点N3搜索资源R8，发现N1曾经向自己发出过同样的请求，因此就直接与N1建立联系获得R8，并更新自己的资源信息，同时更新朋友列表，把N1记为自己的朋友，价值+1。

图1　朋友列表和查询记录列表的形成过程

1.3算法流程

当节点发出查询请求时，按照RBS、UBS和NBS3种不同的搜索机制依次进行查询，直到得出所需资源。假设节点N3发出请求，搜索资源R8，设置转发给邻居节点的个数为n，具体执行步骤如图2所示。

图2　算法执行示意图

2仿真结果与分析

采用Peersim仿真工具，按照Cycle-based模式[13]进行模拟实验，实验中设置该网络环境中共有500个节点，初始文件种数为100，即100个文件都是不同的。初始文件的个数由系统随机生成，并随机分布到各个节点上，每个节点上最多生成不多于5个文件，同一个节点上相同文本只存在一份。每个周期发出200个查询请求，一轮结束以后再进行下一轮实验，实验一共进行10个周期，每次查询设置转发节点比例。

实验中分别从搜索的平均成功率、平均路径长度和平均消息数3个性能指标对比单跳算法、两跳算法和随机漫步算法。对比结果分别如图3、图4和图5所示。

从图3中可以看出随着消息转发节点比例的增加，3种算法的搜索平均成功率逐渐增加。当转发节点比例增加时，查询请求会转发给更多的节点，从而搜索成功率提高明显。当转发比例相同时，单跳算法由于利用3种不同的搜索机制轮流搜索，搜索更加全面，平均成功率更高一些。因此，单跳算法在搜索平均成功率方面要优于其他两种算法。

图3　平均成功率对比结果

图4　平均路径长度对比结果

由图4可知，两跳算法中资源在第一或第二跳会被发现，资源的平均路径长度在1和2之间，而且随着转发节点的增多，搜索到资源的速度就越快，平均搜索跳数基本不变，接近于1。然而，单跳算法可直接根据查询记录列表锁定目标资源节点，资源的平均路径长度等于1。随机漫步算法在平均路径长度方面要远大于前两者。因此，单跳算法减少了搜索跳数，缩短了平均路径长度。

图5　平均消息量对比结果

从图5可以看出，平均每个节点发送和接收消息的数量随着转发节点比例的增加而增加，随机漫步算法因为要转发给多个节点，消息量较大；两跳和单跳算法消息量相对较少，同时在转发比例增加到一定的值时，单跳算法的消息量基本趋于平衡。因此，单跳算法产生更少的冗余消息，节省了内存空间。

3结束语

基于社会行为的单跳算法，在两跳算法的基础上，增加查询记录列表，排列节点的价值，利用基于推荐节点搜索、基于有用的朋友节点搜索和基于邻居节点搜索3种搜索机制提高搜索性能。仿真结果表明，单跳算法的搜索平均成功率高于随机漫步算法和两跳算法，并且减少了搜索跳数，缩短了平均路径长度。同时，节点平均发送和接收的消息数量相对较少，减少了冗余消息，节省了内存空间。

参考文献

[1]房佩.非结构化P2P网络中资源搜索算法研究[D].西安:陕西师范大学,2013:8-52[2015-03-18].http://cdmd.cnki.com.cn/Article/CDMD-10718-1014106666.htm.

[2]周韬.P2P网络资源搜索方法的研究[D]. 北京:北京交通大学, 2015:6-67[2015-04-10].http://cdmd.cnki.com.cn/Article/CDMD-10004-1015545303.htm.

[3]何明, 张玉洁, 孟祥武. 面向用户需求的非结构化P2P资源定位泛洪策略[J/OL]. 软件学报,2015,26(3):640-662[2015-04-21].http://www.cnki.com.cn/Article/CJFDTotal-RJXB201503014.htmDOI:10.13328/j.cnki.jos.004787.

[4]谢晃, 张昱, 王云凯.非结构化P2P网络中基于节点的MQR算法设计与实现[J/OL].计算机工程,2014(9):111-116,123[2015-04-25].http://www.cnki.com.cn/Article/CJFDTotal-JSJC201409024.htm.DOI:10.3969/j.issn.1000-3428.2014.09.023.

[5]刘璇, 于双元. 非结构化P2P网络基于马尔科夫链的搜索算法研究[J/OL]. 软件, 2015, 36(3)：116-121[2015-05-10].http://www.cnki.com.cn/Article/CJFDTotal-RJZZ201503024.htm.DOI:10.3969/j.issn.1003-6970.2015.03.023.

[6]叶培顺.非结构化P2P网络的一种改进搜索算法[J/OL].计算机与现代化，2013(12):44-47[2015-05-16].http://www.cnki.com.cn/Article/CJFDTotal-JYXH201312012.htm.DOI:10.3969/j.issn.1006-2475.2013.12.012.

[7]陈香香, 吴开贵, 陈明. 基于兴趣域的对等网络动态搜索机制[J/OL]. 计算机应用研究, 2011,28(1):226-229[2015-05-21].http://www.cnki.com.cn/Article/CJFDTotal-JSYJ201101064.htm.DOI:10.3969/j.issn.1001-3695.2011.01.063.

[8]SANGUANKOTCHAKORNT.socP2P:P2PcontentDiscoveryenhancementbyconsideringsocialnetworkscharacteristics[C/OL]//2013IEEESymposiumonComputersandCommunications(ISCC).IEEE, 2012:000530-000533[2015-05-10].http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=6249350.DOI: 10.1109/ISCC.2012.6249350

[9]CHENK,SHENH,ZHANGH.LeveragingSocialNetworksforP2PContent-BasedFileSharinginDisconnectedMANETs[J/OL].IEEETransactionsonMobileComputing, 2014, 13(2):235[2015-04-25].http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6361402.DOI: 10.1109/TMC.2012.239

[10]LUL,NICKA,STEPHENN,SocialPeer-to-PeerforResourceDiscovery[C]// 2014 22ndEuromicroInternationalConferenceonParallel,Distributed,andNetwork-BasedProcessing.IEEEComputerSociety, 2007:459[2015-05-15].http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4135311.DOI: 10.1109/PDP.2007.76

[11]LIUY,WUS,XIONGN.Acache-basedsearchalgorithminunstructuredP2Pnetworks[J/OL].JournalofIntelligentManufacturi-ng,2012,23(6):2101-2107[2015-06-10].http://link.springer.com/10.1007/s10845-011-0603-8http://link.springer.com/10.1007/s10845-011-0603-8.DOI: 10.1007/s10845-011-0603-8

[12]WANGJ.HUAD.InP2PnetworktheresourcesearchMechanisminregardtotrustreputation[C/OL]//ConsumerElectronics.CommunicationsandNetworks,2011InternationalConferenceonIEEE,2011:2273[2015-06-21].http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5768650.DOI: 10.1109/CECNET.2011.5768650

[13]廖季萍. 基于P2P的数据资源共享研究[D]. 长春：长春理工大学, 2014:31-34[2015-07-03].http://cdmd.cnki.com.cn/article/cdmd-10186-1014187407.htm.

[责任编辑：祝剑]

SearchalgorithmbasedonsocialbehaviorforunstructuredP2Pnetwork

ZHUGuohui，ZHANGWuqiang，LUChunlan

(SchoolofCommunicationandInformationEngineering，Xi’anUniversityofPostsandTelecommunications，Xi’an710121)

Abstract:To soup up unstructured peer-to-peer (P2P) network in information searching, a one-hop algorithm based on social behavior patterns is proposed. A friends list and a query records list are introduced to each node in the network, to keep an account of the past search experience for peer selection and route query later. the nodes are rearranged by their list values, and therewith, the lists are updated. As for information searching, there are three methods, which are recommended node based searching, useful friend based searching and neighbour based searching. Simulation results show that, the proposed algorithm can decrease the searching hop, improve the searching rates,reduce the redundant information, and save the memory space.

Keywords:P2P network，social behavior，node relationship，one hop algorithm

doi:10.13682/j.issn.2095-6533.2016.02.022

收稿日期：2015-07-22

基金项目：陕西省教育厅科学研究计划资助项目(07JK377)

作者简介：朱国晖(1969-)，男，博士，副教授，从事移动互联网研究。E-mail：zhgh@xupt.edu.cn 张武强(1988-)，男，硕士研究生，研究方向为移动通信技术及应用。E-mail：524463539@qq.com

中图分类号：TN929.53

文献标识码：A

文章编号：2095-6533(2016)02-0111-04