一種基于能量平衡的分簇算法

黃成兵

(阿壩師范學院 計算機科學系,四川 汶川 623002)

?

一種基于能量平衡的分簇算法

黃成兵

(阿壩師范學院 計算機科學系,四川 汶川 623002)

針對簇結構形成后的穩定性問題，分析當前移動自組織網絡中常見分簇算法的不足，提出了一種基于能量平衡的分簇算法。該算法在分簇過程中選簇首時，盡量減少信息交互次數，選取能量最優且離匯聚節點最近的節點為簇首，形成一個完整的簇。結果表明，該算法能夠節約節點能量，使簇結構穩定時間最長。

分簇算法；能量平衡；移動自組網；簇穩定性

移動自組網又稱為移動Ad Hoc網絡，是一種由若干個既充當路由功能又充當節點功能的無線終端組成的網絡，其特點是自組織、多跳和無需骨干網支撐，廣泛應用在世界各國的應急救災、軍事通訊、交通預警[1]及深海探測等不方便搭建基礎設施的重要領域。其抗毀性極強，具有十分重要的應用前景。最初移動自組網的結構采用所有節點都對等的平面式結構，即每個節點均有路由器和終端兩項功能。這種方式的最大優點是在源節點和目的節點之間實現多條通信路徑，減少擁塞。但由于移動自組網具有動態拓撲(節點隨處移動導致時常有新節點加入或退出網絡)、能量有限(依靠電池供電)及帶寬有限等特點，當節點數目增多時就會帶來路由開銷大、可擴展性差、移動管理復雜等問題。因而平面結構只適用于節點數較少的移動自組網。對于節點數較多的移動自組網，則應采用相應的分簇算法構成分層拓撲結構。通過不同的分簇算法，使相鄰的一組節點組成一個簇，簇內節點有簇首、網關和簇成員三種身份。處于相同簇內的各成員之間通信只需要經過簇首即可完成。處于不同簇內的多個節點之間進行通信，則需要通過各簇的網關節點進行轉發。相比平面結構而言，分層拓撲具有擴展性強、減少控制開銷、易于管理和優化帶寬等優點。

1 常見分簇算法及不足

分簇算法的目標是使用盡量簡單高效的算法建立起穩定且覆蓋全網的簇集合。這些簇應具有良好的穩定性及抗毀性，同時在鏈路容量許可的情況下簇首節點的數量應盡可能少。早期典型的分簇算法主要有最小標識優先算法(Lowest-ID)[2]和最大連接度(Max-Degree)優先算法[3]。它們均以移動自組網中某單個因素作為簇首的選取條件。如最小標識優先算法以ID值小的節點為簇首，最大連接度優先算法以連接度最多的節點為簇首，這樣導致網絡性能較差且缺乏公平性。后來有研究者對這兩個基本算法加以改進，如基于權值的分簇算法(DCA)[4]，它假設每個節點有唯一的權值，權值綜合考慮了節點連接度和標識等因素，最后取鄰居節點中權值最大的節點作為簇首，但作者并未對權值的計算作深入的討論。文獻[5]中也曾提到基于能量均衡的分簇算法，該算法在進行簇首選舉時，選舉剩余能量高于平均能量的節點成為簇首。該算法雖能夠保證所選舉出的簇首能量相對較優，但因簇首結點可能會過多而形成更多的簇。相比平面結構而言，分簇的優勢不能夠得到很好的體現。另外還有一些算法，其簇首的選擇與ID或最大連接度無關[6]，如基于節點位置預測的分簇算[7]、基于節點移動性的分簇算法、基于鏈路穩定性的分簇算法、基于模式識別的分簇算法等[8]。這些算法都因需要增加額外設備、應用環境要求較高、實現極其復雜等原因，在應用中仍末獲得較理想的效果，還需進一步完善。

2 基于能量平衡的分簇算法

