Análise de técnicas baseadas em metaheurísticas e dominação de grafos para clustering em redes ad hoc

Abstract

As redes ad hoc são caracterizadas pela ausência de infra-estrutura de comunicação. Uma forma de comunicação entre os nós, assim como a manutenção de mudanças de conexão podem utilizar uma estrutura hierárquica baseada em clusters [EPH87]. Um cluster agrupa dinamicamente um conjunto de nós em torno de um nó central, responsável pelo roteamento de dados, chamado de clusterhead [CHA00]. Os demais membros deste cluster são denominados clusternodes. O conjunto de clusterheads de uma rede é chamado de dominant set. Esta estrutura forma um backbone virtual [CHE02]. O problema do particionamento de uma rede em clusters é NP-completo [REE93], fazendo com que a busca por uma solução ótima para a organização em clusters de uma rede ad hoc com topologia móvel seja um desafio. Uma estratégia para a resolução deste problema é a aplicação de técnicas baseadas em metaheurísticas. Desta forma, obter uma "boa" solução, dentro de um cenário com domínio de busca limitado, mostra-se conveniente em boa parte dos casos [REE93]. Este trabalho usa técnicas baseadas em metaheurísticas, algoritmos genéticos [HOL75], simulated annealing [KIR83] e busca tabu [GLO89] na proposição de algoritmos para o particionamento em clusters, levando em consideração o grau de mobilidade da rede, reafiliações, transmissão de dados, disponibilidade, energia e ciclo de vida. Basicamente, os algoritmos buscam a minimização do fluxo de dados inter-clusters. Dados os clusters já formados, determinam-se os clusterheads. Apresentam-se, também, simulações comparando os algoritmos propostos entre si, assim como com outras técnicas de particionamento. _________________________________________________________________________________________ ABSTRACT

Wireless ad hoc networks are characterized for a lack of fixed communication structure. One of the strategies for communications between nodes and the maintenance of connection changes is to adopt a hierarchy structure based in clusters [EPH87]. A cluster dinamically gathers a set of nodes around a local coordinator of data transmission, called clusterhead. All other members of this cluster are called clusternodes or members. The set of clusterheads on a network is called dominant set [CHA00]. This structure forms a virtual backbone [CHE02]. The clustering partitioning in wireless ad hoc networks is a NP-complete problem [REE93], leading to research for an optimal solution for a mobile generic topology as a challenge. An approach to solve this problem is applying metaheuristics techniques. So, to obtain a "good" solution within a scenario with a limited search range proves convenient for several cases and the use of metaheuristics is a powerful instrument to do so [REE93]. This work presents a study about metaheuristics algorithms, such as genetic algorithms [HOL75], simulated annealing [KIR83], and tabu search [GLO89] to determinate cluster partitioning in a generic wireless mobile ad hoc network, taking in consideration mobility models, data transmission, availability, energy and life cycle of nodes. Basically, the proposed models are based on inter-clusters data flow minimization strategy. In a second phase, clusterheads are determined, once clusters has already formed. Simulation results are presented to compare these techniques and some existing models to prove results.