Probabilistic analysis of power assignments

Maurits de Graaf, Bodo Manthey

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
155 Downloads (Pure)


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 math formula 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 languageEnglish
Pages (from-to)483-505
JournalRandom Structures and Algorithms
Issue number3
Publication statusPublished - Oct 2017


  • Euclidean optimization problems
  • power assignments
  • average-case analysis
  • complete convergence


Dive into the research topics of 'Probabilistic analysis of power assignments'. Together they form a unique fingerprint.

Cite this