基于Adhoc网络中跨层优化拥塞控制算法的研究

1、无线自组织网络论文基于Ad hoc网络中跨层优化拥塞控制算法的研究Abstract：Resources of bandwidth is limitied in wireless Ad hoc networkthe transmission of burst data is too much,because of they could cause congestion.In Internet，TCP congestion control algorithms have become important factors to insure network stability.However,the

2、 traditional TCP congestion control algorithms are not adapt to the wireless Ad hoc because of the characteristics of the wireless Ad hoc.Therefore,the reserch of wireless Ad hoc has become a hot topic on the thought of cross-layer.Different from traditional layered-optimization technology,it is not

3、 an optimization method that is only used in a definite layer which is definited by the OSI strcuture,but to make the cooperation between the higher network layers and lower ones to realize the optimization jointly.And the purpose of the optimization is to guarantee the QoS by choosing the optimized

4、 strategies of the transmission and parameters of protocols.Key words: Ad hoc Networks Cross Layer Optimization Congestion Control Algorithms CCOC摘要：无线Ad hoc网络的带宽等资源有限，突发的数据传输任务较多，易于造成网络的拥塞，拥塞控制是解决网络资源在信息交流之间高效公平分配的有效手段。在Internet上，TCP拥塞控制算法已经成为保证网络稳定的重要因素。然而，无线Ad hoc独特的网络特性，使得传统的TCP拥塞控制算法不适合无线Ad hoc

5、网络，因此，基于跨层思想的无线Ad hoc网络拥塞控制成为了研究热点。与传统的分层优化相比，跨层优化的优点在于它不仅仅着重于追求某一层的优化效果，而是能够通过全局考虑来到达各方面性能的折衷，以此来提高网络的整体性能。本文重点对1移动AdHoc网络的跨层优化拥塞控制一文进行了深入研读，并总结了跨层优化的应用，并提出了展望和相关问题。关键词：无线Ad hoc网络 跨层优化 拥塞控制 CCOC方法1、问题描述及跨层优化简介无线Ad hoc网络的通信具有突发性，当通信子网中有太多的分组时，网络性能降低，这种情况就叫拥塞。产生拥塞的本质原因是网络上的用户的总需求大于网络可提供的资源。在无线Ad hoc中

6、，网络上所有的终端共享节点处理能力、缓存空间和无线链路带宽等网络资源。这三者任何一种资源都可能成为潜在的网络瓶颈，从而导致拥塞。随着网络技术的发展，无线Ad hoc面临越来越多的数据传输业务，这些业务都有很大的“弹性”，数据具有突发性，数据率可以在很大的范围内波动，而无线Ad hoc网络的带宽、能量等资源严重受限，突发的、大量的数据易耗尽网络资源，造成拥塞。因此，设计高效的无线Ad hoc拥塞控制机制，充分利用现有的网络资源，迅速完成数据传输，从而节约整个网络的能量消费，提高网络的性能，是目前急需解决的问题之一。TCP协议的拥塞控制算法原来是为有线网络设计的，并获得巨大的成功，从而也被广泛的应

7、用与无线Ad hoc网络，它是目前无线Ad hoc网络进行拥塞控制的主要方法。然而，与有线网络相比，无线Ad hoc网络的链路带宽与MAC协议、网络参数相关，网络拓扑变化较快，且缺乏中心单元，因此拥塞控制极为困难。而对TCP在Ad hoc网络中性能下降的原因分析，传统TCP拥塞控制机制采用了以下几种机制：慢启动机制：当拥塞窗口小于慢启动门限窗口时，采用慢启动机制，用于探测网络的可用带宽，每个数据包被确认（ACK）后，拥塞窗口就加1。拥塞避免机制：当拥塞窗口大于门限窗口ssthresh 时，采用拥塞避免机制，避免可能发生的拥塞，并尽可能地探测可用带宽，使用加性增加、乘性减小(AIMD)的方式来改

8、变拥塞窗口的大小。快速重传快速恢复机制：当源端收到重复ACK(DupACK)时,采用快速重传机制重发DupACK 指示的数据包并快速恢复机制对拥塞窗口和ssthresh 重新赋值,避免进入慢启动阶段。超时重传机制：在源端发送数据包的同时,启动重传定时器(retransmission timer)。如果源端在定时器超时之前还没有收到ACK,则认为该数据段已经丢失并将进行重传,使用指数RTO(retransmission timeout)退避算法,并进入慢启动阶段。而传统的TCP应用到Ad hoc中网络中是不合适的，主要体现在高误码率、信道接入的不公平性、节点移动等问题，而TCP拥塞控制机制在Ad

9、 hoc网络性能严重下降的根源有两类：一类是Ad hoc网络的特点所致，包括：（1）无线链路的高误码率导致数据包丢失；（2）信道的不公平接入导致数据包丢失和虚假链路失效；（3）节点移动引起的“路由失效”而导致的数据包丢失、乱序和频繁的路由切换；（4）不对称路径导致的ACK 累积。另外一类是TCP拥塞控制机制的本身特性所致，包括：（5）基于数据包丢失的拥塞指示；（6） 慢启动；（7）AIMD；（8）基于窗口的传输；（9）对ACK 的依赖。跨层优化是网络各层将网络信息与其它层共享，并不是完全否定传统网络的分层系统体系结构，而是模糊层与层之间的界限并增加新的非相邻层之间的接口，将网络性能的参数共享。

10、并且针对各层相关模块/协议的不同状态和要求，在整体框架内，利用层与层之间的相互依赖和影响，对网络性能进行整体优化。可参考如下图：图1、Ad hoc网络跨层优化思想跨层设计在无线Ad hoc网络中最主要的优势是通过使用层间信息交互，不同的层之间可以实时的共享网络信息。不相邻的层之间信息的交互很大程度上减少了网络节点的通信和处理数据的开销，提高了网络的性能。相比传统的有限网络，无线Ad hoc网络采用跨层设计，使得层间的信息交互变得复杂，层之间需要识别的层间接口变多，不容易实现。但是跨层实际所带来的好处远大于这些弊端。2、现有的几种跨层设计控制拥塞的方法2.1、2对基于速率的拥塞控制算法（Equa

11、tion-Based Congestion Control，下简称EBCC）的改进在无线Ad hoc网络中，发送端传输层发送数据，当发送点发送的数据发生超市或者发送节点连续接到3个或以上的相同ACK时，传输层通过跨层的机制，向跨层接口中取数据RTT1和p的值，RTT1和p的值计算如下：其中，表示数据帧传输所用的时间，n为多跳网络的跳数，为ACK确认信息传输所消耗的时间。为第n次分组丢失的概率；是数据第n次丢失事件的加权平均，是估计权重，表示的是最近L次的分组丢失事件的时间间隔。在得到参数RTT1和p条件下，传输层计算参数R，R=(RTT1+RTT2)，RTT2是传输层以时间戳的形式得到的往返时

12、间，通过计算得到传输层此时的发送速率，并以此发送速率发送数据，发送完数据后，网络进入TCP拥塞控制的快速恢复的阶段继续发送数据，到此改进的EBCC算法结束，直到发送节点发送的数据再次发生超过或者发送节点连续接到3个或以上的相同ACK时触发此EBCC算法执行。具体流程如图：图2、改进EBCC算法流程图在该算法中，发送速率的参数往返时间R的取值并没有考虑链路竞争，在无线Ad hoc中，单跳网络R是通过MAC层的延时计算出来的，此处将多跳网络分解成n个单跳网络估计出来的，并不准确。发送速率参数分组丢失p值的选取，在有线网络中取样空间过大并不适合无线网络的特性，而且无线网络中确认信息ACK同样很容易丢

13、失，该改进算法中p取值可根据ACK重复数量来计算。将MAC层计算得到的参数R值和p值，通过跨层信息共享的方法传递给TCP层的发送速率，从而到达对拥塞的控制。2.2、3基于多Agent强化学习的Ad hoc网络跨层优化拥塞控制策略 该文主要研究在带宽受限的Ad hoc 网络中，节点之间如何通过博弈学习而实现最佳的数据分流。通过对节点自私性和网络拥塞的关系进行建模，在随机博弈的框架下，将强化学习与对策论相结合，使节点(也称为agent)通过对各种对策形势的学习自动掌握如何在不削弱整体网络性能的同时增加自己的性能。WOLF-PHC(Win-Or-Lose-Fast Policy Hill Climb

14、ing)算法1将“赢否则就要学得更快”策略扩展到PHC的学习策略中，从而既满足单个个体的理性又满足整体的收敛性。该文基于最佳响应多agent 强化学习方法中的WOLF-PHC 算法使节点通过非协同不完全信息下的博弈找到最佳分流点。该文提出一种基于WOLF-PHC 的跨层分流拥塞控制机制(Wolf-PHC based Cross-layer Split-flowcongestion control，WCS)。WCS的主要机理是：由于节点的自私性，从而造成非干扰区域网络的拥塞；当选择一个非干扰区域内的“去耦”分流节点，节点之间采取合作的方式能够大大缓解非干扰区域的网络拥塞。在路由层中选择一对去耦合

15、节点作为转发节点，同时在MAC 层对源节点的发送数据进行分流，从而提高链路的空间重用率。其中，拥塞的提前预测，非干扰区域“去耦”节点的选择以及节点之间最佳分流概率的实现是WCS 的关键。该文主要研究节点是如何通过博弈学习来找到最佳的分流概率点。图3、不同节点数对吞吐量提高的影响该文采用随机博弈框架对节点自私性和网络拥塞的关系进行建模，并证明了存在纳什均衡点。提出了一种基于WOLF-PHC的拥塞跨层分流控制机制(WCS)，主要解决节点之间如何通过博弈学习来找到最佳的分流概率点。并仿真验证了：WCS 在不需要任何额外带宽开销的情况下，能够使各个节点通过博弈学习达到最佳分流点。3、1移动AdHoc网

16、络的跨层优化拥塞控制一文中提出的CCOC算法该文运用跨层设计对拥塞控制协议进行优化设计,充分考虑物理层、MAC 层、网络层、传输层对拥塞控制的影响,以解决:虚假链路失效；数据包乱序和频繁路由切换；ACK 依赖等问题。具体说,采用了如下几种策略:(1) 提高MAC 接入的公平性；(2) 检测虚假链路失效；(3) 增强路由稳定性；(4) 实施网络层反馈机制和探测包机制实现快速启动；(5) 运用SACK 实现可靠传输。图4、CCOC 的跨层设计框架3.1、CCOC方案具体思想3.1.1、提高MAC接入的公平性在IEEE 802.11 DCF 中，节点在竞争信道时,如果信道忙，不能立即发送，则节点需要

17、在0,2iCWmin,i=1,2,7 之间进行随机延迟，其中，CWmin 是最小竞争窗口，i 是发送尝试失败次数.这种方法导致了竞争中失败的节点在下次竞争信道时处于更加不利的地位，从而导致信道接入的不公平性。针对IEEE 802.11 DCF 的这种不公平性，利用链路的拥塞价格(拥塞价格的具体意义和计算方法参见文献23)来提高其接入的公平性。具体做法是:当节点的下行链路的拥塞价格大于等于拥塞价格的门限CP_threshold 时，采用0,CWmin1,1 之间进行随机延迟，让竞争中失败的节点引入较小的随机时延，使其处于竞争有利的地位，增大接入信道的概率，缓解信道接入的不公平性，从而减少出现虚假

18、链路失效问题的可能性。3.1.2、检测虚假链路失效该文采用了以下方法来检测虚假链路。一旦发送节点的路由协议收到来自MAC 层的链路失效报告，就触发向对应的接收节点发送HELLO消息，同时启动计数器，其初始值为Chello。每向接收节点发送HELLO消息1次，计数器的值就减1。如果在Chello=0 之前未收到来自接收节点对该HELLO消息的应答，则判定链路失效是真实的,并立即触发节点启动本地路由修复方案。如果本地路由修复方案不成功，则向源端发送路由失效消息。如果定时器在超时前收到来自接收节点对HELLO 消息的应答，则复位定时器,判定链路失效是虚假的。3.1.3、增强路由稳定性有效设计拥塞控制

19、的最大难点在于Ad Hoc 网络系统的动态性.Ad Hoc 网络中节点的自主移动导致网络拓扑结构的时变，导致频繁的路由失效和路由重构过程，在这过程中，源端将停止数据包的发送，严重影响了网络性能。而且路由重构后，在旧路由上迭代得到的发送速率不再适合新路由。如果在新路由上继续使用此发送速率来发送信息，则要么形成拥塞，要么就是没有充分利用允许的带宽。因此，增强路由的稳定性对拥塞控制的有效实施非常重要。为此，该文通过监测接收信号的信噪比SIR 来预测判断链路的稳定程度，并在链路断开之前尽可能地通过本地路由恢复机制来更新路由以减少路由切换的频繁发生，提高对节点移动和通信中断的抵抗力。3.1.4、实施网络

20、层反馈机制和探测包机制实现快速启动尽管通过增强路由稳定性减少了节点移动导致路由中断的频繁程度，但是，如果路由本地修复不成功，则链路中断处的发送节点就启动网络层反馈机制。即一旦某一中间节点检测到下一跳节点移出它的发送范围(表明路由失效)时，便向源端发送路由失效通知RFN(route failure notification)数据包。沿途的其他中间节点接收到该RFN 数据包后，便令该路由无效。如果它有另外一条可到达目的节点的路由，则对其进行更新，并丢弃RFN数据包；否则，将其继续向源端转发。一旦源端接收到此RFN 消息，则立刻停止发送后续数据包。因为重发的数据仍会因为无法路由而被抛弃，这会浪费网络

21、资源。源端立即开始通过周期性地向接收端发送“探测包”来探测路由是否已经重建，每次发送的方式是一对“探测包”被连续(没有被其他数据包隔开)发送。需要指出的是，“探测包”和普通数据包有相同的包头格式，除了两个域的内容有差别:通过FLAG域置为1 来标识它是“探测包”。中间节点收到“探测包”不需要像处理数据包一样修改拥塞价格域的值，接收端接收“探测包”需要记录其到达时间。假设一对“探测包”的前一个到达接收端的时间是t1，后一个为t2，“探测包”大小为L，则此路由的带宽被估计为BW=L/t2t1.这个值会被接收端反馈给源端，源端就以这个值作为初始发送速率开始重新发送数据，从而实现了快启动。这种快启动方

22、式在连接初始阶段和路由切换时都可以采用，通过探测包机制及时反馈得到的网络速率估计，可以使该连接很快达到其所允许的速率，解决了TCP 采用“慢启动”策略导致的网络资源利用率低下的问题。3.1.5、运用SACK实现可靠传输因为CCOC 不是基于数据包丢失来推断网络是否拥塞的，因此，源端只需要来自接收端关于哪些数据包丢失了需要重传的报告，无需正确判断其原因是因网络拥塞还是路由故障，或者是误码率高造成的。为了避免像在TCP 中依赖ACK 的自定时减少数据包的信道接入机会那样，可靠性机制采用了选择性确认(SACK)。这样，一个SACK 包就可以报告多个数据包接收正确与否的情况。因此，接收端只要实施粗粒度

23、的反馈就可以实现可靠性报告。3.2、CCOC的协议体系结构3.2.1、CCOC数据包头格式每个数据包都携带了一个数据包头，其格式如下图所示，由下列域构成:源端口、目的端口、顺序号、拥塞度量、标志位FLAG。除了拥塞度量和FLAG以外，其他项与TCP的数据包格式类似。拥塞度量用于携带中间节点拥塞价格信息。源端将其设置为0，中间节点对每个经过的数据包根据输出接口队列长度，调整每个数据流的拥塞价格值。可见，拥塞度量是捎带在数据包中的。通过FLAG 域来区分数据包和探测包。 图5、数据包的头格式 图6、SACK反馈包的头格式3.2.2、CCOC的工作过程源端实施快启动方案与接收端建立连接,取得发送速率

24、的初始值。源端在发送数据包时，在其数据包头设置拥塞度量为0，中间节点则对每个经过的数据包的拥塞度量累加上相应的链路拥塞价格。SACK 包通过数据包头的拥塞度量反馈给源端，源端据此调整新一轮的发送速率。循环往复，直到路由切换后重新进入快启动。3.2.3、CCOC的中间节点在CCOC中，中间节点的主要功能是实现拥塞价格的计算、收集和修改。此外，还实现了以下功能:(1) 提高MAC 接入的公平性；(2) 检测虚假链路失效；(3) 构建稳定的路由；(4) 实施网络层反馈机制。为了实现这些功能，中间节点是跨越了物理层到网络层，具体如下图所示。图7、中间节点的功能示意图3.2.4、CCOC的源端和接收端在

25、CCOC 中，源端主要实现快启动、拥塞控制和可靠性控制功能。快启动的实施是在连接的初始阶段和路由切换后重新开始传输阶段，其拥塞控制的实现是根据接收端反馈的路径上的中间节点提供的拥塞度量信息。考虑到尽可能降低反馈通道上的通信量。接收端摒弃了每数据包确认方式，而是采用SACK确认方式。接收端实施周期性反馈以辅助源端实现拥塞控制和可靠性控制，确保每个数据包被准确接收。此外，它也为每个连接记录了前一时刻的拥塞度量值。为了周期性地反馈实施，接收端需要一个定时器，定时器的值在连接或者路由变化后开始的前n 次是等于一个RTT 时间，让拥塞控制尽快地收敛到网络的最优解。此后，接收端在可跟踪网络动态特性的情况下

26、，尽可能少地反馈SACK。对每个属于同一连接的数据包，根据所携带的拥塞度量值来判断是否成立？是指第n 时刻从源段s 出发的信息流到达接收端所携带的拥塞度量总和。如果其相对变化小于预定的取值，即，则这个RTT 就不实施反馈给源端，以尽量降低反馈通道上的通信量；如果不成立，则实施反馈给源端。在本文的仿真中，设置n 为20,为0.05。3.3、仿真验证该文用NS2 仿真平台来比较CCOC 和TCP-Reno,ATCP的性能。仿真环境如下:各节点使用全向天线，无线传播模型采用TwoWayGround 模型。信道传输速率为2Mbps。MAC 协议按前述修改的IEEE 802.11 协议，有效传输距离为2

27、50m,侦听距离为550m;路由采用按第2 节所述修改的AODV协议;每个节点的缓存大小为50。数据包大小等于1 000byte，传输的业务为FTP 数据。所有仿真实验的运行时间都为200s。本文采用的公平性指数(fairness index,简称FI)定义为其中，Ti 是第i 个信息流的吞吐量，n 是信息流总数。FI 的取值越接近于1，则信息流之间的公平性越高。网络拓扑采用100 个节点形成一个10×10 的网格拓扑结构，两个相邻节点之间的距离设置为200m。在此网格拓扑上随机生成4,6,8,10 个信息流。这些信息流在每个仿真中持续连接200s。该文重复了10 次仿真，得到了图8

28、 显示的关于CCOC，TCP-Reno 和ATCP 在4,6,8,10 个信息流的网络场景下的平均公平性指数。进一步地，图9 显示了6 个信息流的网络场景下的瞬时公平性指数，从图8 和图9 可以看出,CCOC 比TCP-Reno 和ATCP 能更好地达到短期和长远公平性。在TCP 中，公平性的问题主要是由于过度的链路竞争。由此产生了虚假链路失效导致某些TCP流被饿死。而CCOC 利用链路的拥塞价格来提高MAC 层接入的公平性。此外，CCOC 能够快速侦测并恢复虚假链接失效，因此能够取得更高的FI。图8、网络拓扑在多种信息流数下的公平性指示 图9、网络拓扑瞬时公平性指数（信息流数为6）4、总结本

29、文通过对无线Ad hoc网络跨层优化拥塞控制的学习，阅读了大量相关论文，做了大量调研工作，对跨层优化拥塞控制有了整体的了解和深入的认识。本文选取了近几年有代表性、效果较好的跨层优化拥塞控制算法进行详细讲解和学习，重点研读了1 移动Ad hoc网络的跨层优化拥塞控制一文，并进行了相关算法的仿真和学习。NS2仿真实验结果表明，PCA 和PCA+AOS 在网络性能上比TCP 和ATCP 有了明显的改进6。CCOC 又取得了优于PCA 和PCA+AOS 的5%10%左右的性能提高。本文先对Ad hoc网络面临的拥塞问题进行论述，指出由于无线Ad hoc网络的独特性质所具有区别于有线网络的拥塞问题，介绍

30、了跨层优化拥塞控制的基本思想，又选取了近几年有代表性的优化算法进行讲解，最后详述了1文中的算法并提出了自己的看法。Reference：1 Bowling M and Veloso M. Rational and convergent learning in stochastic gamesC. Proceedings of the Seventeenth International Joint Conference on Artificial elligence,Washington, 2001: 1021-1026.2 Jorjeta G. Jetcheva,Yih-Chun Hu,A Simple Protocol for Multicast and Broadcast in Mobile Ad Hoc Networks,IETF MANET Working Group,INTERNET-DRAFT