王 鑫，徐海濤，蔣 華，覃 琴

(1.桂林電子科技大學(xué) 計算機(jī)與信息安全學(xué)院，廣西 桂林 541004； 2.桂林電子科技大學(xué)北海校區(qū) 海洋信息工程學(xué)院，廣西 北海 541000)

0 引 言

水下傳感網(wǎng)絡(luò)(underwater sensor networks，UWSNs)的發(fā)展促進(jìn)了各種應(yīng)用的發(fā)展，包括海洋環(huán)境監(jiān)測、海洋地質(zhì)勘探、水下資源開發(fā)和災(zāi)難預(yù)警等[1,2]。由于水域環(huán)境特殊，水下聲通信存在著巨大挑戰(zhàn)。例如能見度跟蹤能力差、聲音的傳播速度低，以及海水的高動態(tài)物理特性，如溫度、壓力和鹽度使其具有多樣性。因此，通過使用具有低帶寬聲學(xué)調(diào)制解調(diào)器的多個傳感器來監(jiān)視這種挑戰(zhàn)性環(huán)境變得至關(guān)重要。由于海洋面積廣闊并且占地球表面的四分之三，所以必須部署多個傳感器來監(jiān)測待測區(qū)域。目前，水下傳感器網(wǎng)絡(luò)的主要挑戰(zhàn)是在整個網(wǎng)絡(luò)生命周期內(nèi)保持節(jié)點之間的能量水平平衡，有效的路由協(xié)議成為完成水域監(jiān)測的必要條件。

近年來，一些科研機(jī)構(gòu)和研究者提出了許多新的路由協(xié)議，文獻(xiàn)[3]提到了一種基于深度的DBR(depth-based routing)路由協(xié)議，節(jié)點通過深度信息進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。文獻(xiàn)[4]提出了多層路由協(xié)議MRP(multi-layer routing protocol)，通過超級節(jié)點解決了空間信息的需求，并通過不同的層轉(zhuǎn)發(fā)數(shù)據(jù)包。文獻(xiàn)[5]提到了DBR協(xié)議改進(jìn)的路由協(xié)議EEDBR，EEDBR考慮了節(jié)點能量和深度信息來選擇下一跳節(jié)點，將感測到的數(shù)據(jù)轉(zhuǎn)發(fā)到淺深度并具有高能量的節(jié)點。文獻(xiàn)[6]提出一種基于輪換轉(zhuǎn)發(fā)優(yōu)先級的機(jī)會路由RFP-OR(rotating forwarding priority-based OR)。通過考慮數(shù)據(jù)包傳遞率、能耗和水壓值估計節(jié)點的適度值，以此來進(jìn)行候選轉(zhuǎn)發(fā)節(jié)點的選擇，并設(shè)置各節(jié)點的轉(zhuǎn)發(fā)優(yōu)先級。節(jié)點轉(zhuǎn)發(fā)優(yōu)先級的輪換通過更新節(jié)點的適度值來實現(xiàn)。

為進(jìn)一步均衡水下傳感網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生命周期，本文提出一種多目標(biāo)優(yōu)化機(jī)會路由MOO-BA。仿真結(jié)果表明，與DBR和EEDBR相比，本協(xié)議在能量高效性、均衡性等方面均具有明顯優(yōu)勢，有效地延長網(wǎng)絡(luò)的使用壽命。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)架構(gòu)

MOO-BA采用多Sink網(wǎng)絡(luò)架構(gòu)如圖1所示，該架構(gòu)由3個部分組成，即控制中心、匯聚節(jié)點和水下傳感器，其中水下傳感器包括錨定節(jié)點、中繼節(jié)點。

圖1 網(wǎng)絡(luò)模型

錨定節(jié)點固定在海洋底部，只感知并收集數(shù)據(jù)。中繼節(jié)點部署在不同的深度，不僅可以發(fā)送數(shù)據(jù)包，還可以轉(zhuǎn)發(fā)接收到的數(shù)據(jù)包。控制中心放置在船舶或海灘上，并從匯聚節(jié)點接收數(shù)據(jù)包。

