考虑负载均衡和用户体验的垂直切换算法

马 彬 钟世林* 谢显中 陈 鑫

①(重庆邮电大学计算机科学与技术学院 重庆 400065)

②(重庆邮电大学重庆市计算机网络与通信技术重点实验室 重庆 400065)

1 引言

在城市核心区域，随着5G基站的大量部署以及公共交通网络的迅速发展，逐渐形成了超密集异构无线网络[1,2]。然而，随着城市的发展和车辆的普及，城市的交通拥堵情况却日益加剧，每天的交通高峰期会有大量的车辆，特别是公交车，拥堵在城市核心区域路段。车辆的爆发式增长除了引起道路的拥堵，还会因大量车载终端(vehicle terminal)在短时间内的聚集性移动造成网络拥塞和带宽资源紧缺，使得已接入网络用户的服务质量出现严重下降。因此，在车辆异构无线网络中如何通过移动性管理缓解网络拥塞，实现负载均衡，进而保证用户体验成为该领域研究的热点问题。

作为异构网络中移动性管理的关键技术，垂直切换是多网融合的基础。目前国内外已有较多文献致力于垂直切换的研究。根据采取研究方法的不同，垂直切换算法大致可以分为以下4类：(1)基于单阈值判决的垂直切换算法[3,4]，当接收信号强度(Receive Singal Strength, RSS)或其他网络参数达到设定阈值后直接触发切换；(2)基于多属性决策的垂直切算法[5,6]，首先确定网络侧和用户侧的多个参数指标(如带宽、抖动、负载、用户偏好等)的权重，然后构建目标效用函数并计算效用值，最后选择最优效用值的网络进行接入；(3)基于人工智能的垂直切换算法，利用模糊逻辑[7,8]、神经网络[9,10]、强化学习[11,12]或智能仿生算法[13,14]等模型，将判决参数作为模型输入进行智能的切换判决；(4)基于匹配博弈网络的垂直切换算法[15,16]，把网络中的基站或者用户抽象为博弈过程的参与者，使用判决参数建立博弈双方的效用函数，并通过博弈过程中的纳什均衡求解，优化网络性能。

当前已有不少的文献致力于研究异构无线网络中的网络拥塞、负载不均、用户体验等问题，并且都取得了一定的成效。文献[17]提出了一种基于效用函数的网络选择方案，通过综合考虑用户的服务质量 (Quality of Service, QoS)需求、偏好、成本以及网络负载，改善了用户体验，提高了网络吞吐量。文献[18]通过分析用户行为给用户设定不同的优先级，然后给不同优先级的用户制定不同的迁移策略，缓解了网络拥塞。文献[19]引入一种基于端对端 (Device to Device, D2D)通信辅助的流量迁移方案，减轻了蜂窝网络中迁移用户给WiFi访问点带来的严重负担。文献[20]则巧妙地将网络建模为一个有向图，并以超载的网络及其n层邻居构建集群，通过在集群中实现局部负载均衡，提高了网络总体性能。另外，文献[21–24]提出通过机器学习和大数据分析的方式，来对自动的流量迁移方案进行学习，达到了缓解网络拥塞，均衡负载的目的。

上述算法大多通过切换迁移的方式在一定程度上缓解了网络拥塞，但在因大量终端短时间聚集性移动引起网络拥塞的场景中，仅通过迁移的方式，而不考虑用户的选网需求会随着网络环境的变化做出相应的调整，并对网络容量进行提升，则极易造成邻近基站的网络资源紧缺和用户体验得不到实质性改善。为解决这一问题，如何提升网络容量、改进切换策略、优化终端的选网过程成为本文研究关注的核心问题。因此，本文提出一种考虑负载均衡和用户体验(Load Balance and User Experience,LBUE)的垂直切换算法。该算法将城市核心区域的网络通信建模为车辆自组织异构无线网络模型，与直接与外基站连接相比，本模型采用了在公交车辆上部署无线信号收发器(Radio Transceiver, RT)的策略，提高了网络总容量。若将部署了RT的车辆作为簇头，以分簇结构组建自组织网络(ad hoc)，能够避免因大量终端与基站直接相连引起服务质量的严重下降，缓解了网络拥塞。此外，当终端触发切换后，通过自适应切换判决算法能够为用户筛选出当前网络环境下满意度最高的网络，提升了用户体验。本文的主要贡献可以概括如下：

