Optimal and near-optimal energy-efficient broadcasting in wireless networks

Christos A. Papageorgiou, Panagiotis C. Kokkinos, Emmanouel A. Varvarigos

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)


In this paper we propose an energy-efficient broadcast algorithm for wireless networks for the case where the transmission powers of the nodes are fixed. Our algorithm is based on the multicost approach and selects an optimal energy-efficient set of nodes for broadcasting, taking into account: i) the node residual energies, ii) the transmission powers used by the nodes, and iii) the set of nodes that are covered by a specific schedule. Our algorithm is optimal, in the sense that it can optimize any desired function of the total power consumed by the broadcasting task and the minimum of the current residual energies of the nodes, provided that the optimization function is monotonic in each of these parameters. Our algorithm has non-polynomial complexity, thus, we propose a relaxation producing a near-optimal solution in polynomial time. Using simulations we show that the proposed algorithms outperform other established solutions for energy-aware broadcasting with respect to both energy consumption and network lifetime. Moreover, it is shown that the near-optimal multicost algorithm obtains most of the performance benefits of the optimal multicost algorithm at a smaller computational overhead.

Original languageEnglish
Title of host publicationEuro-Par 2009 Parallel Processing - 15th International Euro-Par Conference, Proceedings
Number of pages12
Volume5704 LNCS
Publication statusPublished - 2009
Externally publishedYes
EventInternational European Conference on Parallel Processing 2009 - Delft, Netherlands
Duration: 25 Aug 200928 Aug 2009
Conference number: 15th
https://link.springer.com/book/10.1007/978-3-642-03869-3 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5704 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


ConferenceInternational European Conference on Parallel Processing 2009
Abbreviated titleEuro-Par 2009
Internet address

Cite this