鄭曉健，鄭曉蘭，李 彤，付鐵威，龐淑英

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

0 引 言

為了使非結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)的資源搜索算法具有更高的命中率，研究者們的思路轉(zhuǎn)向構(gòu)造良好的P2P覆蓋網(wǎng)絡(luò)拓?fù)鋪?lái)改善查詢算法的性能［1，2，16］。人們發(fā)現(xiàn)傳統(tǒng)的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)完全隨機(jī)的拓?fù)浜秃榉翰樵兯惴ㄔ谙到y(tǒng)性能上的表現(xiàn)不能令人滿意，在查找流行資源時(shí)可以獲得高命中率，但檢索稀有資源時(shí)的效果并不好，統(tǒng)計(jì)數(shù)據(jù)顯示命中率還達(dá)不到82%，而且網(wǎng)絡(luò)帶寬 的 消 耗 很 大［1－5，9，16］?；谒饕北揪彺娴姆椒榇颂峁┝溯^好的解決方案，即在網(wǎng)絡(luò)中擴(kuò)散稀有資源的索引，使查詢包在路由過(guò)程中依靠索引盡快找到資源［1，2，9］。問(wèn)題是擴(kuò)散范圍該如何控制呢？因?yàn)閷⑺邢∮匈Y源的索引副本都到擴(kuò)散網(wǎng)絡(luò)節(jié)點(diǎn)中去固然能提高搜索命中率，但也會(huì)消耗節(jié)點(diǎn)的大量存儲(chǔ)和網(wǎng)絡(luò)的帶寬資源［1，2］。

本文的思想就是在擴(kuò)散稀有資源索引副本時(shí)利用非結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)搜索具有的局部性［3］來(lái)控制范圍。大量研究發(fā)現(xiàn)P2P搜索具有局部性，合理運(yùn)用不同的局部性可以顯著提高非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的資源搜索命中率［3］。具有代表性的是文獻(xiàn) ［1，2］利用搜索的空間局部性提出的在節(jié)點(diǎn)中設(shè)立分級(jí)索引副本表并將稀有資源的索引副本分類(lèi)擴(kuò)散到節(jié)點(diǎn)的方法。文獻(xiàn) ［1］提出兩站式索引副本算法（twohops index replication，THIR），第1站設(shè)在每個(gè)節(jié)點(diǎn)，存儲(chǔ)所有直接鄰居的稀缺資源索引副本。第2 站設(shè)超級(jí)節(jié)點(diǎn)，存儲(chǔ)兩步（two hops）之內(nèi)的超級(jí)節(jié)點(diǎn)的索引副本。遍歷所有超級(jí)節(jié)點(diǎn)就可以找到在線資源。文獻(xiàn) ［2］針對(duì)THIR 算法存在超節(jié)點(diǎn)負(fù)荷過(guò)重和單點(diǎn)易失性問(wèn)題提出了改進(jìn)算法（new layered two－h(huán)ops index replication，NLIR），第1 站仍設(shè)在每個(gè)節(jié)點(diǎn)，鄰居節(jié)點(diǎn)的稀有資源索引副本存儲(chǔ)在其索引副本表（index replication table，IRT）中，第2站按照節(jié)點(diǎn)的異構(gòu)性將節(jié)點(diǎn)分為三級(jí)，各級(jí)別分配數(shù)量不等的索引副本即由網(wǎng)絡(luò)帶寬和存儲(chǔ)費(fèi)用構(gòu)成多階段決策模型，用動(dòng)態(tài)規(guī)劃法求出分配數(shù)量的最優(yōu)解。該方法的搜索命中率略高于THIR，但算法較復(fù)雜且耗時(shí)。盡管文獻(xiàn)［1，2］等兩站式索引副本擴(kuò)散方法存在以上問(wèn)題，但說(shuō)明可以通過(guò)改變網(wǎng)絡(luò)局部的檢索環(huán)境來(lái)改善系統(tǒng)整體性能。本文提出的高頻訪問(wèn)區(qū)域索引副本擴(kuò)散算法（the diffusion of high frequency access areas index replication，DHFA2IR）是利用高頻度訪問(wèn)節(jié)點(diǎn)在網(wǎng)絡(luò)中聚集的局部特性實(shí)現(xiàn)的。實(shí)驗(yàn)說(shuō)明在TTL 受限時(shí)算法比THIR 有更高的搜索命中率。

