基于Memetic算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化

陳偉佳，關(guān) 健

(1.閩江學(xué)院 數(shù)學(xué)系，福建 福州350108;2.閩江學(xué)院 現(xiàn)代教育技術(shù)中心，福建 福州350108)

無線傳感網(wǎng)絡(luò)(WSNs)在軍工和民用領(lǐng)域有著廣泛的應(yīng)用，如戰(zhàn)場偵察、機械故障診斷、生物檢測、家庭安防等［1］.由于無線傳感網(wǎng)絡(luò)通常應(yīng)用在偏遠無人值守的地方、電池更換不便，所以能耗控制是無線傳感網(wǎng)絡(luò)應(yīng)用一個重要的研究方向.由于無線傳感網(wǎng)絡(luò)節(jié)點的高密度部署會帶來大量的節(jié)點冗余，所以需要進行網(wǎng)絡(luò)覆蓋優(yōu)化，從大量的傳感節(jié)點中合理地選取一組節(jié)點進入工作狀態(tài)，以保證區(qū)域充分覆蓋.覆蓋優(yōu)化通過降低網(wǎng)絡(luò)冗余，節(jié)省了能源并延長了網(wǎng)絡(luò)的生存時間，是一種非常有效的能耗控制技術(shù).

近年來，學(xué)者們陸續(xù)提出不同的智能優(yōu)化算法求解無線傳感網(wǎng)絡(luò)的覆蓋優(yōu)化問題，如遺傳算法［2-3］、粒子群算法［4-5］、魚群算法［6］等.遺傳算法(GA)具有搜索速度快、并行搜索能力強的特點，但是容易陷入“早熟”收斂和局部最優(yōu)，不利于找到全局最優(yōu)解.禁忌搜索算法［7］(TS)具有較強的“爬山”能力，在搜索過程中可以接受劣解，從而跳出局部最優(yōu)解、轉(zhuǎn)向其他區(qū)域搜索更好的解或全局最優(yōu)解，但收斂速度慢，較難滿足動態(tài)節(jié)點選取的實時性要求.

Memetic算法是一種將全局尋優(yōu)與局部搜索相結(jié)合的算法框架［8］，兼顧廣度和深度.基于Memetic算法框架，融合了遺傳算法和禁忌算法，采用禁忌搜索算法作為局部搜索來增強遺傳算法的搜索能力，并通過改進目標函數(shù)值的計算公式來提高算法的運算速度，同時利用隨機和貪婪的策略構(gòu)造較優(yōu)的初始種群，仿真實驗表明該算法是可行、有效的.

1 WSNs覆蓋模型

假定在一個形狀規(guī)則的二維監(jiān)測區(qū)域中投放N個傳感節(jié)點，各傳感節(jié)點參數(shù)相同、坐標可知且相互獨立.

定義1監(jiān)測區(qū)域離散化為m×n個像素，則整個監(jiān)測區(qū)域記為像素集A={(x，y)|x∈{1，2，…，m}，y∈{1，2，…，n}}，(x，y)為像素點.

定義2傳感節(jié)點ci的坐標為(xi，yi)，有效感知半徑為r，則該傳感節(jié)點記為圓ci={xi，yi，r}，i∈{1，2，…，N}，所有節(jié)點記為C={c1，c2，…，cN}.

1.1 網(wǎng)絡(luò)節(jié)點利用率

用布爾向量S={s1，s2，…，si，…，sN}標志各傳感節(jié)點的狀態(tài)，si=1表示節(jié)點ci處于工作狀態(tài)，si=0表示節(jié)點ci處于休眠狀態(tài)，則網(wǎng)絡(luò)節(jié)點利用率

1.2 網(wǎng)絡(luò)有效覆蓋率

像素點(x，y)被傳感節(jié)點ci覆蓋的事件記為hi(x，y)，i∈{1，2，…，N}.當像素點(x，y)與傳感節(jié)點ci圓心的距離不大于半徑r且傳感節(jié)點ci處于工作狀態(tài)時，像素點(x，y)被傳感節(jié)點ci覆蓋，記P{hi(x，y)}=1，否則像素點(x，y)未被傳感節(jié)點ci覆蓋，記P{hi(x，y)}=0.事件hi發(fā)生的概率P{hi(x，y)}為一個二值函數(shù):

像素點(x，y)被節(jié)點集C中各節(jié)點覆蓋的事件是相互獨立的，則(x，y)被節(jié)點集C覆蓋的概率

傳感節(jié)點集C中工作節(jié)點所覆蓋的像素點之和即為該節(jié)點集的覆蓋區(qū)域，記為NA(C)，有

則網(wǎng)絡(luò)有效覆蓋率

1.3 覆蓋優(yōu)化數(shù)學(xué)模型

WSNs覆蓋優(yōu)化的目標是在保證網(wǎng)絡(luò)有效覆蓋率盡可能大的情況下努力減少節(jié)點的利用率，可以通過加權(quán)將有效覆蓋率和節(jié)點利用率兩個子目標函數(shù)轉(zhuǎn)化為總體目標函數(shù)，作為算法求解的適應(yīng)值，定義為

其中，S為節(jié)點狀態(tài)的向量，ω1和ω2為兩個子目標函數(shù)對應(yīng)的權(quán)值，ω1，ω2∈(0，1)且ω1+ω2=1.

2 基于Memetic框架的覆蓋優(yōu)化算法

Memetic算法是群體全局優(yōu)化算法和局部優(yōu)化算法的結(jié)合.基于Memetic算法框架，采用遺傳算法作為全局優(yōu)化策略進行廣度搜索，引入禁忌算法作為局部優(yōu)化策略進行深度搜索.

算法1:

①利用算法2產(chǎn)生一個較優(yōu)的初始種群，計算各個體的適應(yīng)值;

②根據(jù)適應(yīng)值，采用輪盤賭選法從群體中選出優(yōu)勝的個體作為父母;

③隨機選擇一個交叉點，根據(jù)交叉率將父母在該點前的基因進行互換，生成兩個新的子個體，期望父母將有益基因組合在一起遺傳給子個體;

④根據(jù)變異率對子個體的個別基因進行變異，維持群體的多樣性;

⑤用算法3對新的子個體進行局部優(yōu)化;

⑥如果子個體的適應(yīng)值優(yōu)于種群中最差個體的適應(yīng)值，用子個體替換最差種群中的個體，完成種群的更新，實現(xiàn)優(yōu)勝劣汰;

⑦判斷是否滿足算法終止條件，若是，結(jié)束算法，否則轉(zhuǎn)第②步.

Memetic利用遺傳算法，選擇質(zhì)量較優(yōu)的兩個個體，通過交叉操作可將兩個體的優(yōu)良部分組合產(chǎn)生更加優(yōu)秀的個體.但Memetic不局限于單純的遺傳算法，在每次交叉和變異后均進行局部搜索，及早剔除不良個體、優(yōu)化種群結(jié)構(gòu)，加快了算法的收斂能力.

2.1 編碼和鄰域結(jié)構(gòu)

采用最簡單的二進制編碼表示問題的解，1表示傳感節(jié)點處于工作狀態(tài)，0表示傳感節(jié)點處于休眠狀態(tài)，即節(jié)點狀態(tài)的標志向量S.鄰域集采用1-變換的方法進行構(gòu)造［9］，設(shè)一個解為S=(s1，s2，…，si，…，sN)，si∈{0，1}，i=1，2，…，N，則該解的鄰域集為NS(S)={Si|Si=(s1，s2，…，1-si，si+1，…，sN)，i=1，2，…，N}，即僅有一個節(jié)點狀態(tài)發(fā)生變換.

2.2 初始種群的構(gòu)造

利用隨機和貪婪的策略構(gòu)造一個質(zhì)量較好的初始種群.為了說明該貪婪策略的思想，做如下的定義:

定義3傳感節(jié)點ci所覆蓋的區(qū)域即為與ci圓心距離不大于r的像素集，記為

覆蓋區(qū)域的大小記為|A(ci)|.

定義4傳感節(jié)點ci的鄰居即為與ci圓心距離不大于2r的節(jié)點集，記為

ci的鄰居的個數(shù)記為|N(ci)|.

隨機和貪婪策略的主要思想:首先，將所有N個傳感節(jié)點處于休眠狀態(tài).其次，在N個傳感節(jié)點中隨機選擇一個節(jié)點，從該節(jié)點和它的鄰居節(jié)點中選擇一個覆蓋區(qū)域最大的節(jié)點處于工作狀態(tài).接著，將該覆蓋區(qū)域最大的節(jié)點和與它距離小于一定值的鄰居節(jié)點鎖定.然后，繼續(xù)從未被鎖定的節(jié)點中隨機選擇一個節(jié)點，從該節(jié)點和它的鄰居節(jié)點中選擇一個覆蓋區(qū)域最大的節(jié)點處于工作狀態(tài)，鎖定該覆蓋區(qū)域最大的節(jié)點和它的鄰居中與它距離小于一定值的節(jié)點，直到所有節(jié)點都被鎖定，完成初始個體的構(gòu)造.

