软件学报  2014, Vol. 25 Issue (10): 2362-2372   PDF    
车联网中传输调度与资源分配相结合的内容下载
陈丽1,2, 李治军2, 姜守旭2    
1. 嘉兴学院 数理与信息工程学院, 浙江 嘉兴 314001;
2. 哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001
摘要:车联网信道资源稀缺及车载节点间的间歇性短暂链接,给车载节点通过无线接入点(AP)接入互联网进行内容下载带来了巨大挑战.AP覆盖范围内的资源分配与Internet链接空洞区域的传输调度相互依赖,共同影响其下载性能,而现有文献往往将二者孤立开来分别进行研究.为了提高下载性能,将二者作为一个整体,从全局优化的角度研究内容下载的效率问题,并将其形式化为下载数据量最大的结合非冲突调度的资源分配问题.但是,在证明该问题是NP-难的基础上,提出结合链接空洞区域的传输调度的资源分配近似算法(JAS)来解决该问题.该算法将整个链接空洞区域节点间链接的时空变化模型化为拓扑图序列,并基于此构建其传输冲突图序列,在AP通信覆盖区域基于图序列计算优化的资源分配节点集进行资源分配,以期达到扩展AP通信范围、填补Internet链接空洞的目的.模拟实验结果表明,JAS算法与现有方法相比显著提高了文件下载量及传输的成功率.此外,还对影响内容下载性能的相关因素进行了分析.
关键词车联网     车载ad hoc网络     无线网络接入点     车间通信     内容下载    
Content Downloading-Oriented Resource Allocation Joint Scheduling in Drive-Thru Networks
CHEN Li1,2, LI Zhi-Jun2, JIANG Shou-Xu2    
1. College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing 314001, China;
2. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
Corresponding author: JIANG Shou-Xu, E-mail: jsx@hit.edu.cn; chenli20040415@hit.edu.cn
Abstract: Vehicular content downloading via open WiFi access points (APs) can be challenging due to sparse AP deployment with bounded communication range and the rapid movement of traveling vehicles. For drive-thru networks, resource allocation and scheduling closely interrelate to and interact with each other, collectively affecting the performance of content downloading. However, none of the previous work has tackled this problem as a whole. This paper discusses joint resource allocation and scheduling problem for efficiently content downloading considering channel contention and scarce AP resource utilized effectively. It formalizes optimization selection problem of node set to maximize the total quantity of data downloaded, and proves that it is NP-hard. Further, it presents a solution with a joint resource allocation and scheduling approximate algorithm (JAS). Theoretical analysis and simulation results both verify that the presented implementation achieves higher throughput and delivery ratio than the existing algorithms.
Key words: drive-thru Internet     vehicular ad hoc network (VANET)     access points (APs)     vehicle-to-vehicle (V2V)     content downloading    

近年来,随着无线通信技术的快速发展以及无处不在的信息需求,移动接入互联网已成为人们日常生活中不可或缺的一部分[1].在公路网中,车辆间及车辆与固定接入点之间相互通信,组成一个自组织的、部署方便、费用低廉、结构开放的通信网络——车载Ad hoc网络(简称VANET).VANET除了在智能交通方面的应用以外,如事故告警、辅助驾驶、道路交通信息查询、乘客间通信等,它还可以作为末端网接入Internet,为车载用户提供数据下载以满足其通信需求.车联网(drive-thru Internet)[2, 3]就是配备无线通信设备(如DSRC[4])的车辆在移动过程中通过路边的无线接入点(access point,简称AP)接入Internet,下载所需数据及共享资讯的另一VANET应用场景.在车辆移动过程中,应用VANET技术可以实现车辆间及车辆与路边Internet接入点间的通信.随着网络信息技术的快速发展,车载用户对Internet通信需求日益迫切,如查询最新的天气、新闻、体育、娱乐、交通及股票信息及在线视频等[4, 5].车联网中的内容下载是近年来迅速兴起的一个新兴研究领域.车载节点接入互联网,从而获取多媒体娱乐、资讯信息等,如何提高下载效率已成为车载Ad hoc网络中一个非常重要而又亟待解决的研究问题.

