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

作者：张珂张利国来源：《自动化学报》日期：2022-08-26人气：1417

车联网技术能够实现车与车、车与路、车与基础设施的信息交换, 但对系统的实时性要求较高[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节点形成的移动拓扑结构, 按照计算需求的时间和空间约束进行计算任务的时空化研究, 建立了基于 $G I / G I / 1$ 排队模型的虚拟车任务队列. 根据任务到达时间、任务地点、任务量等研究任务分配问题, 利用虚拟化概念最大化智能车的利用程度, 提出了基于云平台Voronoi 的任务分配算法. 针对智能车局部任务队列, 引入虚拟服务时间、虚拟截止时间对任务执行模型进行约束. 最后以城市道路交通污染排放的实时计算为例, 讨论了分布式移动边缘计算方法的有效性.

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

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

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

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

Fig. 1 The MEC architecture for vehicle networks

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

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

(1)

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

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

(2)

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

(3)

其中, $T^{a r r}$ 表示任务到达时间; $t a s k^{X}$ 表示任务在空间中的位置, 可以用经纬度( $l a t$ , $l o n$ )表示; $T^{s}$ 表示任务量.

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

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

(4)

其中, $t c_{i}$ 为任务程序, 例如采样其他车辆信息并做交通污染估计; $t_{1}, t_{1} + k, \dots, t_{1} + (i - 1) k, \dots$ 为时钟序列, 时间间隔为 $k;$ 箭头表示的流是时空推进; $x_{1}, x_{1} + n, \dots, x_{1} +$ $(i - 1) n, \dots$ 为空间序列, 空间间隔为n.

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

(5)

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

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

(6)

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

2. MEC系统模型

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

2.1 虚拟车任务队列模型

由第1节基本概念可知, 智能车集合 $I V_{s} = {I V_{m}}_{m = 1}^{M},$ 虚拟车集合 $V V_{s} = {V V_{i}}_{i = 1}^{I} .$ 其中 $M$ 是确定的, $I$ 根据实际需求动态变化. 每辆智能车速度记为 $v^{I V},$ 虚拟车速度记为 $v^{V V},$ 虚拟车速度其实就是智能车在物理世界中行驶速度的映射.

虚拟车可以生成任务序列 ${⟨ T a s k_{i} (j) ⟩}_{j = 1}^{\infty},$ 表示第 $i$ 辆虚拟车产生的第 $j$ 个任务, 每个任务都包括了其到达时间 $T_{i}^{a r r} (j),$ 任务位置 $t a s k_{i}^{X} (j),$ 计算量 $T_{i}^{s} (j) .$ 任务序列 ${⟨ T a s k_{i} (j) ⟩}_{j = 1}^{\infty}$ 由不同的虚拟车产生且相互独立, 因此 $T a s k_{i} (j)$ 关于 $i$ 是相互独立的.

假设每个任务到达过程 ${T_{i}^{a r r} (j)}_{j = 1}^{\infty}$ 是一个更新过程. 则任务时间间隔 $I_{i}^{a r r} (j) = T_{i}^{a r r} (j) -$ $T_{i}^{a r r} (j - 1)$ 关于 $j$ 独立同分布. 其中 $T_{i}^{a r r} (0) \equiv 0,$ 所以每辆虚拟车的任务到达速率表示如下

(7)

式中, $λ_{i}^{V V}$ 表示第 $i$ 辆虚拟车的任务到达速率, $I_{i}^{a r r}$ 表示任务时间间隔的一般项, $E [I_{i}^{a r r}]$ 表示期望.

任务位置 $t a s k_{i}^{X} (j)$ 关于 $i$ 和 $j$ 独立同分布, 可以用经纬度来表示每辆虚拟车产生的每个任务地理位置, $t a s k_{i}^{X} (j) = (l a t_{i j}, l o n_{i j}),$ 其中 $l a t_{i j}$ 表示纬度, $l o n_{i j}$ 表示经度. 同样, 任务计算量 $T_{i}^{s} (j)$ 也是关于 $i$ 和 $j$ 独立同分布, 如果将 $T^{s}$ 作为 $T_{i}^{s} (j)$ 的一般项, 则有 $E [T^{s}] = E [T_{i}^{s} (j)] .$

虚拟车按照先到先服务 (First come first service, FCFS) 的策略执行任务序列 ${⟨ T a s k_{i} (j) ⟩}_{j = 1}^{\infty},$ 依次对指定地点 $t a s k_{i}^{X} (1),$ $t a s k_{i}^{X} (2), \dots$ 执行任务. 并分别执行计算任务时间 $T_{i}^{s} (1), T_{i}^{s} (2), \dots .$ 可以计算得到虚拟旅行时间

(8)

式中, $T_{i}^{V t r a} (j)$ 表示第 $i$ 辆虚拟车前往第 $j$ 个任务点的旅行时间; $D_{i}^{V} (j)$ 表示第 $j - 1$ 次任务位置 $t a s k_{i}^{X} (j - 1)$ 与第 $j$ 次任务位置 $t a s k_{i}^{X} (j)$ 的路径距离, 其中 $t a s k_{i}^{X} (0)$ 是指初始任务分配绑定到智能车时智能车的地理位置.

记任务 $T a s k_{i} (j)$ 的虚拟服务时间为 $T_{i}^{V s e r} (j),$ 包括前往指定位置的旅行时间和执行任务时间, 则

(9)

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

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

Fig. 2 Virtual vehicle task's deadline time calculation schematic diagram

记第 $i$ 辆虚拟车产生的第 $j$ 个任务的虚拟截止时间为 $T_{i}^{V d} (j)$ , 则有

(10)

其中 $T_{i}^{V d} (0) \equiv 0,$ 表示虚拟车无任务时其默认值为0. 当 $T_{i}^{a r r} (j) > T_{i}^{V d} (j - 1)$ 时, 即图2(a)所示; 当 $T_{i}^{a r r} (j) < T_{i}^{V d} (j - 1)$ 时, 即图2(b)所示.

因为每辆虚拟车产生的任务到达速率是 $λ_{i}^{V V} =$ $1 / E [I_{i}^{a r r}],$ 定义虚拟服务速率的一般形式为 $μ^{V V},$ 则有

(11)

同时, 输出的虚拟截止过程 ${T_{i}^{V d} (j)}_{j = 1}^{\infty}$ 是一个随机变量. 则虚拟截止速率如式(12)所示

(12)

如果用户提交了任务, 产生了任务队列, 则虚拟车 $V V_{i}$ 处于繁忙状态, 其工作状态记为 $S_{i} = 1$ ; 如果用户没有提交任务, 则虚拟车处于空闲状态, 记为 $S_{i} = 0.$ 虚拟车 $V V_{i}$ 将呈周期性循环这两种状态. 定义 $T_{i}^{V b u s y} (l)$ 为第 $l$ 次繁忙状态时间, $T_{i}^{V i d l e} (l)$ 为第 $l$ 次空闲状态时间, 则定义第 $i$ 辆虚拟车的利用率为

(13)

因为任务到达时间间隔输入和服务时间都是独立同分布的变量, 则虚拟车的任务队列构成了 $G I / G I / 1$ 队列模型, 用户按照自己选择的任务到达速率创建任务提交到虚拟车. 当 $λ_{i}^{V V} < μ^{V V}$ 时, 虚拟截止率等于到达率, 即 $λ_{i}^{V d} = λ_{i}^{V V}$ . 如果用户提交任务频繁, 超过了约定速度确定的服务速率, 此时 $λ_{i}^{V V} \geq μ^{V V},$ 那么虚拟截止速率等于服务速率, 即 $λ_{i}^{V d} = μ^{V V}$ .

2.2 云平台调度模型

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

智能车上的导航定位装置可实时获取其地理位置坐标. 记 $t$ 时刻 $M$ 辆智能车的位置集合为 $p^{I V} (t) =$ ${p_{m}^{I V} (t)}_{m = 1}^{M},$ 其中 $p_{m}^{I V} (t) = (l a t_{m}, l o n_{m}),$ 表示编号为 $m$ 的智能车的经纬度坐标. $t$ 时刻虚拟车上生成的计算任务地点由第2.1节可知 $p^{V V} (t) =$ ${t a s k_{i}^{X} (t)}_{i = 1}^{I},$ 其中第 $i$ 辆虚拟车产生任务的地理位置坐标 $t a s k_{i}^{X} (t) =$ $(l a t_{i}, l o n_{i})$ .

给定时间 $t$ , Voronoi分配算法表示如下

(14)

式中, $V o r A l l o c a t i o n$ 为分配算法函数, 该函数接受三个参数; $A$ 为智能车覆盖的服务区域, 包含 $A$ 区域交通路网中的node节点和edge边的数据信息; $t a s k_{i}^{X} (t)$ 是 $t$ 时刻第 $i$ 辆虚拟车到达任务的位置; $p^{I V} (t)$ 是 $t$ 时刻智能车的地理位置; $r \in {1, \dots, M}$ 表示分配的智能车编号.

根据 $A$ 区域中有 $M$ 辆智能车, Voronoi分配算法利用连续多中值均匀产生的 $M$ 个点将 $A$ 区域细分为 $M$ 个子区域, 每个子区域是一个Voronoi单元, 则 $A = {V o r C e l l_{m}}_{m = 1}^{M}$ . $M$ 辆智能车分别被派到 $M$ 个子区域中的中值点等待计算任务分配. 此时 $M$ 个中值点即为智能车的初始位置 $p_{m}^{I V} (0)$ . 则Voronoi单元表示如下

(15)

式中, $V o r C e l l_{m}$ 表示第 $m$ 个Voronoi单元; $y$ 为 $A$ 区域的任意一点; $p_{m}^{I V} (0)$ 为第 $m$ 辆智能车的初始位置; $p_{k}^{I V} (0)$ 表示除第 $m$ 辆智能车外的其他智能车初始位置, 故 $k \neq m .$

对于任意的 $t > 0, p_{m}^{I V} (t) \in V o r C e l l_{m} .$ 当虚拟车产生任务指定地点 $t a s k_{i}^{X} (t)$ 时, 如果 $t a s k_{i}^{X} (t) \in$ $V o r C e l l_{m},$ 那么该任务落入第 $m$ 个Voronoi单元, 将该任务分配给该单元的智能车.

2.3 智能车局部队列模型

智能车针对落入该子区域的任务将生成一个新的任务序列 ${⟨ T a s k_{m} (n) ⟩}_{m = 1}^{\infty},$ 任务 $T a s k_{m} (n)$ 表示分配的第 $n$ 个任务将由编号为 $m$ 的智能车前往执行.

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

(16)

其中, $ϕ$ 为集合中的调度策略. 定义 $D_{m}^{I} (n)$ 为在使用调度策略后的第 $n - 1$ 次任务和第 $n$ 次任务间的旅行距离, 则可计算出智能车实际的旅行时间, 记为

(17)

式中, $T_{m}^{I t r a} (n)$ 表示第 $m$ 辆智能车进行第 $n$ 次任务的服务时间, $v^{I V}$ 为平均速度. 记其任务执行时间为 $T_{m}^{I s} (n),$ 则智能车实际的服务时间就是

(18)

令 $T_{m}^{I s e r ϕ}$ 表示在调度策略 $ϕ$ 下的服务总时间, 则我们希望找到服务总时间最小的调度策略

(19)

式中, $ϕ^{o p t i m a l}$ 表示最优策略, 智能车将按照该调度策略执行任务. 记智能车实际完成任务的服务速率一般项为 $μ^{I V},$ 则有

(20)

同时记智能车实际完成任务时间为 $T_{m}^{f i n i s h} (n) .$ 因为虚拟车显示的速度是物理世界中智能车速度的映射, 假设用户不会频繁提交任务, 这样系统便是稳定的. 在此定义 $κ$ 为映射程度[29], 其表示为

(21)

式中, $μ^{I V}$ 表示智能车服务速率, $μ^{V V}$ 表示虚拟车服务速率. 若 $κ$ 接近1, 说明智能车与虚拟车服务速率匹配; 若 $κ$ 较大, 则说明智能车的服务速率较差.

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

图 3 基于Voronoi分配算法的任务队列调度模型图

Fig. 3 Task queue scheduling model diagram based on Voronoi allocation algorithm

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

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

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

3. 道路交通污染排放计算

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

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

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

(22)

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

(23)

式中, $v$ 为机动车瞬时速度( $m / s$ ); $a$ 为机动车瞬时加速度( $m / s^{2}$ ); $g r a d e$ 为道路坡度, 当机动车在城市道路中行驶时道路坡度取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

VSP 等级	VSP mode	$C O_{2} (g / s)$	$C O (g / s)$	$N O_{X} (g / s)$	$H C (g / s)$
$V S P < - 2$	1	1.54369	0.01103	0.00101	0.00090
$- 2 \leq V S P < 0$	2	1.60441	0.00872	0.00104	0.00090
$0 \leq V S P < 1$	3	1.13083	0.00468	0.00042	0.00084
$\cdot \cdot \cdot$	$\cdot \cdot \cdot$	$\cdot \cdot \cdot$	$\cdot \cdot \cdot$	$\cdot \cdot \cdot$	$\cdot \cdot \cdot$
$28 \leq V S P < 33$	12	7.61770	0.24781	0.01438	0.00457
$33 \leq V S P < 39$	13	8.32244	0.41307	0.01597	0.00570
$39 \leq V S P$	14	8.47503	0.62466	0.01672	0.00716

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

4. 仿真实验

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

在Eclipse工程实验中, 我们设计了如图4所示的MEC调度系统仿真模式类图, 创建了VirtualVehicle, TaskData, GlobalQueue, Scheduler, IntelligentVehicle 5个类, 从而建立了运行时仿真环境. 其中VirtualVehicle可以创建多个线程实例, 按照设定的到达规律生成任务TaskData, 这里时间间隔由sleep (InterArrivalTime)函数实现. TaskData作为容器将保存虚拟车生成的任务信息. 在运行时环境下, VirtualVehicle将生成TaskData任务对象保存到自己的队列中, 并发送到全局队列, 全局队列由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 V_{i},$ $m$ 个IntelligentVehicle线程实例 $I V_{m}$ ;

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

5) $V V_{i}$ 生成任务, TaskData存储任务的到达时间、地理位置、任务量;

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

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

