李 明, 胡江平

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

0 引 言

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

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

1 問(wèn)題模型分析

(1)

(2)

(3)

(4)

(5)

(6)

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

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

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

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

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

4)while預(yù)先設(shè)定的終止條件不滿(mǎn)足,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)化算法中選擇操作,使得種群中的個(gè)體差異性逐漸喪失,種群多樣性逐漸降低,導(dǎo)致算法過(guò)早收斂。針對(duì)原始微分進(jìn)化算法的存在的缺點(diǎn),為增強(qiáng)算法的全局搜索能力和避免過(guò)早收斂,本文提出了一種基于改進(jìn)微分進(jìn)化算法EDE解決本文的異構(gòu)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題。

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算法的變異策略在算法開(kāi)始前已經(jīng)確定且在運(yùn)行過(guò)程中不能改變,不能根據(jù)算法進(jìn)化過(guò)程中種群的情況進(jìn)行自適應(yīng)調(diào)整,導(dǎo)致算法的優(yōu)化能力下降。針對(duì)這一缺點(diǎn),本文提出了一種自適應(yīng)的變異策略,具體為

采用的變異策略：

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

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

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

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

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

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

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

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

1)問(wèn)題編碼

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

圖1 染色體編碼示意

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

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

本文要解決的問(wèn)題為在滿(mǎn)足傳感器節(jié)點(diǎn)自身可靠性、壽命、移動(dòng)能力等約束條件下使得在給定的監(jiān)測(cè)時(shí)間和監(jiān)測(cè)區(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è)計(jì)了一系列實(shí)驗(yàn),每一個(gè)實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果均為30次實(shí)驗(yàn)結(jié)果的平均值。

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

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

對(duì)兩種算法在求解過(guò)程中的平均適應(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)測(cè)時(shí)間T利用原始DE和提出EDE算法對(duì)本文的覆蓋優(yōu)化問(wèn)題進(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)可靠性對(duì)性能的影響

將節(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)移動(dòng)性對(duì)性能的影響

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

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

5 結(jié) 論

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