基于網(wǎng)絡流的機場噪聲監(jiān)測點布局模型?

徐 濤 杜昱萱 呂宗磊

（1.中國民航大學計算機科學與技術(shù)學院 天津 300300）（2.中國民航信息技術(shù)科研基地 天津 300300）

1 引言

近年來，機場的快速建設也帶來了機場噪聲問題，而且愈來愈嚴重［1］。為了了解航空器噪聲對機場周圍人群、動物和建筑物等的影響程度和范圍，對機場噪聲進行監(jiān)測必不可少。傳統(tǒng)的噪聲監(jiān)測設備受限于成本，監(jiān)測點數(shù)量較少，通常放置在重點和敏感區(qū)域，不能全面感知機場噪聲。同時，監(jiān)測點對環(huán)境要求高，一旦損壞對監(jiān)測結(jié)果影響大，且與其他的監(jiān)測系統(tǒng)連接時也有困難，可擴展性較差。

無線傳感器網(wǎng)絡（Wireless Sensor Networks，WSNs）是由部署在監(jiān)測區(qū)域內(nèi)大量傳感器節(jié)點相互通信形成的多跳自組織網(wǎng)絡系統(tǒng)，是物聯(lián)網(wǎng)底層網(wǎng)絡的重要技術(shù)形式［2］。無線傳感器網(wǎng)絡中大量節(jié)點的互聯(lián)，可以實現(xiàn)全天候、全方位的監(jiān)測機場噪聲，彌補傳統(tǒng)噪聲布點方案數(shù)量少、無法協(xié)同等不足。目前，無線傳感器網(wǎng)絡在水環(huán)境監(jiān)測、空氣質(zhì)量監(jiān)控等領域，都有成功的應用，而在機場噪聲監(jiān)測中的應用較為少見。

無線傳感器網(wǎng)絡的節(jié)點部署問題是根據(jù)具體的需求，在一定的監(jiān)測范圍內(nèi)以適當?shù)姆绞椒胖酶兄?jié)點，是頗具挑戰(zhàn)性的NP難［3］的最優(yōu)化問題。國內(nèi)外已有諸多研究。節(jié)點部署問題可以分為靜態(tài)部署和動態(tài)部署。靜態(tài)部署時，節(jié)點的位置可以是確定的或隨機的。由于放置在機場的節(jié)點用來監(jiān)測機場噪聲和傳遞噪聲數(shù)據(jù)，節(jié)點位置會影響覆蓋噪聲的區(qū)域和節(jié)點之間的連通性，適宜采用確定性部署方案。

確定性部署方案通常是用有限的資源例如節(jié)點數(shù)量滿足設定的單目標或多目標進行節(jié)點部署。大部分的研究工作集中在增加覆蓋率，提高網(wǎng)絡連通性，延長網(wǎng)絡生命時長和數(shù)據(jù)保真，以及失敗節(jié)點的容忍度，負載平衡等。盡管直覺上可以在理論上滿足所有目標，但是追求最少的資源實現(xiàn)這些目標使得問題變得很難。在過去的研究中，學者們通過建立數(shù)學模型最優(yōu)化這些目標中的一個或多個。本文考慮實現(xiàn)其中的兩個目標：1）最小化感知節(jié)點數(shù)量以減少部署節(jié)點的花費；2）最大化感知節(jié)點覆蓋的區(qū)域以監(jiān)測所有機場噪聲事件。

在求解方法上，與建立的數(shù)學模型有關(guān)。文獻［4］提出一個整數(shù)線性規(guī)劃模型（ILP），在滿足覆蓋關(guān)鍵點和監(jiān)測區(qū)域時最小化感知節(jié)點和轉(zhuǎn)接節(jié)點的開銷。整數(shù)線性規(guī)劃模型可以求出精確解，但當覆蓋區(qū)域較大時，求解復雜度隨著問題規(guī)模呈現(xiàn)指數(shù)級增長。為滿足更多目標和加快計算速度，數(shù)學模型會更復雜，通常采用智能優(yōu)化算法如粒子群（PSO），遺傳算法（GA），差分進化（EA）等解決多目標優(yōu)化問題。例如，文獻［5］建立了一個帶約束的多目標模型。約束條件是確保感知節(jié)點到匯聚節(jié)點是連通的。多目標包括最大化覆蓋區(qū)域，最小化網(wǎng)絡能量消耗，最大化網(wǎng)絡生命時長，最小化節(jié)點個數(shù)。通過把部署的節(jié)點和匯聚節(jié)點之間的連結(jié)抽象為樹結(jié)構(gòu)，使用啟發(fā)式算法中的多目標進化算法（MOEA）求解。在文獻［6］中，為了增加從無線傳感器網(wǎng)絡中提取的數(shù)據(jù)量，采取對瓶頸節(jié)點再充電的方法，盡力減少再充電節(jié)點的比例。作者提出了一個混合整數(shù)線性規(guī)劃模型，并用三種新的解法求解這個NP難問題。

