Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks

By Erran L. Li, Joseph Y. Halpern, Paramvir Victor Bahl, Yi-Min Wang, Roger Wattenhofer. ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2001

489 citations recorded by the source corpus.

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control algorithm. This algorithm, introduced in [16], does not assume that nodes have GPS information available; rather it depends only on directional information. Roughly speaking, the basic idea of the algorithm is that a node u transmits with the minimum power p<subscrpt>u, α</subscrpt> required to ensure that in every cone of degree α around u, there is some node that u can reach with power p<subscrpt>u, α</subscrpt>. We show that taking α = 5π/6 is a necessary and sufficient condition to guarantee that network connectivity is preserved. More precisely, if there is a path from s to t when every node communicates at maximum power then, if α ⪇ 5π/6, there is still a path in the smallest symmetric graph G<subscrpt>α</subscrpt> containing all edges (u, v) such that u can communicate with v using power p<subscrpt>u, α</subscrpt>. On the other hand, if α > 5π/6, connectivity is not necessarily preserved. We also propose a set of optimizations that further reduce power consumption and prove that they retain network connectivity. Dynamic reconfiguration in the presence of failures and mobility is also discussed. Simulation results are presented to demonstrate the effectiveness of the algorithm and the optimizations.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/ae92a106666d12ff5d5c9a7a0891ae5f4ef6e3df

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Topology control in wireless ad hoc and sensor networks (2005, methodology): “2001) and further analyzed in (Li et al. 2001) and the DistRNG protocol presented in (Borbash and Jennings 2002).”
Joint mobility and routing for lifetime elongation in wireless sensor networks (2005, unknown): “, [5], [6], [7], [8]) and clustering (e.”
XTC: a practical topology control algorithm for ad-hoc networks (2004, methodology): “based on CBTC [7, 14 ], some based on other geometric structures, such as a local version of the Delaunay triangulation [15].”
Design and analysis of an MST-based topology control algorithm (2003, methodology): “CBTC [7] is a two-phase algorithm in which each node finds the minimal power such that transmitting with the power ensures that the node can reach some node in every cone of degree .”
On neighbor discovery in wireless networks with directional antennas (2005, background): “We emphasize that the focus of this paper is on neighbor discovery alone and not how the discovered neighbor information is used by topology control algorithms [11], [6], [15], medium access protocols [3], [1] and routing algorithms [4].”
Coverage and connectivity issues in wireless sensor networks: A survey (2008, background): “control, nodes adjust their transmission radii based on local geometric constraints to cut off unnecessary links that increase interference and collisions [38,23].”
Real-time communication and coordination in embedded sensor networks (2003, background): “2) Topology Control: CBTC [84] is a two-phase algorithm in which each node finds the minimum power such that transmitting with ensures that it can reach some node in every cone of degree .”
Topology control and routing in ad hoc networks: a survey (2002, methodology): “A number of distributed topology control algorithms have been proposed recently [ 32 , 43, 52, 53].”
Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks (2002, methodology): “al [ 12 ] provide a more detailed analysis of the protocol of [22] and establish a precise bound on the angle of the cone that ensures connectivity.”