基于多目標(biāo)優(yōu)化的WSNs節(jié)點(diǎn)優(yōu)化部署算法

錢建新,施沈科,何 燕,馮佳俊,徐會(huì)彬,成新民

(1.湖州市特種設(shè)備檢測(cè)研究院， 浙江 湖州 313000；2.湖州師范學(xué)院 信息工程學(xué)院,， 浙江 湖州 313000)

隨著通信、電子技術(shù)的進(jìn)步，物聯(lián)網(wǎng)應(yīng)用得到迅速的發(fā)展。而無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)[1]是物聯(lián)網(wǎng)的基石。WSNs由多個(gè)低功耗、具有感測(cè)、通信能力的微型傳感節(jié)點(diǎn)組成。通常傳感節(jié)點(diǎn)是由電池供電。當(dāng)電池用盡，節(jié)點(diǎn)無法工作[2]。由于節(jié)點(diǎn)常部署于野外或人不便接入的復(fù)雜環(huán)境，即使電池用盡，也無法給節(jié)點(diǎn)更換電池或者補(bǔ)充能量。因此，網(wǎng)絡(luò)能耗問題成為WSNs的研究熱點(diǎn)之一。

監(jiān)測(cè)興趣區(qū)域(Region of Interest,RoI)是部署節(jié)點(diǎn)的主要目的。高效率的監(jiān)測(cè)RoI是需要高質(zhì)量覆蓋保證[3]。通常覆蓋分區(qū)覆蓋和目標(biāo)覆蓋。前者是把監(jiān)測(cè)整個(gè)部署區(qū)域，而后者是監(jiān)測(cè)區(qū)域內(nèi)某個(gè)具體一點(diǎn)[4]。而目標(biāo)覆蓋又可分為Q-覆蓋和簡化覆蓋。在簡化覆蓋中，每個(gè)目標(biāo)至少由一個(gè)傳感節(jié)點(diǎn)監(jiān)測(cè)。而Q-覆蓋至少由Q個(gè)傳感節(jié)點(diǎn)監(jiān)測(cè)目標(biāo)[5]。

除了網(wǎng)絡(luò)覆蓋外，維護(hù)網(wǎng)絡(luò)連通也是部署節(jié)點(diǎn)必須考慮的問題。所謂網(wǎng)絡(luò)連通是指每個(gè)節(jié)點(diǎn)至少存在一條路徑通往信宿。

網(wǎng)絡(luò)能耗、網(wǎng)絡(luò)覆蓋和網(wǎng)絡(luò)連通都是部署節(jié)點(diǎn)時(shí)要考慮的問題。具體而言，部署節(jié)點(diǎn)時(shí)應(yīng)考慮以下4個(gè)問題：① 最小化網(wǎng)絡(luò)總體能耗；② 最大化覆蓋區(qū)域；③ 延長網(wǎng)絡(luò)壽命；④ 維護(hù)網(wǎng)絡(luò)連通，致使RoI內(nèi)每個(gè)節(jié)點(diǎn)能與信宿通信。

換而言之，考慮上述4個(gè)問題可理解成優(yōu)化節(jié)點(diǎn)部署的4個(gè)目標(biāo)。因此，優(yōu)節(jié)點(diǎn)部署問題屬多目標(biāo)優(yōu)化問題。利用多目標(biāo)優(yōu)化(Multi-objective Optimization,MOO)算法解決多目標(biāo)優(yōu)化問題是最好的選擇。例如，為了最大化網(wǎng)絡(luò)覆蓋區(qū)域，應(yīng)將傳感節(jié)點(diǎn)部署的位置離信宿越遠(yuǎn)越好。然而，離信宿越遠(yuǎn)，數(shù)據(jù)傳輸路徑就越長，這加大了能耗。因此，基于MOO算法的節(jié)點(diǎn)部署策略實(shí)質(zhì)上就是在兩個(gè)矛盾目標(biāo)間尋找一種平衡[6-7]。

花朵授粉(Flow Pollinate,FP)算法是由英國學(xué)者于2012年提出的啟發(fā)式智能算法[8]。FP算利用Levy飛行模式，具有良好的全局搜索能力[9]，且可實(shí)現(xiàn)全局搜索與局部搜索間的平衡，已在目標(biāo)函數(shù)優(yōu)化、電子系統(tǒng)優(yōu)化等問題中廣泛應(yīng)用[10-11]。

為此，將FP算法解決節(jié)點(diǎn)部署的多目標(biāo)優(yōu)化問題。通過FP算法計(jì)算節(jié)點(diǎn)的最優(yōu)位置，進(jìn)而使網(wǎng)絡(luò)能耗、壽命以及覆蓋、連通達(dá)到平衡。仿真數(shù)據(jù)表明：相比于同類算法，F(xiàn)PNP算法能夠在滿足96%覆蓋率的條件，能耗最少，網(wǎng)絡(luò)壽命最長。

