WSN 中边界覆盖的最佳部署及其选择

赵海军，陈华月，陈毅红

(1.西华师范大学 计算机学院，四川 南充 637009；2.物联网感知与大数据分析南充市重点实验室，四川 南充 637009)

无线传感器网络（Wireless Sensor Network，WSN）随着技术的进步、价格的下降和发展，将得到更加广泛的应用.传感器网络在弥合现实世界和虚拟信息世界之间的差距方面发挥着重要作用[1-2].WSN 的新兴应用领域就是智能监测和入侵检测.入侵检测作为WSN 的应用之一，它涉及到检测和识别监测区域被外来目标入侵的问题；考虑到最小化功率要求，最好选择执行任务基本数量的传感器节点，而剩余的其他传感器节点处于休眠或关闭状态.尽管对于传感器网络的目标跟踪已得到广泛研究[3-5]，但由于通信、处理和能量限制，采用传感器节点的入侵检测仍提出了不同的挑战.

边界表示监测区域所能达到的物理范围，一般跟应用有关.在传感器节点的典型部署中，传感器节点通常分布在监测的整个区域，有必要确定一组最少的传感器节点监控边界.因此，必须为边界覆盖问题找到一个有效的解决方案.文献[6]针对WSN 的k-覆盖问题进行了研究， 提出了一种由静态传感器和少量移动传感器构成的混合网络结构，并得到了这种网络结构下不依赖于网络大小的k-覆盖以及调度移动传感器移动的分布式移动调度算法，从而实现有效覆盖，但没有分析三维（three Dimension，3D）边界覆盖问题.文献[7]针对现阶段典型的WSN 区域覆盖节点调度算法原理进行了阐述，分析了它们各自的优缺点，但没有考虑边界覆盖，主要针对的是二维（two Dimension，2D）情形.文献[8]研究了基于WSN 的2D 入侵监测区域的可变k-覆盖问题，提出了基于划分聚类规则对传感器节点进行重新部署的CP-var（k）算法，算法首先对区域进行网格划分，根据其覆盖度进行聚类，然后根据当前覆盖度和需求覆盖度的比较得出每个区域是有冗余节点或是覆盖度不足，最后通过对节点的重新部署实现区域内的可变覆盖.

全覆盖问题（即监测区域中的每个点是否被至少一个活跃传感器覆盖）已经在多种环境中得到研究.文献[9]主要研究了水下无线传感器网络中3D 屏障覆盖的高效构建问题，提出了采用移动传感器构建水下屏障覆盖的先进算法，然后对水下无线传感器网络3D 屏障覆盖未来面临的挑战进行了总结.文献[10]研究了3D 区域中的全覆盖问题，提出了算法定位区域中的冗余传感器节点，并采用简单的几何技术禁用它们.文献[11]分析了WSN的能量消耗问题，设计了一种基于集群的路由协议，防止中间瓶颈节点的产生，提出的路由协议避免了中间瓶颈节点的产生，提高了网络的性能.文献[12]研究了大量随机部署的传感器节点，将传感器节点划分为不相交的集合，使得每个集合能够单独执行区域监测任务，从而延长网络寿命.文献[13]提出了一种3D 表面的传感器网络栅栏覆盖部署方法，首先构建监测区域的3D 网格曲面模型，然后计算3D 网格曲面中任意两个数据点之间的最短路径构建栅栏图，最后计算最终的部署结果，能够适用传感器规模较大的应用场景的栅栏部署.文献[14]针对WSN 中覆盖漏洞问题提出了一种基于无弦圈的覆盖漏洞检测算法，算法依据覆盖漏洞边界节点分布连续性，利用无弦圈的覆盖漏洞搜索算法，对预筛选边界节点集进行精确识别，剔除非边界节点，结果表明，算法能够有效地识别覆盖漏洞边界节点和覆盖区域外边界节点.为了提高无线传感器网络漏洞检测效果，文献[15]提出一种基于改进粒子群算法的覆盖漏洞检测方法，实验结果表明，当单元格边长越接近感知半径越有利于漏洞个数和面积检测.文献[16]通过考虑边界效应（Boundary Effects，BEs），并采用二进制和对数正态感知范围模型，分析了在圆形区域（Circular Region，CR）上传输的WSN 的覆盖度量，评价了各种网络变量即传感器节点数、最大感知范围和阴影效果（Shadowing Effects，SEs）的标准差对WSN 的覆盖率的影响.

上述与WSN 覆盖问题相关的现有结果都集中在平面网络，而且没有考虑各种覆盖区域的边界覆盖情形.而对于灾难恢复、地形地貌特征、空间探索和海底监测等应用，都涉及到立体区域和边界覆盖问题.

