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

(1.沈陽(yáng)化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 沈陽(yáng) 110142；2.沈陽(yáng)化工大學(xué) 遼寧省化工過(guò)程工業(yè)智能化技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽(yáng) 110142)

0 引言

如今，無(wú)線傳感器網(wǎng)絡(luò)(WSN)在軍事、農(nóng)業(yè)、醫(yī)療衛(wèi)生、環(huán)境監(jiān)控、智能家居和照明等方面有很大的潛在應(yīng)用價(jià)值，尤其在無(wú)人監(jiān)測(cè)或環(huán)境惡劣情況下的事件監(jiān)測(cè)和事件跟蹤中顯示了很大的優(yōu)勢(shì)[1-2]。在這些應(yīng)用中，往往需要部署成千上萬(wàn)個(gè)互連節(jié)點(diǎn)用以保證服務(wù)質(zhì)量(QoS)，這種高密度情況下很難找到最佳部署位置。一般來(lái)說(shuō)，評(píng)價(jià)傳感器網(wǎng)絡(luò)質(zhì)量的指標(biāo)大都是相互沖突的，如何部署大量傳感器節(jié)點(diǎn)以滿足多個(gè)目標(biāo)的應(yīng)用需求成為一個(gè)多目標(biāo)問(wèn)題[3]。

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

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

1 問(wèn)題描述

1.1 部署空間

本文選用的部署區(qū)域?yàn)樯蜿?yáng)化工大學(xué)致本樓的一個(gè)走廊，樓層建筑平面如圖1所示，實(shí)際部署區(qū)域是一個(gè)328 m2的走廊,如圖2所示。

圖2 實(shí)際部署區(qū)域Fig.2 Actual deployment area

為了解決WSN節(jié)點(diǎn)部署優(yōu)化問(wèn)題，需要對(duì)部署空間精確建模。將部署空間劃分成邊長(zhǎng)為1 m的網(wǎng)格，其中每個(gè)單元格的質(zhì)心可以選擇部署傳感器節(jié)點(diǎn)(Sensor Node)或者匯聚節(jié)點(diǎn)(Sink Node)，也可以選擇同時(shí)部署。另外，選擇的部署區(qū)域中可能包含不同的障礙，例如墻、地板等。無(wú)線電信號(hào)通過(guò)這些障礙物時(shí)會(huì)導(dǎo)致信號(hào)衰減或者感應(yīng)阻塞，會(huì)影響無(wú)線電信號(hào)的傳播和感應(yīng)能力。

在選用的部署區(qū)域中，存在3種類型的障礙(水泥墻、玻璃窗戶和不銹鋼防盜門(mén))，為了獲得更準(zhǔn)確的實(shí)驗(yàn)結(jié)果，首先測(cè)量信號(hào)在通過(guò)這3種障礙時(shí)引起的不同衰減值，測(cè)試結(jié)果如表1所示。

表1 障礙物衰減實(shí)際測(cè)量值Tab.1 Actual measurements of obstacle attenuation

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

(1)

1.2 網(wǎng)絡(luò)感應(yīng)覆蓋

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

(2)

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

本文研究的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為星形結(jié)構(gòu)，每個(gè)傳感器在其感應(yīng)范圍內(nèi)監(jiān)測(cè)事件并且向距離最近的匯聚節(jié)點(diǎn)共享信息。為了使得出部署方案更加靈活，本文根據(jù)用戶的偏好來(lái)評(píng)估感應(yīng)覆蓋范圍。假設(shè)Pcov為用戶可以接受的感應(yīng)概率，si,j為距離單元格ci,j最近的傳感器節(jié)點(diǎn)位置，d(ci,j,si,j)為單元格ci,j到傳感器節(jié)點(diǎn)si,j的歐式距離，通過(guò)式(3)可以得出P(d(ci,j,si,j))即為ci,j被si,j感應(yīng)的概率。感應(yīng)覆蓋矩陣cov(ci,j)可以表示為：

(3)

假設(shè)部署區(qū)域是由X個(gè)單元格構(gòu)成，本文采用的感應(yīng)覆蓋率PS為：

(4)

1.3 網(wǎng)絡(luò)連通性

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

(5)

