车载自组织网络环境下基于软件定义网络的数据协作调度算法

吴 怡，马良义，魏允峰，徐哲鑫

(福建师范大学 光电与信息工程学院，福州 350007)

(*通信作者电子邮箱wuyi@fjnu.edu.cn)

车载自组织网络环境下基于软件定义网络的数据协作调度算法

吴 怡*，马良义，魏允峰，徐哲鑫

(福建师范大学 光电与信息工程学院，福州 350007)

(*通信作者电子邮箱wuyi@fjnu.edu.cn)

针对车载自组织网络(VANET)中路侧单元(RSU)应答车辆请求效率低下的问题，提出基于软件定义网络(SDN)的数据调度算法SDDS。首先，依据车辆状态信息生成策略冲突图，并求解其最大权重独立集，实现单个周期内被应答请求数目最大化；其次，通过分析数据在车辆节点中的冗余度对系统服务能力的影响确定最优参数，设计了一种基于地理位置的协助车辆挑选机制；最后，分析跨区切换车辆的特点和影响多RSU协作的因素，提出一种基于冲突避免的多RSU协作机制；此外，提出了新的评价指标——服务效能来评价系统的整体服务质量。仿真实验中，相比请求数目优先算法(MRF)和协作数据分发算法(CDD)，SDDS的服务效能最高增幅达到15%和20%。仿真结果表明，SDDS能显著提高调度系统的服务效率和质量。

数据调度；车载自组织网络；软件定义网络；协作车辆；多路侧单元协作

0 引言

车载自组织网络(Vehicular Ad Hoc Network, VANET)是智能交通系统(Intelligent Transport System, ITS)的重要组成部分，受到了学术界和工业界的广泛关注[1-2]。随着VANET中的新兴应用越来越多，车和车之间、车和路侧单元(Road Side Unit, RSU)之间共享和传输的消息也越来越多样化，如：路况信息、天气状况、基础设施分布情况等[3]。当面对众多车辆的多种请求时，RSU迫于信道资源限制，难以为所有发出请求的车辆提供及时、有效的服务，因此对于数据调度算法的研究引起了学术界的广泛关注。

为提高基站的服务效率和服务质量，数据调度算法成为研究的热点之一。MRF(Most Requests First)[4]每次优先服务请求数目较多的请求，导致其所服务请求大多为出现频率较高的请求，请求频率不高的请求就很难被服务到。文献[5]提出了一个多信道的数据调度方法，有效地降低了服务时延，提高了带宽的利用率。Zhang等[6]提出了一种两步调度方案D*S/N(deadline, data size and pending requests)来均衡下载和上传请求，方案中RSU包含下载队列和更新队列，两个队列分配不同的带宽，并且有自己的优先分配方案。该方案在选取待服务请求时引入了参数截止时间和数据包大小，优先服务将要脱离服务范围车辆发出的请求和所请求数据包较小的请求，提高了出现频率低的请求被服务到的概率；但是当上传请求中所请求数据已经存在于基站并且已经被下载过，则继续对其进行服务会产生重复性存储，造成资源浪费和降低系统的运作效率。针对该问题文献[7]提出了一个联合调度方案来选择最合适的请求。在该方案中，RSU中同样包含下载和更新队列。该方案首先计算出两个队列中每个请求的权重，然后从两个队列中选择权重最大的两个请求，最后再选择权重大的一个进行服务。如果上传队列中所选请求的权重大于下载队列，则检查该上传请求所请求数据是否已被下载过，如果没有下载过则提供服务，否则不提供服务。为保证安全数据的时效性，文献[8]中将请求分为安全性数据和非安全性数据，且安全性优先级大于非安全性。安全性请求的优先级依据脱离时间、请求车辆数和数据包大小来确定，而非安全性请求的优先级依据请求个数、脱离时间和数据包大小来确定，优先处理数据包较小的。该方法保证了安全数据的优先处理并且实现了非安全数据被服务量的最大化。以上这些方法都是以RSU多播为基础参考请求的请求数目、紧急情况、数据包大小等参数进行I2V(Infrastructure-to-Vehicle)服务，而基站受限于信道资源，在单个周期的服务能力有限，致使总体服务能力并不是很理想。本文将参考以上文献所述参数并侧重于结合I2V和V2V(Vehicle-to-Vehicle)两种服务方式来寻求一种更为有效的数据调度系统。文献[9]借助车辆的转发功能提出了一种分布式的紧急消息传播协议，提高了紧急消息的投递率并降低了传递时延。文献[10]提出了一种基于软件定义网络(Software Defined Network, SDN)的数据调度方法CDD(Cooperative Data Dissemination)。该方法依靠SDN的集中控制思想控制系统中所有车辆和RSU的转发行为，在理论上寻找到了一个全局最优的数据调度方案，在整体性能上取得了进一步的提升。该方法中的转发策略都是基于当前车辆状态所制成，由于车辆的高速移动性，部分车辆会互相脱离通信范围导致转发策略不能完全被执行，即部分策略会在当前周期内失效。针对此问题本文提出了策略失效检测机制以保证转发策略的可靠性。此外，由于基站每次只能服务一种请求，所以数据在车辆中分布很稀疏，而且还存在数据集中在小范围区域的车辆中的情况，当距离较远且超过通信范围的车辆请求这些数据时，虽然这些数据存在于车辆中，但是因为距离问题，这些车辆就不能被V2V方式服务到，这在一定程度上限制了车辆被服务的概率。本文针对这个问题提出了协助转发车辆的概念，利用协助转发车辆增大其他车辆被服务的概率。

