Probabilistic analysis of power assignments. Issue 3 (28th March 2017)

• Record Type: Journal Article
• Authors: de Graaf, Maurits; Manthey, Bodo
• Is Part Of: Random structures & algorithms. Volume 51:Issue 3(2017)
• Page Start: 483
• Page End: 505
• Publication Date: 2017-03-28
• Subjects: Euclidean optimization problems -- power assignments -- average‐case analysis -- complete convergence; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20714
• Languages: English
• ISSNs: 1042-9832

Abstract

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. © 2017 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc., 51, 483–505, 2017