基于企鵝過冬行為的提高網(wǎng)絡(luò)壽命算法性能分析

陳中良，程　磊

（黃淮學院，河南駐馬店463000）

?

基于企鵝過冬行為的提高網(wǎng)絡(luò)壽命算法性能分析

陳中良，程磊

（黃淮學院，河南駐馬店463000）

摘要：由于傳感節(jié)點能量供應(yīng)受限，為延長無線傳感網(wǎng)絡(luò)（wireless sensor networks，WSNs）壽命，提出基于能量消耗率的節(jié)點位置對調(diào)（energy consumption ratio-based node rotation，ECRNR）方案。ECRNR方案將能量消耗率高的傳感節(jié)點位置由多個傳感節(jié)點輪流駐守，即由多個傳感節(jié)點一起分擔任務(wù)，避免由單一傳感節(jié)點獨自承擔繁重任務(wù)而能量過早耗盡。仿真結(jié)果表明：提出的ECRNR方案能夠有效提高網(wǎng)絡(luò)壽命，與傳統(tǒng)的方案相比，網(wǎng)絡(luò)壽命得到有效提高。

關(guān)鍵詞：網(wǎng)絡(luò)壽命；能量消耗；移動；無線傳感網(wǎng)絡(luò)

0　引言

無線傳感網(wǎng)絡(luò)（wireless sensor networks，WSNs）在棲息地監(jiān)控[1]、環(huán)境監(jiān)控[2-3]以及監(jiān)視系統(tǒng)[4]（surveillance systems）等領(lǐng)域應(yīng)用廣泛。這些應(yīng)用需要收集大量數(shù)據(jù)，并向信宿Sink傳輸，因此需長期保持工作狀態(tài)。然而，WSNs內(nèi)節(jié)點是基于有限能量供應(yīng)，如電池，并且WSNs部署于野外環(huán)境，極難第2次充電或替換電池。一旦能量消耗，傳感節(jié)點就無法工作，影響整個WSNs工作時間，即縮短了網(wǎng)絡(luò)壽命（network lifetime）。在這種情況下，為了延長網(wǎng)絡(luò)壽命，只能合理地利用傳感節(jié)點的能量。為此，WSNs應(yīng)用的最大挑戰(zhàn)就是：如何有效地管理節(jié)點能量消耗，以最大化整個網(wǎng)絡(luò)壽命。

研究證實，限制傳感節(jié)點移動，即受控移動（controlled mobility）方案能夠有效地提高WSNs能量消耗效率，如調(diào)整移動節(jié)點位置[5-8]、調(diào)整網(wǎng)絡(luò)通信拓撲結(jié)構(gòu)[8-11]。

企鵝常處于-45℃低溫環(huán)境，為了能共同抵御寒冷，需抱成一團，體弱的小的在中間，大的、體質(zhì)好的在外圈，并且輪流互換位置。通過這種方式共同承擔防御寒風的任務(wù)。同樣地，在WSNs中，處于不同位置的傳感節(jié)點承受的任務(wù)不同，相應(yīng)傳感節(jié)點的能量消耗率不一，有些傳感節(jié)點能量消耗率快、有些慢。如靠近Sink節(jié)點承擔更多的轉(zhuǎn)發(fā)數(shù)據(jù)任務(wù)，相應(yīng)地，其能量消耗率較快。能量消耗快的位置，類似企鵝蜷縮一團的外圍。受企鵝行為的啟發(fā)，本文提出一種新的傳感節(jié)點控制方案，由多個傳感節(jié)點輪流駐守能量消耗快的位置，共同分擔繁重的任務(wù)，保存?zhèn)鞲泄?jié)點能量，最終實現(xiàn)提高網(wǎng)絡(luò)壽命的目標。

