改進差分進化算法下的無線傳感器網絡覆蓋優化

王振東，劉燔桃，胡中棟，李大海，溫 衛

(江西理工大學 信息工程學院，江西 贛州 341000)

E-mail：liufantaojsj@foxmail.com

1 引 言

無線傳感器網絡是由部署在監測區域內的傳感器節點形成的自組織網絡，具有體積小、低成本、低功耗等特點，可以實時協助感知、采集和處理監測對象的信息，因而被廣泛應用于環境檢測、災害預警等方面[1].無線傳感器網絡節點部署位置是否適當對網絡性能和網絡生命周期產生直接影響，節點的部署密度會影響網絡覆蓋率，部署密度高雖能獲得較高的覆蓋率，但會產生大量冗余節點，降低網絡整體性能.因此，無線傳感器網絡節點的部署優化一直是學者們研究的熱點問題.為此，諸多學者提出了多種代表性的覆蓋控制方法.文獻[2]提出基于虛擬勢場力的傳感器網絡區域覆蓋控制算法，該算法將網絡中的移動節點看做虛擬的帶電粒子，相鄰節點之間同時存在引力和斥力，通過兩者的共同作用使無線傳感器網絡覆蓋區域最大化.文獻[3]提出一種基于虛擬力的分簇部署算法，有效的改善了傳統的基于虛擬力算法的節點覆蓋優化，明顯的提高了網絡覆蓋率，但存在局限性，僅在部署初期擁有大量密集節點時效果顯著.文獻[4，5]提出以voronoi圖為基礎的覆蓋控制算法，通過設計基于群集控制的傳感器節點部署分布式控制方法，建立基于Voronoi剖分的監測性能評價函數，有效提高了網絡覆蓋質量.

近年來，智能優化算法在無線傳感器網絡覆蓋優化中得到廣泛應用.如遺傳算法[6，7]，粒子群算法[8，9]，花朵授粉算法[10]等.文獻[6]提出基于元啟發式的遺傳算法解決目標覆蓋問題，用最少的傳感器節點構成目標覆蓋集，但算法容易收斂至局部最優.文獻[7]提出了一種通過改進交叉和變異操作的遺傳算法以解決無線傳感器網絡節點的目標覆蓋問題，該算法一定程度上提高了無線傳感器網絡節點的覆蓋率，但收斂精度不夠高.文獻[8]結合量子粒子群算法與混沌優化，對局部極值位置進行混沌搜索，引導其跳出局部最優，但算法復雜度較高且不夠穩定.文獻[10]提出一種基于花朵授粉算法的無線傳感器網絡覆蓋優化，取得了較好的覆蓋效果，但收斂速度較慢，且節點均勻度不夠理想.

針對相關算法存在的不足，本文提出了一種改進的差分進化算法IDEA(Improved Differential Evolution Algorithm)，由于種群的優劣會對算法的求解精度和收斂速度產生影響，而多樣性較好的種群能有效提升算法性能.故在基本差分進化算法DEA(Differential Evolution Algorithms)的基礎上，IDEA算法設置了混沌反向學習機制以增強種群的多樣性，提升算法性能，同時利用精英篩選策略選出的精英群體來引導變異向量往更優方向進化，進一步加快收斂速度.然后，自適應調整變異因子和交叉概率因子，有效協調算法的全局勘探和局部開發的能力，提高收斂精度.仿真實驗通過對6組基準函數在不同維度下的優化對比，驗證了改進策略的有效性，并將改進后的算法應用于無線傳感器網絡節點覆蓋優化中.選取不同文獻中的3種算法在相同條件下進行對比，在節點相同的情況下IDEA算法的覆蓋率明顯高于其他算法，驗證了該算法的應用價值.

2 傳感器網絡節點覆蓋模型

在無線傳感器網絡中，假設N個同構無線傳感器節點的集合S={s1，s2，...，si，…，sN}，感知半徑都為r，假設監測區域是面積為L·Wm2的矩形區域，為便于計算，將該矩形區域離散化為L·W個面積相等的網格，監測點位于網格的幾何中心位置，若監測點與任意一個節點的距離小于或等于感知半徑r，則認為該監測點被無線傳感器網絡覆蓋.監測節點的集合M={m1，m2，...，mj，…，mL·W}，(xi，yi)與(xj，yj)分別對應集合中si與mj的二維空間坐標.則兩節點之間的歐氏距離為：

(1)

監測點mj被節點si感知的概率定義定義為：

(2)

所有傳感器節點對點mj的聯合感知概率定義為：

(3)

式(3)中：Sall為監控區域內的全部無線傳感器節點.通過式(3)計算出所有監測點的聯合感知概率，覆蓋面積即為所有監測點的聯合感知概率和.則覆蓋率Cr可表示如下：

(4)

3 差分進化進化算法

差分進化算法是一種基于群體智能的啟發式算法，它利用種群個體間的差分信息對個體向量進行擾動，通過變異、交叉和選擇操作進化出更優秀的后代.差分進化算法由一個初始種群開始不斷迭代產生新的種群.種群中的每個個體都可表示為包含每個節點的位置信息的一個向量，種群中的每個個體就是解空間里的一個解.差分進化算法通過不斷的變異、交叉和選擇操作，使得種群不斷向更優的方向進化，將變異算子和交叉算子作用于種群中的每個向量，使之生成試驗向量，然后用選擇算子在試驗向量和當前向量中選擇一個成為種群的下一代個體.通過這種方式，差分進化算法能在確定的迭代次數下不斷向更優方向進化.

3.1 變異算子

(5)

3.2 交叉算子

試驗向量由變異向量與目標向量交叉重組形成，此過程稱為交叉過程，目的是增加種群的多樣性.對于每一個變異向量中的元素j(j∈{1，2，...，D})，用rand表示隨機在區間[0，1]中選擇的一個數，，將rand與交叉概率因子C對比，若rand

(6)

交叉概率因子越大，試驗向量中變異向量的元素所占比例越高、目標向量的元素所占比例越低，即試驗向量與目標向量的差異性越大.

3.3 選擇算子

選擇算子是一種精英篩選機制，通過計算目標向量和試驗向量的適應度函數的適應值(即目標優化函數值)，選擇適應值較好的個體作為下一代種群的個體，由此得到的下一代種群的個體均為目前為止的最優個體.

(7)

在目標向量和對應的試驗向量中選擇一個適應值好的保留到下一代，剩下的淘汰.

首先基于SMIC 0.18μm工藝采用SILVACO Athena工具對有源區直徑為10μm的SPAD器件進行了工藝仿真，獲得與工藝相關的器件結構后再使用SILVACO Atlas工具進行了器件特性仿真。考慮了雜質濃度相關的Conmob和低場的Fldmob遷移率模型、SRH復合模型、Selberherr碰撞電離模型、Band-to-band tunneling(BTBT)隧穿模型和Geiger等模型，提取出雪崩電壓、電場分布、雪崩觸發幾率等重要的器件性能參數。

4 改進的差分進化算法

在DEA算法運行過程中，種群的多樣性會隨著迭代次數的增加而快速下降，導致算法有可能會因早熟收斂而陷入局部最優.為了提升算法的全局尋優能力，須在算法初始階段加強種群多樣性.據此，本文提出一種改進的差分進化算法：在初始階段，引入混沌反向學習策略初始化種群，利用混沌映射的遍歷性和均勻性增強種群的多樣性；在迭代過程中利用精英篩選機制選出的精英群體對變異向量進行引導，使之往更好的方向變異；自適應調整變異因子及交叉概率因子，在加快收斂速度的同時提高算法的尋優精度和穩定性.

4.1 基于混沌反向學習的種群初始化

初始種群的優劣會對算法的求解精度和收斂速度產生影響，多樣性較好的初始種群能有效提升算法性能.混沌映射的隨機性和遍歷性能豐富初始種群的多樣性，使算法可以搜索到更好的解，文獻[11，12]都在算法中使用混沌映射來產生搜索序列，文獻[11]證明了Tent混沌映射對算法性能提升較大，故本文采用Tent混沌映射產生初始初始種群.反向學習策略是對當前可行解生成其反向解，對兩種解進行評估并保留較優的解作為下一代個體.因此改進的算法采用混沌反向學習初始化策略，首先利用Tent混沌序列的隨機性和遍歷性產生初始混沌種群，然后通過反向學習策略生成反向種群，最后計算初始混沌種群個體和反向種群個體的適應值并保留適應值更好的個體作為最終的初始種群.

假設種群規模為N，空間維度用D表示，采用Tent混沌映射在空間中生成混沌序列Z={Zj，j=1，2，...，D}，Zj={Zi,j，i=1，2，…，N}，Tent混沌映射函數如下：

(8)

