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

黃成兵

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

?

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

黃成兵

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

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

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

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

1 常見(jiàn)分簇算法及不足

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

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

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

3 基本描述

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

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

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

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

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

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

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

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

5 具體算法

5.1 初始化階段

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

表1 普通節(jié)點(diǎn)向匯聚節(jié)點(diǎn)報(bào)告報(bào)文格式

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

(1)

(2)

5.2 簇首選舉

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

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

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

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

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

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

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

6 總結(jié)

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

[1] 劉越甲.車(chē)聯(lián)網(wǎng)路口場(chǎ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ú)線傳感器網(wǎng)絡(luò)中一種能量均衡的分簇策略[J].計(jì)算機(jī)應(yīng)用研究,2009.4:1494-1496.

[7] 吳迪，李晴，馮永新，等.一種基于地理定位信息的Ad Hoc分簇算法[J].計(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ú)線傳感器網(wǎng)絡(luò)分簇算法[J].計(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

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

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

TP393

A

2095-4824(2016)06-0062-04