Self-stabilizing algorithm for minimal (α, β)-dominating set. Issue 2 (3rd April 2022) - Saadi, Leila; Benreguia, Badreddine; Arar, Chafik; Moumen, Hamouma
Abstract : This paper deals with the problem of finding dominating set using self-stabilization paradigm in distributed systems. Usually, members of a dominating set are selected to be as cluster heads in Wireless Sensor Networks (WSN) to ensure a permanent service availability. Since failures occur frequently inside WSN due to limited battery energy, self-stabilizing algorithm allows recomputing the dominating set, and hence the network returns to its ordinary running. Existing works have introduced many variants of self-stabilizing algorithms that compute minimal dominating set S where each node out of S has neighbours in S more than it has out S . In this paper, we introduce a generalized self-stabilizing algorithm called minimal ( α, β ) -dominating set. An α -dominating set is a subset of nodes S such that for any node v out of S, the rate of neighbours of v inside S must be greater than α, where 0 < α ≤ 1 . In the same way, an ( α, β ) -dominating set is a subset of nodes S such that: S is α -dominating set and for each node v in S, the rate of neighbours of v inside S is greater than β, where 0 ≤ β ≤ 1 . Mathematical proofs and simulation tests show the correctness and the efficiency of the proposed algorithm. Through our proposed variant ( α, β ) -domination, we prove rigorously the conjecture of Carrier et al. [ Self-stabilizing (f, g)-alliances with safe convergence, J. Parallel Distrib. Comput. 81–82 (2015), pp. 11–23. doi:10.1016/j.jpdc.2015.02.001] who have proposed a self-stabilizing algorithm for a domination variant called ( f, g ) -alliance set only when f ≥ g . We prove the correctness of the case f < g .