基于Q-Learning的机会频谱接入算法

范文翰 赵旦峰

摘要 针对认知无线电在动态信道业务特征场景下的机会频谱接入问题进行研究。将Q-Learning理论应用于频谱接入问题，提出一种基于Q-Learning的适用于动态信道业务特征的机会频谱接入算法。该算法中认知用户通过与外部环境进行交互和迭代来获取信息，从而选择适当的接入策略来降低频谱冲突率。通过将Q-Learning中学习速率设置为动态变化值，使得算法可以在外部环境特征发生改变后快速地再次收敛。仿真结果表明，该算法可以使认知用户在频谱环境未知的情况下选择更加空闲的频段，有效降低频谱冲突率，同时明显提高了动态信道业务特征场景下的收敛速度。

【关键词】认知无线电 机会频谱接入 Q学习冲突 概率

1 引言

近些年来，随着技术和经济水平的不断提升，人们对于无线通信业务的需求不断增长，造成了频谱资源紧缺的情况，为了解决这一问题，专家学者提出了认知无线电概念。机会频谱接入（opportunistic spectrum access，OSA）是认知无线电系统的关键技术之一，其核心思想是认知网络中的认知用户可以在授权频段未被授权用户使用的情况下机会地接入该授权频段。通过对时间、频域、空域三维空间内的大量空闲频谱资源的利用，认知无线电技术可以显著地提高频谱资源的利用率。

机会频谱接入技术的研究难点是认知用户如何在信道环境先验知识未知的情况下接入合适的频段。为了解决这一问题，文献[2]将Q学习算法应用到机会频谱接入中，文献[3]提出一种基于双动作0学习算法的接入方案，文献[4]通过将Q学习算法和拍卖算法结合提高了算法的效率。但是这些算法都没有考虑当信道环境特征发生改变后算法的收敛问题，因此本文在上述算法的基础上，提出一种适用于动态信道特征的Q-Learning频谱接入算法，使认知用户可以在信道环境特征发生改变后可以重新迅速收敛。

2 系统模型

在认知网络中，系统内部存在多个授权用户，授权用户将根据自己的需求占用某些授频带，频段的占用状态随着时间而改变。如图1所示，在认知网络中，当某个频段暂时没有被授权用户使用时，认知用户就可以抓住这个机会利用该频段来进行通信，当授权用户重新占用这段频谱后，认知用户需要迅速停止在该频段上的通信业务以避免干扰授权用户的通信。

3 基于0-Learning的机会频谱接入算法

3.1 Q-Learning理论

Q学习（Q-Leaming）算法是一种重要的无模型强化学习算法，由Watkins在1989年提出。Q-Learning将智能体与外部环境交互的过程看作为一个马尔科夫决策过程（ Markov DecisionProcesses，MDP），即未来状态的概率分布不受历史状态影响，只和当前状态相关。决策者只以當前状态为依据来制定合适的策略。对于未知环境下的决策问题，马尔可夫决策过程有一套统一的模型，其模型一般可以用四元组来表示。其中，S表示智能体所处外部环境的状态集合;A表示智能体可以执行的动作集;T为系统的状态转移函数，通常用T：AxS→P（s'|s，a）来表示智能体在执行了动作a∈A后，状态从s∈S转移到s∈S的概率;R代表回报，即智能体执行动作a之后从外部环境获得的收益，正数表示正收益，负数表示负收益。

在Q-leaming算法中，智能体通过不断与环境交互来获取信息从而制定更优的策略，即在每一次迭代过程中，智能体的目的就是根据当前状态寻找能够最大化期望的长期累积回报的动作，如式（2）所示为长期累积回报的最大值：

3.2.1 问题映射

算法将O学习理论应用于认知网络中，因此将认知用户的资源调度过程建模为一个有限马尔可夫决策过程（MDP），其中主要包括状态空间S、动作空间A、即时回报r等等。

（1）状态空间S：S={s1，S2，…，S_k}表示当前认知用户可以使用的所有频段，当认知用户状态为Sl时表示认知用户此时占用第i个频段。

