AHSWN Home • Issue Contents • Forthcoming Papers

Self-stabilizing Algorithm for Generic Aggregated Weighted Connected Dominating Set
Karim Bessaoud

The addressed problem in this paper is the construction of a virtual backbone for wireless ad hoc networks. Indeed, to tackle the lack of physical infrastructure in the wireless ad hoc networks, a logical infrastructure is proposed. Usually, logical infrastructures have been extensively used in wireless ad hoc networks for various applications such as routing or scheduling. There are several kinds of logical infrastructures that can be used for this purpose, connected dominating set (CDS) is one of them.

In this paper, we present a self-stabilizing algorithm for the construction of a Low Weight Connected Dominating Set by considering weighted nodes and links. The self-stabilizing property confers to our algorithm the ability to recover in a finite time after a transient fault. Our algorithm has been evaluated through extensive simulations that show the efficiency of our solution in different contexts and the large possible applications of our algorithm.

Keywords: Connected Dominating Set, clustering, self-stabilizing algorithms, distributed algorithms, wireless ad-hoc network, wireless sensor networks

Full Text (IP)