臺灣博碩士論文加值系統

摘 要
網路高頻寬需求的時代已經來臨。無疑地，只有光纖傳輸媒體才能適應這種需求。應用光纖通訊技術已能趕上這種網路通訊流量的成長。由於光分波長多工技術的成熟，使光波的廣大頻寬得以有效率的利用。因此，光分波長多工技術將為滿足高頻寬需求帶來美麗的前景。
在光分波長多工技術上的一個重要課題是波長分配問題。我們提出四個方法在這個問題上來探討，以滿足在規劃網路時能達到最小的成本要求。MSB方法是藉著結合、分割和阻塞的技術來求得波長分配的結果。基因演算法利用猜測及非線性的過程，以尋求問題的一組解空間。類神經網路是根據回溯傳播學習規則來架構，主要是要解決應用在即時資料上的動態波長分配問題。我們也建議一個分散式多重代理者策略，以便支援動態選擇網路架構的問題。
在實驗模擬中，顯示了提出的方法都可獲得不同的特性。MSB方法可達到較佳的規劃結果，基因演算法可改善MSB的計算複雜度，類神經網路方法可顯著地降低計算時間和得到較佳的規劃結果。而分散式多重代理者系統可支援各種不同的資料型態。
關鍵字：光分波長多工網路，波長分配，結合、分割、阻塞法，基因演算法，類神經網路，分散式多重代理者系統，單向環狀，動態再架構。

Abstract
A higher bandwidth required age has been coming. Needless to say, there is no better known physical medium than the fiber. The all-optical fiber communication technology has kept up with the growing traffic volume. Owing to the OWDM technology is mature, it makes effective use of the vast fiber bandwidth. Therefore, the OWDM technology will create the most beautiful spectacle that we have been satisfied the high bandwidth requirement.
A wavelength assignment (WLA) problem is the key issue of the OWDM technology service networks. We proposed four methodologies for WLA in OWDM rings that minimize the overall network cost. The MSB approach operates by merging, splitting, and blocking mechanisms. The GA approach utilizes stochastic, and nonlinear process to search the solution space. The ANN was constructed according to the back propagation learning rule and was used to dynamically assign wavelengths for real-time traffic streams using training data, which derived from the MSB approach. A DMAS scheme was proposed for supporting dynamic reconfiguration and wavelength scheduling in a cost-effective fashion.
Our simulation indicates that the proposed approaches may gain various features. The MSB approach can come to the better scheduling results. The GA approach takes the computational time is lower than the MSB approach. The ANN approach may significantly reduce the computational complexity and investment cost compared with other approaches in OWDM ring networks. And the DMAS approach can support various traffic patterns.
Keywords: OWDM network, WLA, MSB, GA, ANN, DMAS, uni-directional ring, Dynamic Reconfiguration.

Table of Contents
Chapter 1 Introduction ------------------------------------1
1.1 Motivation -----------------------------------------1
1.2 Organization of Thesis -----------------------------4
1.3 Contributions of this research ---------------------5
Chapter 2 Related Work ------------------------------------6
2.1 Related Work ---------------------------------------6
2.2 Mathematical Model ---------------------------------9
2.3 New Approaches for the WLA -------------------------11
Chapter 3 MSB Approach for WLA ----------------------------13
3.1 MSB Algorithm --------------------------------------13
3.2 Case study -----------------------------------------19
3.3 Discussion -----------------------------------------24
Chapter 4 Genetic Algorithm Approach for WLA --------------26
4.1 Basic concepts of Genetic Algorithm (GA) -----------26
4.2 GA for Wavelength Assignment -----------------------28
4.2.1 GA Cycle ---------------------------------------28
4.2.2 Crossover Operation ----------------------------29
4.2.3 Mutation Operation -----------------------------29
4.3 Example of GA for Optimization ---------------------29
4.3.1 Example of Crossover Operation -----------------29
4.3.2 Example of Mutation Operation ------------------31
4.4 Case study -----------------------------------------31
4.5 Discussion -----------------------------------------37
Chapter 5 Other Intelligent Methodology for WLA -----------38
5.1 Artificial Neural-Network (ANN) scheme -------------38
5.2 ANN Main Design Principles -------------------------39
5.2.1 Three-Layer Feedforward Network ----------------39
5.2.2 Back Propagation Learning Rule -----------------40
5.2.3 Overall Architecture ---------------------------41
5.3 Distributed Multi-Agent Scheme (DMAS) Technique ----41
5.4 Problem-Solving Feature ----------------------------42
5.5 Proposed DMAS Scheme -------------------------------43
5.5.1 Knowledge Sources (KSs) ------------------------44
5.5.2 Blackboard Module ------------------------------45
5.5.3 Control Engine ---------------------------------45
5.5.4 Implementation ---------------------------------46
Chapter 6 Simulation Results and Discussions ---------------47
6.1 MSB, GA, and ANN for the WLA -----------------------47
6.1.1 Discussion -------------------------------------48
6.2 DMAS scheme for reconfiguration --------------------50
6.2.1 Knowledge Sources ------------------------------50
6.2.2 Application Architecture -----------------------51
6.2.3 Applied Results and Discussions ----------------52
Chapter 7 Conclusion and Future Work -----------------------55
Reference --------------------------------------------------57

