復(fù)雜條件下移動異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋算法*

李 明, 胡江平

(1.重慶工商大學(xué) 計算機科學(xué)與信息工程學(xué)院 檢測控制集成系統(tǒng)工程實驗室, 重慶 400067；2.電子科技大學(xué) 自動化工程學(xué)院, 四川 成都 611731)

0 引 言

近年來,隨著機器人技術(shù)的發(fā)展,借助機器人平臺的移動傳感器網(wǎng)絡(luò)的覆蓋得到了越來越多研究者的重視[1]。文獻[2]提出一種基于遺傳算法的K覆蓋的動態(tài)傳感器網(wǎng)絡(luò)覆蓋算法。文獻[3]提出一種利用基于反向?qū)W習(xí)的蜂群算法優(yōu)化移動節(jié)點的方法。文獻[4]提出一種基于遺傳算法的水下傳感器網(wǎng)絡(luò)部署算法。文獻[5]提出了一種質(zhì)心化的Voronoi圖模型和圓覆蓋結(jié)合的方法用于移動傳感器網(wǎng)絡(luò)覆蓋。文獻[6]基于Voronoi提出兩種解決移動傳感器網(wǎng)絡(luò)的覆蓋空洞修復(fù)算法。以上文獻絕大數(shù)都假定參與覆蓋的傳感器節(jié)點參數(shù)相同,未考慮到節(jié)點異構(gòu)對覆蓋性能的影響。文獻[7] 針對同構(gòu)節(jié)點、異構(gòu)節(jié)點和非規(guī)則區(qū)域應(yīng)用場合研究了基于粒子均衡的移動傳感器網(wǎng)絡(luò)覆蓋算法。文獻[8]對面向區(qū)域覆蓋的異構(gòu)移動傳感器節(jié)點部署進行研究。文獻[9]對不同移動速度和位置測量誤差條件下的移動傳感器覆蓋問題進行研究。以上三篇文獻對節(jié)點異構(gòu)條件下的動態(tài)覆蓋算法進行研究,都假定監(jiān)測區(qū)域目標(biāo)出現(xiàn)的概率均相同,忽視了由于監(jiān)測目標(biāo)出現(xiàn)不均勻?qū)Ω采w性能的影響。

針對這些問題,本文提出了一種復(fù)雜條件下節(jié)點動態(tài)覆蓋算法。該算法考慮到不同部署位置具有不同的重要性、節(jié)點的可靠性、壽命和移動能力均不同的復(fù)雜條件下,以區(qū)域覆蓋性能最大化為優(yōu)化目標(biāo),利用改進的微分進化算法EDE來布置傳感器節(jié)點,達到增強網(wǎng)絡(luò)服務(wù)質(zhì)量的目的。

1 問題模型分析

(1)

(2)

(3)

(4)

(5)

(6)

式(1)使得在某一特定時刻節(jié)點只能工作或休眠狀態(tài)；式(2)使得在特定的時間里每個區(qū)域至多被一個傳感器節(jié)點覆蓋；式(3)使得在特定的時間里每個傳感器節(jié)點至多覆蓋一個區(qū)域；式(4)對節(jié)點的移動性進行約束,使得節(jié)點移動次數(shù)不超過最大移動次數(shù)Ms；式(5)使得節(jié)點生命周期(處于活動狀態(tài)和由于節(jié)點移動導(dǎo)致的壽命損耗總和)不超過其壽命Ls。

2 改進微分進化算法

2.1 微分進化算法

微分進化算法是一種基于群體的啟發(fā)式算法[10],已廣泛運用于各種組合優(yōu)化問題。差分算法的一次迭代包括初始化種群、變異、交叉和選擇4個基本步驟。其算法流程為：

1)設(shè)置算法的控制參數(shù),包括變異參數(shù)F,最大迭代次數(shù),交叉概率CR和種群規(guī)模NP

4)while預(yù)先設(shè)定的終止條件不滿足,Do

ForI=1:NP

a.變異操作

(7)

(8)

(9)

b.交叉操作

式中rand為產(chǎn)生0～1之間的隨機數(shù),jrand為產(chǎn)生1～D之間的隨機整數(shù)

