Protocolo de Encaminhamento
Route Alternating Multipath AODV (RAM-AODV)
Justimiano Andrade Alves
Dissertação para obtenção do Grau de Mestre em
Engenharia electrotécnica e de computadores
Júri:
Presidente: Professor Nuno Cavaco Gomes Horta
Orientador: Professor António Manuel Raminhos Cordeiro Grilo
Co-orientador: Professor Paulo Rogerio Barreiros d'Almeida Pereira
Vogal: Professor Carlos Manuel Ribeiro Almeida
Abril 2012
I
II
Resumo
As redes móveis ad-hoc (Mobile Ad-hoc Networks - MANET) e a proliferação de dispositivos portáteis com
capacidade de comunicação sem fios têm incentivado a investigação na área dos protocolos de
encaminhamento. Devido à liberdade de movimento dos nós, à sua configuração imprevisível, às
limitações de autonomia dos dispositivos e da largura de banda da rede, as falhas de comunicação podem
tornar-se comuns neste tipo de redes.
De modo a ultrapassar estas limitações, e com os objectivos de determinar vários percursos, minimizar a
sobrecarga da rede e maximizar a largura de banda, neste trabalho implementou-se um protocolo Route
Alternating Multipath AODV (RAM-AODV) com encaminhamento multi-percurso. O protocolo
implementado possibilita a descoberta de múltiplos percursos entre os nós de origem e de destino, como
também permite especificar o número de percursos parcialmente disjuntos a serem descobertos, o que
permite reduzir significativamente a sobrecarga da rede. À semelhança do protocolo Ad-hoc On-Demand
Distance Vector (AODV), no protocolo RAM-AODV é feita monitorização local dos vizinhos e são
descartados pedidos redundantes Route Request (RREQ) nos nós intermédios. Para comparar o
desempenho do protocolo desenvolvido com o protocolo AODV foram realizadas várias simulações para
diferentes cenários, onde o protocolo implementado mostrou ter um melhor desempenho do que o
protocolo AODV. Os resultados obtidos mostram-nos que o protocolo desenvolvido é eficiente na redução
do número de pacotes perdidos, no tempo de atraso na comunicação e na utilização da largura de banda.
Em todos os cenários em que o protocolo foi testado, revelou ser mais eficiente do que o protocolo AODV.
III
IV
Abstract
The Mobile Ad-hoc Networks (MANET) and the proliferation of the portable devices capable of wireless
communication have encouraged the research in the area of communication protocols. Due to the freedom
of movement of the nodes, the undefined network’s configuration, the limitations of the devices’
autonomy and of the network’s bandwidth, the communication failures are very common in these
scenarios.
In order to overcome these limitations, as well as with the goals of determining various routes and
minimizing overhead and maximizing the network’s bandwidth, an RAM-AODV protocol (Route
Alternating Multipath AODV - RAM-AODV) with multi-path routing functionality was implemented in this
thesis project. The implemented protocol enables the discovery of multiple paths between the origin and
the destination nodes, but also offers the possibility of specifying the number of partially disjoint paths to
be discovered, which significantly reduces the network’s overhead. The similarities of the developed
protocol with the Ad-hoc On-Demand Distance Vector (AODV) protocol are the local monitoring and the
discarding of the duplicated Route Requests (RREQ) at the intermediate nodes. In order to compare the
performance of the developed protocol with the AODV protocol, several simulations for different
scenarios were performed, where the implemented protocol showed to have better performance than
AODV protocol. The results show us that the developed protocol is effective in reducing of number of the
lost packets and the delivery delay, while improving the bandwidth usage. In all the scenarios in which the
RAM-AODV was tested it showed to have a much better performance than the AODV.
V
VI
Índice
1 Introdução ................................................................................................................................................ 2
1.1 Enquadramento .............................................................................................................................. 2
1.1.1 Arquitectura das redes MANET ....................................................................................... 2
1.1.2 Implementação das redes MANET ................................................................................. 4
1.2 Motivação .......................................................................................................................................... 6
1.3 Objectivos .......................................................................................................................................... 7
1.4 Estrutura da tese ............................................................................................................................ 8
2 Protocolos de encaminhamento para as redes MANET ....................................................... 10
2.1 Protocolo de encaminhamento com percurso único para as redes MANETs ...... 10
2.1.1 Aspectos gerais.................................................................................................................... 10
2.1.2 AODV – Ad-hoc On-Demand Distance Vector .......................................................... 12
2.1.3 DSR - Dynamic Source Routing ..................................................................................... 13
2.1.4 OLSR – Optimized Link State Routing ........................................................................ 13
2.1.5 DSDV - Destination-Sequenced Distance-Vector ................................................... 16
2.1.6 ZRP - Zone Routing Protocol .......................................................................................... 17
2.1.7 Considerações finais e conclusão ................................................................................. 20
2.2 Protocolos de encaminhamento multi-percurso para as redes MANET ............... 21
2.2.1 Aspectos gerais.................................................................................................................... 21
2.2.2 Ad-hoc On-Demand Multipath Distance Vector Routing (AOMDV) ............... 22
2.2.3 Optimized AOMDV routing protocol (OAOMDV) ................................................... 24
2.2.4 Mobility Prediction Ad-hoc on-demand multipath distance vector (MP-
AOMDV) .................................................................................................................................................. 28
2.2.5 New Multipath Node-Disjoint routing based on AODV protocol (NMN –
AODV) 31
2.2.6 Multipath Optimized Link State Routing Protocol (MP-OLSR) ..................... 32
2.2.7 Considerações finais e conclusão ................................................................................. 34
3 Route Alternating Multipath AODV (RAM-AODV) ................................................................. 38
3.1 Formato das mensagens ........................................................................................................... 38
3.2 Estuturas de dados ..................................................................................................................... 40
3.3 Gestão de múltiplos percursos .............................................................................................. 42
3.4 Manutenção dos percursos ..................................................................................................... 43
3.5 O funcionamento do protocolo RAM-AODV ..................................................................... 44
VII
3.5.1 Processamento do RREQ ................................................................................................. 44
3.5.2 Processamento do pacote RREP ................................................................................... 45
3.5.3 Ilustração do funcionamento do protocolo através de um cenário. ............... 46
4 Resultados de Simulação .................................................................................................................. 48
4.1 Método de recolha de dados ................................................................................................... 48
4.2 Cenário 1 - Topologia estática da rede. .............................................................................. 52
4.2.1 Teste de variação da densidade de rede ................................................................... 53
4.2.2 Teste de variação do intervalo de envio dos pacotes ........................................... 58
4.3 Cenário 2 – Topologia dinâmica da rede ............................................................................ 61
5 Conclusão ............................................................................................................................................... 66
6 Bibliografia ............................................................................................................................................ 70
Apêndice A ...................................................................................................................................................... 74
viii
Lista figuras
Figura 1-1: Rede MANET com 5 nós [Fonte: [1]] ....................................................................................................................... 2
Figura 1-2: Rede MANET com 7 Interfaces. [Fonte: [1]] ......................................................................................................... 3
Figura 1-3: MANET: Assimetria entre as interfaces. [Fonte: [1]] ........................................................................................ 4
Figura 2-1: Categoria dos protocolos de encaminhamento para as redes MANET. ................................................. 11
Figura 2-2: Arquitectura do protocolo ZRP. [Fonte: [11]] .................................................................................................. 18
Figura 2-3: Zona de encaminhamento do nó S. [Fonte: [12]] ............................................................................................ 18
Figura 2-4: Zona de encaminhamento do nó. [Fonte: [12]] ................................................................................................ 19
Figura 2-5:Zona de encaminhamento do nó T. [Fonte: [12]] ............................................................................................. 19
Figura 2-6:Processo de descoberta de rotas – AOMDV. ....................................................................................................... 23
Figura 2-7:Processo de definição do percurso inverso – protocolo OAOMDV. .......................................................... 24
Figura 2-8: Formato do pacote RREQ do OAOMDV. ............................................................................................................... 25
Figura 2-9: Formato da mensagem RREP_ACK do protocolo OAOMDV ........................................................................ 26
Figura 2-10:Processo de definição de percurso directo - protocolo OAOMDV. ......................................................... 26
Figura 2-11:Processo de definição do percurso omitido - protocolo OAOMDV. ....................................................... 27
Figura 2-12:Processo de cálculo de nós disjuntos MP-AOMDV. ....................................................................................... 29
Figura 2-13:O algoritmo Dijkstra de multi-percuros. [fonte: [15]] ................................................................................. 33
Figura 2-14: Algoritmo Dijkstra com fp (c) = fe (c) = 2c. Na primeira figura foram calculados 3 percursos e
na segunda figura foram calculadas 10 percursos [fonte: [15]]. .......................................................................... 33
Figura 2-15: processo de descoberta de rota pelo nó F. ....................................................................................................... 34
Figura 3-1:Formato do pacote Route Request – RREQ. ......................................................................................................... 39
Figura 3-2:Formato do pacote Route Reply – RREP. ............................................................................................................... 39
Figura 3-3:Formato do pacote Route Error - RRER. ............................................................................................................... 39
Figura 3-4: Formato do pacote Route Reply Acknowledgement - RREP_ACK. ............................................................. 40
Figura 3-5: Formato da tabela de encaminhamento. ............................................................................................................. 40
Figura 3-6:Formato da entrada da tabela de encaminhamento. ...................................................................................... 41
Figura 3-7:Formato da lista de próximos saltos. ..................................................................................................................... 41
Figura 3-8:Formato da tabela de vizinhos processados. ...................................................................................................... 42
Figura 3-9:Formato da tabela de RREQ Pendentes. ............................................................................................................... 42
Figura 3-10:Tabela de Contador de percurso para o nó de destino. ............................................................................... 43
Figura 3-11:Fluxograma do algoritmo implementado no nó de destino para processar o pacote RREQ. ..... 45
Figura 3-12: Processo de descoberta de rota do protocolo RAM-AODV. ...................................................................... 47
Figura 4-1: Exemplo de uma topologia estática lógica e genérica da rede. ................................................................. 53
Figura 4-2: Valores médios do atraso extremo-a-extremo em redes estáticas, com número de nós variável.
............................................................................................................................................................................................................ 54
Figura 4-3: Valores médios do jitter em redes estáticas, com número de nós variável. ........................................ 55
ix
Figura 4-4: Valores de taxa média dos pacotes recebidos em redes estáticas, com número de nós variável.
............................................................................................................................................................................................................ 56
Figura 4-5: Valores médios do débito em redes estáticas, com número de nós variável. ..................................... 57
Figura 4-6: Valores médios do atraso extremo-a-extremo em redes estáticas, com intervalo de envio de
pacotes variável. ......................................................................................................................................................................... 58
Figura 4-7: Valores médios do jitter em redes estáticas, com o intervalo de envio de pacotes variável........ 59
Figura 4-8: Valores de taxa média de pacotes recebidos em redes estáticas, com intervalo de envio de
pacotes variável. ......................................................................................................................................................................... 60
Figura 4-9: Valores médios do débito em redes estáticas, com intervalo de envio de pacotes variável. ....... 60
Figura 4-10: Valores médios do atraso extremo-a-extremo em redes dinâmicas, com velocidade de
movimento dos nós variável. ................................................................................................................................................ 63
Figura 4-11: Valores médios do jitter em redes dinâmicas, com velocidade de movimento dos nós variável.
............................................................................................................................................................................................................ 63
Figura 4-12: Valores de taxa média de pacotes recebidos em redes dinâmicas, com velocidade de
movimento dos nós variável. ................................................................................................................................................ 64
Figura 4-13: Valores médios do débito em redes dinâmicas, com velocidade de movimento dos nós
variável. .......................................................................................................................................................................................... 65
x
Lista de tabelas
Tabela 2-1: Entrada da tabela de encaminhamento do protocolo OAOMDV. ............................................................. 25
Tabela 2-2: Estrutura da Lista de percursos do protocolo OAOMDV. ............................................................................ 25
Tabela 4-1: Definição dos parâmetros constantes para os dois cenários. .................................................................... 49
Tabela 4-2: Atributos e valores por omissão. ............................................................................................................................ 50
Tabela 4-3: Definição dos parâmetros para o teste 1. ........................................................................................................... 53
Tabela 4-4:Definição dos parâmetros para o cenário da mobilidade............................................................................. 62
xi
xii
Acrónimos
ABR - Associativity Based Routing
AODV – Ad-hoc On-Demand Distance Vector
AODV-DM – Ad-hoc On-Demand Distance Vector - Decoupled Multipath
AODVM - Ad-hoc On-demand Distance Vector Multipath Routing Protocol
AOMDV - Ad-hoc On-Demand Multipath Distance Vector
API - Application Programming Interface
ATM - Asynchronous Transfer Mode
BRP - Bordercast Resolution Protocol
CGSR - Cluster Gateway Switch Routing
DV – Distance Vector
DSDV - Destination-Sequenced Distance Vector
DSR - Dynamic Source Routing
FSR - Fisheye State Routing
IARP - Intrazone Routing Protocol
IERP - Interzone Routing Protocol
LNH -List next hops
LS – Link State
IMANET - Internet Based Mobile Ad-hoc Networks
InVANETs - Intelligent Vehicular Ad-hoc Networks
MANET - Mobile Ad-hoc Network
MMDV - Multipath and MPR based AODV routing protocol
MDA - Multipath Dijkstra Algorithm
MOLSR - Multicast Optimized Link State Routing
xiii
MPR - Multipoint Relay
MP-AOMDV - Mobility Prediction Ad-hoc On-Demand Multipath Distance Vector
MP-DSR - Multi-Path DSR routing protocol
MP-OLSR - Multipath Optimized Link State Routing
NMN-AODV - New Multipath Node-Disjoint Routing Based on AODV Protocol
NDP - Neighbor Discovery Protocol
NS-2 – Netowrk Simulator 2
NS-3 – Network Simulator 3
OAOMDV- Optimized Ad-hoc On-Demand Multipath Distance Vector
OLSR - Optimized Link State Routing
QOLSR - Quality of Service for Ad-hoc Optimized Link State Routing Protocol QoS - Quality of service
RAM-AODV - Route Alternating Multipath AODV
RREP_ACK – Route Reply Acknowledgement
RREP – Route Reply
RREQ - Route Request
SSA - Signal Stability-Based Adaptive Routing Protocol
TPN - Table processed neighbors
TC - Topology Control
TORA - Temporally Ordered Routing Algorithm
VANETs - Vehicular ad-hoc Networks
WMN - Wireless Mesh Network
WSN – Wireless Sensor Network
WRP - Wireless Routing Protocol
xiv
ZRP - Zone Routing Protocol
1
2
1 Introdução
1.1 Enquadramento
As redes móveis ad-hoc (Mobile Ad-hoc Networks – MANETs), são redes auto-configuráveis que se formam
espontaneamente a partir de um conjunto de dispositivos móveis sem fios. A rede funciona de uma forma
autónoma, ou seja, sem qualquer infra-estrutura fixa pré-existente ou controlo centralizado. Nesta rede,
dois dispositivos (também designados por nós) podem comunicar directamente, desde que estejam
dentro do alcance rádio um do outro. Além de efectuarem uma comunicação directa (comunicação one-
hop), os dispositivos cooperam mutuamente para garantir comunicação indirecta (comunicação multi-
hop) entre os dispositivos que não se conseguem alcançar directamente, ou seja, que estão fora do alcance
rádio. Nestes tipos de redes as ligações são definidas pelos raios de comunicação de cada nó da rede. O
raio de alcance máximo dos nós é influenciado pelo tipo de equipamento de que dispõem e por efeitos de
propagação e interferência. Quando dois dispositivos (nós) se afastam, ficando fora do alcance de
comunicação um do outro, ocorre uma falha de ligação. Devido à liberdade de movimento dos terminais, a
topologia está constantemente em alteração e de forma imprevisível. No entanto, a sua rápida instalação e
configuração simplificada, fazem com que este tipo de rede seja indispensável em situações de catástrofe,
emergência ou operações militares, onde à partida não existe uma infra-estrutura de rede montada. Na
Figura 1-1 está exemplificada uma rede com 5 interfaces MANET, em que a área da cobertura de cada um
dos nós está representada por um disco simples de raio fixo. Indica-se a com cor cinza a área de cobertura
da zona rádio de cada interface, correspondendo as áreas mais escuras à sobreposição de áreas de
cobertura. Nesta figura a interface N1 está fora do alcance rádio da interface N5, portanto, a rede tem que
suportar a funcionalidade da comunicação multi-hop descrita previamente.
Figura 1-1: Rede MANET com 5 nós [Fonte: [1]]
1.1.1 Arquitectura das redes MANET
Dois tipos de cenários de utilização das redes MANET podem ser distinguidos. No primeiro cenário, a rede
MANET está conectada pelo menos a uma rede externa (normalmente a Internet) que requer uma gama
de endereços configurados, ou seja, o uso de endereços ou prefixos derivados de um prefixo global. Um
exemplo típico desta configuração são as redes públicas sem-fios de pontos de acesso WLAN fixos
espalhados, que fazem parte de uma rede MANET e que funcionam como routers para utilizadores móveis.
No segundo cenário, as redes MANETS são autónomas, ou seja, não possuem qualquer nó que impõe o uso
de prefixos ou endereços derivados de um prefixo global. Exemplos típicos de redes MANET autónomas
3
são as redes privadas ou temporárias, instaladas em áreas onde não existe uma infra-estrutura de
telecomunicações (exemplo redes de emergências para recuperação de acidentes, redes de sala de
conferências, etc.). Para ambos os cenários, a abordagem do ponto de vista da arquitectura é semelhante.
Faz-se o estudo da arquitectura MANET, a começar por estudar algumas características importantes das
interfaces MANET, tais como: Interfaces semi-broadcast1, largura de banda partilhada, terminal
escondido e conectividade assimétrica. Para fins ilustrativos considera-se a interface N3 da Figura 1-2,
onde se pode ver que a sua zona de cobertura representada pelo disco com a cor cinzento-escuro alcança a
interface N2 e N4 (i.e. as suas transmissões podem ser recebidas pela interface N2 e N4), no entanto não é
recebida pelas interfaces N1 e N5. Isto indica que as interfaces N3, N2 e N4 partilham a mesma ligação, no
entanto têm uma visão diferente da rede. O nó N3 considera que faz parte da mesma ligação com a
interface N2 e N4, enquanto a interface N4 considera que partilha a mesma ligação com N3 e N5. Esta
característica é designada por interfaces semi-broadcast com vizinhos não transitivos. No entanto, a
transmissão da interface N3 pode ser detectada pelas interfaces N1 e N5, mas esta não é descodificada
correctamente. Isto irá provocar interferência com as possíveis transmissões recebidas das interfaces N0
e N6.
Figura 1-2: Rede MANET com 7 Interfaces. [Fonte: [1]]
Dependendo da tecnologia de rádio utilizada (por exemplo IEEE 802.11), as interfaces MANET podem
interferir umas com as outras. Considerando a Figura 1-2, quando N3 está a transmitir, N2 e N4 não
podem transmitir simultaneamente porque a largura de banda disponível é partilhada entre estas
interfaces MANET [2].
A interface N2 transmite para a interface N3. O N4 não detecta esta comunicação e considera o meio livre
e transmite dados para o N3. Como este está em comunicação com o N2, resulta em uma colisão.
Considera-se que o terminal N2 está escondido em relação ao terminal N4.
Nas redes tradicionais é comum assumir que a conectividade entre os nós vizinhos é simétrica, no entanto
nas redes MANET o mesmo não se verifica. Por exemplo, considerando a rede MANET da Figura 1-3, em
1 Semi-broadcast- interfaces que partilham a mesma ligação, mas não partilham a mesma visão da rede.
4
que por alguma razão (potência de transmissão, largura da antena …) a interface N1 tem uma área de
cobertura muito ampla de modo que as suas transmissões são recebidas pela interface MANET N2. A
interface N2 tem um raio de cobertura menor, tal que as suas transmissões não são recebidas pela
interface N1, portanto o N2 considera o N1 como seu vizinho, uma vez que consegue receber as suas
transmissões. No entanto o N1 não o considera como vizinho, por não ser possível receber as suas
transmissões. Esta é uma das características das interfaces MANET designada por conectividade
assimétrica.
Figura 1-3: MANET: Assimetria entre as interfaces. [Fonte: [1]]
As interfaces MANET formam um gráfico dinâmico e arbitrário entre si. Isto indica que a rede de uma
interface MANET varia ao longo do tempo, quer por razoes da mobilidade dos nós ou devido a factores
ambientais que afectam a área da cobertura das interfaces [1].
1.1.2 Implementação das redes MANET
A utilização das redes MANET oferece várias vantagens, que podem variar consoante a sua
implementação. Apresentam-se de seguida os tipos de implementação das redes MANET:
Vehicular Ad-hoc Network (VANET) - são casos particulares, onde as redes MANET são
utilizadas para comunicações entre veículos e comunicações entre veículos e equipamentos
instalados nas auto-estradas. O objectivo destas redes é de proporcionar segurança e conforto aos
viajantes. Para garantir o seu funcionamento, é incorporado dentro de cada veículo um
dispositivo electrónico através do qual é concebida a rede. Esta rede funciona perfeitamente na
ausência de qualquer infra-estrutura fixa. Cada viatura equipada com um dispositivo VANET
funciona como um nó da rede e está capacitada para receber e retransmitir informações de/para
a rede. As preocupações operacionais das MANETs são as mesmas para VANET, mas os detalhes
são diferentes. O movimento nas redes MANET é aleatório enquanto nas redes VANET os veículos
tendem a mover-se de uma forma organizada. A interacção com os equipamentos à beira da
estrada pode também ser caracterizada com bastante precisão e além disso, os veículos têm
restrições de movimento.
Intelligent Vehicular Ad-hoc Network (InVANET) - descreve uma forma inteligente de utilizar
VANET. Baseia-se na integração de múltiplas tecnologias de redes, tais como Wireless Fidelity
5
(WIFI), Worldwide Interoperability for Microwave Access (WiMAX), Bluetooth, ZigBee e outras
redes a fim de obter uma comunicação fácil, precisa, simples e eficaz entre os veículos sobre a
mobilidade dinâmica. Comunicação multimédia entre veículos, bem como rastreamento
automático de veículos também pode ser activado.
A piconet - É uma forma fundamental de comunicação para a tecnologia sem-fios Bluetooth.
Neste tipo de rede um dispositivo equipado com Bluetooth fornece a referência da sincronização e
é conhecido como o mestre, enquanto outros dispositivos na rede são conhecidos como escravos.
O Bluetooth é uma tecnologia sem-fios normalizada de curto alcance para conectividade pessoal
de uma gama de dispositivos electrónicos.
Internet Based Mobile Ad-hoc Network (iMANET) - Tipo de rede que estabelece conectividade
entre nós fixos e nós móveis. É uma técnica emergente que combina redes com fios (Internet) com
as redes mobile Ad-hoc (MANET) para desenvolvimento de uma infra-estrutura de comunicação
ubíqua2.
Através das várias implementações mencionadas, o uso da rede MANET é promissor devido às grandes
vantagens:
Rápida instalação: podem ser instaladas rapidamente em locais sem nenhuma infra-estrutura
prévia.
Resistência a falha de conexão: falha de um dispositivo pode ser facilmente seleccionado com a
reconfiguração da rede ou escolha de uma nova ligação.
Conectividade: se duas ou mais estações estão ao alcance da onda de rádio, então existe um canal
de comunicação entre elas. Nas redes fixas, as estações podem estar uma ao lado dao outras, mas
só comunicam se estiverem ligadas por um meio guiado.
Custo reduzido: a ausência da infra-estrutura fixa e de controlo centralizado reduz
consideravelmente o custo.
Interoperabilidade: uma grande vantagem é que as redes Ad-hoc não se restringem apenas para
uso de computadores, podem ser ainda utilizadas para conectar, telemóveis, PDA e Smartphone,
desde que estes tenham suporte para tal.
Mobilidade: constitui uma das vantagens primordiais das redes móveis.
Quando se desenvolve um protocolo para funcionar nas redes MANET há que ter em consideração
diferentes tipos de desafios presentes nestas redes. Salienta-se como os principais desafios:
2 Ubíquo - Que está ao mesmo tempo em toda a parte.
6
Topologia dinâmica – os terminais (nós) são livres para se mover arbitrariamente. Portanto a
topologia que é tipicamente multi-saltos pode variar de forma aleatória e imprevisível várias
vezes.
Largura de banda limitada e capacidade das ligações variáveis – as redes wireless continuam
a ter capacidade de ligação significativamente menor quando comparado com os dispositivos que
operam nesta rede. Como consequência, pode-se verificar forte congestionamento nas redes por
demasiado tráfego enviado pelos nós.
Tempo de vida dos dispositivos limitada – para algumas das aplicações, em que os terminais
são equipados com baterias, tem-se como critério a máxima optimização da energia a fim de
aumentar o tempo de sobrevivência da rede.
Segurança física limitada – as redes sem fios são mais susceptíveis às ameaças de segurança
quando comparadas com as redes com fios. As técnicas de segurança existentes são aplicadas às
redes sem fios para reduzir as ameaças.
Para superar os desafios das redes MANET acima referidos, vários estudos foram feitos aos longos dos
anos, muitos artigos foram publicados e muitos protocolos foram desenvolvidos para operar nestes tipos
de rede. Neste últimos anos, as tecnologias de informação e telecomunicação têm-se desenvolvido num
ritmo muito acelerado. Isto tem contribuído fortemente para o aparecimento de novos dispositivos e
aplicações para funcionar nas redes MANET. Apesar da existência de uma vasta gama de protocolos, estes
continuam a ter algumas limitações, como também surgem novas limitações com o aparecimento de novas
tecnologias para as redes MANET. Sendo assim, existe uma necessidade contínua de não só efectuar a
actualização dos protocolos existentes, mas também de desenvolver novos protocolos para poder
responder às novas exigências dos dispositivos e aplicações.
1.2 Motivação
A proliferação de dispositivos portáteis com capacidade de comunicação sem fios (por exemplo,
802.11a/b/g, etc.) tem incentivado a investigação na área de protocolos e aplicações para redes MANET.
Devido à liberdade de movimento dos nós na rede e o seu comportamento tipicamente imprevisível, as
falhas de comunicação podem tornar-se comuns neste ambiente de operação. É portanto necessário ter
em conta alguns requisitos quando se desenvolve um protocolo para funcionar neste tipo de cenário. Um
sistema destinado a funcionar numa MANET deve ser capaz de tolerar falhas de comunicação e ter em
conta as restrições de processamento e memória típicas dos dispositivos móveis. Finalmente, a largura de
banda disponível tende a ser também limitada, pelo que uma distribuição uniforme da carga de
comunicação pelos nós da rede reduz o esforço individual de comunicação, processamento e consumo
energético dos nós intervenientes. É de extrema importância realizar um protocolo que maximize a taxa
de transferência e ao mesmo tempo imponha o mínimo de sobrecarga de controlo. Os protocolos com
encaminhamento multi-percurso actuais tentam aliviar este problema através do cálculo e
7
armazenamento na cache de vários percursos obtidos durante uma única descoberta de percursos. Os
protocolos, com base num critério (métrica) específico, avaliam os vários percursos obtidos e escolhem
um como o principal. Os restantes são guardados na cache. Estes percursos apenas são utilizados quando
o percurso principal falhar. Uma nova descoberta só será possível quando falharem todos os percursos
guardados na cache. Alguns destes protocolos não realizam qualquer tipo de manutenção dos vários
percursos calculados durante o processo de descoberta. Como resultado, quando um percurso alternativo
é seleccionado para enviar dados, é muito provável que este também esteja inválido. Usando resultados
tão obsoletos e percursos inválidos, resulta num aumento considerável de perdas de pacotes e num atraso
maior da comunicação. Actualmente, já existem protocolos com encaminhamento multi-percurso que
fazem manutenção dos vários percursos concebidos durante o processo de descoberta. Em alguns destes
protocolos tais como Ad-hoc On-Demand Multipath Distance Vector (AOMDV), Optimized Ad-hoc On-
Demand Multipath Distance Vector (OAOMDV) e New Multipath Node-Disjoint Routing Based on AODV
Protocol (NMN-AODV) a manutenção é realizada localmente entre os nós vizinhos através do envio
periódico das mensagens hello [3], [4], [5]. No caso do protocolo Mobility Prediction Ad-hoc On-Demand
Multipath Distance Vector (MP-AOMDV), a manutenção é feita ao longo do percurso desde o nó de origem
até o nó de destino, através do envio periódico da mensagem heartbeat [4].
Foi proposto para esta tese a implementação e avaliação de desempenho de um protocolo com
encaminhamento multi-percurso. O protocolo desenvolvido teve como base o protocolo Ad-hoc On-
Demand Distance Vector (AODV) (RFC 3561). Escolheu-se o protocolo AODV devido ao seu bom
desempenho em redes densas e na presença de mobilidade. O protocolo desenvolvido realiza a verificação
periódica dos vários percursos concebidos durante o processo de descoberta. Esta verificação é realizada
com base na monitorização da conectividade local entre os nós vizinhos através do envio periódico da
mensagem hello. Deste modo, elimina-se a possibilidade de usar percursos alternativos inválidos. O
protocolo é flexível ao número de percursos que se pretende calcular durante o processo de descoberta. O
número máximo de percursos a ser determinado durante o processo de descoberta é definido através da
configuração manual de um parâmetro. Este parâmetro foi definido com a finalidade de minimizar o fluxo
das mensagens de controlo que circulam na rede, contribuindo desta forma para redução de sobrecarga
da rede.
1.3 Objectivos
Nesta dissertação é realizado o estudo e implementação de um protocolo com encaminhamento multi-
percurso para as redes MANET. O estudo foi conduzido através de simulação, utilizando o Network
Simulator 3 (NS-3) [6]. Foi implementado o protocolo Route Alternating Multipath AODV (RAM-AODV)
baseando no protocolo AODV que já existe no NS-3. O protocolo RAM-AODV foi programado para
determinar vários percursos entre o nó de origem e o nó de destino, num só processo de descoberta de
percursos. Os vários percursos obtidos são actualizados e são utilizados alternadamente para enviar
dados. Com isto pretende-se alcançar os seguintes objectivos:
Minimizar o atraso de comunicação extremo-a-extremo.
8
Maximizar o débito da rede.
Distribuição uniforme do processamento pelos vários nós da rede, maximizando assim o tempo
de vida de cada dispositivo.
Diminuir a frequência com que é feito o pedido de aquisição de percursos.
Desta forma, espera-se que as aplicações que correm sobre a rede MANET deixem de ser prejudicadas
pelos problemas acima referidos. Também se espera com este protocolo minimizar o número de pacotes
descartados e distribuir de forma uniforme a sobrecarga do envio de dados pela rede. Também se tem
como objectivo, realizar vários testes de simulação com o propósito de avaliar o desempenho do protocolo
desenvolvido. Para isto, irá ser utilizada uma diversidade de cenários possíveis, de forma a ter em
consideração todos os casos possíveis que eventualmente possam acontecer numa situação real.
1.4 Estrutura da tese
Este documento encontra-se dividido em 5 capítulos.
No capítulo 2 faz-se um estudo dos principais protocolos de encaminhamento com percurso único e os
protocolos com encaminhamento multi-percurso para as redes MANET. Nesses estudos aborda-se de
forma resumida o funcionamento destes protocolos.
O capítulo 3 aborda de uma forma detalhada e pormenorizada o protocolo desenvolvido. Explica
detalhadamente o modo de operação em termos de cálculos dos diferentes percursos e a manutenção dos
mesmos.
No Capítulo 4 apresenta-se resultados de vários testes e simulações, avaliando o desempenho do
protocolo desenvolvido.
No capítulo 5 apresenta-se as conclusões do trabalho, e indicam-se algumas melhorias que podem ser
realizadas no futuro.
9
10
2 Protocolos de encaminhamento para as redes MANET
2.1 Protocolo de encaminhamento com percurso único para as redes
MANETs
2.1.1 Aspectos gerais
Os protocolos de encaminhamento tradicionais da Internet são algoritmos sofisticados que têm o
propósito de mapear endereços de destino em interfaces de saída por meio de tabelas. Essas tabelas são
designadas por tabelas de encaminhamento. Depois de preencher as tabelas de encaminhamento com os
endereços IP dos nós da rede, tem-se a topologia da rede construída. Tendo em consideração as
características específicas das MANETs (mobilidade, ausência da infra-estrutura fixa…), os protocolos
desenvolvidos para as redes infra-estruturadas revelaram-se ineficientes. Atualmente existe um número
elevado de protocolos de encaminhamento desenvolvidos para as redes MANET. Foi sempre impossível
desenvolver um protocolo óptimo para todos os cenários de aplicação. Neste capítulo estuda-se apenas
alguns dos protocolos de encaminhamento com percurso único mais citados para as redes MANET. Os
protocolos da rede MANET podem ser classificados por categorias:
Reactivos
Pró - activos
Híbridos
Orientados à localização
Orientados à energia
Existem vantagens e desvantagens em cada uma das categorias, dependo do tipo de aplicações. Os
protocolos reactivos (On-Demand) caracterizam-se pelo facto de nem sempre terem disponíveis na sua
tabela de encaminhamento os percursos para todos os nós da rede. Estes tipos de protocolos foram
desenvolvidos para que um caminho só seja calculado apenas quando é necessário. Quando um nó
necessita de enviar um pacote para outro nó na rede, inicia-se um processo de descoberta dos percursos.
Este processo termina quando o percurso é calculado com sucesso, ou caso não exista um percurso
disponível nesse momento (o que pode indicar um partição na rede). A manutenção dos percursos vai
sendo realizada enquanto o nó de destino permanecer alcançável, ou até já não ser mais necessária.
Nos protocolos pró-activos (table-driven), os nós da rede mantêm informações de encaminhamento para
todos os nós da rede, de forma que quando for necessário enviar dados para um determinado nó da rede,
o caminho para este nó já é conhecido, eliminando desta forma o atraso provocado pelo processo de
descoberta de rota. Cada nó envia mensagens de actualizações para a rede, a fim de manter as suas tabelas
consistentes com o estado actual da rede e de poder acompanhar as mudanças da topologia. Uma vez que
11
estas mensagens são iniciadas por mecanismo de temporização, haverá sempre um número regular de
mensagens de actualização enviadas para a rede em intervalos de tempo fixo, mesmo quando a rede já se
encontra em equilíbrio. Desta forma, para uma rede densa, o fluxo de mensagem será demasiado, de tal
forma que a rede ficará sobrecarregada. Recomenda-se o uso destes tipos de protocolos, apenas para as
redes em que os vários nós estão sempre a comunicarem entre si. Sendo assim o envio periódico das
mensagens tem o propósito de diminuir o atraso devido a reconstrução periódica dos percursos. Estes
tipos de protocolos não devem ser utilizados em redes em que os equipamentos de pequena dimensão são
equipados com baterias, e nem em redes com largura de banda muito limitada.
Os protocolos híbridos são um compromisso entre os protocolos reactivos e pró-activos. Com este tipo de
protocolo pretende-se resolver os problemas dos dois tipos protocolos anteriores e aproveitar as suas
vantagens.
Os protocolos orientados à localização só podem ser aplicados quando a informação geográfica está
disponível (e.g. GPS). Estes protocolos são aconselháveis para redes estáticas ou redes com poucas
variações de topologia. Caso contrário a informação indicada por um nó, pode ficar inválida
imediatamente no instante a seguir devido à mobilidade.
Os protocolos orientados à energia fazem sentido em redes em que os equipamentos de pequena
dimensão estão equipados com uma bateria (e.g. PDAs, portáteis, telemóveis, RFID activo, etc.).
Como se pode verificar, o bom desempenho do protocolo está muito dependente do tipo de aplicação e das
características da rede onde irá ser utilizado. A Figura 2-1 mostra as principais categorias dos protocolos e
exemplifica com alguns dos protocolos mais utilizados nas redes MANET [7].
Protocolos de Emcaminhamneto para
Rede MANET
Pró-activo
Reactivo
Hibrido
OLSR
WRP
CGSR
DSR
TORA
ABR
ZRP
FSR
AODV
DSDV
SSA
Figura 2-1: Categoria dos protocolos de encaminhamento para as redes MANET.
Pode-se concluir que os protocolos reactivos são bons quando o tráfego é esporádico, e são mais
escaláveis desde que as condições do canal sejam aceitáveis. Por outro lado, dado que não mantêm a
informação para todos os nós da rede, existe sempre um atraso no início da comunicação. Enquanto isso,
12
os protocolos pró-activos são mais robustos em relação a perdas e não têm o atraso inicial no envio de
dados provocado pelo processo de descoberta de percursos. No entanto são menos escaláveis, a não ser
que se limite o número de destinos para os quais é necessário saber o caminho.
2.1.2 AODV – Ad-hoc On-Demand Distance Vector
O AODV é um protocolo reactivo, em que os percursos são determinados apenas quando são necessários.
Quando um nó de origem pretende criar um percurso para o nó de destino, um pedido de descoberta de
percurso é enviado para a rede. Os nós que recebam este pedido, actualizam a sua informação de
encaminhamento para o nó de origem. O pedido de descoberta de percurso contém o número de
sequência mais recente que o nó de origem conhece em relação ao nó de destino. Se um nó intermédio
conhecer um percurso mais recente para o nó de destino, responde ao nó de origem com essa informação,
caso contrário, retransmite este pedido para a rede. Quando um nó receber um pedido de descoberta de
percurso, ou seja, quando receber o pacote RREQ com o mesmo endereço IP que já tenha processado e o
mesmo identificador de pacote, este pedido é descartado. Quando um nó recebe uma resposta de pedido
de descoberta de percurso, ou seja, o pacote Route Reply (RREP) de um destino, pode começar a utilizar
esse percurso para enviar dados. No entanto, se mais tarde receber uma resposta de aquisição de percurso
com um número de sequência maior (ou com um número de sequência igual mas com um número de
saltos até ao destino menor que o percurso actual) esse percurso é actualizado. Um percurso é apenas
mantido enquanto estiver a ser utilizado, pelo que quando um nó de origem deixa de enviar dados por ele,
este irá eliminar-se por time-out. Se, no entanto, um percurso falhar enquanto estiver a ser utilizado, uma
mensagem de falha de percurso é devolvida ao nó de origem. O nó de origem terá de reiniciar um novo
processo de aquisição de percursos.
Para a manutenção dos percursos, este protocolo definiu um novo pacote chamado hello. Este pacote é
enviado periodicamente entre os nós com o propósito de averiguar se há ligações interrompidas. Neste
pacote são enviadas as informações relativamente ao endereço IP do nó, o seu número de sequência, (que
não é incrementado na mensagem hello) e o campo TTL inicializado a um, indicando que apenas os
vizinhos o recebem e actualizam sua informação de conectividade local. As mensagens de hello só são
enviadas pelos nós que fazem parte de uma rota activa e que não enviaram nenhuma mensagem de
difusão dentro de um intervalo de tempo configurável.
Quando a mensagem hello não é recebida num determinado intervalo de tempo pré-configurado, então
conclui-se que houve quebra de ligação. O nó que detecta esta quebra de ligação, tem a responsabilidade
de enviar uma mensagem Route Error (RERR) para todos os nós afectados. Para além das mensagens de
hello, também é averiguado o estado da ligação através da recepção ou não do ACK (confirmação). Quando
um nó enviar a mensagem Route Reply (RREP) com a flag que indica o reconhecimento da mensagem
activa, o nó destino deve responder com o pacote ACK para confirmar que recebeu o pacote RREP. Se
passar um intervalo de tempo pré-configurado e nó emissor do pacote RREP não receber a confirmação,
admite-se que houve uma quebra de ligação e procede-se com o processo de manutenção dos percursos
afectadas. O processo é análogo ao que se faz no caso das mensagens hello (RFC 3561 ) [8].
13
2.1.3 DSR - Dynamic Source Routing
O DSR é um protocolo de encaminhamento simples e eficiente desenvolvido especificamente da
comunicação multi-hop nas redes MANET.É composto por dois mecanismos essenciais de funcionamento:
A descoberta de rota (Route Discovery) e manutenção de rota (Route Maintenance). A descoberta de rota é
responsável por determinar um percurso entre um nó origem a qualquer outro nó da rede através do seu
endereço IP. O mecanismo de manutenção de rota verifica se a informação de encaminhamento de uma
dada rota ainda é valida. Segue-se a explicação mais detalhada do protocolo:
Descoberta de Rota (Route Discovery): Quando um nó origem S, pretende enviar uma
mensagem para um nó destino D, e que não consta nas suas rotas armazenadas na cache, o nó S
iniciará então um pedido de rota (Route Request). Este pedido vai ser enviado para rede em
broadcast (é adicionado o endereço IP dos nós que encaminham o pedido) até encontrar o destino
D. O nó D irá então responder ao nó origem S confirmando o seu pedido de rota, devolvendo uma
lista de nós intermédios, que formam o caminho pelo qual o nó S o pode contactar.
Manutenção de Rota (Route Maintenance): Quando um nó tenta enviar uma mensagem para
outro nó através de um caminho conhecido, cada nó intermédio necessita confirmar que o
próximo salto da mensagem recebe o pacote com sucesso. Em situações de falha, este pacote será
em princípio retransmitido pelo protocolo MAC (até um número máximo de vezes) se mesmo
assim falhar, um erro de rota é gerado e devolvido ao nó de origem. Quando o nó de origem
receber a mensagem de erro de rota, remove da sua cache a informação relativa a esta rota.
Existem dois factores importantes a reter destes mecanismos. Primeiro, o processo de descoberta de rotas
é muito dispendioso em termos de carga na rede, visto que inunda a rede com um pedido de procura de
um nó. Segundo, a manutenção das rotas é ela também reactiva, pelo que um nó só sabe que um percurso
é inválido se o tentar usar (excepto se a validade da informação na cache expirar). Cada nó DSR contém
uma cache de encaminhamento onde mantém informação em como contactar outros nós. Esta informação
pode ser obtida através do mecanismo de descoberta de rotas, ou por overhearing de informação de
encaminhamento a ser transmitida para outros nós. Adicionalmente, um nó pode receber múltiplas rotas
para comunicar com um determinado nó quando efectua um pedido de rota, e como tal, as tabelas de
encaminhamento contêm informação de encaminhamento redundante, o que aumenta a capacidade de
tolerar reconfigurações topológicas da rede (RFC 4728) [9].
2.1.4 OLSR – Optimized Link State Routing
O OLSR é um protocolo de encaminhamento distribuído e pró-activo, com optimização de topologia,
desenvolvido para redes sem fios que apresentem uma arquitectura Ad-hoc. A principal característica
deste protocolo está na selecção de um conjunto de nós denominados de Multipoint Relays (MPR) que são
responsáveis pela difusão das mensagens topológicas na rede, ao contrário do originalmente definido pelo
conceito de encaminhamento link-state, em que todos os terminais difundiam esta informação – razão pela
14
qual se verifica o uso deste protocolo com bastante regularidade em redes sem fios. O protocolo OLSR,
para além das mensagens de controlo de topologia características do encaminhamento link-state, não gera
qualquer outro tipo de tráfego extra para informar sobre a quebra ou a formação de uma nova ligação.
Devido ao envio periódico da topologia da rede, todos os nós ficam informados sobre as alterações
verificados na rede. Pode assim ser considerado como um protocolo robusto a perdas. O tipo de
encaminhamento realizado é salto-a-salto em que cada nó utiliza a informação que possui acerca da sua
vizinhança a 1-salto para enviar pacotes, deixando o próximo nó que recebe o pacote decidir qual é o
próximo destinatário do mesmo. De seguida explica-se os três procedimentos importantes dos protocolos
OLSR:
Descoberta dos nós vizinhos.
Eleição do conjunto MPR.
Construção da tabela de encaminhamento.
Numa primeira fase, cada nó precisa descobrir quais são os seus nós vizinhos a 1-salto, com os quais tem
uma ligação directa e bidireccional. Seguindo o funcionamento padrão do protocolo “link-state”, cada nó
OLSR descobre o seu vizinho através do envio periódico da mensagem hello. Esta mensagem é difundida
em broadcast, contendo a informação sobre os seus actuais vizinhos (que podem ser classificados como
Symmetric, MPR ou Not Neighbor) e os estados das respectivas ligações (Unspecified, Asymmetric
(Unidireccional), Symetric (Bidireccional) e Lost). Esta troca de mensagens hello permite não só o
conhecimento da vizinhança a 1-salto, mas também a 2-saltos. É com base na informação trocada por estas
mensagens, e depois guardada numa tabela de vizinhança durante um certo período de tempo, que cada
nó selecciona os seus nós MPR. Estes são indicados na mensagem hello com o seguinte par [vizinho MPR,
ligação bidireccional]. A troca de mensagens hello, permite que um nó construa a sua tabela de MPR
Selectors, que contém todos os seus nós vizinhos que o seleccionaram como nó MPR. Esta mensagem é
enviada a todos os nós a 1-salto e não é reencaminhada por estes. Depois de ter o conhecimento dos
vizinhos a 1-salto, procede-se á eleição dos nós MPR. Assim que forem seleccionados os nós MPR
suficientes, há que informar os restantes nós, podendo por fim ser calculada a tabela de encaminhamento,
de modo a se proceder ao envio dos dados. É importante realçar que o cálculo do conjunto de MPR é
realizado de forma que consiga garantir a cobertura de todos os vizinhos a 2-saltos. Explica-se o
procedimento de eleição de nós MRP, considerando o nó S como o nó de referência. Todos os vizinhos a 1-
salto do nó S que apresenta willingness 3= WILL ALWAYS são automaticamente eleitos para o conjunto de
nós MPR. Existem outros critérios a ter em consideração no cálculo de MPR - aconselha-se uma breve
3 Willingness O parâmetro willingness (n) (interpretado por voluntariedade) está associada a cada nó, e representa o
seu livre interesse em retransmitir tráfego. Este parâmetro pode assumir os seguintes valores, WILL NEVER, WILL
ALWAYS e WILL DEFAULT, e os seus respectivos significados são, nunca pode seleccionado como MPR, pode ser
seleccionado e por último corresponde a inicialização do parâmetro.
15
consulta a [10]. O cálculo da eleição do MPR é sempre efectuado desde que se verifiquem as seguintes
situações:
Uma mudança na topologia da rede a 1-salto, com o aparecimento ou a quebra de uma ligação
bidireccional.
Uma mudança no subconjunto de vizinhos a 2-saltos, com o conhecimento de uma nova ligação
bidireccional.
Depois de S elaborar o seu conjunto de nós MPR, é necessário informar os seus vizinhos a 1-salto, no
próximo envio periódico da mensagem hello. Assim, cada nó vizinho que receber a mensagem pode
construir a sua tabela de MPR Selectors. De forma a ser possível a construção das tabelas de
encaminhamento, cada nó difunde em modo de broadcast mensagens de controlo especificas,
denominadas de Topology Control (TC) messages. Esta mensagem apenas são difundidas e retransmitidas
pelos nós previamente seleccionados como nós MPR, enquanto o seu tempo de vida associado não expirar.
O envio desta mensagem por cada nó é periódico, de forma a informar a rede sobre o seu conjunto de MPR
Selector. Cada nó da rede que receber esta mensagem, tem a possibilidade de construir a sua tabela de
encaminhamento. Resumidamente, o protocolo funciona do seguinte modo. Cada nó S da rede selecciona
um conjunto de nós entre os seus vizinhos a 1-salto, responsáveis pela retransmissão das mensagens de
topologia. Todos os outros vizinhos de S que não façam parte deste conjunto apenas recebem a mensagem,
processam-na, mas não a retransmitem. Para tal, cada nó MPR mantém um conjunto de vizinhos
denominados MPR Selectors, e sempre que uma mensagem de topologia vinda de um nó pertencente a
este conjunto é recebida, sabe-se que deve ser retransmitida, pois o nó receptor foi escolhido como MPR
pelo nó emissor. Cada nó escolhe o seu conjunto de nós MPR de entre todos os seus vizinhos a 1-salto que
possam garantir, em termos de alcance rádio, a total cobertura dos nós a 2-saltos. O conjunto de nós MPR
do nó S, denominado de MPR (S), é considerado um subconjunto da vizinhança de S que perfaz a condição
em qualquer nó na vizinhança a 2-saltos de S, tem que ter uma ligação bidireccional com o conjunto MPR
(S). Quanto menor for MPR (S) maior é a optimização do protocolo, pois exige um menor numero de
retransmissões de mensagens.
Consequentemente, o número de retransmissões necessárias para informar todos os nós vizinhos a 2-
saltos de S é reduzido. Os nós MPR não servem apenas para transmitir a informação topológica da rede,
mas também o encaminhamento deve também ser feito pelos nós MPR. Para tal, cada nó transmite
periodicamente o conjunto de nós que o seleccionaram como nó MPR. Com base nesta informação, cada nó
calcula e actualiza o seu percurso para cada nó de destino conhecido, através do seu nó MPR, construindo
assim sempre que possível, um encaminhamento através de nós MPR. O facto de existir uma ligação
bidireccional entre os nós MPR e os seus MPR Selectors garante que a transferência de dados se possa
realizar em ligações bidireccionais (RFC 3626) [10].
16
2.1.5 DSDV - Destination-Sequenced Distance-Vector
O DSDV é um protocolo pró-activo, inspirado no protocolo vector-distância (VD). Este protocolo procura
manter a simplicidade do protocolo vector-distância, mas resolvendo os dois problemas que limitam o seu
uso nas redes MANET. O primeiro é a possível criação de ciclos pelo protocolo VD. O segundo é a
necessidade de um ajuste mais rápido da topologia da rede na medida em que os seus nós se movem.
Todos os nós DSDV possuem uma tabela de encaminhamento com o endereço do nó de destino, o número
de saltos (hop) para alcançar este destino, o número de sequência do nó de destino, o endereço IP do
próximo salto e a identificação do nó para qual é mantida a tabela.
O protocolo funciona do seguinte modo: cada nó da rede envia mensagens de actualização periodicamente
ou imediatamente quando verificar alguma alteração importante na topologia da rede. Quando um nó
receber uma mensagem de actualização, se for uma mensagem nova é inserida de imediato a entrada da
tabela de encaminhamento. Caso já exista uma entrada referente ao destino da mensagem de actualização
recebida, então procede-se com a actualização da entrada da tabela, se verificar uma das duas seguintes
situações:
Se o número de sequência da mensagem da actualização recebida for mais recente, então é
actualizada a informação na entrada da tabela de encaminhamento. No entanto, não é enviada de
imediato, devido ao facto de haver possibilidade de receber outra rota distinta, com melhor
métrica para o mesmo destino.
Se os números de sequência forem iguais, faz-se actualização da informação na entrada da tabela
só no caso do número de saltos da mensagem de actualização ser menor ao que já se encontra na
entrada da tabela.
Por forma a minimizar o congestionamento da rede, foram implementados dois tipos de actualizações:
Incremental Update: Neste tipo de actualização o nó envia para o seu vizinho apenas as últimas
actualizações ocorridas desde o envio do último pacote. O nó adjacente recebe o pacote e adiciona
as suas informações recentes sobre a topologia e retransmite para os seus vizinhos. Quando o
pacote estiver completamente preenchido e não houver mais espaço, automaticamente é
alternado para o segundo tipo de actualização – Full Update.
Full Update: O nó envia toda a informação contida em sua tabela.
Quando um nó envia a sua tabela de informação, mesmo que não seja alterada, incrementa o número de
sequência de duas unidades e inicializa a sua métrica a zero. Quando um nó detectar uma falha de ligação
e consequentemente a perda de um vizinho, então altera o número de sequência referente a este vizinho
para o próximo número ímpar (incrementa apenas uma unidade).
17
2.1.6 ZRP - Zone Routing Protocol
O ZRP é um protocolo desenvolvido para resolver os problemas apresentados nos protocolos reactivos e
pró-activos. Trata-se de um protocolo híbrido, ou seja, pode ser tanto um protocolo reactivo como um
protocolo pró-activo, de maneira a aproveitar as vantagens dos dois tipos de protocolos. Como o próprio
nome indica, este protocolo baseia-se no conceito de zonas, portanto divide toda rede em zonas de
encaminhamento de tamanho R4. A zona de encaminhamento de cada nó é definida separadamente e de
forma independente, sendo assim, as zonas de encaminhamento de cada nó podem ter tamanhos variáveis
e podem estar sobrepostas. Os nós que estão separados a uma distância menor do que o parâmetro R do
nó central, são designados por nós internos, e os que estiveram a uma distância igual a R do nó central são
designados por nós periféricos. O ZRP refere-se ao protocolo de encaminhamento pró-activo no interior
da zona como Intra-zone Routing Protocol (IARP) e ao protocolo de encaminhamento reactivo global
designa-se por Inter-zone Routing Protocol (IERP). O IERP e IARP não são protocolos específicos. O IARP é
uma família protocolos de encaminhamento pró-activo “Link-state” de profundidade limitada. O IARP
mantém informação de encaminhamento para os nós que estão dentro da zona de encaminhamento do nó
central, enquanto o IERP é uma família de protocolos de encaminhamento reactivo que oferece maior
descoberta de percursos e serviços de manutenção de percursos baseado no estado da ligação local
monitorizado por IARP. Dado que é conhecida a topologia do interior da zona de cada nó, pode-se reduzir
o tráfego quando a descoberta de um percurso fora da zona for necessário. Em vez de enviar os pacotes
em broadcasting, o ZRP usa um conceito chamado bordercasting. Este conceito chamado Bordercasting
utiliza a informação fornecida pela topologia IARP para solicitar uma consulta directamente aos nós
periféricos da zona, uma vez que cada nó periférico tem o conhecimento global da sua zona de
encaminhamento. O serviço de pacote bordercast é fornecido por Bordercast Resolution Protocol (BRP).
Considerando a arquitectura do protocolo ZRP, assim como é ilustrado na Figura 2-2, o processo de
encaminhamento do protocolo ZRP inicia-se com o Neighbor Discovery Protocolo (NDP). O NDP é fornecido
pela camada MAC.
4 R – significa o raio da zona. Contabiliza o número de saltos desde o nó central da zona até os nós
periféricos.
18
Figura 2-2: Arquitectura do protocolo ZRP. [Fonte: [11]]
Inicialmente cada nó precisa de conhecer quais são os seus nós vizinhos e os seus nós periféricos. O nó
detecta os seus vizinhos através do protocolo NDP e constrói a sua tabela contendo os seus nós vizinhos.
Esta tabela é posteriormente completada de forma pró-activa com os restantes nós que fazem parte da
zona de encaminhamento através do protocolo IARP. Caso haja qualquer alteração por parte dos nós
vizinhos, o protocolo NDP informa o protocolo IARP acerca do sucedido, para poder manter a sua tabela
sempre actualizada.
Dado que cada nó conhece sua zona de encaminhamento e os seus respectivos nós periféricos, um pedido
de aquisição de rotas, processa da seguinte forma: considera-se a rede da Figura 2-3, o nó S tem um pacote
para enviar para o nó destino X, o raio da zona é de 2-saltos. O nó S usa a tabela de encaminhamento
fornecida pelo IARP para verificar se o nó de destino pertence à sua zona de encaminhamento. Como não
pertence à sua zona de encaminhamento, um pedido de aquisição de rota é feito usando o IERP. O pedido é
enviado em bordercast para nós periféricos. Todos os nós periféricos procuram na sua tabela de
encaminhamento pelo nó de destino. Assim como se encontra ilustrado na Figura 2-3, os nós periféricos
são, H, G, J e I.
Figura 2-3: Zona de encaminhamento do nó S. [Fonte: [12]]
19
O nó I não encontra o nó de destino na sua tabela de encaminhamento, consequentemente faz o bordercast
para os seus respectivos nós periféricos. Assim como mostra o desenho da Figura 2-4, os nós periféricos
do nó I são Q, R, F, S, D e T.
Figura 2-4: Zona de encaminhamento do nó. [Fonte: [12]]
Devido ao mecanismo do controlo do query o pedido não é enviado de volta, para os nós D, F e S.
Finalmente o pedido de aquisição de rota é recebido pelo nó T, no qual consegue encontrar o nó destino
dentro da sua zona de encaminhamento, assim como mostra a Figura 2-4.
Figura 2-5:Zona de encaminhamento do nó T. [Fonte: [12]]
O nó T gera uma resposta de rota e envia-a para o nó que lhe tinha interrogado sobre o nó destino X. Essa
resposta faz o mesmo percurso que tinha sido feito pelo pedido de aquisição, mas no sentido inverso até
chegar ao nó de origem. O caminho inverso até chegar ao nó de origem é possível, devido ao facto de todos
os nós periféricos por onde passou o pedido de aquisição de rota terem inserido os seus próprios
endereços antes de reencaminharem o pedido.
De forma a não pôr em causa o desempenho deste protocolo, é muito importante uma boa definição do
raio da zona de encaminhamento. O raio da zona de encaminhamento pode ser definido manualmente
pelo administrador da rede. É óbvio que esta é a forma mais fácil, mas longe de ser a mais eficiente. No
caso de uma rede que sofre poucas variações, este método pode ser eficaz. A outra forma mais eficiente é a
20
configuração dinâmica, isto é, cada nó pode definir o raio da sua zona de encaminhamento baseado em
medidas locais do tráfego.
Se o valor do raio for muito grande, o protocolo ZRP converge num protocolo puramente pró-activo e
deixamos de ter os protocolos reactivos IERP e o protocolo BRP. Sendo assim, não se pode aproveitar as
vantagens dos protocolos reactivos. Por outro lado se o raio for muito pequeno, o protocolo ZRP converte-
se num protocolo puramente reactivo. Sendo assim, torna-se impossível ter as vantagens do protocolo
IARP e continuamos com os problemas dos protocolos reactivos. O valor do raio da zona de
encaminhamento de cada nó deve ser definido com o máximo de rigor, de forma a eliminar as
desvantagens dos dois tipos de protocolos reactivos e de aproveitar ao máximo as vantagens destes dois
tipos de protocolos.
2.1.7 Considerações finais e conclusão
Neste capítulo apresentou-se os principais protocolos que operam nas redes MANET. Através dos estudos
realizados, pode-se concluir que todos os protocolos são importantes e têm as suas vantagens e
desvantagens. O que se deve ter em consideração é que os protocolos foram desenvolvidos para cenários
específicos. É impossível desenvolver um protocolo que seja bom em todos os cenários. Existem diversas
aplicações, cada uma com exigências diferentes, portanto, para o desenvolvimento de um determinado
protocolo, há que ter sempre em consideração os requisitos da rede ou do tipo de aplicação para a qual é
desenvolvido.
Os protocolos reactivos e pró-activos baseiam-se de alguma forma nos algoritmos de cálculo de vector
distância (DV) e de “Link State” (LS) utilizados nas redes tradicionais. Os protocolos do tipo DV
apresentam bons desempenhos em redes estáticas, uma vez que todos os nós da rede mantêm uma visão
da topologia de toda a rede. São fortemente indicados para redes estáticas ou que requeiram tráfego
intenso, mas não para as redes dinâmicas, pois apresentam convergência lenta e tráfego de controlo
excessivo.
Os protocolos do tipo LS são mais adequados para as redes que exigem garantia de QoS, porque permitem
que se associe os custos às capacidades das ligações, mas o seu tráfego de controlo é ainda maior, uma vez
que todos os nós da rede precisam conhecer a topologia completa e actualizada da rede.
O protocolo OLSR introduz uma optimização adicional no algoritmo LS, minimizando o número de nós que
retransmitem o pacote de controlo, ao determinar um conjunto mínimo de nós vizinhos imediatos
(conjunto MRP) requeridos para alcançar todos os vizinhos a dois saltos.
Os protocolos reactivos, como é o caso do AODV geram menor tráfego de controlo que os protocolos pró-
activos porque não há necessidade de obter rotas para todos os nós da rede a priori, e não é gerado
nenhum tráfego de actualização de rotas. Este tipo de protocolo apresenta melhor desempenho do que os
protocolos pró-activos, mesmo em cenário de alta mobilidade, embora pagando o preço de uma latência
inicial adicional para aquisição de rota. Uma outra desvantagem dos protocolos reactivos surge devido ao
21
facto de detectar quebra de uma ligação apenas quando há envio de um pacote através deste percurso.
Neste caso, há uma latência maior para a aquisição de nova rota. Este é o caso do protocolo DSR que utiliza
rota na origem e os nós intermediários não precisam de saber os percursos para o destino.
O protocolo ZRP tenta mitigar os problemas não resolvidos pelos protocolos reactivos e pró-activos. Uma
vez que não se especifica qual é o protocolo reactivo utilizado fora da zona de encaminhamento e não se
especifica também qual é o protocolo pró-activo utilizado dentro da zona de encaminhamento, isto
constitui uma desvantagem do protocolo ZRP. Posto isto, podemos ter diferentes protocolos pró-activos a
funcionar nas zonas de encaminhamento e diferentes protocolos reactivos a funcionar fora da zona de
encaminhamento. Como consequência, tem-se o problema da interoperabilidade entre os protocolos
dentro da mesma zona de funcionamento.
2.2 Protocolos de encaminhamento multi-percurso para as redes MANET
2.2.1 Aspectos gerais
O encaminhamento multi-percurso tem sido explorado em vários domínios da comunicação. Nas redes
telefónicas tradicionais com comutação de circuitos utilizava-se o encaminhamento multi-percurso
designado por percursos de encaminhamento alternativo. Assim, cada nó de origem e de destino tinham
um conjunto de percursos. Estes percursos dividiam-se em percurso primário e percursos alternativos.
Esta técnica foi proposta com o objectivo de diminuir o bloqueio das chamadas e aumentar a utilização da
rede global [13].
O encaminhamento multi-percurso foi também utilizado em redes de dados que suportam o serviço
orientado à conexão com qualidade de serviço (QoS). Por exemplo Asynchronous Transfer Mode (ATM),
redes que utiliza o protocolo de sinalização, para definir múltiplos percursos entre o nó de origem e o nó
de destino. O encaminhamento multi-percurso pode oferecer balanceamento de carga pela rede,
tolerância a falhas e uma maior largura de banda agregada. O balanceamento de carga pode ser
conseguido ao espalhar a carga ao longo dos vários percursos, e por conseguinte diminui também o
congestionamento. O encaminhamento multi-percurso consiste em três componentes: descoberta de
percursos, manutenção dos percursos e alocação de tráfego.
A descoberta de percursos e manutenção dos percursos consiste em encontrar múltiplos percursos entre
o nó de origem e o nó de destino. O protocolo de encaminhamento multi-percurso determina percursos
com os nós disjuntos e percursos com ligações disjuntas. Os percursos com os nós disjuntos são também
conhecidos como percursos totalmente disjuntos, não têm ligações nem nós em comum. Os percursos com
ligações disjuntas não têm nenhuma ligação em comum, mas podem conter nós em comum.
A alocação de tráfego define as estratégias utilizadas pelos nós de origem para enviar os dados para o nó
destino pelos vários percursos disponíveis. Pode-se fazer alocação de tráfego por conexão, em que se
envia todo o tráfego através de um só caminho, ou pode-se fazer alocação de tráfego por pacotes, no qual
os pacotes são distribuídos através de múltiplos caminhos. A alocação de tráfegos por conexão é
22
apropriada para sistemas de comunicações que apresentam tráfegos constantes (por exemplo de uma
comunicação por voz), necessitando de uma conexão dedicada para a transferência de informações
contínuas. A alocação de tráfegos por pacotes é utilizada para optimizar o uso da largura de banda da rede,
minimizar a latência e aumentar a robustez da comunicação. Este tipo de alocação é mais complexo,
apresentando maior variação na qualidade de serviço, porém utiliza melhor os recursos da rede.
A seguir apresentam-se alguns protocolos de encaminhamento multi-percurso mais citados no contexto
das redes MANETs.
2.2.2 Ad-hoc On-Demand Multipath Distance Vector Routing (AOMDV)
Este protocolo é uma extensão do protocolo AODV para realizar o encaminhamento multi-percurso. Ao
contrário do AODV, cada pacote RREQ é considerado pelo nó de destino. Consequentemente, múltiplos
percursos podem ser descobertos num só pedido de descoberta. A entrada da tabela de encaminhamento
contém uma lista de endereços IP de nós para próximos saltos e os respectivos valores de hop-count. O
AOMDV utiliza apenas as mensagens informativas do protocolo AODV, limitando deste modo a sobrecarga
da rede durante o processo de descoberta dos vários percursos. As únicas fontes de sobrecarga em relação
ao protocolo AODV, são as mensagens RREPs e RRERs extra para descoberta e manutenção dos vários
percursos, juntamente com alguns campos suplementares no encaminhamento dos pacotes de controlo
(RREQs, RREPs e RRERs).
De modo a garantir que os vários percursos calculados estão actualizados, consistentes com a informação
actual da rede e sem ciclos, o AOMDV mantém um número de sequência das mensagens mais recentes
recebidas do nó de destino. O AOMDV mantém o mesmo número de sequência para todos os percursos
descobertos para o mesmo destino. Quando é recebida uma mensagem de anúncio de percurso com um
número de sequência mais recente, todos os percursos mantidos para o número de sequência anterior são
eliminados. A entrada da tabela é actualizada com o percurso referente ao número de sequência mais
recente.
Para o cálculo de percursos sem ciclos, são impostas duas regras para as mensagens de anúncio e
aceitação de percurso, com o número de sequência igual ao número de sequência da entrada da tabela de
encaminhamento:
Regra do anúncio de percurso: nunca anunciar um percurso menor do que já foi anunciado.
Regra da aceitação de percurso: nunca aceitar um percurso maior do que já foi anunciado.
O protocolo AOMDV mantém vários caminhos com o mesmo número de sequência utilizando o conceito
de advertised-hop-count. Cada nó mantém uma variável chamada advertised-hop-count para cada destino.
Esta variável representa o número máximo de saltos para um determinado nó de destino, permitido pelos
nós e permanece inalterável para o mesmo número de sequência. No entanto, quando um Route Response
23
(RREP) é recebido com um número de sequência mais recente, a lista dos endereços IP dos próximos
saltos e o advertised-hop-count são actualizados [5].
Para além de manter vários percursos sem ciclos, o AOMDV visa encontrar percursos alternativos
disjuntos. Os percursos alternativos disjuntos (percursos com ligações disjuntas) revelam-se mais
tolerantes as falhas da rede quando comparados com os percursos alternativos sobrepostos. O mecanismo
proposto para garantir percursos alternativos disjuntos requer a actualização da informação do último e
do próximo salto para todos os percursos. O último salto de um caminho a partir de um nó de origem P
para um nó de destino D refere-se ao nó precedendo imediatamente o nó D neste percurso. O próximo
salto refere-se ao nó vizinho do nó P, para qual é transmitido o pacote RREQ. Para um percurso com
apenas um salto, o próximo salto é o nó D e o último salto é o nó P. Sendo assim, considera-se que dois
percursos do nó de origem P para o nó de destino D são percursos disjuntos, se possuírem a unicidade no
próximo e último salto. No entanto, para obter percursos com os nós disjuntos, a condição da unicidade no
próximo e no último salto não é suficiente. Como se pode ver na rede da Figura 2-6, apesar de existir
unicidade no próximo e no último salto nos percursos (S-A-I-X-D) e (S-B-I-Y-D), estes percursos não são
percursos com os nós disjuntos (possuem nó I em comum). Neste exemplo, para garantir percursos com
os nós disjuntos deve-se introduzir uma restrição adicional. Esta restrição implica que cada nó intermédio
deve fazer parte apenas de um percurso.
S
B
A
D
X
I
Y
RREQ
RREQRREQ
RREQ
RREQ RREQ
RREQ
RREQ
Pacote descartado.
Pacote não descartado.
Figura 2-6:Processo de descoberta de rotas – AOMDV.
O processo de descoberta de percurso é iniciado pelo nó de origem, quando este pretende enviar dados
para o nó de destino e não possui nenhum percurso disponível. O nó de origem gera o pacote RREQ e
envia-o em broadcast para a rede. Quando um nó intermédio recebe o pacote RREQ, se não tiver nenhum
percurso disponível para o nó destino, retransmite o pacote. No caso de o nó intermédio ter percurso
disponível para o nó de destino, gera o pacote RREP e responde para o nó de origem pelo percurso
inverso. O nó intermédio pode responder a vários pacotes RREQ, consoante o número de percursos
diferentes que tiver disponíveis para o nó de destino. Para cada pacote RREQ o nó intermédio responde
com o pacote RREP diferente, e quando enviar todos os percursos disponíveis e voltar a receber o pacote
RREQ, este é descartado. O nó de destino, quando recebe o pacote RREQ responde com o pacote RREP pelo
24
percurso inverso para o nó de origem. Considerando a rede da Figura 2-6, temos como o nó de origem o
nó S e o nó de destino o nó D. O nó S envia o pacote RREQ para a rede à procura do nó de destino D.
Admitindo que a cópia do pacote RREQ via o nó A chega primeiro ao nó I, como é o primeiro pacote RREQ
que ele recebe e uma vez que ainda não tem nenhum percurso para o nó de destino, retransmite o pacote
para rede. De seguida, o nó I vai receber a cópia RREQ via o nó B. Com base na informação do <ID RREQ, IP
SOURCE>, o nó I conclui que o pacote RREQ é uma duplicação, portanto, é descartado. O nó destino D
quando recebe o pacote via nó X, responde com o pacote RREP. Pouco tempo depois recebe a cópia via nó
Y, este apenas garante unicidade no último salto (nó Y é o ultimo salto, que é diferente do nó X). O próximo
salto é o nó A, que é igual à cópia do RREQ via o nó X, portanto, a cópia via nó Y é descartada pelo nó de
destino D. No final do processo temos determinados dois percursos no sentido directo (nó de origem para
o nó de destino), (S-A-I-X-D) e (S-B-I-Y-D). No sentido inverso é formado apenas um percurso (D-X-I-A-S). O
percurso (D-Y-I-B-S) não foi formado, uma vez que o seu percurso directo não verifica a condição de
unicidade no próximo salto. Este fenómeno é designado como problema de “route cutoff” e constitui uma
desvantagem do protocolo AOMDV.
2.2.3 Optimized AOMDV routing protocol (OAOMDV)
Este protocolo foi desenvolvido para resolver o problema de “route cutoff” do protocolo AOMDV. Quando
existe mais do que um nó intermédio comum nas ligações disjuntas entre o nó de origem e o nó de destino,
torna-se difícil determinar todos os percursos inversos5 existentes entre eles. Para minimizar a frequência
com que é feito o pedido de descoberta de percurso, é muito vantajoso descobrir todos os percursos
directos6 e inversos disjuntos existentes entre os nós de origem e de destino.
Se houver dois percursos disjuntos com um ou mais nós intermédios em comum entre o nó de origem e o
nó de destino, pode-se formar então dois percursos directos disjuntos e dois percursos inversos disjuntos.
Considerando a rede representada na Figura 2-7, é possível determinar dois percursos directos (S-A-C-E-
D) e (S-B-C-F-D) e dois percursos inversos (D-E-C-A-S) e (D-F-C-B-A) [3].
S
A
B
C D
E
F
RREQ
RREQRREQ(B)
RREQ(A) RREQ(A)
RREQ(A)
RREQ(A)
RREQ(A)
Detectação do RREQ
Caminho inverso
Figura 2-7:Processo de definição do percurso inverso – protocolo OAOMDV.
5 Percurso inverso – é um percurso definido desde o nó de destino até ao nó de origem. 6 Percurso directo – é um percurso definido desde o nó de origem até ao nó de destino.
25
Para que isto seja possível, o protocolo OAOMDV implementa um mecanismo de funcionamento diferente
do protocolo AOMDV. O pacote RREQ é utilizado para determinar o percurso inverso, o pacote RREP é
utilizado para determinar o percurso directo e o pacote Route Reply Acknowledgement (RREP_ACK) é
utilizado para resolver o problema de “route cutoff”. O processo de descoberta do percurso directo inicia-
se quando um nó de origem tiver que enviar dados para um determinado nó de destino e não tiver
percurso disponível. O nó de origem envia o pacote RREQ em broadcast para rede. Quando um nó vizinho
do nó de origem receber o pacote RREQ guarda o seu endereço IP no campo “Last hop” do pacote RREQ,
para poder identificar os percursos disjuntos inversos, e de seguida retransmite o pacote para a rede.
TYPE
ACK
Last Hop
Hop Count
Destination IP Address
Destination Sequence Number
Originator IP Address
Lifetime
Figura 2-8: Formato do pacote RREQ do OAOMDV.
Os nós intermédios quando recebem o pacote RREQ, se tiverem um percurso disponível para o nó de
destino, geram um pacote RREP e encaminham-o para o nó de origem. Caso os nós intermédios não
tenham nenhum percurso disponível para o nó de destino, então processam o pacote RREQ. Se for o
primeiro pacote RREQ recebido do nó origem, então actualizam a entrada da sua tabela de
encaminhamento com as informações do pacote RREQ e depois transmitem-no para rede. A Tabela 2-1 e a
Tabela 2-2 ilustram alguns dos campos da entrada da tabela de encaminhamento e da lista de percursos,
que são actualizadas com informações do pacote RREQ.
Tabela 2-1: Entrada da tabela de encaminhamento do protocolo OAOMDV.
Destination
Sequence Number
Advertised hop count
Route List
Tabela 2-2: Estrutura da Lista de percursos do protocolo OAOMDV.
Hop_count1
Next_Hop1
Last_Hop1
Expiration_timeout1
Hop_count2
Hop_count2
Last_Hop1
Expiration_timeout2
Caso não seja o primeiro pacote RREQ, então este é processado consoante a informação disponível nos
campos “Last hop” e “hop-count”. O nó intermédio apenas aceita RREQ com diferentes valores de “Last
hop” e com “hop-count” inferior ao advertisid-hop-count mantido na entrada da tabela de encaminhamento
para o destino do RREQ. O nó de destino quando recebe o pacote RREQ pela primeira vez, actualiza a
26
entrada da sua tabela de encaminhamento e gera o pacote RREP para enviar para o nó de origem. Para
salvaguardar a situação de “route cutoff”, o valor do campo “Last hop” do pacote RREQ é copiado para o
campo ACK do pacote RREP. O percurso directo é definido à medida que o nó de destino envia o pacote
RREP para o nó de origem. O vizinho do nó de destino quando recebe o pacote RREP, adiciona o seu
próprio endereço no campo “Last hop” para poder identificar múltiplos percursos disjuntos directos para
o nó de destino. Quando o nó de origem receber o pacote RREP, ficam definidos os percursos directos e
inversos. Para resolver o problema de “route cutoff” ou do percurso omitido, este protocolo criou um novo
pacote de encaminhamento designado por Route Reply Acknowledgement (RREP_ACK).
A Figura 2-9 mostra os campos do pacote RREP_ACK. O campo “LAST RPHOP” contém o endereço IP do nó
vizinho do nó de origem e o campo “LAST FPHOP” contêm o endereço IP do nó vizinho do nó de destino.
TYEPE ORIGINATOR SEQUENCE NUMBERORIGINATOR IP ADDRESSDESTINATIO IP ADDRESSLAST FPHOPLAST RPHOP
Figura 2-9: Formato da mensagem RREP_ACK do protocolo OAOMDV
Para ilustrar melhor como o protocolo resolve o problema do “route cutoff”, considera-se o exemplo da
rede da Figura 2-10. Assumindo que o nó S é o nó de origem e o nó D é o nó de destino e o pacote RREQ
com o “Last hop” X é designado por RREQ (X). O nó S irá fazer o broadcast do pacote RREQ para a rede.
Quando o nó A e B recebem o pacote RREQ, estes adicionam os seus próprios endereços no campo “Last
hop” dos seus respectivos pacotes. O nó A faz broadcast do RREQ (A) e nó B faz broadcast de RREQ (B).
Depois de o nó C receber o RREQ (A) e RREQ (B), são formadas duas ligações disjuntas inversas (C-A-S) e
(C-B-S). O nó C irá enviar em broadcast o RREQ (A) caso não tenha nenhum percurso disponível para o nó
de destino, caso contrário responde com o pacote RREP para o nó S. Quando o nó E e F recebem o pacote
RREQ (A), estes formam respectivamente os caminhos inversos (E-C-A-S) e (F-C-A-S). Por último o nó de
destino D recebe sucessivamente RREQ (A) de E e F. Se D receber primeiro RREQ (A) de E, é definido o
percurso inverso (D-E-C-A-S). Quando ele recebe o segundo RREQ (A) de F, na qual tem o mesmo “Last
hop” não é formado o percurso inverso (D-F-C-A-S).
S
A
B
C D
E
F
RREP (E)
RREP (E)
RREP (E)
RREP (E)
RREP (F)
RREP (F)
RREP (F)
RREP (F)
Direção do RREQ
Percurso directo
Figura 2-10:Processo de definição de percurso directo - protocolo OAOMDV.
27
O nó de destino D responde para E com o pacote RREP, depois de ter copiado o “Last hop” do RREQ (A)
para dentro do campo “ACK” do pacote RREP (ACK =A). Quando o nó E receber o RREP, irá adicionar o seu
endereço no campo “Last hop” do pacote RREP para identificar o percurso disjunto no sentido directo de
transmissão. É formado o percurso directo (E-D) e o nó E retransmite o RREP (E) para o próximo “next-
hop”. Como o caminho inverso (D-E-C-A-S) via E já esta bem definido, então o”next-hop1” é o nó C. O nó C
irá formar o percurso (C-E-D) e transmitir o pacote RREP (E) para seus próximos nós (“next-hop1 = A” ou
next-hop2=”B”). Por último quando o nó origem S receber RREP (E), será formado o percurso directo (S-A-
C-E-D). O nó D irá receber RREQ (A) do nó F pouco tempo depois e responde para F com um RREP. O
campo ACK do pacote RREP é definido com o valor do “Last hop” do pacote RREQ (A). O Nó F conhece o
percurso para o nó de origem S gerado pelo pacote RREQ durante o processo de descoberta, portanto,
considera como o “next-hop1” o nó C. Quando o nó C receber o RREP (F), define-se o percurso directo (C-F-
D) e depois procura o próximo salto para de origem S. O Nó C tem duas ligações disjuntas no percurso
inverso (C-A-S) e (C-B-S) uma das quais já tinha sido utilizado para transmitir o RREP (E).
Consequentemente, irá transmitir o pacote para o percurso via o nó B. Finalmente um outro percurso
directo (S-B-C-F-D) irá ser considerado pelo nó de origem S, uma vez que o “Last hop” de RREP (F) é
diferente de RREP (E).
S
A
B
C D
E
F
Direção do RREQ
Percurso directo
Percurso inverso
RREP_ACK
RREP_ACK
RREP_ACK
RREP_ACK
Figura 2-11:Processo de definição do percurso omitido - protocolo OAOMDV.
Na Figura 2-11, quando o nó origem S receber o primeiro pacote RREP (E) do seu vizinho A, ele irá
comparar o salto anterior do pacote RREP (E) com o valor do campo “ACK” do pacote RREP (E). Como o
salto anterior e o valor do campo “ACK” é o mesmo igual ao nó A, então o caminho inverso (D-E-C-A-S) ao
longo do caminho directo (S-A-C-E-D) foi determinado com sucesso. Quando o nó origem S receber o
segundo RREP (F), conclui que eles são de nós diferentes, o salto anterior é o nó B e o do campo “ACK” do
pacote RREP (F) é o nó A. Isto significa que o caminho inverso ao longo do caminho directo (S-B-C-F-D)
definido por RREP (F) está escondido. O nó origem S irá gerar um RREP_ACK para o destino D ao longo do
caminho directo para formar o caminho inverso. O campo “Last rphop” é o nó B e o “Last fphop” é o nó F.
Quando o nó B receber o RREP_ACK, um caminho inverso (B-S) irá ser definido. Quando nó C receber o
RREP_ACK, um caminho inverso (C-B-S) irá ser definido. Por último o caminho inverso (D-F-C-B-S) irá ser
28
definido pelo destino D. O RREP_ACK não é só para definir o caminho omitido, mas também confirma a
conexão entre o nó fonte e o nó destino.
2.2.4 Mobility Prediction Ad-hoc on-demand multipath distance vector (MP-
AOMDV)
O protocolo Mobility Prediction Ad-hoc on-demand multipath distance vector (MP-AOMDV) é uma extensão
do protocolo AOMDV. O protocolo faz a predição da mobilidade com base na estabilidade geral dos
percursos, baseando na intensidade relativa do sinal das ligações ao longo destes percursos. Com base
nessas predições os vários caminhos são classificados com diferentes prioridades, de modo a ser utilizado
sempre o melhor caminho para o envio de dados. É utilizado como métrica a intensidade do sinal das suas
ligações em vez da contagem de saltos, uma vez que este é insuficiente para determinar a qualidade e
estabilidade de um percurso. Uma ligação com intensidade de sinal muito fraco, mesmo que tenha um
baixo número de salto, pode levar a perdas de muitos pacotes. Estudos realizados mostram que a métrica
da intensidade do sinal é mais eficiente do que a métrica de contagem de número de saltos [4]. Tendo em
consideração a característica dinâmica das redes MANET e a mobilidade dos terminais que provoca falhas
constantes na comunicação, foram proposta duas versões do protocolo MP-AOMDV:
Node-Disjoint MP-AOMDV
Link-Disjoint MP-AOMDV
O nó disjunto é uma versão mais restrita do que a versão de ligação disjunta, portanto, o número de
percursos alternativos descoberto é menor em relação à versão com ligações disjuntas. Uma vez que os
nós disjuntos determinam percursos completamente independentes, a falha de um percurso não tem
qualquer impacto sobre os restantes. Em alguns cenários, a versão com ligações disjuntas revela-se mais
útil do que a versão com os nós disjuntos, uma vez que determina um maior número de percursos
alternativos. A seguir explica-se cada uma das versões [4]:
Node - Disjoint MP-AOMDV
O propósito para determinar percursos alternativos entre o nó de origem e o nó de destino, é para que
quando o percurso principal falhar devido ao movimento do nó, um dos percursos alternativos possa ser
escolhido como próximo percurso principal para enviar pacotes, sem dar inicio a um novo processo de
descoberta de percursos. Uma forma de aumentar a probabilidade de os percursos alternativos serem
válidos depois de o percurso principal falhar é garantir que eles não têm nenhum nó e nem ligação em
comum. Para que isto seja possível, o protocolo MP-AOMDV implementou um mecanismo que calcula
vários percursos alternativos com os nós disjuntos. O pacote RREQ foi modificado de modo a transportar o
endereço IP do nó imediatamente a seguir ao nó de origem, para qual foi transmitido o pacote RREQ. O nó
destino usa esta informação para poder responder apenas a RREQs vindos de diferentes nós vizinhos do
nó de origem. Uma vez que cada nó intermédio envia apenas o primeiro pacote RREQ para o destino, cada
RREQ viaja ao longo de um percurso único desde nó de origem até o nó de destino. Desta forma, quando o
29
nó de destino responder com o RREP aos vizinhos diferentes do nó de origem, estes RREP chegam ao nó
de origem através de percursos de nós disjuntos. Para assegurar que os vários percursos alternativos
estão consistentes com as mudanças da topologia da rede, o nó de origem envia periodicamente uma
mensagem de actualização, designada por heartbeat para o nó de destino ao longo dos percursos
alternativos. Como o pacote heartbeat se propaga através dos percursos alternativos, cada nó ao longo do
percurso actualiza o pacote com a métrica mobility prediction (MP). O MP é uma medida relativa da
intensidade do sinal, com o qual um determinado nó recebe um pacote do seu vizinho e é dado por:
,
Onde é a potência do sinal do nó A que é recebido no nó B e é potência mínima com o qual o sinal
deve ser recebido para que a transmissão seja considerada como válida. O nó de origem inicializa o MP da
mensagem heartbeat com o valor 1 e encaminha-o para o nó de destino através dos percursos
descobertos. Os nós intermédios multiplicam o seu MP pelo valor contido em heartbeat. O nó destino
envia em unicast para a origem o pacote heartbeat depois de ter inicializado a 1. Com este procedimento,
todos os nós obtêm a informação sobre a qualidade da ligação bidireccional.
Os pacotes RREQs e RREPs foram modificados de forma a transportar o valor do MP durante o processo
de descoberta. O nó de origem determina vários percursos, e ordena-os numa lista de prioridade por
ordem decrescente do valor de MP. O percurso que possui maior valor de MP é considerado como
percurso principal. Quando a intensidade do sinal do percurso principal diminuir antes de o percurso
falhar, é alterado para um percurso alternativo com maior estabilidade. Poucos pacotes são perdidos e o
atraso da comunicação é minimizado.
Para a prevenção da oscilação na mudança de percurso entre principal e o alternativo é adoptado um
mecanismo, em que nó de origem altera o seu percurso principal para um percurso alternativo, se a
diferença entre a estabilidade do percurso alternativo em relação ao percurso principal for maior do que
um valor limiar de estabilidade pré-definido.
S
B
A
D
F
E
G
C H
RREQ (0.2)
RREQ (0.15)
RREQ (0.05)
RREQ (0.15)
RREQ (0.2)
RREQ (0.1)
RREQ (0.2)
RREQ (0.2)
RREQ (0.05)
RREQ (0.1)
RREQ (0.15)
Pacote descartado
Pacote transmitido
Figura 2-12:Processo de cálculo de nós disjuntos MP-AOMDV.
30
Consideremos a rede da Figura 2-12 para ilustrar o funcionamento da versão de nós disjuntos do
protocolo MP-AOMDV. O nó S é o nó de origem e o nó D é o nó de destino. O nó S inicia o processo de
descoberta enviando o pacote RREQ para rede. O nó A e B retransmitem o RREQ para o nó E. Neste
exemplo, vamos assumir que o nó E, recebe primeiro o RREQ do nó A e depois recebe do nó B. O nó E
retransmite o RREQ recebido do nó A para suas ligações de saída e descarta o pacote RREQ recebida do nó
B. O nó G e F retransmite o RREQ para o nó de destino D. Semelhantemente, o nó C envia o RREQ para o nó
de destino via nó H. O nó D envia o pacote RREP para o nó F e H e descarta o RREQ via nó G, uma vez que o
RREQ de G foi originado pelo mesmo vizinho que originou o RREQ via nó F. O nó destino apenas aceita
RREQ com diferentes nós vizinhos do nó de origem. Neste exemplo foram determinados pelo nó de origem
dois percursos de nós disjuntos para o nó de destino (S-C-H-D) e (S-A-E-F-D).
Link-Disjoint MP-AOMDV
Nesta versão é permitido que os percursos tenham nós em comum, mas as ligações devem ser únicas. Uma
vez que tem menos limitações do que a versão nós disjuntos, consegue-se obter mais percursos
alternativos. Para calcular os percursos com ligações disjuntas, esta versão baseia-se numa versão do
AOMDV modificada. Deste modo, cada nó apenas retransmite o primeiro RREQ para o nó de destino
durante o processo de descoberta. No entanto mantém uma lista de próximos saltos para cada RREQ
originado por vizinhos diferentes do nó origem. Tal como em node-disjoint MP-AOMDV, o RREQ contém
um campo indicando o primeiro vizinho do nó de origem através do qual o RREQ foi enviado. O nó destino
envia RREPs para cada nó antecessor único através do qual recebeu o RREQ. Quando um nó intermédio
receber o RREP, retransmite-o para o next-hop guardado no topo da sua fila de “next-hop” e depois remove
este nó da fila. Este esquema de retransmissão é repetido pelos restantes nós intermédios. Quando a fila
next-hop ficar vazia, todos os RREP recebidos são descartados. Quando temos um número de ligações
desiguais upstream e downstream, o excesso de ligações não utilizadas no encaminhamento expira por
timeout. Cada nó intermédio mantém um mapeamento de um para um entre os vizinhos de upstream7 e
downstream8. Como o nó de destino envia RREP para seus diferentes nós vizinhos, e os RREPs são
transmitidos pelos diferentes “next-hop” pelos nós intermédios, todos os percursos obtidos pelo nó de
origem são ligações disjuntas. Para a manutenção dos percursos alternativos, assim como no caso de node-
disjoint MP-AOMDV, a mensagem heartbeat é enviada periodicamente ao longo dos percursos alternativos.
Cada nó usa o mapeamento entre os nós upstream e downstream para encaminhar as mensagens
heartbeat. A mensagem de heartbeat acumula a informação da intensidade do sinal em ambos os sentidos:
para o destino e para o nó de origem. Este valor acumulado de MP é utilizado pelos nós intermédios,
origem e o nó de destino para ordenar seus respectivos percursos alternativos em ordem decrescente do
valor de MP.
Para ilustrar o exemplo de cálculo de percursos com ligação disjunta, considera-se a rede da Figura 2-12.
Tal como no caso de percurso de nós disjuntos, o nó E recebe primeiro o RREQ do nó A e depois recebe do
7 Upstream - é a ligação com o sentido directo da comunicação, ou seja, do nó de origem para o nó de destino. 8 Downstream - é a ligação com o sentido inverso da comunicação, ou seja, do nó de destino para o nó de origem.
31
nó B. O nó E transmite o RREQ recebido do nó A para as suas ligações de saída. O RREQ recebido do nó B
não é retransmitido, mas é inserido na lista de “next-hop” para o nó de origem. O nó destino recebe o RREQ
dos nós G, F e H. O nó destino envia RREP para cada um dos vizinhos distintos. O nó E recebe o RREP dos
nós F e G, depois encaminha o RREP do nó F para o nó A, e o do nó G para o nó B. O nó E procede desta
forma devido ao mapeamento entre a lista de “next-hop” e da lista de “previous-hop” criadas durante o
processo de descoberta. Da mesma forma um RREP é encaminhado através do percurso (D-H-C-S). O nó de
origem obtém três percursos com ligações disjuntas para o destino D e são (S-C-H-D), (S-A-E-F-D) e (S-B-E-
G-D).
2.2.5 New Multipath Node-Disjoint routing based on AODV protocol (NMN –
AODV)
Este protocolo resulta de algumas alterações que foram realizadas ao protocolo AODV para poder
determinar vários percursos. O protocolo NMN-AODV utiliza múltiplos percursos de nós disjuntos para
minimizar o atraso da comunicação extremo-a-extremo e balancear a carga pela rede. Através de três
pacotes de controlo determina dois percursos de nós disjuntos entre o nó de origem e o nó de destino. Da
mesma forma, assim como o protocolo MP-AODV, foi adicionado um nova flag F de 1 bit aos pacotes RREQ
e RREP. Quando o nó intermédio recebe o pacote RREQ, guarda o ID RREQ do nó origem e o valor da flag
“F” na tabela de encaminhamento. No protocolo AODV, quando um nó receber o pacote verifica o par
<SOURCE IP, RREQ ID> do pacote RREQ e compara com a informação contida na tabela de
encaminhamento para decidir se retransmite o pacote ou não. O protocolo NMN-AODV faz o
processamento do pacote RREQ e distingue o percurso principal do percurso alternativo com base no
valor da flag F.
Inicia-se o processo de descoberta de percursos quando um determinado nó pretende transmitir dados
para o nó de destino e não possui percursos disponíveis na tabela de encaminhamento. Envia-se para a
rede em broadcast o pacote RREQ, com a flag F inicializado com o valor zero, para poder calcular o
percurso principal. Os nós intermédios, quando receberem o pacote RREQ com a flag F igual a zero, fazem
o procedimento igual ao do protocolo AODV convencional.
Quando o nó de destino receber o pacote RREQ (F=0), responde com o pacote RREP (F=0) para o nó de
origem, e depois de passar o tempo de NET_TRAVERSAL_TIME milissegundos envia o RREQ (F=1). Para
poder definir o percurso alternativo do percurso principal, é definida a flag D, de modo a garantir que o
pacote RREQ será recebido pelo nó destino pretendido. Quando o nó de origem receber o RREP (F=0), o
percurso principal é formado e inicia-se a transmissão. Quando receber o pacote RREQ (F=1), o percurso
alternativo é formado e inicia-se a transmissão com “piggybacking” RREP (F=1) neste caminho alternativo
e simultaneamente enviando dados no percurso principal. O nó de destino, quando receber o pacote RREP
(F=1) descarta-o. Quando um nó intermédio receber o pacote RREQ (F=1), compara <SOURCE IP,
Destination IP> do pacote RREQ com o par <Destination IP, SOURCE IP> contido na sua tabela de
encaminhamento. Caso seja igual, tratando-se de um nó que pertence ao percurso principal, o pacote é
32
descartado, caso contrário o pacote é encaminhando segundo o procedimento do protocolo AODV
convencional [14].
2.2.6 Multipath Optimized Link State Routing Protocol (MP-OLSR)
O protocolo MP-OLSR resulta da alteração ao protocolo clássico OLSR para o cálculo de vários percursos
entre o nó de origem e o nó de destino. Assim como o OLSR clássico, o MP-OLSR envia as mensagens de
hello e TC periodicamente para estar ciente das mudanças de topologia da rede. No entanto, o MP-OLSR
não mantém sempre a tabela de encaminhamento: ele só calcula os percursos quando um nó precisa
enviar pacotes. O funcionamento do protocolo MP-OLSR baseia-se em dois mecanismos essenciais de
funcionamento: Monitorização da topologia (Topology Sensing) e cálculo de rotas (routes computation)
[15].
A monitorização da topologia faz com que os nós obtenham a informação sobre a topologia da rede, o que
inclui a monitorização da ligação (link sensing), detecção de vizinhos (neighbor detection) e descoberta de
topologia (topology discovery). A descoberta de topologia beneficia dos MPRs tal como no OLSR [ver 2.1.4],
para minimizar a inundação dos pacotes de broadcast na rede através da redução de retransmissão de
pacotes duplicados na mesma região. Para o cálculo dos percursos utiliza-se o Multipath Dijkstra
Algorithm (MDA) para preencher os múltiplos percursos com base nas informações obtidas a partir da
monitorização da topologia. Uma das várias alterações que foram realizados ao OLSR para o
encaminhamento multi-percurso, é que as mensagens de TC não incluem apenas as ligações entre o nó
local e o MRP, mas contêm também as ligações para todos os vizinhos, de maneira que cada nó possa ter
mais informação sobre a topologia da rede, podendo deste modo construir facilmente múltiplos percursos
disjuntos. Para efeitos de simulação, ele apresenta um bom desempenho quando se tem uma carga baixa.
Mas em cenário em que há carga elevada, ele vai causar mais congestionamento, porque este método irá
aumentar o tamanho da mensagem de TC. No entanto, com a mensagem que combina o mecanismo em
OLSRv2 este problema pode ser aliviado [16].
33
Figura 2-13:O algoritmo Dijkstra de multi-percuros. [fonte: [15]]
Contrariamente do OLSR clássico, os percursos não são actualizados cada vez que um determinado nó
recebe uma mensagem nova de encaminhamento. Eles são actualizados através do envio das mensagens
On-demand, a fim de evitar o cálculo dos vários percursos para cada destino possível. Quando um
determinado nó tiver que enviar pacotes, inicia-se o procedimento de cálculo de percursos como se
descreve no algorítmico seguinte: O princípio geral do algoritmo é, numa etapa i, procurar o caminho Pi
mais curto para o nó de destino d. Em seguida aumentar o custo da aresta de Pi e das arestas apontado
para Pi, a fim de evitar que os próximos passos utilizem caminhos idênticos. O fp é usado para aumentar o
custo das arestas que pertencem ao caminho antecessor ao Pi (ou arestas que pertencem a caminho
oposto a Pi). Isto incentiva os caminhos futuros a usarem arestas diferentes, para atingir os mesmos
vértices (nós). O fe é utilizado para aumentar o custo das arestas que unem caminhos a vértices (nós) do
percurso anterior a Pi. Pode-se escolher diferentes valores de fe e fp para obter percursos com ligações
disjuntas ou percursos com os nós disjuntos conforme o necessário. A Figura 2-14 ilustra o número de
percursos diferentes calculados pelo algoritmo Dijkstra num cenário de 300 nós.
Figura 2-14: Algoritmo Dijkstra com fp (c) = fe (c) = 2c. Na primeira figura foram calculados 3 percursos e
na segunda figura foram calculadas 10 percursos [fonte: [15]].
34
Quanto ao processo de descoberta de percurso, no OLSR clássico é utilizado o encaminhamento salto-a-
salto, o que significa que quando um pacote chega a um nó intermédio, o protocolo verifica a tabela de
encaminhamento do nó local, e em seguida encaminha o pacote para o próximo salto (nó). Em contraste,
no MP-OLSR os nós intermédios ajudam o nó de origem a manter um bom controlo dos pacotes que serão
encaminhados nos múltiplos percursos. A curto prazo, o encaminhamento de origem puro pode causar
dois problemas: Em primeiro lugar, a informação no nó de origem pode não ser suficientemente actual,
pois precisa de tempo para inundar as mensagens de controlo de topologia para toda rede. O que significa
que quando o nó determina o percurso, pode utilizar ligações que já não existem ou estão obsoletas. Em
segundo lugar, mesmo quando a informação no nó de origem está actualizada, a topologia da rede pode
alterar-se durante o encaminhamento do pacote. Ambos os problemas causam falha de encaminhamento
de pacotes.
Para resolver o problema, cada nó intermédio antes de encaminhar o pacote para o próximo nó de acordo
com o percurso enviado pelo nó de origem, verifica primeiro se próximo nó é um dos seus vizinhos. Em
caso afirmativo, o pacote é transmitido. Caso contrário, é possível que o próximo nó se tenha
movimentado para fora do intervalo de transmissão, portanto, o nó intermédio recalcula o percurso e
envia o pacote através de um novo percurso. Na Figura o nó de origem A possui dois percursos para o nó
de destino D, (A-B-C-D e A-E-F-G-D). Quando é enviado um pacote via o nó E, este antes de o encaminhar
para o próximo nó indicado no percurso mantido pelo nó de origem, verifica primeiro se é o seu vizinho.
Neste exemplo o nó E encaminha o pacote para o nó F, uma vez que é seu vizinho. O nó F quando recebe o
pacote, com base no percurso mantido pelo nó de origem, vai verificar se o nó G é seu vizinho, mas como
este esta fora da sua zona de cobertura conclui que não é seu vizinho. O nó F recalcula o percurso e envia o
pacote para o destino D via o nó H.
A
B C
E F
D
H
G
Figura 2-15: processo de descoberta de rota pelo nó F.
2.2.7 Considerações finais e conclusão
Neste subcapítulo [2.2], foram estudados alguns dos principais protocolos com encaminhamento multi-
percurso, utilizados nas redes MANET. Estes protocolos resultaram de alterações, realizadas aos
protocolos de encaminhamento com percurso único. Os protocolos MP-OLSR, MOLSR e QOLSR são
protocolos pró-activos com encaminhamento multi-percurso e têm como protocolo de base o protocolo
OLSR. O protocolo MOLSR determina múltiplos percursos, apesar de utilizar um percurso em cada
momento, tendo como vantagem a ausência do problema de acoplamento de percursos (percursos
sobrepostos) [1]. O protocolo QOLSR procura percursos que consigam satisfazer um conjunto de
requisitos de largura de banda e de latência [17]. Estes protocolos possuem o núcleo de funcionamento
35
comum, que permite descobrir a topologia da rede. As desvantagens dos protocolos pró-activos resultam
do elevado custo de distribuição dos anúncios. Mesmo quando se utilizam mecanismos (por exemplo,
recorrendo a multipoint relays) para mitigar estes custos, uma vez que todos os nós necessitam de
difundir anúncios, estes protocolos incorrem em elevados custos de sinalização, em particular nas redes
densas. Uma outra desvantagem destes protocolos consiste no encaminhamento realizado com base nos
percursos armazenados no nó de origem. No presente trabalho apenas foi abordado o protocolo MP-OLSR,
dado que este é o que melhor resolve os problemas mencionados. O protocolo MP-OLSR determina vários
percursos que podem ser disjuntos em termos de nós ou de ligação, de acordo com várias funções de
custos. Embora o MP-OLSR realize o encaminhamento com base nos percursos armazenados no nó de
origem, ele proporciona uma melhoria neste procedimento, uma vez que os nós intermédios fazem
confirmação do percurso mantido pelo nó de origem, antes de encaminhar os pacotes para o nó de
destino.
Foram abordados também neste trabalho vários protocolos reactivos com encaminhamento multi-
percurso mais utilizados nas redes MANET. Dado que o protocolo implementado neste trabalho é um
protocolo reactivo com encaminhamento multi-percurso, deu-se mais ênfase a estes tipos de protocolos.
Os protocolos AOMDV e NMN-AODV tiveram como base o protocolo AODV, enquanto que o protocolo
OAOMDV e MP-AOMDV resultaram de algumas melhorias implementadas ao protocolo AOMDV. Estes
protocolos foram desenvolvidos para calcular vários percursos entre os nós de origem e de destino,
diferenciam-se um dos outros no modo de funcionamento. Alguns determinam os vários percursos a custo
da introdução de novas mensagens de sinalização, o que se verifica para o caso do protocolo OAOMDV
(RREP_ACK) e MP-AOMDV (heartbeat). O protocolo NMN-AODV e o AOMDV apenas introduzem novos
campos adicionais para poderem determinar os vários percursos. O protocolo MP-AOMDV apresenta
algumas características particulares, dado que utiliza como métrica para calcular os vários percursos a
intensidade do sinal, enquanto que os outros protocolos utilizam como métrica o valor de hop-count.
Alguns estudos demonstram que a métrica da intensidade do sinal é melhor, uma vez que o hop-count não
concede nenhuma informação sobre a qualidade de ligação dos percursos. O MP-AOMDV considera um
determinado percurso como óptimo, se a soma da intensidade das suas ligações for maior do que os
restantes. A intensidade do sinal é dimensionada com base na potência do sinal recebida de um
determinado nó. O MP-AOMDV faz a manutenção dos percursos alternativos extremo-a-extremo, através
do envio periódico da mensagem heartbeat desde o nó de origem até o nó de destino.
Os outros protocolos mencionados fazem a manutenção dos vários percursos alternativos através da
monitorização das ligações locais entre os nós vizinhos. Os nós que fazem parte do percurso activo enviam
entre si periodicamente a mensagem hello. Este procedimento é mais eficaz do que a manutenção
extremo-a-extremo, uma vez que quando houver uma falha de ligação é detectada de imediato. A
manutenção extremo-a-extremo é desvantajosa, uma vez que a informação sobre a qualidade do percurso
quando é recebida pelo nó de destino/origem, pode suceder que o mesmo percurso já esteja inválido.
36
Existem outros protocolos com encaminhamento multi-percurso interessantes que neste trabalho não
foram abordados, uma vez que não se enquadram dentro do âmbito deste trabalho. Como exemplo,
podemos mencionar a seguinte lista:
Multipath and MPR based AODV routing protocol (MMDV), [18];
Multi-Path DSR routing protocol (MP-DSR) , [19], [20];
Ad-hoc On-demand Distance Vector Multipath Routing Protocol (AODVM);
Ad-hoc On-Demand Distance Vector - Decoupled Multipath (AODV-DM);
Node Disjoint Minimum Interference Multipath (ND-MIM) [21];
Multi-path Dynamic Source Routing with Node Disjoint Routes (MDSR-NDR) [22];
Deste modo, finalizamos o capítulo do estudo sobre os protocolos de encaminhamento multi-percurso e
protocolos de encaminhamento com percurso único para as redes MANET.
37
38
3 Route Alternating Multipath AODV (RAM-AODV)
Neste trabalho foram estudados vários protocolos de encaminhamento multi-percurso, e conseguiu-se
constatar que é possível melhorá-los em alguns aspectos. Entre os vários protocolos estudados, os que
mais contribuíram para o desenvolvimento do protocolo apresentado neste trabalho foram: MP-AOMDV,
AOMDV, NMN-AODV e OAOMDV [4], [14], [3], [5]. Nos estudos realizados são mencionados alguns dos
problemas destes protocolos.
O protocolo AOMDV tem o problema de “route cutoff”. O protocolo OAOMDV resolve o problema de “route
cutoff” do protocolo AOMDV, mas com alguma sobrecarga adicional, uma vez que introduz um novo pacote
de controlo - RREP_ACK.
O protocolo MP-AOMDV tem o problema da definição do parâmetro limiar utilizado nas decisões de
mudança de percurso. A definição errada deste parâmetro pode provocar stress na rede e frequentes
mudanças entre o percurso principal e os percursos alternativos.
O protocolo NMN-AODV é um protocolo muito simples que consegue fazer encaminhamento multi-
percurso utilizando apenas as mensagens (RREQ, RREP, RRER etc.) do protocolo AODV. Apesar da sua
simplicidade, utilizando este protocolo, apenas é possível formar dois percursos entre os nós de origem e
de destino.
A fim de ultrapassar as limitações acima mencionadas, neste trabalho é proposto o estudo e a
implementação de um novo protocolo de encaminhamento multi-percurso RAM-AODV (Route Alternating
Multipath AODV). Este protocolo tem como objectivos minimizar a sobrecarga de rede, diminuir o atraso
da comunicação extremo-a-extremo e realizar o encaminhamento multi-percurso de modo a apresentar
bons desempenhos em redes densas e com suporte a mobilidade. Este é uma extensão do protocolo AODV
para o encaminhamento multi-percurso. Para determinar percursos não sobrepostos, teve-se como
protocolo de base o protocolo MP-AOMDV [4]. Neste último, tal como já foi mencionado, são
implementadas duas versões: percursos com ligações disjuntas e percursos com os nós disjuntos (RAM-
AODV é um compromisso entre as estas duas versões).
3.1 Formato das mensagens
O pacote Route Request (RREQ) é utilizado pelo nó de origem para iniciar o processo de aquisição de
percursos. Para poder determinar vários percursos foram introduzidos dois campos adicionais no pacote
RREQ. O primeiro campo adicional é o Neighbor IP Address que é utilizado para enviar o endereço IP do nó,
através do qual foi recebido o pacote RREQ. É com base nesta informação que o nó de destino calcula os
vários percursos alternativos. O segundo campo adicional é o Max Num Routes, e este é utilizado para
transportar a informação sobre o número máximo de percursos alternativos a serem determinados. A
explicação detalhada do processamento destes campos adicionais é apresentada na secção 3.5.
39
TYPE
J
R
G
D
U
Reserved
Hop Count
RREQ ID
Destination IP Address
Destination Sequence Number
Originator IP Address
Neighbor IP Address
Originator Sequence Number
Max Num Routes
Figura 3-1:Formato do pacote Route Request – RREQ.
O pacote Route Reply (RREP) é enviado pelo nó de destino em resposta ao pacote RREQ. A alteração
realizada neste pacote consiste apenas na introdução de um campo adicional - o Max Num Routes. Na
Figura 3-2 estão ilustrados os campos do pacote RREP.
TYPE
R
A
Reserved
Hop Count
Destination IP Address
Destination Sequence Number
Originator IP Address
Originator Sequence Number
Max Num Routes
Prefix SZ
Figura 3-2:Formato do pacote Route Reply – RREP.
O pacote Route Error (RRER) é enviado pelos nós, quando estes detectam falhas de ligações. Este pacote
não foi alterado no protocolo desenvolvido. Na Figura 3-3 estão ilustrados os campos do pacote RRER.
TYPE
N
Reserved
DestCount
Unreachable Destination Sequence Number (1)
Additional Unreachable Destination IP Addresses
(if needed)
Unreachable Destination IP Address (1)
Additional Unreachable Destination Sequence Numbers
(if needed)
Figura 3-3:Formato do pacote Route Error - RRER.
40
O pacote RREP_ACK também não foi alterado. É utilizado por um determinado nó quando receber um
pacote RREP que carece de uma confirmação. Então o nó receptor do pacote RREP envia o pacote
RREP_ACK, para confirmar a recepção do pacote RREP. Na Figura 3-4 estão ilustrados os campos do
pacote RREP_ACK.
TYPE
Reserved
Figura 3-4: Formato do pacote Route Reply Acknowledgement - RREP_ACK.
3.2 Estuturas de dados
Várias estruturas de dados foram utilizadas para armazenar as informações processadas pelo protocolo,
entre as quais se destacam:
Tabela de encaminhamento
Tabela de vizinhos processados
Tabela de RREQ pendentes
Lista de próximos saltos
Tabela de contador de percurso (ver subsecção 3.3)
Todos os nós da rede possuem uma tabela de encaminhamento, e esta por sua vez pode ter ou não varias
entradas, consoante o número de pedidos (de percursos) recebidos para diferentes nós de destinos. A
título ilustrativo, considera-se um exemplo em que um determinado nó possui três percursos para
diferentes nós de destino (D1,D2 e D3). Neste caso a sua tabela de encaminhamento deve ter três entradas,
tal como ilustrado na Figura 3-5. Se um determinado nó possuir vários percursos para o mesmo nó de
destino, então a sua tabela de encaminhamento será composta por uma entrada referente ao nó de destino
e uma lista de próximos saltos.
Destination D1
Routing Table Entry 1
Destination D2
Routing Table Entry 2
Destination D3
Routing Table Entry 3
Figura 3-5: Formato da tabela de encaminhamento.
A Figura 3-6 ilustra os principais campos das entradas da tabela de encaminhamento.
41
NetDevice Ipv4InterfaceAddress Destination Sequence Number Source LNHRounteCountLive time Max Num Routes
Figura 3-6:Formato da entrada da tabela de encaminhamento.
Na Figura 3-7 está ilustrado o formato da lista de próximos saltos. Neste exemplo foi considerado uma
lista com três endereços de próximos saltos. O número de elementos da lista é limitado pelo valor do
campo Max Num Routes do pacote RREQ.
Hop Count 1Next Hop 1 Flag Status 1
Hop Count 2Next Hop 2 Flag Status 2
Hop Count nNext Hop n Flag Status n
Figura 3-7:Formato da lista de próximos saltos.
Os campos da lista de próximos saltos do exemplo ilustrado na Figura 3-7, são interpretados do seguinte
modo:
Next Hop: é o endereço IP do próximo salto.
Flag Status: é uma flag que indica o estado do percurso. Temos dois tipos de estados para
classificar um determinado percurso. A flag VALID significa que o percurso pode ser utilizado
para enviar dados. A flag INVALID significa que o percurso não pode ser utilizado para enviar
dados.
Hop Count: é o número de saltos a percorrer até chegar ao nó de destino.
A tabela de vizinhos processados consiste num mapeamento entre os endereços IP dos nós de origem e
estruturas de dados do tipo RREQData. Para cada RREQ recebido do nó de origem com diferentes vizinhos
a dois saltos do nó de destino, é estabelecido um mapeamento na tabela de vizinhos processados entre o
endereço IP do nó de origem com o RREQData. A Figura 3-8 ilustra um exemplo de uma tabela de vizinhos
processados referente ao nó de origem (Source 1), em que foram processados três RREQ com diferentes
nós vizinhos do nó que enviou o pacote RREQ para o nó de destino. Para o segundo nó de origem (Source
2), também foram processados três RREQ com diferentes nós vizinhos a dois saltos do nó de destino. O
índice n é dimensionado pelo valor do campo Max Num Routes da entrada da tabela de encaminhamento.
42
IP neighbor two hop 1
ID RREQ 1
IP neighbor two hop 2
ID RREQ 1
IP neighbor two hop n
ID RREQ 1
IP neighbor two hop 1
ID RREQ 2
IP neighbor two hop 2
ID RREQ 2
IP neighbor two hop n
ID RREQ 2
Source 1
Source 2
Figura 3-8:Formato da tabela de vizinhos processados.
A tabela de RREQ pendentes consiste também num mapeamento entre os endereços IP dos nós de origem
e as estruturas de dados do tipo RREQData. Para cada endereço IP do nó de origem apenas existe uma
entrada na tabela de RREQ pendentes. Isto deve-se ao facto de que os nós intermédios apenas processam
o primeiro RREQ e os restantes são descartados.
No exemplo da Figura 3-9 os campos da tabela têm o seguinte significado:
IP key Source: endereço IP do nó de origem que enviou o pacote RREQ.
IP next-previous: endereço IP do nó a partir do qual foi recebido o pacote RREQ. É para este
endereço IP que é enviado o pacote RREP para o nó de origem.
ID RREQ: identificador de cada pedido de aquisição de percurso.
IP Key Source 1
IP next – previous 1
ID RREQ 1
IP Key Source 2
IP next-previous 2
ID RREQ 2
IP Key Source 3
IP next – previous 3
ID RREQ 3
Figura 3-9:Formato da tabela de RREQ Pendentes.
3.3 Gestão de múltiplos percursos
A gestão do número de percursos a calcular entre os nós de origem e de destino durante o processo de
descoberta, tem impacto sobre a carga rede. Ao definir um número limitado de percursos a calcular,
diminui-se o número de pacotes de sinalização enviados para a rede, maximizando deste modo o tempo de
vida das baterias dos dispositivos, largura de banda e minimizando a sobrecarga da rede. Neste protocolo,
é definido um parâmetro que determina o número máximo de percursos entre o nó de origem e o nó de
43
destino e este é configurado manualmente pelo administrador da rede. Para assegurar que os dados são
enviados de forma balanceada pelos vários percursos determinados durante o processo de aquisição, o
protocolo dispõe de uma tabela de contador de percursos para variar a escolha de percurso para enviar os
pacotes. Esta tabela de contador de percursos é utilizada pelo nó de origem de forma a escolher percursos
diferentes para enviar dados para o nó de destino.
Destination D1
Counter Route For Destination D1
Destination D2
Counter Route For Destination D2
Destination D3
Counter Route For Destination D3
Figura 3-10:Tabela de Contador de percurso para o nó de destino.
Cada nó possui uma tabela de contador de percursos com zero ou mais entradas, consoante o número de
nós de destino para os quais o nó envia pacotes. Inicialmente o contador de percursos é inicializado a zero,
portanto, são enviados dados para o nó de destino, utilizando o endereço IP no início da lista de próximos
saltos. Depois de enviar o pacote, o contador de percurso é incrementado. Quando o valor de contador de
percursos for maior ou igual ao número de percursos na lista de próximos saltos, este é reinicializado a
zero. Para o exemplo da Figura 3-10, o nó possui uma tabela de contador de percurso com três entradas
para três nós de destino diferentes (D1,D2 e D3).
3.4 Manutenção dos percursos
Para a manutenção dos percursos alternativos, o protocolo utiliza dois mecanismos de manutenção:
Envio periódico da mensagem hello.
Envio da mensagem RREP_ACK.
O primeiro mecanismo consiste no envio periódico da mensagem hello. Esta mensagem só pode ser
enviada pelos nós vizinhos que fazem parte dos percursos activos, com o objectivo de actualizar o tempo
de vida e a validade das ligações locais. Como esta mensagem é enviada de forma periódica, se não for
recebida durante um período de tempo configurado, admite-se que houve uma quebra da ligação. Segue-
se então o procedimento de manutenção de percursos, em que é enviada a mensagem RRER para todos os
nós afectados. Os nós ao receberem a mensagem RRER, eliminam o percurso afectado na lista de próximos
saltos. Se este era o último percurso para enviar dados ao nó de destino, então elimina-se a entrada da
tabela de encaminhamento para o nó de destino em causa. O segundo mecanismo consiste em enviar o
pacote RREP solicitando a confirmação de que o pacote foi recebido. O tempo que o nó fica a espera da
confirmação do pacote RREP é pré-configurado e é limitado. Se não for recebida nenhuma confirmação,
44
então admite-se que houve uma quebra de ligação. Inicia-se o processo de manutenção dos percursos com
o envio da mensagem de erro para os nós que ficaram afectados.
3.5 O funcionamento do protocolo RAM-AODV
3.5.1 Processamento do RREQ
Quando o nó de origem tem que enviar dados para o nó de destino, este consulta a sua tabela de
encaminhamento, e se não tiver percursos disponíveis, inicia o processo de descoberta. O nó de origem
envia o pacote RREQ em broadcast para a rede. Quando os nós intermédios receberem o pacote RREQ,
com base nas informações <IP Originator, ID RREQ> verificam se o pacote recebido é novo ou se é uma
duplicação. Se o pacote for uma duplicação, é descartado, caso contrário é processado da seguinte forma:
incrementa-se o valor do “hop-count” e actualiza-se a entrada da tabela de encaminhamento com as
informações do pacote RREQ de forma a criar o percurso inverso em direcção do nó de origem. É registado
na tabela de RREQ pendentes o endereço IP do nó vizinho do qual foi recebido o RREQ e o identificador
único (RREQ ID) associado a cada aquisição de percurso [ver a secção 3.2]. Estas informações são
guardadas apenas para diferentes pacotes RREQ do nó de origem. Por último, o nó intermédio insere no
pacote RREQ o endereço IP do nó vizinho que lhe enviou o pacote RREQ e retransmite-o em broadcast
para a rede. O nó de destino responde a um número limitado de pacotes RREQ com diferentes vizinhos a
dois saltos. O número máximo de respostas é definido manualmente pelo administrador da rede. Depois
de atingir esse número máximo de respostas, todos os pacotes RREQ recebidos do mesmo nó de origem
são descartados. Quando o nó de destino receber o pacote RREQ, decide se irá responder ou não a este
pedido com base na informação guardada na tabela de vizinhos processados e no número de pacotes
RREQ que já foram respondidos. Se o endereço IP do vizinho a dois saltos do nó de destino contido no
pacote RREQ não estiver na tabela de vizinhos processados e o número de RREQ que já foram respondidos
for inferior ao número máximo permitido, então o nó de destino responde com o pacote RREP. Se o
vizinho a dois saltos for o nó de origem, o nó de destino responde-lhe mesmo que esteja na tabela de
vizinhos processados, desde que não seja atingido o número máximo de respostas. Não satisfazendo estas
condições, o pacote RREQ é sempre descartado pelo nó de destino. Depois de enviar o pacote RREP, o nó
destino incrementa o número de respostas e insere o vizinho do pacote RREQ na tabela de vizinhos
processados. A Figura 3-11 mostra os procedimentos realizados pelo nó de destino no processamento do
pacote RREQ.
45
INICIO
KeySrc = rreq.GetOrigem()IDRreq = rreq.GetID()
IPN = rreq.GetNeighbor()NR = RT.GetNR()
FIM
Bool result ;result = lookupNP(KeySrc ,RREQData)
NR = NR +1TVP.insert(KsySrc,RREQData)
Send RREP
Result = IsNodeOringin(IPN)
Result
TRUEFALSE
Key Src IP do nó de origem
NR Número de Rotas
IPN Endereço IP do vizinho
TVP Tabela de vizinhos processados
Estrutura de dados com dois campos
{IDRreq ,IPN}
RREQData
NR < NMR
NMR Number Maxim Route
result
TRUE
TRUE
FALSE
FALSE
TRUE
FALSE
FALSE
TRUE
Figura 3-11:Fluxograma do algoritmo implementado no nó de destino para processar o pacote RREQ.
3.5.2 Processamento do pacote RREP
O pacote RREP é gerado para responder ao pedido de aquisição de percurso inicializado pelo nó de
origem. Quando um nó intermédio receber o pacote RREP, incrementa o valor de “hop-count”, em seguida
verifica se existe ou não uma entrada na sua tabela de encaminhamento referente ao nó de destino
indicado no pacote RREP. Se não existir, uma nova entrada é criada e inserida na tabela de
encaminhamento. Caso contrário, esta é actualizada consoante os seguintes critérios:
Se o número de sequência da entrada da tabela de encaminhamento for inválido ou inferior ao
número de sequência contido no pacote RREP, toda a informação da entrada da tabela de
encaminhamento é substituída pela informação nova contida no pacote RREP.
Se o número de sequência à entrada da tabela de encaminhamento for igual ao número de
sequência contido no pacote RREP, mas o pacote RREP for recebido de um vizinho diferente, é
46
adicionado o endereço IP deste vizinho na lista de próximos saltos. Caso o pacote RREP seja
recebido de um vizinho que já consta na lista de próximos saltos, então a lista só é alterada caso o
valor de “hop-count” contido no pacote seja inferior ao valor contido na lista ou se o estado do
percurso da lista for diferente de VALID.
Depois de fazer as actualizações, com base no endereço IP do nó de origem, o nó intermédio consulta a
tabela de RREQ pendentes para descobrir o endereço IP do “next-hop” para enviar o pacote RREP. De
seguida, o pedido de aquisição de percurso para o respectivo nó de origem é eliminado da lista de RREQ
pendentes. Quando o nó de origem receber o pacote RREP, é efectuado o mesmo procedimento dos nós
intermédios. O nó de origem começa a enviar os dados para o nó de destino, mesmo sem ter recebido
todos os pacotes RREP.
3.5.3 Ilustração do funcionamento do protocolo através de um cenário.
Para ilustrar o funcionamento do protocolo, considera-se a rede da Figura 3-12.O nó S é o nó de origem e o
nó D é o nó de destino. O pacote RREQ (X, Y) é o pacote enviado pelo nó Y e proveniente do nó vizinho X. O
número máximo de percursos diferentes que podem ser determinados neste exemplo é quatro. O
processo de aquisição de percurso é iniciado pelo nó S, portanto este envia o pacote RREQ (S, S) em
broadcast para rede. Como se pode verificar o indicador do vizinho a dois saltos corresponde ao nó S, uma
vez que o nó S é o primeiro a enviar o pacote. De seguida o pacote é recebido pelo nó A, B e C, portanto, são
formados os seguintes percursos inversos: (A-S), (B-S) e (C-S). O nó A envia o pacote RREQ (S, A) e o nó B
envia o pacote RREQ (S, B) e o nó C envia RREQ (S, C) para rede. Para o percurso via o nó E, não é
descartado nenhum pacote RREQ. O nó E envia a seguinte cópia RREQ (A, E), e seguindo este
procedimento o nó destino vai receber o pacote RREQ (E, K). O nó B envia para o nó F RREQ (S, B), e o nó F
por sua vez, regista o pedido do nó B na tabela de RREQ pendentes e retransmite o pacote RREQ (B, F)
para a rede. Pouco tempo depois o nó F recebe a cópia do RREQ do nó C, mas este é descartado. Quando os
nós J e G receberem o RREQ do nó F, estes retransmitem para a rede as suas respectivas cópias RREQ (F, J)
e RREQ (F, G). Os nós H e I irão fazer o mesmo procedimento quando receberem o pacote RREQ (F, G).
De acordo com a sequência com que foram enviados os pacotes, o RREQ (E, K) é o primeiro a ser recebido
pelo nó de destino. O nó de destino insere o nó E na tabela de vizinhos processados, incrementa o
contador de número de percursos e depois responde com o pacote RREP para o nó K. Pouco tempo depois,
o nó de destino recebe o RREQ (F, J) do nó J. Como o contador de rotas é inferior ao número máximo de
percursos e o vizinho do nó J ainda não foi processado, o nó destino efectua o mesmo procedimento.
Depois o nó de destino vai receber o RREQ (G, I) e responde com o pacote RREP. Por último o nó destino
irá receber o pacote RREQ (G, H), mas este pacote é descartado porque o vizinho G já tinha sido processado
e inserido na tabela de vizinhos processados. É importante ter em consideração que a regra de não
responder a pacotes com mesmo vizinho a dois saltos só é válida se o vizinho for diferente do nó de
origem.
47
Quando os nós intermédios recebem o pacote RREP, encaminham-no para o nó de origem com base no
endereço IP guardado na tabela de RREQ pendentes. Quando o nó K receber o RREP do nó de destino, com
base na tabela de RREQ pendente encaminha-o para o nó E. Seguindo este procedimento o pacote é
encaminhado até ao nó S, e fica assim definido o primeiro percurso (S-A-E-K-D). Quando o nó J receber o
pacote RREP do nó de destino, encaminha este pacote para o nó F. O nó F, com base na informação
guardada na tabela de RREQ pendentes, envia o RREP para o nó B, e depois o nó B encaminha o pacote
para o nó de origem, e é formado o segundo percurso (S-B-F-J-D). Quando o nó I receber o pacote,
encaminha-o para o nó G e este por sua vez encaminha-o para o nó F. O nó F conclui que não tem nenhum
pedido pendente na tabela de RREQ pendentes, portanto não encaminha o pacote para o nó de origem,
mas é formado o percurso (F-G-I-D). Assim, no final do processo de descoberta, o nó de origem S pode
enviar os pacotes para o nó de destino D através dos seguintes percursos: (S-A-E-K-D), (S-B-F-J-D) e (S-B-F-
G-I-D).
S
GC
JFB D
KEA
I
H
RREQ (S,S)
RREQ(S,A) RREQ(A,E)
RREQ (E,K)
RRESQ(S,S) RREQ(S,B)
RREQ(S,S) RREQ(S,C)
RREQ(B,F) RREQ(F,J)
RREQ(F,G)
RREQ(G,I)
RREQ(F,G)
RREQ(G,H
)
RREQ(B,F)
Pacotes descartados
Pacotes transmitidos
Number Maxim Route = 4
Figura 3-12: Processo de descoberta de rota do protocolo RAM-AODV.
48
4 Resultados de Simulação
Neste capítulo são apresentados e analisados os resultados dos testes efetuados para verificar o
desempenho do protocolo RAM-AODV. Para implementação e simulação do protocolo, neste trabalho foi
utilizado o simulador Network Simulator (NS-3 versão 3.10). O NS-3 é um simulador de rede que foi
desenvolvido para fins académicos e de investigação. Este simulador é uma nova alternativa ao popular
Network Simulator 2 (NS-2) [23] . É um software open-source, distribuído sob a licença GNU GPLv2,
disponibilizado gratuitamente para investigação e desenvolvimento. O NS-3 é desenvolvido utilizando a
linguagem C++ e com interface opcional em Python. O simulador possui uma extensa documentação
relativa à sua Application Programming Interface (API). O NS-3 está disponível para várias versões dos
sistemas operativos Linux, Mac OS X e Windows (neste através da utilização da ferramenta Cygwin) [6].
O NS-3 suporta scripts escritos em linguagens C++ e Python. Neste trabalho optou-se por escrever os
scripts em linguagem C++. Para obter os resultados do desempenho do protocolo desenvolvido, foram
implementados dois cenários:
Cenário 1 – rede estática.
Cenário 2 – rede dinâmica.
Para cada um destes cenários foram realizados vários testes e determinados os parâmetros indicadores da
qualidade de serviço (QoS).
4.1 Método de recolha de dados
O procedimento de avaliação do desempenho do protocolo foi dividido em três fases. A primeira fase
consiste na implementação do cenário para testar o desempenho do protocolo, em que são definidos:
Parâmetros da simulação;
Características do meio de comunicação;
Configuração da topologia da rede9;
Instalação do protocolo desenvolvido nos dispositivos e das aplicações para testar o protocolo [ver
Apêndice A]
A definição dos parâmetros de simulação e das características do meio da comunicação consiste na
escolha dos seguintes parâmetros:
Modelo de propagação;
9 A topologia é a forma como os dispositivos (nós) estão interligados na rede.
49
Protocolo de transporte;
Tempo de simulação;
Distância entre os nós;
Escolha do nó emissor e do nó receptor;
Tamanho dos pacotes em bytes;
Número máximo de pacotes a serem enviados;
Intervalo de envio dos pacotes;
Número de nós da rede;
Definição ou não de qualidade de serviços (QoS) para a tecnologia sem-fios;
Tecnologia sem-fios utilizada.
A seguir são apresentados os parâmetros considerados mais relevantes e que são constantes para os
dois cenários (topologias estática e dinâmica).
Tabela 4-1: Definição dos parâmetros constantes para os dois cenários.
Parâmetros Valores
Tempo de simulação 100s
Protocolo de transporte Protocolo UDP
Tecnologia IEEE 802.11b
Modelo de propagação Valores por omissão do NS-3
Distância entre os nós 20m
Número de nós na horizontal 10
Tamanho dos pacotes 256 Bytes
Número de pacotes enviados em cada simulação 500
Os valores por omissão de propagações utilizadas pelo NS-3 são:
ConstantSpeedPropagationDelayModel: define uma velocidade de propagação constante, sendo o
valor inicial por omissão igual à velocidade da luz ( .
LogDistancePropagationLossModel: define que as perdas de propagação são baseadas no modelo
do logaritmo da distância definido por:
50
Onde os significados dos parâmetros e os seus respectivos valores por omissão são:
n: coeficiente de atenuação que caracteriza o meio de propagação (n=3);
: distância de referência (m), o valor por omissão é 1m;
: atenuação de referência (dB), sendo o valor inicial 46.6777dB (obtido pela equação de Friis
usando a distância de 1m à frequência 5.15 GHz);
: distância (m);
: perdas de propagação (dB);
Para além dos parâmetros que foram definidos para testar o desempenho do protocolo, há também que
definir um conjunto de atributos que são utilizados pelo protocolo de encaminhamento para o cálculo dos
varios percursos. A Tabela 4-2 apresenta todos os atributos que foram utilizados pelo protocolo RAM-
AODV e o protocolo AODV durante o processo de descoberta de percursos.
Tabela 4-2: Atributos e valores por omissão.
Atributos Valores Definição
RreqRetries 2 O número máximo de retransmissões de RREQ com TTL =
NetDiameter para descobrir um percurso.
NetDiameter 35 O NetDiameter mede o número máximo de saltos possíveis entre dois
nós na rede.
RreqRateLimit 10 O número máximo de RREQ por segundo.
ActiveRouteTimeout 1s Período de tempo durante o qual o percurso é considerado válido.
NodeTraversalTime
(NodeTT)
40ms NodeTraversalTime é uma estimativa conservadora do tempo médio
da travessia de um salto dos pacotes e deve incluir os atrasos de fila,
tempos de processamento de interrupção e os tempos de
transferência.
NetTraversalTime NTT Estimativa do tempo médio efectivo da travessia.
PathDiscoveryTime (2) * NTT Estimativa do tempo máximo necessário para encontrar um percurso
na rede.
MyRouteTimeout
(MRT)
MRT Valor do tempo de vida do percurso definido no campo do pacote
RREP gerado pelo presente nó.
HelloInterval 1s Cada HelloInterval o nó verifica se ele enviou uma transmissão dentro
do último HelloInterval. Se não tem, ele pode transmitir uma
51
mensagem Hello.
AllowedHelloLoss 2 Número de mensagens de Hello que pode ser perdido para uma
ligação válida.
DeletePeriod
(DT)
DP DeletePeriod indica um limite superior sobre o tempo que o nó A pode
considerar o vizinho B como um proximo salto activo para o nó de
destino D, enquanto o nó B possui rotas validas para o nó de destino
D.
NextHopWait 10ms *
NodeTT
Periodo de tempo de espera do RREP_ACK de um nó vizinho.
BlackListTimeout
(BLT)
BLT Tempo para o qual o nó é colocado na lista negra.
MaxQueueLen 64 O número máximo de pacotes que é permitido ao protocolo de
encaminhamento guarda no buffer.
MaxQueueTime 30s O período máximo de tempo que é permitido para um protocolo de
encaminhamento gaurdar um pacote no buffer.
NTT= (2*NetDiameter) * NodeTraversalTime.
MRT=2* max (PathDiscoveryTime, ActiveRouteTimeout).
DP =5 * max (ActiveRouteTimeout, HelloInterval)
BLT= (RreqRetries) * NetTraversalTime
NodeTT = NodeTraversalTime
Na segunda fase, define-se o número total de simulações por cada cenário, são escolhidas as métricas de
avaliação do desempenho do protocolo e é determinada a forma de variação dos parâmetros que
influenciam os resultados. Devido à aleatoriedade das simulações, optou-se por simular cada cenário
cinquenta vezes de modo a determinar o comportamento médio. O único parâmetro que é alterado
durante as várias simulações para o mesmo cenário é o valor do seed, os outros parâmetros permanecem
constante. As métricas que foram utilizadas para avaliar o desempenho do protocolo são as seguintes:
Atraso da comunicação extremo-a-extremo - neste atraso inclui todos os possíveis atrasos na
transmissão de dados. Inclui atrasos causados pelo buffer durante o processo de aquisição de
percursos, atrasos de filas-de-espera10 nas interfaces da rede, os atrasos de transmissão11 e de
retransmissão do MAC e os tempos de propagação12.
10 Atraso filas-de-espera - é o tempo que o pacote fica a espera nas filas-de-espera de um equipamento para ser transmitido a rede.
52
Jitter - numa rede Ad-hoc pode se entender a variação de atraso (Jitter), como sendo a variação
no tempo e na sequência de entrega de informações (ex.: pacotes) devido a variação de atraso na
rede. A rede e seus equipamentos impõem um atraso à informação e este atraso é variável devido
a uma séries de factores, a saber:
Tempo de processamento diferentes nos nós intermédios
Maior ou menor atraso nas filas-de-espera;
Taxa de pacotes recebidos – corresponde a uma fração de pacotes recebidos pelo nó de destino
do conjunto de pacotes que foram enviados pelo nó de origem.
Débito - o débito é o número de bits recebidos pelo nó de destino durante a simulação,
contabilizando os dados que são transmitidos efectivamente por unidade de tempo.
Tempo de simulação é o tempo total simulado, i.e., tendo como referência o relógio interno do
simulador.
Durante a simulação, para cada cenário é determinado o valor médio das métricas mencionadas acima.
A terceira fase consiste no processamento e análise de resultados.
4.2 Cenário 1 - Topologia estática da rede.
Neste cenário, pretende-se avaliar o desempenho do protocolo considerando uma topologia de rede
estática com forma de uma matriz de m linhas por n colunas. A variável m corresponde ao número de
linhas e por conseguinte ao número de nós na vertical, e a variável n corresponde ao número de colunas
(largura) e por conseguinte o número de nós na horizontal. Nesta topologia, os dispositivos não são
móveis, sendo assim, uma topologia estática. Um exemplo deste tipo de topologia está apresentado na
Figura 4-1.
11 Atraso de transmissão – corresponde ao tempo que o equipamento, como router, interface de rede etc., leva para transmitir um pacote para uma ligação. 12 Tempo de propagação - refere-se ao tempo que um sinal leva a percorrer o meio que está sendo utilizado.
53
No 3n
No 2n
No 3n-1
No n+3 No 2n-1
No 2 No 3 No 4 No n-1
No nNo n+2No n+1
No 2n+1 No 2n+2 No 2n+3
No 3n+1 No 3n+2 No 3n+3No 4n-1
No 1
No (m-1)n No (m-1)n+1 No (m-1)n+2 No (m-1)n+3 No (m-1)n +(n-1)
Figura 4-1: Exemplo de uma topologia estática lógica e genérica da rede.
Neste cenário foram realizados dois testes diferentes, para avaliar o desempenho do protocolo.
4.2.1 Teste de variação da densidade de rede
A variação da densidade da rede consiste em aumentar o número de nós por unidade de área. Este teste
foi realizado para o estudo do desempenho do protocolo RAM-AODV em comparação com o protocolo
AODV, ao variar o número de nós da rede. Para cada parametrização, foram realizadas cinquenta
simulações variando o valor de seed13. Calcula-se o valor médio sobre os valores obtidos, de modo a
garantir uma maior precisão nos resultados.
Para este teste, para além dos parâmetros definidos na Tabela 4-1, são definidos outros parâmetros que
são específicos. Optou-se por considerar 40 como o número de nós inicial e 80 como o número máximo de
nós da rede. A simulação foi realizada incrementando o número de nós em 10 unidades e fixando os
outros parâmetros da rede indicados na Tabela 4-3. O nó de origem, assim como está indicado na Tabela
4-3, corresponde ao primeiro nó da rede estática (primeira linha e primeira coluna da matriz). O nó de
destino por conseguinte é o último nó da rede (última linha e última coluna da matriz), a posição deste
acompanha o aumento do número de nós da rede.
Tabela 4-3: Definição dos parâmetros para o teste 1.
Parâmetros Valores
Número mínimo de nós 40
Número máximo de nós 80
Variação do número de nós 10
13 Seed - valor definido para gerar a sequência de números pseudo-aleatórios da simulação. É importante que cada simulação seja realizada com um valor diferente de seed.
54
Intervalo de envio dos pacotes 0.001s
Max Num Router 1,2,3,4
Nó de origem Nó 0
Nó de destino Nó {39, 49,59,69 e 79}
Os gráficos apresentados nesta secção permitem-nos analisar o desempenho do protocolo RAM-AODV,
quando for utilizado para realizar o encaminhamento com percurso único e o encaminhamento multi-
percurso. Para avaliar o desempenho do protocolo quando for realizado o encaminhamento multi-
percurso, foram realizadas três simulações com diferentes números de percursos (1, 2, 3 e 4 percursos).
Toda a abordagem feita ao desempenho do protocolo RAM-AODV, tem como referência os resultados do
protocolo AODV. O desempenho do protocolo RAM-AODV é considerado como sendo bom, se for melhor
do que o desempenho obtido pelo protocolo AODV, nas mesmas condições. Com o objectivo de determinar
o número óptimo de percursos (parâmetro Max Num Router) e de mostrar as vantagens de utilizar o
protocolo RAM-AODV em alternativa ao protocolo AODV, foi realizada nesta secção uma análise detalhada
dos vários gráficos que a seguir estão apresentados.
Figura 4-2: Valores médios do atraso extremo-a-extremo em redes estáticas, com número de nós variável.
O gráfico da Figura 4-2 permite-nos estudar o desempenho do protocolo RAM-AODV e do protocolo AODV,
ao comparar os seus respectivos valores médios de atraso. Para uma rede composta por 40, 50 e 60 nós,
obtêm-se menor atraso quando se realiza o encaminhamento com percurso único, utilizando o protocolo
RAM-AODV. Contudo o protocolo RAM-AODV (1 percurso), não foi considerado como a melhor solução,
uma vez que ao analisar o gráfico da Figura 4-4, para estes mesmos números de nós, só se consegue obter,
quando muito, uma taxa média de pacotes recebidos menor do que 20%. Para o protocolo RAM-AODV (2,3
e 4 percursos) nestas mesmas condições consegue-se obter uma taxa média de pacotes recebidos maior
0
0,2
0,4
0,6
0,8
1
1,2
1,4
1,6
1,8
2
40 50 60 70 80
Atr
aso
[s]
Variação de número de nós da rede
RAM-AODV (1 percurso) RAM-AODV (2 percursos)
RAM-AODV (3 percursos) RAM-AODV (4 percursos)
AODV
55
do que 80%. O protocolo AODV nestas mesmas condições teve uma taxa média de pacotes recebidos
aproximadamente de 40%. Para uma rede composta por 70 e 80 nós os resultados evidenciam o protocolo
RAM-AODV com mais de um percurso como sendo a melhor solução, não havendo vantagem em utilizar
mais do que 2 percursos.
Figura 4-3: Valores médios do jitter em redes estáticas, com número de nós variável.
O gráfico da Figura 4-3 apresenta o desempenho do protocolo AODV e RAM-AODV através do cálculo do
jitter. O comportamento do gráfico da Figura 4-3 é justificado com base nos valores do gráfico da Figura
4-2. Ao fazer a comparação entre os dois gráficos, conclui-se que os resultados estão coerentes. Foi
concluído a partir do gráfico do atraso [Figura 4-2], que o melhor desempenho é concebido pelo protocolo
RAM-AODV, ao realizar o encaminhamento multi-percurso com 2, 3 e 4 percursos. No entanto, não foi
possível concluir com clareza qual é o número óptimo de percursos. Ao analisar o gráfico do jitter [Figura
4-3], conclui-se que o melhor desempenho é obtido quando se realiza o encaminhamento multi-percurso,
utilizando o protocolo RAM-AODV com 2 percursos. Esta conclusão mantem-se inalterável,
independentemente do número de nós utilizados. O gráfico da Figura 4-4, mostra que o protocolo RAM-
AODV com 2 percursos obteve-se uma taxa média de pacotes recebidos sempre superior a 80%, enquanto
que para 3 e 4 percursos a partir de 60 nós, a taxa média de pacotes recebidos começa a diminuir. Ao fazer
uma análise comparativa entre o protocolo AODV e o protocolo RAM-AODV com base nos gráficos,
conclui-se que o protocolo RAM-AODV apresenta melhor desempenho.
Uma outra conclusão interessante que o gráfico do jitter realça, resulta do facto do protocolo RAM-AODV
com 1 percurso apresentar um comportamento completamente diferente do protocolo AODV. A partir do
gráfico da Figura 4-4 e o gráfico da Figura 4-5, chega-se à mesma conclusão.
0
0,005
0,01
0,015
0,02
0,025
0,03
0,035
0,04
0,045
40 50 60 70 80
Jitt
er[
s]
Variação de números de nós da rede
RAM-AODV (1 percurso) RAM-AODV (2 percursos)
RAM-AODV (3 percursos) RAM-AODV (4 percursos)
AODV
56
Figura 4-4: Valores de taxa média dos pacotes recebidos em redes estáticas, com número de nós variável.
Esperava-se que o protocolo RAM-AODV com 1 percurso tivesse um desempenho semelhante ou igual ao
protocolo AODV. No protocolo AODV foi permitido aos nós intermédios participarem no processo de
aquisição de percursos, permitindo-lhes responder a pacotes RREQ quando possuem percursos válidos
para o nó de destino. No protocolo RAM-AODV, apenas os nós de destino podem responder aos pacotes
RREQ, sendo que os nós intermédios estão limitados a encaminhar apenas o pacote RREQ. Esta
funcionalidade extra dos nós intermédios no protocolo AODV acelera o processo de aquisição de
percursos e diminui o número de pacotes descartados, contribuindo deste modo para uma melhoria do
desempenho do protocolo AODV. Para uma rede composta por 40, 50 e 60 nós o protocolo AODV
apresentou melhor desempenho do que o protocolo RAM-AODV com 1 percurso. A partir de uma rede
com 60 nós, o desempenho do protocolo AODV começa a diminuir significativamente, enquanto que para
o protocolo RAM-AODV houve uma melhoria no desempenho. Uma das causas da descida do desempenho
do protocolo AODV, está relacionada directamente com o congestionamento da rede, provocado pelas
mensagens de sinalização. Na medida em que aumenta o número de nós, aumenta também o número de
pacotes RREP enviados pelos nós intermédios, em virtude da resposta das mensagens broadcast RREQ.
Aumenta-se também o número de mensagens de hello enviados pelos nós que fazem parte de percursos
activos. Isto tudo contribui para o aumento da sobrecarga e do congestionamento da rede, resultando em
aumento de colisões entre pacotes e, consequentemente, do números de pacotes descartados pela rede.
0
10
20
30
40
50
60
70
80
90
100
40 50 60 70 80
Ta
xa
s d
e p
aco
tes
rece
bid
os
[%]
Variação do número de nós da rede
RAM-AODV (1 percurso) RAM-AODV (2 percursos)
RAM-AODV (3 percursos) RAM-AODV (4 percursos)
AODV
57
Figura 4-5: Valores médios do débito em redes estáticas, com número de nós variável.
De acordo com toda a análise feita sobre os resultados obtidos nesta secção, obtêm-se as seguintes
conclusões:
O encaminhamento multi-percurso realizado pelo protocolo RAM-AODV é mais eficiente e obtém-
se melhor desempenho do que o encaminhamento com percurso único realizado pelo protocolo
AODV.
Conclui-se também que para as redes densas (neste cenário rede composta por 70 e 80 nós) o
desempenho do encaminhamento multi-percurso diminui quando aumenta o número de
percursos entre o nó de origem e o nó de destino. Como se pode ver no gráfico da Figura 4-4 e da
Figura 4-5, a partir de 70 nós, o débito e a taxa média de pacotes recebidos começa a diminuir
para o RAM-AODV com 3 e 4 percursos. Uma das causas pelas quais o desempenho do protocolo
diminui quando aumenta o número de percursos entre o nó de origem e de destino, está
directamente relacionado com congestionamento provocado pelo aumento das mensagens de
sinalização. Por outro lado, quando aumenta o número de percursos entre o nó de origem e de
destino, passa-se a verificar interferência entre os percursos. A interferência entre os percursos,
designado por acoplamento de percursos, tem um impacto negativo nas comunicações e diminui
o desempenho.
Por último, conclui-se que permitir aos nós intermédios responder os pedidos de aquisição de
percursos, quando estes possuem percursos válidos para o nó de destino é vantajoso para redes
não muito densas (menos de 70 nós), tal como foi verificado nesta secção.
0
20
40
60
80
100
120
40 50 60 70 80
Dé
bit
o[k
bp
s]
Variação de número de nós da rede RAM-AODV(1 perucurso) RAM-AODV(2 perucursos)
RAM-AODV(3 perucursos) RAM-AODV(4 perucursos)
AODV
58
4.2.2 Teste de variação do intervalo de envio dos pacotes
Nesta secção é apresentado o desempenho dos dois protocolos ao variar o intervalo de envio dos pacotes.
Para realizar este teste foram definidos alguns parâmetros adicionais, que são específicos para este teste,
para além dos parâmetros da Tabela 4-1. Começa-se por considerar 80 como o número de nós da rede, o
número máximo de percursos (Max Num Router) utilizado pelo protocolo RAM-AODV para realizar o
encaminhamento multi-percurso é 2. Foi escolhido este valor, tendo em consideração os resultados
obtidos na secção 4.2.1. Foram realizadas várias simulações com diferentes valores de intervalos de envio
de pacotes, no entanto, apenas três valores foram considerados para construção do gráfico. Para
intervalos inferiores a 1e-04 s [AODV (0.66kbps), RAM-AODV (17.29kbps)], a taxa média de pacotes
recebidos e débito do protocolo AODV são praticamente nulos [Figura 4-8 e Figura 4-9]. Para intervalos
inferiores a 1e-05 s [AODV (3.42kbps), RAM-AODV (6.5kbps)] a taxa média de pacotes recebidos e débito
são praticamente nulos para o protocolo RAM-AODV. Por isso, foram considerados apenas estes três
intervalos, uma vez que, para intervalos inferiores a 1e-05 s, não é possível tirar qualquer conclusão sobre
o desempenho dos dois protocolos. Segundo o gráfico da Figura 4-6,para o intervalo 0.001s, ambos os
protocolos tiverem o mesmo atraso. Contudo, ao analisar o gráfico apresentado na Figura 4-8 e o gráfico
ilustrado na Figura 4-9, verifica-se que para esse valor de atraso, a taxa média de pacotes recebidos pelo
protocolo AODV é inferior a 20%, enquanto que para o protocolo RAM-AODV é mais de 80%. Conclui-se
então, que o protocolo RAM-AODV teve melhor desempenho do que o protocolo AODV, para este intervalo
de transmissão. Para os intervalos inferiores à 1e-04 s, o protocolo AODV teve um valor de atraso
constante, aproximadamente 0.8s, dando entender que o protocolo tem um comportamento estável para
intervalos inferiores a 1e-04 s. No entanto, de acordo com o gráfico da Figura 4-8, a taxa média de pacotes
recebidos pelo protocolo AODV foi nula, portanto, é razoável que o atraso mantivesse constante para
intervalos inferiores a 1e-04 s.
Figura 4-6: Valores médios do atraso extremo-a-extremo em redes estáticas, com intervalo de envio de
pacotes variável.
0
0,2
0,4
0,6
0,8
1
1,2
1,4
1,6
0,001 0,0001 1,00E-05
Atr
aso
[s]
Variação do intervalo de envio dos pacotes
RAM-AODV (2 Percursos) AODV
59
Figura 4-7: Valores médios do jitter em redes estáticas, com o intervalo de envio de pacotes variável.
O gráfico da Figura 4-7 apresenta o valor médio do jitter dos dois protocolos em ao variar o intervalo de
envio dos pacotes. Diminuir o intervalo de envio dos pacotes, significa aumentar o ritmo com o qual os
pacotes são enviados para a rede. Isto provoca o aumento do tráfego na rede e por conseguinte o
congestionamento e o aumento do número de pacotes descartados. Para o intervalo igual a 0.001s, o
protocolo RAM-AODV teve uma taxa média de pacotes recebidos superior a 80%, enquanto que para o
intervalo 0.0001s teve uma taxa média apenas de 20%. O valor do jitter diminuiu com a diminuição do
intervalo de envio dos pacotes, dado que diminuiu também o número de pacotes recebidos. Por outro
lado, se o valor do intervalo do envio dos pacotes for muito pequeno, como por exemplo 1.00E-05,
rapidamente a rede entra em saturação devido ao congestionamento. Apenas uma pequena quantidade de
pacotes é que se consegue fazer chegar ao nó de destino. Os resultados de atrasos e de jitter deixam de ser
de confiança estatisticamente, pois baseia-se em poucos pacotes recebidos. Ao comparar o gráfico do
atraso da Figura 4-6 com o gráfico do jitter da Figura 4-7, conclui-se que o jitter pode ser ignorado em
relação ao atraso, pois a diferença de ordens de grandeza permite utilizar um buffer para eliminar o jitter.
Para o intervalo de envio de pacotes igual 0.001s tem-se aproximadamente 0.714% do jitter para o
protocolo AODV e para o protocolo RAM-AODV (2 percursos) teve-se 0.428% do jitter, portanto, o jitter é
muito pequeno em relação ao atraso.
0 0,001 0,002 0,003 0,004 0,005 0,006 0,007 0,008 0,009
0,01
0,001 0,0001 1,00E-05
Jitt
er
[s]
Variação do intervalo de envio dos pacotes
RAM-AODV (2 Percursos) AODV
60
Figura 4-8: Valores de taxa média de pacotes recebidos em redes estáticas, com intervalo de envio de
pacotes variável.
O gráfico da Figura 4-8 apresenta a taxa média de pacotes recebidos em função da variação do intervalo de
envio dos pacotes. Os resultados mostram que o protocolo desenvolvido possui melhor desempenho do
que o protocolo AODV. Dado que o protocolo AODV possui apenas um percurso para enviar os pacotes, ao
aumentar o ritmo de envio dos pacotes, facilmente este percurso entra em congestionamento e muitos
pacotes são descartados. O protocolo RAM-AODV, por ter a possibilidade de utilizar mais de um percurso,
utilizando-os alternadamente para enviar os pacotes, consegue aproveitar o máximo da largura de banda
da rede através do balanceamento da carga. No gráfico da Figura 4-8 para intervalos de 0.001s o protocolo
RAM-AODV apresentou uma taxa média de pacotes recebidos de 85%, enquanto que o AODV apenas de
20%.
Figura 4-9: Valores médios do débito em redes estáticas, com intervalo de envio de pacotes variável.
0
10
20
30
40
50
60
70
80
90
0,001 0,0001 1,00E-05 Ta
xa
mé
dia
de
pa
cote
s re
ceb
ido
s [%
]
Variação do intervalo de envio de pacotes
RAM-AODV (2 percursos) AODV
0
10
20
30
40
50
60
70
80
90
100
0,001 0,0001 1,00E-05
Dé
bit
o [
Kb
ps]
Variação do intervalo de envio dos pacotes
RAM-AODV (2 Percursos) AODV
61
Apesar da grande evolução das tecnologias de comunicação sem-fios, estas ainda carecem de mecanismos
ou soluções que viabilizem a transferência de dados multimédia que requerem elevadas taxas de
transferência. Conforme o gráfico da Figura 4-9, em todos os resultados de simulação, o débito foi sempre
inferior a 100Kbps. Mas no que diz respeito à comparação entre os dois protocolos, o protocolo RAM-
AODV apresentou melhor desempenho do que o protocolo AODV. Apesar do débito máximo ser
aproximadamente de 90 kbps, com o protocolo desenvolvido neste trabalho foi obtida uma melhoria mais
do que 50%. É de salientar que se tivesse utilizado a tecnologia 802.11a ou 802.11g, consegue-se débitos
superiores aos que foram obtidos com a tecnologia 802.11b, em boas condições. No entanto, a norma
802.11b é mais robusta em relação a fenómenos de propagação, tais como o desvanecimento multi-
percurso.
4.3 Cenário 2 – Topologia dinâmica da rede
A segunda topologia utilizada é dinâmica, em que os dispositivos se podem movimentar dentro do limite
da área da simulação. Esta topologia pode ser considerada a mais importante, uma vez que a maioria dos
dispositivos utilizados actualmente nas comunicações sem-fios é móveis. O NS-3 disponibiliza vários
modelos de mobilidade. Apresentam-se em seguida alguns destes modelos:
Gauss Markov Mobility Model – o movimento dos dispositivos da rede está dependente de uma
cadeia de Markov. Utiliza-se uma matriz de probabilidade que nos permite determinar a próxima
posição do nó dentro do limite da área de simulação, para o próximo instante de tempo.
Random Direction 2d Mobility Model - os dispositivos escolhem aleatoriamente uma direcção e
percorrem esta direcção até atingirem o limite máximo da área de simulação. Uma vez alcançado
este limite, o nó aguarda por um período de tempo fixo e escolhe aleatoriamente uma outra
direcção angular (entre 0 e 180 graus), repetindo-se o processo.
Random Walk 2d Mobility Model – em intervalos de tempo fixos, os nós movem-se da sua
posição actual para uma outra posição escolhendo aleatoriamente a direcção e a velocidade do
movimento. Quando um nó chega ao destino, espera um intervalo de tempo constante,
escolhendo no final de forma aleatória um novo valor da velocidade e direcção para se mover. Os
valores de velocidades e de direcção escolhidos pelo nó em cada posição são independentes dos
valores escolhidos anteriormente.
Random Waypoint Mobility Model – é escolhida aleatoriamente uma posição inicial para cada nó
dada pela coordenada (x, y) onde x e y são uniformemente distribuídos no intervalo [Xmin, Xmax]
e [Ymin, Ymax], respectivamente. Em seguida, cada nó selecciona um ponto de destino (x', y') com
distribuição uniforme na área da rede. Os parâmetros (Xmin, Xmax, Ymin, Ymax) definem a área
da simulação. O nó escolhe também uma velocidade v uniformemente distribuída no intervalo
[Vmín, Vmax], onde Vmín e Vmax são possíveis velocidades mínima e máxima, respectivamente,
62
que um nó pode escolher, sendo 0 <Vmín <Vmax. Antes de iniciar seu movimento um nó
permanece parado por um tempo de pausa que pode ser fixo ou aleatório. Quando expirar este
tempo, o nó move-se em linha recta para o ponto (x’, y’) com a velocidade v escolhida. Ao atingir o
destino, o nó repete o procedimento.
Entre os vários modelos propostos neste trabalho, escolheu-se o modelo Random Waypoint Mobility
Model. Este modelo apresenta algumas características interessantes, tais como a possibilidade de
variarmos a velocidade do movimento do dispositivo e o tempo de pausa numa determinada posição.
Apesar das suas desvantagens, é um modelo muito utilizado no âmbito das investigações dos protocolos.
Neste cenário, é realizado um teste que pretende avaliar o desempenho do protocolo considerando a
mobilidade dos nós da rede. A mobilidade é uma das principais características das redes MANET,
portanto, é indispensável avaliar o desempenho do protocolo neste tipo de cenários.
Tabela 4-4:Definição dos parâmetros para o cenário da mobilidade.
Parâmetros Valores
Número de nós 80
Intervalo de envio dos pacotes 0.001s
Pausa dos nós 10
Dimensão da área da rede {Xmin = 0, Xmax = 1000}
{Ymin = 0, Ymax = 1000}
Velocidade mínima (1,4,12,20) m/s
Variação da máxima (4,8,16,24) m/s
Max Num Router 2
Modelo da mobilidade Random Waypoint Mobility Model
Nó de origem Nó 0
Nó de destino Nó 79
Para a obtenção dos resultados, foram realizadas várias simulações para diferentes valores de velocidade
de movimento dos nós da rede. A Tabela 4-4 apresenta as definições dos vários parâmetros utilizados na
simulação. Todos os parâmetros indicados na Tabela 4-1 e na Tabela 4-4 não variam durante a simulação.
Os únicos parâmetros que variam durante a simulação são as velocidades do movimento dos nós, o valor
de seed e a posição dos nós. Para o estudo do comportamento do protocolo neste cenário, foram
construídos quatro gráficos a partir dos resultados obtidos. Os resultados obtidos indicam que se
consegue melhor desempenho utilizando o protocolo RAM-AODV (2 percursos) em comparação com o
protocolo AODV.
63
Figura 4-10: Valores médios do atraso extremo-a-extremo em redes dinâmicas, com velocidade de
movimento dos nós variável.
O gráfico da Figura 4-10 apresenta os valores médios do atraso em função da variação da velocidade de
movimento dos nós. Pode-se constatar que ao excluir os efeitos estatísticos impostos pela aleatoriedade
da simulação e do modelo utilizado para o cenário de mobilidade, os dois protocolos tiveram o mesmo
desempenho a nível do atraso. Para concluir que o protocolo RAM-AODV (2 percursos) teve melhor
desempenho é necessário, juntamente com o gráfico do atraso, analisar os outros gráficos que foram
obtidos. Por exemplo, se analisarmos o gráfico da Figura 4-12 e da Figura 4-13, conclui-se que para o
mesmo valor de atraso, o protocolo RAM-AODV (2 percursos) apresenta melhores débitos e uma maior
taxa média de pacotes recebidos.
Figura 4-11: Valores médios do jitter em redes dinâmicas, com velocidade de movimento dos nós variável.
O gráfico da Figura 4-11 apresenta valores médios de jitter do protocolo AODV e RAM-AODV (2
percursos), considerando a mobilidade dos nós. Ao fazer uma análise comparativa do gráfico do jitter da
0
0,5
1
1,5
2
2,5
[1,4] [4,8] [12,16] [20,24]
Atr
aso
[s]
Variação da velocidade de movimento dos nós [m/s]
RAM-AODV (2 Percursos) AODV
0
0,002
0,004
0,006
0,008
0,01
0,012
0,014
[1,4] [4,8] [12,16] [20,24]
Jitt
er
[s]
Variação da velocidade de movimento dos nós [m/s]
RAM-AODV (2 Percursos) AODV
64
Figura 4-11 com o gráfico do atraso da Figura 4-10, conclui-se que os resultados do jitter são
insignificantes em relação aos resultados do atraso. O valor mais alto do jitter do protocolo RAM-AODV (2
percursos) foi concebido para uma velocidade escolhida no intervalo [12,16] m/s e foi de 0.012s. Para esta
mesma velocidade o atraso foi de 0.9s [ver Figura 4-10]. Ao comparar os dois valores, pode constatar que
o jitter é desprezável perante o valor do atraso. Dado que os resultados do atraso do protocolo AODV são
praticamente iguais ao do protocolo RAM-AODV (2 percursos) e analisando o gráfico do jitter da Figura
4-11, conclui-se também de que o jitter do protocolo AODV é desprezável perante o atraso obtido. É de
mencionar que apesar de ambos os protocolos apresentarem valores baixos do jitter, o protocolo RAM-
AODV (2 percursos) para algumas velocidades apresentou menor jitter do que o protocolo AODV.
Figura 4-12: Valores de taxa média de pacotes recebidos em redes dinâmicas, com velocidade de
movimento dos nós variável.
O gráfico da Figura 4-12 mostra como a variação da velocidade de movimento dos nós influência a taxa
média de pacotes recebidos pelo nó de destino. Na medida que aumenta a velocidade de movimento dos
nós, há mais quebras de ligações e mais pacotes são descartados. Com o protocolo RAM-AODV (2
percursos), em virtude dos percursos alternativos, poucos pacotes são descartados com as frequentes
quebras de ligações. A possibilidade de utilizar percursos alternativos, contribuiu para que o protocolo
RAM-AODV (2 percursos) tenha sempre uma taxa média de pacotes recebidos superior à do protocolo
AODV, independentemente do valor da velocidade de movimento dos nós.
A fim de estudar o débito conseguido pelos dois protocolos em redes com suporte a mobilidade, foi
construído um gráfico que apresenta os valores médios do débito em função da velocidade de movimento
dos nós. O comportamento do gráfico do débito é idêntico ao gráfico da taxa média de pacotes recebidos,
dado que o débito vária de forma directamente proporcional ao número de pacotes recebidos, para
atrasos semelhantes.
0
10
20
30
40
50
60
70
[1,4] [4,8] [12,16] [20,24]
Ta
xa
me
dia
de
pa
cote
s re
ceb
ido
s[%
]
Variação da velocidade de movimento dos nós [m/s]
RAM-AODV (2 Percursos) AODV
65
Figura 4-13: Valores médios do débito em redes dinâmicas, com velocidade de movimento dos nós
variável.
O gráfico da Figura 4-13 permite-nos concluir também que o desempenho dos dois protocolos diminui
com o aumento da velocidade de movimento dos nós. O aumento da velocidade de movimento dos nós
contribui significativamente para o aumento da instabilidade da rede e a mudança da sua topologia.
Verifica-se um aumento das quebras de ligações, o que provoca uma degradação do desempenho em
ambos os protocolos. No entanto, devido ao facto do protocolo RAM-AODV poder recorrer a percursos
alternativos parcialmente disjuntos, conseguiu suportar melhor o aumento da instabilidade da rede.
Conclui-se então que o protocolo RAM-AODV é uma opção alternativa considerável para as redes móveis
em relação ao protocolo AODV. Independentemente do valor da velocidade, o protocolo RAM-AODV
apresentou melhores débitos.
0
10
20
30
40
50
60
70
[1,4] [4,8] [12,16] [20,24]
Dé
bit
o[K
bp
s]
Variação da velocidade de movimento dos nós [m/s]
RAM-AODV ( 2 Percursos ) AODV
66
5 Conclusão
O objectivo do presente trabalho foi desenvolver um protocolo de encaminhamento multi-percurso para
funcionar nas redes MANET. O protocolo tem como objectivo minimizar a sobrecarga da rede, tempo de
atraso na comunicação extremo-a-extremo e o número de pacotes perdidos na rede. O protocolo foi
implementado com sucesso no sistema operativo Linux de forma eficiente, tendo em vista que o protocolo
poderá vir a ser utilizado em uma grande diversidade de sistemas embutidos. A implementação do
protocolo foi baseada no protocolo AODV e confiou-se na totalidade das suas mensagens de sinalização e
não se faz uso de qualquer mensagem adicional para o cálculo dos vários percursos. As únicas mensagens
adicionais são as mensagens extras de RREP e RRER, para o cálculo e manutenção de vários percursos. A
tecnologia de transmissão escolhida foi o WIFI 802.11b, uma vez que oferece largura de banda e alcance
adequados aos requisitos do protocolo desenvolvido.
Actualmente vários protocolos de encaminhamento multi-percurso foram desenvolvidos para funcionar
nas redes MANET, no entanto, o protocolo desenvolvido proporciona algumas contribuições. Devido ao
facto do protocolo RAM-AODV conseguir determinar vários percursos alternativos, utilizando apenas as
mensagens de sinalização do protocolo AODV, pode proporcionar as seguintes contribuições para as redes
MANET:
Maximização da largura de banda, através da distribuição uniforme dos pacotes pelos vários
percursos.
Minimiza o atraso da comunicação extremo-a-extremo.
Diminuir a sobrecarga de rede, e como consequência a maximização do tempo de vida dos
dispositivos.
Uma outra contribuição importante que o protocolo irá proporcionar, é no âmbito do simulador NS-3. Até
a data não havia implementado nenhum protocolo de encaminhamento multi-percurso em NS-3. Espera-
se que este trabalho impulsione novos estudos deste protocolo e promova o desenvolvimento de novos
projectos e estudos sobre o mesmo.
Para poder avaliar o desempenho do protocolo, foram realizadas várias simulações em dois cenários
diferentes. Perante todos os testes que foram realizados, o protocolo RAM-AODV revelou-se eficiente e
com melhor desempenho que o protocolo AODV. Os vários resultados obtidos permitiram-nos tirar as
seguintes conclusões:
O protocolo RAM-AODV possui melhor desempenho que o protocolo AODV, quer seja em redes
estáticas ou redes móveis. Pode-se concluir também que o protocolo desenvolvido possui melhor
desempenho do que o protocolo AODV em redes densas.
67
O protocolo RAM-AODV consegue suportar ritmos de envios de pacotes superiores aos do
protocolo AODV. Segundo os resultados obtidos na secção 4.2.2, para o intervalo de envio igual a
0.0001s, o protocolo RAM-AODV teve um taxa média de pacotes recebidos aproximadamente
20%, enquanto que o protocolo AODV teve uma taxa média nula.
Conclui-se também que para redes muito densas, obtém-se melhores desempenho ao realizar o
encaminhamento multi-percurso com o menor número de percursos possíveis. Segundo os
resultados obtidos na 4.2.1, depara-se que a partir de 60 nós o RAM-AODV com 2 percursos
apresentou melhores desempenho do que RAM-AODV com mais de 2 percursos.
Por último conclui-se, que ao limitar o número máximo de percursos que pode ser determinado
entre o nó de origem e de destino é vantajoso. Segundo os resultados obtidos, consegue-se
diminuir a sobrecarga da rede e o número de pacotes descartados.
Todos os requisitos e os objectivos planeados na fase inicial foram alcançados com sucesso. Com o
protocolo RAM-AODV foi possível reduzir o atraso da comunicação e diminuir o número de pacotes
perdidos. O débito obtido pelo protocolo RAM-AODV foi superior aos débitos obtidos pelo protocolo AODV
em todos os cenários. Em todos os testes que foram realizados o jitter foi desprezável em relação ao
atraso.
Apesar de ter atingido os objectivos propostos e embora o protocolo seja eficiente, melhorias futuras
importantes poderão ser realizadas. O protocolo implementado é relativamente simples, podendo
futuramente ser enriquecido pela inclusão das seguintes funcionalidades:
Optimização do tempo de vida dos percursos: a gestão de tempo de vida dos percursos está a
ser realizada apenas a nível da entrada da tabela de encaminhamento, ou seja, todos os percursos
têm o mesmo tempo de vida. Sempre que é actualizado o tempo de vida de um percurso, quer seja
por ter sido descoberto um novo percurso ou por ter recebido uma mensagem de hello, esta
actualização abrange todos os percursos existentes na lista de próximos saltos. A melhoria que
poderá ser realizada, consistirá em gerir o tempo de vida por percurso, ou seja, cada percurso na
lista de próximos saltos tem o seu tempo de vida e deverá ser actualizada separadamente e
independente dos outros.
Gestão de números máximos de percursos: o parâmetro que indica o número máximo de
percursos que é permitido calcular por cada pedido de descoberta de percurso é definido
manualmente pelo administrador da rede. A melhoria que poderá ser realizada é defini-lo
dinamicamente e fazê-lo com base em alguns critérios apropriados.
Encaminhamento com percurso único: o protocolo desenvolvido, foi destinado exclusivamente
para realizar o encaminhamento multi-percurso. Eventualmente se for preciso realizar o
68
encaminhamento com percurso único, algumas melhorias terão que ser implementadas. Uma das
principais melhorias é de possibilitar aos nós intermédios poderem responder aos pacotes RREQ,
quando possuem percursos validos para o nó de destino. Por forma a obter bons resultados com
esta funcionalidade, o protocolo deve poder saber dinamicamente quando a rede entra em
congestionamento e desactivar esta funcionalidade nos nós intermédios. Assim como foi
concluído no capítulo 4, esta funcionalidade só e vantajosa para redes não muito densas.
69
70
6 Bibliografia
[1] Pascale Minet,Anis Laouiti,Laurent Viennot, Thomas Clausen and Cedric Adjih
Philippe Jacquet. (2002, April) IETF MANET Working Group. [Online].
http://tools.ietf.org/html/draft-jacquet-olsr-molsr-00
[2] Thomas Heide Clausen, "A MANET Architecture Model," INSTITUT NATIONAL DE
RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE, Unité de recherche INRIA
Futurs Parc Club Orsay Université, ZAC des Vignes,4, rue Jacques Monod, 91893
ORSAY Cedex (France), Rapport de recherche n 6145 ISSN 0249-6399, January
2007.
[3] HuiMin Chen, and Min Jia YuHua Yuan, "An Optimized Ad-hoc On-demand
Multipath Distance Vector(AOMDV) Routing Protocol," in Communications, 2005
Asia-Pacific Conference on, Western Australia, October 2005, pp. 569- 573.
[4] Perumal Sambasivam and Ashwin Murthy Elizabeth M. Belding-Royer,
"Dynamically Adaptive Multipath Routing Based on AODV," in Proc. Third Ann.
Mediterranean Ad Hoc Networking Workshop (MedHocNet '04), 2004.
[5] Mahesh K. Marina and Samir R. Das, "Ad hoc on-demand multipath distance vector
routing," WIRELESS COMMUNICATIONS AND MOBILE COMPUTING, vol. 6, pp. 969–
988, 2006, Published online in Wiley InterScience (www.interscience.wiley.com).
DOI: 10.1002/wcm.432.
[6] (2011, Dezembro) NS-3. [Online]. http://www.nsnam.org/
[7] R.P.Yadav Narendra Singh Yadav, "Performance Comparison and Analysis of
TableDriven and On-Demand Routing Protocols for Mobile Ad-hoc Networks," Int. J.
Inform. Technol, vol. 4, pp. 101-109, 2007.
[8] Perkins Belding-Royer. (2003, July) datatracker.ietf.org. [Online].
http://www.ietf.org/rfc/rfc3561.txt
[9] Network Working Group. (2007, February ) The Dynamic Source Routing Protocol
(DSR) for Mobile Ad Hoc Networks for IPv4. [Online].
http://www.ietf.org/rfc/rfc4728.txt
[10] T. Clausen and P. Jacque. (2003, October) Optimized Link State Routing Protocol
(OLSR. [Online]. http://www.ietf.org/rfc/rfc3626.txt
[11] Marc R. Pearlman and Zygmunt J. Haas Prince Samar, "Independent Zone Routing:
An Adaptive Hybrid Routing Framework for Ad Hoc Wireless Networks," IEEE/ACM
71
Transactions on Networking (TON), vol. 12, pp. 595-608, August 2004.
[12] Nicklas Beijar, Zone Routing Protocol (ZRP), April 2002,
http://www.netlab.hut.fi/opetus/s38030/k02/Papers/08-Nicklas.pdf.
[13] Rose P. Tsang, Dipak Ghosal Stephen Mueller, "Multipath Routing in Mobile Ad Hoc
Networks: Issues and Challenges," in In Performance Tools and Applications to
Networked Systems , Department of Computer Science, University of California,
Davis, CA 95616 and Sandia National Laboratories, Livermore, CA 94551, 2004, pp.
209-234.
[14] S. Mohammadi V. Zangeneh, "New Multipath Node-Disjoint Routing Based on AODV
Protocol," World Academy of Science, Engineering and Technology, pp. 76-116,
March 2011.
[15] Eddy Cizeron, Salima Hamma, Benoît Parrein and Pascal Lesage Jiazi Yi,
"Implementation of Multipath and Multiple Description Coding in OLSR," in 4th
OLSR Interop/Work Shop, Ottawa : Canada, vol. abs/0902.478, Ottawa: Canada, Feb
2008.
[16] Thomas Clausen Ulrich Herberg, "SECURITY ISSUES IN THE OPTIMIZED LINK
STATE ROUTING PROTOCOL VERSION 2 (OLSRV2)," International Journal of
Network Security & Its Applications (IJNSA), vol. abs/1005.4, pp. 162-181, April
2010.
[17] IETF MANET Working Group - Hakim BadisA. (2007, March) draft-badis-manet-
qolsr. [Online]. http://ietfreport.isoc.org/idref/draft-badis-manet-qolsr/
[18] Abderrahmen Mtibaa and Farouk Kamoun, "MMDV: Multipath and MPR based
AODV routing protocol," Kluwer Academic Publishers ("Med-Hoc-Net"), pp. 137-144,
May 2006.
[19] Jilei Liu, Edmond Poon,Ah-Lot Charles Chan and Baochun Li Roy Leung, "MP-DSR: A
QoS-Aware Multi-Path Dynamic Source Routing Protocol for Wireless Ad-Hoc
Networks," in 26th Annual IEEE International Conference on Local Computer
Networks (LCN'01), Tampa, Florida, 2001, pp. 132-141.
[20] A. Etorban and Peter J.B King Idris Skloul Ibrahim, "Multipath Distance Vector Zone
Routing Protocol for Asymmetric Mobile Ad-Hoc Networks (MDVZRPA)," in UK
Performance Engineering Workshop (UKPEW 2008), Imperial College London,
DTR08-9, 2008, pp. pp. 271–284.
[21] Rajendra Kumar Gupta, "Node Disjoint Minimum Interference Multipath (ND-MIM)
72
Routing Protocol for Mobile Ad hoc Networks," International Journal of Advanced
Research in Computer Science and Software Engineering, vol. Volume 2, pp. 128-131,
March 2012.
[22] David Harle Christos Tachtatzis, "Performance Evaluation of Multi-path and Single-
path Routing Protocols for Mobile Ad-Hoc Networks," in International Symposium
on Performance Evaluation of Computer and Telecommunication Systems, Edinburgh,
2008, pp. 173-180.
[23] The Network Simulator- ns-2. [Online]. http://isi.edu/nsnam/ns/
73
74
Apêndice A
Cenário 1: Redes estáticas
1) Teste do desempenho do protocolo em redes densas.
2) /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ 3) /*************************************************************************** 4) * * 5) * AMBIENTE DE REDE DISTRIBUIDO * 6) * Julho 2011 * 7) * * 8) * TITULO: Simulacao de protocolos em do Redes sem fios ad-hoc * 9) * AUTOR: Justimiano Alves * 10) * CENARIO 1 – Teste de variação da densidade da rede * 11) * O codigo a seguir foi baseado no exemplo open-source de Pavel Boyko * 12) * * 13) ****************************************************************************/ 14) 15) 16) #include "ns3/ram-aodv-module.h" 17) #include "ns3/core-module.h" 18) #include "ns3/common-module.h" 19) #include "ns3/node-module.h" 20) #include "ns3/helper-module.h" 21) #include "ns3/mobility-module.h" 22) #include "ns3/contrib-module.h" 23) #include "ns3/wifi-module.h" 24) #include "ns3/v4ping-helper.h" 25) #include "ns3/flow-monitor-module.h" 26) #include <iostream> 27) #include <cmath> 28) #include <fstream> 29) #include <stdio.h> 30) #include <stdlib.h> 31) #include <string> 32) #include <list> 33) 34) NS_LOG_COMPONENT_DEFINE ("RamAodv"); 35) 36) using namespace ns3; 37) using namespace std; 38) 39) class RamAodvExample 40) { 41) public: 42) RamAodvExample(); 43) /// configure script paramter , return true on successeful configuration. 44) bool Configure (int agrc , char **argv ,int seedSimulator); 45) /// Run simulation 46) bool Run ( int nodeNumber ,vector<double> & resultSimulation); 47) ///Report the result 48) bool Reportresult(vector<double> & resultSimulation); 49) /// total value of the delay 50) double CalculoMeanValue (list<double> listValue); 51) 52) double SumOfTheSquaredValue (list<double> listValue); 53) 54) double ComputerValueVariance (double valueMean ,list<double> listValue); 55) private: 56) ///\name parameters. 57) //\{ 58) /// time of the simulation. 59) uint32_t totalTime; 60) /// number of the nodes. 61) uint32_t size; 62) ///Distance betewenn of the nodes. 63) double distance;
75
64) //gridWidth of the matrix. 65) double gridWidth; 66) ///size of the packet. 67) uint32_t packetSize; 68) ///Number of the packet. 69) uint32_t numPackets; 70) /// Set of the Client Node. 71) int clientNode; 72) /// interval 73) double interval; 74) /// Set of the Server Node. 75) int ServerNode; 76) /// Set of the port socket. 77) int server_port; 78) /// Print routes if true 79) bool printRoutes; 80) /// Write per-device PCAP traces if true 81) bool pcap; 82) /// Number of simulation 83) int totalSimulation; 84) //\} 85) 86) ///\name network 87) //\{ 88) NodeContainer nodes; 89) NetDeviceContainer devices; 90) Ipv4InterfaceContainer interfaces; 91) FlowMonitorHelper flowmon; 92) Ptr<FlowMonitor> monitor; 93) //\} 94) 95) private: 96) void CreateNodes (int nodeNumber); 97) void CreateDevices (); 98) void InstallInternetStack (); 99) void InstallApplications (); 100) string i2string(int i); 101) void Reset(); 102) 103) }; 104) 105) //========================================== Method Construtor =========================== 106) RamAodvExample::RamAodvExample(): 107) totalTime(100),size(40),distance(20),gridWidth(10), 108) packetSize(256),numPackets(500),clientNode(0),interval(0.001), 109) ServerNode(size-1),server_port(4050),printRoutes(false),pcap(false), 110) totalSimulation(50) 111) { 112) } 113) void 114) RamAodvExample::Reset() 115) { 116) size = 0; 117) ServerNode = 0; 118) clientNode =0; 119) numPackets = 0; 120) 121) NodeContainer::Iterator it_node; 122) for (it_node = nodes.Begin() ; it_node != nodes.End() ; it_node++) 123) { 124) (*it_node) -> Dispose(); 125) } 126) 127) NetDeviceContainer::Iterator it_devices; 128) for (it_devices = devices.Begin(); it_devices != devices.End(); it_devices ++) 129) { 130) (*it_devices)->Dispose(); 131) } 132) monitor->Dispose(); 133) Names::Clear(); 134) } 135) //========================================== Method Main =================================
76
136) int main (int argc , char **argv) 137) { 138) RamAodvExample cenarioDensidade; 139) int delt = 10; 140) int numberTotalNode = 40; 141) int n_node = 0; 142) 143) list<double> listDelay; 144) list<double> listJitter; 145) list<double> listPacketLoss; 146) list<double> listPacketReceived; 147) list<double> listDebito; 148) 149) 150) fstream file_op1 ("MeanRAM_AODV.dat" ,ios::out); //ficheiros com os valores todos .. 151) fstream file_op2 ("S_RAM_AODV.dat" ,ios::out); 152) 153) //=========================Set header of file ========================================= 154) file_op1 <<"Node Delay[s] Jitter PLR[%] PR Debito[Mbps]"; 155) file_op1 << "\n"; 156) 157) file_op2 <<"Node Delay[s] Jitter PLR[%] PR Debito[Mbps]"; 158) file_op2 << "\n"; 159) 160) vector<double> resultSimulation; 161) for (n_node = 0 ; n_node <= numberTotalNode; n_node= n_node + delt ) 162) { 163) for (int numeroSimulacao = 1 ; numeroSimulacao <= 50 ;numeroSimulacao++) 164) { 165) 166) RamAodvExample cenario1; 167) 168) std::cout << "Starting simulation for : " << numeroSimulacao << " ...\n"; 169) if(!cenario1.Configure(argc, argv ,numeroSimulacao)) 170) NS_FATAL_ERROR ("Configuration failed. Aborted."); 171) 172) if(!cenario1.Run(n_node ,resultSimulation)) 173) { resultSimulation.clear(); 174) continue; 175) } 176) 177) listDelay.push_back(resultSimulation[0]); //Delay Value 178) listJitter.push_back(resultSimulation[1]); //Jitter Value 179) listPacketLoss.push_back(resultSimulation[2]); //Packet loss Value 180) listPacketReceived.push_back(resultSimulation[3]); //Packet received Value 181) listDebito.push_back(resultSimulation[4]); //Debito Value 182) 183) resultSimulation.clear();// inicializar o vectors. 184) } 185) //-------------------Mean and Variance values Delay --------------------------------
186) double delayMean = cenarioDensidade.CalculoMeanValue(listDelay); 187) double delayVariance = cenarioDensidade.ComputerValueVariance ( delayMean ,listDelay);
188) 189) //------------------ Mean and Variance values Jitter --------------------------------
- 190) double jitterMean = cenarioDensidade.CalculoMeanValue(listJitter); 191) double jitterVariance = cenarioDensidade.ComputerValueVariance(jitterMean,listJitter);
192) 193) //-------------------Mean value packet loss ------------------------------------------
-------------- 194) double packetLossMean = cenarioDensidade.CalculoMeanValue(listPacketLoss); 195) double packetLossVariance = cenarioDensidade.ComputerValueVariance(packetLossMean,list
PacketLoss); 196) 197) 198) //-------------------Mean value packet received------------------------------- -------
----------------------- 199) double packetReceivedMean = cenarioDensidade.CalculoMeanValue(listPacketReceived);
77
200) double packetReceivedVariance = cenarioDensidade.ComputerValueVariance(packetReceivedMean,listPacketReceived);
201) 202) //-------------------Mean value debito------------------------------------------------
------------------------ 203) double debitoMean = cenarioDensidade.CalculoMeanValue(listDebito); 204) double debitoVariance = cenarioDensidade.ComputerValueVariance(debitoMean,listDebito);
205) 206) //-------------------------------- write the informations to file --------------------
----------------- 207) file_op1<<40 + n_node <<" "<<delayMean<<" "<<jitterMean<<" "<<packetLossMean<<"
"<<packetReceivedMean<<" "<<debitoMean; 208) file_op1 << "\n"; 209) 210) file_op2<<40 + n_node <<" "<<delayVariance<<" "<<jitterVariance<<" "<<packetLossV
ariance<<" "<<packetReceivedVariance<<" "<<debitoVariance; 211) file_op2 << "\n"; 212) 213) //=============================== reinicializacao dos parametros =====================
============================================ 214) listDelay.clear(); 215) listJitter.clear(); 216) listPacketLoss.clear(); 217) listPacketReceived.clear(); 218) listDebito.clear(); 219) break; 220) } 221) file_op1.close(); 222) file_op2.close(); 223) return 0; 224) } 225) //========================================== Method Run ================================== 226) bool 227) RamAodvExample::Run ( int nodeNumber ,vector<double> & resultSimulation) 228) { 229) bool result; 230) Config::SetDefault ("ns3::WifiRemoteStationManager::RtsCtsThreshold", UintegerValue (1));
// enable rts cts all the time. 231) CreateNodes (nodeNumber); 232) CreateDevices (); 233) InstallInternetStack (); 234) InstallApplications (); 235) Simulator::Stop(Seconds(totalTime)); 236) monitor = flowmon.InstallAll(); 237) Simulator::Run (); 238) result = Reportresult(resultSimulation); 239) Simulator::Destroy (); 240) Reset(); 241) return result; 242) } 243) //========================================== Method Configure ============================ 244) bool 245) RamAodvExample::Configure(int argc , char**argv ,int seedSimulator) 246) { 247) SeedManager::SetSeed(seedSimulator); 248) CommandLine cmd; 249) cmd.AddValue("totalTime" ,"Tempo total de simulacao",totalTime); 250) cmd.AddValue("distance","Distancia entre os dispositivos",distance); 251) cmd.AddValue("packetSize","Tamanho em bytes dos pacotes UDP",packetSize); 252) cmd.AddValue("numPackets","Numero de pacotes enviados",numPackets); 253) cmd.AddValue("size","Numero dos dispotivos e tamanho da rede",size); 254) cmd.AddValue("server_port","Numero do porto do servidor UDP",server_port); 255) cmd.AddValue("interval","Intervalo de envio de cada pacotes", interval); 256) cmd.Parse(argc,argv); 257) return true; 258) } 259) 260) double 261) RamAodvExample::CalculoMeanValue(list<double> listValue) 262) { 263) double Meanvalue =0.0;
78
264) double totalValue =0.0; 265) 266) list<double>::iterator item; 267) for(item = listValue.begin() ; item != listValue.end() ; item++) 268) { 269) if( !isfinite(*item)) 270) continue; 271) 272) totalValue = totalValue + (*item); 273) } 274) 275) Meanvalue = totalValue / totalSimulation; 276) return Meanvalue; 277) } 278) 279) double 280) RamAodvExample::SumOfTheSquaredValue (list<double> listValue) 281) { 282) double result =0; 283) 284) list<double>::iterator item; 285) for(item = listValue.begin() ; item != listValue.end() ; item++) 286) { 287) if(!isfinite(*item)) 288) continue; 289) 290) result = result + ((*item)*(*item)); 291) } 292) return result; 293) } 294) 295) double 296) RamAodvExample::ComputerValueVariance( double valueMean ,list<double> listValue) 297) { 298) double valueVariance =0.0; 299) 300) /*----------------------------------------------------------- 301) * squaredValue = Sum(Xi^²); i varia de 1 ate totalSimulation; 302) * ---------------------------------------------------------*/ 303) 304) double squaredValue = SumOfTheSquaredValue (listValue); 305) /*----------------------------------------------------------------------------------------
- 306) * ---- --- 307) * 1 | | 308) * valueVariance^² = ----------------- |squaredValue - totalSimulation*(ValueMean^²) | 309) * totalSimulation-1 | | 310) * ---- --- 311) * ---------------------------------------------------------------------------------------
--*/ 312) 313) double squaredMean = valueMean * valueMean; 314) squaredMean = totalSimulation*squaredMean; 315) valueVariance = squaredValue - squaredMean; 316) valueVariance = valueVariance / (totalSimulation-1); 317) 318) return valueVariance; 319) 320) } 321) 322) void 323) RamAodvExample::CreateNodes(int nodeNumber ) 324) { 325) size = size + nodeNumber; 326) cout << "Creating " << (unsigned)size << " nodes " << distance << "m apart.\n"; 327) nodes.Create(size); 328) 329) // Name nodes 330) for (uint32_t i = 0; i < size; ++i) 331) { 332) std::ostringstream os; 333) os << "node-" << i;
79
334) Names::Add (os.str (), nodes.Get (i)); 335) } 336) 337) MobilityHelper mobility; 338) mobility.SetPositionAllocator("ns3::GridPositionAllocator", 339) "MinX", DoubleValue(0.0), 340) "MinY", DoubleValue(0.0), 341) "DeltaX", DoubleValue(distance), 342) "DeltaY", DoubleValue(distance), 343) "GridWidth", UintegerValue(gridWidth), 344) "LayoutType", StringValue("RowFirst")); 345) mobility.SetMobilityModel("ns3::ConstantPositionMobilityModel"); 346) mobility.Install(nodes); 347) } 348) //============================== Method CreateDevices ===================================== 349) void 350) RamAodvExample::CreateDevices() 351) { 352) NqosWifiMacHelper wifiMac = NqosWifiMacHelper::Default (); 353) wifiMac.SetType ("ns3::AdhocWifiMac"); 354) YansWifiPhyHelper wifiPhy = YansWifiPhyHelper::Default (); 355) YansWifiChannelHelper wifiChannel = YansWifiChannelHelper::Default (); 356) wifiPhy.SetChannel (wifiChannel.Create ()); 357) 358) WifiHelper wifi = WifiHelper::Default (); 359) wifi.SetRemoteStationManager ("ns3::IdealWifiManager"); 360) wifi.SetStandard(WIFI_PHY_STANDARD_80211b); 361) devices = wifi.Install (wifiPhy, wifiMac, nodes); 362) 363) if (pcap) 364) { 365) wifiPhy.EnablePcapAll (std::string ("aodv")); 366) } 367) } 368) //============================== Method InstallInternetStack ============================== 369) void 370) RamAodvExample::InstallInternetStack() 371) { 372) 373) RamAodvHelper ramaodv; 374) InternetStackHelper internet; 375) internet.SetRoutingHelper (ramaodv); 376) internet.Install (nodes); 377) 378) Ipv4AddressHelper ipv4; 379) ipv4.SetBase("10.1.1.0", "255.255.255.0"); 380) interfaces = ipv4.Assign(devices); 381) 382) if (printRoutes) 383) { 384) Ptr<OutputStreamWrapper> 385) routingStream = Create<OutputStreamWrapper> ("ramaodv.routes", std::ios::out); 386) ramaodv.PrintRoutingTableAllAt (Seconds (8), routingStream); 387) } 388) } 389) //============================== Method InstallApplications =============================== 390) void 391) RamAodvExample::InstallApplications() 392) { 393) ApplicationContainer apps; 394) uint32_t timeStartUdpCliente = totalTime/5; 395) ServerNode = size -1; 396) /*clientNode = rand() % size;*/ 397) Time interPacketInterval = Seconds(interval); 398) //Create one udpServer applications on node one. 399) 400) UdpServerHelper server(server_port); 401) apps = server.Install(nodes.Get(ServerNode)); 402) apps.Start(Seconds(2)); 403) apps.Stop(Seconds(totalTime)- Seconds(0.005)); 404) 405) // Create one UdpClient application to send UDP datagrams from node to node.
80
406) 407) UdpClientHelper client(interfaces.GetAddress(ServerNode), server_port); 408) client.SetAttribute("MaxPackets", UintegerValue(numPackets)); 409) client.SetAttribute("Interval", TimeValue(interPacketInterval)); 410) client.SetAttribute("PacketSize", UintegerValue(packetSize)); 411) apps = client.Install(nodes.Get(clientNode)); 412) 413) apps.Start(Seconds(timeStartUdpCliente)); 414) apps.Stop(Seconds(totalTime)- Seconds(0.01)); 415) } 416) 417) string 418) RamAodvExample::i2string(int i) 419) { 420) std::ostringstream buffer; 421) buffer << i; 422) return buffer.str(); 423) } 424) 425) //============================== Method Showresult ======================================== 426) bool 427) RamAodvExample::Reportresult(vector<double> & resultSimulation) 428) { 429) 430) bool StatusReturn; 431) monitor->CheckForLostPackets(); 432) Ptr<Ipv4FlowClassifier> classifier = DynamicCast<Ipv4FlowClassifier > (flowmon.GetClassifi
er()); 433) std::map<FlowId, FlowMonitor::FlowStats> stats = monitor->GetFlowStats(); 434) 435) for (std::map<FlowId, FlowMonitor::FlowStats>::const_iterator i = stats.begin(); i != stat
s.end(); ++i) 436) { 437) Ipv4FlowClassifier::FiveTuple t = classifier->FindFlow(i->first); 438) 439) std::string client_address = "10.1.1."; 440) std::string server_address = "10.1.1."; 441) 442) std::string id_client = i2string(1); 443) std::string id_server = i2string(ServerNode+1); 444) 445) client_address = client_address + id_client; 446) server_address = server_address + id_server; 447) 448) if (t.sourceAddress == client_address.c_str() && 449) t.destinationAddress == server_address.c_str() && 450) t.destinationPort == server_port) 451) { 452) 453) resultSimulation.push_back(i->second.delaySum.GetSeconds() / i-
>second.rxPackets); //Delay 454) resultSimulation.push_back(i->second.jitterSum.GetSeconds()/(i->second.rxPackets -
1)); //Jitter 455) resultSimulation.push_back((i->second.txPackets - i-
>second.rxPackets) / (double) i->second.txPackets); // PRL 456) resultSimulation.push_back(i-> second.rxPackets); //packet receveid 457) resultSimulation.push_back(i->second.rxBytes * 8.0 / totalTime
/ 1024 / 1024); //debito 458) 459) //========================== imprimir ============================================
=================== 460) cout << "Flow " << i->first << " (" << t.sourceAddress << " -
> " << t.destinationAddress << ")"<< "\n" 461) << " Tx[B]: " << i->second.txBytes << "\n" 462) << " Pacotes Transmitidos: " << i->second.txPackets << "\n" 463) << " Rx[B]: " << i->second.rxBytes << "\n" 464) << " Pacotes Recebidos: " << i->second.rxPackets << "\n" 465) << " Tput[Mbps]: " << i->second.rxBytes * 8.0 / 10.0 / 1024 / 1024 << "\n" 466) << " PLR[%]: " << (i->second.txPackets - i->second.rxPackets) / (double) i-
>second.txPackets<< "\n" 467) << " D[s]: " << i->second.delaySum.GetSeconds() / i->second.rxPackets << endl; 468)
81
469) if(i->second.rxPackets == 0) 470) StatusReturn = false; 471) else 472) StatusReturn = true; 473) 474) } 475) } 476) std::cout << "END \n\n\n" << std::endl; 477) return StatusReturn; 478)
479) }
2) Teste do desempenho do protocolo com diferentes intervalos de envios de pacotes.
1. /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2. /***************************************************************************
3. * *
4. * AMBIENTE DE REDE DISTRIBUIDO *
5. * Julho 2011 *
6. * *
7. * TITULO: Simulacao de protocolos em do Redes sem fios ad-hoc *
8. * AUTOR: Justimiano Alves *
9. * CENARIO 1 –Teste de Variação do intervalo de envio *
10. De pacotes *
11. * O codigo a seguir foi baseado no exemplo open-source de Pavel Boyko *
12. * *
13. ****************************************************************************/
14.
15.
16. #include "ns3/ram-aodv-module.h"
17. #include "ns3/core-module.h"
18. #include "ns3/common-module.h"
19. #include "ns3/node-module.h"
20. #include "ns3/helper-module.h"
21. #include "ns3/mobility-module.h"
22. #include "ns3/contrib-module.h"
23. #include "ns3/wifi-module.h"
24. #include "ns3/v4ping-helper.h"
25. #include "ns3/flow-monitor-module.h"
26. #include <iostream>
27. #include <cmath>
28. #include <fstream>
29. #include <stdio.h>
30. #include <string>
31. #include <list>
32.
33. NS_LOG_COMPONENT_DEFINE ("RamAodv");
34.
35. using namespace ns3;
36. using namespace std;
37.
38. class RomAodvExample
39. {
40. public:
41. RomAodvExample();
42. /// configure script paramter , return true on successeful configuration.
43. bool Configure (int agrc , char **argv ,int newseed);
44. /// Run simulation
45. bool Run ( double deltPeriodo ,vector<double> & resultSimulation);
46. ///Report the result
47. bool Reportresult(vector<double> & resultSimulation);
82
48. /// total value of the delay
49. double CalculoMeanValue (list<double> listValue);
50.
51. double SumOfTheSquaredValue (list<double> listValue);
52.
53. double ComputerValueVariance (double valueMean ,list<double> listValue);
54.
55. private:
56. ///\name parameters.
57. //\{
58. /// time of the simulation.
59. uint32_t totalTime;
60. /// number of the nodes.
61. uint32_t size;
62. ///Distance betewenn of the nodes.
63. double distance;
64. //gridWidth of the matrix.
65. double gridWidth;
66. ///size of the packet.
67. uint32_t packetSize;
68. ///Number of the packet.
69. uint32_t numPackets;
70. /// Set of the Client Node.
71. int clientNode;
72. /// Set of the Server Node.
73. int ServerNode;
74. /// Set of the port socket.
75. int server_port;
76. ///ritimo de send packte UDP
77. uint64_t DataRate2;
78. /// Print routes if true
79. bool printRoutes;
80. /// Write per-device PCAP traces if true
81. bool pcap;
82. /// Number of simulation
83. int totalSimulation;
84. //\}
85.
86. ///\name network
87. //\{
88. NodeContainer nodes;
89. NetDeviceContainer devices;
90. Ipv4InterfaceContainer interfaces;
91. FlowMonitorHelper flowmon;
92. Ptr<FlowMonitor> monitor;
93. //\}
94.
95. private:
96. void CreateNodes ();
97. void CreateDevices ();
98. void InstallInternetStack ();
99. void InstallApplications (double packetSize);
100. string i2string(int i);
101. void Reset();
102. };
103.
104.
105. //============================== Method Construtor ==============================
106. RomAodvExample::RomAodvExample():
107. totalTime(100),size(80),distance(20),gridWidth(10),
108. packetSize(256),numPackets(500),clientNode(0),
109. ServerNode(size-1),server_port(4050),DataRate2(64000),
110. printRoutes(false),pcap(false),
111. totalSimulation(50)
83
112. {
113. }
114.
115. void
116. RomAodvExample::Reset()
117. {
118. size = 0;
119. ServerNode = 0;
120. clientNode =0;
121. numPackets = 0;
122.
123. NodeContainer::Iterator it_node;
124. for (it_node = nodes.Begin() ; it_node != nodes.End() ; it_node++)
125. {
126. (*it_node) -> Dispose();
127. }
128.
129. NetDeviceContainer::Iterator it_devices;
130. for (it_devices = devices.Begin(); it_devices != devices.End(); it_devices ++)
131. {
132. (*it_devices)->Dispose();
133. }
134. monitor->Dispose();
135. Names::Clear();
136. }
137. //============================== Method Main ====================================
138. int main (int argc , char **argv)
139. {
140. RomAodvExample cenarioDensidade;
141.
142. list<double>::iterator item;
143. list<double> listPeriodo ;
144.
145.
146. /*listPeriodo.push_back(0.001);*/
147. listPeriodo.push_back(0.0001);
148. /*listPeriodo.push_back(0.00001);
149. listPeriodo.push_back(0.000001);
150. listPeriodo.push_back(0.0000001);
151. listPeriodo.push_back(0.00000001);
152. listPeriodo.push_back(0.000000001);*/
153.
154. list<double> listDelay;
155. list<double> listJitter;
156. list<double> listPacketLoss;
157. list<double> listPacketReceived;
158. list<double> listDebito;
159.
160.
161. fstream file_op1 ("MeanRAM_AODV.dat" ,ios::out); //ficheiros com os valores todos ..
162. fstream file_op2 ("S_RAM_AODV.dat" ,ios::out);
163. //=========================Set header of file ============================================
======
164. file_op1 <<"Node Delay[s] Jitter PLR[%] PR Debito[Mbps]";
165. file_op1 << "\n";
166.
167. file_op2 <<"Node Delay[s] Jitter PLR[%] PR Debito[Mbps]";
168. file_op2 << "\n";
169.
170. vector<double> resultSimulation;
171. for (item = listPeriodo.begin() ;item != listPeriodo.end(); item++)
172. {
173. for (int numeroSimulacao = 1 ; numeroSimulacao <= 50 ;numeroSimulacao++)
174. {
84
175. RomAodvExample cenario1;
176. std::cout << "Starting simulation for " << numeroSimulacao << " s ...\n";
177. if(!cenario1.Configure(argc, argv ,numeroSimulacao))
178. NS_FATAL_ERROR ("Configuration failed. Aborted.");
179.
180. if(!cenario1.Run(*item ,resultSimulation))
181. { resultSimulation.clear();
182. continue;
183. }
184.
185. listDelay.push_back(resultSimulation[0]); //Delay Value
186. listJitter.push_back(resultSimulation[1]); //Jitter Value
187. listPacketLoss.push_back(resultSimulation[2]); //Packet loss Value
188. listPacketReceived.push_back(resultSimulation[3]); //Packet received Value
189. listDebito.push_back(resultSimulation[4]); //Debito Value
190.
191. resultSimulation.clear();// inicializar o vectors.
192. }
193. //-------------------Mean and Variance values Delay --------------------------------
194. double delayMean = cenarioDensidade.CalculoMeanValue(listDelay);
195. double delayVariance = cenarioDensidade.ComputerValueVariance ( delayMean ,listDelay);
196.
197. //------------------ Mean and Variance values Jitter --------------------------------
-
198. double jitterMean = cenarioDensidade.CalculoMeanValue(listJitter);
199. double jitterVariance = cenarioDensidade.ComputerValueVariance(jitterMean,listJitter);
200.
201. //-------------------Mean value packet loss ------------------------------------------
--------------
202. double packetLossMean = cenarioDensidade.CalculoMeanValue(listPacketLoss);
203. double packetLossVariance = cenarioDensidade.ComputerValueVariance(packetLossMean,list
PacketLoss);
204.
205.
206. //-------------------Mean value packet received------------------------------- -------
-----------------------
207. double packetReceivedMean = cenarioDensidade.CalculoMeanValue(listPacketReceived);
208. double packetReceivedVariance = cenarioDensidade.ComputerValueVariance(packetReceivedM
ean,listPacketReceived);
209.
210. //-------------------Mean value debito------------------------------------------------
------------------------
211. double debitoMean = cenarioDensidade.CalculoMeanValue(listDebito);
212. double debitoVariance = cenarioDensidade.ComputerValueVariance(debitoMean,listDebito);
213.
214. //-------------------------------- write the informations to file --------------------
-----------------
215. file_op1<<*item <<" "<<delayMean<<" "<<jitterMean<<" "<<packetLossMean<<" "<<pac
ketReceivedMean<<" "<<debitoMean;
216. file_op1 << "\n";
217.
218. file_op2<<*item <<" "<<delayVariance<<" "<<jitterVariance<<" "<<packetLossVariance<
<" "<<packetReceivedVariance<<" "<<debitoVariance;
219. file_op2 << "\n";
220.
221.
222. //=============================== reinicializacao dos parametros =====================
============================================
223. listDelay.clear();
224. listJitter.clear();
85
225. listPacketLoss.clear();
226. listPacketReceived.clear();
227. listDebito.clear();
228. break;
229. }
230. file_op1.close();
231. file_op2.close();
232. return 0;
233. }
234. //============================== Method Run ======================================
235. bool
236. RomAodvExample::Run ( double DeltPeriodo,vector<double> & resultSimulation)
237. {
238. bool result;
239. Config::SetDefault ("ns3::WifiRemoteStationManager::RtsCtsThreshold", UintegerValue (1));
// enable rts cts all the time.
240. CreateNodes ();
241. CreateDevices ();
242. InstallInternetStack ();
243. InstallApplications (DeltPeriodo);
244.
245. std::cout << "Starting simulation for " << totalTime << " and " << DeltPeriodo << " s ...\
n";
246.
247. Simulator::Stop(Seconds(totalTime));
248. monitor = flowmon.InstallAll();
249. Simulator::Run ();
250. result = Reportresult(resultSimulation);
251. Simulator::Destroy ();
252. Reset();
253. return result;
254. }
255. //============================== Method Configure ================================
256. bool
257. RomAodvExample::Configure(int argc , char**argv , int newseed)
258. {
259. SeedManager::SetSeed(newseed);
260. CommandLine cmd;
261. cmd.AddValue("totalTime" ,"Tempo total de simulacao",totalTime);
262. cmd.AddValue("distance","Distancia entre os dispositivos",distance);
263. cmd.AddValue("packetSize","Tamanho em bytes dos pacotes UDP",packetSize);
264. cmd.AddValue("numPackets","Numero de pacotes enviados",numPackets);
265. cmd.AddValue("size","Numero dos dispotivos e tamanho da rede",size);
266. cmd.AddValue("server_port","Numero do porto do servidor UDP",server_port);
267. cmd.Parse(argc,argv);
268. return true;
269. }
270.
271. double
272. RomAodvExample::CalculoMeanValue(list<double> listValue)
273. {
274. double Meanvalue =0.0;
275. double totalValue =0.0;
276.
277. list<double>::iterator item;
278. for(item = listValue.begin() ; item != listValue.end() ; item++)
279. {
280. if( !isfinite(*item))
281. continue;
282.
283. totalValue = totalValue + (*item);
284. }
285.
286. Meanvalue = totalValue / totalSimulation;
86
287. return Meanvalue;
288. }
289.
290. double
291. RomAodvExample::SumOfTheSquaredValue (list<double> listValue)
292. {
293. double result =0;
294.
295. list<double>::iterator item;
296. for(item = listValue.begin() ; item != listValue.end() ; item++)
297. {
298. if(!isfinite(*item))
299. continue;
300.
301. result = result + ((*item)*(*item));
302. }
303. return result;
304. }
305.
306. double
307. RomAodvExample::ComputerValueVariance( double valueMean ,list<double> listValue)
308. {
309. double valueVariance =0.0;
310.
311. /*-----------------------------------------------------------
312. * squaredValue = Sum(Xi^²); i varia de 1 ate totalSimulation;
313. * ---------------------------------------------------------*/
314.
315. double squaredValue = SumOfTheSquaredValue (listValue);
316. /*----------------------------------------------------------------------------------------
-
317. * ---- ---
318. * 1 | |
319. * valueVariance^² = ----------------- |squaredValue - totalSimulation*(ValueMean^²) |
320. * totalSimulation-1 | |
321. * ---- ---
322. * ---------------------------------------------------------------------------------------
--*/
323.
324. double squaredMean = valueMean * valueMean;
325.
326. squaredMean = totalSimulation*squaredMean;
327.
328. valueVariance = squaredValue - squaredMean;
329.
330. valueVariance = valueVariance / (totalSimulation-1);
331.
332. return valueVariance;
333.
334. }
335.
336. void
337. RomAodvExample::CreateNodes( )
338. {
339. cout << "Creating " << (unsigned)size << " nodes " << distance << "m apart.\n";
340. nodes.Create(size);
341.
342. // Name nodes
343. for (uint32_t i = 0; i < size; ++i)
344. {
345. std::ostringstream os;
346. os << "node-" << i;
347. Names::Add (os.str (), nodes.Get (i));
348. }
87
349.
350. MobilityHelper mobility;
351. mobility.SetPositionAllocator("ns3::GridPositionAllocator",
352. "MinX", DoubleValue(0.0),
353. "MinY", DoubleValue(0.0),
354. "DeltaX", DoubleValue(distance),
355. "DeltaY", DoubleValue(distance),
356. "GridWidth", UintegerValue(gridWidth),
357. "LayoutType", StringValue("RowFirst"));
358. mobility.SetMobilityModel("ns3::ConstantPositionMobilityModel");
359. mobility.Install(nodes);
360. }
361. //============================== Method CreateDevices =====================================
362. void
363. RomAodvExample::CreateDevices()
364. {
365. NqosWifiMacHelper wifiMac = NqosWifiMacHelper::Default ();
366. wifiMac.SetType ("ns3::AdhocWifiMac");
367. YansWifiPhyHelper wifiPhy = YansWifiPhyHelper::Default ();
368. YansWifiChannelHelper wifiChannel = YansWifiChannelHelper::Default ();
369. wifiPhy.SetChannel (wifiChannel.Create ());
370. WifiHelper wifi = WifiHelper::Default ();
371. wifi.SetRemoteStationManager ("ns3::IdealWifiManager");
372. wifi.SetStandard(WIFI_PHY_STANDARD_80211b);
373. devices = wifi.Install (wifiPhy, wifiMac, nodes);
374.
375. if (pcap)
376. {
377. wifiPhy.EnablePcapAll (std::string ("aodv"));
378. }
379. }
380. //============================== Method InstallInternetStack ==============================
381. void
382. RomAodvExample::InstallInternetStack()
383. {
384.
385. RamAodvHelper ramaodv;
386. InternetStackHelper internet;
387. internet.SetRoutingHelper (ramaodv);
388. internet.Install (nodes);
389.
390. Ipv4AddressHelper ipv4;
391. ipv4.SetBase("10.1.1.0", "255.255.255.0");
392. interfaces = ipv4.Assign(devices);
393.
394. if (printRoutes)
395. {
396. Ptr<OutputStreamWrapper>
397. routingStream = Create<OutputStreamWrapper> ("ramaodv.routes", std::ios::out);
398. ramaodv.PrintRoutingTableAllAt (Seconds (8), routingStream);
399. }
400. }
401. //============================== Method InstallApplications ===============================
402. void
403. RomAodvExample::InstallApplications(double DeltPeriodo)
404. {
405. ApplicationContainer apps;
406. uint32_t timeStartUdpCliente = totalTime/5;
407. ServerNode = size -1;
408. Time interPacketInterval = Seconds(DeltPeriodo);
409.
410. //Create one udpServer applications on node one.
411.
412. UdpServerHelper server(server_port);
88
413. apps = server.Install(nodes.Get(ServerNode));
414. apps.Start(Seconds(2));
415. apps.Stop(Seconds(totalTime)- Seconds(0.005));
416.
417. // Create one UdpClient application to send UDP datagrams from node to node.
418.
419. UdpClientHelper client(interfaces.GetAddress(ServerNode), server_port);
420. client.SetAttribute("MaxPackets", UintegerValue(numPackets));
421. client.SetAttribute("Interval", TimeValue(interPacketInterval));
422. client.SetAttribute("PacketSize", UintegerValue(packetSize));
423. apps = client.Install(nodes.Get(clientNode));
424.
425. apps.Start(Seconds(timeStartUdpCliente));
426. apps.Stop(Seconds(totalTime)- Seconds(0.01));
427. }
428.
429. string
430. RomAodvExample::i2string(int i)
431. {
432. std::ostringstream buffer;
433. buffer << i;
434. return buffer.str();
435. }
436. //============================== Method Showresult ==========================================
437. bool
438. RomAodvExample::Reportresult(vector<double> & resultSimulation)
439. {
440.
441. bool StatusReturn;
442. monitor->CheckForLostPackets();
443. Ptr<Ipv4FlowClassifier> classifier = DynamicCast<Ipv4FlowClassifier > (flowmon.GetClassifi
er());
444. std::map<FlowId, FlowMonitor::FlowStats> stats = monitor->GetFlowStats();
445.
446. for (std::map<FlowId, FlowMonitor::FlowStats>::const_iterator i = stats.begin(); i != stat
s.end(); ++i)
447. {
448. Ipv4FlowClassifier::FiveTuple t = classifier->FindFlow(i->first);
449.
450. std::string client_address = "10.1.1.";
451. std::string server_address = "10.1.1.";
452.
453. std::string id_client = i2string(1);
454. std::string id_server = i2string(ServerNode+1);
455.
456. client_address = client_address + id_client;
457. server_address = server_address + id_server;
458.
459. if (t.sourceAddress == client_address.c_str() &&
460. t.destinationAddress == server_address.c_str() &&
461. t.destinationPort == server_port)
462. {
463.
464. NS_LOG_INFO("Delay[s]:" << i->second.delaySum.GetSeconds() / i-
>second.rxPackets);
465. NS_LOG_INFO("Variacao atraso:" << i->second.jitterSum.GetSeconds()/(i-
>second.rxPackets -1));
466. NS_LOG_INFO("Packet Perdidos:" << (i->second.txPackets - i-
>second.rxPackets) / (double) i->second.txPackets);
467. NS_LOG_INFO("Packet Recebidos:" << i-> second.rxPackets);
468. NS_LOG_INFO("Debito [Mbit/s]:" << i->second.rxBytes * 8.0 / totalTime
/ 1024 / 1024);
469.
89
470.
471. resultSimulation.push_back(i->second.delaySum.GetSeconds() / i-
>second.rxPackets); //Delay
472. resultSimulation.push_back(i->second.jitterSum.GetSeconds()/(i->second.rxPackets -
1)); //Jitter
473. resultSimulation.push_back((i->second.txPackets - i-
>second.rxPackets) / (double) i->second.txPackets); // PRL
474. resultSimulation.push_back(i-> second.rxPackets); //packet receveid
475. resultSimulation.push_back(i-
>second.rxBytes * 8.0 / 10.0 / 1024 / 1024); //debito
476.
477. //========================== imprimir ============================================
===================
478. cout << "Flow " << i->first << " (" << t.sourceAddress << " -
> " << t.destinationAddress << ")"<< "\n"
479. << " Tx[B]: " << i->second.txBytes << "\n"
480. << " Pacotes Transmitidos: " << i->second.txPackets << "\n"
481. << " Rx[B]: " << i->second.rxBytes << "\n"
482. << " Pacotes Recebidos: " << i->second.rxPackets << "\n"
483. << " Tput[Mbps]: " << i-
>second.rxBytes * 8.0 / timeSimulation / 1024 / 1024 << "\n"
484. << " PLR[%]: " << (i->second.txPackets - i->second.rxPackets) / (double) i-
>second.txPackets<< "\n"
485. << " D[s]: " << i->second.delaySum.GetSeconds() / i->second.rxPackets << endl;
486.
487. if(i->second.rxPackets == 0)
488. StatusReturn = false;
489. else
490. StatusReturn = true;
491.
492. }
493. }
494. std::cout << "END \n\n\n" << std::endl;
495. return StatusReturn;
496.
497. }
Cenário 2: Redes dinâmicas.
3) Teste do desempenho do protocolo em redes móveis.
1. /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2. /***************************************************************************
3. * *
4. * AMBIENTE DE REDE DISTRIBUIDO *
5. * Julho 2011 *
6. * *
7. * TITULO: Simulacao de protocolo em ad-hoc *
8. * AUTOR: Justimiano Alves *
9. * CENARIO 2 - Teste da Mobilidade dos dispositivos *
10. * O codigo a seguir foi baseado no exemplo open-source de Pavel Boyko *
11. * *
12. ****************************************************************************/
13.
14.
15. #include "ns3/ram-aodv-module.h"
16. #include "ns3/core-module.h"
17. #include "ns3/common-module.h"
18. #include "ns3/node-module.h"
19. #include "ns3/helper-module.h"
20. #include "ns3/mobility-module.h"
21. #include "ns3/contrib-module.h"
90
22. #include "ns3/wifi-module.h"
23. #include "ns3/v4ping-helper.h"
24. #include "ns3/flow-monitor-module.h"
25. #include <iostream>
26. #include <cmath>
27. #include <fstream>
28. #include <stdio.h>
29. #include <string>
30. #include <list>
31.
32. #include "ns3/simulator-module.h"
33.
34. NS_LOG_COMPONENT_DEFINE ("RamAodv");
35.
36. using namespace ns3;
37. using namespace std;
38.
39. class RamAodvExample
40. {
41. public:
42. RamAodvExample();
43. /// configure script paramter , return true on successeful configuration.
44. bool Configure (int agrc , char **argv ,int newseed);
45. /// Run simulation
46. bool Run ( int speedDeltMin, int speedDeltMax ,vector<double> & resultSimulation);
47. ///Report the result
48. bool Reportresult(vector<double> & resultSimulation);
49. /// total value of the delay
50. double CalculoMeanValue (list<double> listValue);
51.
52. double SumOfTheSquaredValue (list<double> listValue);
53.
54. double ComputerValueVariance (double valueMean ,list<double> listValue);
55.
56. private:
57. ///\name parameters.
58. //\{
59. /// time of the simulation.
60. uint32_t totalTime;
61. /// number of the nodes.
62. uint32_t size;
63. ///size of the packet.
64. uint32_t packetSize;
65. ///Number of the packet.
66. uint32_t numPackets;
67. /// Set of the Client Node.
68. int clientNode ;
69. /// Set of the Server Node.
70. int ServerNode;
71. /// Set of the port socket.
72. int server_port;
73. /// Write per-device PCAP traces if true
74. bool pcap;
75. /// Print routes if true
76. bool printRoutes;
77. /// interval
78. double interval;
79. ///ritimo de send packte UDP
80. uint64_t DataRate2;
81. /*----------------------------------------------------
82. * Definicao da area da mobilidade dos dispositivos
83. * ---------------------------------------------------*/
84. ///size X
85. double max_XX;
91
86. double min_XX;
87. ///size y
88. double max_YY;
89. double min_YY;
90. /*------------------------------------------------------
91. * Definicao dos parametros da area da topologia da rede
92. * -----------------------------------------------------*/
93. /// tipos de mobilidade
94. bool RWalk2M ; ///RandomWalk2dMobilityModel
95. bool RWayM ;///RandomWaypointMobilityModel
96.
97. ///Parametros da mobilidade.
98. int speedNodeMax;
99. int speedNodeMin;
100. int pauseNode;
101.
102. /// Number of simulation
103. int totalSimulation;
104. //\}
105.
106. ///\name network
107. //\{
108. NodeContainer nodes;
109. NetDeviceContainer devices;
110. Ipv4InterfaceContainer interfaces;
111. FlowMonitorHelper flowmon;
112. Ptr<FlowMonitor> monitor;
113. //\}
114.
115. private:
116. void CreateNodes (int speedDeltMin,int speedDeltMax);
117. void CreateDevices ();
118. void InstallInternetStack ();
119. void InstallApplications ();
120. string i2string(int i);
121. void Reset();
122. };
123.
124. RamAodvExample::RamAodvExample():
125. totalTime(100),
126. size(80),
127. packetSize(256),
128. numPackets(500),
129. clientNode(0),
130. ServerNode(size -1),
131. server_port(4050),
132. pcap(false),
133. printRoutes(false),
134. interval(0.001),
135. max_XX(1000),
136. min_XX(0.0),
137. max_YY(1000),
138. min_YY(0.0),
139. RWalk2M(false),
140. RWayM(true),
141. speedNodeMax(24.0),
142. speedNodeMin(20.0),
143. pauseNode(10),
144. totalSimulation(50)
145. {
146. }
147.
148. void
149. RamAodvExample::Reset()
92
150. {
151. size = 0;
152. ServerNode = 0;
153. clientNode =0;
154. numPackets = 0;
155.
156. NodeContainer::Iterator it_node;
157. for (it_node = nodes.Begin() ; it_node != nodes.End() ; it_node++)
158. {
159. (*it_node) -> Dispose();
160. }
161.
162. NetDeviceContainer::Iterator it_devices;
163. for (it_devices = devices.Begin(); it_devices != devices.End(); it_devices ++)
164. {
165. (*it_devices)->Dispose();
166. }
167. monitor->Dispose();
168. Names::Clear();
169. }
170. //========================================== Method Main =====================================
171. int main (int argc , char **argv)
172. {
173. RamAodvExample CenarioMobilidade;
174. int delt = 6;
175. int valueTotal = 30;
176. int speedDeltMax =0;
177. int speedDeltMin = 0;
178.
179. list<double> listDelay;
180. list<double> listJitter;
181. list<double> listPacketLoss;
182. list<double> listPacketReceived;
183. list<double> listDebito;
184.
185. fstream file_op1 ("MeanAODV.dat" ,ios::out); //ficheiros com os valores todos ..
186. fstream file_op2 ("S_AODV.dat" ,ios::out);
187.
188. //=========================Set header of file =========================================
189. file_op1 <<"Node Delay[s] Jitter PLR[%] PR Debito[Mbps]";
190. file_op1 << "\n";
191.
192. file_op2 <<"Node Delay[s] Jitter PLR[%] PR Debito[Mbps]";
193. file_op2 << "\n";
194.
195. vector<double> resultSimulation;
196. for (speedDeltMax = 0 ; speedDeltMax < valueTotal; speedDeltMax= speedDeltMax + delt ,spe
edDeltMin = speedDeltMin +4)
197. {
198. for (int numeroSimulacao = 1 ; numeroSimulacao <= 50 ;numeroSimulacao++)
199. {
200. std::cout << "Numero of simulation " << numeroSimulacao << ".\n";
201. RamAodvExample cenario1;
202. if(!cenario1.Configure(argc, argv ,numeroSimulacao))
203. NS_FATAL_ERROR ("Configuration failed. Aborted.");
204.
205. if(!cenario1.Run(speedDeltMin,speedDeltMax ,resultSimulation))
206. {
207. resultSimulation.clear();
208. continue;
209. }
210.
211. listDelay.push_back(resultSimulation[0]); //Delay Value
93
212. listJitter.push_back(resultSimulation[1]); //Jitter Value
213. listPacketLoss.push_back(resultSimulation[2]); //Packet loss Value
214. listPacketReceived.push_back(resultSimulation[3]); //Packet received Value
215. listDebito.push_back(resultSimulation[4]); //Debito Value
216.
217. resultSimulation.clear();// inicializar o vectors.
218. }
219. //-------------------Mean and Variance values Delay --------------------------------
220. double delayMean = CenarioMobilidade.CalculoMeanValue(listDelay);
221. double delayVariance = CenarioMobilidade.ComputerValueVariance ( delayMean ,listDelay)
;
222.
223. //------------------ Mean and Variance values Jitter --------------------------------
-
224. double jitterMean = CenarioMobilidade.CalculoMeanValue(listJitter);
225. double jitterVariance = CenarioMobilidade.ComputerValueVariance(jitterMean,listJitter)
;
226.
227. //-------------------Mean value packet loss ------------------------------------------
--------------
228. double packetLossMean = CenarioMobilidade.CalculoMeanValue(listPacketLoss);
229. double packetLossVariance = CenarioMobilidade.ComputerValueVariance(packetLossMean,lis
tPacketLoss);
230.
231.
232. //-------------------Mean value packet received------------------------------- -------
-----------------------
233. double packetReceivedMean = CenarioMobilidade.CalculoMeanValue(listPacketReceived);
234. double packetReceivedVariance = CenarioMobilidade.ComputerValueVariance(packetReceived
Mean,listPacketReceived);
235.
236. //-------------------Mean value debito------------------------------------------------
------------------------
237. double debitoMean = CenarioMobilidade.CalculoMeanValue(listDebito);
238. double debitoVariance = CenarioMobilidade.ComputerValueVariance(debitoMean,listDebito)
;
239.
240. //-------------------------------- write the informations to file --------------------
-----------------
241. file_op1<<4 + speedDeltMax <<" "<<delayMean<<" "<<jitterMean<<" "<<packetLossMean<
<" "<<packetReceivedMean<<" "<<debitoMean;
242. file_op1 << "\n";
243.
244. file_op2<<4 + speedDeltMax <<" "<<delayVariance<<" "<<jitterVariance<<" "<<packetL
ossVariance<<" "<<packetReceivedVariance<<" "<<debitoVariance;
245. file_op2 << "\n";
246. //=============================== reinicializacao dos parametros =====================
============================================
247. listDelay.clear();
248. listJitter.clear();
249. listPacketLoss.clear();
250. listPacketReceived.clear();
251. listDebito.clear();
252. break;
253.
254. }
255. file_op1.close();
256. file_op2.close();
257. return 0;
258. }
259.
260. double
261. RamAodvExample::CalculoMeanValue(list<double> listValue)
94
262. {
263. double Meanvalue =0.0;
264. double totalValue =0.0;
265.
266. list<double>::iterator item;
267. for(item = listValue.begin() ; item != listValue.end() ; item++)
268. {
269. if( !isfinite(*item))
270. continue;
271.
272. totalValue = totalValue + (*item);
273. }
274.
275. Meanvalue = totalValue / totalSimulation;
276. return Meanvalue;
277. }
278.
279. double
280. RamAodvExample::SumOfTheSquaredValue (list<double> listValue)
281. {
282. double result =0;
283.
284. list<double>::iterator item;
285. for(item = listValue.begin() ; item != listValue.end() ; item++)
286. {
287. if(!isfinite(*item))
288. continue;
289.
290. result = result + ((*item)*(*item));
291. }
292. return result;
293. }
294.
295. double
296. RamAodvExample::ComputerValueVariance( double valueMean ,list<double> listValue)
297. {
298. double valueVariance =0.0;
299.
300. /*-----------------------------------------------------------
301. * squaredValue = Sum(Xi^²); i varia de 1 ate totalSimulation;
302. * ---------------------------------------------------------*/
303.
304. double squaredValue = SumOfTheSquaredValue (listValue);
305. /*----------------------------------------------------------------------------------------
-
306. * ---- ---
307. * 1 | |
308. * valueVariance^² = ----------------- |squaredValue - totalSimulation*(ValueMean^²) |
309. * totalSimulation-1 | |
310. * ---- ---
311. * ---------------------------------------------------------------------------------------
--*/
312.
313. double squaredMean = valueMean * valueMean;
314.
315. squaredMean = totalSimulation*squaredMean;
316.
317. valueVariance = squaredValue - squaredMean;
318.
319. valueVariance = valueVariance / (totalSimulation-1);
320.
321. return valueVariance;
322.
323. }
95
324.
325. //========================================== Method Run ======================================
==
326. bool
327. RamAodvExample::Run (int speedDeltMin, int speedDeltMax ,vector<double> & resultSimulation)
328. {
329. bool result;
330. Config::SetDefault ("ns3::WifiRemoteStationManager::RtsCtsThreshold", UintegerValue (1));
331. CreateNodes (speedDeltMin,speedDeltMax);
332. CreateDevices ();
333. InstallInternetStack ();
334. InstallApplications ();
335.
336. Simulator::Stop(Seconds(totalTime));
337. monitor = flowmon.InstallAll();
338. Simulator::Run ();
339. result = Reportresult(resultSimulation);
340. Simulator::Destroy ();
341. Reset();
342. return result;
343. }
344.
345. bool
346. RamAodvExample::Configure(int argc , char**argv , int newseed)
347. {
348. CommandLine cmd;
349. SeedManager::SetSeed(newseed);
350. cmd.AddValue("totalTime" ,"Tempo total da simulacao",totalTime);
351. cmd.AddValue("packetSize","Tamanho do pacote UDP",packetSize);
352. cmd.AddValue("numPackets","Numeros de pacotes a serem enviados",numPackets);
353. cmd.AddValue("size"," Numero de dispositivos (nos) da rede",size);
354. cmd.AddValue("server_port","O numero de porto do servidor",server_port);
355. cmd.AddValue("interval","Entrevalo de envio dos pacotes", interval);
356. cmd.AddValue("RWalk2M","A mobilidade RandomWalk2dMobilityModel",RWalk2M);
357. cmd.AddValue("RWayM","RandomWaypointMobilityModel",RWayM);
358. cmd.AddValue("min_XX","Valor minimo do XX da area da mobilidade dos nos",min_XX);
359. cmd.AddValue("max_XX","Valor maximo da XX area da mobilidade dos nos",max_XX);
360. cmd.AddValue("min_YY","Valor minimo do XX da area da mobilidade dos nos",min_YY);
361. cmd.AddValue("max_YY","Valor maximo da XX area da mobilidade dos nos",max_YY);
362. cmd.AddValue("speedNodeMax","Velocidade do movimento dos nos",speedNodeMax);
363. cmd.AddValue("speedNodeMin","Velocidade do movimento dos nos",speedNodeMin);
364. cmd.AddValue("pauseNode","tempo de pausa dos nos",pauseNode);
365. cmd.Parse(argc,argv);
366. return true;
367. }
368.
369. void
370. RamAodvExample::CreateNodes(int speedDeltMin,int speedDeltMax )
371. {
372. nodes.Create(size);
373. // Name nodes
374. cout << "Simulacao com :" << (int)size << " nos and " << speedDeltMax << " And " << speed
DeltMin <<endl;
375. for (uint32_t i = 0; i < size; ++i)
376. {
377. std::ostringstream os;
378. os << "node-" << i;
379. Names::Add (os.str (), nodes.Get (i));
380. }
381.
382. ObjectFactory pos;
383. MobilityHelper mobility;
96
384. pos.SetTypeId ("ns3::RandomRectanglePositionAllocator");
385. pos.Set ("X", RandomVariableValue (UniformVariable (min_XX, max_XX)));
386. pos.Set ("Y", RandomVariableValue (UniformVariable (min_YY, max_YY)));
387.
388. int speedMax = speedNodeMax+speedDeltMax;
389. int speedMin = speedNodeMin + speedDeltMin;
390.
391. Ptr<PositionAllocator> wifiPositionAlloc = pos.Create ()-
>GetObject<PositionAllocator> ();
392. mobility.SetMobilityModel ("ns3::RandomWaypointMobilityModel",
393. "Speed", RandomVariableValue (UniformVariable (speedMin,speedMax)),
394. "Pause", RandomVariableValue (ConstantVariable (pauseNode)),
395. "PositionAllocator", PointerValue (wifiPositionAlloc));
396.
397. mobility.SetPositionAllocator (wifiPositionAlloc);
398. mobility.Install (nodes);
399.
400. }
401.
402. void
403. RamAodvExample::CreateDevices()
404. {
405. NqosWifiMacHelper wifiMac = NqosWifiMacHelper::Default ();
406. wifiMac.SetType ("ns3::AdhocWifiMac");
407. YansWifiPhyHelper wifiPhy = YansWifiPhyHelper::Default ();
408. YansWifiChannelHelper wifiChannel = YansWifiChannelHelper::Default ();
409. wifiPhy.SetChannel (wifiChannel.Create ());
410. WifiHelper wifi = WifiHelper::Default ();
411. wifi.SetRemoteStationManager ("ns3::IdealWifiManager");
412. wifi.SetStandard(WIFI_PHY_STANDARD_80211b);
413. devices = wifi.Install (wifiPhy, wifiMac, nodes);
414. }
415.
416. void
417. RamAodvExample::InstallInternetStack()
418. {
419. RamAodvHelper RamAodv;
420. InternetStackHelper internet;
421. internet.SetRoutingHelper (RamAodv);
422. internet.Install (nodes);
423.
424. Ipv4AddressHelper ipv4;
425. ipv4.SetBase("10.1.1.0", "255.255.255.0");
426. interfaces = ipv4.Assign(devices);
427. if (printRoutes)
428. {
429. Ptr<OutputStreamWrapper>
430. routingStream = Create<OutputStreamWrapper> ("RamAodv.routes", std::ios::out);
431. RamAodv.PrintRoutingTableAllAt (Seconds (8), routingStream);
432. }
433. }
434.
435. void
436. RamAodvExample::InstallApplications()
437. {
438. ApplicationContainer apps;
439. uint32_t timeStartUdpCliente = totalTime/5;
440. ServerNode = size -1;
441. Time interPacketInterval = Seconds(interval);
442.
443. //Create one udpServer applications on node one.
444.
445. UdpServerHelper server(server_port);
97
446. apps = server.Install(nodes.Get(ServerNode));
447. apps.Start(Seconds(2));
448. apps.Stop(Seconds(totalTime)- Seconds(0.005));
449.
450. // Create one UdpClient application to send UDP datagrams from node to node.
451.
452. UdpClientHelper client(interfaces.GetAddress(ServerNode), server_port);
453. client.SetAttribute("MaxPackets", UintegerValue(numPackets));
454. client.SetAttribute("Interval", TimeValue(interPacketInterval));
455. client.SetAttribute("PacketSize", UintegerValue(packetSize));
456. apps = client.Install(nodes.Get(clientNode));
457.
458.
459. apps.Start(Seconds(timeStartUdpCliente));
460. apps.Stop(Seconds(totalTime)- Seconds(0.01));
461. }
462.
463. string
464. RamAodvExample::i2string(int i)
465. {
466. std::ostringstream buffer;
467. buffer << i;
468. return buffer.str();
469. }
470.
471. bool
472. RamAodvExample::Reportresult(vector<double> & resultSimulation)
473. {
474. bool StatusReturn;
475. //------------------------------------------------------
476. monitor->CheckForLostPackets();
477. Ptr<Ipv4FlowClassifier> classifier = DynamicCast<Ipv4FlowClassifier > (flowmon.GetClassifi
er());
478. std::map<FlowId, FlowMonitor::FlowStats> stats = monitor->GetFlowStats();
479.
480. for (std::map<FlowId, FlowMonitor::FlowStats>::const_iterator i = stats.begin(); i != stat
s.end(); ++i)
481. {
482. Ipv4FlowClassifier::FiveTuple t = classifier->FindFlow(i->first);
483.
484. std::string client_address = "10.1.1.";
485. std::string server_address = "10.1.1.";
486.
487. std::string id_client = i2string(1);
488. std::string id_server = i2string(ServerNode+1);
489.
490. client_address = client_address + id_client;
491. server_address = server_address + id_server;
492.
493. if (t.sourceAddress == client_address.c_str() &&
494. t.destinationAddress == server_address.c_str() &&
495. t.destinationPort == server_port)
496. {
497.
498. resultSimulation.push_back(i->second.delaySum.GetSeconds() / i-
>second.rxPackets); //Delay
499. resultSimulation.push_back(i->second.jitterSum.GetSeconds()/(i->second.rxPackets -
1)); //Jitter
500. resultSimulation.push_back((i->second.txPackets - i-
>second.rxPackets) / (double) i->second.txPackets); // PRL
501. resultSimulation.push_back(i-> second.rxPackets); //packet receveid
502. resultSimulation.push_back(i->second.rxBytes * 8.0 / totalTime
/ 1024 / 1024); //debito
503.
98
504. //========================== imprimir ============================================
===================
505. cout << "Flow " << i->first << " (" << t.sourceAddress << " -
> " << t.destinationAddress << ")"<< "\n"
506. << " Tx[B]: " << i->second.txBytes << "\n"
507. << " Pacotes Transmitidos: " << i->second.txPackets << "\n"
508. << " Rx[B]: " << i->second.rxBytes << "\n"
509. << " Pacotes Recebidos: " << i->second.rxPackets << "\n"
510. << " Tput[Mbps]: " << i-
>second.rxBytes * 8.0 / timeSimulation / 1024 / 1024 << "\n"
511. << " PLR[%]: " << (i->second.txPackets - i->second.rxPackets) / (double) i-
>second.txPackets<< "\n"
512. << " D[s]: " << i->second.delaySum.GetSeconds() / i->second.rxPackets << endl;
513.
514. if(i->second.rxPackets == 0)
515. StatusReturn = false;
516. else
517. StatusReturn = true;
518. }
519. }
520. std::cout << "END \n\n\n" << std::endl;
521. return StatusReturn;
522.
523. }