Mining call and mobility data to improve paging efficiency in cellular networks

ABSTRACT

Locating mobile users and devices efficiently is a critical operation in cellular networks. This is done using a combination of location update(by the mobile) and paging (by the network). The paging scheme determines how and where to search for a mobile user given the latestlocation update information from that user. In this paper, we considerhow to increase the efficiency of the paging scheme.

Much previous work has relied on simulation or modeling to design and evaluate the performance of proposed paging schemes. We take a different, data-driven approach in how we design and evaluate our solution. Specifically, we mine more than 300 million call records from a large cellular operator to characterize user mobility and create mobility profiles. We then develop a family ofprofile-based paging techniques, considering both static schemes and dynamic schemes which adapt as user profiles continuously get updated. We find that our paging techniques can dramatically reducesignaling load (up to 80%) with minimal increase in paging delay (usually less than 10%).

REFERENCES

• 1: 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]
• 2: William Enck , Patrick Traynor , Patrick McDaniel , Thomas La Porta, Exploiting open functionality in SMS-capable cellular networks, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102171]
• 3: Jérémy Serror , Hui Zang , Jean C. Bolot, Impact of paging channel overloads or attacks on a cellular network, Proceedings of the 5th ACM workshop on Wireless security, September 29-29, 2006, Los Angeles, California [doi>10.1145/1161289.1161304]
• 4: Patrick Traynor , William Enck , Patrick McDaniel , Thomas La Porta, Mitigating attacks on open functionality in SMS-capable cellular networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161111]
• 5: Emir Halepovic , Carey Williamson, Characterizing and modeling user mobility in a cellular data network, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada [doi>10.1145/1089803.1089969]
• 6: 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]
• 7: 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]
• 8: C. Rose, Minimizing the average cost of paging and registration: a timer-based method, Wireless Networks, v.2 n.2, p.109-116, June 1996 [doi>10.1007/BF01225634]
• 9: 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]
• 10: M. Verkama, "A simple implementation of distance-based location updates," in IEEE 6th Intl Conf. Universal Personal Communications Record, San Diego, CA, USA, 1997, pp. 163--167.
• 11: 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]
• 12: H. Wu, M.-H. Jin, and J.-T. Horn, "Personal paging area design based on mobile's moving behaviors," in Proc. IEEE Infocom '01, Anchorage, AK, Apr. 2001, pp. 21--30.
• 13: Yang Xiao , Kui Wu, Location Update for PCS Networks with a Fractional Movement Threshold, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.825, May 19-22, 2003
• 14: 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]
• 15: C. K. Ng , H. W. Chan, Enhanced Distance-Based Location Management of Mobile Communication Systems Using a Cell Coordinates Approach, IEEE Transactions on Mobile Computing, v.4 n.1, p.41-55, January 2005 [doi>10.1109/TMC.2005.12]
• 16: A. Bar-Noy, Y. Feng, and M. Golin, "Paging mobile users efficiently and optimally," Proc. IEEE Infocom 2007, Anchorage, AK, Apr. 2007.
• 17: "Cellular Radiotelecommunications Intersystem Operations," EIA/TIA IS.41.
• 18: Guang Wan , Eric Lin, A dynamic paging scheme for wireless communication systems, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.195-203, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262147]
• 19: B. Liang and Z. J. Haas, "Predictive distance-based mobility management for PCS networks," in Proc. IEEE Infocom'99, New York, NY, pp. 1377--84.
• 20: H.-W. Hwang, M.-F. Chang, and C.-C. Tseng, "A direction-based location update scheme with a line-paging strategy for PCS networks," in IEEE Communications Letters, 2000, pp. 149--151.
• 21: C. Rose, "State-based paging/registration: a greedy technique," IEEE Transactions on Vehicular Technology, no. 1, pp. 166--173, 1999.
• 22: G. P. Pollini and C.-L. I, "A profile-based location strategy and its performance," IEEE Journal on Selected Areas in Communications, vol. 15, no. 8, pp. 1415--1424, 1997.
• 23: P. G. Escalle, V. C. Giner, and J. M. Olta, "Reducing location update and paging costs in a pcs network," IEEE Transactions Wireless Communications, vol. 1, no. 1, Jan. 2002.
• 24: Jianting Zhang , Le Gruenwald, Spatial and Temporal Aware, Trajectory Mobility Profile Based Location Management for Mobile Computing, Proceedings of the 13th International Workshop on Database and Expert Systems Applications, p.716-720, September 02-06, 2002
• 25: R. Jain, Y.-B. Lin, C. Lo, and S. Mohan, "A caching strategy to reduce network impacts of pcs," IEEE Journal on Selected Areas in Communications, vol. 12, no. 8, Oct. 1994.
• 26: 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]
• 27: Francois Baccelli , Sergei Zuyev, Poisson-Voronoi Spanning Trees with Applications to the Optimization of Communication Networks, Operations Research, v.47 n.4, p.619-631, April 1999 [doi>10.1287/opre.47.4.619]
• 28: G. Y. Lee and Y. Lee, "Numerical analysis of optimum timer value for time-based location registration," IEEE Communications Letters, vol. 6, no. 10, pp. 431--433, 2002.
• 29: M. Kim, D. Kotz, and S. Kim, "Extracting a mobility model from real user traces," Proc. IEEE Infocom'06, April 2006.
• 30: Minkyong Kim , David Kotz, Periodic properties of user mobility and access-point popularity, Personal and Ubiquitous Computing, v.11 n.6, p.465-479, August 2007 [doi>10.1007/s00779-006-0093-4]
• 31: F. Bai, N. Sadagopan, B. Krishnamachari, and A. Helmy, "Modeling path duration distributions in Manets and their impact on routing performance," in IEEE Journal on Selected Areas in Communications, vol. 22, no. 7, Sept. 2004.
• 32: A. Chaintreau and et al., "Impact of human mobility on the design of opportunistic forwarding algorithms," in Proc. IEEE Infocom'06, Barcelona, Apr. 2006.
• 33: Amit Jardosh , Elizabeth M. Belding-Royer , Kevin C. Almeroth , Subhash Suri, Towards realistic mobility models for mobile ad hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939008]
• 34: Carey Williamson , Emir Halepovic , Hongxia Sun , Yujing Wu, Characterization of CDMA2000 Cellular Data Network Traffic, Proceedings of the The IEEE Conference on Local Computer Networks 30th Anniversary, p.712-719, November 15-17, 2005 [doi>10.1109/LCN.2005.37]
• 35: "Mobile radio interface layer 3 specifications," 3GPP GSM 04.08, Version 7.8.0, Oct. 2000.
• 36: "Upper layer (layer 3) signaling standard for CDMA2000 spread spectrum systems, release D," 3GPP2 C.S0005-D, Version 1.0, Feb. 2004.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

General Terms:
Design, Measurement, Performance, Security

Keywords:
CDMA, data mining, mobility, paging