由于车辆的高速移动性以及RSU通信半径有限，车辆在RSU通信范围内的时间很短，使得单个RSU很难完成对每一个请求的服务，尤其是当车流量比较大时，就会导致很多车辆还未被服务就已经脱离了RSU的服务范围。为解决单个RSU的服务瓶颈，一些专家和学者提出了一些多RSU协作的方案。文献[7]提出DSIN(Deadline Size Inverse Number of pending requests)机制，在该机制中负载较重的RSU将部分请求转移给预测车辆运动方向上负载较轻的RSU，在一定程度上平衡了多个RSU之间的负载情况，但是车辆在远处的RSU范围内重新接受服务会严重影响请求的时效性。文献[8]中针对单个RSU负载过重的情况也作出了相应处理，将部分请求转发至下一个RSU并提升其被服务的优先级，对于请求数据量过大致使在一个RSU内不能完成传输的请求作删除处理。该方法在一定程度上降低了请求被服务的延迟，减轻了单个RSU特殊时期的负载。在另外一种机制MPO(Motion Prediction Optimization)中[11]，基站依据车辆的运动特征预判车辆的运动轨迹并发送相关请求信息给预期方向上的RSU，减轻了单个RSU在特殊时期的负载并提高了整体的带宽利用率，但是与DSIN类似，均难以保证请求信息的时效性。文献[12]也提出了一些基于车辆运动方向的多RSU负载均衡的方法。文献[13]中提出了一种面向高速公路场景的无间隙协助下载方法(Non-Intermittent Cooperative Downloading Method, NICDM)，目标车辆未完成的下载任务依据车速、任务大小以及通信盲区(Dark Area, DA)距离等信息进行分解，并分别委托行驶方向上的最近2个接入点(Access Point, AP)协助下载。一组经过优化选择的协助车辆从AP获得数据，并在DA转交给相遇的目标车辆。但是对于车辆稀疏的场景，寻找协助车辆比较困难，而且协助车辆被占用时间较长，影响协助车辆自身的请求状态。因此本文提出一种基于SDN的多RSU协作机制，以达到在不影响车辆自身请求行为的情况下降低请求被服务时延的目的。

