摘 要： 在无线自组织网络中，合理的退避机制能够有效地利用网络资源，解决多个节点同时抢占共享信道的问题，提高网络带宽利用率。通过建立模型深入分析了由于隐藏终端产生的流不公平问题，给出了一种吞吐量变化率和流不公平度的度量，并提出了一种通过调整退避窗口最小值来改善流公平性的退避算法——BFF（Back-off based on Flow Fairness）算法。通过仿真分析表明算法能够很好地提高公平性，解决BEB算法在实际运用中的流不公平问题。

0 引言

IEEE 802.11DCF是为无线局域网WLAN（Wireless LAN）制定的，但目前的无线自组织网络中大都将其直接作为MAC接入规范，从而带来公平性问题。公平性问题研究一般分为基于节点的公平性和基于流的公平性[1-2]两种，最终都归结为如何在MAC协议中确保每个节点或流的接入机率[3]相等。由于数据类型的多元化，支持服务质量（QoS）的介质访问协议（Media Access Control，MAC）是未来网络的发展趋势，因此基于流的公平性能够更好地根据数据流类型来控制数据流的接入能力[4-8]。本文通过建模，分析了MAC机制中对流公平性的影响因素及解决流不公平问题的方法，提出一种基于流公平性的退避算法BFF（Back-off based on Flow Fairness），通过调整退避窗口最小值以减少传输失败发生的概率，同时兼顾到网络传输时延，改善网络中由于隐藏终端引起的流不公平问题，最后通过网络仿真验证了其合理性。

1 IEEE 802.11 DCF公平性问题分析

无线网络中的隐蔽终端问题会在竞争数据流间产生严重的不公平性。不失一般性地，本文针对如图1所示的一个典型网络场景进行仿真分析实验，针对节点使用共享信道带宽的公平性问题进行建模，讨论Rmax次尝试传输失败（RET事件）发生概率的影响因素[9-12]。节点3和节点1相对于节点2而言互为隐藏终端。节点1和节点2之间、节点3和节点4之间均为构建在UDP传输协议上的CBR数据流，均由Pareto分布流量产生器产生，分别用cbr12和cbr34来表示。

设Y[n]表示节点1连续碰撞后重发n个RTS帧的起始时刻的离散时间随机过程，T[i]表示节点3连续成功发送数据帧情况下发送第i个RTS帧的起始时刻的离散时间随机过程。有：

其中，节点1设定RTS定时器的超时门限tout=tRTS+tCTS+tSIFS，节点3到节点4一次成功传递数据所耗时间tb=tRTS+tCTS+3tSIFS+tD+tA。Rmax为RTS帧的最大重传次数，W0为节点3连续两次成功发送数据帧之间的随机退避间隔（在具体计算中为了分析方便，将其窗口尺寸设为w，w为最小竞争窗口），Wj为节点1第j次RTS重传时的随机退避间隔，最大退避阶数m=log2（CWmax/w），CWmax为最大竞争窗口，tRTS、tCTS、tSIFS、tD、tA分别为RTS、CTS、SIFS、Data以及ACK帧的传输时间。

1.1 节点1和节点2握手成功的充要条件

节点1第n次发RTS帧才能握手成功的充要条件是此次发送在节点3到节点4的第i-1次成功传送结束前tRTS时刻之后开始，而在节点3的第i次发送RTS帧到达节点2的前tSIFS时刻之前结束。

其中，N1为节点3重传次数的下界，此时节点1连续两次成功传输之间的退避间隔在最小竞争窗口内随机选取，一次成功传输所耗时间最多包括tb和w-1；而N2为节点3重传次数的上界，此时节点1的退避间隔为0，即立即传输，一次成功传输所耗时间最少为tb。

1.2 RET事件出现概率计算

通过对Z字型网络中节点1至节点2的数据流被节点3至节点4数据流扼制的过程建模，可以看出节点1成功发送数据的充要条件是发送RTS帧的时刻Y[n]必须满足式（3）。设第n次尝试，节点1发送RTS帧成功的概率为pn：

当Rmax给定时，节点1尝试Rmax次发送RTS帧失败（RET事件）的概率pRET：

n=1时，节点2收到节点3发出的RTS，根据节点3传输该数据帧的时间启动NAV计数器，节点2在计数器结束之前不侦听信道。而节点1在节点3发完该数据帧前发送第一个RTS帧。所以节点2收不到节点1发送的RTS帧，故p1=0。n>1时，将式（1）、式（2）代入式（4）

已知连续碰撞造成的随机退避间隔在对应退避窗口随机选择的事件相互之间是独立的[13]，于是可以利用独立离散随机变量的母函数定义及性质，得到离散随机变量Xn、Yn、Zi、Un和Vn的分布律pkx、pky、prz、pku和pkv。

1.3 RET事件发生概率分析

