Protoclos para Redes Ad hoc

Resumo

O presente trabalho versa sobre Redes Ad Hoc. Nesta pesquisa, pretende-se discutir história, aplicações, dificuldades e principais protocolos. Esta investigação constitui do trabalho da disciplina de Redes de Computadores 2 (EEL879) e diante da sobrecarga de conteúdos existentes e descritos em diferentes padrões, foi observada a necessidade de organizar e descrever. Foram analisados artigos científicos e sites disponíveis pela internet que possibilitaram o crescimento do conhecimento da turma sobre este tema. Para pequenas redes de área local, as redes ad hoc podem ser mais baratas de serem construídas porque não exigem tanto hardware. No entanto, pode ser difícil gerenciar um grande número de dispositivos sem uma infraestrutura maior e mais concreta.

Introdução

Uma rede ad hoc é uma rede composta por dispositivos individuais que se comunicam diretamente. O termo implica construção espontânea ou improvisada, porque essas redes geralmente ignoram o hardware de gatekeeper ou o ponto de acesso central, como um roteador. Muitas redes ad hoc são redes locais em que computadores ou outros dispositivos estão habilitados para enviar dados diretamente um para o outro, em vez de passar por um ponto de acesso centralizado.

Motivação

História

Em 1970 temos o desenvolvimento da primeira tecnologia que posteriormente viria a se caracterizar como uma rede Ad Hoc, sendo financiada pela Defense Advanced Research Projects Agency (DARPA). A Packet Radio Network (PRNET), como era chamada, foi desenvolvida usando radiocomunicação comutada por pacotes para prover uma rede móvel no campo de batalha sem infraestrutura e em ambiente hostil (aviões, soldados e tanques). Posteriormente nos anos 80 o projeto expandiu para Survivable Adaptive Radio Network (SURAN). mantendo o mesmo propósito. O começo dos anos 90 marcam uma nova fase do desenvolvimento de redes Ad Hoc, com a popularização de Notebooks, o uso de softwares open-source e equipamentos de comunicação baseado em radiofrequência e infravermelho. Nessa época o termo Redes Ad Hoc é adotado pelo IEEE 802.11, além do expansão do uso dessa tecnologia para fins não militares.

Aplicações

A idéia de uma rede ad hoc geralmente não é familiar para os usuários finais que só viram pequenas redes residenciais ou comerciais que usam um roteador típico para enviar sinais sem fio para computadores individuais. No entanto, a rede ad hoc está sendo usada bastante em novos tipos de engenharia sem fio, embora até recentemente fosse uma idéia bastante esotérica. Por exemplo, uma rede móvel ad hoc envolve dispositivos móveis se comunicando diretamente entre si. Outro tipo de rede ad hoc, a rede veicular ad hoc, envolve a colocação de dispositivos de comunicação nos carros. Ambos são exemplos de redes ad hoc que usam uma grande coleção de dispositivos individuais para se comunicar livremente sem um tipo de estrutura de comunicação hierárquica ou de cima para baixo.

Classificações

Protocolos proativos de roteamento

Os protocolos de roteamento proativo também são chamados de protocolos de roteamento acionados por tabela. Neste, todos os nós mantêm a tabela de roteamento que contém informações sobre a topologia de rede, mesmo sem a necessidade.

Protocolos de roteamento reativo

O protocolo de roteamento reativo também é conhecido como protocolo de roteamento sob demanda. Nesse protocolo, a rota é descoberta ou criada sempre que necessário. Descoberta de rota: nesta fase, o nó de origem inicia o processo de descoberta de rota. O nó de origem inclui o endereço de destino, nós intermediários para o destino no pacote. Manutenção de rota: devido à falha na rota entre os nós, que ocorre devido à quebra do link. Portanto, a manutenção da rota é feita por mecanismo de reconhecimento.

Protocolo de roteamento híbrido

Protocolo de roteamento híbrido é a combinação de protocolos de roteamento proativo e reativo.



Vantagens e Desafios

