改進灰狼優化算法在WSN節點部署中的應用*

胡小平,曹 敬

(湖南科技大學先進礦山裝備教育部工程研究中心,湖南 湘潭 411201)

無線傳感網絡是由一定規模的終端傳感節點通過無線通信的方式組成的一種自組織網絡。傳感器節點通常具有通信、計算、感知等能力,通過對其規模化部署形成的無線傳感網絡具有對監測區域進行監控的能力。無線傳感網絡中單個節點僅承擔部分檢測任務,單個節點故障對網絡的整體監測能力影響較小,且節點之間進行無線通信無需要人工鋪設線纜擁有更好的連接便利性。因此,通過大量節點部署后組織的無線傳感網絡擁有良好的容錯能力和斷接性能等特點。近年來,無線傳感網絡廣泛運用于輔助農業生產、環境監測、物流和智能家電領域。在應用過程中,傳感器節點多采取隨機拋灑的部署方式,由于部署位置隨機,使其存在覆蓋盲區,難以有效覆蓋待監測區域,從而影響網絡的監控能力。監測區域環境變化和傳感器節點可移動性改變等因素會降低網絡覆蓋率從而影響其監控能力。因此,需要對無線傳感網中傳感器節點的進行自適應的調整部署,以于提高傳感網絡覆蓋率、減少覆蓋盲區、減少傳感器部署數量以節約網絡構建成本[1-2]。

