研究关于物联网边缘计算中的卸载策略

摘要

针对物联网边缘计算中的任务卸载策略与性能优化问题，本文研究了如何有效卸载应用，以实现卸载成本与系统性能之间的权衡。考虑到边缘服务器的区域优势以及远程云计算中心丰富的资源，本文构建了一个以卸载成本为优化目标、队列稳定性为约束条件的优化模型，并提出了一种基于李雅普诺夫优化的漂移加成本计算卸载策略（DCCO）。该策略将优化问题分解为一系列子问题，根据当前队列积压和卸载目标节点的情况分配任务，从而满足用户的优化目标并保证系统的稳定性。
仿真结果表明，该算法有效降低了任务卸载成本以及队列积压的增长。

关键词 -物联网；边缘计算；卸载策略；李雅普诺夫优化

一、引言

随着万物互联和大数据时代的到来，物联网设备数量和数据流量呈现指数增长。预计到2021年，物联网设备数量将从80亿增长至120亿，移动数据流量将达到每月49艾字节。对于海量数据的实时传输和处理需求日益增多。许多物联网应用，如车联网、图像识别、虚拟现实[1]，属于计算密集型和延迟敏感[2]应用。然而，物联网设备资源有限[3]。目前，物联网设备与云的结合是主要的应用模式。但在物联网设备与远程云平台之间的远距离通信中存在较长的网络延迟，且数据传输的海量数据还消耗大量网络带宽资源，导致网络拥塞[4]。

为了应对这一挑战，边缘计算范式应运而生。边缘计算能够有效解决传统云计算的不足，提供类似于远程云中心的计算和存储能力，在网络边缘将物联网设备上的计算任务有效地卸载到附近的边缘服务器，并获得更好的服务[5]。边缘设备（如无线接入点、边缘路由器[7]等）部署在用户附近，但与远程云中心相比，边缘设备的物理资源有限，因此如何在用户设备、边缘设备和远程云计算平台中部署应用，并设计合理的计算卸载方案是一个重要的挑战。

近年来，研究人员开展了边缘计算中卸载策略的研究。参考文献[8]提出了一种以时间延迟为约束的离线计算卸载策略，并采用马尔可夫决策过程以最小化能耗。参考文献[9]提出了一种基于拉格朗日的优化策略，用于计算密集型应用的迁移能耗，以减少终端计算时间和能耗。在[10]中研究了边缘计算系统的成本延迟权衡，并提出了一种双边优化算法。在[11]中使用博弈算法和匈牙利算法相互迭代以优化资源分配。在[12]中提出了一种OREO在线优化算法，通过动态优化服务器缓存和任务卸载并利用李雅普诺夫优化算法，解决了系统状态未知、空间需求耦合以及去中心化协调的问题。在[13]中针对在线优化，提出了一种基于李雅普诺夫优化理论的任务调度算法JOSA，该算法仅使用当前时隙的系统信息进行调度。

目前，大多数关于任务卸载策略的研究集中在边缘计算系统中的任务调度，主要考虑能耗、延迟、传输信道等性能方面，忽略了任务卸载成本与系统性能之间的平衡。由于目标节点的计算能力不同，任务生成和分布的过程高度动态，可能导致队列积压并影响系统的稳定性。为了解决这些问题，本文提出了一种基于边缘设备和远程云的在线决策策略（DCCO），以适应外部环境的变化。在该策略中，首先对物联网设备‐边缘节点‐云服务器系统进行数学建模，包括任务队列、卸载成本等；然后构建优化模型，以优化任务卸载成本为目标，以队列稳定性为约束；基于李雅普诺夫稳定性理论，在每个时隙选择卸载策略以最小化当前漂移加成本函数的上界，从而在长时间范围内降低平均卸载成本，并确保系统处于低拥塞状态。
最后，仿真结果表明，DCCO可以通过控制参数V在卸载成本和系统性能之间取得权衡，同时优化卸载成本并降低处理延迟。

II. SYSTEM MODEL AND PROBLEM MODELING

A. 系统模型

图1展示了系统架构。用户部署多个物联网设备，这些设备随机生成计算任务，并将任务卸载至边缘服务器或云服务器进行执行。边缘节点由有限计算、存储资源和通信设备组成。边缘服务器和云服务器接收来自用户的请求并进行处理，最后将处理结果返回给用户。
该系统包含m个用户设备和n个具有不同处理能力的边缘服务器。假设云计算系统拥有无限计算资源。I表示由物联网设备随机生成的应用i的集合，J表示服务器j的集合。

