车联网中基于改进麻雀搜索算法的任务卸载优化策略

Optimization Strategy for Task Offloading in Internet of Vehicles Based on Improved Sparrow Search Algorithm

摘要: 车联网中计算密集型任务对车辆计算能量消耗和网络延迟提出了更高要求。本文提出一种基于改进的麻雀搜索算法(ISSA)的低延迟低能耗的任务卸载优化策略，以应对车联网动态性、异构性和资源受限的挑战。该方法综合考虑任务特性、网络状态和计算资源，建立以最小化延迟、能耗为目标的优化模型，并设计改进的麻雀搜索算法选择最优的卸载策略。仿真结果表明，该方法能有效降低任务处理延迟和能耗，提高资源利用率，为车联网密集型的应用提供支持。

Abstract: The computation-intensive tasks in the Internet of Vehicles (IoV) impose higher demands on vehicle computing energy consumption and network latency. This paper proposes a low-latency, low-energy task offloading optimization strategy based on an improved Sparrow Search Algorithm-GA-SSA to address the challenges of dynamicity, heterogeneity, and resource constraints in IoV. The method comprehensively considers task characteristics, network state, and computational resources to establish an optimization model aimed at minimizing delay and energy consumption, and designs an improved Sparrow Search Algorithm to select the optimal offloading strategy. Simulation results show that this method can effectively reduce task processing delay and energy consumption, improve resource utilization, and support intensive applications in IoV.

1. 引言

随着无线网络技术和边缘计算的发展，智慧交通系统开始初露头角，如无人驾驶、智慧车载系统、人车对话等。智慧交通系统可通过实时收集和分析交通数据为交管部门提供决策支持，同时也为用户提供安全可靠的智能交通服务[1]。而车联网(Internet of Vehicles, IoV)是智慧交通系统核心，为服务提供商实时收集上传数据，分析车辆当前速度、周围环境等，从而为车辆提供导航和自动驾驶等时延敏感型和计算密集型服务功能提供依据[2] [3]。然而服务过程需要提供大量的实时数据并计算分析。同时车载应用软件的数量规模也海量增长，因此，如何在满足车辆计算服务前提下，快速高效处理海量实时数据，是当前车联网发展继续解决的问题。

在车联网环境下由于车辆自身的计算资源有限，可能会造成无法实时完成计算任务，从而造成车辆导航和自动驾驶等服务延迟过长而导致失败的结果[4]。此外，云服务器距离车辆距离较远，在传输过程中容易造成时延增长，服务质量下降。所以基于边缘服务器的特征，在云服务器和车辆之间部署边缘服务器，能够给车辆用户提供存储和计算资源[5]。车辆用户可以根据当前上下文环境选择将部分的任务卸载到附近的边缘服务器上，从而缓解网络拥塞情况，并且能降低服务延迟[6]。

虽然移动边缘计算提高了车联网的服务响应性能，然而在车联网边缘环境下的任务卸载过程仍存在许多挑战和问题[7]。一是因为边缘服务器的计算能力和存储资源有限，不能在有限时间内处理大量的车辆卸载的任务。二是因为当前车联网环境复杂多变，车辆位置不断变化，而用户服务需求也动态变化，故使得任务卸载问题更加复杂。因此车联网环境下的车辆任务卸载策略问题的研究是当前热点问题。本文主要针对基于多用户车辆的任务卸载场景下的卸载策略问题进行分析研究。

2. 系统建模

2.1. 任务卸载模型

在车辆网场景中，主要包含车辆、路边单元(RSU)、移动边缘计算服务器组成，而一个路边单元和一个MEC服务器相连。为了描述方便，后面称为边缘节点。假设在m区域内，有多个用户车辆在行驶，该区域内部署m个边缘节点，分别记为$\text{ES}=\left\{{\text{ES}}_1,{\text{ES}}_2,\cdots ,{\text{ES}}_m\right\}$ ，在某个时间段内，假设当前有n辆车在道路上行驶，记为$\text{V}=\left\{{\text{V}}_1,{\text{V}}_2,\cdots ,{\text{V}}_n\right\}$ ，当前车辆${\text{V}}_i$ ($i\in (1,n)$ )最近的边缘节点为${\text{ES}}_k$ ($k\in \left(1,m\right)$ )，假设该边缘节点上的计算能力能够满足周边车辆卸载来的计算任务，每辆车上都有L个任务需要计算执行，记为$T_i=\left\{T_{i1},T_{i2},\cdots ,T_i{}_l\right\}$ ，每辆车的每个任务用$T_{ij}=\left\{D_{ij},T_{ij}^{\max }\right\}$ 二元组表示，分别表示任务数据大小和任务能接受的最大时间延迟。

本文研究目标是n辆车在某个区域内行驶过程中，找到一个最优的任务卸载策略方案$X=\left\{X_1,X_2,\cdots X_n\right\}$ ，其中$X_i=\left\{x_{i1},x_{i2},\cdots ,x_{il}\right\}$ ，$i\in \left(1,n\right)$ ，使得所有车辆在当前m个区域内的任务延迟和能耗的效应值最小。其中$x_{ij}\in \left\{0,1\right\}$ ，表示车辆$i$ 上任务${\text{T}}_{ij}$ 卸载的位置。其中$x_{ij}=0$ 表示任务${\text{T}}_{ij}$ 在本地车辆上计算，反之则表示任务${\text{T}}_{ij}$ 卸载到边缘服务器上。

2.2. 延迟计算模型

车辆${\text{V}}_i$ 在行驶过程中，如果是计算密集型的小型任务直接在本地执行，如果车辆${\text{V}}_i$ 上的任务数量较多，且计算量大，则需要把部分任务卸载边缘服务器上$E{S}_k$ 进行计算。这里定义一个二进制变量$x_{ij}$ 表示是否在本地计算，若在本地计算则为1，否则为0。

假设边缘节点$E{S}_k$ ($k\in \left(1,m\right)$ )中的各个虚拟机计算性能一致，其中边缘节点的处理能力记为$E{f}_k$ 。车辆的处理能力为$V{f}_i$ ，$D_{ij}$ 表示数据大小。若任务${\text{T}}_{ij}$ 在本地计算，则延迟计算如下：

${\text{TT}}_{ij}=x_{ij}\times \frac{D_{ij}}{V{f}_i}$ (1)

若任务卸载到边缘节点$E{S}_k$ 上时，任务延迟包含从车辆到边缘节点$E{S}_k$ 上的传输延迟、在边缘节点$E{S}_k$ 上的计算延迟、计算结果从边缘节点上返回到车辆终端[8]。假设从车辆到边缘节点$E{S}_k$ 上的传输速率为$B_{v2e}^k$ ，边缘节点$E{S}_k$ 计算能力为$E{f}_k$ ，${D^{\prime }}_{ij}$ 表示返回结果数据大小。则任务${\text{T}}_{ij}$ 的延迟${\text{TT}}_{ij}$ 计算如下：

${\text{TT}}_{ij}=\left(1-x_{ij}\right)\times \left(\frac{D_{ij}}{B_{v2e}^k}+\frac{D_{ij}}{E{f}_k}+\frac{{D^{\prime }}_{ij}}{B_{v2e}^k}\right)$ (2)

车辆${\text{V}}_i$ 上所有任务的延迟时间为

${\text{TT}}_{ij}=\{\begin{array}{l}{x}_{ij}\times \frac{D_{ij}}{V{f}_i}\\ \left(1-x_{ij}\right)\times \left(\frac{D_{ij}}{B_{v2e}^k}+\frac{D_{ij}}{E{f}_k}+\frac{{D^{\prime }}_{ij}}{B_{v2e}^k}\right)\end{array}$ (3)

2.3. 能耗计算模型

车辆${\text{V}}_i$ 在行驶过程中，若任务${\text{T}}_{ij}$ 在当前边缘服务器上运行，则在本地消耗的能耗计算如下：

$T{E}_{ij}=\frac{D_{ij}}{V{f}_i}\times PV{C}_i$ (4)

若任务计算量较大，需要卸载到边缘服务${\text{V}}_i$ 上进行计算，则该任务能耗计算如下：

${\text{TE}}_{ij}=\left(\frac{D_{ij}}{B_{v2e}^k}\times PV{T}_i+\frac{D_{ij}}{E{f}_k}\times PE{C}_k+\frac{{D^{\prime }}_{ij}}{B_{v2e}^k}\times PE{R}_k\right)$ (5)

其中$PV{C}_i$ 、$PV{T}_i$ 、$PE{C}_k$ 和$PE{R}_k$ 分别表示车辆$i$ 的计算功率，车辆$i$ 的传输功率，边缘服务器$k$ 的计算功率和传输功率。则

车辆${\text{V}}_i$ 上每个任务计算能耗公式如下：

${\text{TE}}_{ij}=\{\begin{array}{l}{x}_{ij}\times \frac{D_{ij}}{V{f}_i}\times PV{C}_i\\ \left(1-x_{ij}\right)\times \left(\frac{D_{ij}}{B_{v2e}^k}\times PV{T}_i+\frac{D_{ij}}{E{f}_k}\times PE{C}_k+\frac{{D^{\prime }}_{ij}}{B_{v2e}^k}\times PE{R}_k\right)\end{array}$ (6)

当前区域内所有车辆任务计算时延和消耗的能耗分别是：

$T={\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{l}T{T}_{ij}}}}$ (7)

