A fault-tolerant and distributed capacitated connected dominating set algorithm for wireless sensor networks

Arapoglu O., DAĞDEVİREN O.

COMPUTER STANDARDS & INTERFACES, vol.77, 2021 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 77
  • Publication Date: 2021
  • Doi Number: 10.1016/j.csi.2020.103490
  • Keywords: Capacitated connected dominating set, Self-stabilizing algorithms, Distributed algorithms, Wireless sensor networks, Fault tolerance, AD-HOC, ENERGY-EFFICIENT, MINIMUM CDS, CONSTRUCTION, APPROXIMATION


Energy efficiency is one of the major issues in wireless sensor networks (WSNs) that lack a fixed infrastructure and centralized control. In order to prolong the network lifetime, a connected dominating set (CDS) has been widely used as a virtual backbone in WSNs. The sensor nodes in WSNs are prone to failure due to a lack of battery, hardware damage, link failure, or environmental interference. Therefore, designing an energy-efficient and fault-tolerant CDS algorithm is quite vital in WSNs. A non-masking fault tolerance method denoted selfstabilizing tolerates any finite number of transient faults. In this paper, we propose a fault-tolerant distributed algorithm for a minimal capacitated CDS (CapCDS) construction in WSNs. To the best of our knowledge, this is (the first distributed self-stabilizing CapCDS algorithm. It makes an illegitimate system legitimate at most n2 3 + )2n moves by using an unfair distributed scheduler where n is the number of nodes. The performance of the algorithm is validated through extensive experimental testbeds and simulations.