移动自组网媒体接入控制协议吞吐量与公平性均衡设计

摘要：针对移动自组网媒体接入控制（MAC）协议高吞吐量、低公平性的失衡问题，提出一种基于最优接入概率的简化协议MACFT。首先推导公平条件下最优吞吐量与节点数、节点数与空闲接入概率的定量关系，设计空闲接入概率评估模型，利用李雅普诺夫漂移函数证明模型的可行性和稳定性；其次利用自回归滑动平均（ARMA） 模型滤波实现空闲时隙接入概率的计算，并通过比例积分控制器（PIC）完成动态控制；最后综合分析吞吐量和公平性等性能。实验结果表明MACFT公平索引值为0.98，吞吐量为6.15Mb/s，接近最优值1和5.85Mb/s，比渐进最佳回退（AOB）、空闲感知（IS）、协议分布式协调（DCF）、改进协议启发式缓变协议（GDCF）性能更优，实现吞吐量和公平性的均衡。

关键词：移动自组网；公平性；空闲接入概率；吞吐量；媒体接入控制

中图分类号： TP393.1

文献标志码：A

0引言

移动自组网（Mobile Ad Hoc NETwork，MANET）具有高度的自组织性、鲁棒性和抗毁性，在无线通信领域异军突起，应用范围覆盖工业、商业、交通、医疗和军事等领域，是地震、极地考察等恶劣环境的终极通信方式之一。但由于MANET无需基础设施，缺少管理节点，若终端用户修改信道参数、丢弃数据包或切换休眠模式[1-3]，则产生自私节点（Selfish Node，SN），违反网络的公平性原则，产生吞吐量较高而公平索引值较低的失衡问题。媒体接入控制（Medium Access Control， MAC）层影响尤为显著，因为MAC协议直接与信道交互，且网络层、传输层、应用层等上层协议均建立在MAC协议基础之上，影响范围更广，因此MAC协议公平性要求更高。但若仅考虑公平性，将导致部分节点接入概率降低，同样无法使吞吐量性能达到最优，因此如何实现公平性和吞吐量的均衡成为MAC协议研究的新课题。

MAC层公平性和吞吐量均衡的研究集中于两类：一是检测、处理自私行为；二是降低算法控制开销。前者在于提高节点公平性，改善吞吐量性能，共同点在于以行为检测为目的，根据统计数据，建立评估机制和检测算法，提出限制模型，并优化改进协议的吞吐量性能。若优于标准协议分布式协调（Distribution Coordination Function，DCF）[4-5]或改进协议启发式缓变协议（Gentle DCF，GDCF）[6]等，则达到预期目的，否则不断修改控制参数，使协议性能最优，属于渐近优化过程，算法复杂度和硬件要求较高，且处理时延、控制开销较大。如Mackenzie等[7]研究指出DCF存在SN问题，并可通过控制节点之间信道参数防止不公平的信道共享。Kyasanur等[8-9]分析DCF自私行为产生机制，指出SN通过修改竞争窗口（Contention Window， CW）、分布式帧间间隙（Distributed InterFrame Space， DIFS）、短帧间间隔（Short InterFrame Space， SIFS）、网络分配向量（Network Allocation Vector， NAV）等参数提高自身接入概率，使得网络吞吐量急剧降低，但缺乏量化机制。刘春风等[10-11]量化分析DCF协议SN，建立描述吞吐量的二维马尔可夫模型，并设计了SWNCUSUM算法实现SN的检测，检测时延和精度较优，但受饱和条件限制。Serrano等[12-13]摆脱无线电假设，基于数理统计和KS评估理论，设计新的检测算法，降低检测时延，性能优于中心极限定理（Central Limit Theorem， CLT）和多米诺理论（Domino theory， DOMINO），且没有任何条件限制，但缺少吞吐量最优值的考虑。Giri等[14]指出通过修改DCF协议中二进制指数回退（Binary Exponential Backoff， BEB）算法实现不同类型、等级的SN的仿真，为SN行为的仿真提供可行性方案。Li等[15]针对多跳Ad Hoc网络MAC层SN问题，根据样本统计规律，设计检测和限制算法，提高检测精度，降低SN对正常节点吞吐量的影响，但控制开销和算法时延增加，且随着网络规模的增加，增速越来越快。Banchs等[16]为了降低SN对网络吞吐量的影响，采用主动机制，设计分布式反应算法，限制SN占用资源，最优吞吐量得到改善，精度较高，但算法开销仍未改善。以上协议均属于第一类，以提高公平性为目的，不断改善吞吐量性能，但算法复杂度和控制开销较高。

