MP2P網(wǎng)絡(luò)基于動態(tài)分組的超級節(jié)點選取

陶 洋，王成宇，潘蕾娜，楊 柳，王 進(jìn)

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

0 引 言

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

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

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

1 相關(guān)工作

1.1 節(jié)點定義

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

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

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

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

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

1.2 節(jié)點的管理

1.2.1 節(jié)點加入

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

1.2.2 節(jié)點離開

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

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

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

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

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

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

2.1.1 初始分組

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

(1)

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

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

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

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

(2)

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

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

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

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

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

(3)

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

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

通過備選超級節(jié)點閾值篩選的備選超級節(jié)點,根據(jù)式(4)對備選超級節(jié)點的綜合能力進(jìn)行計算,從中選擇綜合能力值最大的節(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個能力因素的權(quán)重，需滿足w1+w2+w3+w4+w5=1。

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

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

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

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

2.2 算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真分析

3.1 仿真場景

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

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

3.2 仿真結(jié)果分析

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

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

圖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é)點選取機(jī)制下網(wǎng)絡(luò)中信息檢索延遲。圖中橫坐標(biāo)代表節(jié)點的請求次數(shù)，縱坐標(biāo)代表信息檢索延遲。從圖中可知，DGTM和基于區(qū)域劃分的超級節(jié)點選取機(jī)制下當(dāng)節(jié)點請求次數(shù)分別到達(dá)550和700時，其信息檢索延遲增長率會突然升高，而此時DGSM下的信息檢索延遲還處在一個較低的水平。DGSM通過形成在網(wǎng)絡(luò)物理拓?fù)渲芯嚯x相近的相似興趣節(jié)點進(jìn)行聚類分組，更大程度地使得資源在組內(nèi)共享，減少了由超級節(jié)點組成的高速轉(zhuǎn)發(fā)層的帶寬損耗，降低了網(wǎng)絡(luò)中信息檢索延遲。

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

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

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

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

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

4 結(jié)束語

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