移动传感器网络中路径扫描覆盖问题研究

缪欣，陈璇，鲍红莹，张静轩，余炜

（1.华东理工大学 数学学院，上海 200237；2.华东理工大学 商学院，上海 200237）

0 概述

随着无线通信技术、传感技术、微机电系统等迅速发展，无线传感器网络得到了广泛应用，并逐渐在军事国防、抢险救灾、生态监测、医疗护理、智能家居、目标保护与追踪等领域体现出越来越高的使用价值［1-2］。传感器网络的典型系统结构包括感知、通信、供能、数据处理等单元［3-4］。节点感知、接收和处理被覆盖区域的信息，并通过接收发送器将信息传输至远程控制中心［5］。由于信息传输的质量和及时性与节点覆盖的方式有较大联系，因此覆盖问题是无线传感器网络中基本问题之一［6-7］。

在传统的静态覆盖场景中，网络管理者需要部署大量的无线传感器，因此产生不必要的能量消耗、高额的运营成本和维护成本，而解决这些问题需要良好的调度机制。LI等［8］提出基于兴趣点的扫描覆盖机制，大幅减少移动传感器的部署数量，延长传感器网络使用寿命。

在扫描覆盖的应用场景中，网络管理者采用移动的无线传感器对区域内各个分散的POI 进行定期扫描，以满足POI 的覆盖间隔需求。LI等［8］将扫描覆盖应用到无线传感器网络中，并证明扫描覆盖问题是一个NP-Hard问题。DU等［9］提出OSweep 算法，并设计一个新的启发式算法MinExpand，实验结果表明这2 个算法的性能均较好。CHEN等［10］提出能量约束扫描覆盖问题，并针对有距离约束和基站成本的扫描覆盖问题设计近似比为7的MinDCSC-SB算法。CHEN等［11］通过减少传感器移动距离进行能量约束，提出EEMA 算法，并安排移动传感器到划分后的区域中。GORAIN等［12］混合静态和移动传感器来减少能量消耗，提出近似度为5 的算法，并进行模拟实验。LIANG等［13］针对能量约束情境提出最小距离约束扫描覆盖问题并展开研究，其目标为在能量有限情境下找到完成扫描覆盖的移动传感器及其轨迹的最少数量。NIE等［14］通过假设移动传感器在不同单位路段所产生的能耗不同，将能量限制扫描覆盖扩展到一般能量限制扫描覆盖，并进一步提出GERSC 问题，即在能量约束条件下最小化扫描覆盖范围内所需的移动传感器数量。ZHANG等［15］综合考虑有权重目标以及返回时间约束的无线传感器扫描覆盖问题，提出区域覆盖算法，并采用仿真实验说明该算法相比MinExpand 等算法的平均扫描覆盖周期更短，路径有效率更高。文献［16］处理了周期性覆盖兴趣点进行多移动传感器扫描覆盖调度的问题，并进一步提出CycleSplit、HeterocyceSplit 和PathSplit 3 种常数因子近似，以最小化不同场景下移动传感器的最长扫描周期。GUANG等［17］以最大化POI 扫描覆盖价值为目标，设计随机取整的近似算法和改进的贪心算法。实验结果表明2 种算法的求解质量虽略低于整数规划算法，但运行时间均更快。SHENG等［18］考虑到传感器感知范围受限等问题，提出多目标优化的算法，同时使节点的覆盖面最大及扫描路径最短，仿真实验表明该算法在保证覆盖率的同时能够较大程度降低能耗。LIU等［19］针对带返回时间约束的扫描覆盖问题提出最小化移动传感器节点数目问题，并针对该问题提出G-MSCR 和Min DExpand 算法。

目前的研究主要以最少化传感器数量、最小化扫描成本为目标，并在此基础上考虑有界区域、距离约束、周期性返回基站等问题，其中大多数为非线性模型，一般无法直接求解。然而，在很多场景中，传感器成本较高，数量有限，可能出现某些POI 无法在扫描周期内被覆盖的情形，导致POI 信息时效性下降。此时，扫描覆盖成本除传感器耗用成本之外，还包括部分POI 未被及时扫描覆盖产生的罚时代价。

本文研究最少传感器数量-最小罚时路径扫描覆盖（Minimum Sensor Number and Punishment Sweep Coverage on Path，MNPSCP）问题，通过调度移动传感器扫描给定路径上的POI 集合，使传感器使用数量以及产生的POI 总罚时成本之和最小。将该问题转换为整数规划问题，但由于该整数规划解空间很大［20］，只能高效求解中小规模的实例，因此本文进一步设计贪心算法、遗传算法和遗传模拟退火算法，从而提高求解质量和算法局部寻优能力。

1 MNPSCP 模型

在很多场景中，网络管理者需要调用传感器对某一条路径上的POI 进行扫描覆盖。对于给定路径上 的POI集合P={1，2，…，n}，配备传感器集合S={1，2，…，m}，其中第i个传感器的移动速度为vi，第j个POI 的扫描周期为Tj。在扫描覆盖的场景中，每个POI 在其扫描周期内均至少被覆盖一次，即实现及时扫描覆盖。在传感器数量有限的情况下，若存在扫描覆盖方案能够满足扫描覆盖需求，则探究的问题是，如何在确保分布于一条路径上的POI 均能在各自扫描周期内被覆盖的条件下，通过调度移动传感器使其耗用成本最小。由于网络管理者需要在网络节点上预先完成对无线传感器的数量以及路径的规划，因此不必考虑算法对传感器的能耗。

将第i个传感器以第j个POI 为起点向右最远可以扫描覆盖的POI 集合定义为Cij，用变量xij表示传感器i是否按照Cij进行扫描覆盖，表达式如式（1）所示：

由此可得如下整数规划模型ILP-1：

式（2）的含义是所有的POI 都需要被扫描覆盖，式（3）的含义为每个传感器只能选择一种扫描方案，即只能被使用一次。

以上描述了POI 在其扫描周期内均被扫描覆盖的情形，但若对于上述定义的扫描覆盖方案，所有POI 均不能被及时扫描覆盖，则该模型无可行解。此时，对于未被及时扫描覆盖的POI，该模型也没有考虑到信息时效性下降而产生的罚时成本。对此，本文放宽了对POI 扫描覆盖周期的限制，进一步提出MNPSCP 问题：针对所有分布在一条路径上的POI，通过调度移动传感器使扫描方案的传感器耗用成本和POI 的罚时成本之和最小。在传感器数量充足时，罚时成本为0，生成所需传感器数量成本最少的监测方案；在传感器数量不足以完成对所有POI的及时扫描覆盖时，传感器耗用成本固定，生成罚时成本最少的监测方案。罚时成本的计算方式：为POI 分配一个惩罚算子，惩罚算子和超出POI 扫描周期的时间共同决定了惩罚值，且其随超时时间增加而不断增大，最终给出POI 全覆盖的监测方案，使产生的惩罚值之和最小。

传感器i以第l个POI 为左端点，可能的扫描覆盖方案为{l}，{l，l+1}，…，{l，l+1，…，n}，因此，传感器i所有可能的扫描覆盖方案共有p=种。将第i个传感器的第j个扫描覆盖方案定义为Cij，用变量xij表示第i个传感器是否按照第j个方案扫描覆盖，表达式如式（1）所示，由此可得整数规划模型ILP-2：，约束条件如式（2）～式（4）所示。其中：f为惩罚算子；tij为第i个传感器的第j个方案的超时时间；f(tij)为对应的惩罚值。模型ILP-2 的含义为调度移动传感器扫描给定路径上的POI 集合，使其耗用成本以及产生的POI 总罚时成本之和最小。总罚时成本的计算方式：为所有POI 分配一个惩罚算子，根据未被及时扫描覆盖的时间计算每个POI的罚时代价，并最终求和［21］。

