一种公平的路边基站下行业务调度算法

闫中江，李 波，高 田，左晓亚

（西北工业大学电子信息学院，陕西西安 710072）

一种公平的路边基站下行业务调度算法

闫中江，李 波，高 田，左晓亚

（西北工业大学电子信息学院，陕西西安 710072）

针对车辆网络中现有路边基站下行业务调度算法公平性差的问题，提出了一种公平的基于网络流的路边基站下行业务调度算法.首先，建立包含车辆节点和时隙节点的二部图，如果在给定时隙内车辆节点位于路边基站的通信覆盖范围内，则在该车辆节点与对应的时隙节点之间添加边；然后，在二部图的基础上添加虚拟的源节点和目的节点，建立网络流图；最后，通过计算网络流图的最小花费最大流，得到了一种公平的路边基站下行业务调度策略.仿真结果表明，在保证最大化车辆业务请求的情况下，与现有算法相比，这种算法提高了车辆之间业务请求的公平性，在offline情况下公平性提高了约116.4%，在online情况下公平性提高了约25.9%.

车辆网络；业务调度；公平性；网络流

路边基站（Road Side Unit，RSU）是车辆网络中为过往车辆提供信息服务的基础设施.为克服有线电力部署的局限性，采用太阳能、风能等形式的电池供电，成为车辆网络中路边基站的主要工作方式之一［1-2］.因此，在满足车辆业务请求的情况下，设计低能耗、公平的路边基站下行业务调度算法具有重要意义［3-5］.路边基站的能耗主要由路边基站数据传输能耗组成.文献［1］提出了一种启发式的Nearest-Fastest业务调度算法，降低了路边基站数据传输能耗，但却没有考虑最大化车辆业务请求的问题；文献［2］提出采用网络流的方法，在最大化车辆业务请求的情况下，降低了路边基站数据传输能耗，但却没有考虑车辆之间的公平性问题.

当车辆业务请求较少时，每个车辆的业务请求都能被成功服务，不需要考虑车辆间的公平性问题.然而，当车辆业务请求较多时，则可能会出现部分车辆的业务请求无法得到服务的情况，即出现业务调度不公平的问题.在城市或部分高速公路场景中，车流量大、车辆业务请求多，所有这些业务请求均需路边基站服务，因此如何在最大化总的车辆业务请求的情况下，保证每个车辆的业务请求都能够得到公平调度，同时降低路边基站的数据传输能耗，成为一个亟待解决的问题.

笔者提出了一种基于网络流的业务调度算法，在保证最大化车辆业务请求的情况下，提高了车辆之间业务调度的公平性.

1 系统模型

设有1个路边基站被部署在高速公路上，为过往车辆提供业务请求服务.路边基站只有一个无线收发机，在任意时隙t，路边基站只能与一个车辆进行通信.每个进入路边基站传输覆盖区域的车辆，在与路边基站建立连接时都向路边基站提出业务请求；路边基站根据其传输覆盖区域内车辆总的业务请求，做出下行业务调度传输决策，最大化地满足车辆的业务请求，并同时保证车辆间的公平性，降低路边基站数据传输能耗.

设车辆的随机到达过程是密度为λ的泊松过程，在时间段T内共有N辆车经过路边基站，其中时间段T=｛t1，t2，…，tM｝，表示时隙集合.令V= ｛v1（q1，s1），v2（q2，s2），…，vN（qN，sN）｝，表示过往车辆集合，其中qi表示车辆vi的请求，si表示车辆vi的速度，1≤i≤N.令di，j表示车辆vi与路边基站在时刻tj的距离，1≤i≤N，1≤j≤M，则由无线信号的自由空间衰弱模型可得，为使得车辆vi成功接收路边基站数据，路边基站所需的发送功率为

其中，Rmin（Rmax）为路边基站与车辆之间的最小（最大）距离，P0（d0）为参考功率（距离），ρ为扩展因子，α为路径衰弱指数.因此，在时隙t内，路边基站所消耗的能量为

其中，γ=τρP0dα0.

设路边基站能够将每个时隙独立地分配给不同的车辆.当时隙tj被分配给车辆vi时，路边基站将花费Ei，j的能量，且车辆vi一个单位的业务请求将被满足.定义布尔值变量Bi，j表示时隙tj是否被分配给车辆vi，表示为

