Construction of low cost virtual backbone for sensor networks

Virtual backbone formation is a popular approach to reduce the routing overhead and increase the network scalability in the wireless ad hoc networks. Most of the centralized and distributed algorithms aim at minimizing the size of the virtual backbone. However, if every node of the network has a cost for handling the additional responsibilities as backbone node, goal of the backbone construction algorithm should be the minimization of the total cost. In this paper, we propose a distributed low cost backbone construction algorithm with the message complexity of O(n). Simulation results show that the proposed algorithm is cost and message efficient.