基于移动边缘计算的GI/GI/1 排队建模与调度算法

张 珂 张利国

车联网技术能够实现车与车、车与路、车与基础设施的信息交换,但对系统的实时性要求较高[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 体系架构

本节设计了如图1 所示的车联网环境下时空采样计算的MEC 体系架构.

图1 车联网环境下的MEC 体系架构Fig.1 The MEC architecture for vehicle networks

该体系架构分为三层:物理层、应用层、云端层.物理层由道路车辆形成的车联网组成,通过短程通信技术进行信息交换.应用层由部署在城市交通路网中的智能车组成,数据处理和交通信息计算服务部署于智能车上进行.云端层拥有更多的计算和存储资源,智能车动态感知交通信息后,通过云端的边缘接入上传自身信息与交通信息,云端利用移动拓扑结构对智能车进行调度.

假设交通路网中有M辆具有车载边缘计算服务器的智能车提供分布式服务,记作

集合中下标表示智能车的编号,所有智能车在路网中形成了移动拓扑结构,而每辆智能车负责一个子区的计算任务.由于智能车可以在交通路网中移动,因而车载服务器具有空间属性和速度属性.

为实现多用户可以独立使用智能车而互相不受影响,应用云计算范式对智能车进行虚拟化,则用户可在云端购买虚拟车(Virtual vehicles,VV),以此获得智能车的某些计算或控制服务,该虚拟车反映了智能车的空间属性和速度属性.记用户购买的I辆虚拟车集合

集合中下标表示虚拟车的编号.对于用户而言,事先并不知道智能车的分布情况,只需要在云端购买一辆虚拟车,指定特定地点的计算任务即可.特定地点的计算任务通常可以表示为

其中,Tarr表示任务到达时间;taskX表示任务在空间中的位置,可以用经纬度(lat,lon)表示;Ts表示任务量.

在多任务情况下,虚拟车必须完全隔离,因此需要对虚拟车进行时空建模,描述其在时间和空间上的计算行为.

边缘计算中的核心使能技术是虚拟化,通过虚拟化技术将物理层的CPU、内存、传感器等硬件资源映射到虚拟层上,用户任务通过虚拟车的时空推进程序,利用智能车的传感器、计算资源、控制器、通信设备与周围环境进行交互.则虚拟车任务可以看成一种离散的时空推进模型,这里引入Plotkin符号语义[32]如下

其中,tci为任务程序,例如采样其他车辆信息并做交通污染估计;t1,t1+k,···,t1+(i −1)k,···为时钟序列,时间间隔为k; 箭头表示的流是时空推进;x1,x1+n,···,x1+ (i −1)n,···为空间序列,空间间隔为n.

当n0 时,表示时间上推进而空间上没有推进,此时虚拟车处于静止状态,可以表示为

此时虚拟车可以在某一位置提供MEC 服务.

同样,有些空间工程采样并不需要时间参考,此时虚拟车仅在空间上推进,其空间推进模型可以表示为

利用时空推进模型可以指定智能车的行为,为保证MEC 云平台的调度系统能够快速响应,需要进行MEC 调度系统建模.

2 MEC 系统模型

MEC 中资源调度的实质是根据虚拟车产生的不同计算任务、任务到达时间、任务类型等,云端调度系统选择合适的智能车前往特定地点执行计算任务,为此需要研究调度模型以最大化利用智能车资源.在MEC 中已经实现了资源的虚拟化.本节将进行MEC 系统建模.

2.1 虚拟车任务队列模型

事实上,虚拟服务时间与物理世界中的智能车服务时间会有偏差,因此设定虚拟截止时间作为对智能车的约束.而虚拟截止时间的计算是以任务到达时间算起,如果第j次任务到达时上次任务仍在进行中,则应当以第j −1 次任务的虚拟截止时间算起,两种任务虚拟截止时间计算情况如图2所示.

图2 虚拟车任务虚拟截止时间计算示意图Fig.2 Virtual vehicle task's deadline time calculation schematic diagram

2.2 云平台调度模型

MEC 调度系统中有M辆智能车运行在路网中,虚拟车产生的每个特定地点计算任务都需要由实体的智能车来完成,也就是计算任务Taski(j) 按照某种分配机制分配给智能车中的某辆车去执行.从第2.1 节可知,在时变环境中,虚拟车产生的计算任务是一个排队过程,是有时间限制的.为了更高效地提供计算服务,最小化任务的预期系统时间,本节采用分布式自适应策略,引入一种Voronoi 分配算法来解决该问题.

式中,VorAllocation 为分配算法函数,该函数接受三个参数;A为智能车覆盖的服务区域,包含A区域交通路网中的node 节点和edge 边的数据信息;是t时刻第i辆虚拟车到达任务的位置;pIV(t)是t时刻智能车的地理位置;r∈{1,···,M}表示分配的智能车编号.

根据A区域中有M辆智能车,Voronoi 分配算法利用连续多中值均匀产生的M个点将A区域细分为M个子区域,每个子区域是一个Voronoi 单元,则辆智能车分别被派到M个子区域中的中值点等待计算任务分配.此时M个中值点即为智能车的初始位置则Voronoi 单元表示如下

2.3 智能车局部队列模型

在实际任务执行中,虚拟服务时间与物理世界中的智能车服务时间会有偏差.智能车利用排队论的调度策略,包括先到先服务(First come first service,FCFS),即最先到达队列的任务最先进行服务;最早截止优先服务(First deadline first service,FDFS),即按照截止时间先后顺序重新进行排序,依次进行服务;信用优先服务(Credit first service,CFS),将信用分为2、4、6、8、10 五个等级,按照优先级大的依次进行服务.通过对比,按照时间最优的策略执行任务,令 Φ 表示调度策略,则有

其中,φ为集合中的调度策略.定义为在使用调度策略后的第n−1次任务和第n次任务间的旅行距离,则可计算出智能车实际的旅行时间,记为

式中,φoptimal表示最优策略,智能车将按照该调度策略执行任务.记智能车实际完成任务的服务速率一般项为µIV,则有

式中,µIV表示智能车服务速率,µVV表示虚拟车服务速率.若κ接近1,说明智能车与虚拟车服务速率匹配;若κ较大,则说明智能车的服务速率较差.

由此可以得到如图3 所示的任务队列调度模型图,一个调度模型通常由输入任务、调度决策、任务执行体组成.已知虚拟车产生的任务到达速率以及Voronoi 分配算法,则其调度流程如下.

图3 基于Voronoi 分配算法的任务队列调度模型图Fig.3 Task queue scheduling model diagram based on Voronoi allocation algorithm

1) 输入任务:MEC 资源池中的各个任务相互独立,并且各个任务到达速率为即单位时间间隔内有个任务到达.所有虚拟车的任务到达云平台调度中心构成全局任务队列.

