湯 杰，鄭 霖

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

能耗均衡的無線傳感網(wǎng)絡(luò)不等環(huán)分層路由算法

湯 杰，鄭 霖

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

針對無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)中鄰近匯聚節(jié)點(diǎn)(sink)的傳感節(jié)點(diǎn)負(fù)荷和能耗過載問題，基于整體網(wǎng)絡(luò)能耗平衡目標(biāo)，提出一種不等環(huán)的次優(yōu)分層網(wǎng)絡(luò)路由。在均勻分布的傳感節(jié)點(diǎn)環(huán)境中，以sink為中心，按照拓?fù)渚嚯x進(jìn)行分環(huán)多跳路由，理論推導(dǎo)了不等環(huán)半徑，并考慮單跳能耗。實(shí)驗(yàn)分析仿真結(jié)果表明，該路由分層模型延長了網(wǎng)絡(luò)生存周期，提高了節(jié)點(diǎn)利用效率，且達(dá)到網(wǎng)絡(luò)內(nèi)大部分節(jié)點(diǎn)能耗均衡的目標(biāo)。

無線傳感器網(wǎng)絡(luò)；網(wǎng)絡(luò)生存周期；能耗均衡

0 引言

無線傳感器網(wǎng)絡(luò)中的“熱區(qū)”現(xiàn)象是由sink附近的節(jié)點(diǎn)固定充當(dāng)其他節(jié)點(diǎn)與sink之間的中繼節(jié)點(diǎn)，從而導(dǎo)致這部分節(jié)點(diǎn)能量消耗過快產(chǎn)生的。“熱區(qū)”問題造成的路由空洞會使網(wǎng)絡(luò)提前死亡。為了延長傳感網(wǎng)絡(luò)的生存周期，解決“熱區(qū)”問題無疑變得很關(guān)鍵[1-3]。為部署在環(huán)境艱險和惡劣的傳感器更換電池是不現(xiàn)實(shí)的，再加上能量的不均勻損耗，所以傳感器網(wǎng)絡(luò)能耗一直是關(guān)鍵的問題。

現(xiàn)階段對能耗問題的研究已經(jīng)有很多，文獻(xiàn)[4]基于簡單的Gossiping協(xié)議提出改進(jìn)型E-Gossiping，通過調(diào)整原有協(xié)議的Gossiping概率，以及基于每個節(jié)點(diǎn)自身的剩余能量來控制節(jié)點(diǎn)行為來減小冗余數(shù)據(jù)的發(fā)送，從而來減小網(wǎng)絡(luò)能耗。有大量通過增加考慮影響節(jié)點(diǎn)能耗的因素而對協(xié)議進(jìn)行改進(jìn)的工作存在，因此，早期關(guān)于無線傳感器網(wǎng)絡(luò)能耗研究著重點(diǎn)都在于減少節(jié)點(diǎn)之間的通信頻率和采用能量高效利用的路由協(xié)議[5-6]。與此不同，傳感節(jié)點(diǎn)與sink可直接通信也可以通過成簇，統(tǒng)一由簇頭進(jìn)行通信，大量研究已經(jīng)證明與sink直接通信的方式比成簇或分層路由的方式能耗要大。文獻(xiàn)[7]提出基于成簇的路由協(xié)議，所有節(jié)點(diǎn)會分為若干個規(guī)模相當(dāng)?shù)男〈兀總€簇中會根據(jù)節(jié)點(diǎn)自身能耗，數(shù)據(jù)量大小等因素競爭成為簇頭，簇頭之間進(jìn)行通信并傳輸數(shù)據(jù)給sink節(jié)點(diǎn)，這種方式能耗主要集中在簇頭，所以節(jié)點(diǎn)間競爭成為簇頭的機(jī)制有利于所有節(jié)點(diǎn)均衡分擔(dān)路由所帶來的能耗。為改善無線傳感器網(wǎng)絡(luò)覆蓋性能，文獻(xiàn)[8]提出了隨機(jī)休眠算法，但隨機(jī)的方法難以保證網(wǎng)絡(luò)覆蓋率，只適于節(jié)點(diǎn)密度大覆蓋率要求低的場合。文獻(xiàn)[9]等提出了一種輕量級的部署調(diào)度算法，稱為LDAS，先計(jì)算一個節(jié)點(diǎn)被它若干個鄰居完全覆蓋的概率，隨后計(jì)算一個節(jié)點(diǎn)被它若干個鄰居覆蓋區(qū)域占自身檢測區(qū)域的百分比，基于這2個結(jié)果判斷一個節(jié)點(diǎn)是否應(yīng)休眠，此算法在延長網(wǎng)絡(luò)生存周期的同時又能保證較高網(wǎng)絡(luò)覆蓋率。

