復雜條件下移動異構無線傳感器網絡覆蓋算法*

李 明, 胡江平

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

0 引 言

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

針對這些問題,本文提出了一種復雜條件下節點動態覆蓋算法。該算法考慮到不同部署位置具有不同的重要性、節點的可靠性、壽命和移動能力均不同的復雜條件下,以區域覆蓋性能最大化為優化目標,利用改進的微分進化算法EDE來布置傳感器節點,達到增強網絡服務質量的目的。

1 問題模型分析

(1)

(2)

(3)

(4)

(5)

(6)

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

2 改進微分進化算法

2.1 微分進化算法

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

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

4)while預先設定的終止條件不滿足,Do

ForI=1:NP

a.變異操作

(7)

(8)

(9)

b.交叉操作

式中rand為產生0～1之間的隨機數,jrand為產生1～D之間的隨機整數

c.選擇操作

End for

d.t=t+1

End while

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

2.2 改進的微分進化算法EDE

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

1)自適應的變異策略

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

采用的變異策略：

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

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

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

3)自適應的參數選擇策略

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

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

3 基于EDE的異構傳感器網絡覆蓋算法

對于異構傳感器網絡的覆蓋問題,將其轉化為目標優化問題,采用提出的EDE算法進行求解,具體步驟詳見本文的第2部分。根據要解決問題的特點,算法的一些關鍵部分敘述如下：

1)問題編碼

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

圖1 染色體編碼示意

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

2)適應度函數設計

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

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

4 仿真分析

4.1 仿真參數設置

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

4.2 仿真結果與分析

1)適應度比較

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

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

2)不同參數設置下算法性能比較

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

表1 算法運行結果

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

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

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

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

圖2 算法平均適應度比較 圖3 節點可靠性與覆蓋性能關系 圖4 節點移動性與覆蓋性能的關系

5 結 論

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