不同的是，后者侧重于降低算法复杂度，提高协议效率，共同点是将接入概率或竞争窗口改进为近似计算，将非线性、非齐次模型转化为线性、齐次模型，简化最优解求解过程。Lee等[17-18]以网络利用率最大化为基础研究竞争时间与有效占用信道时间的关系，构建最优化理论条件，定义效用函数，此时最优解才可与算法相关联，并提出利用缓冲过程将多个近似值解决方案转化为可行算法，但吞吐量等性能受限。Rad等[19]在此基础上，证明算法对大规模网络收敛，为近似最优解的可行性提供理论基础，但缺乏现实性考虑，即无限大存储空间和节点间的报文频繁交换，后者是评估通信信道误报率的必要条件。Bononi等[20]提出著名的渐进最佳回退（Asymptotically Optimal Backoff，AOB）协议简化最优值计算，实现网络吞吐量的优化。但AOB属于粗略近似，即假设最佳MAC协议与节点数量完全独立，适用于小规模网络。而空闲感知（Idle Sense，IS）[21]机制则尝试采用节点接入行为优化吞吐量，即最小化竞争和碰撞时间来增加传输可用时间，实现吞吐量最优，IS结果表明当连续感知5.68个连续时隙时，吞吐量最优值最大，且与竞争媒介的节点数量无关，但公平性仍存在较大的改进空间。

综上所述， MAC协议尚未综合考量公平性和吞吐量，仅对二者之一改进优化，失衡问题仍未缓解。但根据上述文献可得到3点启示：1） 降低算法难度能够降低控制开销；2） 节点之间的接入概率值越相近，公平性越高；3） 建立最优吞吐量与接入概率的关系，接入概率最优时，吞吐量最优，且最优值与网络参数相关性较低。基于该思想，结合上述算法的优点，建立最优空闲接入概率和节点数目评估算法，设计吞吐量公平性均衡的简单MAC机制（FairnessThroughput of MAC，MACFT），创新点在于：1） 推导绝对公平条件的网络最优吞吐量、节点数和空闲接入概率之间的函数关系；2） 利用李雅普诺夫漂移函数，证明在最优接入概率的前提下，MAC协议的可行性和稳定性；3） 根据自回归滑动平均模型（AutoRegressive and Moving Average model， ARMA）滤波确定空闲接入概率的评估模型，并通过比例积分控制器（Proportional Integral Controller， PIC）实现控制；4） 对比分析AOB、IS、DCF、GDCF和MACFT协议的公平性和吞吐量指标，证明协议性能的优越性。

第11期

朱清超等：移动自组网媒体接入控制协议吞吐量与公平性均衡设计

计算机应用 第35卷

1系统模型

假设网络节点数为n，任意时刻其子集N最多允许一个节点采用流渗透模式占用信道并发送数据，反之产生碰撞。在给定DIFS时间内若节点感知信道空闲，则计数器为0的节点竞争发送数据包，否则继续监听信道，计数器递减。在竞争周期内，节点管理时隙竞争计数器，回退时间在[0，W-1]内随机选取。若信道感知空闲，则竞争计数器减小；若检测到数据发送，则暂停计数；若DIFS间隔内重新感知空闲，则恢复计数，直至计数器值为0时开始数据传输。

该过程与DCF相似，根本区别在于，当检测到数据碰撞时DCF竞争窗口加倍，执行BEB算法，而MACFT采用单一最优竞争窗口，其值由每次数据发送的最后尝试值确定，与节点前期状态（成功/碰撞）无关。

1.1包发送概率

令τ为节点随机选择时隙发送报文的概率。由于采用DCF回退模型，则MACFT接入概率τ为W的函数[22]，即

τ=2W+1（1

1.2吞吐量

令S为系统吞吐量，表征信道成功利用的比例。根据IEEE802.11定义可知，计算S必须考虑给定时隙检测信道空闲的概率，即：

pi=（1-τ）n（2）

忙时发送成功的概率：

ps=nτ（1-τ）n-1（3）

和忙时碰撞概率：

pc=1-ps-pi（4

系统吞吐量为信道成功应用时间之和与周期平均值之比，即：

S=psE[p]piE[Ti]+psE[Ts]+pcE[Tc]（5）

其中：E[Ts]、E[Tc]、E[Ti]和E[p]分别表示成功、碰撞、空闲和帧周期的平均值。DCF推荐期望周期为常数[4-5]，即E[p]=P，E[Ts]=Ts，E[Ti]=Ti，E[Tc]=Tc，则S简化为：

S=PTs-Tc+[Tc+pi（Ti-Tc）]/ps（6

S最大值可通过确定最优值τ*获得，对式（6）求导可得最优值τ*满足：

（1-τ*）n（Tc-Ti）+（nτ*-1）Tc=0（7

将节点接入概率取值为τ*，可得最优吞吐量S*，式（7）所得τ*可写成n的函数形式，即：

τ*=f（n）（8

因此最佳媒体接入概率τ*仅与竞争信道的节点数量有关，且n>0时f（n）是n的减函数。若节点数目已知，则通过式（7）可得网络最佳接入概率和公平网络最优吞吐量。

1.3节点数量评估

定义a为监听信道空闲概率的估计值，由竞争周期内时隙的状态获得，具有缓慢时变性，可通过时隙样本过滤算法使其收敛到稳态，下节将详细介绍。如果网络正趋近稳态，则所有节点均以最优接入概率τ*竞争信道。若其他n-1个节点无数据发送，则监听空闲时隙，即pa=（1-τ*）n-1。此时对评估概率值a和最优值pa的方差求最小值可得节点数目的估计值，即：

=arg minn∈N（a-（1-τi）n-1）2（9

但问题产生，节点并不知道网络何时到达稳态，则参数τi未知。由于所有节点采用同一竞争窗口，则稳态时节点na可利用本身的媒体接入概率评估节点数量，即τi=τa。但如果网络远离稳态，则评估精度降低，当且仅当τa覆盖最优解τ*时才有效，因此作以下假设。

假设式（9）中节点na利用媒体接入概率τa确定式（8）中最优接入概率τ*，同时保证该媒体接入概率范围覆盖最优值，那么该MAC机制是可行的。

1.4MAC机制设计及稳定性分析

1）模型设计。

考虑媒体接入概率向量T（k）=（τ1（k），τ2（k），…，τn（k）），表征任意时刻k任意节点接入概率。向量T初始化为给定概率值0

1）在k时刻节点利用式（9）中a和概率τi=τinit得到竞争节点数量的评估值（k）；

2）将（k）代入式（8），计算系统参数（k）；

3）（k）通过控制器C（（k））控制输出τ（k+1），用于计算下一次竞争周期的窗口值W（k+1）=2τ（k+1）-1。

值得注意的是，k=3，4，…，m时的估计值a由τi=τ（k=2），τi=τ（k=3），…，τi=τ（k=m-1）获得，并非τi=τ（k=1）=τinit，由此可获得网络公平条件下的最优吞吐量评估值。

图片

图1MAC协议模型

2）稳定性证明。

首先引入李雅普诺夫漂移函数，该函数被成功用于多个稳定系统，如包交换系统[23]。在此基础上分析MAC机制的稳定性。由于MAC机制为马尔可夫型，最终状态等于已经存在的稳态分布。

利用李雅普诺夫二次方程[24]L（T）=∑ni=1τ2i，并根据概率论推出T（k），如果B>0和ε>0，则MAC机制属于强稳定，对所有时刻k，令李雅普诺夫漂移函数为：

Δ（T（k））E{L（T（k+1））-L（T（k））|T（k）}

若公式

Δ（T（k））≤B-ε∑ni=1τi（k）（10）

对于任意δ>0满足∑ni=1τi（k）≥（B+δ）/ε，则Δ（T（k））≤-δ。换言之，当媒体接入概率之和足够大时，条件（式（10））保证李雅普诺夫漂移为负值，即无论何时向量T超出边界区域T≥0|∑ni=1τi（k）≤（B+δ）/ε，负漂移最终使其回归到该区域，保证MAC机制的稳定性。

然后定性说明MACFT的稳定性和假设的有效性，分两种情况讨论：一是节点增加；二是节点减少。对于上述网络行为，MAC机制必须保证收敛到稳定状态的最优媒体接入概率。

1）节点数增加。

考虑到k-1时刻网络操作节点数n=Ke。从k-1到k，新增Ka个节点，由此n=Ke+Ka。已经存在的Ke个节点稳态时收敛到最优解，当Ka个节点接入信道时，式（9）控制估计值a减小。由于Ke个节点媒体接入概率τ（k）决定τ（k+1），如果a（k）（k-1）。由于τ（k+1）由减函数f（n）决定，则τ（k+1）

2）节点数降低。

同理考虑k-1时刻网络存在n=Ke个节点，从k-1到k，Kd个节点停止数据包发送，则剩余n=Ke-Kd个活动节点。已经存在的Ke个节点收敛到稳态最优解，当Kd个节点停止发送数据时，根据式（9）控制评估值a增大。由于剩余的Ke-Kd个节点采用当前接入概率τ（k）决定τ（k+1），如果a（k）>a（k+1），则（k）τ（k）。那么在k+2，k+3，…，k+G时刻，a（k+2）>a（k+1），…，a（k+G）>a（k+G-1）。但由于滤波机制样本值a引入时延，则G+1个周期后，a（k+G+1）（k+G）保持不变，因此在k+G+2时刻的传输概率能够保证负漂移，从而使MAC机制保持稳定τ（k+G+2）

2MAC协议实现

基于上述理论，本章采用最佳接入概率确保网络公平性，并使吞吐量接近公平网络的理论最优值。前文指出，最优接入概率需要4个参数支撑：1）空闲时隙概率估计；2）节点数量估计；3）最优接入概率计算；4）接入概率控制。

如前所述，空闲时隙概率可通过竞争周期内的时隙状态来评估，相关系数为：

1B∑Bi=1sloti（11）

式中： B为时隙数目。若第i时隙空闲，则时隙sloti为0；反之为1。为了获得参数a，采用ARMA滤波[25]，代入式（11）的相关频率，则a为：

a（k+1）=αa（k）+1-αB∑Bi=1sloti（12）

式中α表示滤波存储器系数。

为了确定ARMA滤波参数，场景中节点数目设置为每隔100s变化一次，对应节点数目分别为2、5、10、25、15、5、25。当网络节点数为25时，节点竞争窗口达到最优值。

图2所示为B=1000，α=0.75时a估计值。不难看出滤波参数的选择使a接近稳定状态值pa。当节点数目较少时，a估计值精确度较高，标准差很低。但节点数目较大时，由于样本数量减少，平均竞争时隙周期增加，a标准差较大，如300s到400s时的样本数量小于0到100s，前者波动范围明显大于后者。

图片

图2空闲时隙概率与仿真时间的关系

在确定评估值a后，根据式（9）和式（8）分别计算节点数目评估值和最佳接入概率。值得注意的是，由于考虑内存因素，式（12）中滤波器引入更慢的动态值，式（8）获得的参数不再直接用于每个节点。基于该原因，需根据PIC原理增加控制模块，即图1中所示C（），具体实现如图3所示。C（）根据参数（k）和ARMA动态滤波，简化媒体接入概率。

图片

图3PIC实现控制器C（）

为了确定参数Kp和TI，即增益比例和积分时间，对阶跃响应进行仿真，并采用开环模型估计a达到稳态所需的时间。在此利用经典的齐格勒尼格尔斯调谐方法估计Kp和TI分别为0.6和23.81。

图4和图5中分别采用图3中网络参数时，a和的变化曲线，最优媒体接入概率由MACFT确定，其中Winit为500。可以看出当网络节点数目变化时，在短时周期内媒体接入概率收敛于最优稳态值，精度较低。