本文研究了确定覆盖目标区域边界的最小传感器节点数量及其位置的问题.分别针对2D 和3D 覆盖区域，将传感器节点分别建模为圆盘和封闭球实现WSN 的边界覆盖，并确定出边界覆盖所需的最少传感器节点数目及其位置；同时提出了选择得到的传感器节点的一个子集以保持活跃，提高网络边界覆盖的寿命.仿真实验结果表明，本文提出的边界覆盖最佳部署及其选择策略在所需传感器节点数目和网络边界覆盖寿命方面都优于随机部署和其他边界覆盖算法.

1 问题构建

以下假设要监测区域与单个传感器节点的感知区域相比是很大的，且所有传感器节点的位置已知.全文采用以下记号：R为研究的区域；S为区域中传感器的集合；RS为每个传感器的感知半径；Ai为传感器Si的感知区域；Ciri为传感器Si的2D 感知区域的边界；CF为完全覆盖区域的传感器集合；CB为覆盖区域边界的传感器集合.

本节首先定义感知区域和边界覆盖的概念，然后构建边界覆盖和优化问题.令Oi为能够感知现象P的传感器节点Si的输出，传感器节点Si的感知半径为Ri.假设每个传感器节点知道自己的位置、要监测区域的边界位置以及其邻居的位置.

定义1称位于y∈R3处的现象P被位于Xi∈R3处的传感器Si检测到，当且仅当存在一个恒定的阈值δ使得：

式中：δ为信号阈值，并特定于所采用的传感器类型.位于Xi(xi,yi,zi)处的传感器Si的感知区域是被传感器Si可检测现象P的全部点的集合，即Ai={y∈R3|P是由Si可检测的}.不失一般性，将Si的感知区域限制为中心在Xi∈R3的封闭球，并假设全部部署的传感器节点有相等的感知半径R3.

定义2令Y={y∈R3|Oi(y)＞δ}，位于Xi∈R3的传感器Si的感知区域定义为Ai={y∈Y| ||y-Xi||≤R3}，其中||·||为y与Xi之间的欧氏距离.

在2D 情形，感知区域是半径为R3的一个圆盘，传感器Si的感知边界(圆)用Ciri表示.假设任意两个节点Si和Sj可以直接相互通信，如果它们的欧氏距离小于通信范围RC，一个网络失去其连通性变得无用，则只需由此得到的边界覆盖就可以描述系统的寿命.文献[17]表明，如果通信范围至少是感知范围的2 倍，则凸起区域的完全覆盖意就味着节点之间的连通性.

一个入侵者是指在跨越边界时受到传感器网络检测的任何物体.一般而言，入侵者不知道所部署的传感器节点的位置.下面给出区域边界的确切定义.

定义3令R为2D 或3D 空间的一个子集.如果点p的每个邻域都包含R的一个点，则说点p在R附近，即：

式中：Ball(p,ε)指来自于p的欧氏距离小于ε的所有点的集合.

定义4R中和在R附近的所有点的集合称为R的闭包，表示为cl(R)，即：

定义5用B(R)表示的区域R的边界定义为R的所有公共点及其补集的集合，即：

根据定义3～5，当且仅当一个入侵者在穿越该区域的边界时总是被检测到，即称一个区域被边界覆盖.如果一个传感器的感知区域与监测区域的边界相交，则称这个传感器为边界传感器.

定义6如果R边界上的每个点都属于CB中至少一个传感器的感知区域，即称传感器节点的集合CB为区域R的边界覆盖，即对于某个Si∈CB有p∈Si，∀p∈B(R)，p∈Si.

定义7如果对于某个Si∈CB,R有∀p∈B(R)，p∈Si且没有CB,R的真子集是R的边界覆盖，即对于任意的Sl∈CB,R，有CB,R-Sl不是R的一个边界覆盖，则称传感器节点集合CB,R为区域R的缩小边界覆盖.

定义8如果一个传感器节点的感知区域被其相邻的传感器节点完全覆盖，则称这个传感器节点为冗余传感器节点.禁用一个冗余传感器不影响监测区域的总的全覆盖.

定义9如果被一个传感器节点覆盖的边界部分完全被其相邻的传感器节点完全覆盖，则称这个传感器节点为冗余边界传感器节点.

定义10如果一个传感器节点的感知区域与监测区域的边界不相交，则称这个传感器节点为非边界传感器节点.

从定义9 和10 可以看出，边界冗余传感器或非边界传感器的失活不影响监测区域的总体边界覆盖.根据定义1～10，我们将边界覆盖问题划分为下列2 个子问题：

