MP2P網絡基于動態分組的超級節點選取

陶 洋，王成宇，潘蕾娜，楊 柳，王 進

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

在移動對等(mobile peer-to-peer，MP2P)網絡中，節點間可以進行自由交易，并且節點經常連接并離開網絡，這將動態地改變網絡拓撲。因此，在選取超級節點時，必須要考慮到超級節點的可靠性和穩定性。近年來，MP2P網絡中的超級節點選取策略也是受到了研究人員的廣泛關注。

賈美娟等[1]提出一種根據節點興趣相似度進行動態分組的超級節點選取機制，引入了中繼節點用于組與組間的信息交換，根據節點的資源類型進行分組。郭良敏等[2]提出了一種將物理位置相近的節點分在一個簇中，使同組中的節點在物理位置上相近，降低普通節點與超級節點間的信息檢索延遲。朱廣輝等[2]提出了一種根據信息相關度進行節點分組的超級節點選取機制。Saghiri A M等[3]提出了一種考慮節點的容量的對等關系進行超級對等點選擇的算法，通過節點的數量和節點的容量率方面提升網絡的動態性。文獻[4-6]主要從網絡拓撲方面出發，將節點進行分層，分區處理，從而進行超級節點的選取，但是主要研究點集中在單個超級節點的選取，以及若干個備選節點的選取工作。文獻[7,8]主要從節點的物理位置、IP地址作為分組分簇依據，將網絡拓撲中相近較近的節點分為一組，從而減少組間節點交易的傳輸距離，降低信息傳輸時延。

研究發現，大多數文獻主要考慮了單一因素對網絡中的節點進行分組，并且在選取組內超級節點時都只考慮了單一或者固定節點數的超級節點[9,10]，但是沒有考慮到根據群組的規模大小進行動態的超級節點群組的選取。因此，本文提出一種基于動態分組的超級節點選取機制(dynamic grouping-based super node selection mechanism，DGSM)。該機制考慮節點的興趣向量相似性和物理拓撲中節點間的距離兩個因素進行節點的動態分組，然后根據閾值過濾算法和節點綜合能力計算選出每組的超級節點群組和備選超級節點集合，根據每組的超級節點負載情況動態更新該組的超級節點群組。實驗結果表明，通過該機制選出的超級節點在一定程度下，提供了較低的信息檢索延遲，更少的網絡資源定位消耗和更大的網絡資源定位成功率。

1 相關工作

1.1 節點定義

在每一組中，我們為節點定義3個角色：超級節點、普通節點和中轉節點。

超級節點(super node，SN)：維護了一個信任表和一個組中所有節點的文件列表的節點。信任表記錄組中所有節點的信任信息。當節點請求一些文件時，它將請求發送給超級節點。超級節點根據該節點的請求，首先在本組中查找是否有符合的資源。如果該資源存在，且擁有資源的節點的信任度較高，則超級節點告訴請求節點哪個組成員節點擁有所請求的文件。如果本組中無請求的資源，則超級節點將請求信息轉發給本組的中轉節點，由中轉節點向其它組轉發該節點請求。

中轉節點(relay node，RN)：主要用來連接兩個相鄰的組。來自不同組的節點之間的交易信息存儲在中轉節點中。如圖1所示，首先，ON10請求ON11擁有的文件。ON10向該組超級節點SN1發送一個查詢。如果SN1或該組的其它節點有被請求的文件，SN1向ON10發送響應，該組中某個節點擁有ON10 所請求的文件，則ON10就可以與該節點進行交易。如果SN1所在組中沒有ON10所請求的文件，SN1將查詢發送給該組的中轉節點RN7。RN7將查詢轉發到不同的組的中轉節點，RN8和RN9。中轉節點將查詢發送給組中的超級節點。因為SN3是ON11所在組的超級節點，所以它有該組中所有節點的文件列表。SN3發現ON11有被請求的文件。P2通過RN9發送響應給RN7，該組超級節點SN1向ON10發送應答響應，SN3所在組中的ON11具有請求的目標文件。

