0 概述

无线传感器网络(Wireless Sensor Network, WSN)是由大量传感器节点组成的分布式感知网络, 具有自组织、高鲁棒性等特点。随着无线通信技术和嵌入式硬件的快速发展, WSN已被广泛应用于战场环境监测、工业控制和灾难管理等^[1-3]领域。WSN能否有效发挥系统性能, 很大程度取决于传感器节点部署方案提供的网络覆盖质量。其中, 静态传感器网络覆盖范围受部署方案确定的传感器初始位置影响显著。由于实际部署环境的危险性和不确定性, 通常只能采用无人机搭载等非人为方式部署静态传感器节点, 而风力和建筑等环境因素往往影响传感器节点的实际着陆位置, 导致目标区域覆盖率较低, 存在大量不可避免的覆盖空洞^[4], 即使部署大量冗余节点, 也无法确保覆盖质量达到预期效果, 此外还将产生大量不必要的成本。

解决上述问题的一种方案是部署具备移动能力的传感器节点。移动传感器具备与静态传感器相同的通信和计算能力, 并且能够在部署后移动到指定的目标位置, 以满足部署方案的覆盖要求。文献[5]提出一种基于VL(Voronoi Laguerre)图的节点自主部署算法, 有效提高了节点分布的均匀性和网络的覆盖率。文献[6]将目标区域划分为若干网格, 通过粒子群优化(Particle Swarm Optimization, PSO)算法指导传感器节点移动到低覆盖率候选网格以提高WSN覆盖范围。文献[7]提出一种基于萤火虫算法的部署优化方案, 该方案不需要对传感器节点进行集中控制, 适用于大规模WSN部署。文献[8]研究如何最大限度地减小传感器节点二次移动的距离, 降低了节点能耗, 延长了网络生命周期。然而, 以上研究要求网络中所有传感器节点均具备移动能力且能移动到任何位置, 这在很大程度上增加了网络的部署成本, 同时也使路由和信息交换变得更为复杂^[9], 限制了WSN在许多现实场景中的应用。

考虑到静态传感器网络覆盖率不高和移动传感器网络部署成本高的问题, 文献[10]提出一种由移动传感器节点辅助静态传感器节点部署的混合WSN, 通过将混合传感器节点非均匀地部署于目标区域, 可以在保证网络覆盖范围的前提下有效控制成本, 已成为当前WSN研究领域的前沿和热点之一。文献[11]提出一种基于网格划分的混合传感器节点部署算法, 该算法实现简单, 但计算成本较高。文献[12]基于遗传算法(Genetic Algorithm, GA)实现了对混合WSN节点的优化部署, 该算法具有较好的全局择优能力, 网络覆盖率较高, 但时效性不高。文献[13]提出基于PSO算法的混合WSN覆盖优化方法, 在一定程度上提高了覆盖范围, 但存在陷入局部最优和迭代过久的可能。文献[14]采用改进鱼群优化算法增强了局部搜索能力, 提高了目标区域的覆盖率, 但是没有考虑节点移动距离的影响, 且算法后期时间复杂度迅速增长。文献[15]提出一种基于虚拟力的混合WSN优化部署策略, 在覆盖率和移动距离等性能方面较移动传感器网络部署有所提升, 但是虚拟力算法的实现过于依赖传感器节点间的相互位置关系, 在节点密度较大的WSN中易受限制, 导致优化失败。

针对上述算法未考虑传感器节点移动距离带来的能耗问题, 本文提出一种基于布谷鸟搜索(CS)算法的混合WSN覆盖优化策略。采用CS算法确定移动传感器节点候选目标位置以提高WSN的区域覆盖率, 并通过位置优化方案减少移动的传感器节点数量和缩短平均移动距离, 以确定最佳目标位置, 延长WSN的生存周期。

1 问题描述 1.1 前提假设

本文的讨论基于以下假设:

1) 在目标区域部署了n个传感器节点的混合WSN, 其中, m个移动传感器节点, n-m个静态传感器节点。传感器节点集定义为:

$ S=\left\{s_{1}, s_{2}, \cdots, s_{m}, \cdots, s_{n}\right\} $

(1)

2) 所有传感器节点同构, 并且具有相同的感知范围R_s和通信范围R_c=2R_s^[16]。

3) 每个传感器节点可通过某种机制(例如GPS或其他定位算法)获取其位置信息, 并且可以将位置信息发送到基站。

