Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.unb.br/handle/10482/4590
Files in This Item:
File Description SizeFormat 
2006_HeltonFabianoGarcia.pdf2,86 MBAdobe PDFView/Open
Title: Análise de técnicas baseadas em metaheurísticas e dominação de grafos para clustering em redes ad hoc
Other Titles: Metaheuristics and graph domination techniques analisys for clustering in wireless mobile AD HOC networks
Authors: Garcia, Helton Fabiano
Orientador(es):: Gondim, Paulo Roberto de Lira
Assunto:: Análise por conglomerados
Redes de computação
Issue Date: 18-Aug-2006
Citation: GARCIA, Helton Fabiano. Análise de técnicas baseadas em metaheurísticas e dominação de grafos para clustering em redes ad hoc. 2006. 200 f. Dissertação (Mestrado em Engenharia Elétrica)-Universidade de Brasília, Brasília, 2006.
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.
Description: Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2006.
Appears in Collections:ENE - Mestrado em Engenharia Elétrica (Dissertações)

Show full item record Recommend this item " class="statisticsLink btn btn-primary" href="/handle/10482/4590/statistics">



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.