HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

On the Complexity of Reducing the Energy Drain in Multihop Ad Hoc Networks

Bernard Mans 1
1 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 : Numerous studies on energy-efficient routing for Multihop Ad Hoc Networks (MANET) look at extending battery life by minimizing the cost at the transmitting node. In this paper, we study the complexity of energy efficient routing when the energy cost of receiving packets is also considered. We first prove that, surprisingly, even when all nodes transmit at the same power, finding a simple unicast path that guarantees enough remaining energy locally at each node in the network then becomes an NP-complete problem. Second, we define formally the problem of finding a virtual backbone that minimized the overall energy cost and prove that this leads to a new NP-complete problem, that we name Connected Exact Cover. Finally, we provide a fully distributed algorithm to reduce the energy drain due to the number of redundant receptions in MANET protocols by offering a modification of the Multi-Point Relay selection scheme and give some provably optimal approximation bounds.
Document type :
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:32:02 PM
Last modification on : Friday, February 4, 2022 - 3:07:57 AM
Long-term archiving on: : Tuesday, February 22, 2011 - 11:56:31 AM


  • HAL Id : inria-00071431, version 1



Bernard Mans. On the Complexity of Reducing the Energy Drain in Multihop Ad Hoc Networks. [Research Report] RR-5152, INRIA. 2004. ⟨inria-00071431⟩



Record views


Files downloads