在無(wú)線電傳播過(guò)程中，假設(shè)信號(hào)發(fā)射點(diǎn)為bi′,j′,該點(diǎn)發(fā)射信號(hào)強(qiáng)度為PTX，接收點(diǎn)為ni，j,該點(diǎn)接收信號(hào)強(qiáng)度為RSSI(i,j)，發(fā)射信號(hào)強(qiáng)度與接收信號(hào)強(qiáng)度之間的關(guān)系表示為：

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

(6)

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

(7)

進(jìn)一步得到部署區(qū)域X的連通率PSK為：

(8)

在WSN中，連通性往往作為目標(biāo)之一加入算法進(jìn)行優(yōu)化，而本文將連通性作為MOEA/P算法的約束條件，因?yàn)檫B通性是保證部署方案有效性的前提條件，如果節(jié)點(diǎn)之間不連通，則感應(yīng)數(shù)據(jù)不能正常進(jìn)行傳輸，部署方案將無(wú)意義。

1.4 部署成本

WSN中需要考慮成本問(wèn)題。假設(shè)一個(gè)感應(yīng)節(jié)點(diǎn)的安裝成本和采購(gòu)成本之和為CS，一個(gè)匯聚節(jié)點(diǎn)的采購(gòu)和安裝成本為CSK，‖S‖為部署的傳感器節(jié)點(diǎn)總量，‖SK‖為部署的匯聚節(jié)點(diǎn)總量，該區(qū)域部署成本為：

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

(9)

由于在部署過(guò)程中成本是固定的，為了簡(jiǎn)化計(jì)算，假設(shè)部署感應(yīng)節(jié)點(diǎn)的成本與部署匯聚節(jié)點(diǎn)的成本相同，基于部署空間的定義，可以得出部署成本的矩陣為：

(10)

然后得到部署成本的計(jì)算公式為：

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

(11)

1.5 過(guò)度覆蓋

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

(12)

過(guò)度覆蓋率Pov是過(guò)度覆蓋單元格數(shù)量與總單元數(shù)量的比率：

(13)

但是在一些特定的應(yīng)用場(chǎng)景中，比如火山檢測(cè)，有些應(yīng)用需要用K個(gè)傳感器來(lái)覆蓋一個(gè)單元格，稱為K-覆蓋(K-cov)。通過(guò)保證K-覆蓋率，即使K-1個(gè)節(jié)點(diǎn)出現(xiàn)故障，部署空間仍然被覆蓋。K-覆蓋的矩陣可以表示為：

(14)

K-覆蓋率為：

(15)

2 MOEA/P

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

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

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

投影面P是多目標(biāo)函數(shù)集F的純子集，即P?F。一般選取前m-1維目標(biāo)作為投影面進(jìn)行算法實(shí)驗(yàn)分析，但是在WSN中，投影維的設(shè)置與應(yīng)用需求有關(guān)，重要的目標(biāo)被設(shè)置成投影維并分段，個(gè)體被進(jìn)一步分格細(xì)化，再經(jīng)過(guò)自由維篩選可以得到更優(yōu)的解。

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

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

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

本文對(duì)于給定目標(biāo)解向量F在投影面上的投影記為Fp，在自由維集上的投影記為Fd。自由維的設(shè)置同樣需要考慮部署環(huán)境。

定義3投影格：將投影面分割成一個(gè)個(gè)子面，稱為投影格(Projection Grid，PG)，用其核心點(diǎn)作為標(biāo)識(shí)向量——投影格向量(Projection Grid Vector，Vg)，下面將投影格向量簡(jiǎn)稱為投影格。Vg由組成投影面的各維度值構(gòu)成。

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

2.2 個(gè)體編碼

假設(shè)ci,j為待部署區(qū)域中的任意一個(gè)單元格，i和j分別對(duì)應(yīng)部署區(qū)域的橫坐標(biāo)和縱坐標(biāo)，單元格內(nèi)未部署節(jié)點(diǎn)用0來(lái)表示，部署傳感器節(jié)點(diǎn)用1來(lái)表示，部署匯聚節(jié)點(diǎn)用2來(lái)表示，同時(shí)部署傳感器節(jié)點(diǎn)與匯聚節(jié)點(diǎn)用3來(lái)表示，從形式上來(lái)說(shuō)，ci,j內(nèi)部署情況可能有4種：

①ci,j=<0>，單元格內(nèi)無(wú)節(jié)點(diǎn)部署；

