基于邻居节点位置的无线传感网休眠算法

贾明伟，吴 敏，沙 超,2，王汝传,2

(1.南京邮电大学 计算机学院、软件学院，江苏 南京 210003；2.苏州大学 江苏省计算机信息处理技术重点实验室，江苏 苏州 215006)

基于邻居节点位置的无线传感网休眠算法

贾明伟1，吴 敏1，沙 超1,2，王汝传1,2

(1.南京邮电大学 计算机学院、软件学院，江苏 南京 210003；2.苏州大学 江苏省计算机信息处理技术重点实验室，江苏 苏州 215006)

在无线传感器网络中，节点往往以随机方式密集部署，从而易于产生大量冗余。文中在考虑网络覆盖率的前提下，提出了一种休眠调度算法。节点根据自己与邻居节点的位置关系，计算邻居节点对自己感知区域的覆盖程度。若邻居节点对自己的感知区域覆盖度超过给定的阈值，则节点进入休眠状态。仿真实验证明了算法的有效性，通过关闭网络中的冗余节点，节省了网络能量，延长了整个网络的生命周期；和同类算法相比较，算法检测冗余节点的能力明显优于同类算法，较大程度地减少了网络中的冗余节点。

无线传感器网络；休眠；覆盖冗余；邻居节点位置

0 引 言

在无线传感器网络中，节点的部署方式有两种：确定性部署和随机性部署。针对一些价值比较昂贵的无线传感器节点或者受限于特定的应用需求，无线节点多采用确定性部署;而针对一些价值比较低廉或者确定性部署无法完成的无线传感器网络环境，无线节点采用随机性部署[1]。在随机性部署的无线传感器网络中，为了保证节点完全覆盖目标范围，节点的密度往往很大,从而造成冗余[2-3]。判断出这些冗余节点，并将其休眠既可以节省网络的能量又能减少网络中信道冲突发生的概率。

无线传感器网络一经部署，节点往往不能移动，节点的电池也不可以替换，所以能量问题一直是无线传感器网络研究的热点。在满足覆盖率的前提下，让一部分节点处于休眠状态可以有效地节省网络的总体能量，从而延长整个网络的生命周期。

文中提出一种覆盖冗余节点判别算法(SALN)。传感器节点根据自己以及邻居节点的位置计算自己被邻居节点覆盖的程度，当节点被邻居节点的覆盖度达到预定阈值时，节点判定自己为冗余节点，从而进入休眠状态。

1 相关工作

当前的无线传感器网络休眠调度算法主要分为以下几类:第一类是根据网络的连通性判断节点是否需要休眠，在不改变网络连通性的前提下休眠冗余节点[4-5];第二类是基于距离的休眠调度算法，根据节点与簇头节点的距离，为节点设置不同的休眠概率[4];第三类是根据网络的覆盖率判断节点是否为冗余节点，在满足一定覆盖率的前提下，将部分节点休眠[6-11]。此外，还有根据实际的应用需求对节点进行轮转休眠调度，从而延长网络的生命周期。

在第一类休眠调度算法中，文献[4]首先将网络划分为一个个网格，网络中的节点可以和相邻网格中的任意节点通信，其次让网格中的节点轮转工作，以节省网络能量。文献[5]将拥有相同邻居的节点分在同一组中，在满足网络连通性的前提下，根据一定条件，将单独的节点加到一个组中或自己形成一个组，每个组中选一个节点工作，其余休眠。这类算法以网络的连通性作为判断依据，从而决定一个节点是否休眠。文献[6]是典型的第二类休眠调度算法，它将网络分簇，簇中节点根据与簇头的距离设置不同的休眠概率。在第三类休眠调度算法中，文献[7]提出了一种分布式的休眠调度算法。算法的基本思想是：初始时，网络中的每一个节点都是一个节点组，在保障覆盖度的前提下，相邻的节点组融合为一个节点组，直到节点组之间不能再融合，融合阶段结束后，算法在每一个节点组中选出1～2个节点处于工作状态，其余节点进入休眠状态。文献[8]提出一种轻量级部署调度算法，称为LDAS。算法先设计一个节点被它的n个邻居节点完全覆盖的概率，然后计算一个节点被它的n个邻居覆盖的区域占自身监测区域的百分比，基于这两个结果判断节点是否应该休眠。文献[9]在文献[8]的基础上，重点考虑了两个问题：一是大量节点同时休眠产生感知盲区问题；二是节点是否处于网络边界问题。文献[10]提出了一种面向异构无线传感器网络的节点休眠调度算法。首先根据邻居节点之间的距离对邻居节点进行分类，针对不同类型的邻居节点，算出满足覆盖率条件下所需此种类型邻居节点的最少个数，然后节点根据所有类型的邻居传感器节点的个数判断是否休眠。第三类算法主要是判断休眠一个节点后对网络覆盖率的影响，若一个节点休眠后对网络覆盖率无影响或影响很小，则判定为冗余。