由于整数规划只能求解中小规模的实例，为求解大规模的实例，本文分别设计了贪心算法、遗传算法和遗传模拟退火算法。

2 MNPSCP 问题的贪心算法

本节将针对MNPSCP 问题设计贪心算法，以快速高效求解［22］MNPSCP 问题。贪心算法的主要思想是在选择传感器的过程中，每次都优先选择未超时且覆盖POI 数量最多的传感器，若传感器全部用完仍有POI 未被覆盖，则选择加入此未被覆盖的POI后罚时最小的传感器。贪心算法具体如下：

算法1贪心算法

输入POI集合P={1，2，…，n}和相邻POI之间的距离D={d1，d2，…，dn-1}，其中：第l个POI 的扫描周期为Tl；dl为第l个POI与第l+1 个POI之间的距离；传感器集合S={1，2，…，m}；传感器i的移动速度为vi

输出传感器集合S对POI 集合P的扫描覆盖方案C，即每个传感器应该去扫描哪个POI 子集

1）对于任意的i∈S和l∈P，根据POI 的扫描周期和距离计算Pil，Pil为第i个传感器以第l个POI 为起点向右最远可以扫描覆盖的集合，令使用的传感器集合I=∅，C=∅；

3 MNPSCP 问题的遗传算法

遗传算法作为一种仿生学方法，能够有效解决NP 难问题［23-24］，根据决策变量的0-1 二值变量类型，结合染色体的二进制编码和遗传操作，本文在染色体生成和评估过程中基于模型的约束条件对贪心策略进行调整，使模型能够在较短时间内获得满意的近似解。遗传算法具体如下：

算法2遗传算法

输入POI 集合P={1，2，…，n}和相邻POI 之间的距离D={d1，d2，…，dn-1}，其中：第l个POI 的扫描周期为Tl；dl为第l个POI与第l+1 个POI 之间的距离；传感器集合S={1，2，…，m}；传感器i的移动速度为vi

输出传感器集合对POI 集合的扫描覆盖方案

1）染色体编码与种群的初始化。每个染色体由n个节点组成s1s2…sn，每个节点sl代表1 个POI 节点，采用一位二进制编码，即sl=0 或1。编码表示的含义：若该染色体中=k，则说明编码为1 的节点sl将路径分割为k+1 个片段，每个片段代表1 个传感器规划的路径，扫描所有规划的路径需使用k+1 个传感器。按照上述编码，随机产生一定数量的染色体，每个染色体随机产生最多m-1 个编码为1 的节点，以初始化种群，种群的规模为N。

2）计算适应度函数。由于遗传算法中适应度越大越有利于种群进化，而模型的目标函数则越小越好，因此取目标函数的倒数作为适应度值。每个染色体的目标函数值按照下述方式计算：设=k，则路径分为k+1 个片段，每个片段的路径长度为r1，r2，…，rk+1，将路径从大到小排序后，设r1>r2>…>rk+1，若k+1>m，即使用的传感器数量超出了给定的限制，则目标函数值为无穷大；若k+1 ≤m，则将传感器的速度也从大到小排序，设v1>v2>…>vm，则安排速度为vi的传感器扫描长度为ri的路径，其超时时间为ti，若传感器未被调用，则超时时间为0。适应度函数形式化定义如下：

3）遗传操作。对种群中的个体根据适应度随机进 行遗传操作，包括选择、交叉、变异。

（1）选择。采用随机竞争选择法，假设S1，S2，…，SN为种群中各个个体的适应度，其中N为种群中的个体数量，种群中第t个个体的适应度为St，其被选择的概率为，那么=1，随机选择2 个个体Sa和Sb。

