一種基于社會行為的非結(jié)構(gòu)化P2P搜索算法

朱國暉，張武強，魯春蘭

(西安郵電大學 通信與信息工程學院，陜西 西安 710121)

一種基于社會行為的非結(jié)構(gòu)化P2P搜索算法

朱國暉，張武強，魯春蘭

(西安郵電大學 通信與信息工程學院，陜西 西安 710121)

摘要:針對非結(jié)構(gòu)化對等網(wǎng)絡(P2P)中信息資源搜索效率低的問題，給出一種基于社會行為的單跳算法。為網(wǎng)絡中每個節(jié)點引入朋友列表和查詢記錄列表，記錄過去的搜索經(jīng)驗，用于同伴選擇和路線查詢，之后排列節(jié)點價值，更新列表。利用基于推薦節(jié)點搜索、基于有用的朋友節(jié)點搜索和基于鄰居節(jié)點搜索3種機制，搜索所需資源。仿真結(jié)果表明，所給算法可減少搜索跳數(shù)，提高搜索成功率，減少冗余消息，節(jié)省內(nèi)存空間。

關(guān)鍵詞:P2P網(wǎng)絡；社會行為；節(jié)點關(guān)系；單跳算法

P2P網(wǎng)絡[1]是一種節(jié)點高度自治的分布式結(jié)構(gòu)網(wǎng)絡，相互連接的各個節(jié)點之間可以實現(xiàn)實時通信，已經(jīng)廣泛應用在資源共享、搜索引擎、即時通訊和協(xié)同工作等各個方面[2]。P2P網(wǎng)絡分為結(jié)構(gòu)化和非結(jié)構(gòu)化兩種模式[3]，結(jié)構(gòu)化P2P網(wǎng)絡以哈希函數(shù)實現(xiàn)節(jié)點和文件的映射，能夠在確定的跳數(shù)內(nèi)定位內(nèi)容，但很難有效地支持模糊搜索。然而，非結(jié)構(gòu)化P2P網(wǎng)絡中節(jié)點之間不存在相互約束關(guān)系，資源在網(wǎng)絡中隨機存貯，具有較強的容錯能力，使用戶能夠快速準確的搜索到所需資源，提高了網(wǎng)絡資源的利用率。洪泛算法[4]是一種最基本的隨機搜索算法，消息覆蓋率高，算法適應性好，但存在冗余消息過多，嚴重浪費網(wǎng)絡帶寬和計算能力等缺點，限制了網(wǎng)絡的可擴展性。隨機漫步算法[5]是對洪泛算法的改進，將消息隨機轉(zhuǎn)發(fā)給某些鄰居節(jié)點，減少了冗余消息，但是搜索成功率不高。

社會行為模式[6]依賴于社會關(guān)系網(wǎng)中人們的背景、友誼關(guān)系、共同利益和共享經(jīng)歷，等同于非結(jié)構(gòu)化P2P網(wǎng)絡中節(jié)點的名稱、興趣、所需資源和搜索歷史，基于人們的記憶能力，節(jié)點之間相互聯(lián)系，學習過去的搜索經(jīng)驗和歷史，建立朋友關(guān)系并分享相似的興趣，從而形成索引列表來記憶和修改自己在網(wǎng)絡搜索中獲得的信息。同時，通過資源索引信息來區(qū)分與其他節(jié)點的聯(lián)系?；谂d趣域的搜索算法[7]，與相似興趣的節(jié)點相互分享所需資源，從而提高搜索效率，減少網(wǎng)絡流量；基于社會行為的搜索算法[8]，引入社會網(wǎng)理論，模擬人與人之間的共同利益、友誼和記憶能力，建立節(jié)點之間的聯(lián)系，學習過去的搜索經(jīng)驗和歷史，從而形成索引列表來提高搜索效率；兩跳算法[9]是基于社會行為模式，與鄰居節(jié)點建立朋友關(guān)系，相互學習，并存儲查詢記錄，從而快速搜索到所需資源。但是，上述3種算法在搜索跳數(shù)、網(wǎng)絡存儲空間和網(wǎng)絡可伸縮性等方面還有待于提高。

本文擬基于社會行為模式，對兩跳算法加以改進，提出一種單跳算法。在每個節(jié)點引入朋友列表和查詢記錄列表，通過記錄過去的搜索經(jīng)驗選擇同伴和查詢路線，使節(jié)點之間建立聯(lián)系，并排列節(jié)點的價值更新列表，以期節(jié)省內(nèi)存空間。

1單跳算法模型

1.1單跳算法思想

