基于监测环境的多目标优化WSN部署

◆金世尧

基于监测环境的多目标优化WSN部署

◆金世尧

（沈阳化工大学计算机科学与技术学院 辽宁 110142）

无线传感器网络节点部署中，提高网络覆盖范围、降低网络成本、降低网络等是优化无线传感器网络的多个目标，提高无线传感器网络的服务质量的问题成为一个多目标优化问题。针对沈阳化工大学一个重点监测区域进行节点部署，采用了一种全新的求解多目标优化问题的思想——基于投影面的多目标优化问题进化算法，与物理模型结合后，在实现最大化覆盖区域的同时实现了最小化成本和最小化能耗。实验是在MOEA/P平台框架上实现的，证明提出的解决方案可以根据选用的硬件、应用需求生成最佳部署。结果表明，采用MOEA/P算法进行节点部署优化比采用MOEA/D算法在IGD指标上降低了32.88%。

无线传感器网络；节点部署；多目标优化；投影面；覆盖度；能耗

这项研究的背景是沈阳化工大学致本楼实验室平均每月丢失财物案件数量由每月1起增加到每月3起，通过在致本楼走廊部署人体红外传感节点（以下简称传感节点）来监测外来人员活动情况。每个传感节点由一个热释电模块（HC-SR501）和一个具有WiFi功能的ESP32模块串联构成。当传感节点检测到有人经过时，会通过ESP32中的WiFi模块向上一级汇聚节点发出信息[1]，信息上报后可以选择语音警告驱逐或者通知安保人员到现场查看。部署传感节点应使其覆盖面积尽可能大，同时节点个数和网络总能耗尽可能小，如何平衡相互冲突的目标成为一个多目标优化问题。

钱建新等人针对无线传感网络的节点部署问题，提出基于花朵授粉算法的节点部署算法，将节点部署问题转化为多目标优化问题，利用花朵授粉算法求解该优化问题，降低了网络能耗，提高了网络生存周期[2]。王若霖针对静态网络的确定性部署，节点能量有限的动态网络部署和多目标优化的节点部署进行研究，提出了基于虚拟力的多目标粒子群算法的多目标优化下的节点部署方法，解元素的分布更为均匀，具有很强的优越性和可靠性[3]。金杉从传感器层、汇聚层、网络整体三个方面覆盖优化，分别提出了解决双层WSNs覆盖协调问题的方法，有效减少了汇聚节点数，提高了汇聚层结构稳定性，平衡了网络能耗[4]。这些算法各有各的优势和侧重，但是它们都没有面向目标决策支持在指定方向上进行专门有效的求解。

本文采用的多目标优化算法采用了一种全新的求解多目标优化问题的思想——基于投影面的多目标优化问题进化算法（MOEA/P）[5]，借鉴基于分解的多目标进化算法思想，将目标空间分成投影面和自由维，根据求解需求把投影面分解成多个投影格，并在各个投影格上求解自由维的最优值，从而得到多目标优化问题的最优解。

1 问题描述

1.1 部署空间

部署区域为沈阳化工大学致本楼的一个走廊，楼层建筑平面如图1所示，实际部署区域是一个328平方米的走廊，如图2所示。

图1 楼层建筑平面图

图2 实际部署区域图

选择的部署区域中可能包含不同的障碍，例如墙、地板等。无线电信号通过这些障碍物时会导致信号衰减或者感应阻塞，会影响无线电信号的传播和感应能力。为了获得更准确的实验结果，首先测量信号在通过这三种障碍时引起的不同衰减值，测试结果如表1所示。

表1 障碍物衰减实际测量值

障碍物类型（k）厚度（cm）衰减值（dBm） 水泥墙2020 玻璃窗410 铁质卷帘门510

1.2 能耗模型

整个网络能量消耗计算公式如下：

1.3 感应模型

本文选择埃尔夫斯概率模型[7]。

1.4 成本模型

进一步得到部署成本的计算公式为

2 MOEA/P

2.1 MOEA/P相关概念

为了统一计算尺度，保证在各个目标方向上的计算均衡，需要进行目标空间归一化，这是许多算法都采用的方式。本文此后讨论的目标向量值都缺省设定为归一化后的值。为了减少所得解的数量，得到有一定代表性的较小的解集。MOEA/P[5]将目标空间分解为两部分，投影面和自由维。

