Dynamic minimum spanning tree construction and maintenance for Wireless Sensor Networks





self-organization, topology control, self-healing


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.

= 214 veces | PDF
= 186 veces|


Download data is not yet available.

Author Biographies

Sergio Diaz, Pontifical Xavierian University

Electronic Engineering Department.

Diego Mendez, Pontifical Xavierian University

Electronic Engineering Department.


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.




How to Cite

Diaz, S., & Mendez, D. (2019). Dynamic minimum spanning tree construction and maintenance for Wireless Sensor Networks. Revista Facultad De Ingeniería Universidad De Antioquia, (93), 57–69. https://doi.org/10.17533/udea.redin.20190508

Similar Articles

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 > >> 

You may also start an advanced similarity search for this article.