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

doi:10.11772/j.issn.1001-9081.2015.11.3139

计算机应用 ›› 2015, Vol. 35 ›› Issue (11): 3139-3145.DOI: 10.11772/j.issn.1001-9081.2015.11.3139

• 2015年全国开放式分布与并行计算学术年会(DPCS 2015)论文 • 上一篇下一篇

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

李慧勇, 陈仪香

华东师范大学教育部软硬件协同设计技术与应用工程研究中心, 上海 200062

收稿日期:2015-06-17 修回日期:2015-07-08 发布日期:2015-11-13
通讯作者: 陈仪香(1961-),男,江苏徐州人,教授,博士生导师,博士,主要研究方向:物联网、可信计算.
作者简介:李慧勇(1980-),男,山西太原人,讲师,博士研究生,主要研究方向:物联网、可信计算.
基金资助:
国家973计划项目(2011CB302802);国家自然科学基金资助项目(61370100);上海知识服务平台计划项目(ZF1213);上海市科委项目(14511100400).

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

LI Huiyong, CHEN Yixiang

MoE Engineering Research Center for Software/Hardware Co-design Technology and Application, East China Normal University, Shanghai 200062, China

Received:2015-06-17 Revised:2015-07-08 Published:2015-11-13

摘要/Abstract

摘要： 针对车联网中数据流分布式处理的调度问题,提出了多维服务质量(QoS)改进异构计算最早完成时间(HEFT)调度算法.首先,分别建立了车联网中数据流的分布式处理任务的带权有向无环图模型和车联网分布式计算资源的七维QoS属性带权无向拓扑结构图模型.其次,改进经典的HEFT调度算法中的列表构造方法为最高层最小后继任务优先列表构造方法; 同时,将车联网分布式计算资源的七维QoS属性进行分组、降维,转化为两维综合属性优先权:计算性能优先权和通信性能优先权,形成了两种不同用户偏好的多维QoS改进HEFT调度算法.最后,通过算例分析表明:两种不同用户偏好的多维QoS改进HEFT调度算法综合性能优于经典的HEFT调度算法和轮询调度算法.

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

Abstract: In order to solve the scheduling problem of distributed processing data stream in Internet 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 Internet 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 Internet 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 multi-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.

Key words: distributed mobile computing, Internet of Vehicles, list scheduling algorithm, multi-dimensional QoS scheduling algorithm, Heterogereous Earliest Finish Time (HEFT) scheduling algorithm

中图分类号:

TP39

李慧勇, 陈仪香. 车联网数据流的多维服务质量改进异构计算最早完成时间调度算法[J]. 计算机应用, 2015, 35(11): 3139-3145.

LI Huiyong, CHEN Yixiang. Improved heterogereous earliest finish time scheduling algorithm with multi-dimensional quality of service for data stream processing task in Internet of vehicles[J]. Journal of Computer Applications, 2015, 35(11): 3139-3145.

参考文献

