随机访问网络后退避机制的性能分析

2016-11-30步超伦肖扬叶通吴鹏张小建吴军民

电信科学 2016年2期

关键词：重传非饱和时隙

步超伦，肖扬，叶通，吴鹏，张小建，吴军民

（1.上海交通大学区域光纤通信网与新型光通信系统国家重点实验室，上海200240；2.国网智能电网研究院，江苏南京210003）

研究与开发

随机访问网络后退避机制的性能分析

步超伦1，肖扬1，叶通1，吴鹏2，张小建2，吴军民2

（1.上海交通大学区域光纤通信网与新型光通信系统国家重点实验室，上海200240；2.国网智能电网研究院，江苏南京210003）

无线局域网随机访问协议的性能分析是近年来的研究热点，而现有的模型还未能对其后退避机制进行有效刻画。基于一种两阶段的马尔可夫模型，分析非饱和业务状态下随机访问网络的性能。首先，利用嵌入式马尔可夫链描述每个站点队头分组的服务过程，引入虚拟服务时间的概念，即将传输成功之后的后退避也看成队头分组服务时间的一部分，从而得到队头分组的虚拟服务时间分布。然后，将每个用户队列看成一个Geo/G/1系统，求得非饱和业务状态下系统吞吐量、时延等参数的闭合解表达式以及系统的稳定区间。仿真结果验证了模型的准确性。本文所提模型将对今后研究无线局域网的分布式协调功能（DCF）协议打下基础。

随机访问网络；后退避；性能分析；马尔可夫链

1 引言

近年来，人们对移动通信以及带宽的要求越来越高，无线局域网络的应用越来越广泛。无线信道的随机访问协议是无线局域网的核心协议，其中较常见的随机访问协议有Aloha协议及其变种载波侦听多路访问（CSMA）协议和分布式协调功能（DCF）协议等。

随机访问网络协议的一个突出问题是信道的捕获效应，即信道被同一站点持续占用，而其他站点则一直处在退避重传的过程中无法成功发送数据，从而带来节点间的不公平性。为了解决这一问题，业界引入了“后退避”机制，即在数据分组发送成功之后，站点进行一段随机退避，以便释放信道，从而避免信道被某个站点持续占用。

过去的十几年里，许多学者对基于后退避机制的随机访问协议进行了分析，然而大多数分析都是基于饱和业务假设。所谓饱和业务情形，就是指各站点在发送成功数据分组后，缓存队列中一定有数据在等待发送。在该情形下，当数据分组到达队列时，站点要么在忙于发送数据分组，要么在进行“后退避”。Bianchi［1］提出了一种二维的马尔可夫链模型来刻画数据分组过程，并对系统的吞吐量进行了分析。参考文献［2-5］针对饱和业务情形下的随机访问协议系统进行了分析，然而他们都基于参考文献［1］中饱和业务情形的假设。在实际系统中，网络一般不会工作在饱和业务情形下，因为此时的网络均处于非稳定状态，数据时延性能得不到保障。研究非饱和业务情形下系统的性能具有十分重要的意义。

在非饱和业务情形下，数据分组到达队列时看到的情形要比饱和业务复杂得多。当有新的数据分组到达站点时，该站点可能正在忙于发送队头分组，也可能正处于后退避状态，还可能处于空闲状态。目前，已经有一些文献对非饱和业务情形下的随机访问网络进行了分析。参考文献［6］是基于参考文献［7］的两阶段模型，分析了非饱和业务状态下的DCF系统性能，但未考虑后退避机制。参考文献［8，9］在参考文献［1］的马尔可夫链的基础上，增加了站点空闲的状态，并分析了非饱和业务状态下系统的特性，但仍然没有考虑后退避机制。Malone［10］则针对非饱和业务的特性，在马尔可夫链［1］的基础上增加了后退避状态，然而在分析系统的吞吐量和时延时，涉及站点的空闲概率，而该概率本身又取决于系统的状态，这就产生了记忆性，没法求出各参数的封闭解析表达式。

为此，本文提出虚拟服务时间的概念，并基于一种两阶段模型［7］分析非饱和业务情况下的后退避的随机访问网络性能。假设当共享媒介的站点数量较多时，站点间的行为相互独立，即每个站点看成独立的FIFO队列。首先，利用马尔可夫链描述每个站点队头分组的服务过程，引入虚拟服务时间的概念，即将传输成功之后的后退避过程也看成队头分组服务时间的一部分。于是，上述队头分组可能面对的复杂情形变得清晰，一个分组到达站点时，要么站点处于繁忙状态，要么处于空闲状态，这样就消除了系统的记忆性，体现出模型的马尔可夫特性。然后，将每个用户队列看成一个Geo/G/1系统，求得非饱和业务状态下系统吞吐量、时延等参数的闭合解表达式，并确定系统的稳定区间。

2 物理过程及模型建立

本文研究的随机访问网络如图1所示，多个站点通过随机竞争的方式共享同一个带宽资源。该网络是一个分时隙的系统，每个站点都服从速率为λ的伯努利到达过程，并且都带有无限空间的缓存。

图1 n个站点的时隙随机退避网络模拟队列

图2演示了基于后退避的时隙随机访问网络中两个站点竞争发送分组的过程。当一个数据分组成为队头分组，而且该站点不处于后退避状态时，站点将在当前时隙立即发送它。如果此时另一个站点在此时隙也有分组发送，就会发送冲突，如图2中灰色方框所示。这时两站点都要进行一段随机时间的退避，即以概率q重传该数据分组，如图2中实线箭头所示；当某个时隙只有一个站点发送数据分组时，数据分组可以传送成功。但为了避免成功站点独占信道，该站点将以概率r进行一段后退避，如图2中虚线箭头所示。

图2 基于后退避的时隙随机访问网络中两个站点竞争发送分组的过程

在后退避的随机访问网络中，站点的数据分组看到的本站所处的状态会比较复杂。当此分组到达站点时队列非空，它成为队头分组后仍需要经历一个后退避的过程才能被发送；如果此分组到达时队列为空，但站点后退避过程并未结束，它也需要等到后退避过程结束后才能被发送；如果此分组到达时队列为空，且上一次后退避已经结束，则可以在当前时隙立即被发送。因此，新到达的分组是否能被立即发送，不仅取决于站点队列是否为空，而且取决于站点是否处于后退避状态，这使非饱和业务下的性能分析变得困难。参考文献［1］中假设饱和业务，实际上是只考虑第一种情形，减小了问题复杂度，因此不符合一般情形。

为了全面刻画后退避状态，本文引入虚拟服务时间的概念，即将后退避过程看成一个队头分组服务过程的一部分。换言之，从一个分组成为队头分组到由它引发的后退避结束的这段时间看成虚拟服务时间。在这段时间内，站点都属于“忙”的状态。只有后退避结束之后，队列的下一个分组才能成为一个队头分组。如图3所示，用Ps表示第s个数据分组，用Xs表示数据分组s的真实服务时间，Bs表示数据分组Ps的后退避的时间，队头分组服务过程的虚拟服务时间则由单个分组的真实服务时间Xs和后退避时间Bs两部分构成，即Vs=Xs+Bs。于是，上述队头分组可能面对的复杂情形变得清晰。一个分组到达站点时，站点要么处于繁忙状态，要么处于空闲状态，而且引入虚拟服务时间的概念也不影响真实的平均服务时间的计算。因为，只要把平均虚拟服务时间减去平均后退避时间就可以得到真实的平均服务时间。

图3 虚拟服务时间

本文基于参考文献［7］的两级排队模型对系统进行建模。把每个站点看成一个Geo/G/1的排队系统，其中信道对队头分组的服务过程可以通过图4的马尔可夫链来刻画。队头分组将经历可直接发送状态（状态0）、发送失败后的重传状态（状态1）以及发送成功后的后退避状态（状态-1）。新的队头分组都是先进入初始状态0，如果传送发生冲突则进入状态1，并以概率q再次发送；而如果队头分组以概率p传送成功，则以概率r回到状态0，以概率1-r进入状态-1。同样，如果处于状态1的队头分组再次冲突，则依然处于状态1，如果传送成功则以概率r选择是进入状态-1还是状态0。因此，参数r描述了站点在成功发送分组之后的时隙中，进行后退避过程的概率。换言之，参数r也决定了一个站点处于后退避状态的时长。