1 高頻訪問(wèn)區(qū)域發(fā)現(xiàn)算法

1.1 搜索的局部性

由文獻(xiàn)［3］可知局部性是P2P 搜索具有的典型特征。P2P搜索中存在多種局部性，如時(shí)間局部性、空間局部性、興趣局部性和語(yǔ)義局部性等［3］。實(shí)驗(yàn)表明還有一種因頻繁訪問(wèn)節(jié)點(diǎn)而引發(fā)的高頻度訪問(wèn)節(jié)點(diǎn)在網(wǎng)絡(luò)局部聚集的特性。通常情況下，高度數(shù)節(jié)點(diǎn)具有高訪問(wèn)概率、較好的網(wǎng)絡(luò)帶寬、在線時(shí)間較長(zhǎng)且穩(wěn)定、處理速度快，而低度數(shù)節(jié)點(diǎn)的網(wǎng)絡(luò)處理能力較差且不穩(wěn)定［3］。高度數(shù)的節(jié)點(diǎn)易成為高頻度訪問(wèn)節(jié)點(diǎn)，原因在于網(wǎng)絡(luò)的冪律分布特性［2，3，9］。若以隨機(jī)漫步或洪泛方式訪問(wèn)高度數(shù)節(jié)點(diǎn)后，其周?chē)瑯訒?huì)出現(xiàn)更多高頻度訪問(wèn)節(jié)點(diǎn)，且隨著訪問(wèn)量的增加高頻訪問(wèn)節(jié)點(diǎn)還會(huì)逐漸擴(kuò)散到更大范圍。這種高頻度訪問(wèn)節(jié)點(diǎn)在局部聚集的現(xiàn)象稱為高頻訪問(wèn)節(jié)點(diǎn)的聚集局部性。利用該特性，在高度數(shù)節(jié)點(diǎn)產(chǎn)生的高頻度訪問(wèn)節(jié)點(diǎn)中選擇部分穩(wěn)定性較高的節(jié)點(diǎn)作為索引副本擴(kuò)散的目標(biāo)，就能實(shí)現(xiàn)提高索引命中率和平衡負(fù)載的目的，另外還因非結(jié)構(gòu)P2P搜索本身所具有的高魯棒性而使節(jié)點(diǎn)在動(dòng)態(tài)變化時(shí)對(duì)搜索幾乎不產(chǎn)生影響［3］。

1.2 相關(guān)定義

用無(wú)向圖G 表示P2P網(wǎng)絡(luò)，G＝（V，E）其中V 為G 的節(jié)點(diǎn)集合，對(duì)應(yīng)網(wǎng)絡(luò)中的Peer節(jié)點(diǎn)，E 為邊的集合，表示Peer節(jié)點(diǎn)間的連接。任意節(jié)點(diǎn)vi∈V，vj∈V，若（vi，vj）∈E，則必有（vj，vi）∈E。任意節(jié)點(diǎn)vi∈V 的度（或鄰居數(shù)）mvi為與此節(jié)點(diǎn)相連的邊的個(gè)數(shù)［9］。

定義1 若節(jié)點(diǎn)vc通過(guò)某條路徑（vo，v1，v2，……，vm，vo）訪問(wèn)vo，則稱vc為源節(jié)點(diǎn)，vo為目標(biāo)節(jié)點(diǎn)，并統(tǒng)稱為核心節(jié)點(diǎn)。

定義2 vc的訪問(wèn)覆蓋區(qū)域，簡(jiǎn)稱vc的覆蓋，記為Hc＝｛vi｜vi∈V，d（vc，vi）≤k，i＝1，2，…，h｝，其中vc與vi間至少存在一條無(wú)重復(fù)節(jié)點(diǎn)的訪問(wèn)路徑（vo，v1，v2，……，vm，vi），d（vc，vi）為vc到vi的最短路徑長(zhǎng)度，h 為Hc中的節(jié)點(diǎn)數(shù)，k為vc所發(fā)消息的TTL。

定義4 覆蓋Hc的高頻訪問(wèn)節(jié)點(diǎn)構(gòu)成的集合Γc＝｛vd｜vd∈Hc，d＝1，2，…m，fd＞珟fc｝稱為覆蓋Hc的高頻訪問(wèn)區(qū)域HFAA（high frequency access areas）。

定義5 節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集定義為Ni＝｛vj｜vj，d（vi，vj）＝1，j＝1，2，…，m｝，m 為vi的度。

