改進的自適應灰狼算法在無線傳感網(wǎng)絡覆蓋中的應用

張雪 秦宇祺 張倩倩 黃鵬

摘 要：根據(jù)無線傳感器網(wǎng)絡（WSN）節(jié)點在隨機部署時存在聚集程度高導致覆蓋率低的問題，提出一種改進的自適應灰狼優(yōu)化算法，并將其應用于無線傳感器網(wǎng)絡節(jié)點的優(yōu)化覆蓋。首先，建立WSN覆蓋優(yōu)化的數(shù)學模型;其次，在灰狼優(yōu)化（GWO）算法中，使用一種非線性收斂因子公式，動態(tài)調整算法的全局搜索能力;最后，利用自適應調整策略提高GWO算法的收斂速度。仿真實驗表明，將改進的自適應灰狼優(yōu)化算法應用于無線傳感器網(wǎng)絡覆蓋優(yōu)化中，比標準灰狼優(yōu)化算法效果更好，有更快的優(yōu)化速度，并且網(wǎng)絡覆蓋率有些許提高。

關鍵詞：無線傳感器網(wǎng)絡; 覆蓋率;灰狼優(yōu)化算法;非線性收斂因子;自適應;數(shù)學模型

中圖分類號：TP393文獻標識碼：A文章編號：2095-1302（2019）10-00-04

0 引 言

隨著計算機網(wǎng)絡技術的迅速發(fā)展，無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）應運而生。由大量能量有限的傳感器節(jié)點以自組織和多跳的方式構成的無線傳感器網(wǎng)絡以協(xié)作感知、采集、處理傳感網(wǎng)絡覆蓋區(qū)域被感知對象的信息，并最終把這些信息發(fā)送至網(wǎng)絡所有者。覆蓋控制一直是無線傳感器網(wǎng)絡的重要問題，它反映了一個無線傳感器網(wǎng)絡某區(qū)域被檢測和跟蹤的狀況。覆蓋控制能夠合理分配網(wǎng)絡資源，從而優(yōu)化網(wǎng)絡覆蓋性能[1-2]。近年來，WSN廣泛應用于軍事、智能交通、環(huán)境監(jiān)控、醫(yī)療衛(wèi)生等領域。但在實際應用中，因為物理環(huán)境有所限制，傳感器節(jié)點多采用隨機部署的方式進行播撒，因此存在覆蓋盲區(qū)，不能有效覆蓋待監(jiān)測區(qū)域，從而影響整個無線網(wǎng)絡的監(jiān)控能力。對WSN網(wǎng)絡來說，能夠及時檢測網(wǎng)絡覆蓋率是否最優(yōu)并做出有效調整是基本問題，若此問題能夠得到有效解決，則網(wǎng)絡中數(shù)據(jù)的傳輸質量能夠明顯提高，從而減少網(wǎng)絡資源浪費，延長生命周期[3]。

群體智能算法提出了新的思路來解決WSN覆蓋優(yōu)化問題，近年來大量學者將群體智能算法應用于WSN覆蓋控制中并研究其性能[4-5]。文獻[6]采用遺傳算法優(yōu)化WSN覆蓋網(wǎng)絡，優(yōu)化效果較好，但是算法整體上偏復雜，收斂速度較慢。文獻[7]提出一種基于劃分搜索空間的粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法，該算法全局收斂能力強，能夠快速找到覆蓋率較高的WSN網(wǎng)絡部署模型，但是算法優(yōu)化后極易陷入局部最優(yōu)。文獻[8]將變異因子引入適應度差的魚群個體中，提出一種改進的人工魚群算法，在WSN網(wǎng)絡覆蓋優(yōu)化中取得了較好的優(yōu)化效果，提高了網(wǎng)絡覆蓋率，但是節(jié)點覆蓋冗余度較高。

