Sirocco 2005: welcome

Amotz Bar-Noy: Cellular Networks: Where are the Mobile Users?

Abstract: Mobiles are roaming in a cellular network. Unless they report their new location each time they cross boundaries of cells, the system must conduct a search operation to find their exact location. Reporting new locations by mobiles consumes expensive up-link communication lines. Therefore, in current and future cellular networks, at each point in time for any particular mobile, the system knows only a zone of cells containing the one cell which is the location of this mobile. For this zone, the system maintains a profile that predicts the exact location of the mobile by associating a probability with each cell in the zone. An efficient search should optimize usage of down-link communication lines and the time needed to find the mobile. This model gives rise to many optimization problems. This talk discusses some of them. We first describe the optimal dynamic programming solution that finds a mobile that is located in a zone of n cells in no more than D rounds. This solution assumes an a priori knowledge of the mobile's profile. We then present solutions in which the system develops a mobile's profile while searching for that mobile more than once. The above solutions are for locating one mobile. Next, we address search operations involving m mobiles where m can be greater than one. One example is the call conference search in which the system must find all the m mobiles. Another example is the yellow pages search where the search is over once one out of the m mobiles is found. Finding an optimal solution to the conference call problem is NP-hard. We therefore present an efficient approximation solution. For the yellow pages problem we discuss work in progress. We conclude with the privacy issue by exploring the tradeoff between the accuracy of the profiles and the efficiency of the optimal solutions that are based on these profiles.

Amotz Bar-Noy: is a Professor with the Department of Computer and Information Science ,Brooklyn College , New York

Cyril Gavoille: Distributed Data Structures: a Survey

Abstract: This survey concerns the role of data structures for compactly storing and representing various types of information in a localized and distributed fashion. Traditional approaches to data representation are based on global data structures, which require access to the entire structure even if the sought information involves only a small and local set of entities. In contrast, localized data representation schemes are based on breaking the information into small local pieces, or labels, selected in a way that allows one to infer information regarding a small set of entities directly from their labels, without using any additional (global) information.

Cyril Gavoille: is a Professor with the Laboratoire Bordelais de Recherche en Informatique (LABRI), University Bordeaux, France