论文部分内容阅读
摘要：研究基于介质访问控制协议（MAC）的分布式争用问题的主要焦点就是设计有效的具有高吞吐量性能的MAC协议。该文提出在无线局域网中基于MAC协议的有效争用方法，即改良的冲突解决算法（DCR）。该算法主要做了以下几方面的改良和创新：对所有现用网点主动的分配补偿时间，提高解决冲突的速度；当确定固定数量的连续空闲时间片被探测到时，对成功包传输的站点使用较小的争用窗口，以指数级速度减少补偿时间片和减少空闲时间片的平均数。该文提出的改良冲突解决算法提供了高吞吐量性能和在局域网中的低执行时间。
关键词：介质访问控制协议（MAC）；补偿时间；改良的冲突解决算法（DCR）
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)35-2123-03
DCR Algorithm of MAC Protocols Based on IEEE 802.11b Wireless Networks
XIAO Yi1,2, LIU Lian-hao1
(1.School of Information Science and Engineering, Central South University,Changsha 410083,China;2.Information Science and Technology College of Hunan Agricultural University, Changsha 410128,China)
Abstract: Design of efficient Medium Access Control (MAC) protocols with both high throughput performances is a major focus in distributed contention‐based MAC protocol research. In this paper, we propose an efficient contention‐based MAC protocol for wireless Local Area Networks, namely, the Developed Collision Resolution (DCR) algorithm. This algorithm is developed based on the following innovative ideas: to speed up the collision resolution, we actively redistribute the backoff timers for all active nodes; to reduce the average number of idle slots, we use smaller contention window sizes for nodes with successful packet transmissions and reduce the backoff timers exponentially fast when a fixed number of consecutive idle slots are detected. We show that the proposed DCR algorithm provides high throughput performance and low latency in wireless LANs.
Key words:MAC;backoff;DCR algorithm
1 简介
无线网络中基于介质访问控制协议（MAC）的研究以ALOHA开始，之后相继提出MACA、 MACAW、FAMA 和 DFWMAC，用于合并CSMA技术和避免冲突的RTS和CTS的握手机制。目前最流行的基于争用问题无线MAC协议是CSMA/CA，已经成为IEEE 802.11b MAC协议的基础[1]。但是，我们可以看到如果活动用户数目增加，而由于冲突率非常高，IEEE 802.11b MAC协议的吞吐量性能就会急剧下降。很多研究都集中在分析和提高IEEE 802.11b MAC协议的表现。
要增加基于MAC协议的吞吐量性能，尽量减少每个争用循环里的消耗是一种有效的冲突解决机制[2]。在本文中，我们提出一种新的有效的基于MAC的分布式争用算法，也就是改良的冲突解决算法（DCR）。我们观察到在每个争用循环中，MAC算法来自于因为补偿产生的包冲突和空闲时间片的浪费。DCR算法将通过扩大争用决定中的冲突位置和推迟位置的争用窗口来达到迅速解决冲突的目的。
2 IEEE 802.11b 介质访问控制
最流行的基于争用的MAC协议就是CSMA/CA，目前广泛应用于IEEE 802.11b局域网中。
一个包传送循环是一个从源站点成功发出的包传送开始并跟随着从目标站点发出的承认（ACK）[3]。一般的IEEE 802.11b MAC协议是这样操作的（为简单起见，我们只考虑分布式调和功能，而没有考虑RTS-CTS握手）：如果一个站点有一个包需要发送，它会通过载波感觉机制来检查媒介状态。如果媒介是空闲的，那么传送将会进行。如果媒介是繁忙的，站点将会等待，直到媒介为空闲状态，而补偿程序随之被调用。站点将会根据当前争用窗口（CW）大小将补偿时间设置一个随机补偿时间。
补偿时间（BT）= 随机数×aSlotTime
其中，随机数是从0到CW-1中随机产生的整数。
在分布协调功能帧间隔（DIFS）空闲时间后，站点会执行补偿程序，通过载波感觉机制来判断在每个补偿时间片内是否有活动存在。如果在一个特定的补偿时间片内，媒介被判断为空，然后补偿程序就会通过aslottime减少它的补偿时间。如果在某个站点中，媒介一直都被判断为繁忙，则补偿程序就暂缓执行。如媒介处于DIFS空闲时间，补偿程序就会重新开始。只要补偿时间为0，传送就会开始。源站点在给目标站点传送了一个数据包后，如果源站点收到了一个承认（ACK），并且在这个短的帧间间隔（SIFS）空闲时期没有发生错误，传送过程将会被认为成功完成。这样的话，源站点的争用窗口将被设置为初始（最小化）状态。如果这个传送并没有成功完成，争用窗口大小将被扩大，这个过程被称作是二进制指数补偿（BEB），可用来解决争用循环中的冲突。更详细的操作可以在参考文献4中找到。
3 改进后的无线局域网冲突解决算法
3.1 改进后的冲突解决算法的基本思想
在争用期间，导致IEEE 802.11b MAC协议的传送失败（我们只考虑因为包冲突产生的失败），主要是由于补偿影响了吞吐量性能和空闲时间片。
在高交通负荷下（如：所有的M站点都有包要传送），基于各态历经性假设，我们可以得到下面吞吐量表达式：
（公式 1）
式中E[Nc]表示一个有效传送时间内（或者是一个有效的传输循环）的平均冲突数目。E[Bc]是由每个争用期间补偿产生的空闲时间片的平均个数。ts表示时间片长度（例如：aSlottime），m是平均包长度。
对这个结果来说，最好的脚本将是如下内容：一个成功的包传输将跟随着另一个包传输， E[Nc] = 0，E[Bc] =0，这样吞吐量将是：
（公式 2）
只有完美的安排才能出现这样的结果，在这种情况下，每个站点都能发送包，在每个争用区间，ptrans(i)的值如下：
(公式3)
这意味着如果当今的包传输权利被分配到i站点，且只有i站点可以传送，全部其他站点将延迟他们的包传输。
假设在一些随机补偿计划下，我们假设补偿时间随机选择，那么在当前争用期间，站点i传送包的可能性将取决于补偿时间。
（公式 4）
式中Bi是站点i的补偿时间。这意味着，如果站点i的补偿定时器为0（Bi=0），那么它的补偿时间也为0（BT = BiaSlotTime = 0），站点i可以立即传送包，表明站点i在争用期间可以以1概率传送包。如果站点i的补偿定时器为∞，那么他的补偿时间也为∞，表明站点i在争用期间可以以0概率传送包。依上所述，（公式3）就转变成（公式5）：
（公式 5）
因此，我们可以得出以下结论，如果我们可以如此改进基于争用的MAC算法：在每个争用期间，分配一个补偿定时器0给一个站点，同时分配给其他站点补偿定时器∞，我们就可以达到完美的调度，从而得到最大的吞吐量。不幸的是，这种基于争用的MAC算法在实际中并不存在。然而，这也给我们提供了一个在MAC协议设计中怎样去提高吞吐量性能的基本想法。我们可以使用完美计划中的操作特性去设计接近完美计划行为且更有效的基于争用的MAC算法。
3.2 改进后的冲突解决算法
IEEE 802.11b 介质存储控制协议的主要缺点是，当现用站点数目增加时，冲突解决缓慢。在改良的冲突解决算法中，我们对延迟的站点改变其争用窗口大小，并且对所有潜在的发生站点重新分配补偿时间，动态避免“将来”的潜在冲突[5]。用这样的方法，我们可以很快的解决包冲突的问题。更重要的是，改良的算法保留了IEEE 802.11b介质存储控制的实现的简单性。
改良的冲突解决算法具有以下特点：
1) 使用比IEEE 802.11b MAC更小的初始化（最小化）争用窗口minCW；
2) 使用比IEEE 802.11b MAC更大的最大化争用窗口maxCW；
3) 当位于冲突站和延迟站时，提高该站的争用窗口大小；
4) 当一定数量的连续空闲时间片被探测到时，补偿时间片成指数级速度减少。
详细的DCR算法根据站点的情况描述如下：
1) 补偿过程：所有现用站点将监控介质。如果站点检测到时间片的介质，将用一个时间片来减少补偿时间（BT），即：BTnew =BTold-aSlotTime (or slot)。当其补偿时间片为零时，该站点将传输一个包。如果有[(minCW+1)×2-1]个连续空闲时间片被探测到，其补偿时间片将以指数级速度减少，即：BTnew = BTold / 2 (如果 BTnew < aSlotTime,，则BTnew = 0)。对于网络的影响就是：当一个站点耗尽了所有的传输包的时候，不必要浪费的闲置补偿时间片将会减少。
2) 传输失败（包冲突）：如果一个站点注意到其包传输失败，很可能是由于包冲突引起（即：如果接收从目标接收站传来的确认信息失败），该站争用窗口的大小就应该增加并且选择一个随机补偿时间（BT），即CW = min(maxCW,CW×2)，BT = uniform(0,CW – 1) aSlotTime其中，uniform(a，,b)的含义是从a和b的均匀分布中随机提取的数据，CW表示当前争用窗口大小。
3) 成功包传输：如果一个站已经成功传输了包，则其争用窗口大小将被还原到初始化（最小化）争用窗口大小（minCW），并且根据CW = minCW，BT = uniform(0, CW-1) aSlotTime公式来选择一个随机补偿时间值；
4) 延迟站：对于在延迟站中的站点而言，无论什么时候探测到一个新的忙用时间的开始（意味着在介质中冲突或者包传输的开始），该站点将增加其争用窗口大小并且像如下方式选择一个新的随机补偿时间：CW = min(maxCW, CW×2), BT = uniform(0, CW-1) ×aSlotTime。
在DCR算法中，成功传输包的站点将拥有最小争用窗口和最少补偿时间片。因此，该站点将有更高概率来获取介质的存储，而其他站点则拥有相对大的争用窗口和相对多的补偿时间片。在一个站点成功传输了一系列包之后，另外站点可能争用到资源，随之该新站点将在一段时间内拥有更高的获取介质存储概率。
4 模拟和性能估算
以下演示了对DCR算法和使用DSSS规格的IEEE802.11b MAC的模拟学习。模拟工具是OPNET。在模拟中使用的参数如表1所示（参数基于IEEE802.11b网络配置）。
从图1可发现：从第三秒开始，使用DCR算法的网络平均吞吐量比没有使用DCR算法的吞吐量要提高了很多。在20秒之后，使用DCR算法的平均吞吐量达到稳定状态。
图1 平均吞吐量比较结果
图2是装载这两种算法所需的平均时间的比较。如图所示，在模拟开始阶段，也就是在0s - 2s这个时间段，网络达到了装载高峰，接下来开始趋于稳定。由于在DCR算法中使用了更小的最小化窗口CW和更大的最大化窗口CW，冲突产生概率比没有使用DCR算法时降低了很多。网络装载速度比没有使用DCR算法前减慢了很多。
图3显示延迟的模拟结果。在大约25秒以后，使用DCR算法的延时一直低于2秒，而没有使用DCR算法的延时则大于2秒。对平均延时结果的比较得出，使用DCR算法的平均延时时间低于1.75秒，比没有使用DCR算法的平均延时时间要短很多。
从上面所有的性能分析得出：当站点数目增加到50个以上时，没有使用DCR算法的IEEE 802.11b MAC算法的性能较差。而DCR算法将更有效的提高无线局域网性能。因为在DCR算法中，除了具有正在成功传输包的站点外的所有站点，无论系统是成功的传输包还是遇到冲突，站点都会增加其争用窗口大小。这也就意味着，所有站点都能迅速获取合适大小的争用窗口来防止将来的冲突，因此冲突概率将被降低到非常小的一个值。同时，成功传输包的站点拥有最小窗体大小3，这个值比IEEE 802.11B MAC算法中的最小争用窗口值31（minCW=31）小了很多。和没有使用DCR算法的IEEE 802.11B MAC比较起来，DCR算法把浪费的介质闲置时间降低到了一个相对很小的值。
关键词：介质访问控制协议（MAC）；补偿时间；改良的冲突解决算法（DCR）
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)35-2123-03
DCR Algorithm of MAC Protocols Based on IEEE 802.11b Wireless Networks
XIAO Yi1,2, LIU Lian-hao1
(1.School of Information Science and Engineering, Central South University,Changsha 410083,China;2.Information Science and Technology College of Hunan Agricultural University, Changsha 410128,China)
Abstract: Design of efficient Medium Access Control (MAC) protocols with both high throughput performances is a major focus in distributed contention‐based MAC protocol research. In this paper, we propose an efficient contention‐based MAC protocol for wireless Local Area Networks, namely, the Developed Collision Resolution (DCR) algorithm. This algorithm is developed based on the following innovative ideas: to speed up the collision resolution, we actively redistribute the backoff timers for all active nodes; to reduce the average number of idle slots, we use smaller contention window sizes for nodes with successful packet transmissions and reduce the backoff timers exponentially fast when a fixed number of consecutive idle slots are detected. We show that the proposed DCR algorithm provides high throughput performance and low latency in wireless LANs.
Key words:MAC;backoff;DCR algorithm
1 简介
无线网络中基于介质访问控制协议（MAC）的研究以ALOHA开始，之后相继提出MACA、 MACAW、FAMA 和 DFWMAC，用于合并CSMA技术和避免冲突的RTS和CTS的握手机制。目前最流行的基于争用问题无线MAC协议是CSMA/CA，已经成为IEEE 802.11b MAC协议的基础[1]。但是，我们可以看到如果活动用户数目增加，而由于冲突率非常高，IEEE 802.11b MAC协议的吞吐量性能就会急剧下降。很多研究都集中在分析和提高IEEE 802.11b MAC协议的表现。
要增加基于MAC协议的吞吐量性能，尽量减少每个争用循环里的消耗是一种有效的冲突解决机制[2]。在本文中，我们提出一种新的有效的基于MAC的分布式争用算法，也就是改良的冲突解决算法（DCR）。我们观察到在每个争用循环中，MAC算法来自于因为补偿产生的包冲突和空闲时间片的浪费。DCR算法将通过扩大争用决定中的冲突位置和推迟位置的争用窗口来达到迅速解决冲突的目的。
2 IEEE 802.11b 介质访问控制
最流行的基于争用的MAC协议就是CSMA/CA，目前广泛应用于IEEE 802.11b局域网中。
一个包传送循环是一个从源站点成功发出的包传送开始并跟随着从目标站点发出的承认（ACK）[3]。一般的IEEE 802.11b MAC协议是这样操作的（为简单起见，我们只考虑分布式调和功能，而没有考虑RTS-CTS握手）：如果一个站点有一个包需要发送，它会通过载波感觉机制来检查媒介状态。如果媒介是空闲的，那么传送将会进行。如果媒介是繁忙的，站点将会等待，直到媒介为空闲状态，而补偿程序随之被调用。站点将会根据当前争用窗口（CW）大小将补偿时间设置一个随机补偿时间。
补偿时间（BT）= 随机数×aSlotTime
其中，随机数是从0到CW-1中随机产生的整数。
在分布协调功能帧间隔（DIFS）空闲时间后，站点会执行补偿程序，通过载波感觉机制来判断在每个补偿时间片内是否有活动存在。如果在一个特定的补偿时间片内，媒介被判断为空，然后补偿程序就会通过aslottime减少它的补偿时间。如果在某个站点中，媒介一直都被判断为繁忙，则补偿程序就暂缓执行。如媒介处于DIFS空闲时间，补偿程序就会重新开始。只要补偿时间为0，传送就会开始。源站点在给目标站点传送了一个数据包后，如果源站点收到了一个承认（ACK），并且在这个短的帧间间隔（SIFS）空闲时期没有发生错误，传送过程将会被认为成功完成。这样的话，源站点的争用窗口将被设置为初始（最小化）状态。如果这个传送并没有成功完成，争用窗口大小将被扩大，这个过程被称作是二进制指数补偿（BEB），可用来解决争用循环中的冲突。更详细的操作可以在参考文献4中找到。
3 改进后的无线局域网冲突解决算法
3.1 改进后的冲突解决算法的基本思想
在争用期间，导致IEEE 802.11b MAC协议的传送失败（我们只考虑因为包冲突产生的失败），主要是由于补偿影响了吞吐量性能和空闲时间片。
在高交通负荷下（如：所有的M站点都有包要传送），基于各态历经性假设，我们可以得到下面吞吐量表达式：
式中E[Nc]表示一个有效传送时间内（或者是一个有效的传输循环）的平均冲突数目。E[Bc]是由每个争用期间补偿产生的空闲时间片的平均个数。ts表示时间片长度（例如：aSlottime），m是平均包长度。
对这个结果来说，最好的脚本将是如下内容：一个成功的包传输将跟随着另一个包传输， E[Nc] = 0，E[Bc] =0，这样吞吐量将是：
只有完美的安排才能出现这样的结果，在这种情况下，每个站点都能发送包，在每个争用区间，ptrans(i)的值如下：
这意味着如果当今的包传输权利被分配到i站点，且只有i站点可以传送，全部其他站点将延迟他们的包传输。
假设在一些随机补偿计划下，我们假设补偿时间随机选择，那么在当前争用期间，站点i传送包的可能性将取决于补偿时间。
式中Bi是站点i的补偿时间。这意味着，如果站点i的补偿定时器为0（Bi=0），那么它的补偿时间也为0（BT = BiaSlotTime = 0），站点i可以立即传送包，表明站点i在争用期间可以以1概率传送包。如果站点i的补偿定时器为∞，那么他的补偿时间也为∞，表明站点i在争用期间可以以0概率传送包。依上所述，（公式3）就转变成（公式5）：
因此，我们可以得出以下结论，如果我们可以如此改进基于争用的MAC算法：在每个争用期间，分配一个补偿定时器0给一个站点，同时分配给其他站点补偿定时器∞，我们就可以达到完美的调度，从而得到最大的吞吐量。不幸的是，这种基于争用的MAC算法在实际中并不存在。然而，这也给我们提供了一个在MAC协议设计中怎样去提高吞吐量性能的基本想法。我们可以使用完美计划中的操作特性去设计接近完美计划行为且更有效的基于争用的MAC算法。
3.2 改进后的冲突解决算法
IEEE 802.11b 介质存储控制协议的主要缺点是，当现用站点数目增加时，冲突解决缓慢。在改良的冲突解决算法中，我们对延迟的站点改变其争用窗口大小，并且对所有潜在的发生站点重新分配补偿时间，动态避免“将来”的潜在冲突[5]。用这样的方法，我们可以很快的解决包冲突的问题。更重要的是，改良的算法保留了IEEE 802.11b介质存储控制的实现的简单性。
改良的冲突解决算法具有以下特点：
1) 使用比IEEE 802.11b MAC更小的初始化（最小化）争用窗口minCW；
2) 使用比IEEE 802.11b MAC更大的最大化争用窗口maxCW；
3) 当位于冲突站和延迟站时，提高该站的争用窗口大小；
4) 当一定数量的连续空闲时间片被探测到时，补偿时间片成指数级速度减少。
详细的DCR算法根据站点的情况描述如下：
1) 补偿过程：所有现用站点将监控介质。如果站点检测到时间片的介质，将用一个时间片来减少补偿时间（BT），即：BTnew =BTold-aSlotTime (or slot)。当其补偿时间片为零时，该站点将传输一个包。如果有[(minCW+1)×2-1]个连续空闲时间片被探测到，其补偿时间片将以指数级速度减少，即：BTnew = BTold / 2 (如果 BTnew < aSlotTime,，则BTnew = 0)。对于网络的影响就是：当一个站点耗尽了所有的传输包的时候，不必要浪费的闲置补偿时间片将会减少。
2) 传输失败（包冲突）：如果一个站点注意到其包传输失败，很可能是由于包冲突引起（即：如果接收从目标接收站传来的确认信息失败），该站争用窗口的大小就应该增加并且选择一个随机补偿时间（BT），即CW = min(maxCW,CW×2)，BT = uniform(0,CW – 1) aSlotTime其中，uniform(a，,b)的含义是从a和b的均匀分布中随机提取的数据，CW表示当前争用窗口大小。
3) 成功包传输：如果一个站已经成功传输了包，则其争用窗口大小将被还原到初始化（最小化）争用窗口大小（minCW），并且根据CW = minCW，BT = uniform(0, CW-1) aSlotTime公式来选择一个随机补偿时间值；
4) 延迟站：对于在延迟站中的站点而言，无论什么时候探测到一个新的忙用时间的开始（意味着在介质中冲突或者包传输的开始），该站点将增加其争用窗口大小并且像如下方式选择一个新的随机补偿时间：CW = min(maxCW, CW×2), BT = uniform(0, CW-1) ×aSlotTime。
在DCR算法中，成功传输包的站点将拥有最小争用窗口和最少补偿时间片。因此，该站点将有更高概率来获取介质的存储，而其他站点则拥有相对大的争用窗口和相对多的补偿时间片。在一个站点成功传输了一系列包之后，另外站点可能争用到资源，随之该新站点将在一段时间内拥有更高的获取介质存储概率。
4 模拟和性能估算
以下演示了对DCR算法和使用DSSS规格的IEEE802.11b MAC的模拟学习。模拟工具是OPNET。在模拟中使用的参数如表1所示（参数基于IEEE802.11b网络配置）。
从图1可发现：从第三秒开始，使用DCR算法的网络平均吞吐量比没有使用DCR算法的吞吐量要提高了很多。在20秒之后，使用DCR算法的平均吞吐量达到稳定状态。
图1 平均吞吐量比较结果
图2是装载这两种算法所需的平均时间的比较。如图所示，在模拟开始阶段，也就是在0s - 2s这个时间段，网络达到了装载高峰，接下来开始趋于稳定。由于在DCR算法中使用了更小的最小化窗口CW和更大的最大化窗口CW，冲突产生概率比没有使用DCR算法时降低了很多。网络装载速度比没有使用DCR算法前减慢了很多。
图3显示延迟的模拟结果。在大约25秒以后，使用DCR算法的延时一直低于2秒，而没有使用DCR算法的延时则大于2秒。对平均延时结果的比较得出，使用DCR算法的平均延时时间低于1.75秒，比没有使用DCR算法的平均延时时间要短很多。
从上面所有的性能分析得出：当站点数目增加到50个以上时，没有使用DCR算法的IEEE 802.11b MAC算法的性能较差。而DCR算法将更有效的提高无线局域网性能。因为在DCR算法中，除了具有正在成功传输包的站点外的所有站点，无论系统是成功的传输包还是遇到冲突，站点都会增加其争用窗口大小。这也就意味着，所有站点都能迅速获取合适大小的争用窗口来防止将来的冲突，因此冲突概率将被降低到非常小的一个值。同时，成功传输包的站点拥有最小窗体大小3，这个值比IEEE 802.11B MAC算法中的最小争用窗口值31（minCW=31）小了很多。和没有使用DCR算法的IEEE 802.11B MAC比较起来，DCR算法把浪费的介质闲置时间降低到了一个相对很小的值。