灰狼算法下無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了灰狼算法下無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化范文，希望能給你帶來靈感和參考，敬請閱讀。

摘要:如何利用移動節(jié)點(diǎn)實(shí)現(xiàn)覆蓋的最大化并減少能量的使用是研究無線傳感器網(wǎng)絡(luò)的一個重要方向?；贑ircle映射，改進(jìn)了萊維飛行策略；結(jié)合能量位置融合機(jī)制，用優(yōu)化后的灰狼算法對無線傳感器網(wǎng)絡(luò)覆蓋問題進(jìn)行求解。首先，引入的Cir－cle映射大幅改善了狼群的多樣性，從而能實(shí)現(xiàn)更加有力的搜索；其次，改進(jìn)后的萊維飛行策略平衡了不同時期對全局搜索和局部尋優(yōu)的需求，一定程度上加快了搜索進(jìn)程，提高了收斂速度；最后考慮能量和位置的交融，每個個體不再單一考慮位置，而是結(jié)合一部分能量因素來進(jìn)行移動。仿真結(jié)果表明，未考慮能量受限的改進(jìn)后的灰狼算法較基本灰狼算法覆蓋率有所提升，和其他文獻(xiàn)中的算法相比，也具有更高的收斂速度和覆蓋率。在考慮能量受限以后，不但保證了覆蓋率，還延長了節(jié)點(diǎn)壽命。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；覆蓋優(yōu)化；灰狼算法；萊維飛行；能量位置融合

隨著材料科學(xué)和電子信息技術(shù)的發(fā)展，體積小、能耗低、無線覆蓋范圍廣的傳感器越來越來成為主流，無線傳感器網(wǎng)絡(luò)也就自然而然地走進(jìn)了科學(xué)界和工業(yè)界的視線中。無線傳感器網(wǎng)絡(luò)作為大量傳感器在自組織和多跳的方式下構(gòu)成的無線網(wǎng)絡(luò)結(jié)構(gòu)，目的是群體內(nèi)的協(xié)作感知、收集、處理和轉(zhuǎn)發(fā)網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域內(nèi)感知對象的監(jiān)測信息。無線傳感器網(wǎng)絡(luò)有著深遠(yuǎn)的應(yīng)用前景，無論是在戰(zhàn)爭戰(zhàn)術(shù)［1］、化學(xué)工業(yè)監(jiān)測和預(yù)報，還是航天器狀態(tài)監(jiān)控、城市軌道交通和倉儲物流管理［2］等領(lǐng)域都極具意義。近年來，群體智能算法在WSN覆蓋問題中的應(yīng)用與日俱增。文獻(xiàn)［3］提出了一種粒子群和螢火蟲的混合算法（PG－SO），以粒子群為主體，螢火蟲進(jìn)行局部搜索，算法復(fù)雜度提升較高，需要迭代的次數(shù)顯著增加，同時，節(jié)點(diǎn)部署稀疏時效果不明顯。文獻(xiàn)［4］提出了一種指數(shù)加權(quán)的粒子群改進(jìn)方法，盡管粒子群動態(tài)性能有所改善，但收斂速度并沒有大幅提高，粒子群算法早熟的局限性依然存在，對覆蓋問題的求解不利。Hu等［5］利用混沌映射加上非線性因子和Delta狼的變異行為對灰狼優(yōu)化算法進(jìn)行了改進(jìn)，但由于是第三優(yōu)個體的變異，跳出局部最優(yōu)仍存在困難，變異也導(dǎo)致迭代次數(shù)增加，降低了快速性。上述方法雖然可用于解決覆蓋問題，但算法帶來的覆蓋能力依然不夠，收斂速度慢，有些還沒有考慮能量受限等問題?；依莾?yōu)化算法（GreyWolfOptimizer，GWO）是2014年提出的一種群智能優(yōu)化方法［6］。由于其出色的尋優(yōu)性能，明顯優(yōu)于粒子群、螢火蟲等傳統(tǒng)算法，因此被大量應(yīng)用在核科學(xué)［7］、農(nóng)業(yè)預(yù)測［8］等領(lǐng)域。然而，與其他算法一樣，即便擁有3個優(yōu)勢引導(dǎo)個體，灰狼優(yōu)化算法也不可避免地存在過早收斂、全局能力不足等問題。針對這些問題，國內(nèi)外大量學(xué)者采取了不同的改進(jìn)措施來提升算法的性能。文獻(xiàn)［9］中用混合蛙跳和灰狼混合，大幅提高了精度，但對低維度問題，尤其是最高三維的覆蓋問題求解存在著不足，收斂速度不如傳統(tǒng)算法。Zhang等［10］引入差分策略提升了算法的性能，但由于自適應(yīng)參數(shù)和趨優(yōu)因子的存在，在覆蓋問題上反而降低了算法的迭代速度，延長了達(dá)到最優(yōu)的時間，一定意義上降低了整個網(wǎng)絡(luò)的生存周期。為了提高目標(biāo)區(qū)域覆蓋率，文中提出了一種能量位置融合改進(jìn)灰狼算法。該方法在傳統(tǒng)灰狼算法中加入了混沌映射對初始種群進(jìn)行改進(jìn)；在更新種群的過程中通過本文提出的改進(jìn)萊維飛行策略對算法的全局探索能力進(jìn)行改善；種群更新的同時考慮文中提出的能量和位置融合機(jī)制，使得每一步都是平衡兩者的更優(yōu)解，從而提高覆蓋率，也為能量受限條件下算法的設(shè)計提供新思路。

