引用本文

张珂, 张利国. 基于移动边缘计算的GI/GI/1排队建模与调度算法. 自动化学报, 2022, 48(7): 1737−1746 doi: 10.16383/j.aas.c190902

Zhang Ke, Zhang Li-Guo. GI/GI/1 queuing model and task scheduling for mobile edge computing. Acta Automatica Sinica, 2022, 48(7): 1737−1746 doi: 10.16383/j.aas.c190902

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190902

关键词

车联网，移动边缘计算，排队模型，调度，分配算法 

摘要

针对车联网环境下路侧边缘计算节点部署不均衡、服务密度小、实时调度计算压力大等问题, 提出一种基于智能车移动边缘计算(Mobile edge computing, MEC)的任务排队建模与调度算法, 提供弹性计算服务, 将具备感知、计算、控制功能的智能车作为移动边缘计算服务器, 设计了车联网环境下的MEC体系架构. 首先基于虚拟化技术对智能车进行虚拟化抽象, 利用排队论对虚拟车任务构建了GI/GI/1排队模型. 然后基于云平台Voronoi分配算法对虚拟车任务进行分配绑定, 进而实现了智能车的优化调度与分布式弹性服务, 解决了边缘计算任务分配不均衡等问题. 最后通过城市交通路网中的车辆污染排放的实时计算实验, 验证了该方法的有效性.

文章导读

车联网技术能够实现车与车、车与路、车与基础设施的信息交换, 但对系统的实时性要求较高[1-4]. 如果采用集中式的数据处理模式, 即数据回传数据中心进行计算处理, 则会产生较大时延.

最近兴起的边缘计算(Edge computing, EC)融合了网络、计算、存储等核心使能, 分布式部署于靠近物或数据源头, 是就近提供应用服务的新型计算模型[5-9]. 车联网中的边缘计算[10]主要是基于路侧单元(Road side units, RSU)进行的. 将边缘计算服务器直接部署于道路两侧, 可以将更多的数据计算和存储从“数据中心”转移到“路侧单元”, 部分数据不必再经过网络上传云端处理, 而在本地完成数据交换及自主决策. 从而降低了网络时延和负荷, 有效减少网络传输量, 避免网络拥塞, 同时也提升了数据安全性和应用可靠性. 然而, 一方面由于车辆的移动特点, 车载单元将频繁与不同的路侧单元进行信息交互, 路侧单元间也频繁地转移计算任务, 密集信息交互带来了不稳定性[11-13], 降低了任务传输的可靠性与安全性[14]; 另一方面交通波动导致任务不均衡[15], 路侧单元部署规模大、 成本高, 有些路段可能没有部署边缘计算服务器却有较大的边缘计算需求. 边缘计算任务的空间分布是不确定的, 固定在路侧单元的边缘计算服务器无法对一些指定地点和时间的任务提供服务[16], 如何实现边缘计算服务器的空间优化配置成为了一项重要工作.

智能车的快速发展为上述问题提供了全新的解决思路. 它们通常装备了大量的计算单元、通信设备、传感器和人机交互设备[17-20]. 例如, 百度的无人驾驶汽车 “阿波罗” 装载了价值近百万元的计算机系统进行存储和运算, 用来分析车辆周边人、车、道路与环境[21-22]. 此外, 在智能车与其他车辆行驶中将形成相对静止关系, 此时提供移动边缘计算(Mobile edge computing, MEC)将有效提升实时性与稳定性[23-26].

本文提出一种车联网环境下的MEC架构. 与基于路侧单元的边缘计算相比, 此类MEC范式最大的不同之处在于: 其依赖于具有感知、计算、控制、通信能力的智能车在交通路网中提供弹性的边缘计算服务[27-31]; 智能车作为分布式MEC节点, 执行局部、实时、短周期数据的处理与分析.

本文重点研究了MEC节点形成的移动拓扑结构, 按照计算需求的时间和空间约束进行计算任务的时空化研究, 建立了基于GI/GI/1排队模型的虚拟车任务队列. 根据任务到达时间、任务地点、任务量等研究任务分配问题, 利用虚拟化概念最大化智能车的利用程度, 提出了基于云平台Voronoi 的任务分配算法. 针对智能车局部任务队列, 引入虚拟服务时间、虚拟截止时间对任务执行模型进行约束. 最后以城市道路交通污染排放的实时计算为例, 讨论了分布式移动边缘计算方法的有效性.

本文结构如下: 第1节介绍了车联网环境下的MEC体系架构和任务分配算法; 第2节建立了MEC系统模型; 第3节介绍了道路交通污染排放计算任务; 第4节进行了仿真实验分析; 第5节总结与展望.

图 1  车联网环境下的MEC体系架构

图 2  虚拟车任务虚拟截止时间计算示意图

图 4  MEC调度系统仿真模式类图

本文设计了一种智能车联网环境下的MEC体系架构. 采用虚拟化技术对智能车计算资源进行了虚拟化抽象, 构建了虚拟车服务任务的GI/GI/1排队模型, 同时基于云平台的Voronoi分配算法, 对虚拟车任务进行了分配绑定, 进而实现了智能车的优化调度与分布式弹性服务, 解决了边缘计算任务分配不均衡问题. 下一步, 一个重要的研究方向是讨论MEC优化调度任务的实时性.

作者简介

张珂

北京工业大学信息学部控制科学与工程专业硕士研究生. 2017年获得河南理工大学自动化专业学士学位. 主要研究方向为智能交通系统, 移动边缘计算.E-mail: zhgke766@126.com

张利国

北京工业大学信息学部控制科学与工程专业教授. 2011–2012年国家公派美国加州大学伯克利分校访问学者. 主要研究方向为混杂系统, 智能交通系统和分布式参数控制系统. 本文通信作者.E-mail: zhangliguo@bjut.edu.cn