一種多目標的覆蓋優化策略在WSNs中的應用*

陳 樹，錢 成

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

應用技術

一種多目標的覆蓋優化策略在WSNs中的應用*

陳 樹，錢 成

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

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

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

0 引 言

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

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

1 覆蓋優化策略

1.1 網絡覆蓋率

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

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

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

(1)

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

1.2 網絡節點通信能耗

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

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

每輪的簇群總能耗為

Etotal=K·E[ECluster].

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

Eres=N·E0-r·Etotal.

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

1.3 覆蓋率和能量綜合指數

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

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

(2)

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

2 改進差分進化算法

差分進化(DE)算法[9]是隨機搜索算法，旨在從某一隨機產生的初始種群開始，按照變異、交叉和選擇三種操作規則下不斷迭代，保留優良個體，淘汰劣質個體，引導搜索過程向最優解逼近。DE算法也可以融合其他智能算法，提高算法的尋優特性。例如:文獻[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，運用最優保存策略選擇適應度值較大的個體，進而成為r+1的父代

(5)

5)人工蜂群搜索策略

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

3 實驗仿真

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

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

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

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

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

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

圖4 DE算法最優節點分布Fig 4 The optimal distribution of nodes of conventional DE algorithm

圖5 改進DE算法最優節點分布Fig 5 The optimal distribution of nodes of improved DE algorithm

4 結 論

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

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

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

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

優化[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] 張云洲,吳成東,程 龍,等.確定性空間的無線傳感器網絡節點部署策略研究[J].控制與決策，2010,25(11):1625-1629.

[7] 靳立忠,常桂然,賈 杰,等.基于差分進化算法的移動傳感器網絡節點的分布優化[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].計算機工程,2013,39(5):18-22.

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

[12] 高衛峰,劉三陽,黃玲玲.受啟發的人工蜂群算法在全局優化問題中的應用[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-)，男，江蘇淮安人，副教授，主要從事過程控制與優化、現場總線與控制技術、無線傳感器網絡與通信等研究工作。