文獻(xiàn)[10]采用環(huán)形分層模型，從節(jié)點(diǎn)的不均勻分布入手，推導(dǎo)證明等環(huán)模型下全網(wǎng)能耗均衡的充分必要條件。文獻(xiàn)[11]改進(jìn)了分簇路由協(xié)議，通過控制不同環(huán)里構(gòu)建大小不同的簇，以均衡不同環(huán)的簇頭間的能耗，使其簇頭在簇內(nèi)通信和數(shù)據(jù)聚合上的能量減小，以補(bǔ)償其因?yàn)檗D(zhuǎn)發(fā)外環(huán)簇頭的數(shù)據(jù)包而造成的能量損失；而離sink越遠(yuǎn)的環(huán)，形成簇的規(guī)模越大，使其在簇內(nèi)通信和數(shù)據(jù)聚合上的能量增大，以抵消其轉(zhuǎn)發(fā)數(shù)據(jù)少而節(jié)省的能量，從而達(dá)到網(wǎng)絡(luò)能耗均衡的效果。

正如上述提到的各類算法，延長網(wǎng)絡(luò)生存周期的有效方法可以通過使用高效的路由策略、節(jié)點(diǎn)對自身行為的控制、節(jié)點(diǎn)的休眠喚醒和整體網(wǎng)絡(luò)能耗均衡理論等等。但未從整體上考慮能耗均衡問題，本文在網(wǎng)絡(luò)能耗均衡理論基礎(chǔ)上，結(jié)合節(jié)點(diǎn)的高效利用的想法提出了環(huán)形不等距的網(wǎng)絡(luò)模型，最大化利用所有傳感器節(jié)點(diǎn)處理和能耗，并證明它在延長網(wǎng)絡(luò)生存周期上的作用。

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

假設(shè)網(wǎng)絡(luò)中大量的節(jié)點(diǎn)均勻分布在一個半徑為50 m的圓形區(qū)域內(nèi)。網(wǎng)絡(luò)中唯一的sink置于圓形區(qū)域中心，所有的節(jié)點(diǎn)都是同質(zhì)的，每個節(jié)點(diǎn)的感知半徑固定且相同。如圖1所示，網(wǎng)絡(luò)被劃分為L(L>1)個相鄰的環(huán)形區(qū)域，每個扇環(huán)的寬度根據(jù)計(jì)算所得。從內(nèi)向外，用Li表示第i層，最外層用LR表示。為了簡化問題參見文獻(xiàn)[12-17]，本文路由采用環(huán)與環(huán)之間單跳傳輸[18]，直至數(shù)據(jù)傳輸至sink。

圖1 網(wǎng)絡(luò)模型

2 不等環(huán)網(wǎng)絡(luò)模型分析

假設(shè)一個節(jié)點(diǎn)發(fā)送一比特?cái)?shù)據(jù)所消耗的能量是e1，接收一比特?cái)?shù)據(jù)消耗的能量是e2，感知一比特?cái)?shù)據(jù)消耗的能量是e3，Ni為i環(huán)節(jié)點(diǎn)數(shù)，M為數(shù)據(jù)量。可知最外環(huán)內(nèi)節(jié)點(diǎn)只需感知和發(fā)送數(shù)據(jù)，無需轉(zhuǎn)發(fā)數(shù)據(jù)，則各個環(huán)內(nèi)所有節(jié)點(diǎn)在單位時間內(nèi)消耗的能量為[19]：

(1)

理想情況下，網(wǎng)絡(luò)中的每個節(jié)點(diǎn)同時耗盡自身的能量時，能耗效率得到了最優(yōu)化。此時，網(wǎng)絡(luò)的生存時間為：

(2)

但在最外環(huán)，按上式有NR-1/ER-1=NR/ER，即NR-1(e1+e3)=NR(e1+e2)+NR-1(e1+e3)，很明顯是不成立的。因此，該能耗模型在最外環(huán)無法成立，只能按次優(yōu)處理。當(dāng)最外環(huán)節(jié)點(diǎn)數(shù)較小時，對整個網(wǎng)絡(luò)生存周期影響并不大。

