License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-580
URL: http://drops.dagstuhl.de/opus/volltexte/2005/58/

Epstein, Leah ; Levin, Asaf

Tracking mobile users

pdf-format:
Dokument 1.pdf (108 KB)


Abstract

Cellular telephony systems, where locations of a mobile users may be unknown at some times, are becoming more common. Mobile users are roaming in a zone. A user reports its location only if it leaves the zone entirely. We consider cellular zones with n cells and m mobile users roaming among the cells. The location of the users is uncertain and is given by m probability distribution vectors. The Conference Call Search problem (CCS) deals with tracking a set of mobile users, in order to establish a call between all of them. The search is performed in a limited number of rounds, and the goal is to minimize the expected search cost. In the "unit cost model", a single query for a cell outputs a list of users located in that cell. The "bounded bandwidth" model allows a query for a single user per cell in each round. We discuss three types of protocols; oblivious, semi-adaptive and adaptive search protocols. An oblivious search protocol decides on all requests in advance, and stops only when all users are found. A semi-adaptive search protocol decides on all the requests in advance, but it stops searching for a user once it is found. An adaptive search protocol stops searching for a user once it has been found (and its search strategy may depend on the subsets of users that were found in each previous round). We establish the differences between the distinct protocol types and answer some open questions which were posed in previous work on the subject.

BibTeX - Entry

@InProceedings{epstein_et_al:DSP:2005:58,
  author =	{Leah Epstein and Asaf Levin},
  title =	{Tracking mobile users},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  year =	{2005},
  editor =	{Susanne Albers and Rolf H. M{\"o}hring and Georg Ch. Pflug and R{\"u}diger Schultz},
  number =	{05031},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/58},
  annote =	{Keywords:  mobile users , PTAS}
}

Keywords: mobile users , PTAS
Seminar: 05031 - Algorithms for Optimization with Incomplete Information
Issue date: 2005
Date of publication: 30.05.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI