侯 華，宋 彬，周武旸

(1.河北工程大學(xué) 移動(dòng)通信研究室，河北 邯鄲 056038；2.中國(guó)科學(xué)技術(shù)大學(xué) 無(wú)線(xiàn)信息網(wǎng)絡(luò)實(shí)驗(yàn)室，安徽 合肥 230027)

能量感知非均勻成簇路由優(yōu)化算法

侯 華1，宋 彬1，周武旸2

(1.河北工程大學(xué) 移動(dòng)通信研究室，河北 邯鄲 056038；2.中國(guó)科學(xué)技術(shù)大學(xué) 無(wú)線(xiàn)信息網(wǎng)絡(luò)實(shí)驗(yàn)室，安徽 合肥 230027)

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSN)具有的能量有限，其能量利用效率的高低直接影響著網(wǎng)絡(luò)的生命周期。為了提高無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的能量利用效率，提出了一種能量感知非均勻成簇路由優(yōu)化算法(Energy Awareness Unequal Clustering Routing Optimization Algorithm，EUCR)。該算法通過(guò)節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置確定各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，并以局部能量選舉簇頭，各簇頭根據(jù)其鄰居節(jié)點(diǎn)構(gòu)建非均勻分簇網(wǎng)絡(luò)。同時(shí)該算法在路由階段考慮了簇頭的剩余能量和轉(zhuǎn)發(fā)代價(jià)。仿真結(jié)果表明，EUCR算法能有效提高網(wǎng)絡(luò)的能量利用效率，并延長(zhǎng)網(wǎng)絡(luò)的生命周期。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)；能量感知；非均勻分簇；多跳路由

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)因其快速方便的部署特性和完備的監(jiān)控能力被廣泛應(yīng)用于軍事、救災(zāi)、環(huán)境、醫(yī)療、智能家居等領(lǐng)域[1]。但由于傳感器節(jié)點(diǎn)采用電池供電的模式，且節(jié)點(diǎn)一旦部署之后，其電池不可更換，因此如何延長(zhǎng)網(wǎng)絡(luò)的生命周期是WSN面臨的主要問(wèn)題之一[2-3]。

以L(fǎng)EACH[4]和空間信息與梯度協(xié)議[5]為代表的分簇算法均衡了節(jié)點(diǎn)的能量消耗，但由于該類(lèi)協(xié)議采用的都是單跳路由模型，因此在大規(guī)模網(wǎng)絡(luò)中所提算法涉及到的距離基站比較遠(yuǎn)的節(jié)點(diǎn)能量消耗比較快，很容易使這類(lèi)節(jié)點(diǎn)過(guò)早死亡。文獻(xiàn)[6-7]采用多跳的路由協(xié)議，克服了上述單跳路由模型中部分節(jié)點(diǎn)過(guò)早死亡的不足。但多跳路由模型容易出現(xiàn)能量空洞現(xiàn)象。

為了解決能量空洞問(wèn)題，本文提出了能量感知非均勻成簇路由優(yōu)化算法(EUCR)算法。該算法采用先尋找鄰居節(jié)點(diǎn)，再成簇的思想，提高了成簇效率。同時(shí)，EUCR算法通過(guò)局部能量選舉簇頭，使能量大的節(jié)點(diǎn)盡可能地當(dāng)選為簇頭，提高了網(wǎng)絡(luò)的能量利用效率。在數(shù)據(jù)傳輸階段，EUCR算法將節(jié)點(diǎn)的剩余能量和轉(zhuǎn)發(fā)代價(jià)[7]的比值作為尋找路由的依據(jù)，使得選出的簇頭更適合擔(dān)當(dāng)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)。通過(guò)仿真驗(yàn)證，該算法能有效地均衡網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的能量消耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期。

1 系統(tǒng)模型

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

為了便于研究，本文作出如下假設(shè)：N個(gè)節(jié)點(diǎn)隨機(jī)地分布在一個(gè)正方形區(qū)域，網(wǎng)絡(luò)中的第i個(gè)傳感器節(jié)點(diǎn)用si表示，其中i={1,2,…,N}，基站位于正方形區(qū)域外的一側(cè)。節(jié)點(diǎn)一旦部署之后不可再移動(dòng)，且每個(gè)節(jié)點(diǎn)在部署時(shí)都會(huì)被分配一個(gè)唯一的ID標(biāo)識(shí)符。

1.2 能量消耗模型

本文采用與文獻(xiàn)[6]相同的能量消耗模型。傳感器節(jié)點(diǎn)將lbit的數(shù)據(jù)發(fā)送到與其距離為d的目的節(jié)點(diǎn)時(shí)需要消耗的能量為

(1)

節(jié)點(diǎn)接收l(shuí)bit數(shù)據(jù)包需要消耗的能量為