$E={\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{l}T{E}_{ij}}}}$ (8)

本文将任务卸载过程抽象为一个多目标优化问题，同时考虑任务完成的时间和能耗。最小化系统中的时间延迟和能耗的多目标优化函数为：

min $T$ ，min$E$ (9)

$s.tT{T}_{ij}<T_{ij}^{\max }$ $\forall i=1,2,\mathrm{...},n$ , $\forall j=1,2,\mathrm{...},l$ (10)

2.4. 适应度函数

任务卸载过程需要考虑当前场景中的延迟和能耗，为了简化计算过程，将公式9转换成单目标优化函数，具体如下。

$\min f=\left(w_1\ast T+w_2\ast E\right)$ (11)

当前场景中的问题就转换成一个单目标优化问题，即在时间最大约束下，每个任务执行的延迟和能耗的效应总和最小。针对该问题，本课题采用了改进的麻雀搜索算法进行问题的求解。其中$w_1$ 和$w_2$ 分别表示延迟和能耗在效应函数值中所占权重比例。

3. 算法设计

麻雀搜索算法(SSA)是一种新型的群智能优化算法，其参数少、收敛速度块，寻优能力较强。但SSA容易陷入局部最优解，具有早熟收敛、参数敏感、动态适应性不足问题。而遗传算法(GA)全局搜索能力较强，本文将GA算法和麻雀搜索算法的优点结合起来，提出了一种改进的麻雀算法(GA-SSA)来解决车联网中的任务卸载策略优化问题。GA-SSA算法首先在初始化阶段用GA生成高质量初始种群(迭代次数为5~10次)，并根据种群的多样性来自适应调整发现者数量。然后在麻雀位置更新过程中，引入自适应权重因子，动态调整麻雀的搜索步长，提高算法的全局搜索能力。其次ISSA算法还加入变异操作：在麻雀位置更新后，对部分麻雀进行变异操作，增加种群的多样性，避免算法陷入局部最优。

基于GA-SSA延迟感知任务卸载策略具体步骤如下：

1) 初始化：首先随机初始化麻雀种群，每个麻雀的位置代表一个任务卸载决策方案，利用GA的交叉和变异生成多样性高的初始种群，每个个体(染色体)表示一个卸载决策方案，二进制编码表示卸载策略(0表示本地计算，1表示卸载到边缘节点上)，避免SSA陷入局部最优。

2) 通过预警阈值公式$ST\left(t\right)=0.6-0.3\ast \left(t/T_{\max }\right)$ 动态调整发现者的比例。同时设置最大迭代次数。

3) 适应度计算：根据任务特性、网络状态和计算资源，计算每个麻雀的适应度值，即对应任务卸载决策方案的总执行延迟。

4) 更新发现者位置：根据GA-SSA的位置更新公式，更新发现者的位置。

5) 更新跟随者位置；根据GA-SSA的位置更新公式，更新跟随者的位置。

6) 变异操作：对部分麻雀进行变异操作，增加种群多样性。

7) 判断终止条件：如果达到最大迭代次数，则算法终止，输出最优解；否则，返回步骤2。

4. 实验结果与分析

本文通过仿真实验对GA-SSA算法的总延迟、总能耗的效应值进行评估，并与本地计算(LC)、粒子群优化算法(PSO)和遗传算法(GA)进行实验对比，实验数据来源于仿真数据。实验仿真环境是基于matlab2023b软件，Intel(R) Core(TM) i7-13700H，2.40 GHz，内存为32.00 GB，Windows 11操作系统。

(1) LC：该方法是将每个车辆上所有任务均放在本地车辆上进行计算处理，不将其卸载到任务边缘服务器上。

