一种针对能耗优化的车联网计算卸载方案

高文轩，杨新杰,2

研究与开发

一种针对能耗优化的车联网计算卸载方案

高文轩1，杨新杰1,2

（1. 宁波大学信息科学与工程学院，浙江 宁波 315211；2. 网络与交换技术全国重点实验室（北京邮电大学），北京 100876）

车联网环境下面向车辆的应用普遍具有计算密集和时延敏感等特性，引入移动车辆闲置计算资源作为网络算力的补充，可有效缓解边缘服务器的计算负载压力。针对车联网环境中边缘计算卸载的任务分配问题，充分利用RSU、用户车辆和RSU服务范围内移动车辆的计算资源组合，提出一种基于麻雀搜索算法的计算卸载方案（sparrow search based computation offloading scheme，S2COS），用以优化整体系统能耗。此外，该方案充分考虑了车辆移动性带来的服务时间限制以及计算节点出现故障的可能性等现实问题。仿真结果表明，S2COS在处理计算密集和时延敏感型任务时可以满足任务时延要求，并且能够显著降低系统能耗。

车联网；计算卸载；节点故障；麻雀搜索算法

0 引言

车联网（Internet of vehicles，IoV）是移动物联网技术的衍生形式[1-2]。IoV将车辆和其他网络节点引入移动通信网络中，通过信息收集、处理和实时反馈为车辆提供服务，实现智能交通。随着车辆逐步智能化，智能交通快速发展，计算密集型和时延敏感型任务的需求显著增加[3]。这些任务，如路径规划、车辆感知、虚拟现实等，对计算资源的高效利用和实时响应提出了更高要求。鉴于车辆的有限计算能力，许多任务难以有效地在本地进行处理。同时，传统的云处理方式车辆与云服务器之间距离较远，导致较大的传输时延，降低了服务质量（quality of service，QoS）。

对于蜂窝网络中的卸载问题，为了优化系统的能量效率或任务时延，一些学者研究了二进制卸载策略，即每个用户可以选择在本地执行任务或者将任务卸载到附近的边缘服务器[4-5]。类似地，对于车联网环境中的卸载问题，用户车辆的任务可以卸载到附近配备边缘服务器的路边单元（road side unit，RSU）上进行处理。例如，文献[6]考虑在一个多用户多边缘服务器场景中，用户车辆采用二进制卸载方式且对服务器的负载进行均衡优化，在降低任务时延的同时提高了资源利用率。与二进制卸载相比，部分卸载方式在有限的车辆、服务器计算资源和无线信道资源的情况下显得更为合理。文献[7]在单用户单边缘服务器场景中采用部分卸载方式，提出一种协同优化卸载数据比例和传输功率的策略，既满足业务时延要求又可最小化用户能耗。文献[8]在多车辆、多RSU组成的车辆边缘计算（vehicular edge computing，VEC）网络中考虑部分卸载策略，对卸载比和RSU选择进行协同优化，同时考虑了车辆移动性造成的任务时延，有效提升了系统的能效。

前述研究提出了二进制卸载或部分卸载策略，将任务卸载到边缘服务器上。然而，这些策略未能有效利用IoV中的其他空闲车辆的计算资源。此外，过多地将任务卸载到边缘服务器可能会导致服务器过载，从而降低系统性能。因此，有必要考虑合理利用空闲车辆的计算资源，以实现边缘服务器负载的均衡分配。文献[9]提出了一种联合卸载方案，将用户任务划分为3个部分：本地车辆计算部分，利用V2I（vehicle to infrastructure）通信模式将任务卸载至边缘服务器的部分，以及通过V2V（vehicle to vehicle）通信模式将任务卸载至空闲车辆的部分，该方案旨在优化服务时延。为了减轻边缘服务器的负载，在多用户设备、多空闲车辆组成的移动边缘计算（mobile edge computing，MEC）场景中，文献[10]提出一种空闲车辆辅助的二进制MEC任务卸载和资源分配方案，旨在优化基于任务优先级加权的总处理时延。文献[11]采用二进制卸载方式，利用空闲车辆和边缘服务器共同为多个用户车辆提供计算服务，并提出任务卸载和资源分配联合设计的策略，旨在优化任务时延和系统能耗的加权和。由于所形成的问题具有NP难属性，作者采用了博弈论和Q学习方法分别求解卸载决策和资源分配问题。

