0 引　言

无线传感器网络(Wireless Sensor Networks, WSN)技术提供了一种全新的获取信息、处理信息的途径，可被广泛应用于舰船航行、军事监测、工业故障诊断、智能交通、医疗健康以及智能家居等领域^[1-2]。在舰船无线传感器网络中包含了大量的传感器节点，用于舰船航行信息的采集与传输^[3]。由于在舰船航行过程中网络持续运行，节点会由于自身能量消耗殆尽或受到外界因素的影响而失效，导致覆盖空洞的出现，进而影响整个舰船网络的通信质量，降低舰船信息传输的有效性^[4-6]。因此，当舰船网络中出现覆盖空洞时，如何选择合适的移动传感器节点及时修复覆盖空洞是无线传感器网络近几年研究的热点问题。

目前国内外对覆盖空洞修复问题的研究已取得了很多成果，Khalifa等^[7]提出基于级联的邻居节点覆盖空洞修复策略，利用节点的能量和邻居节点数选择修复节点来修复覆盖空洞区域。杨明霞等^[8]利用相交节点的弦来固定和搜寻覆盖空洞，并将空洞修复问题转换为无向图求解最大团问题，从而实现以最少移动节点和最低重叠覆盖完成对空洞的修复。郝占军等^[9]中提出一种三维覆盖空洞动态检测与修复算法，通过计算覆盖空洞周围的冗余移动节点移动到覆盖空洞时的方向和距离，从而调整移动节点以修复覆盖空洞。以上文献主要针对多个故障节点共同形成的具有一定面积的单个覆盖空洞区域，在修复覆盖空洞时均未考虑对故障节点原先所收集到的总数据流进行处理和覆盖空洞修复时效性的问题。

Feng等^[10]是针对网络中出现多个覆盖空洞的问题，提出了一种集中式节能修复算法，采用迭代机制提前调度移动传感器对覆盖空洞进行修复。同样也没有考虑对故障节点原先所收集到的总数据流进行处理和覆盖空洞修复时效性的问题。

本文针对舰船网络中出现多个覆盖空洞的问题，提出了一种基于时效性覆盖空洞修复(Timeliness Coverage Hole Repair, TCHR)算法。所提算法避免了故障节点原先所收集到的舰船航行数据丢失的情况，同时考虑了修复覆盖空洞时效性的问题。首先基于备选移动节点的可持续最大移动时间，筛选出可选移动节点ID序列。然后，计算出所有可选移动节点对应修复的总时间，以此构建出最小化修复覆盖空洞总时间的目标函数。最后，构建时间代价矩阵，并基于匈牙利算法求解出最优分配方案。通过所提算法的最优分配方案可实现修复覆盖空洞总时间最小化，完成舰船网络中多覆盖空洞及时修复的任务。

1 系统模型 1.1 网络模型

如图1所示，网络中由一个汇聚节点、一个分类节点、随机分布的 $M$ 个正常节点和 $m(0 < m < M)$ 个在网络初始阶段处于休眠状态的移动节点、 $n(0 < n < m)$ 个故障节点组成。假设已知所有节点ID和初始位置信息，能量阈值为 ${E_{{\text{th}}}}$ ；节点发送总数据流包含ID、能量和收集到的舰船航行数据信息；汇聚节点位于网络区域的中心，用于接收并处理节点所收集到的数据信息^[11]；移动节点部署在汇聚节点周围，用于修复因故障节点而引起的覆盖空洞；分类节点用于接收节点的能量和位置信息^[12]，并对其能量状态进行判定。若某节点能量降低到能量阈值，则根据收集的节点位置信息计算各移动节点到该节点所需时间，完成修复任务指派。

1.2 可持续移动时间模型

考虑到移动节点移到故障节点处所剩余的能量仍能进行正常通信的条件，若 ${E_0}$ 为所有移动节点的初始能量， $e$ 为移动过程中单位时间内所消耗的能量，则备选移动节点的可持续最大移动时间记为 ${T_{\max }}$ ，表示如下：

${T_{\max }} = \frac{{{E_0} - {E_{{\text{th}}}}}}{e} 。$

(1)

2 基于时效性覆盖空洞修复算法的设计及实现 2.1 问题描述