A idéia de uma rede ad hoc geralmente não é familiar para os usuários finais que só viram pequenas redes residenciais ou comerciais que usam um roteador típico para enviar sinais sem fio para computadores individuais. No entanto, a rede ad hoc está sendo usada bastante em novos tipos de engenharia sem fio, embora até recentemente fosse uma idéia bastante esotérica. Por exemplo, uma rede móvel ad hoc envolve dispositivos móveis se comunicando diretamente entre si. Outro tipo de rede ad hoc, a rede veicular ad hoc, envolve a colocação de dispositivos de comunicação nos carros. Ambos são exemplos de redes ad hoc que usam uma grande coleção de dispositivos individuais para se comunicar livremente sem um tipo de estrutura de comunicação hierárquica ou de cima para baixo.
Vantagens para os usuários: Rede de alto desempenho. Nenhuma infraestrutura cara deve ser instalada. Distribuição rápida de informações pelo remetente. Nenhum ponto único de falha. Escalabilidade e restrições de bateria.
Porém, devido a sua natureza descentralizada e de topologia dinâmica, aparecem alguns problemas tanto na implementação quanto na utilização do protocolo.
Dificuldades de implementação: Todas as entidades de rede podem ser móveis, portanto, é necessária uma topologia muito dinâmica. As funções de rede devem ter um alto grau de adaptabilidade. Não há entidades centrais, portanto, as operações devem ser gerenciadas de maneira completamente distribuída. Como efeitos colaterais, o uso de espectro de frequência não licenciado, contribuindo para a poluição do espectro radioelétrico. Interferência.

Protocolos

DSDV (Destination-Sequenced Distance-Vector Routing)

Destination sequenced distance vector(DSDV) - ou Vetor de distância sequenciada de destino em tradução livre - é um protocolo pró-ativo adaptado do RIP(Routing Information Protocol) para o cenário de redes Ad Hoc onde a topologia está em constante mudança. Adicionando um atributo número de sequência para cada entrada da tabela de roteamento convencional do RIP.
O número de sequência (Sequence numbering) é utilizado para comparar as informações recebidas sobre a rede e distinguir informações obsoletas das novas e assim evitar problemas na rede como formação de loops.
Amortecimento (Damping): significa anunciar. Cada nó deve anunciar sua tabela de roteamento para seus vizinhos atuais por broadcasting. Os nós vizinhos sabem que há alterações na rede pelo Damping. As atualizações de roteamento são enviadas de duas maneiras: despejo completo e incremental. O despejo completo a tabela completa é enviada aos vizinhos. E o chamado incrementais somente as entradas são enviadas aos vizinhos.

Seleção de Rota
Se um roteador recebe novas informações, ele usa o número de sequência mais recente. Se o número de sequência for o mesmo que o da tabela, a rota com a melhor métrica será usada. Entradas obsoletas são aquelas que não são atualizadas há um tempo. Essas entradas, bem como as rotas que usam esses nós como próximos saltos, são excluídas.

Vantagens:
A disponibilidade de caminhos para todos os destinos na rede resulta em menos atraso necessário no processo de configuração do caminho. O método de atualização incremental com etiquetas de número de sequência marca os protocolos de rede com fio existentes adaptáveis às redes sem fio Ad-hoc. Portanto, todo protocolo de rede com fio disponível pode ser útil para redes sem fio ad hoc com menos modificações.

Desvantagens:
O DSDV requer atualizações regulares de suas tabelas de roteamento, que consomem energia da bateria e uma pequena quantidade de largura de banda, mesmo quando a rede está ociosa.
Sempre que a topologia da rede é alterada, é necessário um novo número de sequência antes da convergência da rede; portanto, o DSDV não é adequado para redes altamente dinâmicas ou em larga escala.

WRP (Wireless Routing Protocol)

O WRP é um protocolo para rede de rádio por pacote que utiliza um algoritmo para descobrir caminhos, não um algoritmo de caminhos mínimos que podem gerar problema de contagem até o infinito.
Esse protocolo é proativo, pois mantém quatro itens que são:
1) Uma tabela de distância
2) Uma tabela de roteamento
3) Uma tabela de custo de link
4) Uma lista de transmissão de mensagens (MRL) para evitar um loop de roteamento temporário.

O WRP usa a transmissão de mensagens de atualização para os nós vizinhos. Se o nó tiver atualização, deve enviar confirmações. Se o nó não tiver alterações na última atualização, envie um hello ocioso para garantir a conectividade. Um nó decide apenas se deseja atualizar ou não após receber a mensagem de atualização do vizinho. Este protocolo também procura o melhor caminho. Se um nó obtiver o melhor caminho, retransmitir essas informações para os nós originais. Depois que o nó original recebe uma confirmação, ele atualiza seu MRL.

