Abstract:

This study devises self-stabilizing algorithms that leverage the expression distance-2 paradigm to compute (i) a maximal distance-2 independent set, wherein selected nodes maintain a separation exceeding two edges, ensuring non-adjacency; and (ii) a minimal dominating set, wherein each external node has at least one node as a neighbor in the dominating set. The efficacy and convergence of the algorithms are established through rigorous proofs within the framework of the expression model. Extensive simulation tests validate the algorithms' proficiency in selecting a minimal subset of nodes across expansive network topologies. These algorithms find practical applications in network operations, particularly in ad hoc and wireless sensor networks for the selection of cluster heads that facilitate critical services. Moreover, the self-stabilizing property of the algorithms guarantees the robust reconfiguration of cluster heads post-failure, thereby preserving network functionality amidst disruptions.

Publisher's Version