基于MOEA/P的無線傳感器網絡節點部署研究

劉 俊，金世堯，陳未如，彭弗楠*

(1.沈陽化工大學 計算機科學與技術學院，遼寧 沈陽 110142；2.沈陽化工大學 遼寧省化工過程工業智能化技術重點實驗室，遼寧 沈陽 110142)

0 引言

如今，無線傳感器網絡(WSN)在軍事、農業、醫療衛生、環境監控、智能家居和照明等方面有很大的潛在應用價值，尤其在無人監測或環境惡劣情況下的事件監測和事件跟蹤中顯示了很大的優勢[1-2]。在這些應用中，往往需要部署成千上萬個互連節點用以保證服務質量(QoS)，這種高密度情況下很難找到最佳部署位置。一般來說，評價傳感器網絡質量的指標大都是相互沖突的，如何部署大量傳感器節點以滿足多個目標的應用需求成為一個多目標問題[3]。

近年來，研究者提出了許多不同假設、目標和模型的WSN部署方法，其中遺傳算法(GA)被大量使用[4-5]。GA大體可以分為3類：基于Pareto支配關系的遺傳算法、基于性能指標的遺傳算法和基于分解的遺傳算法。張亮和黃郡[6]采用了模糊粒子群優化算法，優化目標為感應覆蓋率和節點數量，并且采用的感應模型貼近實際情況，取得了不錯的結果。胡堅等人[7]針對水質監測無線傳感器隨機部署網絡覆蓋率低的問題，采用了一種改進的布谷鳥搜索算法，可以適應水下部署環境，提升了傳感器節點部署優化能力。陳欣等人[8]針對無線傳感器網絡中目標節點部署能力差的問題，提出了基于生物地理學優化算法的節點部署方案。該方案能夠在網絡中找到滿足K-覆蓋和M-連通性要求的傳感器節點最佳部署位置。這些算法各有各的優勢和側重，但是它們都沒有面向目標決策支持在指定方向上進行專門有效的求解。

本文采用的多目標優化算法采用了基于投影面的多目標優化問題進化算法(MOEA/P)，借鑒基于分解的多目標進化算法思想，將目標空間分成投影面和自由維，根據求解需求把投影面分解成多個投影格，并在各個投影格上求解自由維的最優值，從而得到多目標優化問題的最優解。在本算法應用中，可以根據用戶的決策方向，有指導地選擇相應的投影格進行最優求解，既能夠保證求解的精度，又能夠保證所得解滿足用戶決策支持需求。

1 問題描述

1.1 部署空間

本文選用的部署區域為沈陽化工大學致本樓的一個走廊，樓層建筑平面如圖1所示，實際部署區域是一個328 m2的走廊,如圖2所示。

圖2 實際部署區域Fig.2 Actual deployment area

為了解決WSN節點部署優化問題，需要對部署空間精確建模。將部署空間劃分成邊長為1 m的網格，其中每個單元格的質心可以選擇部署傳感器節點(Sensor Node)或者匯聚節點(Sink Node)，也可以選擇同時部署。另外，選擇的部署區域中可能包含不同的障礙，例如墻、地板等。無線電信號通過這些障礙物時會導致信號衰減或者感應阻塞，會影響無線電信號的傳播和感應能力。

在選用的部署區域中，存在3種類型的障礙(水泥墻、玻璃窗戶和不銹鋼防盜門)，為了獲得更準確的實驗結果，首先測量信號在通過這3種障礙時引起的不同衰減值，測試結果如表1所示。

表1 障礙物衰減實際測量值Tab.1 Actual measurements of obstacle attenuation

定義障礙物為Ok，其中k為障礙物的類型。假設ci,j與ci’,j’為部署空間內的2個單元格，定義ci,j與ci’,j’質心之間連線是否存在障礙Ok的函數為：

(1)

1.2 網絡感應覆蓋

已有研究證明，實際的傳感器節點不會在每個方向上提供相同的感應能力[9]，因此二元感應模型[10-11]并不能代表傳感器的真實感應能力。在概率模型中，埃爾夫斯模型[11]考慮了傳感器的距離和硬件參數方面的感應退化，代表了更現實的感應能力。此外，埃爾夫斯模型還引入了感應不確定性，更貼近傳感器的真實感應情況。因此，本文選擇埃爾夫斯概率模型：

