随着Kurs等人^[1]提出电磁耦合谐振能量传输技术, 将此技术引入到无线传感器网络中, 形成无线可充电传感器网络(wireless rechargeable sensor network, WRSN)^[2], WRSN脱胎于无线传感器网络, 因此WRSN应用领域同样也很广泛, 如家居^[3]、军事^[4]、交通^[5]等. 随着无线可充电传感器网络的深入研究和广泛应用, 而充电的路径规划问题已成为该领域研究的热点. 如何通过一个合理的充电顺序依次为传感器节点充电, 即设计一条合理的充电路径, 对于不同规模的传感器网络中, 充电设备又可以分为单台移动设备^[6]或者多台移动设备, 现在常用的充电设备是移动小车(MC)或者无人机, 但由于无人机飞行更便捷, 所遇到障碍物少的特点, 因此研究无人机为WRSN中的节点无线充电时的路径规划非常有意义.

在小规模的传感器网络中, 设计一个无人机补充能量即可满足需求, 但是对于大规模的传感器网络, 就需要采取多个无人机及时为传感器节点补充能量, 此外, 优化算法求解这类问题也有不少突破, 为了找到最优的充电路径同时使得充电设备的能量损耗减少, 吴蕾等人^[7]采用遗传算法解决路径问题并且提出了基于半径的聚类算法来减少目标点数目来达到降低路径距离. 雷蕾等人^[8]运用萤火虫算法来满足网络中节点的动态能耗需求, 并设置合理的动态充电时隙从而进行有效的及时充电规划. 王茜等人^[9]采用改进的鸽群算法和遗传算法混合的方式求解充电路径问题, 并且提出了基于自适应惯性权重的速度更新公式, 以加快全局搜索的收敛速度. Hong等人^[10]提出了环形漫游算法和八流算法, 使其平衡多个充电器之间的充电消耗达到节省能量. Mukase等人^[11]提出了蜉蝣算法(MA)来降低整体系统能耗和总行驶距离, 同时提高移动充电器设备的休假时间比. Jia等人^[12]发明了一种基于计算几何的算法来部署MC停留的多个充电位置为附近的传感器充电. Zhao等人^[13]设计了一种改进的蜂群算法来降低充电能耗和路径成本, 从而选出充电效率最高的路径.

上述针对求解充电路径问题, 虽然用了一些启发式算法, 通过减少目标点或者有效部署充电位置、减少充电器休假时间、加快算法的收敛速度和提高算法最优解的能力来减少充电路径上的能耗, 但是在实际充电问题中, 充电设备在传感器节点上花费时间太多会影响到在其他节点, 将等待时间过长, 因此, 不仅要考虑充电设备自身的能量消耗, 还需要对充电时间进行规划, 当多充电设备如果有不同型号, 搭配的问题也不可忽视.

针对上述存在的问题, 本文在建立多个不同类型的无人机可充电的传感器网络场景下, 综合考虑起无人机飞行路径、能量消耗、充电时间成本和无人机分配成本成为目标函数, 同时对海洋捕食者算法^[14]进行改进, 加入天牛须算法^[15], 并且加入充电模型减少了飞行的停留次数, 用新的算法解决充电路径规划问题.

1 多辆多种无人机的模型与问题描述 1.1 网络模型

考虑一种多无人机的可充电传感器网络作为本文研究的网络模型, 如图1所示, 在一个L×L平方的平面区域内随机部署n个传感器节点、基站和多个无人机, 节点之间是通过多跳路由将监测的数据发送给基站, 多个无人机从基站里出发的, 从高空中采取一对多充电的方式为地面的待充节点集进行无线充电, 节点在无人机的充电范围内就可以接收能量, 最后, 所有的无人机返回到基站休息来补充能量.

1.2 能耗模型

在传感器网络中, 传感器的工作主要是对所检测的数据进行处理. 在接收数据过程中是会消耗能量的, 能量消耗的模型公式如式(1)所示:

