臺灣博碩士論文加值系統

今天大部分的網際網路主要是架構在以光纖為主幹上，以作為來源(Source)端和目的地(Destination)端中間的傳輸媒介，由於每條光纖可以提供巨大的頻寬網路，因此出現很多新的通訊應用，例如: 分散式系統、線上影音服務……等，由於這些應用服務提供大量的使用者需求，同時也需考慮穩定的服務品質(guality of service, QoS)需求，這類的服務品質需求包含:延遲(delay)、頻寬保證(bandwidth)、封包遺失(packet loss)......等。使得這類型的網路服務，產生了服務品質限制下的群播繞送路徑(multicast routing)問題。在目前群播撓送路徑問題，由於計算在服務品質限制下最小成本群播繞送樹是一個NP-complete問題，因此本論文提出一個建立在延遲為基礎下的群播繞送的GFLS方法，這個GFLS方法代表的是基因演算法(genetic algorithm)與糢糊選擇(fuzzy selection)和區域搜尋(local search)的結合。我們主要是希望透過GFLS，找到一個延遲限制下的最小成本的群播繞送樹，以滿足使用者需求。經由實驗模擬結果證明GFLS方法，將可以有效解決QoS下限制的多重路徑的問題

Most of network based on Fiber constructed as a middle-ware from a source node to destination nodes, the fiber supplies a huge of high-speed network. Therefore, many of new communication applications have emerged, such as distribution systems, on-line video-services, and some other applications. These services must ensure stable QoS (Quality of Service) and provide acceptable link costs, time delay, bandwidth, and packet loss constraints, essentially a multicast routing problem. In multicast routing problems, to construct the least-cost multicast routing tree under QoS constraints is an NP-complete problem. In this thesis, we propose a genetic algorithm using fuzzy selection with local search (GFLS) method to meet the problem of QoS under delay constraints. We use GFLS algorithm to find a multicast tree with minimum cost under delay constraints. The simulation results demonstrate that the GFLS can efficiently solve a multicast routing problem under QoS constraints

Table of Contents
中文摘要 I
Abstract II
誌謝 III
Chapter 1 Introduction 1
1.1 The motivation 1
1.2 The research purpose 3
1.3 The research framework 4
Chapter 2 Relative Research 5
2.1 The multicast routing problem 5
2.2 Relative research 7
2.2.1 The research of ANN for CMST 7
2.2.2 The research of heuristic algorithm for CMST 9
2.2.3The research of meta-heuristic algorithm for CMST 10
2.2.3.1 Genetic algorithm 10
2.2.3.2 Meta-heuristic algorithm 15
Chapter 3 Research Schem and Framework 19
3.1 Problem description and formulation 19
3.2 GFLS base algorithm framework 21
3.3 GFLS 25
3.3.1 Chromosomes encoding 25
3.3.2 Initialization population 27
3.3.3 Evaluate fitness 28
3.3.4 Genetic algorithm operator 28
3.3.4.1 Fuzzy selection 29
3.3.4.2 Crossover 34
3.3.4.3 Mutation 34
3.3.5 Local search 35
3.3.6 Check and repair operation 38
Chapter 4 Experiment Results 39
4.1 The cost of multicast tree 40
4.2 The convergence process 42
4.3 Running time 44
Chapter 5 Conclusions and Future works 45
Bibliography 46

