Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2006. / Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2010-05-12T14:48:31Z
No. of bitstreams: 1
2006_HeltonFabianoGarcia.pdf: 2933521 bytes, checksum: 4db50a5ab873f60b925f201613bbef68 (MD5) / Approved for entry into archive by Lucila Saraiva(lucilasaraiva1@gmail.com) on 2010-05-13T02:28:34Z (GMT) No. of bitstreams: 1
2006_HeltonFabianoGarcia.pdf: 2933521 bytes, checksum: 4db50a5ab873f60b925f201613bbef68 (MD5) / Made available in DSpace on 2010-05-13T02:28:34Z (GMT). No. of bitstreams: 1
2006_HeltonFabianoGarcia.pdf: 2933521 bytes, checksum: 4db50a5ab873f60b925f201613bbef68 (MD5)
Previous issue date: 2006-08-18 / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unb.br:10482/4590 |
| Date | 18 August 2006 |
| Creators | Garcia, Helton Fabiano |
| Contributors | Gondim, Paulo Roberto de Lira |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UnB, instname:Universidade de Brasília, instacron:UNB |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds