IEEE 802.11 DCF 性能分析的经典模型

DCF 机制是 IEEE 802.11 协议的 MAC 层接入机制的核心。对其进行理论分析式进行 IEEE 802.11 协议改进与重新设计的基础。Bianchi [1] 的一篇经典论文提出了一种基于 Markov 模型的 DCF 机制性能分析方法。这篇经典论文有超过 1 万次应用，可以说是相关领域的必读论文。这篇文章针对这个 Markov 模型进行简单介绍。读者应当自行具备 Markov 模型的基本知识。

DCF 机制的全称是 Distributed coordination function，这个机制的核心是指数退避方法，并且定义了 ACK，RTS，CTS 机制来进一步增强接入过程的可靠性。这个机制是 IEEE 802.11 协议基础中的基础。笔者在这里不做过多叙述，可以阅读相关论文和技术标准。

一维马尔科夫链主要应用于广播消息的性能分析。在广播通信中，不存在 ACK 机制，因此发送者无法判断发送是否，因此也就无法增加退避窗口并且发起重传。这里整理的一维马尔科夫过程的研究主要来自于[2]，同时包含饱和以及不饱和场景的性能分析。

网络结构为的单跳 Adhoc 网络，节点总数为n。传输环境为：a two-ray propagation model with no hidden terminal or capture effects，即所有的包丢失都是由于碰撞(Collision)导致的。假设每个节点每次只能缓存一个数据包，且包的到达过程为到达率为λ的 Poisson 过程，

如 图 1 所示，退避窗口为W，意味着退避状态一共有W个，以及一个额外的 Idle 状态（记为I）。同时记包的到达概率为q，信道繁忙的概率为qb，则有下面的概率转移矩阵：

⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩P{I|I}=1−qP{k|I}=q/WP{k|I+1}=1−pbP{k|k}=pbP{I|0}=1(1)

下面求解稳态分布bk(k∈[0,W−1])（Idle 状态的稳态概率为bI），我们通过转移概率可以得到如下的方程：

bI=1qb0(2)

bk=(W−k)qW(1−Pb)bI=(W−k)W(1−Pb)b0k∈[1,W−1](3)

bI+b0+W−1∑k=1bk=1(4)

当 backoff counter 为 0 时节点开发发送，则b0为传输概率(transmission probability) τ。通过上面的三个公式组成的方程，我们可以得到：

τ=b0=(1q+1+(W−1)2(1−Pb))−1(5)

在得到传输概率以后，通过经典文章[1]我们可以计算吞吐率性能。不过我们在这里的模型中增加了 Idle 状态，因此分析会有一点不同。

记Pb为信道繁忙的概率，Ps为传输成功的概率，则：

Pb=1−(1−τ)n−1Ps=nτ(1−τ)n−1(6)

按照[1]的方法，将两次 backoff 状态之间的间隔定义为一个 slot（virtual slot），则 virtual slot 可能包含一个空的 slot，一次冲突，或者一次成功的发送。那么有：

SlotTime=(1−τ)nσ+(1−(1−τ)n)T(7)

由于在广播中，没有 RTS/CTS，也没有 ACK，那么一次冲突和一次成功发送占用信道的时间是一样的：

T=H+E[P]R+DIFS+δ(8)

这里H为物理层帧头和 MAC 层帧头的大小，R为发送速率。由于我们假定包的生成过程是 Poisson 过程，则

q=1−e−λSlotTime(9)

通过联立求解(5),(6),(9)非线性方程组，我们可以得到归一化吞吐率性能

S=PsE[P]SlotTime(10)

上面描述的是非饱和状态下的性能计算过程，但是当 λ 趋近于无穷大，即 q 趋向于 1 时，即可以得到饱和场景下的通信性能。

沿用了 Bianchi 的假设条件，包括有限数量的通信节点(n个)以及理想信道条件。这篇文章中研究的是饱和条件下的稳态性能。饱和条件意味着对于每个节点，当其完成一次传输时，立刻就有一个新的包等待传输。

文章采用的 DCF 机制是经典的 DCF 机制，核心特点包括指数增长的退避窗口，在退避期间信道繁忙时，退避计数器的值冻结。退避窗口到达最大以后，停止增长。若发送失败，则窗口保持最大值。反之，如果发送成功，则重置退避窗口。

随机变量的定义则如下：b(t)定义为在 t 时隙上的退避计数器取值。每个节点退避窗口的定义为 Wmin=WWmax=2mW(11) 即共有m+1个退避阶段(backoff stage)。s(t)为用来表示退避阶段的随机变量。那么二元随机过程{s(t),b(t)}构成二维离散马尔科夫链。记条件碰撞概率为p，信道繁忙概率为pb。假定p与pb与退避过程无关。当W和n比较大时此假设更加准确。

二元随机过程{s(t),b(t)}的状态值记为{i,k}。其中0≤i≤m,0≤k≤Wi−1, 其中Wi=2iW。模型中还存在另一个状态{−1,0}。这个状态代表当退避计数器为 0，且经过 DIFS 时间后信道空闲时，节点会在当前时隙立即发送数据。{−1,0}这个状态刻画了此行为。这个状态未在 Bianchi 的模型中引入。

概率转移图如下：

转移概率为：

⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩P{−1,0|−1,0}=(1−p)(1−pb)P{0,k|−1,0}=(1−p)pb+pW0,0≤k≤W0−1P{i,k|i,k}=pb,1≤k≤Wi−10≤i≤mP{i,k|i,k+1}=1−pb,1≤k≤Wi−20≤i≤mP{0,k|i,0}=(1−p)pbW0,0≤k≤Wi−10≤i≤mP{−1,0|i,0}=(1−p)(1−pb),0≤i≤mP{i,k|i−1,0}=pWi,1≤k≤Wi−10≤i≤mP{m,k|m,0}=pWm,0≤k≤Wm=1(12)

