基于多智能体Q学习的异构车载网络选择方法*

聂 雷，刘 博，李 鹏，何 亨

(1.武汉科技大学计算机科学与技术学院，湖北 武汉 430065；2.武汉科技大学智能信息处理与实时工业系统重点实验室，湖北 武汉 430065)

1 引言

随着城市交通的飞速发展，汽车保有量在近十几年来急剧增长，导致交通拥堵和安全问题日益突出[1]。近年来，车载自组织网络VANET(Vehicular Ad hoc NETworks)作为一种结构开放的车辆通信网络，在交通信号控制、内容协助下载、车辆路径规划和紧急消息广播等方面得到了广泛的研究与应用[2 - 5]，有效推动了智能交通的发展。

车载网络中的各类服务与应用依赖于接入网络中数据的可靠传输和交互，随着移动通信技术的飞速发展，具有高速率、低时延优势的5G通信技术近几年受到了人们的青睐。然而，现阶段的5G网络在短时间内无法实现全面部署，此外单一类型的网络难以满足终端用户的多样化需求[6]，因此多种无线网络共存的车载网络，即融合5G通信的异构车载网络是城市智能交通发展的必然趋势。由于车辆的移动性和用户需求的多样性，导致异构车载网络存在拓扑结构频繁变化和网络资源利用不均衡的现象。如何保证车辆终端进行高效的网络选择和切换，在保障用户服务质量QoS(Quality of Service)的同时提高网络资源利用率是现阶段亟需解决的问题[7]。

上述问题的求解可以看作是一个多目标优化的决策过程，目前有大量基于多属性决策MADM(Multi-Attribute Decision-Making)的研究成果[8 - 10]，与传统的基于单因素决策的方法[11]相比较，它们能够较好地提高网络属性权重和网络性能评价的准确性，从而为网络的选择和切换提供依据。然而，该类方法主要针对单台车辆终端进行决策，无法得到系统整体长期有效的切换策略集合，不利于异构网络资源的合理利用。Q学习(Q-learning)是一种基于系统状态下动作回报价值且与模型无关的强化学习算法，其利用智能体与环境的交互来迭代学习优化策略，从而实现特定的优化目标，基于Q学习的方法能够更加有效地解决异构网络环境下的网络选择问题。然而，现有基于Q学习的方法通常存在由状态空间过大引起的迭代效率低下和收敛速度较慢的问题，同时Q值表更新产生的过高估计现象容易导致网络资源的不均衡利用。

考虑到未来融合5G通信的异构车载网络环境，本文提出一种基于多智能体Q学习的网络选择方法MQSM(Multi-agent Q-learning based Selection Method)。该方法的目标是在融合5G通信的异构车载网络环境下得到普遍适用的系统长期运动状态下的最优网络切换策略集合，在保证车辆终端用户的良好QoS体验的同时，提高异构车载网络的资源利用率。

2 相关工作

异构车载网络环境下车载终端用户如何选择接入网络可直接影响其服务质量和网络资源的利用率。基于多属性决策的网络选择方法通过网络的多种属性对网络性能进行评估，从而为用户提供选择网络的依据。文献[12]提出了一种结合层次分析法AHP(Analytic Hierarchy Process)的多标准访问选择方法MCAS(Multi-Criteria Access Selection)，通过设计能效、信号强度、网络成本、延迟和带宽的效用函数建立了多约束优化模型，并提出了一种启发式算法计算效用函数的最优解，极大地提高了对网络性能评价的准确性。文献[13]提出了一种基于网络属性和用户偏好的异构网络选择方法，该方法结合了3种基于多属性决策的方法来提高效用函数的准确性，这些方法包括模糊层次分析法FAHP(Fuzzy Analytic Hierarchy Process)、熵Entropy和最优理想解排序法TOPSIS(Technique for Order Preference by Similarity to an Ideal Solution)。文献[14]提出了一种基于效用函数和TOPSIS的新策略，通过添加或删除网络来消除异常排名，并选择最高排名的网络作为最优解。然而，基于多属性决策的网络选择方法仅从优化单台车辆的角度出发，没有考虑到系统中其他车辆的信息和整体网络资源的利用情况。

