一種基于相對移動性的Ad-hoc網絡分簇算法

王　超　李長庚

(中南大學物理與電子學院　湖南 長沙 410083)

?

一種基于相對移動性的Ad-hoc網絡分簇算法

王超李長庚

(中南大學物理與電子學院湖南 長沙 410083)

針對Ad-hoc網絡中節點移動而導致網絡分層結構不穩定的問題，提出一種基于節點間的相對移動性的加權分簇算法RMCA(RelativeMobilityClusteringAlgorithm)。將局部節點的相關性運用到簇頭的選舉當中，并考慮距離因素的影響。運用層次分析法計算出各因素的權重，通過NS2仿真工具對該算法進行仿真，并與經典算法進行比較。結果顯示該算法在簇頭數目方面得到優化，在簇依附關系變化和簇頭更新次數方面性能提升10%～15%左右，有效地提高了簇結構的穩定性。

Ad-hoc網絡分簇權值相對移動性平均距離層次分析法

0　引　言

無線Ad-hoc網絡，又稱無線自組織網絡或者無線多跳網絡。該網絡由具有無線通信功能的節點組成，且不依賴于任何固定基礎設施。對網絡進行分簇可以提高Ad-hoc網絡的可擴展性。分簇算法對邏輯結構要求較高，且要盡可能地降低維護開銷[1]。在分層結構的網絡中，簇首承擔本簇內成員之間的通信以及本簇成員節點和其他簇成員間通信的任務。因此，選擇合理節點擔任簇頭成為分簇算法的關鍵問題。目前已有幾種受到普遍認可的分簇算法，如最小ID算法[2]、最高節點度算法[3]、加權分簇算法WCA(WeightedClusteringAlgorithm)[4]。最小ID算法較易實現，簇頭更換頻率慢，維護簇花費的開銷較小。但ID較小的節點會因長期擔任簇頭而消耗更多的能量，進而導致網絡出現分區的速度加快。最高節點度分簇算法中，簇的數目較少，降低了分組投遞時延，但較少的簇數目也會導致信道的空間重用率降低。

WCA算法考慮多方面因素的影響，且為每個節點分配一個權值，以此評價節點充當簇頭的能力[5]。該算法引入了電池能量、節點度、距離、節點速度四個因素作為計算權值的系統參數。可以根據不同的環境，對系統參數變量賦以不同權重，以適應不同需求，算法的自適應性較強[6,7]。但每個節點需要保存整個網絡系統的信息，每個循環周期僅能選舉出一個簇頭，延長了網絡初始化周期，增大了網絡通信開銷。在權值公式中，選取節點的平均速率和距離來評價節點的移動性和位置，有其不足之處：(1) 節點速率小只能代表個體節點穩定；(2) 與鄰居節點距離之和小，有可能是因為其簇成員的數目較少，并不能真正確定簇頭與簇成員距離的遠近。

本文提出一種基于相對移動性的分簇算法RMCA，在克服已有算法不足的同時，集合了其他算法的優點。最后在NS2下對RMCA算法進行仿真分析，預計RMCA算法形成的簇結構更穩定，網絡開銷更少。

1　算法描述

算法選取節點度、節點平均距離、節點的相對移動性以及節點剩余電量四個因素作為計算權值的系統參數，采用的權值公式為：

(1)

ω1+ω2+ω3+ω4=1

(2)

1.1權重的確定

本文算法利用權值公式通過計算選舉簇頭，優勢在于可以根據不同的網絡要求，賦予相應的權重以滿足不同的需求。因此，權重的確定尤為重要。層次分析法是美國運籌學家Saaty教授提出的一種簡便、靈活而又方便使用的多準則決策方法[8]。使用層次分析法解決問題時，分為四個步驟：

1) 建立目標問題的遞進關系結構；

2) 構造元素間的比較判斷矩陣；

3) 計算被比較元素的權重；

4) 計算各層次的組合權重。

在兩兩比較過程中，采用層次分析法中的1—9的比例標度，見表1所示。

表1　標度的意義

在Ad-hoc網絡中，由于節點的移動性而導致網絡的拓撲結構不斷變化，進而影響系統的性能，降低了網絡的可擴展性，甚至會引起網絡癱瘓。此外由于本算法針對的是Ad-hoc網絡中由于節點移動而導致網絡分層結構不穩定的問題，研究的重點是基于節點的移動性。故而認為移動性因素相比較其他因素更為重要。

