基于節(jié)點移動特性的移動P2P網(wǎng)絡(luò)分簇算法

宋人杰，鄒振婉，周欣欣

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

?

基于節(jié)點移動特性的移動P2P網(wǎng)絡(luò)分簇算法

宋人杰，鄒振婉，周欣欣

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

摘要：為了提高移動P2P網(wǎng)絡(luò)的覆蓋層拓撲穩(wěn)定性，提出一種基于節(jié)點移動特性的移動P2P網(wǎng)絡(luò)分簇算法。該算法通過對移動P2P網(wǎng)絡(luò)的覆蓋層拓撲變化與節(jié)點移動特性的關(guān)系的研究，將具有相同運動特性且物理位置臨近的節(jié)點聚集成簇，并選取性能較好的節(jié)點作為簇首，使得簇內(nèi)節(jié)點能夠最大程度的保持覆蓋層拓撲結(jié)構(gòu)的穩(wěn)定性。最后通過實驗驗證了該算法的有效性。

關(guān)鍵詞：移動P2P網(wǎng)絡(luò)；分簇算法；運動特性；拓撲變化

作為一種新興的移動數(shù)據(jù)共享方式，移動P2P網(wǎng)絡(luò)以其具有無中心、自組織等特性，在軍事戰(zhàn)場、搶險救災(zāi)以及用戶信息共享等領(lǐng)域有著重要的實用價值和廣闊的應(yīng)用前景[1，2]。然而，由節(jié)點的移動性造成的覆蓋層拓撲頻繁變化問題[3]，不僅減低了覆蓋層的數(shù)據(jù)傳輸速率，同時會產(chǎn)生大量的冗余信息，對底層物理網(wǎng)絡(luò)造成巨大的帶寬壓力，降低網(wǎng)絡(luò)的整體工作性能。

能夠感知網(wǎng)絡(luò)拓撲的分簇方法雖然可以解決覆蓋層拓撲的頻繁變化問題，但網(wǎng)絡(luò)開銷較大且缺乏對節(jié)點的移動特性的考量。通過對節(jié)點移動特性的研究發(fā)現(xiàn)，在實際應(yīng)用環(huán)境中，移動節(jié)點的行為通常不是隨機的，節(jié)點間的關(guān)系和覆蓋層拓撲變化與現(xiàn)實社會有聯(lián)系，呈現(xiàn)分組活動特性[4，5]。因此，本文從節(jié)點移動特性出發(fā)，充分利用這種潛在關(guān)系，提出一種基于節(jié)點移動特性的移動P2P網(wǎng)絡(luò)分簇算法，從而解決網(wǎng)絡(luò)拓撲的頻繁變化問題，減少拓撲維護費用、提高系統(tǒng)穩(wěn)定程度，對提高移動P2P網(wǎng)絡(luò)服務(wù)質(zhì)量具有重要意義。

1基于節(jié)點移動特性的分簇算法

研究發(fā)現(xiàn)在實際的環(huán)境中，比如參觀者在參觀博物館時，每個參觀者都根據(jù)自身的不同興趣以不同的速度循著不同的路線行進。因為參觀者之間有相同興趣和愛好，參觀者在走動中常常會表現(xiàn)出分組特征，如圖1、圖2所示。所以，本文提出的分簇算法的核心思想是：根據(jù)節(jié)點移動特性，將具有相同移動特性且物理位置臨近的節(jié)點聚集成簇，使得簇內(nèi)節(jié)點由于具有相同運動特性，從而能夠最大程度的保證分簇的穩(wěn)定程度。

圖1 參觀者初始位置圖2 一段時間后參觀者的位置

1.1相關(guān)定義

定義1：無向圖G(V，E)表示移動P2P網(wǎng)絡(luò)的覆蓋層拓撲關(guān)系，V表示移動節(jié)點集合，E表示邊集合。

定義2：如果節(jié)點u和v之間有如下關(guān)系邊(u，v)∈E，那么節(jié)點u和v互為相鄰節(jié)點。

定義4：如果節(jié)點u和v是朋友節(jié)點，節(jié)點v和w也是朋友節(jié)點，那么節(jié)點u和w是朋友節(jié)點。

定義4將相鄰節(jié)點間的朋友節(jié)點關(guān)系擴展到了不相鄰的節(jié)點之間，節(jié)點u與v的距離、平均值以及標(biāo)準(zhǔn)方差的計算方法如下：

(1)

(2)

(3)標(biāo)準(zhǔn)方差δ的計算方法：

(3)

1.2簇首節(jié)點的選取

在移動P2P網(wǎng)絡(luò)的維護和查詢過程中需要簇首不僅有較強的計算能力，能夠及時響應(yīng)并處理查詢請求，而且需要簇首擁有充足的存儲空間以便于容納更多的節(jié)點信息。因此這里選擇節(jié)點的CPU處理速率、存儲容量以及有效帶寬作為衡量節(jié)點性能的重要因子。節(jié)點性能Ability的計算方法如下：

Ability[u]=α×B[u]+β×C[u]+γ×S[u]，

(4)

