IEEE 802.11用于ad hoc网络的性能问题及改进方法
发布时间：2015-07-09 11:30
摘 要 本文介绍了基本的802.11DCF协议的操作原理。在Ad Hoc 中，分析了IEEE802.11在特定网络场景下存在的不同性能问题，及其对高层协议的性能影响。依据仿真记录文件,我们分析了仿真结果并且揭露了这些问题存在的根本原因。最后总结了主要的改进方法。
关键词 无线自组织网络；MAC协议；802.11DCF；公平性；吞吐量
1 引言
无线ad hoc 网络是由一组带有无线收发装置的移动节点组成的一个多跳的自治系统。它不需要依赖事先构建的通信基础设施。每个移动节点既作为路由器又作为主机。在ad hoc 网络协议栈中，信道接入协议运行在物理层之上，是所有报文在无线信道上发送和接收的直接控制者，它的性能好坏直接关系着信道的利用率和整个网络的性能。目前没有专门为无线自组织网络设计的MAC协议。
IEEE802.11DCF最初是为无线局域网设计的，然而目前大多数ad hoc网络协议，把IEEE802.11作为底层的通信协议。尽管802.11中的DCF机制可以在没有基础设施的情况下移动的接入无线媒体，但是在多跳性方面不能提供支持。所以在ad hoc 网络中使用802.11协议会引起一些性能问题。
2 IEEE 802.11 DCF协议的操作原理
IEEE 802.11DCF[1]继承了带冲突检测的载波监听多址接入（CSMA/CA）协议。在协议中，为了避免冲突，发送者在发送帧之前要先监听信道的忙闲状态，如果信道空闲并且持续空闲DIFS（DCF Interval Frame Space）的时间，则发送帧。如果在这段时间内信道变忙，发送者就执行退避算法，计算一个随机的退避窗口。一直等到信道空闲，并持续空闲DIFS的时间后，发送者开始以时隙为单位递减退避时间。如果递减到零，就开始发送；如果在递减过程中信道又变忙，节点就停止递减时间，等待信道空闲并持续DIFS的时间后继续递减。当有冲突发生的时候，发送者的竞争窗口就加倍，相同的帧用前面的过程被重传。如果再发生冲突，竞争窗口再加倍直到达到最大竞争窗口。在达到固定重传次数之后，该帧被抛弃，竞争窗口被重置为最小。成功传输该帧后，竞争窗口也被重置。
图 1. IEEE 802.11协议的操作过程
图1描述了在通信范围内的三个节点A B C。在开始，节点A有帧要发送。因为此时介质是空闲的，所以在DIFS之后节点A发送该帧。然后接收者B给出确认。如果在以前的交换还在进行的时候，节点A又有新的帧要发送，A必须执行退避算法，在例子中退避2个时隙。同时C也要发送帧到B，介质被检测到空闲，只要DIFS之后就可以发送。碰巧，A和C选择在同时开始发送，因此在节点B处发生冲突。因为没有确认发出，两个发送者以两倍的竞争窗口重传。此时，C赢得竞争，它的发送阻止了A的2个时隙的退避递减。在数据确认交换完成以后，A重启2个剩余时隙的退避过程。
3 主要的性能问题及仿真分析
文中的仿真是基于NS-2网络仿真器。仿真器中所有节点通过使用相同的半双工无线链路通信，带宽是2Mb/s。节点的最大传输范围是250m 。队列缓存为50个包，且队列是优先丢尾（PriDropTail）的方式。路由协议是AODV。仿真时间是200秒。
图2. 仿真拓扑
3.1暴露终端问题
Ad Hoc网络的多跳共享广播信道的直接影响就是报文的冲突和节点的地理位置有关。在这个网络中，报文冲突只是局部事件，不是所有节点都能感知到。一个节点正确收到了一个报文，而该报文可能在另一个节点处发生冲突。也可能报文在接收节点处发生冲突，而发送节点根本不知道。就是说发送节点和接收节点感知到的信道状况不一定相同。这就容易引起暴露终端问题。
一个节点在发送者的覆盖范围之内，但是在接收者的覆盖范围之外，该节点就叫做暴露终端。暴露终端分为暴露发送终端和暴露接收终端。暴露终端因听到发送节点的发送而延迟发送。但是因为它在接收节点的通信范围之外，它的发送实际上并不会造成冲突。这就引入不必要的延迟，造成信道利用率的下降，能量的浪费。
在图2a中，在2向1发送数据时，3只听到RTS,知道自己是暴露终端，认为可以向4发送数据。3向4发送RTS，在单信道条件下，来自4的CTS会与2的发送的数据报文在3处发生冲突，即3收不到4的CTS这就是暴露发送终端问题。显然暴露终端问题在单信道条件下使用握手机制无法解决。如果4要向暴露终端3发送数据，来自4的RTS会与2发送的数据报文在3处冲突，3收不到来自4的RTS。这是暴露接收终端问题。分析可知，这个问题使用单信道也是不可能解决的。
3.2 不公平性
第一类 长期公平性问题 有些数据流长期占用信道，从而捕获信道。而另一些流几乎不能接入信道，造成“饿死”现象。
（a）长期公平性问题
(b)吞吐量随着跳数的变化
（c）有无RTS/CTS时的吞吐量比较
图 3 仿真结果
在图2b中先考虑发送者之间的链路是通信链路，发送者1和5是完全独立的，异步工作的。这种情况在低吞吐量时，或者当1和5之间有障碍物时都会发生。而且接收者和它们相应的发送者的距离足够近，发送者不发生冲突。
当节点3要发送的时候，它必须等节点1和5同时不发送。因为节点1和5是相互独立的，他们同时不发送的时间也是不一致的，所以节点3看到介质忙的时候比另外两个发送者要多。这个在介质方面基本的不平衡导致一个严重的不公平性问题，3到4的流占介质容量的百分之十五左右，然而其它两个流占容量的百分之七十五。
在这种网络拓扑下，长期不公平性源于一些发送者是相互独立的，意识不到彼此，从而防止了某个发送者接入介质。图3a显示了随着包的大小每个发送者获得的吞吐量。外边两个发送者的吞吐量随着包的增大而增大，然而中间发送者的吞吐量仍然是常量。现在考虑发送者不在通信范围内，而是在触发EIFS的距离内，如图2b所示，这种情况因为使用EIFS更糟糕，因为中间的发送节点不仅要等待另外两个发送者同时不发送，而且必须等待它们同时不发送的时间超过EIFS。和前面的情况相比，由于DCF中更长的固定的等待时间，不公平性被加剧。
第二类 短期公平性问题 某个节点的帧连续发送，其它节点只能等待。
短期不公平现象是由于802.11中的BEB算法在一个节点成功发送之后把竞争窗口重新设为最小，这样总是有利于前一次成功发送的节点短时间内再次竞争信道。短期不公平现象是由于CW变化过于剧烈而造成的，所以这一问题的解决可以通过减慢CW的减小速度。比如乘法增加线性减小算法。
3.3 吞吐量下降
如图3b所示，在ad hoc网络中随着跳数的增加吞吐量下降。在第二个和第三个节点发生多个冲突，又引起EIFS问题。所以有很少的分组到达第四个节点，这个节点传送到目的节点的分组就更少了。
我们还发现在图2c所示的多跳自组织网络中，有RTS-CTS比没有时的吞吐量下降,仿真结果如图3c所示。这是因为有RTS-CTS时，空间复用的概率减小。例如没有RTS-CTS时，节点1，2的通信可以和节点4，5的通信同时进行。然而有的时候，如果节点4正在向5发送分组，节点2因为监听到4的RTS并设置其NAV，就不能回复节点1的RTS。所以节点1，2的通信就不能同时进行。这就降低了空间复用的概率，从而导致了吞吐量的大幅下降。
3.4 对传输层的性能影响和分析
在图2c中的节点1和节点5之间建立一条TCP连接，FTP流从1.0s开始，120s结束。路由协议为AODV。每隔一秒统计一次TCP的吞吐量，结果如图4所示。
从图中看出TCP流的吞吐量很不稳定。在仿真时间内有多次达到0，这表明，在相应的1s内，成功发送的TCP报文数为0。我们根据仿真的记录文件（trace file）来分析造成这种不稳定的原因。
图4. TCP的吞吐量
我们从某一个TCP吞吐量为零的时间段来分析，发现节点1没有发送新的TCP段的原因是发送方没有收到接受方的ACK，而ACK没有到达的原因是节点4因达到重传次数的最大值而认为到节点3的链路故障，从而触发新的路由发现过程，直到节点5重新发现到节点1的路由。我们再看一下为什么节点4发送了7次RTS都没有收到节点3的CTS。其中一部分原因是因为节点4的发送和节点2的发送在节点3处发生冲突，更主要的原因是，尽管节点3收到了RTS但是由于IEEE 802.11 DCF采用虚载波监听方式，在收到RTS之前，节点3已经收到节点2的用于预留信道的CTS，设置其网络分配矢量NAV(Network Allocation Vector)，在NAV不为零的过程中节点3并不发送CTS。此时显示出了RTS/CTS的无效性。当节点1成功发送完一个数据帧之后，它将在[0，CWmin-1]之间按均匀分布随机选择一个退避时间。而节点4由于多次重试，按照IEEE 802.11 DCF的二进制指数退避机制，它将在[0, 2m*CWmin-1]之间选择退避时间，m为已经重发的次数。这样，节点在竞争信道的时候更有利，它将比节点4更早的接入信道发送RTS。这就是不公平性问题。节点2收到RTS后回复CTS，节点3收到 CTS又设置NAV，然后，即使节点3收到节点4的RTS也不回复CTS。重复前面的过程，直到最后节点4重发次数超出限制。
我们从上面的分析看出传输层的不稳定性源于IEEE802.11的MAC层。由于暴露站问题和冲突使得中间站无法到达它的下一跳。而802.11DCF的BEB退避机制使得这一情况更糟糕。
有些拓扑情况可能同时出现上面几种问题。一般在信道容量没有超载的时候，不会出现性能问题。但是由于无线带宽的贫乏和应用需求的不断增加，超载现象时常发生。上面这些问题不是孤立存在的。它们是相互联系，相互影响的。暴露站问题会引起吞吐量的下降，传输层的不稳定。公平性和吞吐量是一对矛盾，一方性能的提高往往会引起另一方性能的下降。如何找到它们之间的折中点常常是人们的研究课题。
4 解决问题方法和改进
我们可以从几个方面来改进IEEE 802.11DCF的性能。目前最主要的方法的是改进退避算法。
通过改进退避算法，可以使MAC协议在吞吐量、公平性、稳定性等一个或几个方面得到性能改善。根据改进退避算法的方法不同，主要又分为以下两类：
(1)改进CW更新规则类
因为网络中节点对信道的竞争激烈程度并不一定变化很快，成功发送报文后将CW重置为最小值通常会引起新的碰撞和重传，直到CW因重传而又增大至合理值，这就造成了网络资源的浪费。同样，在发送失败后，将CW加倍也可能使退避时间不必要的增大而浪费网络资源。所以可以通过改进CW的更新规则使CW更接近于合理值，可降低碰撞概率，提高网络吞吐量。例如：乘性增加线性减小算法MILD和指数增加指数减小算法EIED等都属于这一类。图5是这几个退避算法在公平性方面的比较，IFI为公平指数，该指数值越小公平性越好。
图5. 典型退避算法的公平性比较
(2)动态调整参数类
根据实时监测网络状况获得的信息动态调整某些参数。文献为了提高基于节点的公平性，每个节点通过监听信道上发送的报文来计算自己实际获得的信道权重，并与事先定好的目标权重比较。如果发现所获得权重过高，则将CW增大，反之减小。这样提高了公平性，却损失了部分吞吐量。文献基于网络吞吐量最大化的目的提出了一种改进算法，每个节点通过监测虚拟发送周期中的空闲时隙数量来实时估计当前网络中的活跃节点数n,并将CW设置为最佳值CWopt(n)，若n变化则随之调整CW。采用改进算法后，系统吞吐量接近理论最大值。同时，由于各个节点采用相同的CW，因此该算法的短期公平性也很好。
除了改进退避算法，还可以调整干扰范围和监听范围， 802.11MAC是基于载波监听的。载波监听范围和干扰范围比通信范围要大，在NS2仿真软件中，前者是后者两倍。在多跳情况下，监听范围和干扰范围越大，网络性能下降就越大。干扰范围大会使得隐藏终端问题严重，而监听范围大会加重暴露终端问题。解决暴露终端问题的一些机制也是有用的。可以考虑用多信道协议来解决暴露终端问题，把数据信道和控制信道分离来消除数据和握手信息的干扰，从而彻底解决这一问题。此外还有一些基于服务质量的机制。
5 总结
虽然802.11DCF是ad hoc网络的现行的MAC层协议，但是仍然存在着许多性能问题。如文中分析的暴露终端问题，公平性问题，吞吐量下降和传输层的不稳定性问题。我们对802.11用于Ad hoc网络存在的问题和原因进行了详细的分析，并指出了解决这些问题的主要方法和潜在方向。意在给这个领域的研究者作进一步的研究作基础。目前的解决方法只是针对其中的某个问题，还没有协议使这几个性能同时达到最优。这也是我们将来的努力方向。
参考文献
[1]IEEE Std.802.11, “Wireless LAN Media Access Control (MAC) and Physical Layer (PHY) Specifications.”
The networks simulator ns-2. 2003.
BHARGHAVAN V, DEMERS A, SHENKER S, et al. MACAW: a media access protocol for wireless LANs [A]. In Proceedings of ACM SIGCOMM 1944 [C]. London, U K, Sptember 1994.212-225
SONG N, KWAK B, SONG J, et al. Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease backoff algorithm [A]. In Proceedings of IEEE VTC’2003 [C]. OrIando, Florida, USA, October 2003. 2775-2778
u, Y. Wang, C. C. Ko. Fair Medium Access in 802.11 Based Wireless Ad-Hoc Networks. In IEEE/ACM Mobi-Hoc, Boston, MA, 11 Aug.2000, pp.99-106
CALI 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. December 2000,8(6): 785-799
上一篇：混合P2P网络模型研究与设计
下一篇：电子邮件的安全盾牌PGP