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 \in {{I}}$。为防止UAV之间的通信干扰，UAV与基站之间无线通信采用正交频分多址接入技术^[17]，信道功率增益采用自由空间路径损耗模型^[18]。定义从基站到UAV $i$的数据下行速率为

其中，${b_i}$为分配给UAV $i$的通信带宽，${d_i}$为UAV $i$在观察点与基站的通信距离，${g_i}$为1 m基准距离的信道增益，$\alpha$为信道衰落指数(一般取2)，${Q_i}$为UAV $i$的接收功率，${N_0}$为噪声功率。设式(1)中对数函数所包含的均为常数，使用常数${Y_i}$替代对数部分。定义从UAV $i$到基站的数据上行速率为

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

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

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

其中，等号右边第1项${\tau _i}$为UAV前往观察点的用时；第2项为UAV采集指定数据量${D_i}$的用时，${s_i}$为数据采集速率；第3项为UAV下载指定应用程序的用时，${U_i}$为所请求的应用程序的数据量，${c_i} = 1$表示应用程序${U_i}$已缓存在MEC服务器，${c_i} = 0$表示当前MEC服务器没有缓存${U_i}$，需要从云端获取${U_i}$，${R^M}$是云端到MEC服务器的数据传输速率；最后一项为UAV的CPU计算时间，$f_i^L$为UAV $i$的本地计算资源，${W_i}$为处理数据${D_i}$所需的CPU周期数。类似的，若将UAV计算任务卸载到MEC服务器，则UAV $i$的总时间花费为

其中，$f_i^M$是MEC服务器分配给UAV $i$任务的计算资源。最终，UAV $i$的总时间花费可表示为

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

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

其中，$\left\lfloor \cdot \right\rfloor$表示向下取整。控制中心对所有UAV有统一的AoI要求。设${A^{\max }}$为每架UAV提供现场信息时允许的最大AoI值，有

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

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

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

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

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

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

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

3.   问题描述与求解方案

3.1   系统优化问题

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

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

3.2   问题转换

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

其中，${{\boldsymbol{Z}}^ + } = \{ 0,1,2, \cdots \}$是整数集合。式(19)能够保证整数${z_i}$等价于$\left\lfloor {{T_i}/\Delta \delta } \right\rfloor$，故可用${z_i}$替换原本式(8)中的$\left\lfloor {{T_i}/\Delta \delta } \right\rfloor$，得到式(18)。因此，式(18)–式(20)等价于原来的式(8)，且是线性的。

式(6)和式(12)含有非凸的双线性项${a_i}t_i^L,{a_i}t_i^M,$ ${a_i}e_i^L,{a_i}e_i^M$，它们都是一个0-1变量和一个连续变量的乘积，可以采用凸包络方法^[23]来线性化这种双线性项。以双线性项${a_i}t_i^L$为例，可将其等价地线性化为

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

接下来引入新变量$r_i^b$和$r_i^M$，来分别替换原本的$1/{b_i}$和$1/f_i^M$，即$r_i^b = 1/{b_i}$和$r_i^M = 1/f_i^M$。因此，可将式(4)和式(5)分别改写为

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

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

因为原问题P1最小化能耗，所以最优的$e_i^M$值会尽可能的小。由式(26)可知，最优的${m_i}$值也会尽可能的小。式(28)规定了${m_i}$的下界为$1/{(r_i^M)^2}$，最优的${m_i}$值会等于$1/{(r_i^M)^2}$。所以，可用式(28)等价替换式(27)。带宽总量约束可改写为

可以设$r_{\min }^b = 1/B$，$r_{\max }^b$为一个足够大的数值。计算资源总量约束可改写为

可以设$r_{\min }^M = 1/F$，$r_{\max }^M$为一个足够大的数值。通过引入新变量$\{ {z_i},r_i^b,r_i^M,{m_i},{a_i}t_i^L,{a_i}t_i^M,{a_i}e_i^L, {a_i}e_i^M\} _{i \in {{I}}}$，转换后的优化问题仍含有非线性函数：式(28)中的$1/{(r_i^M)^2}$，式(29)中的$1/r_i^b$和式(31)中的$1/r_i^M$。接下来参考文献[24]，采用离散化手段，用一组直线函数来近似一个非线性函数。