算法2:

①初始化個體k的節(jié)點狀態(tài)標志向量Sk={0，0，…，0}，所有N個傳感節(jié)點未被鎖定;

②從未被鎖定的節(jié)點中隨機選擇一個節(jié)點ci，從ci和N(ci)中選擇一個覆蓋區(qū)域最大的節(jié)點cj，并讓它處于工作狀態(tài)sj=1;

③鎖定cj與N(cj)中與cj距離小于一定值的節(jié)點;④判斷是否還有未被鎖定的節(jié)點，若有，轉(zhuǎn)第②步，否則，初始個體的構(gòu)造完成，轉(zhuǎn)第⑤步;⑤判斷是否達到種群所需的個體數(shù)，若是，轉(zhuǎn)第①步，否則，初始種群構(gòu)造完成，結(jié)束算法.

2.3 禁忌算法

禁忌算法具有強大的局部搜索能力，收斂速度快，最大特點是可以接受劣解，從而跳出局部最優(yōu)，引入禁忌準則來避免迂回搜索，并通過特赦準則來赦免一些被禁忌的優(yōu)良解，進而探索更優(yōu)的解［10］.

算法3:

①初始化算法參數(shù)，選擇一個個體的狀態(tài)標志向量作為初始解S0;

②令當前解Snow=S0，全局最優(yōu)解Sbest=S0，置禁忌表為空;

③構(gòu)造Snow的鄰域解集NS(Snow)并計算各鄰域解的適應(yīng)值，如果禁忌表滿了，則將表中最早保存的解移除;

④按適應(yīng)值從高到低對鄰域解進行排序為{S1，S2，…，SN}，令i=1;

⑤特赦準則判斷，如果鄰域解Si的適應(yīng)值大于全局最優(yōu)解Sbest的適應(yīng)值，則將Si對應(yīng)Snow狀態(tài)發(fā)生變換的節(jié)點加入禁忌表，Snow=Si，Sbest=Si，轉(zhuǎn)第③步，否則轉(zhuǎn)第⑥步;

⑥禁忌準則判斷，如果鄰域解Si對應(yīng)Snow狀態(tài)發(fā)生變換的節(jié)點不在禁忌表中，轉(zhuǎn)第⑦步，否則，i=i+1，轉(zhuǎn)第⑥步;

⑦將Si對應(yīng)Snow狀態(tài)發(fā)生變換的節(jié)點加入禁忌表，Snow=Si，如果鄰域解Si的適應(yīng)值大于全局最優(yōu)解Sbest的適應(yīng)值，則Sbest=Si，轉(zhuǎn)第⑧步，否則直接轉(zhuǎn)第⑧步;

⑧判斷是否滿足算法終止條件，若是，則輸出全局最優(yōu)解Sbest，結(jié)束算法，否則轉(zhuǎn)第③步.

2.4 改進的適應(yīng)值計算

禁忌算法對一個解的所有鄰域進行搜索，需要計算N次目標函數(shù)值.然而，利用式(4)和式(5)對目標函數(shù)中的網(wǎng)絡(luò)有效覆蓋率進行一次計算，所需時間為O(N×m×n).因此，對一個解進行一次鄰域搜索所需時間為O(N2×m×n)，耗費的時間代價非常大.根據(jù)鄰域的結(jié)構(gòu)特點可知，解S與鄰域解Si對比只有一個節(jié)點ci的狀態(tài)發(fā)生了變換，鄰域解Si的適應(yīng)值可由解S的適應(yīng)值加上發(fā)生變換帶來的適應(yīng)值差異Δ，改進適應(yīng)值計算公式為

關(guān)于適應(yīng)值差異Δ，主要需考慮ci所覆蓋的區(qū)域A(ci)被ci的鄰居N(ci)中所有工作的節(jié)點聯(lián)合覆蓋的情況，記為NA(N(ci))，有

其中，hj(x，y)為像素點(x，y)∈A(ci)被節(jié)點cj∈N(ci)所覆蓋的事件.

如果ci的狀態(tài)由工作變?yōu)樾菝?，?/p>

如果ci的狀態(tài)由休眠變?yōu)楣ぷ鳎?/p>

由式(9)可知，利用改進的適應(yīng)值計算公式進行一次鄰域搜索所需時間為O(N×|N(ci)|×|A(ci)|)，而|N(ci)|＜N，|A(ci)|?(m×n)，大大節(jié)省了運算時間.

3 仿真實驗與分析