(1)引入网络拥塞感知模型，提出一个融合自组织网络的超密集异构无线网络架构。

(2)定义业务适应度和负收益因子两个自适应参数，提出一种基于秩和比的自适应切换判决算法。

2 算法设计思路和流程

在城市核心区域，由于车辆的聚集性移动，网络的负载状况呈现出时变特性。因此在设计选网算法时，需要对当前网络状况进行实时感知，并能根据感知结果触发不同的处理机制。若网络环境正常，可直接为切换用户筛选出能保证其偏好需求的目标网络；若网络环境拥塞，则需要缓解拥塞的措施来保证用户的正常通信。基于以上思路，如图1所示，本文算法可设计为以下3个阶段：(1)网络环境感知：获取网络中各个基站的平均负载程度和负载变化率数据评判出网络的拥塞情况。(2)构建自组织网络：当网络环境感知判决网络状态为拥塞时，启动分簇算法，根据车辆的运动信息以分层的簇结构组建车辆自组织网络，让自组织网络也成为用户的备选网络。(3)自适应切换判决算法：终端触发切换后，根据网络的拥塞情况和用户的业务请求，调整输入到决策算法中的决策参数，为用户筛选出当前环境下满意度最高的目标网络。

图1 算法流程示意图

3 网络环境感知

假设各个基站都连接到了网络控制中心，通过中心的负载管理器能对各个基站资源使用情况进行实时监测。网络环境感知指的是通过分析监测到的网络资源变化数据对网络当前的拥塞状况和未来的拥塞趋势作出判决的过程。传统感知策略[25]通常采用单个负载阈值与基站的负载程度进行比较来判断网络是否陷入拥塞，不能对网络的拥塞趋势进行预测。因此，本文提出一种网络拥塞感知模型，首先使用监测数据计算出网络平均负载程度和负载变化率均值，然后根据这两项指标综合评估网络环境是否有拥塞的趋势。

3.1 相关参数定义

(1) 网络平均负载程度。本文通过网络已使用资源块数量占总资源块数量的比值来定义网络平均负载程度。假设某区域内共有N个基站，其中第j个基站能分配的总资源块数为Rj，接入到基站j的终端数量为U，其中第i个终端分配到的资源块数量为rij， 则网络平均负载程度ξ可表示为

3.2 网络拥塞感知模型

设计网络感知模型的目的是简单、直接、有效地获得网络拥塞状况，以便于区分下一步是否需要构建自组织网络。故本文采用网络平均负载程度ξ和平均负载变化率∆ξ¯来综合评判网络的拥塞状况。ξ反映的是网络资源的使用情况，ξ越大表示网络资源消耗越多，拥塞情况越严重； ∆ξ¯反映的则是网络资源被消耗的快慢程度， ∆ξ¯越大表示网络资源消耗越快，网络陷入拥塞的风险越大。式(4)是网络拥塞判断函数

在该函数中，通过引入负载上下限阈值区间[ξmin,ξmax]和 负载变化率阈值∆ξ0，对网络负载程度和负载变化快慢进行度量。在负载达到负载下限阈值时，通过考察平均负载变化率决策网络是否会在较短时间陷入网络拥塞。如果网络持续缓慢增大，无法通过负载变化率感知出拥塞结果，则通过负载上限阈值作为拥塞感知的兜底策略。

图2(a)和图2(b)是负载管理器在2 min内监测到的平均负载程度实时变化曲线，其中1个采样周期∆t的间隔为1 s，从采集的实时数据可计算出在1个∆t内ξt −ξt−1的 取值区间为[–0.05,0.05]，也即∆ξ的取值范围为−0.05≤∆ξ ≤0.05 。在ξ和∆ξ取值范围以及ξmin<ξmax等条件的 约束下，以0.1, 0.1和0.005为步长，对这3个阈值的取值进行组合，将组合得到的605组值依次代入到仿真程序，发现在[0.3,0.5],[0.7,0.9]和[0.04,0.05]范围内进行取值更符合本文设置阈值的意图。在剩下的27组取值组合中，经逐一对比发现，将3个变量分别设置为0.4, 0.8和0.045时，两种策略在不同的终端到达率下对缓解网络拥塞和提高用户体验的效果相对其他组取值更为理想，因此此处采用此组数据来验证两种策略对网络环境的感知效果。从中可以看出，本文策略由于考虑了平均负载程度ξ和平均负载变化率∆ξ¯两个指标，在第80个采样周期∆ξ¯超过∆ξ0时做出了第1次预警，并且在此之后由于负载变化率一直超过∆ξ0，本文感知策略已经预警出网络陷入拥塞的趋势为高风险，在第91个采样周期ξ超过ξmax时再次做出了预警提示。而传统策略只有当ξ超过ξmax时才会进行预警，故本文感知策略相较于传统策略能够根据网络的拥塞趋势提早做出预警。

