一種多目標(biāo)的覆蓋優(yōu)化策略在WSNs中的應(yīng)用*

陳 樹，錢 成

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

應(yīng)用技術(shù)

一種多目標(biāo)的覆蓋優(yōu)化策略在WSNs中的應(yīng)用*

陳 樹，錢 成

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

針對(duì)目前無(wú)線傳感器網(wǎng)絡(luò)(WSNs)能量均衡覆蓋策略大都基于節(jié)點(diǎn)靜態(tài)感知能耗的不足，提出一種基于節(jié)點(diǎn)的動(dòng)態(tài)能耗和網(wǎng)絡(luò)覆蓋率的多目標(biāo)覆蓋優(yōu)化策略。該優(yōu)化覆蓋策略將動(dòng)態(tài)路由協(xié)議引入到覆蓋控制優(yōu)化中，計(jì)算覆蓋區(qū)域在不同節(jié)點(diǎn)分布下的動(dòng)態(tài)通信能耗和網(wǎng)絡(luò)的剩余能量，再結(jié)合區(qū)域覆蓋率構(gòu)成對(duì)覆蓋和能量綜合指數(shù)評(píng)價(jià)的優(yōu)化函數(shù)。最后利用改進(jìn)差分進(jìn)化算法和差分進(jìn)化算法對(duì)優(yōu)化函數(shù)進(jìn)行仿真，并利用覆蓋結(jié)果驗(yàn)證策略的有效性。仿真結(jié)果表明：提出的覆蓋優(yōu)化策略既能使網(wǎng)絡(luò)達(dá)到較高覆蓋率，同時(shí)又能保證網(wǎng)絡(luò)的能耗動(dòng)態(tài)均衡，并將改進(jìn)差分進(jìn)化算法與常規(guī)差分進(jìn)化算法比較，結(jié)果表明：前者克服了早熟現(xiàn)象，覆蓋和能量的綜合優(yōu)化函數(shù)值更高，達(dá)到了6.184。

無(wú)線傳感器網(wǎng)絡(luò); 能量均衡; 動(dòng)態(tài)路由協(xié)議; 網(wǎng)絡(luò)覆蓋; 差分進(jìn)化算法

0 引 言

在無(wú)線傳感器網(wǎng)絡(luò)(WSNs)覆蓋優(yōu)化控制算法中，網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)能耗均衡是熱點(diǎn)研究問題。文獻(xiàn)[1]采用混沌粒子群算法，以網(wǎng)絡(luò)覆蓋率為優(yōu)化目標(biāo)，由算法迭代出覆蓋率最優(yōu)傳感器節(jié)點(diǎn)集，從而實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的覆蓋控制。文獻(xiàn)[2]針對(duì)異構(gòu)傳感網(wǎng)絡(luò)節(jié)點(diǎn)初始隨機(jī)部署時(shí)產(chǎn)生覆蓋盲區(qū)和覆蓋冗余的問題，以降低節(jié)點(diǎn)成本和提高網(wǎng)絡(luò)覆蓋率為目標(biāo)，引入ε目標(biāo)約束法，提出一種基于粒子群算法和魚群算法的群混合算法，實(shí)現(xiàn)網(wǎng)絡(luò)覆蓋率和成本之間的平衡和優(yōu)化。在 WSNs網(wǎng)絡(luò)傳輸層，受限于傳感器節(jié)點(diǎn)自身的電池能量，節(jié)點(diǎn)間采用自組織和多跳的方式進(jìn)行通信和數(shù)據(jù)傳輸，而網(wǎng)絡(luò)簇頭的頻繁更換和發(fā)送成簇信息，將消耗大量節(jié)點(diǎn)能量。因此，網(wǎng)絡(luò)能耗均衡也是一個(gè)重要的指標(biāo)。文獻(xiàn)[1,2]均利用改進(jìn)迭代算法，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的位置進(jìn)行尋優(yōu)，即在網(wǎng)絡(luò)的拓?fù)鋵?，?duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行最優(yōu)部署，實(shí)現(xiàn)覆蓋率最大化目標(biāo)，但文獻(xiàn)[1,2]都沒有考慮能量均衡對(duì)網(wǎng)絡(luò)性能的影響。文獻(xiàn)[3]建立以網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)能量均衡作為優(yōu)化目標(biāo)函數(shù)，將節(jié)點(diǎn)的靜態(tài)感知能量損耗作為能量均衡指標(biāo)，在每次算法迭代中，計(jì)算每個(gè)區(qū)域的剩余能量，并結(jié)合覆蓋率得到綜合優(yōu)化指數(shù)。文獻(xiàn)[4]提出一種基于WSNs能耗、能耗均衡和覆蓋率多目標(biāo)優(yōu)化覆蓋控制策略。在構(gòu)建網(wǎng)絡(luò)模型的基礎(chǔ)上，以覆蓋率、能耗和網(wǎng)絡(luò)能耗均衡為優(yōu)化目標(biāo)，實(shí)現(xiàn)網(wǎng)絡(luò)性能的綜合優(yōu)化。文獻(xiàn)[3,4]將能量均衡引入到覆蓋率控制中，實(shí)現(xiàn)了多目標(biāo)覆蓋優(yōu)化，但文中的能量是基于節(jié)點(diǎn)的感知能耗，沒有考慮節(jié)點(diǎn)的動(dòng)態(tài)通信能耗。