匯聚節(jié)點部署在水面上，配備無線電和聲學(xué)調(diào)制解調(diào)器以及無限的能量。聲學(xué)調(diào)制解調(diào)器用于水下傳感器節(jié)點接收數(shù)據(jù)分組，而無線電波用于將收集的數(shù)據(jù)轉(zhuǎn)發(fā)到岸上控制中心。

1.2 能量傳播模型

水聲信號傳播模型采用Stojanovic[7]提出的水下信道設(shè)計模型?；跀U(kuò)散損耗計算信號的總衰減，并考慮thorps模型用于信號吸收損耗。在給定頻率f下，吸收損失α(f) 可以表示為

(1)

其中，α(f) 以dB/km為單位，f以kHz為單位。

通過式(1)吸收損失值α可以推導(dǎo)為α=10α(f)/10?？偹p量A(d,f) 可以通過組合吸收損耗和擴(kuò)散損耗來獲得，如式(2)所示，距離d上的聲道衰減可表示為

10log(A(d,f))=k×10logd+d×10log(α(f))

(2)

其中，第一項是擴(kuò)散損失，第二項是吸收損失，k代表擴(kuò)散系數(shù)，它定義了傳播的幾何形狀(即k=1是淺水區(qū)域的圓柱形擴(kuò)展，k=2是深水區(qū)域球形擴(kuò)展，k=1.5是實際的擴(kuò)展)，α(f) 代表吸收系數(shù)。水下環(huán)境噪聲[8]可表示為

N(f)=Nt(f)+Ns(f)+Nw(f)+Nth(f)

(3)

其中，Nt(f)、Ns(f)、Nw(f) 和Nth(f) 分別表示由湍流、運(yùn)輸、波浪和熱能引起的噪聲。對于頻率為f的聲學(xué)信號和水下環(huán)境中d的傳播距離，接收機(jī)的信噪比可表示為

SNR(f,d)=P(f)-A(d,f)-N(f)+DI

(4)

其中，P(f) 是發(fā)送方的頻率為f的發(fā)送功率。DI是指向性指數(shù)，是接收器方向靈敏度的函數(shù)或用于傳感器節(jié)點引導(dǎo)其水聽器以避免不必要噪聲。在接收器處，如果SNR(f,d) 等于或大于DT(檢測閾值)，則接收器可以正確地解碼所接收的信號。

2 MOO-BA路由

2.1 問題描述

傳統(tǒng)路由通過貪婪策略選擇一跳鄰居范圍內(nèi)的最佳轉(zhuǎn)發(fā)節(jié)點，很容易陷入局部最優(yōu)解決方案。同時，滿足深度小于當(dāng)前節(jié)點條件的節(jié)點都會參與到數(shù)據(jù)包的轉(zhuǎn)發(fā)工作中，這會導(dǎo)致多個節(jié)點同時轉(zhuǎn)發(fā)相同數(shù)據(jù)包，造成數(shù)據(jù)冗余和能耗。

本文針對傳統(tǒng)協(xié)議能耗不均衡問題，提出一種多目標(biāo)優(yōu)化機(jī)會路由來均衡網(wǎng)絡(luò)能耗。

2.2 MOO-BA中的分組結(jié)構(gòu)和消息流

MOO-BA的路由分組類型和消息格式如圖2和圖3所示。任何數(shù)據(jù)包的數(shù)據(jù)包標(biāo)題包含兩個字段：發(fā)件人ID、數(shù)據(jù)包序列號。發(fā)件人ID是水下傳感器節(jié)點的標(biāo)識符；分組序列號是由水下傳感器節(jié)點分配給分組的唯一序列號。發(fā)件人ID與數(shù)據(jù)包序列號相結(jié)合有助于避免路由過程中的重復(fù)。路由信息包括能量和深度。能量是信標(biāo)節(jié)點的剩余能量；深度是當(dāng)前轉(zhuǎn)發(fā)器的深度信息，在信標(biāo)發(fā)送階段每個節(jié)點自動更新。

圖2 數(shù)據(jù)包格式

