王 磊,喬 莉,齊俊艷,劉志中

(1.河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000;2.大連理工大學(xué) 海岸和近海工程國家重點(diǎn)實(shí)驗(yàn)室,遼寧 大連 116024)

0 概述

水聲傳感網(wǎng)因其應(yīng)用前景廣闊,受到各國研究學(xué)者們的重視[1-3]。但由于節(jié)點(diǎn)能量受限,水下通過聲波傳輸需要消耗更多能量,因此提高能量利用率、延長網(wǎng)絡(luò)運(yùn)行時(shí)間的能量優(yōu)化方法是研究重點(diǎn)。對水聲傳感器網(wǎng)絡(luò)能量優(yōu)化方法的研究應(yīng)結(jié)合網(wǎng)絡(luò)自身特點(diǎn),當(dāng)前主要能量優(yōu)化方法包括物理層數(shù)據(jù)傳輸優(yōu)化、節(jié)點(diǎn)部署優(yōu)化、網(wǎng)絡(luò)層路由協(xié)議優(yōu)化等。其中,網(wǎng)絡(luò)層路由協(xié)議的優(yōu)化方法由于具有更高的實(shí)用性、健壯性、穩(wěn)定性、有效性等特性,成為學(xué)者們解決水聲傳感網(wǎng)絡(luò)能量問題的核心方法[4-6]。

但由于無線傳感網(wǎng)在水下受到帶寬窄、誤碼率高、節(jié)點(diǎn)存儲(chǔ)能量有限又不易更換等諸多因素[7]的影響,網(wǎng)絡(luò)的存活周期大幅降低,因此需設(shè)計(jì)一種降低并均衡能量損耗、延長網(wǎng)絡(luò)收集時(shí)間的路由算法。由于分簇算法能夠把較大規(guī)模的網(wǎng)絡(luò)分成幾個(gè)獨(dú)立的區(qū),每個(gè)簇首在消息傳輸前進(jìn)行消息聚合和處理,以此提高整個(gè)網(wǎng)絡(luò)的消息收發(fā)能力,并且該算法具有低功耗、易擴(kuò)展的優(yōu)點(diǎn),因此獲得了廣泛的應(yīng)用。LEACH[8]是針對陸地?zé)o線傳感網(wǎng)的一個(gè)集簇分層協(xié)議,此協(xié)議中簇首隨機(jī)選擇且單跳傳輸,但在水下環(huán)境中聲信號(hào)衰減嚴(yán)重且能量耗損與距離成正比,這使得與基站距離較遠(yuǎn)的節(jié)點(diǎn)提前失效,降低網(wǎng)絡(luò)生存周期。鑒于此,有學(xué)者提出簇間采用多跳路由方式發(fā)送數(shù)據(jù)[9],提高能量利用率,但由于多跳傳輸造成距離基站近的節(jié)點(diǎn)需承當(dāng)更多的傳播使命而變成“熱區(qū)”漏洞。因此,學(xué)者們提出了非均等成簇EEUC[10]算法,根據(jù)節(jié)點(diǎn)到基站距離不同形成大小不均等的簇,到基站距離越近簇半徑越小、成員數(shù)越少,從而緩解“熱區(qū)”問題。能量均衡的非均等成簇DEBUC[11]采用基于時(shí)間的簇首競爭僅考慮節(jié)點(diǎn)所剩能量,一定程度上規(guī)避了能量較少的節(jié)點(diǎn)參加競選,但并未考慮節(jié)點(diǎn)到SINK節(jié)點(diǎn)間距與能量損耗成比例的情況。文獻(xiàn)[12]的EOUCR協(xié)議對DEBUC算法進(jìn)行改進(jìn),簇頭競選考慮節(jié)點(diǎn)所剩能量、與Sink間距和相鄰節(jié)點(diǎn)平均剩余能量的因素,但沒有考慮到競選成功的簇頭是否能充分發(fā)揮作用;同時(shí),簇間采用貪婪算法進(jìn)行多跳傳輸,簇間路徑不具有動(dòng)態(tài)性,尋找的路徑亦不是能耗最低的。能量高效的多跳非均等成簇EEMUC[13]算法根據(jù)節(jié)點(diǎn)綜合屬性值選舉簇首,雖然在一定程度上提高了水聲傳感網(wǎng)能量的利用率,延長了網(wǎng)絡(luò)的存活周期,但隨著傳感網(wǎng)的運(yùn)轉(zhuǎn),節(jié)點(diǎn)綜合屬性值減小,網(wǎng)絡(luò)能耗急劇增加,同時(shí)多跳傳輸路徑并非最優(yōu)路徑。

