一种新型的Ad hoc QoS多播路由协议

摘要：无线自组织(Ad hoc)网络的应用环境要求其必须提供一定的服务质量(QoS)保证，然而，无线信道固有的特点及节点移动造成网络拓扑的频繁变化，使得在无线Ad hoc网络中支持QoS较困难。可以采用Ad hoc QoS多播(AQM)协议通过事先预约邻居节点以跟踪资源的有效性等措施来解决这一问题。通过考虑传输时延、丢失率、带宽要求、时延抖动、吞吐量等QoS指标，寻找满足特定QoS要求的路由，AQM协议可以明显地改善多播通信的性能。网络仿真结果表明AQM协议基本适合Ad hoc网络。

关键词：自组织网络；服务质量；多播；路由

Abstract:The application environments require that wireless Ad hoc networks should support Quality of Service (QoS). However, in a wireless Ad hoc network, supporting QoS is very difficult because of the inherent characteristics of the wireless channel and the frequent changes of network topology. An Ad hoc QoS multicasting (AQM) protocol can solve this problem by previously reserving neighbor nodes for tracking resource availability. By considering QoS restrictions of transport delay, lose ratio, band request, delay jitter and throughout, and by finding the adaptive routing, the AQM protocol can obviously improve the efficiency of multicasting sessions. The results of network simulation show that QoS is essentially applicable to Ad hoc networks.

Key words:Ad hoc network; QoS; multicasting; routing

在现代网络中，随着对服务质量(QoS)有严格要求的业务(如实时多媒体业务、交互式业务等)的出现，要求网络能够提供具体的QoS保障。自组织(Ad hoc)网络也有同样的QoS保障需求，所以提供QoS保障是实现Ad hoc民用化，确保无线Internet提供多媒体实时服务的关键技术。

QoS路由在实现QoS保障中具有很重要的作用。在建立连接和预留资源前，必须要在源节点和目的节点间选择一条合适的链路，链路的选择一方面受网络中可用资源的限制，另一方面必须满足一定的端到端带宽或时延等QoS需求。多播，是一种一点到多点或多点到多点的通信方式，即多个接收者同时接收一个源发送的相同信息。在一个多播会话中的所有发送和接收节点集合构成多播组。常见的多播应用包括会议电话、视频点播、交互式网络游戏等，是一些基于组或协议的网络应用。将多播技术的有效性和Ad hoc网络的特殊优势相结合，在自组网络中开发一些基于组的多播应用业务，具有非常广阔的前景。

1 现有的多播路由协议

支持多播的路由协议称为多播路由协议，Ad hoc网络多播路由协议的核心是管理多播组的成员，动态生成和维护一个多播传输结构，建立多播数据的传输路由。

Ad hoc网络拓扑结构的不断变化使得QoS路由问题变得相当复杂。假定Ad hoc网络的拓扑结构变化较慢，使得一定时间间隔内网络拓扑改变的状态信息能够得到及时更新，则这时的Ad hoc网络是稳定的。现有的大多数QoS路由算法都是以Ad hoc网络是稳定的这一假设为前提，相关算法也以此为前提。目前已经提出了若干Ad hoc网络的多播路由协议。

1.1 按需多播路由协议

按需多播路由协议(ODMRP)是一种按需的Ad hoc多播路由协议，由多播数据的发送者按需发起建立多播路由[1]。通过建立一个连接多播数据发送者和接收者的多播网结构来进行多播数据分组的转发。多播组成员及路由信息的更新由源发送节点按需周期性地进行。加入和离开多播组不需要发送额外的控制信息，且不需依赖下层的单播路由协议。

ODMRP协议比较简单，健壮性也较好，不足之处是当多播组中的发送节点数量很多的情况下，控制消息的“洪泛”会造成过多的信道开销。

1.2 多播Ad hoc按需距离矢量路由协议

多播Ad hoc按需距离矢量(MAODV)路由协议是在单播Ad hoc按需距离矢量(AODV)路由协议的基础上设计的按需多播路由协议[2]。在该协议中，当一个节点欲加入某个多播组接收数据或欲向某个多播组发送数据时，需要发起建立多播路由的过程。多播路由的建立仍使用单播AODV路由协议中的路由请求(RREQ)和路由响应(RREP)消息，另外还增添了一个多播激活(MACT)消息，用于对多播路由的确认。MAODV通过动态地建立一个多播组成员共享的多播树结构来进行多播数据的传输。节点加入或离开多播组都需要发送一定的控制消息并对多播树进行相应维护。

MAODV路由协议在单播AODV的基础上可以很容易实现，但是在可扩展性、健壮性等方面欠佳。

1.3 核心的网格协议