感知節(jié)點監(jiān)測到的數(shù)據(jù)需要傳到匯聚節(jié)點，也有文獻把節(jié)點間的數(shù)據(jù)傳輸看作一種流，將節(jié)點部署問題類比成網(wǎng)絡流問題。例如，文獻［7］用網(wǎng)絡流模型為感知網(wǎng)絡中的路由選擇問題找到一個解。模型的主要目標是最大化網(wǎng)絡生命時長。利用節(jié)點的剩余能量和使用的傳送能量來定義鏈路的開銷。文獻［8］提出了一個基于休眠安排的交叉層組織過程，又稱為感知-休眠樹，目標是協(xié)調(diào)不同的工程問題，并提出一個方法去增加監(jiān)測覆蓋率和網(wǎng)格網(wǎng)絡的運行生命時長。為達到這個目標，建立了基于網(wǎng)絡流模型的整數(shù)規(guī)劃方程。本文中，機場噪聲分布具有時空性，需覆蓋區(qū)域較大，由于整數(shù)線性規(guī)劃模型只能求出較小范圍內(nèi)的精確解，不適用于機場場景，故選擇網(wǎng)絡流模型。

機場噪聲監(jiān)測點布局方面，研究還較少。文獻［9］提出了一種基于飛機噪聲事件的覆蓋連通集模型，并采用改進的遺傳算法優(yōu)化部署方案。但文中并未考慮感知節(jié)點到達匯聚節(jié)點經(jīng)過的跳數(shù)。如果跳數(shù)太多，傳遞噪聲數(shù)據(jù)過程中信息丟失的風險大，無法把噪聲數(shù)據(jù)完整地傳遞到匯聚節(jié)點。如果跳數(shù)太少，就需要更多的匯聚節(jié)點，匯聚節(jié)點價格較貴，增加開銷。如何確定合理的跳數(shù)，在這之間找到一個平衡點，需要多次實驗，根據(jù)節(jié)點的具體特性來確定。本文提出的基于網(wǎng)絡流的機場噪聲監(jiān)測點布局模型，可自行設定最大跳數(shù)，為節(jié)點部署提供一定的參考，有一定的實際意義。

2 問題提出

機場周邊噪聲監(jiān)測點的部署問題可看作部署一定量的節(jié)點監(jiān)測機場噪聲，即找出部署的節(jié)點的類型、數(shù)量和位置。機場噪聲主要由飛機噪聲事件組成。當把機場區(qū)域離散化為大小相等的正方形網(wǎng)格點時［10］（編號為1到N），問題即轉(zhuǎn)化為在N個網(wǎng)格位置中找出哪些位置放置哪種類型的節(jié)點問題。為了簡便，約定每個網(wǎng)格點的中心代表這個網(wǎng)格點。所在網(wǎng)格點的噪聲值LSEL大于閾值80dB［11］的地方即是需要覆蓋的區(qū)域。

于是，對模型作以下假設：

1）網(wǎng)格中放置三種類型的節(jié)點，感知節(jié)點，轉(zhuǎn)接節(jié)點和匯聚節(jié)點。感知節(jié)點監(jiān)測機場噪聲事件和轉(zhuǎn)發(fā)機場噪聲數(shù)據(jù)，轉(zhuǎn)接節(jié)點只能轉(zhuǎn)發(fā)機場噪聲數(shù)據(jù)，匯聚節(jié)點可以感知機場噪聲和存儲上傳機場噪聲數(shù)據(jù)。匯聚節(jié)點位置已知，數(shù)量為M。

