Distributed Construction of a Multi-level Topology with Unpredictable Metric Values for Wireless Networks

Large ad hoc networks greatly benefit from hierarchical topologies in terms of scalability and robustness. Previous research has explored the construction of such hierarchies by ranking the nodes according to general performance metrics. However, these approaches have been mostly con- fined to two levels with just predictable metric values, con- sidering the multi-level case only by recursive application of the two-level approach. In this paper, we show that this methodology yields only suboptimal results in many cases. Hence, we present a distributed algorithm to construct a multi-metric multi-level independent dominating set topol- ogy for unpredictable metric values, which overcomes the constraints of suboptimality faced previously. Further, our algorithm is also easily parameterizable in order to balance the tradeoff between performance optimality and message complexity which is particularly desirable in dynamic net- works. We substantiate the performance of our algorithm by extensive simulations.