Brief announcement: Minimum spanning trees and cone-based topology control

Abstract

Consider a setting where nodes can vary their transmission power thereby changing the network topology, the goal of topology control is to reduce the transmission power while ensuring the communication graph remains connected. Wattenhofer et al. [6] introduced the distributed cone-based topology control algorithm with parameter α (CBTC(α)) and proved it correct if α ≤ 2π/3. Li et al. [4] proposed performing asymmetric edge removal or increasing α to 5π/6, and proved that when applied separately these minimizations preserve connectivity. Bahramgiri et al. [1] proved that when α ≤ 2π/3 it was possible to extend the algorithm to work in three dimensions and described a variation to preserve k-connectivity.

We give a short self-contained proof that when α ≤ 2π/3 the minimum spanning tree is contained in the graph produced by CBTC(α). Its interesting to note that by comparison, other popular topology control algorithms are variations of the Gabriel Graph [5], the Relative Neighbor Graph [2] or the Delaunay Triangulation [3]; all of which are structures known to contain the minimum spanning tree. The proof is essentially an application of a lemma proved by Yao [7]. As a consequence of this proof we get as corollaries new short proofs of some of the main results of Wattenhofer et al. [6], Li et al. [4] and Bahramgiri et al. [1]. (1) When α ≤ 2π/3 the algorithm CBTC(α) preserves connectivity [6]. (2) The asymmetric edge removal operation preserves connectivity [4]. (3) The algorithm can be extended to three dimensions [1], and generally to n-dimensional space.