Event Date/Time: Aug 26, 2004
Report as Spam


Very few of us may conceive their lifes without cellular phones and more generally, without pervasive connections. But all of us (including those few that remain cool) are attracted by all the challenging algorithmic problems involved to obtain connections anywhere and at any time. New levels of complexity, that were not present in the algorithmic design for wired networking, emerge. Indeed, the algorithms have to optimize the use of scarce resources, like bandwidth and battery power, must face unreliable wireless channels as well as selfish and sometimes byzantine partners, and have to commute from one wireless system to another in a transparent way to the system users.

In the above scenario, the complexity has been tamed using new clever algorithms, which however are often based on those that are already part of the foundations of computer science. For example, the problem of minimizing the usage of the radio bandwidth in cellular networks has been reduced to generalized graph coloring problems, where the same color (channel) is used at nodes (stations) sufficiently apart, so that interference is avoided, and that close nodes get colors (channels) well separated in the spectrum. Similarly, dynamic programming strategies have been used to optimally solve the problem of scheduling data on channels so as to minimize the waiting time experienced by users before
the data they look for is broadcast. Moreover, for sensor networks, the problem of finding the least exposure path when the network is modeled by a bidimensional grid is similar to the problem of finding the shortest path between two vertices of the grid. In addition, many problems posed by the energy-aware management of ad-hoc networks are variants of the minimum spanning tree problem. Finally, game theory and algorithmic mechanism design are a way to model the behaviour in Internet when selfish participants destroy the current attitude of maximizing the social benefit by truthfully following the net protocols.

We are soliciting research contributions on the design, specification, and implementation of algorithms for current and future wireless applications. Both theoretical and practical works, that demonstrate the role of discrete, approximate, optimization, on-line and distributed algorithms for any kind of wireless networks (e.g. personal, sensor, ad-hoc, mobile, and cellular) are relevant in this workshop.