沈一凡，魏冠雄，侯迪波，黃平捷，張光新,張宏建

(浙江大學控制科學與工程學院,浙江 杭州 310027)

供水管網(wǎng)水質(zhì)監(jiān)測傳感器網(wǎng)絡(luò)布局優(yōu)化

沈一凡，魏冠雄，侯迪波，黃平捷，張光新,張宏建

(浙江大學控制科學與工程學院,浙江 杭州 310027)

為應(yīng)對突發(fā)污染物注入預(yù)防供水管網(wǎng)的問題，水質(zhì)監(jiān)測傳感器網(wǎng)絡(luò)布局優(yōu)化已越來越多地受到研究關(guān)注。針對基于“服務(wù)水平”概念的布局優(yōu)化模型易受主觀因素干擾的問題，提出了污染事件檢測時間最短模型。該模型以污染事件平均檢測時間為優(yōu)化目標，無需人為設(shè)定“服務(wù)水平”，所得布局方案監(jiān)測點數(shù)量完全由預(yù)算決定。一旦給定監(jiān)測點數(shù)量，能夠保證污染事件平均檢測時間最優(yōu)，充分保證了模型的客觀準確性。對供水管網(wǎng)系統(tǒng)狀態(tài)進行了平均化處理，提高了計算資源的空間利用率。同時，針對目前常用的模型參數(shù)尋優(yōu)算法難以滿足大規(guī)模供水管網(wǎng)模型求解的特點，提出了基于多線程機制的并行粒子群優(yōu)化(PSO)算法，從而充分發(fā)揮多核心處理器的計算能力，提高了硬件資源的利用率，加快了模型計算的速度。試驗結(jié)果表明，所提出的模型和優(yōu)化算法對實際的供水管網(wǎng)水質(zhì)監(jiān)測網(wǎng)絡(luò)布局優(yōu)化選址具有一定的參考作用。

供水管網(wǎng)； 水污染； 水質(zhì)監(jiān)測網(wǎng)絡(luò)； 并行粒子群算法； 節(jié)點優(yōu)化布局； 時間最短模型； 多線程； 拓撲結(jié)構(gòu)

0 引言

近年來，供水管網(wǎng)中突發(fā)污染物注入已成為各國政府重點防范的供水管網(wǎng)系統(tǒng)水污染來源[1-2]，造成了嚴重的危害和損失。在每個節(jié)點設(shè)置監(jiān)測儀器成本巨大，不切合實際，因此需要優(yōu)化監(jiān)測網(wǎng)絡(luò)布局。

針對此類問題，Kumar等[3-4]首先提出了“q體積服務(wù)水平”的概念。“q體積服務(wù)水平”即從污染物開始注入，到第一次檢測到有污染物注入的這段時間內(nèi)，供水管網(wǎng)系統(tǒng)已經(jīng)對外供出的污染水體積。Ostfeld等[5]提出了一個混合整數(shù)規(guī)劃模型，以求解供水管網(wǎng)水質(zhì)監(jiān)測傳感器網(wǎng)絡(luò)布局優(yōu)化問題。Berry等[6]則以受污染水影響的人口數(shù)量最少為目標，建立了一個混合整數(shù)規(guī)劃模型并對其進行求解。顯然，此類問題的模型應(yīng)盡量避免引入主觀因素，保持模型的客觀正確性；同時，隨著管網(wǎng)系統(tǒng)規(guī)模的日益增大，模型應(yīng)能夠滿足不同需求下的供水管網(wǎng)水質(zhì)監(jiān)測傳感器網(wǎng)絡(luò)布局優(yōu)化研究，求解算法應(yīng)具備較好的時效性和存儲空間利用率。

為了克服基于“服務(wù)水平”概念的模型易受主觀因素干擾、一般尋優(yōu)算法難以滿足大規(guī)模供水管網(wǎng)模型求解的缺點，提出了污染事件檢測時間最短模型。本模型以污染事件平均檢測時間最短為目標，對供水管網(wǎng)系統(tǒng)狀態(tài)進行了平均化處理，并利用基于多線程機制的并行粒子群優(yōu)化(particle swarm optimization,PSO)算法優(yōu)化求解問題模型，提升了模型求解的效率。

1 污染事件檢測時間最短模型

1.1 假設(shè)條件

