移动自组网媒体接入控制协议自私行为优化算法设计

高士娟 王喜军 朱清超

摘 要：针对移动自组网媒体接入控制协议的自私行为处理机制中存在的静态性、不公平性和复杂性等问题，提出一种自私行为优化处理算法。首先，结合最优化理论和反馈原理，利用历史样本推导最优接入概率，实现参数的实时动态变化，改善静态性;然后，设置所有节点特定时刻均采用最优接入概率，改善网络公平索引系数;最后，采用线性迭代机制，避免算法复杂度的增加。在此基础上，利用李雅普诺夫算法和全局稳态点，理论上证明了所提算法的稳定性和有效性。实验结果表明，相比优化前，所提算法自私节点数、时延分别降低了30%～50%、8～10ms，吞吐量、公平索引值分别提高了0.5Mb/s、0.05，控制开销基本保持不变，自私行为处理机制的性能得到改善。

关键词：自私行为;移动自组网;媒体接入控制协议;稳态;李雅普诺夫算法

中图分类号： TP393.04

文献标志码：A

Abstract： To address the problems like static nature， unfairness and complexity in Selfish Misbehavior （SM） processing mechanism of Medium Access Control （MAC） protocol of Mobile Ad Hoc NETwork （MANET）， an optimization algorithm for SM was proposed. By using optimization theory and feedback theory， the Optimal Access Probability （OAP） was conducted through the utilization of historical samples， realizing the dynamic change of parameters to improve static nature. Then， all nodes in the network were set to use the OAP at the given period， thus the fairness index of the network was promoted. Finally， linear iteration mechanism was adopted to avoid the increase of complexity. On basis of the above， stability and effectiveness of the proposed algorithm were proved theoretically by Lyapunov algorithm and global stable point. Experimental results show that， by the proposed algorithm， the number of SM decreases by 30%-50%， the end-to-end delay brings down 8-10ms， the throughput increases about 0.5Mb/s， the fairness index raises by 0.05， while the control overhead remains unchanged， all of which indicates that the performance of the SM processing mechanism has been improved.

Key words： selfish misbehavior; Mobile Ad Hoc NETwork （MANET）; Medium Access Control （MAC） protocol; stability state; Lyapunov algorithm

0 引言

移动自组网（Mobile Ad Hoc NETwork， MANET）以高度的自组织性、鲁棒性和抗毁性，成为地震、极地考察等恶劣环境的首选通信方式之一。但MANET缺乏基础设施等管理节点，若终端/节点修改信道参数、丢弃分组或切换休眠模式[1-2]，优先接入信道，则违背了公平性原则，自私行为（Selfish Misbehavior， SM）产生。媒体接入控制（Media Access Control， MAC）协议中SM的影响尤为显著，因为MAC协议控制分布式帧间隔、短时帧间隔、竞争窗口（Contention Window， CW）等参数，直接与信道交互，SM势必降低邻节点的接入概率，导致节点资源闲置，网络吞吐量降低;且网络层、传输层、应用层等上层协议依赖MAC协议性能，因而后者影响范围更广，因此MAC协议中SM行为的研究备受关注。

