20 August 1998

Date: Tue, 13 Aug 1996 15:23:52 +0200 To: jya@pipeline.com From: interception <interception@ii-mel.com> Subject: MOBILE PHONE LOCATIONS Source: WINLAB, Rutgers University New BRunswick, NJ 08855 AT&T Bell Laboratories 101 Crawfords Corner Road Holmdel, NJ 07733 Authors: David Goodman; P. Krishnan; Binay Sugla The mobility of phones in a cellular or Personnal Communication Service (PCS) environment introduces the problem of efficiently locating the called phone. In this paper, we present an analysis of the delay and number of messages transmitted in different sequential and parallel search strategies, considering for the first time the issue of queuing on radio paging channels. Our analysis shows that parallel search mya not reduce the time to find a mobile phone if the parameters of the system are unfavorable. We also develop an efficient algorithm for searching with minimum expected number of messages when the location of the phone is given by a probability vector. 1 Introduction In a traditional phone network, each phone is associated with a known geographical location. The numbering scheme for these fixed phones takes advantage of their known location. A relatively simple mapping exists from the telephone number to its geographical location. The introduction of the 800 number service utilized an indirection in this mapping while still exploiting the property that the final number is placed at a known geographical location. The 700 number service, first introduced by AT§T, exploits the fact that the called number may be mapped into one of several fixed numbers using a logic and order specified by the customer. The 500 number service is more advanced in that the customer can have his/her calls forwarded to (virtually) any phone; however the mapping between the customer's 500 number and a standard number must be provided by the customer, e.g., by using a touch-tone phone. The techniques used in the services mentioned above are inadequate for the mobile environment since the location of the final destination (viz. the called phone) is unknown and must be determined before the call is completed. In response to this need, several schemes have been employed and suggested. A centralized paging scheme in which the called phone number is broadcast and the called phone responds is inefficient in the use of radio bandwidth. In the more recent techniques, the basic unit of paging is the cell level. The problem now is to design an efficient search algorithm such that the relevant costs are minimized. A number of research papers address facets of the mobile location problem. The problem is complex because there are several performance criteria including costs of reporting, recording, and retrieving the locations of mobile phones, costs of searching for mobile phones when calls arrive, the probability of a successful search, and delays in finding phones. Tracking and search costs include radio channel occupancy, transmissions in fixed networks, and database transactions. The overall complexity is also important because a scheme that requires a highly distributed real-time system may introduce problems of it own, particularly with respect to reliability. Previous papers [1,2,3,4,5,7,8 on request] address network architecture issues, database structures, and tradeoffs between registration and paging costs. This paper focuses on the search process. We assume that the system that accurate knowledge that a phone is in a "location area [LA]" which consists of a collection of cells. We then examine sequential search strategies for determining the cell in which the phone is located. The search procedure consists of sending paging messages to a group of cells in the location area and waiting for a response from the phone. If no response arrives within a fixed waiting period, the network sends paging messages in another group of cells, and again waits for a response. The procedure continues until the phone responds to a paging message. The quality criteria that we examine are the search delay and the total of number of messages transmitted. An important issue is the queuing delay of paging messages on radio channels. Our probabilistic analysis reveals that parallel search may not reduce the time to find a mobile phone if the parameters of the system are unfavorable. We also develop an efficient algorithm for paging to minimize the total numbers of messages when we know the probability of finding a phone in any specific cell. Our goal in this paper is to study the design implications of our analysis taking into account both the delay incurred and number of messages transmitted. The delay analysis focuses on uniformly distributed traffic and includes the effect of a timeout at each cell. In [9], the authors analyze delay as a function of the mean of the ordered distribution that describes the uncertainly about the location of the mobile phone. For the problem of developing an efficient algorithm for paging to minimize the number of messages when we know the probability of finding a phone in any paging cell, our emphasis in this paper is on on the computational complexity of the solution, while in [10] the authors deal with methods for different types of distributions. IN [6], Madhavapeddy et al. propose methods to empirically compute the probability of a mobile phone being in any paging cell using the registration history. They also develop algorithms to minimize the expected number of messages while searching for a mobile phone; we compare and contrast our algorithms with the ones in [6] in Section 4. The rest of the paper is organized as follows. In Section 2, we present our model. In Section 3, we introduce and present an analysis of sequential and parallel schemes used for locating a mobile phone. The simple analysis in Section 3.1 raises important questions about the issue of queuing delays. IN Section 3.2, we analyze the effect of queuing on radio paging channels, assuming a Poisson call-arrival. In Section 4, we develop an efficient paging strategy to minimize the total number of messages sent in locating the mobile phone when the possible locations of the phone are specified by a probability vector. We conclude in Section 5 with directions for future research. We have looked at the question of queuing delays and derived the result that parallel search may not reduce the delay in searching for a phone if the system is heavily loaded. In particular, our analysis, our analysis sheds light on important design issues in paging in cellular telephone networks. We find that at high loads, the delay decreases significantly in going from 1 to 2 paging groups. When considered along with the number of messages sent, perhaps 2-4 paging groups is a good value; e.g., having 4 paging groups reduces the expected total number of messages (relative to flooding)The minimum is 0.5X, achieved with flooding which leads to a high delay. It would be interesting to study the impact of queuing delay on other results in the literature. We have also presented an efficient method to group stations into paging groups when a probability vector defining the likelihood of finding a phone in any paging area is given, and the goal to minimize the expected number of messages. Our algorithm Divide2 optimally and efficiently partitions the states into Ng = 2 paging groups, an important case as suggested by our delay analysis. For general Ng, our algorithm Group takes worst case time proportional to O(ref.4.2)to determine the optimal partitioning. References [1] B. Awerbuch, D. Peleg. "Concurrent Online Tracking of Mobile Users", Proceedings of the 1991 ACM SIGCOMM, pp. 221-233. [2] A. Bar-Noy, I. Kessler, M. Sidi. "Mobile Users: To Update or not to to Update," Wireless Networks, 1(1), 1995, Preprint. [3] A. Bar-Noy, I. Kessler. "Tracking Mobile Users in Wireless Networks," INFOCOMM 93, pp. 1232-1239. [4] S.T.S. Chia. "Location Registration and Paging in a Third Generation Mobile System," BT Technology Journal, vol. 9, no 4, October 1991, pp. 71-68 [5] R. H. Katz. "Adaptation and Mobility in Wireless Systems," R. H. Katz, IEEE Personnal Communications, First Quarter 1994, pp. 6-17 [6] S. Madhavapeddy, K. Basu, A. Roberts. "Adaptive Paging Algorithms for Cellular Systems," Proceedings of the Fifth WINLAB Workshop on Third Generation Wireless Information Networks, April 1995, pp. 347-361. [7] K.S. Meir-Hellstern, E. Alonso, and D. O'Neil. " The Use of SS7 and GSM to Support High Density Personnal Communications," Proceedings of the International Conference on Communications (ICC), 1992. [8] S. Mohan, R. Jain. "Two User Location Strategies for Personnal Communications Services," IEEE Personnal Communications, First Quarter 1994, pp. 42-50 [9] C. Rose and R. Yates. "Ensemble Polling Strategies for Increased Paging Capacity in Mobile Communication Networks,", manuscript. [10]C. Rose and R. Yates. "Minimizing the Average Cost of Paging Under Delay Constraints," ACM Wireless Networks, 1(2), pp. 211-219, 1995 source: ATT BELL (Goodman, Krishnan & Sugla)