1.3簇生成算法

分簇算法的步驟如下：

步驟S1，按照公式(4)計算節(jié)點的性能Ability值。

步驟S2，按照公式(1)、(2)、(3)計算節(jié)點與其相鄰節(jié)點的距離、平均值以及標(biāo)準(zhǔn)方差。

步驟S3，依據(jù)節(jié)點的移動特性，節(jié)點建立自身的朋友節(jié)點列表，具體方法是：假設(shè)節(jié)點u和v滿足定義3，則節(jié)點u將節(jié)點v加入到自己的朋友節(jié)點列表中，節(jié)點u與節(jié)點v周期性地交換彼此處的朋友節(jié)點列表，若節(jié)點w是節(jié)點v的朋友節(jié)點，但節(jié)點w不在節(jié)點u的朋友列表中，則將節(jié)點u將節(jié)點w加入到其朋友列表中；若節(jié)點u的朋友列表中已經(jīng)存在節(jié)點w，但其全部朋友節(jié)點發(fā)來的朋友節(jié)點列表內(nèi)并不存在節(jié)點w，則將節(jié)點w從節(jié)點u的朋友列表內(nèi)刪除。

步驟S4，依據(jù)節(jié)點的移動特性，選取簇首節(jié)點，構(gòu)建分簇結(jié)構(gòu)，具體方法是：將節(jié)點u的Ability值與其朋友列表中的節(jié)點進行比較，如果節(jié)點u的Ability值最大，則節(jié)點u升級成簇首，并將此消息廣播給它的朋友節(jié)點，同時邀請朋友節(jié)點進入該節(jié)點所在的簇；若節(jié)點u的Ability值不是最大，則申請加入以Ability值最大的朋友節(jié)點為簇首的簇中。

步驟S5，重復(fù)步驟S2-步驟S4，直到網(wǎng)絡(luò)中所有節(jié)點或成為簇首節(jié)點，或從屬于某一個簇內(nèi)。

1.4簇動態(tài)維護算法

新節(jié)點加入過程：節(jié)點首先向周圍節(jié)點發(fā)送HELLO消息以獲取與鄰近節(jié)點之間的距離，然后根據(jù)距離關(guān)系構(gòu)建朋友節(jié)點列表，并向其所有朋友節(jié)點發(fā)送信息以獲取其所有朋友節(jié)點所屬簇對應(yīng)的簇首信息，最后向這些簇首發(fā)送HELLO消息以獲取兩者之間的距離，通過比較，選取相距最近的簇首申請加入其簇。

節(jié)點離開：若離開節(jié)點是普通節(jié)點，該節(jié)點會向其所有朋友節(jié)點及簇首發(fā)送離開消息，簇首在收到消息后，更新簇成員列表。若離開節(jié)點是簇首，簇首會向其朋友節(jié)點及簇成員發(fā)送離開消息，以便朋友節(jié)點能及時更新朋友節(jié)點列表，簇成員能及時重新選取簇首避免發(fā)生網(wǎng)絡(luò)故障。

節(jié)點失效處理：若網(wǎng)絡(luò)中的某個節(jié)點已經(jīng)失效，那么其朋友節(jié)點能夠通過定期的心跳函數(shù)檢測到該情況。若失效節(jié)點是普通節(jié)點，那么在朋友節(jié)點檢測出其失效后，該朋友節(jié)點首先會把其從朋友節(jié)點列表刪除，其次檢查兩者是否屬于同一個簇，若屬于同一個簇，則通知簇首該節(jié)點已失效，否則僅更新自身朋友節(jié)點列表；若失效節(jié)點是簇首，當(dāng)朋友節(jié)點檢測到該節(jié)點已失效后，該朋友節(jié)點首先更新自身的朋友節(jié)點列表，其次檢查兩者是否屬于同一個簇，若屬于同一個簇，則通知其它節(jié)點，簇首已失效，并再次選擇簇首，否則僅做更新朋友節(jié)點列表處理。

2仿真分析

本文采用NS-2.4[6]仿真工具對提出的分簇算法C-MP2P和Clustering Scheme[7]進行對比。80個移動節(jié)點都基于組移動模型RPGM[8]且分布在200×200 m的正方形內(nèi)，節(jié)點所具有的最大移動速度是20 m/s，天線覆蓋范圍被設(shè)置成100 m，實驗進行300 s，每隔2 s節(jié)點與相鄰節(jié)點進行一次HELLO消息傳輸。

簇首的變化速率和節(jié)點狀態(tài)的變化速率被用來衡量C-MP2P算法的性能，簇首變化速率是指簇首在單位時間范圍內(nèi)的變化次數(shù)，用模擬時間段內(nèi)簇首的改變次數(shù)除以模擬時間來對其進行表示，簇結(jié)構(gòu)的穩(wěn)定程度取決于簇首的變化頻率，頻率越小，越穩(wěn)定；節(jié)點狀態(tài)變化速率是指成員節(jié)點在單位時間內(nèi)的狀態(tài)變化次數(shù)，其值表示為模擬時間內(nèi)成員節(jié)點發(fā)生改變的次數(shù)與模擬時間的商，簇結(jié)構(gòu)的穩(wěn)定度與節(jié)點狀態(tài)的發(fā)生改變的次數(shù)有關(guān)，次數(shù)越小越穩(wěn)定[9,10]。