在时隙t中，第i个应用卸载到服务器j的任务数量为$ m_{ij}(t) $。其中，$ m_{ij}(t) $是决策变量。令$ j = 1, …, n $表示边缘服务器，$ j = n+1 $表示远程云。$ i \in I $，在时隙t内卸载到服务器的总任务数为$ M_i(t) $：
$$
M_i(t) = \sum_{j=1}^{n} m_{ij}(t) + m_{i,n+1}(t) \tag{1}
$$

大量并发应用被迁移到边缘服务器上执行，其中部分计算任务必须排队等待[14]。根据任务卸载请求的到达过程，本文建立了卸载队列模型。在时隙t内，边缘服务器j对应用i的处理能力为$ r_{ij}(t) $，在服务器j上等待服务的应用i的队列积压为$ Q_{ij}(t) $。则队列积压在相邻时隙之间的动态关系如下：
$$
Q_{ij}(t+1) = \max\left(Q_{ij}(t) + m_{ij}(t) - r_{ij}(t), 0\right) \tag{2}
$$

系统的稳定性条件如下：
$$
\lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \sum_{i \in I} \sum_{j \in J} Q_{ij}(t) < \infty \tag{3}
$$

B. 问题建模

对于系统而言，将部分任务卸载到边缘服务器和远程云会产生传输带宽成本和计算成本，而将任务卸载到远程云产生的卸载成本更高。设任务卸载到移动边缘计算的成本函数为$ U_i \cdot x $，其中$ U_i(t) $是移动边缘计算到应用i的单位卸载成本，远程云的成本函数为$ J \cdot U_i \cdot x $，其中$ J > 1 $。

应用i在时隙t的卸载成本表示为：
$$
A_i(t) = \sum_{j=1}^{n} U_i(t) \cdot m_{ij}(t) + J \cdot U_i(t) \cdot m_{i,n+1}(t) \tag{4}
$$

接下来，构建成本目标函数，其表达式为：
$$
G = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \sum_{i \in I} A_i(t) \tag{5}
$$

根据上述分析，目标函数是最小化平均任务卸载成本，队列稳定性为约束。将计算卸载问题转化为：
$$
\min: G = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \sum_{i \in I} A_i(t) \tag{6}
$$
约束在(1)和(3)中表示。

III. DCCO 策略

A. 问题转换

接下来，提出了一种基于李雅普诺夫优化的在线算法[15]来求解随机优化问题。在每个时隙中，我们只需求解一个确定性优化问题，而无需知晓任务的随机到达情况。
首先，队列的稳态通过队列积压$ Q_{ij}(t) $来反映。令$ W(t) = [Q_{ij}(t)] $表示任务队列积压矩阵，并构造李雅普诺夫函数$ L(W(t)) $。其定义如下：
$$
L(W(t)) = \frac{1}{2} \sum_{i \in I} \sum_{j \in J} Q_{ij}^2(t) \tag{7}
$$

李雅普诺夫漂移函数的变化$ \Delta L(W(t)) $可以定义为：
$$
\Delta L(W(t)) = \mathbb{E}[L(W(t+1)) - L(W(t)) | W(t)] \tag{8}
$$

根据(2)队列积压的动态关系，我们可以得到：
$$
Q_{ij}^2(t+1) \leq Q_{ij}^2(t) + m_{ij}^2(t) + r_{ij}^2(t) + 2Q_{ij}(t)(m_{ij}(t) - r_{ij}(t))
$$

将上述不等式和(7)代入(8)并进行简化后，得到以下结果：
$$
\mathbb{E}[\Delta L(W(t)) | W(t)] \leq B + \sum_{i \in I} \sum_{j \in J} Q_{ij}(t) \mathbb{E}[m_{ij}(t) - r_{ij}(t) | W(t)]
$$
其中，
$$
B = \frac{1}{2} \sum_{i \in I} \sum_{j \in J} (\max M_i^2 + \max r_{ij}^2)
$$

为了最小化平均卸载成本G，将与控制参数V相关的期望卸载成本添加到李雅普诺夫漂移函数中。定义李雅普诺夫漂移加成本函数为：
$$
\Delta L(W(t)) + V \cdot \mathbb{E}[A(t) | W(t)]
$$
其上界满足：
$$
\mathbb{E}[\Delta L(W(t)) + V \cdot A(t) | W(t)] \leq B + V \cdot \sum_{i \in I} \sum_{j=1}^{n} U_i(t) m_{ij}(t) + V \cdot J \cdot U_i(t) m_{i,n+1}(t) + \sum_{i \in I} \sum_{j \in J} Q_{ij}(t) (m_{ij}(t) - r_{ij}(t))
$$
V是一个用于权衡目标函数最优性和队列稳定性的非负常数。

