宋人杰，鄒振婉，周欣欣

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

?

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

宋人杰，鄒振婉，周欣欣

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

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

關(guān)鍵詞：移動(dòng)P2P網(wǎng)絡(luò)；分簇算法；運(yùn)動(dòng)特性；拓?fù)渥兓?/p>

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

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

1基于節(jié)點(diǎn)移動(dòng)特性的分簇算法

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

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

1.1相關(guān)定義

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

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

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

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

(1)

(2)

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

(3)

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

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

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

(4)

1.3簇生成算法

分簇算法的步驟如下：

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

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

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

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

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

1.4簇動(dòng)態(tài)維護(hù)算法

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

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

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

2仿真分析

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

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

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

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

3總結(jié)

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

參考文獻(xià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)曉蘇，宋俊德.移動(dòng)對(duì)等網(wǎng)絡(luò)關(guān)鍵技術(shù)[J].軟件學(xué)報(bào)，2008，19(2):404-418.

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

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

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

[7]楊忠儀，左克.一種適用于移動(dòng)對(duì)等網(wǎng)絡(luò)的分簇算法[J].計(jì)算機(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]張強(qiáng)，胡光明，陳海濤等.MANET基于客觀信任度建模的分簇算法與分析[J].通信學(xué)報(bào)，2009，30(2):12-21.

[10] 宋人杰，史長(zhǎng)東，崔衛(wèi)麗.復(fù)雜場(chǎng)景中多細(xì)節(jié)層次模型生成新算法[J].東北電力大學(xué)學(xué)報(bào)，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

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

收稿日期：2015-12-18