本文将以提升车辆请求被服务率、降低请求被服务时延为目标，提出一种软件定义数据调度(Software Defined Data Scheduling)算法，该算法基于SDN设计；将车辆状态信息生成转发策略集，利用转发策略的有效性检测机制以确保转发策略的可靠性；根据冲突条件将转发策略集生成策略冲突图，引入最大独立集生成算法，通过最大独立集提取，以确保所选集合为最大策略集且所选策略集之间互相不冲突。基于地理位置合理选择协助转发车辆，并下发信息以增加车辆间的信息容量，提高车辆间互相被服务的概率；基于SDN架构提出了新的RSU协作方法，将跨区切换车辆的请求转发至邻近RSU，并挑选合适的协助服务车辆以解决RSU边缘服务问题，降低跨区切换车辆请求的服务时延，提高系统的服务率;提出新的性能评价指标——服务效能，以综合评价系统的服务率和服务时延。仿真结果表明所提机制在周期平均服务能力、服务效能及车辆间服务能力上都有明显的提高。

1 系统场景及模型

本文提出的数据调度方法的系统模型如图1所示。系统场景与文献[10]相似，所设定道路为单向三车道的公路，车辆由右侧进入，多个RSU之间通过电缆连接起来，RSU的服务区覆盖为无缝覆盖。图中请求队列中普通字母表示车辆发出且未被服务到的请求，有下划线的字母表示车辆中已存储的请求数据。车辆发出的请求可以由RSU对其进行服务，相应的转发策略为I2V 转发策略；也可以由已存储请求车辆所需信息的车辆对其服务，相应的转发策略为V2V转发策略。例如：IdV4表示基站发送数据d给车辆V4，V5cV6表示车辆V5发送数据c给车辆V6。基于IEEE1609.4无线通信标准[14-15]，本文将信道划分为控制信道、V2I和V2V三个信道，控制信道用于传输控制信息，V2I信道用于发出请求和传输数据，V2V信道仅用于数据传输，且设定单位时间内车辆只能工作在一个信道内。I2V策略工作于V2I信道，V2V策略工作于V2V信道。对于车辆发送状态信息时的信道分配，本文采用IEEE 802.11p MAC(Media Access Control)层的DCF(Distributed Coordination Function)机制[16]。

RSU作为其覆盖范围内的网络控制中心，负责依据车辆上传的状态信息为整体作出调度策略，并下放表项给车辆以实现整个系统的高效运行，车辆的转发行为完全依照RSU所下发表项。其中车辆的状态信息包含信息如下：自身标识idi、地理位置坐标(xi,yi)、当前车速Vi、请求队列rqi、已被服务请求队列sqi。其中请求类型ID为车辆中已存储的信息类型。RSU中维护一个信息列表如下：list={(id0,x0,y0,v0,rq0,sq0),(id1,x1,y1,v1,rq1,sq1),…,(idn,xn,yn,vn,rqn,sqn)}。RSU根据车辆地理位置及车辆间通信半径求得每一个节点的邻居节点列表Ni组成邻居节点列表N。

图1 系统模型Fig. 1 System model

2 SDDS算法总体流程

车辆进入RSU的服务范围后，在每个周期的开始阶段向RSU发送其自身的状态信息，并且随机地向RSU发出请求。在该阶段，车辆全部工作在V2I信道，RSU处于侦听状态。设定车辆当前处于路侧单元R的服务范围内，行驶方向上下一个路侧单元为R′。

基于SDN的数据调度算法的总体流程如图2所示，主要分为四部分：1)RSU依据车辆上传的状态信息生成所有可能的转发策略，为提高所生成策略的可靠性，利用策略失效检测机制判断策略是否会失效，删除会失效的策略，得到所有可靠的转发策略；2)根据策略冲突条件生成策略冲突图并通过一种贪婪算法求解出冲突图的最大独立集得到当前周期内的转发策略集Vselected；3)基于地理位置均匀地选出协助转发车辆，生成相应的策略并存入Vselected；4)搜索即将脱离当前R且还有请求未被服务到的车辆，将其请求发给下一个R′，R′寻找合适的服务策略并反馈R。

图2 SDDS总体流程Fig. 2 Flow chart of SDDS

3 SDDS各环节设计

3.1 生成策略集

与CDD生成单跳转发策略集类似，SDDS遍历所有节点的请求信息及邻居节点列表信息，生成所有可行的转发策略。如前所述，由于车辆的高速移动性，会导致部分策略在当前周期失效，因此本文提出一种失效检测机制以提高所选策略的可靠性，对于生成的每一个策略检测其在当前周期内是否会失效，若会失效则作删除处理。

