基于改進(jìn)混合蛙跳的移動(dòng)傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化研究

蔡紹堂 ，樂(lè)英高 ，2，胡 駿 ，麻碩琪 ，曹 莉

（1.四川理工學(xué)院 人工智能四川省重點(diǎn)實(shí)驗(yàn)室，自貢 643000；2.四川理工學(xué)院 材料腐蝕與防護(hù)四川省重點(diǎn)實(shí)驗(yàn)室，自貢 643000；3.四川理工學(xué)院 機(jī)械工程學(xué)院，自貢 643000）

無(wú)線傳感網(wǎng)絡(luò)系統(tǒng)包含傳感器技術(shù)、無(wú)線通信技術(shù)、計(jì)算機(jī)處理技術(shù)等多種現(xiàn)代科學(xué)技術(shù)，自感知、自適應(yīng)、自分析的獨(dú)有特點(diǎn)體現(xiàn)了傳感網(wǎng)絡(luò)的優(yōu)越性，因此被廣泛地應(yīng)用于各種領(lǐng)域[1]。國(guó)內(nèi)外學(xué)者對(duì)路由傳輸協(xié)議、拓?fù)浣Y(jié)構(gòu)優(yōu)化設(shè)計(jì)、傳感網(wǎng)絡(luò)安全技術(shù)等進(jìn)行了大量研究，以此從各方面提高自組織多跳網(wǎng)絡(luò)的容錯(cuò)性、穩(wěn)定性、魯棒性等網(wǎng)絡(luò)性能。

最優(yōu)覆蓋可優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)、降低能耗、提升網(wǎng)絡(luò)覆蓋度等，一般通過(guò)功率控制和層次型拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)，以?xún)?yōu)化通信鏈路通信，實(shí)現(xiàn)降低能耗，提升網(wǎng)絡(luò)各方面性能[2-3]，近年來(lái)很多專(zhuān)家學(xué)者對(duì)移動(dòng)傳感網(wǎng)絡(luò)做了大量研究[4-6]。

本文首先闡述了拓?fù)浣Y(jié)構(gòu)優(yōu)化最優(yōu)覆蓋相關(guān)問(wèn)題，具體工作包含傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)建模，詳細(xì)介紹了改進(jìn)混合蛙跳算法原理，以及改進(jìn)混合蛙跳算法在移動(dòng)傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化設(shè)計(jì)，并通過(guò)實(shí)驗(yàn)仿真對(duì)改進(jìn)混合蛙跳算法（ISFLA）與混沌量子粒子群算法、混沌人工蜂群算法進(jìn)行了對(duì)比，驗(yàn)證本文算法對(duì)網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題在提升負(fù)載均衡性、覆蓋率、降低能耗、提高生命周期等方面得到了提高。

1 拓?fù)浣Y(jié)構(gòu)優(yōu)化最優(yōu)覆蓋問(wèn)題

常見(jiàn)的感知模型主要有二元感知模型、概率感知模型、有向感知模型[7-8]。二元感知模型感知半徑大小由感知原件固有物理屬性決定，當(dāng)該目標(biāo)節(jié)點(diǎn)位于檢測(cè)節(jié)點(diǎn)感知圓內(nèi)時(shí)，目標(biāo)節(jié)點(diǎn)能被感知。二元感知模型如圖1所示，感知半徑內(nèi)目標(biāo)節(jié)點(diǎn)被感知的概率為100%，相反感知概率則為0%。

圖1 二元感知模型Fig.1 Binary perception model

本文實(shí)驗(yàn)設(shè)定覆蓋平面為基于二元感知模型，其具有M個(gè)傳感節(jié)點(diǎn)，r表示傳感節(jié)點(diǎn)的通信半徑，R為感知半徑，傳感節(jié)點(diǎn)坐標(biāo)設(shè)定為（xl，yl），傳感節(jié)點(diǎn)集合由O=｛O1，O2，O3…OM｝表示，設(shè)任意坐標(biāo)為（xt，yt）的點(diǎn)Rt。

