有限移动WSNs栅栏覆盖算法

陈业纲，徐则同

（1.长江师范学院 数学与计算机学院，重庆408000；2.中国科学院数学与系统科学研究院，北京100190）

0 引 言

覆盖问题是衡量WSN 服务质量的一项关键指标。在研究该问题时，要考虑节点的部署方式、感知范围和通信范围、能量有效性、算法特征以及节点的移动性这5个方面。根据节点是否具有移动性，将覆盖分为静止和移动覆盖，由于前者对节点的部署是随机的，可能会出现空隙，要解决此问题需要提高部署密度，但会造成节点的冗余。若节点具有有限的移动能力，当随机部署完成后，通过节点的移动进行重新分布，最终形成满足条件的栅栏覆盖。但如何构成节能高效的覆盖算法是一个难点。

1 相关工作

栅栏覆盖研究了监控目标穿越WSN 时被检测到是与否的问题，它反应了对目标区域的感应和监视能力，其目标是找到一条或多条从进入到离开目标区域的路径，不同的模型对监控的目标提供了不同的质量，根据模型的不同，将栅栏覆盖分为最佳覆盖 （best coverage）、最坏覆盖（worst coverage）和暴露穿越 （exposure）。

最佳覆盖就是目标穿越时被节点发现的最大概率，最坏覆盖是目标穿越时不被发现的最小概率，最佳最坏覆盖只考虑传感器的节点距离，在文献 ［1－4］中进行了相关的研究；暴露穿越既考虑了目标暴露又考虑了感应强度，在文献 ［5－8］研究了此问题。前两者的缺点是集中式算法，需要预先知道节点的位置，没有考虑实际中环境的影响；后者存在运行时间与暴露精度的矛盾，没有考虑节点运动造成的影响。为了解决这些问题，本项目提出了移动WSN的栅栏覆盖节能算法。

2 问题描述

假定目标区域 （o）是长为l，宽为w 的矩形区域，在该区域内假定随机部署m 个移动节点，每个节点具有相同的感知半径 （Rs）和通信半径 （Rc）。且部署完成后网络是连通的。由于部署是随机的，不能保证该区域的栅栏覆盖，加之节点能量有限，移动时应尽量减少移动的距离，以延长网络的生命期。满足要求作如下形式化定义。

定义1 k－栅栏覆盖：给定一个狭长区域，假定所有穿越该区域的路径都被至少一个传感器覆盖，则该区域被栅栏覆盖。当穿越时至少被K 个传感器感知，称为K－栅栏覆盖。

定义2 最小移动距离和 （barrier coverage min－sum，BCMS）：在该区域如何找到k个不相交的子集，且每个子集中的节点重新部署后，该区域是K－栅栏覆盖，且满足移动距离之和最小。

由于传感器节点具有有限的移动能力，经过定义2后移动后可以是任何形式的曲线，为了对目标区域进行监控，将该区域划分成n个网格，在该区域的长度方向上的网格数为int（l／Rs），宽度上的网格数为int（w／Rc），将网格的中心点作为该网格的重心。当目标进行穿越时能被一个传感器节点感知，此时就实现了1栅栏覆盖。如果至少能被k个传感器节点感应，相应就实现了k栅栏覆盖。下面对网格和1栅栏覆盖作如下形式化定义。

定义3 网格栅栏 （GB）：在目标区域和以网格为中心的点集 （g），若传感器节点Cx满足：

（2）Ci属于除Cx中横坐标最小的节点，Cj属除Cx中横坐标最大的节点，总存在节点Ck和Cq（k≠q），有：（d（ci，ck）≤2Rs）∩（xk≤xi）且（d（cj，cq）≤2Rs）∩（xq≤xj），即Cx中任意节点，总有不相同的左右邻居相互重叠的一个感知区域。

（3）目标区域的左右边界总能被Cx中的一个节点覆盖。

定义4 栅栏网格最小移动距离和 （grid barrier minsum，GBMS）：根据上面的描述，当移动传感器节点移动后，在整个区域中若形成1条栅栏网格，则称1－GBMS，若形成k条栅栏网格，则称k－GBMS。

3 节能算法

确定性覆盖的一种是基于网格的覆盖，为了节能，提出了一种在有限代价下，节点通过移动最少距离实现对目标区域的覆盖。

3.1 1－GBMS

根据定义4，先对给定的目标区域进行网格化，同时在目标区域左右边界处增加一列网格，下面给出了1－GBMS的线性规划描述。

