密集异构网络中基于强化学习的流量卸载算法

王 倩 聂秀山 尹义龙

1(山东财经大学计算机科学与技术学院 济南 250014)2 (山东大学齐鲁软件学院 济南 250101) (qianwang@sdu.edu.cn)

随着移动互联网的快速发展以及无线移动业务和模式的不断创新，互联网用户规模和网络流量呈现爆炸式的增长.据思科2017年度VNI全球移动数据流量预测，全球移动数据业务量未来每年将以近一倍的速度增长[1].未来10年，无线数据业务将增长1 000倍[2].“万物互联”的无线大数据时代即将到来，未来的移动通信系统需要大幅提升网络容量和频谱效率.为了解决有限无线带宽资源与海量高速业务需求之间的矛盾，出现了许多新的技术，例如D2D(device to device communication)、大规模MIMO(massive multiple-input multiple-output)、密集异构网络等.

在众多的技术方案中，流量卸载(traffic offlo-ading)技术[3]可充分利用现有网络，通过跨网协作实现对蜂窝网络容量的极大提升，成为未来无线通信技术研究热点之一[4-7].其基本原理是在异构网络中，将负载比较重的网络流量卸载到负载较轻的网络中，实现用户业务吞吐量和网络容量的提升，保证对用户业务的服务质量(quality of service, QoS).

1 相关工作

异构网络中，LTE(long term evolution)蜂窝网络与WiFi(wireless fidelity)网络间的流量卸载最为常见[4-5]，其实现形式是将LTE蜂窝网络中的用户流量卸载到WiFi网络中，以缓解LTE蜂窝网络带宽紧张的问题.WiFi网络和LTE蜂窝网络间可实现流量卸载是由于：1)WiFi网络使用的频段是免许可频段，可以与LTE蜂窝网络重叠，2张网络互相没有干扰；2)WiFi网络带宽充足，可提供高吞吐量、高可靠性的无线通信[3]；3)WiFi网络技术成熟，接入点价格低廉，并且应用广泛，在公众场合或室内环境普及率高.由于可大幅度提升网络系统容量，缓解网络拥塞，且实现成本低廉，LTE与WiFi网络间流量卸载引起业界广泛的关注[7-13].

LTE和WiFi网络间流量卸载，最大的挑战是如何设计触发LTE向WiFi流量卸载的最佳判决规则，以保证将LTE蜂窝网络的部分流量卸载到空闲的WiFi网络中后，大幅提高系统的吞吐量和能效性能.过量的流量卸载会导致WiFi网络碰撞冲突，造成性能的严重恶化[6].主要原因是：1)WiFi网络MAC层接入控制算法采用DCF(distributed coordination function)协议.DCF是基于CSMA/CA(carrier sense multiple access with collision avoidance)的接入控制机制，即在传输数据包之前，发送端持续监听信道是否空闲.首先发送一个RTS(request to send)信号，当接收端收到RTS信号后，监听信道状态.如果信道空闲，则反馈CTS(clear to send)信号给发送端.发送端接收到CTS信号后，启动数据传输.然而LTE蜂窝网络采用中心控制式MAC接入协议，且具有连续性的传输机制.所以，如果过量地将LTE的数据流量向WiFi网络卸载，会引起WiFi中原有用户处于持续等待信道空闲状态，造成WiFi用户吞吐量的急剧下降.2)LTE与WiFi可能属于不同的运营商，2张网络无统一的中央控制器，WiFi网络无法获知LTE业务信息和信道状态，同时LTE无法确定WiFi的网络容量和负载状况，一直处于“盲”卸载状态，无法保证卸载的流量在WiFi系统中的服务质量.即使LTE与WiFi之间具备中央控制器，但由于WiFi的用户传输速率、传输时延、系统吞吐量都会受到卸载流量的影响，无法保证卸载后整个系统性能最优.3)WiFi网络的通信安全性、延时及稳定性都难以保证，因此设计卸载模式时，不能仅仅考虑负载分担和网络容量，还应选择对时延、安全性和稳定性要求不高的用户业务进行卸载.

