無(wú)結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)資源聚集模型

2014-03-13 13:28:40鄭曉健等

價(jià)值工程 2014年5期

鄭曉健等

摘要：針對(duì)P2P網(wǎng)絡(luò)規(guī)模的擴(kuò)大使基于洪泛的檢索方法易產(chǎn)生嚴(yán)重的通信消耗問(wèn)題，提出一種區(qū)域資源聚集模型，對(duì)非結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中分散的資源進(jìn)行分層聚集，形成大粒度的資源實(shí)體，從而顯著縮減網(wǎng)絡(luò)規(guī)模，并綜合考慮影響資源檢索命中率的多種因素，構(gòu)造資源引用價(jià)值衰減函數(shù)來(lái)調(diào)節(jié)描述資源實(shí)體的引用價(jià)值向量和矩陣。檢索時(shí)從區(qū)域資源簇中具有最大引用價(jià)值的資源組開(kāi)始逐步尋找所要的資源。實(shí)驗(yàn)證明，該方法的消息轉(zhuǎn)發(fā)范圍得到控制、檢索命中率有顯著提高。

關(guān)鍵詞： P2P網(wǎng)絡(luò)；資源聚集；引用價(jià)值衰減；消息擴(kuò)散

中圖分類號(hào)：TP393.01 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2014）05-0013-05

0 引言

隨著P2P網(wǎng)絡(luò)規(guī)模的擴(kuò)大和資源的分散存儲(chǔ)使節(jié)點(diǎn)的相鄰節(jié)點(diǎn)大量增加且節(jié)點(diǎn)間的最大路徑增大，洪泛和隨機(jī)漫步等傳統(tǒng)檢索方法因此產(chǎn)生了大量無(wú)效通信，占用了網(wǎng)絡(luò)帶寬[1，7，11]，而大部分網(wǎng)絡(luò)節(jié)點(diǎn)的瓶頸在于通信時(shí)的帶寬，計(jì)算和存儲(chǔ)能力相比帶寬約束可以忽略[2，12]，因此提高有效通信成為研究的焦點(diǎn)。

一些P2P網(wǎng)絡(luò)利用社會(huì)特性構(gòu)建新型網(wǎng)絡(luò)結(jié)構(gòu)和調(diào)整查找策略，節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的范圍得到控制，使情況有所好轉(zhuǎn)[1，3]。

文獻(xiàn)[3]提出的Social Search模型將具有類似興趣的節(jié)點(diǎn)組成興趣簇，通過(guò)比較查詢請(qǐng)求與簇中節(jié)點(diǎn)的興趣相似度實(shí)現(xiàn)資源檢索，其中跨簇節(jié)點(diǎn)負(fù)責(zé)簇間消息的轉(zhuǎn)發(fā)。由于未限定簇的規(guī)模，大型簇產(chǎn)生的突發(fā)性簇間通信會(huì)使跨簇節(jié)點(diǎn)過(guò)載。

文獻(xiàn)[4]提出建立一個(gè)可分層的樹(shù)型自治系統(tǒng)模型，并給出相應(yīng)的路由發(fā)現(xiàn)和更新算法，該模型可伸縮性好，通過(guò)動(dòng)態(tài)調(diào)節(jié)保證路由效率。

文獻(xiàn)[1]提出一種通過(guò)資源引用效果、信任度和動(dòng)態(tài)響應(yīng)效率多因素選擇查找路徑的方法，并且發(fā)現(xiàn)引用效果會(huì)隨時(shí)間而衰減，因此采用基于時(shí)間的衰減函數(shù)對(duì)資源檢索進(jìn)行修正，使命中率得到提高。但該方法沒(méi)有考慮資源訪問(wèn)量的增加會(huì)延緩引用價(jià)值的衰減，另外，只通過(guò)時(shí)間因素對(duì)資源引用價(jià)值的衰減方式會(huì)造成部分資源特別是稀有資源的快速邊緣化，不利于資源的有效利用。為此本文提出P2P網(wǎng)絡(luò)區(qū)域資源聚集模型（Regional Resource Aggregation， RRA），根據(jù)資源的聚集效應(yīng)[1]，將分散在網(wǎng)絡(luò)節(jié)點(diǎn)中的資源分層、分類聚集為資源分組、區(qū)域和簇，并簡(jiǎn)化鏈接結(jié)構(gòu)，讓松散鏈接的小粒度的網(wǎng)絡(luò)節(jié)點(diǎn)變成為可伸縮性良好的大粒度的資源實(shí)體。各實(shí)體設(shè)置資源引用價(jià)值向量，通過(guò)多因素綜合構(gòu)造的資源引用價(jià)值衰減函數(shù)動(dòng)態(tài)調(diào)節(jié)實(shí)體的引用價(jià)值。查找資源時(shí)檢索請(qǐng)求按類匹配區(qū)域資源簇，從簇中選擇引用價(jià)值最大的資源組開(kāi)始尋找要檢索的資源，若查找不成功再將查找范圍逐步擴(kuò)大到其他資源組或區(qū)域。實(shí)驗(yàn)結(jié)果表明，該方法有效控制了消息轉(zhuǎn)發(fā)范圍、提高了檢索命中率。

