基于位置信息的船舶編隊自組網路由協議設計?

（武漢第二船舶設計研究所 武漢 430205）

1 引言

隨著科技的不斷發展，海上船舶裝備越來越多，船舶編隊協同越來越多。當前的船舶網絡并沒有構成一個大型的自組網，船舶之間的信息交互和共享能力有待提升［1］，面對海上的突發情況，無法保障船舶編隊的通信質量。而Ad-Hoc網絡具有無中心，獨立組網，自適應更新路由的特點，可以提高船舶之間通信的可靠性［2］。不僅如此，在編隊執行任務的過程中會發生不同隊形的切換，各節點之間的距離發生變化，通信鏈路可能會發生斷裂，保障編隊通信網絡的穩定是至關重要的［3］。

目前的Ad-Hoc網絡采取的路由策略主要有兩種:反應式和先應式，反應式是指當源節點要向目的節點發送報文時，源節點在網絡中發起路由查找過程，找到相應的路由后，才開始發送報文，代表協議有AODV［4］。該類協議通過發送時刻感知拓撲進行轉發，不需要維持路由，但是尋找路由需要一定的時間，增加了報文傳輸時延。先應式主要以OLSR［5］、DSDV［6］為主，網絡中的每個節點周期性地通過拓撲感知，維持并更新路由表。通過文獻［7］中的實驗分析可以看出，反應式路由協議分組投遞率較為高，但是因為轉發之前需要計算路由表，因此時延較高，而先應式路由協議因為每個節點都維持著路由表，因此傳輸時延較低，但是路由表存在滯后性，鏈路可能斷裂。為了控制報文的丟包率，目前有很多算法結合先應式算法與網絡的特點設計鏈路狀態評估方式。比如，在文獻［8～9］中通過對節點剩余能量的評估，優先選取剩余能量更高的節點進行轉發，保障網絡的能量均衡，從而減少了鏈路斷開。

除了上述兩種類型的協議，目前有人提出了基于強化學習的 Q-Routing［10～11］，這類協議與先應式和反應式的都不同，其路由表是逐漸收斂形成。該類算法通過定義節點之間轉發的反饋策略，不斷學習收斂路由表，通過強化學習使節點在動態變化的拓撲結構下自適應切換路由。但是對于不斷變化編隊網絡而言，該算法需要不斷學習，路由形成所需收斂時間過多，而在收斂期間，網絡的通信性能較差。

根據上述分析，為了保障編隊的實時通信，需要采取先應式的路由策略，同時為了減少鏈路的斷開，需要根據編隊的網絡特點，量化鏈路狀態，并且在此基礎上建立最優鏈路狀態拓撲感知模型。因此本文提出了一種基于位置信息的船舶編隊自組網路由協議（Location-based Routing for Ship Formation，LRSF）。首先節點之間交互位置信息，通過位置信息的變化預測鏈路狀態，定義鏈路質量，并在此基礎上建立最優鏈路拓撲感知模型，保障節點感知全網拓撲變化，最后進行路由計算，及時地切換路由，減少鏈路斷開的次數，保障編隊通信質量。

2 船舶編隊自組網概述

當前海上船舶設備數量和種類越來越多，海上任務主要是以船舶編隊的方式執行，船舶編隊頻繁地變化，難以保障船舶之間通信的可靠性。為了提升船舶編隊的通信性能，可以將編隊構建成一個移動自組網。當前的船舶編隊協同面臨一個顯著的問題——如何降低隊形變換的過程中報文的丟失率，如圖1所示。

以圖1所示的場景舉例，編隊從人字形切換到一字形編隊，初始時，B與D之間可以直接一跳傳輸進行通信，隨著編隊的變換，B與D同時繞著C進行轉動，直至呈現一字形，在此過程中，B與D的距離不斷地增大直至無法一跳直接通信，需要由C進行轉發進行轉發。然而當前存在的移動自組網協議，并不能很好地感知節點之間的距離變化，不能及時地進行路由切換，導致B與D之間的通信報文發生丟失。

圖1 人字形編隊切換至一字形編隊

為了解決上述問題，節點需要感知到節點之間相對位置信息的變化并及時切換路由。因此本文考慮通過節點之間的相對移動評估鏈路質量，使節點感知周圍鄰居的變化趨勢，同時結合節點之間的運動趨勢建立拓撲感知模型，保障節點感知全網的變化趨勢，最后結合全局拓撲進行路由計算。

