Dynamic minimum spanning tree construction and maintenance for Wireless Sensor Networks
In a Wireless Sensor Network (WSN), finding the optimal route from each node to the sink is not a straightforward task because of the distributed and dynamic characteristics of the network. For instance, the network suffers frequent changes because the channel quality varies over time and the nodes can leave or join the network at any moment. In order to deal with this variability, we propose the Dynamic Gallager-Humblet-Spira (DGHS) algorithm that builds and maintains a minimum spanning tree for distributed and dynamic networks, and we have found that DGHS reduces the number of control messages and the energy consumption, at the cost of a slight increase in the memory size and convergence time. This paper presents a detailed description of the different stages of the DGHS algorithm (neighbor discovery, tree construction and data collection), an in-depth analysis of extensive results that validates our proposal, and an exhaustive description of the GHS limitations.
A. Castagnetti, A. Pegatoquet, T. N. Le, and M. Auguin, “A joint duty-cycle and transmission power management for energy harvesting wsn,” IEEE Transactions on Industrial Informatics , vol. 10, no. 2, pp. 928–936, May 2014.
R. G. Gallager, P. A. Humblet, and P. M. Spira, “A distributed algorithm for minimum-weight spanning trees,” ACM Trans. Program. Lang. Syst. , vol. 5, no. 1, pp. 66–77, Jan. 1983.
W. Fokkink, Distributed Algorithms: An Intuitive Approach . The MIT Press, 2013.
L. Ngqakaza and A. Bagula, Least Path Interference Beaconing Protocol (LIBP): A Frugal Routing Protocol for The Internet-of-Things . Cham: Springer International Publishing, 2014, pp. 148–161.
A. Bagula, D. Djenouri, and E. Karbab, “Ubiquitous sensor network management: The least interference beaconing model,” in 2013IEEE 24 th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC) , 2013, pp. 2352–2356.
S. Diaz, D. Mendez, and M. Scholzel, “Dynamic gallager-humblet-spira algorithm for wireless sensor networks,” in 2018 IEEE Colombian Conference on Communications and Computing (COLCOM) , May 2018, pp. 1–6.
C. Zhu, S. Wu, G. Han, L. Shu, and H. Wu, “A tree-cluster-based data-gathering algorithm for industrial wsns with a mobile sink,” IEEE Access , vol. 3, pp. 381–396, 2015.
H. Gong, L. Fu, X. Fu, L. Zhao, K. Wang, and X. Wang, “Distributed multicast tree construction in wireless sensor networks,” IEEE Transactions on Information Theory , vol. 63, no. 1, pp. 280–296, Jan. 2017.
S. Gopikrishnan and P. Priakanth, “Hybrid tree construction for sustainable delay aware data aggregation in wireless sensor networks,” Wirel. Pers. Commun. , vol. 90, no. 2, pp. 923–945, Sep. 2016.
W. Y. Alghamdi, H. Wu, W. Zheng, and S. S. Kanhere, “Constructing a shortest path overhearing tree with maximum lifetime in wsns,” in 201649 th HawaiiInternationalConferenceonSystemSciences(HICSS) , Jan. 2016, pp. 5858–5867.
R. Alexander and et al. , “RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks,” RFC 6550, Mar. 2012. [Online]. Available: https://rfc-editor.org/rfc/rfc6550.txt
T. H. Sardar, A. Khatun, and S. Khan, “Design of energy aware collection tree protocol in wireless sensor network,” in 2017 IEEE International Conference on Circuits and Systems (ICCS) , Dec. 2017, pp. 12–17.
S. Xie and Y. Wang, “Construction of tree network with limited delivery latency in homogeneous wireless sensor networks,” Wireless Personal Communications , vol. 78, no. 1, pp. 231–246, Sep. 2014.
K. Srinivasan, M. A. Kazandjieva, S. Agarwal, and P. Levis, “The beta-factor: Measuring wireless link burstiness,” in Proceedings of the 6 th ACM Conference on Embedded Network Sensor Systems , ser. SenSys ’08, New York, USA, 2008, pp. 29–42.
S. Imran and Y. Ko, “A continuous object boundary detection and tracking scheme for failure-prone sensor networks,” Sensors , vol. 17, no. 2, 2017.
S. Chouikhi, I. E. Korbi, Y. Ghamri-Doudane, and L. A. Saidane, “Recovery from simultaneous failures in a large scale wireless sensor network,” Ad. Hoc. Networks , vol. 67, no. Supplement C, pp. 68–76, 2017.
Z. Han, J. Wu, J. Zhang, L. Liu, and K. Tian, “A general self-organized tree-based energy-balance routing protocol for wireless sensor network,” IEEE Transactions on Nuclear Science , vol. 61, no. 2, pp. 732–740, Apr. 2014.
S. Wan, Y. Zhang, and J. Chen, “On the construction of data aggregation tree with maximizing lifetime in large-scale wireless sensor networks,” IEEE Sensors Journal , vol. 16, no. 20, pp. 7433–7440, Oct. 2016.
Y. Choi, M. Khan, V. S. A. Kumar, and G. Pandurangan, “Energy-optimal distributed algorithms for minimum spanning trees,” IEEE Journal on Selected Areas in Communications , vol. 27, no. 7, pp. 1297–1304, Sep. 2009.
M. Khan, V. S. A. Kumar, M. V. Marathe, G. Pandurangan, and S. S. Ravi, “Bi-criteria approximation algorithms for power-efficient and low-interference topology control in unreliable ad hoc networks,” in IEEE INFOCOM 2009 , Apr. 2009, pp. 370–378.
M. Khan and G. Pandurangan, “A fast distributed approximation algorithm for minimum spanning trees,” in Proceedings of the 20 th InternationalConferenceonDistributedComputing . Springer-Verlag, 2006, pp. 355–369.
O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis, “Collection tree protocol,” in Proceedings of the 7 th ACM Conference on Embedded Networked Sensor Systems , New York, NY, 2009, pp. 1–14.
P. Levis, T. H. Clausen, O. Gnawali, J. Hui, and J. Ko, “The Trickle Algorithm,” RFC 6206, Mar. 2011. [Online]. Available: https://rfc-editor.org/rfc/rfc6206.txt
J. Vasseur and A. Dunkels, Interconnecting Smart Objects with IP: The Next Internet . San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2010.
Copyright (c) 2019 Revista Facultad de Ingeniería Universidad de Antioquia
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors can archive the pre-print version (i.e., the version prior to peer review) and post-print version (that is, the final version after peer review and layout process) on their personal website, institutional repository and / or thematic repository
- Upon acceptance of an article, it will be published online through the page https://revistas.udea.edu.co/index.php/ingenieria/issue/archive in PDF version with its correspondent DOI identifier
The Revista Facultad de Ingeniería -redin- encourages the Political Constitution of Colombia, chapter IV
Chapter IV Sanctions 51
The following shall be liable to imprisonment for two to five years and a fine of five to 20 times the legal minimum monthly wage: (1) any person who publishes an unpublished literary or artistic work, or part thereof, by any means, without the express prior authorization of the owner of rights; (2) any person who enters in the National Register of Copyright a literary, scientific or artistic work in the name of a person other than the true author, or with its title altered or deleted, or with its text altered, deformed, amended or distorted, or with a false mention of the name of the publisher or phonogram, film, videogram or software producer; (3) any person who in any way or by any means reproduces, disposes of, condenses, mutilates or otherwise transforms a literary, scientific or artistic work without the express prior authorization of the owners thereof; (4) any person who reproduces phonograms, videograms, software or cinematographic works without the express prior authorization of the owner, or transports, stores, stocks, distributes, imports, sells, offers for sale, acquires for sale or distribution or in any way deals in such reproductions. Paragraph. If either the material embodiment or title page of or the introduction to the literary work, phonogram, videogram, software or cinematographic work uses the name, business style, logotype or distinctive mark of the lawful owner of rights, the foregoing sanctions shall be increased by up to half.