RouteSpray: Um algoritmo deroteamento de multiplas copiasbaseado em rotas de transito
Maurıcio Jose da SilvaUniversidade Federal de Ouro Preto
Dissertacao submetida aoInstituto de Ciencias Exatas e Biologicas
Universidade Federal de Ouro Pretopara obtencao do tıtulo de Mestre em Ciencia da Computacao
2
Catalogação: www.sisbin.ufop.br
S586r Silva, Maurício Jose da. RouteSpray [manuscrito]: um algoritmo de roteamento de multiplas copiasbaseado em rotas de trâ / Maurício Jose da Silva. - 2014. 62f.: il.: color; grafs; tabs.
Orientador: Prof. Dr. Ricardo Augusto Rabelo Oliveira.
Dissertação (Mestrado) - Universidade Federal de Ouro Preto. Instituto deCiências Exatas e Biológicas. Departamento de Computação. Programa de PósGraduação em Ciências da Computação. Área de Concentração: Ciências da Computação.
1. Engenharia de trafego. 2. Redes veiculares. 3. TCP/IP (Protocolo de redede computação). 4. . I. Oliveira, Ricardo Augusto Rabelo. II. UniversidadeFederal de Ouro Preto. III. Titulo.
CDU: 004.738.5:625.7
Dedico este trabalho a Deus e aos meus pais Sandra e Vicente, pessoas de suma
importancia em minha vida.
i
ii
RouteSpray: Um algoritmo de roteamento de multiplas
copias baseado em rotas de transito
Resumo
Redes veiculares sao um tipo especial de redes wireless que ganharam a atencao dos
pesquisadores nos ultimos anos. Protocolos de roteamento para esse tipo de rede tem
que lidar com diversos desafios como alta mobilidade, altas velocidades e frequentes des-
conexoes na rede. Neste artigo e proposto o RouteSpray, um algoritmo de roteamento
veicular que, alem de utilizar as rotas dos veıculos para tomar as decisoes de roteamento,
tambem utiliza a pulverizacao controlada para encaminhar multiplas copias de mensa-
gens, garantindo melhores taxas de entrega sem sobrecarregar a rede. Os resultados
dos experimentos mostram que o RouteSpray entregou 13,12% mensagens a mais do que
outras propostas da literatura e manteve a ocupacao do buffer 73,11% menor.
iii
iv
RouteSpray: A Multiple-Copy Routing Algorithm Based
on Transit Routes
Abstract
Vehicular networks represent a special type of wireless network that has gained the
attention of researchers over the past few years. Routing protocols for this type of
network must face several challenges, such as high mobility, high speeds and frequent
network disconnections. This paper proposes a vehicular routing algorithm called Rou-
teSpray that in addition to using vehicular routes to help make routing decisions, uses
controlled spraying to forward multiple copies of messages, thus ensuring better deli-
very rates without overloading the network. The results of experiments performed in
this study indicate that the RouteSpray algorithm delivered 13.12% more messages than
other algorithms reported in the literature. In addition, the RouteSpray algorithm kept
the buffer occupation 73.11% lower.
v
vi
Declaracao
Esta dissertacao e resultado de meu proprio trabalho, exceto onde referencia explıcita e
feita ao trabalho de outros, e nao foi submetida para outra qualificacao nesta nem em
outra universidade.
Maurıcio Jose da Silva
vii
viii
Agradecimentos
A Deus, por me acompanhar em mais esta caminhada.
A meus pais e a minha namorada, pela paciencia e pelo apoio incondicional.
Aos meus irmaos e amigos, pelos conselhos e por ouvir minhas reclamacoes.
Aos professores, pelos ensinamentos transmitidos.
Ao Ricardo Rabelo, meu orientador.
A UFOP e ao IMobilis, pela infraestrutura.
A Seva e Conselho Nacional de Desenvolvimento Cientıfico e Tecnologico (CNPq).
A todos que contribuıram direta ou indiretamente para a realizacao deste trabalho.
Muito Obrigado.
ix
x
Sumario
Lista de Figuras xv
Lista de Tabelas xvii
Nomenclatura 1
1 Introducao 3
1.0.1 Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.0.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.0.3 Contribuicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Referencial Teorico 9
2.1 Redes DTN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Arquitetura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Roteamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Redes Veiculares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2 Caracterısticas das redes VANETs . . . . . . . . . . . . . . . . . . 15
2.2.3 Pilha de protocolos . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Aplicacoes para VANET . . . . . . . . . . . . . . . . . . . . . . . 19
xi
2.3 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Trabalhos Relacionados 23
3.1 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 Protocolo de Roteamento Route Spray 31
4.1 Algoritmo RouteSpray . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.1 Utilizacao de Rotas . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1.2 Binary Spray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5 VeNeM - Gerador De Mobilidade Veicular Real 37
5.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Simulacoes em Redes Veiculares . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.1 Modelos de mobilidade . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.2 Evolucao dos simuladores . . . . . . . . . . . . . . . . . . . . . . 39
5.2.3 Discussao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3 Simuladores existentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3.1 BonnMotion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3.2 VanetMobiSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3.3 Veins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3.4 Framework de Mobilidade veicular . . . . . . . . . . . . . . . . . 43
5.3.5 VeNeM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.4 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6 Resultados e Discussoes 49
xii
6.1 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.2.1 Taxa de entrega de mensagens . . . . . . . . . . . . . . . . . . . . 51
6.2.2 Ocupacao dos buffers . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.2.3 Quantidade de mensagens enviadas na rede . . . . . . . . . . . . . 53
6.2.4 Atraso medio de entrega das mensagens . . . . . . . . . . . . . . . 54
7 Conclusoes 57
7.1 Conclusoes e Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . 57
Referencias Bibliograficas 59
xiii
xiv
Lista de Figuras
2.1 A camada de agregacao. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Contato previsıvel em uma rede rural. . . . . . . . . . . . . . . . . . . . . 12
3.1 Exemplo do calculo do NP do destino do pacote. . . . . . . . . . . . . . . 29
4.1 Rotas pre-estabelecidas para tres veıculos. . . . . . . . . . . . . . . . . . 34
5.1 Modelo de um grafo de Voronoi. . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 Framework de Gerenciamento de rede movel. . . . . . . . . . . . . . . . . 43
5.3 Rota entre a Estacao central de metro – Belo Horizonte e Paroquia de
Nossa Senhora de Fatima – Belo Horizonte (Retirada do Google Maps
em 02/09/2014). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.1 Mensagens entregues na rede. . . . . . . . . . . . . . . . . . . . . . . . . 52
6.2 Ocupacao do buffer : comparacao entre os tres algoritmos . . . . . . . . . 53
6.3 Ocupacao do buffer entre os algoritmos que utilizam a tecnica de “spray”. 54
6.4 Mensagens enviadas na rede. . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.5 Tempo medio de entrega de mensagens. . . . . . . . . . . . . . . . . . . . 56
xv
xvi
Lista de Tabelas
3.1 Valores estimados de L para uma rede de 100 nos. . . . . . . . . . . . . . 27
5.1 Visao geral das classes de modelos de mobilidade . . . . . . . . . . . . . 41
6.1 Parametros utilizados na simulacao . . . . . . . . . . . . . . . . . . . . . 50
xvii
xviii
Lista de Algoritmos
4.1 Pseudo-codigo RouteSpray . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
xix
xx
“”O proximo grande salto evolutivo da humanidade sera a descoberta de que cooperar e
melhor que competir””
— Prof. Pietro Ubaldi
xxi
xxii
Nomenclatura
DTN Delay Tolerant Network
IPN Interplanetary Networking
DTNRG Delay Tolerant Network Research Group
STI Sistemas de Transporte Inteligentes
VANET Vehicular Ad Hoc Network
V2V Veıculo para veıculo
V2I Veıculo para infra estrutura
MANET Mobile ad hoc Network
NS Navigation System
DSRC Dedicated Short-Range Communication
BCH Basic Chanell
VTP Veicular Transport Protocol
MCTP Mobile Control Transport Protocol
QoS Qualidade de servico
VITP Veicular Information Transfer Protocol
EI Estacoes de Informacao
ETA Estimated Time to Arrive
METD Minimum Estimated Time to Delivery
NP Nearest Point
1
2
Capıtulo 1
Introducao
Em 1923 foi desenvolvida por um policial australiano uma forma de comunicacao bidi-
recional entre carros (?). Essa tecnica foi aprimorada com a segunda guerra mundial,
facilitando a comunicacao entre as tropas. Com o avanco da tecnologia, os equipamen-
tos de radio se tornaram mais comuns em carros, atualmente os veıculos sao sistemas
interligados possibilitando o seu monitoramento, controle e gerenciamento.
Com o grande aumento da frota de veıculos presentes nas rodovias, surgiu a necessi-
dade de comunicacao entre eles, com isto, primeiramente surgiram os semaforos, depois
dispositivos que indicavam direcao nos veıculos. Grande parte dessa comunicacao ge-
ralmente esta presente nas rodovias, e e compartilhado entre todos os veıculos. Com
a constante evolucao das redes moveis, e com a possibilidade de trocar informacoes a
qualquer momento e a qualquer hora possibilitando uma grande variedade de aplicacoes
em redes veiculares, este cenario mudou. Atualmente redes veiculares constituem objeto
de pesquisa em ascendencia, o que fez com que esse tipo de rede ganhasse a atencao dos
pesquisadores nos ultimos anos.
Redes veiculares possuem diversas aplicacao, e podem oferecer, a partir dos Sistemas
de Transporte Inteligentes (ITS), servicos como: (i) assistencia ao motorista, auxiliando-
o durante seu trajeto informando-o sobre condicoes do transito, pontos de interesse
(abastecimento, alimentacao, etc); (ii) disseminacao de informacoes, propagando para
regioes geograficas especificas informacoes sobre acidentes e propagandas, por exem-
plo; e (iii) entretenimento, permitindo aos passageiros de um veıculo uma viagem mais
agradavel (Taysi & Yavuz 2012).
3
4 Introducao
1.0.1 Justificativa
Redes wireless sao redes cujo meio fısico de comunicacao e o ar, ou seja, nao ha a
necessidade de fios para conectar dois ou mais nos permitindo que se comuniquem. Redes
veiculares constituem um tipo especial de redes wireless, com alguns desafios a serem
enfrentados. Em redes wireless, geralmente os nos sao conectados a partir de um Ponto
de Acesso, e esse ponto de acesso e responsavel por rotear e entregar a mensagem para
o nos de destino. Implantar uma infra estrutura as margens da rodovia para permitir
tal topologia teria um alto custo, o que faz com que surja a necessidade de formacao de
uma rede completamente ad hoc (rede entre os nos).
Apesar de redes VANETs serem um subtipo de redes wireless, elas possuem suas
proprias caracterısticas, como exemplo podemos citar a alta mobilidade dos veıculos, que
provoca frequentes desconexoes entre os nos da rede. Como impacto, tal caracterıstica
particiona a rede e impossibilita a utilizacao dos protocolos de roteamento feitos para
redes ad hoc. Isso, porque os algoritmo projetados para serem aplicados a redes ad
hoc assumem a existencia de um caminho fim a fim antes de iniciar a transmissao de
dados, o que pode nunca acontecer em uma rede veicular. Para resolver tal problema, os
algoritmos de roteamento para VANETs utilizam a tecnica de store-carry-and-foward,
que faz com que mensagem seja armazenada em cada no ate que ela atinja o destino.
Porem, algumas caracterısticas das redes VANETs podem ser utilizadas para au-
xiliar no roteamento, como por exemplo, padroes de mobilidade limitados pelas rodo-
vias, tendencia dos veıculos se locomoverem em grupos e a integracao de sensores aos
veıculos (Toor, Muhlethaler & Laouiti 2008) (Li & Wang 2007). Os padroes de mo-
bilidade limitados pelas rodovias permitem que os algoritmos de roteamento consigam
prever, mesmo que com uma margem de erro, as possıvel direcoes que os veıculos irao
seguir, e tal caracterıstica pode ser utilizada para aprimorar o processo de roteamento.
Ja a tendencia dos veıculos se locomoverem em grupos auxilia por aumentar a area
de alcance de uma mensagem. Mesmo que por um tempo imprevisto e possivelmente
pequeno, o fato dos veıculos se moverem em uma mesma direcao e com velocidades
constantes faz com que sejam formados pequenos clusters em que todos os nos estejam
conectados entre si. Essa caracterıstica abre um campo de pesquisa relacionado com
roteamento baseados em clusters (Luo, Zhang & Hu 2010), que nao constituem objetos
de estudo dessa dissertacao. Por fim, outra caracterıstica que beneficia o roteamento e
a integracao de sensores aos veıculos. A cada dia se torna mais comum veıculos serem
fabricados com sensores que aprimoram a experiencia com o usuarios, os dados destes
Introducao 5
sensores podem ser utilizados para aferir informacoes que podem auxiliar na tomada de
decisoes a ate mesmo no roteamento. Como exemplo, os sensores de temperatura dos
veıculos podem ser utilizados para aferir com alta precisao a temperatura media de uma
determinada regiao. Ou utilizando o sensor de combustıvel o algoritmo pode calcular
uma rota de forma que o veıculo passe proximo a um posto antes que o combustıvel
termine. Enfim, uma grande variedade de aplicacoes surgirao nos proximos anos.
Existem varios algoritmos de roteamento propostos para VANETs, mas os recentes
avancos tecnologicos e sua popularizacao como aconteceu com o GPS, por exemplo,
abriram a possibilidade de propor protocolos ainda mais eficientes. Isso, porque um dos
maiores desafio em rotear uma mensagem por uma rede dinamica, e prever a mobilidade
do no de forma que a mensagem seja propagada em direcao ao destino, ou ela podera se
perder e nunca sera entregue. Se veıculos possuem informacoes de localizacao, explora-las
para aprimorar o processo de roteamento tem se tornado uma das principais premissas
entre as novas propostas de roteamento. Por esse motivo tornou-se objeto principal de
pesquisa desse estudo.
1.0.2 Objetivos
Varios protocolos que objetivam realizar o roteamento em redes VANETs tem sido apre-
sentados. A principal diferenca entre esses protocolos sao as informacoes que eles con-
sideram para realizar o roteamento (historico de contato entre os nos, informacoes de
localizacao, etc) e a estrategia que utilizam para encaminhar a mensagem (numero de
replicas geradas por mensagem). Contudo, existe um consenso entre a comunidade ci-
entıfica de que nao existe um protocolo de roteamento ideal para todos os cenarios. O
protocolo RouteSpray tem o objetivo de ser aplicado em cenarios onde tem-se conhe-
cimento previo das rotas dos veıculos, caracterıstica que tornou-se comum nos dias de
hoje devido a popularizacao dos dispositivos de navegacao, principalmente se considerar-
mos frotas com mobilidade controlada, como onibus, caminhoes e taxis. Tal protocolo
foi projetado para utilizar as rotas dos veıculos para tomar as decisoes de roteamento,
sendo essa a unica premissa exigida.
1.0.3 Contribuicoes
Neste estudo e proposto o algoritmo RouteSpray. Tal algoritmo combina quatro concei-
tos importantes para tomar as decisoes de roteamento, sendo: (i) utilizacao da tecnica de
6 Introducao
store-carry-and-forward (Zhao & Cao 2008) para rotear as mensagens; (ii) transmissao
das mensagens baseando-se em contato direto (Spyropoulos, Psounis & Raghavendra
2008a); (iii) utilizacao das rotas dos veıculos para auxiliar no roteamento (Leontiadis
& Mascolo 2007), considerando-se que os veıculos sao esquipados com GPS e (iv) uti-
lizacao da tecnica de pulverizacao controlada de mensagens (Spyropoulos, Psounis &
Raghavendra 2008b). Tendo em mente que todas as tecnicas citadas acima sao estu-
dada pela literatura com o objetivo de melhorar o processo de roteamento, as principais
contribuicoes do RouteSpray sao:
• Combinar a tecnica de pulverizacao controlada com a utilizacao de rotas para
melhorar o processo de roteamento, campo de estudo em aberto e pouco explorado
pela comunidade cientıfica;
• Explorar o roteamento geografico para destinos moveis.
• Oferecer um estudo comparativo e uma analise de desempenho entre as tecnicas de
pulverizacao controlada, roteamento de uma unica copia, e inundacao de mensa-
gens. Utilizadas juntamente com informacoes das rotas doa veıculos para melhorar
o processo de roteamento.
Os resultados e contribuicoes deste estudo resultaram em uma publicacao em Periodico:
• DA SILVA, MAURICIO JOSE ; TEIXEIRA, FERNANDO ; OLIVEIRA, RI-
CARDO AUGUSTO RABELO . RouteSpray: A multiple-copy routing algorithm
based on transit routes. Journal of Applied Computing Research, v. 3, p. 11-18,
2013. (Qualis B5)
e duas publicacoes em Anais de Congresso:
• SILVA, M. J. ; SILVA, S. E. D. ; TEIXEIRA, F. A. ; OLIVEIRA, R. A. R. .
Combining the Spray Technique with Routes to Improve the Routing Process in
VANETS. In: 16th International Conference on Enterprise Information Systems,
2014, Lisbon. Proceedings of the 16th International Conference on Enterprise
Information Systems. p. 583-590. (Qualis B1)
• SILVA, M. J. ; TEIXEIRA, F. A. ; OLIVEIRA, R. A. R. . RouteSpray: Um
algoritmo de roteamento de multiplas copias baseado em rotas de transito.. In:
Introducao 7
SBCUP - V Simposio Brasileiro de Computacao Ubıqua e Pervasiva, 2013, Maceio.
SBCUP - V Simposio Brasileiro de Computacao Ubıqua e Pervasiva, 2013. (Qualis
B5)
8
Capıtulo 2
Referencial Teorico
Redes veiculares constituem o principal foco de estudo desta dissertacao. Porem, para
que seja possıvel a compreensao de nossa proposta, antes precisamos revisar alguns con-
ceitos. Este capıtulo esta dividido em duas Secoes: na primeira e apresentado os prin-
cipais desafios encontrados em redes DTN, abordando sua arquitetura e as limitacoes
enfrentadas por algoritmos de roteamento desenvolvidos para esse tipo de rede. Adici-
onalmente entenderemos como esse tipo de rede esta relacionado com redes veiculares.
Por fim, na segunda Secao sao apresentados os conceitos relacionados as redes veiculares.
2.1 Redes DTN
Desde seu surgimento, a arquitetura TCP/IP se tornou um modelo de comunicacao de
sucesso na internet. A arquitetura foi construıda utilizando um modelo em camadas,
onde, em cada camada, e definido um conjunto de tarefas que fornecem servicos bem
definidos para a camada de nıvel superior. Tal caracterıstica garante a interoperabili-
dade, que e a capacidade de dois sistemas conversarem de forma transparente, sejam
eles semelhantes ou nao. Talvez este seja o grande motivo de sucesso da arquitetura
TCP/IP.
Porem, para que seja possıvel a transmissao de dados em redes TCP/IP, e necessario
que as duas pontas estejam conectadas. Somente depois de estabelecida a conexao entre
os dois nos o protocolo TCP inicia a transmissao de dados. Isso acontece porque o TCP e
um protocolo confiavel, ou seja, ele exige que haja confirmacao de entrega de cada pacote
enviado. Caracterıstica inclusive que impacta em dois outros fatores, a exigencia de
9
10 Referencial Teorico
baixas taxas de erro e de pequenos atrasos na entrega da mensagem (Tanenbaum 2003).
Porem as caracterısticas exigidas para que haja comunicacao em redes de protocolos
TCP/IP nao sao atendidas em todos os tipos redes (Fall 2003), como por exemplo: (i)
redes militares, onde a concentracao dos pontos de comunicacao facilita acao inimiga, o
que exige que os nos dessa rede sejam moveis, alem da necessidade de prever que podem
ser destruıdos a qualquer momento; ou (ii) redes interplanetarias, onde o contato entre
os nos da rede (planetas e satelites) podem ser programados, uma vez que temos conhe-
cimento previo das orbitas de seus elementos e do tempo de propagacao da mensagem
no espaco; ou ainda, (iii) redes de sensores, onde os elementos da rede possuem grandes
restricoes de recursos, e geralmente permanecem desligados grande parte do tempo com
o objetivo de poupar energia. Alem destes, existem diversos outros tipos de rede onde
grandes atrasos de propagacao de mensagem e falta da existencia de um caminho fim
a fim tornam-se problemas a serem enfrentados. Essas caracterısticas deram origem a
um novo tipo de rede, que ficou conhecido como redes DTN (Delay Tolerant Network)
() (Cerf, Burleigh, Hooke, Torgerson, Durst, Scott, Fall, Travis & Weiss 2002) (Cerf,
Burleigh, Hooke, Torgerson, Durst, Scott, Fall & Weiss 2007) .
2.1.1 Arquitetura
A arquitetura DTN surgiu durante o desenvolvimento do projeto de Internet Interpla-
netaria (IPN) 1, e tinha como objetivo criar uma rede capaz de integrar a rede TCP/IP
com uma rede interplanetaria. Rede interplanetaria e caracterizada por nao existir um
caminho fim a fim durante todo o tempo. Para que isso aconteca e necessario que os as-
tros esteja alinhados, o que pode provocar um grande atraso na entrega das mensagens.
Com isso, surge a necessidade de criacao de uma tecnica para armazenar a mensagem a
cada salto, e aguardar a oportunidade de contato para transmiti-la para o proximo no,
esse processo e repetido ate que a mensagem alcance o destino. Observou-se que essas
caracterısticas estao presentes em diversos tipos de redes terrestres, e os esforcos foram
estendidos com a criacao de um grupo de pesquisa chamado DTNRG (Delay Tolerant
Network Research Group) 2. O grupo DTNRG surge com o como objetivo estudar e criar
padroes de protocolos que permitam a comunicacao nesse tipo de rede (Oliveira 2007).
A arquitetura DTN preve a utilizacao de uma camada de persistencia de dados.
A essa camada deu-se o nome de Camada de Agregacao (Scott & Burleigh 2007) e
1Disponıvel em: http://ipnpr.jpl.nasa.gov/index.cfm2Disponıvel em: http://www.dtnrg.org/wiki/Home
Referencial Teorico 11
ela fica situada acima da Camada de Transporte e abaixo da Camada de Aplicacao,
como podemos ver na Figura 2.1. Dessa forma, e possıvel manter a interoperabilidade
com qualquer tipo de rede, permitindo a integracao de uma rede DTN com as redes ja
existentes, sejam redes TCP/IP ou nao. Cada no da rede e conhecido como no DTN, e
ele pode ser um host, um roteador ou um gateway (ou uma combinacao), e agir como a
origem, o destino ou um encaminhador do agregado.
Figura 2.1: A camada de agregacao.
Em redes DTN os nos sao alcancaveis durante todo o tempo, por esse motivo, o
contato e a transferencia de dados acontecem em situacoes favoraveis (Voyiatzis 2012).
Dependendo das caracterısticas da rede DTN, algumas possibilidades de contato po-
dem ser exploradas, sendo elas: contatos persistentes, contatos sob demanda, contatos
programados, contatos previsıveis e contatos oportunistas. Contatos persistentes sao
contatos que sempre estao ativos, ou seja, nunca ficam indisponıveis. Ja os contatos
sob demanda, sao contatos que, em um primeiro momento, nao existem, mas que uma
vez estabelecidos permanecem ativos ate o final da sessao. Contatos programados sao
contatos em que o horario e a duracao do contato e conhecida, muito comum em redes de
sensores por exemplo, onde os nos da rede permanecem desligados para poupar energia,
e em determinado momento ficam ativos para coletar e trocar informacoes com os demais
nos da rede. Muito parecido com os contatos programados, mas com um certo grau de
imprecisao, sao os contatos previsıveis. Neste tipo de contato os nos conseguem prever o
momento do proximo contato. Para isso, eles utilizam informacoes sobre as ocorrencias
de contatos anteriores, porem, essa premissa pode provocar grandes taxas de erro. Po-
demos ter como exemplo as redes rurais Figura 2.2, onde os onibus trafegam entre um
12 Referencial Teorico
centro urbano, potencialmente conectado a internet, e uma area rural. O onibus tem o
papel do agente que transporta dados entre as duas regioes, permitindo que informacoes
cheguem ate a area rural. Obviamente, todo onibus tem horarios pre-definidos, o que
permite com que seja estabelecido um contato programado com algum outro no DTN.
Por outro lado, pode acontecer algum imprevisto que faca com o que o onibus chegue ao
seu destino atrasado, e com isso a oportunidade de contato sera perdida comprometendo
a comunicacao entre as duas regioes.
Figura 2.2: Contato previsıvel em uma rede rural.
Por fim, temos o contato oportunista. O contato oportunista acontece quando o nos
nao tem nenhuma informacao sobre os demais nos da rede, caracterıstica comum em
redes moveis, pois cada no tem sua mobilidade de forma independente. Nessa forma
de contato um no DTN aproveita que o outro entrou em sua area de transmissao e o
entrega a mensagem, encarregando-o de encaminhar a mensagem ate o destino. Essa e a
forma de contato mais utilizada pelos algoritmos de roteamento para redes moveis, que
combinada com alguma polıtica de encaminhamento de mensagem, como por exemplo,
o no que viaja em direcao ao destino, ou o no que tem historico de encontros anteriores
com o destino, tem constituıdo boas tecnicas de roteamento.
2.1.2 Roteamento
Um dos maiores desafios das redes DTN e realizar o roteamento das mensagens. Isso
porque nesse tipo de rede os contatos sao imprevisıveis, ou pior ainda, pode ser que
nunca seja estabelecido um caminho entre a origem e o destino. Para contornar esses
problemas, algoritmos de roteamento para redes DTN confiam na mobilidade dos nos
para entregar a mensagem para o destino, e adotam alguma polıtica de encaminhamento
Referencial Teorico 13
de mensagem para aumentar as chances da mensagem ser entregue. Alguns algoritmos
de roteamento geram replicas da mensagem durante o processo de roteamento, fazendo
com que em um determinado instante existam varias copias da mensagem em pontos
distintos da rede. Apesar de tal tecnica aumentar a probabilidade da mensagem ser
entregue, ela tem suas limitacoes. Uma boa polıtica de roteamento pode diminuir o
numero de mensagens na rede ou ate mesmo o tempo que as mensagens gastam para
atingir seus destinos. Algumas das principais tecnicas de roteamento sao:
• Contato Direto: Nessa tecnica o no de origem A entrega a mensagem para um
outro no DTN B, que passara a ser o novo custodio da mensagem, se B for um
contato direto do no de destino C. Ou seja, B nao entregara a mensagem para
nenhum outro no na rede, senao C, que e o destino da mensagem. Essa tecnica
de roteamento geralmente e utilizada em algoritmos de uma unica copia, o que
significa que em qualquer instante existe somente uma copia da mensagem na
rede. Geralmente a mobilidade dos nos da rede e a principal responsavel pelo
sucesso na entrega.
• Primeiro Contato: O No de origem A envia a mensagem para o primeiro no DTN
B que vier a estabelecer contato. O no B por sua vez encaminha a mensagem
para o primeiro no C que vier estabelecer contato, esse processo se repete ate que
a mensagem alcance o destino.
• Epidemico: Essa tecnica nao exige nenhum conhecimento previo sobre a rede, o que
a torna uma das principais tecnicas de roteamento. Consistem em gerar replicas
da mensagem a cada contato e espalhar a mensagem para todos os nos da rede.
Apesar dessa tecnica ter os melhores resultados quanto ao numero de mensagens
entregues e ao tempo que a mensagem demora para chegar ao destino, ela provoca
grandes degradacoes da rede. Como as mensagens sao pulverizadas para todos os
nos, e preciso adotar alguma polıtica de descarte de mensagens, permitindo que
mensagens que ja foram entregues seja descartadas. Essa tecnica de roteamento
consiste objeto de estudo dessa dissertacao, e sera explorado de forma detalhada
a frente.
• Probabilıstico: Nos contatos previsıveis, apesar do momento exato do estabeleci-
mento de cada contato entre dois nos da rede ser desconhecido, existe uma previsao
do intervalo dentro do qual cada contato podera acontecer. E estabelecida uma
probabilidade de ocorrencia de cada contato baseada em ocorrencias de contatos
14 Referencial Teorico
anteriores. A imprecisao dessa tecnica faz com que ela tenha seu desempenho
comprometido, uma vez que o contato pode nao acontecer.
Como vimos, redes DTN foram projetadas para serem aplicadas em ambientes consi-
derados desafiadores. Ou seja, ambientes em que as condicoes ideais de transmissao nao
sao atendidas. Varios tipos de redes sao considerados desafiadores, dentre eles estao as
redes veiculares. Varias caracterısticas tornam este tipo de rede uma rede de desafios a
qual os conceitos de redes DTN podem ser aplicados. Essa caracterısticas sao melhores
explicadas na Secao a seguir.
2.2 Redes Veiculares
2.2.1 Introducao
A crescente evolucao dos dispositivos de comunicacao tem nos permitido conectar carros
entre si ou a uma rede de infraestrutura. Com isso, surgiram os Sistemas de Transporte
Inteligentes (STI), cujo objetivo e tornar a viagem mais eficiente, mais segura e mais
divertida. Por eficiencia, entende-se reducao de congestionamento e poluicao, melhorias
no sistema de transporte publico, rotas menores e mais rapidas, menores custos de via-
gem e manutencao de veıculos e estradas. Mais seguranca significa oferecer informacoes
sobre acidentes, congestionamentos, condicoes da estrada e do clima, pontos de parada e
de interesse (restaurantes, postos de gasolina, etc). Para tornar a viagem mais divertida
os SITs podem, por exemplo, fornecer acesso a internet, download de arquivos, chats e
informacoes sobre pontos turısticos.
Um componente importante dos STIs saos as VANETs. VANETs sao um tipo espe-
cial de MANETS (Mobile Ad Hoc Network) voltado para veıculos. Com a implantacao
de dispositivos de comunicacao sem fio nos veıculos, sera possıvel a comunicacao ate
mesmo onde nao se tem outros tipos de estrutura, como telefonia movel por exem-
plo. Atualmente, muitos veıculos ja sao fabricados com equipamentos de comunicacao,
computadores de bordo, equipamentos de navegacao, e estes equipamentos podem ser
utilizados para auxiliar o motorista na tomada de decisoes. Orgaos interessados neste
cenario estao em busca de normalizacoes para desenvolver padroes.
Alem das classificacoes apresentadas na Secao ??, VANETs tambem podem ser clas-
sificadas quanto a sua extensao geografica, sendo pequenas areas ou grandes areas de
Referencial Teorico 15
cobertura. Em termos gerais ela se apoia em duas categorias: assistencia ao condutor e
disseminacao de informacao. Outro fator importante e a qualidade de servico exigida,
que vai depender da necessidade das aplicacoes podendo ser onde os dados nao precisam
ser transmitidos em tempo real, onde os dados precisam ser transmitidos em tempo real
e onde uma falha ou atraso na transmissao pode causar serios problemas.
2.2.2 Caracterısticas das redes VANETs
VANETs e MANETs possuem muitas caracterısticas em comum: ambas tem padroes
de mobilidade semelhantes, sao auto gerenciaveis e se auto organizam. Porem, existem
algumas diferencas que faz com que seja inviavel a utilizacao dos conceitos de redes
MANETs em redes VANETs. Como por exemplo, em redes VANETs os dispositivos
nao possuem restricoes de energia, a mobilidade e limitada por rodovias, porem pre-
visıvel, e sofrem grandes variacao de conexoes em pouco intervalo de tempo. Algumas
caracterısticas serao estudadas a seguir:
• Processamento, capacidade de comunicacao, sensoreamento e energia: Em uma
MANET processamento, capacidade de comunicacao, sensoriamento e energia sao
limitados. Em uma VANET e diferente, veıculos podem possuir computadores com
grande capacidade de processamento, varias interface de comunicacao, sensores de
todos os tipos e pode fornecer energia de forma continua. Alem de ainda poder se
comunicar com outros veıculos com a finalidade de distribuir algum processamento.
• Ambiente, modelo de mobilidade e conectividade: Ambientes influenciam direta-
mente no tipo de comunicacao, edifıcios pequenos ou grandes, rodovias, podem
alterar a qualidade da comunicacao. Outro fator importante, e que no caso de
VANET, a mobilidade esta diretamente ligada a forma com que o veıculo e condu-
zido. Ou seja, a velocidade do veıculo altera a topologia da rede de forma rapida,
alem disso, ainda ha a existencia de interferencia de comunicacao provocada por
obstaculos que podem entrar no entre dois dispositivos, como caminhoes e pontes,
por exemplo.
• Padrao de mobilidade: Outro fator importante e que tem que ser levado em conta
sao as restricoes espaco temporal, principalmente em redes V2V. Pois, neste cenario
temos um padrao de mobilidade muito heterogeneo, carros e caminhoes nao tem
uma mobilidade previsıvel, enquanto bondes eletricos tem uma velocidade contro-
lada e um padrao na mobilidade.
16 Referencial Teorico
• Tipos de comunicacao: Uma das principais aplicacoes de redes VANET e para
prevencao e seguranca nas rodovias, para esse tipo de comunicacao geralmente
utilizam-se mensagens multicast. Ou seja, as mensagens sao destinadas somente
aos veıculos que estiverem perto da rodovia, aos quais a mensagem e interessante.
• Armazenando informacoes: Diversas aplicacoes distribuıdas exigem abordagens
para armazenar e distribuir as informacoes. Porem em VANETs, devido a alta
mobilidade, conexoes intermitentes e heterogeneidade dos dispositivos, distribuir
estas informacoes e uma tarefa complexa. Para isto, a maioria da aplicacoes VA-
NETs utilizam algoritmos epidemicos para produzir e distribuir informacoes entre
os nos vizinhos.
2.2.3 Pilha de protocolos
Pilha de protocolo tem que lidar com diversos desafios, considerando veıculos proximos
e equipamentos fixos na rodovia. Faremos um estudo sobre cada camada da pilha de
protocolo.
Camada Fısica
Os protocolos da camada fısica tem que considerar os efeitos gerados pela movimentacao
dos nos, como o Efeito Doppler e Desvanecimento multiplo.
Redes V2V experimentais tem utilizado ondas de radio com frequencia alta. Isto,
porque ondas de banda VHF permitem conexoes a longa distancia, mas somente a baixas
velocidades. DSRC (Dedicated Short-Range Communication) e uma faixa de frequencia
de medio e curso alcance que tem sido aplicado em redes VANETs. Essa banda opera na
faixa de 5.9GHz, com variacoes em diversos paıses, e permite comunicacao entre veıculos
com velocidade de ate 200 km/h, em uma faixa de distancia de 300m a 1km, chegando
a uma taxa de transferencia de dados que varia de 6Mbps a 27Mbps. A banda DSRC e
divida em 7 canais de comunicacao, onde 1 deles e dedicado a transmissao de informacoes
de seguranca e outros 6 a transmissao de dados. As mensagem transmitidas pela banda
tem diferentes prioridades, onde as mensagem de seguranca tem alta prioridade e as de
dados tem baixa prioridade.
Referencial Teorico 17
Camada MAC
A camada MAC tem que oferecer acesso ao canal de forma integra, eficiente e confiavel.
Os protocolos da camada MAC tem que levar em consideracao os tipos de aplicacoes
que podem existir. Tem que oferecer uma conexao confiavel e com pouca latencia para
aplicacoes de seguranca por exemplo, e prever grandes taxas de transmissao de dados
mesmo em momentos em que o cenario nao e o ideal, pensando em aplicacoes de mul-
timıdia.
O protocolo IEEE 802.11p WAVE surgiu a partir de alteracoes no conjunto de pro-
tocolos do padrao 802.11. O objetivo do IEEE 802.11p WAVE e atender os requisitos
apresentados em redes V2V e V2I, onde baixa latencia e confiabilidade sao extremamente
importantes. Por exemplo, e desejavel que veıculos sejam fabricados com sensores inte-
grados que sejam capazes de enviar informacoes, em meio segundo, com todos os veıculos
equipados que estejam em um raio de 500m. WAVE utiliza CSMA/CA como tecnica de
acesso ao meio para compartilhamento de link.
Em ADHOC MAC propoe o uso do RR-ALOHA (Reliable Reservation ALOHA) que
cria uma canal de transmissao confiavel BCH (Basic Chanell) onde cada canal transporta
informacoes de sinalizacao para resolver problemas de sombra e garantir uma conexao
confiavel, permitindo a inclusao de novos dispositivos a rede. O principal problema e
que o numero de veıculos que conseguem se conectar esta limitado ao numero de slots
de tempo que se consegue a partir de um espaco de tempo.
Levando em consideracao que carros sao restritos a regras de direcao, surge a pos-
sibilidade de utilizacao de antenas direcionais para aprimorar a transmissao entre os
veıculos. Visto que, quando temos trafego de dados e direcional, a interferencia de da-
dos e o numero de colisoes e reduzido. Com base nesse cenario surgiu a proposta de
um protocolo direcional para a camanda MAC, o D-MAC (Diretional MAC ). D-MAC
propoem dois esquemas semelhantes ao protocolo 802.11 em alguns aspectos. Um pa-
cote ACK e enviado logo depois dos dados, se um terminal identifica uma transmissao
que nao o pertence ele nao participa dela. D-MAC pode utilizar somente frames RTS
direcionais, quanto pode utilizar uma combinacao entre frames RTS direcionais e frames
RTS omnidirecionais. Em resumo, seu princıpio basico e que se a comunicacao estiver
bloqueada para um terminal, ele podera se comunicar com algum outro ao qual nao
esteja bloqueado. Com isto, diminui-se as colisoes a aumenta a reutilizacao de canal.
18 Referencial Teorico
Camada de Rede
Duas estrategia basicas comumente utilizadas em redes wireless multiponto para rotea-
mento sao protocolos baseados na topologia e protocolos baseados na posicao. Protoco-
los baseados na topologia utilizam informacoes dos caminhos de transmissao, guardando
uma tabela de roteamento em cada no da rede. Esta topologia pode ser divida em duas,
sendo: proativa ou reativa. Protocolos Baseados na posicao assumem que o destino, os
nos vizinhos e a origem sao conhecidos, e podem ser divididos entre: tolerantes a atrasos
(DTN), nao tolerantes a atrasos (Non-DTN) e hıbridos.
Em princıpio, poderia-se aplicar os protocolos de roteamento AODV (Perkins &
Royer 1999) e DSR (Johnson & Maltz 1996) pra VANETs, porem, a alta velocidade
e as rapidas desconexoes fazem com estes protocolos percam muito desempenho. Por
outro lado, os protocolos baseados em posicao tem demonstrado ser boas propostas para
VANETs, pois sao mais robustos e promissores para ambiente altamente dinamicos.
Alem disso, eles nao mantem informacoes de estado, o que os diferencia dos protocolos
baseados na topologia.
GPSR (Karp & Kung 2000) e um conhecido protocolo de roteamento baseado em
posicao para MANETs, porem ele nao tem bom desempenho em redes veiculares. GPCR
(Lochert, Mauve, Fussler & Hartenstein 2005) e GPSRJ+ (Lee, Haerri, Lee & Gerla
2007) sao protocolos baseados em posicao com base no GPSR que foram aprimorados
para resolver o problema de rotas em redes veiculares. D-Greedy/D-MinCost (Skordylis
& Trigoni 2008) e VADD (Zhao & Cao 2008) sao tambem protocolos baseados em posicao
aprimorados sob o GPSR para descoberta de rotas em redes veiculares. Basicamente,
eles decidem se devem transmitir o pacote ou aguardar por ate que um no melhor de en-
caminhamento seja encontrado. No entanto estes protocolos nao consideram informacoes
importantes, como congestionamento de trafego. A-Start (Seet, Liu, Lee, Foh, Wong &
Lee 2004) e CAR (Naumov & Gross 2007) fazem entrega de pacotes de forma efici-
ente considerando congestionamento de trafego, ambos sao otimizados para lidar com
problema de conectividade, porem nao sao projetados para trabalhar com aplicacoes
sensıveis a atraso. PROMPT (Jarupan & Ekici 2010) e um protocolo de comunicacao de
cruzamento de camadas baseado em posicao consistente a atraso que melhora a conexao
fim a fim utilizando mensagens geradas por veıculos enquanto propagam informacoes de
sinal (estado da rede).
O desempenho de protocolos de roteamento depende de diferentes fatores, tais como
modelo de mobilidade veicular, a divulgacao de dados, o trafego de dados e layouts de
Referencial Teorico 19
estrada. Disseminacao de dados pode melhorar significativamente a taxa de entrega de
dados se, por exemplo, buffers de dados estao localizados nas intersecoes das estradas.
Camada de transporte
Como mencionado, redes veiculares sao caracterizadas por frequentes desconexoes e mu-
dancas rapidas de topologia. Em contraste com outras redes moveis, porem, tambem
tem um padrao de mobilidade. As frequentes desconexoes faz com que os protocolos
TCP e UDP nao seja uma boa opcao. Muitas das aplicacoes unicast requerem servicos
confiaveis para entrega de dados, semelhante ao TCP, para isto o protocolo VTP (Vei-
cular Transport Protocol) (Schmilz, Leiggener, Festag, Eggert & Effelsberg 2006) utiliza
dados estatısticos para melhorar o desempenho quando uma conexao e interrompida,
garantindo certa confiabilidade para aplicacoes unicast. MCTP (Mobile Control Trans-
port Protocol) seus princıpios sao baseados em protocolos TCP para redes ad hoc, mas
e aprimorado para oferecer QoS em comunicacao fim-a-fim entre veıculos e hosts na
internet atraves de uma infraestrutura rodoviaria.
Estes protocolos para VANETs sao baseados em aplicacoes unicast, porem muitas
aplicacoes veiculares sao multicast, e a projecao de um protocolo para este fim e um
desafio.
Camada de aplicacao
Os protocolos na camada de aplicacao devem prever uma pequeno atraso fim a fim,
isto, para garantir que um motorista seja notificado a tempo sobre eventos recentes
na rodovia. Outras aplicacoes tambem podem ser previstas na camada de aplicacao,
como protocolos para aplicacoes de multimıdia, de marketing e de venda de produtos.
VITP (Veicular Information Transfer Protocol) e um protocolo da camada de aplicacao
projetado para suportar o estabelecimento de um infraestrutura de servicos distribuıdos
sobre redes ad hoc, semelhante ao HTTP.
2.2.4 Aplicacoes para VANET
Eficiencia e seguranca sao os dois fatores que movem as redes veiculares, porem, eles
nao sao completamente distintos, muito pelo contrario, estao diretamente ligados. Por
20 Referencial Teorico
exemplo, quando acontecer um acidente em uma rodovia, mensagens podem ser enviadas
para os veıculos mais proximos, ajudando os motoristas na tomada de decisao, ou ainda,
para aumentar a eficiencia, estas mensagens podem se propagar pela vias alternativas,
informando aos veıculos que pretendem passar pelo local do acidente do ocorrido e
sugerindo caminhos alternativos, para aliviar o transito no local.
Discutiremos a seguir domınios de aplicativos para redes veiculares, que sao divididos
em assistencia ao motorista e disseminacao de informacao.
Requisitos basicos
Redes veiculares vem surgindo para tornar o transporte mais seguro e eficiente, e isto so
e possıvel atraves de dois requisitos, que sao coleta de dados e comunicacao de dados.
Aplicacoes VANETs irao monitorar condicoes dos veıculos, estradas, transito e am-
biente. Estas informacoes serao utilizadas para auxiliar o motorista a trafegar com mais
seguranca. Alem disso, uma rede veicular pode ser uma boa opcao para monitoramento
urbano, o fato do numero de veıculos dentro da cidade ser mais denso, e dos sensores de
bordo estarem cada vez mais presentes, possibilitara a utilizacao desta rede para moni-
torar as condicoes ambientais e atividades sociais, tornando-as assim um grande aliado
para deteccao urbana.
Veıculos podem receber poderosas unidades de processamento, sensores de diversos
tipos, cameras, dispositivos de localizacao. Tornando possıvel sua utilizacao para diver-
sas aplicacoes, desde vigilancia ambiental, controle de trafego a redes sociais moveis.
Veıculos sao conectados por meio de comunicacao sem fio com outros veıculos ou com
infraestrutura rodoviaria. Uma caracterıstica importante de VANET e a possibilidade
de troca de informacoes de forma rapida, principalmente quando se trata de mensagens
de seguranca. Porem, protocolos utilizados nas camadas mais inferiores tem que evitar
colisoes e garantir integridade das mensagens de emergencia, e o problema e que os
protocolos atuais nao garantem QoS para este tipo de aplicacao.
Assistencia ao motorista
O objetivo de redes VANET e evitar e diminuir o numero de acidentes. Alguns dos
cenario que as aplicacoes de seguranca podem ser uteis sao:
Referencial Teorico 21
Acidentes: Em caso de colisao a aplicacao deve informar aos carros que estao indo em
direcao ao local do acidente sobre o ocorrido, oferecendo rotas alternativas e informacoes
para aumentar a seguranca dos mesmos. Ainda e desejavel que vıdeos sejam enviados a
equipes de paramedicos mostrando o ocorrido e auxiliando na tomada de decisao com a
finalidade de agilizar o socorro as vıtimas. Porem, e desejavel que aplicacoes de seguranca
sejam projetadas para fornecer informacoes previas evitando acidentes.
Intercessoes: Controle e gestao de trafego e uma boa area de pesquisa. Uma vez que
em um cruzamento dois fluxos de carros convergem, os riscos de acidentes sao maiores.
Uma aplicacao poderia auxiliar o motorista nesta situacao com um semaforo virtual, ou
mesmo com informacoes que podem diminuir os riscos de uma colisao. Em ambos os
casos ha requisitos rigorosos para atingir principalmente em tempo real e processamento
distribuıdo.
Aplicacoes de congestionamento podem oferecer melhores rotas para o motorista ou
ate mesmo ajustar o semaforo de forma a otimizar o fluxo, e com isto melhorar o transito
evitando engarrafamentos.
Disseminacao de Informacao
Os pedidos de divulgacao visam uma distribuicao de entrega de informacao para o mo-
torista, passageiro e veıculo, o problema e como manter esta informacao em contexto, ja
que a rede e altamente dinamica. Alguns possıveis tipos de informacao que podem ser
disseminadas em redes VANET sao informacoes sobre mobilidade (transito, acidentes,
informacoes turısticas e de assistencia), comercio eletronico e entretenimento (acesso a
internet, jogos e chats).
2.3 Consideracoes Finais
Rede veicular sem fio e uma tecnologia essencial para os STI. A comunicacao entre
veıculos pode criar uma malha de comunicacao trazendo mais seguranca e mais eficiencia.
E com isso, tornar as viagens mais agradaveis aos usuarios. Redes veiculares futuramente
estarao entre os tipos de redes moveis mais importantes.
As caracterısticas distintas de redes veiculares geram diversos desafios a serem estuda-
dos. A alta mobilidade e a velocidade introduzem um cenario completamente diferente,
22 Referencial Teorico
onde novos protocolos tem que surgir. Os diversos desafios introduzidos pelas redes
VANETs, principalmente se considerarmos uma implantacao real, fara com que surjam
varios algoritmos que deverao ser projetados especificamente para resolve-los.
Capıtulo 3
Trabalhos Relacionados
Nos ultimos anos, varios trabalhos propuseram resolver o problema de roteamento em
redes ad hoc, como o DSR (Dynamic Source Routing) (Johnson & Maltz 1996) e o AODV
(Ad-hoc On-demand Distance Vector) (Perkins & Royer 1999). Esses protocolos iniciam
a transmissao de dados somente apos estabelecerem um caminho entre a origem e o
destino, caracterıstica que na maior parte do tempo nao e satisfeita em VANETs. Isso,
porque esse tipo de rede sofre frequentes desconexoes provocadas pela alta velocidade e
alta mobilidade dos veıculos. Com a finalidade de evitar perdas de dados, os protocolos
de roteamento para VANETs consideram a utilizacao da tecnica de store-carry-and-
forward (Lee & Gerla 2010).
Outra caracterıstica que pode beneficiar algoritmos de roteamento para VANETs, e
a utilizacao de informacoes de localizacao dos nos da rede, que tornou-se possıvel devido
a integracao de Sistemas de Navegacao (NS) aos veıculos. Protocolos de roteamento
que utilizam essa tecnica sao classificados como protocolos position-based, ou geografic-
based (Allal & Boudjit 2012).
3.1 Trabalhos Relacionados
Uma das principais tecnicas de roteamento utilizadas em redes moveis e a tecnica de
inundacao. Tal tecnica compreende em gerar replicas da mensagem e enviar para todos os
nos da rede, ate que a mensagem alcance o no de destino. Um esquema de roteamento
que utiliza a tecnica de inundacao para rotear as mensagens em uma rede movel, e
conhecido como roteamento Epidemico (Vahdat & Becker 2000). Alem da tecnica de
23
24 Trabalhos Relacionados
inundacao, o algoritmo de roteamento Epidemico utiliza a tecnica de store-carry-and-
forward para evitar que uma mensagem seja perdida durante a transmissao. Isso porque
a alta mobilidade dos nos provoca frequentes desconexoes da rede, fazendo com que o
algoritmo tenha que lidar com situacoes onde nao existe um caminho entre a origem e o
destino.
O funcionamento do algoritmo Epidemico se da da seguinte forma: o no A gera uma
mensagem para um no B e a armazena em seu buffer. Quando outro no C entra na
area de transmissao de A, C envia para A informacoes sobre as mensagens armazenadas
em seu buffer. Ao receber essas informacoes, A seleciona as mensagens que possuı em
seu buffer e que C nao possui, e transmite copias dessas mensagens para C. O mesmo
processo e feito pelo no C, ate que, ao final desse processo, ambos os nos possuam as
mesmas mensagem eu seus buffers. Referencias futuras ao processo citado acima serao
feitas como processo de sincronizacao de mensagens.
Algumas hipoteses podem ser levantadas com relacao ao processo de sincronizacao e
de transmissao de mensagens do algoritmo Epidemico. A primeira delas e com relacao
ao tempo de contato entre os nos.
Considerando que em alguns tipos de redes moveis os nos se movem em alta velo-
cidade, como por exemplo em redes VANETs, e que o tempo de associacao entre os
nos algumas vezes excede o tempo de contato, prejudicando a troca de informacoes en-
tre eles. Temos um cenario no qual o processo de sincronizacao falhara. Porem, essa
caracterıstica nao e determinante para que o algoritmo Epidemico perca desempenho,
uma vez que as mensagens nao transmitidas em um primeiro momento, poderao ser
transmitidas em contatos futuros.
Prova de conceito: Considere um no A com as mensagens de id: 001, 003 e 004 ar-
mazenadas em buffer. O no B, que esta com o buffer vazio, entra na area de transmissao
de A. A descobre que B nao possui nenhuma de suas mensagens, e inicia o processo
de sincronizacao de mensagens. Porem, durante a transmissao da segunda mensagem
o no B saı da area de transmissao de A, fazendo com que as mensagens 003 e 004 nao
sejam entregues. Ao final do processo, B possuı em seu buffer somente a mensagem
de id: 001. Em um segundo momento, o no A, ou qualquer outro no que entrar na
area de transmissao de B, percebera que B nao possui as mensagens de id: 003 e 004 e
transmitira essas mensagens para B.
Outra hipotese que podemos levantar com relacao ao roteamento Epidemico e que ele
atinge o limite superior com relacao ao numero de mensagens entregues. Isso acontece
Trabalhos Relacionados 25
porque o algoritmo Epidemico replica as mensagens para todos os nos da rede, fazendo
com que replicas da mensagem sejam enviadas para todos os caminhos possıveis. Se
replicas da mensagem sao enviadas para todos os caminhos, obviamente, se houver um
caminho ate o destino, uma das replicas sera enviada por esse caminho. Portanto,
considerando que nao havera perdas das mensagens transmitidas na rede, o algoritmo
Epidemico entregara o maior numero de mensagens possıveis.
Prova de conceito: Considere uma rede com N nos, onde o no A deseja entregar uma
mensagem para o no Z. No instante de tempo t0, o no B entra na area de transmissao
de A dando inıcio ao processo de sincronizacao de mensagens, ao final do processo, ele
tambem transportara uma copia da mensagem destinada a Z. No instante de tempo
t1, os nos C e D entram nas areas de transmissoes dos nos A e B respectivamente,
fazendo com que, ao final do processo de sincronizacao, todos os nos possuam copias da
mensagem enderecada a Z. No instante de tempo tx, D entra na area de transmissao de
Z e realiza a entrega da mensagem. O fato da mensagem ter sido replicada para todos
os caminhos possıveis, faz com que no instante de tempo tx+ y outros nos entreguem a
mensagem para Z.
A prova de conceito levantada acima nos oferece suporte para mais uma hipotese.
O algoritmo Epidemico entrega a mensagem no menor tempo possıvel. Se o algoritmo
Epidemico envia a mensagem para todos os caminhos possıveis, obviamente a mensagem
seguira o menor caminho entre a origem e o destino, e com isso, sera entregue no menor
tempo. Utilizando o exemplo acima, a mensagem foi entregue ao no Z no instante de
tempo tx, portanto, x e o menor tempo que a mensagem gastaria para alcancar Z, ou
seja, qualquer outro caminho que a mensagem siga, ela precisara de x + y unidades de
tempo para alcancar Z. Isso faz do algoritmo Epidemico limite inferior com relacao ao
tempo que a mensagem precisa para ser entregue ao destino.
Apesar do algoritmo Epidemico ter o melhor desempenho quanto ao numero de men-
sagens entregues e ao tempo que a mensagem demora para alcancar seu destino, ele
inunda a rede com replicas das mensagens, o que torna proibitivo sua utilizacao em
cenarios em que existem restricoes de recursos. Uma das restricoes encontradas em re-
des moveis e o espaco de armazenamento, como o algoritmo Epidemico replica todas as
mensagens para todos os nos da rede, para enviar N mensagens e necessario que cada
no da rede tenha buffer suficiente para armazenar as N mensagens, caso contrario, as
mensagens serao descartadas prejudicando o desempenho do algoritmo. Outra restricao
encontrada e a largura de banda, que geralmente e limitada devido ao meio de trans-
missao de dados e a necessidade de poupar energia, esta, que tambem esta entre as
26 Trabalhos Relacionados
limitacoes encontradas em dispositivos de redes moveis. Porem, o algoritmo Epidemico
exerce um importante papel para academia, pois seus resultados oferecem excelentes
referencias para medir o desempenho de novas propostas de algoritmos.
Outra categoria de algoritmos que podem ser aplicados a redes sem fio, sao os al-
goritmo de uma unica copia, como o GeOpps, que sera estudado mais a frente. Nessa
categoria de algoritmo existe somente uma copia da mensagem na rede durante todo
o tempo, e essa mensagem e transportando entre os nos da rede ate atingir o destino.
Para que isso seja possıvel, esses algoritmos introduzem o uso de um agente importante,
que e conhecido como Mula. O no Mula, ou transportador da mensagem, e o no que
tem a custodia da mensagem e e responsavel por carregar a mensagem, e transmiti-la
para o proximo no que passara a ser o novo custodio da mensagem. Esse processo se
repete ate que a mensagem alcance o destino. Para escolher qual sera o proximo salto da
mensagem, o no custodio leva em consideracao algumas informacoes, como por exemplo,
dados de contatos entre os nos, transmissao por contato oportunista, informacoes de
localizacao, etc. Esse processo que diferencia os diversos algoritmos de roteamento para
esse tipo de rede. Porem, algoritmos de uma unica copia de mensagem provocam gran-
des atrasos na entrega da mensagem em redes moveis, o que impossibilita sua aplicacao
em cenarios que exigem comunicacao em tempo real, como por exemplo, aplicacoes de
resgate de acidentes, alertas de perigo, stream de vıdeo, etc.
Com o objetivo de entregar as mensagens com menor atraso do que algoritmos de
uma unica copia, e sem degradar a rede como os algoritmos de inundacao (Spyropoulos,
Psounis & Raghavendra 2008b) propuseram uma nova categoria de algoritmos, a qual
denominaram algoritmos de “spray”. Essa categoria tem como objetivo gerar somente
algumas copias da mensagem, e com isso, explorar caminhos alternativos, conseguindo
tempos de entrega melhores do que os algoritmos de uma unica copia, e sem provocar
degradacao da rede sobrecarregando-a com numero excessivo de replicas de mensagens,
como os algoritmos de inundacao. Apesar dos autores introduzirem sua utilizacao em
redes esparsas, a tecnica de “spray” foi utilizada pela primeira vez em redes de celulares.
Sua utilizacao objetivava pulverizar as mensagens entre os pontos que os usuarios mais
frequentavam (Tchakountio & Ramanathan 2001).
Apesar da tecnica de “spray” ser uma boa alternativa para resolver o problema de
roteamento em redes moveis, ela introduz dois problemas que nao existem em outras
categorias de algoritmos, que sao: (i) como estimar o numero de nos presentes na rede;
(ii) e como estimar o numero de replicas (L) ideal para reduzir o tempo de entrega de
mensagens sem sobrecarregar a rede. Para o primeiro problema os autores sugerem que
Trabalhos Relacionados 27
pode ser utilizado uma contagem dos identificadores unicos de cada no da rede e com isso
estimar aproximadamente o numero de nos. Porem, tal metodo exigiria uma grande base
de dados para manter as informacoes dos nos da rede e ainda uma operacao de pesquisa
teria que acontecer a cada contato. Os modelos de mobilidade para redes moveis tem
tempos de contato entre os nos representados por uma distribuicao exponencial. Com
isso em mente, os autores sugerem que o numero de nos da rede pode ser estimado
considerando a distribuicao exponencial dos contatos de um no com os dois proximos
nos que ele encontrar. Calcular o numero de replicas necessario para serem pulverizadas
pela rede, e considerado um problema difıcil de forma geral, para facilitar a utilizacao
da tecnica de “spray” pela comunidade academica, os autores sugerem alguns valores
para serem utilizados como numero de replica de mensagens para uma rede de 100 nos.
Esses valores podem ser conferidos na tabela 3.1.
a 1.5 2 3 4 5 6 7 8 9 10
recursao 21 13 8 6 5 4 3 3 3 2
limite superior N.A. N.A. 11 7 6 5 4 3 3 2
serie de taylor N.A. N.A. 10 7 5 4 3 3 3 2
Tabela 3.1: Valores estimados de L para uma rede de 100 nos.
Para comprovar a eficiencia da tecnica de “spray”, (Spyropoulos, Psounis & Raghavendra
2008b) propuseram um algoritmo chamado spray and wait. O algoritmo e divido em
duas fases que sao: fase de “spray” e fase de “wait”, que serao explicadas a seguir:
• Na fase “spray”, o no de origem calcula o numero de copias que devem ser pulve-
rizadas. Esse calculo e baseado no numero de nos da rede e no tempo de atraso
desejado para que a mensagem alcance o destino. Essas copias sao pulverizadas
de forma oportunista entre os nos que entram na area de transmissao do no de
origem. Se a mensagem nao for entregue ao destino na fase “spray”, os nos iniciam
a fase “wait”. Existem duas formas de pulverizar as mensagens, que sao o Binary
spray e o Source Spray, ambas serao estudadas mais a frente.
• Quando o no entra na fase de “wait”, ele contem somente uma copia da mensagem,
e sera encarregado de entregar essa mensagem ao destino. Para isso, o algoritmo
“Spray and wait” utiliza a tecnica de contato direto, onde a mensagem transpor-
tada pode ser entregue somente para o no de destino. Dessa forma cada uma das
28 Trabalhos Relacionados
copias da mensagem e encaminhada de forma independente, seguindo modelos de
roteamento presentes em algoritmos de uma unica copia.
Os algoritmos acima constituem objetos de estudo dessa dissertacao por se tratarem
dos principais algoritmos de roteamento para redes esparsas. Porem, ambos foram de-
senvolvidos para serem aplicados a redes moveis de uma forma geral, nao se beneficiando
de caracterısticas especıficas de um tipo de rede. Por esse motivo, o proximo algoritmo
estudado foi o GeOpps (Leontiadis & Mascolo 2007), que e um dos principais algoritmos
desenvolvidos para ser aplicado em redes VANETs, e utiliza a transmissao de forma
oportunista e informacoes de contexto para melhorar o processo de roteamento.
O algoritmo GeOpps e um algoritmo de uma unica copia, que tem como objetivo
rotear mensagens de dados para uma regiao geografica especıfica. Para que isso seja
possıvel, o algoritmo considera que os veıculos sao equipados com Sistemas de Navegacao
(SN), onde os motoristas informam seus destinos a cada viagem, permitindo que o SN
calcule a rota que o veıculo percorrera para alcancar o destino. Alem disso, o algoritmo
assume que o SN possuı informacoes sobre as localizacoes das Estacoes de Informacao
(EI) que compoem a rede juntamente com os veıculos. Essas EI estao potencialmente
conectadas a internet, e sao utilizadas como uma especie de backbone de rede, para onde
o fluxo de dados deve ser direcionado. Cada veıculo da rede atua como uma especie
de sensor, que e capaz de coletar informacoes sobre o transito (velocidade, aceleracao,
etc.) e sobre as condicoes das estradas (buracos, etc.). Essas informacoes sao enviadas,
atraves das EI, para um Sistema Centralizado que combinara os dados recebidos de varias
origens e produzira estimativas sobre as condicoes de transito atuais. Apos tal processo,
os Sistemas Centralizados produzirao alertas sobre trechos de estrada especıficos, e os
encaminhara para a EI mais proxima de tal trecho, encarregando os veıculos vizinhos
de rotear a mensagem ate a area afetada.
O funcionamento do algoritmo GeOpps consiste em: (i) trocar informacoes das men-
sagens com os nos que estao a um salto de distancia; (ii) Calcular o METD (Tempo
Mınimo Estimado para Entregar a Mensagem ao Destino) e encaminhar o resultado
para o no requisitante; (iii) Manter a custodia da mensagem se tiver o METD menor,
ou encaminha-la para o vizinho encarregando-o de entregar a mensagem.
De forma semelhante aos demais algoritmos de uma unica copia, o algoritmo GeOpps
utiliza contato oportunista e informacoes de contexto para garantir que a mensagem seja
entregue ao destino. O que o torna uma solucao melhor do que os demais algoritmos e
a utilizacao do METD para escolher qual e o melhor transportador para a mensagem.
Trabalhos Relacionados 29
Para isso, uma funcao de utilidade e aplicada. Tal funcao estima o METD da seguinte
forma: o algoritmo percorre a rota do veıculo procurando o ponto mais proximo do
destino (NP); depois de descoberto NP, o algoritmo solicita do SN o tempo estimado de
viagem (ETA) de sua posicao corrente ate o NP; finalmente, o algoritmo soma o tempo
retornado pelo SN com o tempo estimado para que o veıculo viaje em linha reta do NP
ate o destino. Em linhas gerais, o METD pode ser calculado da seguinte forma:
METD = ETA para o NP + ETA do NP para o D.
Para uma melhor compreensao do processo de roteamento, considere a Figura 3.1.
O veıculo a possui uma mensagem destinada ao ponto D. No ponto P1, o veıculo a
encontra com o veıculo b e o escolhe para ser o transportador da mensagem, pois o
METD de b e menor do que o METD de a. Observe que a mensagem nunca alcancara
o NPb, pois no instante de tempo P2, o veıculo b cruza com outro veıculo c, e o escolhe
como o novo transportado da mensagem, encarregando-o de levar a mensagem para
proximo de D.
Figura 3.1: Exemplo do calculo do NP do destino do pacote.
Porem, nem sempre as condicoes ideais para as quais o algoritmo foi projetado sao
30 Trabalhos Relacionados
satisfeitas, como por exemplo quando o motorista desvia ou ignora a rota sugerida, ou
quando ele para o veıculo antes de concluir a rota. Para resolver esses problemas, o
algoritmo GeOpps assume que o veıculo corrente nao e capaz de entregar a mensagem,
e a encaminha para o no vizinho.
Apesar de o algoritmo GeOpps ter sido projetado para redes veiculares, e utilizar
as rotas dos veıculos para otimizar o processo de roteamento. O fato dele nao explorar
rotas alternativas utilizando multiplas copias de mensagens faz com que ele tenha seu
desempenho comprometido, e torna inviavel sua utilizacao pratica. Em contrapartida, o
algoritmo Spray and Wait se beneficia de redes densas, porem em redes veiculares essa
caracterıstica se torna uma armadilha e compromete o desempenho do algoritmo. Isso
acontece porque o fluxo de carros se concentra em cruzamentos ou em semaforos, e os
veıculos se dividem entre as opcoes de direcoes que podem seguir. Tal comportamento
faz com que algumas copias das mensagens sejam levadas para longe do destino.
3.2 Consideracoes Finais
Com o objetivo de eliminar os problemas provocados por algoritmos de inundacao e
de evitar a propagacao de mensagem para regioes distantes da regiao do destino da
mensagem, o algoritmo RouteSpray utiliza as rotas dos veıculos para escolher qual e
a melhor opcao para carregar a mensagem. Ele pulveriza as mensagens somente en-
tre os nos que encontrarao com o destino, e com isso, impede que sejam pulverizadas
desnecessariamente para nos que nunca poderao entrega-las.
Capıtulo 4
Protocolo de Roteamento Route Spray
4.1 Algoritmo RouteSpray
Para realizar o roteamento, o protocolo RouteSpray assume que os veıculos sao equi-
pados com GPS e que alem de conhecer sua propria rota, o veıculo precisa conhecer
a rota do destino da mensagem. Considerando que algoritmos position-based assumem
conhecimento da localizacao do destino da mensagem, esse se torna um requisito basico.
Sendo que o algoritmo RouteSpray se diferencia dos demais por prever a mobilidade do
no de destino. Uma vez que, grande parte desses algoritmos assumem que o destino da
mensagem e um no estacionario, ou ainda, uma regiao geografica. Alem disso, nao e ne-
cessaria a existencia de nenhuma infraestrutura fixa de rede, ou seja, e possıvel realizar
o roteamento entre os veıculos de forma totalmente ad hoc.
O funcionamento do protocolo e baseado no uso de dois tipos de mensagens, sendo
elas as mensagens de controle e as mensagens de dados. As mensagens de controle sao
utilizadas para manter o estado da rede, enviando informacoes de contexto para os nos
vizinhos. Cada mensagem gerada na rede possui um identificar unico, que e composto
pelo endereco do no de origem, o horario de criacao da mensagem e um contador, que
tem como objetivo evitar conflitos de mensagens criadas no mesmo horario.
O processo de troca de informacoes e a tomada de decisao de roteamento pode ser
dividido em tres etapas distintas. Na primeira etapa a comunicacao inicia-se atraves
de um handshake, onde os nos trocam informacoes dos pacotes que ja foram entregues
pela rede, permitindo fazer o controle de mensagens armazenadas em buffer, o que e
conseguido apagando as que ja foram entregues. Ja na segunda e terceira etapas, os nos
31
32 Protocolo de Roteamento Route Spray
trocam informacoes sobre o estado do buffer. O no de origem envia para seus vizinhos
uma lista contendo um identificador e o destino de cada mensagem que possui em seu
buffer. Com essas informacoes o vizinho calcula, utilizando as rotas pre-estabelecidas, o
tempo em segundos que demorara para entregar cada mensagem. Apos a origem receber
a resposta do no vizinho, ela e capaz de decidir qual e o melhor transportador para a
mensagem. Mais detalhes sobre as etapas de roteamento sao apresentadas a seguir.
Considerando que o no X entrou na area de transmissao do no Y . Na primeira
etapa, X envia para Y uma mensagem de handshake que possui como carga de dados
a lista das mensagens que ja foram entregues na rede. Ao receber essas informacoes,
Y e capaz de percorrer seu buffer apagando as mensagens que ja foram entregues aos
seus respectivos destinos. Ao final deste processo, com o buffer consistente, Y realiza a
entrega das mensagens enderecadas a X, e envia para ele a lista de mensagens que Y
possui em seu buffer.
Na segunda etapa, quando X recebe a lista das mensagens presentes no buffer de
Y , X calcula o tempo que ele precisa para entregar cada uma dessas mensagens. Em
seguida envia para Y uma relacao contendo o identificador e o tempo necessario para
entregar cada mensagem. Para calcular o tempo de entrega da mensagem, X percorre
a rota do destino da mensagem a procura de um ponto de intersecao com sua rota. Ao
final desse processo, caso X encontre um ponto de intersecao, ele retorna o tempo em
segundos que demora para ir de sua posicao corrente ate esse ponto. Caso tal ponto nao
exista, o algoritmo retorna um valor negativo, indicando que X nao e capaz de entregar
a mensagem.
Finalmente, na terceira etapa, ao receber as informacoes do tempo que X precisa para
entregar cada mensagem, Y e capaz de decidir quem e o melhor transportador para a
mensagem. Para isso Y precisa calcular quanto tempo ele precisa para realizar a entrega
da mensagem e comparar com o tempo retornado por X. Caso Y possua mais de uma
copia da mensagem, ele ira utilizar a tecnica de binary spray para pulverizar as copias
da mensagem para X. Caso o tempo de entrega retornado por X seja menor do que o
tempo de entrega calculado por Y , Y encaminha a mensagem para X, encarregando-o
de entrega-la ao destino. Todo o processo de roteamento descrito anteriormente pode
Protocolo de Roteamento Route Spray 33
ser visto com mais detalhes no Algoritmo 4.1.
Algoritmo 4.1: Pseudo-codigo RouteSpray
Input: mensagem
if recebeu mensagem de controle then1
if mensagem de handshake then2
LimpaBuffer;3
AtualizaListaDeMensagensEntregues;4
EntregaMensagensEnderecadasOrigem;5
RespondeListaMensagensBuffer();6
else if resposta a mensagem de handshake then7
RecebeRelacaoMensagensVizinho;8
EnviaTempoDeContatoMensagem();9
else10
ProcessaRespostaTempoDeContato;11
DecideQualMelhorTransmissor();12
else if recebeu mensagem de dados then13
if mensagem enderecada a mim then14
ProcessarMensagem();15
else16
ArmazenarNoBuffer();17
A melhoria no desempenho do RouteSpray se da pela combinacao de dois conceitos
importantes: (i) utilizacao de rotas para obter conhecimento previo dos contatos entre
os nos e (ii) utilizacao da tecnica de Binary Spray. Tal combinacao garante melhores
taxas de entrega sem sobrecarregar a rede. Ambos os conceitos sao explicados com mais
detalhes a seguir.
4.1.1 Utilizacao de Rotas
As informacoes de geolocalizacao em uma rede permitem ter conhecimento previo sobre
a posicao de seus nos. Tal caracterıstica possibilita o encaminhamento de pacotes na
direcao do destino e melhora a taxa de entrega de dados. A utilizacao das rotas dos
34 Protocolo de Roteamento Route Spray
veıculos garante que o algoritmo consiga prever os contatos entre os nos da rede. Assim,
ele pode tomar a melhor decisao de encaminhamento.
Considerando que tres veıculos seguirao rotas pre-estabelecidas (Figura 4.1), e que o
veıculo B possui um pacote destinado ao veıculo C, apesar das rotas dos veıculos B e C
se cruzarem o veıculo B escolhera o veıculo A como melhor transportador da mensagem
ate o destino. Isso porque o veıculo A se encontrara com o veıculo C antes do veıculo
B. Esse processo garante que a mensagem seja entregue no menor tempo possıvel.
Figura 4.1: Rotas pre-estabelecidas para tres veıculos.
Protocolo de Roteamento Route Spray 35
4.1.2 Binary Spray
Esquemas de encaminhamento baseados em uma unica copia de mensagem provocam
grandes atrasos na entrega. Por outro lado, esquemas de encaminhamento baseados em
inundacao provocam degradacao na rede. Visando obter o menor atraso na entrega sem
degradar a rede, em (Spyropoulos, Psounis & Raghavendra 2008b) os autores propuse-
ram a tecnica de “spray”, que consiste em gerar um numero controlado de copias de
mensagens e pulveriza-las entre os nos da rede. Quando um veıculo deseja transmitir
uma mensagem, ele gera um numero controlado de copias (L). Para calcular o valor de
L, e levado em consideracao o numero de nos presentes na rede e o tempo desejado de
atraso para que a mensagem alcance o destino. A pulverizacao pode acontecer de duas
formas diferentes, as quais os autores deram os nomes de Source Spray e Binary Spray.
Na pulverizacao baseada no Source Spray, o no de origem encaminha as L copias da
mensagem para os primeiros L nos distintos que encontrar. No Binary Spray, o no de
origem inicia com L copias; enquanto o no A possuir n > 1 copias (for a origem ou o
transportador) e encontrar com outro no B (que nao possui nenhuma copia) ele entregara
ao no B b(n/2)c copias e mantera d(n/2)e consigo; quando o no possuir somente uma
copia, ele escolhera o contato direto para realizar a entrega.
Uma caracterıstica do Source Spray e que a mensagem realiza somente dois saltos
ate atingir o destino, ou seja, o origem encaminha a mensagem para o transportador
tornando-o o responsavel por entrega-la ao destino. Essa caracterıstica provoca atrasos
na entrega em redes com mobilidade controlada, o que inviabiliza seu uso em VANETs.
Ja no Binary Spray, o fato do no transportador receber mais de uma copia da mensagem
encaminhando-as em contatos futuros, faz com que esta tecnica realize o encaminha-
mento baseado em multiplos saltos, diminuindo o tempo de entrega da mensagem. Por
este motivo, optou-se por utilizar o Binary Spray como polıtica de encaminhamento de
mensagem no RouteSpray.
4.2 Consideracoes Finais
Como vimos, o algoritmo RouteSpray combina o melhor dos mundos de duas categorias
de roteamento para redes moveis, que sao o controle de copias pulverizadas e o uso de
informacoes de geoposicionamento. A combinacao de tais caracterısticas faz com que
o RouteSpray consiga, de forma robusta, simples e estavel, rotear a mensagem pelo
36 Protocolo de Roteamento Route Spray
caminho otimo, quando o princıpio de otimizacao for aplicado a tempo de entrega e
sobrerga da rede. Para avaliar a nossa proposta, foi desenvolvido um framework de
mobilidade que permite a coleta de dados de mobilidade em tempo real, garantindo
mais realismo nas simulacoes. Mais detalhes sobre tal framework serao vistos a seguir.
Capıtulo 5
VeNeM - Gerador De Mobilidade
Veicular Real
5.1 Introducao
Redes Ad Hoc Veiculares (VANETs) ganharam destaque entre os Sistemas Inteligentes
(SI) nos ultimos anos. Com isto, surgem diversos pesquisadores interessados em resolver
os desafios encontrados nesse tipo de rede. Porem, para que os pesquisadores consigam
validar suas propostas e necessario a experimentacao, que geralmente advem de ambi-
entes simulados [1]. Isso acontece porque conseguir pessoal e equipamentos suficientes
para realizar experimentos em ambientes reais e inviavel, devido as dificuldade de es-
calabilidade e aos altos custos envolvidos. Uma das maiores dificuldades para simular
uma rede veicular esta em garantir que a os padroes de mobilidade de um ambiente real
sejam reproduzidos. Segundo [2] e [3], os simuladores existentes que possibilitam experi-
mentacoes com padroes de mobilidade semelhantes aos reais, geralmente sao complexos
de serem utilizados e estao disponıveis somente em uma determinada regiao. Tal carac-
terıstica faz com que mais de 50% das novas propostas de algoritmos sejam avaliadas em
simuladores customizados, o que dificulta a implementacao desses algoritmos por outros
membros da comunidade cientıfica [4].
37
38 VeNeM - Gerador De Mobilidade Veicular Real
5.2 Simulacoes em Redes Veiculares
Um importante aspecto para avaliacao de novas propostas de algoritmos para redes
veiculares e o padrao de mobilidade dos nos, o qual determina quando ha contato entre
os nos, e qual sua duracao. De acordo com [5-8], os modelos de mobilidade podem ser
influenciados por diversos fatores. Aos quais sao divididos em duas classes, que sao
parametros relacionados com a micro-mobilidade e com a macro-mobilidade.
Micro-mobilidade tem como objetivo descrever o comportamento de cada veıculo in-
dividualmente. Certamente, esses parametros nao sao comuns a todos os nos da rede,
mas desempenham um papel importante durante a simulacao. Isso porque a mobilidade
individual de cada veıculo influencia diretamente na formacao da rede. Parametros
como velocidade, aceleracao, comportamento em intersecoes (com ou sem semaforos)
sao modelados pelo comportamento e pela maturidade do motorista e podem ser influ-
enciados por diversos fatores, como pontos de interesse, humor, sexo, idade. Levar esses
parametro do mundo real para o mundo simulado e um desafio que tem sido atacado
pelos principais simuladores de rede [9].
Alem dos parametro de micro-mobilidade, que estao relacionados com o comporta-
mento individual de cada veıculo, modelos de mobilidade tem que lidar com parametros
de macro-mobilidade. Tais parametros descrevem o comportamento de um grupo de
veıculos, como por exemplo a densidade dos veıculos, a velocidade media de viagem, os
pontos de interesse aos quais o maior fluxo tente a convergir, dentre outros.
5.2.1 Modelos de mobilidade
Cada modelo de mobilidade tem suas caracterısticas especıficas, podendo ser aplicado em
determinado cenario ou nao. Para entendermos melhor como os modelos de mobilidade
se comportam e como esses parametros afetam nos resultados, sera apresentado uma
breve descricao de alguns dos modelos presentes nos simuladores de VANTEs, uma lista
mais exaustiva pode se encontrada em [5-8].
(a) Random-Waypoint: Segundo [10-11], o Random-Waypoing e um simples modelo
estocastico no qual o no viaja entre dois pontos da area de simulacao durante um
tempo gerado aleatoriamente. Primeiramente, os nos sao colocados aleatoriamente
na area de simulacao. Cada no aguarda durante um tempo de espera que e gerado
utilizando distribuicao normal, quando o tempo de espera termina, o no viaja ate
VeNeM - Gerador De Mobilidade Veicular Real 39
um outro ponto escolhido aleatoriamente dentro da area de simulacao. Entao o
no aguarda um novo tempo de espera e viaja ate um novo ponto escolhido alea-
toriamente. Esse processo se repete durante toda a simulacao. Existem algumas
variacoes desse modelo que tentam tornar o ambiente um pouco mais real, como
por exemplo a insercao de velocidade media para os veıculos viajarem entre os
pontos ou ainda a insercao de pontos de interesse, aos quais tendem ter maior
fluxo de veıculos. Porem, o Random-Waypoint nao considera o uso de nenhum
parametro real, e a mobilidade e completamente aleatoria, o que nao corresponde
a realidade, pois veıculos devem respeitar os limites de estradas e rodovias.
(b) Grid de Manhattan: Proposto por [12], no Grid de Manhattan o cenario e dividido
em quadrados, lembrando os quarteiroes de uma cidade planejada. Inicialmente
os nos sao distribuıdos pelo cenario de forma aleatoria, depois cada no escolhe a
direcao em que ele deve viajar, e vai ate o outro ponto a uma velocidade constante.
Ao alcancar um cruzamento, o no escolhe aleatoriamente uma nova direcao pela
qual ele seguira com uma velocidade diferente, (tambem escolhida aleatoriamente).
Essa direcao, geralmente e distribuıda como sendo, 50% de probabilidade do veıculo
seguir em linha reta, e 25% de probabilidade do veıculo virar para qualquer um
dos lados (direita ou esquerda).
(c) Cluster de Voronoi: Segundo [13], varias cidades nao crescem de forma planeja-
das, fazendo com que as ruas formem um grafo complexo que se assemelha ao
Diagrama de Voronoi (Figura 5.1). Por esse motivo, nesse modelo de mobilidade
a disposicao das ruas sao representadas por um Diagrama de Voronoi. Os veıculos
sao distribuıdos uniformemente pela area da simulacao e se move em uma velo-
cidade inicial escolhida entre 0 e a velocidade maxima predefinida. Quando o no
esbarra em uma borda, que representa as construcoes as margens da via, ele con-
tinua o movimento seguindo o angulo de reflexao, quando acontece a refracao o
movimento do no e espelhado. Em algum instante o no interrompe o movimento e
aguarda por um momento de pausa, tambem predefinido, ao decorrer de tal tempo,
o no volta a se movimentar em um novo angulo e uma nova velocidade.
5.2.2 Evolucao dos simuladores
Segundo [14] evolucao historica dos simuladores de redes VANETs pode ser facilmente
percebida. Quando os modelos de mobilidade que utilizam parametros aleatorios para
40 VeNeM - Gerador De Mobilidade Veicular Real
Figura 5.1: Modelo de um grafo de Voronoi.
representar o movimento dos nos deixaram de atender as expectativas da academia. O
que deixou claro a necessidade do surgimento de propostas que repliquem de forma mais
fiel o comportamento real do no nesse tipo de rede. Com isso surgem simuladores que
modelam a mobilidade dos nos da rede utilizando traces de rotas veiculares coletadas a
partir de sistemas de navegacao. Porem, apesar da mobilidade dos nos da rede estarem
limitadas pelas fronteiras entre as ruas e as construcoes ao seu entorno, a falta de um
modelo para prever o comportamento do motorista provocam resultados indesejados.
Para resolver tal problema, surgem os simuladores de redes com casamento bidire-
cinal [15], ou seja, uma integracao entre dois tipos de simuladores distintos, que sao
os simuladores de redes veiculares e os simuladores de trafego. Ambos os simuladores
trocam informacoes para auxiliar na tomada de decisoes sobre o movimento dos nos na
rede. Com isso conseguem simular de forma dinamica o comportamento do motorista ao
encontrar um cruzamento, um semaforo fechado, ou algum incidente que possa refletir
na simulacao (como uma freada para evitar colisao com o carro da frente, mudancas de
pista, etc). As vantagens e desvantagens de cada classe de modelo de mobilidade pode
ser vista em mais detalhes na Tabela 5.1.
VeNeM - Gerador De Mobilidade Veicular Real 41
Classe de Modelo de Mobilidade Vantagens Desvantagens
Movimento randomico
Simples,
Imprecisointuitivo,
Sempre disponıvel
Rotas reaisMovimento do no mais reais Caro
Rotas reutilizaveis Consome tempo
Rotas artificiaisMovimento do no realista
Sem feedback do motoristaRotas reutilizaveis
Casamento BidirecionalMovimento do no realista
impossıvel replicarfeedback das acoes do motorista
Tabela 5.1: Visao geral das classes de modelos de mobilidade
Como consequencia, juntamente com a evolucao da riqueza de realismo dos simu-
ladores de redes, os simuladores tambem evoluıram em nıvel de complexidade, onde o
simuladores da classe de Casamento Bidirecional sao consideravelmente mais complexos
e os da classe de Movimento randomico sao menos complexos. Tal complexidade faz com
que a curva de aprendizado para utilizar tais simuladores seja muito grande, comprome-
tendo os testes para pesquisas de curto prazo e incentivando a utilizacao de simuladores
customizados.
5.2.3 Discussao
Percebemos que a maioria das novas propostas de algoritmos de roteamento sao testa-
das em simuladores customizados. Alem dos simuladores customizados prejudicarem a
implementacao das propostas por outros membros da comunidade, geralmente os expe-
rimentos sao reportados com ausencia de alguns parametros. Isso faz com que autores
de novas propostas optem por comparar seus algoritmos com algoritmos basicos.
Com isso, percebemos que apesar das pesquisas que envolvem simulacoes em redes
veiculares estarem em constante evolucao, ainda ha lacunas que tornam este, um campo
de pesquisa ainda em aberto.
42 VeNeM - Gerador De Mobilidade Veicular Real
5.3 Simuladores existentes
Nesta secao sera apresentado uma sucinta descricao de alguns dos geradores de mobili-
dade veicular mais utilizados pela comunidade cientıfica.
5.3.1 BonnMotion
BonnMotion [12] e uma ferramenta para gerar mobilidade veicular com foco em gerar
modelos de mobilidade para os principais simuladores de redes sem fio (ns-2, glomosim,
qualnet, cooja e mixim). Porem, os modelos de mobilidade sao gerados a partir de
modelos estatısticos, e o simulador permite que dados seja controlados, como velocidade
e aceleracao. Como pontos positivos o autor destaca a facilidade de uso e uma boa
descricao dos modelos de mobilidade suportados.
5.3.2 VanetMobiSim
VanetMobSim [16] e uma extensao do simulador CanuMobiSim [17], e tem como objetivo
gerar modelos de mobilidade mais proximos da realidade. Para isso, entre seus geradores
de topologia de rodovias possuı modelos extraıdos de bases publicas, que compreende
pequenas regioes geograficas.
5.3.3 Veins
O Veins [15] e construıdo a partir da uniao do simulador de redes OMNeT++ [18] com o
microsimulador de trafego SUMO. O Veins e um simulador de casamento bidirecional que
permite que eventos provocados pela mobilidade dos veıculos tenham influencia sobre
a simulacao de rede. Como ponto positivo, o Veins tras consigo a possibilidade de que
sejam feitas simulacoes com alto grau de realismo. Como ponto negativo, o Veins e um
simulador complexo de ser utilizado, e parametros reais de simulacao estao disponıveis
somente para um pequeno trecho da Europa.
VeNeM - Gerador De Mobilidade Veicular Real 43
5.3.4 Framework de Mobilidade veicular
Propomos um framework que e capaz de coletar dados de veıculos a partir de um web
service e transportar esses dados para um simulador de redes veiculares, Figura 5.2. Com
isso seria possıvel fazer uma simulacao em tempo real, considerando o comportamento do
motorista no momento da simulacao. Esse framework possui tres componentes principais
cujas funcoes sao: coletar dados, gerar a simulacao, e exibir os resultados.
Figura 5.2: Framework de Gerenciamento de rede movel.
A parte de coleta de dados consiste em sensores instalados nos veıculos, que podem
ser integrados com sistemas de navegacao. Esse dados sao enviados para um sistema
centralizado, onde as informacoes de todos os veıculos serao coletadas e tratadas para
serem disponibilizadas para a parte responsavel por gerar as simulacoes. Apos coletados
e tratados, os dados serao organizados e publicados em um web service RESTFULL. A
escolha por um web service RESTFULL e justificada pelo falto dele ser implementado
44 VeNeM - Gerador De Mobilidade Veicular Real
sob a camada de aplicacao, o que garante a interoperabilidade em qualquer tipo de rede,
seja ela TCP/IP ou nao. O fato dos componentes do framework estarem organizados
em camadas, possibilita alteracoes na camada de coleta de dados sem afetar o restante
do framework, o que deixa cada componente aberto a novas propostas.
O web service deve publicar um conjunto mınimo de informacoes composto por:
id, latitude, longitude, altitude (para simulacoes em 3D, o que permite integracao com
VANTs por exemplo) e timestamp. Porem, o framework nao esta limitado a esse pequeno
conjunto de informacoes, o que permite sua extensao de acordo com a necessidade de
cada aplicacao. Essas informacoes serao coletadas pelo componente responsavel por
gerar a simulacao, que atuara com um middleware entre o web service e um simulador
de rede. O objetivo desse middleware e coletar as informacoes dos nos presentes na rede
e exporta-las em um formato compatıvel com algum dos simuladores de redes existentes,
que pode ser o OMNeT++, NS-2, OPNeT, ou qualquer outro simulador consolidado pela
comunidade.
O framework proposto acima permite que empresas (empresas de logıstica, frotas de
onibus, caminhoes, taxis, etc) gerenciem seus veıculos. A integracao de tal framework
com sistemas de mapas que fornecem informacoes sobre as vias, possibilita prever eventos
futuros, gerar alertas aos administradores da frota permitindo-os notificar o motorista,
dentre varias aplicacoes. Como exemplo de sistemas de mapas que poderiam ser utili-
zados temos o google maps1 e o openStreetMaps2. O google maps tem a API limitada,
o que faz que com que seja necessario a utilizacao de biblioteca de terceiros para co-
letar os dados da via(sentido do transito, velocidade permitida, etc). Por outro lado,
como ponto positivo, o google maps tem um sistema de analise de transito em tempo
real, o que permite coletar o tempo medio de viagem de acordo com as condicoes de
transito em determinados horarios com alto nıvel de precisao. Ja o openStreetMaps e
open source e livre e fornece informacoes considerando inclusive a categoria do veıculo,
ex: caminhoes tem velocidade maxima permitida menor do que carro de passeio, ou
motocicletas, ou veıculo de resgate. Porem, como ponto negativo ele esta disponıvel em
um numero restrito de paıses e regioes.
Restringindo nosso cenario a redes veiculares, considerando a classe de simuladores
que utilizam arquivos de traces reais para gerar a mobilidade dos nos da rede, e utilizando
o simulador de rede OMNeT+++, nos propomos o VeNeM. Um software que tem como
objetivo gerar a mobilidade dos nos da rede respeitando parametros reais, e que valida
1Google Maps, disponıvel em: https://www.google.com.br2OpenStreetMaps, disponıvel em: http://www.openstreetmap.org/
VeNeM - Gerador De Mobilidade Veicular Real 45
o framework proposto acima abrindo a comunidade diversas frentes de utilizacao.
5.3.5 VeNeM
O VeNeM determina a mobilidade dos veıculos atraves de rotas pre-configuradas. Para
isso ele realiza uma consulta da rota na API de mapas do google. Tal comportamento faz
com que o VeNeM gere a rede respeitando a topologia das estradas. Essa caracterıstica
e conseguida porque o google maps retorna a rota respeitando as direcoes que o veıculo
deve seguir. Porem, a API de mapas do google retorna somente os pontos em que
devem acontecer mudancas de direcao, ignorando os pontos intermediarios. Os efeitos
provocados por tal caracterıstica e percebido em ruas que possuem curvas acentuadas.
Como sao retornadas somente informacoes dos extremos da rua, o veıculo corta a curva
indo ate a outra extremidade em linha reta. Ainda assim, utilizar a API de mapas do
google para obter estas informacoes e uma decisao melhor do que escolher algum modelo
randomico, pois modelos randomicos os veıculos se movem de forma que nao represente
a realidade.
A partir da utilizacao da API de mapas do google, o VeNeM consegue simular o
comportamento de um veıculo respeitando os parametros retornado para cada trecho da
rota, isso acontece porque a velocidade do trecho e calculada a partir da diferenca do
tempo entre o ponto de partida e de chegada dividido pela distancia entre os pontos.
Alem disso, para os grandes centros urbanos o google consegue retornar informacao con-
siderando as condicoes do trafego em tempo real, o que pode ser visto na Figura 5.3.
Isso permite que simulacoes sejam realizadas considerando situacoes de trafego ameno
(durante a noite) e em situacoes de trafego intenso (horario de pico). Com os parametros
retornados pela api, pode-se considerar como sendo uma situacao media de comporta-
mento do motorista, porem, dados como semaforos e comportamento do motorista em
intersecoes sao descartados, pois a API introduz esta limitacao.
Quando os problemas apresentados acima tornam inviavel o uso do VeNeM para
alguma aplicacao, o VeNeM permite ainda a utilizacao de arquivos de traces. Estes
arquivos sao obtidos facilmente utilizando dispositivos de navegacao, como GPS ou ate
mesmo smartphones, que tornaram-se acessorios comuns entre os passageiros de veıculos.
A utilizacao de arquivos de traces permitem que o usuario tenha controle sobre as coor-
denadas coletadas, pegando todos os pontos necessarios para que a mobilidade do veıculo
respeite todos os limites de ruas, isso faz com que nao existam trechos da simulacao que
nao sejam cobertos, gerando a topologia da rede respeitando de forma fiel o layout das
46 VeNeM - Gerador De Mobilidade Veicular Real
Figura 5.3: Rota entre a Estacao central de metro – Belo Horizonte e Paroquiade Nossa Senhora de Fatima – Belo Horizonte (Retirada do Google Maps em02/09/2014).
ruas. Alem da precisao com relacao a macro mobilidade, os arquivos de traces refletem
as acoes tomadas pelo motorista, como por exemplo as reducoes de velocidade antes
de intersecoes, o tempo esperando o semaforo abrir, e qualquer outro evento que possa
refletir em alteracoes da micro mobilidade. Esse comportamento e desejavel durante as
simulacoes pois podem auxiliar em uma tomada de decisao. Simular uma rede igno-
rando o comportamento individual dos veıculos, ou assumindo que esse comportamento
e baseado em empirismo, pode fazer com que os resultados obtidos nao correspondam a
realidade, isso porque o comportamento do motorista e influenciado por diversos fatores,
como pontos de interesse, humor, sexo, idade e nao pode ser estimado com uma amostra
estatıstica.
As principais caracterısticas do VeNeM sao:
• Software Open Source;
• E simples e facil de ser utilizado;
• Permite que o usuario utilize traces de mobilidade real, coletados a partir de dis-
positivos de GPS;
VeNeM - Gerador De Mobilidade Veicular Real 47
• Gera padroes de mobilidade respeitando as condicoes de cada trecho da rota (Ex.:
velocidade, reducoes de velocidade);
• Permite que simulacoes sejam reproduzidas em diferentes condicoes de trafego
(Ex.: horario de pico);
• E suportado por um dos mais conceituados simuladores de redes sem fio da atua-
lidade, OMNeT++.
5.4 Consideracoes Finais
Redes veiculares tem ganhado crescente atencao da comunidade cientıfica nos ultimos
anos. Isso acontece porque ha uma crescente preocupacao em tornar viagens de carro
mais seguras. Porem, as altas velocidades que os veıculos se movem introduzem diversos
desafios nesse tipo de rede, o que tem resultado no surgimento de varias propostas de
novos algoritmos.
Avaliar essas propostas em ambiente real e inviavel, pois, alem do alto custo envol-
vido, seria necessario a mobilizacao de uma grande quantidade de pessoas. Isso faz com
que pesquisadores recorram a simulacoes para avaliarem suas propostas, o que imprime
a necessidade de simuladores que reflitam melhor as condicoes reais. A falta de um
simulador que atenda as necessidades da comunidade cientıfica e o principal motivador
dessa pesquisa.
A constante evolucao tecnologica levou dispositivos de comunicacao sem fio a todos
os lugares. Explorar os recursos oferecidos por esses dispositivos (gps, wi-fi, 3G) para
coletar informacoes de mobilidade tem se tornado cada vez mais facil. Tais caracterısticas
viabilizam a construcao de um framework para interligar o mundo simulado ao mundo
real.
O VeNeM e uma ferramenta que permite gerar a mobilidade veıcular respeitando
parametros reais, onde, as decisoes do motorista durante a viagem refletem na mobili-
dade gerada, conseguindo assim reproduzir efeitos como comportamento em intersecoes,
em semaforos, etc. Com isso, juntamente com o OMNeT++, o VeNeM nos permite
reproduzir simulacoes mais proximas da realidade, o que nos garante melhores resul-
tados ao avaliar o desempenho do protocolo proposto comparando-o com as principais
propostas de protocolos para VANETs presentes na literatura. Tal avaliacao pode ser
vista em detalhes no Capıtulo a seguir.
48
Capıtulo 6
Resultados e Discussoes
6.1 Experimentos
Apesar de ser desejavel a avaliacao de protocolos de roteamento em ambientes reais, o
alto custo de implementacao e a dificuldade em mobilizar pessoal suficiente para realizar
os experimentos tornam inviavel tal implementacao. Por esse motivo, a comunidade
cientıfica avalia os protocolos de roteamento atraves de simulacoes. Para avaliar o de-
sempenho do RouteSpray, foram realizadas simulacoes comparando-o com os protocolos
Epidemico, Spray and Wait e GeOpps, que sao os principais protocolos de roteamento
existentes para redes esparsas e redes veiculares.
Para o cenario de simulacao foram geradas 16 rotas entre os pontos de interesse da
cidade de Barbacena-MG, no Brasil. Onde, por se tratar de uma cidade que surgiu
e cresceu sem planejamento as ruas e avenidas foram construıdas de forma complexa.
Com isso, o grafo que representa tal cenario nao possui nenhum padrao, diferentemente
do grafo de Manhathan. Para a simulacao a quantidade de veıculos variou entre 5 e 100,
gerando redes com diferentes densidades. Simulacoes cujo numero de veıculos e maior
do que o numero de rotas, mais de um veıculo realiza o mesmo percurso. Nesse caso,
alem dos veıculos serem distribuıdos de forma uniforme entre as rotas, eles partem em
tempos diferentes. Considerou-se ainda que a velocidade de transmissao e maior do que
a velocidade de locomocao.
Para cada cenario, existe somente uma mensagem sendo entregue na rede ao mesmo
tempo. Ou seja, um veıculo aleatorio gera uma mensagem para um destino tambem
aleatorio. Quando a mensagem alcanca o destino, este tem como tarefa gerar uma outra
49
50 Resultados e Discussoes
mensagem para outro desistino aleatorio. Esse processo se repetea ate que o tempo de
simulacao chegue ao final. Cada cenario foi repetido 15 vezes, em cada repeticao variou-
se a aleatoriedade dos veıculos. Os resultados apresentados na proxima Secao 6.2 foram
calculados considerando um Intervalo de Confianca de 95%.
As simulacoes foram realizadas utilizado o framework MiXiM (Kopke, Swigulski,
Wessel, Willkomm, Haneveld, Parker, Visser, Lichte & Valentin 2008), que e uma ex-
tensao ao simulador de redes OMNeT++ (Varga 1999). Simulacoes de mobilidade
veicular baseadas em modelos de mobilidade randomicos, nao correspondem a reali-
dade (Gamess, Acosta & Hernandez 2012). Isso, porque a movimentacao dos veıculos
esta limitada as restricoes das ruas e avenidas. Alem disso, parametros como velocidade
e direcao sofrem variacoes. Por esse motivo, a mobilidade veicular foi gerada utilizando
o software VeNeM (Silva 2012).
Os parametros utilizados na simulacao podem ser conferidos na Tabela 6.1.
Parametros Valores
Tempo de simulacao 2700s
Playground X 2.41km
Playground Y 4.05km
Numero de nos 5, 10, 25, 50, 75, 100
Valores de L 2, 3, 6, 8, 12, 20
Frequencia de banda 2.4GHz
Potencia de transmissao 110.11mW
Atenuacao de sinal -70dBm
Tamanho do pacote 512bits
Tabela 6.1: Parametros utilizados na simulacao
No parametro tempo de simulacao, foi utilizado o valor 2700 segundos por correspon-
der ao tempo necessario para que os veıculos realizem um percurso circular, passando
por alguns pontos de interesse da cidade. Para o tamanho do playground foi utiliza-
dos os valores retornados pelo software VeNeM, e correspondem ao tamanho necessario
para cobrir todas as rotas. O parametro Valores de L varia de acordo com o numero
de nos da rede, e respeita os limites mınimos sugeridos por (Spyropoulos, Psounis &
Raghavendra 2008b). Ja os parametros referentes ao meio fısico, que sao: frequencia de
banda, potencia de transmissao, atenuacao de sinal e Tamanho do pacote, foram confi-
gurados com valores utilizados pelo protocolo 802.11b. O padrao 802.11b foi escolhido
Resultados e Discussoes 51
porque o padrao 802.11p que foi projetado para ser utilizado em redes veiculares foi
descontinuado (IEEE 2010).
6.2 Resultados
O desempenho do protocolo RouteSpray foi avaliado segundo as seguintes metricas: (i)
taxa de entrega de mensagens; (ii) ocupacao dos buffers ; (iii) quantidade de mensagens
enviadas na rede e (iv) atraso medio de entrega das mensagens. A taxa de entrega
de mensagens refere-se ao numero de mensagens entregues ao destino, e e importante
para comprovar a eficacia do protocolo. A ocupacao dos buffers e definida como a
soma de todas as mensagens armazenadas nos nos da rede, e deve ser analisada porque
dispositivos que sao utilizados em redes moveis possuem restricoes de armazenamento.
A quantidade de mensagens enviadas na rede e a soma de todas as mensagens enviadas,
incluindo as de controle, e indica a quantidade de transmissoes necessarias para garantir
a entrega das mensagens. Ja o atraso medio de entrega das mensagens e util para indicar
a eficiencia do algoritmo ao realizar o roteamento.
6.2.1 Taxa de entrega de mensagens
Quando o cenario nao impoe restricoes de armazenamento, o algoritmo Epidemico realiza
a entrega de todas as mensagens enviadas, o que o torna uma importante ferramenta de
comparacao entre os algoritmos de roteamento. Outro algoritmo conhecido pela comuni-
dade cientıfica por garantir boas taxas de entrega e provocar menor degradacao da rede,
e o Spray and Wait. Apesar de ambos os algoritmos se tratarem de boas fontes de re-
ferencias, eles sao projetados para redes esparsas, e nao se beneficiam das caracterısticas
das redes veiculares. Por esse motivo, alem do RouteSpray ser comparado com estes dois
algoritmo, ele tambem e comparado com o algoritmo GeOpss, que e um algoritmo que se
beneficia das rotas dos veıculos para realizar o roteamento de mensagens. Considerando
que o algoritmo Epidemico entrega 100% das mensagens enviadas, os algoritmo RouteS-
pray, Spray and Wait e GeOpps entregaram 87,68%, 62,61% e 12,88%, respectivamente.
Os valores obtidos sao apresentados mais detalhadamente na Figura 6.1.
A melhor taxa de entrega de mensagens e obtida pelo algoritmo RouteSpray, con-
sequencia da utilizacao das rotas dos veıculos combinada com a pulverizacao de multiplas
copias de mensagens. Ja o algoritmo GeOpps teve o menor desempenho com relacao ao
52 Resultados e Discussoes
numero de mensagens entregues. Tal resultado mostra que os algoritmos de multiplas
copias de mensagens superam os algoritmos que utilizam as informacoes de rotas. Porem,
a combinacao das duas caracterısticas mostrou-se mais eficiente do que a utilizacao de
ambas de forma individual.
Figura 6.1: Mensagens entregues na rede.
6.2.2 Ocupacao dos buffers
Como mostrado na Figura 6.2, o algoritmo Epidemico exige que os nos possuam gran-
des capacidades de armazenamento, porque cada no da rede armazena uma copia de
cada mensagem transmitida. Essa caracterıstica pode ser percebida mais claramente
observando-se as transmissoes necessarias para a rede com 100 nos onde, para entregar
15 mensagens, o algoritmo Epidemico armazenou 1493 copias destas. Ja os algoritmos
Spray and Wait e o RouteSpray, provocaram pouca ocupacao dos buffers, o que prova
a eficiencia da tecnica de spray, como podemos ver na Figura 6.3. O algoritmo RouteS-
pray obteve uma ocupacao em buffer 87,35% menor do que o Spray and Wait, pois faz
controle das mensagens armazenadas em buffer, apagando as que ja foram entregues. A
Resultados e Discussoes 53
presenca de mensagens nos buffers dos nos do algoritmo RouteSpray e um indicativo de
que a informacao de que a mensagem foi entregue ainda nao propagou o suficiente para
atingir todos os nos. O fato do algoritmo GeOpps nao provocar replicas da mensagem,
faz com que seu uso nao tenha impacto sob os buffers dos nos. Tal caracterıstica pode
ser comprovada observando a Figura 6.3.
Figura 6.2: Ocupacao do buffer : comparacao entre os tres algoritmos
6.2.3 Quantidade de mensagens enviadas na rede
Conforme apresentado, a utilizacao de mensagens de controle pelo algoritmo RouteS-
pray permite melhorar as taxas de entrega de dados e controlar a ocupacao do buffer.
Porem, elas introduzem um custo adicional a rede, provocando um numero maior de
transmissoes de mensagens. Tal caracterıstica pode ser vista na Figura 6.4. Porem, as
mensagens de controle possuem uma pequena carga de dados, pois transportam somente
informacoes das mensagens que ja foram entregues na rede, o que faz com que o numero
de bytes transmitidos na rede provoque menos impacto do que algoritmos epidemicos,
cujos todas as mensagens possuem carga de dados. Entretanto, varios recursos (buffers
54 Resultados e Discussoes
Figura 6.3: Ocupacao do buffer entre os algoritmos que utilizam a tecnica de“spray”.
de enfileiramento de pacotes, canal de transmissao, processamento para calcular rotas
e gerar cabecalhos, etc) sao afetados pelo excesso de transmissoes, pois transmissoes de
mensagens disputam esses recursos em todos os nos aos quais estao envolvidos.
6.2.4 Atraso medio de entrega das mensagens
O tempo que a mensagem precisa para alcancar o destino e outras caracterıstica impor-
tante de ser analisada. Com essa informacao e possıvel avaliar a eficiencia dos algoritmos
ao rotear as mensagens ate seus destinos. Se observarmos a Figura 6.5, veremos que o
algoritmo GeOpps demora mais tempo para entregar a mensagem ao destino, carac-
terıstica provocada por se tratar de um algoritmo de uma unica copia, o que e esperado,
pois o algoritmo nao explora caminhos alternativos aumentando as chances de entre-
gar a mensagem. Ja, o fato do algoritmo Epidemico enviar a mensagem para todos
os caminhos possıveis faz com que a mensagem siga o menor caminho ate o destino
garantindo-lhe o menor tempo de entrega. Ao analisarmos os casos em que a rede tem 5
Resultados e Discussoes 55
Figura 6.4: Mensagens enviadas na rede.
e 10 veıculos, perceberemos que o algoritmo RouteSpray possui tempo medio de entrega
de mensagens maior do que o Algoritmo Spray and Wait, porem, tais valores acontecem
porque o algoritmo RouteSpray entrega mais mensagens. Ja nesses casos, o algoritmo
GeOpps nao realiza a entrega de nenhuma mensagem, o que justifica a ausencia dos
valores no grafico.
56 Resultados e Discussoes
Figura 6.5: Tempo medio de entrega de mensagens.
Capıtulo 7
Conclusoes
7.1 Conclusoes e Trabalhos Futuros
Roteamento em redes veiculares ainda e um problema em aberto. Diversos algoritmos
surgem para cenarios e condicoes especıficas. Considerando que em redes VANETs temos
recursos que nao sao presentes em outros tipos de redes, e que com isso conseguimos
informacoes que podem ser utilizadas no roteamento sem custo adicional a rede, foi
apresentado neste estudo, o algoritmo RouteSpray. Este se mostrou mais eficiente do
que os algoritmos ate entao apresentados pela comunidade cientıfica para roteamento
veicular, utilizando como base a rota dos veıculos.
Apesar do desafio de rotear pacotes por redes altamente dispersas, o que e comum
em redes VANETs, o algoritmo RouteSpray garantiu uma boa taxa de entrega de mensa-
gens, superando algoritmos cuja eficiencia ja foi comprovada pela comunidade cientıfica.
Alem da boa taxa de entrega de mensagens, o algoritmo RouteSpray demandou pouca
utilizacao de espaco de armazenamento, podendo ser utilizado em dispositivos com re-
cursos restritos.
O algoritmo RouteSpray tem um boa aplicacao em redes onde se conhece a rota dos
veıculos. Um exemplo pratico de uma boa utilizacao seria em empresas de transporte,
como empresas de onibus, de taxis ou transportadoras. O algoritmo RouteSpray oferece
a possibilidade de comunicacao dinamica mesmo em situacoes nao rotineiras onde o
roteamento programado falharia, como quando ocorrem atrasos por razao de mudancas
no transito, pneu do veıculo furado, etc.
57
58
Referencias Bibliograficas
Allal, S. & Boudjit, S. (2012). Geocast routing protocols for vanets: Survey and gui-
delines, Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS),
2012 Sixth International Conference on, pp. 323–328.
Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, R., Scott, K., Fall, K. & Weiss,
H. (2007). Delay-tolerant networking architecture, RFC 4838 (Informational).
URL: http://www.ietf.org/rfc/rfc4838.txt
Cerf, V. G., Burleigh, S. C., Hooke, A. J., Torgerson, L., Durst, R. C., Scott, K. L., Fall,
K., Travis, E. J. & Weiss, H. S. (2002). Delay-tolerant network architecture: The
evolving interplanetary internet.
URL: http://www.ipnsig.org/reports/draft-irtf-ipnrg-arch-01.txt
Fall, K. (2003). A delay-tolerant network architecture for challenged internets, Pro-
ceedings of the 2003 Conference on Applications, Technologies, Architectures, and
Protocols for Computer Communications, SIGCOMM ’03, ACM, New York, NY,
USA, pp. 27–34.
URL: http://doi.acm.org/10.1145/863955.863960
Gamess, E., Acosta, L. & Hernandez, D. (2012). Analyzing routing protocol perfor-
mance versus bitrate in vehicular networks, Global Information Infrastructure and
Networking Symposium (GIIS), 2012, pp. 1–4.
IEEE (2010). IEEE Standard Association.
URL: http://standards.ieee.org/findstds/standard/802.11p-2010.html
Jarupan, B. & Ekici, E. (2010). Prompt: A cross-layer position-based communication
protocol for delay-aware vehicular access networks, Ad Hoc Netw. 8(5): 489–505.
URL: http://dx.doi.org/10.1016/j.adhoc.2009.12.006
59
60 REFERENCIAS BIBLIOGRAFICAS
Johnson, D. & Maltz, D. (1996). Dynamic source routing in ad hoc wireless networks,
in T. Imielinski & H. Korth (eds), Mobile Computing, Vol. 353 of The Kluwer
International Series in Engineering and Computer Science, Springer US, pp. 153–
181.
Karp, B. & Kung, H. T. (2000). Gpsr: greedy perimeter stateless routing for wireless
networks, Proceedings of the 6th annual international conference on Mobile compu-
ting and networking, MobiCom ’00, ACM, New York, NY, USA, pp. 243–254.
Kopke, A., Swigulski, M., Wessel, K., Willkomm, D., Haneveld, P. T. K., Parker, T.
E. V., Visser, O. W., Lichte, H. S. & Valentin, S. (2008). Simulating wireless and
mobile networks in omnet++ the mixim vision, Proceedings of the 1st internati-
onal conference on Simulation tools and techniques for communications, networks
and systems & workshops, Simutools ’08, ICST (Institute for Computer Sciences,
Social-Informatics and Telecommunications Engineering), ICST, Brussels, Belgium,
Belgium, pp. 71:1–71:8.
URL: http://dl.acm.org/citation.cfm?id=1416222.1416302
Lee, K. & Gerla, M. (2010). Opportunistic vehicular routing, Wireless Conference (EW),
2010 European, pp. 873–880.
Lee, K., Haerri, J., Lee, U. & Gerla, M. (2007). Enhanced perimeter routing for ge-
ographic forwarding protocols in urban vehicular scenarios, Globecom Workshops,
2007 IEEE, pp. 1–10.
Leontiadis, I. & Mascolo, C. (2007). Geopps: Geographical opportunistic routing for
vehicular networks, IEEE International Symposium on a World of Wireless, Mobile
and Multimedia Networks (WoWMoM 2007), pp. 1–6.
Li, F. & Wang, Y. (2007). Routing in vehicular ad hoc networks: A survey, IEEE
Vehicular Technology Magazine 2(2): 12–22.
Lochert, C., Mauve, M., Fussler, H. & Hartenstein, H. (2005). Geographic routing in
city scenarios, SIGMOBILE Mob. Comput. Commun. Rev. 9(1): 69–72.
URL: http://doi.acm.org/10.1145/1055959.1055970
Luo, Y., Zhang, W. & Hu, Y. (2010). A new cluster based routing protocol for vanet,
Networks Security Wireless Communications and Trusted Computing (NSWCTC),
2010 Second International Conference on, Vol. 1, pp. 176–180.
REFERENCIAS BIBLIOGRAFICAS 61
Naumov, V. & Gross, T. (2007). Connectivity-aware routing (car) in vehicular ad-
hoc networks, INFOCOM 2007. 26th IEEE International Conference on Computer
Communications. IEEE, pp. 1919–1927.
Oliveira, C. T. (2007). Redes Tolerantes a Atrasos e Desconexoes., Sociedade Brasileira
de Computacao (SBC).
Perkins, C. & Royer, E. (1999). Ad-hoc on-demand distance vector routing, Second IEEE
Workshop on Mobile Computing Systems and Applications (WMCSA), pp. 90–100.
Schmilz, R., Leiggener, A., Festag, A., Eggert, L. & Effelsberg, W. (2006). Analysis of
path characteristics and transport protocol design in vehicular ad hoc networks,
Vehicular Technology Conference, 2006. VTC 2006-Spring. IEEE 63rd, Vol. 2,
pp. 528–532.
Scott, K. & Burleigh, S. (2007). Bundle protocol specification, RFC 5050 (EXPERI-
MENTAL).
URL: http://www.ietf.org/rfc/rfc5050.txt
Seet, B.-C., Liu, G., Lee, B.-S., Foh, C.-H., Wong, K.-J. & Lee, K.-K. (2004). A-
star: A mobile ad hoc routing strategy for metropolis vehicular communications, in
N. Mitrou, K. Kontovasilis, G. Rouskas, I. Iliadis & L. Merakos (eds), Networking
2004, Vol. 3042 of Lecture Notes in Computer Science, Springer Berlin Heidelberg,
pp. 989–999.
Silva, M. J. (2012). VeNeM: vehicular network mobility.
URL: https://github.com/badriciobq/VeNeM/
Skordylis, A. & Trigoni, N. (2008). Delay-bounded routing in vehicular ad-hoc networks,
Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking
and Computing, MobiHoc ’08, ACM, New York, NY, USA, pp. 341–350.
URL: http://doi.acm.org/10.1145/1374618.1374664
Spyropoulos, T., Psounis, K. & Raghavendra, C. (2008a). Efficient routing in intermit-
tently connected mobile networks: The single-copy case, Networking, IEEE/ACM
Transactions on 16(1): 63–76.
Spyropoulos, T., Psounis, K. & Raghavendra, C. S. (2008b). Efficient routing in inter-
mittently connected mobile networks: the multiple-copy case, IEEE/ACM Trans.
Netw. 16(1): 77–90.
62 REFERENCIAS BIBLIOGRAFICAS
Tanenbaum, A. (2003). Redes de computadoras, Editorial Alhambra S. A. (SP).
Taysi, Z. & Yavuz, A. (2012). Routing protocols for geonet: A survey, Intelligent Trans-
portation Systems, IEEE Transactions on 13(2): 939–954.
Tchakountio, F. & Ramanathan, R. (2001). Tracking highly mobile endpoints, Pro-
ceedings of the 4th ACM international workshop on Wireless mobile multimedia,
WOWMOM ’01, ACM, New York, NY, USA, pp. 83–94.
Toor, Y., Muhlethaler, P. & Laouiti, A. (2008). Vehicle ad hoc networks: applications
and related technical issues, Communications Surveys Tutorials, IEEE 10(3): 74–
88.
Vahdat, A. & Becker, D. (2000). Epidemic routing for partially-connected ad hoc
networks, Technical report.
Varga, A. (1999). Using the omnet++ discrete event simulation system in education,
IEEE Transactions on Education 42(4): 11 pp.–.
Voyiatzis, A. (2012). A survey of delay- and disruption-tolerant networking applications,
Journal of Internet Engineering, 5(1): 331–344.
Zhao, J. & Cao, G. (2008). Vadd: Vehicle-assisted data delivery in vehicular ad hoc
networks, Vehicular Technology, IEEE Transactions on 57(3): 1910–1922.