考虑信息年龄的无人机辅助智能交通系统计算卸载优化

钟伟锋 黄旭民 康嘉文 谢胜利

(广东工业大学自动化学院 广州 510006)

1 引言

使用无人机(Unmanned Aerial Vehicle, UAV)的交通监控方法具有机动灵活、部署成本低、隐蔽性强、覆盖范围广等优点，配合现有的固定式交通监控方法，可实现全方位覆盖、全天候监控以及对道路突发事件的快速响应，是打造智能交通系统与建设智慧城市的重要抓手[1]。根据智能交通系统后台(即控制中心)的管理需要，调度多架UAV前往不同观察点，执行交通流量监测、运动目标跟踪、车辆/行人/交通标志监测与识别等任务。为了配合UAV去完成计算密集型的任务(如流量预测[2]、目标监测与追踪[3]、行为分析[4])，结合5G时代的移动边缘计算(Mobile Edge Computing, MEC)技术，在基站侧部署MEC服务器，为存储容量小且计算能力有限的UAV提供额外的存储空间与计算资源[5,6]。可以将常用的交通监控应用程序提前缓存于MEC服务器，并把UAV计算任务卸载到MEC服务器，也可以让UAV从MEC服务器下载应用程序，并在UAV本地执行计算任务。UAV到达指定观察点后，采集周边数据并现场处理数据，完成计算任务后，将最新数据的处理结果作为现场信息反馈至控制中心。控制中心通过综合多架UAV提供的多种现场信息，来制定交通管理策略，如图1所示。

图1 智能交通系统示意图

在UAV辅助的智能交通系统中，需要关注两个关键问题，数据处理产生的能耗和数据的时效性。首先，系统部署完成之后，系统主要的运行成本来自系统能耗，因此需要根据MEC服务器的缓存状态，制定区域内多架UAV与MEC服务器之间的协同通信和计算策略，以降低系统能耗和用电成本。此外，控制中心要求UAV提供足够新鲜的现场信息，以满足实时监控的需求，保证控制中心决策的时效性、准确性和可靠性。信息年龄(Age of Information, AoI)是一种衡量信息新鲜度的时间度量，可将其理解为从信息产生到当前时刻所经历的时长，用于描述信息的时效性，AoI值越小信息新鲜度越高。因此，需要考虑针对智能交通系统设计一种衡量UAV所提供信息的AoI指标，并尽可能让其减小。

目前，已有文献针对UAV数据收集与处理中的AoI与能耗优化问题提出了不同的解决方案。文献[5]提出终端用户与UAV通信中的离散AoI，在用户与UAV开始数据传输时AoI值为1，在传输过程中AoI值持续加1，传输完毕后重置为1。文献[6]关注UAV与MEC服务器等边缘节点状态信息的AoI值，它与终端用户侦测到边缘节点可接入的时间相关。文献[7]把UAV完成终端用户计算卸载服务的时延作为计算任务的新鲜度指标。类似地，文献[8]考虑物联网(Internet of Things, IoT)设备状态信息的AoI值，将其定义为从信息产生到完成信息处理得到结果的时延。进一步，文献[9]考虑多架UAV协助多个IoT设备的状态更新，分析出各IoT设备状态更新数据处理的平均峰值AoI，随后以最小化所有IoT设备的平均峰值AoI和任务处理产生的能耗为目标，联合优化任务卸载与UAV飞行轨迹，然而此文献假定所有IoT设备的本地算力相同且所执行任务相同，这在应用中有一定的局限性。基于相同的优化目标，文献[10]考虑单架UAV依次飞往不同IoT设备附近，作为数据中继转发IoT设备数据至基站，各IoT设备的AoI值主要受UAV飞行次序和数据传输带宽的影响。文献[11]关注UAV飞往不同IoT设备同时进行数据采集和能量传输的场景，与文献[5]类似，IoT设备AoI值的变化是离散的，通过联合优化UAV飞行、数据采集与能量传输策略，来最小化UAV总能耗，此文献同样不涉及UAV的数据处理。文献[12]中，终端用户可将任务卸载至UAV或者基站，不同条件下的任务完成时延影响终端用户的AoI值，而此文献只优化通信信道的分配。