目前MANET中MAC协议集中于分布式SM检测和处理算法的研究，后者起步较晚，研究相对较少。就检测算法而言，文献[3]指出传统DOMINO、CUSUM（CUmulative SUM）和SWN-CUSUM（Sliding Window Non-parameter CUSUM）等算法依賴接入点（Access Point， AP）的检测功能，与MANET分布式、多跳特点不符。文献[4]指出MANET中SM的研究应包含检测和反馈机制，并提出一种集数据搜集、判决和处理于一体的SM检测算法，但时延相对较高。文献[5]指出MAC协议中基于载波监听多址接入冲突避免（Carrier Sense Multiple Access with Collision Detection， CSMA/CA）模式的分布式协调功能（Distributed Coordination Function， DCF）协议是MANET组网的重要组成部分，虽无法完全消除SM，但可最大限度降低SM对吞吐量的影响;并提出一种自由碰撞策略，改善了DCF协议的短期公平性，但与MANET分布式不符。就处理算法而言，其概念由Kyasanur等[6]首次提出，思想在于对判定为SM的节点降低其接入概率，并提出一种分布式协作处理机制[7]，奠定了SM处理算法的基调;但适用范围受限。文献[8]针对SM导致的节点“饿死”现象，引入help标签，使得普通节点多次尝试请求发送（Request To Send， RTS）失败后仍可接入信道，缓解了SM导致的吞吐量降级问题;但控制开销已不容忽视。文献[9]在前期研究基础上，将SM分为丢弃型（Dumb）和智能型（Smart）两类，并提出通过限定参数范围实现分布式处理的思想。在此论文仅针对SM处理算法展开研究。

虽然SM处理机制取得了一定成果，但仍存在以下不足：一是静态性问题，即处理算法仅增加SM节点的接入概率，而邻节点自身参数未作调整，吞吐量并未得到根本改变，原因在于算法缺乏接入概率的预测功能，造成数据资源的浪费;二是公平性问题，即SM处理过程忽略了节点MAC协议信道接入的公平性，使得其他SM节点仍“有机可乘”;三是复杂度问题，即智能型SM处理复杂度较高。

针对上述不足，本文在不增加算法复杂度的基础上，以改善静态性和公平性为目标，将接入概率τ作为研究参数，针对DCF协议智能型SM，基于统计思想和最优化理论，兼顾节点公平性，提出了一种本地参数可实时更改的SM优化处理算法。该算法本质为节点均以最优接入概率接入信道时，可实现SM处理机制的优化，并限制SM性能的提升。在此基础上，基于李雅普诺夫理论证明了算法的稳定性和有效性，并仿真验证了优化算法的公平性、吞吐量等性能。

1 SM优化算法设计

本章基于最优化理论提出一种SM优化处理算法，使其兼顾两个目标：一是执行算法的节点τ收敛到最优值τopt，即最优化指标;二是SM节点吞吐量不高于普通节点，即公平性指标;三是为避免算法复杂度较高，应以多项式为主，尽量减少指数或对数形式。令连续两个控制分组间隔时间为一步，算法原理为：当检测到残余SM时，邻节点在下一步起始位置增加自身τi，阻止SM获得更高接入概率和吞吐量。

不难看出，算法设计的关键在于如何保证普通节点τi收敛到τopt，且避免吞吐量失衡。为解决该问题，将τ离散化，于是迭代过程可视为离散时间系统，状态空间为τ=[τ1，τ2，…，τn]，τi为节点i任意时隙内分组发送概率，即：

2 稳定性和有效性分析

基于算法设计目标，在此定量分析算法稳定性和有效性，稳定性确保节点收敛到最优值，有效性衡量SM的抑制能力。

2.1 稳定性分析

理论条件下，当所有节点均采用该算法时，网络吞吐量趋于最优值，即τi=τopt，i成立。

一般而言，任意τe∈[0，1]n，若满足条件：1）ε>0，δ>0，对于t，‖τ（0）-τe‖<δ ‖τ（t）-τe‖<ε;2）给定τ（0）∈[0，1]n，limt→∞ τ（t）=τe，则称τe为全局稳态点。两者可保证系统收敛到τe，与初始状态无关，且最优值唯一。

根据式（2）可知，存在需要确定参数γ取值的问题，且γ值越小，式（2）收敛越慢，反之亦成立。由Ziegler-Nichols法则[11]可知，γ取值为系统即将变为不稳定状态时对应最大值γmax的一半，即γ=γmax/2。由于式（2）中gi（t）函数与Fi（t）相关，等价于γmax与Fi（t）密切相关。

