張凈霞 陳俊杰

(東南大學儀器科學與工程學院, 南京 210096)

一種基于融合器的多跳能量均衡算法

張凈霞 陳俊杰

(東南大學儀器科學與工程學院, 南京 210096)

為了解決現(xiàn)有的分簇算法能量消耗不均衡問題,提出了一種新的基于融合器的多跳能量均衡 (MEB) 算法．該算法采用定時器并且考慮節(jié)點的剩余能量來優(yōu)化簇頭選舉,通過選舉簇中最多能量的節(jié)點作為融合器,對簇頭轉(zhuǎn)發(fā)的傳感數(shù)據(jù)進行數(shù)據(jù)融合,然后通過由融合器構(gòu)建的多跳路由樹發(fā)送到基站．該算法同時達到了簇內(nèi)和簇間的能量均衡．仿真結(jié)果表明,MEB算法第1個節(jié)點死亡的時間比LEACH算法延長了80%左右,比TB-LEACH算法延長了60%左右．MEB算法第1個節(jié)點死亡到最后1個節(jié)點死亡經(jīng)歷的時間非常短．因此,MEB算法實現(xiàn)了整個網(wǎng)絡(luò)的能量均衡,提高了網(wǎng)絡(luò)的穩(wěn)定度,延長了網(wǎng)絡(luò)的生命周期．

無線傳感器網(wǎng)絡(luò);能量均衡;融合器;多跳

在無線傳感器網(wǎng)絡(luò)中,傳感節(jié)點的能量有限,因此需要仔細地對應(yīng)用和協(xié)議進行設(shè)計,通過優(yōu)化能量消耗來延長網(wǎng)絡(luò)的生命周期[1]．分簇算法是一種設(shè)計無線傳感器網(wǎng)絡(luò)中各種能量高效的協(xié)議．LEACH(low-energy adaptive clustering hierarchy)算法是分簇算法中最廣泛使用的算法[2]．LEACH算法通過將傳感器網(wǎng)絡(luò)劃分成若干個簇,由簇頭負責簇內(nèi)數(shù)據(jù)的融合和轉(zhuǎn)發(fā),所以LEACH算法能夠優(yōu)化網(wǎng)絡(luò)的能量消耗來延長網(wǎng)絡(luò)的生命周期．由于簇頭在傳感器節(jié)點中間隨機輪轉(zhuǎn),簇頭比普通傳感節(jié)點能量消耗要多,因此會造成節(jié)點過早死亡．HEED(hybrid energy-efficient distributed clustering)協(xié)議是一種分布式分簇算法[3],該算法根據(jù)節(jié)點的剩余能量和節(jié)點等級來選擇簇頭．HEED算法是用來設(shè)計需要延長網(wǎng)絡(luò)生命周期、規(guī)模擴展、容錯和負載均衡的傳感器網(wǎng)絡(luò)協(xié)議．

文獻[4]通過簇頭重構(gòu)來實現(xiàn)負載均衡,簇頭重構(gòu)就是本輪簇頭按照一定的規(guī)則產(chǎn)生下一輪簇頭來實現(xiàn)簇頭在輪間的遷移,從而使得簇頭均勻地分布在網(wǎng)絡(luò)中,延長了網(wǎng)絡(luò)的生命周期．文獻[5]提出了DSBCA(balanced clustering algorithm with distributed self-organization)算法,該算法通過考慮節(jié)點連通密度和位置形成能量均衡簇,但需要利用RSSI(received signal strength indicator)計算節(jié)點與基站間的距離．文獻[6]提出了CATD(clustering algorithm based on time delay)算法,該算法通過定時器的時間延遲使得簇頭數(shù)量優(yōu)化和在網(wǎng)絡(luò)中均勻分布,通過多跳機制構(gòu)成了一個路由樹轉(zhuǎn)發(fā)數(shù)據(jù),該算法節(jié)省了網(wǎng)絡(luò)能量，均衡了網(wǎng)絡(luò)負載,延長了網(wǎng)絡(luò)的生命周期．文獻[7]提出了OLBHC(optimal load balancing hierarchical clustering)路由協(xié)議,OLBHC能夠用均衡方法降低能量消耗,利用標記矩陣儲存鄰居節(jié)點的連接狀態(tài),然后應(yīng)用優(yōu)化算法選擇網(wǎng)絡(luò)中最優(yōu)簇，該算法延長了節(jié)點的平均能量周期．文獻[4-7]利用簇頭均勻分布,通過構(gòu)建均衡簇和多跳方式實現(xiàn)負載均衡．

