基于綜合評估的CAOR路由協議仿真

解 羽，譚小波，于立婷

(沈陽理工大學，遼寧 沈陽 110159)

1 引言

自主式水下潛器(Autonomous Underwater Vehicle，AUV)是一種新型智能水下機器人，具有快捷靈活、活動范圍廣、隱蔽性能的特點，可以代替水下節點移動，在軍事和民用領域都有廣泛應用[1]。機會網絡[2-3]是利用水下節點移動帶來的相遇機會實現通信的一種自組織網絡。自組織網絡[4]通常是在相對復雜且不穩定的條件下建立的，因此機會網絡的路由機制以“存儲-攜帶-轉發”的模式工作。在這種模式中，當目標節點不存在源節點的通信范圍內時，節點將存儲并攜帶數據包移動以等待合適的轉發機會。因此，確定最優的下一跳轉發節點和選擇恰當的轉發時機成為高效機會網絡路由協議設計的關鍵。傳統網絡中的依據網絡狀態信息建立和維護路由表，并按照路由表的指向轉發數據包，這一過程逐漸演變成下一跳轉發節點的單跳決策問題，因此采用何種路由度量選擇出最優下一跳轉發節點成為首要問題。

近年來，諸多學者對于水下路由協議進行大量研究。目前的機會路由協議根據路由度量不同主要分為兩類：分別是是基于冗余的路由協議和基于節點信息的路由協議。文獻[5]提出一種基于冗余的Binary Spray and Wait機會路由協議。該協議對節點產生數據包副本數設置閾值，并在spray階段采用二叉樹算法對副本數的復制逐層減半，最終當節點只存在一份副本時進入wait階段，直到目的節點收到該數據包。文獻[6]改進Prophet協議具有較高的數據包投遞率，增加了節點的接觸位置等參數，將兩跳鄰居節點之間的接觸概率計算公式進行更新優化。目前，Epidemic協議[7]與Prophet協議[8]是機會網絡中最具代表性的兩種協議。TOR協議[10]是一種新型的基于信任度評估的機會路由協議，在一定程度上能均衡節點的消耗，但是數據包的投遞率較低。

針對水下自組織網絡路由協議中AUV選擇下一跳時存在傳輸不可靠、網絡整體性能差的問題，提出一種基于AUV綜合評估的機會路由協議(Comprehensive Assessment Opportunity Routing，CAOR)，通過綜合兩種評估機制，動態調整對下一跳AUV的選取做出有效評估。將水下AUV的移動性對于路由設計的劣勢轉化為優勢，充分利用AUV移動產生的相遇機會轉發。實驗結果表明，在鏈路環境極其不穩定的水下環境中，能為可靠傳輸提供保證，通過仿真驗證協議的有效性。

2 綜合評估模型

CAOR協議以評估機制為依據確定下一跳轉發AUV，其評估機制分為兩類。一類是AUV轉發能力的評估機制，基于自身轉發產生的代價，在每完成一次轉發后，基于鏈路產生的副本數和轉發時延，對AUV的轉發能力做出評估；另一類是AUV移動性評估機制，基于水下AUV移動趨勢和活躍程度，對AUV的移動性進行評估。在選擇下一跳AUV時，對兩種評估進行動態調整，使其協同存在。AUV綜合評估模型的設計為路由協議設計的關鍵。

2.1 轉發能力評估機制

在初始轉發階段，有針對性的泛洪進行數據轉發，AUV轉發能力評估有以下兩點原則：

1)轉發時延

轉發時延tFD是衡量AUV轉發效果的指標，轉發時延越短，AUV的轉發能力也就越強。

2)副本數

網絡中副本數nc是衡量AUV轉發效果的指標，副本數越少，AUV轉發效率越高。

根據以上兩點原則，構建AUV轉發能力評估模型。計算AUV轉發能力評估值，由目的AUV以廣播的形式通知網絡中所有AUV此次轉發過程中，源AUV向目的AUV轉發能力評估值，接收到通知的AUV將更新其路由表。

