Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/38205
Tipo: | Dissertação |
Título: | Um algoritmo para projeto de redes hierárquicas |
Título(s) alternativo(s): | An algorithm for hierarchical network design |
Autor(es): | Frederico Rodrigues Borges da Cruz |
Primeiro Orientador: | Henrique Pacca Loureiro Luna |
Primeiro membro da banca : | Luiz Aurélio Raggi |
Segundo membro da banca: | Roberto Diéguez Galvão |
Terceiro membro da banca: | Márcio Luiz Bunte de Carvalho |
Resumo: | A rede de alimentação de uma central telefônica é modelada como uma rede hierárquica. Nesse tipo de rede, um nó central (central telefônica) distribui fluxos a nós terminais com demanda (armários de distribuição), através de um conjunto de concentradores de demanda (estágios de linha remotos). É apresentado um algoritmo em três fases para o projeto da rede hierárquica. A primeira fase consiste em localizar os concentradores, através do problema das p-medianas com custos fixos. A cada concentrador corresponde uma rede, para a qual uma boa topologia é determinada na segunda fase, por meio de um problema de programação inteira mista, resolvido através de um procedimento de adição e substituição de arcos. Na terceira fase, usando-se um modelo similar, é feita a conexão dos concentradores ao nó central. Um sistema é implementado, para testes do algoritmo proposto. É apresentada a documentação do sistema, por meio de diagramas de fluxos de dados, dicionário de dados e diagramas hierárquicos dos módulos. Os resultados obtidos com o algoritmo proposto indicam que boas soluções para a rede hierárquica são determinadas, embora nem sempre as melhores. Redes de porte considerável são resolvidas (200 nós) e os resultados indicam que o tempo de processamento cresce rapidamente com o tamanho do problema. |
Abstract: | The primary network of a telephone switching center is presented as a hierarchical network. In such a network, a root node (switching center) distributes flows to terminal nodes (distribution boxes) via a set of demand concentrators. A 3-phase hierarchical network design algorithm is presented. First, the fixed-charge p-median problem formulation is used to locate the concentrators. For each concentrator's network, a good topology is obtained by solving a mixed integer programming problem through addition and interchange of arcs. The third phase uses a similar model to connect the concentrators to the root node. The proposed algorithm is implemented. Also presented are the data flow diagrams, data dictionary, and the module hierarchical diagrams of the implemented system. The 3-phase algorithm results show that good solutions can be obtained for the hierarchical network, in spite of not being the best. Large networks are solved (200 nodes) and the solutions show that the CPU time grows quickly with the problem size. |
Assunto: | Computação Localização Otimização combinatória Planejamento Redes de computadores |
Idioma: | por |
País: | Brasil |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
Curso: | Programa de Pós-Graduação em Ciência da Computação |
Tipo de Acesso: | Acesso Aberto |
metadata.dc.rights.uri: | http://creativecommons.org/licenses/by-nc-nd/3.0/pt/ |
URI: | http://hdl.handle.net/1843/38205 |
Data do documento: | 6-Ago-1991 |
Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
MScFRBCruz.pdf | Dissertação de mestrado do discente F. R. B. Cruz | 7.72 MB | Adobe PDF | Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons