车载边缘计算中基于轨迹信息的服务迁移策略

宋志文,范艳芳,贾梦欣,蔡英,陈若愚

(北京信息科技大学 计算机学院,北京 100101)

0 引言

车载边缘计算(vehicular edge computing,VEC)将计算能力从云端下沉到边缘端,可以在更加靠近车辆的位置提供服务,物理距离的减少带来了服务质量的提升[1-3]。然而车辆的高速移动性与边缘服务器有限的覆盖范围,给VEC带来了新的挑战。在行驶过程中,车辆会经过多个边缘服务器的覆盖范围,必须保证车辆的服务不会因此而中断。服务迁移是解决该问题的有效方案,主要思想是不断地将服务实体移动到靠近车辆的边缘服务器上[4-5]。在服务迁移中,每当服务实体在边缘服务器之间进行一次迁移都会产生相应的迁移开销。在服务提供商的立场上,不仅需要保证车辆的服务时延,还需要尽可能地减少迁移开销。然而由于边缘服务器构成的网络环境极其复杂,并且车辆行驶的速度较大,因此在该条件下如何做出最优的迁移决策是一个具有挑战性的问题[6]。

在已知车辆轨迹的情况下,可以获得车辆在边缘服务器覆盖范围内的停留时间。选择迁移到停留时间较长的服务器,可以减少迁移次数,降低时延。车辆的轨迹可以通过轨迹预测的方法获取,如卡尔曼滤波,它可以根据历史运动轨迹预测未来一段时间的车辆运动信息[7],也可以从导航软件中获取轨迹信息,或者假设公交车或自动驾驶车辆在一条固定的轨迹上行驶。

一些研究假设用户的移动轨迹是完全已知的。在这种情况下,文献[8]通过迁移策略制定从第一个时隙到最后一个时隙的迁移动作,策略的目标是使这些时隙的总回报最大化。然而在实际的交通场景中,车辆的行驶轨迹通常较长且更复杂,制定整个轨迹上的迁移动作不适用于复杂的道路交通场景。已有研究通过预测车辆的行驶轨迹来降低服务时延和优化迁移路径,Wang等[9]使用用户的历史移动轨迹来获取用户转移概率矩阵,从而预测用户的移动轨迹。然而在交通场景中,车辆的速度具有高速性和动态变化性,这使得车辆在每个基站范围内的停留时间具有很大的差异,考虑车辆的停留时间可以选择更合适的边缘服务器进行迁移。李迎雪等[10]使用卡尔曼滤波算法预测用户的移动性,利用基站的历史负载信息预测基站负载,然后基于二者的预测信息选择用户连接的基站。该方法充分利用了历史信息来优化迁移过程,但是同样没有考虑车辆高速移动的交通场景中停留时间过短而导致频繁迁移的问题。

Wang等[11]认为移动性预测模型过于依赖用户在基站之间移动的历史数据而忽略了用户在基站内位置的变化,于是通过考虑用户在基站内的移动来提高移动预测的可靠性,并且基于移动预测动态地调整虚拟机复制策略。预测车辆具体位置的变化无疑会带来更为庞大的开销,并且在车辆高速移动的场景中,我们更关注于能够与车辆通信的基站以及与基站的连接时间。例如文献[12]假设,如果车辆在启动时已经确定了目的地,导航应用程序就可以制定一个合理的行驶路线。即使车辆在行驶途中改变目的地,那么重新规划一条行驶路线也只需要付出较小的代价。通过这种方式,将车辆移动轨迹的不确定性对于服务迁移决策的影响控制在一个可接受的范围。但是在选择迁移的目标服务器时,文中仅考虑了与车辆最近的边缘服务器,未能充分利用车辆的轨迹信息。如果将行驶轨迹上的其他边缘服务器纳入到迁移决策中,就可以增加迁移策略的动作空间,有效减少迁移次数,降低迁移开销。

综上所述,在依赖轨迹信息的现有研究中,少有利用轨迹信息优化多边缘服务器选择问题以及通过考虑用户停留时间提高迁移效率的研究。因此,本文提出依赖轨迹信息的服务迁移策略,根据车辆的轨迹信息优化服务迁移过程。本文的主要贡献如下:1)针对复杂的VEC网络环境,提出了一种依赖轨迹信息的服务迁移策略,可以更好地解决多边缘服务器选择问题,有效降低服务时延和减少迁移次数;2)设计了一种基于竞争深度Q网络(dueling deep Q-network,Dueling DQN)的迁移算法执行迁移决策,可以解决VEC环境下边缘网络环境复杂导致的状态和动作空间过大的问题。

