用于降低网络开销的改进ODMRP算法研究

杜 丹，王 凯

(1.陆军装备部驻石家庄地区第一军代室，河北 石家庄 050081；2.中国人民解放军32382部队，北京 100072)

0 引言

MANET[1]，由于它不依赖任何固定基础设备的快速组网能力，得到了广泛的应用。网络路由算法的研究也多种多样[1-12]。由于MANET自组织网络应用中存在大量组播业务，因此 MANET 自组织网络的组播路由技术是近几十年来的研究热点之一。MANET现有的组播路由协议各有其优缺点。树型组播路由协议如AMRIS[13]协议和MAODV[14]协议，有较高的数据组分发效率，但其鲁棒性不足。CAMP[15]和ODMRP[16]是网格型组播路由协议，具有很高的健壮性，但它们多重路由增加了网络负载，在一定程度上增加了组播路由协议的控制开销。结合树型与网格型的混合型组播路由协议具有二者共同的优势，取长补短。如AMRoute协议[17]和MCEADR协议[18]，能较好地实现协议的性能，但实现较为复杂，将网格型和树型二者的优势更有效地结合，将是下一步研究的主要内容。针对网格型组播路由协议的不足，在ODMRP协议基础上，提出了备用转发节点的概念，用于减少并控制多重路由，降低了网络负载，保证了路由的鲁棒性，完善了ODMRP协议。

1 ODMRP协议

按需组播路由协议 ODMRP 是网格型组播路由协议，其中转发网格由转发组构成。转发组由多个用于转发组播数据分组的成员节点构成。ODMRP的路由维护与创建是由组播源节点按照需要进行的。

在 ODMRP 中，如果有消息需要发送，就在全网使用广播泛洪路由建立请求。因为转发网格中，任意两个组播成员节点间的传输路由长度均为最短，故组建成以组播发送节点为跟的逆向最短路由树。当组播组内其它成员收到路由建立请求时，按照最短路由树向组播源节点发送应答消息。树的节点都是该组的转发成员，而这些树的叠加便构成了组播路由协议的转发网格。当网格构建完成以后，就可以通过网格中的转发节点发送数据分组，转发网格的建立如图1所示。

图1 单组播源ODMRP的网格发现过程Fig.1 Grid discovery process for single multicast source ODMRP

2 改进方案

2.1 基于备用转发节点的路由建立

改进：原协议因为含有大量非必须转发节点，增加了多重路由，虽然增强了鲁棒性，但产生了极大的分组传输量及网络负载。本文对转发节点进行处理，减少转发节点数量，在保证原协议鲁棒性的基础上，减少了网络控制开销。

请求及应答消息结构：

{组播组地址，消息类型(接入请求/数据)，发送节点地址，TTL跳数，...}

{组播组地址，消息类型(接入应答)，下一跳节点地址，转发标识(0：转发，1：备用转发),...}

改进ODMRP 中组播路由的建立由接入请求及接入应答两部分构成，且根据需要执行。当有数据需要发送且无可达路由时，便周期性地发送泛洪路由请求 JOIN-QUERY(JQ)，更新组播路由及组播成员。转发节点收到在存活期限不为零，且不重复的 JQ 请求，记录其上一跳节点的ID或IP，并继续广播。当该组播其它成员节点收到它的接入请求消息时，则广播接入应答JQ消息，消息中包括该组源节点和下一跳成员地址信息及转发标识(首次或前N次(自定义控制转发组节点数量)收到路由请求置0，非首次收到路由请求置1)。收到JR应答消息的节点，首先查看该接入应答中的下一跳节点地址是否是自己的地址。若是，则表明该节点是转发节点，在通往组播发送节点的路由上。然后查看应答消息中转发标识，对本节点转发标识FG-FLAG(默认-1不转发)进行更新置0，使其进入该组的转发网格，一直继续转发，直到接入应答消息传送至其发送者。应答消息中的转发标识如果不是0，若本节点FG-FLAG为0，则不变；若本节点FG-FLAG为-1，则置1；若本节点FG-FLAG为其它值，则FG-FLAG加1，用作数据转发的概率。ODMRP改进组播路由协议网格的发现过程如图2所示。ODMRP改进协议中路由建立的具体算法流程如图3所示。

图2 单组播源ODMRP改进组播路由协议的网格发现过程Fig.2 Grid discovery process for improving single multicast source ODMRP

图3 ODMRP改进协议中路由建立的具体算法流程Fig.3 Specific algorithm flow for routing establishment in ODMRP improvement protocol

2.2 动态调整接入请求周期

ODMRP中组播成员及路由的形成是根据需要完成的，因此存在相应的生存期限TTL。超过该TTL且未接收到新的 JQ 消息，就判定该节点已经不再是组播网格的转发成员，该节点将停止对其数据报文的转发。所以，组播组内的源和目的节点需要周期性地分别发送接入请求及应答报文，使得网格中的转发节点能够在TTL结束前更新它的上一跳节点及下一跳节点的地址，从而对该组播组的转发网格进行维护。根据网络规模和组播内节点间的距离，动态调整发送路由请求的周期，降低路由控制开销。

2.3 概率性数据转发

当ODMRP组播路由形成之后，其发送节点便能经由组播转发网格向其目的节点传输消息。在源节点发送组播消息过程中，其源节点需通过周期性发送路由控制报文来对转发网格进行维护，收到组播消息的转发节点，在检查该消息不是重复消息，且自身转发标志 FG-FLAG为0有效之后，对其进行转发；在FG-FLAG不为-1且不为0，以概率转发组播分组，概率与节点移动速度快、FG-FLAG数值成正相关。该过程在为组播成员节点提供冗余路径的同时，降低了控制报文开销，且能避免消息通过失效路由传送。同原有ODMRP协议相比，减少了节点转发数量，并在一定程度上保证了鲁棒性。同树型结构相比，增加了分组传递率。

3 结束语

本文在传统ODMRP协议基础上，对转发节点数量进行控制，既保持了原ODMRP协议的鲁棒性，又在数据消息接收率相当的情况下降低了网络控制报文的开销，并且算法简单，容易实现。下一步工作在仿真软件上对改进方案和原ODMRP协议进行仿真，观察改进方案的实际运行效果。随着对组播协议研究渐热，我们后期的工作还要将该方案应用到混合组播路由协议中，并和原混合组播路由协议进行比较,并仿真观察效果。