基于監(jiān)測環(huán)境的多目標優(yōu)化WSN部署

◆金世堯

基于監(jiān)測環(huán)境的多目標優(yōu)化WSN部署

◆金世堯

（沈陽化工大學(xué)計算機科學(xué)與技術(shù)學(xué)院 遼寧 110142）

無線傳感器網(wǎng)絡(luò)節(jié)點部署中，提高網(wǎng)絡(luò)覆蓋范圍、降低網(wǎng)絡(luò)成本、降低網(wǎng)絡(luò)等是優(yōu)化無線傳感器網(wǎng)絡(luò)的多個目標，提高無線傳感器網(wǎng)絡(luò)的服務(wù)質(zhì)量的問題成為一個多目標優(yōu)化問題。針對沈陽化工大學(xué)一個重點監(jiān)測區(qū)域進行節(jié)點部署，采用了一種全新的求解多目標優(yōu)化問題的思想——基于投影面的多目標優(yōu)化問題進化算法，與物理模型結(jié)合后，在實現(xiàn)最大化覆蓋區(qū)域的同時實現(xiàn)了最小化成本和最小化能耗。實驗是在MOEA/P平臺框架上實現(xiàn)的，證明提出的解決方案可以根據(jù)選用的硬件、應(yīng)用需求生成最佳部署。結(jié)果表明，采用MOEA/P算法進行節(jié)點部署優(yōu)化比采用MOEA/D算法在IGD指標上降低了32.88%。

無線傳感器網(wǎng)絡(luò)；節(jié)點部署；多目標優(yōu)化；投影面；覆蓋度；能耗

這項研究的背景是沈陽化工大學(xué)致本樓實驗室平均每月丟失財物案件數(shù)量由每月1起增加到每月3起，通過在致本樓走廊部署人體紅外傳感節(jié)點（以下簡稱傳感節(jié)點）來監(jiān)測外來人員活動情況。每個傳感節(jié)點由一個熱釋電模塊（HC-SR501）和一個具有WiFi功能的ESP32模塊串聯(lián)構(gòu)成。當傳感節(jié)點檢測到有人經(jīng)過時，會通過ESP32中的WiFi模塊向上一級匯聚節(jié)點發(fā)出信息[1]，信息上報后可以選擇語音警告驅(qū)逐或者通知安保人員到現(xiàn)場查看。部署傳感節(jié)點應(yīng)使其覆蓋面積盡可能大，同時節(jié)點個數(shù)和網(wǎng)絡(luò)總能耗盡可能小，如何平衡相互沖突的目標成為一個多目標優(yōu)化問題。

錢建新等人針對無線傳感網(wǎng)絡(luò)的節(jié)點部署問題，提出基于花朵授粉算法的節(jié)點部署算法，將節(jié)點部署問題轉(zhuǎn)化為多目標優(yōu)化問題，利用花朵授粉算法求解該優(yōu)化問題，降低了網(wǎng)絡(luò)能耗，提高了網(wǎng)絡(luò)生存周期[2]。王若霖針對靜態(tài)網(wǎng)絡(luò)的確定性部署，節(jié)點能量有限的動態(tài)網(wǎng)絡(luò)部署和多目標優(yōu)化的節(jié)點部署進行研究，提出了基于虛擬力的多目標粒子群算法的多目標優(yōu)化下的節(jié)點部署方法，解元素的分布更為均勻，具有很強的優(yōu)越性和可靠性[3]。金杉從傳感器層、匯聚層、網(wǎng)絡(luò)整體三個方面覆蓋優(yōu)化，分別提出了解決雙層WSNs覆蓋協(xié)調(diào)問題的方法，有效減少了匯聚節(jié)點數(shù)，提高了匯聚層結(jié)構(gòu)穩(wěn)定性，平衡了網(wǎng)絡(luò)能耗[4]。這些算法各有各的優(yōu)勢和側(cè)重，但是它們都沒有面向目標決策支持在指定方向上進行專門有效的求解。

本文采用的多目標優(yōu)化算法采用了一種全新的求解多目標優(yōu)化問題的思想——基于投影面的多目標優(yōu)化問題進化算法（MOEA/P）[5]，借鑒基于分解的多目標進化算法思想，將目標空間分成投影面和自由維，根據(jù)求解需求把投影面分解成多個投影格，并在各個投影格上求解自由維的最優(yōu)值，從而得到多目標優(yōu)化問題的最優(yōu)解。

1 問題描述

1.1 部署空間

