基于车辆边缘计算的用户能耗最小化资源分配研究

李世超，王秋云，寇为刚，贺国庆

(1.桂林电子科技大学信息与通信学院 广西 桂林 541004；2.甘肃政法大学公安技术学院 兰州 730070)

随着无线通信与物联网技术的发展，车辆因特网(Internet of vehicles, IoV)应运而生，IoV 可以为旅客提供许多新的服务，如语音识别、在线视频以及虚拟现实游戏等[1-2]。这些新的服务需要消耗较多的计算资源并且具有严格的时延约束，但是用户的终端设备往往计算能力有限，无法处理这些应用。为了解决车载用户终端计算能力不足的问题，有学者提出了车辆边缘计算(vehicular edge computing,VEC)，它可以根据业务的需求，灵活地分配资源。

VEC 在提高系统资源利用率的同时，还能够有效提升计算密集业务的用户体验。但是与传统的云服务器相比，当考虑到经济成本以及部署的灵活性时，VEC 服务器的计算能力往往有限[3]。为了进一步提高系统的资源利用率需要一种新的动态资源分配策略。

目前，针对VEC 的资源管理主要有以下研究。为了同时最小化车辆和VEC 服务器的消耗，文献[4]在车辆侧提出了一种联合任务迁移和本地计算资源分配策略。同时在VEC 侧提出了一种联合无线与计算资源分配策略。在智慧城市的车联网中，为了支持更多的时延敏感业务，同时减少网络的负载，文献[5]提出了一种联合无线与计算资源分配方案。文献[6]在车联网中研究了高能效的任务迁移问题，提出了一种基于交替方向乘子法的低复杂度分布式算法。以上所有研究都假设任务在迁移过程中信道状态是固定不变的。但在实际中，任务的迁移时延与车辆信道的相干时间并不在同一个时间级别。例如，当车辆速度为100 km/h，载频为1.8 GHz 时，信道的相干时间约为2.5 ms，而任务的迁移时延可达到数十毫秒至数百毫秒，对于某些时延不敏感的业务，任务的迁移时延可达到数秒。如果不考虑信道的快速时变特性，会使得资源利用率降低，任务的迁移时延也无法得到满足[3-7]。因此，在VEC 系统中进行资源分配时需要考虑信道的时变特性。

信道的快速时变特性是车联网的一个重要特点，本文主要研究在VEC 系统中，信道的快速时变特性对资源分配策略的影响。构建一个在系统计算资源和信道容量有限以及任务QoS 约束下的车载用户终端能耗最小化问题。由于车联网场景中多是视距场景，并且车辆的位置可以预测，因此可以利用路径损耗信息替代信道状态信息(channel state information, CSI)。通过利用李雅普诺夫随机优化理论，可以将原问题转化为两个子问题。由于计算资源分配子问题是一个单变量的优化问题，因此很容易求解。而无线资源分配子问题是一个混合整数规划问题，通过将该问题转换为单变量的优化问题进行求解。基于以上两个子问题的结果，提出一种联合无线与计算资源分配(joint radio and computation resource allocation, JRCRA)算法，并通过仿真结果验证JRCRA 算法的有效性。

本文的主要贡献包括以下3 点：

1) 本文在考虑车辆快速时变信道的特性下，提出一种联合无线与计算资源分配算法来减少车载用户的能量消耗。仿真结果显示，当数据包平均到达速率从20 个/时隙增加到40 个/时隙时，提出的算法性能相较于传统的贪婪算法能耗降低了48.85%。

2) 利用李雅普诺夫随机优化理论，通过调整控制参数V，可以实现车载用户能量消耗与任务处理时延的均衡。

3) 针对分解后的无线资源分配子问题，提出了一种有效算法来求解该混合整数规划问题。

1 系统模型

本节首先给出VEC 的系统模型，接着给出任务的传输队列和计算队列。

1.1 网络模型

式中，α为路径损耗因子。由于小区的信道变化是可预测的，并且每个小区内的信道变化是对称的，因此本文只需要研究半个小区内的资源分配策略[8]。

定义 P(t)为车载用户终端在时刻的发射功率。此时，车辆与RSU 之间的无线传输速率为：

式中， W是系统带宽。假设数据包的大小相同，均为 L比特，则链路容量可以定义为能够传输的最大数据包数量为

1.2 动态队列模型

在本文中，用两类队列模型来表示任务由车载用户终端到VEC 服务器的处理过程。如图1 所示，任务的处理过程被分为两个阶段，一是任务的传输阶段，二是任务在VEC 服务器中的计算阶段。这两个阶段可以分别被建模为任务的传输队列和计算队列。

