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

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

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

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

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

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

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

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

為此，將FP算法解決節(jié)點部署的多目標(biāo)優(yōu)化問題。通過FP算法計算節(jié)點的最優(yōu)位置，進而使網(wǎng)絡(luò)能耗、壽命以及覆蓋、連通達到平衡。仿真數(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個傳感節(jié)點。令Rs、Rc分別表示節(jié)點的感測半徑和通信半徑。通常，假定Rs>Rc。用G=(V,E)圖表示描述網(wǎng)絡(luò)拓撲，其中V為頂點集，其表示傳感節(jié)點{s1,s2,…,si,…,sN}。E為邊集。若對于任意兩個節(jié)點(si,sj)，如果它們間的距離di, j小于Rc，則它們存在一邊，即它們能夠直接通信(圖1)。

圖1 傳感節(jié)點感測和通信范圍示意圖

1.1 能耗模型

(1)

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

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

(2)

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

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

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

(3)

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

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

(4)

1.3 覆蓋感知模型

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

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

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

(5)

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

(6)

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

(7)

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

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

(8)

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

(9)

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

f2=1-ρc

(10)

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

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

(11)

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

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

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

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

表1 FP算法的偽代碼

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

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

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

(12)

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

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

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

(13)

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

再判斷Fi(t+1)

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

3 性能仿真

3.1 仿真參數(shù)

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

表2 仿真參數(shù)

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

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

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

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

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

圖3 能耗曲線

圖4 第一個節(jié)點能量消耗殆盡的時間曲線

圖5 最后一個節(jié)點能量消耗殆盡的時間

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

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

4 結(jié)論

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