(1)

(2)

其中θ为车辆速度与X轴的夹角。若车辆节点下一秒位置满足式(3)，则表明该车在下一秒内将会脱离RSU的范围，则该I2V即为失效策略。

(3)

(4)

删除所有会失效的策略，得到策略集TS。

3.2 构造冲突图求解最大独立集

本文沿用文献[10]的方法将策略集TS中每一个策略都视为一个节点并根据五种策略冲突条件生成策略冲突图G={V,E}，V表示策略节点集，E表示连接两个节点的边，如图3所示。

图3 策略冲突图示例Fig. 3 Example of policy conflict graph

求解策略冲突图的最大独立集步骤如下：

1)计算每个策略节点的权重wi为：

(5)

其中：Li为节点的度数，即在策略冲突图与其相连节点的个数；t为车辆脱离RSU范围所需时间；α取0.04[10,17]。

2)挑选出权重最大的策略节点TSmax，将策略TSmax放入集合Vselected，删除与TSmax相连的策略节点。

3)判断G是否为空，若不为空则返回第2)步。

集合Vselected中策略即为当前周期所要执行的策略集。由集合Vselected可得在当前周期内基站组播数据di、接收基站信息车辆集VRI、V2V策略中发送车辆集VS以及接收车辆集VR。

3.3 选取协助转发车辆

如前所述车辆中所存储信息分布不均匀限制了车辆被服务的概率，为解决这个问题，本文提出了一种基于地理位置的协助车辆选取方法。该方法基于车辆地理位置均匀地选取协助转发车辆，为不影响协助转发车辆的自身请求状态，所选取车辆都是在当前周期处于空闲状态的车辆，即协助转发车辆不存在于前面所挑选的V2V策略，并将基站在本周期组播的数据发送给它们，实现该数据在RSU范围内的全覆盖均匀分布，以此提高在以后周期内该请求被服务的概率。

选择协助转发车辆的方法如下：首先从道路一端的起点开始等距离地选取n个坐标作为协助转发点{(xnod0,ynod0),(xnod1,ynod1),…,(xnodn,ynodn)}，如图4所示。协助转发点个数n的计算公式如下：

n=2·Dr/Dv

(6)

其中:Dr为RSU通信半径，Dv为车辆通信半径。

Vhi∉VS

(7)

图4 协助转发车辆示例Fig. 4 Example of cooperative relay vehicle

3.4 多RSU协作机制

如引言所述，由于单个RSU服务能力有限，导致一些即将驶出RSU范围的车辆还有请求未被服务，针对该问题本文提出了一种基于SDN架构的多RSU协作机制，机制中R将即将脱离车辆的请求信息发给下一个R′，R′负责寻找合适的车辆服务这些请求。具体步骤如下：

步骤1 识别即将脱离RSU服务范围的车辆(下称跨区切换车辆)，并从中找出还有被服务潜力的车辆集Vt，Vt中车辆满足以下两个条件：1)仍有请求未被服务到；2)其邻居节点中没有在当前周期要发送数据的车辆，该条件保证了该车辆接收信息不会受到其他链路的干扰。

步骤2 将Vt中车辆的状态信息及当前周期的决策信息转发给其行驶方向上的R′，决策信息包含di、VS和VR中车辆的状态信息。R′在其服务范围内寻找合适的车辆Vni并制成V2V策略表项下发相关车辆为其服务。R′寻找合车辆的方法如下：对于Vt中的Vti，R′在其服务范围内寻找出满足以下条件的车辆集Vni：

1)与Vti为邻居节点，即Vni满足式(8),确保Vni在Vti的通信范围内。其中L(A，B)表示A，B两点之间的距离。

L(Vti,Vni)

(8)

(9)

(10)

(11)

3)Vni满足式(12)，即Vni中已存储Vti所需数据dj，其中sqni表示车辆Vni中已存储的信息列表。

dj∈sqni

(12)

4)Vni邻居节点在当前周期内不存在于V2V策略中的接收者，式(13)中Nni表示车辆Vni的邻居节点列表，该式确保了Vni作为发送车辆不会影响其邻居节点的接收转状态。

(13)

因为跨区切换车辆都即将驶出边界，因此跨区切换车辆距离边界的距离很近，跨区切换车辆之间的间距也相对很近，而多个V2V转发链路同时工作在V2V信道会相互影响，所以一旦找到可以为Vti服务的车辆后就终止搜索。

步骤4R将Vselected中的策略制成表项下发车辆。至此，发送车辆和接收车辆都接收到了指令，可以开始进行转发。如图1中V6即将驶出RSU1，但是其还有未被服务到的请求c，则RSU1将V6的状态信息转发给RSU2，RSU2在其服务范围内找到合适的车辆V5并生成转发策略V5cV6下发给车辆V5和V6。

4 性能仿真与分析

4.1 仿真场景及参数设置

为了验证所提算法的有效性，在Matlab中进行了仿真实验，场景设置为三条单向的马路，RSU中数据库模型及请求分布模型设置同文献[10]，表1为SDDS机制的性能仿真参数设计。

表1 仿真参数Tab. 1 Simulation parameters

为模拟不同车辆密度下的系统性能，本文设定了五种交通环境的仿真参数如表2所示，随着场景编号的增大，车辆密度逐渐提升，车辆密度由车速确定，车辆间最小车距为车辆2 s行驶的距离。为分析SDDS机制性能，本文还对比了MRF和CDD机制性能，三种算法仿真的场景参数相同，所统计各项性能数据为一个RSU范围内的数据。

表2 不同交通场景下的仿真参数Tab. 2 Simulation statistics under different traffic scenarios

4.2 仿真结果分析

系统平均增益是RSU在每个周期内服务到的请求个数的平均值，既包括I2V所服务的请求个数，也包括V2V所服务到的请求个数，它反映了单个周期内系统服务车辆的能力大小。图5所示为在不同场景下三种算法的系统增益曲线，可以看出，三种算法的平均服务车辆数随着车辆密度的逐渐增大都逐渐增多。在各个场景中，SDDS平均服务数最多，CDD次之，MRF最少。原因在于MRF的服务方式只有I2V方式，而CDD和SDDS还引入了V2V服务方式，并且随着车辆中所存储信息的积累，V2V服务数所占比重也越来越大，刺激了总服务数的增长，所以MRF的平均服务个数最少。SDDS在CDD基础之上又添加了协助转发车辆，提高了车辆中的信息含量，增大了车辆之间互相服务的概率，众多车辆同时运作进行服务大大提高了系统的服务能力；除此之外SDDS还引入了多RSU协助机制，使得部分跨区切换的车辆也能受到服务，也增加了被服务请求的个数，所以SDDS的周期平均服务个数高于CDD算法。

图5 不同场景下系统平均增益比较Fig. 5 Average gain of system under different scenarios

为了比较系统的整体增益，本文提出了服务效能S这一性能指标，用以反映系统服务请求的整体性能，该性能指标基于服务率Ri和平均服务延迟Di这两项性能指标，计算公式如下：

(14)

服务率和平均时延的性能曲线分别如图6和图7所示。从图6可以看出在不同的场景下MRF的服务率最低，CDD的服务率有明显提升，而CDD的服务率最高。这是因为单个周期内车辆所发出的请求个数是一样的，所以单个周期内平均服务请求数目大的算法会有较高的服务率，故而SDDS的服务率最高。从图7可以看出随着车辆密度的增加，三种算法的时延都有明显增加，且在各个场景中MRF时延最短，SDDS次之，CDD最长。MRF时延低于SDDS的原因在于:由于MRF服务基于单个周期内请求类型的数目，而每个周期中请求次数最多的集中为出现频率高的请求，所以其只服务到了出现概率大的信息;又因为其服务到的信息数目相对最少(详见图5),而平均服务时延是由已被服务的请求的时延统计而来，故而服务请求数目较少且服务类型为高频请求的MRF机制的时延较低。相对于MRF，SDDS单个周期内服务的请求数目多且不局限于出现频率高的请求，即SDDS比MRF服务了更多的请求类型，服务了更多的时延较长的请求，故而SDDS的平均时延高于MRF。SDDS的平均时延低于CDD的原因在于SDDS提升了车辆中的信息含量，强化了V2V服务方式，使得SDDS可以在单个周期内通过V2V方式服务到更多的车辆，从而在总体上降低了车辆等待的时间。但综合考虑两个指标，即从服务效能上看，性能曲线如图8所示，随着场景编号的增大，三条曲线都呈下降趋势。这意味着随着车辆密度越大，服务效能越低，但是所提机制在各个场景下的服务效能均优于其他两种机制，并且随着车辆密度的增加，其下降的幅度也相对比较平缓。SDDS服务效能高于MRF的原因在于SDDS有着最高的服务率和较低的服务时延，服务率上的优势弥补了平均服务时延上的欠缺并在整体性能上超越了MRF。MRF虽然在车辆密度小的场景下有较好的服务效能，但是随着密度增大，其下降的幅度是最大的，并且在场景5中其服务效能是最差的，这归咎于其较低的服务率。CDD整体下降幅度不大，但是其服务效能远小于SDDS，这是因为其在服务率和服务时延上都不具有优势，故而服务效能最差。所以本文所提出机制的整体服务性能是最优的。

图6 不同场景下服务率比较Fig. 6 Service ratio under different scenarios

图7 不同场景下服务延迟比较Fig. 7 Service delay under different scenarios

在SDDS中，请求可以通过I2V和V2V两种方式被服务到，为了更清晰地查看这两种服务方式所占比重，本文还分别统计了这两种服务方式各自的服务数目。其中：分布式产能为平均每个周期内以V2V方式服务到的请求数，反映了系统的分布式服务能力；I2V广播产能为RSU平均每个周期内以I2V方式服务到的车辆数，反映了系统中基站广播服务能力。

图9为在不同场景下CDD和SDDS两种算法的车辆服务产能曲线，横坐标还是为场景编号，纵坐标为车辆服务产能，即通过V2V方式服务到的平均请求个数。因为MRF只有I2V服务模式，所以图中无MRF参与比较。由图可以看出SDDS算法的车辆服务产能明显高于CDD，原因在于SDDS机制中有借助协助转发车辆的转发能力，进一步增加了以后周期内车辆间互相被服务的概率，并且增加了RSU协作机制，最终的协作方式也是通过V2V方式来完成服务的，所以SDDS中充分发挥了车辆间互相服务的潜力，在车辆间服务产能上表现更为出色。

图8 不同场景下服务效能比较Fig. 8 Service efficiency under different scenarios

图9 不同场景下分布式产能比较Fig. 9 Distributed productivity under different scenarios

图10所示为不同场景下I2V广播产能的曲线，可以看出，随着车辆密度的增大，三种算法的I2V服务产能都呈现逐渐上升的趋势。因为MRF每个周期都选择请求数目最多的请求进行服务，所以其基站服务能力最强；而CDD和SDDS在选择I2V和V2V时对两种策略进行了权衡处理，更倾向寻求整体最优方案，所以会在I2V服务上有所欠缺。CDD该性能高于SDDS的原因在于SDDS增加了协助转发车辆，增强了车辆之间的互相服务能力，使得车辆被车辆服务的概率大于基站对车辆的服务概率，从而导致了I2V的减少。

5 结语

