距离辅助的无线传感器网络节点覆盖判别模型

凡高娟，孙力娟，王汝传,2，黄海平

(1.南京邮电大学 计算机学院，江苏 南京 210003；2.南京大学 计算机软件新技术国家重点实验室，江苏 南京 210093)

1 引言

由于传感器网络节点的处理能力、通信带宽以及能量等资源有限，且部署在恶劣环境中，对节点替换电池或能量补充是不可能的，所以网络一般采用高密度(20node/m3)部署策略[1]。但这种部署会造成信息冗余、信息冲突、网络消耗能量过多、网络生存时间缩短等问题。

在密集部署的监测区域内达到节约能量的方法就是去除一些覆盖冗余节点，在保证整个网络性能的前提下，将一部分节点处于工作状态，而让其他节点处于低功耗的休眠状态。覆盖是无线传感器网络对物理世界感知能力的体现，常作为描述无线传感器网络监测服务质量(QoS, quality of service)的标准，所以工作节点的选择必须以对目标区域的覆盖为基础[2]。如何判别一个节点的监测区域是否被其邻居节点完全覆盖是选择节点的前提。人们在工作节点选择及节点调度方面进行大量研究[3～13]。文献[4,5]将全部网络节点组织成若干个互不相交的节点集，并且每个节点集都能够完全覆盖目标区域。在每个时刻只有一个节点集处于工作状态，其他处于低功耗的睡眠状态。可以看出，无相交节点集合的个数k越大，网络生存时间越长，但计算满足上述覆盖要求的无相交节点集合的最大个数是 NP完全问题。DiTian[6]提出一个基于网络覆盖的节点调度算法，它是根据自身位置及邻居节点个数来判断节点与其邻居的覆盖关系，保证一定的覆盖能力。Jaekyu等[7]提出能够保证感知覆盖的分布式节点调度算法。通过节点的有效感知区域(ESA, effective sensing area)对节点进行调度。以上这些算法都需要精确知道节点的位置信息，而位置信息的获得要依赖于GPS、有向天线等基础设施或定位机制，这种机制不仅有成本和复杂度较高、较多的能量消耗等问题外，还存在准确定位的问题，不易用于军事等应用场所。

针对位置信息中覆盖判别存在的问题，DiTian[8]等对文献[6]进行改进，提出了位置无关的覆盖判别模型，节点根据自身感知半径内的邻居节点个数或最近距离信息，设定节点成为冗余节点的阈值，若邻居节点个数或最近距离达到设定的阈值，则该节点为休眠节点。该算法计算简单，易于实现，但没有考虑到节点休眠后其邻居节点是否真正达到对该监测区域的完全覆盖，不能保证监测的质量。Gao[9]等分析了节点完全冗余的概率上下限，节点感知半径内邻居节点个数计算自身成为冗余节点的概率，但覆盖判别运算复杂度高，且多个邻居节点造成节点覆盖冗余度高，消耗过多能量的缺点。后来的位置信息未知的一些节点调度算法[10～13]都是在这个思想上进行扩展，但没有考虑节点位置信息未知带来的覆盖判别精度问题，不能保障目标区域的监测质量。所以，如何提高节点的覆盖判别精度是选择工作节点和调度的前提，也是网络生存时间延长、保证目标区域覆盖的基础。

为了克服基于位置信息计算带来的能量消耗及位置信息未知时带来的覆盖判别精度不高、覆盖判别误差大等问题，设计一种距离辅助的节点覆盖判别模型。其基本思想是在节点随机部署情况下，根据节点与邻居节点的距离信息，计算出该节点被邻居节点的覆盖程度，若覆盖度达到应用的需求，则该节点为冗余节点。理论分析和仿真实验结果说明，距离辅助的覆盖判别模型具有较高的覆盖判别精度，在节点位置未知与精确位置已知情况下，对覆盖判别的误差仅为6.396 0%，能精确达到节点的覆盖判别。与DiTian和Gao算法相比，覆盖判别精度明显提高，为服务质量保证的节点覆盖调度提供了基础。

本文组织如下：第2节描述了节点的部署机制及感知模型，并说明覆盖判别中存在的问题；第3节提出覆盖判别模型并对模型进行分析；第4节对覆盖判别模型进行验证及分析；第5节是本文的结束语。

2 网络模型和问题描述

2.1 节点部署和感知模型

假定M个传感器节点随机部署在监测区域A内，对于每一个传感器节点Ui(i = 1, 2, 3,…, M)，做如下假设：

1) 节点的位置信息未知；

2) 节点密集部署且服从均匀分布，即不存在 2个节点重叠的情况；

3) 节点的感知模型采用圆形区域的布尔模型，且所有节点的感知半径相等；

2.2 相关定义

在下面的讨论中，对需要进行覆盖判别的节点称为节点U，首先给出一些定义及定理。