则B=｛Bi，j|1≤i≤N，1≤j≤M｝，为路边基站所确定的对应时隙集合T的业务调度策略.

（i）最大化总的车辆业务请求.定义车辆业务请求满足差，则该目标等价于

令S2为求解式（5）所得的业务调度策略集，S2⊆S1.在此基础上进一步地最小化路边基站进行业务传输所花费的能量.

（iii）最小化路边基站数据传输能耗.在求得式（4）～（5）业务调度策略的基础上，该目标为

由于路边基站的主要作用就是为过往车辆提供信息服务，因此最大化地满足车辆请求（即式（4））的优先级最高，之后再进一步地最大化业务调度的公平性（即式（5）），最后一步是最小化路边基站数据传输的能耗（即式（6）），则具有较低的优先级.

在不同的场景下，笔者所提出的问题具有不同的形式.当每个车辆的请求较少，并且所有的车辆请求都能够被满足时，式（4）～（5）的最优值为零，式（4）～（6）退化为最小化路边基站能耗问题（即式（6））.该最小化路边基站能耗的问题可以采用基于网络流的方法得到最优解［2］.然而，当车辆请求较多，存在部分车辆的请求不能够被满足的情况时，文献［2］则没有考虑车辆之间的公平性问题，不能得到公平性的最优调度策略.因此，笔者将着重研究当车辆请求较多、存在部分车辆请求不能被满足情况时，如何公平地服务车辆请求、并同时最小化路边基站能耗的问题.

2 基于网络流的公平业务调度算法

一般来说，多步最优化问题（比如式（4）～（6））的求解非常困难.因为后续步骤的最优化问题的求解是基于前面问题的求解.比如，需要首先求出式（4）的所有最优解之后才能求出式（5）的最优解；接着，求出式（5）的所有最优解之后才能求出式（6）的最优解.笔者提出一种基于网络流的公平业务调度算法，可以一次性地求解该多步最优化问题（即式（4）～（6）），极大地降低了问题的求解复杂度.

2.1算法描述

图1给出了笔者所提出的网络流算法中所采用的二部图与网络流图.基于网络流的公平业务调度算法的伪代码如下:

图1　二部图与网络流图

（1）对于每一条连接S与vi的边e（S，vi），设置边的容量a（S，vi）=qi，其物理意义是:保证为车辆vi所分配的时隙总数不超过车辆vi的请求数qi.设置边的花费c（S，vi）=ri2Cmax，其中Cmax是路边基站最大传输能耗的倍数，其物理意义是:最大化车辆之间业务请求的公平性Jain因子.

（2）对于每一条连接vi与tj的边e（vi，tj），设置边的容量a（vi，tj）=1，其物理意义是:每个时隙路边基站仅能满足车辆vi一个单位的请求.设置边的花费c（vi，tj）=Ei，j，其物理意义是:如果路边基站在时隙tj给车辆vi传输数据，则将需要花费Ei，j的能量.

（3）对于每一条连接tj与D的边e（tj，D），设置边的容量a（tj，D）=1，其物理意义是:每个时隙路边基站仅能传输一个单位的信息.设置边的花费c（tj，D）=0，其物理意义是:该边没有花费.

至此，网络流图Gf构建结束.通过在Gf上运行典型的最小花费最大流算法，比如Push-relabel算法［7］，将可以计算出图Gf对应的最小花费最大流F.如果在所得的最小花费最大流F中，边e（vi，tj）的流不为零，则表示路边基站应该将时隙tj分配给车辆vi，即对应的布尔值变量Bi，j=1.

2.2online数据传输决策讨论

上节给出了在已知所有时隙以及所有到达车辆的情况下（即offline的情况［2］），计算公平的路边基站业务调度问题的算法.需要指出的是，该算法同样适用于在未知所有时隙以及所有到达车辆的情况（即online的情况［2］）.下面讨论笔者所提出的算法如何应用到online的情况.

