Um algoritmo distribuído e adaptativo para diagnóstico de redes ad hoc móveis com base em informações geográficas

Abstract

Resumo: Algoritmos de diagnóstico de falhas em nível de sistema são comumente utilizados como uma estratégia de tolerância à falhas. Neles, a partir de uma série de testes, podese determinar quais unidades estão com falha e quais estão sem-falha. Os primeiros modelos de diagnóstico de falhas que surgiram eram do tipo centralizado. Nesses modelos, considera-se que uma unidade central é a única responsável por diagnosticar o estado de todas as unidades do sistema. Posteriormente, surgiram os modelos distribuídos, nos quais o diagnóstico é atribuído a algumas ou todas as unidades do sistema. Todos estes modelos foram desenvolvidos para redes estáticas e cabeadas, não sendo facilmente adaptáveis à ambientes móveis. A identificação de unidades com falha em uma rede Ad Hoc móvel é uma tarefa muito difícil. Nestas redes, as unidades se utilizam de comunicações sem _o e podem se mover livremente e de forma imprevisível. Nesse trabalho é apresentado o primeiro algoritmo distribuído e adaptativo para diagnóstico em nível de sistema baseado no modelo PMC para redes Ad Hoc, que não impõe restrições ao movimento dos nós durante todo o diagnóstico. Todos os nós podem testar, serem testados e diagnosticar os demais nós. Além disso, os nós podem ser classificados como falho, sem falha e suspeitos. Um nó é classificado como suspeito quando este deixa de responder a solicitação de teste por sair do raio de alcance das transmissões de radio do seu testador. Como a mobilidade dos nós implica em variação de distâncias entre os nós, testador e testado, as solicitações de testes e suas respostas nem sempre ocorrem de forma satisfatória. Para isso, o algoritmo utiliza-se de coordenadas geográficas para monitorar a mobilidade dos nós de forma que seja possível diferenciar falhas reais, de falhas ocorridas devido a mobilidade.

Abstract: System-level fault diagnosis algorithms are commonly used as a strategy for fault tolerance, in which, from a series of tests, it is possible to determine faulty units. The first fault diagnosis models were centralized, considering that a central unit is the only responsible for diagnose the status of all system units. Subsequently, there were distributed models, in which diagnosis is assigned to some or all units of the system. All these models were developed for static and wired networks, not being easily adaptable to mobile environments. The identification of faulty units in a mobile Ad Hoc network is a very dificult task because units can move freely and unpredictably. In this paper we present the first distributed algorithm for adaptive system-level diagnosis based on the PMC model for Ad Hoc networks, which imposes no restrictions on the movement of the units throughout the diagnosis. All nodes can test, be tested and diagnose other nodes. Furthermore, nodes can be classified as faulty, fault-free and suspect. A node is considered suspect when it moves away from the tester transmission range, thus not responding to tests anymore. As node mobility implies on distances variation between nodes, tester and tested, tests requests and their answers do not always occur in a satisfactory manner. Hence, geographic coordinates are considered by the algorithm in order to keep track of the nodes mobility, so that it is always possible to distinguish real faults from mobility-generated faults.