圖1 動態分組示例

普通節點(ordinary node，ON)：ON是群組中一個不擔任轉發任務的普通節點。它可以請求來自于其它節點的資源，也可以將資源分享給其它節點。在與其它節點交易完成后，ON會更新與交易節點之間的信任值，用于其它節點與該節點進行交易時的推薦。交易完成后將信息發送給該組的超級節點。

1.2 節點的管理

1.2.1 節點加入

一個新節點加入一個MP2P網絡，首先為這個新的節點設置初始的信任值，這可以保證其它節點可以與之進行交易。當一個節點連接到MP2P網絡時，該節點與其它節點之間沒有交互的信息，該節點與各組的超級節點的資源興趣相似度和與各組超級節點間的往返距離是可以計算出來的。這個節點將被添加到興趣與之最相似且距離又相對較近的組中。如果新節點與所有的超級節點的興趣相似度和往返距離都相差較大，則新節點自己成為一組，并作為該組的初始超級節點。當許多節點加入MP2P網絡時，節點之間的信任關系會不斷發生變化。

1.2.2 節點離開

普通節點離開網絡的情況。普通節點離開網絡時，會向同組的其它節點發送其離開信息。同一組的其它普通節點更新鄰居的信息并重新計算信任值。同時，組中的超級節點群組更新其路由信息表和節點資源列表。

中轉節點離開網絡的情況。如果中轉節點離開一個組，它會向同組的其它節點廣播其離開的消息。離開的中轉節點將其信息傳遞給同一組中的選出的繼任的中轉節點。新的中轉節點向超級節點發送信息以確認擔當繼任中轉節點的角色。超級節點在接收來自新的中轉節點的信息后，向組中的所有節點成員廣播關于新的中轉節點的消息。收到消息后，所有節點成員更新了關于中轉節點的信息。

超級節點離開網絡的情況。在一個組中，超級節點管理組中所有節點的信任消息和文件列表。因此，重要的是考慮一個超級節點離開的情況。首先，超級節點被要求廣播它的離開消息，然后從備選超級節點群組中選擇綜合能力值最高的節點作為新的超級節點。新的超級節點接收并存儲離開的超級節點傳輸的組中節點的信任消息和文件列表。組中的所有節點更新關于新超級節點的信息。

備選超級節點離開網絡的情況。備選超級節點因為還未擔任超級節點的工作，所以當其離開網絡時，會像普通節點離開時一樣向其鄰居節點廣播其離開的消息，同一組的其它普通節點更新鄰居的信息并重新計算信任值。同時，同組中的超級節點群組更新其路由表和文件列表。如果該節點離開后，組中沒有剩余的備選超級節點，則觸發備選超級節點更新機制，動態變更備選超級節點能力閾值，選舉出新的備選超級節點集合。

2 基于動態分組的超級節點選取機制

2.1 動態分組流程

2.1.1 初始分組

在MP2P網絡中，節點包括資源屬性和能力屬性。本文選擇將節點的資源屬性作為動態分組的依據之一，節點的能力屬性作為超級節點選取的依據。節點的資源屬性由興趣集來表示，節點i的興趣集定義為Ii={a1，a2，a3，…，ak}。 兩節點之間的興趣相似度計算如下式

(1)

式中：k代表節點的興趣集的個數。

在初始階段，首先使用K-Means算法[11]隨機選擇k個節點作為初始的超級節點，在選擇時盡量考慮選擇距離位置相距較遠的節點。然后，通過k個初始的超級節點建立k個對應的初始組。對于新加入的節點，可以通過式(1)計算它與k個初始超級節點的興趣相似度。

新加入的節點通過向各組的初始超級節點發送探測消息,計算其與各組的初始超級節點的距離，用RTT來表示。

通過式(2)計算它與k個初始超級節點的綜合考量值。節點i和節點j之間的綜合考量值計算如下式

