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)