图片

图4MACFT空闲时隙接入概率曲线

图5所示为MACFT的网络节点评估数目曲线。随着节点数目的增加，产生两种现象：一是ARMA滤波得到的a估计值并不精确，评估误差增加；二是短时间隔内的精确度降低，导致节点利用个体接入概率去评估节点数目。由于个体媒体接入概率未被真实节点数目采用，精度较低。但随着媒体接入概率向最优值收敛，越来越精确。

图片

图5节点数目评估值与真实值对比

3性能分析

3.1参数设置

本节利用软件NS2[26]对MACFT进行仿真，综合分析吞吐量和公平性指标，计算吞吐量与最优值的误差。为了更好地说明协议的有效性，在此与其他4种MAC协议AOB、DCF、GDCF和IS作比较，具体参数如表1所示。

表格（有表名）

表1仿真参数设置

参数值参数值

节点速度2m/s停留时间0s

报文速率1Mb/s路由协议DSR

场地大小1000m×1000m业务流cbr

CWmin16仿真时间700s

CWmax256最大连接数10

3.2性能分析

本节主要分析AOB、IS、DCF、GDCF和MACFT协议吞吐量和公平性指标，对比说明协议的优越性和可行性。

图6所示为各协议的瞬时吞吐量，在此仅列举绝对吞吐量，其值由传输速率实现标准化。结果表明前100s时仅2个节点传输数据，节点规模较小，AOB和IS中媒体接入概率精确度不高，而MACFT性能较优。随着节点数目增加，AOB吞吐量高于其他协议，但AOB和MACFT的差值未超过约150kb/s（600～700s）。原因在于DCF是基于假设建立的，性能与节点数目直接相关，而AOB、IS和MACFT采用最优化原则确定媒体接入概率，因而与节点数目相关性较低，变化幅度较小。除DCF外，其他MAC协议吞吐量均高于最优值，因为式（5）计算的吞吐量最优值是以绝对公平竞争为基础，而由于种种原因，实际媒体接入并不公平，若干节点竞争周期较小，因此网络吞吐量较高。例如极限条件时，若单个节点采用最大媒体接入概率（值为1），禁止其他节点接入，吞吐量等于最大网络利用率，大于绝对公平接入时的最优吞吐量。

图片

图6吞吐量随仿真时间变化曲线

图7所示为不同节点数目的平均吞吐量。随着节点数目的增加，MACFT性能接近IS，约为6.15Mb/s，略低于AOB和GDCF（6.2Mb/s），且吞吐量趋于最优值5.85Mb/s，表示节点并非处于绝对公平状态。而MACFT与IS均接近最优吞吐量，表明网络公平性更高。

图片

图7不同节点数时平均吞吐量曲线

图8所示为25节点不同窗口数目（从低到高分析）时各协议的Jain公平性[27]索引，反映网络的公平性，初始阶段采用小公平窗口分析短期性能，并逐渐增加到2500个接入信道。结果表明若考虑公平窗口大小而言，MACFT公平索引值最高，约为0.98，并接近最优值1，IS次之，AOB公平性索引低于MACFT和IS。原因在于MACFT将相似信道接入概率强加到各个节点，网络接入概率基本相同，趋于公平网络，但造成空闲信道资源的浪费，其吞吐量略低于AOB。IS同样考虑节点的行为控制，属于优化机制，并不强加到每个节点，因而公平性略低于MACFT，相对AOB粗略近似而言，公平性较高，因此协议公平性越高，吞吐量越接近公平网络最优值。

图片

图825节点不同协议Jain公平索引

综上所述，MACFT表现出更高的吞吐量和公平性，接近最优值，性能更优。

4结语

本文针对MANET失衡问题，以计算资源换取信道资源的思想，提出分布式吞吐量和公平性均衡算法MACFT，方法简单易行，并仿真分析AOB、IS、DCF、GDCF和MACFT吞吐量和公平性等指标，结果表明MACFT性能更优。但是尚存在以下问题：一是尚未考虑算法对系统时延等其他指标影响；二是对网络规模较大时系统性能未作分析。在后期工作中将针对上述问题深入研究。

