Introdução

Redes sem fio são redes que utilizam o ar como meio de transmissão entre os dispositivos. Atualmente, este tipo de rede esta presente por toda parte, possibilitando que dispositivos móveis troquem informações entre si, ou ainda conectando esses dispositivos à internet.

Figura 1 – Topologias de redes sem fio. Retirada de: F. Li and Y. Wang “Routing in Vehicular Ad Hoc Networks: Survey”, IEEE Vehic. Tech., 2007

Existem vários cenário distintos onde redes sem fio podem ser utilizadas, a maneira com que a rede se forma em cada cenário determina sua organização. Quando a comunicação acontece através de um ponto de acesso, que é responsável por encaminhar as mensagens para seus respectivos destinos Figura 1(a), temos uma rede de infraestrutura. Quando não existe a presença deste ponto de acesso, e a rede é formada diretamente entre os dispositivos Figura 1(b), temos uma rede ad hoc. Podemos ainda ter casos em que os dois tipos de comunicação são combinados Figura 1(c), formando uma rede híbrida.

Redes de infraestrutura são as redes que geralmente utilizamos quando conectamos o notebook ou smartphone a uma rede sem fio através de um roteador. Esse tipo de rede oferece uma boa conectividade, e permite altas taxas de transferência, mas possuí seu alcance limitado a uma pequena área geográfica, o que restringe sua aplicação prática.

Quando já existe uma infraestrutura, utilizar desta como meio de comunicação é uma boa opção, pois sua arquitetura e protocolos já estão consolidados. Mas implantar uma infraestrutura por completo tem custo muito alto, sobrando como alternativa o uso de comunicação ad hoc. Por este motivo grande parte dos protocolos que surgem para redes veiculares são projetados para trabalhar em redes ad hoc.

Características de redes VANETs

Redes móveis ad hoc (MANETs) possuem características que são comuns a todos os cenários que utilizam esse tipo de rede, uma dessas características é a largura de banda. Os dispositivos presentes nesse tipo de rede geralmente possuem restrições de comunicação, e utilizam meios cuja largura de banda é baixa. Outra característica não tão distinta da anterior, é o baixo alcance da área de transmissão. A baixa reserva de energia dos dispositivos móveis faz com que economia de energia seja prioritária, com isso, o alcance do raio de transmissão fica restrito a poucos metros. Além das características citadas, MANTEs são auto-gerenciáveis e auto-organizáveis. Os nós da redes geralmente não possuem padrões de mobilidade, o que faz com que sua topologia modifique dinamicamente, as características de auto-organização e auto-gerenciamento são as que tornam possível a comunicação nesse cenário. Lidar com essas características é um desafio encontrado em todos os tipos de redes móveis.

Redes veiculares ad hoc (VANETs) constituem um tipo especial de redes MANETs, e possuem, além das características citadas, outras que são únicas desse tipo de rede. Algumas dessas características se tornam um desafio, e devem ser contornadas para garantir que haja comunicação entre os veículos, outras auxiliam no roteamento, e devem ser exploradas para melhorar a entrega de dados. As principais delas são:

• Topologia altamente dinâmica: A alta velocidade dos veículos e as frequentes mudanças de direção fazem com que a rede se particione a todo momento, e provoca mudanças muito rápidas na topologia da rede.

• Frequentes desconexões na rede: O fato dos veículos se moverem rápido, faz com que a rede se particione e a comunicação direta entre origem e destino deixe de existir, algoritmos de roteamento para esse cenário tem que lidar com esta característica;

• Não possui restrições de energia e armazenamento: Estas características geralmente não são presentes em dispositivos de redes sem fio, mas veículos possuem fonte de energia inesgotável, e pode possuir unidades de processamento com maior poder de computação, além de ter espaço para unidades de armazenamento maiores.

• Permite comunicação geográfica: Uma das principais dificuldades encontradas por algoritmos de roteamento para redes sem fio, é o conhecimento sobre a localização do destino. Em redes veiculares isso pode ser contornado, uma vez que a origem sabe a localização geográfica do destino, ela pode encaminhar a mensagem em direção aquela região, o que melhora a taxa de entrega de dados.

• Modelo de mobilidade previsível: Em redes VANETs, os veículos estão sujeito a mobilidade previsível, pois estão limitados as restrições das ruas e avenidas, devem respeitar a direção e a velocidade do trânsito em cada trecho da rota.

• Vários ambientes de comunicação: VANETs oferecem ambientes heterogêneos. A comunicação em uma rede formada dentro de um centro urbano é diferente da comunicação formada em uma rodovia.

• Limites restritos de atraso: Aplicações em redes VANETs podem oferecer serviços de segurança e assistência ao motorista, onde atrasos na comunicação podem comprometer o bom funcionamento da aplicação colocando vidas em risco.

• Integração com sensores built-in: Esta é outra característica que beneficia algoritmos de roteamento para VANETs. Num futuro próximo, todos os veículos serão fabricados com dispositivos de navegação embutidos, permitindo que informações de geolocalização sejam coletadas em tempo real.

Roteamento em VANETs

Como vimos, as características presentes em VANETs provocam frequentes mudanças de topologia, tornando o roteamento de pacotes nesse tipo de rede um desafio. A falta de um caminho fim a fim entre a origem e o destino, faz com que protocolos de roteamento projetados para redes ad hoc falhem, impedindo seu uso em redes veiculares.

Um algoritmo que utiliza transmissões oportunistas juntamente com a técnica de store-carry-and-forward para garantir boas taxas de entrega é o Epidêmico. Seu princípio consiste em armazenar a mensagem em um buffer e aproveitar a oportunidade de contato com outro nó para sincronizarem as mensagens armazenadas. Esse processo se repete até que a mensagem alcance o destino.

Esquemas de roteamento baseados em inundação, além de garantirem a melhor taxa de entrega de mensagens, também garantem que a mensagem alcance o destino no menor tempo possível, o que o torna uma excelente fonte de comparação com novas propostas. Por outro lado, além das transmissões excessivas causadas pelas retransmissões desnecessárias, é comum desse tipo de roteamento provocar grandes ocupações dos buffers. Ambas características fazem com que o algoritmo Epidêmico perca desempenho, impedindo seu uso prático.

Para resolver esses problemas, o algoritmo Spray and Wait faz o controle do número de cópias de mensagens que serão pulverizadas na rede. Seu funcionamento é divido em duas etapas: na fase de spray o algoritmo calcula o número de cópias que irá pulverizar, este calculo é baseado no número de nós da rede e no atraso desejado para que a mensagem alcance o destino, e pulveriza essas cópias entre os nós que encontrar. Caso o destino não esteja entre os nós cuja origem pulverizou a mensagem, os nós entram na fase de wait. Nesta o nó armazena a mensagem em seu buffer e espera até encontrar com o destino para realizar a entrega.

Apesar da eficiência do algoritmo Spray and Wait, em redes veiculares ele perde desempenho. Isso porque os veículo se dividem entre as diversas direções possíveis, fazendo com que cópias da mensagem sejam pulverizadas para longe do destino, o que diminui as chances de entrega. Para evitar que isso aconteça, o algoritmo RouteSpray faz uso das rotas dos veículos, assim ele consegue decidir qual é o melhor transportador para a mensagem pulverizando as cópias somente em direção ao destino.

Algoritmo RouteSpray

Para realizar o roteamento, o Algoritmo RouteSpray assume que todos os veículos são equipados com dispositivos de navegação, e que suas rotas são conhecidas.

Seu funcionamento baseia-se no uso de dois tipos de mensagens, que são as mensagens de controle e as mensagens de dados. As mensagens de controle são utilizadas para os nós trocarem informações sobre as mensagens entregues na rede. Tal procedimento permite que eles façam controle das mensagens armazenadas em seu buffer,  apagando as que já foram entregues. Outra função das mensagens de controle é possibilitar que os nós troquem informações das mensagens armazenadas em buffer. Através dessas informações os nós são capazes de decidir qual é o melhor transportador da mensagem, encarregando-o de entregá-la ao destino no menor tempo possível.

Para melhorar o processo de roteamento, o RouteSpray combina dois conceitos importantes, que são a utilização de rotas e a técnica de pulverização Binary Spray. Ambas são apresentadas com mais detalhes abaixo:

Utilização de rotas

Uma das principais dificuldades encontradas por algoritmos de roteamento para redes sem fio, é a falta de conhecimento sobre a localização do destino. Em redes veiculares esse problema pode ser contornado deviso a popularização dos dispositivos de navegação. A utilização das rotas dos veículos permite ao RouteSpray prever o tempo exato de contato entre os nós, e com isso, decidir qual é o melhor transportador para a mensagem. Considerando as rotas para os três veículos, apresentados na Figura 2. Caso o veículo B deseje enviar uma mensagem ao veículo C, ele escolherá o veículo A como melhor transportador da mensagem, pois o veículo A encontrará com o veículo C em menor tempo.

Figura 2. Rotas para três veículos.

Binary Spray

A técnica de spray surge como alternativa a esquemas de roteamento baseados em uma única cópia, que introduzem grandes atrasos na entrega, e esquemas de inundação, que degradam a rede pelas transmissões excessivas de mensagens. Existem duas formas diferentes de fazer a pulverização, uma delas é chamada source spray, onde o nó encaminha as L cópias geradas para os L primeiros nós distintos que encontrar. Este, se trata de um esquema de dois saltos, já que o nó que recebe uma cópia fica encarregado de entregá-la somente ao destino.

A outra forma de realizar a pulverização é chamada binary spray, onde o nó encaminha a metade das suas cópias em cada oportunidade de contato. Enquanto o nó possuir mais de uma cópia, seja ele a origem ou um transportador, ele deverá repetir esse processo. Esse esquema transmite para o nó transportador a responsabilidade de pulverizar algumas cópias da mensagem, isso faz com que o encaminhamento seja realizado por múltiplos saltos, o que aumenta a probabilidade de entrega. Por esse motivo, ele foi adotado como política de encaminhamento do algoritmo RouteSpray.

Análise de desempenho

Apesar de desejável a avaliação de protocolos de roteamento em ambientes reais, o alto custo envolvido e a dificuldade em mobilizar pessoal suficiente tornam inviável tal implementação. Por esse motivo, para avaliar o desempenho do RouteSpray foram realizadas simulações comparando-o com os algoritmos Epidêmico e Spray and Wait, que são os dois principais protocolos para redes esparsas.

Para comparar o desempenho dos algoritmos, as seguintes métricas foram avaliadas: (i) Taxa de entrega de mensagens; (ii) Ocupação dos buffers e (iii) Qualidade de mensagens enviadas na rede. Taxa de entrega de mensagens é a soma de todas as mensagens entregues ao destino. A ocupação dos buffer é a soma de todas as mensagens armazenadas nos buffers dos nós da rede, e a quantidade de mensagens enviadas na rede é a soma de todas as mensagens enviadas, incluindo as mensagens de controle.

As simulações foram realizadas considerando um ambiente urbano, onde foram geradas 16 rotas entre os pontos de interesse de uma cidade (rodoviária, shoppings, centros comerciais, universidades, etc). O número de veículos variou entre 5 e 100, onde quando o número de veículos é maior do que o número de rotas, os veículos são distribuídos de forma uniforme entre as rotas.

Para as simulações foi utilizado o simulador de redes OMNeT++ juntamente com o framework de redes sem fio MiXiM. Como padrões de mobilidade baseados em modelos randômicos não correspondem a realidade, a mobilidade foi gerada utilizando o software VeNeM (Vehicular Network Mobility), que permite gerar a mobilidade baseada em parâmetros reais, como velocidade e direção, de acordo com cada trecho da rota.

Figura 3. VeNeM (Vehicula Network Mobility) – Disponível em https://github.com/badriciobq/VeNeM

Resultados

Como citado anteriormente, o algoritmo Epidêmico se torna uma excelente fonte de comparação quando aplicado a cenários em que não há perda de mensagens. Isso, porque ele faz com que as mensagens sigam todos os caminhos possíveis, garantindo a melhor taxa de entrega de mensagens e que a mensagem alcance seu destino no menor tempo. Considerando que o algoritmo Epidêmico entrega todas as mensagens, se tornando limite superior para tal requisito, o algoritmo RouteSpray supera o algoritmo Spray and Wait entregando 13,46% mais mensagens. Tal comportamento pode ser visualizado facilmente na Figura 4.

Figura 4. Mensagens entregues na rede.

O fato do algoritmo epidêmico inundar a rede com cópias das mensagens, faz com que sejam geradas transmissões desnecessárias e provoca grandes ocupações dos buffers dos nós da rede. Tal comportamento pode ser visto facilmente na Figura 5, onde na rede com 75 veículos, para entregar 15 mensagens, foram geradas e armazenadas 1035 cópias das mesmas. Os algoritmos baseados na técnica de spray provocam menores ocupações dos buffers, a Figura 6 comprova a eficiência de tal técnica. Se observarmos, veremos que o algoritmo RouteSpray manteve a ocupação do buffer 73,38% menor do que o algoritmo Spray and Wait, superando este também nesse requisito.

Figura 5. Ocupação dos buffers para os três algoritmos. Figura 6. Ocupação dos buffers dos algoritmos baseados na técnica de spray.

Conclusões

O algoritmo RouteSpray se mostrou eficiente em ambientes cujas rotas dos veículos são conhecidas, podendo ser aplicado na prática em empresas de transporte, como empresas de ônibus, táxis e transportadoras;