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

黃成兵

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

?

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

黃成兵

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

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

分簇算法；能量平衡；移動自組網(wǎng)；簇穩(wěn)定性

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

1 常見分簇算法及不足

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

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

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

3 基本描述

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

4 網(wǎng)絡(luò)模型

文中假設(shè)有n個移動自組網(wǎng)工作節(jié)點，并且任其隨機(jī)分布在一個二維平面之內(nèi)，同時具備如下特點：

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

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

c)每個簇首選取出來后，簇內(nèi)節(jié)點通過單跳即可到達(dá)簇首。

d)每個移動自組網(wǎng)節(jié)點均可根據(jù)自身接收的信號強(qiáng)度指示(RSSI)，判斷鏈路質(zhì)量，決定是否增大廣播發(fā)送強(qiáng)度。通過接收到的信號強(qiáng)弱測定發(fā)送者與自身節(jié)點之間的距離，進(jìn)而根據(jù)相應(yīng)數(shù)據(jù)進(jìn)行定位。

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

5 具體算法

5.1 初始化階段

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

表1 普通節(jié)點向匯聚節(jié)點報告報文格式

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

(1)

(2)

5.2 簇首選舉

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

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

5.3 簇運(yùn)行維護(hù)階段

當(dāng)簇結(jié)構(gòu)建立以后，由于節(jié)點的一些行為可能會導(dǎo)致對簇結(jié)構(gòu)產(chǎn)生嚴(yán)重影響，增加控制和通信開銷。為防止簇結(jié)構(gòu)頻繁變化，須建立良好的簇維護(hù)方法。根據(jù)節(jié)點異常行為，可歸納為三種情況，即新節(jié)點加入，節(jié)點離開網(wǎng)絡(luò)，節(jié)點在網(wǎng)絡(luò)中移動。

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

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

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

6 總結(jié)

在移動自組網(wǎng)中，分簇算法的優(yōu)劣直接影響著網(wǎng)絡(luò)的生存時間和工作性能。本文提出一種基于能量平衡的分簇算法(EBCA)，該算法在進(jìn)行分簇時，選取具有最優(yōu)能量，離匯聚層結(jié)點距離最近的結(jié)點作為簇首，同時在生成過程中盡量減少信息交互次數(shù)。該算法有效地使移動自組網(wǎng)在實現(xiàn)快速可靠傳輸?shù)幕A(chǔ)上，盡可能更長時間維持網(wǎng)絡(luò)生命。從而實現(xiàn)了在有限條件下提供最大化簇結(jié)構(gòu)穩(wěn)定時間,增強(qiáng)移動自組網(wǎng)穩(wěn)定性，提高分組投遞率，加快簇間數(shù)據(jù)轉(zhuǎn)發(fā)效率的目的。

[1] 劉越甲.車聯(lián)網(wǎng)路口場景下分簇算法的研究[D].北京:北京交通大學(xué),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] 胡曉禹.基于能量均衡的分簇路由協(xié)議研究[D].太原:太原科技大學(xué),2013:1-3.

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

[7] 吳迪，李晴，馮永新，等.一種基于地理定位信息的Ad Hoc分簇算法[J].計算機(jī)工程與應(yīng)用，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] 龔本燦.一種能量均衡的無線傳感器網(wǎng)絡(luò)分簇算法[J].計算機(jī)應(yīng)用研究,2008(11):3424-3429.

(責(zé)任編輯：熊文濤)

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)；阿壩師范學(xué)院重點課題 (ASA12-23)

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

TP393

A

2095-4824(2016)06-0062-04