(2)

式中：α，β分別表示興趣相似度和節點間RTT的權重，α+β=1，且滿足0<α<1, 0<β<1。RTTmax為網絡中兩節點間最大的往返距離值，RTTi,j為節點i和節點j之間的往返距離值。

選擇新加入節點和各區域超級節點綜合考量值最大的超級節點所在組，并加入該組；通過重復這個過程，直至所有的節點都被添加到相應的組中。

初始分組完成后，繼續重復不斷地計算各組的超級節點并重新分組，直到所有節點不再改變分組(超級節點位置不再改變)。即動態分組完成。

2.1.2 閾值過濾篩選備選超級節點集合

首先對每組內所有節點進行閾值過濾，定義普通節點i的能力屬性集合為Capi={Trui,Cali,Stoi,Timi,Bani}，分別代表節點的信任度，計算能力，存儲能力，平均在線時間，帶寬等。在MP2P網絡中對超級節點的能力閾值定義為：Capt={Trut,Calt,Stot,Timt,Bant}。 各項能力均超過超級節點能力需求閾值的進入備選超級節點集合。其中節點的平均在線時間計算如下式

(3)

式中：TotTi代表節點的累積在線時間總長，n代表節點的上線次數。

2.1.3 超級節點選取策略

通過備選超級節點閾值篩選的備選超級節點,根據式(4)對備選超級節點的綜合能力進行計算,從中選擇綜合能力值最大的節點確定為初始的超級節點

PVal=w1PTru+w2PCal+w3PSto+w4PTim+w5PBan

(4)

式中：w1+w2+w3+w4+w5=1，PTru表示節點的信任度，PCal表示節點的計算能力，PSto表示節點的存儲能力，PTim表示節點的平均在線時間，PBan表示節點的帶寬。其中w1、w2、w3、w4、w5分別為5個能力因素的權重，需滿足w1+w2+w3+w4+w5=1。

為防止惡意節點和臨時節點被誤評為超級節點,造成網絡的不穩定,因此在選取機制中賦予w1和w4更大的權重。由此選出的超級節點可靠性較高，形成的網絡比較穩定。

2.1.4 備選超級節點選取策略

超級節點離開時首先廣播它的離開消息，然后根據選擇備選超級節點群組中綜合能力最高的備選節點成為該組新的超級節點。一個新的超級節點確認后，所有的信任消息和該組的文件列表都被轉移到新的超級節點上。新的超級節點接收原超級節點接傳輸的信息。新超級節點信息接收完畢后，原超級節點正式退出。該組中的所有節點更新它們對新超級節點的信息。

選取備選超級節點群組中綜合能力最強的備選節點加入現有超級節點，成為超級節點群組，為剩余負載能力不足的超級節點承擔一定的負載請求。超過超級節點負載閾值后，啟動選舉策略，選取備選超級節點集合中綜合能力最強的備選節點加入超級節點群組，與原先的若干超級節點共同承擔超級節點的工作。備選節點加入后，原超級節點將擁有的本組的信任表和該組中所有節點的文件列表發送給該備選節點。

2.2 算法流程

本文算法的總體步驟如算法1所示。

算法1：動態分組

步驟1 首先確定節點的資源類型個數，記為k個，隨機選取k個節點作為初始超級節點，選取時盡量選擇物理位置相距較遠的節點；

步驟2 建立k個初始組，并將初始超級節點加入對應組中；

步驟3 將加入的新節點根據式(2)得到與各初始超級節點的綜合考量值，選擇綜合考量值最大的超級節點所在組，并加入該組；循環此步驟直到所有節點全部加入對應組中；

步驟4 所有節點加入對應組后，根據算法2提出的組內超級節點選取算法進行組內超級節點群組與備選超級節點集合的選取；

步驟5 如果組內的超級節點群組與上次超級節點選取后的超級節點群組相同，則動態分組完成；否則重復算法2。

