Minimum-Energy Broadcast Routing in Dynamic Wireless Networks

Afonso Ferreira 1 Aubin Jarry 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : One of the new challenges facing research in wireless networks is the design of algorithms and protocols that are energy aware. A good example is the minimum-energy broadcast routing problem for a static network in the plane, which attracted a great deal of attention these past years. The problem is NPhard and its approximation ratio complexity is a solution proved to be within a factor 6 of the optimal, based on finding a Minimum Spanning Tree of the static planar network. In this paper, we use for the first time the evolving graph combinatorial model as a tool to prove an NP-Completeness result, namely that computing a Minimum Spanning Tree of a planar network in the presence of mobility is actually NP-Complete. This result implies that the above approximation solution cannot be used in dynamic wireless networks. On the positive side, we give a polynomial-time algorithm to build a rooted spanning tree of an on/off network, that minimizes the maximum energy used by any one node. Such tree could then be used in order to maximize the life-time of wireless communication networks.
Complete list of metadatas

https://hal.inria.fr/hal-00793579
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, February 22, 2013 - 3:38:28 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM

Identifiers

  • HAL Id : hal-00793579, version 1

Collections

Citation

Afonso Ferreira, Aubin Jarry. Minimum-Energy Broadcast Routing in Dynamic Wireless Networks. Journal of Green Engineering, River Publishers, 2012, 2 (2), pp.115-123. ⟨hal-00793579⟩

Share

Metrics

Record views

357