面向车联网应用的数据关联性任务调度算法  

Data Related Task Scheduling for Vehicular Ad Hoc Networks

作　　者：丁男[1,2,3] 聂率航 许力[3] 谭国真[1,2] 

机构地区：[1]大连理工大学计算机科学与技术学院,辽宁大连116023 [2]辽宁省物联网与协同感知工程技术研究中心,辽宁大连116023 [3]软件架构国家重点实验室(东软集团股份有限公司),沈阳110179

出　　处：《计算机学报》2017年第7期1614-1625,共12页Chinese Journal of Computers

基　　金：国家自然科学基金项目(61471084);国家"八六三"高技术研究发展计划项目(2012AA111902);软件架构国家重点实验室开放课题基金(SKLSAOP1602)资助~~

摘　　要：多核系统的广泛应用提高了任务的并发性,同时也带来了任务核间通信这一额外开销.对于具有数据关联性的任务,核间通信会极大地影响任务的调度长度和实时性.结合车联网多任务混合并发的应用特点,针对多核系统中任务响应实时性问题,该文提出了一种面向车联网应用的数据关联性任务调度算法(DTSV).首先,根据车联网协议标准中针对车联网应用相关的三类数据及其特性进行了描述与分析.车联网应用中任务被分为安全关键类、交通效率类和安全无关类,每类任务都包含大量参数.有些参数并不仅存在于一个任务中,而会同时被多个任务所应用.因此,在车联网中,任务之间存在着大量的数据关联性.基于常用关联性任务模型以及车联网中任务特性,定义了一种基于车联网应用的数据关联性模型.其次,根据任务相关性模型给出了任务关联性评价函数,该评价函数的建立主要依据与计算型任务有关的所有通信型任务,生成一个多维的向量,以表示任务与内核中任务之间的强弱关联关系.再次,根据上述关联性模型和评价函数设计了基于此评价函数的关联性任务调度算法,通过将数据关联性较强的任务分配到同一个内核,以减少任务执行过程中核间通信量.算法分为初始化阶段和运行阶段.算法的初始化阶段主要解决了车联网系统启动时大量周期性任务的分配问题,能够明显地减少周期性任务的周期调度长度.算法的运行阶段主要解决了车联网系统运行中随机产生的非周期性任务的分配问题,考虑到非周期性任务的特性,算法能够在一定程度上提高其实时性.同时,在算法的运行阶段,通过对非周期性任务的数据关联的预处理,更进一步提高了非周期性任务的实时性.最后,通过实验将DTSV与传统多核任务调度算法做出了比较,结果显示DTSV平均能够缩短10.6%整体任务调度长度,The extensive application of multi-core system improves the concurrency of tasks, however, brings the extra cost of inter-core communication. Inter-core communication will significant affect the schedule length and real-time of data related tasks. Aiming at the problem of real-time task response in multi-core processor system, this paper proposes a data related task scheduling algorithm （DTSV） for Vehicular Ad Hoc Networks （VANETs）, with considering the multi-task concurrency mechanism in VANETs. Firstly, three types of data in Vehicular Ad Hoc Networks applications and their features are described and analyzed according to the vehicular networks protocol standards. In vehicular networks protocol standards, tasks of vehicular networks applications are divided into three types, Critical Safety, Traffic Efficiency and Non-Safety. Every type of task consists of a lot of parameters. In these parameters, some of them are not included in only one task, but included in several tasks. So it can be inferred that tasks of vehicular networks applications are related by data correlation. Based on the common data related task model and the task characteristics in vehicle networks, a related task model based on data correlation of vehicular networks applications is defined. Secondly, an evaluation function is proposed according to the related task model. The evaluation function is mainly constructed by the communicating tasks of computing task. And then a multidimensional vector is gotten from the evaluation function, to characterize the strong and weak correlation between tasks. Furthermore, a data related task scheduling algorithm based on the related task model and evaluation function is designed to reduce the inter-core communications during task execution by assigning tasks which have deep correlation in data into a same core. There are two phases for the algorithm, initialization phase and running phase. The initialization phase of the algorithm works at the start time of VANET system, to assign periodic tasks wh

关 键 词：资源分配 多核系统 数据关联性 车联网 任务调度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]