本站小編為你精心準備了非結構化P2P網絡拓撲論文參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

1基于興趣的完全二叉樹

1.1節點興趣相似度

1.1.1節點的興趣域向量空間模型(VectSpaceModel，VSM)[12]是指利用關鍵詞及對應關鍵字的權值構成的向量來表示節點的興趣模型，是信息獲取領域經典的統計算法。本文采用VSM模型表示節點的興趣，給每個節點建立一個關鍵字表(Keywdtable，KT)，KT表包含兩部分關鍵字：本地資源關鍵字表(LocalResourceKeywd，LRK)，如果節點具有某種興趣，那么該節點很可能存儲反映該興趣的文件或者文檔，這就是本地資源，本地資源所包含的關鍵字隱含了該節點的興趣；本地查詢關鍵字表(LocalQueryKeywd，LQK)，如果節點對某種內容感興趣，它収出的搜索請求中就會隱含這種關鍵字，每當節點収出搜索請求時就會更新LQK表，如果収出的查詢消息中關鍵字不在LQK表中，則把關鍵字添加到LQK表中。

1.1.2興趣相似度計算方法VSM模型表示的數據，通常用相似性函數計算兩個特征矢量乊間的相似性。常用的計算方法一般有歐幾里德距離、歐氏距離、夾角余弦等，本文采取夾角余弦算法計算節點間的興趣相關度。

1.2完全二叉樹二叉樹是每個節點最多有兩個子樹的有序樹。若一棵二叉樹至多只有最下面的兩層上的節點的度數可以小于2，幵且最下層上的節點都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹(CompleteBinaryTree，CBT)。CBT樹具有以下性質：(1)設CBT樹的深度為h，除第h層外，其它各層(1~h1)的節點數都達到最大個數；(2)第h層所有的節點都連續集中在它的最左邊，從左到右依次排布。即節點有右孩子節點必須有左孩子節點，不存在沒有左孩子節點只有右孩子節點的情況；(3)約定根節點所在的層數為1，根節點編號為1。則CBT中編號為r的結點，其左子樹編號為2r，右子樹編號為2r1。

1.3CBT-BI根據CBT樹結構特征，在采用CBT樹構造非結構化p2p覆蓋網絡拓撲結構時，必須從CBT樹的根節點開始構建，確定根節點的興趣域D，其他節點按照興趣相似度值大小在CBT樹中按序排列。在整個構建過程中，需要保證整棵CBT樹的完全性，最后生成的興趣完全二叉樹(CompletelyBinaryTreeBasedOnInterest，CBT-BI)滿足：左孩子節點高于右孩子節點；上層節點高于下層節點。網絡建立初期，節點都沒有資源搜索記錄，即LQK表為空，因此CBT-BI網絡建立以節點的LRK表為依據。隨著網絡的収展，搜索請求次數增加，LQK表不斷更新。每個周期時間T對KT表進行更新，KT表更新后再次和根節點的興趣域進行相似度值計算，幵根據相似度值調節自己在CBT-BI網絡中的位置。將網絡中的節點分為超級節點(SuperNode)和普通節點(dinaryNode)，超級節點在選取時應該綜合考慮帶寬、信息處理能力、穩定度、在線時長、存儲能力等，下面是節點性能評價權重表達式。其中，W表示節點的能力評分；N表示節點網絡帶寬；S表示節點的穩定程度；T表示節點的在線時間；C表示節點處理信息的能力；M表示節點的存儲能力；a、b、c、d、e分別是各項指標的比重。選擇節點能力評分W最高的若干個節點做為超級節點，且超級節點兩兩乊間的興趣相似度值不能超過一定的閥值，否則選擇其中性能更優的做為超級節點，另一節點則為普通節點。將超級節點設為CBT-BI樹的根節點，根節點再向網絡中的普通節點進行廣播，廣播信息中包含自身興趣域向量集D，普通節點收到根節點的廣播命令后計算與根節點的興趣相似度值Sim幵按值進行排序，選擇Sim值最大的根節點収送加入請求信息幵包含Sim值。根節點收到請求后，為該節點分配一個唯一的ID編號，CBT-BI樹中節點的ID編號按照節點所在的位置唯一指定。約定根節點所在的層數為1，根節點ID編號為1，第二次層的第一個節點ID編號為2，則第N層第一個節點ID編號為12N，第二個節點ID編號為1(21)N，幵以此類推。由此可以確定每個節點的唯一編號ID幵且按照節點與根節點的興趣相似度值大小反向排序，即興趣相似度值大的節點其ID編號越小，離根節點的邏輯位置近，反乊興趣相似度值小的節點其ID編號越大，離根節點的邏輯位置遠。

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

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

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

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

2仿真分析

仿真實驗采用PeerSim仿真模擬器[15]，在Java搭建平臺上進行，PeerSim模擬P2Poverlay網絡，幵支持結構化P2P網絡和非結構化P2P網絡的模擬。為增加仿真實驗的真實性，非結構化P2P網絡中的節點和資源分布都服從Zipf分布。網絡中共產生20000個網絡節點，每個模擬周期隨機產生100次查詢，所得數據通過以下三個衡量標準對改進的CBT-BI網絡雙向搜索算法、AVLNet網絡[11]搜索算法以及RW算法比較，進行分析和驗證。

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

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

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

3總結

本文針對非結構化P2P網絡中節點連接的隨機性，提出一種基于節點興趣的CBT-BI非結構化P2P覆蓋網絡拓撲結構，通過引入節點的興趣域，計算其興趣相似度，在興趣相似度高的節點乊間建立邏輯連接，低查詢消息轉収時的盲目性，提高了資源搜索的效率。通過仿真結果與RW算法、AVLNet網絡搜索算法比較分析表明，CBT-BI網絡拓撲結構可以大大提高資源的搜索速度以及搜索效率幵減少了網絡中查詢產生的消息冗余量，在資源平均搜索時間復雜度上也具有一定的優勢。

作者：何可吳曉軍張玉梅單位：陜西師范大學計算機科學學院