一種基于地理位置信息的機會網絡路由*

陳啟航，馬大瑋，張世偉，肖玲娜，李成俊

（中國人民解放軍陸軍工程大學通信士官學校，重慶 400035）

0 引言

機會網絡是一種基于“存儲—攜帶—轉發”機制，通過中繼節點攜帶消息副本，等待與消息目的節點建立連接的機會，實現消息可靠傳輸的一種自組織網絡[1]。相較于移動自組網（Mobile Ad hoc Network，MANET）[2]，機會路由不受限于在節點間時刻維護一條穩定通信鏈路的條件，因此作為野生動物追蹤[3]、災害后通信[4]、戰場通信[5]等挑戰性環境中的可靠通信方案被廣泛研究。

路由策略問題一直是機會網絡的研究熱點，較為經典的路由策略有傳染?。‥pidemic）[6]、噴射等待（Spray and Wait，SAW）[7]等。上述方案通過多消息副本泛洪的方式來增加目的節點接收到消息的概率，但如何實現消息副本的有效分配，仍然是機會網絡領域中的一項研究熱點問題。

本文提出了一種基于地理位置信息的機會網絡消息副本分配方案（Geographic Location Message Copy Allocation，GLMCA）。本文的貢獻有：

（1）GLMCA 利用有限的地理位置信息，根據消息副本分配算法，使有限的消息副本在網絡中快速擴散，并能夠有效減少消息轉發的盲目性；

（2）提出在當節點僅能夠獲取自身路由信息時，通過周期性與事件性兩種路由維護模式與鄰居節點建立位置信息表；

（3）將GLMCA 與Epidemic 和SAW 協議進行比較，GLMCA 算法在短時間內（5 min 內）具有較高的投遞率，在節點密度稀疏的情況下能發揮較好的性能。

在第1 節中，將介紹前期進行的相關工作；第2 節將對GLMCA 的算法流程及細節設計進行描述；第3 節通過MATLAB 仿真平臺進行仿真分析；第4節進行總結。

1 相關工作

在機會路由中，消息的源節點通過生成大量的消息副本交與中繼節點攜帶，以達到提升消息可靠性的目的，如Epidemic 策略中，消息源節點將消息副本交付給每一個能夠接觸到的中繼節點。這種消息副本的分配方式在理論上來說，若不考慮緩存因素，能夠在節點密度稀疏的場景下實現極高的消息交付率；但是在現實應用場景中，這種理想化的節點緩存環境難以實現[8]。為了避免無效消息副本盲目泛洪造成的通信資源浪費，學者提出了限制消息副本生成數量的消息分配策略，其中，較為經典的就是SAW 策略。在SAW 策略中，消息副本的分配分為噴射（Spray）和等待（Wait）兩個階段。在Spray 階段中，消息源節點間將生成L份（L＞1）消息副本，并將消息副本分配給其接觸到的其他節點；當在Spray 階段中源節點未能將消息傳遞給目的節點，且所有接收到消息副本的中繼節點和源節點內僅有一個消息副本時，進入Wait 階段，此時含有消息副本的節點將不做任何操作，等待與目的節點接觸的機會進行消息傳輸[9]。

隨著衛星導航定位系統民用的廣泛應用，用戶能夠通過手持終端（智能手機、智能手表、平板電腦等）或車載終端（車載導航系統）獲取自身甚至其他節點的位置信息，在此基礎上，基于地理位置信息輔助的移動自組網路由策略相繼被提出，如位置輔助路由（Location Aided Routing，LAR）[10]、貪婪周邊無狀態路由（Greedy Perimeter Stateless Routing，GPSR）[11]等。許多學者嘗試在機會網絡的消息副本分配策略上引入地理位置信息，實現消息副本能夠盡可能分配到更有機會與目的節點接觸的高效節點，提升消息交付的成功率。在文獻[12]中，作者將GPSR 策略與機會路由相融合，當消息在傳輸過程中遭遇路由空洞[13]時，作者認為按傳統GPSR 通過“右手法則”重新選擇的中繼節點并不是最優的中繼節點；因此在面臨路由空洞時，距離目的節點直線距離最近的節點將保存消息等待與目的節點建立最短連接的機會。相較于傳統GPSR 和機會路由策略，上述方案的提出雖然進行了一定程度的優化，但在挑戰性環境下，消息源節點極有可能無法獲得目的節點的地理位置信息或出現目的節點地理位置信息過期失效的情況，這種單消息副本轉發的模式的性能會受到極大的限制。文獻[14]提出了一種基于地理位置信息輔助的多副本SAW 策略，該策略在SAW 的Wait 階段中加入消息轉發機制，處于Wait 階段的中繼節點將與接觸到的其他節點交換比較位置信息，中繼節點將消息副本轉發給不攜帶副本的高效節點，形成新的中繼節點。這種副本轉發策略使得消息副本不斷向高效轉發節點靠攏，避免了副本盲目分配至孤僻節點的問題，但也給高效節點增加了更多的消息負載。在文獻[15]中，作者在源節點副本分配策略上參考I.CEpidemic[16]策略中根據鄰居節點選擇最大張角的知識，通過位置信息選擇張角最大的兩個鄰居節點作為分配副本的中繼節點。

