0 引言

在无线传感器网络(Wireless Sensor Network,WSN)研究中，覆盖问题是基本问题之一，它直接影响到WSN的工作效率和质量。在移动无线传感器网络的应用中，因为移动传感器节点的感知范围受限，其覆盖分析就是一个针对目标区域的扫描覆盖问题。近年来国内外对移动传感器节点的扫描覆盖目标区域的算法也有一些研究。王伟等^[1]提出了一种模拟退火算法的扫描覆盖机制，比传统的扫描覆盖表现出更好的性能；雍毅等^[2]提出了一种动态兴趣点的扫描覆盖，更能适应动态的目标区域；李小康等^[3]提出了一种关于路径增量与覆盖间隔差异的插入启发式算法；刘晨光等^[4]设计了一种使用聚类方法的扫描覆盖方法；舒莉等^[5]设计了一种关于兴趣点问题的扫描覆盖；林锋等^[6]设计了一种扫描覆盖方法，它使用具有移动性的传感器节点当作辅助来修复覆盖洞。上述几种算法都是通过多个移动传感器节点之间的编队对覆盖洞进行扫描覆盖，没有考虑到节点的能耗和生命周期，也没有考虑在含有障碍物的情况下的路径规划等问题^[7]。

在上述研究的理论基础上，本文提出了一种优化的扫描覆盖算法。在目标区域中，采用双目标优化策略对单个移动传感器节点进行路径规划，一方面使得节点的覆盖面最大化，另一方面使扫描覆盖的路径最短。通过优化扫描覆盖算法，既降低了节点在扫描覆盖的过程中的能耗，又延长了节点的生命周期。

1 网络模型

本文将计算域定义为D，紧子集定义为R²,障碍物的集合定义为Ω，一个封闭的集合包含了有限数量的连接部件和多个特定的障碍物。传感器节点的半径为r，水平集函数ψ(x)表明的环境包含了两种情况：如果定义域的覆盖部分是在障碍里面，那就表示为负的；如果定义域的覆盖部分是在障碍外面，那就表示为正的。本文定义ψ(x)是障碍物Ω边界的典型符号距离函数。一个传感器节点x位于存在障碍物Ω的计算域D中，x为起始点，以直线的形式向前移动并且在点y的位置停下。如果x和y的绝对值之差小于等于r，那么就表示点y在障碍物的边界或者之内。部分公式概念如表 1所示。

下面定义半径为r的传感器节点移动到点y位置的检测面积的水平集函数φ：

$\varphi (x,r;y)=\underset{z\in L(x,y)}{\mathop{\min }}\,\{\psi (z),r-|z-x|\}$

(1)

其中L(x，y)表示x到y的连线部分。z的位置在障碍物的边界时ψ(z)=0，在障碍物内的时候ψ(z)＜0,在障碍物外界的时候ψ(z)>0。

2 移动传感器节点的路径规划 2.1 节点单位置的路径规划

考虑了移动传感器节点单位置的最大覆盖，更确切地说就是将移动传感器节点移动到最大覆盖范围V的最佳位置。本文使用梯度上升的方法来实现这个目标，即本文按照梯度流来移动节点x的位置，公式^[8]如下：

${{\partial }_{t}}^{x}=\Delta xV(x)$

(2)

其中，Δx表示关于x的梯度算子。梯度算子可以近似地看作有限差分方程。如本文使用中心差分方程可以得到：

${{\partial }_{t}}^{x}={{D}_{0}}^{h}V(x)$

(3)

其中h表示空间步长。

为了能够清晰地表示出移动传感器节点达到最大化覆盖的移动路径，本文在目标区域中设置了三个障碍物，并且通过梯度流的方法移动传感器节点，得到最大化覆盖面积。如图 1所示，表示传感器节点的初始位置；如图 2所示，表示移动传感器节点x位移到与障碍物相切的位置，达到最大化覆盖面积的位置^[9]。移动传感器节点在目标区域中移动，当碰撞到计算域D的边界时，停止计算。其中阴影部分表明三个障碍物，虚线圆圈表示传感器节点的感知面积。

2.2 节点多位置的路径规划

由移动传感器节点单位置发散到移动传感器节点的多位置，本文设{x₁，x₂，…，x_m}表明m个传感器节点，{r₁，r₂，…，r_m}表明m个传感器节点的半径，每个传感器节点的覆盖范围不同^[10]。总的检测范围是多个传感器节点的联合覆盖，多个传感器节点的水平集函数如下所示：

$\varphi ({{x}_{1}},...{{x}_{m}},{{r}_{1}},...{{r}_{m}};y)=\underset{i=1,2,...,m}{\mathop{\max }}\,\varphi ({{x}_{i}},{{r}_{i}};y)$

(4)

另外，多个传感器节点检测面积V如下所示：

