水质监测机器人编队通信节点优化部署策略*

刘 昊，王 鑫，李 静，鲁旭涛

（1.中北大学信息与通信工程学院，太原 030051；2.西北机电工程研究所，陕西 咸阳 712000；3.中北大学电气与控制工程学院，太原 030051）

0 引言

水污染问题一直是影响全球的严重问题［1］，直接关系到人类的健康［2］，水质检测是治理水面污染的第一步。水质监测机器人的出现［3］，使得水质移动监测成为现实，其具有环境适应能力强、数据传输快等优势，在环境监测、渔业等方面有着广泛的前景。随着水域范围的扩大，诸多行业需要长期、实时获取一个大范围的水域内水面的相关信息时，需要建立多组机器人编队［4］。编队之间要进行实时的信息传输，则需要彼此建立起通信网络。如何设计一个合理的通信网络部署方案，是降低通信能耗、提升机器人寿命、优化机器人通信网络性能的关键所在，因而成为国内外一项研究热点。针对此类问题，Sapre S 等人将蝙蝠算法（BA）、内部搜索算法（ISA）以及飞蛾扑火优化算法（MFO）等自然启发式算法，运用到优化网络中继节点的部署来实现网络的全联通，保证了信息传输的可靠性［5］；苗春雨等人提出了面向数量最少化的双层WSN 中继节点部署算法，对网络节点数目进行了优化［6］。但此类研究目标比较单一，且场景比较理想化，仅仅进行了理论层面的研究，缺乏在具体领域内的应用。

对此，本文考虑水面多机器人组网通信系统结构，以真实水面为例，在以具体地理位置以及对实际环境的影响为权重的前提下，以编队通信网络全联通以及优化能耗为目标，采用中继节点及汇聚节点的多级、分层式信息传输方法。通过建立相关模型，并基于免疫遗传算法设计相关优化求解方法，来获得节点的优化部署方案。此外，为保证所述方法的先进性，采用传统的蝙蝠算法、遗传算法进行了对比实验与分析。

1 模型建立

1.1 被监测水域模型

本文以安徽省巢湖为例［7］，考虑实际地理位置、环境条件等对节点部署所带来的影响来对湖面进行区域划分，通过在地图上建立直角坐标系来获取各个节点的位置。水质监测机器人编队在指定区域、按照规划路径进行数据采集。

根据实际地理位置情况，首先将湖面划分为A、B、C、D、E 5 个区域，在每一个区域内部署一个信息中继节点。图中坐标系依据地图与实际比例建立，坐标值与实际值比例为1∶10。即：每一刻度值之间间隔为500，其表示实际距离5 km。考虑到每个区域面积过大，单个机器人编队续航能力有限的情况，将5 个区域中每一个区域继续划分为4 个小区域，（尽量使得每一区域面积相等）区域编码为1 到20，每一区域内由一支水质监测机器人编队来工作；之后对地图进行栅格化划分，结果如图2 所示。

图中每一栅格尺寸为62.5×62.5，换算为实际距离为625 m×625 m。理想条件下，单个水质监测机器人编队监测路径如图2 所示。

图2 机器人监测路径图

假定机器人编队每隔625 m 进行一次水面数据采集，根据划分的水域内栅格的数量（包括对不完整的栅格进行拼接）可以估算出在指定水域内，机器人编队进行的数据采集次数n。机器人编队对指定水域完成一轮水质数据监测时，才通过信息中继节点向汇聚节点传送监测数据，由于所有机器人每次数据采样指标相同，可以认为其每次所采集的数据包大小基本相等，其每次的数据采集量用k 表示。则20 个机器人编队中，每一机器人编队每次向信息中继节点所发送的数据量为：

1.2 多水质机器人编队通信网络全联通模型

考虑到水面任务的特殊性以及水面环境的复杂性，为保证稳定可靠的信息传输，提高工作效率，避免远距离两节点之间采用大功率直接传输带来的高能耗，水质监测机器人之间的通信采用多跳式通信，多台机器人编队组成一个无线多跳式自组织网络。水质监测机器人编队通信网络，如下页图3 所示。

其中，W1，W2，…，Wn为n 台机器人组成的通信网络节点；Wp为n 台机器人通信节点所对应的信息中继节点；DA 为信息汇聚节点（指挥中心）；di，j表示节点Wi到节点Wj的距离（其中，i=1～（n-1），j=2～n）；di，p表示节点Wi（其中i= 1～n）到信息中继节点Wp的距离。