本文提出了一種基于節(jié)點(diǎn)的動(dòng)態(tài)通信能耗結(jié)合網(wǎng)絡(luò)覆蓋率的多目標(biāo)覆蓋優(yōu)化策略。該策略將LEACH[5](low energy adaptive clustering hierarchy)路由協(xié)議引入到覆蓋控制優(yōu)化中，計(jì)算由節(jié)點(diǎn)的動(dòng)態(tài)通信能耗得到網(wǎng)絡(luò)的剩余能量，并結(jié)合網(wǎng)絡(luò)覆蓋率建立優(yōu)化目標(biāo)，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的動(dòng)態(tài)能耗均衡和覆蓋率優(yōu)化的雙重目標(biāo)。

1 覆蓋優(yōu)化策略

1.1 網(wǎng)絡(luò)覆蓋率

假定區(qū)域?yàn)槎S平面，擬在區(qū)域上投放n個(gè)傳感器節(jié)點(diǎn)。設(shè)ci=(xi,yi)為傳感器節(jié)點(diǎn)的坐標(biāo)，則節(jié)點(diǎn)ci對(duì)網(wǎng)格點(diǎn)qj=(xj,yj)的感知概率[3]為

式中d(ci,qj)為節(jié)點(diǎn)ci與qj的實(shí)際距離，Re為節(jié)點(diǎn)測(cè)量的可靠性參數(shù)，b為節(jié)點(diǎn)的感知概率閾值，a為網(wǎng)格點(diǎn)被傳感器監(jiān)測(cè)到的概率隨距離增大而減小的速率。由于目標(biāo)點(diǎn)qj的感知概率是傳感器節(jié)點(diǎn)協(xié)同監(jiān)測(cè)的結(jié)果，設(shè)Call為傳感器節(jié)點(diǎn)的集合，則Call對(duì)目標(biāo)點(diǎn)qj的感知概率[6,7]為

設(shè)目標(biāo)區(qū)域被離散化為M×N個(gè)網(wǎng)格，每個(gè)網(wǎng)格的面積表示為1，則可得Call對(duì)整個(gè)監(jiān)測(cè)區(qū)域的覆蓋率

(1)

由上可知，式(1)的最大值就是網(wǎng)絡(luò)的最大覆蓋率。但對(duì)一個(gè)能量有限的WSNs，僅以最大覆蓋率為優(yōu)化目標(biāo)是片面的。覆蓋率高的網(wǎng)絡(luò)和能量消耗均衡的網(wǎng)絡(luò)并沒有對(duì)應(yīng)關(guān)系。為此，要充分優(yōu)化網(wǎng)絡(luò)的覆蓋性能，一個(gè)好的優(yōu)化方案必須同時(shí)兼顧覆蓋率和動(dòng)態(tài)通信能耗兩方面的要求。

1.2 網(wǎng)絡(luò)節(jié)點(diǎn)通信能耗

運(yùn)用LEACH協(xié)議對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)間的通信進(jìn)行模擬，得到節(jié)點(diǎn)的通信能耗和網(wǎng)絡(luò)的剩余能量。LEACH是一種自組織自適應(yīng)的路由協(xié)議，簇內(nèi)成員節(jié)點(diǎn)將數(shù)據(jù)發(fā)送給簇首，簇首對(duì)數(shù)據(jù)融合后將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。因?yàn)榇厥椎哪芎妮^大，可以通過每輪隨機(jī)的選取簇首來平均節(jié)點(diǎn)的能量消耗，達(dá)到能耗均衡的目的。

若設(shè)傳感器節(jié)點(diǎn)數(shù)為N，每輪的簇頭數(shù)為K，則每輪各簇的能耗[8]為

每輪的簇群總能耗為

