基于移動(dòng)傳感器的大規(guī)模復(fù)雜供水管網(wǎng)監(jiān)測(cè)研究進(jìn)展?

薛學(xué)月 梁俊斌 蔣 嬋

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室 南寧 530004）

1 引言

供水管網(wǎng)（簡(jiǎn)稱管網(wǎng)）是一種影響國民經(jīng)濟(jì)和社會(huì)生活的重要基礎(chǔ)設(shè)施。在2017年，中國98.3%的城市人口依靠管網(wǎng)獲取清潔用水。然而，管網(wǎng)中泄漏和污染等異常事件頻頻發(fā)生，造成了嚴(yán)重?fù)p失。其中，由于管道破損，全國每年泄漏了10%的供水量。此外，由于污染物從破損處入侵，飲用水污染和人員中毒事件時(shí)有發(fā)生。

過往研究表明，采用移動(dòng)傳感器對(duì)管網(wǎng)進(jìn)行監(jiān)測(cè)可以有效降低異常事件造成的損失［1］。雖然管網(wǎng)深埋地下、分布遼闊、結(jié)構(gòu)復(fù)雜等特性不利于異常事件的發(fā)現(xiàn)。但是移動(dòng)傳感器可以被投入管網(wǎng)，隨水流到達(dá)各條管道，獲取數(shù)據(jù)，實(shí)現(xiàn)全面且精確的管網(wǎng)監(jiān)測(cè)［2］。

然而，移動(dòng)傳感器監(jiān)測(cè)管網(wǎng)研究尚處于起步階段，面臨著諸多挑戰(zhàn)：管網(wǎng)內(nèi)水流（流速、流量、方向等）復(fù)雜，刻畫傳感器移動(dòng)軌跡困難；管網(wǎng)規(guī)模龐大、目標(biāo)函數(shù)復(fù)雜，求取部署方案困難。眾多學(xué)者針對(duì)這些問題展開研究，并取得一定成果。按照相關(guān)研究和管網(wǎng)對(duì)應(yīng)關(guān)系（圖1），本文分類總結(jié)相關(guān)工作，分析各自優(yōu)缺點(diǎn)，并展望未來研究方向。

圖1 相關(guān)研究和管網(wǎng)的對(duì)應(yīng)關(guān)系

圖2 墻內(nèi)供水管網(wǎng)

2 管網(wǎng)結(jié)構(gòu)探測(cè)

獲取管網(wǎng)的連接結(jié)構(gòu)信息是管網(wǎng)監(jiān)測(cè)的必要基礎(chǔ)。然而，位于房屋墻體內(nèi)部的管網(wǎng)結(jié)構(gòu)圖紙（圖2）卻常有丟失，對(duì)管網(wǎng)監(jiān)測(cè)形成極大阻礙。針對(duì)該問題，文獻(xiàn)［3～5］逐步完善了利用移動(dòng)傳感器獲取墻體內(nèi)供水管網(wǎng)結(jié)構(gòu)的方案。

2.1 管網(wǎng)的完整覆蓋

文獻(xiàn)［3］提出通過多次重復(fù)投入單個(gè)移動(dòng)傳感器獲取管網(wǎng)結(jié)構(gòu)的方案。該方案共分三步：1）打開一個(gè)樓內(nèi)管網(wǎng)的出水口，形成穩(wěn)定水流通路。2）將移動(dòng)傳感器從入口處投入管網(wǎng)，在隨水流移動(dòng)過程中獲取管網(wǎng)結(jié)構(gòu)數(shù)據(jù)，并在離開管網(wǎng)后上傳這些數(shù)據(jù)。3）打開其他樓內(nèi)管網(wǎng)的出水口，重復(fù)投入移動(dòng)傳感器，直到獲取足夠管網(wǎng)信息。該方案雖然能推測(cè)管網(wǎng)結(jié)構(gòu)，但因缺乏量化處理數(shù)據(jù)方法，具有較大的誤差。

2.2 簡(jiǎn)單類型管道數(shù)據(jù)處理

文獻(xiàn)［4］進(jìn)一步給出了精確獲取管網(wǎng)結(jié)構(gòu)的方案。為了簡(jiǎn)化處理，該方案限制了管道類型：1）管道管徑統(tǒng)一不變。2）只有垂直于地面的垂直管道、平行于地面的水平管道等兩種管道。在此基礎(chǔ)上，通過加速度傳感部件、水壓傳感部件、陀螺儀等獲取管網(wǎng)結(jié)構(gòu)。