②ci,j=<1>，單元格內(nèi)部署一個(gè)傳感器節(jié)點(diǎn)；

③ci,j=<2>，單元格內(nèi)部署一個(gè)匯聚節(jié)點(diǎn)；

④ci,j=<3>，單元格內(nèi)同時(shí)部署了一個(gè)傳感器節(jié)點(diǎn)和一個(gè)匯聚節(jié)點(diǎn)。

假設(shè)部署區(qū)域如圖4所示。

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

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

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

MOEA/P算法框架輸入:·多目標(biāo)問(wèn)題MOP;·結(jié)束條件;·DS:目標(biāo)決策空間(投影面)設(shè)定;·ω:投影格邊長(zhǎng);·ε:投影格影響半徑(容忍量);·S:初始種群大小。輸出:目標(biāo)解集OP過(guò)程:·步驟 1) 目標(biāo)空間劃分 根據(jù)DS確定MOP投影面及投影范圍,并將之分割成邊長(zhǎng)為F的多個(gè)投影格PGs; 設(shè)目標(biāo)解集OP為空?！げ襟E 2) 在每個(gè)投影格上求非ε-Pareto投影格支配解 對(duì)于PGs的每一個(gè)投影格,執(zhí)行步驟2.1^2.3: 步驟 2.1) 初始化種群 初始化長(zhǎng)度為S的種群G,構(gòu)造種群中個(gè)體并初始個(gè)體基因序列,保證所有個(gè)體滿足MOP約束條件; 對(duì)種群G每個(gè)個(gè)體進(jìn)行初始計(jì)算,得到相應(yīng)的目標(biāo)函數(shù)值。 步驟 2.2) 種群進(jìn)化: 如果滿足結(jié)束條件,轉(zhuǎn)步驟2.3; 設(shè)置新一代備選列表GenPOOL; 分別對(duì)種群G中的個(gè)體進(jìn)化操作; 計(jì)算每一個(gè)新生成個(gè)體并根據(jù)適度優(yōu)先關(guān)系并將之按序加入GenPOOL中; 令G=GenPOOL; 對(duì)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)系對(duì),從OP中刪去被支配的個(gè)體。 步驟 3) 輸出OP

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

2.4 進(jìn)化計(jì)算

由于多目標(biāo)優(yōu)化問(wèn)題最優(yōu)解在大部分空間的連續(xù)性，MOEA/P算法的進(jìn)化計(jì)算采取“計(jì)劃生育模式”：

① 按個(gè)體排序優(yōu)先次序，從1～0確定各個(gè)種群個(gè)體的選擇概率，進(jìn)入到下一代的備選列表中；

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

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

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

⑤ 所有新生成的個(gè)體都應(yīng)滿足MOP約束條件才能進(jìn)入下一代的備選列表中；

⑥ 當(dāng)一次進(jìn)化沒(méi)有得到足夠多的有效新個(gè)體時(shí)，進(jìn)化將提前結(jié)束。

2.5 算法框架

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

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

本文實(shí)驗(yàn)設(shè)備是一臺(tái)配備Intel(R) Core(TM) i7-5700U CPU，2.4 GHz處理器和12 GB內(nèi)存的電腦。將連通性作為約束條件，將成本、覆蓋率和過(guò)度覆蓋率作為MOEA/P算法的3個(gè)目標(biāo)進(jìn)行優(yōu)化。在運(yùn)行模擬部署之前，WSN決策者必須指定不同的參數(shù)，例如部署空間坐標(biāo)及其特征、節(jié)點(diǎn)類型、所使用的協(xié)議、考慮的拓?fù)浜驮O(shè)計(jì)者偏好等，這些參數(shù)被格式化為算法的初始條件。

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

在MOEA/P算法介紹中，相對(duì)重要的指標(biāo)被設(shè)置為投影維。第1次實(shí)驗(yàn)的3個(gè)指標(biāo)中，成本和覆蓋率是最受用戶所關(guān)注的，應(yīng)該被設(shè)置為投影維如表2所示。從表2可以看出，成本和覆蓋率作為投影維時(shí)解集質(zhì)量和分布性最好，證實(shí)了這一點(diǎn)，故本文在后續(xù)實(shí)驗(yàn)將成本和覆蓋率作為投影維。

表2 設(shè)置不同投影維結(jié)果對(duì)比Tab.2 Comparison of results of setting different projection dimensions

