混合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.