江禹生，李 萍，馬 超

（重慶大學(xué)通信工程學(xué)院，重慶市 400030）

0 引言

無線傳感器網(wǎng)絡(luò)低功耗、低成本、自組織與分布式等特點使其成為信息獲取的重要技術(shù)，然而資源受限使得對無線傳感器網(wǎng)絡(luò)的應(yīng)用面臨著巨大的挑戰(zhàn)。減少能量消耗，延長網(wǎng)絡(luò)生命周期是無線傳感器網(wǎng)絡(luò)領(lǐng)域的重要研究方向。拓撲控制作為無線傳感器網(wǎng)絡(luò)中減少能量消耗、延長網(wǎng)絡(luò)生命周期的重要技術(shù)［1］，近年來成為了無線傳感器網(wǎng)絡(luò)領(lǐng)域研究的熱點與難點之一。

現(xiàn)有的拓撲控制算法主要集中于節(jié)點功率控制和分簇的層次型拓撲控制2個方面，本論文主要針對分簇的層次型拓撲控制算法進行深入研究。LEACH（low-energy adaptive clustering hierarchy）［2］是比較經(jīng)典的層次型拓撲算法，其他的算法:HEED（hybrid energy-efficient distributed）［3］，DEEUC（distributed energy-efficient unequal clus-tering）［4］等，幾乎都是在LEACH算法基礎(chǔ)上做的改進。

由于LEACH是隨機等概率的選擇簇頭，沒有考慮節(jié)點的剩余能量，簇頭數(shù)量和質(zhì)量都得不到保證。針對簇頭能耗過大的問題，Yassein M B等人在文獻［5］中提出了VLEACH（vice-LEACH）算法，該算法簇頭的選擇過程中設(shè)置了候選簇頭以均衡全網(wǎng)的能量消耗，但該算法未考慮全網(wǎng)的能量分布情況;在文獻［6］中，王偉超等人提出了LEACH-H算法，該算法在簇頭選擇過程中考慮了能量因素，但其涉及到鄰居節(jié)點ID、鄰居節(jié)點剩余能量、被選作為簇頭的次數(shù)、是否是鄰居節(jié)點4個數(shù)據(jù)項，增加了節(jié)點間的通信量，因而增加了能量的消耗;在文獻［7］中，周治平等人提出了EB-LEACH（energy balance LEACH）算法，該算法在簇頭的選擇過程中增加了能量閾值這一約束條件，但該算法只能平衡簇頭地區(qū)的能量分布，缺乏對全網(wǎng)能量消耗的平衡;通過對網(wǎng)絡(luò)中最佳簇頭數(shù)目的考慮，Thein M C M等人在文獻［8］中提出了能量有效的簇頭選擇算法，但該算法忽略了穩(wěn)定階段的能量消耗。

本文在LEACH分簇算法的基礎(chǔ)上結(jié)合EB-LEACH的一些優(yōu)秀思想，分別從建立階段和穩(wěn)定階段進行改進，提出了一種能量高效的拓撲控制算法（energy efficient topology control algorithm，EETCA）。其基本思想是:在簇頭的選舉中，考慮節(jié)點的剩余能量，保證每輪選舉最佳節(jié)點當選簇頭;簇的形成綜合考慮了簇的規(guī)模，防止簇頭節(jié)點因為簇的規(guī)模過大而過早死亡;數(shù)據(jù)穩(wěn)定傳輸階段，簇頭與Sink節(jié)點間的通信采用多跳路由方式，平衡網(wǎng)絡(luò)負載。

1 相關(guān)理論

1.1 能耗模型

通常傳感器節(jié)點的能量消耗模型采用文獻［2］中提出的無線電能量消耗模型，如圖1所示。

圖1 無線電能量消耗模型Fig 1 Radio energy dissipation model

在該模型中，傳感器節(jié)點發(fā)送kbit的數(shù)據(jù)包到距離為d的另一個傳感器節(jié)點，所消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，用ETx（k，d）表示

節(jié)點接收kbit數(shù)據(jù)包消耗的能量用ERx（k）為接收數(shù)據(jù)主要是電路能量消耗，具體見式（2）所示

1.2 最優(yōu)簇數(shù)目

在EATC算法中，簇頭與Sink節(jié)點的通信采用多跳方式，結(jié)合文獻［2］中對LEACH算法最優(yōu)簇數(shù)目的推導(dǎo)，可以對最優(yōu)簇數(shù)目的計算公式進行調(diào)整。

