Skip to Main content Skip to Navigation
Journal articles

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 metadata
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Friday, February 22, 2013 - 3:38:28 PM
Last modification on : Friday, October 22, 2021 - 4:36:02 PM


  • HAL Id : hal-00793579, version 1



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⟩



Record views