ERX(l)=lEelec

(2)

式中：Eelec代表收發(fā)電路的損耗能量，εfs和εmp為放大器系數(shù)，d0表示臨界距離。當(dāng)數(shù)據(jù)傳輸距離小于臨界距離d0時(shí)，采用自由空間模型，此時(shí)的能量消耗和距離的2次方成正比；當(dāng)數(shù)據(jù)傳輸距離大于臨界距離d0時(shí)，采用多徑衰落模型，此時(shí)的能量消耗和距離的4次方成正比。d0的取值為

(3)

2 算法設(shè)計(jì)

2.1 簇頭選舉

在LEACH協(xié)議中，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)隨機(jī)數(shù)，若隨機(jī)數(shù)大于簇頭選舉的閾值T(si)，則該節(jié)點(diǎn)就當(dāng)選為簇頭。每個(gè)節(jié)點(diǎn)參加簇頭選舉的閾值為

(4)

由式(4)可以看出，在LEACH協(xié)議中，每個(gè)節(jié)點(diǎn)參加簇頭選舉的概率都為P。而在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，隨著網(wǎng)絡(luò)的長(zhǎng)時(shí)間運(yùn)行，網(wǎng)絡(luò)中各節(jié)點(diǎn)的能量都會(huì)出現(xiàn)很大的差異，這時(shí)能量小的節(jié)點(diǎn)可能會(huì)被當(dāng)選為簇頭，而簇頭的能量消耗要比簇內(nèi)節(jié)點(diǎn)大很多，這會(huì)致使網(wǎng)絡(luò)中的節(jié)點(diǎn)能量更加不均衡。本文利用節(jié)點(diǎn)的當(dāng)前能量和局部最大能量的比值作為簇頭選舉概率P的調(diào)節(jié)參數(shù)，增大了高能量節(jié)點(diǎn)當(dāng)選為簇頭的概率。局部最大能量可由式(6)確定，在確定局部最大能量時(shí)，需要先尋找節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)的確定在后文會(huì)有介紹。改進(jìn)后的簇頭選舉概率Psi,CH如

(5)

(6)

式中：Psi,CH為網(wǎng)絡(luò)中的任意節(jié)點(diǎn)si參加簇頭選舉的概率；Esi為節(jié)點(diǎn)si的當(dāng)前能量；ELocalMax為節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)中的最大能量；NEIGHBORSsi為節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)集。

改進(jìn)后簇頭的選舉閾值可表示為

廣告商定義了產(chǎn)品的調(diào)性，消費(fèi)者趨之若鶩，走進(jìn)一些人滿(mǎn)為患的性冷淡風(fēng)店鋪，嘗試一些沒(méi)多驚艷的網(wǎng)紅食品。錦鯉的獎(jiǎng)品就是欲望的合集，獲得它，你就是擁有品位和運(yùn)氣的女孩。

(7)

2.2 非均勻分簇算法

為了構(gòu)建非均勻分簇網(wǎng)絡(luò)，本文提出了一個(gè)與節(jié)點(diǎn)在網(wǎng)絡(luò)中位置相關(guān)的節(jié)點(diǎn)成簇通信半徑Rsi·comp，即

(8)

式中：dmax為網(wǎng)絡(luò)中節(jié)點(diǎn)距基站的最遠(yuǎn)距離；dmin為網(wǎng)絡(luò)中節(jié)點(diǎn)距基站的最近距離；dsi,BS為網(wǎng)絡(luò)中任意節(jié)點(diǎn)si距基站的距離。

在網(wǎng)絡(luò)啟用時(shí)的第一次成簇階段，網(wǎng)絡(luò)中的任意節(jié)點(diǎn)si在半徑為Rsi·comp的通信范圍內(nèi)尋找自己的鄰居節(jié)點(diǎn)。首先，節(jié)點(diǎn)si隨機(jī)地退避一段時(shí)間，退避時(shí)間結(jié)束后，節(jié)點(diǎn)si發(fā)送廣播消息Node_Find_Neighbor_MSG尋找自己的鄰居節(jié)點(diǎn)，收到Node_Find_Neighbor_MSG消息的節(jié)點(diǎn)sj根據(jù)信號(hào)強(qiáng)度求得其與節(jié)點(diǎn)si的距離dsi,sj。為了保持網(wǎng)絡(luò)的連通性，本文規(guī)定只有當(dāng)dsi,sj≤Rsi·comp且dsi,sj≤Rsj·comp時(shí)，節(jié)點(diǎn)sj才為節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)，反之則不是。若節(jié)點(diǎn)sj為節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)，則節(jié)點(diǎn)sj向節(jié)點(diǎn)si返回一個(gè)包含自己能量信息的確認(rèn)消息Node_Neighbor_ACK_MSG。節(jié)點(diǎn)si收到確認(rèn)消息Node_Neighbor_ACK_MSG后，會(huì)將節(jié)點(diǎn)sj記錄到自己的鄰居節(jié)點(diǎn)集NEIGHBORSsi中。鄰居節(jié)點(diǎn)集確定后，各節(jié)點(diǎn)按式(7)參加簇頭選舉。節(jié)點(diǎn)當(dāng)選為簇頭后，該節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)集就組成一個(gè)簇。對(duì)于同時(shí)屬于多個(gè)簇頭的鄰居節(jié)點(diǎn)，依據(jù)式(9)判斷其應(yīng)加入哪個(gè)簇。