8) $V V_{i}$ 将任务打包发送到Channel通道中的全局任务队列;

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

10) 智能车 $I V_{m}$ 将接收到的任务放入自己的局部队列, 按照式(16)调度策略及式(17) ~ 式(19) 分别计算 $T_{m}^{I s e r ϕ}$ ;

11) 重复步骤4) 至步骤10), 直至达到额定任务数量, 求得服务总时间最小的调度策略 $ϕ^{o p t i m a l}$ .

实验调用API从Open Street Map获取以北京工业大学为中心, 方圆3000米范围的交通路网拓扑图作为实验区域数据. 任务处理过程中的其中6个任务分配结果如图5所示, 最底层是交通路网, 9个方块表示在 $A$ 区域内提供边缘计算的智能车, 圆点表示虚拟车发出的计算任务位置, 通过Voronoi算法可以计算得到分界线, 将该区域分成了9个Voronoi单元, 区域索引与智能车索引相同. 创建9个IntelligentVehicle线程实例模拟9辆智能车, 随机产生9个均匀分布在路网中的地理位置坐标作为智能车初始位置坐标, 如图5(a)中的方块所示. 创建16个VirtualVehicle线程实例模拟16辆虚拟车, 每辆虚拟车都将按照不同的分布规律产生50个任务, 任务被动态地发送到全局队列. Scheduler按照式(15)将该区域分成9个Voronoi单元, 即 $A = {V o r C e l l_{m}}_{m = 1}^{9},$ 逐个将全局队列中的任务取出, 按照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矩阵将普通车辆放入仿真的真实场景中, 然后放入智能车 $I V_{5}$ 作为控制对象. 通过Aimsun API编写程序模拟 $I V$ 执行任务, 落入第5单元区域的任务被 $I V$ 生成局部任务序列 ${⟨ T a s k_{5} (n) ⟩}_{n = 1}^{6},$ 其任务地点标注如图7中的圆点所示, 智能车 $I V_{5}$ 初始位置如图7中车辆所示.

