基于机器学习的移动自组网MAC协议研究综述

郑博文，肖 卓，刘丽哲，梁 晨

(1.中国电子科技集团公司第五十四研究所，河北 石家庄 050081;2.中国人民解放军96764部队，河南 洛阳 471000)

0 引言

移动自组织网络(MANET)是一个自组织、自管理的无线通信网络，每个节点既充当主机又充当路由器，并转发不在彼此传输范围内的节点数据，其节点接入控制、资源分配等MAC协议设计较为复杂，也是MANET领域的研究重点之一。MANET的MAC协议主要解决随机接入和资源分配问题，通常可以表述为最优化问题和马尔科夫决策问题(Markov Decision Process,MDP)，传统的MAC协议往往是对其中多个条件进行理想假设，不能很好地满足实际网络工作环境要求。当网络节点移动快、无线电链路环境复杂以及传输带宽增加压力时，高效、稳健的MAC协议设计变得更加具有挑战性。

机器学习是一门多学科交叉专业，涵盖概率论、统计学和近似论等理论，可以在大量的经验学习中自动优化或改进算法性能，目前机器学习在计算机视觉和自然语言处理等领域取得了重大突破。随着机器学习技术的发展，网络研究人员也开始认识到深度学习的力量和重要性，并在积极探索机器学习解决移动网络领域特定问题的方法，例如，利用机器学习从复杂的数据中自动提取高级特征，用以指导网络尽量寻求到最优解和最佳路径，保证MAC协议的高效性和稳健性。

目前虽然有些文献阐述了机器学习技术在无线网络中的应用情况，但分散在不同的研究领域，且缺乏针对自组织网络的研究综述。本文在介绍机器学习技术基础上，分析总结了机器学习用于解决MANET的MAC协议潜在前景和现有研究成果，对其中的关键技术以及未来研究方向进行了梳理归纳。

1 研究现状

机器学习可大致分为三大类：监督学习、无监督学习和强化学习，分为学习阶段和训练阶段。在训练阶段，机器根据训练数据训练学习模型；在测试阶段，机器将训练后的模型应用于预测。监督学习是从标记的数据中学习，主要解决分类和回归问题，常用的监督学习算法包括神经网络、判决树、支持向量机及Logistic回归等[1]。无监督学习是通过无标签数据进行学习，主要解决聚类和降维问题，常用的无监督学习算法包括聚类算法、自动编码器和自组织图(Self-Organizing Map,SOM)等[1]。强化学习是以“试错”方式进行学习，通过与环境进行交互获得的回报指导行为，目标是获得最大回报，主要解决复杂、多变量问题，常见模型是标准的MDP。

MDP可以表示为{S,A,Pa(·,·),Ra(·,·)}，其中S为状态空间，A为动作空间，定义Pa(·,·)为状态转移概率函数，Ra(·,·)为回报函数。状态转移概率函数采用当前状态s和可能的新状态s′，并以动作a为条件输出转移到该新状态的概率，如下所示：

Pa(s,s′)=Pr(St+1=s′|St=s,At=a)。

(1)

Ra(·,·)给出通过动作a从状态s过渡到状态s′之后直接获得的奖励，其定义为：

Ra(s,s′)=E[Rt+1|St=s,At=a]。

(2)

强化学习的目的是寻找策略函数π，最大化未来长期回报。策略函数是从感知到的环境状态到处于这些状态时要采取的动作的映射。评价策略好坏的值函数由式(3)给出：

(3)

式中，Rt为随时间变化观察到的收益，γ为比例参数，用于权衡未来收益的权重要小于当前收益。

深度学习是机器学习领域一个新的研究方向，是一种以人工神经网络为架构，学习样本数据的内在规律[2]，深度学习不是机器学习的单独细分[3]，可以与监督学习、无监督学习和强化学习联合使用，常见的深度学习框架包括深度神经网络、卷积神经网络和深度置信网络等。