与基于多属性决策的网络选择方法不同，基于Q学习的网络选择方法更加倾向于获得系统长期有效的最优网络选择决策集合[15,16]。文献[17]提出了一种基于Q学习的垂直切换算法，目的是获得最大化用户体验质量QoE(Quality of Experience)效用值的最优网络。然而该模型的回报值奖励方法过于简单，难以适应网络属性较多的异构车载网络环境。文献[18]提出了一种多智能体协作学习方法CMA-DQN(Cooperative Multi-Agent learning based on Deep Q-Network)，该方法将蜂窝网络中的用户进行划分，通过多个智能体的协作学习来获取回报值，并使用Double Q-Learning算法进行Q值表更新，有效解决了单表Q学习在状态空间过大时产生的无法正常收敛问题。文献[19]提出了一种双Q学习路由协议DQLR(Double Q-Learning Routing)来预测消息的下一跳传播，实验结果表明，双Q值表交替更新的方式比单表更新的方式更为稳定。文献[20]提出了一种多智能体网络选择算法MANSA(Multi-Agent Network Selection Algorithm)，将状态相似的车辆用户划分为一个智能体，每个智能体采用一个Q值表进行学习更新。然而该方法中的智能体彼此之间不交流学习经验，并且只采用单Q值表更新方式，容易出现过高估计的问题。文献[21]提出了一种基于Q学习的网络选择机制QBNS(Q-learning Based Network Selection)，其将网络容量和用户的服务质量作为网络性能的评价指标，通过求解自定义的优化方差获得了更好的总回报值，但该方法同样存在由单表更新引起的过高估计现象。

基于多属性决策的网络选择方法在评价网络性能方面具有较高的准确性，例如MCAS[12]方法，然而该类方法无法得到系统整体长期有效的最优切换决策集合。基于Q学习的决策方法在上述方面有着独特的优势，但是现阶段仍然存在许多问题，例如MANSA[20]和QBNS[21]方法，虽然都通过Q学习优化了决策模型，且前者还提出了一个简单的多智能体分割方法，但是核心的回报值函数设计过于简单，无法准确体现网络性能效用评分；此外，Q值表更新方式单调，无法应对更为复杂的异构车载网络环境。针对以上问题，本文提出了一种基于多智能体Q学习的异构网络切换方法，其关键在于使用一种综合效用函数来计算动作的即时回报值，极大地提高了回报奖励值的准确性，并采用一种多智能体协作学习方式提高学习迭代的效率，同时引入了多表交替更新来解决过高估计问题，与同类方法相比，该方法具有更好的稳定性，提高了网络资源利用率。

3 系统模型与假设

本文将一定地理范围内的异构车载网络作为整体进行分析，对应的系统模型如图1所示。该系统模型展现了一个典型城市交通环境下的异构车载网络环境，且该系统模型满足以下假设条件：

(1)车辆行驶在多车道的城市道路上，其速度和方向随着时间在不断变化；

(2)来自4个移动通信基站的信号(分别是LTE、WLAN1、WLAN2和5G)覆盖了整个交叉路口及相邻区域，行驶在该区域的车辆被所有基站的信号范围所覆盖，且任意车辆同一时刻只接入一个网络中享受数据通信服务；

(3)车辆终端装配有适用于车与车V2V(Vehicle-to- Vehicle)通信的车载端元OBU(On-Board Unit)和适用于车与基础设施V2I(Vehicle-to- Infrastructure)通信的移动通信接口，从而支持数据的实时传输与交互；

(4)车辆传输和交互业务流主要分为语音对话、实时流媒体、网络交互和后台下载4种流量类型。

Figure 1 System model图1 系统模型

4 异构车载网络选择方法MQSM

4.1 Q-learning简介

Q-learning是一种基于价值(Value-based)且与模型无关的强化学习算法，其利用智能体与环境的交互来迭代学习优化策略，从而实现特定的优化目标。Q-learning根据状态空间S={s1,s2,…,sm}和动作集合A={a1,a2,…,an}构建二维矩阵Q值表Q，用于评估期望的累计折扣回报值，并决策当前环境状态的执行动作。具体来讲，每次迭代过程中智能体首先观察当前时刻t的环境状态st，并根据贪婪策略ε-greedy选择动作at，获得即时回报值r(st,at)；接着，智能体基于下一时刻t+1的最大预期折扣值maxQ(st+1,at+1)更新当前状态和动作对应的Q值。即当前状态st指向下一状态st+1，且Q值的更新公式如式(1)所示：

Q(st+1,at+1)=Q(st,at)+

(1)

其中，α表示学习率，γ表示折扣因子。

重复上述过程直到指向最终时刻状态，此过程记为完成一次学习。不断重复学习过程，直到总预期折扣值收敛，则得到最优Q值矩阵，此时迭代结束，且每一个状态对应的最优动作组成了最优策略集合。

4.2 基于协作学习的即时回报值计算方法

一般基于单智能体的Q-learning算法的最优策略是最大化回报值，而对于基于多智能体的Q-learning算法而言，则是使得所有智能体的策略达到纳什均衡(Nash Equilibrium)[22]。本节采用基于多智能体Q学习的思想解决了单智能体状态空间过大导致算法无法正常收敛的问题[23]，并基于协作学习的思想提出一种即时回报值计算方法，提高了动作选择评价的准确性。

(1)智能体。

本文将异构车载网络系统视作一个整体，首先根据车辆行驶方向和速度信息，将相同方向和近似速度的车辆划分为一个群体，即将所有的车辆终端划分为N个群体，记作G= (G1,G2,…,GN)，且群体Gi(1 ≤i≤N)对应智能体Agenti，群体Gi的状态空间为Si(Si⊆S)。单个群体内的车辆具有相似的运动状态，因此这些车辆维护了一个相对稳定的网络拓扑。基于车辆之间的信息交互，群体Gi使用智能体Agenti进行迭代学习，并得到该群体的最优动作策略集合。每次学习时所有智能体同时执行操作，且每个群体均会学习其他群体此刻动作的即时回报值。利用群体间的协作学习，从而得到异构车载网络系统的最优动作策略集合。

(2)状态。

异构车载网络系统中备选网络的性能受到多种网络属性的影响，例如带宽B、时延D、延迟抖动J、丢失率L、误码率E和成本C。系统中被智能体观察的状态数量正比于车辆节点的数量。

(3)动作。

异构车载网络系统中，算法的动作选择就是网络选择。备选网络集合记为Net= {net1,net2,…,netM}，其中M表示网络数量。

(4)回报值。

群体Gi的智能体Agenti在状态st下选择动作at，然后计算网络属性的综合效用值，接着将网络的QoS评分记为未考虑其他群体影响的初始即时回报值ri(st,at)，且ri(st,at)的计算方法如式(2)所示：

(2)

其中，u(x)表示网络属性x的综合效用值，其计算方法如式(3)所示。

u(x)=βf(x)wx+(1-β)uobj

(3)

其中，f(x)表示网络属性x的效用函数，β表示效用值权重因子，wx表示不同决策属性效用函数的综合权重，uobj表示属性的客观效用值，且采用最优理想解排序法TOPSIS[14]计算uobj。

为了得到更为准确的网络属性综合效用值，wx将主客观效用值加权求和，且满足式(4)和式(5)：

(4)

wx=μwsub+(1-μ)wobj

(5)

其中，μ(0<μ<1)表示主客观权重因子，wsub和wobj分别表示主观和客观权重。本文采用模糊层次分析法FAHP[13]计算主观权重wsub，采用熵Entropy[10]计算客观权重wobj。

除了体现QoS的网络属性之外，车载终端接收网络信号的强度和备选网络的网络容量变化也会影响网络的性能，从而影响动作选择后的即时回报值和网络资源的利用率。这里分别引入基于网络接收信号强度RSS(Recieved Signal Strength)的效用函数u(rss)和基于网络容量NC(Network Capacity)的效用函数u(nc)，其计算方法分别如式(6)和式(7)所示：

(6)

(7)

(8)

其中，λ(0<λ<1)表示折扣因子,1≤i,j≤N且i≠j。

计算综合即时回报值的具体过程如算法1所示。

算法1群体Gi综合即时回报值算法

输入：选择动作at，网络状态st，车辆信息，备选网络容量capacity，选择网络的属性参数列表list，网络属性的参数修正值K，网络接收信号强度门限值Trss，最大网络容量maxCapacity。

初始化网络属性参数矩阵;

计算车辆终端对at对应的网络接收信号强度rss;

ifrss

elseifcapacity>maxCapacity

else{

根据式(6)和式(7)对网络属性进行参数预处理;

对于网络属性B：list(x)=list(x)·(ω·u(rss)+ (1-ω)·u(nc));

对于网络属性D,J,L,E：list(x)=list(x)+ω(1-u(rss))·K+ (1-ω)·(1-u(nc))·K;

标准化和归一化参数矩阵;

使用FAHP计算主观权重wsub，使用Entropy计算客观权重wobj，根据式(5)计算综合权重wx;

使用TOPSIS计算客观效用值uobj，根据式(3)计算综合效用值u(x);

return}

4.3 基于多智能体Q-learning的网络选择