部署區(qū)域為沈陽化工大學(xué)致本樓的一個走廊，樓層建筑平面如圖1所示，實際部署區(qū)域是一個328平方米的走廊，如圖2所示。

圖1 樓層建筑平面圖

圖2 實際部署區(qū)域圖

選擇的部署區(qū)域中可能包含不同的障礙，例如墻、地板等。無線電信號通過這些障礙物時會導(dǎo)致信號衰減或者感應(yīng)阻塞，會影響無線電信號的傳播和感應(yīng)能力。為了獲得更準確的實驗結(jié)果，首先測量信號在通過這三種障礙時引起的不同衰減值，測試結(jié)果如表1所示。

表1 障礙物衰減實際測量值

障礙物類型（k）厚度（cm）衰減值（dBm） 水泥墻2020 玻璃窗410 鐵質(zhì)卷簾門510

1.2 能耗模型

整個網(wǎng)絡(luò)能量消耗計算公式如下：

1.3 感應(yīng)模型

本文選擇埃爾夫斯概率模型[7]。

1.4 成本模型

進一步得到部署成本的計算公式為

2 MOEA/P

2.1 MOEA/P相關(guān)概念

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

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

例如在要求高覆蓋率低成本的監(jiān)控場景中，覆蓋率目標和成本目標非常重要，這兩維會被優(yōu)先設(shè)置為投影維。對于二目標優(yōu)化問題，投影面就是一條坐標軸；對于三目標優(yōu)化問題，投影維就是兩個目標構(gòu)成的一個坐標面。

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

2.2 個體編碼

例如：假設(shè)部署區(qū)域如圖3所示：

圖3 部署區(qū)域舉例

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

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

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

投影面分割算法 輸入：? k：投影面維數(shù)（前k維構(gòu)成投影面）；? ω：投影格邊長；輸出：投影格向量集PGs過程：. 設(shè)s=1/ω，為每個投影維的分段數(shù)，則在k維投影面上可平均分割g=sk個投影格。. 設(shè)置PGs為一g*k二維數(shù)組，記錄各投影格向量值. 設(shè)置tmpPGs為一維數(shù)組，記錄當前投影格向量值. 設(shè)cv為當前向量下標，初值為1. 調(diào)用回溯函數(shù)ProjectVectorBackTrack（1），計算各投影格向量。 ProjectVectorBackTrack（d）　//d表示當前向量的第d維{if （d==k+1）cv++；elsefor （i = 0；i < s；i++）PGs[cv][d] = i*ω；ProjectVectorBackTrack（d+1）；}

2.4 算法框架

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

3 實驗及討論

作為對比，預(yù)先用MOEA/D算法（迭代次數(shù)為與種群大小均設(shè)置為2000）求解本文設(shè)計的WSN部署模型，在此情況下得到的解看作為真實的Pareto前沿，通過計算與真實前沿的距離（比如GD指標和IGD指標）來評價后續(xù)實驗的優(yōu)劣。IGD主要通過計算每個在真實 Pareto前沿面上的點到算法獲取的個體集合之間的最小距離和，來評價算法的收斂性能和分布性能，值越小，算法的綜合性能包括收斂性和分布性能越好[8]；GD是從一組候選解指向最近的真實前沿上的點的歐式距離的平均，值越小，算法的收斂性越好[8]。

在2.1節(jié)MOEA/P算法介紹中，相對重要的指標被設(shè)置為投影維。第一次實驗的三個指標中，成本和覆蓋率是最受用戶所關(guān)注的，應(yīng)該被設(shè)置為投影維；投影格數(shù)量越多，解空間內(nèi)的解向量被劃分得更細致，得到的解的質(zhì)量更好，解的個數(shù)更多。從表2可以看出，當成本分段不小于覆蓋性分段時，IGD的值更小，這是因為本文選用的部署區(qū)域是328個單元格，部署節(jié)點數(shù)量的變化范圍遠小于覆蓋單元格數(shù)量的變化范圍，換句話說，部署節(jié)點數(shù)量的輕微變化都會對覆蓋單元格數(shù)量產(chǎn)生較大影響，所以對成本目標（節(jié)點數(shù)量）的分段適當大于覆蓋單元的分段會得到略好的結(jié)果。

表2 投影維分段數(shù)量不同對結(jié)果的影響

