Análise de técnicas baseadas em metaheurísticas e dominação de grafos para clustering em redes ad hoc / Metaheuristics and graph domination techniques analisys for clustering in wireless mobile AD HOC networks

AUTOR(ES)

Helton Fabiano Garcia

DATA DE PUBLICAÇÃO

2006

RESUMO

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.

ASSUNTO(S)

análise por conglomerados sistemas de telecomunicacoes metaheurísticas redes de computação algoritmos genéticos, simulated annealing, busca tabu clustering metaheuristics, clustering in wireless ad hoc networks, genetic algorithms, simulated annealing, tabu search. redes ad hoc otimização combinatória

Documentos Relacionados

• UM FRAMEWORK PARA SIMULAÇÃO DE REDES MÓVEIS AD HOC
• Metaheurísticas para o problema de agrupamento de dados em grafo
• Analise comparativa entre protocolos de camada MAC para redes ad-hoc sem fio
• Performance analysis of wireless Ad Hoc networks
• Roteamento adaptativo em redes ad hoc sem fio : modelagem e simulação