Constructing a load-balanced virtual backbone in wireless sensor networks

A Connected Dominating Set (CDS) is used as a virtual backbone for efficient routing and broadcasting in Wireless Sensor Networks (WSNs). Most existing works focus on constructing a Minimum CDS (MCDS), a k-connect m-dominating CDS, a minimum routing cost CDS or a bounded-diameter CDS. However, no work considers the load-balance factor of CDSs in WSNs. In this paper, we propose a new concept - the Load-Balanced CDS (LBCDS), and a new problem - the Load-Balanced Allocate Dominatee (LBAD) problem. Consequently, a greedy-based approximation algorithm is proposed to construct an LBCDS in a WSN in this paper. Moreover, we propose an optimal centralized algorithm and an efficient probability-based distributed algorithm to solve the LBAD problem. Through extensive simulations, we demonstrate that our proposed methods extend network lifetime by 80% compared with the latest CDS construction algorithm.