基于指数退避算法的IEEE 802.11协议吞吐量分析

doi:10.12677/HJWC.2018.82007

期刊菜单

基于指数退避算法的IEEE 802.11协议吞吐量分析
Analysis of Throughput of IEEE 802.11 Protocol Based on Exponential Backoff Algorithm

DOI: 10.12677/HJWC.2018.82007, PDF, HTML, XML, 下载: 1,401 浏览: 4,177 国家自然科学基金支持
作者: 向巧, 黎锁平：兰州理工大学理学院，甘肃兰州
关键词: IEEE 802.11；退避算法；非理想信道；吞吐量；IEEE 802.11； Backoff Algorithm； Nonideal Channel； Throughput

摘要: 在实际网络通信环境下，数据分组因为信道干扰而导致信息不能有效传输，因此在非理想信道下改善系统的性能影响是有必要的。本文以无线局域网为通信背景，考虑到非理想信道对WLANs产生的诸如信号衰落和失真等影响的条件下，在以往文献指数退避算法的基础上加入冻结概率来减少信道中的数据冲突，并结合两种接入访问方式分别求得IEEE 802.11协议下的饱和吞吐量公式，最后模拟仿真对该模型进行分析和验证。

Abstract: In the actual network communication environment, data packets cannot be efficiently transmitted due to channel interference, so it is necessary to improve the system performance impact under non-ideal channels. This paper takes the wireless LAN as the communication background, consi-dering the impact of non-ideal channels on WLANs such as signal fading and distortion, adds the freezing probability based on the previous literature exponential backoff algorithm to reduce the data collision in the channel and combine them. The two types of access methods are used to obtain the saturation throughput formula under the IEEE 802.11 protocol. Finally, simulation and analysis of the model are performed.

文章引用：向巧, 黎锁平. 基于指数退避算法的IEEE 802.11协议吞吐量分析[J]. 无线通信, 2018, 8(2): 64-69. https://doi.org/10.12677/HJWC.2018.82007

2. 改进后的模型分析

定义信道传输为非理想状态，主要受到噪声干扰，多路径衰落而导致信道传输失败，在存在非理想信道条件时，站点的传输有以下几种情况：1) 首先站点感知信道是否空闲，如果空闲将不进入退避程序直接传输数据分组，若在传输过程中受到信道的干扰会以概率 $P_{e}$ 导致传输失败而进入下一阶的重传，以 $1 - P_{e}$ 的概率成功传输；2) 若站点感知信道为忙状态时，该站点在传输分组之前需要进入退避程序，并以冻结概率P进行倒计时，直至为“0”后传输分组；3) 数据分组在每一次退避程序结束后都由于传输冲突而一直转入下一阶退避，直至最大阶数m后该分组将进入无限重传状态或丢弃该分组。

结合非理想信道条件和退避算法，我们得出二维离散时间的马尔科夫过程。定义 $b (t)$ 是站点处于退避状态的随机过程，当帧进入退避后以随机值t倒计时， $s (t)$ 为站点在时隙t中的退避阶数i， $b (t)$ 和 $s (t)$ 是退避程序内的离散参数值，不与信道产生冲突，P为帧在传输过程中发生冲突的概率，并且帧的冲突概率与该帧已经遭受的冲突次数无关，表示在站点退避过程中一边进行以概率 $1 - P$ 的时间“1”递减，一边同时感知信道的传输状态。随机窗口大小表示如下：

(1)

其中i为数据帧传输失败进入重传的退避阶数且 $i \in [0, m]$ ，m为最大退避阶数， $W_{0}$ 为最小竞争窗口数， $W_{max}$ 为最大窗口数。结合公式(1)我们可以得到如下的一步转移概率公式：