MANET的MAC协议的关键技术是设计高效稳健的多节点协商机制，实现各节点对空间、时间、频率等有限资源的合理共享，以解决各节点的随机接入和资源分配问题，保障多节点之间的稳定可靠通信。随机接入和多址接入问题通常可以表述为MDP，而强化学习是解决MDP的有力方案。资源分配问题通常可以表述为最优化问题，鉴于机器学习的强大函数拟合能力[4]，机器学习被认为是解决该问题的主要手段之一。因此，学者们开始关注和研究机器学习技术在移动自组网的应用。ZHANG C等人[5]调研了深度学习在移动无线网络中的研究情况，讨论了几种有助于将深度学习有效部署到移动系统上的技术和平台，指出当前的挑战和未来的研究方向。他指出，相对于传统方法，采用深度学习解决移动网络问题既有优势，又有不足。

采用深度学习解决移动网络问题的优势主要有[5]：

① 深度学习可以从具有复杂结构和内部相关性的数据中自动提取高级特征；

② 移动网络可以生成大量不同类型的数据，深度学习能够处理大量数据，通过训练防止模型过拟合；

③ 当前大多数移动系统都会生成未标记或半标记的数据，深度学习可以采用无监督的方式学习；

④ 深度神经网络学习到的压缩表示可以在不同任务之间共享；

⑤ 深度学习在处理几何移动数据方面很有效[6]。

采用深度学习解决移动网络问题的不足主要有[5]：

① 深度学习(包括深度强化学习)容易受到对抗性示例的影响[7-8]；

② 深度学习算法主要是黑盒子，解释性很低；

③ 深度学习高度依赖数据；

④ 深度学习对计算的要求可能很高；

⑤ 深度神经网络通常具有许多超参数，因此很难找到其最佳配置。

2 关键技术

本节讨论一些使用机器学习来增强自组网MAC协议的工作，包括广播调度问题[9-13]、自适应MAC协议[14-15](Self-Adapting MAC Layer,SAML)、多信道自组网MAC协议[16-19]和异构网络动态频谱共享问题[20-22]。SAML是指系统可以根据参数在MAC协议库中自动选择最合适的MAC协议，并进行MAC协议的切换。强化学习是通过对环境进行观测，学习最优策略的方法，适合用于MAC协议选择。多信道多址接入和异构网络频谱共享可以表述为MDP，采用深度强化学习模型(Deep Rein forcement Learning,DRL)能够有效地解决该问题[16-17,22-23]。

2.1 基于机器学习的广播调度问题

广播调度问题(Broadcast Scheduling Problem，BSP)是移动自组网MAC协议设计中资源分配问题的一个代表，也是TDMA网络研究的关键问题，其目的是找到一个最佳TDMA调度，为所有节点提供传输时隙和最大化系统吞吐量，同时最小化TDMA周期[9]。可描述如下：

(4)

由上述可知，广播调度问题是NP问题，可以表述为非凸函数的最优化问题，传统的方案是采用启发式方法，具有一定的局限性。已有研究学者[9-13]使用神经网络的变体解决广播调度问题，包括结合Hopfield神经网络和遗传算法[10]的方法、结合顺序顶点着色(SVC)和噪声混沌神经网络(NCNN)的方法[11]。文献[12]和文献[13]分别独立采用结合模糊逻辑和Hopfield神经网络的方法，解决BSP问题，其中文献[12]采用的是单阶段方法，一步解决了最小化时隙数量和最大化网络信道利用率两个目标；文献[13]采用两阶段法，首先采用图论着色算法，找到最小时隙数量，然后运用模糊Hopfield神经网络最大化网络信道利用率，文献[13]方法的第2步可以看做是文献[12]方法在f=2时的特例。研究结果表明采用机器学习方法能够得到更优的结果。

文献[12]和文献[13]的具体解决方案如下：

用μxi表示时隙tx∈T分配给节点i的程度，最小化代价函数E表示如下：

(5)

式中，α和β为正系数，f为模糊化参数，diy=1表示节点i和节点y相连。等式中的第1项确保了每个节点至少发送1次；第2项确保了相距1跳和2跳的节点不能同时发送。仿真结果表明，基于模糊Hopfield神经网络的BSP方法在平均时间延迟方面，既优于结合Hopfield神经网络和遗传算法的方法[10]，又优于结合顺序顶点着色(SVC)和噪声混沌神经网络(NCNN)的方法[11]。

2.2 SAML

SHA M等人首次提出了SAML，SAML由可重配置MAC库(Reconfigurable MAC Architecture,RMA)和MAC选择器两个主要组件组成，其中RMA用于在不同的MAC协议之间进行切换，MAC选择器用于学习适合当前网络条件下的MAC协议[14]。根据数据包间隔、接收信号强度指示、应用层QoS要求等指标，使用决策树选择最优MAC协议。SAML框架如图1所示[14]。

