基于遺傳算法優化的WSN覆蓋控制算法

李向峰，席志紅，李 爽

(1.哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001；2.衛星導航系統與裝備技術國家重點實驗室，河北 石家莊050081)

0 引言

隨著通信技術、嵌入式軟件技術和傳感器技術的高速發展與應用，WSN已經發展到第四代技術[1]，作為物聯網的關鍵組成部分，已經廣泛應用于軍事領域、環境監測、自然災害預報、醫療健康和智能家居等領域[2-4]。覆蓋控制是影響整個網絡服務質量、感知信息能力、網絡能耗和壽命的直接因素。因此，降低因為節點電池耗盡而出現的網絡區域覆蓋漏洞，高效利用節點能量和延長網絡生命周期保障監測區域的有效覆蓋是無線傳感器網絡十分重要的研究課題[5]。

無線傳感器網絡有效覆蓋控制是保障服務質量(QoS)的首要條件，在部署節點時通常會使用冗余節點來保障目標區域的完全覆蓋，這就形成了k重覆蓋問題[6]。文獻[7]使用文化基因(Memetic)算法產生平衡簇來均衡每個節點的能量消耗，避免覆蓋漏洞過早出現，但是使用了部分移動節點，并沒有考慮節點運動所消耗的附加能量[8-10]。文獻[11]基于(m，k)-Gur Game算法改進的休眠策略，通過交替性地休眠喚醒節點均勻節點能耗，避免某些節點過度使用提前死亡造成覆蓋漏洞，但是其仍然沒有避免WSN網絡產生大量冗余數據。

本文基于Memetic算法框架結構對遺傳算法(Genetic Algorithm，GA)進行改進，在遺傳算法的基礎上結合針對WSN提出的局部搜索策略(Local Search Algorithm，LSA)進一步優化算法性能，盡可能使用最少的節點保障監測區域的完全覆蓋。本文算法中遺傳操作主要完成種群迭代評估覆蓋率，局部搜索算法在保障覆蓋率不下降的同時進一步減小需要激活的節點數量，提高適應度。

1 網絡模型和相關理論

假設普通節點、匯聚節點和監測目標點(Monitored Target Points，MTP)在部署之后都是靜止的，節點都是同構類型，它們具有相同的初始能量、數據處理能力和感知半徑。當MTP在某個節點感知半徑范圍Rs內時，則認為該節點可以監測到此MTP，如圖1所示，每一個MTP都至少被一個節點覆蓋。為了簡化實驗復雜性，本文使用文獻[12]中研究測試的感知半徑范圍Rs為17.675 m。節點將監測到的數據發送給簇、頭，簇、頭接收到數據后再通過直接發送或者多跳的方式發送給匯聚節點[13-14]。

圖1 無線傳感器網絡模型

1.1 感應覆蓋模型

基于二元感知模型構建WSN的感知覆蓋模型，將傳感器節點定義為S={s1，s2，s3，…，sN}，N為節點總數。監測目標定義為T={t1，t2，t3，…，tM}，M為MTP的數量。定義MTP二進制覆蓋變量Gi，j為：

(1)

式中，E為節點si當前能量，當si和tj之間的距離小于等于Rs時，則tj被si所監測，令Gi，j=1。當tj在v個節點時，定義Tj表示目標監測節點tj是否被監測，當Tj=1時，表示tj被監測。

Tj=G1，j∪G2，j∪…∪Gv，j。

(2)

集合覆蓋問題(Set Covering Problem，SCP)是經典的NP-Complete問題，SCP調度節點使某一組傳感器節點保障目標區域中每一個MTP都至少被一個節點所監測。SCP數學描述如下：

(3)

(4)

式中，cost(i)表示激活節點si的成本代價，用si=1表示節點處激活狀態，si=0表示處于休眠狀態。式(3)表示在最優狀態下，激活使用最少的節點，以達到代價成本最低，但是其受式(4)的約束，必須保證每一個MTP都至少被一個節點所覆蓋。求解SCP問題的過程就是上述2個公式相互制約、互相博弈的過程。

1.2 遺傳算法

在進行遺傳操作之前首先要得到一個初始種群，為了得到初始種群，根據遺傳算法的相關理論進行如下定義：

定義1 基因(Gene)：傳感器節點si的取值稱為一個基因或者等位基因，為了方便算法的實施采用二進制編碼。si=1表示傳感器節點處于激活狀態；si=0表示傳感器節點處于休眠狀態。

定義2 染色體(Chromosome)：將若干基因的集合稱為染色體或者個體，使用二進制字符串表示。假設在區域內分布N個傳感器節點，則這N節點的二進制編碼構成一個染色體。

定義3 種群(Population)：在同一區域內若干同類個體構成種群，在初始種群的基礎上進行遺傳操作得到新一代的種群，它是進化的基本單位。

第一代初始種群采用隨機產生方法生成，每一個節點在初始時隨機地選擇激活或者休眠狀態，所以理論上處于激活和休眠狀態的節點數量各占一半。一個種群模型示例如圖2所示，根據定義1，基因li，j表示染色體i中第j個節點sj的狀態，li，j為1表示節點sj激活狀態，為0表示休眠，每個染色體的長度為N。

圖2 種群模型示例

根據上述初始節點取值和染色體的定義可知，每一個染色體的編碼都由一串二進制代碼組成。染色體編碼示例如圖3所示，假設共有15個傳感器節點用于感測7個目標監測點MTP，顯然圖中存在k重覆蓋問題，通過遺傳算法操作可以達到激活最少數量的節點覆蓋所有監測點。這里使用9個節點(s1，s3，s7，s8，s9，s12，s13，s14，s15)就可以覆蓋所有的7個監測點，剩下的6個(s2，s4，s5，s6，s10，s11)為冗余節點。根據上面定義的基因模型，就可以方便地將圖3中給出的示例染色體用二進制字符串“101000011001110”來表示這15個等位基因{l1，1，l1，2，l1，3，l1，4，l1，5，l1，6，l1，7，l1，8，l1，9}的編碼。

圖3 染色體編碼示例

1.3 選擇、交叉、變異運算

