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

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

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

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

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

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

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

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

0 引言

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

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

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

1 污染事件檢測時(shí)間最短模型

1.1 假設(shè)條件

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

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

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

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

④因?yàn)榉抡孳浖⒉荒芴峁┯嘘P(guān)管道的精確計(jì)算結(jié)果，所以預(yù)警監(jiān)測點(diǎn)只能設(shè)置在管網(wǎng)節(jié)點(diǎn)處，而非管道處。

1.2 模型定義

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

(1)

(2)

(3)

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

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

2 基于多線程機(jī)制的并行PSO算法

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

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

粒子的當(dāng)前位置為：

xi=(xi1,xi2,…,xiD)

(4)

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

pi=(pi1,pi2,…,piD)

(5)

粒子的速度為：

vi=(vi1,vi2,…,viD)

(6)

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

Gi=(Gi1,Gi2,…,GiD)

(7)

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

(8)

(9)

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

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

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

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

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

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

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

3 模型計(jì)算流程

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

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

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

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

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

(10)

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

(11)

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

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

圖2 最短檢測時(shí)間模型計(jì)算流程圖

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

4.1 算例介紹

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

圖3 Net3管網(wǎng)拓?fù)浣Y(jié)構(gòu)示意圖

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

4.2 計(jì)算結(jié)果分析

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

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

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

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

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

圖5 水質(zhì)檢測時(shí)間最短模型拓?fù)浣Y(jié)構(gòu)示意圖

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

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

圖6 不同線程條件下模型計(jì)算時(shí)間曲線圖

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

5 結(jié)束語

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

[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].上海理工大學(xué)學(xué)報(bào),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

國家自然科學(xué)基金資助項(xiàng)目(U1509208、61573313)、浙江省重點(diǎn)研發(fā)計(jì)劃基金資助項(xiàng)目(2015C03G2010034)、中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目(2016FZA6004)

沈一凡(1991—)，男，在讀碩士研究生，主要從事水質(zhì)監(jiān)測與預(yù)警技術(shù)的研究。E-mail:shenyf 0811@gmail.com。 侯迪波(通信作者)，男，博士，教授，主要從事先進(jìn)傳感技術(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