Sua vantagem é o não acontecimento da contagem até o infinito, algo que pode acontecer em um algoritmo para achar o caminho mínimo como Bellman-Ford.

Sua desvantagem é complexidade para manter múltiplas tabelas demandando mais memória e processamento dos nós da rede(em comparação ao DSDV). Dessa forma o protocolo não é apropriado para grandes redes móveis, por serem altamente dinâmicas.

OLSR (Optimized Link State Routing Protocol)

O OLSR é um protocolo de roteamento proativo para redes móveis ad hoc. O protocolo herda a estabilidade de um algoritmo de estado do enlace e tem a vantagem de ter rotas disponíveis imediatamente quando necessário, devido à sua natureza proativa. O OLSR é uma otimização sobre o protocolo de estado de link clássico, adaptado para redes móveis ad hoc.

O OLSR minimiza a sobrecarga resultante da inundação do tráfego de controle usando apenas nós selecionados, chamados Retransmissores multiponto (MPRs), para retransmitir mensagens de controle. Essa técnica reduz significativamente o número de retransmissões necessárias para inundar uma mensagem para todos os nós na rede. Em segundo lugar, o OLSR exige que apenas o estado do enlace parcial seja inundado para fornecer rotas de caminho mais curto. O conjunto mínimo de informações sobre o estado do enlace equacionado é que todos os nós, selecionados como MPRs, DEVEM declarar os enlaces para seus seletores de PR. Informações topológicas adicionais, se presentes, podem ser alteradas, por exemplo, para fins de redundância.

Como o roteamento do estado do enlace exige que o banco de dados da topologia seja sincronizado na rede, o OSPF e o IS-IS executam a inundação da topologia usando um algoritmo confiável. Esse algoritmo é muito difícil de projetar para redes sem fio ad hoc, portanto o OLSR não se preocupa com a confiabilidade; simplesmente inunda os dados da topologia com frequência suficiente para garantir que o banco de dados não permaneça dessincronizado por longos períodos de tempo. A idéia dos retransmissores multiponto é minimizar a sobrecarga das mensagens de inundação na rede, reduzindo as retransmissões redundantes na mesma região. Cada nó na rede seleciona um conjunto de nós em sua vizinhança simétrica de 1 salto, que pode retransmitir suas mensagens. Esse conjunto de nós vizinhos selecionados é chamado de conjunto "Retransmissores multiponto " (MPR) desse nó. Os vizinhos do nó N que estão NÃO em seu conjunto MPR, recebem e processam mensagens de transmissão, mas não retransmitem mensagens de transmissão recebidas do nó N.

https://www.researchgate.net/figure/OLSR-Multipoint-Relays-selection_fig1_26488157
Figura 1 - Retransmissores multiponto, extraídas do trabalho Effects of Unstable Links on AODV Performance in Real Testbed.
Fonte: https://www.researchgate.net/figure/OLSR-Multipoint-Relays-selection_fig1_26488157


Formato e encaminhamento de pacotes

Uma especificação universal do formato de pacote e um mecanismo de inundação otimizado servem como mecanismo de transporte para todo o tráfego de controle OLSR.

Detecção de enlace

A detecção de enlace é realizado através da emissão periódica de mensagens HELLO as interfaces através das quais a conectividade é verificada. Uma mensagem HELLO separada é gerada para cada interface e emitida em correspondência. Como resultado temos um conjunto de links local, descrevendo links entre "interfaces locais" e "interfaces remotas" - ou seja, interfaces em nós vizinhos.

Detecção de vizinhos

Dada uma rede com apenas nós de interface única, um nó pode deduzir o conjunto vizinho diretamente das informações trocadas como parte da detecção de enlace: o "endereço principal" de um único nó de interface é, por definição, o endereço da única interface nesse nó.

Em uma rede com vários nós de interface, são necessárias informações adicionais para mapear endereços de interface para endereços principais (e, portanto, para nós). Esta informação adicional é adquirida através de mensagens de declaração de interface múltipla (MID).

https://tools.ietf.org/html/rfc3626
Figura 2 - Mensagem HELLO.
Fonte: https://tools.ietf.org/html/rfc3626


