research-article

Distributed Low-Latency Data Aggregation Scheduling in Wireless Sensor Networks

Authors:

Mohamed Younis,

Djamel Djenouri,

Abdelouahid Derhab,

Nadjib BadacheAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 11, Issue 3

Article No.: 49, Pages 1 - 36

https://doi.org/10.1145/2744198

Published: 23 April 2015 Publication History

Abstract

This article considers the data aggregation scheduling problem, where a collision-free schedule is determined in a distributed way to route the aggregated data from all the sensor nodes to the base station within the least time duration. The algorithm proposed in this article (Distributed algorithm for Integrated tree Construction and data Aggregation (DICA)) intertwines the tree formation and node scheduling to reduce the time latency. Furthermore, while forming the aggregation tree, DICA maximizes the available choices for parent selection at every node, where a parent may have the same, lower, or higher hop count to the base station.

The correctness of the DICA is formally proven, and upper bounds for time and communication overhead are derived. Its performance is evaluated through simulation and compared with six delay-aware aggregation algorithms. The results show that DICA outperforms competing schemes. The article also presents a general hardware-in-the-loop framework (DAF) for validating data aggregation schemes on Wireless Sensor Networks (WSNs). The framework factors in practical issues such as clock synchronization and the sensor node hardware. DICA is implemented and validated using this framework on a test bed of sensor motes that runs TinyOS 2.x, and it is compared with a distributed protocol (DAS) that is also implemented using the proposed framework.

References

[1]

Miloud Bagaa, Yacine Challal, Adlen Ksentini, Abdelouahid Derhab, and Nadjib Badache. 2014. Data aggregation scheduling algorithms in wireless sensor networks: Solutions and challenges. IEEE Communications Surveys & Tutorials 16, 3 (Third 2014), 1339--1368.

[2]

Miloud Bagaa, Abdelouahid Derhab, Noureddine Lasla, Abdelraouf Ouadjaout, and Nadjib Badache. 2012. Semi-structured and unstructured data aggregation scheduling in wireless sensor networks. In Proc. IEEE INFOCOM’12.

[3]

Chafika Benzaïd, Miloud Bagaa, and Mohamed Younis. 2014. An efficient clock synchronization protocol for wireless sensor networks. In Proceedings of IEEE IWCMC’14.

[4]

Yu Bo, Li Jianzhong, and Li Yingshu. 2009. Distributed data aggregation scheduling in wireless sensor networks. In Proceedings of IEEE INFOCOM’09. 2159--2167.

[5]

X. Chen, X. Hu, and J. Zhu. 2005. Minimum data aggregation time problem in wireless sensor networks. In Proc. MSN’05. Lecture Notes in Computer Science, Vol. 3794. Springer-Verlag, 133--142.

Digital Library

[6]

C. B. des Roziers, G. Chelius, T. Ducrocq, E. Fleury, A. Fraboulet, A. Gallais, N. Mitton, T. Noel, E. Valentin, and J. Vandaele. 2011. Two demos using SensLAB: Very large scale open WSN testbed. In Proc. IEEE DCOSS’11.

[7]

Djamel Djenouri and Miloud Bagaa. 2014. Synchronization protocols and implementation issues in wireless sensor networks: A review. IEEE Systems Journal PP (2014), 1--11.

[8]

Djamel Djenouri, Nassima Merabtine, Fatma Zohra Mekahlia, and Messaoud Doudou. 2013. Fast distributed multi-hop relative time synchronization protocol and estimators for wireless sensor networks. Ad Hoc Networks 11, 8 (2013), 2329--2344.

Digital Library

[9]

Denise Dudek, Christian Haas, Andreas Kuntz, Martina Zitterbart, Daniela KrÃ¼ger, Peter Rothenpieler, Dennis Pfisterer, and Stefan Fischer. 2009. A wireless sensor network for border surveillance. Proceedings of ACM SenSys’09.

Digital Library

[10]

Shashidhar Rao G, Milind Daw, Ravi Prakash, and S. Venkatesan. 2003. Energy Efficient Schemes for Wireless Sensor Networks with Multiple Mobile Base Stations. (2003).

[11]

A. Ghosh, O. D. Incel, V. S. A. Kumar, and B. Krishnamachari. 2011. Multichannel scheduling and spanning trees: Throughput--delay tradeoff for fast data collection in sensor networks. IEEE/ACM Transactions on Networking 19, 6 (2011), 1731--1744.

Digital Library

[12]

Amitabha Ghosh, Özlem Durmaz Incel, Bhaskar Krishnamachari, and Anil Vullikanti. 2009. Multi-channel scheduling algorithms for fast aggregated convergecast in sensor networks. In Proc. IEEE MASS’09. 363--372.

[13]