1 多目標(biāo)函數(shù)的構(gòu)建

考慮兩維平面l1×l2網(wǎng)絡(luò)結(jié)構(gòu)。在該網(wǎng)絡(luò)區(qū)域內(nèi)部署N個(gè)傳感節(jié)點(diǎn)。令Rs、Rc分別表示節(jié)點(diǎn)的感測(cè)半徑和通信半徑。通常，假定Rs>Rc。用G=(V,E)圖表示描述網(wǎng)絡(luò)拓?fù)?，其中V為頂點(diǎn)集，其表示傳感節(jié)點(diǎn){s1,s2,…,si,…,sN}。E為邊集。若對(duì)于任意兩個(gè)節(jié)點(diǎn)(si,sj)，如果它們間的距離di, j小于Rc，則它們存在一邊，即它們能夠直接通信(圖1)。

圖1 傳感節(jié)點(diǎn)感測(cè)和通信范圍示意圖

1.1 能耗模型

(1)

其中：MEi表示維持節(jié)點(diǎn)正常工作的啟動(dòng)能耗；TEi為傳輸能耗；Psi表示從節(jié)點(diǎn)至信宿的最短路徑；REi為接收數(shù)據(jù)所消耗的能量；αi表示節(jié)點(diǎn)si將數(shù)據(jù)傳輸至信宿中所參與的節(jié)點(diǎn)數(shù)。

整個(gè)網(wǎng)絡(luò)所消耗的能量可依式(2)計(jì)算，并形成第一個(gè)目標(biāo)函數(shù)：

(2)

1.2 網(wǎng)絡(luò)壽命

對(duì)于網(wǎng)絡(luò)而言，引用兩個(gè)指標(biāo)表述網(wǎng)絡(luò)壽命。首先，考慮網(wǎng)絡(luò)內(nèi)第一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間，如式(3)所示：

LT1=min(ti),i=1,2,…,N

(3)

同時(shí)，考慮最后一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間，如式(4)所示：

LT2=max(ti),i=1,2,…,N

(4)

1.3 覆蓋感知模型

將l1×l2網(wǎng)絡(luò)區(qū)域劃分離散的m×n個(gè)網(wǎng)格。令(xi,yi)表示節(jié)點(diǎn)si的位置坐標(biāo)。如圖2所示，節(jié)點(diǎn)si的感知區(qū)域就是以(xi,yi)為圓心，半徑為Rc的圓。

圖2 基于網(wǎng)格的感測(cè)示意圖

對(duì)于網(wǎng)格內(nèi)點(diǎn)p(x,y)，它與節(jié)點(diǎn)si間的距離d(si,p)：

(5)

令P(ri)表示點(diǎn)p(x,y)被節(jié)點(diǎn)si覆蓋的概率，其定義如式(6)所示：

(6)

假定有多個(gè)節(jié)點(diǎn)對(duì)點(diǎn)p(x,y)進(jìn)行了覆蓋，這些節(jié)點(diǎn)構(gòu)成集合C。而點(diǎn)p(x,y)被C覆蓋的概率可表示為：

(7)

其中|C|表示集合C的元素個(gè)數(shù)。

集合C內(nèi)的節(jié)點(diǎn)覆蓋的網(wǎng)格點(diǎn)的面積之和：

(8)

將式(8)進(jìn)行推廣。網(wǎng)絡(luò)內(nèi)總共有N個(gè)節(jié)點(diǎn)。令Ψ表示這N個(gè)節(jié)點(diǎn)所形成的節(jié)點(diǎn)集。集合Ψ所覆蓋的網(wǎng)格點(diǎn)的面積之和：

(9)

最后，建立第2個(gè)目標(biāo)函數(shù)：

f2=1-ρc

(10)

1.4 目標(biāo)函數(shù)

最后，建立式(11)所示的目標(biāo)函數(shù)，其中ω1、ω2為權(quán)重系數(shù)。式(11)由兩項(xiàng)組成。第一項(xiàng)是最小能耗，第二項(xiàng)最大化覆蓋率：

(11)

2 基于FP算法的目標(biāo)函數(shù)求解

FP算法是基于顯花植物的授粉過程而演化的算法。有兩種方式授粉：自花授粉和異花授粉。前者是指植株成熟的花粉粒傳播到花朵上，而后者是通過自然界動(dòng)物飛行攜帶花粉粒給花朵授粉。相比于自花授粉，異花授粉的傳播范圍大[9]。

FP算法求解目標(biāo)函數(shù)的實(shí)質(zhì)，就是搜索解。對(duì)應(yīng)其兩種授粉方式，搜索解也分為兩種：局部尋優(yōu)搜索和全局尋優(yōu)搜索。且這種搜索方式可進(jìn)行轉(zhuǎn)換，且轉(zhuǎn)換概率為p。

