Protocolos de Redes Ad Hoc

1. Introdução

Uma rede ad hoc sem fio é um tipo de rede descentralizada que não depende de uma infraestrutura pré-existente, como roteadores ou pontos de acesso. Nela os nós atuam tanto como hosts quanto como roteadores. Eles possuem livre movimentação no espaço, e podem entrar ou sair da rede à qualquer instante. A topologia da rede está, também, em constante mudança com a variação de distâncias entre os dispositivos. Assim, redes ad hoc devem ser capazes de lidar com desconexões frequentes, atraso variante e perda de pacotes. Devido à cobertura limitada do sinal de cada nó a rede depende de protocolos de roteamento multi-hop.

Esse modelo de rede é útil em casos que a infraestrutura é inexiste ou não pode ser confiada como por exemplo em situações militares no campo de batalha, série de sensores espalhados em uma região para monitoramento biológico, ou uma rede de laptops em uma sala de aula ou conferência.

2. História

Modelos de redes similares à ad hoc datam desde os anos 70 e 80, onde projetos financiados pela Defense Advanced Research Projects Agency (DARPA) foram criados com fins militares. A Packet Radio Network e a Survivable Adaptive Radio Network buscavam providenciar uma rede móvel no campo de batalha sem infraestrutura.

É nos anos 90 que o termo rede ad hoc é adotado pelo sub comitê do IEEE 802.11. Com a popularização de laptops e outros equipamentos de comunicação o interesse em uma rede sem infraestrutura para fins não militares começa a crescer. Assim, são criados grupos que buscavam padronizar protocolos de roteamento das MANET.

3. Desafios

3.1. Instabilidade

A natureza altamente dinâmica das redes ad hoc traz um alto grau de instabilidade relacionado. À qualquer momento nós que se comunicavam diretamente podem ficar fora do alcance um do outro, nós podem deixar a rede e outros podem entrar. Além disso muitas vezes existe ruído e interferência associado aos ambientes e situações de uso.

3.2. Escalabilidade

Assim como em redes cabeadas, as redes ad hoc sem fio enfrentam problemas relacionados à escalabilidade. Essa questão envolve o aumento da complexidade e do custo do roteamento relacionado ao aumento do número de nós e mudanças dos enlaces.

3.3. Segurança

O ambiente potencialmente inseguro em um meio de rádio compartilhado deixa as redes ad hoc suscetíveis à ataques de DoS, com atacantes mais difíceis de serem encontrados do que em redes cabeadas. Esses ataques podem ser usados também com o objetivo de esgotar a bateria dos nós da rede.

Além disso, como as redes constantemente se organizam e cada nó pode passar repassar pacotes pros outros elas são particularmente suscetíveis à possíveis controles de tráfego maliciosos.

3.4. Energia

A rede não assume a existência de uma infraestrutura, então nós individuais podem depender de uma fonte de energia portátil e limitada. Dessa forma se torna necessário a existência de mecanismos de economia de energia.

4. Protocolos

4.1. Protocolos Proativos (Table-driven)

Protocolos proativos são caracterizados por cada nó possuir a completa tabela de roteamento. Quando alterações são feitas na topologia da rede todos os nós precisam ser avisados para terem suas tabelas atualizadas. Assim, todos dispositivos possuem rotas para todos os outros a todo momento. Esses protocolos adaptam algoritmos existentes usados em redes comuns.

4.1.1. DSDV

O protocolo DSDV, ou Destination Sequenced Distance Vector, é baseado no algoritmo de roteamento Bellman-Ford e adapta o RIP, usado em redes fixas. Nele, as estações possuem tabelas completas com todos os destinos da rede e número de saltos até eles. Os dispositivos periodicamente enviam suas tabelas buscando manter consistência entre todos da rede, e transmitem atualizações significativas imediatamente quando ocorrem.

A tabela de roteamento possui quatro campos principais: destina, próximo salto, métrica (número de saltos) e número de sequência. O número de sequência é gerado pelo nó destino, sendo incrementado sempre que ele mandar novas informações, e é usado na detecção de rotas obsoletas. Quando um nó recebe uma mensagem com novas informações ele primeiro checa o número de sequência. Se o número de um destino for maior que o presente atualmente na tabela ele atualiza a rota. Se for o mesmo número que o atual é feita a checagem da métrica, e a rota com a menor é escolhida.

Destino	Próximo Salto	Métrica	Número de Seq.
A	A	0	A 22
B	B	1	B 12
C	B	2	C 8

Para diminuir a quantidade de dados transmitidas os nós possuem dois modos de transmissão de tabela de roteamento. No modo full dump a tabela inteira é enviada para os vizinhos. Em ocasiões onde a rede está relativamente estável mensagens full dump podem acontecer com frequência relativamente baixa. Já o modo incremental são compartilhadas as penas as rotas que sofreram mudanças desde o último full dump. Quando alterações na rede começam a ficar muito frequentes um full dump é lançado.

