Capacity Bounds for Small-World and Dual Radio Networks

• Type: Thesis
• Date: 2007

Authors

Costa, Rui Filipe Mendes Alves da (Author) FEUP; João Barros (Author) FEUP; João Barros (Technical adviser) FEUP

Scientific classification

FOS: Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

CORDIS: Technological sciences > Engineering > Communication engineering

Associated Institutions

FCUP - Faculdade de Ciências da Universidade do Porto

Other information

Resumo (PT): 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 uma segunda 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 classe de 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.

Abstract (EN): Recent results from statistical physics show that large classes of complex networks, both man-made and of natural origin, are characterized by high clustering properties yet strikingly short path lengths between pairs of nodes. This class of networks are said to have a small-world topology. In the context of communication networks, navigable small-world topologies, i.e. those which admit efficient distributed routing algorithms, are deemed particularly effective, for example, in resource discovery tasks and peer-to-peer applications. Breaking with the traditional approach to small-world topologies that privileges graph parameters pertaining to connectivity, and intrigued by the fundamental limits of communication in networks that exploit this type of topology, in the first part of this thesis we investigate the capacity of these networks from the perspective of network information flow. Our contribution includes upper and lower bounds for the capacity of standard and navigable small-world models, and the somewhat surprising result that, with high probability, random rewiring does not alter the capacity of a small-world network. Motivated by the proliferation of dual radio devices, we consider, in the second part of 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 two radio interfaces in a combined manner, we define a wireless network model in which all devices have short-range transmission capability, but a subset of the nodes has a secondary long-range wireless interface. For the resulting class of random graph models, we present analytical bounds for both the connectivity and the max-flow mincut capacity. The most striking conclusion to be drawn from our results is that the capacity of this class of networks grows quadratically with the fraction of dual radio devices, thus indicating that a small percentage of such devices is sufficient to improve significantly the capacity of the network.

Language: Portuguese

Type (Professor's evaluation): Scientific

No. of pages: 55