Escalonamento de Enlaces e Roteamento Multi-Caminho para Redes em Malha Sem Fio
Autores
|
5244 |
1980,163,883,2371
|
|
|
5257 |
1980,163,883,2371
|
|
|
5258 |
1980,163,883,2371
|
|
|
5259 |
Serge Fdida
(Co-orientador) |
1980,163,883,2371
|
Informações:
Publicações do PESC
Título
Escalonamento de Enlaces e Roteamento Multi-Caminho para Redes em Malha Sem Fio
Linha de pesquisa
Inteligência Artificial
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
23/5/2012
Resumo
Nós apresentamos duas heurísticas como solução para dois problemas ligados à interferência nas redes sem fio. Inicialmente, nós propomos escalonar os enlaces pertencentes a um conjunto de rotas dado em uma rede congestionada. Nós adotamos um protocolo TDMA que oferece uma fonte de intervalos de tempo sincronizados e buscamos escalonar os enlaces das rotas objetivando maximizar o número de pacotes que são entregues nos destinos das rotas por intervalo de tempo do escalonamento. Nossa abordagem consiste em construir um grafo não orientado $G$ e obter múltiplas colorações paro os nós de $G$ que podem induzir aos escalonamentos de enlaces ótimos segundo nosso critério de entrega de pacotes aos destinos. Em $G$ cada nó representa um enlace a ser escalonado e as arestas são acrescentadas ao grafo para representar todas as possíveis interferências dentro de um conjunto de hipóteses sobre a interferência na rede. Nós apresentamos duas heurísticas de multi-coloração e estudamos seus desempenhos baseados em uma longa serie de experimentos. Uma das heurísticas é baseada em no relaxamento da noção de multi-coloração de nós e dessa forma, a heurística é capaz de eliminar os desperdícios de intervalos de tempo provocados pelos escalonamentos com estrita multi-coloração. Nós constatamos que, o desempenho dela é significativamente superior se comparado as demais heurísticas de coloração de nós. Na segunda proposta, nós apresentamos uma heurística que determina um subconjunto dos múltiplos caminhos previamente descobertos por qualquer algoritmo de roteamento. Esse conjunto possui a distinguível característica de não possuir caminhos que se interferem.
A heurística proposta é totalmente local do ponto de vista de cada nó da rede, pois utiliza apenas a informação disponível na vizinhança imediata do nó onde está sendo executada. Nós executamos extensivos experimentos computacionais com a nova heurística, utilizando os algoritmos AODV e OLSR assim como suas versões multi-caminho. Para dois mecanismos de acesso ao meio (TDMA e CSMA), nós demonstramos que a heurística obtém resultados significativamente superiores aos algoritmos de roteamento originais, tanto em termos de justiça na rede como em taxa de transferência.
Abstract
We present algorithmic solutions for two problems related to the wireless network interference.
The first one proposes to schedule the links of a given set of routes under the assumption of a heavy-traffic pattern. We assume some TDMA protocol provides a background of synchronized time slots and seek to schedule the routes' links to maximize the number of packets that get delivered to their destinations per time slot. Our approach is to construct an undirected graph $G$ and to heuristically obtain node multicolorings for $G$ that can be turned into efficient link schedules. In $G$ each node represents a link to be scheduled and the edges are set up to represent every possible interference for any given set of interference assumptions. We present two multicoloring-based heuristics and study their performance through extensive simulations. One of the two heuristics is based on relaxing the notion of a node multicoloring by dynamically exploiting the availability of communication opportunities that would otherwise be wasted. We have found that, as a consequence, its performance is significantly superior to the other's. In the second proposal, we consider wireless mesh networks and the problem of routing end-to-end traffic over multiple paths for the same origin-destination pair with minimal interference. We introduce a heuristic for path determination with two distinguishing characteristics. First, it works by refining an extant set of paths, determined previously by a single- or multi-path routing algorithm. Second, it is totally local, in the sense that it can be run by each of the origins on information that is available no farther in the network than the node's immediate neighborhood. We have conducted extensive computational experiments with the new heuristic, using AODV and OLSR as well as their multi-path variants as the underlying routing method. For one TDMA setting running a path-oriented link scheduling algorithm and two different CSMA settings (as implemented on 802.11), we have demonstrated that the new heuristic is capable of improving the average throughput network-wide. When working from the paths generated by the multi-path routing algorithms, the heuristic is also capable to provide a more evenly distributed traffic pattern.
Arquivo