海上移動信息網路由算法技術研究

丁峰，趙民召，方勇

（北京航天益來電子科技有限公司，北京，100074）

1 概述

海上船隊采用移動網絡組織形式，具有無中心、自組織，自動路由，強健壯性等特點。其除了滿足內部成員間進行移動信息交互外還要與地面網絡互聯，實現海上與岸上信息平臺間的信息交互，見圖1。

為了讓海上移動信息網中的節點能夠實時訪問地面網絡，須解決如下問題：當某個移動節點通過衛星鏈路與地面網絡相連時，它如何向網絡內的所有其他節點通告它的存在；當一個新的節點加入海上移動信息網絡中，或者一個需要訪問地面網絡的節點缺乏有效的移動節點網關信息時，如何及時了解到當前網絡中有哪些移動節點可以充當網關。

2 算法研究

2.1 移動節點網關信息通告

移動節點網關信息通告算法的步驟描述如下：

（1）移動節點網關節點向所有鄰近節點發出通告消息AdMsg；（2）收到通告消息AdMsg的鄰近節點MNode（Mobile Node）向發送者（即MNode的F節點）立即回一條AdAckMsg（確認消息），同時將其F節點設為缺省網關DGW（default GW）。若收到多個AdMsg，MNODE則按先后順序，分別設定其第一，第二......第X DGW等等。為了減少海上移動信息網絡中的網關信息通過開銷，限定每個節點最多允許擁有DGW數量,假定設為SX。如果一個海上移動信息網絡節點本身已經通過衛星鏈路與地面信息網絡相連，則將其作為首選缺省。（3）MNODE向周圍節點發AdMsg，該消息包含有來源信息，告訴鄰近節點消息本身是源自GW的，因而GW節點為地面信息網絡接入網關，MNODE則為中間節點；若MNODE接收到或者轉發過某一AdMsg，不再接收源于同一個移動節點網關的通告消息AdMsg；如果MNODE已經接收了源自不同移動節點網關的AdMsg達到限制數量，則會拋棄以后所有來自其它移動節點網關的AdMsg。（4）重復步驟2和3；（5）一個節點在規定時間內收不到AdAckMsg，則向其F節點（DGW）發送RtMsg；此消息中包含了節點所有路由信息；（6）收到路由消息的節點必須修改自身的路由表，并向其F節點發出RtMsg；（7）重復以上步驟5和步驟6，直到GW為止。

圖1 海上移動信息網示意

實例說明：以網絡中某節點為網關時路由TREE表的產生過程。假設海上移動信息網絡由6個節點組成，網絡拓撲結構如圖2所示。

圖3中節點1作為移動節點網關構成一條路徑的生成過程，該圖了省去網關通告消息的確認信息和其它路徑的AdMsg消息。表1給出了節點1為網關時構成的TREE表。

圖2 海上移動信息網絡邏輯圖

圖3

表1 節點1為網關時構成的TREE表

圖4描述了節點4作為移動節點網關構成的TREE，圖中略去了網關通告消息的確認信息以及其它路徑的AdMsg消息。表2給出了節點4為網關時構成的TREE表。

表3為全部路由信息，假設節點1先廣播AdMsg。

表2 節點4為網關時構成的TREE表

表3 節點1和節點4同時為網關時構成的TREE表

通過此算法，相對于移動節點網關而言，海上移動信息網絡中的所有節點就是一個TREE。在這個TREE中的每一個節點都清楚它所有子孫節點的信息（只有LEAF節點除外），同時清楚F節點（DGW）信息（ROOT節點除外）。LEAF節點僅知道它的F節點的信息，ROOT節點還知道TREE中所有其它節點的信息。

2.2 移動節點網關發現

一個新加入的海上移動節點MNODE加入網絡之后，或包含有無效的移動節點網關信息的節點MNODE想通過此移動節點訪問地面網絡時，會執行此發現算法，以可以發現當前可用移動節點網關信息和相應的路由信息。

相關步驟如下∶（1）節點先向鄰近節點發出RqstMsg，查詢可以使用的移動節點接入網關。（2）若鄰近節點緩存的移動節點網關信息有效，即將有效信息通過肯定RplMsg發送給MNODE節點。MNODE將最早收到的確認RplMsg的發送者fMNODE作為其F節點；并向fMNODE發送AckMsg，然后，fMNODE將MNODE作為其孩子節點，并將MNODE通報給其F節點あMNODE，使MNODE成為あMNODE的孫節點，向上遞歸，直到移動節點。（3）若鄰近節點緩存的移動節點網關信息無效，向MNODE節點發送否定的RplMsg。若MNODE沒有收到肯定的RplMsg，向最早收到的否定RplMsg的發送者fMNODE發送一個否定確認消息AckMsg。沒有收到否定AckMsg的MNODE的鄰近節點不再有任何動作；收到否定AckMsg的鄰近節點fMNODE向其F節點發送RqstMsg，請求可用的移動節點網關的信息，若fMNODE收到肯定的RplMsg，則轉發給MNODE，否則跳到步驟4。（4）按照步驟2、3順序向上遞歸，直到某個節點搞清楚有效移動節點網關消息。若RqstMsg一直發送到移動節點網關，則移動節點網關將進行一次移動節點網關AdMsg，使整個網絡中所有節點獲取最新移動節點網關消息。

以上節的例子說明網絡中新加入一個節點時的路由更新情況。新加入節點7后的網絡拓撲結構如圖5所示。

圖4

圖5 加入節點7的網絡拓撲圖

節點7加入網絡后的路由樹表見表4。

表4 節點7加入后節點1和節點4同時為網關時構成的TREE表

2.3 移動節點網關切換

當一個移動節點網關進遠程鏈路切換時，先發送網關AdMsg，啟動網關通告算法；然后通過外地agent向其本地agent注冊，或者直接請求本地agent注銷其以前的綁定，以提高了移動節點網關的切換速度。若移動節點網關脫離當前鏈路，并且會脫離一段時間，即該移動節點確定一定時間中不能再作為網關，此移動節點需要立即向整個網絡廣播一個不可用消息（Invalid Msg ），該消息被廣播給網絡中所有節點，以便相關網關自身調整接入網關信息。

3 總結

本文給出了一種海上移動信息網與地面網絡互聯互通的解決方法，著重研究出網關通告、網關發現、網關切換以及路由選擇等算法，使得網內任意節點均可快速找到一條到達移動網關節點的可靠路由，從而通過網關節點的轉發以及衛星鏈路的傳輸實現與地面網絡間的通信。