Delay Efficient Scheduling Algorithms for Data Aggregation in Multi-Channel Asynchronous Duty-Cycled WSNs

Xianlong Jiao, Wei Lou, Songtao Guo, Libin Yang, Xinxi Feng, Xiaodong Wang, Guirong Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)


Data aggregation scheduling is a critical issue in WSNs. This paper studies the Delay efficient Data Aggregation scheduling problem in multi-Channel asynchronous Duty-cycled WSNs (DDACD problem), which aims to accomplish data aggregation with minimum delay. Existing studies, nevertheless, either focus on non-sleeping scenarios or assume that nodes communicate with one single channel, and thus may have poor performance if directly applied to multi-channel asynchronous duty-cycled scenarios. We first show that the DDACD problem is NP-hard. Then, we propose two new concepts of candidate active conflict graphs (CACGs) and feasible active conflict graphs (FACGs) to depict the relationship of the data aggregation links and present two coloring methods to well separate the links at different time slots or on different channels. Based on these two new concepts and two coloring methods, we propose an efficient data aggregation scheduling algorithm called EDAS, which exploits the fewest-children-first rule to choose the forwarding nodes to benefit the link scheduling. To reduce unused time slots or channels, we further propose a novel algorithm called NDAS by making full use of the characteristics of multi-channel asynchronous duty-cycled WSNs. We prove that our algorithms can achieve provable performance guarantee. The results of extensive simulations confirm the efficiency of our algorithms.

Original languageEnglish
Article number8743491
Pages (from-to)6179-6192
Number of pages14
JournalIEEE Transactions on Communications
Issue number9
Publication statusPublished - Sep 2019
Externally publishedYes


  • Approximation algorithms
  • data aggregation scheduling
  • duty cycle
  • multi-channel
  • wireless sensor networks

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this