經分析，現有移動自組網分簇算法存在各種缺陷或不足。受移動自組網自身能量十分有限且節點隨機移動性等特點制約，對移動自組網網絡結構研究的最終目的，就是為了在快速可靠的基礎上，找到盡可能長時間維持網絡結構不變的分簇算法，更長時間維護每個通信節點的生命周期。因而，節能、穩定成為分簇研究時最需要考慮的問題。前面提到的幾個分簇算法，對于節能的考慮，主要是從單個節點的角度進行思考，沒有對整個網絡的節能進行全面綜合的考慮。因簇首的負載大小及能量使用時限均取決于其所支持的節點數，維護簇結構與簇間路由需要消耗簇首大量資源。若選出的簇首能量有限，將使生成的簇很快解散，帶來系統更多的開銷和不穩定性。因而若將鄰居節點中能量最大的節點作為簇首是一種保障分簇結構相對維持較久時間的有效方法。同時，在設計整個分簇算法時，簇的形成及工作維持要盡量減少信息交互的次數，因為無線網絡通信模塊所消耗的能量將遠遠大于處理器模塊消耗的能量[9]。基于以上考慮，本文提出一種基于能量平衡的分簇算法EBCA(The energy balance clustering algorithm)。算法的基本思想是：當移動自組網各節點初始化成功后，在進行簇首選擇過程中，匯聚層節點收集與其連接的普通移動節點能量及距離等相關信息，結合給定的閾值，通過使用模糊理論計算出移動自組網各節點信號強度來判斷各自節點能量的優劣及距離，最終選取能量最優且離匯聚層相對較近的節點作為該簇的簇首。當簇首確定之后，找出簇間網關節點，最終建立快速可靠的，且盡可能長時間維持網絡生命周期的分簇結構。當簇結構在運行過程中若因某些節點加入或退出，或者因節點位置發生改變而導致拓撲結構變化時，將觸發新一次的分簇算法，重新選取簇首。在新一次的分簇算法中，原有的簇首可將其職責轉移給簇內其他最優成員節點。在整個算法運行過程中，均盡量考慮減少信息交互的次數，減少能源消耗，達到能量最優的目的。

3 基本描述

本文假設移動自組網中各節點工作時功率相同，能量各有不同，每個節點的能量范圍都是一個同心圓且半徑為1，當兩個同心圓有兩個交點時，認為這兩個節點之間可以直接進行雙向通信。對于網絡中的每一個節點，均分配有一個全網唯一的ID值，設定一個閾值 T(n)，用于確定該自組織網絡分簇，當分簇算法運行成功結束后，一個簇內只有一個簇頭，并且簇頭到簇內任意一節點的跳數均為1。基于以上假設，希望通過分簇算法分簇后，最終能夠達到使成簇速度盡可能迅速且全網中簇數量盡可能少，簇生成后維持最長時間(即簇結構的穩定性)的目標。簇的運行方式將分為簇建立階段和簇維護階段，所設計的算法將在移動自組網初始化或運行過程中拓撲發生改變(有節點加入或退出，位置發生變化)時自動運行。

4 網絡模型

文中假設有n個移動自組網工作節點，并且任其隨機分布在一個二維平面之內，同時具備如下特點：

a)初始化時所有節點能量均各有不同，且各節點能準確知道自身剩余能量百分比。

b)各節點處于平等地位且均具備數據處理能力和計算能力。

c)每個簇首選取出來后，簇內節點通過單跳即可到達簇首。

d)每個移動自組網節點均可根據自身接收的信號強度指示(RSSI)，判斷鏈路質量，決定是否增大廣播發送強度。通過接收到的信號強弱測定發送者與自身節點之間的距離，進而根據相應數據進行定位。

e)各節點采用廣播方式向四周發送無線信號，消耗自身能量。

5 具體算法

5.1 初始化階段

移動自組網初始化時，匯聚節點向整個網絡發送初始化的廣播信息。各節點收到初始化信息后計算出自身到匯聚節點距離，并檢測自身當前剩余能量百分比。普通節點收到初始化信息后，根據RSSI計算出自身到匯聚節點距離，并檢測本節點當前剩余能量，以百分比表示。最后，將距離和能量信息傳送至匯聚節點，其中傳送的數據包中包含節點ID、剩余能量、與匯聚節點距離。

表1 普通節點向匯聚節點報告報文格式

當匯聚節點收到周邊節點發送的相關信息后，計算出當前平均能量值Eavg和平均距離Davg，并把這兩個平均值又返回給附近移動節點。Eavg和Davg計算公式如下：

(1)

(2)

5.2 簇首選舉

在推選簇首的過程中，每個移動自組網節點將自己當前剩余能量與式(1)中得到的Eavg進行對比，小于Eavg，則不再參與競選，大于Eavg，則參加下一輪競選。在高于平均能量的節點中產生一個0～1的隨機數，將產生的隨機數與閾值T(n)比較，小于T(n)則成為候補簇首節點。T(n)由如下公式得出：

在比較過程中若遇節點能量及距離值相等則取ID值小的為簇首。當簇首節點確定后，普通節點(非簇首節點)則根據信號強弱來選擇離自己最近的簇加入，并等待簇首返回確認信息。選舉出的簇首在收到成員節點的請求后根據簇內的節點數目產生一個 TDMA 時隙表，并為每個加入的成員節點分配一個時隙，然后告知簇內的每個節點在分配的時間段內進行數據傳輸，簇內成員節點也是根據 TDMA 表來判斷何時發送數據的[10]，至此，完成整個簇生成過程。

