Recoloração geométrica na recuperação de falhas em redes sem fios

Abstract

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.