Heurísticas mono e multiobjetivo para o problema de cobertura e conectividade de redes de sensores sem fio planas

AUTOR(ES)

Flavio Vinicius Cruzeiro Martins

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

05/08/2009

RESUMO

Este trabalho aborda o Problema de Cobertura e Conectividade em Redes de Sensores sem Fio (RSSF), formulando-o de diferentes maneiras como problemas de otimização mono-objetivo e multiobjetivo. Em todos os casos, é considerada a questão da reconfiguração dinâmica da rede realizada `a medida em que ocorram falhas na rede devidas ao esgotamento da energia dos nos sensores. No caso da formulação mono-objetivo, a heurística proposta se baseia em um Algoritmo Genético (AG) para fazer a escolha inicial dos nos a serem ativados e para atualizar essa escolha em alguns momentos, quando a rede se afasta significativamente de uma configuração ótima. Essa heurística envolve ainda uma busca gulosa para realizar reconfiguração locais de forma rápida imediatamente apos a ocorrência de cada falha. Tal heurística é comparada com uma formulação exata do mesmo problema, tratada por meio de Programação Linear Inteira, a qual foi resolvida utilizando um pacote comercial de otimização. Embora, conforme esperado, a heurística proposta não tenha sido capaz de determinar as soluções ótimas exatas para o problema, verificou-se que os ganhos de tempo de execução obtidos com a heurística tornam plausível sua aplicação em problemas práticos mesmo em situações envolvendo um grande numero de nos sensores. No que diz respeito a desenvolvimentos realizados especificamente no ambito desta dissertação, esta parte do trabalho apresenta alguns aperfeiçoamentos sobre algoritmos que já tinham sendo construídos anteriormente, com a participação deste autor. A principal contribuição desta dissertação é a proposição de uma formulação multiobjetivo para o problema de cobertura e conectividade de RSSF, associada a uma correspondente heurística para sua solução. O princípio em que se fundamenta tal formulação ´e o de que é possível realizar uma troca entre o tempo de funcionamento da rede e o percentual da área coberta. Um Algoritmo Genético multiobjetivo, baseado no NSGA (Non-dominated Sorting Genetic Algorithm), foi desenvolvido para substituir o AG monoobjetivo, de forma a determinar, em paralelo, um conjunto de soluções não-dominadas em relação a tais objetivos. Um algoritmo simples de tomada de decisão é empregado de maneira a escolher a configuração a ser adotada pela rede a cada instante. Resultados de simulação mostram que a introdução de pequenas relaxações na área coberta permitem obter significativos aumentos no tempo de funcionamento da rede. O tempo de execução da heurística multiobjetivo proposta é similar ao da heurística mono-objetivo para redes de mesmo tamanho.

ASSUNTO(S)

engenharia elétrica teses.

Documentos Relacionados

• Planejamento dinâmico para controle de cobertura e conectividade em redes de sensores sem fio planas
• Algoritmo para o problema de atribuição de papéis em redes de sensores sem fio
• Heurísticas e algoritmos evolutivos para formulações mono e multiobjetivo do problema do roteamento multicast
• Middleware seguro para redes de sensores sem fio
• Arquiteturas Cross-layer para Redes de Sensores sem Fio