Qualificação de doutorado da discente Josiane Rezende, dia 13/12/18, na Sala de Multimídia do ICEB.

Qualificação de doutorado da discente Josiane Rezende, dia 13/12/18, as 15 horas, na Sala de Multimídia do ICEB.

Título: Algoritmos para Programas Lineares Binários Genéricos e Redes de Sensores Sem Fio com Coletores Móveis

Orientador: Marcone Jamilson Freitas Souza
Banca Examinadora: Prof. Dr. Vitor Nazário Coelho - UFF;  Prof. Dr. Puca Huachi Vaz Penna - UFOP; Prof. Dr. Túlio Ângelo Machado Toffolo – UFOP

Data: 13/12/18 Horário: 15hs

Resumo

Este trabalho apresenta dois problemas de pesquisa. O primeiro busca resolver problemas lineares binários genéricos. Para isto é desenvolvido um algoritmo Multi-Start que combina técnicas exatas e heurísticas, tais como Variable Neighborhood Descent -- VND, propagação de restrições, e cortes Local branching. O método proposto, nomeado eHMS, apresenta duas fases que interagem entre si até que o tempo limite seja atingido. A primeira fase visa a construção de uma solução inicial; a segunda, por sua vez, visa ao refinamento dessa solução construída. Na fase de construção, é utilizado o resolvedor CBC e um procedimento de propagação de restrições, de forma a gerar uma solução inicial para o problema. O resolvedor CBC relaxa as variáveis binárias, isto é, atribui o valor de cada variável ao intervalo real [0, 1]. O procedimento propagação de restrições possui a finalidade de verificar se existe solução viável ao se fixar o valor de uma determinada variável binária. Se esta solução existir, ele poderá retornar, ainda, um conjunto de possíveis fixações nos valores das demais variáveis. Na fase de refinamento são utilizados cortes Local branching controlados pelo procedimento VND até que um tempo previamente definido seja atingido. Os cortes Local branching utilizam um resolvedor de programação linear inteira como uma ferramenta caixa-preta para explorar eficientemente subespaços das soluções do problema. O método desenvolvido foi aplicado a um conjunto de problemas binários da biblioteca MIPLIB 2010 com o intuito de verificar sua capacidade de obter soluções viáveis de qualidade variando-se o tempo de processamento. Os experimentos computacionais realizados mostraram que, quando o tempo de processamento aumenta, o método consegue aumentar tanto o número de soluções viáveis quanto a qualidade delas. Além disso, o método desenvolvido se mostrou superior a outros métodos da literatura, bem como a dois outros resolvedores de código aberto nesses dois indicadores de avaliação. No segundo problema de pesquisa referido neste trabalho, tem-se por objetivo aumentar o tempo de vida e diminuir o tempo de coleta de dados de Redes de Sensores Sem Fio (RFFS) que utilizam drones como coletores móveis. Tradicionalmente, os dados coletados por uma RSSF são enviados por rotas de múltiplos saltos para um nó especial, denominado estação base ou sorvedouro (sink). Entretanto, os nós sensores nas proximidades do sorvedouro tendem a consumir mais energia que os demais, devido à sua função de retransmissão dos pacotes de dados vindos de nós em regiões mais distantes da rede. Isso leva à morte prematura desses nós e a consequente desconexão da RSSF. A literatura apresenta vários trabalhos que estudam a utilização de coletores móveis (sorvedouros móveis ou mulas de dados) para distribuir o consumo de energia entre os nós da rede e reduzir o tamanho (em saltos) das rotas de dados, o que reduz o consumo de energia. Entretanto, em praticamente todos os trabalhos analisados, o coletor móvel não possui restrições, como tempo de viagem e trajetória a ser seguida. Ademais, em tais trabalhos a quantidade de dados a ser transmitida por cada nó sensor é pequena. Isso possibilita a utilização de um coletor móvel que não precisa parar para coletar os dados, basta passar na proximidade de cada nó.
Neste trabalho é considerado como coletor móvel um quadricóptero drone com capacidade de pairar para realizar a coleta de dados em qualquer ponto da área monitorada pela RSSF. Considera-se, também, RSSFs que possuem nós com muitos dados a serem transmitidos, de forma que a simples passagem do drone não fornece tempo suficiente para a transmissão de todos os dados. Os drones, no entanto, têm uma fonte de energia limitada que restringe seu tempo de voo. Portanto, além do consumo de energia da RSSF, o consumo de energia do drone em si também deve ser considerado para aumentar a quantidade de dados coletados. Objetiva-se investigar o problema de determinar a melhor trajetória para o drone realizar a coleta de dados e propor novos algoritmos que considerem a energia restante no drone e em cada nó sensor para prolongar o tempo de vida da rede e reduzir o tempo de coleta de dados. Tais algoritmos se encontram em fase de estudo e implementação.