Power consumption in packet radio networks: Extended abstract

Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper we study the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that adequate power is provided to the nodes to ensure that the network is strongly connected (i.e., each node can communicate along some path in the network to every other node). Such assignment of transmission ranges is called complete. We also consider the problem of achieving strongly connected bounded diameter networks. For the case of n+1 colinear points at unit distance apart (the unit chain) we give a tight asymptotic bound for the minimum cost of a range assignment of diameter h when h is a fixed constant and when h ∈ Ω(log n). When the distances between the colinear points are arbitrary, we give an O(n4) time dynamic programming algorithm for finding a minimum cost complete range assignment. For points in three dimensions we show that the problem of deciding whether a complete range assignment of a given cost exists, is NP-hard. For the same problem we give an O(n2) time approximation algorithm which provides a complete range assignment with cost within a factor of two of the minimum. The complexity of this problem in two dimensions remains open, while the approximation algorithm works in this case as well.

Original languageEnglish (US)
Title of host publicationSTACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsRudiger Reischuk, Michel Morvan
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540626169
StatePublished - 1997
Event14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997 - Lubeck, Germany
Duration: Feb 27 1997Mar 1 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Power consumption in packet radio networks: Extended abstract'. Together they form a unique fingerprint.

Cite this