除了網(wǎng)絡(luò)最外層的節(jié)點(diǎn)外，其他各個環(huán)中的所有節(jié)點(diǎn)能實(shí)現(xiàn)能耗的均衡，即

(3)

根據(jù)式(3)成立，得

NiEi+1=Ni+1Ei。

(4)

考慮到傳感節(jié)點(diǎn)一般不采用較為復(fù)雜的功率控制[20-22]，所以各節(jié)點(diǎn)采用等發(fā)射功率e1，且假設(shè)該發(fā)射功率滿足通信距離的要求將能耗式(1)代入式(4)得:

(5)

交叉相乘化簡后得：

1≤i≤R-2。

(6)

(7)

根據(jù)式(7)，當(dāng)L=3，已知:

(8)

當(dāng)L=4，已知：

(9)

可得：

(10)

可知當(dāng)滿足網(wǎng)絡(luò)次優(yōu)化理論時，圓環(huán)LR-1到L1節(jié)點(diǎn)數(shù)目以等比數(shù)值q遞增，LR-1與LR節(jié)點(diǎn)數(shù)目之比為q-1。

3 能耗均衡策略

(11)

當(dāng)L=3,

(12)

當(dāng)L=4,

(13)

當(dāng)L=5,

(14)

當(dāng)L=k,

(15)

根據(jù)網(wǎng)絡(luò)次優(yōu)化理論，可知不等環(huán)環(huán)寬是隨著外環(huán)負(fù)載的大小而變化的，不同的負(fù)載對應(yīng)著不同的環(huán)寬以達(dá)到整個網(wǎng)絡(luò)負(fù)載平衡的目的，而且不相等的每一環(huán)中有不相等的節(jié)點(diǎn)數(shù)量，環(huán)大的對應(yīng)的節(jié)點(diǎn)數(shù)多，環(huán)小的對應(yīng)的節(jié)點(diǎn)數(shù)少，這樣可大大地提高了節(jié)點(diǎn)的利用效率。所以假設(shè)最外環(huán)節(jié)點(diǎn)數(shù)為：

(16)

因?yàn)閞k=R已知，所以rk-1已知，從而再算出r1與q值，再由上述環(huán)寬關(guān)系式得出各個環(huán)半徑。

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

4.1 仿真環(huán)境

使用Matlab仿真平臺[23]對本文提出的模型進(jìn)行仿真實(shí)，并與等環(huán)網(wǎng)絡(luò)模型進(jìn)行比較。網(wǎng)絡(luò)節(jié)點(diǎn)為100～500，對應(yīng)最外環(huán)節(jié)點(diǎn)數(shù)為21～104。q為等比數(shù)值取為1.5，節(jié)點(diǎn)剩余能耗在0.03、0.04和0.05中隨機(jī)分配，sink節(jié)點(diǎn)的坐標(biāo)位置在(0，0)，L為分環(huán)數(shù)目取為5，εfs參數(shù)取為10 pJ/(bit·m2)，εmp參數(shù)取為0.001 3 pJ/(bit·m2)。

4.2 對比說明

如圖2所示，仿真證明當(dāng)最外環(huán)節(jié)點(diǎn)數(shù)較小時，對整個網(wǎng)絡(luò)生存周期影響并不大。

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

如圖3所示，不等環(huán)網(wǎng)絡(luò)模型是基于次優(yōu)的網(wǎng)絡(luò)能耗均衡理論得出，從仿真結(jié)果看，不等環(huán)模型下網(wǎng)絡(luò)的生存周期是高于等環(huán)模型的，而且整體趨勢相同。隨著節(jié)點(diǎn)數(shù)目增加，網(wǎng)絡(luò)生存周期都是首先提高趨勢明顯然后趨于平緩，但還是有略微上升的趨勢。

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

如圖4所示，首個節(jié)點(diǎn)的死亡時間代表著網(wǎng)絡(luò)能正常工作的周期。在節(jié)點(diǎn)數(shù)目較少的情況下，等環(huán)模型下出現(xiàn)節(jié)點(diǎn)死亡的時間遠(yuǎn)早于不等環(huán)模型。隨著節(jié)點(diǎn)數(shù)目增加，兩模型出現(xiàn)死亡節(jié)點(diǎn)的時間靠近，隨著節(jié)點(diǎn)數(shù)增多首節(jié)點(diǎn)死亡出現(xiàn)時間呈波浪分布是由網(wǎng)絡(luò)本身節(jié)點(diǎn)能量的不均勻分配和路由選路造成的。

圖4 首節(jié)點(diǎn)死亡周期