1.3 高頻訪問(wèn)區(qū)域的存在性和產(chǎn)生的范圍

證明：由假設(shè)知，Aij為基本事件，vi向網(wǎng)絡(luò)發(fā)送和接收消息都要通過(guò)vij完成即AijAil＝，Ai1＋Ai2＋…＋Aim＝Ω，所以Ai1，Ai2，…，Aim是一個(gè)完備事件組，由此

另外，由貝葉斯公式

而消息洪泛時(shí)vij對(duì)于進(jìn)出vi的消息都會(huì)轉(zhuǎn)發(fā)即

因此由式（1）和式（3），可得式（2）為

但vi既向任何鄰居發(fā)送消息，也從任何鄰居接收消息即P（Aij｜Ai）≤P（Ai），因此P（Ai）≥P（Aij），于是引理成立，證畢。

說(shuō)明兩個(gè)核心節(jié)點(diǎn)的互訪路徑上的節(jié)點(diǎn)接收或發(fā)送消息的概率高于非路徑節(jié)點(diǎn)，產(chǎn)生較高訪問(wèn)次數(shù)的概率也高于非路徑節(jié)點(diǎn)。

定理1 若核心節(jié)點(diǎn)覆蓋的交集非空，則在它們交集中產(chǎn)生高頻訪問(wèn)區(qū)域的概率高于覆蓋中其他區(qū)域。

證明：首先，設(shè)核心節(jié)點(diǎn)vc和vo的覆蓋分別為Hc和Ho，且Hc∩Ho≠，即Hc∩Ho＝｛v′i｜v′i∈Hc∩v′i∈Ho｝。由定義2知vc和vo都有路徑與v′i鏈接，因此可設(shè)vc和vo的互訪路徑為（vc，v1，v2，…，vk，v′1，v′2，…，v′m，v1，v2，…，vs，vo），k≥0，m＞0，s≥0，其中路徑上的分段（v′1，v′2，…，v′m）為vc和vo互訪時(shí)形成的重疊部分，該部分節(jié)點(diǎn)構(gòu)成的集合為Γ＝｛v′d｜v′d，d＝1，2，…m｝，顯然ΓHc∩Ho。設(shè)vc和vo互訪使節(jié)點(diǎn)v′d∈Γ產(chǎn)生的訪問(wèn)次數(shù)為f′d，使非重疊部分的節(jié)點(diǎn)vi∈（Hc∪Ho）－Γ 產(chǎn)生的訪問(wèn)次數(shù)為fi。由引理知，f′d≥fi的概率大于f′d＜fi的概率，因此Hc∩Ho≠時(shí)定理成立。

另外，假設(shè)H1∩H2∩…∩Hn－1≠時(shí)定理成立，如果

則Hn≠，由集合的結(jié)合律知式 （4）可表示為

即集合H1∩H2∩…∩Hn－1和Hn的交集非空，由前面的證明知兩個(gè)的交集中產(chǎn)生高頻訪問(wèn)區(qū)域的概率高于覆蓋的其他節(jié)點(diǎn)，因此定理結(jié)論成立，證畢。

利用定理1的結(jié)論，發(fā)現(xiàn)算法的目標(biāo)就是到覆蓋的非空交集中去尋找高頻訪問(wèn)區(qū)域。

定理2 訪問(wèn)覆蓋中的任意節(jié)點(diǎn)可以在該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)范圍內(nèi)產(chǎn)生高頻訪問(wèn)節(jié)點(diǎn)。

證明：設(shè)-vc∈Hc，vc的度為m，且其鄰居集為Nc即-vi∈Nc，i＝1，2，…，m，節(jié)點(diǎn)vi的被訪問(wèn)次數(shù)記為｜vi｜。如果vi∈Nc，vj∈Nc，i≠j且｜vi｜＝｜vj｜，由定義1，-vo∈Ho，當(dāng)vo訪問(wèn)vc時(shí)，必然-vi∈Nc，使｜vi｜至少增加1，于是｜vi｜＞｜vj｜，i≠j；否則，如果｜vi｜≠｜vj｜，i≠j，即有｜vi｜＞｜vj｜或｜vi｜＜｜vj｜；由定義3，vc的鄰居節(jié)點(diǎn)中總能得到訪問(wèn)次數(shù)大于其他鄰居節(jié)點(diǎn)的節(jié)點(diǎn)，且其訪問(wèn)次數(shù)高于鄰居節(jié)點(diǎn)的平均值即在vc的鄰居節(jié)點(diǎn)范圍存在高頻訪問(wèn)節(jié)點(diǎn)，因此定理結(jié)論成立，證畢。