对于任务传输队列，车载用户终端将K 个独立的任务迁移至VEC 服务器。定义任务集合为K={1,2,···,K}。 定 义 H( t)=[H1(t),H2(t),···,Hk(t)]为传输队列积压向量，其中 Hk(t)为 第 k 个任务在t时刻的传输队列积压。

定 义 A( t)=[A1(t),A2(t),···,Ak(t)]为 任 务 所 产 生的数据包向量，其中 Ak(t)为 第 k 个任务在t时刻所产生的数据包。任务数据包的产生速度满足均值为λk=E[Ak(t)]的 独立同分布过程，并且第 k个任务在每一时隙所能产生的最大数据包为 Bk。定义ck(t)∈[0,Hk(t)]为 第 k 个任务在t时刻所迁移的数据包。因此，第k 个任务的传输队列可以表示为：

为了保证任务的QoS 需求，从长期平均的角度来看，平均的迁移数据包不应小于 qk。计算。定义 Q( t)=[Q1(t),Q2(t),···,Qk(t)]为VEC 服务器的计算队列积压向量，其中 Qk(t)为 第 k个任务在t时刻的计算队列积压。定义 µk( t)∈[0,Qk(t)]为 第 k个任务在t时刻所计算的数据包。因此，第k 个任务的计算队列可以表示为：

对于任务计算队列，任务由VEC 服务器进行

2 问题建模与重构

本节首先在VEC 系统中构造一个联合无线与计算资源分配问题，该问题是在保证任务QoS 要求下实现车载用户终端能耗最小化。然后利用随机动态优化理论对该问题进行重构。

2.1 队列稳定与问题建模

为了避免丢包，所有的队列应该保持稳定。对于任意变量z，定义长期平均期望为：

基于长期时间平均期望，队列稳定需要满足如下条件[10]：

基于以上队列稳定的定义，联合无线与计算资源分配的问题可以建模为：

式中， µtotal为VEC 服务器的总计算资源。约束式(6b)表示每个任务的QoS 要求；约束式(6c)确保队列稳定；约束式(6d)为信道容量约束；约束式(6e)为VEC 服务器总计算资源约束；约束式(6f)和式(6g)分别表示迁移数据包和计算数据包约束。由于式(6)是一个非凸问题，难以求解，因此需要对该问题进行重构。

2.2 问题重构

由于式(6)存在时间平均，因此难以求解。本小节采用随机动态优化理论将约束式(6b)重新构建为单个时间平均的函数[9]。引入虚拟队列 Zk(t)，可以表示为：

其初始条件为 Zk( 0)=0。 对于虚拟队列 Zk(t)，ck(t)可以看作是每个虚拟队列所处理的数据包，qk可 以看作是虚拟队列 Zk(t)的到达数据包。

基于虚拟队列 Zk(t)，式(6)可以被重构为：

式(8)仍然难以求解，下一节利用动态随机优化算法来求解该问题。

3 动态无线与计算资源分配算法

本节利用动态随机优化理论来求解式(8)。首先，利用李雅普诺夫随机优化理论将式(8)分解为两个独立的子问题。然后通过对两个子问题进行求解，提出动态无线与计算资源分配算法。

3.1 李雅普诺夫漂移

定义 Z(t)为 虚拟队列 Zk(t)所 组成的向量。 Θ(t)为虚拟队列和实际队列所组成的向量，可以表示为：

二阶李雅普诺夫函数可以表示为：

李雅普诺夫漂移可以表示为：

由于 ∆(Θ (t))难 以求解，因此下面对 ∆(Θ (t))的上界进行分析。

定理 1在t 时刻，对于任意队列状态，在任意接入控制与资源分配策略下，Θ (t)应满足以下不等式：

式中，

相关证明见文献[11]。

3.2 问题分解

上一小节得到了李雅普诺夫漂移 ∆(Θ (t))的上界。本小节利用漂移惩罚因子理论来最小化“漂移惩罚因子”，其表达式为：

根据李雅普诺夫随机优化理论，问题目标是最小化李雅普诺夫漂移 ∆(Θ (t))，可以通过在每一时隙最小化的右式来求得。右式可被分解为一系列子问题，可以在每一时隙利用实际队列与虚拟队列进行求解。对于式(15)，可以被分解为两个独立的子问题。

从式(15)中分解出 ck(t) 和 P(t)，可以得到无线资源分配子问题：

同理，从式(15)中分解出 µk(t)，可以得到计算资源分配子问题：

3.3 计算资源分配

3.4 无线资源分配

无线资源分配子问题可表示为：

由于 ck(t)是一个整数变量，式(19)是一个混合整数规划问题，因此难以求解。接下来通过将式(19)转换为一个单变量问题，提出一种无线资源分配策略。为了简化方便，下面省略时间标号t。

