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

朱國暉，張武強(qiáng)，魯春蘭

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

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

朱國暉，張武強(qiáng)，魯春蘭

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

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

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

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

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

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

1單跳算法模型

1.1單跳算法思想

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

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

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

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

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

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

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

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

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

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

1.3算法流程

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

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

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

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

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

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

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

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

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

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

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

3結(jié)束語

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

參考文獻(xiàn)

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

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

[3]何明, 張玉潔, 孟祥武. 面向用戶需求的非結(jié)構(gòu)化P2P資源定位泛洪策略[J/OL]. 軟件學(xué)報(bào),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)絡(luò)中基于節(jié)點(diǎn)的MQR算法設(shè)計(jì)與實(shí)現(xiàn)[J/OL].計(jì)算機(jī)工程,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)絡(luò)基于馬爾科夫鏈的搜索算法研究[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)絡(luò)的一種改進(jìn)搜索算法[J/OL].計(jì)算機(jī)與現(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]陳香香, 吳開貴, 陳明. 基于興趣域的對(duì)等網(wǎng)絡(luò)動(dòng)態(tài)搜索機(jī)制[J/OL]. 計(jì)算機(jī)應(yīng)用研究, 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]. 長春：長春理工大學(xué), 2014:31-34[2015-07-03].http://cdmd.cnki.com.cn/article/cdmd-10186-1014187407.htm.

[責(zé)任編輯：祝劍]

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

基金項(xiàng)目：陜西省教育廳科學(xué)研究計(jì)劃資助項(xiàng)目(07JK377)

作者簡介：朱國暉(1969-)，男，博士，副教授，從事移動(dòng)互聯(lián)網(wǎng)研究。E-mail：zhgh@xupt.edu.cn 張武強(qiáng)(1988-)，男，碩士研究生，研究方向?yàn)橐苿?dòng)通信技術(shù)及應(yīng)用。E-mail：524463539@qq.com

中圖分類號(hào)：TN929.53

文獻(xiàn)標(biāo)識(shí)碼：A

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