sj∈CCHsi:dsj,CHsi≤dsj,CHsk

(9)

式中：CHsi和CHsk為簇頭，sj為簇頭CHsi和CHsk的鄰居節(jié)點(diǎn)，CCHsi代表簇頭為CHsi的簇。

在網(wǎng)絡(luò)經(jīng)歷了第一次成簇之后，網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)都保存了一個(gè)自己的鄰居節(jié)點(diǎn)集，由于每個(gè)節(jié)點(diǎn)的通信半徑是固定的，所以在網(wǎng)絡(luò)啟用時(shí)的第一次成簇階段，節(jié)點(diǎn)所確定的鄰居節(jié)點(diǎn)集即為該節(jié)點(diǎn)的最大鄰居節(jié)點(diǎn)集，當(dāng)網(wǎng)絡(luò)中有節(jié)點(diǎn)死亡時(shí)，相應(yīng)的節(jié)點(diǎn)就會(huì)從自己的鄰居節(jié)點(diǎn)集中刪除死亡節(jié)點(diǎn)。在本文中，每個(gè)節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)集被稱(chēng)為一個(gè)偽簇，在網(wǎng)絡(luò)第一次成簇之后的生存周期中，只要確定了簇頭，簇頭節(jié)點(diǎn)所確定的偽簇就自動(dòng)升級(jí)為簇。這種先確定鄰居節(jié)點(diǎn)再分簇的方法相對(duì)于傳統(tǒng)的先確定簇頭再分簇的方法，減少了成簇階段所耗費(fèi)的時(shí)間，同時(shí)也簡(jiǎn)化了成簇的復(fù)雜度，提高了成簇的效率。

2.3 路由

本文在選擇下一跳路由時(shí)，對(duì)簇頭的通信范圍和簇頭到基站的距離等參數(shù)做了限制，同時(shí)從能量利用效率的角度考慮了下一跳路由的轉(zhuǎn)發(fā)代價(jià)。

(10)

3 算法評(píng)價(jià)

本文通過(guò)與LEACH和NEW-LEACH算法的仿真對(duì)比來(lái)評(píng)估EUCR算法的有效性和可行性。本文所有的仿真實(shí)驗(yàn)在MATLAB環(huán)境下進(jìn)行。在仿真實(shí)驗(yàn)中，網(wǎng)絡(luò)為200 m×200 m正方形區(qū)域，基站位于(100，250)m處，節(jié)點(diǎn)總數(shù)為400個(gè)，節(jié)點(diǎn)的初始能量為0.5 J，Eelec為50 nJ/bit，εfs為10 pJ/(bit·m2)，εamp為0.001 3 pJ/(bit·m4)，數(shù)據(jù)包大小為4 000 bit，控制包大小為200 bit。

圖1為3種算法網(wǎng)絡(luò)生命周期的對(duì)比。其中LEACH，NEW-LEACH和EUCR算法中第1個(gè)節(jié)點(diǎn)的死亡時(shí)間分別為220，700和921，可見(jiàn)EUCR的網(wǎng)絡(luò)生命周期比NEW-LEACH的提高了32%，比LEACH的提高了319%。原因在于，在LEACH中，簇頭采用單跳的方式與基站進(jìn)行數(shù)據(jù)交換，使距離基站較遠(yuǎn)的簇頭能量消耗較大，導(dǎo)致其過(guò)早死亡。而NEW-LEACH和EUCR都采用多跳的通信方式與基站進(jìn)行數(shù)據(jù)交換，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。由于EUCR算法采用的簇頭選舉策略和路由協(xié)議，比NEW-LEACH算法的更加合理，所以EUCR的網(wǎng)絡(luò)生命周期比NEW-LEACH要長(zhǎng)。

圖1 網(wǎng)絡(luò)生存周期