管網(wǎng)系統(tǒng)本身具有較高的動態(tài)變化特性，同時污染事件具有較大的不確定性；基于突發(fā)污染物注入事件模擬的供水管網(wǎng)水質(zhì)監(jiān)測傳感器網(wǎng)絡(luò)布局優(yōu)化問題，以隨機污染矩陣的方式模擬污染物注入事件，未必能夠?qū)⑺星闆r計算在內(nèi)。因此，在構(gòu)建模型之前，對管網(wǎng)系統(tǒng)本身作了一定的簡化，主要包括以下幾點。

①突發(fā)污染物注入事件可在任意節(jié)點發(fā)生，且每個節(jié)點發(fā)生污染物注入事件的概率相等。同時，在本模型中，只考慮單污染源形式，即任意時刻只有一個節(jié)點發(fā)生突發(fā)污染事件。

②污染物在管網(wǎng)中以一維平流輸送的形式擴散，且污染物從一個節(jié)點擴散到另一個節(jié)點的時間等同于水流從源節(jié)點輸送到目標節(jié)點的最短時間，不考慮其他因素造成的污染物在管道擴散時的衰減作用。

③一旦污染物到達監(jiān)測節(jié)點，監(jiān)測設(shè)備能夠立即提供及時的預(yù)警信息，并采取相應(yīng)的措施，處理污染事故。檢測設(shè)備具有高可靠性、高靈敏性。

④因為仿真軟件并不能提供有關(guān)管道的精確計算結(jié)果，所以預(yù)警監(jiān)測點只能設(shè)置在管網(wǎng)節(jié)點處，而非管道處。

1.2 模型定義

基于以上概念，建立以下污染事件檢測時間最短模型：

(1)

(2)

(3)

式中：NS為監(jiān)測點數(shù)量；lj為二進制變量，表示節(jié)點j是否被選為監(jiān)測節(jié)點，若是則lj取1,若不是則lj取0；L為監(jiān)測節(jié)點集合。

污染事件檢測時間最短模型是一個典型的搜索問題。隨著管網(wǎng)節(jié)點數(shù)量的增多，可選的監(jiān)測點配置方案數(shù)量快速增長，普通的全局搜索算法將不能滿足計算的需求，故本文采用基于多線程機制的并行PSO算法來求解模型結(jié)果。

2 基于多線程機制的并行PSO算法

PSO算法源于對鳥群捕食行為的研究，類似于遺傳算法，是一種基于迭代的尋優(yōu)算法。由于該算法結(jié)構(gòu)簡單、過程易于理解，且算法本身的性能穩(wěn)定、效率高，因而在眾多優(yōu)化問題模型中得到了廣泛的應(yīng)用[7]。

基本的粒子群算法中，問題的解空間被抽象為粒子位置的集合，通過粒子的移動來模擬尋找最優(yōu)解的過程。每個粒子根據(jù)自身的歷史最優(yōu)位置和整個群體的全局最優(yōu)位置，在一定的隨機擾動下決定下一步的移動方向。假設(shè)搜索的解空間維度為D，粒子群體的數(shù)量為M，則可以用如下四個D維向量表示第i個粒子的信息。

粒子的當前位置為：

xi=(xi1,xi2,…,xiD)

(4)

粒子的歷史最優(yōu)位置為：

pi=(pi1,pi2,…,piD)

(5)

粒子的速度為：

vi=(vi1,vi2,…,viD)

(6)

整個粒子群的最優(yōu)位置為：

Gi=(Gi1,Gi2,…,GiD)

(7)

粒子根據(jù)式(6)和式(7)更新速度和位置：

(8)

(9)

在本模型中，粒子搜索的空間維度D即監(jiān)測點數(shù)；粒子i位置向量xi=(xi1,xi2,…,xiD)中，x為節(jié)點編號1～n(節(jié)點數(shù)量)的隨機排序，約束條件為不能出現(xiàn)相同編號，粒子位置限制在[1,n]之間。

從基本的PSO算法看，其計算過程具有典型的并行計算特征，主要體現(xiàn)在[8]：①單粒子個體的位置、速度、個體歷史最優(yōu)解等更新是并行的；②整個群體的最優(yōu)解評價是并行的；③下一代群體的產(chǎn)生是并行的。因此，基本的粒子群算法通過一個并行結(jié)構(gòu)、用串行計算的方式來實現(xiàn)。

