基于能量探测的WSN节点调度算法研究*

郑学伟

（1.辽宁广播电视大学，沈阳110034；2.辽宁装备制造职业技术学院，沈阳110161）

基于能量探测的WSN节点调度算法研究*

郑学伟1，2*

（1.辽宁广播电视大学，沈阳110034；2.辽宁装备制造职业技术学院，沈阳110161）

针对无线传感器网络在节点传输过程中的延迟与链路质量问题，设计一种基于能量探测的节点休眠调度算法EAS，通过对节点插入苏醒时隙来减小端到端之间的延迟，并根据每个节点的剩余能量值进行能量探测，使整个网络中各节点的能量相对均衡地消耗，在保证传输质量的基础上达到延长网络的生命周期的目的。实验结果表明，对比现有算法，EAS算法能够在保证使WSN网络在延迟一定的情况下明显降低能耗，延长整个网络的工作寿命。

WSN；传输延迟；节点休眠调度；能量探测

无线传感器网络WSN（Wireless Sensor Networks）是由在一定区域内大量部署的微型传感器节点组成的，将被监控对象的监测信息发给监控者，集中了传感器技术、分布式处理技术及嵌入式技术，是一种自组织多跳的无线网络［1］。由于WSN的节点采用电池供电，能量寿命一直是WSN生存周期中的核心问题。如何降低WSN在传输过程中的能耗，最大限度地延长节点的使用周期进而延长整个WSN的生存时间一直研究者关注的焦点。目前的研究主要集中在硬件设计和电源管理方面。通过改变节点占空比技术来节省能量是近一年新兴起的研究方向［2］。降低节点的占空比可以有效地延长节点的使用寿命，但是降低占空比会导致整个WSN在传输过程中延迟增大，只有有效地降低节点传输过程中的延迟才能保证低占空比节点的WSN达到预期的性能指标。传统的降低延迟算法往往忽略链路质量的因素，对节点能量的变化没有进行深入的研究。目前，国内外的一些学者也针对节点剩余能量和链路质量等问题提出了一些解决方法。ESC协议［3］通过引入一个透明的中间件来最大程度减小网络传输延迟，从而延长节点寿命。MMSPEED提出了一种多路径多速度的路由协议用来在一定程度上保证网络的链路质量［4］。PTW（Pipelined Tone Wakeup）［5］介绍了一种在能耗节省和端到端延迟之间的平衡方法。Gu［6］等人提出了SDC算法，SDC算法能够在特定条件下控制延迟，节省节点的能量消耗。但是，该算法仍然存在着一些不足之处，如并没有考虑链路质量可能引起的数据重传，从而导致节点间的传输延迟增大。

本文提出了基于能量检测的节点休眠调度算法EAS（Energy-Aware based Scheduling Scheme），通过对节点插入苏醒时隙来减小端到端之间的延迟，并根据每个节点的剩余能量值进行能量探测，从而有效地避免节点过早死亡，使整个网络中各节点的能量相对均衡地消耗，延长网络的生命周期。

项目来源：辽宁省教育厅科技项目（L2014579）；辽宁省现代远程教育学会重点课题项目（2014XH02-12）；国家开放大学规划课题项目（G14A0602Y）

收稿日期：2015-06-15修改日期：2015-08-12

1　系统模型

1.1网络模型

一个已经部署完成的WSN系统中的节点一般处于工作和休眠两种状态，处于休眠状态的节点关闭除定时以外的一切功能，而处于工作状态的节点将提供感知、侦听与数据通信功能。

节点i的一个工作周期是由工作和休眠两种状态组成的集合Γi，假定T为节点i的一个周期持续的时间，用数组表示节点i在第 j次的工作状态，式中tij表示第 j次的工作状态的开始时间；τ表示该次工作状态持续的时间，即时隙个数，整个周期T时隙大小固定，节点i在周期T中苏醒的次数为n，则节点i的一个周期工作调度表，见式（1）。

节点占空比DC（Duty Cycle）指的是传感器节点i在周期T中处于工作状态所花费的时间同整个周期的比值，用DCi表示节点i的占空比，根据式（1）得出：

图1表示了节点i的一个工作周期，一个方框表示一个时隙，周期T为10个时隙。图中用阴影代表节点的工作状态，空白代表节点的休眠状态，因此，可以计算出节点i在一个工作周期内的工作调度表为，从而可以算出节点i的占空比为DCi==40%。

图1　节点工作调度表

