Utilize este identificador para referenciar este registo: http://hdl.handle.net/10451/9830
Título: Algoritmo genético para o problema de localização de sensores
Autor: Carvalho, Ana Sofia Fonseca de
Orientador: Captivo, Maria Eugénia
Rodrigues, António José
Palavras-chave: Rede de sensores
Proteção de Portos
Localização contínua
Admissibilidade
Linha de visão
Heurística
Chaves aleatórias
Teses de mestrado - 2013
Data de Defesa: 2013
Resumo: Ao longo dos anos, os problemas de redes de sensores têm-se estendido, progressivamente, a diversas áreas de aplicação. Nesta dissertação propõe-se estudar o problema de localização de sensores no âmbito da proteção de portos face a eventuais ataques terroristas numa área de interesse contínua. Mais especificamente, o principal objetivo é encontrar a melhor configuração de recursos, ou seja, o número e tipo de sensores a instalar, que maximize a proporção total de área coberta e, consequentemente, minimize o risco de uma ameaça não ser detetada - problema mono-objetivo. Posteriormente, inclui-se também na análise do problema a minimização dos custos totais que incluem custos fixos e custos de localização - problema biobjetivo. A abordagem ao problema considera a introdução de obstáculos na área de interesse. Assim, para além do caso mais simples em que a área de interesse corresponde apenas à região marítima, a existência de obstáculos introduz dois casos de estudo: analisa-se a questão da admissibilidade das soluções mediante as restrições de localização para cada tipo de sensor e estuda-se o problema da linha de visão. Para os três casos em estudo foram obtidas soluções através da aplicação do biased random-key genetic algorithm, uma heurística baseada em algoritmos genéticos onde a codificação de cada solução é feita através de chaves aleatórias. Adotando algumas simplificações, foram testados vários parâmetros de forma a obter os melhores resultados. O problema mono-objetivo, considerando a área de interesse mais simples, permitiu analisar a qualidade da heurística. Posteriormente, foram realizados testes para os restantes casos de estudo e para o problema biobjetivo. Os resultados obtidos permitiram concluir que esta metodologia é eficaz para o problema em estudo, esperando-se que, futuramente, possa ser aplicada a casos reais, através de algumas adaptações e desenvolvimentos que se sugerem.
Over the years, sensor network issues have been considered for a wide range of applications. In this dissertation, the study of the problem of locating sensors in order to protect ports in a continuous area of interest is proposed. The main goal is to find the best configuration of resources, concerning the number and type of sensors to install so that the total proportion of covered area is maximized. Therefore, the risk of not detecting a threat is minimized - a mono-objective problem. Besides, it is also considered in the analysis of the problem the minimization of total costs which includes fixed costs and costs dependent on location - a bi-objective problem. The effect of incorporating obstacles in the area of interest is studied. While the simplest case considers that the area of interest corresponds only to the maritime area, the existence of obstacles leads to two study cases: the feasibility of solutions is analysed by the location constraints for each type of sensor and the line of sight problem is also considered. Solutions to all three study cases have been obtained through a biased randomkey genetic algorithm which codifies each solution by random numbers. Taking into account some simplifications, different parameters have been tested in order to get the best results. The mono-objective problem considering the simplest area of interest allows the analysis of the heuristic's quality. Various tests were performed considering the remaining study cases and the bi-objective problem. The results obtained allow us to conclude that this is an effective methodology to the problem studied. In the future, we expect that it can be applied to real cases through some adaptations and developments that are suggested.
Descrição: Tese de mestrado em Estatística e Investigação Operacional, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2013
URI: http://hdl.handle.net/10451/9830
Aparece nas colecções:FC - Dissertações de Mestrado

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ulfc105754_tm_Ana_Sofia_Carvalho.pdf2,32 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.