Self-stabilizing algorithm for minimal (α, β)-dominating set. Issue 2 (3rd April 2022)

• Record Type: Journal Article
• Authors: Saadi, Leila; Benreguia, Badreddine; Arar, Chafik; Moumen, Hamouma
• Is Part Of: International journal of computer mathematics. Volume 7:Issue 2(2022)
• Page Start: 81
• Page End: 94
• Publication Date: 2022-04-03
• Subjects: Self-stabilizing algorithm -- dominating set -- α-domination -- distributed system -- expression distance-2 model; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2022.2072400
• Languages: English
• ISSNs: 2379-9927

Abstract

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 .