（2）动作空间A：A={a1，a2，…a_k）表示认知用户可以执行的动作集合。动作空间A由k个动作构成，表示k个可用频段，认知用户执行动作a_i表示认知用户将占用频段i，同时智能体进入状态s.。

（3）即时回报r：回报值r体现环境对认知用户的反馈。算法主要目的是降低认知用户与授权用户之间的冲突率，即时回报r主要体现主次用户之间的冲突情况，其表达式为：

（4）学习速率：在一般的0学习算法中，学习速率α的值将随着Q值得迭代逐渐变小，这种方法既可以使Q学习初期拥有更快的学习速率，又可以避免产生不成熟收敛。但是当环境的特征发生改变时，算法需要重新收敛，在学习速率较小的情况下，算法的收敛速度将很慢。为了解决这个问题，提出了适用于动态环境特征的Q-Learning算法，算法将学习速

率α设置为动态值，其表达式为：

a=l/（1+arr（s，a）） （6）

其中arr（s，a）为智能体到达状态.动作对（s，a）的次数，每当智能体到达该状态.动作对一次，并且环境产生正反馈时，arr（s，a）的值将增加，而当环境产生负反馈时，arr（s，a）将以指数形式递减。因此，随着迭代的不断进行，arr（s，a）的值不断增加，相应的α将不断减小，算法逐渐以概率1收敛于最优状态，若环境特征突然改变，访问（s，a）状态对将获得环境的负反馈，arr（s，a）的值将变小，随着访问次数和负反馈次数的增多，arr（s，a）的值将迅速减小，使得u迅速增大，算法将重新拥有更快的学习速率并快速收敛于新的状态。

3.2.2 Boltzmann学习规则

拥有学习能力的认知用户以0值表为依据选择最优策略，其最优策略一般是最大化长期累积回报，即选择拥有最大0值得动作。在算法迭代初期，智能体需要通过不断地试探来对环境进行探索，当智能体获得了足够的信息后就可以对这些信息进行利用。探索可以使用户访问更多的状态，增加用户获得更多长期回报的可能性，而利用可以使认知用户选择最优的策略来增加其长期回报。但是这种方法存在一定问题，当智能体对环境的探索不够完全时，算法有可能收敛于错误的状态。为了避免这种情况的发生，Q学习要求智能体能够尽可能多地访问每个状态.动作对，因此认知用户在制定策略的时候不能简单地选择最大0值对应的动作。算法将采用Boltzmann学习规则，智能体根据Q值大小以不同的概率选择各个动作，即Q值大的动作被选中的概率大，Q值小的动作也有较小的可能被选中，其概率表达式为：

其中P（a./s）表示认知用户在状态s下选择动作a_i的概率，T是温度系数，表示Q值大小对概率的影响程度。T较大时Q值对概率的影响较小，不同0值对应的概率相差较小，当T较小时，Q值变化会对概率产生比较明显的影响。算法将根据退火原理使温度系数T随着迭代次数的增加不断减小，在算法迭代初期即使某个Q值较大也不会产生用户只选择该Q值对应的动作的情况，而随着迭代不断进行，用户对外部环境的探索逐渐完善，此时的T值较小，Q值相差较大的动作之间对应的概率也有较大差距，用户选择较大Q值的概率将明显高于选择较小Q值的概率。通过引入Boltzmann学习规则可以使智能体从探索阶段逐渐过渡到利用阶段。

3.2.3 算法流程

算法的具体流程为：

步骤1：初始化Q值表、迭代次数t，arr（s，a）值、折现因子γ、温度T等参数，随机选择初始状态sO;

步骤2：观察当前所处状态s.，根据当前Q值表和式（8）计算各动作执行概率并依据得到的概率选择动作a.;

步骤3：感知模块对频段i进行侦测判断此时频段i是否空闲，若空闲进入步骤4，若繁忙进入步骤5;

步骤4：执行动作a_i，并传递环境的回报值r，进入步骤6;

步骤5：计算冲突概率，并传递环境的回报值r，进入步骤6;

步骤6：根据式（5）更新Q值，根据环境的反馈更新arr（s，a）值，更新状态为s，t加l;

步骤7：判断t是否满足结束条件，若不满足，进入步骤2，若满足则算法结束。

4 仿真结果与分析

为了验证算法的有效性，本文将对三种Q-Leaming算法分别在静态信道业务特征和动态信道业务特征两种场景进行仿真对比，三种算法分别为α递减、a=0.5以及本文所提出的α动态变化的Q-Learning算法。仿真长度为20000个时隙，认知用户在每个时隙根据Q值表以不同概率接入某一频段，即每个时隙是认知用户的一个迭代过程，认知用户迭代20000次后停止仿真。为了便于分析，将20000个时隙分为40个相等的学习阶段统计认知用户与授权用户的冲突概率，同时采用蒙特卡洛实验策略，每个时隙将进行100次相互独立的实验并取其平均值为最后的实验结果。

基于Q-Learning的频谱接入算法的参数设计如下：频段个数m=6，静态信道业务特征场景下的频段的业务负载分别为l，1，0.7，0.5，0.3，0.05，动态信道业务特征场景下的频段的业务负载变化规律如表1所示。为了体现长期回报对策略选择的重要性，设置折现因子γ=0.8。算法将采用Boltzmann学习规则，设置其初始温To=l×l0⁵⁰，终止温度Tend=l，温度To将随着迭代次数增加以参数为0 9的指数规律逐渐递减，直到减小至终止温度后停止递减。

图2为信道业务特征保持恒定的情况下三种Q学习算法下的主次用户间的冲突概率，可以明显看出三种Q学习都在大约第四个统计阶段收敛。但是当a=0.5恒定不变时，冲突概率收敛于0.2左右，远远高于另外两者，说明出现不成熟收敛。在静态的信道业务特征的情况下，α递减和动态α两种Q学习算法的性能表现几乎相同，二者的冲突概率几乎同时收敛于0.1。

图3为动态信道业务特征下的三种Q学习算法下的冲突概率，通过对比三种算法可知表现最差的是α递减的Q学习算法，当信道特征发生改变后，其主次用户的冲突概率激增至1，而且在接下来的迭代过程中冲突概率并没有呈现迅速降低的趋势，直到第三十个统计阶段后冲突概率才开始下降至收敛值，这是因为迭代多次后，α的值递减至较小的值，算法的学习速率将变得很低，在信道特征改变后算法无法快速学习新的环境知识。而α=0.5的Q学习算法在信道特征改变后主次用户的冲突概率并没有出现比较明显的增加，这是因为α=0.5的Q学习学习速率较大，能够迅速学习新的环境知识，但是固定较大的α值使认知用户偏向于选择一些迭代初期Q值较大的动作，即认知用户并没有遍历全部的状态，错过了更优的动作，造成算法的不成熟收敛，其冲突概率维持在0.2左右高于正常的最低冲突概率0.1。相比于这两种0学习算法，α动态变化的Q学习算法首先可以将主次用户的冲突概率迅速降低至0.1左右，并且能够在信道特征发生改变后迅速收敛至新的概率值。因此在信道业务特征动态变化的情况下，α动态变化的Q学习算法要明显优于α恒定和α递减的Q学习算法。

5 结论

本文针对动态信道业务特征情景下0学习的收敛问题提出了一种基于Q-Leaming的机会频谱接入算法，通过令学习速率α以一定规律动态变化的方式使算法能够适用于信道业务动态变化的场景。仿真结果表明，當频段的业务特征发生改变后，算法可以迅速收敛于最优策略，即认知用户与授权用户的频谱冲突率最低。

参考文献

[l]Mitola J I，Maguire G Q J.Cognitiveradio： making software radiosmore personal [J]. IEEE PersCommun， 1999，6 （04）： 13-18.

[2] Alsaleh 0，Hamdaoui B，Fern A.Q-learning for opportunistic spectrumaccess [C]. Interna tional

Wireles sCommunications and Mobile ComputingConference. ACM， 2010： 220-224.

[3]吴启晖，刘琼俐，基于DAQL算法的动态频谱接八方案[J].解放军理工大学学报：自然科学版，2008，9 （06）： 607-611.

[4] Chen Z，Qiu R C.Q-learning basedbidding algorithm for spectrumauction in cognitive radio [C].Southeas tcon，2011

Proceedings ofIEEE. IEEE， 2011： 409-412.

[5]张凯，李鸥，杨白薇，基于Q-learning的机会频谱接入信道选择算法[J].计算机应用研究，2013， 30（05）：1467-1470.

[6]Watkins C J C H.Learning from DelayedRewards [J]. Robotics & Au tonomousSystems，1989，15 （04）： 233-235.

[7]桂林，武小悦.部分可观测马尔可夫决策过程算法综述[J]，系统工程与电子技术，2008， 30 （06）：1058-1064.

[8] Kaelbling L P，Littman M L，MooreA W. Reinforcement Learning：ASurvey[J]. J Artificial IntelligenceResearch，1996，4（01）：237-285.

[9] Gosavi A. Reinforcement Learning：A Tutorial Survey and RecentAdvances [J]. Informs Journal onComputing， 2009， 21 （02） ： 178-192.

[lO]Guo M，Liu Y，Malec J.A new Q-learningalgorithm based on the metropoliscriterion. [J]. IEEE Transactions onSystems Man & Cybernetics PartCybernetics A Publication of theIEEE Systems Man & CyberneticsSociety， 2004， 34 （05）： 2140.