Delay-constrained data aggregation scheduling in wireless sensor networks

Cheng Feng, Zhijun Li, Shouxu Jiang, Weipeng Jing

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

This article focuses on data aggregation scheduling problem with delay constraint in wireless sensor networks. Prior works on this problem have dealt with a tree topology wireless sensor network. However, in fact it is more common that the topology of wireless sensor network is graph topology. Delay-constrained data aggregation problem is formulated. To solve this problem, we propose an algorithm based on dynamic programming in the shortest path tree of the wireless sensor network. This approach classifies conflicts into two types, tree-inside conflicts and tree-outside conflicts with the aggregating tree. First, scheduling transmission time utilizes a dynamic programming algorithm. Then, transmissions with tree-outside conflicts are removed with maximum weight independent set in tree-outside conflict graph. As the scheduling performance depends on the aggregation tree, we propose another idea, simultaneous execution of aggregation tree construction and scheduling. We propose a greedy algorithm in wireless sensor networks. This approach is to maximize the number of scheduled nodes in every time slot from deadline to time slot 1. Simulation results show that greedy algorithm in wireless sensor networks outperforms dynamic programming in the shortest path tree and naive algorithm in terms of the effectiveness and the average delay.

Original languageEnglish (US)
JournalInternational Journal of Distributed Sensor Networks
Volume13
Issue number6
DOIs
StatePublished - Jun 2017

Bibliographical note

Publisher Copyright:
© The Author(s) 2017.

Keywords

  • Data aggregation
  • Delay constraint
  • Dynamic programming
  • Maximum weight independent set
  • Wireless sensor networks

Fingerprint

Dive into the research topics of 'Delay-constrained data aggregation scheduling in wireless sensor networks'. Together they form a unique fingerprint.

Cite this