Break-and-join tree construction for latency-aware data aggregation in wireless sensor networks
- PDF / 2,471,728 Bytes
- 15 Pages / 595.276 x 790.866 pts Page_size
- 4 Downloads / 202 Views
(0123456789().,-volV)(0123456789().,-volV)
Break-and-join tree construction for latency-aware data aggregation in wireless sensor networks Tien-Dung Nguyen1
•
Vyacheslav Zalyubovskiy2 • Duc-Tai Le3
•
Hyunseung Choo4
Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Emerging applications require processing a huge amount of environmental data from wireless sensor networks, and then triggering appropriate actions in response to the detected events. To this end, it is desirable to minimize the time needed for data aggregation. This paper investigates the minimum-latency aggregation scheduling problem in wireless sensor networks. We propose an aggregation tree construction algorithm called Break-and-Join which adjusts any aggregation tree toward a smaller delay one. In order to perform tree adjustments, the algorithm iteratively changes parent of some nodes in the tree, using a novel numerical metric as a tree quality guideline. Each node determines if it can adopt an additional child in the neighborhood in order to relax the aggregation load at some bottleneck node in the network, thereby improving the overall aggregation tree quality. We performed the algorithm on several state-of-the-art aggregation schemes, and the results shows that final aggregation delay is quite indifferent to choice of initial tree and the tree quality can be significantly improved (e.g. 7 times for shortest path tree). Scheduling on the obtained trees also outperforms the best known scheme up to 13% in terms of delay. Keywords Wireless sensor networks Data aggregation Tree construction Minimum latency Parent changing
1 Introduction Wireless sensor networks (WSNs) have a wide range of applications, such as forest fire detection and security surveillance, in which fast data delivery to a sink is critical in order to trigger appropriate actions [1]. To this end, & Hyunseung Choo [email protected] Tien-Dung Nguyen [email protected] Vyacheslav Zalyubovskiy [email protected] Duc-Tai Le [email protected] 1
Convergence Research Center, Sungkyunkwan University, Suwon, Korea
2
Sobolev Institute of Mathematics, Novosibirsk, Russia
3
Department of Electrical and Computer Engineering, Sungkyunkwan University, Suwon, Korea
4
College of Computing, Sungkyunkwan University, Suwon, Korea
delay performance of a data collection scheme is gaining greater attention [2, 3]. In a data collection scheme, sensor nodes come with very short transmission ranges so that data are collected through multi-hop transmissions [4]. Moreover, sensory data in a WSN are typically correlated, so the aggregation technique is performed to reduce network traffic. Each interior node needs to collect data from its neighbors, combine them into a single outgoing packet, and then transmit the packet toward the sink [5]. The transmission links form a data aggregation tree rooted at the sink node. In multi-hop wireless communication, collisions may happen when transmissions from two or more nodes arrive simultaneously at the same destination [6]. A pr
Data Loading...