从1.2节可以看出，连续Rmax尝试传输失败（RET事件）的概率与pn和Rmax有关，而pn与pkx、pky、prz、pku和pkv，以及它们的求和边界有关，进而可以发现pkx、pky、prz、pku和pkv与tRTS、tCTS、tSIFS、tDIFS、tA、tD以及最小竞争窗口尺寸w有关。由此pRET可以看成与Rmax以及tRTS、tCTS、tSIFS、tDIFS、tA、tD、最小竞争窗口大小w有关，其中除Rmax、tD和w以外的参数都被802.11物理层规范所约束。又tD由MAC数据帧长决定，Rmax的变化对网络的影响非常大，不仅影响MAC层传输时延，还会浪费节点能量，因而可以通过调整w达到pRET减小的效果。

当w增大，prz、pkx、pky跟着增大。同时在式（6）中pkx的独立离散变量概率求和范围k<（i-1）tb+r+tRTS-tSIFS-tn比pky的求和范围k<（i-1）tb+r-tRTS-tn大，由此2≤n≤m时，第n次节点1尝试发送RTS帧成功的概率pn随w增大。同理，m≤n≤Rmax时pn也会增大。由此，w增大pRET减小，但同时会增加重传MAC帧的时延，因此需要兼顾pRET和MAC帧时延。

数值仿真计算得到的数据与仿真数据能够较好地吻合，如图2所示。可以看出，pRET对于CWmin的变化非常敏感。

2 基于流公平性的退避算法

2.1 算法的重要参数指标

（1）吞吐量变化率

BFF算法需要一个参数指标来判断是否出现了造成数据流接收节点吞吐量急速下降的不公平现象。定义一个新的参数——吞吐量变化率Th_Rate，表示节点受流不公平影响时其吞吐量下降的程度。

ThroughputT表示第T个周期内的当前节点吞吐量，ThroughputT+1表示第T+1个周期内的当前节点吞吐量。Th_Rate∈（-∞，0]，该点吞吐量增大；Th_Rate∈（0，启动门限），该点吞吐量适当减小；Th_Rate∈[启动门限，1]，该点吞吐量急剧减小。

（2）流不公平度

定义一个新参数——流不公平度fs作为流不公平的衡量标准。

其中，ThroughputT为当前考察数据流对应的接收节点吞吐量，Throughputaver指可侦听范围内节点接收的数据流吞吐量平均值。fs是该数据流吞吐量相对于数据流吞吐量平均值的差异，能够有效地反映流公平性的情况，fs=0时为绝对公平。

2.2 RTS帧结构

为了获得可侦听范围内其他节点的情况，BFF算法修改了初始的请求发送（Request To Send，RTS）帧结构，在其中携带1 B的吞吐量信息（如图3所示）。

2.3 公平性状况监测表

获得可侦听范围内数据流的吞吐量后，每个节点维护一张公平状况监测表（Fairness State Detection Table，FSDT），如表1所示，用来储存数据流的ID和可侦听节点对应数据流的吞吐量。在初始化FSDT表时，获得数据流的吞吐量后，计算吞吐量平均值（Throughputaver），以获得网络传输数据流的公平性性能[13-14]。FSDT要实时更新，保证网络公平性情况准确。

当有节点离开当前节点的侦听范围（即收不到RTS帧）时，删除FSDT中的相关行。

2.4 BFF算法流程

BFF算法利用RTS帧将各个节点对应数据流的周期吞吐量交换给邻居节点，通过这种信息的交互得到临近区域内的数据流吞吐量的平均值[15-17]。同时，节点计算当前数据流吞吐量变化率，判断是否需要启动算法。一旦启动，就调整退避窗口最小值（CWmin）。接着利用吞吐量平均值作为衡量对象，求得流不公平度，判断CWmin是否继续调整。目的是使网络传输的数据流公平地占用网络资源，使被压制的数据流增加访问网络的机会，消弱突发数据流对信道的垄断，从而减小突发数据流对正在传输的数据流产生的影响。仿真采用单个节点作为观察对象，但算法可以普适于网络中任意节点，流程如图4所示。

3 算法仿真

3.1 网络仿真场景设置

通过NS模拟器对基于流公平性改进的BFF退避算法进行性能仿真。设置如表2所示的网络仿真场景。

其网络拓扑结构如图5所示。在第0~20 s网络中只有8个节点（如图5（a）所示），初始状态8个节点位置随机，数据流随机。第20 s时，节点0和节点3加入（如图5（b）所示），并开始由节点0至节点3发送数据。节点0的发送会被节点1、4、7侦听到，这样的情况下，数据流0→3为无线自组网常见的突发数据，节点0的发送干扰了节点1、4、7的发送，成为隐藏终端。本网络为单跳网络。

3.2 仿真结果及分析

IEEE 802.11采用的是BEB算法。首先仿真了BEB算法在如图5所示的仿真场景中由隐藏终端带来的流不公平现象。仿真结果如图6所示。

