水下傳感網絡多目標優化機會路由

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

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

0 引 言

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

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

為進一步均衡水下傳感網絡能耗，延長網絡生命周期，本文提出一種多目標優化機會路由MOO-BA。仿真結果表明，與DBR和EEDBR相比，本協議在能量高效性、均衡性等方面均具有明顯優勢，有效地延長網絡的使用壽命。

1 系統模型

1.1 網絡架構

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

圖1 網絡模型

錨定節點固定在海洋底部，只感知并收集數據。中繼節點部署在不同的深度，不僅可以發送數據包，還可以轉發接收到的數據包?？刂浦行姆胖迷诖盎蚝┥?，并從匯聚節點接收數據包。

匯聚節點部署在水面上，配備無線電和聲學調制解調器以及無限的能量。聲學調制解調器用于水下傳感器節點接收數據分組，而無線電波用于將收集的數據轉發到岸上控制中心。

1.2 能量傳播模型

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

(1)

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

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

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

(2)

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

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

(3)

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

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

(4)

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

2 MOO-BA路由

2.1 問題描述

傳統路由通過貪婪策略選擇一跳鄰居范圍內的最佳轉發節點，很容易陷入局部最優解決方案。同時，滿足深度小于當前節點條件的節點都會參與到數據包的轉發工作中，這會導致多個節點同時轉發相同數據包，造成數據冗余和能耗。

本文針對傳統協議能耗不均衡問題，提出一種多目標優化機會路由來均衡網絡能耗。

2.2 MOO-BA中的分組結構和消息流

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

圖2 數據包格式

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

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

2.3 初始信標

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

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

2.4 動態壽命估計(DLE)

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

(5)

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

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

(6)

每個節點消耗的能量表示為

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

(7)

網絡中的所有節點能量估計DLE表示為

(8)

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

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

(9)

其中，LOAm為接受請求條目列表，LOCm為確認請求條目列表，DLEm為特定節點的動態壽命估計。

2.4.2 基于動態壽命估計的確認(DLEC)

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

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

(10)

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

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

2.5 初始路徑

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

2.6 標準蝙蝠算法

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

fi=fmin+(fmax-fmin)β

(11)

(12)

(13)

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

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

xnew=xold+δA(t)

(14)

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

xnew=xold+σδtA(t)

(15)

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

(16)

(17)

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

(18)

2.7 改進BA的路徑優化

2.7.1 引入優化因子[9]

由于經典蝙蝠算法在進行迭代優化時會陷入局部優化性，因此引入優化因子λ來對MOO-BA算法的頻率進行優化，以此來達到全局搜索和局部搜索的平衡。

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

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

(19)

(20)

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

2.7.2 算法步驟

BA優化路徑的具體過程如下：

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

步驟3 根據式(11)～式(13)，對網絡中的蝙蝠的速度和位置進行更新；

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

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

步驟6 經過一段時間運行，對新的蝙蝠群體進行評估判定,把網絡中所有的蝙蝠適應度值按照從大到小順序排列，找到最小值以及對應的位置，就是當前最優解和最優值；

步驟7 重復執行步驟2～步驟5，直到滿足設定的最優解條件或達到最大迭代次數；

步驟8 輸出全局最優值和最優解。

具體流程如圖4所示。

圖4 MOO-BA協議數據轉發流程

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

fφ=Wmo1+Wmo2

(21)

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

針對最初填充的路徑計算并且排名基于權重的適應度函數。具有最小適應度的路徑被命名為最佳蝙蝠BB，如式(22)所示

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

(22)

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

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

3 實驗結果與分析

在本節中，將提出的路由協議MOO-BA的性能與UWSNs中的現有路由協議DBR和EEDBR進行比較。

3.1 仿真環境

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

表1 仿真參數

3.2 結果與分析

3.2.1 網絡生命周期

圖5展示了不同算法的網絡周期對比曲線，MOO-BA協議的網絡生命周期明顯高于EEDBR和DBR協議，在不同的節點下，比EEDBR高約500 s，比DBR高約800 s。原因是MOO-BA選擇高剩余能量和靠近接收器的深度的節點進行數據轉發。同時，蝙蝠算法參考最佳路徑隨機改變最佳轉發器來動態優化初始填充的路徑，防止同一節點因頻繁轉發數據耗盡能量，達到能耗均衡的目的，提高了網絡生命周期。

圖5 網絡生命周期對比曲線

3.2.2 端到端延遲

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

圖6 端到端延遲對比曲線

3.2.3 數據包傳輸量

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

圖7 數據包傳輸對比曲線

4 結束語

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