可以看出，上述研究主要以时延、能耗、自定义效用或成本函数为优化目标，有的研究采用二进制或部分卸载将任务卸载到边缘服务器，却忽略了空闲车辆的资源利用。另一些研究虽然同时利用了边缘服务器和空闲车辆资源，但却选择了二进制卸载方式，这在一定程度上导致了用户车辆计算资源的浪费。此外，大多数研究假设节点工作时不会发生故障，这与实际情况存在偏差，导致结果的准确性受到影响。

在当前绿色网络的快速发展的背景下，在满足任务基本性能指标如时延的同时，有效降低整体系统能耗是一个值得关注的重要目标。本文的工作将用户任务进行部分本地计算、部分卸载给配备边缘服务器的RSU和RSU范围内的空闲车辆进行计算以充分利用资源，用以降低系统总能耗。同时，本文考虑了各个计算节点的故障情况和车辆移动性对任务计算时长的影响，并针对节点故障提出任务再分配和重计算机制，以确保任务能够完成。因为该优化问题的特殊属性，可以使用群智能优化算法来求解，相较于文献[12-13]中所使用的遗传算法和模拟退火等群智能方法，麻雀搜索算法具有更好的收敛速度、收敛稳定性和全局寻优能力[14]。因此，本文采用更契合本文优化问题的麻雀搜索算法来优化任务分配以最小化系统总能量消耗。

1 车辆边缘计算卸载系统模型

1.1 系统模型

图1 车辆边缘计算卸载系统模型

1.2 通信模型

用户车辆到RSU的上行链路速率和接收信噪比（signal-to-noise ratio，SNR）可分别定义为[15]：

1.3 计算模型

1.4 考虑工作节点故障的重计算机制

在实际系统中，节点处理任务时可能会突发故障，因此需要在系统设计中考虑这种情况，以提高整个系统的稳定性。在由多个计算节点连接组成的分布式计算系统（distributed computing system，DCS）中，可以采取一些策略来提高系统的可靠性，比如使用高可靠的处理单元硬件等。当DCS的硬件配置固定时，系统可靠性取决于如何将给定的计算任务分配到适当的节点上，以及每个节点成功执行分配任务的概率[19-20]。本节将分析各个工作节点发生故障的情况。

如果节点在处理任务时没有发生故障，即成功完成分配的任务，这种情况的概率定义为成功概率。反之，如果节点在处理任务时发生故障，将无法完成分配的任务，这种情况的概率定义为故障概率。节点的成功概率和故障概率可由如下计算式表示[21]。

因此，在进行重计算前，服务车辆计算任务经历的最大时延为：

此时整个计算卸载任务的系统总能耗为：

1.5 问题描述

分布式程序可靠性（distributed program reliability，DPR）是指分布式计算系统（DCS）中含有分布式文件的程序成功运行的概率。通过尽可能多地分配任务给节点来提高DCS可靠性是一个NP难问题[20,22]。式（26）是以DCS可靠性为基础的一个问题，因此也是一个NP难问题，且具有非凸性。对于此类问题，利用群智能算法求解可在多项式时间内获得近似最优解，相比一般的搜索算法更高效。因此，本文采用麻雀搜索算法对以上优化问题求解，并将其命名为基于麻雀搜索算法的计算卸载方案（sparrow search based computation offloading scheme，S2COS）。

2 基于麻雀搜索算法的计算卸载方案

在麻雀搜索算法中，麻雀种群分为发现者群体和加入者群体。选取群体中一定比例数量的位置较优的若干麻雀作为发现者群体，每一次的迭代寻优过程中都会更新发现者群体，种群中剩下的麻雀作为加入者群体，发现者负责全局搜索并为加入者提供觅食方向和区域，一旦发现者找到更好的位置，加入者便会向发现者方向飞去。在每一轮迭代的后期，随机抽取一定数量的麻雀个体用作侦察预警，称作侦察者，对应麻雀在自然界中的反捕食行为，如果侦察者发现危险则放弃觅食飞向新的位置[23]。

2.1 种群的设定和更新

发现者位置更新计算式如下：

加入者位置更新计算式如下：

侦察者的位置更新计算式如下：

2.2 适应度函数的设定和约束处理

算法1中描述了S2COS的具体流程。

算法1 S2COS算法

end for

使用式（28）对麻雀位置进行更新

end for

使用式（30）对麻雀位置进行更新

end for

使用式（31）对麻雀位置进行更新

end for

end while

3 仿真与分析

系统仿真基于由单个用户车辆、单个RSU和多辆移动空闲车辆组成的如图1所示的IoV系统。参数设定参考文献[26-27]，并做了符合系统环境的参数调整，仿真参数及取值见表1。除非有明确说明，否则仿真都使用参数的默认值。