图3 水质监测机器人编队通信网络示意图

水质监测机器人编队通信流程图如图4 所示。

图4 水质监测机器人编队通信流程图

在整个工作过程中，每一台水质监测机器人负责指区域的数据采集，并将所采集的数据传送给距离最近且空闲的节点，依此类推，若某节点Wi距离信息中继节点Wp最近，则由该节点传递信息至Wp，最后由Wp将所有节点所采集的数据实时传回信息中心。

假定W=W1，W2，…，Wn为部署在水面上的一组水质机器人。任意两个水质监测机器人之间的距离可用式（3）来描述：

1.3 编队通信网络节点部署及传输能耗模型

针对水质监测机器人在特大面积水域工作时的远距离信息传输问题，采用中继节点和汇聚节点的多级、分层式信息传输方法。

首先，作出如下假设：

1）信息中继节点的最大信息转发量总可以满足所在区域各机器人编队的需求，并且由其所在区域的所有编队发送的总信息量决定；

2）一个信息中继节点只负责其所在水域的信息转发；

3）考虑到实际情况，信息汇聚节点不能建立在水面上。

基于上述假设建立模型。目标函数是使得每一信息中继节点到所在区域的各编队、汇聚节点到每一信息中继节点的信息量和距离值的乘积之和最小：

N=｛1，2，…，20｝表示所有机器人编队的集合；

Mi为备选信息中继节点位置到机器人编队i 的距离小于s 的集合，i∈N，Mi⊆N；wi表示机器人编队的单次发送信息量；

dij表示机器人编队i 到它最近的信息中继节点j 的距离；

s 为信息中继节点距离机器人编队的距离上限。

在信息汇聚节点部署时：

N=｛1，2，…，5｝表示所有信息中继节点的集合；

Mi为备选信息汇聚节点位置到信息中继节点i的距离小于s 的集合，i∈N，Mi⊆N；wi表示中继节点的单次发送信息量；

dij表示信息中继节点i 到它最近的信息汇聚节点j 的距离；

Zij为0～1 变量，表示信息中继节点对汇聚节点的需求关系，若信息中继节点要向汇聚节点j 发送信息则Zij=1，否则Zij=0；hj为0～1 变量，hj=1，表示节点j 被选为信息汇聚节点；

s 为信息汇聚节点到信息中继节点距离上限。

对于每一个机器人编队完成一次指定水域数据采集时，通过中继节点向汇聚节点完成一次信息传输的能耗Ea用如下公式计算［8］：

相关符号说明如表1 所示：

2 算法设计及参数设定

2.1 算法设计

免疫遗传算法（ImmuneGeneticAlgorithm，IGA）［9］，是将遗传算法与免疫算法组合的一种启发式智能算法。此算法将免疫算法中免疫算子引入遗传算法中，避免了遗传算法在优化求解过程中种群的退化，以获得全局最优解。

本文中，将式（6）的目标函数D 在式（7）的约束条件下的最小值作为免疫算法中的抗原，所有的备选节点对应为抗体。在寻优过程中，通过亲和度函数的值来评价所求节点部署位置解的优劣性。亲和度函数F 设计过程如下：

首先，针对算法求得违反通信网络全联通约束

2.2 参数设定

按照1.1 对各个区域的栅格划分思路，结合1.2所阐述的网络全联通的情况下，通过对实际区域进行考察调研，在以环境、地理位置等因素为权重的前提下进行综合考量，确定节点部署的可行位置：在ABCDE 每个区域内确定机器人向中继节点发送信息的位置，并且在每一区域各确定3 个备选中继节点，在全地图范围内设立5 个备选汇聚节点。具体分布如图5 所示。

图5 候选节点分布图

通过对各个区域内栅格个数进行统计，根据式（2）获得每一机器人编队对指定水域完成一次监测向中继节点发送的信息量，如下页表2 所示。

各区域的备选中继节点，备选汇聚节点的坐标（备用节点和汇聚节点编号按横坐标从左到右顺序）及信息量如表3 所示。

不同类型节点的覆盖半径如表4 所示。算法参数设定如表5 所示。

2.3 仿真流程

仿真实验步骤如下：

1）抗原识别：通过识别目标函数及约束条件（抗原），判断此问题是否被处理过。若有解决记录，则搜寻对应记忆细胞；

2）产生初始抗体群：随机产生N 个个体，然后从记忆库中提取m 个个体构成初始群体；

3）亲和度评价：利用亲和度评价公式，对步骤（2）中的群体中各个抗体进行评价；

4）抑制和促进抗体：选择亲和度高的抗体进行记忆并存入记忆库中；

表2 机器人编队发送节点位置及信息量

表3 备选节点位置及信息量

表4 不同类型节点的覆盖范围

表5 算法参数设定

5）选择算子：按照轮盘赌选择机制进行选择操作；

6）交叉算子：在节点部署问题中，采用单点交叉法进行操作；

7）变异算子：采用随机选择变异位进行变异操作；

8）新种群：基于步骤4）的计算结果对抗体群体进行选择、交叉、变异等操作得到新的群体，之后再从记忆库中取出新的记忆个体，共同构成新一代群体；

9）判断是否满足迭代终止条件，是则输出最优节点，否则返回执行步骤3）。

算法流程图如图6 所示：

图6 IGA 算法流程图

3 实验结果及数据分析

通过matlab 2016a 对上述模型按照所述步骤进行仿真。使用IGA 算法得出的节点部署方案如图7所示。

图7 IGA 节点部署方案

同样，本文利用传统的遗传算法（Genetic Algorithm，GA）［10］以及蝙蝠算法（Bat Algorithm，BA）［11］进行了仿真对比实验。得出在不同方案下，最终得到的信息中继节点以及信息汇聚节点坐标，具体结果如表6 所示。

在不同算法所得方案下，利用式（3）求得各机器人编队到其所在区域的中继节点的距离及该中继节点到汇聚节点的距离。

求解结果如图8、图9 所示。

图8 各求解方案下编队节点到各区域中继节点距离

由图8、图9 综合表4 节点覆盖范围，可得出在本文提出的方案下，各编队的通信节点均处在其所属的中继节点的覆盖半径内；各区域中继节点同样也处于汇聚节点的覆盖范围内。3 种算法求解结果均保证了整个水域内的机器编队通信网络全联通。

图9 各求解方案下各区中继节点到汇聚节点的距离

在此基础上，利用式（8）分别求得在3 种方案下水质监测机器人编队所在区域中继节点向汇聚节点完成一次信息传输时的能耗。同理，可求得3种方案下水质监测机器人编队向所在区域中继节点完成一次信息所需能耗，进而求得不同方案下的总能耗，求解结果如图10、图11 所示。

图10 各区中继节点向汇聚节点完成一次信息发送能耗对比

图11 不同算法方案下总能耗对比

综合图10、图11 的能耗结果，可以看出，在IGA 算法的求解方案下，各区域节点能耗波动最小、总能耗最小，能够有效避免中继节点因能耗差而造成网络脱节。相比在BA 算法方案下，其优化效果比较接近IGA 算法，但从图10 中可以看出其最终完成一次信息传输总能耗要比IGA 算法的方案高出7 038 mW。而对于GA 算法，在C、D、E 区均取得了最优解，但在从全局结果来看其求解方案能耗波动比较大，总能耗与其他算法方案相比最高，很明显其暴露出了GA 算法容易“早熟”的缺陷，求解结果陷入了局部最优。由此可见IGA 算法相对BA 和GA 算法具有较强的寻优和跳出局部最优的能力。以上结果表明，在本文所提出的基于免疫遗传算法的方案下，通过优化中继节点和汇聚节点的部署，保证了水质机器人编队信息传输网络全联通，有效提升了水质监测机器人编队通信网络的续航能力和存活能力，其求解结果也符合实际的问题背景。

表6 不同算法求得各区域节点坐标

4 结论

本文对多水质监测机器人编队在大面积水域环境监测过程中信息传输的问题，采用信息中继节点、汇聚节点的多级、分层式信息传输方法，并针对节点部署问题，提出一种基于免疫遗传算法的解决方案。实验对比结果表明：本方法在保证整个水质监测机器人编队网络全联通的前提下，精确地完成了各个节点优化的部署。所述方法具有实际的参考意义，特别是在解决大面积水域上组网通信时节点的部署问题方面具有较强的应用价值。