1) 感知点。指在监测区域内的任意点xi。对于布尔感知模型，用感知点可以表示为

2) 网络覆盖度。指处于活动状态节点的覆盖总面积与监测区域总面积的比值，对于工作节点覆盖面积来说，取的是工作节点覆盖的并集，即

其中，Acoverage代表工作节点对网络覆盖程度，Ai表示第i个工作节点的覆盖面积，k表示监测区域内工作节点的个数。

3) 邻居节点集。设节点的感知半径为R，则存在任意节点 U的邻居集是指与该节点的距离小于或等于R的所有节点的集合，用Neighbor(U)表示，则

如图1所示，节点U的感知区域内的所有节点都属于U的邻居节点集。

图1 节点的邻居集

4) 邻居覆盖。若某一节点的感知范围被其邻居节点集 Neighbor(U)的感知范围所覆盖，则称该节点被邻居覆盖。

5) 邻居覆盖期望。指节点的邻居节点集对本节点的覆盖程度，它是邻居集在该节点的感知范围内构成的监测面积并集与该节点感知面积的比值。

其中，Cneighbor(U)表示节点U的邻居覆盖期望，AU表示节点U的覆盖面积，Aj表示U邻居集对节点U的覆盖面积。

定理1 在节点感知半径为R的感知区域内存在邻居集，对于任意感知点x，如果x在R的感知范围内且被某一邻居节点覆盖的概率为Px，则在R内平均有Px的感知区域被邻居节点覆盖。

证明 假设R内有N个感知点{x1, x2,…, xN}，感知点在R内服从均匀分布，且感知点被邻居节点覆盖情况相互独立，设N个感知点中，有n个感知点被邻居节点覆盖的事件为X，Px表示某一感知点被某一邻居节点覆盖的概率，可知事件X服从

从式(4)中可以看出，事件X服从二项分布，即X～ B(Px，N)。

通过对事件X求期望，得：

从式(5)可以看出，在 R感知范围内平均有 NPx个感知点被邻居节点覆盖。

当N趋于无穷大时，感知区域R可以看成是由无穷多个感知点组成，所以R感知范围被邻居节点平均覆盖程度可以看成 R内的感知点被邻居节点覆盖的程度，即

定理得证。

2.3 问题描述

在节点位置信息未知的情况下，节点U的感知半径为 R，在其感知区域内存在邻居节点集Neighbor(U)，判别节点 U的邻居覆盖期望是否达到某一阈值Cth，即

也就是说式(3)是否精确达到应用中需要的覆盖期望值，如图2所示，判别节点U的覆盖面积被邻居节点A、B、C、D、E覆盖的程度。

图2 问题描述

3 节点覆盖判别模型

设在节点U感知区域内由x={x1, x2,…, xi,…}感知点组成的感知集，由定理1可知，如果感知集x能被其邻居节点覆盖，则节点U可被其邻居节点覆盖。

假设在半径为R的节点U内存在n个邻居节点，且邻居节点在U内服从均匀分布，对于任意一点xi，其在半径为R的感知范围内的分布函数为

对节点的覆盖判别，若只考虑邻居节点个数，首先定义覆盖函数fp= f (p,n1,…,nn)，其中p表示节点被邻居节点覆盖的概率，n1,…,nn表示邻居节点。

若节点内任意监测点 xi被一个邻居节点覆盖的概率为

存在2个邻居节点，至少被一个邻居节点覆盖的概率为

n个邻居节点中，至少被一个邻居节点覆盖的概率为

根据式(9)～式(11)可以求出节点U被邻居节点覆盖的程度，但在节点位置信息未知的情况下，邻居节点与U的距离各不相同，造成在相同的邻居节点个数情况下，对节点U的覆盖程度存在很大误差，如图3、图4所示，同样为3个邻居节点，从式(9)～式(11)计算的覆盖概率是相同的，但实际上或者是部分覆盖(如图3所示)，或者是全覆盖(如图4所示)。

图3 节点部分覆盖

图4 节点全覆盖

为了解决覆盖判别误差大的问题，对覆盖函数fp=f (p,n1,…,nn)改写，引入节点到邻居节点的距离信息，其改写后的覆盖函数为fp= f {p, (p1, d1), (p2, d2),…, (pi,di) ,…, (pn, dn) }，pi(i = 1, 2, 3,…, n)表示距离为 di的邻居节点对节点的覆盖概率。

若节点U存在邻居节点V，如图5所示，设U到V的距离为d (d≤R)，则节点V对节点U的覆盖面积为

节点U的面积为

图5 节点V对节点U的覆盖面积

假定节点U内有一个感知点xi，则该感知点被一个邻居节点覆盖的覆盖函数为fp= f {p, (p1, d1)}，该感知点被覆盖的概率为