移动节点 $i$ 修复由故障节点 $j$ 形成的覆盖空洞所需要的总时间 $T_j^i$ 分为两部分，一是故障节点 $j$ 利用剩余能量发送总数据流的传输时间 $T_j^{{\text{trans}}}$ ，二是移动节点 $i$ 接收来自分类节点的故障指派移到指定的故障节点 $j$ 处所需的移动时间 $T_{ij}^{{\text{move}}}$ 。假设与总时间 $T_j^i$ 相比，移动节点 $i$ 接收来自分类节点的故障指派所用的时间可忽略不计。因此，覆盖空洞所需的总时间 $T_j^i$ 可计算如下：

1）假设故障节点 $j$ 发送的总数据流大小为 ${l_j}$ ，则其传输时间 $T_j^{{\text{trans}}}$ ^[13]为：

$T_j^{{\text{trans}}} = \frac{{{l_j}}}{{{r_j}}} 。$

(2)

式中， ${r_j}$ 为故障节点发送总数据流时的传输速率，bit/s。因此，上式可表示为：

$T_j^{{\text{trans}}} = \frac{{{l_j}}}{{{r_j}}} = \frac{{{l_j}}}{{B{\text{lo}}{{\text{g}}_2}\left(1 + \dfrac{{{p_j}{h_{kj}}}}{{{\sigma ^2}}}\right)}}。$

(3)

式中： $B$ 表示传输带宽，Hz； ${p_j}$ 表示故障节点 $j$ 的传输功率，dBm； ${\sigma ^2}$ 表示噪声功率，dBm； ${h_{kj}}$ 表示分类节点 $k$ 与故障节点 $j$ 之间的信道增益。假设路径损耗符合自由空间模型，则 ${h_{kj}} = d_{kj}^{{{ - }}\xi }$ 。其中， ${d_{kj}}$ 表示分类节点 $k$ 与故障节点 $j$ 之间的直线距离，m； $\xi$ 表示路径衰落因子，且 $\xi$ =3。

2）从备选移动节点集中选择一个合适的移动节点 $i$ 去替换相应的故障节点 $j$ 完成覆盖空洞的修复，其移动距离为：

${d_{ij}} = \sqrt {{{({x_i} - {x_j})}^2} + {{({y_i} - {y_j})}^2}}。$

(4)

式中： ${x_i}$ 和 ${y_i}$ 代表第 $i$ 个移动节点的位置坐标； ${x_j}$ 和 ${y_j}$ 代表第 $j$ 个故障节点的位置坐标。

假设移动节点移到故障节点处所做的是匀速直线运动。那么，移动节点 $i$ 接收来自分类节点的故障指派移到指定的故障节点 $j$ 处所需的移动时间 $T_{ij}^{{\text{move}}}$ 为：

$T_{ij}^{{\text{move}}} = \frac{{{d_{ij}}}}{{{v_{ij}}}}。$

(5)

式中： ${d_{ij}}$ 为移动节点 $i$ 到故障节点 $j$ 的移动距离； ${v_{ij}}$ 为移动节点 $i$ 移向故障节点 $j$ 所做匀速直线运动的速度值，m/s。

令 ${\lambda _{ij}}$ 为移动节点的移动因子，可表示如下：

