摘 要

在個人通訊網路中，位置管理係利用位置更新(location updating)及傳呼(paging)兩種功能，提供持續追蹤行動用戶位置的能力。當行動用戶人數持續增加，為了有效的利用有限的頻寬，蜂胞(cell)的面積會變的更小，使得位置管理所耗的系統資源將更龐大。因此在第三代個人通訊系統，減少位置更新及傳呼所引起的信號成本，是最重要的效能最佳化課題之一。減少位置更新及傳呼所引起的信號成本，最有效的方法就是適當的設計位置更新區域(location registration area) 及傳呼區域(paging area)的大小。

本論文中，我們發展一個新的動態位置更新策略來節省追蹤行動用戶的成本，其中使用了以個別行動用戶特性來將服務區域劃分為最佳的位置註冊區域。個別行動用戶特性包括行動用戶移動及被呼叫的類型。其中我們發展一個更真實的具方向性移動模型，可以把街道佈局考慮進來，然後用馬可夫程序來分析追蹤行動用戶的成本。這個移動模型能準確預估行動電話用戶的駕駛行為，並且計算的複雜度也不太高。為了降低實作的成本及使得所提的策略更合理，我們還採用行動用戶歸類分群的觀念及等效四邊形位置註冊區域。

將位置註冊區域劃分成最佳的傳呼區域，然後利用選擇性傳呼，可以有效減低傳呼的信號成本。本論文中，我們使用了個別行動用戶移動特性及被呼叫的類型來估算行動用戶被呼叫時可能停留的位置機率，利用這些資訊及最高位置機率優先的策略來劃分成最佳的傳呼區域。劃分最佳的傳呼區域，是一件極耗時的事。我們發展的一個演算法，利用成本函式的特性來導出推論，然後能將劃分最佳的傳呼區域的工作複雜度降到O(NKlogK) ，其中N和K各別為傳呼區域的個數及位置更新區內的蜂胞個數。

最後，不是從個別行動用戶的觀點，而是從整體系統資源來考量，我們提出了一個簡單的整體傳呼策略。使用客戶最近一次報告的位置訊息及最短距離優先的方式，在最大延遲時間的限制下，我們採用一種分散在各個蜂巢式細胞執行的兩階段傳呼策略，來增加每個傳呼週期的傳呼發現率。我們發現在重載時，這個傳呼策略可以大大的降低電話的阻斷率及傳呼等待時間。而且在輕載時，這個傳呼策略的效能也不會比傳統的傳呼策略差。我們由模擬結果發現所提出的傳呼策略不但簡單、計算成本小而且有效。

Abstract

In personal communication networks (PCN), location management provides the function of tracking a mobile user within the service area by using location update and paging. As the number of mobile subscribers grows rapidly, the cell size has to decrease for reusing the limited and scarce wireless bandwidth. Hence, the increasing of the tracking cost is significant. To reduce these signaling costs is one of the most important issues in the third generation PCN. This can be achieved by the proper design of Location areas (LAs) and the optimal Paging Areas.

In this thesis, we propose an intersection-oriented dynamic location update (LU) strategy, which is designed to minimize the cost of mobility tracking by optimally partitioning the service area into Location Areas (LAs) on a per-user basis. A realistic mobility model is proposed, in which we consider not only the mobility behavior of individual subscriber but also the street layout. Based on this model, a transient Markov process is developed to analyze the tracking cost. To reduce the implementation cost and to make the proposed strategy feasible, the concept of MS grouping and equivalent quadrangular LA are also adopted in this thesis.

A selective paging strategy can minimize the paging cost of locating users in wireless personal communications. In this scheme, a location registration area is partitioned into several disjoint paging areas and the system sequentially pages each paging area until the user is found. In this thesis, we derive corollaries from the properties of the cost function to reduce the computation complexity of optimization, and we present a fast optimal partition algorithm of complexity O(NKlogK), where N and K is the number of partitions and cells, respectively.

Finally, Instead of per user basis, we propose a simple paging strategy based on the consideration of ensemble paging channel resource of each cell. Using only the information of the last known locations of mobile subscribers, the proposed paging scheme under a maximum delay constraint can improve the system performance ( discovery rate, blocking rate, and average paging delay ) significantly in the heavy load. The proposed strategy is very simple and the computational complexity is very low.