基于上述研究，本文提出了一種基于地理位置信息的機會網絡消息副本分配策略（GLMCA）。該策略的特點有：

（1）鄰居節點間互相交換自身位置信息，源節點產生的消息副本能夠按最短距離擴散至指定位置；

（2）限制源節點生成消息副本的數量；

（3）根據節點位置信息，按劃分角度方向分配副本。

2 GLMCA 模型設計

假設在間歇性連接網絡[17]中各節點能夠獲取到自身位置信息，當不考慮節點能量消耗及緩存資源時，GLMCA 策略將進行下述操作。

GLMCA 策略分為3 個階段：鄰接節點信息維護階段、消息副本分配階段和虛擬源節點消息轉發階段。各階段間關系如圖1 所示。

圖1 GLMCA 階段關系

2.1 鄰接節點信息維護階段

在鄰接節點信息維護階段中，網絡中各節點與鄰居節點交換控制信息記為控制消息（Control Message，CM），并根據接收到的控制信息在節點自身建立并維護一個鄰接節點位置信息表。

如表1 所示，鄰接節點位置信息表內包含有鄰接節點的標識ID、X和Y坐標以及一個位置信息剩余保留時間記為TTL_g。當表內位置信息存儲的時間到達TTL_g時，該條位置信息將被丟棄以減少冗余信息。

表1 鄰接節點位置信息

鄰接節點信息維護階段的觸發方式分為周期性觸發和事件性觸發兩種模式，在不同觸發模式下，具有不同的發送控制信息的節點與控制信息字段。

（1）周期性觸發：該模式下，相鄰的一跳節點間將交換控制信息CM_p，CM_p字段如圖2所示。

圖2 CM_ p 字段

接收到CM_p的節點根據字段內容更新維護鄰接節點位置信息表。

與自組網協議中的路由收斂機制不同的是，CM_p屬于彈性信息，即不需要對位置信息表進行實時的維護，不同節點可以根據自身能耗狀態合理設置CM_p的發送周期。

（2）事件性觸發：該模式下，虛擬源節點向相鄰的一跳節點發送控制信息CM_i，CM_i字段如圖3所示。

圖3 CM_i 字段

CM_i信息中加入了一個征詢信息，使節點在接收到CM_i時，將回復自身位置信息表信息。

2.2 消息副本分配階段

當消息源節點產生消息時，源節點將在自身鄰接節點位置信息表內檢查是否存在目的節點的位置信息，若存在則將消息直接轉發給目的節點，否則將生成N個消息副本，并按算法分配的方向矢量選擇鄰接節點作為轉發的中繼節點，如圖4 所示。

圖4 源節點副本分配流程

在這里本文加入了方向矢量的概念，如圖5所示，方向矢量的作用是作為選擇中繼節點的一個指針，消息副本只會轉發給方向矢量范圍內的中繼節點。

如圖5 所示，消息源節點S 一跳通信范圍內有A、B、C、D，4 個節點，當源節點需要轉發消息副本時，則根據方向矢量V的方向，選擇節點A 作為轉發消息的中繼節點。

方向矢量分配算法：假設消息節點位置坐標為(X0,Y0)，其周圍n個鄰接節點的坐標集為{(X1,Y1),(X2,Y2),…,(Xn,Yn)}，并根據式（1）得出矢量方向集合{V1,V2,…,Vn}，則有：

式中：Vi為第i個鄰接節點的矢量方向；(Xi,Yi)為第i個鄰接節點的位置坐標，i∈[1,n]。

記消息源節點生成N個副本，建立參考集合求得矢量方向距離集合{|V|}，取最大值|Vmax|對應的方向為參考方向，若存在多個最大值，則在其中隨機選取一個為參考方向。根據式（2）得出矢量方向與參考方向夾角集合{?1,?2,…,?n}，n為一跳內鄰居節點數量。

式中：i∈[1,n]。

選擇與參考集合中最為接近且差值在區間[-θ,θ]內的夾角的方向矢量為消息副本的轉發方向。

如圖6 所示，當消息源節點產生4個消息副本時，參考方向為一跳范圍內最遠距離節點的方向（圖中為節點A 的方向），而后根據分配算法，將副本分配給節點A、B、C、E 作為中繼節點。

圖6 N=4 時算法演示

當中繼節點接收到副本時，將進行以下判斷：

（1）中繼節點一跳內鄰居節點是否存在消息目的節點；

（2）消息傳遞跳數是否達到傳遞閾值；

（3）矢量方向的差值區間內是否存在鄰居節點。

當鄰居節點內存在目的節點時，由中繼節點將消息傳輸給目的節點，否則需要進行下兩步判斷。在這里提出了一個傳遞閾值的概念，當節點密度大時，隨著跳數的增加，副本轉發方向的誤差將無限增大，因此需要設計一個傳遞閾值。本文假設閾值為3 跳，當副本轉發超過3 跳且仍未交付給目的節點時，消息副本的第3 跳中繼節點則轉為虛擬源節點，進入虛擬源節點模式；若副本轉發次數未超過傳遞閾值，中繼節點需要判斷在分配的方向差值區間內是否存在下一跳節點，若存在則向夾角最接近分配方向的節點轉發消息，否則中繼節點則轉為虛擬源節點，進入虛擬源節點模式，流程如圖7 所示。

圖7 中繼節點副本分配流程

2.3 虛擬源節點消息轉發階段

當進入虛擬源節點消息轉發階段時，虛擬源節點每當遇到新的鄰居節點時，將按鄰接節點信息維護階段中事件性觸發鄰接節點維護模式。虛擬源節點將檢查其鄰居節點是否為消息的目的節點，若為目的節點則進行消息的發送，若不是目的節點，則檢查其位置信息表內是否存在目的節點的位置信息，若存在，則將消息轉發給鄰居節點實現消息的傳遞，否則繼續等待新的事件觸發或者消息到達生存時間后被節點丟棄。

3 仿真分析

本文在MATLAB 平臺上實現了GLMCA 算法的仿真，相較于其他仿真平臺如NS、ONE 等，MATLAB 通過逐幀切換的方式能夠更好地模擬網絡中節點間拓撲變化，其仿真結果在相對意義上與其他仿真平臺相同。仿真參數如表2 所示。

表2 仿真參數

當不考慮節點緩存和節點能量時，假設SAW和GLMCA 消息產生副本數為4，GLMCA 傳遞閾值為3，在不同節點密度下，對Epidemic、SAW 和GLMCA 3 種策略的消息投遞率、平均時延和網絡開銷[18]進行仿真分析。

3.1 消息投遞率

消息投遞率是成功投遞消息數和產生消息數的比值。消息投遞率的仿真結果如圖8 所示。

圖8 消息投遞率對比

如圖8 所示，在短時間（5 min）內，機會路由消息投遞率普遍不高，這是由于短時間內中繼節點移動性受限，無法將消息迅速攜帶或者擴散，其中GLMCA 和SAW 算法在節點數量較低時相較于Epidemic 算法具有較好的消息投遞率表現，尤其是當節點數量小于40 個時，CLMCA 算法的投遞率比SAW 算法高了60%，比Epidemic 算法高了100%。當網絡中節點數量在（0,180）區間內時，GLMCA算法的投遞率一直高于其他兩種算法，當節點數高于200 時，Epidemic 算法憑借消息副本無限制泛洪的優勢，其消息投遞率突變上升，此時GLMCA 算法投遞率仍高于SAW 算法。

3.2 平均時延

平均時延是消息成功交付所需要時間的平均值。平均時延的仿真結果如圖9 所示。

如圖9 所示，由于節點移動性的限制，絕大部分消息的交付時間在1 s 左右，即源節點直接交付。這是由于在有限的時間內，消息的副本無法迅速擴散。其中，表現最為突出的算法為SAW 算法，然而由于該算法限制了消息副本的數量，使得其無法像Epidemic 算法那樣隨著節點密度的增高將消息副本快速在網絡中擴散，當節點移動性低時，其副本轉發模式的盲目性使得中繼節點無法將副本快速攜帶“遠離”源節點。而GLMCA 算法在消息副本轉發的設計上，使得消息副本在中繼節點中仍能夠進行多次轉發，并根據位置信息避免了消息副本轉發的盲目性。

圖9 平均時延對比

3.3 網絡開銷

網絡開銷是冗余消息副本數與成功投遞消息數的比值，其仿真結果如圖10 所示。

圖10 網絡開銷對比

如圖10 所示，當節點數較低時，3 種算法的網絡開銷相差不大。隨著節點數量的增加，Epidemic算法開銷逐漸上升，當節點數量為240 時，其開銷是GLMCA 算法的1.82 倍。

由于限制了網絡中消息副本泛洪的數量，GLMCA 算法和SAW 算法的網絡開銷較為穩定，并且由于GLMCA 算法的中繼節點依舊能夠進行有限次的消息副本轉發，因此相較于SAW 算法，在短時間內將消息副本擴散的概率更大，而SAW 算法由于轉發的盲目性以及中繼節點無法轉發消息副本的局限性，使得其平均開銷低于GLMCA算法4.55%。

4 結語

本文提出了一種基于地理位置信息的機會網絡消息副本分配策略（GLMCA），并按鄰接信息維護模式、消息副本分配模式和虛擬源節點模式3 種模式對GLMCA 策略進行設計。根據設計，GLMCA 策略能夠利用節點自身位置信息，將產生消息的副本按設計的消息副本分配算法短時間內擴散至網絡中生成的虛擬源節點，虛擬源節點根據拓撲變化主動檢測鄰接節點位置信息，進一步擴大了對目的節點的檢測范圍。通過與經典機會路由策略Epidemic 和SAW 的仿真對比發現，GLMCA 算法在短時間內具有較好的消息投遞率，當節點密度稀疏時，能夠有效利用中繼節點轉發來提升通信可靠性，并在節點密度提升時，能夠保持較低的網絡開銷。