Bounded-distance multi-coverage backbones in wireless sensor networks

Topology control can improve the performance of Wireless Sensor Network (WSN) by allowing only a subset of nodes to be active at any time with guaranteed network coverage. We present the first centralized and distributed solutions for computing Bounded-Distance Multi-Coverage Backbones in WSNs. The solutions are based on the (k, r)-CDS problem from graph theory for computing backbones in which any regular node is covered by at least k backbone members within distance r, offering a variable degree of redundancy and reliability. Applications that require reliable data gathering with bounded-delays are the intended targets for such structures. Given that the centralized solution is unsuitable for WSNs, because of the incurred control overhead, it is used as a lower bound for evaluating the performance of the distributed solution. The distributed solution is source-based in the sense that usually the base-station (or sink) is the focus of attention in a WSN. The two approaches are evaluated through extensive simulations, and it is shown that even though the distributed solution builds larger backbones, it does not incur on much control overhead.