• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.45.2012.tde-12032012-104708
Documento
Autor
Nome completo
Paulo Henrique Floriano
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2012
Orientador
Banca examinadora
Lejbman, Alfredo Goldman Vel (Presidente)
Mini, Raquel Aparecida de Freitas
Pina Junior, Jose Coelho de
Título em português
Grafos evolutivos na modelagem e análise de redes dinâmicas
Palavras-chave em português
Algoritmos Distribuídos
DTNs
Exclusão Mútua Distribuída
Grafos Evolutivos
MANETs
Rastros
Redes Dinâmicas
Resumo em português
Atualmente, muitas redes com características dinâmicas estão em funcionamento (por exemplo MANETs, DTNs, redes oportunistas, etc). Neste trabalho, estudamos um modelo para estas redes chamado de Grafos Evolutivos, que permite expressar a dinamicidade das conexões entre nós por meio de uma simples extensão da estrutura comum de grafos. Esta modelagem é utilizada no arcabouço proposto por Casteigts et al. para definir algoritmos distribuídos em redes dinâmicas, que utiliza grafos evolutivos para representar a topologia da rede e renomeação de rótulos para expressar a comunicação entre os nós. Utilizamos esta abordagem para estudar o problema da exclusão mútua distribuída em redes dinâmicas e diversos algoritmos propostos para ele, a fim de definir e validar suas condições necessárias e suficientes de conectividade em redes dinâmicas. Além da formalização de algoritmos, o modelo de grafos evolutivos também pode ser utilizado para analisar redes dinâmicas. Rastros de redes dinâmicas reais são amplamente utilizados na literatura para estudos de algoritmos pois estes geram resultados mais realísticos do que redes simuladas com padrões de movimento. A partir dos detalhes de cada conexão entre nós de um destes rastros, é possível construir um grafo evolutivo, do qual se pode extrair dados como jornadas ótimas entre nós, variação da conectividade no tempo, estabilidade, e periodicidade. Com as informações mencionadas, um pesquisador pode observar com maior precisão as características do rastro, o que facilita na escolha da rede mais apropriada para sua necessidade. Além disso, o conhecimento prévio de tais características de uma rede auxilia no estudo do comportamento de algoritmos executados sobre ela e provém uma validação para suposições geralmente feitas pelos pesquisadores. Para fornecer estas informações, desenvolvemos uma ferramenta Web que analisa rastros de redes dinâmicas e agrega os dados em um formato de fácil visualização. Descrevemos, neste trabalho, a implementação e a utilidade de todos os serviços da ferramenta.
Título em inglês
Evolving Graphs in the Modeling and Analysis of Dynamic Networks
Palavras-chave em inglês
Distributed Algorithms
Distributed Mutual Exclusion
DTNs
Dynamic Networks
Evolving Graphs
MANETs
Traces
Resumo em inglês
Lately, several networks with dynamic properties (for instance MANETs, DTNs, opportunistic networks, etc) are functioning. In this work, we studied a model for these networks called Evolving Graphs, which allows the expression of the dynamicity of the conections between nodes through a simple extension of the common graph structure. This model is used by the framework proposed by Casteigts et al. to define distributed algorithms in dynamic networks, which uses evolving graphs to represent the network topology and graph relabelling to express the communication between nodes. Using this approach, we study the distributed mutual exclusion problem in dynamic networks and several algorithms proposed to solve it, in order to define and validate their necessary and sufficient connectivity conditions. Apart from the formalization of algorithms, the evolving graphs model can also be used to analyze dynamic networks. Dynamic network traces are widely used in the literature in order to study algorithms, as they generate better results than simulated networks with movement patterns. From the details of every connection between nodes in a trace, it is possible to build an evolving graph, from which a large amount of information can be extracted, such as optimal journeys between nodes, variation of the conectivity over time, stability and periodicity. With the aforementioned information, a researcher might observe the characteristics of a trace more precisely, which facilitates the process of choosing the most appropriate trace for his needs. Furthermore, the early knowledge of such characteristics of a network helps in the study of the behavior of the algorithms exected over it and provides a validation for the assumptions usually made by the researchers. In order to provide this information, we developed a web tool which analyzes dynamic network traces and aggregates the data in an easily readable format. In this work, we describe the implementation and usefulness of every service in the tool.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
tese.pdf (1.33 Mbytes)
Data de Publicação
2012-03-19
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2021. Todos os direitos reservados.