◆金世堯

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

◆金世堯

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

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

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

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

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

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

1 問題描述

1.1 部署空間

部署區(qū)域?yàn)樯蜿柣ご髮W(xué)致本樓的一個(gè)走廊，樓層建筑平面如圖1所示，實(shí)際部署區(qū)域是一個(gè)328平方米的走廊，如圖2所示。

圖1 樓層建筑平面圖

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

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

表1 障礙物衰減實(shí)際測量值

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

1.2 能耗模型

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

1.3 感應(yīng)模型

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

1.4 成本模型

進(jìn)一步得到部署成本的計(jì)算公式為

2 MOEA/P

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

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

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

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

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

2.2 個(gè)體編碼

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

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

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

2.3 目標(biāo)空間劃分及初始化種群

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

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

2.4 算法框架

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

3 實(shí)驗(yàn)及討論

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

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

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

成本目標(biāo)分段覆蓋率目標(biāo)分段投影格數(shù)平均時(shí)間（s）（偏差）平均IGD（偏差）解的個(gè)數(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

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

表3 運(yùn)行時(shí)間相同時(shí)與MOEA/D、NSGAII算法比較

算法名稱（迭代次數(shù)，種群大?。┢骄\(yùn)行時(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í)降低成本和能耗。接著設(shè)置ESP32模塊上傳數(shù)據(jù)的頻率為一分鐘上傳一次，分別采用MOEA/P算法和MOEA/D算法求解本部署模型，兩個(gè)算法的種群次數(shù)和迭代次數(shù)均設(shè)置為1000，得到能耗和節(jié)點(diǎn)數(shù)的關(guān)系如表4和圖4所示。實(shí)驗(yàn)結(jié)果表明采用劃分求解空間并在限定空間內(nèi)求解的算法質(zhì)量比傳統(tǒng)的MOEA/D算法得到的解能耗更低。

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

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

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

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

圖5 計(jì)劃給出的節(jié)點(diǎn)部署方案

4 結(jié)束語

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

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

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

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

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

[5]楊爽，陳未如.基于投影面的多目標(biāo)進(jìn)化算法MOEA/P [J].沈陽化工大學(xué)學(xué)報(bào)，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]馮水鳳.基于指標(biāo)的多目標(biāo)優(yōu)化算法研究[D]. 廣東工業(yè)大學(xué)，2020.