4) 移动传感器节点具有充足能量, 确保其能够移动到范围内指定位置。采用欧氏距离计算传感器节点$ s_{i}=\left(x_{i}, y_{i}\right)$和$s_{j}=\left(x_{j}, y_{j}\right) $之间的距离:

$ d_{i j}=\sqrt{\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2}} $

(2)

5) 本文算法以集中式架构实现, 基站负责算法的执行并将移动方案分发到各移动传感器节点^[17]。

1.2 问题模型

假设目标区域A是二维平面, 且数字化为L×H的网格, 其中每个网格大小等于1^[18]。传感器节点s_i的覆盖范围可以表示为以其坐标$ \left( {{x_i}, {y_i}} \right)$为中心的圆, 半径为感知范围R_s。随机事件H_i表示描述网格点$ G\left( {{x_g}, {y_g}} \right)$被传感器节点s_i覆盖, P{H_i}表示随机事件H_i发生的概率, 等同于覆盖概率$P\left\{ {{s_i}, \left( {{x_g}, {y_g}} \right)} \right\} $。覆盖概率由布尔感知模型表示^[4]:

$ P\left\{ {{s_i}, \left( {{x_g}, {y_g}} \right)} \right\} = \left\{ {\begin{array}{*{20}{l}} {1, d\left[ {{s_i}, \left( {{x_g}, {y_g}} \right)} \right] \le {R_s}}\\ {0, d\left[ {{s_i}, \left( {{x_g}, {y_g}} \right)} \right] > {R_s}} \end{array}} \right. $

(3)

假设随机事件H_i独立于其他事件, i, j∈[1, n]且i≠j, 因此, H_i和H_j不相关, 同时可以得到以下2种关系^[16]:

$ {P\left\{ {{{\bar H}_i}} \right\} = 1 - P\left\{ {{H_i}} \right\} = 1 - P\left\{ {{s_i}, \left( {{x_s}, {y_s}} \right)} \right\}} $

(4)

$ {P\left\{ {{H_i} \cup {H_j}} \right\} = 1 - P\left\{ {{{\bar H}_i} \cap {{\bar H}_j}} \right\} = 1 - P\left\{ {{{\bar H}_i}} \right\} \cdot P\left\{ {{{\bar H}_j}} \right\}} $

(5)

其中, $ \overline {{H_i}} $是H_i的补集, 表示网格点$ G\left( {{x_g}, {y_g}} \right)$不被传感器节点s_i覆盖这一事件。如果节点集中的任一节点覆盖了网格点$ G\left( {{x_g}, {y_g}} \right)$, 则可以认为网格点$ G\left( {{x_g}, {y_g}} \right)$被节点集覆盖。因此, 网格点$ G\left( {{x_g}, {y_g}} \right)$被节点集覆盖这一事件可认为是随机事件H_i并集, 其概率表示如下:

$ \begin{array}{l} P\left\{ {S, \left( {{x_g}, {y_g}} \right)} \right\} = P\left\{ {\mathop \cup \limits_{i = 1}^n {H_i}} \right\} = 1 - P\left\{ {\mathop \cap \limits_{i = 1}^n {{\bar H}_i}} \right\} = \\ 1 - \prod\limits_{i = 1}^n {\left( {1 - P\left\{ {{s_i}, \left( {{x_g}, {y_g}} \right)} \right\}} \right)} \end{array} $

(6)

1.3 相关定义

为便于讨论, 对本文涉及的2个重要概念进行定义。

定义1 (区域覆盖率)   区域覆盖率表示所有传感器节点感知区域的并集与目标区域总面积的比值, 反映了覆盖质量的好坏, 定义为R_area(S):

$ {R_{{\rm{area }}}}(S) = \frac{{{A_{{\rm{area }}}}(S)}}{A} = \frac{{\sum\limits_{x = 1}^L {\sum\limits_{y = 1}^H P } \{ S, (x, y)\} }}{{L \times H}} $

(7)

其中, A表示目标区域的总面积, A_area(S)是传感器节点集S的感知区域。WSN覆盖优化算法通常选取式(7)作为目标函数, 通过最大化R_area(S)的值以提高WSN的覆盖质量。

定义2 (距离覆盖率)  距离覆盖率表示区域覆盖率与传感器节点平均移动距离的比值, 能够有效反映传感器节点移动的效率, 是衡量WSN覆盖优化算法性能的另一个指标, 定义为:

$R d(S)=\frac{R_{\text {area }}(S)}{a d(S)} $

(8)

其中, ad(S)表示传感器节点的平均移动距离。显然, Rd(S)值越高越好, 通过增大分子R_area(S)并减小分母ad(S)的值可以实现这一目的。因此, 区域覆盖率R_area(S)和平均移动距离ad(S)是本文算法的2个优化目标。区域覆盖率的提高通常伴随着平均移动距离的增加, 当区域覆盖率和平均移动距离达到一定平衡时, Rd(S)的值将增大。另一方面, 缩减移动传感器节点的平均移动距离同时保持区域覆盖率不变, 也可以增大Rd(S)的值, 这也是本文算法在第2阶段中所做的工作。因此, 选取距离覆盖率式(8)作为本文算法的目标函数, 以获取一种区域覆盖率R_area(S)较高, 同时平均移动距离ad(S)较短的传感器节点移动方案。

2 覆盖优化策略

基于上述假设与相关定义, 本文研究一种基于混合WSN的覆盖优化策略。算法主要分2个阶段执行:1)通过CS算法获取移动传感器节点的候选目标位置, 目的是提高WSN的区域覆盖率; 2)对第1阶段获取的候选目标位置进行优化以确定传感器节点的最佳目标位置。算法架构如图 1所示。