式（1）為傳感節(jié)點(diǎn)到任意點(diǎn)距離。式（2）為傳感節(jié)點(diǎn)Ol到目標(biāo)節(jié)點(diǎn)感知測(cè)量率。式（3）為Ol中目標(biāo)節(jié)點(diǎn)覆蓋一坐標(biāo)為（x，y）的節(jié)點(diǎn)覆蓋率。設(shè)覆蓋區(qū)域I面積為ab，式（4）為傳感網(wǎng)絡(luò)區(qū)域有效覆蓋率，為傳感器工作節(jié)點(diǎn)有效覆蓋面積，式（5）為節(jié)點(diǎn)利用率，為傳感區(qū)域工作節(jié)點(diǎn)數(shù)，式（6）由f1（x）、f2（x）子目標(biāo)函數(shù)加權(quán)轉(zhuǎn)換得到總目標(biāo)函數(shù)。ω1、ω2為f1（x）、f2（x）相應(yīng)權(quán)值，且 ω1+ω2=1（ω1、ω2∈［0，1］），f（x）數(shù)值越大可判斷節(jié)點(diǎn)部署方案越優(yōu)。

2 改進(jìn)混合蛙跳算法

如圖2所示為傳統(tǒng)混合蛙跳算法，其在求解一些復(fù)雜問(wèn)題上存在收斂時(shí)間長(zhǎng)、易陷入局部極值、尋優(yōu)精度低等問(wèn)題。因此提出一種基于改進(jìn)混合蛙跳算法拓?fù)浣Y(jié)構(gòu)優(yōu)化設(shè)計(jì)。

圖2 傳統(tǒng)混合蛙跳算法Fig.2 Traditional shuffled frog leaping algorithm

改進(jìn)混合蛙跳算法流程如圖3所示，步驟如下[9]：

（1）初始化種群：青蛙種群總數(shù)F，子群總數(shù)M，解的維數(shù)P，算法混合迭代次數(shù)G，進(jìn)化代數(shù)N；

（2）計(jì)算每個(gè)青蛙適應(yīng)度函數(shù)；

（3）青蛙的適應(yīng)度值進(jìn)行，找出全局最優(yōu)青蛙；

圖3 改進(jìn)混合蛙跳算法流程Fig.3 Improved shuffled frog leaping algorithm flow chart

（4）子種群劃分：將最優(yōu)個(gè)體分到第一子群組，第二適應(yīng)度青蛙分到第二子群組，依次將青蛙種群劃分為包含Q只青蛙個(gè)體的M個(gè)子群，其中M×Q=F，如式（7）所示為劃分為M個(gè)子群T1，T2，…TM。

（5）局部搜索：在子群中尋找最差解Pw，最優(yōu)值為Pb，計(jì)算組內(nèi)青蛙的平均值Pa，通過(guò)式（8）更新最差解的位置，同時(shí)根據(jù)式（9）對(duì)組內(nèi)最差青蛙Pw的歷史最優(yōu)值Ph進(jìn)行更新。其中Dmax表示最大移動(dòng)步長(zhǎng)，g表示子群搜索迭代次數(shù)；利用最優(yōu)青蛙與最差青蛙的歷史最優(yōu)位置之間隨機(jī)點(diǎn)出發(fā)，以組內(nèi)所有青蛙的平均值與最差青蛙的差值為步長(zhǎng)基數(shù)，雙方向隨機(jī)查找更優(yōu)青蛙。直到更新后的最差解適應(yīng)度小于原適應(yīng)度最差解，隨之將其代替。在設(shè)置進(jìn)化代數(shù)內(nèi)進(jìn)行循環(huán)更新，在滿足達(dá)到進(jìn)化代數(shù)的同時(shí)找到子群最差解，否則重復(fù)局部搜索步驟。

（6）子群淘汰機(jī)制：局部搜索結(jié)束后，依據(jù)最優(yōu)解與最差解的變化關(guān)系，比較預(yù)設(shè)定連續(xù)代數(shù)與設(shè)定較小值大小，若連續(xù)代數(shù)均小于設(shè)定較小值，淘汰該子群并進(jìn)行重新隨機(jī)搜索，否則保留該子種群。