$V({{x}_{1}},{{x}_{2}},...{{x}_{m}})=\int_{\Omega }{\left( H\varphi ({{x}_{1}},...{{x}_{m}},{{r}_{1}},...{{r}_{m}};y) \right)dy}$

(5)

其中H表示一维的赫维赛德函数。

在目标区域中，两个移动传感器节点的情况下，需要寻找两个新的位置达到彼此的覆盖范围不相交，这样就使得覆盖面积达到最大化^[11]。如图 3所示两个移动传感器节点的初始状态，如图 4所示两个移动传感器节点通过移动达到与障碍物相切，最终达到最大化覆盖面积，其中阴影部分表明三个障碍物，虚线圆圈表明传感器节点的检测面积^[12]。

当有三个移动传感器节点时，本文也考虑了多个节点的局部优化。图 5为三个传感器节点的初始状态；图 6为三个传感器节点达到的局部最大化覆盖。其中阴影部分表示三个障碍物，虚线圈表示传感器节点的覆盖范围^[13]。

2.3 解锁方法

在移动传感器节点的扫描过程中，面对障碍物的阻拦时需要改变位移的路径^[14]。扫描过程中有可能会出现路径交叉的情况，这样会延长完成覆盖的时间^[15]。为了解决交叉路径问题，完成最短时间的优化，本文在交叉点的位置补充了两个移动的位置。这样就可以达到解锁的目的，完成最短时间的最大覆盖优化。如图 7所示，移动传感节点的四个位置出现交叉，此时本文在交叉点位置加上了两个移动位置完成解锁，如图 8所示。

为了能够清晰地表示出该方法如何解锁，本文给出了一般情况下的解锁方法。

步骤1 假设移动传感器节点的路径为x₁,x₂,…,x_m，其中路径线段x_ix_i+1和x_jx_j+1存在交叉点。

步骤2 假设路径线段的交叉点为x_inter，那么将x_inter分别加入到x_ix_i+1和x_jx_j+1两个路径线段之间。

步骤3 将交叉点加入到路径线段之后，对移动传感器节点的路径重新排序如下所示：x_i,x_inter,x_j,x_j-1,x_j-2,…,x_i+2,x_i+1,x_inter,x_j+1。

步骤4 重复步骤1到步骤3，直至路径中不存在交叉点。

一般解锁方法如图 9所示。

3 扫描覆盖算法设计

扫描覆盖问题的目标是以最少数量的移动传感器达到最大的覆盖面积。在扫描覆盖问题的相关场合中，决策者在目标区域布置少许的移动传感器节点进行周期性的覆盖，代替了大规模固定式传感器节点覆盖的间隔需要。由于目标区域覆盖所需的节点数量减少，目标区域覆盖所需的工作成本也随之降低。

在传感器节点覆盖功能的水平集框架中，目标区域被描述的正值表示在覆盖区域的障碍外，负值表示在障碍物内，零值表示在障碍物的边界。传感器节点直线前进遇到障碍物时，会导致覆盖范围丢失，如果目标区域中的点和传感器节点的线段不相交于任何障碍物，那么该目标区域的点就会被传感器节点所覆盖。本文考虑了传感器节点的有限覆盖范围，使用单个移动传感器节点代替多个固定传感器节点对目标区域进行扫描覆盖。对于存在障碍物的目标区域，本文通过移动传感器节点的路径规划方法实现最大化覆盖。扫描算法设计如下：

步骤1 将多个固定传感器节点，依次地加入到目标区域中，按照几何方式布置达到全覆盖。

步骤2 存在障碍物的情况下，利用单个移动传感器节点代替多个固定传感器节点，按原路径进行扫描覆盖。

步骤3 根据路径规划，使得移动传感器节点达到最大覆盖，通过位移多个节点所扫描的位置，达到节点的最大化覆盖面积，并且删除冗余的节点。

步骤4 按照最短路径算法Dijkstra，利用移动传感器节点求出全覆盖下的最优路径。

步骤5 如果初始化路径中存在交叉路径，那么使用解锁方法来达到收敛。

步骤6 计算原有路径长度和扫描覆盖之后的路径长度，进行比较。如果优化之后的路径长度较短，那就说明本文扫描覆盖方法的有效性；反之，则效果不佳。

4 仿真实验及性能评估 4.1 实验参数设置

本文采用Matlab 2012b仿真平台来进行仿真。平台是基于Intel Core i5-2300的CPU，4 GB的运行内存的PC。为了表示传感器节点的覆盖性能，本文分别在没有障碍物的情况和存在障碍物的情况下进行分析。

1) 无障碍物场景下的参数设置。

假定在20 m×20 m的目标区域内，依次布置的固定式传感器节点数N=16，节点的理想探测半径为r=6。无障碍物的仿真参数如表 2所示。

2) 有障碍物场景下的参数设置。

为了能够适应复杂地形，本文在实验过程中加入了障碍物的干扰，并且加大了目标区域和传感器节点的移动范围，使得实验结果更加具有真实性。假定在30 m×30 m的目标区域内，依次布置的固定式传感器节点数N=36，节点的理想探测半径为r=52/2。三个障碍物的参数为：障碍物一是以半径为22的圆形，障碍物二是以半径为102/3的圆形，障碍物三是边长为9的正方形区域。有障碍物场景下的仿真参数如表 3所示。

4.2 实验结果对比

1) 无障碍物场景。

本文使用16个固定式传感器节点依次部署在20 m×20 m的目标区域中，达到全覆盖的效果，如图 10所示。

接下来本文利用单个移动传感器节点按照原来的路径进行扫描，扫描过程按照几何的方法进行。

如图 11所示，移动传感器节点移动了16次位置，并且存在冗余覆盖面积。接下来本文会使用优化的扫描覆盖算法来对移动次数优化，防止移动传感器节点的能量耗尽。

由图 11可知，移动传感器节点代替固定传感器节点进行扫描覆盖完成后，明显存在冗余节点位置，冗余覆盖。使用本文提出的扫描覆盖算法，进行路径规划，并且将冗余节点位置去除。这样可以达到移动传感器节点以最少时间、最短路径，达到最大化覆盖面积的效果。如图 12可知，移动传感器节点移动了10次位置，达到了全覆盖的效果。

2) 有障碍物场景。

在含有障碍物的情况下，该算法先假设障碍物不存在，使用36个固定传感器节点依次部署在30 m×30 m的目标区域中，达到全覆盖的效果，如图 13所示。

接下来利用单个移动传感器节点按照原来的路径进行扫描，扫描过程按照几何的方法进行。如图 14所示，移动传感器节点移动了36次位置，并且存在冗余覆盖面积。接下来本文会使用优化的扫描覆盖算法来对移动次数优化，防止移动传感器节点的能量耗尽，来延长网络寿命。

此时加入障碍物，也就相当于在复杂地形下，移动传感器节点的路径位置，如图 15所示障碍物阻挡了多个传感器节点位置的感知面积。

经过扫描覆盖优化方法之后，去除冗余的移动传感器节点位置，减小了移动路径的长度，缩短了移动到全覆盖的时间，移动传感器节点位移了33次，如图 16所示。

4.3 计算开销性能和路径长度

由实验结果可知，在无障碍物场景下，在20 m×20 m的目标区域内，依次布置的固定式传感器节点数目N=16，节点的理想探测半径为r=6。通过几何方法求得的原有移动传感器节点的路径长度为60 m，优化后的扫描覆盖路径长度为36.27 m。在有障碍物场景下，在30 m×30 m的目标区域内，依次部署的固定式传感器节点数N=36，节点的理想探测半径为r=52/2，根据几何方法能够求得原有的移动路径长度为175 m，优化过后的扫描覆盖路径长度为164.48 m。由此可知本文设计的扫描覆盖方法的有用性。如表 4所示，分析了不含障碍物和含有障碍物两种情况的各种参数。

4.4 仿真对比

与传统扫描覆盖^[5]相比，本文采用的是单个移动传感器节点扫描覆盖，通过路径规划使得节点达到最大覆盖面积，而不是用多个移动传感器节点实行编队扫描覆盖，后者大幅增加了成本，也增加了能耗。下面对本文提出的单个移动传感器节点扫描覆盖方法和双节点编队的扫描覆盖方法进行仿真对比。如图 17所示，本文采用单个移动传感器节点和两个节点作对比，评估它们每个节点的时间和能耗。如图 18所示，在有限的时间内本文提出的单移动传感器节点和双移动传感器节点编队的覆盖率作出了对比。

根据图 17的仿真结果，在相同时间内本文提出的单个移动传感器节点，没有节点之间的编队和通信，减少了能量消耗，延长了节点的生命周期。这样可以确保移动传感器节点在维持覆盖的时间上能够延长。根据图 18的仿真结果可知，随着时间的增加，单移动传感器节点和双移动传感器节点的覆盖率都在增加，其中双移动节点的覆盖率较高些。

相比之下，虽然双移动传感器节点的覆盖率较高些，但是它的两个节点之间需要进行编队和通信消耗了部分能量，每个节点能耗是单移动传感器节点的近乎两倍。为了延长节点的生命周期，在满足覆盖维持的前提下，可以选择单移动传感器节点对目标区域进行扫描覆盖。

5 结语

本文提出了一种优化的扫描覆盖。在目标区域中，使用单个移动传感器节点来代替固定传感器节点，对目标区域进行扫描修复。通过节点的路径规划，使得节点的覆盖面最大化，同时扫描覆盖的路径最短。实验结果表明，本文提出的算法在适度降低覆盖率的情况下，可大幅降低移动能耗。