定义1 投影面：根据目标决策需求选取部分主要目标维构成投影面（Projection Plane），投影面上的各目标维称为投影维（Projection Dimension）。

例如在要求高覆盖率低成本的监控场景中，覆盖率目标和成本目标非常重要，这两维会被优先设置为投影维。对于二目标优化问题，投影面就是一条坐标轴；对于三目标优化问题，投影维就是两个目标构成的一个坐标面。

本文实验采用的MOEA/P算法求得落在指定投影面上的目标向量后，以该投影面所限定的目标子空间进化求解自由维最优解。为此给出如下定义和定理。

2.2 个体编码

例如：假设部署区域如图3所示：

图3 部署区域举例

该部署区域的染色体表示为[0，2，3，1，0，1]。

2.3 目标空间划分及初始化种群

目标决策空间的设定将最优化求解空间设定到了一个较小的范围之内，可以大大缩小计算时间并提高计算精度。投影面选定之后，需要根据投影格边长对投影面进行分割，以便进一步求解。投影格由相应的投影格标识向量所标定，对投影面进行分割就是要生成相应的投影格向量，其算法如下。

投影面分割算法 输入：• k：投影面维数（前k维构成投影面）；• ω：投影格边长；输出：投影格向量集PGs过程：. 设s=1/ω，为每个投影维的分段数，则在k维投影面上可平均分割g=sk个投影格。. 设置PGs为一g*k二维数组，记录各投影格向量值. 设置tmpPGs为一维数组，记录当前投影格向量值. 设cv为当前向量下标，初值为1. 调用回溯函数ProjectVectorBackTrack（1），计算各投影格向量。 ProjectVectorBackTrack（d）　//d表示当前向量的第d维{if （d==k+1）cv++；elsefor （i = 0；i < s；i++）PGs[cv][d] = i*ω；ProjectVectorBackTrack（d+1）；}

2.4 算法框架

MOEA/P算法框架输入：• 多目标问题MOP；• 结束条件；• DS：目标决策空间（投影面）设定；• ω：投影格边长；• ε：投影格影响半径（容忍量）；• S：初始种群大小。输出：目标解集OP过程：. 步骤 1）目标空间划分. 步骤 1）目标空间划分根据DS确定MOP投影面及投影范围，并将之分割成边长为F的多个投影格PGs；设目标解集OP为空。. 步骤 2）在每个投影格上求非ε-Pareto投影格支配解对于PGs的每一个投影格，执行步骤2.1-2.3：步骤 2.1）初始化种群初始化长度为S的种群G，构造种群中个体并初始个体基因序列，保证所有个体满足MOP约束条件；对种群G每个个体进行初始计算，得到相应的目标函数值。步骤 2.2）种群进化：如果满足结束条件，转步骤 2.3；设置新一代备选列表GenPOOL；分别对种群G中的个体进化操作；计算每一个新生成个体并根据适度优先关系将之按序加入GenPOOL中；令G=GenPOOL；对G进行截断操作；重复本步骤 2.2。步骤 2.3）提交进化结果将G中所有非ε-Pareto投影格支配个体提交到OP，并保证不与OP中任何现有个体相互Pareto支配。若存在Pareto支配关系对，从OP中删去被支配的个体。步骤 3）输出OP

3 实验及讨论

作为对比，预先用MOEA/D算法（迭代次数为与种群大小均设置为2000）求解本文设计的WSN部署模型，在此情况下得到的解看作为真实的Pareto前沿，通过计算与真实前沿的距离（比如GD指标和IGD指标）来评价后续实验的优劣。IGD主要通过计算每个在真实 Pareto前沿面上的点到算法获取的个体集合之间的最小距离和，来评价算法的收敛性能和分布性能，值越小，算法的综合性能包括收敛性和分布性能越好[8]；GD是从一组候选解指向最近的真实前沿上的点的欧式距离的平均，值越小，算法的收敛性越好[8]。

