臺灣博碩士論文加值系統

隨著無線網路 (Wireless Networks) 技術的成熟，大眾對於行動通訊的需求愈來愈高。不僅只有語音通話的需求，數據傳輸 (Data Transmission) 的應用，如多媒體、電子郵件等等也將變得愈來愈重要。而目前的主流是第二代行動通訊系統GSM。由於GSM先天設計的特性，它只適合用來傳輸語音，不適合用來傳輸資料，因此有了第二點五代系統：整合封包無線傳輸服務 (GPRS) 的產生。GPRS可以在現存GSM網路架構下，提供數據傳輸的技術，其特色就是將資料分封成數個封包 (Packets) 一起傳送。因此大幅提昇傳輸速率，達到更有效的頻譜資源分配。由於GSM和GPRS是使用共同的頻道，所以時槽 (Time Slot) 的分配便是一項可研究的議題。不同的時槽分配原則 (Policy) 會導致系統有不同的收益、效能和服務品質等。在系統營運業者的角度來看，收益極大化是最主要的考量，因此在這篇論文中，我們希望根據使用者的分配，能找到一個時槽分配的原則，讓整個系統的收益最佳化。
在本研究中針對GPRS頻道分配的問題，我們提出了兩個數學模型。兩個模型的目的都是去最佳化GPRS頻道分配系統的收益，在給定使用者的流量參數之後，在頻道數目限制之下，找出一個最好的頻道分配原則，達成收益最佳化的要求。而二個模型的主要差別在於時間的型態，第一個模型是考慮連續的時間 (Continuous-Time) ，而第二個模型則是離散 (Discrete) 的形式。由於這二個模型的數學結構和規模的緣故，我們採用馬可夫決策過程 (Markovian Decision Process) 來解決我們的問題。
在兩個模型的實驗中，我們都得到優異的結果。我們以馬可夫決策過程為基礎的解題程序在我們的模型下可以找到使收益最佳化的頻道分配原則。我們找到的原則比起原來的經驗法則，在收益方面可達到數倍以上的改進，證明我們的方法可以提供系統營運業者和網路規劃人員良好的決策。

With the maturity of the wireless networks technology, the demands for the mobile communication become higher and higher. Besides voice communication demands, data transmission applications such as WWW, multimedia are becoming more and more important. The main system of mobile communication is GSM, which is mainly designed for voice and is not suitable for data transmission. In order to satisfy the increasing user requirements, in developing of GSM phase 2+, the ETSI has specified a general packet radio service (GPRS) that accommodates data connections with high bandwidth efficiency. Since GPRS is based on GSM and they use the same physical channels, the allocation of time slot is an academic issue. Different slot allocation policy will cause different revenue, throughput and QoS of the system. In the vendor's point of view, revenue maximization is the main consideration. Thus in this thesis, we want to find a policy to maximize the system revenue according to the users' traffic pattern.
We propose two mathematical models to deal with the slot allocation problem in this thesis. The goal of our model is to find a slot allocation policy to maximize the system revenue under the capacity constraint. The main difference between two models is the time type. The first model is continuous-time, and the second model is discrete time. We apply Markovian decision process to solve our problem due to the problem size and the mathematical structure of our model.
The computational results are good in our experiments. We can find a slot allocation policy to maximize the system revenue according to users' traffic pattern. Comparison to the policy that the vendors often used, the policy we found has great improvement in system revenue. Thus, our model could provide good decisions for system vendors and network planners.

Chapter 1 Introduction1
1.1 Background1
1.2 Motivation3
1.3 Proposed Approach4
1.4 Thesis Outline7
Chapter 2 GPRS Architecture and Markovian Decision Process 8
2.1 GPRS Architecture8
2.2 GPRS Air Interface Protocol10
2.3 GPRS Resource Allocation Issues12
2.4 Markovian Decision Process13
2.4.1 Policy Iteration Method: Discrete Case13
2.4.2 Policy Iteration Method: Continuous-Time Case15
Chapter 3 Problem Formulation: Continuous-Time Case18
3.1 Notation21
3.2 Problem Formulation22
3.3 Solution Procedure25
3.4 Computational Experiments26
3.5 Model Expansion: Considering Blocking Probability34
Chapter 4 Problem Formulation: Discrete Case36
4.1 Notation40
4.2 Problem Formulation41
4.3 Solution Procedure43
4.4 Computational Experiments45
Chapter 5 Summary and Future Research52
5.1 Summary52
5.2 Future Research53
References54