接下来介绍γmax值的计算。直观而言，系统经过特定算法处理后，剩余SM数目nr相对较小。为简化计算，且不失一般性，令nr=1，扩展到nr个节点时结论成立。由DCF原理可知，任意节点i执行二进制指数回退（Binary Exponential Backoff， BEB）算法时，节点吞吐量与Bianchi公式[12]类似。但接入概率并非一成不变，其值随SM波动。令τi为任意节点接入概率，对于N个信道竞争节点，吞吐量s（τi）表示为：

根据全局稳态点定义可知，函数V和γ取值可保证系统趋于稳定，且分析过程中假设节点包含sj相关信息。但由于MANET节点移动性，其值产生随机波动，系统以小概率事件偏离理论值。只要干扰受限，其值将趋于理论值，但必须满足以下条件：1）存在两类K函数α1和α2，使得|x|≤c时，α1（|x|）≤V（x）≤α2（|x|）;2）存在K函数α3，使得|x|≤c时，V（x（t+1）-x（t））≤-α3（|x|）;3）对于系统节点接入概率τ，存在连续李亚普诺夫函数;4）系统在干扰条件时为连续函数。根据算法模型，当α1=α2=‖τ-τopt‖∞时条件1）成立;当‖x‖∈[0，τopt/2]，即‖τ-τopt‖≤τopt/2时条件2）成立;函数V使条件3）成立;对于任意τi和ri，gi（t）使条件4）恒成立。综上所述，新算法中参数γ、Fi（t）可使MANET系统趋于稳态，吞吐量收敛到最优值。

2.2 有效性分析

如前文所述，当所有节点采用新算法时，系统将收敛到稳态，即节点接入概率为τi=τopt，吞吐量为si=sopt。在此定量分析任意节点不遵守算法时，吞吐量不超过sopt。对采用优化处理算法的节点称为普通节点，否则为SM。下面定量证明任意节点吞吐量不超过sopt。

2.3 复杂度分析

本文算法复杂度包括最优接入概率和SM处理两部分。前者对应复杂度为T1（n）≈O（n*n+n）=O（n2），后者对应复杂度为T2（n）≈O（n3*n）=O（n4），因此该算法对应复杂度为T（n）=T1（n）+T2（n）=O（n4），这与目前SM相关处理算法的复杂度基本相同，该值可用控制开销/分组数描述。

3 性能仿真结果与分析

3.1 参数设置

假设节点为手持设备，对应中低速运动场景，速率限定为2m/s，频率为300Mb/s，分组传输速率为11Mb/s。对于MANET而言，网络层选择动态源路由（Dynamic Source Route， DSR）协议[14]，应用层选择恒定比特流（Constant Bit Rate， CBR），参数设置如表1所示。其他參数与IEEE文档规范[15]保持一致，并利用软件NS-2[16]对协议各项性能指标进行仿真。

3.2 性能指标

为了衡量改进算法的性能，分别对吞吐量、端到端时延、公平性指数和控制开销等指标进行分析（使用awk工具分析），所有数据由NS-2中的trace文件获得。

吞吐量是指單位时间内成功传输的比特数，端到端时延是指分组从源节点到目的节点成功传输所经历的时间（忽略传播时延和排队时延），两者可衡量优化算法改进的程度。前者由式（9）计算，值越大越好，后者由trace文件统计平均获得，值越小越好。

4 结语

本文基于所有节点采用最优接入概率的思想，缓解了SM处理机制存在的静态性和公平性问题，理论和仿真验证了算法的稳定性、有效性和优越性。但是仍存在以下几个问题亟待解决：一是能耗问题，所提算法以计算资源、存储资源换取性能优化，不难理解其能耗必然增加，如何实现性能与能耗的均衡是必须考虑的问题;二是多点协同处理问题，该算法设计过程中未考虑节点之间的互操作，如何实现节点之间的协同处理是算法改进设计的难题;三是所提算法在维持算法复杂度的基础上实现了公平性、吞吐量等性能的改善，但复杂度方面仍存在一定的改进空间，后期将继续针对上述问题展开研究。