(2)

式中，d為事件與傳感器的距離；γ和β為傳感器硬件參數；Rmin和Rmax分別為100%感應半徑和最大感應半徑。

本文研究的網絡拓撲結構為星形結構，每個傳感器在其感應范圍內監測事件并且向距離最近的匯聚節點共享信息。為了使得出部署方案更加靈活，本文根據用戶的偏好來評估感應覆蓋范圍。假設Pcov為用戶可以接受的感應概率，si,j為距離單元格ci,j最近的傳感器節點位置，d(ci,j,si,j)為單元格ci,j到傳感器節點si,j的歐式距離，通過式(3)可以得出P(d(ci,j,si,j))即為ci,j被si,j感應的概率。感應覆蓋矩陣cov(ci,j)可以表示為：

(3)

假設部署區域是由X個單元格構成，本文采用的感應覆蓋率PS為：

(4)

1.3 網絡連通性

目前文獻中最常用的連通模型有3種：FSPL[12]，1SM[13]和MWF[14]。FSPL模型基礎的傳播模型適用于理想化環境，只考慮了光線對無線電傳播的影響；1SM則一般不考慮室內環境；而WMF考慮了因墻壁和地板穿透引起的衰減，并且易于實施。本文選擇WMF作為實驗的無線電傳播模型。假設L0為參考距離1 m處的衰減，3種類型障礙引起的衰減為a(Ok)，η為路徑損耗因子，節點ni,j與ni′,j′之間路徑損耗為：

(5)

在無線電傳播過程中，假設信號發射點為bi′,j′,該點發射信號強度為PTX，接收點為ni，j,該點接收信號強度為RSSI(i,j)，發射信號強度與接收信號強度之間的關系表示為：

RSSI(i,j)=PTX-PL(bi′,j′,ni,j)。

(6)

通過式(6)可以看出，如果單元格ni，j中計算出的RSSI(i，j)大于良好通信所需的最低信號強度Ptsh，則在對應矩陣位置取1，否則取0，可以得出連通性矩陣：

(7)

進一步得到部署區域X的連通率PSK為：

(8)

在WSN中，連通性往往作為目標之一加入算法進行優化，而本文將連通性作為MOEA/P算法的約束條件，因為連通性是保證部署方案有效性的前提條件，如果節點之間不連通，則感應數據不能正常進行傳輸，部署方案將無意義。

1.4 部署成本

WSN中需要考慮成本問題。假設一個感應節點的安裝成本和采購成本之和為CS，一個匯聚節點的采購和安裝成本為CSK，‖S‖為部署的傳感器節點總量，‖SK‖為部署的匯聚節點總量，該區域部署成本為：

CostX=CS×‖S‖+CSK×‖SK‖。

(9)

由于在部署過程中成本是固定的，為了簡化計算，假設部署感應節點的成本與部署匯聚節點的成本相同，基于部署空間的定義，可以得出部署成本的矩陣為：

(10)

然后得到部署成本的計算公式為：

CostX=∑i∑jD(i,j)。

(11)

1.5 過度覆蓋

在實際部署情況中，一個單元格可能在多個傳感器的感應覆蓋范圍內，造成覆蓋冗余，這種情況稱為過度覆蓋[15]。一般情況下，部署過程中應該盡量減少過度覆蓋的范圍，也就是使覆蓋冗余最小化，以避免能源浪費和降低部署成本。過度覆蓋矩陣可以表示為：

(12)

過度覆蓋率Pov是過度覆蓋單元格數量與總單元數量的比率：

(13)

但是在一些特定的應用場景中，比如火山檢測，有些應用需要用K個傳感器來覆蓋一個單元格，稱為K-覆蓋(K-cov)。通過保證K-覆蓋率，即使K-1個節點出現故障，部署空間仍然被覆蓋。K-覆蓋的矩陣可以表示為：

(14)

K-覆蓋率為：

(15)

2 MOEA/P

2.1 MOEA/P相關概念