从图6中可以看出，当第20 s节点0和节点3加入网络后，阻塞了其他节点的正常数据传输。节点1的吞吐量迅速下降，直降为原来的10%，而数据流0→3则抢占了信道的使用权，节点3的吞吐量大幅上升，一直占有信道，造成节点4和节点7的吞吐量也有所下降。而节点0由于作为发送节点，没有接收数据分组，所以吞吐量一直为0。

对图5所示的仿真场景采用BFF算法解决由隐藏终端引起的流不公平问题进行了仿真，仿真结果如图7所示。第20 s时，节点1的吞吐量变化率由于小于0.5，触发了BFF算法，开始调整退避窗口最小值。在第40 s时，由于网络公平性已经比较好，节点1的流不公平度小于0.1，停止调整退避窗口最小值。图7与图6对比可明显看出，BFF算法较好地解决了新加入节点以及突发业务造成的流不公平问题。

如图8所示为用公平性指数FI来衡量网络流公平性的情况。图中很直观地体现了整个网络的公平性程度的改进。从图上可以看出，在第20 s时BEB算法的公平性指数骤然下降，这是由于出现了流不公平问题。而BFF算法在第20 s之前并没有被触发，所以与BEB算法公平性指数一样。在第20 s之后，BFF算法被触发，流不公平性问题得到缓解，公平性指数上升，直到第40 s处，算法认为流不公平问题得到解决，暂停调整退避窗口最小值，保持了公平性指数的相对稳定。

4 结束语

通过建立无线网络碰撞模型对无线自组网中的数据流公平性进行了细致分析，并通过NS网络模拟器仿真验证了隐藏终端造成的网络中传输数据流不公平的问题，这种情况是无线自组网中MAC机制带来的流不公平问题。通过对流不公平问题进行建模分析，提出了一种通过调整退避窗口最小值改进流公平性的退避算法——BFF算法，软件仿真分析结果验证了该算法的有效性。通过与BEB算法的性能比较，BFF算法在提高流公平性，缓解由隐藏终端带来的流不公平性问题上具有较好优势。

参考文献

[1] Wang Xiaodong， Yun Jun， Zhang Qi， et al. A cross-layer approach for efficient flooding in wireless sensor networks[C]. Wireless Communications and Networking Conferenee， 2005： 1812-1817.

[2] BHARGHAVAN V， DEMERS A， SHENKER S， et al. MACAW： a media access protocol for wireless LAN′s [C]. In Proceedings of ACM SIGCOMM′94， London， UK， 1994： 212-225.

[3] COLVIN A. CSMA with collision avoidance[J]. Computer Communications， 1983，16（5）： 27-35.

[4] 柏诗玉，徐祎，朱浩.基于DSR路由协议的跨层退避算法研究[J].计算机应用研究，2012（29）：55-56.

[5] 黄家玮，王建新.无线接入网络中TCP流的上下行信道公平算法[J].小型微型计算机系统，2011，32（5）：5-7.

[6] 黄家玮.有线/无线网络中TCP拥塞控制的公平性研究[D].长沙：中南大学，2010.

[7] 于倩.基于Ad Hoc网络退避算法的研究[D].秦皇岛：燕山大学，2012.

[8] 刘涛.Ad hoc无线自组网的研究[D].无锡：江南大学，2011.

[9] 李大鹏，袁涛，赵海涛.车载自组织网络中基于邻居节点数估计的最小竞争窗口调整算法[J].电信科学，2013（6）：14-15.

[10] 袁涛.基于IEEE802_11p的车载自组网MAC层关键技术研究[D].南京：南京邮电大学，2013.

[11] 张黎达.基于IEEE802_11MAC层协议的研究与实现[D].重庆：重庆大学，2008.

[12] 吕军.无线自组织网络MAC层退避和竞争避免算法研究[D].合肥：中国科学技术大学，2009.

[13] 唐勇，周满元.Ad hoc网络中MAC不公平性的研究与改进[J].计算机工程，2010，36（22）：100-102.

[14] 曾海文，周满元，唐勇.基于流的Ad hoc网络接入公平性分析与研究[J].计算机工程，2011，37（2）：85-87.

[15] YASSEIN M B， OQAILY O A， MIN G. Enhanced fibonacci backoff algorithm for mobile Ad-Hoc network[C]. 10th International Conference on Computer and Information Technology， 2010：749-754.

[16] 李林韬，王呈贵，王先，等.无线组网中基于卡尔曼滤波有退避界限的MAC算法[J].军事通信技术，2009，30（3）：11-17.

[17] ABDELKADER T， NAIK K， NAYAK A， et al. Adaptive backoff scheme for contention-based vehicular networks using fuzzy logic[C]. FUZZ-IEEE， Korea，2009：1621-1626.