车载用户可以通过多种方式(如3G,4G或WiFi等)接入Internet.目前,普遍采用车载宽带无线接入技术(wireless fidelity,简称WiFi,基于IEEE 802.11p标准的无线局域网)来进行车联网数据传输的研究.其主要原因是3G,4G网络的使用费用高昂,相对于高昂费用,其通信性能并不理想.如实际的GSM与GPRS网络也没有做到普适覆盖(对于欧洲与美国这样的发达地区而言),而且在不远的将来也达不到[7];其次,对于大多数车联网应用场景而言,并不需要普适接入Internet,WiFi网络在有限地理区域内免费提供高性能的Internet链接,它是当前车联网较为理想的选择.

但由于部署AP的成本较高,而且其部署还受AP间无线通信干扰等因素的局限,现有公路网AP的部署一般都较为稀疏;又由于AP通信半径有限,因此车辆节点在移动过程的大部分时间处于Internet链接空洞(即AP通信覆盖范围外的区域,如图 1所示),无法接入Internet,导致车载节点在移动过程中的网络链接是间歇性的[8].随着网络与信息技术的快速发展和日益普及,人们在车辆移动过程中的通信服务需求日益增大,这就使得爆发式增长的车辆接入互联网的通信需求与稀缺Internet链接资源间的矛盾日益激化,势必造成大量用户的网络接入请求无法得到满足.

1 相关工作

对于车联网内容下载应用场景AP覆盖范围内,AP将信道资源分配给哪些节点,在很大程度上影响了后续Internet链接空洞区域节点间的数据传输,进而影响数据的下载量,因而无法有效地利用稀缺的AP信道资源.同时,Internet链接空洞区域的传输调度,一定程度上决定了在此之前AP信道资源分配策略的效用,因此也无法有效地填补链接空洞.然而,已有文献往往将AP覆盖范围内的资源分配与Internet链接空洞区域的传输调度孤立开来分别进行研究,而AP通信覆盖区域内的信道资源分配策略直接影响了链接空洞区域数据包的多源转发,链接空洞区域数据包传输调度依赖于AP覆盖区域内的信道资源分配,资源分配与传输调度二者相互影响、相辅相成,共同作用于车联网中内容下载的性能,对车联网通信服务能力的提升至关重要.然而,已有文献往往将AP覆盖范围内的资源分配与后续Internet链接空洞区域的传输调度孤立起来分别进行研究,仅针对数据传输过程中的传输调度[7,9,10,11]或资源分配[12,13,14,15,16]利用进行研究,如基于传输延迟[9]、公平性[7]、截止时间[5,10]等指标,或基于随机[11]等方式进行传输调度,文献基于定价方式[12]或信道衰减[13, 14, 15]、QoS[16]等指标进行资源分配提高网络通信性能.现有数据传输方法的传输性能并不理想,如传输延迟高、传输成功率低,不能满足车载用户内容下载需求.

为了提高车联网内容下载的性能,即提高传输成功率与系统吞吐量,本文将AP通信覆盖区域信道资源的分配与后续链接空洞区域的传输调度建立关联,将二者相结合作为整体进行考虑,去解决由于链接空洞造成的内容下载服务的有效性问题.为实现其研究目的必须要解决如下两个问题:

(1) 链接空洞区域如何调度,才能使得ad hoc链接的车载节点间更有效地进行内容下载?

(2) 在AP通信覆盖区域,如何分配AP的信道资源,使其能更为有效地利用V2V通信填补链接方法?

本文针对以上两个问题展开研究,将链接空洞区域的传输调度与AP通信覆盖区域的信道资源分配作为一个有机整体进行考虑,从全局优化的角度研究内容下载的效率问题.