1）垂直管道長(zhǎng)度。若移動(dòng)傳感器在垂直管道中，則水壓讀數(shù)變化，加速度和陀螺儀讀數(shù)穩(wěn)定。取水壓變化?Presure，水密度ρ，重力加度g ，那么垂直管道長(zhǎng)度為：

2）水平管道長(zhǎng)度。若移動(dòng)傳感器在水平管道中，則水壓、加速度、陀螺儀讀數(shù)都相對(duì)穩(wěn)定。取持續(xù)時(shí)間t，移動(dòng)傳感器移動(dòng)速度為水流流速Speed，則水平管道長(zhǎng)度為

3）水平管道角度。陀螺儀的讀數(shù)可以記錄水平管道中移動(dòng)傳感器的運(yùn)動(dòng)方向，該方向即為水平管道的角度。額外說明的是，由于垂直管道角度固定，并不需要獲取。

4）管道連接點(diǎn)三維坐標(biāo)。假設(shè)每個(gè)樓層內(nèi)有一條跨樓層的垂直管道和m 條水平管道，取第i 條水平管道的長(zhǎng)度，水平偏轉(zhuǎn)角度θi，垂直管道的長(zhǎng)度Lengthver。通過累計(jì)各條管道，即可以計(jì)算每個(gè)樓層內(nèi)的管道連接點(diǎn)三維坐標(biāo)：

該方案給出了精確獲取管網(wǎng)結(jié)構(gòu)的方法，但其應(yīng)用范圍也因管道類型簡(jiǎn)單而被限制。

2.3 復(fù)雜類型管道數(shù)據(jù)處理

文獻(xiàn)［5］擴(kuò)展了管道的類型：1）由多種管徑的標(biāo)準(zhǔn)PVC管道組成的水平組合管道；2）與水平面呈45°交叉的45°垂直管道。在此基礎(chǔ)上，文獻(xiàn)給出了各自處理過程。

1）水平組合管道。若移動(dòng)傳感器在水平組合管道中，則水壓和陀螺儀讀數(shù)基本穩(wěn)定，而加速度出現(xiàn)突變。取標(biāo)準(zhǔn)PVC管道截面Ai，水流流量S，則對(duì)應(yīng)管段內(nèi)水流流速為

當(dāng)移動(dòng)傳感器在不同wi的管段間移動(dòng)時(shí)，形成不同的加速度突變峰值，以此對(duì)比加速度數(shù)據(jù)，可以推測(cè)出各階段的流速wi和對(duì)應(yīng)時(shí)間ti。由此，水平組合管道長(zhǎng)度為

2）45°垂直管道。若移動(dòng)傳感器在45°垂直管道中，其水壓讀數(shù)緩慢變化，陀螺儀和加速度讀數(shù)基本穩(wěn)定，其管道長(zhǎng)度為

該方案的管道類型依然有限，仍有其局限性。

3 移動(dòng)傳感器移動(dòng)建模

刻畫傳感器的移動(dòng)軌跡是基于移動(dòng)傳感器的供水管網(wǎng)監(jiān)測(cè)的關(guān)鍵，而影響所刻畫軌跡的主要因素有管網(wǎng)結(jié)構(gòu)和水流、移動(dòng)傳感器在管道連接點(diǎn)處選擇下游管道的模型。

3.1 管網(wǎng)結(jié)構(gòu)和水流

管網(wǎng)結(jié)構(gòu)通常被建模為加權(quán)有向圖G（V，E）。其中，V=｛vi｝表示管道連接點(diǎn)的集合，vi表示編號(hào)i的連接點(diǎn)；E=｛ei，j｝表示管道的集合，ei，j表示從連接點(diǎn)vi通向連接點(diǎn)vj的管道。

現(xiàn)有研究通常采用兩種水流模型：靜態(tài)水流模型和動(dòng)態(tài)水流模型。前者指管網(wǎng)內(nèi)水流流速、流量等性質(zhì)不隨時(shí)間改變，僅適用于用戶用水量穩(wěn)定的場(chǎng)景。而后者的水流隨時(shí)間改變，適用情況更為廣泛。此外，現(xiàn)有研究大多采用Micropolis［6］和EPA?NET［7］等模擬軟件獲取管網(wǎng)結(jié)構(gòu)和水流數(shù)據(jù)。

3.2 連接點(diǎn)選擇模型

現(xiàn)有研究通常采用兩種模型刻畫移動(dòng)傳感器在連接點(diǎn)處選擇進(jìn)入下游管道的方式。

1）最大流量選擇模型。文獻(xiàn)［7～9］采用了該模型，認(rèn)為移動(dòng)傳感器將進(jìn)入擁有最大水流流量的下游支路管道。實(shí)際中，移動(dòng)傳感器可能進(jìn)入不同管道，與該模型有所偏差。