基于以上分析，当前国内外关于流量卸载的研究大多围绕着如何设计LTE向WiFi流量卸载的最佳控制规则，推导流量卸载量上限值，达到跨网协作的负载均衡点，最大化LTE和WiFi系统的吞吐量，保证密集异构网络的整体性能[7-13].文献[7] 提出了一种竞合式的流量卸载算法，WiFi网络可在忙时将部分流量卸载到LTE网络的免许可频段，占用LTE的非授权频谱资源，即LTE和WiFi网络的跨网协作是一种竞争下的合作，并从理论和仿真中证明此算法大大提高了系统吞吐量，达到了竞争与合作的最佳折中.文献[8]针对异构网络中不同业务需求差异，提出了兼顾激励和公平性的WiFi流量卸载模式，可以提供基于业务感知的流量卸载.文献[9]提出了一种基于博弈论的机会流量卸载算法，理论分析及仿真结果表明，流量卸载后的系统性能远好于蜂窝网络或WiFi网络的性能.文献[10]针对流媒体应用场景下，根据媒体特征，提出一种分片式流量卸载，实现对流媒体业务的QoE保证.文献[11]是一种分布式异构网络融合结构，将可延时的流量卸载到WiFi系统，这样既可以保证LTE中实时业务的带宽需求，也可以对时延不敏感的业务提供QoS保障，提高了系统整体频谱效率和功率有效性.文献[12]针对时延不敏感的业务，将其卸载到WiFi网络中，在保证蜂窝用户的干扰低于阈值的前提下最大化LTE和WiFi用户的性能.文献[13]以提高LTE和WiFi整体系统功率有效性为目标，提出了一种最优的负载均衡策略.其实验结果表明，流量卸载后的系统频谱效率大大优于传统LTE或WiFi网络性能.

现有的研究成果大多数都是根据蜂窝流量需求来触发流量卸载，这些策略中的流量卸载判决规则都是基于当前时刻的瞬时流量或者系统的当前吞吐量，并没有考虑流量卸载历史对系统性能造成的影响.然而当前WiFi系统容量和网络吞吐量与先前用户卸载量是密切相关的.当前用户结合先前用户流量卸载情况，准确地预测可卸载的流量，并推导当前网络的可达卸载量(最大卸载量)，可有效避免流量过度卸载造成的WiFi系统时延和吞吐量的急剧恶化，并且会带来额外的频谱增益，最大限度地提高系统性能.

机器学习是人工智能的重要核心，主要思想是通过计算机模拟人类的学习行为.学习是学习者适应环境的过程，学习者根据环境变化调节自己的行为，更好地适应环境，达到某种利益的最大化.学习的过程就是根据历史经验动态调节自身行为的过程.近年来，越来越多的通信业界研究者将机器学习方法用于解决无线通信系统的关键问题[14-18].大多研究集中在资源优化[14-15]、干扰检测[16]、异构网络融合[17]、信道均衡[18]等方面，但将机器学习的思想引入到流量卸载策略鲜有研究.本文将采用强化学习(reinforcement learning， RL)[19]模型来解决流量卸载问题.

强化学习[19]是机器学习中的一个分支，是学习者通过与环境互动进行学习的算法.关键要素有：环境(environment)、回报值(reward)、动作(action)和状态(state).强化学习的目标是学习在每个状态采取何种动作来最大化一个特定的指标.学习者通过反复与控制环境进行交互，利用回报值来评价其性能，从而达到一个最优决策.强化学习无输入输出数据，只有某种规则，相当于试错学习，其目的是在大量可能路径中寻找最佳决策或者路径，因其自适应性被广泛应用于机器人和自动化控制领域[20-22].

本文将强化学习的思想引入流量卸载算法中，提出了一种异构网络基于强化学习的流量卸载方法.该流量卸载算法是把流量卸载问题映射为一个强化学习问题，通过以往用户流量卸载带来的性能增益，基于每一状态的WiFi网络吞吐量计算回报值，寻找最佳的WiFi网络接入点(access point, AP)，并推导出最优的流量卸载判决规则，达到异构网络整体吞吐量最大化.

2 系统模型