3 基于位置信息的船舶編隊自組網路由協議設計

3.1 基于位置信息的鏈路狀態量化

船舶編隊在隊形變換時，節點之間的相對運動趨勢不一樣，相應的通信鏈路狀態也不一樣，為了能夠感知鏈路狀態的變化，需要結合節點之間的位置信息變化對鏈路狀態進行評估。在OLSR中并沒有考慮鏈路質量差異，該算法默認每一跳鏈路具有相同的鏈路質量，并不符合船舶編隊自組網的特點。在文獻［12］中提出了基于期望傳輸次數的鏈路質量指標，如式（1）所示。

其中R表示兩點之間的通信鏈路，LQ(R)表示R的鏈路質量，η表示R中的某一跳鏈路，ETX代表報文從源節點成功發送到目的節點的期望傳輸次數，φ(η)代表報文經過η的接收成功率，ρ(η)代表反向接收成功率，也即是相應的ACK報文的接收成功率。ETX越小，則鏈路傳輸效率越高。對于拓撲變化頻率低的移動自組網而言，ETX可以較好地反映鏈路狀態。但是船舶編隊中，節點之間的拓撲變化較為頻繁，節點之間會因為相對移動而導致鏈路突然斷開，僅僅靠ETX無法真實地反映相對移動節點之間的鏈路狀態。

為了解決這個問題，需要分析節點之間的相對位置變化和鏈路狀態的聯系。船舶編隊隊形變化導致了鏈路狀態發生變化，而節點之間的相對加速度是隊形開始變化的一個重要指標，感知節點之間的相對加速度可以預測鏈路狀態。因此本文結合節點之間的相對加速度建立鏈路質量預測鏈路狀態，鏈路質量如式（2）所示。

其中LQ(η)表示η的鏈路質量，節點i與j為一跳鏈路η的相鄰節點，ai,j是節點i，j之間的相對加速度，μ是非負經驗參數。在鏈路擁有相同的ETX情況下，節點之間的相對加速度越大，拓撲變化越劇烈，鏈路η更容易斷開，因此在路由計算中，源節點與目的節點之間選擇LQ(R)最小的鏈路作為通信鏈路。

相對加速度ai,j如式（3）所示:

其中vi,j(t2)為節點i和j在t2時刻的相對速度，vi,j(t1)為節點i和j在t1時刻的相對速度。vi,j(t2)和vi,j(t1)分別如式（4）、式（5）所示。

其中(xi(t),yi(t),zi(t))代表t時刻i節點的位置坐標，(xj(t),yj(t),zj(t))代表t時刻j節點的位置坐標。

3.2 最優鏈路狀態拓撲感知模型

當前的船舶編隊可以利用GPS或者北斗衛星獲取實時位置信息，采取上述鏈路質量評估方式，節點只需知曉鄰居節點之間的相對位置信息的變化，便可以預測鏈路狀態變化。但是對于船舶編隊移動自組網而言，節點本身的通信范圍有限，并不能感知全網的所有鏈路變化，需要結合拓撲感知模型進行全網拓撲感知，才可以選擇最小鏈路質量的鏈路進行路由。

目前OLSR采用最少中繼節點拓撲感知模型，節點在鄰居集合中選取最少的能夠覆蓋兩跳鄰居的節點作為中繼節點，構成中繼節點集合，一跳以外的節點可以通過中繼節點與該節點進行通信，為了減少控制開銷，只將節點與中繼節點集合的鏈路加入拓撲結構。因為OLSR無法感知相對移動節點之間的鏈路狀態的差異，選取的中繼節點的不一定最優，形成的拓撲結構并非最優，以圖2所示菱形拓撲場景為例，其中A節點兩端來回勻速移動，S、B、D靜止，S為源節點，D為目的節點，在OLSR算法下，D一旦選擇A加入中繼集合，將拓撲A->D發送到網絡中洪泛，S只能感知到A->D，無法感知B->D拓撲，只能生成S->A->D的路由。

圖2 菱形拓撲場景

為了保證節點盡可能按照最優鏈路進行轉發，本文建立最優鏈路狀態拓撲感知模型。在該模型中，節點優先鏈路質量最小的鄰居節點加入中繼節點集合，直至通過該集合可以覆蓋所有的兩跳鄰居節點。在圖2所示的場景下，D優先選擇B加入中繼節點集合，S感知到B->D的拓撲，生成S->B->D的路由。與OLSR的拓撲感知模型相比，最優鏈路拓撲感知模型可以保證最優的中繼節點的鏈路參與全網的路由計算，提升網絡通信的穩定性。

4 仿真實驗及結果分析

為了評估LRSF算法的性能，在QualNet上模擬船舶編隊變換的場景，比較LRSF和OLSR的網絡性能指標。實驗場景如圖3所示，開始在QualNet上布置了8個節點組成人字形編隊，隨后經過時間t1切換成一字形，經過時間t2切換成菱形，為了研究算法在不同的拓撲變化快慢場景下的性能，設定多組t1和t2進行多次實驗（因為船舶編隊從一個隊形切換到另一個隊形，拓撲的初始狀態和結束狀態一致，變化的時間越短，拓撲變化越快），本次實驗做了五組不同變換時間的對比實驗，船舶編隊切換時間參數配置如表1所示。

表1 船舶編隊切換時間（s）配置

為了評估網絡的性能，本文選取如下的網絡性能指標。

1）平均端到端時延，如式（7）所示，指的是數據包從源節點發送到目的節點接收所需的時間，反映了路由協議的有效性。

其中表示平均端到端時延，Tr代表接收到數據包的時間，Ts代表發送數據包的時間，N表示發送數據包的個數。

圖3 船舶編隊切換場景

2）分組投遞率，如式（8）所示，定義為到達目的節點的數據包的個數與源節點發送的數據包的個數的比值。投遞率反映路由的可靠性，投遞率越大，丟失分數據包越少，通信越可靠。

其中Pd指分組投遞率，Pr表示目的節點接收數據包的個數，Ps表示源節點發送的數據包的個數。

為了保證實驗結果的可靠性，隨機選取源節點-目的節點并且設置CBR數據流，進行多次實驗，取多次實驗的平均結果作為網絡性能指標的評估值。

本次實驗中，隨著編隊切換的時間增加，兩種算法的分組投遞率如圖4所示。隨著編隊變換所用時間的減少，網絡拓撲結構劇烈程度增加，OLSR和LRSF的分組投遞率都有一定程度的減少，但是LRSF的分組投遞率明顯高于OLSR，而且在80s以上的編隊變化時間范圍內，LRSF的分組投遞率都在90%左右，而OLSR只有大約70%，LRSF此時的分組投遞率遠高于OLSR。

圖4 分組投遞率比較

隨著編隊切換的時間增加，兩種算法的平均端到端時延如圖5所示。在編隊切換時間60s以上的范圍內，OLSR的平均端到端時延一直都是高于LRSF，但是隨著編隊切換時間的減少，OLSR的時延開始快速下降，而LRSF可以保持平緩，主要是LRSF能夠保持一個良好的分組投遞率，而OLSR在此期間分組投遞率下降較多，導致參與時延統計的報文數量減少，從而統計的平均端到端時延減少。在編隊切換時間60s以內的范圍，OLSR的平均端到端時延下降至LRSF以下，而LRSF此時的平均端到端時延也存在一定程度的下降，主要原因是此時的編隊拓撲結構變化較快，LRSF的分組投遞率也存在一定程度的降低。

圖5 平均端到端時延比較

綜上，在船舶編隊進行簡單的隊形變化時，本文設計的LRSF算法能夠保持一個較高的分組投遞率，并且端到端時延有所下降，相較于OLSR具有一定的優越性。

5 結語

本文針對海上船舶編隊提出了LRSF路由算法，通過實驗結果可以看出在面向動態拓撲變化的場景下，LRSF比OLSR具有更高的報文投遞率，網絡通信更為可靠，盡管犧牲了些許時延，但是并未影響到網絡通信的及時性，相較于傳統的移動自組網協議具有一定的優越性。盡管如此，本文研究的是簡單場景下船舶編隊變換，拓撲變化較為單一，一旦發生網絡拓撲劇烈或是不規則的變化，LRSF算法也不能保持良好的分組投遞率，丟包較多，無法保持良好的通信性能，因此如何應用拓撲控制減少拓撲變化，并與路由算法相結合需要后續進行深入的研究。