c.選擇操作

End for

d.t=t+1

End while

由于微分進化算法中選擇操作,使得種群中的個體差異性逐漸喪失,種群多樣性逐漸降低,導(dǎo)致算法過早收斂。針對原始微分進化算法的存在的缺點,為增強算法的全局搜索能力和避免過早收斂,本文提出了一種基于改進微分進化算法EDE解決本文的異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題。

2.2 改進的微分進化算法EDE

采用三種措施增強算法的優(yōu)化能力,分別為：自適應(yīng)的變異策略、與模擬退火相結(jié)合的局部搜索能力增強策略和自適應(yīng)的控制參數(shù)設(shè)置。具體改進措施為：

1)自適應(yīng)的變異策略

在文獻[13]定義的變異策略中,式(7)有利于保持種群的多樣性,全局搜索能力較強,式(9)有利于種群的快速收斂,式(8)的優(yōu)化能力處于式(7)和式(9)之間。原始的DE算法的變異策略在算法開始前已經(jīng)確定且在運行過程中不能改變,不能根據(jù)算法進化過程中種群的情況進行自適應(yīng)調(diào)整,導(dǎo)致算法的優(yōu)化能力下降。針對這一缺點,本文提出了一種自適應(yīng)的變異策略,具體為

采用的變異策略：

2)局部搜索能力增強策略

原始DE算法具有較強的全局搜索能力,但其單純依靠適應(yīng)度大小來決定解的優(yōu)劣,使得當(dāng)種群中某個個體適應(yīng)度較大時,則該個體的基因迅速擴散,降低了種群的多樣性。將具有良好局部搜索能力的模擬退火算法與全局搜索能力強的DE算法相結(jié)合,可以更好解決局部的早熟收斂問題。具體操作為：對經(jīng)過變異、交叉、選擇操作所產(chǎn)生的一組新個體中的最佳個體進行模擬退火操作,將差分操作后的群體中最佳個體作為新解,采用Metropolis準(zhǔn)則來判斷是否接受新解。在算法優(yōu)化的每一代,若這個新解使得適應(yīng)度改善,則被接受；否則,以指數(shù)概率形式來決定是否被接受。接受新解的概率公式為

式中 fit(k+1)為新解的適應(yīng)度值,fit(k)為原解的適應(yīng)度值；rand為區(qū)間(0,1)之間的隨機數(shù)；(T(k+1))為溫度T(k+1)下的接收概率；T(k+1)的計算公式為T(k+1)=α×T(k)

3)自適應(yīng)的參數(shù)選擇策略

原始DE算法中控制參數(shù)F、交叉因子CR為常數(shù),不能根據(jù)種群演化情況調(diào)整,影響算法的優(yōu)化能力。針對這一問題,本文提出一種自適應(yīng)的參數(shù)選擇策略,具體為

式中Fmin,Fmax,CRmin,CRmax分別為F和CR的最小值和最大值。當(dāng)種群個體有早熟的趨勢時,采用較大的F的值和較小的CR值進行抑制,保持種群的多樣性；反之,當(dāng)種群個體收斂較慢時,采用較小的F的值和較大的CR,加快種群的收斂；其他情況下,產(chǎn)生隨機的F和CR。

3 基于EDE的異構(gòu)傳感器網(wǎng)絡(luò)覆蓋算法

對于異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋問題,將其轉(zhuǎn)化為目標(biāo)優(yōu)化問題,采用提出的EDE算法進行求解,具體步驟詳見本文的第2部分。根據(jù)要解決問題的特點,算法的一些關(guān)鍵部分?jǐn)⑹鋈缦拢?/p>

1)問題編碼

種群中的每個個體代表求解問題的一個候選解,染色體編碼示意圖如圖1所示。

圖1 染色體編碼示意

本文中每個個體的維數(shù)為|S|×|T|×|W|,其中|S|是傳感器類型數(shù),|T|是時間長度,|W|是區(qū)域數(shù)目。染色體中取1或0,分別對應(yīng)節(jié)點在該區(qū)域該時間內(nèi)是工作狀態(tài)還是休眠狀態(tài),如圖1所示。其中,t1,t2表示部署的時間；z1,z2表示候選的放置傳感器節(jié)點的位置；s1,s2表示不同的傳感器類型。

