基于时隙的R2V网络上行链路规划通信价值最大化研究

朱容波，王洪波，张 浩，徐文刚

(中南民族大学 计算机科学学院，武汉 430074)

基于时隙的R2V网络上行链路规划通信价值最大化研究

朱容波，王洪波，张 浩，徐文刚

(中南民族大学 计算机科学学院，武汉 430074)

对路边单元与车辆之间(R2V)进行上行数据传输的价值最大化问题进行了研究，通过对RSU时域进行时隙划分，采用Santa Claus Problem进行规约，证明了传输价值最大化是NPC问题，并进行了线性规划描述.分别对静态和动态的场景进行了模拟，针对静态场景，提出了近似比为1+ε的多项式时间近似调度算法(PTAS)；针对动态场景，分别模拟了先到先服务算法(FCFS)，以及基于速度、权重、传输量为启发函数的启发式算法(WFCS).仿真结果表明：WFCS算法能更好地适应网络通信价值最大化的需要，在保证网络服务质量的同时有效提升网络整体通信价值.

车载自组织网络；路边单元；路边单元与车通信；最大通信价值；线性规划

近年来，车载自组织网络(VANETs)得到了学术界与工业界的极大关注.随着车辆通信需求和车流量的增加，如何确保不同类型的业务需求与服务质量(QoS)成为重要的研究问题[1].本文基于通信时隙，对路边单元(RSU)与车辆之间(R2V)上行网络通信最大价值传输问题进行了研究.证明了通过时隙进行车载网络通信的价值最大化算法是NP完全的.同时，也给出了价值最大化过程的多项式近似调度算法方案(PTAS)和动态场景的启发式算法(WFCS)，在获得更大传输价值的同时，保障业务的QoS.

在文献[2-5]中，研究者们提出了基于聚簇的通信手段，通过簇头节点来统一规划通信，在避免信息碰撞导致的丢包重传的同时提升了网络吞吐量.为了提升传输质量，同时考虑到节能，研究者提出了对车辆或者RSU的传输范围进行动态调整的方案[6-10]，通过传输范围的动态优化实现节能，并提升传输效率.

Hammad A A等人[11]提出了基于时隙的传输规划算法，通过混合整数线性规划思想(MILP)，提出了R2V通信之间最小通信能耗的算法，并给出了时域内最小通信能耗的下限，同时也给出了具有较低时间复杂度的Greedy Minimum Cost Flow (GMCF)算法和Nearest Fastest Set(NFS) 算法[12].文献[13]中考虑了RSU的吞吐量最大化问题，通过最优控制理论提出了一个基于802.11e 混合控制信道访问(HCCA)的规划算法.

本文提出的静态贪婪最大传输价值算法(MTVA-G)，通过贪心选择可以有效避免无效通信的能量损耗，从而达到节能的效果.与聚簇方案[2-5]、传输范围动态调整方案[6,7]相比，基于贪心的MTVA-G对节能的考量粒度更粗，通过选择能够达到最大通信价值的车辆，忽略掉部分低价值车辆的通信来实现节能，并获得更高的传输价值.

R2V上行网络最大通信价值采取了基于时隙的研究方案，如图1所示，每个时隙分为监听态和传输态，不同于文献[11]采取最小费用最大流的算法，本研究采用MTVA-G算法来达到近似比为1+ε的多项式时间近似方案.

图1 时隙结构图Fig.1 The time-slot structure

1 系统模型

1.1 问题描述

图2所示是一个RSU与车辆队列进行通信的场景，圆圈部分代表RSU的通信范围.当车辆通信需求足够大的时候，RSU将无法满足所有车辆的通信需求，这意味着RSU在通信的过程中将有所取舍.本文中所用到的参数如表1所示.

定义车辆i具有属性Vi(Si,Di,Wi,Ci,t，DISi,t集合内各属性分别代表速度、数据传输量、权重、当前时隙传输完成率、当前与RSU距离.特别指出的是，任意车辆Vi的权重Wi为后续算法的初始输入，是车辆进行通信的基本属性.

定义1 传输价值(Transmission Value, TV)为：

TV=Wi·Di.

(1)

图2 RSU与覆盖范围内车辆进行通信Fig.2 RSU communicating with vehicles within its range

表1 参数含义Tab.1 Parameters meaning

定义2 时域T，对于某一个车辆队列，从第一辆车进入到最后一辆车驶出RSU通信范围的时间区间T(1,2,3,4，…,n)，其T包含n个时隙.车辆集合V(V1,V2,V3,…,Vm)，数据Di,i∈(1,2,3,4，…,m)为各车辆通信需求.

定义3 车辆集合V在RSU时域T(1,2,3,4,…,n)内可完成的数据最大传输量为：

(2)

称为T时域内的最大通信价值(MCV)，其中Ki,t是一个布尔型二维矩阵，表示在t时刻内是否与车辆节点i通信，0代表不通信，1代表通信.

(3)

(4)

(5)

(6)

1.2 复杂度分析

定理1 R2V上行网络通信价值最大化问题是NP完全的.

证明 可以从经典的圣诞老人问题[14]来进行规约，前者已经被证明是NP完全问题.

关于圣诞老人问题，描述如下：

圣诞老人有礼物集合P{1,2,3,4,…,n}，存在儿童集合K{1,2,3,4,…,n}，其中每个儿童对P中的礼物有着不同的期待值Ei,j，假设给定一个期待值的阈值S，要求找出这样的一种礼物分配方式，使得每个儿童得到的礼物满意度(期待值)之和不小于S，即：

(7)

(8)

Dk,p={0,1},∀k∈K,∀p∈P,

(9)

(3)式两边同时除以Di,可写为：

(10)

同理变换(8)式：

(11)

1.3 传输价值最大化算法

1.3.1MTVA-G算法

MTVA-G：基于贪心的静态算法描述如下：

Sortallvehiclesbywi

For artitraryε>0, letk=「1/ε⎤

A(I)=0

For 0≤j≤kFor arbitrary ∪jwhich hasjvehicles Step1: 把 ∪j中的j辆车放入计划表 Step2: 对剩下的n-j辆车调用贪心

Greedy()，并更新A(I)保持最大

Greedy():

sort all vehicles in ∪ bywi

letj=0;K=0;CV=0;Z={}

Whilej

j=j+1

ifSj≤T.Length ()-KZ.append(Vj)K=K+SjCV=CV+CVj

end if

end while

return Z

通过定理1可知，此问题是NP完全的，本研究设计近似比为1+ε的MTVA-G算法，来完成本次通信的选择策略.

推论1 MTVA-G算法可以得到与最优解之间近似比为1+ε的车辆通信价值最大化的PTAS结果.

证明 令集合X是最优解对应的车辆集合，

(12)

如果|X|≤k，则MTVA-G算法给出了最优解.如果|X|>k，令Y={u1,u2,u3,…,uk} 是集合X中价值最大的k辆车，Z={uk+1,uk+2,uk+3，…,ur}=XY，其中车辆按权重排序.

如MTVA-G算法所示，假设在某个循环中，算法先选中了Y中的k辆车，令um是其中第一个没被MTVA-G算法选中的车辆，令集合Z是被算法在um之前选中的，且不在{u1,u2,u3,…,um}中的车辆集合，车辆j需要的时隙总数为Sj，为方便理解，这里令车辆j的传输价值为Vj，车辆队列时域T的总时隙容量为C，则有：

(13)

1.3.2FCFS算法

FCFS算法是VANETs中R2V经典动态算法，对于RSU，总是为进入通信区域内的车辆提供服务.当然，这样的通信方式存在显著的局限性，RSU很可能会由于时隙被低权重的车辆占用而错失与高权重车辆的通信.FCFS的详细描述如下：

RSUwaittingforCommunication,CV,WaittingQueue={null}

While(1){

ifVjin Range Then

WaittingQueue.add(Vj)

if (等待队列非空 &&Vj传输完成) then

WaittingQueue.next().Communication()

Else{

Record CV

CV=0

}

}

在动态场景下，由于车辆到来的未知性，FCFS算法是最简单的R2V通信策略.如图1所示，每个时隙在开始时都会有一段时间处于监控模式，用于接收新的车辆请求，如果当前车辆处于通信状态，当有新进入车辆时，则将车辆放入待通信队列，并按照先后顺序与车辆进行通信.

FCFS在车辆较稀疏的场景下表现很好，由于其O(1)的时间复杂度，对RSU的计算能力要求较低，但是时延较大，虽然可以保证RSU的吞吐量，但是由于其先来先服务的简单策略，总体QoS并没有保证.

1.3.3 WFCS算法

FCFS算法虽然以较低的时间复杂度来服务车辆，但是其缺点也比较明显，那就是在车辆比较密集、通信压力较大时，没有一种竞争机制可以让高权重的车辆优先通信，基于此，提出了高权重优先通信启发式算法(WFCS)，详细描述如下：

RSU waitting for Communication, CV, WaittingQueue={null}

While(1){

ifVjin Range Then

WaittingQueue.add(Vj)

if (RSU.communication=NULL) then

RSU.communication=WaittingQueue.next()

else{

if(Vj.HValue>Now.HValue) then{//大于当前启发函数值

RSU.communication=Vj//切换通信对象

waittingQueue.add(RSU.communication)

}

end if

}

end if

}

WFCS是一种动态算法，它以速度和权重作为启发函数的自变量，RSU综合车辆的行驶速度和权重以及传输完成率.将它们综合考量后排序，在每个时隙选择权重最高的车辆来进行通信，从而优化时域内的通信价值.WFCS算法考虑了车辆进入时的速度、权重、整体传输量等参数，WFCS会根据车辆的传输完成率动态地改变车辆的初始权重，当有新的车辆进来时，根据启发函数的结果来决定是否切换通信对象.算法的启发公式如下：

x=Wi·Di·Si,

(14)

(15)

在这里，(15)式引入了Sigmoid函数，由Sigmoid函数的特性可知，当车辆上行传输完成率大于50%时，新进入车辆无法打断本次传输.

每当有新进入车辆，车辆首先向RSU传输自身状态参数，RSU根据启发函数计算出车辆通信权值，并和当前通信车辆的权值作比较，选择权值较大的车辆进行通信.当车辆速度较快，自身隐含通信价值较高时，Sigmoid函数可以保证车辆的启发函数值以较快的速度提升，优先获得传输机会完成通信.

2 仿真结果

本实验采用的仿真工具为Python 2.7(matplotlib + numpy + pandas).在实验参数的设定上，分别在车辆密度、速度上进行上行网络通信价值的对比，并假设车辆在通过RSU覆盖范围时是匀速直线运动，速度、权重、通信数据量均为算法输入参数.

如图3所示，在车速较慢、队列车辆较少的稀疏状态，由于通信压力较低，WFCS和FCFS的表现非常接近.但在车辆密集场景下，由于RSU已经无法满足所有队列车辆的通信需求，在通信的取舍上，由于WFCS存在通信打断策略，FCFS仅仅依靠车辆进入的先后规划通信，WFCS则会在Sigmoid启发函数的作用下，在权重、数据量、车速优于当前通信车辆时，会打断当前车辆通信，接管当前时隙.

图3 稀疏场景(RSU:辐射半径300m,队列长度：10)Fig.3 Sparse scene(RSU TR:300m,QL:10)

如图4所示，在多数情况下，WFCS算法由于启发函数的存在比FCFS获得了更高的通信价值，然而在实际场景中，存在WFCS算法在选择车辆的过程中，由于频繁地被打断造成了部分低权重车辆无法获得通信机会，浪费了先前通信的部分时隙，反倒获得了较之FCFS算法更低的通信价值，然而这种情况一般出现在通信被后进入车辆多次打断的场景下，并且后进入车辆占用的时隙较多，等待队列的车辆没有足够的通信时隙，发生概率较低.

图4 密集场景(RSU辐射半径:300m,队列长度：100)Fig.4 Dense scene(RSU TR:300m, QL:100)

如图5所示，车辆在高速场景下，队列通过RSU覆盖范围的时间显著缩短，被服务的车辆数目减少， WFCS在高速场景下有更大概率选择高权重车辆，由于启发函数是Sigmoid函数，在速度很快的情况下趋近于阶跃函数，高权重车辆很容易打断低权重车辆的通信，从而占据时隙完成通信.因此，在高速场景的仿真中，WFCS算法表现较好.

图5 高速场景(RSU 辐射半径300m，车速：30-40m/s)Fig.5 High speed scene(RSU TR:300m,Speed:30-40m/s)

如图6所示，在能耗方面，对随机车辆队列进行50次通过仿真模拟，从这3种算法的能耗对比可见，由于WFCS和FCFS算法是动态的满负荷通信，故此两种算法能量损耗相同，能耗曲线完全重合.而静态MTVA-G贪心算法则有粗粒度的节能效果，会直接放弃低通信价值的车辆通信，因此并非满负荷通信，存在通信间歇，故较之前二者能达到较好的节能效果.

图6 平均能耗Fig.6 Average energy consumption

3 结语

本文对RSU与车辆之间通信传输的最大价值问题进行了研究，通过把动态问题静态化，给出了线性规划描述，通过圣诞老人问题对其进行规约，证明了这个问题是NPC的，通过给出PTAS静态算法MTVA-G，确定了R2V最大通信价值的1+ε近似算法，并将算法的结果作为实际动态场景算法的上界，在动态化的场景中，分别模拟了时间复杂度较低的FCFS算法和具备退避策略的启发式算法WFCS，结果表明WFCS算法不仅保证了QoS，在综合表现上性能更优.

[1] Hammad A A, Badawy G H, Todd T D, et al.Traffic scheduling for energy sustainable vehicular infrastructure[C]//IEEE.IEEE GLOBECOM 2010.Miami: GLOBECOM, 2010: 1-6.

[2] Liu Y, Xiong N, Zhao Y, et al.Multi-layer clustering routing algorithm for wireless vehicular sensor networks[J].IET Communications,2010,4(7):810-816.

[3] Bali R S, Kumar N, Rodrigues J J P C.An efficient energy-aware predictive clustering approach for vehicular ad hoc networks [J].International Journal of Communication Systems, 2015, 36 (6): 154-161.

[4] Kumar W, Bhaacharya S, Qazi B R, et al.An energy efficient double cluster head routing scheme for motorway vehicular networks[C]//IEEE.2012 IEEE International Conference on Communications.Ottawa: SmartGridComm, 2012: 141-146.

[5] Wang C H, Yu G J.Power control and channel assignment mechanisms for cluster-based multichannel vehicular ad-hoc networks[C]//IEEE.2013 12th IEEE International Conference on Trust.Melbourne: Security and Privacy in Computing and Communications, 2013: 1762-1767.

[6] Corporation H P.An energy-efficient broadcast mac protocol for hybrid vehicular networks[J].International Journal of Distributed Sensor Networks, 2013, 12(3): 188-192.

[7] Yang C, Fu Y, Zhang Y, et al.Energy-efficient hybrid spectrum access scheme in cognitive vehicular ad hoc networks[J].IEEE Communications Letters, 2013, 17(2): 329-332.

[8] Rodoplu V, Meng T H.Minimum energy mobile wireless networks[J].IEEE Journal on Selected Areas in Communications, 1999, 17(8): 1333-1344.

[9] Rawat D B, Popescu D C, Yan G, et al.Enhancing VANET performance by joint adaptation of transmission power and contention window size[J].IEEE Transactions on Parallel &Distributed Systems, 2011, 22(9): 1528-1535.

[10] Hafeez K A, Zhao L, Mark J W, et al.Distributed multichannel and mobility-aware cluster-based mac protocol for vehicular ad hoc networks[J].IEEE Transactions on Vehicular Technology, 2013, 62(8): 3886-3902.

[11] Hammad A A, Todd T D, Karakostas G.Variable bit rate transmission schedule generation in green vehicular roadside units[J].IEEE Transactions on Vehicular Technology, 2015, 65(3): 1590-1604.

[12] 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.

[13] Alcaraz J J, Vales-Alonso J, Garcia-Haro J.Control-based scheduling with QoS support for vehicle to infrastructure communications [J].IEEE Wireless Communications, 2009, 16(6): 32-39.

[14] Bansal N, Sviridenko M.The Santa Claus problem [C]// ACM.Proceedings of the Annual Acm Symposium on Theory of Computing.New York: Association for Computing Machinery, 2006: 31-40.

Time-Slot Based Transmission Value Maximization of Uplink in R2V Network

ZhuRongbo,WangHongbo,ZhangHao,XuWengang

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

This paper focused on the transmission value maximization problem of uplink between RSU to Vehicles (R2V).Through division of the RSU time-slot and reduction from Santa Claus Problem, the problem was proved to be NP-Complete problem, and this problem was formulated by linear programming method.Both the static and dynamic scenarios were simulated, for static scenario, the Polynomial-Time Approximate Scheme (PTAS) was proposed which can achieve 1+εperformance ratio.For dynamic scenario, the First Come First Serve (FCFS) algorithm, and the heuristic algorithm Weight Fixed Communication Scheme (WFCS) based on speed,weight and data transmission rate were simulated respectively.The results showed that the WFCS algorithm can meet the needs of network transmission value maximization better.Both improved maximum transmission value and guaranteed the network QoS.

VANETs；road side unit；RSU to Vehicles；maximum transmission value；linear programming

2016-12-07

朱容波(1978-)，男，教授，博士，研究方向：无线网络，E-mail: rbzhu@mail.scuec.edu.cn

国家自然科学基金资助项目(61272497)；国家民委中青年英才培养计划项目；中南民族大学研究生创新基金资助项目(2016sycxjj203)

TP393.1

A

1672-4321(2017)01-0096-06