${\lambda _{ij}} = \left\{ {\begin{array}{*{20}{c}} 1&{{T_{\max }} \geqslant T_{ij}^{{\text{move}}}}，\\ 0&{{T_{\max }} < T_{ij}^{{\text{move}}}} 。\end{array}} \right.$

(6)

式中： ${\lambda _{ij}}$ =0表示移动节点无法移到故障节点处； ${\lambda _{ij}}$ =1表示移动节点可移到故障节点处完成覆盖空洞的修复任务。

由此可得，移动节点的移动时间 $T_{ij}^{{\text{move}}}$ 只在备选移动节点的可持续最大移动时间 ${T_{\max }}$ 内，才能移到故障节点处。以此筛选出所有满足 ${\lambda _{ij}}$ =1的移动节点ID，使其按 $N$ 维序列的长度排列得到一个可选移动节点ID序列 $\mathbb{Z}$ =[ $1,2, \cdots ,i, \cdots ,N$ ]。

由上述分析可知，可选移动节点 $i$ 修复由故障节点 $j$ 形成的覆盖空洞所需要的总时间 $T_j^i$ 为：

$\begin{split} T_j^i = & T_j^{{\text{trans}}} + T_{ij}^{{\text{move}}}= \\ & \frac{{{l_j}}}{{B{\text{lo}}{{\text{g}}_2}\left(1 + \dfrac{{{p_j}{h_{kj}}}}{{{\sigma ^2}}}\right)}} + \frac{{{d_{ij}}}}{{{v_{ij}}}} 。\end{split}$

(7)

由可选移动节点ID序列 $\mathbb{Z}$ 和式(7)可得，可选移动节点修复故障节点所需的总时间集合 $\mathbb{F}$ =[ $T_j^1,T_j^2, \cdots , T_j^i, \cdots ,T_j^N$ ]。

此时，舰船网络最小化修复覆盖空洞总时间的问题可描述如下：

$\begin{split} & \min \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{x_{ij}}T_j^i} }，\\ & {\text{s}}{\text{.t}}\left\{ {\begin{array}{*{20}{c}} {{x_{ij}} \in \left\{ {0,1} \right\},1 \leqslant i \leqslant m,1 \leqslant j \leqslant n} ，\\ {\displaystyle\sum\limits_{i = 1}^m {{x_{ij}} = 1,1 \leqslant j \leqslant n} }，\\ {\displaystyle\sum\limits_{j = 1}^n {{x_{ij}} = 1,1 \leqslant i \leqslant m} } 。\end{array}} \right. \end{split}$

(8)

式中，第1个约束条件中 ${x_{ij}}$ 是指派因子，当 ${x_{ij}}$ =1时，表示移动节点 $i$ 被指派到故障节点 $j$ 完成覆盖空洞修复任务，否则 ${x_{ij}}$ =0；第2个约束条件表示一个移动节点只能修复一个覆盖空洞；第3个约束条件表示一个覆盖空洞只能由一个移动节点来进行修复。

2.2 最小化修复覆盖空洞总时间的问题求解

TCHR算法流程如图2所示。

基于式(7)和式(8)构建出时间代价矩阵Ann如下：

${{\boldsymbol{A}}_{{\boldsymbol{nn}}}} = \left( {\begin{array}{*{20}{c}} {T_1^1}& \cdots &{T_1^n} \\ \vdots & \ddots & \vdots \\ {T_n^1}& \cdots &{T_n^n} \end{array}} \right) 。$

(9)

式中， $T_n^n$ 代表在舰船网络中第 $n$ 个移动节点修复第 $n$ 个覆盖空洞所需的总时间。

最后，基于匈牙利算法^[14-15]对Ann求得最优解，该最优解使得 $n$ 个移动节点完成 $n$ 个覆盖空洞修复任务时所花的时间总和最小，从而高效修复相应的覆盖空洞。

3 仿真结果与分析

假设随机部署 $M(50 \leqslant M \leqslant 1000)$ 个正常节点在一个 $r \times r$ ( ${\text{50 m}} \leqslant r \leqslant {\text{200 m}}$ )的监测区域内，汇聚节点部署在监测区域的中心位置， $m(0 < m \leqslant 100)$ 个移动节点和一个分类节点随机部署在汇聚节点附近， $n(0 < n \leqslant 100)$ 个故障节点随机分布在监测区域内，所有移动节点的移动速度均为 ${v_{ij}}(0{\text{ m/s}} < {v_{ij}} \leqslant 1{\text{ m/s}})$ 。仿真参数设置如表1所示。

为了验证所提出的TCHR算法的性能，将TCHR算法与穷举算法、贪婪(Greedy)算法进行了比较，如图3所示。将监测区域边长设置为 $r$ =60 m，正常节点数量 $M$ =200，移动节点数量 $m$ =10，移动节点的移动速度 ${v_{ij}}$ =0.4 m/s，覆盖空洞数量 $n$ 分别为3，4，5，6，7。从图3可看出，随着覆盖空洞数量的增加，覆盖空洞的总修复时间也会逐渐增加。

对比不同算法可看出，所提算法与穷举算法所获得的总修复最小时间基本一致，但由于穷举算法遍历了所有移动节点可能修复的策略，其算法复杂度高。与Greedy算法相比，所提算法可搜索得到更优的总修复最小时间。这是因为Greedy算法总是派遣最接近覆盖空洞位置的可移动节点修复覆盖空洞，会导致陷入局部最优，无法获得全局最优解。而所提算法能对所有待修复的覆盖空洞进行全局寻优，实现总体修复时间最小化。由上述分析可知，所提算法在兼顾计算效率的前提下，可有效实现最小化总修复时间。

在节点移动速度不同的情况下，将所提的TCHR算法与Greedy算法进行对比，研究这2种算法所获得的修复覆盖空洞总体最小时间随覆盖空洞数量的变化曲线如图4所示。将监测区域边长设置为 $r$ =60 m；正常节点数量 $M$ =200；移动节点数量 $m$ =55；覆盖空洞数量 $n$ 分别为10，20，30，40，50；移动节点的移动速度 ${v_{ij}}$ 分别为0.3 m/s和0.8 m/s。从图4可看出，在覆盖空洞数量相同的情况下，节点移动速度越大，所需的总修复时间就越小。当节点移动速度相同时，与Greedy算法相比，覆盖空洞数量越多，所提算法实现最小化总修复时间的效果越显著。由上述分析可知，所提算法较Greedy算法更适用于舰船网络中出现覆盖空洞数量较多的情况。

图5为所提出的TCHR算法在不同监控区域中覆盖空洞数与修复覆盖空洞总体最小时间的关系图。将监测区域边长分别设置为 $r$ =30，40，50，60，70 m；正常节点数量 $M$ =200；移动节点数量 $m$ =10；覆盖空洞的数量分别为 $n$ =3，4，5；移动节点的移动速度 ${v_{ij}}$ 为0.4 m/s。从图5可看出，在覆盖空洞数量一定时，随着监控区域的不断扩大，修复单个覆盖空洞所用的时间有所增加，从而修复覆盖空洞的总体最小时间也会逐渐增加。当监控区域的边长为30 m和40 m时，修复覆盖空洞的总体最小时间随着覆盖空洞数量的增加而小幅度增加，如 $n$ =3与 $n$ =4以及 $n$ =4与 $n$ =5分别所对应的最小总修复时间的时间差均在60 s内。当监控区域的边长为50 m，60 m，70 m时，随着覆盖空洞数量的增加，修复覆盖空洞的总体最小时间逐渐增加并且增加幅度相比之前更大。特别是在监控区域为 $70{\text{ m}} \times {\text{70 m}}$ 的情况下， $n$ =4所对应的最小总修复时间与 $n$ =5相比，时间差达132.4 s，说明在大规模舰船网络中出现覆盖空洞数量越多，对移动节点移动修复的影响就会越大，相应的总修复时间也会随之增加。

图6为利用所提的TCHR算法对不同移动节点占比情况下，修复覆盖空洞总体最小时间随正常节点总数的变化情况。将监测区域边长设置为 $r$ =60 m，正常节点数量 $M$ 分别为100，150，200，250，300，移动节点占正常节点的比例 ${\text{P}}$ 分别为10%和20%，覆盖空洞数量 $n$ =8；移动节点的移动速度 ${v_{ij}}$ 为0.4 m/s。从图6可看出，在相同移动节点所占比例的情况下，修复覆盖空洞总体最小时间随正常节点总数的增加而逐渐增加，说明网络中部署节点越密集，修复覆盖空洞所用的时间就会越长。当部署的正常节点数量相同时，移动节点占比为10%较占比为20%所获得的修复覆盖空洞总体最小时间要长。由上述分析可知，所提算法在舰船网络部署节点稀疏并且移动节点所占比例较大的情况下，能有效实现最小化总修复时间。

4 结　语

本文主要针对舰船网络中同时出现多个覆盖空洞的问题，提出了TCHR算法。该算法在避免故障节点原先所收集到的舰船航行数据信息丢失的情况下，以总修复时间最小化为准则，利用匈牙利算法获得移动节点修复覆盖空洞的最优分配方案，从而选派合适的移动节点至相应的覆盖空洞处，完成舰船网络中多覆盖空洞及时修复的任务。仿真结果表明，所提算法在兼顾计算效率的前提下，可有效修复网络中所有的覆盖空洞并实现最小化总修复时间。未来，将进一步考虑舰船在航行过程中，非理想场景条件下对修复覆盖空洞的影响。