Etotal=K·E[ECluster].

設(shè)傳感節(jié)點(diǎn)的初始能量為E0，傳感器網(wǎng)絡(luò)LEACH協(xié)議下模擬運(yùn)行了r輪，則第r輪后，網(wǎng)絡(luò)的剩余能量為

Eres=N·E0-r·Etotal.

當(dāng)節(jié)點(diǎn)的當(dāng)前剩余能量小于0，則表示該節(jié)點(diǎn)已經(jīng)死亡。

1.3 覆蓋率和能量綜合指數(shù)

本文綜合考慮網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)通信能耗參數(shù)，采用線性加權(quán)和法得到覆蓋率和能量綜合指數(shù)為

f=w1·Cov(Call)+w2·Eres.

(2)

其中，w1,w2為各子優(yōu)化目標(biāo)的權(quán)值且w1+w2=1。在對(duì)實(shí)際場(chǎng)景進(jìn)行覆蓋控制優(yōu)化時(shí)，可以通過改變子目標(biāo)的權(quán)重因子，實(shí)現(xiàn)不同的優(yōu)化要求。例如:當(dāng)權(quán)重因子w1>w2時(shí)，表示網(wǎng)絡(luò)覆蓋率在綜合覆蓋優(yōu)化中成為主要因素；反之，當(dāng)w1

2 改進(jìn)差分進(jìn)化算法

差分進(jìn)化(DE)算法[9]是隨機(jī)搜索算法，旨在從某一隨機(jī)產(chǎn)生的初始種群開始，按照變異、交叉和選擇三種操作規(guī)則下不斷迭代，保留優(yōu)良個(gè)體，淘汰劣質(zhì)個(gè)體，引導(dǎo)搜索過程向最優(yōu)解逼近。DE算法也可以融合其他智能算法，提高算法的尋優(yōu)特性。例如:文獻(xiàn)[10]提出的基于DE的魚群算法，該算法通過引入DE策略，克服人工魚群算法存在的收斂速度慢，精度差等不足。

算法的操作過程如下：

1)反學(xué)習(xí)方法初始化種群[11,12]

在種群初始化時(shí)采用反學(xué)習(xí)方法，可以增加初始種群解的多樣性，加快算法的全局收斂速度。設(shè)解向量的維數(shù)為D，種群數(shù)為NP，r為進(jìn)化代數(shù)，則每代的解向量可表示為

Xi,r=(X1i,r,X2i,r,…,XDi,r),i=1,2,…,NP.

設(shè)解向量的搜索空間為

種群初始解向量可表示為

初始解向量產(chǎn)生對(duì)應(yīng)的反向解可表示為

將初始解和方向解帶入式(2)，選取適應(yīng)度值較大的個(gè)體作為初始種群的解向量。

2)種群變異

種群變異策略是從父代種群中根據(jù)變異算子生成新個(gè)體。新個(gè)體解向量由下式產(chǎn)生

Vi,r+1=Xa,r+F·(Xb,r-Xc,r).

(3)

其中，整數(shù)a,b,c∈[1,NP]且和當(dāng)前個(gè)體i互不相同。本文采用文獻(xiàn)[13]提出的變異因子F的自適應(yīng)調(diào)整策略，有利于始終保持種群的多樣性，加強(qiáng)局部搜索能力和收斂速度。

3)種群交叉

種群交叉策略是新舊個(gè)體按照交叉概率交換部分元素，形成新的個(gè)體。新個(gè)體解向量可由下式產(chǎn)生

Ui,r+1=(U1i,r+1,U2i,r+1,…,UDi,r+1),i=1,2,…,NP,

(4)

其中，CR為交叉概率。

4)種群選擇

將經(jīng)過變異，交叉操作得到Ui,r和父代Xi,r，運(yùn)用最優(yōu)保存策略選擇適應(yīng)度值較大的個(gè)體，進(jìn)而成為r+1的父代

(5)

5)人工蜂群搜索策略

DE算法在進(jìn)化中后期, 由于種群多樣性的降低, 當(dāng)優(yōu)化復(fù)雜的多峰問題時(shí), 如果有個(gè)體陷入局部最優(yōu)跳不出去, 則它會(huì)將附近的個(gè)體向局部最優(yōu)區(qū)域引導(dǎo);當(dāng)很多個(gè)體陷入局部最優(yōu)區(qū)域時(shí),容易出現(xiàn)早熟現(xiàn)象。針對(duì)上述DE算法的缺陷，本文引入文獻(xiàn)[11]提出的人工蜂群搜索策略。在該策略中，新的候選解向種群中隨機(jī)選擇的個(gè)體移動(dòng),由于選擇的隨機(jī)性, 適應(yīng)值好的個(gè)體和適應(yīng)值差的個(gè)體被選擇的概率是相同的，從而使種群中的個(gè)體盡快跳出局部最優(yōu)點(diǎn),達(dá)到避免早熟的目的。