Reference:
[1]M. Kuznetsov, N. M. Froberg, and S. R. Henion, “A Next-
Generation Optical Regional Access Network,” IEEE
Communications Magazine, Vol. 38, No. 1,pp.66-72, Jan. 2000.
[2]http://www.find.org.tw
[3]S. V. Kartalopoulos, “Introduction to DWDM Technology Data
in a Rainbow,” IEEE Press, 1999.
[4]WDM Technology, http://www.telcite.fr/nwdmen.htm
[5]Sudhir S. Dixit and Antti Yia-Jaaske, “WDM Optical
Networks: A Reality Check,” IEEE Communications Magazine,
Vol. 38, No. 3, pp.58-59, Mar. 2000.
[6]N. Antoniades, S.J.B. Yoo, K. Bala, G. Ellinas, and T.E.
Stern, “An Architecture for a Wavelength-Interchanging
Cross-Connect Utilizing Parametric Wavelength Converters,”
IEEE Journal of Lightwave Technology, Vol.17, No.7, pp.1113-
1125, July 1999.
[7]S. Subramaniam, A.K. Somani, M. Azizoglu, and R.A. Barry,
“The Benefits of Wavelength Conversion in WDM Networks with
Non-Poisson Traffic,” IEEE Communications Letters, Vol.3,
No.3, pp.81-83, March 1999.
[8]S. Subramaniam, M. Azizoglu, and A.K. Somani, “On the
Optimal Placement of Wavelength Converters in Wavelength-
Routed Networks,” Proceedings of IEEE Infocom’98. (CD-ROM
Version)
[9]N.F. Huang and R.C. Wang, “WDM-Based PCN Architecture,”
Proceedings of IEEE Globecom’97. (CD-ROM Version)
[10]L. Wuttisittikulkij, S. Leelanunnukul, S. Arreewanit, and
P. Prapinmongkolkarn, “Routing and Wavelength Allocation
in Multi-Wavelength All-Optical Ring Networks,”
Proceedings of ICC’99, 1999. (CD-ROM Version)
[11]O. Gerstel, R. Ramaswami, and G. Sasaki, “Cost Effective
Traffic Grooming in WDM Rings,” Proceedings of IEEE
Infocom’98. (CD-ROM Version)
[12]R. Ramaswami and K. Sivarajan, “Optimal Routing and
Wavelength Assignment in All-Optical Networks,” in Proc.
INFOCOM’94, (Toronto, Canada), June 1994.
[13]D. Banerjee and B. Mukherjee, “A Practical Approach for
Routing and Wavelength Assignment in Large Wavelength-
Routed Optical Networks,” IEEE JSAC, Vol.14, No.5, pp.903-
908, June 1996.
[14]L. Wuttisittikkulkij and M.J. O’Mahony, “Design of an
Efficient and Practical Algorithm for Wavelength Assignment
in Multi-Wavelength Ring Transport Networks,” IEEE,pp.571-
575,1997.
[15]O. Gerstel, P. Lin, and G. Sasaki, “Wavelength Assignment
in a WDM Ring to Minimize Cost of Embedded SONET Rings,”
Proceedings of IEEE Infocom’98. (CD-ROM Version)
[16]R. Inkret, B. Mikac, and I. Podnar, “A Heuristic Approach
to Wavelength Assignment in All-Optical Networks,”
IEEE ,pp.759-763,1998
[17]K.S. Tang, K.T. Ko. K.F. Man, S. Kwong, “Genetic
Algorithm: Concept and Applications,” IEEE Transactions on
Industrial Electronics, Vol.43, No.5,pp.519-534,Oct. 1996.
[18]I. Baldine and G.N. Rouskas, “Dynamic Load Balancing in
Broadcast WDM Networks with Tuning Latencies,” Proceedings
of IEEE Infocom’98. (CD-ROM Version)
[19]A. Mokhtar and M. Azizoglu, “Adaptive Wavelength Routing
in All-Optical Networks,” IEEE/ACM Transactions on
Networking, Vol.6, No.2, pp.197-206, April 1998.
[20]E. J. Harder, S. K. Lee, and H. A. Choi, “On Wavelength
Assignment in WDM Optical Network,” IEEE ,pp.32-38,1997
[21]L. Davis, Genetic Algorithms and Simulated Annealing,
London, U.K.: Pitman, 1987.
[22]J. H. Holland, Adaption in Natural and Artificial Systems.
Cambridge, MA: MIT Press, 1975.
[23]Dirk Beckmann, Ulrich Killat, “A New Strategy for the
Application of Genetic Algorithm to the Channel-Assignment
Problem.” IEEE Transactions on Vehicular Technology,
Vol.48, No.4, July 1999.
[24]K.S. Tang, K.T. Ko. K.F. Man, S. Kwong, “Topology Design
and Bandwidth Allocation of Embedded ATM Networks Using
Genetic Algorithm,” IEEE Communications Letters, Vol.2,
No.6, pp.171-173, June 1998.
[25]J.D. Chou and J.L.C. Wu, “Bandwidth Allocation of Virtual
Paths Using Neural-Network-Based Genetic Algorithms,” IEEE
Proceedings- Communications, Vol.145, No.1, pp.33-39, Feb.
1998.
[26]T. Fritsch, “Cellular Mobile Communication Design Using
Self-Organizing Feature Maps,” Neural Networks in
Telecommunications, pp.211-231, 1994.
[27]G. Kechriotis and E.S. Manolakos, “A Hybrid Digital Signal
Processing Neural Network CDMA Multiuser Detection
Scheme,” IEEE Transactions on Circuits and Systems-II,
Vol.43, No.2, pp.96-104, Feb. 1996.
[28]H.El-Rewini, H.H. Ali, and T. Lewis, “Task Scheduling in
Multiprocessing Systems,” IEEE Computer Magazine, pp.27-
38, December 1995.
[29]H. Eriksson,” Expert Systems as Knowledge Sources,” IEEE
Expert, Vol.11, No.3, pp.14-19, June 1996.
[30]H.W. Tzeng, J.L. Chen, and N.K. Chen, “A Genetic Algorithm
for Traffic Grooming in Optical WDM Networks,” Proceedings
of IEEE SMC’99, Oct. 1999. (CD-ROM Version)