SARAH Project

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.

image of a DT-MANET composed of several partitions

The project is divided in four main axes:

  1. Support for DTN communication
  2. Service platform
  3. Security issues
  4. Simulation and evaluation of delay-tolerant networks and services
Le Havre and Bordeaux are in charge of the last one: 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.

Objectives

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:
    • broadcasting;
    • building and maintaining spanning forests;
    • building and maintaining robust shortest paths;
    • etc.
  • 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);
    • etc.
In the sequel we give some examples of the results that were achieved so far.

Results

Madhoc

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.

a snapshot of madhoc, a mobile ad hoc network simulator


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.

DA-GRS

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. According to the density value, the network may be connected of partitioned. The problem of the hidden terminal, when one station receives simultaneously messages from two sources that cannot detect themselves
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.

white eeePC Smartphone Qtek 9000

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 each of them two questions have to be answered: How can a decentralized algorithm build a structure in a dynamic graph? If this structure has to be kept for a given period of time, then how can a decentralized algorithm maintain a structure/a property in a dynamic graph? In fact it appears that an answer to the second question is also an answer to the first one and conversely. Indeed, building a structure in a dynamic graph may suppose that the building process is much faster than the evolution speed of the graph, in which case we can assume that the whole structure can be produced before any change in the graph. In such a situation, building the required structure in a dynamic graph is equivalent to find a decentralized algorithm to build such a structure within a series of static graphs. But, what happens if during the building process part of the structure is lost because of a change in the graph? In such a situation, the algorithm has to be able to "repair" the structure, which is similar to "maintain" the structure while the graph evolves.

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.

Number of token moves necessary for recovering a unic spanning tree with respect to the length of the tabu list. For the evaluation of the token-based decentralized algorithm for building a unic spanning tree, we make some experiments with two full binary trees linked by a fixed number of edges.
The picture represents the evolution of the mean number of token moves for recovering a unic spanning tree with respect to the length of the tabu list. Using a tabu list of length 1 improves by a factor of 3 the performances of the algorithm for building spanning-trees. Example of the trees used for measuring the performances of the algorithm with and without tabu list. On the picture two full binary trees are considered. Some edges with extremities belonging to both trees are added. Each token is only allowed to move in its own tree. The algorithm stops when both tokens are located on the adjacent vertices of the same edge.

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 People

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))