基于服务量的异构车载网络资源调度算法

熊舸　张煜　杨勇

摘要：资源调度是提高车载网络数据吞吐量、降低数据传输时延的重要技术手段，也是车载网络的重点研究内容。本文关注异构车载网络资源调度算法研究，提出了一种基于移动服务量的异构车载网络资源调度算法（Moble ServicesResource Scheduling algorithm，MSRS），通过移动服务量精确刻画车载网络链路传输能力，在此基础上采用中继选择和最大服务量配对等手段提升移动车载网络的总吞吐量。仿真实验表明，与现有基于瞬时速率的资源调度算法相比，在不同车辆数量、车速、基站覆盖范围条件下MSRS算法都可以提供更高的数据吞吐量。

关键词：计算机网络；移动服务量；车载网络；资源调度算法；二分图

中图分类号：TP311 文献标识码：A DOI：10.3969/j.issn.1003-6970.2015.05.012

0 引言

车载网络（Vehicular Ad Hoc Networks，VANETs）是支撑智能交通系统（Intelligent Transportation System，ITS）的关键技术，由具有无线通信能力的车辆节点或路边基础设施（Roadside Infrastructure Unit，RIU）构成。与传统移动自组织网络不同，车载网络管理的是公路上高速移动的机动车辆，网络拓扑随车辆移动动态变化，基于车载网络的交通应用对通信实时性要求较高。资源调度是提高车载网络数据吞吐量、降低数据传输时延的重要技术手段，是车载网络的重点研究内容。

为改进传统智能交通系统低效的通信模式，车载网络以更直接、高效的方式收集、传播和分发信息。资源调度是提高车载网络数据传输能力的重要技术手段，车载网络资源调度的主要挑战在于如何有效利用车载网络物理层条件（车辆移动性、车辆无线信道、车辆相对位置）满足应用层的需求。

Liu等人研究了如何利用RIU作为协作中继帮助车载网络车辆传输数据。Wu等人提出了一种从路边基站到行驶车辆的下行调度算法，对车载网络下行信道资源进行有效管理。Zhang等人提出了同时考虑上行和下行请求的调度算法。2013年Li针对WiMAX网络和WAVE网络中资源调度方式不同，提出一种基于反馈的两级资源调度机制。H.Ilhan等人提出了一种基于放大转发的自组织Ad Hoc网络的车载网络架构。M.Seyfi等人提出了一种两跳车载网络的中继选择策略。M.F.Feteiha等人提出了一种基于多天线放大中继的车载网络资源调度策略。Zheng等人基于图论提出了一种车辆与基础设施之间的链路V2I（Vehicle-to-Infrastructure）和车辆与车辆之间的链路V2V（Vehicle-to-Vehicle）并存的车载网络资源调度方法。文献[18]基于多选择的联合链路调度与资源优化方法。文献[19]基于LTE-Advanced架构提出了中继车载网络的一种传输方法。

这些研究从车载网络信道资源分配管理角度提高了路边基站的访问效率。不足之处在于，现有车载网络资源调度方法大多都基于车辆的瞬时状态，没有考虑车辆的移动性，难以准确刻画车载网络链路传输能力并充分发挥车载网络移动下的系统性能。

1 异构车载网络

如图1所示，一个典型的异构车载网络结构包含公路上高速行驶的车辆节点和RIU，所有的车辆都可通过V2I/V2V两种链路与RIU通信，进而接入Internet。同时，车辆与车辆之间通过V2V链路互相通信，共享路面信息。本文研究的异构车载网络由V2I（采用LTE-Advanced协议）和V2V（采用Dedicated Short RangeCommunication，DSRC协议）两部分链路组成；采用的调度算法是通过调度管理车载网络传输链路资源（V2I与V2V），帮助车载网络范围内各车辆互相协作，从而提高车载网络整体数据传输性能。

针对车载网络中网络节点是高速移动的机动车辆，本文提出了一种基于移动服务量的异构车载网络资源调度算法（Moble Services Resource Scheduling algorithm，MSRS）。MSRS算法中，由基站对两种网络资源进行统一调度。与现有算法（Achievable Rate-based Resource Scheduling algorithm，ARRS）使用车辆瞬时可达速率调度不同，MSRS算法首先依据车辆的运行轨迹计算调度周期内V2I和V2V链路移动服务量；根据V2I移动服务量分配车辆使用直接与基站通信还是通过协作转发车辆与基站通信；若车辆为协作通信方式，基站利用图论中的二分图最大权重匹配算法为车辆分配协作转发车辆，车辆作为二分图顶点、V2I和V2V链路为二分图边、V2I和V2V移动服务量为边的权重。MSRS算法为异构车载网络数据传输提供最大总吞吐量传输方案。仿真实验表明，与现有基于瞬时速率的资源调度算法相比，在不同车辆数量、车速、基站覆盖范围条件下MSRS算法都可以提供更高的数据吞吐量，与穷举资源调度算法相比，MSRS算法复杂度更低。

2 车载网络链路误差分析