从式(19a)中可以看出，如果 Hk+Zk⩽Qk，那么问题的最优解是 ck= 0， P= 0。

当 Hk+Zk>Qk时，首先忽略C 的整数特性，当取得最优的无线资源分配策略时，约束式(19b)可以写为：

式(20)成立是因为对于任意的可行解 ck都可以通过减少C 和P 在满足约束式(19b)、式(19c)的情况下进一步增大。对于式(20)，功率消耗可以表示为：

约束式(19c)可以进一步写为：

其次，考虑C 的整数特性，无线资源分配的式(19)可以重新被构建为一个单变量优化问题：

式中，

为了求解式(23)，首先给出以下定理：

定理 2函数在 [0, f(K)]范围内是关于C 的单峰函数。

基于定理2，提出一种无线资源分配算法如算法1 所示。

算法1 无线资源分配算法

1) 初始化 ck= 0；( 0)=0 ；C=0

2) 将任务按照 Hk+Zk−Qk降序排列，得到排列集合{k1,k2,···,kK}

3) for n=1 to K do

5) C:=C+1

then

9) 跳至步骤13)

10) end if

11) end for

12) end for

13) 通过式(21)，得到 P 和ck

3.5 联合无线与计算资源分配算法

基于以上两个独立的子问题，本小节提出JRCRA算法如算法2 所示。首先初始化所有的系统参数，在每一时隙根据式(18)和算法1 求解计算资源分配和无线资源分配两个子问题。在每一时隙结束时，队列向量 Θ( t+1)通过式(3)，式(4)和式(7)来进行更新。在每一时隙重复该算法。

算法2 JRCRA 算法

1) 初始化系统参数；

2) while t ∈ [0,T] do

3) for k=1 to K do

4) 通过式(18)得到µk(t)

5) 通过求解子式(19)得到 ck(t) 和P(t)

6) 通过式(3)，式(4)和式(7)更新 Hk(t)，Qk(t)和 Zk(t)

7) end for

8) end while

4 仿真结果与分析

本节验证提出的JRCRA 算法性能。仿真参数如表1 所示。

图2 为不同控制参数V 对总平均功率消耗的影响。从该图中可以看出，总平均功率消耗随着参数V 的增加而下降，并且当V 足够大时，会收敛至最优的功率消耗。图3 为不同控制参数V 对总平均队列积压的影响。从该图中可以看出，总平均队列积压随着V 线性增加。从图2 和图3 可以看出，总平均功率消耗和队列积压可以通过调整控制参数V 以实现均衡。另外，随着数据包到达速度的增加，平均功率消耗和队列积压都有明显的增加。

表1 仿真参数

为了证明提出的JRCRA 算法的有效性，本文将JRCRA 算法与贪婪算法进行比较。贪婪算法是按顺序一个接一个的处理任务，只有处理完一个任务才会处理下一个任务。

图4 为不同算法下数据包平均到达速率对平均功率消耗的影响。所有的任务QoS 要求相同并且控制参数V 为200。从该图中可以看出当数据包平均到达速率增大时，贪婪算法所消耗的功率大于JRCRA 算法所消耗的功率。当数据包平均到达速率从20 个/时隙增加到40 个/时隙时，提出的JRCRA算法相较于传统的贪婪算法能耗降低了48.85%。这是因为对于贪婪算法来说，如果一个任务要被处理，那么必须要等该任务之前的所有任务都已处理完毕。这样可能会导致在信道条件较差的情况下，有大量的数据包需要被迁移至服务器。为了确保任务的QoS 需求，用户则需要增加发射功率。

5 结 束 语

本文在VEC 系统中研究了车辆快速时变信道对资源分配策略的影响。首先构建了一个联合无线与计算资源分配使得车载用户终端能量消耗最小化的问题，并利用车辆信道的可预测特性和李雅普诺夫随机优化理论，将原问题分解为两个子问题。然后通过对两个子问题进行求解，提出了JRCRA 算法。最后仿真结果显示，当数据包平均到达速率从20 个/时隙增加到40 个/时隙时，此算法性能相较于传统的贪婪算法能耗降低了48.85%。

本文仅研究了一个VEC 服务器的迁移与资源分配问题。后续可以接着从多VEC 服务器选择方面进行研究。当网络中存在大量VEC 服务器时，车载用户可以通过选择计算资源更为丰富的VEC 服务器来进行迁移计算，进一步降低时延，减少能耗。

本文的研究还得到兰州市科技局项目(2018-3-9)和甘肃政法学院校级科研项目(GSZF2018XQNLW10,GSZF2017XQNLW02)的支持，在此表示感谢！