圖3 邀請請求接受消息格式

路由信息包括5種類型的請求，即邀請請求、邀請請求接受、邀請請求確認(rèn)、邀請請求拒絕、選擇另一個最佳轉(zhuǎn)發(fā)器。邀請請求IR(invitation request)是發(fā)送給符合條件的一跳鄰居的初始信標(biāo)消息。在接收到邀請請求后，在動態(tài)壽命估計(DLE)之后發(fā)出邀請請求接受IRA(invitation request acceptance)。邀請請求確認(rèn)IRC(invitation request confirmation)是數(shù)據(jù)傳輸之前的最終消息。邀請請求拒絕IRR(invitation request rejection)是在請求超過DLE時發(fā)出的拒絕消息。選擇另一個最佳轉(zhuǎn)發(fā)器SAOF(selected another optimal forwarder)是發(fā)送到所有節(jié)點的重定向消息。

2.3 初始信標(biāo)

在初始信標(biāo)期間，水下傳感器節(jié)點在位于傳輸范圍(Ni)之間驗證身份，同時維護(hù)一張 [ENS(Ni)] 表，[ENS(Ni)] 將符合條件的鄰居節(jié)點插入到接收器中，其深度小于已發(fā)起請求的節(jié)點的接收器。其中深度測量為必要條件，深度信息由深度傳感器探測獲得。

當(dāng)傳感器向上轉(zhuǎn)發(fā)數(shù)據(jù)包時，就可以在符合條件的鄰居節(jié)點選擇列表 [ENS(Ni)] 中選擇最佳轉(zhuǎn)發(fā)器進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，防止傳感器節(jié)點向所有鄰居節(jié)點廣播邀請請求。初始信標(biāo)過程如下：①較深處傳感器節(jié)點將邀請請求(IR)廣播到 [ENS(Ni)] 中；②列出的淺深度節(jié)點。

2.4 動態(tài)壽命估計(DLE)

假設(shè)同質(zhì)傳感器由S={s1，s2，…sn} 表示，并且每個傳感器節(jié)點都能夠基于基本信息(如能量、深度)從該組轉(zhuǎn)發(fā)器中選擇最佳轉(zhuǎn)發(fā)器。如式(5)所示，只有當(dāng)節(jié)點的剩余能量高于εng(τth) 時，節(jié)點才能將自身聲明為最優(yōu)轉(zhuǎn)發(fā)器。εng(τth) 定義為在距離t上發(fā)送k比特消息所需的最小能量

(5)

在通信的初始階段，每個節(jié)點的剩余能量將近似等于初始能量。節(jié)點的剩余能量表示為

εng剩余=εng初始-εng消耗

(6)

每個節(jié)點消耗的能量表示為

εng消耗=εng傳輸+εng接收

(7)

網(wǎng)絡(luò)中的所有節(jié)點能量估計DLE表示為

(8)

2.4.1 基于動態(tài)壽命估計的接受(DLEA)

DLEA根據(jù)DLE確定是否可以處理特定請求IR，并根據(jù)單個節(jié)點的DLE評估情況發(fā)出IRA或IRR令牌。接收到IR并發(fā)出IRA的淺深度節(jié)點充當(dāng)父節(jié)點，而通過發(fā)送IRC確認(rèn)IRA的深度節(jié)點充當(dāng)子節(jié)點。網(wǎng)絡(luò)中所有節(jié)點都維護(hù)兩個名為LOA(list of acceptances)和LOC(list of confirmations)的表，LOA表包含父節(jié)點發(fā)出的IRA，LOC表包含子節(jié)點發(fā)出的IRC。當(dāng)接收到IR時，父節(jié)點基于DLE來確定該請求是否在父節(jié)點的容量范圍內(nèi)。如式(9)所示，通過將LOAm、LOCm進(jìn)行計數(shù)相加，如果當(dāng)前請求的和值小于特定節(jié)點的DLEm，則發(fā)出IRA令牌，并在LOAm中添加一個條目。否則發(fā)出IRR令牌

(9)

