Self-stabilizing algorithm for minimal (α,β)-dominating set

Leila Saadi

doi:10.1080/23799927.2022.2072400

Self-stabilizing algorithm for minimal (α,β)-dominating set

2022-05-19

1

OA

AI

DOI：10.1080/23799927.2022.2072400

原文链接

摘要

En 中文

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 (alpha , beta)-dominating set. An alpha-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 alpha, where 0 < alpha <= 1 . In the same way, an (alpha , beta)-dominating set is a subset of nodes S such that: S is alpha-dominating set and for each node v in S, the rate of neighbours of v inside S is greater than beta, where 0 <= beta <= 1 . Mathematical proofs and simulation tests show the correctness and the efficiency of the proposed algorithm. Through our proposed variant ( alpha , beta ) -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

Keyword:

Self-stabilizing algorithm

dominating set

alpha-domination

distributed system

expression distance-2 model

Self-stabilizing algorithm for minimal (α,β)-dominating set

摘要

期刊

机构

引用论文