Construcción y mantenimiento dinámico del árbol de expansión mínima para redes inalámbricas de sensores

Autores/as

DOI:

https://doi.org/10.17533/udea.redin.20190508

Palabras clave:

auto-organización, control de topología, auto-curación

Resumen

En una red inalámbrica de sensores (WSN por su sigla en inglés), encontrar la ruta óptima desde cada nodo al sumidero no es una tarea sencilla debido a las características distribuidas y dinámicas de la red. Por ejemplo, la red sufre cambios frecuentes porque la calidad del canal varía con el tiempo y los nodos pueden abandonar o unirse a la red en cualquier instante. Con el objetivo de controlar esta variabilidad, proponemos el algoritmo dinámico Gallager-Humblet-Spira (DGHS) que construye y mantiene un árbol de expansión mínima para redes dinámicas y distribuidas, y hemos encontrado que DGHS reduce el número de mensajes de control y el consumo de energía, a costa de un ligero aumento en el tamaño de la memoria y el tiempo de convergencia. Este artículo presenta una descripción detallada de las diferentes etapa del algoritmo DGHS (descubrimiento de vecinos, construcción del árbol y recopilación de datos), un análisis profundo de un conjunto extenso de resultados que validan nuestra propuesta, y una descripción exhaustiva de las limitaciones que tiene GHS.

|Resumen
= 286 veces | PDF (ENGLISH)
= 213 veces|

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

Sergio Diaz, Pontificia Universidad Javeriana

Departamento de Ingeniería Electrónica.

Diego Mendez, Pontificia Universidad Javeriana

Departamento de Ingeniería Electrónica.

Citas

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.

Descargas

Publicado

2019-08-23

Cómo citar

Diaz, S., & Mendez, D. (2019). Construcción y mantenimiento dinámico del árbol de expansión mínima para redes inalámbricas de sensores. Revista Facultad De Ingeniería Universidad De Antioquia, (93), 57–69. https://doi.org/10.17533/udea.redin.20190508