在2.1节MOEA/P算法介绍中，相对重要的指标被设置为投影维。第一次实验的三个指标中，成本和覆盖率是最受用户所关注的，应该被设置为投影维；投影格数量越多，解空间内的解向量被划分得更细致，得到的解的质量更好，解的个数更多。从表2可以看出，当成本分段不小于覆盖性分段时，IGD的值更小，这是因为本文选用的部署区域是328个单元格，部署节点数量的变化范围远小于覆盖单元格数量的变化范围，换句话说，部署节点数量的轻微变化都会对覆盖单元格数量产生较大影响，所以对成本目标（节点数量）的分段适当大于覆盖单元的分段会得到略好的结果。

表2 投影维分段数量不同对结果的影响

成本目标分段覆盖率目标分段投影格数平均时间（s）（偏差）平均IGD（偏差）解的个数 22412.861（0.709）25.120（2.126）5.8 32616.479（0.517）9.487（1.233）44.4 23617.045（0.594）17.084（8.345）42 33923.481（1.069）8.468（1.546）60 431230.991（0.783）8.649（0.971）63 341230.506（0.496）7.684（0.489）61.4

第二次实验目的是在运行时间相同时与MOEA/D、NSGAII算法结果的对比，如表3所示。由于MOEA/P算法是在限定的区域内进化求解，MOEA/D算法是对整个解空间进化求解，NSGAII采用了非支配快速排序算法，所以运行速度要比MOEA/D和NSGAII算法要快，并且更接近最优解集。

表3 运行时间相同时与MOEA/D、NSGAII算法比较

算法名称（迭代次数，种群大小）平均运行时间（s）GD（偏差）IGD（偏差） MOEA/D（300，100）14.520.092（10.681）15.408（1.506） MOEA/P（110，60）14.513.225（9.164）11.595（1.201） NSGAII（300，70）14.574.891（1.696）107.156（0.259）

在监测应用中，一般要求覆盖率90%以上，同时降低成本和能耗。接着设置ESP32模块上传数据的频率为一分钟上传一次，分别采用MOEA/P算法和MOEA/D算法求解本部署模型，两个算法的种群次数和迭代次数均设置为1000，得到能耗和节点数的关系如表4和图4所示。实验结果表明采用划分求解空间并在限定空间内求解的算法质量比传统的MOEA/D算法得到的解能耗更低。

表4 覆盖率90%以上能耗与节点数关系

算法节点数（个）能耗（mAh） MOEA/D16112.21 17109.37 18101.25 1996.63 MOEA/P16106.21 17102.96 1891.5 1981.83

图4 覆盖率90%以上能耗与节点数变化曲线

最后，给出采用MOEA/P算法求解WSN节点部署问题的优化方案，该方案部署了一个汇聚节点，13个传感节点，覆盖率为92.68%，整个网络能耗为112mAh，部署位置如图5所示。

图5 计划给出的节点部署方案

4 结束语

针对无线传感网络的节点部署问题，提出采用基于投影面的多目标优化算法MOEA/P。首先将无线传感器网络节点部署问题转换成多目标优化问题，再利用MOEA/P算法搜索部署节点的最佳位置。通过部署最佳位置，提高覆盖率，降低网络能耗和成本。实验证明，采用MOEA/P算法与节点部署相结合比MOEA/D、NSGAII算法得到的结果更好。

[1]谢永超，章若冰，严俊.基于HC-SR501和DS18B20的人体感应温控直流电机控制器的设计[J]. 电子设计工程，2020，28（03）：60-64.

[2]钱建新，施沈科，何燕，等. 基于多目标优化的WSNs节点优化部署算法[J]. 兵器装备工程学报，2020，41（06）：174-177.

[3]王若霖.基于群智能算法的异构WSN节点部署优化研究[D]. 哈尔滨工程大学，2020.

[4]金杉. 无线传感器网络的覆盖优化方法研究[D]. 天津大学，2017.

[5]杨爽，陈未如.基于投影面的多目标进化算法MOEA/P [J].沈阳化工大学学报，2021.

[6]浦和鸣.基于分级结构的无线传感器网络节能策略研究[D]. 电子科技大学，2020.

[7]Yun Z，Teng J，Yu Z，et al. Notice of Violation of IEEE Publication Principles：Connected Optimal Two-Coverage of Sensor Networks[J]. IEEE/ACM Transactions on Networking，2019：1-12.

[8]冯水凤.基于指标的多目标优化算法研究[D]. 广东工业大学，2020.