HTime
Este campo especifica o intervalo de emissão HELLO usado pelo nó nesta interface específica, ou seja, o tempo antes da transmissão do próximo HELLO (esta informação pode ser usada em detecção avançada de enlace).

Willingness
Este campo especifica a disposição de um nó para transportar e encaminhar tráfego para outros nós.

Link Code
Este campo especifica informações sobre o link entre a interface do remetente e a seguinte lista de interfaces vizinhas. Também especifica informações sobre o status do vizinho. Os códigos de link, não conhecidos por um nó, são descartados silenciosamente.

Link Message Size
O tamanho da mensagem do link, contado em bytes.

Neighbor Interface Address
O endereço de uma interface de um nó vizinho.

AODV (Ad hoc On-Demand Distance Vector Routing)

O protocolo AODV, On-Demand Distance Vector, tem como objetivo ser leve e adaptativo, utilizando menos banda e espaço e minimizando o processamento nos nós a partir da realização de menos cálculos no algoritmo. Dessa forma, o protocolo se mostra um ótimo candidatos para dispositivos móveis por suas economias.

O AODV consegue realizar roteamento uni e multicast e é um protocolo reativo, sendo considerado uma combinação do DSR e do DSDV. Sua principal diferença para o DSR é o fato dos saltos da rota serem descobertas a partir dos nós intermediários que escolhem o endereço do próximo salto, característica do DSDV, que diferencia do DSR por este guardar todos os saltos em sua tabela. Dessa forma, o protocolo consegue diminuir a sobrecarga da redes pois cada nó não precisa ter a tabela contendo todo o caminho até o nó, além de realizar o descobrimento da rede sob demanda a partir da manutenção da rota e do descobrimento da rota.

No AODV, se o nó que deseja uma conexão transmite uma solicitação (RREQ). O nó de origem transmite um RREQ pela rede como o processo de descoberta de rota. Se um nó de destino receber RREQ, ele enviará uma resposta de rota (RREP). Se, em caso de falha, retransmitir o RREQ. Se o nó descartar RREQ que já possuía.

DSR (Dynamic Source Routing)

O DSR é um protocolo reativo para iniciar o processo de descoberta de rotas por fonte. O nó de origem decide apenas a rota da origem para o destino e os nós intermediários também. É um protocolo sem aviso no qual nenhuma mensagem HELLO é trocada entre nós para notificá-los de seus vizinhos na rede. O Protocolo foi pensando para ter pouca sobrecarga de processamento e ainda assim reagir de forma rápidas as mudanças na topologia da rede, além de não se utiliza de pacotes periódicos como outros protocolos. O DSR fornece alta reatividade para ajudar a segurar a entrada dos pacotes apesar da movimentação dos nós e outra mudanças na rede.

Para conseguir garantir o funcionamento do protocolo ele é composto de dois mecânicos que possibilitam o descobrimento e a manutenção de rotas na rede, o descobrimento de rota e a manutenção de rota.

O descobrimento de rota é o mecanismo usando quando um nó A nao conhece caminho para o nó B e dessa forma A precisar obter essa rota. Enquanto que a manutenção da rota é usada quando o nó A está enviando pacotes para o nó B e acontece alguma modificação da topologia de forma que a rota inicial não funciona mais, nessa situação A pode usar outra rota que conhece D ou rodar novamente o descobrimento de Rota.

Os dois mecanismos acontecem sob-demanda, esse fato somado a não utilização de envios de pacotes intermediários possibilita que o overhead de pacotes tenda a zero nas situações onde todos os nós são aproximadamente estacionários entre si e todas as rotas que são necessárias para comunicação já foram descobertas.

À medida que os nós começam a se mover e a comunicação dos pacotes mudam, a sobrecarga dos pacotes de roteamento escalam automaticamente somente para o que é necessário para as conexões em uso. As mudanças na topologia da rede não afetam o protocolo em casos que essas modificações não afetem as conexões em uso.

ZRP (Zone Routing Protocol)

O protocolo ZRP é um protocolo híbrido que possui parte proativa e parte reativa, sendo desenvolvido para acelerar o envio e diminuir a sobrecarga de processamento selecionando a forma mais eficiente de roteamento pela rede.