本文研究的网络场景是LTE蜂窝网络和IEEE 802.11的WiFi网络构成的密集异构网络.移动用户的业务流量可以通过宏基站(marco base station, MBS)或者WiFi AP接入到相应网络中.如图1所示，本文采用一个蜂窝中只包含一个宏基站(MBS)和N个WiFi AP的应用场景，其中WiFi AP是任意分布在蜂窝里.每个WiFi AP用APi(i∈{1,2,…,N})表示.有K个移动用户，dj是指用户j(j∈{1,2,…,K})所在的位置，即与MBS的距离.

Fig. 1 System model图1 系统示意图

网络吞吐量是指在某个时刻网络提供给用户的最大带宽，即在没有帧丢失的情况下网络能够提供的最大速率.由此可见，网络吞吐量可以帮助寻找网络路径中的瓶颈，间接体现当前网络负载情况.LTE网络向WiFi网络进行流量卸载，可大幅提高网络容量.但是过量的流量卸载会导致WiFi网络碰撞冲突，造成性能的严重恶化.虽然LTE网络和WiFi网络无集中控制器，LTE网络无法实时获知WiFi网络的负载情况，但我们可以通过WiFi网络吞吐量变化，直观、准确地将WiFi网络拥塞情况反馈给LTE蜂窝网络，对流量卸载进行自适应控制，避免卸载的蜂窝流量超过WiFi网络中可卸载无线网络资源的总和.因此，首先，我们推导WiFi网络和LTE网络的吞吐量的闭合表达式.

2.1 WiFi吞吐量

根据文献[23]，WiFi网络中，吞吐量可用离散Markov模型进行分析.令用户数为K，Pslot表示在单位时隙Tslot中至少有一个用户发送数据的概率，Pok为单位时隙Tslot中用户成功发送数据的概率，则Pslot和Pok可分别表示如下：

Pslot=1-(1-θ)K,

(1)

Pok=Kθ(1-θ)K-1Pslot,

(2)

其中,θ是每个用户的传输概率.根据文献[23]可知，WiFi网络的平均吞吐量可表示为

(3)

其中，Tτ是空时隙的间隔时间，Tb是用户数据成功传输占用信道的平均时间，Tc是用户间碰撞导致信道忙的平均时间，E[Lave]是数据包长度的均值.

求解WiFi系统的平均吞吐量ThWiFi(K)，先需要确定其中Tb和Tc的值.对于WiFi网络来说，MAC采用DCF接入控制机制，Tb和Tc可分别表示为[23]

Tb=RTSR+SIFS+Tτ+CTSR+SIFS+Tτ+
E[Lave]R+SIFS+Tτ+ACKR+DIFS+Tτ,

(4)

Tc=RTSR+DIFS+Tτ,

(5)

其中，R是WiFi网络的信道比特速率.WiFi网络的R不是固定值；但在同一WiFi网络中，R的数值与信道状态、当前网络吞吐量、网络负载无关，因此我们可以将其视为常数.ACK，DIFS，SIFS，RTS和CTS分别是ACK，DIFS，SIFS，RTS和CTS控制信号持续时间，均为WiFi网络参数.

2.2 LTE吞吐量

在LTE蜂窝网络中，假设用户k，以及对应的信道增益为Gk，噪声功率为n2，P为发送功率.则对于LTE的一个蜂窝小区来说，SINR可表示为[24]

(6)

在LTE蜂窝网络的平均吞吐量可表示为[24]

ThLTE=B×E{lb(1+SINR)},

(7)

其中，B是LTE蜂窝网络的信道带宽，E表示对信道衰落及干扰的数学期望值.

2.3 问题描述

在密集异构网络中，当LTE蜂窝网络流量过大而导致较大时延时，通过将LTE中的部分数据包卸载到WiFi网络，可以缓解网络拥塞，保证用户业务的QoS.但是过量的卸载会导致WiFi网络性能恶化，因此流量卸载的目标是在保证WiFi网络性能的同时最大化LTE系统吞吐量.我们用用户的平均吞吐量作为其性能度量，考虑最大化LTE用户平均吞吐量.对于WiFi网络，我们需要保证每个用户的最小吞吐量.假设LTE基站会向WiFiAPi卸载K个用户， LTE网络中用户平均吞吐量的最优化问题可表示为

(8)

(8a)

Nk≤Nmax,∀k,

(8b)

3 基于强化学习的流量卸载算法

3.1 强化学习之Q学习

