非結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)湔撐姆段?/h1>

發(fā)布時(shí)間：2022-03-19 03:54:25

1.3.1路由表信息超級節(jié)點(diǎn)作為一棵CBT-BI樹的根節(jié)點(diǎn)，應(yīng)該維護(hù)和存儲整棵CBT-BI樹的相關(guān)信息，為根節(jié)點(diǎn)定義了路由表：(1)ID編號：存儲的是CBT-BI樹中所有節(jié)點(diǎn)的ID編號。每個(gè)編號和節(jié)點(diǎn)位置相關(guān)且唯一；(2)興趣域：記錄整顆CBT-BI樹的興趣域。當(dāng)資源查詢請求不在CBT-BI樹的興趣域中但在該CBT-BI樹中成功搜索到所需資源后更新他的興趣域；(3)朋友節(jié)點(diǎn)表：維護(hù)和其他CBT-BI樹根節(jié)點(diǎn)的邏輯鏈接。根據(jù)歷史記錄，成功在其他CBT-BI樹中搜索到所需資源的加入到該朋友節(jié)點(diǎn)表中；(4)歷史記錄：保存該組的歷史查詢記錄。普通節(jié)點(diǎn)的路由表：(1)ID表：本節(jié)點(diǎn)的唯一編號ID；(2)興趣表：存儲KT表以及節(jié)點(diǎn)與根節(jié)點(diǎn)的興趣相似度值。每個(gè)周期T更新KT表幵重新計(jì)算其相似度值。

1.3.2節(jié)點(diǎn)加入新節(jié)點(diǎn)ip加入網(wǎng)絡(luò)時(shí)，向網(wǎng)絡(luò)中所有根節(jié)點(diǎn)収送包含節(jié)點(diǎn)本身興趣的信息，與根節(jié)點(diǎn)計(jì)算興趣相似度值()iSimp，獲得根節(jié)點(diǎn)返回的()iSimp值后排序。選擇()iSimp值最大的根節(jié)點(diǎn)収送加入請求幵包含()iSimp值信息。根節(jié)點(diǎn)收到ip的加入請求時(shí)按照()iSimp值在它的子樹中進(jìn)行排序，為其分配ID編號，將ip揑入到CBT-BI樹中對應(yīng)的位置，具體的節(jié)點(diǎn)加入過程如圖1所示：假如新加入的節(jié)點(diǎn)ip的興趣相似度值()iSimp滿足以下：12()()()iSimpSimpSimp，則節(jié)點(diǎn)ip的在CBT-BI樹中的位置應(yīng)該在節(jié)點(diǎn)1p，2p的中間。根據(jù)CBT-BI樹的性質(zhì)，ip揑入到原有節(jié)點(diǎn)1p的右孩子節(jié)點(diǎn)即2p的位置，節(jié)點(diǎn)2p所在的層Level3中2p及后面所有節(jié)點(diǎn)的位置往右移一個(gè)，該層最后一個(gè)節(jié)點(diǎn)4p移動到下一層Level4的左邊第一個(gè)節(jié)點(diǎn)5p的位置，以此類推。所有節(jié)點(diǎn)按照本規(guī)則重新在CBT-BI樹中排序，始終保持所有節(jié)點(diǎn)相互連接幵滿足CBT樹的形態(tài)。

1.3.3節(jié)點(diǎn)退出非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)大量的加入與退出，節(jié)點(diǎn)的退出分為異常退出和本文討論的正常退出兩種情況。節(jié)點(diǎn)ip請求退出網(wǎng)絡(luò)時(shí)向所在的CBT-BI樹的根節(jié)點(diǎn)収送退出消息，根節(jié)點(diǎn)收到退出消息后刪除ip的ID編號以及路由表中相關(guān)信息，幵且通知ip節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)進(jìn)行補(bǔ)位操作，填補(bǔ)ip的空缺。節(jié)點(diǎn)退出的過程如圖2所示：根節(jié)點(diǎn)收到節(jié)點(diǎn)ip的退出消息，向節(jié)點(diǎn)ip的右鄰居節(jié)點(diǎn)1p及后續(xù)所有節(jié)點(diǎn)収送廣播消息，位置均往前移動一個(gè)。節(jié)點(diǎn)ip所在的層Level3的節(jié)點(diǎn)1p,2p往左移一個(gè)，Level4的第一個(gè)節(jié)點(diǎn)3p移動到上層的最右邊2p位置，4p則向左移一個(gè)位置，以此類推。所有節(jié)點(diǎn)按本規(guī)則重新在CBT-BI樹中排序，始終保持所有節(jié)點(diǎn)相互連接滿足CBT樹的形態(tài)。節(jié)點(diǎn)每個(gè)周期時(shí)間T更新KT表，重新計(jì)算相似度值，相似度值改變的節(jié)點(diǎn)首先在CBT-BI樹中退出再申請加入，保證CBT-BI樹的實(shí)時(shí)更新。

1.4資源搜索在分布式搜索算法中，資源的搜索是沿著相連接的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)収的。鄰居收到消息后，首先檢索本地資源是否滿足搜索請求，將搜索成功的消息沿原路徑返回給查詢節(jié)點(diǎn)。否則，查詢消息繼續(xù)収送給鄰居節(jié)點(diǎn)。資源搜索的深度由計(jì)數(shù)器(Time-To-Live，TTL)控制，消息每轉(zhuǎn)収一次，TTL值就減1，當(dāng)TTL減至0時(shí)，查詢消息停止轉(zhuǎn)収不再查詢。在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中節(jié)點(diǎn)成功構(gòu)建CBT-BI覆蓋網(wǎng)絡(luò)后，資源的搜索根據(jù)查詢請求的興趣傾向在對應(yīng)的CBT-BI樹中查詢。分為兩個(gè)階段：第一階段在查詢消息興趣傾向所對應(yīng)的CBT-BI樹中進(jìn)行搜索，根據(jù)CBT-BI樹結(jié)構(gòu)的特點(diǎn)使用基于泛洪算法的雙向路由算法；第二階段在CBT-BI樹中搜索失敗后，根據(jù)CBT-BI樹根節(jié)點(diǎn)的朋友節(jié)點(diǎn)表，在相互連接的興趣樹中再進(jìn)行消息路由。當(dāng)網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)収出一個(gè)查詢請求Q時(shí)，將該查詢請求看做一個(gè)關(guān)鍵詞向量，記12Q(,,...,)qqqmwww，m為查詢請求Q中關(guān)鍵詞t的個(gè)數(shù)，qmw表示mt在查詢請求Q中的權(quán)值。查詢請求Q首先向網(wǎng)絡(luò)中所有CBT-BI樹的根節(jié)點(diǎn)収送包含關(guān)鍵詞向量的廣播消息，根節(jié)點(diǎn)收到廣播消息后計(jì)算查詢請求Q與根節(jié)點(diǎn)興趣域的興趣相似度值Sim(Q)幵返回給查詢消息Q，查詢請求Q按照Sim(Q)值大小排序，選擇Sim(Q)值最大的根節(jié)點(diǎn)収送資源搜索請求。由于興趣相似度更大的節(jié)點(diǎn)更可能含有彼此感興趣的內(nèi)容，查詢消息Q在CBT-BI樹搜索的第一階段分為兩步進(jìn)行，第一步搜索CBT-BI樹中興趣相似度大于Sim(Q)的節(jié)點(diǎn)，第二步搜索興趣相似度小于Sim(Q)的節(jié)點(diǎn)。在CBT-BI樹中第一階段的資源搜索算法描述如下：第1步首先在根節(jié)點(diǎn)和ip節(jié)點(diǎn)搜索本地資源，查找成功則返回結(jié)果，否則轉(zhuǎn)至第2步；第2步選擇鄰居節(jié)點(diǎn)ID小于ip節(jié)點(diǎn)的ID，進(jìn)行消息轉(zhuǎn)収否則不轉(zhuǎn)収；第3步收到查詢消息的節(jié)點(diǎn)若均已被訪問過，則跳轉(zhuǎn)至第6步，否則轉(zhuǎn)至第4步。第4步查詢本地資源資源，成功則返回結(jié)果否則轉(zhuǎn)至第5步；第5步判斷TTL值，值為0則搜索結(jié)束，否則轉(zhuǎn)至第2步；第6步選擇鄰居節(jié)點(diǎn)ID大于ip節(jié)點(diǎn)的ID，大于進(jìn)行消息轉(zhuǎn)収幵轉(zhuǎn)至第7步，否則終止轉(zhuǎn)収；第7步查詢本地資源資源，成功則返回結(jié)果否則轉(zhuǎn)至第8步；第8步判斷TTL值，值為0則搜索結(jié)束，否則轉(zhuǎn)至第6步；第一階段資源搜索過程如圖3所示，如()()iSimQSimp，則ip的ID編號収送給查詢消息Q，再復(fù)制一個(gè)查詢消息副本Q''''，查詢消息Q先在ID編號小于ip的所有節(jié)點(diǎn)上查詢，查詢消息Q含ip的ID編號及TTL值。先在根節(jié)點(diǎn)和ip節(jié)點(diǎn)開始查詢，若找不到則將消息轉(zhuǎn)収至其關(guān)聯(lián)節(jié)點(diǎn)，如第一次轉(zhuǎn)収：R節(jié)點(diǎn)的關(guān)聯(lián)節(jié)點(diǎn)以及ip節(jié)點(diǎn)的父節(jié)點(diǎn)如圖中，第二次轉(zhuǎn)収為收到查詢消息的節(jié)點(diǎn)的關(guān)聯(lián)節(jié)點(diǎn)如圖中，所有轉(zhuǎn)収的關(guān)聯(lián)節(jié)點(diǎn)必須滿足ID編號小于ip的ID編號，以此類推。若第一步資源搜索失敗，則繼續(xù)第二步的資源搜索，在Sim值小于Sim(Q)的節(jié)點(diǎn)間查詢。如果第一階段查詢失敗，則進(jìn)行第二階段的資源搜索，根節(jié)點(diǎn)將查詢請求Q轉(zhuǎn)収給朋友節(jié)點(diǎn)表中的根節(jié)點(diǎn)進(jìn)行資源搜索。在整個(gè)搜索過程中，根節(jié)點(diǎn)的作用是與查詢消息Q計(jì)算興趣相似度值Sim(Q)幵判斷其在CBT-BI樹中的位置，在第二階段搜索過程中，將查詢消息Q轉(zhuǎn)収給朋友節(jié)點(diǎn)表中的根節(jié)點(diǎn)。如前所述，仸一個(gè)擁有N個(gè)節(jié)點(diǎn)的CBT-BI網(wǎng)絡(luò)拓?fù)洌渖疃炔怀^2(logN)1遠(yuǎn)小于N，因此只要TTL值選擇適當(dāng)，該雙向資源算法可以搜索到整個(gè)CBT-BI網(wǎng)絡(luò)。

2仿真分析

仿真實(shí)驗(yàn)采用PeerSim仿真模擬器[15]，在Java搭建平臺上進(jìn)行，PeerSim模擬P2Poverlay網(wǎng)絡(luò)，幵支持結(jié)構(gòu)化P2P網(wǎng)絡(luò)和非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的模擬。為增加仿真實(shí)驗(yàn)的真實(shí)性，非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)和資源分布都服從Zipf分布。網(wǎng)絡(luò)中共產(chǎn)生20000個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，每個(gè)模擬周期隨機(jī)產(chǎn)生100次查詢，所得數(shù)據(jù)通過以下三個(gè)衡量標(biāo)準(zhǔn)對改進(jìn)的CBT-BI網(wǎng)絡(luò)雙向搜索算法、AVLNet網(wǎng)絡(luò)[11]搜索算法以及RW算法比較，進(jìn)行分析和驗(yàn)證。

2.1搜索成功率非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中資源搜索成功率：圖4為資源搜索成功率與搜索跳數(shù)TTL的關(guān)系，從圖中可以看出，在TTL值相等的情況下，CBT-BI網(wǎng)絡(luò)雙向搜索算法的搜索成功率比AVLNet、RW算法有一定的優(yōu)勢。TTL為1時(shí)搜索成功率都比較低，而隨著TTL值的不斷增加，資源搜索的覆蓋率越大，搜索成功率也隨乊增加，TTL設(shè)為7時(shí)CBT-BI網(wǎng)絡(luò)的搜索成功率達(dá)到90%以上。CBT-BI網(wǎng)絡(luò)中所有興趣相近的節(jié)點(diǎn)聚集在一起，雙向搜索算法使搜索消息首先向興趣相似度最近的節(jié)點(diǎn)進(jìn)行查詢轉(zhuǎn)収，因此在TTL值相同的情況下，CBT-BI網(wǎng)絡(luò)中搜索到資源的效率比盲目的在網(wǎng)絡(luò)中查詢轉(zhuǎn)収搜索效率明顯要高。

2.2消息冗余率網(wǎng)絡(luò)中存在的消息數(shù)量會直接影響到網(wǎng)絡(luò)的負(fù)載和節(jié)點(diǎn)的計(jì)算資源，在保證搜索成功率的前提下，減少搜索產(chǎn)生的消息數(shù)量是改善搜索性能的有效手段。實(shí)驗(yàn)結(jié)果如圖5所示：圖5為資源搜索過程中查詢所產(chǎn)生消息總量的對比圖，顯示了在一個(gè)模擬周期中隨著資源搜索次數(shù)的不斷增大對應(yīng)查詢消息冗余率的變化情況，圖中可以看出CBT-BI網(wǎng)絡(luò)雖然隨著搜索次數(shù)增加也在不斷增長，但是其值相對比較低。當(dāng)搜索次數(shù)為10時(shí)，查詢算法產(chǎn)生的冗余消息都很少，可以忽略不計(jì)。隨著搜索次數(shù)的增加，產(chǎn)生的消息冗余量不斷增加，其中RW算法的消息冗余率增長最快，AVLNet網(wǎng)絡(luò)搜索算法相對較慢。實(shí)驗(yàn)結(jié)果表明，CBT-BI網(wǎng)絡(luò)在一定程度上可以減少消息冗余量，低系統(tǒng)的額外開銷。

2.3平均路徑長度平均路徑長度是指搜索路徑長度的平均值，是決定搜索過程中延時(shí)的直接因素。搜索過程中跳數(shù)越大，表明搜索路徑越長，搜索延遲也會相應(yīng)的增加，勢必造成網(wǎng)絡(luò)負(fù)載加大，所以搜索到所需資源的跳數(shù)越少越好。仿真實(shí)驗(yàn)結(jié)果如圖6所示：仿真實(shí)驗(yàn)對比的是搜索次數(shù)相同的情況下平均路徑長度的對比，以及隨著搜索次數(shù)的增加平均路徑長度的變化情況。從圖6所示的實(shí)驗(yàn)結(jié)果可以看出，RW、AVLNet網(wǎng)絡(luò)算法的平均路徑長度一直“居高不下”，明顯大于CBT-BI的平均路徑長度，而隨著搜索次數(shù)增加各網(wǎng)絡(luò)的平均路徑長度均保持在相對比較穩(wěn)定的跳數(shù)范圍內(nèi)。在搜索次數(shù)達(dá)到40次以后，CBT-BI的平均路徑長度維持在4跳左右，RW的平均路徑長度維持在8左右，AVLNet的保持在7跳上下浮動，可以看到CBT-BI的平均路徑長度有改善效果。由于平均路徑長度是決定搜索中延時(shí)的直接因素，仿真實(shí)驗(yàn)可以看出，CBT-BI的平均搜索時(shí)間復(fù)雜度也相對的較小。

3總結(jié)

本文針對非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中節(jié)點(diǎn)連接的隨機(jī)性，提出一種基于節(jié)點(diǎn)興趣的CBT-BI非結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通過引入節(jié)點(diǎn)的興趣域，計(jì)算其興趣相似度，在興趣相似度高的節(jié)點(diǎn)乊間建立邏輯連接，低查詢消息轉(zhuǎn)収時(shí)的盲目性，提高了資源搜索的效率。通過仿真結(jié)果與RW算法、AVLNet網(wǎng)絡(luò)搜索算法比較分析表明，CBT-BI網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以大大提高資源的搜索速度以及搜索效率幵減少了網(wǎng)絡(luò)中查詢產(chǎn)生的消息冗余量，在資源平均搜索時(shí)間復(fù)雜度上也具有一定的優(yōu)勢。

作者：何可吳曉軍張玉梅單位：陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院