則整個網(wǎng)絡(luò)的能量消耗Etotal為

其中，EDA為簇頭進行數(shù)據(jù)融合所消耗的能量，dCH-to-CH為簇頭與相鄰其他簇頭之間的平均距離。

對式（5）求導(dǎo)并令導(dǎo)數(shù)等于0，可得出改進的最優(yōu)簇的數(shù)目mopt，計算如式（6）所示

1.3 多跳通信

大量研究表明，當網(wǎng)絡(luò)規(guī)模較大時，簇頭與Sink節(jié)點的通信采用多跳方式可以顯著降低能量消耗［9］。

對于節(jié)點多跳通信，如圖2所示，數(shù)據(jù)在線性網(wǎng)絡(luò)鏈路上轉(zhuǎn)發(fā)。其中相鄰2個傳感器節(jié)點間的平均距離為d，最后一個節(jié)點B到匯聚節(jié)點的距離也為d。假設(shè)節(jié)點A發(fā)送一個kbit的數(shù)據(jù)包，數(shù)據(jù)包數(shù)據(jù)經(jīng)過n跳傳輸?shù)竭_匯聚節(jié)點，所消耗的能量為

式（7）對n求導(dǎo)，并令導(dǎo)數(shù)為0，可以求出簇頭發(fā)送信息到基站的最優(yōu)跳數(shù)nopt。

圖2 多跳轉(zhuǎn)發(fā)網(wǎng)絡(luò)模型Fig 2 Multi-hop transmit network model

2 EETCA實現(xiàn)策略

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

為了便于控制策略的描述和分析，先做如下假設(shè):

1）監(jiān)測區(qū)域為規(guī)則正方形，基站在監(jiān)測區(qū)域的中心位置，能量沒有限制;

2）節(jié)點均勻分布在監(jiān)測區(qū)域中，所有節(jié)點都知道自己的位置信息，節(jié)點位置固定不動;

3）每個節(jié)點具有相同的初始能量，且能夠獲得自身的剩余能量，都可以與基站直接通信;

4）鏈路是對稱的，可以根據(jù)源節(jié)點的發(fā)射功率和接收信號的RSSI估計到源節(jié)點的距離;

5）忽略真實環(huán)境中存在障礙物等影響通信質(zhì)量的因素，所有節(jié)點的數(shù)據(jù)包都能夠進行可靠傳輸。

2.2 EETCA 設(shè)計思路

2.2.1 簇頭選擇階段

在此過程中，各節(jié)點首先選取一個［0，1］之間的隨機數(shù)，如果節(jié)點n產(chǎn)生的隨機數(shù)小于閾值T（n），則將節(jié)點n選為候選簇頭。然后繼續(xù)計算此時候選節(jié)點的剩余能量，并與能量閾值Eth進行比較，當節(jié)點的剩余能量大于該輪的能量閾值Eth時，則該節(jié)點當選為簇頭，然后簇頭節(jié)點向網(wǎng)絡(luò)中發(fā)送廣播信息［9］。其中T（n）的計算公式為

其中，p為節(jié)點當選簇頭的概率;r為選舉輪數(shù);G為最近1/p輪中還未當選過簇頭的節(jié)點集合。

第r輪節(jié)點的能量閾值Eth的計算公式為

其中，L為網(wǎng)絡(luò)預(yù)計要運行的輪數(shù)，E0為節(jié)點的初始能量。

通過引入能量閾值，有效地防止了低能量的節(jié)點成為簇頭，避免了因為簇頭死亡造成的數(shù)據(jù)丟失和網(wǎng)絡(luò)空洞，使網(wǎng)絡(luò)能量得到均衡的利用，顯著地延長網(wǎng)絡(luò)的壽命。

2.2.2 簇的建立階段

離Sink節(jié)點近的簇頭承擔(dān)了轉(zhuǎn)發(fā)其他簇頭數(shù)據(jù)信息的任務(wù)，其能量消耗比離Sink節(jié)點遠的簇頭大，為了保證各簇頭節(jié)點的能量消耗達到均衡，離Sink節(jié)點近的簇的規(guī)模應(yīng)適當?shù)臏p?。?］。

假定簇頭節(jié)點都以一定的功率進行通信，其傳輸半徑為R，非簇頭節(jié)點根據(jù)式（10）加入相應(yīng)的簇

其中，dj-to-CHi為節(jié)點j到簇頭i的距離，di-t--Sink為簇頭i到Sink節(jié)點間的距離，NCHi為簇頭i的一跳鄰居數(shù)，γ為權(quán)重。