图1 SAML架构Fig.1 Overview of SAML architecture

ZHANG M等人[15]针对无人机自组网，提出了一种可以在CSMA/CA和TDMA协议之间切换的容错同步MAC协议(Fault-tolerant Synchronous-MAC,FS-MAC)。FS-MAC协议框架如图2所示，它采用基于分布式Q学习的MAC交换方案，包含一个MAC预选择操作和一个基于实用拜占庭容错(PBFT)的共识决策程序，以产生MAC交换决策。通过MAC预选操作，每个无人机都可以准确评估其性能，并确定哪种MAC协议更合适。然后，借助基于PBFT的共识决策程序，所有无人机都可以实现容错同步切换。

图2 FS-MAC协议架构Fig.2 Overview of FS-MAC architecture

2.3 多信道自组网MAC协议

针对多信道TDMA的多址接入问题，NAPARSTEK O等人提出了一种基于深度多用户强化学习的分布式动态频谱访问算法(Deep Q-learning for Spectrum Access,DQSA)[16-17]。DQSA的基本思想是，共享带宽被分成K个正交信道，在每个时隙的起始，每个用户选择一个信道并以一定的传输概率发送一个分组；在每个时隙结束，已经发送了分组的用户接收ACK信号。DQSA将信道选择结果、信道容量和ACK观测结果以热独编码(One-Hot编码)的方式作为深度神经网络(Deep Q-Network,DQN)的输入，DQN的输出为Q值，即下一时隙的信道选择结果，DQN模型如图3所示[17]。

图3 DQN模型Fig.3 Model of DQN

由于每个用户的网络状态都是部分可观察到的，并且动态状态是非马尔可夫的，且由多用户操作确定，因此添加了一个长短期记忆网络(Long Short Term Memory,LSTM)层，该层既保持了内部状态，又随着时间的推移汇总了观察结果，确保了网络能够学习历史经验。考虑无论采取什么动作都不影响Q值的状态存在，DQSA采用了Dueling DQN模型[18]。DQSA采用演员-评论家方法(Actor-Critic)，训练两个DQN网络，DQN1用于选择动作，DQN2用于估计Q值。DQSA采用Exp3策略[19]进行动作选取，如式(6)所示，可以看作是在softmax和ε-greedy策略之间的平衡，参数α很小，将其随时间取为零，因此在选择具有较高估计Q值的动作方面，该算法随时间变得更加贪婪。

(6)

DQSA采用线下集中训练，线上分布式执行的方式，仿真结果表明，DQSA在无先验信息的情况下吞吐量显著优于采用最优概率值的时隙化Aloha协议。

2.4 异构网络动态频谱共享问题

受频谱资源所限，诸如WiFi、蓝牙等多种无线通信技术使用相同的频谱进行无线传输，从而导致异构无线通信网络之间的干扰。为了避免这种干扰，往往需要大量的处理设备协调它们之间工作。针对异构网络动态频谱共享的问题，已有学者采用机器学习方法进行解决[20-22]。

(7)

图4 深度神经网络模型Fig.4 Model of deep neural network

针对有无ACK的情况，MENNES R等人提出了两种Xf,n的表达方式。仿真结果表明，如果来自其他网络的节点按照泊松分布发送数据，则能够将冲突次数减少50%，当另一个网络的节点遵循更周期性的流量模式时，可以减少15倍的冲突[20]。

针对异构网络动态频谱共享问题，美国国防高级研究计划局(Defense Advanced Research Projects Agency,DARPA)主办了为期3年的频谱协作挑战赛(Spectrum Collaboration Challenge,SC2)，该挑战赛旨在寻找出一种协作式机器学习竞争方法以解决射频频谱的稀缺性问题，并且DARPA致力于研究满足瞬时供需的快速动态频谱共享方法。在参与SC2的过程中，YU Y等人获得灵感，提出了基于深度强化学习模型(Deep Reinforcement Learning,DRL)的多址接入协议(Deep-reinforcement Learning Multiple Access,DLMA)[21]。

