COMPARAÇÃO ENTRE MÉTODOS EXATO E HEURÍSTICO PARA O PROBLEMA DE ALOCAÇÃO DE SENSORES EM REDES DE SENSORES SEM FIO

Abstract

Wireless Sensor Networks (WSNs) are increasingly present in society, whether in homes, cars, factories or in support for rescue and environmental preservation. Several optimization methods have been proposed in the literature to allocating the sensor nodes in order to improve the network performance, considering one or more objectives. However, most studies on this subject are carried out with heuristic methods, which do not guarantee optimality. Exact approaches, on the other hand, generally do not solve large instances due to the complexity involved in finding the optimal solution. In this research, two approaches to solve the Sensor Allocation Problem (SAP) are compared in order to minimize the overall energy cost of the network: the first is an exact method using Mixed Integer Linear Programming (MILP), through mathematical formulation proposed, and the second is a proposed heuristic method based on the concepts of Genetic Algorithms (GAs). The results show that the exact approach achieved optimal results for PAS considering small, medium and large instances. In turn, the GA generated suboptimal results for almost twice as many instances as the exact approach, in the same period of time. Instances of regular and non-regular formats were used.Redes de Sensores Sem Fio (RSSFs) estão cada vez mais presentes na sociedade, sejam em casas, carros, fábricas ou em apoio a resgates e preservação ambiental. Vários métodos de otimização são propostos na literatura a fim de alocar os nós sensores de forma a melhorar o desempenho da rede, considerando um ou mais objetivos. Contudo, grande parte dos estudos neste tema são realizados com métodos heurísticos, os quais não possuem garantia de otimalidade. Já abordagens exatas, devido à complexidade envolvida na garantia da solução ótima, geralmente não resolvem instância de grande porte. Nesta pesquisa, são comparadas duas abordagens de solução para o Problema de Alocação de Sensores (PAS) com objetivo de minimizar o custo energético geral da rede: a primeira e um método exato usando Programação Linear Inteira Mista (PLIM), através de formulação matemática proposta, e a segunda um método heurístico proposto baseado nos conceitos de Algoritmos Genéticos (AGs). Os resultados obtidos mostraram que a abordagem exata alcançou resultados ótimos para o PAS considerando instâncias de pequeno, médio e grande portes. Por sua vez, o AG gerou resultados subotimos para quase o dobro de instancias que a abordagem exata, no mesmo período de tempo. Foram utilizadas instancias de formatos regular e não regulares.