文獻[8]提出了TB-LEACH(time-based cluster-head selection algorithm for LEACH)算法,該算法利用定時器發(fā)送廣播信息來競爭簇頭,通過優(yōu)化簇頭數(shù)量來實現(xiàn)簇間能量均衡,但是TB-LEACH競選簇頭時沒有考慮節(jié)點的剩余能量．文獻[9]提出了LEACH-B(LEACH-balanced)算法,該算法通過2次選擇簇頭來優(yōu)化簇頭數(shù)量,平衡了系統(tǒng)能量消耗,延長了網(wǎng)絡(luò)生命周期．文獻[8-9]通過簇頭數(shù)量優(yōu)化來實現(xiàn)能量均衡,延長了網(wǎng)絡(luò)的生命周期．文獻[10]提出了IBLEACH(intra-balanced LEACH)協(xié)議,該協(xié)議考慮幀間的能量均衡,通過分配簇頭的負載到簇內(nèi)的普通節(jié)點,延長了整個網(wǎng)絡(luò)的生命周期．

上述的分簇算法中,數(shù)據(jù)融合都是在簇頭進行,數(shù)據(jù)傳輸都是基于單跳或者構(gòu)建了基于簇頭之間的多跳路由樹,這使得網(wǎng)絡(luò)中所有節(jié)點之間的能量消耗并不均衡．為了實現(xiàn)網(wǎng)絡(luò)所有節(jié)點之間的能量消耗均衡,同時克服TB-LEACH選擇簇頭時不考慮剩余能量的缺陷,本文提出了一種新的實現(xiàn)能量均衡的多跳能量均衡(MEB)算法．MEB算法基于TB-LEACH算法選舉簇頭,同時考慮了節(jié)點的剩余能量．為了降低簇頭的負擔,選舉簇中能量最多的節(jié)點作為融合器進行數(shù)據(jù)融合．最后,構(gòu)建基于融合器的多跳路由樹,將采集的數(shù)據(jù)傳輸?shù)交荆?/p>

1 無線電能量模型

為了分析MEB算法的能量消耗,本文采用與LEACH算法相同的無線電能量模型．假設(shè)節(jié)點傳輸l個比特信息,發(fā)射器和接收器通信距離為d,所消耗的能量為

(1)

ERx(l)=lEelec

(2)

節(jié)點對l個比特的數(shù)據(jù)進行融合,所消耗的能量為

EDA(l)=lEDA

(3)

式中,EDA為每個比特的數(shù)據(jù)融合所消耗的能量．

從無線傳感器網(wǎng)絡(luò)的節(jié)點感知、處理和數(shù)據(jù)通信3方面來看,節(jié)點消耗的能量主要集中在數(shù)據(jù)通信上,而發(fā)送信號消耗了通信的大部分能量．發(fā)送信號所消耗的能量與節(jié)點之間的距離d有很大的關(guān)系,當d≤d0時,節(jié)點功率放大器采用自由空間模型,節(jié)點消耗的能量較少．當d>d0時,節(jié)點功率放大器采用多徑路徑模型,節(jié)點消耗的能量較多．

2 MEB算法

MEB算法的執(zhí)行過程由輪組成,每輪分為簇建立階段和穩(wěn)定階段，與LEACH,TB-LEACH算法的簇建立階段類似,MEB算法的簇建立階段將網(wǎng)絡(luò)中的節(jié)點劃分為若干個簇,每個簇的節(jié)點選舉出自己的簇頭．MEB算法對TB-LEACH算法簇頭選舉的函數(shù)進行了優(yōu)化．在簇穩(wěn)定階段,非簇頭節(jié)點按照簇頭發(fā)送給自己的TDMA調(diào)度,在自己的時間片內(nèi)發(fā)送數(shù)據(jù)給簇頭．簇頭接收的數(shù)據(jù)經(jīng)過處理(數(shù)據(jù)融合),發(fā)送數(shù)據(jù)給基站．MEB算法在簇穩(wěn)定階段與LEACH,TB-LEACH算法有2點不同:①MEB算法增加了數(shù)據(jù)融合節(jié)點(融合器)的選擇,融合器是指包括簇頭在內(nèi)的剩余能量最多的簇內(nèi)節(jié)點;②LEACH,TB-LEACH算法是單跳傳輸,簇頭直接發(fā)送數(shù)據(jù)給基站,而MEB算法是多跳傳輸,構(gòu)建了基于融合器的多跳路由樹．