定義1：(轉發能力評估函數)設F表示初始化階段，源AUVAi向目的AUVAj的轉發能力評估函數，則

(1)

式中，τ表示轉發時延反饋的調節因子，0<τ<1，并根據網絡延時需求進行設置；t表示消息產生時間；t′表示消息到達目的AUV的時間；λ0表示副本數調節因子，根據網絡內存情況進行設置；轉發能力評估值取值范圍為0

2.2 移動性能力評估機制

移動性評估機制由目的AUV進行周期性廣播，源AUV根據目的AUV各項運動參數計算移動性評估值M′ij，反映AUV的移動趨勢與活躍程度。AUV移動性評估有以下兩點原則：

1)運動趨勢

為避免盲目泛洪，待轉發區AUV在遇到轉發機會時選擇向有運動趨勢的AUV作為下一跳，能夠增大數據包成功傳輸的概率。

2)活躍程度

若待轉發區中某AUV的平均移動速度快、旋轉次數多，說明該AUV更有活力，數據包成功傳輸到目的AUV的可能性也就越大。

根據以上兩點原則，移動性評估模型構建過程如下：

(2)

式中，0<α<1表示方向影響因子；θ為待轉發區AUV的運動方向與目的AUV運動方向形成的角度；N為旋轉次數；0<β<1表示位移影響因子；x為平均位移；0<μ<1，表示速度影響因子；v為平均速度。移動性評估函數M′ij的取值范圍為0

定義3：(鼓勵函數)設δij表示目的AUV在消息生存周期TTL內成功接收到數據包，并對轉發鏈路中的每個AUV反饋一個鼓勵值

δij=σ1(ρencourage(t)+φencourage(x))

(3)

式中，σ1鼓勵函數系數；ρencourage(t)表示對成功轉發鏈路中每個AUV的延時獎勵函數；φencourage(x)表示對成功轉發鏈路中每個AUV所在的鏈路位置的鼓勵函數。

(4)

Δt為延時，Δt越小，延時鼓勵值越大，取值范圍為e-λ1<ρencourage(t)<1；TTL為消息生存周期；λ1為正常數，表示延時鼓勵調節因子，該鼓勵函數根據網絡延時性要求對調節因子的設置做出適當調整。hop(Ai)表示Ai在成功轉發鏈路中的位置，hop(Ai)越大，位置鼓勵值越高；hop(An)表示成功轉發過程中的總跳數；ε1為跳數鼓勵調節因子，取值范圍為0≤ε1<1。

定義4：(懲罰函數)設γij表示目的AUV在消息生存周期TTL內未接收到數據包，則認為轉發失敗，并對參與轉發的AUV反饋一個懲罰值，則

γij=σ2(ρpunish(t)+φpunish(x))

(5)

與設置獎勵函數同理，σ2為懲罰函數系數，ρpunish(t) 表示對參與轉發的每個AUV設置延時懲罰函數；φpunish(x)表示參與轉發過程中的每個AUV設置一個位置懲罰函數。

(6)

式中，λ2為非負數，表示延時懲罰調節因子，該懲罰函數根據網絡延時性要求對調節因子的設置做出適當調整。hop(Ai)表示AUV節點Ai在轉發失敗鏈路中的位置，hop(Ai)越小，位置懲罰值越高；hop(An)表示轉發過程中的總跳數；ε2為位置懲罰調節因子，取值范圍為0≤ε2<1。

(7)

2.3 綜合評估函數

AUV綜合評估模型是將轉發能力評估模型與移動性評估模型相結合。并針對水下自組織網絡的情況動態調整兩種評估模型所占權重，并且動態調整AUV的轉發個數，確保路由過程可靠，并且盡量少的消耗網絡資源。

Cij=(1-k)Fij+kMij

(8)

其中，0≤k≤1，表示綜合評估調節因子，該調節因子根據水下移動自組織網絡AUV的移動情況動態調整。

定義7：(轉發AUV個數)在選擇下一跳AUV時，AUV將選擇nc個AUV作為下一跳轉發AUV，則

nc=(1-b)k+b

(9)

其中，b表示待轉發區AUV中高于平均轉發能力評估值的AUV的個數。nc的取值范圍為nc=[1，b]。當k=0時，Cij=Fij，選取待轉發區中所有高于平均轉發能力評估值的AUV作為下一跳AUV，此時nc=b。而隨著水下AUV的移動性增強，k值隨之增大，nc減小。當k=1時，Cij=Mij，選取移動性評估值最高的AUV作為下一跳轉發AUV，此時nc=1。

在路由初期階段，由于沒有足夠的可以反映出AUV移動性的數據，CAOR路由采用轉發能力評估機制為主導評估機制。在路由建立中后期，AUV的移動范圍逐漸擴大，CAOR路由協議將選擇移動性評估機制為主導評估機制。兩種評估機制根據網絡中AUV的移動范圍等影響因素進行動態調整。

3 CAOR路由協議設計

3.1 基本原理

路由協議的設計從路由發現階段出發，首先需要確定源AUV的附近AUV；再進入路由轉發階段，在附近AUV中擇優作為下一跳轉發。設定恰當的時間窗口衡量是否在源AUV附近的依據，進而確定待轉發區AUV。

首先設置時間窗口，如式(10)所示

(10)

式中：R為通信半徑；Dn為AUV到其n個鄰居的距離；θ為水聲速度，約為1500m/s。

每個AUV將維護一張記錄AUV綜合評估值的路由表(Comprehensive assessment routing table，CART)，反映出節點的轉發能力與移動性。采用n×n的二維矩陣表示，如下所示

(11)

網絡中的各個AUV將周期性的根據路由表中的綜合評估值更新自身的綜合評估路由表，降低了傳統路由度量計算的復雜性，節點付出較小的存儲和計算代價維護綜合評估路由表。在數據包轉發過程中，CAOR采用沿著綜合評估值遞增的梯度轉發，若目的AUV處于源AUV的待轉發區范圍內，那么可直接轉發；否則，轉發給帶轉發區中包含自身在內的綜合評估值較高的AUV，若源AUV的綜合評估值最高，則將攜帶數據包到下一時間周期再根據綜合評估值選擇下一跳轉發AUV。

3.2 數據包采集

數據包m從源AUV轉發到目的AUV需要經過多個中間AUV協助轉發，如圖所示，由此可以將源AUV向目的AUV轉發數據包所經過的鏈路表示為：Path：A0→A1→A2→A3→A4…→Aj，如圖1所示。為了對成功轉發鏈路中AUV的綜合評估值做出更新，目的AUVAj需要采集到中間AUV(A1，A2，A3，A4…Aj-1)的轉發記錄，包括轉發時延以及中間AUV所在的鏈路位置等等。本文采用捆綁攜帶(Captive-Carry)機制[10]，在數據包的轉發過程中，將AUV的轉發記錄動態捆綁到數據包中，由數據包攜帶到目的AUV。目的AUV接收到數據包后，同時獲得參與轉發AUV的轉發記錄，從而對這些中間轉發AUV進行綜合評估值的更新。

圖1 轉發鏈路示意圖

數據包格式采用層狀模型實現捆綁攜帶機制[11]，該模型由基礎層和擴展層組成，基礎層由源節點在產生數據包時按照指定格式生成。多個擴展層由攜帶數據包的AUV在轉發給下一跳AUV時動態生成。

圖2 基于層狀模型的數據包格式

數據包在隨著轉發過程的進行會逐漸增加其擴展信息，因此對于基本消息開銷稍大，本文將合理設計數據報占用字節數。其中數據包頭包括消息ID、AUV的ID、和時間戳等基本字段，每個字段占用8個字節，數據包頭部的6個字段共占48個字節；消息內容所占字段由加密后生成的E(A0|C|AN)其自身決定；基礎層中的擴展層與轉發AUV生成的擴展層包括3個基本字段與一個轉發記錄，所以每一個擴展層占有24+rec0個字節，那么在數據包轉發過程中，由源AUV經過k轉發到目的AUV，會產生k擴展層，最終目的AUV所接收到的數據包大小LengthN(m)為：

LengthN(m)=48+E(A0|C|AN)+(k+1)(24+rec)

=72+E(A0|C|AN)+24k·rec

(12)

其中，E(A0|C|AN)表示消息內容C加密后的長度，rec表示轉發記錄長度，數據包長度主要由消息內容和擴展層信息構成。假設轉發記錄rec所占長度為10個字節，若此次轉發任務需要經過10次轉發，那么擴展層信息的總長度為：L=24k·rec=24×10×10=2400字節，約為0.78kB，完全可以滿足轉發的存儲需求。

3.3 路由表更新

每一次轉發過程中，AUV將通過計算移動性評估值并綜合每次轉發結果對應的鼓勵(懲罰)值以及AUV轉發能力的評估值，以此確定下一跳AUV。在每一次轉發結束后，目的AUV都會針對轉發結果廣播一個反饋值，以此更新評估路由表，評估路由表ART的更新過程偽代碼如下所示：

CAOR機會路由階段ART的建立：

1)初始化，設置TTL、λ、ε1、ε2參數值

2)IFAi在TTL接收消息m&&m.tar==AjTHEN

3)Ai提取發送消息時間戳m.tsi

4)Ai+1提取發送消息時間戳m.tsi+1

5)計算消息延時時間Δt=m.tsi+1-m.tsi

6)FOR對每次轉發的AUV做移動性評估獎勵

7) 式(4)計算參與轉發i個AUVAi鼓勵值

8) 式(7)更新路由表Ai對AD移動性評估值

9)endFOR

10)elseIFAj在TTL時間內未接收到消息m；THEN

11) 目的AUVAj廣播發送失敗通知

12)IF參與轉發的AUVAi接收到消息m失敗通知；THEN

13) 重復步驟3)-步驟5)

14)FOR對每次轉發的AUV做移動性評估懲罰

15) 式(6)計算參與轉發i個AUVAi懲罰值

16) 式(7)更新路由表Ai對AD的移動評估值

17) endFOR

18) endIF

19)endIF

3.4 算法實現

水下自組織網絡中，攜帶數據包m的Ai需要將該數據包發送給Aj，CAOR路由協議的轉發流程圖如下：

圖3 CAOR路由協議轉發流程圖

CAOR路由協議轉發步驟可以總結如下：

1) AUV廣播路由請求RR，在通信范圍內的所有AUV將向Ai發送路由應答RREP，執行步驟2)；

2)計算時間窗口th(n)，執行步驟3)；

3)選擇在時間窗口th(n)內接收到的路由應答請求RREP對應的AUV，作為待轉發區AUV，并生成待轉發區{Ax1，Ax2，Ax3，…，Axn}，執行步驟4)；

4)若Aj∈{Ax1，Ax2，Ax3，…，Axn}，那么直接將數據包m轉發給Aj，轉發結束。否則，執行步驟5)；

5)利用式(8)計算待轉發區中各AUV的綜合評估值Cx1，Cx2，Cx3，…，Cxn，排列優先級，執行步驟6)；

6)利用式(9)確定轉發AUV的個數nc，將數據包m發送給優先級大于nc的AUV；

7)若C優先級=nc{A1,…，An}≤Cij，源AUVAi將代替優先級為nc的AUV，攜帶數據包m移動直到下一轉發周期，返回步驟1)。

4 仿真驗證與分析

仿真環境：Intel(R)Core i7-1065G7處理器，16GB內存Window操作系統，算法運行平臺是在NS-2仿真平臺基礎上的Aqua-Sim仿真器。Aqua-Sim仿真平臺針對水聲信道，可以有效模擬水下移動自組織網絡的包沖突和聲信道的衰減。網絡仿真參數設置見表2。

表2 網絡仿真參數

