Data aggregation scheduling in uncoordinated duty-cycled wireless sensor networks under protocol interference model

Xianlong Jiao, Wei Lou, Xiaodong Wang, Jiannong Cao, Ming Xu, Xingming Zhou

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


Data aggregation is a critical and widely-used operation in wireless sensor networks (WSNs). Data aggregation scheduling (DAS) aims to find an interference-free scheduling for data aggregation with the minimum latency. Most existing algorithms for the DAS problem, unfortunately, assume that nodes are always active, and hence are not suitable for duty-cycled scenarios. In this paper, we investigate the DAS problem in uncoordinated duty-cycled WSNs (DAS-UDC problem) under protocol interference model and prove its NP-hardness. To solve this problem, we propose two novel approximation algorithms called SDAS and CDAS with the data aggregation latency of at most O(Rs+ Δ) and O(R + Δ) respectively, where Rs, Δ and R are the maximum depth of the breadthfirst- search tree rooted at the sink node s, the maximum node degree and the graph-theoretic radius of the network respectively.We conduct extensive simulations to evaluate the performance of our algorithms and report their average performance.
Original languageEnglish
Pages (from-to)315-338
Number of pages24
JournalAd-Hoc and Sensor Wireless Networks
Issue number2-4
Publication statusPublished - 2 Jul 2012


  • Approximation algorithms
  • Breadth-first-search
  • Data aggregation scheduling
  • Duty cycle
  • Protocol interference model
  • Wireless sensor networks

ASJC Scopus subject areas

  • Computer Science(all)
  • Instrumentation
  • Electrical and Electronic Engineering

Cite this