Dynamic task scheduling algorithm of parallel computing for FCD big data

doi:10.3969/j.issn.0253-2778.2018.09.005

Journal of University of Science and Technology of China ›› 2018, Vol. 48 ›› Issue (9): 718-722.DOI: 10.3969/j.issn.0253-2778.2018.09.005

• Original Paper • Previous Articles Next Articles

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

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

CLC Number:

TP391

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.

References

［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]	QIU Zhen, WANG Qiyuan, LIU Di, MENG Hongmin. A novel method for mining latent events based on scalable patterns [J]. Journal of University of Science and Technology of China, 2019, 49(7): 524-532.
[2]	CHEN Zhizhu, WANG Hongzhi, XIONG Feng, ZHANG Yice, GAO Hong, LI Jianzhong. Research on the auction strategies and pricing of big data [J]. Journal of University of Science and Technology of China, 2018, 48(6): 486-494.
[3]	CAI Yong, CHEN Hongmei,. A parallel algorithm for constructing concept lattice based on hierarchical concept under MapReduce [J]. Journal of University of Science and Technology of China, 2018, 48(4): 275-283.
[4]	WANG Jiayu, ZHANG Zhenyu, CHU Zheng, WU Xiaohong. A trajectory data density partition based distributed parallel clustering method [J]. Journal of University of Science and Technology of China, 2018, 48(1): 47-56.
[5]	XU Ziwei, WANG Peng, CHEN Zonghai. A two-stage feature selection method based on Fisher’s ratio and prediction risk for telecom customer churn prediction [J]. Journal of University of Science and Technology of China, 2017, 47(8): 686-694.
[6]	CHEN Zhenguo, TIAN Liqin, LIN Chuang. Data reliable assurance model of Internet of Things based on the trust evaluation of perceived source [J]. Journal of University of Science and Technology of China, 2017, 47(4): 297-303.
[7]	BU Yao, WU Bin, CHEN Yufeng, BAI Demeng. BDAP: A data mining platform based on Spark [J]. Journal of University of Science and Technology of China, 2017, 47(4): 358-368.
[8]	GUO Jing, CHEN Xianfu. Parallel implementation of surf algorithm based on OpenCL [J]. Journal of University of Science and Technology of China, 2017, 47(10): 808-816.
[9]	XIE Qing, PENG Wei, LIU Yaoge, HUANG Tao, LU Detang. Improvements for direct sampling stochastic simulation and GPU implementation [J]. Journal of University of Science and Technology of China, 2013, 43(8): 626-630.

Dynamic task scheduling algorithm of parallel computing for FCD big data

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 9

Recommended Articles

Metrics

Comments