超級節點群組和備選超級節點集合的選取算法如算法2所示。

算法2：超級節點群組和備選超級節點集合選取

步驟1 對每組內所有節點進行綜合能力的篩選，通過閾值篩選的節點進入每組的初始備選超級節點集合;

步驟2 根據系統中對于超級節點不同能力的需求，確定各個能力屬性的權重因子;

步驟3 根據式(4)計算出所有備選超級節點的綜合能力值;

步驟4 選擇綜合能力值最大的節點作為該組的超級節點，其它節點則作為備選超級節點，當超級節點退出或者被評定為惡意節點后，由備選超級節點中選擇綜合能力值最大的節點作為繼任的超級節點。

3 仿真分析

3.1 仿真場景

利用Matlab在DGSM、基于興趣動態分組的超級節點選取機制(dynamic grouping trust model，DGTM)、基于區域劃分的超級節點選取機制(super node selection mechanism，SNSM)和傳統的未分組的SNSM進行對比驗證。仿真參數設置見表1。

表1 仿真參數設置

3.2 仿真結果分析

3.2.1 動態分組后的節點分布

圖2、圖3分別是動態分組前后的節點分布情況。會發現此種分組下會有一部分物理位置距離稍遠但興趣相似的節點會分到一組中，這樣的分組方式保證了即使同組內相距較遠的兩節點進行交易時，雖然兩節點的物理位置相距較遠，但因為在同一個分組下，省去了不同組間超級節點和中轉節點的信息傳遞和請求轉發的時間，減少了網絡中的整體的信息檢索延遲。在網絡規模越大的系統中，該種分組方式在網絡中信息檢索延遲和網絡資源定位成功率越好。

圖2 動態分組前的節點分布

圖3 動態分組后的節點分布

3.2.2 信息檢索延遲比較

在本實驗中，采用類Flooding的算法，檢索延遲是消息在傳播路徑上的延遲總和，根據傳播路徑上每一跳的節點間的距離之和來計算。

圖4、圖5是節點數為200的情況下，節點請求次數分別從0到200和0到1000時，DGSM和其它3種超級節點選取機制下網絡中信息檢索延遲。圖中橫坐標代表節點的請求次數，縱坐標代表信息檢索延遲。從圖中可知，DGTM和基于區域劃分的超級節點選取機制下當節點請求次數分別到達550和700時，其信息檢索延遲增長率會突然升高，而此時DGSM下的信息檢索延遲還處在一個較低的水平。DGSM通過形成在網絡物理拓撲中距離相近的相似興趣節點進行聚類分組，更大程度地使得資源在組內共享，減少了由超級節點組成的高速轉發層的帶寬損耗，降低了網絡中信息檢索延遲。

圖4 請求次數從0到200時各機制信息檢索延遲比較

圖5 請求次數從0到1000時各機制信息檢索延遲比較

3.2.3 網絡資源定位成功率比較

圖6是各機制下網絡資源定位成功率的比較，如圖所示，隨著節點請求次數的增加，本文提出的機制在資源定位成功率上一直保持較高的資源定位成功率。相比于其余幾種機制，資源成功率隨著節點請求次數的增加下降數率明顯較低。且當節點資源請求次數達到1000次時，相比于其它3種超級節點機制，本文提出的機制在資源定位成功率上分別提高了15.4%、20%、157%，驗證本文提出的超級節點選取機制可以有效的提高網絡中資源定位成功率。

圖6 各機制網絡資源定位成功率比較

4 結束語

本文提出了一種基于動態分組的超級節點選取機制(DGSM)。通過綜合仿真結果表明本算法與其它最新算法相比，經過動態分組的超級節點選取機制可以有效地降低MP2P網絡的信息檢索延遲，提高網絡中資源定位成功率，并且具有較好的擴展性。因此，本文提出的基于動態分組的超級節點選取機制可有效提升MP2P網絡的動態適應性，降低了網絡的信息檢索延遲,提高了網絡資源定位成功率。