1 系统模型

图1显示了VEC中的服务迁移示例。假设目标车辆从当前位置开始行驶,带有箭头的实线为其行驶轨迹。道路两旁设置基站和边缘服务器,服务实体运行在边缘服务器上,每个基站的信号覆盖范围用一个圆形表示。将每个基站和与其连接的边缘服务器看作一个整体,用Bi表示第i个基站和边缘服务器组。以图1中的A点和B点为例,当图中车辆行驶到位置A时,如果只考虑通信时延,那么服务实体将会迁移至B2。根据车辆的轨迹可以得知车辆只会在B2内行驶很短的一段距离,驶出后需重新进行迁移决策,而频繁的迁移将会产生额外的迁移开销。市区中的基站部署通常都会很密集,某些位置会同时被多个基站覆盖,比如图中的位置B,车辆同时被B3和B4覆盖,如果此时迁移到B3,那么车辆向右行驶后又将忍受高服务时延或再次执行迁移。

图1 VEC中的服务迁移示例Fig.1 Example of service migration in VEC

利用车辆的轨迹信息可以高效地解决上述问题。如果可以得知车辆在B2范围内的行驶时间,那么在位置A时,将服务实体迁移到B4可以牺牲一些通信时延来换取更少的迁移成本。当车辆从起始位置行驶到位置B时,如果将服务实体迁移至B4,那么无论是服务时延还是迁移开销都比迁移至B3时更少。

本文考虑二维的交通场景,车辆的行驶轨迹上包含多组基站和边缘服务器,车辆与最近的基站进行无线通信,基站之间使用有线连接进行通信。场景中的位置用二维坐标(x,y)表示,用N表示每组基站和边缘服务器所在位置的集合,将基站之间的相对距离定义为基站之间跳数。车辆的移动和服务迁移过程是一个无记忆的连续决策过程,具有马尔可夫性质。因此,本文使用基于马尔可夫决策过程(Markov decision process,MDP)的时隙模型,在一个时隙开始时,车辆会更新其位置并与最近的基站建立连接,然后进行一次迁移决策。换而言之,一个时隙内的车辆位置保持不变且始终与最近的基站保持连接。车辆和服务实体在时隙t的位置分别用lv(t)和ls(t)表示,服务实体迁移的目标位置用ls′(t)表示。本文模型将距离车辆最近的基站的位置视为车辆当前所在的位置,每个边缘服务器的位置被视为与其连接的基站的位置,即lv(t),ls(t),ls′(t)∈N。

1.1 通信时延

在本文考虑的模型中,通信时延由车辆与基站之间的无线通信时延和基站与基站之间的回程线路通信时延组成。

根据香农定律,W为信道带宽,N为噪声功率,S为车辆的传输功率,g(t)表示车辆与基站之间的信道增益,则无线通信方式的最大传输速率为

(1)

由于下行传输的数据量较小,所以忽略下行传输的时延。用bv(t)表示车辆的上传数据量大小,则无线通信时延为

(2)

参考文献[13],回程线路通信时延定义为

(3)

因此,通信时延定义为

(4)

1.2 迁移开销

参考文献[14],将迁移开销函数定义为如下形式:

(5)

2 依赖轨迹信息的服务迁移策略

2.1 问题描述

本文所提策略的目标是减少通信时延和迁移开销之和,使系统总开销最小化。用U(t)表示时隙t内的系统总开销:

U(t)=ω1Dnet(dv,s(t))+ω2Cmigrate(ds,s′(t))

(6)

式中:ω1、ω2为权重,分别表示迁移开销和通信时延的重要性。在一个时隙中,迁移开销和通信开销都受车辆位置和服务实体位置的影响,本文的目标是在T时隙内最小化系统总开销。因此,目标函数如下:

(7)

多个边缘服务器不仅导致了庞大状态空间,也增大了动作空间,要快速地获取最优解更是一个挑战。深度强化学习在基于MDP的决策问题上具有很好的表现,而Dueling DQN可以更快地进行决策,因此,本文使用基于Dueling DQN的服务迁移算法来求解P1。

2.2 基于Dueling DQN的服务迁移算法