[1] ARMBRUST M, FOX A, GRIFFITH R, et al.A view of cloud computing[J]. Communications of the ACM, 2010, 53(4): 50-58.
[2] HARTENSTEIN H. VANET: vehicular applications and inter-networking technologies[M]. Chichester: Wiley, 2010:10-15.
[3] GERLA M, LEE E K, PAU G, et al.Internet of vehicles: From intelligent grid to autonomous cars and vehicular clouds[C]// Proceedings of the 2014 IEEE World Forum on Internet of Things. Piscataway: IEEE, 2014: 241-246.
[4] LI J, PENG J. Task scheduling algorithm based on improved genetic algorithm in cloud computing environment[J]. Journal of Computer Applications, 2011, 31(1): 184-186. (李建锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,31 (1):184-186.)
[5] HUA X, ZHENG J, HU W. Ant colony optimization algorithm for computing resource allocation based on cloud computing environment [J]. Journal of East China Normal University:Natural Science, 2010(1): 127-134. (华夏渝,郑骏,胡文心. 基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报:自然科学版,2010(1):127-134.)
[6] SUN R, ZHAO Z. Resource scheduling strategy based on cloud computing[J]. Aeronautical Computing Technique, 2010, 40(3): 103-105. (孙瑞锋,赵政文. 基于云计算的资源调度策略[J].航空计算技术,2010,40(3):103-105.)
[7] SUN D, CHANG G, LI F, et al.Optimizing multi-dimensional QoS cloud resource scheduling by immune clonal with preference[J]. Acta Electronica Sinica, 2011, 39(8): 1824-1831.(孙大为,常桂然,李凤云,等.一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J].电子学报,2011,39(8):1824-1831.)
[8] ZHAO J. Genetic algorithm and ant colony algorithm based energy efficient task scheduling[D]. Jinan: Shandong University,2013: 22-28.(赵建峰.基于遗传算法和蚁群算法的节能调度研究[D].济南: 山东大学,2013: 22-28.)
[9] GUO Y, LI N, LI X, et al. Multiple projects scheduling method based on cloud multi-objective particle swarm optimization[J]. Computer Engineering and Applications, 2012, 48(21): 15-20. (郭研,李南,李兴森,等.基于云多目标微粒群算法的多项目调度方法[J].计算机工程与应用,2012,48(21):15-20.)
[10] ZUO L, CAO Z. Review of scheduling research in cloud computing[J]. Application Research of Computers, 2012, 29(11): 4023-4027. (左利云,曹志波.云计算中调度问题研究综述[J].计算机应用研究,2012,29(11):4023-4027.)
[11] LI J,WANG X,WU Y, et al.Improved priority list task scheduling algorithm[J].Computer Science,2014,41(5):20-23.(李静梅,王雪,吴艳霞,等.一种改进的优先级列表任务调度算法[J].计算机科学,2014,41(5):20-23.)
[12] KWOK Y K, AHMAD I. Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(5): 506-521.
[13] LIU Z, FANG B, JIANG Y, et al.A new algorithm for scheduling Fork-Join task graph[J]. Journal of Software, 2002, 13(4): 693-696. (刘振英, 方滨兴, 姜誉, 等. 一个调度 Fork-Join 任务图的新算法[J]. 软件学报, 2002, 13(4):693-696.)
[14] WU M, GAJSKI D D. Hypertool: a programming aid for message-passing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 1990, 1(3): 330-343.
[15] KRUATRACHUE B, LEWIS T. Grain size determination for parallel processing[J]. IEEE Software, 1988, 5(1): 23-32.
[16] SIH G C, LEE E A. Scheduling to account for interprocessor communication within interconnection-constrained processor networks[C]// Proceedings of the 1990 International Conference on Parallel Processing. Piscataway: IEEE, 1990: 9-16.
[17] TOPCUOGLU H, HARIRI S, WU M. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.
[18] CHENG H, HUANG X, XIONG N. Minimum-energy broadcast algorithm for wireless sensor networks with unreliable communications[J]. Journal of Software, 2014,25(5):1101-1112.(程红举,黄行波,XIONG Naixue.不可靠通信环境下无线传感器网络最小能耗广播算法[J].软件学报,2014,25(5):1101-1112.)
[19] STOJMENOVIC I, NAYAK A, KURUVILA J, et al.Physical layer impact on the design and performance of routing and broadcasting protocols in Ad Hoc and sensor networks[J]. Computer Communications, 2005, 28(10): 1138-1151.
[20] ANIELLO L, BALDONI R, QUERZONI L. Adaptive online scheduling in storm[C]// Proceedings of the 7th ACM International Conference on Distributed Event-based Systems. New York: ACM, 2013: 207-218.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈成瑞, 孙宁, 何世彪, 廖勇. 面向C-V2X通信的基于深度学习的联合信道估计与均衡算法[J]. 计算机应用, 2021, 41(9): 2687-2693.
[2]	陈葳葳, 曹利, 顾翔. 基于区块链的车联网电子取证模型[J]. 计算机应用, 2021, 41(7): 1989-1995.
[3]	王家瑞, 谭国平, 周思源. 高速车联网场景下分簇式无线联邦学习算法[J]. 计算机应用, 2021, 41(6): 1546-1550.
[4]	巫光福, 王影军. 基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案[J]. 计算机应用, 2021, 41(10): 2885-2892.
[5]	陈锦宇, 刘兆伟. 基于改进投票证明共识协议的车联网系统[J]. 计算机应用, 2021, 41(1): 170-176.
[6]	黄辰, 曹建农, 王时绘, 张龑. 基于协作反馈控制算法的车联网行车安全动态强化模型[J]. 计算机应用, 2020, 40(4): 1209-1214.
[7]	陈葳葳, 曹利, 邵长虹. 基于区块链技术的车联网高效匿名认证方案[J]. 计算机应用, 2020, 40(10): 2992-2999.
[8]	樊娜, 朱光源, 康军, 唐蕾, 朱依水, 王路阳, 段嘉欣. 车联网环境下基于节点认知交互的路由算法[J]. 计算机应用, 2019, 39(2): 518-522.
[9]	陈镜任, 吴业福, 吴冰. 基于车辆行驶数据的驾驶人行为谱分析方法[J]. 计算机应用, 2018, 38(7): 1916-1922.
[10]	袁娜, 史昕, 赵祥模. 基于改进人工鱼群算法的车辆轨迹规划方法[J]. 计算机应用, 2018, 38(10): 3030-3035.
[11]	董柏宏, 邓健, 张定杰, 吴维刚. 软件定义车联网的数据转发策略和路由选择技术[J]. 计算机应用, 2018, 38(1): 26-30.
[12]	张春花, 臧海娟, 薛小平, 张芳, 陈康强, 冯丽娟. 车联网轨迹隐私保护研究进展[J]. 计算机应用, 2017, 37(7): 1921-1925.
[13]	左雨星, 郭爱煌, 黄博, 王露. 基于网络效用最大化的车联网功率控制算法[J]. 计算机应用, 2017, 37(12): 3345-3350.
[14]	杨志伟, 陈昊亮, 张波, 吴丽娟, 吴维刚. 软件定义车联网的数据转发机制[J]. 计算机应用, 2017, 37(1): 84-89.
[15]	王永胜, 谭国真, 刘明剑, 丁男. 车联网环境下的公交自适应优先方法[J]. 计算机应用, 2016, 36(8): 2181-2186.