首先，当第1辆车v1进入路边基站的传输覆盖范围时，使用笔者所提出的算法，即可为车辆v1计算出一个最小化路边基站能耗的业务调度算法（因为此时只有一辆车，故最大化公平性Jain因子（式（5））不存在）.此时，车辆节点集V′=｛v1｝，时隙节点集T′=｛t1，t2，…，tM′｝，其中M′=2Rmaxs1，s1为车辆的恒定速率.其他部分参照基于网络流的公平业务调度算法.

设在时隙tj，一个新的车辆vi到达并进入到路边基站的数据传输区域.设此时在路边基站的数据传输区域内，同时还存在着N′个车辆正在被路边基站服务.不管现有的业务调度决策是否已经被执行结束，笔者所提出的基于网络流的公平业务调度算法将被重新调用，并计算新的业务调度决策.此时，节点集V′=｛v1，v2，…，vN′｝，时隙节点集T′=｛tj，tj+1，…，tj+M′｝，其中tj+M′为V′中最后一个车辆离开路边基站数据传输区域的时隙.其他部分参照基于网络流的公平业务调度算法.

当新的数据传输决策被计算出来之后，路边基站将更新并执行新的数据传输决策.在online情况下，每当有新的车辆到达，路边基站都将根据当前车辆的情况，重新计算并执行新的数据传输决策.

2.3算法的计算复杂度及算法可行性讨论

笔者所提算法的计算复杂度取决于所使用的Push-relabel算法的复杂度，而Push-relabel算法的复杂度为O（V2E ）［7］，其中V 为网络流图中节点的个数，E 为网络流图中边的个数.文中，在最坏情况下，V=2+N+M，而E=N+M+NM，因此算法的计算复杂度为O （max（N3，M3））.

文献［8］提出了一种分层的车载容迟网络架构，其中控制层面（BSC）负责完成车辆注册、关联等，并以较大的通信半径、较低的数据传输速率，在车辆与路边基站进行数据通信之前建立连接，数据层面（BAD）则以较小的通信半径、较大的数据传输速率在车辆进入到BAD区域时才开始进行数据传输.假设BSC半径区域为300 m，BAD区域半径为200 m，车辆行驶速度为120 km/s，则车辆在进入BSC后而未进入BAD前的时间为7.8 s；设车辆到达密度λ=0.1辆/秒，时隙长度t=0.01 s，则在BAD区域内平均有3辆车，总的时隙个数M=1.2×103；设路边基站的CPU时钟频率为1 GHz，则完成O（max（N3，M3））的计算平均需要1 s（远小于7.8 s），因此笔者所提出的算法是可行的.

3 仿真结果

总的车辆请求信息被满足的个数、路边基站总的能耗以及业务调度决策的公平性是衡量业务调度决策性能的重要指标.将笔者所提出的算法与文献［2］中的算法进行了仿真比较，同时比较了offline和online两种情况.

设总的仿真时间Tsimu=150 s，车辆到达密度λ=0.1辆/秒.设车辆速度s为服从高斯分布的随机变量，平均车速s=120 km/s，方差为2.0.设路边基站最大传输半径Rmax=200 m，车辆与路边基站之间的最小距离Rmin=5 m.设每个车辆的业务请求从40以步长10增长到100.对于每一组仿真参数，随机产生30个仿真场景，并取所有结果的均值为最终的仿真结果.

图2给出了文献［2］中的算法与笔者提出的算法分别在offline和online情况下，总的车辆请求信息被满足的情况.从图中可以看出，在两种情况下，两种算法的性能几乎完全相同.由于online情况下车辆以及业务请求信息的不完整性，总的车辆请求信息被满足的个数比offline情况要小约6.5%.

图2　总的车辆请求信息被满足的个数

图3 路边基站总的能耗

图3给出了两种算法分别在offline和online情况下，所有车辆总的能耗情况.从图中可以看出，在offline情况下，由于所传输的业务信息较多，因此路边基站花费了比online情况更多的能量；在online情况下，两种算法性能差别不大，笔者提出的算法花费的能量比文献［2］的高出约1.2%.

图4　offline情况的公平性Jain因子

图5 online情况的公平性Jain因子

图4和图5分别给出了两种算法在offline和online情况下的公平性Jain因子的比较.在offline情况下，笔者提出算法的Jain因子比文献［2］的高出约116.4%.在online情况下，笔者所提出的算法比文献［2］的高出约25.9%.