2）每個網(wǎng)格可以不放置任何節(jié)點或者同時放置三種節(jié)點中的一種。

3）對于任意兩個網(wǎng)格i和 j，如果這兩個網(wǎng)格的 歐 式 距 離 d(i，j)在 通 信 半 徑 Rc內(nèi) ，即d(i，j)≤Rc，則意味著網(wǎng)格位置之間是連通的，可以傳遞數(shù)據(jù)。

4）對于任意兩個網(wǎng)格i和 j，如果這兩個網(wǎng)格之間的歐式距離 d(i，j)在感知半徑 Rs內(nèi)，即d(i，j)≤Rs則意味著在一個網(wǎng)格位置放置感知點可

以監(jiān)測到另一個網(wǎng)格位置。

3 數(shù)學模型

3.1 符號定義

根據(jù)以上對問題的分析和假設，下面對機場噪聲監(jiān)測點布局問題建立網(wǎng)絡流模型。

設 G={V，s，t，A，C，w}表示無線傳感器節(jié)點布局網(wǎng)絡，其中V代表頂點集合，A代表弧集合，C為容量集合，給每條弧(u，v)賦予一個非負實數(shù)w(u，v)，稱為弧(u，v)的費用。以下是相關(guān)符號定義：

i，j 網(wǎng)格點標號，i，j∈{1，…，N}

fuv通過弧(u，v)的流量

Cij弧(u，v)的容量

s，t 網(wǎng)絡G的源點和匯點

F 飛機噪聲事件集合，共m個

Xi網(wǎng)格i處的感知節(jié)點

Yi網(wǎng)格i處的轉(zhuǎn)接節(jié)點

Zi網(wǎng)格i處的匯聚節(jié)點

CX感知節(jié)點的花費集合

CZ匯聚節(jié)點的花費集合

3.2 網(wǎng)絡流模型的建模過程

1）飛機噪聲事件

選取m個飛機噪聲事件Fi，可表示為模型中的第一列頂點，編號為1-m。

2）需覆蓋的網(wǎng)格點

需覆蓋的網(wǎng)格點Hj表示為模型中的第二列頂點，共N個，如果噪聲事件Fi被網(wǎng)格點Hj監(jiān)測到，那么Fi和Hj之間用一條容量為N，費用為0的弧連接。

3）感知節(jié)點

感知節(jié)點 Xi為模型中的第三列頂點，共N個。如果感知節(jié)點Xj可以感知覆蓋候選位置Hi，兩節(jié)點之間距離d(i，j)小于等于感知半徑Rs那么Hi和Xj之間用一條容量為N，費用為0的弧連接。

4）轉(zhuǎn)接節(jié)點

轉(zhuǎn)接節(jié)點Yi在為模型中的第四列頂點，共N個。如果感知節(jié)點 Xi和轉(zhuǎn)接節(jié)點Yj之間的距離d(i，j)小于通信半徑 Rc，那么 Xi和Yj之間用一條容量為N，費用為d(i，j)的弧連接。

考慮到多跳網(wǎng)絡，即感知節(jié)點跳到轉(zhuǎn)接節(jié)點后，要經(jīng)過多個轉(zhuǎn)接節(jié)點才能到達匯聚節(jié)點，可再增加幾列轉(zhuǎn)接節(jié)點。比如經(jīng)過感知節(jié)點經(jīng)過三跳到達匯聚節(jié)點，那么轉(zhuǎn)接節(jié)點就是兩列。并且，把轉(zhuǎn)接節(jié)點之間的距離d(i，j)當作轉(zhuǎn)接節(jié)點之間弧的費用，不僅可以避免最大跳數(shù)多時，經(jīng)過過多的轉(zhuǎn)接節(jié)點，而且可以減少數(shù)據(jù)傳遞的開銷。

5）匯聚節(jié)點

匯聚節(jié)點 Zi為模型中的最后一列頂點，共M個(M≤N)。如果轉(zhuǎn)接節(jié)點Yi和匯聚節(jié)點Zj之間的距離小于連通半徑Rc，那么Yi和Zj之間用一條容量為N，費用為d(i，j)的弧連接。