為解決簇頭分布不均勻、水聲能耗不均衡、多跳傳輸路徑非最優(yōu)以及參數(shù)因素考慮不全等問題,本文設(shè)計(jì)一種非均勻成簇及簇間路由能量優(yōu)化算法,并通過仿真實(shí)驗(yàn)進(jìn)行對比分析。

1 網(wǎng)絡(luò)與能耗模型

1.1 網(wǎng)絡(luò)模型

為了方便研究路由算法對水下網(wǎng)絡(luò)性能的影響,本文考慮二維靜態(tài)水下傳感網(wǎng),對改進(jìn)算法的網(wǎng)絡(luò)模型作如下假設(shè):

1)所有節(jié)點(diǎn)具有相似的處理/通信能力、初始能量相同且具有唯一的ID號(hào);

2)所有節(jié)點(diǎn)可以通過水聲信號(hào)強(qiáng)度來測算到基站距離,自動(dòng)控制發(fā)射功率以減少能耗;

3)節(jié)點(diǎn)部署在水下特定范圍內(nèi),位置不變且能量有限,而Sink節(jié)點(diǎn)有持續(xù)的能量源不許考慮能耗;

4)所有節(jié)點(diǎn)鏈路對稱可感知自己所剩能量并進(jìn)行數(shù)據(jù)融合。

二維靜態(tài)水下傳感網(wǎng)絡(luò)模型如圖1所示。

圖1 二維靜態(tài)水下傳感網(wǎng)絡(luò)模型

1.2 能耗模型

水下傳感器網(wǎng)絡(luò)通過聲信號(hào)作為信息載體把數(shù)據(jù)傳播出去,不同于陸地節(jié)點(diǎn)的能量消耗,水下傳感節(jié)點(diǎn)的能耗隨著距離的增加成指數(shù)級(jí)增長,且水下節(jié)點(diǎn)的能耗主要由傳輸能耗構(gòu)成。本文算法采用與文獻(xiàn)[14]相同的水聲通信能耗模型,式(1)給出了節(jié)點(diǎn)能耗模型:

(1)

其中,f是聲信號(hào)頻率,d是傳播距離,k為路徑耗損指數(shù)。式(2)是由于多普勒效應(yīng)而造成與聲信號(hào)頻率f關(guān)聯(lián)的能量衰減指數(shù):

2.75×10-4f2+0.003

(2)

2 蟻群優(yōu)化的成簇算法

改進(jìn)的蟻群優(yōu)化成簇算法流程如圖2所示。在水下傳感網(wǎng)絡(luò)的初始階段,基站首先廣播一條提前分配給各個(gè)節(jié)點(diǎn)的TDMA時(shí)隙消息,節(jié)點(diǎn)在收到這條消息后,根據(jù)接收到信號(hào)強(qiáng)度不同估算到匯聚節(jié)點(diǎn)間的距離,節(jié)點(diǎn)據(jù)此確定信號(hào)的發(fā)射功率及如何進(jìn)行分簇。

圖2 改進(jìn)的蟻群優(yōu)化成簇算法流程