（7）混合運(yùn)算：若大于最大進(jìn)化代數(shù)，終止搜索，否則重新返回步驟2。

3 改進(jìn)混合蛙跳在拓?fù)浣Y(jié)構(gòu)優(yōu)化中應(yīng)用

根據(jù)移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點(diǎn)，本文對(duì)其基于特性條件約束，賦予人為定義并優(yōu)化，使用層次型拓?fù)浣Y(jié)構(gòu)作為無(wú)線傳感網(wǎng)絡(luò)拓?fù)浠灸Ｐ停C合拓?fù)浣Y(jié)構(gòu)優(yōu)化策略，提出能量高效的拓?fù)淇刂扑惴ǎ阂酝桓怕手芷谛噪S機(jī)選擇簇頭，令移動(dòng)傳感網(wǎng)絡(luò)的總體能量消耗均衡分配至各傳感器節(jié)點(diǎn)中，實(shí)現(xiàn)簇中成員節(jié)點(diǎn)數(shù)據(jù)的均衡分布，完成無(wú)線傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的設(shè)計(jì)。該算法在保證數(shù)據(jù)時(shí)延性要求的條件下，提高網(wǎng)絡(luò)覆蓋率和數(shù)據(jù)傳輸穩(wěn)定性。

近年，通過(guò)積極探索水生態(tài)系統(tǒng)保護(hù)與修復(fù)，黃河流域水生態(tài)質(zhì)量得到顯著改善。黃河實(shí)現(xiàn)連續(xù)12年河道不斷流；黃河河口三角洲生態(tài)補(bǔ)水、引黃濟(jì)淀、黃河源區(qū)水源涵養(yǎng)、烏梁素海綜合治理等生態(tài)效益顯著。山西省、西安浐灞等水生態(tài)系統(tǒng)保護(hù)與修復(fù)試點(diǎn)工作取得重要進(jìn)展。

步驟1初始化階段建立一個(gè)網(wǎng)絡(luò)權(quán)重樹(shù)，并且針對(duì)每個(gè)單位周期獲取一個(gè)可行覆蓋子集。

步驟2可行覆蓋子集的建立過(guò)程是從一個(gè)空集合開(kāi)始，之后迭代的通過(guò)特定機(jī)制選取未被該子覆蓋集覆蓋的關(guān)鍵目標(biāo)節(jié)點(diǎn)，再選取最大貢獻(xiàn)節(jié)點(diǎn)去覆蓋該關(guān)鍵目標(biāo)，依次迭代直到全部目標(biāo)節(jié)點(diǎn)均被覆蓋，此時(shí)將得到一個(gè)子可行覆蓋集合。在保證傳感器節(jié)點(diǎn)間連通性的前提下，尋找一組最小的節(jié)點(diǎn)集，實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)覆蓋率的最大化。除了最優(yōu)覆蓋節(jié)點(diǎn)集中的節(jié)點(diǎn)以外，其它節(jié)點(diǎn)都可以處于休眠的狀態(tài)，直到最優(yōu)覆蓋節(jié)點(diǎn)集里面出現(xiàn)某些節(jié)點(diǎn)由于電量耗盡的時(shí)候，它們才進(jìn)入正常工作狀態(tài)，代替原來(lái)節(jié)點(diǎn)的工作。

步驟3當(dāng)子可行覆蓋集合建立之后，對(duì)子覆蓋集合的傳感器節(jié)點(diǎn)進(jìn)行分簇，之后選取出觸頭結(jié)點(diǎn)，每個(gè)頭節(jié)點(diǎn)被選舉出來(lái)之后首先發(fā)送消息通知其鄰近節(jié)點(diǎn)。

步驟4當(dāng)鄰近的源節(jié)點(diǎn)收到對(duì)應(yīng)的簇頭節(jié)點(diǎn)發(fā)送的通知之后便開(kāi)始于對(duì)應(yīng)的頭節(jié)點(diǎn)進(jìn)行通信，頭節(jié)點(diǎn)主要負(fù)者收集周邊源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包，之后進(jìn)行數(shù)據(jù)融合處理再通過(guò)單跳或者多跳的方式轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)。這樣就形成一個(gè)連通的權(quán)重樹(shù)。