图4 带有后退避机制的时隙随机退避网络队头分组服务过程马尔可夫链

用f0、f1和f-1分别代表图4中各状态的稳态概率。利用离散时间马尔可夫链的性质，可以得到：

因为后退避过程也可看成队头分组服务过程的一部分，把引入后退避机制后数据分组的到达速率和虚拟服务速率的比值称为虚拟负载率ρυ。每一个队头分组的起始状态是0，而结束状态也是0，因此一个队头分组的服务速率是f0，假设输入速率为λ，每个站点的虚拟负载率为：

3 性能分析

3.1 吞吐量

每个站点可能存在5种状态：状态1，空闲且缓存为空；状态2，忙于传送一个状态为0的新分组；状态3，忙于重传一个状态为1的发生过冲突的分组；状态4，由于传送发生冲突而进行退避；状态5，进行后退避。

由式（1）～式（4）可知，Pr｛状态1}=1-ρυ，Pr｛状态2}=ρυf0，Pr｛状态3}=ρυf1q，Pr｛状态4}=ρυf1（1-q），Pr｛状态5}=ρυf-1。

当站点处于状态1、4和5时，并不会发送数据分组。而一个站点想要成功发送分组的条件就是其余n-1个站点不发送分组，那么成功发送分组的概率为：

在稳定状态下，系统的输出λout应该和输入λin相等，根据式（5）可知，每个时隙的平均尝试发送分组率为：

所以稳定状态下的吞吐量为：

这与参考文献［11］中的结果是一致的，这说明本文模型在吞吐量上的分析是正确的。

3.2 时延

由图4可知，队头分组的服务时间是在所有状态经历时间的总和，用Di表示从状态i开始直到服务完成所经过的时间，用Yi表示在状态i所花费的时间，有：

Yi是服从几何分布的随机变量，Yi的概率母函数为：

根据式（8）和式（9），Di的概率母函数可以表示为：

根据式（11）和式（12），有：

根据概率母函数的性质可知，虚拟服务时间V的均值和方差可以表示为：

根据参考文献［7］中的Pollaczek-Kintchine公式以及式（13）～式（16），可以得到平均虚拟服务时间为：

平均等待时间为：

计算平均总时延时，应将平均虚拟服务时间和平均等待时间相加后，再减去平均后退避时间，即：

3.3 稳定区间

根据参考文献［11］，时隙随机退避网络的最大吞吐量约为0.368，由式（7）可以得到系统吞吐量与尝试发送率之间的关系，如图5所示。

图5 λout与G的关系曲线

假定系统总输入λin=nλ＜0.368，那么系统稳定的条件就是λout=λin=nλ。对应图5中可以发现，只有在两个红色实心交点处满足该条件，把这两个交点分别记作GS和GL，根据式（6）可以得到对应的两个成功发送分组概率分别为pS和pL。

q是唯一一个可以由系统改变的参数，系统只有当ρυ≤1时才会处于稳定状态，所以令ρυ=1，求出临界状态下的两个q值。由式（4），有：

代入pL和pS有：

系统稳定时需要满足两个条件，即ρυ≤1且E［T］＜∞，下面将分5种情形分别讨论关于q的稳定区间。

（1）情形1：q∈［0，qS）

将q代入式（4）和式（19）可知，无论p取何值，都会得到ρυ＞1且E［T］=∞，在这种情况下系统一定不稳定。

（2）情形2：q=qS

这种情形下，p=pS可以得到ρυ=1，系统处于临界稳定，然而此时E［T］=∞，系统并不稳定。

（3）情形3：q∈（qS，qL）

