基于區(qū)域資源聚集的P2P檢索策略

鄭曉健，李 彤，付鐵威

（1.昆明理工大學 津橋學院 計算機科學與電子信息技術系，云南 昆明650106；2.云南大學 軟件學院，云南 昆明650091；3.昆明理工大學 計算中心，云南 昆明650093）

0 引 言

P2P網絡的資源分散性迫使基于洪泛的檢索方法采用大面積擴散檢索信息的方法來查找資源，因此占用了大量網絡帶寬［1］，而大部分節(jié)點間通信的瓶頸是帶寬［2，3］，如何減少P2P網絡的無效通信信息成為了研究的重點。一些研究者利用社會特性構建的網絡模型使節(jié)點轉發(fā)消息的范圍得到較好的控制，改善了網絡的性能［1，2，4］。

文獻［2］提出的SocialSearch模型將具有相似興趣的節(jié)點組成興趣簇，通過比較節(jié)點提出的查詢請求與簇節(jié)點興趣的相似度實現(xiàn)資源檢索。由于未限定簇的規(guī)模，大型簇產生的突發(fā)性簇間通信會使負責簇間消息轉發(fā)的跨簇節(jié)點過載。文獻［1］通過資源引用效果、信任度和動態(tài)響應效率來確定查找路徑，其中引用效果隨時間而衰減，目的是反映信任度的動態(tài)變化。但該方法沒有考慮到訪問量的增加反而會延緩資源引用價值的衰減，而且只通過時間因素對引用價值的衰減方式還會造成部分資源特別是稀有資源的快速邊緣化，不利于資源的有效利用。為此本文提出基于區(qū)域資源聚集的P2P檢索策略 （regional resource aggregation，RRA），根據資源的聚集效應［1］，將分散在網絡節(jié)點中的資源分層、分類聚集為資源分組、區(qū)域和簇，并簡化鏈接結構，讓松散鏈接的小粒度的網絡節(jié)點變成為可伸縮性良好的大粒度的資源實體。各實體設置資源引用價值向量，通過多因素綜合構造的資源引用價值衰減函數(shù)動態(tài)調節(jié)實體的引用價值。查找資源時檢索請求按類匹配區(qū)域資源簇，從簇中選擇引用價值最大的資源組開始尋找要檢索的資源，若查找不成功再將查找范圍逐步擴大到其它資源組或區(qū)域。實驗結果表明，該方法有效控制了消息轉發(fā)范圍、提高了檢索命中率。

1 資源聚集模型

1.1 模型描述

采取了分層聚集和平衡負荷的思想，RRA 模型先將網絡劃分為規(guī)模適度的區(qū)域，區(qū)域內節(jié)點分組聚集為小粒度的資源組，各組設中心節(jié)點再形成環(huán)狀鏈接的大粒度區(qū)域，區(qū)域再度聚集成整個網絡拓撲。如圖1所示為一個P2P 網絡資源及區(qū)域劃分實例，圖2為其區(qū)域資源聚集模型。其中由節(jié)點4為原點形成區(qū)域R1＝ ｛4，1，2，5，3，6，7，10｝，分組R1.G1＝ ｛4，1，2，5｝和R1.G2＝ ｛3，6，7，10｝；由節(jié)點11為原點形成區(qū)域R2＝ ｛11，10，6，9，7，12，14｝，分組R2.G1＝ ｛11，10，6，9｝和R2.G2＝ ｛7，12，14｝，存在跨區(qū)域節(jié)點10，6，7 和暫時孤立節(jié)點8，13。暫時孤立節(jié)點可由區(qū)域歸并，如節(jié)點13 可并入R2，節(jié)點8可并入R1或R2；區(qū)域R1的分組R1.G1和R1.G2連接成環(huán)，區(qū)域R2 的分組R2.G1 和R2.G2 連接成環(huán)，R1.G2，R2.G1和R2.G2包含跨區(qū)域節(jié)點所以連接成環(huán)。

圖1 P2P網絡資源及區(qū)域劃分實例

設網絡G 的資源種類集M ＝｛m1，m2，...，mL｝，G 的資源集合R ＝｛r｜-mi∈M，kind（r）＝mi｝，G 的mi類資源集合Ri＝｛r｜r∈R，kind（r）＝mi｝，R ＝i∪∈LRi且i∩∈LRi＝Φ，R1，R2，...，RL為R 一個劃分；SRiRi為資源實體包含的mi類資源集合，顯然SR1∩SR2∩...∩SRL＝Φ，資源實體的資源集合SR ＝｛r｜r ∈SR1∪SR2∪...∪SRL｝；資源向量RV ＝ （a1，a2，...，aL），其中ai＝｜SRi｜。

定義1 區(qū)域：為與原點有相同距離的節(jié)點的集合，區(qū)域的作用是控制資源實體規(guī)模和負載平衡。

如以節(jié)點4為原點在其2跳范圍內利用深度優(yōu)先法遍歷網絡而形成區(qū)域 ｛4，1，2，5，3，6，7，10｝。

定義2 資源組：區(qū)域內按規(guī)模要求劃定的由若干節(jié)點組成的集合簡稱組，其作用是均衡區(qū)域負荷。

如設定組規(guī)模為4，于是區(qū)域R1 分成資源組R1.G1和R1.G2。

RRA 模型的資源檢索方法是基于引用價值的。從總趨勢上，資源的引用價值隨時間在不停地衰減［1］，但是同時存在多種影響資源引用價值衰減的因素，首先，如果節(jié)點資源不斷被其它節(jié)點訪問，說明該節(jié)點資源的影響力在持續(xù)甚至擴大，引用價值的衰減會延緩；另外，節(jié)點的度具有冪率分布特征，高度數(shù)節(jié)點的命中率較高且比較穩(wěn)定［5－7］，因而其資源的影響力和引用價值能夠長時間維持在較高水平上；最后，資源引用價值的衰減應該進行差異化處理。稀有資源的檢索命中率一般都很低［8，9］，為了保證資源特別是稀有資源不因長期不被訪問而使引用價值迅速衰減，RRA 采取兩段式衰減策略即設置資源引用最低保證值，使資源在沒有達到設定訪問次數(shù)前其引用價值不會快速衰減，超過最低保證值后才正常衰減。

定義3 引用價值衰減函數(shù)：在時間序列｛t1，t2，...，tn｝的時間段ti，引用價值衰減函數(shù)為

式中：Q——節(jié)點訪問次數(shù) （最好為最近時段內的訪問次數(shù)），Deg——節(jié)點度數(shù)，α∈（0，1）為時間衰減系數(shù) （由衰減速度確定），L——系統(tǒng)設定的資源引用最低保證值。

定義4 引用價值向量：資源實體的引用價值向量為

表1 節(jié)點引用價值向量

為了說明式 （1）和式 （2）描述了引用價值與各因素的關系，現(xiàn)用如下2個實驗來說明。測節(jié)點訪問量不變時的情況如圖3所示，實驗參數(shù)見表2。

圖3 節(jié)點訪問量不變

表2 引用價值衰減實驗系統(tǒng)參數(shù)

訪問量隨時間逐漸增加時的情況如圖4所示，其中L＝10，α＝0.8，Q 從0開始每個時段增加10。

不難看出，當節(jié)點訪問量不變時超過最低保證值的資源引用價值隨時間正常衰減，而未超過最低保證值的資源引用價值保持穩(wěn)定。當被測節(jié)點訪問量逐漸增加時資源引用價值的衰減被延緩。

聚集運算是資源形成更大粒度實體的重要步驟，方法是對資源引用向量施行聚集運算。

圖4 節(jié)點訪問量逐漸增加和訪問量不變的對比

定義6 聚集半群：設ARV ＝｛RV1，RV2，...，RVp｝，則（ARV，）為ARV 關于聚集運算︵＋資源引用價值向量聚集半群。

為實現(xiàn)區(qū)域聚集，支持以資源簇為基礎的按類檢索，可構造引用價值矩陣。

定義7 引用價值矩陣

其中：RVi＝（a1i，a2i，...，aLi）為實體i的資源引用價值向量。

引用價值矩陣中RVi可以是某區(qū)域各組或網絡各區(qū)域的引用價值向量，前者為區(qū)域引用價值矩陣，后者進一步形成整個網絡的引用價值矩陣。

通過R1.G1和 成組，并構成區(qū)域R1的引用價值矩

圖5 區(qū)域引用價值矩陣

1.2 模型建立

定義9 節(jié)點：為八元組

Node＝ （ID，T，RLst，IPLst，SLst，N，visited，PLst）其中ID 為節(jié)點編碼，T 為節(jié)點類型 （普通或中心），RLst為區(qū)域信息表，IPLst為節(jié)點IP 地址表 （普通節(jié)點保存所屬組中心節(jié)點IP，中心節(jié)點保存組節(jié)點IP），SLst為節(jié)點的資源信息表，N 為節(jié)點被訪問次數(shù)，visited 為節(jié)點訪問控制符，PLst中心節(jié)點環(huán)狀鏈IP。

