Construcción y mantenimiento dinámico del árbol de expansión mínima para redes inalámbricas de sensores
DOI:
https://doi.org/10.17533/udea.redin.20190508Palabras clave:
auto-organización, control de topología, auto-curaciónResumen
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.
Descargas
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
Cómo citar
Número
Sección
Licencia
Derechos de autor 2019 Revista Facultad de Ingeniería Universidad de Antioquia
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Los artículos disponibles en la Revista Facultad de Ingeniería, Universidad de Antioquia están bajo la licencia Creative Commons Attribution BY-NC-SA 4.0.
Eres libre de:
Compartir — copiar y redistribuir el material en cualquier medio o formato
Adaptar : remezclar, transformar y construir sobre el material.
Bajo los siguientes términos:
Reconocimiento : debe otorgar el crédito correspondiente , proporcionar un enlace a la licencia e indicar si se realizaron cambios . Puede hacerlo de cualquier manera razonable, pero no de ninguna manera que sugiera que el licenciante lo respalda a usted o su uso.
No comercial : no puede utilizar el material con fines comerciales .
Compartir igual : si remezcla, transforma o construye a partir del material, debe distribuir sus contribuciones bajo la misma licencia que el original.
El material publicado por la revista puede ser distribuido, copiado y exhibido por terceros si se dan los respectivos créditos a la revista, sin ningún costo. No se puede obtener ningún beneficio comercial y las obras derivadas tienen que estar bajo los mismos términos de licencia que el trabajo original.
Twitter