Outline of the project
The SARAH Project is funded by the French National Research Agency (ANR) in the framework of the 2005 program ARA SSIA (Security, Embedded Systems and Ambiant Intelligence). The official web site of this project is here.
The main objective of this project is to investigate the way of building Delay-Tolerant Distributed Services for Mobile Ad Hoc Networks. The target networks are called Delay-Tolerant Mobile Ad Hoc Networks (DT-MANET). These networks are infrastructure-free, based on wireless communications and may be partitioned. This means that there may exist some period of time during which between two given stations there is no path.
The project is divided in four main axes:
- Support for DTN communication
- Service platform
- Security issues
- Simulation and evaluation of delay-tolerant networks and services
Simulation and Evaluation of DT Networks and Services
Up to now the goal of most researches on the simulation aspects of MANET has been to precisely model the behavior of the lowest layers of the network stack, and especially the MAC layer. In contrast other aspects of mobile networking simulation is often neglected. Hence, most simulators implement very crude mobility models and little attention has been paid so far to the simulation and to the evaluation of distributed algorithms that are meant to reside on top of the network stack.
The goal of this workpackage is thus to devise models and a simulation suite that will make it possible to simulate an environment composed of heterogeneously distributed mobile devices, as well as DT (delay-tolerant) communication between these devices, DT service discovery and high level algorithms running on top of these devices. This package aims at integrating or at least at making more interoperable Madhoc and DA-GRS simulators previously designed and implemented by the partners of the project. For that purpose, we have defined a bridging dynamic graph format called DGS standing for Dynamic GraphStream.
The main issues addressed within this workpackage are:
- the design and the evolution of current simulators (Madhoc and DAGRS);
- a high-level description of distributed algorithms in the context of dynamic graphs;
- the design and the implementation of decentralized strategies for DT-MANET:
- building and maintaining spanning forests;
- building and maintaining robust shortest paths;
- the conception and the simulation of close-to-real-life mobility models and environments:
- environments with obstacles;
- volatility of stations: devices may be switched on/off at any moment;
- mobility schemes constrained by the environment (obstacles, corridor);
Madhoc is a discrete-time MANET simulator able to cope with DT-MANET as well as with the volatility of stations. It offers the possibility to implement new environments, new mobility schemes and new applications thanks to an API part of the software. In the context of the SARAH project, Madhoc was partially rewritten according to the needs of the other partners. Madhoc is freely distributed (under GPL License) written in Java and is part of the PhD thesis of Luc Hogie. Follow the link for more information.
Click on the picture to obtain a larger image.
This picture represents a snapshot of the Madhoc simulator. On the West part of the window the menu allow the user to choose the view (either the network or the performance charts). The central part of the window contains the view chosen by the user, on the snapshot, the network was chosen. The East part of the window is either devoted to the control about the drawing of the environment and about the application, or to the presentation of information about a particular station chosen by the user by a mouse click on it. Finaly, the South part of the window shows some information about the running simulation.
The DA-GRS simulator is a tool for test and visualization of algorithms based on the DA-GRS model (Dynamicity-Aware Graph Relabeling Systems), a graph relabeling model adapted to mobility. DA-GRS, Madhoc and GraphStream, were all intensively used by Le Havre and Bordeaux teams for addressing the problem of building and maintaining structures in DT-MANET using decentralized algorithms. This simulator is free software (under GPL License) written in the Java programming language and is part of the PhD thesis of Arnaud Casteigts about mobility management, in the SOD team at LaBRI. Follow the link for more information.
Broadcasting in DT-MANETs
DT-MANET are mobile wireless networks that feature inherent connection disruption. In particular such networks are generally non-connected. There exist a little number of protocols solving the problem of broadcasting across DT-MANET. Almost all of them exhibit a static behavior, i.e. they provide no control parameter. Several points constitute major issues for broadcasting in DT-MANET: heterogeneity of the density, the broadcasting-storm problem, and the problem of the hidden terminal.
Click on the pictures to obtain larger ones.
|Various densities of stations within an open obstacle-free environment.||Illustration of the problem of the hidden station, when a given station receives simultaneously messages from different sources.|
In this action, we have proposed two different decentralized algorithms for achieving this task. The first one is called DFCN (standing for Delayed Flooding with Cumulative Neighborhood), that was mainly designed for taking into account both the heterogeneous density of stations within the environment and its partitioned property. DFCN was implemented on real devices (smartphones HTC Diamond and Qtek 9000 and notebook eeePC) and is currently used within another project for risk management.
The second broadcasting protocol proposed was more related with applications. In particular, for some domains, it is important that the user (the source of the broadcast message) can control the way the message gets spread across the network. The CABP protocol (standing for Context-Aware Broadcasting Protocol), adapts its greediness according to the "urgency" (priority) of the broadcast message.
More information may be found about both broadcasting strategies in the publication page of the project.
Decentralized Strategies for Building and Maintaining Properties/Structures in DT-MANETs
Two main problems were addressed:
- Building and Maintaining Spanning Forests in DT-MANET;
- Building and Maintaining Robust Shortest Paths in DT-MANET.
For the spanning forest problem, we rely on a decentralized token-based algorithm developed in Bordeaux using the DA-GRS model of computation. We performed a probabilistic analysis of the algorithm and show that constraining the token moves, by the use of a tabu list, entails a significant increase of the performances of the algorithm in term of token moves for achieving a unic spanning tree when the network is not partitioned. Indeed, the algorithm that uses a tabu list is 3 times faster than the original one.
Click on the pictures to obtain larger ones.
Robust Shortest Path: the description of the problem is coming soon.
Mobility Model Study
We are interested in designing, implementing and analyzing various environment models and mobility models of stations. Our aim is to study the applicability of our decentralized algorithms but also to study the impact of both the environment and the mobility scheme on the connection graphs associated to the underlying DT-MANET. So far, we have investigated and implemented several environments and mobility models in Madhoc, but also using GraphStream.
More to come soon...
In DT-MANET, it is also supposed that stations may appear and disappear at any moment without any prior notice to their neighbors; we call this characteristic the volatility of stations.
The researchers involved in this workpackage come mainly from the Universities of Bordeaux and Le Havre, but former phD students holding now postdoc positions outside are still participating in some of the actions described in these pages.
- Aboue-Nze Cédric (phD student - Le Havre University)
- Albert Jeremy (phD student - University of Bordeaux 1)
- Barrere Lionel (phD student - University of Bordeaux 1)
- Casteigts Arnaud (page at the University of Ottawa) (Postdoc - University of Ottawa Canada)
- Chaumette Serge (Professor - University of Bordeaux 1)
- Franzolini Julien (phD student - Le Havre University)
- Guinand Frédéric (Professor - Le Havre University)
- Hogie Luc (postdoc INRIA Sophia-Antipolis)
- Pigné Yoann (phD student Le Havre University (defense the 4th of december))