Towards reliable communication and agreement in mobile ad-hoc networks : algorithms, simulation and testbed

During the last decade, the number of wireless devices like digital organizers, mobile phones and laptop computers has drastically increased. At the same time, several technologies, like Bluetooth, GPRS, or WiFi have become mature and offer a high-performance wireless infrastructure to mobile users. However, there exist still many non-equipped areas where no infrastructure is available. For example, during emergency operations, rescuers may want to deploy temporarily an autonomous (or ad-hoc) network. Under these settings, mobile devices (or nodes) operate in a self-organized manner and can only communicate with their immediate wireless neighbors. To send a packet to a remote destination, a node relies on the routing capabilities of the other nodes. In a mobile ad-hoc network (MANET), problems are inherently more complicated to solve than in a regular wired network because of the dynamic topology and the absence of an underlying communication infrastructure. Many algorithms and protocols have been proposed for mobile ad-hoc networks, but very little has been done to evaluate these solutions in real environments. In most cases, algorithms are evaluated by simulation. Such a solution leads however to incorrect conclusions, as we show in the thesis. In order to avoid the shortcomings of simulations, an adequate software framework must be available, in order to ease the development and the deployment of applications or algorithms. We have developed FRANC, a lightweight Java framework dedicated to the implementation of real ad-hoc applications. FRANC is composed of an extensible library of building blocks that can be composed to build more complex applications. The thesis is not limited to practical contributions. We have also addressed two important problems that are at the root of many other distributed computing algorithms. Although extensively studied in wired networks, this research domain is however still in its early stages in MANETs. We first propose a simple broadcast protocol that disseminates efficiently and reliably a message in a one dimensional graph like a car highway. Then, we study the consensus problem and identify the necessary and sufficient conditions for solving it in self-organized networks when the participants are unknown (in the absence of crashes). Finally, we discuss a pragmatic solution to consensus with crashes based on weak ordering oracles. More specifically, we propose an implementation of these oracles and present results collected in a real small-scale wireless testbed.