一種基于節點興趣的移動P2P 網絡動態分組算法

◆石曦彤

（四川大學網絡空間安全學院 四川 610065）

1 引言

隨著無線通信技術的迅速發展，移動P2P 作為一種新型覆蓋網絡技術也在不斷發展中。移動P2P 網絡中節點的地位是對等的，每個節點既是資源下載者，也是資源提供者，這種資源共享模式解決了傳統C/S 模式下服務器性能瓶頸的問題，更能充分利用網絡中節點的計算資源。現有的移動P2P 網絡的拓撲結構分為集中式、完全分布式（結構化和非結構化）、混合式三種類型[1]。

集中式P2P 網絡以目錄服務器為中心形成星形結構，維護簡單且搜索效率高，但同時也容易造成單點故障、訪問的“熱點”現象等問題，同時網絡缺乏可擴展性。

完全分布式結構化P2P 網絡，又稱為DHT 網絡，在完全分布式結構化網絡中引入了分布式散列表（Distributed Hash Table，DHT）技術，經典的DHT 算法有Chord[2]、Pastry[3]和Kademlia[4]等。DHT 網絡的優點是采用了確定性拓撲結構，能夠精確地定位資源。缺點是DHT 的維護機制比較復雜，尤其是當節點頻繁加入、退出網絡時造成的網絡波動會極大增加系統的維護代價。完全分布式非結構化網絡采用完全隨機的組織結構，優點是所有節點是完全對等的，所以網絡的可擴展性和容錯性較強。缺點是由于采用泛洪式的消息傳播方式增加了網絡的負載。

混合式P2P 網絡結合了集中式和完全分布式兩種方式，把移動節點分成多個域，每個域內有一個超級節點，功能是存儲普通節點信息、內容管理和與有線P2P 網絡的通信，普通節點發出文件查詢請求之后，該請求在超級節點間進行轉發，之后該節點獲得一個反饋結果列表，然后選擇與之進行交易的節點。

本文提出一種基于節點興趣的移動P2P 網絡動態分組算法，其基本思想是：考慮到相同興趣的節點間交易概率比較大，另外，移動P2P 網絡是一種覆蓋網絡，其在設計之初并未考慮到與物理網絡的結合，導致邏輯拓撲結構與物理拓撲結構不匹配，相鄰節點間的信息延遲較大，故根據節點間的興趣相似度、資源相似度以及物理距離對節點進行動態分組，從而提高整個網絡的資源共享效率。

2 相關工作

2.1 節點聚類方式

聚類是指將物理或抽象的對象集合分成由類似的對象組成的多個類的過程。由聚類所生成的簇是一組對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。為了提高移動P2P 網絡的資源共享效率及安全性，研究者提出了許多移動P2P 網絡的分組算法。曹曉梅等人[5]提出一種改進的分組P2P 信任模型，該模型利用模糊推理規則結合信任值和貢獻值，將網絡中節點劃分為若干不同等級的小組，通過小組等級限制節點的資源訪問權限，實驗表明該模型能有效抑制惡意節點的攻擊。為了提高移動P2P 網絡的覆蓋層拓撲穩定性，宋人杰等人[6]提出了一種基于節點移動特性的移動P2P 網絡分簇算法，實驗表明該算法使簇內節點能夠最大程度地保持覆蓋層拓撲結構的穩定性。

2.2 超級節點選取方式

文獻[7]通過分析影響超級節點選取的各種因素，將這些因素分為效益型屬性和成本型屬性，建立超級節點選取的帶約束多目標優化模型，利用免疫克隆算法對超級節點選取問題進行求解。文獻[8]選取服務能力強和節點活躍度高的節點作為超級節點，主要考慮的影響因素有CPU 速度、帶寬大小和內存容量以及節點單位時間的貢獻度。文獻[9]提出了一種基于信任模式的P2P 超級節點選取機制，主要思想是通過計算節點的總體信任度作為評選超級節點的一項重要指標，在選取超級節點時采用閾值過濾算法從普通節點中篩選備選超級節點集合，然后再從備選超級節點集合中選取最優的節點作為超級節點。王秀娟等人[10]提出一種基于區域劃分的超級節點選取機制，將P2P 網絡中的節點按照物理位置劃分成若干區域，保證區域內節點在物理位置上是相近的。

3 基于節點興趣的動態分組算法

本文提出一種移動P2P 網絡中基于節點興趣的動態分組算法，首先根據資源類型的個數，將移動P2P 覆蓋網絡劃分為若干個組，動態分組的依據是網絡中節點的興趣相似度，資源相似度、節點的移動特性以及節點的物理位置因素，然后根據交易信息動態的更新分組。

3.1 節點角色

（1）超級節點

超級節點具有更高的計算能力和穩定性，其維護一個組中所有節點的文件列表和不同組節點之間交易的事務信息，文件列表記錄了組內所有節點的文件，當一個節點請求一些文件時，它可以將請求發送給超級節點，超級節點告訴請求者哪個組成員擁有請求的文件。

（2）普通節點

不是超級節點的節點，它可以向其他節點請求資源，也可以為其他節點提供資源。普通節點在每次事務后將事務信息發送給對應的超級節點。

3.2 節點管理

（1）節點加入

當一個新節點加入網絡時，根據興趣相似節點間交易概率比較大的思想，首先計算該新節點與所有超級節點的興趣相似度，使節點能夠加入到與其興趣相似度較高的組中；然后考慮到一個組內的節點之間擁有的資源重疊較少時能更好地為其他節點提供分享資源，故通過計算節點間的資源相似度，使分組后組內節點資源盡可能更豐富；最后計算該新節點與所有超級節點的物理距離，使其能被添加到距離相對近的組中。

（2）普通節點離開

當一個普通節點離開網絡時，節點向同一組中的其他節點廣播離開的消息。同一組中的其他節點更新鄰居的信息并重新計算信任值。同時，組中的超級節點更新路由表和文件列表。

圖1 動態分組示意圖

（3）超級節點離開

當一個超級節點離開網絡時，首先要求超級節點廣播其離開消息，然后根據超級節點選擇機制重新選擇新的超級節點。一旦確定了新的超級節點，組的所有文件列表和節點間交易的事務信息都將傳輸到新的超級節點。新的超級節點響應它從原超級節點接收到的信息。然后，原超級節點退出網絡。

3.3 動態分組流程

在移動 P2P 網絡中，資源節點i的興趣集Ipi表示為：Ipi = {a1,a2,…al}，l 為文件類型個數，對于第k個興趣ak ∈{0,1}，表示節點i是否擁有至少一個該類型的文件，若擁有則ak =1，否則ak =0。資源節點j的興趣集Ipj表示為：Ipj ={b1,b2,…bl}，l 為文件類型個數，對于第k個興趣bk ∈{0,1}，表示節點j是否擁有至少一個該類型的文件，若擁有則bk = 1，否則bk =0。節點i和節點j之間的興趣相似度ISimi,j計算如下：

式中，si,j表示Ipi和Ipj中對應位置的值相同的個數，l 表示文件類型總數。

資源節點i所擁有的文件集Fpi表示為：Fpi ={f1,f2,…fn}，n為節點i所擁有的文件資源個數。資源節點j所擁有的文件集Fpj表示為：Fpj ={f1,f2,…fm}，m為節點j所擁有的文件資源個數。節點i和節點j之間的資源相似度FSimi,j計算如下：

在初始階段，因為l 是節點興趣集中的類型數，故選擇l 個節點作為初始中心節點。然后，得到l 個中心節點和l 個對應的初始群。為改善移動P2P 網絡中邏輯拓撲結構與物理拓撲結構不匹配而帶來的P2P 節點間的延遲增大的問題，故在分組時還需考慮節點之間的物理位置，使各組內節點盡量靠近，在新節點加入時，通過向各中心節點發送探測消息，獲得往返時延值RTT。

給定一個節點，我們可以通過公式（3）分別計算它與l 個中心節點的綜合分組考量值。

式中，δ1、δ2和δ3分別為節點興趣相似度、資源相似度和物理距離的權重，且δ1+δ2+δ3 =1，如果給定節點和中心節點之間的分組考量值最終得分最大，則將給定節點添加到中心節點的組中。通過重復此過程，將所有節點添加到相應的組中。之后，我們使用K-means[11]中采用的方法更新每組的中心點。然后，通過計算節點與更新中心節點的相似度，得到l 個新的節點群。如果每個組中的節點停止更改，則終止此進程。

在網絡交易階段，如果節點成功收到請求的文件，則更新該節點擁有的文件集。若系統中的事務成功交易率小于閾值θ，或者網絡中節點加入/離開的比例大于閾值?，則重新進行動態分組。

3.4 超級節點選取機制

在資源搜索時，為了減少響應時間，提高搜索效率，查詢信息請求應該發送給性能和穩定性相對較高的節點，即超級節點。本文在選擇超級節點時把節點的能力因素作為主要參考指標，主要考慮的性能指標參數有：在線時間（OT）、CPU 的有效處理能力（Speed）、帶寬（BW）、存儲空間（Memory）。用Ability變量來表示節點的能力值，節點的Ability值越大，則表示該節點處理能力越強。節點i的Ability值計算公式如下：

其中，OTmin表示超級節點的最短在線時間，單位是秒；Speedmin表示超級節點的最小有效處理能力，單位是MIPS；BWmin表示超級節點的最小帶寬，單位是kpbs；Memorymin表示最小存儲空間，單位是GB。

另外在選取超級節點時還考慮了節點對系統的貢獻度，即主動提供的資源數、成功轉發其他節點的請求消息數。為每個節點定義一個貢獻度變量Contribution，計算公式如下：

其中Fupload表示表示在時間T內節點成功上傳的文件數，Fforward表示節點成功轉發的消息數，即間接為系統做出的貢獻，T表示系統運行的時間周期。

節點i的Utility值計算公式如下：

其中，γ1和γ2分別為節點能力值和貢獻值的權重，且γ1+γ2 =1。系統中的每個節點都有其對應的Utility值，周期性地對它們的Utility值進行評估，擁有最大Utility值的節點將成為本分組中的超級節點。

4 實驗與分析

本文仿真基于 PeerSim1.0.5 仿真系統，PeerSim 支持2 種仿真模式，即 Cycle-based 模式和傳統的 Event-based 模式，Cycle-based 擁有更好的伸縮性及性能，本文采用Cycle-based 模式進行仿真，對傳統的半分布式移動P2P 網絡和基于節點興趣的動態分組算法的移動P2P 網絡進行信息檢索延遲的比較。

具體仿真環境為：節點總數為250 個，文件個數為1000 個，文件種類為8 個，文件在各節點均勻隨機分布。其他仿真參數如表1 所示：

表1 仿真參數

數軸中橫坐標代表請求次數，縱坐標代表網絡延時（從源節點到目的節點的所有路徑延時之和）。實驗結果如圖2、3 所示。

圖2 請求次數從0 到500 時的信息檢索時延

圖3 請求次數從0 到1000 時的信息檢索時延

由以上仿真結果可以看出，基于節點興趣的動態分組算法的轉發延時比傳統半分布式的延時低30%～40%左右，所以基于節點興趣的動態分組算法能夠一定程度地降低網絡的信息檢索延遲，提高資源檢索的效率，并且具有較好的可擴展性。

5 結束語

為了提高移動P2P 網絡的資源共享效率，本文根據興趣相似節點間交易概率比較大的思想，提出一種基于節點興趣的動態分組算法，并在分組時考慮到節點擁有的資源類型及節點間的物理位置，從仿真實驗可以得出此算法能夠降低節點間通信延時，提高移動P2P 網絡中的文件共享效率，并具有一定的擴展性。