此外，针对无线传感器网络的区域覆盖问题，Tian等[12]提出基于节点状态调度的分布式覆盖算法；Zhang等[13]提出分布式节点密度控制算法，根据节点邻居和自己的位置信息计算相互的覆盖关系；Y.Xu等[14]采用整数序列编码的遗传算法，找出网络的一个最小覆盖子集；M.Cardei等[15]用整数规划调节传感半径，用贪心算法找到K个覆盖子集；H.Chen等[16]把网络划分为网格，并用贪心算法找最小的覆盖子集。

综合上述各类休眠调度算法，文中选取第三类基于覆盖率的休眠调度算法作为研究点，重点关注休眠节点对网络覆盖率的影响。受文献[8,10]的思想启发，文中提出一种以邻居节点位置及间距来判断是否冗余的方法。在满足指定覆盖率的前提下，最大化休眠网络中的冗余节点。

2 网络模型及相关定义

2.1 网络模型

(1)为了满足连通性和覆盖率，节点以随机方式密集部署。

(2)节点的通信距离和感知距离相同。感知范围是以节点所在位置为圆心、感知距离为半径的圆。

(3)节点自带定位功能，暂时不考虑节点的定位问题。

(4)节点的能量受限，且一经部署不能移动，不能替换电池。

2.2 相关定义

(1)邻居节点。

网络中节点i的邻居集合定义为:

(1)

其中：ix为节点i的x坐标；iy为节点i的y坐标；R为传感器节点的最大感知距离。

(2)覆盖重叠区域。

假设网络中节点i有一个邻居节点j，两个节点的感知覆盖区域所形成的圆(以下简称感知圆)相交于P和Q两点，以节点i的感知圆的两条半径以及圆上的一段弧组成的扇形区域称作节点j对节点i的覆盖重叠区域，如图1中阴影部分所示。

(3)覆盖重叠区域圆心角。

节点j对节点i的覆盖重叠圆心角即为图1中的α角，其大小可由式(2)给出：

(2)

其中：r为两个节点之间的距离；R为节点感知圆的半径。

(4)覆盖区间。

假设节点的感知圆上的每一个点拥有一个弧度值，定义过圆心平行于Y轴与圆周相交的点的弧度值为0弧度，圆上其他点的弧度值按圆周上的逆时针方向依次增大。节点j在节点i上的覆盖区间定义为[q,p]，其中q为Q点的弧度值，p为P点的弧度值，Q、P为两感知圆的交点。

(5)节点的被覆盖率。

节点i的所有邻居节点覆盖区间的集合定义为：

(3)

举例说明，如图1所示，节点i有三个邻居节点，分别为节点j、h、g，节点j、h、g对节点i的覆盖重叠区域圆心角分别为α、β、γ，相应的覆盖区间分别为[q,p]、[e,f]、[c,d]。节点i的所有邻居节点的覆盖区间的并集为：

(4)

从图1可以看出，节点i的邻居节点的覆盖重叠区域占据了节点i感知区域的绝大部分。可简单认为只有锐角∠EiP(i为节点i的感知圆的圆心)所对应扇形区域未被节点i的邻居节点覆盖，其余部分全部被其邻居节点覆盖(实际上，节点i的未覆盖区域面积要小于∠EiP所对应扇形区域的面积)。此时节点i的被覆盖率为：

(5)

图1 节点被覆盖率计算

3 方法实现及分析

3.1 SALN算法实现

SALN算法分为三个阶段：节点初始化阶段、内部计算阶段和休眠调度阶段。

步骤1：节点初始化阶段。

传感器节点部署完成之后，每个节点向外界发送自己的坐标位置，同时监听邻居节点发送来的数据包，数据包包含邻居节点的x坐标和y坐标。

步骤2：节点内部计算阶段。

