基于多智能体强化学习的动态频谱分配方法综述

宋 波, 叶 伟, 孟祥辉

(1.航天工程大学电子与光学工程系, 北京 101416; 2.中国人民解放军95801部队, 北京 100076)

0 引 言

近年来,5G移动通信技术获得迅速发展和应用,该技术在物联网、车联网中具有非常广泛的应用前景,因此导致了无线电设备数量的快速增长和对频谱需求的大幅增加。目前的频谱管理方式仍然以静态分配为主,将频谱进行划分后分配给固定的授权用户,这种已经延续了上百年的频谱管理体制已经无法继续满足网络容量的扩增对频谱的需求。

1998年Mitola等人提出了认知无线电和认知循环概念[1],引入了一种自动感知外部无线环境,自主决策并机会式接入空闲频谱的新型无线电技术。Haykin等人对认知无线电的构成、关键技术和应用前景的进一步研究,完善了认知循环定义[2]。IEEE、FCC和ITU等机构均对认知无线电给予了充分重视,进行了广泛研究,给出了定义并制定了相关标准,如IEEE 802.22无线地域网标准、IEEE 1900.7动态频谱接入网络标准等。

动态频谱分配技术作为认知无线电的关键技术,可以大幅提高对频谱资源的利用效率,改善目前的频谱资源在开发利用中存在的不均衡的现象,因此在业界引起了广泛关注与深入研究。目前来看,基于非智能技术的动态频谱分配算法的研究根据理论基础可以分为以下3个方向:基于图论、博弈论和交易理论的方法。其中基于图论的动态频谱分配算法把问题抽象为图论中的顶点着色问题,将各认知无线电用户及其可用信道作为图中的顶点,当用户间不能共用同一信道时,以边进行连接,将频谱分配过程抽象为对这种被称为干扰图的各顶点的逐一着色过程。

干扰图的顶点着色是一个非确定多项式难题问题,难以得到最优解,Peng等人提出了寻求次优解的启发式算法[3],该算法需要事先设定不同应用环境以对不同节点设置优先级,对优先级高的节点优先分配频谱,当信道较多时计算复杂度较高,收敛速度慢。廖楚林等人提出了一种分解复杂干扰图为简单图的方法,将对节点的依次染色转化为简单图的并行染色[4],改善了顺序染色带来的时间开销大的问题。郝丹丹等人提出了一种基于信道回报的异构频谱分配算法,在首次分配时以贪婪方法分配信道减小算法迭代次数[5]。Wang等提出了一种列表着色算法,每一轮随机分配信道后在列表中删去该信道,提升了收敛速度[6]。刘鹏等提出了基于量子遗传和图着色方法的动态频谱分配算法[7],将小生境技术与量子遗传算法相结合,可以解决算法陷入局部最优问题,通过动态调整旋转门并提高染色体阈值,提高了整体收敛速度。何建强等人提出了一种基于颜色敏感图着色的改进方法,以最大化带宽为目标函数,在二次分配时采取最大公平准则,在性能上优于单一颜色敏感图着色算法和最大公平准则算法[8]。

利用博弈论分析与解决多个认知无线电用户竞争频谱获得最大频谱利用效率的动态频谱分配算法取得了很好的效果。Neel等人第一次分析了博弈论在认知无线电系统中的应用前景,推导并提出了在完全潜博弈模型下,动态频谱分配将最终收敛到纳什均衡[9],之后分别分析了利用重复博弈、短视博弈、S-模博弈、潜博弈的认知无线电模型的收敛性[10]。滕志军等人提出了一种基于潜博弈的分布式算法,通过仿真验证了收敛性[11]。Cao等人提出了一种分布式局部议价算法,改进了一般基于博弈论的频谱分配纳什均衡在环境拓扑结构发生改变时必须重新计算的不足,并根据Feed Poverty策略提升了算法的公平性[12],但假设了合作博弈的前提,而一般情况下,各用户间是非合作关系。Etkin等人针对非合作博弈下难以收敛到纳什均衡的问题,以重复博弈的方法证明了其长期有效性[13]。徐昌彪等人提出了一种改进定价函数的博弈论动态频谱分配模型,并分别在静态博弈与动态博弈下进行了验证[14]。

除了基于图论和博弈论的方法外,基于频谱市场理论和拍卖机制的动态频谱分配算法也发展出了不少成果。基于拍卖理论的动态频谱分配方法将活跃认知用户视作拍卖竞标者,将空闲频谱认知用户视作拍卖出售者,基站作为拍卖交易方协调竞标与出售过程[15]。Chen等人提出了一种基于简化VGG(Vickrey-Clark-Groves)模型的频谱拍卖算法,根据累积参与与成功接入次数提出了一种基于首次定价封闭拍卖的新叫价方法,降低了频谱切换时的通信中断并提高了频谱分配的公平性[16]。Zhou等人提出了一种可信双频谱拍卖模型,解决了频谱重复利用和双拍卖中的不可信问题[17]。Wang等人考虑以最大化频谱利用率作为目标函数,引入近似诚信概念,兼顾频谱利用率与诚信,可以最大化频谱拍卖者利润[18]。基于拍卖理论的方法整体上虽然能在限定主次用户条件下收敛到最大化频谱利用效率,但缺乏灵活性。

上述算法虽然可以解决动态频谱分配中的频谱利用与用户通信效能和网络通信效能间的约束与优化问题,但存在灵活性差,收敛速度慢和无法满足分布式条件下需求的问题。这种中心化的分配方法对控制中心与用户间的通信条件和频谱感知的精确性要求比较高,在实际中实现难度大。