網絡的仿真場景為2000*2000*2000m3的三維水下自組織網絡。利用現如今比較成熟且參與搜救馬航MH370，由美國Hydroid公司研制的型號為Bluefin-21的AUV的各項參數為依據進行仿真[12]。在設置好的三維網絡環境內，投放20個AUV，基本可以實現網絡覆蓋。此20個AUV的參數設置是完全相同的，不存在等級劃分，不同的地方在于它們會被不同的任務所驅動，移動軌跡一定不同。AUV的最大通信距離設置為700m。每個AUV的初始運動速度設置為2m/s，其中設置AUV的最小移動速度為0.2m/s，最大移動速度為2.75m/s，并向隨機方向移動。

仿真過程中，隨機指定編號從1到20的AUV在任意時刻生成一個數據包，每個數據包的大小為50B。攜帶數據包的AUV以20s為一個周期，廣播路由請求。仿真時間設置為1000s，源AUV從20s后開始執行路由過程，在960s后準備結束仿真過程，不再轉發新的數據包。

由于MAC層的設定在一定程度上影響路由效果，因此需對MAC層協議進行設置。但目前水聲MAC層沒有標準協議，因此本文借鑒了DBR協議和VBF協議中對MAC層的設置，利用了一個基于CSMA/CA的簡單MAC協議[13]。在這個MAC協議中，當某個AUV要轉發數據包時，首先對信道進行監聽，如果信道處于空閑狀態，則發送數據包。如果無法接入信道，該AUV就利用退避機制等待信道，最大的退避窗口設置為4個時隙。如果退避一段時間后監測到信道空閑，則發送數據包，如果4個時隙過后信道依舊無法接入信道，則該AUV將數據包丟棄不再發送。

為了驗證CAOR路由算法的有效性、可行性以及優越性。本文選取Epidemic、prophet、TOR三種協議與CAOR協議進行比較。從平均端到端時延、數據包投遞率、平均被轉發次數三個方面，對協議進行評價。

如圖4所示，本文提出的CAOR協議很大程度上減少網絡的暫時性擁塞，降低網絡端到端時延。隨著仿真時間的推進，惡意節點的數量增多，4種路由協議的時延呈上升趨勢。而CAOR路由協議的轉發時延控制在3s以下。在100s之前，4種算法的時延相當。在100s之后，CAOR協議的時延處于較低水平并趨于穩定，其它3種算法的時延明顯交替上升。

圖4 多種協議平均端到端時延比較

如圖5所示，本文提出CAOR協議的數據包投遞率在80%左右，有效提升了網絡整體性能。Epidemic、Prophet兩種傳統協議的數據包投遞率均值在35%左右，TOR在80%左右。這是因為Epidemic、prophet兩種傳統協議沒有反饋機制，隨著網絡環境逐漸復雜，轉發效率較低。CAOR、TOR協議需要通過大量的轉發反饋來更新轉發策略，反饋值的數量對轉發策略的更新起到積極作用，逐漸提升數據包投遞率。

圖5 多種協議數據包投遞率比較

如圖6所示，CAOR協議可以通過綜合評估模型動態調整轉發AUV個數，減少了跳數冗余，降低了轉發過程的能量消耗。CAOR協議將平均被轉發次數控制在平穩狀態，說明復雜的水下網絡環境對AUV轉發次數影響較小。Epidemic協議隨著網絡環境的復雜性增強，其平均交付率與轉發次數呈現下降趨勢，但總體保持較多的轉發次數。

圖6 多種協議數據包平均被轉發次數比較

5 總結

本文將機會網絡中節點移動帶來的相遇機會具體化，采用節點移動性與轉發能力兩個度量進行評估對決定AUV下一跳和AUV轉發個數的路由度量進行深入的研究，提出一種基于AUV綜合評估的機會路由協議。該協議的關鍵在于用動態調整所占權重的方法對AUV進行綜合評估，并對轉發結果成功與否給出反饋，通過不斷更新評估模型去選擇合適的轉發路徑和調整下一跳個數，實現水下路由轉發過程。仿真結果證明，本文克服水下復雜的網絡環境，利用AUV在三維海域中的移動趨勢實現路由轉發，達到降低網絡延時，提高可靠傳輸效果。