当通信完成之后，节点为每一个邻居节点保存一个坐标值。节点根据邻居节点的坐标值和自身的坐标值计算各个邻居节点的覆盖区间。计算完成后，节点将这些覆盖区间进行合并，并计算出节点被邻居节点的覆盖率。关于覆盖区间的计算，举例说明如下。如图1所示，若计算节点j在节点i上的覆盖区间，首先计算C点的弧度值。当节点i的x坐标值大于节点j的x坐标值时，c=β；当节点i的x坐标值小于等于节点j的x坐标值时，c=360-β。公式如下：

(6)

(7)

节点j在节点i上的覆盖区间为[q,p](p、q均在0～360之间)。q和p的值由式(8)和式(9)给出。

(8)

(9)

步骤3:节点休眠调度阶段。

节点根据计算得出的被覆盖率，同给定的阈值θ(0～1之间)相比较，从而确定自己是否为冗余节点。如果节点的被覆盖率大于θ，节点可以进入休眠状态；否则，正常工作。θ的值通常根据在网络实际运行时用户所要求的覆盖率进行设置。

3.2 时间复杂度分析

由SALN算法的实现过程可知，节点判断自己是否冗余所费时长主要和节点的邻居节点数量有关。若网络中节点的平均邻居数量为nnei，则SALN的时间复杂度为O(nnei)，由于节点的邻居节点个数必定小于节点总数n，故时间复杂度为O(n)。

4 仿真实验与分析

4.1 实验设置

用Matlab+Java进行仿真实验，通过改变网络规模、节点的被覆盖率阈值，从而观察网络休眠节点的数量、网络的总体覆盖率。由于节点部署的方式为随机性部署，故每次的实验结果不唯一。以下实验数据均是在同一实验参数条件下，重复10次的平均值。

4.2 算法自身对比实验

当在网络中撒播250个感知半径为10 m的节点时，增大网络规模，在不同的阈值下，网络达到休眠条件的节点数量如图2所示。

图2 不同条件下节点休眠个数对比

从图中可以看出,网络规模越大，满足休眠条件的节点数量就越少。因为网络规模越大，节点之间的平均距离就越大，节点的平均邻居数就越少，平均被覆盖率越小，从而造成休眠节点数减少。在同一网络规模下，被覆盖率阈值设置越大，休眠的节点数量也越少。因为被覆盖率阈值越高，满足覆盖率阈值条件的节点数就越少。

在150 m×150 m的区域内随机撒播250个和200个感知半径为10 m的节点时，网络初始化时的覆盖情况如图3(a)和(c)所示，图中灰色的区域为节点的感知区域，空白区域为未被节点覆盖的区域。图3(b)和(d)为节点调用完算法后网络的覆盖情况。

从对比图可以直观且明显地看出，调用算法后网络中冗余节点的数量大大减少了。

表1为在150 m×150 m的区域内随机撒播250个节点，当节点设置不同的被覆盖率阈值时，网络的总体覆盖率的变化情况，此时网络未运行算法时的覆盖率为93.9%。

图3 算法运行前后直观对比图

节点被覆盖率算法运行后覆盖率/%320/36093.39330/36093.62340/36093.9350/36093.9360/36093.9

从表1可以看出,当节点的被覆盖阈值设置为340/350、350/360时网络的总体覆盖率并无影响。此时满足休眠条件的节点个数分别为70以及53，休眠节点占总节点数的比值分别为28.0%和21.2%，也就是说在不改变网络原始覆盖率的前提下，执行算法后，可以减少网络中21.2%～28.0%的冗余节点。即使节点的被覆盖率设置为320/360，相比较未调用算法时，网络的总体覆盖率也只下降了0.61个百分点而已，而此时，休眠节点的占比可达到28.0%，由此可以看出文中算法的实用性和高效性。

表2为随机撒播250个以及300个节点时，网络的总体覆盖率随网络规模的变化情况。

从表中可以看出，并非网络规模越小，部署的密度越大，节点调用算法后网络的总体覆盖率就越大。当网络的规模过小，密度过大时，节点调用完算法后，网络的总体覆盖率反而会下降。造成这种现象的原因是若网络中的节点很密集，满足被覆盖率阈值的节点占比过高，从而大量的传感器节点进入休眠状态，使网络总体覆盖率降低。一种解决办法是：为网络中的节点设置一个休眠优先级。当节点在网络中依次休眠时，节点计算覆盖区间时就不会再考虑已休眠的节点，从而不会出现这种现象。当撒播250个节点，网络规模为100 m×150 m时，总体覆盖率出现最大值。此时的网络密度为100 m2内有1.67个节点。同时，当撒播300个节点，网络规模为150 m×150 m时,网络总体覆盖率达到最大值。此时的节点密度为100 m2内有1.33个节点。算法实际投入运行时，网络的节点密度应在1.33～1.67之间，这样监测区域才能达到最优覆盖。

