祁育仙， 李國勇

(太原理工大學 信息工程學院，山西 太原 030024)

?

計算與測試

混合WSNs中基于多目標優(yōu)化的覆蓋控制算法*

祁育仙， 李國勇

(太原理工大學 信息工程學院，山西 太原 030024)

摘要:針對無線傳感器網絡(WSNs)隨機部署產生的區(qū)域覆蓋率低、節(jié)點利用率差和能量不均衡的問題，引入移動傳感器節(jié)點，將快速非支配排序遺傳算法Ⅱ(NSGA-Ⅱ)運用到混合無線傳感器網絡覆蓋控制部署并進行改進，采用分層編碼策略，引入刪除算子避免早熟，自適應改變交叉、變異概率提高局部搜索能力，獲得較優(yōu)解集后基于決策者信息偏好選擇最優(yōu)目標。仿真實驗結果表明:有效解決了WSNs覆蓋控制問題，可以在網絡覆蓋率最大化的同時，節(jié)點利用率較大且能耗系數較低，延長網絡壽命。

關鍵詞：無線傳感器網絡； 覆蓋； 多目標優(yōu)化； 算子

0引言

無線傳感器網絡(wireless sensor networks,WSNs)是一種全新的信息獲取和處理的方式，廣泛應用于軍事、環(huán)境保護、農業(yè)和醫(yī)療等其他領域。在條件惡劣的情況下，由飛行器隨機部署網絡節(jié)點，會產生高密度節(jié)點和覆蓋空洞，影響網絡服務質量，又由于WSNs中每個節(jié)點電池能量有限、難以補充，因此，在覆蓋率最大化的同時延長網絡生命周期是WSNs面臨的重要難題。文獻[1]將免疫優(yōu)化引入粒子群算法，維持了種群多樣性，但是沒有考慮能耗均衡對網絡性能的影響。文獻[2]綜合考慮了網絡覆蓋率、節(jié)點利用率和能耗均衡對網絡性能的影響，利用混沌運動的遍歷性提高了算法的全局搜索能力，但是其目標函數采用加權算法，決策者很難做出取舍與平衡。文獻[3]建立了最大化網絡覆蓋率、最大化節(jié)點休眠率和最小化網絡工作能耗的傳感器網絡壽命多目標優(yōu)化模型，提出基于非支配排序遺傳算法(nondominated sorting genetic algorithm Ⅱ，NSGA—Ⅱ)的網絡覆蓋解決方案，可以獲得更有效的網絡覆蓋率和更少的網絡能量消耗，但是其WSNs中需隨機布設大量的靜態(tài)節(jié)點，成本相應增加。

本文采用固定節(jié)點和移動節(jié)點相結合的方式組成混合WSNs，利用少量移動節(jié)點的移動性滿足覆蓋質量，將NSGA—Ⅱ進行改進用于混合WSNs覆蓋優(yōu)化。

1WSNs覆蓋問題描述

1.1問題建模

M個移動傳感器節(jié)點和N個固定傳感器節(jié)點構成節(jié)點集S(S={s1,s2,…，si,…,sM+N})由飛行器隨機部署在監(jiān)測區(qū)域D的二維矩形平面。研究的問題是：1)盡可能發(fā)現(xiàn)固定傳感器冗余節(jié)點使其進入休眠狀態(tài)，使得網絡在連通的前提下使用盡可能少的節(jié)點下獲得最大的覆蓋率；2)求得各個移動傳感器節(jié)點的運動規(guī)劃，使得最小的運動代價獲得網絡覆蓋質量的最大提升；3)使得網絡能耗盡量均衡，延長網絡生命周期。

在不影響問題本質的前提下，做出如下假設：1)已知固定節(jié)點的精確位置信息；所有傳感器均為同一結構，感知半徑為Rs,通信半徑為Rc，且Rc=2Rs；2)每個節(jié)點具有工作、休眠和偵測三種狀態(tài)；3)將區(qū)域D離散化為m×n個像素點；4)所有移動傳感器節(jié)點可準確移動到指定位置。

1.2節(jié)點感知模型

目前，在WSNs研究中廣泛使用的是二元感知模型和概率感知模型，本文使用更符合實際應用的概率感知模型。傳感器節(jié)點si(xi,yi)對監(jiān)測區(qū)域中任意一點p(xp,yp)感知概率為[4]

(1)

式中d(si,p)為節(jié)點si(xi,yi)到p點的歐氏距離