随着近年来强化学习等机器学习研究领域的快速发展,基于机器学习算法的智能动态频谱分配方法逐渐吸引了越来越多研究者的注意。

强化学习(reinforcement learning, RL)是为解决马尔可夫决策过程(Markov decision process, MDP)策略优化问题发展出的机器学习算法分支,用于解决具有马尔可夫性的动态环境序贯决策问题。

近年来,在多智能体系统问题中引入RL后获得了很好的效果,多智能体强化学习(multi-agent reinforcement learning, MARL)方法逐渐成为机器学习与群体智能的研究热点,而多认知用户网络在分布式决策模式下的动态频谱分配问题可以视为多个智能体的分布式马尔可夫决策过程。这种分布式群体智能方法在动态频谱分配问题中的应用前景十分广阔。

下面首先对RL和MARL的相关理论基础进行简要介绍并对发展现状进行梳理;对近年来基于MARL的动态频谱分配方法方面的相关工作进行了归纳与分析;最后对当前算法中存在的关键问题与解决思路进行概括与展望。

1 强化学习

认知环的感知与决策过程如图1所示,基于图论的频谱分配模型如图2所示。

图1 认知环的感知与决策过程

图2 基于图论的频谱分配模型

RL是一种针对MDP长期收益最大化的机器学习算法。而MDP可以这样描述:如果环境当前状态st,智能体观测到该状态后,根据策略π(at|st)选取动作at,环境根据状态转移概率p(st+1|st,at)∈(0,1)进入下一状态st+1,智能体根据动作好坏获得环境给予的即时奖励rt,由于智能体做出决策只基于st,与之前的所有状态s0,s1,…,st-1无关,因此(s,a,r)具有马尔可夫链性质,MDP如图3所示。

图3 MDP示意图

根据贝尔曼方程,状态st的价值函数v(st)为

(1)

式中:{at}表示t时刻所有动作的集合；{st+1}表示t+1时刻所有状态的集合；γ∈(0,1)为折扣因子,表示未来状态下的奖励对当前策略的影响程度。

为表征动作a的好坏,定义动作状态价值函数(也称为Q函数)q(st,at)为

q(st,at)=

(2)

式中：{at+1}表示t+1时刻所有动作的集合。

根据是否学习p(st+1|st,at)与rt,可以将强化学习方法分为基于模型的RL(model-based RL, MBRL)方法和与模型无关的RL(model-free RL, MFRL)方法两类。其中,MFRL已成为当前的主流方向。下面分别对基于值函数和策略梯度的MFRL算法与MBRL算法进行介绍。

1.1 基于值函数的强化学习方法

1.1.1 Q-学习方法

Q-学习是一种经典的时序差分RL算法,Q-学习将当前时刻的回报与下一时刻的状态Q函数的最大值作为当前状态最优策略的Q值估计,以其与当前状态下Q函数的误差对当前状态下的Q函数进行更新:

(3)

式(3)的更新过程如图4所示。

图4 Q-学习更新过程

Q-学习的训练过程中需要建立并初始化一个|S|×|A|(S为环境状态空间)的Q值表格,根据式(3)迭代更新该表格,待其收敛后,最佳策略π*(st|at)为

(4)

表格式Q-学习无法应用于状态空间和动作空间都很大或者动作空间连续或不存在终止状态的问题中,而深度Q-学习能有效解决这些问题。

1.1.2 深度Q-学习方法

2015年,一种结合了深度神经网络拟合能力的Q函数拟合方法——深度Q-学习(deep Q-learning, DQL)被Mnih等人提出[19],大幅提升了RL在复杂环境下的学习能力,引起了广泛关注。

在文献[19]中,作者提出的深度Q-网络(deep Q-network, DQN)将Atari游戏画面直接输入卷积神经网络进行状态特征提取,利用2层全连接层进行Q函数的拟合，DQN结构如图5所示。同时提出了经验回放、随机采样、批次训练等技术减小样本间的相关以加快DQN训练速度,DQN是一种端到端学习的RL算法。

图5 深度Q-网络

由于在Q-学习和DQL中,Q值的估计直接利用下一状态最优Q值,造成了对Q值的过高估计。因此,Hasselt等人提出了一种双Q-学习方法以改善对Q值的过高估计造成的训练波动问题[20],并将其与DQN结合,提出了一种改进后的深度双Q网络(double deep Q-network, DDQN)算法[21],在估计当前Q值时用相同结构,但参数不同的另一个DQN(称为目标网络)代替,用行为网络与环境交互,有效改善了DQN训练不稳定的问题。Wang等人将Q函数分解为状态价值函数V与各动作的优势函数A(ai)的组合,提高了Q函数的表示能力,在Atari游戏环境中获得了超过DQN的表现[22]。Fortunato等人为提高DQL算法的策略探索能力,提出了一种在DQN参数中加入随机噪声的Noisy Net算法[23],通过在神经网络超参数中随机加噪的方法提高了DQN在价值函数表示的多样性与随机性。Hessel等人将上述改进进行了有效结合并全部集中在了所提出的Rainbow算法中[24],成为DQL的发展里程碑与集大成者。

DQL相比于表格式Q-学习方法解决了在连续状态空间下的适用性,但仍无法有效解决连续动作空间如机械手臂的连续控制问题。Gu等人提出的归一化优势函数(normalized advantage functions, NAF)算法[25]第一次将Q-学习算法完整的拓展到了连续控制问题中。NAF采用了与竞争DQN[22]类似的思路,将Q函数分解为优势函数与状态价值函数的组合,将状态输入神经网络中输出动作并作为Q-学习方法中的最大价值动作,以被评估动作与Q函数最优值的差构建一个二次型作为优势函数,利用经验回放、随机采样与批次训练等DQN的经典技巧进行训练。NAF算法的提出扩展了DQN的应用范围。

下面对MFRL的另一条发展路径——基于策略梯度的RL方法进行简要介绍。

1.2 基于策略梯度的强化学习方法

1.2.1 随机策略梯度算法

相比于值函数方法通过搜索Q值最大的动作获得最优策略,策略梯度方法直接通过训练优化策略函数π(a|s),同时由于策略函数是动作的概率分布,天然地保留了一定的探索性,也有避免陷入局部最优的优势。

如果智能体在参数为ω的策略函数πω(a|s)下对环境进行探索与采样,轨迹为T,在使得T的累积奖励最大的优化目标下,可以得到目标函数ytarget(ω)为

(5)

式中:r(T)为轨迹T下的奖励函数。

可利用梯度上升法求上述目标函数的最大值,对式(5)求导可得

(6)

式(5)被称为策略梯度(policy gradient, PG),在离散动作空间问题中,将式(6)中求数学期望的形式变换一下,可得

(7)

同时可以利用优势函数Aπ,γ:

Aπ,γ=r+γ·v(st+1)-v(st)

(8)

代替式(7)中的累积奖励,可以显著改善训练中策略梯度的波动。

Konda等人提出的行动器—评判器(actor-critic, AC)算法[26]中利用线性拟合算法拟合πω(a|s)、价值函数v(s)与优势函数Aπ,γ,以优势函数Aπ,γ作为损失函数进行训练;Mnih等人提出了一种用深度神经网络分别拟合πω(a|s)与v(s),并利用多线程采样交互进行训练的异步优势AC(asynchronous advantage AC, A3C)算法[27],有效提升了训练速度。

这些基于策略梯度的AC算法对策略的训练需要基于当前策略与环境的交互数据支撑,这种同策略方法存在策略函数方差大、训练不够稳定的问题。因此,Schulman等从策略更新约束的角度提出了改进方法:利用更新前后的策略分布KL散度作为约束项以提高收敛稳定性,称为置信域策略优化(trust region policy optimization, TRPO)算法[28],但该算法每次更新需要计算费舍尔信息矩阵的逆,计算复杂度比较高,后Wu等人提出用Kronecker分解来降低费舍尔信息矩阵求逆运算的复杂度[29];Schulman等人后来又提出一种TRPO算法的改进算法:近端策略优化(proximal policy optimization, PPO)算法,PPO算法通过限制更新前后策略分布比率的范围代替TRPO的复杂优化方法,使得计算复杂度大幅降低,但实际效果不低于TRPO算法[30]。

为改善随机策略梯度方法基于同策略更新,无法充分利用历史交互数据的缺陷,Wang等人提出了一种异策略更新的AC算法——经验回放AC算法(actor-critic experience replay, ACER)[31],利用了Munos等人提出的Retrace算法[32]使用异策略经验缓存更新当前策略的Q函数,利用重要性采样方法进行策略梯度的更新;同时,为解决策略梯度波动的问题,提出了一种类似于TRPO算法的KL散度约束以降低策略梯度方差,但由于只用了KL散度的一阶导,计算复杂度上比TRPO算法低。

由于A3C、TRPO、PPO等随机策略梯度算法不能利用历史数据进行学习,而ACER算法虽然利用了重要性采样等手段具备了异策略更新的能力,但DQN中的随机采样、批次训练等可以提高训练效率的手段难以应用到Critic的更新上。确定策略梯度算法可以很好地解决这个问题。

1.2.2 确定策略梯度算法

Silver等人提出一种使得AC算法中策略梯度更新与价值函数更新解耦,从而可以利用随机采样和批次训练加快价值函数训练的深度确定性策略梯度(deep deterministic policy gradient, DDPG)方法,有效提升了AC算法的收敛性[33]。随机策略梯度算法中策略网络输出动作空间的概率分布,根据分布采样得到具体动作,DDPG算法则直接输出确定动作,如果以参数为β的深度神经网络μβ(s)拟合该函数,以参数为θ的深度神经网络Qθ(s,a)拟合价值函数,则目标函数可以这样定义:

(9)

(10)

式中:ytarget(θ)为值函数网络更新的目标函数;ytarget(β)为策略网络更新的目标函数。

作者证明了Qθ(s,a)不必遵从固定策略,这意味着可以通过经验缓存机制更有效率的训练价值函数,但基于TD-error的更新容易过高估计Q函数。

为解决DDPG过高估计Q函数的问题,Fujimoto等人提出的双延迟深度确定性策略梯度算法(twin delayed deep deterministic poli-cy gradient algorithm, TD3)[34]进行了如下改进:① 同时训练两个Q函数,选择输出较小的值;② 延迟更新策略网络,减小策略更新的波动;③ 在策略网络输出中加噪声,以平滑Q函数的估计误差。

DDPG与TD3虽然实现了连续动作问题的异策略学习,但由于其采用了确定性的动作策略网络,训练过程对超参数(如学习率α等)的调整比较敏感,而且确定性策略输出带来了对环境探索性不足的问题。因此,Haarnoja等人提出通过在Critic部分的Q函数中加入熵约束的软AC(soft AC, SAC)算法,学习过程中不但要最大化Q函数,同时要最大化动作的熵,以增强动作的探索性[35]。

1.3 基于模型的强化学习方法