图 7 交通污染排放计算的智能车调度策略

Fig. 7 Intelligent vehicle scheduling strategy for traffic pollutant emission computing

仿真程序按照FCFS调度策略执行任务. 读取第一个任务地点 $t a s k_{5}^{X} (1),$ 智能车所在地点 $p_{5}^{I V} (0),$ 计算得到第一次执行任务地点与智能车初始位置之间的距离 $D_{5}^{I} (1),$ 通过获取路段平均车速可以计算出智能车到达任务点所在路段的实际旅行时间 $T_{5}^{I t r a} (1)$ . 同理计算出智能车通过任务地点所在路段的时间, 这段时间也是智能车执行任务时间, 即 $T_{5}^{I s} (1)$ .

通过式 (18) 可以得到实际服务时间 $T_{5}^{I s e r} (1),$ 即智能车需要提供服务的时间. 智能车物理移动前往任务地点, 按照虚拟截止时间约束完成计算任务.

实验中设置跟踪模式, 记录车辆实际旅行时间、实际执行任务时间、实际服务时间和实际完成任务时间. 第一个交通污染排放计算任务完成后, 程序将控制智能车前往第二个任务地点 $t a s k_{5}^{X} (2)$ 执行交通污染排放计算任务. 同理, 智能车将依次按照任务分配前往 $t a s k_{5}^{X} (3) \sim t a s k_{5}^{X} (6)$ 执行任务. $V V_{s}$ 发出的任务计算参数如表2所示.