B. 在线算法

我们提出了一种DCCO算法，通过最小化（13）中漂移加成本函数的上界来求解每个时隙的最优卸载决策。
（13）中与卸载计算相关的变量是$ m_{ij}(t) $。给定B和$ r_{ij}(t) $，最小上界问题可以分解为一系列子问题来求解：
$$
\min \sum_{j=1}^{n} Q_{ij}(t) m_{ij}(t) + Q_{i,n+1}(t) m_{i,n+1}(t) + V \cdot U_i(t) \sum_{j=1}^{n} m_{ij}(t) + V \cdot J \cdot U_i(t) m_{i,n+1}(t)
$$
约束在(1)中表示。

由于不同应用的卸载决策相互独立，最小化问题可以解耦为一个分布式优化问题，以求解每个应用的卸载决策。方程(14)被转化为一个0‐1整数规划问题来获得卸载决策，$ m_{ij}(t) $可通过以下方式获得：
$$
m_{ij}(t) =
\begin{cases}
1, & \text{if } j = \arg\min_{j \in {1,2,…,n}} {Q_{ij}(t) + V \cdot U_i(t)} \
0, & \text{otherwise}
\end{cases}
\tag{14}
$$
$ m_{ij}(t)=1 $，表示将任务卸载到边缘端执行。相反，在云中执行。

DCCO算法的实现如下：
步骤1：创建用户卸载任务请求，获取任务卸载队列，任务等待队列初始化；
步骤2：在每个时隙内，根据(4)计算任务卸载的成本；
步骤3：通过求解0‐1整数规划问题的(13)和(14)，得到当前时隙的卸载决策$ m_{ij}(t) $；
步骤4：结合上述步骤的结果，根据公式(2)更新任务队列长度$ Q_{ij}(t) $。

第四节 仿真评估

A. 仿真环境

本文使用MATLAB仿真平台评估所提出的DCCO算法的性能。主要参数如下：用户设备数量N=10，物联网设备CPU的工作频率为1.0GHz，用户任务卸载请求的到达过程建模为服从参数 λi=50 Mbit/s的泊松分布。
边缘服务器中的虚拟机CPU设置为1.5GHz单核，边缘服务器的计算能力设置为10GHz，远程云服务器的计算能力设置为θi=100GHz。本实验采用综合数据来衡量卸载成本，并执行3600个时间片。

B. 结果分析

本节将本文提出的DCCO算法与其它类似的计算卸载算法进行比较，即OREO算法[11]和JOSA算法[12]。实验仿真从任务卸载成本和队列积压两个方面展开。从图2和图3可以直观看出：随着V的增加，卸载成本逐渐降低，而系统队列积压逐渐增加。这是因为V越高，系统对目标函数的要求越高，相应地会将更多任务卸载到移动边缘计算（MEC）以降低总卸载成本。可以看出，队列积压在初期趋于增大，当控制参数V超过4000后趋于稳定。其中，DCCO和OREO的队列积压增长较慢，且卸载成本较低。

选择合适的控制参数V对于平衡优化目标和队列稳定性具有重要意义。通过仿真，对两种算法进行了权衡。
图4中，OREO算法的拐点为V=1800，卸载成本为180.67，队列积压为341.04。图5展示了本文提出的DCCO算法，选择控制参数V=2000作为最优控制阈值，其卸载成本为115.62，队列积压为256.51。结果表明，与OREO算法相比，DCCO算法节省了36%的卸载成本和24.79%的网络延迟。总体而言，DCCO算法在维持队列稳定性和优化卸载成本方面表现更优。

V. 结论

本文研究了如何降低物联网边缘计算中任务卸载的成本，以及如何平衡任务卸载成本与队列积压。提出了一种在线DCCO计算卸载算法，该算法能够根据外部环境的变化做出卸载决策，在保证性能的同时最小化卸载成本。仿真结果表明，DCCO能够较好地控制卸载成本和队列积压。本文所研究的计算任务被视为相互独立且同等重要，下一步将考虑优先级敏感任务之间的计算卸载策略。