RL的经典算法动态规划(dynamic programming, DP)以当前状态为根节点,根据状态转移函数与策略函数建立未来状态作为叶子节点的状态转移树型结构,根据树型结构计算每个状态下的叶子节点(后续状态)的期望累积回报,这是一种典型的MBRL方法。但这种方法在计算状态的价值时需要遍历所有以该状态为根节点的所有叶子节点状态,在状态空间很大的问题上实现起来复杂度过高。

基于模型的Dyna算法框架首先由Sutton等人提出[36],是一种结合了MBRL和MFRL的算法。该算法中,首先初始化一个状态转移模型,根据当前状态和动作输出下一状态和当前(s,a)下的奖励;初始化Q函数。在与环境交互过程中,根据Q函数结合贪婪策略进行轨迹的更新,根据交互轨迹对Q函数和模型分别进行更新;同时随机产生状态与动作输入模型后,利用模型输出的下一状态与奖励对Q函数进行n次更新。Silver等人提出的Dyna-2算法[37]对Dyna算法进行了改进:该算法在每轮的更新中需要重新建立一个称为瞬时记忆的Q′函数,利用Q′进行策略的选择以产生交互轨迹,对模型与被称为长期记忆的Q函数进行更新。

相比于Dyna算法每一次更新需要对环境进行完整的蒙特卡罗探索,蒙特卡罗树搜索(Monte-Carlo tree search, MCTS)算法[38]首先通过随机采样动作后得到当前状态为根节点的子节点,如果该子节点尚未被探索就将其加入蒙特卡罗树中,之后在该节点后用模拟交互的方法直到得到终止状态,根据模拟交互得到的终止状态获得的奖励对该子节点处的总探索数及胜利数(以围棋为例)信息进行更新,在之后对该节点的探索中以置信度上界(upper confidence bound, UCB)方法在此信息的基础上增加随机性并作为采样的依据。

MBRL在AlphaGo[39]算法中大获成功,在2016年AlphaGo以5∶0击败了欧洲围棋冠军樊麾,2017年以3∶0击败了专业9段棋手柯洁,在人工智能的研究中具有里程碑式的意义。该算法结合了MCTS与AC算法的优势,首先利用人类专业棋手的对决棋谱和监督学习方法对策略网络进行训练,并开创性地采用了一种自博弈方法进一步对策略网络进行提升,在MCTS的初始搜索中利用训练好的策略网络指导探索行为,避免了从零开始学习。

在其后续的改进版本AlphaZero中[40],进一步强化了自博弈方法的重要性,DeepMind团队利用与AlphaGo的自博弈代替人类专业棋手的棋谱来监督训练的方法大幅度提高了AlphaZero算法的训练速度与效果,同样利用MCTS方法进行策略搜索与状态转移模型的学习。

AlphaGo与AlphaZero算法的成功大大刺激了基于模型算法的研究热度,但这种专门针对围棋和象棋等棋类游戏的强化学习算法如何泛化在其他领域的问题中也被人们经常讨论和质疑。而MuZero算法的提出[41]为这个问题的解决提出了一种前景非常广阔的思路:通过环境转移模型在建模时以隐藏状态的形式进行表示与学习,在减小状态空间复杂度的同时不以精确表示真实的环境状态转移为目的,而是以对策略提升的贡献为评价指标,同时利用了MCTS方法以解决状态空间过大的问题。该算法的提出把AlphaGo及后续改进的算法拓展到雅达利游戏测试环境中,在同MFRL和其他MBRL基线算法的对比中取得了最好的结果。

近年来,人们开始考虑利用离线采样交互的轨迹代替智能体与环境交互利用试错的方法进行强化学习,如模仿学习与结合了生成式对抗网络(generative adversarial network, GAN)[42]思想的生成式对抗模仿学习(generative adversarial imitation learning, GAIL)[43]以及离线学习(offline reinforcement learning, ORL)[44]。这些方法立足于改善现存的强化学习算法在训练过程中必须不断重新与环境交互的过程,致力于解决利用离线的采样数据进行强化学习训练过程中存在的问题,也同样是强化学习的热点方向之一。

当强化学习应用在实际问题的解决中不可避免的遇到了在部分复杂控制问题中所遇到的维度灾难问题,特别是在下文中提到的集中式MARL问题中随着智能体个数的增加而出现的维度指数性增长。而分层强化学习在近年来由于其具有的分解复杂任务空间为子空间的特性,在解决状态空间非常大的问题时相比于其他强化学习方法具有明显的优势,受到了研究者们的广泛关注。分层强化学习中基于选项、基于分层抽象以及基于值函数分解[45]的思想已经部分应用于多智能体问题的解决中,特别是利用基于值函数分解的方法解决MARL方面已经涌现出了不少成果,是最近受到广泛关注的热点方向。

2 多智能体强化学习

MARL与单智能体RL所不同之处在于其要解决的是分布式部分可观测MDP(decentralized partially observable MDP, Dec-POMDP)。Dec-POMDP可用一个元组〈N,S,A,R,T,γ,O〉来表示,其中N表示智能体集合;S表示环境全局状态空间;A表示智能体联合动作空间,动作向量a=[a1,a2,…,ai,…]∈A,其中ai代表智能体i的独立动作;R表示当前状态-动作对(s,a1,a2,…,ai,…)下的全局奖励函数;T代表环境的状态转移函数T(s′|s,A)∈(0,1);γ为折扣因子;O为各时刻智能体部分观测状态向量[o1,o2,…,oi,…]。Dec-POMDP如图6所示。

图6 部分可观测MDP

