Self-stabilizing distributed formation of minimal k-dominating sets in mobile ad Hoc networks

Li-Hsing Yen*, Zong Long Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Dominating set in a mobile ad-hoc network (MANET) is a collection of devices acting as servers that store, forward, or backup data for other devices not in the set. To fulfill the service requirement, every device is either a dominator or adjacent to a dominator. Devices of the latter case are dominatees. To provide a more robust service, we can extend the definition of dominating set to k-dominating set, where each dominatee must be adjacent to at least k dominators (k is a constant). This paper proposes a self-stabilizing protocol that identifies a kdominating set in a MANET. The identified set is guaranteed minimal in the sense that it contains no proper subset that is also a k-dominating set. We prove correctness and analyze stability property of this protocol. Simulation results indicate that the proposed protocol finds kdominating sets of smaller size when compared with existing approaches. The message overhead of the proposed protocol is proportional to the number of nodes and is small with either small or large k.

Original languageEnglish
Pages (from-to)38-48
Number of pages11
JournalJournal of Computers (Taiwan)
Issue number4
StatePublished - 1 Jan 2017


  • distributed algorithms
  • dominating set
  • self-stabilization


Dive into the research topics of 'Self-stabilizing distributed formation of minimal k-dominating sets in mobile ad Hoc networks'. Together they form a unique fingerprint.

Cite this