定義10 3H 節(jié)點：為資源組內具有超過平均訪問量、平均節(jié)點度數(shù)、并包含超過平均資源類型的節(jié)點。

顯然，資源組的中心節(jié)點要承擔提高資源組檢索命中率、較重的工作負荷的責任，應該設為3H 節(jié)點。

定義11 建模消息：為四元組CM ＝（RCode，BIP，NLst，d），其中RCode 為區(qū)域代碼，BIP 為原點的IP，NLst為節(jié)點信息表，包含區(qū)域中節(jié)點的IP 和資源引用價值向量，d 為建模消息轉發(fā)的規(guī)定深度。

建立模型過程是由原點發(fā)出建模消息，采用深度優(yōu)先法遍歷區(qū)域內規(guī)定深度范圍的節(jié)點完成：①建立引用價值向量，節(jié)點先按照式 （2）建立引用價值向量；②標定區(qū)域范圍，區(qū)域范圍由節(jié)點的區(qū)域代碼標識。通過原點發(fā)送建模消息，在規(guī)定深度內以深度優(yōu)先法遍歷節(jié)點，所到達的節(jié)點設置為區(qū)域范圍；③收集資源信息，接收到建模消息的節(jié)點將IP 和資源引用價值向量嵌入消息的節(jié)點信息表中；④形成區(qū)域，當原點收到傳回的建模消息時將所經歷節(jié)點分組并選出中心節(jié)點，中心節(jié)點與組內節(jié)點交換信息，再將各中心節(jié)點鏈接成環(huán)，聚合成區(qū)域。

RRA 區(qū)域資源聚集算法：

P2P網絡中新節(jié)點的加入和退出頻繁發(fā)生［10］，特別是那些暫時未被區(qū)域覆蓋到的節(jié)點必須及時加入鄰近區(qū)域，因為孤點將會影響檢索命中率。RRA 挑選已經屬于某區(qū)域的鄰近節(jié)點幫助發(fā)送加入區(qū)域請求，獲得批準后就成為區(qū)域節(jié)點。隨后要更新區(qū)域各組引用價值向量，接納節(jié)點的組應立即更新，其它組由更新由路經的消息攜帶更新信息去更新。普通節(jié)點退出時只要更新組中心節(jié)點信息即可。中心節(jié)點退出時要在本組中挑選接任者，再通知組員和區(qū)域各組。

1.3 檢索策略

方法是以資源簇引用價值為基礎，從最大引用價值開始按類匹配資源組。節(jié)點s產生查找資源r的請求q （r，sIP）并發(fā)送給其資源組的中心節(jié)點 （如果是跨區(qū)域節(jié)點可以選擇資源組發(fā)送或都發(fā)送），通過歸類查詢獲知r∈mi，利用中心節(jié)點的區(qū)域引用價值矩陣獲取該區(qū)域的mi資源簇，按照該資源簇的引用價值由高到低的順序向對應的資源組的中心節(jié)點發(fā)送檢索請求或者同時向所有資源組的中心節(jié)點發(fā)送檢索請求，由資源組在組內查詢資源r，然后通過sIP返回查詢結果。如果在規(guī)定時間內未獲得返回消息，則通過跨區(qū)域中心節(jié)點的區(qū)域引用價值矩陣的mi資源簇，選擇其它區(qū)域并發(fā)送查詢請求q （r，sIP），接收到請求的區(qū)域按照上述過程進行檢索。

基于區(qū)域資源簇的檢索算法：

2 實驗與分析

與文獻 ［1，5，11］的NS2網絡模擬軟件相同，采用VC＋＋6.0和SQL Server2008數(shù)據庫開發(fā)的P2P網絡模擬程序進行實驗。每一個節(jié)點具有仿真的網絡連接、計算和存儲能力，在關系數(shù)據庫中建立關系表描述節(jié)點的信息和鄰接關系，節(jié)點間的鄰居關系由鄰接關系表描述，節(jié)點的計算和存儲能力由節(jié)點信息表描述即設節(jié)點計算和存儲能力數(shù)據域，為節(jié)點計算和存儲能力設立由低到高10個等級以表示節(jié)點的能力值。實驗由功能命令完成即執(zhí)行關系查詢。通過關系查詢獲得節(jié)點的鄰居關系，節(jié)點間轉發(fā)消息是查找節(jié)點信息表中鄰居節(jié)點的記錄。由于實際P2P 系統(tǒng)中節(jié)點的加入和退出、節(jié)點間的連接狀況 （網絡延遲或故障）、節(jié)點查找請求的時機、查找的文件等都是隨機的和有時延的，因此程序隨機產生功能命令及其參數(shù)，由相應關系查詢完成，節(jié)點間通信的網絡延遲通過計時器的計時中斷實現(xiàn)。實驗結果表明，模擬程序可以保證單位時間查找請求數(shù)量及網絡消息的隨機性。

