Métodos para redução integrada do consumo de energia e do atraso na entrega de dados em Redes de Sensores Sem Fio

Abstract

Um dos principais desafios de tais redes reside nos recursos energéticos limitados disponíveis para nós sensores, uma vez que os sensores são geralmente implantados em ambientes de difícil acesso e em grandes quantidades tornando complicado, ou mesmo impossível, substituir ou recarregar as baterias. Uma possível solução para economizar energia é permitir que um agente móvel percorra a RSSF coletando os dados, mas esta abordagem aumenta o atraso na entrega dos dados. Neste trabalho é usada uma floresta de comunicação, onde as raízes (cluster heads) das árvores são os nós sensores visitados pelo agente móvel; os outros sensores enviam seus dados para os cluster heads usando um ou mais saltos. Permitir saltos pode diminuir a qualidade de serviço da rede e aumentar o número de falhas, por isso limita-se o número de saltos a um inteiro H. Para controlar o atraso na entrega dos dados, o tempo da trajetória do agente móvel é limitado. Então, o problema é definir os cluster heads, a floresta de comunicação com H saltos e a trajetória restrita do agente móvel, minimizando a energia consumida total. É apresentado um modelo de Programação Linear Inteira Mista (PLIM) para o problema definido como Problema Integrado de Agrupamento e Roteamento com Restrição de Salto e Tempo (PARST). Como o PLIM se mostrou computacionalmente difícil de se resolver, são propostos métodos híbridos (Algoritmo Genético e GRASP) que definem o conjunto de cluster heads usando heurísticas especiais para construir e avaliar as soluções. Uma formulação baseada em geração de colunas também é proposta com o objetivo de aumentar o tempo de vida útil da rede. Resultados são apresentados para a RSSF com até 100 nós sensores usando diferentes limites para o tempo de percurso do agente móvel. A otimalidade das soluções para algumas instâncias com 20 e 30 nós foi confirmada através da resolução da formulação exata do modelo PLIM proposto.

One of the main challenges in such networks lies in the constrained energy resources available to sensor nodes. Since the sensors are usually deployed in hostile environments and in large quantities, it is difficult or impossible to replace or recharge their batteries. A possible solution to save energy is to allow a mobile agent to move through the WSN to collect the data, but this approach increases the delay delivery of messages. In this work a communication forest is used, where the roots (cluster heads) of the trees are the sensors visited by the mobile agent; the other sensors send their information to the cluster heads using one or more hops. Allowing hops can decrease the quality of network service and increase the number of failures, so the number of hops is limited in H. To control the delay data delivery, the time of the mobile agent trajectory is limited. Then, the problem is to define the cluster heads, the communication forest within H hops and the constrained mobile agent path in order to minimize the total energy consumption. It is presented a Mixed-Integer Linear Programming (MILP) formulation for the problem defined as Integrated Problem of Clustering and Routing with Hop and Time Constrained (PCRHT). As the MILP showed up computationally hard to solve, hybrid methods (Genetic Algorithm and GRASP) are proposed. These methods define the set of cluster heads using specialized heuristics to build and evaluate the solutions. A formulation based on column generation is also proposed with the aim of increasing the lifetime of the network. Results are presented for WSN with up to 100 nodes sensors using different limits for the travel time of the mobile agent. The optimality of the solutions for some instances with 20 and 30 nodes were confirmed by solving the MILP formulation.