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

丁峰，趙民召，方勇

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

1 概述

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

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

2 算法研究

2.1 移動節(jié)點網關信息通告

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

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

圖1 海上移動信息網示意

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

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

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

圖3

表1 節(jié)點1為網關時構成的TREE表

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

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

表2 節(jié)點4為網關時構成的TREE表

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

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

2.2 移動節(jié)點網關發(fā)現(xiàn)

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

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

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

圖4

圖5 加入節(jié)點7的網絡拓撲圖

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

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

2.3 移動節(jié)點網關切換

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

3 總結

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