对于多智能体在环境中的学习过程,当采用中心化训练时,以完全合作博弈来描述;当采用无中心化的完全竞争模式进行训练时,以完全竞争博弈来描述;当采用无中心化的混合策略进行训练时,即智能体间既竞争又合作时,以随机博弈来描述[46]。

MARL的优化目标可以用一个纳什均衡来表示:

(11)

MARL相比于单智能体强化学习的难点在于对每个智能体来说,其他智能体的策略优化过程构成了环境的一部分,因此对每个智能体来说,环境的状态转移概率是非平稳的,这就意味着如果不加限制地利用单智能体强化学习方法解决多智能体问题,会存在收敛困难的问题。

随着近年来DQN、DDPG等深度强化学习算法的提出,吸收了这些算法优点的多智能体深度强化学习算法逐渐发展起来并取得了一系列成果。

按照MARL算法的训练与决策方式,可以分为3种类型,即集中训练集中执行、集中训练分布执行与分布训练分布执行模式[52]。

集中训练集中执行模式下,通过一个中心训练并控制所有智能体的行为。Sukhbaatar等人提出了一种CommNet算法和隐层信息池化共享的思想,利用深度神经网络(deep neural network, DNN)的全连接性进行隐式的信息共享,同时利用平均池化方法可以适用于智能体数量变化的场景[53]。Peng等提出了一种BicNet算法,利用循环神经网络(recurrent neural network, RNN)的记忆功能,依靠隐藏状态hi在各智能体间共享信息[54]。

此类方法存在的问题主要是:随着智能体数量的增加,联合动作空间呈指数增长,导致了计算复杂度增加,训练难度加大;同时也无法解决智能体信用分配避免“懒惰智能体”问题。

在分布训练分布执行模式下,可分为基于独立值函数的学习——独立Q-学习(independent Q-learning, IQL)与基于AC结构的算法两种。其中,Tan等人最早提出IQL方法[55],在同构智能体前提下,作者证明了IQL能收敛到团队最优均衡策略;Littman等人提出的Team-Q算法能在确定环境条件下收敛,但如果环境是非平稳的则难以收敛[47];Matignon等人提出了一种滞后Q-学习算法[56],通过设置两个不同的学习率因子调整价值函数的更新;基于此,Omidshafiei等人采用基于RNN的DQN代替了之前的表格学习[57],加入RNN结构的DQN具有记忆能力,能在一定程度上克服环境的非平稳性造成的难以训练的问题。

基于AC结构的独立学习算法有Perolat等人提出的虚构AC算法[58],该算法通过对行动器与评判器设置不同的更新延迟,以增加策略更新的稳定性。

分布训练分布执行模式算法在无相互协作和全局信息的条件下进行独立训练存在的主要问题是训练难度大,随着智能体数量增加,收敛变得非常困难。

集中训练分布执行结构下智能体间可以建立通信从而传递信息进行协调,由于深度强化学习的兴起,智能体间可以利用DNN中的全连接层进行信息传递与融合,这方面具有代表性的算法有:Foerster等人提出的增强型智能体间学习(reinforced inter-agent learning, RIAL)与微分型智能体间学习(differential inter-agent learning, DIAL)[59],代表各智能体的DQN均以RNN构建并相互串联,将并行决策架构改为串行决策架构,利用RNN的记忆功能对智能体间的动作进行学习与协调;Mao等人提出了一种基于AC架构的多智能体协作学习方法AC-CNet与A-CCNet[60],其中AC-CNet在行动器端建立通信网络进行信息编码与交换,A-CCNet则在评判器端进行信息编码与共享;Lowe等人则提出了一种多智能体深度确定性策略梯度(multi-agent deep deterministic policy gradient, MADDPG)算法[61],在集中训练下,利用全局状态信息分别训练各个智能体的值函数网络,促进各智能体的策略网络进行更新。

针对集中训练的MARL算法无法有效解决智能体信用分配问题从而容易导致出现“懒惰智能体”现象的问题,Foerster等提出了一种反事实基线MARL(counterfactual baseline of MARL, COMA)算法[62],以非纳什均衡策略下联合Q函数的期望与纳什均衡策略联合Q函数得到反事实基线,依此评估单个智能体对总体收益所做贡献;而Sunehag等人则结合分层强化学习中的值函数分解方法,将其应用在MARL的智能体信用评价上[63],论文中提出的分解方法建立了两个强假设:① 联合价值函数对独立价值函数是单调的;② 联合价值函数与独立价值函数符合线性拟合的关系。这两点假设在实际情况下均不容易满足。因此,Rashid等人提出了一种改进的值函数分解方法——QMIX[64],该算法利用全连接层对联合值函数与独立值函数的关系进行非线性拟合,提升了分解的多样化,增强了独立值函数的表示能力。随着多头注意力机制[65]在深度学习研究中获得越来越广泛的关注,Yang等人提出了一种利用泰勒展开对联合值函数进行非线性分解的Qatten算法,并利用多头注意力机制网络实现了不同阶数系数的训练,在多智能体实验环境星际争霸多智能体挑战赛(starcraft multi-agent challenge, SMAC)中取得了很好的效果[66]。

MARL方法近年来获得了迅速发展,虽然还存在理论支撑较少、算法的泛化性不足等问题,但在应用并解决自动驾驶[67]、集群规划[68]、资源调度[69]等问题中已经显示出较好的前景,在认知无线电与动态频谱分配的研究者中也有越来越多的人将目光投入这一生机勃勃且前景广阔的研究领域中,涌现出了一些开创性的工作,下面将进行简要介绍。

3 基于多智能体强化学习的动态频谱分配方法