(1)边界覆盖的最佳部署：寻找一个给定区域R(2D/3D)的边界覆盖的最小传感器节点数及其部署；

(2)边界覆盖的选择：给定一个区域R中传感器节点的密集部署，寻找保证R边界覆盖的活跃节点的最小子集.

2 边界覆盖问题算法

2.1 边界覆盖的最佳部署策略WSN 中的一个关键问题就是传感器网络的部署和组织.尽管许多场景假设随机部署，但这种部署并不是最佳的，因为给定区域中过多活跃节点会导致大量的能量浪费，所以需要找到传感器节点的最佳边界部署，以便用最小数量的节点实现边界覆盖.

2.1.1 边界覆盖的最佳2D 部署 2D 部署问题就是确定建模为圆盘的传感器节点的最小数量及其在给定矩形区域R的边界覆盖的位置.将边界覆盖区域假设为一个矩形区域，算法略作修改可以扩展到边界覆盖任意形状的区域.

定理1考虑长为L和宽为W的矩形区域R，实现R的边界覆盖所需的传感器节点数的下界为：

式中：

证明实现区域边界覆盖的最佳方法是将传感器节点沿整个区域的周长部署，使得同一行或同一列上的任意2 个相邻传感器节点彼此相切.[L/2RS]是覆盖长度为L的直线的传感器节点的最小数量.对于长度为L和宽度为W的矩形区域，周长可以用2([L/2RS]+[W/2RS])个传感器节点最佳覆盖.但这样的覆盖在矩形的顶点(即角点)将有重叠的感知覆盖，传感器节点数量并不完全覆盖每个边，最后一个传感器将部分覆盖相邻边，所以更好的方法是选择中心的下一个位置，使其感知圆与其边界交叉部分的最后一个圆相交.

特殊情形[图1(a)]令2d1和2d2分别为L除以2RS和W除以2RS的余数，即2d1=Lmod (2RS)和2d2=Wmod (2RS).如果角传感器节点能够完全覆盖矩形长度上的剩余d1和每个相应角上矩形宽度上的RS+d2，则将获得最佳部署.这样，基于三角形的第三边法则(即三角形的两边之和应大于第三边)，用一个传感器节点覆盖超过其直径，即d1+(RS+d2)＞2RS.因此，如果下列2 个条件之一成立，则可建立最佳部署：

图1 边界覆盖的最佳2D 部署示例Fig.1 An example of the optimal 2D deployment for boundary coverage

在这种情况下，需要2([L/2RS]+[W/2RS]+1)个节点覆盖矩形的边界.

一般情形[图1(b)]如果不满足上述2 个条件之一，则基于对述特殊情形的观察，采用以下部署策略.首先用并排包装的[L/2RS]个节点覆盖L，然后在角上构造一个直角三角形，其斜边长度为2RS，另外两条边分别为2d1=L(mod2RS)和d1,new=将一个传感器节点部署在覆盖来自L的d1和来自W的d1,new的那个角上.取Wnew=Wd1,new并执行相同的部署过程，将保证全部角上最大的边界覆盖，直至最后一个角，其中需要一个额外的传感器节点，边界覆盖一个矩形区域所需的传感器节点总数为：

式中：

由于要监测的区域相比于单个传感器节点的感知区域要大，故覆盖一个矩形区域的节点数就可以近似为2([L/2RS]+[W/2RS]).

2.1.2 边界覆盖的最佳3D 部署 边界覆盖3D最佳传感器部署比2D 情形复杂，可通过确定覆盖立方体区域表面所需的最小传感器节点数解决.由于把传感器节点的覆盖区域建模为一个封闭的球，故边界覆盖问题需要确定由传感器节点覆盖的立方体表面上的全部点.为此，首先定义感知区域和边界平面的交点，然后将它用于确定边界覆盖所需的最小传感器节点数.

定义11球面上的一个大圆就是该球与通过球心的平面的交点.

定义12一个传感器覆盖的厚度θ定义为覆盖空间中一个点的传感器节点的平均数量.令θ为每个基本区域体积的一个感知区域的体积，即：

式中：n为活跃传感器节点数，Vi为传感器Si的感知区域的体积，VT为感知区域Ri的总体积.

定义13以X1，X2，···，Xn为中心的球的覆盖半径R就是覆盖区域R的最小感知半径.

定理2边界覆盖一个3D 立体区域的传感器节点的最佳部署位置就是球的位置，其中心在立方体的每个面上形成间距Λ=1.732 2RS的晶格.