3 實(shí)驗(yàn)仿真

為了驗(yàn)證本文提出的覆蓋優(yōu)化策略的有效性，設(shè)計(jì)了Matlab仿真程序，并將DE和改進(jìn)DE算法對(duì)優(yōu)化策略的仿真結(jié)果進(jìn)行對(duì)比。各項(xiàng)實(shí)驗(yàn)參數(shù)如下：算法迭代次數(shù)rmax為900；目標(biāo)區(qū)域范圍為20 m×20 m；傳感器節(jié)點(diǎn)數(shù)為60個(gè)；交叉概率為40 %；節(jié)點(diǎn)檢測(cè)概率減小速率為50 %；節(jié)點(diǎn)感知概率閾值為30 %；節(jié)點(diǎn)檢測(cè)可靠范圍Re為1 m；LEACH協(xié)議模擬通信輪數(shù)為400;節(jié)點(diǎn)初始能量E0為0.3 J;Sink節(jié)點(diǎn)的坐標(biāo)為(10,10)m;覆蓋率優(yōu)化系數(shù)w1為0.3;網(wǎng)絡(luò)剩余能量?jī)?yōu)化系數(shù)w2為0.7。

圖1為運(yùn)用DE和改進(jìn)DE算法對(duì)覆蓋率和能量綜合指數(shù)的仿真結(jié)果對(duì)比圖。由圖1可知，DE算法在290代時(shí)陷入了早熟收斂，最優(yōu)值維持在6.109直到迭代結(jié)束。改進(jìn)DE算法相較于DE算法最優(yōu)值搜索速率更快，在迭代期間沒有陷入早熟，迭代結(jié)束時(shí)最優(yōu)值為6.184。

圖1 改進(jìn)DE與DE算法迭代過程Fig 1 Iterative process of improved DE algorithm and conventional DE algorithm

圖2、圖3分別為經(jīng)過DE算法和改進(jìn)DE算法對(duì)優(yōu)化目標(biāo)迭代得到的最優(yōu)節(jié)點(diǎn)分布在LEACH仿真下區(qū)域剩余能量和仿真輪數(shù)的關(guān)系。由圖2、圖3可知，經(jīng)DE算法得到的最優(yōu)節(jié)點(diǎn)分布在LEACH仿真輪數(shù)為400時(shí)區(qū)域能量為8.4 J，而經(jīng)改進(jìn)DE算法得到的最優(yōu)節(jié)點(diǎn)分布對(duì)應(yīng)的區(qū)域能量則為8.6 J，可見改進(jìn)DE算法的仿真結(jié)果優(yōu)于DE算法。若假設(shè)投放到區(qū)域的節(jié)點(diǎn)數(shù)量增多，節(jié)點(diǎn)的能耗參數(shù)加大，由上二種算法得到的區(qū)域能量差值則會(huì)更大。圖4、圖5分別為經(jīng)DE算法和改進(jìn)經(jīng)DE算法得到的最優(yōu)節(jié)點(diǎn)在區(qū)域中的分布。由圖4、圖5可知，經(jīng)改進(jìn)DE算法得到的節(jié)點(diǎn)在區(qū)域中分布地更加均勻，節(jié)點(diǎn)相互重疊區(qū)域更少，有利于覆蓋率增加和網(wǎng)絡(luò)的能量均衡。

圖2 LEACH仿真下DE算法區(qū)域剩余能量和輪數(shù)關(guān)系Fig 2 Relation between regional residual energy and round number of conventional DE algorithm simulated by LEACH

圖3 LEACH仿真下改進(jìn)DE算法區(qū)域剩余能量和輪數(shù)關(guān)系Fig 3 Relation between regional residual energy and round number of improved DE algorithm simulated by LEACH

圖4 DE算法最優(yōu)節(jié)點(diǎn)分布Fig 4 The optimal distribution of nodes of conventional DE algorithm

圖5 改進(jìn)DE算法最優(yōu)節(jié)點(diǎn)分布Fig 5 The optimal distribution of nodes of improved DE algorithm

4 結(jié) 論

