Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks

Inspired by the backbone concept in wired networks, a Virtual Backbone (VB) is expected to benefit routing in Wireless Sensor Networks (WSNs). A Connected Dominating Set (CDS) based VB is a competitive approach among the existing methods used to establish VBs in WSNs. Most existing works focus on constructing a Minimum-sized CDS (MCDS), a k-connected m-dominating CDS, a minimum routing cost CDS or a bounded-diameter CDS. However, few works consider the load-balance factor. In this work, the size and the load-balance factors are both taken into account when constructing a VB in WSNs. Specifically, three NP-hard problems are investigated in the paper, namely, the MinMax Degree Maximal Independent Set (MDMIS) problem, the Load-Balanced Virtual Backbone (LBVB) problem, and the MinMax Valid-degree non-Backbone node Allocation (MVBA) problem. Furthermore, their approximation algorithms and comprehensive theoretical analysis of the approximation factors are presented. Finally, our theoretical analysis and the simulation results indicate that the proposed algorithms outperform the existing state-of-the-art approaches. (C) 2012 Elsevier B.V. All rights reserved.