NOTE SPECIAL TIME and PLACE:
December 22, Tuesday 12:15, Room 570, Education Building
Stabilization in motion
Lecturer :
Elad Michael Schiller
Lecturer homepage : http://www.chalmers.se/cse/EN/people/schiller-elad6848
Affiliation : Department of Computing Science,
The widespread of wireless mobile devices and 802.11/Wi-Fi wireless networking
has made mobile ad hoc networks (MANETs) one of the
most exciting and fast growing fields in computer networks. In a MANET, each
device is free to move in space and communicate without the need for
preexisting infrastructure (such as base stations or telephone lines). This
provides users with flexibility and mobility, but it also makes protocol design
very challenging, because communication links unexpectedly appear and
disappear. The talk presents two results that significantly simplify the design
of MANETs and improve their robustness.
In the first part of the talk we present high-level communication primitives for MANETs, such as services for group communication and resource allocation. These primitives facilitate the design of MANET protocols by freeing the designers from having to deal with low level complications that naturally occur in MANETs.
The second part of the talk focuses on a low level communication primitive that is imperative in wireless communications. We address the problem of collision avoidance in MANETs by presenting a design for Media Access Control (MAC) protocols that is based on vertex-coloring. The challenge here is that nodes are free to move, and therefore, the vertices must be re-colored. In order to do that the algorithm must access the communication media that is prone to message collision. We present a new collision avoidance technique for MAC algorithms that are based on vertex-coloring.
MANETs are by nature susceptible to transient faults, because communication links unexpectedly disappear and message transmissions can collide. Transient faults can corrupt data and make systems unavailable. Our algorithms are self-stabilizing and recover after the occurrence of transient faults. We use new analytical approaches for modeling the location of mobile nodes and estimating the algorithm performances. We expect that our models can be used for the design of additional self-stabilizing protocols for MANETs.
Some of the results presented in the talk are joint work with Shlomi Dolev, Pierre Leone, Marina Papatriantafilou, Jennifer Welsh and Gongxi Zhu [PODC'02, SRDS'02, IEEE Trans. Mob. Comput.'06, SSS'09, Algosensors'09, SOMSED’09].