参考文献：

[1]TOH C K， DONGKYUN K， SUTAEK O H. The controversy of selfish nodes in Ad Hoc networks[C]// Proceedings of the 2010 12th International Conference on Advanced Communication Technology. Piscataway： IEEE， 2010： 1087-1092.

[2]IVAN D B， RENIER V H， MARTIN S O. Analysing the fairness of trustbased mobile Ad Hoc network protocols[C]// Proceedings of the 2011 Information Security for South Africa. Piscataway： IEEE， 2011： 1-8.

[3]ABDERRAHIM B， ABDERREZAK R， DEEPAK D. Relative fairness and optimized throughput for mobile Ad Hoc networks[C]// Proceedings of the 2008 IEEE International Conference on Communications. Piscataway： IEEE， 2008： 2233-2237.

[4]EASTLAKE D 3rd， ABLEY J. IANA considerations and IETF protocol and documentation usage for IEEE 802 parameters： RFC7042[EB/OL]. [20131001]. http：// www. /rfc/rfc7042.txt.

[5]EASTLAKE D 3rd. IANA considerations and IETF protocol usage for IEEE 802 parameters： RFC5342[EB/OL].[20080901]. http：///rfc/rfc5342.txt.

[6]WANG C， LI B， LI L M. A new collision resolution mechanism to enhance the performance of IEEE 802.11 DCF[J]. Vehicular Technology， 2004， 53（4）： 1235-1246.

[7]MACKENZIE A， WICKER S. Stability of multipacket slotted Aloha with selfish users and perfect information[C]// Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications. Piscataway： IEEE， 2003： 1583-1590.

[8]KYASANUR P， VAIDYA N. Detection and handling of MAC layer misbehavior in wireless networks[C]// Proceedings of the 2003 International Conference Dependable Systems and Networks. Piscataway： IEEE， 2003： 173-182.

[9]KYASANUR P， VAIDYA N. Selfish MAC layer misbehavior in wireless networks[J]. IEEE Transactions on Mobile Computing， 2005， 4（5）： 502-516.

[10]LIU C， SHU Y， LI M， et al. A new mechanism to detect selfish behavior in IEEE 802.11 Ad Hoc networks[C]// Proceedings of the 2009 IEEE International Conference on Communications. Piscataway： IEEE， 2009： 1-5.

[11]LIU C. Study on selfish behavior in MAC layer of IEEE802.11 wireless Ad Hoc networks [D]. Tianjin： Tianjin University， 2008. （刘春凤. IEEE802.11无线Ad Hoc网络MAC层自私行为研究[D]. 天津：天津大学， 2008.）

[12]SERRANO P， BANCHS A， TARGON V， et al. Detecting selfish configurations in 802.11 WLANs[J]. IEEE Communications Letters， 2010， 24（2）： 142-144.

[13]SERRANO P， BANCHS A， PATRAS P， et al. Optimal configuration of 802.11e EDCA for realtime and data traffic [J]. IEEE Transactions on Vehicular Technology， 2010， 59（5）： 2511-2528.

[14]GIRI V R， JAGGI N. MAC layer misbehavior effectiveness and collective aggressive reaction approach[C]// Proceedings of the 33rd IEEE Sarnoff Symposium. Piscataway： IEEE， 2010： 1-5.

[15]LI M， SERGIO S， LI P， et al. MACLayer selfish misbehavior in IEEE802.11 Ad Hoc networks： detection and defense[J]. IEEE Transactions on Mobile Computing， 2015， 14（6）： 1203-1217.

[16]BANCHS A， ORTIN J， DOUGLAS J L， et al. Thwarting selfish behavior in 802.11 WLANs[J]. IEEE/ACM Transactions on Networking， 2014， 34（1）： 1-14.

[17]LEE J W， TANG A， HUANG J W， et al. Reverseengineering MAC： a noncooperative game model[J]. IEEE Journal on Selected Areas in Communications， 2007， 6（25）： 1135-1147.

[18]LEE J W， TANG A， HUANG J W， et al. Utilityoptimal randomaccess control[J]. IEEE Communications Society， 2007， 7（6）： 2741-2751.