臺灣博碩士論文加值系統

近來，擴充非同步傳輸模式（ATM）的技術，以便能應用於無線通訊環境的許多議題已引起廣泛的興趣與研究。而其主要的動機是在無線通訊網路與非同步傳輸模式網路之間，設計一個完整無瑕之連結；及在實際生活中對於行動多媒體之服務的急切需求。於本文中，我們將研究個人通訊服務（PCS）系統中之基地台指派至ATM網路中之交換器的問題。此問題討論：若給定一個行動通訊系統及一個非同步傳輸模式網路，並假設基地台及交換器之位置為固定且已知，則如何將基地台指派及連接至交換器以獲得最佳的效率。
在本論文內，我們首先以一個複雜的整數規劃模式來定義此問題，因為找出此問題之最佳解答為一個NP-Hard的問題，故我們發展數個啟發式演算法，基因演算法及模擬退火演算法來解決此問題。實驗之結果顯示出，這些演算法獲得良好之效率。
其次，因為行動電話的快速普及，導致話務量大增；而基地台本身有通話容量的限制，導致必須建立新的基地台或經過細胞分裂的過程，以增加基地台的通話量進而能提供較佳的通話品質。而當基地台增加的同時，新基地台與寬頻骨幹的交換器之間的連線方式亦是一個亟待解決的問題。另外，基於可靠度及網路可用度的考量，我們也考慮到當基地台所指派的交換器不只一個時的派模式。針對不同的模式，我們均發展出基因演算法用以解決。

Recently, there has been some interest in extending ATM (Asynchronous Transfer Mode) technology to the wireless environment. The motivation behind this extension (termed wireless ATM) includes the desire for seamless interconnection of wireless and ATM networks, and the need to support emerging mobile multimedia services. In this dissertation, we investigate the problem of optimum assignment of cells in PCS (Personal Communication Service) to switches in a wireless ATM network. Given cells and switches in an ATM network (whose locations are fixed and known), the problem is assigning cells to switches such that the cost can be minimized. The cost has two components, one is the cost of handoffs that involve two switches, and the other is the cost of cabling.
In this dissertation, first, this problem named cell assignment problem is modeled as a complex integer-programming problem. Since finding an optimal solution to this problem is NP-hard, we develop several heuristic algorithms, genetic algorithms, and a simulated annealing algorithm to solve this problem. Experimental results show that these algorithms have good efficiency. Second, due to the tremendous growth in the usage of mobile phone, the call may be dropped if the congestion occurred at the base station. To provide better quality of the communication, new base stations may be added into the PCS network or cell may be split to increase the whole capacities of the PCS network.
Moreover, the original connections between cells and switches may be out of date or the handoff traffic between cells may be changed. After the number of base stations is increased, how to assign newly added and split cells of PCS network to switches in ATM network such that the total cost is minimized is an important issue. Furthermore, extended cell assignment problem and the network expansion problem are formulated and solved. Beside, since the availability and the reliability of the wireless ATM network are important. We also solve the dual-homing cell assignment problem, which allows each cell can be assigned to two switches in ATM network. For the different kinds of cell assignment problem, genetic algorithms are proposed to solve these problems.

Cover
Abstract (in Chinese)
Abstract (in English)
Acknowledgments
Contents
List of Figures
List of Tables
1 Introduction
1.1 Why Cell Assignment Problem?
1.2 Overviews of Main Results
2 Problem Formulation
2.1 Formulation of Cell Assignment Problem
2.2 Formulation of Extended Cell Assignment Problem
2.3 Formulation of Network Expansion Problem
2.4 Formulation of Dual-homing Cell Assignment Problem
2.5 Problem model
3 Reviews of Related Studies
3.1 Background of Genetic Algorithms
3.2 Background of Simulated Annealing
4 Cell Assignment Problem
4.1 Solution Model for Cell Assignment Problem
4.2 Heuristic Solution Approach for Cell Assignment Problem
4.3 Genetic Algorithms for Cell Assignment Problem
4.4 Simulated Annealing Algorithm for Cell Assignment Problem
4.5 Comparisons of Different Solution Algorithms
4.6 Summary of Cell Assignment Problem
5 Extended Cell Assignment Problem
5.1 Introduction
5.2 Heuristic Algorithm for Extended Cell Assignment Problem
5.3 Genetic Algorithm for Extended Cell Assignment Problem
5.4 Simulated Annealing Algorithm for Extended Cell Assignment Problem
5.5 Experimental Results
5.6 Summary of Extended Cell Assignment Problem
6 Genetic Algorithm for Network Expansion Problem in Wireless ATM Network
6.1 Introduction
6.2 Problem Formulation
6.3 Outline of Solution Algorithm
6.4 Genetic Algorithm for Network Expansion Problem
6.5 Experimental Results
6.6 Summary
7 Dual-homing Cell Assignment Problem
7.1 Introduction
7.2 Genetic Algorithm for Dual-homing Cells Assignment Problem
7.3 Experimental Results
7.4 Summary
8 Conclusions and Future Works
8.1 Conclusions
8.2 Future Works