由好产业与好龙头带领，解决贫困人口收益机制问题。因利益机制不健全这一问题在农业产业扶贫中较为普遍，要将健全的农业产业扶贫利益机制相结合，共享理念贯彻落实其中，秉承长短结合的原则，使贫困人口真正受益。另外，推广订单帮扶模式，政府财政扶持资金根据相关比例落实到集体，村集体根据资产入股企业，与企业签订协议，建立合理的受益分配机制，企业形成利益机制，既能够提高村民的收益，也能够调动企业的积极性。

（2）交叉。采用两点交叉法，根据给定的交叉概率pu对选择的2 个个体进行交叉，若交叉，则随机选择2 个交叉点，将2 个个体交叉点之间的染色体交换组成新的个体；若不交叉，则这2 个个体将直接作为新的个体。

（3）变异。对于2 个新的个体，根据给定的变异概率pv进行变异，随机选择1 个染色体节点sl，并作取反运算。

重复上述遗传操作，产生新的种群，直到新的种群与原种群个体数量一致。

4）进化迭代。设置最大进化代数MAXGEN，重复步骤2 和步骤3，当进化次数达到MAXGEN 时停止计算，取适应度最高的个体作为模型的近似解。

4 MNPSCP 问题的遗传模拟退火算法

虽然遗传算法的全局搜索能力较强，但是算法的“早收敛”特点影响了求解结果［25］。由于模拟退火算法可以有效避免传统遗传算法的早熟现象，因此本文考虑将遗传算法和模拟退火算法相结合，使算法更加有效。其基本思路为在遗传操作后引入模拟退火操作。

算法3遗传模拟退火算法

输入POI集合P={1，2，…，n}和相邻POI之间的距离D={d1，d2，…，dn-1}，其中：第l个POI 的扫描周期为Tl；dl为第l个POI与第l+1 个POI之间的距离；传感器集合S={1，2，…，m}；传感器i的移动速度为vi

输出传感器集合对POI 集合的扫描覆盖方案

1）染色体编码与种群的初始化。

2）计算适应度函数。

3）遗传操作。

4）模拟退火操作。

（1）初始化参数。设初始温度Ts，结束温度Te，降温系数α。

（2）对于种群中的第t个个体，其适应度为St。为随机产生扰动，随机生成2 个点位l和l′，设l′>l，颠倒l和l′之间的染色体节点，即s1s2…sj-1sj′sj′-1…sjsj′+1…sn。

（3）对新产生的解计算适应度，设为Snew，若Snew>St，则将种群中的该个体替换为新产生的个体；否则，根据Metropolis 准则接受新解，即按照概率接受新解。

（4）降温过程。令Ts=αTs。

（5）若Ts>Te，则一直重复步骤（2）～步骤（5）。

5）进化迭代。设置最大进化代数MAXGEN，重复算法3 的步骤2）～步骤4），当进化次数到达MAXGEN时停止计算，取适应度最高的个体作为模型的近似解。

5 时间和空间复杂度分析

5.1 贪心算法

算法1 中的步骤1 需要的运行时间为O(mn2)，步骤2～步骤4 需要的运行时间为O(mn)，步骤5 需要重复步骤2～步骤4 至多m次，因此步骤1～步骤5需要的运行时间为O(m2n2)。步骤6 和步骤7 的运行时间相对于步骤1～步骤5 的更少，因此贪心算法的时间复杂度为O(m2n2)。

贪心算法的空间复杂度主要体现在步骤1 中的扫描覆盖方案消耗内存，其他变量则相对为常数，故空间复杂度为O(mn2)。

5.2 遗传算法

算法步骤1 需要的运行时间为O(Nn)，步骤2 需要对种群中的每个个体计算适应度，遍历个体需要的运行时间为O(n)，排序需要的运行时间为O(nlogan)，遗传操作的运行时间相对步骤1 和步骤2的更少，因此步骤2 和步骤3 需要的运行时间为O(Nnlogan)。由于需要迭代MAXGEN 次，因此遗传算法的时间复杂度为O(MAXGEN×Nnlogan)。