成本目標分段覆蓋率目標分段投影格數(shù)平均時間（s）（偏差）平均IGD（偏差）解的個數(shù) 22412.861（0.709）25.120（2.126）5.8 32616.479（0.517）9.487（1.233）44.4 23617.045（0.594）17.084（8.345）42 33923.481（1.069）8.468（1.546）60 431230.991（0.783）8.649（0.971）63 341230.506（0.496）7.684（0.489）61.4

第二次實驗?zāi)康氖窃谶\行時間相同時與MOEA/D、NSGAII算法結(jié)果的對比，如表3所示。由于MOEA/P算法是在限定的區(qū)域內(nèi)進化求解，MOEA/D算法是對整個解空間進化求解，NSGAII采用了非支配快速排序算法，所以運行速度要比MOEA/D和NSGAII算法要快，并且更接近最優(yōu)解集。

表3 運行時間相同時與MOEA/D、NSGAII算法比較

算法名稱（迭代次數(shù)，種群大小）平均運行時間（s）GD（偏差）IGD（偏差） MOEA/D（300，100）14.520.092（10.681）15.408（1.506） MOEA/P（110，60）14.513.225（9.164）11.595（1.201） NSGAII（300，70）14.574.891（1.696）107.156（0.259）

在監(jiān)測應(yīng)用中，一般要求覆蓋率90%以上，同時降低成本和能耗。接著設(shè)置ESP32模塊上傳數(shù)據(jù)的頻率為一分鐘上傳一次，分別采用MOEA/P算法和MOEA/D算法求解本部署模型，兩個算法的種群次數(shù)和迭代次數(shù)均設(shè)置為1000，得到能耗和節(jié)點數(shù)的關(guān)系如表4和圖4所示。實驗結(jié)果表明采用劃分求解空間并在限定空間內(nèi)求解的算法質(zhì)量比傳統(tǒng)的MOEA/D算法得到的解能耗更低。

表4 覆蓋率90%以上能耗與節(jié)點數(shù)關(guān)系

算法節(jié)點數(shù)（個）能耗（mAh） MOEA/D16112.21 17109.37 18101.25 1996.63 MOEA/P16106.21 17102.96 1891.5 1981.83

圖4 覆蓋率90%以上能耗與節(jié)點數(shù)變化曲線

最后，給出采用MOEA/P算法求解WSN節(jié)點部署問題的優(yōu)化方案，該方案部署了一個匯聚節(jié)點，13個傳感節(jié)點，覆蓋率為92.68%，整個網(wǎng)絡(luò)能耗為112mAh，部署位置如圖5所示。

圖5 計劃給出的節(jié)點部署方案

4 結(jié)束語

針對無線傳感網(wǎng)絡(luò)的節(jié)點部署問題，提出采用基于投影面的多目標優(yōu)化算法MOEA/P。首先將無線傳感器網(wǎng)絡(luò)節(jié)點部署問題轉(zhuǎn)換成多目標優(yōu)化問題，再利用MOEA/P算法搜索部署節(jié)點的最佳位置。通過部署最佳位置，提高覆蓋率，降低網(wǎng)絡(luò)能耗和成本。實驗證明，采用MOEA/P算法與節(jié)點部署相結(jié)合比MOEA/D、NSGAII算法得到的結(jié)果更好。

[1]謝永超，章若冰，嚴俊.基于HC-SR501和DS18B20的人體感應(yīng)溫控直流電機控制器的設(shè)計[J]. 電子設(shè)計工程，2020，28（03）：60-64.

[2]錢建新，施沈科，何燕，等. 基于多目標優(yōu)化的WSNs節(jié)點優(yōu)化部署算法[J]. 兵器裝備工程學(xué)報，2020，41（06）：174-177.

[3]王若霖.基于群智能算法的異構(gòu)WSN節(jié)點部署優(yōu)化研究[D]. 哈爾濱工程大學(xué)，2020.

[4]金杉. 無線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化方法研究[D]. 天津大學(xué)，2017.

[5]楊爽，陳未如.基于投影面的多目標進化算法MOEA/P [J].沈陽化工大學(xué)學(xué)報，2021.

[6]浦和鳴.基于分級結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)節(jié)能策略研究[D]. 電子科技大學(xué)，2020.

[7]Yun Z，Teng J，Yu Z，et al. Notice of Violation of IEEE Publication Principles：Connected Optimal Two-Coverage of Sensor Networks[J]. IEEE/ACM Transactions on Networking，2019：1-12.

[8]馮水鳳.基于指標的多目標優(yōu)化算法研究[D]. 廣東工業(yè)大學(xué)，2020.