海上移动信息网路由算法技术研究

丁峰，赵民召，方勇

（北京航天益来电子科技有限公司，北京，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 总结

本文给出了一种海上移动信息网与地面网络互联互通的解决方法，着重研究出网关通告、网关发现、网关切换以及路由选择等算法，使得网内任意节点均可快速找到一条到达移动网关节点的可靠路由，从而通过网关节点的转发以及卫星链路的传输实现与地面网络间的通信。