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

0 概述

无线传感器网络（Wireless Sensor Network，WSN）广泛应用于环境监控、反恐救灾、军事、医疗健康、动物跟踪等领域^[1]。传统的静态WSN完全由固定传感器组成，所有的传感器在部署完之后位置都保持不变，只能通过将网络中部署的冗余传感器从睡眠状态唤醒的方法来完成覆盖洞修补，该覆盖洞修补方式需要监控区域能被传感器网络全覆盖，而这在敌对或恶劣的自然环境中（如战场、森林火场等）是不切实际的，在这些场景中很难对WSN进行人工部署。通过飞机撒播、火箭弹射等随机部署方式，在遇到障碍物时即使提高节点的部署密度，也难以一次就将所有传感器部署到适当的位置，极易造成节点分布过密或过疏从而形成覆盖重叠区和覆盖盲区，难以实现区域全覆盖。

近年来，研究人员提出由固定传感器和移动传感器组成的混合无线传感器网络（Hybrid Wireless Sensor Network，HWSN）^[2-3]，与完全由固定传感器组成的静态WSN不同，HWSN可以对移动传感器进行重新部署^[4-5]，修复传感器网络由于节点分布不均或节点因能量耗尽而失效等原因形成的覆盖洞^[6-7]，从而优化网络覆盖性能^[8-10]。

针对HWSN的覆盖控制问题，学术界进行了大量研究。文献^[11-13]提出基于虚拟力的WSN覆盖算法，但该算法容易陷入局部最优，导致网络覆盖优化失败。由于覆盖问题是NP-难问题^[14]，因此研究人员将各种智能算法应用于HWSN覆盖控制任务，如鱼群算法^[15-17]、遗传算法^[18-20]、差分演化算法^[21-22]、蚁群算法^[23-25]、粒子群算法^[26-27]等，且取得了较好的效果，但是，这些方法存在的最大问题是算法时间复杂度高，计算量大，收敛速度慢，有时甚至收敛于局部最优解，导致覆盖优化失败。

在HWSN中，能耗主要来源于2个方面，即相邻传感器之间的通信以及移动传感器节点的机械运动。文献^[28]指出，将移动传感器节点移动1 m所消耗的能量是传感器发送一个消息所消耗能量的300倍，因此，HWSN的能耗主要体现在重新部署移动传感器位置时移动传感器所耗费的能量。本文用移动节点的平均移动距离（Average Moving Distance，AMD）作为移动传感器机械运动能耗的度量标准，因此，优化移动节点的AMD具有十分重要的意义。文献^[29]提出一种基于蜂窝结构的HWSN覆盖优化算法HWSNBCS，根据移动节点和其$ \sqrt[]{3} $倍感知半径范围内固定节点间的位置关系，基于蜂窝结构和漏洞修补策略对移动节点进行重新部署，以改善网络的覆盖性能。该算法包括2个阶段：第一阶段基于蜂窝结构计算每个移动传感器的候选目标位置，其中，算法给出了4种情况下移动节点的移动方案；第二阶段对所有移动节点的候选目标位置进行进一步优化，确定移动节点的最终目标位置。算法通过移动传感器移动距离优化算法来减少移动传感器的AMD，从而降低移动节点的能耗，确定移动节点的最终目标位置。HWSNBCS算法能显著改善网络的覆盖性能，且执行效率较高，但算法第二阶段的移动传感器移动距离优化算法只是通过简单地将移动传感器的候选目标位置两两互换，以寻找移动节点移动距离的可能优化结果，这种启发式方法得到的解不一定是最优解，本文将在第2章对其进行例证和分析。

本文将HWSN移动节点移动距离之和最小化问题转化为二分图最优匹配问题，用带权二分图匹配算法KM（Kuhn-Munkres）对文献^[29]中的HWSNBCS算法进行改进，具体地，利用KM算法对HWSNBCS算法第一阶段移动节点的移动距离进行优化，在保持算法第一阶段网络覆盖率不变的前提下，减少移动节点的平均移动距离以及单个移动节点的最大移动距离，从而降低系统能耗。