第2次實(shí)驗(yàn)同樣設(shè)置種群大小與迭代次數(shù)均為200，運(yùn)行20次取平均值，討論投影維不同分段導(dǎo)致的結(jié)果。

投影維分段數(shù)量不同對(duì)結(jié)果的影響如表3所示。從表3可以看出，投影維分段越多，投影格格數(shù)越多，解空間被劃分的越細(xì)致，越需要耗時(shí)進(jìn)化，解的質(zhì)量越好。投影格數(shù)量與IGD之間的關(guān)系如圖5所示。從圖5可以看出，當(dāng)成本分段不小于覆蓋性分段時(shí)，IGD的值更小，這是因?yàn)楸疚倪x用的部署區(qū)域是328個(gè)單元格，部署節(jié)點(diǎn)數(shù)量的變化范圍遠(yuǎn)小于覆蓋單元格數(shù)量的變化范圍，換句話說(shuō)，部署節(jié)點(diǎn)數(shù)量的輕微變化都會(huì)對(duì)覆蓋單元格數(shù)量產(chǎn)生較大影響，所以對(duì)成本目標(biāo)(節(jié)點(diǎn)數(shù)量)的分段適當(dāng)大于覆蓋單元的分段會(huì)得到略好的結(jié)果。

表3 投影維分段數(shù)量不同對(duì)結(jié)果的影響Tab.3 Impact of different number of projection dimension segments on results

圖5 投影格數(shù)量與IGD之間的關(guān)系Fig.5 Relationship between the number of projection grids and IGD

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

本次實(shí)驗(yàn)MOEA/P中算法設(shè)置成本目標(biāo)和覆蓋率目標(biāo)為投影維，均分為3段。3種算法結(jié)果均運(yùn)行20次取平均值。MOEA/P與MOEA/D，NSGAII算法比較如表4所示。從表4可以看出，在種群大小和迭代次數(shù)均為200時(shí)，MOEA/D算法執(zhí)行最快，這是因?yàn)镸OEA/D通過(guò)聚合函數(shù)直接把多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題；NSGAII相對(duì)來(lái)說(shuō)慢一些，因?yàn)镹SGAII主要是利用Pareto支配關(guān)系進(jìn)行非支配排序；MOEA/P算法執(zhí)行較慢，因?yàn)樾枰獙?duì)解空間進(jìn)行劃分。通過(guò)IGD，GD和C-METRIC指標(biāo)可以看出，MOEA/P的解更貼近真實(shí)Pareto前沿，多樣性也更好。

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

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

表5 目標(biāo)設(shè)置為投影維或約束條件結(jié)果對(duì)比Tab.5 Comparison of results with objectives set as projection dimensions or constraints

如果連通性目標(biāo)作為約束條件，在初始化種群時(shí)會(huì)生成滿足約束條件的個(gè)體，經(jīng)過(guò)交叉、變異后的新個(gè)體再經(jīng)過(guò)篩選之后才能進(jìn)入種群，這個(gè)過(guò)程比較耗時(shí)。如果采用限定求解空間的連通性目標(biāo)，初始化種群時(shí)會(huì)隨機(jī)生成個(gè)體，交叉、變異后生成的新個(gè)體進(jìn)入種群中，迭代完成后，滿足目標(biāo)設(shè)定的個(gè)體輸出，相對(duì)來(lái)說(shuō)節(jié)省時(shí)間。

在要求覆蓋性最大，節(jié)點(diǎn)全連通，成本與過(guò)度覆蓋率最小的應(yīng)用需求下，本文給出了一種部署方案，本方案采用1個(gè)sink節(jié)點(diǎn)和13個(gè)sensor節(jié)點(diǎn)；未覆蓋單元格17個(gè)，覆蓋率是94.82%；過(guò)度覆蓋11個(gè)，過(guò)度覆蓋率為3.35%，主要集中在鐵質(zhì)卷簾門(mén)附近，因?yàn)檫@個(gè)區(qū)域信號(hào)衰減比較大，需要適當(dāng)過(guò)度覆蓋來(lái)保證覆蓋范圍。節(jié)點(diǎn)位置如圖6所示。

圖6 建議的節(jié)點(diǎn)部署方案Fig.6 Proposed node deployment scheme

4 結(jié)束語(yǔ)

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