本文第2节构建网络及传输冲突模型,将整个链接空洞区域节点间链接的时空变化模型化为拓扑图序列,并基于此构建其传输冲突图序列.第3节对以上提出的两个问题进行形式化定义,将其形式化为下载数据量最大的非冲突节点集序列调度问题及结合非冲突调度的资源分配问题.但是,第3.3节却证明出该问题是NP-难的.因此在第4节,本文提出结合链接空洞区域的传输调度的资源分配近似算法(JAS)来解决该问题.该算法在AP通信覆盖区域基于图序列计算优化的资源分配节点集进行资源分配,通过充分利用AP覆盖区域内的资源分配及链接空洞区域的传输调度进行内容下载,以期达到虚拟扩展AP通信范围,从而填补链接空洞,提高车联网内容下载系统性能的目的.第5节进行模拟实验,实验结果证实本文提出的JAS算法的有效性.与现有方法相比,显著提高了文件下载量及传输的成功率.此外,还对影响内容下载性能指标的因素进行了分析.

2 网络模型及架构

车联网的网络架构图如图 1所示,网中稀疏部署多个AP节点,AP有线接入Internet,图中的灰色区域为AP的通信覆盖区域,在该区域的车载节点可通过AP接入Internet进行数据下载,而其他区域为Internet链接空洞区域,该区域中的车载节点只能通过Ad Hoc链接与通信半径内的其他节点通信.

Fig. 1 Drive-Thru network architecture图 1 车联网的网络架构

本文假设车载节点的移动轨迹已知,车载节点的通信半径及传输速率相同.我们根据车辆在公路网的移动轨迹构建动态网络拓扑图[17,18],每个时间槽中的网络拓扑是静态的,其详细定义见文献[18].为了简化,我们将动态网络拓扑图变形为静态图序列(NGS),若链接空洞区域中F个时间槽,则该序列是由时间槽分割为F个静态的网络拓扑图组成.如图 2(a)所示,我们将时间槽tf的车联网的网络拓扑图模型化为图Gf=(Vf,Ef,Hf),其中,Vf是车载节点集,节点表示在时间槽tf时协作组[19]的第i个车载节点;Ef为节点间边的集合,边表示节点间的链接,即两个节点彼此在其通信范围内可以直接通信;Hf为节点上权值的集合,表示节点在时间槽tf所请求内容已下载到的数据量.

Fig. 2 Network model and corresponding conflict model图 2 网络模型及相应的传输冲突模型

网络模型及其相应的传输冲突模型如图 2(b)所示,我们将时间槽tf的传输冲突模型化为图G(I)f=(Vf,E(I)f,Hf),

其中,Vf同上;E(I)f为边集,边表示节点冲突,用符号来表示(见定义1).

AP通信覆盖区域内的车载节点通过AP无线接入Internet进行数据下载,以满足车辆接入互联网的通信需求.处于Internet链接空洞区域的车载节点已经出了AP的通信覆盖范围,接入不了Internet,只能与其通信半径内的邻居节点相互通信.车联网内容下载实例如图 3所示.V2V的传输调度如图 3中Internent链接空洞区域第1个虚线框所示,发送节点将数据包无线广播给其通信半径内的其他节点.

Fig. 3 An example of content downloading in drive-thru network图 3 车联网中内容下载实例
3 问题的形式化

本节将对车联网中结合资源分配与调度的内容下载问题及相关内容进行形式化描述.

3.1 相关定义及符号 3.1.1 符号及术语

在形式化问题之前,我们首先定义问题研究过程中用到的相关术语及符号,见表 1.

Table 1 Symbols and terms 表 1 相关术语及符号
3.1.2 相关定义

V2V数据传输过程中无线通信的传输冲突发生在以下两种情况:

(1) 若,则节点与节点发生发送冲突;

(2) 若,则节点与节点同时发送,此时,节点发生接收冲突,由此定义节点间的传输冲突,见定义1.

定义1(传输冲突). 若,则称节点与节点冲突,记为;否则,若则称节点与节点非冲突,记为