1覆蓋模型分析

假設(shè)求解的是二維覆蓋問題，即可定義網(wǎng)絡(luò)監(jiān)測區(qū)域面積為M×N，區(qū)域內(nèi)目標(biāo)可以被離散化為M×N個點(diǎn)，在區(qū)域內(nèi)隨機(jī)布置n個傳感器節(jié)點(diǎn)，節(jié)點(diǎn)集可以表示為U＝｛u1，u2，…，un}，所有節(jié)點(diǎn)的感知半徑Rs和通信半徑Rc都相同，且Rs≤2Rc。被檢測區(qū)域任意節(jié)點(diǎn)Ui的坐標(biāo)為（xi，yi），目標(biāo)節(jié)點(diǎn)Oj的坐標(biāo)為（xj，yj），兩者之間的距離表示為：d（ui，Oj）＝（xi－xj）2＋（yi－yj）■2（1）用Q（ui，Oj）表示節(jié)點(diǎn)ui對Oj的感知品質(zhì)，目標(biāo)Oj處于節(jié)點(diǎn)ui的感知范圍內(nèi)就可以被成功感知，感知質(zhì)量就是1；反之，節(jié)點(diǎn)ui無法感知目標(biāo)Oj，感知質(zhì)量就是0，數(shù)學(xué)表達(dá)式如下：Q（ui，Oj）＝1，d（ui，Oj）≤Rs0，其他｛（2）式（2）就是0－1感知模型，感知范圍內(nèi)的目標(biāo)都可以被成功感知。以提高感知概率為導(dǎo)向，同一目標(biāo)可能被多個傳感節(jié)點(diǎn)感知，其節(jié)點(diǎn)聯(lián)合感知概率分布（即聯(lián)合感知質(zhì)量）為：Q（U，Oj）＝1－∏ni＝1［1－Q（ui，Oj）］（3）監(jiān)測區(qū)域的總覆蓋率Rcov的定義是所有節(jié)點(diǎn)覆蓋的目標(biāo)數(shù)與總目標(biāo)數(shù)的比值，數(shù)學(xué)表達(dá)式如下：

2灰狼算法原理

灰狼算法是模擬灰狼群體性行為，利用灰狼的等級制度以及在捕食過程中的搜索、包圍、捕獵等行為來達(dá)到優(yōu)化的目的。假設(shè)灰狼種群個體數(shù)為pop，搜索區(qū)域的維度為h。其中，第i個灰狼個體的位置可以表示為Zi＝｛Zi1，Zi2，…，Zih}，在種群中適應(yīng)度（Fitness）最大的個體被記作α，將順次適應(yīng)度第二名的個體記作β，第三名記作δ，剩余的個體記作ω。在搜索獵物的過程中，灰狼接近并且圍捕獵物行為的數(shù)學(xué)模型［6］，具體如式（5）－式（9）所示：其中，Zp（t）為第t代獵物的位置；Z（t）為第t代灰狼個體的位置；Ci為擺動因子；r1為［0，1］之間的隨機(jī)數(shù)；A為收斂因子；Tmax為最大迭代次數(shù)；r2為［0，1］之間的隨機(jī)數(shù)；a為控制參數(shù)，其取值隨著迭代次數(shù)的增加而線性遞減，從2減至0。當(dāng)灰狼搜索到獵物所在的位置時，頭狼α最先帶領(lǐng)狼群對獵物采取包圍操作；其次，頭狼α帶領(lǐng)β狼和δ狼對獵物進(jìn)行攻擊捕捉。在灰狼群體中，狼、狼、狼距離獵物位置最近，也就是位置最優(yōu)的前三名。根據(jù)3個頭狼位置Zα，Zβ，Zδ來計算其余灰狼個體向獵物移動后的位置，其具體的數(shù)學(xué)模型如式（10）－式（13）所示：

