Utility-based Message Replication for Intermittently Connected Heterogeneous Networks

Abstract : Communication networks (wired or wireless) have traditionally been assumed to be connected at least most of the time. However, emerging applications such as emergency response, special operations, smart environments, VANETs, etc. coupled with node heterogeneity and volatile links (e.g. due to wireless propagation phenomena and node mobility) will likely change the typical conditions under which networks operate. In fact, in such scenarios, networks may be mostly disconnected, i.e., most of the time, end-to-end paths connecting every node pair do not exist. To cope with frequent, long-lived disconnections, {\em opportunistic routing} techniques have been proposed in which, at every hop, a node decides whether it should either forward and/or store-and-carry a message. As a result, a number of message replicas may be created and routed independently (``spraying''). Most opportunistic routing schemes to-date perform {\em greedy} replication handing over a copy of a message to the first nodes encountered. Yet, in a network with heterogeneous nodes, where some nodes may be much ``better'' relays than others, such greedy schemes waste a lot of message replicas (and thus energy, storage space, etc.) on ``useless'' relays. For this reason, we propose the idea of \emph{utility-based replication}, where some \emph{fitness} or \emph{utility} function is maintained for all nodes in a distributed fashion, and a small budget of message replicas is allocated according to this utility only to the fittest nodes. We describe a number of variations using different utility functions, and show that an improvement of up to 5-6 times in delay can be achieved over greedy algorithms.
Type de document :
[Research Report] RR-6129, INRIA. 2007, pp.17
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 22 février 2007 - 12:36:04
Dernière modification le : mercredi 11 avril 2018 - 01:55:46
Document(s) archivé(s) le : lundi 27 juin 2011 - 15:40:44


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00132480, version 2



Thrasyvoulos Spyropoulos, Thierry Turletti, Katia Obraczka. Utility-based Message Replication for Intermittently Connected Heterogeneous Networks. [Research Report] RR-6129, INRIA. 2007, pp.17. 〈inria-00132480v2〉



Consultations de la notice


Téléchargements de fichiers