为理解所提S2COS的全面性能，考虑以下S2COS简化应用方案并进行性能比较。

• 方案1：用户车辆和服务车辆进行计算，RSU只转发任务给服务车辆。

• 方案2：RSU和服务车辆进行计算，用户车辆卸载全部任务。

• 方案3：用户车辆和RSU进行计算，不使用服务车辆的计算资源。

另外，将所提S2COS和以下常用算法进行性能比较。

• 算法1：文献[12]提出的优化能量效率的模拟退火算法（simulated annealing algorithm，SA）。

• 算法2：文献[13]提出的基于遗传算法的卸载策略（genetic algorithm-based offloading strategy，GAO）。

表1 仿真参数及取值

不同方案和不同任务量对能耗和时延的影响如图2所示。可以看出，所有方案的系统能耗都随着任务量的增加而增加，其中，方案3的能耗最大且无法满足时延要求。因为对于数据量大、时延要求高的任务而言，用户车辆和RSU的计算资源相对有限。S2COS和方案2均可满足任务时延要求，而S2COS使用了用户车辆承担一部分计算任务，可以通过合理的任务分配进一步降低整个系统能耗。方案1的系统能耗虽然最小，但以牺牲时延要求为代价，不适合时延要求高的任务，如辅助驾驶、路径导航规划等应用。

图2 不同方案和不同任务量对能耗和时延的影响

不同的服务车辆数量和时延约束下，S2COS 的不同服务车辆数和不同时延约束下能耗对比如图3所示，不同服务车辆数和不同时延约束下时延对比如图4所示。结果表明，随着服务车辆增多，系统能耗下降，且不同时延约束下的系统能耗性能差别逐步变小。这表明，随着服务车辆增多，系统会表现出更好的鲁棒性。这是因为更多的节点意味着更多的任务分配方式，因而可以进一步降低系统能耗。此外，从图3中可以看到，当服务车辆数增加到6辆以上时，对于时延约束相对宽松的0.65 s的情况，系统的能耗已经相差无几，这表明当服务车辆数达到一定数量后，系统能耗将难以进一步优化。因此，对于在不同时延约束、不同任务量的条件下，选择合适的服务车辆数可能是未来值得研究的。图4显示S2COS在不同服务车辆数量时均可满足时延约束。

图3 S2COS的不同服务车辆数和不同时延约束下能耗对比

图4 不同服务车辆数和不同时延约束下时延对比

为了评估重计算机制对系统性能的提升，本文对比了S2COS方案在重计算机制和无重计算机制时的性能。在无重计算机制中，所有故障节点的任务退还给用户车辆计算。重计算机制与无重计算机制的比较如图5所示，设定任务的时延约束为0.55 s，随着总任务量增加，系统的能耗也随之增加，且考虑节点故障并进行重计算的系统的能耗要比没有重计算机制的系统显著降低。另外，无重计算的系统当任务量大于800 KB时无法满足时延约束，而有重计算的系统将此指标提升至950 KB。这是因为，在无重计算的系统中，不成功的任务只能退还给用户车辆计算，而有重计算的系统会提前考虑节点故障情况并通过任务再分配尽可能降低系统能耗。

图5 重计算机制与无重计算机制的比较

不同系统环境下有无重计算机制的对比如图6所示，进一步评估了不同节点故障率对于系统性能的影响，将任务量设定成800 KB，复杂度设定为7 500，时延约束设定0.5 s。本文假设在每一个故障率区间内，故障率遵循均匀分布并将故障率大于0.1的区间定义为恶劣系统环境。由图6可知，系统的能耗会随着故障率的升高而升高。相比无重计算机制，重计算机制可显著降低系统能耗，并可满足时延要求，无重计算机制在平均故障率大于0.2 s时无法满足时延要求。这说明所提方案在恶劣系统环境下仍具有良好的鲁棒性。

图6 不同系统环境下有无重计算机制的对比

不同算法的系统能耗对比如图7所示，显示了S2COS和其他两个常用对比算法的系统能耗比较，任务复杂度设置为6 500。可以看出，随着任务量的增加各算法所需系统能耗都会增加，所提方案相较于其他两种算法拥有更好的全局搜索最优解能力，在时延约束下，可找到更好的任务卸载比例和任务分配卸载决策以达到最低的系统能耗，避免了能量的浪费，有效降低系统能耗。

图7 不同算法的系统能耗对比

4 结束语