1.2传输延迟

当一个普通的WSN中所有节点都处于工作状态时，相邻节点间可以随时发送或接收信息，节点的数据延迟一般是毫秒级。但是当处于一个低占空比的WSN中时，由于有相当数量的节点处于休眠状态，节点间传送数据的延迟可能是几秒甚至是十几秒。我们将节点数据传送时所等待的时间定义为休眠延迟，由于在低占空比的WSN数据传输中由于休眠节点产生的数据延迟要远远大于正常通信的数据延迟，我们在算法设计时忽略不考虑通信延迟。考虑问题的关键是链路数据传输的质量，不考虑链路质量的话，延迟计算比较简单，直接计算数据传输时的休眠延迟之和即可，考虑链路质量则比较复杂，由于数据传输可能失败，则要考虑到数据重传带来的传输成本。

1.2.1不考虑链路质量

图2所示的传输网络中，有A，B，C 3个传输节点，3个节点的工作周期都为10τ，τ取值为1 s。节点A的工作调度是，同理可知。如果用dij（）t表示发送节点i在时间t收到数据信息，然后将该数据信息发送给其邻居节点 j的休眠延迟，Dij（t）表示非相邻节点i，j的休眠延迟，那么可以计算出节点A和节点B之间的休眠延迟为dAB（1）=（4，1）·τ=3×1=3 s，则可以计算出DAc（1）=8 s。

图2　不考虑链路质量的网络传输模型

1.2.2考虑链路质量

在实际的工作环境中，WSN节点数据传输的链路质量不可能是100%，我们假定pij为节点i到j之间的链路质量，nij节点i到j之间数据传输的重传次数，若重传次数大于最大重传次数nmax则将数据包丢弃，如图3所示，假设一个WSN的T为100 s，nmax=3（本文以下的例子中都采取以上数据假设）。假设节点A至B的数据传输链路质量为pAB=0.8，节点B至节点C的数据传输链路质量为pBC=0.6，则节点A到节点C之间端到端的休眠延迟DAc（1）的期望值为：

图3　考虑链路质量的网络传输模型

仅仅是在链条路径的运算中，在考虑链路质量因素后，节点A至节点C的休眠延迟就由8 s增长到约81.64 s，整整增长了10倍，可见随着网络传输过程中节点跳数的增加，休眠延迟的增长将是几何级数的增加。

2　算法设计

EAS算法的核心思想是：针对WSN链路传输过程中的能量消耗问题，增加节点苏醒时隙的次数进行节点休眠调度，在进行节点休眠调度的同时进行以保证能量探测使得网络均匀地消耗能量，从而延长网络的工作时间。能量消耗最小。

2.1节点休眠调度算法

2.1.1节点相邻

由于在链路质量不可靠的WSN中延迟大而不能够满足实际的应用，图4中，节点A向节点B传输的休眠延迟期望值约为69.02 s，在节点B增加一次苏醒时隙后，休眠延迟期望值值变为11.55 s，延迟降低83%。

对于WSN中邻居节点i和 j，节点j在增加一次苏醒时隙后其工作周期由Γj=｛｝时，如果此时+1，则新的延迟期望值如式（4）所示。

图4　增加苏醒时隙减小延迟

但是一味的增加节点的苏醒时隙次数会大大增加节点的能量消耗，算法的关键在于取得增加的苏醒时隙次数与能量消耗的平衡，即在增加苏醒时隙次数最少的情况下达到符合要求的数据传输延迟。算法设计的关键在于节点间休眠延迟的计算。假定节点i在t时刻收到数据包并准备发送给节点 j，中间跳数为m，达到理想休眠延迟期望值时所需的苏醒时隙次数为h次，h≤m，首先根据节点i到 j计算出延迟期望值。若，即延迟期望值小于等于实际延迟值B，满足实际应用需要，停止计算。若，即延迟期望值大于实际延迟值B，则继续运算，逐步对苏醒时隙增加，每增加一次重新计算延迟期望值，直至满足，假设此时增加h=m次苏醒时隙，此时的h值最小，消耗的能量也最少。对于相邻节点i和j，可通过增加苏醒时隙减少休眠延迟，延迟期望值计算如下所示：

2.1.2节点不相邻

上节研究的是理想状况，即节点i和j相邻。现假设节点i和j不相邻，节点i向j发送数据的话须经过某条路径，假设须经过m-1跳节点。这样，对于节点j接收从节点i发送过来的数据可能会出现两种情况：

