用户名: 密码: 验证码:
基于复杂网络理论的多约束QoS组播路由技术研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
复杂网络的研究,为我们提供了一种复杂性研究的新视角、新方法,其研究涉及到人类生活的方方面面,然而将复杂网络理论用于QoS组播路由及算法,对这方面的研究国内外的学者们还处于理论探索阶段,到目前为止,还没有比较成熟的研究成果。论文在前人研究基础之上,围绕多约束QoS组播路由问题进行研究,其成果可概括如下。
     运用复杂网络理论对多约束QoS组播路由问题模型进行新的诠释并将其用于QoS组播路由问题求解,构造满足多个约束条件的最小代价组播树,实现不同业务对时延、时延抖动、丢包率和带宽等不同约束的性能需求,从而达到节省网络带宽资源、降低网络负载、减少拥塞和提高服务质量的目的。根据复杂网络中小世界特性和BA无标度网络中的择优增长特性,提出一种基于综合学习和智能协同的改进粒子群优化算法(PSO-CLIC)。在生成的网络模型上对算法的组播树费用、时延和时延抖动等指标进行仿真,仿真结果表明该算法是可行的、有效的且在收敛速度和求解精度等方面具有明显的优势。
     为使组播树的建立更加有效、精确,本文利用代理技术实现对路由器资源的监测,并以VC6.0为开发平台,设计开发了路由器资源监测Agent。该软件可以有效的监测路由器资源信息,实时、动态地收集网络数据,不仅能够有效地解决多约束QoS组播路由问题、满足认知网络对资源的需求,而且也能为用户其它服务提供数据支持。数据传输采用Push与Pull相结合的方式,一方面提高了数据传输的有效性和可靠性,另一方面也减少了网络资源的消耗。
The study of complex networks provides us with new perspective, new methods for complexity research, it is related to all aspects of human life, however, applying complex networks theory on QoS multicast routing and its algorithm is still in the exploratory stage for domestic and outside scholars, so far, it does not have mature research results. Based on previous researches in this filed, this dissertation studies in depth the problem of multiple constrained QoS multicast routing, the results can be summarized as follows.
     Using complex networks theory on the model of multiple constrained QoS multicast routing problem with a new interpretation and applying the theory on solving QoS multicast routing problem, constructing a minimum cost multicast tree that can satisfy multiple constraints, implementing different constraint performance requirements of different service on delay, delay jitter, packet loss and bandwidth, reaching the goal of saving network bandwidth resource, reduceing network load and improving quality of service. According to the characteristic of small-world network and the preference of growth characteristic of BA scale-free network, the improving algorithm of particle swarm optimization based on comprehensive learning and intelligent cooperation is proposed. Based on generated network model, simulations to the multicast tree cost, delay and delay jitter of PSO-CLIC algorithm are carried, results show that this algorithm has a great advantage on convergence rate and solution accuracy.
     To establish a more effective and precise multicast tree, this paper uses agent technology to monitor the router resources, develops router resource monitoring agent with VC6.0 platform. The software can effectively monitor the router resource information, collect network data with real-time and dynamic, not only can it effectively solve the multiple constrained QoS multicast routing problem, meet the demands for resources of cognitive network, but also it can provide data to support other service. Data transmission uses the method of‘Push and Pull’, on the one hand it can improve the effectiveness and reliability of data transmission, on the other hand it can reduce the consumption of network resources.