针对RSU服务范围内的数据调度问题，提出了基于SDN的数据调度算法SDDS，在CDD的基础之上提出了转发策略失效监测算法，监测在当前周期会失效的策略并删除，保障了转发策略的可靠性；将转发策略生成策略冲突图并引入最大独立集提取算法，求得策略集的最大独立集，实现了转发策略集的最大化；基于地理位置均匀地选取协助转发车辆，将基站广播信息发送到更多的车辆中，提高了车辆间的信息容量，进而提高了车辆被车辆服务的概率；将跨区切换车辆的未被服务信息发送给邻居RSU，邻居RSU选取合适车辆为其服务，降低了跨区切换车辆请求的服务时延，改善了系统的服务效能。最后仿真表明，SDDS在不同车辆密度场景下的周期平均服务能力、服务效能、车辆间服务能力上均优于CDD机制与MRF机制；SDDS在基站服务产能上不及MRF和CDD，但SDDS在V2V服务产能上的优势可以弥补基站服务性能的不足。本文的研究工作是假定RSU包含所有数据内容，但RSU缓存空间有限，大多数据内容还需要从数据中心获取，导致网络间重复性流量。因此，RSU如何在缓存空间有限的情况下保证一定的服务效能并减少网络间流量，将是下一步的研究内容。

图10 不同场景下I2V广播产能比较Fig. 10 I2V broadcast productivity under different scenarios

References)

[1] WANG H, LIU R P, NI W, et al. VANET modeling and clustering design under practical traffic, channel and mobility conditions [J]. IEEE Transactions on Communications, 2015, 63(3): 870-881.

[2] AKHTAR N, ERGEN S C, OZKASAP O. Vehicle mobility and communication channel models for realistic and efficient highway VANET simulation [J]. IEEE Transactions on Vehicular Technology, 2015, 64(1): 248-262.

[3] NEGI S, SINGH S, GOEL S K, et al. Data scheduling in VANET: a survey [J]. International Journal of Computer Science Trends and Technology, 2016, 4(2): 25-31.

[4] ALI G G M N, CHAN E. Co-operative data access in multiple road side units (RSUs)-based Vehicular Ad Hoc Networks (VANETs) [C]// ATNAC 2011: Proceedings of the 2011 Australasian Telecommunication Networks and Applications Conference. Piscataway, NJ: IEEE, 2011: 1-6.

[5] LIU K, LEE V C S, LEUNG K R P H. Data scheduling for multi-item requests in multi-channel on-demand broadcast environments [C]// MobiDE ’08: Proceedings of the Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access. New York: ACM, 2008: 47-54.

[6] ZHANG Y, ZHAO J, CAO G. Service scheduling of vehicle-roadside data access [J]. Mobile Networks and Applications, 2010, 15(1): 83-96.

[7] ALI G G M N, CHAN E, LI W. Two-step joint scheduling scheme for road side units (RSUs)-based vehicular Ad Hoc networks (VANETs) [C]// DASFAA’11: Proceedings of the 16th International Conference on Database Systems for Advanced Applications. Berlin: Springer-Verlag, 2011: 453-464.

[8] BOK K, HONG S, LIM J, et al. A multiple RSU scheduling for V2I-based data services [C]// Proceedings of the 2016 International Conference on Big Data and Smart Computing. Washington, DC: IEEE Computer Society, 2016: 163-168.

[9] ZEMOURI S, DJAHEL S, MURPHY J. A fast, reliable and lightweight distributed dissemination protocol for safety messages in urban vehicular networks [J]. Ad Hoc Networks, 2015, 27: 26-43.

[10] LIU K, NG J K Y, LEE V C S, et al. Cooperative data scheduling in hybrid vehicular Ad Hoc networks: VANET as a software defined network [J]. IEEE/ACM Transactions on Networking, 2016, 24(3): 1759-1773.

[11] GUI Y, CHAN E, A motion prediction based cooperative scheduling scheme for vehicle-roadside data access [C]// Proceedings of the 2011 2nd International Conference on Networking and Information Technology. Singapore: IACSIT Press, 2011: 195-204.

[12] GUI Y, CHAN E. Data scheduling for multi-item requests in vehicle-roadside data access with motion prediction based workload transfer [C]// WAINA ’12: Proceedings of the 2012 26th International Conference on Advanced Information Networking and Applications Workshops. Washington, DC: IEEE Computer Society, 2012: 569-574.

[13] 谢永,吴黎兵,何炎祥,等.无间隙的车联网协助下载方法[J].通信学报,2016,37(1):180-190. (XIE Y, WU L B, HE Y X, et al. Non-intermittent cooperative downloading approach for VANET [J]. Journal on Communications, 2016, 37(1): 180-190.)