由定理2 可以知，通過(guò)訪問(wèn)覆蓋中預(yù)設(shè)的目標(biāo)節(jié)點(diǎn)，就可以使其鄰居節(jié)點(diǎn)中產(chǎn)生高頻訪問(wèn)節(jié)點(diǎn)，從而使高頻訪問(wèn)區(qū)域的位置產(chǎn)生在可以預(yù)測(cè)和控制的范圍內(nèi)。

1.4 索引副本擴(kuò)散和資源檢索

利用以上結(jié)論，索引副本設(shè)為兩站式結(jié)構(gòu)，第1 站設(shè)在每個(gè)節(jié)點(diǎn)上，存儲(chǔ)所有直接鄰居的稀缺資源的索引副本。搜索的局部性表明，節(jié)點(diǎn)更有可能從鄰近的節(jié)點(diǎn)那里得到查詢應(yīng)答，設(shè)此站的目的是盡量建立和鄰近節(jié)點(diǎn)的連接，讓搜索算法優(yōu)先查找鄰近節(jié)點(diǎn)［3］，第2站設(shè)在高頻訪問(wèn)區(qū)域的節(jié)點(diǎn)上，讓高頻訪問(wèn)節(jié)點(diǎn)的索引副本相互擴(kuò)散，以提高檢索命中率［8－10］?？梢栽诰W(wǎng)絡(luò)中選擇一批高度數(shù)節(jié)點(diǎn)作為種子，然后由種子節(jié)點(diǎn)采用隨機(jī)走或洪泛算法互發(fā)建立高頻訪問(wèn)區(qū)域消息，這樣在種子節(jié)點(diǎn)的鄰居中將產(chǎn)生覆蓋的交集，進(jìn)而形成覆蓋的高頻訪問(wèn)區(qū)域，再經(jīng)過(guò)高頻訪問(wèn)節(jié)點(diǎn)間的信息互換就實(shí)現(xiàn)了索引副本的擴(kuò)散。普通節(jié)點(diǎn)建立高頻訪問(wèn)區(qū)域表HFAAT（high frequency access areas table），記錄高頻訪問(wèn)節(jié)點(diǎn)的ID、IP、覆蓋ID；高頻訪問(wèn)節(jié)點(diǎn)還要建立索引副本表IRT（index replication table），記錄覆蓋中所有節(jié)點(diǎn)的ID、IP、關(guān)鍵字、文件屬性［2］。

首先，定義如下記號(hào)：節(jié)點(diǎn)vi發(fā)消息M 給節(jié)點(diǎn)vj記為vi｜Mvj；節(jié)點(diǎn)vj收到節(jié)點(diǎn)vi發(fā)的消息M 記為vivj｜M；節(jié)點(diǎn)vj向鄰居轉(zhuǎn)發(fā)消息M（檢查M 的TTL 是否為0，不為0則轉(zhuǎn)發(fā)M，否則停止轉(zhuǎn)發(fā)）記為vj｜M。

算法1：高頻訪問(wèn)區(qū)域索引副本擴(kuò)散算法DHFA2IR

輸入：核心節(jié)點(diǎn)T＝｛v1，v2，…，vm｝，vi∈T 建 立HFAAT；

輸出：高 頻 訪 問(wèn) 區(qū) 域Γ1，Γ2，…，Γm，ΓjHj，v∈Hj的HFAAT 記錄覆蓋的高頻訪問(wèn)節(jié)點(diǎn)，v′j∈Γj，v′j建立HFAAT 和IRT；

（2）vivt｜M，vt∈Hj，vt檢查M，若不重復(fù)則η＋＋；vj還要將vi的信息記錄到HFAAT，并檢查η≥m 否？是，vj｜Mηvt，vt∈Hj；vt｜M；

（3）vjvt｜Mη，vt∈Hj，vt以節(jié)點(diǎn)的ID、IP、關(guān)鍵字、文件屬性、節(jié)點(diǎn)的度mt和η 等信息產(chǎn)生Mrη，vt｜Mrηvj；vt｜Mη；

