Towards Scalable Routing for Wireless Multi-hop Networks

Abstract

The growing di usion of wireless interfaces (namely using the IEEE 802.11 standard) in the most diverse type of equipments has led to a myriad of new networking scenarios. Several wireless capable gadgets are expected to be interconnected, demanding an increasing amount of resources to existing network infrastructures. In order to suppress these networking needs, in any possible scenario, the Ad-hoc paradigm allows the creation of autonomous infrastructure-less networks, capable of heterogeneously guarantee communication between these wireless devices. Even though previous works already exist regarding routing in Mobile Adhoc Networks (MANETs), the increasing demand for these networks revealed that these protocols do not scale accordingly. Bearing this issue in mind, the presented work addresses the scalability of routing protocols, proposing a new routing paradigm capable of handling large-scale networks, bene ting from the contextual proximity between users. By introducing a well de ned network organisation with di erent granularity levels, the Deferred Routing scheme, presented in this thesis, uses a hierarchical structure to handle existing clusters of nodes, in conjunction with virtual clusters that aggregate the real clusters. This organisation provides nodes with more stable network views, detracting the unwanted e ects of mobility between neighbour clusters. The routing stability and scalable mechanisms are also achieved by using a packet forwarding technique in which the routing information is progressively more accurate, as the level of routing information detail increases when nodes are closer to the desired destination. During the forwarding process, nodes in the borders of clusters, or Gateway nodes, are identi ed in order to cross di erent clusters. In the gateway selection process a link quality estimation model is used, ensuring that the best existing gateway nodes are selected, implicitly achieving a balanced load between the available gateways. This forwarding approach further improves the performance of the proposed protocol, being extremely resilient to network changes and enabling self-healing properties of the chosen paths, as they are maintained by the di erent gateway nodes across clusters. Through an extensive performance analysis of Deferred Routing, resorting to di erent evaluation scenarios, an improvement on tra c delivery was registered when compared to well-known routing alternatives. The obtained results also revealed an increased stability regarding topology changes and routing table calculations, leading to a lower control tra c overhead in all the assessed scenarios, outperforming the analysed competitors. These results motivate a new era of applications for MANETs and suggest that ubiquitous communication is likely to take place in a near future. This results not only from the increasing availability of wireless capable devices, but also due the possibility of managing large-scale networks using lightweight routing mechanisms.

A crescente disponibiliza c~ao de interfaces sem- os (nomeadamente seguindo o standard IEEE 802.11) nos mais diversos tipos de equipamentos, deu origem a uma grande diversidade de novos cen arios de redes de comunica c~ao. Espera-se que v arios dispositivos com capacidades de comunica c~ao sem- os se encontrem interligados, exigindo uma crescente quantidade de recursos as infraestruturas de rede existentes. De modo a dar resposta a estas necessidades de comunica c~ao nos v arios cen arios poss veis, o paradigma Ad-hoc possibilita a cria c~ao de redes sem-infraestrutura aut onomas e capazes de garantir de forma heterog enea a comunica c~ao entre estes dispositivos sem- os. Apesar de j a existirem trabalhos anteriores que dizem respeito ao encaminhamento em redes m oveis Ad-hoc, a crescente procura destas redes revelou que os seus protocolos n~ao s~ao escal aveis. Tendo este problema em considera c~ao, o trabalho apresentado aborda a escalabilidade dos protocolos de encaminhamento, propondo um novo paradigma capaz de lidar com redes de larga-escala, que bene cia da proximidade contextual entre utilizadores. Por meio de uma organiza c~ao de rede bem de nida com diferentes n veis de granularidade, o esquema de Encaminhamento Diferido (Deferred Rout- ing) apresentado nesta tese usa uma estrutura hier arquica para lidar com os grupos de n os existentes, utilizando em simult^aneo grupos virtuais que agregam os grupos reais. Esta organiza c~ao fornece aos n os vistas da rede mais est aveis, reduzindo os efeitos indesejados da mobilidade entre grupos vizinhos. A estabilidade do encaminhamento e mecanismos de escalabilidade s~ao tamb em alcan cados atrav es da utiliza c~ao de uma t ecnica de reencaminhamento de pacotes onde a informa c~ao de encaminhamento e progressivamente mais precisa, uma vez que o n vel de detalhe da informa c~ao de encaminhamento aumenta quando os n os se encontram mais perto do destino desejado. Durante o processo de reencaminhamento, os n os na fronteira do seu grupo, denominados n os fronteira, s~ao identi cados por forma a atravessar v arios grupos. No processo de selec c~ao de n os fronteira e utilizado um modelo de estima c~ao da qualidade de uma liga c~ao sem- os, garantindo um equil brio da carga entre os n os fronteira existentes. Esta abordagem de reencaminhamento melhora a performance do protocolo proposto, sendo extremamente resiliente a altera c~oes na rede e atribuindo propriedades de auto-repara c~ao dos caminhos escolhidos, uma vez que estes s~ao mantidos por diferentes n os fronteira atrav es dos grupos de n os. Atrav es de uma extensa an alise da performance do protocolo de Encaminhamento Diferido, recorrendo a diferentes cen arios de avalia c~ao, foi registada uma melhoria na entrega de tr afego quando comparado com outras alternativas de encaminhamento conhecidas. Os resultados obtidos revelam tamb em uma crescente estabilidade no que diz respeito a altera c~oes de topologia e c alculos da tabela de encaminhamento, resultando numa menor sobrecarga do tr afego de controlo em todos os cen arios avaliados, superando os concorrentes analisados. Estes resultados sugerem que e prov avel o in cio de uma nova era de aplica c~oes para redes m oveis Ad-hoc e comunica c~ao ub qua. Isto ocorre n~ao s o devido ao aumento do n umero de equipamentos sem- os existentes, mas tamb em devido a possibilidade de manuten c~ao de redes de larga-escala utilizando mecanismos de encaminhamento com pouca sobrecarga.