3算法改進(jìn)策略

3．1混沌初始化

混沌是非線性系統(tǒng)獨(dú)有的且廣泛存在的一種非周期運(yùn)動形式，其涉及自然科學(xué)和社會科學(xué)的每一個分支。因?yàn)槠淦者m性和隨機(jī)性，不同優(yōu)化算法都能在全局區(qū)域?qū)崿F(xiàn)高效尋優(yōu)。灰狼算法雖然收斂速度不慢，但在全局尋優(yōu)上仍然需要改善初始種群的質(zhì)量。為此，本文在灰狼算法的初始化過程中引入混沌映射，混沌映射可以讓初始種群個體分布更加均勻?；煦缒Ｐ蜕?，本文選擇了Circle映射，數(shù)學(xué)描述如下：其中，Zk為個體位置，通常a取0．2，b取0．5。

3．2改進(jìn)萊維飛行策略

分析原始灰狼算法可知，整個種群隨著迭代次數(shù)的增加逐漸向三頭優(yōu)勢狼靠近，灰狼個體分布變得集中，極有可能錯失全局最優(yōu)解。為此，文中提出了一種改進(jìn)的萊維飛行策略，在傳統(tǒng)策略下，個體每次都要進(jìn)行飛行［11］，改進(jìn)后的策略是否飛行取決于時間步長近似出的數(shù)值概率，而在算法全程運(yùn)行的不同周期中概率不同，有效地平衡了全局和局部能力，既可以讓算法在前期不至于全局過于發(fā)散，也可以保證在后期具有跳出局部最優(yōu)的能力。改進(jìn)的飛行概率隨迭代次數(shù)t變化的公式如下：其中，Tmax為最大迭代次數(shù)。結(jié)合改進(jìn)的萊維飛行策略，下面對灰狼優(yōu)化算法進(jìn)行改進(jìn)，更新后的灰狼個體位置為：Zl（t）＝Z（t）＋α⊕Levy（λ）（20）其中，Zl（t）為飛行后灰狼個體的位置，⊕是點(diǎn)乘符號，α為步長控制參數(shù)，Levy（λ）表示隨機(jī)游走方程，表現(xiàn)形式為冪次未知的概率密度函數(shù)，數(shù)學(xué)表達(dá)式如下：Levy～μ＝t－λ，1＜λ≤3（21）通常使用Mantegna算法來模擬萊維分布的隨機(jī)步長s，為了保證飛行后的個體不會劣于原先位置，引入貪婪策略。如果飛行后的位置優(yōu)于原先位置，就用新位置替代舊位置；反之，在原位置不動。表達(dá)式如下：

3．3能量位置融合

傳感器節(jié)點(diǎn)的能量儲備是有限的，為了節(jié)省能量的使用，優(yōu)化網(wǎng)絡(luò)資源，提升網(wǎng)絡(luò)生存周期，本文將能量概念引入算法中，使得算法尋找的最優(yōu)點(diǎn)不再單單是整個網(wǎng)絡(luò)的最大覆蓋率，而是能量位置移動綜合考慮后的最優(yōu)位置。對灰狼的每一次移動進(jìn)行歸一化以此代表能量，公式如下：改進(jìn)后適應(yīng)度函數(shù)就變?yōu)槲锤采w率和能量之和，其值越小越優(yōu)，公式如下：

4覆蓋優(yōu)化設(shè)計

改進(jìn)后的灰狼優(yōu)化算法目的是未覆蓋率和能量之和最小化，算法步驟如下：Step1初始化參數(shù)，設(shè)置灰狼種群規(guī)模為pop，求解問題的維數(shù)為2，最大迭代次數(shù)為Tmax。對參數(shù)A，C，a進(jìn)行賦值。Step2初始化種群，利用Circle映射隨機(jī)產(chǎn)生種群個體。Step3由給出的適應(yīng)度函數(shù)計算各灰狼個體的適應(yīng)度fitness，并按適應(yīng)度排序，前三名設(shè)置為個體α，β，δ，對應(yīng)的位置信息為Z1，Z2，Z3。Step4利用式（5）－式（16）更新個體位置。Step5重新按適應(yīng)度排序，更新前三名。Step6比較隨機(jī)產(chǎn)生的［0，1］隨機(jī)數(shù)是否大于概率p，如果大于，則進(jìn)行萊維飛行，保留更優(yōu)的位置；反之，則不進(jìn)行飛行，直接進(jìn)入下一步。Step7再次對灰狼個體按適應(yīng)度排序，給出前三名的適應(yīng)度值。Step8判斷迭代次數(shù)t是否達(dá)到了最大迭代次數(shù)，如果達(dá)到，則輸出最優(yōu)解，即α個體的適應(yīng)度值，否則返回Step4繼續(xù)執(zhí)行。流程圖如圖1所示。

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

