一种改进的无线传感器网络密度自适应冗余节点调度算法

何少尉

（浙江邮电职业技术学院，浙江 绍兴 312366）

0 引 言

无线传感器是一种自带能源并基于某种通信协议进行通信，能够实时感知环境参数并传输至终端客户的小体积传感器[1]。无线传感器网络（Wireless Sensor Networks，WSN）是基于无线通信技术将无线传感器自由组织而成的分布式网络，具有组网灵活、覆盖广泛、环境适应性强等优点，在军事、环境监测、医疗等众多领域得到了广泛应用[2-3]。在WSN中，所有节点的组织都是随机的，这会导致部署节点数量远远大于所需数量，导致某些节点的感知区域互相重叠。若网络中所有节点同时运行，节点之间存在许多重叠区域，这不仅损耗大量的能量，而且会增加数据冲突及其融合的复杂性[4]。此外，由于传感器节点的能量均为受限状态，当网络部署完毕后，节点的能量补充较为困难[5]。因此，降低节点的能耗，对于延长WSN的生存时间有着非常重要的价值[6]。节点休眠调度是WSN降低能耗、延长生存时间的有效途径，其基本思想是利用WSN中节点的冗余性，使WSN中部分节点保持活跃，部分节点保持休眠，以充分提高节点的能源利用率，延长网络的生存时间[7]。在节点休眠调度算法中，传感器节点首先判断自己是否为冗余节点，并根据判断结果来决定自己何时进入休眠状态。因此，对节点休眠调度算法研究的主要目的是在确保整个网络的覆盖区域和连通性的同时，保持更多数量的节点处于休眠状态。

目前，人们对节点休眠调度算法进行了大量的研究。文献[8]提出Ditian算法，利用各节点间的互相通信，判断邻居节点能否覆盖其感知区域，并决定本节点是否休眠，以达到休眠的目的。文献[9]提出基于数据相似度的节点休眠调度策略，能从冗余节点的不同聚类来筛选休眠节点。文献[10]提出一种树型协议，通过创建成对的节点，在节点间进行休眠模式切换。文献[11]提出一种与节点位置无关的节点休眠调度算法。文献[12]提出一种基于动态能量感知的节点休眠调度算法。上述算法均从某个特定角度对WSN中节点的休眠调度进行了研究，本文针对Ditian算法对WSN节点低密度状态下效果不佳的不足，提出一种改进的密度自适应冗余节点调度算法。

1 Ditian算法简介

节点休眠调度方法是让不需要工作的节点进入休眠状态，在“侦听”“休眠”模式之间不断切换，使传感器节点轮换工作。这样可以增加网络使用时间，提升节点能量效率。

传感器节点处于休眠状态时能量损耗最少。以某传感器网络中某个节点为例，该节点在一个周期内发送、接收、空闲和休眠状态时的能耗对比如图1所示。可以明显看出，节点在休眠状态时的功耗仅为空闲状态的很小一部分，在覆盖率和连通度不发生变化的前提下，可以通过提高节点进入休眠状态的数量来实现能量的低消耗，用节点间相互的交替工作来减少网络的能耗。节点休眠调度算法一般通过合理的资源调度算法，尽可能增加节点的休眠时间，减少节点的发送、接收和空闲时间。Ditian算法就是节点休眠调度算法的一种。

图1 传感器节点能量消耗情况

Ditian算法的前提是有一个节点被周围节点全覆盖。若存在节点v，与其邻居节点u集合满足N(v)={v|d(u,v)≤rs}，则称节点v称为冗余节点。式中，rs是门限距离，d(u,v)表示节点u到节点v的欧几里得距离，可表示为

式中：(xu,yu)、(xv,yv)表示节点u、v的坐标。

如图2所示，对于节点A而言，被周围节点B覆盖的区域为弧P1B1P2和弧P1A1P2相交的地方。由图中几何关系可知，节点间的重叠面积不易计算，而扇形P1B1P2的面积不难计算。为使计算简单，只需计算扇形P1B1P2对应的圆心角∠P1AP2取值在[0,2π)中，即可认定该节点为冗余节点。

图2 冗余节点判断示意图

因此，Ditian算法中，首先计算节点与基准轴的夹角，当该节点与周围邻居节点的角度在[0,2π)时，即认为该节点为冗余节点。

式中：βui→v表示从集合N(v)中节点ui与节点v之间的夹角。

如图3所示，节点A被节点B，C和D覆盖，∠BAC+∠CAD+∠DAB=2π。按照Ditian算法，节点A不是冗余节点。对于节点A的错误判断，导致最终判断出的冗余节点数目偏少。在Ditian算法中，节点在被覆盖时，采用夹角判定。但Ditian算法具有一定的局限性，仅适用于半径范围内的节点，只能得到比较小的冗余节点集合。因此，Ditian算法是节点密度较高的情况下的首选。而在节点密度较低的情况下，Ditian算法的效果将会受到严重影响。

图3 扇区覆盖误差示意图

2 改进的密度自适应冗余节点调度算法

针对Ditian算法对探测区域内低密度不适用的情况，本文提出一种改进的密度自适应冗余节点调度算法，利用最少节点覆盖全部检测范围，降低节点部署的数目。

2.1 密度自适应冗余节点调度算法