Bibliography
[1]Y. Leung, G. Li, and Z. B. Xu (1998), “A Genetic Algorithm for the Multiple Destination Routing Problems,” IEEE Transactions on Evolutionary computation, Vol. 2, pp.150-161.
[2]H. F. Salama, D. S. Reeves, and Y. Viniotis (1997), “Evaluation of Multicast Routing Algorithms for Real-Time Communication on High-Speed Networks,” IEEE Journal on Selected Areas in Communications, Vol. 25, No. 3, pp.332-345.
[3]D. Bertsekas and R. G. Gallager (1992), Data Networks, 2nd ed, Englewood Cliffs, NJ: Prentice-Hall.
[4]S. L. Hakimi (1971), “Steiner’s Problem in Graphs and Its Implications,” Networks 1, Vol. 1, No. 1, pp. 113-133.
[5]R. M. Karp (1972), “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, pp. 85-103.
[6]C. Pornavalai, G. Chakraborty, and N. Shiratori (1995), “ A Neural Network Approach to Multicast Routing in Real-Time Communication Network,” in Proceedings of IEEE International Conference on Network Protocols, pp. 332-339.
[7]N. Shimamoto, A. Hiamatsu, and K. Yamasaki (1993), “A Dynamic Routing Control Based on A Genetic Algorithm,” in Proceedings of IEEE International Conference on Neural Network, pp. 1123-1128.
[8]R. H. Hwang, W. Y. Do, and S. C. Yang (2000), “Multicast Routing Based on Genetic Algorithms,” Journal of Information Science and Engineering, Vol. 16, pp. 885-901.
[9]V. J. R. Smith and A Clare (1986), “On Finding Steiner Vertices,” Networks, Vol. 16, pp. 283-294.
[10]Z. Qingfu and Y. W. Leung (1999), Senior Member, “A Orthogonal Genetic Algorithm for Multimedia Multicast Routing,” IEEE Transactions on Evolutionary Computation, Vol.3, No 1, pp. 53-62.
[11]A. T. Haghighat, K. Faez, M. Dehghan, A. Mowlaei, and Y. Ghanhremani (2003), “GA-Based Heuristic Algorithms for QoS Based Multicast Routing,” Knowledge-Based System 16, pp. 305-312.
[12]A. T. Haghighat, K. Faez, M. Dehghan, A Mowlaei, and Y. Ghanhremani (2004), “Genetic Algorithm-Based Heuristic Algorithms for Bandwidth-Delay-Constrained Least-Cost Multicast Routing,” Computer Communications 27, pp. 111-127.
[13]C. P. Raviuman and R. Bajpai (1998), “Source-Based Delay-Bounded Multicasting in Multimedia Networks,” Computer Communications 21, pp. 126-132.
[14]J. Holland (1975), Adaptation in Neural and Artificial Systems, University of Michigan Press.
[15]Z. Wang, B. Shi, and E. Zhao (2001), “Bandwidth-Delay-Constrained Least-Cost Multicast Routing Based on Heuristic Genetic Algorithm,” Computer Communications 24, Vol. 24, pp. 685-692.
[16]P. Chen and T. l. Dong (2003), “A Fuzzy Genetic Algorithm for QoS Multicast Routing, ” Computer Communications 26, pp. 506-512.
[17]M. Dorigo (1997), “Ant Colony System A Cooperative Learning Approach to The Traveling Salesman Problem,” IEEE Transaction on Evolutionary Computation, Vol. 1, pp. 53-66.
[18]F. Xiang, L. Junzhoou, and W. Jieyi, G. Guanqun (1999), “QoS Routing Based on Genetic Algorithm,” Computer Communications 22, pp. 1394-1399.
[19]Y. W. Yuan, H. H. Zhan, and L. M. Yan (2003), “An Adaptive Qos Route Selection Algorithm Based on Genetic Approach in Combination with Neural Network,” Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xi’an, pp. 1808-18132-5.
[20]E. Gelebe (1997), Fellow, IEEE, A. Ghanwani, and V. Srinivasan, “Improved Neural Heuristics for Multicast Routing,” IEEE Journal on Selected Area in Communications, Vol. 15, No. 2, pp. 147-155.
[21]Q. Zhu, M. Parsa, and J. J. Garacia-Luna-Aceves (1995), “A Source-Based Algorithm for Delay-Constrained Minmum-Cost Multicasting,” In Proceeding of IEEE INFORCOM’95, pp.337-385.
[22]V. P. Kompella, J. C. Pasquale, and G. C. Polyzos (1992), “Multicasting for Multimedia Applications, ” In Proceeding IEEE INFORCOM’92, pp. 2078-2085.
[23]R. Widyono (1994), “The Design and Evaluation of Routing Algorithms for Real-time Channels,” International Computer Science Institute, University of California at Berkeley, Tech, Rep. ICSI TR-94-024.
[24]A. G. Waters (1994), “A New Heuristic for ATM Multicast Routing,” In Proc Second IFIP Workshop Performance Modeling Evaluation ATM Networks, pp.8.1-8.9.
[25]Q. Sun and H. Langendoerfer (1995), “Efficient Multicasting Routing for Delay-Sensitive Applications,” In Proceeding of Second Workshop Protocols Multimedia Systme(PROMS’95), 1995.
[26]J. H. Holland (1992), Adaption in Natural and Artificial System, Boston, MA: MIT Press.
[27]P. Winter (1987), “Steiner Problem in Networks : A Survey, ” IEEE Network, Vol. 17, No. 2, pp. 128-167.
[28]M. R. GAREY and D. S. Johnson (1998), Computers and Intractability a Guide to The Theory of NP-completeness, Freeman, New York.
[29]M. Mitchell (1996), An Introduction to Genetic Algorithms Cambridge, MA: MIT Press.
[30]J. Hopfield, J., and D. Tank (1958), “Neural Computations of Decisions In Optimization Problems,” Cybernetics, Vol. 51, pp. 141-152.
[31]F. Glover (1997), “Heuristic for Integer Programming Using Surrogate Constraints,” Decision Science, Vol. 8, pp. 156-166.
[32]F. Glover (1989), “Tabu Search-Part I,” ORSA Journal of Computing, Vol. 1, No. 3, pp. 190-206.
[33]F. Glover (1986), “Future Paths for Integer Programming and Links to Artificial Intelligence,” Computer and Operations Research, Vol. 13, No. 5, pp. 533-549.
[34]C. F. Tsai, C. W. Tsai, and C. P. Chen (2004), “A Novel Algorithm for Multimedia Multicast Routing in A Large Scale Network,” The Journal of Systems and software 72, pp.431-441.
[35]葉怡成 (2003)，”類神經網路模式應用與實作，”儒林出版社, 第 12-2 – 12-3頁.
[36]蔡崇煒 (2001)，多重搜尋基因演算法: 一個新的有效解決通訊網路及資料庫中複雜問題之方法，”碩士論文，屏東科技大學資訊管理系，屏東。
[37]呂紹瑩 (2002)，服務品質保證下群找群播路由之研究，碩士論文，中正大學資訊管理系，嘉義。
[38]http://ganley.org/steiner/intro.html.