基于网关信息素的MANET接入Internet自适应网关发现算法

摘要

本发明涉及一种基于网关信息素的MANET接入Internet自适应网关发现算法。步骤为：第一，采用了链路稳定性评估方法，用于选择稳定链路和预测链路是否断开；第二，通过网关信息素来标记节点是否具有转发GWADV信息的资质，GWADV信息通过由网关、具有转发资格的节点和源节点组成的活跃区域内转发至源节点；第三，周期性的调整节点的转发资质，调整活跃区域，使活跃区域自动适应MANET的拓扑变化，从而可以将GWADV信息转发至源节点。本发明参与转发的节点少，建立的路由稳定，控制开销小，网络的整体性能高，适应性强，不会增加额外的硬件需求及能耗。

说明书

技术领域

本发明属于移动自组织网络（MANET：Mobile Ad Hoc Networks）领域，具体为一种基于 网关信息素的MANET接入Internet自适应网关发现算法。

背景技术

移动自组织网络（MANET：Mobile Ad Hoc Networks）是一组具有路由和转发功能的移动 节点组成的网络，它可以在没有任何通信基础设施支持的环境中进行通信。两个节点之间可 以通过多跳的方式实现通信，中间节点即作为终端节点，又具有路由转发功能。

移动自组网接入Internet可以扩展自组网的应用，也是下一代4G网络将所有已存在的网 络无缝连接起来的一个目标。因为MANET中的地址结构与IP地址结构不兼容，因此，二者 不能直接互联。现有方法主要是利用网关作为MANET与Internet之间的桥梁，实现协议的转 换功能。因而MANET移动节点与Internet通讯的第一步就是发现网关，建立移动节点与网关 的路径。目前常见的网关发现算法可以分为被动方案(reactive scheme)，主动方案（proactive  scheme），混合方案（hybrid scheme）。被动方案是以按需的方式建立网关到移动节点之间的 路由：当移动节点需要与Internet中的固定节点（Fixed node）通信的时候在MANET中广播 网关请求（GWSOL：Gateway Solicitation）信息，MANET网络中的每个节点都会收到这些用于 发现网关并建立路由的控制信息。主动方案由网关周期性的广播网关通告(GWADV：Gateway  advertisement)信息到整个MANET，收到GWADV信息的节点据此报文建立到网关的路由。在 被动方案中，网关周期性的广播GWADV信息，因而MANET中的每个节点都会周期性的收到 网关发出的GWADV信息。混合方案是以网关为中心，以跳数TTL为半径，指定一个主动区域， 处在主动区域内的移动节点采用主动网关方案，而在主动区域之外的移动节点，采用被动网 关发现。

现有网关发现算法的缺点是：

1.不论是采用哪种网关发现方式，都是以在MANET中广播大量信息包（GWADV或GWSOL） 作为网关发现算法的基础，因而在网关发现过程中会产生大量的控制开销。这些控制开销会 影响MANET的性能。算法中产生的控制包越多，对网络的性能影响越大。

2.混合网关发现算法虽然可以一定程度上减少控制开销，但是一旦TTL参数确定，则在 主动区域内的所有节点还是会周期性的产生大量控制包。对大部分没有Internet通讯需求的 移动节点而言，这些控制包是没有必要接收和转发的。

3.MANET因为节点的移动性，网络拓扑是不稳定的。因而建立的网关和移动节点之间的 路由也具有不稳定性。如果通信过程中路由失效，重建路由的开销是非常大的，比如产生大 量的控制开销，引起信息传输的延迟。现在的网关发现算法在建立到网关的路由时没有考虑 选择稳定的路由。

发明内容

为了解决现有网关发现算法中存在的上述问题，本发明提供一种基于网关信息素 (Gateway pheromone)的MANET接入Internet自适应网关发现算法，它将移动节点分成具有 转发GWADV信息资格和不具有转发资格两类移动节点，并采用网关信息素标记具有转发资 格的移动节点。GWADV信息只通过少量具有转发资格的移动节点转发至源节点，通过减少参 与转发的节点个数减少控制开销；此外，该算法通过评估链路的稳定状况，在可选范围内优 先选择稳定链路建立路由，减少在数据传输过程中因路由失效重建而引起的额外控制开销和 传输延迟。该算法具有开销低，数据传输延迟低，自动适应网络拓扑变化等优点。