其中，LOAm為接受請求條目列表，LOCm為確認(rèn)請求條目列表，DLEm為特定節(jié)點的動態(tài)壽命估計。

2.4.2 基于動態(tài)壽命估計的確認(rèn)(DLEC)

DLEC是用來確定是否可以確認(rèn)收到的IRA。在此階段，子節(jié)點有機(jī)會根據(jù)能量深度范圍(EDR)信息確認(rèn)最佳父節(jié)點之一。IRA由父節(jié)點在淺層發(fā)布。在接收到IRA令牌之后收到信息的子節(jié)點確認(rèn)淺深度處的最佳轉(zhuǎn)發(fā)器節(jié)點。輪詢基于表中該節(jié)點維護(hù)的EDR信息。如果一個子節(jié)點收到一個或一個以上的IRA令牌，就有機(jī)會成為上層朝向接收器的最佳節(jié)點

Max{EDR={Em，Dm};m=1,2…n}

(10)

其中，Em和Dm是LOAm中從接收器到節(jié)點的能量和深度差異。

一旦深層節(jié)點通過基于式(10)中的條件發(fā)出IRC，則將此條目添加到在LOCm中，同時此節(jié)點向最先發(fā)送IRA請求的淺層節(jié)點發(fā)送通知消息SAOF(selected another optimal forwarder)。收到SAOF消息的淺層節(jié)點從LOAm中刪除接受條目并更新DLEm。

2.5 初始路徑

通過連接子節(jié)點和父節(jié)點，從源到目的地建立路徑進(jìn)行數(shù)據(jù)傳輸。在初始階段，較高深度的節(jié)點n發(fā)出IRC到淺層節(jié)點m，將已啟動傳輸?shù)墓?jié)點n添加到路徑中，直到m等于sink。

2.6 標(biāo)準(zhǔn)蝙蝠算法

由Xin-She Yang開發(fā)的一種新的元啟發(fā)式搜索算法稱為蝙蝠算法[9]。通過模擬蝙蝠的回聲定位能力，實現(xiàn)了群優(yōu)化問題的求解。

fi=fmin+(fmax-fmin)β

(11)

(12)

(13)

其中，β∈[0,1] 是服從均勻分布的隨機(jī)向量，x*是當(dāng)前全局最佳位置(解)。

通過比較n個蝙蝠找到的最優(yōu)解，每個蝙蝠開始時會被隨機(jī)分配一個服從均勻分布 [fmin,fmax] 的頻率。對于局部搜索部分，一旦從當(dāng)前最佳解中選擇了一個解，則使用隨機(jī)游走對每個蝙蝠產(chǎn)生一個新解

xnew=xold+δA(t)

(14)

從實現(xiàn)的角度來看，最好能夠提供一個縮放參數(shù)來控制步長。因此，可以將這個方程改寫為

xnew=xold+σδtA(t)

(15)

其中，δt服從高斯正態(tài)分布N(0,1)，σ是縮放因子。響度Ai和脈沖發(fā)射率ri也隨著迭代的進(jìn)行而相應(yīng)地更新。更新公式為

(16)

(17)

其中，α和γ是常數(shù)。對于任何0<α<1和γ>0，有

(18)

2.7 改進(jìn)BA的路徑優(yōu)化

2.7.1 引入優(yōu)化因子[9]

由于經(jīng)典蝙蝠算法在進(jìn)行迭代優(yōu)化時會陷入局部優(yōu)化性，因此引入優(yōu)化因子λ來對MOO-BA算法的頻率進(jìn)行優(yōu)化，以此來達(dá)到全局搜索和局部搜索的平衡。

將式(11)變更為式(19)

fi=(fmin+(fmax-fmin)β)λ

(19)

(20)

式中：t為當(dāng)前迭代次數(shù)，由式(20)可以看出，λ的大小隨著t的增長而減小。在迭代初期時，t值較小，λ值較大，因此蝙蝠發(fā)出的脈沖頻率較高，加大了全局搜索的力度；而在迭代后期，隨著t值的增大λ值變小，脈沖頻率較低，加強(qiáng)了局部搜索的能力。

