Author(s):
Pereira, Salomé Santos Rodrigues 
Date: 2011
Persistent ID: http://hdl.handle.net/10773/10536
Origin: RIA - Repositório Institucional da Universidade de Aveiro
Subject(s): Matemática aplicada; Ciências da computação; Redes sem fios; Grafos
Description
Numa era em que a importância da tecnologia não pára de crescer, as redes
sem os têm assumido um papel cada vez mais relevante. O elevado
crescimento das redes di culta a Recuperação de Falhas com base na informa
ção de todos os elementos de uma rede, levando à utilização de algoritmos
em que cada elemento altera a sua informação consoante a informação da
maioria dos seus vizinhos.
Considerando então uma rede bicromática, em que os elementos azuis são os
saudáveis e os vermelhos os defeituosos, usou-se um método, denotado por
Recoloração Geométrica, que reclassi ca o estado de um elemento através
de uma recoloração deste sempre que esteja cercado por elementos da cor
oposta. Assim, se um elemento defeituoso estiver cercado por saudáveis,
este corrigirá a sua informação.
Nesta dissertação de nem-se duas novas estruturas de redes, as redes
NIC&Mi2 e as NIC&QC, cujas sequências de recoloração têm, respectivamente,
comprimentos (n2) e (n), onde n é o número de nós. Propõe-se
algoritmos que permitem alterar uma rede aleatória para que passe a satisfazer
as propriedades destas novas redes. Propõe-se também um algoritmo
para alterar uma rede para NIC, em detrimento de um já existente cuja
complexidade é superior. Estas alterações pretendem garantir a nitude do
algoritmo de recoloração, usado na Recuperação de Falhas. Testa-se a e -
ciência da Recuperação de Falhas para estas três estruturas de redes através
de estudos experimentais e conclui-se que as redes NIC apresentam uma
melhor recuperação devido ao número de alterações, que é inferior no caso
destas. In an age where technology's importance is growing continually, wireless
networks have assumed a major role. Due to network's high growth, Fault
Recovery based on the entire network's information has become ine cient,
therefore leading to algorithms in which every element changes its information
based on its neighbor's information.
Considering a bi-chromatic network, in which the blue elements are the
healthy ones and the red are the faulty ones, the Fault Recovery is done
by reclassifying the elements through a recoloring of the ones that are surrounded
by elements of the opposite color. Thus, if a faulty element is
surrounded by healthy elements, it will become healthy. This method is
denoted by Geometric Recoloring.
This discussion presents two new network structures: NIC&Mi2 and
NIC&QC networks. The recoloring sequence's length of these networks are,
respectively, (n2) e (n), where n is the number of nodes. It is proposed
two algorithms that change a random network so it will satisfy the properties
of these new networks. It is also proposed a new algorithm to transform a
random network into a NIC one. This new approach is more e cient than a
previous known algorithm for this purpose as it presents a lower complexity.
The changes that are made in all of these three cases ensure that the recoloring
algorithm, used in Fault Recovery, is nite. Experimental tests were
performed on these three network structures to assess the e ciency of Fault
Recovery. These tests have concluded that NIC networks are the ones with
best recovery due to the fewer number of changes. Mestrado em Matemática e Aplicações
