胡小平,曹 敬

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

無線傳感網(wǎng)絡(luò)是由一定規(guī)模的終端傳感節(jié)點通過無線通信的方式組成的一種自組織網(wǎng)絡(luò)。傳感器節(jié)點通常具有通信、計算、感知等能力,通過對其規(guī)?；渴鹦纬傻臒o線傳感網(wǎng)絡(luò)具有對監(jiān)測區(qū)域進行監(jiān)控的能力。無線傳感網(wǎng)絡(luò)中單個節(jié)點僅承擔部分檢測任務(wù),單個節(jié)點故障對網(wǎng)絡(luò)的整體監(jiān)測能力影響較小,且節(jié)點之間進行無線通信無需要人工鋪設(shè)線纜擁有更好的連接便利性。因此,通過大量節(jié)點部署后組織的無線傳感網(wǎng)絡(luò)擁有良好的容錯能力和斷接性能等特點。近年來,無線傳感網(wǎng)絡(luò)廣泛運用于輔助農(nóng)業(yè)生產(chǎn)、環(huán)境監(jiān)測、物流和智能家電領(lǐng)域。在應(yīng)用過程中,傳感器節(jié)點多采取隨機拋灑的部署方式,由于部署位置隨機,使其存在覆蓋盲區(qū),難以有效覆蓋待監(jiān)測區(qū)域,從而影響網(wǎng)絡(luò)的監(jiān)控能力。監(jiān)測區(qū)域環(huán)境變化和傳感器節(jié)點可移動性改變等因素會降低網(wǎng)絡(luò)覆蓋率從而影響其監(jiān)控能力。因此,需要對無線傳感網(wǎng)中傳感器節(jié)點的進行自適應(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)化算法是由學者Mirjalili等人于2014年提出了一種新的群智能算法,文獻[3]表明,在基準函數(shù)求解問題上,GWO算法與粒子群算法PSO(Particle Swarm Optimization)算法、(差分進化算法DE(Differential Evolution)算法和萬有引力算法GSA(Gravitational Search Algorithm)算法相比擁有更高的精度和穩(wěn)定性。國內(nèi)外學者對灰狼優(yōu)化算法進行了大量的研究:姚鵬等人將灰狼優(yōu)化算法與流體擾動算法結(jié)合應(yīng)用于無人機三維航路規(guī)劃得到了平滑性和可飛性高的三維航路[4];Sulaiman等人研究了灰狼算法在最優(yōu)無功電力調(diào)度問題上的應(yīng)用,表明與其他技術(shù)相比灰狼算法能實現(xiàn)更小的功率損耗和電壓偏差[5];Madadi等人利用灰狼優(yōu)化算法對直流電機PID控制器參數(shù)進行優(yōu)化,相比PSO算法提高了控制的穩(wěn)定性[6];Song等人將GWO應(yīng)用于表面波色散曲線反演,與遺傳算法相比GWO算法減少了控制參數(shù)的同時提高了收斂速度[7];HM Song將灰狼優(yōu)化算法引入電力系統(tǒng)的組合經(jīng)濟排放調(diào)度問題,以此得到了最佳的發(fā)電方式[8];Mahdad等人將灰狼優(yōu)化算法應(yīng)用于電力控制系統(tǒng)以減小停電風險,通過實際測試證明了該方法的安全性和可行性[9];針對在應(yīng)用過程中灰狼優(yōu)化算法出現(xiàn)的中后期收斂速度慢和易陷入局部極值的問題。Nasrabadi 等人通過并行和反向?qū)W習改進灰狼優(yōu)化算法,提高了算法在解決基準函數(shù)求解問題上的速度和精度[10];郭振洲等人將非線性收斂因子與動態(tài)權(quán)重引入灰狼優(yōu)化算法,加快了算法收斂速度[11];徐松金等人利用佳點集理論初始化種群,在迭代過程中引入算術(shù)交叉和多樣性變異操作以避免算法陷入局部最優(yōu)解并增強算法的局部搜索能力,其改進算法在較高維度函數(shù)求解問題上對比標準灰狼優(yōu)化算法擁有明顯優(yōu)勢[12]。

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

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

(1)

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

(2)

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

(3)

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

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

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

(4)

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

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

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

(5)

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

(6)

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

A=2ar1-a

(7)

C=2r2

(8)

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

a=2-2t/tmax

(9)

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

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

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)對灰狼個體進行更新。

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

3.1 混沌初始化

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

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

(17)

(18)

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

3.2 非線性收斂因子

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

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

(19)

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

3.3 δ狼的融合變異

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

(20)

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

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

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

4.1 算法步驟

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

Step 2 根據(jù)3.1節(jié)所述方法對初始種群進行混沌初始化,設(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所述對δ狼進行融合變異。

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é)點部署中的覆蓋率優(yōu)化問題。以式(4)為目標函數(shù)進行優(yōu)化,可得到滿足各約束條件的覆蓋優(yōu)化后的各節(jié)點分布位置。

具體流程如圖1所示。

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

5 仿真實驗與分析

假設(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。實驗中40個無線傳感節(jié)點均為移動傳感節(jié)點。使用MATLAB在主頻為2.3 GHz的PC機上進行無線傳感網(wǎng)絡(luò)優(yōu)化部署仿真。

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

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

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

圖3 初始部署

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

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

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

6 結(jié)束語

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

參考文獻:

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

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