對本文算法的設(shè)計(jì)優(yōu)化,每一輪均包含非均等成簇和簇間多跳傳播2個(gè)階段。首先節(jié)點(diǎn)形成一個(gè)0-1之間的隨機(jī)數(shù)u,然后計(jì)算成為待選簇首的閾值T(n),閾值T(n)與u進(jìn)行比較,若u

2.1 非均等成簇

2.1.1 候選簇首生成

式(3)、式(4)分別為EOUCR算法和本文提出的改進(jìn)算法的簇首選舉閾值公式。從式(3)可以看出,原EOUCR算法僅考慮了節(jié)點(diǎn)的所剩能量,并沒有考慮候選簇首與匯聚節(jié)點(diǎn)距離。對此,改進(jìn)后的閾值公式增加了節(jié)點(diǎn)自身所剩能量與到基站距離,一定范圍內(nèi)規(guī)避了所剩能量較少、距離基站較遠(yuǎn)的節(jié)點(diǎn)參與競選。若參選節(jié)點(diǎn)的所剩能量較充裕,到基站距離較近時(shí),此節(jié)點(diǎn)有更大幾率變成候選簇首;同時(shí),考慮到隨著網(wǎng)絡(luò)的運(yùn)行節(jié)點(diǎn)能量一直在減少,這導(dǎo)致被選為候選簇首的節(jié)點(diǎn)數(shù)量越來越少,為此增加能耗因子γ(1-Ei-res/Ei-init)對閾值大小進(jìn)行調(diào)整,能更好地平衡網(wǎng)絡(luò)能耗。閾值T(n)new計(jì)算公式如式(4)所示。

(3)

(4)

其中,α、β、γ為參數(shù)控制因子且α+β+γ=1,p為簇頭數(shù)目與總節(jié)點(diǎn)數(shù)目比重,r為當(dāng)前輪數(shù),在前r×mod(1/p)輪中,沒有參選過候選簇首的所有節(jié)點(diǎn)組成的一個(gè)群集G,Ei_cur為節(jié)點(diǎn)所剩能量,Ei_init為節(jié)點(diǎn)初始能量,daver為節(jié)點(diǎn)到基站的平均距離大小,dmax、d(i,bs)分別為節(jié)點(diǎn)到基站的最大距離與當(dāng)前節(jié)點(diǎn)到基站的距離。

2.1.2 節(jié)點(diǎn)競爭半徑計(jì)算

由于水聲網(wǎng)絡(luò)對能量的要求較為苛刻,為此,參考文獻(xiàn)[15]中節(jié)點(diǎn)競爭半徑的計(jì)算,引入因節(jié)點(diǎn)所剩能量和到基站的距離而動(dòng)態(tài)變化的節(jié)點(diǎn)競爭半徑Rcom,計(jì)算公式如式(5)所示。

(5)

其中,ξ、φ為參數(shù)控制因子,Eaver為節(jié)點(diǎn)平均剩余能量,R0為節(jié)點(diǎn)最大競爭半徑,其余參數(shù)與式(3)意義相同。在網(wǎng)絡(luò)初始時(shí)期,節(jié)點(diǎn)初始能量相等,競爭半徑大小主要取決于節(jié)點(diǎn)與基站的距離,隨著網(wǎng)絡(luò)的運(yùn)轉(zhuǎn),節(jié)點(diǎn)的能量在減少,這時(shí)競爭半徑由節(jié)點(diǎn)所剩能量和到基站的距離共同決定,由此形成的競爭半徑不會(huì)由于遠(yuǎn)離基站而保持著較大的簇規(guī)模,控制簇頭的分布范圍,從而均衡節(jié)點(diǎn)能量耗損。

2.1.3 成簇權(quán)值計(jì)算