2) 调度决策:任务到达云平台调度中心后,根据Voronoi 分配算法,判断各个任务地点落入哪一Voronoi 单元,然后将该任务分配给该单元内的智能车,即

3) 任务执行体:同一虚拟车的任务落入不同的Voronoi 单元,将由不同的智能车进行计算服务,所以M辆智能车都有自己的局部任务队列.智能车将按照局部调度策略对任务队列进行任务排序,依次对指定地点执行MEC 任务,并在时间期限内完成计算任务.

3 道路交通污染排放计算

随着电动车、机动车、混合动力车等多能源结构汽车上路,将呈现出混合交通流的趋势.原来利用宏观交通流数据作机动车尾气排放计算的方法已不再适用,而交通管理部门对准确反映且灵活地获取某一地点的交通污染排放情况有着强烈的需求.

为完成混合交通流下的移动交通污染排放计算任务,本文提出将VSP (Vehicle specific power)模型部署在智能车上.即交管部门提交计算任务地点与计算量后,系统根据任务地点落入哪一Voronoi单元而将任务分配给该单元内的智能车,智能车利用短程通信技术与指定路段的车辆建立通信,发起信息获取请求,收集道路上车辆类型、运行数据,利用VSP 模型执行交通污染排放的动态测算任务.

VSP 理论的物理意义是瞬态机动车输出功率与机动车质量的比值,与车辆的瞬态排放具有较强的相关性,能够评价以秒为单位的瞬间排放量.不同的机动车类型具有不同的VSP 计算公式,根据已有研究,我国城市小型轿车的交通污染排放可以简化为由速度、加速度和坡度组成的VSP 表达式,如式(22)所示

