(100.26.179.251) 您好!臺灣時間:2021/04/15 17:32
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:王國龍
研究生(外文):Kuo-Lung Wang
論文名稱:利用可調式突變機率基因演算法進行分波多工網路之預設式備份群播樹修復
論文名稱(外文):Optimization of Preplanned Multicast Backup Tree Using Genetic Algorithm with Varying Mutation Probability in WDM Network
指導教授:黃振發黃振發引用關係王億富王億富引用關係
指導教授(外文):Jen-Fa HuangYih-Fuh Wang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:英文
論文頁數:62
中文關鍵詞:修復群播樹基因演算法
外文關鍵詞:genetic algorithmrestorationmulticast tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:89
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:12
  • 收藏至我的研究室書目清單書目收藏:0
運用分波多工(Wavelength-Division Multiplexing, WDM)技術的全光纖網路(All-Optical Network),為廣域網路(Wide Area Network, WANs)應用中最被看好的網路技術之一。分波多工網路中,任意網路節點或線路的破壞,都可能造成整個網路傳輸的困難。為了能維持網路的正常運作,找到最佳的備份群播樹,以解決節點或線路破壞而產生的問題更顯重要。因此,分波多工網路之修復成為一個很重要的課題。而預設式修復為用來保護或修復高速網路最常見的方法之一。基於網路存活性的需要, 本篇論文探討分波多工網路中,預設式備份群播樹修復之機制,並針對此問題提出一些有效的解決方法。
為了有更好的修復成果,我們先利用基因演算法(Genetic Algorithm,GA)-一種基於自然選擇過程的一種最佳化搜尋機制,來追求效能的最佳化。基因演算法已經被廣泛應用於解決複雜的最佳化問題。然而,傳統的基因演算法並非毫無缺點;收斂速度慢及不能保證一定可以收斂到最佳解為基因演算法二項主要缺點,現今已有許多改良式基因演算法來加強執行的效能。
同時考慮母體的多樣性(diversity)及演化時間(evolution time)二者間的關係,我們提出可調式突變機率之壓縮映射基因演算法(Contract Mapping Genetic Algorithm with Varying Mutation Probability, CMGAVaPm )來搜尋最佳備用群播樹。模擬的結果顯示,該演算法不但具有較強的廣域搜索能力,而且能有效避免早熟(premature convergence)的問題。
Optical networks employing wavelength division multiplexing are potential candidates for future wide area networks. Because these networks are prone to component failures and carry a large volume of traffic, maintaining a high level of service availability is an important issue. It is important to find the optimal backup multicast backup tree that can ensure fiber network survivability for maintaining the normal operation of the network.
The preplanned restoration is one of the common methods we considered to protect or restore the network failures. We have presented a new method based upon a GA to find the near optimal preplanned backup multicast trees for the primary multicast trees in WDM network. In this thesis, GA has been employed for solving many complex optimization problems. Although GA is not perfect, i.e., the speed of convergence is slow and it cannot guarantee to converge to globally optimal solution, they are more efficient in attaining near-optimal solutions significantly than conventional point-by-point exhaustive search techniques, especially in large solution spaces.
Taking the relation between diversity of evolution population and evolution times into account, a Contract Mapping Genetic Algorithm with Varying Mutation Probability (CMGAVaPm) is proposed. Not only can the algorithm converge to globally optimal solution, but also it solve premature convergence problem efficiently. Simulation results show that the algorithm CMGAVaPm presented in this thesis performs better contrast with simple genetic algorithm and former contract mapping genetic algorithm.
Abstract
Chapter 1. Introduction…………………………………………………1
1.1 WDM System and Network Evolution………………………………1
1.2 Multicasting in Optical Networks………………………………9
1.3 Wavelength Converter………………………………………………11
1.4 Genetic Algorithms ………………………………………………14
Chapter 2. Restoration Facilities in WDM Network ………………17
2.1 Classification of Restoration Methods ………………………17
2.2 Point-to-Point Restoration Schemes……………………………20
2.3 Restoration Schemes for Multicast Tree………………………24

