Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071431
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:32:02 PM
Last modification on : Wednesday, September 16, 2020 - 5:07:09 PM
Long-term archiving on: : Tuesday, February 22, 2011 - 11:56:31 AM

Identifiers

  • HAL Id : inria-00071431, version 1

Collections

Citation

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

Share

Metrics

Record views

193

Files downloads

314