2.1 簇頭的優(yōu)化選擇

在LEACH算法中,簇頭的選擇基于閾值與一個隨機數(shù)的比較．TB-LEACH算法為了優(yōu)化簇頭數(shù)量,選擇簇頭時不再基于閾值,而是基于一個時間延遲的定時器．每個節(jié)點都利用定時器發(fā)送廣播信息來競爭簇頭,發(fā)送廣播信息的時間間隔是由定時器隨機產(chǎn)生．由于定時器的時間短,因而具有最小隨機數(shù)的節(jié)點成為簇頭的概率較大．TB-LEACH算法定時器產(chǎn)生隨機數(shù)的公式為

Tt=rand(0,1)

(4)

根據(jù)文獻[2]的證明,簇的數(shù)量太多或者太少,每輪消耗的平均能量都較大,因此簇頭數(shù)有一個優(yōu)化值kopt．在TB-LEACH算法中,當競爭簇頭的個數(shù)k>kopt時,所有的定時器停止,節(jié)點不再競爭簇頭．

由式(4)可知,TB-LEACH算法選擇簇頭是隨機的,不考慮節(jié)點的當前能量,這樣能量少的節(jié)點可能頻繁地成為簇頭而導致能量耗盡死亡．在一些節(jié)點死亡后,系統(tǒng)變得不穩(wěn)定,可靠性降低．因此簇頭的選擇需要考慮節(jié)點的剩余能量,這樣簇頭選擇在能量較多的節(jié)點之間輪轉(zhuǎn),使得同一時刻節(jié)點的能量差異減小,使節(jié)點的能量負載均衡,節(jié)點能夠在理想情況下同時死亡,提高了系統(tǒng)的可靠性．因此MEB算法對TB-LEACH算法的簇頭選舉方法進行了改進,使定時器產(chǎn)生的隨機數(shù)包含節(jié)點的剩余能量信息,節(jié)點剩余能量越多，定時器產(chǎn)生的隨機數(shù)越小,成為簇頭的概率越大,則式(4)改進為

(5)

式中,α為時間調(diào)節(jié)因子;R為節(jié)點的剩余能量;I為節(jié)點的初始能量;rand(0,β)為最佳簇頭調(diào)節(jié)因子．rand(0,β)在產(chǎn)生的隨機數(shù)相同時,調(diào)節(jié)簇頭的個數(shù)．本算法中α=1,β=0.000 01．同樣地,在MEB算法中當競爭簇頭的個數(shù)k>kopt時,所有的定時器停止,節(jié)點不再競爭簇頭．

2.2 融合器的選擇

融合器的選擇是在非簇頭節(jié)點發(fā)送數(shù)據(jù)給簇頭節(jié)點階段進行的．非簇頭節(jié)點在TDMA調(diào)度分配給自己的時隙時,發(fā)送采集數(shù)據(jù)和剩余能量信息給簇頭,簇頭比較自己和所有成員節(jié)點的剩余能量信息,選舉出能量最多的節(jié)點作為融合器．如果簇頭的剩余能量比所有成員節(jié)點的剩余能量多,那么簇頭自身作為融合器．如果選擇簇頭節(jié)點作為融合器,那么MEB算法融合器選擇方法與LEACH,TB-LEACH算法相同．如果選擇非簇頭節(jié)點作為融合器,那么在LEACH 和TB-LEACH算法中,數(shù)據(jù)穩(wěn)定階段簇頭的能量消耗為

(6)

式中,N為網(wǎng)絡(luò)中所有節(jié)點數(shù)量;dtoBS為從簇頭到基站的距離．