除移動性外，電池能量、節點距離、節點度三個因素仍需考慮。在一些特定的場景中，節點能量有一定的保障，節點的距離與節點度的大小可通過動態調節節點傳輸功率來降低對系統性能的影響。如現代軍事演習或災難救援等，而節點移動速度是根據現實情況的需求，任意改變的，故而節點的移動性顯得尤為重要。同時，為了便于計算，因此假設三個因素同等重要。根據表1可得，移動性因素重要于其他三個因素，標度為a(a∈[2,9])；其他因素相對于移動性因素標度為1/a；相同元素之間比較或重要性相同的元素之間比較，因其重要性相同，標度為1,結果如表2所示。

表2　兩兩判斷的對比情況

將所得矩陣進行歸一化處理，得到矩陣的特征向量Wi：

(3)

(4)

再對矩陣進行一致性檢驗，公式為：

(5)

(6)

(7)

其中，CI為一致性指標，λmax為矩陣的最大特征值,RI為隨機一致性指標,CR為一致性比率[9]。n為因素的個數，n=4。

隨機一致性指標RI 數值表如表3 所列。如果一致性比率指標：CR=CI/RI<0.1時，認為其不一致程度在容許范圍之內，一致性檢驗通過[10]。

表3　隨機一致性指標RI數據表

本文對不同的a值分別進行實驗仿真，現以中間值5為例進行介紹。當a=5時,計算此時的一致性比率：

認為一致性檢驗通過。故而可得當a=5時的判斷矩陣最終為：

通過計算得到權重為ω1=0.135，ω2=0.135，ω3=0.595，ω4=0.135。

1.2最佳節點度的計算

在Ad-hoc分層網絡中，簇的大小影響網絡運行效率。簇頭節點覆蓋范圍應該適中，覆蓋范圍過大，就會發生擁塞，過小則帶寬利用率降低；為了使吞吐率達到最佳，采用了Gerla等給出的一個結論[11]：網絡中的最佳節點度的大小為:

(8)

1.3平均相對移動性的計算

在WCA算法中節點平均速率的確定依賴于節點的定位，現有的大多數文獻所采取的策略是對節點安裝GPS定位裝置，這加大了網絡成本，增大了通信消耗。使用節點相對其鄰居節點的相對移動速率，提高了簇結構的穩定性，并且不需要明確節點每一時刻的具體位置，這大大減少了網絡能量消耗。

本方案利用節點連續兩次與其相鄰節點的交互信息，計算每一個節點的平均相對移動性：

(9)

其中,Pr1、Pr2為鄰居節點連續兩次接收功率的大小，Pis1、Pis2為節點連續兩次發送功率大小。該移動性的評價是節點與其他鄰居節點連續兩次交互信息之間移動性的狀態，避免了節點因能耗等因素導致發送功率改變所帶來的影響，確定了評價移動性的唯一標準，即Vi越小越好。此方案不依賴于GPS等定位儀對節點進行定位，降低了網絡能耗，同時，局部范圍內節點間的相關性較大。因此，網絡局部的穩定性較強，所選的簇結構較為穩定。

1.4平均距離的計算

實驗傳播模型采用雙反射模型，運用文獻[12,13]中的跨層設計方案，利用發送信號強度與MAC層接收信號強度的關系[14]：

(10)

式中，Pt為節點的發送信號強度，si為發送節點和接收節點之間的距離，G代表發送節點和接收節點的增益，ht和hr分別為發射天線和接收天線的高度，Pr為節點的MAC層接收信號的強度。由式(10)可得發送節點和接收節點之間的距離為:

(11)

由此可計算出節點i到其所有鄰居節點的平均距離:

(12)

本方法考慮了鄰居節點的個數，避免了因節點度較小而得出距離較近的誤判。

1.5簇頭的選舉

當網絡中有新節點加入或網絡開始成簇時，網絡通過初始化選舉簇頭。所有網絡中的節點通過發送“hello”消息以此來建立相互之間的鏈路，進而計算權值。步驟如下：

第一步節點間通過周期性的發送交互“hello”信息報文獲知鄰居節點的信息，得到每個節點的鄰居節點數，作為它的度數di,其中“hello”信息報文攜帶節點ID、節點度、權值、所屬簇、鄰居信息表等；

第二步計算得到節點度與最佳節點度差值Di；

第三步用Ei表示節點i剩余的電量；

