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 , 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.
Type de document :
Article dans une revue
Journal of Green Engineering, River Publishers, 2012, 2 (2), pp.115-123. <http://riverpublishers.com/journal/journal_articles/RP_Journal_1904-4720_222.pdf>
Liste complète des métadonnées

https://hal.inria.fr/hal-00793579
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 22 février 2013 - 15:38:28
Dernière modification le : mercredi 14 décembre 2016 - 01:06:03

Identifiants

  • 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. <http://riverpublishers.com/journal/journal_articles/RP_Journal_1904-4720_222.pdf>. <hal-00793579>

Partager

Métriques

Consultations de la notice

160