李 明, 胡江平

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

0 引 言

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

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

1 問題模型分析

(1)

(2)

(3)

(4)

(5)

(6)

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

2 改進(jìn)微分進(jìn)化算法

2.1 微分進(jìn)化算法

微分進(jìn)化算法是一種基于群體的啟發(fā)式算法[10],已廣泛運(yùn)用于各種組合優(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之間的隨機(jī)數(shù),jrand為產(chǎn)生1～D之間的隨機(jī)整數(shù)

c.選擇操作

End for

d.t=t+1

End while

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

2.2 改進(jìn)的微分進(jìn)化算法EDE

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

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

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

采用的變異策略：

2)局部搜索能力增強(qiáng)策略

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

式中 fit(k+1)為新解的適應(yīng)度值,fit(k)為原解的適應(yīng)度值；rand為區(qū)間(0,1)之間的隨機(jī)數(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值進(jìn)行抑制,保持種群的多樣性；反之,當(dāng)種群個體收斂較慢時,采用較小的F的值和較大的CR,加快種群的收斂；其他情況下,產(chǎn)生隨機(jī)的F和CR。

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

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

1)問題編碼

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

圖1 染色體編碼示意

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

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

本文要解決的問題為在滿足傳感器節(jié)點(diǎn)自身可靠性、壽命、移動能力等約束條件下使得在給定的監(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ū)間的隨機(jī)數(shù)。微分進(jìn)化算法的參數(shù)設(shè)置為種群數(shù)為50,最大迭代次數(shù)為500,F在區(qū)間[0.1,0.9]取值,CR取值范圍為[0.3,0.9]。λ1=λ2=λ3=λ4=1 000。下面設(shè)計了一系列實(shí)驗(yàn),每一個實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果均為30次實(shí)驗(yàn)結(jié)果的平均值。

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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