兩層式無線非同步傳輸模式網路細胞指派問題的研究

Abstract

近來，擴充非同步傳輸模式（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.