基于极坐标的无线传感器网络覆盖盲区发现算法*

邢冬平， 段 富, 樊茂森

(太原理工大学 计算机科学与技术学院，山西 太原 030024)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)的覆盖问题是无线传感器网络需要解决的基本问题之一[1]。所谓的覆盖问题，即指特定的目标监测区域是否被无线传感器充分覆盖和处于完全监视之下。产生覆盖问题的原因主要来自以下几个方面：1)无线传感器大都通过随机的形势部署的，导致部分监测区域没有传感器，产生覆盖盲区；2)传感器在使用的过程中损毁，能量耗尽等[2]造成的使用过程中的失效，产生覆盖盲区作为衡量无线传感器网络质量的重要参考，覆盖盲区直接影响网线传感网络的收集数据的可靠性、完整性。因此，当网络中出现覆盖盲区时，应立即检测到，以保持无线传感器网络的完整性、可靠性[3]。

当前针对无线传感器网络覆盖盲区发现的研究，许多研究者提出了一些检测方法。Kanno J等人[4]先建立的通信连接图，再用最大单纯复形把通信连接图转换成为一个二维的单纯复形，进行对网络中的覆盖盲区进行检测。Dong D等人[5]利用代数拓扑去建立传感器节点的通信拓扑图，该算法适用于包含移动节点和静态节点的混合型的无线传感器网络。Xin等人[6]依据无线传感器网络的覆盖空洞由边界弧包围，提出了一种通过计算出边界弧和边界节点的位置，检测到了网络中的覆盖盲区的算法。然而这些算法的代价都太大，特别是当网络中的节点数过多时，整个网络的通信代价和能量消耗都非常大。Ma Hwa-chun等人[7]提出一种以单个节点为中心，通过该节点与相邻节点构成的三角形进行覆盖盲区检测的理论方法，并证明了该方法可行性。

本文在上述理论研究的基础上，进一步研究，提出一种基于极坐标进行无线传感器网络盲区检测的分布式算法。

1 问题描述

在无线传感器网络中由于初期采取随机部署或者使用的路由算法不佳、环境恶劣等因素，而使节点失效，进而使无线网络中存在覆盖盲区，如图1所示。

图1 空洞示意图

图1矩形区域是需要被传感器检测的目标区域，灰色的部分是未被任何传感器节点所覆盖的目标区域称为覆盖盲区。

本文的传感器网络采用静态网络模型，即所有节点都为静态节点。每一个节点都具有通过定位服务获得在部署区域边界以内的位置和坐标，并能感知相邻节点的坐标。节点的最大通信半径Rc是最大感知半径Rs的2倍[8]。

2 理论基础

2.1 极坐标理论

在一个平面内选定一点X和任一射线XO为极轴,则平面上任一点P在极坐标系中的坐标可以表示为P(ρ,θ)，其中,ρ为点X到点P的直线距离，θ为XO到XP的角度。本文使用极坐标系来表示选定的节点与它相邻节点的关系，并按极角的大小进行排序。如果列表中存在极角相同的多个点，则只保留极径较小的一个点。

如图2所示，参考节点X有邻居节点A,B,C,D,E,F,G,H,J,K,L,M。采用极坐标表示后，按极角升序排列将得到有序列表L1={F,E,D,C,B,A,M,L,K,J,H,G,F} 。

图2 节点分布图

2 2 基于相邻节点的几何判定理论

Ma Hwa-chun等人[7]提出了关于选定节点的覆盖盲区的几何判定理论，并进行了详细的论证。具体地，当选定节点与其2个邻居节点构成三角形且三角形的外接圆半径R≤RS，则在该节点附近没有覆盖盲区；反之，当R>RS或三角形的外接圆圆心Z不被其他传感器节点覆盖，则在该节点附近有覆盖盲区。

2.3 三角形外接圆的计算

(1)

(2)

外接圆圆点Z在极坐标系中的坐标为(R，θZ),其中,θZ的计算公式如下

(3)

式中θ，L为节点B，C中极角较小的节点。

3 算法描述

在上述理论的基础上，本文提出一种基于极坐标表示的无线传感器网络覆盖盲区的发现算法，该算法是分布式的算法，节点之间可并行执行。算法的具体描述如下：

1) 随机选取任何一个参考节点X，其平面直角坐标为(a,b)。

2)找出该参考节点的所有与节点X的距离小于RS的节点，作为集合N。