此外，现有文献也提出了基于UAV的缓存辅助边缘计算优化方案。文献[13]认为UAV可以缓存部分终端用户的应用程序以服务相应用户，其余用户的应用程序缓存在MEC服务器中，然后构建针对数据缓存、任务卸载、通信和计算资源分配的联合优化问题。类似地，文献[14]也考虑由UAV缓存应用程序，并定时更新缓存内容，进而联合优化UAV的缓存选择、UAV飞往不同终端用户的轨迹以及用户任务卸载目的地的选择等。文献[15]考虑由MEC服务器与两架UAV联合提供缓存空间，使它们向过往车辆提供计算卸载，主要优化系统中存储、通信与计算资源的分配，默认每辆车均需要任务卸载，目标是最大化所服务的车辆数量。然而，以上文献中UAV提前缓存好与任务处理相关的应用程序的假设在应用中将受到挑战。一方面，在现场飞行的UAV可能会被要求临时承担未计划的任务，此时UAV不一定已缓存相应的应用程序。另一方面，UAV作为低功耗的嵌入式设备，其存储空间相当有限，无法缓存全部应用程序(包含可执行文件、函数库与辅助数据等)，尤其当面向智能交通系统的应用程序数据量过大时，UAV难以充当高效的缓存节点。此时MEC服务器与云计算服务器是更好的应用程序缓存地点。

综上所述，同时考虑多架UAV进行数据收集与处理的AoI约束、MEC服务器缓存部分应用程序等条件，并从系统能耗优化角度研究多架UAV与MEC服务器之间协同的工作，在现有文献中是欠缺的。为了解决以上问题，本文针对如图1所示的UAV辅助智能交通系统，提出一种考虑信息年龄的计算卸载方案，集中式联合优化多架UAV任务卸载决策、UAV上下行通信带宽分配和所有被卸载任务的计算资源分配，满足交通监测的实时性需求，最小化数据处理产生的系统能耗。

本文的主要贡献如下：

(1) 考虑UAV交通监测与MEC技术结合的智能交通系统，其中多架UAV执行不同类型的交通监测任务，MEC服务器同时提供数据缓存与计算卸载。利用MEC服务器缓存常用的UAV交通监测应用程序，可提高缓存辅助边缘计算的可执行性。

(2) 模型中考虑多架UAV数据收集与处理的AoI约束，要求每架UAV的AoI峰值不超过某个给定值，构建包括所有UAV与MEC服务器在内的系统能耗最小化问题，联合决策UAV任务卸载、通信和计算资源分配。

(3) 运用离散化和线性化手段，将复杂的混合整数且非凸的能耗最小化问题转化为近似的混合整数线性规划问题，并设计离散点生成算法来调节近似误差。实验结果表明，本方法适用于大型优化问题，可以快速获得原非凸问题的近似最优解。

2 系统模型

2.1 系统描述

如图1所示，控制中心根据决策需要，指派多架UAV前往不同观察点(比如十字路口、主干道出入口与停车场的上空)，以监测当前的车流量、行人数量与空余车位等交通要素。UAV到达观察点后，采集图像数据，并执行相关数据分析与计算任务，以得到有效的现场信息。为了配合UAV, MEC服务器被部署于通信网络的边缘，与本地基站有线连接，它可以提供存储空间以缓存常用的交通监测应用程序(比如流量预测、车辆监测与行人识别)，也可以为邻近UAV提供计算资源。值得一提的是，由于每个应用程序包含可执行文件、函数库与辅助数据等，存储容量有限的UAV无法提前安装好所有的应用程序。在此条件下，如果UAV选择本地执行任务，则需要向MEC服务器请求缓存数据以加载应用。如果UAV选择卸载计算任务，则需要将所收集的数据上传至MEC服务器，由MEC服务器启动相应的应用程序来处理计算任务。计算完成后UAV得到的现场信息不能超过规定的最大AoI。最终，把现场信息上传至控制中心，为综合决策提供依据。