遗传算法中种群的复杂度为O(Nn)，而适应度评估、遗传操作等均可以原地实现，故遗传算法的空间复杂度为O(Nn)。

5.3 遗传模拟退火算法

6 实验结果与分析

为检验上述算法的性能，本文基于MATLAB编写程序进行仿真实验。在仿真场景中，传感器和POI的参数范围参考文献［4，26］，并由程序随机生成，设置罚时算子为线性算子f(tij)=αtij。传感器的移动速度范围为8～10 m/s，POI 之间的距离为80～120 m，扫描周期为80～100 s。实验环境为windows10 系统，12 GB 内存，Intel i7-7500U 处理器。

由于整数规划模型可以较快地求解中小规模实例，而较大规模实例难以求解，故本实验在不同的惩罚算子下，对比在较大规模实例中不同算法的性能。由于需要对比算法产生的近似解与最优解的差距，因此将传感器分为每组10 个，同组内移动速度相同，不同组的传感器移动速度不同，以简化变量、加快求解速度。实验将对比整数规划、贪心算法、遗传算法和遗传模拟退火算法在不同惩罚算子和数据规模下的运行时间以及求解质量，以完成对算法性能的综合评价，结果如表1 所示，其中：近似解是指将算法重复执行10 次的结果中最优的解；平均解是指算法执行10 次所得到的所有解的平均值。

表1 大规模分组实验的结果对比Table 1 Comparison of results of large-scale grouping experiment

由表1 可知，整数规划求出的是最优解，具有最低的覆盖代价。对于贪心算法而言，其运行时间最短，但是求出的解与最优解差距较大，质量较差。遗传算法虽然运行时间比贪心算法时间长，但解的质量比贪心算法要好，在算法执行次数较多时普遍可以得到比贪心算法更优的解，但仍有求解不稳定的问题，求解平均值有时比贪心算法好，有时差。遗传算法经过模拟退火操作优化后，稳定性有了明显提高，其求解的平均值优于贪心算法，解的质量也明显优于其他算法。

由于遗传算法的“早收敛”对求解结果影响很大，因此本文引入了模拟退火算法。为对比遗传算法和模拟退火算法的局部寻优能力，本文设置仿真实验，实验中每种算法迭代1 000 次，若每次迭代得出的结果比迭代前的最优结果更优，则认为算法跳出了局部极值，不同算法在不同传感器数量和POI数量下跳出局部极值的次数对比结果如表2 所示。已知同一条件下跳出局部极值的次数越多，局部寻优能力越强。由表2 可以看出，遗传模拟退火算法跳出局部最优的能力明显强于遗传算法。

表2 不同算法跳出局部极值的次数对比Table 2 Comparison of times for different algorithms to jump out of local extremum

综上可知，遗传模拟退火算法较好地提升了模拟退火算法的局部寻优能力，但对于全局寻优能力没有明显提升，求出的解与最优解仍有差距，收敛速度相对遗传算法较好，适用于大规模实例求解。

7 结束语

本文研究了移动传感器网络中最少传感器数量-最小罚时路径扫描覆盖问题，将该问题转换为整数规划模型，并设计贪心算法、遗传算法以及遗传模拟退火算法。实验结果表明：贪心算法的耗时远低于整数规划，但解的质量较差；与贪心算法相比，遗传算法的运行时间更长，解的质量有所提高，但仍有不稳定的问题。经过模拟退火操作优化后，遗传算法的稳定性得到明显提高，解的平均质量优于贪心算法，且运行时间比整数规划少。本文的创新点在于放宽POI 扫描覆盖周期的限制，对已有研究中扫描覆盖成本最小问题进行了拓展，但本文只考虑了一维给定路径的扫描覆盖问题，下一步可以将其拓展至二维场景，如探究树形结构或平面上点或网格结构中的最少传感器数量-最小罚时路径扫描覆盖问题。