Customizable localized computation of connected dominating sets for self-organizing wireless networks

In self-organizing wireless networks, connected dominating sets (CDS) have many applications such as in routing. Many algorithms for localized computation of CDS have been proposed. However, in reality, customization is needed under many situations when certain nodes should be given higher priority for entering CDS. A gap between the research and reality exists because the customizability has not been fully explored so far. In this paper, we attempt to fill the gap by proposing a purely localized algorithm that is highly customizable. Its message complexity is also low. Theoretical analysis is provided for performance verification. We also customize the algorithm to observe better performance. Finally, by simulations, the general (i.e. non-customized) algorithm and the customized version are compared with two purely localized algorithms in term of average CDS sizes.