2)適應(yīng)度函數(shù)設(shè)計

本文要解決的問題為在滿足傳感器節(jié)點自身可靠性、壽命、移動能力等約束條件下使得在給定的監(jiān)測時間和監(jiān)測區(qū)域內(nèi)覆蓋性能最大。結(jié)合前面的分析,本文優(yōu)化的目標(biāo)為

式中λ1,λ2,λ3,λ4為懲罰因子,一般取較大的數(shù)值。

4 仿真分析

4.1 仿真參數(shù)設(shè)置

其中,U(A,B)表示在區(qū)間[A,B]均勻分布,R(0,1)為(0,1)區(qū)間的隨機數(shù)。微分進化算法的參數(shù)設(shè)置為種群數(shù)為50,最大迭代次數(shù)為500,F在區(qū)間[0.1,0.9]取值,CR取值范圍為[0.3,0.9]。λ1=λ2=λ3=λ4=1 000。下面設(shè)計了一系列實驗,每一個實驗的實驗結(jié)果均為30次實驗結(jié)果的平均值。

4.2 仿真結(jié)果與分析

1)適應(yīng)度比較

對兩種算法在求解過程中的平均適應(yīng)度進行比較,結(jié)果如圖2所示。

從圖中可以看出,隨著迭代次數(shù)的增加,原始DE算法和EDE算法都逐漸趨于收斂,且EDE算法的適應(yīng)度優(yōu)于原始DE算法,證明了EDE算法的有效性。

2)不同參數(shù)設(shè)置下算法性能比較

分別在不同數(shù)目的部署區(qū)域數(shù)W、節(jié)點部署數(shù)量N和監(jiān)測時間T利用原始DE和提出EDE算法對本文的覆蓋優(yōu)化問題進行求解,求解的結(jié)果如表1所示。從表1可以看出,隨著W,N,T的增加,目標(biāo)函數(shù)值也在增加；在相同的參數(shù)設(shè)置情況下,EDE算法均優(yōu)于原始DE算法,證明了改進算法的有效性。

表1 算法運行結(jié)果

3)節(jié)點可靠性對性能的影響

將節(jié)點可靠性設(shè)置為不同的值,利用EDE算法進行求解,求解結(jié)果如圖3所示。其中,橫坐標(biāo)為節(jié)點數(shù)量,縱坐標(biāo)為覆蓋函數(shù)。從圖中可以看出,在節(jié)點數(shù)相同的情況下,可靠性越高,覆蓋性能越好；在可靠性不變的情況下,節(jié)點數(shù)越多,網(wǎng)絡(luò)覆蓋性能越好。

4)節(jié)點移動性對性能的影響

設(shè)置不同的移動參數(shù),求解結(jié)果如圖4所示。其中,橫坐標(biāo)為節(jié)點移動性能與壽命的比值,縱坐標(biāo)為覆蓋函數(shù)。從圖中可以看出,隨著節(jié)點移動性能的增強,覆蓋性能也隨之變大。比如當(dāng)橫坐標(biāo)從0.1增加到1時,EDE和DE算法覆蓋性能分別提高了58.9 %和49.0 %。原因在于,隨著移動性能的增強,節(jié)點可以移動到權(quán)重比較大的區(qū)域。再者,在移動能力相同的情況下,EDE算法覆蓋性能優(yōu)于DE算法,證明了改進算法的有效性。

圖2 算法平均適應(yīng)度比較 圖3 節(jié)點可靠性與覆蓋性能關(guān)系 圖4 節(jié)點移動性與覆蓋性能的關(guān)系

5 結(jié) 論

本文提出了一種基于改進微分進化算法的覆蓋策略,解決在給定節(jié)點的壽命,可靠性、移動性能不同和部署區(qū)域具有不同的權(quán)重條件下覆蓋性能最大化問題。下一步的工作為,將節(jié)點的概率感知模型引入優(yōu)化目標(biāo)中,得到更一般的覆蓋性能函數(shù),進一步對概率感知模型下的覆蓋算法進行研究。