引文
[1] Watts D J, Strogatz S H. Collective dynamics of‘small-world’networks[J].Nature.1998,393(6684): 440-442.
    [2] Barabási A, Albert R. Emergence of scaling in random networks[J].Science.1999,286(5439):509-512.
    [3] Newman M E J. Scientific collaboration networks.II.Shortest paths, weighted networks, and centrality[J].Phys Rev E.2001,64(1):16132.
    [4] Jeong H, Mason S P, Barabási A, et al. Lethality and centrality in protein networks[J].Nature.2001,411:41-42.
    [5] Albert R, H J, Barabási A. Diameter of the World Wide Web[J].Nature.1999,401:130-131.
    [6] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology[J].Comput Commun- ication Rev.1999,29:251-263.
    [7]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.
    [8]吴金闪,狄增如.从统计物理学看复杂网络研究[J].物理学进展.2004,24(1):18-46.
    [9] Dorogovtsev S N, Mendes J F F, Samukhin A N. Metric structure of random networks[J].Nuclear Physics B. 2003,653(3):307-338.
    [10] Cohen R, Havlin S. Scale-free networks are ultrasmall[J].Phys. Rev. Lett. 2003,90(5):58701.
    [11] Erd?s P, A R. On random graphs[J].Publicationes Mathematical.1959:290-297.
    [12] Bollobás B. Random Graphs[M].New York:Academic Press,2001.
    [13] Newman M E J, Watts D J. Renormalization group analysis of the small-world network model[J].Phys.Lett.A. 1999,263:341-346.
    [14]刘强,方锦清,李永.探索小世界特性产生的一种新方法[J].复杂系统与复杂性科学.2005,2(2):13-19.
    [15] Kleinberg J M. Navigation in a small world[J].Nature.2000,406:845.
    [16] Xiang L, Guanrong C. A local world evolving network model[J].Physica A. 2003,328(1-2):274-286.
    [17] Yook S H, Jeong H, Barabási A. Weighted evolving networks[J].Phys.Rev.Lett. 2001,86(25):5835-5838.
    [18] Yan G, Zhou T, Hu B, et al. Efficient Routing on Complex Networks[J].Phys. Rev. E. 2006,73:46108.
    [19] Wen-Xuwang, Bing-Hongwang, Chuan-Yangyin, et al. Traffic dynamcis based on local routing protocol on scale-free networks[J].Phys. Rev. E. 2006,73:26111.
    [20] Yin C, Wang B, Wang W, et al. Efficient routing on scale-free networks based on local information[J].Phys. Lett. A. 2006,351:220-224.
    [21] Han Z, Ming L, Li F. Local routing strategy for scale-free networks based on degree-load joint preference[J]. Journal of University of Shanghai for Science and Technology.2008,30(3):264-270.
    [22] Chen Z Y, Wang X F. Effects of network structure and routing strategy on network capacity[J].Phys. Rev. E.2006,73:36107.
    [23] Zhang H, Liua Z, Tang M, et al. An adaptive routing strategy for packet delivery in complex networks[J].Phys. Lett. A.2007,364:177-182.
    [24]王先朋.复杂网络上的路由策略研究[D].上海交通大学,2009.
    [25] Theus Hossmann F L T S. From Contacts to Graphs: Pitfalls in Using Complex Network Analysis for DTN Routing[C].Rio de Janeiro,Brazil:IEEE Press Piscataway,2009.
    [26] Zhang Q, Leung Y. An Orthogonal Genetic Algorithm for Multimedia Multicast Routing[J].IEEE Transactions on Evolutionary Computation.1999,3(1):53-62.
    [27]葛连升,江林,秦丰林. QoS组播路由算法研究综述[J].山东大学学报.2010,45(1):55-65.
    [28] Shaikh A, Shin K G. Destination-Driven Routing for Low-Cost Multicast[J].IEEE Journal on Selected Areas in Communications.1997,15(3):373-381.
    [29] W S. High-Speed Networks:TCP/IP and ATM Design Principles[M].Englewood Cliffs:NJ:Prentice Hall,1998.
    [30] Qing Z, Mehrdad P, J G J. A source-based algorithm for delay constrained minimal cost multicasting: Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies(INFOCOM’95)[Z].Washington.DC: IEEE Computer Society,1995:377-384.
    [31] Kou L, Markowsky G, Berman L. A Fast Algorithm for Steiner Trees[J].Acta Information.1981,15(11): 141-145.
    [32] G R N, I B. Multicast routing with end-to-end delay and delay variation constraints[J].IEEE Journal on Selected Area in Communications.1997,15(3):346-356.
    [33] Pirong S, Shantai C. A fast and efficient heuristic algorithm for the delay and delay variation bounded multicast tree problem[J].Computer Communications.2001,25(8):825-833.
    [34] Holland J H. Adaptation in natural and artificial systems[M].Michigan:University of Michigan Press,1975.
    [35] Dorigo M, Maniezzo V, Colorni A. Positive feedback as a search strategy[R].Milan,Italy:Dipartimento di Elettronica,Politecnico di Milano,1991.
    [36] Poli R, Kennedy J, Blackwell T. Particle Swarm Optimization: IEEE International Conference on Neural Networks [Z].Perth,Australia:1995,1942-1948.
    [37] Lipo W, Wen L, Haixiang S. Delay-Constrained Multicast Routing Using the Noisy Chaotic Neural Networks[J].IEEE Transactions on Computers,2009,58(1):82-89.
    [38] Armaghan M, Haghighat A T, Armaghan M. An effective candidate list strategy for Tabu Search based QoS multicast routing[J].17th International Conference on Software,Telecommunications and Computer Networks. 2009:201-205.
    [39] Lin H. Multicast Routing Based on the Simulated Annealing[J].Journal of System Simulation.2009,21(S2): 43-45.
    [40] Proemel H U, Steger A. The Steiner Tree Problem: A Tour Through graphs, Algorithms and Complexity[G]. Vieweg Teubner Verlag,2002.
    [41] Hoang A T, Le V T, Nguyen N G. A Novel Particle Swarm Optimization-Based Algorithm for the Optimal Communication Spanning Tree Problem[J].Second International Conference on Communication Software and Networks.2010:232-236.
    [42] Eberhart, Shi Y. Particle swarm optimization: developments, applications and resources[J]. Proceedings of the 2001 Congress on Evolutionary Computation 2001.2001,1:81-86.
    [43] Jin X, Bai L, Ji Y, et al. Probability Convergence based Particle Swarm Optimization for Multiple Constrained QoS Multicast Routing[J].Fourth International Conference on Semantics,Knowledge and Grid.2008: 412-415.
    [44] Li C, Cao C, Li Y. Hybrid of Genetic Algorithm and Particle Swarm Optimization for Multicast QoS Routing[J].IEEE International Conference on Control and Automation.2007:2355-2359.
    [45]纪震,周家锐,廖惠连,等.智能单粒子优化算法[J].计算机学报.2010,3.
    [46] Yeh W, Lin Y. A Particle Swarm Optimization Approach Based on Monte Carlo Simulation for Solving the Complex Network Reliability Problem[J].IEEE Transactions on Reliability.2010,59(1):212-221.
    [47] Shujun L, Shengli S. An Improved Particle Swarm Optimization Algorithm and its Convergence Analysis[J]. Second International Conference on Computer Modeling and Simulation.2010(2):138-141.
    [48] Yan Y, Jianhua W, Jianfeng Z. Method for Intelligent Decision Making Based Rough Sets and Particle Swarm Optimization[J]. Second International Conference on Computer Modeling and Simulation.2010(4):230-233.
    [49] Liang J J, Qin A K, Suganthan P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation.2006,10(3): 281-295.
    [50] Goudos S K, Moysiadou V. Application of a Comprehensive Learning Particle Swarm Optimizer to Unequally Spaced Linear Array Synthesis With Sidelobe Level Suppression[J].IEEE Antennas and Wireless Propagation Letters.2010,9:125-129.
    [51] Van Den Bergh F, P A. A Cooperative approach to particle swarm optimization[J].IEEE Transactions on Evolutionary Computation.2004,8(3):225-239.
    [52] Lin C, Chen C, Lin C. A Hybrid of Cooperative Particle Swarm Optimization and Cultural Algorithm for Neural Fuzzy Networks and Its Prediction Applications[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews.2009,39(1):55-68.
    [53] M W B. Routing of Multipoint Connections[J].IEEE Journal on Selected Areasin Communications.1988,6(9): 1617-1622.
    [54] Salama H F, Reeves D S, Viniotis Y. Evaluation of multicast routing algorithms for realtime communication onhigh-speed networks[J].IEEE Journal on Selected Areas in Communications.1997,15(3):332-345.
    [55] Thomas R W. Cognitive networks [D].Virginia Polytechnic and State University,2007.
    [56] Mahmoud Q H. Cognitive Networks-Towards Self-Aware Networks[M].Canada: John Wiley and Sons,Ltd, 2007.
    [57] O Othman, Balasubramanian, D S. Performance evaluation of an adaptive middleware load balancing and monitoring service : Proc of the 24th IEEE Intl[Z].2004:135-146.
    [58] Thomas R W. Congnitive networks: adaptation and learning to achieve end-to-end performance objectives[J]. IEEE Communications Magazine.2006:51-57.
    [59] Domingues P, Silva L. DRMonitor -A Distributed Resource Monitoring System: Pro 11th Euromicro Conference on Parallel,Distributed and Network-based Processing[Z].2003,127-133.
    [60] Poladian Vahe,Garlan David,Shaw Mary,et al. Leveraging resource prediction for anticipatory dynamic configuration: First International Conference on Self-Adaptive and Self-Organizing Systems[Z].2007,214-223.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700