式中λ，β為傳感器節(jié)點檢測質量的衰減系數；Re(0

由式(1)可以得出所有節(jié)點在p點的聯(lián)合監(jiān)測概率為

(2)

若p點被有效感知，且區(qū)域內任意一點被有效感知的概率閾值為Cth，則其必須滿足Cp(S,p)′≥Cth。

為了簡化運算，本文將p點的覆蓋率定義為

(3)

1.3WSNs覆蓋目標

定義子集S′?S，根據問題模型可得出覆蓋目標為：

目標1：覆蓋率Pcov(S′)最大,即

(4)

目標2：子集S′中工作節(jié)點數最少,即

maxf2=1-|S′|/|S|.

(5)

其中，|S′|為工作節(jié)點總數；|S|為WSNs中部署的傳感器節(jié)點總數。

目標3：子集S′構成的WSNs中能耗系數最小，即

(6)

其中，Ei為節(jié)點i的剩余能耗。

WSNs覆蓋目標可以歸結為滿足網絡全連通條件(即對于工作狀態(tài)的任意傳感器節(jié)點si(xi,xj)，在其通信范圍內至少存在一個傳感器節(jié)點sj(xj,yj))的多目標優(yōu)化問題，即

max[f1,f2,f3]

s.t.?i∈[1,N+M],?j∈[1,N+M],且i≠j,

(7)

2混合WSNs覆蓋優(yōu)化算法

WSNs覆蓋優(yōu)化問題是個典型的多目標優(yōu)化問題，多個目標間存在沖突，就所有目標而言，不存在一個唯一的最大值或最小值。相反地，存在多個最優(yōu)解，這些解是所有沖突目標之間的折中結果。

目前的多目標優(yōu)化算法很多，但是帶精英策略的快速NSGA—Ⅱ算法是應用最為廣泛的一種[5～7]，但是其種群迭代過程會陷入局部最優(yōu)解，為了獲取優(yōu)秀的Pareto最優(yōu)解，提高搜索能力，防止陷入局部最優(yōu)解，本文對NSGA—Ⅱ算法加以改進應用到WSNs覆蓋優(yōu)化問題，并采用基于決策者信息偏好選擇最優(yōu)解。

2.1種群編碼

2.2交叉與變異策略的自適應

SGA中交叉概率Pc和變異概率Pm是不變的，導致后期搜索遲鈍，進化停滯，自適應控制可以有效地改善后期收斂速度，在進化過程中自適應的改變Pc,Pm的大小，將進化過程分為漸進和突變兩個不同的階段：漸進階段強交叉、弱變異，擴大整體搜索范圍，突變階段弱交叉、強變異，使優(yōu)良基因結構得以保存，且防止陷入局部最優(yōu)，自適應調節(jié)公式為[8]

式中f為兩個交叉?zhèn)€體適應度值的較大值；f ′為變異個體的適應度值；favg,fmax和fmin分別為當前種群所有個體的平均適應度值、最大適應度值和最小適應度值；Pc min和Pc max分別為交叉概率的最小值和最大值；Pm min和Pm max分別為變異概率的最小值和最大值。

2.3遺傳算子改進

刪除算子：種群繁殖過程中，計算適值之后對個體進行排序，在排序的同時引入刪除算子，將種群中相同的個體刪除，避免高適值個體占領種群引起早熟[9]。

交叉算子：前一部分為移動節(jié)點集，采用部分映射交叉，后一部分為所有節(jié)點工作狀態(tài)，為二進制編碼，采用單點交叉。

變異算子：前一部分采取隨機選取兩個點，將其對換位置。后一部分采用基本位變異的方法。

2.4種群更新過程

改進后的NSGA-Ⅱ種群更新過程如圖1所示。

圖1　種群更新過程Fig 1　Update process of populations

2.5最優(yōu)個體的選取

根據多目標遺傳算法將得到多組Pareto解集，實際應用中，必須在解集中選取一組解當做最優(yōu)WSNs節(jié)點部署方案。本文將非劣前端中的個體采用式(8)的加權法得出集合中各個體的適應度值，選取適應度值最大的個體作為最優(yōu)的部署方案

maxf=w1f1+w2f2+w3f3.

(8)

其中，w1+w2+w3=1，三個加權系數的選取依據設計者的選擇偏好來定。

3實驗結果與分析

3.1實驗環(huán)境與參數設置

參數設置為：區(qū)域D為50 m×50 m，N為100，M為20，感知半徑為Rs=9 m，通信半徑為Rc=18 m，容錯感知半徑為Re=5 m，λ=0.5,β=0.5，感知概率門限Cth=0.7，初始種群規(guī)模為50，最大迭代次數為200，Pc max=0.45，Pc min=0.25,Pm max=0.04,Pm min=0.02,w1=0.6,w2=0.25,w3=0.15。

3.2算法有效性與穩(wěn)定性

首先，檢驗算法的可行性，由參數設定，得出WSNs覆蓋優(yōu)化結果如圖2所示。

圖2　WSNs覆蓋優(yōu)化結果Fig 2　Optimization results of WSNs coverage

由圖2可知，經過本文算法優(yōu)化后，由節(jié)點覆蓋率、節(jié)點休眠率以及能耗系數組成的三維坐標均勻分布，且優(yōu)化后覆蓋率增加明顯，節(jié)點休眠率也明顯增大，能耗系數也相應的減小。