3.3   离散化

先以$1/r_i^M$为例，令${f_1}(r_i^M) = 1/r_i^M$。离散化取值范围是$[r_{\min }^M,r_{\max }^M]$，定义离散点集合$\{ r_{i,k}^M\} _{k = 1}^{{K_1}}$，其中${K_1}$是离散点的个数，且$r_{\min }^M = r_{i,1}^M < \cdots < r_{i,{K_1}}^M = r_{\max }^M$。任取两个相邻的离散点$r_{i,k}^M, r_{i,k + 1}^M$，经过这两点定义一条直线

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

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

同样地，针对${f_3}(r_i^b) = 1/r_i^b$定义离散点集合$\{ r_{i,k}^b\} _{k = 1}^{{K_3}}$，定义经过$r_{i,k}^b,r_{i,k + 1}^b$的直线$l_{k,k + 1}^3(r_i^b)$，然后使用式(37)、式(38)来近似非线性约束式(29)。

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

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

决策变量有$\{ {a_i},r_i^b,r_i^M,{m_i},{a_i}t_i^L,{a_i}t_i^M,{a_i}e_i^L,{a_i}e_i^M, {a_i}r_i^M\} _{i \in {{I}}}$，完整的约束条件应该还包括线性化双线性项${a_i}t_i^M,{a_i}e_i^L,$ ${a_i}e_i^M,{a_i}r_i^M$的不等式以及$l_{k,k + 1}^2(r_i^M), l_{k,k + 1}^3(r_i^b)$的表达式。P2是一个MILP问题，可使用现有的求解器来求解。表1总结了从P1到P2的7个转化操作。前5个操作是等价转化，后3个操作是近似等价转化，因此P2是P1的近似，存在近似误差。误差来源于后3个操作中对非线性函数$1/r_i^M$, $1/{(r_i^M)^2}$, $1/r_i^b$的线性化，误差的大小决定于离散点的数量和位置。若离散点越多、越密集，则近似误差越小。接下来，本文提出一种离散点生成算法，可根据预设的最大允许误差来生成离散点，允许调节P2的近似误差。

表 1  P2与P1的关系

P2中的新变量和新函数	与原问题P1的关系
整数变量${z_i}$	用于等价线性化AoI等式(8)，见式(18)–式(20)
连续变量${a_i}t_i^L,{a_i}t_i^M,{a_i}e_i^L,{a_i}e_i^M,{a_i}r_i^M$	用于定义凸包络，精确松弛5个双线性项${a_i}t_i^L,{a_i}t_i^M,{a_i}e_i^L,{a_i}e_i^M,{a_i}r_i^M$，见式(21)、式(22)
连续变量$r_i^b,r_i^M$	用于等价替换$1/{b_i}$，$1/f_i^M$，见式(23)–式(27)
连续变量${m_i}$	用于等价松弛式(27)，见式(28)
直线函数$l_{k,k + 1}^1(r_i^M)$和连续变量${F_i}$	用于近似函数$1/r_i^M$，见式(33)–式(35)
直线函数$l_{k,k + 1}^2(r_i^M)$	用于近似函数$1/{(r_i^M)^2}$，见式(36)
直线函数$l_{k,k + 1}^3(r_i^b)$和连续变量${B_i}$	用于近似函数$1/r_i^b$，见式(37)、式(38)

下载: 导出CSV 

| 显示表格

3.4   离散点生成算法

函数$1/r_i^M$, $1/{(r_i^M)^2}$, $1/r_i^b$在正实数轴上都是凸函数，因此可以利用凸函数的性质来生成离散点。用$f(r)$表示一个凸函数，其中$r$满足$0 < {r_{\min }} \le r \le {r_{\max }}$。定义离散点集合$R = \{ {r_k}\} _{k = 1}^K$，有${r_{\min }} = {r_1} < \cdots < {r_K} = {r_{\max }}$。经过两点${r_k},{r_{k + 1}}$定义直线

在${r_k} \le r \le {r_{k + 1}}$范围里，始终有${l_{k,k + 1}}(r) \ge f(r)$。因此，用${l_{k,k + 1}}(r)$来近似$f(r)$的最大垂直误差是

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

即在点${r^*}$处，可得近似误差的最大值${\varDelta ^*}$。算法1给出了生成离散点集合$R = \{ {r_k}\} _{k = 1}^K$的具体步骤。

算法1 离散点生成算法
输入：$\delta$, $f(r)$, $r \in [{r_{\min }},{r_{\max }}]$, ${r_1} = {r_{\min }}$, $R = \{ {r_1}\}$, $i = 1$
输出：$R$
1. Repeat
2. 　令${r_L} = {r_i}$, ${r_R} = {r_{\max }}$, $E = \{ {r_L},{r_R}\}$
3. 　Repeat
4. 　　${r^*} = {f'^{ - 1}}\left( {\frac{{f({r_R}) - f({r_L})}}{{{r_R} - {r_L}}}} \right)$
5. 　　${\varDelta ^*} = {l_{L,R}}({r^*}) - f({r^*})$
6. 　　获得$\ell$，使得$E$中第$\ell$个元素${E_\ell } = {r_R}$
7. 　　If ${\varDelta ^*} > \delta$ Then
8. 　　${r_R} \leftarrow ({E_\ell } + {E_{\ell - 1}})/2$, $E \leftarrow E \cup \{ {r_R}\}$
9. 　　ElseIf ${\varDelta ^*} < \delta - {\delta _0}$ Then
10. 　　${r_R} \leftarrow ({E_\ell } + {E_{\ell + 1}})/2$, $E \leftarrow E \cup \{ {r_R}\}$
11. 　 EndIf
12. 　　对$E = \{ {E_1},{E_2}, \cdots \}$排序，使得${E_1} < {E_2} < \cdots$
13. 　Until $\delta - {\delta _0} \le {\varDelta ^*} \le \delta$
14. 　$R \leftarrow R \cup \{ {r_R}\}$, $i \leftarrow i + 1$
15. Until ${r_R} = {r_{\max }}$

下载: 导出CSV 

| 显示表格

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

4.   仿真结果

4.1   仿真设定

考虑系统中有1个MEC服务器和$I$架UAV，设UAV数量为$I = 10,20,30$。设UAV参数服从给定范围的均匀分布，接收功率${Q_i} \in [0.4,1]$ W，发射功率 ${P_i} \in [0.4,1]$ W, 数据上行和下行参数${X_i} \in [1.25,2.5]$ B，${Y_i} \in [1.25,2.5]$ B，计算资源$f_i^L \in [0.5,1]$ GHz，能耗参数${\epsilon}_{i}\in [1,5]\times {10}^{-27}$ Ws³，飞行时间${\tau _i} \in [5,20]$ s，数据采集速度${s_i} \in [1,5]$ MB/s，计算任务参数${U_i} \in [1,5]$ MB，${D_i} \in [5.5,10]$ MB，${W_i} \in [1,2] \times {10^9}$CPU周期，$\Delta \delta = 1$ s。云端传输速率${R^M} = 10$ MB/s, MEC服务器缓存容量${C_s} = 6I$ MB，带宽总量$B = 4I$ MHz, MEC服务器计算资源总量$F = 2I$ GHz。本文中的优化问题和算法都通过MATLAB和YALMIP来实现。

4.2   计算性能结果

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

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

下载: 全尺寸图片 幻灯片

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

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

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

UAV	求解器	本方法
数量	BNB(1 h)	δ=0.05	δ=0.1	δ=0.2
I=10	11 min	9 s	5 s	4 s
I=20	1 h	28 s	17 s	10 s
I=30	1 h	78 s	50 s	31 s

下载: 导出CSV 

| 显示表格

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

4.3   系统决策结果

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

图 3  不同能耗系数${\epsilon}_{{\mathrm{s}}}$与不同信息年龄上限${A^{\max }}$下的系统能耗

下载: 全尺寸图片 幻灯片

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

图 4  不同能耗系数${\epsilon}_{{\mathrm{s}}}$与不同信息年龄上限${A^{\max }}$下在MEC服务器上执行的计算任务数量

下载: 全尺寸图片 幻灯片

5.   结束语

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