公務(wù)員期刊網(wǎng) 論文中心 正文

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

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

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

摘要:如何利用移動(dòng)節(jié)點(diǎn)實(shí)現(xiàn)覆蓋的最大化并減少能量的使用是研究無線傳感器網(wǎng)絡(luò)的一個(gè)重要方向?;贑ircle映射,改進(jìn)了萊維飛行策略;結(jié)合能量位置融合機(jī)制,用優(yōu)化后的灰狼算法對(duì)無線傳感器網(wǎng)絡(luò)覆蓋問題進(jìn)行求解。首先,引入的Cir-cle映射大幅改善了狼群的多樣性,從而能實(shí)現(xiàn)更加有力的搜索;其次,改進(jìn)后的萊維飛行策略平衡了不同時(shí)期對(duì)全局搜索和局部尋優(yōu)的需求,一定程度上加快了搜索進(jìn)程,提高了收斂速度;最后考慮能量和位置的交融,每個(gè)個(gè)體不再單一考慮位置,而是結(jié)合一部分能量因素來進(jìn)行移動(dòng)。仿真結(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)感知對(duì)象的監(jiān)測(cè)信息。無線傳感器網(wǎng)絡(luò)有著深遠(yuǎn)的應(yīng)用前景,無論是在戰(zhàn)爭戰(zhàn)術(shù)[1]、化學(xué)工業(yè)監(jiān)測(cè)和預(yù)報(bào),還是航天器狀態(tài)監(jiān)控、城市軌道交通和倉儲(chǔ)物流管理[2]等領(lǐng)域都極具意義。近年來,群體智能算法在WSN覆蓋問題中的應(yīng)用與日俱增。文獻(xiàn)[3]提出了一種粒子群和螢火蟲的混合算法(PG-SO),以粒子群為主體,螢火蟲進(jìn)行局部搜索,算法復(fù)雜度提升較高,需要迭代的次數(shù)顯著增加,同時(shí),節(jié)點(diǎn)部署稀疏時(shí)效果不明顯。文獻(xiàn)[4]提出了一種指數(shù)加權(quán)的粒子群改進(jìn)方法,盡管粒子群動(dòng)態(tài)性能有所改善,但收斂速度并沒有大幅提高,粒子群算法早熟的局限性依然存在,對(duì)覆蓋問題的求解不利。Hu等[5]利用混沌映射加上非線性因子和Delta狼的變異行為對(duì)灰狼優(yōu)化算法進(jìn)行了改進(jìn),但由于是第三優(yōu)個(gè)體的變異,跳出局部最優(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ù)測(cè)[8]等領(lǐng)域。然而,與其他算法一樣,即便擁有3個(gè)優(yōu)勢(shì)引導(dǎo)個(gè)體,灰狼優(yōu)化算法也不可避免地存在過早收斂、全局能力不足等問題。針對(duì)這些問題,國內(nèi)外大量學(xué)者采取了不同的改進(jìn)措施來提升算法的性能。文獻(xiàn)[9]中用混合蛙跳和灰狼混合,大幅提高了精度,但對(duì)低維度問題,尤其是最高三維的覆蓋問題求解存在著不足,收斂速度不如傳統(tǒng)算法。Zhang等[10]引入差分策略提升了算法的性能,但由于自適應(yīng)參數(shù)和趨優(yōu)因子的存在,在覆蓋問題上反而降低了算法的迭代速度,延長了達(dá)到最優(yōu)的時(shí)間,一定意義上降低了整個(gè)網(wǎng)絡(luò)的生存周期。為了提高目標(biāo)區(qū)域覆蓋率,文中提出了一種能量位置融合改進(jìn)灰狼算法。該方法在傳統(tǒng)灰狼算法中加入了混沌映射對(duì)初始種群進(jìn)行改進(jìn);在更新種群的過程中通過本文提出的改進(jìn)萊維飛行策略對(duì)算法的全局探索能力進(jìn)行改善;種群更新的同時(shí)考慮文中提出的能量和位置融合機(jī)制,使得每一步都是平衡兩者的更優(yōu)解,從而提高覆蓋率,也為能量受限條件下算法的設(shè)計(jì)提供新思路。

1覆蓋模型分析

假設(shè)求解的是二維覆蓋問題,即可定義網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域面積為M×N,區(qū)域內(nèi)目標(biāo)可以被離散化為M×N個(gè)點(diǎn),在區(qū)域內(nèi)隨機(jī)布置n個(gè)傳感器節(jié)點(diǎn),節(jié)點(diǎn)集可以表示為U={u1,u2,…,un},所有節(jié)點(diǎn)的感知半徑Rs和通信半徑Rc都相同,且Rs≤2Rc。被檢測(cè)區(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對(duì)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)可能被多個(gè)傳感節(jié)點(diǎn)感知,其節(jié)點(diǎn)聯(lián)合感知概率分布(即聯(lián)合感知質(zhì)量)為:Q(U,Oj)=1-∏ni=1[1-Q(ui,Oj)](3)監(jiān)測(cè)區(qū)域的總覆蓋率Rcov的定義是所有節(jié)點(diǎn)覆蓋的目標(biāo)數(shù)與總目標(biāo)數(shù)的比值,數(shù)學(xué)表達(dá)式如下:

2灰狼算法原理

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

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

3.1混沌初始化

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

3.2改進(jìn)萊維飛行策略

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

3.3能量位置融合

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

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

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

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

5.1未考慮能量受限的仿真

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

5.2能量位置融合仿真

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

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