这种情形下需要对p的取值分情况进行讨论，当p=pS时，ρυ＜1，且ρυ随着q的增加而降低，E［T］有上界，且E［T］随着q的增加而逐渐降低，此时系统稳定；而当p取pL时，ρυ≥1，系统不稳定，E［T］为负值，显然不可能。这说明，在这个区间内系统要想稳定，其发送分组成功概率p一定只能等于pS。

（4）情形4：q=qL

当q=qL时，p=pL，ρυ突然增加到1，系统处于临界状态，而E［T］突然又增加到无穷，系统不稳定。

（5）情形5：q∈（qL，1］

此时无论p取pL还是pS，ρυ＜1均成立，且E［T］均有界。这似乎暗示着系统可以同时处于pL和pS状态，然而模型各态遍历的前提说明模型在此区域已经失效，系统在稳定状态下p不可能有两个解，即模型无法刻画系统的行为。

综上，系统的稳定区间为q∈（qS，qL）。并且当q∈［qS，qL）时，站点发送分组成功概率为p=pS；当q=qL时，站点发送分组成功概率为p=pL。因此，在qS≤q≤qL区间内，p是q的阶跃函数。

4 仿真与分析

在C++的环境下对每个站点队头分组的不同状态进行仿真，默认取站点个数n为50，并且令r=q，分别在3种不同的系统输入流量λin=0.1、0.3和0.35的情况下进行对比仿真，只设置一个可调参数：重传因子q，接下来通过设置不同的q值，得到吞吐量、时延、负载率等参数的仿真结果。

图6是吞吐量λout在不同的系统输入流量下关于重传因子q的仿真结果比较。可以看出，稳定区间的仿真结果边界值与用式（21）和式（22）计算的理论值（qSqL）相符，当重传因子q超出稳定区间时，系统的吞吐量快速下降，而当重传因子q在稳定区间（qS，qL）内时，系统吞吐量λout始终保持恒定，即系统输入流量λin。

图6 吞吐量的仿真结果比较

图7则对系统的平均总时延进行仿真。可以看出，仿真结果可以和式（19）算出的理论结果相匹配。当重传因子q在稳定区间内逐渐增加时，平均时延从无穷大开始逐渐下降，这是因为随着q的增加，各站点在发生冲突后的重传概率变大，那么出现某个站点持续占用信道的概率减小，也就是增加了系统的公平性，站点的缓存中排队等待发送的数据分组变少，站点中队头分组发送冲突后退避的时间也减少，从而降低了平均时延。而当重传因子q超出稳定区间后，时延突然增加到无穷大，系统状态又变为不稳定。

图7 平均时延的仿真结果比较

图8则是虚拟负载率ρυ关于q的关系曲线。在稳定区间内，仿真结果与式（4）的理论值相符。虚拟负载率ρυ等于数据分组的到达速率和虚拟服务速率的比值，随着q的增加，站点中队头分组发送冲突后退避的时间减少，也就是服务时间减少，即服务速率增加，那么在到达速率λ不变的情况下，虚拟负载率ρυ是关于q的一条单调递减曲线。而在稳定区间的两个端点处，负载率为1，系统处于临界稳定。

图8 系统负载率的仿真结果比较

当q∈［qS，qL）时，站点成功发送分组的概率p始终等于pS；而当重传因子q=qL时，站点发送分组成功概率为p=pL。成功发送分组概率的仿真结果如图9所示。在［qS，qL）内，p始终保持恒定且等于pS，而当q=qL时，p发生跳变，变为pL，这又进一步验证了理论分析中所预测的阶跃性是正确的。

图9 成功发送分组概率的仿真结果比较

5 结束语

本文提出了一种带有后退避机制的马尔可夫链模型，以分析时隙随机退避网络协议的性能。通过引入的虚拟服务时间和虚拟负载率等参数，分析了系统各项参数的性能，并求解出非饱和业务状态下系统吞吐量、时延等参数的闭合解表达式以及系统的稳定区间。仿真结果与理论分析相符，证实了本文模型的正确性。接下来将分析后退避机制在更加复杂的随机退避网络协议（如分布式协调功能（DCF）协议）中的应用。