图2 本文策略和传统策略对比

4 组建车辆自组织网络

4.1 相关假设

由于自组织网络具有随时随地自动组网、可扩展性强等特性，当某段道路有大量车辆拥堵引起网络拥塞时，可建立带簇头节点的自组织网络来提升网络性能。因此本文将自组织网络引入到城市核心区域的网络场景中，形成宏蜂窝、微蜂窝、无线局域网(Wireless Local Area Network, WLAN)、自组织网络异构而成的车辆自组织异构无线网络[26]。该场景中的相关假设如下：

(1)每辆车上都装备了GPS，并能协助车载终端精准获取到速度、位置、方向等运动信息。

(2)每辆公交车上都装备了一种能够提供网络服务的无线信号收发器，该装置启动后便能与外部基站建立起通信链路，为接入的车载终端提供网络服务[27]。

(3)将自组织网络的组网形式考虑成由1个簇头(cluster head) 和多个簇节点(cluster node)组成的若干个簇结构。当多个车载终端接入到RT，组成的网络结构称为簇。在一个簇中，装载了无线信号接收器的车辆为簇头，接入到RT的车载终端节点为簇节点。簇头(cluster head)的数量为ch，每个簇头有唯一的编号h，第h个簇中的簇节点(cluster node)数量为cn，各个簇节点也有唯一的编号n。

(4)每个簇头都维护了一张簇信息表(Cluster Information Table, CIT)，用于存储簇的基本信息。

4.2 自组织网络的生成过程和维护

(1)簇相关因子。簇相关因子用于描述自组织网络生成过程中，簇头和簇节点车辆之间的相关性。如果簇节点车辆与簇头的运动方向一致，相对速度越小，位置越接近，则簇相关因子值越大。簇节点更适合加入到簇相关因子更大的簇以维持更持久的连接，簇节点n和簇头h的簇相关因子β可表示为

(3)车辆自组织网络分簇算法。当网络环境感知算法判决出网络有拥塞趋势时，就应该提早启动分簇算法组建车辆自组织网络来缓解网络拥塞。由于车辆的移动会导致簇头和簇节点之间的状态频繁发生变化，为了维持簇内的正常通信，本文通过报文消息机制对簇的生成、簇饱和限制、簇销毁几个阶段进行维护，在簇头和簇节点之间传输的报文消息携带了建簇过程需要采集的数据，算法具体步骤如表1所示。

表1 车辆自组织网络分簇算法

5 自适应切换判决算法

在本文网络场景中将车载终端的业务请求大致分为高带宽时延敏感型业务(如视频通话)和低带宽数据型业务(如网页浏览)两种类型。通过分析用户的实际用网体验可知，随着网络环境的变化，用户对网络的要求也会做出相应调整。当网络环境正常时，大多数网络都能满足用户的基本服务需求，此时用户希望用更低的网络花费换来更高的传输速率；当网络环境拥塞时，一味地追求性价比会加剧网络的拥塞，此时低阻塞率成为用户关注的重点。因此本文提出一种自适应切换判决算法，该算法能够根据终端请求的业务类型和网络环境感知结果，自适应调整用户的候选网络和输入到判决算法中的选网参数，为终端筛选出当前环境下满意度最高的目标网络。

5.1 相关参数定义

(1)接收信号强度与数据传输速率。接收信号强度(Received Signal Strength, RSS)是终端评价网络的一个基本指标，它反映了网络的信道质量。由于信号在传输过程中存在路径损耗，终端i接入网络j的接收信号强度可表示为