O DSDV possui tempo de atraso de encontrar rotas muito baixo, posto que todos os dispositivos sempre tem uma tabela de roteamento atualizada. Por outro lado, a constante troca de mensagens de controle ocupa banda e gasta energia dos dispositivos.

4.1.2. OLSR

OLSR, ou Optimized Link State Routing Protocol, é um protocolo de roteamento de estado de enlace. Diferente de implementações clássicas do estado de enlace o OLSR se baseia no uso de Multipoint Relays (MPRs). Ao invés de todos os nós da rede realizarem o flooding (inundação), apenas alguns selecionados (os MPRs) ficam responsáveis por retransmitir mensagens de controle. Diminuindo, assim, o número de mensagens redundantes (overhead). Cada nó é responsável por selecionar seus MPRs, garantindo que exista caminho para todos vizinhos à dois saltos de distância passando por um MPR. Vizinhos diretos são encontrados pelas mensagens Hello, e vizinhos à dois saltos são encontrados pelas respostas dos diretos.

O protocolo não depende de transmissão confiável de dados. Os nós transmitem periodicamente seus dados, criando uma razoável tolerância à perdas. Mensagens de controle contém números de sequência, o que permite que os nós possam identificar informações mais recentes.

Por ser proativo, as rotas no OSPR estão disponíveis prontamente, então não há grande atraso associado à busca de rotas. Além disso, a otimização com os MPRs garante certa escalabilidade ao tamanho da rede. Por outro lado existe um custo computacional associado ao cálculo de rotas ótimas que, junto com as transmissões periódicas de mensagens, levam à um gasto de energia considerável.

4.2. Protocolos Reativos (On-demand)

Nos protocolos reativos a fonte só vai procurar uma rota quando quiser enviar uma mensagem. Dessa forma, os nós não possuem a tabela da topologia completa, e não são necessárias mensagens de controle sendo trocadas constantemente.

4.2.1. DSR

O protocolo DSR, Dynamic Source Routing, se baseia em dois principais processos: descoberta de rota e manutenção de rota.

O processo de descoberta é iniciado quando uma fonte deseja se comunicar com um nó destino e não possui nenhuma rota cacheada para ele. A fonte envia uma mensagem para todos seus vizinhos buscando o destino. Não sendo o destino, o nó vizinho adicionará um identificador próprio à mensagem e retransmitirá ela aos seus vizinhos. Quando essa mensagem de busca chega ao nó alvo ele devolve a mensagem, que agora contém todos os nós intermediários, à origem. Assim a fonte descobre um ou mais caminhos possíveis e os armazena.

O processo de manutenção serve para checar a validade de rotas armazenadas. Se durante o envio de uma mensagem um nó for detectado como inválido ou inexistente o nó fonte é informado e a rota que utilizava esse nó é retirada da tabela. Caso a fonte possua uma rota alternativa armazenada ela pode usar, caso contrário o processo de descoberta deve ser rodado novamente.

Por ser reativo, esse protocolo tem um overhead relacionado às mensagens de controle muito baixo quando comparado aos proativos. Não existe a necessidade de inundações periódicas que gastam energia e ocupam a banda. Por outro lado o tempo de estabelecimento de uma rota pode ser bem maior, pois todos os caminhos não estão disponíveis sempre. Além disso, como todos os roteadores intermediários em uma rota são armazenados, as tabelas de rotas cacheadas podem se tornar extensas em redes grandes.

4.2.2. AODV

O protocolo AODV, On-Demand Distance Vector, pode ser tratado como uma extensão do DSDV para torná-lo reativo. Assim como no DSR, o processo de descoberta de rota só é iniciado quando a fonte não possui nenhuma rota válida para um destino e deseja enviar uma mensagem para ele.

A tabela de roteamento armazenada no nó é similar à do DSDV, possui destino, próximo salto, número de saltos e número de sequência. Cada nó possui um número de sequência associado que é usado para verificar a validade de um pedido ou resposta (se é mais antigo ou mais novo do que a informação presente atualmente), diminuindo situações de atualizações com informações obsoletas e prevenindo loops.

Um nó quando verifica que um vizinho seu está indisponível manda para rede uma mensagem avisando o ocorrido, fazendo com que rotas que usassem o vizinho sejam descartadas.

Por não armazenar todos os dispositivos no caminho de uma rota, como o DSDV, o protocolo possui tabela de roteamento ocupando menos espaço, sendo mais adequado para redes maiores.

4.3. Protocolos Híbridos

