XTC: A Practical Topology Control Algorithm for Ad-Hoc Networks
Abstract: The XTC AD-HOC network topology control algorithm introduced shows three main advantages over previously proposed algorithms. First, it is extremely simple and strictly local. Second, it does not assume the network graph to be a unit disk graph; XTC proves correct also on general weighted network graphs. Third, the algorithm does not require availability of node position information. Instead, XTC operates with a general notion of order over the neighbors' page link qualities. In the special case of the network graph being a unit disk graph, the resulting topology proves to have bounded degree, to be a planar graph, and - on average-case graphs - to be a good spanner.