將混沌序列映射到解空間得到種群Yj={Yj，i=1，2，…，N}，Yi={Yi,j，j=1，2，…，D}，種群個體Yi,j表示如下：

Yi,j=Ymin,j+Yi,j(Ymax,j-Ymin,j)

(9)

OYi,j=Ymin,j+Ymax,j-Yi,j

(10)

其中：Ymin,j和Ymax,j分別是搜索下界和搜索上界，Yi,j表示種群的第i個種群個體的第j維值.然后計算得到反向種群OYj={OYj，i=1，2，…，N}，OYi={OYi，j，j=1，2，…，D}，最后計算種群和反向種群個體的適應值，選取適應值較好的個體作為最終初始種群.

4.2 精英群體引導變異向量

基本DEA算法中，變異向量由父代種群中隨機選取的三個向量計算得到，未能充分利用進化過程中的優秀經驗指導新個體的變異方向.本文引入精英群體概念，對當前群體按適應值由好到差進行排序，定義種群中適應度值較好的前Pelite個個體為精英群體.以精英群體中的個體為基向量，引導變異向量向適應值更好的方向尋優：

(11)

(12)

式(12)中：g為當前迭代次數，G為總迭代次數，ceil{λ}表示大于λ的最小整數.Pelite表示精英個體的數量，精英個體數量在進化前期較大，但會隨著迭代次數非線性遞減，故能在迭代前期兼顧種群的多樣性，后期趨向于全局最優解，加快算法的收斂速度.

4.3 參數自適應策略

差分進化算法對參數的選擇非常敏感，變異因子影響搜索范圍，交叉概率因子決定搜索方向，因此變異因子和交叉概率因子的設置會對算法的收斂性能和尋優效率產生深刻影響.在算法初期，應盡可能使算法在搜索空間內充分探測，保證種群的多樣性，避免因早熟收斂而陷入局部最優.到了算法后期，應充分挖掘最優個體的信息，提升算法的收斂精度，因此本文采用參數自適應策略來對變異因子和交叉概率因子進行調整，以平衡算法的全局勘探和局部開能力.

4.3.1 變異因子自適應策略

變異因子具備平衡算法局部搜索和全局搜索的能力.在差分進化算法初期，為避免局部最優，變異因子取值較大，后期為了保留精英個體、提高搜索效率，變異因子應取值較小.為了加快種群進化，每個個體宜采用不同的變異因子.對于求解最小化問題，第g+1代變異因子集合更新策略如下：

(13)

(14)

(15)

4.3.2 交叉概率因子自適應策略

交叉概率因子對算法的搜索能力和收斂性存在較大影響.本文利用基于父代個體適應值與群體平均適應值的相對值進行調整，第g+1代交叉因子集合更新策略如下：

(16)

5 改進差分進化算法的實現步驟

通過以上分析，本文提出了一種改進的差分進化算法，通過混沌反向學習初始化種群以增加初始種群分布的隨機性和均勻性，在初始階段就得到一個相對較好的種群，然后采用精英策略，用精英群體引導變異向量，同時自適應調整變異因子和交叉概率因子，加快收斂速度，提升算法性能.具體過程如表1中的偽代碼所示.

表1 IDEA偽代碼

6 仿真和結果分析

采用主頻為2.4GHz的PC機在MATLAB R2016a環境中，通過一系列的仿真實驗來檢驗本文算法的性能.為了對比各種算法的性能指標，仿真實驗的相關參數均同等設置.

6.1 對6個基準測試函數的尋優性能比較

為了測試IDEA算法的性能，從文獻[12]中的選取6個不同類型的基準測試函數進行計算.其中有3個單峰函數和3個多峰函數，理論最優值均為0，其具體函數名、表達式、搜索范圍、最優值、類型如表2所示，并與遺傳算法GA[13]，粒子群算法PSO[14]和花朵授粉算法FPA[15]等三種算法在不同維度時的計算結果進行對比，所有算法的種群規模均設置為30，迭代5000次.對于每個測試函數，在不同維度下每種算法均獨立運行20次，記錄其平均值.表3是6個基準測試函數分別在維度是30和100的情況下各算法的平均值，其中黑色粗體為各算法中的最好結果.

表2 基準測試函數

表3 算法對基準測試函數在不同維度下的平均值比較

