开放科学(资源服务)标志码(OSID)：

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

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

$ {x}_{ij}=\left\{\begin{array}{l}1, \mathrm{按}{C}_{ij}\mathrm{扫}\mathrm{描}\mathrm{覆}\mathrm{盖}\\ 0, \mathrm{不}\mathrm{按}{C}_{ij}\mathrm{扫}\mathrm{描}\mathrm{覆}\mathrm{盖}\end{array}\right. $

(1)

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

$ \begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\sum\limits _{i=1}^{m}\sum\limits _{j=1}^{n}{x}_{ij}\\ \mathrm{s}.\mathrm{t}.\sum\limits _{(i, j), l\in {C}_{ij}}{x}_{ij}\ge 1, \forall l\in P\end{array} $

(2)

$ \sum\limits _{j=1}^{n}{x}_{ij}\le 1, \forall i\in S $

(3)

$ {x}_{ij}\in \left\{\mathrm{0, 1}\right\}, \forall i\in P, j\in S $

(4)

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

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

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

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

2 MNPSCP问题的贪心算法

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

算法1   贪心算法

输入   POI集合$ P=\left\{\mathrm{1, 2}, \cdots , n\right\} $和相邻POI之间的距离$ D=\left\{{d}_{1}, {d}_{2}, \cdots , {d}_{n-1}\right\} $，其中：第$ l $个POI的扫描周期为$ {T}_{l} $；$ {d}_{l} $为第$ l $个POI与第$ l+1 $个POI之间的距离；传感器集合$ S=\left\{\mathrm{1, 2}, \cdots , m\right\} $；传感器$ i $的移动速度为$ {v}_{i} $

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

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

2）遍历所有$ {P}_{il} $，使$ \left|{P}_{{i}^{*}{l}^{*}}\right|=\underset{\begin{array}{l}1\le i\le m\\ 1\le l\le n\end{array}}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\left|{P}_{il}\right|\right\} $，记为$ {P}_{{i}^{*}{l}^{*}} $，即传感器$ {i}^{\mathrm{*}} $的扫描覆盖方案为$ {P}_{{i}^{\mathrm{*}}{l}^{\mathrm{*}}} $；

3）令$ S=S-\left\{{i}^{\mathrm{*}}\right\} $，$ C=C\bigcup \left\{{P}_{{i}^{*}{l}^{*}}\right\} $，$ I=I\bigcup \left\{{i}^{*}\right\} $，$ P=P-{P}_{{i}^{*}{l}^{*}} $；

4）令$ {P}_{il}:={P}_{il}-{P}_{{i}^{*}{l}^{*}}, i=\mathrm{1, 2}, \cdots , m, l=\mathrm{1, 2}, \cdots , n $；令$ {P}_{{i}^{\mathrm{*}}l}=\mathrm{\varnothing }, l=\mathrm{1, 2}, \cdots , n $；

5）若$ P=\mathrm{\varnothing } $，则算法停止，输出扫描覆盖方案$ C=\left\{{P}_{{i}^{\mathrm{*}}{l}^{\mathrm{*}}}\right\} $，对应使用的传感器集合I；若$ P\ne \mathrm{\varnothing } $且$ S\ne \mathrm{\varnothing } $，则重复步骤2~步骤5；若$ P\ne \mathrm{\varnothing } $且$ S=\mathrm{\varnothing } $，传感器集合无法满足式（2），进入步骤6和步骤7；

6）对于余下的$ l\in P $和扫描覆盖方案$ C=\left\{{P}_{{i}^{*}{l}^{*}}\right\} $，遍历所有$ T{P}_{{i}^{*}{l}^{*}}={P}_{{i}^{*}{l}^{*}}\bigcup \left\{l\right\} $，对于每个方案$ T{P}_{{i}^{*}{l}^{*}} $，计算对应的罚时$ {t}_{{i}^{*}} $，令$ {t}_{k}=\underset{i\in I}{\mathrm{m}\mathrm{i}\mathrm{n}}\left\{{t}_{i}\right\} $，$ {P}_{k{l}^{*}}=T{P}_{k{l}^{*}} $，即将$ l $并入到所有罚时最小的传感器扫描方案中；