若存在2个邻居节点，感知点xi至少被一个邻居节点覆盖的覆盖函数为fp= f {p, (p1, d1), (p2, d2)}，被邻居节点覆盖的概率为

其中，

表示节点被距离为di的邻居节点覆盖的面积。

若存在n个邻居节点，则被邻居节点覆盖的概率为

根据定理1，可以从邻居节点的距离信息判别出节点被其邻居节点覆盖的程度，若被邻居节点覆盖的程度满足需要的邻居覆盖期望，即满足式(7)，则可以认为节点可以被邻居节点覆盖。

4 验证与分析

4.1 实验环境及参数

为了评价和分析本文提出的节点覆盖判别算法，在MATLAB7.0上进行多次验证，对该模型与覆盖精确计算及节点信息未知的Gao[9]方案和DiTian[8]方案进行了对比验证。

假定某一节点的感知半径为40个单位，在其内部随机部署1～20个邻居节点。

4.2 实验及分析

4.2.1 与精确计算覆盖度比较

为了确保邻居节点对节点的覆盖精确性，在节点半径为40个单位的节点感知范围内产生361 201个像素，随机生成n个邻居节点均匀独立地分布在R内。每个像素定义为一个结构，根据感知半径的大小和n个邻居节点的坐标，依次计算节点内的像素被其邻居节点的覆盖情况，若像素点没有被邻居节点覆盖，结构内的值为0，若被邻居节点覆盖其值为1。显然，节点被邻居节点覆盖的情况就是被邻居节点覆盖的像素点的数目与总的像素数目的比值。为了更好地反映统计规律，所有的结果都是200次模拟实验的平均抽样，其比较结果如图6所示。

图6说明了节点位置信息已知和未知情况下，随着邻居节点个数增加，对节点的覆盖判别的比较结果。从图中可以看出，当只有一个邻居节点时，通过精确计算的节点覆盖度为59.654 3%，DANCI计算的覆盖度为64.996 6%，二者的误差为5.342 3%；邻居节点个数增加到 4时，精确计算的节点覆盖度为96.137 6%，DANCI计算值为98.885 8%，二者的误差为2.748 2%；节点个数增加到7时，精确计算的节点覆盖度为 99.543 5%，DANCI的节点覆盖度为99.975 5%，二者误差仅为 0.432 0%；节点个数达到12时，精确计算的值为99.977 3%，DANCI的节点覆盖度为99.999 9%，二者误差为0.022 6%，可以看作节点被邻居节点全覆盖。

图6 与精确位置信息误差情况

通过对误差值进行统计分析，得出在2种方法下，当距离确定时，随着节点个数的增加，二者覆盖判别最大误差为6.396 0%，最小误差为0.000 1%，说明DANCI节点覆盖判别模型已达到十分精确的值。但从总体上来说，DANCI对节点覆盖判别的程度比精确计算的覆盖度要略高一些。

4.2.2 与邻居节点个数比较

Gao[9]等在位置信息未知的情况下，用邻居节点个数对节点的覆盖进行分析与验证，同样在节点位置信息未知情况下，当采用DANCI判别时，二者覆盖判别精度上的比较，如图7所示。

图7 与邻居节点个数比较

从图7可以看出，在相同的邻居节点个数下，采用距离辅助的节点覆盖判别的精度比Gao的要高，当节点内有 2个邻居节点时，Gao的判别覆盖度为62.791 9%，DANCI的判别覆盖度为90.712 3%；当有4个邻居节点时，Gao的判别覆盖度为 86.241 3%，DANCI的判别覆盖度为99.015 5%，其对节点的覆盖度明显提高，这是因为采用了距离辅助信息，节点的距离代表了邻居节点对节点的覆盖程度，极大地提高了节点的覆盖判别精度。

随着邻居节点个数的增加，节点的覆盖度呈上升趋势，Gao有10个邻居节点时，节点覆盖度才达到99.298 3%，而DANCI在有5个邻居节点时，对节点的覆盖判别已达到99.669 2%，这说明DANCI在相同覆盖度的情况下，减少邻居节点的个数，进而达到节约节点能量，减少覆盖冗余带来的信息冗余，信息冲突等体现较好的效果，在节点调度中，可以保证较少的工作节点，最小化网络能量消耗。

4.2.3 与最近距离算法比较

DiTian[8]等在节点位置信息未知的情况下，采用最近距离算法来判别节点的覆盖度相对于使用DANCI模型时的覆盖度的比较，比较结果如图 8所示。

图8 与最近距离比较