第四步計算得到節點相對于其鄰居節點的相對移動性Vi；

第六步每個節點i按照式(1)計算組合權重Wi，并將權值置于“hello”信息中廣播；

第七步所有相鄰的節點通過比較權值，擁有最小權值的節點作為簇頭，并廣播消息宣布自己的簇頭地位，在權值相等的情況下，ID較小的節點具有優先成為簇頭的權利，未知節點接收到某簇頭的廣播消息即成為該簇頭的成員節點，修改自己的所屬簇列表，并廣播至網絡，且自身不再參與簇頭選舉；

第八步不斷重復前七步，直到所有節點都處于統治集范圍內，初始化過程結束。

1.6簇的更新維護

在簇的初始化完成后，由于節點自身的移動、耗能等內在因素和外在環境的變化，可能導致節點間的鏈路發生改變，進而使網絡結構發生改變，這需要對網絡結構進行實時更新維護：

1) 鏈路失效。如果該鏈路兩端為同一層次的節點，或一個節點是簇頭，另一個節點是其他簇的成員節點，則只需更新自己的成員信息表和鄰居信息表；如果鏈路兩端有簇依附關系，則簇頭更新自己的信息表，成員節點則找尋其他的簇，并成為新簇的成員節點；如果沒有發現其他簇頭，則自成一簇。

2) 新建鏈路。假設發生在節點i、j之間。

(1) 如果鏈路兩端都是成員節點，則只需更新自己的鄰居信息表。

(2) 如果i是簇頭，j是以節點k為簇頭的成員節點，則比較節點i和k的權值。如果weight(i)小于weight(k)，則節點j加入以i為簇頭的簇，節點i和節點k更新自己的鄰居信息表和成員信息表。如果weight(i)大于weight(k)，則節點i只是更新自己的鄰居信息表，其余狀態保持不變。

(3) 如果鏈路兩端都是簇頭，則只更新自己的鄰居信息表，其余狀態保持不變。

2　算法仿真與性能分析

NS2是面向對象的網絡仿真工具，具有豐富的構件庫，但NS2中沒有集成分族算法。因此需要用OTcl腳本語言擴展NS2中的代理來實現仿真，對RMCA算法進行模擬分析，并與其他經典分簇算法進行比較。

2.1仿真性能指標

1) 平均簇頭數目。當簇頭數目過大時，會增大端到端的延遲、增加通信開銷；當簇頭數目過少時，會加大簇頭節點的工作強度，加快網絡出現分割的時間。

2) 單位時間內，簇依附關系變化次數。簇結構越穩定，節點重新加入其他簇的次數就越少。

3) 單位時間內，簇頭統治集更新次數。分簇算法在分簇過程中會有大量的計算與通信開銷，因此要盡可能降低簇頭更新的頻率[17]。本算法規定，當有節點移出原簇，卻無法加入其他簇，則自成簇頭，并觸發統治集更新。此外，當大量節點的簇依附關系發生變化，說明當前網絡的簇結構極不穩定。因此，本算法規定單位時間內簇依附關系變化次數超過10時，觸發統治集更新。

2.2仿真結果分析

仿真環境采用NS2軟件中的內置工具setdest生成[18]，場景為100×100單位距離的區域；節點數N=100個；節點的移動方式采用RandomWayp-oint模型，Waypoint方式的節點移動速度為5～50m/s；節點傳輸范圍為5～50m；節點初始狀態能量設為50J；模擬時間為300s；監測周期為5s。

實驗考查節點傳輸范圍和節點移動速度兩種因素對算法的影響，故模擬時采用兩種仿真場景，圖1-圖3采用場景一：節點移動速率為10m/s，節點傳輸范圍由5m均勻變化到50m。圖4-圖5采用場景二：節點傳輸范圍為20m，節點的移動速率由5m/s均勻變化到50m/s。實驗中每組數據通過50次仿真結果平均得到。

在實驗中，隨著節點傳輸距離的增加，簇頭數目逐漸減少，當傳輸距離達到20m后，簇頭數目減少的趨勢逐漸變緩，最終減少到1個。如圖1所示。由于WCA算法和RMCA算法對節點度的限制，簇頭數目適中，且接近符合最佳節點度數的要求。

圖1　簇頭數目隨節點傳輸距離的變化