参考文献 （References）

[1] 朱清超，陈靖，龚水清，等.移动自组网媒体接入控制协议吞吐量与公平性均衡设计[J].计算机应用，2015，35（11）：3275-3279，3311.（ZHU Q C， CHEN J， GONG S Q， et al. Design of medium access control protocol tradeoff between throughput and fairness in MANET [J]. Journal of Computer Applications， 2015， 35（11）： 3275-3279， 3311.）

[2] 朱清超，陈靖，龚水清，等.移动自组网自私行为闭环惩罚模型设计[J].计算机应用研究，2016，33（8）：2446-2450.（ZHU Q C， CHEN J， GONG S Q， et al. Design of closed-loop model on selfish behavior in MANET [J]. Application Research of Computers， 2016， 33（8）： 2446-2450.）

[3] GUANG L， ASSI C， BENSLIMANE A. MAC layer misbehavior in wireless networks： challenges and solutions [J]. IEEE Wireless Communications， 2008， 15（4）： 6-14.

[4] TARANNUM R， PANDEY Y. Detection and deletion of selfish MANET nodes a distributed approach [C]// Proceedings of the 2012 1st International Conference on Recent Advances in Information Technology. Piscataway， NJ： IEEE， 2012： 152-156.

[5] SANABRIA-RUSSO L， BARCELO J， BELLALTA B， et al. A high efficiency MAC protocol for WLANs： providing fairness in dense scenarios [J]. IEEE/ACM Transactions on Networking， 2017， 25（1）： 492-505.

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

[7] KYASANUR P， VAIDYA N H. Detection and handling of MAC layer misbehavior in wireless networks [C]// Proceedings of 2003 International Conference on Dependable Systems and Networks. Piscataway， NJ： IEEE， 2003： 1-10.

[8] HUANG C， LEA C-T， WONG A K-S. Fairness enhancement for 802.11 MAC [C]// Proceedings of the 2010 International Conference on Access Networks， LNICST 37. Berlin： Springer， 2010： 25-39.

[9] LI M， SALINAS S， LI P， et al. MAC-layer selfish misbehavior in IEEE 802.11 Ad Hoc networks： detection and defense [J]. IEEE Transactions on Mobile Computing， 2015， 14（6）： 1203-1217.

[10] KONORSKI J. A game-theoretic study of CSMA/CA under a backoff attack [J]. IEEE/ACM Transactions on Networking， 2006， 14（6）： 1167-1178.

[11] FRANKLIN G F， POWELL J D ， WORKMAN M L. Digital Control of Dynamic Systems [M]. Reading， MA： Addison-Wesley， 1990： 192-196.

[12] BIANCHI G. Performance analysis of the IEEE 802.11 distributed coordination function [J]. IEEE Journal on Selected Areas in Communications， 2000， 18（3）： 535-547.

[13] KALIL H K. Nonlinear Systems [M]. 3rd ed. New York： Macmillan， 2002： 174-180.

[14] MISTRY H P， MISTRY N H. A survey use of ACO on AODV & DSR routing protocols in MANET [C]// Proceedings of the 2015 International Conference on Innovations in Information Embedded and Communication System. Piscataway， NJ： IEEE， 2015： 1-6.

[15] EASTLAKE 3rd D E， ABLEY J. IANA considerations and IETF protocol and documentation usage for IEEE 802 parameters： RFC7042 [EB/OL]. [2018-09-26]. https：//tools.ietf.org/pdf/rfc7042.pdf.

[16] CHUNG J， CLAYPOOL M. NS by example [EB/OL].[2018-09-26]. http：//nile.wpi.edu/NS/.

[17] JAIN R K， CHIU D-M W， HAVE W R. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems： DEC-TR-301 [R]. Hudson， MA： Eastern Research Laboratory， 1984.