遺傳算法包含選擇、交叉和變異，通過多次種群選擇迭代減少冗余節點來提高適應度。選擇過程可以得到較好的復制品，但是不能產生新的個體，為了保持種群的多樣性，提高遺傳質量，必須引入新的個體。交叉操作是模仿生物的交配繁殖過程，確定適當的交叉率很重要。以交叉率Rc(0

圖4 交叉操作示意

2 改進遺傳算法

首先改進遺傳算法適應度函數，然后根據Memetic文化基因算法框架結構提出局部搜索策略，最后在遺傳算法的基礎之上結合局部搜索策略構成本文算。

2.1 適應度函數

適應度值的大小是遺傳操作中選擇個體的重要指標[19]。本文算法的目標是激活使用盡可能少的節點來實現最佳覆蓋率。對于每個節點，用覆蓋向量ci表示某一個特定節點si對每一個MTP的覆蓋情況，ci=[Gi，1，Gi，2，…，Gi，M]，其中si∈S。同樣，對于另一個傳感器節點sj∈S，覆蓋向量cj表示為cj=[Gj，1，Gj，2，…，Gj，M]，i≠j。通過布爾或運算，可以得到節點si和sj的綜合覆蓋變量ω(si，sj)定義為：

ω(si，sj)= [ci∪cj]=
[Gi，1∪Gj，1，Gi，2∪Gj，2，…，Gi，M∪Gj，M]。

(5)

用ω(si，sj)來確定每個MTP是否被節點si或者sj覆蓋。因此，推廣到某一個染色體k的綜合覆蓋向量ω(k)定義如下：

ω(k)=(lk，1c1)∪(lk，2c2)∪…∪(lk，NcN)。

(6)

將式(5)代入式(6)得：

(7)

通過將覆蓋評估過程簡化為二進制操作，可以大幅簡化CMACP協議計算的復雜性。可以通過以下公式計算染色體k的覆蓋率：

(8)

式中，‖ω(k)‖表示染色體k覆蓋的MTP數量。則染色體k的節點利用率可以通過以下公式計算：

(9)

f(k)=α1×(‖ω(k)‖)τ1-α2×(μ(k，s))τ2。

(10)

將式(8)和式(9)的染色體k覆蓋MTP數量ε(k)和節點利用率μ(k，s)代入式(10)得：

(11)

式中，α1和α2是加權系數；τ1和τ2是指數因子。由式(11)可以得到適應度函數f(k)隨著ε(k)的增大或μ(k，s)減少而增大，顯然，覆蓋MTP數量越多并且使用的節點數量越少則適應度越高，滿足SCP所描述的最佳模型式(3)和約束條件式(4)。如果染色體k具有較高的適應度值，則意味著其可以激活使用更少的節點來監測比其他染色體更多的MTP目標。在遺傳操作的過程中，每個染色體需要通過適應度函數進行計算排序，按照排序保留適應度最大的種群作為下一代的父本。通過適應度函數選擇精英種群，經過數代的迭代后將得到一個覆蓋率最大和適應度較高的種群。

2.2 局部搜索策略

Memetic算法中的局部搜索策略就有很高的靈活性，可以和不同的搜索策略相結合。基于無線傳感器網絡的特點和本文構建的二進制模型，改進了一種能優化染色體適應度的搜索策略。每一代染色體的遺傳操作完成后，通過局部搜索策略進一步提高染色體適應度。局部搜索算法的偽代碼描述如下：

本地搜索策略:步驟1:輸入種群Popk={chrom1,chrom2,…,chrompop_size}k,pop_size為種群大小。步驟2:設chromi是種,群Popk中第i-th的個體,N為chro-mi的長度。根據等位基因li,j定義可知,染色體chromi是由等位基因li,j組成的二進制字符串。?i,1≤j≤N.Fori=1topop_sizedo Forj=1toNdo ∥記錄值為1的等位基因 Ifthevalueofli,jisequaltoonethen Recordthealleleli,jinthearraysi. End EndEnd步驟3:Fory=1topop_sizedoLethbethelengthofSy.Forl=1tohdo fitness1=fit(chromy); Inchromy,lettheallelelv,htobezeroinSy.∥將等位基因置零 fitness2=fit(chromy); Iffitness1>fitness2then Letlv,hequaltoone. EndEndEnd步驟4:輸出最佳解種群Popk

該策略將每個等位基因li，j的值從1變為0，如果改變后覆蓋率不變則保留這個改變，如果覆蓋率下降則恢復。局部搜索方案遍歷所有的等位基因，盡可能地提高個體的適應度，并通過比較原始染色體和新染色體的適應度大小來確定是否保持修改。運行局部搜索策略后可以得到一個比原先適應度更高(至少等于)的種群。

其中Popk是具有pop_size個染色體的一個種群，chromi是種群中的一個染色體。令f(k)previous=fitness1，f(k)current=fitness2，經過局部搜索算法操作后，必然有f(k)previous≥f(k)current。搜索算法計算后可以得到新的適應度值f(k)：

f(k)=max{f(k)previous，f(k)current}。

(12)

運行遺傳算法和局部搜索策略后，可以得到初始激活節點集合Pactive和休眠節集合Psleep。CMACP算法可以通過執行局部搜索過程獲得更好的結果，加速算法收斂過程。

2.3 本文算法流程

綜上所述，改進的遺傳算法的適應度函數結合局部搜索構成本文算法，算法流程圖如圖5所示。

圖5 本文算法流程

本文算法的設計思路是在遺傳算法進行每一代的迭代后添加局部搜索策略對種群進一步優化。通過局部搜索策略對每一個等位基因進行搜索，尋找遺傳算法中遺漏未優化的冗余節點。如果發現冗余節點則對節點進行優化，進一步提高種群適應度，如此往復運行直到滿足適應度終止標準或者達到最大迭代次數進化過程終止適應度最大的種群為最優解。

3 仿真實驗及結果分析

本文仿真環境使用Matlab 8.1[20-21]平臺，設置在大小為100 m×100 m的區域內部署400個傳感器節點和64個MTP。通過與遺傳算法對比來測試局部搜索算法對提高適應度的有效性，根據本文算法處理流程，首先每一次迭代中先由遺傳算法得到一個初始種群，然后局部搜索算法負責進一步優化種群適應度后完成一次迭代，從中選出精英種群作為母本，最后經過多次迭代后得到一個較為理想的種群。遺傳算法和本文算法運行前節點和MTP的分布情況如圖6、圖7和圖8所示，分別表示經過遺傳算法和本文算法迭代40代后得到的最優初始種群覆蓋情況。

其中，數字表示傳感器節點序號，“○”表示節點的感知范圍，“*”表示 MTP監測點。從圖7和圖8中可以得出遺傳算法在初始覆蓋時使用的節點數量明顯比本文算法更多，說明遺傳算法的適應度并不高，選擇出的種群不是最優種群，進一步對比分析二者的適應度同樣驗證了這一結論，圖9對比了2種算法的初始適應度、平均適應度和最大適應度值。

圖6 400個節點，64個MTP均勻分布

圖7 遺傳算法40次迭代后初始覆蓋

圖8 本文算法40次迭代后初始覆蓋

圖9 GA算法和本文算法適應度值對比

在算法運行迭代之前，二者的初始適應度值幾乎相同，經過40次種群迭代之后，不論是平均適應度還是最大適應度，有局部搜索算法的本文算法都要比沒有的遺傳算法的適應度值都要高出近一倍。更高的適應度必然在網絡壽命和覆蓋率上有更好的表現，圖10對比了2種算法的覆蓋率和節點死亡的變化情況。

圖10 GA算法和本文算法覆蓋率和節點死亡變化對比

圖10(a)顯示CAMCP算法比遺傳算法維持100%覆蓋MTP運行的輪數更多，分別為1 815輪和1 166輪，100%覆蓋輪數提高了55.66%，整體網絡壽命分別為5 134輪和3 984輪，網絡壽命提高28.87%。從圖10(b)中可以看出，遺傳算法的節點死亡速度更快，這是因為遺傳算法的適應度并不高，仍然有冗余節點處于激活工作狀態，它們做重復性工作的同時也在消耗能量。從以上分析中可以得出，本文算法可以有效地進一步提高遺傳算法的適應度，延長100%覆蓋MTP的時間和網絡整體壽命。

4 結束語

本文基于Memetic算法框架結構在遺傳算法的基礎上構建了無線傳感器網絡覆蓋模型，結合局部搜索策略改進了遺傳算法。通過分析遺傳算法發現其存在過早收斂和適應度低的情況，并且為了保障初始覆蓋率而大量布置的傳感器節點造成了節點冗余，在WSN網絡運行時冗余傳感器節點又會產生大量的冗余數據進一步加重了WSN網絡的數據處理負擔增加能耗。本文算法針對提高遺傳算法適應度和規劃冗余節點2個方面進行優化，通過仿真實驗對比得出，與遺傳算法相比本文算法通過局部搜索將適應度值提高了近1倍，在保障100%覆蓋 MTP同時使用更少的節點，節點規劃更加合理，有效延長了100%覆蓋時間和整體網絡壽命。

[1] 陶志勇，蔣守鳳.基于模糊理論的無線傳感器網絡簇首選舉算法[J].計算機工程，2015，41(9)：115-119.

[2] 肖發遠，李好威.基于模糊理論的無線傳感器網絡路由優化算法[J].廣西師范大學學報，2017，35(1)：37-43.

[3] 曾東，熊飛.面向能耗控制的無線傳感器網絡節點協議優化[J].無線電通信技術，2014，40(1)：28-31.

[4] 熊煉，葉建光，劉曉彤.基于動態簇半徑的非均勻分簇算法[J].無線電通信技術，2017，43(1)：51-55.

[5] 徐晶晶，張欣慧，許必宵.無線傳感器網絡分簇算法綜述[J].計算機科學，2017，44(2)：31-37.

[6] MEENAKSHI Y，DANIEL A K.Performance Analysis of Approaches for Coverage Issues in WSN[C]∥2016 International Conference on Computing for Sustainable Global Development (INDIACom)，2016：782-787.

[7] MASOOD A，ATAUL A I，ISHTIAQ W，et al.A Memetic Algorithm Approach to Clustering inMobile Wireless Sensor Networks[C]∥Future Technologies Conference，2016：936-940.

[8] 湯杰，鄭霖.能耗均衡的無線傳感網絡不等環分層路由算法[J].無線電工程，2017，47(10)：12-16.

[9] XIAOHUI Y，MOHAMED E，HAMDY K E.Genetic Algorithm-based，Dynamic Clustering Method Towards Improved WSN Longevity[C]∥Journal of Network and Systems Management，2016：1-26.

[10] 戚玉濤，劉芳，常偉遠.求解多目標問題的 Memetic免疫優化算法[J].軟件學報，2013(7)：1529-1544.

[11] TIAGO S，CARLOS M，PAULO P A.Sleep-scheduling Scheme for Enhancing QoS and Network Coverage in IEEE 802.15.4 WSN[C]∥Factory Communication Systems,2015：1-4.

[12] GAO Y，WKRAM C H，Duan J，et al.A Novel Energy-aware Distributed Clustering Algorithm for Heterogeneous Wireless Sensor Networks in the Mobile Environment[J].Sensors，2015，15(12)：31108-31124.

[13] 馬簫雯，余翔，許未.基于LEACH的WSN路由算法研究[J].無線電通信技術，2013，39(2)：14-16.

[14] 孔令榮，王昊，莊濤.基于WSN的分簇路由協議研究與改進[J].無線電工程，2014，44(12)：48-51.

[15] SRINIVAS M，PATNAIK L M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J].IEEE Transactions on Systems Man & Cybernetics，2002，24 (4)：656-667.

[16] EIBEN A E，MICHALEWICZ Z，SCHOENAUER M，et al.Paraeter Control in Evolutionary Algorithms[J].In Parameter Setting in Evolutionary Algorithms，2007，54：19-46.

[17] 周杰.基于進化算法的大規模無線傳感器網絡覆蓋關鍵技術研究[D].北京：北京郵電大學，2015.

[18] 祁育仙.基于遺傳算法的無線傳感器網絡覆蓋控制研究[D].太原：太原理工大學，2015.

[19] YUAN Xiaohui，MOHAMED E，HAMDY K，et al. A Genetic Algorithm-Based，Dynamic Clustering Method Towards Improved WSN Longevity[J].Journal of Network and Systems Management，2017，25(1)：21-46.

[20] 薛定宇，陳陽.泉高等應用數學問題的MATLAB求解[M].北京：清華大學出版社，2008：264-325.

[21] 莫勒，喻文健.MATLAB數值計算(2013修訂版)[M].北京：機械工業出版社，2013：462-511.