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

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

0 引言

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

近年來，研究者提出了許多不同假設(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)模型貼近實際情況，取得了不錯的結(jié)果。胡堅等人[7]針對水質(zhì)監(jiān)測無線傳感器隨機(jī)部署網(wǎng)絡(luò)覆蓋率低的問題，采用了一種改進(jìn)的布谷鳥搜索算法，可以適應(yīng)水下部署環(huán)境，提升了傳感器節(jié)點(diǎn)部署優(yōu)化能力。陳欣等人[8]針對無線傳感器網(wǎng)絡(luò)中目標(biāo)節(jié)點(diǎn)部署能力差的問題，提出了基于生物地理學(xué)優(yōu)化算法的節(jié)點(diǎn)部署方案。該方案能夠在網(wǎng)絡(luò)中找到滿足K-覆蓋和M-連通性要求的傳感器節(jié)點(diǎn)最佳部署位置。這些算法各有各的優(yōu)勢和側(cè)重，但是它們都沒有面向目標(biāo)決策支持在指定方向上進(jìn)行專門有效的求解。

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

1 問題描述

1.1 部署空間

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

(4)

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

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

(5)

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

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

(6)

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

(7)

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

(8)

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

1.4 部署成本

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

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

(9)

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

(10)

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

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

(11)

1.5 過度覆蓋

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

(12)

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

(13)

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

(14)

K-覆蓋率為：

(15)

2 MOEA/P

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

為了統(tǒng)一計算尺度，保證在各個目標(biāo)方向上的計算均衡，需要進(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)行算法實驗分析，但是在WSN中，投影維的設(shè)置與應(yīng)用需求有關(guān)，重要的目標(biāo)被設(shè)置成投影維并分段，個體被進(jìn)一步分格細(xì)化，再經(jīng)過自由維篩選可以得到更優(yōu)的解。

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

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

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

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

2.2 個體編碼

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

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

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

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

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

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

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

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

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

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

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

2.4 進(jìn)化計算

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

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

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

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

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

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

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

2.5 算法框架

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

3 實驗與討論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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