Self-Stabilizing Algorithm for Low Weight Connected Dominating Set

Recently, virtual backbones have been extensively used in wireless ad-hoc networks for various applications such as routing, route maintenance, broadcasting or scheduling. In wireless ad-hoc and sensor networks, a Connected Dominating Set (CDS) is useful as a virtual backbone due to the absence of fixed infrastructure or centralized management. Most of CDS construction methods seek to minimize the size of the backbone. Nevertheless, other constraints than reducing the number of nodes can be considered. In that case, it is more interesting to consider nodes´ weights (according to a specific purpose) and to reduce the total backbone´s weight. This construction is called a Low Weight Connected Dominating Set (LWCDS). In this paper, we present a self-stabilizing distributed algorithm for the construction of a LWCDS. The self-stabilizing property confers to our algorithm the ability to recover in a finite time after a transient fault. Our algorithm is evaluated through extensive simulations that show the efficiency of our solution in different contexts and the large possible applications of our algorithm. We also introduce two new evaluation criteria to evaluate the algorithms of CDS construction in the specific context of mobility.