3.1.1 1－GBMS的线性规划

给定传感器节点集 （S）和网格化后的中心点集 （G），增加的左列网格中心点集 （Zl）和右列中心点集 （Zr）增加2个节点 （O，T），O 节点只能在增加的左列移动，T节点只能在增加的右列移动，对目标区域中所有节点进行编号 （1－m）；用nl表示长度方向上的网格数；用A 表示所有节点集 （包括增加的节点）。G 表示网格中心点集 （包括增加的两列）。xij当其值为1时表示i节点移动到第j个网格中心。

为了实现此算法作了如下假设：

每个节点最多只能移动到一个网格中心，每个网格中心最多移入一个节点，1－GBMS看成节点O 到节点T 的一个流，若ab这2个节点相连的节点，a为前驱，b为后继，将a看成流入节点b，其值为1，根据能量守恒，有进入的流就有离开的流，将 （O，T）节点所在列移动的距离其值为0，其余移动距离为节点到网格中心的距离。在满足上述约束下，如果找到∑dij×xij的最小值，则实现了1－GBMS。

3.1.2 形成概率

假定移动传感器节点以柏淞分布随机部署于20×400 m 的区域，且其Rs为3m，移动距离最大为12m，且初始时是连通网络，节点的密度由0.002到0.04，在随机生成80个／密度值，其形成概率为1－BC的个数与80的比值。下面通过100 次实验，使用matlab11 对1－GBMS 进行仿真。结果如图1所示。

图1 密度分布与形成概率

图1可以看出，当密度分布小于0.015 时形成概率低于0.2，移动传感器网络也无法形成1－GBMS，其他情况可形成1－GBMS。后面的实验都是建立在密度分布在0.015～0.04之间。

3.2 CBMS算法

利用上述算法可以求得最优解，但是该算法是NPhard问题，提出一种求解该问题的近似CBMS算法。

对目标区域进行划分，选择与平行于边界的1 行，在每个网格中心放置一个节点，这种方式称为基准栅栏（BG），本文采用文献 ［6］提供的算法构建1－GBMS，当移动传感器重新定位后，从节能的角度，需要移动的节点数要最少且GBMS要最小。为了实现上述功能，应分两步实现，首先构建BG，然后使目标区域节点最少移动。

3.2.1 基准栅栏生成

当WSN 中的所有节点都移动到最近的网格，则GBMS最小。基于以上策略，提出了生成的基准栅栏思路，先标记目标区域的所有节点ni，然后求出所有节点到最近网格 （lk）的最小距离d （ni，lk），分别计算 每行的GBMS，找出最小的GBMS即为BG 的位置。其具体算法如下：

算法1：基准栅栏生成算法

（1）对目标区域所有节点扫描，并标记出每个节点到最近网格的gsd（lk）；

该算法1步求出gsd（lk），时间复杂度为O（n）；2－8步求出gsd数组，时间复杂度为O（int（w／（2Rc）），9－10步求出每一行得sr（i），时间复杂度为O（int（l／（2Rs）），故该算法的时间复杂度为O（n）。

3.2.2 最优移动

上述算法求出了基准栅栏，下面要从m 个节点中如何选取最少的节点使之移动，且满足GBMS最小。称此移动为最优移动。

由文献 ［9］证明最优移动实质上是二部图的赋值匹配，因此可以利用二部图的赋值匹配算法求解最优移动。其求解用文献 ［10］算法，其时间复杂度为O（x2y），其中x，y为二部图中节点数，其中x ≤y。

3.2.3 算法分析

20×400m 的区域内，节点密度在 ［0.015，0.04］变化，对CBMS和最优算法进行了模拟，如图2所示。

图2可以看出当密度为0.015时，二者相差4.5%，当密度增加到0.04时，差值变为不到1%，故提出近似算法能较好地替换最优算法。

图2 节点密度与移动距离和

4 构建k－栅栏覆盖

GBMS算法能够很好的解决通过上下边界的穿越，但是当目标对象水平穿越时可能会出现漏洞，同时由于此算法只能对矩形区域进行进行，当目标区域是狭长的带状区域时此算法就不能满足实际需要，为了解决上述问题，用隔离栅栏解决漏洞问题，将狭长区域中用不规则的区域分解成矩形和平行四边形解决此问题。其主要思想如下：①将目标区域平均分为u×v个矩形或平行四边形，其中每个小区域长为m（l／v）宽为n（w／u）。②在目标区域的右边界和相邻的2个区域中增加隔离栅栏。③在每个子区域分别执行GBMS算法，当所有节点移动结束后，在整个区域实现了k－栅栏覆盖。

