车联网中路边设施的分布式调度策略的研究

顾伟 任勇军

0 引言

车联网(Vehicular Ad Hoc Networks,VANETs)已成为智能交通系统(Intelligent Transportation System,ITS)的重要组成部分[1-2].在VANETs(图1)中，车辆通过安装车载设备(On-Broad Units,OBU)[3-4]与其他车辆和路边设施(Road Side Unit,RSU)进行通信,其中车与车之间通信简称为V2V通信,车与RSU通信简称为V2I通信.

图1 VANETs结构Fig.1 Structure of VANETs

RSU在VANETs中起重要作用.在V2V通信中，RSU为其覆盖范围内的车辆提供通信服务，包括转发消息或者起网关作用，为其覆盖范围内的车辆接入外网.通过RSU转发消息，提高了车辆从外网获取消息的成功率.

若采用有线电网给RSU供电，并沿路部署RSU,这将耗资巨大，不易实现.为此，绿色能源供电成为一个可考虑的选择.由于RSU能够采集的能量有限，需采用有效的调度策略，合理地选择服务的车辆，进而提高RSU能量的利用率.

因此，为RSU设计有效的调度策略是提高RSU能量利用率的关键.文献[5]提出一种RSU的调度策略，但不是针对绿色能源供电场景.文献[6]提出一种新的RSU部署策略，其RSU由电网和太阳能共同供电；同时，该策略还引用了休眠模式，即当RSU无需工作时，就进入休眠状态，降低能耗.文献[7]为了减少RSU的电能消耗，研究了开/关的休眠周期.文献[8]考虑绿色能源给RSU供电问题，并研究了在满足一定约束条件下最大化RSU服务的车辆数问题.

本文针对太阳能供电的RSU服务车辆的调度问题进行研究，并提出基于Markov 链和基于阈值的两个在线调度策略，提高了RSU服务的车辆数.

1 系统模型

1.1 网络模型

考虑双车道的单向道路场景，如图2所示.车辆进入路段服从均值为λ的泊松分布.令V表示N辆车构成的车辆集(V={ϑ1,ϑ2,…,ϑN})，这些车辆随机分布于路段上;令R表示部署于路旁的M个RSU集(R={R1，R2，…，RM}).

图2 单向道路场景Fig.2 One-way road scenario

每辆车在道路上的行驶速度服从在[vmin,vmax]区间的截断常态分布(Truncated Normal Distribution,TND).每辆车向RSU请求的数据大小为在[Dmin,Dmax]区间的均匀分布随机变量.

RSU仅由绿色能源供电.令hr(t)表示第r个RSURr在时隙t采集的能量，其中r=1,2,…,M.假定采集的能量为太阳能.令kr表示Rr的电池容量.RSU利用电池存储所采集的能量.令Er(t)表示Rr的电池在时隙t的能量状态.对于任意时刻，Rr所采集的能量和电池所存储的能量之和不大于其电池容量，即：hr(t)+Er(t)

1.2 通信模型

仅考虑RSU向车辆传输的下行链路.将时间细分为多个时隙，每个RSU为其覆盖范围内的车辆分配一个时隙.车辆在所分配的时隙内行驶并通信.令I表示可用的时隙集，每个时隙的时长为τ.

当车辆在道路上行驶时，车辆向其最近的RSU发送数据请求消息.该消息包含车辆的行驶速度和位置信息.每个RSU依据车辆的移动信息计算通信能量成本，并据此给该车辆分配最佳时隙，进而最小化能量消耗.

假定RSU与车辆间通信链路服从对数距离路径损耗模型[9].依据式(1)计算Rr与车辆ϑi(i=1,2,…,N)的能量成本Cr(i,t)：

(1)

式中：Ptx表示Rr在时隙t的传输功率；Prx(i,t)表示车辆ϑi在时隙t的接收功率；d0表示参考距离；dr(i,t)表示Rr与车辆ϑi在时隙t的距离；γ表示路径衰减指数；B表示信道的带宽；N0表示噪声功率；Pd0表示在参考距离时的路径损耗；D表示数据率.

2 分布式在线调度策略

本文提出两种在线调度策略：基于Markov 链的调度策略和基于阈值的调度策略.

2.1 基于Markov 链的调度策略