定义2(非冲突节点集). 非冲突节点集为无线通信时相互不冲突的节点组成的集合,用符号表示.时间槽tf的非冲突节点集表示,则NitÇNjt=Æ;其中,表示时间槽tf的非冲突节点集族.

3.2 问题的形式化定义

为了提高车联网内容下载的性能,必须解决以下两个问题:(1) 在链接空洞区域如何进行传输调度,才能使得所请求数据的下载量最大化;(2) 在AP通信覆盖区域内如何分配信道资源,才能够充分利用链接空洞区域节点间的数据通信(扩展AP的通信范围),填补Internet链接空洞.资源分配与传输调度相互制约、相互影响,本文将其形式化为资源分配与传输调度相结合的优化内容下载问题,即:在车联网中,对于给定的AP及协作组中车载节点的下载请求,通过AP资源分配及V2V数据传输调度,最大化数据下载量.

3.2.1 优化非冲突节点集序列调度问题

本文根据链接空洞区域节点间的链接情况,对于链接空洞区域的F个时间槽的传输冲突模型化为传输冲突图序列.从全局优化的角度,如何进行调度才能使得整个链接空洞区域所请求数据的下载量最大化.为了解决该问题,我们将其形式化为满足冲突约束的优化调度问题,即优化非冲突节点集序列调度问题(optimal conflict- free node set sequence scheduling problem,简称CFSS)及优化非冲突节点集调度问题(optimal conflict-free node set scheduling problem,简称CFSS),其定义如下:

定义3(CFSS问题). 在给定的图序列áG1,G2,…,GF-1,GFñ上求一个使得公式(1)的值最大的非冲突调度(冲突

模型如图 2(b)所示)节点集序列序列

(1)

公式(1)中的表示时间槽tf内非冲突节点集的数据下载增量,其中,

表示节点ni发送数据所产生的下载增量.

定义4(CFS问题). 在给定的拓扑图Gf上求一个使得公式(2)的值最大的非冲突调度节点集序列序列

(2)

CFS问题就是在给定的拓扑图Gf上求使得下载增量最大的非冲突节点集.

然而,本文已证明,CFS问题与CFSS问题都是NP-难的,证明见引理2及定理1.

3.2.2 结合调度的资源分配问题

一个协作组经过AP通信覆盖区域可用的AP信道资源是一定的,即AP覆盖区域的数据下载量为常数D;若确定了AP的资源分配策略,则传输调度决定了已下载资源通过链接空洞区域V2V传输产生的后期效用,即总的下载数据增量,资源分配与传输调度二者相互制约、相互关联,共同影响内容下载性能的优劣.本文形式化其为结合调度的资源分配问题(resource allocation joint scheduling problem,简称AJS),其定义如下:

定义5(AJS问题). 在最优非冲突调度节点集序列上求使得公式(3)的值最大的资源分配节点集

(3)

公式(3)中的表示使得链接空洞区域下载的数据量最大的资源分配节点集,将该节点集作为最初的数据源节点进行后续转发.而ra*是由该组节点在链接空洞区域的非冲突节点集序列的优化选择得到的,其中,扩展节点集(expanding node set)表示链接空洞区域数据下载量最大的调度节点集序列的第i个时间槽调度节点集多播后,新增的获得数据包的备选源节点的集合.rar为第r个备选的资源分配节点集,表示AP将其信道资源分配给节点集rar时,在链接空洞区域应用优化调度策略整个协作组节点下载数据的增量.

3.3 问题分析

引理1. CFSS问题要进行调度节点集序列的优化选择使得下载数据量最大,则在最后一个时间槽tF一定选择下载数据量最大的非冲突节点集.

证明:(反证法)假设为优化调度节点集序列,且在最后一个时间槽tF调度的节点集不是下载数据量最大的非冲突节点集,那么,其中,为第f个时间槽调度节点集在该时间槽内的数据下载量.令,则.因此,调度节点集序列的下载数据量这与为优化调度节点集序列,即数据下载量最大的非冲突节点集序列矛盾.

因此假设不成立,即求证的定理正确.引理1得证.

