基于企鵝過冬行為的提高網絡壽命算法性能分析

陳中良，程　磊

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

?

基于企鵝過冬行為的提高網絡壽命算法性能分析

陳中良，程磊

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

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

關鍵詞：網絡壽命；能量消耗；移動；無線傳感網絡

0　引言

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

研究證實，限制傳感節點移動，即受控移動（controlled mobility）方案能夠有效地提高WSNs能量消耗效率，如調整移動節點位置[5-8]、調整網絡通信拓撲結構[8-11]。

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

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

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

1　問題描述

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

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

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

假定在時間t，設定L1（si，sj，t）為節點si與sj未交換位置的網絡壽命，如果節點si與sj交換位置后，網絡壽命為L2（si，sj，t）。若L2（si，sj，t）＞L1（si，sj，t），則認為可以將節點si與sj的位置交換，提高網絡壽命。

圖1　調整傳感節點位置示意圖

2　ECRNR方案

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

2.1臨界節點集

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

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

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

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

2.2對調合作節點的選取

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

在每一輪對調位置中，每個傳感節點s執行以下算法：

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

1）在每輪中子節點s′沒有承諾與其他節點對調位置；

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

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

或者：

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

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

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

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

2.3位置對調

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

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

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

3　數值仿真

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

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

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

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

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

2）傳感節點數對網絡壽命的影響。電量E=1000J，傳感節點數在50，75，125，150變化。仿真結果如圖5所示。

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

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

圖5　網絡壽命隨傳感節點數的變化情況

圖6　網絡壽命隨初始電量的變化情況

3）電量E對網絡壽命的影響。傳感節點數為100，電量E在500，750，1250，1500 J變化。仿真結果如圖6所示。

由圖可知，網絡壽命隨傳感節點的初始電量E的增加而上升。與JMR和EASR方案相比，本文提出的ECRNR方案性能最優，并且隨著初始電量的增加，性能優勢越明顯。其原因在于：ECRNR方案全局考慮網絡內的傳感節點的能量消耗狀態，有針對性將能量消耗高的節點進行移動，使其不再承擔繁重的數據轉發，保存電池能量。

4　結束語

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

參考文獻

[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信譽系統的魯棒安全定位算法[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-），男，河南方城縣人，實驗師，碩士，研究方向為軟件工程、計算機應用。

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

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

doi：10.11857/j.issn.1674-5124.2016.02.031

文獻標志碼：A

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