灰狼算法下無線傳感器網(wǎng)絡覆蓋優(yōu)化
前言：想要寫出一篇引人入勝的文章？我們特意為您整理了灰狼算法下無線傳感器網(wǎng)絡覆蓋優(yōu)化范文，希望能給你帶來靈感和參考，敬請閱讀。
摘要:如何利用移動節(jié)點實現(xiàn)覆蓋的最大化并減少能量的使用是研究無線傳感器網(wǎng)絡的一個重要方向?；贑ircle映射，改進了萊維飛行策略；結(jié)合能量位置融合機制，用優(yōu)化后的灰狼算法對無線傳感器網(wǎng)絡覆蓋問題進行求解。首先，引入的Cir－cle映射大幅改善了狼群的多樣性，從而能實現(xiàn)更加有力的搜索；其次，改進后的萊維飛行策略平衡了不同時期對全局搜索和局部尋優(yōu)的需求，一定程度上加快了搜索進程，提高了收斂速度；最后考慮能量和位置的交融，每個個體不再單一考慮位置，而是結(jié)合一部分能量因素來進行移動。仿真結(jié)果表明，未考慮能量受限的改進后的灰狼算法較基本灰狼算法覆蓋率有所提升，和其他文獻中的算法相比，也具有更高的收斂速度和覆蓋率。在考慮能量受限以后，不但保證了覆蓋率，還延長了節(jié)點壽命。
關(guān)鍵詞：無線傳感器網(wǎng)絡；覆蓋優(yōu)化；灰狼算法；萊維飛行；能量位置融合
隨著材料科學和電子信息技術(shù)的發(fā)展，體積小、能耗低、無線覆蓋范圍廣的傳感器越來越來成為主流，無線傳感器網(wǎng)絡也就自然而然地走進了科學界和工業(yè)界的視線中。無線傳感器網(wǎng)絡作為大量傳感器在自組織和多跳的方式下構(gòu)成的無線網(wǎng)絡結(jié)構(gòu)，目的是群體內(nèi)的協(xié)作感知、收集、處理和轉(zhuǎn)發(fā)網(wǎng)絡覆蓋目標區(qū)域內(nèi)感知對象的監(jiān)測信息。無線傳感器網(wǎng)絡有著深遠的應用前景，無論是在戰(zhàn)爭戰(zhàn)術(shù)［1］、化學工業(yè)監(jiān)測和預報，還是航天器狀態(tài)監(jiān)控、城市軌道交通和倉儲物流管理［2］等領域都極具意義。近年來，群體智能算法在WSN覆蓋問題中的應用與日俱增。文獻［3］提出了一種粒子群和螢火蟲的混合算法（PG－SO），以粒子群為主體，螢火蟲進行局部搜索，算法復雜度提升較高，需要迭代的次數(shù)顯著增加，同時，節(jié)點部署稀疏時效果不明顯。文獻［4］提出了一種指數(shù)加權(quán)的粒子群改進方法，盡管粒子群動態(tài)性能有所改善，但收斂速度并沒有大幅提高，粒子群算法早熟的局限性依然存在，對覆蓋問題的求解不利。Hu等［5］利用混沌映射加上非線性因子和Delta狼的變異行為對灰狼優(yōu)化算法進行了改進，但由于是第三優(yōu)個體的變異，跳出局部最優(yōu)仍存在困難，變異也導致迭代次數(shù)增加，降低了快速性。上述方法雖然可用于解決覆蓋問題，但算法帶來的覆蓋能力依然不夠，收斂速度慢，有些還沒有考慮能量受限等問題?；依莾?yōu)化算法（GreyWolfOptimizer，GWO）是2014年提出的一種群智能優(yōu)化方法［6］。由于其出色的尋優(yōu)性能，明顯優(yōu)于粒子群、螢火蟲等傳統(tǒng)算法，因此被大量應用在核科學［7］、農(nóng)業(yè)預測［8］等領域。然而，與其他算法一樣，即便擁有3個優(yōu)勢引導個體，灰狼優(yōu)化算法也不可避免地存在過早收斂、全局能力不足等問題。針對這些問題，國內(nèi)外大量學者采取了不同的改進措施來提升算法的性能。文獻［9］中用混合蛙跳和灰狼混合，大幅提高了精度，但對低維度問題，尤其是最高三維的覆蓋問題求解存在著不足，收斂速度不如傳統(tǒng)算法。Zhang等［10］引入差分策略提升了算法的性能，但由于自適應參數(shù)和趨優(yōu)因子的存在，在覆蓋問題上反而降低了算法的迭代速度，延長了達到最優(yōu)的時間，一定意義上降低了整個網(wǎng)絡的生存周期。為了提高目標區(qū)域覆蓋率，文中提出了一種能量位置融合改進灰狼算法。該方法在傳統(tǒng)灰狼算法中加入了混沌映射對初始種群進行改進；在更新種群的過程中通過本文提出的改進萊維飛行策略對算法的全局探索能力進行改善；種群更新的同時考慮文中提出的能量和位置融合機制，使得每一步都是平衡兩者的更優(yōu)解，從而提高覆蓋率，也為能量受限條件下算法的設計提供新思路。
1覆蓋模型分析
假設求解的是二維覆蓋問題，即可定義網(wǎng)絡監(jiān)測區(qū)域面積為M×N，區(qū)域內(nèi)目標可以被離散化為M×N個點，在區(qū)域內(nèi)隨機布置n個傳感器節(jié)點，節(jié)點集可以表示為U＝｛u1，u2，…，un}，所有節(jié)點的感知半徑Rs和通信半徑Rc都相同，且Rs≤2Rc。被檢測區(qū)域任意節(jié)點Ui的坐標為（xi，yi），目標節(jié)點Oj的坐標為（xj，yj），兩者之間的距離表示為：d（ui，Oj）＝（xi－xj）2＋（yi－yj）■2（1）用Q（ui，Oj）表示節(jié)點ui對Oj的感知品質(zhì)，目標Oj處于節(jié)點ui的感知范圍內(nèi)就可以被成功感知，感知質(zhì)量就是1；反之，節(jié)點ui無法感知目標Oj，感知質(zhì)量就是0，數(shù)學表達式如下：Q（ui，Oj）＝1，d（ui，Oj）≤Rs0，其他｛（2）式（2）就是0－1感知模型，感知范圍內(nèi)的目標都可以被成功感知。以提高感知概率為導向，同一目標可能被多個傳感節(jié)點感知，其節(jié)點聯(lián)合感知概率分布（即聯(lián)合感知質(zhì)量）為：Q（U，Oj）＝1－∏ni＝1［1－Q（ui，Oj）］（3）監(jiān)測區(qū)域的總覆蓋率Rcov的定義是所有節(jié)點覆蓋的目標數(shù)與總目標數(shù)的比值，數(shù)學表達式如下：
2灰狼算法原理
灰狼算法是模擬灰狼群體性行為，利用灰狼的等級制度以及在捕食過程中的搜索、包圍、捕獵等行為來達到優(yōu)化的目的。假設灰狼種群個體數(shù)為pop，搜索區(qū)域的維度為h。其中，第i個灰狼個體的位置可以表示為Zi＝｛Zi1，Zi2，…，Zih}，在種群中適應度（Fitness）最大的個體被記作α，將順次適應度第二名的個體記作β，第三名記作δ，剩余的個體記作ω。在搜索獵物的過程中，灰狼接近并且圍捕獵物行為的數(shù)學模型［6］，具體如式（5）－式（9）所示：其中，Zp（t）為第t代獵物的位置；Z（t）為第t代灰狼個體的位置；Ci為擺動因子；r1為［0，1］之間的隨機數(shù)；A為收斂因子；Tmax為最大迭代次數(shù)；r2為［0，1］之間的隨機數(shù)；a為控制參數(shù)，其取值隨著迭代次數(shù)的增加而線性遞減，從2減至0。當灰狼搜索到獵物所在的位置時，頭狼α最先帶領狼群對獵物采取包圍操作；其次，頭狼α帶領β狼和δ狼對獵物進行攻擊捕捉。在灰狼群體中，狼、狼、狼距離獵物位置最近，也就是位置最優(yōu)的前三名。根據(jù)3個頭狼位置Zα，Zβ，Zδ來計算其余灰狼個體向獵物移動后的位置，其具體的數(shù)學模型如式（10）－式（13）所示：
3算法改進策略
3．1混沌初始化
混沌是非線性系統(tǒng)獨有的且廣泛存在的一種非周期運動形式，其涉及自然科學和社會科學的每一個分支。因為其普適性和隨機性，不同優(yōu)化算法都能在全局區(qū)域?qū)崿F(xiàn)高效尋優(yōu)?；依撬惴m然收斂速度不慢，但在全局尋優(yōu)上仍然需要改善初始種群的質(zhì)量。為此，本文在灰狼算法的初始化過程中引入混沌映射，混沌映射可以讓初始種群個體分布更加均勻。混沌模型上，本文選擇了Circle映射，數(shù)學描述如下：其中，Zk為個體位置，通常a取0．2，b取0．5。
3．2改進萊維飛行策略
分析原始灰狼算法可知，整個種群隨著迭代次數(shù)的增加逐漸向三頭優(yōu)勢狼靠近，灰狼個體分布變得集中，極有可能錯失全局最優(yōu)解。為此，文中提出了一種改進的萊維飛行策略，在傳統(tǒng)策略下，個體每次都要進行飛行［11］，改進后的策略是否飛行取決于時間步長近似出的數(shù)值概率，而在算法全程運行的不同周期中概率不同，有效地平衡了全局和局部能力，既可以讓算法在前期不至于全局過于發(fā)散，也可以保證在后期具有跳出局部最優(yōu)的能力。改進的飛行概率隨迭代次數(shù)t變化的公式如下：其中，Tmax為最大迭代次數(shù)。結(jié)合改進的萊維飛行策略，下面對灰狼優(yōu)化算法進行改進，更新后的灰狼個體位置為：Zl（t）＝Z（t）＋α⊕Levy（λ）（20）其中，Zl（t）為飛行后灰狼個體的位置，⊕是點乘符號，α為步長控制參數(shù)，Levy（λ）表示隨機游走方程，表現(xiàn)形式為冪次未知的概率密度函數(shù)，數(shù)學表達式如下：Levy～μ＝t－λ，1＜λ≤3（21）通常使用Mantegna算法來模擬萊維分布的隨機步長s，為了保證飛行后的個體不會劣于原先位置，引入貪婪策略。如果飛行后的位置優(yōu)于原先位置，就用新位置替代舊位置；反之，在原位置不動。表達式如下：
3．3能量位置融合
傳感器節(jié)點的能量儲備是有限的，為了節(jié)省能量的使用，優(yōu)化網(wǎng)絡資源，提升網(wǎng)絡生存周期，本文將能量概念引入算法中，使得算法尋找的最優(yōu)點不再單單是整個網(wǎng)絡的最大覆蓋率，而是能量位置移動綜合考慮后的最優(yōu)位置。對灰狼的每一次移動進行歸一化以此代表能量，公式如下：改進后適應度函數(shù)就變?yōu)槲锤采w率和能量之和，其值越小越優(yōu)，公式如下：
4覆蓋優(yōu)化設計
改進后的灰狼優(yōu)化算法目的是未覆蓋率和能量之和最小化，算法步驟如下：Step1初始化參數(shù)，設置灰狼種群規(guī)模為pop，求解問題的維數(shù)為2，最大迭代次數(shù)為Tmax。對參數(shù)A，C，a進行賦值。Step2初始化種群，利用Circle映射隨機產(chǎn)生種群個體。Step3由給出的適應度函數(shù)計算各灰狼個體的適應度fitness，并按適應度排序，前三名設置為個體α，β，δ，對應的位置信息為Z1，Z2，Z3。Step4利用式（5）－式（16）更新個體位置。Step5重新按適應度排序，更新前三名。Step6比較隨機產(chǎn)生的［0，1］隨機數(shù)是否大于概率p，如果大于，則進行萊維飛行，保留更優(yōu)的位置；反之，則不進行飛行，直接進入下一步。Step7再次對灰狼個體按適應度排序，給出前三名的適應度值。Step8判斷迭代次數(shù)t是否達到了最大迭代次數(shù)，如果達到，則輸出最優(yōu)解，即α個體的適應度值，否則返回Step4繼續(xù)執(zhí)行。流程圖如圖1所示。
5仿真實驗與分析
5．1未考慮能量受限的仿真
未考慮能量時的仿真主要是改進的IGWO與原始灰狼算法即文獻［6］，還有文獻［3］、文獻［4］、文獻［5］進行對比，其中不同文獻的實驗參數(shù)設置與本文相同，隨后進行比較。實驗平臺為CPU主頻為2．9GHz、動態(tài)加速頻率4．2GHz的計算機，仿真軟件為MATLAB，所有后續(xù)實驗均在此實驗環(huán)境中進行。表1所列為對比算法。（1）與GWO對比實驗參數(shù)設置：監(jiān)測區(qū)域為10×10的正方形區(qū)域，傳感器節(jié)點數(shù)為48，種群數(shù)量為30，迭代次數(shù)1000，感知半徑為1m，通信半徑10m。圖2給出了GWO與IGWO迭代時的覆蓋率變化曲線。由圖2可以看出，改進灰狼算法跳出局部最優(yōu)只有40次迭代，而原始灰狼算法大約需要200次。在改進的萊維飛行策略下，不論是最優(yōu)還是最弱的個體，跳出局部能力都有一定程度的提升，帶來了迭代次數(shù)的減少。在尋找全局最優(yōu)上，改進灰狼算法達到了全覆蓋，灰狼算法只有99％，一定程度上可以歸功于Circle映射下的初始種群優(yōu)越性，使得IGWO能做到100％的覆蓋率。由此可見，IGWO的全局能力遠強于GWO。（2）與PGSO，IPSO，F(xiàn)GWO的對比實驗參數(shù)同上。圖3給出了4種算法的共同對比圖。由表2可見，改進后的灰狼優(yōu)化算法性能明顯優(yōu)于文獻［3－5］中所提到的算法。在迭代40次后，改進灰狼算法的覆蓋率達到了100％，而其他算法此時的覆蓋率不到90％，這可以歸因于初始種群的優(yōu)越性，并且改進的萊維飛行在保證全局能力的同時沒有降低前期的收斂速度，全局收斂速度因此有所提高。萊維飛行所進行的隨機行走使得個體按照重尾分布改變自身位置，大大提高了跳出局部最優(yōu)的能力。
5．2能量位置融合仿真
實驗平臺及參數(shù)同上。由圖4可見，在考慮能量位置融合后依然能夠達到網(wǎng)絡的100％覆蓋。算法在整個迭代過程中覆蓋率也并非一直在上升，由于要考慮能量的影響，覆蓋率也會出現(xiàn)回退，但最終仍然能夠達到全局最優(yōu)，即全覆蓋。6結(jié)束語面對傳統(tǒng)無線傳感器網(wǎng)絡覆蓋問題，在隨機拋灑的節(jié)點覆蓋和能量利用效率不佳的情況下，本文提出了改進的萊維飛行策略和能量融合機制并基于Circle映射改進了灰狼算法。改進后的萊維飛行策略進一步加快了收斂速度和全局探索速度。在文章最后提出的能量位置融合機制將節(jié)點移動的最優(yōu)和網(wǎng)絡能量的最小化結(jié)合在一起，為節(jié)省移動節(jié)點網(wǎng)絡能量提供了新思路。然而，本文研究仍存在一定的改進空間，例如，覆蓋模型上可以采用更加貼合現(xiàn)實場景的概率密度分布模型；算法改進上可以采用動態(tài)優(yōu)勢種群，使群體探索更靈活；能量受限上可以從網(wǎng)絡拓撲的角度進行考慮分析，這也是我們未來要研究的內(nèi)容。
作者:范星澤 禹梅 單位:華北電力大學控制與計算機工程學院