近幾年，大量學者比較關注灰狼優(yōu)化（Grey Wolf Optimizer，GWO）算法?；依莾?yōu)化算法是Mirjalili[9]等人于2014年提出的一種新的群體智能算法，具有模型簡單、參數(shù)設置較少、尋優(yōu)性能較好等優(yōu)點。研究結果表明，GWO算法明顯比PSO算法和遺傳算法的優(yōu)化性能更好。因此，GWO算法在多傳感器訓練[10]、面波參數(shù)優(yōu)化[11]、K-均值聚類優(yōu)化[12]等領域中有著廣泛應用。

雖然GWO算法得到了廣泛關注，但也存在一些缺點，如收斂速度慢、全局搜索能力弱等，且在不斷迭代中，GWO算法易陷入局部最優(yōu)。因此，本文提出一種改進的自適應灰狼優(yōu)化（Self-Adaption Grey Wolf Optimizer，SAGWO）算法，將非線性收斂因子引入GWO算法，以此平衡算法的局部搜索精度與全局搜索能力，并結合適應度構造自適應位置更新策略，提高算法收斂速度。將改進的SAGWO算法應用于無線傳感網(wǎng)絡覆蓋中，并通過實驗與基本GWO進行比較。從實驗結果可看出，改進的SAGWO算法性能更好，優(yōu)化效果更好。

1 WSN覆蓋模型

無線傳感器網(wǎng)絡中每個傳感節(jié)點的覆蓋范圍都以自身為中心，有著固定半徑的圓形區(qū)域，因此所有傳感器節(jié)點對監(jiān)測區(qū)域的總覆蓋率用公式求解比較困難。為了簡化區(qū)域內的覆蓋率求解問題，待監(jiān)測區(qū)域可被離散化為m×n個像素點，假設有x個像素點被無線傳感器網(wǎng)絡覆蓋，則覆蓋率可表示為x/（m×n）。

假設WSN網(wǎng)絡中每個傳感器節(jié)點的測量半徑r與通信半徑rs相同，且每個傳感器節(jié)點覆蓋范圍是半徑為r的圓形區(qū)域。被測區(qū)域是二維平面M，將這個二維平面離散化為m×n個像素點，無線傳感器網(wǎng)絡中有N個傳感器節(jié)點，被測區(qū)域內傳感器節(jié)點集合為，

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

灰狼算法是受到狼群獵食行為的啟發(fā)，通過模仿狼群中的等級制度與獵食策略提出的一種智能優(yōu)化算法。

視種群中每個個體為一個解，在D維搜索空間中，第i只灰狼個體的位置為，i=1， 2， ...， N，N為種群規(guī)模，選擇當前最優(yōu)解、次最優(yōu)解、第三最優(yōu)解所在的狼（分別標記為α，β，δ狼，其余個體標記為ω狼），獵食過程中，狼群在α，β，δ狼的引導下，向食物位置（全局最優(yōu)解）逼近。

3 改進的SAGWO算法

3.1 非線性收斂因子策略

群體智能算法都存在易陷入局部最優(yōu)的問題，種群的多樣性通過全局搜索能力來保證。而局部搜索能力強則能夠保證算法對于局部的精確搜索，且大大加快了算法的優(yōu)化速度。因此，灰狼優(yōu)化算法中的全局搜索能力和局部搜索能力之間的平衡極其重要。

采用非線性收斂策略，GWO算法的收斂因子a隨著迭代次數(shù)呈非線性遞減，在初期將a的衰減程度降低，可更好地找到全局最優(yōu)解，而到了后期，將a的衰減程度提高，則能夠更加準確地找到局部最優(yōu)解，避免陷入局部最優(yōu)。

3.2 自適應調整策略

GWO算法中適應度值是重要參數(shù)。在灰狼個體進行尋優(yōu)的過程中，α，β，δ的位置對于尋找全局最優(yōu)的重要性不言而喻。但在GWO算法中，位置更新時并未表現(xiàn)出α，β，δ之間真實的相對關系，僅僅簡單地求解其平均值，使搜索范圍擴大，減緩了優(yōu)化速度。

4 SAGWO算法用于WSN覆蓋優(yōu)化

本文設計的改進的SAGWO算法的優(yōu)化目標：求解無線傳感器網(wǎng)絡覆蓋優(yōu)化的目標函數(shù)的最大值，輸出SAGWO優(yōu)化后的覆蓋率，得到待測區(qū)域內所有傳感節(jié)點優(yōu)化部署后的分布位置。

灰狼種群中包含多個灰狼個體，且每個灰狼個體擁有相同的維數(shù)，待測區(qū)域為二維平面，則灰狼個體的維數(shù)為傳感節(jié)點數(shù)的2倍，其中第2d-1維表示第d個傳感器節(jié)點的橫坐標，第2d維表示第d個傳感器節(jié)點的縱坐標。

4.1 算法步驟

WSN覆蓋優(yōu)化步驟如下。

（1）設置算法參數(shù)：種群規(guī)模N、最大迭代次數(shù)tmax及a，A，C等參數(shù)。

（2）初始化種群X（x1， x2， ...， xD），即隨機產(chǎn)生N個智能個體的位置。

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

（4）通過式（8）計算控制參數(shù)a的值，根據(jù)式（5）更新A，C的值。

（5）由式（9）更新位置。

（6）再次計算每個灰狼適應度值，并更新Xα，Xβ，Xδ，然后選取適應度值較好的灰狼個體。

（7）判斷是否滿足結束條件。若不滿足，則迭代次數(shù)加1，返回（3）;若滿足，則結束，并輸出Xα。

4.2 算法流程

SAGWO算法覆蓋優(yōu)化流程如圖1所示。

5 仿真實驗與分析?

5.1 實驗環(huán)境

為了驗證本文基于改進的SAGWO算法WSN覆蓋優(yōu)化的性能進行仿真實驗。實驗的運行環(huán)境為Intel? CoreTM i5-4210U CPU @ 1.70 GHz，2.39 GHz，內存8 GB，Windows 1064位操作系統(tǒng)，仿真軟件采用Matlab R2016a。

5.2 參數(shù)設置與實驗結果分析

設監(jiān)測區(qū)域為50 m×50 m的二維平面，將該區(qū)域離散化為26×26個像素點。無線傳感器節(jié)點數(shù)為70，節(jié)點的感知半徑r =5 m，通信半徑[17]rs=2r =10 m，算法最大迭代次數(shù)Max_iteration=200。

無線傳感器網(wǎng)絡節(jié)點隨機部署后，標準GWO算法與改進的SAGWO算法進行迭代優(yōu)化后的覆蓋率對比如圖2所示。初始部署如圖3所示，GWO優(yōu)化覆蓋如圖4所示，SAGWO優(yōu)化覆蓋如圖5所示。可以看出，經(jīng)兩種算法優(yōu)化后的節(jié)點覆蓋率均有明顯提高，SAGWO算法的節(jié)點覆蓋率甚至達到95%以上。

GWO算法優(yōu)化后的覆蓋率為92.24%，而SAGWO算法優(yōu)化后的覆蓋率為97.78%，SAGWO算法對比GWO算法覆蓋率提升了5.54%，節(jié)點在待測區(qū)域內分布較均勻，但仍有部分區(qū)域節(jié)點過于聚集。

由于SAGWO算法中引入了非線性收斂因子和自適應位置更新策略，在優(yōu)化無線傳感器節(jié)點覆蓋率上表現(xiàn)優(yōu)異，具有優(yōu)越的全局尋優(yōu)能力，避免陷入局部最優(yōu)（即早熟），同時，收斂速度也明顯提高，當?shù)螖?shù)達到30代時，已找到較為優(yōu)異的值。

從上述實驗結果可以看出，SAGWO算法適應性強，優(yōu)化速度較快，將該算法應用于無線傳感網(wǎng)絡覆蓋優(yōu)化問題中，能夠使網(wǎng)絡覆蓋率得到明顯提高，從而減少覆蓋盲區(qū)。

6 結 語

本文分析了GWO算法的基本原理和不足之處，在此基礎上提出一種改進的SAGWO算法，該算法引入非線性收斂因子，以此避免陷入局部最優(yōu)，加強了全局搜索能力。同時，結合適應度值，提出自適應位置調整策略，加快了算法的收斂速度，并將SAGWO算法應用于無線傳感器網(wǎng)絡的節(jié)點部署問題中。實驗結果表明，SAGWO算法有效避免了陷入局部最優(yōu)，且加快了收斂速度，對比基本GWO算法，SAGWO算法對無線傳感器網(wǎng)絡優(yōu)化后的覆蓋率提升了5%，應用適應性強。因此，本文設計的SAGWO算法在一定程度上提高了WSN網(wǎng)絡的覆蓋性能，但在應用過程中出現(xiàn)了部分區(qū)域節(jié)點過于聚集的情況，今后的研究方向應使WSN覆蓋更為均勻，減少節(jié)點聚集的區(qū)域。

參 考 文 獻

[1] WANG B.Coverage problems in sensor networks： a survey [J]. ACM computing surveys，2011，43（4）： 1-53.

[2]周則順.無線傳感器網(wǎng)絡覆蓋與連通優(yōu)化算法的研究[D].武漢：武漢理工大學，2013.

[3] WANG Y，WANG R C，CHENG X.Improved multipath routing with WNN for the open networks [J]. The journal of China universities of posts and telecommunications，2008，15（2）： 107-113.

[4] YOON Y，KIM Y-H.An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks [J]. IEEE transactions on cybernetics，2013，43（5）： 1473-1483.

[5] AKBARZADEH V，GAGNE C，PARIZEAU M，et al. Probabilistic sensing model for sensor placement optimization based on line-of-sight coverage [J]. IEEE transactions on instrumentation and measurement，2013，62（2）： 293-303.

[6]賈杰，陳劍，常桂然，等.無線傳感器網(wǎng)絡中基于遺傳算法的優(yōu)化覆蓋機制[J].控制與決策，2007，22（11）： 1289-1292.

[7]曹劍煒，陳慶奎，莊松林，等.UPSO：基于劃分空間粒子群優(yōu)化的WSN動態(tài)覆蓋優(yōu)化算法[J].計算機科學，2014，41（6）： 255-257.

[8]王明亮，閔新力，薛君志.基于改進人工魚群算法的WSN覆蓋優(yōu)化策略[J].微電子學與計算機，2015，32（6）： 78-81.

[9] MIRJALILI S，MIRJLILI S M，LEWIS A. Grey wolf optimizer [J]. Advances in engineering software，2014，69（7）：46-61.

[10] MIRJALILI S. How effective is the grey wolf optimizer in training multilayer perceptrons [J]. Applied intelligent，2015，42（2）：608-619.

[11] 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（5）：147-157.

[12]楊紅光，劉建生.一種結合灰狼優(yōu)化和K-均值的混合聚類算法[J].江西理工大學學報，2015，36（5）：85-89.

[13]張娟.基于粒子群優(yōu)化算法的無線傳感器網(wǎng)絡節(jié)能覆蓋研究[D].上海：華東理工大學，2014.

[14] PANDA G，PRADHAM P M，MAJHI B.IIR system identification using cat swarm optimization [J]. Expert systems with applications，2011，38（10）：12671-12683.

[15]郭振州，劉然，拱長青，等.基于灰狼算法的改進研究[J].計算機應用研究，2017，34（12）：3603.

[16]張悅，孫惠香，魏政磊，等.具有自適應調整策略的混沌灰狼優(yōu)化算法[J].計算機科學，2017，44（11A）： 119-122.

[17] ZHANG H，HOU J.Maintaining sensing coverage and connectivity in large sensor networks [J]. Ad Hoc & sensor wireless networks，2005，1（2）：89-124.