表1反映了求解目標(biāo)函數(shù)的過程。先初始化基本參數(shù)，包括迭代參數(shù)MaxT、種群個(gè)體數(shù)Nf和轉(zhuǎn)換概率p。

表1 FP算法的偽代碼

然后，再對(duì)種群內(nèi)每個(gè)個(gè)體位置進(jìn)行隨機(jī)初始化，并計(jì)算其對(duì)應(yīng)的適應(yīng)度值。再獲取最優(yōu)的全局解g*。

第3步，檢測(cè)是否滿足條件rand≥p′檢測(cè)是否滿足搜索模式的轉(zhuǎn)換條件。若滿足，進(jìn)行全局搜索，并依據(jù)式(12)進(jìn)行處理：

Fi(t+1)=Fi(t)+L(g*-Fi(t))

(12)

其中Fi(t+1)、Fi(t)分別表示第t+1、t次迭代的第i解。而g*為全局解。L是服從Levy分布的隨機(jī)步長。

若不滿足，就進(jìn)行局部搜索，并依式(13)處理：

Fi(t+1)=Fi(t)+ε(Fk(t)-Fj(t))

(13)

其中：ε表示在[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)；Fk(t)和Fj(t)表示不同于Fi(t)的兩個(gè)位置。

再判斷Fi(t+1)

最后，判斷是否滿足迭代終止條件。終止迭代后，就輸出最優(yōu)解。最優(yōu)解就是部署節(jié)點(diǎn)的最優(yōu)位置。

3 性能仿真

3.1 仿真參數(shù)

利用NS 2.34軟件建立仿真平臺(tái)，并分析FPNP算法的性能。在60 m×60 m區(qū)域內(nèi)部署N個(gè)節(jié)點(diǎn)。并將60 m×60 m區(qū)域劃分為邊長為1 m的網(wǎng)格。具體的仿真參數(shù)值如表2所示。

表2 仿真參數(shù)

此外，選擇同類的PSO算法[1]和NSG-Ⅱ算法[13]作為參照，并對(duì)比分析FPNP算法性能，包括能耗及網(wǎng)絡(luò)壽命。

3.2 數(shù)據(jù)分析

首先，分析在實(shí)現(xiàn)網(wǎng)絡(luò)覆蓋率ρ=0.96時(shí)，3個(gè)算法所消耗的能量，簡稱能耗如圖3所示。

從圖3可知：相比于PSO和NSGA-Ⅱ算法，提出的FPNP算法的能耗最低，即在實(shí)現(xiàn)同樣的覆蓋率的同時(shí)，所消耗的網(wǎng)絡(luò)能量最低。而PSO算法的能耗最高，原因在于：PSO算法在運(yùn)行時(shí)，具有兩個(gè)復(fù)雜的約束條件，并限制了種群個(gè)體數(shù)的分布。而FPNP算法將降低能耗作為目標(biāo)函數(shù)的第一項(xiàng)(如式(11))，其旨在降低能耗。

接下來，分析網(wǎng)絡(luò)壽命，圖4、圖5分別顯示了第一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間、最后一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間，定義分別如式(3)、式(4)所示。

圖3 能耗曲線

圖4 第一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間曲線

圖5 最后一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間

從圖4可知：FPNP算法有效地延長了第一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間，而PSO算法最早出現(xiàn)能量消耗殆盡的節(jié)點(diǎn)。而NSGA-Ⅱ算法與FPNP算法的性能相近，F(xiàn)PNP算法的性能略優(yōu)于NSGA-Ⅱ算法，第1個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間延長了平均約6 h。

圖5顯示了最后一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間，與圖4類似。結(jié)合圖4、圖5可知，F(xiàn)PNP算法的有效地降低網(wǎng)絡(luò)能耗。相比于PSO算法、NSGA-Ⅱ算法，F(xiàn)PNP算法通過優(yōu)先部署節(jié)點(diǎn)，在維持相同的覆蓋率，降低了網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)壽命。

4 結(jié)論

針對(duì)無線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)部署問題，提出基于花朵授粉算法的節(jié)點(diǎn)部署FPNP。FPNP算法先將節(jié)點(diǎn)部署問題轉(zhuǎn)換成多目標(biāo)優(yōu)化問題，再利用花朵授粉算法搜索部署節(jié)點(diǎn)的最優(yōu)位置。通過部署最優(yōu)位置，降低能耗，延長網(wǎng)絡(luò)壽命。仿真結(jié)果表明：提出的FPNP算法降低了網(wǎng)絡(luò)能耗，延長了網(wǎng)絡(luò)壽命。