引理2. 下载数据量最大的非冲突节点集CFS问题是NP难的.

证明:对于任意给定图的最大权独立集问题MWIS的一个实例:是否存在一个权值之和大于等于的独立集,那么图上MWIS问题实例相对应的图G¢=(V¢,E¢,W¢)上的CFS问题的实例:是否存在一个权值之和大于等于K¢的非冲突节点集.

任意图的MWIS问题实例构造CFS问题实例,如图 4所示,图 4(a)中的图为任意图MWIS问题的实例,在图上按如下规则(1)~规则(4)构造对应的CFS问题实例图G¢,如图 4(b)所示.而图G为传输冲突图G¢的原网络拓扑图,如图 4(c)所示.

Fig. 4 An instance of CFS is created by an instance of NP-hard problem (MWISP) on arbitrary graph图 4 由任意图上NP难(MWIS)问题实例构造CFS问题实例

(1) 构造节点集V¢:对于,在图G¢上新增一个权值为0的节点相对应,即

,

其中,映射g为边集到节点集的双射,;

(2) 构造边集E¢:

(3) 构造权值那么;

(4) 构造

对该问题进行分析不难看出,传输冲突图G¢=(V¢,E¢)的网络拓扑图为G=(V,E),其中,V=V¢,.因此,任意图上MWIS问题的实例都可以对应到图G¢上CFS问题的实例,并且新加入节点的权值为0.因此,这些节点及所关联边的加入不影响问题的求解.将MWIS问题的解作为CFS问题的解,即,若图存在权值和大于等于

的独立集,则图G¢存在权值和大于等于K¢的非冲突节点集.从而,MWIS问题可多项式时间归约到CFS问题.而MWIS问题已被证明是NP完全的[20],因此,CFS问题是NP难的.引理2得证. 

定理1. 调度节点集序列的优化选择问题CFSS是NP难的.

证明:由引理1可知,CFSS问题的解包含CFS问题的解;而由引理2可知,CFS问题是NP难的,即CFSS问题的子问题是NP难的.因此,CFSS问题至少是NP难的.定理1得证. 

定理2. AJS问题是NP难的.

证明:由AJS问题定义(见定义5)可知,AJS问题包含CFSS问题,而CFSS问题是NP难的(见定理1),因此,AJS问题至少是NP难的.定理2得证.

4 结合调度的资源分配算法JAS

在车联网内容下载过程中,信道资源分配的关键在于:如何分配信道资源才能充分利用链接空洞区域节点间的V2V数据通信,以填补Internet链接空洞.假设AP信道资源能满足N¢个节点的下载需求.本文仅对车联网中下载请求过载情况下的内容下载进行研究,即N¢<N.因为当下载请求不过载时,AP只需“先来先服务”或“随机服务”即可;然而当系统过载时,这些方法的性能就不尽如人意,过载越严重,下载性能越差.由于下载数据量最大的资源分配AJS问题是NP-难的(其证明见定理2),从而无法直接求解使得整个协作组在链接空洞区域下载量最大的资源分配节点集.基于以上所述,本文给出结合调度的资源分配近似算法来求解该问题.

4.1 算法描述

本文提出了结合非冲突调度的资源分配算法JAS求解下载数据量最大的资源分配问题,其算法描述如下:

1) 进入AP前,节点将包含节点ID号、GPS坐标及其下载请求的(ID号,X,Y,r)数据包,通过WAP发送给AP;

2) 根据Internet链接空洞区域的图序列构建冲突图序列,基于时间槽tf的网络拓扑图G构建冲突图G¢,如图 2所示;

3) 基于网络拓扑图序列及相应冲突图序列,计算使得下载数据量最大的非冲突节点集序列,但是,由于CFSS问题是NP难的(见定理1),于是,本文基于贪心思想,提出CFSA算法,其算法如下:

(1) 在时间槽tf:① 在图G¢中选择权值最大的节点;② 将该节点加到调度节点集;③ 更新图G与图

G¢,即,在图G与图G¢上删除该节点及其所有相关联的边;