節點重入簇次數隨著節點的傳輸距離增大而變化的情況如圖2所示。四種分簇算法都呈拋物線狀，因為當傳輸距離較小時，網絡形成的簇結構較多，成員節點很少，節點脫離原簇的概率小。節點脫離原簇的概率隨著距離的增大也逐漸增加，峰值出現在傳輸距離為25m左右。隨后，由于簇的統治范圍增大，節點脫離原簇的概率再次減小。RMCA算法較其他三種算法而言，重入簇次數明顯減小， 簇的穩定性增強。

圖2　節點重入簇次數隨節點傳輸距離的變化

節點傳輸距離對統治集更新的影響如圖3所示。四種算法的結果呈拋物線狀，峰值出現在10m左右。本方案中，節點與鄰居節點的距離考慮節點度的影響，計算平均距離，使簇頭到簇成員的距離更為準確，因此在同等條件下，本算法的統治集更新次數較少。

圖3　統治集更新次數隨節點傳輸距離的變化

重入簇次數隨節點速度的變化情況如圖4所示，RMCA算法明顯較優。這是由于當節點速度較快時，節點更容易發生簇間移動，本方案采用節點間的相對移動性，減弱了節點移動速度對簇結構的影響，能更好地維護簇的拓撲結構。

圖4　重入簇次數隨節點移動速度的變化

圖5反映了統治集更新次數隨節點移動速度的變化情況，隨著移動速度的增大，四種算法的統治集更新次數都有增大的趨勢。相比較而言，RMCA與WCA算法考慮到了節點的移動性的影響，因此要優于其他算法。RMCA算法利用節點間的相對移動性，節點之間的相關性較大，考慮到了節點周圍拓撲結構的變化，因此本算法所形成的簇結構和網絡的統治域更為穩定。

圖5　統治集更新次數隨節點移動速度的變化

2.3不同的權重對于網絡性能的影響

本文的仿真是在以移動性的標度為5為例的基礎上進行的，不同的標度值得出的權重各有不同。現對其他標度值進行仿真對比。仿真環境中的參數設定為：節點移動速率為10m/s,節點的傳輸范圍為20m。其他保持不變。仿真結果如表4所示。

表4　不同標度值對網絡系統性能的影響

由表4和前文中的仿真圖可知，在本算法中，a取不同的值時，系統性能較其他算法總體有所提升，且當a=5時，網絡性能最優。

從表4中可以看出，平均簇頭數隨a值的增大呈遞減的趨勢。因為當a較小時，節點度的影響相對較大，對簇頭數目有一定的約束，隨著a值的增大，節點度的影響相對減弱，簇頭數目隨之減少，偏離最佳節點度的幅度隨之增大。

平均簇依附關系和平均統治集更新次數隨a值的增大，呈拋物線狀。當a較小時，節點移動性的重要程度較低，節點移動性對簇頭的選擇貢獻值較小，導致所確定的簇結構穩定性較差，故而簇依附關系變化次數和統治集更新次數相應較大；當a較大時，移動性對于簇頭選擇的貢獻較大，得到的簇結構只是物理上的相對穩定，但因為節點能量、節點度以及距離因素對網絡拓撲結構的形成貢獻較少，導致部分節點因能量損耗，節點分布不均勻、節點死亡等因素的影響而引起網絡結構的不穩定。最終導致節點平均簇依附關系變化次數和平均統治集更新次數逐漸升高。

3　結　語

RMCA算法考慮四個因素，具有更好的適應性，與僅考慮單因素的算法相比，雖然復雜度稍高，但可通過極少的計算開銷而獲得較好的系統性能。并且運用層次分析法得到的權重更加符合主觀和客觀的要求。與WCA算法比較，RMCA算法采用相對移動性，更好地考慮了節點局部拓撲結構的變化。另外，采用平均距離，考慮節點的節點度對距離因素的影響，故而在簇結構穩定性、能量利用率等方面實現了合理優化。通過仿真工具NS2，將RMCA算法和WCA等三種算法進行了分析比較，驗證了RMCA算法形成的簇結構具有更強的穩定性，節點重新入簇次數和統治集更新次數等方面性能提高了10%～15%左右。

[1]AkbariTorkestaniJ,MeybodiMR.Amobilitybasedclusterformationalgorithmforwirelessmobilead-hocnetworks[J].Clustercomputing,2011,14(4):311-324.

[2]LinCR,GerlaM.Adaptiveclusteringformobilewirelessnet-works[J].IEEEJournalonSelectedAreasinCommunication,1997,15(7):1268-1275.