節(jié)點在入簇過程中，綜合考慮了簇頭的鄰居數(shù)與傳感器節(jié)點到簇頭的距離，防止某個簇的規(guī)模過于龐大，均衡簇頭能量消耗。當所有傳感器節(jié)點都已成簇之后，簇頭節(jié)點為簇內(nèi)節(jié)點分配通信時隙和進行簇內(nèi)通信的直接序列擴頻碼，然后進入穩(wěn)定數(shù)據(jù)傳輸階段。

2.2.3 穩(wěn)定數(shù)據(jù)傳輸

基站根據(jù)網(wǎng)絡(luò)規(guī)模使用式（7）算得最優(yōu)跳數(shù)nopt。簇內(nèi)節(jié)點以單跳方式把數(shù)據(jù)發(fā)送到簇頭，簇頭進行數(shù)據(jù)融合，然后查詢路由表，若Sink節(jié)點在其通信范圍之內(nèi)，則直接將數(shù)據(jù)信息發(fā)送給Sink節(jié)點;若不在，則根據(jù)最優(yōu)跳數(shù)選擇轉(zhuǎn)發(fā)代價Etotal最小的簇頭作為下一跳，間接將數(shù)據(jù)傳送到Sink節(jié)點。

3 仿真實驗與結(jié)果分析

本文采用Matlab建立了網(wǎng)絡(luò)仿真模型，對EETCA進行仿真分析，并從網(wǎng)絡(luò)整體剩余能量、存活節(jié)點數(shù)等方面與LEACH，EB-LEACH算法進行比較。

3.1 仿真模型與參數(shù)設(shè)置

100個傳感器節(jié)點隨機分布在100 m×100 m的監(jiān)測區(qū)域內(nèi)，Sink節(jié)點部署在坐標為（50，50 m）的點上，如圖3。

圖3 網(wǎng)絡(luò)中隨機分布100個節(jié)點的示意圖Fig 3 Schematic diagram of 100 sensor nodes are scattered randomly in networks

實驗的其他參數(shù)如表1所示。

表1 實驗參數(shù)Tab 1 Experimental parameters

3.2 結(jié)果分析

3.2.1 最優(yōu)跳數(shù)

圖4是當跳數(shù)n取不同值時，一個數(shù)據(jù)包經(jīng)過網(wǎng)絡(luò)傳輸?shù)竭_基站時所消耗的能量關(guān)系圖。從圖中可以看出:當n從1變化到2時，能量急劇下降，這主要是因為n=1時節(jié)點無線通信模塊的能耗與通信距離的四次方成正比;n=2時，網(wǎng)絡(luò)能耗達到最小值。隨著n的增大，增加了網(wǎng)絡(luò)對數(shù)據(jù)的轉(zhuǎn)發(fā)，網(wǎng)絡(luò)能耗也隨之增加。

圖4 能量消耗與傳輸跳數(shù)關(guān)系圖Fig 4 Transmission hop number vs energy dissipation

3.2.2 網(wǎng)絡(luò)剩余能量

圖5是網(wǎng)絡(luò)整體剩余能量隨網(wǎng)絡(luò)運行輪數(shù)的變化曲線。從圖中可以看出:本文提出的EETCA每輪剩余的總能量最多，其次是EB-LEACH算法，最差的是LEACH算法。主要因為EETCA中簇頭的選舉、簇的形成以及數(shù)據(jù)的傳輸方式更加合理，減少了節(jié)點的能量消耗，使網(wǎng)絡(luò)每輪的剩余能量隨之增加。

圖5 網(wǎng)絡(luò)整體剩余能量與網(wǎng)絡(luò)運行輪數(shù)關(guān)系圖Fig 5 Network running number of sheaves vs overall residual energy of network

圖6是3種算法節(jié)點剩余能量的標準差隨網(wǎng)絡(luò)運行輪數(shù)變化的曲線圖。EETCA的節(jié)點剩余能量標準差比LEACH算法和EB-LEACH算法的都小，且隨著輪數(shù)的增加有明顯的下降趨勢。其根本原因在于，EETCA在均衡簇頭節(jié)點和普通節(jié)點能耗的同時，還通過減小離Sink節(jié)點近的簇的規(guī)模均衡了簇頭之間的能耗，使網(wǎng)絡(luò)總體能量消耗更加均衡。