本文将采用强化学习中应用最广泛的算法之一——Q学习[25-26].Q学习把学习看作试探评价过程.Q学习模型由动作集合α∈A={1,2,…,N}和状态集合s∈S构成.学习者选择一个动作α∈A用于环境，环境接受该动作后状态发生变化，同时产生一个回报值Re(s)反馈给学习者，学习者根据Re(s)值和环境当前状态s∈S再选择下一个动作α′∈A，选择的动作不仅影响瞬时回报值Re(s)，而且影响环境下一时刻的状态及状态s的折扣累积回报值ReC(s).Q学习的目标是在发现最优策略以使累积回报值ReC(s)最大.状态s的累积回报值ReC(s)可表示如下[25]：

(9)

其中0<ε<1是回报因子；P(s′|s,α)是当学习者执行动作α′时，从状态s到状态s′的状态转移概率.

根据Bellman理论[27],当累积回报值ReC(s)最大时，流量卸载策略最佳.即:

(10)

最佳判决策略为

(11)

由于Re(s,α)和P(s′|s,α)不可知，我们可以利用Q学习去学习出这些值.Q函数可表示为

(12)

3.2 问题映射

本文将Q学习的思想引入流量卸载算法中，提出了异构网络中一种基于Q学习的流量卸载方法.要将Q学习的学习者agent、状态s、动作α∈A和Reward信号等因素映射到实际的流量卸载模型中，具体的映射原理如下所述：

1) 学习者agent

流量卸载的学习者agent是K个移动用户.

2) 状态集合S

状态集合定义如下：

st={di,i∈{1,2,…,K}},

其中di是每个用户离开基站的距离，也代表着用户位置.假设小区内有K个用户，所以st的状态空间是离散且有限的.

3) 动作集合αdi

当αdi=0时，意味着在位置di的用户将连接到宏基站;APn是指位置n处的WiFin，当αdi=n(n∈{1,2,…,N})时，意味着位置di的用户将通过WiFiAPn进行网络接入.

4) 回报函数Re(s)

(13)

从式(13)可以看出，对于连接LTE基站的移动用户，网络吞吐量只与SINR有关.

(14)

其中，0<α<1是权值因子.则我们引入激励参数W(di):

(15)

(16)

3.3 基于Q学习的最优网络卸载算法

根据3.2节的问题映射，我们可以看出，最优的网络卸载算法是在保证WiFi最小吞吐量的前提下，完成最大程度的LTE网络向WiFi网络的流量卸载，以获得最大的网络吞吐量，也就是说，我们的优化目标是最大化WiFi和LTE回报函数值的差，可以得出效用函数为

(17)

最优网络卸载判决可转化为

(18)

s.t.

(18a)

Nk≤Nmax,∀k，

(18b)

β≤βth，

(18c)

β≥1.

(18d)

将式(3)，(14)和(16)，带入(18)，优化问题表示为

(19)

s.t.

(19a)

Nk≤Nmax,∀k,

(19b)

β≤βth,

(19c)

β≥1.

(19d)

(20)

(21)

对式(20)进行β的二次求导可得，

(22)

(23)

(24)

对于λ来说，

(25)

将式(21)带入式(25),

(26)

由式(24)得，

(27)

因此，最佳的负载调节因子βopt为

(28)

3.4 算法实现

综合考虑网络的负载情况、业务属性、终端的移动性以及用户在网络中的位置，基于Q学习方法，根据3.2节映射规则，提出了超密集异构无线网络中最佳网络卸载策略，具体实现步骤如下：

1) 移动用户观察当前状态s;

2) 从动作集合中选择动作α∈A;

3) 移动用户观察下一个状态s′;

4) 根据环境，接收瞬时回报值Ret(s,α);

5) 不断执行Q学习方法，直到获得最大的累积Qt(s,α).即

Qt(s,α)=Qt-1(s,α)+δ[Ret(s,α)+
εmaxQt-1(s′,α′)-Qt-1(s,α)],

(29)

其中，δ表示Q学习速率，0<δ<1.具体如算法1：

算法1. 基于Q学习的流量卸载算法.

输入：初始化状态s∈S、动作α∈A;

输出：Q最大值.

① Forα∈A,s∈S