2）概率選擇模型。為了刻畫移動(dòng)傳感器隨機(jī)選擇下游支路管道的實(shí)際情況，文獻(xiàn)［10～13］采用了概率選擇模型。該模型認(rèn)為移動(dòng)傳感器將按概率選擇進(jìn)入不同的下游管道。取vi作為起始點(diǎn)的下游管道集合D（vi），管道ei，j對(duì)應(yīng)權(quán)值ri，j，則選擇下游支路管道的概率為

一般而言，權(quán)值ri，j被設(shè)為管道內(nèi)的水流流量［10～11］或者水流流速［12～13］。相對(duì)而言，概率選擇模型與實(shí)際情況更為接近，因此被大多數(shù)研究所采用。

3.3 移動(dòng)傳感器移動(dòng)軌跡模型

對(duì)于移動(dòng)傳感器的完整移動(dòng)軌跡，現(xiàn)有研究主要采用兩種模型來刻畫：1）概率矩陣移動(dòng)模型，記錄在連接點(diǎn)間移動(dòng)概率。2）拉格朗日移動(dòng)模型，記錄有序的連接點(diǎn)集合。

1）概率矩陣移動(dòng)模型。文獻(xiàn)［14～15］采用概率矩陣描述移動(dòng)傳感器在管網(wǎng)中任意兩個(gè)連接點(diǎn)之間移動(dòng)的概率。移動(dòng)概率選擇模型可以用如下公式描述：

其中，M=｛mi，j｝，mi，j表示在連接點(diǎn)vi處移動(dòng)傳感器到達(dá)連接點(diǎn)vj的概率；I 為單位矩陣，P=｛pi，j｝，pi，j指在連接點(diǎn)vi處的移動(dòng)傳感器進(jìn)入管道ei，j的概率；|V|中為管道中連接點(diǎn)數(shù)量?；谠撃Ｐ?，相關(guān)研究證明了有限成本下，采用移動(dòng)傳感器覆蓋管網(wǎng)是NP-難問題，具有次模函數(shù)特性［14］等性質(zhì)。但是，該模型僅適用于具有靜態(tài)水流的管網(wǎng)監(jiān)測(cè)。

2）拉格朗日移動(dòng)模型。為了能夠監(jiān)測(cè)動(dòng)態(tài)水流管網(wǎng)，文獻(xiàn)［16～17］采用了有序連接點(diǎn)集合的方式描述移動(dòng)傳感器的移動(dòng)軌跡，即拉格朗日移動(dòng)模型。該模型以如下算法描述：

算法1拉格朗日模型算法

輸入：vi，time，t，maxt

輸出：Path

Path=｛＜vi，time>｝，T=time

WHILE T＜maxt&&D（T，vi）≠?

vj=連接點(diǎn)選擇模型確定的進(jìn)入管道的另一端點(diǎn)

IF 移動(dòng)傳感器未離開管道ei，j

T=T+t；調(diào)用水力模擬程序，并更新移動(dòng)傳感器位置

ELSE

T=移動(dòng)傳感器離開時(shí)刻；vj=離開端點(diǎn)；Path=Path∪｛＜vj，T>｝；vi=vj

END

END

RETURN Path

該算法的輸入是：移動(dòng)傳感器投入的位置vi，投入的時(shí)刻time，算法更新時(shí)間步長(zhǎng)t，結(jié)束算法條件的時(shí)間限制maxt。而輸出是移動(dòng)傳感器經(jīng)過各個(gè)連接點(diǎn)和時(shí)刻的集合Path。其中，D（T，vi）表示T時(shí)刻下vi的下游支路管道集合。該模型適用范圍更寬泛、更靈活。但是，它的計(jì)算負(fù)擔(dān)較大，并且只能給出具體的移動(dòng)軌跡，而非期望概率，具有不穩(wěn)定性。

4 移動(dòng)傳感器投放變量?jī)?yōu)化

管網(wǎng)呈現(xiàn)網(wǎng)狀結(jié)構(gòu)，并不能被移動(dòng)傳感器的單條移動(dòng)軌跡所覆蓋。因此，現(xiàn)有研究大多采用多個(gè)移動(dòng)傳感器一起投入管網(wǎng)進(jìn)行監(jiān)測(cè)。為此，需要設(shè)計(jì)一定評(píng)價(jià)指標(biāo)，與優(yōu)化部署算法來決定如何協(xié)調(diào)部署這些移動(dòng)傳感器。

4.1 決策變量評(píng)價(jià)指標(biāo)