References
[1] A. Acharya, ``Primitives for Location Management and Handoff in Mobile ATM Networks,'' ATM Forum cont., Aug. 1996, pp. 96-1121.
[2] P. Agrawal, P. P. Mishra, and M. Srivastava, ``Network architecture for mobile and wireless ATM,'' ICDC'96; Proceedings of the 16th International Conference on Distributed Computing System; May 27-30 1996, Hong Kong, IEEE, May, 1996, pp. 299-310.
[3] E. Arts and J. Korst, Simulated Annealing and Boltzman Machines, John Wiley & Sons, 1989.
[4] R. B. Boppana, ``Eigenvalues and graph bisection: an average-case analysis,'' Proc. 28th Symp. Foundations of Computer Science, 1987, pp. 280-285.
[5] T. N. Bui and A. Peck, ``Partitioning planar graphs,'' SIAM J. Computing, vol. 21, no. 2, 1992, pp. 203-215.
[6] G. G. Brush and N. A. Malrow, ``Assuring the dependability telecommunications networks and services,'' IEEE Network Magazine, January 1990, pp. 29-34.
[7] M. Cheng, S. Rajagopalan, L. F. Chang, G. P. Pollini, and M. Barton, ``PCS mobility support over fixed ATM networks,'' IEEE Communication Magazine, Nov. 1997, pp. 82-91.
[8] G. A. Cleveland and S. F. Smith, ``Using genetic algorithms to schedule flow shop releases.'' In Proceedings of the 3rd International/ Conference on Genetic Algorithms (Edited by J. D. Schaffer), George Mason University, 1989.
[9] D. C. Cox, ``Personal Communication - A viewpoint,'' IEEE Commun. Mag., Nov, 1990, pp. 8-20.
[10] L. Davis (ed), Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991.
[11] Der-Rong Din and S. S. Tseng, ``A solution model of integrating cells of PCS to switches in wireless ATM network'', submitted to IEICE for possible publication.
[12] Der-Rong Din and S. S. Tseng, ``Genetic algorithms for optimal design of two-level wireless ATM network,'' to appear in Proceeding of National Science Council, R. O. C. Part A: Physical Science and Engineering.
[13] Der-Rong Din and S. S. Tseng, ``Heuristic algorithm for optimal design of two-level wireless ATM network,'' to appear in Journal of Information Science and Engineering.
[14] Der-Rong Din and S. S. Tseng, ``Simulated annealing algorithm for optimal design of two-level wireless ATM network,'' submitted to International Journal of Computer System Science and Engineering for possible publication.
[15] Der-Rong Din and S. S. Tseng, ``Genetic algorithms for extended cell assignment problem in two-level wireless ATM network,'' Jifeng He and Masahiko Sato (Eds.) ASIAN 2000, Lecture Notes in Computer Science (LNCS) 1961, Springer-Verlag Berlin Heidelberg, 2000, pp. 69-87.
[16] Der-Rong Din and S. S. Tseng, ``A simulated annealing algorithm for extended cell assignment problem in wireless ATM network'', E. J. W. Boers et al. (Eds.) EvoWorkshop 2001, Lecture Notes in Computer Science (LNCS) 2037, Springer-Verlag Berlin Heidelberg, 2001, pp. 150-160.
[17] Der-Rong Din and S. S. Tseng, ``A Heuristic and a Simulated Annealing Algorithm for Extended Cell Assignment Problem in Wireless ATM Network'', submitted to Communication systems for possible publication.
[18] J. Dennis, ``Data Flow Supercomputers,'' Computer, 1980, pp. 48-56.
[19] J. G. Donnett, M. Starkey, D. B. Skillcorn, ``Effective algorithms for partitioning distributed problems,'' Proceedings of the Seventh Annual International Phoenix Conference on Computers and Communications, IEEE, March, 1988, pp. 363-369.
[20] K. Efe, ``Heuristic methods of task assignment scheduling in distributed system,'' IEEE Computer, 15(6), June, 1982, pp. 50-56.
[21] Gangsheng Wang and Nirwan Ansari, ``Searching for optimal frame patterns in an integrates TDMA communication system using mean field annealing,'' IEEE Trans. Neural Networks, Vol. 9, No. 6, Novenmber 1998, pp. 1292-1300.
[22] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Reading, MA, 1989.
[23] V. B. Gylys, J. A. Edwards, ``Optimal partitioning of workload for distributed systems,'' Proc Compcon Fall, 1976, pp. 353-356.
[24] T. Hattori, ``Personal communication - Concept and architecture,'' in International Conference on Communications (ICC'90), Georgia World Congress Center, Altanta, Georgia, April, 1990, pp. 333.4.1-335.4.7.
[25] R. Jain, Y. B. Lin, C. Lo, and S. Mohan, ``A caching strategy to reduce network impacts of PCS,'' IEEE J. Select. Areas in Commun., vol. 12, Oct. 1994. pp. 1434-1444.
[26] B. W. Kernighan and S. Lin, ``An efficient heuristic procedure for partitioning graphs,'' Bell Systems Technical J., vol. 49, Feb. 1970, pp. 291-307.
[27] Kirkpatrick S., Gelatt C. D. and Vecchi M. P. ``Optimization by simulated annealing'', Science 220, 1983, pp. 671-680.
[28] H. W. Kuhn, ``The Hungarian Method for the Assignment Problem,'' Naval Research Logistics Quarterly, 2, 1955, pp. 83-97.
[29] Van Laarhoven, E. Arts, Simulated Annealing: Theory and Application, D. Reidel Publishing Company, Holand, 1987.
[30] E. L. Laeler, Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart & Winston, 1976.
[31] Y. B. Lin,``Determining the user locations for personal communications services networks,'' IEEE Trans. Veh. Technol., vol. 43, Aug. 1994, pp. 466-473.
[32] Y. B. Lin and S. Y. Hwang, ``Comparing the PCS location tracking strategies,'' IEEE Trans. Veh. Technol., vol. 45, Feb. 1996, pp. 114-121.
[33] R. C. V. Macario, Cellular Radio. McGraw-Hill, New York, 1993.
[34] A. Merchant and B. Sengupta, ``Assignment of Cells to Switches in PCS Networks'', IEEE/ACM Trans. on Networking, vol. 3, no. 5, Oct., 1995, pp.521-526.
[35] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, ``Equation of State Calculations by Fast Computing Machines,'' Journal of Chemical Physics, 21, 1953, pp. 1087-1091.
[37] S. Mohan and R. Jain, ``Two user location strategies for personal communications services,'' IEEE Personal Communications, vol. 1, no. 1, 1994, pp. 42-50.
[38] S. Narasimhan, The concentrator location problem with variable coverage. Computer Networks and ISDN Systems, 19, 1990.
[39] G. L. Nemhauser and L. A. Woolsey, Integer and Combinatorial Optimization, New York, Wiley, 1988.
[40] H. Pirkul and E. Rolland, A lagrangian based heuristic for graph partitioning. Working paper, University of California. Riverside, California, 1991.
[41] H. Pirkul, S. Prikul, Narasimhan. and P. De, Locating concentrators for primary and secondary coverage in a computer communication network. IEEE Transactions on Communications, COM-36, 1988, pp.450-458.
[42] D. Raychaudhuri and N. D. Wilson, ``ATM-Based transport architecture for multiservices wireless personal communication networks,'' IEEE Journal on Selected Areas in Communications, Oct., 12(8), 1992, pp. 1401-1413.
[43] J. T. Rhapsodic, M. R. Palmer, G. E. Liepins, and M. Hilliard, ``Some guidelines for genetic algorithms with penalty functions,'' In Proceedings of the 3rd International Conference on Genetic Algorithms (Edited by J. D. Schaffer). George Mason University, 1989.
[44] Richardson, J. T. M. R. Palmer, G. L. Liepins, and M. Hilliard, (1989) Some guidelines for genetic algorithms with penalty functions. In Proceedings of the 3rd International Conference on Genetic Algorithms, (Edited by J. D. Schaffer), George Mason University.
[45] E. Rolland, Abstract Heuristic Search Methods for Graph Partitioning. Ph.D. dissertation, The Ohio State University Columbus, Ohio, 1991.
[46] R. Steele, ``Deploying personal communication networks,'' IEEE Commun. Mag., Vol. 4, Sept. 1990, pp. 6-11.
[47] D. T. Tang, L. S. Woo and L. R. Bahl, ``Optimization of teleprocessing networks with concentrators and multiconnected terminals,'' IEEE Transactions on Computers, C-27, 1978.
[48] U. Varshney, ``Supporting Mobile using Wireless ATM'', IEEE Computer, 30(1), January, 1997, pp. 131-133.
[49] H. B. Zhou, ``Two-stage m-way graph partitioning.'' Parallel Computation, 19, 1993, pp.1359-1373.