民航信息交换任务调度方案

doi:10.11772/j.issn.1001-9081.2014.05.1507

摘要
图/表
参考文献(0)
相关文章 (15)

全文: PDF (766 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要

民航信息数据交换平台承担了大数据量的分布式传输任务，需要建立完善的任务调度模型和调度算法。基于民航信息交换平台的架构和需求，在分析比较现有的任务调度模型和调度算法基础上，提出适用于数据交换任务调度问题的解决方案，将点对多点数据传输网络映射为带约束的Steiner树模型，并用改进的遗传算法进行求解。实验仿真将此算法与最大带宽优先分配算法对比，结果充分验证了模型的正确性和可行性。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	潘宇
	宋雪雁
	孙济洲

Abstract：

In order to support the distributed transmission of a lot of tasks on the data exchange platform for civil aviation information, it needs to establish the efficient task scheduling algorithms and models. Based on the infrastructure and needs of the platform, after analyzing the existing task scheduling models and scheduling algorithms, a new task scheduling model was proposed to fulfill the data exchange on this platform. This model mapped the point-to-multipoint data transmission network to a Steiner tree problem with delay and bandwidth constraints, and an improved Genetic Algorithm (GA) was also proposed to solve the constrained Steiner tree problem. The results of comparative experiment with the maximum bandwidth allocation algorithm prove the validity and feasibility of the proposed model.

收稿日期: 2013-10-18 出版日期: 2014-05-30

基金资助:

国家自然科学基金项目;天津市科技支撑计划重点项目

通讯作者: 宋雪雁 E-mail: songxy@tju.edu.cn

作者简介: 潘宇(1989-),男,河北秦皇岛人,硕士研究生,主要研究方向:分布式系统、组合优化;
宋雪雁(1970-),女,天津人,副教授,博士,主要研究方向:优化、调度、机器学习;
孙济洲(1949-),男,天津人,教授,博士生导师,博士,主要研究方向:计算机图形与图像、分布式与并行计算、计算机系统结构。

引用本文:

潘宇宋雪雁孙济洲. 民航信息交换任务调度方案[J]. 计算机应用, 2014, 34(5): 1507-1510. PAN Yu SONG Xueyan SUN Jizhou. Task scheduling scheme for civil aviation information exchange. Journal of Computer Applications, 2014, 34(5): 1507-1510.

链接本文:

http://www.joca.cn/CN/10.11772/j.issn.1001-9081.2014.05.1507 或 http://www.joca.cn/CN/Y2014/V34/I5/1507

［1］	YANG J. How China faces significant changes in international AIS field ［J］. China Civil Aviation, 2006, 71(11): 39-40. (杨京.中国如何面对国际AIS领域的重大变革［J］.中国民用航空, 2006, 71(11): 39-40.)
［2］	BRUNK B K, POROSNICU E. A tour of the AIXM concept ［C］// Proceedings of the 2004 ESRI International Users Conference. San Diego: ［s.n.］, 2004: 2190.
［3］	LI Y, WANG J. Research of flight procedure data sharing and exchanging technology XML-based ［D］. Tianjin: Civil Aviation University of China, 2011. (李亚娟,王洁宁.基于XML的飞行程序数据共享与交换技术研究［D］.天津:中国民航大学,2011.)
［4］	LIU Y, LIAN D. Design of task scheduling model of data exchange platform ［J］. Journal of Chinese Computer Systems, 2013, 34(7): 1543-1546. (刘应明,廉东本.数据交换平台的任务调度模型设计［J］.小型微型计算机系统, 2013, 34(7): 1543-1546.)
［5］	FENG J, QI D, QIAN Z. Job scheduling solution based on data exchange and synchronization ［J］. Journal of Computer Applications, 2009, 29(11):3165-3170. (冯家耀,齐德昱,钱正平.基于数据交换与同步的作业调度方案［J］.计算机应用,2009,29(11):3165-3170.)
［6］	LENSTRA J K, RINNOOY KAN A H G. An introduction to multiprocessor scheduling ［J］. Qüestiió, 1981, 5(1): 49-57.
［7］	HOU E S H, ANSARI N, REN H. A genetic algorithm for multiprocessor scheduling ［J］. IEEE Transactions on Parallel and Distributed Systems, 1994, 5 (2): 113-120.
［8］	TAURA K, CHIEN A A. A heuristic algorithm for mapping communicating tasks on heterogeneous resources ［C］// HCW '00: Proceedings of the 9th Heterogeneous Computing Workshop. Washington, DC: IEEE Computer Society, 2000: 102-115.
［9］	WINTER P, ZACHARIASEN M. Euclidean Steiner minimum trees: an improved exact algorithm ［J］. Networks, 1997, 30(3): 149-166.
［10］	GANLEY J L. Computing optimal rectilinear Steiner trees: a survey and experimental evaluation ［J］. Discrete APPI Mathematics, 1999, 90(1/2/3): 161-171.
［11］	KARP R M. Reducibility among combinatorial problems ［M］// Complexity of Computer Computations. New York: Plenum Press, 1972: 85-103.
［12］	MELZAK Z A. On the problem of Steiner ［J］. Canadian Mathematical Bulletin, 1961, 4(2): 143-148.
［13］	PRFER H. Neuer beweis eines satzes über permutationen ［J］. Archiv der Mathematik und Physik, 1918, 27: 142-144.
［14］	LUAN W. Multi-objective GA for the Steiner tree problem ［D］. Shenyang: Northeastern University, 2008. (栾威.基于多目标遗传算法求解Steiner树问题［D］.沈阳:东北大学,2008.)