从图8可以看出，当节点与邻居节点的距离越小时，对节点的覆盖度越大。当仅存在一个邻居节点时，2种覆盖判别的结果是相等的，这是因为DiTian是在邻居节点中选择了一个最近距离的邻居节点来判别覆盖，不考虑其他邻居节点对它的覆盖度。DiTian算法随着距离的增大，对节点的判别覆盖度呈线性下降趋势，DiTian对节点的覆盖判别不受邻居节点个数增加的影响，但DANCI模型随着邻居节点个数越多具有明显优势。邻居节点个数越多，对节点的覆盖度就越大，在与节点的距离为25个单位时，3个邻居节点可以达到90.405 2%，4个邻居节点对节点的覆盖度可达到94.951 7%。

图9说明了DANCI模型在邻居节点个数与距离增加的情况下，对节点的覆盖度情况。从图中可以看出，随着邻居节点个数的增加，对节点的覆盖度判别呈上升趋势，但随着距离的加大，对节点的覆盖判别呈下降趋势，但二者在某个数据值上对节点的覆盖度达到饱和。

图9 节点个数、邻居距离与节点覆盖度关系

5 结束语

本文深入研究了无线传感器网络中节点覆盖判别中存在的问题，针对当前节点位置信息未知的情况下，基于邻居节点个数、单一距离信息下节点覆盖判别存在不精确问题，提出了基于距离的节点覆盖判别模型，通过理论验证及仿真分析，证明该模型相对于节点位置信息已知的情况下，覆盖判别的精度最大误差仅存在6.396 0%，相对于邻居节点个数和最近距离覆盖判别算法，具有较高的覆盖判别精度，为保证整个监测区域的覆盖提供基础。在本文中假设节点间的距离信息已知，然而在实际的应用中，节点间距离信息的不稳定会对节点的覆盖判别产生很大的影响，造成覆盖判别上的误差，在将来的工作中，着重分析节点位置对覆盖判别的影响，进而在此基础上进行节点调度，达到节约节点能量，延长网络生存时间的目的。

[1] SHIH E, CHO S, ICKES N, et al. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks[A].Proceedings of the 7th Annual International Conference on Mobile Computing and Networking[C]. Rome, Italy, 2001.272-287.

[2] 陶丹, 孙岩, 陈后金. 视频传感器网络中最坏情况覆盖检测与修补算法[J]. 电子学报, 2009, 37(10)∶ 2284-2290.TAO D, SUN Y, CHEN H J. Worst-case coverage detection and repair algorithm for video sensor networks[J]. Acta Electronica Sinica, 2009,37(10)∶ 2284-2290.

[3] WANG L, XIAO Y. A survey of energy efficient scheduling mechanisms in sensor networks[J]. IEEE Transactions on Wireless Communications, 2007, 1(4)∶ 660-670.

[4] LIU C, WU K. Random coverage with guaranteed connectivity∶ joint scheduling for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(6)∶ 562-575.

[5] XIAO Y, CHEN H, et al. Modeling detection metrics in randomized scheduling algorithm in wireless sensor networks[A]. IEEE Conference on Wireless Communications and Networking (WCNC’07)[C].Kowloon, Hong Kong, China, 2007. 3741-3745.

[6] TIAN D, GEORGANAS N. A node scheduling scheme for energy conservation in large wireless sensor networks[J]. Journal of Wireless Communications and Mobile Computing Journal, 2003, 3(2)∶ 271-290.

[7] JAEKYU C, GILSOO K, TAEKYOUNG K, et al. A distributed node scheduling protocol considering sensing coverage in wireless sensor networks[A]. IEEE 66th Vehicular Technology Conference[C]. Baltimore, MD, 2007. 352-356.

[8] TIAN D, GEORGANAS N. Location and calculation-free nodescheduling schemes in large wireless sensor networks[J]. Ad Hoc Networks, 2004, 2(1)∶ 65-85.

[9] GAO Y, WU K, LI F. Analysis on the redundancy of wireless sensor networks[A]. Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications[C]. San Diego, CA,USA, 2003. 108 - 114.

[10] ZHANG M, CHAN M, CHOON A A. Coverage protocol for wireless sensor networks using distance estimates[A]. The 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON '07)[C]. San Diego, CA,USA, 2007. 183-192.

[11] JIANG S F, YANG, M H. An enhanced perimeter coverage based density control algorithm for wireless sensor network[A]. Third International Conference on Wireless and Mobile Communications(ICWMC '07)[C]. Guadeloupe, French Caribbean, 2007.79-79.

[12] GAO Y, WU K, LI F, et al. Lightweight deployment-aware scheduling for wireless sensor networks[J]. Mobile Networks and Applications,2005, 10(6)∶ 837-852.

[13] CHEN J, YU F Q. A location independent and coverage efficient protocol for wireless sensor networks[A]. IEEE International Conference on Integration Technology(ICIT '07)[C]. Shenzhen, China, 2007.751-755.

[14] BEJERANO Y. Simple and efficient k-coverage verification without location information[A]. The 27th Conference on Computer Communications (INFOCOM’08)[C]. Phoenix, AZ, 2008. 291-295.