水聲無線傳感網(wǎng)的生存周期能否得以延長主要為能否降低節(jié)點(diǎn)能耗,因此,需考慮簇首的能耗,簇首耗能不僅包含簇間數(shù)據(jù)傳輸而且包含簇內(nèi)數(shù)據(jù)收集,所以,在節(jié)點(diǎn)選擇入簇時(shí)要考慮節(jié)點(diǎn)的入簇權(quán)值。本文算法在參考了文獻(xiàn)[16]中入簇權(quán)值(式(6))的基礎(chǔ)上進(jìn)行改進(jìn),改進(jìn)算法的入簇權(quán)值不僅考慮了簇首的能量剩余、到基站距離,同時(shí)考慮到簇內(nèi)成員數(shù)目。改進(jìn)成簇權(quán)值計(jì)算函數(shù)Wi如式(7)所示。

(6)

(7)

其中,λ1、λ2、λ3為參數(shù)控制因子且λ1+λ2+λ3=1,Ech-init為簇節(jié)點(diǎn)初始能量,Ech-cur為簇節(jié)點(diǎn)所剩能量,d(i,bs)與式(3)意義相同,d(i,ch)為節(jié)點(diǎn)i到簇首的間距,Nnb為當(dāng)前簇首的成員數(shù)目,N為總結(jié)點(diǎn)數(shù)目。從式(6)可知,當(dāng)節(jié)點(diǎn)所要加入簇的簇首所剩能量Ech-cur越大、兩者的歐式間距d(i,ch)越小且簇內(nèi)成員數(shù)目Nnb較少時(shí),則節(jié)點(diǎn)更有可能進(jìn)入該簇,實(shí)現(xiàn)合理均衡分簇。

2.2 簇間多跳路由

在簇間多跳路由階段,對于如何選擇最優(yōu)的通信路徑問題,本文通過改善蟻群算法的啟發(fā)函數(shù),以找到能量消耗盡量小、跳數(shù)路徑盡量最優(yōu)的途徑。蟻群算法[17]用于通過信息素痕跡和啟發(fā)函數(shù)信息的指引來構(gòu)造最優(yōu)路徑。

2.2.1 啟發(fā)函數(shù)的改進(jìn)

蟻群算法起初用于解決旅行商問題[18],僅考慮兩點(diǎn)間的距離并且在多路徑優(yōu)化方面有很好的效果。若把此算法引入傳感網(wǎng)用來尋找最優(yōu)路徑問題,不能單一考慮兩節(jié)點(diǎn)間距。針對文獻(xiàn)[19]中啟發(fā)函數(shù)(如式(8)所示)僅考慮到簇節(jié)點(diǎn)間距及剩余能量所帶來的因跳數(shù)較多而造成的能耗問題,本文改進(jìn)的啟發(fā)函數(shù)在考慮了簇節(jié)點(diǎn)間距及剩余能量的同時(shí)考慮到了節(jié)點(diǎn)跳數(shù)問題,由此,本文新啟發(fā)函數(shù)定義如式(9)所示。

(8)

(9)

2.2.2 信息素更新

螞蟻k從簇節(jié)點(diǎn)i跳轉(zhuǎn)到簇節(jié)點(diǎn)j后,要對此段路上的信息素按式(10)進(jìn)行更新:

τ(i,j)new=(1-×Δt)×τ(i,j)old+Δτ(i,j)

(10)

(11)

(12)

其中,e為默許的信息素?fù)]發(fā)系數(shù),ω為默許的信息素局部更新增量。由于傳播距離和跳數(shù)共同決定數(shù)據(jù)的能耗,因此從式(8)可知,新的啟發(fā)函數(shù)將降低節(jié)點(diǎn)傳播能耗。

2.2.3 路徑選擇概率

螞蟻k在t時(shí)間內(nèi)從節(jié)點(diǎn)i跳轉(zhuǎn)到節(jié)點(diǎn)j,可由式(13)、式(14)的選取函數(shù)來決定:

(13)

(14)