在LEACH,TB-LEACH和MEB算法中,沒有競選成為融合器的普通非簇頭節(jié)點的能量消耗為

(7)

式中,dtoCH為非簇頭節(jié)點到簇頭節(jié)點之間的距離.假設(shè)基站離傳感器網(wǎng)絡(luò)較遠,那么dtoBS>dtoCH,進而推導出ECH>Enon-CH．消耗在簇頭的能量比消耗在非簇頭的能量大得多,因此,為了均衡網(wǎng)絡(luò)負載,需要降低簇頭的能量消耗．

在MEB算法中,數(shù)據(jù)穩(wěn)定階段簇頭的能量消耗為

(8)

在MEB算法中,融合器的能量消耗為

(9)

顯然有EDA>Enon-CH,融合器比普通非簇頭節(jié)點消耗的能量多,因為它承擔了數(shù)據(jù)融合和中轉(zhuǎn)的作用,融合器分擔了簇頭的能量消耗,均衡了網(wǎng)絡(luò)負載．

2.3 基于融合器的多跳路由樹

多跳傳輸是實現(xiàn)網(wǎng)絡(luò)能量均衡的一種重要方法,融合器直接將數(shù)據(jù)轉(zhuǎn)發(fā)給基站會消耗自身較多的能量,因此融合器選擇基站方向距離自己最近的融合器作為下一跳節(jié)點,而離基站最近的融合器直接將數(shù)據(jù)傳送給基站．多跳傳輸將長距離傳輸分為短距離各個分段傳輸,每次數(shù)據(jù)轉(zhuǎn)發(fā)都是短距離傳輸,結(jié)合第1節(jié)的無線電能量模型,節(jié)點采用的是自由空間模型,而接收信息所耗費的能量較少,所以多跳傳輸可以減少能量消耗,同時均勻地消耗網(wǎng)絡(luò)能量．

多跳傳輸路由樹的構(gòu)建如圖1所示．由圖中可以看出，本文算法將基于簇的拓撲和基于樹的拓撲相結(jié)合,從而構(gòu)建了數(shù)據(jù)傳輸?shù)淖罴逊桨福?/p>

圖1 多跳融合器路由樹的構(gòu)建

3 仿真結(jié)果及分析

為了評估算法的性能,采用軟件OPNET14.5仿真了MEB,LEACH和TB-LEACH算法．網(wǎng)絡(luò)規(guī)模為100 m×100 m,基站的位置為(50,175),100個節(jié)點在網(wǎng)絡(luò)中隨機分布,如圖2所示．普通節(jié)點的初始能量為0.5 J,基站的能量不受限．其他參數(shù)的設(shè)置如表1所示．

圖2 100個節(jié)點的隨機網(wǎng)絡(luò)

參數(shù)參數(shù)值MAC協(xié)議IEEE802．11DCF協(xié)議發(fā)射功率/W0．005信道模型(d≤d0)自由空間模型信道模型(d>d0)多徑模型數(shù)據(jù)包大小/bit4000控制包大小/bit200最優(yōu)簇數(shù)量kopt5運行無線電路耗能Eelec/(nJ·bit-1)50自由空間路徑εfs/(pJ·bit-1·m-2)10多徑路徑εmp/(pJ·bit-1·m-4)0．0013每個信號的融合耗能EDA/(nJ·bit-1)5距離閾值d0/m87

能量效率是對傳感器網(wǎng)絡(luò)的重要度量,主要通過網(wǎng)絡(luò)能量消耗的均勻性和網(wǎng)絡(luò)的生命周期來表示．通常把第1個節(jié)點死亡時間作為網(wǎng)絡(luò)生命周期最重要的衡量指標．

圖3為分布在網(wǎng)絡(luò)區(qū)域內(nèi)的節(jié)點死亡時間三維趨勢圖,反映了網(wǎng)絡(luò)內(nèi)節(jié)點的負載均衡程度．x,y軸所決定區(qū)域的節(jié)點按圖2隨機分布,z軸反映了節(jié)點的死亡時間．節(jié)點死亡時間越接近,所有節(jié)點死亡時間的偏差越小,則網(wǎng)絡(luò)內(nèi)節(jié)點的能量消耗越均勻,負載均衡程度越好．圖3中曲面表面變化趨勢較小,則較為平坦．

