Dynamic minimum spanning tree construction and maintenance for Wireless Sensor Networks
DOI:
https://doi.org/10.17533/udea.redin.20190508Keywords:
self-organization, topology control, self-healingAbstract
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.
Downloads
References
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.
Downloads
Published
How to Cite
Issue
Section
License
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.
Revista Facultad de Ingeniería, Universidad de Antioquia is licensed under the Creative Commons Attribution BY-NC-SA 4.0 license. https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en
You are free to:
Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material
Under the following terms:
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
NonCommercial — You may not use the material for commercial purposes.
ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
The material published in the journal can be distributed, copied and exhibited by third parties if the respective credits are given to the journal. No commercial benefit can be obtained and derivative works must be under the same license terms as the original work.
