陳 樹，錢 成

(江南大學 物聯網工程學院，江蘇 無錫 214122)

應用技術

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

陳 樹，錢 成

(江南大學 物聯網工程學院，江蘇 無錫 214122)

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

無線傳感器網絡; 能量均衡; 動態(tài)路由協議; 網絡覆蓋; 差分進化算法

0 引 言

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

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

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

1.1 網絡覆蓋率

假定區(qū)域為二維平面，擬在區(qū)域上投放n個傳感器節(jié)點。設ci=(xi,yi)為傳感器節(jié)點的坐標，則節(jié)點ci對網格點qj=(xj,yj)的感知概率[3]為

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

設目標區(qū)域被離散化為M×N個網格，每個網格的面積表示為1，則可得Call對整個監(jiān)測區(qū)域的覆蓋率

(1)

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

1.2 網絡節(jié)點通信能耗

運用LEACH協議對網絡節(jié)點間的通信進行模擬，得到節(jié)點的通信能耗和網絡的剩余能量。LEACH是一種自組織自適應的路由協議，簇內成員節(jié)點將數據發(fā)送給簇首，簇首對數據融合后將數據發(fā)送給Sink節(jié)點。因為簇首的能耗較大，可以通過每輪隨機的選取簇首來平均節(jié)點的能量消耗，達到能耗均衡的目的。

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

每輪的簇群總能耗為

Etotal=K·E[ECluster].

設傳感節(jié)點的初始能量為E0，傳感器網絡LEACH協議下模擬運行了r輪，則第r輪后，網絡的剩余能量為

Eres=N·E0-r·Etotal.

當節(jié)點的當前剩余能量小于0，則表示該節(jié)點已經死亡。

1.3 覆蓋率和能量綜合指數

本文綜合考慮網絡覆蓋率和網絡通信能耗參數，采用線性加權和法得到覆蓋率和能量綜合指數為

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

(2)

其中，w1,w2為各子優(yōu)化目標的權值且w1+w2=1。在對實際場景進行覆蓋控制優(yōu)化時，可以通過改變子目標的權重因子，實現不同的優(yōu)化要求。例如:當權重因子w1>w2時，表示網絡覆蓋率在綜合覆蓋優(yōu)化中成為主要因素；反之，當w1

2 改進差分進化算法

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

算法的操作過程如下：

1)反學習方法初始化種群[11,12]

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

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

設解向量的搜索空間為

種群初始解向量可表示為

初始解向量產生對應的反向解可表示為

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

2)種群變異

種群變異策略是從父代種群中根據變異算子生成新個體。新個體解向量由下式產生

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

(3)

其中，整數a,b,c∈[1,NP]且和當前個體i互不相同。本文采用文獻[13]提出的變異因子F的自適應調整策略，有利于始終保持種群的多樣性，加強局部搜索能力和收斂速度。

3)種群交叉

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

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

(4)

其中，CR為交叉概率。

4)種群選擇

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

(5)

5)人工蜂群搜索策略

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

3 實驗仿真

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

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

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

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

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

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

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

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

4 結 論

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

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

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

[3] 黃瑜岳,李克清.基于人工魚群算法的無線傳感器網絡覆蓋

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

[4] 梁 天,周 暉,謝 靜,等.無線傳感器網絡的多目標覆蓋控制策略[J].傳感技術學報,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é)點部署策略研究[J].控制與決策，2010,25(11):1625-1629.

[7] 靳立忠,常桂然,賈 杰,等.基于差分進化算法的移動傳感器網絡節(jié)點的分布優(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] 張大斌，楊添柔，溫 梅.基于差分進化的魚群算法及其函數優(yōu)化應用[J].計算機工程,2013,39(5):18-22.

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

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

[13] 余 兵.差分進化算法及其應用[D].西安：西安工程大學,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

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

TP 273

A

1000—9787(2014)10—0151—04

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