基于传统算法如图染色法、博弈论与交易理论的方法需要利用中心控制实体对频谱资源进行分配。这些方法存在的共性问题主要是频谱分配控制中心与用户间的通信需要占用大量资源,并且这些算法鲁棒性差,环境发生变化时必须重新进行分配,因此时间开销比较大,达不到实际应用中动态频谱分配的实时性要求。

而利用MARL方法恰好能解决这样的问题,各智能体可以根据对信道环境的部分观测信息,根据训练所得的经验进行分布式决策并收敛到最优。当外部环境变化时,各个用户(智能体)可以根据训练好的策略迅速进行响应,并快速收敛。这种智能化的动态频谱分配方法在对动态环境的适应性和重新分配频谱的实时性上相比传统的算法具有巨大的优势。

3.1 基于Dec-POMDP的动态频谱分配模型分析

动态频谱分配模型的研究是研究动态分配算法的基础,也是认知无线电理论研究的重要方面,Zhao等人[70]总结了动态频谱分配的研究成果,将动态频谱分配模型总结为专用模型、开放共享模型和分层接入模型3种,其中专用模型分为频谱产权模型与动态专有模型;分层接入模型分为频谱下垫接入模型与机会式频谱接入模型两种。动态频谱分配模型分类如图7所示。

图7 动态频谱分配模型

其中频谱产权模型下各用户把拥有的频谱作为可自由支配的财产,可以互相租赁、出售,无需监管部门介入;动态专有模型下根据各用户的频谱需求在空域与频谱对频谱资源进行快速分配;开放共享模型中无主次用户的区别,可以采取合作(或中心化)和竞争(或去中心化)的频谱分配方式,在工业、科学、医疗频段这些无授权用户的频段中可以采用这样的接入方式;频谱下垫接入模型中认知用户通过微功率技术(如超宽带技术)接入频谱,需要满足主用户接收端的干扰温度约束[71];机会式频谱接入模型既是Mitola在关于认知无线电的定义中建议的一种模型,也是最能够兼容当前的频谱管理政策与无线电系统的模型,因此成为了当前认知无线电研究领域的主流[70]。

南京邮电大学的夏婷婷等人针对多认知用户下的机会式频谱接入问题,提出了一种基于Dec-POMDP的模型[73],以各信道的可用性作为状态向量s(t)=[s1,s2,…,sN],sn∈{0(空闲),1(占用)},1≤n≤N,以各认知用户的频谱接入行为作为动作向量a(t)=[a1(t),a2(t),…,aN(t)],其中an(t)表示各用户在时隙t的频谱接入动作(选择哪个信道接入)。以认知用户在时隙t的吞吐量作为奖励函数,通过作者提出的发送前请求(request to send, RTS)和发送前确认(confirm to send, CTS)以及在观测到可用信道时采取的随机等待时间等机制进行信道的准入,以本地对s(t)的观测和是否准入发射信道作为观测值o(t)。

电子科技大学的郭冰洁提出的Dec-POMDP动态频谱分配模型中各用户的时隙中加入确认字符(acknowledge character, ACK)状态字,将观测信道状态增加为4种:空闲、繁忙、成功、失败。除此之外,还在观测信息种加入了繁忙率指标来表示截至当前观测时隙观测信道为繁忙的次数与对该信道的总观测次数的比率[74],通过加入该统计量表征各信道的繁忙程度。但该模型在奖励函数的设计中没有考虑用户业务的服务质量(quality of service, QoS),仅简单地以接入信道成功与否作为奖励的依据,在实际动态频谱分配中,不仅要考虑到用户能否接入频谱,还必须考虑接入同一信道后造成的干扰(尤其是对主用户)对QoS造成的影响,在此约束条件下进行权衡。

电子科技大学的何浩考虑了在能效约束下优化认知用户的总吞吐率的问题,在文献[75]中,他在将信道状态建模为有限状态马尔可夫信道(finite state Markov channel, FSMC),在考虑了不同信道状态(信道增益)下基于M元正交振幅调制下满足误码率门限下的最小功率约束条件下,将所有信道的信道状态与频谱感知结果作为状态向量s,将各用户的信道选择与速率选择(调制信息)作为动作向量a,目标函数为在平均功率耗费门限约束下最大化各用户的总吞吐量,由于认知用户对状态信息的观测由认知用户发送导频到基站，由基站估计后回传得到,因此也是部分观测状态,本文在这种Dec-POMDP模型下提出其最优策略满足纳什均衡。

上面所提的这些模型中都没有将发射功率控制及其对网络效用造成的影响进行考虑,广东工业大学的叶梓峰提出频谱下垫接入模型中[76],通过微基站作为感知节点辅助次用户进行频谱接入决策。将认知无线电网络中的微基站接收到的主用户、次用户信号与噪声功率的和作为状态向量,以离散化的功率水平控制作为动作向量,在主用户QoS满足门限要求时,其奖励函数为次用户的信噪比和;当主用户QoS在次用户接入后不满足门限要求,则奖励函数为次用户信噪比和的负值。目标函数为最大化网络的总吞吐率。

综上所述,把动态频谱分配问题映射到Dec-POMDP模型中,其状态空间S主要表示当前频谱分配的状态、信道状态(信道增益)以及主用户接收端的信号与干扰加噪声功率比(signal to interference plus noise ratio, SINR);决策(动作)空间A主要可以分为两个方面,一是频谱的分配,二是认知用户的功率控制(功率水平的选择);而奖励函数R是MARL的关键,一般是在频谱分配约束(一个信道同时最多只能分配给一个次用户)下的总频谱利用率与主用户干扰温度约束下的认知无线电网络的总吞吐率以及主用户QoS的变化。

