改進(jìn)灰狼優(yōu)化算法在WSN節(jié)點(diǎn)部署中的應(yīng)用*

胡小平,曹 敬

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

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

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

標(biāo)準(zhǔn)灰狼優(yōu)化算法在應(yīng)用于優(yōu)化問題時存在中后期收斂速度慢且容易陷入局部極值問題[13]。文獻(xiàn)[14]認(rèn)為,提高初始種群的多樣性有助于提高搜索算法的搜索效率。而混沌算法具非線性系統(tǒng)的特點(diǎn),具有非重復(fù)性與遍歷性的特點(diǎn)?；煦缢惴ㄒ敕N群初始化,利用其特點(diǎn)生成初始種群以提高初始種群多樣性,為全局搜索提供基礎(chǔ);此外,使用改進(jìn)的非線性收斂因子代替標(biāo)準(zhǔn)灰狼優(yōu)化算法中的線性收斂因子,以提高算法中后期的搜索能力加快收斂速度;最后,對第三優(yōu)解進(jìn)行融合變異,以加快搜索速度和避免陷入局部最優(yōu)解。并將改進(jìn)灰狼優(yōu)化算法應(yīng)用于無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)部署問題,開展改進(jìn)算法的仿真分析。

1 節(jié)點(diǎn)與覆蓋模型

(1)

任一目標(biāo)點(diǎn)可以被多個傳感節(jié)點(diǎn)同時檢測,則對目標(biāo)點(diǎn)的聯(lián)合測量概率為:

(2)

式中:gov為測量目標(biāo)點(diǎn)的傳感器集合。所有節(jié)點(diǎn)對待檢測區(qū)域的覆蓋率為:

(3)

式(3)覆蓋率函數(shù)值的最大化為無線傳感網(wǎng)絡(luò)覆蓋模型的優(yōu)化目標(biāo)。

若無線傳感網(wǎng)絡(luò)中的兩節(jié)點(diǎn)間距離不大于通信半徑,則認(rèn)為兩節(jié)點(diǎn)間存在一條通信路徑。定義Hij為任意兩節(jié)點(diǎn)i與j之間的通信路徑數(shù)量。滿足網(wǎng)絡(luò)連通要求的約束為:Hij≥1。同時,所有的節(jié)點(diǎn)位置應(yīng)處于待監(jiān)測目標(biāo)區(qū)域內(nèi),可表示為:L(gi)∈M。

綜上所述目標(biāo)函數(shù)為:

(4)

2 灰狼優(yōu)化算法基本原理

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

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

(5)

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

(6)

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

A=2ar1-a

(7)

C=2r2

(8)

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

a=2-2t/tmax

(9)

式中:tmax為最大迭代次數(shù)。

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

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)

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

3 改進(jìn)灰狼優(yōu)化算法

3.1 混沌初始化

混沌是一種確定的、隨機(jī)的非線性動力系統(tǒng),具有非周期性、不收斂和有界的特點(diǎn)。自上個世紀(jì)以來混沌映射在優(yōu)化算法領(lǐng)域得到了廣泛的重視。因為其動態(tài)隨機(jī)特性,能使優(yōu)化算法在搜索區(qū)域進(jìn)行更有效的的全局搜索。

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

(17)

(18)

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

3.2 非線性收斂因子

啟發(fā)式算法在需要在搜索能力和開發(fā)能力之間保持良好的平衡,從而實(shí)現(xiàn)有效的全局和局部搜索。搜索能力即尋找新的適應(yīng)度更高的個體的能力;開發(fā)能力即為在當(dāng)前最優(yōu)解位置附近尋找更優(yōu)的解的能力。

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

(19)

式中:ainitial為a給定的初始值;常數(shù)μ為非線性調(diào)節(jié)系數(shù);常數(shù)k的值影響算法搜索和開發(fā)能力,k值越小則在最優(yōu)解附近搜索新的最優(yōu)解能力越強(qiáng)。實(shí)際應(yīng)用中,可根據(jù)具體優(yōu)化問題,調(diào)節(jié)收斂因子相關(guān)系數(shù)從而平衡算法搜索能力與開發(fā)能力,提高算法搜索效率。

3.3 δ狼的融合變異

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

(20)

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

4 節(jié)點(diǎn)部署優(yōu)化算法

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

4.1 算法步驟

Step 1 設(shè)置算法a、A、C等參數(shù),種群規(guī)模m,迭代次數(shù)t。

Step 2 根據(jù)3.1節(jié)所述方法對初始種群進(jìn)行混沌初始化,設(shè)t=1。

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

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

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

Step 6 根據(jù)3.3所述對δ狼進(jìn)行融合變異。

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

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

4.2 算法流程圖

根據(jù)上述內(nèi)容,IGWO可應(yīng)用于WSN節(jié)點(diǎn)部署中的覆蓋率優(yōu)化問題。以式(4)為目標(biāo)函數(shù)進(jìn)行優(yōu)化,可得到滿足各約束條件的覆蓋優(yōu)化后的各節(jié)點(diǎn)分布位置。

具體流程如圖1所示。

圖1 IGWO覆蓋優(yōu)化流程圖

5 仿真實(shí)驗與分析

假設(shè)在面積S=50 m×50 m的待檢測區(qū)域。所有傳感節(jié)測量半徑為r=5 m,通訊半徑為rs=15 m,最大迭代次數(shù)tmax=100,其余參數(shù)設(shè)置為ainitial=2,μ=10,k=4,D=0.15。實(shí)驗中40個無線傳感節(jié)點(diǎn)均為移動傳感節(jié)點(diǎn)。使用MATLAB在主頻為2.3 GHz的PC機(jī)上進(jìn)行無線傳感網(wǎng)絡(luò)優(yōu)化部署仿真。

圖2 最大迭代次數(shù)與覆蓋率

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

圖6 算法優(yōu)化后覆蓋率對比

圖3 初始部署

圖4 GWO優(yōu)化覆蓋

圖5 IGWO優(yōu)化覆蓋

上述仿真實(shí)驗結(jié)果表明,改進(jìn)灰狼優(yōu)化算法應(yīng)用適應(yīng)性強(qiáng),收斂速度快。應(yīng)用于無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)部署優(yōu)化問題,能快速有效的提升網(wǎng)絡(luò)覆蓋率,減少覆蓋盲區(qū)。在同樣的覆蓋率要求下,所需節(jié)點(diǎn)數(shù)量較少,能降低網(wǎng)絡(luò)構(gòu)建成本。

6 結(jié)束語

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

參考文獻(xiàn):

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

[2] 吳意樂,何慶,徐同偉. 改進(jìn)自適應(yīng)粒子群算法在WSN覆蓋優(yōu)化中的應(yīng)用[J]. 傳感技術(shù)學(xué)報,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ìn)流體擾動算法與灰狼優(yōu)化的無人機(jī)三維航路規(guī)劃[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ìn)研究[J]. 計算機(jī)應(yīng)用研究,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.