圖3(a)為LEACH算法的所有節(jié)點死亡時間三維分布趨勢圖．從圖中可以看出,第1個節(jié)點死亡時間大約為800輪,遠離基站的節(jié)點比靠近基站的節(jié)點死亡早.由于簇頭節(jié)點選擇的隨機性和單跳傳輸?shù)脑?LEACH算法節(jié)點死亡的先后次序波動非常大,趨勢較為陡峭,整個網(wǎng)絡(luò)節(jié)點能量消耗極為不平衡．

圖3(b)為TB-LEACH算法所有節(jié)點死亡時間三維分布趨勢圖．與LEACH算法相比,TB-LEACH算法的簇頭數(shù)量已經(jīng)優(yōu)化,網(wǎng)絡(luò)能量均衡程度有了很大的提高,節(jié)點死亡的先后次序較為平緩,同時第1個節(jié)點死亡延長了100輪左右．與LEACH算法相似的是,遠離基站的節(jié)點比離基站近的節(jié)點死亡早．

(a) LEACH算法

(b) TB-LEACH算法

(c) MEB算法

圖3(c)是MEB算法的所有節(jié)點死亡時間的三維分布趨勢圖．從圖中看出,與前2種算法相比,節(jié)點的死亡次序在小范圍內(nèi)波動,非常平緩,這反映了本算法的網(wǎng)絡(luò)負載均衡程度非常好．第1個節(jié)點在1 460輪左右死亡,網(wǎng)絡(luò)的穩(wěn)定程度較前2種算法提高了很多．

圖4比較了3種算法的網(wǎng)絡(luò)生命周期．從圖中可以看出,MEB算法第1個節(jié)點的死亡時間比LEACH 算法延長了80%左右,比TB-LEACH算法延長了60%左右．MEB算法中50%節(jié)點的死亡時間比LEACH算法延長了40%左右,比TB-LEACH算法延長了35%左右．從圖中也可以看出,MEB算法第1個節(jié)點死亡到最后1個節(jié)點死亡經(jīng)歷的時間非常短,網(wǎng)絡(luò)能量消耗很均勻．

圖4 系統(tǒng)的網(wǎng)絡(luò)生命周期

采用MEB算法能夠使得能量消耗較為均衡,是因為基于節(jié)點剩余能量的簇頭選擇使得能量多的節(jié)點有更高的概率成為簇頭．能量較少的節(jié)點成為非簇頭節(jié)點,消耗的能量少,延遲了能量少節(jié)點的死亡時間．融合器的選擇降低了簇頭的能量，簇頭不會很快死亡．另外,多跳路由使得簇頭與簇頭、簇頭與基站之間的通信采用自由空間模型,使得離基站較遠的簇頭的能量消耗降低．而LEACH,TB-LEACH算法采用單跳路由,離基站較近的節(jié)點死亡比較早,因為這些遠離基站的節(jié)點擔當簇頭的過程中采用了多徑模型,節(jié)點能量衰減較快,而離基站較近的節(jié)點擔當簇頭的過程中采用的是自由空間模型,能量消耗較少,節(jié)點最后死亡．

4 結(jié)語

本文提出了一種基于融合器的多跳能量均衡MEB算法．該算法通過優(yōu)化簇頭選舉和基于融合器的多跳傳輸?shù)臋C制,最終實現(xiàn)了網(wǎng)絡(luò)內(nèi)的能量均衡．仿真結(jié)果表明,與LEACH和TB-LEACH算法相比,MEB算法均衡了網(wǎng)絡(luò)節(jié)點的能量消耗,延長了網(wǎng)絡(luò)的生命周期．所以,在網(wǎng)絡(luò)穩(wěn)定度要求較高的場合,MEB算法具有較高的應(yīng)用價值．本文假設(shè)節(jié)點初始能量相同,研究的是同構(gòu)網(wǎng)絡(luò)的能量高效問題．如何實現(xiàn)異構(gòu)網(wǎng)絡(luò)的能量高效和動態(tài)重構(gòu)性是下一步的工作．

References)