首先, 在目标区域对混合传感器节点进行随机投放, 通过GPS或定位算法获取其初始位置信息并发送给基站; 其次, 通过2个阶段的覆盖优化算法确定移动传感器节点的最佳目标位置; 最后, 基站将算法得到的最佳移动方案分发到各传感器, 进行节点重部署^[19]。下文主要对本文算法的2个优化阶段进行具体阐述。

2.1 基于CS的覆盖优化算法

CS算法最早由文献[20]提出, 是一种模拟布谷鸟侵略性寻巢孵蛋这一繁殖特性的仿生优化算法。CS算法需要设置的参数较少, 流程简单且收敛速度快, 对许多优化问题具有较好的鲁棒性, 已在工业设计等实际问题中广泛应用^[21-23]。

CS算法基于以下3个理想规则^[20]:

1) 每只布谷鸟一次只产下一个蛋, 并将蛋随机放在选择的宿主巢中进行孵化;

2) 在随机选择的一组巢中, 质量最优的巢将被保留到下一代;

3) 可用宿主巢的数量是固定的, 由宿主鸟发现的布谷鸟蛋的概率是P_a, 且P_a∈[0, 1], 通常取固定值^[20]。在这种情况下, 宿主鸟可以将布谷鸟蛋扔掉或丢弃该巢, 并重新寻找位置建立一个全新的巢。

基于上述3个规则, 利用图 2所示流程表示CS算法的主要步骤。CS算法采用Lévy飞行搜索机制, 适应度函数主要用于在N维空间中搜索最佳巢(解)时引导Lévy飞行。

Lévy飞行被定义为基于重尾概率分布步长的随机游走, 是一种长短距离相间隔的游走方式, 而非简单的各向同性的随机游走, 将确保算法具有很好的局部寻优能力^{[20, 24]}。当新的解产生时, 算法根据Lévy飞行搜索机制更新鸟巢位置, 公式如下:

$ x_{i}^{(t+1)}=x_{i}^{(t)}+\alpha \oplus {Levy}(\lambda) $

(9)

其中, x_i^(t)表示第t次迭代中第i个鸟巢位置, α表示步长因子, 其取值与兴趣问题的尺度相关, 通常取$ \alpha=1, \oplus$表示点对点乘法。上述等式在通常情况下是一个马尔可夫链, 其下一位置仅取决于当前位置(上述等式中的第1项)和转移概率(第2项)。Levy(λ)表示Lévy飞行随机搜索路径, 满足:

$ {Lev} y(\lambda) \sim \frac{\phi \times \mu}{|v|^{\frac{1}{\beta}}}, \beta \in(1, 3] $

(10)

其中, μ和v均服从标准高斯分布, 即:

$ \left\{\begin{array}{l}{\mu \sim N\left(0, \phi^{2}\right)} \\ {v \sim N\left(0, \phi^{2}\right)}\end{array}\right. $

(11)

ϕ满足:

$ \phi=\frac{\mathit{\Gamma}(1+\beta) \sin (\pi \times \beta / 2)}{\mathit{\Gamma}\left\{[(1+\beta) / 2] \times \beta \times 2^{[(\beta-1) / 2]}\right\}} $

(12)

CS算法作为一种基于种群的智能算法, 类似于GA算法和PSO算法。但基于重尾概率分布步长的随机游走, 使得CS算法的随机化更加有效, 寻优能力更强。当CS算法终止时, 它将输出移动传感器节点的候选目标位置, 作为算法第2阶段优化方案的输入。

2.2 目标位置优化方案

目标位置优化方案旨在通过缩减移动的传感器节点数量及平均移动距离, 达到降低节点移动能耗、延长WSN生命周期的目的, 前提是不减少网络的覆盖范围。移动传感器节点在网络覆盖优化过程中执行虚拟移动, 物理移动仅在识别出最终目标位置后执行。该方案主要从需要移动的传感器节点数量、总移动距离以及可替换的移动传感器节点等3个方面对候选目标位置进行优化。

假设P_i0(x_i0, y_i0)和P_j0(x_j0, y_j0)分别为移动传感器节点s_i和s_j的初始位置, P_i1(x_i1, y_i1)和P_j1(x_j1, y_j1)分别为传感器节点s_i和s_j的候选目标位置。$ {d_1} = |\overline {{P_0}{P_{11}}} |, {d_2} = |\overline {{P_p}{P_1}} |, {d_3} = |\overline {{P_0}{P_1}} |, {d_4} = |\overline {{P_{{j_0}}}{P_{i1}}} |$分别表示线段$\overline {{P_{i0}}{P_{i1}}} 、\overline {{P_{j0}}{P_{j1}}} 、\overline {{P_{i0}}{P_{j1}}} $和$\overline {{P_{j0}}{P_{i1}}} $的长度。具体方案描述如下:

1) 移动传感器节点数量优化。当一些传感器节点移动到第1阶段CS算法得到的候选目标位置时, 覆盖区域的位置虽然发生了改变, 但覆盖范围实际上并没有明显提高。如图 3(a)所示, 当传感器节点s_i从P_i0移动到P_i1时, 区域覆盖率R_area(S)没有变化。在这种情况下, 覆盖质量并没有得到有效改善, 这也就意味着这种移动实际上是没有必要的, 此时可以取消移动传感器节点s_i的移动计划, 如图 3(b)所示。通过这种方式, 可以减少需要移动的传感器节点数量, 同时也减少了传感器节点总的移动距离。

2) 传感器节点目标位置交换。如果2个传感器节点移动到候选目标位置后增加相同的覆盖范围, 那么可以交换这2个节点的候选目标位置。如图 4(a)所示, 当节点s_i和s_j分别移动到P_i1和P_j1后, 区域覆盖率R_area(S)提升程度相同, 此时传感器节点s_i和s_j的总移动距离为d₁+d₂, 而如图 4(b)所示交换候选目标位置之后, 节点s_i和s_j的总移动距离为d₃+d₄, 显然, d₃+d₄ < d₁+d₂。通过这种方式, 可以有效缩减节点s_i和s_j的总移动距离。此外, 由于WSN的区域覆盖率在交换后不会减小, 距离覆盖率此时也将增大。

3) 移动传感器节点替换。此步骤类似于第2)步, 区别在于其中一个传感器节点原本是不需要移动的。第3)步旨在减少传感器节点的长距离移动, 因为如果传感器节点在长距离移动过程中消耗太多能量, 那么在到达目标位置后短时间内剩余能量就会消耗殆尽, 此时必须寻找另一个移动传感器节点并重新进行部署。如图 5(a)所示, 节点s_i原本不需要移动, 而节点s_j计划从P_j0移动到P_j1。假设A₁是图 5(a)中节点s_j从P_j0移动到P_j1之后的总覆盖面积, A₂为图 5(b)中节点s_j保持静止, s_i代替s_j从P_i0移动到P_j1的总覆盖面积。可以看出, A₁ < A₂且d₂ < d₁。通过这种方式, 不仅可以增大WSN的覆盖范围, 还能够缩减传感器节点的总移动距离, 也不会增加移动的传感器节点数量, 同时还能增大距离覆盖率。

3 仿真实验分析

为验证本文所提算法性能, 选取100 m×100 m的目标区域进行仿真实验。随机部署目标区域60个混合传感器节点, 其中30 %为移动传感器节点。假设传感器节点的感知范围R_s=10 m, CS算法参数设置为:种群个数n=20, 发现概率P_a=0.25, 迭代次数T=200。初始部署节点分布如图 6所示, 其中深色圆盘代表移动传感器节点感知范围, 浅色圆盘代表静态传感器节点感知范围。从图 6可以看到, 在目标区域中存在覆盖空洞, 且部分传感器节点的感知区域重叠, 当前目标区域覆盖率为65.31 %。

3.1 算法有效性分析

为验证算法有效性, 分别对算法2个阶段的优化结果进行仿真实验, 结果如图 7所示, 其中直线段表示传感器节点从初始位置到目标位置的移动距离。

图 7(a)为第1阶段CS算法优化后的覆盖情况, 当传感器节点移动到目标位置后, 目标区域覆盖质量明显改善, 覆盖率增加到90.16 %, 此时所有移动传感器节点均发生移动, 平均移动距离为22.84 m。图 7(b)显示了算法最终的优化结果, 从中可以看到, 一些距离较远的移动被取消, 移动的传感器节点数量也减少到11个, 此时节点的平均移动距离为14.98 m。通过以上对比可知, 本文算法能够有效提高WSN的区域覆盖率, 同时可以减少移动传感器节点的数量和平均移动距离。

3.2 算法性能对比

为进一步验证算法性能, 将GA算法、PSO算法和本文算法进行比较。3种算法在相同仿真环境下分别进行1 000次独立实验, 实验结果取平均值, 如表 1所示。

从表 1可以看到, GA和PSO的区域覆盖率略高于本文算法, 但节点的平均移动距离均远大于本文算法, 导致距离覆盖率反而小于本文算法, 移动传感器节点数量也大于本文算法。这是因为GA和PSO将区域覆盖率作为算法的目标函数, 在算法执行过程中节点的移动距离没有被考虑在内, 而本文算法选择前述定义的距离覆盖率作为目标函数, 同时将区域覆盖率、移动传感器节点数量和平均移动距离进行了优化。由此可见, 区域覆盖率并不是评价算法性能的唯一标准, GA和PSO算法在优化过程中移动传感器节点消耗了更多能量, 导致WSN的生存周期更短, 而本文算法则更好地平衡了覆盖率与能耗之间的关系。

3.3 移动传感器节点比例

考虑到移动传感器节点数量对算法性能的影响, 进一步设计如下的仿真实验, 研究移动节点比例与覆盖率、平均移动距离和移动节点数量的关系。保持混合传感器节点总数不变, 改变移动节点所占比例, 每种算法分别进行1 000次独立实验后取平均值, 得到如图 8所示的实验结果。图 8(a)显示了移动节点比例对区域覆盖率的影响, 不难发现, 随着移动节点比例的上升, 3种算法对区域覆盖率均有明显提升。从图 8(b)可以看到, 本文算法在节点的平均移动距离方面具有明显优势。图 8(c)显示了移动节点数量随节点比例的变化, 在不同比例下本文算法中移动的节点数量均有一定程度减少, 且在比例较大的混合WSN中优势更为明显。综上所述, 本文算法在区域覆盖率、平均移动距离和移动节点数量等方面均有显著改善, 在保证网络覆盖率提升的前提下, 能够更好地节约网络覆盖优化的成本, 更具实用性。

3.4 传感器节点数量

为研究传感器节点数量对算法性能的影响, 在不同传感器节点数量的情况下进行实验。保持移动传感器节点所占比例不变, 改变传感器节点总数量, 每种算法分别进行1 000次独立实验后取平均值, 得到如图 9所示的实验结果。图 9(a)显示了传感器节点数量对区域覆盖率的影响, 可以看出, 随着节点数量的增加, 3种算法的区域覆盖率均有所降低, 其中PSO算法下降最为明显, 并在传感器节点数量大于120后低于本文算法的区域覆盖率, 相比而言, 本文算法的下降趋势较为平稳。从图 9(b)显示的平均移动距离和传感器节点数量的关系中可以明显看出, 本文算法在优化节点平均移动距离方面的优势。结果表明, 本文算法能够较好地实现覆盖率与节点移动能耗之间的平衡。

4 结束语

针对静态传感器网络覆盖效果不佳和移动传感器网络部署成本过高的问题, 本文在混合WSN基础上, 提出一种基于CS算法的覆盖优化策略。采用CS算法提高WSN的区域覆盖率, 并通过位置优化方案减少移动传感器节点数量和缩短平均移动距离, 以降低节点移动过程中的能量损耗。实验结果表明, 本文算法在保证网络覆盖率提升的前提下, 能够更好地节约网络覆盖优化成本, 更具实用性。