然后，添加從源點s出發(fā)到每件噪聲事件Fi都有一條容量為1，費用為0的弧。從每個匯聚節(jié)點Zi到匯點t都有一條容量為N，費用為N的弧。

與典型的網(wǎng)絡流模型不同的是，我們的目標是最小化節(jié)點的個數(shù)，費用即是需放置的感知節(jié)點和匯聚節(jié)點個數(shù)（轉(zhuǎn)接節(jié)點功能單一，費用低，此處忽略）。通常的處理辦法是把點上的費用轉(zhuǎn)換為弧的費用。這里把一個感知節(jié)點分裂為兩個感知節(jié)點，如圖1所示，把節(jié)點的費用轉(zhuǎn)換為弧費用［12］。

圖1 把一個感知節(jié)點分裂為兩個感知節(jié)點，把感知節(jié)點的費用轉(zhuǎn)換為弧費用

然而，如果一個感知節(jié)點可以覆蓋多個監(jiān)測位置，則有多條弧連到該感知節(jié)點，于是一個感知節(jié)點的弧費用，乘以通過的流量時，費用會計算多次。為了解決這個問題，將感知節(jié)點連接的弧的費用設為與可覆蓋的候選位置數(shù)成反比記。Cov_Hi表示感知節(jié)點Xi覆蓋的候選位置數(shù)。已經(jīng)放置了匯聚節(jié)點的位置，由于匯聚節(jié)點也可監(jiān)測噪聲，感知節(jié)點的費用設為0。

這樣就得到了表達機場噪聲監(jiān)測點布局的網(wǎng)絡圖，如圖2所示。

3.3 約束條件

1）覆蓋每一個機場噪聲事件，即從源點出發(fā)的最大流等于噪聲事件的數(shù)量。

圖2 機場噪聲監(jiān)測點布局網(wǎng)絡流模型

2）每一條弧都滿足

3）除源點s和匯點t以外的其他頂點的入度等于出度：

4）對于源點s和匯點t滿足：

3.4 目標函數(shù)

目標是最小化網(wǎng)絡流模型中的費用

費用中包含所有感知節(jié)點的費用，感知節(jié)點到轉(zhuǎn)接節(jié)點、轉(zhuǎn)接節(jié)點到轉(zhuǎn)接節(jié)點以及轉(zhuǎn)接節(jié)點到匯聚節(jié)點的距離費用和所有匯聚節(jié)點的費用。

4 使用最小費用流算法求解

將感知節(jié)點對應弧的費用修改為和其覆蓋的網(wǎng)格位置數(shù)量有關(guān)后，最小費用流算法中每次會選擇費用最小的感知節(jié)點，即可覆蓋更多網(wǎng)格位置的感知節(jié)點。具體步驟見表1。

表1 基于網(wǎng)絡流的機場噪聲監(jiān)測點布局模型的最小費用流算法

運用最小費用流算法求得G中流量為最大流時的最小費用流。如果在設定的初始匯聚節(jié)點條件下，無法得到流量為M的最小費用流，查出未覆蓋的飛機噪聲事件，調(diào)整初始匯聚節(jié)點位置，易知一定存在一種初始匯聚節(jié)點放置方案，可以求得最大流M下的最小費用流。

5 實驗與分析

5.1 實驗

選取國內(nèi)某樞紐機場周邊10km*10km的區(qū)域，在INM（Integrated Noise Model）［14］軟件中輸入機場數(shù)據(jù)（包括機場的經(jīng)度、緯度、高度、溫度、跑道數(shù)據(jù)等）、機型等飛機相關(guān)數(shù)據(jù)和2014年7月3日50條地面航跡信息后，可計算得到機場各網(wǎng)格點的噪聲值LSEL。在INM中畫出的噪聲等值線圖，等值線從75dB～95dB，每條等值線相差5dB，如圖3所示。矩陣ini_FH是一個50行，10000列的矩陣，LSEL≥80的值有27559個。若某個頂點處的監(jiān)測所有航跡的噪聲值LSEL＜80，那么這個頂點一定不用覆蓋，相反，監(jiān)測到至少一條航跡的頂點可以被覆蓋。可以監(jiān)測到機場噪聲的網(wǎng)格點有4286個。

