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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00132480
Contributor : Rapport de Recherche Inria <>
Submitted on : Thursday, February 22, 2007 - 12:36:04 PM
Last modification on : Wednesday, August 7, 2019 - 12:18:47 PM
Long-term archiving on: Monday, June 27, 2011 - 3:40:44 PM

Files

RR-6129.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00132480, version 2

Collections

Citation

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⟩

Share

Metrics

Record views

292

Files downloads

458