虛擬導(dǎo)向的改進(jìn)灰狼算法綜合無線傳感器網(wǎng)絡(luò)布局

秦宇祺 張雪 張倩倩 黃鵬

摘 要：為了提高無線傳感網(wǎng)絡(luò)覆蓋率和目標(biāo)檢測概率，動態(tài)無線傳感網(wǎng)絡(luò)布局優(yōu)化成為無線傳感器網(wǎng)絡(luò)覆蓋研究的關(guān)鍵。由于傳統(tǒng)的灰狼算法在優(yōu)化過程中難以協(xié)調(diào)全局探索和局部開發(fā)能力，文中將基本灰狼算法（GWO）與Logistic序列變異，并與干擾粒子相結(jié)合，采取一種從整體到局部的優(yōu)化策略，同時學(xué)習(xí)虛擬力算法在指導(dǎo)無線傳感節(jié)點散步過程中的優(yōu)越性，對狼群位置更新機制做出一些改進(jìn)，提出一種虛擬導(dǎo)向的改進(jìn)灰狼算法，在有效提高網(wǎng)絡(luò)覆蓋率的同時，提高算法的收斂速度和收斂精度。

關(guān)鍵詞：GWO;動態(tài)網(wǎng)絡(luò)布局;Logistic序列變異;干擾粒子;虛擬力;傳感器

中圖分類號：TP39;TN911.72文獻(xiàn)標(biāo)識碼：A文章編號：2095-1302（2019）09-000-05

0 引 言

隨著無線通信技術(shù)、嵌入式計算技術(shù)、傳感器技術(shù)、微電子技術(shù)的高速發(fā)展，無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）應(yīng)運而生[1]。無線傳感器網(wǎng)絡(luò)以其低功耗、低成本、分布式、自組織等特點為信息感知帶來一場新的變革，被廣泛運用于目標(biāo)跟蹤和環(huán)境監(jiān)測等領(lǐng)域。由于傳感器節(jié)點的能量有限及其應(yīng)用區(qū)域的特殊性，為了增強無線傳感器網(wǎng)絡(luò)的監(jiān)測質(zhì)量、提高網(wǎng)絡(luò)可靠性，動態(tài)無線傳感器網(wǎng)絡(luò)布局優(yōu)化已成為無線傳感器網(wǎng)絡(luò)性能優(yōu)化的關(guān)鍵[2]。

近年來，研究人員嘗試從不同角度解決傳感器節(jié)點位置優(yōu)化問題，在文獻(xiàn)[3]中，研究了基于移動機器人的節(jié)點部署算法—假設(shè)節(jié)點均具有準(zhǔn)確定位能力，利用已有信息部署后續(xù)節(jié)點。但由于依次部署會導(dǎo)致較長延時，因此不具有普遍性。文獻(xiàn)[4-5]中提出了改進(jìn)的混合無線傳感器網(wǎng)絡(luò)節(jié)點分布優(yōu)化算法，文獻(xiàn)[6]中提出了一種基于虛擬力的節(jié)點分布優(yōu)化算法（Virtual Force Algorithm，VFA），該算法將每個傳感器節(jié)點近似為一個虛擬電荷，建立傳感器節(jié)點與目標(biāo)、其他傳感器節(jié)點間的虛擬力模型，根據(jù)受力平衡，各點受到其他點的虛擬力作用，向目標(biāo)區(qū)域擴散，最終達(dá)到平衡狀態(tài)，從而實現(xiàn)網(wǎng)絡(luò)充分覆蓋。與上述其他算法相比，該算法具有更快的運算速度，在提高網(wǎng)絡(luò)覆蓋率性能方面表現(xiàn)突出。然而對于由固定傳感節(jié)點和移動傳感節(jié)點構(gòu)成的無線傳感網(wǎng)絡(luò)，固定傳感節(jié)點對移動傳感節(jié)點的虛擬力可能會限制無線傳感網(wǎng)絡(luò)的布局優(yōu)化。針對上述問題，本文結(jié)合灰狼算法和虛擬力算法，提出了一種虛擬導(dǎo)向的改進(jìn)灰狼算法。

灰狼算法作為一種新型智能進(jìn)化算法，已經(jīng)被證明與粒子群算法（Particle Swarm Optimization，PSO）、引力搜索算法（Gravitational Search Algorithm，GSA）相比性能更優(yōu)，同時具有模型簡單、參數(shù)設(shè)置較少、尋優(yōu)性能較好等優(yōu)點，但與其他算法一樣，灰狼算法也存在探索和開發(fā)能力難以協(xié)調(diào)、求解精度低等缺點。因此，本文將基本灰狼算法與Logistic序列變異、干擾粒子相結(jié)合，從而在平衡灰狼群體探索和開發(fā)能力的同時，增強種群多樣性，提高收斂精度。

