16-05-2012, 03:49 PM
Buddy tracking — efficient proximity detection among mobile friends
mob tracking.pdf (Size: 235.29 KB / Downloads: 52)
Introduction
Global positioning systems and mobile phone networks
make it possible to track individual users with
an increasing accuracy. One attractive application of
knowing the geographic location of users is to compute
and maintain social networks. In these networks,
each user may specify or be associated with a group
of other users, called the user’s friends. Whenever a
friend moves into the user’s vicinity, both users are
notified by a proximity alert message. In a more general
context, a social group is one that is predefined
by enrollment or by matching the personal profiles of
users. A group may refer to a list of individuals but
also to other groups of individuals.
Related work:
Algorithms for tracking moving
objects are found in mobile computing literature, both
in the database community, and in the mobile communications
community. Much of the work assumes
that moving objects are represented by simple point
objects whose locations are continuously updated in
an index. This however requires continuous updating
of the locations of all users, which would result in a
huge number of location messages. Trajectory-based
algorithms are becoming increasingly popular [18],
[19].
The Strips algorithm
In this distributed, peer-to-peer model, it is assumed
that each user carries a wireless device that knows its
own location and has enough computational power
for a local computation. In order to compute its
distance from a friend it needs to get the location
of that friend, and this requires a location update
message to be sent. Our objective is to minimize the
communication complexity, or the number of location
update messages exchanged with devices of other
users.
The Strips algorithm vs. the quadtree algorithm.
Comparing between these two algorithms is not an
obvious task. The Strips algorithm, designed for peerto-
peer operation, aims at minimizing the communication
complexity, namely the number of location update
messages being sent between pairs of users. On the
other hand, the centralized, quadtree-based algorithm,
aims at minimizing the computational complexity,
assuming that it knows where are all the users at all
times (or, at least at all cell crossing events).