论文部分内容阅读
摘要：针对无线ad hoc网络不能提供数据流优先级区分的问题，本文提出了一种基于802.11 DCF退避算法的改进机制，该机制通过设置不同的MAC层最小竞争窗口来实现数据流的区分服务，使发送高优先级数据流（如实时数据流）的节点更容易连接信道，从而使高优先级数据流占有更多带宽资源。数学分析表明，该策略能有效的提高高优先级数据流的传输性能。
关键词：802.11DCF; 区分服务; 马尔科夫链模型; 性能分析
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)35-2120-03
Service Differentiation Scheme Based on Minimum Contention Windows for IEEE 802.11 WLAN
WU Zhi-qiang, ZHU Hong-li
(Henan Polytechnic University, Jiaozuo 454000, China)
Abstract: Considering that IEEE 802.11 ad hoc networks can not provide any priority scheme, this paper proposes a new scheme based on the 802.11 DCF back-off algorithm. The algorithm, by setting different number of Minimum Contention Windows at the data link layer, can make high-priority data flow(such as Real-time data flow) access channel more easily. As a result, the high-priority data flow can obtain more bandwidth. Our mathematical analyses demonstrate that the new algorithm improve the transmission performance of data flows in high priority significantly.
Key words: 802.11DCF; diffserv; markov chain model; performance analysis
1 引言
无线ad hoc网络是一种无固定控制中心、多跳、对等式网络，它不需要任何额外的架构设备，只需要接点配以无线收发装置即可随时组成无线局域网络。这种网络实现简单、灵活、不需要昂贵的基础设施、成本低，所以在军事通信和民用通信领域得到了广泛的应用。但ad hoc网络并不能提供业务的区分，难以满足那些对QoS有严格要求的业务（如实时流媒体业务）的传输要求。
目前，对于在ad hoc网络中提高实时业务的服务质量研究大多集中于MAC层，大部分研究者提出的支持QoS的MAC协议大多建立在IEEE802.11 DCF[1]机制上。其中的QoS增强机制主要集中在修改退避算法、帧间间隔、最大退避次数、最大帧长度等方面[2-7]。本文主要研究通过减小高优先级数据流的MAC层最小竞争窗口值来实现业务的区分服务，并利用相关数学模型对修改后的退避算法进行分析。分析结果表明，该策略能使高优先级数据流占用相对较多的带宽，从而提高高优先级数据流的传输性能。
本文第2节简要介绍IEEE 802.11 DCF退避机制；第3节则利用相关数学模型深入分析本文建立的区分服务机制；第4节对区分服务模型的性能进行分析和评价；第5节总结全文。
2 802.11 DCF描述
802.11DCF机制定义了两种信道接入机制，即基本接入机制和RTS/CTS机制。在基本接入方式下，一个节点在发送数据分组之前要监听信道，如果信道空闲超过一个分布式帧间间隔(DIFS)，该节点就启动一个退避过程，DIFS之后的时间被划分成一个个的时隙（time slot,记为σ），当信道空闲时间每超过一个时隙时间σ，计数器的值就减1。若探测到信道忙（有分组传输或者分组冲突）则退避计数器冻结，当再次探测到信道空闲超过一个分布式帧间间隔(DIFS)时计数器再次激活，当计数器的值到达0 时节点开始发送数据分组。如果数据分组传输失败，则启动一个指数退避过程。每个分组传输需要后退的时隙数目从区间（0,W-1）中均匀选取，W称为竞争窗口，m为最大退避次数。每次开始传输一个新的分组时，竞争窗口被设置成最小竞争窗口，记为CWmin。此后每次传输失败，竞争窗口加倍，直到达到一个最大值CWmax。若数据分组被成功接收，目的节点需要回复一个确认分组（ACK）。
在RTS/CTS接入方式下，节点遵循相同的指数退避机制，只是当退避计数器的值为0时发送方不是直接发送数据分组，而是发送一个称为RTS的短分组，目的节点收到RTS分组后需要回复一个CTS分组，发送方接收到CTS分组后方可开始发送数据分组。特别是当数据分组很大的情况下RTS/CTS接入方式明显优于基本接入方式，因为它减小了竞争阶段用于检测信道状况的帧长度。在理想信道的情况下，仅仅当两个或两个以上的数据分组尝试在同一个时隙的起始点发送时会导致冲突，当两个发送节点都采用RTS/CTS机制时，冲突仅仅会发生在RTS分组，发送方因收不到CTS分组而得知有冲突的发生。
3 区分服务机制的数学建模分析
本文参考了文献[8,9]中所用的方法，对本文提出的区分服务机制进行了数学建模分析，并通过相关模型得出了两种优先级数据流的饱和吞吐量、以及总体饱和吞吐量的计算方法。
3.1 马尔科夫链分析模型
在本文中，我们将网络中的数据流分为两种，一种为对时延敏感的数据流，我们简称RT（Real-Time）流；另一种为对时延不敏感的数据流，我们简称BF（Best-Effort）流。显然RT流对QoS的要求高于BF流。因此本文设置RT流为高优先级数据流，而BF流为低优先级数据流。
为便于分析，定义i为数据流的优先级类别，取值为0或1，其中0表示高优先级的RT流，1代表低优先级的BF流。两种数据流的分组都采用相同的退避机制竞争信道，因此两种数据流的竞争窗口值可用公式(1)计算。
(1)
其中Wi,0为数据流i的最小竞争窗口值，CWi,max为数据流i的最大竞争窗口值，j为退避计数器的退避阶段，m为最大退避次数，L为MAC层的最大重传次数，这里我们设置W0,0 该文参考文献[8]和[9]中所用的方法，对改进后的退避算法作如下建模分析。我们假设：
1) 网络中每个节点只发送一类数据分组，并且每一类数据分组在传输过程产生冲突的概率恒定且独立。
2) 信道是理想的，即分组丢失只会是由冲突造成的。
3) 系统处于饱和状态，每个节点在成功进行一次分组发射后，立即监听信道，待其退避计数器退至0时马上发送下一分组。
对于传输第i类数据分组的节点，设B(i,t)表示其在时刻t的退避计数器值，S(i,t) 表示其在时刻t的退避阶段。根据文献[8]和[9]，{S(i,t), B(i,t)}构成了一个离散的二维马尔科夫链模型。令pi为属于数据流i的数据分组发送时产生冲突的概率，pi,b表示属于数据流i的数据分组在退避阶段检测到信道忙的概率。则其单步状态转移概率如下（我们简记）： (2)
记为马尔科夫链的稳态概率分布，由马尔科夫链的相关性质可以得到如下关系：
(3)
(4)
(5)
(6)
定义τi为发送第i类数据分组的节点在一个随机选择的时隙中发送分组（RTS或Data）的概率。因为节点发送分组只会在退避计数器的值为0时才发送，所以有：
(7)
设发送属于数据流i的数据分组的节点为ni个，pi,b表示发送属于数据流i的数据分组的节点在退避阶段检测到信道忙的概率。在本模型中，信道忙只会在有数据分组成功发送或者是发生分组冲突的情况下发生。因此，pi,b也可以理解为在上一个时隙内余下的（n0+n1-1）个节点中至少有一个节点发送了分组。由此，我们可以得出：
(8)
(9)
pi表示属于数据流i的数据分组发送时产生冲突的概率。在本模型中，分组发生冲突只会是剩余的(n0+n1-1)个节点中至少有一个节点也在同一时隙内发送了分组。因此，可以有以下结论：
(10)
(11)
在节点数量、最小竞争窗口、最大退避次数、MAC层最大重传次数等参数已知的情况下，可以由公式（6-11）计算出p0、p1、p0,b、p1,b的值，并且有唯一值。
3.2 饱和吞吐量分析
设Ptr为在一个随机选择的时隙内网络中至少有一次分组发送的概率；Pi,s表示在一个随机选择的时隙中成功发送一个属于数据流i的数据分组的概率；而Ps表示在一个随机选择的时隙中成功发送一个任何一种数据分组的概率。则有以下结论：
(12)
(13)
(14)
Ps=P0,s+P1,s (15)
设S为归一化的系统饱和吞吐量，定义为成功发射有效载荷的信道时间在总的信道时间中所占的份额。Si表示数据流i所占有的饱和吞吐量的份额。
参考文献[8]和[9]，可以得出数据流i所占用的吞吐量为：
(16)
系统的饱和吞吐量为：
(17)
其中，Ts表示因为一个成功发送而使信道检测为忙的时间；Tc表示因为一个分组冲突而使信道检测为忙的时间；σ表示空闲时隙的持续时间。E(pi)为数据流i的有效载荷的平均大小；E(p)则是系统中有效载荷的平均大小；我们假设MAC层数据分组大小恒定，所以有E(p0)= E(p1)= E(p)，这里E[pi]，E(p)，Ts，Tc，σ的值具有相同的单位。该文只考虑了基本接入机制，RTS/CTS机制可以以此类推。
参考文献[8]，得出：
(18)
4 区分服务模型的数学分析与评价
为验证上述分析的正确性，本节将采用数学分析的方法对在基本接入机制下改进的具有区分服务功能的MAC层协议进行性能分析。本文所采用的参数如表1所示。假设MAC层发送的数据分组大小恒定，且有n0=n1=0.5*n（n0为发送RT分组的节点的数量，n1为发送BF分组的节点的数量，n为网络中的节点总数）。
图1为两种数据流在基本接入机制下所占有的饱和吞吐量对比分析。从中可以很明显的看出本文提出的方法能够使RT流占用相对较多的带宽资源，且随着节点数量的最多，BF流的吞吐量会有所下降，而RT流占用的吞吐量基本维持不变。
图2为改进后的系统饱和吞吐量与标准802.11DCF机制下的饱和吞吐量在基本接入机制下的的变化情况，从中可以看出随着节点数量的最多，损失的带宽资源会加大，但加大的幅度不是很大，因而不会影响系统的整体性能。
5 结束语
针对无线ad hoc网络不能提供数据流优先级区分的问题，本文提出了一种基于802.11MAC协议的改进机制，该机制通过设置不同的MAC层最小竞争窗口来实现数据流的区分服务，使发送高优先级数据流（如实时数据流）的节点更容易连接信道，从而使高优先级数据流占有更多带宽资源。数学分析表明，该策略能有效的提高高优先级数据流的传输性能。
我们下一步的工作将继续深入探讨在无线ad hoc网络中如何引入区分服务模型，以及如何提高实时多媒体业务在无线网络中的传输性能。
参考文献：
[1] IEEE Std 802.11-1999. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S]. International Standard ISO/IEC 8802-11: 1999(E) ANSI/IEEE Std 802.11,1999.
[2] 李云, 隆克平等. IEEE802.11无线局域网中的一种支持业务区分的回退算法[J]. 电子学报, 2006,10(34):1877-1890.
[3] Jianhua He, Lin Zheng, et al. Analytical model for service differentiation schemes for IEEE 802.11 wireless LAN [J ]. IEICE Transactions on Communications, 2004, E87-B(6):1724-1729.
[4] Li Bo, Li jianDong et al. Supporting service differentiation with enhancements of the IEEE 802.11 MAC protocol:model and analysis[J]. Science in China series F: Information Sciences. 2007,50(5):732-746.
[5] Yang Xiao, Yi Pan. Differentiation, QoS guarantee, and optimization for real-time traffic over one-hop ad hoc networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(6):538-549.
[6] 杨宗凯, 许昌春, 等. 基于分组到达率的IEEE802.11无线局域网区分服务方法[J]. 电子学报, 2006,10(34):1864-1867.
[7] 王朝阳, 孙丹丹, 等. 带区分服务扩展的802.11MAC协议及其性能分析[J]. 通信学报, 2007,28(3):1-7.
[8] Giuseppe Bianchi. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547.
[9] Yang Xiao. Saturation Performance Metrics of the IEEE 802.11 MAC[H]. Proceedings of The IEEE Vehicular Technology Conference, Oct 2003, 6-9:1453-1457.
关键词：802.11DCF; 区分服务; 马尔科夫链模型; 性能分析
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)35-2120-03
Service Differentiation Scheme Based on Minimum Contention Windows for IEEE 802.11 WLAN
WU Zhi-qiang, ZHU Hong-li
(Henan Polytechnic University, Jiaozuo 454000, China)
Abstract: Considering that IEEE 802.11 ad hoc networks can not provide any priority scheme, this paper proposes a new scheme based on the 802.11 DCF back-off algorithm. The algorithm, by setting different number of Minimum Contention Windows at the data link layer, can make high-priority data flow(such as Real-time data flow) access channel more easily. As a result, the high-priority data flow can obtain more bandwidth. Our mathematical analyses demonstrate that the new algorithm improve the transmission performance of data flows in high priority significantly.
Key words: 802.11DCF; diffserv; markov chain model; performance analysis
1 引言
无线ad hoc网络是一种无固定控制中心、多跳、对等式网络，它不需要任何额外的架构设备，只需要接点配以无线收发装置即可随时组成无线局域网络。这种网络实现简单、灵活、不需要昂贵的基础设施、成本低，所以在军事通信和民用通信领域得到了广泛的应用。但ad hoc网络并不能提供业务的区分，难以满足那些对QoS有严格要求的业务（如实时流媒体业务）的传输要求。
目前，对于在ad hoc网络中提高实时业务的服务质量研究大多集中于MAC层，大部分研究者提出的支持QoS的MAC协议大多建立在IEEE802.11 DCF[1]机制上。其中的QoS增强机制主要集中在修改退避算法、帧间间隔、最大退避次数、最大帧长度等方面[2-7]。本文主要研究通过减小高优先级数据流的MAC层最小竞争窗口值来实现业务的区分服务，并利用相关数学模型对修改后的退避算法进行分析。分析结果表明，该策略能使高优先级数据流占用相对较多的带宽，从而提高高优先级数据流的传输性能。
本文第2节简要介绍IEEE 802.11 DCF退避机制；第3节则利用相关数学模型深入分析本文建立的区分服务机制；第4节对区分服务模型的性能进行分析和评价；第5节总结全文。
2 802.11 DCF描述
802.11DCF机制定义了两种信道接入机制，即基本接入机制和RTS/CTS机制。在基本接入方式下，一个节点在发送数据分组之前要监听信道，如果信道空闲超过一个分布式帧间间隔(DIFS)，该节点就启动一个退避过程，DIFS之后的时间被划分成一个个的时隙（time slot,记为σ），当信道空闲时间每超过一个时隙时间σ，计数器的值就减1。若探测到信道忙（有分组传输或者分组冲突）则退避计数器冻结，当再次探测到信道空闲超过一个分布式帧间间隔(DIFS)时计数器再次激活，当计数器的值到达0 时节点开始发送数据分组。如果数据分组传输失败，则启动一个指数退避过程。每个分组传输需要后退的时隙数目从区间（0,W-1）中均匀选取，W称为竞争窗口，m为最大退避次数。每次开始传输一个新的分组时，竞争窗口被设置成最小竞争窗口，记为CWmin。此后每次传输失败，竞争窗口加倍，直到达到一个最大值CWmax。若数据分组被成功接收，目的节点需要回复一个确认分组（ACK）。
在RTS/CTS接入方式下，节点遵循相同的指数退避机制，只是当退避计数器的值为0时发送方不是直接发送数据分组，而是发送一个称为RTS的短分组，目的节点收到RTS分组后需要回复一个CTS分组，发送方接收到CTS分组后方可开始发送数据分组。特别是当数据分组很大的情况下RTS/CTS接入方式明显优于基本接入方式，因为它减小了竞争阶段用于检测信道状况的帧长度。在理想信道的情况下，仅仅当两个或两个以上的数据分组尝试在同一个时隙的起始点发送时会导致冲突，当两个发送节点都采用RTS/CTS机制时，冲突仅仅会发生在RTS分组，发送方因收不到CTS分组而得知有冲突的发生。
3 区分服务机制的数学建模分析
本文参考了文献[8,9]中所用的方法，对本文提出的区分服务机制进行了数学建模分析，并通过相关模型得出了两种优先级数据流的饱和吞吐量、以及总体饱和吞吐量的计算方法。
3.1 马尔科夫链分析模型
在本文中，我们将网络中的数据流分为两种，一种为对时延敏感的数据流，我们简称RT（Real-Time）流；另一种为对时延不敏感的数据流，我们简称BF（Best-Effort）流。显然RT流对QoS的要求高于BF流。因此本文设置RT流为高优先级数据流，而BF流为低优先级数据流。
为便于分析，定义i为数据流的优先级类别，取值为0或1，其中0表示高优先级的RT流，1代表低优先级的BF流。两种数据流的分组都采用相同的退避机制竞争信道，因此两种数据流的竞争窗口值可用公式(1)计算。
其中Wi,0为数据流i的最小竞争窗口值，CWi,max为数据流i的最大竞争窗口值，j为退避计数器的退避阶段，m为最大退避次数，L为MAC层的最大重传次数，这里我们设置W0,0
1) 网络中每个节点只发送一类数据分组，并且每一类数据分组在传输过程产生冲突的概率恒定且独立。
2) 信道是理想的，即分组丢失只会是由冲突造成的。
3) 系统处于饱和状态，每个节点在成功进行一次分组发射后，立即监听信道，待其退避计数器退至0时马上发送下一分组。
对于传输第i类数据分组的节点，设B(i,t)表示其在时刻t的退避计数器值，S(i,t) 表示其在时刻t的退避阶段。根据文献[8]和[9]，{S(i,t), B(i,t)}构成了一个离散的二维马尔科夫链模型。令pi为属于数据流i的数据分组发送时产生冲突的概率，pi,b表示属于数据流i的数据分组在退避阶段检测到信道忙的概率。则其单步状态转移概率如下（我们简记
记
定义τi为发送第i类数据分组的节点在一个随机选择的时隙中发送分组（RTS或Data）的概率。因为节点发送分组只会在退避计数器的值为0时才发送，所以有：
设发送属于数据流i的数据分组的节点为ni个，pi,b表示发送属于数据流i的数据分组的节点在退避阶段检测到信道忙的概率。在本模型中，信道忙只会在有数据分组成功发送或者是发生分组冲突的情况下发生。因此，pi,b也可以理解为在上一个时隙内余下的（n0+n1-1）个节点中至少有一个节点发送了分组。由此，我们可以得出：
pi表示属于数据流i的数据分组发送时产生冲突的概率。在本模型中，分组发生冲突只会是剩余的(n0+n1-1)个节点中至少有一个节点也在同一时隙内发送了分组。因此，可以有以下结论：
在节点数量、最小竞争窗口、最大退避次数、MAC层最大重传次数等参数已知的情况下，可以由公式（6-11）计算出p0、p1、p0,b、p1,b的值，并且有唯一值。
3.2 饱和吞吐量分析
设Ptr为在一个随机选择的时隙内网络中至少有一次分组发送的概率；Pi,s表示在一个随机选择的时隙中成功发送一个属于数据流i的数据分组的概率；而Ps表示在一个随机选择的时隙中成功发送一个任何一种数据分组的概率。则有以下结论：
Ps=P0,s+P1,s (15)
设S为归一化的系统饱和吞吐量，定义为成功发射有效载荷的信道时间在总的信道时间中所占的份额。Si表示数据流i所占有的饱和吞吐量的份额。
参考文献[8]和[9]，可以得出数据流i所占用的吞吐量为：
系统的饱和吞吐量为：
其中，Ts表示因为一个成功发送而使信道检测为忙的时间；Tc表示因为一个分组冲突而使信道检测为忙的时间；σ表示空闲时隙的持续时间。E(pi)为数据流i的有效载荷的平均大小；E(p)则是系统中有效载荷的平均大小；我们假设MAC层数据分组大小恒定，所以有E(p0)= E(p1)= E(p)，这里E[pi]，E(p)，Ts，Tc，σ的值具有相同的单位。该文只考虑了基本接入机制，RTS/CTS机制可以以此类推。
参考文献[8]，得出：
4 区分服务模型的数学分析与评价
为验证上述分析的正确性，本节将采用数学分析的方法对在基本接入机制下改进的具有区分服务功能的MAC层协议进行性能分析。本文所采用的参数如表1所示。假设MAC层发送的数据分组大小恒定，且有n0=n1=0.5*n（n0为发送RT分组的节点的数量，n1为发送BF分组的节点的数量，n为网络中的节点总数）。
图1为两种数据流在基本接入机制下所占有的饱和吞吐量对比分析。从中可以很明显的看出本文提出的方法能够使RT流占用相对较多的带宽资源，且随着节点数量的最多，BF流的吞吐量会有所下降，而RT流占用的吞吐量基本维持不变。
图2为改进后的系统饱和吞吐量与标准802.11DCF机制下的饱和吞吐量在基本接入机制下的的变化情况，从中可以看出随着节点数量的最多，损失的带宽资源会加大，但加大的幅度不是很大，因而不会影响系统的整体性能。
5 结束语
针对无线ad hoc网络不能提供数据流优先级区分的问题，本文提出了一种基于802.11MAC协议的改进机制，该机制通过设置不同的MAC层最小竞争窗口来实现数据流的区分服务，使发送高优先级数据流（如实时数据流）的节点更容易连接信道，从而使高优先级数据流占有更多带宽资源。数学分析表明，该策略能有效的提高高优先级数据流的传输性能。
我们下一步的工作将继续深入探讨在无线ad hoc网络中如何引入区分服务模型，以及如何提高实时多媒体业务在无线网络中的传输性能。
参考文献：
[1] IEEE Std 802.11-1999. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S]. International Standard ISO/IEC 8802-11: 1999(E) ANSI/IEEE Std 802.11,1999.
[2] 李云, 隆克平等. IEEE802.11无线局域网中的一种支持业务区分的回退算法[J]. 电子学报, 2006,10(34):1877-1890.
[3] Jianhua He, Lin Zheng, et al. Analytical model for service differentiation schemes for IEEE 802.11 wireless LAN [J ]. IEICE Transactions on Communications, 2004, E87-B(6):1724-1729.
[4] Li Bo, Li jianDong et al. Supporting service differentiation with enhancements of the IEEE 802.11 MAC protocol:model and analysis[J]. Science in China series F: Information Sciences. 2007,50(5):732-746.
[5] Yang Xiao, Yi Pan. Differentiation, QoS guarantee, and optimization for real-time traffic over one-hop ad hoc networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(6):538-549.
[6] 杨宗凯, 许昌春, 等. 基于分组到达率的IEEE802.11无线局域网区分服务方法[J]. 电子学报, 2006,10(34):1864-1867.
[7] 王朝阳, 孙丹丹, 等. 带区分服务扩展的802.11MAC协议及其性能分析[J]. 通信学报, 2007,28(3):1-7.
[8] Giuseppe Bianchi. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547.
[9] Yang Xiao. Saturation Performance Metrics of the IEEE 802.11 MAC[H]. Proceedings of The IEEE Vehicular Technology Conference, Oct 2003, 6-9:1453-1457.