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

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

0 引 言

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

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

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

1 相關工作

1.1 節(jié)點定義

在每一組中，我們?yōu)楣?jié)點定義3個角色：超級節(jié)點、普通節(jié)點和中轉節(jié)點。

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

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

圖1 動態(tài)分組示例

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

1.2 節(jié)點的管理

1.2.1 節(jié)點加入

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

1.2.2 節(jié)點離開

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

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

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

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

2 基于動態(tài)分組的超級節(jié)點選取機制

2.1 動態(tài)分組流程

2.1.1 初始分組

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

(1)

式中：k代表節(jié)點的興趣集的個數(shù)。

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

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

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

(2)

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

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

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

2.1.2 閾值過濾篩選備選超級節(jié)點集合

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

(3)

式中：TotTi代表節(jié)點的累積在線時間總長，n代表節(jié)點的上線次數(shù)。

2.1.3 超級節(jié)點選取策略

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

PVal=w1PTru+w2PCal+w3PSto+w4PTim+w5PBan

(4)

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

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

2.1.4 備選超級節(jié)點選取策略

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

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

2.2 算法流程

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

算法1：動態(tài)分組

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

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

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

步驟4 所有節(jié)點加入對應組后，根據(jù)算法2提出的組內(nèi)超級節(jié)點選取算法進行組內(nèi)超級節(jié)點群組與備選超級節(jié)點集合的選??；

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

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

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

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

步驟2 根據(jù)系統(tǒng)中對于超級節(jié)點不同能力的需求，確定各個能力屬性的權重因子;

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

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

3 仿真分析

3.1 仿真場景

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

表1 仿真參數(shù)設置

3.2 仿真結果分析

3.2.1 動態(tài)分組后的節(jié)點分布

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

圖2 動態(tài)分組前的節(jié)點分布

圖3 動態(tài)分組后的節(jié)點分布

3.2.2 信息檢索延遲比較

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

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

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

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

3.2.3 網(wǎng)絡資源定位成功率比較

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

圖6 各機制網(wǎng)絡資源定位成功率比較

4 結束語

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