一种多速率的ap主动队列管理算法

一种多速率的ap主动队列管理算法

1wla网络中的时间公平主动阵列管理随着无线网络技术的成熟，无线网络已融入internet，成为重要的组成部分。由于IEEE802.11等无线技术能让用户方便地接入Internet,这些技术已经被广泛地部署在学校、车站、机场、运动场等信息“热点”地区。其中,WLAN作为目前最成熟的无线网络,已经广泛地运用到日常的生活中。然而,WLAN作为一种新的技术也面临着一些新的问题。目前,WLAN普遍存在无线网络和有线网络的带宽不对称性和流量不对称性。一方面,通常有线网络的带宽大于无线网络的带宽;另一方面,从有线网络向无线网络方向(下行)的数据流量要远大于无线网络向有线网络方向(上行)的数据流量。从而很容易在AP(accesspoint)造成下行流拥塞,就会导致排队延迟加长、大量丢包和吞吐率的下降。在IEEE802.11WLAN中,因为信号衰减以及干扰等原因,无线节点的信号传输质量与其所在位置相关。目前在WLAN中广泛采用自适应速率选择策略(如ARF、RBAR),它能根据特定时间内外界因素来决定无线数据最佳发送速率,这就使得在WLAN中普遍存在不同数据传输速率。而在多速率WLAN中,低速传输的流会占用大量的信道时间,无形中挤占了高速传输流的信道时间,这样不但WLAN总体吞吐率的急剧下降,而且下行高速流的包大部分时间只能在AP排队等待信道变得可用,进一步加剧AP的拥塞。为此,各国学者针对这些问题提出了改进办法,虽然在某些方面也上获得了较好的效果,但仍面临着拥塞导致网络效率低和流之间公平性无法保证等问题。本文在详细分析WLAN网络中拥塞控制和公平性策略的研究成果基础上,提出一种在AP上的时间公平主动队列管理(TFRED,temporalfairRED)算法,既能避免或缓解拥塞,又可以保证各无线节点的时间公平性,提高了网络的整体效率;同时能惩罚恶意的UDP流,保护TCP流的吞吐率。2关于研究现状经过多年的研究发展,针对WLAN出现了大量的改进方法和增强策略。其中,针对拥塞控制和时间公平这2个问题,主要做了以下的研究。2.1通过ap上的严格控制在WLAN中,下行流的数据包和上行TCP流的ACK包都要由AP发送,很容易造成AP缓存的拥塞。如果对AP的缓存实施拥塞控制,就能有效地避免或缓解WLAN的拥塞。在有线网络主动队列管理机制中,各输出流在相同的有线链路上发送,具有相等的发送速率。FDA、RateAdaptiveSnoop和VQ-RED等算法沿用有线网络中公平拥塞控制的思路,在AP上实施拥塞控制,同时保证通过AP的下行流吞吐率公平。FDA算法中,当AP出现下行流拥塞时,由AP向下行TCP的发送端重复发送3次收到的ACK包副本。由于吞吐率较大的TCP流的ACK包到达AP可能性较大,吞吐率较大流降速的可能性也就较高,从而提高各流的吞吐率公平。RateAdaptiveSnoop在AP上将无线信道带宽和AP可用缓存平均分配给各流,用ACK的通告窗口把分配给各流的带宽延时乘积反馈给TCP发送端,保证各流的吞吐率公平。VQ-RED对通过AP的单流运用RED拥塞控制算法,为每流设置相同的丢弃门限,确保每流的吞吐率公平。但实际上在多速率WLAN中,通过AP的下行流虽然共享同一无线信道,但有不同的发送速率。如果在WLAN中保证发送速率不同的单流间吞吐率公平,反而会让慢速发送的流长期占用无线信道,导致网络总体效率低下。因此,在AP上保证吞吐率公平的拥塞控制管理算法完全忽视了目前WLAN中多种速率共存的实际情况,并不适用于目前普遍存在的多速率WLAN。2.2时间公平的mac层协议在多速率无线网络中实现时间公平的核心思想是增加高速信道节点的发送概率,减少低速信道节点的发送概率,目的是保证各节点实现依据其信道速率的比例公平,即保证各节点占有相等长度的无线信道时间。相对于吞吐率公平,虽然会降低慢速信道节点的吞吐率,但由于避免了慢速信道节点占据不公平的信道时间,时间公平的策略保护了快速信道节点的吞吐率,从而提高网络总吞吐率。目前已有保证时间公平的MAC层相关改进协议,这些协议依据各无线节点的信道速率来设置各节点不同竞争窗口大小、帧间的时隙长度和每次发送包的个数等MAC层参数,保证各节点占用相等的无线信道时间。典型的时间公平的MAC层协议包括OAR、Idlesense、802.11e协议改进。但修改MAC层协议需要大范围更新网络设备,因此目前不大可能推广应用。在已有的多速率WLAN的AP队列管理算法中,TTPDE算法在AP拥塞丢包时选择丢弃发送延时最大的包,AP在发送包时选择发送延时最小的包发送。这种极端的方法让快速流尽量长时间占据信道,尽最大可能提高网络效率,但同时有可能造成低速节点长期处于“饿死”状态,完全牺牲公平性。另外,在AP上利用队列调度算法能够保证时间公平,但这些算法并不能解决AP队列的拥塞问题。针对上述问题,本文设计的目标是:对于造成拥塞的下行流,设计一种在AP上的时间公平主动队列管理算法,同时解决拥塞和公平性问题,简单而有效地实现效率和公平性的双赢。3基于时间公平的tranet算法3.1tf监测技术如图1所示,TFRED算法的核心思想是:当下行流在AP发生拥塞时,TFRED算法依据AP的无线信道数据发送速率,以较低的丢包概率随机丢弃高速发送流中的包,以较高的丢包概率随机丢弃低速发送流中的包,将各流队列长度稳定在各自理想的目标值,保证各流占用无线信道时间相等,并能有效避免AP上的拥塞。需要指出的是,发送到各无线节点的包在AP中并不需要真正按流来形成队列,AP只需要统计目前在缓存等待发送到各无线节点的包的个数(各流“虚队列”的长度)。同时为了避免死锁和全局同步,采用了随机丢弃的方法丢弃缓存单流队列中数据包。TFRED算法如图2所示,具体实现过程如下。1)当包到达AP时,被按目的节点分成单流,并且根据每流的无线信道发送速率r计算每流的目标队列长度l。2)根据缓存中聚集流的当前队列长度判断是否拥塞。如果拥塞,计算丢弃概率pdrop,并选择当前队列长度与目标队列长度之差最大的单流,依据丢弃概率pdrop,随机丢弃该单流的一个包,同时不论是否拥塞,将到达包入队。3.2基于tov的策略在TFRED算法中,依据AP的无线信道发送速率来计算各流的目标队列长度。定义1802.11WLAN中,如果忽略传输时延,向节点i发送一个数据包的信道占用时间tchannel由发送时延ttr和控制开销时延tov组成,记为其中,发送延时Sd为发送数据包的大小,ri为AP第i流无线信道发送速率。控制开销延时tov包括节点的随机退避延时和控制帧发送延时。在MAC层采用RTS/CTS机制,在没有数据包碰撞,并且在退避时间服从均匀分布的情况下,退避时间取平均值CWmin×Slot/2。因此,tov可以认为是一个常数。例如,IEEE802.11b标准设置如表1所示,则tov=3×SIFS+定义2假设AP采用先进先出调度算法,AP发送第i流中包的概率pi为其中,li是第i流的当前队列长度,n是当前通过AP的流的数目,是当前聚集流队列的总长度。定义3假设各流的数据包大小相等,第i流的无线信道占用时间Ti为其中,T为所有流占用信道的总时间。由式(2)、式(3)可知,为了使得不同速率的流占用相等的信道时间,AP缓存中每流的队列长度li应与成反比。这样可以计算出第i流目标队列长度为其中,L是AP缓存中聚集流的目标队列长度。依据RED算法的参数,将L设为4总吞吐率对比在多速率WLAN中,吞吐率公平的算法保证各流的吞吐率相等,但会导致慢速流压制了快速流的吞吐率;时间公平的算法保证各流的信道占用时间相等,保护了各单流的吞吐率不会受其他节点影响。下面给出采用吞吐率公平和时间公平算法的网络总吞吐率比较。假设从有线网络向WLAN中各节点分别发送n条流,各流传输的数据包大小都是Sd,AP发送各流数据的速率分别为r1,r2,…,rn。由3.2节中的分析得到每发送一个数据包的吞吐率ti为如果保证时间公平,各流占用的信道时间相等,则时间公平的WLAN总吞吐率为:由式(5)、式(6)可知,当r1=r2=…=rn时,Ttf=Trf。由此可见,如果向各节点发送速率相同,保证各节点时间公平其实就是保证了吞吐率公平。但如果速率存在差异,采用时间公平比吞吐率公平的网络效率高。5基于ap的算法仿真实验为了验证算法的有效性,利用网络仿真软件NS2.27实现了TFRED算法,并与RED、VQ-RED、TTPDE算法进行性能比较。其中,RED作为经典的拥塞控制算法,VQ-RED代表了吞吐率公平算法,TTPDE则是完全牺牲公平追求效率的算法。在仿真实验中,每个移动节点包括AP采用的协议如图3所示。路由协议采用NOAd-HocRouting(NOAH),MAC层采用IEEE802.11b协议。队列位于LL层和MAC层之间。无线信道速率调节算法采用RBAR,信号传播模型采用Ricean衰落信道模型。同时为了降低多路径衰减,将Ricean模型中主径衰落因子设为较大的值256。5.1节点e和ap之间的速率实验1比较了AP采用RED、VQ-RED、TTPDE和TFRED时各无线节点吞吐率,实验的网络拓扑如图4所示。实验场景设置节点A~E到AP的距离分别是:10m、60m、80m、102m和10m。因此各节点和AP之间的速率分别是:11Mbit/s、5.5Mbit/s、2Mbit/s、1Mbit/s和11Mbit/s。模拟实验开始后,节点E以1m/s的速率移动远离AP,这时,节点E和AP之间的速率从11Mbit/s逐步降至5.5Mbit/s、2Mbit/s、1Mbit/s。有线链路带宽都是25Mbit/s,延时为1ms。AP缓存容量为100个包。设置RED、VQ-RED和TFRED算法参数为:wq=0.002,minth=40,maxth=60,maxp=0.1。5.1.1节点间的数据发送速率首先设置5条UDP流1~5,分别从节点1~5到节点A~E。每流带宽为5Mbit/s,数据包大小为1000字节。图5(a)显示当AP使用RED算法时,各节点的吞吐率虽然变化较大,但总体趋势都是随着节点E的移动而下降。从图5(b)可以看出当AP使用VQ-RED算法时,各节点的吞吐率基本相同,都随着节点E的移动而下降。这是由于VQ-RED算法使用较多的较为准确的流状态信息,使各节点获取相同的吞吐率,但结果却反而压制了快速节点的吞吐率。图5(c)显示当AP使用TTPDE算法时,保证了快速节点的吞吐率,但大大压制其他慢速节点的吞吐率。而图5(d)显示当AP使用TFRED算法时,各节点的吞吐率和其数据速率相关。由于TFRED算法考虑了各节点的情况,保证各节点的时间公平,当节点E的数据发送速率下降,而其他静止节点的数据发送速率不变时,TFRED算法能够确保静止节点的吞吐率不会降低。同时节点的数据发送速率下降意味着AP发送到节点E的数据包数减少,从而减小了AP和节点E之间通信控制开销,其他静止节点得到更多的信道资源,提高了静止节点的吞吐率。从图5(e)可以看出TFRED算法相对RED、VQ-RED算法网络总吞吐率平均提升40%,这是由于TFRED算法保护静止节点吞吐率不会下降,从而大大提高网络整体效率。5.1.2般网络接收点设置5条TCP流1~5,分别从节点1~5到节点A~E。节点移动和位置如图4所示,节点E移动,其他节点静止,数据包大小为1000字节。统计在4种算法下5条TCP流的平均吞吐率和网络平均吞吐率如图6所示。尽管TCP流由于在AP的拥塞和信道速率变化而出现抖动,但从图6可以看出,TFRED算法仍然能够使得TCP流的吞吐率依据其发送速率形成“梯度”,保证了网络总吞吐率相对RED和VQ-RED算法的网络总吞吐率较高。TTPDE算法虽然获取了最高的吞吐率,但这完全是以牺牲慢速的TCP吞吐率为代价。5.1.3节点移动场景下实验结果为了比较算法在多种流共存时的性能,设置4条TCP流和1条发送速率为2Mbit/s的UDP流。TCP流1~4分别从节点1~4到节点A~D,UDP流从节点5到节点E,节点移动和位置如图4所示,节点E移动,其他节点静止。实验结果如图7、图8所示。从实验结果看,在UDP流节点移动场景中,由于RED算法无法惩罚非响应的UDP流,导致UDP流压制其他TCP流;VQ-RED算法为了保证各流公平性,牺牲了网络的总体效率,网络总吞吐率最低;TTPDE算法获得的网络总吞吐率是最高的,但慢速TCP流几乎“饿死”;而TFRED算法保证各流的信道时间公平,有效地压制了UDP流,保护了TCP流,同时在TCP流中依据发送速率分配信道占用时间,获得了较好的网络效率。5.2udp流测试实验2用5条UDP流测试采用RED、VQ-RED、TTPDE和TFRED时各无线节点的时间公平性和吞吐率公平性,目的是验证TFRED算法既能保证多速率无线节点的时间公平,又能保证相同速率无线节点吞吐率公平。实验的网络拓扑如图9所示。实验场景设置除了节点A~D到AP的距离都是10m外,其他设置都与实验1的UDP流测试场景相同。实验采用公平性因子对时间公平性和吞吐率公平性进行量化。假设各个无线节点n1,