(2)业务适应度。当网络拥塞时，希望通过自组织网络来缓解网络拥塞，但由于自组织网络提供的服务能力有限，因此应尽可能避免让高带宽业务需求的终端接入到自组织网络。为了让切换的终端能根据业务请求自适应匹配候选网络，本文定义业务适应度这一指标来衡量各网络对业务的适应能力，业务适应度越高表示网络越适宜该类业务请求，反之，越不适宜。若业务适应度为0，则表示网络不支持用户请求的业务。因此终端i以业务类型l接入网络j的业务适应度可表示为

5.2 基于秩和比的自适应切换判决算法

秩和比综合评价法[28]，是一种集古典参数统计与近代非参数统计各自优点于一体的统计分析方法，它能够很好地避免决策过程中的主观因素。在终端选网决策过程中，将待评价的候选网络和评价网络性能的参数抽象为一个N行M列的数据矩阵，便可通过秩和比综合评价法决策出最优网络。本文所提基于秩和比的自适应切换判决算法的流程如图3所示。

图3 基于秩和比的自适应切换判决算法

(1)获取选网参数：选网判决过程中需提前获取的网络参数有网络拥塞程度(ρ)、终端请求的业务类型(l)、数据传输速率(e)、网络成本(c)、网络阻塞率(b)。

6 仿真结果分析

6.1 系统模型和仿真参数设置

为了评估本文所提算法的性能，利用Matlab仿真工具模拟了城市核心区域潮汐高峰期某一段长3000 m、宽30 m双向4车道的网络仿真场景。在该仿真场景中，假设部署有2个5G宏基站(5GM)，2 0 个5 G 微 基 站(5 G S)以 及2 0 个 无 线 局 域 网(WLAN)和若干车辆自组织网络(Ad Hoc)。在整个网络覆盖范围内，假设车辆的到达服从到达率为1≤λ ≤10的泊松分布。本文的网络场景如图4所示，为了便于观察，图4的网络场景简化了5G微基站、无线局域网和车辆自组织网络的数量。

图4 城市核心区域异构无线网络仿真场景

为了验证本文算法能够适应车辆自组织异构网络中的接入问题，仿真中设计了平均负载程度、网络吞吐量、平均阻塞率、接入终端掉话率等8组实验。由于文献基于层次分析法和简单加权(Analytic Hierarchy and Simple Additive Weighting, AHPSAW)的垂直切换算法[30]，基于阈值的多业务负载均衡(Multi-Traffific Load Balance, MTLB)算法[31]和基于负载均衡和QoS感知(Load Balancing and QoS-Aware, LBQA)的网络选择算法[32]提出了不同的方案来解决与本文类似的网络拥塞和负载均衡等问题，故选取了这3种算法与本文所提算法进行对比分析。仿真中的网络参数设置如表2所示。

表2 网络仿真参数

6.2 网络平均负载程度和吞吐量

图5为4种算法的平均负载程度变化曲线，从中可以看出随着车载终端数量的增加，网络的平均负载程度逐渐上升。在车载终端数量低于400台时，本文的LBUE算法的网络平均负载程度比MTLB算法略高，这是因为LBUE算法在网络不拥塞时，选择的是网络服务质量较好且成本较低的网络，消耗了更多的网络资源。但随着车载终端数量增加到500台时，本文算法通过网络环境感知判决出网络有拥塞风险，便通过分簇算法引入车辆自组织网络，并通过自适应算法调整决策参数，让终端接入到了阻塞率较低的网络，减少了接入到重负载基站的终端数量，降低了网络的平均负载程度。

图5 网络平均负载程度

图6比较了4种算法的网络总吞吐量。从中可以看出，随着终端数量的增加，系统总吞吐量呈上升趋势，当终端数量低于500台时，4种算法的总吞吐量都迅速上升；当终端数量高于500台时，由于网络总的资源有限，总吞吐量上升的趋势逐渐趋于平稳。但当终端数量相同时，LBUE算法的总吞吐量始终高于其他3种算法。这是因为当网络即将拥塞时，本文算法引入了车辆自组织网络，增加了网络容量，减少了接入到蜂窝网络和WLAN中的车载终端数量，均衡了各个网络的负载，有效地提高了网络总吞吐量。

图6 网络总吞吐量

6.3 平均阻塞率和接入终端掉话率