(2) 若V¹Æ并且V¢¹Æ,那么跳转到步骤(1)循环执行;否则,CFSA算法结束;

CFSA算法通过选出的非冲突节点集来传输数据,由此,该节点集的接收节点集可以获得近似最大量的下载数据.

4) 在AP通信覆盖区域内,AP基于未来链接空洞区域的传输调度进行资源分配,将其信道资源分配给ra*(见式(2)).

4.2 JAS算法伪代码

JAS算法. 结合传输调度的资源分配算法.

输入:图序列Gf=(Vf,Ef,Hf)并构建G¢f=(Vf,E¢f,Hf);

/*f=1,2,…,F,Vf为在时间槽tf通过AP通信区域的协作组中节点集*/

输出:ra.

初始化:ra=Æ,S=Æ /*ra,,S分别为资源分配节点集、时间槽tf的调度节点

集及整个链接空洞的调度节点序列*/

for f from 1 to F do

for j from 1 to N do

;

; /*求得时间槽tf的调度节点集*/

for l from 1 to N do

if then ; /*更新图Gf*/

Endfor

for l¢ from 1 to N do

if then ; /*更新图G¢f*/

Endfor

Endfor

; /*求得调度节点集序列S**/

Endfor

ra* /*根据公式(2)求得ra**/

5 模拟实验与性能分析

本节通过模拟实验对结合调度的资源分配算法的性能JAS进行分析,进而证实该方法的有效性.

5.1 实验环境

实验环境为Lenovo Thinkpad SL400,Intel Core(TM)2 Do CPU T5870 @2.00GHz,4G内存.模拟环境基于SUMO(simulation of urban mobility)模拟器.为了验证本文提出的JAS方法的有效性,我们采用SUMO模拟器产生了实验所用的车辆轨迹数据.本文使用多种移动模型并进行了多组实验取平均值,以降低偶然因素对算法性能的影响.其模拟实验参数如下设置:

· 公路网参数设置见表 2,在SUMO利用上述的参数定义出道路网络;

Table 2 Parameter settings of road networks 表 2 公路网参数设置

·表 3中,分别标注了该公路网中移动的4种不同车辆节点的参数.

Table 3 Parameter settings of vehicles 表 3 车载节点参数设置
5.2 模拟实验及实验结果

本文采用SUMO模拟器产生的数据,设计实现了Random(随机策略)、MLQ(最大化链接质量策略)、APL[19]及JAS这4种不同的算法.

5.3 性能分析

本节以传输率及系统吞吐量作为性能衡量指标,通过模拟实验,对不同内容下载策略(Random,MLQ,APL[19],JAS)的实验结果(如图 5图 6所示)进行比较来分析JAS方法的性能,并分析了协作组中车载用户数及请求下载文件大小这两个参数对文件下载性能的影响.

Fig. 5 Delivery ratio vs. file size and number of vehicles图 5 下载文件大小及车载节点数量对传输率的影响

Fig. 6 Throughput vs. file size and number of vehicles图 6 下载文件大小及车载节点数量对吞吐量的影响

从实验结果可以清楚看到:由于Random随机分配信道资源而没有考虑网络拓扑及节点间链接,因此其性能是其中最差的;MLQ考虑了节点间的链接(信噪比、速率),并基于当前节点间信道质量进行资源分配,MLQ的性能大大优于Random策略;APL策略根据车载节点的速度、加速度及车间距预测下一时间槽节点间链接的概率及链接时长,基于节点间的机会链接进行信道资源分配,其性能优于MLQ.如图 5图 6所示,本文提出的结合链接空洞区域调度的资源分配JAS策略是所有方法中最优的,该策略充分考虑了AP信道资源稀缺及节点间的竞争问题.为了高效地进行内容下载,JAS在分配信道资源时充分考虑了链接空洞区域的传输调度,并将链接空洞区域传输调度与AP通信覆盖范围内的资源分配有机地结合起来.

APL由于考虑了下一时间槽的网络拓扑,相比于Random与MLQ方法提高了系统吞吐量及传输率.在APL方法的基础上,JAS考虑了整个链接空洞F个时间槽节点间链接及每个时间槽的传输调度来进行资源分配,因此其性能在APL的基础上有了大幅度的提高.由图 5图 6可以看出:当网络不过载时,JAS性能与其他方法相近;而当系统过载越严重时,JAS相比于其他方法的优势越明显.JAS全面考虑了整个传输过程中节点间的链接问题,并在进行资源分配时充分考虑了协作组移出AP通信覆盖区域后整个链接空洞区域的传输调度问题,因此,其系统吞吐量要远远高于其他方法.实验结果证实了本文提出的JAS算法的有效性.对于所有方法,传输率都随车载节点的数量及请求文件尺寸的增加而快速下降,如图 5所示.然而,随着车载节点的数量及请求文件尺寸的增加,吞吐量呈线性增长的趋势,并大体稳定在系统吞吐能力上,不会高于系统吞吐能力(上界),如图 6所示.

6 总 结

对于车辆接入互联网的应用场景,AP响应其通信覆盖范围内车载节点接入互联网通信请求,分配其信道资源.由于AP部署稀疏且通信范围有限,这使得车辆通过AP接入互联网进行内容下载成为该网中最具挑战性的问题之一.信道资源如何分配,直接影响到链接空洞区域文件的多源转发,而链接空洞区域的传输调度又在很大程度上决定了资源分配策略的有效性,二者相互作用、互相依赖、共同影响内容下载的性能.但现有方法未将链接空洞区域节点间的链接情况与信道资源的分配建立关联,从而没能有效地利用链接空洞区域节点间的V2V通信,提高AP通信服务能力.

为了提高车联网内容下载的性能,即提高传输成功率与系统吞吐量,如下两个关键性的问题必须要解决:

· 在AP通信覆盖范围内,如何分配稀缺的Internet链接资源,才能更为有效地利用AP通信覆盖范围外节点间的V2V通信,扩展AP通信服务范围?

· 在链接空洞区域,如何进行传输调度,才能充分利用车载节点间ad hoc链接,更有效地进行内容下载?

本文针对以上两个问题展开研究,将链接空洞区域的传输调度与AP通信覆盖区域的信道资源分配作为一个整体,从全局优化的角度研究内容下载的效率问题,并将其形式化为下载数据量最大的结合非冲突调度的资源分配问题.但是,本文证明该问题是NP-难的,因此提出结合链接空洞区域的传输调度的资源分配近似算法(JAS)来解决该问题.该算法将整个链接空洞区域节点间链接的时空变化模型化为拓扑图序列,并基于此构建其传输冲突图序列,在AP通信覆盖区域基于图序列计算优化的资源分配节点集进行资源分配,通过充分利用AP覆盖区域内的资源分配及链接空洞区域的传输调度进行内容下载,以期达到虚拟扩展AP通信范围,从而填补链接空洞提高车联网内容下载系统性能的目的.模拟实验也证实了本文提出的JAS算法的有效性.与现有方法相比,显著提高了文件下载量及传输的成功率.此外,本文还对影响内容下载性能指标的因素进行了分析.