本文在標準并行粒子群優(yōu)化算法的基礎(chǔ)上，提出一種基于Java多線程編程模型的島嶼群體并行粒子群算法。將粒子群等分為幾個小的群體，每個子群體在一個線程內(nèi)獨自進行計算和評價，以產(chǎn)生子群體的最佳粒子，并采用異步通信的方式，使子群體更新所在線程區(qū)域最優(yōu)解時同步更新全局最優(yōu)解[9-11]。

在本模型中，粒子的位置代表了監(jiān)測網(wǎng)絡(luò)節(jié)點的實際位置，在同一節(jié)點不可能設(shè)置兩套設(shè)備，因此，粒子的位置向量不應(yīng)包含重復(fù)的元素。為避免新產(chǎn)生的粒子違反上述約束條件，需要對粒子更新后的位置進行可行性判斷，一旦發(fā)現(xiàn)不滿足條件，需要局部更新產(chǎn)生粒子位置，以滿足約束條件。算法中的更新動作主要通過對重復(fù)元素進行隨機變異操作得到。同時，基本粒子群算法具有容易陷入局部最優(yōu)解而無法跳出解空間的缺陷。在本文的模型中引入遺傳算法中的變異概念，對新產(chǎn)生的粒子按一定的概率進行變異操作。

并行PSO算法求解流程如圖1所示。

圖1 并行PSO算法求解流程圖

圖1中：xi為粒子的位置;vi為粒子的當前速度;pi為粒子的歷史最優(yōu)位置;pg為全局最優(yōu)位置;f(i)為粒子的適應(yīng)度。每次粒子位置更新后，對新產(chǎn)生的連續(xù)解進行取整運算，并對產(chǎn)生的粒子進行合適性篩選。

3 模型計算流程

污染事件檢測時間最短模型的求解流程如下。

①管網(wǎng)系統(tǒng)模型構(gòu)建。采用EPANET軟件構(gòu)建管網(wǎng)系統(tǒng)模型[12]，編輯管網(wǎng)系統(tǒng)各節(jié)點、管道初始屬性；設(shè)定供水管網(wǎng)系統(tǒng)供水模式，用來描述供水管網(wǎng)系統(tǒng)的供水量周期性變化規(guī)律；完成模型導入，將可視化模型拓撲圖導出為管網(wǎng)描述文件，作為二次開發(fā)程序輸入文件。

②二次開發(fā)程序編寫?；诘谝徊綄С龅墓芫W(wǎng)描述文件、EPANET toolkit編寫二次開發(fā)程序，導出管網(wǎng)系統(tǒng)各管道長度、起始節(jié)點編號以及流量、流速時間序列數(shù)據(jù)。

③最短擴散時間矩陣構(gòu)建。基于第二步獲取數(shù)據(jù)，構(gòu)建管網(wǎng)系統(tǒng)最短擴散時間矩陣T。根據(jù)第二步獲取數(shù)據(jù)，構(gòu)建一個簡單的輔助矩陣P，P描述了平均狀態(tài)下管網(wǎng)系統(tǒng)各管道內(nèi)水流的流經(jīng)時間。

P中元素p(i,j)通過式(10)計算得到：

(10)

基于輔助矩陣P，利用圖論算法中的最短路徑算法可計算任意兩個節(jié)點之間的最短擴散時間。t(i,j)為水流從節(jié)點i擴散到節(jié)點j所需的最短時間。

(11)

④模型求解?；诘谌将@取的最短擴散時間矩陣T，利用基于多線程機制的并行PSO算法求解監(jiān)測點布局方案。

通過這四步計算，可以得到監(jiān)測節(jié)點選址的最終結(jié)果。最短檢測時間模型計算流程如圖2所示。

圖2 最短檢測時間模型計算流程圖

4 仿真試驗及結(jié)果分析

4.1 算例介紹

以EPANET軟件自帶的管網(wǎng)系統(tǒng)Net3為例，進行模型計算。Net3管網(wǎng)系統(tǒng)拓撲結(jié)構(gòu)如圖3所示。

圖3 Net3管網(wǎng)拓撲結(jié)構(gòu)示意圖

