无线传感器网络多栅栏覆盖构建算法研究*

杨 涛，慕德俊

(西北工业大学自动化学院，西安 710072)

0 引言

覆盖问题是无线传感器网络配置首先面临的基本问题，它决定着一个无线传感器网络的工作性能。栅栏覆盖较全覆盖模型，更加符合实际应用中长时间、无间断工作的需要，已成为无线传感器网络的研究热点之一[1－3]。

已有工作主要基于随机部署的静态传感器网络对监控区域实施单栅栏覆盖，存在两个问题：1)由于部署的随机性，传感器网络中可能存在空隙，或随着时间延续，网络中出现死节点的弱区域，使得入侵者可能通过监控区域而不被检测到;2)随机部署时，监控区域内会散布大量节点，而单栅栏覆盖只选取其中一部分，这就造成节点冗余浪费。

文中针对带状监控区域内随机部署的无线传感器网络，研究如何通过分治算法高效的构建k－覆盖的问题。主要研究工作包括：1)形式化定义了传感器节点k－覆盖的条件，确保在监控区域中，入侵者穿越路径至少被一个传感器节点覆盖;2)提出了区域多栅栏覆盖构建算法DPA。实验表明该算法与传统的多边形栅栏构筑算法相比，构筑栅栏数目超出30%，并降低了通信开销和计算复杂度，延长了网络的工作寿命。

1 网络模型和问题描述

1.1 网络模型

传感器网络N，是一组传感器节点的集合，它们被随机布置于大小为A的二维模型环境中，假设这个二维环境是一个带状区域，这个带状区域有4条边界，两条水平的，两条竖直的，其中宽度为w，长度为l，A2d=l×w，见图1，则可以假设每个传感器节点随机泊松分布在区域A中，设数量为N(A)的传感器以参数为na分布，则得到：

图1 传感器部署带状区域

用u来代表一个传感器节点，设每一个传感器节点的感应半径为rs，当传感器节点u与监测区域的任意点p的欧式距离小于传感半径rs时，则点p被覆盖。

1.2 问题描述

监测的带状区域的每一个点都被覆盖的模型叫做全覆盖模型。在带状区域中，仅在水平方向部署传感器的模型叫做栅栏覆盖模型。当入侵者的入侵轨迹经过k个传感器节点感应区域时，称之为k－覆盖。一个覆盖区域的所有入侵路径都最少经过k个传感器节点的感应区域，就称该覆盖支持k－覆盖。如图2所示。

图2 覆盖模型

图3 带状区域没有被栅栏覆盖因为存在一条无覆盖突破路径

在文献[1]中发现栅栏覆盖对于全覆盖有一定的局限性，例如，在一段长约500km，宽度为50m的带状区域中，通过全局栅栏覆盖定义，仍存在一条近似于带状区域宽度的无覆盖穿越路径，称之为突破路径，如图3所示。

Ai等人提出L本地化栅栏覆盖的概念用于解决此问题，将带状区域分成若干长度为L的片段，每一个L长度片段内实现栅栏覆盖，则该片段内的每一条路径就实现了覆盖[4]。Liu.等人提出强栅栏覆盖的概念解决此问题，提出了在带状区域的竖直方向上建立栅栏，保证每一条路径在穿越时都至少经过一条竖直方向的栅栏，这样就实现了所有穿越路径的栅栏覆盖[5]。

这两种方法在一定程度上都能解决这个问题，但本地化的算法对传感器能量消耗过大，不利于延长网络寿命。在竖直方向上建立栅栏的强栅栏覆盖又不能保证竖直栅栏正好建立在两个漏洞点中间。所以文中将提出利用多栅栏构筑算法实现多栅栏切换，加强覆盖质量的方法。

2 栅栏覆盖的基本条件

一般无线传感器网络的配置是由飞机等在空中随机播撒传感器节点，所有的传感器节点就会在带状监测区域内部的一条线段上随机分布。假设这个线段为[0，L]，把它分为N个片段，每一个片段的长度为传感器感应半径的两倍2rs，即N=L/2rs。

在两个相邻的片段i和i+1中，片段i中的最右端节点A的位置为X1，片段i+1中的最左端节点B的位置为X2，需要以下条件保证传感器全覆盖，如图4所示。

1)每个长度为2rs的片段内都必须有一个传感器节点u。

2)当相邻传感器节点距离大于等于两个感应半径即2rs≤X2－ X1＜ 3rs时，在[X1+rs，X2－ rs]，即区域CD中至少有一个传感器节点。

3)当相邻传感器节点距离大于等于3倍感应半径即3rs≤X2－ X1＜ 4rs时，在[X1+2rs，X2－ rs]即区域FD或者[X1+rs，X2－2rs]即区域CE内至少有一个传感器节点。

图4 片段i全覆盖的条件(1＜i＜N)

