FCD大数据并行处理的动态任务调度算法

doi:10.3969/j.issn.0253-2778.2018.09.005

中国科学技术大学学报 ›› 2018, Vol. 48 ›› Issue (9): 718-722.DOI: 10.3969/j.issn.0253-2778.2018.09.005

FCD大数据并行处理的动态任务调度算法

陈锋，张智，李琴剑，陈宇强，陈国良

1.中国科学技术大学信息学院，合肥 230027;2.安徽中科龙安科技股份有限公司，安徽合肥 230088; 3.中国科学技术大学计算机学院，安徽合肥 230027

收稿日期:2018-03-27 修回日期:2018-04-27 接受日期:2018-04-27 出版日期:2018-09-30 发布日期:2018-04-27
通讯作者: 陈锋
作者简介:陈锋(通讯作者),男,1966年生,博士/副教授.研究方向: 研究神经网络与模式识别. E-mail: chenfeng@ustc.edu.cn
基金资助:
国家重点研发(973)计划(２０１７YFC０８４０２０６)，安徽省重大科技专项(１７０３０９０１００７)资助.

Dynamic task scheduling algorithm of parallel computing for FCD big data

CHEN Feng, ZHANG Zhi, LI Qinjian, CHEN Yuqiang, CHEN Guoliang

1. Department of Automation, University of Science and Technology of China, Hefei 230027, China; 2. Anhui LoongSon Science and Technology Co.,Ltd, Hefei 230088, China; 3. School of Computer Science and technology, University of Science and Technology of China, Hefei 230027, China

Received:2018-03-27 Revised:2018-04-27 Accepted:2018-04-27 Online:2018-09-30 Published:2018-04-27

摘要/Abstract

摘要： 浮动车数据（floating car data, FCD）技术是大规模城市路网交通流实时采集的有效方法.城市交通的动态诱导和控制需要对海量FCD进行快速处理.鉴于此，提出了FCD并行计算的动态任务调度方法.针对FCD数据包计算时间的不确定性和动态性，根据计算节点的处理能力进行数据包的动态分割，在处理过程中，采用动态任务分配策略以实现计算节点的同步.该方法在龙芯国产大数据一体机平台上进行了实现，并采用现场FCD数据进行了实验验证，结果表明，该方法较轮询和Min-Min调度算法，显著地提高了并行处理的性能.

关键词: 浮动车数据, 大数据, 并行计算, 动态任务划分, 动态任务调度

Abstract: FCD (floating car data) technique is new way of collecting real-time traffic flow from large-scale urban networks. It is necessary to implement rapid processing of FCD big data for the dynamic guidance and control of urban traffic. A dynamic task scheduling algorithm is proposed for parallel computation of FCD. To address the uncertainty and dynamics of FCD package processing, FCD packages are partitioned dynamically. The load balance among computing nodes can be achieved using the dynamic task allocation strategy. The algorithm is developed on LoongSon big data integrated machine platform and evaluated using field FCD. The experimental results indicate that the proposed algorithm has significantly higher parallel processing performances compared to the polling scheduling algorithm and Min-Min scheduling algorithm.

Key words: floating car data, big data, parallel computing, dynamic task partition, dynamic task scheduling

中图分类号:

TP391

陈锋，张智，李琴剑，陈宇强，陈国良. FCD大数据并行处理的动态任务调度算法[J]. 中国科学技术大学学报, 2018, 48(9): 718-722.

CHEN Feng, ZHANG Zhi, LI Qinjian, CHEN Yuqiang, CHEN Guoliang. Dynamic task scheduling algorithm of parallel computing for FCD big data[J]. Journal of University of Science and Technology of China, 2018, 48(9): 718-722.

参考文献