為了統一計算尺度，保證在各個目標方向上的計算均衡，需要進行目標空間歸一化[16]，這是許多算法都采用的方式。本文此后討論的目標向量值都缺省設定為歸一化后的值。為了減少所得解的數量，得到有一定代表性的較小的解集。MOEA/P[17]將目標空間分解為2部分：投影面和自由維。

定義1投影面：根據目標決策需求選取部分主要目標維構成投影面(Projection Plane)，投影面上的各目標維稱為投影維(Projection Dimension)。

投影面P是多目標函數集F的純子集，即P?F。一般選取前m-1維目標作為投影面進行算法實驗分析，但是在WSN中，投影維的設置與應用需求有關，重要的目標被設置成投影維并分段，個體被進一步分格細化，再經過自由維篩選可以得到更優的解。

例如在要求高覆蓋率低成本的監控場景中，覆蓋率目標和成本目標非常重要，這兩維會被優先設置為投影維。對于二目標優化問題，投影面就是一條坐標軸；對于三目標優化問題，投影維就是2個目標構成的一個坐標面，如圖3所示。

圖3 三維目標下自由維與投影面的關系Fig.3 Relationship between free dimension and projection plane under three-dimensional objectives

定義2自由維：除投影面外的目標空間其他維稱為自由維(Free Dimension，fd)，由所有自由維所組成的集合稱為自由維集(Free Dimension Set，D)。

本文對于給定目標解向量F在投影面上的投影記為Fp，在自由維集上的投影記為Fd。自由維的設置同樣需要考慮部署環境。

定義3投影格：將投影面分割成一個個子面，稱為投影格(Projection Grid，PG)，用其核心點作為標識向量——投影格向量(Projection Grid Vector，Vg)，下面將投影格向量簡稱為投影格。Vg由組成投影面的各維度值構成。

本文實驗采用的MOEA/P算法求得落在指定投影面上的目標向量后，以該投影面所限定的目標子空間進化求解自由維最優解。為此給出如下定義和定理。

2.2 個體編碼

假設ci,j為待部署區域中的任意一個單元格，i和j分別對應部署區域的橫坐標和縱坐標，單元格內未部署節點用0來表示，部署傳感器節點用1來表示，部署匯聚節點用2來表示，同時部署傳感器節點與匯聚節點用3來表示，從形式上來說，ci,j內部署情況可能有4種：

①ci,j=<0>，單元格內無節點部署；

②ci,j=<1>，單元格內部署一個傳感器節點；

③ci,j=<2>，單元格內部署一個匯聚節點；

④ci,j=<3>，單元格內同時部署了一個傳感器節點和一個匯聚節點。

假設部署區域如圖4所示。

該部署區域的染色體表示為[0，2，3，1，0，1]。

2.3 目標空間劃分及初始化種群

目標決策空間的設定將最優化求解空間設定到了一個較小的范圍之內，可以大大縮小計算時間并提高計算精度。投影面選定之后，需要根據投影格邊長對投影面進行分割，以便進一步求解。投影格由相應的投影格標識向量所標定，對投影面進行分割就是要生成相應的投影格向量，其算法如下。

MOEA/P算法框架輸入:·多目標問題MOP;·結束條件;·DS:目標決策空間(投影面)設定;·ω:投影格邊長;·ε:投影格影響半徑(容忍量);·S:初始種群大小。輸出:目標解集OP過程:·步驟 1) 目標空間劃分 根據DS確定MOP投影面及投影范圍,并將之分割成邊長為F的多個投影格PGs; 設目標解集OP為空。·步驟 2) 在每個投影格上求非ε-Pareto投影格支配解 對于PGs的每一個投影格,執行步驟2.1^2.3: 步驟 2.1) 初始化種群 初始化長度為S的種群G,構造種群中個體并初始個體基因序列,保證所有個體滿足MOP約束條件; 對種群G每個個體進行初始計算,得到相應的目標函數值。 步驟 2.2) 種群進化: 如果滿足結束條件,轉步驟2.3; 設置新一代備選列表GenPOOL; 分別對種群G中的個體進化操作; 計算每一個新生成個體并根據適度優先關系并將之按序加入GenPOOL中; 令G=GenPOOL; 對G進行截斷操作; 重復本步驟2.2。 步驟 2.3) 提交進化結果 將G中所有非ε-Pareto投影格支配個體提交到OP,并保證不與OP中任何現有個體相互Pareto支配。若存在Pareto支配關系對,從OP中刪去被支配的個體。 步驟 3) 輸出OP