②Q(s,α)=0;

③ 初始化回报值Re(s,α);

④ End For

⑤ For 对于每一个用户，取任意一个随机值rand(·)

⑥ Ifrand(·)<ε

⑦ 选择α;

⑧ 计算Re(s,α);

⑨ 在下一个状态s′，根据式(29)更新Q表;

⑩ End If

4 实验与结果

本节中用计算机仿真的方法评价本文提出的基于Q学习的流量卸载方案，并与传统的基于无线信号强度(RSS)的流量卸载方案进行对比.仿真参数如表1所示：

Table 1 Simulation Parameters表1 仿真参数

1) 仿真验证了一个蜂窝内的WiFi AP数量对本文基于Q学习的流量卸载算法复杂度的影响.结果如图2所示，随着WiFi AP数量的增加，Q学习算法收敛迭代次数随之增加，算法复杂度也上升.图2可以看出，当WiFi AP数量为30时，收敛迭代次数是28次；而WiFi AP数量增加为60时，迭代次数增加到51次.这是因为WiFi AP数增加，则Q学习的Q表空间增加.因此，移动用户在任意位置di，通过Q学习达到流量卸载最优需要更多少次数的迭代才能达到收敛.可见，WiFi AP的密集部署会引起基于Q学习的流量卸载，卸载的延迟增大，尤其不适合时延敏感的实时性业务.

Fig. 2 Number of iterations of Q-learning under different number of WiFi APs图2 Q学习收敛迭代次数与WiFi AP数量关系图

2) 我们仿真了在不同的负载调节因子β下网络平均吞吐量的变化趋势，验证了β对网络平均吞吐量的影响.网络平均吞吐量代表着流量卸载后，异构网络总体性能的提升.负载调节因子β越小，移动用户流量卸载到邻近WiFi的可能性越大.为了便于比较，首先我们将吞吐量转化为归一化吞吐量率γ.假设AP1和AP2的吞吐量最大值为Thmax1和Thmax2，在某状态st时，AP1和AP2的吞吐量最大值为Th1和Th2，则总的归一化吞吐量率可以表示为

(30)

Fig. 3 Normalized throughput radio γ under different load weight factor β图3 归一化吞吐量率γ与负载调节因子β的关系

Fig. 4 Normalized throughput radio γ for Q-learning offloading and RSS offloading图4 Q学习与RSS的流量卸载的归一化吞吐量率γ对比

3) 将本文提出的基于Q学习的流量卸载算法与传统的基于RSS的流量卸载算法的性能进行了对比，结果如图4所示.在仿真中，我们选取了WiFi AP数量为40，β=2.从图4可以看出，我们提出的基于Q学习的流量卸载算法的性能优于传统的基于RSS的流量卸载算法.如图4所示，当负载为30%时，基于Q学习的流量卸载算法下，归一化吞吐量率γ=0.8(即80%)；而基于RSS的流量卸载算法，γ只有0.3(即30%)左右，基于Q学习的流量卸载算法的吞吐量是传统的基于RSS的流量卸载算法2倍以上.而且，随着负载程度越来越高，WiFi冲突率会越来越严重.对于传统的基于RSS的流量卸载算法，当负载高于60%时，用户就会停止向WiFi卸载；而基于Q学习的流量卸载算法，可根据WiFi的实时网络负载动态调节，直到负载接近100%时才会停止向WiFi的流量卸载.基于RSS的流量卸载算法，只考虑选取最大的RSS瞬时值进行流量卸载；基于Q学习的方案，不仅考虑了实时SINR和负载情况，还通过以往用户流量卸载的经验和性能增益，分析网络负载变化趋势判断其是否为进行流量卸载，并推导出最佳的流量卸载判决规则，达到网络吞吐量最大化.

4) 我们还验证了最佳负载调节因子βopt与WiFi负载的关系.通过式(27)可以看出，βopt与负载率L成反比，WiFi网络负载越重，βopt的值越小.这是因为L越小，代表WiFi的空闲网络资源越多，移动用户更容易将流量卸载至WiFi，缓解蜂窝网络中的容量不足、吞吐量低等问题.如图5所示，当负载L=10%时，βopt=4.5；而L=80%时，βopt=0.6.当WiFi的负载很重时，需限制蜂窝网络流量向WiFi卸载，保证WiFi网最小吞吐量和QoS要求.

