Probabilistic analysis of power assignments

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

4 Citations (Scopus)

Abstract

A fundamental problem for wireless ad hoc networks is the assignment of suitable transmission powers to the wireless devices such that the resulting communication graph is connected. The goal is to minimize the total transmit power in order to maximize the life-time of the network. Our aim is a probabilistic analysis of this power assignment problem. We prove complete convergence for arbitrary combinations of the dimension d and the distance-power gradient p. Furthermore, we prove that the expected approximation ratio of the simple spanning tree heuristic is strictly less than its worst-case ratio of 2. Our main technical novelties are two-fold: First, we find a way to deal with the unbounded degree that the communication network induced by the optimal power assignment can have. Minimum spanning trees and traveling salesman tours, for which strong concentration results are known in Euclidean space, have bounded degree, which is heavily exploited in their analysis. Second, we apply a recent generalization of Azuma-Hoeffding's inequality to prove complete convergence for the case p ≥ d for both power assignments and minimum spanning trees (MSTs). As far as we are aware, complete convergence for p>d has not been proved yet for any Euclidean functional.
Original languageUndefined
Title of host publication39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014)
Place of PublicationBerlin
PublisherSpringer
Pages201-212
Number of pages12
ISBN (Print)978-3-662-44464-1
DOIs
Publication statusPublished - 2014
Event39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014 - Budapest, Hungary
Duration: 25 Sep 201429 Sep 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume8635
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014
Period25/09/1429/09/14
Other25-29 September 2014

Keywords

  • METIS-305900
  • IR-91588
  • EWI-24793

Cite this