在上述过程中，各UAV与MEC服务器都需要进行优化决策。UAV的决策变量主要为0-1任务卸载变量，即选择本地执行任务或卸载任务至MEC服务器。MEC服务器需要分配与各UAV数据传输的通信带宽，也需要将自身有限的计算资源分配给那些被卸载的任务。本文关注所有UAV与MEC服务器的能耗总和，称之为系统能耗。通过掌握各UAV与MEC服务器的状态和参数，集中式联合优化上述的决策变量。优化目标是，最小化系统能耗，同时保证满足AoI和资源容量等约束条件。

2.2 数学模型

(1) 通信模型。参考文献[16]，本文考虑准静态决策模型，首先指派UAV去观察点执行监测任务，UAV到达观察点后保持悬停状态，使自身空中位置不变，通过建立视距信道与MEC服务器进行无线通信。设无线信道为准静态信道，即信道状态在数据传输过程中保持不变。考虑某区域内多架UAV和1个MEC服务器组成的系统。用I表示所有UAV的集合，将每架UAV标记为i ∈I。为防止UAV之间的通信干扰，UAV与基站之间无线通信采用正交频分多址接入技术[17]，信道功率增益采用自由空间路径损耗模型[18]。定义从基站到UAVi的数据下行速率为

其中，bi为分配给UAVi的通信带宽，di为UAVi在观察点与基站的通信距离，gi为1 m基准距离的信道增益，α为信道衰落指数(一般取2)，Qi为UAVi的接收功率，N0为噪声功率。设式(1)中对数函数所包含的均为常数，使用常数Yi替代对数部分。定义从UAVi到基站的数据上行速率为

其中，Pi表示UAVi的发射功率。同样，使用常数Xi替代对数部分。参考文献[19]，本文考虑每架UAV的上下行通信带宽大小一样，以简化模型。

(2) 时延模型。考虑二进制任务卸载方式，定义0-1变量ai，ai=0 表 示UAVi在本地执行计算任务，ai=1表 示UAVi将计算任务卸载到MEC服务器，有

若UAV在本地执行计算任务，则UAVi的总时间为

其中，等号右边第1项τi为UAV前往观察点的用时；第2项为UAV采集指定数据量Di的用时，si为数据采集速率；第3项为UAV下载指定应用程序的用时，Ui为所请求的应用程序的数据量，ci=1表示应用程序Ui已缓存在MEC服务器，ci=0表示当前MEC服务器没有缓存Ui，需要从云端获取Ui，RM是云端到MEC服务器的数据传输速率；最后一项为UAV的CPU计算时间，为UAVi的本地计算资源，Wi为处理数据Di所需的CPU周期数。类似的，若将UAV计算任务卸载到MEC服务器，则UAVi的总时间花费为

(3) 信息年龄模型。各UAV有不同的数据收集与处理过程，故UAV所提供的现场信息有不同的AoI值。AoI值越小，现场信息新鲜度越高；AoI值越大，现场信息越不新鲜。参考文献[5]，将时间离散化为若干个时隙，将每个时隙记为δ=1,2,...，时隙长度为 Δδ。定义在时隙δ中UAVi的AoI值为

设AoI初始值为1，UAV到达观察点并收集充足输入数据之后，在数据处理完毕之前，UAV未能提供有效的现场信息，此时AoI值会持续增加。当UAV得到计算结果并将其作为现场信息传输至控制中心后，AoI被重置为初始值。本文关注UAVi最终提供现场信息时的AoI值，即

其中，■·」表示向下取整。控制中心对所有UAV有统一的AoI要求。设Amax为每架UAV提供现场信息时允许的最大AoI值，有

