Optimal Packet Scheduling Strategy for Roadside Units＇ Bursty Traffic Based on Relaying Vehicles
-
摘要:
高速公路车联网场景中, 路边单元(Roadside units, RSUs)可作为多种周边监测数据的汇入网关, 其业务具有突发特性, 且可通过移动车辆以“存储−载带−转发”方式传输到与骨干网络互联的RSU. 针对RSU间业务传输问题, 源RSU可根据实时业务到达率按需匹配资源, 以应对业务突发性对分组端到端时延的影响. 本文首先针对RSU突发业务传输过程建立突发业务到达模型、车辆到达模型和离散车速状态模型; 进而利用受限马尔科夫决策过程对系统状态转移过程进行分析, 并建立非线性平均端到端时延最小化问题; 最后通过分析最优解的形式得出最优分组调度策略具有门限结构. 仿真结果验证了RSU间业务传输过程中排队时延和传播时延之间存在折中, 且该分组调度策略能降低业务传输过程的平均端到端时延.
Abstract:In the highway Internet of vehicles scenario, the roadside units (RSUs), whose generated traffic has burst characteristic, served as the gateway of multiple kinds monitored data. Those fused data can be transmitted to the RSU connected with the backbone network through the passing vehicles which serve as opportunistic store-carry-forward devices. For traffic transmission between the RSUs, the source RSU should match resource according to arrival rate of bursty traffic, to control the bursty impact on end-to-end delay. Firstly, the bursty traffic arrival model, the vehicles arrival model, and discrete speed states model were established for bursty traffic transmission between RSUs. Then, the state transition processes were analyzed by constrained Markov decision process, and a non-linear average end-to-end delay minimization problem is established. Finally, it is concluded that the optimal packet scheduling strategy has a threshold structure by analyzing the structure of the optimal solution. The simulation results show that the packet scheduling strategy can reduce the average end-to-end delay of bursty traffic transmission between the RSUs, and verify the tradeoff between average queuing delay and the propagation delay.
-
Key words:
- Internet of vehicles /
- roadside unit /
- busty traffic /
- packet scheduling /
- store-carry-forward
-
车联网作为协同车 − 路 − 环境的开放融合网络系统, 可为智能交通系统管理和控制提供新思路和手段[1], 还可作为物联网实体为道路及周边的事件监测作传输载体[2].
高速公路沿线部署多个RSU给行驶车辆提供信息服务是车联网的重要应用场景. RSU不仅可作为经过其无线覆盖范围内过往车辆的互联网接入设备; 部分RSU还承担着其周边交通状况、环境监测、自然灾害及动物活动信息的收集和转发功能. 为了降低高速公路车联网中通信基础设施的部署开销, 部分RSU与骨干网络处于隔离状态[3]. 孤立RSU可通过移动车辆以“存储 − 载带 − 转发”的方式将所收集到的周边交通状况、环境监测、动物活动等信息转发到与骨干网络相连的RSU[4-6]. 由于源RSU业务源的动态变化性和不可预测性使得自适应的分组调度面临挑战, 如森林火灾监控、各种静止或移动的被监测保护动物等, 业务状态在短时间内表现出高度的突发性[7-8], 需要以自适应和鲁棒的方法解决突发业务调度问题, 以提高网络资源利用率.
在上述应用背景下, 应设计有效的源RSU节点分组调度策略, 在其无线覆盖范围内有车辆经过时, 决定是否将收集的数据发送给过往车辆进行载带中继传输. 分组端到端时延由源RSU缓存中的排队时延与车辆载带分组至目的RSU过程中的传播时延两部分组成. 若源RSU给到达车辆均发送分组, 能使平均排队时延最小, 但会导致较大的平均传播时延; 若为了等待速度较快的车辆而导致分组在缓存中过多积压, 则平均排队时延增加. 因此, 平均排队时延和平均传播时延之间存在最佳折中能使平均端到端时延最小化. 当源RSU的突发业务到达其缓存队列时, 如果能根据突发业务到达率动态调整载带车辆的速度选择范围, 就能缓解由于分组队列阻塞带来的排队时延增长.
1. 相关工作及本文贡献
车联网中由于车辆移动速度快导致网络拓扑频繁变化, 网络节点间断连通, 这种间歇连通特性虽然增大了数据传输时延, 但也增加了数据分发的机会和网络容量, 适用于时延容忍的业务[9]. 车联网可使用“存储 − 载带 − 转发(Store-carry-forward)”的机会传输方式进行时延容忍业务的多跳传输[10]. 现有的高速公路车联网场景以“存储 − 载带 − 转发”方式进行时延容忍业务传输研究主要关注于如何保证车辆间多跳传输的可达性, 而对网络性能考虑较少. 文献[11]在高速公路场景下, 得到了通过车辆载带中继的消息在一定距离上的传播时延的概率分布, 以此为基础, 研究两个紧邻车辆簇中后簇簇首通过车辆载带中继将分组发给前簇簇尾的时延概率分布, 进而得到该场景下端到端时延的分布情况[12]. Huang等[13]考虑了车辆分布稀疏且相对移动速度不同会导致其通信过程频繁中断, 研究了长距离车辆载带中继消息恢复时延的稳态分布. 文献[14]提出了一种结合V2V (Vehicle to vehicle)和V2I (Vehicle to infrastructure)混杂方式的车辆载带中继的车联网数据分发方法, 有数据待发的车辆可以通过多跳成簇的方式, 将数据通过其他车辆载带中继到RSU节点, 该方法可以优化网络资源利用率及减少数据交付时延.
互不连通的RSU可通过过往车辆“存储 − 载带 − 转发”的方式将所收集到的周边的交通状况、环境监测、动物活动等信息转发到与骨干网络相连的RSU, 进而传送给数据中心[4-6]. 高速公路车联网中, RSU可作为多种传感器网络的汇入网关, 承担着周边交通状况、环境监测、动物活动等信息的收集和转发功能. 该场景下, 在RSU节点形成的业务具有突发性[15]. 在进行RSU分度调度研究时, 需要考虑业务突发性对分组排队时延和分组传播时延的影响. 目前车联网突发业务相关研究主要集中在由车辆随机到达引起的业务突发性, 包括车与车, 车与路边单元之间待传输的业务. 文献[16]通过V2V多跳方式将具有突发性的车辆业务传输到RSU, 并根据车辆与RSU间的延迟约束估算覆盖该路段所需的最少RSU数量. 文献[17]在车辆通信环境下提出一种突发分组生成算法, 能更加精确地描述突发业务传输过程中的分组生成情况. 在文献[18]中, 作者研究了异构车载网络基于位置路由的端到端时延界问题, 考虑了车辆间通信的突发特性, 将车辆间多跳通信建模成广义随机有界突发模型. 文献[19]考虑了车辆业务的突发性和信道环境的高度动态性, 研究V2V多跳通信过程中业务源缓存情况、端到端时延性能及多跳传输带来的业务突发累积效应. 文献[20]根据车辆轨迹数据统计车辆行驶过程中与RSU相遇的概率分布, 在业务分组具有随机性和突发性的条件下, 研究车联网中移动数据卸载问题. 也有相关文献从较大时间尺度来考虑车联网性能, 车联网的业务需求及可用网络资源随着交通流量的时空变化而变化, 其业务到达具有突发性[21-22].
由车辆载带中继的分组在RSU间传输过程中, 其端到端时延主要由排队时延和传播时延两部分组成. 贪婪中继方案(Greedy bundle relaying scheme, GBRS)[23]不考虑车辆速度, 源RSU向经过的每个车辆均发送1个分组, 该方法能使排队时延最小, 但传播时延较大. 为降低传播时延, Khabbaz等[23-25]提出了一种RSU分组概率中继方案(Probabilistic bundle relaying scheme, PBRS), 在该方案中定义一个称为发送概率的参数Pr, 该发送概率与车速成正相关, 该方案不能对分组队列长度的动态变化做出相应调整. 在文献[26-28]中作者基于分组重传机制, 将虚拟空间引入分组延迟感知的分组传输方案, 目的是在1个分组到达目的RSU前, 源RSU可将虚拟空间中该分组备份重传给后续到达但速度更快的车辆, 以便更早地交付给目的RSU, 但会造成分组冗余传输, 影响网络资源利用率. Ramaiyan等[29]假设源节点能感知车辆到达时间和车速, 并根据车速和累计的分组数量做传输决策, 利用动态规划方法解决了RSU间分组传输端到端时延最小化问题, 该方法需要已知完整的网络信息知识(即精确的车辆到达时刻、车辆速度等), 并以每辆车到达时刻作为决策点, 不能及时感知RSU缓存中分组的动态变化. 在文献[30]中, 作者在相同背景下, 通过建立马尔科夫链分析了传播时延对接收端RSU缓冲区中分组传输和重新排序的影响, 统计间歇性连通车载网络场景下的延迟数据来评估网络性能.
在上述研究工作中, 源RSU向每个经过车辆发送1个分组的方式使得传输资源利用率低, 且排队时延受分组到达率的影响较大. 据此, Khabbaz等[23-24, 31-32]提出了一种批量分组概率传输方案 (Probabilistic bundle relaying scheme with bulk bundle release, PBRS-BBR), 通过提高服务率减少分组在缓存中的排队时延, 并仿真验证了PBRS-BBR相对于批量分组贪婪传输方案(Greedy bundle relaying scheme with bulk bundle release, GBRS-BBR)的优势. 在文献[33]中, Fawaz等建模并分析了上游RSU与中游RSU同时依靠车流向下游RSU载带中继分组的场景, 提出了一个能够缓解存储饱和度且延迟最小的分组批量发送方案. Wang等[10]的研究侧重于RSU向过往车辆发送数据的下行传输问题, 在双向车流中选择中继车辆将信息从RSU转发给有下载需求的目的车辆, 减少车辆的传输中断时间.
本文针对基于车辆载带中继的RSU突发业务分组调度问题, 提出一种能使分组端到端时延最小的随机优化策略. 该策略根据源RSU缓存中的分组累积数量和移动车辆的速度状态做分组调度决策, 能根据突发业务量的实时变化, 动态调整分组调度的载带车辆速度选择范围. 当突发业务到达时, 及时增加载带车辆资源; 突发业务量过后, 再次调整车速选择范围, 从而保证系统服务质量, 实现分组传输过程中的平均端到端延时最小化.
2. 系统模型
基于车辆载带中继的RSU突发业务分组传输场景如图1所示, 高速公路某个路段存在两个固定RSU节点, 分别为源节点
$ {\rm{RSU_1}} $ 与目的节点$ {\rm{RSU_2}} $ . 由于部署位置原因$ {\rm{RSU_1}} $ 不能接入互联网, 该节点作为多种传感器网络的网关节点负责将周边具有突发性质的监测数据转发给与骨干网络相连的$ {\rm{RSU_2}} $ 节点. 两个RSU间隔距离用$ L $ 表示, 该距离远大于RSU的无线覆盖范围[24-25]. 相比距离$ L, $ RSU无线覆盖范围可忽略.
图 1 路边单元突发业务分组传输调度示意图Fig. 1 The schematic of bursty traffic transmission scheduling between roadside unitsRSU−车辆分组随机调度系统如图2所示, 突发业务分组随机到达
$ {\rm{RSU_1}} $ , 在其缓存中存储并排队等待发送. 将系统时间划分为等长时隙, 在某个时隙内, 若没有车辆到达$ {\rm{RSU_1}} $ , 则分组在缓存中排队等候; 若该时隙内有车辆到达, 则$ {\rm{RSU_1}} $ 根据分组调度策略确定是否向经过车辆发送分组, 以及发送的分组数量.2.1 突发业务到达模型
假设每个时隙有不同数量的突发业务分组随机到达
$ {\rm{RSU_1}} $ , 且分组到达过程是独立同分布的. 突发业务可用多状态伯努利分布进行描述[34-35]. 令$ a[t] = $ $m $ 表示在第$ t $ 个时隙有$ m $ 个分组新到达$ {\rm{RSU_1}} $ , 分组到达过程的概率质量函数表示为$$ {\rm{P}} \{ a[t] = m\} = {\theta _m},\;m = 0,1, \cdots ,M $$ (1) 其中,
$ {\theta _m} \in [0,1] $ 表示$ a[t] = m,m \in \{ 0,1, \cdots ,M\} $ 的概率, 由于受到物理限制,$ M $ 为每个时隙RSU所能接收周 边监测数据的最大分组个数. 则$ a[t] $ 的分布满足$\sum\nolimits_{m = 0}^M {{\theta _m}} = 1,$ 且分组平均到达率为$ \bar \alpha = $ $\sum\nolimits_{m = 0}^M {m{\theta _m}} .$ $ {\rm{RSU_1}} $ 中的缓存用来存储尚未传输的积压分组, 缓存容量为$ K $ 个分组, 其中$ K = \infty $ 和$ K < \infty $ 分别表示缓存容量无限和有限的情况. 第$ t-1 $ 个时隙结束时, 缓存中的分组个数, 即队列长度, 用$ q[t] $ 表示, 其状态变化为$$ q[t + 1] = \max \{ \min \{ q[t] + a[t],K\} - s[t],0\} $$ (2) 其中,
$ s[t] \in [0,S] $ 表示$ {\rm{RSU_1}} $ 在第$ t $ 个时隙向到达车 辆发送的分组个数,$ S $ 为每个时隙受到物理限制, RSU所能传输的最大分组数量. 新到达的分组在该时隙可以立即传送, 故在本系统中不区分新到达的分组和已存储在缓存中的分组. 因此, 可将第$ t $ 个时隙的队列状态等效定义为$ x[t] = q[t] + a[t] $ , 得出$$ x[t + 1] = x[t] - s[t] + a[t + 1] $$ (3) 2.2 车辆到达模型
高速公路自由流交通状态下, 车辆到达
$ {\rm{RSU_1}} $ 服从参数为$ \lambda $ 的泊松过程. 用$ T $ 表示两车相继到达$ {\rm{RSU_1}} $ 的时间间隔, 则$ T $ 服从负指数分布, 其概率密度函数为$f(t) = \lambda {{\rm{e}}^{ - \lambda {{t}}}},\;t \! > 0,$ 概率分布函数为$F(t) = $ $ {\rm P} (T \le t) = 1 - {{\rm{e}}^{ - \lambda t}},\;t > 0.$ 令系统时隙长度为固定值, 用$ \Delta t $ 表示, 则在该时隙内(至少)有1辆车到达$ {\rm{RSU_1}} $ 的概率(即两辆车相继到达的时间间隔小于等于$ \Delta t $ 的概率)为$$ {P_a} = {\rm{P}}(T \le \Delta t) = 1 - {{\rm{e}}^{ - \lambda \Delta t}},\;\;\Delta t > 0 $$ (4) 因此, 一个时隙内没有车到达
$ {\rm{RSU_1}} $ 的概率为$ 1 - {P_a} $ . 当时隙足够小时可确保每个时隙最多有一辆车到达.2.3 离散车速状态模型
令
$ v[t] $ 表示第$ t $ 个时隙到达$ {\rm{RSU_1}} $ 的车辆速度, 其中$ v[t] = 0 $ 表示该时隙没有车辆进入$ {\rm{RSU_1}} $ 覆盖范围. 假设在RSU间行驶过程中, 车辆速度保持不变, 并且对于各个时隙独立同分布. 本文将连续的车速量化成$ W + 1 $ 个离散的车速状态: 令${{V}} = [{v_1},$ $ {v_2}, \cdots ,{v_{W + 1}}] $ 为阈值向量, 其中,$ {v_1} = {V_{\max }} $ 和$ {v_{W + 1}} = $ ${V_{\min }} $ 分别是车速的上限和下限, 且满足${v_w} > {v_{w + 1}} ,$ 即下标越小代表车速越快.将第
$ t $ 个时隙到达$ {\rm{RSU_1}} $ 的车辆速度状态用$ h[t] $ 表示, 其中,$h[t] = w, \;1 \le w \le W,$ 表示$v[t] \in [{v_{w + 1}},$ ${v_w}) ;$ $ h[t] = W + 1 $ 表示该时隙$ t $ 内没有车辆到达, 即$ v[t] = 0 $ . 车速离散为5个状态的模型如图3(a)所示, 其中,$ w = 1 $ 和$ w = 4 $ 分别表示车速最快与最慢的状态;$ w = 5 $ 表示无车辆到达$ {\rm{RSU_1}} $ . 类似地,$ W + 1 $ 个离散车速状态模型如图3(b)所示.车速处于状态
$ w $ 的概率用$ {\eta _w} $ 表示, 其概率质量函数表达式为$$ \begin{split} {\eta _w} =\;& P\{ h[t] = w\} =\\ & \left\{ \begin{aligned} &{P_a}\int_{{v_{w + 1}}}^{{v_w}} {f(v){\rm{d}}v,\;\quad 1 \le w \le W} \\& 1 - {P_a},\;\qquad\qquad\;\;\;\, w = W + 1 \end{aligned} \right. \end{split} $$ (5) 其中,
$ f(v) $ 表示车速$ v $ 的分布, 且有$ \sum\nolimits_{w = 1}^{W + 1} {{\eta _w} = 1} $ . 根据自由流交通模型, 假设车速分布与车辆到达过程无关, 且车速服从均值为$ \overline V $ 、标准差为$ \sigma $ 的正态分布, 则其概率密度函数为$$ {f_{(v)}^*} = \frac{1}{{\sigma \sqrt {2{\text{π}} } }}\exp \left[ { - {{\left( {\frac{{v - \overline V }}{{\sigma \sqrt 2 }}} \right)}^2}} \right] $$ (6) 令
$ v \in [{V_{\min }},{V_{\max }}) $ , 则车速分布的截断概率密度函数为[36]$$ f(v) = \dfrac{{{2f_{(v)}^*}}}{{erf\left( {\dfrac{{{V_{\max }} - \overline V }}{{\sigma \sqrt 2 }}} \right) - erf\left( {\dfrac{{{V_{\min }} - \overline V }}{{\sigma \sqrt 2 }}} \right)}} $$ (7) 2.4 传播时延
在车速状态模型中将连续的车速离散为
$ W+1 $ 个状态, 则传播时延也相应的离散为$ W+1 $ 个状态. 令$ {T_w} $ 表示车速状态为$ w $ 时,$ {\rm{RSU_1}} $ 向车辆发送1个分组的平均传播时延, 并分以下两种情况讨论:1) 当车速状态为
$w,\;1 \le w \le W$ 时, 速度取区间中值, 该状态下发送1个分组的平均传播时延表达式为$$ {T_w} = \dfrac{L}{{\dfrac{1}{2}({v_{w + 1}} + {v_w})}},\;\quad1 \le w \le W $$ (8) 显然, 平均传播时延
$ {T_w} $ 与车速成反比, 即车速状态越好, 平均传播时延越小, 即$ {T_1} < {T_2} < \cdots < $ ${T_W} $ .2) 当车速状态为
$ w = W + 1 $ 时, 表示没有车辆到达$ {\rm{RSU_1}} $ , 故不能传输分组, 此状态下平均传播时延为0, 即$ {T_{w + 1}} = 0 $ .3. 马尔科夫决策框架与时延分析
马尔科夫决策是用于不确定条件下的决策优化模型, 描述代理与环境或系统交互的随机决策过程[37-38]. 基于车辆载带中继的路边单元分组调度问题面临突发业务到达时刻与数量的随机性、车辆到达的随机性, 以及车速的随机性. 本文基于马尔科夫决策的随机优化方法, 提出一个分组调度最优策略, 该策略能根据突发业务量、缓存状态的实时变化, 动态、弹性地调整车速状态的选择范围以最小化端到端分组传输时延. 本节通过建立马尔科夫决策(Markov decision process, MDP)框架对分组传输过程中的排队时延和传播时延进行分析, 并以分组端到端时延最小化为目标, 建立一个非线性优化问题.
MDP框架制定如下: 上文所描述的分组传输系统可由一个5元组
$ (X,N,S,P,\overline D ) $ 组成. 其中,$ X = \{ 0,1, \cdots ,K\} $ 表示系统状态集合, 每个状态代表$ {\rm{RSU_1}} $ 缓存中的分组队列长度;$N = \{ (m,w)\left| m \right. \in $ $ \{ 0,1, \cdots ,M\} ,w \in \{ 1, \cdots ,W + 1\} \} $ 表示所有可能的分组到达状态与车速状态的组合, 表示系统的不确定性;$ S = \{ 0,1, \cdots ,S\} $ 表示发送分组个数的行动集合;$ P = \{ {\tau _{k,l}}\left| {k,l \in X} \right.\} $ 表示转移概率矩阵, 其中$ {\tau _{k,l}} = \Pr \{ x[t + 1] = l\left| {x[t] = k} \right.\} $ 表示从时隙$ t $ 到时隙$ t+1 $ ,$ {\rm{RSU_1}} $ 缓存中分组队列长度由$ k $ 转变为$ l $ 的一步转移概率;$ \overline D $ 表示分组从$ {\rm{RSU_1}} $ 传输到$ {\rm{RSU_2}} $ 的平均端到端时延, 即MDP框架中的报酬函数. 令${{\overline D_q}}$ 表示平均排队时延,${{\overline D_t}}$ 表示平均传播时延, 可得到:$\overline D = {{\overline D_q}} + {{\overline D_t}}$ .在每个时隙,
$ {\rm{RSU_1}} $ 根据系统状态、车速状态做出行动决策. 在系统状态$ x[t] = k $ , 车速状态$ h[t] = w $ 的条件下,$ {\rm{RSU_1}} $ 向到达车辆发送$ s $ 个分组的概率用$ f_{k,w}^s $ 表示, 即$$ f_{k,w}^s = {\rm{Pr}} \{ s[t] = s\left| {x[t] = k} \right.,h[t] = w\} $$ (9) 其中, 当
$ k = 0 $ 时, 缓存中没有分组可以发送, 所以有$ f_{0,w}^0 = 1 $ ,$f_{0,w}^s = 0\;(s \ne 0)$ ; 当车速状态$ w[t] = $ $ M + 1 $ 时, 表示没有车到达,$ {\rm{RSU_1}} $ 不能发送分组, 所以有:$ f_{k,W + 1}^0 = 1 $ ,$f_{k,W + 1}^s = 0\;(s \ne 0)$ . 对$ \forall k,w $ , 满足$ \sum\nolimits_{s = 0}^S {f_{k,w}^s = 1} $ .系统转移概率分以下三种情况讨论:
1) 若时隙
$ t-1 $ 结束时,$ {\rm{RSU_1}} $ 缓存中有$ k $ 个分组, 且在时隙$ t $ 有$ i $ 个分组到达$ {\rm{RSU_1}} $ , 并发送$ i - m $ 个分组给经过车辆, 则$ {\rm{RSU_1}} $ 缓存在时隙$ t $ 增加了$ m $ 个分组, 其转移概率为$$ {\lambda _{k,m}} = {\tau _{k,k + m}} = \sum\limits_{i = m}^{\min \{ M,(S + m)\} } {{\theta _i}} \sum\limits_{w = 1}^{W + 1} {{\eta _w}f_{k,w}^{i - m}} \; $$ (10) 其中,
$ k \in [0,K - 1],m \in [1,M] $ .2) 若时隙
$ t-1 $ 结束时,$ {\rm{RSU_1}} $ 缓存中有$ k $ 个分组, 且在时隙$ t $ 有$ i $ 个分组到达$ {\rm{RSU_1}} $ , 并发送$ i + s $ 个分组给经过车辆, 则$ {\rm{RSU_1}} $ 缓存在时隙$ t $ 减少了$ s $ 个分组, 其转移概率为$$ {\mu _{k,s}} = {\tau _{k,k - s}} = \sum\limits_{i = 0}^{\min \{ M,(S - s)\} } {{\theta _i}} \sum\limits_{w = 1}^{W + 1} {{\eta _w}f_{k,w}^{i + s}} \; $$ (11) 其中,
$ k \in [1,K],s \in [1,S] $ .3) 若时隙
$ t-1 $ 结束时,$ {\rm{RSU_1}} $ 缓存中有$ k $ 个分组, 且在时隙$ t $ 缓存中分组个数保持不变的概率为$$ { \lambda _{k,0}}\!=\! \left\{\! {\begin{aligned} &1 - \sum\limits_{m = 1}^M {{\lambda _{k,m}}} ,\qquad\qquad\quad k = 0\\ &{1 -\!\! \sum\limits_{m = 1}^M {{\lambda _{k,m}}} \!-\! \! \sum\limits_{s = 1}^S {{\mu _{k,m}}},\quad 1 \!\le\! k \!\le\! K \!-\! 1} \\ &{1 - \sum\limits_{s = 1}^S {\mu _{k,m}}} ,\;\qquad\qquad\quad k = K \end{aligned}} \right. $$ (12) 当
$ M \le K $ 时,$ {\rm{RSU_1}} $ 缓存状态的一步转移马尔科夫链如图4所示.马尔科夫链的局部平衡方程为
$$ \begin{split}& \sum\limits_{i = k}^{\max \{ 0,[k - (M - 1)]\} } {{\pi _i}} \sum\limits_{j = i - k + 1}^M {{\lambda _{i,j}}}= \\&\qquad \sum\limits_{i = k + 1}^{\min \{ K,(k + s)\} } {{\pi _i}\sum\limits_{j = i - k}^S {{\mu _{i,j}}} ,} \;\;\;\forall k \in [0,K - 1] \end{split} $$ (13) 根据MDP框架, 状态转移概率矩阵用
${{P}}$ 表示, 矩阵中第$ (i + 1,j + 1) $ 个元素为$ {\tau _{i,j}} $ ; 系统到达稳态时, 队列状态为$ k $ 的稳态概率用${\pi _k}$ 表示, 且${{\pi }} =[{\pi _0},$ ${{\pi} _1}, \cdots ,{{\pi} _K}]^{\rm T}$ . 因为本系统所建立得马尔科夫链是齐次、不可约且非周期的, 所以其稳态概率可以通过${{\Pi P = \Pi }}$ 获得. 归一化方程为:$\sum\nolimits_{k = 0}^K {{\pi _k} = 1}$ . 令${{f}}$ 表示参数为$ \{ f_{k,w}^s\} $ 的向量, 当调度概率$ \{ f_{k,w}^s\} $ 已知, 则通过解以上方程可得到${\pi _k}$ , 所以${\pi _k}$ 是${{f}}$ 的函数, 可表示为${\pi _k}({{f}})$ .平均队列长度为队列长度的概率加权之和, 即
$E\{ q[t]\} = \sum\nolimits_{k = 0}^K {k{\pi _k}}$ . 根据Little定理, 分组在$ {\rm{RSU_1}} $ 缓存中的平均排队时延为$$ {{\overline D_q}} = \frac{1}{{\bar \alpha }}\sum\limits_{k = 0}^K {k{\pi _k}} $$ (14) 根据式(9), 在缓存队列状态为
$ x[t] = k $ , 车速为$ h[t] = w $ 的条件下, 时隙$ t $ 发送$ s $ 个分组的平均传播时延为$ {\phi _{k,w}} = \sum\nolimits_{s = 0}^S {{T_w}sf_{k,w}^s} $ . 每个时隙$ {\rm{RSU_1}} $ 发送分组产生的平均传播时延为$$ \begin{split} & \sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {{\rm{Pr}} \{ x[t] = k,h[t] = w\} \times {\phi _{k,w}}} } =\\ &\qquad \sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\Pr \{ x[t] = k\} \times {\rm{Pr}} \{ h[t] = w\} \times {\phi _{k,w}}} }= \\ &\qquad \sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{\pi _k}{\eta _w}{T_w}sf_{k,w}^s} } } \\[-15pt]\end{split} $$ (15) 同理,
$\sum\nolimits_{k = 0}^K {\sum\nolimits_{w = 1}^{W + 1} {\sum\nolimits_{s = 0}^S {{\pi _k}{\eta _w}sf_{k,w}^s} } }$ 表示每个时隙$ {\rm{RSU_1}} $ 所发送分组的平均数量. 因此, 本文所描述的RSU−车辆分组随机调度系统中, 每个分组的平均传播时延表示为$$ {{\overline D_t}} = \frac{{\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{\pi _k}{\eta _w}{T_w}sf_{k,w}^s} } } }}{{\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{\pi _k}{\eta _w}sf_{k,w}^s} } } }} $$ (16) 4. 优化问题与调度策略
根据式(14)和式(16), 分组平均排队时延
${{ \overline D_q}}$ 和平均传播时延${{\overline D_t}}$ 均为参数${\pi _k}$ 与$ f_{k,w}^s $ 的函数, 因此以平均端到端时延$ \overline D $ 最小化为目标函数的优化问题可表示为$$ \begin{split}& \mathop {\min }\limits_{\{ f_{k,w}^s\} } \;\overline D = \frac{1}{{\bar \alpha }}\sum\limits_{k = 0}^K {k{\pi _k}} + \frac{{\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{\pi _k}{\eta _w}{T_w}sf_{k,w}^s} } } }}{{\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{\pi _k}{\eta _w}sf_{k,w}^s} } } }}\\ &\qquad {\rm{s.t}}.\left\{ \!\!{\begin{aligned} &\sum\limits_{s = 0}^S {f_{k,w}^s = 1} ,\;\;\forall k,w \\ & \sum\limits_{k = 0}^K {\pi _k} \!=\! 1\\ &\sum\limits_{i = k}^{\max \{ 0,[k - (M - 1)]\} } {{\pi _i}}\! \sum\limits_{j = i - k + 1}^M {{\lambda _{i,j}}} \!=\\ &\qquad\ \ \sum\limits_{i = k + 1}^{\min {\rm{\{ }}K(k + s){\rm{\} }}} {{\pi _i}} \sum\limits_{j = i - k}^S {{\mu _{i,j}}}\\ &\qquad\qquad\qquad{f_{k,w}^s \in [0,1],\;\;\forall k,w,s} \end{aligned}} \right.\\[-10pt] \end{split} $$ (17) 其中, 参数
$ f_{k,w}^s $ 是可控变量. 因为${\rm{\{ }}{{\pi} _k}{\rm{\} }}$ 是关于$ f_{k,w}^s $ 的非线性函数, 所以优化问题(17)是一个非线性优化问题.为简化该问题, 本文引入一组新的变量
$ \{ y_{k,w}^s\} $ :$ y_{k,w}^s = {\pi _k}{\eta _w}f_{k,w}^s $ . 由于$ \sum\nolimits_{s = 0}^S {f_{k,w}^s = 1} $ 和$ \sum\nolimits_{w = 1}^{W + 1} {{\eta _w} = } $ $1, $ 将$ y_{k,w}^s = {{\text{π}} _k}{\eta _w}f_{k,w}^s $ 等号两边累加, 可得到$$ \sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {y_{k,w}^s} } = \sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{\pi _k}{\eta _w}f_{k,w}^s} } = {\pi _k} $$ 于是, 平均排队时延与平均传播时延分别可转化为
$$\begin{split} &{{\overline D_q}} =\dfrac{1}{{\bar \alpha }}\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {ky_{k,w}^s} } }\\ &{{\overline D_t}} = {\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{T_w}sy_{k,w}^s} } } }/{\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {sy_{k,w}^s} } } } \end{split}$$ 由此,
${{\overline D_q}}$ 转化为关于变量$ \{ y_{k,w}^s\} $ 的线性函数,${{\overline D_t}}$ 转化为关于变量$ \{ y_{k,w}^s\} $ 的非线性函数. 归一化方程转化为$\sum\nolimits_{k = 0}^K {\sum\nolimits_{w = 1}^{W + 1} {\sum\nolimits_{s = 0}^S {y_{k,w}^s} } = 1}$ ; 局部平衡方程转化为$$\begin{align} &\sum\limits_{i = k}^{\max \{ 0,[k - (M - 1)]\} } \sum\limits_{j = i - k + 1}^M \sum\limits_{v = j}^{\min \{ M,(S + j)\} }\sum\limits_{w = 1}^{W + 1} {{\theta _v}{\eta _w}y_{i,w}^{v - j}} =\\ &\sum\limits_{i = k + 1}^{\min \{ M,(k + s)\} } {\sum\limits_{j = i - k}^S {\sum\limits_{v = 0}^{\min \{ M,(S - s)\} } {\sum\limits_{w = 1}^{W + 1} {{\theta _v}{\eta _w}y_{i,w}^{v + j}} } } }\end{align}$$ 根据
$ f_{k,w}^s \in [0,1] $ , 有$ 0 \le y_{k,w}^s \le {\eta _w}\sum\nolimits_{i = 1}^{W + 1} {\sum\nolimits_{j = 0}^S {y_{k,i}^j} } $ . 于是, 优化问题(17)可等效转化为关于变量$ \{ y_{k,w}^s\} $ 的以下形式:$$ \begin{split} &\mathop {\min }\limits_{\{ y_{k,w}^s\} } \;\bar D = \frac{1}{{\bar \alpha }}\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {ky_{k,w}^s} } }\; + \\ &\quad \sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{T_w}sy_{k,w}^s} } } /\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {sy_{k,w}^s} } } \\ &\quad {\rm{s.t.}}\left\{ {\begin{aligned} &{\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {y_{k,w}^s} } = 1} }\\ &\!{\sum\limits_{i = k}^{\max \{ 0,[k - (M - 1)]\} } \!\!\!\!\!\!\!{\sum\limits_{j = i - k + 1}^M \!\!\!\!\!\!\!{\sum\limits_{v = j}^{\min \{ M,(S + j)\} } \!{\sum\limits_{w = 1}^{W + 1} {{\theta _v}{\eta _w}y_{i,w}^{v - j}} } } } }\!\!=\!\!\\ &{ \sum\limits_{i = k + 1}^{\min \{ M,(k + s)\} } \!\!\!{\sum\limits_{j = i - k}^S \!\!{\sum\limits_{v = 0}^{\min \{ M,S - s)\} } {\sum\limits_{w = 1}^{W + 1} {{\theta _v}{\eta _w}y_{i,w}^{v + j}} } } } ,\,\forall k}\\ &\quad\qquad{0 \le y_{k,w}^s \le {\eta _w}\sum\limits_{i = 1}^{W + 1} {\sum\limits_{j = 0}^S {y_{k,i}^j} } ,\;\;\forall k,w,s} \end{aligned}} \right. \end{split} $$ (18) 本文采用LINGO软件中的建模语言对优化问题(18)进行描述, 利用该软件中的非线性模型求解器解出该优化问题的全局最优解
$ \{ y_{k,w}^s\} ,$ 分别根据${\pi _k} = \sum\nolimits_{w = 1}^{W + 1} {\sum\nolimits_{s = 0}^S {y_{k,w}^s} }$ 和$f_{k,w}^{s*} = \dfrac{{y_{k,w}^{s*}}}{{\pi _k^*{\eta _w}}}$ 求得最优稳态概率$\{\pi _k^*\}$ 和最优分组调度参数$ \{ f_{k,w}^{s*}\}. $ 参数
$ \{ f_{k,w}^{s*}\} $ 的求解结果表明, 本文提出的RSU间分组最优调度策略具有双门限结构.对于已知的车速状态
$ w $ 和发送分组个数$ s $ , 队列长度$ k $ 存在一个最优门限$ k_w^s $ , 且满足$k_w^{{s_1}} \le k_w^{{s_2}}\;({s_1} \le$ $ {s_2}) ,$ 即在相同车速状态$ w $ 下, 发送分组数$ s $ 越多, 队列长度门限$ k_w^s $ 越大. 此时, 最优传输参数$ f_{k,w}^s $ 的门限结构为$$ \left\{ {\begin{aligned} &{f_{k,w}^{s{\rm{*}}} = 1,\;\;\;k_w^s \le k < k_w^{s + 1}}\\ &{f_{k,w}^{s{\rm{*}}} = 0,\;\;\;{\text{其他}}} \end{aligned}} \right. $$ (19) 同理, 对于已知队列长度
$ k $ 和发送分组个数$ s ,$ 车速状态存在一个最优门限$ w_k^s $ , 且满足$w_k^{{s_1}} \ge w_k^{{s_2}}\;({s_1} \le$ ${s_2}), $ 即在相同分组队列长度$ k $ 的条件下, 车速状态越小(车速越快), 发送分组数$ s $ 越多, 车速状态门限$ w_k^s $ 越小. 此时, 最优传输参数$ f_{k,w}^s $ 的门限结构为$$ \left\{ {\begin{aligned} &{f_{k,w}^{s{\rm{*}}} = 1,\;\;\;w_k^{s + 1} < w \le w_k^s}\\ &{f_{k,w}^{s{\rm{*}}} = 0,\;\;\;{\text{其他}}} \end{aligned}} \right. $$ (20) 5. 仿真分析
本文的仿真分为3部分. 1)通过优化问题(18)的最优解
$ \{ y_{k,w}^{s*}\} $ 计算最优分组调度参数$ \{ f_{k,w}^{s*}\} $ , 验证本文所提出的路边单元突发业务分组调度最优策略(Optimal packet scheduling strategy for roadside units＇ bursty traffic, OPSS-RSUs)具有门限结构; 2) 仿真并做出突发业务分组平均排队时延、平均端到端时延随平均传播时延的变化曲线, 分析平均排队时延与平均传播时延间的折中; 3) 将本文提出的OPSS-RSUs方法与贪婪中继方案GBRS-BBR (Greedy bundle relaying scheme with bulk bundle release)、概率中继方案PBRS-BBR (Probabilistic bundle relaying scheme with bulk bundle release)以及Q-Learning算法Q-Learning-BBR (Q-learning scheme with bulk bundle release)在平均排队时延、平均传播时延以及平均端到端时延三个方面进行对比和分析.仿真参数设置如表1所示, 其中, 速度区间取[16.67, 33.33] m/s, 即[60, 120] km/h; 将连续车速离散为
$ W+1 = 5 $ 个车速状态, 即$ 1 \le w \le 5 $ , 且$ w $ 越小表示车速状态越快, 车速状态$ w = 5 $ 时表示没有车辆到达$ {\rm{RSU_1}} $ . 根据式(5), 不同车速状态的概率取值为$ [{\eta _1},{\eta _2},{\eta _3},{\eta _4},{\eta _5}] = [0.1259,0.1494,0.1494, $ $0.1259,0.4493] $ . 相应地, 根据式(8), 不同车速状态下$ {\rm{RSU_1}} $ 发送1个分组的传播时延为$ [{T_1},{T_2},{T_3},{T_4}, $ ${T_5}] = [320.0256,369.2421,436.3477,533.2622,0] $ . 为便于分析, 取$ S = 2 $ , 即$ {\rm{RSU_1}} $ 在每个时隙向到达车辆发送的分组个数$ s \in \{ 0,1,2\} $ .表 1 仿真参数表Table 1 Simulation parameters参数名称 符号/单位 参数值 RSU缓存容量 $K$/个 100 RSU间隔距离 $L$/m 10 000 速度区间 $[{V_{\min }},{V_{\max }}]$/(m/s) [16.67, 33.33] 速度期望 $\overline V $/(m/s) 25 速度标准差 $\sigma $ 10 车辆到达率 $\lambda $/(辆/s) 0.55 时隙长度 $\Delta t$/s 1 车速状态数量 $W$ 4 发送分组数量上限 $S$ 2 5.1 OPSS-RSUs方法门限结构验证
本文按分组到达概率
$ {\theta _i} $ 的不同分为两组方案进行仿真, 且两组$ {\theta _i} $ 的取值如表2所示. 其中, 方案1中分组的平均到达率$ \bar \alpha = 0.5 $ , 方案2中$ \bar \alpha = 0.7 $ .表 2 分组到达参数表Table 2 Packets arrival parameters分组到达概率${\theta _i}$ ${\theta _0}$ ${\theta _1}$ ${\theta _2}$ 平均到达率$\bar \alpha $ 方案 1 0.7 0.1 0.2 0.5 方案 2 0.6 0.1 0.3 0.7 两种分组到达方案中,
$ \{ f_{k,w}^{s*}\} $ 的求解结果分别如图5(a)和图5(b)所示. 为清楚地表示调度策略的门限结构, 图中截断选取分组队列长度$ k \in [0,30] $ 的范围进行展示.由图5可知, 调度策略
$ s $ 是基于车速状态$ w $ 和分组队列长度$ k $ 的双门限结构. 在图5(a)中, 当$ w = 3 $ 时,$ k_3^0 = 0,k_3^1 = 11,k_3^2 = 12 $ . 根据式(19), 有$$ \left\{ {\begin{aligned} &{f_{k,3}^{{\rm{0*}}} = 1,\;\;\;\;0 \le k < 11\;}\\ & f_{k,3}^{{\rm{1*}}} = 1,\;\;\;\;11 \le k < 12\\ &f_{k,3}^{{\rm{2*}}} = 1,\;\;\;\;k \ge 12 \end{aligned}} \right. $$ (21) 当
$ 0 \le k < 11 $ 时,$ {\rm{RSU_1}} $ 发送0个分组; 当$ 11 \le $ $ k < 12 $ 时, 发送1个分组; 当$ k \ge 12 $ 时, 发送2个分组. 因此, 在相同车速状态下, 分组队列长度较小时,$ {\rm{RSU_1}} $ 不发送分组以等待速度更快的车辆; 当分组累积数量增大到门限值时,$ {\rm{RSU_1}} $ 会及时发送分组, 以降低排队时延.在图5(a)中, 当
$ k = 11 $ 时,$ w_{11}^0 = 5,w_{11}^1 = 3, $ $w_{11}^2 = 2 $ . 根据式(20), 有$$ \left\{ {\begin{aligned} &{f_{11,w}^{0*} = 1,\;\;3 < w \le 5}\\ &{f_{11,w}^{1*} = 1,\;\;2 < w \le 3}\\ &{f_{11,w}^{2*} = 1,\;\;w \le 2\;\;\;\;\;} \end{aligned}} \right. $$ (22) 当
$ 3 < w \le 5 $ 时,$ {\rm{RSU_1}} $ 发送0个分组; 当$ 2 < $ $ w \le 3 $ 时, 发送1个分组; 当$ w \le 2 $ 时, 发送2个分组. 由此可得出结论, 在相同分组队列长度的条件下, 车速状态$ w $ 越大(车速越小),$ {\rm{RSU_1}} $ 发送分组个数越少; 反之, 发送分组个数越多.综上所述, 车速状态越好, 分组队列长度越大, 则发送分组数目越多; 车速状态越差, 分组队列长度越小, 则发送分组数目越少甚至不发送分组.
当
$ k = 24,s = 2 $ 时, 方案1与方案2车速状态的门限值分别出现在车速状态3与车速状态4处, 说明在相同的分组队列长度条件下, 分组到达率较小($ \bar \alpha = 0.5 $ )时, 该调度策略选取速度较快($ w \le 3 $ )的车辆发送分组, 放弃车速较慢的车辆($ w = 4,5 $ ). 当$ \bar \alpha $ 增大($ \bar \alpha = 0.7 $ )时, 分组累积速率加快, 该调度策略将扩大发送分组的车速选择范围($ w \le 4 $ ), 给速度较慢的车($w\,{\rm{ = }}\,4$ )也发送分组, 该方法能防止排队时延的过快增长.5.2 排队时延与传播时延的折中验证
在优化问题式(18)中, 将平均传播时延
$${{\overline D}_{t}} ={{\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {{T_w}sy_{k,w}^s} } } }/ {\sum\limits_{k = 0}^K {\sum\limits_{w = 1}^{W + 1} {\sum\limits_{s = 0}^S {sy_{k,w}^s} } } }} $$ 由小到大取定值作为新增约束条件带入求最优解
$ \{ y_{i,m}^*\} $ , 分别求出对应的平均排队时延${ {{\overline D_q^*}} }$ 和平均端到端时延$ {\overline D ^*}, $ 相应变化曲线如图6所示.
图 6 平均排队时延和平均端到端时延随平均传播时延的变化曲线Fig. 6 Changes in average queuing delay and average end-to-end delay as the average propagation delay increases如图6(a)所示, 在OPSS-RSUs方法中, 当平均传播时延较小时, 说明
$ {\rm{RSU_1}} $ 仅选择速度较快的车辆发送分组, 故平均排队时延较高; 随着平均传播时延逐渐增大,$ {\rm{RSU_1}} $ 扩大载带分组的车速选择范围, 使得分组传输机会增加, 平均排队时延随之快速下降; 当平均传播时延继续增大时, 由于分组平均到达率$ \bar \alpha $ 不变, 扩大车速选择范围对平均排队时延的影响逐渐减弱, 平均排队时延的下降速率逐渐平缓并趋近于0, 即分组到达$ {\rm{RSU_1}} $ 后几乎立刻发送给车辆. 因此, 平均排队时延与平均传播时延之间存在折中, 且该折中点能使得平均端到端时延最小化. 在图6(b)中, 随着平均传播时延逐渐增大, 平均端到端时延经历了先降低后增加的过程, 验证了折中点的存在性.5.3 时延性能对比分析
GBRS-BBR方法不考虑车辆速度, 在缓存中分组个数不为0的情况下, 向每一个经过的车辆均发送分组, 即传输参数如下式所示:
$$ \left\{ {\begin{aligned}& {f_{k,w}^0 = 1,\;\;\;k = 0}\\& {f_{k,w}^1 = 1,\;\;\;k = 1}\\ &{f_{k,w}^2 = 1,\;\;\;k \ge 2} \end{aligned}} \right. $$ (23) PBRS-BBR方法中,
$ {\rm{RSU_1}} $ 向第$ i $ 辆车传输分组的概率为$ {P_{br,i}} \in [0,1] $ , 根据文献[25]中式(4), RSU给第$ i $ 辆车发送分组的概率表达式为$$ {P_{br,i}} = {\rm{exp}}\left[ { - {\mu _v}\left( {\frac{{{d_{SD}}}}{{{v_i}}} - \frac{{{d_{SD}}}}{{{V_{\max }}}}} \right)} \right] $$ (24) 其中,
$ {\mu _v} $ 表示车辆到达率,$ {d_{SD}} $ 表示源 − 目的RSU间隔距离,$ {V_{\max }} $ 表示限定车速的最大值,$ {v_i} $ 表示第$ i $ 辆车的速度. 由此可知, 在车辆到达率$ {\mu _v} $ 为定值的条件下,$ {P_{br,i}} $ 仅由车速决定, 车速越大,$ {P_{br,i}} $ 越大; 反之,$ {P_{br,i}} $ 越小. 因此PBRS-BBR方法仅能降低分组平均传播时延, 无法对平均排队时延进行控制.Q-Learning是一种无模型的强化学习算法, 在该算法中. 定义系统状态
$ state(k,w) $ , 其中$ k \in \{ 0, $ $1, \cdots ,K\} $ ,$ w \in \{ 1, \cdots ,W\} $ ; 行动$ act $ 表示发送分组个数; 报酬$ r $ 为状态$ state(k,w) $ 且采取行动$ act $ 时, 单位时隙所产生的端到端时延, 故状态 − 行动报酬矩阵${{R}}$ 如下式所示:$$ \begin{split} &{{R}}(state(k,w),act)=\\ &\qquad\left\{ \begin{aligned} &{{\rm{ - }}100\,000\,000,\qquad\qquad\quad act > k}\\ &{{\rm{ - }}100\,000\,000,\qquad\qquad\quad w = W + 1,act \ne 0}\\ &{\rm{ - [}}(k{\rm{ - }}act)\times(1 + \frac{L}{\bar V}) +\\ &\qquad act\times{T_w}],\;\;\qquad\qquad {\text{其他}} \end{aligned} \right. \end{split} $$ (25) 其中, 对某一状态, 非有效行动的报酬为
$ - \infty $ , 仿真中设定为−100 000 000.本文使用
$\epsilon $ -greedy ($\epsilon $ -贪婪算法) 来保证源路边单元探索环境参数及保障数据包调度决策质量. 应用$\epsilon $ -greedy之后的源路边单元在进行强化学习决策时, 做出在当前车辆速度状态和数据包队列状态下进行发送分组数量的决策.算法整体步骤如下:
步骤 1. 给定参数
$\gamma = 0.5,$ ${R} ;$ 步骤 2. 令
${{Q}}(state,act)=0$ ;步骤 3. 随机生成初始状态
$ state(k,w) $ ;${\bf{for}}\ {\rm{each}}\ {{\epsilon}}\ {\bf{do}}$ 在当前状态
$ state(k,w) $ 的所有行动中选取一个行动$act;$ 根据行动
$ act $ 生成下一个状态$ s' $ ;$Q(state,act) \leftarrow r(state,act) +\\ \gamma \max \{Q(state',act')\};$ $ state \leftarrow state' $ ;${\bf{ end }}$ 算法中
${{\epsilon}} $ 是一个在0和1之间服从均匀分布的随机变量, 在每次决策之前随机选取，在每次迭代中$0\leq{{\epsilon}}\leq1 $ 是恒定的探索参数.本文所提出的OPSS-RSUs方法以端到端时延最小化为优化目标, 根据分组排队数量和车速状态两个因素决定是否给该车发送分组以及发送分组的数量. 将车辆到达率取固定值
$ \lambda = 0.55 $ , 平均分组到达率$ \bar \alpha $ 的变化范围取$ [0.1,1.0] $ , OSPT-RSUs、GBRS-BBR、PBRS-BBR和Q-Learning-BBR四种分组调度方法的平均排队时延、平均传播时延以及平均端到端时延的仿真结果如图7所示.与另外三种方法相比, GBRS-BBR方法产生的平均排队时延最小, 但平均传播时延最大, 如图7(a)和图7(b)所示. GBRS-BBR方法向所有到达车辆发送分组, 能在最短时间内将分组发送给车辆, 但不对车速进行选择, 其平均传播时延是
$ {\rm{RSU_1}} $ 和$ {\rm{RSU_2}} $ 的间隔距离与车速期望值的比值, 大小不随$ \bar \alpha $ 变化. PBRS-BBR方法中,$ {\rm{RSU_1}} $ 向不同车辆发送分组的概率$ {P_{br,i}} $ 与其速度大小成正相关, 其平均传播时延小于GBRS-BBR. 当$ \bar \alpha $ 较小时, 该方法与Q-Learning-BBR方法均能通过降低平均传播时延达到降低端到端时延的目的; 当$ \bar \alpha $ 较大时, 分组在$ {\rm{RSU_1}} $ 缓存中迅速累积, 排队时延增大, PBRS-BBR和Q-Learning-BBR方法的端到端时延显著高于GBRS-BBR方法和OSPT-RSUs方法, 如图7(c)所示. 对比图7(c)与图7(a)和图7(b)可知, 本文所提出的OSPT-RSUs方法能根据$ \bar \alpha $ 的增大动态地扩大车速选择范围, 用较小平均排队时延的增长换取平均传播时延的大幅降低, 从而使得平均端到端时延显著小于其他三种方法.将平均分组到达率取固定值
$ \bar \alpha = 0.2 $ , 车辆到达率的变化范围取$ \lambda = [0{\rm{.2, 0}}{\rm{.6]}} $ , 三种分组调度方法的平均排队时延、平均传播时延以及平均端到端时延的仿真结果如图8所示.随着车辆到达率
$ \lambda $ 取值由小增大, 四种分组调度方法的平均排队时延均呈下降趋势, 如图8(a)所示. 当车辆到达率$ \lambda $ 较小时, 为防止缓存中分组累积数量过多导致排队时延过大, OSPT-RSUs方法会扩大车速选择范围增加分组服务率, 因此其平均传播时延较大, 且与GBRS-BBR方法相近, 如图8(b)所示. 随着$ \lambda $ 不断增大, 分组载带机会增多, OSPT- RSUs方法能通过不断优化载带车辆的速度范围, 使得平均传播时延和端到端总时延逐渐降低, 其分组平均端到端时延较GBRS-BBR、PBRS-BBR以及Q-Learning-BBR方法有明显优势, 如图8(c)所示.6. 结论
本文研究了高速公路车联网场景下基于车辆载带中继的RSU突发业务分组调度问题, 提出一种能使分组端到端时延最小的随机优化策略, 该策略根据源RSU缓存中的分组累积数量和移动车辆的速度状态做分组调度决策. 本文通过受限马尔科夫决策框架对分组传输过程中的状态转移过程进行分析, 建立一个非线性平均端到端时延最小化问题并求解. 该方法可使得源路边单元根据突发业务到达率的实时变化, 动态、弹性地调整分组调度策略, 即动态调整车速选择范围, 当突发业务量到达时, 及时增加载带车辆资源; 突发业务量过后, 再次调整车速选择范围, 从而保证系统服务质量, 实现分组传输过程中的平均端到端延时最小化.
-
图 1 路边单元突发业务分组传输调度示意图
Fig. 1 The schematic of bursty traffic transmission scheduling between roadside units
图 6 平均排队时延和平均端到端时延随平均传播时延的变化曲线
Fig. 6 Changes in average queuing delay and average end-to-end delay as the average propagation delay increases
表 1 仿真参数表
Table 1 Simulation parameters
参数名称 符号/单位 参数值 RSU缓存容量 $K$/个 100 RSU间隔距离 $L$/m 10 000 速度区间 $[{V_{\min }},{V_{\max }}]$/(m/s) [16.67, 33.33] 速度期望 $\overline V $/(m/s) 25 速度标准差 $\sigma $ 10 车辆到达率 $\lambda $/(辆/s) 0.55 时隙长度 $\Delta t$/s 1 车速状态数量 $W$ 4 发送分组数量上限 $S$ 2 
下载: 导出CSV
表 2 分组到达参数表
Table 2 Packets arrival parameters
分组到达概率${\theta _i}$ ${\theta _0}$ ${\theta _1}$ ${\theta _2}$ 平均到达率$\bar \alpha $ 方案 1 0.7 0.1 0.2 0.5 方案 2 0.6 0.1 0.3 0.7
下载: 导出CSV
-
[1] 王晓, 要婷婷, 韩双双, 曹东璞, 王飞跃. 平行车联网基于ACP的智能车辆网联管理与控制. 自动化学报, 2018, 44(8): 1391−1404Wang Xiao, Yao Ting-Ting, Han Shuang-Shuang, Cao Dong-Pu, Wang Fei-Yue. Parallel internet of vehicles: The ACP-based networked management and control for intelligent vehicles. Acta Automatica Sinica, 2018, 44(8): 1391−1404 [2] 冯建周, 宋沙沙, 孔令富. 物联网语义关联和决策方法的研究. 自动化学报, 2016, 42(11): 1691−1701Feng Jian-Zhou, Song Sha-Sha, Kong Ling-Fu. Research on semantic association and decision method of the internet of things. Acta Automatica Sinica, 2016, 42(11): 1691−1701 [3] Atallah R F, Khabbaz M J, Assi C M. Modeling and performance analysis of medium access control schemes for drive-thru Internet access provisioning systems. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(6): 3238−3248 doi: 10.1109/TITS.2015.2440447 [4] He J P, Cai L, Pan J P, Cheng P. Delay analysis and routing for two-dimensional VANETs using carry-and-forward mechanism. IEEE Transactions on Mobile Computing, 2017, 16(7): 1830−1841 doi: 10.1109/TMC.2016.2607748 [5] Huang L J, Jiang H, Zhang Z, Yan Z J. Efficient data traffic forwarding for infrastructure-to-infrastructure communications in VANETs. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(3): 839−853 doi: 10.1109/TITS.2017.2705047 [6] Si P B, He Y, Yao H P, Yang R Z, Zhang Y H. DaVe: Offloading delay-tolerant data traffic to connected vehicle networks. IEEE Transactions on Vehicular Technology, 2016, 65(6): 3941−3953 doi: 10.1109/TVT.2016.2550105 [7] Oh S, Schenato L, Chen P, Sastry S. Tracking and coordination of multiple agents using sensor networks: System design, algorithms and experiments. Proceedings of the IEEE, 2007, 95(1): 234−254 doi: 10.1109/JPROC.2006.887296 [8] Mencagli G, Torquati M, Danelutto M, Matteis T D. Parallel continuous preference queries over out-of-order and bursty data streams. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(9): 2608−2624 doi: 10.1109/TPDS.2017.2679197 [9] Chen J Q, Mao G Q, Li C L, Liang W F, Zhang D G. Capacity of cooperative vehicular networks with infrastructure support: Multiuser case. IEEE Transactions on Vehicular Technology, 2018, 67(2): 1546−1560 doi: 10.1109/TVT.2017.2753772 [10] Wang Y, Liu Y S, Zhang J Y, Ye H N, Tan Z H. Cooperative store-carry-forward scheme for intermittently connected vehicular networks. IEEE Transactions on Vehicular Technology, 2017, 66(1): 777−784 [11] Shahidi R, Ahmed M H. Probability distribution of end-to-end delay in a highway VANET. IEEE Communications Letters, 2014, 18(3): 443−446 doi: 10.1109/LCOMM.2014.011214.132606 [12] Seliem H, Shahidi R, Ahmed M H, Shehata M S. Probability distribution of the re-healing delay in a one-way highway VANET. IEEE Communications Letters, 2018, 22(10): 2056−2059 doi: 10.1109/LCOMM.2018.2859928 [13] Huang J J, Tseng Y T. The steady-state distribution of rehealing delay in an intermittently connected highway VANET. IEEE Transactions on Vehicular Technology, 2018, 67(10): 10010−10021 doi: 10.1109/TVT.2018.2865500 [14] Ni Y Z, He J P, Cai L, Bo Y M. Data uploading in hybrid V2V/V2I vehicular networks: Modeling and cooperative strategy. IEEE Transactions on Vehicular Technology, 2018, 67(5): 4602−4614 doi: 10.1109/TVT.2018.2796563 [15] Kuo Y W, Li C L, Jhang J H, Lin S. Design of a wireless sensor network-based IoT platform for wide area and heterogeneous applications. IEEE Sensors Journal, 2018, 18(12): 5187−5197 doi: 10.1109/JSEN.2018.2832664 [16] Abdrabou A, Zhuang W H. Probabilistic delay control and road side unit placement for vehicular ad hoc networks with disrupted connectivity. IEEE Journal on Selected Areas in Communications, 2011, 29(1): 129−139 doi: 10.1109/JSAC.2011.110113 [17] Carpenter S E, Sichitiu M L. BUR-GEN: A bursty packet generator for vehicular communication channels. IEEE Transactions on Vehicular Technology, 2018, 67(11): 10232−10242 doi: 10.1109/TVT.2018.2866946 [18] Katsaros K. End-to-end delay bound analysis for location-based routing in hybrid vehicular networks. IEEE Transactions on Vehicular Technology, 2016, 65(9): 7462−7475 doi: 10.1109/TVT.2015.2482362 [19] Hu Y, Li H Y, Chang Z, Han Z. End-to-end backlog and delay bound analysis for multi-hop vehicular ad hoc networks. IEEE Transactions on Wireless Communications, 2017, 16(10): 6808−6821 doi: 10.1109/TWC.2017.2731847 [20] Li Y, Jin D P, Hui P, Chen S. Contact-aware data replication in roadside unit aided vehicular opportunistic networks. IEEE Transactions on Mobile Computing, 2016, 15(2): 306−321 doi: 10.1109/TMC.2015.2416185 [21] Zhang S, Zhang N, Fang X J, Yang P, Shen X S. Self-sustaining caching stations: Toward cost-effective 5G-enabled vehicular networks. IEEE Communications Magazine, 2017, 55(11): 202−208 doi: 10.1109/MCOM.2017.1700129 [22] Zhang N, Zhang S, Yang P, Alhussein O, Zhuang W H, Shen X S. Software defined space-air-ground integrated vehicular networks: Challenges and solutions. IEEE Communications Magazine, 2017, 55(7): 101−109 doi: 10.1109/MCOM.2017.1601156 [23] Khabbaz M J, Fawaz W F, ASSI C M. Probabilistic bundle relaying schemes in two-hop vehicular delay tolerant networks. IEEE Communications Letters, 2011, 15(3): 281−283 doi: 10.1109/LCOMM.2011.011011.102512 [24] Khabbaz M J, Fawaz W F, Assi C M. Modeling and delay analysis of intermittently connected roadside communication networks. IEEE Transactions on Vehicular Technology, 2012, 61(6): 2698−2706 doi: 10.1109/TVT.2012.2200001 [25] Khabbaz M J, Fawaz W F, Assi C M. A probabilistic bundle relay strategy in two-hop vehicular delay tolerant networks. In: Proceedings of the 2011 IEEE International Conference on Communications. Kyoto, Japan, IEEE, 2011. 1−6 [26] Khabbaz M J, Alazemi H M K, Assi C M. Stochastic data delivery delay analysis in intermittently connected vehicular networks. In: Proceedings of the 2012 IEEE Global Communications Conference. Anaheim, CA, USA: IEEE, 2012. 183−188 [27] Khabbaz M J, Alazemi H M K, Assi C M. Delay-aware data delivery in vehicular intermittently connected networks. IEEE Transactions on Communications, 2013, 61(3): 1134−1143 doi: 10.1109/TCOMM.2012.122712.120222 [28] Khabbaz M J, Alazemi H M K, Assi C M. Modeling and delay analysis of a retransmission-based bundle delivery scheme for intermittent roadside communication networks. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(2): 700−708 doi: 10.1109/TITS.2012.2228192 [29] Ramaiyan V, Altman E, Kumar A. Delay optimal scheduling in a two-hop vehicular relay network. Mobile Networks and Applications, 2010, 15(1): 97−111 [30] Badia L, Scalabrin M. Stochastic analysis of delay statistics for intermittently connected vehicular networks. In: Proceedings of the 20th European Wireless Conference. Barcelona, Spain: VDE, 2014. 1−6 [31] Khabbaz M J, Fawaz W F, Assi C M. A probabilistic and traffic-aware bundle release scheme for vehicular intermittently connected networks. IEEE Transactions on Communications, 2012, 60(11): 3396−3406 doi: 10.1109/TCOMM.2012.082712.110473 [32] Khabbaz M J, Fawaz W F, Assi C M. Modeling and analysis of bulk bundle release schemes in two-hop vehicular DTNs. In: Proceedings of the 2011 IEEE Global Telecommunications Conference. Houston, TX, USA: IEEE, 2011. 1−6 [33] Fawaz W F, Atalla R F, Khabbaz M J. A first step towards the resolution of the starvation problem in multi-point-to-point ICRCNs. IEEE Communications Letters, 2013, 17(11): 2104−2107 doi: 10.1109/LCOMM.2013.091913.131740 [34] Arafa A, Baknina A, Ulukus S. Online fixed fraction policies in energy harvesting communication systems. IEEE Transactions on Wireless Communications, 2018, 17(5): 2975−2986 doi: 10.1109/TWC.2018.2805336 [35] Wang M, Liu J, Chen W. On delay-power tradeoff of rate adaptive wireless communications with random arrivals. In: Proceedings of the 2017 IEEE Global Communications Conference. Singapore, Singapore: IEEE, 2017. 1−6 [36] Khabbaz M J, Fawaz W F, Assi C M. A simple free-flow traffic model for vehicular intermittently connected networks. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(3): 1312−1326 doi: 10.1109/TITS.2012.2188519 [37] 徐昕, 沈栋, 高岩青, 王凯. 基于马氏决策过程模型的动态系统学习控制: 研究前沿与展望. 自动化学报, 2012, 38(5): 673−687Xu Xin, Shen Dong, Gao Yan-Qing, Wang Kai. Learning control of dynamical systems based on Markov decision processes: Research frontiers and outlooks. Acta Automatica Sinica, 2012, 38(5): 673−687 [38] Puterman M L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Hoboken, NJ, USA: Wiley, 1994. 期刊类型引用(3)
1. 宁克，刘志伟，侯滨. 全渠道供应链网络节点约束存储转发调度方法. 电子设计工程. 2024(08): 134-138 . 
百度学术2. 苏北坡，代亮，巨永锋. 基于信息安全强度的路侧设备任务调度优化策略. 网络与信息安全学报. 2024(02): 106-120 . 百度学术3. 代亮，张金龙，秦雯. 面向交通能源融合的路侧单元传输控制优化策略. 控制与决策. 2023(12): 3354-3362 . 百度学术其他类型引用(5)
-
下载:
计量
- 文章访问数: 1111
- HTML全文浏览量: 145
- PDF下载量: 137
- 被引次数: 8
