A self-stabilizing protocol for minimal weighted dominating sets in arbitrary networks
Guangyuan Wang, Hua Wang, Xiaohui Tao, Ji Zhang · 2013
A lot of self-stabilizing algorithms for computing dominating sets problem have been proposed in the literature due to many real-life applications. Most of the proposed algorithms either work for dominating sets with a uniform weight or find approximation solutions to weighted dominating sets. However, for non-uniform weighted dominating sets (WDS) problem, there is no self-stabilizing algorithm for the WDS. Furthermore, how to find the minimal weighted dominating set is a challenge. In this paper, we propose a self-stabilizing algorithm for the minimal weighted dominating set (MWDS) under a central daemon model when operating in any general network. We further prove that the worst case convergence time of the algorithm from any arbitrary initial state is O(n2) steps where n is the number of nodes in the network.