[1]Agha, K.A. and Boussettta, K., “Dynamic Slot Allocation for Multicasting in GPRS Systems,” IEEE Vehicular Technology Conference Proceedings, 51st, vol. 3, pp. 2355—2359, 2000.
[2]Ajib, W. and Godlewski, P, “Acknowledgment Operations in the RLC Layer of GPRS,” Mobile Multimedia Communications, pp. 311-317, 1999.
[3]Brasche, G. and Walke, B., “Analysis of Multi-slot MAC Protocols Proposed for the GSM Phase 2+ General Packet Radio Service,” IEEE Vehicular Technology Conference, 47th, vol. 2, pp. 1295—1300, 1997.
[4]Brignol, L., Brouet, J., Charriere, P., and Mercier, F., “Effects of Traffic Characteristics on the GPRS Performance,” IEEE Vehicular Technology Conference, vol. 2, pp. 844-848, 1999.
[5]Cisco, “GPRS White Paper,” Cisco Systems, Inc, 2000.
[6]ETSI Technical Specification GSM 02.60, GPRS Service description — Stage 1, V6.3.0, July 2000.
[7]ETSI Technical Specification GSM 03.60, GPRS Service description — Stage 2, V7.4.0, April 2000.
[8]ETSI Technical Specification GSM 03.64, Overall description of the GPRS radio interface — Stage 2, V8.5.0, August 2000.
[9]Fabri, S.N., Kondoz, A., Tatesh, S. and Dometroseu, C., “Proposed Evolution of GPRS for the Support of Voice Services,” IEEE Communications, vol. 146, pp. 325 —330, October 1999.
[10]Giuseppe, Antonio and Luigi, ”Packet Data Services over GSM Networks with Dynamic Stealing of Voice Channels,” IEEE GLOBECOM'95, vol. 2, pp. 1152-1156, 1995.
[11]Gotz Brasche and Bernhard Walke, ”Concepts, Services, and Protocols of the New GSM Phase 2+ General Packet Radio Service,” IEEE Communication Magazine, pp. 94-104, August 1997.
[12]Hamdy A. Taha, “Operations Research: an Introduction,” third edition, 1982.
[13]Hillier and Lieberman, ”Introduction to Operations Research,” fourth edition, Holden-Day, Inc, 1986.
[14]Ho, J., Zhu, Y. and Madhavapeddy, S., “Throughput and Buffer Analysis for GSM General Packet Radio Service (GPRS),” IEEE Wireless Communications and Networking Conference, pp. 1427 —1431, 1999.
[15]Hoff, S., Meyer, M. and Schieder, A., “A Performance Evaluation of Internet Access via the General Packet Radio Service of GSM,” IEEE Vehicular Technology Conference, vol. 3, pp. 1760-1764, 1998.
[16]J.E. Wieselthier and A. Ephremides, “Fixed- and Movable Boundary Channel-Access Schemes for Integrated Voice/Data Network,” IEEE Trans. on Communication, vol. 43, no. 1, pp. 64-74, January 1995.
[17]J.S. Kaugman, “Blocking in Completely Shared Resource Environment with State Dependent Resource and Residency Requirements,” IEEE INFOCOM’92, pp. 2224-2232, 1992.
[18]Jian Cai and David, J. Goodman, “General Packet Radio Service in GSM,” IEEE Communications Magazine, vol. 35, no. 10, pp. 122-131, October 1997.
[19]Jonathan Sau and Chris Scholefied, “Scheduling and Quality of Services in the General Packet Radio Service,” IEEE 1998 International Conference on, vol. 2, pp. 1067-1071, 1998.
[20]Kennedy, K. and Van Luipen, B., “Interference Effects of GPRS on a GSM Network,” IEEE Vehicular Technology Conference, vol.4, pp. 2087-2091, 1999.
[21]Mahdavi, M and Tafazolli, R, “Analysis of Integrated Voice and Data for GPRS,” 3G Mobile Communication Technologies First International Conference on, pp. 436—440, 2000.
[22]Martin L. Puterman, “Markov Decision Processes: Discrete Stochastic Dynamic Programming,” Wiley, New York, 1994.
[23]Moorhead, C., Hardman, V.J. and Lane, P.M., ”Resource Allocation Schemes to Provide QoS for VoIP over GPRS,” 3G Mobile Communication Technologies First International Conference on, pp. 138—142, 2000.
[24]Otto Brestscher, “Linear Algebra With Applications,” Prentice-Hall Inc., 1997.
[25]Roger Kaldem, Ingo Meirick and Michael Meyer, “Wireless Internet Access Based on GPRS,” IEEE Personal Communications, pp. 8-18, April 2000.
[26]Ronald A. Howard, “Dynamic Programming and Markov Processes,” Wiley, New York, 1970.
[27]S. Ghani and m. Schwartz, “A Decomposition Approximation for the Analysis of Voice/Data Integration,” IEEE Trans. on Communication, vol. 42, no. 7, pp. 2441-2451, July 1994.
[28]Shaoji Ni and Sven-Gustav Haggman, “GPRS Performance Estimation in GSM Circuit Switched Services and GPRS Shared Resource System,” IEEE Wireless Communications and Networking Conference, vol. 3, pp. 1417-1421, 1999.
[29]Stuckmann, P. and Muller, F., ”GPRS Radio Network Capacity and Quality of Service Using Fixed and on-Demand Channel Allocation Techniques,” IEEE Vehicular Technology Conference Proceedings, 51st, vol. 1, pp. 440-444, 2000.
[30]V.A. Chitre and J.N. Daigle, “IP Traffic over GPRS- An Internet Service Oriented Analysis,” IEEE Wireless Communications and Networking Conference, vol. 3, pp. 1263-1267, 1999.