表2 不同网络密度下算法执行后的覆盖率 %

4.3 SALN算法同其他算法的对比实验

下图为在不同实验条件设置下，SALN算法和Random算法、GBS算法、NDBS算法的对比实验图，得到不同网络覆盖率以及撒播不同节点数目对节点关闭率(休眠节点数占总节点数的比值)的影响。其中，Random算法是在保证特定网络覆盖率的情况下，随机性休眠网络中的节点。GBS算法是首先将网络划分为网格，针对每个网格中的节点，在保证覆盖率的前提下，随机休眠节点。在NDBS算法中，节点根据邻居节点的数量和指定的网络覆盖率判断自己是否是冗余节点，是否休眠[8]。

图4为在100 m×100 m的网络中撒播500个半径为10 m的节点时，节点关闭率随着网络覆盖率的变化情况。当网络的实际覆盖率在0.5～0.9[8]之间变化时，网络中节点关闭率呈下降趋势。由图4也可以看出，指定的网络覆盖率越高，满足关闭条件的节点数量也就越少。同时，在相同的网络覆盖率条件下，SALN算法的节点关闭率明显高于其他三种算法。

图4 不同覆盖率下节点关闭率的变化情况

图5是在100 m×100 m的网络中撒播不同数量的节点时，四种算法的节点关闭率的变化趋势图。此时节点的半径为10 m，网络覆盖率为0.8。当在网络中的撒播节点数量越多时，满足关闭条件的节点数量也就越多。从图5中也可以看出，当网络中节点的数目增加时，四种算法的节点关闭率均呈现上升状态。同时，在相同的节点数目下，SALN算法的节点关闭率要高于其他三种算法。

图5 不同节点数目下节点关闭率的变化情况

由图4、5可以看出，无论是改变网络的覆盖率还是在网络中撒播不同的节点数量，文中提出的SALN算法在四种关闭冗余节点的算法中有明显优势。

5 结束语

文中提出了一种基于邻居节点位置的覆盖冗余判别算法。节点只需知道网络中邻居节点的位置，即可判断自己是否冗余，减少了网络中的额外通信量，节省了网络能量消耗。仿真实验从网络规模、休眠节点数、被覆盖阈值等方面对SALN算法进行了验证和分析，计算出了网络部署时的最优部署值区间；同时从网络覆盖率和撒播不同数量节点将该算法同其他算法进行了比较，验证了该算法的关闭冗余节点能力。

在下一步工作中，将优化文中提出的算法，以防止网络中大量节点同时进入休眠状态。考虑经过计算后满足休眠条件的节点，在其邻居节点休眠后不再满足休眠条件这种特殊情况的出现。同时，考虑加入节点的轮转工作。

[1] 马祖长,孙怡宁,梅 涛.无线传感器网络综述[J].通信学报,2004,25(4):114-124.

[2] 徐朋豪,冯玉光,奚文骏,等.基于ZigBee的无线温湿度采集系统研究[J].国外电子测量技术,2013,32(1):33-36.

[3] 石 欣,冉启可,范 敏,等.无线传感器网络动态加权DV-Distance算法[J].仪器仪表学报,2013,34(9):1975-1981.

[4] Zebbane B.Energy-efficient protocol based sleep-scheduling for wireless sensor networks[C]//Proceedings of 2012 international conference on complex systems.[s.l.]:[s.n.],2012:407-412.

[5] Zebbane B.Enhancing the sensor network lifetime by topologycontrolandsleep-scheduling[C]//Proceedingsofinternationalconferenceonsmartcommunicationsinnetworktechnologies.[s.l.]:IEEE,2013.

[6]SinghB,LobiyalDK.Energypreservingsleepschedulingforcluster-basedwirelesssensornetworks[C]//Procofsixthinternationalconferenceoncontemporarycomputing.[s.l.]:IEEE,2013:97-101.