(4) 能耗模型。本文主要考虑系统中UAV的通信与计算能耗。若UAVi在本地执行计算任务，则相关的能耗为

其中，等号右边第1项为UAV下载应用程序的能耗，第2项为UAV的CPU能耗。ϵi为UAVi的能耗系数，代表 CPU的有效开关电容[20]。若将UAVi的计算任务卸载到MEC服务器，则相关的能耗为

其中，等号右边第1项为UAV上传所采集数据的能耗，第2项中参数ϵs为MEC服务器的CPU能耗系数。最终，处理UAVi计算任务所导致的系统能耗可表示为

参考文献[21]，认为相比于计算输入数据量，计算输出数据量可忽略不计，进而在式(4)-式(5)和式(10)-式(11)中忽略MEC服务器将输出结果回传给UAV以及UAV将输出结果作为现场信息发送至控制中心两个过程所需的时间和能耗。参考文献[13]，本文关注系统中每架UAV的通信与计算能耗，不计及UAV的飞行和悬停能耗。

(5) 资源容量约束。设MEC服务器的存储容量为Cs，有MEC服务器数据存储约束条件

设B为通信带宽总量，有带宽总量约束条件

设F为MEC服务器的计算资源总量，对于所有被卸载的任务有计算资源总量约束条件

3 问题描述与求解方案

3.1 系统优化问题

本文优化目标是最小化所有UAV与MEC服务器的总能耗，即系统能耗。将系统能耗最小化问题记为P1，形式如下。

问题的决策变量是 {ai,bi,fiM}i∈I。P1是一个非凸的混合整数非线性规划(Mixed-Integer NonLinear Programming, MINLP)问题，如果问题规模较大，则很难得到问题的全局最优解[22]。本文求解P1的思路如下：首先采用线性化手段将P1转化为混合整数线性规划(Mixed-Integer Linear Programming, MILP)问题，即用MILP问题来近似原MINLP问题，然后提出一种算法来调节由线性化带来的近似误差，最后使用现有的求解器来求解MILP问题。

3.2 问题转换

首先处理式(8)中的取整操作，定义新的整数变量zi，令

其中，Z+={0,1,2,...}是整数集合。式(19)能够保证整数zi等价于Ti/Δδ」，故可用zi替换原本式(8)中的Ti/Δδ」，得到式(18)。因此，式(18)-式(20)等价于原来的式(8)，且是线性的。

其中，tx,tn分别是的上下界。注意，此时把a当作一个独立变量。线性不等式(21)和式(22)可以保证：当ai=0 时，有ai=0 ；当ai=1时，有ai=。这与原本双线性项的效果一样。因此，可以使用满足式(21)和式(22)的变量ai(独立变量)，来等价替换原本的双线性项ai(两个变量的乘积)。可以用同样的方法来线性化其他双线性项，具体公式省略。

式(23)和式(24)均为线性等式。然后将式(10)和式(11)分别改写为

其中，式(25)和式(26)是线性的，mi为中间变量。进一步将式(27)等效地松弛为

可以设r=1/B，r为一个足够大的数值。计算资源总量约束可改写为

可以设r=1/F，r为一个足够大的数值。通过引入新变量ai}i∈I，转换后的优化问题仍含有非线性函数：式(28)中的 1/(r)2，式(29)中的 1/和式(31)中的1/。接下来参考文献[24]，采用离散化手段，用一组直线函数来近似一个非线性函数。

3.3 离散化

然后使用式(34)、式(35)来近似非线性约束式(31)。

其中，Fi是中间变量。式(34)中含有双线性项air，可采用与式(21)、式(22)类似的方式对其进行等价线性化。类似地，针对f2()=1/()2定义另一个离散点集合 {r}。与式(33)类似，定义经过r,r+1的直线,k+1()，然后使用式(36)来近似非线性约束式(28)。

同样地，针对f3()=1/定义离散点集合 {r}，定义经过,k+1的 直线,k+1()，然后使用式(37)、式(38)来近似非线性约束式(29)。