3)对集合N中的所有元素求关于X的参考极坐标位置并按极角大小排列生成列表L,对L进行加工形成列表L1。

4) 从L1中选取两点Ai和Aj，其中,i

a.If(△XAiAj的外接圆半径R≤RS)节点X附近没有覆盖盲区;

b.elseif(△XAiAj外接圆圆心Z被其他传感器节点覆盖)节点x附近没有覆盖盲区;

c.else节点x附近有覆盖盲区。

5)令L1=L1-{Ai}，重复步骤(4),直到列表L1为空。

4 仿真实验验证算法的有效性与性能

4.1 算法有效性验证

为了验证算法的有效性，将用计算机仿真软件对现实传感器无线网络进行模拟仿真。本文仿真实验采用的计算机硬件平台为计算机：Thinkpad E420 EBC；处理器：Inter(R)Core(TM)i5—2430M CPU @2.40 GHz；安装内存(RAM)：6.00 GB；操作系统：Win 7旗舰版 64位操作系统；仿真软件是Matlab 7.12。实验参数如下：网络规模为100 m×100 m;感知半径为10 m;通信半径为20 m；节点个数为100个；数据包传递的能量消耗2 J；数据包接收的能量消耗为1 J。

在二维平面100 m×100 m的正方形区域内，随机部署100个传感器节点在该区域内，如图3所示。

图3 节点的随机分布图

在每个传感器节点上并行的运行算法上述漏洞检测算法，可以成功监测到目标区域内存在的覆盖空洞，并成功监测到这些覆盖空洞的边界节点。如图4所示，在100 m×100 m的目标区域内存在4个覆盖空洞，使用的算法可以检测到全部26个边界节点，用加粗线标出。

图4 覆盖盲区和边界节点的检测

4.2 算法性能评估

为了验证本算法的性能，本文选取文献[5]中算法为参照算法，在Matlab仿真环境下，比较了2种算法发现覆盖盲区的效率。每种情况下分别进行多次运算，取其时间平均值，得到的结果如图5所示：

图5 不同算法下盲区发现时间表比较

从图5中对比可看出:在相同盲区数量的前提下，本文算法的盲区发现的平均时间要少于文献[5]中的算法。该结果即表明了本算法的可靠性，同时也体现了分布式算法的优越性,提高了覆盖盲区的发现效率。

5 结 论

由于传感器初始分布的不均匀，且在使用过程中传感器自身原因和恶劣环境的影响，传感器覆盖盲区的出现不可避免。通过上述实验，验证本算法不仅能找到覆盖盲区，而且能找出覆盖盲区所有边界节点。检测无线传感网络的覆盖盲区，不仅为了确定传感网络的可用性，当检测出盲区后，如何找到一种合适的方法去修补盲区或者使用更好的传感器节点的分布算法[10]，将是下一步研究的重点。

参考文献:

[1] Trajcevski G,Avci B,Zhou F,et al.Motion trends detection in wireless sensor networks[C]∥2012 IEEE 13th International Conference on Mobile Data Management (MDM),2012:232-237.

[2] 邢冀鹏.无线传感器网络目标覆盖算法研究[D].武汉：华中科技大学,2008.

[3] 刘丽萍,王 智,孙优贤.无线传感器网络部署及其覆盖问题研究[J].电子与信息学报,2006,28(9):1752-1757.

[4] Kanno Jinko ,Buchart Jack G,Selmic Rastko R,et al.Detecting coverage holes in wireless sensor networks[C]∥Proceedings of 17th Mediterranean Conference on Control and Automation,2009:452- 457.

[5] Dong D,Liao X,Liu K,et al.Distributed coverage in wireless Ad Hoc and sensor networks by topological graph approaches[J].IEEE Transactions on Computers,2012,61(10):1417-1428.

[6] Xin Yue,Zhang Zhenjiang,Liu Yun.A coverage hole detecting algorithm in wireless sensor networks[J].Journal of Convergence Information Technology,2011,6(9):159-168.

[7] Ma Hwachun ,Sahoo Prasan Kumar ,Chen Yenwen.Computational geometry based distributed coverage hole detection protocol in wireless sensor network[J].Journal of Network and Computer applications,2011,34:1743-1756.

[8] 蒋 丹.无线传感器网络覆盖盲区的发现与修复方法研究[D].沈阳:东北大学,2008.