核心的网格协议(CAMP)是一种基于多播网的Ad hoc多播路由协议[3]。它为每个多播组建立一个包含所有接收节点到发送节点逆向最短路径的共享多播网结构。在该协议中有一个或多个核心节点，其他节点将向核心节点发送加入多播组的请求，而不是采用“洪泛”的方法，从而可以节省节点加入一个多播组的通信开销。核心节点不需要是多播网结构的一部分，它的失效也不会导致数据分组转发及多播网维护过程的停止。CAMP支持发送节点以单工方式加入多播节点，即节点仅发送多播数据，却不接收该多播组中其他节点发送的多播数据。CAMP协议需要依赖下层的单播路由协议，要求它必须能够在有限的时间内提供到所有目的节点的正确路由及距离消息。

CAMP通过使用核心节点，避免了节点加入多播组时控制消息的“洪泛”。但是在节点失效和网络分割的情况下，CAMP需要依赖下层的单播路由协议才能正常工作。

1.4 Ad hoc多播路由协议

Ad hoc多播路由(AMRoute)协议为每个多播组建立一个多播组成员共享的双向虚拟多播树，只有多播数据的发送者和接受者才是多播树中的节点，且只有多播组成员才可以进行分组的复制和转发，无需网络中其他不相关节点的支持[4]。在多播树建立之前需要先建立一个多播网结构来建立多播组成员之间的连接关系。该协议主要关注多播路由的健壮性，而不是最小带宽或时延指标，而且它需要依赖下层协议处理网络的动态变化。

1.5 递增序号的Ad hoc路由协议

递增序号的Ad hoc路由协议(AMRIS)[5]是一种基于共享树的按需多播路由协议，支持在一个多播会话中有多个发送者和接受者。AMRIS的核心思想是以多播会话中的某个发起节点为根，动态地给每个节点分配一个组播会话成员标识(MSM_ID)号，形成一个有向无环图(节点离根越远，其MSM_ID的值越大)，然后在此基础上利用有向无环图的子集形成一个多播树。节点的MSM_ID号可用来动态管理节点加入或离开多播组，决定多播数据的传送方向及用于链路中断时多播树的重构等，以避免多播树产生环路。

该协议中，节点无需存储任何全局性的信息，链路的修复具有局部性，但当网络的拓扑变化频繁时，维护节点MSM_ID的控制开销较大。

2 AQM路由协议

前面介绍的几种多播路由协议，设计的目的是用最少的冗余，将多播数据分组传送到多播组的每个成员节点，以及当路由发生变化时，协议如何保证重选路由等问题，对于网络的传输时延、时延抖动、带宽等问题都没有予以考虑。

随着网络的发展和用户需求的不断提高，一些特殊业务不仅要求保证通信的基本需求，同时要求网络能够在时延、带宽等方面提供保障，以保证业务的开展。因此，在Ad hoc网络中，如何合理有效地利用资源，提高数据传输性能，进而为各种多媒体业务的服务质量提供保障，已成为一个十分突出的问题。

在这种情况下，设计多播路由时，还要考虑传输时延、丢失率、带宽要求、时延抖动、吞吐量等QoS指标，寻找满足特定QoS要求的路由。按照此原则设计的Ad hoc QoS多播(AQM)协议可以分为3个功能模块：会话建立和结束、成员节点管理、邻居节点保持。

2.1 会话建立和结束

一次会话可以由任何一个节点通过广播一个会话开始(SES_INIT)消息来发起。SES_INIT消息中，包括节点的标识符、会话的应用类型，以及所要求的QoS保障的参数。网络中，每个参与会话的节点都有一个会话表(TBL_SESSION)，用来存放会话信息。

成员节点表(TBL_MEMBER)用来记录上一跳节点的状态，以及源节点经上一跳节点到本地节点的链路上的QoS状况。在报文继续向前广播之前，节点要先根据当前的网络状况来更新QoS表项。如果现在的网络状况达不到要求，报文将被丢弃，而不再继续向前广播。在这个表中，用跳(Hop)数信息来避免自环。

会话的发起者如果发出结束(SET_DESTROY)消息，则这个会话将会被结束。节点一旦接收到此消息，将会把与此会话相关的所有表项中的内容全部清除。如果收到消息的节点正在传输与此会话相关的内容，节点将立即释放占用的信道，停止传输。接收到结束消息的节点将会被强制性地停止此次会话。

2.2 成员节点管理

如果一个节点想要加入到一个会话中，必须首先广播一个加入请求(JOIN_REQ)消息。只有目的多播组的成员节点才能对JOIN_REQ消息发送应答。当目的多播组的成员节点收到JOIN_REQ消息时，则修改相应的路由表和多播表，并单播发送加入应答(JOIN_REP)消息(包含下一跳的地址和链路上的QoS信息)。

发送JOIN_REQ消息的节点等待一段时间后，通常会收到多个JOIN_REP消息，它会在可选链路中选择能提供最佳QoS保障的链路，并向选好的下一跳单播发送JOIN_RES消息，激活多播表中选定的下一跳。当下一跳节点收到该消息后，将更新多播表中的条目，如果此节点以前不是多播树成员，则也向自己多播表中的下一跳单播JOIN_RES消息。如此循环，直至到达发送JOIN_REP消息的节点，一个更新后的多播树就建立好了。

如果一个节点想要离开多播树，则需发送离开会话(LEAVE_SES)消息，就可以脱离多播树。当相邻节点收到LEAVE_SES消息后，将其信息从多播路由表中删去，不需返回应答消息。

2.3 邻居节点管理

节点周期性地向邻居节点广播Hello消息(NBR_HELLO)。通过Hello消息来向邻节点表明自己的存在，以及自己的带宽利用情况。节点将收到的NBR_HELLO消息的内容保存到邻居节点表(TBL_NEIGHBOUR)中。这个表中的信息将会被用来计算邻居节点分配给多播会话的带宽总数。如果节点在一定的时间内没有收到来自邻居节点的Hello消息，就表明此邻居节点已经失踪，可以将它从TBL_NEIGHBOUR、TBL_SESSION、TBL_MEMBER表中删除。

由于无线网络的特点，节点的可用带宽是与它相邻的节点的剩余带宽。一个节点只能用还没有被自己和邻居节点用掉的剩余资源。这种近似剩余带宽的算法有一些缺陷，它没有考虑未与它直接相连的节点的信息。因此，可能会存在“隐终端”的问题。

3 AQM路由协议的网络仿真

文献[6]对AQM路由协议进行了仿真。仿真针对两种不同类型的业务：高质量话音业务和高质量视频业务进行。两种业务QoS要求不同。高质量话音业务要求速率128 kb/s，传输时延不超过10 ms。高质量视频业务要求速率256 kb/s，传输时延不超过100 ms。仿真结果如图1、图2所示。

从图1中可以看出，由于高质量话音业务所需带宽较小，因此，在网络节点数小于15的情况下，两种算法没有明显的差别，但随着网络规模的增大，采用AQM协议可以支持更多的会话。在50个节点的网络中，采用AQM协议时的会话满意度可以达到75%，没有采用QoS路由协议时的会话满意度仅为50%左右。

在对高质量视频业务的仿真中，采用AQM协议的网络，在节点少于30的小型网络中，会话满意度在60%以上，随着网络的增大，会话满意度逐渐减小到25%左右。但在没有采用QoS路由协议的网络中，在网络节点数大于30的情况下，网络满意度就迅速减少至20%左右。

通过以上两个仿真结果可以很明显地看到，采用AQM协议的网络性能明显地优于没有采用QoS路由协议的网络。随着网络规模的增加，这种差别会更加明显。

4 结束语

AQM协议通过事先预约邻居节点、跟踪资源的有效性来提高多点传输的效率，同时在会话开始时通告网络的QoS状况。在AQM协议工作过程中，信息是随时更新的，并且被用来选择能满足会话的QoS要求的最佳路由，所以AQM协议能明显地改善多播的性能。

AQM是一种相对简单的QoS多播路由协议，在协议制订的过程中没有涉及多播路由协议的可靠性、可扩展性及安全性等问题，这些都是今后研究多播路由的方向。

5 参考文献

[1] Lee S J, Gerla M, Chiang C C. On-Demand Multicast Routing Protocol [A]. Proceedings of IEEE Wireless Communications and Networking Conference (WCNC´99),Vol 3[C]. New Orleans(LA,USA), 1999. Piscataway(NJ,USA): IEEE Operations Center, 1999.1298-1302.

[2] Royer E M, Perkins C E. Multicast Ad Hoc On-Demand Distance Vector (MAODV) Routing[R]. IETF draft-ietfmanet-maodv-OO.txt). 2000.

[3] Garcia-Luna-Aceves J J, Madruga E L. The Core Assisted Mesh Protocol(CAMP)[J]. IEEE Journal on Selected Areas in Communications, 1999,17(8): 1380-1394.

[4] Xie J, Talpade R R, McAuley A, et al. AMRoute: Ad Hoc Multicast Routing Protocol[J]. Mobile Networks and Applications, 2002,7(6): 429-439.

[5] Wu C W, Tay Y C. AMRIS: A Multicast Protocol for Ad Hoc Wireless Networks[A]. Proceeding of IEEE Military Communications Conference (MILCOM´99),Vol 1[C]. Atlantic City(NJ,USA), 1999. Piscataway(NJ,USA): IEEE,1999.25-29.

[6] Bur K, Ersoy C. Multicast Routing for Ad hoc Network with a Quality of Service Scheme for Session Efficiency[A]. Proceedings of 15th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, Vol 2[C]. Barcelona(Spain),2004. Piscataway (NJ,USA): IEEE.1000-1004.

作者简介：

赵莉，南京邮电大学信息工程系信号与信息处理专业在读硕士研究生，研究方向为移动通信与无线技术。