鄭曉健，李 彤，付鐵威

（1.昆明理工大學(xué) 津橋?qū)W院 計(jì)算機(jī)科學(xué)與電子信息技術(shù)系，云南 昆明650106；2.云南大學(xué) 軟件學(xué)院，云南 昆明650091；3.昆明理工大學(xué) 計(jì)算中心，云南 昆明650093）

0 引 言

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

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

1 資源聚集模型

1.1 模型描述

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

圖1 P2P網(wǎng)絡(luò)資源及區(qū)域劃分實(shí)例

設(shè)網(wǎng)絡(luò)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為資源實(shí)體包含的mi類資源集合，顯然SR1∩SR2∩...∩SRL＝Φ，資源實(shí)體的資源集合SR ＝｛r｜r ∈SR1∪SR2∪...∪SRL｝；資源向量RV ＝ （a1，a2，...，aL），其中ai＝｜SRi｜。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義7 引用價值矩陣

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

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

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

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

1.2 模型建立

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

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

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

顯然，資源組的中心節(jié)點(diǎn)要承擔(dān)提高資源組檢索命中率、較重的工作負(fù)荷的責(zé)任，應(yīng)該設(shè)為3H 節(jié)點(diǎn)。

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

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

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

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

1.3 檢索策略

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

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

2 實(shí)驗(yàn)與分析

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

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

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

圖6 100節(jié)點(diǎn)模擬

圖7 500節(jié)點(diǎn)模擬

圖8 1000節(jié)點(diǎn)模擬

3 結(jié)束語

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

采用最低保證值來保障新加入節(jié)點(diǎn)的性能的思想還可以運(yùn)用到P2P網(wǎng)絡(luò)信任模型的構(gòu)造中，對激勵機(jī)制的改進(jìn)有積極意義。

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

［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.