該管網(wǎng)系統(tǒng)包含主要節(jié)點97個、管道117條。其中，節(jié)點包括取水口2個、水塔3個、日常取水節(jié)點92個。該管網(wǎng)系統(tǒng)供水模式以24 h為周期，每個供水模式持續(xù)為1 h，因此該管網(wǎng)系統(tǒng)運行狀態(tài)呈以24 h為周期的周期性變化趨勢。

4.2 計算結(jié)果分析

利用第2節(jié)所述的方法，對該管網(wǎng)系統(tǒng)進行長時間水動力學模擬計算，并導出穩(wěn)定狀態(tài)下管網(wǎng)系統(tǒng)單供水周期內(nèi)管道的流速、流量時間序列數(shù)據(jù)。然后，依據(jù)第1節(jié)提出的污染事件檢測時間最短模型，編制基于Java多線程編程模型的代碼，以優(yōu)化求解不同監(jiān)測點數(shù)量下供水管網(wǎng)水質(zhì)監(jiān)測傳感器網(wǎng)絡(luò)布局結(jié)果。

不同監(jiān)測節(jié)點數(shù)目下的污染事件平均監(jiān)測時間對比如圖4所示。

圖4 不同監(jiān)測節(jié)點數(shù)目下的平均檢測時間曲線

從圖4中可以看出，當監(jiān)測節(jié)點數(shù)量為9個時，可以將整個管網(wǎng)系統(tǒng)的平均污染事件檢測時間限制在4 h之內(nèi)；且節(jié)點數(shù)量從8個增加到9個時，檢測時間明顯縮短。綜合考慮成本以及方案的有效性，認為監(jiān)測點數(shù)量設(shè)置為9較為合適。

以設(shè)置9個監(jiān)測點為例，圖5給出了污染事件水質(zhì)檢測時間最短模型的布局方案拓撲結(jié)構(gòu)。

圖5 水質(zhì)檢測時間最短模型拓撲結(jié)構(gòu)示意圖

圖5中，圓圈部分表示水質(zhì)監(jiān)測傳感網(wǎng)絡(luò)的布局節(jié)點。從圖5中也可以看出，污染事件檢測時間最短模型布局的結(jié)果一般具有較好的分散性，能夠避免節(jié)點向供水量較大的節(jié)點集中。這是因為該模型是以整個系統(tǒng)任意節(jié)點遭受污染物注入情況的平均檢測時間最短為目標，所以其優(yōu)化結(jié)果必然具有較好的分散性。

在Intel i3處理器(雙核四線程)的條件下，對比查看不同線程條件下本模型計算所需時間，結(jié)果如圖6所示。

圖6 不同線程條件下模型計算時間曲線圖

通過圖6可以看出，隨著線程數(shù)量從1個增加到4個，模型的計算速度有較為明顯的增加；而當線程數(shù)量從4個增加到5個時，受限于處理器本身的核心數(shù)量，速度提升并不明顯。從圖6也可以看出，通過多線程機制處理PSO算法可明顯加快模型求解的速度，充分發(fā)揮了計算機硬件的作用。

5 結(jié)束語

針對供水管網(wǎng)系統(tǒng)水質(zhì)監(jiān)測網(wǎng)絡(luò)布局問題，本文提出了污染事件檢測時間最短模型。該模型以污染事件平均檢測時間為優(yōu)化目標，無需人為設(shè)定“服務(wù)水平”，所得布局方案監(jiān)測點數(shù)量完全由預(yù)算決定；一旦給定監(jiān)測點數(shù)量，能夠保證污染事件平均檢測時間最優(yōu)，充分保證了模型的客觀準確性；通過對供水管網(wǎng)系統(tǒng)運行狀態(tài)平均化處理，提高了計算資源的空間利用率。同時，提出了基于多線程機制的并行PSO算法，提高了模型求解的效率。污染事件檢測時間最短模型和基于多線程機制的并行PSO算法相結(jié)合，對實際的供水管網(wǎng)水質(zhì)監(jiān)測傳感器網(wǎng)絡(luò)布局設(shè)計具有一定的參考作用。

[1] WATSON J,GREENBERG H J,HART W E.A multiple objective analysis of sensor placement optimization in water networks[C]//American Society of Mechanical Engineers,2004.