Dueling DQN是在深度Q网络(deep Q-network,DQN)的基础上,使用两层不同的网络分别表示状态函数和动作函数,在存在多个类似价值的动作时,可以学习到更好的策略[15]。在本文考虑问题中,车辆的轨迹上具有一系列覆盖范围相互重叠的边缘服务器,同一个位置被多个边缘服务器覆盖,基于Dueling DQN的算法可以在此条件下学习到更优的策略。

每个时隙可以从环境中获取状态信息,包括车辆的位置、服务实体的位置、车辆的轨迹信息和可迁移的服务器集合,那么时隙t的状态表示为S(t)={lv(t),ls(t),Ltra(t),Lbs(t)}。其中,本文假设可以获取To时隙内的车辆轨迹,Ltra(t)就表示从t时隙开始到t+To时隙内的车辆轨迹信息,Lbs(t)表示可迁移的边缘服务器位置集合。

动作：在每个时隙开始时,服务实体会被迁移至目标位置,包括以车辆为中心一定距离范围内的所有基站的位置,A(t)表示迁移的动作集合。在本文考虑的场景中,基站的部署非常密集并且车辆在某一基站的停留时间很短,距离车辆最近的边缘服务器未必是最优的迁移选择,因此动作集合也会包括车辆行驶轨迹外的基站位置。

奖励：本文的目标是权衡通信时延和迁移开销,使系统总开销最小化,因此奖励定义为系统总开销的负数:R(t)=-U(t)。

基于Dueling DQN的服务迁移算法的决策过程如算法1所示。首先初始化经验回放集合、初始状态。在每个时隙中利用ε-贪心策略选择迁移动作(第3～7行),在ε的概率下选择随机动作,在1-ε的概率下,选择所有动作中Q值最大的迁移动作,即在所有可迁移的边缘服务器中选择Q值最大的边缘服务器。执行迁移动作后会获取当前时隙的奖励和下一个状态(第8行),然后把当前状态、动作、奖励和下一个状态存储到经验回放集合中(第9行)。最后每隔一定时间执行算法2训练Q网络。

算法1:决策算法输入:初始探索率ε,训练周期Y1.初始化经验回放集合D和初始状态S(1)2.fort=1 to T do3. if rand()<ε then4. 随机选取动作A(t)5. else6. 通过Q网络计算所有动作的Q值,并选择Q值最大的动作A(t)7. end if8. 执行A(t)并得到R(t)和S(t+1)9. 将{S(t),A(t),R(t),S(t+1)}存储到D中10.if t mod Y=0 then11. 执行算法212. end if13.end for

3 仿真实验

3.1 参数设置

为了验证所提策略在不同交通环境的有效性,共设置了3个数据集。

数据集1:采样间隔为1 s的仿真车辆轨迹数据,车辆以30 km/h的速度匀速行驶在长度为10 km的道路上,此数据集中车辆行驶的特点是匀速直线行驶。

数据集2:来自真实世界采集的车辆轨迹数据集[17-18],包含了7 d的北京出租车轨迹数据,选取一条行驶距离约为18 km的车辆轨迹,根据北京市的5G基站部署[19]设置了50组基站和边缘服务器。该轨迹数据相较数据集1更为复杂,不仅车辆的速度会有变化,并且会有停靠和掉头的驾驶行为,这导致车辆在每个边缘服务器覆盖范围内的停留时间差异较大。

数据集3:同样来自真实世界采集的车辆轨迹数据,选取了一条行驶距离约为170 km的车辆轨迹,沿途部署600组基站和边缘服务器。与数据集2相比,车辆轨迹更长,并且部署的基站和边缘服务器更加密集。

不失一般性,其他环境参数设置见表1。

表1 环境参数设置Table 1 Environmental parameter setting

本文使用Python进行实验环境的搭建,并使用PyTorch工具包训练DQN。所提算法的Q网络由5层256个神经元的全连接神经网络构成,采用LeakyReLU激活函数,使用Adam优化器调整学习率,其他参数见表2。

表2 DQN参数设置Table 2 DQN parameter setting

3.2 结果分析

为了验证本文所提策略的有效性,将其与以下3种策略进行对比。

始终迁移策略:服务实体总是迁移到距离车辆最近的目标边缘服务器上。

固定距离迁移策略:设定一个距离阈值,只有当服务实体与车辆之间的距离大于这个阈值时,才会进行服务迁移。