其中：

接下来我们需要计算稳态概率分布。记平稳分布为bi,k=limt→∞P{s(t)=i,b(t)=k}。对于平稳分布我们有如下的关系： bi,0=pib0,00≤i≤m−1(13) bm,0=pm1−pb0,0(14) bi,k=Wi−kWi11−pbbi,00≤i≤m1≤k≤Wi−1(15) b0,0=pb+p(1−pb)1−pbb−1,0(16)

然后使用正则化条件

b−1,0+m∑i=0Wi−1∑k=0bi,k=1(17)

经过推导可以得到

b−1,0=2(1−pb)2(1−2p)(1−p)2(1−pb)2(1−2p)(1−p)+(pb+p(1−pb))(1−2p)(W+1)+pW(pb+p(1−pb))(1−(2p)m)(18)

已知平稳分布以后，我们可以计算对于某个节点任意时隙的传输概率

τ=m∑i=−1bi,0=b−1,0+m−1∑i=0bi,0+bm,0(19)

当退避计数器到 0 时，节点即会尝试发送数据包。

这个公式全部展开也非常长，不过也是简单的多项式计算

τ=2(1−pb)(1−2p)2(1−pb)2(1−2p)(1−p)+(pb+p(1−pb)(1−2p)(W+1)+pW(pb+p(1−pb))(1−(2p)m)(20)

进而得到碰撞概率为 p=1−(1−τ)n−1(21)

信道繁忙的概率为

pb=1−(1−τ)n(22)

将(21)及(???)代入(???)可以得到关于τ的非线性方程。此方程可以通过数值方法求解。

类似 Bianchi 的做法，这里认为对于每一次传输，无论成功与非，都视为一个更新过程。因此，可以计算相邻两次传输之间的 CSMA/CA 协议的吞吐率。此时吞吐率S可以表达为:

S=E[ time used for successful transmission in an interval ]E[ length between two consecutive transmissions ]=PsE[P]E[Ψ]+PsTs+(1−Ps)Tc(23)

其中，E[P]为 Payload 的平均大小。Ts为成功传输的平均时间，Tc为冲突的平均持续时间。Ps为传输成功的概率。而E[Ψ]则表示在传输发生之前由于退避引入的空余时隙的长度。一般我们假定包的大小都是相同的，即E[P]=P。Ts和Tc的值取决于具体的 DCF 机制：

Tacks=H+P+δ+SIFS+ACK+δ+DIFSTackc=H+P+δ+DIFS}ACKCSMA/CA(24) Tretss=RTS+δ+SIFS+CTS+δ+SIFS+H+P+δ+SIFS+ACK+δ+DIFSTretsc=RTS+δ+DIFS}RTS/CTSCSMA/CA(25)

其中H=PHYhdr+MAChdr为帧头，δ为传输延时。传输成功要要求有且仅有一个节点参与传输，故

Ps=nτ(1−τ)n−11−(1−τ)n(26)

最后：

E[Ψ]=1pb−1(27)

注意这里的所有时间变量都是表示的时隙数量。通过上面的式子我们可以计算出吞吐率(23)。

更新过程: 相比泊松过程，更新过程约束更少，算是对泊松过程的一个推广。我们知道下面的几个定义是可以推出泊松过程的：

类比过程，可以得到更新过程的定义，仅仅把 1 中的随机变量服从的指数分布去掉，不指定具体的分布，后续的 2，3 保持不变，这样的过程就是更新过程。而泊松过程是更新过程的一个特例吧！ 来源

令随机变量D代表延时，其均值为E[D]。平均延时可以通过如下公式进行计算：

E[D]=E[Nc](E[BD]+Tc+TO)+(E[BD]+Ts)(28)

其中E[Nc]为一个数据包在最终被接收前经过的冲突的次数。E[BD]为在繁忙的信道条件下，一个节点在访问信道前经过的退避延时的平均值（包含在空闲条件下需要等待的时隙以及在繁忙条件下需要冻结退避计数器的时长）。TO为在发生碰撞时，再次访问信道前需要等待的时间。而Tc和Ts的定义与上一部分吞吐率分析中定义的一致。平均碰撞次数可以用简单一维马尔科夫链的方法计算得到：

E[Nc]=1Ps−1(29)

平均退避掩饰则取决于退避计数器的值及冻结时长。假设退避状态为bi,k，则需要等带k个空时隙才能发送。那么平均退避延时可以按照如下方式计算：

E[X]=m∑i=0Wi−1∑k=1kbi,k(30)

根据 System Model 中得到的平稳分布我们可以得到

E[X]=b0,06(1−pb)W2(1−p−3p(4p)m)+4p−1(1−4p)(1−p)(31)

另外我们还需要计算冻结退避计数器的时间。这一时间的平均值为E[F]。为了计算这一均值，我们需要先计算E[NFr]，即退避计数器到 0 前会检测到的传输次数。注意到E[X]为退避计数器退避到 0 的平均时间（时隙数），而E[Ψ]为一次传输前需要经过的空闲时隙的数量，则我们可以计算

E[NFr]=E[X]max(E[Ψ],1)−1(32)

则

E[F]=E[NFr](PsTs+(1−Ps)Tc)(33)

结合(???)和(???)，可以得到

E[BD]=E[X]+E[NFr](PsTs+(1−Ps)Tc)(34)

最后，TO的取值规则如下：

TO={SIFS+ACK− timeout SIFS+CTS− timeout (35)

至此我们计算得到了延时需要的所有参数。