7）$ P=P-\left\{l\right\} $，重复步骤6直到$ P=\mathrm{\varnothing } $。

3 MNPSCP问题的遗传算法

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

算法2   遗传算法

输入   POI集合$ P=\left\{\mathrm{1, 2}, \cdots , n\right\} $和相邻POI之间的距离$ D=\left\{{d}_{1}, {d}_{2}, \cdots , {d}_{n-1}\right\} $，其中：第$ l $个POI的扫描周期为$ {T}_{l} $；$ {d}_{l} $为第$ l $个POI与第$ l+1 $个POI之间的距离；传感器集合$ S=\left\{\mathrm{1, 2}, \cdots , m\right\} $；传感器$ i $的移动速度为$ {v}_{i} $

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

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

2）计算适应度函数。由于遗传算法中适应度越大越有利于种群进化，而模型的目标函数则越小越好，因此取目标函数的倒数作为适应度值。每个染色体的目标函数值按照下述方式计算：设$ \sum\limits _{l=1}^{n}{s}_{l}=k $，则路径分为$ k+1 $个片段，每个片段的路径长度为$ {r}_{1}, {r}_{2}, \cdots , {r}_{k+1} $，将路径从大到小排序后，设$ {r}_{1} > {r}_{2} > \cdots> {r}_{k+1} $，若$ k+1 > m $，即使用的传感器数量超出了给定的限制，则目标函数值为无穷大；若$ k+1\le m $，则将传感器的速度也从大到小排序，设$ {v}_{1} > {v}_{2} > \cdots> {v}_{m} $，则安排速度为$ {v}_{i} $的传感器扫描长度为$ {r}_{i} $的路径，其超时时间为$ {t}_{i} $，若传感器未被调用，则超时时间为0。适应度函数形式化定义如下：

$ S({s}_{1}{s}_{2}\cdots {s}_{n})=\left\{\begin{array}{l}0, \sum\limits _{l=1}^{n}{s}_{l} > m-1\\ \frac{1}{k+1+\sum\limits _{i=1}^{k+1}f\left({t}_{i}\right)}, \mathrm{其}\mathrm{他}\end{array}\right. $

(5)

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

（1）选择。采用随机竞争选择法，假设$ {S}_{1}, {S}_{2}, \cdots , {S}_{N} $为种群中各个个体的适应度，其中N为种群中的个体数量，种群中第$ t $个个体的适应度为$ {S}_{t} $，其被选择的概率为$ {p}_{{S}_{t}}=\frac{{S}_{t}}{\sum\limits _{t=1}^{N}{s}_{t}} $，那么$ \sum\limits _{t=1}^{N}{p}_{{s}_{t}}=1 $，随机选择2个个体$ {S}_{a}\mathrm{和}{S}_{b} $。

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

（3）变异。对于2个新的个体，根据给定的变异概率$ {p}_{v} $进行变异，随机选择1个染色体节点$ {s}_{l} $，并作取反运算。

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

4）进化迭代。设置最大进化代数$ \mathrm{M}\mathrm{A}\mathrm{X}\mathrm{G}\mathrm{E}\mathrm{N} $，重复步骤2和步骤3，当进化次数达到$ \mathrm{M}\mathrm{A}\mathrm{X}\mathrm{G}\mathrm{E}\mathrm{N} $时停止计算，取适应度最高的个体作为模型的近似解。

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

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

算法3  遗传模拟退火算法

输入   POI集合$ P=\left\{\mathrm{1, 2}, \cdots , n\right\} $和相邻POI之间的距离$ D=\left\{{d}_{1}, {d}_{2}, \cdots , {d}_{n-1}\right\} $，其中：第$ l $个POI的扫描周期为$ {T}_{l} $；$ {d}_{l} $为第$ l $个POI与第$ l+1 $个POI之间的距离；传感器集合$ S=\left\{\mathrm{1, 2}, \cdots , m\right\} $；传感器$ i $的移动速度为$ {v}_{i} $

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

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

2）计算适应度函数。

3）遗传操作。

4）模拟退火操作。

（1）初始化参数。设初始温度$ {T}_{s} $，结束温度$ {T}_{e} $，降温系数$ \alpha $。

（2）对于种群中的第$ t $个个体，其适应度为$ {S}_{t} $。为随机产生扰动，随机生成2个点位$ l $和$ l' $，设$ l' > l $，颠倒$ l $和$ l' $之间的染色体节点，即$ {s}_{1}{s}_{2}\cdots {s}_{j-1}{s}_{j'}{s}_{j'-1}\cdots {s}_{j}{s}_{j'+1}\cdots {s}_{n} $。