［1］BIANCHI G.Performance analysis of the IEEE 802.11 distributed coordination function［J］.IEEE Journal on Selected Areas in Communications，2000，18（3）：535-547.

［2］KUMAR A，ALTMAN E，MIORANDI D，et al.New insights from a fixed point analysis of single cell IEEE 802.11 WLANs［C］/The 24th Annual Joint Conference of the IEEE Computer and Communications Societies，March 13-17，2005，Miami，FL，USA.New Jersey：IEEE Xplore，c2005：1550-1561.

［3］CALì F，CONTI M，GREGORI E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit［J］.IEEE/ACM Transactions on Networking，2000，8（6）：785-799.

［4］WU H，PENG Y，LONG K，et al.A simple model of IEEE 802.11 wireless LAN［C］//The International Conferences on Info-tech and Info-net，October 12-14，2001，Beijing，China.New Jersey：IEEE Xplore，c2001：514-519.

［5］SAKURAI T，VU H L.MAC access delay of IEEE 802.11 DCF［J］.IEEE Transactions on Wireless Communications，2007，6（5）：1702-1710.

［6］DAI L，SUN X.A unified analysis of IEEE 802.11 DCF networks：stability，throughput，and delay［J］.IEEE Transactions on Mobile Computing，2013，12（8）：1558-1572.

［7］LEE T T，DAI L.Buffered aloha with K-exponential backoff--part I：stability and throughput analysis［J］.arXiv preprint arXiv：0907.4251，2009.

［8］WANG B，SONG F，ZHANG S D，et al.Throughput modeling analysis of IEEE 802.11 DCF mechanism in multi-hop non-saturated wireless ad-hoc networks［C］/The International Conference on Communications，Circuits and Systems，May 25-27，2008，Xiamen，China.New Jersey：IEEE Xplore，c2008：383-387.

［9］GUPTA N，RAI C S.Non-saturation throughput analysis of IEEE 802.11 DCF considering short retry limit for single hop ad hoc networks［C］/The Second International Conference on Future Generation Communication Technology（FGCT），November 12-14，2013，London，United Kingdom.New Jersey：IEEE Xplore，c2013：10-15.

［10］MALONE D，DUFFY K，LEITH D.Modeling the 802.11 distributed coordination function in nonsaturated heterogeneous conditions［J］.IEEE/ACM Transactions on Networking，2007，15（1）：159-172.

［11］ABRAMSON N.Packet switching with satellites［C］/The National Computer Conference and Exposition，June 4-8，1973，New York，USA.New York：AFIPS Press，c1973：695-702.

步超伦（1991-），男，上海交通大学硕士生，主要研究方向为无线通信网络协议性能分析。

Performance analysis of random access network w ith post-backoff

BU Chaolun1，XIAO Yang1，YE Tong1，WU Peng2，ZHANG Xiaojian2，WU Junmin2
1.State Key Laboratory of Advanced Optical Communication Systems and Networks，Shanghai Jiaotong University，Shanghai 200240，China 2.State Grid Smart Grid Research Institute，Nanjing 210003，China

Performance analysis of random access network protocol in wireless local area network is a research hotspot in recent years，and the existing models have yet to describe post-backoff mechanism effectively.Therefore，the performance of the random access network under the unsaturated condition based on a two stage Markov model was analyzed.First of all，embedded Markov chain was used to describe the service process of the head-of-line（HOL）packet in each node，then the concept of virtual service time was introduced，namely regarding the p ost-backoff process after the successful transmission as a part of the HOL packet service time，then the virtual service time distribution of the HOL packet was attained.Next，the queuing process of each node was considered as a Geo/G/1 system，then the close-form result of system throughput，delay and the range of the stable region under the unsaturated condition was achieved.The simulation results have verified the accuracy of our model.The model will shed light on the future research on distributed coordination function（DCF）protocol in wireless local area network.

random access network，post-backoff，performance analysis，Markov chain

The Key Technology and Power Grid Application Research of All-Optic Switching

TN929.5

10.11959/j.issn.1000-0801.2016055

2015-08-20；

2016-01-07

全光交换关键技术及电网应用研究项目