[1]Tyagi S, Kumar N. A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks [J].JournalofNetworkandComputerApplications, 2013, 36(2): 623-645. DOI:10.1016/j.jnca.2012.12.001.

[2]Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks [J].IEEETransactionsonWirelessCommunications, 2002, 1(4): 660-670. DOI:10.1109/twc.2002.804190.

[3]Younis O, Fahmy S. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks [J].IEEETransactionsonMobileComputing, 2004, 3(4):366-379. DOI:10.1109/tmc.2004.41.[4]Kim N, Heo J, Kim H S, et al. Reconfiguration of clusterheads for load balancing in wireless sensor networks [J].ComputerCommunications, 2008, 31(1): 153-159. DOI:10.1016/j.comcom.2007.10.039.

[5]Liao Y, Qi H, Li W. Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks [J].IEEESensorsJournal, 2013, 13(5): 1498-1506. DOI:10.1109/jsen.2012.2227704.

[6]Shang F. A multi-hop routing algorithm based on integrated metrics for wireless sensor networks [J].AppliedMathematics&InformationSciences, 2013, 7(3): 1021-1034. DOI:10.12785/amis/070321.

[7]Wang T S, Zhang G X,Yang X C, et al. Hierarchical clustering routing protocol based on optimal load balancing in wireless sensor networks [J].LectureNotesinComputerScience, 2013, 8299:227-240. DOI:10.1007/978-3-642-45293-2_17.

[8]Hu J, Jin Y, Dou L. A time-based cluster-head selection algorithm for LEACH[C]//IEEESymposiumonComputersandCommunications. Marrakech, Morocco,2008:1172-1176.

[9]Tong M, Tang M. LEACH-B: An improved LEACH protocol for wireless sensor network[C]//6thInternationalConferenceonWirelessCommunicationsNetworkingandMobileComputing. Chengdu, China, 2010:1-4.

[10]Salim A, Osamy W, Khedr A M. IBLEACH: Intra-balanced LEACH protocol for wireless sensor networks [J].WirelessNetworks, 2014, 20(6):1515-1525. DOI:10.1007/s11276-014-0691-4.

A multi-hop energy balancing algorithm based on aggregator

Zhang Jingxia Chen Junjie

(School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China)

To resolve the energy unbalancing problem in the current clustering algorithms, a new multi-hop energy balancing (MEB) algorithm based on the aggregator is proposed. The proposed algorithm utilized timers and considered node residual energy to optimize the cluster head selection. It selects the maximum residual energy node from the intra-cluster nodes as the aggregator, fuses data from the sensing data that cluster heads relay and then forwards data to the sink through the multi-hop routing tree constructed by the aggregators. The algorithm simultaneously realized intra-cluster and inter-cluster energy balancing. The simulation results show that the MEB algorithm can enhance first node dies (FND) by about 80% compared with the low-energy adaptive clustering hierarchy (LEACH) algorithm and by about 60% compared with the time-based cluster-head selection algorithm for LEACH (TB-LEACH). The MEB algorithm costs very short time from the death of the first node until the death of the last node. Therefore, the MEB algorithm achieves energy balancing for the entire network, improves the network stability, and prolongs the network lifetime.

wireless sensor networks; energy balancing; aggregator; multi-hop

第47卷第1期2017年1月 東南大學學報(自然科學版)JOURNALOFSOUTHEASTUNIVERSITY(NaturalScienceEdition) Vol．47No．1Jan．2017DOI：10．3969/j．issn．1001-0505．2017．01．011

2016-06-07. 作者簡介:張凈霞(1984—),女,博士生;陳俊杰(聯(lián)系人),男,博士,教授,博士生導師,inschenjj@seu.edu.cn.

“十二五”國家科技支撐計劃資助項目(2014BAD08B03)、江蘇省水產(chǎn)三新工程資助項目(Y2016-3)、蘇北科技專項資金資助項目(BN2014085)、江蘇省農(nóng)業(yè)科技支撐資助項目(BN2014312).

張凈霞,陳俊杰.一種基于融合器的多跳能量均衡算法[J].東南大學學報(自然科學版),2017,47(1):56-60.

10.3969/j.issn.1001-0505.2017.01.011.

TP393

A

1001-0505(2017)01-0056-05