证明在2D 中，当圆心位于六边形晶格的顶点时，就得到具有圆形区域的最佳覆盖.设相邻顶点之间的距离是一个单位，则整个区域可以被覆盖半径为RC==0.577 3(完全覆盖一个区域的最小感知半径)的圆盘覆盖.这样的晶格是周期性的，且是完全还原的.此外，覆盖厚度θ=2π/=1.209 2(覆盖该区域中一个点的传感器节点的平均数量).因此，如果相邻圆盘中心之间的间距等于Λ=RS/0.577 3，则部署就是最佳的.因此，覆盖一个3D 立体区域边界的最佳部署是将球采用间距Λ=1.732 2RS放置在立方体的每个面上的晶格的中心.考虑一个边长为a(a相比于RS足够大)的立方体区域R，为实现R的边界覆盖，感知半径为RS的传感器节点数的下界可近似为：

定义14一个RS-条带模式由一串RS圆盘构成，这些圆盘沿一条垂直线放置，使得任意两个相邻节点中心之间的距离为

完全覆盖矩形的部署策略是通过放置平行于y轴的RS-条带的m列实现的，任意两个相邻RS-长条中心之间的距离为1.5RS.

在一个全局直角坐标系中，原点位于矩形的左底部，将m个RS-条带平行于y轴放置，每个条带中有n个圆盘，以完全覆盖矩形.第k行(1≤k≤n)和第l列(1≤l≤m)圆盘的中心位于[xkc,ykc]：

由于目标是采用建模为3D 球的传感器节点边界覆盖一个3D 立方体，故这个问题可以定义为用圆圈完全覆盖立方体的每个面.然而，一些球可能会对立方体的多个面产生作用，从而导致更多的边界覆盖.设在x-y平面上的立方体的第一行在方程组的圆盘中切割x-z平面：

对于x-z平面中的正方形，开始从x轴上方的一条线覆盖在d=(1-(/2))RS的面，得到边a和a1=a-d的一个矩形，并继续执行覆盖模式，以完全覆盖立方体的一个面.对于立方体的所有其他面也是如此，因此需要覆盖每个边为a的3 个正方形以及边为a和a1=a-d的3 个矩形.所以覆盖边为a的一个立体区域所需的传感器节点总数为：

如果监测区域是一个球形区域而不是一个立方体区域，则最佳部署球的全部中心以覆盖球面区域就位于球的表面，且边界覆盖一个3D 球形区域R，建模为球的传感器的最佳部署位置就是圆圈的中心位置，这些圆圈在球R的表面形成一个密集覆盖，如图2 所示.

图2 球形区域表面上大量圆圈的最密集覆盖Fig.2 The densest covering of a large number of circles on the surface of a spherical region

定理3边界覆盖一个半径为 ℜ的球形区域R的传感器节点数的下界为n=1.76 ℜ/(1-cosRS).

证明由于关心的是覆盖球边界所需的传感器节点数的下界，所以把这个问题看作一个包装问题，得到包装球的边界所需圆的最小数目，圆的面积计算为球覆盖的面积.在单位球面上，半径为r(rad)的圆的面积S为：

因此，如果在单位球面上存在半径为RS的不重叠的n个圆，则包装密度D为：

由于目标是最小化边界覆盖球形区域所需的传感器数量，这相当于寻找覆盖球形区域表面的许多圆的最致密的包装.由于关心的是下界，取D=0.88，则n=[1.76 ℜ/(1-cosRS)].

2.2 边界覆盖的选择前面的结果不仅实现了边界覆盖区域R的最佳部署，同时考虑到监测区域的边界覆盖，可以很容易找到边界覆盖所需的传感器节点数量及其位置；如果传感器节点已经部署，并选择这些传感器节点的一个子集保持活跃，就可以定义一个最佳性度量.WSN 边界覆盖的最佳性度量是网络中活跃边界传感器节点数与可以边界覆盖同一区域的最小传感器节点数的比值，也就是与传感器节点的最佳部署相比，监测区域中消耗的过剩能量的度量.一个最佳度量较低的网络将使得监测该区域的能量支出减少.

3 仿真及结果

仿真采用Matlab7.0 并结合C++进行，考虑覆盖大小为10(单位长)×10(单位长)的2D 区域和大小为10(单位长)×10(单位长)×10(单位长)的3D 区域所需的传感器节点数.测试边界覆盖节点的随机部署、最佳边界部署、边界覆盖选择、文献[10]和文献[14]的覆盖算法，并对它们进行比较；为了测试边界覆盖，将区域划分为2D 或3D 网格，通过生成占用网格和检查网格中的第1 行和最后一行以及第1 列和最后一列是否被覆盖，测试边界覆盖.如果第1 行和最后一行以及第1 列和最后一列中的所有单元格都被占用，则整个区域被边界覆盖.

图3 为当传感器节点随机部署时，采用最佳2D覆盖算法寻找区域10(单位长)×10(单位长)的最佳边界覆盖，节点的感知半径为1 (单位长)，最开始不同数量的节点采用均匀分布随机部署在该区域.从图3(a)可见，采用本文的最佳边界部署和边界覆盖选择算法的平均最佳度量为0.728，即在最佳边界覆盖中活跃节点平均节省了27.2%；图3(b)比较了采用随机部署、最佳边界部署、边界覆盖选择、文献[10]和文献[14]的覆盖算法对于不同感知半径所需的传感器节点数.可以看出，本文的边界覆盖选择和最佳边界部署算法明显优于随机部署、文献[10]和文献[14]的覆盖算法，而且随着感知半径的增大，这种优势愈加明显.

图3 2D 情形下不同算法的所需传感器节点数比较Fig.3 Comparison of the number of sensor nodes required by different algorithms in 2D case

图4 为3D 情形得到的结果.从图4(a)可见，当 随 机 部 署1 500、2 000、2 500、3 000、3 500 和4 000 个节点时，得到的平均最佳度量为0.877，即在最佳边界覆盖中活跃节点平均节省了12.3%；从图4(b)可见，本文的最佳边界部署和边界覆盖选择算法对于不同半径所需的传感器节点数也明显少于随机部署、文献[10]和文献[14]的覆盖算法.

图4 3D 情形下不同算法的所需传感器节点数比较Fig.4 Comparison of the number of sensor nodes required by different algorithms in 3D case

用于评价覆盖系统寿命的指标为总的边界覆盖寿命，它是指覆盖系统在边界覆盖下降到其特定阈值下(如90%)之前的连续工作时间.假设每个传感器节点的初始能量、发射、接收、空闲和休眠模式的功耗已知，且当节点能量耗尽时被禁用，节点部署密度分别为300 和600，对于每个密度，节点随机分布在10×10 区域网络中.随着时间的推移，传感器节点将由于缺乏能量而被禁用，并在区域的边界上留下一些覆盖孔.图5 所示为节点部署密度分别为300 和600 时初始网络的边界覆盖、边界覆盖选择、文献[10]和文献[14]覆盖算法的边界覆盖寿命比较.从图5(a)可见，大约在1 600、1 680 s和1 750 s 后，初始网络的边界覆盖百 分比、文献[10]和文献[14]覆盖算法的边界覆盖百分比将下降至90%以下，而采用本文的边界覆盖选择算法要在大约2 450 s 后边界覆盖百分比才下降至90%以下；从图5(b)可见，当将部署节点数增加到600 时，初始网络的边界覆盖百分比、文献[10]和文献[14]覆盖算法的边界覆盖百分比将分别在大约1 790、1 850 s 和1 900 s 后下降至90%以下，而本文的边界覆盖选择算法则在2 690 s 后边界覆盖百分比下降到阈值90%以下.显然，采用本文的边界覆盖选择算法获得的网络边界覆盖寿命要好得多；图6 所示为当部署节点数为600 时，将覆盖区域边界划分为1 000 个网格点，并测试在运行边界覆盖选择算法前后有多少个传感器节点覆盖每个网格点.可见，在启动算法之前，边界覆盖程度远高于运行算法后，这意味着随机部署由于给定边界区域中的太多活跃节点而浪费了大量的能量.在运行算法后，大多数冗余边界节点被禁用，从而导致节点的节能部署.

图5 不同部署传感器节点数的网络边界覆盖寿命比较Fig.5 Comparison of network boundary coverage lifetime with different number of deployed sensor nodes

图6 运行边界覆盖选择算法前后的边界覆盖程度比较Fig.6 Comparison of boundary coverage degree before and after running boundary coverage selection algorithm

4 结束语

本文研究了WSN 中的边界覆盖问题，提出了计算给定区域边界覆盖所需传感器节点最小数量的算法.不同于该领域所进行的大多数研究，本文研究了2D 和3D 一般情形.还提出了一种最佳性度量表明WSN 的能量效率，可作为在WSN 的两个不同部署之间进行选择的有用手段.仿真实验结果表明，本文提出的最佳边界部署和边界选择覆盖相比于传统的随机部署覆盖和其他边界覆盖算法有更好的覆盖性能.未来研究可以采用本文提出的算法作为WSN 的跟踪应用.