資源檢索命中率實驗的系統(tǒng)參數(shù)見表3。節(jié)點信息表記錄節(jié)點信息及其鄰接關系；區(qū)域資源聚集算法建立3種規(guī)模的模擬網絡；以不同速率隨機產生節(jié)點的資源查詢請求，并利用區(qū)域資源簇的檢索算法查找資源；計算出所有規(guī)模的檢索命中率的平均值，將RRA 的實驗結果與SocialSearch和Kazaa進行比較，結果如圖6～圖8所示。

表3 檢索命中率實驗系統(tǒng)參數(shù)

圖6 100節(jié)點模擬

圖7 500節(jié)點模擬

圖8 1000節(jié)點模擬

3 結束語

傳統(tǒng)檢索模型查找資源時需向網絡大范圍擴散檢索消息易引起網絡帶寬資源的大量消耗，本文提出的基于區(qū)域資源聚集的P2P網絡模型較好地解決了該問題。實驗表明，該方法從邏輯上有效縮減了網絡規(guī)模，與對照模型相比明顯減少了消息的擴散量，并提高了檢索命中率。另外，用資源訪問量、引用價值的時間衰減、資源引用最低保證多個因素構造的資源引用價值衰減函數(shù)，更精確的描述了資源引用價值衰減情況，提高了稀有資源檢索命中率。

采用最低保證值來保障新加入節(jié)點的性能的思想還可以運用到P2P網絡信任模型的構造中，對激勵機制的改進有積極意義。

可以看出，RRA 的檢索命中率明顯高于對照者，而且區(qū)域數(shù)和組規(guī)模對實驗結果有較大影響，設置較大區(qū)域數(shù)和組規(guī)?？梢悦黠@減少檢索跳數(shù)，原因是減少了區(qū)域包含的資源組數(shù)，但也明顯增加了跨區(qū)域檢索消息量，從而增加跨區(qū)域節(jié)點的負荷。另外，對部分孤點的檢索需要較大的檢索跳數(shù)，可以通過強制要求節(jié)點及時主動地尋找管轄區(qū)域，并更新引用價值矩陣的方法減少孤點。

［1］HUANG Yongsheng， MENG Xiangwu，ZHANG Yujie.Strategy of content location of P2Pbased on the social network［J］.Journal of Software，2010，21 （10）：2622－2630.

［2］CHEN Zhuo，XUE Feiteng.P2Presource searching strategy based on social characteristics ［J］.Computer Engineering，2012，38 （6）：32－36.

［3］Ye Jianhong，Sun Shixin，Zhang Yunsheng，et al.New selforgnizing P2P Network and routing algorithm ［J］.Application Research of Computers，2009 （1）：306－310.

［4］Li Shaojing，Su Wanli.Research on reputation model based on interest group in P2Pfile sharing system ［J］.Computer Science，2013 （40）：129－132.

［5］ZHANG Tian，MAO Li，ZHANG Zhaoxin.Simplified routing simulation strategy for NS2 ［J］.Computer Engineering and Design，2011 （32）：386－388.

［6］Ma Wenming，Meng Xiangwu，Zhang Yujie，et al.Bidirectional random walk search mechanism for unstructured P2Pnet－work ［J］.Journal of Software，2012，23 （4）：894－911.

［7］Tang Daquan，He Mingke，Meng Qingsong.Research on searching in unstructured P2Pnetwork based on power－law distribution and small world character ［J］.Journal of Computer Research and Development，2007，44 （9）：1566－1571.

［8］Xu Haimei，Lu Xianliang，Ge Lijia，et al，Rare Resource’s sharing mechanism in unstructured P2Pnetworks［J］.Journal of Electronics ＆ Information Technology，2009，31 （8）：2029－2032.

［9］Ma Wenming，Meng Xiangwu，Zhang Yujie，et al.Bidirectional random walk search mechanism for unstructured P2Pnetwork ［J］.Journal of Software，2012，23 （4）：894－911.

［10］Ren Liyong，Lei Ming，Zhang Lei.Data traffic optimization in P2Papplication layer ［J］.Journal of University of Electronic Science and Technology of China，2011，40 （1）：111－115.

［11］WEI Wenhong，LIANG Kejie，WANG Gaocai.CPN：A P2Pmodel based on small－world network ［J］.Computer Engineering，2010，36 （13）：15－17.