Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
PONTIFICIA UNIVERSIDADE CATOLICA DE MINAS GERAIS
Programa de Pos-Graduacao em Informatica
Luiz Henrique da Costa Silva
UM PROTOCOLO DE DISSEMINACAO DE DADOS EM
REDES VEICULARES ORIENTADO A DENSIDADE DE
VEICULOS
Belo Horizonte
2020
Luiz Henrique da Costa Silva
UM PROTOCOLO DE DISSEMINACAO DE DADOS EM
REDES VEICULARES ORIENTADO A DENSIDADE DE
VEICULOS
Dissertacao apresentada ao Programa dePos-Graduacao em Informatica da PontifıciaUniversidade Catolica de Minas Gerais, comorequisito parcial para obtencao do tıtulo deMestre em Informatica.
Orientadora:Prof.a Dr.a Raquel Apare-cida de Freitas Mini
Belo Horizonte
2020
FICHA CATALOGRÁFICA
Elaborada pela Biblioteca da Pontifícia Universidade Católica de Minas Gerais
Silva, Luiz Henrique da Costa
S586p Um protocolo de disseminação de dados em redes veiculares orientado à
densidade de veículos / Luiz Henrique da Costa Silva. Belo Horizonte, 2020.
77 f. : il.
Orientadora: Raquel Aparecida de Freitas Mini
Dissertação (Mestrado) - Pontifícia Universidade Católica de Minas Gerais.
Programa de Pós-Graduação em Informática
1. Sistemas inteligentes de veículos rodoviários. 2. Trânsito -
Congestionamento. 3. Sistemas de comunicação móvel. 4. Sistemas de transmissão
de dados. 5. Protocolo de aplicação sem fio (Protocolo de rede de computador). 6.
Métodos de simulação. I. Mini, Raquel Aparecida de Freitas. II. Pontifícia
Universidade Católica de Minas Gerais. Programa de Pós-Graduação em
Informática. III. Título.
CDU: 681.3.01:621.39
Ficha catalográfica elaborada por Fabiana Marques de Souza e Silva - CRB 6/2086
Luiz Henrique da Costa Silva
UM PROTOCOLO DE DISSEMINACAO DE DADOS EM
REDES VEICULARES ORIENTADO A DENSIDADE DE
VEICULOS
Dissertacao apresentada ao Programa dePos-Graduacao em Informatica como re-quisito parcial para qualificacao ao Graude Mestre em Informatica pela PontifıciaUniversidade Catolica de Minas Gerais.
Prof.a Dr.a Raquel Aparecida de FreitasMini – PUC Minas (Orientadora)
Prof. Dr. Joao Guilherme Maia de Menezes– UFMG
Prof.a Dr.a Fatima de Lima ProcopioDuarte Figueiredo – PUC MINAS
Belo Horizonte, 17 de abril de 2020.
Para minha famılia
AGRADECIMENTOS
Sou grato a Deus antes de qualquer outra fonte de auxılio. Sua Palavra tem sido
fonte de sabedoria desde muito antes de eu existir, e tenho aprendido muito com ela
mesmo nos dias de hoje, e ainda ha muito o que aprender.
Pai, mae, irmaos e irma, sou muito grato e feliz por estar no meio de voces em toda
minha vida, e mesmo fisicamente distante, tenho a certeza de que posso dividir minhas
necessidades e minhas felicidades com voces, sei que sempre me socorrerao e se alegrarao
comigo.
A todos familiares, sem excecao (tios e tias, primos e primas, e etc), obrigado.
Voces participaram desta etapa, as vezes fisicamente presentes, as vezes via WhatsApp.
Fato e que os momentos que pude falar com voces foram momentos de genuına alegria.
Rukia e Bolinha, voces me alegraram e cuidaram de mim, provavelmente sem saber o
que estavam fazendo. Desculpe pelas vezes que gritei com voces, pretendo fazer isso por
muitos anos mais.
Agradeco a minha orientadora Raquel, pela paciencia e dedicacao mesmo no nosso
primeiro contato, quando era apenas a professora de P.A.A. Pude aprender como seu
aluno na graduacao, como orientado no trabalho de conclusao de curso da graduacao e
agora orientado no mestrado. Foram muitos anos de sofrimento nas suas maos, portanto,
muito obrigado.
Obrigado Felipe, pela oportunidade de conhece-lo. Pelo ensino como professor e
como coorientador. Obrigado pelo apoio, paciencia e amizade. Mais que um profissional
fundamental para o alcance deste objetivo, voce me apoiou em questoes pessoais e me
auxiliou em decisoes difıceis. Que Deus lhe recompense conforme seu coracao.
A todos envolvidos no Programa de Pos-Graduacao em Informatica, professores,
alunos e funcionarios, que por vezes chamaram minha atencao para detalhes importantes
da vida como um todo, muito obrigado.
“A simplicidade e o ultimo grau de sofistica-
cao.”
Leonardo Da Vinci
RESUMO
Redes veiculares (Vehicular Ad Hoc Networks - VANETs) sao um tipo de redes forma-
das por veıculos automotores com capacidade de comunicacao, processamento e sensoria-
mento. O objetivo destas redes e o aumento da seguranca e desempenho do transito no que
tange a sua eficiencia e a sua resiliencia, alem de prover entretenimento aos passageiros.
Aplicacoes nesses contextos permitirao que usuarios de vias urbanas ou rodovias ganhem
tempo e conforto em seus deslocamentos. Uma atividade demandada por aplicacoes em
redes veiculares e a atividade de disseminacao de dados. A disseminacao de dados pode
ser expressa como a capacidade de entrega de uma mensagem especıfica a um conjunto
de veıculos interessados na informacao. Na literatura, diversos estudos foram feitos sobre
o tema, em especial os que consideram, unicamente, o modo de comunicacao de veıculo
para veıculo (V2V). Entretanto, estudos recentes no ambito da disseminacao de dados
em redes veiculares, tem buscado dar suporte a coexistencia de multiplas tecnologias de
comunicacao sem fio para maximizar a utilizacao do recurso, estabilidade e robustes, pro-
vendo qualidade de servico na comunicacao entre os veıculos. Neste contexto, o presente
trabalho propoe o protocolo TBD (Trajectory Based Dissemination) que considera a uti-
lizacao de parte da infraestrutura existente nas cidades, a rede celular, como uma das
tecnologias de comunicacao sem fio dando suporte a comunicacao veicular no modo V2V,
a fim de desempenhar a entrega de mensagens em cenarios urbanos. Resultados de simu-
lacao, avaliados em cenarios de diferentes densidades, mostraram que e possıvel reduzir
em mais de 50% o numero de veıculos envolvidos na comunicacao, mantendo a taxa de
entrega superior a 90% dos veıculos interessados na informacao.
Palavras-chave: Redes Veiculares. Disseminacao de dados. Protocolo. Trajetoria.
ABSTRACT
Vehicular Ad Hoc Networks (VANETs) are a type of network formed by automotive
vehicles with communication, processing and sensing capabilities. The purpose of these
networks is to increase traffic safety and performance with regard to their efficiency and
resilience plus passenger entertainment. Applications in these two contexts will allow
users of urban roads or highways to gain time and comfort in their travels. One activity
demanded by applications in vehicular networks is the data dissemination activity. Data
dissemination can be expressed as the ability to deliver a specific message to a set of
vehicles interested in the information. In the literature, several studies have been done
on the subject, especially those that consider only the vehicle-to-vehicle (V2V) mode of
communication. However, more recent data dissemination studies in vehicular networks
have sought to support the coexistence of multiple wireless communication technologies
to maximize resource utilization, stability, and robustness, providing quality of service in
vehicle communication. In this context, the present work propose the TBD protocol that
make use of part of the existing infrastructure in cities, the cellular network, as one of the
wireless communication technologies supporting vehicular communication in V2V mode
to perform message delivery in urban scenarios. Simulation results evaluated in scenarios
of different densities showed that it is possible to reduce by more than 50 % the number of
vehicles involved in the communication, keeping the delivery rate above 90 % of vehicles
interested in the information.
Keywords: Vehicular Ad Hoc Network. Data Dissemination. Protocol. Trajectory.
LISTA DE FIGURAS
FIGURA 1 – Mortes em acidentes de transito por 100 mil habitantes . . . . . . . . . . . . . 17
FIGURA 2 – Origem das mensagens em funcao da RoI . . . . . . . . . . . . . . . . . . . . . . . . . 18
FIGURA 3 – Ambiente de redes veiculares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
FIGURA 4 – Cenario de baixa densidade de veıculos . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
FIGURA 5 – Cenario de alta densidade de veıculos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
FIGURA 6 – Taxonomia para divisao dos protocolos da literatura . . . . . . . . . . . . . . . 33
FIGURA 7 – Zona de Preferencia do protocolo GEDDAI . . . . . . . . . . . . . . . . . . . . . . . 34
FIGURA 8 – Diferentes regioes do protocolo Geo-Orientado . . . . . . . . . . . . . . . . . . . . . 35
FIGURA 9 – Zona de preferencia do protocolo CARRO . . . . . . . . . . . . . . . . . . . . . . . . 38
FIGURA 10 – Zona de retransmissao do protocolo HyDiAck . . . . . . . . . . . . . . . . . . . . 40
FIGURA 11 – Cenario para o qual aplica-se o TBD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
FIGURA 12 – Matriz de densidades de veıculos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
FIGURA 13 – Grafo com pesos nos vertices, convertidos em valores de arestas . . . . . 47
FIGURA 14 – Transmissao broadcast direcionada atraves do cone de retransmissao . 49
FIGURA 15 – Cenario de grid 2000 x 1000 metros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
FIGURA 16 – Intersecoes do grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
FIGURA 17 – Cenario de Belo Horizonte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
FIGURA 18 – Cenario de Belo Horizonte com bloqueio . . . . . . . . . . . . . . . . . . . . . . . . . 57
FIGURA 19 – Grafico da taxa de entrega na ROI no cenario em grid . . . . . . . . . . . . . 60
FIGURA 20 – Grafico do numero de mensagens duplicadas no cenario em grid . . . . . 61
FIGURA 21 – Grafico do percentual de veıculos transmissores no cenario em grid . . 62
FIGURA 22 – Grafico do atraso medio no cenario em grid . . . . . . . . . . . . . . . . . . . . . . 62
FIGURA 23 – Grafico do numero de saltos no cenario em grid . . . . . . . . . . . . . . . . . . . 63
FIGURA 24 – Taxa de entrega no interior da ROI no cenario de Belo Horizonte . . . 64
FIGURA 25 – Numero de mensagens duplicadas e percentual de veıculos transmissores 64
FIGURA 26 – Atraso medio na transmissao da mensagem e numero medio de saltos
ate a ROI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
LISTA DE TABELAS
TABELA 1 – Protocolos da literatura e suas caracterısticas . . . . . . . . . . . . . . . . . . . . . 42
TABELA 2 – Resumo dos parametros de simulacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
TABELA 3 – Parametros de adaptacao do cone de retransmissao . . . . . . . . . . . . . . . . 58
TABELA 4 – Diferencas entre as solucoes adotadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
TABELA 5 – Fatores e valores assumidos nos dois nıveis. . . . . . . . . . . . . . . . . . . . . . . . 68
TABELA 6 – Representacao adotada para exibicao dos resultados. . . . . . . . . . . . . . . . 68
TABELA 7 – Resultados do projeto fatorial para variavel resposta mensagens recebidas. 69
TABELA 8 – Resultados do projeto fatorial para variavel resposta mensagens trans-
mitidas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
TABELA 9 – Resultados do projeto fatorial para variavel resposta colisoes de men-
sagens. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
LISTA DE ABREVIATURAS E SIGLAS
AID - Adaptive Approach for Information Dissemination
CARRO - Context-Aware Routing Protocol
CPB - Clustering and Probabilistic Broadcasting
DDBC - Data Dissemination Protocol Based on Centrality
DV-CAST - Distributed Vehicular Broadcast
ERB - Estacao Radio Base
GEDDAI - Geographical Data Dissemination for Alert Information
GPS - Global Positioning System
IEEE - Institute of Electrical and Electronic Engineers
ITS - Intelligent Transport Systems
LTE - Long Term Evolution
MANET - Mobile Ad-hoc Networks
OBU - Onboard Unit
OMNET++ - Objective Modular Network Testbed in C++
ROI - Region Of Interest
RSU - Road Side Unit
SUMO - Simulation of Urban Mobility
TA - Thrusted Authority
TBD - Trajectory-based Dissemination
TBF - Trajectory-based Forwarding
TEDD - Trajectory and Energy-based Data Dissemination
TLCB - Two-level Cluster Based
TTL - Time-to-Live
UV-CAST - Urban Vehicular Broadcast
V2I - Vehicle-to-Infrastructure
V2V - Vehicle-to-Vehicle
V2X - Vehicle-to-Everything
VANET - Vehicle Ad-hoc Networks
VEINS - Vehicles In Network Simulation
VISIONS - Vehicular communication Improvement: Solution based on IMS Operational
Nodes and Services
VMASC - Vehicular Multihop Algorithm for Stable Clustering
VOV - Video Over VANETs
WHO - World Health Organization
WSN - Wireless Sensor Network
5GAA - 5G Automotive Association
SUMARIO
1 INTRODUCAO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1 Motivacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Organizacao da Dissertacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 FUNDAMENTACAO TEORICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Redes Veiculares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Disseminacao de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2 Problemas em Disseminacao de Dados . . . . . . . . . . . . . . . . . . . . . . 24
2.2.3 Estrategias para Tratamento dos Problemas em Disseminacaode Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.4 Estrategia para Solucao do Problema de Particoes na Rede . . . . 28
2.3 Consideracoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 TRABALHOS RELACIONADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1 Disseminacao em Curva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Disseminacao em Redes Veiculares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.1 Disseminacao baseada em Informacoes a Bordo . . . . . . . . . . . . . . 32
3.2.2 Disseminacao baseada em Informacoes Locais . . . . . . . . . . . . . . . 36
3.2.2.1 Solucao para problema de particoes na rede. . . . . . . . . . . . . . . . . . . 36
3.2.2.2 Nao solucao para problema de particoes na rede . . . . . . . . . . . . . . 38
3.2.3 Disseminacao baseada em Informacoes Globais . . . . . . . . . . . . . . 39
3.3 Consideracoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 DISSEMINACAO BASEADA EM TRAJETORIA . . . . . . . . . . . . . . . . . . . 43
4.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Participacao da Rede Celular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3 Transmissao direcionada via broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.4 Funcionamento basico do protocolo TBD . . . . . . . . . . . . . . . . . . . . . . 50
5 AVALIACAO DE DESEMPENHO E RESULTADOS . . . . . . . . . . . . . . . . . 53
5.1 Simulacao do Protocolo TBD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.2 Cenario de Simulacao em grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.1.3 Cenario de Belo Horizonte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.1.4 Parametros de Simulacao para Cenario de grid . . . . . . . . . . . . . . . 56
5.1.5 Parametros de Simulacao para Cenario de Belo Horizonte . . . . 57
5.1.6 Metricas de avaliacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.1.7 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.7.1 Resultados para o cenario de Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.7.2 Resultados para o cenario de Belo Horizonte . . . . . . . . . . . . . . . . . . 63
5.2 Projeto Experimental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.2 Metodologia dos Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2.3 Obtencao e Caracterizacao dos Dados . . . . . . . . . . . . . . . . . . . . . . 66
5.2.4 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6 CONCLUSAO E TRABALHOS FUTUROS . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.1 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
REFERENCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
15
1 INTRODUCAO
1.1 Motivacao
Redes veiculares (Vehicular Ad Hoc Networks - VANETs) sao um tipo de redes
formadas por veıculos automotores com capacidade de comunicacao, processamento e
sensoriamento. Nessas redes, os nos podem ser carros, onibus, motos e outros veıculos
com interface de comunicacao sem fio. Esses nos podem obter dados atraves da comu-
nicacao com outros veıculos (Vehicle-to-Vehicle - V2V), com infraestruturas (Vehicle-to-
Infrastructure - V2I) ou ainda atraves da Internet. Essas redes tem sido objeto de varios
estudos e nos ultimos anos o termo redes veiculares pode ser utilizado para referir-se a um
conjunto de tecnologias de comunicacao sem fio que utilizadas conjuntamente promovem
qualidade de comunicacao entre veıculos (CHEN et al., 2017). Este conjunto de tecnolo-
gias engloba as unidades de comunicacao a bordo dos veıculos (on-board units - OBU), a
infraestrutura das cidades e rodovias (roadside units - RSU) e as redes celulares que po-
dem ser referidas como LTE (Long Term Evolution), LTE-Advanced e futuras redes 5G.
As redes veiculares apresentam grande potencial em oferecer melhorias nos servicos de
transporte, trafego seguro e entretenimento, alem da contribuicao para o desenvolvimento
de cidades inteligentes (JALOOLI; SONG; WANG, 2019).
Diferentes aplicacoes em redes veiculares apresentam diferentes requisitos da rede,
no entanto, apresentam em comum a necessidade de um servico para a entrega de men-
sagens aos nos de interesse da aplicacao. Algumas aplicacoes podem ter como objetivo
atingir apenas alguns nos, que estao no interior de uma regiao de interesse (Region of
Interest - ROI), enquanto outras aplicacoes podem apresentar a necessidade de entregar
a mensagem em toda a cidade. Por exemplo, numa aplicacao comercial, pode interessar a
um comerciante que os motoristas num raio de alguns quilometros saibam da ocorrencia
de evento promocional nos proximos minutos, mas nao e seu objetivo que essa mensagem
alcance o outro lado da cidade. Por outro lado, numa aplicacao de seguranca pode inte-
ressar a todos envolvidos num determinado evento que a informacao seja alcancada por
um numero esperado de veıculos, cujos condutores podem se envolver em alguma especie
de risco. Por exemplo, uma aplicacao de seguranca que emite uma notificacao rapida de
um acidente de transito em uma rodovia permitiria que os motoristas proximos se deslo-
16
cassem com cautela. Os mais distantes seriam capazes de mudar sua trajetoria a fim de
evitar um congestionamento, e os servicos de urgencia poderiam ser alertados a iniciarem
os trabalhos de deslocamento antes que uma ligacao telefonica os acionasse. O servico
descrito e chamado de disseminacao de dados e consiste no envio de mensagens a partir
de uma fonte para todos os veıculos localizados dentro de uma regiao geografica (CUNHA
et al., 2014). A disseminacao de dados tem como objetivo alcancar muitos nos da rede
numa ROI, com uma baixa latencia na transmissao, reduzindo o numero de mensagens
duplicadas alem do nao envolvimento de veıculos nao interessados na mensagem.
A seguranca no transito e um dos principais aspectos em que as redes veiculares
beneficiara os condutores de veıculos. As aplicacoes neste sentido dependem da ativi-
dade de disseminacao de dados, por este motivo, o tema tem sido bastante estudado pela
comunidade cientıfica. Em 2013, a Organizacao Mundial de Saude publicou um relato-
rio (W.H.O., 2013) que apresenta o atual estado global da seguranca no transito. De
acordo com o relatorio, cerca de 1,24 milhao de pessoas morrem em acidentes de transito
todos os anos. Conforme o grafico da Figura 1, o numero e maior na regiao africana e
menor na regiao europeia. Garantir a entrega de notificacoes de seguranca em tempo
habil apresenta potencial para uma grande reducao nestes numeros. Um estudo apresen-
tado em (TOOR et al., 2008) mostrou que aplicacoes de seguranca em redes veiculares
podem reduzir acidentes em cerca de 60% se capazes de informar aos condutores acerca
dos eventos com cerca de 0,5 segundo de antecedencia. A disseminacao de dados e a tarefa
que se propoe a informar aos condutores em tempo suficiente para a tomada de decisoes
relacionadas a informacao transmitida, o que pode reduzir drasticamente a quantidade de
acidentes.
Diversas propostas de protocolos para disseminacao de dados tem sido apresen-
tadas na literatura e buscam tratar problemas em cenarios urbanos e de rodovias, de
diferentes densidades. Mais recentemente, com o advento das redes de 5a Geracao e os
novos recursos de comunicacao voltados para as redes veiculares, um problema que surge
e a integracao das tecnologias existentes com as novas, o que permitira um avanco factıvel
para implantacao das redes veiculares, fornecendo condicoes para o desenvolvimento das
aplicacoes cruciais para melhoria da seguranca no transito.
No que tange a cenarios reais, em uma aplicacao de seguranca, um veıculo de
emergencia pode precisar comunicar-se com uma regiao geografica local de acidente e nao
necessariamente estar no interior da regiao de interesse, embora a caminho. Numa outra
aplicacao, de melhoria do desempenho do trafego, pode-se necessitar da comunicacao entre
distantes regioes geograficas para obter informacoes de densidade do trafego, contribuindo
para a melhor escolha de rotas para os condutores de veıculos. Mesmo em aplicacoes de
prioridade inferior, como aplicacoes comerciais de propaganda, um evento que ocorre num
lado da cidade pode interessar veıculos/condutores de regioes mais distantes, que nao
17
Figura 1 – Mortes em acidentes de transito por 100 mil habitantes
Fonte: Adaptada pelo Autor de (W.H.O., 2013)
conhecem a informacao.
Assim sendo, este trabalho se propoe a apresentar o protocolo de disseminacao
de dados TBD (Trajectory Based Dissemination) que utiliza infraestrutura existente na
cidade para efetuar a disseminacao de mensagens independente de sua origem, consu-
mindo menos recursos de rede e alcancando apenas os veıculos realmente interessados na
mensagem.
1.2 Objetivo
O objetivo deste trabalho e desenvolver um protocolo de disseminacao de dados
capaz de entregar mensagens aos veıculos interessados ainda que a origem da mensagem
nao esteja na regiao de interesse. A Figura 2 ilustra este objetivo, em que On representam
diferentes origens de mensagens num dado cenario em redes veiculares e a regiao demar-
cada em verde representa a regiao de interesse. O protocolo ira integrar comunicacao
V2V e a comunicacao V2I em uma abordagem que utiliza a rede celular, infraestrutura
atualmente existente nas cidades, para a obtencao de informacoes sobre as densidades de
veıculos nos diferentes locais do mapa. A densidade e obtida atraves das submissoes feitas
por cada veıculo, em intervalos de tempo definidos, de suas coordenadas geograficas para
um servidor, cujo acesso e feito pela comunicacao via rede celular. As principais carac-
18
terısticas deste protocolo sao a utilizacao da rede celular para estimar com precisao as
densidades de veıculos no mapa e a utilizacao dessa informacao de densidade para definir
o caminho que a mensagem a ser disseminada deve percorrer ate a regiao de interesse.
Alem disso, este trabalho se propoe a identificar e a analisar fatores que impactam
o desempenho da disseminacao de dados considerando as metricas de taxa de mensagens
transmitidas e a taxa de mensagens recebidas.
Figura 2 – Cenario em que diferentes locais origens de mensagens (On) devemalcancar os veıculos numa regiao de interesse
Fonte: Proprio Autor
1.3 Organizacao da Dissertacao
Esta dissertacao esta organizada da seguinte forma: no Capıtulo 2 e apresentado o
referencial teorico abordando a disseminacao de dados em redes veiculares e seus proble-
mas classicos. O Capıtulo 3 apresenta alguns trabalhos relacionados e alguns detalhes das
estrategias implementadas. O Capıtulo 4 apresenta a solucao proposta neste trabalho.
No Capıtulo 5 sao apresentados os parametros de simulacao, as metricas e os resultados
da avaliacao do protocolo. Por fim, o Capıtulo 6 apresenta a conclusao do trabalho e
consideracoes para trabalhos futuros.
19
2 FUNDAMENTACAO TEORICA
Este capıtulo foi dividido em duas partes: a Secao 2.1 introduz o assunto redes
veiculares e suas aplicacoes, em seguida a Secao 2.2 descreve a atividade de disseminacao
de dados em redes veiculares, seus problemas classicos e situacoes em que ocorrem.
2.1 Redes Veiculares
As redes ad-hoc veiculares (vehicular ad-hoc networks - VANETs) ou simplesmente
redes veiculares, sao redes formadas por veıculos automotores, equipados com dispositivo
de comunicacao sem fio com capacidade de processamento e sensoriamento. Redes veicu-
lares sao um topico em sistemas de transporte inteligente (Intelligent Transport Systems -
ITS) alvo de grande interesse da comunidade academica em razao do seu enorme potencial
em prover aplicacoes de conforto e seguranca aos condutores de veıculos. Pode-se defi-
nir as redes veiculares como auto-organizadas redes distribuıdas de veıculos que coletam,
armazenam, processam e distribuem informacoes que podem ser utilizadas em aplicacoes
de conforto e seguranca para motoristas e passageiros (LU; QU; LIU, 2019; SHARMA;
AWASTHI, 2018).
Como descrevem os autores de (LU; QU; LIU, 2019), essas redes sao compostas
primariamente por unidades a bordo dos veıculos (onboard units - OBUs), unidades esta-
cionarias ao longo das vias (roadside units - RSUs) e uma autoridade confiavel (trusted
authority - TA), responsavel pela autenticidade e seguranca na comunicacao. Os veıcu-
los sao equipados com OBUs, dispositivo que os permite processamento, sensoriamento,
comunicacao com outros veıculos na rede e armazenamento de informacoes. As RSUs
sao unidades com a mesma capacidade de comunicacao, sensoriamento e processamento
que as OBUs e que contribuem para o aumento do alcance das redes veiculares alem de
conectar a rede de veıculos com a Internet atraves da rede infraestruturada.
As grandes vantagens dessas redes sao elencadas por (ONISHI, 2018) como sendo:
(i) baixa latencia na comunicacao e, (ii) a nao necessidade de infraestrutura. Entretanto,
o atual contexto dos estudos em tecnologias de comunicacao conduzem as redes veiculares
a integracao com as redes de 5a Geracao (5G) que apresentam a necessidade de lidar
com 1000 vezes mais trafego que hoje alem da conexao de 50 a 100 bilhoes de dispositi-
20
vos com taxas de transmissao na ordem de 10 Gbps apresentando latencia muito baixa,
confiabilidade e disponibilidade muito altas (AMGOUNE; MAZRI, 2018).
As redes veiculares, enquanto lidam apenas com a comunicacao entre veıculos,
tem seu alcance de dispositivo de comunicacao sem fio influenciado, por exemplo, pela
presenca de edifıcios, arvores e ate mesmo outros veıculos. Esta e uma das caracterısticas
que identificam as redes moveis (Mobile Ad Hoc Networks - MANETs), das quais as redes
veiculares sao uma subclasse especial. Embora seja uma subclasse das MANETs, as redes
veiculares apresentam caracterısticas que a torna unica, carente de tratamento especial
pela natureza da(s):
• Dimensao: as redes veiculares sao limitadas pelos espacos das vias, logo, seu tama-
nho em termos de espaco nao deve exceder o mapa da cidade ou extensao da rodovia,
alem disso, as conexoes tendem a ser orientadas pelas vias, onde obrigatoriamente
os nos se encontram;
• Alta mobilidade dos nos: diferente das MANETs, os nos em redes veiculares
apresentam velocidades muito altas, o que provoca sucessivas mudancas na lista de
nos vizinhos;
• Topologia dinamica: as caracterısticas de dimensao aliadas a alta mobilidade dos
nos faz com que as redes veiculares, embora permanecam com tamanho semelhante,
sofram mudancas topologicas constantemente, ou seja, os veıculos podem entrar e
sair da rede em um tempo muito curto alem de estabelecerem conexoes com outros
novos veıculos a todo instante de tempo;
• Desconexoes constantes: a alta mobilidade dos nos em ambientes onde a den-
sidade de veıculos e baixa faz com que os veıculos constantemente se desconectem
da rede, impedindo a comunicacao efetiva. Devido a alta velocidade dos veıculos e
o alcance do dispositivo de comunicacao, a duracao de uma conexao pode variar de
poucos segundos a alguns minutos; O padrao IEEE 802.11p estabelece mudancas que
agilizam de maneira significativa o processo de conexoes e desconexoes, viabilizando
as redes veiculares;
• Comunicacao por broadcast : os esforcos primarios em redes veiculares se concen-
tram no modo de comunicacao V2V. Neste modo de comunicacao as mensagens sao
transmitidas via broadcast, ou seja, um veıculo ao emitir uma mensagem alcanca
todos os veıculos que estejam dentro do alcance de seu dispositivo de comunicacao.
A forma de reduzir o numero de veıculos alcancados encontra-se na diminuicao do
raio do dispositivo de comunicacao, o que limita a comunicacao aos veıculos mais
proximos;
21
• Escalabilidade: as redes veiculares apresentam um potencial de crescimento muito
grande, proporcional a populacao de veıculos nas vias, ou seja, cidades com vias
extensas e muitas faixas tendem a apresentar um numero de veıculos muito grande.
Conforme aumenta a densidade de veıculos, aumenta-se o numero de conexoes e a
necessidade de gestao otimizada dos recursos de rede;
• Nao-restricao de energia: em contraste com as MANETs tradicionais, as redes
veiculares nao apresentam a limitacao energetica pois a queima de combustıvel nos
veıculos sao a propria fonte de energia. Esta e uma diferenca significativa das VA-
NETs para com as MANETs, uma vez que trata-se de uma das maiores limitacoes
das redes moveis.
• Capacidade de processamento e sensoriamento: alem da capacidade de co-
municacao, os veıculos apresentam capacidade de processamento e sensoriamento.
As redes veiculares podem processar informacoes fornecidas pelos proprios sensores,
contribuindo para aplicacoes que dao seguranca e informacao aos condutores;
• Interacao com a Internet: apesar dos esforcos primarios serem na comunicacao
V2V, os veıculos podem interagir com a Internet atraves da comunicacao via rede
celular e da comunicacao com a infraestrutura das cidades;
Figura 3 – Exemplo de ambiente de redes veiculares
Fonte: (GONCALVES, 2017)
22
A Figura 3 exemplifica um ambiente de redes veiculares. Neste ambiente, os veıcu-
los podem se comunicar atraves da comunicacao V2V alem da possibilidade de comunicar-
se com a infraestrutura existente na cidade, que por sua vez conecta-se a Internet. A exis-
tencia de edifıcios e arvores podem ser obstaculos que limitam o alcance do dispositivo de
comunicacao.
Em ambientes como o exemplificado na Figura 3 pode-se apresentar dois cenarios
distintos em redes veiculares. Num primeiro cenario, de baixas densidades de veıculos,
os nos apresentam-se provavelmente mais distantes. Alem dos veıculos se encontrarem
menos, o que proporciona um numero menor de conexoes, eles tem liberdade para alcan-
carem velocidades mais altas, o que provoca conexoes por tempos mais curtos que a media
(desconexoes mais constantes).
Num segundo cenario, de altas densidades de veıculos, os nos aglomeram-se mais
facilmente devido as restricoes espaciais. Alem disso, movem-se mais lentamente, permi-
tindo conexoes mais longas entre si, apesar de serem naturalmente curtas. Este cenario e
facilmente percebido em horarios de pico, durante o inıcio da manha e o fim da tarde de
dias uteis, caracterizado pelos constantes congestionamentos.
Os cenarios e os ambientes de redes veiculares podem apresentar aos condutores
a necessidade de aplicacoes que contribuem para a seguranca, desempenho do transito e
entretenimento. No aspecto da seguranca, um dos principais em que as redes veiculares
pode beneficiar, sao esperadas aplicacoes como as seguintes:
• Prevencao de acidentes: a comunicacao previa entre os veıculos na via pode permitir
que os veıculos, de forma automatica ou nao, recebam comandos de parada, reducao
de velocidade, desvio, e etc.
• Gestao de acidentes e resgates: enquanto um acidente normalmente exige uma liga-
cao para acionamento de servicos de urgencia, com as redes veiculares essa comuni-
cacao pode acontecer de maneira automatica, por meio da identificacao do sinistro
atraves dos sensores e da comunicacao direta com os canais de emergencia;
• Alertas diversos: talvez uma das aplicacoes mais simples em redes veiculares, ca-
paz de informar os condutores sobre as condicoes da pista, mudancas climaticas e
quaisquer situacoes de risco;
Alem das aplicacoes voltadas para a seguranca no transito, tambem fala-se bastante
em melhoria no desempenho do transito. Talvez esteja nesta lista as aplicacoes que mais
apresentam melhoria na vida das pessoas, promovendo o conforto em tarefas diarias que
envolvem deslocamentos:
23
• Controle de congestionamento: os congestionamentos ocorrem devido as restricoes
espaciais da via e o aumento da densidade de veıculos. Diariamente muitos cida-
daos passam por rotinas de longas esperas em congestionamentos que, atraves da
comunicacao, poderiam ser evitados. Enquanto as aplicacoes de auxılio a bordo
contribuem para encontrarmos o caminho mais curto e nos mostram com precisao o
mapa da cidade, a mesma informacao alcanca a todos seus usuarios. Este modo de
ser auxiliado a bordo faz com que os usuarios utilizem as mesmas vias com o ledo
engano de estar chegando mais rapido, afinal, trata-se do caminho mais curto. A
comunicacao pode permitir uma melhor distribuicao dos veıculos nas vias, de forma
que congestionamentos sejam evitados.
• Adaptacao de semaforos: o conhecimento das densidades de veıculos obtido atraves
da comunicacao em redes veiculares permite uma melhor gestao semaforica. Vias
onde nao existem veıculos parados nao precisam sequer que o semaforo abra para
veıculos. No caso de existirem poucos veıculos, um minuto pode ser tempo demais,
provocando ocio numa pista extremamente movimentada.
• Reducao de consumo e controle de emissao de CO2: a presenca de sensores nos
veıculos aliada a comunicacao entre os veıculos permite aos condutores uma melhor
gestao dos recursos. Alem do proprio veıculo ser uma fonte de informacoes, na qual
o condutor apoia suas decisoes sobre como dirigir, a escolha das vias em funcao de
inclinacoes e congestionamentos permite uma reducao no consumo de combustıvel
(custo financeiro) e consequentemente na diminuicao de emissao de CO2.
Aplicacoes voltadas para entretenimento e consumo tambem se aproveitam da co-
municacao em redes veiculares. As propagandas de produtos e servicos ao longo dos
deslocamentos alem de servicos de streaming de audio e vıdeo permitem aos condutores e
passageiros usufruırem dos recursos que a cidade/rodovia oferecem.
2.2 Disseminacao de Dados
2.2.1 Introducao
As aplicacoes em redes veiculares apresentam alguns requisitos para sua implemen-
tacao. Dentre as atividades requisitadas esta a atividade de disseminacao de dados. A
disseminacao de dados consiste no envio de mensagens a partir de uma fonte para todos
os veıculos localizados dentro de uma regiao geografica (CUNHA et al., 2014). A dissemi-
nacao de dados tem como objetivo alcancar muitos nos da rede numa regiao de interesse
(Region of Interest - ROI), com uma baixa latencia na transmissao.
24
A forma mais simples conhecida para disseminacao de dados em redes veiculares
e atraves do algoritmo de flooding, como mostrado por (TSENG et al., 2002). Neste
algoritmo, um veıculo fonte S inicia a transmissao de uma mensagem m a todos os veıculos
no raio de alcance do seu dispositivo de comunicacao. Cada veıculo alcancado por S efetua
a retransmissao de m tambem a todos que estao em seu alcance. Estas retransmissoes
ocorrem sucessivamente ate que a rede seja inundada com os pacotes.
A abordagem de flooding e muito simples diante desta importante atividade no
contexto das redes veiculares, tanto para o entendimento quanto para a implementacao.
Entretanto, esta abordagem tambem e bastante didatica no que tange aos problemas
classicos da disseminacao de dados.
2.2.2 Problemas em Disseminacao de Dados
A utilizacao do algoritmo de flooding para a disseminacao de dados apresenta pro-
blemas nos dois cenarios apresentados na Secao 2.1. No primeiro deles, o cenario de baixas
densidades de veıculos, a rede apresenta caracterısticas como alta mobilidade dos veıcu-
los, menor numero de conexoes devido ao numero reduzido de veıculos, desconexoes mais
constantes e consequentemente um particionamento da rede. Este problema e denominado
na literatura como problema de conexoes intermitentes (intermittently connected network
problem) (SPYROPOULOS; PSOUNIS; RAGHAVENDRA, 2008), ou apenas problema
de particoes na rede.
Em cenarios de baixas densidades de veıculos, o comportamento do algoritmo de
flooding nao ocorre em sua totalidade devido as premissas assumidas pelo mecanismo.
Para que ocorra a inundacao da rede com a mensagem, faz-se necessario que a rede esteja
completamente conectada, assim, cada no executara de maneira satisfatoria o papel de
encaminhar a mensagem. As particoes existentes na rede fazem com que a mensagem se
perca e veıculos em particoes diferentes da rede nao tomem conhecimento.
Por outro lado, em cenarios de alta densidades de veıculos a rede apresenta outras
caracterısticas. Por exemplo, os veıculos nao tem a liberdade de moverem-se tao rapida-
mente quanto em cenarios de baixa densidade pois a via permanece com suas restricoes
espaciais encontra-se mais ocupada (existem mais veıculos na via). Estes deslocamentos
nao tao rapidos aliados a um numero maior de veıculos faz com que se aglomerem mais fa-
cilmente, permitindo um numero maior de conexoes. Devido a forma de comunicacao em
redes veiculares ser primariamente via broadcast, uma emissao de mensagens num cenario
denso como o descrito anteriormente faz com que muitos nos recebam a mensagem.
Quando em redes veiculares tem-se um cenario denso de veıculos, ocorre a formacao
de diversos subgrafos completos. Grafos (ou subgrafos) completos sao aqueles em que
25
todos os nos se conectam com todos. O problema da forma de disseminar mensagens
em redes veiculares pela abordagem do algoritmo de flooding numa rede que represente
um grafo completo esta no numero de mensagens transmitidas e na ocupacao do meio de
comunicacao.
A Figura 4 nao parece apresentar nenhum problema. Enquanto o numero de nos
na rede permanecer pequeno, como ocorre em cenarios de baixas densidades de veıculos,
realmente o problema e minimizado. No entanto, o que acontece com a abordagem do
algoritmo de flooding para o cenario da Figura 5?
Figura 4 – Exemplo de cenario com baixa densidade de veıculos
Fonte: Simulador de redes OMNET++
Assim que o primeiro veıculo receber a mensagem a ser disseminada, fara o enca-
minhamento a todos os veıculos que estejam em seu alcance (um numero relativamente
grande), estes veıculos por sua vez farao o mesmo, retransmitindo a mensagem sucessiva-
mente ate que todos a encaminhem. Estudos iniciais em redes sem fio mostraram que uma
retransmissao alcanca menos de 45% de nova area em relacao a transmissao anterior con-
siderando o alcance dos dispositivos de comunicacao como cırculos perfeitos (TSENG et
al., 2002). Este numero sugere que mais de 55% da area alcancada por uma retransmissao
ja havia recebido a mensagem. Em um grafo completo, o numero de retransmissoes feitas
e equivalente ao numero de vertices, ou seja, o numero de mensagens que cada um dos nos
recebe e equivalente ao numero de vizinhos. Como estamos lidando com a transmissao de
uma mensagem que ao ser recebida vai ser processada por uma aplicacao de rede veicular,
faz-se necessario recebe-la apenas uma vez.
A quantidade de mensagens transmitidas pela abordagem de flooding e muito
grande, muitas delas desnecessarias pois alcancam veıculos que ja conhecem a mensagem,
26
provoca um numero elevado de colisoes de pacotes em razao dos muitos veıculos proximos
se comunicando simultaneamente, congestiona o meio de comunicacao e eventualmente
provoca interrupcao de servico na camada de controle de acesso ao meio (WILLIAMS;
CAMP, 2002). Este problema e conhecido na literatura como tempestade de broadcast ou
broadcast storm problem. Apesar de apresentar estas dificuldades, o algoritmo de flooding
possui diversas estrategias de tratamento que corrigem falhas.
Figura 5 – Exemplo de cenario com alta densidade de veıculos
Fonte: Simulador de redes OMNET++
Em resumo, entende-se que em cenarios densos de veıculos existe a necessidade de
tratamento do problema de broadcast storm, por outro lado, em cenarios esparsos, com
baixa densidade de veıculos, existe a necessidade de tratamento do problema de particoes
na rede. Muitas solucoes para disseminacao de dados em redes veiculares apresentam
propostas para os dois cenarios de forma adaptativa, de forma que em baixas densidades
de veıculos opera-se num modo A e para altas densidades de veıculos num modo B.
2.2.3 Estrategias para Tratamento dos Problemas em Disseminacao deDados
Em (TSENG et al., 2002) foram apresentadas varias estrategias para tratamento
do problema de broadcast storm. Algumas delas bastante encontradas em outras propostas
mais elaboradas, de forma hıbrida, sao apresentadas a seguir:
• Probabilistic Scheme: esta classe de solucoes explora a probabilidade como uma
forma intuitiva de reduzir o numero de retransmissoes. Define-se que os veıculos
tenham uma probabilidade P de efetuarem retransmissoes, dessa forma veıculos
27
mais interessantes para retransmissoes recebem P mais proximo de 1. Nota-se que
quando P = 1 para todos os veıculos, o mecanismo se comporta como o algoritmo
de flooding.
• Counter-Based Scheme: este mecanismo de transmissao explora o conhecimento que
os veıculos tem das retransmissoes feitas por seus vizinhos. Enquanto um veıculo
aguarda para retransmitir uma mensagem, ele pode receber a mesma mensagem
repetidas vezes de seus vizinhos. Atraves da definicao de um limiar k ideal, se
o veıculo recebe a mensagem que quer retransmitir k vezes antes de retransmitir,
cancela sua retransmissao. Isso ocorre devido a percepcao de que sua retransmissao
nao trara benefıcio algum para a rede. Estudos recentes mostraram que nao ha
benefıcio em definir valores de k superiores a 4.
• Distance-Based Scheme: neste esquema, os veıculos utilizam a distancia relativa
entre eles para a tomada de decisao sobre a retransmissao. Dado que uma fonte S
efetua a transmissao de uma mensagem e um veıculo V recebe esta mensagem, V
verifica sua distancia de S. Enquanto mais proximo de S, menor a cobertura adicional
de V, o que leva a crer que uma retransmissao nao alcancara muitos novos veıculos.
Em contrapartida, veıculos distantes terao uma cobertura adicional superior, o que
e uma caracterıstica interessante para um bom retransmissor.
• Location-Based Scheme: o conhecimento preciso da localizacao dos veıculos pode
garantir melhor conhecimento a respeito de suas coberturas adicionais, informacao
fundamental para a tomada de decisao acerca de qual melhor retransmissor de uma
mensagem. A localizacao pode ser obtida pela utilizacao de dispositivos GPS (Global
Positioning System).
• Cluster-Based Scheme: esta abordagem aproveita-se do agrupamento de veıculos
para a escolha de melhores retransmissores e parte do pressuposto que os veıculos
conhecem seus vizinhos mais proximos. Define-se que atraves das conexoes exis-
tentes entre os vizinhos, o de maior grau e o cluster-head. Alem disso, os veıculos
que conectam clusters distintos sao chamados gateways e por fim, os veıculos nao
cluster-heads ou gateways sao cluster-members. Nesta estrategia os cluster-heads
sao naturalmente melhores retransmissores de mensagens em virtude de apresenta-
rem uma conectividade maior no interior de um cluster. A tarefa de disseminar e
tambem entregue aos gateways que carrega a mensagem para os clusters vizinhos.
• Delay-Based Scheme: no problema de broadcast storm o excesso de retransmissoes ao
mesmo tempo e o nucleo dos efeitos negativos. Uma possibilidade para tratamento
deste problema e a definicao de tempos de espera aleatorios para as retransmissoes.
Desta forma, ao receber uma mensagem o veıculo devera aguardar um tempo alea-
28
torio antes de retransmiti-la. Esta e uma possıvel variacao do mecanismo de flooding
que consegue reduzir a dimensao do problema, mas nao o resolve por completo.
2.2.4 Estrategia para Solucao do Problema de Particoes na Rede
Embora haja um grande numero de estrategias para mitigar os problemas de broad-
cast storm, apenas uma solucao tem sido praticada na literatura para solucao do problema
de particoes na rede.
Os trabalhos encontrados na literatura que apresentam solucao para o problema de
particoes na rede utilizam de um recurso de redes veiculares nao disponıvel na implemen-
tacao do algoritmo de flooding. O recurso utilizado e denominado beacon e consiste em
pacotes menores, transferidos periodicamente para os nos vizinhos, carregando informa-
coes de contexto. A solucao encontrada na literatura utiliza beacons para conhecimento
da vizinhanca proxima bem como para ter conhecimento das mensagens que os vizinhos
dispoe em sua memoria. Dessa forma, em cenarios de baixas densidades de veıculos, os
vizinhos podem obter uns dos outros as informacoes de mensagens com tempo de vida
que sao do interesse e que ainda nao tiveram acesso. Os veıculos que possuem a mensa-
gem carregam-na enquanto houver tempo de vida, dessa forma, uma vez que a mensagem
e perdida pelo mecanismo de disseminacao padrao, nao e impossibilitada de alcancar
os veıculos em componentes isolados. Este mecanismo e conhecido na literatura como
store-carry-forward.
2.3 Consideracoes
Neste capıtulo as redes veıculares foram introduzidas com maior nıvel de detalhes
e apresentadas caracterısticas que as diferenciam das redes moveis tradicionais, das quais
as redes veiculares sao uma subclasse especial. Em virtude. Tambem foi detalhada a
atividade de disseminacao de dados, servico necessario para os diversos tipos de aplicacoes
em redes veiculares.
No que tange a disseminacao de dados, dois problemas principais afetam o desem-
penho de protocolos de disseminacao de dados, sendo eles conhecidos pela densidade de
veıculos. Em cenarios com baixas densidades de veıculos, o problema de particoes na rede
fica evidente, por outro lado, em cenarios com altas densidades de veıculos, evidencia-se
o problema de broadcast storm. Diferente do problema de particoes na rede que apre-
senta escasses de solucoes na literatura, o problema de broadcast storm pode ser mitigado
implementando-se diversas estrategias basicas, sozinhas ou em formas combinadas.
Na solucao proposta neste trabalho, foram utilizadas as estrategias basicas para
tratamento do problema de broadcast storm denominadas counter-based scheme, distance-
29
based scheme e delay-based scheme, e por se tratar de uma solucao para altas densidades
de veıculos, nao apresenta solucao para o problema de particoes na rede.
30
3 TRABALHOS RELACIONADOS
Este capıtulo apresenta os trabalhos que mais se relacionam com a proposta desta
dissertacao, partindo de trabalhos que implementam encaminhamento de pacotes por
meio de trajetorias ate os trabalhos da literatura que resolvem problemas de dissemi-
nacao de dados em redes veiculares. Sao apresentadas solucoes mais elaboradas que as
introduzidas no Capıtulo 2 que se propuseram a resolver os problemas classicos da dissemi-
nacao. Ao final deste capıtulo serao feitas consideracoes acerca dos trabalhos apresentados
relacionando-os ao trabalho proposto nesta dissertacao.
3.1 Disseminacao em Curva
Conforme introduzido no Capıtulo 2, as redes veiculares sao uma subclasse especial
das redes moveis, nas quais estao inseridas as redes de sensores sem fio (Wireless Sen-
sor Networks - WSNs). Conhecer formas originarias de disseminacao de dados nas redes
moveis como um todo tem o potencial de prover insights para o desenvolvimento de proto-
colos em redes veıculares, razao considerada suficiente para o presente aprofundamento. A
atividade de disseminacao de dados foi enderecada primeiramente nas WSNs, no entanto,
essas redes apresentam caracterısticas diferentes das redes veiculares, especialmente no
que se refere a disponibilidade energetica.
A topologia das redes de sensores sofre alteracoes constantes devido a nos com
pouca capacidade energetica que entram em modo de hibernacao apos coleta de informa-
coes, tecnica que extende o tempo de atividade do no. Neste cenario, os protocolos de
roteamento que se baseavam na escolha de nos para desempenhar o encaminhamento de
pacotes apresentavam dificuldades nas avaliacoes de desempenho. Eis que os autores de
(NICULESCU; NATH, 2003) propuseram o protocolo TBF (Trajectory based forwarding),
em que a atividade de encaminhar pacotes nao e mais designada a nos especıficos e sim a
regioes. O protocolo define uma trajetoria por onde o pacote deve passar e nessa trajetoria
os nos mais indicados para a tarefa de encaminhamento do pacote o fazem, de tal forma
que nos especıficos nao sejam mais responsaveis pela tarefa, cuja falha impediria que o
pacote chegasse ao destino.
Em uma abordagem que alia os princıpios explorados no TBF ao conhecimento
31
do mapa de energia, os autores de (MACHADO et al., 2005) propuseram o protocolo
TEDD (Trajectory and energy-based data dissemination). O mapa de energia consiste
nas informacoes de disponibilidade energetica de cada no que compoe a rede, permitindo
que uma visao global possa identificar as regioes mais disponıveis bem como as regioes
mais carentes de energia. Semelhantemente ao TBF, a proposta do protocolo TEDD
e determinar uma trajetoria nao vinculada a nos especıficos, que explore regioes com
nıveis de energia mais altos, ou seja, com menor chance de apresentar falhas por falta de
energia. Os autores dividem o processo em duas partes: (a) a primeira e um algoritmo
que gera trajetorias que passam por regioes com nıveis mais altos de energia e se esquiva
de regioes com baixos nıveis de energia. A ideia e selecionar conjuntos de nos que sao
mais indicados para a tarefa de disseminacao e encontrar o melhor conjunto de curvas que
passam por estes nos, (b) um novo mecanismo de encaminhamento de pacotes baseado
no receptor. Os autores destacam que o protocolo TEDD melhora o protocolo TBF em
dois pontos, eliminando a necessidade de manter uma tabela de vizinhos e apresentando
um comportamento mais robusto em cenarios com topologias dinamicas.
Tal como as redes de sensores sem fio, as redes veiculares tambem apresentam
dinamicidade na topologia, no entanto pela caracterıstica movel dos nos e nao por sua
capacidade energetica. Apesar do motivo, essa rede tambem apresenta diferentes densi-
dades em diferentes regioes, sugerindo que o mecanismo de definicao de trajetorias por
regioes densas apresenta semelhante potencial para melhoria de desempenho na tarefa de
disseminacao de dados.
3.2 Disseminacao em Redes Veiculares
A atividade de disseminacao de dados em redes veiculares pode ser confundida
na literatura com a atividade de roteamento. Em (AHMAD; SHCHERBAKOV, 2018)
os autores definiram protocolos de roteamento como sendo um conjunto de regras que
determinam o metodo de conexao entre os nos e como distribuem dados entre eles. A tarefa
basica de um protocolo de roteamento, conforme os autores, e encontrar um caminho otimo
para comunicacao entre nos. Em (SALEH; HASSON, 2019), em um extenso trabalho
acerca de protocolos de roteamento, os autores dividem os protocolos em unicast routing
e broadcast routing. Neste trabalho, broadcast routing trata-se, em resumo, da entrega de
uma mensagem a um conjunto de nos interessados na informacao, definicao equivalente a
de disseminacao de dados dada por (CUNHA et al., 2014).
A grande maioria dos trabalhos propostos para roteamento e disseminacao de da-
dos em redes veiculares encontrados na literatura exploraram o modo de comunicacao
V2V e V2I. Conforme introduzido no Capıtulo 2, dois problemas classicos para esses pro-
tocolos sao caracterizados pela quantidade de veıculos existentes nos cenarios, ou seja, sao
32
caracterizados pela densidade de veıculos. Basicamente, em cenarios de alta densidade
de veıculos, existe a necessidade de tratamento do problema de broadcast storm, e em
cenarios de baixa densidade de veıculos existe a necessidade de tratamento do problema
de particoes na rede. Alem disso, as solucoes que tratam ambos os problemas, comu-
mente implementam algum criterio para alternancia entre as densidades, estabelecendo
um limite que separa baixas densidades de altas densidades de veıculos.
Ainda no Capıtulo 2, foram introduzidas algumas abordagens estatısticas para
tratamento do problema de broadcast storm que sao melhorias no algoritmo de flooding,
sao elas: Probabilistic Scheme, Counter-Based Scheme, Distance-Based Scheme, Location-
Based Scheme, Cluster-Based Scheme e Delay-Based Scheme. Essas estrategias foram
selecionadas devido a serem implementadas em diversas solucoes da literatura. Muitos
dos trabalhos encontrados na literatura apresentam estrategias inovadoras juntamente
com estas solucoes estatısticas, de maneira hıbrida.
Conforme a Figura 6, as secoes deste capıtulo tratam de uma taxonomia que divide
as solucoes encontradas na literatura sob o aspecto das informacoes necessarias para sua
implementacao: (i) disseminacao baseada em informacoes a bordo, em que os veıculos
dispoem de toda informacao utilizada na implementacao do protocolo a bordo do veıculo;
(ii) disseminacao baseada em informacoes locais, na qual os veiculos se comunicam com
os vizinhos proximos a fim de obterem o conhecimento da vizinhanca a poucos saltos; e
(iii) disseminacao baseada em informacoes globais, onde os veıculos recebem informacoes
relacionadas a toda a rede. As solucoes elencadas envolvem protocolos identificados como
de roteamento e/ou disseminacao de dados, classificados aqui conforme a informacao
de que eles dispoe no desenvolver de suas tarefas, entretanto, este trabalho relaciona
protocolos que implementaram alem dos modos de comunicacao V2V e V2I, tambem a
comunicacao com a rede celular.
3.2.1 Disseminacao baseada em Informacoes a Bordo
Esta secao apresenta trabalhos que abordaram os problemas classicos da disse-
minacao de dados a partir de uma visao local, na qual os veıculos sao dotados de toda
informacao necessaria para a execucao do algoritmo que o protocolo implementa, sem
necessidade de qualquer comunicacao externa durante a execucao. Importa destacar as
limitacoes dessas solucoes: (i) sao abordagens baseadas em estatıstica, que nao consi-
deram o contexto bem como a vizinhanca de cada veıculo, (ii) nao apresentam solucoes
satisfatorias para o problema de particoes na rede devido a dificuldade em reconhecer que
existem particoes na rede, problema comum em cenarios de baixas densidades de veıculos.
O primeiro trabalho considerado neste contexto e o apresentado em (BAKHOUYA;
GABER; LORENZ, 2011). Neste trabalho, os autores propuseram o protocolo AID (Adap-
33
Figura 6 – Taxonomia para classificacao dos protocolos da literatura
Fonte: Proprio Autor
tive approach for Information Dissemination) que utiliza uma abordagem estatıstica para
dar continuidade ao processo de disseminacao em cenarios urbanos. Neste protocolo, a
decisao de efetuar a retransmissao da mensagem e baseada no tempo entre recepcao das
mensagens. Basicamente, se durante o tempo de recepcao de uma mensagem ocorrer
a recepcao de mensagens redundantes, a retransmissao nao deve ser feita. Trata-se de
um protocolo adaptativo que implementa uma das propostas estatısticas apresentadas
anteriormente, a Distance-Based Scheme. Uma vez que uma mensagem nova chega ao
veıculo, estabelece-se imediatamente um tempo de espera aleatorio baseado na distan-
cia estimada a partir do veıculo transmissor. Em seguida, escalona-se uma retransmissao
para o tempo atual adicionado a um tempo aleatorio estabelecido. Se nenhuma mensagem
repetida for recebida durante o tempo aleatorio estabelecido, a retransmissao escalonada
vai ocorrer. Entretanto, uma vez que esta mesma mensagem torne a chegar, o tempo
aleatorio e reiniciado e uma nova espera se inicia. Este trabalho implementa tambem
o esquema Delay-Based Scheme apresentado no Capıtulo 2, em que veıculos aguardam
para retransmitir, esta iniciativa impede as transmissoes simultaneas, promovendo uma
melhora consideravel em evitar colisoes.
No entanto, essa proposta nao lida com o problema de particoes na rede. E im-
portante observar que ainda que haja um controle consideravel do numero de mensagens
transmitidas, nada se faz em relacao a redes particionadas. Alem disso, a estrategia apre-
34
sentada nao e aplicavel a qualquer contexto. por exemplo, aplicacoes de seguranca como
notificacoes de emergencia sao muito sensıveis ao tempo, logo, propostas que implementam
delays sao pouco efetivas.
Ainda no contexto de protocolos que utilizam informacoes a bordo, em (VILLAS et
al., 2012) os autores propuseram GEDDAI (GEographical Data Dissemination for Alert
Information). GEDDAI e uma solucao que lida com o problema de broadcast storm
introduzindo o conceito de zona de preferencia. Em GEDDAI, o veıculo que depara-se com
um evento inicia a disseminacao da mensagem, que deve ser propagada por toda a regiao
de interesse. Nesse processo reativo, zonas de preferencias, que sao definidas conforme o
raio do dispositivo de comunicacao dos veıculos, recebem atencao especial. Os veıculos
nessas regioes precedem os demais nas sucessivas retransmissoes pois apresentam menor
sobreposicao de areas em relacao aos demais. A Figura 7 destaca em verde os veıculos em
zonas de preferencia que forcam o cancelamento das retransmissoes dos veıculos que nao
estao em zonas de preferencia, reduzindo assim a quantidade de mensagens transmitidas.
Embora funcione em qualquer densidade, o protocolo apresenta cobertura insuficiente em
cenarios de baixas densidades.
Figura 7 – Zona de Preferencia do protocolo GEDDAI
Fonte: Adaptada pelo Autor de (VILLAS et al., 2012)
Uma estrategia diferente para controle do problema de broadcast storm foi proposta
em (SILVA et al., 2017). Neste trabalho e apresentado um protocolo hıbrido, de nome
Geo-Oriented, que utiliza o conhecimento do mapa e a abordagem estatıstica Probabilistic-
Scheme introduzida no Capıtulo 2. A solucao para a disseminacao de dados considera,
como inspiracao para a proposta do protocolo, uma abordagem para disposicao de antenas
telefonicas. A extensao da area de cobertura de uma Estacao Radio Base (ERB) pode ser
35
estimada a partir de alguns atributos como, por exemplo, a localizacao da antena. Dado
um mapa e uma antena com raio de alcance maximo r, qual o maior numero de antenas
possıvel a serem dispostas no mapa sem que haja intersecao na cobertura das antenas?
A Figura 8 apresenta um cenario em que o maior numero e 4. Perceba que existem
3 regioes distintas neste cenario. Primeiro, a menor regiao, em vermelho, representa
a localizacao dos veıculos centrais, mais indicados para efetuarem retransmissoes, com
posicao semelhante a de uma ERB. Segundo, em azul, a regiao de veıculos relevantes
para retransmissoes, mas nao tao indicados. A borda externa do cırculo azul representa
o limite da comunicacao do veıculo no centro do cırculo vermelho. Por ultimo, em cinza,
os veıculos nao considerados interessantes para retransmissoes.
Figura 8 – Zonas do Protocolo Geo-Orientado
Fonte: (SILVA et al., 2017)
O centro do cırculo vermelho e chamado de HotPoint. Os HotPoints sao pontos
definidos arbitrariamente e sao considerados os locais ideais para veıculos efetuarem re-
transmissoes. Por exemplo, dada a forma como os HotPoints estao distribuıdos no mapa
da Figura 8, bastam 4 retransmissoes para que pouco mais de 78% da area deste mapa
sejam cobertos pela mensagem. A partir destes HotPoints definiu-se que os veıculos no
interior do cırculo vermelho sao altamente indicados a retransmissores da mensagem no
processo de disseminacao. Os veıculos na regiao em azul, por sua vez, sao veıculos com
capacidade para retransmitir, mas menos indicados. E por fim, os veıculos nas regioes em
cinza sao considerados nao-indicados a atividade de retransmissao. A localizacao do veı-
culo no mapa e o principal aspecto observado para a atribuicao da probabilidade do veıculo
efetuar a retransmissao das mensagens recebidas, mas tambem sao considerados posicao,
velocidade e localizacao de origem. Resultados iniciais mostraram que esta abordagem
voltada para o mapa desempenha bem em relacao as demais abordagens estatısticas.
36
3.2.2 Disseminacao baseada em Informacoes Locais
Nesta secao, os trabalhos apresentados apresentam conhecimento adicional em re-
lacao as informacoes a bordo dos veıculos. O conhecimento adicional refere-se a topologia
local, conexoes que os veıculos apresentam com sua vizinhanca a poucos saltos. Estas so-
lucoes se destacam pela comunicacao previa exigida para sua execucao. Com o surgimento
deste conhecimento da vizinhanca, grande parte dos protocolos apresentam solucoes para
ambos os problemas classicos da disseminacao de dados, particoes na rede e broadcast
storm.
3.2.2.1 Solucao para problema de particoes na rede
Os primeiros protocolos desta secao sao o DV-CAST (Distributed Vehicular Bro-
adCAST) (TONGUZ; WISITPONGPHAN; BAI, 2010) e o UV-CAST (Urban Vehicular
BroadCAST) (VIRIYASITAVAT; BAI; TONGUZ, 2010). Nestes protocolos os autores
empenharam-se em tratar tanto o problema de particoes na rede quanto o problema de bro-
adcast storm para cenarios de rodovias (DV-CAST) e para cenarios urbanos (UV-CAST).
A forma como abordaram o problema envolve um mecanismo de difusao de beacons. Bea-
cons sao pacotes de dados de tamanho reduzidos que armazenam informacoes de contexto
e sao transmitidos com um intervalo constante entre eles. As informacoes de contexto
podem ser, por exemplo, a localizacao estimada por meio de sistemas de posicionamento
global (Global Positioning System - GPS), numero de vizinhos, velocidade do veıculo, etc.
Estas informacoes permitem que os veıculos facam estimativas acerca da topologia da
rede. Apesar de extremamente dinamica, a topologia da rede pode fornecer algumas ca-
racterısticas extremamente interessantes durante a disseminacao de dados, por exemplo,
conhecer a densidade de veıculos no local. Com base nestas informacoes, a disseminacao
de dados nao e mais feita as cegas, como acontece no algoritmo de flooding. O mecanismo
de transmissao de beacons adotado pelos autores permite aos veıculos o conhecimento de
seus vizinhos a um salto e tambem das mensagens que eles possuem. Dessa forma, quando
identifica um cenario denso de veıculos, opera no modo de supressao de broadcast, quando
o cenario apresenta poucos veıculos, opera no modo store-carry-forward como forma de
tratamento para o problema de particoes na rede.
No modo de supressao de broadcast, o protocolo UV-CAST considera veıculos em
cruzamentos para o calculo de um tempo de espera. E implementado o esquema estatıstico
Delay-Based Scheme apresentado no Capıtulo 2. A supressao e feita da seguinte forma:
uma vez que o tempo de espera de um veıculo expira sem que este tenha recebido uma
nova mensagem redundante, efetua a retransmissao da mensagem. Caso tenha recebido a
mesma mensagem durante o tempo de espera, reinicia o tempo de espera. O protocolo DV-
CAST por sua vez, implementa o esquema estatıstico Distance-Based Scheme, tambem
37
introduzido no Capıtulo 2. Nesta implementacao os veıculos recebem uma probabilidade
maior de efetuarem a retransmissao da mensagem caso apresentem uma maior distancia
em relacao ao veıculo origem da mensagem.
Em outro modo de operacao, quando em densidades de veıculos menores, o proto-
colo UV-CAST considera os veıculos mais proximos das bordas do componente da rede
como carregadores da mensagem. Por meio da troca de beacons, ao encontrar um veıculo
interessado na mensagem que nao a possui, verifica a validade da mensagem e efetua a
retransmissao se ainda for valida. O protocolo DV-CAST por sua vez entrega a tarefa
de carregar a mensagem aos veıculos no sentido oposto, que encontrarao antes os veıculos
interessados na mensagem (veıculos no mesmo sentido que o evento).
Apesar do ganho apresentado pela abordagem proposta nesses dois protocolos e
do potencial para apresentar melhorias nos resultados da disseminacao, ela apresenta um
custo adicional. O acrescimo do numero de mensagens transmitidas periodicamente, como
acontece com a utilizacao dos beacons, aumenta o consumo do recurso rede, o que por si
so aumenta os efeitos do problema de broadcast storm. Embora tenha este custo adicio-
nal, a estrategia apresenta resultados satisfatorios do ponto de vista global, provocando
menos transmissoes de mensagens desnecessarias e aumentando a cobertura da rede. Os
resultados apresentados pelos autores mostram que existe uma melhoria na cobertura em
cenarios com baixa densidade de veıculos, sugerindo que o custo adicional associado a
transmissao de beacons pode ser pago.
Em (AKABANE et al., 2016), os autores propuseram um protocolo que atua tanto
em cenarios urbanos como em rodovias. Alem disso, o protocolo proposto CARRO
(Context-Aware Routing pROtocol) lida com os dois problemas classicos de dissemina-
cao de dados, broadcast storm e particoes na rede. O processo de disseminacao de dados
tambem ocorre a partir da observacao da densidade de veıculos no cenario. Em cenarios
densos de veıculos o protocolo CARRO trata o problema de broadcast storm utilizando
um mecanismo de supressao de broadcast chamado Zona de Preferencia introduzido em
(VILLAS et al., 2012). Conforme mostra a Figura 9, Zonas de Preferencia sao setores
na borda do raio de comunicacao em que veıculos localizados em seu interior sao consi-
derados melhores potenciais retransmissores de tal forma que bastando a retransmissao
desses veıculos a disseminacao sera eficiente. Por outro lado, em cenarios pouco densos de
veıculos, o protocolo proposto pelos autores utiliza o mecanismo de store-carry-forward
utilizado no protocolo UV-CAST para dar continuidade ao processo de disseminacao.
De semelhante modo, os protocolos CC-DEGREE (CUNHA et al., 2014), VOV
(MAIA et al., 2015) e HyDiAck(MAIA et al., 2013) operam nos modos de suppressao
de broadcast e store-carry-forward, mas apresentando diferentes abordagens para os al-
goritmos de supressao. CC-DEGREE utiliza metricas sociais para selecao de veıculos
38
Figura 9 – Zona de Preferencia em cenarios urbanos e rodovias
Fonte: (AKABANE et al., 2016)
potenciais melhores retransmissores. As metricas sao o coeficiente de clusterizacao e o
grau dos nos de forma que os veıculos que apresentem alto grau e no entanto nao se
enxergam (devido a possuirem baixo coeficiente clusterizacao) sao os mais indicados. O
protocolo VOV se propoe a controlar a comunicacao via broadcast implementando de
maneira hıbrida duas estrategias estatısticas apresentadas no Capıtulo 2, Location-Based
Scheme e Distance-Based Scheme. O protocolo HyDiAck procura determinar qual deve
ser o subgrupo de veıculos responsavel pela retransmissao da mensagem, considerando
veıculos no interior de uma zona de retransmissao (Forwarding Zone) os mais indicados.
A Figura 10 ilustra a zona de retransmissao implementada pelo protocolo HyDiAck.
Para o modo de operacao de baixas densidades, os protocolos CC-DEGREE, VOV
e HyDiAck implementam store-carry-forward como solucao.
3.2.2.2 Nao solucao para problema de particoes na rede
Os protocolos a seguir embora utilizem do conhecimento da vizinhanca, o que
permite estimar a topologia local, nao apresentam solucoes para o problema de particoes
na rede. As propostas que utilizam o recurso beacons apresentadas ate aqui procuravam o
conhecimento dos vizinhos a 1-salto e utilizavam de informacoes topologicas para estimar
a densidade de veıculos, alem de tomar decisoes considerando as localizacoes aproximadas
dos veıculos.
Em (COSTA et al., 2017) foi proposto um protocolo que tambem utiliza do recurso
beacon mas que busca o conhecimento de vizinhos ate 2-saltos. A estrategia dos autores
para o protocolo de nome DDBC (Data Dissemination protocol Based on Centrality) e
39
construir um grafo local e atribuir a tarefa de retransmissao das mensagens aos pontos de
articulacao deste grafo. A Teoria dos Grafos diz que um ponto de articulacao (ou vertice
de corte) e um vertice de um grafo tal que a remocao deste vertice provoca a desconexao
do grafo. A partir do conhecimento dos pontos de articulacao existentes entre os vizinhos,
a decisao acerca do retransmissor da mensagem e centralizada ao veıculo origem. Definiu-
se que os veıculos que sao pontos de articulacao no grafo construıdo localmente serao
os responsaveis pelas retransmissoes. Havendo mais de um ponto de articulacao, o que
tiver maior numero de vizinhos e maior distancia do veıculo de origem e selecionado. Nao
havendo pontos de articulacao no grafo construıdo, o que tiver maior numero de vizinhos
e selecionado.
O protocolo CPB (LIU et al., 2018) utiliza beacons para estimar a topologia local
num contexto diferente. Ocorre que este protocolo e proposto para disseminar dados em
rodovias e a forma como a disseminacao e feita envolve, de maneira hıbrida, duas solu-
coes basicas apresentadas no Capıtulo 2, Probabilistic Scheme e Cluster-Based Scheme.
O diferencial, como destacam os autores, acerca da abordagem probabilıstica esta no fato
de as propostas da literatura implementarem probabilidades estaticas, nao impedindo um
grande numero de mensagens redundantes sendo transmitidas. Os autores implementaram
uma probabilidade dinamica, em funcao da densidade de veıculos no cenario de rodovia
implementado. Alem disso, operam conforme os estados dos veıculos no cluster. Um
veıculo nao cluster-head recebendo uma mensagem verifica se o cluster-head recebeu, caso
nao o tenha, encaminha a mensagem ao cluster-head. Caso tenha recebido, descarta a
mensagem. Por outro lado, se o veıculo for um cluster-head e estiver na direcao da mensa-
gem (estimada facilmente devido a rodovia apresentar apenas dois sentidos), retransmite
a mensagem, caso contrario a descarta.
3.2.3 Disseminacao baseada em Informacoes Globais
Nesta secao, os protocolos consideram que os veıculos sao dotados com informacoes
a bordo do veıculo bem como informacos globais, nao restritas a topologia local. Esta
nao limitacao permite que o problema de particoes na rede tenha efeitos bem menos
significantes, uma vez que sao bem mais facilmente detectados. Os protocolos classificados
como dotados de informacoes globais utilizam da rede celular no mınimo como fonte de
informacao precisa e global.
Em (LEQUERICA; RUIZ; CABRERA, 2010), os autores implementaram uma
solucao util como backup para comunicacao entre veıculos mas tambem um mecanismo
para disseminacao de informacoes de controle para aplicacoes e protocolos. Neste trabalho,
denominado VISIONS (Vehicular communication Improvement: Solution based on IMS
Operational Nodes and Services), a ideia geral e apresentar uma solucao para protocolos
40
Figura 10 – Zona de retransmissao do protocolo HyDiAck
Fonte: (MAIA et al., 2013)
de roteamento em redes veiculares cujo problema e encontrar a lista apropriada de ruas e
intersecoes conectando a origem da mensagem e o destino.
Para alcancar este objetivo, os autores utilizaram a rede 3G como meio de comuni-
cacao entre os veıculos e um servidor onde a informacao e processada e disponibilizada a
toda a rede. O foco dos autores esta na disponibilizacao de toda informacao relevante para
aplicacoes, servicos e protocolos a fim de que apresentem uma melhoria de desempenho e
alcancem uma mudanca positiva em suas propostas.
VMaSC foi o nome dado ao protocolo proposto por (UCAR; ERGEN; OZKASAP,
2016). Este protocolo emprega o modo de comunicacao V2V por meio do protocolo IEEE
802.11p bem como a comunicacao V2V por meio da rede celular LTE. Neste trabalho que
tambem emprega o esquema Cluster-Based, os veıculos eleitos cluster-heads podem emitir
e retransmitir mensagens tambem por meio da rede celular LTE, via multicast, no entanto
os veıculos cluster-members estao limitados a comunicacao via protocolo IEEE 802.11p,
o que pode mudar caso sejam eleitos cluster-heads em algum momento. O emprego da
comunicacao global na comunicacao entre os veıculos e um passo para o futuro das redes
de 5a geracao.
Como um grande avanco nas tecnologias de comunicacao, as redes de 5a Geracao
(5G) apresentam um cenario completamente diferente tambem para as redes veiculares.
Em (KHAN et al., 2019), os autores propuseram um algoritmo de roteamento para co-
municacao 5G V2X (Vehicle-to-Everything) que implementa um esquema Cluster-Based
41
(Capıtulo 2) em dois nıveis. As novidades nesta proposta comecam com os problemas
classicos em disseminacao de dados, broadcast storm e particoes na rede, que sequer sao
mencionados. Isso se deve ao fato da comunicacao via rede 5G oferecer suporte a comu-
nicacao nao exclusiva por meio de broadcast.
3.3 Consideracoes
A disseminacao em curva foi inicialmente abordada em redes de sensores sem fio,
nas quais as curvas eram baseadas na disponibilidade energetica dos nos que compunham
a rede. Os autores do protocolo TEDD acrescentaram ao protocolo TBF o conhecimento
de um mapa de energias, que permite uma visao global do mapa para a definicao de
curvas melhores por onde os pacotes deveriam passar. Este conhecimento global que
proporcionou uma melhoria significativa para o problema de disseminacao em redes de
sensores tambem e explorado no presente trabalho, em que busca-se conhecer a densidade
de veıculos em todo mapa atraves da comunicacao via rede celular.
Os diversos trabalhos apresentados neste capıtulo abordaram o problema de bro-
adcast storm de pontos de vista diferentes. Dentre os protocolos que implementaram
solucoes que tratam o problema de particoes na rede, todos o fizeram por meio da conhe-
cida abordagem de store-carry-forward. Embora os trabalhos de (BAKHOUYA; GABER;
LORENZ, 2011), (VILLAS et al., 2012) e (SILVA et al., 2017) nao implementem solucoes
para o problema de particoes na rede, tambem nao sofrem com o overhead provocado pelos
beacons para desempenhar a disseminacao. Embora diversas solucoes sejam apresentadas
na literatura para disseminacao de dados, a esmagadora maioria nao utiliza informacoes
globais como pre-requisito, como e o caso dos trabalhos de (LEQUERICA; RUIZ; CA-
BRERA, 2010), (UCAR; ERGEN; OZKASAP, 2016) e (KHAN et al., 2019). Assim sendo,
o presente trabalho propoe-se a desenvolver mais a ideia de utilizar a rede celular, nao
presa a tecnologia de uma unica geracao, a fim de entregar informacoes de controle aos veı-
culos que participam da disseminacao de dados. O presente trabalho apresenta melhorias
em relacao aos protocolos da literatura apresentados no que tange a utilizacao do recurso
rede, reduzindo o numero de mensagens duplicadas bem como nao dando conhecimento
da mensagem aos veıculos nao interessados nela.
A Tabela 1 resume as informacoes acerca dos protocolos apresentados neste capıtulo
com destaque para os problemas classicos tratados em cada solucao alem da identificacao
do cenario para o qual a proposta foi desenvolvida.
42
Protocolo InformacoesProblemas Cenario
Broadcast storm Particoes na rede Urbano Rodovia
AID(BAKHOUYA; GABER; LORENZ, 2011) a bordo X - X -
CARRO(AKABANE et al., 2016) locais X X X X
CC-DEGREE(CUNHA et al., 2014) locais X X X -
CPB(LIU et al., 2018) locais X - - X
DDBC(COSTA et al., 2017) locais X - X -
DV-CAST(TONGUZ; WISITPONGPHAN; BAI, 2010) locais X X - X
GEDDAI(VILLAS et al., 2012) a bordo X - X -
Geo-Orientado(SILVA et al., 2017) a bordo X - X -
HYDIACK(MAIA et al., 2013) locais X X X -
TLCB(KHAN et al., 2019) globais X X X X
UV-CAST(VIRIYASITAVAT; BAI; TONGUZ, 2010) locais X X X -
VISIONS(LEQUERICA; RUIZ; CABRERA, 2010) globais X - X -
VMasC(UCAR; ERGEN; OZKASAP, 2016) globais X X X X
VOV(MAIA et al., 2015) locais X X X -
Tabela 1 – Protocolos propostos na literatura nos ultimos anos e suas caracte-rısticas em termos de informacoes necessarias, problemas tratados e cenariosatendidos.
Fonte: Proprio Autor
43
4 DISSEMINACAO BASEADA EM TRAJETORIA
Neste capıtulo o protocolo proposto TBD (Trajectory Based Dissemination) e apre-
sentado. O protocolo TBD considera a definicao de uma trajetoria para direcionar a dis-
seminacao de dados da origem ate a regiao a ser alcancada. O protocolo sera apresentado
em quatro etapas, conforme as secoes a seguir. Primeiro sera feita uma breve introducao
acerca do problema a solucionar e os requisitos assumidos. Em seguida, sera apresentada
a participacao da rede de celular, detalhando o conhecimento que ela fornece ao proto-
colo. O mecanismo de transmissao direcionado via broadcast e o modo de funcionamento
do protocolo sao explicados nas duas ultimas secoes.
4.1 Introducao
O objetivo deste protocolo e solucionar o problema de transmitir uma mensagem
de um local origem ate uma regiao destino (SALEH; HASSON, 2019). Pretende-se fazer
com que uma mensagem originada a partir de alguma aplicacao trafege pela rede ate
os veıculos na regiao de interesse, e na regiao de interesse seja disseminada a todos os
veıculos, como exemplificado pela Figura 11.
Para alcancar este objetivo, as seguintes premissas foram assumidas:
(i) Os veıculos estao equipados com dispositivo de comunicacao sem fio com mesmo
alcance de comunicacao
(ii) Os veıculos estao conectados a rede celular
(iii) Os veıculos estao equipados com dispositivo GPS (Global Positioning System)
(iv) A mensagem a ser transmitida carrega a localizacao da regiao de interesse
(v) O veıculo origem da mensagem esta fora da regiao de interesse
Embora o envolvimento da rede celular em redes veiculares seja uma possibilidade
desde o inıcio, a maioria das solucoes propostas para disseminacao de dados em redes
44
veiculares so envolvem os modos de comunicacao V2V e V2I. Em grande parte esta situ-
acao se deve ao fato de a rede celular apresentar latencia para a comunicacao superior a
latencia no modo de comunicacao V2V, feita atraves do protocolo IEEE 802.11p.
Apesar das condicoes pouco favoraveis destacadas, a rede celular pode ser vista
como uma oportunidade no que tange a infraestrutura existente. Alem disso, considerar
que todos os veıculos estejam conectados a rede celular e uma premissa que pode ser
verificada nos dias de hoje, diante da popularizacao dos smartphones e dos servicos que
estes oferecem para condutores de veıculos e no futuro os veıculos estarao equipados com
chip 5G (5GAA, 2016).
Assumindo essas condicoes, o cenario indicado para o presente protocolo e o se-
guinte: (i) o veıculo origem da mensagem esta distante da regiao de interesse; (ii) a rede
e densa de veıculos em alguns pontos e nao densa em outros, cenario urbano tıpico; (iii)
a regiao de interesse esta distante do veıculo origem da mensagem, mas contem diversos
veıculos. Dessa forma, para que o objetivo seja alcancado e necessario que o veıculo ori-
gem transmita a mensagem para os veıculos mais indicados para a tarefa de encaminha-la
pela rede, e atraves de saltos a regiao de interesse seja alcancada. No interior da regiao
de interesse, e necessario que ela seja disseminada para todos os veıculos, tarefa capaz de
responder pela confiabilidade do protocolo. A Figura 11 apresenta um cenario exemplo
em que VO representa a posicao do veıculo origem da mensagem e Vd os veıculos destinos
da mensagem, localizados no interior da regiao de interesse. A Figura 11 apresenta ainda
uma rota possıvel para a mensagem, tal que os veıculos Vin sao selecionados para retrans-
mitirem as mensagens. Os demais pontos representam veıculos que nao sao interessados
na mensagem e nao executam retransmissoes.
O presente protocolo utiliza a comunicacao via rede celular em todo tempo de
deslocamento dos veıculos atualizando suas localizacoes junto a uma entidade global que
fornece informacoes precisas e globais a todos os veıculos na rede, mas nao e um recurso
utilizado para a disseminacao de dados propriamente dita, permanecendo a comunicacao
V2V como meio para a transmissao das mensagens entre os veıculos.
4.2 Participacao da Rede Celular
Como requisito fundamental da disseminacao, a mensagem deve alcancar os veıcu-
los no interior da regiao de interesse. Neste contexto, o TBD trabalha para efetuar esta
tarefa minimizando o consumo dos recursos de rede. Assim, atraves de uma interacao
com a rede celular, o protocolo obtem informacao da densidade de veıculos por regiao, de
forma a definir a trajetoria que a mensagem ira percorrer ate alcancar a regiao de destino.
Para que este conhecimento seja possıvel, definiu-se que os veıculos encaminhem
45
Figura 11 – Cenario indicado para utilizacao do protocolo TBD
Fonte: Proprio autor
suas posicoes geograficas a cada instante de tempo definido para um servidor externo,
atraves da comunicacao via rede celular. Este servidor externo e o responsavel por ar-
mazenar e processar os dados de posicao submetidos pelos veıculos e quando alguma
aplicacao demandar pelas informacoes de posicao, fornecer a informacao. Por exemplo,
uma aplicacao pode demandar o conhecimento acerca da densidade de veıculos numa via
que pretende acessar cujo valor sera determinante na decisao de fazer ou nao aquele tra-
jeto. Basicamente a comunicacao com a rede celular permite que, ao fornecer informacao
local, os veıculos podem usufruir do conhecimento acerca do comportamento global do
transito. Essa abordagem e uma alternativa a troca constante de beacons entre os veıculos,
o que contribui para reduzir o consumo de recursos da rede V2V e maximiza a precisao e
a dimensao das informacoes que sao compartilhadas entre os veıculos.
Para a presente estrategia, definiu-se que o mapa da cidade e representado por
celulas quadradas. Cada quadrado imaginario definido representa no servidor uma celula
da matriz. Dessa forma, a quantidade de veıculos e contabilizada por celulas e nao por
toda a cidade. A Figura 12 ilustra a divisao de um cenario quadrado em celulas. Neste
exemplo, cada celula trata-se de um quadrado menor de lado equivalente ao tamanho do
raio de alcance do dispositivo de comunicacao. Dessa forma, a partir dos envios atraves
da rede celular de mensagens de localizacao de cada veıculo e das celulas definidas, tem-se
uma matriz de densidades.
A Figura 12 identifica visualmente os locais densos de veıculos em cor escura, com
46
Figura 12 – Exemplo de matriz de densidades, conforme atualizacoes de veı-culos nas celulas.
Fonte: Proprio Autor
valores mais proximos ou iguais a 100 e os locais mais esparsos com cores mais claras e
valores mais proximos ou iguais a 0. Com a frequencia definida, a matriz de densidades
passa por mudancas constantemente, conforme a rotina do transito. A frequencia do
envio destas mensagens pode ser definida de forma estatica, por um intervalo de tempo
ou ainda conforme a movimentacao de cada veıculo, permitindo um numero menor de
submissoes de mensagens atraves da rede celular para veıculos lentos que nao saıram da
celula enquanto se deslocava.
Conhecendo a matriz de densidades, e possıvel criar um grafo com pesos nos ver-
tices, que representem as densidades de veıculos nas celulas correspondentes. Primeira-
mente, para determinar a conectividade do grafo, estabeleceu-se que as celulas se conectam
com suas celulas vizinhas imediatas de tal forma que o maximo de vizinhos que uma ce-
lula pode ter a um salto e 8, podendo as celulas perifericas ter 3 ou 5 celulas vizinhas.
Alem disso, os valores de densidades sao convertidos em pesos para os vertices do grafo.
A conversao feita ocorre atraves da simples inversao de numerador e denominador, o que
garante que os maiores valores de densidades apresentem os menores valores de pesos e
por sua vez, os menores valores de densidades apresentem os maiores valores de pesos. A
equacao 4.1 generaliza a conversao de uma celula n em um vertice n.
Vn =1
peson(4.1)
Considerando o grafo definido anteriormente, a Figura 13 ilustra a conversao da
matriz de densidades da Figura 12 num grafo com pesos nos vertices. A partir do grafo
47
de pesos, definiu-se que as arestas terao como valor a soma dos pesos dos vertices nela
conectados. Isto e, para uma aresta A-B, seu valor sera a soma dos pesos dos vertices
A e B. O grafo preenchido com os valores de arestas e utilizado na presente proposta
para que seja encontrado o caminho mais denso de veıculos da origem ate o destino
da mensagem. Foi definido o algoritmo de Dijkstra o responsavel pelo calculo, fazendo-se
necessaria a conversao da matriz de densidades num grafo cujos vertices apresentem pesos
menores para celulas com maiores densidades de veıculos e pesos maiores para celulas com
menores densidades de veıculos, dessa forma, permitindo o calculo de valores para arestas
cujo caminho mais curto representa o caminho mais denso no cenario.
Figura 13 – Densidades de veıculos convertidas em pesos nos vertices, que porsua vez sao convertidos em valores de arestas, entrada valida para o algoritmode Dijkstra.
Fonte: Proprio autor
Na Figura 13, pode-se verificar, em tom de cinza mais escuro, os nos cujas celulas
na matriz de densidade da Figura 12 sao pouco densos, e em cor mais clara os nos cujas
celulas apresentam densidades maiores. A posterior conversao do grafo com pesos nos
vertices para os valores de arestas e necessaria para que o grafo seja entrada valida para
o algoritmo de Dijkstra. Com densidades maiores convertidas aos menores caminhos, a
saıda do algoritmo favorecera essas regioes. Dessa forma, todos os veıculos, assim que
recebem a mensagem, apuram as informacoes de densidade e calculam o melhor caminho,
naquele instante de tempo, ate a regiao de interesse, de tal forma que nao necessariamente
o caminho calculado pelos veıculos no salto 2 sera o mesmo para os veıculos no salto n-2,
por exemplo. A dinamicidade da topologia, responsavel pela definicao de densidades nas
diferentes celulas, pode interferir no caminho conforme os saltos durante a disseminacao
de dados.
48
4.3 Transmissao direcionada via broadcast
A partir do caminho entre as celulas de origem e destino retornado pelo algoritmo
de Dijkstra, a mensagem pode ser encaminhada por meio da comunicacao V2V ate a regiao
de interesse. Assim, alguns dos veıculos pertencentes a essa rota devem encaminhar a
mensagem. Destaca-se que os veıculos realmente interessados no conteudo da mensagem
sao os veıculos localizados no interior da regiao de interesse, por sua vez os veıculos
envolvidos no encaminhamento da mensagem ate a regiao de interesse nao sao interessados
na mensagem. Isso mostra que um numero mınimo de veıculos deve ser envolvido no
encaminhamento da mensagem pois essa medida vai garantir mais eficiente utilizacao do
meio de comunicacao.
A caracterıstica que deseja-se melhorar atraves da implementacao de um trajeto
entre a origem e o destino e a reducao da comunicacao na disseminacao de dados. Uma
das formas de mensurar a comunicacao na disseminacao de dados e atraves do numero
de veıculos que recebem a tarefa de transmitir a mensagem. Em razao da metodologia
comumente adotada na literatura, que considera o veıculo origem da mensagem no interior
da regiao de interesse, os protocolos propostos ficam restritos a determinadas aplicacoes
alem da mensuracao nao ser totalmente efetiva. Por exemplo, aplicacoes de notificacoes de
um acidente devem imediatamente alcancar os veıculos proximos, tornando aquela regiao,
a regiao de interesse. No entanto, a comunicacao entre veıculos do local do acidente e
um veıculo de resgate, que nao esteja no interior da regiao de interesse, e tambem de
grande importancia, o que justifica um olhar menos restrito para a area envolvida na
disseminacao de dados.
Considerando a comunicacao de mensagem cuja origem nao e a regiao de interesse,
faz-se necessaria a escolha de alguns poucos veıculos encaminhadores da mensagem a fim
de que veıculos nao partes do caminho bem como os nao interessados na mensagem nao
envolvam-se na comunicacao, o que consumiria recursos de rede de maneira desnecessaria.
Para alcancar a finalidade apresentada, e proposta a utilizacao do mecanismo de
transmissao direcionada via broadcast que define um cone de retransmissao. Conforme
mostra a Figura 14, o cone de retransmissao e uma area no interior do raio de alcance
do dispositivo de comunicacao, definido conforme um angulo determinado. A definicao
deste cone de retransmissao para comunicacao direcionada ocorre em funcao da natureza
da comunicacao no modo V2V, em que os veıculos comunicam-se com todos os vizinhos
via broadcast de forma nao direcionada. Assim sendo, considerou-se que os veıculos no
interior daquele cone devem efetuar retransmissoes para que a mensagem seja propagada
naquela direcao. Este mecanismo e ilustrado na Figura 14 em que o veıculo v0 representa
a origem da mensagem e os demais veıculos ate o veıculo vn representam veıculos parte
do caminho ate o destino da mensagem, a regiao de interesse. O raio de alcance do
49
Figura 14 – A retransmissao so e feita na area do cone, a cada salto ate aregiao de interesse.
Fonte: Proprio Autor
dispositivo de comunicacao e representado pelo cırculo completo em volta de cada veıculo
e equivalente para todos os veıculos. A regiao no interior do raio de alcance do dispositivo
de comunicacao e entao dividida em duas partes: a regiao em cinza, onde estao os veıculos
potenciais receptores da mensagem, que poderao verificar o seu destino e descarta-la, e na
regiao em verde, denominada cone de retransmissao, onde estao os veıculos que receberao
a tarefa de retransmitirem a mensagem. Dessa forma, a tarefa de retransmissao das
mensagens limita-se aos veıculos no interior do cone de retransmissao, cuja definicao da
area e determinada conforme o caminho que a mensagem deve percorrer.
Ainda observando a Figura 14, observa-se o limite da zona de recepcao. Uma
vez que os veıculos nas extremidades superior e inferior do cone efetuem retransmissoes,
o limite para a zona de recepcao e determinado, no exemplo da Figura 14, pela linha
pontilhada em vermelho. Basicamente a largura da regiao pela qual a mensagem sera
recebida, ou seja, a largura do trajeto da mensagem no cenario ate a regiao de interesse,
tem dimensao maxima de 3 cones paralelos.
A premissa estabelecida de conhecimento da regiao de interesse (destino da men-
sagem) e importante para que cada veıculo, ao verificar o caminho da celula em que se
encontra ate a regiao de interesse, consiga estimar a posicao do cone de retransmissao.
50
Em razao da regiao de interesse nao ser um local especıfico, com uma unica coordenada
geografica, define-se como seu ponto de referencia, preferencialmente, a coordenada ge-
ografica central da regiao. Alem da posicao do cone de retransmissao, faz-se necessario
definir o angulo do cone, de forma estatica ou dinamica, de tal forma que as regioes muito
densas de veıculos recebam cones menos abertos e regioes nao tao densas recebam cones
mais abertos. Esta possibilidade de adaptacao do cone permite a proposta a reducao do
numero de mensagens transmitidas mesmo limitadas ao cone, o que e considerada pratica
valida para mitigacao dos problemas de broadcast storm.
4.4 Funcionamento basico do protocolo TBD
As secoes anteriores destacaram a obtencao das informacoes pelos veıculos acerca
do melhor caminho para se enviar a mensagem e a forma como os veıculos sao selecionados
para este envio. Nesta Secao, os algoritmos envolvidos na disseminacao propriamente
dita serao detalhados, de forma que consolide-se o entendimento acerca do protocolo de
disseminacao de dados baseado em trajetoria.
Para que a mensagem seja disseminada, e necessario que um veıculo origem a
emita inicialmente. Apos a emissao da mensagem, cada um dos veıculos que a receberam
verificarao se estao no interior do cone de retransmissao para que ela seja encaminhada
ate a regiao de interesse. Este procedimento e executado atraves do Algoritmo 1.
Algoritmo 1: Algoritmo TBD – Trajectory Based Dissemination.
1 Evento: Decisao sobre retransmitir m recebida do vizinho v
2 se veıculo esta na regiao de interesse entao3 retransmite m com algoritmo de supressao;4 fim5 senao6 se veıculo esta no cone de v entao7 retransmite m com algoritmo de supressao;8 fim9 senao
10 descarta m;11 fim
12 fim
A execucao do Algoritmo 1 determinara se o veıculo receptor da mensagem m do
vizinho v esta no interior do cone de retransmissao para que a retransmissao seja feita no
trajeto da mensagem. Primeiro, o veıculo verifica se encontra-se na regiao de interesse
(linha 2), neste caso nao existe a necessidade de encaminhar a mensagem pelo cone de
retransmissao ate a regiao de interesse, portanto basta que o Algoritmo 2 seja executado
(linha 3). Se o veıculo nao esta na regiao de interesse, como e a premissa assumida,
51
o veıculo entao verifica se encontra-se no interior do cone de retransmissao do veıculo v
(linha 6). Se o veıculo encontrar-se no interior do cone de retransmissao de v, a mensagem
e retransmitida por meio do Algoritmo 2 (linha 7). Caso o veıculo nao esteja no interior do
cone de retransmissao de v, a mensagem e descartada (linha 10), pois o veıculo encontra-se
apenas em zona de recepcao, conforme a Figura 14.
O procedimento descrito para o algoritmo do protocolo TBD fara com que a men-
sagem seja encaminhada salto a salto ate encontrar a regiao de interesse, e no interior
da regiao de interesse seja executado o Algoritmo 2. No Algoritmo 2, quando um veıculo
recebe uma mensagem de dados sinalizada para retransmissao (linha 1), ele deve adicio-
nar a mensagem m na lista de mensagens recebidas (linha 2). Em seguida, calcular um
intervalo de tempo para retransmissao (linha 3) de acordo com a distancia em relacao ao
vizinho v. Enquanto maior a distancia (distancia em relacao ao veıculo do qual recebeu
a mensagem, ate o limite do raio do dispositivo de comunicacao), menor sera o tempo
definido para a retransmissao (maior tempo possıvel equivalente a 500 ms). A escolha de
500 ms como limite para o tempo maximo acompanha o trabalho de (VIRIYASITAVAT;
BAI; TONGUZ, 2010), em que os autores encontraram 500 ms como um valor de limite
superior. Vale destacar que se a distancia for igual ao raio de alcance do dispositivo de
comunicacao, a retransmissao e feita imediatamente. O calculo do tempo e feito atraves
do seguinte modelo matematico:
t = (1.0− min(DS,r)r
)∗500 (4.2)
Neste modelo, DS refere-se a distancia do veıculo do qual recebeu a mensagem e r ao
raio de alcance do dispositivo de comunicacao, parametros da funcao min(), que retorna
o menor entre os dois valores.
Com o tempo calculado (linha 3), verifica-se a existencia de agendamento para re-
transmissao futura (linha 4). Se existir agendamento e este for o primeiro agendamento,
cancela-se e efetua um reagendamento para o tempo t calculado (linha 6). Caso nao seja
o primeiro agendamento, cancela-se o envio da mensagem m (linha 9). Esta verificacao
acompanha uma das estrategias basicas para melhorias no algoritmo de flooding, introdu-
zida no Capıtulo 2 com o nome counter-based-scheme. Nesta estrategia, conta-se o numero
de retransmissoes assumindo que a recepcao de muitas mensagens implica em retransmis-
soes desnecessarias. O reagendamento de mensagens caracteriza a recepcao duplicada da
mensagem.
Caso verifique que nao existe agendamento de retransmissao da mensagem m, o
veıculo efetua o primeiro agendamento para o tempo t (linha 13). Assim que o tempo
t expirar, a mensagem e entao retransmitida (linhas 15 e 16). Atraves do mecanismo
de transmissao direcionada via broadcast e deste algoritmo de supressao de broadcast,
52
Algoritmo 2: Algoritmo de supressao de broadcast.
1 Evento: mensagem de dados m recebida do vizinho v sinalizada para retransmissao2 adicionar m na lista de mensagens recebidas;
3 t← obterTempoDeRetransmissao();4 se o envio de m esta agendado entao5 se agendada 1 vez entao6 cancela e efetua reagendamento para tempo t;7 fim8 senao9 cancela o envio da mensagem m;
10 fim
11 fim12 senao13 efetua agendamento para tempo t;14 fim
15 Evento: tempo t de agendamento da mensagem m expira16 Retransmite m;
os veıculos mais proximos do objetivo de levarem a mensagem ao destino na regiao de
interesse terao prioridade na retransmissao da mensagem.
Este capıtulo apresentou com detalhes o protocolo TBD - Trajectory Based Disse-
mination, no proximo capıtulo serao feitas avaliacoes de desempenho sob o aspectos de
confiabilidade e economia de recursos de rede.
53
5 AVALIACAO DE DESEMPENHO E RESULTADOS
O presente capıtulo compreende a avaliacao de desempenho do protocolo proposto
TBD sob aspectos de confiabilidade e economia de recursos de rede. Alem disso, apresenta
tambem uma analise de fatores que impactam a disseminacao de dados a fim de determinar
quais fatores mais influenciam as avaliacoes de protocolos de disseminacao de dados da
literatura. Dessa forma, este capıtulo esta dividido em duas secoes, a primeira secao lida
com a avaliacao de desempenho do protocolo TBD e em seguida a secao de analise dos
fatores que impactam a disseminacao de dados.
5.1 Simulacao do Protocolo TBD
5.1.1 Introducao
A avaliacao de desempenho da solucao proposta foi efetuada por meio de simula-
coes em ambiente virtual e teve como ferramentas o simulador de rede OMNeT++ 4.6
(VARGA, 2003) e como simulador de mobilidade a ferramenta SUMO 0.25.0 (BEHRISCH
et al., 2011), ambos por meio do framework de redes veiculares VEINS (SOMMER; GER-
MAN; DRESSLER, 2011).
Os resultados foram comparados com protocolos da literatura AID, CARRO e UV-
CAST, introduzidos no Capıtulo 3. A escolha dos protocolos UV-CAST e CARRO se deve
ao fato de implementarem a difusao de beacons para conhecimento da vizinhanca local,
de maneira semelhante ao protocolo TBD que efetua submissoes de posicoes geograficas
periodicamente a rede movel para conhecimento da densidade global. Alem disso, foi
selecionado tambem o protocolo AID para a comparacao com uma abordagem puramente
estatıstica.
Dois cenarios para simulacoes foram adotados nesta avaliacao de performance. O
primeiro cenario trata-se de um grid com mobilidade gerada atraves do simulador de
mobilidade SUMO. O segundo cenario e um ambiente real, alguns quarteiroes da cidade
de Belo Horizonte, Brasil, cuja mobilidade tambem foi gerada atraves do simulador de
mobilidade SUMO. Nas subsecoes a seguir serao descritos com mais detalhes os cena-
rios, os parametros de simulacao, as metricas utilizadas na avaliacao e os resultados das
54
simulacoes.
Na subsecao 5.1.2 e 5.1.3 sao apresentados os detalhes dos cenarios de simulacao,
dimensoes, formato e as vias. Em seguida, nas subsecoes 5.1.4 e 5.1.5 sao definidos os
parametros de simulacao. Na subsecao 5.1.6 sao descritas as metricas selecionadas para
comparacao de desempenho dos protocolos e finalmente a subsecao 5.1.7 apresenta as
discussoes e os resultados de simulacao.
5.1.2 Cenario de Simulacao em grid
A avaliacao do protocolo proposto TBD exige a implementacao de um cenario que
favoreca a ocorrencia do problema de broadcast storm. Para esta finalidade, definiu-se um
grid com 20 vias duplas, uniformemente espacadas em uma area de 2000 × 1000 metros.
Esta decisao se deve ao fato de ser um cenario urbano que apresenta condicoes semelhantes
para todos os veıculos.
Figura 15 – Cenario de simulacao implementado. Um grid com dimensoes 2000× 1000 metros
Fonte: Proprio Autor
A Figura 15 apresenta o cenario implementado. Neste cenario, a mensagem parte
da origem O e deve percorrer o cenario ate alcancar o destino D, localizado no centro da
regiao de interesse. Como adiantado no Capıtulo 4, o ponto D e apenas um ponto de
referencia da regiao de interesse, de forma que o objetivo final da mensagem e alcancar
todos os veıculos em seu interior. No cenario da Figura 15, a regiao em verde representa
a regiao de interesse. Da origem O ate o destino D, a figura sugere tres rotas possıveis,
dentre as diversas que podem ocorrer para a entrega da mensagem a regiao de interesse.
No entanto, em termos de espaco existe uma rota otima, a que exigira menos saltos ate
que a entrega seja feita. O protocolo TBD em um cenario de densidade equivalente para
cada celula procura esta rota otima.
55
Para o presente cenario foi assumido que cada quarteirao tem 100 × 100 metros.
A Figura 16 representa cada intersecao entre as vias. Cada via apresenta duas faixas
de rolamento, uma para cada um dos sentidos. Alem disso, os cruzamentos sao dotados
de sinalizacao semaforica. Neste cenario de grid foi definido que os veıculos surgem de
maneira aleatoria e suas rotas sao definidas no interior do cenario, de forma que veıculos
nao podem surgir fora e adentrar o grid ou surgirem no interior do grid e saırem dele.
Figura 16 – Intersecoes entre vias do grid
Fonte: (VILLAS et al., 2012)
5.1.3 Cenario de Belo Horizonte
Em consonancia com o proposto pelo cenario de simulacao em grid, este cenario
de Belo Horizonte tambem favorece a ocorrencia do problema de broadcast storm. No
entanto, diferente das caracterısticas do grid, o espaco selecionado no presente cenario nao
apresenta vias uniformemente espacadas, o que permite uma abordagem mais realıstica
na simulacao.
A Figura 17 e uma ilustracao do mapa do centro da cidade de Belo Horizonte,
com dimensoes aproximadas de 1600 × 1000 metros com vias de dois bairros centrais,
Santo Agostinho e Lourdes. Alem da verificacao de desempenho do protocolo mediante as
metricas definidas, este cenario permite verificar o mecanismo de transmissao direcionada
via broadcast implementada. Para tal, foi bloqueado um quarteirao central do cenario, de
forma que o caminho da mensagem obrigatoriamente deve desviar do centro para alcancar
a regiao de interesse, fazendo uma curva pelo caminho mais denso de veıculos. A Figura
18 ilustra o bloqueio efetuado no cenario.
Neste cenario os veıculos surgem de maneira aleatoria, nunca no interior do quar-
teirao bloqueado e em nenhum momento tem acesso as vias internas do quarteirao. De
maneira diferente do cenario de grid, os veıculos podem sair do cenario delimitado uma
56
Figura 17 – Cenario de Belo Horizonte composto por vias dos bairros SantoAgostinho e Lourdes
Fonte: OpenStreetMap em 11/01/2020
vez que a rota do veıculo pode envolver parte de vias que nao estao no cenario e da mesma
forma podem surgir a partir de deslocamentos por essas vias.
5.1.4 Parametros de Simulacao para Cenario de grid
Dadas as dimensoes do cenario de grid implementado, 2000 × 1000 metros, definiu-
se como origem O da mensagem uma RSU localizada na posicao (200, 200) e na outra
extremidade do mapa, a regiao de interesse foi definida como os ultimos 400 × 400 metros,
com centro na posicao (1800, 800), identificado como destino D, conforme exemplifica a
Figura 15. Destaca-se que a unica funcao desta RSU neste ambiente de simulacao e o
inıcio da disseminacao, de forma que ela encaminhe a mensagem com destino a todos os
veıculos no raio de alcance de seu dispositivo de comunicacao, que e equivalente ao raio
de alcance dos dispositivos de comunicacao dos veıculos no cenario. Assumiu-se que o
dispositivo de comunicacao tem alcance equivalente a 250 metros.
O angulo do cone de retransmissao e definido de maneira dinamica, conforme in-
troduzido no Capıtulo 4. Para este cenario de grid, o angulo do cone de retransmissao
varia entre 100◦ e 130◦ conforme a densidade de veıculos, eliminando transmissoes de
veıculos que se encontram no espaco dos 260◦ e 230◦ fora do cone, respectivamente. Com
o objetivo de quantificar a evolucao do trafego neste cenario, a densidade de veıculos foi
57
Figura 18 – Cenario de Belo Horizonte com identificacao do quarteirao centralbloqueado
Fonte: OpenStreetMap em 11/01/2020
variada de 100 veıculos/km2 a 300 veıculos/km2. O trafego neste cenario foi gerado pelo
simulador de mobilidade SUMO.
A RSU posicionada nas coordenadas (200, 200) gera 1 mensagem de 2048 bytes aos
15 s de simulacao, com tempo de vida (time-to-live - TTL) equivalente a 30 s, dessa forma
definiu-se o tempo de cada simulacao como 55 s. O tempo maximo de espera atribuıdo
aos veıculos para que retransmitem via broadcast e de 500 ms seguindo valores usuais
encontrados na literatura.
Para o protocolo TBD no cenario de grid foram simuladas tres frequencias de
atualizacao de posicao junto a rede celular sendo elas 1, 5 e 9 segundos. Simulacoes
nessas condicoes poderao responder pelo desempenho do protocolo em situacoes em que a
comunicacao com a rede celular falhar, ou seja, a densidade de veıculos esta desatualizada.
5.1.5 Parametros de Simulacao para Cenario de Belo Horizonte
O cenario de Belo Horizonte apresenta dimensoes 1600 × 1000 metros. A partir
dessas dimensoes, definiu-se o local de origem da mensagem a ser disseminada a coorde-
nada (350, 350) a fim de se alcancar a regiao de interesse, tambem localizada na outra
extremidade do cenario. A regiao de interesse no cenario de Belo Horizonte foi definida
como os ultimos 600 × 350 metros, com centro na coordenada (1300, 825).
58
O tempo maximo de espera para retransmissao foi mantido o mesmo do cenario de
grid, bem como o alcance do raio de comunicacao e o angulo do cone de retransmissao.
No entanto, a frequencia de mensagens de localizacao foi definida como 1 s e a densidade
de veıculos neste cenario e de 100 a 250 veıculos/km2. A Tabela 2 resume os parametros
de simulacao.
Parametro Grid Belo HorizonteTamanho da area total 2000 × 1000 m 1600 × 1000 mTamanho da area da ROI 400 × 400 m 600 × 350 mOrigem da mensagem (200, 200) (350, 350)Tamanho da mensagem 2048 bytes 2048 bytesDestino da mensagem (1800, 800) (1300, 825)Tempo maximo de espera 500 ms 500 msAlcance do raio de comunicacao 250 m 250 mAngulo do cone de retransmissao 100o a 130o 100o a 130o
Frequencia de mensagens de localizacao 1, 5 e 9 s 1 sDensidades de veıculos 100 a 300 v/km2 100 a 250 v/km2
Tabela 2 – Resumo dos parametros de simulacao
Fonte: Proprio Autor
A Tabela 3 apresenta os valores utilizados em simulacoes para adaptacao do angulo
do cone de retransmissao. Observe que o parametro que define a variacao da dimensao
do angulo do cone e a densidade de veıculos global, fornecida pela comunicacao via rede
celular, e a proposta deste trabalho lida com cenarios de altas densidades de veıculos. A
Tabela 3 e referencia para os dois cenarios avaliados neste estudo.
Densidade de veıculos Angulo
100 a 140 veıculos/km2 130o
140 a 200 veıculos/km2 120o
200 a 240 veıculos/km2 110o
240 a 300 veıculos/km2 100o
Tabela 3 – Valores de adaptacao do cone de retransmissao, conforme densidadede veıculos
Fonte: Proprio Autor
5.1.6 Metricas de avaliacao
A proposta deste protocolo pretende alcancar uma boa taxa de entrega utilizando
do recurso de rede de maneira eficiente, especialmente nao efetuando transmissoes desne-
59
cessarias, ou seja, nao dando conhecimento da informacao contida na mensagem a veıculos
que nao tem interesse nela. Para esta finalidade, as seguintes metricas foram selecionadas:
• Taxa de entrega na ROI: Representa o percentual de veıculos alcancados dentro
da regiao de interesse. O desafio nesta avaliacao e garantir uma cobertura total
desta regiao. Diferente da metrica anterior, quando a taxa de entrega em relacao a
regiao de interesse for alta, significa que a cobertura do protocolo e satisfatoria.
• Mensagens duplicadas: Esta metrica representa o total de mensagens repetidas
recebidas pelos veıculos durante o processo de disseminacao. Desempenham melhor
sob o ponto de vista desta metrica os protocolos que apresentarem um percentual
menor de mensagens duplicadas.
• Percentual de veıculos transmissores: Com esta metrica, e possıvel avaliar o
percentual de veıculos envolvidos durante a disseminacao. E importante destacar
que uma boa solucao deve garantir uma boa cobertura da ROI, evitando o overhead,
i.e., mensagens transmitidas desnecessariamente. Assim, quanto menor for essa
taxa, melhor sera o desempenho da solucao.
• Atraso medio na entrega: Esta metrica representa a media do tempo que uma
mensagem de dados leva para ser transmitida da origem ate o destino. Muitas
aplicacoes em redes veiculares apresentam restricoes de atraso, por exemplo, servicos
de alerta. Para estes tipos de aplicacoes, as mensagens devem ser disseminadas o
mais rapido possıvel.
• Numero de saltos: Esta e uma metrica que reflete o numero de veıculos envolvidos
na entrega da mensagem, ou seja, o numero de saltos entre o veıculo origem e o
veıculo receptor da mensagem. Para cada salto existe a recepcao, processamento
de decisao e a espera para a retransmissao, portanto, um numero de saltos menor
implica num atraso menor para a entrega.
Nao e objeto deste estudo mensurar o desempenho da rede celular, este e um
objetivo para trabalhos futuros. Neste trabalho, usufrui-se do benefıcio concedido pela
rede celular, o que pode fornecer intuicoes relacionadas ao custo-benefıcio de servicos em
redes veiculares orientados pela rede celular.
5.1.7 Resultados
5.1.7.1 Resultados para o cenario de Grid
Para o cenario de grid , foram efetuados um total de 50 replicacoes de simula-
coes. Os resultados apresentados a seguir representam a media dos valores obtidos com
60
essas replicacoes. As legendas dos graficos a seguir identificam como TBD 1 o protocolo
TBD com intervalo de atualizacao de localizacao de 1 segundo, TBD 5 para intervalo de
atualizacao de localizacao de 5 segundos e TBD 9 para 9 segundos.
O grafico da Figura 19 apresenta a taxa de entrega no interior da regiao de in-
teresse. Pode-se observar que os protocolos UV-CAST, AID e TBD com atualizacoes
de densidade de veıculos a cada 1 segundo apresentam comportamento semelhante, en-
tregando a mensagem em toda a regiao de interesse. Em razao do maior intervalo entre
atualizacoes de densidade, o protocolo TBD com atualizacoes a cada 5 e a cada 9 segundos
sofrem um pouco para entregarem a mensagem. Isso ocorre devido a falta de precisao nas
informacoes de localizacao, o que pode gerar atrasos e gargalos durante o encaminhamento
da mensagem ate a regiao.
Figura 19 – Taxa de entrega no interior da ROI no cenario em grid
Fonte: Dados de pesquisa
O grafico da Figura 20 apresenta o numero de mensagens duplicadas por veıcu-
los em todo o cenario. E possıvel observar que o protocolo TBD apresenta os melhores
resultados, pois limita o numero de mensagens transmitidas a poucos veıculos, consequen-
temente duplicando menos. De acordo com o seu funcionamento, que define um cone que
direciona a retransmissao das mensagens, a quantidade de veıculos retransmissores e redu-
zida. Mesmo com informacoes menos precisas, o protocolo TBD com atualizacoes a cada
5 e 9 segundos reduzem o numero de mensagens duplicadas em aproximadamente 50%
se comparado aos demais protocolos. Nota-se tambem que os demais protocolos, por nao
implementarem nenhum mecanismo de contencao na disseminacao, apresentaram valores
bem superiores e com crescimento acelerado conforme o aumento da densidade de veıcu-
los, entretanto, o protocolo TBD tende a aumentar o numero de mensagens duplicadas
61
mais lentamente, visto que a largura do caminho que a mensagem percorre e estatico e o
aumento de veıculos retransmissores so ocorre no interior dos cones de retransmissao dos
veıculos.
Figura 20 – Numero de mensagens duplicadas recebidas no cenario em grid
Fonte: Dados de pesquisa
Ao observar a taxa de veıculos transmissores no grafico da Figura 21, verifica-se
conformidade com os resultados apresentados no grafico da Figura 20. A quantidade de
veıculos envolvidos na disseminacao pelo protocolo TBD e inferior em todas as densidades,
e reduz conforme a densidade de veıculos aumenta, fenomeno que fica mais evidente em
cenarios maiores, nos quais a quantidade de veıculos envolvido no caminho da mensagem
e um numero muito pequeno em relacao ao numero de veıculos que compreendem todo
o cenario. Ao comparar com as demais solucoes avaliadas neste cenario, pode-se verificar
que cerca de 25% dos veıculos estao envolvidos na disseminacao dos dados, o que explica
os resultados obtidos com relacao a metrica de mensagens duplicadas.
Pode-se observar os resultados para o atraso medio na Figura 22. Nota-se que
o protocolo TBD apresenta resultados bastante satisfatorios comparado aos demais da
literatura, igualando ao protocolo AID que tambem apresenta um atraso baixo. Tanto o
protocolo CARRO e UV-CAST adicionam atraso nas retransmissoes como mecanismo de
contencao para o problema de broadcast storm. Por esse motivo esses protocolos apresen-
tam valores superiores. Ao analisar o comportamento do TBD, pode-se notar um bom
desempenho do protocolo em todas as suas tres versoes, independente da densidade de
veıculos avaliada.
Ao analisar o numero medio de saltos efetuados na disseminacao Figura 23, observa-
se que em media o TBD apresenta 2 saltos a menos que os demais. A metrica atraso medio
62
Figura 21 – Percentual de veıculos transmissores em todo o cenario em grid
Fonte: Dados de pesquisa
Figura 22 – Atraso medio para o alcance da regiao de interesse
Fonte: Dados de pesquisa
apresentar valores inferiores para o protocolo TBD esta diretamente ligado a quantidade
de saltos efetuados da origem ao destino da mensagem, assim, por apresentar um numero
de saltos inferior, o protocolo TBD apresenta melhores resultados em termos de atraso
medio.
Alem dos resultados apresentados sob as metricas definidas na subsecao 5.1.6,
percebeu-se que o intervalo de tempo entre os acessos a rede celular para submissao das
novas posicoes pouco influenciou o desempenho do protocolo. Esta informacao sugere
63
que conforme o tempo passa, as densidades de veıculos no mapa nao sofrem mudancas
significativas em relacao aos segundos anteriores devido aos veıculos estarem limitados
pelas restricoes espaciais. Essa informacao contribui com a avaliacao de custo financeiro
dos acessos a rede movel, sugerindo que sao desnecessarios acessos muito frequentes devido
a nao agregarem informacoes capazes de refletir em melhoria no desempenho.
Figura 23 – Grafico do numero medio de saltos para o alcance da regiao deinteresse
Fonte: Dados de pesquisa
5.1.7.2 Resultados para o cenario de Belo Horizonte
Para o cenario de Belo Horizonte, foram efetuados um total de 50 replicacoes de
simulacoes. Os resultados apresentados a seguir representam a media dos valores obtidos
com essas replicacoes.
O grafico da Figura 24 ratifica o apurado nas simulacoes do cenario de grid. Quando
verificada a taxa de entrega no interior da ROI, verifica-se que os protocolos AID, UV-
CAST e TBD mantem bom desempenho. Embora o desempenho destes protocolos sejam
semelhantes, o protocolo TBD nao apresenta 100% de taxa de entrega no interior da ROI
neste cenario, isso ocorre em funcao do quarteirao isolado no mapa nao estar perfeitamente
centralizado. Essa nao centralizacao faz com que replicacoes com densidade maior na parte
mais estreita do mapa (parte superior) provoca mais perdas de mensagens.
Por outro lado, a avaliacao sob o ponto de vista das metricas mensagens duplicadas
e percentual de veıculos retransmissores estao dispostas na Figura 25. A quantidade de
mensagens duplicadas em todas as densidades simuladas nao passa de 2 mensagens por
veıculo e se mantem estavel mesmo com o aumento da densidade. Esta informacao e
64
Figura 24 – Taxa de entrega no interior da ROI no cenario de Belo Horizonte
Fonte: Dados de pesquisa
confirmada pela taxa de veıculos transmissores, que permanece sempre abaixo do protocolo
AID, o que desempenha melhor entre os tres protocolos da literatura selecionados. Alem
de transmitir um menor numero de mensagens, o numero de mensagens duplicadas e
pequeno devido ao mecanismo de transmissao direcionada implementado, com a definicao
do cone de retransmissao, que garante envios limitados geograficamente pelo cone.
Por ultimo a analise do atraso medio para a entrega das mensagens, bem como
o numero de saltos necessarios para que a mensagem alcance os veıculos na regiao de
interesse e apresentado na Figura 26.
Figura 25 – Numero de mensagens duplicadas e percentual de veıculos trans-missores
Fonte: Dados de pesquisa
65
Figura 26 – Atraso medio na transmissao da mensagem e numero medio desaltos ate a ROI
Fonte: Dados de pesquisa
Tal como apurado no experimento do cenario de grid, o atraso medio para a en-
trega da mensagem e muito baixo, apresentando desempenho pouco inferior ao protocolo
AID, que por sua natureza estatıstica apresenta retransmissoes mais rapidas. De maneira
semelhante, o numero medio de saltos para o alcande da regiao de interesse e menor na
solucao proposta em razao da preferencia de escolha por veıculos na borda do alcance
do raio do dispositivo de comunicacao. Embora outras solucoes tambem optem por esse
mecanismo, os veıculos selecionados no interior do cone, na borda, apresentam melhor
desempenho que os demais veıculos na borda de todo o raio de comunicacao.
Os resultados apurados no cenario de Belo Horizonte ratificam os resultados apre-
sentados no cenario de grid, com alteracoes ocorridas em virtude da assimetria do cenario
do mapa real bem como do quarteirao isolado, o oposto do cenario de grid que e perfeita-
mente simetrico.
5.2 Projeto Experimental
5.2.1 Introducao
A disseminacao de dados em redes veiculares e afetada por diversos fatores. Estes
fatores sao alvo de estudos para que protocolos sejam desenvolvidos e os explorem com
a finalidade de alcancar melhor desempenho em relacao aos objetivos da atividade de
disseminacao de dados.
Embora exista um grande numero de protocolos na literatura, poucos se propuse-
ram a identificar fatores que impactam na disseminacao de dados como forma de contribuir
66
para os estudos no campo das redes veiculares. Assim sendo, nesta secao sera apresen-
tado um projeto experimental com o objetivo de explorar alguns fatores fundamentais que
influenciam o desempenho de qualquer proposta de solucao para a disseminacao.
Nas subsecao 5.2.2 sera descrita a metodologia dos experimentos. Em seguida sera
apresentada a obtencao e caracterizacao dos dados com destaque para o cenario de redes
veiculares e a escolha dos fatores na subsecao 5.2.3. Por fim, a subsecao 5.2.4 apresentara
os resultados do projeto experimental com destaque para o conhecimento alcancado.
5.2.2 Metodologia dos Experimentos
Este estudo e baseado no projeto fatorial 2k. O projeto fatorial 2k, conforme
descrito por Raj Jain (JAIN, 1990), e utilizado para determinar o efeito de k fatores, cada
um com duas alternativas ou nıveis. O autor de (JAIN, 1990) avalia que esta classe de
projeto fatorial e facil de analisar e ajuda ordenar fatores em ordem de impacto. O projeto
fatorial 2k define que deve haver uma variavel resposta que e o resultado a ser mensurado
no experimento, alem de k outras variaveis que sao os fatores que afetam esta variavel
resposta, e cada um dos fatores possuem dois valores alternativos chamados nıveis.
Diz-se que os fatores interagem entre si, se o efeito de um depende do nıvel de outro.
Diante disso, foram feitas simulacoes para a obtencao dos dados a serem submetidos ao
projeto fatorial.
5.2.3 Obtencao e Caracterizacao dos Dados
Os dados utilizados para este projeto fatorial sao resultados de simulacoes executa-
das em simuladores de redes veiculares. O cenario de simulacao implementado e um grid.
A escolha do grid como cenario para avaliacao do protocolo deve-se a simplicidade de
implementacao e ao fato de apresentar condicoes equivalentes a todos os veıculos, repre-
sentacao considerada suficiente para avaliacao da capacidade de disseminar dados. Para
avaliacao dos protocolos, definiu-se um grid com 10 vias duplas uniformemente espacadas
em uma area de 1 km2 com quarteiroes de 100m x 100m. O trafego neste cenario foi
gerado pelo simulador de mobilidade SUMO e no centro do grid foi posicionada uma RSU
(Road Side Unit), responsavel pela criacao e envio da mensagem a ser disseminada.
A RSU participa da simulacao unicamente efetuando o envio de uma unica men-
sagem de tamanho 2048 bytes. Para cada densidade de veıculos foram simuladas 50
replicacoes e os resultados apresentam valores medios. A implementacao dos protocolos
bem como do cenario foi feita com a utilizacao do simulador de redes OMNET++ atraves
do framework de redes veiculares VEINS.
Para este experimento, e importante que os dados de simulacoes de fatores que
67
impactam a disseminacao de dados assumem valores extremos (JAIN, 1990). Neste es-
tudo foram avaliadas tres variaveis resposta, sendo elas: mensagens recebidas, mensagens
transmitidas e colisao de mensagens. Atraves da revisao bibliografica, levantou-se os se-
guintes fatores para este projeto fatorial: solucao adotada, densidade de veıculos e raio
de alcance do dispositivo de comunicacao. A seguir sao detalhados os fatores e os valores
assumidos nos dois nıveis do projeto experimental.
• Solucao adotada: o primeiro fator considerado para avaliacao e a solucao utilizada
para disseminacao. Diversas sao as solucoes existentes na literatura, mas para este
experimento foram selecionados os protocolos AID, e UV-CAST introduzidos no
Capıtulo 3. A escolha das duas solucoes se deve ao fato de serem fundamental-
mente diferentes, empregarem recursos distintos na estrategia, alem da aceitacao
da comunidade cientıfica mensurada pela referenciacao bibliografica. A Tabela 4
apresenta caracterısticas que distanciam as solucoes em termos do modo de funcio-
namento. Para este experimento, consideramos a solucao AID no nıvel -1 e a solucao
UV-CAST no nıvel 1.
Tabela 4 – Diferencas entre as solucoes adotadas.
AID UV-CASTDecisoes tomadas localmente, sem co-nhecimento dos vizinhos
Difusao de beacons para estimar topolo-gia a 1-salto.
Baseia-se em estatıstica. Baseia-se em informacoes de contexto
Trata apenas o problema de broadcaststorm
Tratamento do problema de broadcaststorm e do problema de particoes na rede
Emprega Distance-Based Scheme eDelay-Based Scheme
Emprega apenas Delay-Based Scheme
Fonte: Proprio Autor
• Densidade de veıculos: o segundo fator selecionado e a densidade de veıculos no ce-
nario. Este fator e bastante utilizado na avaliacao de protocolos de disseminacao de
dados a fim de transparecer o comportamento do protocolo em cenarios com poucos
e muitos veıculos. Este fator independe do protocolo e nao e possıvel controla-lo,
entretanto, estima-lo e parte de muitos algoritmos que se propoe a solucionar os
problemas da disseminacao de dados. Notadamente, protocolos desempenham de
maneira diferente sob diversas metricas em cenarios com poucos veıculos se com-
parados com cenarios com muitos veıculos. Para esta avaliacao o fator densidade
assume o valor 60 veıculos/km2 no nıvel -1, representando cenarios esparsos e 350
veıculos/km2 no nıvel 1 representando cenarios densos.
68
• Raio de alcance do dispositivo de comunicacao: o terceiro e ultimo fator selecionado
e o raio de alcance do dispositivo de comunicacao. Os protocolos de disseminacao
de dados da literatura costumam utilizar alcances diversos em suas avaliacoes, in-
clusive alcances dinamicos, que se ajustam conforme a proposta do protocolo. De
modo geral, os alcances em metros variam de 150 a 300 metros, o que afeta conside-
ravelmente os resultados de simulacoes. Para esta avaliacao de fatores foi definido
o valor 150 metros no nıvel -1 e 300 metros no nıvel 1 para o alcance do dispositivo.
Alem disso, definiu-se que o alcance e estatico.
A Tabela 5 apresenta de forma resumida os fatores, seus identificadores e os valores
que assumem nos dois nıveis.
Tabela 5 – Fatores e valores assumidos nos dois nıveis.
ID FATORES -1 1
A Solucao adotada AID UV-CASTB Densidade de veıculos 60 350C Raio de alcance do dispositivo de comunicacao 150 300
Fonte: Proprio Autor
5.2.4 Resultados
Dados os fatores descritos na subsecao 5.2.3, a Tabela 6 apresenta os fatores, suas
combinacoes e a simbologia adotada para exibicao dos resultados.
Tabela 6 – Representacao adotada para exibicao dos resultados.
Fatores Sımbolo
Solucao ADensidade BRaio da comunicacao CSolucao & Densidade ABSolucao & Raio da Comunicacao ACDensidade & Raio da Comunicacao BCSolucao & Densidade & Raio da Comunicacao ABC
Fonte: Proprio Autor
A ideia por tras de um projeto fatorial 2k e que o valor da variavel resposta pode
ser obtido dos valores das variaveis xA, xB e xC usando o seguinte modelo nao linear:
y = q0 +qAxA +qBxB +qCxC +qABxAxB +qACxAxC +qBCxBxC +qABCxAxBxC (5.1)
69
Na Equacao 5.1, y e a variavel resposta, q0 e a media dos valores da variavel
resposta para todas as possibilidades de variacao dos fatores e cada uma das q∗ variaveis
e a influencia de um ou mais fatores na variavel resposta.
A B C AB AC BC ABC y
-1 -1 -1 1 1 1 -1 33.84-1 -1 1 1 -1 -1 1 92.84-1 1 -1 -1 1 -1 1 41.31-1 1 1 -1 -1 1 -1 83.341 -1 -1 1 -1 1 1 53.031 -1 1 -1 1 -1 -1 82.031 1 -1 -1 -1 -1 -1 42.121 1 1 1 1 1 1 62.74
Tabela 7 – Resultados do projeto fatorial para variavel resposta mensagensrecebidas.
Fonte: Dados de pesquisa
A Tabela 7 trata da variavel resposta mensagens recebidas. Esta tabela representa
nas primeiras 3 colunas todas as possibilidades de valores assumidos para as variaveis A,
B e C. Os valores nas colunas em seguida sao os produtos dos valores dessas variaveis
interagindo entre si. Por ultimo, a coluna y representa a media de mensagens recebidas
das 50 replicacoes das simulacoes executadas. Dado o modelo nao linear 5.1 e a Tabela 7,
temos a seguinte equacao:
y= 61.41−1.42xA−4.02xB+18.83xC−3.52xAxB−6.42xAxC−3.16xBxC+1.07xAxBxC (5.2)
A Equacao 5.2 pode ser interpretada da seguinte forma. O numero medio de men-
sagens recebidas e 61.41, o efeito do fator solucao (qA) e -1.42, o efeito do fator densidade
de veıculos (qB) e -4.02 e o efeito do raio de alcance do dispositivo de comunicacao (qC) e
18.83. Em seguida a Equacao 5.2 exibe o efeito de combinacoes desses fatores.
O grafico apresentado junto a Tabela 7 descreve os resultados do projeto fatorial
para a variavel resposta mensagens recebidas. Este grafico nos revela a importancia de
se justificar a escolha dos valores para o raio de alcance do dispositivo de comunicacao.
Pode-se notar que o valor do raio de comunicacao escolhido, que aqui decidiu-se por
alternar entre 150 e 300 metros, tem aproximadamente 74.55% de impacto nos resultados
70
das simulacoes quando observada a variavel resposta mensagens recebidas. Tambem, em
todas as simulacoes em que o valor do fator C e 1, o valor de y e maior, ou seja, sempre
que o fator raio de alcance do dispositivo de comunicacao assumir o nıvel mais alto (300
metros), uma transmissao alcancara mais veıculos e portanto o numero de mensagens
recebidas sera maior.
A B C AB AC BC ABC y
-1 -1 -1 1 1 1 -1 24.85-1 -1 1 1 -1 -1 1 61.33-1 1 -1 -1 1 -1 1 28.84-1 1 1 -1 -1 1 -1 143.921 -1 -1 1 -1 1 1 28.481 -1 1 -1 1 -1 -1 42.401 1 -1 -1 -1 -1 -1 21.361 1 1 1 1 1 1 77.10
Tabela 8 – Resultados do projeto fatorial para variavel resposta mensagenstransmitidas.
Fonte: Dados de pesquisa
y = 53.53−11.2xA +14.27xB +27.65xC−7.37xAxB−10.23xAxC +15.05xBxC−4.60xAxBxC
(5.3)
O grafico apresentado junto a Tabela 8 trata-se dos resultados do projeto fatorial
para a variavel resposta mensagens transmitidas, cujos efeitos dos fatores sao apresen-
tados na Equacao 5.3. Atraves deste grafico podemos verificar que o raio de alcance do
dispositivo de comunicacao permanece com grande influencia no numero de mensagens
transmitidas durante as simulacoes, corroborando o resultado apresentado anteriormente.
Embora apresentando impacto maior, 41,89%, os valores apresentados pelos demais fatores
nao devem ser descartados, afinal, tambem apresentam valores significativos. Observando
a Tabela 8 pode-se observar que quando a densidade de veıculos e alta e o raio de alcance
do dispositivo de comunicacao e alto, o protocolo AID transmite aproximadamente 2x o
numero de mensagens se comparado ao UV-CAST. Isso sugere que estrategias nao rıgidas,
ou seja, que se adaptam conforme a densidade de veıculos muda, podem ser mais eficientes
na decisao de retransmitir a mensagem.
71
A B C AB AC BC ABC y
-1 -1 -1 1 1 1 -1 7.63-1 -1 1 1 -1 -1 1 9.055-1 1 -1 -1 1 -1 1 11.85-1 1 1 -1 -1 1 -1 43.651 -1 -1 1 -1 1 1 55.571 -1 1 -1 1 -1 -1 74.841 1 -1 -1 -1 -1 -1 48.151 1 1 1 1 1 1 244.24
Tabela 9 – Resultados do projeto fatorial para variavel resposta colisoes demensagens.
Fonte: Dados de pesquisa
y= 61.87+43.82xA+25.10xB+31.07xC+15.39xAxB+22.76xAxC+25.90xBxC+18.30xAxBxC
(5.4)
Por sua vez, a Tabela 9 apresenta os resultados do projeto fatorial para a variavel
resposta colisoes de mensagens. O grafico da Tabela 9 ressalta a influencia do fator
solucao adotada na analise de colisao de pacotes. Embora o protocolo UV-CAST transmita
apenas cerca de 50% do numero de mensagens que o protocolo AID no cenario mais
denso com raio da comunicacao mais alto, o UV-CAST provoca aproximadamente 5x
mais colisoes. Observe ainda que existem fatores nao relacionados neste experimento que
podem impactar mais que qualquer um dos relacionados no aspecto das colisoes, revelando
a necessidade de estudos mais profundos acerca do assunto.
Segundo (JAIN, 1990), esses valores percentuais permitem facilmente calibrar a
importancia dos fatores, ou seja, fatores com um percentual de variacao alto sao consi-
derados importantes. No entanto, o autor chama atencao para o fato de que um fator
que representa 60% de variacao pode representar ou nao 60% da variancia total de y e
que o percentual da variancia e bastante difıcil de computar, assim sendo, o percentual
de variacao e muito util no auxılio a tomada de decisoes.
O objetivo definido para este projeto experimental era de identificar a influencia de
alguns fatores na disseminacao de dados. Atraves da selecao dos fatores solucao adotada,
densidade de veıculos e raio de alcance do dispositivo de comunicacao, que estao envolvi-
dos em todos os cenarios de disseminacao de dados em redes veiculares, identificou-se a
72
importancia de se fundamentar a escolha do raio de alcance do dispositivo de comunicacao
em simulacoes.
73
6 CONCLUSAO E TRABALHOS FUTUROS
6.1 Conclusao
Neste trabalho foi proposto um protocolo de disseminacao de dados que permitisse
o encaminhamento de uma mensagem do local de emissao ate a regiao de interesse daquela
mensagem. Em seguida, no interior da regiao de interesse, a mensagem fosse difundida a
todos os veıculos interessados. Para este fim, o protocolo proposto utilizou a infraestrutura
existente nas cidades, a rede celular, como forma de comunicacao de controle. Cada
veıculo atualiza sua posicao via rede celular periodicamente, permitindo que os demais
veıculos da cidade conhecam as densidades de veıculos de cada regiao. Atraves desse
conhecimento, o protocolo TBD faz com que a mensagem seja transmitida por um caminho
orientado a densidade de veıculos, de forma que a mensagem a ser disseminada na regiao de
interesse nao seja entregue e retransmitida por veıculos fora da regiao de interesse ou fora
deste caminho da disseminacao. Os resultados de simulacoes mostraram que o protocolo
desempenha bem para o problema proposto, reduzindo de maneira expressiva o numero de
mensagens duplicadas assim como o numero de veıculos nao interessados na mensagem que
a recebem. Foi verificado tambem que o percentual de veıculos transmissores diminuiu,
o que explica a reducao no numero de mensagens duplicadas, sem mudanca significativa
na entrega aos veıculos no interior da regiao de interesse. Alem disso, foi observado
que o intervalo entre atualizacoes pouco interfere nos resultados de entrega e custo de
transmissoes, o que permite implementacoes com custos reduzidos mantendo-se registros
de localizacao desatualizados por mais tempo.
Tambem foi feito um estudo atraves do projeto experimental fatorial 2k em que tres
fatores foram analisados a fim de identificar qual deles mais influenciavam os resultados
da disseminacao, alem de quanto influenciavam. Os fatores definidos para o experimento
foram (1) solucao proposta, (2) densidade de veıculos e (3) raio de alcance do dispositivo
de comunicacao. Atraves do experimento concluiu-se que o raio de alcance do dispositivo
de comunicacao dos veıculos e o fator que mais influencia os resultados da disseminacao
de dados e sua escolha deve ser fundamentada visto que valores usuais na literatura
apresentam resultados discrepantes.
74
6.2 Trabalhos Futuros
Para trabalhos futuros, pretende-se utilizar do conhecimento dos veıculos sobre
seus destinos e velocidades para tornar as atualizacoes a rede celular dinamicas, sensıveis
as informacoes locais de cada veıculo na rede. Essas informacoes permitirao a tomada de
decisao mais inteligente acerca do intervalo de tempo entre as atualizacoes de posicao, o
que pode reduzir o numero de acessos a rede. Alem disso, pretende-se avaliar novas formas
para definicao da trajetoria, reduzindo a quantidade de veıculos transmissores sem com-
prometer a cobertura da disseminacao na regiao de interesse. Finalmente, implementar
solucao que atenda situacoes e cenarios em que a rede celular nao encontra-se disponıvel
em todas as regioes, bem como avaliar o desempenho da rede celular na disseminacao de
dados, inclusive utilizando-se dos recursos que as redes 5G hao de oferecer.
75
REFERENCIAS
5GAA. The case for cellular v2x for safety and cooperative driving. White Paper, 5GAutomotive Association, november 2016. Disponıvel em: <http://5gaa.org/pdfs/5GAA-whitepaper-23-Nov-2016.pdf>.
AHMAD, S. A.; SHCHERBAKOV, M. A survey on routing protocols in vehicularadhoc networks. In: 2018 9th International Conference on Information,Intelligence, Systems and Applications (IISA). Zakynthos, Greece: IEEE, 2018.p. 1–8.
AKABANE, A. et al. Carro: A context-awareness protocol for data dissemination inurban and highway scenarios. In: IEEE. Communications (LATINCOM), 2016 8thIEEE Latin-American Conference on. Medellin, Colombia, 2016. p. 1–6.
AMGOUNE, H.; MAZRI, T. 5g: Interconnection of services and security approaches.In: Proceedings of the 3rd International Conference on Smart CityApplications. New York, NY, USA: Association for Computing Machinery, 2018. (SCA’18).
BAKHOUYA, M.; GABER, J.; LORENZ, P. An adaptive approach for informationdissemination in vehicular ad hoc networks. Journal of Network and ComputerApplications, Elsevier, v. 34, n. 6, p. 1971–1978, 2011.
BEHRISCH, M. et al. Sumo–simulation of urban mobility. In: The ThirdInternational Conference on Advances in System Simulation (SIMUL2011). Barcelona, Spain: ThinkMind, 2011.
CHEN, S. et al. Vehicle-to-everything (v2x) services supported by lte-based systems and5g. IEEE Communications Standards Magazine, IEEE, v. 1, n. 2, p. 70–76, 2017.
COSTA, J. et al. Centrality-based data dissemination protocol for vehicular adhoc networks. In: 2017 IEEE 16th International Symposium on NetworkComputing and Applications (NCA). Cambridge, MA, USA: IEEE, 2017. p. 1–4.
CUNHA, F. D. et al. Socially inspired data dissemination for vehicular ad hoc networks.In: ACM. Proceedings of the 17th ACM international conference onModeling, analysis and simulation of wireless and mobile systems. NewYork, NY, USA, 2014. p. 81–85.
GONCALVES, F. B. Relatorio tecnico: Controle distribuıdo de trafego baseadoem veıculos conectados e comunicacoes veiculares centradas em interesses. CoRR,abs/1708.00741, 2017. Disponıvel em: <http://arxiv.org/abs/1708.00741>.
JAIN, R. The art of computer systems performance analysis: techniquesfor experimental design, measurement, simulation, and modeling.Chichester, UK: John Wiley & Sons, 1990.
76
JALOOLI, A.; SONG, M.; WANG, W. Message coverage maximiza-tion in infrastructure-based urban vehicular networks. Vehicular Com-munications, v. 16, p. 1 – 14, 2019. ISSN 2214-2096. Disponıvel em:<http://www.sciencedirect.com/science/article/pii/S221420961830161X>.
KHAN, Z. et al. Two-level cluster based routing scheme for 5g v2x communication.IEEE Access, IEEE, v. 7, p. 16194–16205, 2019.
LEQUERICA, I.; RUIZ, P. M.; CABRERA, V. Improvement of vehicular communicationsby using 3g capabilities to disseminate control information. IEEE Network, v. 24,n. 1, p. 32–38, Jan 2010. ISSN 0890-8044.
LIU, L. et al. A data dissemination scheme based on clustering and probabilisticbroadcasting in vanets. Vehicular Communications, Elsevier, v. 13, p. 78–88, 2018.
LU, Z.; QU, G.; LIU, Z. A survey on recent advances in vehicular network security, trust,and privacy. IEEE Transactions on Intelligent Transportation Systems,v. 20, n. 2, p. 760–776, Feb 2019. ISSN 1524-9050.
MACHADO, M. V. et al. Data dissemination in autonomic wireless sensor networks.IEEE Journal on Selected Areas in Communications, IEEE, v. 23, n. 12, p.2305–2319, 2005.
MAIA, G. et al. Data dissemination in urban vehicular ad hoc networks with diversetraffic conditions. In: 2013 IEEE Symposium on Computers and Communications(ISCC). Split, Croatia: IEEE, 2013. p. 000459–000464. ISSN 1530-1346.
MAIA, G. et al. A rate control video dissemination solution for extremely dynamicvehicular ad hoc networks. Performance Evaluation, Elsevier, v. 87, p. 3–18, 2015.
NICULESCU, D.; NATH, B. Trajectory based forwarding and its applications. In:Proceedings of the 9th Annual International Conference on MobileComputing and Networking. New York, NY, USA: Association for ComputingMachinery, 2003. p. 260–272.
ONISHI, H. A survey: Engineering challenges to implement vanet security. In: 2018IEEE International Conference on Vehicular Electronics and Safety(ICVES). Madrid, Spain: IEEE, 2018. p. 1–6.
SALEH, H. H.; HASSON, S. T. A survey of routing algorithms in vehicular networks.In: 2019 International Conference on Advanced Science and Engineering(ICOASE). Zakho - Duhok, Iraq, Iraq: IEEE, 2019. p. 159–164.
SHARMA, A.; AWASTHI, L. K. A comparative survey on information disseminationin heterogeneous vehicular communication networks. In: 2018 First InternationalConference on Secure Cyber Computing and Communication (ICSCCC).Jalandhar, India, India: IEEE, 2018. p. 556–560.
SILVA, L. H. C. et al. Geo-oriented protocol: Retransmissions and hops analysis. IEEELatin America Transactions, v. 15, n. 12, p. 2298–2304, Dec 2017. ISSN 1548-0992.
77
SOMMER, C.; GERMAN, R.; DRESSLER, F. Bidirectionally Coupled Network andRoad Traffic Simulation for Improved IVC Analysis. IEEE Transactions on MobileComputing, IEEE, v. 10, n. 1, p. 3–15, January 2011.
SPYROPOULOS, T.; PSOUNIS, K.; RAGHAVENDRA, C. S. Efficient routing inintermittently connected mobile networks: the multiple-copy case. Networking,IEEE/ACM Transactions on, IEEE, v. 16, n. 1, p. 77–90, 2008.
TONGUZ, O. K.; WISITPONGPHAN, N.; BAI, F. Dv-cast: A distributed vehicularbroadcast protocol for vehicular ad hoc networks. IEEE Wireless Communications,IEEE, v. 17, n. 2, p. 47–57, 2010.
TOOR, Y. et al. Vehicle ad hoc networks: applications and related technical issues.IEEE Communications Surveys Tutorials, v. 10, n. 3, p. 74–88, Third 2008. ISSN1553-877X.
TSENG, Y.-C. et al. The broadcast storm problem in a mobile ad hoc network.Wireless networks, Springer, v. 8, n. 2-3, p. 153–167, 2002.
UCAR, S.; ERGEN, S. C.; OZKASAP, O. Multihop-cluster-based ieee 802.11p and ltehybrid architecture for vanet safety message dissemination. IEEE Transactions onVehicular Technology, v. 65, n. 4, p. 2621–2636, April 2016. ISSN 0018-9545.
VARGA, A. Omnet++ simulator. Department of Telecommunications,Technical University of Budapest, Budapest, Hungary, 2003.
VILLAS, L. A. et al. An efficient and robust data dissemination protocol for vehicular adhoc networks. In: Proceedings of the 9th ACM symposium on Performanceevaluation of wireless ad hoc, sensor, and ubiquitous networks. New York,NY, USA: Association for Computing Machinery, 2012. p. 39–46.
VIRIYASITAVAT, W.; BAI, F.; TONGUZ, O. K. Uv-cast: an urban vehicular broadcastprotocol. In: IEEE. Vehicular Networking Conference (VNC), 2010 IEEE.Jersey City, NJ, USA, 2010. p. 25–32.
W.H.O. Global status report on road safety 2013: supporting a decade of action:summary. World Health Organization, 2013.
WILLIAMS, B.; CAMP, T. Comparison of broadcasting techniques for mobile ad hocnetworks. In: Proceedings of the 3rd ACM international symposium onMobile ad hoc networking & computing. New York, NY, USA: Association forComputing Machinery, 2002. p. 194–205.