商务车VSP 的计算公式,如式(23)所示

式中,v为机动车瞬时速度(m/s);a为机动车瞬时加速度(m/s2);grade为道路坡度,当机动车在城市道路中行驶时道路坡度取0.

从式(22)、式(23)可以看出,想要计算一辆机动车的VSP 值需要获取车辆类型、瞬时速度、瞬时加速度等参数,而车辆移动传感技术 (如GPS、陀螺仪、加速度计等微传感器) 迅猛发展使得获取这些参数成为可能.智能车获得该路段内的车辆类型、速度、加速度、坡度等信息后,根据VSP 计算公式得到每辆车的VSP 值,结合BIN方法便能够对排放因子进行分析计算,对照VSP BIN 表1 即可获得不同类型的机动车瞬时排放量.将该路段的车辆瞬时排放进行累加便可得到路段的交通污染排放水平.

表1 VSP 排放等级与平均排放清单Table 1 VSP modes and the average modal emission rates of each

本节提出利用智能车MEC 技术前往指定路段执行交通污染排放计算任务,为了验证系统的有效性和任务流程的可行性,将进行仿真实验进行相应的实验验证.

4 仿真实验

本文在Eclipse 中搭建仿真项目,部署调度模型算法,验证系统模型的有效性.并在仿真软件Aimsun 中进行交通污染排放计算任务调度实验,建立仿真地图、路网、交通路况等.通过Aimsun API 接口编写算法控制智能车前往指定地点执行任务,记录各阶段时间,最后进行分析.

在Eclipse 工程实验中,我们设计了如图4 所示的MEC 调度系统仿真模式类图,创建了VirtualVehicle,TaskData,GlobalQueue,Scheduler,IntelligentVehicle 5 个类,从而建立了运行时仿真环境.其中VirtualVehicle 可以创建多个线程实例,按照设定的到达规律生成任务TaskData,这里时间间隔由sleep (InterArrivalTime) 函数实现.TaskData 作为容器将保存虚拟车生成的任务信息.在运行时环境下,VirtualVehicle 将生成Task-Data 任务对象保存到自己的队列中,并发送到全局队列,全局队列由ArrayBlockingQueue 实现.可以实现VirtualVehicle 和Scheduler 的互斥操作,保证全局队列中数据的安全性.全局队列的大小是动态变化的,Scheduler 可以从全局队列中取出任务并按照任务地点落入Voronoi 单元的编号将任务对象发送给对应的IntelligentVehicle.GlobalQueue和Scheduler 在此承担了信息通道(Channel)的作用,IntelligentVehicle 拥有本地调度器,将根据不同的调度规则计算服务总时间,并得到最优的调度策略.

图4 MEC 调度系统仿真模式类图Fig.4 Simulation mode class diagram of MEC scheduling system

算法操作步骤如下:

1) 设定虚拟车数量i和智能车数量m;

2) 设定全局任务队列阈值;

3) 实例化i个VirtualVehicle 线程实例V Vi,m个IntelligentVehicle 线程实例IVm;

4) 设定V Vi产生任务的时间到达规律参数、任务地点范围、任务量及范围;

5)V Vi生成任务,TaskData 存储任务的到达时间、地理位置、任务量;

6) 按照式(9)计算虚拟服务时间;

7) 按照式(10)计算虚拟截止时间;

8)V Vi将任务打包发送到Channel 通道中的全局任务队列;

9) 调度器Scheduler 从全局任务队列取出任务,按照式(14)、式(15)将任务分配到对应的智能车IVm;

10) 智能车IVm将接收到的任务放入自己的局部队列,按照式(16)调度策略及式(17)～式(19)分别计算

11) 重复步骤4) 至步骤10),直至达到额定任务数量,求得服务总时间最小的调度策略φoptimal.

实验调用API 从Open Street Map 获取以北京工业大学为中心,方圆3 000 米范围的交通路网拓扑图作为实验区域数据.任务处理过程中的其中6 个任务分配结果如图5 所示,最底层是交通路网,9 个方块表示在A区域内提供边缘计算的智能车,圆点表示虚拟车发出的计算任务位置,通过Voronoi 算法可以计算得到分界线,将该区域分成了9 个Voronoi 单元,区域索引与智能车索引相同.创建9个IntelligentVehicle 线程实例模拟9 辆智能车,随机产生9 个均匀分布在路网中的地理位置坐标作为智能车初始位置坐标,如图5(a)中的方块所示.创建16 个VirtualVehicle 线程实例模拟16 辆虚拟车,每辆虚拟车都将按照不同的分布规律产生50个任务,任务被动态地发送到全局队列.Scheduler 按照式(15)将该区域分成9 个Voronoi 单元,即逐个将全局队列中的任务取出,按照Voronoi 分配算法进行分配.

图5 基于Voronoi 算法的任务分配结果示意图Fig.5 Allocation result based on Voronoi algorithm

智能车根据FCFS,FDFS,CFS 调度策略对局部任务队列进行计算,得到各自最优的调度策略.在FCFS,FDFS,CFS 三种调度算法下的智能车服务时间对比结果如图6 所示.

图6 FCFS,FDFS,CFS 调度算法下智能车服务时间对比Fig.6 Service time comparison under scheduling algorithm of FCFS,FDFS,CFS

调度完成后在Aimsun 中模拟智能车提供交通污染排放计算服务的任务场景.利用OSMnx 库可以获取北京市朝阳区的交通路网GIS 数据,利用Aimsun 仿真软件中的插件GIS Importer 将该数据导入Aimsun 生成路网,建立交通网络.

选择图5 中的第5 辆智能车所在区域 (中间区域) 作为实验区域,根据OD 矩阵将普通车辆放入仿真的真实场景中,然后放入智能车IV5作为控制对象.通过Aimsun API 编写程序模拟IV执行任务,落入第5 单元区域的任务被IV生成局部任务序列其任务地点标注如图7 中的圆点所示,智能车IV5初始位置如图7 中车辆所示.

图7 交通污染排放计算的智能车调度策略Fig.7 Intelligent vehicle scheduling strategy for traffic pollutant emission computing

仿真程序按照FCFS 调度策略执行任务.读取第一个任务地点,智能车所在地点计算得到第一次执行任务地点与智能车初始位置之间的距离通过获取路段平均车速可以计算出智能车到达任务点所在路段的实际旅行时间同理计算出智能车通过任务地点所在路段的时间,这段时间也是智能车执行任务时间,即

表2 VVs 的任务计算参数Table 2 VVs calculation parameters

执行交通污染排放计算任务时,采用Plotkin时空推进式(4),设置程序时间间隔为1 s,同时仿真步长设置成1 s.智能车可以获得该路段所有车辆的动态信息,通过获取不同车辆的瞬时速度v和加速度a,利用VSP 模型可以得到每辆车的VSP值,根据BIN 方法得到每辆车的瞬时排放,将计算得到的所有值进行累加得到该路段的整体交通污染排放情况.在此过程中,智能车的实际运行参数以及在每次任务中计算得到的交通污染排放情况如表3所示.

表3 IV 的实际运行参数Table 3 Actual operating parameters of IV

由式(7)、式(11)可知,任务到达速率λVV0.375,虚拟服务速率µVV0.448,此时λVV <µVV.经计算得到智能车真实服务速率µIV0.476,通过式(21)得到κ1.0625,接近1.由文献[29]可知映射程度较好,提高了智能车的计算资源利用率.

5 结论

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