圖3 50條航跡的噪聲等值線圖，噪聲值從75dB到95dB，每條等值線相差5dB

將ini_FHij中噪聲值≥80的設為1，其他設為0后，得到FH矩陣。

為了驗證基于網(wǎng)絡流的機場噪聲監(jiān)測點布局模型的正確性并找到最少的感知點及其位置，模擬以下實驗，輸入的參數(shù)值見表2，需要覆蓋的50條航跡編號為1～50。選取機場當前的噪聲監(jiān)測點設為初始匯聚點，共20個，把它們的經(jīng)緯度轉(zhuǎn)化為網(wǎng)格編號表示如下：2514 2679 2800 2839 3077 3221 3331 3818 3903 4482 4692 4907 5125 5135 5285 6258 6285 6478 6886 7397。

表2 輸入的實驗參數(shù)

5.2 實驗結(jié)果

圖4顯示了最大跳數(shù)分別為2，3，4時，最大流，匯聚節(jié)點的數(shù)量，轉(zhuǎn)接節(jié)點的數(shù)量，感知節(jié)點的數(shù)量。

圖4 最大跳數(shù)分別為2，3，4時的實驗結(jié)果對比圖

當最大跳數(shù)為2時，即每個感知節(jié)點最多經(jīng)過2跳到達匯聚節(jié)點。用表2的算法求解，每次增加1個流，最小費用增廣路如表3所示。

表3 最大跳數(shù)為3時的最小費用增廣路

每一條最小費用增廣路中，第1個是匯點t。第2個是匯聚節(jié)點的編號，第3，4個是轉(zhuǎn)接節(jié)點，第5，6個是感知節(jié)點。匯聚節(jié)點，轉(zhuǎn)接節(jié)點和感知節(jié)點的編號都是1～10000。第7個是覆蓋航跡的網(wǎng)格位置，編號1～10000。第8個是飛機噪聲事件，編號1～50。第9個是源點s。圖5中給出了第47，48，49條最小費用增廣路的路徑，其中正方形代表可監(jiān)測到飛機噪聲事件的網(wǎng)格位置，網(wǎng)格上的數(shù)字代表飛機噪聲事件的編號，圓形代表感知節(jié)點，三角形代表轉(zhuǎn)接節(jié)點，五角星代表匯聚節(jié)點。

圖5 最大跳數(shù)為3時，第47，48，49條最小費用增廣路的路徑

由以上實驗可得如下結(jié)論：1）由初始的20個匯聚節(jié)點減少到6個，有效地減少了機場開銷。2）從飛機噪聲事件到匯聚節(jié)點經(jīng)過的節(jié)點路徑，可快速地知道哪個飛機噪聲沒有被覆蓋。最大跳數(shù)是3或4時，最大流都是49，查看是第28條航跡沒有被覆蓋，增加匯聚節(jié)點6244，即可覆蓋所有50個飛機噪聲事件。3）最大跳數(shù)較小時，有些噪聲事件不能被覆蓋，例如最大跳數(shù)為2時，最大流是48，第28條和第50條飛機噪聲事件沒有被感知節(jié)點覆蓋。4）最大跳數(shù)越多，網(wǎng)絡越復雜，需要的轉(zhuǎn)接節(jié)點數(shù)量越多。

6 結(jié)語

本文提出了一種基于網(wǎng)絡流的機場噪聲監(jiān)測點布局模型，通過把節(jié)點費用轉(zhuǎn)換為弧費用，利用最小費用流求得覆蓋所有噪聲事件的節(jié)點部署方案，不僅可覆蓋指定的飛機噪聲事件，也可確保感知節(jié)點到匯聚節(jié)點之間的連通性，并通過最小化節(jié)點數(shù)量來節(jié)省機場的費用。該模型的最大特點是可根據(jù)實際情況設定感知節(jié)點到匯聚節(jié)點的最大跳數(shù)和初始匯聚節(jié)點的位置，得到適用于不同機場的方案，簡便靈活。該模型的提出為改進機場根據(jù)經(jīng)驗部署噪聲監(jiān)測點的現(xiàn)狀有較大價值。