为实现上述目的，本发明采用如下技术方案：

一种基于网关信息素的MANET接入Internet自适应网关发现算法，

第一步，评估移动节点所处环境的各条链路的稳定性状况，只允许控制信息在稳定链路 上转发，并预测链路是否断开；节点间定时发送Hello消息来维持邻居关系，也会发送其它的 信息，如数据包、控制包等。当检测到邻居节点发送的数据包时，检测节点会为每一个邻居 节点维持一个接受信号强度（功率）的列表。通过对信号强度采样来评估节点间链路的稳定 性。

第二步，通过网关信息素标记允许转发控制信息的移动节点，GWADV信息通过具有转发 资格的节点转发至源节点，这些转发节点、网关节点及源节点组成一个子网区域作为活跃区 域（Active region）；网关信息素用于标记节点是否具有转发资格，进而用于定义活跃区域的 范围。MANET的移动特性会导致活跃区域变化，通过挥发完网关信息素使某些节点失去转发 资格，进而排除出活跃区域，同时让某些节点具有网关信息素从而具有转发资格，周期性的 调整维护活跃区域，使其在MANET拓扑不断变化的情况下能够将GWADV信息转发至源节点。

第三步，定期调整维护活跃区域确保控制信息只通过活跃区域转发至源节点，并建立网 关与源节点之间的路由，使活跃区域自动适应MANET的拓扑变化，从而将GWADV信息转发 至源节点。本算法主要采用主动网关发现方式，由网关周期性的产生GWADV信息，并通过 活跃区域中的节点转发至源节点，并在可选范围内选择稳定链路建立源节点与网关之间的路 由。当活跃区域失效，无法将GWADV信息转发至源节点或者源节点需要与Internet通信却没 有到网关的有效路由时，采用被动网关发现方式。

第一步中，所述链路稳定性状况评估方式为：

根据Friis自由空间传播模型，接受功率与发送功率的比值与传输距离r的平方成反比， 即MANET中节点发送功率记为P_T，α、β用于控制节点之间的距离及功率变化率 对链路稳定评估值的影响，为了能够正常收到数据，P_min为节点的最小接收功率，节点u对节 点v接收功率采样最近的两次记为和变化趋势为d_Δ为正值，表 示节点u,v距离越来越近，链路趋向稳定；为负值，表示链路向不稳定趋势变化，Δt为采 样时间间隔。S(u,v)取值范围介于0和1之间，取值越大，说明链路越稳定。

第二步中，网关信息素用来标志一个移动节点是否具有转发控制信息的资格，进而定义 活跃区域。每个节点维持一个网关信息素表，用于记录其每条链路的网关信息素信息，节点 u的链路L(u,v)上的网关信息素记为Φ_uv。当链路被选中作为源节点到网关路由的一部分时， 该链路上会被放置一定数量的网关信息素。如果某个移动节点作为端点的多条链路中，有至 少一条链路拥有网关信息素，那么认定这个节点具有转发控制信息的资格，否则即使收到控 制信息，也不允许转发。如果GWADV信息通过具备转发资格的节点最终转发到了源节点，那 么所有参与转发的节点，网关节点及源节点组成一个子网区域，称为活跃区域；若子网区域 拥有若干具备转发资格的节点，但不包含网关节点或源节点，不能称为活跃区域。本算法中， 网关发出的控制信息只通过活跃区域发送到源节点。

所述活跃区域随MANET的移动特性而变化，此时通过挥发完网关信息素使某些节点失去 转发资格，进而排除出活跃区域，同时让某些节点具有网关信息素从而具有转发资格，周期 性的调整维护活跃区域，使其在MANET拓扑不断变化的情况下能够将GWADV信息转发至源 节点。

因为节点的移动性，MANET的拓扑是不稳定的，链路可能会逐渐不稳定甚至断开，节点 也可能会因其移动而失去转发资格。通过周期性的挥发链路上的网关信息素来调整节点的转 发资格，进而调整维护活跃区域。链路L(u,v)的网关信息素按照如下公式周期性的挥发：

${\Phi }_{\mathrm{uv}}=\left(\begin{array}{cc}{\Phi }_{\mathrm{uv}}-{\mathrm{\lambda \Phi }}_{\Delta }(1-S(u,v)),& {\Phi }_{\mathrm{uv}}\ge {\mathrm{\lambda \Phi }}_{\Delta }(1-S(u,v)),\\ 0,& {\Phi }_{\mathrm{uv}}<{\mathrm{\lambda \Phi }}_{\Delta }(1-S(u,v)),\end{array}\right)$

λ为挥发系数，λ值越大，挥发越快，可根据网络状况设定，节点移动越快，节点密度越小， 挥发越快；S(u,v)代表链路L(u,v)的稳定性评估值，链路越稳定则挥发的越慢；Φ_Δ为一常量,表 示链路上网关信息素的初始值。当一个节点的所有链路上的网关信息素都已经挥发完毕，则 这个节点将失去转发控制信息的资格。如果一条链路因为节点的移动性而断开，链路上的网 关信息素将被清零。

调整维护：

节点的移动会导致某条标志有网关信息素的链路断开，从而导致活跃区域被分成两个部 分，网关发出的控制信息无法转发至源节点。源节点无法通过获取网关通告信息建立到网关 的路由。因此，为确保在MANET拓扑不断变化的情况下能够通过活跃区域将GWADV信息转 发至源节点，需要周期性的调整维护以动态适应MANET拓扑的变化。通过借助于所述第一步 中的链路稳定性评估方法，对拥有网关信息素的链路进行稳定性预测，当预测到链路将会在 下一个网关公告周期中断开时，通过选择替代链路确保活跃区域不会断开。节点只预测拥有 网关信息素的链路是否会断开。

某个节点u预测其链路L(u,v)将是否要断开，检查下面两个条件：

a.链路的稳定性评估值S(u,v)比预先设定的阈值S_Disconnect小；

b.接收信号的变化趋势d_Δ小于0。

如果条件a和b都满足，则可以预测链路L(u,v)将要断开。一旦预测某条链路将要断开， 则可能使节点失去转发资格进而导致活跃区域变小或者可能会导致活动区域失效，因而需要 对活跃区域进行调整修复。节点u将选择一条比较稳定的且没有网关信息素的链路L(u,v)，并 分配一定数量的网关信息素，从而使该条链路的另一端的节点w具备转发网关控制信息的资 格。节点u选择链路L(u,w)时需满足下列条件：

a.链路L(u,w)之上没有网关信息素；

b.对于节点w的两条链路L(u,w)和L(w,v)的稳定性评估值S(u,w)和S(w,v)都要大于阈值 S_Replace。

如果有多条链路满足这两个条件，只需要随机选择其中一个即可。选择链路L(u,w)作为 替换链路后，将链路L(u,v)上的所有网关信息素转到上L(u,w)上。L(u,w)拥有了网关信息素， 则节点w具备了转发资格，节点w的加入可确保活跃区域不会因链路L(u,v)的断开而失效或 导致活跃区域过小。链路断开预测及活跃子网的维护修复需要周期性的进行，从而使活跃子 网自动适应网络拓扑的动态变化。在活跃子网的调整维护过程中，不断淘汰即将断开的链路， 添加稳定的链路，因而，在活跃区域中是可以建立到网关的稳定路由的。

所述网关与源节点之间的路由采用主动发现和被动发现的混合网关发现方案建立；主动 网关发现方式，由网关周期性的产生GWADV信息，并通过活跃区域中的节点转发至源节点， 并在可选范围内选择稳定链路建立源节点与网关之间的路由；当活跃区域失效，无法将 GWADV信息转发至源节点或者源节点需要与Internet通信却没有到网关的有效路由时，采用 被动网关发现方式。

所述主动网关发现是将网关公告信息通过活跃区域发送至源节点，活跃区域之外的节点 不参与网关公告信息的转发，其过程为：

A.网关周期性的将GWADV信息发送给邻居节点；

B.某个节点u收到GWADV信息后，按以下步骤处理：

1）节点u是否具有转发资格：即节点u是否有至少一条链路有网关信息素；具有转发资 格，则转到步骤2）处理，否则，节点u丢弃信息包；

2）如果GWADV信息包是通过链路L(u,v)由节点v转发而来，节点u检查链路L(u,v)的稳定 性，当稳定性评估值S(u,v)大于阈值S_Disconnect时，转到步骤3）处理，否则，节点u丢弃信 息包，不再处理；

3）节点u按下面的公式计算GWADV信息从网关转发到u所走的路径的稳定性值R，然 后将将值R保存到GWADV信息的扩展字段中，转发给节点u的邻居节点:

R＝Min(R,S(u,v))

C.源节点收到转发而来的GWADV信息。如果通过不同路径收到同一个GWADV信息， 则选择扩展字段中R值最大的那个信息包来建立反向路由。源节点沿该路由向网关发 送注册信息，路径上的所有中间节点都会更新该节点用于组成路由的链路的网关信息 素值，更新方法是不论之前是否有网关信息素，该链路的网关信息素都设为Φ_Δ，即 Φ(u,v)＝Φ_Δ。

所述被动网关发现的过程为：源节点需要Internet服务的时候，主动向MANET发送网关 请求GWSOL信息，MANET中的每个移动节点都可以接收GWSOL信息；当节点u收到邻居节 点v转发而来的信息时，先判断链路L(u,v)的稳定评估值是否大于S_Disconnect，如果小于则丢弃 这个信息包，如果大于，则计算该信息包传输路径的稳定评估值：R＝Min(R,S(u,v))，然后将 R值保存到GWSOL信息的扩展字段中；网关收到不同路径转发过来的同一个GWSOL信息的拷 贝时，选择R值最大的一个信息包建立至源节点的反向路由，路径上的每个节点更新其用于 组成路由的链路的网关信息素值。

本发明的有益效果是：

1）本发明通过网关信息素的引导，通过活动区域中的少量节点即可将网关公告信息转发 至源节点。转发目标明确、效率高，控制开销低。

2）本发明通过链路稳定性预测，及时调整节点的转发资格，从而使活跃区域动态适应 MANET网络的拓扑变化。

3）与其它方法中由网关决定节点是否转发相比，本发明由节点本身决定是否转发网关控 制信息，因而更加灵活，适应性好。

4）本发明限制网关公告信息的只在活跃区域内传播的同时，还优先选择稳定链路建立路 由，而且对活跃子网的调整维护过程确保可以在活跃区域内找到稳定路由，进一步降低了控 制开销，全面提升了MANET网络接入Internet时的性能。

附图说明

图1是用网关信息素定义活跃区域的例子。

图2预测链路断开并调整维护活跃区域流程图。

图3链路断开导致活跃区域无效示意图。

图4选择替换链路示意图。

图5基于网关信息素的MANET接入Internet自适应网关发现算法流程图。

具体实施方式

下面结合附图与实施例对本发明做进一步说明。

在图1中实直线表示标记有网关信息素的链路，虚直线表示没有网关信息素的链路。只 要一个移动节点有一条链路标记了网关信息素，那这个节点就允许转发网关公告信息。比如 节点u,其两条链路L(u,v),L(u,b)标记有网关信息素，则节点u具有转发资格；节点h不具有转 发资格，因为其所有链路L(h,d),L(h,u)都没有标记网关信息素。灰色区域中包含网关节点和源 节点s，其它节点全部都具有转发资格，且至少有一个邻居节点具备转发资格，称这个区域为 活跃区域。GWADV信息只通过活跃区域中转发至源节点s，活跃区域外的节点如h，w等不 具备转发GWADV信息的资格。

图2是调整维护活跃区域的流程图。具有转发资格的节点会周期性的预测标记有网关信 息素的链路是否会在下一个网关广播周期内断开，如果断开则寻找可以替代的链路，并将将 要断开链路上的网关信息素转到替代链路上，这个过程中可能会有节点失去转发资格，也可 能会有节点获得转发资格，活跃区域得到调整维护，以适应MANET动态变化的拓扑结果。调 整维护活跃区域的步骤包括预测链路是否断开，寻找替换链路，重新分配网关信息素。

结合图3说明预测链路是否在下一个网关广播周期断开的方法：

图3中节点u预测其链路L(u,v)否要断开，只需核实下面两个条件：

a.链路的稳定性评估值S(u,v)比预先设定的阈值S_Disconnect小；

b.接收信号的变化趋势d_Δ小于0。

条件a和b都满足，则可以预测链路L(u,v)将会在下一个网关广播周期断开。L(u,v)的断开将会 导致活跃区域失效，即GWADV信息无法转发到源节点，因此需要提前维护，确保活跃区域 可用。

结合图4说明选择替换链路调整维护活跃区域的方法：

节点u将选择一条比较稳定的且没有网关信息素的链路。节点u选择替换链路L(u,w)时需 满足下列条件：

c链路L(u,w)之上没有网关信息素；

d对于节点w的两条链路L(u,w)和L(w,v)的稳定性评估值S(u,w)和S(w,v)都要大于阈值S_Replace。

图4中，深灰色区域中的节点的链路满足条件，即节点w的链路L(u,w)将作为L(u,v)的替换 链路。如果有多条替换链路可选，随机选择其中一条即可。将链路L(u,v)上的网关信息素转移 到替换链路L(u,w)上，节点w则获取了转发资格，并添加到活跃区域中，确保活跃区域有效。

图5是基于网关信息素的MANET接入Internet自适应网关发现算法的主要流程图。网 关将GWADV信息通过活跃区域发送至源节点，活跃区域之外的节点不参与网关公告信息的 转发，其过程为：

A.网关周期性的将GWADV信息发送给邻居节点。

B.某个节点u收到GWADV信息后，按以下步骤处理：

1）节点u是否具有转发资格：即节点u是否有至少一条链路有网关信息素。具有转 发资格，则转到步骤2）处理，否则，节点u丢弃信息包。

2）如果GWADV信息包是通过链路L(u,v)由节点v转发而来，节点u检查链路L(u,v) 的稳定性，当稳定性评估值S(u,v)大于阈值S_Disconnect时，转到步骤3）处理，否则， 节点u丢弃信息包，不再处理。

3）节点u按下面的公式计算GWADV信息从网关转发到u所走的路径的稳定性值R， 然后将值R保存到GWADV信息的扩展字段中，转发给节点u的邻居节点。 R＝Min(R,S(u,v))

C.源节点收到转发而来的GWADV信息。如果通过不同路径收到同一个GWADV信息，

则选择扩展字段中R值最大的那个信息包来建立反向路由。源节点沿该路由向网关发 送注册信息，路径上的所有中间节点都会更新该节点用于组成路由的链路的网关信息 素值，更新方法是不论之前是否有网关信息素，该链路的网关信息素都设为，即。

被动网关发现的过程为：源节点需要Internet服务的时候，主动向MANET发送网关请求 （GWSOL）信息，MANET中的每个移动节点都可以接收GWSOL信息。当节点u收到邻居节 点v转发而来的信息时，先判断链路L(u,v)的稳定评估值是否大于S_Disconnect，如果小于则丢弃 这个信息包，如果大于，则计算该信息包传输路径的稳定评估值：R＝Min(R,S(u,v))，然后将 R值保存到GWSOL信息的扩展字段中。网关收到不同路径转发过来的同一个GWSOL信息的拷 贝时，选择R值最大的一个信息包建立至源节点的反向路由，路径上的每个节点更新其用于 组成路由的链路的网关信息素值。