Graph-Theoretic and Computational Geometry Approaches for the Management of Sensor Networks in Process Monitoring

Abstract

Este artículo integra métodos de teoría de grafos y geometría computacional para modelar el despliegue de sensores como grafos de Delaunay ponderados, capturando la proximidad espacial y los costes de comunicación. Se proponen diversas estrategias para abordar problemas comunes relacionados con la gestión de redes de sensores, incluyendo la gestión de baterías, la reconfiguración de topologías de comunicación de red, la recolección eficiente de datos, etc. En particular, se presentan seis métodos algorítmicos que combinan: Árboles de expansión mínima (MST), Cálculo de rutas más cortas, Contracción de aristas, Etiquetado de grafos, Segmentación mediante diagramas de Voronoi, Triangulación de Delaunay. Estos métodos cuentan con el respaldo teórico de resultados novedosos sobre la hamiltonicidad y las propiedades cromáticas de los grafos de Delaunay, garantizando rutas de recorrido completas. El rendimiento y la escalabilidad del marco de trabajo se demuestran con una implementación real —la monitorización de un campo de caña de azúcar—, donde se evalúan el desempeño y los requisitos computacionales de los métodos propuestos.