多峰函數存在許多局部極值點，通常被認為是優化算法很難處理的復雜多模態問題，由表2 可知，對于6個測試函數，不論是多峰還是單峰函數，所有比較算法中IDEA算法的結果都是最優的，特別是對于多峰函數F4和F6，IDEA算法都找到了其理論最優值0，剩下的其他4個測試函數中，IDEA算法的收斂精度都是最高的.因為IDEA算法中混沌反向學習策略豐富了種群的多樣性，當陷入局部最優和停滯狀態時，算法可以憑借自適應調整的變異因子和交叉概率因子擺脫這種狀態，而且精英群體引導的變異向量能有效引導變異因子向更優方向進化，同時加快收斂速度.故算法能有效協調全局勘探和局部開發能力，在遇到高維復雜的函數時也能提高收斂精度.

圖1 F1的三維圖形和在維度分別是30和100時各算法的收斂曲線

圖2 F2的三維圖形和在維度分別是30和100時各算法的收斂曲線

圖3 F3的三維圖形和在維度分別是30和100時各算法的收斂曲線

圖4 F4的三維圖形和在維度分別是30和100時各算法的收斂曲線

圖5 F5的三維圖形和在維度分別是30和100時各算法的收斂曲線

圖6 F6的三維圖形和在維度分別是30和100時各算法的收斂曲線

圖1-圖6是6個測試函數的三維圖形以及各自分別在30維和100維時四種算法的收斂曲線圖.從結果上看，對于多峰函數F4和F6，改進后的差分進化算法找到了理論最優值0，尋優成功率達到了百分之百，說明其尋優性能良好且魯棒性強，性能明顯優于文獻中的其他三種算法.對于本文中的所有測試函數，IDEA算法的收斂速度和收斂精度都是最好的.如測試函數F1，雖然IDEA算法沒有找到理論最優值，但其收斂精度相比GA算法在30維和100維時分別提升了127和75個數量級，相比PSO算法在30維和100維時分別提升了87和73個數量級，相比PSO算法在30維和100維時分別提升了125和68個數量級，說明IDEA算法能有效跳出局部最優，且在處理高維復雜問題時更能體現出性能良好和穩定的優勢.這是因為改進的差分進化算法中精英群體引導變異向量能有效提升算法的收斂速度，幫助算法從全局搜索平穩的過渡到后期的局部搜索，自適應的變異因子和交叉概率因子在處理目標函的時候能有效協調算法的全局勘探和局部開發能力，在遇到多峰高維的函數時能提高收斂精度.

6.2 各算法在不同傳感器網絡節點數量下的覆蓋率比較

為了驗證IDEA算法對無線傳感器網絡節點覆蓋的優化性能，對監測區域內各算法在不同數量傳感器節點下的覆蓋率進行比較.在50m×50m的正方形監控區域內部署傳感器節點，感知半徑為5m，通信半徑為10m，種群規模是50，初始階段設定變異因子為0.7，交叉概率因子為0.5，最大迭代次數為300，分別在傳感器節點數量為30、35、40、45、50、55、60的情況下用不同算法進行20次獨立實驗，記錄其平均值，其他參數不變，不同算法部署策略下的覆蓋率隨節點數量變化趨勢如圖7所示.

圖7 覆蓋率隨節點數量變化折線圖和條形圖

由圖7可知，在節點數量確定的情況下，IDEA算法部署策略下的無線傳感器網絡節點覆蓋率一直是領先其他算法的，且在50個節點時就能達到百分之百的覆蓋率.而其他三種算法在60個節點時都沒有達到百分之百的覆蓋率，說明改進的差分進化算法確實能夠有效協調算法的全局勘探和局部開發能力，進而提升無線傳感器網絡節點的有效覆蓋率.

7 總 結

節點部署是無線傳感器網絡研究領域的一個重要問題.在基本差分進化算法的基礎上，本文提出了一種改進的差分進化算法，并成功應用于無線傳感器網絡的節點優化部署.通過設置混沌反向學習初始化種群，提升了種群的多樣性；定義了精英群體實現對變異向量的引導，加快了種群的全局尋優速度；使用參數自適應調整機制協調算法的全局勘探和局部開發的能力，提高收斂精度.將該算法在6個基準測試函數上與其他文獻的3種算法分別在30維和100維時進行實驗對比，并應用于無線傳感器網絡覆蓋優化中.仿真結果表明，與其他文獻中的三種算法相比，改進后的差分進化算法在無線傳感器網絡節點覆蓋率和收斂速度及收斂精度上均有較大程度的提升，證明了改進后算法的有效性.