圖3和圖4分別表示簇首的變化速率和節(jié)點狀態(tài)的變化速率隨節(jié)點速度變化的情況。由圖3和圖4可知，伴隨節(jié)點的移動速度的不斷增加，這兩種算法對應(yīng)的簇首變化率和節(jié)點狀態(tài)變化率均隨之增加，這說明節(jié)點移動的速率越快，簇結(jié)構(gòu)的穩(wěn)定性也會隨之降低。由于C-MP2P算法對節(jié)點的移動特性考慮的較為充分，同簇節(jié)點具有相同的運動特征，速度變化大致相同，而Clustering Scheme算法并未考慮這些因素，因此C-MP2P算法的性能受速度變化的影響較小，性能明顯優(yōu)于Clustering Scheme算法。

圖3 簇首變化速率圖4 節(jié)點狀態(tài)變化速率

3總結(jié)

本文根據(jù)移動P2P網(wǎng)絡(luò)覆蓋層拓撲結(jié)構(gòu)變化與節(jié)點的移動特性之間的聯(lián)系，提出一種基于節(jié)點移動特性的移動P2P網(wǎng)絡(luò)分簇算法。該算法將物理位置臨近且具有相同運動特征的兩個相鄰節(jié)點劃分到一個簇內(nèi)，使得在分簇時可以產(chǎn)生更穩(wěn)定的簇結(jié)構(gòu)。由仿真結(jié)果可知，該算法可以有效提升分簇的穩(wěn)定程度，適應(yīng)于具備高度移動性的無線網(wǎng)絡(luò)環(huán)境，有很大的實用價值。

參考文獻

[1]Xin-Xin Z，Zhen-Wan Z，Peng K，et al.A Survey of Resource Discovery in Mobile Peer-to-Peer Networks[C]//Communication Systems and Network Technologies (CSNT)，2015 Fifth International Conference on.IEEE，2015:122-125.

[2]Waluyo A B，Taniar D，Rahayu W，et al.Mobile Peer-to-Peer data dissemination in wireless ad-hoc networks[J].Information Sciences，2013，230:3-20.

[3]歐中洪，宋美娜，戰(zhàn)曉蘇，宋俊德.移動對等網(wǎng)絡(luò)關(guān)鍵技術(shù)[J].軟件學(xué)報，2008，19(2):404-418.

[4]張斯捷，柏青，蘇旸.移動P2P網(wǎng)絡(luò)中基于穩(wěn)定組的雙向匿名通信方案[J].計算機應(yīng)用，2013，33(6):1615-1618.

[5]吳旭.基于增強穩(wěn)定組模型的移動P2P網(wǎng)絡(luò)信任評估方法[J].計算機學(xué)報，2014，37(10):2118-2127.

[6]Ns-2 network simulator [EB/OL].[2013-05-16].http://www.Isi.edu/nsnam/ns/.

[7]楊忠儀，左克.一種適用于移動對等網(wǎng)絡(luò)的分簇算法[J].計算機工程與科學(xué)，2014，26(7):1268-1274.

[8]Wang K H，Li B.Efficient and guaranteed service coverage in partitionable mobile ad-hoc networks[C]//INFOCOM 2002.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE.IEEE，2002，2:1089-1098.

[9]張強，胡光明，陳海濤等.MANET基于客觀信任度建模的分簇算法與分析[J].通信學(xué)報，2009，30(2):12-21.

[10] 宋人杰，史長東，崔衛(wèi)麗.復(fù)雜場景中多細節(jié)層次模型生成新算法[J].東北電力大學(xué)學(xué)報，2014，34(13)：80-84.

A Clustering Algorithm Based on Node Mobility for Mobile P2P Network

SONG Ren-jie，ZOU Zhen-wan，ZHOU Xin-xin

(School of Information Engineering，Northeast Dianli University，Jilin Jilin 132012)

Abstract：Aiming at the problem that layer topology changes frequently in mobile P2P network which is caused by node mobility，a clustering algorithm based on node mobility is proposed.By studying the relationship between the changes of the topology structure and the changes of node mobility，this algorithm divide the nodes with adjacent physical location and same mobility into a cluster，and select the nodes which has the best performance as the cluster-head，which makes the nodes in the same cluster can maintain the maximum degree of network topology stability.Experimental results show the effectiveness of proposed algorithm.

Key words：Mobile P2P networks；Clustering；Mobility；Topology change

中圖分類號：TP393

文獻標(biāo)識碼：A

文章編號：1005-2992(2016)01-0087-04

作者簡介：宋人杰(1963-)，女，吉林省吉林市人，東北電力大學(xué)信息工程學(xué)院教授，碩士，碩士生導(dǎo)師，主要研究方向:計算機在電力系統(tǒng)中的應(yīng)用.

收稿日期：2015-12-18