蔡紹堂 ，樂英高 ，2，胡 駿 ，麻碩琪 ，曹 莉

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

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

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

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

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

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

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

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

式（1）為傳感節(jié)點到任意點距離。式（2）為傳感節(jié)點Ol到目標(biāo)節(jié)點感知測量率。式（3）為Ol中目標(biāo)節(jié)點覆蓋一坐標(biāo)為（x，y）的節(jié)點覆蓋率。設(shè)覆蓋區(qū)域I面積為ab，式（4）為傳感網(wǎng)絡(luò)區(qū)域有效覆蓋率，為傳感器工作節(jié)點有效覆蓋面積，式（5）為節(jié)點利用率，為傳感區(qū)域工作節(jié)點數(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é)點部署方案越優(yōu)。

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

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

圖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）計算每個青蛙適應(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)個體分到第一子群組，第二適應(yīng)度青蛙分到第二子群組，依次將青蛙種群劃分為包含Q只青蛙個體的M個子群，其中M×Q=F，如式（7）所示為劃分為M個子群T1，T2，…TM。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對于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ù)的比，其直接反映了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)目煽啃?。如圖6所示，當(dāng)通信半徑增加，混沌量子粒子群算法、混沌人工蜂群算法、本文算法的分組平均投遞率差異逐漸明顯，雖都在下降，但本文算法下降最緩慢。當(dāng)通信半徑為350 m時，混沌量子粒子群算法的分組平均投遞率為77%，混沌人工蜂群算法為82%，而本文算法依然保持著89%的高投遞率。

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

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

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

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

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

5 結(jié)語

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