- search hit 1 of 1
Dynamic Gallager-Humblet-Spira Algorithm for Wireless Sensor Networks
- The problem of constructing and maintaining a tree topology in a distributed manner is a challenging task in WSNs. This is because the nodes have limited computational and memory resources and the network changes over time. We propose the Dynamic Gallager-Humblet-Spira (D-GHS) algorithm that builds and maintains a minimum spanning tree. To do so, we divide D-GHS into four phases, namely neighbor discovery, tree construction, data collection, and tree maintenance. In the neighbor discovery phase, the nodes collect information about their neighbors and the link quality. In the tree construction, D-GHS finds the minimum spanning tree by executing the Gallager-Humblet-Spira algorithm. In the data collection phase, the sink roots the minimum spanning tree at itself, and each node sends data packets. In the tree maintenance phase, the nodes repair the tree when communication failures occur. The emulation results show that D-GHS reduces the number of control messages and the energy consumption, at the cost of a slight increase in memory sizeThe problem of constructing and maintaining a tree topology in a distributed manner is a challenging task in WSNs. This is because the nodes have limited computational and memory resources and the network changes over time. We propose the Dynamic Gallager-Humblet-Spira (D-GHS) algorithm that builds and maintains a minimum spanning tree. To do so, we divide D-GHS into four phases, namely neighbor discovery, tree construction, data collection, and tree maintenance. In the neighbor discovery phase, the nodes collect information about their neighbors and the link quality. In the tree construction, D-GHS finds the minimum spanning tree by executing the Gallager-Humblet-Spira algorithm. In the data collection phase, the sink roots the minimum spanning tree at itself, and each node sends data packets. In the tree maintenance phase, the nodes repair the tree when communication failures occur. The emulation results show that D-GHS reduces the number of control messages and the energy consumption, at the cost of a slight increase in memory size and convergence time.…
Author details: | Sergio Diaz, Diego Mendez, Mario SchölzelORCiDGND |
---|---|
ISBN: | 978-1-5386-6820-7 |
Title of parent work (English): | 2018 IEEE Colombian Conference on Communications and Computing (COLCOM) |
Publisher: | IEEE |
Place of publishing: | New York |
Publication type: | Other |
Language: | English |
Date of first publication: | 2018/09/20 |
Publication year: | 2018 |
Release date: | 2022/03/04 |
Tag: | Minimum spanning tree; Tree maintenance |
Number of pages: | 6 |
Funding institution: | Pontificia Universidad Javeriana [5685]; German Research Foundation (Deutsche Forschungsgemeinschaft - DFG)German Research Foundation (DFG) [KR 3576/21-1]; Colombian Administrative Department of Science, Technology and Innovation (Colciencias) through the Fondo Nacional de Financiamiento para la Ciencia, la Tecnologia y la Innovacion Francisco Jose de CaldasDepartamento Administrativo de Ciencia, Tecnologia e Innovacion Colciencias [FP44842-090-2015] |
Organizational units: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer review: | Referiert |