Please use this identifier to cite or link to this item: http://hdl.handle.net/10216/96727
Author(s): Costa, Rui Filipe Mendes Alves da
João Barros
Title: Capacity Bounds for Small-World and Dual Radio Networks
Issue Date: 2007
Abstract: Recent results from statistical physics show that large classes of complex networks,both man-made and of natural origin, are characterized by high clustering propertiesyet strikingly short path lengths between pairs of nodes. This class of networks aresaid to have a small-world topology. In the context of communication networks,navigable small-world topologies, i.e. those which admit efficient distributed routingalgorithms, are deemed particularly effective, for example, in resource discovery tasksand peer-to-peer applications. Breaking with the traditional approach to small-worldtopologies that privileges graph parameters pertaining to connectivity, and intriguedby the fundamental limits of communication in networks that exploit this type oftopology, in the first part of this thesis we investigate the capacity of these networksfrom the perspective of network information flow. Our contribution includes upperand lower bounds for the capacity of standard and navigable small-world models, andthe somewhat surprising result that, with high probability, random rewiring does notalter the capacity of a small-world network.Motivated by the proliferation of dual radio devices, we consider, in the second partof this thesis, communication networks in which the devices have two radio interfaces.With the goal of studying the performance gains in this networks when using the tworadio interfaces in a combined manner, we define a wireless network model in whichall devices have short-range transmission capability, but a subset of the nodes hasa secondary long-range wireless interface. For the resulting class of random graphmodels, we present analytical bounds for both the connectivity and the max-flow mincutcapacity. The most striking conclusion to be drawn from our results is that thecapacity of this class of networks grows quadratically with the fraction of dual radiodevices, thus indicating that a small percentage of such devices is sufficient to improvesignificantly the capacity of the network.
Description: Grafos aleatórios do tipo Small-World e Power-Law têm sido utilizados como modelos para um número elevado de redes naturais e redes tecnológicas, porque capturam algumas das suas propriedades fundamentais. Em redes de comunicação, pensa-se que topologias Small-World navegáveis, i.e. aquelas que admitem algoritmos distribuídos de encaminhamento, sejam particularmente eficientes, por exemplo, em tarefas de descoberta de recursos e aplicações peer-to-peer. Apesar do potencial evidenciado por topologias deste tipo em redes de comunicação, a abordagem tradicional a redes Small-World privilegia parâmetros relacionados com a conectividade. Assim, torna-se crucial saber quais são os limites fundamentais de comunicação em redes que exploram este tipo de topologia. Com o objectivo de estudar esses limites, na primeira parte desta tese estudamos a capacidade destas redes do ponto de vista de fluxos de informação em redes. As nossas contribuições incluem limites superiores e inferiores para a capacidade de redes do tipo Small-World, incluindo um resultado surpreendente, que pode ter a seguinte interpretação: alterar aleatoriamente os extremos de algumas ligações não altera a capacidade da rede, com probabilidade convergente para 1.Na segunda parte desta tese, motivados pela proliferação de aparelhos com duas interfaces de rádio, consideramos redes de comunicação em que os aparelhos são deste tipo. Com o objectivo de estudar os ganhos ao utilizar de uma forma combinada as duas interfaces de rádio, definimos um modelo para redes sem fios em que todos os aparelhos partilham uma tecnologia sem fios de curto alcance e alguns possuem umasegunda tecnologia sem fios, esta de longo alcance. Para a classe de grafos definida pelo modelo, apresentamos limites superiores e inferiores tanto para a probabilidade de uma instância do modelo ser conexa, como para a sua capacidade. A conclusão mais interessante a retirar dos nossos resultados é o facto de a capacidade desta classede grafos crescer quadraticamente com a proporção de aparelhos que possuem as duas tecnologias sem fios, indicando assim que apenas uma pequena percentagem destes aparelhos é suficiente para melhorar significativamente a capacidade da rede.
Subject: Engenharia de comunicações, Engenharia electrotécnica, electrónica e informática
Communication engineering, Electrical engineering, Electronic engineering, Information engineering
Call Number: 27016
URI: http://hdl.handle.net/10216/96727
Document Type: Dissertação
Rights: restrictedAccess
Appears in Collections:FEUP - Dissertação

Files in This Item:
File Description SizeFormat 
27016.pdf486.92 kBAdobe PDF    Request a copy


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