根據目標決策空間(投影面)確定多目標問題MOP投影面及投影范圍，并將之分割成邊長為F的多個投影格PGs；設目標解集OP為空。初始化長度為S的種群G，構造種群中的個體并初始個體基因序列，保證所有個體滿足MOP約束條件,本文實驗的約束條件是連通性。

2.4 進化計算

由于多目標優化問題最優解在大部分空間的連續性，MOEA/P算法的進化計算采取“計劃生育模式”：

① 按個體排序優先次序，從1～0確定各個種群個體的選擇概率，進入到下一代的備選列表中；

② 每個個體要與其他個體交叉繁殖2個后代，使這2個后代分別繼承父母的前后2段不同基因；

③ 每個個體在所有基因位(決策變量)上都有變異的機會，使得個體可以能夠有機會跳出本地局限尋求全局最優；

④ 引入一種新的變異機制——振蕩，它使得每個個體在所有基因位上都有一次機會以原基因位值為中心的上下振蕩，以逐步向最優解靠近；

⑤ 所有新生成的個體都應滿足MOP約束條件才能進入下一代的備選列表中；

⑥ 當一次進化沒有得到足夠多的有效新個體時，進化將提前結束。

2.5 算法框架

投影維設置方案平均運行時間/s(偏差)平均IGD(偏差)平均出現解的個數設置成本和過度覆蓋率為投影維110.624(6.368)9.807(2.348)28.5設置成本和覆蓋率為投影維116.666(2.866)9.652(1.658)32.1設置覆蓋率和過度覆蓋率為投影維153.653(8.823)28.957(4.06)6.42

3 實驗與討論

本文實驗設備是一臺配備Intel(R) Core(TM) i7-5700U CPU，2.4 GHz處理器和12 GB內存的電腦。將連通性作為約束條件，將成本、覆蓋率和過度覆蓋率作為MOEA/P算法的3個目標進行優化。在運行模擬部署之前，WSN決策者必須指定不同的參數，例如部署空間坐標及其特征、節點類型、所使用的協議、考慮的拓撲和設計者偏好等，這些參數被格式化為算法的初始條件。

本文實驗區域選擇的是一塊328 m2的區域，采用的感知模型是埃爾弗斯概率模型，γ設置為0.1，β設置為2.2。無線電傳播模型選擇修正后的WMF模型，為了匹配實際測量值，η設置為1.7。一般部署目標是實現成本最小、覆蓋率最大，在此需求下，第1次實驗將任意2個目標作為投影維且均分為3段，這樣投影格數量固定在9個，種群大小和迭代次數均設置成200，運行20次取均值對比討論投影維與自由維最佳設定。作為對比，事先將本文提出的模型用MOEA/D算法執行20次(種群大小與迭代次數設置為2 000)，選出最好的一組解作為Pareto前沿計算反向迭代距離(IGD)來比較好壞。

在MOEA/P算法介紹中，相對重要的指標被設置為投影維。第1次實驗的3個指標中，成本和覆蓋率是最受用戶所關注的，應該被設置為投影維如表2所示。從表2可以看出，成本和覆蓋率作為投影維時解集質量和分布性最好，證實了這一點，故本文在后續實驗將成本和覆蓋率作為投影維。

表2 設置不同投影維結果對比Tab.2 Comparison of results of setting different projection dimensions

第2次實驗同樣設置種群大小與迭代次數均為200，運行20次取平均值，討論投影維不同分段導致的結果。

投影維分段數量不同對結果的影響如表3所示。從表3可以看出，投影維分段越多，投影格格數越多，解空間被劃分的越細致，越需要耗時進化，解的質量越好。投影格數量與IGD之間的關系如圖5所示。從圖5可以看出，當成本分段不小于覆蓋性分段時，IGD的值更小，這是因為本文選用的部署區域是328個單元格，部署節點數量的變化范圍遠小于覆蓋單元格數量的變化范圍，換句話說，部署節點數量的輕微變化都會對覆蓋單元格數量產生較大影響，所以對成本目標(節點數量)的分段適當大于覆蓋單元的分段會得到略好的結果。

