Network Lifetime and Power Assignment in ad hoc Wireless Networks

Gruia Calinescu, Sanjiv Kapoor, Alexander Olshevsky, Alexander ZelikovskyESA 2003 · OpenReview

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) = max uv ∈ E(H) c(uv). The power of H is given by $p(H) = \sum_{u \in v}p{\sc H}(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).
BibTeX
@inproceedings{calinescu2003network,
  author = {Gruia Calinescu and Sanjiv Kapoor and Alexander Olshevsky and Alexander Zelikovsky},
  title = {{Network Lifetime and Power Assignment in ad hoc Wireless Networks}},
  booktitle = {ESA},
  year = {2003},
  url = {https://openreview.net/forum?id=C_oreRo1kL2},
}

Loading related content...

Figure