（4）vtvj｜Mrη，vj將vt的信息記錄到IRT；獲得Hj的所有n 個(gè)節(jié)點(diǎn)的信息后，計(jì)算，找出η＞avg 和mt超過(guò)設(shè)定值的節(jié)點(diǎn)v′t作為Hj的高頻訪問(wèn)節(jié)點(diǎn)，建立高頻訪問(wèn)區(qū)域聯(lián)系表HFAAT 并將v′t記錄其中 （建立Γj），以HFAAT 信息產(chǎn)生MΓ，vj｜MΓvt，vt∈Hj；以IRT 信息產(chǎn)生MI，vj｜MIv′t，v′t∈Hj；

（5）vjvt｜MΓ，vt∈Hj，vt建立HFAAT 并記錄vj發(fā)來(lái)的高頻訪問(wèn)節(jié)點(diǎn)；vt｜MΓ；

（6）vjv′t｜MI，v′t∈Γj，v′t建立IRT 并記錄vj發(fā)來(lái)的Hj的索引副本表點(diǎn)；v′t｜MI；

（7）當(dāng)系統(tǒng)中沒(méi)有消息發(fā)送和接收時(shí)，算法結(jié)束。

算法2：普通節(jié)點(diǎn)退出算法

（1）vt∈Hj以ID 產(chǎn) 生Mq，vt｜Mqv′j，v′j為HFAAT 中記錄的高頻訪問(wèn)節(jié)點(diǎn)；

（2）vtv′j｜Mq，v′j從IRT 中刪除vt記錄；

算法3：高頻訪問(wèn)節(jié)點(diǎn)退出算法

（1）v′t∈Hj以ID 產(chǎn) 生MΓq，v′t｜MΓqv′j，v′j為HFAAT 中記錄的高頻訪問(wèn)節(jié)點(diǎn)，v′t｜MΓqvs，vs為IRT中記錄的普通節(jié)點(diǎn)；

（2）v′tv′j｜MΓq，v′j從IRT和HFAAT 中刪除vt記錄；

（3）v′tvs｜MΓq，vs從HFAAT 中刪除v′t記錄；

算法4：節(jié)點(diǎn)加入算法

（1）vt｜Mnvi，vi∈Nt；

（2）vtvi｜Mn，vi以HFAAT 產(chǎn)生Mrn，vi｜Mrnvt；

（3）vivt｜Mrn，vt建立HFAAT 并記錄vi發(fā)來(lái)的高頻訪問(wèn)節(jié)點(diǎn)；

（4）vt以ID、IP、關(guān)鍵字、文件屬性、mt和η 等信息產(chǎn)生Min，vt｜Minv′j，v′j為HFAAT 中記錄的高頻訪問(wèn)節(jié)點(diǎn)；

（5）vtv′j｜Min，v′j將vt的信息記錄到IRT；

算法5：高頻訪問(wèn)區(qū)域刷新算法

（1）vt∈Hj以HFAAT 產(chǎn)生MR，v′t｜MRv′s，v′s為HFAAT 記錄的高頻訪問(wèn)節(jié)點(diǎn)；

（2）v′tv′s｜MR，v′t更新HFAAT 并記錄；

高頻訪問(wèn)區(qū)域刷新算法可以采用定時(shí)方式執(zhí)行，以保持信息一致。

算法6：資源檢索算法

輸出：v的資源請(qǐng)求Q 的查詢結(jié)果（資源不存在返回（3））；

（1）以v的資源請(qǐng)求Q 產(chǎn)生，利用HFAAT，vt｜Mqv′j；

（2）vtv′j｜Mq，v′j查詢IRT，存在擁有資 源節(jié)點(diǎn)v′t，v′j｜Mqv′t；否則，v′j利用HFAAT，v′j｜Mqv′k；

（3）v′jvt｜Mq，vt返回要查詢的信息；

（4）v′jv′k｜Mq，v′k∈Γk，v′k查詢IRT，存在擁有資源節(jié)點(diǎn)vs，v′k｜Mqvs；否則，返回 （3）；

（5）v′kvs｜Mq，vs返回要查詢的信息。

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

實(shí)驗(yàn)所用的仿真模型參考了文獻(xiàn)［7，9－15］提出的建立網(wǎng)絡(luò)拓?fù)浼夹g(shù)，仿真程序用VB6.0開(kāi)發(fā)。實(shí)驗(yàn)包括高頻訪問(wèn)區(qū)域的存在性驗(yàn)證和算法的有效性驗(yàn)證。