為檢驗算法的穩(wěn)定性，將算法執(zhí)行10次，其覆蓋率如圖3所示。 圖中數字表示工作節(jié)點數，通過算法優(yōu)化，可以使WSNs覆蓋率均可以達到97 %以上，且使得網絡中的冗余節(jié)點均處于休眠狀態(tài)，延長網絡壽命。

圖3　優(yōu)化前后覆蓋率對比Fig 3　Coverage rate comparison before and after optimization

3.3與NSGA—Ⅱ算法進行比較

為進一步驗證算法的性能，將本文算法與原始NSGA—Ⅱ算法進行比較分析，得出如圖4所示性能對比曲線。

圖4　性能對比曲線Fig 4　Performance comparison curves

由圖4可知，在工作節(jié)點數相同的情況下，本文算法可以獲得更高的覆蓋率，延長網絡壽命。

進一步，將本文算法與NSGA—Ⅱ每一種群迭代更新后的能耗系數平均值做比較，如圖5所示。可得出，本文算法對于混合WSNs覆蓋可以更好地降低能耗系數，延長網絡壽命。

圖5　能耗系數迭代過程Fig 5　Iterative process of energy consumption coefficient

4結束語

本文對混合WSNs覆蓋問題進行分析，由其是典型的多目標優(yōu)化問題，將NSGA—Ⅱ算法并進行改進用于WSNs的覆蓋優(yōu)化，使用分層編碼策略，引入刪除算子，自適應調整交叉、變異概率，得到Pareto最優(yōu)解集采用決策者信息偏好來選擇最優(yōu)解，通過實驗仿真顯示：該算法可以用于混合WSNs覆蓋控制，改進后的算法較NSGA—Ⅱ可以防止陷入局部最優(yōu)解，在工作節(jié)點數相同的情況下，改進后的算法可以得到更高的覆蓋率，增大節(jié)點利用率，且能耗系數較低，延長網絡壽命。

參考文獻:

[1]Mo Yuanbin,Liu Jizhong,Wang Baolei,et al.A novel swarm in-

telligence algorithm and its application in solving wireless sensor networks coverage problems[J].Journal of Networks,2012,7(12):2037-2042.

[2]蘭慎,彭剛.基于改進魚群算法的無線傳感器網絡覆蓋優(yōu)化[J].計算機仿真,2013,30(9):252-255.

[3]賈杰,陳劍,常桂然,等.基于節(jié)點協(xié)同覆蓋的傳感器網絡壽命最大化模型[J].控制與決策, 2009,24(8):1181-1186.

[4]黃月,吳成東,張云洲,等.混合無線傳感器網絡覆蓋空洞修復策略[J].江南大學學報:自然科學版,2012,11(4):418-422.

[5]孔維鍵,丁進良,柴天佑.高維多目標進化算法研究綜述[J].控制與決策,2010,25(3):321-326.

[6]Segupta Soumyadip,Das Swagatam,Nasir M D,et al.Multi-objective node deployment in WSNs:In search of an optimal trade-off among coverage,lifetime,energy consumption, and connectivity[J].Engineering Applications of Artificial Intelligence,2013,26:405-415.

[7]Segupta S,Das S,Vasilakos A V,et al.An evolutionary multi-objective sleep-scheduling scheme for differentiated coverage in wireless sensor networks [J].Applications and Reviews,2012,42(6):1093-1102.

[8]包北方,楊育,李雷霆,等.產品定制協(xié)同開發(fā)任務分配多目標化[J].計算機集成制造系統(tǒng),2014,20(4):740-746.

[9]李滿林,杜雷,聞英友,等.多目標遺傳算法在移動網絡規(guī)劃中的應用[J].控制與決策, 2003,18(4):441-444.

Coverage control algorithm for hybrid WSNs based on multi-objective optimization*

QI Yu-xian, LI Guo-yong

(College of Information Engineering,Taiyuan University of Technology,Taiyuan 030024,China)

Abstract:Aiming at problem of low coverage rate, poor utilization rate of node and energy imbalance caused by random deployment of wireless sensor networks(WSNs),introduce mobile sensor nodes,use and modify NSGA-Ⅱ to hybrid WSNs coverage control deployment.Use hierarchical coding strategies,introduce delete operator to avoid early-maturing,adjust crossover and mutation probability adaptively to improve local search ability,choose the optimal target based on decision makers’ information preference,after obtaining optimal solution sets.Simulation experimental result show that this algorithm is an effective solution for coverage control problem,having higher nodes usage and lower energy consumption coefficient,prolong network lifetime,while maximizing network coverage rate and extend network lifetime.

Key words:wireless sensor networks(WSNs); coverage; multi-objective optimization; operator

DOI:10.13873/J.1000—9787(2016)02—0136—04

收稿日期：2015—03—25

*基金項目：國家自然科學基金資助項目(51075291)

中圖分類號：TP 212

文獻標識碼：A

文章編號：1000—9787(2016)02—0136—04

作者簡介:

祁育仙(1989-)，女，山西太原人，碩士，主要從事預測控制、智能控制理論及應用等研究。

李國勇，通訊作者，E—mail:tygdlgy@163.com。