鲍 楠，周思瑶，孙希霞，左加阔，潘 甦
(南京邮电大学物联网学院，江苏 南京 210003)
随着物联网（Internet of Things，IoT）［1］和无线技术的发展，交通认知、自动驾驶、实时交通控制和增强现实（Augmented Reality，AR）［2－3］等前沿应用正在涌现，旨在提高交通系统的效率和安全性。这些新型应用带来的关键挑战之一是它们需要分析大量数据以做出适当和及时的决策，这对车辆的计算能力要求较高。然而车辆上可用的计算资源有限，很难有效地处理时延敏感型任务［4］。
近年来，人们开始使用云计算［5］，将消耗资源的任务卸载到功能强大的云中心进行计算，并将结果返回给车辆［6］。在云计算中，车辆与云中心之间的传播距离较长，会产生较大的传播时延；
此外，大量的卸载可能导致骨干网拥塞。
为了解决时延敏感的计算卸载问题，车辆雾计算（Vehicle Fog Computing，VFC）［7］被广泛应用，旨在通过在车辆附近进行计算卸载来改善车辆服务。任务车辆可以在每个时隙内建立和维护多个V2V和V2I 链路，通过边缘的近距离通信和多个雾节点的联合计算实现低时延。
在实践中，许多移动应用程序由多个进程或组件组成，这使得实现细粒度的计算卸载成为可能。具体来说，每个任务可以被分割成多个独立的子任务，分配给不同的节点执行。根据任务的不同操作，计算卸载方案可以工作在多种模式下，例如顺序卸载和并行卸载。在发送端和接收端使用多输入多输出（Multiple Input Multiple Output，MIMO）可以增强信道容量，同时可以轻松地将多个天线单元放置在车辆中，因此MIMO-V2V［8］支持并行传播。并行卸载可以减少整体完成时间，比车载网络中的其他任务操作模式更具竞争力。
VFC 中的服务质量衡量指标主要是时延和能耗，优化的关键点在于充分利用通信速率的差异和服务节点的异构计算能力，以平衡各个节点的工作量。文献［9］提出了一种基于动态规划的启发式算法，以最小化所有用户之间的总服务时延。文献［10］针对典型的异构雾网络，提出了一种通用的多用户系统模型，在该模型中，任务节点可以同时将计算任务卸载给多个具有异构能力的邻近服务节点实现任务的并行执行。基于匹配理论，将任务卸载最小化时延问题转化为多对一匹配问题，在计算资源和通信能力之间实现有效的折中，显著降低了服务时延。文献［11］提出了一种高效的作业缓存算法，可以根据邻近车辆的信息调度作业，设计了一种基于蚁群算法的调度算法来解决分配问题。文献［12］提出了一种基于半马尔可夫决策过程（Semi-Markov Decision Process，SMDP）的任务卸载问题，推导了不同决策下的传输延迟和任务到达率，分析了VFC 系统中的最大车辆数量以确保时延满足最大延迟限制，利用基于贝尔曼方程的迭代算法来逼近期望的解。文献［13］提出了一种移动感知任务卸载方案，旨在最小化软件定义的车辆网络中的任务计算时延。该方案包括两个阶段：雾节点选择和任务卸载。在第一阶段利用整数线性规划获得给定网络所需的最优雾节点数；
在任务卸载阶段，提出了一种贪婪启发式方法来优化时延。文献［14］研究了单用户多服务器场景下的卸载调度策略，基于混合流水车间调度模型对任务的卸载调度进行建模，获得系统时延并作为优化目标。文献［15］设计了一种遗传算法来求解车辆调度优化问题，选择了随机遍历采样的方法来选择个体，以突变概率随机指定个体编码串中的某个位点。
尽管文献［14］考虑了任务执行顺序对时延的影响，但没有针对任务的执行顺序进行优化。文献［15］忽略了遗传算法对初始种群的依赖性以及交叉变异率对收敛速度的影响。
由于时延是反映服务质量的重要因素，因此本文将最小化时延作为优化目标。基于上述技术背景和提出的问题，本文基于两阶段生产计划对计算卸载过程进行建模，以最小化时延为目标，提出了一种基于遗传算法（Genetic Algorithm，GA）的计算卸载算法（Computation Offloading Algorithm，COA）对优化问题进行求解，针对算法稳定性和收敛性，对初始种群和交叉变异规则进行优化；
运用Johnson Rules确定卸载顺序实现单节点最优调度，获得近似最优解，降低时延。通过仿真，分别分析任务大小与时延之间的关系以及子任务数目与时延之间的关系；
将COA 与GA、枚举法进行比较，评估了COA 在不同任务大小、不同子任务数目下的平均卸载时延，对算法的稳定性和收敛性分别进行了分析。
考虑一个车辆雾网络，如图1 所示，由集成移动边缘计算（Mobile Edge Computing，MEC）服务器［16］的RSU 和车辆组成，这些实体称为雾节点，用N＝｛n1，…，nk，…，nN｝ 表示，N是雾节点的数量。产生计算任务的车辆称为任务车辆。
图1 车辆雾网络
车辆在RSU 的通信覆盖范围内通过长期演进（LTE）支持的V2I 通信与RSU 连接，车辆间采用IEEE802.11p 标准通过一跳通信相互连接。因此在任务车辆的通信范围内，具有空闲通信和计算资源的RSU 或车辆都可以作为服务节点执行任务车辆卸载的计算任务。
1.1 计算卸载模型
考虑细粒度的任务卸载，即任务可以按最小粒度被分割成多个独立的子任务，分配给不同的节点执行。由于配备了多天线，请求车辆可以同时将数据传播给多个服务节点。记某个计算任务为T＝｛st1，st2，…stT｝，下标T是组成T的子任务数量，sti（单位为Mb）表示子任务的数据量。计算卸载模型满足以下假设：（1） 不限制任务执行时间；
（2） 每个子任务可以在任意一个节点上进行计算；
（3） 任意时刻每个子任务至多在一个节点上进行处理；
（4）每个节点某时刻只能计算一个子任务；
（5） 子任务的计算过程不允许中断；
（6） 每个节点都有一个足够大的空间存储等待计算的子任务。
在任务车辆的通信范围内具有空闲通信和计算资源的雾节点定义为可用节点Navl，数量为｜Navl｜。候选服务节点Ncand是最终可能为任务车辆提供服务的节点集合，数量用sn表示。对Navl按照综合能力进行降序排序，如果｜Navl｜大于子任务数量T，则将Navl的前T个节点作为Ncand，sn＝T；
否则Ncand＝Navl，sn＝｜Navl｜。
对于任务T，卸载决策表示为
式中，σi表示第i个子任务的服务节点，σi应满足σi∈N，且σi和σj可以相同，i≠j，∀i，j＝1，2，…，T，即一个服务节点可以处理多个子任务。
为了方便计算时延，将σ转化为
式中φnk表示nk负责处理的子任务集合。
任务数据通过无线V2V 信道或者V2I 信道并行传播，任务车辆到服务节点nk的数据传播速率表示为
式中，B为信道带宽，P为车辆的发送功率，对于每辆车功率是恒定的。N0为加性高斯白噪声（Additive White Gaussian Noise，AWGN）的功率。Lnk表示任务车辆和服务节点nk之间的距离，h为无线信道的小尺度衰落信道系数。
每个服务节点的处理能力不同，将nk的主频记为fnk。用γ表示计算强度，单位为CPU cycles／bit，即计算1 bit 数据所需的CPU 周期数。服务节点按照先到先服务的方式处理子任务，并且在空闲时才能计算下一个子任务。
将式（4）定义为nk的综合能力。
计算卸载时延包括传播时延、计算时延和结果回传时延。由于任务计算结果较小，因此计算结果回传时延可以忽略不计。式（5）和式（6）分别表示sti在nk上的传播时间和计算时间。
当nk处理包含m个子任务的φnk时，在计算子任务的同时可以接收下一个子任务的数据，因此nk的时延的递归公式如下
式中，t1（nk） 表示在服务节点nk处理的第一个子任务的结束时间，tm，1（nk） 和tm，2（nk） 分别表示第m个子任务的传播时间和计算时间。则nk的时延为。
1.2 问题建模
由于多个服务节点并行处理任务，因此任务总时延为最迟完成任务的服务节点的时延。基于以上分析，以最小化任务总时延为目标，对计算卸载问题建模为
式中，σ＝［σ1，…，σi，…，σj，…，σN］，σi∈N。
2.1 遗传算法
本节介绍一种基于遗传算法（GA）［17］的计算卸载算法。GA 作为一种智能优化算法被广泛用于解决调度问题，具有简单高效的特点，以较低的时间复杂度获得问题的近似最优解。
对于优化问题P，首先，通过为每个子任务随机分配一个服务节点来生成卸载决策，初始种群由PopSize个卸载决策组成。适应度函数是评判决策优劣的标准，在以时延为优化目标的问题中，将时延作为适应度函数，适应度函数越小，则该决策更接近最优解。交叉操作的作用是把优良的基因直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。根据适应度函数的大小选择父代决策，通过交叉操作形成下一代决策。以此类推，直到满足终止条件，最终生成卸载决策σ。
GA 的伪代码如算法1 所示。
算法1遗传算法
2.2 Johnson Rules
Johnson［18］在1954 年提出了一种两阶段生产计划的决策规则——Johnson Rules，用于生产的最优调度，并给出了最优性的证明。在两阶段生产计划问题中，一组项目必须先后经过两个生产阶段，每个阶段只有一台机器提供服务，一台机器上同时只能有一个项目。项目p由（ps1，ps2） 表示，这两个数分别表示该项目通过第一阶段和第二阶段的服务时间。通过运用Johnson Rules 构建项目执行顺序使整个操作的总运行时间最小。
而计算卸载过程主要包括传播阶段和计算阶段。当同一服务节点执行多个子任务时，一旦完成前一个子任务的传播阶段并开始计算，该服务节点就可以接收下一个子任务的数据。这与两阶段生产计划的调度问题极为相似，这种相似性使得Johnson Rules 能够应用于计算卸载中的卸载顺序问题。
假设子任务st1和st2被分配给同一个服务节点，st1由（4，5）表示，这两个数分别表示传播和计算时延，st2用（1，3）表示。图2 演示了两个子任务以不同顺序执行时的时延。在图2（a）所示的甘特图中可以看出在先执行st1情况下，st1的传播时延与st2的计算时延重叠1 s，总时延为12 s。如果调换执行顺序，如图2（b）所示，重叠时间为3 s，总时延为10 s。
图2 st1 和st2 的执行顺序
用下面的例子来介绍Johnson Rules 的决策规则。表1 第4 列的dmin是传播时延和计算时延中的最小值。如果传播时延小于计算时延，则子任务的type属性为1；
否则为2。首先，这4 个子任务根据dmin属性升序排列，如表2 所示。然后从表2 中提取子任务，如果type为1，则子任务sti从调度的开头放置；
否则从尾部放置。那么最终的任务调度顺序为［st1，st4，st2，st3］。
表1 4 个子任务的示例
表2 根据Johnson Rules 排序后4 个子任务
2.3 计算卸载算法
文中提出的计算卸载算法（COA）在遗传算法的基础上进行了改进，并应用Johnson Rules 来确定卸载顺序。
首先对子任务进行分组和排序。将T个子任务分为任意数量的组，不考虑子任务的执行顺序，至少分为一组，最多分为T组，每组子任务的数量可以不同。接下来将分组后的子任务按照数据量大小降序排列，如果大小相同，则子任务数量少的优先。
假设将任务T划分为k个组，k∈［1，sn］。服务节点按综合能力降序排列为［n1，…，nsn］，子任务分组按照数据量大小降序排列为［φn1，…，φnsn］，φnk可以为空。则对应序号的服务节点负责该子任务集，服务节点的时延用delay＝［dn1，…，dnsn］ 表示。由于服务节点并行处理任务，T的总时延为Delay＝max（［dn1，…，dnsn］）。
根据以上描述，φn1是数据量最大、耗时最长的子任务集，分配给综合能力最强的节点n1，因此Delay一定大于dn1。如果delay不是按降序排列的，则为此决策执行变异操作。具体操作如下：假设在服务节点数组中时延最大的服务节点位于lmax，最小的服务节点位于lmin，如果lmin小于lmax，则在下一轮迭代中将lmax节点负责的子任务集交给lmin节点处理。
COA 的伪代码如算法2 所示。
算法2计算卸载算法（COA）
为了评估所提出的计算卸载算法的性能，使用SUMO 和MATLAB 进行了比较仿真。假设任务车辆和服务节点在任务完成之前连接不会断开，且传播速度不变。在迭代次数和种群大小相同的情况下，将文中提出的计算卸载算法（COA）与遗传算法（GA）的时延性能进行了比较，并通过枚举法（EM）得到的最优决策进行验证。SUMO 用于模拟道路和车辆的真实轨迹，70 辆汽车被放置在一条长度为1 500 m的6 车道道路上，模拟时间为100 s。任务大小范围为［10，250］ Mb，每10 Mb 为一个区间，每个区间随机生成20 个不同大小的任务，每个任务生成时间和网络条件均不同。主要仿真参数见表3。
表3 仿真参数设置
图3 显示了相同子任务数量的平均卸载时延的变化。可以看出，无论对于哪一种算法，时延都随着子任务数量的增加而降低，这是因为子任务的并行执行减少了整体完成时间，因此卸载时延与子任务的数量成反比。在平均卸载时延方面，文中提出的COA 性能明显优于GA，接近最优决策。COA 的平均时延仅比最优决策的平均时延高2.6%，而GA 的平均时延比相同任务规模的最优决策的平均时延高31.85%。在迭代次数和种群规模都相同的情况下，COA 的平均时延比GA 低20.1%。这是因为GA 没有考虑到子任务等待计算的时间过长的问题，从而导致总时延变大；
而COA 利用Johnson Rules 确定了子任务的最优执行顺序，使得子任务等待计算的时间减少，从而使得时延得以减少。从图中可以看出，COA 的曲线相对GA 来说更平滑，说明COA 的稳定性优于GA。这是因为GA 对初始种群的选择有一定的依赖性［19］，随机产生初始种群导致计算结果不稳定；
COA 在初始种群中引入了节点综合能力与任务大小的对应关系，对初始种群进行了优化，从而使得算法稳定性得以增强。
图3 平均卸载时延与子任务数量的关系
图4 显示了任务大小和时延之间的关系。可以看出时延随着数据大小的增加而增加，因此时延与任务大小成正比。在相同子任务数量的情况下，COA 的平均时延仅比最优决策的平均时延高1.97%，GA 的平均时延比最优决策的平均时延高27.7%。COA 的平均卸载时延比GA 低20.1%。
图5 对比了GA 和COA 的收敛性。从图中可以看出，在相同的迭代次数下，COA 的平均卸载时延更小。此外还可以看出COA 经过5 次迭代后，逐渐收敛至最优解，而GA 经过90 次迭代后才得到了局部最优解。因此，COA 的收敛速度和寻优结果都优于GA。这是因为GA 的交叉变异率会增加算法的迭代次数，对解的全局收敛性影响很大［19］；
COA考虑了卸载时延可能的最小值，对变异的判定标准和变异的操作进行了优化，从而提升了算法的全局收敛性。
图5 COA 和GA 收敛性对比
为了更好地服务于车辆和交通系统，文中提出了一种应用于车辆雾网络的计算卸载算法。在GA基础上结合两阶段生产计划模型对计算任务卸载调度问题进行建模分析，利用Johnson Rules 获取近似最优的卸载顺序。仿真结果表明，对于不同的任务规模和不同的子任务数量，该算法在平均卸载时延、稳定性和收敛性方面优于遗传算法，并且平均卸载时延接近理论上最优决策下的卸载时延。基于以上成果，在后续工作中将进一步研究具有依赖关系的计算卸载问题并考虑资源的可用性。
猜你喜欢 时延遗传算法调度 《调度集中系统(CTC)/列车调度指挥系统(TDCS)维护手册》正式出版铁道通信信号(2020年10期)2020-02-07一种基于负载均衡的Kubernetes调度改进算法成都信息工程大学学报(2019年3期)2019-09-25虚拟机实时迁移调度算法三门峡职业技术学院学报(2019年1期)2019-06-27基于GCC-nearest时延估计的室内声源定位电子制作(2019年23期)2019-02-23基于改进二次相关算法的TDOA时延估计测控技术(2018年6期)2018-11-25基于自适应遗传算法的CSAMT一维反演石油地球物理勘探(2017年2期)2017-11-23一种基于遗传算法的聚类分析方法在DNA序列比较中的应用中央民族大学学报（自然科学版）(2017年1期)2017-06-11基于遗传算法和LS-SVM的财务危机预测统计与决策(2017年2期)2017-03-20FRFT在水声信道时延频移联合估计中的应用系统工程与电子技术(2016年7期)2016-08-21基于分段CEEMD降噪的时延估计研究电测与仪表(2016年17期)2016-04-11