基于網絡流的機場噪聲監測點布局模型?

徐 濤 杜昱萱 呂宗磊

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

1 引言

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

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

無線傳感器網絡的節點部署問題是根據具體的需求，在一定的監測范圍內以適當的方式放置感知節點，是頗具挑戰性的NP難［3］的最優化問題。國內外已有諸多研究。節點部署問題可以分為靜態部署和動態部署。靜態部署時，節點的位置可以是確定的或隨機的。由于放置在機場的節點用來監測機場噪聲和傳遞噪聲數據，節點位置會影響覆蓋噪聲的區域和節點之間的連通性，適宜采用確定性部署方案。

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

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

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

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

2 問題提出

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

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

1）網格中放置三種類型的節點，感知節點，轉接節點和匯聚節點。感知節點監測機場噪聲事件和轉發機場噪聲數據，轉接節點只能轉發機場噪聲數據，匯聚節點可以感知機場噪聲和存儲上傳機場噪聲數據。匯聚節點位置已知，數量為M。

2）每個網格可以不放置任何節點或者同時放置三種節點中的一種。

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

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

以監測到另一個網格位置。

3 數學模型

3.1 符號定義

根據以上對問題的分析和假設，下面對機場噪聲監測點布局問題建立網絡流模型。

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

i，j 網格點標號，i，j∈{1，…，N}

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

Cij弧(u，v)的容量

s，t 網絡G的源點和匯點

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

Xi網格i處的感知節點

Yi網格i處的轉接節點

Zi網格i處的匯聚節點

CX感知節點的花費集合

CZ匯聚節點的花費集合

3.2 網絡流模型的建模過程

1）飛機噪聲事件

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

2）需覆蓋的網格點

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

3）感知節點

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

4）轉接節點

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

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

5）匯聚節點

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

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

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

圖1 把一個感知節點分裂為兩個感知節點，把感知節點的費用轉換為弧費用

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

這樣就得到了表達機場噪聲監測點布局的網絡圖，如圖2所示。

3.3 約束條件

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

圖2 機場噪聲監測點布局網絡流模型

2）每一條弧都滿足

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

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

3.4 目標函數

目標是最小化網絡流模型中的費用

費用中包含所有感知節點的費用，感知節點到轉接節點、轉接節點到轉接節點以及轉接節點到匯聚節點的距離費用和所有匯聚節點的費用。

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

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

表1 基于網絡流的機場噪聲監測點布局模型的最小費用流算法

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

5 實驗與分析

5.1 實驗

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

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

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

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

表2 輸入的實驗參數

5.2 實驗結果

圖4顯示了最大跳數分別為2，3，4時，最大流，匯聚節點的數量，轉接節點的數量，感知節點的數量。

圖4 最大跳數分別為2，3，4時的實驗結果對比圖

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

表3 最大跳數為3時的最小費用增廣路

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

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

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

6 結語

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