Sunday, May 7, 14:15-15:15
at 14:00
Schreiber Building, Room 309
User tracking is based on two elementary operations: {\bf Registration}
(location update) - a message sent by the user that informs the network
about
its location, and {\bf paging} (or search)- a search conducted by the
network,
to find the user location.
There is a clear trade-off between the rate of registration messages
and the cost of paging the user when a connection to the user (for
an
incoming call) is requested.
Hence, the problem of tracking mobile users is an optimization problem:
the goal is to minimize the {\it combined cost} of registration and
search operations.
Existing tracking schemes and previous studies addressing this issue
are based either on {\it user operated} algorithms which are
{\it pure distributed} in nature, or on {\it network operated} algorithms
which are {\it centralized} in nature.
Unfortunately, due to the complex nature of the tracking problem,
efficient user tracking cannot be done by the user only nor by the
network only.
Due to the huge number of mobile users, any efficient tracking scheme
that consider the individual user call and mobility parameters,
must be distributed among the users.
On the other hand, an efficient tracking scheme must use network-dependent
information, such as the system topology and the activity of other
users.
Such information is not generally available to the user.
Furthermore, the requirement of real-time service to millions of users
implies that no sophisticated algorithm is indeed feasible, if it is
to be
installed solely on user equipment.
For these reasons, a pure distributed tracking scheme is incomplete
and
unreliable under realistic conditions.
Recognizing these drawbacks, we propose a novel approach to the problem
of
tracking mobile users. The proposed method is neither centralized nor
distributed. Rather, it is a combined scheme that incorporates a distributed
scheme with a centralized scheme.
We refer to this scheme as an {\it interactive scheme}.
The basic idea is to use the broadcast mechanism that already exists
in
wireless networks in order to: A) Provide users with the information
essential
for efficient tracking, that is not generally available to them, and
B) to govern the registration activity and reduce the contention among
users wishing to register.
The basic concept of the proposed method is to to leave user specific
decisions in the user equipment while moving network general decisions
to the
network. Consequently, user tracking is neither done by the user only
nor by the network only. Rather, a combined scheme that utilizes the
strengths of both entities is used.
Guided by this idea, we construct schemes and protocols based on
{\it interaction} between the network and the users, yielding very
efficient
tracking algorithms. The tracking schemes proposed in this study can
significantly reduce the wireless cost of tracking mobile users, in
comparison
to existing methods and previous studies.
The talk consists of three main parts:
The first part focuses on analyzing the registration efficiency, as
a function
of the user call and mobility parameters, for Markovian motion model.
Previous
studies addressing this issue were either restricted to simple motion
patterns and specific system topology, or approached this issue with
too much generality to obtain closed form terms.
We derive closed form terms, expressing the registration
efficiency as a function of the user call profile and mobility pattern
for Markovian motion model.
The second part is devoted to load-dependent tracking schemes that adapt
the
tracking activity to the local network load.
The strategies proposed in this section can significantly reduce
the wireless cost of tracking mobile users in comparison to the use
of
equivalent load-insensitive strategies, without increasing the computational
task imposed on the user.
The third part proposes mechanisms and encoding schemes to be
used by the network to convey useful location information to the
users. A typical piece of information is that of location or distance,
which the user equipment cannot determine on its own. The deployment
of this
information can be effectively used by the users to identify their
location,
or distance, and guide them in their registration activity.
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html