一种基于流公平性的退避算法

徐立强，徐 祎，王 锐

（合肥电子工程学院，安徽 合肥 230037）

0 引言

IEEE 802.11DCF是为无线局域网WLAN（Wireless LAN）制定的，但目前的无线自组织网络中大都将其直接作为MAC接入规范，从而带来公平性问题。公平性问题研究一般分为基于节点的公平性和基于流的公平性[1-2]两种，最终都归结为如何在MAC协议中确保每个节点或流的接入机率[3]相等。由于数据类型的多元化，支持服务质量（QoS）的介质访问协议（MediaAccess 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来表示。

图1 Z字型网络拓扑图

设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），并令对应的取 值 范 围 为 εXn=[0，（2n-2）w-n+1]，εYn=[0，（2n-1）wn]，εZi=[0，（i-1）w]，εUn=[0，（（n-m+1）2m-2）w-n+1]，εVn=[0，（（n-m+1）2m-1）w-n]，离散事件 Xn，Yn，Zi，Un，Vn相应的分布律为 pkx，pky，prz，pku，pkv，可得 pn：

已知连续碰撞造成的随机退避间隔在对应退避窗口随机选择的事件相互之间是独立的[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）吞吐量变化率

图2 pRET随着CWmin变化情况

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所示）。

图3 RTS数据包结构

2.3 公平性状况监测表

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

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

表1 公平性状况监测表FSDT

2.4 BFF算法流程

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

图4 算法流程图

3 算法仿真

3.1 网络仿真场景设置

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

表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的发送，成为隐藏终端。本网络为单跳网络。

图5 网络拓扑结构图

3.2 仿真结果及分析

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

图6 BEB算法流间不公平现象

从图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算法较好地解决了新加入节点以及突发业务造成的流不公平问题。

图7 BFF算法改进效果

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

图8 BFF算法在公平性指数上与BEB算法的比较

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].10thInternational 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.