Efficient location area planning for personal communication systems

ABSTRACT

A central problem in personal communication systems is to optimize bandwidth usage, while providing Quality of Service (QoS) guarantees to mobile users. Network mobility management, and in particular, location management, consumes a significant portion of bandwidth, which is a necessary overhead for supporting mobile users. We focus our efforts on minimizing this overhead. Unlike previous works, we concentrate on optimizing existing schemes, and so the algorithms we present are easily incorporated into current networks. We present the first polynomial time approximation algorithms for minimum bandwidth location management. In planar graphs, our algorithm provably generates a solution that uses no more than a constant factor more bandwidth than the optimal solution. In general graphs, our algorithm provably generates a solution that uses just a factor O(logn) more bandwidth than optimal where n is the number of base stations in the network. We show that, in practice, our algorithm produces near-optimal results and outperforms other schemes that are described in the literature. For the important case of the line graph, we present a polynomial-time optimal algorithm. Finally, we illustrate that our algorithm can also be used for optimizing the handoff mechanism.

REFERENCES

• 1: Michel Mouly , Marie-Bernadette Pautet , Thomas Haug, The GSM System for Mobile Communications, Telecom Publishing, 1992
• 2: I. F. Akyildiz, J. McNair, J. S. M. Ho, H. Uzunalioglu, and W. Wang. Mobility management in next generation wireless systems. IEEE Proceedings Journal, 87(8):1347--1385, August 1999.
• 3: 3GPP, Boston, MA, USA and London, UK. 3GPP TS 23.012 V5.0.0, 3rd Generation Partnership Project, Technical Specification Group Core Network, Location Management Procedures (Release 5), March 2001.
• 4: B. Jabbari, G. Colombo, A. Nakajima, and J. Kulkarni. Network issues for wireless communication. IEEE Communications Magazine, 33(1):88 --99, January 1995.
• 5: R. Steele, J. Whitehead, and W. C. Wong. Network issues for wireless communication. IEEE Communications Magazine, 33(1):80--87, January 1995.
• 6: S. Okasaka, S. Onoe, S. Yasuda, and A. Maebara. A new location updating method for digital cellular systems. In Proceeding of the IEEE $41^st$ Vehicular Technology Conference, VTC'41, pages 345--350, St. Louis, Missouri, May 1991.
• 7: P. G. Escalle, V. C. Giner, and J. M. Oltra. Reducing location updates and paging costs in a pcs network. IEEE Transaction on Wireless Communications, 1(1):200--209, January 2002.
• 8: M. Shirota, Y. Yoshida, and F. Kubota. Statistical paging area selection scheme (spas) for cellular mobile communication systems. In Proceeding of the IEEE $44^th$ Vehicular Technology Conference, VTC'44, volume 1, pages 367--370, 1994.
• 9: S. Mishra and O. K. Tonguz. Most recent interaction area and speed-based intelligent paging in pcs. In Proceeding of the IEEE $47^th$ Vehicular Technology Conference, VTC'47, volume 2, pages 505--509, 1997.
• 10: Christopher Rose , Roy Yates, Minimizing the average cost of paging under delay constraints, Wireless Networks, v.1 n.2, p.211-219, 1995 [doi>10.1007/BF01202543]
• 11: Y. Bejerano and I. Cidon. Efficient location management based on moving location areas. In Proceedings of IEEE INFOCOM'01, pages 3--12, Anchorage, Alaska, USA, April 2001.
• 12: Hai Xie, Sami Tabbane, and David J. Goodman. Dynamic location area management and performance analysis. In Proceeding of the IEEE $43^th$ Vehicular Technology Conference, VTC'43, pages 536--539, May 1993.
• 13: Z. Lei and C. Rose. Wireless subscriber mobility management using adaptive individual location areas for pcs systems. In IEEE International Conference on Communications, ICC'98, volume 3, pages 1390 --1394, 1998.
• 14: Zhuyu Lei , Cem U. Saraydar , Narayan B. Mandayam, Paging area optimization based on interval estimation in wireless personal communication networks, Mobile Networks and Applications, v.5 n.1, p.85-99, March 2000 [doi>10.1023/A:1019135923695]
• 15: J. Ming-Hui, H. Jorng-Tzong, and H-K. Wu. Personal paging area design based on mobiles moving behaviors. In Proceedings of IEEE INFOCOM'01, volume 1, pages 21--30, Anchorage, Alaska, USA, April 2001.
• 16: S. Tabbane. An alternative strategy for location tracking. IEEE Journal on Selected Areas in Communications, JSAC, 13(5):880--892, June 1995.
• 17: G. P. Pollini and I. Chih-Lin. A profile-based location strategy and its performance. IEEE Journal on Selected Areas in Communications, JSAC, 15(8):1415 --1424, October 1997.
• 18: Sanjoy K. Sen , Amiya Bhattacharya , Sajal K. Das, A selective location update strategy for PCS users, Wireless Networks, v.5 n.5, p.313-326, Oct. 1999 [doi>10.1023/A:1019119632106]
• 19: Amiya Bhattacharya , Sajal K. Das, LeZi-update: an information-theoretic approach to track mobile users in PCS networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.1-12, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313457]
• 20: Amotz Bar-Noy , Ilan Kessler , Moshe Sidi, Mobile users: to update or not to update?, Wireless Networks, v.1 n.2, p.175-185, 1995 [doi>10.1007/BF01202540]
• 21: Ian F. Akyildiz , Joseph S. M. Ho, Dynamic mobile user location update for wireless PCS networks, Wireless Networks, v.1 n.2, p.187-196, 1995 [doi>10.1007/BF01202541]
• 22: Ian F. Akyildiz , Joseph S. M. Ho , Yi-Bing Lin, Movement-based location update and selective paging for PCS networks, IEEE/ACM Transactions on Networking (TON), v.4 n.4, p.629-638, Aug. 1996 [doi>10.1109/90.532871]
• 23: Joseph S. M. Ho , Ian F. Akyildiz, Mobile user location update and paging under delay constraints, Wireless Networks, v.1 n.4, p.413-425, 1995 [doi>10.1007/BF01985754]
• 24: B. Liang and Z. J. Haas. Predictive distance-based mobility management for pcs networks. In Proceedings of IEEE INFOCOM'01, volume 3, pages 1377--1384, New York, NY, USA, March 1999.
• 25: Guang Wan , Eric Lin, Cost reduction in location management using semi-realtime movement information, Wireless Networks, v.5 n.4, p.245-256, July 1999 [doi>10.1023/A:1019155212541]
• 26: Z. Lei and C. Rose. Probability criterion based location tracking approach for mobility management of personal communication systems. In IEEE Global Telecommunications Conference, GLOBECOM '97, volume 2, pages 977--981, 1997.
• 27: V. Wong and V. Leung. Location management for next-generation personal communciations network. IEEE Network, pages 18--24, September/October 2000.
• 28: R. Thomas, H. Gilbert, and G. Mazziotto. Influence of the moving of the mobile stations on the performance of a radio mobile cellular network. In Proceedings 3rd Nordic Seminar, Copenhagen, Denmark, September 1998.
• 29: E. Alonso, K. S. Meier-Hellstern, and G. P. Pollini. Influence of cell geometry on handover and registration rates in cellular and universal personal telecommunications networks. In Proceedings 8th Int. Teletraffic Seminar, pages 261--270, Genova, Italy, October 1992.
• 30: M. Vudali. The location area design problem in cellular and personal communications systems. In 5th IEEE International Conference on Universal Personal Communications, volume 2, pages 591--595, 1996.
• 31: Chih-Lin I , Gregory P. Pollini , Richard D. Gitlin, PCS mobility management using the reverse virtual call setup algorithm, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.13-24, Feb. 1997 [doi>10.1109/90.554718]
• 32: C. U. Saraydar and C. Rose. Location area design using population and traffic data. In Proceedings of Conference on Information Science and Systems, CISS 1998, pages 739--744, Princeton, NJ, USA, March 1998.
• 33: P. R. L. Gondim. Genetic algorithm and the location area partition problem in cellular networks. In Proceeding of the IEEE $46^th$ Vehicular Technology Conference, VTC'46, volume 3, pages 1835 --1838, 1996.
• 34: P. Demestichas, E. Tzifa, V. Demesticha, N. Georgantas, G. Kotsakis, M. Kilanioti, M. Striki, M. E. Anagnostou, and M. E. Theologou. Control of the location update and paging signaling load in cellular systems by means of planning tools. In Proceeding of the IEEE 49th Vehicular Technology Conference, VTC'49, volume 4, pages 2119--2123, 1999.
• 35: I. Demirkol, C. Ersoy, M. U. Caglayan, and H. Delic. Location area planning in cellular networks using simulated annealing. In Proceedings of IEEE INFOCOM'01, Anchorage, Alaska, April 2001.
• 36: J. Plehn. The design of location areas in a gsm-network. In Proceeding of the IEEE 45th Vehicular Technology Conference, VTC'45, volume 2, pages 871--875, 1995.
• 37: I. G. Tollis. Optimal partitioning of cellular networks. In IEEE International Conference on Communications, ICC'96, volume 3, pages 1377 --1381, 1996.
• 38: M. Munguia-Macario, D. Munoz-Rodriguez, and C. Molina. Optimal adaptive location area design and inactive location areas. In Proceeding of the IEEE 47th Vehicular Technology Conference, VTC'47, volume 1, pages 510--514, 1997.
• 39: C. U. Saraydar, O. E. Kelly, and C. Rose. One-dimensional location area design. IEEE Transactions on Vehicular Technology, 49(5):1626 --1632, September 2000.
• 40: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 41: M. M. Deza and M. Laurent. Geometry of cuts and metrics. Springer-Verlag, Berlin-Heidelberg, 1997.
• 42: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 43: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
• 44: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 45: Éva Tardos , Vijay V. Vazirani, Improved bounds for the max-flow min-multicut ratio for planar and Kr,r-free graphs, Information Processing Letters, v.47 n.2, p.77-80, Aug. 20, 1993 [doi>10.1016/0020-0190(93)90228-2]
• 46: B. Efron and R. J. Tibshirani. An Introduction to the Bootstrap. Chapman & Hall, New York, NY, first edition, 1993.
• 47: Moses Charikar , Venkatesan Guruswami , Anthony Wirth, Clustering with Qualitative Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.524, October 11-14, 2003
• 48: Erik D. Demaine and Nicole Immorlica. Correlation clustering with partial information. Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2003.
• 49: Dotan Emanuel and Amos Fiat. Correlation clustering --- minimizing disagreements on arbitrary weighted graphs. European Symp. on Algorithms, 2003.
• 50: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.238, November 16-19, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Management, Performance, Theory

Keywords:
approximation algorithms, cellular systems, location area planning, mobility management, personal communication system