近幾年來,灰狼優化算法GWO(Grey Wolf Optimizer)得到了廣泛關注。灰狼優化算法是由學者Mirjalili等人于2014年提出了一種新的群智能算法,文獻[3]表明,在基準函數求解問題上,GWO算法與粒子群算法PSO(Particle Swarm Optimization)算法、(差分進化算法DE(Differential Evolution)算法和萬有引力算法GSA(Gravitational Search Algorithm)算法相比擁有更高的精度和穩定性。國內外學者對灰狼優化算法進行了大量的研究:姚鵬等人將灰狼優化算法與流體擾動算法結合應用于無人機三維航路規劃得到了平滑性和可飛性高的三維航路[4];Sulaiman等人研究了灰狼算法在最優無功電力調度問題上的應用,表明與其他技術相比灰狼算法能實現更小的功率損耗和電壓偏差[5];Madadi等人利用灰狼優化算法對直流電機PID控制器參數進行優化,相比PSO算法提高了控制的穩定性[6];Song等人將GWO應用于表面波色散曲線反演,與遺傳算法相比GWO算法減少了控制參數的同時提高了收斂速度[7];HM Song將灰狼優化算法引入電力系統的組合經濟排放調度問題,以此得到了最佳的發電方式[8];Mahdad等人將灰狼優化算法應用于電力控制系統以減小停電風險,通過實際測試證明了該方法的安全性和可行性[9];針對在應用過程中灰狼優化算法出現的中后期收斂速度慢和易陷入局部極值的問題。Nasrabadi 等人通過并行和反向學習改進灰狼優化算法,提高了算法在解決基準函數求解問題上的速度和精度[10];郭振洲等人將非線性收斂因子與動態權重引入灰狼優化算法,加快了算法收斂速度[11];徐松金等人利用佳點集理論初始化種群,在迭代過程中引入算術交叉和多樣性變異操作以避免算法陷入局部最優解并增強算法的局部搜索能力,其改進算法在較高維度函數求解問題上對比標準灰狼優化算法擁有明顯優勢[12]。

標準灰狼優化算法在應用于優化問題時存在中后期收斂速度慢且容易陷入局部極值問題[13]。文獻[14]認為,提高初始種群的多樣性有助于提高搜索算法的搜索效率。而混沌算法具非線性系統的特點,具有非重復性與遍歷性的特點。混沌算法引入種群初始化,利用其特點生成初始種群以提高初始種群多樣性,為全局搜索提供基礎;此外,使用改進的非線性收斂因子代替標準灰狼優化算法中的線性收斂因子,以提高算法中后期的搜索能力加快收斂速度;最后,對第三優解進行融合變異,以加快搜索速度和避免陷入局部最優解。并將改進灰狼優化算法應用于無線傳感網絡節點部署問題,開展改進算法的仿真分析。

1 節點與覆蓋模型

(1)

任一目標點可以被多個傳感節點同時檢測,則對目標點的聯合測量概率為:

(2)

式中:gov為測量目標點的傳感器集合。所有節點對待檢測區域的覆蓋率為:

(3)

式(3)覆蓋率函數值的最大化為無線傳感網絡覆蓋模型的優化目標。

若無線傳感網絡中的兩節點間距離不大于通信半徑,則認為兩節點間存在一條通信路徑。定義Hij為任意兩節點i與j之間的通信路徑數量。滿足網絡連通要求的約束為:Hij≥1。同時,所有的節點位置應處于待監測目標區域內,可表示為:L(gi)∈M。

綜上所述目標函數為:

(4)

2 灰狼優化算法基本原理

灰狼優化算法是一種啟發式算法,其通過模擬自然界中灰狼群的等級劃分以及狩獵機制達到逼近目標的目的。根據簡化的灰狼的社會層次結構數學模型,灰狼個體被劃為4個類型:α、β、δ、ω。其中頭狼α狼為當前最優解,β狼為當前次優解,δ狼為當前第三優解,ω狼為其余的備選解。為描述灰狼在包圍獵物過程提出的數學模型為:

D=|C·Xp(t)-X(t)|

(5)

X(t+1)=Xp(t)-A·D

(6)

式中:D為個體與目標之間的距離,t為當前迭代次數,C和A為系數向量,Xp為目標位置向量,X為單只灰狼位置向量。C和A計算公式為:

A=2ar1-a

(7)

C=2r2

(8)

式中:r1,r2表示[0,1]間的隨機數,收斂因子a隨迭代次數增加從2線性減小到0:

a=2-2t/tmax

(9)

式中:tmax為最大迭代次數。

自然界中的灰狼擁有判斷目標位置和包圍獵物的能力。而在實際的函數優化過程中目標位置是不可知的。在實際應用中,通過計算每個灰狼對目標函數的適應度,選取灰狼種群中適應度前三的個體:α狼、β狼和δ狼,并由其指引狼群搜索方向,對目標位置進行搜索。通過多次灰狼的位置更新逐漸逼近目標位置。其數學描述如下:

Dα=|C1Xα-X|

(10)

Dβ=|C2Xβ-X|

(11)

Dδ=|C3Xδ-X|

(12)

X1=Xα-ADα

(13)

X2=Xβ-ADβ

(14)

X3=Xδ-ADδ

(15)

X(t+1)=(X1+X2+X3)/3

(16)

根據式(15)對灰狼個體進行更新。

3 改進灰狼優化算法

3.1 混沌初始化

混沌是一種確定的、隨機的非線性動力系統,具有非周期性、不收斂和有界的特點。自上個世紀以來混沌映射在優化算法領域得到了廣泛的重視。因為其動態隨機特性,能使優化算法在搜索區域進行更有效的的全局搜索。

John Wiley[12]等人認為較高的初始種群多樣性能提高啟發式搜索算法的搜索效率。在全局最優解未知的情況下,將初始種群盡可能遍布在搜索范圍內,能為算法前期提供良好全局搜索基礎。盡管標準灰狼優化算法具有較好的收斂速度,但在解決全局最優問題時隨機產生的初始種群可能導致多樣性較差,影響算法的全局搜索能力,出現收斂速度較慢或者收斂精度不理想的情況。為了提高算法搜索效率,將混沌映射引入灰狼算法的初始化中,通過混沌映射使初始個體均勻的分布在搜索區域內,提高初始化種群的多樣性。在混沌映射模型的選擇上,本文采用較為常用的Logistic映射模型進行算法種群的初始化。數學描述如下[13]:

(17)

(18)

式中:j=1,2,…,m為種群序號;[ai,bi]為Xi的搜索范圍。

3.2 非線性收斂因子

啟發式算法在需要在搜索能力和開發能力之間保持良好的平衡,從而實現有效的全局和局部搜索。搜索能力即尋找新的適應度更高的個體的能力;開發能力即為在當前最優解位置附近尋找更優的解的能力。

在標準灰狼優化算法中,收斂因子a的自適應值起到平衡搜索能力和開發能力的作用。算法初期較大的a值保證全局搜索能力。隨著迭代次數的增加a的值逐漸減小,從而加強在當前最優解附近搜索的能力。文獻[11]表明,GWO算法根據A的絕對值進行搜索能力與開發能力的調節,當A絕對值大于1時,灰狼個體將擴大搜索范圍進行全局搜索;反之灰狼個體將縮小搜索范圍進行局部搜索。由式(6)可知A的值由收斂因子與系數決定。在復雜的算法搜索過程中,標準灰狼優化算法從2到0線性減小的收斂因子不能完全平衡算法搜索過程中的搜索能力和開發能力。為了提升算法搜索精度和速度,改進的灰狼優化算法,其收斂因子隨迭代次數增加呈非線性變化,表達式如下:

(19)

式中:ainitial為a給定的初始值;常數μ為非線性調節系數;常數k的值影響算法搜索和開發能力,k值越小則在最優解附近搜索新的最優解能力越強。實際應用中,可根據具體優化問題,調節收斂因子相關系數從而平衡算法搜索能力與開發能力,提高算法搜索效率。

3.3 δ狼的融合變異

標準灰狼優化算法在中后期主要由前三優的解引導搜索方向。若這3個解陷入局部極值,則容易導致最優解的更新停滯從而出現算法過早收斂。為改善過早收斂問題,在一定概率下將δ與α和β的進行融合變異,產生新的δ狼。將第三優解與適應度更高的兩個解進行融合變異,更容易得到比當前第三優解適應度高的解,并將其取代當前第三優解。以此加快δ狼更新,從而影響其余個體搜索方向,改善算法陷入局部極值的情況同時也能加快算法搜索速度。以D的概率對δ狼中的第j維進行融合變異,過程如下:

(20)

式中:j=1,2,…,n為維度序號,υ1、υ2、υ3為[0,1]的隨機數且υ1+υ2+υ3=1。

4 節點部署優化算法

本文算法以無線傳感網絡覆蓋模型中覆蓋率最大化為優化目標,利用一定的數量的傳感節點實現對檢測區域覆蓋率的最大化。算法中灰狼種群包含多灰狼個體,每個灰狼個體擁有相同的維度數,均代表所有傳感節點的一種覆蓋分布方式。待測區域為二維平面,則灰狼個體的維度數為傳感節點數的兩倍,其中第2i和第2i-1維分別為第i個傳感節點的橫坐標和縱坐標。算法優化結束后輸出算法優化過程中搜索到的適應度最好的一個解,得到所有傳感節點優化部署后的分布位置。

4.1 算法步驟

Step 1 設置算法a、A、C等參數,種群規模m,迭代次數t。

Step 2 根據3.1節所述方法對初始種群進行混沌初始化,設t=1。

Step 3 計算初始群體中每個灰狼個體的適應度值,選取適應度值前三的個體并分別設置為Xα、Xβ和Xδ。

Step 4 由式(15)更新每個灰狼位置。

Step 5 計算種群每個灰狼適應度值,并更新Xα、Xβ和Xδ。

Step 6 根據3.3所述對δ狼進行融合變異。

Step 7 根據式(18)更新a的值,根據式(6)和式(7)更新A和C的值。

Step 8 判斷是否滿足算法結束條件。若不 滿足,則t=t+1,返回Step 4;若滿足,則算法結束,輸出Xα。

4.2 算法流程圖

根據上述內容,IGWO可應用于WSN節點部署中的覆蓋率優化問題。以式(4)為目標函數進行優化,可得到滿足各約束條件的覆蓋優化后的各節點分布位置。

具體流程如圖1所示。

圖1 IGWO覆蓋優化流程圖

5 仿真實驗與分析

假設在面積S=50 m×50 m的待檢測區域。所有傳感節測量半徑為r=5 m,通訊半徑為rs=15 m,最大迭代次數tmax=100,其余參數設置為ainitial=2,μ=10,k=4,D=0.15。實驗中40個無線傳感節點均為移動傳感節點。使用MATLAB在主頻為2.3 GHz的PC機上進行無線傳感網絡優化部署仿真。

圖2 最大迭代次數與覆蓋率

圖2為采用初始隨機拋撒后,標準算法灰狼優化算法與改進灰狼優化算法的進行覆蓋優化后的覆蓋率對比圖。經兩種算法優化后的節點覆蓋率較初始部署覆蓋率均有大幅提高。節點數量為70時,IGWO優化算法與GWO算法均能使覆蓋率接近100%。在節點數量為40時,IGWO算法對目標區域的覆蓋率與GWO算法的覆蓋率差值較大。在目標區域內拋撒40個傳感器節點,分別采用標準灰狼優化算法和改進灰狼優化算對無線傳感網節點部署進行優化后的結果如圖4和圖5所示,優化用時分別為:147.7 s和158.6 s,改進后灰狼優化算法優化用時增加主要為算法種群初始化計算用時增加,改進后灰狼優化算法在一定程度上提高了算法復雜度。兩者對待測區域覆蓋率分別為91.16%,94.28%,改進灰狼算法對比標準灰狼優化算法覆蓋率提升了3.12%。節點在待測區域內分布更加均勻,改善了部分區域節點聚集過于的情況。改進灰狼優化算法與標準灰狼優化算法相比在收斂速度上也得到了提升,如圖6所示。

圖6 算法優化后覆蓋率對比

圖3 初始部署

圖4 GWO優化覆蓋

圖5 IGWO優化覆蓋

上述仿真實驗結果表明,改進灰狼優化算法應用適應性強,收斂速度快。應用于無線傳感網絡節點部署優化問題,能快速有效的提升網絡覆蓋率,減少覆蓋盲區。在同樣的覆蓋率要求下,所需節點數量較少,能降低網絡構建成本。

6 結束語

本文在標準灰狼優化算法的基礎上,使用混沌映射進行種群初始化提高灰狼種群多樣性以加強算法全局搜索能力;利用改進的非線性收斂因子以平衡算法的搜索和開發能力;將第三優解進行融合變異以減小算法陷入局部最優的可能。并將改進灰狼優化算法應用于WSN的覆蓋優化問題中。仿真實驗結果表明,改進后的灰狼優化算法能在一定程度上提高無線傳感網絡性能。在應用過程中出現算法優化結果不穩定的現象,今后的研究方向應進一步提高算法穩定性,并將在綜合考慮網絡節點移動距離與環境因素的前提下完成傳感器節點部署。

參考文獻:

[1] Wang Y,Wang R C,Cheng X. Improved Multipath Routing with WNN for the Open Networks[J]. 中國郵電高校學報(英文版),2008,15(2):107-113.

[2] 吳意樂,何慶,徐同偉. 改進自適應粒子群算法在WSN覆蓋優化中的應用[J]. 傳感技術學報,2016,29(4):559-565.

[3] Mirjalili S,Mirjalili S M,Lewis A. Grey Wolf Optimizer[J]. Advances in Engineering Software,2014,69(3):46-61.

[4] 姚鵬,王宏倫. 基于改進流體擾動算法與灰狼優化的無人機三維航路規劃[J]. 控制與決策,2016,31(4):701-708.

[5] Sulaiman M H,Mustaffa Z,Mohamed M R,et al. Using the Grey Wolf Optimizer for Solving Optimal Reactive Power Dispatch Problem[J]. Applied Soft Computing,2015,32(C):286-292.

[6] Madadi A,Motlagh M. Optimal Control of DC Motor Using Grey Wolf Optimizer Algorithm[J]. Technical Journal of Engineering and Applied Science,2014,4(4):373-379.

[7] Song X,Tang L,Zhao S,et al. Grey Wolf Optimizer for Parameter Estimation in Surface Waves[J]. Soil Dynamics and Earthquake Engineering,2015,75:147-157.

[8] Song H M,Sulaiman M H,Mohamed M R. An Application of Grey Wolf Optimizer for solving combined economic emission dispatch Problems[J]. International Review on Modelling and Simulations,2014,7(5):838-844.

[9] Mahdad B,Srairi K. Blackout Risk Prevention in a Smart Grid Based Flexible Optimal Strategy Using Grey Wolf-Pattern Search Algorithms[J]. Energy Conversion and Management,2015,98:411-429.

[10] Nasrabadi M S,Sharafi Y,Tayari M. A Parallel Grey Wolf Optimizer Combined with Opposition Based Learning[C]//Swarm Intelligence and Evolutionary Computation. IEEE,2016:18-23.

[11] 郭振洲,劉然,拱長青. 基于灰狼算法的改進研究[J]. 計算機應用研究,2017(12):1-8.

[12] Haupt R,Haupt S. Practical Genetic Algorithm[M]. New York:John Wiley and Sons,2004:38-39.

[13] Ragulskis M,Vainoras A,Smidtaite R,et al. The Logistic Map of Matrices[J]. Discrete and Continuous Dynamical Systems-Series B(DCDS-B),2017,16(3):927-944.