[3]GerlaM,TsaiTC.Multicluster,Mobile,Multime-Dia,RadioNetwork[C]//JournalofWirelessNetworks.1995:255-265.

[4]ChatterjeeM,DasS,TurgutD.WCA:AWeightedClusteringAlgorithm(WCA)formobileadhocnetworks[J].ClusterComputing,2002,5(7):193-204.

[5]DhurandherSK，SinghGV.WeightBasedAdaptiveClusteringinWirelessAdHocNetworks[C]//Proceedingsofthe2005IEEEInternationalConferenceonPersonalWirelessCommunications,NewDelhi,India,2005:95-100.

[6] 李瑾,潘宏,劉中兵，等.MANET中基于連通支配集的組合權值簇生成算法[J].計算機應用,2012,32(7):1840-1843,1855.

[7] 杜國勇,束永安.基于鏈接率的AdHoc自適應按需加權分簇算法[J].計算機技術與發展,2014,24(1):93-97.

[8] 孫璐.層次分析法中用于確定權重的最小-最大優化方法[J].東南大學學報:英文版,2012,28(2):245-250.

[9]SainiVK，KumarV.AHP,fuzzysetsandTOPSISbasedreliablerouteselectionforMANET[C]//ComputingforSustainableGlobalDevelopment(INDIACom),2014InternationalConferenceon.NewDelhi,India,2014:24-29.

[10] 許樹柏．層次分析法原理[M]．天津：天津大學出版社，1988.

[11]XuKaixin,HongXiaoyan,MarioGerla，etal.Anadhocnetworkwithmobilebackbones[J].IEEE,ICC,2002,16(4):11-21.

[12] 鄭騰飛,朱琦.認知AdHoc網絡中的跨層路由協議[J].計算機應用,2011,31(S2):9-13.

[13] 張永敏,徐偉強,黃炯，等.AdHoc網絡節能型功率控制與擁塞控制的跨層優化[J].軟件學報,2013,24(4):900-914.

[14] 王慶文,史浩山,戚茜，等.一種新的AdHoc網絡跨層能量均衡廣播協議[J].西北工業大學學報,2011,29(5):671-675.

[15] 柯志亨,程榮祥,鄧德雋.NS2 仿真實驗-多媒體和無線網絡通信[M]. 北京:電子工業出版社,2009.

[16]QiBing,ShenFangyang.Propagationmodelsformulti-hopwirelessnetworksinNs-2Simulator[C]// 8thInternationalConference2011,Infor-mation,Technology:NewGenerations.lasVegas,Nevadam,USA,2011:701-706.

[17]YuJiguo,WangGuanghui.Constructingminimumextendedweakly-connecteddominatingsetsforclusteringinadhocnetworks[J].JournalofParallelandDistributedComputing,2012,72(1):35-47.

[18] 黃化吉，馮穗力,秦麗姣，等.NS網絡模擬和協議仿真[M].北京：人民郵電出版社，2010.

ANAD-HOCNETWORKCLUSTERINGALGORITHMBASEDONRELATIVEMOBILITY

WangChaoLiChanggeng

(School of Physics and Electronics,Central South University,Changsha 410083， Hunan, China)

Aimingattheinstabilityproblemofnetworkhierarchystructurecausedbythemovementofnodesinad-hocnetwork,thispaperproposesaweightedclusteringalgorithmwhichisbasedonrelativemobilitybetweennodes.Thealgorithmappliesthecorrelationmobilitybetweenlocalnodestoclusterselection,andconsiderstheeffectofdistancefactoraswell.Throughtheanalytichierarchyprocess(AHP)itcalculatestheweightofeachfactor.ThealgorithmissimulatedusingNS2simulationtoolandcomparedwiththeclassicalalgorithms.Resultsshowthatthisalgorithmisoptimisedinnumbersoftheclusterhead,theperformanceincreasesofabout10%～15%innumberoftheclusterattachmentchangesandthenumberofclusterheadupdate.Itimprovesthestabilityoftheclusterstructureeffectively.

Ad-hocnetworkClusteringWeightsRelativemobilityAveragedistanceAHP

2014-08-23。王超，碩士生，主研領域：無線自組織網絡，無線傳感器網絡拓撲控制，路由協議。李長庚， 教授。

TP393.0

ADOI:10.3969/j.issn.1000-386x.2016.03.034