本文提出了一種基于節(jié)點(diǎn)的動(dòng)態(tài)通信能耗和網(wǎng)絡(luò)覆蓋率的多目標(biāo)覆蓋優(yōu)化策略。該優(yōu)化策略既能使網(wǎng)絡(luò)達(dá)到較高覆蓋率，又能保證網(wǎng)絡(luò)的能耗動(dòng)態(tài)均衡,覆蓋和能量的綜合優(yōu)化函數(shù)值達(dá)到了6.184,有效克服了早熟現(xiàn)象，實(shí)現(xiàn)了網(wǎng)絡(luò)動(dòng)態(tài)能耗均衡和覆蓋優(yōu)化的雙重目標(biāo)。

[1] 劉維亭,范洲遠(yuǎn).基于混沌粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].計(jì)算機(jī)應(yīng)用,2011,31(2):338-340.

[2] 張 斌,毛劍琳,李海平,等.群混合算法應(yīng)用于異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的優(yōu)化部署[J].計(jì)算機(jī)應(yīng)用,2012,32(5):1228-1231.

[3] 黃瑜岳,李克清.基于人工魚群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋

優(yōu)化[J].計(jì)算機(jī)應(yīng)用研究,2013,30(2):554-556.

[4] 梁 天,周 暉,謝 靜,等.無(wú)線傳感器網(wǎng)絡(luò)的多目標(biāo)覆蓋控制策略[J].傳感技術(shù)學(xué)報(bào),2010,23(7):994-999.

[5] Heinzelman W R,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications,2002,1(4):660-670.

[6] 張?jiān)浦?吳成東,程 龍,等.確定性空間的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署策略研究[J].控制與決策，2010,25(11):1625-1629.

[7] 靳立忠,常桂然,賈 杰,等.基于差分進(jìn)化算法的移動(dòng)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的分布優(yōu)化[J].控制與決策,2010,25(12):1857-1860.

[8] Gamwarige S,Kulasekere C.Performance analysis of the EDCR algorithm in a distributed wireless sensor networks[C]∥2006 IFIP International Conference on Wireless and Optical Communications Networks,2006:1-5.

[9] Stron R,Price K.Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.

[10] 張大斌，楊添柔，溫 梅.基于差分進(jìn)化的魚群算法及其函數(shù)優(yōu)化應(yīng)用[J].計(jì)算機(jī)工程,2013,39(5):18-22.

[11] 黃玲玲,劉三陽(yáng),高衛(wèi)峰.具有人工蜂群搜索策略的差分進(jìn)化算法[J].控制與決策,2012,27(11):1644-1648.

[12] 高衛(wèi)峰,劉三陽(yáng),黃玲玲.受啟發(fā)的人工蜂群算法在全局優(yōu)化問題中的應(yīng)用[J].電子學(xué)報(bào),2012,40(12):2309-2316.

[13] 余 兵.差分進(jìn)化算法及其應(yīng)用[D].西安：西安工程大學(xué),2007.

Application of a multi-objective coverage optimization strategy in WSNs*

CHEN Shu, QIAN Cheng

(School of IoT Engineering,Jiangnan University,Wuxi 214122,China)

Aiming at most energy equilibrium coverage strategy is based on insufficiency of energy consumption of static perception of node mostly in WSNs,a multi-target coverage optimization strategy is brought forward based on dynamic energy consumption and network coverage rate based on node.The strategy introduces dynamic routing protocol to coverage control optimization compute the dynamic energy consumption and the residual energy of the network,establish optimal function which evaiuate on coverage and energy comprehensive index combined with area coverage rate.Improved differential evolution algorithm and differential evolution algorithm are used for simulation and use result of coverage result to verify effectiveness of strategy.Simulation result shows that the coverage optimization strategy can achieve high coverage rate and guarantee dynamic balance of network energy consumption at the same time.In addition,in comparison with the improved differential evolution algorithm and the conventional differential evolution algorithm,the improved differential evolution algorithm overcomes prematurity value of comprehensive optimization of coverage and energy is more higher,which reaches 6.184 function.

wireless sensor networks(WSNs); energy balance; dynamic routing protocol; network coverage; differential evolution algorithm

10.13873/J.1000—9787(2014)10—0151—04

2014—01—10

江蘇省六大人才高峰資助項(xiàng)目(2012—WLW—006)；國(guó)家自然科學(xué)基金資助項(xiàng)目(21206053)

TP 273

A

1000—9787(2014)10—0151—04

陳 樹(1969-)，男，江蘇淮安人，副教授，主要從事過程控制與優(yōu)化、現(xiàn)場(chǎng)總線與控制技術(shù)、無(wú)線傳感器網(wǎng)絡(luò)與通信等研究工作。