其中,θt(i,j)為t時(shí)間從節(jié)點(diǎn)i到節(jié)點(diǎn)j的決策因子,Zk(i)為螞蟻k在節(jié)點(diǎn)i下一跳簇節(jié)點(diǎn)群集,q0為控制采取先驗(yàn)常識(shí)與摸索新路徑的緊要性,規(guī)避節(jié)點(diǎn)能耗不均的情況,q是0-1之間的隨機(jī)數(shù),若q≤q0,則選取決策因子極大的節(jié)點(diǎn),反之,則根據(jù)下一跳節(jié)點(diǎn)的幾率進(jìn)行選取。決策因子θt(i,j)的計(jì)算如式(15)所示。

θt(i,j)=ατt(i,j)+βηt(i,j)

(15)

其中,τt(i,j)表示t時(shí)刻鏈路i節(jié)點(diǎn)與j節(jié)點(diǎn)間的信息素濃度,ηt(i,j)表示在同樣的鏈路下的啟發(fā)函數(shù),α、β分別為信息素濃度和啟發(fā)函數(shù)的參數(shù)控制因子。

3 仿真實(shí)驗(yàn)與結(jié)果分析

本文算法使用Matlab仿真軟件進(jìn)行仿真實(shí)驗(yàn),針對水下傳感器網(wǎng)絡(luò)的環(huán)境特性,將200個(gè)傳感節(jié)點(diǎn)隨機(jī)部署在1 000 m×1 000 m區(qū)域中,基站位置為(500 m,1 050 m)。仿真實(shí)驗(yàn)實(shí)現(xiàn)對LEACH、EEUC、EEMUC和本文算法在網(wǎng)絡(luò)穩(wěn)健性、簇首能耗和網(wǎng)絡(luò)所剩能量方面的分析對照。仿真參數(shù)如表1示。

表1 實(shí)驗(yàn)仿真參數(shù)設(shè)置

節(jié)點(diǎn)存活數(shù)量多少是權(quán)衡水聲傳感網(wǎng)性能的指標(biāo)之一。

如圖3所示,在仿真輪數(shù)相同的情況下,本文算法一直都較LEACH、EEUC和EEMUC算法的存活節(jié)點(diǎn)數(shù)多且最晚死亡,這是由于本文算法成簇時(shí)包括了節(jié)點(diǎn)所剩能量、到基站間距大小,同時(shí)在節(jié)點(diǎn)入簇時(shí)考慮了成簇能耗且簇間使用改善的蟻群算法進(jìn)行消息的多跳傳輸,從而更有利于均衡能耗。

圖3 4種算法的生存節(jié)點(diǎn)數(shù)目比較

圖4(a)～圖4(d)分別表示在網(wǎng)絡(luò)沒有任何節(jié)點(diǎn)失效時(shí)4種算法的簇首個(gè)數(shù)分布情況。

圖4 4種算法簇首個(gè)數(shù)分布情況

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的穩(wěn)健性取決于節(jié)點(diǎn)的存活數(shù)和簇首數(shù)目的變動(dòng)范圍。由圖4可知,LEACH算法簇首變動(dòng)范圍[7,28],高于其他2種算法,其主要原因是LEACH采用隨機(jī)選取策略使簇首很難控制;EEUC算法簇首變動(dòng)范圍[9,19],較LEACH算法的簇首變動(dòng)范圍有所縮減,其原因是EEUC算法在簇首競選時(shí)加入了節(jié)點(diǎn)的所剩能量,從而在一定程度上控制了簇首變動(dòng)范圍;EEMUC算法簇首變動(dòng)范圍[12,19],本文算法為[13,18],簇首變動(dòng)范圍最小。這是由于本文算法對閾值公式進(jìn)行改進(jìn)優(yōu)化選舉簇首,考慮節(jié)點(diǎn)所剩能量同時(shí)考慮節(jié)點(diǎn)與基站間距大小,節(jié)點(diǎn)入簇時(shí)考慮成簇能耗,這保證了最終簇首在局部范圍內(nèi)生成,故簇首變動(dòng)范圍較小,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)較穩(wěn)定,這也與圖3中的本文算法的節(jié)點(diǎn)存活曲線相一致。

