Topology control for wireless ad-hoc networks.

摘要

Wireless ad-hoc networks are formed by autonomous nodes that communicate via radio, without any additional a priori infrastructure. Nodes unable to hear each other communicate through intermediate nodes relaying their messages. In other words, the communication infrastructure is provided by the nodes themselves. Topology control deals with establishing and maintaining such a virtual infrastructure (topology), and constitutes an important algorithmic challenge.;This thesis explores efficient algorithms for constructing efficient topologies for wireless networks satisfying several properties, such as the spanner property, low degree, low weight and low-interference. In particular, we propose a new distributed algorithm (SLISE) that constructs, in O(log n) rounds of communication, a low-interference spanner for wireless ad hoc n-node networks modeled by Quasi Unit Disk Graphs (qUDG). For any t > 1, the resulting spanner has optimal interference among all t-spanners of the qUDG, stretch factor t(1+epsilon) for any epsilon > 0, and constant maximum degree. Our method uses a relaxed greedy algorithm for filtering edges of a LISE (Low Interference Spanner Establisher) structure developed by Burkhart, Rickenbach, Wattenhofer and Zollinger. Simulation results indicate that our method produces sparse graphs of low maximum interference, low average interference and low weight.