Protocolos híbridos buscam aproveitar os benefícios dos dois métodos, alternando entre o uso de roteamento proativo e reativo dependendo da necessidade.

4.3.1. ZRP

O ZRP, Zone Routing Protocol, estabelece o conceito de zonas para otimizar o uso dos protocolos existentes. Uma zona é determinada por um raio de distância (em número de saltos) de um nó. Para interagir com nós dentro de sua zona, uma fonte usa uma tabela de roteamento feita através de um protocolo proativo. Assim a rota é determinada imediatamente para nós próximos.

Quando a interação é feita com um nó fora de sua zona o processo de descobrimento de rota começa. O nó se comunica com nós na borda de sua zona, que, por sua vez buscam nas próprias zonas o nó destino. Se encontrarem a rota pode ser acessada instantaneamente (proativo). Caso contrário o processo de descoberta continua e os nós das bordas seguintes são comunicados.

5. Conclusão

É por causa dessa natureza, também, que surgem os vários desafios e obstáculos: elevado grau de instabilidade, gasto de bateria limitado, falta de escalabilidade, entre outros. Nesse cenário surgem os vários protocolos diferentes, cada um tentando resolver problemas não resolvidos pelos outros ou ser mais apropriado para determinadas condições. Por ainda não existir algoritmo perfeito, o campo das redes ad hoc ainda é altamente estudado e trabalhado.

Com o avanço da eletrônica e computação, dispositivos estão cada vez mais numerosos, resilientes, autônomos e precisando se interagir uns com os outros, e é por isso que as redes ad hoc continuarão tendo grande importância.

6. Perguntas

6.1. O que define uma rede Ad Hoc?

Uma rede ad hoc sem fio é um tipo de rede descentralizada que não depende de uma infraestrutura pré-existente. Nela os nós atuam tanto como hosts quanto como roteadores. Eles possuem livre movimentação no espaço, e podem entrar ou sair da rede à qualquer instante.

6.2. Qual a diferença entre protocolos proativos e reativos das redes Ad Hoc?

Em protocolos proativos todos os nós possuem a completa tabela de roteamento, e ela é periodicamente atualizada. Nos protocolos reativos um dispositivo só vai buscar uma rota quando quiser se comunicar com outro, diminuindo a necessidade de mensagens de controle.

6.3. Qual a função dos Multipoint Relays no protocolo OLSR?

Os MPRs são responsáveis por retransmitir as mensagens de controle. Eles são eleitos com o objetivo de minimizar o número de mensagens redundantes na rede, otimizando o processo de inundação.

6.4. Por que os protocolos OLSR e DSDV tem problemas de gasto energético? Como os protocolos reativos contornam esse problema?

Por enviarem mensagens periodicamente, buscando tabela de roteamento atualizada e igual em todos os nós da rede, os nós nos protocolos OLSR e DSDV estão funcionando constantemente, gastando bateria. Nos protocolos reativos essa mensagem periódica não existe, então nós só precisam se comunicar quando estão procurando uma rota nova (ou de fato transmitindo dados).

6.5. O que é um protocolo Ad Hoc Híbrido?

Protocolos híbridos buscam aproveitar os benefícios dos dois métodos, alternando entre o uso de roteamento proativo e reativo dependendo da necessidade. É o caso do ZRP, que usa o roteamento proativo para nós próximos e busca nós mais distantes através do roteamento reativo.

7. Bibliografia

1. R. Ramanathan e J. Redi, “A brief overview of ad hoc networks: challenges and directions”, IEEE Communications Magazine, vol. 40, nº 5, p. 20–22, maio 2002.

2. D. Niu, Y. Zhang, Y. Zhao, e M. Yang, “Research on Routing Protocols in Ad Hoc Networks”, in 2009 International Conference on Wireless Networks and Information Systems, 2009.

3. L. Chi, Z. Hao, C. Yao, Y. Zhang, K. Wang, e Y. Sun, “A Simulation and Research of Routing Protocol for Ad hoc Mobile Networks”, in 2006 IEEE International Conference on Information Acquisition, 2006.

4. N. Gupta e R. Gupta, “Routing protocols in Mobile Ad-Hoc Networks: An overview”, in INTERACT-2010, 2010.

5. Charles E. Perkins , Pravin Bhagwat, “Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers”, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom

6. T. Clausen and P. Jacquet, Eds., “Optimized Link State Routing Protocol (OLSR),” RFC Editor, Oct. 2003.

7. D. Johnson, Y. Hu, e D. Maltz, “The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4”, RFC Editor, fev. 2007.

8. C. Perkins, E. Belding-Royer, e S. Das, “Ad hoc On-Demand Distance Vector (AODV) Routing”, RFC Editor, jul. 2003.