Mohamed Hefeeda and Majid Bagheri. 2009. Forest fire modeling and early detection using wireless sensor networks. Ad Hoc & Sensor Wireless Networks 7, 3-4 (2009), 169--224.

[14]

Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, and Kristofer Pister. 2000. System architecture directions for networked sensors. ACM SIGPLAN Not. 35, 11 (Nov. 2000), 93--104.

Digital Library

[15]

S. Huang, P. Wan, C. Vu, Y. Li, and F. Yao. 2007. Nearly constant approximation for data aggregation scheduling in wireless sensor networks. In Proceedings of IEEE INFOCOM’07. 366--372.

[16]

Wei Huangfu, Yan Liu, Bin Duan, Limin Sun, Jian Ma, and Canfeng Chen. 2008. EATA: Effectiveness based aggregation time allocation algorithm for wireless sensor networks. Proceedings of the IEEE Symposium on Computers and Communications (ISCC’08).

[17]

O. D. Incel and B. Krishnamachari. 2008. Enhancing the data collection rate of tree-based aggregation in wireless sensor networks. In Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON’08). 569--577.

[18]

Özlem Durmaz Incel, Amitabha Ghosh, Bhaskar Krishnamachari, and Krishna Chintalapudi. 2012. Fast data collection in tree-based wireless sensor networks. IEEE Trans. Mob. Comput. 11, 1 (2012), 86--99.

Digital Library

[19]

Nhat X. Lam, Min Kyung An, Dung T. Huynh, and Trac N. Nguyen. 2011. Minimum latency data aggregation in the physical interference model. In Proceedings of the 14th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (Proc. ACM MSWIM’11). ACM, New York, NY, 93--102.

Digital Library

[20]

Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. 2002. TAG: A Tiny Aggregation service for ad-hoc sensor networks. ACM SIGOPS Oper. Syst. Rev. 36, SI (Winter 2002), 131--146.

Digital Library

[21]

Baljeet Malhotra, Ioanis Nikolaidis, and Mario Nascimento. 2010. Aggregation convergecast scheduling in wireless sensor networks. Springer Wireless Networks 17, 2 (2010), 319--335.

Digital Library

[22]

M. Maróti, B. Kusy, G. Simon, and A. Lédezi. 2004. The flooding synchronization protocol. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys’04).

[23]

Networkx. http://networkx.lanl.gov.

[24]

L. Philip, L. Nelson, W. Matt, and C. David. 2003. TOSSIM: Accurate and scalable simulation of entire TinyOS applications. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys’03). ACM, New York, NY.

Digital Library

[25]

V. Raghunathan, C. Schurgers, Sung Park, and M. B. Srivastava. 2002. Energy-aware wireless microsensor networks. IEEE Signal Processing Magazine 19, 2 (2002), 40--50.

[26]

Andreas Savvides, Chih-Chieh Han, and Mani B. Strivastava. 2001. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom’01).

Digital Library

[27]

B. L. Titzer, D. K. Lee, and J. Palsberg. 2005. Avrora: Scalable sensor network simulation with precise timing. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN’05).

Digital Library

[28]

Peng-Jun Wan, Scott C.-H. Huang, Lixin Wang, Zhiyuan Wan, and Xiaohua Jia. May 2009. Minimum-latency aggregation scheduling in multihop wireless networks. In Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’09). 185--194.

Digital Library

[29]

Peng-Juan Wan, K. M. Alzoubi, and O. Frieder. 2002. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02). 1597--1604.

[30]

G. Werner-Allen, P. Swieskowski, and M. Welsh. 2005. MoteLab: A wireless sensor network testbed. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN’05).

Digital Library

[31]

WISEBED. 2012. Homepage. Retrieved March 12, 2014, from http://www.wisebed.eu.

[32]

Xiaohua Xu, Xiang-Yang Li, Xufei Mao, Shaojie Tang, and Shiguang Wang. 2011. A delay-efficient algorithm for data aggregation in multihop wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems 22, 1 (2011), 163--175.

Digital Library

[33]

Bo Yu, Jianzhong Li, and Yingshu Li. 2009. Distributed data aggregation scheduling in wireless sensor networks. In INFOCOM. 2159--2167.

Cited By

Laidi RDjenouri DDjenouri YLin J(2024)TG-SPRED: Temporal Graph for Sensorial Data PREDictionACM Transactions on Sensor Networks10.1145/364989220:3(1-20)Online publication date: 13-Apr-2024
https://dl.acm.org/doi/10.1145/3649892
Vo VLe DRaza SKim MChoo H(2024)Active Neighbor Exploitation for Fast Data Aggregation in IoT Sensor NetworksIEEE Internet of Things Journal10.1109/JIOT.2024.335473011:8(13199-13216)Online publication date: 15-Apr-2024
https://doi.org/10.1109/JIOT.2024.3354730
Long PWu YChen QCheng L(2024)Distributed low‐latency broadcast scheduling for multi‐channel duty‐cycled wireless IoT networksConcurrency and Computation: Practice and Experience10.1002/cpe.804436:13Online publication date: 14-Feb-2024
https://doi.org/10.1002/cpe.8044
Show More Cited By