Fig. 5 Optimal load factor βopt under different load percentage L图5 负载L与最佳负载调节因子βopt的关系图

5) 我们仿真了当负载调节因子取最优值βopt时，基于Q学习的流量卸载算法与传统的基于RSS的流量卸载算法的性能比较，结果如图6所示.仿真中，选取了AP数量为40.从图6可以看出，基于Q学习的流量卸载算法，在负载从0～90%都保持着最大的网络吞吐量，保证用户的服务质量；而传统的基于RSS的流量卸载算法由于只考虑自身负载，忽略了其他的用户关键参数，比如切换时延等.因此，从仿真结果可知，基于Q学习的流量卸载算法，可最大限度地提高网络吞吐量，当负载调节因子取最优值βopt时，吞吐量取最大值.

Fig. 6 Normalized throughput radio γ for Q-learning offloading and RSS offloading (β=βopt)图6 Q学习的流量卸载与RSS的流量卸载的归一化吞吐量率γ对比图(β=βopt)

Fig. 7 Per-user average throughput of LTE versus minimum per-user average throughput of WiFi图7 WiFi用户最小平均吞吐量条件下 LTE用户平均吞吐量

6) 我们分别仿真了基于Q学习的流量卸载算法和传统的基于RSS的流量卸载算法在保证获得WiFi用户最小平均吞吐量条件下，用户数量对LTE的移动用户可获得平均吞吐量的影响.从图7可以看出，WiFi用户获得最小平均吞吐量和LTE的用户可获得平均吞吐量是成反比的.WiFi用户获得最小平均吞吐量越大，占用的WiFi频谱资源就越多，能提供给LTE网络中的用户进行流量卸载的机会就越小，因此LTE的用户可获得平均吞吐量就越小.同时，移动用户数量越多，用户业务流量就越大，LTE的用户与WiFi用户争用WiFi网络资源，因此LTE可获得平均吞吐量也越小.从图7还可以看出，我们提出的基于Q学习的流量卸载方案，由于可以利用历史经验，学习并预测WiFi资源负载情况，有效避免由于无控制卸载造成的WiFi网络的接入碰撞，因此基于Q学习的流量卸载方案下的LTE用户平均吞吐量比传统RSS方式的高.如图7所示，当用户数为60时，Q学习的流量卸载方案的LTE用户可获得平均吞吐量比传统RSS方案高近2倍.可见，基于Q学习的流量卸载算法更能有效地实现自适应流量卸载控制规则，达到跨网协作的负载均衡点，在保证WiFi用户服务质量的条件下，最大限度地提高吞吐量，保证异构网络的整体性能.

5 结 论

近年来互联网用户规模和网络流量呈现爆炸式的增长，不断逼近蜂窝移动通信网络的容量极限.流量卸载技术可充分利用现有网络，将蜂窝网络的部分流量卸载到空闲网络中，进行跨网协作实现对蜂窝网络容量的极大提升，可有效解决为有限的无线带宽资源与海量高速业务需求的矛盾.

本文将强化学习的思想引入流量卸载算法中，提出了一种密集异构网络中基于强化学习的流量卸载算法.此算法把流量卸载问题映射为一个强化学习问题.将WiFi网络吞吐量作为回报函数，吞吐量的瞬时变化可直观、准确地反映出WiFi网络拥塞情况，准确地预测需卸载的流量，并推导当前网络的最大卸载量，作为自适应的流量卸载策略的最佳判决.寻找最佳的βopt，最大限度提升系统吞吐量.仿真结果表明，基于Q学习的流量卸载算法更能有效地实现自适应流量卸载控制规则，达到跨网协作的负载均衡点，在保证WiFi用户服务质量的条件下，最大限度地提高LTE系统吞吐量，保证密集异构网络的整体性能.

WangQian, born in 1976. PhD, associate professor. Member of CCF. Her main research interests include machine learning, wireless communication, resource allocation.

NieXiushan, born in 1981. PhD, professor. Member of CCF. His main research interests include database theory, data mining, Web mining, machine learning.

YinYilong, born in 1972. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include machine learning, data mining, computational medicine.