Redes ad hoc
Introdução
Ad hoc é uma expressão em Latin que significa,
literalmente, “para isso”.
No idioma inglês, geralmente significa uma solução
designada para uma tarefa ou problema específico, não
generalizável e que não tem intenção de ser adaptado
para outros propósitos.
2
No contexto de ad hoc networks, ou redes
descentralizadas, a expressão se encaixa como um
verbo, descrevendo um método temporário, provisório ou
improvisado de resolver um determinado problema.
Em resumo, uma rede ad hoc se refere a uma tecnologia
que permite comunicação em rede de forma ad hoc, ou,
descentralizada.
3
São dois os principais tipos de redes ad
hoc: rede ad hoc sem fio/móvel, do inglês
wireless ad hoc network (WANET) ou
mobile ad hoc network (MANET); e rede ad
hoc veicular, do inglês vehicular ad hoc
network (VANET).
4
O que torna as redes ad hoc diferentes das redes
fisicamente conectadas é que todas as regras
habituais a respeito de topologias fixas, vizinhos
fixos e conhecidos, relacionamento fixo entre
endereço IP e localização e outras, são
repentinamente abandonas.
Os roteadores podem ir e vir, ou aparecer em novos
lugares de um momento para outro.
Foram propostos diversos algoritmos de roteamento para
redes ad hoc. Um dos mais interessantes é o algoritmo de
roteamento AODV, do inglês Ad hoc On-demand Distance
Vector.
Trata-se de um algoritmo semelhante ao de
roteamento com um vetor de distância de Bellman-
Ford, mas adaptado para funcionar em um ambiente
móvel e que considera a largura de banda limitada e
a baixa duração das baterias nesse ambiente.
7
Outra característica incomum é que é um
algoritmo por demanda, isto é, determina
uma rota até algum destino apenas
quando alguém deseja enviar um pacote
para esse destino.
8
Uma diferença crítica entre os algoritmos AODV e
Bellman-Ford é o fato de que os nós não transmitem
difusões periódicas contendo sua tabela de roteamento
inteira.
Essa diferença economiza largura de banda e também a
carga das baterias.
9
WANET
ou
MANET
10
Uma rede sem fio ou móvel ad hoc é um tipo
descentralizado de rede. Esse tipo de rede é chamado de
ad hoc porque não necessita de uma infraestrutura pré-
existente, como, por exemplo, roteadores em redes
cabeadas. A primeira vez que foi colocada em prática e
demostrado que era viável foi em 1999, mas o início de
sua pesquisa data do início da década de 1990.
11
Nela, cada nó participa do processo de roteamento, ao
encaminhar os dados para outros nós. A definição sobre
qual dos nós deve encaminhar os dados é feito de forma
dinâmica, baseando-se na conectividade de rede e no
algoritmo de roteamento utilizado.
12
No exemplo ilustrado pela Figura 1, o nó C não está
dentro do alcance do transmissor sem fio do nó A e o nó
A também não está dentro do alcance do transmissor
sem fio do nó C. Se A e C desejarem trocar pacotes,
terão que recrutar os serviços do nó B para encaminhar
os seus pacotes, já que B está em sobreposição com o
alcance de A e C.
13
Figura 1 - Estrutura simples de rede ad hoc sem fio com três nós.
14
Desafios e benefícios
Questões desafiadoras
● Se um hospedeiro pode se mover, como será possível descobrir
sua localização corrente na rede, de modo que seja possível lhe
transmitir dados.
● Como é realizado o endereçamento, dado que um hospedeiro
pode estar em uma entre muitas localizações possíveis.
● Se o hospedeiro se movimentar durante uma conexão, como os
dados serão roteados de modo que a conexão continue sem
interrupção.
15
Entre as vantagens, estruturas ad hoc proporcionam uma
rede de alta performance, não demandam uma
infraestrutura de alto custo monetário para operarem,
permite uso de espectro de frequência não licenciado,
proporcionam distribuição rápida de informações ao redor
dos remetentes e, em caso de falhas, não há
interferência no funcionamento da rede, visto que não há
roteadores centrais.
16
Requisitos técnicos
Uma rede ad hoc é formada por múltiplos nós conectados.
A conexão entre esses nós é influenciada pelos recursos de
cada um dos nós, como:
⬡ potência do transmissor;
⬡ potência de computação;
⬡ memória.
17
Aspectos de comportamento, como confiabilidade, também
influenciam. Esses recursos afetam diretamente a qualidade
entre as conexões, como:
⬡ largura da conexão;
⬡ perda de sinal;
⬡ interferência;
⬡ ruído.
18
Visto que conexões podem ser feitas e desfeitas a
qualquer momento, uma rede funcional deve ser capaz
de lidar com essa restruturação dinâmica,
preferencialmente de uma forma que seja conveniente,
eficiente, confiável, robusta e escalável. A rede deve
permitir que dois nós se comuniquem ao retransmitir
informação por meio de outros nós.
19
Aplicações
Devido a essa natureza descentralizada e falta de
complexidade, redes ad hoc, são aplicáveis à uma
gama de diferentes situações onde nós centrais, como
roteadores, não são confiáveis.
20
Além disso, esse tipo de rede é mais escalável em
comparação com redes sem fio gerenciadas por
rotadores.
Por exigirem pouquíssima configuração e serem rápidas
de tornar disponível, redes ad hoc são ótimas soluções
para situações de emergência ou crises, como desastres
naturais.
21
A aplicação mais comum de rede ad hoc é para
dispositivos móveis. Por dispensar infraestrutura e ser
autoconfigurável, permite que esses dispositivos se
conectem com o mínimo de fricção.
22
Smartphones
É possível utilizar um tipo específico de rede ad hoc,
denominado smartphone ad hoc networks (SPAN).
23
O que a diferencia de uma rede ad hoc móvel comum é
o uso de hardware pré-existente nesses dispositivos,
como Wi-Fi e Bluetooth, para atuar como conexão,
permitindo ligação de ponta a ponta com dispositivos
semelhantes.
24
Sua vantagem é dispensar o uso da rede celular das
operadoras de telefonia, roteadores sem fio ou
qualquer outra forma tradicional de infraestrutura de
rede.
25
Aplicação veicular VANET
Esse tipo é utilizado para a comunicação entre veículos e
equipamentos de beira de estrada.
26
A comunicação ocorre por meio de ondas de rádios,
sendo formadas de forma instantâneas conforme esses
veículos se movem ao longo da estrada.
27
Subproduto da VANET
São as redes ad hoc veiculares inteligentes, do inglês
Intelligent vehicular ad hoc networks (InVANETs), que por
meio de inteligência artificial auxiliam os veículos a se
comportar em situações de colisões com outros veículos
e acidentes em geral.
28
Outras aplicações que se beneficiam das facilidades das
redes ad hoc são as militares, principalmente por não
necessitar de infraestrutura e serem fáceis de operar, e o
âmbito de sensores, como naqueles presentes em
dispositivos de smart home, sinais de tráfego e até
mesmo robôs.
29
Roteamento em redes ad hoc
Redes ad hoc é uma estrutura de rede formada por
roteadores móveis.
30
Entre exemplos possíveis estão:
⬡ veículos militares em um campo de batalha;
⬡ uma frota de navios no mar;
⬡ trabalhos de emergência em calamidades;
⬡ um grupo de pessoas com notebooks.
Todos esses casos em um situações onde não há uma
infraestrutura prévia
31
Em todos esses casos e em outros, cada nó consiste em
um roteador e um host, normalmente no mesmo
dispositivo.
Em qualquer instante, uma rede ad hoc pode ser descrita
por um grafo dos nós, ou seja, roteadores e hosts.
32
Dois nós estão conectados, isto é, há um arco entre eles
no grafo, se puderem comunicar-se diretamente
utilizando seus sinais de rádio. Tendo em vista que um
dos dois pode ter um transmissor mais potente que o
outro, é possível que A esteja conectado a B, mas que B
não esteja conectado a A.
33
Algoritmo AODV
Figura 2, onde um processo do nó A deseja enviar um
pacote ao nó I. O algoritmo AODV mantém uma tabela
em cada nó, classificada por destino, fornecendo
informações sobre esse destino, inclusive a que vizinhos
enviar pacotes para alcançar o destino.
34
Supondo que A procure em sua tabela e não encontre
uma entrada correspondente a I. Será necessário
descobrir uma rota até I. Essa propriedade de
descoberta de rotas apenas quando surge a
necessidade é o que torna esse algoritmo por
demanda.
35
Figura 2 – Grafo de descoberta de rota utilizando algoritmo AODV.
36
As etapas demonstradas na Figura 2 são:
a) alcance da difusão de A;
b) depois de B e D receberem a difusão de A;
c) depois de C, F e G receberem a difusão de A;
d) depois de E, H e I receberem a difusão de A.
As setas mostram as rotas inversas possíveis.
37
Para localizar I, A constrói um pacote especial,
denominado Route Request, e o transmite por difusão.
O pacote alcança B e D, conforme a etapa a) da Figura
2.
38
De fato, a razão para B e D estarem conectados a A no
grafo é que eles podem receber comunicações de A. Por
exemplo, F não é mostrado como um arco para A, pois
não pode receber o sinal de rádio de A. Dessa forma, F
não está conectado a A.
39
Pacote Route Request
Mostrado na Figura 3, o pacote contém os endereços
de origem e destino, em geral seus endereços IP, que
identifica quem está sendo procurado.
40
Há também um campo ID da solicitação, um contador
local mantido separadamente por cada nó e
incrementado toda vez que um pacote Route Request é
transmitido. Juntos, os campos endereço de origem e ID
de solicitação identificam de forma exclusiva o pacote
Route Request, a fim de permitir que os nós descartem
quaisquer duplicadas que venham a receber.
41
Figura 3 – Formato de um pacote Route Request.
42
Além do contador ID de solicitação, cada nó também
mantém um segundo contador de sequência,
incrementado sempre que é enviado um pacote
Route Request, ou uma resposta ao pacote de outro
roteador.
43
Sua função é identificar novas rotas
a partir de rotas antigas. O quarto
campo da Figura 3 é o contador de
sequência de A; o quinto campo é o
valor mais recente do número de
sequência de I que A detectou,
sendo 0 se ele nunca foi detectado.
44
O último campo, contagem de saltos,
controlará o número de saltos que o
pacote efetuou. Seu valor inicial é 0.
Quando um pacote Route Request
chega a um nó, B e D no exemplo da
Figura 3, esse é processado conforme
as seguintes etapas:
45
i) O par, endereço de origem e ID de solicitação, é
procurado em uma tabela de histórico local para
verificar se essa solicitação já foi vista e processada.
Se for uma duplicata, será descartada e o
processamento será interrompido. Se não for uma
duplicata, o par será inserido na tabela de histórico,
para que duplicatas futuras possam ser rejeitadas, e o
processamento irá continuar;
46
ii) O receptor procura o destino em sua tabela de rotas. Se for
conhecida uma nova rota até o destino, será transmitido de
volta à origem um pacote Route Reply, informando como chegar
ao destino. Nesse caso, a palavra nota significa que o número
de sequência de destino armazenado na tabela de roteamento
é maior que ou igual ao número de sequência de destino
contido no pacote Route Request. Se for menor, isso quer dizer
que a rota armazenada é mais antiga que a rota anterior que a
origem tinha para o destino, e então a etapa iii será executada;
47
iii) Tendo em vista que o receptor não conhece uma nova rota para
o destino, irá incrementar o campo contagem de saltos e
retransmite o pacote Route Request. Também irá extrair os dados
do pacote e o armazena como uma nova entrada em sua tabela de
rotas inversas. Essas informações serão utilizadas para construir a
rota inversa, de forma que a resposta possa voltar à origem mais
tarde. As setas na Figura 2 são usadas para construir a rota
inversa. Também será inicializado um timer com a entrada de rota
inversa inserida mais recentemente. Se ela expirar, a entrada será
eliminada.
48
Os pontos B e D não sabem onde está I, e então cada um
deles cria uma entrada de rota inversa apontando de volta
para A, como demonstrado pelas setas na Figura 2, e
transmite o pacote com o campo contagem de saltos
definido como 1.
49
A difusão de B alcança C e D. C cria uma entrada para
ela em sua tabela de rotas inversas e retransmite. Em
contraste, D a rejeita como uma duplicata.
De modo semelhante, a difusão de D é rejeitada por B.
50
Porém, a difusão de D é aceita por F e G, sendo
armazenada, como mostra a etapa c) da Figura 2.
Depois de E, H e I receberem a difusão, o pacote Route
Request finalmente alcança um destino que sabe onde I
está, ou seja, o próprio I, como ilustra a etapa d) da
Figura 2.
51
É possível observar que, embora tenhamos mostrado
as difusões em três etapas discretas nesse caso, as
difusões de nós diferentes não são coordenadas de
nenhuma forma.
52
Em resposta à solicitação recebida, I constrói um pacote
Route Reply, como ilustra a Figura 4. Os campos
endereço de origem, endereço de destino e contagem de
saltos são copiados da solicitação recebida, mas o campo
número de sequência de destino é removido de seu
contador na memória.
53
O campo contagem de saltos é definido como 0. O campo
duração controla por quanto tempo a rota é válida. Esse
pacote é retransmitido por unidifusão para o nó de onde
veio o pacote Route Request, nesse caso, o nó G.
54
Então o pacote segue o caminho inverso até D e
finalmente até A. Em cada nó, o campo contagem de
saltos é incrementado, de forma que o nó possa ver a
que distância se encontra do destino, no caso I.
55
Figura 4 – Formato de um pacote Route Reply
56
Em cada nó intermediário no caminho de volta, o pacote é
inspecionado. O mesmo é inserido na tabela de roteamento local
como uma rota para I se uma ou mais das três condições a seguir
é satisfeita:
⦁ Não é conhecida nenhuma rota para I;
⦁ O número de sequência correspondente a I no pacote
Route Reply é maior que o valor encontrado na tabela de
roteamento;
⦁ Os números de sequência são iguais, mas a nova rota é
mais curta. 57
Desse modo, todos os nós na rota inversa aprendem a
rota para I de forma indireta, como um subproduto da
descoberta de rota de A. Os nós que receberam o
pacote Route Request original, mas que não estavam
no caminho inverso, ou seja, B, C, E, F e H no
exemplo, descartarão a entrada da tabela de rotas
inversas quando o timer associado expirar.
58
Em uma rede grande, o algoritmo gera muitas difusões,
até mesmo para destinos que estão próximos. Há,
entretanto, uma forma de reduzir número de difusões. O
campo prazo de validade do pacote IP é inicializado pelo
transmissor com o diâmetro esperado da rede e é
decrementado em cada salto.
59
Se alcançar 0, o pacote será descartado, ao invés de ser
transmitido por difusão. O processo de descoberta é
então modificado. Para localizar um destino, o
transmissor envia um pacote Route Request com o
campo prazo de validade definido como 1.
60
Se não houver nenhuma reposta dentro de um período de
tempo razoável, um outro pacote será enviado, dessa vez
com prazo de validade definido como 2. As tentativas
subsequentes utilizarão 3, 4, 5, etc. Desse modo, a
pesquisa será realizada por tentativa, primeiro no local, e
depois em anéis cada vez mais amplos.
61
Manutenção de rotas
Por ser possível mover ou desativas os nós, a topologia
pode mudar espontaneamente. Por exemplo, na Figura 2,
se G for desativado, A não perceberá que a rota esteve
usando para I não é mais válida. O algoritmo precisa ter a
possibilidade de lidar com esse problema.
62
Periodicamente, cada nó transmite por difusão uma
mensagem de “olá”. Cada um de seus vizinhos deve
responder a essa mensagem. Se não chegar nenhuma
resposta, o transmissor saberá que aquele vizinho saiu
de seu alcance e não está mais conectado a ele.
63
Essas informações são usadas para limpar rotas que não
estão mais ativas. Para cada destino possível, cada nó N
mantém o controle de seus vizinhos que enviaram um
pacote para esse destino durante os últimos T segundos.
Esses vizinhos são chamados de ativos de N para esse
destino.
64
N faz isso mantendo uma tabela de roteamento
organizada por destino e contendo o nó de saída a ser
utilizado para acessar o destino, a contagem de saltos até
o destino, o número de sequência de destino mais
recente e a lista de vizinhos ativos correspondente a esse
destino.
65
Figura 5 - Tabela de roteamento de D antes de G ficar inativo
66
Quando qualquer dos seus vizinhos se torna inacessível,
N verifica sua tabela de roteamento para ver quais
destinos tem rotas que utilizam o vizinho agora inativo.
Para cada uma dessas rotas, cada vizinho ativo é
informado de que sua rota que passa por N agora é
inválida e, portanto, deve ser limpa de suas tabelas de
roteamento.
67
Em seguida, os vizinhos ativos comunicam essa
informação a seus próprios vizinhos ativos e assim por
diante, recursivamente, até todas as rotas que
dependem do nó agora inativo serem retiradas de todas
as tabelas de roteamento.
68
Como uma ilustração de manutenção de rotas, iremos
considerar o exemplo anterior, mas agora com G
repentinamente desativado. A topologia alterada é
demonstrada na Figura 6.
69
Quando descobre que G está inativo, D observa sua
tabela de roteamento e vê que G foi usado nas rotas para
E, G e I. A união dos vizinhos ativos para esses destinos
é o conjunto {A, B}.
70
Figura 6 - Grafo depois que G fica inativo.
71
Considerações finais
Redes ad hoc, em geral conhecidas como MANET ou
WANET, são um tipo de rede sem infraestrutura e
continuamente autoconfigurável de dispositivos móveis
conectados de forma sem fio.
72
➢ Cada dispositivo é livre para se mover de maneira
independente em qualquer direção, assim sendo, sua
conexão com outros dispositivos irá mudar com
frequência.
➢ Cada um desses dispositivos deve encaminhar dados
mesmo que esse dado não tenha uso para si próprio,
portanto, cada dispositivos é de certa forma um
roteador.
73
➢ O principal desafio em construir uma rede ad hoc é
equipar cada dispositivo para continuamente manter a
informação necessária para rotear o tráfego de
maneira apropriada.
➢ Essas redes podem operar de forma independente ou
podem estar conectar a Internet.
74
➢ Podem conter um ou múltiplos e diferentes
transceptores entre os nós. Isso resulta em uma
topologia altamente dinâmica e autônoma.
➢ A principal vantagem de redes ad hoc é a sua natureza
ad hoc, onde os nós são móveis, ou seja, não há uma
infraestrutura fixa, tornando possível diversas
aplicações em áreas diferentes.
75
➢ Por ser descentralizada, esse tipo de rede é
tipicamente mais robusta que redes comuns
centralizadas, devido a forma multisaltos com que a
informação é retransmitida.
76
A Figura 7 ilustra a diferença entre uma rede com
protocolo de salto único e uma rede multisaltos.
Outras vantagens incluem:
❖ flexibilidade;
❖ Escalabilidade;
❖ baixo custo de administração.
77
Figura 7 - a) Roteamento de salto único; b) roteamento multisaltos
78
Com essas vantagens seguem algumas desvantagens
em performance de rede. Em virtude da falta de
infraestrutura fixa, variações de performance podem
ocorrer frequentemente.
79
Em referência as aplicações, são diversas as
possibilidades, indo desde sensores para captação de
informações ambientais, comunicação entre veículos,
equipamentos de tráfego, dispositivos de domésticos
inteligentes, troca de mensagens de ponta a ponta,
operações de resgate em desastres, robôs e assim por
diante.
80
Referências
Hoebeke, Jeroen, et al. "An overview of mobile ad hoc networks:
applications and challenges." Journal-Communications Network 3.3
(2004): 60-66.
Johnson, David B., and David A. Maltz. "Dynamic source routing in ad
hoc wireless networks." Mobile computing. Springer, Boston, MA, 1996.
153-181.
Li, Jinyang, et al. "Capacity of ad hoc wireless networks." Proceedings of
the 7th annual international conference on Mobile computing and
networking. ACM, 2001. 81
Maltz, David A., et al. "A performance comparison of multi-hop wireless ad hoc network
routing protocols." Proceedings of ACM MobiCom. Vol. 114. 1998.
Tanenbaum, Andrew S. "Network protocols." ACM Computing Surveys (CSUR) 13.4
(1981): 453-489.
Toh, C-K., et al. "Experimenting with an ad hoc wireless network on campus: insights and
experiences." ACM SIGMETRICS Performance Evaluation Review 28.3 (2000): 21-29.
Toh, Chai-Keong. Wireless ATM and Ad-Hoc Networks: Protocols and Architectures.
Springer Science & Business Media, 2012.
Zanjireh, Morteza M., Ali Shahrabi, and Hadi Larijani. "Anch: A new clustering algorithm for
wireless sensor networks." 2013 27th International Conference on Advanced Information
Networking and Applications Workshops. IEEE, 2013
82
