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. / 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.
| Identifer | oai:union.ndltd.org:up.pt/oai:repositorio-aberto.up.pt:10216/96727 |
| Date | January 2007 |
| Creators | Costa, Rui Filipe Mendes Alves da, João Barros |
| Contributors | João Barros, Faculdade de Engenharia |
| Source Sets | Universidade do Porto |
| Language | Portuguese |
| Detected Language | English |
| Type | Dissertação |
| Format | application/pdf |
| Rights | restrictedAccess |
Page generated in 0.0023 seconds