现有的Q-learning算法在进行Q值更新时通常采用单表自更新方式，容易出现过高估计的问题，即导致某一动作的评价值过高，使得在多次迭代后动作的评价值不再准确。针对该问题，本节基于协作学习的即时回报值计算方法，采用双表交替更新的方式进行迭代学习。下面以群体Gi为例描述算法的交替更新过程。

首先在创建Gi的Q值表时，分别创建QA和QB2个相同的Q值表，每一个Q值表是由状态子空间Si和动作集合A构成的二维矩阵，储存每一个动作的长期报酬。2个表同时参与更新，其中一个表负责动作的选择，另一个表负责Q值的更新。每当更新Q值表时，随机使用一个表对另一个表进行更新，且一次动作选择只会对一个Q值表进行更新。对应的2个更新函数公式分别如式(9)和式(10)所示：

(9)

(10)

动作的选择采用ε-greedy策略，公式如式(11)所示：

(11)

在学习开始时，系统希望能够探索所有的状态-动作，概率初始值应很大，保证系统能够学习到所有的可能情况，智能体随机选择一个网络接入动作，下一状态同样采取随机策略，其更新公式分别如式(9)和式(10)所示：

(12)

(13)

随着迭代的进行，系统希望能够进行更加高效的学习，所以概率应取一个很小的值，保证对最大Q值对应动作进行扩展学习，此时智能体选择动作报酬最大的动作，下一状态同样采取最优选取策略。由于每次学习时都会同时使用2个Q函数，因此，学习效率并不低于传统的单表更新方式。基于多智能体Q学习的网络选择算法如算法2所示。

算法2基于多智能体Q学习的网络选择算法

输入：状态空间S、动作集合A、学习率α、折扣率γ、探索率ε、学习迭代次数episode。

输出：新Q值表。

初始化Q值表;

fori=1:episodedo

初始化群体Gi的网络状态空间Si;

whileSiis not NULLdo

fori=1:Ndo

群体Gi的智能体Agenti观察当前状态st，根据式(11)选择动作；

Agenti根据算法1计算群体Gi的综合即时回报值；

Agenti寻找下一状态st+1；

ifAgenti采取随机动作

根据式(12)和式(13)随机更新QA或者QB;

elseifAgenti采取最优动作选择 {

if更新QA

根据式(9)更新QA;

elseif更新QB

根据式(10)更新QB;}

当前状态st指向下一状态st+1。

endfor

endwhile

endfor

根据多智能体纳什均衡的收敛性证明[22]，算法在多次迭代之后会达到收敛状态。在预设迭代次数完成之后，若收敛成功，则输出Gi的Q值表，其状态对应的最优动作策略集合即为Gi的最优网络切换策略集合；若收敛失败，说明学习迭代无法如期完成，算法收敛性较差。

5 实验与分析

5.1 实验环境与参数

通过模拟城市场景下的交叉路口，并采用矩阵运算初始化车辆节点。如图1所示，异构车载网络环境中车辆速度被设置为15～70 km/h，且包含了LTE、WLAN1、WLAN2和5G共4个无线通信基站。网络及网络属性参数值的设置综合考虑了文献[12,13,20,21]的网络参数设置，其中，网络的覆盖半径和容量信息如表1所示。网络属性参数初始值如表2所示，除带宽B和成本C以外，其他网络属性参数值均在一定范围内波动。网络属性参数权重分配如表3所示。此外，调整参数的初始值是由多次实验以及相关参考文献确定的经验值，例如根据Q学习本身的特性，学习率应该保持在较低值，以提高每次学习的精度，折扣率应该保持在较高值，以保证当前动作选择作为主要回报值参考对象，调整参数初始值的具体设置如表4所示。

5.2 实验结果与分析

在实验部分，本文所提出的基于多智能体Q学习的异构车载网络选择方法MQSM选取了同类型的MANSA[20]和QBNS[21]方法，以及基于多属性决策的MCAS[12]方法作为对比对象。通过多次实验分别比较了4种方法的系统总切换次数、系统平均总折扣值和网络容量利用率。

Table 1 Network radius and capacity表1 网络半径及容量

Table 4 Initial value of the adjusted parameters表4 调整参数初始值