如圖1所示，傳感節(jié)點s1、s2和s3能量消耗比其他的傳感節(jié)點能量消耗率更高。節(jié)點s1、s2消耗了大量的能量，因為它們有大量的子節(jié)點（descendants），這些子節(jié)點需要節(jié)點s1、s2向Sink節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。節(jié)點s3消耗了大量的能量，由于其遠離父節(jié)點s1，遠距離傳輸數(shù)據(jù)能量消耗大。針對這種情況，可利用調(diào)整移動位置，即將不同的節(jié)點輪流移動到能量消耗高位置上。例如，將s1所在的位置與s8互換、s2所在的位置與s7互換、s3所在的位置與s5互換。這樣的話，能量消耗高的位置由兩節(jié)點而不是一個節(jié)點承擔，以提高網(wǎng)絡(luò)壽命。

為此，提出基于能量消耗率的節(jié)點位置對調(diào)（energy consumption ratio-based node rotation，ECRNR）方案。ECRNR方案規(guī)定何時移動、哪些節(jié)點移動以及每個節(jié)點向何地移動，依據(jù)傳感節(jié)點的能量消耗率進行節(jié)點位置移動。任務(wù)繁重位置由多個傳感節(jié)點輪流駐守、共同分擔任務(wù)，從而合理有利用傳感節(jié)點能量，提高網(wǎng)絡(luò)壽命。

1　問題描述

假定網(wǎng)絡(luò)內(nèi)有N個傳感節(jié)點si，i=1，2，…，N。傳感節(jié)點si的位置為pi，i=1，2，…，N。假定每個傳感節(jié)點初始能量為E。傳感節(jié)點si的電量壽命為t（si），整個網(wǎng)絡(luò)壽命為T。網(wǎng)絡(luò)壽命T等于網(wǎng)絡(luò)內(nèi)傳感節(jié)點電量壽命最小的值：

WSNs中位于不同位置的傳感節(jié)點承擔的任務(wù)不同，如圖1所示，相比其他傳感節(jié)點，s1承擔s2、s3、s6以及s7、s8向Sink傳輸數(shù)據(jù)的任務(wù)，因此，其能量消耗速度快，即能量消耗率高。而傳感節(jié)點s6、s7、s8的任務(wù)比較輕，相應(yīng)地，能量消耗速度慢，能量消耗率低。假定s1的電量壽命t（s1）=30h，而s8的電量壽命t（s8）=100h。若不采取合理措施，整個網(wǎng)絡(luò)壽命只有T=30h。

由于傳感節(jié)點的能量是一定的，要延長電量壽命，只能合理、高效地利用傳感節(jié)點的有限能量。因此，在不影響傳感節(jié)點完成任務(wù)（收集數(shù)據(jù)、檢測異常情況）的情況下，只能將任務(wù)繁重的位置由多個傳感節(jié)點來完成，即由多個傳感節(jié)點輪流分擔任務(wù)，從而避免某個節(jié)點電量提前耗盡，以延長整個網(wǎng)絡(luò)壽命。

假定在時間t，設(shè)定L1（si，sj，t）為節(jié)點si與sj未交換位置的網(wǎng)絡(luò)壽命，如果節(jié)點si與sj交換位置后，網(wǎng)絡(luò)壽命為L2（si，sj，t）。若L2（si，sj，t）＞L1（si，sj，t），則認為可以將節(jié)點si與sj的位置交換，提高網(wǎng)絡(luò)壽命。

圖1　調(diào)整傳感節(jié)點位置示意圖

2　ECRNR方案

ECRNR方案的核心思想：能量消耗率高的位置由多個節(jié)點輪流駐守。

2.1臨界節(jié)點集

ECRNR方案中，首先計算臨界節(jié)點（critical nodes）。所謂臨界節(jié)點就是指其能量消息率（energy consumption rate，ECR）高于門限值lcr的節(jié)點，其位置需要調(diào)整。設(shè)Lcr為臨界節(jié)點集。信宿Sink收集其他節(jié)點的能量以及位置信息，并計算初始臨界節(jié)點集Lcr：

式中：λi——傳感節(jié)點si的能量消耗率；

lcr——判斷臨界能量消耗率的門限值。

