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

祁育仙， 李國(guó)勇

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

?

計(jì)算與測(cè)試

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

祁育仙， 李國(guó)勇

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

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

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)； 覆蓋； 多目標(biāo)優(yōu)化； 算子

0引言

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

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

1WSNs覆蓋問(wèn)題描述

1.1問(wèn)題建模

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

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

1.2節(jié)點(diǎn)感知模型

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

(1)

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

式中λ，β為傳感器節(jié)點(diǎn)檢測(cè)質(zhì)量的衰減系數(shù)；Re(0

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

(2)

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

為了簡(jiǎn)化運(yùn)算，本文將p點(diǎn)的覆蓋率定義為

(3)

1.3WSNs覆蓋目標(biāo)

定義子集S′?S，根據(jù)問(wèn)題模型可得出覆蓋目標(biāo)為：

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

(4)

目標(biāo)2：子集S′中工作節(jié)點(diǎn)數(shù)最少,即

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

(5)

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

目標(biāo)3：子集S′構(gòu)成的WSNs中能耗系數(shù)最小，即

(6)

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

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

max[f1,f2,f3]

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

(7)

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

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

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

2.1種群編碼

2.2交叉與變異策略的自適應(yīng)

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

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

2.3遺傳算子改進(jìn)

刪除算子：種群繁殖過(guò)程中，計(jì)算適值之后對(duì)個(gè)體進(jìn)行排序，在排序的同時(shí)引入刪除算子，將種群中相同的個(gè)體刪除，避免高適值個(gè)體占領(lǐng)種群引起早熟[9]。

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

變異算子：前一部分采取隨機(jī)選取兩個(gè)點(diǎn)，將其對(duì)換位置。后一部分采用基本位變異的方法。

2.4種群更新過(guò)程

改進(jìn)后的NSGA-Ⅱ種群更新過(guò)程如圖1所示。

圖1　種群更新過(guò)程Fig 1　Update process of populations

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

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

maxf=w1f1+w2f2+w3f3.

(8)

其中，w1+w2+w3=1，三個(gè)加權(quán)系數(shù)的選取依據(jù)設(shè)計(jì)者的選擇偏好來(lái)定。

3實(shí)驗(yàn)結(jié)果與分析

3.1實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

參數(shù)設(shè)置為：區(qū)域D為50 m×50 m，N為100，M為20，感知半徑為Rs=9 m，通信半徑為Rc=18 m，容錯(cuò)感知半徑為Re=5 m，λ=0.5,β=0.5，感知概率門(mén)限Cth=0.7，初始種群規(guī)模為50，最大迭代次數(shù)為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)定性

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

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

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

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

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

3.3與NSGA—Ⅱ算法進(jìn)行比較

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

圖4　性能對(duì)比曲線Fig 4　Performance comparison curves

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

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

圖5　能耗系數(shù)迭代過(guò)程Fig 5　Iterative process of energy consumption coefficient

4結(jié)束語(yǔ)

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

參考文獻(xiàn):

[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]蘭慎,彭剛.基于改進(jìn)魚(yú)群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].計(jì)算機(jī)仿真,2013,30(9):252-255.

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

[4]黃月,吳成東,張?jiān)浦?等.混合無(wú)線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)策略[J].江南大學(xué)學(xué)報(bào):自然科學(xué)版,2012,11(4):418-422.

[5]孔維鍵,丁進(jìn)良,柴天佑.高維多目標(biāo)進(jìn)化算法研究綜述[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]包北方,楊育,李雷霆,等.產(chǎn)品定制協(xié)同開(kāi)發(fā)任務(wù)分配多目標(biāo)化[J].計(jì)算機(jī)集成制造系統(tǒng),2014,20(4):740-746.

[9]李滿(mǎn)林,杜雷,聞?dòng)⒂?等.多目標(biāo)遺傳算法在移動(dòng)網(wǎng)絡(luò)規(guī)劃中的應(yīng)用[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

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(51075291)

中圖分類(lèi)號(hào)：TP 212

文獻(xiàn)標(biāo)識(shí)碼：A

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

作者簡(jiǎn)介:

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

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