5.3 簇運行維護階段

當簇結構建立以后，由于節點的一些行為可能會導致對簇結構產生嚴重影響，增加控制和通信開銷。為防止簇結構頻繁變化，須建立良好的簇維護方法。根據節點異常行為，可歸納為三種情況，即新節點加入，節點離開網絡，節點在網絡中移動。

a) 新節點加入。當一個新節點加入到現有的移動自組網時，將導致原有節點從休眠狀態轉為工作狀態并重新連接通信鏈路。此時的處理方法是，先給新加入節點分配ID值，根據信號強度指標尋找距新節點最近的簇首進行加入，宣布成為該簇的成員節點，記錄簇首信息，接著進行泛洪廣播，獲取該簇中其他節點信息。

b) 節點離開網絡。有幾種情況可導致節點離開網絡：節點從工作轉為休眠、節點能量不足導致關閉、節點鏈路中斷等。當節點離開移動自組網時，簇頭發送探測信息時無法獲取該節點信息，則簇頭更新其成員列表，若離開節點是簇頭節點則立即啟動初始化流程。

c)節點在網絡中移動。當節點在移動自組網中移動時，其位置發生變化。即從一個簇所在范圍移動到另一個簇所在范圍。因此，對于原有簇而言就是節點離開行為。對于后一個簇而言就是新節點的加入。節點在移動的過程中應向其他節點發送廣播信號使其他節點知道其在移動，否則按新節點加入來處理。

6 總結

在移動自組網中，分簇算法的優劣直接影響著網絡的生存時間和工作性能。本文提出一種基于能量平衡的分簇算法(EBCA)，該算法在進行分簇時，選取具有最優能量，離匯聚層結點距離最近的結點作為簇首，同時在生成過程中盡量減少信息交互次數。該算法有效地使移動自組網在實現快速可靠傳輸的基礎上，盡可能更長時間維持網絡生命。從而實現了在有限條件下提供最大化簇結構穩定時間,增強移動自組網穩定性，提高分組投遞率，加快簇間數據轉發效率的目的。

[1] 劉越甲.車聯網路口場景下分簇算法的研究[D].北京:北京交通大學,2016:1-6.

[2] Gerla M,Tsai J T C.Multicluster mobile,multimedia radio network.Wireless Networks,1995,1(3):255-265.

[3] Parekh A K.Selecting routers in ad-hoc wireless networks[C]//Proceedings SBT/IEEE Intl Telecommunications Symposium. 1994: 420-424.

[4] Basagni S.Distrbuted clustering for Ad Hoc networks[C]//Parallel Architectures, Algorithms, and Networks, 1999.(I-SPAN'99) Proceedings. Fourth InternationalSymposium on. IEEE, 1999: 310-315.

[5] 胡曉禹.基于能量均衡的分簇路由協議研究[D].太原:太原科技大學,2013:1-3.

[6] 付華,趙剛.無線傳感器網絡中一種能量均衡的分簇策略[J].計算機應用研究,2009.4:1494-1496.

[7] 吳迪，李晴，馮永新，等.一種基于地理定位信息的Ad Hoc分簇算法[J].計算機工程與應用，2005，42(14):135-141.

[8] Fall K,Varadhan K.The ns Manual(formerly ns notes and documentation).California: UC Berkeley, LBL, USC/ISI, and Xerox PARC,2007.

[9] Estrin D. Wireless sensor networks tutorial part IV: sensor network protocols[C]//Proc of the 8th Annual International Conference on Mobile Computing and Networking， 2002: 23-28.

[10] 龔本燦.一種能量均衡的無線傳感器網絡分簇算法[J].計算機應用研究,2008(11):3424-3429.

(責任編輯：熊文濤)

A Clustering Algorithm Based on Energy Balance

Huang Chengbing

(ComputerScienceDepartment,AbaTeachersUniversity,Wenchuan,Sichuan623002,China)

The shortcomings of common clustering algorithms are analyzed in current mobile ad hoc networks. A clustering algorithm is proposed based on energy balance for the stability of the cluster structure. In the clustering process, the algorithm can reduce the number of information interaction, and select the best energy and the nearest node from the sink node to become the cluster head, and further form a complete cluster. The results show that the algorithm can achieve the goal of saving energy and the longest time of cluster structure stability.

clustering algorithm; energy balance; mobile ad hoc network; cluster stability

2016-09-25

四川省教育廳重點課題 (11ZB151)；阿壩師范學院重點課題 (ASA12-23)

黃成兵(1980- ),男,四川宜賓人,阿壩師范學院計算機科學系副教授,碩士。

TP393

A

2095-4824(2016)06-0062-04