最小化迁移开销和通信开销的迁移策略(minimize migration and transmission cost,MMTC):使用基于DQL的服务迁移算法进行迁移决策,只根据当前车辆的位置和服务实体的位置进行迁移,目标是最小化迁移开销和通信时延。与本文所提策略不同的是,该策略没有考虑车辆的轨迹信息和其他的边缘服务器,迁移的目标仅为车辆当前所在的边缘服务器。

为了避免偶然性,所有的实验结果都是进行了100次实验后取的平均值。图2显示了不同数据集下的系统总开销,可以看到所提策略在3个数据集中的系统总开销均低于其他策略,能够达到最小化系统总开销的目标,这意味着本文所提出的基于Dueling DQN的服务迁移算法可以适应不同的VEC环境。

图2 不同数据集下的系统总开销Fig.2 Total system cost with different datasets

以数据集2上的实验为例研究4种策略的通信开销和迁移开销的具体情况,结果如图3所示。始终迁移策略能够取得最少的通信开销,但是频繁的迁移导致了最高的迁移开销。固定距离迁移策略则恰好相反,能够取得最少的迁移开销,但是通信开销达到了最高。MMTC策略可以在通信开销和迁移开销之间取得一个较好的平衡。而本文所提策略可以根据轨迹信息优化迁移,有效降低迁移次数来降低迁移开销,取得最小的系统总开销。

图3 四种策略的不同开销性能评估Fig.3 Performance evaluation of four strategies with different cost

本文对比了不同边缘服务器部署密度对开销的影响,结果如图4所示。基站之间的距离设置参考北京市5G基站的部署情况[19],并将此边缘服务器部署密度称为中等。在此基础上,将边缘服务器数量减少一半的部署密度称为稀疏,将边缘服务器数量增加一倍的密度称为密集。可以看出,所有策略的系统开销随着部署的边缘服务器密度的增加而下降。这是因为随着边缘服务器部署密度的增加,可供选择的边缘服务器更多,策略就可以选择更合适的迁移动作。而本文所提策略可以在任何密度下取得最小的总开销,并且在边缘服务器部署密集的情况下,所提策略的优势更加明显,这是因为所提策略充分考虑了所有可选动作,能够做出通信开销最小,迁移次数最少的迁移决策。

图4 不同部署密度下的系统总开销Fig.4 Total system cost for different deployment densities

图5展示了所提策略在不同观测时隙长度下的总开销。3个数据集中实验结果呈现出了类似的趋势,随着观测时隙长度的增加,系统总开销随之减少。观测时隙长度的增加意味着可以知道更多的轨迹信息,所提算法可以根据未来的轨迹得到更好的迁移策略;但是当观测时隙长度继续增加时,总开销的增长趋势开始减缓,这是因为已经获取最优的迁移位置之后,额外的轨迹信息也不会再对策略有所帮助,并且增加观测时隙的长度还会使算法处理的数据规模增加,导致决策算法开销的增加。

图5 边缘服务器不同观测时隙长度下的系统总开销Fig.5 Total system cost for edge servers with different observed time slots

图6为使用所提策略在数据集2上某次实验的结果,展示了车辆在每个基站覆盖范围内的停留时隙和服务实体的迁移位置。服务实体在整个轨迹上执行迁移的所有目标位置用圆点标注了出来。可以看到,在该策略下,可以选择车辆停留时间较长的基站作为迁移的目标位置,证明所提策略可以有效使用车辆的轨迹信息优化迁移决策。

图6 车辆在每个基站覆盖范围内的停留时隙和迁移位置Fig.6 Vehicle dwell time slots and migration positions within each base station′s coverage area

4 结束语

针对服务迁移过程,本文提出一种依赖轨迹信息的服务迁移策略来降低系统总开销,并使用基于Dueling DQN的服务迁移算法求解。所提策略考虑车辆的轨迹和可迁移的边缘服务器的位置,在多服务器之间选择合适的迁移目标,通过权衡时延和迁移开销,使整个轨迹上的系统总开销最小。仿真实验中,通过与始终迁移策略、固定距离迁移策略和MMTC策略进行比较,验证了所提策略的优越性。在未来的工作中,将考虑带宽和能耗等更多的因素来优化所提策略,以应对更复杂的环境和更严格的服务质量要求。