1 HWSNBCS算法

设由n个传感器节点S={s₁，s₂，…，s_n}组成的HWSN随机分布在二维平面区域A中。为了讨论方便，对HWSN作如下假设：

1）每个传感器都知道自己的位置信息。

2）所有传感器的通信半径R_c相同，感知半径R也相同，且R_c=2R。

3）在区域A中存在一个Sink节点，该节点负责完成算法的移动距离优化。

在分析HWSNBCS算法之前先介绍算法中的2个概念：

定义1    设R为传感器s_a的感知半径，以传感器节点s_a为圆心、以$ \sqrt{3}R $为半径的圆周称为节点s_a的邻接蜂窝节点轨迹圆（Neighboring Cellular Node Locus Circle，NCNLC）^[29]。

定义2    若移动节点m_a在固定节点s_a的NCNLC上，则称s_a的NCNLC为m_a的候选蜂窝节点轨迹圆（Candidate Cellular Node Locus Circle，CCNLC）^[29]。

1.1 基于蜂窝结构的节点移动策略

HWSNBCS算法第一阶段给出4种情况下移动传感器的移动方案：

1）若移动传感器m_a的NCNLC内没有固定传感器，则m_a不需要移动^[29]。如图 1所示，虚线圆周是移动传感器m_a的NCNLC，由于m_a的NCNLC内没有固定传感器，因此m_a不需要移动。

2）若移动传感器m_a位于某个固定传感器s_a的NCNLC内，记s_a的NCNLC为⊙s_a，则m_a沿直线s_am_a移动到⊙s_a上距m_a较近的点^[29]。如图 2所示，m_a沿直线s_am_a移动到⊙s_a上的A点。

3）当移动传感器m_a位于某个固定传感器的NCNLC内，且m_a有一个CCNLC时，m_a移动到CCNLC与固定节点的NCNLC的交点中距离m_a较近的点^[29]。如图 3所示，m_a有一个CCNLC，为s_a的NCNLC，记为⊙s_a，同时m_a位于s_b的NCNLC内，记s_b的NCNLC为⊙s_b，则m_a移动到⊙s_a与⊙s_b的2个交点中距离m_a较近的B点^[29]。

4）若移动传感器m_a位于某个固定传感器的NCNLC内，且m_a有2个CCNLC时，m_a移动到3个固定传感器的NCNLC的交点中距离m_a较近的外层交点^[29]。如图 4所示，m_a有2个CCNLC，分别是固定节点s_a、s_b的NCNLC，且m_a位于固定节点s_c的NCNLC内，则m_a移动到这3个NCNLC的交点中距离m_a最近的最外层交点A^[29]。

1.2 节点移动距离优化

HWSNBCS算法第二阶段通过对移动节点的移动距离进行优化，从而确定移动节点的最终目标位置^[29]。通过将移动传感器的候选目标位置两两交换，寻找移动节点移动距离的可能优化结果，其原理如图 5所示。假设P_a、P_b分别为移动节点m_a、m_b的候选目标位置，如果|m_aP_a|+|m_bP_b| > |m_aP_b|+|m_bP_a|，则交换m_a、m_b的候选目标位置P_a、P_b。

1.3 算法描述

基于蜂窝结构的HWSN覆盖优化算法HWSNBCS描述如下：

算法1   HWSNBCS算法

输入   目标区域A，初始节点集合S={s₁，s₂，…，s_n}，其中s₁，s₂，…，s_m为移动节点，其余为固定节点

输出    移动节点重新部署的目标位置P={p₁，p₂，…，p_m}，其中p₁，p₂，…，p_m分别为移动节点s₁，s₂，…，s_m的新目标位置

步骤1    For i：= 1 to m do