[14] 张书侨.DSRC无线通信模式的原理及应用[J].数字通信世界,2014(9):43-45. (ZHANG S Q. The principle and application of DSRC wireless communication mode [J]. Digital Communication World, 2014(9): 43-45.)

[15] MORGAN Y L. Notes on DSRC & WAVE standards suite: Its architecture, design, and characteristics [J]. IEEE Communications Surveys & Tutorials, 2010, 12(4): 504-518.

[16] WU Q, ZHENG J. Performance modeling and analysis of IEEE 802.11 DCF based fair channel access for vehicle-to-roadside communication in a non-saturated state [J]. Wireless Networks, 2015, 21(1): 1-11.

[17] BOURGIN G, BOURRICAUD F, GERNET L, et al. Review: human behavior and the principle of least effort (an introduction to human ecology) by George Ripf Kingsley [J]. Lannée Sociologique, 1948-1949, 3(3): 157-158.

This work is partially supported by the National Natural Science Foundation of China (61571128), the Research Fund for the Doctoral Program of Higher Education of China (20133503120003), the Key Projects of Science and Technology Plan for Industy of the Science and Technology Department of Fujian Province (2014H0019).

WUYi, born in 1970, Ph. D., professor. Her research interests include wireless communication network, computer network.

MALiangyi, born in 1993, M. S. candidate. His research interests include mobile communication, computer network.

WEIYunfeng, born in 1988, M. S. candidate. His research interests include photo-communication, computer network.

XUZhexin, born in 1985, Ph. D., associate professor.His research interests include wireless communication network, smart home.

DataschedulingalgorithmbasedonsoftwaredefinednetworkforvehicularAdHocnetwork

WU Yi*, MA Liangyi, WEI Yunfeng, XU Zhexin

(CollegeofPhotonicandElectronicEngineering,FujianNormalUniversity,FuzhouFujian350007,China)

Focusing on the issue that the Road Side Unit (RSU) has inefficient response to the request of the vehicles in Vehicular Ad Hoc Network (VANET), a data scheduling algorithm based on Software Defined Network (SDN) architecture, namely SDDS, was proposed. Firstly, a graph of conflicting policies was generated based on status information of vehicles, and a maximum weighted independent set of the graph was solved to maximize the number of satisfied requests in current cycle. Secondly, the redundancy of data in vehicles was analyzed to figure out the optimum parameter, and a selection mechanism for collaborative vehicles was designed based on geographical position. Finally, the characteristics of handover vehicles and some factors that would affect the multi-RSU cooperation were analyzed, and a multi-RSU cooperation mechanism was put forward based on collision avoidance. In addition, a new evaluation indicator, service efficiency, was proposed to estimate the overall quality of service. Simulation results showed that compared with Most Requests First (MRF) and Cooperative Data Dissemination (CDD) algorithms, the service efficiency of SDDS algorithm was increased up to 15% and 20% respectively. The simulation results prove that SDDS algorithm can observably improve the sevice eficiency and quality of scheduling system.

data scheduling; Vehicular Ad Hoc NETwork (VANET); Software Defined Network (SDN); collaborative vehicle; multiple Road Side Unit (multi-RSU) cooperation

TN929.52

A

2017- 01- 13;

2017- 03- 03。

国家自然科学基金资助项目(61571128)；教育部高等学校博士学科点专项科研基金(新教师类)资助项目(20133503120003)；福建省科技厅工业科技计划重点项目(2014H0019)。

吴怡(1970—)，女，辽宁葫芦岛人，教授，博士，主要研究方向：无线通信网络、计算机网络； 马良义(1993—)，男，河南濮阳人，硕士研究生，主要研究方向：移动通信、计算机网络； 魏允峰(1988—)，男，安徽亳州人，硕士研究生，主要研究方向：光通信、计算机网络； 徐哲鑫(1985—)，男，福建福州人，副教授，博士，主要研究方向：无线通信网络、智能家居。

1001- 9081(2017)08- 2139- 06

10.11772/j.issn.1001- 9081.2017.08.2139