节点i和j相邻数据传输过程，存在节点1，如果节点1不增加苏醒时隙，则从节点1到节点j增加苏醒时隙h次；如果从节点1开始增加苏醒时隙，则从节点1到节点j增加苏醒时隙h-1次。根据以上分析，通过迭代计算节点i向j的延迟期望值为：

图5　EAS算法示意图

图5（a）为节点A到节点C初始休眠延迟期望值约为135.32 s，图5（b）增加一次苏醒时隙后能够取得的最小值为72.15 s，图5（c）增加两次苏醒时隙的值为38.22 s。

2.2能量探测

通过实际应用检测发现，在WSN网络中，由于实际应用环境很复杂，导致不同的节点对能量的消耗差异往往会很大。低能量值节点可能会比预期更早的失效，而每增加一个失效点都会大大降低整个WSN的性能，缩短WSN的生存周期。为保证WSN的效能与生存周期，需要在节点休眠调度算法的基础上增加能量探测，通过能量探测使能量值较低的节点尽可能的处于休眠状态，用Eavg表示网络平均能量，节点j自身的剩余能量用jEres表示。具体算法见式（7）。

式（7）中，α为动态权重值。当节点1要想增加苏醒时隙时，先将自己的剩余能量和网络平均能量进行比较，检测条件，只有当剩余能量大于α倍的网络平均能量时会增加苏醒时隙，否则按照原来的工作调度表工作。通过仿真数据测试，当α=1.2为宜。

图6中，假设节点B剩余能量不足，不考虑节点剩余能量的情况下，节点A到节点C的休眠延迟期望值约为］≈45.8 s。考虑节点剩余能量，节点B不动而节点C增加苏醒时隙，得到］≈80.7 s，根据结果可得网络中延迟期望值变大，但是网络生存周期却得到延长。

图6　EAS能量探测过程

3　仿真实验与性能评价

3.1EAS算法性能仿真

为验证EAS算法的性能，我们在延迟要求分别为1 000 s、700 s、400 s、100 s和10 s的情况下对算法进行验证，在0～1之间每次产生一个随机数，如果该数值不小于链路的质量则表示传输成功，小于则传输失败，每次增加苏醒时隙的仿真次数为50次，实验结果如图7所示。

由图7可得，不同的延迟条件对实验结果有较大的影响，但如果延迟条件一定的话，随着苏醒时隙次数的增加，满足条件的百分比会迅速提高，以延迟要求为1 000 s为例，当苏醒时隙增加1次时满足条件的百分比约为53.31%，苏醒时隙增加2次时满足条件的百分比约为79.84%，苏醒时隙增加3次时满足条件的百分比约为91.2%，但当延迟要求缩短为10 s时，已经很难通过增加苏醒时隙来提高满足条件的百分比。

图7　EAS算法在不同延迟要求下满足条件百分比

3.2不同参数对算法性能的影响

本节对不同条件下的EAS［7］算法和TOSS算法［8］就前面指出的标准进行仿真实验已验证算法性能。

3.2.1延迟要求的影响

在EAS算法中，为满足不同要求的延迟值，苏醒时隙次数需要不同程度的增加，但是随着苏醒时隙次数的增加，网络的生存周期也会受到不同程度的影响。在不同的延迟值下，EAS和TOSS算法两种算法的仿真结果如图8所示。

由图8（a）可以看出，随着延迟要求的增大，为满足该要求值而要增加的苏醒时隙次数最小值会随之减小。这是因为随着要求延迟增大，只需要增加很少的几次苏醒时隙就能满足。但是在相同延迟要求的情况下，EAS算法比TOSS算法要增加的苏醒时隙次数少。比如说延迟要求值在800 s的情况下，EAS算法要增加的苏醒时隙次数最小值为9次，而TOSS算法要增加的苏醒时隙次数最小值为11次，EAS算法较TOSS算法要增加的苏醒时隙次数最小值较少了18%。在要求的延迟值为500 s的情况下，TOSS算法要增加的苏醒时隙次数最小值为17次，而EAS算法要增加的苏醒时隙次数为15次，EAS算法仍比TOSS要增加的时隙小。EAS算法比TOSS算法要增加的苏醒时隙次数少，就表明EAS算法使节点在更多的时间内将会处于休眠状态，从而可以节省节点能量消耗，延长网络的工作寿命。由图8（b）可以看出，随着要求的延迟值减小，在EAS算法和TOSS算法下都会延长网络的生命周期。EAS算法比TOSS算法在差距最大时延长46%的生命周期，在差距最小的情况下也会延长27%的生命周期。