網(wǎng)絡節(jié)點在一次成功搜索后，會在自己的朋友列表中記錄此次搜索資源信息，同時被搜索節(jié)點也會在查詢記錄列表中記錄此次搜索信息，主動節(jié)點和被動節(jié)點在多次搜索過程中形成朋友列表和查詢記錄列表兩張路由表。節(jié)點的新一次搜索就可根據(jù)查詢記錄列表信息直接確定目標資源節(jié)點，從而實現(xiàn)一跳鎖定資源，這就是單跳算法的基本原理。與此同時，節(jié)點在每次搜索中會評價朋友對自己的重要程度，刪除一些列表里面無用的節(jié)點信息，從而節(jié)省內(nèi)存空間。

當查詢節(jié)點發(fā)起查詢時，先使用基于推薦節(jié)點搜索[10](RecommendedNodeBasedSearch，RBS)開始搜索，如果有推薦節(jié)點查詢記錄，就直接連接推薦節(jié)點獲得所需資源。如果沒有推薦節(jié)點的查詢記錄，使用基于有用的朋友搜索[11](UsefulFriendBasedSearch，UBS)連接朋友節(jié)點。如果節(jié)點既沒有推薦節(jié)點也沒有朋友節(jié)點，將查詢發(fā)送到n個(轉(zhuǎn)發(fā)節(jié)點個數(shù))鄰居節(jié)點，使用基于鄰居搜索[12](NeighbourBasedSearch，NBS)，否則認定搜索失敗。設(shè)3種搜索機制的成功次數(shù)分別為R、U、N，總搜索次數(shù)為T，則搜索的平均成功率可表示為[9]

1.2節(jié)點列表的形成

網(wǎng)絡中節(jié)點通過模仿社會行為中人們的記憶能力，建立索引列表來記錄和修改自己在網(wǎng)絡搜索中獲得的信息，并引入兩張列表記錄過去的搜索經(jīng)驗選擇同伴和查詢路線，同時排列節(jié)點的價值更新列表，節(jié)省內(nèi)存空間。

如圖1所示，Ni代表節(jié)點名稱，Ri代表節(jié)點所擁有資源名稱。初始狀態(tài)下，有用的朋友列表和每個節(jié)點的查詢記錄列表是空的。

設(shè)置轉(zhuǎn)發(fā)節(jié)點個數(shù)為2，發(fā)出3次搜索請求。

第1次搜索，節(jié)點N1發(fā)出請求搜索資源R8，N1把請求消息分別轉(zhuǎn)發(fā)給N2和N3，從N2獲得資源R8，這時N1更新自己的資源信息擁有R1和R8，并更新朋友列表，把N2記為自己的朋友，價值+1。同時，在N3中沒有找到資源R8，這時N3更新自己的被查詢列表，記錄N1查找過R8。

第2次搜索，節(jié)點N4搜索資源R8，此時N4有3個鄰居節(jié)點。假設(shè)N4向N3和N5發(fā)出搜索請求，從N5獲得資源R8，這時N4更新自己的資源信息擁有R2和R8，并更新朋友列表，把N5記為自己的朋友，價值+1，同時N4向N3發(fā)出請求時，發(fā)現(xiàn)N1曾經(jīng)向N3發(fā)出過同樣的請求，因此N4直接跟N1建立聯(lián)系，獲得R8，并更新朋友列表，把N1記為自己的朋友，價值+1，這樣從邏輯上來說直接跳過N3，通過一跳找到N1中的資源R8。

第3次搜索，節(jié)點N3搜索資源R8，發(fā)現(xiàn)N1曾經(jīng)向自己發(fā)出過同樣的請求，因此就直接與N1建立聯(lián)系獲得R8，并更新自己的資源信息，同時更新朋友列表，把N1記為自己的朋友，價值+1。

圖1　朋友列表和查詢記錄列表的形成過程

1.3算法流程

當節(jié)點發(fā)出查詢請求時，按照RBS、UBS和NBS3種不同的搜索機制依次進行查詢，直到得出所需資源。假設(shè)節(jié)點N3發(fā)出請求，搜索資源R8，設(shè)置轉(zhuǎn)發(fā)給鄰居節(jié)點的個數(shù)為n，具體執(zhí)行步驟如圖2所示。

圖2　算法執(zhí)行示意圖

2仿真結(jié)果與分析

采用Peersim仿真工具，按照Cycle-based模式[13]進行模擬實驗，實驗中設(shè)置該網(wǎng)絡環(huán)境中共有500個節(jié)點，初始文件種數(shù)為100，即100個文件都是不同的。初始文件的個數(shù)由系統(tǒng)隨機生成，并隨機分布到各個節(jié)點上，每個節(jié)點上最多生成不多于5個文件，同一個節(jié)點上相同文本只存在一份。每個周期發(fā)出200個查詢請求，一輪結(jié)束以后再進行下一輪實驗，實驗一共進行10個周期，每次查詢設(shè)置轉(zhuǎn)發(fā)節(jié)點比例。

