供水管网水质监测传感器网络布局优化

第38卷第6期2017年6月白动化仪表PROCESSAUTOMATIONINSTRUMENTATIONVol.38No.6June.2017供水管网水质监测传感器网络布局优化沈一凡，魏冠雄，侯迪波，黄平捷，张光新，张宏建(浙江大学控制科学与工程学院，浙江杭州310027)摘要：为应对突发污染物注入预防供水管网的问题，水质监测传感器网络布局优化已越来越多地受到研究关注。针对基于“服务水平”概念的布局优化模型易受主观因素干扰的问题，提出了污染事件检测时间最短模型。该模型以污染事件平均检测时间为优化目标，无需人为设定“服务水平”，所得布局方案监测点数量完全由预算决定。一旦给定监测点数量，能够保证污染事件平均检测时间最优，充分保证了模型的客观准确性。对供水管网系统状态进行了平均化处理，提高了计算资源的空间利用率。同时，针对目前常用的模型参数寻优算法难以满足大规模供水管网模型求解的特点，提出了基于多线程机制的并行粒子群优化（PS0)算法，从而充分发挥多核心处理器的计算能力，提高了硬件资源的利用率，加快了模型计算的速度。试验结果表明，所提出的模型和优化算法对实际的供水管网水质监测网络布局优化选址具有一定的参考作用。关键词：供水管网；水污染；水质监测网络；并行粒子群算法；节点优化布局；时间最短模型；多线程；拓扑结构中图分类号：TH81;TP23文献标志码：ADOI：10.16086/j.cnki.issnl000-0380.201706012OptimizationoftheLayoutofWaterQualityMonitoringSensorsNetworkforWaterDistributionNetworkSHENYifan,WEIGuanxiong,HOUDibo,HUANGPingjie,ZHANGGuangxin,ZHANGHongjian(CollegeofControlScienceandEngineering,ZhejiangUniversity,Hangzhou310027,China)Abstract：Todealwiththesuddenpollutantinjection,theoptimizationoflayoutofwaterqualitymonitoringsensorsforwaterdistributionnetworkhasbeenmoreandmoreconcernedinresearch.Toagainsttheshortcomingofthelayoutoptimizationbasedontheconceptof“servicelevel”whichiseasilytobedisturbedbysubjectivefactors，themodeloftheshortestdetectiontimeforpollutionincidentisproposed.Withtheaveragedetectiontimeofthepollutionincidentastheoptimizationobject,themanualsettingof“servicelevel”isunnecessary，thenumberofthedetectionpointsofthelayoutstrategyprovidedbythemodelisfullydeterminedbybudget,oncethenumberofmonitoringpointsisgiven,theaveragedetectiontimeofthepollutionincidentisoptimum,andtheobjectiveaccuracyofthemodelcanbeguaranteed.Thestatusofthewaterdistributionnetworkisaveragingprocessedtoimprovethespatialutilizationofcalculationresources.Inaddition,becausethecommonlyusedoptimizingalgorithmsofmodelparameterscannotsatisfytherequirementforlargescalewaterdistributionnetwork,theparallelPSOalgorithmbasedonmulti-threadingmechanismisalsoproposed.Thisfullyplaysthecapabilityofmulti-coreprocessor,andenhancestheutilizationofhardwareresourceandthemodelcalculationspeed.Thetestresultsindicatethatthemodelandalgorithmproposedpossesscertainreferencesignificanceforlayoutoptimizationofwatermonitoringsensorsinwaterdistributionnetwork.Keywords：Waterdistributionnetwork；Waterpollution；Waterqualitymonitoringnetwork；ParallelPSOalgorithm；Nodelayoutoptimization；Modeloftheshortestdetectiontime；Multithreading；Topologystructure〇引言近年来，供水管网中突发污染物注入已成为各国政府重点防范的供水管网系统水污染来源，造成了严重的危害和损失。在每个节点设置监测仪器成本巨大，不切合实际，因此需要优化监测网络布局。针对此类问题，Kumar等[3_4]首先提出了“q体积服务水平”的概念。“q体积服务水平”即从污染物开修改稿收到日期:2016-03-16基金项目：国家自然科学基金资助项目（U1509208、61573313)、浙江省重点研发计划基金资助项目（2015C03G2010034)、中央髙校基本科研业务费专项基金资助项目（2016FZA6004)作者简介:沈一凡（1991一），男，在读硕士研究生，主要从事水质监测与预警技术的研究。E-mail:[e-mail]。侯迪波(通信作者），男，博士，教授，主要从事先进传感技术、智能信息处理、环境监测预警等技术的研究。E-mail:[e-mail]0•52•自动化仪表第38卷始注入，到第一次检测到有污染物注入的这段时间内，供水管网系统已经对外供出的污染水体积。Ostfeld等[5]提出了一个混合整数规划模型，以求解供水管网水质监测传感器网络布局优化问题。Berry等[6]则以受污染水影响的人口数量最少为目标，建立了一个混合整数规划模型并对其进行求解。显然，此类问题的模型应尽量避免引入主观因素，保持模型的客观正确性;同时，随着管网系统规模的日益增大，模型应能够满足不同需求下的供水管网水质监测传感器网络布局优化研究，求解算法应具备较好的时效性和存储空间利用率。为了克服基于“服务水平”概念的模型易受主观因素干扰、一般寻优算法难以满足大规模供水管网模型求解的缺点，提出了污染事件检测时间最短模型。本模型以污染事件平均检测时间最短为目标，对供水管网系统状态进行了平均化处理，并利用基于多线程机制的并行粒子群优化（particleswarmoptimization，PSO)算法优化求解问题模型，提升了模型求解的效率。1污染事件检测时间最短模型1.1假设条件管网系统本身具有较高的动态变化特性，同时污染事件具有较大的不确定性;基于突发污染物注入事件模拟的供水管网水质监测传感器网络布局优化问题，以随机污染矩阵的方式模拟污染物注入事件，未必能够将所有情况计算在内。因此，在构建模型之前，对管网系统本身作了一定的简化，主要包括以下几点。①突发污染物注入事件可在任意节点发生，且每个节点发生污染物注入事件的概率相等。同时，在本模型中，只考虑单污染源形式，即任意时刻只有一个节点发生突发污染事件。②污染物在管网中以一维平流输送的形式扩散，且污染物从一个节点扩散到另一个节点的时间等同于水流从源节点输送到目标节点的最短时间，不考虑其他因素造成的污染物在管道扩散时的衰减作用。③一旦污染物到达监测节点，监测设备能够立即提供及时的预警信息，并采取相应的措施，处理污染事故。检测设备具有尚可罪性、尚灵敏性。④因为仿真软件并不能提供有关管道的精确计算结果，所以预警监测点只能设置在管网节点处，而非管道处。可将本模型中供水管网系统视作一个由顶点集F和有向边集合E组成的图C=(F，E)。设监测节点集合为L(LeF)，对于供水管网系统内任意节点f，若^时刻在节点i处发生突发污染事故，节点eL)在时刻第一个检测到有污染事件发生，则此时污染事件检测时间为=4-^。在本模型给定的条件下，设=min(^y))(yeL)为节点；和节点y之间的最短扩散时间。节点间最短扩散时间的计算方法类似于图论算法中，有向图中任意节点之间的最短路径。在本模型中，最短路径表示水流从一个节点输送到另一个节点所需的最短扩散时间。因此，利用图论算法中经典的Floyd-Warshall算法，可快速构建整个管网系统的最短扩散时间矩阵。L2模型定义基于以上概念，建立以下污染事件检测时间最短模型：min^t\ie/(1)ns.t.工lj=Nsljj=iE|〇，l}(2)=min(^“y))jeL(3)式中为监测点数量为二进制变量，表示节点y是否被选为监测节点，若是则/；取1，若不是则/；取〇;l为监测节点集合。污染事件检测时间最短模型是一个典型的搜索问题。随着管网节点数量的增多，可选的监测点配置方案数量快速增长，普通的全局搜索算法将不能满足计算的需求，故本文采用基于多线程机制的并行PSO算法来求解模型结果。2基于多线程机制的并行PSO算法PSO算法源于对鸟群捕食行为的研究，类似于遗传算法，是一种基于迭代的寻优算法。由于该算法结构简单、过程易于理解，且算法本身的性能稳定、效率高，因而在众多优化问题模型中得到了广泛的应用[7]。基本的粒子群算法中，问题的解空间被抽象为粒子位置的集合，通过粒子的移动来模拟寻找最优解的过程。每个粒子根据自身的历史最优位置和整个群体的全局最优位置，在一定的随机扰动下决定下一步的移动方向。假设搜索的解空间维度为込粒子群体的数量为M，则可以用如下四个D维向量表示第f个粒子的信息。粒子的当前位置为：'-（％il，%i2，…)(4)粒子的历史最优位置为：Pi=(Pn,Pi2,'-,PiD)(5)粒子的速度为：第6期供水管网水质监测传感器网络布局优化沈一凡，等•53•\=(汜a，汜i2，•••，”iD)(6)整个粒子群的最优位置为：=(Ga，Ga，…，GiD)(7)粒子根据式(6)和式(7)更新速度和位置：v\Jx=wXv\.+XrandX(p^-x^)+c2xrandx(-oc^)(8)4+1=4+4(9)式中:为粒子i在第g欠迭代过程中第y维的速度，一般将粒子的速度限制在〃min与〃max之间;为粒子i在第“欠迭代中第y维的位置，为避免粒子盲目搜索不必要的空间，一般将粒子的位置限制在％_与&ax之间^为惯性权重，一般随着演化推进从大到小逐渐调整;为一个服从均勻分布的随机数;q和c2都为非负常数，这两个常数使得粒子具有自我总结和向群体内其他粒子学习的能力，使粒子本身向着自己的历史最优位置和群体全优位置靠拢，一般研究中q和c2的取值为2。在本模型中，粒子搜索的空间维度D即监测点数;粒子€位置向量A=(〜，〜，…，〜）中，％为节点编号1〜〃(节点数量）的随机排序，约束条件为不能出现相同编号，粒子位置限制在[1，〃]之间。从基本的PSO算法看，其计算过程具有典型的并行计算特征，主要体现在[8]:①单粒子个体的位置、速度、个体历