Metaheurísticas multiobjetivo para la resolución del problema del posicionamiento de nodos repetidores en redes de sensores inalámbricos

Abstract

Una Red de Sensores Inalámbricos (WSN) se compone de un conjunto de sensores, que capturan información sobre el entorno, y un nodo central, que recolecta toda la información proporcionada por la red. Estas redes son sensibles al consumo energético, sobre todo al considerar protocolos de enrutado multi-salto, donde todos los dispositivos pueden comunicarse entre sí. Recientemente, un nuevo dispositivo especializado en tareas de comunicación y denominado Nodo Repetidor (RN), fue añadido a las WSNs tradicionales como una posible vía de abordar esta cuestión, dando lugar al Problema del Posicionamiento de Nodos Repetidores (RNPP), que es un problema de optimización NP-completo. En esta tesis abordamos tres diferentes versiones del RNPP, divididas en torno a dos grupos: WSNs exteriores y WSNs interiores. En la primera versión estudiamos cómo desplegar RNs en WSNs exteriores estáticas previamente establecidas, con el objetivo de optimizar el consumo energético medio y la cobertura media. La segunda versión aporta un enfoque más realista sobre la primera, donde además optimizamos la robustez de la red. Ambas versiones se resuelven mediante múltiples metaheurísticas multiobjetivo: NSGA-II, SPEA2, MO-VNS, MO-ABC, MO-FA, MO-GSA y MOEA/D. En la tercera versión y basándonos en el conocimiento adquirido, proponemos una novedosa línea de investigación: el despliegue de WSNs interiores estáticas de bajo coste, tratando de aprovechar la infraestructura existente. Este nuevo problema de optimización se deriva de la necesidad de desplegar redes interiores de bajo coste para proporcionar servicios de localización, ej. para robótica doméstica y del hogar.

A Wireless Sensor Network (WSN) is composed of a set of sensors, capturing information about the environment, and a sink node, which collects all the information provided by the network. WSNs are particularly sensitive to energy cost, especially with multi-hop routing protocols, where the devices send data to each other’s. In recent years, a new device specialised in communication tasks and called Relay Node (RN) is added to traditional WSNs as a possible way to address this issue, resulting in the NP-hard optimisation Relay Node Placement Problem (RNPP). In this thesis, we tackle three different approaches of the RNPP, divided into two groups: outdoor and indoor networks. In the first approach, we study how to efficiently deploy energy-harvesting RNs in previously-established static outdoor WSNs for optimising average energy consumption and average coverage. The second approach is a more realistic version of the previous deployment problem, where we also optimise network reliability. Both approaches are solved by applying a wide range of Multi-Objective (MO) metaheuristics. Specifically, we implement NSGA-II, SPEA2, MO-VNS, MO-ABC, MOFA, MO-GSA, and MOEA/D algorithms. In the third approach and based on the knowledge obtained from the outdoor problem, we propose a new line of research not considered before in the literature: the deployment of low-cost static indoor WSNs, trying to leverage existing infrastructure. This new MO problem derives from the need to deploy low-cost networks for providing indoor localisation services, e.g. for domestic and industrial robots.