TY - GEN

T1 - Bounded-distance multi-coverage backbones in wireless sensor networks

AU - Sausen, P. S.

AU - Spohn, M. A.

AU - Lima, A. M.N.

AU - Perkusich, A.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - Backbone

KW - Connected dominating sets

KW - Domination in graphs

KW - Wireless sensor networks

UR - http://www.scopus.com/inward/record.url?scp=35248818226&partnerID=8YFLogxK

U2 - 10.1145/1244002.1244056

DO - 10.1145/1244002.1244056

M3 - Conference contribution

AN - SCOPUS:35248818226

SN - 1595934804

SN - 9781595934802

T3 - Proceedings of the ACM Symposium on Applied Computing

SP - 203

EP - 208

BT - Proceedings of the 2007 ACM Symposium on Applied Computing

PB - Association for Computing Machinery

T2 - 2007 ACM Symposium on Applied Computing

Y2 - 11 March 2007 through 15 March 2007

ER -