ads:
Universidade Federal do Rio Grande do Norte
Centro de Ciências Exatas e da Terra
Departamento de Informática e Matemática Aplicada
Mestrado em Sistemas e Computação
Avaliação de Desempenho de Protocolos de
Roteamento para Redes Móveis Ad Hoc Sob
Condições de Tráfego de Aplicações de VideoFone
Glaucia Melissa Medeiros Campos
Natal/RN
Maio de 2005
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ii
Glaucia Melissa Medeiros Campos
Avaliação de Desempenho de Protocolos de Roteamento para
Redes Móveis
Ad Hoc
Sob Condições de Tráfego de
Aplicações de VideoFone
Dissertação de Mestrado apresentada à
banca examinadora do Programa de Pós-
Graduação em Sistemas e Computação da
Universidade Federal do Rio Grande do Norte,
como requisito parcial para a obtenção do título
de Mestre em Sistemas e Computação.
Orientador:
Prof.
Gledson Elias da Silveira
Natal/RN
Maio de 2005
ads:
iii
Glaucia Melissa Medeiros Campos
Avaliação de Desempenho de Protocolos de Roteamento para
Redes Móveis
Ad Hoc
Sob Condições de Tráfego de
Aplicações de VideoFone
Dissertação de Mestrado apresentada à banca examinadora do Programa de Pós-Graduação
em Sistemas e Computação da Universidade Federal do Rio Grande do Norte, como requisito
parcial para a obtenção do título de Mestre em Sistemas e Computação.
Orientador:
Prof. Gledson Elias da Silveira
_____________________________________________
Prof. Gledson Elias da Silveira, D. Sc. – UFPB
_____________________________________________
Prof. Ivan Saraiva Silva, D. Sc. – UFRN
_____________________________________________
Prof. Djamel Fawzi Hadj Sadok, D. Sc. – UFPE
Natal/RN
Maio de 2005
iv
Dedico este trabalho, e tudo o que ele
representa, à minha família, em especial à
minha mãe e as minhas irmãs, companhias
constantes e fundamentais em minha vida.
v
A G R A D E C I M E N T O S
A Deus pela companhia fiel, sempre iluminando os meus caminhos... Ah! Senhor,
obrigada também pela vida, pelo Teu amor, pelo conforto nas horas mais difíceis... Obrigada
Pai por me conduzir em Teus braços quando tudo parecia perdido, reabastecendo-me com a
Tua força, fazendo-me acreditar que ao amanhecer tudo seria diferente, que os obstáculos e
os desafios seriam vencidos, e que as recompensas logo viriam.
Aos meus familiares, em especial à minha mãe, Leci e às minhas irmãs, Glenda e
Gardênia. Obrigada mãe por ter me guiado pelos caminhos corretos, pelo esforço e
dedicação para que hoje eu pudesse ser o que sou. Eu sei que não é fácil amar e educar os
filhos com a responsabilidade de ser pai e mãe ao mesmo tempo. Mas hoje, pode ter certeza
de que os seus esforços não foram em vão. Às minhas irmãs, obrigada pelo carinho, pelos
conselhos e desentendimentos (risos)... podem ter certeza de que tudo isso foi muito
importante para a minha formação. Agradeço a alguém que infelizmente partiu antes que este
momento chegasse, o meu pai, Gilberto... Queria muito poder encontrá-lo e abraçá-lo, sentir
o seu coração transbordando de orgulho. Mas, enfim ... sei que de uma forma ou de outra
ele sempre estará comigo.
A um alguém que me acolheu, acreditou em mim, me fez acreditar que eu seria
capaz, me ajudou nos momentos mais difíceis e desesperadores, me conduziu para que tudo
saísse “perfeito”. Alguém que eu aprendi a gostar e a respeitar durante estes dois anos de
dedicação e que sempre vai ser o meu referencial. Ao meu orientador, Glêdson Elias.
Aos verdadeiros amigos que encontrei durante o mestrado. Amigos estes que me
aconselharam, que de uma forma ou de outra contribuíram imensamente para este
trabalho, e ainda ouviram todas as minhas lamentações (e não foram poucas, risos). Não
seria justo citar nomes, mas aqueles que são realmente especiais sabem o valor que tem
para mim. Podem ter certeza de que onde eu estiver vocês estarão comigo.
Aos meus vizinhos, Jaqueline e Júnior, por terem trazido ao mundo a criatura mais
linda e mais maravilhosa que eu já conheci. Um alguém tão pequenininho, mas que sempre
me traz grandes alegrias... o meu Fafito (Rafael).
vi
Aos professores Ivan Saraiva e Djamel Sadok, membros da banca examinadora,
pelos comentários que contribuíram imensamente para o enriquecimento deste trabalho.
Ao programa de incentivo à pesquisa da CAPES pela bolsa durante estes dois anos
de mestrado, ao professor Dario por ter cedido o laboratório PROMETH para realizar
pesquisas e a toda família DIMAP.
Enfim, agradeço a todos que diretamente (ou indiretamente) me ajudaram
durante todo este mestrado...
vii
“Quando coisinhas pequenininhas tirarem você do
sério, pare um segundo para contemplar o tamanho do
sol ou a distância até as estrelas – isso sempre põe as
coisas em perspectivas.”
(Bradley Trevor Greive)
viii
SUMÁRIO
1. INTRODUÇÃO.....................................................................................................................1
1.1 M
OTIVAÇÃO E
O
BJETIVOS DO
T
RABALHO
..........................................................................4
1.2 O
RGANIZAÇÃO DO
T
RABALHO
...........................................................................................5
2.
REDES MÓVEIS
AD HOC
..................................................................................................7
2.1 C
OMUNICAÇÃO EM
R
EDES
M
ÓVEIS
A
D HOC
.....................................................................10
2.1.1 Padrão IEEE 802.11 .................................................................................................10
3. PROTOCOLOS DE ROTEAMENTO
AD HOC
.............................................................16
3.1 C
LASSIFICAÇÃO DOS
P
ROTOCOLOS DE
R
OTEAMENTO
A
D HOC
.........................................17
3.1.1 DESTINATION SEQUENCED DISTANCE VECTOR (DSDV)................................19
3.1.2 AD HOC ON-DEMAND DISTANCE VECTOR (AODV) .........................................23
3.1.3 DYNAMIC SOURCE ROUTING (DSR)...................................................................28
3.1.5 Comparação entre os Protocolos de Roteamento Ad hoc ........................................33
4. MODELO DE SIMULAÇÃO............................................................................................35
4.1 A
MBIENTE DE
S
IMULAÇÃO
...............................................................................................36
4.1.1 Network Simulator ....................................................................................................36
4.2 C
ARACTERIZAÇÃO DA
A
PLICAÇÃO DE
V
ÍDEO
...................................................................38
4.3 D
ESCRIÇÃO DOS
C
ENÁRIOS
..............................................................................................41
4.4 M
ODELO DE
M
OBILIDADE
................................................................................................43
4.1.1 Definição do Padrão de Movimento para os Dispositivos Móveis...........................44
4.5 P
ARÂMETROS
Q
UANTITATIVOS
........................................................................................47
5. ANÁLISE DOS RESULTADOS .......................................................................................49
5.1 T
AXA DE
E
NTREGA
...........................................................................................................50
5.1.1 Distribuição do Número de Pacotes Perdidos na Seqüência ...................................58
5.2 R
ETARDO DE
E
NTREGA
.....................................................................................................61
5.3 D
ISTRIBUIÇÃO DO
R
ETARDO DE
E
NTREGA DE
P
ACOTES
...................................................66
5.4 V
ARIAÇÃO DO
R
ETARDO
(
J
ITTER
).....................................................................................69
5.4 C
ARGA DE
R
OTEAMENTO
.................................................................................................73
6. TRABALHOS RELACIONADOS....................................................................................80
7. CONSIDERAÇÕES FINAIS.............................................................................................85
7.1 T
RABALHOS
F
UTUROS
......................................................................................................87
REFERÊNCIAS......................................................................................................................89
ANEXO....................................................................................................................................93
ix
LISTA DE FIGURAS
Figura 1.1 – Ambiente de Comunicação sem fio Infra-Estruturado...........................................3
Figura 2.1 – Rede
ad hoc
com três dispositivos .........................................................................8
Figura 2.2 – Modelo de Arquitetura Infra-Estruturado para Redes 802.11..............................11
Figura 2.3 – Modelo de Arquitetura Ad hoc para Redes 802.11..............................................11
Figura 2.4 – Método de Acesso do DFWMAC Distribuído.....................................................13
Figura 2.5 – Problema do Terminal Escondido ........................................................................14
Figura 3.1 – Movimento em Redes Móveis
Ad hoc
.................................................................20
Figura 3.2 – Procedimento inicial de requisição de rotas para o AODV..................................24
Figura 3.3 – Procedimento de retransmissão de pacotes RREQ para o AODV .......................25
Figura 3.4 – Procedimento de resposta de rotas iniciado pelo destino para o AODV..............26
Figura 3.5 – Procedimento de resposta de rotas iniciado por um dispositivo intermediário para
o AODV .................................................................................................................26
Figura 3.6 – Procedimento inicial de requisição de rotas para o DSR .....................................29
Figura 3.7 – Procedimento de retransmissão de pacotes de requisição de rotas para o DSR...30
Figura 3.8 – Procedimento de resposta de rotas iniciado pelo destino para o DSR .................31
Figura 3.9 – Procedimento de resposta de rotas iniciado por um dispositivo intermediário para
o DSR.....................................................................................................................31
Figura 4.1 – Arquitetura Geral da Ferramenta NS....................................................................37
Figura 4.2 – Cenário 3x3 ..........................................................................................................42
Figura 4.3 – Arquivo de saída que representa o padrão de movimento dos dispositivos
móveis ....................................................................................................................45
Figura 4.4 – Arquivo de entrada utilizado na simulação de um cenário 4x4............................46
Figura 5.1 – Taxa de entrega dos pacotes de dados por sessão de videofone para o AODV em
cenários de mobilidade alta....................................................................................51
Figura 5.2 – Taxa de entrega dos pacotes de dados por sessão de videofone para o DSR em
cenários de mobilidade alta....................................................................................51
Figura 5.3 – Taxa de entrega dos pacotes de dados por níveis de mobilidade para o DSDV em
cenários com uma sessão de videofone..................................................................52
Figura 5.4 – Taxa de entrega dos pacotes de dados por níveis de mobilidade para o AODV em
cenários com oito sessões de videofone.................................................................52
x
Figura 5.5 – Taxa de entrega dos pacotes de dados por níveis de mobilidade para o DSR em
cenários com oito sessões de videofone.................................................................52
Figura 5.6 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade baixa com uma
sessão de videofone................................................................................................53
Figura 5.7 - Taxa de entrega dos pacotes de dados nos cenários de mobilidade moderada com
uma sessão de videofone........................................................................................53
Figura 5.8 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade alta com uma
sessão de videofone...............................................................................................54
Figura 5.9 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade baixa com oito
sessões de videofone ..............................................................................................55
Figura 5.10 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade moderada
com oito sessões de videofone ...............................................................................55
Figura 5.11 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade alta com oito
sessões de videofone ..............................................................................................55
Figura 5.12 – Distribuição do número de pacotes perdidos na seqüência para o protocolo
DSDV, em cenários 3x3 de mobilidade baixa, com uma sessão de videofone .....59
Figura 5.13 – Retardo de entrega por sessão de videofone para o AODV em cenários de
mobilidade alta.......................................................................................................61
Figura 5.14 – Retardo de entrega por sessão de videofone para o DSR em cenários de
mobilidade alta.......................................................................................................62
Figura 5.15 – Retardo de Entrega por níveis de mobilidade para o DSDV em cenários com
uma sessão de videofone........................................................................................62
Figura 5.16 – Retardo de Entrega por níveis de mobilidade para o AODV em cenários com
uma sessão de videofone........................................................................................63
Figura 5.17 – Retardo de Entrega por níveis de mobilidade para o DSR em cenários com uma
sessão de videofone................................................................................................63
Figura 5.18 – Retardo de Entrega nos cenários de mobilidade baixa com uma sessão de
videofone................................................................................................................64
Figura 5.19 – Retardo de Entrega nos cenários de mobilidade moderada com uma sessão de
videofone................................................................................................................64
Figura 5.21 – Retardo de Entrega nos cenários de mobilidade baixa com oito sessões de
videofone................................................................................................................65
Figura 5.22 – Retardo de Entrega nos cenários de mobilidade moderada com oito sessões de
videofone................................................................................................................66
xi
Figura 5.23 – Retardo de Entrega nos cenários de mobilidade alta com oito sessões de
videofone................................................................................................................66
Figura 5.24 – Probabilidade de Entrega dos Pacotes de Dados em Intervalos de Retardo para
Cenários de Mobilidade Baixa...............................................................................67
Figura 5.25 – Probabilidade de Entrega dos Pacotes de Dados em Intervalos de Retardo para
Cenários de Mobilidade Alta .................................................................................68
Figura 5.26 – Variação do retardo dos pacotes de dados por sessão de videofone para o
AODVem cenários de mobilidade alta ..................................................................70
Figura 5.27 – Variação do retardo dos pacotes de dados por sessão de videofone para o DSR
em cenários de mobilidade alta..............................................................................70
Figura 5.28 – Variação do retardo para o AODV em cenários com uma sessão de videofone71
Figura 5.29 – Variação do retardo para o DSR em cenários com uma sessão de videofone....71
Figura 5.30 – Variação do retardo em cenários de mobilidade moderada com uma sessão de
videofone................................................................................................................72
Figura 5.31 – Variação do retardo em cenários de mobilidade moderada com oito sessões de
videofone................................................................................................................72
Figura 5.32 – Variação do retardo em cenários de mobilidade alta com uma sessão de
videofone................................................................................................................72
Figura 5.33 – Variação do retardo em cenários de mobilidade alta com oito sessões de
videofone................................................................................................................73
Figura 5.34 - Carga de roteamento para o DSDV em cenários com uma sessão de
videofone................................................................................................................73
Figura 5.35 – Carga de roteamento para o AODV em cenários com uma sessão de
videofone................................................................................................................74
Figura 5.36 – Carga de roteamento para o DSR em cenários com uma sessão de videofone..74
Figura 5.37 – Carga de roteamento para o AODV em cenários de mobilidade alta ................75
Figura 5.38 – Carga de roteamento para o DSR em cenários de mobilidade alta ....................75
Figura 5.39 – Carga de roteamento nos cenários de mobilidade baixa com uma sessão de
videofone................................................................................................................76
Figura 5.40 – Carga de Roteamento nos cenários de mobilidade moderada com uma sessão de
videofone................................................................................................................76
Figura 5.41 – Carga de Roteamento nos cenários de mobilidade alta com uma sessão de
videofone................................................................................................................77
xii
Figura 5.42 – Carga de Roteamento nos cenários de mobilidade baixa com oito sessões de
videofone................................................................................................................78
Figura 5.43 – Carga de Roteamento nos cenários de mobilidade moderada com oito sessões de
videofone................................................................................................................78
Figura 5.44 – Carga de Roteamento nos cenários de mobilidade alta com oito sessões de
videofone................................................................................................................78
xiii
LISTA DE TABELAS
Tabela 3.1 – Tabela de roteamento do dispositivo D ...............................................................21
Tabela 3.2 – Tabela de roteamento do dispositivo D depois das mudanças na topologia
da rede ....................................................................................................................21
Tabela 3.3 – Quadro Comparativo dos Protocolos de Roteamento
Ad hoc
..............................34
Tabela 4.1 – Parâmetros de Simulação.....................................................................................47
Tabela 5.1 – Número de pacotes de dados entregues ao destino com retardo maior do que
400ms (Mobilidade Baixa – 1 sessão de videofone)..............................................57
Tabela 5.2 – Número de pacotes de dados entregues ao destino com retardo maior do que
400ms (Mobilidade Alta - 8 sessões de videofone) ..............................................57
Tabela 5.3 - Distribuição das rajadas de perda de pacotes na seqüência em cenários de
mobilidade alta com 1 sessão de videofone (Protocolo DSDV)............................58
Tabela 5.4 – Distribuição das rajadas de perda de pacotes na seqüência em cenários de
mobilidade alta com 1 sessão de videofone (Protocolos AODV e DSR) .............59
Tabela 5.5 – Distribuição das rajadas de perda de pacotes na seqüência em cenários de
mobilidade alta com 8 sessões de videofone (Protocolos AODV e DSR)...........60
Tabela 7.1 – Resultados das Simulações ..................................................................................85
xiv
LISTA DE SIGLAS
AODV
Ad Hoc On-Demand Distance Vector Routing
ARP
Address Resolution Protocol
BSS
Basic Service Set
CADV
Congestion-Aware Distance Vector
CCA
Clear Channel Assessment Signal
CGSR
Clusterhead Gateway Switch Routing Protocol
CTS
Clear to Send
DCF
Distributed Coordination Function
DFWMAC
Distributed Foundation Wireless MAC
DHSS
Direct Sequence Spread Spectrum
DIFS
DCF Inter-Frame Spacing
DSDV
Destination-Sequenced Distance-Vector
DSR
Dynamic Source Routing
ERB
Estação de Radio Base
ESS
Extended Service Set
FHSS
Frequence Hopping Spread Spectrum
GFSK
Gaussian Frequence Shift Keying
IEEE
Institute of Electrical and Electronic Engineers
IP
Internet Protocol
ISM
Industrial, Scientific and Medical
MAC
Medium Access Control
MANET
Mobile Ad Hoc Network
NAM
Network Animator
NAV
Net Allocation Vector
NPDU
Network Protocol Data Unit
NS
Network Simulator
OLSR
Optimized Link State Routing
PA
Ponto de Acesso
PCF
Pontual Coordination Function
PSK
Phase Shift Keying
QCIF
Quarter-CIF (Common Intermediate Formate)
xv
RERR
Route Error
RREP
Route Replay
RREQ
Route Request
RTS
Request to Send
SCO
Synchronous Connection-Oriented
SIFS
Short Inter-Frame Spacing
TBRPF
Topology Broadcast based on Reverse-Path Forwarding
TORA
Temporally-Ordered Routing Algorithm
TTL
Time-to-Life
UDP
User Datagram Protocol
WLANs
Wireless Local Area Networks
WPANs
Wireless Personal Area Networks
WRP
Wireless Routing Protocol
ZRP
Zone Routing Protocol
xvi
AVALIAÇÃO DE DESEMPENHO DE PROTOCOLOS DE ROTEAMENTO PARA
REDES MÓVEIS AD HOC SOB CONDIÇÕES DE TRÁFEGO DE
APLICAÇÕES DE VIDEOFONE
Autora: GLAUCIA MELISSA MEDEIROS CAMPOS
Orientador: Profº GLÊDSON ELIAS DA SILVEIRA
RESUMO
A evolução das tecnologias de comunicação sem fio, aliada à grande variedade e
disponibilidade de dispositivos portáteis, contribui fortemente para a adoção das redes
móveis, inovando o conceito de conectividade no sentido de atender a requisitos de acesso
sem restrição de tempo e espaço. Neste contexto, destacam-se as redes móveis
ad hoc
, que
consistem em uma coleção de dispositivos independentes de qualquer infra-estrutura,
formando uma rede temporária e arbitrária. Um dos maiores desafios para as redes
ad hoc
é
manter a conectividade entre os dispositivos móveis, devido às mudanças freqüentes na
topologia da rede. Portanto, é imprescindível a adoção de mecanismos de roteamento que
considerem as restrições de um ambiente de rede móvel. Embora existam diversas propostas
de protocolos de roteamento para redes móveis
ad hoc
, a adoção de um destes protocolos
ainda é uma tarefa bastante complexa. Diversos aspectos devem ser considerados para não
comprometer o desempenho da rede e da própria aplicação. Por exemplo, aplicações de
videofone requerem que parâmetros como taxa de entrega, retardo de entrega e variação do
retardo sejam respeitados. Neste contexto, este trabalho apresenta uma análise comparativa
dos principais protocolos de roteamento para redes móveis
ad hoc
(DSDV, AODV e DSR). A
principal contribuição deste trabalho é a análise do comportamento destes protocolos de
roteamento sob as condições de tráfego gerado por aplicações de videofone em um cenário
híbrido de redes
ad hoc
, proposto como uma possível solução de conectividade plena
requerida por sistemas de monitoramento de vídeo digital. O cenário híbrido é caracterizado
por uma matriz de pontos de acesso fixos que implementam protocolos de roteamento para
redes móveis
ad hoc
.
Palavras-Chaves:
Redes Móveis
Ad Hoc
, Protocolos de Roteamento, Videofone e Sistemas de Monitoramento
de Vídeo.
xvii
AVALIAÇÃO DE DESEMPENHO DE PROTOCOLOS DE ROTEAMENTO PARA
REDES MÓVEIS AD HOC SOB CONDIÇÕES DE TRÁFEGO DE
APLICAÇÕES DE VIDEOFONE
Autora: GLAUCIA MELISSA MEDEIROS CAMPOS
Orientador: Profº GLÊDSON ELIAS DA SILVEIRA
ABSTRACT
The evolution of wireless communication technologies, together with the variety and
availability of portable devices, strongly contributes to the adoption of mobile networks,
leveraging the concept of connectivity in the sense of meeting access requirements that avoid
time and space constraints. In such a context, it can be highlighted
ad hoc
mobile networks,
which are composed of a collection of devices that are independent of infrastructure and,
jointly, create a temporary and arbitrary network. Taking into account the movement of
mobile devices, one of the major challenges of ad hoc mobile networks is to ensure the full
connectivity among them. Therefore, it is essential the adoption of routing mechanisms that
regard mobile network issues. Despite the existence of diverse ad hoc routing protocol
proposals, the adoption of one of such protocols in a specific network scenario and for a given
class of application is still a complex task. Various aspects must be considered in order to do
not compromise the performance of the network and supported applications. For example, in
videophone applications, parameters such as packet delivery rate, end-to-end delay and jitter
ought to be considered. In such a context, this work presents a simulation-based comparative
analysis of the main ad hoc routing protocols (DSDV, AODV and DSR). The key
contribution of this work is the analysis of the behavior of such routing protocols under a
traffic pattern generated by videophone applications in a hybrid scenario of ad hoc mobile
networks, which is proposed as a possible solution to provide the full connectivity required by
video surveillance systems. The hybrid scenario is characterized as a matrix of fix access
points that support ad hoc routing protocols.
Keywords:
Ad hoc
mobile networks, routing protocols, videophone, video surveillance.
1
1
Capítulo 1
Introdução
A evolução da tecnologia de comunicação sem fio, aliada à crescente variedade e
disponibilidade de dispositivos portáteis, está inovando o conceito de conectividade, onde a
mobilidade de dispositivos e serviços é um requisito extremamente relevante e urgente, e
certamente redefinirá paradigmas convencionais de trabalho, aprendizado e lazer.
Este cenário contribuiu fortemente para a expansão das redes de computadores e
despertou grande interesse das empresas comerciais e instituições acadêmicas em desenvolver
tecnologias e padrões que permitam o acesso móvel e, em tempo real, a um conjunto de
serviços e informações restritos, até então, aos ambientes de redes tradicionais. Em
conseqüência, a comunicação sem fio ganhou um espaço considerável nas tecnologias de
transmissão de dados, apresentando-se também como solução para a comunicação em
ambientes de redes locais. Neste contexto, os padrões para redes móveis que mais se
desenvolveram foram
Bluetooth
[Miller 01],
HomeRF
[Kaminski 01] e o
IEEE 802.11 [IEEE 99].
Uma rede móvel sem fio consiste em uma coleção de dispositivos transmissores e
receptores que se movimentam em uma determinada área e utilizam, normalmente, como
tecnologia de transmissão freqüências de radio ou infravermelho. Estas redes foram
desenvolvidas com o objetivo de superar as limitações de mobilidade e instalação de
cabeamento impostas pelas redes tradicionais. Algumas aplicações práticas incluem:
•
Utilização de dispositivos móveis por profissionais para executar tarefas (acesso a
dados de estoque, índices financeiros, elaboração de relatórios etc) enquanto estão
em trânsito;
2
•
Envio e recebimento de e-mails, mensagens e arquivos;
•
Manutenção e acompanhamento de serviços de empresas de entrega utilizando
dispositivos móveis;
•
Utilização em serviços de emergência nos locais de desastres ou de emergências
médicas para acesso a informações e dados referentes à situação;
•
Consulta a sistemas de informações que fornecem dados sobre hotéis, restaurantes
e pontos turísticos a visitantes, utilizando como parâmetro de consulta a
localização do usuário.
A combinação da comunicação sem fio e a mobilidade dos dispositivos
computacionais impõem restrições, típicas do ambiente, que devem ser consideradas no
desenvolvimento de tecnologias e padrões para redes móveis: capacidade de comunicação
limitada, com largura de banda variável e altas taxas de erros; autonomia de energia limitada
por baterias com restrições de consumo; limitação física do hardware, o que restringe o poder
de processamento dos dispositivos; perda temporária de comunicação provocando a perda de
pacotes; e a falta de segurança dos dados, comprometendo a privacidade das informações dos
usuários devido a um maior grau de susceptibilidade a danos físicos, acesso não autorizado,
perda ou roubo [Forman 94, Satyanarayanan 96].
As redes móveis são classificadas, de acordo com o IEEE (
Institute of Electrical and
Electronics Engineers
), em dois tipos:
infra-estruturada
e
ad hoc
(independente). Nas redes
infra-estruturadas, a comunicação entre os dispositivos móveis é sempre realizada através de
um ponto de acesso fixo e central, que serve como ponte entre os vários dispositivos móveis
localizados em sua área de alcance, assim como acontece nas redes de telefonia celular
[Smith 01]. Por outro lado, nas redes
ad hoc
[Giordano 01, Perkins 01], cada dispositivo
móvel pode comunicar-se diretamente com outros dentro de sua área de alcance,
estabelecendo conexões de forma dinâmica, temporária e arbitrária, sem a necessidade do
ponto de acesso.
As redes infra-estruturadas são constituídas de componentes fixos e móveis. Os
componentes móveis representam os dispositivos computacionais portáteis que permitem a
mobilidade do usuário baseado na comunicação sem fio. Os componentes fixos, também
conhecidos por Pontos de Acesso (PA) ou Estações de Radio Base (ERB), são responsáveis
pelo gerenciamento dos dispositivos móveis que estão dentro de sua célula – área geográfica
3
de cobertura. As redes são divididas em um conjunto de células, sendo que para cada uma
delas há necessidade de pelo menos um ponto de acesso fixo e central. A Figura 1.1 apresenta
o modelo de uma rede infra-estruturada, onde os dispositivos comunicam-se através das
ERBs. Os hexágonos representam as células que são gerenciadas pelas ERBs.
Figura 1.1 – Ambiente de Comunicação sem fio Infra-Estruturado
(Fonte: Figura baseada em [Amorim 02])
As redes infra-estruturadas ainda apresentam como desafio o procedimento de
handoff
provocado pela mobilidade dos dispositivos [Santos 03]. Este procedimento permite o usuário
manter uma chamada enquanto move-se entre as células da rede. As ERBs comunicam-se
através de redes fixas de alta velocidade (Mbps ou Gbps) trocando as informações necessárias
à mudança de domínio de células para os dispositivos.
A principal desvantagem das redes infra-estruturadas é a necessidade de uma rede fixa
pré-estabelecida, o que muitas vezes é inviável em cenários de desastres (incêndios,
inundações, terremotos e campos de batalha), esforços coordenados de emergência e resgate,
reuniões, feiras e exposições. As redes
ad hoc
surgem como solução para estes cenários,
devido às suas vantagens quando comparadas às redes infra-estruturadas: facilidades de
instalação; tolerância à falhas com a reconfiguração dinâmica da rede; conectividade direta
entre os dispositivos móveis dentro da mesma área de alcance; e a mobilidade dos
dispositivos que compõem a rede, em contraposição à falta de mobilidade dos pontos de
acesso fixos [Camara 99].
G
G
Rede Fixa
4
Entretanto, os dispositivos móveis das redes
ad hoc
só conseguem transmitir
informações para um outro dispositivo dentro da sua área de transmissão. Conseqüentemente,
para que os pacotes alcancem um destino fora da sua área de alcance, cada dispositivo deve
prover facilidades de roteamento aos demais. Por este motivo, um dos maiores desafios para
as redes
ad hoc
está relacionado com a transmissão eficiente dos pacotes de dados entre os
dispositivos móveis. A Figura 1.2 mostra um exemplo de redes móveis
ad hoc
que representa
um ambiente de comunicação sem fio entre militares em um campo de batalha.
Figura 1.2 – Ambiente de Comunicação sem fio Ad hoc
1.1 Motivação e Objetivos do Trabalho
O baixo custo, a facilidade de implantação e a grande variedade de aplicações são os
principais fatores responsáveis pela adoção das redes
ad hoc
. No entanto, ainda existem
alguns desafios que são objetos de pesquisas da academia e indústria.
Um dos principais problemas existentes em redes
ad hoc
está relacionado à
possibilidade de perda de comunicação entre os dispositivos, como conseqüência da
mobilidade que provoca freqüentes mudanças na topologia da rede. A comunicação entre
estes dispositivos deve ser sempre restaurada, segundo um mecanismo de roteamento que
considere as características específicas do ambiente sem fio. O problema surge a partir do
momento em que se deseja enviar uma mensagem para um outro dispositivo que se move com
freqüência, pois há necessidade de se encontrar o destino desta mensagem e então definir uma
5
rota até ele. Depois de estabelecida, esta rota deve ser mantida até o final da comunicação
através de um mecanismo de manutenção de rotas.
Existem diversas razões que explicam o motivo do roteamento ser uma tarefa tão
complexa para as redes
ad hoc
: mobilidade e topologia de rede dinâmica, maior retardo,
interferência com outros dispositivos móveis, inexistência de uma entidade central,
comunicação através de um meio sem fio e maior consumo de energia dos dispositivos
computacionais. Portanto, é imprescindível a adoção de protocolos de roteamento eficientes.
O problema de roteamento tem sido o foco de muitos dos trabalhos na área de redes
móveis
ad hoc
. Como conseqüência, diversas propostas de protocolos de roteamento têm sido
desenvolvidas [Royer 99]. Porém, a seleção de um determinado protocolo, em um cenário de
rede específico e para uma classe de aplicação ainda é uma tarefa bastante complexa.
Diversos aspectos devem ser considerados para não comprometer o desempenho geral da rede
e da própria aplicação. Por exemplo, as aplicações de videofone requerem que parâmetros tais
como taxa de entrega, retardo de entrega e variação do retardo sejam respeitados.
Como conseqüência do desenvolvimento das redes
ad hoc
e o avanço nas técnicas de
compressão de vídeo digital, a transmissão de objetos não convencionais, tais como áudio e
vídeo, através de tecnologias de transmissão sem fio, apresenta-se como solução para diversos
sistemas. Por exemplo, os sistemas de monitoramento de vídeo que são utilizados como
recursos adicionais e necessários para a segurança institucional e pessoal.
Neste contexto, este trabalho apresenta uma análise comparativa, baseada em
simulação, dos principais protocolos de roteamento para redes
ad hoc
(DSDV [Perkins 94],
AODV [Perkins 03] e DSR [Johnson 04]), com o objetivo de avaliar o comportamento dos
mesmos em sistemas de monitoramento de vídeo, em um cenário de redes
ad hoc
constituído
de dispositivos fixos e móveis [Campos 05]. Os resultados são analisados considerando os
requisitos de retardo de entrega, variação do retardo (
jitter
), taxa de perda dos pacotes e carga
de roteamento que modelam aplicações de videofone. Nesta análise, os pontos de
variabilidade são os próprios protocolos, a abrangência da rede, a mobilidade dos usuários e o
número de sessões de videofone estabelecido.
1.2 Organização do Trabalho
O trabalho está organizado em sete capítulos. A introdução é o primeiro deles e o restante está
estruturado da seguinte forma:
6
Capítulo 2 –
Redes Móveis Ad hoc:
apresenta os principais conceitos relacionados a redes
móveis
ad hoc
, apresentando suas vantagens e desvantagens e explicando o porquê do
roteamento nestas redes ser uma tarefa tão complexa. Este capítulo ainda descreve o padrão
para redes sem fio IEEE 802.11.
Capítulo 3 –
Protocolos de Roteamento Ad hoc
: apresenta uma discussão sobre as principais
características que um protocolo de roteamento deve considerar para as redes
ad hoc
e a
descrição dos protocolos avaliados, identificando suas propriedades.
Capítulo 4 –
Modelo de Simulação
: descreve o modelo de simulação adotado na ferramenta
Network Simulator
, caracterizando a aplicação de videofone para os sistemas de
monitoramento de vídeo e identificando os cenários e o modelo de mobilidade adotado pelos
usuários de dispositivos móveis.
Capítulo 5 –
Análise dos Resultados
: apresenta os resultados das simulações realizadas, com
base em parâmetros quantitativos tais como: taxa de entrega, retardo de entrega, variação do
retardo e carga de roteamento. A análise destes parâmetros considera os requisitos das
aplicações de videofone.
Capítulo 6 –
Trabalhos Relacionados:
apresenta alguns dos trabalhos desenvolvidos com o
objetivo de analisar qual o melhor protocolo de roteamento para redes
ad hoc
, fazendo
comentários sobre no que cada um deles difere da proposta deste trabalho.
Capítulo 7 –
Considerações Finais
: apresenta considerações sobre as simulações realizadas e
indica possíveis temas como trabalhos futuros que podem dar continuidade à proposta deste
trabalho.
7
Capítulo 2
Redes Móveis
Ad hoc
A comunicação sem fio vem ganhando um espaço considerável nas tecnologias de
transmissão de dados, deixando de ser utilizada apenas para comunicações de longas
distâncias (por exemplo, via satélite), para fazer parte dos ambientes locais. Essa tendência foi
fortalecida pelo investimento das instituições e empresas com o objetivo de aplicar a
transmissão sem fio em redes de computadores.
Neste contexto, um dos principais focos de pesquisas são as redes móveis
ad hoc
(MANET –
Mobile Ad hoc Network
) [MANET 04], que consistem em uma coleção de
dispositivos independentes de qualquer infraestrutura, formando uma rede temporária e de
forma arbitrária. O grande interesse por esta tecnologia deve-se ao baixo custo, a facilidade de
implantação e a grande variedade de aplicações que estas redes podem fornecer.
Cada um dos dispositivos que fazem parte da rede possui uma interface sem fio e
comunica-se com os outros dispositivos através de tecnologias de transmissão como ondas de
rádio ou infravermelho. Estes dispositivos freqüentemente são móveis, mas também podem
comportar-se como um ponto de acesso à Internet, por exemplo. A comunicação entre eles
somente é possível quando um está dentro do raio de alcance do outro, sendo portanto
vizinhos imediatos. Conseqüentemente, um pacote que deve alcançar um destino, fora da área
de transmissão da origem, deverá utilizar outros dispositivos intermediários como roteadores.
Assim, cada dispositivo deve prover mecanismos de roteamento para outros dispositivos na
rede, permitindo o estabelecimento de rotas entre pares de dispositivos com múltiplos saltos
(
multi-hop
), ao contrário do que acontece nas redes infra-estruturadas, onde existem pontos de
acesso fixos e centrais que permitam a comunicação com um simples salto (
single-hop
).
8
A Figura 2.1 apresenta uma rede
ad hoc
simples com apenas três dispositivos. Os
dispositivos com identificações
A
e
C
não estão dentro do raio de alcance um do outro.
Contudo, o dispositivo
B
pode ser utilizado como roteador para encaminhar mensagens de
A
até
C
. No entanto, o roteamento em redes
ad hoc
[Johnson 94, Corson 99] não é tão simples
como mostra a Figura 2.1. Imagine uma situação onde vários dispositivos estão se
comunicando ao mesmo tempo em que se movimentam. Por este motivo, mecanismos de
roteamento que considerem a mobilidade dos dispositivos devem ser adotados em redes
móveis
ad hoc.
Figura 2.1 – Rede ad hoc com três dispositivos
(Fonte: Figura baseada em [Johnson 94])
Quando comparadas com outras redes, as redes
ad hoc
apresentam vantagens e
desvantagens, que devem ser consideradas antes mesmo de se adotar este padrão de redes
móveis [Camara 99]. Como vantagens podemos citar:
•
Rápida instalação:
formação de redes temporárias e arbitrárias sem a
necessidade de uma infraestrutura prévia para encaminhar e gerenciar mensagens
pela rede;
•
Tolerância à falhas:
problemas em alguns dos dispositivos podem ser
resolvidos com a reconfiguração dinâmica da rede, o que pode provocar retardos
mais altos, mas a rede continua em um estado operacional;
•
Conectividade:
se dois dispositivos estão dentro do mesmo raio de
alcance de transmissão, eles têm um canal de comunicação direto, diferentemente
do que acontece nas redes infra-estruturadas ou mesmo nas redes fixas;
•
Mobilidade:
em contraposição à restrição de mobilidade em
computadores fixos, ou a falta de comunicação enquanto um dispositivo move-se
em uma região ausente de infraestrutura prévia.
A
B
C
9
As redes móveis
ad hoc
apresentam, basicamente, os mesmos problemas
relacionados a qualquer rede móvel devido a utilização de enlaces sem fio para a
comunicação e a mobilidade dos dispositivos. Como principais desvantagens podemos citar:
•
Banda passante:
os enlaces de comunicação sem fio apresentam bandas
passantes bem menores e limitadas devido a utilização do ar como meio de
transmissão;
•
Erros nos enlaces sem fio:
a taxa de erros em um enlace sem fio é
considerada muito alta, um bit errado para cada 10
5
a 10
6
bits transmitidos;
•
Localização:
para as redes fixas, os dispositivos podem ser localizados
através do endereço IP, que indica implicitamente a localização de cada um deles.
Nas redes ad hoc, localizar um terminal móvel é algo meio complicado, uma vez
que não são disponíveis informações geográficas e o endereço do dispositivo não
tem nenhuma relação com a sua posição;
•
Roteamento:
como nas redes fixas a topologia dificilmente se altera,
não há necessidade de novas rotas serem estabelecidas freqüentemente. Nas redes
ad hoc, os dispositivos movem-se livremente e de forma não-determinística,
havendo a necessidade de um mecanismo de roteamento específico que considere
as características de mobilidade destas redes.
É importante ressaltar que os problemas de largura de banda variável, altas taxas de
erros e localização dos dispositivos móveis são típicos de qualquer ambiente sem fio. Porém,
o problema de roteamento é específico para as redes móveis
ad hoc.
A comunicação entre os
dispositivos móveis em redes infra-estruturadas é responsabilidade das Estações de Rádio
Base que se comunicam através de redes fixas [Smith 01].
Existem diversas razões que tornam o roteamento e a localização de um dispositivo
móvel muito mais difícil em redes móveis do que em redes fixas. Podemos citar como
principais motivos [Amorim 02]:
•
Mobilidade e topologia dinâmica da rede
: os enlaces mudam
freqüentemente de acordo com a mobilidade dos dispositivos móveis, o que
provoca mudanças na topologia da rede;
10
•
Vazão:
uma das principais preocupações em redes
ad hoc
, já que o
espectro é um recurso escasso, principalmente, em se tratando de aplicações
multimídia;
•
Retardo:
requisito importante para praticamente todos os tipos de
aplicações, especialmente aquelas que apresentam uma relação com o tempo, tais
como áudio e vídeo;
•
Inexistência de uma entidade central:
a operação de roteamento em
redes
ad hoc
é mais complexa pela ausência de uma entidade central que coordene
a rede de forma completa;
•
Comunicação através de enlaces sem fio:
pode provocar problemas
relacionados à conectividade, propagação de sinais e baixa velocidade do canal.
2.1 Comunicação em Redes Móveis
Ad hoc
Como já foi comentado anteriormente, a comunicação entre dois dispositivos em uma rede
ad
hoc
nem sempre é direta, podendo ser realizada através de múltiplos saltos, sendo que cada
um destes dispositivos deve prover facilidades de roteamento aos demais. Existem várias
tecnologias que podem ser utilizadas nesta comunicação, entre elas: o padrão IEEE 802.11
[IEEE 99], para redes locais sem fio (WLANs) e a tecnologia
Bluetooth
[Miller 01], que é um
padrão para redes pessoais sem fio (WPANs). A próxima seção apresenta o padrão 802.11
utilizado nas simulações deste trabalho, principalmente por atender aos requisitos de área de
alcance e taxa de transmissão dos cenários de redes móveis definidos.
2.1.1 Padrão IEEE 802.11
O padrão 802.11 [IEEE 99] foi desenvolvido pelo IEEE com o objetivo de definir um nível
físico para redes locais que utilizam como tecnologia de transmissão freqüências de radio ou
infravermelho, e um protocolo de controle de acesso ao meio.
O padrão utiliza uma banda de freqüência não licenciada para a comunicação, também
denominada 2.4 GHz ou ISM (
Industrial, Scientific and Medical
). As taxas de transmissão
iniciais eram de 1 Mbps e 2 Mbps. Mas, com o avanço da tecnologia, estas taxas aumentaram
11
para 5.5 Mbps e 11 Mbps na especificação 802.11b [IEEE 99b] e, futuramente, para 54 Mbps
na especificação 802.11a [IEEE 99a], sendo que esta última opera na faixa de 5 GHz.
O padrão 802.11 implementa dois modelos de arquitetura para as redes móveis:
infra-
estruturado
e
ad hoc
. O modelo infra-estruturado permite a comunicação dos dispositivos
móveis com uma rede fixa. A área de cobertura é dividida em regiões menores denominadas
células. Um grupo de dispositivos que se comunicam em uma célula constitui um BSS (
Basic
Service Set
). O tamanho das células depende da potência de transmissão e recepção dos
dispositivos, sendo que para a construção de redes maiores, múltiplos BSSs são interligados
através de um sistema de distribuição. Um elemento importante que permite a comunicação
entre os dispositivos dentro de uma célula, ou mesmo entre BSSs diferentes é o ponto de
acesso. A interligação de vários BSSs forma um ESS (
Extended Service Set
). A Figura 2.2
apresenta o modelo de arquitetura infra-estruturado para redes 802.11.
Figura 2.2 – Modelo de Arquitetura Infra-Estruturado para Redes 802.11
O modelo de arquitetura
ad hoc
, adotado nas simulações realizadas para este trabalho,
consiste em dispositivos móveis dentro de um mesmo BSS que se comunicam diretamente. A
Figura 2.3 apresenta o modelo de arquitetura
ad hoc
.
Figura 2.3 – Modelo de Arquitetura Ad hoc para Redes 802.11
BSS-1
BSS-2
PA
-
1
PA
-
2
BSS
-
1
BSS
-
2
Sistema de Distribuição
ESS
PA
-
1
PA
-
2
BSS
-
1
BSS
-
2
Sistema de Distribuição
ESS
12
A camada física do 802.11 é definida em três técnicas de acesso diferentes, são elas:
espalhamento de espectro por salto de freqüência (FHSS –
Frequence Hopping Spread
Spectrum
), espalhamento de espectro por seqüência direta (DHSS –
Direct Sequence Spread
Spectrum
) e infravermelho, sendo que todas elas utilizam o sinal CCA (
Clear Channel
Assessment
) para identificar se o meio está livre ou não.
O DSSS é uma técnica de espalhamento de espectro, onde cada bit de dado é
representado por múltiplos bits no sinal transmitido. Os dados são diretamente multiplicados
por uma seqüência pseudo-randômica (também denominada chips) de alta taxa, resultando no
sinal a ser transmitido. Este sinal é enviado somente após a aplicação da modulação PSK
(
Phase Shift Keying
), sendo que a técnica de modulação por chaveamento de fase não
necessariamente é a mesma para todas as taxas de transmissão. O 802.11 define um
“
chipping
” de 11 bits, chamado de “
Barker Sequence
”, para codificar toda a informação a ser
transmitida, ou seja, cada seqüência de 11 bits representa um simples bit do dado (0 ou 1).
Diferentemente do DSSS, o FHSS é uma técnica de espalhamento que divide a banda
passante disponível em subcanais de pequena largura e faz com que o transmissor e o receptor
saltem para um outro subcanal após ter estado, durante um determinado tempo, em um deles.
Cada um destes subcanais em uso são alterados de acordo com um código (seqüência)
pseudo-randômico, sendo que o transmissor e o receptor devem estar sincronizados com
relação ao padrão de saltos. O acesso básico desta banda utiliza uma modulação gaussiana por
chaveamento de freqüência (GFSK –
Gaussian Frequence Shift Keying
)
Já a especificação do infravermelho usa comprimentos de onda de 850 a 950 nm. O
infravermelho foi projetado para áreas internas. Os dispositivos recebem os dados por
transmissões refletidas ou em linhas de visada. Opera com transmissões cujo alcance máximo
é de 10 metros aproximadamente (ou 20 metros na ausência de interferências).
A camada MAC do 802.11 define um novo protocolo de controle de acesso ao meio, o
DFWMAC (
Distributed Foundation Wireless MAC
), que suporta dois métodos de acesso, um
obrigatório e baseado no controle distribuído e o outro centralizado, baseado em consultas
realizadas por pontos de acesso aos dispositivos móveis, dando-lhes a permissão de
transmissão e recepção dos quadros. Estes dois métodos podem coexistir, sendo o distribuído
a base para o método centralizado [Soares 95].
O método de acesso básico do DFWMAC é uma função de coordenação distribuída
(DCF –
Distributed Coordination Function
) também conhecida como CSMA/CA com
13
reconhecimento. Este mecanismo requer que cada dispositivo fique escutando a transmissão
dos outros usuários. Se o canal está livre, o dispositivo deve aguardar um período de tempo
em silêncio, para então transmitir. Caso contrário, o dispositivo deve esperar que a
transmissão do outro dispositivo finalize, mais o tempo que o receptor envie o
reconhecimento, além de um novo período de silêncio. O DFWMAC adiciona ao método
CSMA/CA com reconhecimento, um mecanismo opcional que envolve a troca de quadros de
controle RTS (
Request to Send
) / CTS (
Clear to Send
) antes mesmo da transmissão dos
quadros de dados.
O tempo de acesso para um dispositivo acessar o meio depende dos níveis de
prioridade definidos pelo DFWMAC. Para o controle distribuído são utilizados dois níveis de
prioridade: o
Short Inter-Frame Spacing
(SIFS),
que representa o espaço entre quadros
menores, sendo portanto o menor tempo de espera para acesso ao meio (maior prioridade); e o
DCF Inter-Frame Spacing
(DIFS), que representa o espaço entre os quadros da DCF, sendo
este parâmetro o que denota o maior tempo de espera e, portanto, a menor prioridade de
acesso ao meio.
Figura 2.4 – Método de Acesso do DFWMAC Distribuído
(Fonte: Figura baseada em [Soares 95])
O mecanismo de controle de acesso distribuído (DCF) está ilustrado na Figura 2.4.
Nesta figura, podemos observar que um dispositivo (A) com quadros para transmitir, deve
primeiro escutar o meio livre por um período de silêncio mínimo (DIFS), antes mesmo de
utilizá-lo. Quando este dispositivo ganha a posse do meio, ao invés de enviar imediatamente o
quadro de dados, transmite um quadro de controle RTS, que carrega uma estimativa de
receptor (B)
transmissor (A)
DIFS
RTS
SIFS
CTS
SIFS
Dados
SIFS
Ack
DIFS
NAV (RTS)
NAV (CTS)
Outros dispositivos
(C e D)
14
duração no tempo da futura transmissão de quadros. O dispositivo receptor (B), em resposta
ao quadro RTS, envia um quadro de controle CTS (que também armazena o tempo da futura
transmissão) avisando que está pronto para receber os dados. Só então o transmissor envia os
dados, que é respondido com um reconhecimento (Ack) enviado pelo receptor.
O tempo SIFS é utilizado para a transmissão de quadros carregando respostas
imediatas (CTS e Ack) como mostra a Figura 2.4. Se os pacotes de controle RTS e CTS não
sofrem nenhuma colisão, todos os outros dispositivos que estão dentro da região de
transmissão, tanto do dispositivo transmissor quanto do destino, armazenam informações
sobre a duração da transmissão subseqüente.
Nos sistemas de rádio baseados em detecção do meio, pode ocorrer um fenômeno
conhecido como problema do “terminal escondido”. Este problema aparece quando uma
estação pode receber quadros de duas ou mais estações, mas estes terminais não estão dentro
do mesmo raio de alcance de transmissão. Neste caso, um transmissor pode “ouvir” o meio e
concluir erroneamente que não há nenhuma transmissão. No entanto, outra estação está
transmitindo e isto pode gerar colisões no terminal receptor. A Figura 2.5 mostra uma
situação onde existe a possibilidade de colisões no receptor provocadas pelo problema do
“terminal escondido”. As estações
A
e
C
estão dentro da mesma área de alcance do destino
B,
porém não recebem sinais uma da outra. O problema surge quando
A
e
C
enviam quadros
simultaneamente para
B
, provocando colisões de quadros neste destino
.
Figura 2.5 – Problema do Terminal Escondido
(Fonte: Figura baseada em [Amorim 02])
Para solucionar este problema, pode ser utilizado o esquema de troca de dados de
controle RTS e CTS da camada MAC. Quando um dispositivo origem envia um quadro RTS
e recebe a confirmação de reserva do canal para transmissão através de um quadro CTS do
destino, todos os dispositivos dentro do raio de alcance tanto do transmissor quanto do
B
A
C
15
receptor “escutam” estes quadros de controle. Considerando que tais quadros armazenam
informações sobre a duração da transmissão subseqüente, a camada MAC de cada um dos
dispositivos que recebe estes quadros sabe quando uma transmissão termina. Assim, as
tentativas de transmissão ficam para depois do intervalo de tempo alocado. Estes valores que
correspondem ao tempo de transmissão de outros terminais são armazenados em cada
dispositivo através de tabelas denominadas NAV (
Net Allocation Vector
). Este mecanismo é
conhecido como
Virtual Carrier Sense
. A Figura 2.4 apresenta este comportamento para os
dispositivos
C
e
D
.
O método de acesso distribuído do DFWMAC não garante que um dispositivo consiga
acessar o meio. Para oferecer um serviço determinístico, o padrão suporta opcionalmente um
método centralizado, baseado na função de coordenação pontual (PCF –
Pontual
Coordination Function
) centralizada. Utilizando o PCF, um ponto de acesso controla o acesso
ao meio determinando, a cada momento, qual dispositivo deve transmitir. As redes
ad hoc
não
utilizam esta função, devido à ausência de um ponto de acesso. Por este motivo, o método
centralizado não será descrito neste trabalho, podendo ser encontrado em [Soares 95].
16
Capítulo 3
Protocolos de Roteamento
Ad hoc
A combinação da comunicação sem fio e da mobilidade introduziu restrições inexistentes nos
ambientes de redes tradicionais. Um dos principais desafios para as redes móveis
ad hoc
é
determinar, de forma rápida, rotas válidas e eficientes entre pares de dispositivos, uma vez
que a mobilidade provoca mudanças freqüentes na topologia da rede [Johnson 94, Corson 99].
Se existe a necessidade de adoção de um protocolo de roteamento em redes
ad hoc
, por que
não utilizar os protocolos de roteamento convencionais, já testados e adotados para vários
ambientes de redes fixas? O principal motivo é que estes protocolos foram projetados para
topologias estáticas e podem não convergir rapidamente quando houver a necessidade de se
estabelecer rotas entre pares de dispositivos que se movimentam continuamente.
Os protocolos de roteamento convencionais são baseados nos algoritmos de
Vetor de
Distância
e
Estado de Enlace
[Tanembaum 03], que podem até ser utilizados em redes
ad hoc
com baixo nível de mobilidade dos dispositivos (ou seja, onde a topologia não muda
freqüentemente). Estes protocolos utilizam tabelas para armazenar informações de roteamento
entre os vários pares de dispositivos da rede. Para manter estas informações atualizadas,
mensagens de roteamento são propagadas, periodicamente e em
broadcast
, entre os
dispositivos e os seus vizinhos (aqueles que estão em sua área de alcance). Porém, estas
abordagens apresentam problemas quando adotadas em redes
ad hoc
[Johnson 94]:
•
As mensagens de atualização periódicas provocam um aumento na utilização da
largura de banda da rede e no consumo de energia dos dispositivos, que são
recursos escassos em ambientes de redes móveis;
17
•
A transmissão entre dois dispositivos em uma rede de comunicação sem fio não
trabalha necessariamente bem em ambas direções, pois antenas com alcances de
transmissão diferentes podem ser utilizadas;
•
A propagação de informações de roteamento, que depende do número de
dispositivos existentes, pode provocar uma sobrecarga na rede à medida que
aumenta o número de dispositivos, diminuindo, assim, a escalabilidade.
Uma vez que os protocolos de roteamento convencionais não atendem às exigências
das redes
ad hoc
, é imprescindível a adoção de protocolos de roteamento específicos para
estas redes. Corson [Corson 99] descreve as características desejáveis para tais protocolos,
entre elas:
•
Operar de forma distribuída, ou seja, não ser dependente de nenhum ponto de
acesso fixo e central;
•
Garantir que as rotas estabelecidas sejam livres de
loops
;
•
Adoção de múltiplas rotas, para evitar que os pacotes não sejam entregues por
ausência de rotas;
•
Suportar conexões unidirecionais e modos de operação dos dispositivos (
standby
)
que consumam pouca energia das baterias.
Diversas classes de protocolos de roteamento
ad hoc
foram desenvolvidas com o
objetivo de atender os requisitos acima. Porém, a seleção de um determinado protocolo deve
ser acompanhada de um estudo sobre suas principais características. As seções seguintes
descrevem os protocolos adotados neste trabalho, classificando-os de acordo com os critérios
de estabelecimento e manutenção de rotas.
3.1 Classificação dos Protocolos de Roteamento
Ad hoc
Os protocolos de roteamento para redes
ad hoc
podem ser classificados em pró-ativos e
reativos [Royer 99]. Os protocolos pró-ativos tentam manter informações de roteamento
consistentes para todos os dispositivos. Para tal, cada dispositivo móvel periodicamente
propaga informações de roteamento. A principal vantagem desta classe de protocolos é a
disponibilidade imediata de rotas, reduzindo assim o atraso de transmissão inicial dos pacotes.
18
No entanto, a mobilidade pode provocar intervalos consideráveis de perda de conectividade,
que ocorrem enquanto o mecanismo de propagação periódica determina uma nova rota válida.
Além disso, estes protocolos tendem a gerar uma carga elevada de mensagens de roteamento,
fator crítico em um ambiente com restrições de largura de banda. São exemplos de protocolos
pró-ativos o DSDV [Perkins 94], CGSR [Chiang 97] e WRP [Murthy 96].
Por outro lado, os protocolos reativos atuam sob demanda, criando e mantendo rotas
somente quando requisitado por um determinado dispositivo. A principal vantagem desta
classe de protocolos é a otimização do uso de recursos da rede, evitando propagações
desnecessárias de informações de roteamento. Estes protocolos impõem um certo retardo
inicial no roteamento de pacotes para um determinado dispositivo destino, cuja rota não está
disponível e deve ser criada. No entanto, a mobilidade dos usuários provoca apenas pequenos
intervalos de perda de conectividade, pois a abordagem sob demanda rapidamente ativa a
criação de uma nova rota válida. Os protocolos AODV [Perkins 03], DSR [Johnson 04] e
TORA [Park 97] fazem parte desta abordagem reativa.
Considerando que aplicações de videofone para sistemas de monitoramento de vídeo
requerem pequenos retardos na entrega dos pacotes [Mehaoua 99], os protocolos pró-ativos
são considerados menos adequados em função dos retardos iniciais, assim como os retardos
para o estabelecimento de novas rotas após a perda de conectividade, o que acaba provocando
um número maior de descarte de pacotes. Desta forma, a análise comparativa concentra-se em
protocolos reativos, avaliando o AODV e o DSR, que são os mais utilizados dentro desta
classe de protocolos. No entanto, com o objetivo de avaliar o efeito crítico da mobilidade em
protocolos pró-ativos, a análise também inclui o protocolo DSDV.
Os protocolos CGSR e WRP ainda não foram implementados para a ferramenta de
simulação adotada neste trabalho (NS-2). Como o objetivo deste trabalho é avaliar o
comportamento dos protocolos de roteamento mais utilizados, e não implementar novas
propostas para estes protocolos, o CGSR e WRP não foram considerados no conjunto de
simulações adotado para esta pesquisa. Algumas simulações foram realizadas para o TORA,
no entanto, este protocolo apresenta comportamento inadequado para aplicações de
videofone. Nos cenários menores, com níveis de mobilidade baixos e apenas uma única
sessão de videofone, o TORA provoca uma perda de pacotes diferenciada nos dois sentidos da
comunicação bidirecional.
19
3.1.1 DESTINATION SEQUENCED DISTANCE VECTOR (DSDV)
O DSDV [Perkins 94] é um protocolo de roteamento pró-ativo baseado no clássico algoritmo
de Vetor de Distância, que permite a cada dispositivo móvel armazenar tabelas de roteamento
com informações sobre todos os dispositivos que constituem a rede.
As entradas na tabela de roteamento representam os destinos na rede. Os atributos
para cada destino são o próximo dispositivo usado para alcançá-lo (próximo salto), a métrica
utilizada (normalmente a quantidade de dispositivos intermediários) e o número de seqüência
que é estabelecido pelo destino. O número de seqüência ordena as informações de roteamento,
evitando o problema de formação de
loops
provocados pelos protocolos baseados em
algoritmos de roteamento Vetor de Distância, quando utilizados em redes móveis
ad hoc
.
Para manter a consistência destas tabelas, os dispositivos transmitem suas
informações de roteamento (tabelas) aos seus vizinhos imediatos (
broadcast
), de forma
periódica ou quando alguma mudança é detectada na topologia da rede. Estas atualizações
asseguram que qualquer dispositivo móvel possa localizar um outro dentro da rede. Os dados
difundidos por cada dispositivo contêm seu novo número de seqüência, o endereço do destino,
o número de saltos requerido para alcançar o destino e o número de seqüência original da
informação que foi criado e enviado pelo destino.
Ao receber um pacote de atualização, cada dispositivo compara-o com as informações
armazenadas em sua tabela. Rotas com números de seqüência mais antigos são consideradas
desatualizadas, sendo portanto, descartadas. Em caso de rotas com números de seqüência
iguais, aquela com a menor métrica é utilizada. Este valor é incrementado em um, uma vez
que os pacotes a serem transmitidos necessitam de mais um salto para chegar ao destino. O
número de seqüência da rota também é incrementado (em números pares), permitindo que
cada vizinho a reconheça como atualizada. Após atualizar sua tabela de roteamento, o
dispositivo propaga novas mensagens de atualização. Este processo se repete até que todos os
dispositivos tenham recebido uma cópia deste pacote.
Um dos problemas provocados pela mobilidade dos dispositivos em redes móveis é a
ruptura nos enlaces. Uma rota inválida pode ser detectada pelo hardware de comunicação ou
mesmo ser inferida se nenhuma mensagem de atualização tem sido recebida do vizinho. O
dispositivo que detecta a ruptura no enlace representa-o pela métrica infinita (
∞
). Qualquer
rota que passe por este enlace é imediatamente marcada com esta métrica infinita e o número
20
de seqüência incrementado em um para cada destino não alcançável. Um novo procedimento
de atualização de rotas é então requerido. As rotas para os destinos que utilizam os enlaces
com falhas somente serão recriadas quando a conectividade for restabelecida, e o dispositivo
destino propagar uma mensagem de atualização com número de seqüência maior.
As mensagens de atualização de rotas provocam um aumento considerável no tráfego
da rede. Para reduzir a quantidade de informação nos pacotes de roteamento, evitando a
sobrecarga da rede, este protocolo define dois tipos de pacotes de atualização. O primeiro,
denominado pacote completo (
full dump
) contém toda a informação disponível na tabela de
roteamento. O outro, chamado de pacote com incremento (
incremental dump
), transporta
somente a informação alterada desde o último pacote completo. Este último necessita apenas
de uma única Unidade de Dados do Protocolo de Rede (NPDU –
Network Protocol Data
Unit
), enquanto o pacote completo necessita de várias destas unidades.
Como forma de visualizar o comportamento do DSDV ao serem detectadas mudanças
na topologia da rede, a Figura 3.1 mostra um movimento em uma rede
ad hoc
. As linhas
pretas preenchidas representam os enlaces na topologia inicial da rede. As linhas pontilhadas
e vermelhas descrevem o movimento dos dispositivos.
Figura 3.1 – Movimento em Redes Móveis Ad hoc
(Figura obtida de [Perkins 94] e adaptada para este documento)
A Tabela 3.1 apresenta uma possível estrutura da tabela de roteamento armazenada
pelo dispositivo
D
, representado na Figura 3.1, antes mesmo das mudanças na topologia da
rede, que provoca atualizações nas tabelas de roteamento dos dispositivos.
A
B
C
D
E
F
G
H
A
C
A
B
C
D
E
F
G
H
A
C
21
Tabela 3.1 – Tabela de roteamento do dispositivo D
Destino
Próximo
Salto
Métrica
Número de
Seqüência
A
E
3
S420-A
B
B
1
S126-B
C
B
2
S550-C
D
D
0
S168-D
E
E
1
S690-E
F
E
4
S428-F
G
E
2
S592-G
H
E
3
S876-H
Agora, suponha que o dispositivo
A
moveu-se de sua posição inicial para uma outra
posição ao alcance do dispositivo
B
e que este último dispositivo detectou uma falha na
comunicação com
C
. A tabela de roteamento para o dispositivo
D
não será a mesma
representada pela Tabela 3.1 depois das mensagens de atualização serem propagadas. A nova
tabela de
D
está representada na Tabela 3.2 . Convém ressaltar que durante o tempo de
atualização foram recebidos novos números de seqüência.
Tabela 3.2 – Tabela de roteamento do dispositivo D depois das mudanças na topologia da rede
Destino
Próximo Salto
Métrica
Número de Seqüência
A
B
2
S542-A
B
B
1
S212-B
C
B
∞
S551-C
D
D
0
S316-D
E
E
1
S780-E
F
E
4
S596-F
G
E
2
S842-G
H
E
3
S914-H
22
O critério de seleção de rotas atualizadas adotado pelo protocolo DSDV (em relação
ao número de seqüência e ao tamanho da rota) pode provocar problemas de flutuações nas
rotas. Este problema acontece quando um dispositivo recebe uma tabela de atualização com
um número de seqüência e uma métrica (número de saltos) e, logo em seguida, recebe uma
nova tabela de atualização com o mesmo número de seqüência, porém com métrica menor.
Este procedimento pode provocar uma rajada de novas atualizações de rotas, uma vez que
estas atualizações são transmitidas para os dispositivos vizinhos.
A solução para este problema está no atraso da divulgação destas rotas até a chegada
da melhor rota. Enquanto isso, a rota pode ser disponibilizada para uso, mas não deve ser
propagada imediatamente, a menos que seja uma rota para um destino que estava fora do
alcance anteriormente. Assim, os dispositivos devem manter duas tabelas de roteamento, uma
responsável em repassar os pacotes quando necessário e a outra para a propagação dos
pacotes de incremento.
Os dispositivos determinam a probabilidade de chegadas das rotas com métricas
melhores através da manutenção de um histórico dos tempos médios para um determinado
destino. Este tempo é calculado a partir da chegada da primeira atualização e continua até que
a rota com melhor métrica seja recebida.
Apesar da vantagem de fornecer rotas livres de
loops
a qualquer momento, o
protocolo DSDV apresenta algumas desvantagens devido a sua abordagem pró-ativa, o que o
torna um protocolo não escalável:
•
Pela sua característica de propagar informações de roteamento periódicas, o
DSDV necessita de um tempo de convergência antes mesmo que uma rota possa
ser utilizada. Este tempo representa uma grande perda na taxa de entrega de
pacotes até que uma nova rota seja estabelecida;
•
A necessidade de largura de banda e o tamanho das tabelas aumenta com a
mobilidade e o número de dispositivos da rede. A quantidade de pacotes de
atualização necessária para manter as tabelas é bem maior e esta sobrecarga
diminui o desempenho da rede.
23
3.1.2 AD HOC ON-DEMAND DISTANCE VECTOR (AODV)
O AODV [Perkins 03] é um protocolo de roteamento, também baseado no clássico algoritmo
de Vetor de Distância, para estabelecer e manter rotas ativas em uma rede
ad hoc
. Diferente
do DSDV, adota uma abordagem reativa estabelecendo rotas somente quando requisitadas.
Estas informações são armazenadas, temporariamente, em tabelas de roteamento. Somente as
rotas ativas são mantidas nestas tabelas, diminuindo assim a quantidade de mensagens de
roteamento propagadas na rede, principal problema que limita a escalabilidade do DSDV.
Cada dispositivo móvel armazena uma tabela de roteamento semelhante à do
protocolo DSDV, com o número de seqüência estabelecido pelo destino para cada entrada
desta tabela, como forma de diferenciar as rotas desatualizadas das mais recentes. Como este
protocolo adota uma abordagem reativa, estas entradas são temporárias, e para controlar esta
característica, campos adicionais são armazenados nas tabelas, como o tempo de vida de uma
rota e a lista de vizinhos ativos (dispositivos que utilizam aquela entrada da tabela como uma
rota válida).
O protocolo utiliza diferentes mensagens para descobrir novas rotas e mantê-las. As
mensagens de requisição de rotas (RREQ -
Route Request
) são propagadas pela rede até
alcançar o destino ou algum dispositivo intermediário que tenha uma rota válida para o
destino. Esta solicitação retorna ao dispositivo origem através de uma mensagem de resposta
de rota (RREP –
Route Replay
). Todos os dispositivos devem ser capazes de implementar
estas mensagens. Outros dois tipos de pacotes também são utilizados neste protocolo. As
mensagens
hello
(RREP especial) oferecem informações de conectividade para as rotas ativas
e as mensagens de erros (RERR –
Route Error
) determinam a indisponibilidade de uma rota.
O procedimento de requisição de rotas começa quando um dispositivo deseja enviar
pacotes de dados a um destino para o qual não conhece uma rota, ou a rota disponível não é
válida (tempo de utilização da rota expirou). Este dispositivo propaga para os seus vizinhos
imediatos, em
broadcast
, uma mensagem RREQ com os seguintes campos:
•
O último número de seqüência do destino conhecido pela origem (se for
desconhecido, utiliza zero como padrão), juntamente com seu endereço IP;
•
O número de seqüência da origem (incrementado antes mesmo de propagar esta
mensagem para evitar conflitos com rotas estabelecidas anteriormente) junto ao
seu endereço IP;
24
•
Um contador de dispositivos intermediários com valor 0 (zero), também
conhecido por número de saltos (métrica);
•
Um identificador de requisições, incrementado a cada requisição enviada.
A Figura 3.2 mostra uma situação onde o dispositivo
A
precisa enviar informações
para o dispositivo
G
, mas não tem em sua tabela de roteamento uma rota válida para o
destino. Imediatamente, o dispositivo
A
envia uma mensagem RREQ para os seus vizinhos
imediatos, neste caso, os dispositivos
B
,
C
e
D
, solicitando uma rota válida para
G
.
Figura 3.2 – Procedimento inicial de requisição de rotas para o AODV
Ao receber um pacote RREQ, o dispositivo verifica a identificação desta requisição e
o endereço IP da origem, campos estes que identificam unicamente uma requisição. Caso esta
mensagem já tenha sido processada por este dispositivo, o pacote será descartado. No entanto,
se esta solicitação ainda não tiver sido processada, o dispositivo verifica se é o destino para
aquela requisição. Sendo apenas um simples dispositivo intermediário, consulta a sua tabela a
procura de uma rota válida para o destino, como mostra a Figura 3.3, onde o dispositivo
D
consulta a sua tabela de roteamento e verifica que a rota armazenada para o dispositivo
G
,
além de possuir um número de seqüência menor do que aquele da mensagem RREQ, o tempo
de vida da rota também expirou.
RREQ
RREQ
RREQ
A
B
C
D
E
F
G
Mensagem RREQ
Dispositivo A propaga RREQ para os seus vizinhos imediatos
RREQ
RREQ
RREQ
A
B
C
D
E
F
G
Mensagem RREQ
Dispositivo A propaga RREQ para os seus vizinhos imediatos
264
0
Id
-
Requisi
ç
ão
M
é
trica
S
-
242G
G
N_Seq
Destino
Destino
S
-
256A
A
N_Seq
Origem
Origem
264
0
Id
-
Requisi
ç
ão
M
é
trica
S
-
242G
G
N_Seq
Destino
Destino
S
-
256A
A
N_Seq
Origem
Origem
25
Figura 3.3 – Procedimento de retransmissão de pacotes RREQ para o AODV
Como a informação necessária não foi encontrada, o dispositivo
D
retransmite a
requisição para os seus vizinhos imediatos, incrementando o contador de dispositivos
intermediários e armazenando sua própria identificação ao pacote para a formação do
caminho reverso. O número de retransmissões dos pacotes RREQs entre os dispositivos da
rede é determinado pelo campo TTL (
time-to-life
) do cabeçalho IP. Sempre que retransmite
um pacote de requisição, cada dispositivo intermediário armazena em sua tabela de rotas o
endereço do vizinho pelo qual recebeu a primeira cópia do pacote. Este endereço é utilizado
posteriormente para estabelecer o caminho reverso.
Quando a requisição chega ao dispositivo destino (G), este gera uma mensagem de
resposta de rota para a origem. Esta nova mensagem deve conter os endereços IP da origem e
do destino, assim como os números de seqüência. O destino é o responsável por incrementar o
seu próprio número de seqüência, para ficar maior do que aquele armazenado no pacote
RREQ. Caso esta condição já esteja satisfeita, o número de seqüência não precisa ser
modificado, apenas o contador de dispositivos intermediários é zerado, sendo incrementado a
cada dispositivo que compõe a rota reversa. A Figura 3.4 mostra uma situação onde o
dispositivo
E
propaga a requisição recebida, por não ter informações de roteamento válida até
o destino. Como um de seus vizinhos imediatos é o próprio destino, este gera uma mensagem
RREP e a transmite em
unicast
pela rota reversa até chegar à origem.
RREQ
RREQ
RREQ
A
B
C
D
E
F
G
Dispositivos B, C e D verificam se existe rota válida para dest
ino G em sua tabela
de roteamento e retransmitem a requisição
RREQ
RREQ
0
2
E
S
-
240G
G
...
...
...
...
...
2,48 ms
1
B
S
-
286B
B
2 ms
1
A
S
-
252A
A
Tempo
M
é
trica
Pr
ó
ximo
N_Seq
Destino
Destino
0
2
E
S
-
240G
G
...
...
...
...
...
2,48 ms
1
B
S
-
286B
B
2 ms
1
A
S
-
252A
A
Tempo
M
é
trica
Pr
ó
ximo
N_Seq
Destino
Destino
26
Figura 3.4 – Procedimento de resposta de rotas iniciado pelo destino para o AODV
Procedimento semelhante acontece quando um dispositivo intermediário tem em sua
tabela de rotas uma informação válida para se chegar ao destino (número de seqüência para o
destino em sua tabela de rotas é maior ou igual do que aquele armazenado no RREQ e rota
com tempo de vida não expirado). Como mostra a Figura 3.5, o dispositivo intermediário
E
adiciona à mensagem RREP as informações sobre o destino da sua tabela de roteamento. O
tempo que estabelece o período de ativação da rota é determinado subtraindo o tempo atual
daquele armazenado na tabela deste dispositivo intermediário. Convém ressaltar que cada
dispositivo que participou do caminho da requisição conhece somente as suas informações e
não a rota completa.
Figura 3.5 – Procedimento de resposta de rotas iniciado por um dispositivo intermediário para o AODV
RREP
A
B
C
D
E
F
G
Dispositivo E consulta sua tabela e retransmite RREQ que chega a
o destino G.
Dispositivo G propaga mensagem RREP até chegar a origem através
da rota reversa
RREP
Mensagem RREP (G)
RREP
RREQ
RREQ
RREQ
RREQ
RREQ
RREQ
2,8 ms
1
G
S
-
236G
G
...
...
...
...
...
2,3 ms
3
D
S
-
286B
B
2,5 ms
2
D
S
-
252A
A
Tempo
M
é
trica
Pr
ó
ximo
N_Seq
Destino
Destino
2,8 ms
1
G
S
-
236G
G
...
...
...
...
...
2,3 ms
3
D
S
-
286B
B
2,5 ms
2
D
S
-
252A
A
Tempo
M
é
trica
Pr
ó
ximo
N_Seq
Destino
Destino
3 ms
0
Tempo
M
é
trica
S
-
244G
G
N_Seq
Destino
Destino
S
-
256A
A
N_Seq
Origem
Origem
3 ms
0
Tempo
M
é
trica
S
-
244G
G
N_Seq
Destino
Destino
S
-
256A
A
N_Seq
Origem
Origem
A
B
C
D
E
F
G
Dispositivo E consulta tabela de roteamento e propaga mensagem R
REP com
rota válida para G, através da rota reversa, até chegar na orige
m.
Mensagem RREP (E)
RREP
RREP
2,8 ms
1
G
S
-
242G
G
...
...
...
...
...
2,3 ms
3
D
S
-
286B
B
2,5 ms
2
D
S
-
252A
A
Tempo
M
é
trica
Pr
ó
ximo
N_Seq
Destino
Destino
2,8 ms
1
G
S
-
242G
G
...
...
...
...
...
2,3 ms
3
D
S
-
286B
B
2,5 ms
2
D
S
-
252A
A
Tempo
M
é
trica
Pr
ó
ximo
N_Seq
Destino
Destino
2 ms
1
Tempo
M
é
trica
S
-
242G
G
N_Seq
Destino
Destino
S
-
256A
A
N_Seq
Origem
Origem
2 ms
1
Tempo
M
é
trica
S
-
242G
G
N_Seq
Destino
Destino
S
-
256A
A
N_Seq
Origem
Origem
27
A lista de vizinhos para cada entrada da tabela de roteamento de um dispositivo
armazena os endereços dos seus vizinhos que o utilizam como dispositivo intermediário para
chegar ao destino. Sempre que um dispositivo requisita uma rota para um destino, o endereço
deste dispositivo fica armazenado na lista de vizinhos para a entrada da tabela que representa
aquele destino.
Para manter as rotas ativas funcionando de forma correta , o AODV exige que cada
dispositivo envie mensagens periódicas (pacotes RREP com TTL=1) para a sua lista de
vizinhos ativos. Se durante um intervalo de tempo, o dispositivo não receber mensagens de
conectividade dos seus vizinhos, pode deduzir que a rota está indisponível.
Como os dispositivos estão sempre em movimento, existem duas situações onde há a
necessidade de manutenção de rotas. Se a origem move-se para uma outra posição, este
dispositivo é responsável em reiniciar o procedimento de descoberta de rotas para encontrar
uma nova rota até o destino. Quando um dispositivo intermediário detecta uma rota inválida,
uma mensagem de erro (RERR) é gerada e propagada na rede para os seus vizinhos ativos que
utilizam esta rota até chegar a origem. O número de seqüência do destino é alterado
(incrementado em um) para que os dispositivos possam perceber a falha na comunicação,
assim como o número de saltos é alterado para infinito (
∞
). Dentro da mensagem RERR,
existe um campo onde o número de destinos não alcançáveis pela rota inválida é armazenado.
O AODV, quando comparado a protocolos de abordagem pró-ativa, apresenta uma
redução no número de propagações de mensagens de roteamento, aumentando o desempenho
da rede. Este protocolo apresenta uma única rota para cada destino, o que pode ser
considerado vantagem pela quantidade de mensagens do protocolo propagadas na rede. No
entanto, a ausência de rotas pode provocar um retardo de transmissão maior na entrega dos
pacotes de dados. Comparado a protocolos reativos que adotam mecanismos de roteamento na
origem, o AODV pode apresentar uma carga de roteamento maior devido à forma como as
rotas são estabelecidas. Com um simples ciclo de requisição, os protocolos de roteamento na
origem estabelecem um número maior de rotas do que o AODV, que aprende rotas somente
para os seus vizinhos imediatos e a origem. Um outro problema do AODV é que ele não
trabalha para enlaces unidirecionais. Para prevenir este problema, quando um dispositivo
detecta que a transmissão do seu RREP falhou (através de mensagens de reconhecimento,
RREP – Ack), ele adiciona o próximo salto em sua “lista negra”. Assim, este dispositivo
ignora qualquer RREQ enviado pelos dispositivos que compõem sua lista negra.
28
3.1.3 DYNAMIC SOURCE ROUTING (DSR)
O DSR [Johnson 04] é um protocolo de roteamento com abordagem reativa que permite aos
dispositivos móveis estabelecerem rotas dinâmicas entre quaisquer pares de dispositivos. A
principal característica que o diferencia dos outros protocolos reativos é a adoção do
mecanismo de roteamento na origem. Esta técnica permite que a origem determine por qual
rota os pacotes devem ser transmitidos pela rede, armazenando no cabeçalho de cada um deles
os endereços dos dispositivos que fazem parte desta rota. O DSR ainda considera que a
velocidade dos dispositivos é moderada se comparada com a taxa de transmissão e que o
diâmetro da rede é pequeno.
Diferentemente dos outros protocolos, o DSR não propaga mensagens periódicas para
verificar a conectividade com os seus vizinhos, reduzindo assim a utilização da largura de
banda da rede e da energia da bateria dos dispositivos, principalmente durante os períodos em
que não há mudanças significativas na topologia da rede, ou mesmo quando todas as rotas
necessárias já tenham sido descobertas. Assim, mudanças na topologia da rede que não afetam
as rotas utilizadas são ignoradas e não provocam reações no protocolo.
De acordo com [Maltz 99], o protocolo DSR consiste de dois mecanismos principais
que trabalham em conjunto para permitir a operação em redes móveis
ad hoc
, são eles:
descoberta de rotas
e
manutenção
de rotas
. Cada dispositivo móvel que participa da rede
mantém uma
cache
, onde são armazenadas as rotas aprendidas pelo procedimento de
descoberta de rotas, assim como as rotas ativas que não apresentam rupturas em enlaces.
A partir de um único procedimento de descoberta de rotas, um dispositivo pode
aprender e armazenar em sua
cache
múltiplas rotas para o mesmo destino. Isto permite
reações mais rápidas deste protocolo quando mudanças na topologia da rede, ou mesmo falhas
em enlaces são detectados. Este mecanismo, além de diminuir o retardo de entrega, também
evita a ativação de novos procedimentos de descoberta de rotas, diminuindo assim a carga de
roteamento.
O mecanismo de descoberta de rotas é ativado quando o dispositivo deseja enviar um
pacote e não tem uma rota pré-estabelecida para o destino. Ao receber um pacote das camadas
superiores, o dispositivo inicialmente procura em sua
cache
uma rota válida para o destino.
Com esta informação de roteamento disponível em sua
cache
, o dispositivo acrescenta a rota
ao cabeçalho do pacote e o envia para o primeiro dispositivo indicado na lista, que, por sua
vez, envia para o próximo até que chegue ao destino.
29
A Figura 3.6 mostra um exemplo onde o dispositivo origem
A
não encontra uma rota
válida em sua cache para transmitir pacotes ao destino
G
. Neste caso, o protocolo de
descoberta de rotas é iniciado com o dispositivo
A
propagando, em difusão, um pacote de
requisição de rotas aos seus vizinhos imediatos. Esta requisição contém os endereços da
origem e do destino, um identificador de requisição e um registro de rotas para armazenar os
endereços dos dispositivos intermediários até que o pacote chegue ao destino. Como se pode
observar na Figura 3.6, esta lista é iniciada com o próprio endereço da origem.
Figura 3.6 – Procedimento inicial de requisição de rotas para o DSR
Ao receber um pacote de requisição, o dispositivo executa o seu processamento de
acordo com as seguintes condições:
•
Se o par de atributos <
endereço da origem, identificador de requisição
> para
esta requisição está armazenado na lista de requisições recebidas pelo dispositivo,
significa que o pacote já foi processado, então deve ser descartado;
•
Se o endereço do dispositivo já estiver armazenado no registro de rotas da
requisição, o pacote também deve ser descartado;
•
Se o dispositivo é o destino do pacote, então o registro de rotas no pacote de
requisição contém a rota para se chegar à origem. Um pacote de resposta de rota é
enviado ao dispositivo origem (procedimento semelhante seria realizado se o
dispositivo tem em seu
cache
uma rota para o destino);
Cache (A)
A
B
C
D
E
F
G
Pacote de Requisição (A)
Dispositivo A consulta sua cache e propaga requisição de rotas
para os
seus vizinhos, iniciando o registro de rotas
A
82
Registro Rotas
Id
-
Requisi
ç
ão
G
A
Destino
Origem
A
82
Registro Rotas
Id
-
Requisi
ç
ão
G
A
Destino
Origem
A,D,E
E
...
...
A,B
B
A
A
Rota
Destino
A,D,E
E
...
...
A,B
B
A
A
Rota
Destino
30
•
Não satisfeita nenhuma das condições acima, o dispositivo armazena o seu
endereço no registro de rotas da requisição e retransmite o pacote aos seus
vizinhos imediatos.
Este procedimento se repete até que a requisição alcance o próprio destino ou um
dispositivo intermediário com uma rota válida para o destino. A Figura 3.7 mostra um
exemplo onde o dispositivo
D
recebe a requisição e, como não tem informações de
roteamento válidas para o destino, retransmite o pacote de requisição, armazenando no
registro de rotas sua própria identificação.
Figura 3.7 – Procedimento de retransmissão de pacotes de requisição de rotas para o DSR
Quando a mensagem de requisição chega ao destino, este dispositivo deve armazenar
as novas informações de roteamento para os dispositivos intermediários que fazem parte do
registro de rotas da requisição, e gerar um pacote de resposta de rotas. Esta resposta é enviada
à origem, em
unicast,
utilizando a seqüência armazenada no registro de rotas da requisição. A
rota reversa somente pode ser utilizada em enlaces simétricos. No entanto, se existem enlaces
unidirecionais na rede, o destino deve verificar se em sua
cache
existe uma rota para se chegar
à origem. Caso contrário, o pacote de resposta de rotas deve ser encapsulado (
piggbacking
)
em um pacote de requisição de rotas propagado pelo destino até a origem. Dessa forma,
supondo que não houve falhas na comunicação, os dispositivos aprendem como chegar até a
origem e ao destino, assim como a todos os outros dispositivos que fazem parte da rota (em
virtude do mecanismo de roteamento na origem).
Cache (D)
A
B
C
D
E
F
G
Pacote de Requisição (D)
Dispositivos D e C consultam suas caches e retransmitem o pacote
de
requisição para os seus vizinhos imediatos, armazenando seus end
ereços
no registro de rotas deste pacote
A,D
82
Registro Rotas
Id
-
Requisi
ç
ão
G
A
Destino
Origem
A,D
82
Registro Rotas
Id
-
Requisi
ç
ão
G
A
Destino
Origem
D,E
E
...
...
D,A,B
B
D,A
A
Rota
Destino
D,E
E
...
...
D,A,B
B
D,A
A
Rota
Destino
31
A Figura 3.8 mostra o exemplo de uma rede com enlaces simétricos, onde o destino
G
recebe uma requisição através do dispositivo
E
. As informações de roteamento do registro de
rotas da requisição são armazenadas na cache de
G
(rotas para os dispositivos
E
,
D
e
A
). O
destino
G
é o responsável por propagar o pacote de resposta de rotas para a origem utilizando
o registro de rotas da requisição.
Figura 3.8 – Procedimento de resposta de rotas iniciado pelo destino para o DSR
Figura 3.9 – Procedimento de resposta de rotas iniciado por um dispositivo intermediário para o DSR
Procedimento semelhante acontece quando o dispositivo intermediário tem a
informação de roteamento disponível para o destino. O pacote de resposta de rota é gerado a
partir das informações de roteamento de sua
cache
adicionadas àquelas armazenadas no
A
B
C
D
E
F
G
Pacote de Resposta (G)
Dispositivo G recebe requisição de E, atualiza sua cache e propa
ga
mensagem de resposta de rotas utilizando informações do registro
de rotas
Cache (G)
Requisição de Rotas
Resposta de Rotas
G,E,D,A
G
A
Rota
Destino
Origem
G,E,D,A
G
A
Rota
Destino
Origem
G,E
E
...
...
G,E,D
D
G,E,D,A
A
Rota
Destino
G,E
E
...
...
G,E,D
D
G,E,D,A
A
Rota
Destino
A
B
C
D
E
F
G
Pacote de Resposta (E)
Dispositivo intermediário E consulta sua cache e propaga mensage
m de resposta de
rotas utilizando as informações do registro de rotas mais as inf
ormações de sua cache
Cache (E)
Requisição de Rotas
Resposta de Rotas
G,E,D,A
G
A
Rota
Destino
Origem
G,E,D,A
G
A
Rota
Destino
Origem
E,G
E
...
...
E,D
D
E,D,A
A
Rota
Destino
E,G
E
...
...
E,D
D
E,D,A
A
Rota
Destino
32
registro de rotas da mensagem de requisição. Este pacote é propagado pela rede até que
chegue à origem, assim como mostra a Figura 3.9.
Assim como no AODV, o número de retransmissões das mensagens de requisição de
rota do DSR é limitado utilizando o parâmetro TTL do cabeçalho do pacote IP. Este limite é
decrementado sempre que o pacote passa por um dispositivo e quando chega a zero, a
requisição não pode mais ser retransmitida, ficando a critério da origem retransmitir a
requisição ou inferir que não há como alcançar o destino.
Como a topologia nas redes móveis
ad hoc
é altamente dinâmica, o DSR também
contém um mecanismo para manutenção de rotas. Diferentemente dos outros protocolos de
roteamento, que utilizam mensagens de sinalização periódicas para manter a conectividade
com seus vizinhos e, conseqüentemente, manter as rotas ativas, o DSR não propaga estas
mensagens em nenhuma camada da rede, tendo que adotar um outro mecanismo para a
manutenção de rotas. Ao invés destas mensagens de sinalização, enquanto uma rota está em
uso, cada dispositivo monitora os pacotes de confirmação dos outros dispositivos (pacotes de
reconhecimento da camada MAC) ou mesmo trabalha em modo promíscuo, onde ouve todas
as comunicações que passam por ele. Este tipo de reconhecimento é determinado
reconhecimento passivo. Desta forma, quando um dispositivo detecta falhas na comunicação
com algum dos seus vizinhos, imediatamente remove este enlace de sua
cache
e retorna uma
mensagem de erro para cada dispositivo que tenha enviado um pacote para aquela rota,
utilizando-o como dispositivo intermediário. Ao receberem um pacote de erro, os dispositivos
origem podem usar qualquer outra rota que tenha em seu
cache
, ou mesmo ativar um novo
mecanismo de descoberta de rotas.
Com o objetivo de reduzir a carga dos pacotes, uma vez que este protocolo adota o
mecanismo de roteamento na origem, além de fornecer eficiência nas rotas utilizadas para a
transmissão dos pacotes de dados, diversas otimizações são propostas em [Maltz 99] para as
operações básicas de descoberta de rotas e manutenção de rotas do DSR, entre elas:
•
Salvaging
– dispositivo intermediário utiliza uma rota de seu próprio
cache
quando são encontradas falhas sobre um dos enlaces que compõem a rota
estabelecida pela origem. Se esta rota não existe, o dispositivo descarta o pacote e
retorna uma mensagem de erro para a origem;
•
Gratuitous route repair
– o pacote de erro pode ser encapsulado em um pacote de
requisição de rotas. Este procedimento ajuda na limpeza de
caches
de outros
33
dispositivos da rede que tem o enlace com falhas como parte de uma das rotas
armazenadas;
•
Promiscuos listening
– quando um dispositivo escuta um pacote não endereçado a
ele, checa se este mesmo pacote não poderia ser roteado através de um caminho
mais curto armazenado em sua
cache
.
Uma das vantagens deste protocolo é a utilização da abordagem reativa com
roteamento na origem, o que permite uma economia na largura de banda da rede e na energia
da bateria dos dispositivos, devido à forma como as rotas são aprendidas e a ausência de
mensagens de sinalização periódicas. A utilização do roteamento na origem, por outro lado,
também apresenta problemas, próprios deste mecanismo, na escalabilidade da rede. Outro
ponto negativo é quando as interfaces de rede trabalham em modo promiscuo, ou seja, quando
todas as informações são compartilhadas, mesmo aquelas destinadas a um dispositivo
específico. O modo promíscuo pode gerar problemas de segurança, sendo necessária uma
atenção muito especial neste aspecto.
3.1.5 Comparação entre os Protocolos de Roteamento Ad hoc
Os protocolos de roteamento utilizados nas simulações deste trabalho apresentam
propriedades diferentes, mesmo aqueles que abordam procedimentos semelhantes de
descoberta de rotas até o destino. O objetivo aqui não é apresentar uma comparação exaustiva
destes protocolos, até mesmo por que outros trabalhos [Royer 99] abordam esta análise
teórica. A Tabela 3.3 apresenta as principais características que diferem um protocolo de
outro. Estas características serão utilizadas como justificativa na análise dos resultados das
simulações realizadas.
Como características comuns, os protocolos adotados neste trabalho são distribuídos,
não requerendo um ponto de acesso central para o roteamento das mensagens, cuja
vulnerabilidade poderia provocar sérios riscos ao funcionamento da rede. É possível perceber
que cada protocolo mantém características que os tornam aplicáveis a certos ambientes. Por
exemplo, o protocolo DSR que adota o conceito de múltiplas rotas, pode ser utilizado em
aplicações onde os requisitos de tolerância a falhas são rigorosos. Por outro lado, o DSR não
poderia ser utilizado em rede maiores, com um número de fluxos conversacionais
relativamente alto, devido a sua característica de roteamento na origem.
34
Tabela 3.3 Quadro Comparativo dos Protocolos de Roteamento Ad hoc
DSDV
AODV
DSR
Livre de loops
Sim
Sim
Sim
Roteamento na origem
Não
Não
Sim
Múltiplas rotas
Não
Não
Sim
Utilização de número de
seqüência para as mensagens
Sim
Sim
Não
Modo de operação promíscuo
Não
Não
Sim
Metodologia de
reconfiguração de rotas
Propaga
atualizações
com número
de seqüência
do destino
modificado
Apaga a rota e
notifica a origem,
sendo que este pacote
notifica todos os
vizinhos que utilizam
o enlace com falhas
Apaga a rota
e notifica a
origem
Reativo/Pró-Ativo
Pró-Ativo
Reativo
Reativo
Propagação de mensagens
periódicas
Sim
Sim
Não
Suporte a enlaces
unidirecionais
Não
Não
Sim
Utilização de temporizadores
para as tabelas de roteamento
Não
Sim
Não
35
Capítulo 4
Modelo de Simulação
Os sistemas computacionais, independentemente da área em que estejam sendo
desenvolvidos, necessitam de uma avaliação de desempenho. Esta avaliação permite
identificar, através de um conjunto de índices estatísticos, o comportamento dos sistemas em
termos de eficiência e rendimento (por exemplo, o número de tarefas a serem realizadas e o
tempo de resposta). O objetivo é, a partir de um conjunto de valores ótimos de desempenho,
comparar diferentes propostas de solução até encontrar a que melhor se adequa aos requisitos
definidos para um sistema em específico.
Para avaliar tais sistemas foram desenvolvidos vários métodos que diferem na forma
com que os resultados são obtidos e gerados. Uma destas abordagens consiste em modelar um
determinado sistema, contendo as variáveis de interesse, de forma que este modelo possa
representar as especificações deste sistema. O tratamento do modelo oferecerá diversos
resultados de acordo com as situações desejadas. Para um sistema de redes de computadores,
por exemplo, o retardo, os pacotes perdidos e a vazão média podem ser considerados
variáveis de interesse.
A solução do modelo pode ser desenvolvida através de métodos analíticos ou através
de simulação. O método analítico, ou método algébrico, implica na posse de profundo
conhecimento matemático, mas confere exatidão. Dependendo do modelo matemático, a
resolução torna-se extenuante, o que obriga a simplificações do modelo, o que pode resultar
em imperfeições na representação do sistema. O método por simulação, por outro lado,
permite a confecção de modelos complexos e resolução destes com menor desenvolvimento
matemático. Para isso, emprega-se poder computacional para as iterações numéricas
requeridas implicando, a depender dos resultados desejados, grande consumo computacional.
Várias são as ferramentas de simulação para redes de computadores que permitem a
36
avaliação, comparação, otimização e ajuste de parâmetros, entre elas:
Maryland Routing
Simulator
(MaRS)
[Shankar 94],
Global Mobile Information Systems Simulation Library
(GloMoSim) [GloMoSim 04] e
Network Simulator
(NS) [ISI 05].
Para este trabalho, a ferramenta escolhida foi o
Network Simulator
. O NS é utilizado
em vários ambientes acadêmicos para pesquisas em diversos tipos de redes, sendo, portanto
uma ferramenta completamente aceita para estudos em redes de computadores. O simulador
NS é bastante simples e fácil de entender, estando atualmente bem documentado, o que
facilita a utilização da ferramenta. Um outro ponto é a facilidade na obtenção dos resultados,
onde diversas linguagens de
scripts
podem ser utilizadas. Ainda apresenta uma ferramenta de
animação, que permite a visualização da topologia da rede e do tráfego definido. Por último,
o núcleo do simulador foi desenvolvido em C++, uma linguagem muito conhecida, o que
facilitou a modificação dos códigos originais para que as simulações fossem realizadas com as
alterações necessárias para este trabalho.
4.1 Ambiente de Simulação
Como mencionado, as simulações foram realizadas com a ferramenta
Network Simulator
,
utilizando as extensões fornecidas em [CMU 03] para mobilidade em redes sem fio. A versão
utilizada foi a ns-2.27b, disponibilizada em 2004. As simulações foram executadas em
estações convencionais configuradas com o sistema operacional
Linux RedHat
8.0 e
equipadas com processador de 1.1GHz e memória principal de 128MB.
4.1.1 Network Simulator
O
Network Simulator
(NS) é um simulador de eventos discretos, utilizado no
desenvolvimento de pesquisas em redes de computadores. A ferramenta foi desenvolvida de
forma modular na linguagem orientada a objetos C++. O uso desta linguagem confere
velocidade e praticidade na implementação de protocolos e modificação de classes. A
interface com o usuário, configuração, estabelecimento de parâmetros e manipulação de
objetos e classes é feita em modo texto, através da linguagem interpretada OTcl [Chung 05],
que também é orientada a objetos. OTcl, por ser uma linguagem interpretada, é bem mais
lenta, porém pode ser facilmente alterada. O usuário comum (não o desenvolvedor) utiliza os
37
recursos implementados pela ferramenta através de um script OTcl, onde ele inicia um
escalonador de eventos, configura a topologia da rede e determina as fontes de tráfego.
Para que os usuários possam escrever suas simulações na linguagem interpretada
OTcl, os objetos C++ gerados a partir da compilação do núcleo do NS devem ser
disponibilizados ao interpretador OTcl através de uma ligação OTcl, que cria uma
correspondência do objeto OTcl para cada um dos objetos C++. Esta correspondência também
permite que as funções de controle e as variáveis de configuração especificadas pelo objeto
C++ trabalhem como funções de membros e variáveis de objetos OTcl correspondentes. Desta
forma, os controles de objetos C++ são dados pelo OTcl.
A Figura 4.1 apresenta uma visão simplificada da arquitetura NS. A ferramenta nada
mais é do que um interpretador de
script
Tcl orientado a objeto (OTcl) mais uma biblioteca.
Esta biblioteca contém objetos escalonadores de eventos, objetos de componentes de rede e
módulos de ajuda de configuração de rede. Quando uma simulação é realizada, o NS produz
um ou mais arquivos de texto de saída, que contém dados detalhados da simulação. Os dados
podem ser utilizados para análise de simulações ou como entrada para uma ferramenta de
simulação gráfica chamada
Network Animator
(NAM), que foi desenvolvida como parte do
projeto do NS. O NAM tem uma interface gráfica de usuário bastante amigável e um
controlador de velocidade. As informações produzidas pelo NAM não podem ser utilizadas
para análise de simulações, somente para visualização da topologia da rede.
Figura 4.1 – Arquitetura Geral da Ferramenta NS
(Figura baseada em [Chung 05])
O módulo de extensão para mobilidade em redes sem fio, desenvolvido para a
ferramenta NS, é baseado no modelo de compartilhamento do meio de transmissão. Todos os
Script
OTcl
OTcl
:
Interpretador TCL
com extensões OO
Biblioteca do NS
•
Objetos Escalonadores
de Eventos
•
Objetos Componentes
de Redes
•
Módulos de Ajuda de
Configuração de Redes
Resultados
da Simulação
Análise
NAM
Script
OTcl
OTcl
:
Interpretador TCL
com extensões OO
Biblioteca do NS
•
Objetos Escalonadores
de Eventos
•
Objetos Componentes
de Redes
•
Módulos de Ajuda de
Configuração de Redes
Resultados
da Simulação
Análise
NAMNAM
38
dispositivos móveis possuem uma ou mais interfaces de rede que são conectadas a um canal.
Um canal representa uma freqüência de radio em particular com um esquema de modulação e
codificação diferentes. Estes canais são ortogonais, o que significa que a transmissão e
recepção de pacotes em um canal não interferem em um outro canal. As simulações utilizam
como protocolo de controle de acesso ao meio o IEEE 802.11, baseado no método de acesso
distribuído (DCF – Função de Coordenação Distribuída), apresentado no Capítulo 2.
Os endereços dos pacotes de dados e roteamento enviados pela camada de rede são
mapeados em endereços MAC pelo protocolo ARP. Quando esta informação está disponível,
os pacotes são armazenados em uma fila de transmissão até que a camada MAC possa
transmiti-los. Esta fila de transmissão é baseada em um esquema FIFO (
first-in, first-out)
,
com o tamanho máximo de 50 pacotes. Os pacotes de roteamento têm prioridade mais alta do
que os pacotes de dados para esta fila.
Para a configuração das simulações, além das características descritas acima para
redes sem fio, foram adotados os seguintes parâmetros: transmissão de ondas de rádio com
modelo de propagação
TwoRayGround
(a potência do sinal diminui com o quadrado da
distância percorrida); taxa de transmissão de 11Mbps a uma freqüência de 914MHz; raio de
alcance de 100m; e antenas
omnidirecionais
.
4.2 Caracterização da Aplicação de Vídeo
Desde os primórdios, a comunicação sempre foi uma necessidade da sociedade humana.
Dentre as mais novas e eficientes formas de transmitir e armazenar informações, a
transmissão de vídeo em tempo real vem se apresentando como solução aos sistemas de
monitoramento de vídeo. A justificativa é bem simples, o valor da informação visual é
inquestionável, sem contar que a infraestrutura de redes disponível atualmente e o avanço nas
técnicas de compressão de vídeo digital são os principais fatores que viabilizam o controle e a
vigilância das organizações públicas e privadas através do monitoramento digital.
Os sistemas de monitoramento de vídeo consistem normalmente de câmeras de vídeo
(digitais ou analógicas), com dispositivos opcionais de gravação de áudio, distribuídos em
posições estratégicas no ambiente monitorado. O objetivo é capturar e, posteriormente,
transmitir estas informações através da rede para uma central de monitoramento. Esta central
não necessariamente representa um local fechado, com vários telões que reproduzem os sinais
de vídeo capturados no ambiente. Pode também ser formada por um grupo de homens, que
39
providos de dispositivos móveis circulam constantemente neste ambiente, sendo responsáveis
pela sua vigilância. Estas informações também podem ser compartilhadas com um grupo de
pessoas autorizadas.
Com estas características, podemos afirmar que são inúmeras as áreas de aplicações
que necessitam desta tecnologia de monitoramento. O sistema pode ser implantado em
ambientes como escolas e universidades, bancos e financeiras, aeroportos e rodoviárias, casas
de detenção, instituições governamentais e até mesmo em locais de lazer como áreas
esportivas e
shopping centers
. Todos estes ambientes necessitam de vigilância permanente
que permita identificar situações suspeitas.
Uma das principais exigências para os sistemas de monitoramento é a conectividade
direta entre os seus componentes em toda a área de abrangência do ambiente monitorado.
Sendo assim, não haverá perda de informações provocadas pela ausência de conectividade
entre os dispositivos, informações estas que podem ser muito importantes para avaliar
situações suspeitas. No entanto, existem sérios problemas quando tais sistemas utilizam os
meios de transmissão tradicionais, como cabo metálico ou mesmo fibra óptica. Estes meios
são facilmente danificados pelo clima, pássaros, insetos, acidentes ou mesmo intrusos. Para
resolver estes problemas, os sistemas de monitoramento de vídeo podem utilizar comunicação
sem fio através de ondas de rádio.
O ponto chave neste tipo de comunicação ainda é o método de compressão ou
codificação do sinal de vídeo, que permite um maior número de pessoas utilizarem um
determinado canal. Algumas das técnicas para codificação de sinais de vídeo disponíveis
atualmente podem ser utilizadas nos sistemas de monitoramento de vídeo. Para este trabalho,
foram adotadas sessões de videofone com base no formato de codificação QCIF do padrão
H.263 [ITU-T 98], que define técnicas de codificação a baixas taxas. Este formato de
codificação adota uma definição de imagem de 176x144 pontos e uma taxa de quadros que
varia entre 10 e 15 quadros por segundo, gerando uma taxa média de aproximadamente
28.8Kbps [Miki 97]. Como as taxas adotadas são relativamente baixas, tanto o vídeo como o
áudio apresentam pequenas distorções, mas nada que comprometa o uso da aplicação.
Tipicamente, a codificação gera uma taxa variável de bits. Caso transmitidos
diretamente, estes bits também geram um tráfego com taxa variável. No entanto, existem
técnicas de ajustes dinâmicos de parâmetros específicos da qualidade da codificação que,
auxiliadas por técnicas de gerenciamento de
buffers
, permitem a transmissão a uma taxa
constante. Desta forma, dependendo do tipo de controle sobre a codificação utilizada, uma
40
aplicação de videofone pode gerar um tráfego com taxa variável (VBR –
Variable Bit Rate
)
ou constante (CBR –
Constant Bit Rate
).
Para selecionar o padrão de tráfego a ser adotado, diversas simulações foram
realizadas considerando a taxa de geração constante e variável. No primeiro caso, uma taxa
constante de 28.8Kbps foi adotada. No segundo caso, uma taxa média de 28.8Kbps foi
configurada. Considerando as médias dos parâmetros avaliados, os resultados produzidos por
tais simulações são muito semelhantes, indicando que o padrão de tráfego constante ou
variável tem pouca influência sobre os protocolos de roteamento.
Em resumo, foram realizadas simulações com 1, 2, 4 e 8 sessões de videofone entre
dois, quatro, oito e dezesseis usuários, respectivamente, equipados com dispositivos móveis.
Estes usuários fazem parte do grupo de vigilância que monitoram o ambiente através de
câmeras de vídeo digital acopladas a tais dispositivos. Não foram realizadas simulações que
representam ambientes com câmeras de vídeo fixas em posições estratégicas, transmitindo
informações para dispositivos móveis. O objetivo era considerar o pior caso, quando dois
dispositivos estão em constante movimento, para avaliar o desempenho dos protocolos de
roteamento das redes
ad hoc
. Com os resultados desta avaliação, considerando que estes
protocolos são adequados a ambientes de mobilidade plena, podemos deduzir que os mesmos
também se adequam a situações onde um dos dispositivos está fixo.
Uma outra observação é quanto ao número de sessões de videofone utilizado nas
simulações. Na verdade, não foi definido inicialmente o número máximo de sessões. Os
primeiros cenários foram simulados com somente uma sessão. Como os protocolos de
roteamento atendiam aos requisitos de entrega de uma aplicação de videofone, este valor foi
incrementado até o número máximo de sessões onde os protocolos de roteamento
fornecessem uma taxa de entrega de pacotes de 95% (requisito de uma aplicação de
videofone). Como nos cenários com oito sessões estes resultados já não eram mais
satisfatórios, as simulações foram finalizadas.
Cada sessão de videofone caracteriza-se pela comunicação ponto-a-ponto bidirecional,
onde os dispositivos móveis são configurados para gerar tráfego constante a 28.8Kbps ao
outro participante, utilizando o protocolo UDP como mecanismo de transporte. O protocolo
UDP é configurado para gerar datagramas de 512 bytes a uma taxa aproximada de 7.03
pacotes por segundo. O tempo para cada sessão de videofone muda de acordo com o tamanho
dos cenários, tempo este necessário para que os dispositivos móveis percorram o mesmo
padrão de movimento. Da mesma forma que o tempo de simulação, o número de pacotes
41
enviados também muda de acordo com o tamanho dos cenários, considerando que cada sessão
dura o tempo total da simulação. As próximas seções mostram como estes valores são
calculados.
4.3 Descrição dos Cenários
O cenário simulado permite a mobilidade dos usuários dentro de uma determinada região,
enquanto realizam uma sessão de videofone usando dispositivos móveis. O objetivo da sessão
de videofone neste cenário é permitir o monitoramento do ambiente através de imagens de
vídeo compartilhadas entre os usuários dos dispositivos móveis. Para assegurar a existência de
rotas e manter a conectividade exigida pelos sistemas de monitoramento de vídeo entre
quaisquer dois dispositivos móveis em toda a área de abrangência, um cenário híbrido de
redes
ad hoc
é estabelecido. Neste cenário, uma matriz de pontos de acesso fixos é
configurada. A localização de cada ponto de acesso é calculada levando em consideração o
alcance de todos os seus vizinhos nas direções horizontal e vertical, permitindo a definição de
rotas nestas direções.
Nesta matriz, embora os pontos de acesso possuam uma localização fixa, todos
suportam os protocolos de roteamento
ad hoc
, permitindo a comunicação com qualquer outro
ponto de acesso ou dispositivo móvel dentro da área de alcance. A Figura 4.2 ilustra um
cenário com uma matriz 3x3 de pontos de acesso.
Em todos os cenários, a distância horizontal e vertical entre pontos de acesso é igual
ao raio de alcance de transmissão (R) dos mesmos. O cenário simulado é definido pela região
quadrangular cujos lados podem ser dados aproximadamente pela equação (N-1)R + 2R
(1/2)
1/2
, onde N é o número de dispositivos em uma linha ou coluna da matriz e R é o raio de
alcance de um ponto de acesso. Sendo a distância na diagonal entre pontos de acesso igual a
2
1/2
R, tais dispositivos não se comunicam diretamente. Considerando o cenário 3x3 e um raio
de alcance de 100m, a região do cenário é o quadrado de aproximadamente 340m x 340m.
42
Figura 4.2 – Cenário 3x3
Para cada protocolo avaliado (DSDV, AODV e DSR) diferentes simulações foram
realizadas variando o tamanho dos cenários. Esta variação é determinada pela mudança na
matriz de pontos de acesso e conseqüente região de abrangência. Em todos os cenários, os
pontos de acesso possuem raio de alcance de transmissão de 100m. Os cenários foram
simulados com matriz 3x3, 4x4, 5x5, 6x6, 7x7, 8x8, 9x9 e 10x10, totalizando 9, 16, 25, 36,
49, 64, 81 e 100 pontos de acesso, respectivamente. Desta forma, as regiões de abrangência
destes diversos cenários definem espaços retangulares de 340m x 340m até 1040m x 1040m,
incrementando em 100m a cada cenário.
A escolha destes cenários para as simulações não foi por acaso. Primeiramente, não
seria adequado utilizar redes infra-estruturadas para permitir a comunicação entre os
dispositivos móveis, devido ao seu alto custo de instalação e manutenção. Daí o motivo pela
adoção de redes
ad hoc
, onde os dispositivos provêem facilidades de roteamento aos demais.
Os cenários com matrizes de pontos de acesso fixos asseguram a existência de rotas e mantém
a conectividade desejada entre os dispositivos móveis em toda a área de abrangência, principal
motivação do nosso estudo. Os sistemas de monitoramento de vídeo também se beneficiam da
utilização destes cenários. As câmeras de vídeo acopladas aos dispositivos móveis estão
sempre dentro do raio de alcance destes pontos de acesso permitindo que os sinais de vídeo
sejam transmitidos às centrais de monitoramento (que também podem ser outros dispositivos
móveis).
R
R
(1/2)
1/2
R
(1/2)
1/2
R
(1/2)
1/2
R
R
(1/2)
1/2
R
R
2
1/2
R
43
Estes cenários não são adequados somente a sistemas de monitoramento de vídeo como
aqueles citados anteriormente. Todas as áreas de aplicações associadas aos sistemas de
monitoramento podem adotar como estrutura de rede a proposta deste trabalho. Convém
ressaltar que estes cenários podem ser ampliados, de acordo com a potência do sinal dos
dispositivos
ad hoc
, permitindo a utilização destes cenários em ambientes maiores do que
aqueles definidos neste trabalho.
4.4 Modelo de Mobilidade
O modelo de mobilidade considera que os usuários dos dispositivos móveis deslocam-se a
uma velocidade constante durante todo o tempo, percorrendo randomicamente a região de
abrangência dos pontos de acesso. O comportamento randômico é gerado da seguinte forma.
Inicialmente, cada usuário é colocado em uma localização randômica dentro da região de
abrangência. Em seguida, cada usuário seleciona, de forma randômica, uma nova localização
dentro da região para onde começa a se deslocar. Sempre que um usuário alcança esta
localização, uma outra localização é selecionada, definindo assim um padrão de deslocamento
randômico. Pode-se observar que a seleção randômica de uma nova localização representa a
escolha randômica de uma direção e duração do tempo de deslocamento.
Vale ressaltar que o modelo de mobilidade adotado não é originalmente suportado
pelo ambiente de simulação (ns-2). No modelo original de mobilidade do simulador, a cada
intervalo de 30s, todos os dispositivos móveis selecionam randomicamente novas localizações
e velocidades. Desta forma, os dispositivos que rapidamente alcançam suas localizações ficam
parados, aguardando o término do intervalo para seleção conjunta de novas localizações e
velocidades. Opcionalmente, é possível configurar um tempo de pausa adicional,
representando assim um tempo suplementar que os dispositivos não se movimentam.
A mobilidade adotada não utiliza tempos de pausa e velocidades randômicas, ou seja,
o usuário está sempre se movendo a velocidade constante. Desta forma, uma nova classe de
dispositivo móvel é requerida para modelar a mobilidade adotada. Para tal, a classe original
mobilenode.cc
foi modificada, incluindo um método que calcula o instante em que o
dispositivo chega à nova localização, e em seguida, configura um evento de seleção de nova
localização para este instante do tempo de simulação.
44
Para cada protocolo e cenário avaliado, diferentes simulações foram realizadas
considerando três níveis de mobilidade do usuário: baixa, moderada e alta. Esta variação é
determinada pela adoção de diferentes velocidades para os usuários dos dispositivos móveis.
Na mobilidade baixa, ambos usuários da sessão de videofone deslocam-se a uma velocidade
constante de 1m/s, representando que os mesmos estão caminhando. Na mobilidade alta, estes
usuários movem-se a uma velocidade constante de 20m/s, modelando que os mesmos estão
em um automóvel em movimento. Por fim, na mobilidade moderada, estes usuários deslocam-
se a 1m/s e 20m/s respectivamente.
4.1.1 Definição do Padrão de Movimento para os Dispositivos Móveis
O trabalho desenvolvido por Campos [Campos 05] define o mesmo padrão de movimento
dentro de cada cenário de rede simulado para todos os protocolos de roteamento. Sendo
assim, considerando os oitos cenários de rede e os três níveis de mobilidade, foram gerados 24
padrões de movimentos diferentes. No entanto, os gráficos gerados a partir destas simulações
apresentam pontos de descontinuidade, próprios do movimento randômico adotado. Cada um
dos cenários foi simulado com padrões de movimentos distintos, o que justifica o
comportamento dos protocolos. Alguns destes cenários podem ter gerado movimentos onde
os dispositivos móveis estão na maior parte do tempo próximos um do outro, comunicando-se
através de rotas diretas ou mesmo com um número de dispositivos intermediários pequeno.
Outros podem ter gerado movimentos onde estes mesmos dispositivos móveis estão sempre
muito distantes um do outro. O problema é que estes protocolos não podem ser comparados
para padrões de movimentos completamente diferentes dos dispositivos móveis, pois geram
descontinuidades nos gráficos.
Como estratégia para as novas simulações, o mesmo padrão de movimento foi
considerado para todos os cenários em um mesmo nível de mobilidade, não sendo portanto,
mais baseadas no tempo de simulação. Sendo assim, considerando os 3 níveis de mobilidade
dos dispositivos e as 4 combinações para as sessões de videofone (1, 2, 4 e 8), foram gerados
apenas 12 padrões de movimentos diferentes.
Para atingir o objetivo de gerar o mesmo padrão de movimento dentro de um mesmo
nível de mobilidade dos dispositivos, o cenário 3x3 foi simulado inicialmente com um
movimento completamente randômico, durante 1200 segundos. Esta simulação gerou alguns
arquivos de saída, dentre os quais um arquivo *.nam (
network animator
) onde o movimento
45
destes dispositivos foi observado graficamente para garantir que eles percorressem todo o
cenário durante o tempo de simulação. Um outro arquivo gerado a partir destas simulações
corresponde ao movimento padrão que será utilizado como entrada para a simulação dos
outros cenários dentro deste mesmo nível de mobilidade. A Figura 4.3 mostra um exemplo
deste arquivo, onde a primeira linha indica que no instante
(segundos), o
dispositivo com identificação
, iniciou o movimento para a posição (x,y)
com velocidade igual a m/s
Figura 4.3 – Arquivo de saída que representa o padrão de movimento dos dispositivos móveis
Depois de gerado este arquivo, o desafio agora seria adaptá-lo para os outros cenários
permitindo, dessa forma, que os dispositivos realizassem o mesmo padrão de movimento.
Considerando que os lados da região quadrangular dos cenários simulados são representados
pela equação (N-1)R + 2R (1/2)
1/2
(ver seção 4.3), e que os cenários 3x3 definem o
movimento padrão de todos os outros cenários em um mesmo nível de mobilidade, observou-
se que, para cada cenário, dividindo-se o valor do lado do quadrado do cenário pelo valor
correspondente dos cenários 3x3 (340m), obtém-se um fator que pode ser utilizado
posteriormente na geração dos movimentos dos dispositivos para cada um destes cenários.
Após o cálculo deste fator, o arquivo gerado a partir da simulação dos cenários 3x3 é
modificado de acordo com o cenário a ser simulado. Os campos da Figura 4.3 que
correspondem ao tempo
e a posição final dos dispositivos móveis
são multiplicados por este fator. Sendo assim, o novo arquivo representa o
comportamento de mobilidade dos dispositivos para aquele cenário em específico, baseado no
padrão de movimento definido pelo cenário 3x3.
Considerando o cenário 4x4 como exemplo, onde a região quadrangular possui lados
de 440m, o comportamento de mobilidade dos dispositivos é inicialmente calculado através
$ns at 0.000000 "$node_(9) setdest 217.623004 14.550150 1.000000"
$ns at 0.000000 "$node_(10) setdest 59.433786 144.043290 1.000000"
$ns at 78.452669 "$node_(9) setdest 5.447684 247.287391 1.000000"
$ns at 149.707570 "$node_(10) setdest 165.963283 319.219978 1.000000"
$ns at 354.732949 "$node_(10) setdest 113.308338 334.831332 1.000000"
$ns at 393.389154 "$node_(9) setdest 303.713827 296.018973 1.000000"
$ns at 409.653415 "$node_(10) setdest 243.260160 59.503468 1.000000"
$ns at 695.610032 "$node_(9) setdest 210.768166 189.831228 1.000000"
$ns at 714.108517 "$node_(10) setdest 58.405366 16.680186 1.000000"
$ns at 836.729602 "$node_(9) setdest 67.392753 34.346372 1.000000"
$ns at 903.858692 "$node_(10) setdest 132.023713 24.395731 1.000000"
$ns at 977.880247 "$node_(10) setdest 309.579653 126.906398 1.000000"
$ns at 1048.229127 "$node_(9) setdest 230.535047 203.595754 1.000000"
$ns at 1182.903535 "$node_(10) setdest 237.023170 148.399634 1.000000"
46
do fator resultante da divisão de 440m/340m. Para este exemplo, este fator corresponde a
1,2941. Multiplicando este valor pelos campos que correspondem ao tempo e a posição final
dos dispositivos móveis mostrados no arquivo da Figura 4.3, obtemos o arquivo da Figura 4.4.
Este comportamento de mobilidade é utilizado como entrada na simulação dos cenários 4x4.
Figura 4.4 – Arquivo de entrada utilizado na simulação de um cenário 4x4
Além de modificar o arquivo com o padrão de movimento dos dispositivos móveis,
outros valores também devem ser alterados dentro do arquivo
tcl
para permitir que estes
dispositivos apresentem o mesmo comportamento de mobilidade. Como a partir dos cenários
4x4 o movimento dos dispositivos não é mais randômico, e sim baseado no movimento dos
dispositivos nos cenários 3x3, a posição inicial de cada um deles deve ser definida dentro do
arquivo
tcl.
Esta posição é definida de acordo com a posição inicial dos dispositivos para a
simulação dos cenários 3x3. Da mesma forma que o fator deve ser multiplicado pelos campos
definidos no arquivo da Figura 4.3, as posições iniciais dos dispositivos móveis também
devem ser multiplicadas por este fator e inseridas dentro do
script tcl.
Outro parâmetro que
também deve ser alterado é o tempo de simulação. Como as simulações não são mais
baseadas no tempo, mas no mesmo padrão de movimento dos dispositivos, o tempo em que
estes realizam um movimento dentro de um cenário 3x3 não é o mesmo tempo no qual
realizam este mesmo movimento dentro de um cenário 4x4, por exemplo. Sendo assim, o
tempo de simulação para cada cenário corresponde ao valor que resulta da multiplicação entre
o fator para este cenário e o tempo de simulação dos cenários 3x3, que é de 1200 segundos. O
maior tempo de simulação foi de aproximadamente 3670 segundos para os cenários 10x10. O
Apêndice A mostra exemplos de
scripts tcl
para os cenários 3x3 e 4x4.
Convém ressaltar que, assim como o tempo de simulação muda para cada cenário de
rede, o número de pacotes de dados enviados por cada dispositivo das sessões de videofone
$ns at 0.000000 "$node_(16) setdest 281.629770 18.829606 1.000000"
$ns at 0.000000 "$node_(17) setdest 76.914311 186.408964 1.000000"
$ns at 101.526983 "$node_(16) setdest 7.049944 320.018977 1.000000"
$ns at 193.739208 "$node_(17) setdest 214.776013 413.108207 1.000000"
$ns at 459.066169 "$node_(17) setdest 146.634320 433.311136 1.000000"
$ns at 509.091846 "$node_(16) setdest 393.041423 383.083377 1.000000"
$ns at 530.139714 "$node_(17) setdest 314.807266 77.004488 1.000000"
$ns at 900.201218 "$node_(16) setdest 272.758803 245.663942 1.000000"
$ns at 924.140434 "$node_(17) setdest 75.583415 21.586123 1.000000"
$ns at 1082.826544 "$node_(16) setdest 87.214151 44.448246 1.000000"
$ns at 1169.699484 "$node_(17) setdest 170.854217 31.570946 1.000000"
$ns at 1265.492084 "$node_(17) setdest 400.632492 164.231809 1.000000"
$ns at 1356.531811 "$node_(16) setdest 298.339473 263.476858 1.000000"
$ns at 1530.816339 "$node_(17) setdest 306.735867 192.046585 1.000000"
47
também é modificado de acordo com o tamanho destes cenários, uma vez que estas sessões
têm duração igual ao tempo de simulação. A Tabela 4.1 apresenta os valores utilizados como
parâmetros para as simulações deste trabalho.
Tabela 4.1 – Parâmetros de Simulação
CENÁRIOS
N. PACOTES ENVIADOS
Configuração
Tamanho
Tempo de Simulação
1 sessão
2 sessões
4 sessões
8 sessões
3x3
340m
1200s
16876
33752
67504
135008
4x4
440m
1552s
21840
43680
87360
174720
5x5
540m
1905s
26802
53604
107208
214416
6x6
640m
2258s
31766
63532
127064
254128
7x7
740m
2611s
36728
73456
146912
293824
8x8
840m
2964s
41692
83384
166768
333536
9x9
940m
3317s
46656
93312
186624
373248
10x10
1040m
3670s
51618
103236
206472
412944
4.5 Parâmetros Quantitativos
Os parâmetros quantitativos definem os critérios adotados para avaliação dos protocolos de
roteamento. Estes parâmetros não são automaticamente fornecidos pelo ambiente de
simulação, requerendo assim ferramentas adicionais de tratamento dos dados gerados na
simulação. Algumas ferramentas foram testadas, mas resultados inconsistentes foram obtidos.
Assim, para prover maior confiabilidade nos parâmetros quantitativos, uma ferramenta
específica foi desenvolvida utilizando a linguagem
awk
[Close 95]. Os parâmetros
quantitativos utilizados na análise comparativa são os seguintes:
•
Taxa de Entrega dos Pacotes de Dados:
proporção entre o número de pacotes
recebidos pela camada de aplicação CBR do destino e o número de pacotes
gerados por esta camada no dispositivo origem. Para manter uma boa qualidade da
imagem, uma aplicação de videofone requer taxas de entrega de pacotes da ordem
de 95% [Cherriman 96, Chen 02]. Dentro deste parâmetro, outros requisitos, tais
48
como o número de pacotes seqüenciais que foram perdidos e o número de pacotes
que foi entregue com um retardo maior do que 400ms são considerados.
• Retardo de Entrega:
intervalo de tempo médio decorrido entre a geração dos
pacotes na origem e a entrega destes pacotes no destino. Este retardo inclui todos
os possíveis atrasos: espera na fila de transmissão, propagação do pacote e
retransmissões MAC. A espera na fila pode ser ocasionada por congestionamento
na rede ou inexistência de rota. O retardo de entrega máximo para aplicações de
videofone é de 400ms [Mehaoua 99].
• Distribuição do Retardo:
o retardo de entrega máximo aceito para aplicações de
videofone (400ms) foi dividido em intervalos de 50 ms e dentro destes intervalos
foi considerada a probabilidade do número de pacotes de dados entregues para
cada um deles. O objetivo é analisar a probabilidade destes pacotes chegarem em
intervalos de tempo cada vez menores, uma vez que quanto menor for este
retardo, melhor a qualidade do áudio e vídeo apresentados no receptor.
• Variação do Retardo (Jitter):
o efeito
jitter
corresponde à variação entre os
tempos de chegada dos pacotes no destino provocados pela rede. Este parâmetro é
muito importante para aplicações com áudio e vídeo, como as aplicações de
videofone, que aceitam um
jitter
de até 130ms [Mehaoua 99, Wong 00]. Assim
como o retardo máximo de entrega, a variação do retardo influencia muito na
apresentação destas informações ao receptor.
• Carga de Roteamento:
relação entre o número de mensagens de roteamento
geradas pelos protocolos de roteamento e o número de pacotes de dados CBR
recebidos pelos destinos, sendo que cada retransmissão é considerada no cálculo
do número de mensagens de roteamento.
Os quatro primeiros parâmetros são importantes para avaliar as condições de tráfego
da rede para aplicações de videofone. A carga de roteamento determina a eficiência do
protocolo de roteamento em encontrar rotas para o destino. Na verdade, estes resultados não
são independentes. Se a taxa de entrega dos pacotes de dados for muito pequena, isto significa
que o protocolo de roteamento não se adapta às mudanças na rede. E se o retardo de entrega
for muito alto, o protocolo de roteamento não converge rapidamente às estas mudanças. O
Apêndice A mostra um dos arquivos de
script awk
utilizado para gerar os resultados.
49
Capítulo 5
Análise dos Resultados
Este capítulo apresenta uma análise dos resultados das simulações realizadas, com base nos
parâmetros quantitativos:
taxa de entrega, retardo de entrega, distribuição do retardo, jitter
e
carga de roteamento.
Nesta análise, os requisitos de uma aplicação de videofone são
considerados para cada um destes parâmetros. Os resultados correspondem a simulações que
possuem diferentes tamanhos dos cenários híbridos
ad hoc
, níveis de mobilidade dos
dispositivos e número de sessões de videofone entre estes dispositivos.
Os resultados obtidos destas simulações podem ser representados através de diversos
gráficos. São três os modelos de gráficos que podem ser gerados. O primeiro corresponde aos
resultados dos diferentes níveis de mobilidade dos dispositivos, para um mesmo protocolo de
roteamento e uma mesma sessão de videofone. O segundo representa os resultados dos
diversos números de sessões de videofone estabelecidas entre os dispositivos, para um mesmo
protocolo de roteamento e um mesmo nível de mobilidade de tais dispositivos. O terceiro, e
último, mostra os resultados dos diferentes protocolos de roteamento, para uma mesma sessão
de videofone e um mesmo nível de mobilidade.
Considerando todos os parâmetros quantitativos definidos para este trabalho, pode-se
observar que o número de gráficos gerados é bastante elevado. Com o objetivo de não
sobrecarregar o capítulo com gráficos que, na maioria das vezes, apresentam comportamentos
semelhantes, este capítulo apresenta um número reduzido destes gráficos que mostram o
comportamento dos protocolos de roteamento
ad hoc
para aplicações de videofone. No
entanto, todos os outros gráficos estão disponíveis no Apêndice deste trabalho para consulta.
Novamente, para não sobrecarregar o trabalho com um número elevado de gráficos, este
Apêndice foi anexado ao trabalho no formato digital (cd-rom).
50
Como estratégia, dentre os gráficos apresentados neste capítulo, aqueles que
representam o comportamento dos diferentes protocolos de roteamento são mostrados em
maior quantidade, considerando que o objetivo do trabalho é avaliar o desempenho destes
protocolos para aplicações de videofone em redes móveis
ad hoc
. Estes gráficos mostram tais
resultados para os cenários com uma única sessão de videofone e cenários com oito sessões de
videofone, pois nos cenários com duas e quatro sessões, os protocolos apresentam
comportamentos semelhantes àqueles com uma sessão. A escolha destes cenários não foi por
acaso. Os cenários com uma sessão mostram o comportamento dos três protocolos de
roteamento
ad hoc
avaliados. Já nos cenários com oito sessões, os protocolos de roteamento
não atendiam mais aos requisitos de uma aplicação de videofone, condição esta de parada
para o conjunto de simulações deste trabalho.
5.1 Taxa de Entrega
O parâmetro taxa de entrega foi analisado de acordo com o retardo de entrega dos pacotes de
dados para aplicações de videofone. Considerando que esta classe de aplicação define um
retardo de entrega de 400ms [Mehaoua 99], somente os pacotes entregues neste intervalo
foram considerados para as avaliações.
Para manter uma boa qualidade da imagem, uma aplicação de videofone requer taxas
de entrega de pacotes da ordem de 95% [Cherriman 96, Chen 02]. Este parâmetro foi utilizado
como condição de parada para o conjunto de simulações deste trabalho. À medida que um
protocolo de roteamento não atendesse às exigências de taxa de entrega desta classe de
aplicação, este protocolo não seria mais simulado para os cenários subseqüentes. Dessa forma,
as simulações foram finalizadas quando nenhum dos protocolos já não mais atendia a este
requisito.
Em praticamente todos os cenários, o número de sessões de videofone exerce pouca
influência sobre a taxa de entrega dos pacotes de dados, exceto para os cenários de
mobilidade alta com 8 sessões, como mostram as Figuras 5.1 e 5.2. Nestes cenários, os
protocolos de roteamento não apresentam comportamentos estáveis, com taxas de entrega
inferiores a 95%. Como se pode perceber em tais gráficos, o protocolo DSDV não foi inserido
em nenhum deles. A justificativa é bastante simples. Este protocolo apresenta taxas de entrega
muito baixas já nos cenários com uma única sessão de videofone. Portanto, não foi simulado
para os cenários com 2, 4 e 8 sessões.
51
Protocolo AODV
(
Mobilidade Alta
)
70
75
80
85
90
95
100
Cenários
Taxa de Entrega
1 sessão
96,439
96,300
96,709
96,921
97,168
97,376
97,321
97,460
2 sessões
96,175
96,399
96,545
96,917
96,635
96,950
97,083
97,290
4 sessões
95,901
95,615
95,738
95,815
96,018
96,228
96,382
96,475
8 sessões
94,092
92,298
92,463
92,248
91,736
90,056
89,976
87,287
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.1 – Taxa de entrega dos pacotes de dados por sessão de videofone para o AODV
em cenários de mobilidade alta
Protocolo DSR
(
Mobilidade Alta
)
70
75
80
85
90
95
100
Cenários
Taxa de Entrega
1 sessão
99,964
99,789
99,713
99,314
98,876
98,700
98,007
97,299
2 sessões
99,822
99,551
99,541
99,246
98,935
98,472
98,170
97,437
4 sessões
99,407
99,072
98,867
98,553
98,354
98,069
97,794
97,338
8 sessões
92,971
88,884
87,057
86,373
88,545
91,732
91,555
91,561
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.2 – Taxa de entrega dos pacotes de dados por sessão de videofone para o DSR
em cenários de mobilidade alta
O nível de mobilidade dos dispositivos exerce maior influência sobre a taxa de entrega
dos pacotes de dados do que o número de sessões de videofone, principalmente para o
protocolo DSDV (devido a sua abordagem pró-ativa) e os cenários de mobilidade alta com 8
sessões. A justificativa para este comportamento é bastante intuitiva. Quanto maior o nível de
mobilidade dos dispositivos, maior a possibilidade de perda de conectividade, e maior a
probabilidade de perda de pacotes pela ausência de rotas. As Figuras 5.3, 5.4 e 5.5 mostram
claramente estes resultados. O protocolo DSDV, como justificado anteriormente, foi simulado
somente para os cenários com uma única sessão de videofone.
52
Protocolo DSDV
(1 sessão de videofone)
0
10
20
30
40
50
60
70
80
90
100
Cenários
Taxa de Entrega
Baixa
79,93
86,21
82,37
85,68
83,94
84,36
87,71
87,72
Moderada
35,36
35,97
32,59
35,98
40,02
42,22
43,40
42,99
Alta
26,17
21,63
20,33
21,56
25,04
25,35
26,51
25,55
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.3 – Taxa de entrega dos pacotes de dados por níveis de mobilidade para o DSDV
em cenários com uma sessão de videofone
Protocolo AODV
(8 sessões de videofone)
50
60
70
80
90
100
Cenários
Taxa de Entrega
Baixa
98,464
98,172
98,245
98,331
98,326
98,534
98,757
98,001
Moderada
96,399473
95,370879
95,177132
95,361393
95,825392
96,009126
96,295493
96,504868
Alta
94,0922
92,2980
92,4628
92,2480
91,7361
90,0560
89,9756
87,2867
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.4 – Taxa de entrega dos pacotes de dados por níveis de mobilidade para o AODV
em cenários com oito sessões de videofone
Protocolo DSR
(8 sessões de videofone)
50
60
70
80
90
100
Cenários
Taxa de Entrega
Baixa
98,464
98,172
98,245
98,331
98,326
98,534
98,757
98,001
Moderada
98,499348
96,985462
96,85238
96,453907
96,843348
96,839022
96,898577
96,841945
Alta
92,9708
88,8839
87,0569
86,3730
88,5445
91,7317
91,5547
91,5606
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.5 – Taxa de entrega dos pacotes de dados por níveis de mobilidade para o DSR
em cenários com oito sessões de videofone
53
Como mostram as Figuras 5.6, 5.7 e 5.8, o protocolo DSDV apresenta as piores taxas
de entrega de pacotes já nos cenários com uma única sessão de videofone. Estes péssimos
resultados, principalmente nos cenários de mobilidade moderada e alta são justificados pelo
comportamento pró-ativo do protocolo. Ou seja, o dispositivo não toma a iniciativa de
requisitar a recriação e o estabelecimento de rotas, aguardando os mecanismos de propagação
indicarem a existência de uma rota válida.
Mobilidade Baixa
(
1 sessão de videofone
)
0
20
40
60
80
100
Cenários
Taxa de Entrega
DSDV
79,930
86,210
82,367
85,679
83,940
84,360
87,710
87,720
AODV
99,700
99,780
99,880
99,850
99,890
99,880
99,870
99,800
DSR
99,970
99,980
99,930
99,920
99,870
99,920
99,740
99,740
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.6 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade baixa
com uma sessão de videofone
Mobilidade Moderada
(
1 sessão de videofone)
0
10
20
30
40
50
60
70
80
90
100
Cenários
Taxa de Entrega
AODV
98,181
98,292
98,108
97,881
98,407
98,296
98,055
98,271
DSDV
35,359
35,971
32,595
35,976
40,019
42,222
43,403
42,985
DSR
99,870
99,867
99,679
99,427
99,006
98,779
98,422
98,256
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.7 - Taxa de entrega dos pacotes de dados nos cenários de mobilidade moderada
com uma sessão de videofone
54
Mobilidade Alta
(1 sessão de videofone)
0
10
20
30
40
50
60
70
80
90
100
Cenários
Taxa de Entrega
AODV
96,439
96,300
96,709
96,921
97,168
97,376
97,321
97,460
DSDV
26,173
21,635
20,327
21,561
25,038
25,353
26,511
25,553
DSR
99,964
99,789
99,713
99,314
98,876
98,700
98,007
97,299
3x3
4x4
5x5
6x6
7x7
8x8
9x9
10x10
Figura 5.8 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade alta
com uma sessão de videofone
Convém ressaltar que, o incremento da mobilidade dos dispositivos torna mais
evidente esta deficiência do protocolo DSDV. Em conseqüência de sua abordagem pró-ativa,
podem acontecer longos períodos sem rotas válidas na tabela de roteamento, quando então os
pacotes são enviados por rotas desatualizadas ou mesmo descartados das filas de transmissão
por falta de espaço nos
buffers
. Embora o DSDV não tenha apresentado um excelente
comportamento nos cenários de baixa mobilidade, como as mudanças topológicas são bem
menores, a taxa de entrega é da ordem de 80%.
Por outro lado, em praticamente todos os cenários, os protocolos AODV e DSR
apresentam as melhores taxas de entrega. Independente do tamanho da rede, do nível de
mobilidade e do número de sessões de videofone, estas taxas são próximas a 100% (ver
Figuras 5.9 e 5.10), e nunca são inferiores a 95%, exceto nos cenários de mobilidade alta com
8 sessões de videofone, como mostra a Figura 5.11. Estes resultados podem ser explicados
pelo comportamento reativo dos protocolos AODV e DSR, e principalmente pela
concentração das atualizações de rotas nas suas extremidades. Ou seja, como ambos
dispositivos móveis geram pacotes, ambos são os primeiros a perceber a perda de
conectividade, reenviando mensagens de requisição para recriação das rotas. No entanto,
como os dispositivos intermediários com rotas válidas podem responder as requisições, os
dispositivos móveis rapidamente recebem respostas de pontos de acesso próximos. Assim, as
rotas são recriadas de forma quase instantânea em ambas as direções, em função da simetria
de rotas adotadas nestes protocolos, e os pacotes não precisam ser descartados das filas de
transmissão por ausência de espaço de armazenamento nos
buffers
.
55
Mobilidade Baixa
(
8 sessões de videofone
)
70
75
80
85
90
95
100
Cenários
Taxa de Entrega
AODV
98,464
98,172
98,245
98,331
98,326
98,534
98,757
98,800
DSR
99,859
99,741
99,764
99,849
99,686
99,865
99,879
99,800
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.9 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade baixa
com oito sessões de videofone
Mobilidade Moderada
(
8 sessões de videofone
)
70
75
80
85
90
95
100
Cenários
Taxa de Entrega
AODV
96,399473
95,370879
95,177132
95,361393
95,825392
96,009126
96,295493
96,504868
DSR
98,499348
96,985462
96,85238
96,453907
96,843348
96,839022
96,898577
96,841945
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.10 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade moderada
com oito sessões de videofone
Mobilidade Alta
(
8 sessões de videofone
)
70
75
80
85
90
95
100
Cenários
Taxa de Entrega
AODV
94,092
92,298
92,463
92,248
91,736
90,056
89,976
87,287
DSR
92,971
88,884
87,057
86,373
88,545
91,732
91,555
91,561
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.11 – Taxa de entrega dos pacotes de dados nos cenários de mobilidade alta
com oito sessões de videofone
56
Como pode ser observado, principalmente nas Figuras 5.7, 5.8, 5.9 e 5.10, o protocolo
DSR apresenta comportamento um pouco melhor do que o AODV em praticamente todos os
cenários. A justificativa para estes resultados é a forma como o DSR aprende novas rotas,
além de sua característica de múltiplas rotas. Um simples ciclo de requisição de rotas permite
o aprendizado de um número maior de rotas por todos os dispositivos que recebem os pacotes
de controle do DSR, uma vez que este protocolo trabalha com o mecanismo de roteamento na
origem. Uma outra vantagem deste protocolo é o modo de operação promíscuo dos
dispositivos móveis, que os permitem “escutar” pacotes de dados que não são endereçados a
eles, aprendendo assim um número maior de rotas sem a necessidade de propagar requisições
na rede. Já o protocolo AODV limita o aprendizado de novas rotas entre os dispositivos e os
seus vizinhos imediatos, além dos dispositivos origem e destino. Sem contar que o AODV
não adota o conceito de múltiplas rotas, roteamento na origem e escuta em modo promíscuo
dos dispositivos móveis.
No entanto, o comportamento do DSR muda de acordo com o tamanho dos cenários,
onde o AODV apresenta comportamento semelhante ou até mesmo um pouco melhor. Estes
resultados já eram esperados, pois de acordo com [Royer 99, Johansson 99], o DSR adapta-
se melhor a cenários com diâmetro de rede pequeno, onde os dispositivos possuem
velocidades moderadas, não sendo portanto, um protocolo muito escalável. Este
comportamento deve-se ao roteamento na origem adotado por este protocolo. Além disso, o
AODV adota o conceito de lista de vizinhos ativos. Quando um dispositivo detecta uma falha
em um enlace ativo, os dispositivos que fazem parte da lista de vizinhos para aquele enlace
recebem uma mensagem de erro notificando a invalidez da rota. No DSR, uma mensagem de
erro é retornada exatamente para o dispositivo que enviou um pacote de dados e encontrou
uma rota inválida. Os dispositivos que não fazem parte da rota deste pacote de dados, mas
utilizam o enlace com falha não são notificados apropriadamente [Perkins 00].
Convém ressaltar que, o número de pacotes de dados que chegam ao destino com um
retardo maior do que 400ms é muito pequeno quando comparados ao número de pacotes que
foi enviado. A Tabela 5.1 mostra estes resultados para os cenários de mobilidade baixa com
uma sessão de videofone (as outras tabelas podem ser encontradas no Apêndice D deste
trabalho).
57
Tabela 5.1. Número de pacotes de dados entregues ao destino com retardo maior do que 400ms
(Mobilidade Baixa – 1 sessão de videofone)
Pacotes
Enviados
Pacotes Recebidos com
Retardo < 400ms
Pacotes Recebidos com
Retardo > 400ms
DSDV
AODV
DSR
DSDV
AODV
DSR
3x3
16876
13489
16826
16872
0
11
0
4x4
21840
18829
21794
21837
0
15
2
5x5
26802
22076
26771
26785
3
0
2
6x6
31766
27217
31720
31743
0
12
5
7x7
36728
30830
36688
36682
0
1
4
8x8
41692
35172
41644
41661
0
0
7
9x9
46656
40922
46596
46537
0
13
11
10x10
51618
45282
51518
51484
2
40
8
No entanto, nos cenários com 8 sessões de videofone e nível de mobilidade alto dos
dispositivos, o que se percebe é exatamente o contrário (ver Tabela 5.2). Na verdade, a
porcentagem de pacotes que chegam com um retardo maior do que 400ms já é considerada
relevante, e por este motivo, a partir destes cenários, os protocolos de roteamento AODV e
DSR são considerados instáveis, com taxas de entrega inferiores a 95%. Estes valores podem
ser justificados pelo número de sessões de videofone e nível de mobilidade dos dispositivos
móveis. Quanto maior o número de sessões de videofone e o nível de mobilidade destes
dispositivos, maior a probabilidade de colisões na rede e maior o número de retransmissões,
conseqüentemente, os pacotes de dados podem demorar muito mais tempo nas filas de
transmissão até chegarem aos dispositivos destinos.
Tabela 5.2 –Número de pacotes de dados entregues ao destino com retardo maior do que 400ms
(Mobilidade Alta - 8 sessões de videofone)
Pacotes
Enviados
Pacotes Recebidos
com Retardo <
400ms
Pacotes Recebidos
com Retardo >
400ms
AODV
DSR
AODV
DSR
3x3
135008
127032
125518
1596
9117
4x4
174720
161263
155298
3570
18326
5x5
214416
198255
186664
4914
25160
6x6
254128
234428
219498
5908
30623
7x7
293824
264606
260165
5750
30021
8x8
333536
305973
187162
6073
14424
9x9
373248
335832
341726
5773
26475
10x10
412944
360445
378094
4864
27910
Uma outra observação sobre a taxa de entrega dos pacotes de dados é que não foram
apresentadas neste trabalho as taxas de entrega mínima e máxima destes pacotes para cada
58
sessão de videofone em particular, mas apenas a taxa média de todas as sessões de videofone.
Os valores para as taxas de entrega mínima e máxima foram observados durante a análise dos
resultados das simulações e verificou-se que os mesmos eram semelhantes. Portanto, não
foram inseridas como mais um parâmetro quantitativo.
5.1.1 Rajadas de Perda dos Pacotes de Dados
Como este trabalho aborda a utilização de aplicações de videofone em redes móveis
ad hoc
,
outro requisito associado à taxa de entrega interessante para a análise é o número de pacotes
de dados que foram perdidos na seqüência (rajadas). Em aplicações de videofone, o ideal é
que estes valores sejam muito baixos para manter uma boa qualidade da imagem a ser
apresentada ao destino.
Os resultados gerados sobre o número de pacotes de dados perdidos na seqüência
foram condensados em tabelas como forma de simplificar o número elevado de informações
obtidas durante todas as simulações. Como exemplo, temos as Tabelas 5.3 e 5.4 que mostram
tais resultados para cenários com mobilidade alta dos dispositivos e uma sessão de videofone.
Para uma melhor compreensão destas tabelas, considere a Tabela 5.3 que mostra os resultados
do protocolo DSDV nos cenários de mobilidade alta com uma única sessão de videofone. De
acordo com esta tabela, o
cenário 3x3
apresenta
1316
rajadas de pacotes perdidos na
seqüência, com tamanhos que variam entre
0
e
200
pacotes,
21
rajadas com tamanhos entre
200
e
400
pacotes e, por fim,
0
rajadas com tamanhos acima de
400
pacotes.
Tabela 5.3 - Distribuição das rajadas de perda de pacotes na seqüência em cenários de mobilidade alta
com 1 sessão de videofone (Protocolo DSDV)
PROTOCOLO PRÓ-ATIVO (DSDV)
0-200
200-400
400-600
600-800
800-1000
Acima de 1000
3x3
1316
21
0
0
0
0
4x4
1383
33
0
1
0
0
5x5
2063
32
6
0
0
0
6x6
3098
34
11
0
0
0
7x7
4046
28
4
2
0
0
8x8
4871
27
4
2
0
0
9x9
5458
22
8
2
1
0
10x10
5911
43
3
3
3
0
59
Tabela 5.4 – Distribuição das rajadas de perda de pacotes na seqüência em cenários de mobilidade alta
com 1 sessão de videofone (Protocolos AODV e DSR)
PROTOCOLOS REATIVOS
0-200
200-400
400-600
600-800
800-1000
Acima de 1000
AODV
DSR
AODV
DSR
AODV
DSR
AODV
DSR
AODV
DSR
AODV
DSR
3x3
334
3
0
0
0
0
0
0
0
0
0
0
4x4
495
21
0
0
0
0
0
0
0
0
0
0
5x5
531
17
0
0
0
0
0
0
0
0
0
0
6x6
647
121
0
0
0
0
0
0
0
0
0
0
7x7
794
245
0
0
0
0
0
0
0
0
0
0
8x8
968
398
0
0
0
0
0
0
0
0
0
0
9x9
977
585
0
0
0
0
0
0
0
0
0
0
10x10
1094
676
0
0
0
0
0
0
0
0
0
0
Os resultados das Tabelas 5.3 e 5.4 mostram que o protocolo DSDV apresenta o maior
número de pacotes perdidos na seqüência, sendo que estes valores são bem maiores no início
da simulação ou mesmo quando não existem rotas estabelecidas e os dispositivos esperam
pelas propagações de rotas ao invés de tomar a iniciativa de estabelecer e recriar novas rotas.
A Figura 5.12 mostra o exemplo do cenário 3x3, com mobilidade baixa dos dispositivos, para
uma sessão de videofone. Este cenário teve um total de 754 rajadas. Como se pode observar,
inicialmente foram perdidos aproximadamente 700 pacotes de dados na seqüência (a primeira
rajada). Depois deste intervalo de tempo inicial, onde as rotas foram estabelecidas e
propagadas para todos os dispositivos da rede, o número de pacotes perdidos na seqüência
reduz-se a no máximo quatro.
Distribuição do Número de Pacotes Perdidos na Sequência
Cenário 3x3 -
Mobilidade Baixa - 1 sessão de videofone
Protocolo DSDV
0
100
200
300
400
500
600
700
800
Número das Rajadas
Número de Pacotes Perdidos na
Sequência
754
349
451
Figura 5.12 – Distribuição do número de pacotes perdidos na seqüência para o protocolo DSDV, em
cenários 3x3 de mobilidade baixa, com uma sessão de videofone
60
No entanto, em algumas outras situações, como nas rajadas de número 340 e 451, os
valores destas rajadas também são considerados relevantes. Nestes casos, os dispositivos
ficam esperando pelas propagações de rotas, ao invés de tomar a iniciativa de requisitar novas
rotas. Por isso, a perda de um número maior de pacotes na seqüência durante a simulação.
Os protocolos AODV e DSR, devido a sua abordagem reativa, que permite estabelecer
e recriar novas rotas rapidamente, apresentam valores para perda de pacotes na seqüência
muito baixos, sendo a maioria deles menores do que dez pacotes. No entanto, estes resultados
mudam à medida que aumenta o número de sessões de videofone. A Tabela 5.5 apresenta os
resultados dos cenários de mobilidade alta com oito sessões de videofone quando tais
protocolos de roteamento não são mais estáveis. Nestes cenários, até mesmo os protocolos
reativos apresentam dificuldades em entregar os pacotes de dados. Como já foi comentado
anteriormente, quanto maior o número de sessões de videofone e o nível de mobilidade dos
dispositivos, maior a probabilidade de colisões na rede, maior o número de retransmissões,
conseqüentemente, os pacotes de dados podem demorar muito mais tempo nas filas de
transmissão até chegarem ao destino.
Tabela 5.5 – Distribuição das rajadas de perda de pacotes na seqüência em cenários de mobilidade alta
com 8 sessões de videofone (Protocolos AODV e DSR)
PROTOCOLOS REATIVOS
0-200
200-400
400-600
600-800
800-1000
Acima de 1000
AODV
DSR
AODV
DSR
AODV
DSR
AODV
DSR
AODV
DSR
AODV
DSR
3x3
4327
253
102
7
65
9
7
1
0
0
0
0
4x4
6117
791
55
33
31
14
1
2
0
0
0
0
5x5
8832
2084
140
40
72
16
5
1
0
0
0
0
6x6
10653
2961
137
99
58
50
2
9
0
1
0
0
7x7
15308
2902
170
53
70
19
3
1
0
2
0
0
8x8
14456
4517
70
40
39
7
2
5
0
0
0
0
9x9
20296
4562
137
28
51
2
0
0
0
0
0
0
10x10
27871
5508
167
30
55
9
0
0
0
0
0
0
Considerando que para manter a qualidade de imagem, uma aplicação de videofone
requer taxas de entrega de pacotes da ordem de 95% e valores baixos para as rajadas de
pacotes perdidos na seqüência, os resultados demonstram que os protocolos AODV e DSR
alcançam resultados satisfatórios em praticamente todos os cenários. No entanto, como se
pode observar na Figura 5.11 e na Tabela 5.5, estes ótimos resultados apresentam um limite
quanto ao nível de mobilidade dos dispositivos e o número de sessões de videofone. Assim,
considerando o cenário híbrido de redes móveis
ad hoc
, pode-se concluir que tais protocolos
61
são adequados para esta classe de aplicação com restrições no número de sessões de
videofone e no nível de mobilidade dos dispositivos.
5.2 Retardo de Entrega
Considerando que aplicações de videofone requerem pequenos retardos, especificamente
valores menores do que 400ms [Mehaoua 99] para uma interação natural dos participantes,
estes resultados correspondem ao retardo de entrega (medido em segundos) dos pacotes de
dados que chegaram dentro do intervalo válido para esta classe de aplicação, uma vez que os
pacotes entregues com retardo maior do que 400ms são descartados no receptor.
Comparando os resultados mostrados nas Figuras 5.13 e 5.14, percebe-se que
normalmente os retardos aumentam com o tamanho dos cenários e com o número de sessões
de videofone estabelecido entre os dispositivos móveis. Quanto maior o tamanho dos
cenários, maior a probabilidade de procedimentos de aquisição de rotas bem mais longos,
assim como o estabelecimento de rotas cada vez maiores.
Mobilidade Alta
(Protocolo AODV)
0,00
0,01
0,02
0,03
0,04
0,05
0,06
0,07
Cenários
Retardo de Entrega
1 sessão
0,0095
0,0119
0,0136
0,0153
0,0165
0,0179
0,0191
0,0202
2 sessões
0,0145
0,0185
0,0199
0,0216
0,0230
0,0238
0,0247
0,0251
4 sessões
0,0245
0,0297
0,0316
0,0326
0,0328
0,0328
0,0328
0,0328
8 sessões
0,0479
0,0566
0,0578
0,0570
0,0538
0,0529
0,0504
0,0481
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.13 – Retardo de entrega por sessão de videofone para o AODV
em cenários de mobilidade alta
62
Mobilidade Alta
(Protocolo DSR)
0,00
0,01
0,02
0,03
0,04
0,05
0,06
0,07
0,08
Cenários
Retardo de Entrega
1 sessão
0,0106
0,0140
0,0173
0,0205
0,0229
0,0258
0,0281
0,0291
2 sessões
0,0161
0,0205
0,0236
0,0267
0,0288
0,0308
0,0316
0,0335
4 sessões
0,0270
0,0331
0,0360
0,0384
0,0398
0,0404
0,0417
0,0424
8 sessões
0,0534
0,0630
0,0654
0,0656
0,0656
0,0663
0,0670
0,0657
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.14 – Retardo de entrega por sessão de videofone para o DSR
em cenários de mobilidade alta
Já o número de sessões de videofone influencia muito mais o retardo de entrega dos
pacotes do que o tamanho dos cenários. A justificativa para este comportamento é bastante
simples, à medida que cresce o número de origens de tráfego dentro da rede, o retardo
aumenta devido às filas de transmissão dos dispositivos tornarem-se cada vez mais cheias. O
trabalho desenvolvido por Johansson [Johansson 99] também identificou o mesmo
comportamento em termos de origens de tráfego.
Como se pode observar nas Figuras 5.15 e 5.16, um parâmetro que pouco influencia o
retardo de entrega dos pacotes é o nível de mobilidade dos dispositivos. Apenas para o
protocolo DSR que este parâmetro exerce uma influência considerada relevante (Figura 5.17).
Estes resultados já eram esperados, pois de acordo com [Royer 99, Johansson 99] o DSR
adapta-se melhor a cenários onde os dispositivos movem-se a velocidades moderadas.
Protocolo DSDV
(1 sessão de videofone)
0,000
0,002
0,004
0,006
0,008
0,010
0,012
0,014
0,016
Cenários
Retardo de Entrega
Baixa
0,006
0,007
0,009
0,011
0,012
0,013
0,014
0,015
Moderada
0,005
0,008
0,008
0,010
0,011
0,013
0,013
0,015
Alta
0,004
0,005
0,007
0,009
0,010
0,011
0,012
0,014
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.15 – Retardo de Entrega por níveis de mobilidade para o DSDV
em cenários com uma sessão de videofone
63
Protocolo AODV
(1 sessão de videofone)
0,000
0,005
0,010
0,015
0,020
0,025
Cenários
Retardo de Entrega
Baixa
0,009
0,009
0,011
0,013
0,015
0,015
0,017
0,017
Moderada
0,009
0,011
0,013
0,015
0,016
0,017
0,018
0,020
Alta
0,009
0,012
0,014
0,015
0,016
0,018
0,019
0,020
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.16 – Retardo de Entrega por níveis de mobilidade para o AODV
em cenários com uma sessão de videofone
Protocolo DSR
(1 sessão de videofone)
0,000
0,005
0,010
0,015
0,020
0,025
0,030
0,035
Cenários
Retardo de Entrega
Baixa
0,007
0,009
0,010
0,012
0,014
0,015
0,016
0,017
Moderada
0,009
0,012
0,014
0,016
0,018
0,019
0,020
0,022
Alta
0,011
0,014
0,017
0,020
0,023
0,026
0,028
0,029
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.17 – Retardo de Entrega por níveis de mobilidade para o DSR
em cenários com uma sessão de videofone
Nos cenários simulados com o DSDV, este protocolo apresenta os menores retardos
de entrega, como mostram as Figuras 5.18, 5.19 e 5.20. Uma das principais características dos
protocolos pró-ativos é a disponibilidade imediata de rotas, mantendo informações
consistentes para todos os dispositivos, o que reduz, consideravelmente, o atraso de
transmissão inicial dos pacotes. Convém ressaltar que, este retardo corresponde à pequena
parcela de pacotes de dados que foram entregues ao destino.
64
Mobilidade Baixa
(
1 sessão de videofone
)
0,004
0,006
0,008
0,010
0,012
0,014
0,016
0,018
0,020
Cenários
Retardo de Entrega
DSDV
0,0056
0,0072
0,0092
0,0108
0,0116
0,0130
0,0141
0,0149
AODV
0,0090
0,0095
0,0115
0,0129
0,0148
0,0153
0,0166
0,0174
DSR
0,0068
0,0087
0,0098
0,0119
0,0138
0,0150
0,0160
0,0168
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.18 – Retardo de Entrega nos cenários de mobilidade baixa com uma sessão de videofone
Mobilidade Moderada
(1 sessão de videofone
)
0,000
0,005
0,010
0,015
0,020
0,025
Cenários
Retardo de Entrega
AODV
0,008736
0,010663
0,012719
0,014659
0,015813
0,017238
0,018435
0,020025
DSDV
0,005229
0,007608
0,008204
0,009679
0,010871
0,012705
0,013487
0,014787
DSR
0,008981
0,011519
0,013788
0,015941
0,017507
0,018948
0,020248
0,021601
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.19 – Retardo de Entrega nos cenários de mobilidade moderada com uma sessão de videofone
Mobilidade Alta
(1 sessão de videofone)
0,000
0,005
0,010
0,015
0,020
0,025
0,030
0,035
Cenários
Retardo de Entrega
AODV
0,00945
0,011864
0,013642
0,015346
0,016499
0,017912
0,01906
0,020198
DSDV
0,004019
0,004996
0,006531
0,008533
0,010058
0,011369
0,012429
0,013855
DSR
0,010582
0,014047
0,017284
0,02045
0,022851
0,025804
0,028072
0,02912
3x3
4x4
5x5
6x6
7x7
8x8
9x9
10x10
Figura 5.20 – Retardo de Entrega nos cenários de mobilidade alta com uma sessão de videofone
65
Nos cenários de mobilidade baixa, ou seja, os cenários com 1, 2, 4 e 8 sessões de
videofone, o protocolo DSR apresenta desempenho superior ao AODV em termos de retardo
de entrega, como mostram as Figuras 5.18 e 5.21 para os cenários com 1 e 8 sessões de
videofone respectivamente. Este comportamento pode ser explicado pela forma como as rotas
são estabelecidas para este protocolo, que adota o conceito de múltiplas rotas. Em apenas um
ciclo de requisição de rotas, um número maior de rotas é determinado, devido às suas
características de roteamento na origem e do modo de operação promíscuo para manter rotas
válidas. No entanto, esta diferença diminui à medida que o tamanho da rede aumenta,
podendo estes resultados serem revertidos em alguns cenários.
Como mostram as Figuras 5.22 e 5.23, nos cenários de mobilidade moderada e alta
(exceto os cenários com uma sessão de videofone), o protocolo AODV apresenta os menores
retardos, sendo que nos cenários menores estes valores são considerados relativamente
próximos, com esta diferença aumentando à medida que o tamanho dos cenários aumenta.
Esta mudança de comportamento deve-se ao roteamento na origem, principal característica do
DSR, que interfere diretamente no desempenho deste protocolo em cenários maiores, níveis
de mobilidade mais altos e um número maior de sessões de videofone, tornando-o um
protocolo não muito escalável. Além disso, o DSR utiliza as rotas armazenadas em
cache
e
não adota nenhum mecanismo para expirar rotas velhas ou mesmo diferenciar rotas mais
velhas daquelas atualizadas no caso de múltiplas rotas para o mesmo destino [Perkins 00].
Mobilidade Baixa
(
8 sessões de videofone
)
0,00
0,01
0,02
0,03
0,04
0,05
0,06
0,07
Cenários
Retardo de Entrega
AODV
0,0480
0,0563
0,0586
0,0550
0,0546
0,0533
0,0519
0,0492
DSR
0,0396
0,0498
0,0533
0,0537
0,0521
0,0510
0,0514
0,0502
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.21 – Retardo de Entrega nos cenários de mobilidade baixa com oito sessões de videofone
66
Mobilidade Moderada
(8 sessões de videofone
)
0,00
0,01
0,02
0,03
0,04
0,05
0,06
0,07
Cenários
Retardo de Entrega
AODV
0,0450
0,0537
0,0555
0,0552
0,0540
0,0520
0,0510
0,0502
DSR
0,0431
0,0540
0,0583
0,0591
0,0589
0,0586
0,0578
0,0568
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.22 – Retardo de Entrega nos cenários de mobilidade moderada com oito sessões de videofone
Mobilidade Alta
(8 sessões de videofone)
0,00
0,01
0,02
0,03
0,04
0,05
0,06
0,07
0,08
Cenários
Retardo de Entrega
AODV
0,047932
0,056582
0,057834
0,056987
0,053771
0,052939
0,050381
0,048053
DSR
0,053437
0,062972
0,065428
0,065552
0,065590
0,066318
0,066985
0,065662
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.23 – Retardo de Entrega nos cenários de mobilidade alta com oito sessões de videofone
5.3 Distribuição do Retardo de Entrega de Pacotes
Um outro requisito importante para aplicações de videofone definido neste trabalho é a
probabilidade de entrega dos pacotes de dados dentro de intervalos de retardo. Como o retardo
máximo de entrega para esta classe de aplicação é de 400ms (milisegundos), este valor foi
dividido em intervalos de 50ms, que vão desde 0ms até 400ms. O objetivo é analisar a
probabilidade destes pacotes chegarem em intervalos de tempo cada vez menores, uma vez
que quanto menor for este retardo, melhor a qualidade do áudio e vídeo apresentados no
receptor. Sendo esta probabilidade muito maior para pequenos intervalos (por exemplo, 0ms a
67
50ms), isto significa que a informação é apresentada ao usuário com uma boa qualidade
durante praticamente toda a sessão de videofone.
As Figuras 5.24 e 5.25 mostram estes resultados para os cenários 7x7 de mobilidades
baixas e altas, com 1, 2, 4 e 8 sessões de videofone. Como este comportamento se repete em
praticamente todos os cenários, optamos em colocar todos os outros gráficos no Apêndice E.
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
P[Intervalos de Retardo]
0-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
Intervalos de Retardo
Mobilidade Baixa - Cenários 7x7 - 1 sessão videofone
AODV
DSDV
DSR
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
P[Intervalos de Retardo]
0-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
Intervalos de Retardo
Mobilidade Baixa - Cenários 7x7 - 2 sessões videofone
AODV
DSR
0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1,0
P[Intervalos de Retardo]
0-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
Intervalos de Retardo
Mobilidade Baixa - Cenários 7x7 - 4 sessões videofone
AODV
DSR
0,0
0,1
0,2
0,3
0,4
0,5
0,6
P[Intervalos de Retardo]
0-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
Intervalos de Retardo
Mobilidade Baixa - Cenários 7x7 - 8 sessões de videofone
AODV
DSR
Figura 5.24 – Probabilidade de Entrega dos Pacotes de Dados em Intervalos de Retardo para
Cenários de Mobilidade Baixa
68
0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1,0
P[Intervalos de Retardo]
00-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
Intervalos de Retardo
Mobilidade Alta - Cenários 7x7 - 1 sessão de videofone
AODV
DSDV
DSR
0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1,0
P[Intervalos de Retardo]
00-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
Intervalos de Retardo
Mobilidade Alta - Cenários 7x7 - 2 sessões de videofone
AODV
DSR
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
P[Intervalos de Retardo]
00-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
Intervalos de Retardo
Mobilidade Alta - Cenários 7x7 - 4 sessões de videofone
AODV
DSR
0
0,1
0,2
0,3
0,4
0,5
0,6
P[Intervalos de Retardo]
00-50
50-100
100-150
150-200
200-250
250-300
300-350
350-400
Intervalos de Retardo
Mobilidade Alta - Cenários 7x7 - 8 sessões de videofone
AODV
DSR
Figura 5.25 – Probabilidade de Entrega dos Pacotes de Dados em Intervalos de Retardo para
Cenários de Mobilidade Alta
Normalmente, nos cenários de rede com até 2 sessões de videofone, a probabilidade
de entrega dos pacotes de dados dentro do intervalo de 0 a 50ms é de praticamente 1 para
todos os protocolos de roteamento. Os cenários com 4 sessões começam a apresentar
resultados diferentes, onde um número pequeno destes pacotes começa a ser entregue dentro
do intervalo de 50 a 100ms. Para cenários com 8 sessões, percebe-se uma certa dificuldade
dos protocolos de roteamento em entregar estes pacotes em intervalos cada vez menores,
ficando uma probabilidade de quase 0.5 para cada um destes dois intervalos de retardo (0 a
50ms; 50 -100ms). Além disso, um pequeno número de pacotes já começa a ser entregue em
intervalos de 100 a 150ms.
Como se pode observar na Figura 5.24, o protocolo DSR normalmente apresenta
maior probabilidade de entrega de pacotes de dados dentro do intervalo de 0 a 50ms, em
cenários com mobilidade baixa dos dispositivos, do que o protocolo AODV, sendo esta
diferença bem visível em cenários com um maior número de sessões de videofone (4 e 8
sessões). Em praticamente todos os outros cenários, estes resultados são revertidos, assim
como mostra a Figura 5.25. Como já foi explicado anteriormente, o roteamento na origem,
69
uma das principais características do DSR, limita a escalabilidade deste protocolo em termos
de mobilidade dos dispositivos.
Como a maioria dos resultados mostra uma probabilidade de entrega de pacotes em
intervalos de retardo de até 150ms, conclui-se então que os protocolos de roteamento para
redes móveis
ad hoc
convergem rapidamente às mudanças na topologia da rede (exceto o
protocolo DSDV que apresenta uma taxa de entrega muito pequena se comparada aos outros
protocolos). No entanto, como pode ser observado através das Figuras 5.24 e 5.25, o número
de sessões de videofone influencia muito mais estes resultados do que o nível de mobilidade
dos dispositivos, sendo que o tamanho dos cenários não apresenta praticamente nenhuma
influência sobre a probabilidade de entrega destes pacotes em intervalos de retardo menores.
5.4 Variação do Retardo (
Jitter
)
Normalmente, as aplicações de videofone podem tolerar uma variação do retardo de até
130ms [Mehaoua 99, Wong 00] enquanto preservam uma boa interatividade entre os
participantes de uma sessão. Valores acima deste intervalo podem provocar perdas
significativas na qualidade do vídeo (distorções das cores), além de aumentar a probabilidade
de perdas de sincronização entre o áudio e o vídeo, provocando o chamado
skew
. Estes
resultados mostram a variação do retardo (medido em segundos) provocada pelas aplicações
de videofone em um cenário híbrido de redes
ad hoc.
As Figuras 5.26 e 5.27 mostram que a variação do retardo aumenta com o número de
sessões de videofone. Quanto maior o número de sessões de videofone, maior a probabilidade
de congestionamento na rede e, conseqüentemente, maior a probabilidade de colisões. Os
pacotes que sofrem colisão devem ser retransmitidos, sofrendo um retardo diferente e variável
em relação àqueles que não foram retransmitidos.
70
Protocolo AODV
(Mobilidade Alta)
0,000
0,005
0,010
0,015
0,020
0,025
0,030
0,035
0,040
Cenários
Variação do Retardo
1 sessão
0,0070
0,0074
0,0080
0,0084
0,0081
0,0085
0,0083
0,0084
2 sessões
0,0104
0,0121
0,0128
0,0130
0,0133
0,0134
0,0135
0,0133
4 sessões
0,0161
0,0187
0,0193
0,0196
0,0194
0,0189
0,0187
0,0183
8 sessões
0,0293
0,0341
0,0346
0,0336
0,0309
0,0297
0,0279
0,0261
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.26 – Variação do retardo dos pacotes de dados por sessão de videofone para o AODV
em cenários de mobilidade alta
Protocolo DSR
(Mobilidade Alta)
0,00
0,01
0,02
0,03
0,04
0,05
0,06
Cenários
Variação do Retardo
1 sessão
0,0076
0,0102
0,0128
0,0155
0,0175
0,0194
0,0215
0,0221
2 sessões
0,0128
0,0161
0,0186
0,0211
0,0230
0,0243
0,0250
0,0257
4 sessões
0,0217
0,0255
0,0272
0,0289
0,0297
0,0304
0,0311
0,0320
8 sessões
0,0478
0,0555
0,0570
0,0561
0,0537
0,0517
0,0518
0,0501
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.27 – Variação do retardo dos pacotes de dados por sessão de videofone para o DSR
em cenários de mobilidade alta
Outro fator que influencia diretamente na variação do retardo é o nível de mobilidade
dos dispositivos, como pode ser observado nas Figuras 5.28 e 5.29. Quanto maior o nível de
mobilidade dos dispositivos, maior o número de mudanças na topologia da rede e,
conseqüentemente, maior o número de alterações na rota entre os pares de dispositivos. Cada
nova rota estabelecida entre dois dispositivos apresenta retardos diferentes. Como estas rotas
mudam constantemente, o retardo de entrega dos pacotes também sofre alterações.
71
Protocolo AODV
(1 sessão de videofone)
0,000
0,001
0,002
0,003
0,004
0,005
0,006
0,007
0,008
0,009
Cenários
Variação do Retardo
Baixa
0,00393
0,00406
0,00403
0,00413
0,00398
0,00362
0,00396
0,00381
Moderada
0,00571
0,00610
0,00693
0,00725
0,00721
0,00732
0,00765
0,00814
Alta
0,00695
0,00742
0,00799
0,00842
0,00814
0,00847
0,00832
0,00837
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.28 – Variação do retardo para o AODV em cenários com uma sessão de videofone
Protocolo DSR
(1 sessão de videofone)
0,000
0,005
0,010
0,015
0,020
0,025
Cenários
Variação do Retardo
Baixa
0,00358
0,00405
0,00420
0,00463
0,00520
0,00468
0,00475
0,00459
Moderada
0,00570
0,00721
0,00839
0,00928
0,00975
0,01042
0,01071
0,01100
Alta
0,00756
0,01023
0,01278
0,01547
0,01748
0,01940
0,02151
0,02211
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.29 – Variação do retardo para o DSR em cenários com uma sessão de videofone
Como se pode observar nas Figuras 5.30, 5.31, 5.32 e 5.33, o protocolo AODV
apresenta um comportamento melhor do que o DSR na maioria dos cenários. O problema é
que o mecanismo de roteamento na origem adotado por este último protocolo, pode provocar
intervalos consideráveis e variáveis na chegada dos pacotes, uma vez que estes pacotes são
processados pelos dispositivos intermediários, que tentam extrair informações de roteamento
antes mesmo de retransmiti-los. Como os dispositivos que trocam informações estão sempre
se movendo, novas rotas são estabelecidas, com uma quantidade de dispositivos
intermediários diferentes, o que provoca variações no retardo entre origem e destino.
72
Mobilidade Moderada
(1 sessão de videofone)
0,000
0,002
0,004
0,006
0,008
0,010
0,012
Cenários
Variação do Retardo
AODV
0,005707
0,006099
0,006929
0,007247
0,007209
0,007321
0,007652
0,008139
DSDV
0,003316
0,003982
0,003774
0,003738
0,003756
0,003947
0,003964
0,004197
DSR
0,005704
0,007211
0,008394
0,009276
0,009752
0,010422
0,010713
0,010999
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.30 – Variação do retardo em cenários de mobilidade moderada com uma sessão de videofone
Mobilidade Moderada
(8 sessões de videofone)
0,000
0,005
0,010
0,015
0,020
0,025
0,030
0,035
0,040
0,045
Cenários
Variação do Retardo
AODV
0,025287
0,029302
0,029939
0,029861
0,028462
0,027285
0,026516
0,02555
DSR
0,03164
0,038376
0,040371
0,040969
0,039757
0,039171
0,038065
0,036725
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.31 – Variação do retardo em cenários de mobilidade moderada com oito sessões de videofone
Mobilidade Alta
(1 sessão de videofone)
0,000
0,005
0,010
0,015
0,020
0,025
Cenários
Variação do Retardo
AODV
0,00695
0,007416
0,007985
0,008423
0,008142
0,008473
0,008317
0,008366
DSDV
0,002537
0,002977
0,003338
0,003965
0,003817
0,004118
0,003851
0,004098
DSR
0,007558
0,010234
0,012783
0,01547
0,017475
0,019403
0,021506
0,022109
3x3
4x4
5x5
6x6
7x7
8x8
9x9
10x10
Figura 5.32 – Variação do retardo em cenários de mobilidade alta com uma sessão de videofone
73
Mobilidade Alta
(8 sessões de videofone)
0,00
0,01
0,02
0,03
0,04
0,05
0,06
Cenários
Variação do Retardo
AODV
0,0293
0,0341
0,0346
0,0336
0,0309
0,0297
0,0279
0,0261
DSR
0,0478
0,0555
0,0570
0,0561
0,0537
0,0517
0,0518
0,0501
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.33 – Variação do retardo em cenários de mobilidade alta com oito sessões de videofone
Considerando os requisitos de uma aplicação de videofone, os gráficos mostram
claramente que o
jitter
para os cenários de rede móveis
ad hoc
definidos neste trabalho está
dentro dos limites da variação do retardo máximo, ou seja, dentro dos 130ms.
5.4 Carga de Roteamento
Os resultados mostrados nas Figuras 5.34, 5.35 e 5.36 evidenciam que a carga de roteamento
aumenta com o incremento da mobilidade dos dispositivos. A justificativa é bastante simples
e intuitiva. Quanto maior for a mobilidade, maior a possibilidade de perda de conectividade,
maior o número de ativações dos mecanismos de estabelecimento de rotas, e assim, maior o
número de mensagens de roteamento.
Protocolo DSDV
(1 sessão de videofone)
0
2
4
6
8
10
12
14
16
18
20
Cenários
Carga de Roteamento
Baixa
0,0830
0,1320
0,2357
0,3992
0,7944
1,6048
2,9393
4,5089
Moderada
0,2375
0,4243
0,9120
1,5876
2,5311
4,2000
6,6809
9,9292
Alta
0,307222
0,785503
1,831133
3,415609
5,302836
8,545704
12,505735
18,269615
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.34 - Carga de roteamento para o DSDV em cenários com uma sessão de videofone
74
Protocolo AODV
(1 sessão de videofone)
0
1
2
3
4
5
Cenários
Carga de Roteamento
Baixa
0,0246
0,0340
0,0498
0,0574
0,0724
0,0931
0,1143
0,1339
Moderada
0,2417
0,3677
0,5047
0,6661
0,7975
1,0176
1,2589
1,5979
Alta
0,411081
0,634173
0,893999
1,167698
1,529420
1,821482
2,304530
2,804722
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.35 – Carga de roteamento para o AODV em cenários com uma sessão de videofone
Protocolo DSR
(1 sessão de videofone)
0
1
2
3
4
5
Cenários
Carga de Roteamento
Baixa
0,0135
0,0256
0,0370
0,0496
0,0758
0,1002
0,1344
0,1377
Moderada
0,1138
0,2273
0,3519
0,5405
0,7629
0,9998
1,3222
1,5803
Alta
0,208262
0,370399
0,630087
0,951740
1,429210
1,832776
2,808208
3,450563
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.36 – Carga de roteamento para o DSR em cenários com uma sessão de videofone
Como se pode observar nas Figuras 5.37 e 5.38, a carga de roteamento também é
influenciada diretamente pelo tamanho dos cenários. Da mesma forma que o incremento na
mobilidade provoca a perda de conectividade entre os dispositivos, quanto maior for o
tamanho do cenário, maior a distância entre estes dispositivos para que realizem o mesmo
padrão de movimento. Conseqüentemente, maior o número de retransmissões das mensagens
de roteamento, pois à medida que aumentamos os cenários, também aumentamos o número de
pontos de acesso. No entanto, o número de sessões de videofone pouco influencia nestes
resultados, exceto nos cenários com oito sessões. Estes protocolos se beneficiam do
incremento no número de fluxos conversacionais. Um simples mecanismo de requisição ou
manutenção de rotas pode beneficiar um número maior destes fluxos, evitando novas
75
propagações de mensagens de roteamento na rede. Resultados semelhantes também foram
encontrados no trabalho desenvolvido por Das [Das 00].
Protocolo AODV
(
Mobilidade Alta
)
0,0
0,5
1,0
1,5
2,0
2,5
3,0
3,5
4,0
4,5
Cenários
Carga de Roteamento
1 sessão
0,411081
0,634173
0,893999
1,167698
1,529420
1,821482
2,304530
2,804722
2 sessões
0,4912
0,6942
0,9603
1,2653
1,5280
1,8876
2,3536
2,7583
4 sessões
0,6595
0,9114
1,1744
1,5037
1,8561
2,2604
2,6683
3,1531
8 sessões
1,1095
1,6121
1,9625
2,2627
2,6153
3,0606
3,4901
3,9552
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.37 – Carga de roteamento para o AODV em cenários de mobilidade alta
Protocolo DSR
(Mobilidade Alta)
0,0
0,5
1,0
1,5
2,0
2,5
3,0
3,5
4,0
Cenários
Carga de Roteamento
1 sessão
0,208262
0,370399
0,630087
0,951740
1,429210
1,832776
2,808208
3,450563
2 sessões
0,2320
0,3807
0,5897
0,9012
1,2600
1,6757
2,1854
3,3984
4 sessões
0,2911
0,4699
0,6847
1,0282
1,3207
1,6981
2,2676
2,8991
8 sessões
0,4685
0,7801
1,1341
1,5853
1,9338
2,3459
2,8308
3,4198
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.38 – Carga de roteamento para o DSR em cenários de mobilidade alta
Como mostram as Figuras 5.39, 5.40 e 5.41, em todos os cenários para os quais foi
simulado, o protocolo DSDV apresenta as maiores cargas de roteamento devido a sua
abordagem pró-ativa. Estes resultados são influenciados diretamente pelo tamanho da rede e
nível de mobilidade dos dispositivos. No entanto, é possível perceber, através da Figura 5.34
(mostrada anteriormente) que o tamanho da rede influencia de forma mais acentuada a carga
de roteamento do que o nível de mobilidade. Este comportamento pode ser justificado pelas
propagações periódicas que todos os dispositivos devem realizar para manter rotas válidas
76
entre quaisquer pares de dispositivos dentro da rede (mesmo entre aqueles que não estão
trocando informações). Desta forma, quanto maior o número de dispositivos, maior a carga de
roteamento. Para mostrar mais uma vez que os cenários de rede e as aplicações influenciam
diretamente nos resultados das simulações, estes resultados divergem daqueles encontrados
em [Lu 03] que identificam o DSDV como um protocolo mais escalável do que o AODV.
Mobilidade Baixa
(
1 sessão de videofone
)
0,0
0,5
1,0
1,5
2,0
2,5
3,0
3,5
4,0
4,5
5,0
Cenários
Carga de Roteamento
DSDV
0,083
0,132
0,236
0,399
0,794
1,605
2,939
4,509
AODV
0,025
0,034
0,050
0,057
0,072
0,093
0,114
0,134
DSR
0,013
0,026
0,037
0,050
0,076
0,100
0,134
0,138
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.39 – Carga de roteamento nos cenários de mobilidade baixa com uma sessão de videofone
Mobilidade Moderada
(
1 sessão de videofone
)
0
2
4
6
8
10
12
Cenários
Carga de Roteamento
AODV
0,242
0,368
0,505
0,666
0,798
1,018
1,259
1,598
DSDV
0,238
0,424
0,912
1,588
2,531
4,200
6,681
9,929
DSR
0,114
0,227
0,352
0,540
0,763
1,000
1,322
1,580
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.40 – Carga de Roteamento nos cenários de mobilidade moderada com uma sessão de videofone
77
Mobilidade Alta
(1 sessão de videofone)
0
2
4
6
8
10
12
14
16
18
20
Cenários
Carga de Roteamento
AODV
0,411081
0,634173
0,893999
1,167698
1,529420
1,821482
2,304530
2,804722
DSDV
0,307222
0,785503
1,831133
3,415609
5,302836
8,545704
12,505735
18,269615
DSR
0,208262
0,370399
0,630087
0,951740
1,429210
1,832776
2,808208
3,450563
3x3
4x4
5x5
6x6
7x7
8x8
9x9
10x10
Figura 5.41 – Carga de Roteamento nos cenários de mobilidade alta com uma sessão de videofone
Por outro lado, em praticamente todos os cenários, os protocolos AODV e DSR
apresentam as menores cargas de roteamento. Os excelentes resultados do AODV e DSR
podem ser justificados pela semelhança no procedimento de estabelecer rotas. As atualizações
de rotas destes protocolos são concentradas apenas nas extremidades das mesmas. Ou seja,
como os dispositivos móveis são os únicos que geram pacotes, ambos são os primeiros a
perceber a perda de conectividade, reenviando mensagens de requisição de rotas para
recriação de rotas. Como os dispositivos intermediários possuem rotas válidas e respondem
tais requisições, os dispositivos móveis recriam as rotas sem a necessidade de inundar a rede
com mensagens de roteamento. Adicionalmente, estes protocolos adotam o conceito de rotas
simétricas, permitindo que, em um único procedimento, rotas em ambas as direções sejam
estabelecidas. Este mecanismo reduz sensivelmente o número de mensagens de roteamento.
Observando as Figuras 5.42, 5.43 e 5.44, percebe-se que o protocolo DSR apresenta
um excelente comportamento, em termos de carga de roteamento, para todos os cenários,
inclusive nos cenários de mobilidade alta e nos cenários com 8 sessões de videofone. Estes
valores são quase sempre menores (ou pelo menos equivalentes, como mostram as Figuras
5.39, 5.40 e 5.41) do que aqueles correspondentes ao do protocolo AODV, que também utiliza
mecanismos de requisição e manutenção de rotas sob demanda. Os resultados contradizem
com aqueles encontrados em análises anteriores [Royer 99, Johansson 99], que identificam o
DSR como um protocolo adequado somente para redes menores e com níveis de mobilidade
moderados. Em algumas situações isoladas, como mostra a Figura 5.41, observa-se este
comportamento, onde a diferença entre os valores de carga de roteamento para o DSR e o
AODV diminui à medida que o tamanho da rede aumenta.
78
Mobilidade Baixa
(
8 sessões de videofone
)
0,00
0,10
0,20
0,30
0,40
0,50
0,60
Cenários
Carga de Roteamento
AODV
0,0946
0,2800
0,3678
0,3859
0,4270
0,4796
0,4722
0,5047
DSR
0,0311
0,0657
0,0977
0,1313
0,1523
0,1751
0,2183
0,2744
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.42 – Carga de Roteamento nos cenários de mobilidade baixa com oito sessões de videofone
Mobilidade Moderada
(8 sessões de videofone)
0,0
0,5
1,0
1,5
2,0
2,5
3,0
Cenários
Carga de Roteamento
AODV
0,6867
0,9912
1,2342
1,4483
1,6369
1,8770
2,1344
2,4404
DSR
0,2410
0,4064
0,5959
0,8055
1,0342
1,2932
1,5682
1,7761
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.43 – Carga de Roteamento nos cenários de mobilidade moderada com oito sessões de videofone
Mobilidade Alta
(8 sessões de videofone)
0,0
0,5
1,0
1,5
2,0
2,5
3,0
3,5
4,0
4,5
Cenários
Carga de Roteamento
AODV
1,1095
1,6121
1,9625
2,2627
2,6153
3,0606
3,4901
3,9552
DSR
0,4685
0,7801
1,1341
1,5853
1,9338
2,3459
2,8308
3,4198
3X3
4X4
5X5
6X6
7X7
8X8
9X9
10X10
Figura 5.44 – Carga de Roteamento nos cenários de mobilidade alta com oito sessões de videofone
79
Os gráficos mostram claramente que o protocolo DSR se adapta melhor a cenários
com um número maior de sessões de videofone do que o próprio AODV, que adota
mecanismos similares para obtenção de rotas. Este comportamento pode ser explicado por
vários aspectos destes protocolos. Primeiro, o DSR é um protocolo de roteamento na origem
que requer que os dispositivos operem em modo promíscuo. Desta forma, todos os
dispositivos escutam os pacotes transmitidos pelos demais, aprendendo as rotas sinalizadas
nestes pacotes, sem a necessidade de gerar mensagens de roteamento adicionais. Segundo, o
DSR suporta múltiplas rotas, o que reduz o número de ativações dos procedimentos de
estabelecimento de rotas. Em uma única solicitação, o DSR aprende um número maior de
rotas, diferentemente do que acontece com o AODV, limitado somente ao aprendizado de
rotas entre a origem e o destino da comunicação. Terceiro, o AODV utiliza mensagens de
sinalização periódicas para manter a noção de conectividade, sendo que no DSR os
dispositivos monitoram os pacotes de confirmação dos outros dispositivos ou mesmo escutam
todas as comunicações que passam por eles.
Considerando que uma baixa carga de roteamento sinaliza que rotas são estabelecidas
de forma mais rápida, pode-se concluir que os protocolos AODV e DSR certamente mantêm
rotas válidas nas tabelas dos diversos dispositivos por um maior intervalo de tempo. Por sua
vez, estas rotas permitem a entrega de um maior número de pacotes e reduz o retardo de
entrega dos mesmos.
80
Capítulo 6
Trabalhos Relacionados
Embora já existam algumas análises comparativas para os protocolos de roteamento
ad hoc
,
nenhuma destas é conduzida levando em consideração um cenário híbrido de redes
ad hoc
e
os requisitos de uma aplicação de videofone para um sistema de monitoramento digital de
imagens. Alguns destes trabalhos serão apresentados aqui, de forma resumida, como forma de
diferenciar cada um deles com a contribuição da proposta deste trabalho. Todos os trabalhos
abaixo relacionados foram simulados na ferramenta NS.
Um dos primeiros trabalhos com o objetivo de analisar o desempenho destes
protocolos de roteamento foi desenvolvido por Broch [Broch 98]. Esta simulação foi baseada
em 50 dispositivos móveis que se movem em uma área de 1500m x 300m por 900 segundos.
Foram gerados 70 arquivos de cenários diferentes, alterando apenas o padrão de movimento e
o número de fluxos conversacionais, sendo que os protocolos DSDV, AODV, DSR e TORA
foram simulados para cada um destes cenários. O movimento é semelhante ao desenvolvido
para este trabalho, porém existe um intervalo de velocidade máxima (20m/s e 1m/s) que os
dispositivos podem alcançar, além de 7 diferentes tempos de pausa para quando os
dispositivos alcançarem a posição destino (10 cenários para cada tempo de pausa definido). O
modelo de comunicação adotado utiliza um tráfego constante na origem (CBR), com pacotes
de 64 Bytes sendo transmitidos por 10, 20 e 30 origens a 4 pacotes por segundo. As
características de transmissão foram baseadas no alcance de 250 metros e uma taxa de
transmissão de 2 Mbps. Os parâmetros qualitativos adotados foram taxa de entrega dos
pacotes, carga de roteamento e o melhor caminho para se chegar ao destino (em termos de
número de dispositivos intermediários). Como resultados, o trabalho apresenta o DSDV com
problemas de convergência quando o nível de mobilidade dos dispositivos aumenta. O TORA
apresenta uma carga de roteamento elevada, mas entrega cerca de 90 % dos pacotes para um
81
número menor de fluxos conversacionais, não se adequando a redes mais densas. O DSR
apresenta um bom desempenho para todos os níveis de mobilidade, embora apresente uma
carga de roteamento, em termos de bytes, muito elevada. O protocolo AODV apresenta
comportamento semelhante ao DSR em praticamente todos os cenários, sendo que o aumento
nas taxas de mobilidade requer um número maior de transmissão de pacotes de roteamento, o
que torna o AODV mais dispendioso do que o DSR. Apesar de alguns pontos semelhantes, a
pesquisa desenvolvida por Broch apresenta muitas diferenças deste trabalho. Primeiramente, o
trabalho de Broch não direciona o seu conjunto de simulações para análise de requisitos de
uma aplicação de videofone e muito menos utiliza um cenário híbrido de redes
ad hoc
, que
permita a definição de rotas em quaisquer posições que se encontrem os dispositivos móveis.
O tamanho da rede não foi considerado um parâmetro qualitativo para os protocolos de
roteamento
ad hoc
, diferentemente da abordagem proposta para este trabalho. Sem contar que
as simulações realizadas por Broch apresentam valores diferentes para tamanho dos pacotes,
velocidade dos dispositivos móveis, alcance de transmissão e tempo de simulação, o que
podem influenciar diretamente nos resultados das simulações, como foi observado nas
considerações feitas neste trabalho.
O trabalho desenvolvido por [Lu 03] propõe um novo protocolo de roteamento
ad
hoc
, baseado num estudo comparativo entre os protocolos DSDV e AODV. O protocolo
CADV (
Congestion-Aware Distance Vector
) tem como objetivo integrar mecanismos que
evitem congestionamentos na rede, com protocolos de roteamento pró-ativos para fornecer
um melhor desempenho nas funções de roteamento. O estudo comparativo entre os dois
protocolos Vetor de Distância também utiliza a ferramenta NS e define como pontos de
variabilidade a mobilidade dos dispositivos, o número de fluxos conversacionais e o tamanho
da rede. Muitos dos parâmetros foram adotados do trabalho [Broch 98] comentado
anteriormente. Por exemplo, movimento randômico com a definição do tempo de pausa de 10
segundos, taxa de transmissão de 2Mbps, alcance de 250 metros dos dispositivos e tráfego
CBR com pacotes de 512 Bytes, sendo transmitidos 4 pacotes por segundo. Os parâmetros
qualitativos adotados foram
taxa de entrega dos pacotes, retardo de transmissão, carga de
roteamento
e
consumo de energia dos dispositivos.
As simulações onde o nível de mobilidade
varia (4, 8, 12, 16, 20 e 24m/s) apresentam comunicação entre 30 dispositivos móveis, com
tempo de pausa de 10 segundos. Já nas simulações que alteram o número de fluxos
conversacionais (de 10 a 80), a velocidade máxima é de 4m/s, sendo o número de dispositivos
e o tempo de pausa os mesmos. As outras simulações modificam apenas o número de
82
dispositivos (de 20 a 70), sendo o número de fluxos conversacionais igual à quantidade de
dispositivos. Como resultados, o trabalho considera o protocolo DSDV mais escalável do que
o AODV em relação ao tamanho da rede, sendo que o incremento na mobilidade não afeta
muito o desempenho dos protocolos. Além disso, o DSDV apresenta um comportamento
melhor do que o AODV em redes mais densas, com um tráfego maior na rede.
O trabalho realizado por [Johansson 99] apresenta um estudo sobre o desempenho dos
protocolos de roteamento
ad hoc
(DSDV, AODV e DSR) em cenários randômicos. As
simulações foram realizadas em um espaço de 1000m x 1000m, com 50 dispositivos móveis,
a 250 metros de raio de alcance um do outro, durante 250 segundos. A taxa de transmissão é
de 2Mbps. O modelo de comunicação utiliza tráfego CBR, com pacotes de 64 Bytes para 15
fluxos conversacionais. O tempo de pausa definido foi de 1 segundo. Os pontos de
variabilidade são a mobilidade dos dispositivos (velocidade máxima de 0 ate 20m/s) e a
quantidade de pacotes transmitidos por segundo (de 5 a 20 pacotes por segundo). Os
parâmetros qualitativos definidos foram o retardo de transmissão e a vazão. Os resultados
mostram que os protocolos AODV e DSR apresentam um ótimo desempenho em
praticamente todos os cenários simulados, enquanto que o DSDV tem sérios problemas à
medida que aumenta o nível de mobilidade dos dispositivos. Este trabalho recomenda o
protocolo DSR em cenários de rede, onde as rotas tenham um número limite de dispositivos
intermediários e onde é crucial a quantidade de pacotes de roteamento. Já o protocolo AODV
aparece como melhor solução em redes com um número de dispositivos intermediários para
as rotas e que necessitam de uma carga de roteamento bem menor em termos de bytes.
Um outro trabalho realizado por [Perkins 00] apresenta um estudo comparativo dos
principais protocolos de roteamento reativos (AODV e DSR). Os valores de taxa de
transmissão e raio de alcance são os mesmos definidos pelos trabalhos anteriores. As
simulações utilizam duas configurações de espaço: 1500m x 300m com 50 dispositivos
móveis e 220m x 600m com 100 dispositivos móveis. O modelo de mobilidade adotado foi o
randômico, com uma velocidade máxima entre 0 e 20m/s e o tempo de pausa variando entre 0
e 500 segundos. O tempo de simulação para 50 e 100 dispositivos foi, respectivamente, de
900 e 500 segundos. O modelo de tráfego utilizado foi o CBR, com pacotes de 512 Bytes. Os
principais pontos de variabilidade para estas simulações são os níveis de mobilidade dos
dispositivos (de acordo com os tempos de pausa definidos), o número de fluxos
conversacionais (10, 20, 30 e 40 origens de tráfego e uma taxa de 4 pacotes por segundo, para
a simulação de 50 dispositivos móveis; e 10, 20 e 40 origens de tráfego para uma taxa de 4
83
pacotes por segundo, na simulação de 100 dispositivos móveis) e a quantidade de informações
enviadas por segundo em Kbps (com 10 origens, a rede satura com 325Kbps para o DSR e
700Kbps para o AODV; já para 40 origens, a rede satura muito antes para os dois protocolos,
são esses valores, respectivamente, 300Kbps e 150Kbps). Os parâmetros qualitativos adotados
foram taxa de entrega dos pacotes, retardo de transmissão e carga de roteamento. Os
resultados mostram que apesar de compartilhar a mesma abordagem reativa, estes protocolos
apresentam muitas diferenças. Em geral, o DSR se adapta melhor em cenários de rede com
um número menor de dispositivos móveis, baixo tráfego na rede e níveis de mobilidade mais
baixos. O baixo desempenho do protocolo DSR em termos de retardos de transmissão e vazão
atribui-se ao uso da
cache
e da ausência de um mecanismo para expirar rotas antigas e
determinar quais rotas são mais recentes em virtude da disponibilidade de múltiplas rotas para
um mesmo destino.
Outros trabalhos foram desenvolvidos com o objetivo de analisar o desempenho dos
protocolos de roteamento
ad hoc
. No entanto, nenhum deles compara os protocolos DSDV,
AODV, DSR e TORA entre si, através do simulador de redes NS. O estudo realizado por
[Amorim 02] apresenta como objetivo investigar o impacto da utilização de Diferenciação de
Serviços nos protocolos de roteamento. Foram usadas duas técnicas de diferenciação,
denominadas Diferenciação de Serviços por Variação no DIFS e Diferenciação de Serviços
por Variação na Função
Backoff
aplicadas nos protocolos DSR e DSDV. Os resultados
mostram o desempenho dos protocolos originais e dos protocolos modificados com as
técnicas de diferenciação através da ferramenta NS.
Como se pode perceber, nenhuma das análises comparativas para estes protocolos de
roteamento considera um cenário híbrido de redes
ad hoc
e os requisitos de uma aplicação de
videofone. Os parâmetros qualitativos são semelhantes, porém, considerando os requisitos de
aplicações de videofone, as simulações adotam valores completamente diferentes em termos
de raio de alcance, taxa de transmissão, tamanho de rede, número de dispositivos (móveis
e/ou fixos), tamanho dos pacotes de dados e número de pacotes transmitidos por segundo. O
modelo de mobilidade também apresenta diferenças, os dispositivos móveis não utilizam
tempos de pausa e velocidades randômicas. Como um dos objetivos do trabalho seria avaliar
os efeitos da mobilidade sobre aplicações de videofone, os tempos de pausa poderiam
mascarar estes efeitos.
Os resultados foram semelhantes em alguns aspectos, mas como conclusão pré-
eliminar pode-se afirmar que dos 3 protocolos simulados, apenas o AODV e o DSR
84
apresentam os requisitos necessários para uma aplicação de videofone, em praticamente todos
os cenários. No entanto, estes ótimos resultados apresentam limites quanto ao nível de
mobilidade dos dispositivos e o número de sessões de videofone. Diferentemente dos
resultados dos outros trabalhos, onde em geral os protocolos AODV e DSR sempre
apresentavam resultados satisfatórios para todos os cenários simulados.
85
Capítulo 7
Considerações Finais
Considerando os 3 protocolos de roteamento (DSDV, AODV e DSR), os 8 cenários (3x3 até
10x10) de rede, os 3 níveis de mobilidade (baixa, moderada e alta) e as 4 combinações de
sessões de videofone (1, 2, 4 e 8), este trabalho sintetiza os resultados de um total de 216
simulações (o protocolo DSDV foi simulado somente para cenários com uma sessão de
videofone). Estas simulações geraram, em conjunto, cerca de 50GBytes de informações de
saída compactadas. Por sua vez, estas saídas foram processadas por um
script awk
,
desenvolvido especialmente para este estudo, que gerou diversos gráficos comparativos dos
parâmetros quantitativos considerados.
A Tabela 7.1 apresenta, de forma resumida, os resultados dos diversos parâmetros
quantitativos avaliados sob condições de tráfego de aplicações de videofone em cenários
híbridos de redes móveis
ad hoc
. Para cada nível de mobilidade dos dispositivos e números de
sessões de videofone, a tabela mostra se os requisitos da aplicação de videofone foram
atendidos ou não.
Tabela 7.1 – Resultados das Simulações
Mobilidade Baixa
(número de sessões)
Mobilidade Moderada
(número de sessões)
Mobilidade Alta
(número de sessões)
1
2
4
8
1
2
4
8
1
2
4
8
DSDV
Não
-
-
-
Não
-
-
-
Não
-
-
-
AODV
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Não
DSR
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Sim
Não
Como se pode observar na Tabela 7.1, o protocolo DSDV não atende aos requisitos de
uma aplicação de videofone nem mesmo nos cenários de mobilidades baixa, moderada e alta
com uma única sessão de videofone. A taxa de entrega nestes cenários é bem menor do que
86
aquela definida para esta classe de aplicação (95%). Considerando que este trabalho define a
taxa de entrega como um dos parâmetros quantitativos que define a condição de parada do
conjunto de simulações de um protocolo de roteamento
ad hoc
, o DSDV não foi simulado
para os cenários subseqüentes
.
Os protocolos AODV e DSR apresentam comportamento similar para todo o conjunto
de simulações. Nos cenários de mobilidades baixa, moderada e alta, com 1, 2 e 4 sessões de
videofone, estes protocolos satisfazem os requisitos de uma aplicação de videofone. Já nos
cenários com 8 sessões, somente nos níveis de mobilidade baixa e moderada que os resultados
são satisfatórios. Os cenários de mobilidade alta com 8 sessões de videofone apresentam taxas
de entrega inferior à 95% desde o menor cenário híbrido configurado (cenário 3x3).
Como primeira conclusão, pode-se perceber claramente que, no geral, os protocolos
reativos (AODV e DSR) são superiores ao pró-ativo (DSDV). O procedimento de estabelecer
rotas sob demanda é a principal justificativa para o bom comportamento desta classe de
protocolos. No entanto, assim como afirmam os trabalhos sobre protocolos pró-ativos
[Perkins 94, Chiang 97, Murthy 97] em relação a disponibilização imediata de rotas, os
resultados deste trabalho comprovam que esta classe de protocolos apresenta os menores
retardos de entrega.
Por outro lado, o DSDV apresenta as maiores taxas de perdas de pacotes,
principalmente quando o nível de mobilidade dos dispositivos e o tamanho dos cenários
aumentam. Conclui-se, então, que os protocolos pró-ativos apresentam dificuldades
consideráveis em manter rotas válidas, principalmente em redes com topologias dinâmicas.
No entanto, o trabalho [Lu 03] apresenta um estudo onde os protocolos pró-ativos são mais
escaláveis do que os reativos, em termos de tamanho de rede, o que justifica a necessidade de
simulações para a escolha de um determinado protocolo em um cenário de rede específico e
para uma dada classe de aplicação.
Os protocolos AODV e DSR apresentam comportamentos bastante similares em
praticamente todos os cenários simulados. Entretanto, existem diferenças que tornam o
AODV mais adequado a cenários maiores e com níveis de mobilidade mais altos do que o
DSR, embora adotem o mesmo comportamento reativo. Acreditamos que a utilização de
mecanismos que expirem rotas velhas e diferencie as rotas mais novas daquelas mais
desatualizadas (assim como o número de seqüência adotado pelo AODV), poderia tornar o
DSR um protocolo tão escalável e dinâmico quanto o AODV.
87
Por outro lado, considerando o número de sessões de videofone estabelecido entre os
dispositivos móveis, normalmente o protocolo DSR apresenta um comportamento mais
adequado do que o AODV. Este comportamento pode ser explicado pelo mecanismo de
roteamento na origem e a “escuta” em modo promíscuo dos pacotes pelos dispositivos
móveis. Todavia, o roteamento na origem dificulta a adaptação do protocolo DSR a cenários
maiores e a níveis de mobilidade mais altos destes dispositivos.
Como recomendação, considerando os diversos parâmetros quantitativos avaliados de
acordo com os requisitos de uma aplicação de videofone, os protocolos AODV e DSR
apresentam resultados satisfatórios em praticamente todas as simulações, sendo, portanto os
mais adequados para esta classe de aplicação em um cenário híbrido de redes
ad hoc
. No
entanto, apesar dos bons resultados obtidos durante quase todas as aplicações, estes
protocolos apresentam uma taxa de entrega inferior (em torno de 86 a 94%) àquela definida
para este tipo de aplicação (95%), em todos os cenários de mobilidade alta com 8 sessões de
videofone, o que poderia provocar efeitos negativos na apresentação do vídeo.
Conclui-se então que, apesar dos ótimos resultados obtidos pelos protocolos de
roteamento AODV e DSR para aplicações de videofone, tais protocolos apresentam
limitações quanto ao nível de mobilidade dos dispositivos e, principalmente, ao número de
sessões de videofone estabelecido entre tais dispositivos.
7.1 Trabalhos Futuros
Muitos outros aspectos de análise podem contribuir para tornarem mais completo o
estudo sobre o desempenho de protocolos de roteamento para aplicações de videofone em
redes de comunicação
ad hoc
. Os cenários híbridos de redes
ad hoc
definidos neste trabalho
permitem a comunicação direta entre os pontos de acesso apenas nas direções horizontais e
verticais, considerando que estas distâncias são iguais ao raio de alcance de transmissão (R).
No entanto, como se pode observar na Figura 4.2 (ver Capítulo 4), utilizada para exemplificar
o cenário de rede 3x3, a distância na diagonal entre os pontos de acesso é igual a 2
1/2
R. Sendo
esta distância maior do que o próprio raio de alcance, tais dispositivos não se comunicam
diretamente devido a ausência de rotas na diagonal.
Considerando esta limitação nos cenários híbridos de redes
ad hoc
, uma primeira
possibilidade é realizar um novo conjunto de simulações que permita a definição de rotas na
88
diagonal, o que pode melhorar a taxa de entrega dos pacotes e, conseqüentemente, o retardo
de entrega. Sendo assim, aumenta a probabilidade de um número maior de pacotes de dados
ser entregue com até 400ms, requisito este importante para aplicações de videofone.
Além disso, como forma de analisar abordagens completamente diferentes, outros
protocolos de roteamento podem ser adotados para este novo conjunto de simulações: OLSR
(
Optimized Link State Routing
) [Clausen 03], TBRPF (
Topology Broadcast based on Reverse-
Path Forwarding
) [Ogier 04] e ZRP (
Zone Routing Protocol
) [Haas 98].
89
REFERÊNCIAS
[Amorim 02]
Amorim, G. F.,
Análise de Desempenho de Protocolos de Roteamento
com Diferenciação de Serviços em Redes de Comunicação Móvel Ad
Hoc
. Dissertação de Mestrado. Instituto Militar de Engenharia –
Secretaria de Ciência e Tecnologia. Rio de Janeiro, 2002.
[Broch 98]
Broch, J., et al,
A Performance Comparison of Multi-Hop Wireless Ad
Hoc Network Routing Protocols,
4
th
Annual ACM/IEEE International
Conference on Mobile Computing and Networking (MobiCom’98),
Dallas, October 1998.
[Camara 99]
Camara, D., Loureiro, A.,
Redes de Computação Móvel Ad Hoc.
Jornada de Atualização em Informática, Rio de Janeiro, 1999.
[Campos 05]
Campos, G. M. M., Elias, G.,
Performance Issues of Ad Hoc Routing
Protocols in a Network Scenario used for VideoPhone Applications.
Hawaii International Conference on System Sciences (HICSS-38),
January 2005.
[Chen 02]
Chen, L., et al,
Power Resource Cooperation Control Considering
Wireless QoS for CDMA Packet Mobile Communications Systems.
13
th
IEEE International Symposium on Personal, Indoor and Mobile Radio
Communications, vol.3, pp. 1092-1096, 2002.
[Cherriman 96]
Cherriman, P., Hanzo, L.,
Robust H.263 Video Transmission over
Mobile Channels in Interference Limited Environments
. 1
st
IEEE
Wireless Video Communications Workshop, Loughborough, UK,
1996, pp. 1-7.
[Chiang 97]
Chiang, C.-C.,
Routing in Clustered Multihop,Mobile Wireless
Networks with Fading Channel
, IEEE Singapore International
Conference on Networks (SICON'97), April 1997, pp.197-211.
[Chung 05]
Chung, J.; Claypool, M.,
Ns by Example (Tutorial).
Disponível em:
http://nile.wpi.edu/NS. [capturado em 2005]
[Clausen 03]
Clausen, T., et al,
Optimized Link State Routing Protocol (OLSR).
RFC 3626, October 2003.
[Close 95]
Close, D. B., et al,
The AWK Manual.
Edition 1.0, December 1995.
[CMU 03]
The CMU Monarch Project,
The CMU Monarch Project´s Wireless
and Mobility Enhancements to ns,
November 2003. Disponível em
http://www.monarch.cs.cmu.edu. [capturado em 2004].
90
[Corson 99]
Corson, S., Macker, J.,
Mobile Ad Hoc Networking (MANET): Routing
Protocol Performance Issues and Evaluation Considerations
, RFC
2501, January 1999.
[Das 00]
Das, S. R., et al,
Simulating-based performance evaluation of routing
protocols for mobile ad hoc networks
. Mobile Networks and
Applications, 5:179-189, 2000.
[Forman 94]
Forman, G. H., Zahorjan, J.,
The Challenges of Mobile Computing.
IEEE Computer, 27(6), April 1994.
[Giordano 01]
Giordano, S.
Mobile ad-hoc networks.
In Handbook of Wireless
Network and Mobile Computing, ed. I. Stojmenovic. John Wiley &
Sons, 2001.
[GloMoSim 04]
GloMoSim Manual – Global Mobile Information Systems Simulation
Library. Disponível em
http://pcl.cs.ucla.edu/projects/glomosim.
[capturado em 2004].
[Haas 98]
Haas, Z., et al,
The Performance of Query Control Schemes for the
Zone Routing Protocol
. ACM SIGCOMM, Vancouver, Canada,
September 1998.
[IEEE 99]
IEEE,
Wireless LAN medium Access control (MAC) and physical layer
(PHY) specifications.
IEEE Standard 802.11, 1999. Disponível em
http://grouper.ieee.org./groups/802/11/ [capturado em 2004].
[IEEE 99a]
IEEE,
Wireless LAN medium access control (MAC) and physical layer
(PHY) specifications: High-speed physical layer in the 5 GHz band.
IEEE Standard 802.11a, 1999. Disponível em:
http://grouper.ieee.org/groups/802/11. [capturado em 2004].
[IEEE 99b]
IEEE,
Wireless LAN medium access control (MAC) and physical layer
(PHY) specifications: Higher-speed physical layer in the 2.4 GHz
band.
IEEE Standard 802.11b, 1999. Disponível em:
http://grouper.ieee.org/groups/802/11. [capturado em 2004].
[ISI 05]
ISI, Information Sciences Institute.
The Network Simulator-ns-2.
Disponível em:
http://www.isi.edu/nsnam/ns. [capturado em 2005]
[ITU-T 98]
ITU-T,
Recommendation H.263: Video Coding for Low Bit Rate
Communication
, International Telecommunications Union, February
1998.
[Johnson 94]
Johnson, D. B.,
Routing in Ad Hoc Networks of Mobile Hosts,
Workshop on Mobile Computing Systems and Applications, pp. 158-
163, December 1994.
91
[Johnson 04]
Johnson, D., et al,
The Dynamic Source Routing Protocol for Mobile
Ad Hoc Networks (DSR),
Internet Draft draft-ietf-manet-dsr-10.txt,
July 2004.
[Johansson 99]
Johansson, P., et al,
Scenario-based Performance Analysis of Routing
Protocols for Mobile Ad Hoc Networks
. 5
th
Annual ACM/IEEE
International Conference on Mobile Computing and Networking
(MobiCom’99), Seattle, August 1999.
[Kaminski 01]
Kaminski, S.,
Tecnologhy overview of HomeRF 2.0.
May 2001.
Disponível em
http://www.homenethelp.com/web/explain/about-
homerf-2.asp. [capturado em 2004].
[Lu 03]
Lu, Y. at al,
Study of Distance Vector Routing Protocols for Mobile Ad
Hoc Networks
, IEEE International Conference on Pervasive
Computing and Communications (PerCom), Dallas, March 2003.
[Maltz 99]
Maltz, D., et al,
The effects of on-demand behaviour in routing
protocols for multihop wireless ad hoc networks.
IEEE Journal on
Selected Areas in Communication, 1999.
[MANET 04]
MANET,
Mobile Ad Hoc Networks.
Disponível em
http://www.ietf.org./html.charters/manet-charter.html. [capturado em
2004].
[Mehaoua 99]
Mehaoua, A., Boutaba, R.,
The Impacts of Errors and Delays on the
Performance of MPEG2 Video Communications
. ICASSP 99, Arizona,
March 1999.
[Miki 97]
Miki, M. H., et al,
Low-Power H.263 Video CoDec Dedicated to
Mobile Computing
. International Symposium on Low Power
Electronics and Design, August 1997, pp. 80-83.
[Miller 01]
Miller, M.,
Descobrindo o Bluetooth
. Tradução de Altair Dias Caldas e
Cláudio Belleza Dias. Rio de Janeiro: Campus, 2001. 289 páginas.
Título original: Discovering Bluetooth.
[Murthy 96]
Murthy, S., Garcia-Luna-Aceves, J.J.,
An Efficient Routing Protocol
Wireless Networks
, ACM Mobile Networks and Applications Journal,
Special Issue on Routing in Mobile Communication Networks,
October 1996, pp. 183-97.
[Ogier 04]
Ogier, R., et al,
Topology Dissemination Based on Reverve-Path
Forwarding (TBRPF).
RFC 3684, February 2004.
[Park 97]
Park, V. D., and Corson, M. S.,
A Highly Adaptive Distributed Routing
Algorithm for Mobile Networks,
16
th
Annual Joint Conference of the
IEEE Computer and Communications Societies (INFOCOM´97),
92
Kobe, Japan, April 1997.
[Perkins 94]
Perkins, C., Bhagwat, P.,
Highly Dynamic Destination-Sequenced
Distance-Vector Routing (DSDV) for Mobile Computers
. ACM
Special Interest Group on
Data Communications (SIGCOMM), October 1994.
[Perkins 00]
Perkins, C., et al,
Performance Comparison of Two On-Demand
Routing Protocols for Ad Hoc Networks.
19
th
Annual Joint Conference
of the IEEE Computer and Communications Societies
(INFOCOM 200), Israel, March 2000.
[Perkins 01]
Perkins, C.,
Ad Hoc Networking
, 1
st
Edition. Addison-Wesley
Professional, 2001. 384 pages.
[Perkins 03]
Perkins, C., et al,
Ad-Hoc On-Demand Distance Vector (AODV)
Routing
, RFC 3561, July 2003.
[Royer 99]
Royer, E. .M., Toh, C.-K.,
A Review of Current Routing Protocols for
Ad-Hoc Mobile Wireless Networks
. IEEE Personal Communications
Magazine, April 1999, pp. 46-55.
[Santos 03]
Santos, A. S.,
Estratégias de Hand-off com Balanceamento de Carga
para Computação Móvel.
Dissertação de Mestrado. Universidade de
São Paulo – Instituto de Matemática e Estatística. São Paulo, 2003.
[Satyanarayanan 96]
Satyanarayanan, M.,
Fundamental Challenges in Mobile Computing.
15
th
Annual ACM Symposium on Principles of Distributed
Computing, 1996.
[Shankar 94]
Shankar, K.; et al,
Design and Implementation of MaRS: A Routing
Testbed.
Journal of Internetworking – Research and Experience, vol5,
n° 1, pp 17-41, March 1994.
[Smith 01]
Smith, C., Collins, D.,
3G Wireless Networks.
McGraw-Hill Telecom
Professional, 2001. 500 páginas.
[Soares 95]
Soares, L. F. G, Lemos, G e Colcher, S.,
Redes de Computadores. Das
LANs, MANs e WANs às Redes ATM.
Rio de Janeiro: Editora Campus,
1995. 705 páginas.
[Tanembaum 03]
Tanembaum, A. S.,
Redes de Computadores.
4ª Edição. Rio de
Janeiro: Editora Campus, 2003. 955 páginas.
[Wong 00]
Wong, T. C., Mark, J. W., Chua, K. C.,
Delay Jitter Performance of
Video Traffic in a Cellular Wireless ATM Network
. 3
rd
ACM
International Workshop on Wireless Mobile Multimedua, Boston,
2000, pp 101-107.
93
ANEXO
Este trabalho apresenta como anexo os resultados obtidos durante as simulações no formato
de gráficos e tabelas, assim como os códigos
tcl
e
awk
utilizados para gerar estas informações
de saída. Para não sobrecarregar o trabalho com um número elevado de páginas, este anexo
foi inserido no formato digital (cd-rom). Este CD armazena um arquivo *.pdf com os diversos
Apêndices (total de oito, de A até H). No início deste arquivo existe um sumário navegável
que facilita a consulta do leitor a resultados específicos.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
