网络按需距离矢量多播路由协议的多路径改进方法和装置

摘要

本发明提供了一种网络按需距离矢量多播路由协议的多路径改进方法和装置，利用组领导周期性广播GRPH消息机制，对多播树结构进行优化的同时，在已经建立的多播树内建立并维护备用路径，并将其添加到备用路由表中，以便主路径失效时使用，该改进方法在维护树结构的同时，提高了多播树的鲁棒性和可靠性，降低了分组传送时延，提高了无线自组网的多播路由质量。

说明书

技术领域

本发明涉及无线自组织网络技术领域，特别是涉及一种基于网络按需距离矢量多播路由协议(MAODV-Multicast Ad Hoc On-Demand MultipathDistance Vector)的多路径改进方法和装置。

背景技术

无线自组网是一种复杂的分布式网络系统，由于其自组织、无需固定基础设施、节点可移动以及良好的抗毁性等优点而在军事指挥、紧急救援等军用和民用领域得以广泛应用。多播作为一种一点对多点或多点对多点的通信方式，具有较高的分组发送和传播效率。由于无线自组网的应用场合常常要求支持多播业务，因此对无线自组网的多播路由协议进行研究显得尤为重要。然而，无线自组网分布式、网络拓扑变化、带宽有限等固有特点，使得实现多播路由协议具有很大的挑战。当前无线自组网的多播路由协议大多数只考虑如何实现有效的通信路由，对其他因素考虑得很少，尤其在服务质量QoS(Quality of Service)和安全性方面还需要大量的深入研究。

多路径作为保障QoS的一种机制，与单路径相比，在容错、路由可靠性等方面有很多优势。单路径路由倾向于把所有负载分布在源到目的的最短路径上，在路由发现阶段只获取一条路径，无法很好地获取整个网络的拓扑信息。多路径路由为任意一对节点同时提供多条可用的路径，并允许节点选择如何使用这些路径。源节点和目的节点对之间的多条路径能够补偿无线自组网的动态特性和不可预测性。

现有的多播路由协议MAODV是一种支持多播功能的按需距离矢量路由协议，它采用双向共享树多播分发机制，按需创建多播树。树形结构中发送节点只需发送每个数据包一次，仅在树的分支处复制数据包，并且允许并行传输数据包到各个接收节点。实际应用中，这种树状结构的鲁棒性较差，网络中两节点间只有一条路径。研究表明，在网络负载较低时，MAODV协议表现出良好的性能。然而，当网络负载增大、节点移动性增强时，容易出现网络拥塞、负载不均和服务质量下降等情况。

目前，对于单播多路径的研究较多，已经提出了多种单播多路径的改进算法(如AOMDV、SMR等)。相比于单播，多播多路径的研究较少，相关文献中提出了一种MP-MAODV多路径改进算法。在MP-MAODV中，源节点发起路由寻找的过程中，利用增加的两种控制分组，根据回复的多个RREP(Routing-reply)消息建立并激活主备两条路径。然而，基于MP-MAODV协议较为复杂，协议操作中工作量大，并且其建立并计算多路径所需要的开销也很高。

因此，需要本领域技术人员迫切解决的一个技术问题就是：如何能够创新地提出一种基于网络按需距离矢量多播路由协议(MAODV-Multicast Ad Hoc On-Demand Multipath Distance Vector)的多路径改进方法和装置，以解决现有技术中存在的当负载增大时出现的网络拥塞、服务质量下降等问题，有效提高无线自组网的多播路由质量，降低实现难度。

发明内容

本发明所要解决的技术问题是提供一种基于网络按需距离矢量多播路由协议(MAODV-Multicast Ad Hoc On-Demand Multipath Distance Vector)的多路径改进方法和装置，用以保证无线自组网的多播路由质量，并有效降低实现难度。

为了解决上述问题，本发明公开了一种基于网络按需距离矢量多播路由协议的改进方法，所述方法包括：

步骤A、多播组成员利用组领导周期性组通知(GRPH-Group Hello)消息机制获得可用的多播树节点之间的备用路径信息；

步骤B、为多播组成员的每个节点增加一个备用路由表；

步骤C、用所获得的可用的备用路径信息，为多播组成员的每个节点在多播树内选择并建立备用路径，并将建立的备用路径信息记录在节点的备用路由表中；

步骤D、当节点发现主路径失效后，启用备用路由表中记录的备用路径继续多播数据分组的传输。

优选的，所述方法在启用备用路由表中记录的备用路径时还包括：

若备用路径为空，则发送消息进行路由修复。

优选的，所述步骤A具体包括以下子步骤：

多播组成员节点接收到GRPH消息；

比较GRPH消息中携带的多播组地址和组领导地址是否与本节点当前组领导表中记录的多播组地址和组领导地址相同：

若是，则通过所接收GRPH消息的ID号判定是否接收过该消息：

若是，则丢弃该GRPH消息；

若否，则判断GRPH消息是否从多播树结构的上游方向获得：

若是，则与MAODV协议操作相同；

若否，则组成员节点更新组领导表，同时，比较GRPH消息中节点到组领导跳数是否小于多播路由表中节点到组领导跳数的大小：

若是，则该多播组成员节点更新组领导表和多播路由表，同时对多播树结构进行优化，向原来的上游发送MACT-P剪枝消息；

若否，则该多播组成员节点获得一条可用的备用路径信息；

若否，则丢弃该GRPH消息。

优选的，所述备用路由表为节点所在的每一个多播组的冗余树结构列出下一跳。

优选的，所述备用路由表中记录的内容有组领导地址、多播组序列号、节点身份、下一跳、到达组领导跳数(hops)和生存时间(TTL)。

优选的，所述备用路由表中记录的下一跳包括上游下一跳和下游下一跳。

本发明还公布了一种基于网络按需距离矢量多播路由协议的改进装置，所述装置包括：

GRPH消息处理模块，利用组领导周期性广播GRPH(Group-hello)消息机制，多播组成员节点获得可利用的多播树节点之间的备用路径信息；

备用路由表添加模块，用于为多播组成员的每个节点增加一个备用路由表；

多路径的选择与建立模块，利用组领导周期性广播GRPH消息机制获得的可用的备用路径信息，为多播组成员节点在多播树内选择并建立备用路径，并将备用路径信息记录在节点的备用路由表中；

多路径路由维护机制模块，用于在路由维护模块，当节点发现主路由失效后，启用备用路由表中记录的备用路由继续多播数据分组的传输。

优选的，所述装置还包括：

修复模块，用于当启动模块所启动的备用路径为空时，发送消息进行路由修复。

优选的，所述GRPH消息处理模块具体包括以下子模块：

接收子模块，用于完成多播组成员节点接收到GRPH消息；

第一比较子模块，用于比较GRPH消息中携带的多播组地址和组领导地址是否与本节点当前组领导表中记录的多播组地址和组领导地址相同：

第一判定子模块，用于当第一比较子模块的比较结果为是时，通过所接收GRPH消息的ID号判定是否接收过该消息：

第一丢弃子模块，用于当第一判定子模块的判定结果为是时，丢弃该GRPH消息；

第二判定子模块，用于当第一判定子模块的判定结果为否时，判断GRPH消息是否从多播树结构的上游方向获得：

第一操作子模块，用于当第二判定子模块的判定结果为是时，进行与MAODV协议相同的操作；

第二比较子模块，用于当第二判定子模块的判定结果为否时，组成员节点更新组领导表，同时，比较GRPH消息中节点到组领导跳数是否小于多播路由表中节点到组领导跳数的大小：

剪枝消息发送子模块，用于当第二比较子模块的比较结果为是时，多播组成员节点更新组领导表和多播路由表，同时对多播树结构进行优化，向原来的上游发送MACT-P剪枝消息；

获得子模块，用于当第二比较子模块的比较结果为否时，该多播组成员节点获得一条可用的备用路径信息；

第二丢弃子模块，用于当第一比较子模块的比较结果为否时，丢弃该GRPH消息。

优选的，所述备用路由表为节点所在的每一个多播组的冗余树结构列出下一跳。

与现有技术相比，本发明具有以下优点：

本发明利用组领导周期性广播GRPH消息机制，对多播树结构进行优化的同时，在已经建立的多播树内建立并维护备用路径，并将其添加到备用路由表中，以便主路径失效时使用，该改进方法在维护树结构的同时，提高了多播树的鲁棒性和可靠性，降低了分组传送时延，提高了无线自组网的多播路由质量。

同时，通过基于NS2仿真平台，对本发明所述的改进方法与MAODV多播路由协议性能进行了比较分析，仿真表明随着网络负载增加，本发明所述的改进方法较好的保证了网络多方面的性能。

附图说明

图1是本发明实施例一所述的一种基于MAODV的多路径改进方法流程图；

图2是本发明实施例一所述的MAODV协议GRPH消息的处理流程示意图；

图3是本发明实施例一所述的一种基于MAODV的多路径改进方法中多路径的扩展体系结构示意图；

图4(a)是本发明实施例一所述的一种基于MAODV的多路径改进方法中已建立的多播树结构示意图；

图4(b)是本发明实施例一所述的一种基于MAODV的多路径改进方法中多播树结构的优化示意图；

图4(c)是本发明实施例一所述的一种基于MAODV的多路径改进方法中备用路径的选择与建立示意图；

图4(d)是本发明实施例一所述的一种基于MAODV的多路径改进方法中备用路由的激活与使用示意图；

图5是本发明实施例一所述的本发明所述改进方法与MAODV分组投递率比较的示意图；

图6是本发明实施例一所述的本发明所述改进方法与MAODV分组端到端平均时延比较的示意图；

图7是本发明实施例一所述的本发明所述改进方法与MAODV控制包开销比较的示意图；

图8是本发明实施例二所述的一种基于MAODV的多路径改进装置结构图。

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

实施例一：

参照图1，示出了本发明的所述的一种基于MAODV的多路径改进方法流程图，所述方法具体包括：

步骤S101，多播组成员利用组领导周期性组通知(GRPH-Group Hello)消息机制获得可用的多播树节点之间的备用路径信息；

通常来讲，网络中节点分为树外节点和树上节点，树上节点又分为组成员节点和树上转发节点，其中在组成员节点中选取一个为多播组的组领导，即树上节点共有三类：组领导、组成员和转发节点。网络中节点身份标识包括：组领导(group_leader)、组成员节点(on_group)、树上转发节点(on_tree)和树外节点(not_on_tree)。

本发明所提方法是对MAODV多播路由协议的改进，MAODV中有四种控制包分组，分别为RREQ(Route Request)、RREP(Route Reply)、MACT(Multicast Activation)以及GRPH(Group Hello)，通常称GRPH控制分组为组通知消息，GRPH消息主要用于更新或维护多播组的路由信息。

步骤S102，为多播组成员的每个节点增加一个备用路由表；

S103，用所获得的可用的备用路径信息，为多播组成员的每个节点在多播树内选择并建立备用路径，并将建立的备用路径信息记录在节点的备用路由表中；

S104，当节点发现主路径失效后，启用备用路由表中记录的备用路径继续多播数据分组的传输。

优选的，所述方法在启用备用路由表中记录的备用路径时还包括：

若备用路径为空，则发送消息进行路由修复。

参见图2，为MAODV协议GRPH消息的处理流程示意图，在MAODV协议中，组领导通过周期性地在全网中广播GRPH消息来维护多播树。每个节点仅处理第一次接收到的GRPH消息，对具有相同多播组地址和组领导地址的GRPH消息不再重复处理，根据GRPH消息来更新它的组领导表，来表明这个组领导以及到该组领导的路由。对于非多播树成员节点，收到GRPH消息后置标志位M，指示此GRPH消息已传出该多播树，然后转发此消息，其他节点收到带M标志的GRPH消息将不再转发。对于多播树成员节点，从其上游收到GRPH消息后，根据GRPH消息来更新自己当前的组领导表信息，包括组序列号、组领导地址以及节点到组领导的跳数等。