Chapter 3. GA-Based Multicast Backup Tree Scheme ………………26
3.1Problems Formulation ………………………………………27
3.2 Initialization………………………………………………………33
3.3 Encoding of Chromosome……………………………………………34
3.4 Fitness Function……………………………………………………35
3.5 Reproduction and Selection………………………………………36
3.6 Crossover ……………………………………………………………36
3.7 Mutation………………………………………………………………37
3.8 Termination Rule……………………………………………………38
Chapter 4. Contract Mapping Genetic Algorithm with Varying Mutation Probability (CMGAVaPm )………………………...39
4.1 Contract Mapping Genetic Algorithm (CMGA)………………..39
4.2 Proposed Contract Mapping Genetic Algorithm with Varying Mutation Probability (CMGAVaPm)…………………………………………………………………42
4.2.1 Modified Mutation Operation …………………………………43
4.2.2 Varying Mutation Probability…………………………………44
4.2.3 Proposed CMGAVaPm ………………………………………………46
Chapter 5. Simulation and Results…………………………………49
5.1Control Parameters ……………………………………………50
5.2Optimization results comparison……………………………56
Chapter 6. Conclusions………………………………………………..61
Reference
[1] R. Ramaswami and K. N. Sivarajan, Optical Networks-A Practical Perspective. San Francisco: Morgan Kaufmann, 1998.
[2] G. Keiser, Optical fiber communication. New York: McGraw-Hill, 2000.
[3] B. Mukherjee, “DWDM optical communication networks: progress and challenges,” Selected Areas in Communications, IEEE Journal on, vol. 18, pp. 1810-1824, Oct. 2000.
[4] L. H. Sahasrabuddle and B. Mukherjee, “ Light-Trees: Optical Multicasting for improved performance in Wavelength-Routed Networks,” IEEE Communications
Magazine, Vol. 37, No. 2, pages 67-73, Feb. 1999.
[5] R. Malli, X. Zhang and C. Qiao, “Benefits of Multicasting in All-optical Networks,” Proc. of SPIE, All optical Networking, Vol. 3531, pp. 209-220, Nov. 1998.
[6] B. Mukherjee, Optical Communication Networks. New York: McGraw-Hill, July 1997.
[7] C. A. Brackett et al., “A scalable multiwavelength multihop optical network: A proposal for research on all-optical networks,” J. Lightwave Technol., vol. 11, pp. 736—753, May/June 1993.
[8], G. Mohan, C. S. R. Murthy, and A. K. Somani, “Efficient algorithms for routing dependable connections in DWDM optical networks Networking,” IEEE/ACM Transactions on, Vol. 9, pp.553-566, Oct. 2001.
[9] J. Holland, “Adaptation in Natural and Artificial Systems,” Univ. of Michigan Press (Ann Arbor), 1975.
[10] D. E. Goldberg, “Genetic algorithms in Search, Optimization and Machine learning,” Reading. MA: Addison Wesley, 1989.
[11] M. Mitchell, “An introduction to genetic algorithms,” London, England, 1996.
[12] S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks, Part I─Protection,” in Proc. IEEE INFOCOM, 1999, pp. 744—751.
[13] G. Mohan and A. K. Somani, “Routing Dependable Connections With Specified Failure Restoration Guarantees in WDM Networks,” Proc. IEEE INFOCOM 2000, Mar. 2000.
[14] G. Mohan, C. S. R. Murthy, “Routing and wavelength assignment for establishing dependable connections in WDM networks,” Fault-Tolerant Computing, 1999. Digest of Papers. Twenty-Ninth Annual International Symposium on, pp. 94 -101, 1999.
[15] G. Mohan, C. S. R. Murthy, “Lightpath restoration in DWDM optical networks,” IEEE Network, vol. 14, pp.24-32, Nov.-Dec. 2000.
[16] R. Kawamura, I. Tokizawa, “Self-Healing Virtual Path Architecture in ATM Networks”, IEEE Communications Magazine, pp.72-79, Sep. 1995
[17] B. T. Doshi et al., “Optical network Design and Restoration,” Bell Labs Tech. J., Jan.-Mar. 1999, pp. 58-84.
[18] Cheng-Shong Wu and Shi-Wei Lee, “Study of working and backup path routing policies in self-healing ATM networks,” ISCOM’95
[19] R. Kawamura, K. Sato. and I. Tokizawa, “Self-healing ATM networks based on virtual path concept,” IEEE JSAC, vol. 1, no. 1, pp. 120-127, June 1996.
[20] Cheng-Shong Wu and Shi-Wei Lee, Young-tseng Hou, and Yuan-Sun Chu,“A new preplanned self-healing scheme for multicast ATM networks,” Communication Technology Proceedings, vol. 2, no. 5-7, May 1996
[21] B. M. Waxman, “Routing of multipoint connections,” IEEE JSAC, vol. 6, no. 9, pp. 1617-1622, Dec. 1988.
[22] J. K. Shapiro, D. Towsley, and J. Kurose,” Optimization-based congestion control for multicast communications,” IEEE Communications Magazine, vol. 40 Issue: 9, 2002.

[23] E. N. Gilbert and H. O. Pollak, “Steiner minimal trees,” SIAM J. Appl. Math., vol. 16, no. 1, pp. 1-29, 1968.
[24] H. S. M. Coxeter, Introduction to Geometry. New York: Wiley, 1961.

[25] R. E. Miller and J. W. Thatcher, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. M. Karp, Ed. New York: Plenum, pp.85-103, 1972.
[26] K. Bharath-Kumar and J. M. Jaffe, “Routing to multiple destinations in computer networks,” IEEE Trans. Commun., vol. COM-31,no. 3, pp. 343-351, Mar. 1983.
[27] A. Szalas and Z. Michalewicz, Contract mapping genetic algorithm and their convergence, Dept. of computer science, University of North Carolina at Charlotte, Technical Report 006-1993.

[28] Z. Michalewicz, Genetic Algorithm + data structure=Evolution Programs. Springer-Verlag, 1994.
[29] S. Banach, Sur les operations dans les ensembles abstraits et leur applications aux equations integrals, Fundamenta Mathematica, vol. 3, pp.133-181, 1922.
[30] Dunwei Gong and Xiaoyan Sun, “A modified contract mapping genetic algorithm,” ISIE 2002, vol. 1, pp. 353-356, 2002.
[31] M. Srinivas and L. M. Patnaik, ”Adaptive probabilities of crossover and mutation in genetic algorithms,” IEEE transactions on systems, Man and Cybernetics, vol. 24, no. 4, Apr. 1994.
[32] K. Murakami and H. S. Kim, “Near-optimal virtual path routing for survivable ATM networks,” INFOCOM ''94. Networking for Global Communications. 13th Proceedings IEEE, vol.1, pp. 208 —215, Jun. 1994.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