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

張雪 秦宇祺 張倩倩 黃鵬

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

關鍵詞：無線傳感器網絡; 覆蓋率;灰狼優化算法;非線性收斂因子;自適應;數學模型

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

0 引 言

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

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

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

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

1 WSN覆蓋模型

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

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

2 基本灰狼優化算法 ? ?

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

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

3 改進的SAGWO算法

3.1 非線性收斂因子策略

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

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

3.2 自適應調整策略

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

4 SAGWO算法用于WSN覆蓋優化

本文設計的改進的SAGWO算法的優化目標：求解無線傳感器網絡覆蓋優化的目標函數的最大值，輸出SAGWO優化后的覆蓋率，得到待測區域內所有傳感節點優化部署后的分布位置。

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

4.1 算法步驟

WSN覆蓋優化步驟如下。

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

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

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

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

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

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

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

4.2 算法流程

SAGWO算法覆蓋優化流程如圖1所示。

5 仿真實驗與分析?

5.1 實驗環境

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

5.2 參數設置與實驗結果分析

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

無線傳感器網絡節點隨機部署后，標準GWO算法與改進的SAGWO算法進行迭代優化后的覆蓋率對比如圖2所示。初始部署如圖3所示，GWO優化覆蓋如圖4所示，SAGWO優化覆蓋如圖5所示?？梢钥闯?，經兩種算法優化后的節點覆蓋率均有明顯提高，SAGWO算法的節點覆蓋率甚至達到95%以上。

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

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

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

6 結 語

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

參 考 文 獻

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

[2]周則順.無線傳感器網絡覆蓋與連通優化算法的研究[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]賈杰，陳劍，常桂然，等.無線傳感器網絡中基于遺傳算法的優化覆蓋機制[J].控制與決策，2007，22（11）： 1289-1292.

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

[8]王明亮，閔新力，薛君志.基于改進人工魚群算法的WSN覆蓋優化策略[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]楊紅光，劉建生.一種結合灰狼優化和K-均值的混合聚類算法[J].江西理工大學學報，2015，36（5）：85-89.

[13]張娟.基于粒子群優化算法的無線傳感器網絡節能覆蓋研究[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]張悅，孫惠香，魏政磊，等.具有自適應調整策略的混沌灰狼優化算法[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.