如圖5所示，以300個節(jié)點(diǎn)數(shù)，62個最外環(huán)節(jié)點(diǎn)數(shù)為例。隨著網(wǎng)絡(luò)的運(yùn)行等環(huán)模型下節(jié)點(diǎn)首先開始出現(xiàn)死亡，且死亡速率相對較快，在整個網(wǎng)絡(luò)周期中有一段時間不等環(huán)模型下死亡的節(jié)點(diǎn)數(shù)是多于等環(huán)模型的，但整體上死亡節(jié)點(diǎn)數(shù)目還是在等環(huán)模型之下。

圖5 網(wǎng)絡(luò)節(jié)點(diǎn)剩余數(shù)

從以上仿真不等環(huán)模型與等環(huán)模型的仿真對比來看，不等環(huán)模型下能更好地均衡整體網(wǎng)絡(luò)能耗，從而更有效減緩熱區(qū)效應(yīng)，進(jìn)而達(dá)到網(wǎng)絡(luò)的生存周期的提高，并且就節(jié)點(diǎn)的部署方式來看，不等環(huán)模型下非均勻的節(jié)點(diǎn)分布模式減小了節(jié)點(diǎn)間重疊覆蓋區(qū)域，從而提高了節(jié)點(diǎn)利用效率。

5 結(jié)束語

本文針對無線傳感器網(wǎng)絡(luò)中存在的熱區(qū)問題，從節(jié)點(diǎn)的非均勻分布入手。首先對節(jié)點(diǎn)的非均勻分布進(jìn)行理論分析。鑒于以上理論分析，在此基礎(chǔ)上提出不等環(huán)網(wǎng)絡(luò)模型，論述了不等環(huán)模型在提高節(jié)點(diǎn)利用率方面的作用，并進(jìn)行了仿真實(shí)驗(yàn)和性能分析。實(shí)驗(yàn)從網(wǎng)絡(luò)生存周期、網(wǎng)絡(luò)正常工作周期和節(jié)點(diǎn)死亡數(shù)量3個方面與等環(huán)網(wǎng)絡(luò)模型進(jìn)行比較，結(jié)果表明不等環(huán)模型能夠達(dá)到延長網(wǎng)絡(luò)生存周期的目的。

[1] XUE Y,CHANG X,ZHONG S,et al.An Efficient Energy Hole Alleviating Algorithm for Wireless Sensor Networks[J].IEEE Transactions on Consumer Electronics,2014,60(3):347-355.

[2] REN J,ZHANG Y,ZHANG K,et al.Lifetime and Energy Hole Evolution Analysis in Data-gathering Wireless Sensor Networks[J].IEEE Transactions on Industrial Informatics,2015,12(2):1-10.

[3] 馬祖長,孫怡寧,梅濤.無線傳感器網(wǎng)絡(luò)綜述[J].通信學(xué)報(bào),2004,25(4):114-124.

[4] LEE B,SONG H K,SUH Y,et al.Energy-efficient Gossiping Protocol of WSN with Realtime Streaming Data[Z].IEEE International Conference on Dependable,2014:219-224.

[5] LI J,SHATZ S,KSHEMKALYANI A D.Mobile Sampling of Sensor Field Data Using Controlled Broadcast[J].IEEE Transactions on Mobile Computing,2010,10(6):881-896.

[6] BLUM R S.Ordering for Estimation and Optimization in Energy Efficient Sensor Networks[J].IEEE Transactions on Signal Processing,2011,59(6):2847-2856.

[7] 陳飛.無線傳感器網(wǎng)絡(luò)成簇算法及路由協(xié)議研究[D].成都：電子科技大學(xué),2011:1-83.

[8] LIUC，WU K,XIAO Y,et al.RandomCoverage with Guaranteed Connectivity:Joint Scheduling for Wireless Sensor Networks[J].IEEE Transactions onParallel & Distributed Systems,2006,17(6):562-575.

[9] WU K,GAO Y,LI F,et al.Lightweight Deployment-ware Scheduling for Wireless Sensor Networks[J].Mobile Networks and Applications,2005,10(6):837-852.

[10] WU X,CHEN G,DAS S K.On the Energy Hole Problem of Nonuniform Node Distribution in Wireless Sensor Networks[J].IEEE International Conference on Mobile Ad Hoc and Sensor Systems,2006,31(2):180-187.

[11] 黃亮.無線傳感網(wǎng)分層路由算法的改進(jìn)研究[D].西安:西安科技大學(xué),2014:1-68.

