海上移動(dòng)信息網(wǎng)路由算法技術(shù)研究

丁峰，趙民召，方勇

（北京航天益來(lái)電子科技有限公司，北京，100074）

1 概述

海上船隊(duì)采用移動(dòng)網(wǎng)絡(luò)組織形式，具有無(wú)中心、自組織，自動(dòng)路由，強(qiáng)健壯性等特點(diǎn)。其除了滿足內(nèi)部成員間進(jìn)行移動(dòng)信息交互外還要與地面網(wǎng)絡(luò)互聯(lián)，實(shí)現(xiàn)海上與岸上信息平臺(tái)間的信息交互，見(jiàn)圖1。

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

2 算法研究

2.1 移動(dòng)節(jié)點(diǎn)網(wǎng)關(guān)信息通告

移動(dòng)節(jié)點(diǎn)網(wǎng)關(guān)信息通告算法的步驟描述如下：

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

圖1 海上移動(dòng)信息網(wǎng)示意

實(shí)例說(shuō)明：以網(wǎng)絡(luò)中某節(jié)點(diǎn)為網(wǎng)關(guān)時(shí)路由TREE表的產(chǎn)生過(guò)程。假設(shè)海上移動(dòng)信息網(wǎng)絡(luò)由6個(gè)節(jié)點(diǎn)組成，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2所示。

圖3中節(jié)點(diǎn)1作為移動(dòng)節(jié)點(diǎn)網(wǎng)關(guān)構(gòu)成一條路徑的生成過(guò)程，該圖了省去網(wǎng)關(guān)通告消息的確認(rèn)信息和其它路徑的AdMsg消息。表1給出了節(jié)點(diǎn)1為網(wǎng)關(guān)時(shí)構(gòu)成的TREE表。

圖2 海上移動(dòng)信息網(wǎng)絡(luò)邏輯圖

圖3

表1 節(jié)點(diǎn)1為網(wǎng)關(guān)時(shí)構(gòu)成的TREE表

圖4描述了節(jié)點(diǎn)4作為移動(dòng)節(jié)點(diǎn)網(wǎng)關(guān)構(gòu)成的TREE，圖中略去了網(wǎng)關(guān)通告消息的確認(rèn)信息以及其它路徑的AdMsg消息。表2給出了節(jié)點(diǎn)4為網(wǎng)關(guān)時(shí)構(gòu)成的TREE表。

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

表2 節(jié)點(diǎn)4為網(wǎng)關(guān)時(shí)構(gòu)成的TREE表

表3 節(jié)點(diǎn)1和節(jié)點(diǎn)4同時(shí)為網(wǎng)關(guān)時(shí)構(gòu)成的TREE表

通過(guò)此算法，相對(duì)于移動(dòng)節(jié)點(diǎn)網(wǎng)關(guān)而言，海上移動(dòng)信息網(wǎng)絡(luò)中的所有節(jié)點(diǎn)就是一個(gè)TREE。在這個(gè)TREE中的每一個(gè)節(jié)點(diǎn)都清楚它所有子孫節(jié)點(diǎn)的信息（只有LEAF節(jié)點(diǎn)除外），同時(shí)清楚F節(jié)點(diǎn)（DGW）信息（ROOT節(jié)點(diǎn)除外）。LEAF節(jié)點(diǎn)僅知道它的F節(jié)點(diǎn)的信息，ROOT節(jié)點(diǎn)還知道TREE中所有其它節(jié)點(diǎn)的信息。

2.2 移動(dòng)節(jié)點(diǎn)網(wǎng)關(guān)發(fā)現(xiàn)

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

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

以上節(jié)的例子說(shuō)明網(wǎng)絡(luò)中新加入一個(gè)節(jié)點(diǎn)時(shí)的路由更新情況。新加入節(jié)點(diǎn)7后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖5所示。

圖4

圖5 加入節(jié)點(diǎn)7的網(wǎng)絡(luò)拓?fù)鋱D

節(jié)點(diǎn)7加入網(wǎng)絡(luò)后的路由樹(shù)表見(jiàn)表4。

表4 節(jié)點(diǎn)7加入后節(jié)點(diǎn)1和節(jié)點(diǎn)4同時(shí)為網(wǎng)關(guān)時(shí)構(gòu)成的TREE表

2.3 移動(dòng)節(jié)點(diǎn)網(wǎng)關(guān)切換

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

3 總結(jié)

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