實驗中分別從搜索的平均成功率、平均路徑長度和平均消息數(shù)3個性能指標對比單跳算法、兩跳算法和隨機漫步算法。對比結(jié)果分別如圖3、圖4和圖5所示。

從圖3中可以看出隨著消息轉(zhuǎn)發(fā)節(jié)點比例的增加，3種算法的搜索平均成功率逐漸增加。當轉(zhuǎn)發(fā)節(jié)點比例增加時，查詢請求會轉(zhuǎn)發(fā)給更多的節(jié)點，從而搜索成功率提高明顯。當轉(zhuǎn)發(fā)比例相同時，單跳算法由于利用3種不同的搜索機制輪流搜索，搜索更加全面，平均成功率更高一些。因此，單跳算法在搜索平均成功率方面要優(yōu)于其他兩種算法。

圖3　平均成功率對比結(jié)果

圖4　平均路徑長度對比結(jié)果

由圖4可知，兩跳算法中資源在第一或第二跳會被發(fā)現(xiàn)，資源的平均路徑長度在1和2之間，而且隨著轉(zhuǎn)發(fā)節(jié)點的增多，搜索到資源的速度就越快，平均搜索跳數(shù)基本不變，接近于1。然而，單跳算法可直接根據(jù)查詢記錄列表鎖定目標資源節(jié)點，資源的平均路徑長度等于1。隨機漫步算法在平均路徑長度方面要遠大于前兩者。因此，單跳算法減少了搜索跳數(shù)，縮短了平均路徑長度。

圖5　平均消息量對比結(jié)果

從圖5可以看出，平均每個節(jié)點發(fā)送和接收消息的數(shù)量隨著轉(zhuǎn)發(fā)節(jié)點比例的增加而增加，隨機漫步算法因為要轉(zhuǎn)發(fā)給多個節(jié)點，消息量較大；兩跳和單跳算法消息量相對較少，同時在轉(zhuǎn)發(fā)比例增加到一定的值時，單跳算法的消息量基本趨于平衡。因此，單跳算法產(chǎn)生更少的冗余消息，節(jié)省了內(nèi)存空間。

3結(jié)束語

基于社會行為的單跳算法，在兩跳算法的基礎(chǔ)上，增加查詢記錄列表，排列節(jié)點的價值，利用基于推薦節(jié)點搜索、基于有用的朋友節(jié)點搜索和基于鄰居節(jié)點搜索3種搜索機制提高搜索性能。仿真結(jié)果表明，單跳算法的搜索平均成功率高于隨機漫步算法和兩跳算法，并且減少了搜索跳數(shù)，縮短了平均路徑長度。同時，節(jié)點平均發(fā)送和接收的消息數(shù)量相對較少，減少了冗余消息，節(jié)省了內(nèi)存空間。

參考文獻

[1]房佩.非結(jié)構(gòu)化P2P網(wǎng)絡中資源搜索算法研究[D].西安:陜西師范大學,2013:8-52[2015-03-18].http://cdmd.cnki.com.cn/Article/CDMD-10718-1014106666.htm.

[2]周韜.P2P網(wǎng)絡資源搜索方法的研究[D]. 北京:北京交通大學, 2015:6-67[2015-04-10].http://cdmd.cnki.com.cn/Article/CDMD-10004-1015545303.htm.

[3]何明, 張玉潔, 孟祥武. 面向用戶需求的非結(jié)構(gòu)化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]謝晃, 張昱, 王云凱.非結(jié)構(gòu)化P2P網(wǎng)絡中基于節(jié)點的MQR算法設(shè)計與實現(xiàn)[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]劉璇, 于雙元. 非結(jié)構(gòu)化P2P網(wǎng)絡基于馬爾科夫鏈的搜索算法研究[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]葉培順.非結(jié)構(gòu)化P2P網(wǎng)絡的一種改進搜索算法[J/OL].計算機與現(xiàn)代化，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]陳香香, 吳開貴, 陳明. 基于興趣域的對等網(wǎng)絡動態(tài)搜索機制[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的數(shù)據(jù)資源共享研究[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-)，男，博士，副教授，從事移動互聯(lián)網(wǎng)研究。E-mail：zhgh@xupt.edu.cn 張武強(1988-)，男，碩士研究生，研究方向為移動通信技術(shù)及應用。E-mail：524463539@qq.com

中圖分類號：TN929.53

文獻標識碼：A

文章編號：2095-6533(2016)02-0111-04