期刊名称：International Journal of Distributed Sensor Networks
印刷版ISSN：1550-1329
电子版ISSN：1550-1477
出版年度：2017
卷号：13
期号：6
页码：1
DOI：10.1177/1550147717716591
出版社：Hindawi Publishing Corporation
摘要：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.
关键词：Wireless sensor networks; data aggregation; delay constraint; dynamic programming; maximum weight independent set