步驟5滿足設(shè)定迭代次數(shù)的選取可行覆蓋子集合之后生成帶權(quán)重邊的連通樹(shù)，直到網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量不再滿足生成可行覆蓋子集為止，獲取的網(wǎng)絡(luò)生存時(shí)間即為目標(biāo)網(wǎng)絡(luò)生命周期最優(yōu)結(jié)果。實(shí)現(xiàn)改進(jìn)混合蛙跳算法的移動(dòng)傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化方法，提高了網(wǎng)絡(luò)的覆蓋范圍與網(wǎng)絡(luò)工作效率。

4 算法仿真對(duì)比與結(jié)果分析

本文算法仿真環(huán)境在Windows7操作平臺(tái)下Matlab 2014a進(jìn)行，對(duì)改進(jìn)混合蛙跳算法與混沌量子粒子群算法[10]、混沌人工蜂群算法[11]進(jìn)行了性能對(duì)比，仿真結(jié)果表明在拓?fù)浣Y(jié)構(gòu)優(yōu)化設(shè)計(jì)中，改進(jìn)混合蛙跳算法在節(jié)點(diǎn)網(wǎng)絡(luò)總能耗、負(fù)載均衡率、分組平均投遞率、網(wǎng)絡(luò)覆蓋率、網(wǎng)絡(luò)存活節(jié)點(diǎn)個(gè)數(shù)等指標(biāo)表現(xiàn)明顯優(yōu)于混沌量子粒子群算法與混沌人工蜂群算法。在本文設(shè)定仿真環(huán)境中，傳感器節(jié)點(diǎn)感知數(shù)據(jù)能耗、接收數(shù)據(jù)能耗、傳送數(shù)據(jù)能耗、分組平均投遞率的計(jì)算公式如下：

式（10）中，εs=60×10-9J/bit；式（11）中，εr=135×10-9J/bit，控制包長(zhǎng)度為 200 bit，Eelect=45×10-9J/bit；式（12）中Fa為平均傳輸時(shí)延，F(xiàn)r為設(shè)定上一數(shù)據(jù)包傳輸時(shí)間，F(xiàn)p為數(shù)據(jù)處理時(shí)間，F(xiàn)n為到達(dá)下一跳到達(dá)時(shí)間；式（13）中Rgad為分組平均投遞率，Trdp為接收數(shù)據(jù)包總數(shù)，Tsdp為發(fā)送數(shù)據(jù)包總數(shù)。

如表1所示為仿真環(huán)境參數(shù)，發(fā)送數(shù)據(jù)包數(shù)據(jù)長(zhǎng)度l=4000 bit，閾值d0=87 m，初始能量E0=1 J。 為了算法仿真結(jié)果的可靠，仿真結(jié)果為算法平均運(yùn)行100次后得出。

表1 仿真環(huán)境參數(shù)Tab.1 Simulation environment parameters

圖4 剩余平均能量Fig.4 Residual average energy

負(fù)載均衡因子LBF是負(fù)載均衡建立在現(xiàn)有的無(wú)線傳感器網(wǎng)絡(luò)架構(gòu)之上，為網(wǎng)絡(luò)性能分析提供一種方便快捷有效的評(píng)估方法，另外LLBF定義為網(wǎng)絡(luò)內(nèi)部成員感知節(jié)點(diǎn)數(shù)（包括簇頭節(jié)點(diǎn)）方差的倒數(shù)，其中如LLBF越大，則網(wǎng)絡(luò)負(fù)載均衡性能越好，具體計(jì)算公式為

式中：nc為無(wú)線傳感器網(wǎng)絡(luò)感知節(jié)點(diǎn)的個(gè)數(shù)；xi為第i個(gè)簇頭成員中感知節(jié)點(diǎn)數(shù)；u為所有簇頭節(jié)點(diǎn)的平均節(jié)點(diǎn)數(shù)。

