Probabilistic analysis of power assignments

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.

• Publication year

  2014

• Venue

  Random Struct. Algorithms

• Publication date

  2014-03-24

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1002/rsa.20714arXiv 1403.5882
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Power of Non-Uniform Wireless Power

  2012cited by this paper
• On the Method of Typical Bounded Differences

  2012cited by this paper
• A Probabilistic Analysis of Christofides' Algorithm

  2012influential reference
• Brief Announcement: A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model

  2012cited by this paper
• Wireless connectivity and capacity

  2011cited by this paper
• Poisson Processes

  2011cited by this paper
• Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals

  2011cited by this paper
• Power assignment problems in wireless communication: Covering points by disks, reaching few receivers quickly, and energy-efficient travelling salesman tours

  2011cited by this paper
• Smoothed Analysis: Analysis of Algorithms Beyond Worst Case

  2011cited by this paper
• Wireless information networks

  2010cited by this paper
• On the connectivity threshold for general uniform metric spaces

  2010influential reference
• Wireless Communication

  2010cited by this paper
• A constant-factor approximation for wireless capacity maximization with power control in the SINR model

  2010cited by this paper
• Smoothed analysis: an attempt to explain the behavior of algorithms in practice

  2009cited by this paper
• An average case analysis of the minimum spanning tree heuristic for the range assignment problem

  2007cited by this paper
• Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks

  2006cited by this paper
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis

  2005cited by this paper
• On the Power Assignment Problem in Radio Networks

  2004cited by this paper
• Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks

  2002cited by this paper
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

  2001cited by this paper
• Power consumption in packet radio networks

  2000cited by this paper
• Critical Power for Asymptotic Connectivity in Wireless Networks

  1999cited by this paper
• A Strong Law for the Longest Edge of the Minimal Spanning Tree

  1999cited by this paper
• Probability theory of classical Euclidean optimization problems

  1998influential reference
• The longest edge of the random minimal spanning tree

  1997cited by this paper
• A Matching Problem and Subadditive Euclidean Functionals

  1993cited by this paper
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space

  1990cited by this paper
• Probability inequalities for sum of bounded random variables

  1963cited by this paper

• Probabilistic Properties of Highly Connected Random Geometric Graphs

  2018cites this paper
• An average case analysis of the minimum spanning tree heuristic for the power assignment problem

  2018cites this paper
• Average Case Analysis of the MST-heuristic for the Power Assignment Problem: Special Cases

  2016cites this paper