假设BCOV(α)是该区域被覆盖的概率，Yi代表i片段被传感器全覆盖，P(Yi)表示事件Yi发生的概率，当片段长度为2rs时，可以得到P(Yi|Y1∩Y2…，并且事件 Yi和Y1…Yi－2是相互独立的。所以：

把图4中填充区域的CE、FD分成无数个长度为Δθ的小片段，无线传感器节点以参数为λ的泊松分布配置在区域中，由离散逼近可以得到：

将式(3)～式(5)代入式(2)就可以得到P(Y1∩Y2…∩YN)的值。

3 多栅栏构筑算法

3.1 分治算法

在满足以上覆盖条件的基础上，就可以进行多栅栏构筑。同时，将覆盖区域分为若干个小的片段区域，就可以有效降低整个网络的能量开销，增大网络的使用寿命。在水平与竖直方向分别构筑栅栏，比传统的多边形覆盖算法(PMI)更有效。

区域分割的机制如图5所示，先通过传感器节点上的GPS模块获得各节点的地理位置信息，然后在与带状区域的延伸方向上选取竖直方向的传感器节点，并把他们相连，形成图6中的竖直构筑区，该竖直构筑区是随机产生的，其余的节点即在水平方向上互连，形成水平构筑区。

图5 分离后的多栅栏覆盖图

3.2 DPA算法描述

由上节中讨论的分治算法思想，可以知道多栅栏构筑算法DPA在能够获知网络全局信息的中心簇头节点上运行，中心节点可以通过选举等方式确定。通过分割覆盖区域的方式，整个网络的信息延迟、通信开销和计算消耗都明显降低。对于连通网络G(V，E)，其网络开销和构筑栅栏的计算复杂度分别是O(|V||E|)和O(|V|3)。如果带状覆盖区域被分为n个小区域，则每个区域的节点不多于 |v|/n，则它们的通信开销就是O(|V|2/n2)算法复杂度为O(|V|3/n3)。

District Partition Algorithm(DPA)Require：Many Sensors are deployed in the belt region Ensure：Different barrier in the belt region，barrieri;The work time of barrieri，ti.1：Invoke the Edmond-Karp algorithm to find a maximum flow from s to t in G(N).2：Deleting all value of vertices with 0 from G(N).3：Choosing sensors from far left in the deployed belt，which means the sensors are connecting with node s.4：Connecting the neighbor sensors one by one until the sensor is connecting with node t.The neighbor sensors location must to the right of prior sensor.5：Collecting the GPS information of sensors in a barrier and calculating the average vertical value to differentiate the barriers.Then different barrier are constructed.6：Sort these barriers by descending order ofrest energy.Then get the rest energy sequence sq1，sq2...，sqi 7：We denote the work time of barrierias ti.Then t1sq1∑n i=1sqi= t2sq2∑n i=1sqi= t3sq3∑n i=1sqi=…= tisqi∑n i=1sqi If t1is the work time of barrier1，then the work time of barrier s2t2ist1sq1 sq3…8：return ti ;

4 仿真实验

为了验证上述方法的真实有效性，文中利用Matlab进行仿真实验。在实验中，设定部署区域长度为7000m，宽度为1000m。布置一定数量的传感器节点，可以看到文中使用的区域分割法(DPA)构筑栅栏比传统的多边形栅栏构筑方式IPM更加有效。如图6。

当泊松分布参数由0.001到0.05。传感器感应半径为100m到200m。通过仿真实验与式(3)～式(5)推导出来的结果进行比较得出，分析公式能够很好的指导实际仿真结果。实际结果如图7所示。其中 x轴为泊松分布参 λ的值，y轴为覆盖率。

图6 多栅栏构筑

图7 泊松分布参数与覆盖率关系图

当节点数量不断增加时，DPA算法可以根据传感器节点剩余能量决定各条栅栏的工作时长，可以有效延长系统的工作时间。图8中的参考值是部署4500个节点时，传感器网络工作的时长T，纵坐标为通过DPA算法构筑的多栅栏网络的工作时长与T的比率。可以看出通过DPA算法构筑的多栅栏有效延长了网络的工作时间。

图8 DPA构筑多栅栏的网络寿命

5 结论

栅栏覆盖是无线传感器网络覆盖的一种更高效的模型。已有研究工作主要针对单栅栏覆盖。文中研究如何改进单栅栏覆盖的质量，更高效的实现k栅栏覆盖的问题，提出了DPA算法。将监控区域分割成多个子区域，分别进行栅栏构筑，最终连接所有区域，实现高效可靠的覆盖。实验表明，DPA可以构筑更多栅栏，并且可以有效的延长网络的工作寿命。

[1]S Kumar，T H Lai，A Arora.Barrier coverage with wireless sensors[C]//Proc.of ACM MobiCom，Cologne，2005：284－298.

[2]Bai XL，Yun ZQ，Xuan D，et al.Deploying four-connectivity and full-coverage wireless sensor networks[C]//Proc.of the IEEE INFOCOM，2008：296－300.

[3]I F Akyildiz，T Melodia，K R Chowdhury.A survey on wireless multimedia sensor networks[J]Computer Networks Journal，2007，51(4)：921－960.

[4]Ai Chen，S Kumar，T H Lai.Designing localized algorithms for barrier coverage[C]//Proc.of ACM MobiCom，2007：63－74.

[5]Liu BY，Dousse O，Wang J，et al.Strong barrier coverage of wireless sensor networks[C]//Proc.of the 9th ACM Int’l Symp.on Mobile Ad Hoc Networking and Computing(Mobihoc)，2008：411－420.

[6]Balister P，Bollobas B，Sarkar A，et al.Reliable density estimates for coverage and connectivity in thin strips of finite length[C]//Proc.of the 13th Annual ACM Int’l Conf.on Mobile Computing and Networking(MobiCom)，2007：75－86.

[7]Jren-Chit Chin，Yu Dong，Wing-Kai Hon，et al.Detection of intelligent mobile target in a mobile sensor network[J].IEEE/ACM Transactions on Networking，2010，18(1)：41－52.

[8]何欣，桂小林，安健.面向目标覆盖的无线传感器网络确定性部署方法[J].西安交通大学学报，2010，44(6)：6－15.