其中，Bi是中间变量。值得注意的是，被近似的3个函数在其定义域中均为凸函数，过凸函数上任意两点的线段总在该段凸函数的上方，故式(34)-式(38)中的多条直线形成了对原函数的高估(Overestimation)，即式(34)-式(38)高估了资源实际使用量。因此，满足约束(34)-式(38)的解，也满足原本的资源约束式(28)、式(29)、式(31)。

最终，原问题P1被转换为以下问题，记为P2。

表1 P2与P1的关系

3.4 离散点生成算法

在rk ≤r ≤rk+1范围里，始终有lk,k+1(r)≥f(r)。因此，用lk,k+1(r) 来近似f(r)的最大垂直误差是

这是一个凸优化问题，进一步通过分析其KKT条件[25]，可知最优解为

即在点r*处，可得近似误差的最大值Δ*。算法1给出了生成离散点集合R={rk}的具体步骤。

算法的输入参数δ是预设的最大允许误差。在第9, 第13行中可以设置δ0=0.1δ，从而使得实际最大误差Δ*在δ附近且小于等于δ。算法思路如下：最初，离散点集合R中只有1个离散点r1，从第1个点r1开始，找到第2个点r2使得两点之间的Δ*在δ附近，然后再找第3个点r3，使得r2和r3之间的Δ*在δ附近，如此重复，直至达到最后一个点rmax。可见，算法每次生成一个离散点，都能保证最大垂直误差Δ*≤δ，故在最差的情况下，式(34)和式(37)的近似误差为Iδ，式(36)的近似误差为δ。算法只涉及简单代数计算，并采用二分法寻找新点，能够快速获得合适的离散点集合R。仿真中，在δ=0.05下算法1运算时间＜0.01 s。在求解P2之前，只需针对 1/, 1/()2, 1/分别运行算法1各1次即可，然后将生成的离散点代入P2中的约束式(34)、式(36)、式(37)。

算法1 离散点生成算法

4 仿真结果

4.1 仿真设定

考虑系统中有1个MEC服务器和I架UAV，设UAV数量为I=10,20,30。设UAV参数服从给定范围的均匀分布，接收功率Qi ∈[0.4,1] W，发射功率Pi ∈[0.4,1] W, 数据上行和下行参数Xi ∈[1.25,2.5] B，Yi ∈[1.25,2.5] B，计算资源∈[0.5,1] GHz，能耗参数ϵi ∈[1,5]×10-27Ws3，飞行时间τi ∈[5,20] s，数据采集速度si ∈[1,5] MB/s，计算任务参数Ui ∈[1,5] MB，Di ∈[5.5,10] MB，Wi ∈[1,2]×109CPU周期， Δδ=1 s。云端传输速率RM=10 MB/s, MEC服务器缓存容量Cs=6IMB，带宽总量B=4IMHz, MEC服务器计算资源总量F=2IGHz。本文中的优化问题和算法都通过MATLAB和YALMIP来实现。

4.2 计算性能结果

首先比较原非凸MINLP问题P1和MILP问题P2的结果。使用YALMIP内置的求解器BNB来求解P1，设置运算时间上限为1小时。在求解P2之前，先设置最大允许误差δ，通过算法1得到P2中的离散点集合，然后使用求解器GUROBI求解P2。图2给出了不同求解方案下的系统能耗。图中不同的δ值表示本方法在P2中使用了不同的离散点集合，δ值越小，近似误差越小，但离散点数量越多。由本方法的结果可知，UAV数量I越多，计算任务数量越多，系统能耗越高。

图2 不同求解方案下的系统能耗