在DLMA协议中，DRL模型的动作空间为{发送、等待}，观测空间为{成功、冲突、空闲}，通过ACK信号确定观测值zt∈{成功、冲突、空闲}，定义DRL代理在t+1时刻的状态空间为ct+1≡(at,zt)，其中at∈{发送、等待}为DRL代理在t时刻的动作，定义在t+1时刻的环境状态为之前M个时刻的集合，st+1≡{ct-M+2…,ct,ct+1}，DRL代理在t+1时刻的回报为rt+1∈{0(冲突或空闲),1(成功)}。YU Y等人通过深度神经网络拟合出Q值(Q Neural Network，QNN)，QNN结构如图5所示，并仿真了DLMA与其他TDMA和ALOHA共存时的异构网络动态频谱共享情况。DLMA节点在无先验信息的情况下，通过对环境、自身行为以及所产生的回报的一系列学习，可学习最佳MAC策略，根据指定目标(最大吞吐量或比例公平)与TDMA和ALOHA节点和谐共存[21]。

图5 DLMA协议的QNN模型Fig.5 Model QNN of protocol DLMA

YU Y等人在DLMA的基础上，进一步研究，提出载波侦听深度强化学习多址访问协议(Carrier-Sense Deep-reinforcement Learning Multiple Access,CS-DLMA)[20]，仿真结果表明，CS-DLMA与TDMA，ALOHA和WiFi协议共存时，可以通过调整其自身的传输策略来达到α-公平性目标，当与WiFi共存时，CS-DLMA比其他CSMA协议(例如p-persistent CSMA)更具帕累托效率。

3 未来研究方向

尽管机器学习已用于解决移动自组网MAC协议的诸多问题，但许多问题仍悬而未决，仍需要进一步的研究工作。

(1) 工程实现

针对移动自组网MAC协议的诸多问题，采用机器学习算法得到了很好的效果，但是部分机器学习算法有较高的计算复杂度，因此如何设计硬件架构，高效地实现机器学习算法，满足产品化要求，是未来需要研究解决的问题。

(2) 针对无线自组网设计的机器学习架构

现有机器学习架构在设计之初主要是用于图像处理，如卷积神经网络(Convolutional Neural Networks,CNN)和深度残差网络(Residual Network,ResNet)；或是自然语言处理，如循环神经网络(Recurrent Neural Networks,RNN)，值得考虑针对无线自组网设计新的机器学习架构。

(3) 基于机器学习的多点交互机制学习

针对多信道自组网MAC协议和异构网络动态频谱共享问题，现有文献通常仅利用了ACK信息，没有考虑各个节点交互信息的情况。交互信息如何设计，能否通过机器学习算法自动学习需要交互的信息内容，都是值得研究的问题。FOERSTER J等人[23]首次通过深度学习方法研究了多智能体(Multi-Agent)之间的交互机制，将这种思想用在无线通信上，通过深度学习，让多智能体自己学习通信协议是未来的研究方向。

(4) 基于多智能体强化学习的自组网协议

由于在无线自组网中，每个节点很难观测全局状态信息，这是部分可观测马尔科夫决策问题(Partially Observable Markov Decision Process,POMDP)，现有文献通常通过采用集中调度或线下集中式学习线上分布式部署的方式回避该问题。因此，在部分可观测的情况下，从每个节点角度来看，当其他节点积极探索状态和操作空间以进行策略学习时，它观察到的环境就会呈现出不稳定状态，由于环境不稳定和局部可观察性，使得学习变得极为困难，多智能体强化学习[24](Multi-Agent reinforcement learning,MARL)被认为是解决该问题的手段，研究基于多智能体强化学习的自组网协议是未来的研究方向。

4 结束语

随着机器学习技术的不断发展，以及其在移动自组网应用研究的不断深入，基于机器学习的移动自组网MAC协议技术会越来越完善，有望大幅提升复杂环境下的移动自组网性能，进一步满足其应用需求。本文详细介绍了基于机器学习的自组网MAC协议研究的最新成果，包括广播调度问题、SAML、多信道自组网MAC协议和异构网络动态频谱共享问题；展望了未来的研究方向，包括工程实现、针对无线自组网设计机器学习架构、基于机器学习的多点交互机制学习和基于多智能体强化学习的自组网协议。旨在为关注和研究该领域的初学者提供一些思路，启发他们积极探索和挖掘该领域的技术潜力，推动移动自组网技术的发展。