${\begin{cases} P {i, k | i, k + 1} = 1 - P k \in (0, W_{i} - 3), i \in (0, m) \\ P {0, k | i, 0} = \frac{(1 - P_{r}) P}{W_{0}} k \in (0, W_{0} - 2), i \in (0, m) \\ P {i, k | i - 1, 0} = \frac{P_{r}}{W_{0}} k \in (0, W_{0} - 2), i \in (0, m) \\ P {m, k | m, 0} = \frac{P_{r}}{W_{m}} k \in (0, W_{m} - 2) \\ P {- 1, 0 | i, 0} = (1 - P) (1 - P_{r}) k \in (0, W_{i} - 2) \end{cases}$ (2)

其中 $P_{r}$ 表示数据分组重传概率，P表示冻结概率，等价于系统中其他站点之间的冲突概率。

3. 饱和吞吐量分析

由文献 [2] 两种握手机制的时延图中，我们分别得出两种接入方式下成功传输数据分组的平均时延：

基本接入方式：

$T_{S}^{b a s} = H + E [L] + δ + T_{S I F S} + T_{A C K} + δ + T_{D I F S}$ (3)

RTS/CTS接入方式：

$T_{S}^{r t s} = T_{R T S} + σ + T_{S I F S} + T_{C T S} + σ + T_{S I F S} + H + E [L] + δ + T_{S I F S} + T_{A C K} + δ + T_{D I F S}$ (4)

其中σ，δ， $T_{S I F S}$ ， $T_{D I F S}$ ， $T_{A C K}$ 分别表示信道空闲状态的时延，空间传播时延，短帧间间隔，长帧间间隔以及确认返回帧间隔， $T_{R T S}$ ， $T_{C T S}$ 表示请求发送和清除发送的时延，一个数据在非理想信道中传输错误的原因与误码率(BER)以及该包的分组长度 $E [L]$ 有关，结合平均时延公式(3)和(4)，我们分别得出基本接入机制和RTS/CTS接入机制下的数据分组在信道中传输错误的概率 $P_{e}$ 为：

(5)

定义网络环境下的总站数为n，当数据帧在一个时隙槽期间有一个以上的站点在传输时，其他站点视信道处于忙状态，其概率和冻结概率是相同的，即为：

$P = 1 - {(1 - τ)}^{n}$ (6)

当帧在退避机制中计时到0后，无论传输是否成功，它都与对目的站点进行数据传输，既是在第i阶退避结束后开始传输，这样我们就能表示出一个站点随机选择一个时隙的传输概率τ：

$τ = \sum_{i = - 1}^{m} b_{i, 0} = \frac{(1 - P P_{r}^{m + 2} - (P + P_{r}) P_{r}^{m + 1}) \cdot (2 - 2 P) (1 - 2 P_{r})}{2 {(1 - P)}^{2} (1 - 2 P_{r}) (1 - P_{r}) + ((1 - P_{r}) P + P_{r}) (1 - 2 P_{r}) (W_{0} + 1) + ((1 - P_{r}) P + P_{r}) (1 - {(2 P_{r})}^{m}) W_{0} P_{r}}$ (7)

一个站点传输数据帧失败的概率可以看成包传输失败而再次进入退避程序进行重传的概率，因此，它与重传概率 $P_{r}$ 是等价的：

$\begin{matrix} P_{r}^{b a s} \\ P_{r}^{r t s} \end{matrix}} = {\begin{cases} 1 - {(1 - τ)}^{n} {(1 - B E R)}^{H + E [L] + T_{A C K}} \\ 1 - {(1 - τ)}^{n} {(1 - B E R)}^{T_{R T S} + T_{C T S} + H + E [L] + T_{A C K}} \end{cases}$ (8)

站点之间传输成功的概率的条件是在信道上发送的分组没有错误，并且没有其他站点在相同的时隙发送，结合上述公式得到两种访问方式下成功传输的概率 $P_{S}$ 。

基本访问方式成功传输概率：

$P_{S}^{b a s} = \frac{n τ {(1 - τ)}^{n} {(1 - B E R)}^{H + E [L] + T_{A C K}}}{P}$ (9)

RTS/CTS访问方式成功传输概率：

(10)

综合上述公式，令S为归一化的系统吞吐量，可从如下公式得到：

$S = \frac{E [数据成功传输的平均分组长度]}{E [数据成功传输的平均时延]}$ (11)

将上述公式带入实际参数，得到两种不同接入方式下的饱和吞吐量公式：

$\begin{matrix} \begin{matrix} S^{b a s} \\ S^{r t s} \end{matrix}} = \frac{E [d]}{E [σ]} = \frac{P_{S} \cdot P \cdot E [L]}{(1 - P) σ + P_{S} \cdot T_{S} \cdot P + (1 - P_{S}) \cdot T_{C} \cdot P} \\ = {\begin{cases} \frac{n τ {(1 - τ)}^{n} {(1 - B E R)}^{T_{R T S} + T_{C T S} + H + E [L] + T_{A C K}} \cdot E [L]}{(1 - P) σ + P_{S} \cdot T_{S} \cdot P + (1 - P_{S}) \cdot T_{C} \cdot P} \\ \frac{n τ {(1 - τ)}^{n} {(1 - B E R)}^{H + E [L] + T_{A C K}} \cdot E [L]}{(1 - P) σ + P_{S} \cdot T_{S} \cdot P + (1 - P_{S}) \cdot T_{C} \cdot P} \end{cases} \end{matrix}$ (12)

其中 $T_{S}$ 和 $T_{C}$ 为在非理想信道存在的情况下数据分组传输成功和失败所产生的时延，由公式(12)易知基本接入机制和RTS/CTS访问机制的吞吐量数值结果是不同的。

4. 数值分析

本文模型工作环境为物理层采用的直接序列扩频(Direct Hopping SpreadSpectrum, DSSS)系列，在2.4 GHz频段上进行数据传输，局域网内的所有数据帧都在IEEE 802.11协议服务标准下进行站点间传送数据，对IEEE 802.11 DCF协议下的基本接入机制和RTS/CTS接入机制两种情况的饱和吞吐量仿真效果加以验证。具体各参数仿真值为最小退避窗口值 $W_{0} = 32$ ，最大退避窗口值为 $W_{\max} = 1024$ ，最大退避阶数为 $i = 5$ ，最大重传次数 $m = 8$ ，物理层信头时延 $H = 192 bit$ ，MAC层信头时延为224 bit，数据分组平均长度为 $E [L] = 8184 bit$ ，RTS，CTS，ACK时延长度分别为 $163 bit + H$ , $112 bit + H$ , $112 bit + H$ ，空闲时隙 $σ = 20 μ s$ ，空间传播时延 $δ = 1 μ s$ ，帧间间隔SIFS和DIFS分别为10 μs和50 μs。结合给出的参数值和具体公式，我们分别得出不同接入方式下的以5.5 Mb/s，11 Mb/s传输速率的饱和吞吐量曲线。

从图1中可以看出，随着网络总站点数n增大，数据在信道中传输的冲突概率增大，站点间的传输成功率下降，吞吐量随之降低。其次，基本接入方式下以5.5 Mb/s传输速率的吞吐量要高于11 Mb/s传输速率的吞吐量，这是由于分组在信道中传输时，若以较快速率传输会导致数据帧在信道中更替过快，造成分组之间的紊乱而传输冲突，使得吞吐量减少。图1中当误码率增大时，分组在传输过程中受到信道的影响直接导致传输失败的概率增加，从而吞吐量较大程度下降。从图2中看出，由于本文假设系统环境不存在隐藏终端问题，图2整个系统的饱和吞吐量值略小于图1，并且该吞吐量同样随着总站数增加而减少，与图1不同的是图2吞吐量的下降趋势相对缓慢。图2中低传输速率吞吐量同样高于高传输

Figure 1. Saturation throughput graph for basic access method

图1. 基本接入方式的饱和吞吐量图

Figure 2. Saturation throughput graph for RTS/CTS access method

图2. RTS/CTS接入方式的饱和吞吐量图

速率吞吐量，并且与图1相比，由于RTS/CTS是四路握手机制，控制帧较多，信道中冲突概率更大，因此吞吐量下降趋势更明显。

图1和图2中系统的饱和吞吐量都随着误码率的增加而降低，特别当误码率达到 $5 \times 10^{- 5}$ 以上时，基本接入方式和RTS/CTS接入方式的吞吐量曲线基本没有较大程度的变化，也不会随着站点数量的增加而改变，这说明在非理想信道条件下，误码率为一定值时，系统的吞吐量受到的主要影响因素取决于信道条件而不是站点之间的碰撞或冲突。

5. 结束语

本文考虑通信环境的实际情况，讨论系统处于非理想信道条件下的传输质量，并将原模型的二维离散时间的马尔科夫链做出改进，即在退避算法中加入冻结概率来减少站点间的冲突，并通过公式的推导求得IEEE 802.11 DCF协议在两种接入机制下的饱和吞吐量表达式，最后结合模拟仿真分析两种情况下的吞吐量走向并加以验证，为以后进一步的理论研究和实际工程中提供理论参考。

资助信息

国家自然科学基金项目资助(61663024)。

参考文献

[1]	Bianchi, G. (2006) Performance Analysis of the IEEE 802.11 Distributed Coordination Function. IEEE Press, New York, 18(3): 535-547.
[2]	Weng, C.E. and Chen, H.C. (2016) The Performance Evaluation of IEEE 802.11 DCF Using Markov Chain Model for Wireless LANs. Advanced Materials. Springer International Publishing, Germany, 144-149.
[3]	Tuysuz, M.F. and Mantar, H.A. (2015) Exploiting the Channel Using Uninterrupted Collision-Free MAC Adaptation over IEEE 802.11 WLANs. Wireless Commu-nications & Mobile Computing, 15, 889-909. https://doi.org/10.1002/wcm.2391
[4]	Hong, K., Kim, J.P., Kim, M.S., et al. (2016) Channel Measurement-Based Access Point Selection in IEEE 802.11 WLANs. Pervasive & Mobile Computing, 30, 58-70. https://doi.org/10.1016/j.pmcj.2015.10.018
[5]	Petruzzella, V., Vergari, R.I., Boffoli, D., et al. (2005) Saturation Throughput Analysis of IEEE 802.11 Wireless LANs for a Lossy Channel. IEEE Communications Letters, 9, 100-102. https://doi.org/10.1109/LCOMM.2005.02011
[6]	Panthum, T., Sittichivapark, S. and Sartthong, J. (2016) Performance Anal-ysis of EIED Backoff Algorithm of the IEEE 802.11 MAC under Fading Channel Errors. International Joint Conference on Computer Science and Software Engineering, IEEE, 1-6.

友情链接