Index Terms

Distributed Low-Latency Data Aggregation Scheduling in Wireless Sensor Networks
1. Networks
  1. Network properties
    1. Network structure
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Efficient data aggregation scheduling in wireless sensor networks with multi-channel links
MSWiM '13: Proceedings of the 16th ACM international conference on Modeling, analysis & simulation of wireless and mobile systems

In-network data aggregation is often pursued to remove redundancy and correlate the data en-route to the base-station in order to save energy in wireless sensor networks (WSNs). In this paper, we present a novel cross-layer approach for reducing the ...
In-network aggregation trade-offs for data collection in wireless sensor networks

This paper explores in-network aggregation as a power-efficient mechanism for collecting data in wireless sensor networks. In particular, we focus on sensor network scenarios where a large number of nodes produce data periodically. Such communication ...
Achieving Scalable Privacy Preserving Data Aggregation for Wireless Sensor Networks
CIT '10: Proceedings of the 2010 10th IEEE International Conference on Computer and Information Technology

A sink node must be aware of the identifications (node IDs) of those all sensor nodes which contribute in aggregated value of sensors data in order to derive exact result of them in privacy preserving data aggregation scheme for wireless sensor networks ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 11, Issue 3

May 2015

400 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/2737802

Editor:
Chenyang Lu
Department of Computer Science and Engineering / School of Engineering and Applied Sciences / Washington University, MO

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 23 April 2015

Accepted: 01 March 2015

Revised: 01 October 2014

Received: 01 March 2014

Published in TOSN Volume 11, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Algerian Ministry of Higher Education through the DGRSDT
National Science Foundation, award # CNS 1018171

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
587
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Laidi RDjenouri DDjenouri YLin J(2024)TG-SPRED: Temporal Graph for Sensorial Data PREDictionACM Transactions on Sensor Networks10.1145/364989220:3(1-20)Online publication date: 13-Apr-2024
https://dl.acm.org/doi/10.1145/3649892
Vo VLe DRaza SKim MChoo H(2024)Active Neighbor Exploitation for Fast Data Aggregation in IoT Sensor NetworksIEEE Internet of Things Journal10.1109/JIOT.2024.335473011:8(13199-13216)Online publication date: 15-Apr-2024
https://doi.org/10.1109/JIOT.2024.3354730
Long PWu YChen QCheng L(2024)Distributed low‐latency broadcast scheduling for multi‐channel duty‐cycled wireless IoT networksConcurrency and Computation: Practice and Experience10.1002/cpe.804436:13Online publication date: 14-Feb-2024
https://doi.org/10.1002/cpe.8044
Bomnale AMore A(2023)Node utilization index-based data routing and aggregation protocol for energy-efficient wireless sensor networksThe Journal of Supercomputing10.1007/s11227-023-05800-480:7(9220-9252)Online publication date: 6-Dec-2023
https://doi.org/10.1007/s11227-023-05800-4
Long PWu YChen QCheng LTao Y(2023)Distributed Latency-Efficient Beaconing for Multi-channel Asynchronous Duty-Cycled IoT NetworksAlgorithms and Architectures for Parallel Processing10.1007/978-981-97-0808-6_3(39-55)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-97-0808-6_3
Chen QCai ZCheng LGao HLi J(2022)Structure-Free Broadcast Scheduling for Duty-Cycled Multihop Wireless Sensor NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2021.308414521:12(4624-4641)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TMC.2021.3084145
Chen QCai ZCheng LGao H(2022)Structure-Free General Data Aggregation Scheduling for Multihop Battery-Free Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2021.305355721:9(3342-3359)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TMC.2021.3053557
Zhu TLi JGao HLi Y(2022)Data Aggregation Scheduling in Battery-Free Wireless Sensor NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2020.303567121:6(1972-1984)Online publication date: 1-Jun-2022
https://doi.org/10.1109/TMC.2020.3035671
Vo VNguyen TLe DKim MChoo H(2022)Link-Delay-Aware Reinforcement Scheduling for Data Aggregation in Massive IoTIEEE Transactions on Communications10.1109/TCOMM.2022.318640770:8(5353-5367)Online publication date: Aug-2022
https://doi.org/10.1109/TCOMM.2022.3186407
Jiao XLou WGuo SWang NChen CLiu K(2022)Hypergraph-Based Active Minimum Delay Data Aggregation Scheduling in Wireless-Powered IoTIEEE Internet of Things Journal10.1109/JIOT.2021.31163449:11(8786-8799)Online publication date: 1-Jun-2022
https://doi.org/10.1109/JIOT.2021.3116344
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents