一种新的区分接入算法及其理论分析*

何晓鸿(武汉交通职业学院,湖北 武汉 430065)

一种新的区分接入算法及其理论分析*

何晓鸿
(武汉交通职业学院,湖北 武汉 430065)

文章基于IEEE802.11e EDCA接入机制,提出一种区分接入算法。不同优先级的业务,使用自适应的、不同次数的RTS请求,可增强高优先级业务成功接入的概率;针对高优先级业务之间同时接入的竞争状况,提出了避让策略,以降低高优先级业务之间的碰撞。文章对该算法在马尔科夫链建模的基础上进行理论分析,证明其能够优化高优先级数据流的接入成功率,提高高优先级数据流的饱和吞吐量。

区分接入算法;服务质量;接入控制;马尔科夫链

随着网络内容的不断丰富,业务对网络的QoS保证要求也越来越高,但无线Mesh网的不确定因素使其QoS问题非常复杂,这必然要求无线Mesh网络MAC层具有业务区分能力,能够为不同等级的业务提供不同的优先级保障。

IEEE802.11e的EDCA定义了背景数据尽力而为、视频、音频四种接入类,并且分别定义了彼此不同的AIFS仲裁帧间间隔、CWmaxCWmin最大及最小竞争窗口,以保证对不同的接入类提供不同的QoS。然而,它只是一种概率优先机制,并不能消除优先级较低的数据流对优先级较高的数据流的影响。

基于公平,改善高优先级数据的传输效率,学者们在MAC层做了大量的研究。文献[1][2]用分级的微时隙间的竞争使高优先级数据拥有高接入率。文献[3][4]调整信道占用的决策方式,降低冲突概率,从而提高数据信道的吞吐量。但以上解决方案都要求网络严格同步,这在Mesh结构的无线网络中是很困难的。文献[5]根据业务的不同等级定义了一个含有不同时隙数的超时隙,且退避以超时隙作为单位。以提高高优先级数据流的传输机会,不过当高等级业务比较多的时候,反而会降低高等级业务的吞吐量。

1 区分接入算法

本文从提高高优先级数据接入信道的成功率,减少接入失败导致的等待延迟,降低等待时间出发,基于IEEE802.11e的EDCF接入方式,提出了一种新的算法,该算法可以在高低优先级数据流的状况之下,改善高优先级数据流的接入成功率。

本文在EDCF的接入时序上做了调整:针对不同的业务优先级,用差异性的间隔和重试次数来发送RTS帧,有助于较高等级的业务成功抢占信道。图1为改进的接入时序。如图1所示,高优先级的数据RTS帧成功预约信道,接收方回应CTS帧,发送方一旦收到CTS帧,立即进行数据发送;如预约失败,则等待UIFS=SIFS+σ× slottime,σ∈(0,1,2)间隔,发送RTS请求帧,σ随机取0,1,2,如成功,接收方发送CTS帧,发送方收到以后则发送数据;如失败进入退避。对中等优先级业务,当信道预约成功时,获取发送机会;但如果RTS预约失败,则可以等待MIFS=SIFS +3×slottime间隔,发送RTS请求帧,预约成功数据流则发送,失败则开始退避过程。对低优先级业务,则没有再次预约的机会,RTS帧如果发生了碰撞,预约失败的话,将直接进入退避过程。

图1 区分接入算法机制接入时序

区分接入算法对于非低优先级数据在第一次发送RTS帧的时候,如预约失败将第二次发送RTS请求数据帧,从而加大预约成功的概率。而低优先级数据只能发送一次请求,如果预约失败将会进行退避。另外,高优先级数据流和中等优先级的数据流在第一次预约失败的情况下,第二次发送RTS帧的发送间隔也是不同的。确保了高优先级数据预约成功的概率。文献[6]也提出了一种RTS帧多次预约的算法,它在高优先级数据进行信道预约时,使用了背靠背的多个RTS帧,这种做法导致在首次预约成功后,也会连续地传送多个RTS帧,这无庸置疑浪费了信道带宽。而本算法在信道预约成功时,将不重复发送RTS帧,自然降低了不需要的控制帧在带宽上的消耗。而且一旦高优先级数据帧和低优先级数据帧产生冲突时,优先级较高的数据流可以通过第二次的RTS请求帧抢占信道,从而降低了因为较低优先级数据流的存在而产生的碰撞,同时优先级较低的数据流因为发送失败,会加大退避的窗口,发送概率则会进一步降低,优先级较高的数据流获取发送机会的概率则会更大。此外,由于高优先级数据再次发送RTS帧的间隔是随机调整的,这样也相应降低了多个高优先级数据流在同一时间同时接入信道而产生的碰撞。

综上所述,本文提出的区分接入算法能够降低优先级较低的数据流对优先级较高的数据流的影响,进而加大对高优先级数据业务服务质量的保障。

2 理论建模及分析

假设同一冲突域的无线Mesh网络中包含相互独立且共享信道的n个节点,则单个节点的信道竞争过程分析如下,若k(t)作为其在时刻t的退避等级,取值范围在[0,m]内;v(t)表示在时刻t,该节点的退避时隙计数器的取值,取值范围在[0,Wi-1]内,其中Wi=2iW0,W0=CWmin,i∈[0, m]为该节点退避等级。则k(t)和v(t)分别是一个随机过程,本文把此两随机过程看成一个整体,用二维的随机过程{k(t),v(t)}来表述此站点的竞争信道过程。

设数据帧的碰撞概率p彼此独立且固定。二维随机过程在t+1时刻的状况{k(t+1),v(t+ 1)}只与前的一个时刻状态{k(t),v(t)}相关,且状态、时间皆为离散,那么随机过程{k(t),v(t)}为二维Markov链。此外,在进行退避过程中,各节点信道为空闲,则用一样的概率来减少退避计数值。如图2所示。

公式(2)表明在退避的过程中,计数器在每个时隙减1;公式(3)表明在i为退避级数的时候,如果发送失败,退避等级加1,退避计数器的值随机的从[0,Wi+1-1]中取值;公式(4)表明,如果退避级数已达最大值,发送失败后,退避等级不发生变化;公式(5)表明,发送成功后,退避等级回到最小值0。

如公式(6)所示:

从图2所示的Markov模型能够得到在稳态下各个状态之间的关系:

对任意的j∈[0,Wi-1]

全部vi,j都能够用v0,0和p来表示,且=1,所以

因为当退避计时器减到零时,站点即发送数据包。所以节点在发送数据的概率是

设最小竞争窗口 W1为高优先级的窗口值,最小竞争窗口 W2为中等优先级的窗口值,最小竞争窗口W3为中等优先级的窗口值,那么,高优先级发送数据的概率r1,中等优先级发送数据的概率r2,低优先级发送数据的概率r3分别为:

p1、p2、p3依次是数据流发送时高优先级、中等优先级以及低优先级的碰撞概率。n1、n2、n3分别是高优先级的节点数目、中等优先级的节点数目和低优先级的节点数目。则对于本文算法的接入流程有:

所有站点竞争信道的过程中任意时隙内,至少有一个站点发送数据也就是信道忙的概率为:

ps1、ps2、ps3分别为高中低优先级数据流发送成功的概率,ps11、ps22分别为在无碰撞情况下,且无更高级数据流发送时,高中优先级数据流成功发送的概率,ps12、ps13分别为高优先级数据流与中、低等优先级数据流发生碰撞的状况下的发帧成功的概率, ps23为在没有高优先级数据发送的条件之下,中等优先级与低优先级数据流发生碰撞时,中等优先级成功发送的概率。pc1、pc2、pc3分别为在没有更高优先级数据流发送时,高、中、低优先级数据流和同等优先级之间发生碰撞且发送成功的概率。pc11、pc12分别表示高优先级数据流之间发生了碰撞,但发送成功的概率和发送失败的概率。bs11、bs12、bs13、bs22、bs23、bs3、bc11、bc12、bc2和bc3对应着其占用信道的时长:

从上面的分析,高优先级数据流、中等优先级数据流、低优先级数据流的饱和吞吐量分别为公式(36)、(37)、(38):

θ为单个空时隙的持续时间,E[data]为传送的平均净荷时间。作为IEEE802.11e EDCF的机制,高优先级数据流的发送成功概率,会被较低优先级的数据流影响,可是,本文提出的算法理论上,从公式(14)、(15)(16)中可以看出,发送数据帧时,因为碰撞导致失败的概率只会被高优先级的数据流所影响。此外,公式(18)、(19)、(20)中可以看出,在不同优先级数据流的站点数和发帧概率一样时,较高优先级的数据流发送数据的成功概率要高于较低优先级数据流。进而,公式(36)、(37)、(38)能够得到,较高优先级的饱和吞吐量也要比较低优先级数据流要高。

3 结论

本文基于IEEE802.11e EDCA接入机制,提出了一种新的区分接入算法。该算法对优先级不同的业务,使用自适应的、变次数的RTS请求,加强了高优先级数据流的成功接入概率。此外,对于高优先级业务同时接入的而发生竞争的状况,提出了相应的避让策略,减轻了高优先级业务之间的碰撞。而后,本文对该算法在马尔科夫链建模的基础上,进行了理论分析,证明了其能够优化高优先级数据流的接入成功率,提高高优先级数据流的饱和吞吐量。

[1]Jiang Sehngming,He Dajiang,Ling Xinhua,et a1.A Simple Distributed PRMA for MANETs[J].IEEE Transactions on Vehicular Technology,2002,(3): 293-305.

[2]You T,Yeh C-H,Hassanein HS.A New Class of Collision-free MAC Protocols for Ad Hoc Wireless Networks[A].Proceedings of the Eighth IEEE International Symposium on Computers and Communication(ISCC'03)[C].2003:843-848.

[3]Tantra J W.Chuan Heng Foh.Achieving near maximum throughput in IEEE802.11 WLANs with contention tone[J].IEEE Communications Letters, 2006,(9):658-660.

[4]Yang Xue,Vaidya Nitin H.A Wireless MAC Protocol Using Implicit Pipelining[J].IEEE Transactions on Mobile Computing,2006,(3):258-273.

[5]康凯,胡海波,林孝康.一种新的用于IEEE 802. 11e EDCA中提供QoS的方法[J].电子与信息学报,2007,(12):2991-2995.

[6]王朝翔,韦蓉,丁炜.带拥塞控制的多预约MAC协议[J].电子科技大学学报,2008,(5):765-768.

10.3969/j.issn.1672-9846.2014.01.018

TN929.5

A

1672-9846(2014)01-0074-04

2014-01-07

何晓鸿(1976-),女,湖北汉川人,武汉交通职业学院电子与信息工程学院教师,主要从事电子与信息工程研究。