$ {E_r} = ERX \times cm\;\;\; $

(1)

其中, $ ERX $ 为接收每比特信息消耗的能量, 数值为 $5 \times {10^{ - 14}} \; {\rm{J/bit}}$ , $ cm $ 为接收数据中控制信息的大小.

数据传输消耗能量公式如式(2)所示:

$ {E_t} = \left\{ \begin{gathered} ETX \times dm + Efs \times dm \times {d^2}, \; d < {d_0} \\ ETX \times dm + Efs \times dm \times {d^4}, \; d \geqslant {d_0}\; \\ \end{gathered} \right.\;\; $

(2)

式(2)指的是, 距离基站越远的节点, 消耗的能量会更多, 其中 $ETX$ 是传输每比特信息消耗的能量, 数值为 $5 \times {10^{ - 14}} \; {\rm{J/bit}}$ , $dm$ 为传输数据中数据信息的大小, $Efs$ 是节点本身耗散的能量, $d$ 是节点到基站的距离, ${d_0}$ 是常量, 节点到基站之间的距离临界值为30 m.

无人机给传感器节点充电中, 主要是分为飞行途中消耗能量和无线能量发射单元消耗(给传感器补充的能量), 如图2所示.

无人机总能量消耗公式模型如下:

$ {E_{{\rm{zong}}}} = {E_f} + {E_b}\;\; $

(3)

$ {E_f} = {P_f} \times {T_f} = {P_f} \times \frac{L}{V}\;\;\; $

(4)

$ {E_b} = {P_d} \times \sum {{t_i}} $

(5)

$ {t_i} = \frac{{{E_{\max }} - {E_i}}}{{{P_d}}} $

(6)

其中, ${P_f}$ 为无人机飞行的功率, ${T_f}$ 为飞行的时间, $V$ 是飞行的速度, $L$ 是飞机的距离, $ {P_d} $ 为无人机固定发射功率, 式(6)中的 ${t_i}$ 是每个传感器节点所补充能量的时间, ${E_{\max }}$ 是传感器节点的最大电池容量, ${E_i}$ 为传感器节点的没有充电之前的能量.

1.3 充电模型

选择正六边形结构的充电簇, 可以覆盖整个网络区域^[16], 本文的充电模型如图3所示, 根据在充电半径r内是可以接收无人机的能量进行充电, 假设本文的网络区域中可以按照多个正六边形拼接而成, 那么这就可以把无人机飞行途中的停留点, 也就是把需要到达待充节点的这个位置变为正六边形的正中心的位置点.

1.4 问题描述

本文中, 根据参考文献[9]设置了两种不同类型的无人机给传感器节点充电. 在这个过程中, 主要研究的问题是: 在每个无人机所能承受的充电能力没有超过自身的电池容量约束下, 合理分配出无人机的数量, 使其多无人机充电路径规划的成本最小化. 将该问题描述为:

$ \min F $

(7)

约束条件为:

$ \max (m) < M $

(8)

$ {{c}}harg e({C_i}) \leqslant {E_{{\rm{uav}} {\text{-}} \max }}, \; 1 \leqslant i \leqslant M\;\; $

(9)

$ \sum\limits_i^N \; {S_{charge, i}} \subseteq V $

(10)

$ {\textit{consume}}({S_i}) \leqslant {E_{\max }}, \; 1 \leqslant i \leqslant M\;\; $

(11)

$ {q_i} \leqslant {t_i} \leqslant {{\textit{z}}_i} $

(12)

式(8)中的 $ M $ 为无人机的最大的总数, 意思是无人机的分配数量不大于无人机的总数量.

式(9)中的 $charg e({C_i})$ 表示第 $ i $ 个无人机给节点充电的能耗不大于 ${E_{{\rm{uav}} {\text{-}} \max }}$ (无人机本身能量). 式(10)中的 ${S_{charg e, i}}$ 表示所需充电节点序列不大于 $ V $ (总节点序列). 式(11)中的 ${\textit{consume}}({S_i})$ 表示第 $ i $ 节点所消耗的能量都不大于 $ {E_{\max }} $ (节点本身的能量). 式(12)表示无人机给第 $ i $ 个节点充电的时间 $ {t_i} $ 要在请求充电的时间 $ {q_i} $ 和维持节点运行时间 $ {{\textit{z}}_i} $ 之间.

$ {f_1} = \sum\limits_i^N {\;\sum\limits_m^M {(di{s_{i, i + 1}} + di{s_{m, 0}})} } \;\; $

(13)

$ {f_2} = \sum\limits_i^N {\;{P_f} \times \frac{{di{s_{i, i + 1}}}}{V}} \;\; $

(14)

$ {f_3} = \sum\limits_i^N {\;\sum\limits_m^M {(({t_{i, m}} - {{\textit{z}}_{i, m}}) \times {\textit{z}}\cos t + ({q_{i, m}} - {t_{i, m}}) \times q\cos t)} } \;\; $

(15)

$ {f_4} = {M_1} \times a\cos t + {M_2} \times b\cos t, \; 0 \leqslant {M_1} + {M_2} \leqslant M\;\; $

(16)

$ F = \frac{{{f_1} + {f_2} + {f_3} + {f_4}}}{4}\;\; $

(17)

关于 $ F $ 成本目标模型是由无人机路径距离, 能量消耗, 时间成本和无人机分配成本组成, 其中, 式(13)中的 ${f_1}$ 是无人机充电飞行距离, 式(14)中的 ${f_2}$ 就是无人机飞行消耗能量, 是把每个无人机对所需节点序列进行充电所消耗的能量的总和. 式(15)中的 ${f_3}$ 是充电时间成本, 并且充电时间是在式(12)的约束下进行的, 当无人机到达节点的时间大于维持节点运行时间, 将产生等待成本为 ${\textit{z}}\cos t$ , 当无人机到达节点的时间小于请求充电的时间, 将产生等待成本为 $q\cos t$ . 式(16)中的 ${f_4}$ 是无人机的选取成本, 有两种无人机型号, 它们电池容量和成本都不一样, 并且无人机分配的数量小于无人机的总数. 式(17)也就是说对 ${f_1}, {f_2}, {f_3}, {f_4}$ 取均值, 用组合而成的新成本目标 $ F $ 反映路径距离、能量消耗、时间成本和搭配成本的最优情况.

2 改进的海洋捕食者算法BMPA 2.1 海洋捕食者算法

海洋捕食者算法(MPA)主要是模拟海洋生物捕食的行为. 在MPA中, 捕食者与猎物是相对的, MPA的种群个体都以猎物表示, 当一头猎物捕获到它的猎物时, 它就升为捕食者, 其位置为当前的最优解. MPA算法的关键是三段优化和FADs效应.

2.1.1 三段优化

三段优化是MPA的重要过程, 主要是为了模拟捕食者和猎物的整个生命周期, 达到从解空间的全局搜索到对解空间的当前最优解位置进行局部搜索过渡, MPA的第1阶段是在迭代初期(当前迭代的次数小于总迭代次数1/3), 通过布朗随机游走更新猎物的位置, 公式如下:

$ {\textit{Stepsiz}}{e_i} = {R_b} \times (Elit{e_i} - {R_b} \times Pre{y_i}), \; i = 1, 2 ,\cdots, n\;\;\; $

(18)

$ Pre{y_i} = Pre{y_i} + P \times R \times {\textit{Stepsiz}}{e_i}\;\; $

(19)

其中, ${\textit{Stepsiz}}{e_i}$ 是猎物的移动步长, ${R_b}$ 是布朗运动, $P$ 是常量为0.5R是表示的(0, 1)的均匀随机变量.

第2阶段是在迭代中期(迭代的次数小于总迭代次数2/3), 种群被分为两部分, 其中猎物是Levy运动, 捕食者是布朗运动, 前者负责在搜索空间内开发, 后者负责在搜索空间内探索. 前一半种群更新公式如式(20), 后一半种群更新公式如式(21).

$ \begin{split} Pre{y_i} =& Pre{y_i} + P \times R \times {R_l} \times (Elit{e_i} - {R_l} \times Pre{y_i}), \\ &i = 1, 2, \cdots, n \end{split} $

(20)

$ \begin{split} Pre{y_i} =& Elit{e_i} + P \times CF \times {R_b} \times ({R_b} \times Elit{e_i} - Pre{y_i}), \\ &i = 1, 2 ,\cdots , n \end{split} $

(21)

$ CF = {\left(1 - \frac{{Iter}}{{Max}}\right)^{\left(\frac{{2 \times Iter}}{{Max}}\right)}}\;\; $

(22)

其中, ${R_l}$ 是模拟Levy运动的随机向量, $CF$ 是控制捕食者移动步长的自适应参数.

最后一个阶段是在迭代后期(迭代的次数发生在最后是总迭代次数的1/3), 该阶段捕食者和猎物速度都慢, 此时捕食者的策略为Levy运动, 公式如式(23):

$ \begin{split} Pre{y_i} =& Elit{e_i} + P \times CF \times {R_l} \times ({R_l} \times Elit{e_i} - Pre{y_i}), \\ &i = 1, 2, \cdots , n \end{split} $

(23)

2.1.2 FADs效应解决局部收敛

FADs效应指的是鱼群喜欢聚集在某个地方, 可以引申为局部最优解, 算法在优化过程中通过设置更长的跳跃可以避免陷入局部最优, 公式如式(24):

$ \begin{split} &Pre{y_i} =\\ &\left\{ \begin{gathered} Pre{y_i} + CF({X_{\min }} + R \times ({X_{\max }} - {X_{\min }})) \times U, \;\, \quad{\rm{if}}{\text{ }}r \leqslant FADs \\ Pre{y_i} + (FADs(1 - r) + r) \times (Pre{y_{l1}} - Pre{y_{l2}}), {\rm{if}}{\text{ }}r > FADs \\ \end{gathered} \right.\;\; \end{split} $

(24)

其中, $FADs$ 表示影响算法优化过程的概率, 通常情况下取0.2; $U$ 是通过在[0, 1]中生成一个随机数组, 如果随机数组小于 $FADs$ , 则 $U$ 转换为0, 如果随机解大于 $FADs$ , 则 $U$ 转换为1. $r$ 表示[0, 1]中产生的一个随机数, ${X_{\max }}$ 和 ${X_{\min }}$ 表示包含维数上下限, $Pre{y_{l1}}$ 和 $Pre{y_{l2}}$ 是猎物矩阵的每行数据为一组的随机排列的新矩阵.

2.2 改进的海洋捕食者算法 2.2.1 MPA算法参数的改进

移动步长的自适应参数 $CF$ 对MPA迭代优化过程中勘探与开采的平衡有重要影响. 式(22)表示在迭代过程中 $CF$ (1–0), 移动步长的自适应参数增加了全局开发^[17], 为此, 本文提出了一种新的非线性的移动步长的自适应参数, 如式(25)所示, 旨在进一步改善勘探与开发的平衡, 提高全球搜索能力, 促进局部研究的快速收敛.

$ CF = \cos {\left(\frac{{\text{π}} }{2}\left(1 - \frac{{Iter}}{{Max}}\right)\right)^{\left(\frac{{2 \times Iter}}{{Max}}\right)}}\;\; $

(25)

2.2.2 BMPA混合算法的基本思想

海洋捕食者算法虽然在解决一些复杂的优化问题上优势明显^{[18, 19]}, 但在解决路径问题上存在收敛速度慢和寻优精度低等问题^[20]. 天牛须搜索算法则与其他仿生类算法不同, 天牛须算法是一种单体搜索算法, 天牛觅食时会利用左右触须来感知食物的气味强度, 如果左边触须收到的气味强度大, 它下一步就往气味强度大的左边飞, 否则往右边飞, 天牛所找到位置即为可行解, 且天牛须搜索算法前期收敛性强, 为了进一步增加MPA算法的搜索能力, 本文将天牛须搜索算法(BAS)与改进的MPA算法结合^[21]起来解决充电规划的问题.

首先使用天牛须搜索算法在大范围内搜索一组粗略解, 然后以这组粗略的解作为海洋捕食者算法的初始种群, 然后利用MPA算法不断的游走碰到捕食者之后, 将更新好的精英代入BAS算法再进行游走更新, 然后比较MPA更新好的精英个体的目标函数值和BAS更新好的精英个体的目标函数值, 更新公式如下所示:

$ dir = \frac{{rand(1, k)}}{{eps + norm(rand(1, k))}}\; $

(26)

$ {d_0} = \frac{{step(i)}}{c}\; $

(27)

$ {B_{{\rm{right}}}}(i) = X(i + 1) - dir \times {d_0}\; $

(28)

$ {B_{{\rm{left}}}}(i) = X(i + 1) + dir \times {d_0}\; $

(29)

$ B(i + 1) = X(i + 1) - dir \times sign(F({B_{{\rm{left}}}}(i)) - F({B_{{\rm{right}}}}(i))) $

(30)

$ X(i + 1) = \left\{ \begin{gathered} B(i + 1), \; F(B(i + 1)) < F(X(i + 1)) \\ X(i + 1), \; F(B(i + 1)) \geqslant F(X(i + 1)) \\ \end{gathered} \right.\;\; $

(31)

其中, $eps$ 表示1到它下一个浮点数之间的距离的一半, $rand(1, k)$ 表示生成k维的变量, $dir$ 是天牛的右须, 指向左须的向量的朝向, $c$ 是天牛步长和两须之间的比, ${d_0}$ 是天牛须的之间的长度, $X(i + 1)$ 为执行MPA后更新的精英个体, ${B_{{\rm{left}}}}(i)$ 和 ${B_{{\rm{right}}}}(i)$ 分别为天牛的左须的和右须的位置, $B(i + 1)$ 为BAS更新后的精英个体, $sign$ 为符号函数, $step(i)$ 为第i次迭代的步长, $F$ 为目标函数.

该混合算法既有海洋捕食者算法全局寻优的特性, 又具备天牛须搜索算法的前期收敛快的特性, 算法流程图如图4所示.

算法具体步骤如下.

Step 1. 输入传感器节点的集合, 结合充电模型得到待充节点的位置.

Step 2. 种群初始化, 根据搜索空间每一维的上界和下界, 用天牛须搜索算法搜索一组粗略解当作初始化猎物矩阵, 对每一个猎物个体计算其目标函数值, 然后使用最优个体复制成同规模同纬度的精英矩阵.

Step 3. 在迭代次数范围内, 经过3个阶段更新得到的精英个体, 代入BAS算法继续搜索寻优, 最后与其对比, 最优个体替代原来精英矩阵中相应的个体(一个精英个体即为问题的一个解).

Step 4. 最后, 鱼类聚集装置(FADs)是会改变海洋捕食者觅食行为, 这一策略使在寻优过程中克服早熟收敛问题, 逃离局部极值. 然后计算适应度值, 更新最优位置.

Step 5. 判断是否满足停止条件, 如果不满足则重复Step 3–5, 否则输出算法最优结果.

2.3 BMPA运用到WRSN的充电路径规划上

研究多辆无人机的充电方案的问题, 就是要寻找到充电成本最小的无人机路线, 因此, 本文将对4个目标 ${f_1}, {f_2}, {f_3}, {f_4}$ 线性整合为一个单目标 $ F $ , $ F $ 为该算法的成本目标函数, 具体转换如式(18)所得.

对于无人机充电的路径规划问题, 本文采用整数编码的方式, 有 $ m $ 个无人机为 $ n $ 个待充节点充电, 假设0为基站, 节点充电的顺序为 (0, $ {i_{1, 1}} $ , $ {i_{1, 2}} $ , …, $ {i_{1, a}} $ , 0; 0, $ {i_{2, 1}} $ , $ {i_{2, 2}} $ , …, $ {i_{2, b}} $ , 0, …, 0, $ {i_{m, 1}} $ , $ {i_{m, 2}} $ , …, $ {i_{m, n}} $ , 0), 起始节点都为0, 同时 $ a $ 和 $ b $ 代表的是无人机负责充电节点的个数, 而两个0之间的序列为子序列, 如图5所示, 这些数字代表着节点的序号, 相当于矩阵, 每行指的是序号, 每列代表着节点的位置和能量等属性. 通过算法优化, 最终就可以得到最佳路径, 该路径可被看作种群内的一个体, 节点序号排版的序列为个体的属性, 并且子序列代表着一次飞行的轨迹, 有几个子序列就代表着安排了几次飞行.

3 仿真和性能分析

本文使用的是Matlab R2022a软件, 根据参考文献[9]给定参数如表1, 搭建实验仿真场景, 将本文改进算法(BMPA)和MPA算法, BAS算法和PreWBAS算法^[22]分别在同一场景下进行比较.

假设40个节点分布在100×100平方米的监控区域内, 如图6所示, “○”是待充节点, “×”是基站.

使用本文算法得到的多个无人机的充电轨迹图为图7、图8所示, 图7是原始充电轨迹图, 图8是加入充电模型之后的轨迹图, 可以看出不用去遍历每个节点, 只需要飞行到这些节点所在充电半径内的正六边形正中心的位置即可, 明显飞行停靠次数减少. 表2列出了使用本文算法在有无充电模型下的总飞行路径距离的3次实验数据结果, 可以看出在加入充电模型后总飞行路径是减少了.

3.1 收敛性性能比较

为了验证BMPA的收敛性能, 将其在成本目标函数F上进行收敛性能实验, 如图9所示, 本文改进后的算法BMPA对比其他算法, 其收敛速度是最快的, 也获得了最优的解. 4种算法在独立运行10次获得的平均运行时间如图10所示, BAS耗时最低, 随后是MPA (10.18 s)、BMPA (10.89 s)和PreWBAS (11.16 s), 本文算法BMPA运行时间不是最低的原因是, 本文提出的改进策略是替代策略加混合策略, 会有额外的计算. 表3列出了基于4种不同算法下的目标函数和路线, 并且对无人机分配情况做出了说明, 可以看出B型无人机次数比A型多, 说明考虑时间的优先级要高于无人机的本身的成本, 并且本文算法BMPA的充电成本是最低的, 比BAS、MPA和PreWBAS算法的目标函数分别减少了50.90%、4.85%和14.38%.

3.2 无人机路径能量消耗分析

在相同的参数设置下进行多次仿真实验, 分析无人机在不同节点数目下飞行消耗, 进一步验证本算法的性能的优越性.

从图11可以看出, 在节点数为40的时候, 本文算法飞行消耗能量比BAS、MPA和PreWBAS算法少36.12%、5.25%和8.03%, 随着节点数增多, 无人机的路径消耗也在增加, 本文提出的算法路径消耗相较于其他对比算法也是最低的.

4 结语

本文通过对无人机充电路径进行分析, 以路径、能耗、时间成本和无人机搭配成本为最小为优化目标, 提出改进的海洋捕食者算法和天牛须搜索算法结合的新算法. 对比传统的海洋捕食者算法和天牛须算法, 提出的算法能有效地降低成本.

在未来的工作里, 将在三维空间内对无人机的部署问题进行研究, 使其更加符合部署实际.