[7] 石冠雄.节点休眠调度仿真系统及优化算法[D].天津:天津大学,2012.

[8]WuK,GaoY,LiFL,etal.Lightweightdeployment-awareschedulingforwirelesssensornetworks[J].MobileNetworksandApplications,2005,10(6):837-852.

[9] 温 涛,张冬青,郭 权,等.无线传感器网络冗余节点休眠调度算法[J].通信学报,2014,35(10):67-80.

[10] 孙力娟,魏 静,郭 剑,等.面向异构无线传感器网络的节点调度算法[J].电子学报,2014,42(10):1907-1912.

[11] 韩志杰,吴志斌,王汝传,等.新的无线传感器网络覆盖控制算法[J].通信学报,2011,32(10):174-184.

[12]TianD,GeorganasND.Acoverage-preservingnodeschedulingschemeforlargewirelesssensornetworks[C]//ProcoffirstACMinternationalworkshoponwirelesssensornetworksandapplications.NewYork:ACMPress,2002:32-41.

[13]ZhangH,HouJC.Maintainingschemecoverageandconnectivityinlargesensornetworks[C]//ProcofNSFinternationalworkshopontheoreticalandalgorithmicaspectsofsensor,adhocwireless,andpeer-to-peernetworks.Chicago,USA:[s.n.],2004.

[14]XuY,YaoX.AGAapproachtotheoptimalplacementofsensorsinwirelesssensornetworkswithobstaclesandpreferences[C]//ProcofIEEEconsumercommunicationsandnetworkingconference.LasVegas,NV,USA:IEEE,2006:127-131.

[15]CardeiM,WuJ,LuM,etal.Maximumnetworklifetimeinwirelesssensornetworkswithadjustablesensingranges[C]//ProceedingsoftheIEEEinternationalconferenceonwirelessandmobilecomputingnetworkingandcommunications.[s.l.]:IEEE,2005:438-445.

[16]ChenH,WuH,TzengNF.Grid-basedapproachforworkingnodeselectioninwirelesssensornetworks[C]//ProcofIEEEinternationalconferenceoncommunications.[s.l.]:IEEE,2004:3673-3678.

A Sleeping Algorithm for Wireless Sensor Network Based on Location of Neighbors

JIA Ming-wei1,WU Min1,SHA Chao1,2,WANG Ru-chuan1,2

(1.Computer and Software College,Nanjing University of Posts and Telecommunications, Nanjing 210003,China; 2.Key Laboratory for Computer Information Processing Technology of Jiangsu Province，Soochow University, Suzhou 215006,China)

In Wireless Sensor Networks (WSNs),nodes are densely deployed,which may increase a number of redundant nodes.Considering the network’s coverage,a type of sleeping scheduling algorithm is proposed about coverage redundancy.Each node calculates the coverage rate of its sensing area according to the locations of its neighbors nodes.If the coverage rate is beyond the threshold,the node goes into sleeping mode while other sensor nodes remain active.Simulation experiment shows the effectiveness of the algorithm.By sleeping redundant nodes in the network,network energy is saved and network life is prolonged.Moreover,compared with other algorithms,the ability of the algorithm to detect redundant nodes is much better.The number of redundant nodes is greatly reduced in the network.

wireless sensor networks;sleeping scheduling;coverage redundancy;location of neighbors

2015-07-20

2015-10-23

时间：2016-03-22

国家自然科学基金资助项目(61202355)；高等学校博士学科点专项科研基金(20123223120006)；中国博士后基金(2013M531394)；江苏省自然科学基金(BK2012436)；江苏省博士后基金(0801019C)；江苏省高校自然科学基础研究项目(14KJB520029)；江苏省计算机信息处理技术重点实验室开放课题(KJS1327)

贾明伟(1991-)，男，硕士研究生，研究方向为无线传感器网络数据收集、覆盖等；吴 敏，副教授，硕士生导师，研究方向为海量数据管理,网络安全技术,密钥管理和认证以及物联网在智能家居、医疗健康护理等方面的应用技术等；沙 超，副教授，硕士生导师，研究方向为WSN的数据融合技术、智能定位算法、QoS路由机制以及覆盖调度技术等；王汝传，教授，博士生导师，研究方向为基于通信网络的计算机软件技术、网络安全技术、信息网络应用技术等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1522.090.html

TP301.6

A

1673-629X(2016)04-0056-05

10.3969/j.issn.1673-629X.2016.04.012