Dec-POMDP与动态频谱分配过程之间的映射关系如图8所示。

图8 基于Dec-POMDP的动态频谱分配建模

3.2 基于Dec-POMDP模型的动态频谱分配方法

目前基于Dec-POMDP模型和MARL的动态频谱分配算法分为:基于独立Q-学习(independent Q-learning, IQL)的方法、基于合作Q-学习(cooperative Q-learning, CQL)的方法、基于联合Q-学习(joint Q-learning, JQL)的方法以及基于多智能体AC算法(multi-agent AC，MAAC)的集中训练分布执行方法。

3.2.1 基于IQL的动态频谱分配方法

基于独立Q-学习的方法使每个智能体(用户)根据独立观测的信息利用式(3)和式(4)进行状态价值估计与策略的优化,通过大量训练收敛到稳定点。

Li等人分析了两认知用户下无协同的基于IQL的动态频谱分配过程,证明并验证了认知用户无论在仅获得部分观测信息或完整观测时均可收敛到稳定点(纳什均衡点)[77];Teng等提出了一种基于IQL的竞价拍卖机制进行动态频谱分配[78],次用户通过IQL算法学习最优的竞价策略,主用户则根据次用户的策略产生可接受价格向量确保自身利益,该算法有效提升了竞价效率;Wu等根据认知网络中用户间由于频谱接入行为造成的相互干扰构建了IQL的奖励函数[79];伍春等将无监督机器学习方法k-means与IQL算法结合,用户进行聚类减小智能体数量后,用可变学习率IQL方法进行策略优化[80];除此之外,Zia等人讨论了在多层异构网络下,D2D通信用户与蜂窝用户间的动态频谱共享问题,利用IQL算法进行优化并与两种理想状态方法进行了对比[81]; Asheralieva等人利用IQL算法优化一个基站内的D2D通信用户动态频谱分配问题,并提出了一种利用当前状态下Q函数的的玻尔兹曼分布作为策略函数,增加策略的随机性与探索性,与贪婪Q-学习、其他两种理想状态下的传统算法进行了对比,证明了基于MARL方法相较于传统方法在性能上的优越性[82]。

上述方法均采用了表格学习对各用户的独立Q函数进行更新,而这种方法随着智能体数量、观测状态空间的增加,Q表的更新和收敛速度会受到很大的影响,因此Naparstek等人结合DQL领域的进展,提出利用DQN拟合各用户的Q函数,并加入循环神经网络层如长短期记忆(long short-term memory, LSTM)网络或门控循环单元(gated recurrent unit, GRU)网络,利用构造的DQN的记忆能力和认知用户的同构性,仅训练一个DQN网络将其在用户间共享,利用RNN的记忆性在用户间建立协调关系,利用经验回放和随机采样等DQN中的技巧加快了训练速度[83]。Zhao等人提出的MADQN算法是一种结合了DQN的IQL方法,在仿真实验中用户数较少的环境下,与基于比例公平权重的信道选择算法和随机分配算法进行对比,在单用户吞吐率、系统总吞吐率、单用户的成功发送概率等性能指标上优于两类传统方法[84]。Nasir等人对基于DQN与IQL的认知无线电网络中的功率分配算法进行了研究,与传统算法进行对比后,结果表明该算法不仅在频谱效率和系统总吞吐率上取得比传统算法更好的表现,在收敛速度上也有不低于传统算法的表现[85]。

基于IQL算法的动态频谱分配方法忽略了对于单个用户而言外部环境变化具有的非马尔可夫链的性质,其状态转移模型并不是平稳的,加之在值函数的优化上没有考虑用户间协作产生均衡策略的约束,因此适用的用户数量较少,训练时收敛速度慢,且不一定能收敛到最优策略,往往得到的是次优策略。

3.2.2 基于CQL的动态频谱分配方法

基于合作Q-学习的方法中单个用户Q函数中不仅考虑当前状态下自身动作,还包含了其他用户动作的因素,通过考虑其他智能体的策略优化趋势,使得单独用户的Q函数可以更快收敛到稳定点(或纳什均衡点)。

CQL算法在更新独立Q函数过程中需要得到其他所有智能体的动作与Q函数以及环境的联合状态信息,在分布式决策条件下,全局状态实际上不容易得到;这种完备的信息交互在实际的通信网络中将造成很大的通信开销,难以实现。

3.2.3 基于JQL的动态频谱分配方法

基于JQL的方法是一种集中训练集中执行的方法,该方法将所有用户的动作视为在全局环境状态下的统一动作,因此将分布执行下智能体决策的部分可观测马尔可夫决策问题简化为一般的马尔可夫决策问题,从而可以直接应用单智能体强化学习。

Wang等人将DQN作为集中训练集中执行算法,在实验环境中验证了算法的收敛性,与Whittle索引启发式算法和信道正相关条件下的最优短视算法进行对比,结果表明DQN能收敛到与最优算法相近的结果[88]。

但这种JQL算法首先需要进行集中决策,在每个状态下都必须确保中心对用户的完全控制,因此存在通信开销大的缺点;其次是该算法要求得到对环境的完整感知信息,由于多径、阴影衰落和路径损耗,这种对环境的完整感知在实际中难以做到;加之该方法随着用户数量增加,其评估与决策的动作空间维度呈指数级增长,容易造成值函数表示困难、难以训练等问题。所以其适合解决用户数量较少的问题,不适合解决用户数量庞大如超密集网络的动态频谱分配问题。