4 总 结

在车辆网络中，路边基站的数据业务传输策略是车辆网络高效工作的基础.笔者研究了在车辆请求较多的情况下，如何公平地进行业务调度传输并同时最小化数据传输能耗的问题，提出了一种基于网络流的业务调度算法，可适用于offline和online两种情况.仿真结果表明，与现有文献［2］只最小化路边基站能耗的算法相比，笔者提出的算法在保证最大化车辆被服务业务请求的情况下，提高了车辆间被服务的公平性，特别是在offline情况下公平性提高了约116.4%，在online情况下公平性提高了约25.9%.

［1］HAMMAD A A，BADAWY G H，TODD T D，et al.Traffic Scheduling for Energy Sustainable Vehicular Infrastructure ［C］//Proceedings of the 2010 IEEE Global Telecommunications Conference.New York:IEEE，2010:5683759.

［2］HAMMAD A A，TODD T D，KARAKOSTAS G，et al.Downlink Traffic Scheduling in Green Vehicular Roadside Infrastructure［J］.IEEE Transactions on Vehicular Technology，2013，62（3）:1289-1302.

［3］YAN Z，ZHANG Z，JIANG H，et al.Optimal Traffic Scheduling in Vehicular Delay Tolerant Networks［J］.IEEE Communications Letters，2012，16（1）:50-53.

［4］RAMAIYAN V，ALTMAN E，KUMAR A.Delay Optimal Scheduling in a Two-hop Vehicular Relay Network［J］. Mobile Networks and Applications，2010，15（1）:97-111.

［5］KHABBAZ M J，FAWAZ W F，ASSI C M.Probabilistic Bundle Relaying Schemes in Two-hop Vehicular Delay Tolerant Networks［J］.IEEE Communications Letters，2011，15（3）:281-283.

［6］JAIN R，DURRESI A，BABIC G.Throughput Fairness Index:an Explanation［R］.Columbus:Department of CIS，the Ohio State University，1999.

［7］CORMEN T H，LEISERSON C E，RIVEST R L，et al.Introduction to Algorithms［M］.2nd Edition.Cambridge:MIT Press，2001.

［8］ISENTO J N G，RODGIGUES J J P C，DIAS J A F F，et al.Vehicular Delay-tolerant Networks a Novel Solution for Vehicular Communications［J］.IEEE Intelligent Transportation Systems Magazine，2013，5（4）:10-19.

（编辑:郭 华）

Fair traffic scheduling algorithm for the roadside unit

YAN Zhongjiang，LI Bo，GAO Tian，ZUO Xiaoya （School of Electronics and Information，Northwestern Polytechnical Univ.，Xi’an 710072，China）

To improve the fairness performance of the downlink traffic scheduling algorithm，a network flow based downlink traffic scheduling algorithm is proposed for the roadside unit（RSU）in vehicular networks.In the proposed algorithm，a bipartite graph is constructed firstly，where the node set is composed by the vehicle set and the timeslot set.At any given timeslot if a vehicle can communicate with the RSU，then an edge between the given timeslot and that vehicle is added into the edge set.Next，a flow network graph is constructed based on the bipartite graph by adding a virtual source node and a virtual sink node.By applying the conventional minimum cost maximum flow algorithms，a minimum cost maximum flow can be computed，which is converted to the fair traffic scheduling strategy.Simulation results show that，when the total vehicle requirements are maximized，compared with the existing algorithms，the fairness performance of the proposed algorithm is improved by 116.4%in the offline case，and by 25.9%in the online case.

vehicular networks；traffic scheduling；fairness；network flow

TP393

A

1001-2400（2016）01-0133-06

10.3969/j.issn.1001-2400.2016.01.024

2014-08-18 网络出版时间：2015-04-14

国家自然科学基金资助项目（61201157，61271279）；国家863计划资助项目（2014AA01A707）；国家重大专项资助项目（2015ZX03002006）；西北工业大学基础研究基金资助项目（3102015ZY038，3102015ZY039）

闫中江（1983-），男，副教授，博士，E-mail:zhjyan@nwpu.edu.cn.

网络出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.021.html