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

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

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

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

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

1 拓撲結(jié)構(gòu)優(yōu)化最優(yōu)覆蓋問題

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

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

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

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

2 改進混合蛙跳算法

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

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

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

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

（2）計算每個青蛙適應度函數(shù)；

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

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

（4）子種群劃分：將最優(yōu)個體分到第一子群組，第二適應度青蛙分到第二子群組，依次將青蛙種群劃分為包含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進行更新。其中Dmax表示最大移動步長，g表示子群搜索迭代次數(shù)；利用最優(yōu)青蛙與最差青蛙的歷史最優(yōu)位置之間隨機點出發(fā)，以組內(nèi)所有青蛙的平均值與最差青蛙的差值為步長基數(shù)，雙方向隨機查找更優(yōu)青蛙。直到更新后的最差解適應度小于原適應度最差解，隨之將其代替。在設置進化代數(shù)內(nèi)進行循環(huán)更新，在滿足達到進化代數(shù)的同時找到子群最差解，否則重復局部搜索步驟。

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

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

3 改進混合蛙跳在拓撲結(jié)構(gòu)優(yōu)化中應用

根據(jù)移動無線傳感器網(wǎng)絡拓撲結(jié)構(gòu)特點，本文對其基于特性條件約束，賦予人為定義并優(yōu)化，使用層次型拓撲結(jié)構(gòu)作為無線傳感網(wǎng)絡拓撲基本模型，綜合拓撲結(jié)構(gòu)優(yōu)化策略，提出能量高效的拓撲控制算法：以同一概率周期性隨機選擇簇頭，令移動傳感網(wǎng)絡的總體能量消耗均衡分配至各傳感器節(jié)點中，實現(xiàn)簇中成員節(jié)點數(shù)據(jù)的均衡分布，完成無線傳感網(wǎng)絡拓撲結(jié)構(gòu)的設計。該算法在保證數(shù)據(jù)時延性要求的條件下，提高網(wǎng)絡覆蓋率和數(shù)據(jù)傳輸穩(wěn)定性。

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

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

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

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

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

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

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

本文算法仿真環(huán)境在Windows7操作平臺下Matlab 2014a進行，對改進混合蛙跳算法與混沌量子粒子群算法[10]、混沌人工蜂群算法[11]進行了性能對比，仿真結(jié)果表明在拓撲結(jié)構(gòu)優(yōu)化設計中，改進混合蛙跳算法在節(jié)點網(wǎng)絡總能耗、負載均衡率、分組平均投遞率、網(wǎng)絡覆蓋率、網(wǎng)絡存活節(jié)點個數(shù)等指標表現(xiàn)明顯優(yōu)于混沌量子粒子群算法與混沌人工蜂群算法。在本文設定仿真環(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ù)據(jù)包傳輸時間，F(xiàn)p為數(shù)據(jù)處理時間，F(xiàn)n為到達下一跳到達時間；式（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

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

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

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

圖5 負載均衡性Fig.5 Load balancing

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

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

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

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

無線傳感網(wǎng)絡的傳感節(jié)點隨著時間的增加、節(jié)點能量的消耗，導致節(jié)點失效。如圖8所示，整個傳感網(wǎng)絡的節(jié)點存活數(shù)隨網(wǎng)絡節(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)絡存活節(jié)點個數(shù)Fig.8 Number of surviving nodes on the network

5 結(jié)語

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