在WSN中，若某节点检测的范围内节点数目过多，即节点密度过大，仅需较少的周围节点就能判断出覆盖节点。相反，若节点的密度过小，则需要检查节点监测范围外的周围节点。故节点的密度大小和分布方式对于WSN内节点的调度有着重要价值。本文提出一种改进的密度自适应冗余节点调度算法，可以依据不同的节点密度自适应冗余节点调度算法。此算法能够有效地降低检测范围外的节点个数，并根据节点密度执行节点休眠。

假定WSN中全部节点的功能结构均相同，通信和监测范围均为圆形。令监测直径为通信半径的一半，利用定位系统确认出节点位置。算法的流程如下。

（1）系统初始化，节点vi传送位置、能量信息给其周围节点Ni={vj|d(vi,vj)＜2rs,vj＜Ni}。

（2）获取周围节点数据，确立周围节点表，将节点从近到远排列。

（3）把周围节点表上的节点分类：Ni1={vi1|d(vi1,vj)＜2rs,vi1＜Ni}，Ni2={vi2|d(vi2,vj)＜2rs,vi2＜Ni}。

（4）STEP4：当Ni1∈ϕ，即节点vi监测的范围内没有周围节点，则判断不可以覆盖此节点，算法结束。如果节点监测的范围C(v)内没有周围节点，由于圆心很难被覆盖，所以C(v)不能全部被覆盖。

（5）当Ni1∈φ，从近到远检查vi范围内的周围节点，推测此节点与周围节点的覆盖角。如图4所示。

图4 vi半径内的邻居节点

计算得知：

式中：α是vj、vi与X轴之间的夹角，(xvj,yvj)是vj的坐标，(xvi,yvi)是vi的坐标。

式中：β是vj、vi与B之间的夹角，dvi→vj是vi到vj的距离，rs是节点覆盖圆的半径。

上述中覆盖的角度为[α-β,α+β]，由于α-β＜0，所以覆盖的角度是[0,α+β]∪[2π+(α-β),2π]。当节点vi全部检测范围内的周围节点将覆盖角全部覆盖时，此时节点应判定为冗余节点。

（6）当节点vi对检测范围的周围节点的覆盖角没有全部覆盖，只需算出节点Ni1与vi的相交点B、C，如图4所示，可以通过下面公式得出B、C的位置：

式中：rs是节点覆盖圆的半径，α是vj、vi与X轴之间的夹角，β是vj、vi与B之间的夹角。

节点vi对检测范围内周围节点的覆盖角没有全部覆盖，全部范围内至多4个相交点，坐标位置亦可由上式得出。

式中：rs是节点覆盖圆的半径，d(vj,B)是vj与B之间的距离，d(vj,C)是vj与C之间的距离。

（7）得出Ni3内部的节点vj覆盖在vi中的圆弧。这时把vj当作坐标系，再由第（5）步得出vi的圆弧。

（8）节点vj将会检查Ni内的节点，来判断vi有没有覆盖vj。当Ni3内全部节点在vi内部的圆弧全都覆盖，则判断vi是全覆盖节点。

（9）全部判断为全覆盖节点会向周围节点递送休眠信号，在此过程中，可能会导致一些地区不能覆盖，所以需要在任一全覆盖节点设置一段延迟，当在延迟时没有接收到休眠信号，就会执行休眠操作；当在延迟时收到休眠信号，则会去除此节点，然后再次检测周围节点是否被全部覆盖。

2.2 算法流程图

根据上述算法过程，可以得到密度自适应冗余节点的判定算法流程图，如图5所示。

图5 密度自适应冗余节点调度算法流程图

3 仿真结果与分析

3.1 仿真环境

本节利用Matlab软件来实现仿真。假设N个节点均匀存在于一个面积为100 m×100 m的正方形内，L取100，N分别取100、200、300、400、500、600、700、800和900九个值。假设单个节点的监测范围是直径为20 m的圆，通信半径与探测直径一致，即20 m。

3.2 实验结果

3.2.1 节点总数与活跃节点数关系

节点总数与活跃节点数目关系如图6所示，随着系统中网络节点密度的增加，Ditian算法和改进的算法所需要的活跃节点数量均上升。但与Ditian算法相比，改进的算法所需要的活跃节点数较少。这表明在同等的网络节点密度时，改进的算法所需系统中活跃的节点数量较低，可有效降低系统中节点的能耗。

3.2.2 节点总数与节点寿命的关系

节点总数与系统寿命的关系如图7所示。与Ditian算法相比，改进的算法网络寿命显著延长。此外，在Ditian算法下，系统中节点总数的变化对系统的网络寿命影响不大，而改进的算法与节点总数呈现出正相关的关系，随着网络节点总数的增加，网络寿命越长。

4 结 语

节点能耗对无线传感器网络的安全可靠运行有着非常重要的作用。节点在运行过程中，收发信息时的能量消耗最大，休眠时的能量消耗比较低。因此，通过对节点休眠来降低节点能耗，能有效延长WSN的生存时间。本文分析了Ditian算法存在的不足，提出了一个改进的密度自适应休眠调度算法，能在不同的环境变量下，合理选择节点进行休眠，有效降低算法复杂度和节点冗余度。仿真结果显示，改进后的算法有效降低节点的平均能耗，延长系统的生存时间。