[12] TIAN D,GEORGANAS N D.A Coverage-preserving Node Scheduling Scheme for Large Wireless Sensor Networks[M].USA:WSNA ′02 Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications,2002:32-41.

[13] XUE Y,CHANG X,ZHONG S,et al.An Efficient Energy Hole Alleviating Algorithm for Wireless Sensor Networks[J].IEEE Transactions on Consumer Electronics,2014,60(3):347-355.

[14] REN J,ZHANG Y,ZHANG K,et al.Lifetime and Energy Hole Evolution Analysis in Data Gathering Wireless Sensor Networks[J].IEEE Transactions on Industrial Informatics,2015,12(2):1-11.

[15] XU Y,ZENG Z R,DING O.An Energy Efficient Hole Repair Node Scheduling Algorithm for WSN[M].Wireless Networks,2015:1-14.

[16] LI J,MOHAPATRA P.An Analytical Model for the Energy Hole Problem in Many-to-one Sensor NetWorks[J].IEEE Vehicular Technology Conference，2006,4(4):2721-2725.

[17] BANERJEE.Energy Efficient Routing and by Passingenergy-hole through Mobile Sink in WSN[Z].Int-ernational Conference on Computer Communica-tion and Informatics，2014:1-6.

[18] AINI A,SALEHIPOUR A.Speeding up the Floyd-War-shall Algorithm for the Cycled Shortest Path Problem[J].Applied Mathematics Letters,2012,25(1):1-5.

[19] RAPPAPORTT S.Wireless Communications:Principles and Practice[M].Prentice Hall,2001.

[20] WANG X,WANG X,XING G,et al.Minimum Transmis-sion Power Configuration in Real Time Sensor Networks with Overlapping Channels[J].ACM Tra-nsactions on Sensor Networks,2013,9(2):1-28.

[21] 胥楚貴,鄧曉衡,鄒豪杰.無線傳感器網(wǎng)絡(luò)通信半徑動態(tài)調(diào)整的能耗均衡策略[J].傳感技術(shù)學(xué)報(bào),2009,22(5):712-716.

[22] YILDIZ H U,TAVLI B,YANIKOMEROGLU H.Transmissio-n Power Control for Link-Level Handshaking in Wireless Sensor Networks[J].IEEE Sensors Jour-nal,2015,16(2):561-576.

[23] 張培強(qiáng).MATLAB語言[M].合肥:中國科學(xué)技術(shù)大學(xué)出版社,1995：1-203.

HierarchicalRoutingAlgorithmwithDifferentRing-radiusBasedonEnergyConsumptionBalanceforWirelessSensorNetworks

TANG Jie,ZHENG Lin

(SchoolofInformationandCommunicationEngineering,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China)

Aiming at the problem of the load and energy overload in the nodes around the sink,this paper proposed a suboptimal network routing model with inequality rings based on the theory of balance energy consumption of the whole network.This model makes use of uniform node distribution around the sink,routing between rings according to the topology radius,which is deduced combined with energy consumption.Performance analysis and simulation results show that the proposed model extends the network lifetime,improves the utilization efficiency of nodes,and reaches the goal of energy balance of most nodes in the network.

wireless sensor network(WSN);network lifetime;energy balance

10.3969/j.issn.1003-3106.2017.10.03

湯杰，鄭霖.能耗均衡的無線傳感網(wǎng)絡(luò)不等環(huán)分層路由算法[J].無線電工程,2017,47(10)12-16.[TANG Jie,ZHENG Lin.Hierarchical Routing Algorithm with Different Ring-radius Based on Energy Consumption Balance for Wireless Sensor Networks[J].Radio Engineering,2017,47(10):12-16.]

TN915.04

A

1003-3106(2017)10-0012-05

2017-05-19

國家自然科學(xué)基金資助項(xiàng)目(61362006,61571143)；廣西無線寬帶通信與信號處理重點(diǎn)實(shí)驗(yàn)室基金資助項(xiàng)目(GXKL061501)；廣西自然科學(xué)基金資助項(xiàng)目(2014GXNSFBA118288)。

湯杰男，(1992—)，碩士研究生。主要研究方向：無線傳感網(wǎng)絡(luò)。鄭霖男，(1975—)，教授，碩士生導(dǎo)師。主要研究領(lǐng)域：超寬帶通信、無線傳感器網(wǎng)絡(luò)、移動通信、自適應(yīng)信號處理、擴(kuò)頻通信。