采用虛擬力改進(jìn)灰狼算法的狼群包圍策略，指導(dǎo)頭狼帶領(lǐng)包圍進(jìn)攻方向，加快算法收斂。該策略既避免了虛擬力算法導(dǎo)致的移動傳感節(jié)點優(yōu)化約束，又使灰狼算法有目的的向擴大覆蓋率和目標(biāo)監(jiān)測率的方向進(jìn)化。

1 GWO算法優(yōu)化WSN覆蓋基本原理

4.2 測試結(jié)果數(shù)據(jù)比較

從仿真及數(shù)據(jù)比較圖中可以看出，無論是灰狼算法還是改進(jìn)灰狼算法，相較于粒子群算法在收斂速度方面明顯提高，并且虛擬導(dǎo)向的改進(jìn)灰狼算法與其他兩種算法相比，覆蓋率明顯提高，收斂精度較高，收斂速度快，性能較穩(wěn)定，魯棒性較好。

5 結(jié) 語

無線傳感網(wǎng)絡(luò)布局優(yōu)化有利于改善網(wǎng)絡(luò)性能，提高網(wǎng)絡(luò)有效覆蓋率，本文提出一種用于無線傳感網(wǎng)絡(luò)布局優(yōu)化的虛擬導(dǎo)向改進(jìn)灰狼算法，采用概率測量模型評價網(wǎng)絡(luò)性能，以優(yōu)化網(wǎng)絡(luò)的有效覆蓋率為目標(biāo)，在對基本灰狼算法改進(jìn)其探索和局部開發(fā)能力，提高其收斂精度的基礎(chǔ)上，更新灰狼位置時引入虛擬導(dǎo)向策略，指導(dǎo)灰狼種群進(jìn)化，提高收斂速度和精度。實驗表明，虛擬導(dǎo)向的改進(jìn)灰狼算法能有效實現(xiàn)無線傳感網(wǎng)絡(luò)布局優(yōu)化，收斂精度更高，速度更快且魯棒性更好。

參 考 文 獻(xiàn)

[1]賈杰.無線傳感器網(wǎng)絡(luò)覆蓋控制與節(jié)點部署技術(shù)[D].南京：南京郵電大學(xué)，2010.

[2] WANG X，JIANG A，WANG S. Mobile agent based wireless sensor network for intelligent maintenance [J]. Lecture notes in computer science，2005（2）：316-325.

[3] HOWARD A，MATARIC M J，SUKHATME G S. An incremental self-deployment algorithm for mobile sensor networks [J]. Autonomous robots，2002，13（2）：113-126.

[4] WANG G，CAO G，PORTA T L. A bidding protocol for deploying mobile sensors [C]// Proceedings of the 11th IEEE International Conference on Network Protocols（ICNP）. Atlanta，Georgia，USA：IEEE，2003：315-324.

[5]王雪，王晟，馬俊杰.無線傳感網(wǎng)絡(luò)移動節(jié)點位置并行微粒群優(yōu)化策略[J].計算機學(xué)報，2007，30（4）：563-568.

[6] ZOU Y，CHAKRABARTY K. Sensor deployment and target localization based on virtual forces [A]. IEEE INFOCOM [C]// Piscataway，NJ，USA：IEEE Press，2003：1293-1303.

[7] KUMAR S，TEN H L，BALOGH J. On k-coverage in a mostly sleeping sensor network [C]// Proc 10th Annual Int1 Conference Mobile Computing and Networking. New York：ACM Press，2004：144-158.

[8] LI S，XU C，PAN W，et al. Sensor deployment optimization for detecting maneuvering targets [A]. 7th International Conference on Information Fusion [C]// Piscataway，NJ，USA：IEEE Press，2005.

[9] WANG X，WANG S，MA J. Dynamic deployment optimization in wireless sensor networks [J]. Lecture notes in control and information sciences，2006，344：182-187.

[10] WANG X，WANG S，MA J J. Dynamic sensor deployment strategy based on virtual force-directed particle swarm optimizaion in wireless sensor networks [J]. Chinese journal of electronics，2007，35（11）：2038-2042.

[11] ZHOU L M，YANG K H，ZHOU P. Optimal coverage configuration based on artificial fish swarm algorithm in WSNs [J]. Application research of computers，2010.

[12] LIU H，CHAI Z J，DU J Z，et al.Sensor redeployment algorithm based on combined virtual forces in three dimensional space [J]. Acta aotumatica sinica，2011（6）.

[13] CUI L Z，LI X Y，HU H D，et al. A coverage hole recovery algorithm with minimum energy consumption based on polar coordinates in WSNs [J] .Computer engineering & science，2018.

[14] FANG W，SONG X H. A deployment strategy for coverage control in wireless sensor networks based on the blind-zone of Voronoi diagram [J]. Acta physica sinica，2014，63（22）：220701.