Maximización de la Vida Útil en Redes de Sensores Inalámbricos con Rangos de Sensibilidad Ajustables mediante Generación de Columnas

Published in: Engineering Innovations for Global Sustainability: Proceedings of the 14th Latin American and Caribbean Conference for Engineering and Technology
Date of Conference: July 20-22, 2016
Location of Conference: San Jose, Costa Rica
Authors: Fabián Castaño
Nubia Velasco
André Rossi
Marc Sevaux
Refereed Paper: #295

Abstract:

En este trabajo se explora el problema de maximizar la vida útil de una red de sensores inalámbricos contando con sensores capaces de ajustar sus rangos de sensibilidad, modificando así su consumo energético. Este tipo de redes son usadas para monitorear objetos localizados en posiciones fijas. Además, se consideran restricciones sobre la conectividad de la red, en la cual los sensores que captan alguna señal deben ser capaces de transmitir la información a un usuario final mediante comunicaciones inalámbricas multi-hop. Se propone un esquema híbrido de solución basado en generación de columnas que aprovecha la representación casi natural del problema mediante un modelo lineal construido sobre un número exponencial de variables. El método propuesto divide el problema entre un problema auxiliar y un problema maestro. El primero se encarga de determinar los rangos de sensibilidad asignados a cada sensor en subgrupos satisfaciendo requerimientos de conectividad. Por su lado, el problema maestro determina el tiempo total que un subgrupo dado de sensores, representado además en las columnas del modelo lineal, debe operar con el fin de maximizar la vida de la red. Para resolver el problema auxiliar, se propone un nuevo modelo de programación entero basado en conjunto exponencial de cortes que, correctamente implementado, permite identificar nuevas columnas rápidamente mediante la aplicación de un enfoque Branch & Cut. El enfoque propuesto es evaluado en un conjunto de instancias de tamaño mediano con hasta 300 sensores y 180 objetivos. Los resultados preliminares indican la eficacia del método propuesto y sugieren también nuevas posibilidades para su aplicación a redes de sensores con tecnologías similares.