参考文献
[1] Zhao J, Arnold T, Zhang Y, Cao G. Extending drive-thru data access by vehicle-to-vehicle relay. In: Proc. of the 5th Int’l Conf. on Vehicular Inter-NETworking. San Francisco: ACM Press, 2008. 66-75 .
[2] Ott J, Kutscher D. Drive-Thru Internet: IEEE 802.11b for “Automobile” users. In: Proc. of the 23rd Conf. of the IEEE Communications Society, Vol.1. Hongkong: IEEE, 2004.362-373 .
[3] Ott J, Kutscher D. A disconnection-tolerant transport for drive-thu Internet: Environments. In: Proc. of the 24th Annual Joint Conf. of the IEEE Computer and Communications Societies, Vol. 3. Miami: IEEE, 2005.1849-1862 .
[4] Carter A. The status of vehicle-to-vehicle communication as a means of improving crash prevention performance. Technical Report, 05-0264, NHTSA, 2005. http://www-nrd.nhtsa.dot.gov/pdf/nrd-01/esv/esv19/05-0264-W.pdf
[5] Yang S, Yeo CK, Lee BS. Predictive scheduling in drive-thru networks with flow-level dynamics and deadlines.In: Proc. of the 2011 IEEE Int’l Conf. on Communications. Kyoto: IEEE, 2011.1-5 .
[6] Malandrino F, Casetti C, Chiasserini CF, Fiore M. Content downloading in vehicular networks: What really matters.In: Proc. of the 30th IEEE Int’l Conf. on Computer Communications. Shanghai: IEEE, 2011.426-430 .
[7] Lu S, Bharghavan V, Srikant R. Fair scheduling in wireless packet networks. Computer Communication Review, 1997,27(4): 63-74 .
[8] Zheng Z, Sinha P, Kumar S. Sparse WiFi deployment for vehicular Internet access with bounded. IEEE ACM Trans. on Networking, 2012,20(3):956-969 .
[9] Huang SCH, Wan P, Jia X, Du H, Shang W. Minimum-Latency broadcast scheduling in wireless ad hoc networks. In: Proc. of the 26th Annual IEEE Conf. on Computer Communications. Anchorage: IEEE, 2007.733-739 .
[10] Hariharan S, Shroff N. Deadline constrained scheduling for data aggregation in unreliable sensor networks. In: Proc. of the 2011 Int’l Symp. on Modeling and Optimization of Mobile (WiOpt 2011). Princeton: IEEE Computer Society, 2011.140-147 .
[11] Chafekar D, Levin D, Kumar A, Marathe M, Parthasarathy S, Srinivasan A. Capacity of asynchronous random-access scheduling in wireless networks. In: Proc. of the 27th IEEE Communications Society Conf. on Computer Communications. Phoenix: IEEE, 2008.1822-1830 .
[12] Yuan X, Li B, Klara N. Optimal resource allocation in wireless ad hoc networks: A price-based approach. IEEE Trans. on Mobile Computing, 2006,5(4):347-364 .
[13] Tse D, Hanly S. Multiaccess fading channels—Part I: Polymatroid structure, optimal resource allocation and throughput capacities. IEEE Trans. on Inf Theory, 1998,44(7):2796-2815 .
[14] Kivanc D, Li G, Liu H. Computationally efficient bandwidth allocation and power control for OFDMA. IEEE Trans. on Wireless Commun, 2003,2(6):1150-1158 .
[15] Nassar K, Pascal B, Philippe C, Walid H. Resource allocation for downlink cellular OFDMA systems—Part II: Practical algorithms and optimal reuse factor. IEEE Trans. on Signal Process, 2010,58(2):735-749 .
[16] Cruz-Pérez FA, Ortigoza-Guerrero L. Equal resource sharing allocation with QoS differentiation for conversational services in wireless communication networks. Communications, 2003,150(5):391-398 .
[17] Ford LR, Fulkerson DR. Flows in Networks. Princeton: Princeton University Press, 1962.
[18] Malandrino F, Casetti C, Chiasserini CF, Fiore M. Optimal content downloading in vehicular networks. IEEE Trans. on Mobile Computing, 2013,12(7):1377-1391 .
[19] Chen L, Li ZJ, Jiang SX, Fang WT, Wang S. Optimal allocation of resource based on probabilistic link in drive-thru networks. Journal of Harbin Institute of Technology, 2013,45(5):40-44 (in Chinese with English abstract).
[20] Trevisan L. Inapproximability of combinatorial optimization problems. Technical Report, TR04-065, Electronic Colloquium on Computational Complexity, 2004.
[19] 陈丽,李治军,姜守旭,方文涛,王帅.车辆接入互联网基于机会链接的资源分配.哈尔滨工业大学学报,2013,45(5):40-44 (in Chinese with English abstract).