Information-theory based optimal location management schemes for integrated multi-system wireless networks

ABSTRACT

In a multi-system environment where a mobile node can utilize multiple interfaces and simultaneously connect to multiple providers, new opportunities exist for efficient location management strategies spanning heterogeneous cellular wireless networks. In this paper, an integrated framework is developed for location management in such a multi-system, fourth generation (4G) wireless networks. This information-theoretic framework allows each individual sub-system to operate fairly independently, and does not require the knowledge of individual sub-network topologies. An efficient location management in such a loosely coupled network is designed by having a mobile node view its movement as a vector-valued sequence, and then transmit this sequence in an entropy coded form to the network. We demonstrate how an intelligent, integrated paging strategy must consider the joint residence probability distribution of a mobile node in multiple sub-networks. We prove that the determination of an optimal paging sequence is NP-complete, and also propose an efficient greedy heuristic to compute the paging sequence, both without and with bounds on the paging delay. Three different location tracking strategies are proposed and evaluated; they differ in their degrees of centralized control and provide tradeoff between the location update and paging costs. Simulation experiments demonstrate that our proposed schemes can result in more than 50% savings in both update and paging costs, in comparison with the basic movement-based, multi-system location management strategy.

REFERENCES

• 1: I. F. Akyildiz and W. Wang, "A dynamic location management scheme for next-generation multitier PCS systems," IEEE Trans. Wireless Commun., vol. 1, no. 1, pp. 178-189, Jan. 2002.
• 2: A. Bar-Noy and I. Kessler, "Tracking mobile users in wireless communication networks," IEEE Trans. Inf. Theory, vol. 39, no. 6, pp. 1877-1886, Nov. 1993.
• 3: 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]
• 4: R. Berezdivin, R. Breinig, and R. Topp, "Next-generation wireless communications concepts and technologies," IEEE Commun. Mag., vol. 40, no. 3, pp. 108-116, Mar. 2002.
• 5: Amiya Bhattacharya , Sajal K. Das, LeZi-update: an information-theoretic framework for personal mobility tracking in PCS networks, Wireless Networks, v.8 n.2/3, p.121-135, March-May 2002 [doi>10.1023/A:1013759724438]
• 6: Yitzhak Birk , Yaron Nachman, Using direction and elapsed-time information to reduce the wireless cost of locating mobile units in cellular networks, Wireless Networks, v.1 n.4, p.403-412, 1995 [doi>10.1007/BF01985753]
• 7: M. Buddhikot, G. Chandranmenon, S. J. Han, Y. W. Lee, S. Miller, and L. Salgarelli, "Integration of 802.11 and Third Generation wireless data networks," in Proc. of IEEE INFOCOM, Apr. 2003.
• 8: Erdal Cayirci , Ian F. Akyildiz, User Mobility Pattern Scheme for Location Update and Paging in Wireless Systems, IEEE Transactions on Mobile Computing, v.1 n.3, p.236-247, July 2002 [doi>10.1109/TMC.2002.1081758]
• 9: Edith Cohen , Amos Fiat , Haim Kaplan, Efficient sequences of trials, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 11: M. Feder, N. Merhav, and M. Gutman, "Universal prediction of individual sequences," IEEE Trans. Inf. Theory, vol. 38, no. 4, pp. 1258-1270, Jul. 1992.
• 12: 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
• 13: J. N. Kapur and H. K. Kesavan, Entropy Optimization Principles with Applications. New York: Academic, 1992.
• 14: G. P. Pollini and C.-L. I, "A profile-based location strategy and its performance," IEEE J. Select. Areas Commun., vol. 15, no. 8, pp. 1415-1424, 1997.
• 15: 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]
• 16: W. Wang, I. Aykildiz, and G. Stuber, "An optimal paging scheme for minimizing signaling costs under delay bounds," IEEE Commun. Lett., vol. 5, no. 2, pp. 43-45, Feb. 2001.
• 17: Rung-Hung Gau , Zygmunt J. Haas, Concurrent search of mobile users in cellular networks, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.117-130, February 2004 [doi>10.1109/TNET.2003.822662]
• 18: Pars Mutaf , Claude Castelluccia, Hash-based paging and location update using bloom filters: a paging algorithm that is best suitable for IPv6, Mobile Networks and Applications, v.9 n.6, p.627-631, December 2004 [doi>10.1145/1035715.1035723]
• 19: Ana Sanz Merino , Yasuhiko Matsunaga , Manish Shah , Takashi Suzuki , Randy H. Katz, Secure authentication system for public WLAN roaming, Mobile Networks and Applications, v.10 n.3, p.355-370, June 2005 [doi>10.1007/s11036-005-6428-y]
• 20: S. Gros, S. Lein, and S. Steinbrecher, "A multilateral secure payment system for wireless LAN hotspots," in 2nd Int. Conf. on Trust, Privacy and Security in Digital Business (TrusBus '05), Aug. 2005.
• 21: C. Ribeiro, F. Silva, and A. Zuquete, "A roaming authentication solution for wifi using IPSec VPNs with client certificates," in Proc. Terena Network. Conf., June 2004.
• 22: Eugene Shih , Paramvir Bahl , Michael J. Sinclair, Wake on wireless: an event driven energy saving strategy for battery operated devices, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570666]
• 23: W. Spankowski, "Asymptotic properties of data compression and suffix trees," IEEE Trans. Inf. Theory, vol. 39, no. 5, pp. 1647-1659, Sept. 1993.
• 24: J. H. Sun, D. Howie, and J. Sauvola, "Mobility management techniques for next generation wireless networks," in Proc. SPIE, Wireless and Mobile Commun., Oct. 2001, vol. 4586, pp. 155-166.
• 25: Wenye Wang , Ian F. Akyildiz, A cost-efficient signaling protocol for mobility application part (MAP) in IMT-2000 systems, Proceedings of the 7th annual international conference on Mobile computing and networking, p.345-355, July 2001, Rome, Italy [doi>10.1145/381677.381709]
• 26: G. Wu and M. Mizuno, "MIRAI architecture for heterogeneous network," IEEE Commun. Mag., vol. 40, no. 2, pp. 126-134, Feb. 2002.
• 27: T. B. Zaharidis, K. G. Vaxevanakis, C. P. Tsantilas, and N. A. Zervos, "Global roaming in next-generation networks," IEEE Commun. Mag., vol. 40, no. 2, pp. 145-151, Feb. 2002.
• 28: J. Ziv and A. Lempel, "Compression of individual sequences via variable-rate coding," IEEE Trans. Inf. Theory, vol. 24, no. 5, pp. 530-536, Sep. 1978.
• 29: A. Roy, A. Misra, and S. K. Das, "Location update vs. paging tradeoff in cellular networks: An approach based on vector quantization," IEEE Trans. Mobile Comput., vol. 6, no. 12, pp. 1426-1440, Dec. 2007.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

General Terms:
Algorithms, Design, Theory

Keywords:
LZ compression, cellular networks, information theory, location management, multi-system, paging