1 區(qū)域資源聚集模型的建立

1.1 模型描述

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

P2P網(wǎng)絡(luò)中新節(jié)點(diǎn)的加入和退出是頻繁發(fā)生的事件[]，特別是對(duì)于那些暫時(shí)未被區(qū)域覆蓋到的節(jié)點(diǎn)必須及時(shí)加入到確定的區(qū)域內(nèi)，因?yàn)楣曼c(diǎn)將會(huì)影響檢索命中率。RRA采用就近加入?yún)^(qū)域的方法即挑選已經(jīng)屬于某區(qū)域的鄰近節(jié)點(diǎn)幫助發(fā)送加入?yún)^(qū)域請(qǐng)求，獲得批準(zhǔn)后即可成為區(qū)域節(jié)點(diǎn)。

加入過(guò)程需要更新區(qū)域各資源組引用價(jià)值向量，接納節(jié)點(diǎn)的中心節(jié)點(diǎn)消息可立即更新，其他中心節(jié)點(diǎn)的更新由路經(jīng)的消息攜帶更新信息去各中心節(jié)點(diǎn)更新。

節(jié)點(diǎn)退出，普通節(jié)點(diǎn)的退出先要更新資源組中心節(jié)點(diǎn)消息，中心節(jié)點(diǎn)的更新需要先在本資源組挑選接任者，再通知組員和區(qū)域各組，更新方法與加入時(shí)相同。

1.3 基于區(qū)域資源簇的檢索策略

RRA模型以資源簇引用價(jià)值為基礎(chǔ)，從最大引用價(jià)值開(kāi)始按類匹配資源組的檢索策略。

節(jié)點(diǎn)s產(chǎn)生查找資源r的請(qǐng)求q（r，sIP）并發(fā)送給其資源組的中心節(jié)點(diǎn)（如果是跨區(qū)域節(jié)點(diǎn)可以選擇資源組發(fā)送或都發(fā)送），通過(guò)歸類查詢獲知r∈mi，利用中心節(jié)點(diǎn)的區(qū)域引用價(jià)值矩陣獲取該區(qū)域的mi資源簇，按照該資源簇的引用價(jià)值由高到低的順序向?qū)?yīng)的資源組的中心節(jié)點(diǎn)發(fā)送檢索請(qǐng)求或者同時(shí)向所有資源組的中心節(jié)點(diǎn)發(fā)送檢索請(qǐng)求，由資源組在組內(nèi)查詢資源r，然后通過(guò)sIP返回查詢結(jié)果。

如果在規(guī)定時(shí)間內(nèi)未獲得返回消息，則通過(guò)跨區(qū)域中心節(jié)點(diǎn)的區(qū)域引用價(jià)值矩陣的mi資源簇，選擇其他區(qū)域并發(fā)送查詢請(qǐng)求q（r，sIP），接收到請(qǐng)求的區(qū)域按照上述過(guò)程進(jìn)行檢索。

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

2 實(shí)驗(yàn)結(jié)果與分析

借鑒文獻(xiàn)[1，6，13]提出的簡(jiǎn)化的NS2網(wǎng)絡(luò)模擬軟件，采用VC++6.0和SQL Server2008數(shù)據(jù)庫(kù)開(kāi)發(fā)的P2P網(wǎng)絡(luò)模擬程序進(jìn)行實(shí)驗(yàn)。

程序讓每一個(gè)節(jié)點(diǎn)具有模擬的網(wǎng)絡(luò)連接、計(jì)算和存儲(chǔ)能力，方法是在關(guān)系數(shù)據(jù)庫(kù)中建立關(guān)系表描述節(jié)點(diǎn)的信息和鄰接關(guān)系，節(jié)點(diǎn)間的鄰居關(guān)系由鄰接關(guān)系表描述，節(jié)點(diǎn)的計(jì)算和存儲(chǔ)能力由節(jié)點(diǎn)信息表描述即設(shè)節(jié)點(diǎn)計(jì)算和存儲(chǔ)能力數(shù)據(jù)域，對(duì)節(jié)點(diǎn)計(jì)算和存儲(chǔ)能力的量化方法是設(shè)立由低到高10個(gè)等級(jí)以表示節(jié)點(diǎn)的能力值。endprint