如圖5所示,本文算法簇首耗能最少,其原因是本文算法簇首采用多跳的方式與基站進(jìn)行數(shù)據(jù)傳輸,且傳輸路徑是根據(jù)改進(jìn)蟻群算法探索到的最好途徑;EEMUC與EEUC算法簇首耗能次之;LEACH算法的簇首耗能最大,這不僅因?yàn)槠浯厥撞扇‰S機(jī)選舉策略,而且也由于簇首單跳方式進(jìn)行消息傳遞,所以與基站通信耗能較大。

圖5 簇首耗能之和對比

如圖6所示,LEACH算法網(wǎng)絡(luò)能耗最大,這是因?yàn)榇厥追植疾痪?距離更遠(yuǎn)的節(jié)點(diǎn)單跳傳輸需耗損大量能量,所以網(wǎng)絡(luò)耗能最大、生存時(shí)間最短;EEUC算法網(wǎng)絡(luò)耗能次之,其原因是簇首的選舉考慮節(jié)點(diǎn)能量且多跳傳輸,與LEACH算法相比網(wǎng)絡(luò)耗能有一定的減少;EEMUC算法又較EEUC能耗有所縮減,是因?yàn)榇厥椎母傔x考慮了節(jié)點(diǎn)能量、到基站間距和節(jié)點(diǎn)度,不僅簇內(nèi)消息接收且簇間數(shù)據(jù)傳輸均有足夠的能量,但隨著網(wǎng)絡(luò)的運(yùn)轉(zhuǎn),簇首得不到合理選擇,能量耗損急速增長;本算法網(wǎng)絡(luò)能耗最少,主要由于對簇首閾值進(jìn)行改進(jìn),選舉合理的簇首且在節(jié)點(diǎn)入簇時(shí)考慮入簇耗能并加入簇首能量較大的簇,在簇間引入改進(jìn)的蟻群算法得到最優(yōu)數(shù)據(jù)傳輸路徑,使能量消耗進(jìn)一步減小、生存周期得到延伸。

圖6 網(wǎng)絡(luò)所剩能量對比

4 結(jié)束語

為平衡水聲無線傳感網(wǎng)的能耗、延長網(wǎng)絡(luò)生存周期,本文設(shè)計(jì)一種非均勻成簇及簇間路由能量優(yōu)化的算法。該算法簇首閾值公式考慮了節(jié)點(diǎn)所剩能量、到基站距離與能耗因子,隨著網(wǎng)絡(luò)的運(yùn)行,選舉的簇首不會(huì)因節(jié)點(diǎn)所剩能量的減少而出現(xiàn)不均勻的情況;引入的競爭半徑隨著節(jié)點(diǎn)能量多少與到基站距離大小而動(dòng)態(tài)變化,從而均衡節(jié)點(diǎn)能耗;改進(jìn)的入簇權(quán)值考慮了簇首能量、節(jié)點(diǎn)到簇首距離與簇內(nèi)成員數(shù)目,實(shí)現(xiàn)合理均衡分簇;簇間引入改善的蟻群算法,不僅啟發(fā)函數(shù)考慮了節(jié)點(diǎn)能量、節(jié)點(diǎn)跳數(shù)與下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)距離,且在信息素更新時(shí)引入簇節(jié)點(diǎn)所剩能量百分比,以便在尋找到最優(yōu)的數(shù)據(jù)傳輸路徑時(shí)規(guī)避信息素濃度高而節(jié)點(diǎn)所剩能量少的情況,延長網(wǎng)絡(luò)生存時(shí)間。仿真結(jié)果表明,與LEACH、EEUC和EEMUC算法相比,該算法平衡了傳感網(wǎng)能量耗損、提升了能量使用率,延長了傳感網(wǎng)生存周期。