對(duì)于3種算法部署仿真的負(fù)載均衡性線如圖5所示，改進(jìn)混合蛙跳算法部署策略相比混沌量子粒子群算法與混沌人工蜂群算法LLBF更強(qiáng)。由圖可知本文算法LLBF在0.3～0.98之間?；煦缛斯し淙核惴ㄔ?.18～0.93之間，混沌量子粒子群算法LLBF則在0.16～0.20之間，可得出本文算法在網(wǎng)絡(luò)性能均優(yōu)越于另外2種算法。

圖5 負(fù)載均衡性Fig.5 Load balancing

分組平均投遞率為接收數(shù)據(jù)包總數(shù)與發(fā)送書(shū)包總數(shù)的比，其直接反映了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)目煽啃浴Ｈ鐖D6所示，當(dāng)通信半徑增加，混沌量子粒子群算法、混沌人工蜂群算法、本文算法的分組平均投遞率差異逐漸明顯，雖都在下降，但本文算法下降最緩慢。當(dāng)通信半徑為350 m時(shí)，混沌量子粒子群算法的分組平均投遞率為77%，混沌人工蜂群算法為82%，而本文算法依然保持著89%的高投遞率。

圖6 分組平均投遞率Fig.6 Group average delivery rate

傳感器感知范圍確定情況下有效的部署方式能夠有效提升網(wǎng)絡(luò)的覆蓋率。如圖7所示，隨著輪詢(xún)次數(shù)的增加網(wǎng)絡(luò)覆蓋率都在降低，本文算法相比混沌量子粒子群算法與混沌人工蜂群網(wǎng)絡(luò)覆蓋率在同輪詢(xún)次數(shù)時(shí)更高且下降速度緩慢，因?yàn)槠浯貎?nèi)能耗均勻分布且區(qū)域覆蓋算法設(shè)計(jì)優(yōu)良。在4000輪時(shí)混沌量子粒子群算法部署策略下網(wǎng)絡(luò)已經(jīng)完全不能有效覆蓋，混沌人工蜂群則到達(dá)了5000輪，本文算法在5000輪后依然有0.1的網(wǎng)絡(luò)覆蓋率。

圖7 網(wǎng)絡(luò)覆蓋率Fig.7 Network coverage

無(wú)線傳感網(wǎng)絡(luò)的傳感節(jié)點(diǎn)隨著時(shí)間的增加、節(jié)點(diǎn)能量的消耗，導(dǎo)致節(jié)點(diǎn)失效。如圖8所示，整個(gè)傳感網(wǎng)絡(luò)的節(jié)點(diǎn)存活數(shù)隨網(wǎng)絡(luò)節(jié)點(diǎn)工作時(shí)間增加而降低，混沌量子粒子群算法在60 s左右就出現(xiàn)了節(jié)點(diǎn)失效的現(xiàn)象，且在400 s時(shí)存活數(shù)僅為72個(gè)，存活率為72%，而混沌人工蜂群算法與本文算法在110 s左右存活數(shù)出現(xiàn)節(jié)點(diǎn)失效現(xiàn)象，相比于人工魚(yú)群算法，本文算法在400 s時(shí)仍存在85個(gè)節(jié)點(diǎn)存活，存活率依然可以保持在85%左右。

圖8 網(wǎng)絡(luò)存活節(jié)點(diǎn)個(gè)數(shù)Fig.8 Number of surviving nodes on the network

5 結(jié)語(yǔ)

本文針對(duì)傳統(tǒng)無(wú)線傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)部署方法中存在的覆蓋率低、網(wǎng)絡(luò)生命周期短等問(wèn)題，提出了改進(jìn)混合蛙跳算法的移動(dòng)傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化設(shè)計(jì)，以組內(nèi)所有青蛙的平均值與最差青蛙的差值為步長(zhǎng)基數(shù)，雙方向隨機(jī)查找更優(yōu)青蛙，利用部署策略提高了網(wǎng)絡(luò)能量利用率等。仿真表明，該改進(jìn)蛙跳算法有效可靠，可以較好解決無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化相關(guān)問(wèn)題。