O ZRP define o conceito de zona de roteamento sendo uma área A de um nó N é definido sendo a menor distância em saltos de um nó N a todos os nós da Área A respeitando o máximo definido que é definido como o Raio de Zona. Essa área pode ser variável dentro do protocolo podendo ser manualmente definida em casos de uma rede com poucas modificações. Dentro dessa área é utilizado um protocolo pró-ativo para guardar uma tabela com os caminhos para os nós da Zona.

No caso do destino estar fora da zona do nó A, um protocolo reativo valida as zonas vizinhas se o destino está dentro dessas zonas e assim que o destino é encontrado, é realizado o protocolo pró-ativo dentro da zona do destino ou é utilizado a rota armazenada da tabela daquela zona.

Dessa forma, o protocolo diminui o atraso causado pelo processo de descoberta de rota dos protocolos reativos e diminui a sobrecarga de processamento realizados o algoritmo para definir a tabela da rota em uma pequena área apenas.

O tamanho da zona pode ser definido dinamicamente ou manualmente, o melhor tamanho de zona a ser escolhido vai depender das características da rede, sendo uma rede esparsa ou dena e se ela se move rápido ou lentamente.

Considerações Finais

Para pequenas redes de área local, as redes ad hoc podem ser mais baratas de serem construídas porque não exigem tanto hardware. No entanto, pode ser difícil gerenciar um grande número de dispositivos sem uma infraestrutura maior e mais concreta. Além de que o protocolo reativo demanda muito tempo para determinar a rota, o proativo ocupa espaço na banda durante a troca de informações além de necessitar de processamento e memória do dispositivo móvel. Apenas observando essas grandes desvantagens entre as duas principais classificações de protocolos é possível perceber que existe muito a ser estudado e trabalhado. Grupos de pesquisa estão procurando maneiras de habilitar funcionalidades de rede mais animadoras com essas redes ponto a ponto.

Perguntas

1) O que são redes Ad Hoc?

São redes descentralizadas onde não é necessária uma infra-estrutura de comunicações definida. São composta por dispositivos individuais que se comunicam diretamente. O termo implica construção espontânea ou improvisada.

2) O que são protocolos proativos? Cite ao menos uma vantagem.

Nos protocolos proativos, são enviadas informações sobre a topologia da rede em intervalos fixos de tempo, com o objetivo de manter as tabelas de roteamento atualizadas. Não há atraso na descoberta de rotas.

3) O que são protocolos reativos? Cite ao menos uma vantagem.

Nos protocolos reativos, uma rota até um determinado destino será descoberta apenas quando requisitada e esta não constar na tabela de roteamento atual. Menor quantidade de informação armazenada, dependendo da rede pode ter menos troca de mensagens de controle, possível menor gasto de energia.

4) Para que server retransmissores multiponto (MPR) no protocolo OLSR?

A idéia dos retransmissores multiponto é minimizar a sobrecarga das mensagens de inundação na rede, reduzindo as retransmissões redundantes na mesma região. Cada nó na rede seleciona um conjunto de nós em sua vizinhança simétrica de 1 salto, que pode retransmitir suas mensagens.

5) Para que servem os números de seqüência implementados no protocolo DSDV?

É utilizado para comparar as informações recebidas sobre a rede e distinguir informações obsoletas das novas e assim evitar problemas na rede como formação de loops.

Bibliografia

UFRJ - Redes de Computadores II - Segundo semestre de 2019

Alunos: Renan Neri e Ary Andrade

Tema: Redes Ad Hoc

Este trabalho foi totalmente produzido pelos autores que declaram não terem violado os direitos autorais de terceiros, sejam eles pessoas físicas ou jurídicas. Havendo textos, tabelas e figuras transcritos de obras de terceiros com direitos autorais protegidos ou de domínio público tal como idéias e conceitos de terceiros, mesmo que sejam encontrados na Internet, os mesmos estão com os devidos créditos aos autores originais e estão incluídas apenas com o intuito de deixar o trabalho autocontido. O(s) autor(es) tem(êm) ciência dos Artigos 297 a 299 do Código Penal Brasileiro e também que o uso do artifício de copiar/colar texto de outras fontes e outras formas de plágio é um ato ilícito, condenável e passível de punição severa. No contexto da Universidade a punição não precisa se restringir à reprovação na disciplina e pode gerar um processo disciplinar que pode levar o(s) aluno(s) à suspensão;