現(xiàn)有評(píng)價(jià)指標(biāo)有兩類：針對(duì)異常事件的樣本類指標(biāo)、針對(duì)監(jiān)測(cè)系統(tǒng)的系統(tǒng)類指標(biāo)。

1）樣本類評(píng)價(jià)指標(biāo)。該類研究會(huì)先隨機(jī)生成一組異常事件樣本，并為每個(gè)樣本設(shè)定對(duì)應(yīng)的發(fā)生概率。隨后，對(duì)每個(gè)異常事件樣本下的決策變量表現(xiàn)加權(quán)求和。這類指標(biāo)有異常事件發(fā)現(xiàn)概率［7］、期望監(jiān)測(cè)延遲［8～9］、異常事件期望影響人口［10～11］等等。這些評(píng)價(jià)標(biāo)準(zhǔn)的表現(xiàn)取決于所用異常事件樣本組，樣本組的代表性對(duì)評(píng)價(jià)結(jié)果具有很強(qiáng)的影響。

2）系統(tǒng)類評(píng)價(jià)指標(biāo)。此類指標(biāo)以監(jiān)測(cè)成本、被監(jiān)測(cè)覆蓋的管網(wǎng)區(qū)域?yàn)榛A(chǔ)。這類指標(biāo)有期望監(jiān)測(cè)覆蓋［6，18］、期望監(jiān)測(cè)覆蓋人口［14］、移動(dòng)傳感器數(shù)量［6，19］。這些評(píng)價(jià)指標(biāo)實(shí)際上假定了異常事件在管網(wǎng)各處發(fā)生的概率是一致的。然而，這個(gè)假設(shè)并不是總能成立，在一些情況下，這些評(píng)價(jià)標(biāo)準(zhǔn)并不適用。

4.2 決策變量?jī)?yōu)化策略

通過結(jié)合評(píng)價(jià)指標(biāo)，相關(guān)研究采用一定的優(yōu)化更新決策變量策略以獲取最終算法解。目前，相關(guān)研究主要采用的更新優(yōu)化算法有貪婪算法和遺傳算法。

1）貪婪算法。貪婪算法［13，20］將移動(dòng)傳感器的投入決策視為決策集合。通過遍歷單個(gè)移動(dòng)傳感器所有可能的投入位置，每次確定一個(gè)移動(dòng)傳感器的最佳投入決策，從而逐步獲得所有移動(dòng)傳感器的部署決策。該類算法相對(duì)簡(jiǎn)潔，但由于難以遍歷所有時(shí)間，貪婪算法僅應(yīng)用于靜態(tài)水流監(jiān)測(cè)。

2）遺傳算法。在動(dòng)態(tài)水流管網(wǎng)監(jiān)測(cè)中，為了搜索最優(yōu)移動(dòng)傳感器投入時(shí)間，相關(guān)工作采用遺傳算法［18，21］加以解決。該類算法將移動(dòng)傳感器的投入位置和投入時(shí)間作為決策變量，通過變異、交叉、選擇等操作逐步確定最優(yōu)的移動(dòng)傳感器部署決策。然而，該類算法通常收斂緩慢，需要較長(zhǎng)的計(jì)算時(shí)間。

5 結(jié)語

基于移動(dòng)傳感器的供水管網(wǎng)監(jiān)測(cè)不但有著獨(dú)特的應(yīng)用價(jià)值，也面臨著一定的困難挑戰(zhàn)。近幾年，相關(guān)工作在管網(wǎng)結(jié)構(gòu)探測(cè)、移動(dòng)傳感器移動(dòng)建模、移動(dòng)傳感器投放決策變量的選擇等方面取得了一定成果。但于此同時(shí)，優(yōu)化計(jì)算困難、管網(wǎng)水流情況多變等問題依然困擾該領(lǐng)域的研究。

未來該領(lǐng)域的研究方向可能集中在以下幾個(gè)方面：1）建立具有隨機(jī)特性的移動(dòng)軌跡模型。現(xiàn)有研究的水流模型不包含隨機(jī)特性，與實(shí)際情況不符，導(dǎo)致所刻畫傳感器移動(dòng)軌跡不精確。2）允許移動(dòng)傳感器間通信。雖然允許移動(dòng)傳感器之間通信有助于管網(wǎng)監(jiān)測(cè)，但由于無法量化傳感器間通信對(duì)監(jiān)測(cè)結(jié)果的影響，現(xiàn)有監(jiān)測(cè)方案都不考慮這點(diǎn)。3）部署算法并行化。現(xiàn)有部署算法都面臨著計(jì)算量龐大的問題，可以考慮并行化加速計(jì)算。