由式（2）可知，只要傳感節(jié)點si的能量消耗率λi高于門限值，就納入Lcr集。計算門限值lcr采取平均化原則：其等網(wǎng)絡(luò)內(nèi)最小的能量消耗率lmin和最大能量消耗率lmax的均值，即lcr=（lmin+lmax）/2。

2.2對調(diào)合作節(jié)點的選取

ECRNR方案采取多輪對調(diào)位置。假定每輪對調(diào)傳感節(jié)點位置的時長為rs。在進行對調(diào)位置前，先選擇符合條件的對調(diào)合作節(jié)點（swap partner）。所謂對調(diào)合作節(jié)點就是指被選中與臨界節(jié)點對調(diào)位置的傳感節(jié)點。如圖1所示，s1為臨界節(jié)點，s8是其swap partner。

在每一輪對調(diào)位置中，每個傳感節(jié)點s執(zhí)行以下算法：

若節(jié)點s的ECR大于門限值lcr，為臨界節(jié)點，即s∈Lcr。首先，計算子節(jié)點集Ds，并要從Ds集中選擇一個節(jié)點與其位置進行交換。那么子節(jié)點s′∈Ds能夠被選中的條件如下：

1）在每輪中子節(jié)點s′沒有承諾與其他節(jié)點對調(diào)位置；

2）子節(jié)點s′離節(jié)點s最多有h跳的距離，h為門限值，單位為跳（hop）。

滿足上述兩條件的子節(jié)點成為候選節(jié)點（candidate nodes）。將候選節(jié)點納入候選節(jié)點集Cs。候選節(jié)點再將自己的信息，包括位置、能量消耗率ECR，發(fā)送給節(jié)點s。節(jié)點s依據(jù)這些信息，選擇一個節(jié)點，假定為s*。若s*滿足式（3）或式（4），便可成為節(jié)點s的swap partner。

或者：

式中：e、e*——節(jié)點s、s*的初始能量；

λ、λ*——節(jié)點s、s*的能量消耗率，并且λ＞λ*；

k——將節(jié)點從一個位置移到另一個位置所消耗的能量。

若候選節(jié)點中沒有合適的節(jié)點成為swap partner，那么節(jié)點s在本輪中不進行位置調(diào)整，選擇swap partner的算法流程如圖2所示。

2.3位置對調(diào)

已選擇了swap partner的節(jié)點進行位置調(diào)整，經(jīng)過一輪調(diào)整后，以類似的方式，開始新一輪。這種分布式選舉swap partner的方式降低了時鐘同步的要求。每個節(jié)點只需要知道能量消耗率ECR以及路由樹中的父節(jié)點以及門限值lcr。

最初，節(jié)點網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖3（a）所示，節(jié)點a，b，c位于樹的根上，能量消耗率高，納入Lcr集，成為臨界節(jié)點。為了延長網(wǎng)絡(luò)壽命，基于“順根摸藤”原則，需尋找swap partner與它們進行位置對調(diào)。如尋找節(jié)點a的swap partner時，首先找到以節(jié)點a為根的樹，然后沿著該樹找到其子節(jié)點e，若節(jié)點e?Lcr，將節(jié)點e作為節(jié)點a的swap partner。依據(jù)同樣的方法，分別找到節(jié)點b，c的swap partner，分別為j，k，并交換位置，如圖3（b）所示。隨后，準備第2輪對調(diào)位置，將節(jié)點e與節(jié)點i交換、節(jié)點j與節(jié)點q交換、節(jié)點k與節(jié)點m交換，如圖3（c）所示。

圖2　選擇swap partner的算法流程圖

3　數(shù)值仿真

為了評估ECRNR方案延長網(wǎng)絡(luò)壽命的性能，利用Matlab軟件建立仿真平臺，仿真區(qū)域為100m× 100m，傳感節(jié)點傳輸范圍為25 m。分別考察傳感節(jié)點數(shù)、初始電量E對網(wǎng)絡(luò)壽命的影響。

1）首先分析ECRNR方案中每輪對調(diào)傳感節(jié)點位置的時長r及門限值h參數(shù)的選取。先定義壽命提高率R：

仿真結(jié)果如圖4所示，ECRNR方案的壽命提高率隨r的增長而增長，當r增長到60 s時，趨于飽和狀態(tài)。再增長r，反而導(dǎo)致壽命提高率的下降。此外，h對壽命提高率也存在不少的影響，由圖可知，h=2hop時，壽命提高率達到最大。這是因為h?。╤= 1hop），離臨界節(jié)點近，其能量消耗也比較大，而h大（h=3 hop），距離比較遠，長距離移動節(jié)點本身消耗能量也比較大。因此，在仿真中選取r=60s、h=2hop。

圖3　基于能量消耗率的節(jié)點交換位置示意圖

將ECRNR方案與文獻[12]提出的EASR（energyaware sink relocation）方案以及文獻[13]提出了JMR （joint sink mobility and routing strategy）方案進行比較。

2）傳感節(jié)點數(shù)對網(wǎng)絡(luò)壽命的影響。電量E=1000J，傳感節(jié)點數(shù)在50，75，125，150變化。仿真結(jié)果如圖5所示。

由圖可知，在整個傳感節(jié)點變化范圍內(nèi)，本文提出的ECRNR方案的性能優(yōu)于JMR和EASR。JMR方案的性能最差。這是因為JMR方案僅考慮Sink節(jié)點移動，并且移動軌跡單一。此外，EASR方案優(yōu)于JMR方案，盡管EASR方案也僅移動Sink節(jié)點，但是移動軌跡不再是單一的，而是依據(jù)傳感節(jié)點能量變化。

圖4　ECRNR方案的壽命提高率隨r、h的變化情況

圖5　網(wǎng)絡(luò)壽命隨傳感節(jié)點數(shù)的變化情況

圖6　網(wǎng)絡(luò)壽命隨初始電量的變化情況

3）電量E對網(wǎng)絡(luò)壽命的影響。傳感節(jié)點數(shù)為100，電量E在500，750，1250，1500 J變化。仿真結(jié)果如圖6所示。

由圖可知，網(wǎng)絡(luò)壽命隨傳感節(jié)點的初始電量E的增加而上升。與JMR和EASR方案相比，本文提出的ECRNR方案性能最優(yōu)，并且隨著初始電量的增加，性能優(yōu)勢越明顯。其原因在于：ECRNR方案全局考慮網(wǎng)絡(luò)內(nèi)的傳感節(jié)點的能量消耗狀態(tài)，有針對性將能量消耗高的節(jié)點進行移動，使其不再承擔繁重的數(shù)據(jù)轉(zhuǎn)發(fā)，保存電池能量。

4　結(jié)束語

本文針對WSNs網(wǎng)絡(luò)壽命問題，展開分析，提出了基于能量消耗率的節(jié)點位置對調(diào)ECRNR方案。ECRNR方案受企鵝蜷縮和旋轉(zhuǎn)的過冬行為的啟發(fā)，將工作負擔重的位置由多個傳感節(jié)點輪流承擔，而不是由某一個節(jié)點承擔，從而提高整個網(wǎng)絡(luò)的傳感節(jié)點電量使用時間。ECRNR方案首先依據(jù)傳感節(jié)點的能量消耗率，其大于門限值的節(jié)點納入臨界節(jié)點集Lcr。Lcr內(nèi)的傳感節(jié)點，依據(jù)選擇swap partner的算法選擇自己的swap partner，并與其對調(diào)位置。仿真結(jié)果表明，提出的ECRNR方案有效地提高網(wǎng)絡(luò)壽命。

參考文獻

[1] SZEWCZYK R，MAINWARING A P. An analysis of a large scale habitat monitoring application[C]∥International Conference on Embedded Networked Sensor Systems. Association for Computing Machinery. Baltimore，2004：214-226.

[2] SUZUKI M，SARUWATARI S，KURATA N. A highdensity earthquake monitoring systemusing wireless sensor networks[C]∥Proceedings of the 5th international conference on Embedded networked sensor systems Association for Computing Machinery Sydney NSW Australia，2007：373-374.

[3] FILIPPONI L，SANTINI S，VITALETTI A.Data collection in wireless sensor networks for noise pollution monitoring[C] ∥Distributed Computing in Sensor Systems. 4th IEEE International Conference.Springer-Verlag.Santorini Island, 2008：492-497.

[4]胡峻峰，曹軍.基于Bete信譽系統(tǒng)的魯棒安全定位算法[J].計算機工程，2014，40（8）：116-122.

[5] ZITTERBART D，WIENECKE B，BUTLER J. Coordinated movements prevent jamming in an emperor penguin huddle[J]. PLoS，2011，6（6）：202-216.

[6] XU H，HUANG L，ZHANG Y，et al. Energy-efficient cooperative data aggregation for wireless sensor networks[J]. J. Parallel Distrib. Comput，2010，70（9）：953-961.

[7] WANGP，DAI RM，AKYILDIZ I F. Collaborative data compression using clustered source coding for wirelessmultimediasensornetworks[C]∥IEEE INFOCOM 2010 -IEEE Conference on Computer Com munications IEEE. San Diego，2010：2106-2114.

[8] LUO H，WANG J，SUN Y，et al. Adaptive sampling and diversity reception in multi -hop wireless audio sensornetworks [C]∥2010 IEEE 30th International Conference on Distributed Computing Systems. Genova：IEEE，2010：378-387.

[9] MOUKADDEM F，TORNG E，XING G. Maximizing data gather ing capacity of wireless sensor networks using mobilerelays [C]∥2010IEEE7thInternational Conference on Mobile Adhoc and Sensor Systems. IEEE Computer Society.San Francisco，2010：312-321.

[10] SHA M，XING G，ZHOU G. C -mac：Modeldriven concurrent medium access control for wireless sensor networks[J]IEEE Technology，2009，3（5）：1845-1853.

[11] LIU Y，LUO Z，XU K. A reliable clustering algorithm base on leach protocol in wireless mobile sensor networks[C]∥2010 2nd International Conference on Mechanical and Electrical Technology. IEEE Piscataway，2010：692-696.

[12] WANG C，SHIH J，PAN B. A Network lifetime enhancement method for sink relocation and its analysis in wireless sensor networks [J]. IEEE Technology，2013，45 （5）：45-52.

[13] DANTU K，RAHIMI M，SHAH H. Robomote: enabling mobility insensor networks[C]∥FourthInternational SymposiumonInformationProcessinginSensor Networks IEEE. Los Angeles：IEEE，2005：404-409.

（編輯：莫婕）

Penguin wintering behavior-based improved network lifetime algorithm performance

CHEN Zhongliang，CHENG Lei
（Huanghuai University，Zhumadian 463000，China）

Abstract:Limited energy supplies have made the extension of network lifetime one of the technical challenges for wireless sensor networks（WSNs）. Therefore，an energy consumption ratio-based node rotation（ECRNR）scheme has been proposed in this paper. The purpose of this scheme is to allocate more sensor nodes at the positions of high energy consumption in turns，that is to say，the relay information is shared by more than one sensor nodes to avoid early energy consumption. Simulation results show that the scheme has prolonged the lifetime of networks a lot compared with traditional schemes.

Keywords:network lifetime；energy consumption；rotation；wireless sensor networks

作者簡介：陳中良（1980-），男，河南方城縣人，實驗師，碩士，研究方向為軟件工程、計算機應(yīng)用。

基金項目：河南省科技發(fā)展計劃項目（132102210463）

收稿日期：2015-05-04；收到修改稿日期：2015-06-23

doi：10.11857/j.issn.1674-5124.2016.02.031

文獻標志碼：A

文章編號：1674-5124（2016）02-0136-05