圖6 節(jié)點剩余能量標準差與網(wǎng)絡(luò)運行輪數(shù)關(guān)系圖Fig 6 Network running number of sheaves vs standard deviation of residual energy of node

3.2.3 網(wǎng)絡(luò)生命周期

圖7是隨著網(wǎng)絡(luò)運行輪數(shù)的推移，在相同的環(huán)境條件下，3種算法的存活節(jié)點個數(shù)與網(wǎng)絡(luò)運行輪數(shù)關(guān)系圖。由于EETCA與EB-LEACH算法在簇頭選擇階段都充分考慮了節(jié)點的剩余能量，因此，在同樣規(guī)模的環(huán)境下網(wǎng)絡(luò)生命周期明顯較LEACH算法長。又由于EETCA在簇的形成時考慮了簇的規(guī)模，在穩(wěn)定數(shù)據(jù)傳輸階段采用單、多跳相結(jié)合的方式傳輸數(shù)據(jù)，所以，EETCA與EB-LEACH算法相比，網(wǎng)絡(luò)生命周期又有一定延長。

圖7 存活節(jié)點個數(shù)與網(wǎng)絡(luò)運行輪數(shù)關(guān)系圖Fig 7 Network running number of sheaves vs number of nodes alive

表2統(tǒng)計了3種算法在第一個節(jié)點死亡、10%的節(jié)點死亡和剩余節(jié)點為節(jié)點總數(shù)10%時的輪數(shù)。如果以網(wǎng)絡(luò)剩余節(jié)點為節(jié)點總數(shù)10%作為網(wǎng)絡(luò)生命周期判斷，3種算法網(wǎng)絡(luò)生命周期分別為707，1484，1633，可以看出:EETCA有效地延長了網(wǎng)絡(luò)生命周期。

表2 3種算法節(jié)點死亡輪數(shù)比較Tab 2 Death number of rounds comparison of three algorithms of node

4 結(jié)束語

本文提出了一種能量高效的拓撲控制算法，該算法主要從簇頭的產(chǎn)生、簇的形成以及穩(wěn)定階段數(shù)據(jù)傳輸3個方面對LEACH進行了改進，并與LEACH和EB-LEACH算法進行比較。仿真實驗驗證了EETCA算法在網(wǎng)絡(luò)整體剩余能量、存活節(jié)點數(shù)方面均優(yōu)于LEACH和EB-LEACH算法。

［1］Mahfoudh S，Minet P.Survey of energy efficient strategies in wireless Ad Hoc and sensor networks［C］//The Seventh International Conference on Networking，Cancun:IEEE，2008:1-7.

［2］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）:660-670.

［3］Younis O，F(xiàn)ahmy S.HEED:A hybrid，energy-efficient，distributed clustering approach for Ad Hoc sensor networks［J］.IEEE Trans on Mobile Computing，2004，3（4）:660-669.

［4］尚鳳軍，Mehran Abolhasan，Tadeusz Wysocki.無線傳感器網(wǎng)絡(luò)的分布式能量有效非均勻成簇算法［J］.通信學(xué)報，2009，30（10）:34-43.

［5］Yassein M B，Al-zou'bi A，Khamayseh Y，et al.Improvement on LEACH protocol of wireless sensor networks（VLEACH）［J］.International Journal of Digital Content Technology and Its Applications，2009，3（2）:1-5.

［6］王偉超，代增全，徐啟建.LEACH協(xié)議簇頭選擇算法的改進［J］.無線電工程，2010，40（3）:1-3.

［7］周治平，王 亭，張明亮.傳感器網(wǎng)絡(luò)中一種能量有效的簇頭選擇機制［J］.計算機工程與應(yīng)用，2012，48（8）:105-108.

［8］Thein M C M，Thein T.An energy efficient cluster-head selection for wireless sensor networks［C］//2010 International Conference on Intelligent Systems，Modelling and Simulation（ISMS），2010:287-291.

［9］Li C F，Chen G H，Ye M，et al.An uneven cluster-based routing protocol for wireless sensor networks［J］.Chinese Journal of Computer，2007，30（1）:27-36.

［10］Rashed M G，Kabir M H，Ullah S E.WEP:An energy efficient protocol for cluster-based heterogeneous wireless sensor networks［J］.International Journal of Distributed and Parallel Systems（IJDPS），2011，2（2）:54-60.

［11］Saini P，Sharma A K.Energy efficient scheme for clustering protocol prolonging the lifetime of heterogeneous wireless sensor networks［J］.International Journal of Computer Applications，2010，6（2）:30-36.