图7表示的是4种算法的平均阻塞率变化曲线，从中可以看出当车载终端的到达率λ≤3时，网络资源充足，4种算法的接入阻塞率都趋近于0，随着到达率的增大，网络中会有越来越多的终端开始竞争网络资源，因此3种对比算法都相继出现部分终端被阻塞。从图中不难看出MTLB算法的阻塞率一直处于最大，而本文所提的LBUE算法在终端到达率λ= 8时才开始出现阻塞，这是因为MTLB算法在均衡实时业务和非实时业务时，部分实时业务被迁移到了将要发生阻塞的网络中，增加了阻塞的可能性。而本文算法，在通过环境感知判决出网络有拥塞的可能就会引入自组织网络，增加了终端的接入选择，因此随着终端到达率的增加，本文算法的接入阻塞率始终低于其他3种算法。

图7 用户平均阻塞率

图8是接入终端掉话率随到达率的变化曲线。从图中可以看出当网络中接入的终端数量较少时，每个终端能够分配到足够的网络资源，因此掉话率趋近于0，但由于网络资源有限，随着接入网络终端数量的增加，部分终端分配到的网络资源将无法满足其最低需求，终端掉话率逐渐上升，但本文算法相较于其他3种算法，掉话率上升得比较缓慢，这是因为自组织网络能够为部分网页浏览类业务终端提供服务，较大程度地减少了掉话终端的数量。

图8 接入终端掉话率

6.4 接入终端数量和网络稳定性

图9反映的是当接入终端数量为1000台时，采用本文算法的不同业务类型终端接入到各类网络的数量。从中可以看出浏览网页的终端在各类网络中均有接入，而视频通话的终端则主要接入到了5G微蜂窝和WLAN网络。这是因为浏览网页所需的资源块较少，在计算业务适应度时各类网络均能适应其业务请求，视频通话需要的资源块较多，接入到自组织网络的业务适应度会比较低。

图9 不同业务类型终端接入各类网络的数量

图10反映的是某业务类型为网页浏览的终端在1 min内接入4种不同类型网络所能获得的数据传输速率。从中不难看出，该终端在各个时刻获得的数据传输速率一直处于波动状态，但4类网络均能满足该终端的业务需求。由于标准差能够衡量数据的稳定性，使用4组数据计算标准差，求得宏蜂窝的标准差为5.4325，微蜂窝的标准差为5.7729,WLAN的标准差为5.7709，Ad Hoc网络的标准差为5.9772。因此，相较于已有的网络，自组织网络的数据传输速率的波动在可接受范围，且能够保证该终端的正常通信。

图10 数据传输速率波动情况

6.5 时间开销和信令开销

图11为4种算法的时间开销变化曲线，从中可以看出随着车载终端数量的增加，4种算法的时间开销都逐渐增加。刚开始时几种算法的时间复杂度相差不大。但随着车载终端数量增加到500台时，本文算法的时间复杂度比其他3种算法略微偏大。出现这种现象是因为本文算法感知到网络拥塞时，就启动了自组织网络的构建过程，组建自组织网络的过程产生了一定的时间开销，并且随着车辆数量的增加，越来越多的车辆会考虑接入到自组织网络，因此本文算法的时间开销始终略微高于其他3种算法。

图11 时间开销

图12显示了随着车载终端数量增加时，4种算法的信令开销占总资源消耗的比值对比。随着终端数量的增加，4种算法的信令开销占比也在不断增加，这是因为终端请求接入网络的过程会有一定的信令开销。当终端数量增加到500台时，本文算法的信令开销占比相较于其他3种算法一直处于略微偏高的状态，这是因为本文采用了报文消息机制构建自组织网络，在簇的生成和维护过程中产生了一些必要的信令开销。

图12 信令开销

7 结束语

本文提出一种考虑负载均衡和用户体验的垂直切换算法，该算法适用于城市核心区域车辆自组织异构无线网络中的切换问题。首先根据负载程度和负载变化率数据实时感知网络环境的拥塞情况。其次，通过网络环境感知结果判决是否建立带簇节点的自组织网络，并把簇头节点加入备选网络集。再次，当终端触发切换后，自适应切换判决算法会根据网络的拥塞状况和业务请求，调整输入到决策算法中的自适应参数，为用户筛选出满意的接入网络。最后，仿真表明，该算法能够缓解城市核心区域的网络拥塞问题，实现负载均衡，提升用户体验。下一步工作，希望通过位置预测和跳跃切换算法解决城市核心区域超密集部网引起的频繁切换，服务降级问题。