(2) PSO：该方法是基于粒子群搜索算法的计算卸载方式，寻找到最优的卸载策略，使得当前时刻函数效应值最小。假设惯性权重为0.8，学习因子c₁和c₂的值分别为1.5和1.5，最大的迭代次数为100。

(3) GA：该方法是基于遗传算法的计算卸载方式，寻找到最优的卸载策略，使得当前时刻函数效应值最小。假设当前交叉概率为0.8，选择方式是以锦标赛方式。变异概率为0.05，最大的迭代次数为100。

(4) GA-SSA：该方法是基于改进的麻雀算法计算卸载方式，寻找到最优的卸载策略，使得当前时刻函数效应值最小。假设最大迭代次数为100。

假设当前使用的是5G网络，传输速率为100 Mbps，车辆数量n取值10、20、30三种情况进行实验比较，其中每辆车上任务数量为10个，边缘节点数量为6。公式11中的$w_1$ 和$w_2$ 分别取0.6和0.4。为了方便计算，我们将实验过程中其他参数进行设置如下表1所示。

Table 1. Parameter settings

表1. 参数设置

参数	取值
车辆数量	10、20、30
边缘节点	8
任务数量	10
任务数据量	15 KB~20 KB
任务最大容忍延迟	100 mS
车辆计算功率	10 w
车辆传输功率	2 W
边缘服务器的计算功率	300 w
边缘服务器的传输功率	2 W
车辆计算能力	500 MIPS
边缘服务器计算能力	3000 MIPS

通过仿真数据，对比四种方法进行实验，通过对多个边缘服务器节点环境中的多车辆多任务的计算卸载决策进行实验分析，旨在寻找良好的卸载决策，使得这些车辆上的任务部分卸载在边缘节点上，从而使得车辆在行驶过程中能获取最低的效应值，这里的效应值是延迟和能耗的加权和。实验计算结果如下图1所示和表2所示：

Figure 1. Comparison of effect values of different algorithms

图1. 不同算法的效应值比较

Table 2. Unloading proportions of different algorithms

表2. 不同算法的卸载比例

算法	卸载比例	本地计算比例
GA-SSA	45%	55%
PSO	58%	42%
GA	37%	63%
LC	0%	100%

由图1可知，LC算法的效应值最大，即任务均在本地车辆进行处理时延迟和所消耗的时间总效应值最大，而GA-SSA算法效应值最小。GA算法的效应值仅次于GA-SSA算法。GA-SSA算法在任务总执行延迟方面优于传统的SSA、PSO和GA算法。随着任务数量的增加，GA-SSA算法的优势更加明显。这是因为GA-SSA算法通过引入自适应权重因子和变异操作，提高了算法的全局搜索能力和局部搜索能力，能够更好地找到最优的任务卸载决策方案。

从表2可知，本文提出的GA-SSA算法卸载比例是45%，比例适中，能够防止边缘节点过载情况。而在GA算法中，卸载比例最低，但是效应值比本文提出的GA-SSA算法大。PSO算法卸载比例最大，边缘节点的负载过高，造成部分任务延迟超标。所以，GA-SSA算法最适合该问题，因其全局搜索能力强，适应度最低。GA适用于实时性要求高的场景，如计算速度较快，但适应度稍高。PSO容易陷入局部最优，需调整参数(如增加多样性)以提升性能。所以本文提出的GA-SSA算法比较适合在实时性要求比较高的自动驾驶场景中，延迟较低。并且能够快速响应用户的服务请求。

5. 总结

本文通过改进的GA-SSA算法解决车联网中计算密集型任务的能量消耗与网络延迟低的高要求问题。通过构建最小化延迟与能耗加权和的效应值为目标的优化模型，将车联网中的任务卸载策略优化问题转换成一个单目标优化问题。GA-SSA算法在麻雀位置更新过程中，引入自适应权重因子，动态调整麻雀的搜索步长，提高算法的全局搜索能力。通过实验表明GA-SSA算法在解决该问题时具有一定的优势，比GA、PSO算法获得的策略更优。车辆网中多边缘节点的任务卸载问题的研究对智能驾驶技术的发展具有实际的指导意义。所以后期课题组还会对车辆网中计算卸载的安全性问题进行研究，这是后期开展的研究工作的主要方向。

基金项目

2024年江苏省大学生创新训练计划项目xcx2024184。