车载网络中由于车辆快速移动，从而导致网络拓扑快速变化，节点间的通信链路质量变化也很快。采用基于瞬时可达速率的车载网络资源调度算法，为了适应网络的这种快变特点，必须缩短调度周期，不断计算并更新调度结果。这会带来调度计算和网络信令的开销大幅增长，降低车载网络有效传输能力。

如图2所示场景，V1远离RIU行驶，V2、V3与V1相对行驶靠近RIU。在图2（a）时刻车载网络进行资源调度，此时若采用传统的瞬时可达速率作为优化目标效用函数，由于V1此时离RIU近、信道条件好，则V3的最大可达速率策略为选择V1作为协作节点协助V3与RIU通信。图2（b）所示为调度周期结束时车辆的所在位置。比较图2（a）与（b）可以看出，由于V3与V1相对行驶且V1逐渐远离RIU，V3通过V1协助与RIU的可达速率不断减少，调度周期内V3获得的通信速率大大少于预期。可见，图2（a）调度获得的最优调度方案在实际运行时并不是最优方案，调度方案预期性能与实际效果有较大误差。

造成这种误差的原因是资源调度方案只考虑车载网络的瞬时静态可达速率状态，并以此为依据进行资源调度。而车载网络是不断运动变化的网络，节点相互位置动态变化，以静态方案规划动态变化的网络必然造成误差，难以达到最优配置网络资源的目的。为减少误差，现有资源调度方案大多通过增加调度频率、减少调度周期的方法减少网络在调度周期运行期间与方案规划时状态的差异。这种方法增加了通信开销，减少了算法有效持续时间，越来越不适应车辆密度越来越大、车速越来越快的现代交通网络。

因此，本文提出基于移动服务量的车载网络资源调度算法，通过计算调度周期内车辆能获得的移动服务量代替调度时的瞬时可达速率进行车载网络资源调度。该算法能反映调度周期内车辆位置变化带来的车辆可达速率改变，从而更精确的描述车载网络状态变化，减少车载网络资源调度算法在实际应用中出现的误差。

3 移动服务量

为设计更精确的资源调度方案，采用移动服务量代替瞬时可达速率，计算车辆在一个调度周期可以获得的移动服务量，从而更精确的描述车载网络链路状态，为更精确的资源调度方案设计打下基础。定义第k个调度周期可以获得的移动服务量为：

图7仿真车辆数目对MSRS算法的影响。20、40、60、80、100、120、140、160、180、200辆车辆随机分布在道路上，车辆最大时速35m/s，RIU覆盖半径500m，每种车辆数目进行200次实验取均值。从图7可以看出，十字路口场景下，无论车辆数目如何变化，MSRS算法相比ARRS算法所获得的资源分配方案更优，能使车载网络达到更大的数据吞吐量。

图8仿真车速对车载网络资源调度算法的影响。100辆车随机分布在道路上，RIU覆盖半径500m，车辆最大时速为22-52m/s，每种车速进行200次实验取均值。图8可以看出，十字路口场景下，无论最大车速如何变化，MSRS算法相比ARRS算法得出的资源分配方案更优，能使车载网络达到更大的数据吞吐量。随着最大车速增加，MSRS算法相对ARRS算法的总吞吐量也呈现不断增长趋势；在最大车速大于40米/秒后，MSRS算法相对ARRS算法的性能优势更明显，说明随着车速增加，车辆在一个调度周期移动的距离增大，ARRS算法描述车辆链路性能的误差也越大，因此MSRS算法相对ARRS算法的性能优势更加明显，MSRS算法更适合高速移动车载网络。

图9仿真RIU覆盖范围对车载网络资源调度算法的影响。100辆车辆随机分布在道路上，车辆最大时速为35m/s，RIU覆盖半径500-1500m，为每种覆盖半径进行200次实验取均值。

图9表明，随着RIU覆盖范围的不断增加，MSRS算法和ARRS算法的总吞吐量都在不断下降。这是因为RIU发送功率不变，当RIU覆盖范围增加时场景面积相应变大，车辆间、车辆与RIU间距离也相应增加，因此路径损耗变大、接收功率降低、吞吐量随之下降。但无论RIU覆盖范围如何变化，MSRS算法都优于ARRS算法，MSRS算法使车载网络达到更高的数据吞吐量。

6 结论

本文首先分析了近期国内外在车载网络资源调度上的研究现状以及研究中存在的问题。针对这些问题，本文引入移动服务量的概念，提出了基于移动服务量的异构车载自组网资源分配算法（MSRS），根据车载网络的实际因素（车速、位置）来改进车载网络状态描述，更精确的根据车载网络状态分配车载自组网资源，利用排序选择、KM算法以及二分查找法设计了降低复杂度的算法提高网络整体吞吐量。利用MATLAB分别从车载网络总车辆数量、最大车速、RIU覆盖范围三方面仿真对车载网络整体吞吐量的影响，结果表明与现有基于瞬时速率的资源调度算法相比，MSRS算法可以提供更高的数据吞吐量，与穷举资源调度算法相比，MSRS算法有更低的算法复杂度。