定義6 高頻訪問(wèn)區(qū)域出現(xiàn)率為核心節(jié)點(diǎn)的覆蓋內(nèi)產(chǎn)生高頻訪問(wèn)區(qū)域的次數(shù)與實(shí)驗(yàn)次數(shù)的百分比。

2.1 高頻訪問(wèn)區(qū)域的存在性驗(yàn)證

通過(guò)仿真程序產(chǎn)生具有1000個(gè)節(jié)點(diǎn)的模型網(wǎng)絡(luò)，在每個(gè)網(wǎng)絡(luò)中隨機(jī)產(chǎn)生20個(gè)高度數(shù)測(cè)試節(jié)點(diǎn)，即度數(shù)超過(guò)網(wǎng)絡(luò)平均節(jié)點(diǎn)度數(shù)的節(jié)點(diǎn)，以洪泛和隨機(jī)漫步方法實(shí)現(xiàn)節(jié)點(diǎn)互訪（為了尋找規(guī)律性TTL不加限制），檢查測(cè)試節(jié)點(diǎn)的鄰近節(jié)點(diǎn)的訪問(wèn)次數(shù)，然后計(jì)算覆蓋中高頻訪問(wèn)區(qū)域的出現(xiàn)率，實(shí)驗(yàn)結(jié)果如圖1所示?？梢钥闯?，節(jié)點(diǎn)的覆蓋中均存在高頻訪問(wèn)節(jié)點(diǎn)，并構(gòu)成了高頻訪問(wèn)區(qū)域，表明覆蓋的交集中高頻訪問(wèn)區(qū)域出現(xiàn)率近100%，與理論分析結(jié)果吻合。

圖1 高頻訪問(wèn)區(qū)域存在性實(shí)驗(yàn)

2.2 算法的有效性驗(yàn)證

DHFA2IR 為兩站式索引副本算法的改進(jìn)型，實(shí)驗(yàn)針對(duì)兩站式索引副本擴(kuò)散的經(jīng)典算法THIR，在相同仿真網(wǎng)絡(luò)中對(duì)它們的平均命中率和平均查找長(zhǎng)度進(jìn)行比較。在不同規(guī)模的仿真網(wǎng)絡(luò)中，隨機(jī)選擇100個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)放置一個(gè)稀缺資源。實(shí)驗(yàn)分兩種情況進(jìn)行：①比較DHFA2IR算法使用前后平均命中率和平均查找跳數(shù)；②比較DHFA2IR 和THIR 算法的平均命中率和平均查找跳數(shù)?？紤]到比較的公平性只將DHFA2IR 的索引副本擴(kuò)散到網(wǎng)絡(luò)中兩跳以內(nèi)。

首先，用DHFA2IR 算法將節(jié)點(diǎn)索引副本擴(kuò)散到網(wǎng)絡(luò)中，然后用隨機(jī)漫步方法搜索稀缺資源，比較應(yīng)用DHFA2IR 算法前后的命中率。由實(shí)驗(yàn)結(jié)果圖2看出應(yīng)用算法前后的效果差別明顯，如網(wǎng)絡(luò)規(guī)模為500和TTL 為50時(shí)，采用DHFA2IR 算法前后搜索成功率分別為1%和20%，平均查找跳數(shù)分別為31.2和8.4。兩種算法的查找跳數(shù)與網(wǎng)絡(luò)規(guī)模成正比，但DHFA2IR 算法平均查找跳數(shù)的增加比較平緩，說(shuō)明算法性能比較穩(wěn)定。

DHFA2IR 和THIR 算法的比較在規(guī)模為1000 個(gè)節(jié)點(diǎn)的仿真網(wǎng)絡(luò)上進(jìn)行，分別用DHFA2IR 和THIR 算法將索引副本擴(kuò)散到網(wǎng)絡(luò)中，然后用隨機(jī)漫步方法搜索稀缺資源，比較DHFA2IR 算法和THIR 算法的搜索命中率和平均查找跳數(shù)。由圖3可以看出在TTL 相同時(shí)，DHFA2IR 在搜索命中率優(yōu)于THIR 算法，如TTL 為5時(shí)，DHFA2IR 和THIR 搜索命中率分別為0.6 和0.2。這是因?yàn)镈HFA2IR充分利用了高頻訪問(wèn)節(jié)點(diǎn)在數(shù)量和訪問(wèn)概率方面的優(yōu)勢(shì)，而THIR 只利用少量超級(jí)節(jié)點(diǎn)來(lái)擴(kuò)散索引副本。隨著TTL的增大，搜索深度的加大，漫游到超級(jí)節(jié)點(diǎn)的機(jī)率會(huì)逐步增大，THIR 搜索的成功率逐步提高。

