Algoritmo para localização em redes de sensores sem fio
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Ricardo Martins de Abreu Silva
Jose Marcos Silva Nogueira
Alexandre Salles da Cunha
Luiz Filipe Menezes Vieira
Jose Marcos Silva Nogueira
Alexandre Salles da Cunha
Luiz Filipe Menezes Vieira
Resumo
O conhecimento da localização geográfica dos nós sensores nas Redes de Sensores Sem Fio é uma característica essencial, pois a informação coletada por um nó da rede só é realmente significativa se for conhecida a localização do mesmo. O problema de Localização em Redes de Sensores Sem Fio consiste em encontrar a posição para os nós sensores de uma rede sem a necessidade de instalar qualquer infraestrutura, como GPSs por exemplo, para todos eles. Dentre as diversas abordagens existentes, o presente trabalho trata do problema baseando-se na existência de âncoras (alguns nós da rede que possuem posição correta conhecida) e nas estimativas de distância entre os demais nós da rede e entre esses nós e os âncoras. O problema é NP-Difícil, o que mostra a viabilidade de se utilizar uma heurística para o mesmo.O presente trabalho propõe uma heurística específica para o problema, utilizando-se abordagem centralizada e baseada nos métodosde trilateração e interseção entre dois círculos. A forma de controle do uso desses métodos através do processo de escolhados nós de referência, da ordem de escolha dos nós, e do controle de tolerância de erros permitem que se encontre soluçõesmelhores do que geralmente são encontradas por algoritmos baseados nesses métodos. Foram realizados experimentos comparandoo algoritmo proposto com os algoritmos publicados por outros quatro autores. Foram analisados diversos conjuntos de instâncias, variando-se o tamanho da rede, a quantidade de nós âncoras, o alcance de rádio e o fator de ruído. Os experimentos realizados mostram que o algoritmo proposto é competitivo, alcançando melhores resultados em várias das instâncias testadas, inclusive na presença de ruído.
Abstract
The knowledge of the geographical location of sensor nodes in Wireless Sensor Networks is an essential feature, because the information collected by a node is only significant if we know the node's location. The Wireless Sensor Network Localization Problem is defined as determine the location off all sensor nodes in a network without need the use infrastructure, such as GPSs, for them. Among the various existing approaches to the problem, this work addresses the problem based on the existence of anchors (some network nodes that know their positions) and estimates distance between the other nodes of the network and among these nodes and anchors. The problem is NP-Hard, therefore we designed a heuristic for it.This thesis proposes a specific heuristic to the problem, using a centralized approach based on trilaterations and intersections between two circles. The control of these methods through the process of choosing reference nodes, the order of choice for the reference nodes, and the fault tolerance control make it possible to find solutions better than are usually found by algorithms based on these methods. Experiments carried out compared the proposed algorithm with other four algorithms. We analyzed several sets of instances by varying the network size, the number of anchor nodes, the radio range and the noise factor. The results show that the proposed algorithm is competitive, achieving the best results in several of the instances tested, evenwhen noise is considered.
Assunto
Computação
Palavras-chave
Ciência da Computação