［1］
ISAENKO N, COLOMBARONI C, FUSCOG.Traffic dynamics estimation by using raw floating car data[C]// Proceedings of the 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems. 2017: 704-709.
[2] DE FABRITIIS C, RAGONA R, VALENTI G. Traffic Estimation and prediction based on real time floating car data[C]// 11th International IEEE Conference on Intelligent Transportation Systems. Beijing: IEEE Press, 2008:197-203.
[3] YU Q, RONG J, LIU X M. Floating vehicle data detection system in Beijing[C]//2006 IEEE Intelligent Vehicles Symposium. Tokyo, Japan: IEEE Press, 2006: 320-324.
[4] MESSELODI S, MODENA C M, ZANIN M, et al. Intelligent extended floating car data collection [J]. Expert Systems with Applications, 2009, 36(3):4213-4227.
[5] SONG G, ZHANG F, LIU J, et al. Floating car data-based method for detecting flooding incident under grade separation bridges in Beijing[J]. IET Intelligent Transport Systems, 2015, 9(8): 817-823.
[6] PFOSER D, TRYFONA N, VOISARD A. Dynamic travel time maps - enabling efficient navigation[C]// 18th International Conference on Scientific and Statistical Database Management. Vienna,Astria: IEEE Press, 2006: 369-378.
[7] MICHAEL JONES; YANFENG GENG; DANIEL NIKOVSKI, et al. Predicting link travel times from floating car data[C]// 16th International IEEE Conference on Intelligent Transportation Systems. Hague, Newtherlands: IEEE Press, 2013: 1756-1763.
[8] ISAENKO N, COLOMBARONI C, FUSCO G. Traffic dynamics estimation by using raw floating car data[C]// 2017 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems. Naples, Italy: IEEE Press, 2017: 704-709.
[9] 陈锋，庞昊, 等. KD-50-I-E平台的FCD 并行计算与交通动态诱导[J]. 中国科学技术大学学报, 2009，39(5): 558-560.
[10] DENG Z, BAI Y Q. Floating car data processing model based on Hadoop-GIS tools[C]// Fifth International Conference on Agro-GeoInformatics. Tianjing, China: IEEE Press, 2016: 1-4.
[11] ZHANG D B, SHOU Y F, XU J M. The modeling of big traffic data processing based on cloud computing[C]// 12th World Congress on Intelligent Control and Automation. Guilin, China: IEEE Press, 2016: 2394-2399.
[12] LU W, WANG W J, KIMITA K, et al. Decreasing FCD processing delay by deploying distributed processing system[C]// 6th International Conference on ITS Telecommunications. Chengdu, China: IEEE Press, 2006: 206-209.
[13] ZHANG Z H, JIANG C J, FANG Y. Road situation modeling and parallel algorithm implementation with FCD based on principle curves[C]// Eighth International Conference on High-Performance Computing in Asia-Pacific Region. Beijing， China: IEEE Press, 2005: 6 -11.

[14] CHAUHAN SS, JOSHI R C. QoS guided heuristic algorithms for grid task scheduling. International Journal of Computer Applications, 2010, 2(9): 24-31.
[15] KOKILAVANI T, AMALARETHINAM D I. Load balanced Min-Min algorithm for static meta-task scheduling in grid computing[J]. International Journal of Computer Applications, 2011, 20(2): 43-49.
[16] 朱虹宇，李挺，闫建恩，等. 基于动态负载均衡的分布式任务调度算法研究[J]. 高技术通讯，2014，24(12): 1261-1269.

()
()

[1]	邱镇，王琪媛，刘迪，孟洪民. 一种基于可伸缩模式的潜在语义挖掘方法[J]. 中国科学技术大学学报, 2019, 49(7): 524-532.
[2]	陈志注，王宏志，熊风，张义策，高宏，李建中. 大数据拍卖的定价策略与方法[J]. 中国科学技术大学学报, 2018, 48(6): 486-494.
[3]	蔡勇，陈红梅，. MapReduce环境下基于概念分层的概念格并行构造算法[J]. 中国科学技术大学学报, 2018, 48(4): 275-283.
[4]	王佳玉，张振宇，褚征，吴晓红. 一种基于轨迹数据密度分区的分布式并行聚类方法[J]. 中国科学技术大学学报, 2018, 48(1): 47-56.
[5]	徐子伟，王鹏，陈宗海. 一种基于Fisher比率和预测风险准则的电信客户流失预测分步特征选择方法[J]. 中国科学技术大学学报, 2017, 47(8): 686-694.
[6]	陈振国，田立勤，林闯. 基于感知源信任评价的物联网数据可靠保障模型[J]. 中国科学技术大学学报, 2017, 47(4): 297-303.
[7]	卜尧，吴斌，陈玉峰，白德盟. BDAP——一个基于Spark的数据挖掘工具平台[J]. 中国科学技术大学学报, 2017, 47(4): 358-368.
[8]	郭景，陈贤富. 基于OpenCL的加速鲁棒特征算法并行实现[J]. 中国科学技术大学学报, 2017, 47(10): 808-816.
[9]	谢青，彭威，柳瑶阁，黄涛，卢德唐. 改进的储层直接取样随机模拟方法及GPU实现[J]. 中国科学技术大学学报, 2013, 43(8): 626-630.

FCD大数据并行处理的动态任务调度算法

Dynamic task scheduling algorithm of parallel computing for FCD big data

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价