本文针对一个由RSU、用户车辆和多个服务车辆组成的车联网系统，提出了一种联合卸载方案S2COS。该方案引入RSU范围内服务车辆的计算资源，在满足任务时延要求的前提下，通过获得最优的任务分配方式最大限度地降低系统能耗。此外，所提出的方案考虑每种节点的故障情况，提出一种故障节点任务重计算机制。仿真结果表明，S2COS在满足时延要求和降低能耗方面相对于对比方案和其他算法具有明显优势，并且具备良好的优化效果。未来计划将工作扩展到多RSU小区场景，研究资源的分配和因车辆的移动性而产生的信道时变对系统的影响。

[1] ZHUANG W, YE Q, LYU F, et al. SDN/NFV-empowered future IoV with enhanced communication, computing, and caching[J]. Proceedings of the IEEE, 2019, 108(2): 274-291.

[2] 王鲲, 董振江, 杨凡, 等. 基于C-V2X的车路协同自动驾驶关键技术与应用[J]. 电信科学, 2023, 39(3): 45-60. WANG K, DONG Z J, YANG F, et al. Key technologies and applications of C-V2X based vehicle-infrastructure cooperative autonomous driving[J]. Telecommunications Science, 2023, 39(3): 45-60.

[3] WANG J, FENG D, ZHANG S, et al. Computation offloading for mobile edge computing enabled vehicular networks[J]. IEEE Access, 2019(7): 62624-62632.

[4] LIU C, LI K, LI K. A game approach to multi-servers load balancing with load-dependent server availability consideration[J]. IEEE Transactions on Cloud Computing, 2021, 9(1): 1-13.

[5] FAN W, HAN J, YAO L, et al. Latency-energy optimization for joint Wi-Fi and cellular offloading in mobile edge computing networks[J]. Computer Networks, 2020(181): 107570.

[6] XU X, XUE Y, LI X, et al. A computation offloading method for edge computing with vehicle-to-everything[J]. IEEE Access, 2019(7): 131068-131077.

[7] REN C, ZHANG G, GU X, et al. Computing offloading in vehicular edge computing networks: full or partial offloading?[C]//Proceedings of 2022 IEEE 6th Information Technology and Mechatronics Engineering Conference (ITOEC). Piscataway: IEEE Press, 2022: 693-698.

[8] DAI Y, XU D, MAHARJAN S, et al. Joint load balancing and offloading in vehicular edge computing and networks[J]. IEEE Internet of Things Journal, 2019, 6(3): 4377-4387.

[9] WANG H, LI X, JI H, et al. Federated offloading scheme to minimize latency in MEC-enabled vehicular networks[C]//Proceedings of 2018 IEEE Globecom Workshops (GC Wkshps). Piscataway: IEEE Press, 2018: 1-6.

[10] FAN W, LIU J, HUA M, et al. Joint task offloading and resource allocation for multi-access edge computing assisted by parked and moving vehicles[J]. IEEE Transactions on Vehicular Technology, 2022, 71(5): 5314-5330.

[11] ZHANG H, WANG Z, LIU K, et al. V2X offloading and resource allocation in SDN-assisted MEC-based vehicular networks[J]. China Communications, 2020, 17(5): 266-283.

[12] 王艳阁, 奚建清. 具有隐私保护的车联网边缘计算任务卸载资源分配策略[J]. 计算机工程与设计, 2023, 44(2): 372-378. WANG Y G, XI J Q. Privacy preserving resource allocation strategy for edge computing task offloading in internet of vehicles[J]. Computer Engineering and Design, 2023, 44(2): 372-378.

[13] 余翔, 刘一勋, 石雪琴, 等. 车联网场景下的移动边缘计算卸载策略[J]. 计算机工程, 2020, 46(11): 29-34. YU X, LIU Y X, SHI X Q, et al. Mobile edge computing offloading strategy under Internet of vehicles scenario[J]. Computer Engineering, 2020, 46(11): 29-34.

[14] 李雅丽, 王淑琴, 陈倩茹, 等. 若干新型群智能优化算法的对比研究[J]. 计算机工程与应用, 2020, 56(22): 1-12. LI Y L, WANG S Q, CHEN Q R, et al. Comparative study of several new swarm intelligence optimization algorithms[J]. Computer Engineering and Applications, 2020, 56(22): 1-12.

[15] LIU J, WANG Y, ZHANG W, et al. A novel offloading and resource allocation scheme for time-critical tasks in heterogeneous internet of vehicles[C]//Proceedings of 2023 2nd International Conference for Innovation in Technology (INOCON). Piscataway: IEEE Press, 2023: 1-7.