3.2.4 基于MAAC的动态频谱分配方法

由于多智能体环境中单个智能体的环境非平稳性,给基于Q-学习的算法带来了很大的挑战,虽然可以利用合作学习或集中学习的方法减缓因此造成的影响,但收敛速度慢、容易陷入局部最优或某一固定点以及协同、控制中对通信需求较大等缺点仍然难以有效解决。

因此,随着近年来集中训练分布执行的MARL算法取得了很多突破与进展,利用该类型的MARL算法解决多用户动态频谱分配策略的训练就显的非常具有研究意义与前景。

Li等人提出了一种利用MAAC算法解决车联网环境中D2D用户与蜂窝用户间的动态频谱分配问题的方法。并在MAAC算法的基础上,提出了一种基于距离降低训练样本需求的NAAC算法可以进一步加快训练的速度,降低计算复杂度。在实验中将MAAC和NAAC算法与DQN、IQL以及基于主从博弈的随机学习算法(stochastic learning algorithm, SLA)进行了对比,无论在用户的中断率还是收敛后的网络整体效用上均大大超过了DQN、IQL和SLA算法[89]。

表1中对比了4种基于多智能体强化学习方法的动态频谱方法的特点。

表1 4种方法特性对比

4 基于多智能体强化学习的动态频谱分配方法关键问题

通过总结归纳上述文献可以发现,现有的文献中在建立基于Dec-POMDP模型的MARL动态频谱分配算法中往往将SUA与OSA模型分开考虑,即利用功率控制算法解决SUA问题,利用频谱选择接入算法解决OSA问题。而在实际的动态频谱分配问题中,频谱分配与功率控制需要同时考虑;在集中训练分布执行的MARL算法中,集中训练过程需要对环境具有完整的观测或估计,如何由认知用户的部分观测信息推断出频谱分配的完整信息是一个重要的问题;当前的MARL算法多数应用在智能体数量固定的环境中,而认知无线电网络中用户数量可能是动态变化的。

通过以上分析可以进一步梳理出如下3种基于MARL的动态频谱分配方法的关键问题。

(1)基于Dec-POMDP建立更合理的动态频谱分配模型

在基于OSA的模型中,往往只考虑了频谱的选择,次用户在频谱感知后只要检测到主用户信号的存在,就要立即从该信道中退出,这种接入方式既增加了次用户的中断率,容易增加次用户的通信时延,又使得次用户的频谱利用率降低;而基于SUA的模型中,基于超宽带等技术的认知用户受限于在所有频段上的发射功率都处于较低水平,为保证主用户的干扰温度约束,信道容量容易受限,在主用户未占用的频带内,功率不能灵活调整以提高QoS。因此,可以考虑结合频谱下垫接入与机会式频谱接入模型,在主用户占用的频带内,在主用户干扰温度约束下以SUA接入,而在主用户尚未占用的频带内以OSA接入,以进一步提高频谱利用率与次用户QoS。

基于MARL的动态频谱分配方法中,奖励函数以及产生的即时奖励是促进算法优化的激励信号,如何合理设置奖励函数是算法能否快速收敛的关键因素,尤其是奖励函数中体现对主用户QoS的保护以及提高频谱利用率的约束条件是算法合理性的关键条件,需要进行进一步深入研究。

(2)基于分层抽象建立部分观测到状态的映射

传统的POMDP问题的解决方法中加入了信念向量的辅助,信念向量由历史观测值{ot,at,ot-1,at-1,…,o0,a0}组成的观测向量由状态转移函数进行变换后得到一个关于真实状态转移的概率分布。但实际上状态转移函数是未知的,而利用分层强化学习可以解决这个问题,在不需要信念向量的条件下,通过设置选项、分层抽象等方法，从观测信息中对真实的环境全局状态进行学习,映射到动态频谱分配问题中,也就是利用认知用户的不完全频谱感知信息在集中训练架构下通过分层强化学习的方法估计真实的频谱分配状态,这也将解决集中训练方法中真实状态不可知条件下全局Q函数的学习问题。

(3)认知无线电网络的动态拓展

目前基于MARL的动态频谱分配算法存在的主要问题之一是如何应用在用户数量变化的认知无线电网络中,换言之,也就是如何解决智能体策略的泛化性。利用集中训练分布执行的模式有效解决了多智能体间环境的非平稳性导致的训练收敛性问题,但集中训练的前提是多智能体整体所处外部环境是平稳的,一旦加入新的用户,即智能体后,多智能体整体的外部环境也变得非平稳,这就导致一旦网络内用户数量发生变化,网络内的所有用户的策略都需要重新进行训练。

随着离线强化学习的提出,这种利用其他智能体与环境的交互轨迹对新的智能体策略进行训练的方式为解决智能体策略的泛化性或者认知无线电网络用户的可扩展性提供了新的思路。

5 结束语

基于传统理论的动态频谱分配算法存在分配时间长,计算复杂度高,不适应动态变化的无线通信环境且不适合分布式决策的缺点,而随着MARL为代表的群体智能技术的兴起和发展,基于这种群体智能技术的动态频谱分配方法相比于传统方法来说具有智能化、实时化和分布化的诸多优势。本文对现有的基于MARL的动态频谱分配方法的研究现状进行了梳理与总结,根据应用算法框架将这些研究成果分为4种类型,比较了4种类型方法的优劣,结合RL、MARL及其在动态频谱分配问题中的应用,提出了模型建立、从部分观测信息中分层学习以及认知无线电网络用户的拓展性中存在的关键问题,并分析了解决思路。