基于改进NSGA-Ⅲ算法的城市管网多传感器优化部署_吴建锋.pdf

第 36 卷 第 2 期2023 年 2 月传 感 技 术 学 报CHINESE JOUNAL OF SENSOS AND ACTUATOSVol.36No.2Feb 2023项目来源:浙江树人大学引进人才项目(KXJ0421110);2017 年浙江省教育厅一般科研项目(Y201738650)收稿日期:20220406修改日期:20220423Multi-Sensor Optimal Deployment Based on Improved NSGA Algorithm*WU Jianfeng1*，ZHAO Wenjing2，WANG Disheng3，XU Sen1，XU Zhenyu1(1College of Information Science Technology，Zhejiang Shuren University，Hangzhou Zhejiang 310015，China;2State Grid Wencheng Electric Power Supply Company，Wenzhou Zhejiang 325300，China;3College of Electronics and Information，Hangzhou Dianzi University，Hangzhou Zhejiang 310018，China)Abstract:Due to external reasons，pipeline failures occur from time to time，and it is often necessary to deploy a sensor network to monitorthe pipeline network in real time In order to obtain the best monitoring efficiency under the premise of limited resources，the deploymentproblem of sensors in the pipeline network is studied，and an improved NSGA algorithm is proposed to solve the deployment problem ofsensor networks and achieve the diversity and convergence of the solution set The network uses a graph of“G=(V，E)”composed of avertex set V and an edge set E for modeling，and encodes the individuals;with the overall coverage rate of the network and the coveragerate of the designated area by the sensor as the optimization goals，application and improvement of the non-dominated solution set are per-formed to solve the problem of optimal deployment of sensors The simulation experiment results show that the improved algorithm increa-ses the diversity of the optimization solution set and effectively solves the problem of multi-sensor optimal deployment in the pipeline net-work under the premise of ensuring the convergenceKey words:multi-objective optimization;sensor deployment;nondominated solution;differential evolutionEEACC:7220doi:103969/jissn10041699202302012基于改进 NSGA算法的城市管网多传感器优化部署*吴建锋1*，赵文静2，王迪晟3，许森1，徐振宇1(1浙江树人大学信息科技学院，浙江 杭州 310015;2国网浙江省电力有限公司文成县供电公司，浙江 温州 325300;3杭州电子科技大学电子信息学院，浙江 杭州 310018)摘要:由于外部原因管道故障时有发生，常需布置传感器网络对城市管道网络进行实时监测。为在资源有限的前提下获得最佳的监测效率，对网络中传感器的部署问题进行研究，提出了一种改进 NSGA算法对传感器网络部署问题进行求解，实现求得解集多样性和收敛性的均衡;网络采用一个由顶点集 V 和边集 E 组成的图 G=(V，E)进行建模，并对个体进行编码;以传感器对网络整体覆盖率和指定区域覆盖率为优化目标，应用并改进求解传感器优化部署问题的非支配解集。仿真实验结果表明，改进后算法在保证收敛性的前提下提高了优化解集的多样性，可有效解决管网多传感器优化部署问题。关键词:多目标优化;传感器部署;非支配解;差分进化中图分类号:TP393文献标识码:A文章编号:10041699(2023)02025108城市排水管道是基础建设的重要组成部分，是保障日常生活的重要基础设施。由于管道设备老化、外力作用原因造成管道阻塞、泄漏等故障时有发生，常需要布置传感器网络对城市排水管道网络进行实时监测。为了在传感器资源有限的前提下获得最佳的监测效率，需要寻求一系列符合实际需求的优化部署方案，是一项具有实际应用意义的多目标优 化 问 题(Multi-Objective Optimization Problem，MOP)12。MOP 通过调用多个具有约束条件的决策变量来优化多个选定的目标函数。MOP 是一个具有多个约束的非线性、非凸、不可微的问题。利用传统的搜索方法例如分层求解法3 进行求解时，按目标函数的重要程度进行排序后转化为单目标优化求解，这样求得的结果由于加入了决策者主观要求，使得目标优性和重要度的差异难以调控和把握，且对于非线性的多目标优化问题难以求解。启发式搜索方法47 在决策变量数目较大的情况下能够保证较高的收敛速度和精确度。利用启发式搜索方法求解多目标问题一般分为两类，一种是将多个目标函数赋以权重系数再进行线性累加转化为单目标优化问题，这类方法只能得到一个最优解，无法区分每个目标函数的表现情况，并且权重系数的选择需要充分考虑各个目标函数值传感技术学报chinatransducersseueducn第 36 卷尺度，选择不当就难以达到预期结果。另一种方法就是多目标进化算法(MOEA)，如 MOPSO4、NS-GA56 和 MOEAD7 算法，该类算法不需要对多个目标函数加权后线性累加转化为单目标优化问题，而且最终求解结果可以得到多个优化解。在使用多目标进化算法进行求解时，需要对目标问题建立模型，构建目标函数和决策变量空间，并根据实际问题的各项约束条件对决策变量进行编码。在本文的应用场景中，若采用一般的平面区域建模方法12，8 进行编码，由于管道对传感器网络部署的限制，算法执行时决策变量约束条件过多，边界处理较为困难且运算速度较慢。若采用文献 9 中决策空间离散分布约束优化方法对决策空间进行分块处理，在决策变量数目过多时，上述问题就会变得过于复杂化，不适用于该问题求解。文献 10 通过对 NSGA和 NSGA在各种多目标测试问题的性能进行比较后，发现在高维多目标优化的测试问题 DTLZ1DTLZ3 中，NSGA算法整体表现较好，NSGA、MOPSO 和 MOEA D 算法采用的拥挤算子和聚类算子在处理多维目标的优化问题时不能较好地评价解集的多样性11。考虑到传感器网络优化部署过程中解集的多样性及综合指标的影响，本文提出了改进后的 NSGA算法求解传感器网络的优化部署问题。主要包括三个方面:排水管网进行数学建模，构建目标函数并对个体重新进行编码;提出了一种 NSGA改进算法，引入差分算子 DE 替换原有的二进制交叉及多项式变异产生后代的策略，增强算法在进化过程中的搜索能力，提高种群的多样性;设置交叉/变异概率随迭代过程线性递减，确保引入差分算子后算法逐步收敛。1城市管道模型建立城市排水管网监测传感器的部署问题涉及到整体监测覆盖率和指定目标区域监测覆盖率的优化，属于典型的多目标优化问题，最终目的是在约束范围内寻找最优部署方案。11管网模型建立本文采用无向图模型对排水管网进行建模，模型包括顶点集 V=(xi，yi)|i=1，2，M 和边集 E=eij|i=1，2，M;j=1，2，M，其中 M 为节点编号。eij表示节点间的距离，若节点 i 和节点 j 不连接，则 eij=0，组成的图 G=(V，E)。本文中的管网模型采用 EPANET 软件的实例 Net2 进行仿真。如图 1 所示，该模型中有节点 35 个、管道 39 条。图 1Net2 管网实例12多目标优化问题城市排水管网监测传感器的部署问题的数学模型可以表述为如下形式:max z1=f1(x)，z2=f2(x)，zq=fq(x)(1)st gi(x)0，i=1，2，m(2)式中:x=x1，x2，xnT是决策变量的向量，zk是 q个线性或非线性目标函数，gi(x)是线性或非线性约束条件函数。最大化问题与最小化问题可以通过对目标函数取倒数或符号取反相互转化。在第 11 节建立模型的基础上，决策变量的编码方式由原来的横纵坐标形式 x，y(如图 1 所示)转换为所在管道位置编号和距离节点距离的形式 index，dist(如图 2 所示)。图 2原编码示意图图 3修改后编码示意图13优化目标本文主要考虑到传感器网络对指定目标区域监测覆盖率 f1fM1(2M5)和整体监测覆盖率 fM多个目标的优化。在尽量减少传感器放置数量的前提下，使目标函数 f=(f1，f2，fM)最大化，具体处理中将目标函数适应度值取倒数转化为最小化问题。252第 2 期吴建锋，赵文静等:基于改进 NSGA算法的城市管网多传感器优化部署目标函数 f1fM 1:描述传感器网络对排水管网指定区域的监测覆盖情况。对于指定监测区域，要求监测覆盖率尽可能地高。假设 Ci表示第 i 个传感器的监测覆盖范围，Cj表示第 j 个指定监测区域排水管网的管道总长度，指定监测区域内放置的传感器数量为 n，则目标函数 f1fM 1可表示为:fj=ni=1(CiCj)/Cjj=1，2，M1(3)目标函数 fM:描述传感器网络对排水管网的整体监测覆盖情况。假设传感器总数为 m，Ci表示第i 个传感器的监测覆盖情况，Call表示整个排水管网的管道总长度，则目标函数 fM可表示为:fM=mi=1(CiCall)/Call(4)2多传感器优化部署的求解算法NSGA是 Deb 等于 2014 年提出的基于算法NSGA的改进算法。相比于 NSGA，NSGA算法最大的特点就是在保留快速非支配排序和精英选择策略的基础上，淘汰了基于拥挤度进行排序保证种群的多样性5 这一方法，采用通过根据目标函数值建立的超平面生成参考点6，12，联系个体和参考点的选择方式保证解决方案的多样性。21改进的 NSGA算法一般实数编码问题中，采用 SBX 模拟二进制交叉算子13 和多项式变异产生后代个体 cm+1child1，j和cm+1child2，j，保证种群的多样性，后代个体通过式(57)得到。cm+1child1，j=05(1+)cmparent1，j+(1)cmparent2，jcm+1child2，j=05(1)cmparent1，j+(1+)cmparent2，j(5)cm+1ch