skip to main content
article

Efficient location area planning for personal communication systems

Published: 01 April 2006 Publication History

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(log n) 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]
{1} M. Mouly and M. B. Pautet, The GSM System For Mobile Communication . Paris, France: Telecom Publishing, Jun. 1992.
[2]
{2} I. F. Akyildiz, J. McNair, J. S. M. Ho, H. Uzunalioglu, and W. Wang, "Mobility management in next generation wireless systems," Proc. IEEE, vol. 87, no. 8, pp. 1347-1385, Aug. 1999.
[3]
{3} 3rd Generation Partnership Project, Technical Specification Group Core Network, Location Management Procedures (Release 5), 3GPP, Boston, MA, USA, and London, U.K. 3GPP TS 23.012 V5.0.0, Mar. 2001.
[4]
{4} B. Jabbari, G. Colombo, A. Nakajima, and J. Kulkarni, "Network issues for wireless communication," IEEE Commun. Mag., vol. 33, no. 1, pp. 88-99, Jan. 1995.
[5]
{5} R. Steele, J. Whitehead, and W. C. Wong, "Network issues for wireless communication," IEEE Commun. Mag., vol. 33, no. 1, pp. 80-87, Jan. 1995.
[6]
{6} V. Wong and V. Leung, "Location management for next-generation personal communciations network," IEEE Network, vol. 14, no. 5, pp. 18-24, Sep./Oct. 2000.
[7]
{7} S. Okasaka, S. Onoe, S. Yasuda, and A. Maebara, "A new location updating method for digital cellular systems," in Proc. 41st IEEE Vehicular Technology Conf. (VTC'41), St. Louis, MO, May 1991, pp. 345-350.
[8]
{8} P. G. Escalle, V. C. Giner, and J. M. Oltra, "Reducing location updates and paging costs in a PCS network," IEEE Trans. Wireless Commun., vol. 1, no. 1, pp. 200-209, Jan. 2002.
[9]
{9} M. Shirota, Y. Yoshida, and F. Kubota, "Statistical paging area selection scheme (spas) for cellular mobile communication systems," in Proc. 44th IEEE Vehicular Technology Conf. (VTC'44), 1994, vol. 1, pp. 367-370.
[10]
{10} S. Mishra and O. K. Tonguz, "Most recent interaction area and speed-based intelligent paging in PCS," in Proc. 47th IEEE Vehicular Technology Conf. (VTC'47), 1997, vol. 2, pp. 505-509.
[11]
{11} C. Rose and R. Yates, "Minimizing the average cost of paging under delay constraints," ACM-Baltzer J. Wireless Netw., vol. 1, no. 2, pp. 211-219, Jul. 1995.
[12]
{12} Y. Bejerano and I. Cidon, "Efficient location management based on moving location areas," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 3-12.
[13]
{13} H. Xie, S. Tabbane, and D. J. Goodman, "Dynamic location area management and performance analysis," in Proc. 43th IEEE Vehicular Technology Conf. (VTC'43), May 1993, pp. 536-539.
[14]
{14} Z. Lei and C. Rose, "Wireless subscriber mobility management using adaptive individual location areas for PCS systems," in Proc. IEEE Int. Conf. Communications (ICC'98), 1998, vol. 3, pp. 1390-1394.
[15]
{15} J. Ming-Hui, H. Jorng-Tzong, and H.-K. Wu, "Personal paging area design based on mobiles moving behaviors," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, vol. 1, pp. 21-30.
[16]
{16} G. P. Pollini and I. Chih-Lin, "A profile-based location strategy and its performance," IEEE J. Sel. Areas Commun., vol. 15, no. 8, pp. 1415-1424, Oct. 1997.
[17]
{17} S. K. Sen, A. Bhattacharya, and S. K. Das, "A selective location update strategy for PCS users," ACM-Baltzer J. Wireless Netw., vol. 5, no. 5, pp. 313-326, Oct. 1999.
[18]
{18} A. Bhattacharya and S. K. Das, "Lezi-update: an information-theoritic approach to track mobile users in PCS networks," in Proc. ACM/IEEE MobiCom '99, Seattle, WA, Aug. 1999, pp. 1-12.
[19]
{19} A. Bar-Noy, I. Kessler, and M. Sidi, "Mobile users: to update or not to update?," ACM-Baltzer J. Wireless Netw., vol. 1, no. 2, pp. 175-185, Jul. 1995.
[20]
{20} I. F. Akyildiz and J. S. M. Ho, "Dynamic mobile user location update for wireless PCS networks," ACM-Baltzer J. Wireless Netw., vol. 1, no. 2, pp. 187-196, Jul. 1995.
[21]
{21} I. F. Akyildiz, J. S. M. Ho, and Y. Lin, "Movement-based location update and selective paging for PCS networks," IEEE/ACM Trans. Netw., vol. 4, no. 4, pp. 629-638, Aug. 1996.
[22]
{22} I. F. Akyildiz and J. S. M. Ho, "A mobile user location update and paging mechanism under delay constrains," ACM-Baltzer J. Wireless Netw., vol. 1, no. 4, pp. 413-425, Dec. 1995.
[23]
{23} R. Thomas, H. Gilbert, and G. Mazziotto, "Influence of the moving of the mobile stations on the performance of a radio mobile cellular network," presented at the 3rd Nordic Seminar, Copenhagen, Denmark, Sep. 1988.
[24]
{24} 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 Proc. 8th Int. Teletraffic Seminar, Genova, Italy, Oct. 1992, pp. 261-270.
[25]
{25} M. Vudali, "The location area design problem in cellular and personal communications systems," in Proc. 5th IEEE Int. Conf. Universal Personal Communications, 1996, vol. 2, pp. 591-595.
[26]
{26} C.-L. I, G. P. Pollini, and R. D. Gitlin, "PCS mobility management using the reverse virtual call setup algorithm," IEEE/ACM Trans. Netw., vol. 5, no. 1, pp. 13-24, Feb. 1997.
[27]
{27} C. U. Saraydar and C. Rose, "Location area design using population and traffic data," in Proc. Conf. Information Science and Systems (CISS'98), Princeton, NJ, Mar. 1998, pp. 739-744.
[28]
{28} 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 Proc. 49th IEEE Vehicular Technology Conf. (VTC'49), 1999, vol. 4, pp. 2119-2123.
[29]
{29} I. Demirkol, C. Ersoy, M. U. Caglayan, and H. Delic, "Location area planning in cellular networks using simulated annealing," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 13-20.
[30]
{30} P. R. L. Gondim, "Genetic algorithm and the location area partition problem in cellular networks," in Proc. 46th IEEE Vehicular Technology Conf. (VTC'46), 1996, vol. 3, pp. 1835-1838.
[31]
{31} J. Plehn, "The design of location areas in a gsm-network," in Proc. 45th IEEE Vehicular Technology Conf. (VTC'45), 1995, vol. 2, pp. 871-875.
[32]
{32} I. G. Tollis, "Optimal partitioning of cellular networks," in Proc. IEEE Int. Conf. Communications (ICC'96), 1996, vol. 3, pp. 1377-1381.
[33]
{33} M. Munguia-Macario, D. Munoz-Rodriguez, and C. Molina, "Optimal adaptive location area design and inactive location areas," in Proc. 47th IEEE Vehicular Technology Conf. (VTC'47), 1997, vol. 1, pp. 510-514.
[34]
{34} C. U. Saraydar, O. E. Kelly, and C. Rose, "One-dimensional location area design," IEEE Trans. Veh. Technol., vol. 49, no. 5, pp. 1626-1632, Sep. 2000.
[35]
{35} M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman, 1979.
[36]
{36} M. M. Deza and M. Laurent, Geometry of Cuts and Metrics. Berlin-Heidelberg, Germany: Springer-Verlag, 1997.
[37]
{37} V. V. Vazirani, Approximation Algorithms. New York: Springer-Verlag, 2001.
[38]
{38} V. V. Vazirani, N. Garg, and M. Yannakakis, "Approximate max-flow min-(multi) cut theorems and their applications," SIAM J. Computing, vol. 25, pp. 235-251, 1996.
[39]
{39} S. Plotkin, P. Klein, and S. Rao, "Excluded minors, network decomposition, and multicommodity flow," in Proc. 25th ACM Symp. Theory of Computing, 1993, pp. 682-690.
[40]
{40} E. Tardos and V. V. Vazirani, "Improved bounds for the max-flow min-multicut for planar and kr,r -free graphs," Inf. Process. Lett., vol. 47, pp. 77-80, 1993.
[41]
{41} B. Efron and R. J. Tibshirani, An Introduction to the Bootstrap, 1st ed. New York: Chapman & Hall, 1993.
[42]
{42} M. Charikar, V. Guruswami, and A. Wirth, "Clustering with qualitative information," in IEEE Symp. Foundations of Computer Science, 2003, pp. 524-533.
[43]
{43} E. D. Demaine and N. Immorlica, "Correlation clustering with partial information," in Proc. 6th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2003, pp. 1-13.
[44]
{44} D. Emanuel and A. Fiat, "Correlation clustering-minimizing disagreements on arbitrary weighted graphs," in Proc. 11th Eur. Symp. Algorithms, 2003, pp. 208-220.
[45]
{45} N. Bansal, A. Blum, and S. Chawla, "Correlation clustering," Machine Learning, vol. 56, pp. 89-113.

Cited By

View all
  • (2017)Synthesizing Mapping Relationships Using Table CorpusProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3064010(1117-1132)Online publication date: 9-May-2017
  • (2016)Automatic Discovery of Attribute Synonyms Using Query Logs and Table CorporaProceedings of the 25th International Conference on World Wide Web10.1145/2872427.2874816(1429-1439)Online publication date: 11-Apr-2016
  • (2016)Higher-order segmentation via multicutsComputer Vision and Image Understanding10.1016/j.cviu.2015.11.005143:C(104-119)Online publication date: 1-Feb-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 14, Issue 2
April 2006
217 pages

Publisher

IEEE Press

Publication History

Published: 01 April 2006
Published in TON Volume 14, Issue 2

Author Tags

  1. cellular systems
  2. location area planning
  3. mobility management
  4. personal communication system
  5. terms-approximation algorithms

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Synthesizing Mapping Relationships Using Table CorpusProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3064010(1117-1132)Online publication date: 9-May-2017
  • (2016)Automatic Discovery of Attribute Synonyms Using Query Logs and Table CorporaProceedings of the 25th International Conference on World Wide Web10.1145/2872427.2874816(1429-1439)Online publication date: 11-Apr-2016
  • (2016)Higher-order segmentation via multicutsComputer Vision and Image Understanding10.1016/j.cviu.2015.11.005143:C(104-119)Online publication date: 1-Feb-2016
  • (2015)On dynamic signaling congestion mitigation by overlapping tracking area listsJournal of Network and Computer Applications10.1016/j.jnca.2015.03.00953:C(164-172)Online publication date: 1-Jul-2015
  • (2015)A grouping biogeography-based optimization for location area planningNeural Computing and Applications10.1007/s00521-015-1856-526:8(2001-2012)Online publication date: 1-Nov-2015
  • (2013)Gateway relocation avoidance-aware network function placement in carrier cloudProceedings of the 16th ACM international conference on Modeling, analysis & simulation of wireless and mobile systems10.1145/2507924.2508000(341-346)Online publication date: 3-Nov-2013
  • (2013)An adaptive location management scheme for mobile broadband cellular systemsTelecommunications Systems10.1007/s11235-011-9665-352:1(299-315)Online publication date: 1-Jan-2013
  • (2013)RETRACTED ARTICLEComputing10.1007/s00607-012-0210-395:1(25-66)Online publication date: 1-Jan-2013
  • (2010)A new strategy for managing user's locations in PCS networks using hot spots topology: discussion and analysisInternational Journal of Mobile Network Design and Innovation10.1504/IJMNDI.2010.0380983:3(169-190)Online publication date: 1-Jan-2010
  • (2008)Performance improvement of LTE tracking area designProceedings of the 6th ACM international symposium on Mobility management and wireless access10.1145/1454659.1454673(77-84)Online publication date: 30-Oct-2008
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media