A cone-based distributed topology-control algorithm for wireless multi-hop networks

TLDR

Wireless multi‑hop network topology can be controlled by adjusting each node’s transmission power. The paper analyzes a cone‑based distributed topology‑control algorithm and proposes optimizations that reduce power while preserving connectivity. CBTC uses only directional information, setting each node’s power to the minimum needed so every α‑degree cone contains a reachable node, and supports dynamic reconfiguration for failures and mobility. The authors prove that α = 5π/6 is necessary and sufficient for connectivity, that smaller α preserves connectivity while larger α may break it, and simulations confirm the algorithm and optimizations effectively reduce power consumption.

Abstract

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 (CBTC) algorithm. This algorithm 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/sub u,/spl alpha// required to ensure that in every cone of degree /spl alpha/ around u, there is some node that u can reach with power p/sub u,/spl alpha//. We show that taking /spl alpha/=5/spl pi//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 /spl alpha//spl les/5/spl pi//6, there is still a path in the smallest symmetric graph G/sub /spl alpha// containing all edges (u,v) such that u can communicate with v using power p/sub u,/spl alpha//. On the other hand, if /spl alpha/>5/spl pi//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.