对移动传感器节点m_i，根据图 1~图 4所示的4种情况，计算其候选目标位置P_i。

步骤2    随机选取2个移动传感器m_a、m_b，设其初始位置分别为P_a0、P_b0，当前候选目标位置分别为P_a1、P_b1。如果|P_a0P_a1|+|P_b0P_b1| > |P_a0P_b1|+|P_b0P_a1|，则P_a1↔P_b1，其中|·|表示节点之间的欧式距离。

步骤3    重复步骤2，直至整个HWSN的AMD不能减少为止。

步骤4    输出集合P。

显然，步骤2~步骤3不会改变整个网络的覆盖率，但可减少移动节点的AMD，从而进一步优化移动节点的布局。

2 基于蜂窝结构的改进HWSN覆盖控制算法

HWSNBCS算法的步骤2简单地将移动节点的候选目标位置两两互换，以寻找移动节点移动距离的可能优化结果，这是一种启发式方法，得到的解不一定是最优解。图 6所示为一个简单的带权二分图，P_a、P_b、P_c分别为移动传感器m_a、m_b、m_c的候选部署位置，m_a、m_b、m_c分别到P_a、P_b、P_c的距离如图中所示。不失一般性，移动传感器按照m_a、m_b、m_c的顺序依次选择候选部署位置，将会选择P_b、P_a、P_c分别作为m_a、m_b、m_c的目标位置，3个移动节点移动距离之和为|m_aP_b|+|m_bP_a|+|m_cP_c|=3+5+8=16，比原来的|m_aP_a|+|m_bP_b|+|m_cP_c|=5+4+8=17仅减少1，但实际上最短距离之和为|m_aP_c|+|m_bP_b|+|m_cP_a|=4+4+4=12。因此，HWSNBCS算法中移动节点移动距离优化方案得到的解并非全局最优解，移动节点的移动距离还可以进一步优化。

HWSNBCS算法中距离优化的实质是寻找移动传感器节点初始位置与其候选目标位置之间的最优匹配，使得移动节点移动距离之和最小化。为此，本文采用带权二分图最优匹配算法KM来解决这一匹配问题，以实现对HWSNBCS算法的改进。

2.1 算法描述

KM是用于求解带权二分图最优匹配问题的经典算法。本文通过构造带权二分图，将HWSN移动传感器移动距离优化问题转化为二分图最优匹配问题。设HWSN中移动节点s₁，s₂，…，s_m的初始位置为Q={q₁，q₂，…，q_m}，q_i为移动节点s_i的初始位置，通过HWSNBCS算法步骤1得到的移动节点候选目标位置为P={p₁，p₂，…，p_m}，p_i为移动节点s_i的候选目标位置。构造带权二分图G=（V，E），顶点集V=Q∪P，边集E={（u，v，w_uv）|u∈Q，v∈P，w_uv=-|uv|}，w_uv表示边（u，v）的权值，为顶点u、v之间欧式距离的相反数。用KM算法求出图G的最优匹配，即可得到移动节点移动距离之和最小化的目标位置。本文所提基于蜂窝结构的改进HWSNBCS算法（IHWSNBCS）描述如下：

算法2    IHWSNBCS算法

输入   移动节点s₁，s₂，…，s_m初始位置Q，通过HWSNBCS算法步骤1得到的候选目标位置P

输出    集合Q与集合P移动距离之和最小的匹配结果

步骤1    定义初始可行顶点标记L：

$ \left\{\begin{array}{l}L（{q}_{i}）=\underset{{p}_{j}}{\mathrm{m}\mathrm{a}\mathrm{x}}{w}_{{q}_{i}{p}_{j}}, {q}_{i}\in Q, i=\mathrm{1, 2}, \cdots , m\\ L（{p}_{j}）=0, {p}_{j}\in P, j=\mathrm{1, 2}, \cdots , m\end{array}\right. $

(1)

步骤2    设$ {E}_{l}=\left\{（{q}_{i}, {p}_{j}）\left|L\right({q}_{i})+L({p}_{j})={w}_{{q}_{i}{p}_{j}}\right\} $，$ {G}_{l}=(V, {E}_{l}\} $，设X为$ {G}_{l} $的一个匹配。若Q中每个点都是X的饱和点，则X就是所求的移动传感器移动距离之和最小的匹配结果，计算结束；否则，取X的非饱和点$ {q}_{i}\in Q $，令A={q_i}，B=Ø，A、B为2个集合。

步骤3    令$ {N}_{{G}_{L}}\left(A\right)=\left\{{p}_{j}\right|{q}_{i}{p}_{j}\in {E}_{l}, {q}_{i}\in Q, {p}_{j}\in P\} $，若$ {N}_{{G}_{L}}\left(A\right)=B $，则$ {G}_{l} $没有最优匹配，转步骤4；否则，转步骤5。$ {N}_{{G}_{L}}\left(A\right)\subseteq P $是与A中节点邻接的节点集合。

步骤4    调整可行顶点标记。令$ d=\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{ }\{L（{q}_{i}）+L（{p}_{j}）-{w}_{{q}_{i}{p}_{j}}|{q}_{i}\in A, {p}_{j}\in P-B\} $，按式（2）修改可行顶点标记：

$ \left\{\begin{array}{l}{L}^{\text{'}}\left(v\right)=L\left(v\right)-d, v\in A\\ {L}^{\text{'}}\left(v\right)=L\left(v\right)+d, v\in B\\ {L}^{\text{'}}\left(v\right)=L\left(v\right), \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\end{array}\right. $

(2)

根据$ {L}^{\text{'}} $计算$ {E}_{{L}^{\text{'}}} $及$ {G}_{{L}^{\text{'}}} $，令L=$ {L}^{\text{'}}, {G}_{L}={G}_{{L}^{\text{'}}} $，转步骤2。

步骤5    取p$ \in {N}_{{G}_{L}}\left(A\right)-B $，若p是X的饱和点，转步骤6；否则，转步骤7。

步骤6    设qp$ \in X $，令A=A∪{q}，B=B∪{p}，转步骤3。

步骤7    $ {G}_{L} $中的（u，p）路是X增广路，记为path，并令X=X$ \oplus $path，转步骤2，最终求得X。

从IHWSNBCS算法可以看出，其输入和HWSNBCS算法第二阶段的输入完全一样，但HWSNBCS算法第二阶段采用启发式方法，而IHWSNBCS算法采用全局优化方法，即KM算法，KM算法的正确性早已得到证明，因此，本文IHWSNBCS算法能得到一个较好的解。

IHWSNBCS算法并不改变HWSNBCS算法的网络覆盖率，仅改变HWSNBCS算法中移动节点的平均移动距离，这是因为IHWSNBCS算法只对HWSNBCS算法移动节点的初始位置和目标位置进行重新匹配，在整个HWSN中，固定节点的位置没有发生变化，因此，其监测区域也没有变化，相比HWSNBCS算法而言，IHWSNBCS中移动节点整体监测的区域实际上也没有发生变化，变化的只是单个传感器的监测区域。因此，IHWSNBCS算法传感器节点的监测区域与HWSNBCS算法相同，即IHWSNBCS算法并未改变HWSNBCS算法的网络覆盖率。

2.2 复杂度分析

首先分析IHWSNBCS算法的时间复杂度。IHWSNBCS的输入是运行HWSNBCS算法步骤1的输出，其时间复杂度为O（m（n-m））^[29]。IHWSNBCS算法中的KM算法通过不断寻找从未匹配点$ {q}_{i}\in Q $出发的可增广路，以扩充当前的匹配情况，执行次数为m，利用深度优先搜索可增广路，其时间复杂度为O（m²），即KM算法的时间复杂度为O（m³）^[30]。因此，IHWSNBCS算法的时间复杂度为O（mn+m³），高于HWSNBCS算法的时间复杂度O（mn）^[29]，原因是IHWSNBCS算法要调用KM算法，提高了运算复杂度。

然后分析IHWSNBCS算法的空间复杂度。IHWSNBCS算法和HWSNBCS算法的内存消耗主要来源于移动节点的初始位置和候选目标位置，因此，空间复杂度均为O（m），改进算法并未增加空间开销。

最后分析IHWSNBCS算法的通信复杂度。为了得到IHWSNBCS算法的输入而运行HWSNBCS算法的步骤1，其通信开销为O（m）^[29]。IHWSNBCS算法中KM算法的输入是各移动传感器节点的初始位置和候选目标位置，对于给定的目标监测区域A，设移动节点发送数据包到Sink节点的平均跳数为h，则移动节点将其初始位置信息和候选目标位置信息发送到Sink节点的通信开销为O（mh），Sink节点将KM算法计算出的各移动节点的最终目标位置信息发送至各移动节点的通信开销为O（mh）。因此，IHWSNBCS算法的总通信开销为O（mh），高于HWSNBCS算法的通信开销O（m）^[29]，其原因也是因为调用KM算法时需要向Sink节点发送消息。

3 实验结果与分析

为了评估本文算法的性能，在Win 10下用Visual studio 2019进行仿真，仿真场景为一个125 m×125 m的矩形区域，其中随机分布着若干传感器，传感器的感知半径和通信半径分别为10 m和20 m。

为了更好地评价算法性能，本文引入式（3）所示的ΔCov-Dist指标：

$ Δ{\rm{Cov - Dist}}= Δ覆盖率/平均移动距离 $

(3)

其中：平均移动距离是HWSN中所有移动节点移动距离的平均值，平均移动距离越小，系统因重新部署移动传感器节点的总能耗越低；$ \mathrm{\Delta } $Cov-Dist是单位移动距离下网络覆盖率的变化，为网络覆盖率的变化与移动节点平均移动距离的比值，$ \mathrm{\Delta } $Cov-Dist越大，移动节点移动相同距离时网络覆盖率提升越大，HWSN能效越高。

图 7（a）所示为一个由40个固定传感器和20个移动传感器所组成的HWSN，对图 7（a）所示的HWSN分别运行HWSNBCS和IHWSNBCS算法，得到图 7（b）、图 7（c）所示的实验结果，图中小空心圆表示传感器节点，深色填充大圆表示移动传感器的感知区域，浅灰色填充大圆表示固定传感器的感知区域，线段表示移动传感器初始位置和目标位置之间的直线距离，线段越长，表示移动传感器移动距离越远。从图 7可以看出，图 7（a）中传感器分布不均，区域中有明显的覆盖洞，其网络覆盖率为65.29%。图 7（b）、图 7（c）通过对移动传感器重新部署，网络的覆盖性能明显改善，其覆盖率达到83.39%。虽然图 7（b）和图 7（c）的覆盖率一样，但图 7（b）中移动传感器的AMD为35.45 m，而图 7（c）中移动传感器的AMD为21.67 m，前者AMD减少了38.87%，显然，本文IHWSNBCS算法中移动节点的AMD更短。图 7（b）的ΔCov-Dist为0.51，图 7（c）的$ \mathrm{\Delta } $Cov-Dist为0.84，后者为前者的1.64倍，说明网络能效更高。此外，从图 7中还可以看出，图 7（c）中长度较长的线段数量比图 7（b）中少，且最长线段的长度比图 7（b）中短，说明本文算法单个节点的最大移动距离也大幅缩短，单个节点的最大移动距离过大，会导致该节点因能量消耗过快而成为失效节点，从而形成覆盖盲区，影响网络的覆盖性能。

图 8所示为一个由56个固定传感器和24个移动传感器所组成的HWSN，其初始覆盖率为75.25%。对图 8所示的HWSN分别运行HWSNBCS和IHWSNBCS算法，得到表 1所示的实验结果。从表 1可以看出，通过对部分移动节点进行重新部署，2种算法都大幅提高了网络覆盖率，改善了网络的覆盖性能。虽然本文IHWSNBCS算法并不改变HWSNBCS算法的覆盖率，但IHWSNBCS算法移动节点的平均移动距离更小，与HWSNBCS算法相比减少了43.28%，说明达到相同的覆盖性能，本文算法移动节点的能耗更小，且单个移动节点的最大移动距离更短，比HWSNBCS算法减少66.58%，这将降低单个节点因能量过早耗完而失效的概率，从而有助于延长整个传感器网络的生命周期。此外，IHWSNBCS算法的ΔCov-Dist指标是HWSNBCS算法的1.76倍，说明前者能效更高。

在HWSN传感器总数保持不变的情况下，改变移动传感器的比例，分别运行HWSNBCS和IHWSNBCS算法，实验中移动节点均为随机选取。表 2所示为2种算法在不同移动节点比例下的覆盖率和单个节点最大移动距离。从表 2可以看出：随着移动传感器节点比例的提升，通过对更多的移动节点进行重新部署，网络的覆盖率逐渐提升，但本文算法单个移动节点的最大移动距离比HWSNBCS算法减少了22.65%~66.58%，这将大幅减少单个移动节点重新部署的最大能耗，降低节点因能量过早耗完而失效的概率。

图 9所示为2种算法移动节点平均移动距离在不同移动节点比例下的变化情况。从图 9可以看出：随着移动节点比例的增加，有更多的移动节点被重新部署，本文IHWSNBCS算法移动传感器的AMD逐渐减少，其AMD比HWSNBCS算法中的AMD小很多，这是因为对于移动传感器移动距离最小化问题，本文使用的KM算法能够得到全局最优解，而HWSNBCS算法得到的是局部最优解，因此，HWSNBCS算法的AMD比本文算法大，且随着移动传感器比例的增大，HWSNBCS算法移动节点的AMD变化趋势也没有IHWSNBCS算法明显。

图 10所示为2种算法$ \mathrm{的} $ΔCov-Dist指标在不同移动节点比例下的变化情况。从图 10可以看出，本文算法的ΔCov-Dist指标明显大于HWSNBCS算法，这是由于在覆盖率变化相同的情况下，本文算法的平均移动距离更小，因而通过式（3）计算出的ΔCov-Dist更大，能效更高。

对一个由56个固定节点和24个移动节点组成的HWSN分别运行标准遗传算法、粒子群算法、HWSNBCS算法和IHWSNBCS算法，实验结果如表 3所示。其中，粒子群算法和遗传算法均以最大化网络覆盖率为优化目标，在达到与HWSNBCS以及IHWSNBCS相同的覆盖率时算法停止。粒子群算法和遗传算法各运行50次，取其平均值，HWSNBCS和IHWSNBCS算法各运行1次。实验中移动节点的初始能量为1 500 J，移动节点每移动1 m所消耗的能量为30 J。当重新部署某个移动节点时，如果其需要耗费的能量大于初始能量，则认为该节点失效。从表 3可以看出，本文算法的失效节点数明显少于其他3种算法，因此，其网络生命周期会更长。

4 结束语

本文提出一种基于蜂窝结构的改进HWSN覆盖优化算法IHWSNBCS。将HWSN中移动传感器的移动距离优化问题转化为二分图匹配问题，然后利用带权二分图匹配算法KM计算匹配问题的最优解，从而实现对HWSNBCS算法的优化。实验结果表明，IHWSNBCS算法可在保持原有HWSNBCS算法网络覆盖率不变的前提下，大幅减少移动节点的平均移动距离以及单个移动节点的最大移动距离，同时提高系统能效，延长网络的生命周期。下一步将在单个移动节点的最大移动距离约束下优化节点的位置部署，从而提高网络覆盖性能。