详情

原文传递车辆WiFi接入互联网中基于轨迹的下载任务调度研究

论文题名：	车辆WiFi接入互联网中基于轨迹的下载任务调度研究
关键词：	车载网络;下载任务调度;服务质量;拓扑结构;轨迹信息
摘要：	车载网络是车辆间、车辆与路边基础设施之间通过无线连接形成的一种拓扑动态变化的无线移动网络。路边基础设施分为两类，一类通过有线接入Internet，通常简称为AP(Access Point)，另一类只提供简单的存储转发，简称RSU(RoadSide Unit)。在车载网络中，车辆之间、车辆与RSU之间主要通过Ad Hoc方式相连，而车辆与路边基础设施之间则主要通过WiFi方式连接。　　车载用户通过车载网络接入 Internet获得各种信息服务，如查询商场、饭店、加油站、交通管理、路况及最新的天气、新闻等。当然，车载用户也可以通过3G或卫星获得上述服务，但其费用比较昂贵，而通过AP一般可以免费获得高性能的Internet链接。因此，如何充分利用AP为车载用户提供Internet接入服务、尤其是数据下载服务是目前车载网络中的重要研究内容。　　虽然各国政府都在投入大量资金部署各种 AP，但仍无法满足日益增长的车载用户对Internet的下载请求。目前，即使在较发达的城市中，AP的通信范围也还不能完全覆盖街道上行驶的车辆，我们将两个相邻 AP之间未被AP通信覆盖的区域称为链接空洞。进入链接空洞的车载用户将无法通过WiFi方式接入Internet，但可以通过Ad Hoc方式通过其周围的其它车载节点经多跳接入Internet。　　在AP不能完全满足车载用户下载请求的条件下，各个 AP可以通过对其接收到的下载请求进行调度，以便提高整个车载网络的服务能力。显然，那些可以为更多相邻节点提供转发服务的车载节点的请求应该被优先调度执行，因此，AP调度的核心任务就是为其覆盖范围内的车载节点确定一种优先级，优先级高的节点的请求将被优先调度执行。　　车载节点的调度优先级主要取决于相邻节点的下载请求类别及车载网络的拓扑结构，由于下载请求的类别比较容易判别，而车载网络的拓扑结构却是动态变化的，因此如何获取车载网络的拓扑结构并利用其确定节点的调度优先级就是AP调度的一个关键问题。　　本文主要研究基于动态网络拓扑的车载节点下载任务调度问题，车载网络的拓扑结构主要跟车辆的行驶轨迹有关。有些车辆(如出租车)会定期向服务器发送其GPS信息，这类车辆形成的轨迹信息是确定的，而其他车辆的轨迹信息则往往是不确定的，因此，本文基于车辆轨迹信息确定和不确定两种情况对AP下载任务调度开展了如下几个方面的研究：　　首先，在车辆轨迹信息确定的情况下，研究了基于链接空洞区域车辆间Ad Hoc连接的AP下载任务调度问题。　　由于进入链接空洞的车载用户只能通过那些已经获得所需信息的相邻节点下载所需信息，因此进入链接空洞后能为更多相邻车辆提供转发服务的节点应该具有更高的调度优先级。为此，本文研究了使链接空洞区域数据下载总量最大的AP任务调度集求解问题，并证明了该问题是NP-完全的，于是，本文提出了一种JAS近似算法来对该问题进行求解，实验结果表明该算法是有效的。　　然后，在车辆轨迹信息不确定的情况下，研究了基于链接空洞区域车辆间机会链接的AP下载任务调度问题。　　虽然车辆轨迹信息不确定时无法确定链接空洞区域车辆间的连接情况，但利用车辆的当前行驶情况可以预测下一时段前方车辆间的链接情况，基于这种通过预测建立起来的机会可达图，本文研究了使链接空洞区域数据下载成功率最高的AP任务调度集求解问题，并证明了该问题是 NP-完全的，为此，本文提出了一种基于机会可达图的任务调度近似算法，实验结果表明该算法是有效的。　　其次，在车辆行驶过程中不经过 AP的情况下，研究了基于节点间机会链接历史统计信息的无AP任务调度问题。　　如果车辆在行驶过程中不经过任何 AP，仍然可以通过多跳携带-转发的方式获得所需要的信息，但需要其他车辆充当它的移动网关(简称MG)，路线固定、运行特征可预测的公交车就是最理想的移动网关。本文研究了基于公交车移动网关的无 AP下载任务调度问题，提出了一种最小化传输延迟期望的下载任务调度方法，实验结果表明该方法在满足下载成功率阈值前提下，能够获得最小传输延迟期望。　　最后，为了解决车载网络中 AP负载不均衡的问题，本文研究了基于下载请求时空分布的多AP合作的下载任务调度问题。　　针对网络中 AP通信负载不均衡的问题，本文利用AP通信负载随时空动态变化这一规律，将整网 AP通信负载的时空分布抽象为一个 AP任务队列的时变图序列，基于该序列，提出了一种基于轨迹的多 AP合作下载任务调度方法，实验表明，该方法可以从时空两个维度均衡整网AP的通信负载。
作者：	陈丽
专业：	计算机软件与理论
导师：	姜守旭
授予学位：	博士
授予学位单位：	哈尔滨工业大学
学位年度：	2014
正文语种：	中文