Orientadora : Profª. Drª. Andréa Weber / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 27/08/2015 / Inclui referências : f. 75-81 / Resumo: Diagnóstico em nível de sistema e uma sub-área de tolerância a falhas. O objetivo de um algoritmo de diagnostico em nível de sistema e reportar, para todas as unidades sem-falha de um sistema distribuído, o estado das demais unidades do sistema. A di- agnosticabilidade do sistema depende de algumas propriedades topologicas do grafo de diagnostico. Nesse contexto, um assinalamento de testes e um conjunto de testes mótuos entre as n unidades de um sistema. Um sistema com n unidades e dito t-diagnosticavel se o numero de unidades falhas nao ultrapassar t e satisfizer as seguintes condicões: (i) n > 2t + 1; e (ii) cada unidade for testada por, no mínimo, t outras unidades. Um sistema t-diagnosticóvel e definido como ótimo se n = 2t + 1. Considera-se o problema da definicao de um assinalamento de testes para a identificaçao de nós com falha em uma Rede de Sensores Sem Fio - RSSF. Dado um conjunto de 2t +1 sensores, a abordagem Optimal Design Testing Assignment - ODTA [36] gera um assinalamento de testes ótimo do ponto de vista da diagnosticabilidade do sistema. Entretanto, o problema da escolha em termos da distancia dos 2t +1 sensores que farao parte do assinalamento de testes tem características de um problema computacionalmente intratavel. Devido a ausencia de tal prova, apresenta-se o aprimoramento da heurística do ODTA para a escolha deste conjunto de sensores. Por meio da heurística Set of Sensors Chosen by Centroid and Radius - SSCCR apresentada, e possível selecionar em tempo polinomial tal conjunto nao somente otimo em termos de número de sensores, mas com uma considerável melhora dos resultados em termos de distancia geográfica entre os sensores. Por fim, apresenta-se a comparacõo das duas heurísticas abordadas com a solucõo ítima obtida pela formulacao do problema em programacao linear inteira, na qual pode-se confirmar que a heurística SSCCR apresenta melhor desempenho em relacao a heurística ODTA na escolha do conjunto de sensores com relacao a distancia entre eles e ate mesmo, em algumas situacoes, pode proporcionar o alcance de valores íotimos e consequentemente obter a reduçcõao do consumo de energia na execucao do diagnostico de falhas. / Abstract: System-level diagnosis is a subset of fault tolerance. The goal of a system-level diagnosis algorithm is to report the state of the units of a distributed system to all fault-free units of the system. The diagnosability of the system depends on some topological properties of the diagnostic graph. In this context, a test assignment is a set of mutual tests between n units of a system. A system with n units is called t-diagnosable if the number of faulty units does not exceed t and it satisfies the following conditions: (i) n > 2t +1; and (ii) each unit is tested at least by t other units. A t-diagnosable system is said to be optimal if n = 2t +1. Consider the problem of defining a test assignment to identify faults in a wireless sensor network (WSN). Given a set of 2t +1 sensors, the approach Optimal Design Testing Assignment - ODTA [36] generates an optimal test assignment for the diagnosability of the system. However, the problem of the choice of 2t + 1 sensors that will take part of the testing assignment has characteristics of a computationally intractable problem. Due to the absence of such proof, the improvement of ODTA heuristics is presented. According to the heuristic Set of Sensors Chosen by Centroid and Radius - SSCCR it is possible to select that set in polynomial time, optimal not only in terms of number of sensors, but with a considerable improvement of results in terms of geographical distance between the sensors. Finally, a comparison of the two heuristics with the optimal solution obtained by the problem formulated in integer linear programming is presented, which confirms that the heuristic SSCCR has better performance compared with ODTA heuristic, and in many cases achieves optimal values, and consequently achieve the reduction of energy consumption in the implementation of fault diagnosis.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.c3sl.ufpr.br:1884/41362 |
| Date | January 2015 |
| Creators | Barros, Mauricio de Oliveira |
| Contributors | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática, Weber, Andréa |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 83 f. : il., algumas color., tabs., grafs., application/pdf |
| Source | reponame:Repositório Institucional da UFPR, instname:Universidade Federal do Paraná, instacron:UFPR |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Disponível em formato digital |
Page generated in 0.0021 seconds