（3）对新产生的解计算适应度，设为$ {S}_{\mathrm{n}\mathrm{e}\mathrm{w}} $，若$ {S}_{\mathrm{n}\mathrm{e}\mathrm{w}} > {S}_{t} $，则将种群中的该个体替换为新产生的个体；否则，根据Metropolis准则接受新解，即按照概率$ {\mathrm{e}}^{{S}_{\mathrm{n}\mathrm{e}\mathrm{w}}-{S}_{t}} $接受新解。

（4）降温过程。令$ {T}_{s}=\alpha {T}_{s} $。

（5）若$ {T}_{s} > {T}_{e} $，则一直重复步骤（2）~步骤（5）。

5）进化迭代。设置最大进化代数$ \mathrm{M}\mathrm{A}\mathrm{X}\mathrm{G}\mathrm{E}\mathrm{N} $，重复算法3的步骤2）~步骤4），当进化次数到达$ \mathrm{M}\mathrm{A}\mathrm{X}\mathrm{G}\mathrm{E}\mathrm{N} $时停止计算，取适应度最高的个体作为模型的近似解。

5 时间和空间复杂度分析 5.1 贪心算法

算法1中的步骤1需要的运行时间为$ O\left(m{n}^{2}\right) $，步骤2~步骤4需要的运行时间为$ O\left(mn\right) $，步骤5需要重复步骤2~步骤4至多m次，因此步骤1~步骤5需要的运行时间为$ O\left({m}^{2}{n}^{2}\right) $。步骤6和步骤7的运行时间相对于步骤1~步骤5的更少，因此贪心算法的时间复杂度为$ O\left({m}^{2}{n}^{2}\right) $。

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

5.2 遗传算法

算法步骤1需要的运行时间为$ O\left(Nn\right) $，步骤2需要对种群中的每个个体计算适应度，遍历个体需要的运行时间为$ O\left(n\right) $，排序需要的运行时间为$ O\left(n\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\right) $，遗传操作的运行时间相对步骤1和步骤2的更少，因此步骤2和步骤3需要的运行时间为$ O\left(Nn\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\right) $。由于需要迭代MAXGEN次，因此遗传算法的时间复杂度为$ O(\mathrm{M}\mathrm{A}\mathrm{X}\mathrm{G}\mathrm{E}\mathrm{N}\times Nn\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n) $。

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

5.3 遗传模拟退火算法

算法在遗传算法的基础上增加了模拟退火操作，因此仅分析该操作的时间复杂度即可。随机产生扰动所需要的时间较少，对新解计算适应度需要的时间复杂度是$ O\left(n\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\right) $，故降温一次需要的时间复杂度是$ O\left(Nn\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\right) $。而模拟退火操作需要重复执行$ \mathrm{l}\mathrm{o}{\mathrm{g}}_{\alpha }^{\frac{{T}_{s}}{{T}_{e}}} $次，因此算法的实际时间复杂度为$ O\left(\mathrm{M}\mathrm{A}\mathrm{X}\mathrm{G}\mathrm{E}\mathrm{N}\times Nn\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\times \mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\frac{{T}_{s}}{{T}_{e}}\right) $。遗传模拟退火算法的空间间复杂度为$ O\left(Nn\right) $。

6 实验结果与分析

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

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

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

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

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

7 结束语

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