圖2 搜索成功時(shí)平均查找跳數(shù)隨網(wǎng)絡(luò)規(guī)模變化情況

圖3 搜索命中率隨TTL的變化情況

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

為了提高非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中稀缺資源的搜索命中率，通過(guò)對(duì)非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中高頻度訪問(wèn)節(jié)點(diǎn)在網(wǎng)絡(luò)中的聚集局部性的研究，發(fā)現(xiàn)高頻訪問(wèn)節(jié)點(diǎn)在節(jié)點(diǎn)覆蓋區(qū)域的交集中以高概率出現(xiàn)，并形成高頻訪問(wèn)區(qū)域。本文從理論和實(shí)驗(yàn)上證實(shí)了高頻訪問(wèn)區(qū)域的存在，并利用高頻訪問(wèn)在局部聚集的特性提出了控制節(jié)點(diǎn)索引副本在高頻訪問(wèn)區(qū)域擴(kuò)散的方法。實(shí)驗(yàn)表明，相比傳統(tǒng)兩站式索引副本擴(kuò)散方法THIR，DHFA2IR 方法明顯提高了檢索命中率。算法使節(jié)點(diǎn)存儲(chǔ)和網(wǎng)絡(luò)帶寬開(kāi)銷(xiāo)有一定增加，對(duì)網(wǎng)絡(luò)性能影響不大。該方法也為網(wǎng)絡(luò)負(fù)載的分擔(dān)提供了一條思路。

今后，研究重點(diǎn)將放在對(duì)高頻訪問(wèn)區(qū)域的動(dòng)態(tài)遷移規(guī)律上，進(jìn)一步探索提高算法穩(wěn)定性的方法。

［1］Krishna P，Puttaswamy N，Alessandra Sala，et al.Searching for rare objects using index replication ［C］／／Phoenix，AZ：IEEE INFOCOM，2008：1723－1731.

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

［3］LI Zhijun，JIANG Shouxu，LI Xiaoyi.Exploiting multi－level locality to implement the scalable search in unstructured P2P network ［J］.Journal of Software，2011，22 （9）：2104－2120.

［4］Sharifkhani F，Pakravan MR.A new metric for comparison of P2Psearch algorithms［C］／／Seventh International Conference on P2P，Parallel，Grid，Cloud and Internet Computing，2012：191－195.

［5］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）：1256－1261.

［6］Zhang Yuxiang，Zhang Hongke.A load balancing method in superlayer of hierarchical DHT－based P2Pnetwork ［J］.Chinese Journal of Computers，2010，33 （9）1580－1590.

［7］Li Zhen，Duan Hancong，Nie Xiaowen，et al.Routing optimization on the layered peer－to－peer management network ［J］.Journal of Chinese Computer Systems，2012，31 （1）：54－57.

［8］Li Pua，Chen Shiping，Li Jianfen.Cloud resources locating algorithm based on peer－to－peer network ［J］.Application Research of Computers，2013，30 （2）：570－573.

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

［10］Yao Quanzhu，Li Wei，Kong Wei.Research on communication protocol of unstructured P2Poverlay network ［J］.Computer Engineering and Applications，2011，47 （7）：99－102.

［11］Sarshar N，Roychowdhury V P.Multiple power－law structures in heterogeneous complex networks［J］.Physics Review E，2005，72 （2）：1－11.

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

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

［14］Hoong P K，Matsuo H.Push－pull two－layer super－peer based P2Plive media streaming ［J］.Journal of Applied Sciences，2008，8 （4）：585－593.

［15］Qian Ning，Wu Guoxin，Zhao Shenghui.A Bayesian network－based search method in unstructured peer－to－peer networks［J］.Journal of Computer Research and Development，2009，46 （6）：889－897.

［16］Zhou Xiaobo，Zhou Jian，Lu Haneheng.A layered interest based topology organizing model for unstructured P2P ［J］.Journal of Software，2007，18 （12）：3131－3138.