表3 投影維分段數量不同對結果的影響Tab.3 Impact of different number of projection dimension segments on results

圖5 投影格數量與IGD之間的關系Fig.5 Relationship between the number of projection grids and IGD

第3次實驗討論在同樣部署區域、同樣優化模型中MOEA/P與MOEA/D，NSGAII的比較結果。首先把MOEA/P迭代次數與種群大小均設置成2 000，投影維設置為成本和覆蓋性，均分為10段，即100投影格，運行20次取最好的一組解作為真實Pareto前沿，通過Pareto前沿計算IGD和GD。另外使用了C-METRIC指標來評價在相同迭代次數和種群大小情況下算法的好壞。IGD主要通過計算每個在真實Pareto前沿面上的點到算法獲取的個體集合之間的最小距離和，來評價算法的收斂性能和分布性能，值越小，算法的綜合性能包括收斂性和分布性能越好[18]；GD是從一組候選解指向最近的真實前沿上的點的歐式距離的平均，值越小，算法的收斂性越好[18]；C-METRIC為解集覆蓋率，C(A_B)表示B中被A中至少一個解支配的解的百分比[19]。

本次實驗MOEA/P中算法設置成本目標和覆蓋率目標為投影維，均分為3段。3種算法結果均運行20次取平均值。MOEA/P與MOEA/D，NSGAII算法比較如表4所示。從表4可以看出，在種群大小和迭代次數均為200時，MOEA/D算法執行最快，這是因為MOEA/D通過聚合函數直接把多目標優化問題轉化為單目標問題；NSGAII相對來說慢一些，因為NSGAII主要是利用Pareto支配關系進行非支配排序；MOEA/P算法執行較慢，因為需要對解空間進行劃分。通過IGD，GD和C-METRIC指標可以看出，MOEA/P的解更貼近真實Pareto前沿，多樣性也更好。

表4 MOEA/P與MOEA/D，NSGAII算法比較Tab.4 Comparison of MOEA/P,MOEA/D and NSGAII algorithms

MOEA/P算法支持限定求解空間，第4次實驗討論設置限定空間的目標與目標作為約束條件二者的優劣。以連通性為例，分別將連通性作為目標、約束及同時作為目標和約束3種模型均在種群大小和迭代次數為200的情況下運行，與Pareto前沿進行IGD與GD的計算，結果如表5所示。

表5 目標設置為投影維或約束條件結果對比Tab.5 Comparison of results with objectives set as projection dimensions or constraints

如果連通性目標作為約束條件，在初始化種群時會生成滿足約束條件的個體，經過交叉、變異后的新個體再經過篩選之后才能進入種群，這個過程比較耗時。如果采用限定求解空間的連通性目標，初始化種群時會隨機生成個體，交叉、變異后生成的新個體進入種群中，迭代完成后，滿足目標設定的個體輸出，相對來說節省時間。

在要求覆蓋性最大，節點全連通，成本與過度覆蓋率最小的應用需求下，本文給出了一種部署方案，本方案采用1個sink節點和13個sensor節點；未覆蓋單元格17個，覆蓋率是94.82%；過度覆蓋11個，過度覆蓋率為3.35%，主要集中在鐵質卷簾門附近，因為這個區域信號衰減比較大，需要適當過度覆蓋來保證覆蓋范圍。節點位置如圖6所示。

圖6 建議的節點部署方案Fig.6 Proposed node deployment scheme

4 結束語

本文提出了一種解決WSN部署問題的新方法。首先將該問題建模為單約束三目標優化問題，在MOEA/P框架內，目標包括確定無線節點的最佳位置并確保優化傳感覆蓋范圍、連通性、過度覆蓋和成本，接著對已有文獻采用的方法進行分析和物理模型的改進，最后通過實驗來確定投影維的設置和其他參數。這種優化方法可以根據環境、不同應用程序的規范和用戶首選項生成最佳部署，根據對多組測試數據進行各種實驗對這些模擬進行的分析證實了所提出的方法的可行性和有效性。下一步的工作是引入能耗或者生存周期等指標，利用MOEA/P算法解決三維空間內的節點部署問題。