基于蚁群算法的异构数据集成动态调度优化研究
|
摘要
随着计算机和网络技术的加速发展,各种数据以不同的形式存储在不同的系统中,呈分布异构状态。而越来越多的用户希望能够透明地获取和处理这些海量信息源中有用的数据,这也是数据集成系统研究一直是相关领域一个非常热门话题的主要原因。异构信息集成系统的目的是通过集成各种可用资源建立一个复杂的信息系统,屏蔽现在已有的各种异构数据管理系统不同的访问方法和用户界面,给用户提供一个访问多种异构数据源的公共接口,建立一个集成处理多种数据源、整合多个数据查询结果的信息交互处理平台。
本文重点研究的异构数据集成系统动态调度优化机制是在数据源的自主性以及数据量不断增加而严重影响系统性能下提出的。以往提出的调度优化机制大多受数据源自主性以及网络的传输速度的影响,所以对系统中大量返回结果提供一种快速而有效的调度机制是当务之急。
蚁群算法是一种基于启发式的仿生进化算法。已经在若干领域,特别是组合优化问题中获得了成功的应用。如:TSP、QAP(quadratic assignmentproblem)、job-shop调度等,易于与其它方法结合,其有较强的鲁棒性和自组织性。本文在阅读了大量相关论文基础上提出了一种基于蚁群算法的异构数据集成动态调度优化机制,同时引入了物化策略和分域求解策略。这三者的结合有效地解决了初始化延迟、数据的突发性以及慢传输速率问题,可以独立于系统的其它模块和数据源而自行调度。
最后,通过与本文介绍的静态调度优化算法(MST-SO)和一种基于统计推理(Statistical Reasoning)的动态调度优化算法(SR-DD)进行算法性能比较得出,基于蚁群算法的异构数据集成动态调度优化算法ACDSA性能上优异前两者。
Accelerates along with the computer and the networking to develop, each kind of data saves by the different form in the different system, assumes the distributed heterogeneous state. More and more people want to gain and process the useful information among each massive information sources and different information sources in transparently, it is also the research on data integration system was always the primary cause of very hot topic of discussion in related domain. The aim of HIIS (heterogeneous information integrative system) is establish a complex information system by making use of available information sources, shield most of the differences of existing access methods and user interfaces of each heterogeneous data management systems. It also provides to the user an information interoperating platform as a common interface to access multiple heterogeneous data sources, integrate managing and combine the intermediate query results from these sources.
Heterogeneous data integration dynamic scheduling optimization mechanism is the important of this paper research, it is proposes that autonomous data sources as well as the data quantity increase unceasingly had serious influence system performance.the scheduling optimization mechanism being put out before was affect by autonomous data sources and the rate of the network transmission. Design a fast and effective scheduling mechanism for the return results of the system is urgent affairs.
Ant colony algorithm is a kind of biological evolution algorithm based on the heuristic.it was get the successful application in some domains, specially in the question of the Combinatorial optimization, for example, TSP、QAP and job-shop and so on, and also be easy to unite the other methods, having strong robust. After reading lots of the related paper of data scheduling, this paper propose a mechanism of heterogeneous data integration dynamic scheduling optimization based on ant colony algorithm,at the same time import MS and DS. the three aspect combine effectively that solve the issue of initialize delay、outburst of the data and slowly transmission rate, and scheduling by itself independence the other mode and data sources of the system.
Finally, compared with a MST-TO and SR-DO, we are obtain the result that the algorithm performance of the heterogeneous data integration dynamic scheduling optimization based on ant colony algorithm more than front two.
本文重点研究的异构数据集成系统动态调度优化机制是在数据源的自主性以及数据量不断增加而严重影响系统性能下提出的。以往提出的调度优化机制大多受数据源自主性以及网络的传输速度的影响,所以对系统中大量返回结果提供一种快速而有效的调度机制是当务之急。
蚁群算法是一种基于启发式的仿生进化算法。已经在若干领域,特别是组合优化问题中获得了成功的应用。如:TSP、QAP(quadratic assignmentproblem)、job-shop调度等,易于与其它方法结合,其有较强的鲁棒性和自组织性。本文在阅读了大量相关论文基础上提出了一种基于蚁群算法的异构数据集成动态调度优化机制,同时引入了物化策略和分域求解策略。这三者的结合有效地解决了初始化延迟、数据的突发性以及慢传输速率问题,可以独立于系统的其它模块和数据源而自行调度。
最后,通过与本文介绍的静态调度优化算法(MST-SO)和一种基于统计推理(Statistical Reasoning)的动态调度优化算法(SR-DD)进行算法性能比较得出,基于蚁群算法的异构数据集成动态调度优化算法ACDSA性能上优异前两者。
Accelerates along with the computer and the networking to develop, each kind of data saves by the different form in the different system, assumes the distributed heterogeneous state. More and more people want to gain and process the useful information among each massive information sources and different information sources in transparently, it is also the research on data integration system was always the primary cause of very hot topic of discussion in related domain. The aim of HIIS (heterogeneous information integrative system) is establish a complex information system by making use of available information sources, shield most of the differences of existing access methods and user interfaces of each heterogeneous data management systems. It also provides to the user an information interoperating platform as a common interface to access multiple heterogeneous data sources, integrate managing and combine the intermediate query results from these sources.
Heterogeneous data integration dynamic scheduling optimization mechanism is the important of this paper research, it is proposes that autonomous data sources as well as the data quantity increase unceasingly had serious influence system performance.the scheduling optimization mechanism being put out before was affect by autonomous data sources and the rate of the network transmission. Design a fast and effective scheduling mechanism for the return results of the system is urgent affairs.
Ant colony algorithm is a kind of biological evolution algorithm based on the heuristic.it was get the successful application in some domains, specially in the question of the Combinatorial optimization, for example, TSP、QAP and job-shop and so on, and also be easy to unite the other methods, having strong robust. After reading lots of the related paper of data scheduling, this paper propose a mechanism of heterogeneous data integration dynamic scheduling optimization based on ant colony algorithm,at the same time import MS and DS. the three aspect combine effectively that solve the issue of initialize delay、outburst of the data and slowly transmission rate, and scheduling by itself independence the other mode and data sources of the system.
Finally, compared with a MST-TO and SR-DO, we are obtain the result that the algorithm performance of the heterogeneous data integration dynamic scheduling optimization based on ant colony algorithm more than front two.
引文
[1]熊海灵,伍胜,余建桥,异构数据源的集成与访问,计算机科学,2003,30(5):183-184
[2]李贺,张东锋,王江,基于信息资源整合的企业异构数据源集成研究,Library and Information Service.2007.9,51(9):55-57,116
[3]高明,宋瀚涛,异构数据源集成应用模型及其查询处理方法,计算机工程,2003.9,29(15):91-92,150
[4]M.Conti,M.Kumar,S.K.Das etc,Quality of Service Issues in Internet Web Services,IEEE Transactions on Computers,2002,51(6):593-594
[5]David Matthews,Phil Collier,Assessing the Value of a C4ISREW System-of-Systems Capability,In Proceedings of the 5th International Command and Control Research and Technology Symposium(ICCRTS2000),2000:1-18
[6]Michael Stonebraker,Paul M.Aoki,Witold Litwin etc,Mariposa:A Wide-Area Distributed Database System,The VLDB Journal,1996,5(1):48-63
[7]R.J.Miller,M.A.Hernández,L.M.Haas etc,The Clio Project:Managing Heterogeneity,ACM SIGMOD Record,2001,30(1):78-83
[8]Frank P.Coyle,Legacy Integration-Changing Perspectives,IEEE Software,2000,17(2):37-41
[9]Donald Kossmann,The State of the Art in Distributed Query Processing.ACM Computing Surveys,2000,32(4):422-469
[10]Y.Breitbart,H.Garcia-Molina,A.Silberschatz,Overview of Multidatabase Transaction Management,The VLDB Journal,1992,1(2):181-239
[11]Saltor F,Castellanos M,Garcia-Solaco M,Suitability of Data Models as Canonical Models for Federated Databases,ACM SIGMOD Record,1991,20(4):44-48
[12]Y.Yamada,N.Craswell,S.T.Nakatoh,Testbed for Information Extraction from DeepWeb.In Proceedings of the 13th International World Wide Web Conference(WWW 2004),New York,2004:346-347
[13]Zhiyuan Chen,Chen Li,Jian Pei etc,Recent Progress on Selected Topics in Database Research,Journal of Computer Science&Technology,2003,18(5):538-552
[14]A.Bouguettaya,B.Benatallah,A.Elmagarmid,An Overview of Multidatabase Systems:Past and Present,In:A.Elmagarmid,M.Rusinkiewicz,A.Sheth(ed.).Management of Heterogeneous and Autonomous Database Systems.San Francisco:Morgan Kaufmann Publishers,1999:1-32
[15]高曙,郑德,一种基于蚁群算法的任务调度方法,软件时空,2007,2:191-192,252
[16]E.Bonabeau,M.Dorigo,Inspiration for optimization from social insect behavior,Nature,2000,406(6):39-42
[17]T.Kaji,Approach by ant tabu agents for traveling salesman problem,Proceedings of IEEE International Conference on Systems,Man and Cybemetics,2001.5:3429-3434
[18]Y.Gajpal,C.Raj endran,An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops,International Journal of Production Economics,2006,101(2):259-272
[19]C.J.Liao,H.C.Juan,An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups,Computers and Operations Research,2007,34(7):1899-1909
[20]王海星,王德占,申金升,蚁群算法解决有时间窗的车辆优化调度问题研究,Logistics Technlolgy,2006,11:37-40
[21]W.D.Lin,T.X.Cai,Ant colony optimization for VRP and Mail Delivery Problems,IEEE International Conference on Industrial Informatics,2006:1143-1148
[22]S.H.Atm,S.G..Lee,T.C.Chung,Modified ant colony system for coloring graphs,Proceedings of the 2003 Joint Conference of the Fourth International Conference on Information Communications and Signal Processing and the Fourth Pacific Rim Conference on Multimedia,2003.3:1849-1853
[23]吕勇,赵光宙,苏凡军,基于蚁群算法的自适应动态路由算法.浙江大学学报(工学版),2005.10,39(10):1537-1540
[24]K.M.Sim,W.H.Sun,Multiple ant-colony optimization for network routing,Proceedings of the First International Symposium on Cyber Worlds,2002:277-281
[25]M.Dorigo,T.Stutzle,Ant Colony Optimization,MIT Press,Cambridge,MA,2004
[26]M.Dorigo,V.Maniezzo,A.Colomi,The ant system:Optimization by a colony of cooperating agents,IEEE Transactions on Systems,Man,and Cybernetics Part B,1996,26(1):29-41,15
[27]A.Coloni,M.Dorigo,V.aniezzo etc,Ant system for job-shop scheduling,Belgian Journal of Operation Research,Statistics and Computer Science(JORBEL),1994,34:39-53
[28]L.Amsaleg,M.J.Franklin,A.Tomasic,Dynamic Query Operator Scheduling for Wide-Area Remote Access,Journal of Distributed and Parallel Databases,1998.7,6(3):217-246
[29]T.Urhan,M.J.Franklin,L.Amsaleg,Cost Based Query Scrambling for Initial Delays,ACM SIGMOD Int.Conf.on Management of Data,1998:130-141
[30]杨宏英,林长松,异构数据集成系统的应用模式与技术实现,微电子学与计算机,2006,23(8):70-72
[31]Loana Manolescu,Daniela Florescu,Donald Kossmann,Answeing XML Queries over Heterogeneous Data Sources,VLDB,2001:4-20
[32]李军怀,周明全,耿国华 等,XML在异构数据集成中的应用研究,计算机应用,2002.9,22(9):10-12
[33]Z.Ives,D.Florescu,M.Friedman ete,An Adaptive Query Execution System for Data Integration,ACM SIGMOD Int.Conf.on Management of Data,1999:299-310
[34]L.Bouganim,EFabret,C.Mohan etc,A Dynamic Query Processing Architecture for Data Integration Systems,IEEE Data Engineering Bulletin,2000,23(2):42-48
[35]Luc Bouganim,Francoise Fabret,Patrick Valduriez etc,Dynamic Query Scheduling in Data Integration Systems,Proc.of Int.Conf.on Data Engineering(ICDE),2000:425-434
[36]李瑞轩,卢正鼎,吴炜等,一种异构数据集成中的动态查询优化方法,计算机工程与科学,2004,12:71-74,81
[37]肖卫军,吴炜,卢正鼎等,多数据库系统中查询分解算法的研究,小型微型计算机系统,2001,22(4):488-491
[38]甄玉钢,刘璐莹,康建初,基于XML的异构数据库集成系统构架与开发,计算机工程,2006.1,32(2):85-87
[39]孔祥疆,马玉鹏,李英凡,异构数据库中的数据类型转换,计算机应用研究,2006,4:217-218,221
[40]A.M.Ayad,J.ENaughton,Static Optimization of Conjunctive Queries with Sliding Windows over Infinite Streams,In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data(SIGMOD 2004),Paris,France,2004:419-430
[41]K.L.Tan,P.K.Eng,B.C.Ooi etc,Join and Multi-join Processing in Data Integration Systems,Data&Knowledge Engineering,2002,40(2):217-239
[42]J.EDittrich,B.Seeger,D.S.Taylor etc,On Producing Join Results Early,in Proceedings of the 22rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2003),San Diego,California,2003:134-142
[43]H.Paques,L.Liu,C.Pu,Distributed Query Adaptation and its Trade-offs,In Proceedings of the 2003 ACM Symposium on Applied Computing,Melbourne,Florida,2003:528-535
[44]朱庆保,杨志军,基于变异和动态信息素更新的蚁群优化算法,软件学报,2004,15(2):185-192
[45]刘玉华,滕玮,基于蚁群算法的车辆调度问题研究,硕士学位论文,武汉,华中师范大学,2006:38-39
[46]Ming-ChuanHung*,Man Lin Huang,Don-Lin Yang etc,Efficient approaches for materialized views selection in a data warehouse,Information Sciences 177(2007):1333-1348
[47]王云峰,张祖平,数据仓库中物化视图的选取策略.计算技术与自动化,2004.9,23(3):43-45
[48]吴斌,史忠植,一种基于蚁群算法的TSP问题分段求解算法,计算机学报,2001.12,24(12):1328-1333
[49]王宏宇,顾冠群,集成服务网络中的分组调度算法研究综述,计算机报,1999.10,22(10):1090-1099
[50]祝崇隽,刘民,吴澄 等,针对模糊需求的VRP的两种2-OPT 算法,电子学报,2001,29(8):1035-1037
[51]祝崇隽,刘民,吴澄等,针对CVRP的2-OPT算法的时间复杂度均值分析,清华大学学报(自然科学版),2002,42(9):1218-1221
[52]周刚,郭建胜,基于本体的异构数据集成系统分析与设计,计算机工程,2007.10,33(19):273-275
[53]吴孟泉,宋晓东,崔伟宏,基于本体的异构空间数据的集成研究,武汉大学学报,2007.10,32(10):915-918
[2]李贺,张东锋,王江,基于信息资源整合的企业异构数据源集成研究,Library and Information Service.2007.9,51(9):55-57,116
[3]高明,宋瀚涛,异构数据源集成应用模型及其查询处理方法,计算机工程,2003.9,29(15):91-92,150
[4]M.Conti,M.Kumar,S.K.Das etc,Quality of Service Issues in Internet Web Services,IEEE Transactions on Computers,2002,51(6):593-594
[5]David Matthews,Phil Collier,Assessing the Value of a C4ISREW System-of-Systems Capability,In Proceedings of the 5th International Command and Control Research and Technology Symposium(ICCRTS2000),2000:1-18
[6]Michael Stonebraker,Paul M.Aoki,Witold Litwin etc,Mariposa:A Wide-Area Distributed Database System,The VLDB Journal,1996,5(1):48-63
[7]R.J.Miller,M.A.Hernández,L.M.Haas etc,The Clio Project:Managing Heterogeneity,ACM SIGMOD Record,2001,30(1):78-83
[8]Frank P.Coyle,Legacy Integration-Changing Perspectives,IEEE Software,2000,17(2):37-41
[9]Donald Kossmann,The State of the Art in Distributed Query Processing.ACM Computing Surveys,2000,32(4):422-469
[10]Y.Breitbart,H.Garcia-Molina,A.Silberschatz,Overview of Multidatabase Transaction Management,The VLDB Journal,1992,1(2):181-239
[11]Saltor F,Castellanos M,Garcia-Solaco M,Suitability of Data Models as Canonical Models for Federated Databases,ACM SIGMOD Record,1991,20(4):44-48
[12]Y.Yamada,N.Craswell,S.T.Nakatoh,Testbed for Information Extraction from DeepWeb.In Proceedings of the 13th International World Wide Web Conference(WWW 2004),New York,2004:346-347
[13]Zhiyuan Chen,Chen Li,Jian Pei etc,Recent Progress on Selected Topics in Database Research,Journal of Computer Science&Technology,2003,18(5):538-552
[14]A.Bouguettaya,B.Benatallah,A.Elmagarmid,An Overview of Multidatabase Systems:Past and Present,In:A.Elmagarmid,M.Rusinkiewicz,A.Sheth(ed.).Management of Heterogeneous and Autonomous Database Systems.San Francisco:Morgan Kaufmann Publishers,1999:1-32
[15]高曙,郑德,一种基于蚁群算法的任务调度方法,软件时空,2007,2:191-192,252
[16]E.Bonabeau,M.Dorigo,Inspiration for optimization from social insect behavior,Nature,2000,406(6):39-42
[17]T.Kaji,Approach by ant tabu agents for traveling salesman problem,Proceedings of IEEE International Conference on Systems,Man and Cybemetics,2001.5:3429-3434
[18]Y.Gajpal,C.Raj endran,An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops,International Journal of Production Economics,2006,101(2):259-272
[19]C.J.Liao,H.C.Juan,An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups,Computers and Operations Research,2007,34(7):1899-1909
[20]王海星,王德占,申金升,蚁群算法解决有时间窗的车辆优化调度问题研究,Logistics Technlolgy,2006,11:37-40
[21]W.D.Lin,T.X.Cai,Ant colony optimization for VRP and Mail Delivery Problems,IEEE International Conference on Industrial Informatics,2006:1143-1148
[22]S.H.Atm,S.G..Lee,T.C.Chung,Modified ant colony system for coloring graphs,Proceedings of the 2003 Joint Conference of the Fourth International Conference on Information Communications and Signal Processing and the Fourth Pacific Rim Conference on Multimedia,2003.3:1849-1853
[23]吕勇,赵光宙,苏凡军,基于蚁群算法的自适应动态路由算法.浙江大学学报(工学版),2005.10,39(10):1537-1540
[24]K.M.Sim,W.H.Sun,Multiple ant-colony optimization for network routing,Proceedings of the First International Symposium on Cyber Worlds,2002:277-281
[25]M.Dorigo,T.Stutzle,Ant Colony Optimization,MIT Press,Cambridge,MA,2004
[26]M.Dorigo,V.Maniezzo,A.Colomi,The ant system:Optimization by a colony of cooperating agents,IEEE Transactions on Systems,Man,and Cybernetics Part B,1996,26(1):29-41,15
[27]A.Coloni,M.Dorigo,V.aniezzo etc,Ant system for job-shop scheduling,Belgian Journal of Operation Research,Statistics and Computer Science(JORBEL),1994,34:39-53
[28]L.Amsaleg,M.J.Franklin,A.Tomasic,Dynamic Query Operator Scheduling for Wide-Area Remote Access,Journal of Distributed and Parallel Databases,1998.7,6(3):217-246
[29]T.Urhan,M.J.Franklin,L.Amsaleg,Cost Based Query Scrambling for Initial Delays,ACM SIGMOD Int.Conf.on Management of Data,1998:130-141
[30]杨宏英,林长松,异构数据集成系统的应用模式与技术实现,微电子学与计算机,2006,23(8):70-72
[31]Loana Manolescu,Daniela Florescu,Donald Kossmann,Answeing XML Queries over Heterogeneous Data Sources,VLDB,2001:4-20
[32]李军怀,周明全,耿国华 等,XML在异构数据集成中的应用研究,计算机应用,2002.9,22(9):10-12
[33]Z.Ives,D.Florescu,M.Friedman ete,An Adaptive Query Execution System for Data Integration,ACM SIGMOD Int.Conf.on Management of Data,1999:299-310
[34]L.Bouganim,EFabret,C.Mohan etc,A Dynamic Query Processing Architecture for Data Integration Systems,IEEE Data Engineering Bulletin,2000,23(2):42-48
[35]Luc Bouganim,Francoise Fabret,Patrick Valduriez etc,Dynamic Query Scheduling in Data Integration Systems,Proc.of Int.Conf.on Data Engineering(ICDE),2000:425-434
[36]李瑞轩,卢正鼎,吴炜等,一种异构数据集成中的动态查询优化方法,计算机工程与科学,2004,12:71-74,81
[37]肖卫军,吴炜,卢正鼎等,多数据库系统中查询分解算法的研究,小型微型计算机系统,2001,22(4):488-491
[38]甄玉钢,刘璐莹,康建初,基于XML的异构数据库集成系统构架与开发,计算机工程,2006.1,32(2):85-87
[39]孔祥疆,马玉鹏,李英凡,异构数据库中的数据类型转换,计算机应用研究,2006,4:217-218,221
[40]A.M.Ayad,J.ENaughton,Static Optimization of Conjunctive Queries with Sliding Windows over Infinite Streams,In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data(SIGMOD 2004),Paris,France,2004:419-430
[41]K.L.Tan,P.K.Eng,B.C.Ooi etc,Join and Multi-join Processing in Data Integration Systems,Data&Knowledge Engineering,2002,40(2):217-239
[42]J.EDittrich,B.Seeger,D.S.Taylor etc,On Producing Join Results Early,in Proceedings of the 22rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2003),San Diego,California,2003:134-142
[43]H.Paques,L.Liu,C.Pu,Distributed Query Adaptation and its Trade-offs,In Proceedings of the 2003 ACM Symposium on Applied Computing,Melbourne,Florida,2003:528-535
[44]朱庆保,杨志军,基于变异和动态信息素更新的蚁群优化算法,软件学报,2004,15(2):185-192
[45]刘玉华,滕玮,基于蚁群算法的车辆调度问题研究,硕士学位论文,武汉,华中师范大学,2006:38-39
[46]Ming-ChuanHung*,Man Lin Huang,Don-Lin Yang etc,Efficient approaches for materialized views selection in a data warehouse,Information Sciences 177(2007):1333-1348
[47]王云峰,张祖平,数据仓库中物化视图的选取策略.计算技术与自动化,2004.9,23(3):43-45
[48]吴斌,史忠植,一种基于蚁群算法的TSP问题分段求解算法,计算机学报,2001.12,24(12):1328-1333
[49]王宏宇,顾冠群,集成服务网络中的分组调度算法研究综述,计算机报,1999.10,22(10):1090-1099
[50]祝崇隽,刘民,吴澄 等,针对模糊需求的VRP的两种2-OPT 算法,电子学报,2001,29(8):1035-1037
[51]祝崇隽,刘民,吴澄等,针对CVRP的2-OPT算法的时间复杂度均值分析,清华大学学报(自然科学版),2002,42(9):1218-1221
[52]周刚,郭建胜,基于本体的异构数据集成系统分析与设计,计算机工程,2007.10,33(19):273-275
[53]吴孟泉,宋晓东,崔伟宏,基于本体的异构空间数据的集成研究,武汉大学学报,2007.10,32(10):915-918