车联网数据流的多维服务质量改进异构计算最早完成时间调度算法  

Improved heterogereous earliest finish time scheduling algorithm with multi-dimensional quality of service for data stream processing task in Internet of vehicles

作　　者：李慧勇[1] 陈仪香[1] 

机构地区：[1]华东师范大学教育部软硬件协同设计技术与应用工程研究中心,上海200062

出　　处：《计算机应用》2015年第11期3139-3145,共7页journal of Computer Applications

基　　金：国家973计划项目(2011CB302802);国家自然科学基金资助项目(61370100);上海知识服务平台计划项目(ZF1213);上海市科委项目(14511100400)

摘　　要：针对车联网中数据流分布式处理的调度问题,提出了多维服务质量(QoS)改进异构计算最早完成时间(HEFT)调度算法。首先,分别建立了车联网中数据流的分布式处理任务的带权有向无环图模型和车联网分布式计算资源的七维QoS属性带权无向拓扑结构图模型。其次,改进经典的HEFT调度算法中的列表构造方法为最高层最小后继任务优先列表构造方法;同时,将车联网分布式计算资源的七维QoS属性进行分组、降维,转化为两维综合属性优先权:计算性能优先权和通信性能优先权,形成了两种不同用户偏好的多维QoS改进HEFT调度算法。最后,通过算例分析表明:两种不同用户偏好的多维QoS改进HEFT调度算法综合性能优于经典的HEFT调度算法和轮询调度算法。In order to solve the scheduling problem of distributed processing data stream in Interact of vehicles, two kinds of improved Heterogereous Earliest Finish Time （HEFT） scheduling algorithm for multi-dimensional QoS （ Quality of Service） were proposed. Firstly, the weighted directed acyclic graph model of distributed processing data stream task and the seven- dimensional QoS attributes weighted undirected topology model of distributed computing resources of Intemet of vehicles were established. Secondly, the method of building lists in the classic HEFT scheduling algorithm was improved to a new one based on the priority of highest-level, minimum-successor tasks. Meanwhile, the seven-dimensional QoS attributes of computing resources in Interact of vehicles were grouped and reduced into two-dimensional composite attributes： the computing priority and communicating priority. Based on this improvement, two different improved HEFT scheduling algorithms due to the preferences of users for muhi-dimensional QoS were proposed. Finally, the analysis of an example shows that the overall performance of these two multidimensional QoS improved HEFT scheduling algorithms are better than the classical HEFT scheduling algorithm and the round-robin scheduling algorithm.

关 键 词：分布式移动计算 车联网 列表调度算法 多维服务质量调度算法 异构计算最早完成时间调度算法 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]