表 2 VVs的任务计算参数

Table 2 VVs calculation parameters

$T a s k_{i} (j)$	$T_{i}^{a r r} (j)$	$t a s k_{i}^{X} (j)$	$T_{i}^{V t r a} (j)$	$T_{i}^{s} (j)$	$T_{i}^{V s e r} (j)$	$T_{i}^{V d} (j)$
$i = 2, j = 2$	9:09:02	(39.8726, 116.466)	89	169	258	9:13:20
$i = 3, j = 3$	9:13:37	(39.8702, 116.476)	110	80	190	9:16:47
$i = 7, j = 1$	9:16:52	(39.875, 116.475)	200	60	260	9:21:12
$i = 9, j = 6$	9:21:14	(39.8787, 116.471)	0	52	52	9:22:06
$i = 12, j = 3$	9:22:06	(39.8767, 116.466)	78	60	138	9:24:24
$i = 15, j = 4$	9:24:34	(39.8705, 116.466)	40	43	83	9:25:57

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

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

5. 结论

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

表 3 IV的实际运行参数

Table 3 Actual operating parameters of IV

$T a s k_{m} (n)$	$T_{m}^{I t r a} (n)$	$T_{m}^{I s} (n)$	$T_{m}^{I s e r} (n)$	$T_{m}^{f i n i s h} (n)$	${C O}_{2} (g)$	$C O (g)$	${N O}_{X} (g)$	$H C (g)$
$m = 5, n = 1$	95	178	273	9:13:35	992.78	6.76	0.81	0.51
$m = 5, n = 2$	117	76	193	9:16:50	1144.42	7.76	0.79	0.63
$m = 5, n = 3$	202	58	260	9:21:12	426.80	2.96	0.29	0.24
$m = 5, n = 4$	0	50	50	9:22:04	590.63	4.11	0.41	0.33
$m = 5, n = 5$	83	63	146	9:24:32	1658.42	11.41	1.14	0.92
$m = 5, n = 6$	37	39	46	9:25:20	868.51	5.92	0.61	0.48

关键字：优秀论文

上一篇：高通量抗污染氧化石墨烯膜研究进展
下一篇：污水处理过程递推双线性子空间建模及无模型自适应控制

栏目分类

热门排行

推荐信息

期刊知识