3.2.2节点占空比的影响

节点占空比对休眠延迟期望值和节点能量消耗都会产生明显的影响，也将会影响要增加的苏醒时隙次数最小值和网络生命周期。本次仿真在固定延迟要求条件下，考察节点占空比对EAS算法性能的影响（如图9所示）。

从图9（a）的仿真结果可以看出，随着节点占空比越来越高，要满足给定延迟要求所需增加的苏醒时隙最小值也会减少。在同一占空比下，EAS算法比TOSS算法要增加的苏醒时隙次数最小值要小。在占空比为2%的情况下，EAS算法要增加的次数最小值为12次，而TOSS算法则需要15次。EAS算法和TOSS就需要增加的次数最小值相比，根据仿真结果，在最好的情况下，EAS算法将比TOSS少60%左右。随着节点占空比越来越高，网络的生命周期会显著下降，这是因为节点处于空闲状态的时间会越来越多。在节点占空比从1%～5%变化的过程中，使用EAS算法比TOSS算法更能够延长网络的工作时间。在最好的情况下延长近42%，在最坏的情形下也会比TOSS算法延长21%的生命周期。

图8　延迟要求的影响

图9　节点占空比的影响

4　结束语

针对低占空比无线传感器网络中链路质量不高、延迟大等特点，提出了EAS算法。该算法在考虑链路质量的基础上，使得网络能够在满足一定延迟要求的情况下所消耗的能量最小；同时加入能量探测技术，使得节点能够均匀地消耗能量，从而延长网络的工作时间。EAS算法可以为限定延迟下的节点休眠调度算法提供研究基础，同时，在通过能量探测来延长网络生命周期方面提供思路。实验结果表明，对比现有算法，EAS算法能够在保证WSN网络延迟一定的情况下能够明显降低能耗，可以延长整个网络的工作寿命。

［1］ 高建良，徐勇军，李晓维.基于加权中值的分布式传感器故障检测［J］.软件学报，2007，18（5）：1208-1217.

［2］ 闫丹，雷霖.基于免疫神经网络的无线传感器网络节点的故障诊断［J］.自动化信息，2009，95（3）：37-39.

［3］ 邢倩，郝鹏，刘维亭，等.基于WLSE-KF的传感器融合定位算法研究［J］.电子器件，2014，37（6）：1199-1203.

［4］ 托乎提努尔，陈曙.一种无需测距的无线传感器网络定位算法研究［J］.电子器件，2013，36（4）：527-530.

［5］ 胡中栋，谢金伟.基于近似投影校正的无线传感器网络三维定位机制［J］.传感技术学报，2014，27（11）：1573-1577.

［6］ Perspective MLAP.Machine Learning：A Probabilistic Perspective ［J］.The MIT Press，2012：348-352.

［7］ Chang C，Lin C，Hsieh C，et al.Patrolling Mechanisms for Disconnected Targets in Wireless Mobile Data Mules Networks：Parallel Processing（ICPP）［C］//2011 International Conference on.2011，93-98.

［8］ 吴凡，彭力.基于节点密度及路径优化的无线传感器网络定位算法研究［J］.传感技术学报，2014，27（11）：1539-1544.

郑学伟（1979-），男，满族，辽宁抚顺人，辽宁广播电视大学副教授。硕士，研究方向为无线传感器网络、移动通信。

WSN Nodes Scheduling Algorithms Based on Energy Detection*

ZHENG Xuewei1，2*
（1.Liaoning Radio and TV University，Shenyang 110034，China；2.Liaoning Vocational and Technical College of Equipment Manufacturing，Shenyang 110161，China）

During the process of node transmission，an energy-aware based scheduling scheme（EAS）can be designed against the delay and link quality problem in WSN.Through inserting time slot into the node，the port-to-port delay can be reduced；in the meanwhile，the remaining energy value of each node can be detected，thereby relatively consuming the energy of each node in the network on a balanced basis，and extending the network lifecycle on the premise of ensuring the transmission quality.Test finding shows that EAS scheme can significantly reduce energy consumption by stabilizing WSN delay，thus extending the working life of entire network.

WSN；delay transmission；node scheduling scheme；energy detection

TN923

A

1005-9490（2016）03-0581-05

EEACC：6150P10.3969/j.issn.1005-9490.2016.03.016