基于多目標優化的WSNs節點優化部署算法

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

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

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

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

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

網絡能耗、網絡覆蓋和網絡連通都是部署節點時要考慮的問題。具體而言，部署節點時應考慮以下4個問題：① 最小化網絡總體能耗；② 最大化覆蓋區域；③ 延長網絡壽命；④ 維護網絡連通，致使RoI內每個節點能與信宿通信。

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

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

為此，將FP算法解決節點部署的多目標優化問題。通過FP算法計算節點的最優位置，進而使網絡能耗、壽命以及覆蓋、連通達到平衡。仿真數據表明：相比于同類算法，FPNP算法能夠在滿足96%覆蓋率的條件，能耗最少，網絡壽命最長。

1 多目標函數的構建

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

圖1 傳感節點感測和通信范圍示意圖

1.1 能耗模型

(1)

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

整個網絡所消耗的能量可依式(2)計算，并形成第一個目標函數：

(2)

1.2 網絡壽命

對于網絡而言，引用兩個指標表述網絡壽命。首先，考慮網絡內第一個節點能量消耗殆盡的時間，如式(3)所示：

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

(3)

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

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

(4)

1.3 覆蓋感知模型

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

圖2 基于網格的感測示意圖

對于網格內點p(x,y)，它與節點si間的距離d(si,p)：

(5)

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

(6)

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

(7)

其中|C|表示集合C的元素個數。

集合C內的節點覆蓋的網格點的面積之和：

(8)

將式(8)進行推廣。網絡內總共有N個節點。令Ψ表示這N個節點所形成的節點集。集合Ψ所覆蓋的網格點的面積之和：

(9)

最后，建立第2個目標函數：

f2=1-ρc

(10)

1.4 目標函數

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

(11)

2 基于FP算法的目標函數求解

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

FP算法求解目標函數的實質，就是搜索解。對應其兩種授粉方式，搜索解也分為兩種：局部尋優搜索和全局尋優搜索。且這種搜索方式可進行轉換，且轉換概率為p。

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

表1 FP算法的偽代碼

然后，再對種群內每個個體位置進行隨機初始化，并計算其對應的適應度值。再獲取最優的全局解g*。

第3步，檢測是否滿足條件rand≥p′檢測是否滿足搜索模式的轉換條件。若滿足，進行全局搜索，并依據式(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]區間內的隨機數；Fk(t)和Fj(t)表示不同于Fi(t)的兩個位置。

再判斷Fi(t+1)

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

3 性能仿真

3.1 仿真參數

利用NS 2.34軟件建立仿真平臺，并分析FPNP算法的性能。在60 m×60 m區域內部署N個節點。并將60 m×60 m區域劃分為邊長為1 m的網格。具體的仿真參數值如表2所示。

表2 仿真參數

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

3.2 數據分析

首先，分析在實現網絡覆蓋率ρ=0.96時，3個算法所消耗的能量，簡稱能耗如圖3所示。

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

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

圖3 能耗曲線

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

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

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

圖5顯示了最后一個節點能量消耗殆盡的時間，與圖4類似。結合圖4、圖5可知，FPNP算法的有效地降低網絡能耗。相比于PSO算法、NSGA-Ⅱ算法，FPNP算法通過優先部署節點，在維持相同的覆蓋率，降低了網絡能耗，延長網絡壽命。

4 結論

針對無線傳感網絡的節點部署問題，提出基于花朵授粉算法的節點部署FPNP。FPNP算法先將節點部署問題轉換成多目標優化問題，再利用花朵授粉算法搜索部署節點的最優位置。通過部署最優位置，降低能耗，延長網絡壽命。仿真結果表明：提出的FPNP算法降低了網絡能耗，延長了網絡壽命。