当I=10，BNB得到的P1全局最优结果是28.42 J，本方法在δ=0.05,0.1,0.2的结果分别是28.67 J, 30.22 J, 32.35 J。可见，δ值越小，本方法的结果越接近全局最优结果。随着UAV数量I增加，P1问题规模增大，BNB无法在1h内得到全局最优。当I=20，BNB得到的P1局部最优结果是61.08 J，本方法在δ=0.05,0.1,0.2的结果分别是57.15 J, 60.24 J, 64.53 J。当I=30，BNB无法在1 h内得到可行解，本方法在δ=0.05,0.1,0.2的结果分别是85.43 J, 90.07 J, 96.55 J。可见，本方法在求解大规模问题方面更有优势，而且减小δ值可以降低本方法对原问题P1的近似误差。

但是，δ值越小，离散点数量越多，这会导致P2中的约束条件数量增多，进而增加求解问题的运算时间。表2给出了不同求解方案的运算时间。运算时间包括两部分：YALMIP导入问题的时间和求解器求解问题的时间。P1是非凸MINLP问题，约束条件数量较小，最花费时间的环节在于求解器搜索全局最优解。当I=10时，大概需要11分钟才能获得P1全局最优解。P2是MILP问题，求解器求解这类问题的速度较快，但随着P2的约束条件数量增多，导入问题的时间和求解问题的时间都会增大。如表2所示，δ值越大，运算时间越短。通过调节δ值，本方法可以在结果准确性和运算时间之间取得较好的平衡。比如，在δ=0.05和I=10的情况下，与全局最优解对比，本方法的能耗增加了0.88%，但运算时间降低了约98%。

表2 不同求解方案的运算时间

本方法采用的近似手段是对原非线性函数的高估，即使δ值较大，P2的近似误差较大，但P2的解仍然是原问题P1的可行解，并不违反带宽和计算资源上限约束条件。因此，可以在允许的最大误差内尽可能提高δ值。简单起见，仿真时所有非线性函数使用同一个δ值。实际上可采用不同的值。假如允许的最大带宽误差为 ΔB，则相应的δ值可设为 ΔB/I。假如允许的最大计算资源误差为 ΔF，则相应的δ值可设为ΔF/I。

4.3 系统决策结果

接下来，考虑本方法在δ=0.05和I=10情况下的决策结果。本文的优化目标是最小化系统能耗，所以MEC服务器CPU能耗系数ϵs的大小对系统决策的影响较大。从图3可以看出，ϵs值越小，系统能耗越小。图中横坐标表示控制中心设定的信息年龄AoI上限Amax。如图所示，Amax值越大，系统能耗越低。这是因为较大的AoI上限可以降低UAV和MEC服务器的计算资源使用量，进而降低CPU能耗。

图3 不同能耗系数 ϵs 与不同信息年龄上限 A max下的系统能耗

图4给出了在不同情况下从UAV卸载到MEC服务器的计算任务数量。在Amax=3的情况下，MEC服务器的任务数量都是4。这意味着，当AoI上限Amax较小时，系统优化空间较小，不论MEC能耗系数ϵs是多大，计算卸载的决策都不变。但随着Amax的提高，系统优化空间增大，不同的ϵs会导致不同的计算卸载决策。如果MEC服务器能耗系数ϵs较小，如ϵs=5，那么系统会增加在MEC服务器上执行的计算任务数量。如果MEC服务器能耗系数ϵs较大，如ϵs=10,15，系统趋向于在UAV上完成计算任务，所以MEC服务器的任务数量较少。

图4 不同能耗系数 ϵs 与不同信息年龄上限 A max下在MEC服务器上执行的计算任务数量

5 结束语

本文考虑UAV交通监测与MEC技术结合的智能交通系统，研究UAV到达现场执行交通监测任务过程中的任务卸载、通信与计算资源分配联合决策问题，尤其考虑多架UAV进行数据收集与处理的AoI约束条件，并由MEC服务器提供缓存辅助边缘计算。本文旨在最小化系统能耗，把优化问题构造为非凸的MINLP问题，进一步采用线性化手段并设计算法来高效求解问题。仿真结果验证了所提方法在不同UAV任务条件下的有效性和优越性。