[16] RAZA S, LIU W, AHMED M, et al. An efficient task offloading scheme in vehicular edge computing[J]. Journal of Cloud Computing, 2020(9): 1-14.

[17] GUO S T, XIAO B, YANG Y, et al. Energy-efficient dynamic offloading and resource scheduling in mobile cloud computing[C]//Proceedings of IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications. Piscataway: IEEE Press, 2016: 1-9.

[18] WANG Y, SHENG M, WANG X, et al. Mobile-edge computing: partial computation offloading using dynamic voltage scaling[J]. IEEE Transactions on Communications, 2016, 64(10): 4268-4282.

[19] PLANK J S, ELWASIF W R. Experimental assessment of workstation failures and their impact on checkpointing systems[C]//Proceedings of Digest of Papers, Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing (Cat. No. 98CB36224). Piscataway: IEEE Press, 1998: 48-57.

[20] VIDYARTHI D P, TRIPATHI A K. Maximizing reliability of distributed computing system with task allocation using simple genetic algorithm[J]. Journal of Systems Architecture, 2001, 47(6): 549-554.

[21] LAWLESS J F. Statistical models and methods for lifetime data[M]. Hoboken: John Wiley & Sons, 2011.

[22] LIN M S, CHEN D J. The computational complexity of the reliability problem on distributed systems[J]. Information Processing Letters, 1997, 64(3): 143-147.

[23] 薛建凯. 一种新型的群智能优化技术的研究与应用[D]. 上海: 东华大学, 2020.XUE J K. Research and application of a new swarm intelligence optimization technology[D]. Shanghai: Donghua University, 2020.

[24] 陈刚, 林东, 陈飞, 等. 基于 Logistic 回归麻雀算法的图像分割[J]. 北京航空航天大学学报, 2021, 49(3): 636-646. CHEN G, LIN D, CHEN F, et al. Image segmentation based on logistic regression sparrow algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 49(3): 636-646.

[25] WU G, MALLIPEDDI R, SUGANTHAN P N. Problem definitions and evaluation criteria for the CEC 2017 competition on constrained real-parameter optimization[R]. 2017.

[26] DINH T Q, TANG J, LA Q D, et al. Offloading in mobile edge computing: task allocation and computational frequency scaling[J]. IEEE Transactions on Communications, 2017, 65(8): 3571-3584.

[27] GUO H, LIU J, REN J, et al. Intelligent task offloading in vehicular edge computing networks[J]. IEEE Wireless Communications, 2020, 27(4): 126-132.

A computation offloading scheme for energy consumption optimization in Internet of vehicles

GAO Wenxuan1, YANG Xinjie1,2

1. Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China 2.State key Laboratory of Networking and Switching Technology (Beijing University of Posts and Telecommunications), Beijing 100876, China

In Internet of vehicles (IoV), vehicle-oriented applications are generally computation-intensive and latency-sensitive. Introducing idle computing resources from mobile vehicles as a supplement to network computing power can effectively alleviate the load pressure on edge servers. The problem of task allocation for edge computation offloading in the context of IoV environment were researched. By fully leveraging the combined computing resources of roadside units (RSU), user vehicles, and mobile vehicles within the RSU service range, a computation offloading strategy based on the sparrow search algorithm was proposed and referred to as sparrow search based computation offloading scheme (S2COS), aiming to optimize the overall system energy consumption. In addition, this strategy fully taked into account practical network issues such as service time constraints caused by vehicle mobility and the potential occurrence of computation node failures. The simulation results demonstrate that S2COS can meet the latency requirements for computation-intensive and latency-sensitive tasks, while significantly reducing system energy consumption.

Internet of vehicles, computation offloading, node failure, sparrow search algorithm

The Ningbo Municipal Natural Science Foundation (No.2019A610073), Open Foundation of State key Laboratory of Networking and Switching Technology (Beijing University of Posts and Telecommunications) (No.SKLNST-2021-1-12)

TP393

A

10.11959/j.issn.1000−0801.2023189

2023−07−19；

2023−09−28

宁波市自然科学基金资助项目（No.2019A610073）；网络与交换技术全国重点实验室（北京邮电大学）开放课题资助项目（No.SKLNST-2021-1-12）

高文轩（1998− ），男，宁波大学硕士生，主要研究方向为车联网系统的资源管理和性能优化。

杨新杰（1971− ），男，宁波大学信息科学与工程学院教授、硕士生导师，主要研究方向为下一代移动通信系统架构、移动物联网接入技术、协作中继网络性能等。