Scholarlink

In this paper, we study the problem of constructing a minimum dominating set (MDS) and a minimum connected dominating set (MCDS) in WSNs under the sleeping model. The sleeping model and the notion of awake complexity, which are recently introduced in the distributed computing literature, can model energy consumption of algorithms for wireless sensor networks (WSNs) in a more suited way. To the best of our knowledge, this paper is the first to study these problems under the sleeping model. Our MDS algorithm achieves a constant factor approximation for MDS in growth-bounded graphs in O(1) average and sublogarithmic worst-case awake complexity, whereas our MCDS algorithm is a 8.399 approximation algorithm for MCDS in Unit Disk Graphs (UDG) in \(O(\log n)\) worst-case awake complexity and \(O(n\log n)\) round complexity.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Minimum Dominating Set and Minimum Connected Dominating Set Construction in Wireless Sensor Networks Under the Sleeping Model

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Tan D. Lam,
  • Dung T. Huynh

摘要

In this paper, we study the problem of constructing a minimum dominating set (MDS) and a minimum connected dominating set (MCDS) in WSNs under the sleeping model. The sleeping model and the notion of awake complexity, which are recently introduced in the distributed computing literature, can model energy consumption of algorithms for wireless sensor networks (WSNs) in a more suited way. To the best of our knowledge, this paper is the first to study these problems under the sleeping model. Our MDS algorithm achieves a constant factor approximation for MDS in growth-bounded graphs in O(1) average and sublogarithmic worst-case awake complexity, whereas our MCDS algorithm is a 8.399 approximation algorithm for MCDS in Unit Disk Graphs (UDG) in \(O(\log n)\) worst-case awake complexity and \(O(n\log n)\) round complexity.