ALGORITMOS PARA RASTREAMENTO DE ALVOS EM ÁREAS QUANTIZADAS COM REDES DE SENSORES SEM FIO ÉFREN LOPES DE SOUZA ALGORITMOS PARA RASTREAMENTO DE ALVOS EM ÁREAS QUANTIZADAS COM REDES DE SENSORES SEM FIO Tese apresentada ao Programa de Pós- -Graduação em Informática do Instituto de Computação da Universidade Federal do Amazonascomo requisito parcialparaaob- tenção do grau de Doutor em Informática. Orientador: Eduardo Freire Nakamura Manaus Março de 2014 (cid:13)c 2014, Éfren Lopes de Souza. Todos os direitos reservados. Lopes de Souza, Éfren D1234p Algoritmos para Rastreamento de Alvos em Áreas Quantizadas com Redes de Sensores Sem Fio / Éfren Lopes de Souza. — Manaus, 2014 xix, 185 f. : il. ; 29cm Tese (doutorado) — Universidade Federal do Amazonas Orientador: Eduardo Freire Nakamura 1. Rastreamento de Alvos. 2. Algoritmos Distribuídos. 3. Agrupamento. 4. Previsão. 5. Estrutura de Faces. 6. Algoritmos de Localização. I. Título. CDU 519.6*82.10 [Folha de Aprovação] Quando a secretaria do Curso fornecer esta folha, ela deve ser digitalizada e armazenada no disco em formato gráfico. Se você estiver usando o pdflatex, armazene o arquivo preferencialmente em formato PNG (o formato JPEG é pior neste caso). Se você estiver usando o latex (não o pdflatex), terá que converter o arquivo gráfico para o formato EPS. Em seguida, acrescente a opção approval={nome do arquivo} ao comando \ppgccufmg. Se a imagem da folha de aprovação precisar ser ajustada, use: approval=[ajuste][escala]{nome do arquivo} onde ajuste é uma distância para deslocar a imagem para baixo e escala é um fator de escala para a imagem. Por exemplo: approval=[-2cm][0.9]{nome do arquivo} desloca a imagem 2cm para cima e a escala em 90%. Agradecimentos Agradeço aos meus pais, irmãos, amigos e professores. Este trabalho contou com o apoio da Superintendência da Zona Franca de Ma- naus (SUFRAMA) e da Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES). v Resumo Rastreamento de alvos em Redes de Sensores Sem Fio (RSSFs) é um tipo de aplicação em que os nós cooperam para estimar a posição de um ou mais objetos de interesse. Nesse contexto, este trabalho possui quatro contribuições. A primeira contribuição é um levantamento bibliográfico do estado-da-arte, em que identificamos três diferentes formulações de rastreamento e as classificamos de acordo com suas características. Além disso, dividimos o processo de rastreamento em componentes para facilitar o entendimento geral. A segunda contribuição é a elaboração e avaliação do algoritmo PRATIQUE para rastrear animais em florestas. Nesse caso, os nós são organizados em grade para viabilizar a utilização dos nós sensores nesse tipo de área, de forma que cada célula da grade é uma região que pode ser ocupada pelo alvo. O algoritmo estima a célula em que o alvo está, e usa previsão e um esquema híbrido de agrupamento para reduzir o custo de comunicação e garantir a precisão do rastreamento. Os resultados das simulações mostram que os erros de previsão são de aproximadamente uma célula. A terceira contribuição é o algoritmo TATI, esse algoritmo guia um objeto que visa alcançar o alvo. Arede é estruturada em faces para facilitar a cooperação entre osnós e reduzirocaminhoentreoobjetoguiadoeoalvo. Osresultadosmostramqueoconsumo de energia é reduzido em 15% e o objeto guiado fica cerca de 10m mais próximo do alvo, secomparadocomaabordagemrelacionada. Aquartacontribuiçãoéumesquema para executar as tarefas de localização e rastreamento simultaneamente para reduzir os erros dos algoritmos de localização baseados em alcance. As mensagens enviadas para rastrear o alvo são aproveitadas para filtrar os ruídos presentes nas estimativas de distância, reduzindo o erro de localização enquanto o rastreamento ocorre. Os resultados mostram que os erros de localização podem ser reduzidos em até 70%. Palavras-chave: Rastreamento de Alvos, Algoritmos Distribuídos, Agrupamento, Previsão, Estrutura de Faces, Algoritmos de Localização. vi Abstract Target tracking in Wireless Sensor Networks (WSNs) is an application in which the nodes cooperate to estimate the position of one or more objects of interest. In this context, the contributions of this work are fourfold. First, a survey the state-of-the-art about target tracking algorithms, in which we identified three formulations of tracking problem, and we classified them according to their characteristics. Furthermore, we divided the target tracking process in components to make the general understanding easier. Second,weproposeandevaluatethePRATIQUEalgorithmfortrackinganimals in forests. In this case, the nodes are organized into a grid to make feasible the use of sensor nodes in this kind of area in such a way that each cell of the grid is a region that canbeoccupiedby thetarget. Thealgorithmestimates thecellwhere thetargetis, and uses predictions and hybrid clustering to reduce the communication cost and ensure the tracking accuracy. The results of the simulations show that prediction errors are approximately one cell. The third contribution is the TATI algorithm, this algorithm guides a tracker to approach the target. The sensor network is organized into faces to make the cooperation among the nodes easier, and reduce the path between the tracker and the target. The results show that energy consumption is reduced by 15%, and the tracker stays about 10m closer to the target, compared to the baseline. The fourth contribution is a scheme for performing localization and tracking tasks simultaneously in such a way that errors of range-based localization algorithms are reduced. This algorithm takes advantage of the messages sent to track the target to filter the noise in the distance estimation, reducing localization errors while tracking. The results show that the localization errors can be reduced by up to 70%. Keywords: Target Tracking, Distributed Algorithms, Clustering, Prediction, Face Structure, Localization Algorithms. vii Lista de Figuras 2.1 Formulações do problema de rastreamento. . . . . . . . . . . . . . . . . . . 15 2.2 Componentes dos algoritmos de rastreamento. . . . . . . . . . . . . . . . . 18 2.3 Técnicas para estimar a posição do alvo. . . . . . . . . . . . . . . . . . . . 26 2.4 Representação do filtro de Kalman e suas fases. . . . . . . . . . . . . . . . 28 2.5 Requisitos das aplicações de rastreamento. . . . . . . . . . . . . . . . . . . 42 2.6 Mecanismo de poda do STUN. . . . . . . . . . . . . . . . . . . . . . . . . 54 2.7 Exemplo da construção de uma árvore usando DAB. . . . . . . . . . . . . 55 2.8 Exemplos de detecção e atualização de contorno do alvo contínuo com CODA 58 2.9 Rede organizada em faces . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.1 Rede organizada em grade. . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.2 Cálculo de posição simples. . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.3 Previsão de posição do alvo. . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.4 Influência do alcance do alvo. . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.5 Influência das falhas de detecção de eventos. . . . . . . . . . . . . . . . . . 81 3.6 Influência da interferência do ambiente. . . . . . . . . . . . . . . . . . . . . 82 3.7 Influência da imprecisão das estimativas de distância. . . . . . . . . . . . . 84 3.8 Influência da correlação de mobilidade do alvo. . . . . . . . . . . . . . . . 84 4.1 Configuração da rede antes do rastreamento iniciar. . . . . . . . . . . . . . 89 4.2 Três possibilidades de anúncio de borda. . . . . . . . . . . . . . . . . . . . 90 4.3 Organização do byte de agrupamentos participantes. . . . . . . . . . . . . 91 4.4 Encaminhamento dos dados quando o evento cobre apenas um agrupamento. 94 4.5 Encaminhamento dos dados quando o evento cobre mais de um agrupamento. 94 4.6 Formação de agrupamento dinâmico e fusão de todos os dados sobre um evento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.7 Previsão de posição com base no histórico de mobilidade do alvo. . . . . . 96 4.8 Sincronização de filtro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 viii 4.9 Impacto do alcance do alvo. . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.10 Impacto da detecção de eventos. . . . . . . . . . . . . . . . . . . . . . . . . 105 4.11 Impacto da quantidade de agrupamentos. . . . . . . . . . . . . . . . . . . . 108 4.12 Impacto da quantidade de alvos. . . . . . . . . . . . . . . . . . . . . . . . . 109 5.1 Diagrama de estados dos nós. . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.2 Visão geral do algoritmo de rastreamento e da estrutura de faces. . . . . . 116 5.3 Representação gráfica dos algoritmos de planarização. . . . . . . . . . . . . 119 5.4 Formação de faces usando buffer-circular ordenado. . . . . . . . . . . . . . 120 5.5 Ativação das faces durante o rastreamento. . . . . . . . . . . . . . . . . . . 123 5.6 Alvo sendo perdido pela rede no intervalo entre duas amostragens. . . . . . 124 5.7 Pontos de consulta calculados pela rede para reduzir o percurso do objeto guiado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.8 Atalho criado no caminho de beacons depois que o alvo passa por k = 6 faces.127 5.9 Removendo o laço de beacons formados pela trajetória do alvo. . . . . . . . 128 5.10 Avaliações variando a velocidade do alvo. . . . . . . . . . . . . . . . . . . . 130 5.11 Avaliações variando a diferença de velocidade entre o objeto guiado e o alvo.131 5.12 Avaliação de escalabilidade. . . . . . . . . . . . . . . . . . . . . . . . . . . 133 5.13 Avaliações aumentando o raio de comunicação dos nós. . . . . . . . . . . . 134 6.1 Fases da localização recursiva. . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.2 Localização direcionada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.3 Comunicação entre os módulos de rastreamento e localização. . . . . . . . 144 6.4 Distribuição dos erros de localização do RPE ao longo do tempo. . . . . . 148 6.5 O erro médio de localização é reduzido durante o rastreamento. . . . . . . 149 6.6 Distribuição dos erros de localização do DPE ao longo do tempo. . . . . . 150 6.7 Impacto das imprecisões das estimativas de distância na localização. . . . . 152 6.8 Impacto das imprecisões das estimativas de distância no rastreamento. . . 153 6.9 Impacto das imprecisões dos sensores na localização. . . . . . . . . . . . . 154 6.10 Impacto das imprecisões dos sensores no rastreamento. . . . . . . . . . . . 155 6.11 Impacto da escala da rede na localização. . . . . . . . . . . . . . . . . . . . 156 6.12 Impacto da escala da rede no rastreamento. . . . . . . . . . . . . . . . . . 156 6.13 Impacto da escala da rede na energia e mensagens. . . . . . . . . . . . . . 157 6.14 Impacto da quantidade de beacons na localização. . . . . . . . . . . . . . . 158 6.15 Impacto da quantidade de beacons no rastreamento. . . . . . . . . . . . . . 159 ix Lista de Tabelas 2.1 Elementos dos algoritmos de rastreamento de alvos. . . . . . . . . . . . . . 16 2.2 Resumo da classificação dos algoritmos de rastreamento. . . . . . . . . . . 48 3.1 Parâmetros de simulação usados nas avaliações do rastreamento quantizado. 76 3.2 Parâmetros de energia usados nas avaliações do rastreamento quantizado. . 78 4.1 Parâmetros de simulação usados nas avaliações do PRATIQUE. . . . . . . 99 4.2 Parâmetros de energia usados no PRATIQUE. . . . . . . . . . . . . . . . . 100 5.1 Elementos envolvidos no rastreamento. . . . . . . . . . . . . . . . . . . . . 115 5.2 Parâmetros de simulação usados nas avaliações do TATI. . . . . . . . . . . 128 5.3 Parâmetros de energia usados nas simulações do TATI. . . . . . . . . . . . 129 6.1 Parâmetros de simulação usados nas avaliações de localização e rastrea- mento simultâneos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.2 Parâmetros de energia usados nas simulações de localização e rastreamento simultâneos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.3 Oerromédio delocalizaçãoequantidade denóslivres sãoreduzidos durante o rastreamento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 x