解放军理工大学通信工程学院 王海涛
摘 要：个人通信和移动计算的发展要求网络基础设施可以快速配置并能够支持多媒体业务。本文介绍了移动多跳无线网络中支持QoS的困难和相关工作，阐述了一种用于在Ad hoc网络中支持多媒体业务的异步网络协议—MACA/PR，并详细地说明了其捎带预约机制和QoS路由算法。
关键词：Ad hoc网络 服务质量 载波监听多址访问 媒体接入冲突避免/捎带预约 QoS路由
王海涛 男，生于1976年生，博士，讲师。现在解放军理工大学通信工程学院工作，研究方向包括移动IP、Ad hoc网络和QoS保障。
一、前言
Ad hoc网络是一种移动多跳无线网络，在这种网络中传输多媒体业务至今仍是一个非常困难和复杂的问题。分组无线电网络（PRNET）解决了移动多跳网络中的数据传输问题，但是不能支持多媒体业务，它采用在多个路径同时转发相同分组的方法来保证分组投递的可靠性，但是在网络负载增加时无法保证业务的QoS。WAMIS (Wireless Adaptive Mobile Information Systems)的目标也是解决3M问题，它使用一种分簇的TDMA机制，每个簇可以使用不同的码字来增加空间重用，并且每个簇可以管理自己的信道接入，从而能够比较容易地支持实时业务。簇间使用一个全局同步的时隙TDM帧，时隙可以通过快速预约的方式被实时业务预约，空闲的时隙可以通过随机接入机制被数据报业务使用。此外UCLA还提出了虚拟网络和SWAN网络，它们也采用时隙同步方式，但是更多地利用了CDMA采用的直接序列扩频编码技术（DSSS），即通过高效的分布式功率控制技术使更多使用不同码字的连接采用相同的时隙。但是以上这些机制要求多个码字和全局同步，实现比较复杂，成本较高。为此可以考虑采用一种不需要时隙同步和码字分割的网络协议来支持多媒体业务。
二、媒体接入冲突避免/捎带预约协议（MACA/PR）
目前在WLAN中，一些新的MAC机制和网络体系结构已经部分解决了这个问题，尽管WLAN范围较小、带宽较高、通常是与一个中心基站一跳相连，但是一些WLAN技术可以扩展应用到多跳环境。传统的WLAN使用CSMA机制，解决了发送侧的冲突，但是不能解决接收者处的冲突，即隐终端问题，如图1所示。媒体接入冲突避免协议（MACA）使用RTS/CTS握手机制很大程度上解决了这个问题，但是也不能完全消除，如图2所示，D发出的CTS可能与S1发送的RTS在时间t2冲突，使得D1无法接收到来自D的CTS，于是可能向D发送RTS而与D处收到的数据发生冲突。MACAW进一步提高了MACA的性能，MACA中链路层的冲突必须由传输层进行恢复，从而大大降低了服务性能（由于TCP的流控机制回退避重发分组并可能进入慢启动阶段），而MACAW提供了快速恢复机制，即使用链路层ACK确认来加速数据报的重传从而减少了隐终端造成的性能将级。FAMA又对MACAW进行了改进，它在每个空闲时隙的开始使用非坚持CSMA来防止重复的冲突，从而提高了业务重载时的网络性能。目前广泛用于WLAN物理层和MAC层的IEEE802.11标准包括了MACA和MACAW的冲突避免特征，它采用CSMA/CA并使用ACK确认机制来加速重传，具有很多优良的特性：异步、分布式、消除隐终端并能提供较好的信道利用率，但是它不能很好地支持实时业务。为此文献提出了一种基于CSMA/CA并组合了WLAN的异步特征和传统TDM网络支持QoS的特性的网络协议—MACA/PR，它在MAC层使用CSMA/CA，在网络层采用带宽预约和QoS路由机制。
MACA/PR是对IEEE 802.11和FAMA机制的扩展。严格说来，MACA/PR是一种允许在单跳链路上建立实时连接的媒体接入协议，但是通过增加了QoS路由算法和快速连接建立机制，它能够在Ad hoc网络中支持QoS路由和端到端的多媒体连接。它包括三个部分：用于传输数据分组的MAC协议，建立实时连接的预约协议和QoS路由算法。对于数据报业务，MACA/PR采用的MAC层协议与IEEE802.11类似，并集成了FAMA中提出的非坚持机制。在MACA/PR中，节点必须等待预约表（RT）中出现一个空闲“窗口”，RT记录在其传输范围内的所有站预约的发送和接收窗口。如果发现空闲窗口，它将继续等待一段时间后对信道进行侦听，如果信道空闲，则通过RTS-CTS-PKT-ACK过程来传输分组，否则继续等待直到信道空闲并重复以上过程。对于实时分组而言，为了传递一个实时会话的第一个数据分组，源节点首先发起RTS-CTS会话，如果收到CTS，再发起PKT-ACK，但对于这个实时会话的其它分组只需使用PKT-ACK，从而减少了时延。如果发送节点连续几次没有收到ACK，它将重新使用RTS-CTS发起会话，并且在发生分组冲突时不重传实时分组。为了给实时业务预留带宽，实时调度信息包含在PKT和ACK的分组头中传输。也就是说，实时分组通过邻居节点中传播和维护的预约表来避免隐终端而不是借助于RTS-CTS会话。在节点移动和RT没有得到及时更新时会出现暂时的冲突，但当RT稳定时，每个节点只在允许的窗口内传送而不会冲突。
三、MACA/PR中的捎带预约机制
MACA/PR通过快速预约来建立实时连接，实时业务可以是CBR业务流或VBR业务流。实时业务流的第一个数据分组沿着所选路径进行资源预约，一旦第一个分组在某条链路上被接受，该链路上的一个传输窗口将在合适的时间间隔被预约用于该连接随后的所有分组，当窗口在规定的时间内空闲未用，则被释放。为了在每跳链路上成功地发送一个实时连接的第一个分组，源节点发出的第一个分组同样采用RTS-CTS握手机制，RTS和CTS中规定了该数据分组的长度，收到CTS后发送者发送该数据分组，并且接收者使用ACK来确定来分组的成功发送，否则发送者重发RTS分组。该过程反复进行直到成功传送第一个数据分组。我们假设CYCLE为两个实时分组允许的最大时间间隔，发送者在当前分组传输后的CYCLE时间内调度下个分组的传输并在当前分组中捎带预约信息。接收者将此预约信息放入预约表并使用ACK向发送者确认预约。收到数据分组的发送节点的邻居节点被暂时阻塞从而避免与返回的ACK造成冲突，并可以了解下一个分组的传输时间。与此相似，接收节点的邻居节点收到ACK后会避免在接收者接收下一个分组时进行传输。图3给出了MACA/PR的连接建立过程，图4解释了数据分组和ACK分组如何向邻居节点通知下一个分组的传输调度。对于一个进行之中的会话，ACK用于刷新预约而不是用于重传（实时分组不重传），如果源节点连续N次收不到ACK，那么它将认为预约时隙失效，这可能是因为链路干扰或路径失效造成的。此时，它将重新使用RTS-CTS在相同链路的其它时隙或另一条替换路径上发起连接建立过程。图4中，任何听到RTS的邻居节点会推迟发送从而使得发送节点S可以收到CTS，收到CTS的邻居节点同样会避免与随后的数据分组发生冲突，而随后接收节点发出的ACK将包含下一个分组的传输时间，收到此ACK分组的邻居节点将会避免与下一个分组的传输冲突。尽管ACK会引入新的开销，但是可以在下一个传输周期保护接收者的接收窗口，并可以通知发送节点路径是否失效（如由于节点移动而收不到ACK），这些功能虽然可以通过交换预约表实现，但是ACK可以提供一种快速的反应机制。
为了实现预约机制，每个节点维护一个RT用于记录其传输范围内任何节点的发送和接收预约窗口。一旦收到实时分组或ACK，节点将从分组头中读出下一个传送时间并将其记录到RT中，每个节点使用RT来防止与正在进行的预约发生冲突。图6给出了图5的网络拓扑中节点1和节点6的预约调度情况。为了便于解释，此处假设采用时隙同步帧，一个时隙可以容纳序列，并且假设CYCLE时间相同，实际上通用算法可以适用于具有不同周期的非时隙情况。图6中给出了节点1和6记录的每个时隙的预约情况。例如对于连接5-1，节点6在第2个时隙既可以收到5到1的数据分组，也可以收到1到5的ACK，于是在该时隙记录{5 tx}和{1 rec}。如果节点6打算向节点1发送数据或建立一个新的连接，它需要检查节点6到节点1的预约表来寻找可行的传输时隙，该时隙需满足在节点6的RT内没有其它节点在此时隙接收(即图6中的时隙1,3,4)，并且在节点1的RT内没有其它节点在此时隙发送(即图6中的时隙3,5,6)，因此可行的时隙为3。可行时隙或可行窗口（在非时隙情况下）的正确选择要求邻居节点周期性地交换RT，同时在邻居节点间发送RT可以用来消除隐终端问题。例如，当节点6从节点2和节点3了解到相应时隙的预约后，可以防止与节点7和8发生冲突。RT的交换可以随路由表的交换一同进行，预约在每个CYCLE进行刷新，如果在连续N个CYCLE得不到刷新则丢弃。
MACA/PR假设链路是对称的双向链路，这样RTS-CTS-PKT-ACK 机制就可以保证相关的邻居节点能够收听到相应的分组来避免冲突，从而使得预约得到承诺。此外，数据报和实时分组可以交织传输，但给予实时分组较高的优先级，数据报分组可以填充一个周期中的空闲窗口或时隙，为了防止实时业务饿死数据报业务，对一个周期可以预约的最大数量加以限制。MACA/PR中，为了发送一个数据报分组或实时会话的第一个分组.，发送节点需要首先检查它的预约表来选择一个空闲的时隙或时间窗口来发送RTS，如果在超时时间到来时仍没有收到相应的CTS，它也使用二进制指数退避算法来选择重传超时时间。当一个新节点加入系统时，它首先需要处于侦听模式一段时间来了解所有当前的预约以及接收其它邻居节点的预约表。
四、QoS路由
网络为了保证QoS，必须实施资源预约和资源控制。路由可以看作是资源预约的第一步，即采用QoS路由算法首先找到满足应用资源要求的路由，而后逐跳地实施资源预约过程。因此，预约请求的成功与否在一定程度上取决于路由算法能否找到合适的路径。考虑到带宽的重要性和简化实现，QoS路由可以只考虑带宽指标，具体是指每个CYCLE内的可用空闲时隙。带宽算法的目标是寻找具有足够带宽的最短路径来支持某个连接。这里采用的是基于无路由环回的DSDV的带宽受限路由算法。带宽路由算法需要跟踪适用于所有带宽值的最短路径，为了得到这些路径，每个节点需要向邻居节点周期性地广播所选路径的到每个目的节点的{带宽，跳距离}信息。为了简单起见，可以只记录两个带宽值：最短路径的带宽和所有可行路径的最大带宽。一个节点接收到一个具有带宽要求的实时分组时需要判断是否存在可行路径，如不存在它将丢弃此分组并且不发送ACK，而源端最终会重新选择路由。
链路带宽信息可以从预约表方便地获得，例如图6中，节点6只能通过一个时隙3向节点1传送数据，于是带宽是一个时隙，在非时隙情况下，带宽是指可用窗口可以容纳的分组数。如果一个链路的带宽不能满足要求，可将其权重设为∞，即不允许新的连接使用该链路直到旧的连接释放部分资源，从而使实时业务可以比较均匀地在网络中分布。在有线网络中，路径的可用带宽是路经上最小的链路带宽，但无线网络中这个结论并不成立。例如图7中，时隙1既可以用于节点1向节点2的传输，又可以用于节点2向节点3的传输，但是在无线网络中，节点2不能在时隙1同时接收和发送分组，（不考虑邻居节点使用正交码字同时进行收发的情况）因此可用的带宽为0而不是1。由于这个特征，无线网络中寻找带宽受限的最短路径是NP完全问题，中提供了一种启发式带宽路由算法用于计算端到端路径的可用带宽。对于数据分组，仍使用无带宽约束的最短路由算法。此外，可以采用备份路由的方法来减少由于拓扑改变而造成连接失效导致的性能下降，因为备份路由的计算不会引入额外的路由和控制信息交换，它们使用相同的路由表计算路由，并且如果主路由无环回，备份路由也无环回。例如图8中，节点首先使用主路由传送分组，如果失效，则使用备份路由作为主路由，同时在构建一条新的备份路由。主路由是具有或不具有带宽限制的最短路径，而备份路由是第一跳链路与主路由的第一跳链路不同的次最短路径。
五、结论
MACA/PR是一种几乎不需同步机制的可以支持实时业务的无线网络结构，它扩展了MACA、MACAW和FAMA中的冲突避免接入机制，同时保持了异步操作的简单性。MACA/PR是完全异步的分组无线电网络（PRNET）和同步的分簇TDMA机制间的较好折衷。相比与分簇TDMA和自适应分簇机制，MACA/PR中的每个中间节点都不需要等待新帧的到来，因此端到端时延较低。但是MACA/PR所能获得的聚集吞吐量小于其它两种机制，因为：MACA/PR中实时分组的传输位置是随机的，而不是严格按时隙放置的，从而会引起较多的带宽碎片；由于使用相同的码字，空间重用率较少，而其它两种机制在不同的簇可以采用不同的码字。正是因为不采用全局同步和码字分割机制，所以减少了系统的总吞吐量，但是简化了实现复杂性和成本。总之，MACA/PR具有较低的时延和分组丢失率，节点能够较公平的共享带宽、可以较好地实施允许控制、适应节点的移动性并具有较好的可扩展性。此外，它不需要同步并且集成了IEEE 802.11标准，因此实现简单，成本低，有广阔的应用前景。
----《中国多媒体视讯》
|