2.7.2 算法步驟

BA優(yōu)化路徑的具體過程如下：

步驟1 基于DLE初始化蝙蝠種群Xi和Vi(i=1,2,…,n) 初始化頻率fi，脈沖發(fā)射率ri，響度Ai和最大迭代次數(shù)Nmax；

步驟3 根據(jù)式(11)～式(13)，對網(wǎng)絡(luò)中的蝙蝠的速度和位置進(jìn)行更新；

步驟4 生成隨機(jī)數(shù)R1，假如R1大于ri時,從最佳解中選擇一個BB(解)，圍繞BB產(chǎn)生一個LBB(局部解)；

步驟5 生成隨機(jī)數(shù)R2，假如R2小于Ai同時f(xi)

步驟6 經(jīng)過一段時間運(yùn)行，對新的蝙蝠群體進(jìn)行評估判定,把網(wǎng)絡(luò)中所有的蝙蝠適應(yīng)度值按照從大到小順序排列，找到最小值以及對應(yīng)的位置，就是當(dāng)前最優(yōu)解和最優(yōu)值；

步驟7 重復(fù)執(zhí)行步驟2～步驟5，直到滿足設(shè)定的最優(yōu)解條件或達(dá)到最大迭代次數(shù)；

步驟8 輸出全局最優(yōu)值和最優(yōu)解。

具體流程如圖4所示。

圖4 MOO-BA協(xié)議數(shù)據(jù)轉(zhuǎn)發(fā)流程

通過上述步驟蝙蝠算法將蝙蝠行為捕獲到適應(yīng)度函數(shù)中。目標(biāo)是建立具有最小延遲和最大輸送比的優(yōu)化路徑。通過DLE改變Xi和Vi，在從源到目的地的初始填充期間填充機(jī)會路徑。適應(yīng)度函數(shù) (fφ) 具有歸一化的多目標(biāo)權(quán)重，傳遞比mo1和延遲mo2由式(21)獲得

fφ=Wmo1+Wmo2

(21)

其中，Wmo1=1-mo1，Wmo2=mo2。

針對最初填充的路徑計算并且排名基于權(quán)重的適應(yīng)度函數(shù)。具有最小適應(yīng)度的路徑被命名為最佳蝙蝠B(yǎng)B，如式(22)所示

最佳蝙蝠(BB)=min[fφ(pi)]
BB=P，P∈pi

(22)

其中，pi是最初填充的路徑，P是最初填充的路徑中的BA路徑。

通過基于BB隨機(jī)改變具有最佳個體來進(jìn)一步獲得LBB，如果LBB的適應(yīng)度小于BB，則隨機(jī)飛行后，將LBB的適應(yīng)度更新為BB，蝙蝠B(yǎng)B被記錄為最佳蝙蝠。最后選擇與已獲得的最佳蝙蝠相對應(yīng)的路徑進(jìn)行數(shù)據(jù)傳輸。

3 實驗結(jié)果與分析

在本節(jié)中，將提出的路由協(xié)議MOO-BA的性能與UWSNs中的現(xiàn)有路由協(xié)議DBR和EEDBR進(jìn)行比較。

3.1 仿真環(huán)境

利用MATLABR2012b建立仿真平臺?？紤]200 m×200 m×200 m區(qū)域。蝙蝠算法參數(shù)設(shè)置：fmax=1，fmin=0，α=0.9，γ=0.9。種群個數(shù)設(shè)為30、最大迭代次數(shù)Nmax為100、最大慣性系數(shù)ωmax=1.2和最小慣性系數(shù)ωmin=0.1。傳感器節(jié)點個數(shù)N在50～400變化，用不同組(即50、100、150等直到400)節(jié)點重復(fù)30次實驗。具體的仿真參數(shù)見表1。

表1 仿真參數(shù)

3.2 結(jié)果與分析

3.2.1 網(wǎng)絡(luò)生命周期

圖5展示了不同算法的網(wǎng)絡(luò)周期對比曲線，MOO-BA協(xié)議的網(wǎng)絡(luò)生命周期明顯高于EEDBR和DBR協(xié)議，在不同的節(jié)點下，比EEDBR高約500 s，比DBR高約800 s。原因是MOO-BA選擇高剩余能量和靠近接收器的深度的節(jié)點進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。同時，蝙蝠算法參考最佳路徑隨機(jī)改變最佳轉(zhuǎn)發(fā)器來動態(tài)優(yōu)化初始填充的路徑，防止同一節(jié)點因頻繁轉(zhuǎn)發(fā)數(shù)據(jù)耗盡能量，達(dá)到能耗均衡的目的，提高了網(wǎng)絡(luò)生命周期。

圖5 網(wǎng)絡(luò)生命周期對比曲線

3.2.2 端到端延遲

圖6展示了MOO-BA與DBR、EEDBR的端到端延遲變化曲線。如圖6所示，隨著時間的增加，MOO-BA的延遲明顯低于其它兩種協(xié)議，因為MOO-BA不計算保持時間，可以避免數(shù)據(jù)包碰撞。同時，蝙蝠算法通過參考最佳蝙蝠的適應(yīng)性隨機(jī)替換最佳節(jié)點來優(yōu)化建立的路徑，數(shù)據(jù)以機(jī)會路徑轉(zhuǎn)發(fā)到接收器，降低了延遲。而在DBR中，數(shù)據(jù)包從源推送到接收器時跳數(shù)增加，保持時間依次增加，這會導(dǎo)致端到端延遲增加。與DBR相比，EEDBR盡管消除了冗余，但分配優(yōu)先級的保持時間會隨著時間的增加而增加，延遲會越來越大。

圖6 端到端延遲對比曲線

3.2.3 數(shù)據(jù)包傳輸量

圖7顯示了所有協(xié)議的數(shù)據(jù)包傳輸對比曲線。在DBR中，任何路徑丟失的數(shù)據(jù)包都不能到達(dá)接收器，因為沒有恢復(fù)機(jī)制。而EEDBR的數(shù)據(jù)包可以從不同路由到達(dá)接收器，所以EEDBR數(shù)據(jù)包傳輸量要比DBR好。而MOO-BA數(shù)據(jù)包傳輸量高于其它兩種協(xié)議的原因是初始信標(biāo)通過ENS(Ni)避免了不必要的節(jié)點參與進(jìn)來，降低了無效數(shù)據(jù)包的傳輸。此外蝙蝠算法動態(tài)識別全局最佳路徑，提高了有效數(shù)據(jù)包傳輸量。

圖7 數(shù)據(jù)包傳輸對比曲線

4 結(jié)束語

本文針對水下傳感網(wǎng)絡(luò)能耗均衡的問題，提出了水下傳感網(wǎng)絡(luò)多目標(biāo)優(yōu)化機(jī)會路由MOO-BA。當(dāng)節(jié)點需要轉(zhuǎn)發(fā)數(shù)據(jù)包時，MOO-BA協(xié)議利用DLE進(jìn)行節(jié)點動態(tài)壽命估計，符合條件的節(jié)點發(fā)放DLEA令牌充當(dāng)最佳轉(zhuǎn)發(fā)器并將消息發(fā)布出去。接著由DLEC再次確認(rèn)最佳轉(zhuǎn)發(fā)器的消息。最后使用改進(jìn)的蝙蝠算法動態(tài)優(yōu)化最初填充的路由。蝙蝠算法找到最初填充的路徑的適合度并選擇最佳的傳輸路徑，同時使用其它填充路徑迭代最佳蝙蝠，直到全局收斂獲得數(shù)據(jù)傳輸最佳的路徑。仿真結(jié)果表明，MOO-BA協(xié)議能夠有效地降低端到端延遲，提高有效數(shù)據(jù)包傳輸量，延長網(wǎng)絡(luò)壽命。另外，未來的研究工作可以考慮兩點：一是研究移動水下傳感網(wǎng)絡(luò)的增強(qiáng)路由;二是研究具有適當(dāng)恢復(fù)機(jī)制的水下傳感網(wǎng)絡(luò)機(jī)制。