實(shí)驗(yàn)過(guò)程是用功能命令完成，執(zhí)行命令就是執(zhí)行關(guān)系查詢。通過(guò)關(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)查找請(qǐng)求的時(shí)機(jī)、查找的文件等都是隨機(jī)的和有一定時(shí)延的，因此由程序隨機(jī)產(chǎn)生功能命令及其參數(shù)，由相應(yīng)關(guān)系查詢完成，節(jié)點(diǎn)間通信的網(wǎng)絡(luò)延遲通過(guò)計(jì)時(shí)器的計(jì)時(shí)中斷實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明模擬程序可以保證P2P規(guī)模和單位時(shí)間查找請(qǐng)求數(shù)量及網(wǎng)絡(luò)消息的隨機(jī)性。

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

可以看出，RRA的檢索命中率有明顯提高，而且區(qū)域數(shù)和組規(guī)模對(duì)實(shí)驗(yàn)結(jié)果有較大影響，設(shè)置較大區(qū)域數(shù)和組規(guī)模可以明顯減少檢索跳數(shù)，原因是減少了區(qū)域包含的資源組數(shù)，但也明顯增加了跨區(qū)域檢索消息量，從而增加跨區(qū)域節(jié)點(diǎn)的負(fù)荷。

另外，對(duì)部分孤點(diǎn)的檢索需要較大的檢索跳數(shù)，可以通過(guò)強(qiáng)制要求節(jié)點(diǎn)及時(shí)主動(dòng)地尋找管轄區(qū)域，并更新引用價(jià)值矩陣的方法減少孤點(diǎn)。

3 結(jié)束語(yǔ)

本文提出建立區(qū)域資源聚集模型，實(shí)現(xiàn)P2P網(wǎng)絡(luò)資源實(shí)體的聚集方法。

通過(guò)定義的資源聚集運(yùn)算實(shí)現(xiàn)了資源的分層聚集，資源組中心節(jié)點(diǎn)保存區(qū)域資源引用價(jià)值矩陣，并通過(guò)資源簇實(shí)現(xiàn)資源的按類檢索，RRA模型從邏輯上縮減網(wǎng)絡(luò)規(guī)模，使按照資源類型的查詢更加高效，較好地控制了無(wú)效網(wǎng)絡(luò)通信消息的擴(kuò)散，提高了稀有資源檢索命中率。

參考文獻(xiàn)：

[1]Huang Yong-Sheng， Meng Xiang-Wu， Zhang Yu-Jie. Strategy of Content Location of P2P Based on the Social Network[J]. Journal of Software， 2010，21（10）：2622-2630.

[2]Ge Zihui，F(xiàn)igueiredo D R Jaiswai S，et al.Modeling Peer to Peer File Sharing Systems[c]//Proc of the 22nd Annual Joint Conference on IEEE Computer and Communications Societeis，San francisco：IEEE Press，2003：2188-2198.

[3]Chen Zhuo， Xue Fei-teng. P2P Resource Searching Strategy Based on Social Characteristics[J]. Computer Engineering，2012，38（6）：32-36.

[4]Ye Jian-Hong，Sun Shi-xin，Zhang Yun-sheng，et al.New self-orgnizing P2P Network and Routing Agarithm[J].Application Research of Computers，2009，26（1）：306-310.

[5]Li Shao-jing，Su Wan-li.Research on Reputation Model Based on Interest Group in P2P File Sharing System[J].Computer Science，2013，40（2）：129-132.

[6]Zhang Tian， Mao Li， Zhang Zhao-xin. Simplified routing simulation strategy for NS2[J]. Computer Engineering and Design，2011，32（2）：386-388.

[7]Ma Wen-Ming， Meng Xiang-Wu， Zhang Yu-Jie， et al. Bidirectional Random Walk Search Mechanism for Unstructured P2P Network [J]. Journal of Software， 2012， 23（4）： 894-911.

[8]Tang Daquan， He Mingke， Meng Qingsong. Research on Searching in Unstructured P2P Network Based on Power-Law Distribution and Small World Character [J]. Journal of Computer Research and Development， 2007， 44（9）：1566-1571.

[9]Xu Hai-Mei，Lu Xian-Liang，Ge Li-Jia，et al，Rare Resources sharing mechanism in unstructured P2P networks[J].Journal of electronics & information technology，2009，31（8）：2029-2032.

[10]Ma Wen-Ming， Meng Xiang-Wu， Zhang Yu-Jie， et al. Bidirectional Random Walk Search Mechanism for Unstructured P2P Network [J]. Journal of Software， 2012， 23（4）： 894-911.

[11]Ren Li-yong， Lei Ming， Zhang Lei. Data Traffic Optimization in P2P Application Layer[J]. Journal of University of Electronic Science and Technology of China，2011，40（1）：111-115.

[12]Wei Wen-hong， Liang Ke-jie， Wang Gao-cai.CPN：A P2P Model Based on Small-world Network[J]. Computer Engineering，2010，36（13）：15-17.

[13]Hoong P K， Matsuo H. Push-pull two-layer super-peer based P2P live media streaming[J]. Journal of Applied Sciences， 2008， 8（4）： 585-593.endprint