本文以網(wǎng)絡(luò)中第1個(gè)節(jié)點(diǎn)的死亡時(shí)間和最后1個(gè)節(jié)點(diǎn)的死亡時(shí)間的比值作為網(wǎng)絡(luò)生存周期的能量平衡率。算法的能量平衡率越高，網(wǎng)絡(luò)的能量利用效率就越好。由圖2可知LEACH，NEW-LEACH和EUCR算法的能量平衡率分別為36%，52%，60%。其中LEACH的能量平衡率最低，EUCR的能量平衡率較NEW-LEACH有所提高。說(shuō)明EUCR的能量利用效率最高，NEW-LEACH次之，LEACH的最差。

圖2 能量平衡率

本文對(duì)隨機(jī)選取的20輪簇頭能量消耗進(jìn)行了對(duì)比，如圖3所示。其中，LEACH算法中的簇頭能量消耗波動(dòng)較大，NEW-LEACH和EUCR兩種算法中的簇頭能量消耗波動(dòng)較小。這說(shuō)明NEW-LEACH和EUCR能更好地平衡簇頭之間的能耗。由圖3還可以看出，EUCR中簇頭的能耗最低，說(shuō)明EUCR的簇頭能量利用效率最高。

圖3 簇頭的能耗

4 結(jié)論

本文提出的能量感知非均勻成簇路由優(yōu)化算法由于只需在第一次啟用網(wǎng)絡(luò)時(shí)尋找一次鄰居節(jié)點(diǎn)，所以與其他傳統(tǒng)的算法相比提高了網(wǎng)絡(luò)的成簇效率。簇頭選舉策略和路由的改進(jìn)，提高了網(wǎng)絡(luò)的能量利用效率。但本文提出的算法只考慮了網(wǎng)絡(luò)的局部能量消耗，使得選出的簇頭和路由不是最優(yōu)的。下一步的工作，將考慮全局能量消耗對(duì)網(wǎng)絡(luò)的影響。

[1] KUILA P，GUPTA S K，JANA P K. A novel evolutionary approach for load balanced clustering problem for wireless sensor networks[J].Swarm and Evolutionary Computation，2013(12)：48-56.[2] YAN R，SUN Hanghang，QIAN Yuning.Energy-aware sensor node design with its application in wireless sensor networks[J]. IEEE Trans. Instrumentation and Measurement，2013，62(5)：118-1191.

[3] SUN Hanghang，QIAN Yuning，YAN Ruqiang.Design and realization of an intelligent sensor node with its application in energy-aware WSNs[C]//Proc. IEEE International Conference on Instrumentation and Measurement Technology. [S.l.]：IEEE Press，2012：941- 946.

[4] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[EB/OL].[2014-12-12].IEEE Trans. Wireless Communications，2002，1(4)：660 - 670.

[5] 廖惜春，楊志高，任敬哲. 基于空間信息與梯度的WSN分簇路由算法[J].電視技術(shù)，2014，38(5)：120-123.

[6] LI Chengfa，YE Mao，CHEN Guihai，et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]//Proc. IEEE International Conference on Mobile Adhoc and Sensor Systems.[S.l.]：IEEE Press，2005：8- 604.

[7] 胡峰松，肖球.一種基于LEACH的能耗均衡多跳路由算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2014(1)：70-73.

宋 彬(1987— )，研究生，研究方向?yàn)闊o(wú)線(xiàn)傳感器網(wǎng)絡(luò)；

周武旸(1972— )，博士，教授，博士生生導(dǎo)師， 研究方向?yàn)槎噍d波技術(shù)跨層協(xié)議處理。

責(zé)任編輯：許 盈

Energy Awareness Unequal Clustering Routing Optimization Algorithm

HOU Hua1, SONG Bin1,ZHOU Wuyang2

(1.HebeiUniversityofEngineering,MobileCommunicationsResearchLaboratory,HebeiHandan056038,China;2.USTC,WirelessInformationNetworkLab,Hefei230027,China)

Wireless sensor networks (WSN) have limited energy, so its energy efficiency directly affects the life cycle of the network. In this paper, a new kind of energy awareness unequal clustering routing optimization algorithm (EUCR) is put forward. EUCR algorithm selects cluster head by local energy, and it expressly makes an optimization in clustering method and route. The simulation results show that EUCR can effectively improve the network energy efficiency, and prolong the life cycle of the network.

WSN; energy awareness; unequal clustering; multi-hop routing

【本文獻(xiàn)信息】侯華，宋彬，周武旸.能量感知非均勻成簇路由優(yōu)化算法[J].電視技術(shù),2015，39(13).

河北省高等學(xué)?？茖W(xué)技術(shù)研究重點(diǎn)項(xiàng)目(ZH2011222)

TP393

A

10.16280/j.videoe.2015.13.016

侯 華(1980— )，女，博士，副教授，研究生導(dǎo)師，研究方向?yàn)橐苿?dòng)通信、無(wú)線(xiàn)通信和認(rèn)知無(wú)線(xiàn)電技術(shù)；

2015-01-13