Network lifetime and power assignment in ad hoc wireless networks

Gruia Calinescu, Sanjiv Kapoor, Alexander Olshevsky, Alexander Zelikovsky

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Used for topology control in ad-hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity) The input consists of a directed complete weighted graph G = (V,c). The power of a vertex u in a directed spanning subgraph H is given by PH(u) = maxuv∈E(H) c(uv). The power of H is given by p(H) =∑u∈V PH(u), Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint. We present asymptotically optimal O(log n)-approximation algorithms for three Power Assignment problems: Min-Power Strong Connectivity, Min-Power Symmetric Connectivity (the undirected graph having an edge uv iff H has both uv and vu must be connected) and Min-Power Broadcast (the input also has r ∈ V, and H must be a r-rooted outgoing spanning arborescence). For Min-Power Symmetric Connectivity in the Euclidean with efficiency case (when c(u,v) = ∥u,v∥K/e(u) , where ∥u,v is the Euclidean distance, κ is a constant between 2 and 5, and c(u) is the transmission efficiency of node u), we present a simple constant-factor approximation algorithm. For all three problems we give exact dynamic programming algorithms in the Euclidean with efficiency case when the nodes lie on a line. In Network Lifetime, each node u has an initial battery supply b(u), and the objective is to assign each directed subgraph H satisfying the connectivity constraint a real variable α(H) ≥ 0 with the objective of maximizing ∑Hα(H) subject to ∑HPT(u) α(H) ≤ b(u) for each node u ∈ V. We are the first to study Network Lifetime and give approximation algorithms based on the PTAS for packing linear programs of Garg and Könemann. The approximation ratio for each case of Network Lifetime is equal to the approximation ratio of the corresponding Power Assignment problem with non-uniform transmission efficiency.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsGiuseppe di Battista, Uri Zwick
PublisherSpringer
Pages114-126
Number of pages13
ISBN (Print)3540200649, 9783540200642
DOIs
StatePublished - 2003

Publication series

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Network lifetime and power assignment in ad hoc wireless networks'. Together they form a unique fingerprint.

Cite this