此算法的主要时间开销在第3部，在每个子区域内的时间复杂度为O（x2iy），xi与子区域的面积有关，y跟子区域的节点数有关，其节点的平均数量为So／（uv），So为目标区域的面积。与全局算法相比，算法的时间复杂度低。

5 性能分析

为了研究此算法，从平均移动距离和与其他的栅栏覆盖算法进行了比较。

5.1 平均移动距离

为了研究移动传感器节点的平均移动距离，在20×1000m 的狭长区域内，按柏淞分布部署节点，其密度为0.03，在分布密度不变的情况下，图3给出了区域长度的范围从200到1000 m，目标区域的节点的平均移动距离。图4给出了k－栅栏覆盖中k值发生变化目标区域的节点的平均移动距离。

由图3和图4知，节点的平均移动距离不随网络的长度和k值得变化而变化，说明此算法的扩展性较好。

5.2 k－栅栏覆盖与文献 ［11］算法的比较

图5表示了k－栅栏覆盖与文献 ［11］算法 （简称C 算法）在相同密度分布下，节点移动的距离和的比较。

图3 区域长度与平均移动距离

图4 k值与平均移动距离

图5 节点密度与平均移动距离之和

由图5知，k－栅栏覆盖算法所有节点的移动距离之和随着密度的增加基本保持不变，而C 算法随着密度的增加而移动距离和增加，此说明提出的算法高于C 算法，能够有效地改善传感器网络的覆盖性能，并能有效地延长WSN的寿命。

6 结束语

k－栅栏覆盖解决了集中式算法需要预先知道节点的位置以及未考虑实际中环境的影响的问题；既克服了运行时间与暴露精度的矛盾，又考虑到节点运动造成的影响。利用节点具有有限的移动性，通过分治法将狭长的区域分成子区域，在子区域内通过节点向最近的网格中心移动，使之平均移动距离最小，实验仿真表明，提出的算法接近最优解，时间复杂度低，具有可扩展性。在后面的研究中拟在混合网络 （移动和静止）中研究覆盖。

［1］Yu L，Li JZ，Cheng SY.Approximate continuous aggregation via time window based compression and sampling in WSNs［J］.Wireless Sensor Networks，2010，2 （9）：675－682.

［2］Cortes J，Martinez S，Karatas T，et al.Cove－rage control for mobile sensing networks［J］.IEEE Trans on Robotics and Automation，2004，20 （2）：243－255.

［3］Meguerdichian S，Koushanfar F，Potkonjak M，et al.Coverage problems in wireless ad－hoc sensor network ［C］／／Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE，2001：1380－1387.

［4］Li JZ，Cheng SY.（ε，δ）－Approximate aggregation algorithms in dynamic sensor networks［J］.IEEE Trans on Parallel and Distributed Systems，2012，23 （3）：385－396.

［5］Meguerdichian S，Koushanfar F，Qu G，et al.Exposure in wireless ad－hoc sensor networks［C］／／Proceedings of the 7th Annual International Conference on Mobile Computing and Networking.New York：ACM Press，2001：139－150.

［6］Bi R，Li JZ，Cheng SY.（ε，δ）－Approximate top－k query processing algorithm in wireless sensor networks ［J］.Journal on Communications，2011，32 （8）：45－54.

［7］Veltri G，Huang Q，Qu G，et al.Minimal and maximal exposure path algorithms for wireless embedded sensor networks［C］／／Proceedings of the 1st International Conference on Embedded Networked Sensor Systems.New York：ACM Press，2003：40－50.［8］Adlakha S，Srivastava M.Critical density thresholds for coverage in wireless sensor networks ［C］／／Wireless Communications and Networking.New Orleans：IEEE Press，2003：1615－1620.

［9］BAN Dongsong，WEN Jun，JIANG Jie，et al.Constructing k－barrier coverage in mobile wireless sensor networks ［J］.Journal of Software，2011，22 （9）：2089－2102.

［10］LI Jing，WANG Shiying.An algorithm for constructing the maximum matching graphs on bigraphs ［J］.ACTA Electronica Sinica，2010，38 （1）：161－166.

［11］Shen CX，ChengWF，Liao XK，PengSL.Barrier coverage with mobile sensor［C］／／International Symposium on Parallel Architectures，Algorithms，and Networks.New Jersey：IEEE Press，2008：99－104.