DRIFT: Efficient message ordering in ad hoc networks using virtual flooding

Stefan Pleisch, André Schiper
2006
Rapport ou document de travail

We present DRIFT --- a total order multicast algorithm for ad hoc networks with mobile or static nodes. Due to the ad hoc nature of the network, DRIFT uses flooding for message propagation. The key idea of DRIFT is virtual flooding --- a way of using unrelated message streams to propagate message causality information in order to accelerate message delivery. We describe DRIFT in detail. We evaluate its performance in a simulator and in a wireless sensor network. In both cases our results demonstrate that the performance of DRIFT exceeds that of the simple total order multicast algorithm designed for wired networks, on which it is based. In simulation at scale, for certain experiment settings, DRIFT achieved speedup of several orders of magnitude.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Stefan Pleisch, André Schiper
2006
Rapport ou document de travail

Résumé

Official source

https://infoscience.epfl.ch/record/85608?ln=fr

À propos de ce résultat

Concepts associés (3)

Concepts associés

Chargement

Publications associées (4)

Publications associées

Chargement

A Turnover based Adaptive HELLO Protocol for Mobile Ad Hoc and Sensor Networks

François Ingelrest

We present a turnover based adaptive HELLO protocol (TAP), which enables nodes in mobile networks to dynamically adjust their HELLO messages frequency depending on the current speed of nodes. To the best of our knowledge, all existing solutions are based on specific assumptions (e.g., slotted networks) and/or require specific hardware (e.g., GPS) for speed evaluation. One of the key aspects of our solution is that no additional hardware is required since it does not need this speed information. TAP may be used in any kind of mobile networks that rely on HELLO messages to maintain neighborhood tables and is thus highly relevant in the context of ad hoc and sensor networks. In our solution, each node has to monitor its neighborhood table to count new neighbors whenever a HELLO is sent. This turnover is then used to adjust HELLO frequency. To evaluate our solution, we propose a theoretical analysis based on some given assumptions that provides the optimal turnover when these assumptions hold. Our experimental results demonstrate that when this optimal value is used as the targeted turnover in TAP, the HELLO frequency is correctly adjusted and provides a good accuracy with regards to the neighborhood tables.

2007

Chargement

Distributed sensor failure detection in sensor networks

Pascal Frossard, Nikolaos Thomos, Tamara Tosic

We investigate the problem of distributed sensors' failure detection in networks with a small number of defective sensors, whose measurements differ significantly from neighboring sensor measurements. Defective sensors are represented by non-zero values in binary sparse signals. We build on the sparse nature of the binary sensor failure signals and propose a new distributed detection algorithm based on Group Testing (GT). The distributed GT algorithm estimates the set of defective sensors from a small number of linearly independent binary messages exchanged by the sensors. The distributed GT algorithm uses a low complexity distance decoder that is robust to noisy messages. We first consider networks with only one defective sensor and determine the minimal number of linearly independent messages needed for detection of the defective sensor with high probability. We then extend our study to the detection of multiple defective sensors by modifying appropriately the message exchange protocol and the decoding procedure. We show through experimentation that, for small and medium sized networks, the number of messages required for successful detection is actually smaller than the minimal number computed in the analysis. Simulations demonstrate that the proposed method outperforms methods based on random walk measurements collection in terms of detection performance and convergence rate. Finally, the proposed method is resilient to network dynamics due to the effective gossip-based message dissemination protocol.

2011

Chargement

Distributed sensor failure detection in sensor networks

Pascal Frossard, Nikolaos Thomos, Tamara Tosic

We investigate the problem of distributed sensors' failure detection in networks with a small number of defective sensors, whose measurements differ significantly from neighbouring sensor measurements. We build on the sparse nature of the binary sensor failure signals and propose a new distributed detection algorithm based on Group Testing. The distributed GT algorithm estimates the set of defective sensors by a low complexity distance decoder from a small number of linearly independent binary messages exchanged by the sensors. We first consider networks with one defective sensor and determine the minimal number of linearly independent messages needed for detection of the defective sensor with high probability. We then extend our study to the detection of multiple defective sensors by modifying appropriately the message exchange protocol and the decoding procedure. We show through experimentation that, for small and medium sized networks, the number of messages required for successful detection is actually smaller than the minimal number computed in the analysis. Finally, simulations demonstrate that the proposed method outperforms methods based on random walks in terms of detection performance and convergence rate.

Elsevier Science Bv2013

Chargement

Réseau de capteurs sans fil

Un réseau de capteurs sans fil est un réseau ad hoc d'un grand nombre de nœuds, qui sont des micro-capteurs capables de recueillir et de transmettre des données d'une manière autonome. La position de

Message

Un message est un ensemble de signes. Il implique donc un codage par l'émetteur, et un décodage par le récepteur (d'où la nécessité d'un code commun). La théorie de l'information fut mise au point po

Réseau informatique

thumb|upright|Connecteurs RJ-45 servant à la connexion des réseaux informatiques via Ethernet. thumb|upright Un réseau informatique ( ou DCN) est un ensemble d'équipements reliés entre eux pour échan