基于Markov 链的调度策略旨在使多个RSU间的能源管理行为一致.每个RSU依据其现有的能量和所采集的能量数据，并结合与车辆通信所消耗的能量数据，决定服务于哪辆车.

受文献[10]的启发，采用离散状态Markov链捕获RSU可采集能量的变动性和RSU将消耗的能量.先对RSU所采集的能量进行统计，再构建控制下行链RSU通信的查询表.查询表存储了RSU应该采取的最优动作.

用有限状态Markov链表述RSU能量状态.每个状态由一个二元组表示.具体而言，用二元组〈hr(t),Er(t)〉表示Rr的能量状态，其中hr(t)表示Rr所采集的能量，Er(t)表示Rr目前电池所存储的能量.

若Rr采取了动作αr(t)，则Rr的能量状态从〈hr(t),Er(t)〉转变为状态〈hr(t+1),Er(t+1)〉的转换概率为

P〈hr(t+1),Er(t+1)|〈hr(t),Er(t)〉〉(αr(t))=

P{hr(t+1)|hr(t)}×

P{Er(t+1)|Er(t),hr(t),αr(t)},

(2)

式中：αr(t)表示Rr在时隙t所采集的动作，若αr(t)为零，表示Rr为了保存能量，不为车辆提供服务.

2.1.1 能量采集模型

由于在线调度策略要实时地决策服务的车辆，因此需预测在观察时间内RSU可以采集的能量.本文采用文献[11]的能量预测(采集)模型.该模型通过历史能量数据估计在未来可能采集的能量.对RSU采集的能量进行限定( [0,hmax]),hmax表示RSU可采集的最大能量，具体内容可参见文献[11].

2.1.2 电池的能量状态

RSU电池能量的状态转换取决于与车辆通信时消耗的能量和所采集的能量.在每个时隙，RSU需要估计与车辆通信所消耗的能量.为了简化表述，将每个RSU的覆盖区域划分为5个层次(Z1,Z2,Z3,Z4,Z5)，如图3所示.

图3 RSU覆盖区域的层次划分Fig.3 Hierarchical division of RSU coverage

令Ci表示RSU服务区域Zi内车辆所消耗的能量，其中i=1,2,3,4,5.Ci的值可以通过式(1)进行计算.在每个时隙，RSU优化给最远的区域(Z5)进行服务.

2.1.3 调度策略

调度策略旨在优化RSU通信，使其在避免能量消耗殆尽的基础上最大化RSU服务的车辆数.

为了最大化服务车辆数，对动作αr(t)进行奖励.如果Rr能够与车辆通信，则κ(αr(t))=1；若不能通信，则κ(αr(t))=0.在整个观察时间T内，最大化服务车辆数就等价于获取最大的奖励.为此，建立目标函数：

(3)

式中：E(·)表示期望函数.

利用文献[12]的逆向归纳法(Backward Induction)求解式(3).令K(hr(t)，Er(t))表示从时隙t至时隙T期望所获取的最大奖励，其定义如式(4)和式(5)所示：

K(hr(T+1)，Er(T+1))=0，

(4)

E(K(hr(t+1),Er(t+1)))}.

(5)

将最大化K(hr(t),Er(t))的动作存储于查询表中.当通信状态和转换概率发生变化时，就更新此查询表.一旦完成了查询表的构建，RSU就依据查询表选择所实施的动作.

2.2 基于阈值的调度策略

基于阈值的调度策略是依据服务于车辆所消耗的能量和RSU现存储的能量信息进行调度的.与基于Markov 链的调度策略类似，基于阈值的调度策略仍假定在观察时间内，RSU能够预测其所采集的能量.

具体而言，假定在时隙t，有n辆车向Rr请求服务.令vr={ϑ1,ϑ2,…,ϑn}表示这n辆车所构建的车辆集.不失一般性，假定车辆ϑi是vr集内的任意一辆车，即ϑi∈vr.Rr先计算服务于车辆ϑi时的能量补偿因子λr,i(t)：

(6)

式中φr(i,t)表示Rr服务于车辆ϑi后剩余的能量与RSU总的电池容量之比，其定义如式(7)所示：

(7)

式中：Er(t)表示Rr现有的能量；Cr(i,t)表示Rr服务于车辆ϑi所消耗的能量；kr表示Rr的电池容量.

(8)

图4 基于阈值的调度策略的执行流程Fig.4 Execution flow of threshold-based scheduling strategy

3 性能分析

3.1 仿真环境

在Windows 7操作系统，8 GB内存，core i7 CPU的PC上进行实验仿真.道路长度2 km，采用双向四车道，每个车道方向上部署3个RSU(M=3),每个RSU的覆盖半径为400 m.RSU的电池容量kr=100能量单位(Units of Energy,UE),hmax=10 UE.具体的仿真参数如表1所示.

表1 仿真参数Table 1 Simulation parameters

本文将对基于Markov 链的调度策略、基于阈值的调度策略和文献[8]算法进行对比分析.为了简化表述，将基于Markov 链的调度策略、基于阈值的调度策略和文献[8]算法分别标记为Markov-Scheduling、Threshold-Scheduling和Reference-[8]进行比较，分析它们的服务车辆数性能.选择服务车辆数百分比作为性能指标，且服务车辆数百分比等于服务的车辆数与总的车辆数之比.

3.2 阈值ε的选取

图5给出了阈值ε对Threshold-Scheduling策略的服务车辆数的影响.考虑到RSU覆盖半径和RSU电池的容量，只能有效地覆盖几辆车，所以，ε取值1，5和8进行仿真.

图5 阈值ε的设定Fig.5 Setting of the threshold ε

大的阈值允许RSU服务更多车辆，即使它们有高的能量成本，但是当服务车辆数越多，RSUs的能耗速度就越快.相反，小的阈值限制了RSU服务的车辆数.从图5可知，相比于ε=1和ε=8，ε=5时RSU服务于车辆数最多.因此，在后续仿真实验中，ε=5.

3.3 参数λ对服务的车辆数百分比的影响

图6显示了服务的车辆数百分比随λ(平均车辆到达率)的变化情况，其中λ在1～3 辆/s变化.从图6可知，服务的车辆数随λ的增加而下降.因为λ越大，道路上的车辆数越多.在RSU数量不变(M=3)的情况下，车辆获取RSU服务的机会越少，相应地服务的车辆数百分比就随之减少.

图6 服务的车辆数百分比随参数λ的变化情况Fig.6 Impact of traffic density on the percentage of served vehicles

图6还显示， Markov-Scheduling和Threshold-Scheduling的服务车辆数百分比均高于Reference-[8].Reference-[8]算法旨在降低RSU消耗的功率，它更倾向于选择离RSU近的车辆进行服务，这就使得离RSU远的车辆得到服务的概率下降.

3.4 车辆行驶速度对服务的车辆数百分比的影响

图7为车辆行驶速度对服务的车辆数百分比的影响，其中车辆的平均速度为15～35 m/s.从图7可知，平均速度增加，服务的车辆数百分比呈下降趋势.因为车速越大，网络拓扑变化越快，RSU服务的车辆的时间越短.相比于Reference-[8]算法，Markov-Scheduling和Threshold-Scheduling算法的优势并不明显.因为Markov-Scheduling和Threshold-Scheduling算法在选择服务车辆时，并没有优先服务车速快的车辆.

图7 平均车速对服务车辆数百分比的影响Fig.7 Impact of average velocity on the percentage of served vehicles

3.5 参数hmax对服务车辆数百分比的影响

图8给出了hmax对服务车辆数百分比的影响.从图8可知，hmax越大，服务车辆数百分比也越大.因为hmax的增加，使RSU的电池电量保持较充足的概率增加，它可以服务的车辆数就越大.

图8 hmax对服务车辆数百分比的影响Fig.8 Impact of hmax on the percentage of served vehicles

此外，相比于Reference-[8]，Markov-Scheduling和Threshold-Scheduling随hmax变化的波动较大.hmax越大，Markov-Scheduling策略和Threshold-Scheduling策略的服务车辆数百分比的优势越明显.

4 结语

RSU的能量消耗直接影响部署RSU的成本.本文针对面向太阳能供电的RSU，提出两个分布式的在线调度策略.该调度策略最大化了服务的车辆数.仿真结果表明，提出的两个分布式在线调度策略能够增加服务的车辆数.本文仅针对简单场景进行分析，在仿真阶段，也仅考虑了2 km的道路.后期将进一步优化所提出的调度策略，使其适用于复杂场景.