如果多播树成员节点从其非上游收到GRPH消息，首先检查自己的多播路由表中的组领导信息，如果和收到的GRPH消息中的一样，那么此GRPH消息就会被丢弃；如果两者不一致，说明有另一个具有相同多播组地址但不同组领导的多播树存在，那么就发起树的合并。树的合并是由多播树成员中其组领导地址比GRPH中组领导地址小的节点发起的。如果它的组领导地址比GRPH中的大，则将此GRPH消息丢弃。

所述步骤S101具体包括以下子步骤：

多播组成员节点接收到GRPH消息；

比较GRPH消息中携带的多播组地址和组领导地址是否与本节点当前组领导表中记录的多播组地址和组领导地址相同：

若是，则通过所接收GRPH消息的ID号判定是否接收过该消息：

若是，则丢弃该GRPH消息；

若否，则判断GRPH消息是否从多播树结构的上游方向获得：

若是，则与MAODV协议操作相同；

若否，则组成员节点更新组领导表，同时，比较GRPH消息中节点到组领导跳数是否小于多播路由表中节点到组领导跳数的大小：

若是，则该多播组成员节点更新组领导表和多播路由表，同时对多播树结构进行优化，向原来的上游发送MACT-P剪枝消息；

若否，则该多播组成员节点获得一条可用的备用路径信息；

若否，则丢弃该GRPH消息。

本发明所述的改进方法中，多播组成员利用组领导周期性组通知(GRPH-Group Hello)消息机制获得可用的多播树节点之间的备用路径信息，若多播组成员节点，收到与本节点当前组领导表具有相同多播组地址和组领导地址的GRPH消息，并且此消息是从多播树结构的上游方向获得，则该多播组成员节点更新该节点的组领导表，然后继续广播GRPH消息，符合MAODV协议的基本操作；若此GRPH消息是从多播树结构的非上游方向获得，则该多播组成员节点在更新组领导表的同时，比较GRPH消息中节点到组领导跳数与多播路由表中节点到组领导跳数的大小。

若GRPH消息中携带的节点到组领导的跳数更小，则该多播组成员节点更新组领导表和多播路由表，同时对多播树结构进行优化，向原来的上游发送MACT-P剪枝消息，向新的上游发送MACT-J激活消息。若GRPH消息中携带的节点到组领导跳数不小于多播路由表中节点到组领导跳数，则为该多播组成员节点增加一条备用路径。所述改进方法中，多路径的扩展体系结构示意图可参照图3所示。

为进一步进行介绍，这里进行举例说明，如图4(a)、4(b)、4(c)、4(d)所示，节点L为多播组的组领导，节点A、D、F、G、H、I、J和K为组成员节点，节点B、C、E为多播树上的转发节点。组领导L周期性广播GRPH消息，用于更新或维护多播组的路由信息。当组成员节点F收到节点G广播的GRPH消息时，判断节点G是节点F所在多播树的上游节点，则节点F更新自己的组领导表，继续广播该GRPH消息。当节点F收到节点D广播的GRPH消息时，判断节点D不是节点F所在多播树的上游节点，但属于相同的多播组且具有相同的组领导地址。若节点F判断此路径优于原来已建立的多播树结构，则节点F向节点G发送MACT-P剪枝消息，向节点D发送MACT-J激活消息，进行多播树结构优化。同理，若节点J收到节点D广播的GRPH消息，判断此路径并不优于原来已建立的多播树结构，则J节点将其添加或更新到备用路由表中，待使用时再激活，然后将此GRPH消息丢弃。由于备用路径的建立，当节点J与节点E之间发生断链时，组领导L仍然可以通过备用路径与节点J建立通信，降低了由于修复断链或重新发起路由请求而造成的缓存分组丢失、未投递的概率，增强了多播树结构的鲁棒性和可靠性，降低了平均分组传送时延。

优选的，所述备用路由表为节点所在的每一个多播组的冗余树结构列出下一跳。

优选的，所述备用路由表中记录的内容有组领导地址、多播组序列号、节点身份、下一跳、到达组领导跳数(hops)和生存时间(TTL)。

优选的，所述备用路由表中记录的下一跳包括上游下一跳和下游下一跳。

在本发明所述的改进方法中，为多播组成员的每个节点增加一个备用路由表，备用路由表数据结构负责记录多播树内节点的备用路由信息。备用路由表为节点所在的每一个多播组的冗余树结构列出下一跳，即其中每一个条目代表一个多播组隐含的树结构。这样在本发明所述的改进方法中，每个节点除了要维护一个单播路由表、一个多播路由表和一个组领导表外，还需维护一个备用路由表。备用路由表也用于维护多播路由，负责记录多播树内节点的备用路由信息。

备用路由表为节点所在的每一个多播组的冗余树结构列出下一跳，即其中每一个条目代表一个多播组隐含的树结构。备用路由表条目包含的内容有组领导地址、多播组序列号、节点身份、下一跳、到达组领导跳数(hops)和生存时间(TTL)。与多播路由表类似，备用路由表的相关操作也包含备用路由表项的创建、查找多播组、删除指定多播组、添加多播组等基本操作函数。由于多播路由表中记录的下一跳(包括上游下一跳和下游下一跳)是通过邻居链表来实现的，因此，备用路由表也需要创建自己的邻居链表，其包含了关于邻居链表的构造函数和析构函数，以及查找、删除、清空等函数。

对于多播组成员节点，收到非上游节点发送的GRPH消息，若GRPH消息携带的节点到组领导跳数不小于多播路由表中节点到组领导跳数，则为该多播组成员节点增加或更新备用路由。

首先，查看备用路由表状态，如果备用路由表为空，则为该节点创建一个备用路由条目；如果备用路由表不为空，且GRPH消息中携带到组领导跳数更小，则更新备用路由表条目。GRPH消息处理结束后，将此消息分组丢弃。

由于节点的移动性、网络拓扑变化等原因，链路容易发生断裂。节点在一段时间内没有收到相邻节点发送的任何消息或者不能将数据分组发送给路由上的下一跳节点，则判断节点间的链路发生中断。

多播树节点发现一条活跃链路断开，如果是下游链路，则删除那条链路并且需要的话，设置剪除定时器进行剪枝操作。如果是上游链路，首先删除其路由表中的相关路由项，同时判断到达该上游节点是否存在备用路径。如果备用路由表不为空，则启用备用路径，发送MACT消息进行备用路由激活，继续多播数据分组的传输，否则按照MAODV协议的操作处理，发送RREQ-J消息进行路由修复。

使用网络仿真软件NS2对改进算法B-MAODV进行仿真验证。通过增加发送数据分组的节点数目，来模拟网络负载的不断增加。以下选取了分组投递率、分组端到端的平均延时以及控制包开销，分别对B-MAODV和MAODV协议的性能进行评估。

如图5所示，随着发送节点数量的不断增加，本发明所述改进方法与MAODV的分组投递率大体上都是逐渐降低的，但本发明所述的改进方法的分组投递率始终高于MAODV。分析原因，发送节点数目增加，意味着向多播组发送数据分组随之增多，网络的负载也随之增大，随着节点的移动发生断链的几率增大，使得丢包率有所提升。本实施例中所述的改进方法与MAODV不同的是建立了备用路径，降低了由于修复断链或重新发起路由请求而造成的缓存分组丢失、未投递的概率，因此分组投递率不会有明显下降，相比于MAODV仍维持在较高水平。可见，多路径提高树状多播路由协议可靠性和鲁棒性，协议性能得到改善。

如图6所示，随着发送节点数量的增加，本发明所述改进方法与MAODV分组端到端平均时延比较的示意图，两种情形下的平均延时都逐渐增大。从图中可以看出，改进方法对分组端到端平均延时的改善明显。分析原因，随着发送节点数目的增多和节点的移动，网络拓扑结构更容易发生变化，这时就需要不断维护链路，使得分组端到端延时也逐渐增加。与MAODV不同的是，本发明所述的改进方法，在已经建立的多播树上增加冗余路径，提高了多播树内多播数据的传送效率，降低了分组传送时延，在维护树结构的同时，大大减少了由于频繁路由寻找而带来的网络延迟。

如图7所示，当发送节点数量小于6时，本发明所述改进方法中的控制包开销高于MAODV，但随着发送节点数量的逐渐增大，本发明所述的改进方法控制包开销逐渐降低，而MAODV协议的控制包开销逐渐升高。这是因为，改进方法中提供的备用路径机制减少了频繁重新发起路由请求的可能，降低了协议在频繁重建路由上花费的控制包开销，但由于备用路径的建立也增加了一定的控制开销，因而，协议的改善效果在网络负载较大时更为明显。

对本实施例进行补充介绍的有，本发明中基于MAODV多播路由协议的多路径改进方法，称其为B-MAODV(Backup Routing Multicast Ad HocOn-Demand Multipath Distance Vector)。

实施例二：

参照图8，示出了本发明的一种基于网络按需距离矢量多播路由协议的改进装置的结构图，所述装置包括：

GRPH消息处理模块801，利用组领导周期性广播GRPH(Group-hello)消息机制，多播组成员节点获得可利用的多播树节点之间的备用路径信息；

备用路由表添加模块802，用于为多播组成员的每个节点增加一个备用路由表；

多路径的选择与建立模块803，利用组领导周期性广播GRPH消息机制获得的可用的备用路径信息，为多播组成员节点在多播树内选择并建立备用路径，并将备用路径信息记录在节点的备用路由表中；

多路径路由维护机制模块804，用于在路由维护模块，当节点发现主路由失效后，启用备用路由表中记录的备用路由继续多播数据分组的传输。

优选的，所述装置还包括：

修复模块，用于当启动模块所启动的备用路径为空时，发送消息进行路由修复。

优选的，所述GRPH消息处理模块801具体包括以下子模块：

接收子模块8011，用于完成多播组成员节点接收到GRPH消息；

第一比较子模块8012，用于比较GRPH消息中携带的多播组地址和组领导地址是否与本节点当前组领导表中记录的多播组地址和组领导地址相同：

第一判定子模块8013，用于当第一比较子模块的比较结果为是时，通过所接收GRPH消息的ID号判定是否接收过该消息：

第一丢弃子模块8014，用于当第一判定子模块的判定结果为是时，丢弃该GRPH消息；

第二判定子模块8015，用于当第一判定子模块的判定结果为否时，判断GRPH消息是否从多播树结构的上游方向获得：

第一操作子模块8016，用于当第二判定子模块的判定结果为是时，进行与MAODV协议相同的操作；

第二比较子模块8017，用于当第二判定子模块的判定结果为否时，组成员节点更新组领导表，同时，比较GRPH消息中节点到组领导跳数是否小于多播路由表中节点到组领导跳数的大小：

剪枝消息发送子模块8018，用于当第二比较子模块的比较结果为是时，多播组成员节点更新组领导表和多播路由表，同时对多播树结构进行优化，向原来的上游发送MACT-P剪枝消息；

获得子模块8019，用于当第二比较子模块的比较结果为否时，该多播组成员节点获得一条可用的备用路径信息；

第二丢弃子模块80110，用于当第一比较子模块的比较结果为否时，丢弃该GRPH消息。

优选的，所述备用路由表为节点所在的每一个多播组的冗余树结构列出下一跳。

本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。对于装置实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。

以上对本发明所提供的一种网络按需距离矢量多播路由协议的多路径改进方法和装置进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。