5．1未考慮能量受限的仿真

未考慮能量時的仿真主要是改進(jìn)的IGWO與原始灰狼算法即文獻(xiàn)［6］，還有文獻(xiàn)［3］、文獻(xiàn)［4］、文獻(xiàn)［5］進(jìn)行對比，其中不同文獻(xiàn)的實(shí)驗(yàn)參數(shù)設(shè)置與本文相同，隨后進(jìn)行比較。實(shí)驗(yàn)平臺為CPU主頻為2．9GHz、動態(tài)加速頻率4．2GHz的計算機(jī)，仿真軟件為MATLAB，所有后續(xù)實(shí)驗(yàn)均在此實(shí)驗(yàn)環(huán)境中進(jìn)行。表1所列為對比算法。（1）與GWO對比實(shí)驗(yàn)參數(shù)設(shè)置：監(jiān)測區(qū)域?yàn)?0×10的正方形區(qū)域，傳感器節(jié)點(diǎn)數(shù)為48，種群數(shù)量為30，迭代次數(shù)1000，感知半徑為1m，通信半徑10m。圖2給出了GWO與IGWO迭代時的覆蓋率變化曲線。由圖2可以看出，改進(jìn)灰狼算法跳出局部最優(yōu)只有40次迭代，而原始灰狼算法大約需要200次。在改進(jìn)的萊維飛行策略下，不論是最優(yōu)還是最弱的個體，跳出局部能力都有一定程度的提升，帶來了迭代次數(shù)的減少。在尋找全局最優(yōu)上，改進(jìn)灰狼算法達(dá)到了全覆蓋，灰狼算法只有99％，一定程度上可以歸功于Circle映射下的初始種群優(yōu)越性，使得IGWO能做到100％的覆蓋率。由此可見，IGWO的全局能力遠(yuǎn)強(qiáng)于GWO。（2）與PGSO，IPSO，F(xiàn)GWO的對比實(shí)驗(yàn)參數(shù)同上。圖3給出了4種算法的共同對比圖。由表2可見，改進(jìn)后的灰狼優(yōu)化算法性能明顯優(yōu)于文獻(xiàn)［3－5］中所提到的算法。在迭代40次后，改進(jìn)灰狼算法的覆蓋率達(dá)到了100％，而其他算法此時的覆蓋率不到90％，這可以歸因于初始種群的優(yōu)越性，并且改進(jìn)的萊維飛行在保證全局能力的同時沒有降低前期的收斂速度，全局收斂速度因此有所提高。萊維飛行所進(jìn)行的隨機(jī)行走使得個體按照重尾分布改變自身位置，大大提高了跳出局部最優(yōu)的能力。

5．2能量位置融合仿真

實(shí)驗(yàn)平臺及參數(shù)同上。由圖4可見，在考慮能量位置融合后依然能夠達(dá)到網(wǎng)絡(luò)的100％覆蓋。算法在整個迭代過程中覆蓋率也并非一直在上升，由于要考慮能量的影響，覆蓋率也會出現(xiàn)回退，但最終仍然能夠達(dá)到全局最優(yōu)，即全覆蓋。6結(jié)束語面對傳統(tǒng)無線傳感器網(wǎng)絡(luò)覆蓋問題，在隨機(jī)拋灑的節(jié)點(diǎn)覆蓋和能量利用效率不佳的情況下，本文提出了改進(jìn)的萊維飛行策略和能量融合機(jī)制并基于Circle映射改進(jìn)了灰狼算法。改進(jìn)后的萊維飛行策略進(jìn)一步加快了收斂速度和全局探索速度。在文章最后提出的能量位置融合機(jī)制將節(jié)點(diǎn)移動的最優(yōu)和網(wǎng)絡(luò)能量的最小化結(jié)合在一起，為節(jié)省移動節(jié)點(diǎn)網(wǎng)絡(luò)能量提供了新思路。然而，本文研究仍存在一定的改進(jìn)空間，例如，覆蓋模型上可以采用更加貼合現(xiàn)實(shí)場景的概率密度分布模型；算法改進(jìn)上可以采用動態(tài)優(yōu)勢種群，使群體探索更靈活；能量受限上可以從網(wǎng)絡(luò)拓?fù)涞慕嵌冗M(jìn)行考慮分析，這也是我們未來要研究的內(nèi)容。

作者:范星澤 禹梅 單位:華北電力大學(xué)控制與計算機(jī)工程學(xué)院