References
[1] I. F. Akyildiz, and J. S. M. Ho, “On location management for personal communication networks”, IEEE Communication Magazine, pp. 138-145, Sept., 1996.
[2] I. F. Akyildiz, J. Mcnair, J. S. M. Ho and et al., “Mobility management in next-generation wireless systems”, Proceedings of IEEE, Vol. 87, No. 8, pp. 1347-1999, Aug., 1999.
[3] V. O. K. Li, and X. Qiu, “Personal communication system (PCS)”, Proc. of the IEEE, Vol. 83, No. 9, pp. 1210-1243, Sep., 1995.
[4] H. Xie and D. J. Goodman, “Mobility models and biased sampling problem”, in IEEE ICUPC’93, pp. 803-807, 1993.
[5] H. Xie, S. Tabbane, and D. J. Goodman, “Dynamic location area management and performance analysis”, in Proc. IEEE Veh. Technol. Conf., pp. 536-539, 1993.
[6] W. F. Fuhrmann and V.Brass, “Performance aspects of the GSM radio subsystem”, PROC. of the IEEE, Vol. 82, No. 9, pp. 1449-1466, Sep., 1994.
[7] S. Mohan and R.Jain, “Two user location strategies for personal communications services”, IEEE Personal Communication, pp. 42-50, First Quarter 1994.
[8] F. V. Baumann and I. G. Niemegeers, “A evaluation of location management procedures”, in IEEE ICUPCR’94, pp. 359-364, 1994
[9] G. P. Pollini, K. S. Meier-Hellstern and D. J. Goodman, “Signaling traffic volume generated by mobile and personal communications”, IEEE Communication Magzine, pp. 60-65,June 1995.
[10] H. Jung, S. Mishra and O. K. Tonguz, “Efficient location management in PCS”, IEEE, pp. 284-288, 1995.
[11] I. Seskar, S. V. Maric, J. Holtzman and J. Wasserman, “Rate of location area updates in cellular systems”, in IEEE VTC’92, pp. 694-697,1992.
[12] U. Madhow, M. L. Honig, and K. Steiglitz, “Optimization of wireless resources for personal communications of mobility tracking”, IEEE Trans. on Networking, Vol. 3, No. 6, pp.698-707, Dec. 1995.
[13] A. Bar-Noy, I. Kessler,and M. Sidi,“Mobile users:To update or not update?”, ACM/Baltzer Wireless Networks , Vol. 1, No. 2, pp. 175-185 ,1995.
[14] M. Shirota, Y. Yoshida and F. Kubota,“Statistical paging area selection scheme (SPAS) for cellular mobile communication systems”, in IEEE VTC’94, pp. 367-370, 1994.
[15] R. C. Shyu and C. C. Lu, “A study of dynamic location update strategies for wireless personal communications”, Thesis for Master degree, Depart. of Elec. Eng., NTHU, Taiwan, R. O. C., 1996.
[16] S. J. Kim, and C. Y. Lee, “Modeling and analysis of the dynamic location registration and paging in micro cellular systems”, IEEE Trans. on Vehicular Tech., Vol. 45, No. 1, pp. 82-90, Feb. , 1996.
[17] A. Abutaleb and V. O. K. Li, “Location update optimization in wireless personal communication systems”, ACM/Baltzer Wireless Networks , Vol 3, No.3, pp. 205-216, 1997.
[18] G. L. Lyberopoulos, J. G. Markoulidakis, et al., “Intelligent paging strategies for third generation mobile telecommunication systems”, IEEE Trans. on Vehicular Tech., Vol. 44, No. 3, pp. 543-552, Aug., 1995.
[19] J. G. Markoulidakis ,and E. D. Sykas, “Method for efficient location area planning in mobile telecommunications”, Electronics Letters 9th, Vol. 29 ,No. 25, pp. 2165-2166, Dec., 1993.
[20] S. Okasaka, S. Onoe, S. Yasuda, and A. Maebara, “A new location updating method for digital cellular systems”, in Proc. IEEE Veh. Technol. Conf., pp. 345-350, 1991.
[21] A. Bar-Noy, I. Kessler, “Tracking mobile users in wireless networks”, IEEE Trans. on Information theory, Vol. 39, No. 6, pp. 1877-1884, Nov., 1993.
[22] R. C. Larson, “Markov models of signpost sensor AVL systems”, Trans. Science, Vol. 12, No. 4, pp. 331-352, 1978.
[23] R. A. Howard, Dynamic probabilistic system, Volume I: Markov models, John Wiley&sons, New York, 1971.
[24] The Traffic Control Division of Taipei, The characteristics of traffic flow in Taipei, The city government of Taipei, Taipei, Taiwan, June 1996.
[25] EIA/TIA, Mobile Station-Base station Compatibility Standard for Dual-Mode Wide Band Spread Spectrum Cellular System, Technical Report IS-95, EIA/TIA, 1993.
[26] R. F. Chang and K. T. Chen, “Dynamic mobility tracking for wireless personal communication networks”, in IEEE ICUPC, pp. 448-452, 1997.
[27] C. Rose and R. Yates, “Minimizing the average cost of paging under delay constraints”, ACM/Baltzer Wireless Networks , Vol. 1, No. 2, pp. 211-219, 1995.
[28] J. S. M. Ho and I. F. Akyildiz, “Mobile user location update and paging under delay constraints”, ACM/Baltzer Wireless Networks , Vol. 1, No. 4, pp. 413-425, 1995.
[29] I. F. Akyildiz, J. S. M. Ho and Y. B. Lin, “Movement-based location update and selective paging for PCS networks”, IEEE/ACM Trans. on Networking, Vol. 4, No. 4, pp. 629-638, 1996.
[30] A. Abutaleb and V. O. K. Li, “Paging strategy optimization in wireless personal communication systems”, ACM/Baltzer Wireless Networks , Vol 3, No.3, pp. 195-204, 1997.
[31] S. Madhavapeddy, K. Basu and A. Roberts, “Adaptive paging algorithms for cellular systems”, in Proc. IEEE Vehic. Tech. Conf., pp. 976-980, 1995.
[32] H. C. Lee and J. Sun, “Mobile location tracking by optimal paging zone partitioning”, in IEEE ICUPC, vol. 1, pp. 168-172, 1997.
[33] D. Gu and S. S. Rappaport, “A dynamic location tracking strategy for mobile communication systems”, in Proc. IEEE VTC’98, pp. 259-263, 1998.
[34] R. F. Chang and K. T. Chen, ” Dynamic paging strategy in wireless personal communication networks”, in Proceedings of the 1997 International Symposium on Communications, Vol. 1, pp. 50-54, 1997.
[35] W. Wang, I. F. Akyildiz and G. L. Stuber, “An optimal paging scheme for minimizing signaling costs under delay bounds”, IEEE Communication Letters, Vol. 5, No. 2, pp. 43-45, Feb., 2001.
[36] J. M. Oltra, V. C. Giner and P. G. Escalle, “Evaluation of tracking local strategies in wireless networks with stochastic activity networks”, in IEEE ICUPC’98, Vol. 1, pp. 735-740, 1998.
[37] T. X. Brown and S. Mohan, “Mobility management for personal communications systems”, IEEE Trans. on Vehicular Technology, Vol. 46, No. 2, pp. 269-278, May 1997.
[38] O. K. Tonguz, S. Mishra, and H. Jung, “A simple analytical framework for location management in personal communication systems”, IEEE Trans. on Vehicular Technology, Vol. 47, No. 2, pp. 428-439, May 1998.
[39] H. C. Lee and J. Sun, “Mobile location tracking by optimal paging zone partitioning”, in 6th IEEE International Conference on Universal Personal Communications Record, pp. 168-172, 1997.
[40] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, Eleventh printing, MaGraw-Hill book company, New York, 1994.
[41] C. Rose and R. Yates, “Ensemble polling strategies for increased paging capacity in mobile communication networks”, ACM/Baltzer Wireless Networks, vol. 3, No. 2, pp. 159-167, 1997.
[42] R. Rezaiifar and A. M. Makowski, “From optimal search theory to sequential paging in cellular networks”, IEEE J. Select. Areas Commun., vol. 15, no. 7, pp. 1253-1264, 1997.
[43] S. Nanda, “Teletraffic models for urban and suburban microcells: cell sizes and handoff rates”, IEEE Trans. on Vehicular Tech., Vol. 42, No. 4, pp. 673-681, Nov., 1993.