[2] COZZOLINO L,MUCHERINO C,PIANESE D,et al.Positioning,within water distribution Networks,of Monitoring stations aiming at an early detection of intentional contamination[J].Civil Engineering and Environmental Systems,2006,23(3):161-174.

[3] KUMAR A,KANSAL M L,ARORA G.Detecting accidental contaminations in municipal water networks - discussion[J].Journal of Water Resources Planning and Management-ASCE,1999,125(5):308-309.

[4] KESSLER A,OSTEFELD A,SINAI G.Detecting accidental contaminations in municipal water networks[J].Journal of Water Resources Planning and Management,1998,124(4):192-198.

[5] OSTFELD A,SALOMONS E.Optimal layout of early warning detection stations for water distribution systems security[J].Journal of Water Resources Planning and Management-ASCE,2004,130(5):377-385.

[6] BERRY J W,FLEISCHER L,HART W E,et al.Sensor placement in municipal water networks[J].Journal of Water Resources Planning and Management-ASCE,2005,131(3):237-243.

[7] JORDEHI A R.Particle Swarm optimisation for dynamic optimisation problems:a review[J].Neural Computing & Applications,2014,25(7-8):1507-1516.

[8] 黃芳，樊曉平.基于島嶼群體模型的并行粒子群優(yōu)化算法[J].控制與決策,2006,21(2):175-179,188.

[9] 馬慧民，吳勇，葉春明.車輛路徑問題的并行粒子群算法研究[J].上海理工大學學報,2007,29(5):435-439,444.

[10]王華秋，曹長修.基于模擬退火的并行粒子群優(yōu)化研究[J].控制與決策,2005,20(5):500-504.

[11]沈林成，霍霄華，牛軼峰.離散粒子群優(yōu)化算法研究現(xiàn)狀綜述[J].系統(tǒng)工程與電子技術(shù).2008,30(10):1986-1990,1994.

[12]ELIADES D G,KYRIAKOU M,POLYCARPOU M M.Sensor placement in water distribution systems using the S-PLACE Toolkit[J].Procedia Engineering,2014,70:602-611.

Optimization of the Layout of Water Quality Monitoring Sensors Network for Water Distribution Network

SHEN Yifan，WEI Guanxiong，HOU Dibo，HUANG Pingjie，ZHANG Guangxin，ZHANG Hongjian

(College of Control Science and Engineering,Zhejiang University,Hangzhou 310027,China)

To deal with the sudden pollutant injection,the optimization of layout of water quality monitoring sensors for water distribution network has been more and more concerned in research.To against the shortcoming of the layout optimization based on the concept of “service level” which is easily to be disturbed by subjective factors,the model of the shortest detection time for pollution incident is proposed. With the average detection time of the pollution incident as the optimization object,the manual setting of “service level” is unnecessary,the number of the detection points of the layout strategy provided by the model is fully determined by budget,once the number of monitoring points is given,the average detection time of the pollution incident is optimum,and the objective accuracy of the model can be guaranteed.The status of the water distribution network is averaging processed to improve the spatial utilization of calculation resources.In addition,because the commonly used optimizing algorithms of model parameters cannot satisfy the requirement for large scale water distribution network,the parallel PSO algorithm based on multi-threading mechanism is also proposed.This fully plays the capability of multi-core processor,and enhances the utilization of hardware resource and the model calculation speed.The test results indicate that the model and algorithm proposed possess certain reference significance for layout optimization of water monitoring sensors in water distribution network.

Water distribution network; Water pollution; Water quality monitoring network; Parallel PSO algorithm; Node layout optimization; Model of the shortest detection time； Multithreading; Topology structure

國家自然科學基金資助項目(U1509208、61573313)、浙江省重點研發(fā)計劃基金資助項目(2015C03G2010034)、中央高校基本科研業(yè)務(wù)費專項基金資助項目(2016FZA6004)

沈一凡(1991—)，男，在讀碩士研究生，主要從事水質(zhì)監(jiān)測與預(yù)警技術(shù)的研究。E-mail:shenyf 0811@gmail.com。 侯迪波(通信作者)，男，博士，教授，主要從事先進傳感技術(shù)、智能信息處理、環(huán)境監(jiān)測預(yù)警等技術(shù)的研究。 E-mail:houdb@zju.edu.cn。

TH81;TP23

A

10.16086/j.cnki.issn1000-0380.201706012

修改稿收到日期:2016-03-16