Time-Space Opportunistic Routing in Wireless Ad hoc Networks: Algorithms and Performance Optimization by Stochastic Geometry

François Baccelli 1, 2, 3 Bartlomiej Blaszczyszyn 2, 3 Paul Mühlethaler 4
3 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt
4 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : This paper is meant to be an illustration of the use of stochastic geometry for analyzing the performance of routing in large wireless ad hoc (mobile or mesh) networks. In classical routing strategies used in such networks, packets are transmitted on a pre-defined route that is usually obtained by a shortest-path routing protocol. In this paper we review some recent ideas concerning a new routing technique which is opportunistic in the sense that each packet at each hop on its (specific) route from an origin to a destination takes advantage of the actual pattern of nodes that captured its recent (re)transmission in order to choose the next relay. The paper focuses both on the distributed algorithms allowing such a routing technique to work and on the evaluation of the gain in performance it brings compared to classical mechanisms. On the algorithmic side, we show that it is possible to implement this opportunistic technique in such a way that the current transmitter of a given packet does not need to know its next relay a priori, but the nodes that capture this transmission (if any) perform a self-selection procedure to choose the packet relay node and acknowledge the transmitter. We also show that this routing technique works well with various medium access protocols (such as Aloha, CSMA, TDMA). Finally, we show that the above relay self-selection procedure can be optimized in the sense that it is the node that optimizes some given utility criterion (e.g. minimize the remaining distance to the final destination), which is chosen as the relay. The performance evaluation part is based on stochastic geometry and combines simulation as analytical models. The main result is that such opportunistic schemes very significantly outperform classical routing schemes when properly optimized and provided at least a small number of nodes in the network know their geographical positions exactly.
Type de document :
Article dans une revue
The Computer Journal, Oxford University Press (UK), 2010, 53 (5), pp.592-609. 〈10.1093/comjnl/bxp049〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00940564
Contributeur : Fabien Mathieu <>
Soumis le : samedi 1 février 2014 - 18:45:01
Dernière modification le : mardi 17 avril 2018 - 11:32:44

Identifiants

Collections

Citation

François Baccelli, Bartlomiej Blaszczyszyn, Paul Mühlethaler. Time-Space Opportunistic Routing in Wireless Ad hoc Networks: Algorithms and Performance Optimization by Stochastic Geometry. The Computer Journal, Oxford University Press (UK), 2010, 53 (5), pp.592-609. 〈10.1093/comjnl/bxp049〉. 〈hal-00940564〉

Partager

Métriques

Consultations de la notice

308