實驗環(huán)境參照文獻［4］設(shè)置:監(jiān)測區(qū)域為100 m×100 m，將其離散為100×100個像素，節(jié)點感知半徑為11.5 m.首先，確定性部署39個節(jié)點以正六邊形結(jié)構(gòu)最優(yōu)化分布于監(jiān)測區(qū)域，如圖1所示.然后，再隨機部署61個節(jié)點于該監(jiān)測區(qū)域，如圖2所示.適應(yīng)值函數(shù)式(7)中，ω1=0.1，ω2=0.9.

圖1 最優(yōu)節(jié)點分布Fig.1 The optimal distribution of nodes

圖2 初始節(jié)點分布Fig.2 The initial distribution of nodes

Memetic算法的參數(shù)設(shè)置如下:種群數(shù)量為5，交叉概率為0.8，變異概率為0.05，達到100次迭代終止迭代，TS的最大迭代次數(shù)為20，禁忌長度為10.圖3中(a)、(b)、(c)分別為Memetic算法優(yōu)化過程第1 s，3 s和5 s的節(jié)點分布情況.整個優(yōu)化過程節(jié)點分布逐步趨于最優(yōu)，第5 s時的節(jié)點分布圖3(c)已經(jīng)非常接近圖1中的最優(yōu)節(jié)點分布，覆蓋率為99.76%，節(jié)點利用率為39%.結(jié)果表明，Memetic算法能快速收斂于優(yōu)秀解、達到優(yōu)化覆蓋的目的，是一種有效的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化算法.

圖3 M emetic優(yōu)化過程的節(jié)點分布Fig.3 The distributions of nodes in the optim ization process of Memetic

為了驗證算法的優(yōu)越性，在相同的仿真環(huán)境下，采用遺傳算法和禁忌算法對無線傳感網(wǎng)絡(luò)覆蓋進行優(yōu)化對比，仿真結(jié)果如圖4所示.從圖4中可以看出，在相同的運行時間下，Memetic算法得到的目標函數(shù)值高于GA和TS.為獲得超過0.95的目標函數(shù)值，Memetic算法需要運行的時間小于5 s，而GA算法和TS算法需要運行的時間分別高于50 s和60 s.因此，3種算法中，Memetic算法的性能優(yōu)于其他兩種算法，是一種性能更優(yōu)的覆蓋優(yōu)化算法.

圖4 目標函數(shù)值隨運行時間的變化曲線Fig.4 The change curve of objective function value and time

4 結(jié)語

提出了基于Memetic算法的覆蓋優(yōu)化.算法考慮了解的質(zhì)量和多樣性，利用相鄰節(jié)點間的區(qū)域覆蓋關(guān)系，提高了目標函數(shù)值的計算速度.與遺傳算法和禁忌算法對比，Memetic算法的收斂結(jié)果好、速度快，在保證盡可能高的網(wǎng)絡(luò)覆蓋率下減少了節(jié)點的利用率，有效解決了高密度部署的WSNs工作節(jié)點集的選取問題.

［1］Liu Y，Suo L，Sun D，et al.A virtual square grid-based coverage algorithm of redundant node for wireless sensor network［J］.Journal of Network and Computer Applications，2013，36(2):811-817.

［2］賈杰，陳劍，常桂然.無線傳感器網(wǎng)絡(luò)中基于遺傳算法的優(yōu)化覆蓋機制［J］.控制與決策，2007，22(11):1289-1292.［3］林梅金，蘇彩紅，王飛.無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法研究［J］.計算機仿真，2011，28(3):178-181.

［4］林祝亮，馮遠靜.基于粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化策略［J］.計算機仿真，2009，26(4):190-193.

［5］沈海洋.基于遺傳PSO的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化算法研究［J］.微電子學(xué)與計算機，2013，30(3):148-151.

［6］周利民，楊科華，周攀.基于魚群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略［J］.計算機應(yīng)用研究，2010，27(6):2276-2279.

［7］胡峻浩，劉興長，談昨非.基于禁忌算法的無線傳感器網(wǎng)絡(luò)PEGASIS算法改進［J］.后勤工程學(xué)院學(xué)報，2013，29(4):91-96.

［8］魏心泉，王堅.多目標資源優(yōu)化分配問題的Memetic算法［J］.控制與決策，2014，29(5):809-814.

［9］林耿，朱文興.多維背包問題的變鄰域填充函數(shù)算法［J］.福州大學(xué)學(xué)報:自然科學(xué)版，2012，40(1):14-21.

［10］劉霞，齊歡.最小-最大車輛路徑問題的禁忌搜索算法［J］.系統(tǒng)工程，2007，25(1):49-51.