首先，4种方法的系统总切换次数分别在不同车辆数量和车辆速度下进行了对比，结果如图2所示。考虑到网络资源的利用率，过少的切换次数会导致优先接入的5G网络资源利用较为集中，因此适当地增加切换次数有利于异构网络资源的充分利用。从图2a中可以看出，4种方法的系统总切换次数均随着车辆数量的增加呈现出增长趋势。其中，基于多属性决策的MCAS方法的总切换次数明显少于另外3种基于Q学习的方法，这是因为MCAS方法针对单台车辆进行决策，每台车辆都从优化自身的角度出发优先选择性能最佳的5G网络，只有当车辆数量超过一定阈值导致5G网络负载过大时才会选择切换到其他网络中。而基于Q学习的其他3种方法从提高整个系统资源利用率出发，在保证用户QoS的前提下合理利用所有类型的网络资源，因此会产生更多的切换次数。3种基于Q学习的方法中，MANSA和QBNS在车辆数量增长到70以后都出现了较为明显的波动情况，其中QBNS的波动尤为明显，而本文的MQSM方法波动较为平稳。产生此结果的原因是QBNS和MANSA均使用了单表更新方式，容易出现某些动作选择评价值过高估计的现象，导致大量用户长期接入同一网络，多次迭代后，此次学习得到的奖励值超出正常值，大量用户接入同一网络且不再进行切换选择，导致切换次数大幅度减少。而MQSM使用双表更新，避免了过高估计问题的大量出现，同时MQSM使用了多约束效用函数，将网络的QoS评分作为即时回报值，大大提高了决策的准确性。图2b是在车辆数量为80的情况下，4种方法的系统总切换次数在不同车辆速度下的变化情况，且均呈现出先增后减的现象。其中，MCAS方法的总切换次数最少，其他3种基于Q学习的方法相对较多，该结果的原因与图2a的分析一致。同时可以看出，MQSM相比MANSA更适应速度的变化，具有良好的稳定性。

Table 2 Initial value of network attribute parameters表2 网络属性参数初始值

Table 3 Weight distribution of network attribute parameters表3 网络属性参数权重分配

Figure 2 Total handovers of system图2 系统总切换次数

其次，比较了3种基于强化学习的方法在不同迭代次数下的系统平均总折扣值，结果如图3所示。3种方法平均总折扣值的增长速度均随着迭代次数的增加逐渐减小，其中MQSM和MANSA在迭代次数达到100后趋于收敛，比QBNS更快到达收敛状态。这是因为MQSM和MANSA使用了多智能体的协作模式，相对于单智能体模式的QBNS可以减少状态空间，从而加快收敛。未达到收敛状态时，MQSM的平均总折扣值比MANSA更低，这是因为其使用了双Q值表交替更新的方式，使得学习效率相对较低，导致迭代次数相对较多，但MQSM解决了MANSA单表更新导致的过高估计问题，使得总折扣值相对较小。

Figure 3 Average total discount value of system图3 系统平均总折扣值

Figure 4 Network resource utilization图4 网络资源利用率

最后，比较了4种方法在车辆数量为100时的网络资源利用率，结果如图4所示。5G网络展现出的优秀性能使得其成为车辆终端用户的主要选择倾向，QBNS和MANSA的5G网络占用容量接近甚至超过了5G网络所能容纳用户数量的最高值，明显是总折扣值估计过高，导致大量用户接入了理论上性能最优，但实际上已经负载严重的5G网络，使得其他网络资源无法得到充分利用；MQSM的5G网络占用容量保持在一个良好的水平，并且其他网络得到了更好的利用，整体上网络利用率最高。该结果体现了MQSM的模型设计更为合理，可以在保证5G网络容量合理利用的同时，提高其他网络的接入数量，使系统在长期的运动状态下保持较高的网络资源利用率。

6 结束语

为了获得异构车载网络环境下系统长期有效的最优网络切换决策集合，考虑到未来融合5G通信的异构车载网络环境，提出一种基于多智能体Q学习的网络选择方法MQSM，用于在保证车辆终端用户的良好QoS体验的同时，提高异构车载网络的资源利用率。该方法构建了一个以Q-learning为基础的多智能体协作学习模型，通过设计的多约束效用函数计算网络的QoS评分作为回报值奖励，从而更加准确地评价网络性能。此外，利用双Q值表交替更新方式优化学习过程，一定程度上解决了过高估计问题。实验结果表明，该方法在不同的交通条件下均具备良好的适应性和稳定性，有效提高了网络资源利用率。

随着城市智能交通的发展，异构车载网络中车载终端用户的需求将更加多样化，用于评估网络性能的属性种类和数量将变得更加复杂，对应的网络状态空间也将更加庞大。当前的多智能体Q学习模型在复杂化后的异构车载网络中难以发挥作用，因此在下阶段的工作中，将考虑结合深度学习来应对更加复杂的环境。