基于企鹅过冬行为的提高网络寿命算法性能分析

陈中良，程　磊

（黄淮学院，河南驻马店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