车辆雾网络中一种近似最优的计算卸载算法.pdf

第 卷第 期 年 月南 京 邮 电 大 学 学 报（自 然 科 学 版）（）：车辆雾网络中一种近似最优的计算卸载算法鲍 楠，周思瑶，孙希霞，左加阔，潘 甦南京邮电大学 物联网学院，江苏 南京()摘要：智能车辆上的时延敏感型任务对计算能力的要求很高，然而请求车辆上可用的计算资源有限不足以单独处理整个任务数据，很难满足时延需求。车辆雾计算（，）通过在请求车辆附近进行计算卸载来改善车辆服务。文中基于两阶段生产计划对计算卸载过程进行建模，提出了一种计算卸载算法（，）来优化卸载决策和执行顺序，从而降低计算卸载时延。在遗传算法（，）的基础上应用了 决定卸载顺序。通过 和 仿真，显示出与 相比，在相同的迭代次数下，具有更低的平均卸载时延和更好的稳定性。关键词：计算卸载；车辆雾计算；任务调度；遗传算法中图分类号：文献标志码：文章编号：（），()：，（），（），（），：；（）；（）收稿日期：；修回日期：本刊网址：基金项目：国家自然科学基金（）和中国博士后科学基金（）资助项目作者简介：鲍楠，女，博士，讲师，引用本文：鲍楠，周思瑶，孙希霞，等车辆雾网络中一种近似最优的计算卸载算法南京邮电大学学报（自然科学版），（）：随着物联网（，）和无线技术的发展，交通认知、自动驾驶、实时交通控制和增强现实（，）等前沿应用正在涌现，旨在提高交通系统的效率和安全性。这些新型应用带来的关键挑战之一是它们需要分析大量数据以做出适当和及时的决策，这对车辆的计算能力要求较高。然而车辆上可用的计算资源有限，很难有效地处理时延敏感型任务。近年来，人们开始使用云计算，将消耗资源的任务卸载到功能强大的云中心进行计算，并将结果返回给车辆。在云计算中，车辆与云中心之间的传播距离较长，会产生较大的传播时延；此外，大量的卸载可能导致骨干网拥塞。为了解决时延敏感的计算卸载问题，车辆雾计算（，）被广泛应用，旨在通过在车辆附近进行计算卸载来改善车辆服务。任务车辆可以在每个时隙内建立和维护多个 和 链路，通过边缘的近距离通信和多个雾节点的联合计算实现低时延。在实践中，许多移动应用程序由多个进程或组件组成，这使得实现细粒度的计算卸载成为可能。具体来说，每个任务可以被分割成多个独立的子任务，分配给不同的节点执行。根据任务的不同操作，计算卸载方案可以工作在多种模式下，例如顺序卸载和并行卸载。在发送端和接收端使用多输入多输出（，）可以增强信道容量，同时可以轻松地将多个天线单元放置在车辆中，因此 支持并行传播。并行卸载可以减少整体完成时间，比车载网络中的其他任务操作模式更具竞争力。中的服务质量衡量指标主要是时延和能耗，优化的关键点在于充分利用通信速率的差异和服务节点的异构计算能力，以平衡各个节点的工作量。文献提出了一种基于动态规划的启发式算法，以最小化所有用户之间的总服务时延。文献针对典型的异构雾网络，提出了一种通用的多用户系统模型，在该模型中，任务节点可以同时将计算任务卸载给多个具有异构能力的邻近服务节点实现任务的并行执行。基于匹配理论，将任务卸载最小化时延问题转化为多对一匹配问题，在计算资源和通信能力之间实现有效的折中，显著降低了服务时延。文献提出了一种高效的作业缓存算法，可以根据邻近车辆的信息调度作业，设计了一种基于蚁群算法的调度算法来解决分配问题。文献提出了一种基于半马尔可夫决策过程（，）的任务卸载问题，推导了不同决策下的传输延迟和任务到达率，分析了 系统中的最大车辆数量以确保时延满足最大延迟限制，利用基于贝尔曼方程的迭代算法来逼近期望的解。文献提出了一种移动感知任务卸载方案，旨在最小化软件定义的车辆网络中的任务计算时延。该方案包括两个阶段：雾节点选择和任务卸载。在第一阶段利用整数线性规划获得给定网络所需的最优雾节点数；在任务卸载阶段，提出了一种贪婪启发式方法来优化时延。文献研究了单用户多服务器场景下的卸载调度策略，基于混合流水车间调度模型对任务的卸载调度进行建模，获得系统时延并作为优化目标。文献设计了一种遗传算法来求解车辆调度优化问题，选择了随机遍历采样的方法来选择个体，以突变概率随机指定个体编码串中的某个位点。尽管文献考虑了任务执行顺序对时延的影响，但没有针对任务的执行顺序进行优化。文献忽略了遗传算法对初始种群的依赖性以及交叉变异率对收敛速度的影响。由于时延是反映服务质量的重要因素，因此本文将最小化时延作为优化目标。基于上述技术背景和提出的问题，本文基于两阶段生产计划对计算卸载过程进行建模，以最小化时延为目标，提出了一种基于遗传算法（，）的计算卸载算法（，）对优化问题进行求解，针对算法稳定性和收敛性，对初始种群和交叉变异规则进行优化；运用 确定卸载顺序实现单节点最优调度，获得近似最优解，降低时延。通过仿真，分别分析任务大小与时延之间的关系以及子任务数目与时延之间的关系；将 与、枚举法进行比较，评估了 在不同任务大小、不同子任务数目下的平均卸载时延，对算法的稳定性和收敛性分别进行了分析。系统模型考虑一个车辆雾网络，如图 所示，由集成移动边缘计算（，）服务器的 和车辆组成，这些实体称为雾节点，用 ，表示，是雾节点的数量。产生计算任务的车辆称为任务车辆。图 车辆雾网络车辆在 的通信覆盖范围内通过长期演进（）支持的 通信与 连接，车辆间采用 标准通过一跳通信相互连接。因此在任务车辆的通信范围内，具有空闲通信和计算资源第 期鲍 楠，等：车辆雾网络中一种近似最优的计算卸载算法的 或车辆都可以作为服务节点执行任务车辆卸载的计算任务。计算卸载模型考虑细粒度的任务卸载，即任务可以按最小粒度被分割成多个独立的子任务，分配给不同的节点执行。由于配备了多天线，请求车辆可以同时将数据传播给多个服务节点。记某个计算任务为 ，下标 是组成 的子任务数量，（单位为）表示子任务的数据量。计算卸载模型满足以下假设：（）不限制任务执行时间；（）每个子任务可以在任意一个节点上进行计算；（）任意时刻每个子任务至多在一个节点上进行处理；（）每个节点某时刻只能计算一个子任务；（）子任务的计算过程不允许中断；（）每个节点都有一个足够大的空间存储等待计算的子任务。在任务车辆的通信范围内具有空闲通信和计算资源 的 雾 节 点 定 义 为 可 用 节 点，数 量 为 。候选服务节点 是最终可能为任务车辆提供服务的节点集合，数量用 表示。对 按照综合能力进行降序排序，如果 大于子任务数量，则将 的前 个节点作为，；否则，。对于任务，卸载决策表示为 ，（）式中，表示第 个子任务的服务节点，应满足，且 和 可以相同，即一个服务节点可以处理多个子任务。为了方便计算时延，将 转化为 ，（）式中 表示 负责处理的子任务集合。任务数据通过无线 信道或者 信道并行传播，任务车辆到服务节点 的数据传播速率表示为 （）（）式中，为信道带宽，为车辆的发送功率，对于每辆车功率是恒定的。为加性高斯白噪声（，）的功率。表示任务车辆和服务节点 之间的距离，为无线信道的小尺度衰落信道系数。每个服务节点的处理能力不同，将 的主频记为。用 表示计算强度，单位为 ，即计算 数据所需的 周期数。服务节点按照先到先服务的方式处理子任务，并且在空闲时才能计算下一个子任务。将式（）定义为 的综合能力。（）计算卸载时延包括传播时延、计算时延和结果回传时延。由于任务计算结果较小，因此计算结果回传时延可以忽略不计。式（）和式（）分别表示在 上的传播时间和计算时间。，（），（）当 处理包含 个子任务的 时，在计算子任务的同时可以接收下一个子任务的数据，因此 的时延的递归公式如下（），（），（）（）（）（），（），（）（）（）（），（），（）（）（）（）式中，（）表示在服务节点 处理的第一个子任务的结束时间，（）和，（）分别表示第 个子任务的传播时间和计算时间。则 的时延为。问题建模由于多个服务节点并行处理任务，因此任务总时延为最迟完成任务的服务节点的时延。基于以上分析，以最小化任务总时延为目标，对计算卸载问题建模为（，）（）式中，。算法 遗传算法本节介绍一种基于遗传算法（）的计算卸载算法。作为一种智能优化算法被广泛用于解决调度问题，具有简单高效的特点，以较低的时间复杂度获得问题的近似最优解。对于优化问题，首先，通过为每个子任务随机分配一个服务节点来生成卸载决策，初始种群由 个卸载决策组成。适应度函数是评判决策南京邮电大学学报（自然科学版）年优劣的标准，在以时延为优化目标的问题中，将时延作为适应度函数，适应度函数越小，则该决策更接近最优解。交叉操作的作用是把优良的基因直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。根据适应度函数的大小选择父代决策，通过交叉操作形成下一代决策。以此类推，直到满足终止条件，最终生成卸载决策。的伪代码如算法 所示。算法 遗传算法：（）随机生成初始种群：（）：（）：（）：（）（）：在 年提出了一种两阶段生产计划的决策规则 ，用于生产的最优调度，并给出了最优性的证明。在两阶段生产计划问题中，一组项目必须先后经过两个生产阶段，每个阶段只有一台机器提供服务，一台机器上同时只能有一个项目。项目 由（，）表示，这两个数分别表示该项目通过第一阶段和第二阶段的服务时间。通过运用 构建项目执行顺序使整个操作的总运行时间最小。而计算卸载过程主要包括传播阶段和计算阶段。当同一服务节点执行多个子任务时，一旦完成前一个子任务的传播阶段并开始计算，该服务节点就可以接收下一个子任务的数据。这与两阶段生产计划的调度问题极为相似，这种相似性使得 能够应用于计算卸载中的卸载顺序问题。假设子任务 和 被分配给同一个服务节点，由（，）表示，这两个数分别表示传播和计算时延，用（，）表示。图 演示了两个子任务以不同顺序执行时的时延。在图（）所示的甘特图中可以看出在先执行 情况下，的传播时延与 的计算时延重叠 ，总时延为 。如果调换执行顺序，如图（）所示，重叠时间为 ，总时延为 。（）先 后（）先 后 图 和 的执行顺序用下面的例子来介绍 的决策规则。表 第 列的 是传播时延和计算时延中的最小值。如果传播时延小于计算时延，则子任务的 属性为；否则为。首先，这 个子任务根据属性升序排列，如表 所示。然后从表 中提取子任务，如果 为，则子任务 从调度的开头放置；否则从尾部放置。那么最终的任务调度顺序为，。表 个子任务的示例任务调度顺序 传播时延 计算时延 表 根据 排序后 个子任务任务调度顺序 传播时延 计算时延 计算卸载算法文中提出的计算卸载算法（）在遗传算法第 期鲍 楠，等：车辆雾网络中一种近似最优的计算卸载算法的基础上进行了改进，并应用 来确定卸载顺序。首先对子任务进行分组和排序。将 个子任务分为任意数量的组，不考虑子任务的执行顺序，至少分为一组，最多分为 组，每组子任务的数量可以不同。接下来将分组后的子任务按照数据量大小降序排列，如果大小相同，则子任务数量少的优先。假设将任务 划分为个组，。服务节点按综合能力降序排列为，子任务分组按照数据量大小降序排列为，可以为空。则对应序号的服务节点负责该子任务集，服务节点的时延用 ，表示。由于服务节点并行处理任务，的总时延为 （，）。根据以上描述，是数据量最大、耗时最长的子任务集，分配给综合能力最强的节点，因此 一定大于。如果 不是按降序排列的，则为此决策执行变异操作。具体操作如下：假设在服务节点数组中时延最大的服务节点位于，最小的服务节点位于，如果 小于，则在下一轮迭代中将 节点负责的子任务集交给 节点处理。的伪代码如算法 所示。算法 计算卸载算法（）：（）：（）：（）：（），：（）：（）：（）（）：仿真结果分析为了评估所提出的计算卸载算法的性能，使用 和 进行了比较仿真。假设任务车辆和服务节点在任务完成之前连接不会断开，且传播速度不变。在迭代次数和种群大小相同的情况下，将文中提出的计算卸载算法（）与遗传算法（）的时延性能进行了比较，并通过枚举法（）得到的最优决策进行验证。用于模拟道路和车辆的真实轨迹，辆汽车被放置在一条长度为 的 车道道路上，模拟时间为 。任务大小范围为，每 为一个区间，每个区间随机生成 个不同大小的任务，每个任务生成时间和网络条件均不同。主要仿真参数见表。表 仿真参数设置参数值小尺度衰落信道系数 路径损耗指数 噪声功率 车辆传播功率 的传播功率 上行带宽 上行带宽 车辆计算能力 ，计算能力 ，车辆通信覆盖半径 与车辆的通信范围 子任务数，迭代次数，种群大小，图 显示了相同子任务数量的平均卸载时延的变化。可以看出，无论对于哪一种算法，时延都随着子任务数量的增加而降低，这是因为子任务的并行执行减少了整体完成时间，因此卸载时延与子任务的数量成反比。在平均卸载时延方面，文中提出的 性能明显优于，接近最优决策。的平均时延仅比最优决策的平均时延高，而 的平均时延比相同任务规模的最优决策的平均时延高。在迭代次数和种群规模都相同的情况下，的平均时延比 低。这是因为 没有考虑到子任务等待计算的时间过长的问题，从而导致总时延变大；而 利用 确定了子任务的最优执行顺序，使得子任务等待计算的时南京邮电大学学报（自然科学版）年间减少，从而使得时延得以减少。从图中可以看出，的曲线相对 来说更平滑，说明 的稳定性优于。这是因为 对初始种群的选择有一定的依赖性，随机产生初始种群导致计算结果不稳定；在初始种群中引入了节点综合能力与任务大小的对应关系，对初始种群进行了优化，从而使得算法稳定性得以增强。图 平均卸载时延与子任务数量的关系图 显示了任务大小和时延之间的关系。可以看出时延随着数据大小的增加而增加，因此时延与任务大小成正比。在相同子任务数量的情况下，的平均时延仅比最优决策的平均时延高，的平均时延比最优决策的平均时延高。的平均卸载时延比 低。图 平均卸载时延与数据大小的关系图 对比了 和 的收敛性。从图中可以看出，在相同的迭代次数下，的平均卸载时延更小。此外还可以看出 经过 次迭代后，逐渐收敛至最优解，而 经过 次迭代后才得到了局部最优解。因此，的收敛速度和寻优结果都优于。这是因为 的交叉变异率会增加算法的迭代次数，对解的全局收敛性影响很大；考虑了卸载时延可能的最小值，对变异的判定标准和变异的操作进行了优化，从而提升了算法的全局收敛性。图 和 收敛性对比 结束语为了更好地服务于车辆和交通系统，文中提出了一种应用于车辆雾网络的计算卸载算法。在 基础上结合两阶段生产计划模型对计算任务卸载调度问题进行建模分析，利用 获取近似最优的卸载顺序。仿真结果表明，对于不同的任务规模和不同的子任务数量，该算法在平均卸载时延、稳定性和收敛性方面优于遗传算法，并且平均卸载时延接近理论上最优决策下的卸载时延。基于以上成果，在后续工作中将进一步研究具有依赖关系的计算卸载问题并考虑资源的可用性。参考文献：，：，（）：，：，（）：，：第 期鲍 楠，等：车辆雾网络中一种近似最优的计算卸载算法 ，：，（）：，：，：，（）：，（）：，：，：，（）：，：，（）：，（）：，：，（）：凌雪延，王鸿，宋荣方 多核服务器边缘计算系统中任务卸载调度和功率分配的研究 南京邮电大学学报（自然科学版），（）：，（），（）：（），：，（）：李强，袁福生，陈晶，等能源互联网场景下的计算卸载机制研究 南京邮电大学学报（自然科学版），（）：，（），（）：（），：，（）：，：，：（责任编辑：潘雪松）南京邮电大学学报（自然科学版）年