Universidade Federal do Rio de Janeiro

Escola Politécnica

Departamento de Eletrônica e de Computação

Proposta de Roteamento para Redes Veiculares Tolerantes a Atrasos

Autor:

_________________________________________________ Rafael Portugal Serrado

Orientador:

_________________________________________________ Prof. Aloysio de Castro Pinto Pedroza, Dr.

Examinador:

_________________________________________________ Prof. Heraldo Luís Silveira de Almeida, D. Sc.

Examinador:

_________________________________________________ Prof. Sérgio Barbosa Villas Boas, Ph. D.

DEL

Junho de 2014

ii

UNIVERSIDADE FEDERAL DO RIO DE JANEIRO

Escola Politécnica – Departamento de Eletrônica e de Computação

Centro de Tecnologia, bloco H, sala H-217, Cidade Universitária

Rio de Janeiro – RJ CEP 21949-900

Este exemplar é de propriedade da Universidade Federal do Rio de Janeiro, que

poderá incluí-lo em base de dados, armazenar em computador, microfilmar ou adotar

qualquer forma de arquivamento.

É permitida a menção, reprodução parcial ou integral e a transmissão entre

bibliotecas deste trabalho, sem modificação de seu texto, em qualquer meio que esteja ou

venha a ser fixado, para pesquisa acadêmica, comentários e citações, desde3 que sem

finalidade comercial e que seja feita a referência bibliográfica completa.

Os conceitos expressos neste trabalho são de responsabilidade do(s) autor(es) e

do(s) orientador(es).

iii

AGRADECIMENTO

Agradeço aos meus pais, Arlindo e Solange, por todo carinho e apoio que me

dedicaram e por eventualmente perderem a paciência, mas nunca a confiança em mim. À

minha irmã, Isabelle, pelo companheirismo, preocupação e por ser meu braço na

universidade, sempre disposta a ajudar. À minha namorada, Patrícia, por seu incentivo e

compreensão constantes, além de apoio irrestrito.

Agradeço em especial ao meu chefe e amigo, Renato, por ter voluntariamente se

apresentado como co-orientador, me oferecendo dados, ideias e experiência que se

mostraram fundamentais para esse projeto.

Agradeço aos professores da graduação e em especial ao meu orientador, Aloysio,

que sempre me recebeu com ótimas sugestões e diálogos, e que sempre esteve

comprometido com o término do projeto.

iv

RESUMO

Na última década a Internet sofreu uma nova guinada com a introdução de redes

móveis, que prometiam conectividade em áreas cada vez mais abrangentes e que

rapidamente convergem para a conectividade a todo momento, em qualquer lugar. Para

isso, novos padrões emergiram para estender a robustez, eficiência e flexibilidade do

modelo TCP/IP consolidado na Internet a novas aplicações em diferentes cenários. Um

desses cenários são as chamadas redes veiculares. Nelas, veículos comunicam-se entre si

ou com uma infraestrutura, levando o modelo TCP/IP também aos motoristas e

passageiros.

No entanto, em cenários de longos atrasos e frequentes desconexões, os

protocolos TCP/IP não funcionam e novos protocolos são necessários. Redes com essas

características são denominadas Redes Tolerantes a Atrasos (Delay Tolerant Networks–

DTNs) e um dos seus principais desafios é o roteamento, pois é preciso determinar rotas

sem o estabelecimento de um caminho fim-a-fim.

Neste trabalho, é apresentada uma proposta de roteamento capaz de lidar com a

falta de conectividade por meio da previsão do movimento dos veículos em um cenário

controlado. Tal proposta foca na diminuição da latência a um baixo custo em termos do

número de transmissões, réplicas de mensagens e espaço ocupado nos buffers. A

eficiência do protocolo foi testada em um simulador de rede utilizando um cenário

imaginado baseado em dados coletados de uma rodovia real.

Palavras-Chave: Internet, redes veiculares, DTN, roteamento, rodovia, conectividade

v

ABSTRACT

In the last decade, the Internet saw a great boom with the introduction of mobile

networks, which promised connectivity in increasingly larger areas and which rapidly

converges into connectivity at any time, in anywhere. For this purpose, new patterns

emerged to extend the flexibility, efficiency and reliability of the TCP/IP Internet model

to new applications in different scenarios. One of those scenarios are the so-called

vehicular networks, in which vehicles communicates between themselves and an

infrastructure, delivering the TCP/IP architecture to drivers and passengers.

Nevertheless, in scenarios of high delay and frequent disconnections, the TCP/IP

family protocols do not work properly and new protocols are necessary. Networks with

these traits are called Delay Tolerant Networks (DTNs) and one of the main challenges

is routing, since it is necessary to calculate routes without an end-to-end path.

In this work, a routing mechanism capable of dealing with the lack of connectivity

by predicting the vehicles’ movements in a controlled scenario is presented. This routing

protocol aims to lower the delay at a low cost in terms of number of transmissions, copies

of the messages and buffer space. The protocol’s efficiency was tested on a network

simulator using a topology based in data collected on a real interstate.

Key-words: Internet, vehicular networks, DTN, protocol, interstate, connectivity

vi

SIGLAS

ANT – Accident to Notification Time

ARP – Address Resolution Protocol

AU - Application Units

CAR – Contex-aware Routing

DNIT – Departamento Nacional de Infraestrutura de Transportes

DSRC – Dedicated Short-Range Communications

DTN – Delay Tolerant Network

ETSI – European Telecommunications Standards Institute

FCC - Federal Communications

GPRS – General Packet Radio Service

GPS – Global Positioning System

GSM – Global System for Mobile Communications

HSDPA - High-Speed Downlink Packet Access

IEEE – Institute of Electrical and Electronics Engineers

IP – Internet Protocol

ISO – International Organization for Standardization

ITS – Inteligent Transport System

LAN – Local Area Network

LTE – Long Term Evolution

MAC – Media Access Control

MANET – Mobile Ad Hoc Network

NS-2 – Network Simulator 2

OBU - On-board Units

OTcl – Object Tool Command Language

PAN – Personal Area Network

PROPHET – Probabilistic Routing Protocol using History of Encounters and

Transitivity

RSU – Road Side Unit

TCP – Transmission Control Protocol

V2I – Vehicle to Infrastructure

V2R – Vehicle to Road

V2V – Vehicle to Vehicle

vii

VADD – Vehicle-Assisted Data Delivery

VANET – Vehicular Ad Hoc Network

VDTN – Vehicular Delay Tolerant Network

WAN – Wide Area Network

WAVE – Wireless Access in Vehicular Environments

WiMAX - Worldwide Interoperability for Microwave Access

viii

Sumário

1 Introdução 1

1.1 - Motivação e Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.5 - Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.6 - Roteiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Redes Veiculares 5

2.1 - Características Especiais de Redes Veiculares . . . . . . . . . . . . 5

2.2 - Arquiteturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 - Padronização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 - Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4.1 - Segurança no Trânsito . . . . . . . . . . . . . . . . . . . . . 16

2.4.2 - Entretenimento . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4.3 - Assistência ao Motorista . . . . . . . . . . . . . . . . . . . 17

2.5 - Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 DTN e Trabalhos Relacionados 20

3.1 - Fundamentos e Características . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 - Roteamento em DTN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2.1 - Roteamento DTN Convencional . . . . . . . . . . . . . . . 24

3.2.2 - Protocolos de Roteamento VDTN . . . . . . . . . . . . . . 31

3.3 - Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

ix

4 Proposta 38

4.1 - Motivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.2 - Cenário considerado, arquitetura e premissas . . . . . . . . . . . . 40

4.3 - O Protocolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.4 - Considerações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5 Simulação e Resultados 51

5.1 - Citação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.1.1 - Arquitetura NS-2 . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.1.2 - O nó móvel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.1.3 - Gerador de tráfego . . . . . . . . . . . . . . . . . . . . . . . . 53

5.1.4 - Arquivos de Movimento e de Trace . . . . . . . . . . 54

5.2 - Parâmetros de Simulação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.2.1 - Configurando os nós . . . . . . . . . . . . . . . . . . . . . . 56

5.2.2 - Topologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.2.3 - Instanciando os nós . . . . . . . . . . . . . . . . . . . . . . . 61

5.3 - Desenvolvimento do Protocolo . . . . . . . . . . . . . . . . . . . . . . . . 63

5.4 - Desenvolvimento do Protocolo Epidêmico . . . . . . . . . . . . . . 65

5.5 - Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.5.1 - Teste 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.5.2 - Teste 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6 Conclusão 77

Bibliografia 79

x

A Trace do Novo Protocolo 82

B Trace do Protocolo Epidêmico 88

xi

Lista de Figuras

2.1 – Cenários de uma rede veicular. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 – Alocação de espectro para aplicações DSRC. . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 – Pilha de protocolos WAVE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 – Modelo de referência. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5 – Arquitetura C2C–CC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.6 – Arquitetura CALM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1 – Desafios para redes fim–a–fim. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 – Bundle Layer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3 – Nós DTN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.4 – Troca de mensagens no roteamento Epidêmico. . . . . . . . . . . . . . . . . . . . . . . 24

3.5 – Sessão anti–entropia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.6 – Exemplo de funcionamento do protocolo Spray–and–Wait com L=4. . . . . . 29

3.7 – Cálculo do ponto mais próximo entre o destinatário e os caminhos C1 e C2. 32

3.8 – Um exemplo do modelo de atraso do VADD. . . . . . . . . . . . . . . . . . . . . . . . . 34

3.9 – Seleção do próximo veículo em um cruzamento. . . . . . . . . . . . . . . . . . . . . . 35

4.1 – Densidade de tráfego na BR–290. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2 – Arquitetura proposta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.3 – Entrega da mensagem no cenário proposto. . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.4 – Transferência convencional x Transferência DTN. . . . . . . . . . . . . . . . . . . . . 44

4.5 – Diagrama de blocos de um veículo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.6 – Diagrama de blocos de uma RSU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.1 – Classe NSObject. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.2 – Conectores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

xii

5.3 – Saídas do NS–2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.4 – Topologia Inicial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.5 – Nó 0 deseja enviar uma mensagem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.6 – Topologia do Teste 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.7 – Nó 0 transmite para o nó 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.8 – Nó 4 transmite para o nó 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.9 – Nó 1 retransmite para o nó 4 em modo ganancioso. . . . . . . . . . . . . . . . . . . . 70

5.10 – Nó 4 retransmite para o nó 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.11 – Nó 5 transmite para o nó 0, respondendo a requisição. . . . . . . . . . . . . . . . . 72

xiii

Lista de Tabelas

2.1 – Comparação entre DSRC e ISM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5.1 – Latência obtida nos testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

A.1 – Estrutura do trace. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

1

Capítulo 1

Introdução

A popularização das redes sem fio vivida na década de 2000 expandiu o conceito

de conectividade para além das LANs com infraestrutura fixa. As redes de dados através

de telefonia móvel como as tecnologias 2G, 3G, e LTE (Long Term Evolution) além do

WIMAX ( Worldwide Interoperability for Microwave Access) e das redes pessoas (PANs)

utilizando Bluetooth ajudaram a criar a ideia de que a conectividade deve ser ubíqua. A

adoção do padrão de protocolos da família IEEE 802.11 pela indústria, no entanto foi a

grande responsável pela penetração das redes sem fio no mercado e o constante

barateamento do hardware necessário.

Como consequência da alta aceitação dos padrões 802.11, criou-se uma demanda

cada vez maior por novas soluções que levem conectividade a ambientes em que as redes

infraestruturadas encontram restrições à sua aplicabilidade que as áreas acadêmica e

comercial visam explorar. Redes ad hoc móveis (MANETs – Mobile Ad Hoc Networks)

é uma área que vem recebendo considerável atenção. Uma MANET é uma rede

autogeradora capaz de funcionar sem a necessidade de um controle centralizado. Cada nó

em uma rede ad hoc age tanto como terminal e como roteador. Estes nós utilizam sua

interface de rádio para se comunicar com outros nós que estiverem em seu alcance. O

benefício dessas redes é a facilidade e baixo custo de aplicação em lugares em que não é

economicamente viável instalar e administrar uma infraestrutura fixa.

As VANETs (Vehicular Ad Hoc Networks) são uma subclasse de MANETs cujos

nós são equipamentos de rede instalados em veículos automotores. Diversos trabalhos

como [6] e [4] mostram que tais redes podem ser construídas com interfaces de rede

802.11 disponíveis no mercado e portanto, de baixo custo. Tal facilidade junto a

possibilidade de se implementar diversas aplicações relacionadas a veículos, tráfego,

motoristas, passageiros e pedestres tornou as redes veiculares o objetivo de grupos de

pesquisas e fabricantes de automóveis. “Sistemas de Transporte Inteligente (ITS –

Inteligent Transport System) que visam simplificar a operação de veículos, gerenciar o

tráfego automotivo, auxiliar os motoristas com aplicações de segurança e prover

2

informações relevantes à motoristas e passageiros são factíveis e estarão presentes nas

estradas e veículos em futuro próximo” [8].

Apesar das facilidades, as redes veiculares encontram alguns obstáculos técnicos

para sua implementação, como a alta mobilidade dos veículos, grande variação da

velocidade relativa entre os nós, frequentes desconexões e utilização de aplicações em

tempo real. Além disso, a escalabilidade da rede se torna um problema, em especial em

aplicações que requerem que a informação seja retransmitida por múltiplos saltos entre

carros, já que redes veiculares podem ser as redes ad hoc mais distribuídas e com o maior

número de nós.

1.1 – Motivação e Objetivo

Dentre as aplicações de redes veiculares, destacam-se aquelas voltadas à

segurança. Segundo dados do Departamento Nacional de Infraestrutura de Transportes

(DNIT), no ano de 2011 foram registrados 188.925 nas rodovias do país, dentre os quais

7.008 tiveram vítimas fatais. Aplicações de segurança em redes veiculares podem ajudar

a diminuir esse número e preservar a vida humana.

Uma aplicação que atende a esse fim é a notificação automática de acidentes. O

tempo discorrido entre o acidente e a notificação dos sistemas de emergência médicos

(ANT – Accident to Notification Time) pode ser crucial para evitar fatalidades. Em [7], o

autor cita dados do departamento de trânsito dos EUA de 1990 que mostram que o ANT

de acidentes com fatalidades em rodovias urbanas chegava a até 15,2 minutos. Parece

seguro afirmar que em áreas rurais esse tempo seja consideravelmente maior. No Brasil,

não há dados disponíveis sobre ANT, mas é presumível que o tempo seja ainda maior.

Em casos extremos, como uma rodovia pouco movimentada em horário de baixo tráfego,

esse tempo tende a ser bem superior.

Para minimizar esse tempo, a aplicação pode transmitir um pedido de socorro que

é encaminhado através de múltiplos saltos para o ponto de emergência mais próximo,

diminuindo o tempo de resposta para atendimento ao acidente. Para que aplicação

funcione entretanto, é preciso sobrepujar os problemas das desconexões constantes e da

segmentação da rede.

Para lidar com estas restrições de conectividade, a arquitetura DTN permite que

se armazene persistentemente mensagens em uma nova camada de rede denominada

bundle layer, com isto, ela torna-se capaz de utilizar o paradigma armazena-carrega-

3

encaminha, isto é, uma mensagem é armazenada, em um nó e segue com ele até que seja

encaminhada para um segundo nó quando houver conectividade. É através dessa camada

que a DTN consegue fornecer comunicação entre redes descontínuas. No caso de

VANETs, ela se aproveita da mobilidade do veículo para armazenar um bundle e

encaminhá-lo a outro nó VANET quando possível.

Essa nova arquitetura exige protocolos de roteamento próprios, já que os

protocolos convencionais de roteamento TCP/IP não atendem ao paradigma armazena-

carrega-encaminha. Há na literatura exemplos de protocolos desenvolvidos para as

chamadas VDTNs (Vehicular DTNs).

O objetivo desse trabalho é o de desenvolver um protocolo de roteamento VDTN

que atenda os pré-requisitos das aplicações de redes veiculares que exijam um tempo de

resposta baixo. Para isso, utilizar-se-á uma única métrica: o tempo decorrido desde a

última vez em que o veículo esteve em contato com um gateway da infraestrutura, capaz

de entregar o pacote para o seu destino final, ou ser ele próprio o destino final do pacote.

Assumindo que existem nós desse tipo espalhados ao redor da rodovia, assume-se que em

nós que viajam a velocidades constantes estarão mais próximos do próximo gateway caso

haja discorrido mais tempo desde o gateway anterior. Além disso, comparar-se-á os

resultados obtidos com os do protocolo mais simples, porém de menor latência estimado

em uma VDTN, o Epidêmico, garantindo uma latência semelhante mas com o uso mais

eficiente dos recursos da rede.

1.2 – Metodologia

Para validar o roteamento tolerante a atrasos proposto, foi utilizado o simulador

NS-2 (Network Simulator - 2), que permite a simulação de redes ad hoc e a ferramenta

NAM, que permite a visualização da simulação. O algoritmo do protocolo foi

desenvolvido em OTcl (Object Tool Command Language), uma das linguagens aceitas

pelo interpretador do simulador.

O ambiente de simulação tenta retratar o tráfego de uma rodovia operando em

uma topologia de rede escolhida de forma a testar a utilidade do protocolo sob requisitos

mínimos de latência e processamento, de forma que o foco seja o funcionamento do

protocolo e não seu desempenho em cenários extremos. Ao mesmo tempo, tentou-se

aproximar o máximo possível de um cenário real. Para isso, foi utilizado dados de tráfego

da BR-290 coletados em [24].

4

Para medir a eficiência do protocolo, um segundo algoritmo foi desenvolvido para

simular o protocolo Epidêmico, um dos mais simples protocolos de roteamento DTN e

também aquele que possui conceitualmente a menor latência fim a fim. A performance

dos dois protocolos será testada em dois cenários distintos.

No primeiro, apenas quatro veículos transitarão pela rodovia bem espaçados entre

si. O objetivo é testar o protocolo em uma rede descontínua em um cenário possível, onde

a densidade de veículos é próxima daquela obtida após as 0h em [24]. Também nesse

cenário espera-se observar a tomada de decisão do protocolo, para isso o movimento dos

veículos é tal que o nó 0 terá duas opções de nós para encaminhar o seu pacote, mas

deverá escolher aquele com a melhor métrica.

Já no segundo cenário, será testado o outro caso extremo, isto é, uma rodovia com

alto tráfego em ambos os sentidos. Aqui, vinte e seis veículos irão trafegar, treze em cada

direção, de forma equidistantes e a velocidades constantes. O espaçamento dos veículos

em uma pista será tal que não haverá alcance para transmissão entre eles.

1.3 – Roteiro

Primeiramente, no capítulo 2, serão introduzidas as características básicas das

redes veiculares, os esforços de padronização iniciados na década passada e um overview

da arquitetura e das aplicações previstas na literatura. No capítulo seguinte serão

apresentadas as redes DTN com enfoque nos seus protocolos de roteamento, que estarão

divididos em protocolos para DTN e protocolos para VDTNs, integrando assim o assunto

do capítulo anterior.

O capítulo quatro trará a proposta do novo protocolo detalhadamente em seus dois

modos de operação bem como a arquitetura do sistema proposto que viria a se beneficiar

de sua utilização. A seguir, o capítulo cinco traz uma visão geral do simulador utilizado,

suas principais funções e métodos de entrada e saída de forma contextualizada com o que

foi utilizado na simulação do protocolo. Os cenários das simulações também são descritos

nesse capítulo, assim como um comparativo entre os resultados obtidos para o protocolo

desenvolvido e o protocolo epidêmico.

Por fim o capítulo seis mostra o que se pôde concluir do experimento, críticas e

benefícios do modelo escolhido e tópicos de melhorias para futuros trabalhos.

5

Capítulo 2

Redes Veiculares

A Comunicação Inter Veicular (IVC – Inter Vehicle Communication) atrai há

algum tempo a atenção de pesquisadores e da indústria automotiva. Esta, enxerga a

capacidade de prover Sistemas de Transporte Inteligentes (ITS) além de serviços de

assistência ao motorista e aos passageiros. Nesse contexto, as Redes Ad Hoc Veiculares

(VANETs) se destacam como nova classe de redes sem fio. Mais precisamente, tratam-

se de uma subclasse de rede ad hoc móvel (MANETs) resultado dos avanços nas

tecnologias de transmissão de redes sem fio, formadas espontaneamente entre veículos

em movimento equipados de interfaces wireless com tecnologias homogêneas ou

heterogêneas de rádio e podendo possuir sistemas de comunicação de curto ou médio

alcance. Como uma rede ad hoc móvel, ainda possui algumas características em comum

com outras redes deste tipo, tais quais as constantes mudanças em sua topologia

provocadas pela mobilidade dos nós, que acarretam desconexões frequentes.

Essa classe de redes pode ser considerada uma aplicação real das redes ad hoc

móveis, possibilitando a comunicação entre veículos próximos bem como entre veículos

e equipamentos fixos no entorno das vias. Mas para sua implementação, existem alguns

desafios que devem ser sobrepostos. Uma grande diferença entre uma MANET e uma

VANET é que esta, por ser composta de veículos, exibe um padrão de mobilidade

particular. Em autoestradas, por exemplo, veículos podem se deslocar a velocidades

muito altas, possivelmente em direções opostas, o que diminui a janela de tempo a qual

dois nós podem se comunicar diretamente. Outra importante diferença é que os veículos

se deslocam exclusivamente ao longo de ruas, estradas e avenidas, o que aumenta a

previsibilidade de sua trajetória. Não obstante, as redes veiculares necessitam de um grau

de escalabilidade maior devido ao elevado número de nós. Todas essas características

fazem com que protocolos criados para outras redes sem fio, como as MANETs, não

sejam adequados.

2.1 – Características Especiais

6

Redes veiculares possuem características especiais que a distinguem de outros

tipos de redes móveis. Em comparação com outras MANETs, tais redes possuem alguns

atrativos únicos, tais como:

• Fontes de energia praticamente ilimitadas: Níveis de carga de bateria não

constituem uma restrição significativa em redes veiculares como o são em

redes ad hoc clássicas ou redes de sensores, já que o veículo pode prover

energia contínua para o dispositivo de comunicação.

• Maior capacidade computacional: Veículos podem suportar sistemas

computacionais complexos, além de poderem ser equipados com diversos

sensores e demais hardware auxiliar.

• Movimento previsível: Ao contrário das redes ad hoc clássicas, onde é difícil

prever a posição futura de um nó, veículos tendem a se locomover de forma

previsível sendo limitados pelas vias de trânsito (ruas, estradas e rodovias).

Além disso, veículos são frequentemente equipados com sistemas de

posicionamento, como o GPS. Dada a velocidade média e a trajetória da via,

a posição futura do veículo pode ser facilmente calculada.

Entretanto, para tirar proveito dessas vantagens, um projeto de redes veiculares

deve sobrepor alguns desafios, tais como:

• Alta escalabilidade: Ao contrário das redes ad hoc normalmente estudadas na

literatura que assumem um número limitado de nós, uma rede veicular pode

se estender por toda uma rede rodoviária e, portanto, incluir um número

grande de nós.

• Alta mobilidade: O ambiente em que uma rede veicular opera é extremamente

dinâmico. Dependendo do ambiente ou da hora do dia podemos ter extremos

distintos de alguns fatores críticos. Em uma rodovia pouco movimentada, a

velocidade relativa entre os nós pode chegar a 300 km/h e a densidade de

veículos pode ser entre 1 e 2 por km [10], podendo ser ainda menor nos

períodos noturnos. Enquanto isso, em ambientes urbanos, as velocidades

relativas não costumam passar de 60km/h e a densidade dos nós pode ser

bastante grande, especialmente no horário do rush.

7

• Rede particionada: Redes veiculares serão frequentemente particionadas. A

natureza dinâmica do tráfego pode resultar em grandes lacunas entre os

veículos em cenários mais dispersos. Consequentemente, é comum haver

vários clusters isolados de nós.

• Topologia e conectividade: Como os veículos estão em movimento e trocando

sua posição constantemente, a topologia da rede muda frequentemente

enquanto links entre nós são criados e quebrados muito rapidamente. O grau

de conectividade de uma rede depende de alguns fatores, como o alcance dos

links sem fio, a densidade dos veículos e a quantidade de veículos

participantes, já que apenas uma fração dos veículos numa via podem estar

equipados com uma interface wireless.

2.2 – Arquiteturas

A arquitetura das redes veiculares define a forma como os nós se organizam e se

comunicam. Atualmente, existem três arquiteturas principais: ad hoc puro (também

chamada V2V – Vehicle to Vehicle), infraestruturada (V2I – Vehicle to Infrastructure) ou

híbrida (V2R – Vehicle to Road) [Alves et al. 2008]. Na arquitetura ad hoc, os veículos

comunicam-se sem qualquer suporte externo ou elemento centralizador. Para tanto, os

veículos funcionam como roteadores e encaminham tráfego através de múltiplos saltos.

Embora essa seja a configuração mais simples, por não exigir nenhum tipo de

infraestrutura, ela tem como principal desvantagem a conectividade da rede que depende

da densidade e do padrão de mobilidade dos veículos. Para evitar problemas de

conectividade, a arquitetura infraestruturada emprega nós estáticos distribuídos ao longo

das ruas ou estradas. Esses nós estáticos funcionam como pontos de acesso de redes IEEE

802.11 também em modo infraestruturado. Eles centralizam todo o tráfego da rede,

servindo como nós intermediários das comunicações. A vantagem do modo

infraestruturado e o aumento da conectividade e a possibilidade da comunicação com

outras redes, como por exemplo, a Internet. A conectividade da rede, entretanto, só é

garantida mediante um número grande de elementos fixos, o que pode elevar os custos da

rede. A arquitetura híbrida é uma solução intermediária entre a ad hoc e a infraestruturada.

Na arquitetura híbrida, uma infraestrutura mínima é utilizada para aumentar a

conectividade da rede e prover serviços como os de interconexão. Entretanto, há também

8

a possibilidade dos veículos se comunicarem por múltiplos saltos. Nas redes veiculares,

o modo ad hoc equivale à arquitetura V2V e o modo infraestruturado à V2I. Atualmente

alguns pesquisadores referem-se às redes veiculares em geral como VANETs, mesmo

quando existe infraestrutura. A figura abaixo apresenta as diversas arquiteturas das redes

veiculares.

Figura 2.1 – Cenários de uma rede veicular Fonte: [1]

2.3 – Padronização

Como dito no início desse capítulo, o campo das redes veiculares tem chamado a

atenção da comunidade científica assim como a da indústria automotiva, mas não são os

únicos. Autoridades governamentais e instituições de padronização também já mostraram

notado interesse nessa área. No ano de 1999, a FCC (Federal Communications

Commission) alocou 75 MHz do espectro DSRC (Dedicated Short Range

Communications) na faixa de 5,9 GHz (5,850 – 5,925 GHz), para o uso exclusivo de

comunicação V2V e V2I. A faixa DSRC é livre, porém licenciada, isto é, é restrita em

termos de aplicações e tecnologias utilizadas. O espectro DSRC é dividido em sete canais

de 10 MHZ como pode ser observado na figura abaixo:

9

Figura 2.2 - Alocação de espectro para aplicações DSRC Fonte: [1]

O canal 178 (5885-5895 MHz) é o canal de controle, geralmente restrito ao uso

em comunicações de segurança apenas. Os dois canais das bordas do espectro (172 e 184)

são reservados respectivamente para futuras aplicações de emergência e preservação da

vida e para alta potência segurança pública. Os demais (174, 176, 180 e 182) são canais

de serviço disponíveis tanto para aplicações de segurança como para outras aplicações.

Em comparação com a faixa de frequência utilizada nos rádios por espalhamento

espectral, localizada entre 902 – 908 MHZ, isto é, a faixa ISM, a DSRC proporciona uma

taxa de dados e alcance bem superiores, como pode ser observado na tabela abaixo:

Tabela 2.1 – Comparação entre DSRC e ISM

Fonte: [10]

Parâmetros ISM (902 - 928 MHz) DSRC (5850 - 5925

MHz)

Espectro 12 MHz 10 MHz

Taxa de dados 500 Kbps 6 - 27 MHz

Proteção Nenhuma Primária

Interferência Telefone 900 MHz; radar

Espalhamento espectral de rádio

Alguns radares; satélites

Alcance máximo 91,44 m 1000 m

Capacidade do canal 1 - 2 7

Potência (downlink) < 10 watts < 2 watts

Potência (uplink) < 4 mW < 2 watts

No Japão, o espectro alocado para aplicações DSRC varia de 5,770 a 5,850 GHZ.

Já na Europa, o espectro destinado à aplicações de ITS é o de 5,855 a 5,925 GHz.

IEEE

Inicialmente o esforço para a padronização da tecnologia de rádio DSRC nos EUA

foi liderado pela American Society for Testing and Materials através do grupo de trabalho

10

ASTM 2213 [9], que tinha como objetivo o desenvolvimento de aplicações de segurança

e melhoria do trânsito, como o pagamento automático de pedágios. O trabalho desse

grupo serviu como base para a regulamentação do uso do espectro DSRC pela FCC.

Em 2004 porém, o esforço de padronização foi migrado para o grupo de trabalho

802.11 do IEEE, já que a tecnologia de rádio DSRC foi baseada no padrão IEEE 802.11a

ajustado para operações de baixo overhead no espectro de 5,9GHz. Uma implicação de

se mover o padronização para o escopo do IEEE é a internacionalização do padrão, que

não fica mais restrito ao mercado norte-americano.

Figura 2.3 – Pilha de protocolos WAVE Fonte: [1]

No IEEE, o padrão ganhou o nome de WAVE (Wireless Access in the Vehicular

Environment). Sua arquitetura é definida em seis documentos: IEEE P1609.1, IEEE

P1609.2, IEEE P1609.3, IEEE P1609.4, IEEE 802.11 e IEEE 802.11p. O padrão IEEE

802.11p define as camadas físicas e de controle de acesso ao meio (MAC) para redes

veiculares e é baseado no padrão de redes locais IEEE 802.11a. Já a pilha de protocolos

entre a camada de rede e a camada de aplicação é descrita nos padrões IEE 1609. Portanto,

o IEEE 1609 nada mais é do que uma família de padrões para as camadas superiores as

quais o IEEE 802.11p é baseado.

Tal família consiste de quatro padrões:

• IEEE 1609.1 – WAVE Resource Manager, define a plataforma de aplicação

básica e inclui protocolos de leitura/escrita de dados de aplicação entre

elementos de rede.

11

• IEEE 1609.2 – WAVE Security Services, define a segurança, anonimato,

autenticidade e confidencialidade do DSRC.

• IEEE 1609.3 – WAVE Networking Services, especifica os serviços das

camadas de rede e transporte, incluindo o endereçamento e o roteamento.

Além disso, o padrão 1609.3 define a MIB (Management Information Base)

para a pilha WAVE.

• IEEE 1609.4 – WAVE Multichannels Operation, se posiciona logo acima do

802.11p e habilita a operação das camadas superiores através de múltiplos

canais sem conhecimento prévio dos parâmetros da camada física.

C2C-CC

Uma das principais forças motoras para a comunicação interveicular baseada em

tecnologia sem fio na Europa é a C2C-CC, um consórcio de fabricantes de automóveis,

fornecedores e institutos de pesquisa. O C2C-CC assimila inovações de vários projetos

de P&D europeus, cria sistemas e especificações de protocolos e provê um framework

para protótipos de sistemas [10]. Em 2007 foi publicado o seu “manifesto” descrevendo

os principais conceitos do sistema, cobrindo arquitetura de protocolos e sistemas, cenários

de uso e protocolos de comunicação. Um conceito central da abordagem de rede do C2C-

CC é a base em redes ad hoc de múltiplos saltos que utilizam endereçamento e roteamento

geográficos, isto é, com base na posição geográfica dos nós. O consórcio visa permitir a

interoperabilidade entre carros de diferentes fabricantes e fornecedores de dispositivos de

redes e diz se preocupar com demonstrações de aplicações reais de segurança para redes

ad hoc tangíveis.

A arquitetura descrita no manifesto prevê 3 domínios distintos:

• Domínio intraveicular: Rede logicamente composta por uma On-board Units

(OBU) e Application Units (AUs). Uma AU é um dispositivo que executa uma

ou mais aplicações e utiliza a capacidade de comunicação da OBU. Uma AU

pode ser uma parte integrada da OBU ou um dispositivo portátil, como um

laptop.

• Domínio ad hoc (ou VANET): Composta de veículos equipados de OBUs e

road-side units (RSUs). OBUs formam uma MANET que permite a

comunicação entre nós de maneira distribuída sem a necessidade de uma

12

instância central de coordenação. Se não houver comunicação direta entre

duas OBUs, protocolos dedicados de roteamento permitem a comunicação em

múltiplos saltos até que o pacote chegue a seu destino. A principal função de

uma RSU está em aplicações de segurança, executando aplicações especiais e

extender a área de cobertura de uma rede ad hoc ao receber e encaminhar

pacotes.

• Domínio de infraestrutura: Trata-se dos elementos fixos que provêm serviços

para as OBUs. Podem ser formadas por RSUs ou Hot Spots Particulares (HS)

e toda infraestrutura por trás que as ligam ao serviço prestado, como a internet.

As OBUs ainda podem utilizar as redes celulares (GSM, GPRS, HSDPA,

WiMax, LTE) para prover acesso à internet.

Figura 2.4 - Modelo de referência Fonte: C2C-CC Manifesto

13

Figura 2.5 - Arquitetura C2C-CC Fonte: C2C-CC Manifesto

ETSI

O Instituto Europeu de Padrões de Telecomunicações (ETSI - European

Telecommunications Standards Institute) possui o comitê técnico TC ITS que visa

desenvolver padrões e especificações para serviços de ITS. O TC ITS está organizado em

cinco grupos de trabalho: WG1 – Requerimentos de usuário e aplicação; WG2 –

Arquitetura e questões de “Cross-Layer” (interação entre protocolos de camadas

diferentes); WG3 – Rede e Transporte; WG4 – Meio e questões relacionadas; e WG5 –

Segurança.

Para permitir o uso de diferentes meios de acesso, a especificação distingue entre

funções de rede dependentes e independentes do meio. As especificações são apoiadas

por outros grupos de trabalho, que especificamente se preocupam com questões de meio

de acesso e segurança. Trabalhos relacionados a ITS dentro da ETSI são liderados pela

ETSI ERM TG37 (Assuntos de compatibilidade eletromagnética e espectros de rádio),

que trabalha em cooperação com outros comitês ETSI e de outras organizações de

padronização (SDOs), notadamente o ISSO TC204. ERM TG37 contribui para o processo

14

de desenvolvimento de padrões do ISSO TC204 e desenvolverá padrões complementares

se apropriado.

ISO

O globalizado ISSO TC204/WG16 produziu uma série de rascunhos de padrões

conhecidos como CALM (Continuous Air-interface, Long and Medium Range). O

objetivo do CALM é desenvolver uma rede padronizada capaz de conectar veículos e

sistemas de acostamento continuamente. Para alcançar esse objetivo, o padrão sugere o

uso de uma larga variedade de mídias de comunicação como a telefonia móvel, WLANs,

DSRC e infravermelho (IR). A arquitetura CALM provê o acesso universal através de um

número de mídias complementares e os interliga através de protocolos de internet

modernos, camadas de adaptação e entidades de manutenção. A arquitetura separa o

provimento de serviços do meio através de uma camada de rede em IPV6, com handover

entre meios de acesso e suporte a serviços utilizando 2G, 3G, LTE, 5GHz, 60GHz, Mobile

Wireless Broadband (802.16e - WiMax, 802.20 e HC-SDMA). O sistema será capaz de

incluir outras tecnologias de acesso conforme suas evoluções através do uso de protocolos

de acesso comuns e redes IPV6.

O conceito do CALM, que a ETSI está ajudando a desenvolver, está no cerne de

várias pesquisas europeias de frameworks IPV6 como a SAFESPOT [10] e CVIS (que já

teve seu draft final aprovado), que testam soluções com CALM. Nos estados unidos a

iniciativa VII operará utilizando os padrões IEEE 802.11p/1609 a 5,9GHz, que serão

compatíveis com os padrões CALM 5,9GHZ, apesar do padrão IEEE não possuir

handover entre mídias diferentes.

15

Figura 2.6 - Arquitetura CALM Fonte: ITU-T Technology Watch Briefing Reports: Continuous Air-interface, Long and Medium

Range (CALM)

2.4 – Aplicações

As aplicações de redes veiculares podem ser divididas em três classes: segurança

no trânsito, entretenimento e assistência ao motorista. As aplicações de segurança

possuem caráter preventivo e emergencial, onde o principal desafio é divulgar

rapidamente as informações para que o condutor tenha tempo para reagir. A classe das

aplicações de entretenimento inclui adaptações de aplicações da Internet para redes

veiculares. Por fim, as aplicações de assistência ao motorista envolvem o recebimento de

informações que auxiliem o condutor em buscas ou automatizem serviços. A seguir, são

apresentadas as principais aplicações e projetos relacionados a redes veiculares.

16

2.4.1 – Segurança no Trânsito

A promessa de aumento de segurança no trânsito tem sido um dos principais

incentivos ao desenvolvimento das redes veiculares. Em geral, as aplicações de segurança

têm por objetivo reduzir o número e a gravidade dos acidentes através da troca de

informações entre os veículos. Essas informações podem ser apresentadas ao motorista

ou utilizadas para acionar um sistema ativo de segurança. Essas aplicações impõem

requisitos estritos de latência e confiabilidade para as mensagens, exigindo características

diferenciadas dos protocolos de camadas inferiores. Além disso, as aplicações precisam

ser robustas à inserção de mensagens falsas e lidar com informações conflitantes.

Muitos acidentes de trânsito podem envolver veículos parados, lentos ou

desgovernados. Uma maneira de evitar esses acidentes é através do emprego de

mensagens periódicas que indiquem a posição, a velocidade e a direção dos veículos.

Outra abordagem é a utilização de mensagens assíncronas disparadas somente quando um

mecanismo de emergência é acionado. O CCA (Cooperative Collision Avoidance) [11] é

um exemplo de aplicação nessa categoria que tem por objetivo evitar colisões utilizando

uma abordagem cooperativa. O CCA envia mensagens em múltiplos saltos avisando aos

motoristas da ocorrência de uma situação de emergência. Essa abordagem também pode

ser utilizada em situações em que o motorista não possui visão completa. Por exemplo, o

motorista pode ter ciência de veículos a sua frente através de sondas em situações de

neblina ou de chuvas intensas.

Existem ainda aplicações onde a troca de informações entre veículos permite a

realização segura de manobras no trânsito, prevenindo acidentes. Por exemplo, em

situações em que os veículos precisam realizar uma mudança de faixa, mensagens podem

ser trocadas para evitar colisões laterais [1].

Além das comunicações entre veículos, as comunicações com a infraestrutura

podem reduzir o número de colisões em cruzamentos. Através de sondas periódicas, os

veículos podem avisar RSUs instaladas em cruzamentos sobre sua posição e velocidade.

Com esses dados, a RSU pode calcular uma possível colisão e alertar os envolvidos sobre

o risco iminente. Outra abordagem é o envio de sondas pelas RSUs informando o estado

de sinais, avisando motoristas desatentos sobre a possível violação da sinalização.

Tipicamente, avisos são colocados em locais com curvas acentuadas para que o motorista

reduza a velocidade.

17

2.4.2 – Entretenimento

Informações sobre restaurantes locais, hotéis, postos de gasolina e demais pontos

de interesse podem ser carregadas no veículo por uma RSUs e compartilhadas com os

demais veículos em uma arquitetura ad hoc. O mesmo pode ser feito com arquivos

multimídia (música, filmes, notícias, e-books etc). Um anúncio pode ser transmitido da

mesma maneira, e sua exibição ainda pode ser condicionada às informações coletadas do

veículo. Por exemplo postos de gasolina podem ser sugeridos a veículos com pouco

combustível, oficinas mecânicas a veículos com problemas diagnosticados

eletronicamente. A maioria das aplicações de entretenimento propostas para redes

veiculares, no entanto, está associada à onipresença de acesso à Internet. Por isso, é

necessário adaptar as aplicações mais usadas na Internet de acordo com as características

das redes veiculares.

Muitas aplicações para redes veiculares defendem o uso da arquitetura ad hoc por

dispensar elementos centralizadores e por possibilitar a comunicação entre veículos sem

o intermédio de pontos de acesso. Além disso, no caso infraestruturado, manter a rede

totalmente conectada requer um alto custo de instalação e manutenção. A partir desses

argumentos, muitas aplicações de entretenimento preferem utilizar os sistemas par-a-par

ao modelo cliente-servidor, que é centralizado. A questão é que frequentemente essas

aplicações necessitam de acesso à Internet, que só é possível através de pontos fixos de

interconexão ligados a uma infraestrutura cabeada. Esses pontos fixos, que podem ser

RSUs, são nós especiais que também pertencem à rede veicular e são chamados de

gateways.

2.4.3 – Assistência ao Motorista

A principal finalidade das aplicações de assistência ao motorista é auxiliar a

condução do veículo a partir da disponibilização de informações úteis. Essas informações

são adquiridas a partir de serviços que podem ser oferecidos ao condutor em momentos

oportunos ou podem ser de fácil acesso através de procedimentos de busca. Dentre alguns

exemplos pode-se citar: aviso de estacionamentos, disseminação de informações de vias,

controle de tráfego, auxílio a cruzamentos, condução conjunta de veículos, localização

em mapas, aumento da visibilidade e veículos sem condutor humano.

18

Dentre as aplicações desta classe, as aplicações de indicação de vagas de

estacionamento vêm recebendo bastante atenção. Um dos argumentos utilizados é que

além de conveniente, ela pode reduzir os problemas de congestionamento nas cidades.

Um trabalho realizado em uma cidade no distrito de Munique, Alemanha revela que 44%

de todo o tráfego de veículos é devido à busca de lugares para estacionar. Isso pode gerar

prejuízos anuais da ordem de milhões de Euros e ainda provocar muitas horas perdidas

no trânsito [1]. Em [12], os autores desenvolveram uma solução para controle e

divulgação de vagas de estacionamento. Essa solução divide uma área onde há vagas de

estacionamento em pequenas zonas, de forma que cada zona seja gerenciada por uma

Unidade de Acostamento (RSU). Cada RSU controla a posição e o estado das vagas na

zona em que se encontra e, quando um veículo se aproxima dela, ela informa sua posição,

obtida através de um receptor GPS, e verifica para onde o motorista pretende ir. Assim, a

RSU verifica se existe alguma vaga livre próxima ao destino pretendido e, caso exista,

informa ao motorista. Quando um veículo se encaminha para alguma vaga, ele verifica a

presença de outros veículos ocupando outras vagas utilizando sensores ao redor do

veículo. As informações coletadas sobre o estado das vagas próximas são enviadas à RSU.

Quando um veículo sai de uma vaga, ele informa à RSU a liberação.

Outra aplicação importante de auxílio ao motorista é a disseminação de

informações sobre as condições das vias. Essas aplicações buscam reduzir o tempo de

espera dos motoristas em congestionamentos, apresentando rotas alternativas que evitam

áreas com tráfego lento. Essas aplicações possuem ainda o efeito indireto de redução da

poluição ambiental e podem ser utilizadas para evitar áreas de risco.

Em [13] os autores propõem uma aplicação que utiliza redes veiculares para

informar aos motoristas a aproximação de veículos de emergência (Emergency Service

Vehicles - ESVs), facilitando a passagem deles até seus destinos. Cada ESV envia

periodicamente mensagens em difusão contendo o identificador do veículo, o tipo de ESV

(carro de polícia, ambulância etc.), seus pontos de origem e de destino, a identificação da

rota (lista das vias pertencentes àquela rota), a velocidade ideal para alcançar o destino,

sua posição atual e a estampilha de tempo de envio da mensagem pelo ESV. Dessa forma,

os veículos recebem informações completas sobre o ESV que está se aproximando,

auxiliando aos motoristas a tomarem a melhor decisão com antecedência.

As aplicações de condução conjunta de veículos (vehicle platooning) são

utilizadas para os veículos que viajam juntos, reduzindo o espaço entre eles. Por reduzir

o espaço entre os veículos, o conjunto de veículos permite uma viagem mais segura e com

19

menores chances de ocorrências de congestionamentos. Essas aplicações realizam a troca

de informações de posição e velocidade dos veículos do conjunto, permitindo um controle

rápido e preciso da distância entre os veículos.

2.5 – Contextualização

Este trabalho está fundamentado em um cenário de redes veiculares. Os elementos

de redes envolvidos são veículos em movimento e unidades estacionárias distribuídas ao

longo do acostamento de uma rodovia, o que o enquadra como de arquitetura híbrida. Nas

sessões anteriores desse capítulo tentou-se mostrar as diferenças que esse cenário

proporciona na montagem da arquitetura dessa rede, suas características peculiares e

principalmente os entraves a serem sobrepujados. Dentre estes, destacam-se as

desconexões e a segmentação da rede, que justificam o uso de redes tolerantes a atrasos,

tema do capítulo seguinte.

A fim de contextualizar o leitor, os três tipos de aplicações foram citadas. No

entanto, o trabalho foca-se em uma arquitetura voltada para facilitar aplicações de

segurança e diminuir seu tempo de resposta. O implemento de outras aplicações no

cenário não é suportado e não foi descartado. O desenvolvimento do modo de operação

ganancioso possibilita que o veículo obtenha dados de uma rede externa, possibilitando

que aplicações de entretenimento e assistência ao motorista sejam utilizadas.

O padrão de rede mais conhecido e difundido é aquele do IEEE. Como houve a

preocupação de apresentar uma solução de baixo custo que utiliza itens amplamente

disponíveis no mercado, o uso do padrão IEEE é adequado a esse trabalho. As camadas

física e de acesso ao meio devem ser regidas pelo padrão IEEE 802.11p. No simulador,

utilizaremos o IEEE 802.11a que é o mais próximo suportado. Já os padrões de camadas

superiores não serão utilizados e o novo protocolo será desenvolvido para a camada de

rede.

20

Capítulo 3

DTN e Redes Oportunísticas

3.1 – Fundamentos e Características

Os protocolos de roteamento existentes partem do pressuposto que existe uma

conexão fim a fim da origem ao destino, possivelmente via múltiplos intermediários. Esse

pressuposto nem sempre é verdadeiro devido à falta de confiabilidade (redes com alta

latência ou elevadas taxas de erro) ou, o que é mais importante para esse trabalho, à

conectividade intermitente entre os nós. Um exemplo desse último caso dá-se quando um

nó sem fio está fora do alcance do resto da rede.

Figura 3.1 - Desafios para redes fim-a-fim Fonte: [3]

Redes Tolerantes à Atrasos (DTN – Delay Tolerant Networks) tentam estender o

alcance das redes comuns e prometem habilitar a comunicação entre redes que antes

21

apresentavam um grande desafio, como redes interplanetárias, MANETs (Mobile Ad-Hoc

Networks) e redes de baixo custo, onde não há uma infraestrutura fixa.

DTNs veiculares têm o potencial de interconectar veículos em regiões remotas

(ou rurais) a baixo custo onde as tecnologias de redes atuais não possuem cobertura. A

principal dificuldade dessas redes é que uma conexão fim-a-fim pode nunca ser

alcançada. Para tornar a comunicação fim-a-fim possível, nós retransmissores se utilizam

da mobilidade para armazenar os dados a serem transmitidos e encaminhá-los assim que

a oportunidade surgir. Para isso, a arquitetura DTN implementa um paradigma de

“armazenar e encaminhar” onde mensagens inteiras ou fragmentadas são movidas de um

local de armazenamento (buffer) de um nó até serem transmitidas ao nó seguinte onde

são então armazenadas novamente e retransmitidas ao longo do caminho até

eventualmente chegarem ao seu destino.

No exemplo de redes interplanetárias, os dispositivos de comunicação estão em

movimento e os links podem ser obstruídos periodicamente por corpos celestes. Além

disso, a latência advinda das grandes distâncias (dezenas de minutos dentro do nosso

sistema solar) são significantes. Se nós com potencial de comunicação se moverem

através de caminhos previsíveis eles podem conhecer sua posição futura e receber

atualização da posição futura de seus potenciais vizinhos e com essas informações

agendar as sessões de comunicação entre si, com isso o nó pode encerrar qualquer link e

economizar energia até o horário agendado. Nesse caso, diz-se que o contato é agendado.

Já quando uma comunicação é feita sem agendamento, dizemos que se trata de um contato

oportunístico.

A arquitetura prevê ainda a adição de uma nova camada de protocolo ao modelo

TCP/IP chamada de camada de agregação, cujo objetivo é prover interoperabilidade entre

redes heterogêneas que atuam em diferentes meios de transmissão. Na borda de cada rede

remota há um sistema com um gateway na camada de aplicação que termina aplicações e

produz bundles de dados.

22

Figura 3.2 - Bundle Layer Fonte: [3]

Em DTN, um nó é uma entidade que possui uma camada bundle [3] e pode ser

classificado em três tipos. Um Host envia e/ou recebe bundles, mas não os encaminha.

Um router encaminha bundles dentro de uma região DTN e pode opcionalmente ser um

host. Já um Gateway encaminha bundles entre duas ou mais regiões DTN e pode

opcionalmente ser um host. Um gateway provê conversão entre os protocolos de camada

mais baixa das regiões para as quais serve de fronteira.

Figura 3.3 - Nós DTN Fonte: [3]

Vale notar que nas premissas da DTN, com grande atraso ou intermitência em

seus links, protocolos como o TCP que garantem confiabilidade por diversas trocas de

mensagens fim-a-fim de envio e confirmação de dados recebidos podem se tornar

impraticáveis. Por essa razão, as camadas bundle comunicam-se entre si de forma simples

23

com mínima ou nenhuma confirmação de recebimento. Entretanto, os protocolos de

camada inferior, como o TCP, ainda podem manter sua função de confiabilidade e

retransmissão de dados não recebidos. Para isso, roteadores e gateways DTN agem como

substitutos para comunicações fim-a-fim, terminando a camada de transporte em suas

camadas bundle.

Redes DTN são também chamadas de redes oportunísticas. Como não há uma

terminologia definida ou uma separação clara entre os dois conceitos, ambos os termos

são usados de forma intercambiável. Segundo [14] porém, redes oportunísticas

correspondem a um conceito mais amplo que incluem DTNs. Enquanto DTNs assumem

que a topologia de rede é conhecida, nas redes oportunísticas tal conhecimento prévio não

é mandatório. Além disso, rotas em DTN são tipicamente calculadas por técnicas legadas

da internet, que consideram a indisponibilidade como apenas mais um componente do

custo do link. Enquanto isso nas redes oportunísticas as rotas são computadas a cada salto

em que o pacote é encaminhado, ou seja, diferentemente de redes DTN, em redes

oportunísticas cada nó age como um gateway.

A arquitetura das redes oportunísticas também foi expandida para redes de

trânsito, chamadas Vehicular DTN (VDTN). Nessas redes, veículos (carros, ônibus,

barcos, etc.) são utilizados como retransmissores que se movimentam ao longo da rede

coletando mensagens dos nós de origem. Diversos projetos foram baseados nesse

conceito geral. A seguir, serão apresentados alguns protocolos de roteamento em redes

oportunísticas.

3.2 – Roteamento em DTN

Como dito anteriormente, as redes DTN ganharam forma com o intuito de

conectar redes que apresentam um desafio para as estruturas convencionais de redes. Tais

desafios incluem os problemas de atrasos extremamente longos e as frequentes

desconexões. Outro desafio é que para algumas redes determinados enlaces podem existir

durante apenas alguns intervalos de tempo de forma que a topologia da rede varia ao

longo do tempo. Nesses casos, é possível que dois nós específicos nunca estejam

conectados e, consequentemente, nunca haja um caminho fim-a-fim entre ambos.

24

Tais dificuldades fazem com que o desenho de uma estratégia eficiente de

roteamento seja uma tarefa complicada. De um modo geral, a performance do roteamento

incrementa quanto mais informações sobre a topologia são conhecidas, conforme

explicado em [15]. Infelizmente, esse conhecimento não é facilmente obtido e uma troca

deve ser feita entre performance e falta de conhecimento. Por esta razão, diversos

trabalhos classificam as propostas para roteamento em redes oportunísticas/DTN de

acordo com seu conhecimento da topologia. Neste trabalho, entretanto, a única

diferenciação será quanto à finalidade (VDTN ou não).

3.2.1 – Roteamento DTN Convencional

Epidêmico

Neste protocolo as mensagens são difundidas na rede de modo semelhante a

doenças ou vírus. Um nó é infectado por uma mensagem quando ele gera ou recebe a

mensagem de outro nó, armazenando-a em um buffer local para que possa ser

encaminhada adiante. Um nó é suscetível à infecção enquanto ainda não tiver recebido a

mensagem. Ele se torna infectado quando estabelece contato com um nó infectado e

recebe mensagens deste. Por sua vez, um nó infectado é recuperado (curado da doença)

uma vez que tenha entregado a mensagem ao nó de destino. Como resultado, ele também

se torna imune à mesma infecção e não mais encaminhará aquela mensagem.

Figura 3.4 – Troca de mensagens no roteamento Epidêmico Fonte: [2]

25

O protocolo utiliza-se da distribuição transitiva de mensagens através de redes ad

hoc, com mensagens eventualmente atingindo o seu destino. Cada host mantém um buffer

com as mensagens originadas por ele mesmo ou carregadas por ele em favor de outro nó.

Uma tabela hash indexa a lista de mensagens e um vetor de bits chamado “vetor de

sumarização” e armazenado em cada host para indicar quais entradas na tabela hash estão

ativas. Quando dois hosts estão ao alcance um do outro para que a comunicação seja

estabelecida, o host com o menor identificador inicia uma sessão de anti-entropia [2] com

o host de maior identificador. Para evitar conexões redundantes, cada host mantém um

cache dos hosts com os quais ele falou recentemente. A anti-entropia não será reiniciada

com hosts que foram contatados dentro de um período configurável.

Segundo a literatura, uma sessão de anti-entropia consiste na comparação de todas

as réplicas de cada pedaço de dado que existe e atualizar cada réplica com a versão mais

recente. Durante uma sessão de anti-entropia do roteamento epidêmico, dois hosts trocam

seus vetores de sumarização para determinar quais mensagens armazenadas remotamente

ainda não foram vistas pelo host local. A seguir, cada host requer copias das mensagens

que ele ainda não viu.

Figura 3.5 – Sessão anti-entropia Fonte: [2]

A figura 5 retrata a troca de mensagens no protocolo. O host� entra em contato

com o host� e inicia uma sessão de anti-entropia. No passo 1,� transmite seu vetor de

sumarização,��� para�. A seguir,� executa uma operação lógica AND entre o seu vetor

de sumarização invertido,¬��� (representando as mensagens que ele ainda não possui)

e���. Isso é,� determina a diferença entre as mensagens armazenadas em� e as

mensagens armazenadas em si próprio. No passo 3,� transmite as mensagens

26

requisitadas para�. Esse processo é repetido transitivamente quando� entra em contato

com um novo vizinho.

Dado o devido tempo e espaço em buffer, essas sessões de anti-entropia garantem

eventual entrega da mensagem a seu destino, como garantido pela teoria dos algoritmos

epidêmicos, a qual o protocolo se utiliza de uma variante. Entretanto, para evitar que a

epidemia fuja do controle e as mensagens sejam encaminhadas indefinidamente através

dos nós consumindo recurso de buffer, o protocolo implementa um campo de contagem

de saltos que age de forma similar ao campo TTL nos pacotes IP. Mensagens com um

TTL de 1, apenas podem ser encaminhadas ao destino.

Mesmo com essa medida, o maior problema deste protocolo é a alta quantidade

de cópias de mensagens na rede e o espaço de armazenamento ocupado nos nós, levando

a uma baixa escalabilidade. Quando muitas mensagens são replicadas, um dado nó pode

não ter espaço de armazenamento suficiente. Quando isto ocorre frequentemente, a

probabilidade de entrega das mensagens pode se tornar menor, e consequentemente

aumentar o atraso de entrega da informação.

PROPHET

O Probabilistic Routing Protocol using History of Encounters and Transitivity

(PROPHET) foi proposto para mitigar o problema da baixa escalabilidade e alta utilização

de recursos do roteamento epidêmico [16]. Apesar de ainda se utilizar de um mecanismo

de flood, este é controlado por intermédio de uma nova métrica chamada “previsibilidade

de entrega”,(�, ) ∈ [0, 1], em cada nó � para cada destino �. Essa informação

corresponde à probabilidade de cada nó� entregar a mensagem para o nó�.

O valor de(�, ) aumenta sempre que� e� se encontram. Se� e� deixam de se

encontrar frequentemente,(�, ) decai com o tempo a proporção das constantes�,� ∈

[0,1] (constante de envelhecimento) e�� (número de unidades de tempo discorridos

desde a última vez que a métrica foi atualizada):

(�, ) =(�, )��� × ���

A probabilidade de entrega também possui uma propriedade transitiva que se

baseia na seguinte observação: se um nó� encontra um nó� frequentemente e um nó�

encontra frequentemente um nó , logo o nó provavelmente é um bom nó para se

27

encaminhar mensagens destinadas à�. Uma constante! (! ∈ [0,1]) é utilizada para

definir o impacto da transitividade na entrega:

(�,") =(�,")��� + (1 − (�,")���) × (�, ) × ( ,") × !

De forma similar ao roteamento epidêmico, quando dois nós iniciam um contato

eles trocam os vetores de sumarização, que nesse caso também contém a informação da

previsibilidade de entrega. Quando um nó recebe o vetor de sumarização de um vizinho,

ele calcula a probabilidade de entrega para cada uma das mensagens que ainda não possui

armazenada. Em seguida, para cada mensagem, o nó compara a probabilidade indicada

na sua lista com a probabilidade indicada na lista recebida do vizinho. Essa comparação

é realizada para verificar qual dos dois nós possui a maior probabilidade de entrega. Feito

isso, devem ser realizados três procedimentos. Primeiro, o nó deve enviar um pedido das

mensagens não armazenadas que possuem uma maior probabilidade de serem entregues

através dele. Segundo, recebe o pedido de mensagens do vizinho e as envia. Terceiro,

apaga do buffer todas as mensagens cujas probabilidades de entrega sejam maiores

quando a entrega é realizada através dele.

Há entretanto uma escolha que deve ser feita com relação ao encaminhamento de

pacotes. O protocolo permite que um limite mínimo de probabilidade de entrega seja

exigido para se encaminhar mensagens a um nó. Quanto menor o limite, mais nós

encaminharão a mensagem e maior será a probabilidade da mensagem ser entregue a seu

destino, porém mais recursos do sistema serão gastos. Por outro lado, um limite maior

fará com que a mensagem seja entregue a poucos nós, utilizará poucos recursos, mas a

probabilidade de entrega será reduzida e o delay será aumentado. No artigo, a estratégia

de encaminhamento sugerida é a de entregar uma mensagem sempre que um nó possuir

uma probabilidade de entrega maior que a daquele que carrega a mensagem.

Um algoritmo similar é utilizado no projeto ZebraNet [17], onde colares são

colocados em zebras para coletar periodicamente sua posição via GPS. As informações

de posicionamento são armazenadas em uma memória flash no colar para que sejam

enviadas a uma estação-base móvel. A disponibilidade da estação-base móvel é

esporádica, já que trata-se de um carro conduzido por pesquisadores que coletam as

informações enquanto o veículo está em movimento na região. Como nem todos os

colares se comunicarão com a estação-base móvel, os colares também trocam dados entre

si. Para isso, ela se utiliza de um protocolo baseado em histórico. Esse protocolo é similar

ao PROPHET, mas a métrica adotada aqui chama-se hierarquia. Inicialmente todos os

28

nós possuem a mesma hierarquia, entretanto, quanto mais tempo um nó ficar fora do

alcance da estação-base móvel, seu nível de hierarquia diminui. A escolha do nó para o

qual o pacote deve ser roteado é feita de forma semelhante à do PROPHET, onde a maior

hierarquia é preferível.

Spray and Wait

Os protocolos baseados em utilidade (como a previsibilidade do PROPHET)

trouxeram uma abordagem para reduzir o overhead que o flood de mensagens do

roteamento epidêmico gera e melhorar sua performance que consiste basicamente em

encaminhar uma cópia com uma probabilidade% < 1 baseada na utilidade de cada nó na

rede para o nó de destino. Apesar dessa abordagem apresentar uma performance melhor

e possuir melhores decisões de encaminhamento do que o roteamento epidêmico [16],

esses protocolos ainda são baseados em flood. Além disso, ainda há o dilema de se

escolher um limite para a utilidade. Um limite muito baixo e o protocolo se comportará

como epidêmico (puramente flood), muito alto e a latência aumentará significativamente

e a probabilidade de mensagem alcançar seu destino diminuirá.

O protocolo Spray and Wait se propõe a reduzir significativamente o overhead de

transmissão dos esquemas baseados em flooding e apresenta performance melhor no que

diz respeito ao atraso de entrega na maioria dos cenários além de não utilizar qualquer

informação da rede [18]. Para isso, o protocolo dissemina um número de cópias pré-

fixado da mesma mensagem para outros nós na rede e aguarda até que uma dessas cópias

atinja o destino.

O Spray and Wait consiste de duas fases. Na primeira (fase Spray), para cada

mensagem originada em um nó,' cópias são geradas e então espalhadas para outros nós

para serem entregues ao nó de destino. Um nó é considerado ativo quando possui( > 1

cópias da mensagem em seu buffer e, portanto, ainda está na fase de Spray. Quando um

nó ativo� encontra outro nó�, � entrega para � *(() cópias da mensagem e retém para

si as outras( − *(() cópias. * é a função que define o processo de espalhamento.

Quando as cópias são pulverizadas através dos nós de modo que um único nó mantém

apenas uma única cópia da mensagem, o algoritmo entra em sua segunda fase, Wait.

29

Nessa fase, cada um dos' nós com uma única cópia só pode encaminhar a mensagem

para o seu destino final.

Figura 3.6 – Exemplo de funcionamento do protocolo Spray-and-Wait com ' = 4 Fonte: [16]

Na figura, temos o caso específico chamado Spray and Wait Binário, que é dito

ótimo (menor latência possível) quando os nós se movimentam de forma independente e

identicamente distribuída (IID). Nesse caso,*(() = (2- , isto é, em ./ o nó de origem

cria ' = 4 cópias da mensagem que deseja encaminhar. Em.0, o nó de origem encontra

o nó 1 e encaminha 1

0 cópias ao nó 1, permanecendo com as outras

1

0 cópias. Em.2, o nó

1 encontra o nó 3 e o nó de origem encontra o nó 2, enviando 1

0 cópias a cada novo nó.

A partir daqui, já não há mais nós ativos e o protocolo entra no estado de Wait. Finalmente

em.3, o nó 3 encontra o destino e encaminha a mensagem.

Contex-aware Routing (CAR)

Até aqui foram citados exemplos de protocolos que utilizavam técnicas de

disseminação (flood) de mensagens combinadas ou não à técnicas probabilísticas para

entrega de mensagens à retransmissores com maiores chances de encontrar o destino.

Esses e outros algoritmos que visam diminuir o número de cópias de mensagens como o

30

Spray and Wait tratam-se na verdade de algoritmos semi-epidêmicos, já que mantém a

idéia original da teoria dos algoritmos epidêmicos [2], que é o uso de diversas réplicas

para garantir que a mensagem seja entregue. Os algoritmos baseados em contexto visam

diminuir drasticamente o número de réplicas da mensagem utilizando parâmetros de

contexto de cada nó para identificar o melhor próximo salto para determinada mensagem.

No protocolo CAR, probabilidades de entrega são calculadas localmente

derivadas de informações de contexto. O contexto é formado por um conjunto de atributos

do sistema que podem ser utilizados para conduzir o processo de entrega de mensagens

[19]. Exemplos de informações de contexto incluem a carga restante de bateria, a taxa de

conectividade com um nó (número de conexões e desconexões que o host experimentou

com outro nó nos últimos4 segundos), a probabilidade do host estar ao alcance do

destino, o grau de mobilidade do host, etc. A posição geográfica do nó, no entanto, não

pode fazer parte das informações do contexto já que o algoritmo supõe que a única

informação de sua posição que o nó possui diz respeito à sua conectividade lógica com

outros nós.

A tomada de decisão do próximo salto é otimizada utilizando-se uma estimativa

dos valores futuros atributos de contexto ao invés da informação atual de contexto. Isso

permite que a escolha da melhor rota seja feita com uma precisão mais apurada, baseada

em informações mais próximas das atuais ao invés daquelas armazenadas. Um host que

queira enviar uma mensagem a um destino ou qualquer host no caminho para o destino

utiliza um filtro Kalman para predição e a teoria da decisão multicritério para escolher o

melhor próximo salto para a mensagem [19]. A decisão é baseada na mobilidade do nó e

sua posição (lógica) anterior em relação ao recebedor da mensagem. Ao contrário dos

protocolos anteriores, uma única mensagem é enviada pelo nó de origem, sem que haja

réplicas na rede.

O processo de predição e avaliação das informações de contexto podem ser

resumidas da seguinte forma:

1. Cada host calcula suas probabilidades de entrega para um determinado conjunto

de hosts. Esse processo é baseado no cálculo das utilidades para cada atributo que

descrevem o contexto. Os futuros valores dessas utilidades são então estimados

utilizando-se a teoria de decisão multicritério. As probabilidades de entrega

calculadas são periodicamente enviadas aos outros nós que se encontram dentro do

alcance como parte das atualizações de informações de roteamento.

31

2. Cada host mantém uma tabela de encaminhamento descrevendo o próximo salto e

a probabilidade de entrega associada a ele para todos os outros destinos.

3. Os hosts utilizam-se de técnicas de predição para prever as probabilidades de

entrega entre as atualizações de roteamento. O processo de predição é usado

durante desconexões temporárias e é executado até que uma certa precisão seja

alcançada.

3.2.2 – Protocolos de Roteamento VDTN

Por conta do alcance limitado, somente clientes ao redor do AP (Access Point)

podem receber dados diretamente. Entretanto, esses dados podem ser benéficos para

pessoas se movendo em veículos a quilômetros de distância. Um motorista pode, por

exemplo, querer requisitar informações de diversas lojas de departamento para decidir

onde ir. Além disso, esse mesmo motorista se beneficiaria caso pudesse observar o vídeo

de câmeras de tráfico e receber informações sobre vagas de estacionamento próximas à

loja para decidir o melhor caminho a tomar. Um passageiro pode requisitar informações

de vários pontos de ônibus para decidir onde descer para mudar de linha. Todas essas

requisições podem ser realizadas a quilômetros da área de broadcast com uma tolerância

de poucos minutos de atraso [20] graças ao uso de VDTNs. Nessa sessão veremos alguns

protocolos de roteamento tolerantes à atrasos propostos especificamente para redes

veiculares.

GeOpps

O protocolo GeOpps (Geographical Opportunistic Routing for Vehicular

Networks), em seu funcionamento, considera as rotas sugeridas pelo sistema de

navegação do veículo para escolher o nó com maior probabilidade de se mover em direção

ao destino, na qual será encaminhada a mensagem [21]. Ele calcula a menor distância

entre o destinatário da mensagem e o ponto mais próximo da rota de um veículo vizinho

e faz uma estimativa de tempo no qual o pacote chegará ao destinatário.

32

O valor da estimativa do tempo de chegada do agregado ao destinatário (Minimum

Estimated Time of Delivery) é utilizado na tomada de decisão do protocolo. Comparando-

se o valor estimado do nó que carrega a informação com a estimativa de seus nós vizinhos,

o protocolo determina para qual veículo o agregado deve ser transferido. Caso o valor de

METD do veículo que carrega o agregado for menor que os valores de seus vizinhos, ele

continuará com a custódia do agregado. Caso contrário, ele encaminhará a informação

para o nó que possuir o menor tempo de entrega estimado. O valor estimado é calculado

em função do trajeto que será percorrido pelo veículo. A Equação 3.5 exibe como o valor

de METD é determinado.

5647 = 64�(8,9) + 64�(9,7),

onde o valor de 64�(�, �)denota o tempo estimado que o veículo levará para percorrer

a rota entre os pontos � e �, 8 denota a posição atual do veículo e 9 denota a posição

mais próxima do trajeto do veículo ao posicionamento do destinatário do agregado (7).

O protocolo funciona enviando periodicamente a posição de destino dos

agregados que ele mantém a custódia. Quando um nó veicular recebe tal informação, o

protocolo estima o valor de5647 para cada posição recebida, a fim de calcular o tempo

estimado que o veículo levaria para carregar o agregado até o destinatário. Com posse

desses valores, o protocolo transmite essas informações de volta aos veículos que lhes

enviaram a mensagem de posicionamento, e assim cada veículo pode determinar se

continua com a custódia do agregado, ou se deve transferi-la para outro veículo.

Figura 3.7 – Cálculo do ponto mais próximo entre o destinatário e os caminhos 8/ e 80

Fonte: [21]

33

Durante o trajeto dos veículos, caso surja outro nó com melhor tempo estimado

de entrega, a mensagem será encaminhada para ele. O Processo continua até que a

mensagem seja encaminhada ao destino. O GeOpps necessita que informações de

navegação estejam disponíveis na rede, portanto, um dos pontos fracos deste protocolo

diz respeito à privacidade das rotas dos veículos.

VADD

O protocolo VADD (Vehicle-Assisted Data Delivery) [22] assume que a posição

e a trajetória de cada nó é conhecida. Para isso, o veículo deve estar equipado com um

sistema de posicionamento que contenha mapas digitais pré-carregados com informações

das ruas e estatísticas do tráfego, como densidade de veículos em uma via e a velocidade

média de estradas em diferentes partes do dia.

O protocolo defende que em redes esparsamente conectadas, veículos devem

tentar utilizar o canal de comunicação wireless e sempre encaminhar para o nó com maior

velocidade, o que gera os seguinte princípios básicos:

1. Transmitir pelo canal wireless tanto quanto possível.

2. Se o pacote deve ser encaminhado através de certas vias, a via com a maior

velocidade deve ser escolhida.

3. Dada a natureza imprevisível de uma VANET, não se pode esperar que

um pacote seja roteado com sucesso por uma rota ótima pré-computada,

portanto a seleção dinâmica de caminho deve ser continuamente executada

durante o processo de encaminhamento do pacote.

Dados esses princípios, a melhor rota é escolhida com base no menor atraso de

entrega esperado para o pacote. O atraso esperado de entrega de mensagens de um

caminho é modelado em função da densidade veicular, velocidade média e tamanho da

estrada segundo a Equação abaixo:

:;< = =1 −>?@.BCDE.�CD."

@+ >@.BCD .

�CDFCD

,

34

onde:;< denota o atraso de entrega esperado entre os cruzamentos G e H (I;<), R o

alcance de transmissão, J;< a densidade veicular em I;<, uma constante e K;< a

velocidade média em I;<.

Uma maneira de se ver o modelo de atraso do VADD é representar a rede veicular

como um grafo no qual os nós representam as interseções e as linhas representam as

estradas conectando interseções adjacentes. A direção de cada linha é o sentido do tráfego.

O atraso de entrega entre duas interseções adjacentes é o peso daquela linha. Dado o peso

de cada linha, pode parecer tentador utilizar o algoritmo de Dijkstra para calcular o menor

caminho, mas como não podemos selecionar livremente a linha de saída do pacote

(apenas as linhas com veículos podem ser candidatas à entrega do pacote) e não podemos

prever que direção o pacote tomará na próxima interseção, o algoritmo não pode ser

utilizado. Em outras palavras, é impossível computar o caminho completo de

encaminhamento do pacote.

Figura 3.8 – Um exemplo do modelo de atraso do VADD Fonte: [22]

Desta forma, os autores do protocolos VADD propuseram uma solução baseada

em um conjuntos de equações lineares do atraso estimado:;< e da probabilidade;< de

um pacote ser encaminhado através deI;< no cruzamentoG e limitaram o número de

35

interseções para realização do cálculo. Depois de montado o sistema de equações lineares

ela pode ser resolvida por um algoritmo de eliminação Gaussiano, por exemplo.

O protocolo pode assumir dois comportamento distintos, dependendo da posição

do nó que carrega o agregado. O primeiro comportamento ocorre quando o nó se encontra

entre dois cruzamentos, em uma linha do grafo e é chamado de modo direto. Nesse caso

o protocolo encaminha a informação de forma gananciosa, encaminhando o pacote para

o vizinho geograficamente mais próximo do destino que é o próximo cruzamento.

Figura 3.9 – Seleção do próximo veículo em um cruzamento Fonte: [22]

O segundo caso se dá quando o veículo se encontra em um cruzamento. Nesse

caso há duas possíveis opções e cada uma delas constitui em um uso diferente do

protocolo. Dada a figura acima, o nó� possui um pacote para encaminhar a dado destino.

Supondo que a direção ótima para esse pacote é o norte, existem duas possibilidades de

encaminhamento: o encaminhamento baseado em localização, priorizará o nó� já que

este está geograficamente mais próximo da direção ótima e pode contar com a sua

interface sem fio para encaminhar pacotes naquela direção no modo direto; enquanto isso

o encaminhamento baseado na direção escolherá o nó8, já que este se desloca na direção

ótima. A primeira opção dá origem ao protocolo Location First Probe (L-VADD)

enquanto o segundo é chamado de Direction First Probe (D-VADD).

36

GeoDTN+Nav

O protocolo GeoDTN+Nav é um protocolo de abordagem híbrida [23], ou seja,

hora funciona com DTN e hora não, que inclui um modo de funcionamento ganancioso e

um modo perímetro. Ele comuta seu modo de funcionamento (DTN ou não-DTN)

estimando a conectividade da rede baseando-se no número de saltos que um pacote

consegue realizar, qualidade de encaminhamento e direção do vizinho em relação ao

destinatário.

No modo de funcionamento ganancioso, assim como no VADD, o protocolo

escolhe os nós vizinhos para encaminhar as mensagens que estiverem mais próximos do

destino. Entretanto, tal abordagem pode fazer com que a informação seja encaminhada

para um nó (máximo local) que não possui vizinhos próximos ao destinatário. Quando

isto ocorre, o protocolo muda seu comportamento para o modo perímetro.

No modo perímetro, a mensagem é encaminhada segundo a regra da mão-direita.

Inicialmente um nó n define um vetor em direção ao destino (vetor inicial de restrição -

LMN) e um vetor originalKN voltado para o nó que lhe enviou a informação. As mensagens

serão encaminhadas para o primeiro nóO, no sentido anti-horário deKN, que puder se

comunicar com n sem cruzar o vetor inicial de restrição. Quando uma mensagem é

encaminhada para um nó mais próximo do destino o protocolo volta a funcionar em modo

ganancioso, caso contrário, a mensagem volta para o nó que a encaminhou e é descartada.

Uma questão importante do modo de funcionamento do protocolo é quando ele

deve mudar para o modo DTN e quando ele deve mudar para o modo ganancioso. O

GeoDTN+Nav deve mudar para o modo DTN quando a qualidade do padrão de

mobilidade do nó e o particionamento da rede, usando uma função de custo, superarem

um determinado patamar. E ele deve mudar para o modo ganancioso quando um nó

intermediário estiver mais próximo do destino que o nó que ativou o modo DTN.

A qualidade de encaminhamento é obtida através de uma interface de navegação

virtual (VNI - Virtual Navegation Interface) que abstrai informações das camadas

inferiores (sistemas de navegação, mapas etc). Já o particionamento da rede é conseguido

baseando-se na quantidade de saltos que a mensagem realizou quando o protocolo estava

em modo perímetro. Desta forma, segundo os autores, quanto maior a quantidade de

saltos maior a probabilidade da rede estar desconectada.

37

3.3 – Contextualização

Neste projeto, o uso de uma DTN foi o caminho encontrado para resolver os

problemas de conectividade e segmentação das redes veiculares expostos no capítulo

anterior. As quatro primeiras camadas do modelo TCP/IP serão mantidas e uma camada

de agregação armazenará o pacote no buffer de cada nó até que este entre no alcance de

seu próximo salto.

O principal objetivo desse trabalho é o desenvolvimento de um protocolo de

roteamento para bundles no sistema que será proposto no capítulo seguinte. Todo o

roteamento será feito nessa nova camada, enquanto a camada IP apenas transmitirá

pacotes nos links ponto a ponto entre dois nós diretamente conectados. O novo protocolo

transmitirá os bundles de um veículo até um gateway DTN, que será uma RSU. Alguns

conceitos empregados nos protocolos apresentados foram incorporados no novo

protocolo, especialmente aqueles empregados em VDTNs

38

Capítulo 4

Proposta

4.1 – Motivação

A promessa de aumento de segurança no trânsito tem sido um dos principais

incentivos ao desenvolvimento de redes veiculares. Por esse motivo, as aplicações de

segurança receberam tratamento diferencial dos órgãos reguladores e dos fabricantes de

veículos. Essas aplicações impõem requisitos estritos de latência e confiabilidade para as

mensagens [4], mas devem conviver com o complexo ambiente de VANETs sujeitos a

desconexões frequentes, alta escalabilidade e possível não existência de um caminho fim

a fim entre origem e destino das mensagens.

Considere como cenário uma rodovia. Pode haver momentos, conforme

mencionado no capítulo 1, em que a densidade de veículos na pista seja pequena o

suficiente para haver segmentação da rede (a densidade de veículos que participem da

rede pode ser ainda menor) e a conectividade fim-a-fim pode nunca existir. Na verdade,

um nó pode até mesmo permanecer isolado por longos períodos de tempo. Nesse cenário,

uma aplicação que envie uma mensagem com um pedido de socorro, pode jamais alcançar

o seu destino.

O cenário descrito acima é altamente provável em rodovias pouco movimentadas

durante horário de baixo tráfego. Para comprovar, podemos utilizar de exemplo o do

trecho da rodovia BR-290 ente Eldorado do Sul e Osório, administrado pela CONCEPA

(Concessionária da Rodovia Osório-Porto Alegre), onde o site da rodovia [24] mostra que

há períodos do dia que a densidade de carros é inferior a 1 por minuto após as 2h.

39

Figura 4.1 – Densidade de tráfego na BR-290 Fonte: [24]

Nesse caso, os protocolos da pilha TCP/IP não são capazes de encaminhar os

pacotes, já que não há conectividade ininterrupta entre origem e destino. Para garantir a

entrega das mensagens, a arquitetura dessa rede deve prever o uso de DTNs. Mesmo com

todos os NEs (Network Elements) suportando o modelo DTN com sua camada de bundle,

os pacotes ainda precisarão ser roteados para seus destinos. Para tal, deve se utilizar um

protocolo como aqueles apresentados no capítulo anterior.

Os protocolos baseados em flood têm a desvantagem de onerarem a rede com

múltiplas cópias de uma mesma mensagem, em especial em momentos de alta densidade

de nós, além de utilizarem-se pouco da óbvia previsibilidade do movimento dos veículos

em uma rodovia. Protocolos baseados em utilidade como o CAR, tornar-se-iam uma boa

opção, mas devido a simetria de movimento dos veículos na rodovia, parâmetros como

mobilidade e taxa de conectividade dos nós não são bons critérios na hora de se escolher

o próximo salto da mensagem.

Já os protocolos propostos para atender à VDTNs apresentados, necessitam de um

sistema de mapas integrado ao sistema de navegação do veículo. O GeOpps possui uma

abordagem simples, mas que ignora o fato de que em uma rodovia, os veículos se moverão

apenas ao longo da mesma, tornando o uso de mapas desnecessário. O mesmo vale para

40

o VADD, que no caso de um longo trecho sem cruzamentos, funcionará somente em

modo ganancioso, de forma muito parecida com o GeOpps. Por sua vez, o protocolo

GeoDTN+Nav também se utilizará do modo ganancioso para o encaminhamento até que

encontre um nó que não pode mais encaminhar pacotes. Nesse caso ele entenderá que há

um obstáculo entre o máximo local e o destino e tentará contornar esse obstáculo através

do modo perímetro. Como numa rodovia não se supõe a existência de cruzamentos, a

suposição de que se pode contornar o obstáculo está enganada e pode levar a uma latência

ainda maior para a entrega da mensagem a seu destino.

Tendo isso em mente, a proposta desse trabalho é desenvolver um protocolo que

permita a entrega do pacote ao seu destino com a menor latência possível em uma rodovia

sem que nos utilizemos de mecanismos de flood para tal. O protocolo deve se utilizar da

trajetória conhecida de rodovias e do fluxo contínuo, ainda que esparso, de veículos para

escolher o melhor caminho sem utilizar-se de mapas que podem não estar disponíveis em

todos os sistemas, ou mesmo conter versões discrepantes entre dois nós distintos. Um

sistema de posicionamento, seja ele por satélite tal como o GPS (Global Positioning

System) ou por triangulação ainda será necessário. O protocolo deve entregar a mensagem

para um destino externo ao domínio DTN, alcançado somente por um nó de infraestrutura,

que chamaremos de “Gateway”, que fará o papel de borda da DTN. O protocolo também

deverá garantir a resposta da mensagem (caminho inverso) do gateway até o nó de origem.

4.2 – Cenário considerado, arquitetura e premissas

O cenário descrito acima corresponde à topologia da nossa VANET. Nele,

veículos só podem se mover ao longo de uma estrada sem interseções. Há gateways

espalhados periodicamente no acostamento ao longo da via, equidistantes entre si. Os

gateways são nós de infraestrutura que funcionam como bordas da rede DTN e se

conectam com a rede externa onde se encontra o endereço de destino dos pacotes.

A arquitetura da solução segue o modelo DTN apresentado no capítulo anterior.

Os veículos e as RSU’s fazem parte de um mesmo domínio DTN, enquanto a rede externa

(infraestrutura) segue o modelo TCP/IP convencional. A integração entre a DTN e a

infraestrutura é feita pela RSU, que portanto tem o papel de gateway na DTN e funciona

como elemento de borda entre os domínios tolerante a atraso e não-tolerante a atraso.

41

Dentro do domínio DTN o roteamento se dá a nível de agregação onde mais de

um segmento UDP pode ser encapsulado em um único bundle que é roteado por múltiplos

saltos através de veículos na estrada até o gateway. O gateway é o destino do bundle,

mas não da mensagem, que continuará a ser roteada até o seu destino final na

infraestrutura pela camada de rede. A figura abaixo denota a arquitetura da solução:

Figura 4.2 - Arquitetura proposta

A figura 4.3 demonstra uma requisição feita por um veículo que se envolve em

uma colisão. O destino da requisição é uma rede externa ao domínio DTN, dentro da

nuvem da infraestrutura (seja ele na internet ou em uma intranet do serviço de

emergência). Para encaminhar a sua requisição para essa rede externa, o veículo deve

encaminhar seus pacotes para uma das RSUs na figura. Cada RSU possui comunicação

com a rede externa e portanto, faz o papel de gateway da DTN. Diversas RSUs como as

da figura devem estar espalhadas ao longo do acostamento da rodovia, todas a uma

distância : da anterior. A distância constante adotada é um fator de previsibilidade que

impomos ao sistema. Essa previsibilidade será importante para o desenvolvimento do

protocolo de roteamento, já que poderemos facilmente inferir a posição da próxima RSU

sem a necessidade de manter essa informação armazenada em cada nó, ou atualizada por

trocas de mensagens de controle.

Continuando com a troca de mensagens, no caso da figura abaixo, como não há

conexão direta do requisitante com uma RSU, aquele deve encaminhar seus bundles para

outro veículo que por sua vez se deslocará até entrar em contato com uma RSU ou os

reencaminhará a outro veículo que poderá fazê-lo mais rapidamente.

42

Figura 4.3 – Entrega da mensagem no cenário proposto Para fins de simulação, apenas uma requisição será feita por vez, de forma a nunca

existir mais de um pacote armazenado no buffer de um nó, que consequentemente sempre

terá memória disponível. Dito isto, não será levado em conta o gerenciamento de buffer

e demais implicações de se lidar com múltiplas mensagens, como comparação de buffers

(sessão anti-entropia) e enfileiramento de mensagens, o protocolo sempre conseguirá

transmitir a mensagem quando o canal estiver disponível e não haverá tratamento de

exceções. Por fim, um sistema de posicionamento está sempre presente em cada nó, de

forma que este sempre seja conhecedor de sua posição atual.

43

4.3 – Cenários de teste

Para se tornar viável, o protocolo deve ser testado sob todas as condições da via.

Ao longo do dia a densidade de veículos de uma via pode variar consideravelmente. Em

[24] foram medidas picos de cinquenta e quatro carros por minuto em um trecho de

aproximadamente 30km entre Porto Alegre e Gravataí. Essa média de dois carros por

quilômetro ainda é baixa, o que torna esse trecho de rodovia ideal para este protocolo.

Entretanto, um acidente, obras na pista, ou congestionamentos por motivos diversos em

outras situações críticas podem elevar essa densidade em pequenos momentos ao longo

do dia. Faz-se necessário que o protocolo também suporte esse tipo de cenário, a um custo

talvez de uma menor eficiência, a fim que ele seja confiável em qualquer momento.

Para isso, dois testes foram desenvolvidos, um deles com apenas quatro veículos

transitando pela rodovia bem espaçados entre si. O objetivo é testar o protocolo em uma

rede descontínua em um cenário possível, onde a densidade de veículos é próxima

daquela obtida após as 0h em [24]. Também nesse cenário espera-se observar a tomada

de decisão do protocolo, para isso o movimento dos veículos é tal que o nó 0 terá duas

opções de nós para encaminhar o seu pacote, mas deverá escolher aquele com a melhor

métrica.

Já no segundo cenário, será testado o outro caso extremo, isto é, uma rodovia com

alto tráfego em ambos os sentidos. Aqui, vinte e seis veículos irão trafegar, treze em cada

direção, de forma equidistantes e a velocidades constantes. O espaçamento dos veículos

em uma pista será tal que não haverá alcance para transmissão entre eles.

4.4 – O protocolo

Diferentemente das transferências na internet, onde o roteamento é realizado

somente na camada de rede do modelo TCP/IP, o roteamento DTN é terminado na camada

de agregação. As camadas inferiores possuem o mesmo comportamento da internet, mas

tratam saltos intermediários como o destino final de cada pacote. Somente a camada de

agregação conhecerá o destino final da aplicação e encaminhará o bundle através da DTN.

A diferença entre o roteamento convencional (internet) e o roteamento DTN é

mostrado na figura abaixo. Os roteadores da internet encaminham pacotes de camada de

44

rede em múltiplos saltos até o seu destino, onde a camada de transporte estabelece uma

sessão. Enquanto isso, cada salto de um roteamento DTN estabelece uma sessão completa

da camada de transporte, isto é, do ponto de vista das camadas inferiores (1 a 4) a conexão

é do tipo ponto-a-ponto. Somente a camada superior de agregação reconhecerá que o

destino final do pacote está outro host, acessível por múltiplos saltos. A camada de

agregação roteará o bundle via múltiplos saltos até seu destino final.

Figura 4.4 - Transferência convencional x Transferência DTN

Quanto ao funcionamento do protocolo em si, ele se dará em duas partes: em um

modo chamado “oportunístico” quando a mensagem tiver destino na infraestrutura e no

modo ganancioso quando tiver destino em um nó ad hoc (veículo).

Primeiramente, os nós participantes enviarão beacons contendo a sua posição, a

métrica e uma flag para identificar se é um gateway ou não. O valor da flag deve ser 1

para um nó gateway. Se um beacon é recebido com a flag acionada (1), o nó atualizará

sua própria métrica “tempo”. Essa métrica se traduz na última vez em que este nó entrou

em contato com um gateway. Com base nas informações recebidas pelos beacons de nós

45

ao alcance da interface de rádio, cada elemento de rede montará uma tabela de contatos

contendo a posição, a métrica e o flag do vizinho.

Uma mensagem a ser transmitida (seja por requisição de camada superior, em

caso do nó originar a mensagem, ou armazenada no buffer para ser retransmitida) possui

um flag que denota o modo de encaminhamento. Caso a flag esteja ativada, o nó

transmissor entenderá que deve encaminhá-la de forma gananciosa, caso contrário o

modo oportunístico deve ser utilizado. A flag é ativada sempre que a mensagem atravessa

um gateway, o que só vai ocorrer quando a mensagem for originada em uma rede externa

ao domínio DTN ou no próprio gateway.

Caso a flag esteja desativada, o encaminhamento se dará no modo oportunístico.

Aqui o protocolo se faz valer do conhecimento prévio da topologia e da mobilidade de

cada nó. Sabe-se que a velocidade média dos nós é aproximadamente constante, já que se

supõe que todos os veículos respeitarão a velocidade limite da pista e que a os nós só se

locomoverão ao longo da rodovia. Soma-se a isso o fato de os gateways estarem

uniformemente distribuídos na via e equidistantes entre si. O protocolo assume, então,

que um nó que entrou em contato com um gateway há mais tempo tem maior

probabilidade de entrar em contato com o próximo gateway.

Portanto, no modo oportunístico o nó transmissor consultará sua lista de contatos

e procurará retransmitir a mensagem para um nó com a flag de gateway ativada. Caso não

haja nenhum, a transmissão será feita para o nó com a maior métrica, ou seja, o nó que

atravessou a mais tempo um gateway. O processo será repetido até que a mensagem

chegue ao gateway, que então o encaminhará a seu destino.

No caso da flag da mensagem estar ativada, o protocolo mudará sua forma de

encaminhamento para o modo ganancioso. Assim como em outros protocolos já

demonstrados, neste modo o nó transmissor procurará sempre encaminhar a mensagem

para um contato geograficamente mais próximo do destino.

Vale ressaltar que cada nó ad hoc só possui conhecimento da posição de seus

contatos. Quando uma mensagem é encaminhada no modo oportunístico, esta deve conter

a posição do nó de origem. Apenas o nó gateway deve manter uma tabela com a posição

dos nós ad hoc. Dessa forma, quando uma mensagem chegar da infraestrutura com

destino a um nó na rede DTN, apenas o gateway que recebeu a mensagem daquele nó

anteriormente conhecerá uma rota para aquele nó. Quando a mensagem for encaminhada

no modo ganancioso, o campo posição deverá ser preenchido pelo gateway com a posição

esperada do nó de destino considerando a velocidade média da pista.

46

De forma resumida, no protocolo cada veículo deve tomar o conjunto de decisões

ilustrados no diagrama abaixo:

Há mensagem no

buffer?

Sim

Qual o modo de

operação?Ganancioso

Há contato mais

próximo do

destino?

Oportunístico

Há contato com

maior métrica?

SimSim Transmitir

Destino está nos

contatos?NãoNão

Possui RSU nos

contatos?

Sim Sim

Não

Apagar buffer

Não

Não

Figura 4.5 - Diagrama de blocos de um veículo

De forma análoga, uma RSU também deve tomar algumas decisões de

encaminhamento de bundles. Entretanto, por ser uma estrutura fixa ela participa de forma

passiva do roteamento dito oportunístico. Seu único papel nesse modo é o de encaminhar

o pacote para a infraestrutura. Já para o modo ganancioso, a RSU possui o papel

fundamental de ativar o flag de modo ganancioso para permitir que nos saltos seguintes

o pacote seja encaminhado neste modo. Além disso, nesse caso ela funciona como um nó

DTN e armazena o bundle em seu buffer a espera de um contato válido para transmiti-lo.

O diagrama abaixo resume a operação do protocolo em uma RSU:

47

Recebe Mensagem

Qual a origem da

mensagem?

Retirar bundle e

transmitir para a

infraestrutura

Encapsular bundle

ativando flag de modo

ganancioso

Veículo DTN Infraestrutura

Transmitir para

DTN

Há contato mais

próximo do

destino?

Sim

Não

Figura 4.6 - Diagrama de blocos de uma RSU

A desvantagem dessa abordagem é que se o veículo não tiver feito nenhuma

requisição ao gateway, esse não conhecerá sua posição e não saberá encaminhar o pacote.

Do ponto de vista de segurança, isso pode ser visto como uma vantagem, já que pacotes

serão enviados para a rede ad hoc apenas se uma sessão já houver sido estabelecida pelo

veículo.

A seguir, o pseudocódigo com a lógica de funcionamento do protocolo:

48

Loop Infinito {

envia e recebe beacons de nós vizinhos contendo métrica, posição e tempo

monta tabela de contatos

para cada beacon recebido {

Se for um Gateway {

atualizar própria métrica

}

}

Há mensagem no buffer?

sim {

Se este nó for um Gateway {

seta flag de modo ganancioso

}

Qual é o modo de operação?

Oportunístico {

para cada contato {

é um Gateway?

sim {

Transmitir para contato

limpar buffer

encerrar

}

não {

comparar métricas

}

}

há contato com métrica melhor?

sim {

transmitir mensagem para o contato

com a melhor métrica

limpar buffer

}

não {

mantém mensagem no buffer

49

}

}

Ganancioso {

calcula distância entre esse nó e o destino

calcular distância entre cada contato e destino

se houver contato cuja distância é menor {

Transmitir para contato com a menor

distância

limpar buffer

}

}

}

não {

escuta o meio

se receber mensagem {

armazena no buffer

se este nó for um gateway {

armazena posição do nó de origem

}

}

}

}

4.5 – Considerações

A proposta tem como objetivo formular um protocolo de roteamento em camada

de agregação que se aproveite da previsibilidade da rede para entregar um agregado

(bundle) a seu destino. O cenário teorizado visa atender os requisitos de previsibilidade

necessários para que o protocolo opere corretamente de forma palpável e com hardware

convencional. Uma RSU nada mais é do que um AP (Access Point) e cada veículo deve

estar equipado somente com uma placa de rede wireless compatível com o padrão IEE

802.11a.

50

O protocolo e o cenário foram pensados de forma a otimizar o tempo entrega de

uma mensagem originada em um veículo para o destino atendendo os requisitos de

latência de aplicações de segurança que acionam serviços de emergência públicos. Como

mostrado em [7], o tempo de resposta entre um acidente e acionamento do serviço de

emergência é crítico para reduzir a taxa de mortalidade em acidentes. O modo

oportunístico do protocolo foi teorizado com esse intuito. Um protocolo de roteamento

não pode servir para uma única aplicação e tampouco em uma única direção. Portanto um

modo ganancioso inspirado naqueles dos protocolos VADD e GeoDTN+Nav foi

desenvolvido com a única preocupação de estabelecer o caminho de volta de um pacote.

Dessa forma, sessões que necessitem de confirmação de resposta como o protocolo TCP,

podem ser implementados, assim como aplicações interativas, que não são o foco desse

projeto.

O capítulo seguinte mostra o resultado da simulação desse protocolo em dois

testes. Para comprovarmos a eficácia desse protocolo, a simulação do protocolo

Epidêmico para os dois testes também será realizada. Tal protocolo foi escolhido tendo

em vista a baixa complexidade e a menor latência teórica que ele apresenta em relação

aos demais protocolos.

51

Capítulo 5

Simulação e Resultados

5.1 – Simulador

Para simular a operação do protocolo, foi utilizado o software NS-2. O NS-2 é

uma ferramenta de simulação de código livre desenvolvido para sistemas operacionais

baseados em unix. É um simulador de eventos discreto resultante de um projeto conhecido

como VINIT (Virtual InterNetwork Testbed) que teve a participação de importantes

instituições como DARPA, USC/ISI, Xerox e Universidade de Berkley.

O simulador NS é baseado em duas linguagens: C++ para a estrutura básica e um

interpretador OTcl (Object Tool Command Language) como um frontend, Ele suporta

uma hierarquia de classes compiladas em C++ e uma hierarquia interpretada em OTcl.

Ambas possuem correspondência de um pra um entre si.

A hierarquia compilada em C++ permite alcançar uma maior eficiência na

manipulação de bytes, cabeçalhos de pacotes e na implementação de algoritmos que

trabalhem com grandes conjuntos de dados. Para essas tarefas o tempo de execução é

mais importante que o tempo de turn-around (execução da simulação, encontrar bugs,

recompilar e re-executar).

Por outro lado, quando as classes da hierarquia compilada são suficientes, ou

deseja-se apenas variar parâmetros e configurações destas classes, ou mesmo explorar

rapidamente um grande número de cenários, o uso do OTcl é recomendado. Nesses casos,

o tempo de interação (mudança do modelo e execução da simulação) é mais importante.

Como o cenário considerado nesse trabalho contempla apenas um pacote por vez

na rede (e consequentemente na simulação), o tempo de execução não é tão importante

quanto o tempo de turn-around. Por isso, a linguagem utilizada foi o OTcl.

5.1.1 – Arquitetura do NS-2

52

Como mencionado anteriormente, o ns-2 é um simulador de eventos discretos

orientado a objetos. Os eventos são processador por um dos cinco tipos de agendadores,

sendo o padrão o calendar queue. O agendador seleciona o próximo evento agendado

para mais cedo, executa-o por completo e retorna para executar o próximo evento. O

agendador é mono-tarefa, portanto apenas um evento é processado de cada vez. A unidade

de tempo utilizada pelo agendador é o segundo.

Um evento é manipulado chamando-se a classe de Handler apropriada. A classe

de Handler mais importante é a NSObject, com a TclObject como sua gêmea no mundo

OTcl. Elas provêm todas as funções básicas que permitem que objetos interajam uns com

os outros. NSObject/TclObject são as classes pais para algumas importantes outras

classes, como a Classifier, a Connector e a TraceFile.

Figura 5.1 – Classe NSObject Fonte: [26]

5.1.2 – O nó móvel

Um nó sempre recebe um pacote do seu ponto de entrada. O primeiro passo que

um pacote toma é ir para um classificador. A função do classificador é a de examinar os

campos dos pacotes, normalmente os endereços de origem e destino. Ela deve então

mapear estes valores para uma interface de saída do objeto para o próximo recipiente do

pacote. Isso pode ser outro classificador ou um agente.

Agentes pertencem ao grupo dos conectores. Quando um conector recebe um

pacote, ele executa algumas funções e entrega o pacote para seu vizinho ou o descarta.

53

Existem vários conectores como Agent, Link Layer (LL), Interface Priority Queue (IFq),

MAC (Medium Access Control) module e Network Interface (NetIF).

Figura 5.2 – Conectores Fonte: [26]

5.1.3 – Gerador de tráfego

Os geradores de tráfico são os objetos que injetarão tráfego na rede. Os pacotes

de dados são sempre injetados por um agente como o TCP (Transmission Control

Protocol) ou o UDP (User Datagram Protocol), que são agregados à um nó. Para

emissão, o agente envia o pacote para o ponto de entrada de seu nó. Para recepção, o

agente recebe o pacote através dos classificadores do nó.

Um agente transmissor precisa de um agente receptor para funcionar como destino

dos seus pacotes. No caso do agente transmissor ser o TCP, seu correspondente receptor

será o sink (tanque) e tem a incumbência de gerar pacotes de reconhecimento (ACK –

Acknowledge). No cado do agente transmissor ser o UDP, o receptor chama-se null (nulo).

54

O agente, entretanto, não é a origem dos dados. Um processo alimenta o agente emissor

com os dados, ou mais especificamente, um gerador de tráfego.

Para a simulação, um gerador de tráfego CBR (Constant Bit Rate) com um agente

UDP foi utilizado. Com essa configuração é possível estudar a real performance da rede

ad hoc sem qualquer influência indesejada e desconhecida de outros protocolos. Isso se

aproxima bastante do comportamento do mundo real.

5.1.4 – Arquivos de Movimento e de Trace

Para simular redes móveis, além de definir a topologia (declarando os nós no

objeto simulador), podemos introduzir movimento aos nós através de um arquivo de

movimento. Esse arquivo contém as instruções como posição inicial, destino e velocidade

de cada nó. Em suma, esse arquivo gerará eventos para o agendador com a posição dos

nós ao longo do tempo de simulação.

O resultado dessa simulação são dois arquivos de trace: um arquivo de trace

normal (criado pelos comandos $ns_ trace-all) e um arquivo de trace nam ($ns_ nam-

traceall).

O arquivo de trace nam é um derivado do arquivo de trace normal com o sufixo

“,nam”. Ele contém a informação para visualizar o fluxo dos pacotes e o movimento dos

nós na ferramente homônima “nam”. Nam é um ferramenta de animação baseada em

Tcl/TK para visualização de traces de simulações ou mesmo de traces de dados reais.

Para estudar o comportamento de um protocolo, deve-se observar o arquivo de

trace normal, com o sufixo “.tr”. Ele contém todos os dados de trace produzidos pela

simulação. No script de configuração TCL pode-se dizer ao simulador que tipo de

informação deve ser rastreada: agente, rota ou MAC.

55

Figura 5.3 – Saídas do NS-2 Fonte: [26]

5.2 – Parâmetros de simulação

A proposta desse trabalho é desenvolver um protocolo que seja compatível com

hardware comum de prateleira que execute padrões conhecidos de protocolos de camadas

inferiores. Para tanto, nossa camada física constitui de uma antena omnidirecional com

potência de transmissão de 20dBm a uma frequência de 2,4GHz, que são valores padrão

de mercado para dispositivos 802.11b/g:

# Potência de transmissão (em Watts)

set opt(Pt) 0.1

# Equivalente a 20 dBmPa

# Frequencias de operacao

set opt(freq) 2437e6

56

O modelo de propagação utilizado foi o free space. Além de oferecer um cálculo

mais simples do alcance do sinal, ele nos oferece um valor inferior de alcance do que no

two-ray ground, o que colocará o novo protocolo sob condições ligeiramente mais

agressivas de transmissão. Para compensar, as taxas de transmissão foram limitadas a

6Mbps, obtendo uma relação SNR de 7dB com 0.001 de PER.

O cálculo do alcance é realizado pela procedure calculaAlcance abaixo:

proc calculaAlcance { snr } {

global opt

# calculo do alcance de acordo com o modelo de propagacao FreeSpace

# Pr = Pt*Gt*Gr*lambda^2/(4p)^2 * L * d^2

set PI 3.14159265359

set RXPwr [expr $opt(noisePower)*pow(10,$snr/10.0)]

# Cálculo realizado: snrDB = 10 log (pr / noisePower)

puts "Pr= $RXPwr"

set lambda [expr 3.0e8 / $opt(freq)]

# Cálculo realizado: lambda = c / f

set aux [expr (4.0 * $PI) / $lambda ]

set opt(alcance) [expr sqrt($opt(Pt) / ($RXPwr * $aux * $aux))]

# Cálculo realizado: d^2 = pt*gt*gr*lambda^2 / (4PI)^2 *L*pr

puts stderr "Alcance : $opt(alcance)"

Introduzindo-se o SNR (Signal to Noise Ratio), a procedure calcula e retorna o

alcance de cada nó através da equação apresentada no modelo free space.

5.2.1 – Configurando os nós

57

Antes de instanciar os nós, devemos configurar o objeto “node” para definirmos

alguns parâmetros de camada física, como o tipo de antena, canal de transmissão, modelo

de propagação e tamanho da fila (em bytes) das interfaces. Mais importante, definimos

aqui o tipo de link físico que será sem fio.

$ns_ node-config \

-adhocRouting NOAH \

-llType LL \

-macType Mac/802_11/Multirate \

-ifqType Queue/DropTail/PriQueue \

-ifqLen 10 \

-antType Antenna/OmniAntenna \

-propType Propagation/FreeSpace/PowerAware \

-phyType Phy/WirelessPhy/PowerAware \

-channel [new Channel/WirelessChannel/PowerAware]

Aqui também definimos os conectores que serão utilizados. O Link Layer Object

será o LL, que suporta os protocolos e mecanismos padrões da camada de enlace, como

a fragmentação e remontagem dos pacotes, enfileiramento, retransmissões a nível de

enlace, etc. O Interface Priority Queue configurado é do tipo Drop Tail, onde não há

diferenciação do tráfego e os pacotes mais recentes são descartados quando a fila da

interface estiver cheia. Como só haverá um pacote na rede de cada vez, foi decido utilizar

o tipo de enfileiramento mais simples.

O agente MAC escolhido foi o 802.11, padrão IEEE. O NS-2 implementa ambas

as funções de coordenação DFWMAC (Distributed Foundation Medium Access Control),

ele utiliza CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance) para pacotes

broadcast e multicast e RTS (Request To Send) / CTS (Clear To Send) para pacotes

unicast.

Por fim, definimos o Routing Agent Object (Rtagent), que implementa o protocolo

de roteamento a ser utilizado. Para redes ad hoc, é comum utilizar-se AODV (Ad hoc On-

Demand Distance Vector) ou o DSDV (Destination-Sequenced Distance Vector).

Entretanto, como o objetivo do trabalho é desenvolver um protocolo para substituir os

dois anteriores (que são ineficientes para o nosso cenário), esse agente foi configurado

58

com a opção NOAH (No Ad Hoc). O NOAH é um agente de roteamento wireless que

suporta apenas a comunicação direta entre os nós, de forma que o cenário de múltiplos

saltos será criado por cima desse agente. Isto é, acima dele teremos a camada de agregação

armazenando o pacote e o novo protocolo roteando o agregado por meio de múltiplos

saltos (multihop).

5.2.2 – Topologia

Antes de definir os nós propriamente ditos no código, faz-se necessário uma breve

explicação sobre a topologia a ser utilizada.

No primeiro teste serão considerados seis nós dispostos ao longo de uma rodovia

que segue ao longo do eixo vertical. Desses, quatro são veículos e dois são elementos de

infraestrutura (RSUs) conectados à uma rede externa que contém o destino das

solicitações feitas pelos veículos.

Figura 5.4 – Topologia Inicial

59

Em um primeiro momento, os nós 0 e 3 estão próximos à RSU 1 e se deslocam

para cima no eixo vertical, enquanto o nó 4 está próximo à RSU 2 e se desloca para baixo

ao longo do mesmo eixo. As RSUs, como unidades de acostamento, ficarão imóveis,

assim como o nó 5, situado verticalmente mais abaixo dos demais. Os nós 0, 3 e 4 são

veículos em movimento na rodovia, enquanto o nó 5 é um veículo que entrará nesse trecho

da via em um futuro próximo, mas deve ser declarado desde o início, por isso, ficará mais

abaixo, fora do alcance da RSU 1.

Já no segundo momento, o nó 0 para no meio da rodovia e requisita serviço de

emergência, porém não há nenhum veículo ou RSU ao seu alcance para ele encaminhar

a mensagem. Deverá portanto esperar os nós 3 e 4 se deslocarem até estarem ao alcance

para que a mensagem seja enviada. A velocidade e posição desses 2 veículos foi calculada

de forma que eles entrarão na área de alcance do nó 0 ao mesmo tempo e o protocolo de

roteamento deverá escolher a melhor opção para encaminhar a mensagem. Paralelamente,

o nó 5 inicia seu movimento para cima à velocidade constante, assim como os demais

veículos.

O protocolo deverá fazer com que a mensagem gerada no nó 0 seja encaminhada

para o nó mais próximo da próxima RSU, já que suas velocidades são as mesmas. Como

vemos na figura, o veículo 4 está mais próximo da RSU 1 do que o veículo 3 está da RSU

2. Portanto, esperamos que o protocolo seja capaz de encaminhá-lo para esse veículo.

60

Figura 5.5 – Nó 0 deseja enviar uma mensagem

Já para o teste dois, a topologia é semelhante, com os nós 1 e 2 representando

RSU’s fixas e o nó 0 representando um veículo que em determinado momento para e

solicita serviço de emergência. Além desses, outros 25 veículos estão dispostos em duas

faixas. Os da esquerda se deslocam para baixo e os da direita se deslocam para cima ao

longo da rodovia de acordo com sua mão. A densidade de veículos será maior, e em

determinados momentos pode haver conectividade fim a fim entre o nó 0 e uma RSU. O

que se verifica, entretanto é que essa conectividade não existe no momento em que o

serviço de emergência é requisitado.

61

Figura 5.6 – Topologia do Teste 2

5.2.3 – Instanciando os nós

Como visto na topologia, a simulação precisa instanciar seis nós, para isso, um

laço “for” de 0 a 5 foi criado onde a variável “i” substitui o índice do nó. Cada nó é então

declarado como um objeto do tipo node na classe ns:

set node_($i) [$ns_ node]

Dentro desse laço, serão declarados cada vetor e argumentos que queremos

armazenar em cada nó. O vetor de contatos manterá a lista de contatos de cada nó que

será calculado pela procedure “findContacts”.

# Vetor de contatos de um nó

set contacts_($i) [list $i]

62

A variável time_ mantém a data (dia, hora, minutos, segundos e frações de

segundos) em que um veículo trocou beacons com uma RSU. O valor padrão é -1. Esse

valor será repassado aos outros nós a cada beacon e será usado de métrica.

# Vetor que armazena o tempo em que do nó i passou pelo AP

set time_($i) -1

Um nó deve diferenciar uma RSU e de um veículo, para isso foi criada a variável

FGW_, que será 1 em caso do nó ser uma RSU e se manterá desabilitada caso contrário.

A chamada flag de gateway será trocada nas atualizações do protocolo com os nós

vizinhos, de forma que este possa atualizar sua variável time_ além de servir como uma

métrica de maior peso que a time_.

# Flag de Gateway

if {$i == 1 || $i == 2 } {

set FGW_($i) 1

} else {

set FGW_($i) 0

}

Quando um pacote é originado em uma RSU, ou mesmo atravessa uma RSU vinda

da rede externa com destino na instância DTN, a RSU define um flag de modo

ganancioso, que dirá aos nós seguintes que essa mensagem deverá ser encaminhada em

modo ganancioso. A variável FGreedy armazena essa flag.

#Flag de Modo Ganancioso

set FGreedy 0

Por fim, dois vetores armazenarão os geradores e os recebedores de tráfego de

cada nó, que serão ativados quando um nó tiver que encaminhar a mensagem para o nó

seguinte. O gerador de tráfego simulará tanto o pacote sendo gerado no nó 0 ou na RSU

quanto o pacote sendo retirado do buffer e retransmitido para outro nó na VDTN.

# Armazena os geradores de trafego de cada no

63

set cbr_($i) { }

# Armazena os recebedores de trafego de cada no

set loss_($i) [new Agent/LossMonitor]

Vale ressaltar que o valor da posição dos nós também é um atributo do nó. Porém,

diferentemente dos acima, os valores das posições X e Y do nó no plano da simulação

são atributos inerentes do objeto node da classe ns e por isso não precisam ser declarados

explicitamente.

5.3 – Desenvolvimento do Protocolo

A procedure “findContacts” simula a troca de beacons entre os nós da rede. Ela

possui dois laços “for” em cadeia, onde o primeiro se refere ao nó de origem e o segundo

ao nó de destino de forma que todos os nós sejam testados entre si. Dentro do laço

primeiramente é calculada a distância entre o par origem/destino e essa então é comparada

com o alcance retornado pela procedure “calculaAlcance”. Se o valor da distância for

menor que o alcance, o nó destino recebeu o beacon do nó origem. O ó destino irá então

verificar se o nó origem já se encontra em seu vetor de contatos e em caso negativo irá

adicioná-lo ao final do mesmo. Adicionalmente, o nó destino também verificará se o

beacon recebido possui a flag de gateway FGW ativada, caso em que deverá atualizar sua

própria métrica time_ para a data atual. Já no caso do nó origem não estiver ao alcance

do nó destino, ele será então removido do vetor de contatos do primeiro nó.

Ao final dessa procedure há uma chamada recursiva a ela mesma dentro de um

tempo definido pelo protocolo para uma nova troca de beacons. Não é objetivo desse

trabalho calcular o melhor tempo de intervalo entre beacons, mas certamente a escolha

deste tempo seria uma decisão fundamental para a implementação do protocolo em larga

escala. Quanto menor o tempo de intervalo, maior a precisão das métricas e menor será o

atraso entre o nó entrar ao alcance do outro e haver uma transmissão. Entretanto, um

menor intervalo também significa que pacotes de controle serão transmitidos com maior

frequência, gerando maior congestionamento da rede e consumindo tempo de transmissão

da interface aérea. Uma possível solução para esse problema seria o envio de pacotes de

controle em um canal de controle dedicado, independente do tráfego dos dados.

64

Para essa simulação, foi escolhido o tempo de 50ms:

$ns_ at [expr 0.05 + $now] "findContacts"

A procedure “habilitarTX” é chamada no momento em que um nó deseja

transmitir uma mensagem. Ela realiza dois testes e então chama a procedure adequada ou

não faz nada. O primeiro teste verifica se há contatos disponíveis no vetor de contatos do

nó enquanto o segundo testa o status da flag de modo ganancioso (FGreedy). Se a a flag

estiver habilitada e houver contatos disponíveis, a procedure “greedyContact” será

invocada. Já se a flag estiver desabilitada e houver contatos disponíveis, a procedure a

ser invocada será a “melhorContato” e o protocolo estará em seu modo de operação

normal. Caso não haja contato disponível os testes falham e nenhuma procedure será

invocada. O resultado dessas funções será armazenado na variável relay, que será

repassada de argumento para a procedure “criarRota”. Assim como a “findContacts”,

essa função chama a si mesma recursivamente após o intervalo entre beacons.

As duas procedures invocadas na “habilitarTX” definem o modo de operação do

protocolo. Ambas as funções recebem o index do nó de origem e seu vetor de contatos,

mas enquanto a “melhorContato” utilizará as métricas time_ e FGW para transmitir a

mensagem para o próximo nó, a “greedyContact” levará em conta apenas a posição dos

nós em relação ao destino.

A “melhorContato” testa um contato por vez e o compara sua métrica time_ com

a sua própria métrica time_. Se o contato possuir uma métrica melhor, ele será eleito o

melhor contato provisório e as comparações seguintes serão feitas com a sua métrica ao

invés daquela do nó de origem. No final, o contato com a melhor métrica será eleito o

melhor contato e seu index será retornado para a linha da procedure “habilitarTX” que o

chamou.

A “greedyContact”, por outro lado, calculará a distância do nó atual e de todos os

seus contatos para a posição do nó de destino que foi encaminhada com a mensagem. O

contato que possuir o menor valor de distância será eleito o próximo salto. Vale ressaltar

que se um contato for o nó de destino, espera-se que a distância deste para a posição do

nó destino carregada na mensagem seja zero e, portanto, ele seja eleito o próximo salto

independentemente do valor de distância dos demais contatos.

Uma vez eleito o próximo salto, ele será utilizado pela “habilitarTX” como

argumento para invocar a função “criarRota”. Essa procedure criar os agentes UDP e

65

associa os geradores de tráfego, estabelecendo a troca de dados. Além disso, aqui também

será ligada a flag de modo ganancioso caso o nó atual seja uma RSU, isso é, possua sua

flag de gateway (FGW) acionada.

5.4 – Desenvolvimento do protocolo epidêmico

Para ter-se uma melhor ideia do desempenho do novo protocolo, foi desenvolvido

uma versão epidêmica semelhante àquela proposta em [2]. Nele, um nó que queira enviar

uma mensagem fará uma inundação na rede, espalhando uma cópia a todos os nós que

puderem recebe-la até que ela chegue a seu destino, no caso, a RSU 1.

Sempre que um nó estiver ao alcance de outro, estes realizarão uma sessão de anti-

entropia onde o nó de destino verificará se já possui a mensagem que o nó de origem quer

transmitir ou não e informará ao nó de origem o resultado. Caso a mensagem ainda não

seja conhecida, o nó de origem irá transmiti-la. Vale ressaltar que como na simulação

anterior, apenas uma mensagem deverá ser transmitida, mas nesse caso diversas cópias

da mensagem poderão existir simultaneamente na rede.

Para implementá-lo, foi criada a procedure “criaMSG”, que habilita a flag de

mensagem no objeto node de origem e configura uma variável TTL_ com valor inicial

10. O TTL, como explicado no capítulo anterior, limita o número de cópias da mensagem

na rede. Quando uma cópia da mensagem é transmitida a outro nó, o TTL dessa cópia é

decrementado em 1. Uma cópia com TTL igual a 1 só poderá ser transmitida para o seu

destino.

Além da “criarMSG”, a procedure “habilitarTX” foi modificada de modo que a

procedure “criarRota” é invocada para todos os contatos do nó de origem, além disso ela

deve parar quando encontrar o nó destino. A procedure “criarRota” é responsável pela

sessão de anti-entropia e pelo controle do TTL.

proc criarRota { currentNode relay } {

global rota_ ns_ mensagem_ currentContacts_ destination TTL_

set now [$ns_ now]

66

if { $rota_($currentNode) == "N" && $rota_($relay) == "N" } {

if { $mensagem_($currentNode) == 1 && $mensagem_($relay) == 0 } {

if { $currentNode == $destination } {

criarAgente $currentNode $relay

set mensagem_($relay) 1

set mensagem_($currentNode) 0

} else {

if { $TTL_($currentNode) > 1 } {

criarAgente $currentNode $relay

set mensagem_($relay) 1

set TTL_($relay) [expr $TTL_($currentNode) - 1]

}

}

}

}

}

proc habilitarTX { } {

global opt ns_ habilitados_ rota_ jaEnviado_ currentContacts_ destination

set now [$ns_ now]

for {set i 0} {$i < [llength $habilitados_]} {incr i} {

set currentNode [lindex $habilitados_ $i]

set currentContacts $currentContacts_($currentNode)

quebrarRota $currentNode $currentContacts "alcance"

if { [llength $currentContacts] > 0 } {

for {set j 0} {$j < [llength $currentContacts]} {incr j} {

set relay [lindex $currentContacts $j]

if { $relay > -1 } {

if { $relay == $destination } {

criarRota $currentNode

$relay

break

} else {

67

criarRota $currentNode

$relay

}

}

}

}

}

$ns_ at [expr 0.05 + $now] "habilitarTX"

5.5 – Resultados

Nessa sessão serão exibidos os resultados obtidos nos cenários simulados. O principal fator a ser testado é a latência com que o agregado alcança o seu destino. As transmissões intermediárias também serão mostradas e comentadas de forma a ilustrar e explicar o que pôde ser visto no simulador. A latência obtida nas quatro simulações pode ser observada na tabela 5.1. A latência medida aqui é do trecho veículo – RSU.

Tabela 5.1 – Latência obtida nos testes

Novo Protocolo Protocolo Epidêmico

Teste 1 – 6 nós 9s 9,1s

Teste 2 – 28 nós 6s 4s

5.5.1 – Teste 1

Novo protocolo

Os resultados das simulações estão nos arquivos de trace no apêndice A. A

simulação no NAM mostra graficamente os mesmos resultados. O nó 0 para e solicita o

serviço de emergência aos 4s, porém como não há nenhum outro nó ao alcance, ele

armazena a solicitação em seu buffer e aguarda um veículo entrar em área de contato.

Então os nós 3 e 4 se aproximam de direções diferentes até entrarem simultaneamente ao

alcance do nó transmissor. Neste momento as métricas de 3 e 4 são comparadas com

aquela de 0, que foi alterada para o valor de 999 quando a mensagem foi originada. A

mensagem é então transmitida para o nó 4, com a menor métrica.

68

At 8.0499999999999936 currentContacts_(0) = 3 4 time_(0) = 999

At 8.0499999999999936 - Transmissao - currentNode = 0, relay = 4 (time_(4) = 4.9999999999999902)

Figura 5.7 – Nó 0 transmite para o nó 4

O nó 4 carrega a mensagem em seu buffer até entrar em contato com o destino,

onde então a mensagem é transmitida.

At 13.000000000000064 currentContacts_(4) = 1 5 time_(4) = 13.00000000000005

At 13.000000000000064 - Transmissao - currentNode = 4, relay = 1 (time_(1) = -1)

69

Figura 5.8 – Nó 4 transmite para o nó 1

Após ser entregue à RSU, uma mensagem de reply será enviada de volta ao nó 0.

A flag de modo ganancioso é ativada. No modo ganancioso, a mensagem será transmitida

para o nó geograficamente mais próximo do destino, nesse caso o nó 0. Como o nó 4 está

mais próximo do 0, a mensagem é retransmitida para ele.

Flag de Greedy Mode ativada em 13.000000000000064

At 13.100000000000065 currentContacts_(1) = 4 5 time_(1) = -1

At 13.100000000000065 - Transmissao - currentNode = 1, relay = 4

70

Figura 5.9 – Nó 1 retransmite para o nó 4 em modo ganancioso

Conforme o nó 5 se desloca em direção ao nó 0 e o nó 4 se afasta do mesmo, em

determinado momento o veículo 5 ultrapassa o detentor da mensagem e passa a deter uma

melhor métrica (menor distância). Nesse momento, a mensagem é encaminhada ao nó 5.

At 14.000000000000078 currentContacts_(4) = 1 5 time_(4) = 14.000000000000064

At 14.000000000000078 - Transmissao - currentNode = 4, relay = 5

71

Figura 5.10 – Nó 4 retransmite para o nó 5

O nó 5 então, sem mais nenhum contato ao alcance, carrega a mensagem até entrar

em contato com o nó 0 e entrega-la a seu destino.

At 17.000000000000121 currentContacts_(5) = 0 time_(5) = 14.950000000000077

At 17.000000000000121 - Transmissao - currentNode = 5, relay = 0 (time_ = 999)

72

Figura 5.11 – Nó 5 transmite para o nó 0, respondendo a requisição

Epidêmico

Assim como na sessão anterior, o resultado completo da simulação do protocolo

epidêmico para o mesmo cenário está no arquivo de trace no apêndice 2. Como a

simulação do NAM deste protocolo envolve um grande número de troca de mensagens,

é mais viável analisar apenas as trocas de mensagens conforme a saída da execução da

simulação. Todas essas saídas estão de acordo com o trace.

A simulação foi executada apenas para a mensagem com origem no nó 0 e destino

no nó 1, já que o protocolo funciona da mesma forma em ambos os sentidos. Os valores

obtidos foram os seguintes:

At 8.0999999999999801 currentContacts_(0) = {3 4} TTL = 10

At 8.0999999999999801 - Transmissao - currentNode = 0, relay = 3

At 8.1999999999999815 currentContacts_(0) = {3 4} TTL = 10

73

At 8.1999999999999815 - Transmissao - currentNode = 0, relay = 4

At 13.05000000000005 currentContacts_(4) = {1 5} TTL = 9

At 13.05000000000005 - Transmissao - currentNode = 4, relay = 1

At 18.050000000000122 currentContacts_(3) = {2} TTL = 9

At 18.050000000000122 - Transmissao - currentNode = 3, relay = 2

A mesma mensagem transmitida pelo protocolo desenvolvido neste trabalho,

obteve o seguinte desempenho:

At 8.0499999999999936 currentContacts_(0) = 3 4 time_(0) = 999

At 8.0499999999999936 - Transmissao - currentNode = 0, relay = 4 (time_(4) = 4.9999999999999902)

At 13.000000000000064 currentContacts_(4) = 1 5 time_(4) = 13.00000000000005

At 13.000000000000064 - Transmissao - currentNode = 4, relay = 1 (time_(1) = -1)

Podemos ver que o protocolo epidêmico troca um total de quatro mensagens, o

que significa quatro cópias da mesma mensagem ocupando recursos de rede. Quando o

nó 0 deseja transmitir a mensagem, ele aguarda até os nós 3 e 4 estarem ao alcance para

fazer a transmissão. Entretanto, diferentemente da simulação anterior, o protocolo

epidêmico transmite uma cópia da mensagem para ambos os nós. Verifica-se também que

o protocolo epidêmico continua transmitindo mensagens mesmo após a mesma ter

atingindo o seu destino, já que outros nós que possuem uma cópia não foram alertados

que a mensagem que carregam já foi entregue. No caso, o nó 3 transmite para o nó 5

mesmo após a mensagem ter atingido o seu destino através do nó 4 .

Por fim, vemos que a mensagem é transmitida ao destino com um atraso

ligeiramente superior no protocolo epidêmico, o que pode ser explicado com o overhead

gerado pela sessão anti-entropia.

5.5.2 – Teste 2

Novo Protocolo

Diferentemente do teste anterior, o nó 0 agora cessa o movimento aos 9s. Essa

alteração foi realizada para que quando o nó parasse já existisse um fluxo de carros

constante na via, para isso sua posição inicial foi deslocada para baixo. Apesar disso, sua

74

posição de parada é semelhante àquela do teste 1. Neste momento o veículo 4, cuja

trajetória não é a mesma do teste anterior e se desloca para baixo, já está ao alcance do

nó 0.

O nó 0 então encaminha o agregado para o nó 4 e este se desloca para cima até

entrar em contato com o RSU 2, onde o agregado é transmitido a seu destino. A seguir

segue a saída da simulação demonstrando as transmissões:

At 9.0500000000000149 currentContacts_(0) = 4 time_(0) = 999

At 9.0500000000000149 - Transmissao - currentNode = 0, relay = 4 (time_ = -1)

At 15.000000000000099 currentContacts_(4) = 2 23 time_(4) = 15.000000000000078

At 15.000000000000099 - Transmissao - currentNode = 4, relay = 2 (time_ = -1)

#Flag de Greedy Mode ativada em 15.000000000000099

Vê-se que desde o momento em que a requisição é feita até a mensagem ser

entregue ao destino, discorre-se 6s. Comparado aos 9s do teste 1, concluímos como

esperado que uma maior densidade de veículos implicará em uma menor latência.

A seguir o protocolo entra em modo ganancioso e a RSU 2 deseja enviar a resposta

de volta ao nó 0. Para isso ela possui duas opções, os nós 4 e 23 em sentidos contrários

um do outro. O nó 23 se desloca no sentido do nó 0, mas este opta pelo nó 4 por estar

mais próximo geograficamente do nó 0. Entretanto, o cenário muda apenas 0,1s depois,

quando o nó 23 “ultrapassa” o nó 4 e encurta a distância para o nó 0. Depois disso, uma

sequência de transmissões é feita seguindo a mesma lógica até que o agregado finalmente

é entregue ao nó 0, passando ao todo por oito nós intermediários.

At 15.100000000000101 currentContacts_(2) = 4 23 time_(2) = -1

At 15.100000000000101 - Transmissao - currentNode = 2, relay = 4 (time_ = 15.10000000000008)

At 15.200000000000102 currentContacts_(4) = 2 23 time_(4) = 15.200000000000081

At 15.200000000000102 - Transmissao - currentNode = 4, relay = 23 (time_ = 15.200000000000081)

At 17.000000000000128 currentContacts_(23) = 6 7 time_(23) = 15.950000000000092

At 17.000000000000128 - Transmissao - currentNode = 23, relay = 7 (time_ = 10.950000000000021)

At 17.100000000000129 currentContacts_(7) = 22 23 time_(7) = 10.950000000000021

At 17.100000000000129 - Transmissao - currentNode = 7, relay = 22 (time_ = 14.950000000000077)

At 17.200000000000131 currentContacts_(22) = 8 time_(22) = 14.950000000000077

At 17.200000000000131 - Transmissao - currentNode = 22, relay = 8 (time_ = 12.950000000000049)

At 19.000000000000156 currentContacts_(8) = 24 time_(8) = 12.950000000000049

At 19.000000000000156 - Transmissao - currentNode = 8, relay = 24 (time_ = 17.150000000000109)

At 20.000000000000171 currentContacts_(24) = 9 10 time_(24) = 17.150000000000109

At 20.000000000000171 - Transmissao - currentNode = 24, relay = 10 (time_ = 15.950000000000092)

75

At 20.100000000000172 currentContacts_(10) = 23 24 time_(10) = 15.950000000000092

At 20.100000000000172 - Transmissao - currentNode = 10, relay = 23 (time_ = 15.950000000000092)

At 20.200000000000173 currentContacts_(23) = 0 11 time_(23) = 15.950000000000092

At 20.200000000000173 - Transmissao - currentNode = 23, relay = 0 (time_ = 999)

Epidêmico

Da mesma forma em que foi realizado no teste 1, aqui somente a requisição de

emergência será vista e a resposta será deixada de lado já que o funcionamento do

protocolo é o mesmo em ambos os sentidos. Aqui, diferentemente do teste 1, o protocolo

epidêmico alcançou seu destino em pouco mais de 4s, tempo consideravelmente melhor

que o novo protocolo. Isto se deve a maior densidade de nós na rede, o que favorece o

protocolo epidêmico.

At 9.0999999999999943 currentContacts_(0) = {4} TTL = 10

At 9.0999999999999943 - Transmissao - currentNode = 0, relay = 4

At 10.050000000000008 currentContacts_(0) = {4 5 15 16} TTL = 10

At 10.050000000000008 - Transmissao - currentNode = 0, relay = 5

At 10.050000000000008 currentContacts_(4) = {0 15 16} TTL = 9

At 10.050000000000008 - Transmissao - currentNode = 4, relay = 15

At 10.150000000000009 currentContacts_(0) = {4 5 15 16} TTL = 10

At 10.150000000000009 - Transmissao - currentNode = 0, relay = 16

At 11.050000000000022 currentContacts_(4) = {18} TTL = 9

At 11.050000000000022 - Transmissao - currentNode = 4, relay = 18

At 11.050000000000022 currentContacts_(15) = {0 5 6 16} TTL = 8

At 11.050000000000022 - Transmissao - currentNode = 15, relay = 6

At 12.050000000000036 currentContacts_(4) = {19} TTL = 9

At 12.050000000000036 - Transmissao - currentNode = 4, relay = 19

At 12.050000000000036 currentContacts_(15) = {7 16} TTL = 8

At 12.050000000000036 - Transmissao - currentNode = 15, relay = 7

At 13.05000000000005 currentContacts_(4) = {17 20} TTL = 9

At 13.05000000000005 - Transmissao - currentNode = 4, relay = 17

At 13.05000000000005 currentContacts_(15) = {8 16} TTL = 8

At 13.05000000000005 - Transmissao - currentNode = 15, relay = 8

At 13.150000000000052 currentContacts_(4) = {17 20} TTL = 9

At 13.150000000000052 - Transmissao - currentNode = 4, relay = 20

At 13.150000000000052 currentContacts_(17) = {4 20 21} TTL = 8

At 13.150000000000052 - Transmissao - currentNode = 17, relay = 21

At 13.200000000000053 currentContacts_(15) = {8 9 16} TTL = 8

At 13.200000000000053 - Transmissao - currentNode = 15, relay = 9

At 13.250000000000053 currentContacts_(16) = {1 8 9 15} TTL = 9

76

At 13.250000000000053 - Transmissao - currentNode = 16, relay = 1

Entretanto, o melhor tempo se dá a um custo computacional mais elevado. Até

alcançar a RSU 1, o protocolo realizou 14 transmissões. Somada com a cópia mantida no

nó 0, são 15 cópias da mesma mensagem na rede em um mesmo tempo. Esse número

cresce ainda mais mesmo após a entrega da mensagem, como visto nos logs a seguir, onde

mais 12 transmissões são realizadas até o término da simulação aos 20s.

At 14.050000000000065 currentContacts_(4) = {21 22} TTL = 9

At 14.050000000000065 - Transmissao - currentNode = 4, relay = 22

At 14.050000000000065 currentContacts_(15) = {1 9 10 16} TTL = 8

At 14.050000000000065 - Transmissao - currentNode = 15, relay = 10

At 14.150000000000066 currentContacts_(22) = {2 4} TTL = 8

At 14.150000000000066 - Transmissao - currentNode = 22, relay = 2

At 14.200000000000067 currentContacts_(2) = {23} TTL = 7

At 14.200000000000067 - Transmissao - currentNode = 2, relay = 23

At 15.050000000000079 currentContacts_(15) = {1 11 16} TTL = 8

At 15.050000000000079 - Transmissao - currentNode = 15, relay = 11

At 16.050000000000093 currentContacts_(4) = {2 24} TTL = 9

At 16.050000000000093 - Transmissao - currentNode = 4, relay = 24

At 16.050000000000093 currentContacts_(15) = {12 13 14 16} TTL = 8

At 16.050000000000093 - Transmissao - currentNode = 15, relay = 12

At 16.150000000000095 currentContacts_(15) = {12 13 14 16} TTL = 8

At 16.150000000000095 - Transmissao - currentNode = 15, relay = 14

At 16.200000000000095 currentContacts_(4) = {2 24 25} TTL = 9

At 16.200000000000095 - Transmissao - currentNode = 4, relay = 25

At 17.050000000000107 currentContacts_(4) = {25 26} TTL = 9

At 17.050000000000107 - Transmissao - currentNode = 4, relay = 26

At 17.150000000000109 currentContacts_(26) = {3 4 27} TTL = 8

At 17.150000000000109 - Transmissao - currentNode = 26, relay = 3

At 17.25000000000011 currentContacts_(26) = {3 4 27} TTL = 8

At 17.25000000000011 - Transmissao - currentNode = 26, relay = 27

77

Capítulo 6

Conclusão

A promessa de aumento de segurança no trânsito tem sido um dos principais

incentivos ao desenvolvimento de redes veiculares. Uma miríade de aplicações foram ou

estão em desenvolvimento para melhorar a forma como nós dirigimos reduzir o risco de

acidentes. A maioria dessas aplicações prevê a interatividade entre veículos ou mesmo o

desenvolvimento de ITS (Inteligent Traffic Systems) integrados a várias formas de

transportes.

Essas aplicações não levam em conta o cenário descontínuo que pode existir em

uma rodovia e certamente não preveem os requisitos para uma comunicação eficiente

nesse cenário. Segundo dados do DNIT (Departamento Nacional de Infraestrutura de

Transportes), as estradas federais possuem alto número de acidentes fatais, enquanto em

zonas urbanas a tendência é a de um maior número de acidentes sem casualidades. Há um

dissenso então entre as necessidades reais e as aplicações propostas.

Esse trabalho apresentou não somente um novo protocolo para redes veiculares

tolerantes a atrasos, como também um cenário para estender essas aplicações às rodovias.

A instalação de uma estrutura física nessas estradas é financeiramente inviável e os

sistemas ad hoc existentes não se enquadram em meios descontínuos onde as DTNs

fazem-se necessárias. O uso de poucas RSUs espalhadas a distâncias conhecidas e

possivelmente longas, conectadas à internet ou a uma rede privada de emergência,

conectadas via DTN aos veículos que possuem hardware de prateleira podem ser uma

solução viável e barata para que ITS sejam expandidos para fora dos centros urbanos.

O novo protocolo desenvolvido é uma possível solução de roteamento para

permitir a comunicação nesse cenário hipotético. O primeiro modo de operação do

protocolo mostrou possuir baixo overhead já que mantém as informações dos nós

vizinhos em cada nó, sem precisar de uma troca de mensagens extra sempre que se deseja

transmitir um dado. Por conta desse baixo overhead, também apresentou latência

possivelmente inferior ao protocolo epidêmico, com a vantagem de possuir uma única

cópia da mensagem na rede, consumindo poucos recursos da rede.

78

O baixo consumo de recursos faz-se importante uma vez que a velocidade relativa

dos veículos em uma estrada pode ser muito alta, ocasionando intervalos pequenos para

a comunicação, já que os nós estarão ao alcance das antenas um do outro por poucos

segundos. Além disso, evita o recebimento de várias cópias da mesma mensagem no

destino, o que pode ser confundido com diversas solicitações ao invés de uma única.

Já o modo ganancioso opera de forma semelhante aos diversos protocolos

propostos na literatura. Ele é bastante eficiente quando se deseja transmitir ao longo de

um único eixo. Caso houvesse cruzamentos nessa rodovia, esse algoritmo teria sua

eficiência reduzida, já que ele leva em conta somente a posição e não a trajetória de cada

nó, o que poderia levar a loops de roteamento ou mesmo blackholes.

A desvantagem desse protocolo é a de uma sessão de comunicação só poder ser

iniciada por um veículo. Uma RSU que queira trocar mensagens com um veículo só

poderá fazê-lo se a posição do veículo constar em sua base de dados. Se levarmos em

conta que a intenção do sistema é prover somente aplicações que funcionem sob demanda

do motorista ou de seus passageiros, a desvantagem se torna uma vantagem sob o aspecto

de segurança. Não haverá requisições indesejadas e o risco de ataques serem realizados

aos veículos diminui consideravelmente.

Os cenários testados previam somente uma única mensagem sendo enviada de

cada vez em uma rodovia com densidade de veículos constante. Um trabalho futuro

poderia verificar sua escalabilidade em um cenário real com densidade de veículos

variável e múltiplas mensagens. O payload das aplicações também não foi considerado,

de forma que se mensagens de payload elevado fossem transmitidas deveria haver

fragmentação do pacote e sua reconstrução poderia incorrer em uma latência superior, já

que as partes das mensagens poderiam percorrer caminhos distintos.

Uma outra melhoria para o trabalho seria sua simulação criando-se novas classes

na hierarquia compilada, de forma a tornar a simulação mais rápida e fidedigna.

79

Bibliografia

[1] Alves, R., Campbell, I., Couto, R., Campista, M., Moraes, I., Rubinstein, M., Costa, L., Duarte, O., Abdalla, M., "Redes Veiculares: Princípios, Aplicações e Desafios", Minicursos do Simpósio Brasileiro de Redes de Computadores, pp. 199-254, Recife, 2009.

[2] VAHDAT, A., E BECKER, D. Epidemic Routing for Partially-Connected Ad Hoc

Networks. Relatório técnico, Duke University, abril de 2000. http://issg.cs.duke.edu/epidemic/epidemic.pdf.

[3] WARTHMAN, F. Delay-Tolerant Networks (DTNs): A Tutorial v1.1. Relatório

técnico, Warthman Associates, março de 2003. http://www.dtnrg.org/docs/tutorials/warthman-1.1.pdf.

[4] Alves, R., Abdesslem, F., Cavalcanti, S., Campista, M., Costa, L., Rubinstein, M.,

Amorim, M., Duarte, O., “Uma Análise Experimental da Capacidade de Redes Ad Hoc Veiculares” , XXVI Simpósio Brasileiro de Telecomunicações, Rio de Janeiro, 2008.

[5] Oliveira, C. T., Uma Proposta de Roteamento Probabilístico para Redes Tolerantes a

Atrasos e Desconexões. M.Sc. dissertation, Universidade Federal do Rio de Janeiro, Março 2008.

[6] Gass, R., Scott, J., Diot, C., “Measurements of In-Motion 802.11 Networking”. In:

Mobile Computing Systems and Applications. WMCSA '06. Proceedings. 7th IEEE Workshop, pp: 69-74, Orcas Island, 2006

[7] Evanco, W. M., The Impact of Rapid Incident Detection on Freeway Accident

Fatalities. Relatório técnico, Mitretek Center for Information Systems, junho de 2006. http://ntl.bts.gov/lib/16000/16200/16295/PB2000103371.pdf

[8] Karagiannis, G., Altintas, O., Ekici, E., Heijenk, G., Jarupan, B., Lin, K., Weil, T.,

Vehicular Networking: “A Survey and Tutorial on Requirements, Architectures, Challenges, Standards and Solutions”, Communications Surveys & Tutorials - IEEE, v. 13 pp. 584-616, 2011.

[9] Jiang, D., Delgrossi, L., IEEE 802.11p: “Towards an International Standard for

Wireless Access in Vehicular Environments”, In: Vehicular Technology Conference, IEEE, pp. 2036-2040, Singapura, 2008.

[10] Moustafa, H., Zhang, Y., Vehicular Networks: Techniques, Standards, and

Applications. Flórida, CRC Press, 2009. [11] Biswas, A., Donaldson, T., Singh, J., Diamond, S., Gauthier, D., Longford, M.,

“Assessment of mobile experience engine, the development toolkit for context aware mobile applications”. In: ACE ’06: Proceedings of the 2006 ACM SIGCHI

80

international conference on Advances in computer entertainment technology, pp. 8, New York, 2006

[12] Panayappan, R., Trivedi, J., Studer, A., Perrig, A., “VANET-based approach for

parking space availability”. In: ACM International Workshop on Vehicular Ad Hoc Networks (VANET), pp. 75–76, New York, 2007

[13] Rizvi, S., Olariu, S.,Weigle, M., Rizvi, M., “A novel approach to reduce traffic chaos

in emergency and evacuation scenarios”. In: IEEE Vehicular Technology Conference (VTC-Fall), pp. 1937–1941, Baltimore, 2007.

[14] Pelusi, L., Passarella, A., Conti, M., “Opportunistic networking: data forwarding in

disconnected mobile ad hoc networks”. Communications Magazine, IEEE, v. 44, pp. 134-141, 2006.

[15] JAIN, S., FALL, K., PATRA, R., “Routing in a Delay Tolerant Network”. In: ACM

SIGCOMM (2004), pp. 145–158, New York, 2004 [16] LINDGREN, A., DORIA, A., SCHELÉN, O., “Probabilistic Routing in

Intermittently Connected Networks”. International Workshop on Service Assurance with Partial and Intermittent Resources (SAPIR), v. 7, pp. 19-20, 2003.

[17] Juang, P., Oki, H., Wang, Y., Martonosi, M., Peh, L., Rubenstein, D., “Energy-

Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with ZebraNet”. In: ASPLOS X Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, pp. 96-107, New York, 2002.

[18] Spyropoulos, T., Psounis, K., Raghavendra, C., “Spray and wait: an efficient routing

scheme for intermittently connected mobile networks”. In: WDTN '05 Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, pp. 252-259, New York, 2005

[19] Musolesi, M., Mascolo, C., CAR: “Context-Aware Adaptive Routing for Delay-

Tolerant Mobile Networks”, Mobile Computing, IEEE Transactions on, v. 8, pp. 246-260, 2009

[20] Karimi, R., Ithnin, N., Razak, S., Najafzadeh, S., “DTN Routing Protocols for

VANETs: Issues and Approaches”, IJCSI International Journal of Computer Science Issues, v. 8, pp. 89-93, 2011

[21] Leontiadis, I., Mascolo, C., “GeOpps: Geographical Opportunistic Routing for

Vehicular Networks”, World of Wireless, Mobile and Multimedia Networks (WoWMoM), IEEE Internetional Symposium on a, v. no., pp. 1-6, 18-21, 2007.

[22] Zhao, J., Cao, G., “VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc

Networks”, Vehicular Technology, IEEE Transactions on, v. 57, pp. 1910-1922, 2008

81

[23] Cheng, P., Lee, K., Gerla, M., Härri, J., “GeoDTN+Nav: Geographic DTN Routing with Navigator Prediction for Urban Vehicular Environments”, Mobile Networks and Applications, v. 15, pp. 61-82, 2010

[24] Homepage da concessionária Triunfo CONCEPA. Disponível em:

<http://www.triunfoconcepa.com.br/home.aspx>, Acesso em: 17 fev. 2014. [25] Fall, K., Varadhan, K., The ns Manual, The VINIT Project, UC Berkley and Xerox

PARC, 2004. [26] Baumann, R., Vehicular Ad Hoc Networks - Engineering and simulation of mobile

ad hoc routing protocols for VANET on highways and in cities, M.Sc. dissertation, Swiss Federal Institute of Technology Zurich, 2004.

82

Apêndice A

Trace do Novo Protocolo

Aqui será apresentado um resumo do arquivo de trace gerado pela saída da

simulação. Devido ao tamanho (superior a 700 linhas) e à redundância das informações

contidas nele, como movimento dos nós e troca constantes e extensas de dados, optou-se

por mostrar apenas um resumo comentado nesse trabalho.

Antes de apresenta-lo, é importante frisar que as únicas trocas de informação

apresentadas neste trace são as que antecedem e realizam a troca de mensagens. As

mensagens de controle não são mostradas nesse trace por opção. Como dito na proposta,

tais mensagens são broadcasts de camada dois enviados periodicamente e recebidos por

todos os vizinhos ao alcance. Neste trace isso se refletiria em 2400 mensagens extras

((20P 50OP⁄ ) × 6(óP) enviadas e uma entrada extra para cada nó que recebesse cada

mensagem. Esse número, portanto, poluiria a saída e afastaria o foco da transmissão dos

dados no trace convencional (.tr) e seria ainda mais desastroso no NAM, onde 2400

transmissões extras seriam visíveis.

O trace é apresentado como uma tabela, onde cada linha segue o seguinte formato:

Tabela 2 - Estrutura do trace

Ação Tempo Nó Flags Nº de

sequência Tipo Tamanho [A B C D] Flags

Onde:

Ação: s – Enviado

r – Recebido

D – Descartado

f – Encaminhado

M – Movimento

Tempo: Quando o pacote foi enviado

83

Camada: AGT – Aplicação

RTR – Roteamento

LL – Camada de enlace

IFQ – Fila de saída (entre LL e MAC)

MAC – Camada MAC

PHY – Camada física

Tipo: cbr – fluxo de dados (constant bit rate)

DSR – Pacote de roteamento DSR

RTS – Request to Send, gerado por um MAC 802.11

ARP – Address Resolution Protocol

Tamanho: Tamanho do pacote na camada atual

[A B C D]: A – Duração do pacote

B – Endereço MAC de destino

C – Endereço MAC da origem

D – Protocolo de camada 2 do corpo do pacote

#Posição inicial e movimento dos nós (t = 0s):

M 0.00000 0 (975.00, 400.00, 0.00), (975.00, 1000.00), 150.00

M 0.00000 1 (875.00, 500.00, 0.00), (875.00, 500.00), 0.00

M 0.00000 2 (875.00, 2000.00, 0.00), (875.00, 2000.00), 0.00

M 0.00000 3 (1000.00, 100.00, 0.00), (1000.00, 2400.00), 100.00

M 0.00000 4 (950.00, 1900.00, 0.00), (950.00, 100.00), 100.00

M 0.00000 5 (1000.00, 45.00, 0.00), (1000.00, 2400.00), 0.00

#Movimento dos nós (posição, destino e velocidade) em t = 8s:

M 8.00000 3 (1000.00, 900.00, 0.00), (1000.00, 2400.00), 100.00

M 8.00000 4 (950.00, 1100.00, 0.00), (950.00, 100.00), 100.00

84

#No momento da primeira transmissão, o agente CBR na camada de aplicação do

nó 0 requisita às camadas inferiores uma sessão com o nó 4:

s 8.050000000 _0_ AGT --- 0 cbr 1024 [0 0 0 0] ------- [0:0 4:0 32 0] [0] 0 0

r 8.050000000 _0_ RTR --- 0 cbr 1024 [0 0 0 0] ------- [0:0 4:0 32 0] [0] 0 0

s 8.050000000 _0_ RTR --- 0 cbr 1044 [0 0 0 0] ------- [0:0 4:0 32 4] [0] 0 0

#A camada MAC do nó 0 realiza uma requisição ARP para o endereço de

broadcast “fff.fff.fff” para descobrir o endereço MAC do nó 4. A requisição é recebida

pelos nós 4 e 3:

s 8.050055000 _0_ MAC --- 0 ARP 62 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/4]

r 8.050169327 _4_ MAC --- 0 ARP 28 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/4]

r 8.050169327 _3_ MAC --- 0 ARP 28 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/4]

# O nó 4 envia a resposta ARP com o seu endereço MAC para o nó 0 de forma

unicast, que a recebe na sequência:

s 8.050224327 _4_ MAC --- 0 ARP 62 [3c 0 4 806] ------- [REPLY 4/4 0/0]

r 8.050338655 _0_ MAC --- 0 ARP 28 [3c 0 4 806] ------- [REPLY 4/4 0/0]

#O nó 0 envia uma mensagem de acknowledment:

s 8.050348655 _0_ MAC --- 0 ACK 14 [0 4 0 0]

r 8.050398982 _4_ MAC --- 0 ACK 14 [0 4 0 0]

#A mensagem é então enviada via UDP:

s 8.050668655 _0_ MAC --- 0 cbr 1078 [3c 4 0 800] ------- [0:0 4:0 32 4] [0] 0 0

r 8.052138982 _4_ MAC --- 0 cbr 1044 [3c 4 0 800] ------- [0:0 4:0 32 4] [0] 1 0

s 8.052148982 _4_ MAC --- 0 ACK 14 [0 0 4 0]

r 8.052163982 _4_ AGT --- 0 cbr 1044 [3c 4 0 800] ------- [0:0 4:0 32 4] [0] 1 0

r 8.052199309 _0_ MAC --- 0 ACK 14 [0 0 4 0]

s 8.056145536 _0_ AGT --- 1 cbr 1024 [0 0 0 0] ------- [0:0 4:0 32 0] [1] 0 0

85

r 8.056145536 _0_ RTR --- 1 cbr 1024 [0 0 0 0] ------- [0:0 4:0 32 0] [1] 0 0

(...)

s 8.148328582 _0_ AGT --- 16 cbr 1024 [0 0 0 0] ------- [0:0 4:0 32 0] [16] 0 0

r 8.148328582 _0_ RTR --- 16 cbr 1024 [0 0 0 0] ------- [0:0 4:0 32 0] [16] 0 0

s 8.148328582 _0_ RTR --- 16 cbr 1044 [0 0 0 0] ------- [0:0 4:0 32 4] [16] 0 0

s 8.148403582 _0_ MAC --- 16 cbr 1078 [3c 4 0 800] ------- [0:0 4:0 32 4] [16] 0 0

r 8.149873878 _4_ MAC --- 16 cbr 1044 [3c 4 0 800] ------- [0:0 4:0 32 4] [16] 1 0

s 8.149883878 _4_ MAC --- 0 ACK 14 [0 0 4 0]

r 8.149898878 _4_ AGT --- 16 cbr 1044 [3c 4 0 800] ------- [0:0 4:0 32 4] [16] 1 0

r 8.149934173 _0_ MAC --- 0 ACK 14 [0 0 4 0]

# O mesmo processo se repete para as demais transmissões, como na transmissão

do nó 4 para o nó 1:

M 13.00000 3 (1000.00, 1400.00, 0.00), (1000.00, 2400.00), 100.00

M 13.00000 4 (950.00, 600.00, 0.00), (950.00, 100.00), 100.00

M 13.00000 5 (1000.00, 445.00, 0.00), (1000.00, 2400.00), 100.00

s 13.000000000 _4_ AGT --- 17 cbr 1024 [0 0 0 0] ------- [4:1 1:0 32 0] [0] 0 0

r 13.000000000 _4_ RTR --- 17 cbr 1024 [0 0 0 0] ------- [4:1 1:0 32 0] [0] 0 0

s 13.000000000 _4_ RTR --- 17 cbr 1044 [0 0 0 0] ------- [4:1 1:0 32 1] [0] 0 0

s 13.000055000 _4_ MAC --- 0 ARP 62 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/1]

r 13.000169417 _1_ MAC --- 0 ARP 28 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/1]

#Nesse caso, o nó 5 está ao alcance do nó 4 e “escuta” a transmissão. Aqui pode-

se ver que o algoritmo do protocolo fez uma escolha pelo nó 1 ao invés do nó 5. Isso pode

ser concluído já que o nó 5 recebe o broadcast da requisição ARP do nó 4, o que o faria

apto a ser um possível destinatário da transmissão:

r 13.000169543 _5_ MAC --- 0 ARP 28 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/1]

s 13.000224417 _1_ MAC --- 0 ARP 62 [3c 4 1 806] ------- [REPLY 1/1 4/4]

r 13.000338833 _4_ MAC --- 0 ARP 28 [3c 4 1 806] ------- [REPLY 1/1 4/4]

s 13.000348833 _4_ MAC --- 0 ACK 14 [0 1 4 0]

r 13.000399250 _1_ MAC --- 0 ACK 14 [0 1 4 0]

#Logo em seguida, o protocolo entra em modo ganancioso e o nó 4 busca

transmitir uma resposta (que se trata de um agregado diferente) de volta ao nó 1:

86

s 13.100000000 _1_ AGT --- 34 cbr 1024 [0 0 0 0] ------- [1:1 4:2 32 0] [0] 0 0

r 13.100000000 _1_ RTR --- 34 cbr 1024 [0 0 0 0] ------- [1:1 4:2 32 0] [0] 0 0

s 13.100000000 _1_ RTR --- 34 cbr 1044 [0 0 0 0] ------- [1:1 4:2 32 4] [0] 0 0

s 13.100075000 _1_ MAC --- 34 cbr 1078 [3c 4 1 800] ------- [1:1 4:2 32 4] [0] 0 0

r 13.101545390 _4_ MAC --- 34 cbr 1044 [3c 4 1 800] ------- [1:1 4:2 32 4] [0] 1 0

s 13.101555390 _4_ MAC --- 0 ACK 14 [0 1 4 0]

r 13.101570390 _4_ AGT --- 34 cbr 1044 [3c 4 1 800] ------- [1:1 4:2 32 4] [0] 1 0

r 13.101605781 _1_ MAC --- 0 ACK 14 [0 1 4 0]

s 13.106145536 _1_ AGT --- 35 cbr 1024 [0 0 0 0] ------- [1:1 4:2 32 0] [1] 0 0

r 13.106145536 _1_ RTR --- 35 cbr 1024 [0 0 0 0] ------- [1:1 4:2 32 0] [1] 0 0

s 13.106145536 _1_ RTR --- 35 cbr 1044 [0 0 0 0] ------- [1:1 4:2 32 4] [1] 0 0

s 13.106220536 _1_ MAC --- 35 cbr 1078 [3c 4 1 800] ------- [1:1 4:2 32 4] [1] 0 0

r 13.107690925 _4_ MAC --- 35 cbr 1044 [3c 4 1 800] ------- [1:1 4:2 32 4] [1] 1 0

s 13.107700925 _4_ MAC --- 0 ACK 14 [0 1 4 0]

r 13.107715925 _4_ AGT --- 35 cbr 1044 [3c 4 1 800] ------- [1:1 4:2 32 4] [1] 1 0

r 13.107751314 _1_ MAC --- 0 ACK 14 [0 1 4 0]

# Transmissão do nó 4 para o nó 5. O nó 1 está ao alcance do nó 4 e recebe a

requisição ARP, mas o algoritmo ganancioso considera que o nó 5 está mais próximo do

destino do agregado:

M 14.00000 3 (1000.00, 1500.00, 0.00), (1000.00, 2400.00), 100.00

M 14.00000 4 (950.00, 500.00, 0.00), (950.00, 100.00), 100.00

M 14.00000 5 (1000.00, 545.00, 0.00), (1000.00, 2400.00), 100.00

s 14.000000000 _4_ AGT --- 51 cbr 1024 [0 0 0 0] ------- [4:3 5:0 32 0] [0] 0 0

r 14.000000000 _4_ RTR --- 51 cbr 1024 [0 0 0 0] ------- [4:3 5:0 32 0] [0] 0 0

s 14.000000000 _4_ RTR --- 51 cbr 1044 [0 0 0 0] ------- [4:3 5:0 32 5] [0] 0 0

s 14.000055000 _4_ MAC --- 0 ARP 62 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/5]

r 14.000169224 _5_ MAC --- 0 ARP 28 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/5]

r 14.000169250 _1_ MAC --- 0 ARP 28 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/5]

s 14.000224224 _5_ MAC --- 0 ARP 62 [3c 4 5 806] ------- [REPLY 5/5 4/4]

r 14.000338449 _4_ MAC --- 0 ARP 28 [3c 4 5 806] ------- [REPLY 5/5 4/4]

s 14.000348449 _4_ MAC --- 0 ACK 14 [0 5 4 0]

r 14.000398673 _5_ MAC --- 0 ACK 14 [0 5 4 0]

s 14.000808449 _4_ MAC --- 51 cbr 1078 [3c 5 4 800] ------- [4:3 5:0 32 5] [0] 0 0

r 14.002278673 _5_ MAC --- 51 cbr 1044 [3c 5 4 800] ------- [4:3 5:0 32 5] [0] 1 0

87

s 14.002288673 _5_ MAC --- 0 ACK 14 [0 4 5 0]

r 14.002303673 _5_ AGT --- 51 cbr 1044 [3c 5 4 800] ------- [4:3 5:0 32 5] [0] 1 0

r 14.002338898 _4_ MAC --- 0 ACK 14 [0 4 5 0]

s 14.006145536 _4_ AGT --- 52 cbr 1024 [0 0 0 0] ------- [4:3 5:0 32 0] [1] 0 0

r 14.006145536 _4_ RTR --- 52 cbr 1024 [0 0 0 0] ------- [4:3 5:0 32 0] [1] 0 0

s 14.006145536 _4_ RTR --- 52 cbr 1044 [0 0 0 0] ------- [4:3 5:0 32 5] [1] 0 0

s 14.006220536 _4_ MAC --- 52 cbr 1078 [3c 5 4 800] ------- [4:3 5:0 32 5] [1] 0 0

r 14.007690763 _5_ MAC --- 52 cbr 1044 [3c 5 4 800] ------- [4:3 5:0 32 5] [1] 1 0

#Transmissão do nó 5 para o nó 0, o agregado alcança o seu destino:

M 17.00000 3 (1000.00, 1800.00, 0.00), (1000.00, 2400.00), 100.00

M 17.00000 4 (950.00, 200.00, 0.00), (950.00, 100.00), 100.00

M 17.00000 5 (1000.00, 845.00, 0.00), (1000.00, 2400.00), 100.00

s 17.000000000 _5_ AGT --- 68 cbr 1024 [0 0 0 0] ------- [5:1 0:1 32 0] [0] 0 0

r 17.000000000 _5_ RTR --- 68 cbr 1024 [0 0 0 0] ------- [5:1 0:1 32 0] [0] 0 0

s 17.000000000 _5_ RTR --- 68 cbr 1044 [0 0 0 0] ------- [5:1 0:1 32 0] [0] 0 0

s 17.000055000 _5_ MAC --- 0 ARP 62 [0 ffffffff 5 806] ------- [REQUEST 5/5 0/0]

r 17.000169523 _0_ MAC --- 0 ARP 28 [0 ffffffff 5 806] ------- [REQUEST 5/5 0/0]

s 17.000224523 _0_ MAC --- 0 ARP 62 [3c 5 0 806] ------- [REPLY 0/0 5/5]

r 17.000339047 _5_ MAC --- 0 ARP 28 [3c 5 0 806] ------- [REPLY 0/0 5/5]

s 17.000349047 _5_ MAC --- 0 ACK 14 [0 0 5 0]

r 17.000399570 _0_ MAC --- 0 ACK 14 [0 0 5 0]

s 17.001029047 _5_ MAC --- 68 cbr 1078 [3c 0 5 800] ------- [5:1 0:1 32 0] [0] 0 0

r 17.002499570 _0_ MAC --- 68 cbr 1044 [3c 0 5 800] ------- [5:1 0:1 32 0] [0] 1 0

s 17.002509570 _0_ MAC --- 0 ACK 14 [0 5 0 0]

r 17.002524570 _0_ AGT --- 68 cbr 1044 [3c 0 5 800] ------- [5:1 0:1 32 0] [0] 1 0

r 17.002560092 _5_ MAC --- 0 ACK 14 [0 5 0 0]

s 17.006145536 _5_ AGT --- 69 cbr 1024 [0 0 0 0] ------- [5:1 0:1 32 0] [1] 0 0

r 17.006145536 _5_ RTR --- 69 cbr 1024 [0 0 0 0] ------- [5:1 0:1 32 0] [1] 0 0

s 17.006145536 _5_ RTR --- 69 cbr 1044 [0 0 0 0] ------- [5:1 0:1 32 0] [1] 0 0

s 17.006220536 _5_ MAC --- 69 cbr 1078 [3c 0 5 800] ------- [5:1 0:1 32 0] [1] 0 0

r 17.007691058 _0_ MAC --- 69 cbr 1044 [3c 0 5 800] ------- [5:1 0:1 32 0] [1] 1 0

s 17.007701058 _0_ MAC --- 0 ACK 14 [0 5 0 0]

r 17.007716058 _0_ AGT --- 69 cbr 1044 [3c 0 5 800] ------- [5:1 0:1 32 0] [1] 1 0

88

Apêndice B

Trace do Protocolo Epidêmico

Novamente será feito um resumo do trace do protocolo epidêmico onde o mais importante será mostrado, que são as trocas de mensagens. O trace segue a mesma apresentação tabular do anterior.

#Posição inicial e movimento dos nós:

M 0.00000 0 (975.00, 400.00, 0.00), (975.00, 1000.00), 150.00

M 0.00000 1 (875.00, 500.00, 0.00), (875.00, 500.00), 0.00

M 0.00000 2 (875.00, 2000.00, 0.00), (875.00, 2000.00), 0.00

M 0.00000 3 (1000.00, 100.00, 0.00), (1000.00, 2400.00), 100.00

M 0.00000 4 (950.00, 1900.00, 0.00), (950.00, 100.00), 100.00

M 0.00000 5 (1000.00, 45.00, 0.00), (1000.00, 2400.00), 0.00

#Movimento dos nós e transmissão do nó 0 para o nó 3. O nó 4 também está ao alcance

do nó 0 e recebe a requisição ARP, mas ainda não recebe o agregado:

M 8.00000 3 (1000.00, 900.00, 0.00), (1000.00, 2400.00), 100.00

M 8.00000 4 (950.00, 1100.00, 0.00), (950.00, 100.00), 100.00

s 8.100000000 _0_ AGT --- 0 cbr 1024 [0 0 0 0] ------- [0:0 3:0 32 0] [0] 0 0

r 8.100000000 _0_ RTR --- 0 cbr 1024 [0 0 0 0] ------- [0:0 3:0 32 0] [0] 0 0

s 8.100000000 _0_ RTR --- 0 cbr 1044 [0 0 0 0] ------- [0:0 3:0 32 3] [0] 0 0

s 8.100055000 _0_ MAC --- 0 ARP 62 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/3]

r 8.100169311 _4_ MAC --- 0 ARP 28 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/3]

r 8.100169311 _3_ MAC --- 0 ARP 28 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/3]

s 8.100224311 _3_ MAC --- 0 ARP 62 [3c 0 3 806] ------- [REPLY 3/3 0/0]

r 8.100338623 _0_ MAC --- 0 ARP 28 [3c 0 3 806] ------- [REPLY 3/3 0/0]

s 8.100348623 _0_ MAC --- 0 ACK 14 [0 3 0 0]

r 8.100398934 _3_ MAC --- 0 ACK 14 [0 3 0 0]

s 8.100668623 _0_ MAC --- 0 cbr 1078 [3c 3 0 800] ------- [0:0 3:0 32 3] [0] 0 0

r 8.102138934 _3_ MAC --- 0 cbr 1044 [3c 3 0 800] ------- [0:0 3:0 32 3] [0] 1 0

89

s 8.102148934 _3_ MAC --- 0 ACK 14 [0 0 3 0]

r 8.102163934 _3_ AGT --- 0 cbr 1044 [3c 3 0 800] ------- [0:0 3:0 32 3] [0] 1 0

r 8.102199244 _0_ MAC --- 0 ACK 14 [0 0 3 0]

#Transmissão da mesma mensagem do nó 0 para o nó 4. Diferentemente do novo

protocolo, o Epidêmico não precisa fazer uma escolha pelo nó de melhor métrica para

encaminhar o agregado. Uma cópia é prontamente enviada de forma unicast ao nó 4 logo

após a transmissão ao nó 3 foi finalizada. O nó 3 ainda se encontra ao alcance e recebe a

requisição ARP de 0, além de escutar a transmissão:

s 8.200000000 _0_ AGT --- 17 cbr 1024 [0 0 0 0] ------- [0:1 4:0 32 0] [0] 0 0

r 8.200000000 _0_ RTR --- 17 cbr 1024 [0 0 0 0] ------- [0:1 4:0 32 0] [0] 0 0

s 8.200000000 _0_ RTR --- 17 cbr 1044 [0 0 0 0] ------- [0:1 4:0 32 4] [0] 0 0

s 8.200264141 _0_ MAC --- 0 ARP 62 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/4]

r 8.200378421 _4_ MAC --- 0 ARP 28 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/4]

r 8.200378421 _3_ MAC --- 0 ARP 28 [0 ffffffff 0 806] ------- [REQUEST 0/0 0/4]

s 8.200433421 _4_ MAC --- 0 ARP 62 [3c 0 4 806] ------- [REPLY 4/4 0/0]

r 8.200547700 _0_ MAC --- 0 ARP 28 [3c 0 4 806] ------- [REPLY 4/4 0/0]

s 8.200557700 _0_ MAC --- 0 ACK 14 [0 4 0 0]

r 8.200607979 _4_ MAC --- 0 ACK 14 [0 4 0 0]

s 8.200897700 _0_ MAC --- 17 cbr 1078 [3c 4 0 800] ------- [0:1 4:0 32 4] [0] 0 0

r 8.202367979 _4_ MAC --- 17 cbr 1044 [3c 4 0 800] ------- [0:1 4:0 32 4] [0] 1 0

s 8.202377979 _4_ MAC --- 0 ACK 14 [0 0 4 0]

r 8.202392979 _4_ AGT --- 17 cbr 1044 [3c 4 0 800] ------- [0:1 4:0 32 4] [0] 1 0

r 8.202428258 _0_ MAC --- 0 ACK 14 [0 0 4 0]

#Por fim, a camada de aplicação do nó 4 solicita a rede para transmitir ao nó 1, seu destino

final. O broadcast da requisição ARP é escutado pelos nós 1 e 5, mas apenas o nó 1

responde com seu endereço MAC. Por se tratar do destino final do agregado, uma cópia

não será enviada ao nó 5:

M 13.00000 3 (1000.00, 1400.00, 0.00), (1000.00, 2400.00), 100.00

M 13.00000 4 (950.00, 600.00, 0.00), (950.00, 100.00), 100.00

M 13.00000 5 (1000.00, 445.00, 0.00), (1000.00, 2400.00), 100.00

s 13.050000000 _4_ AGT --- 34 cbr 1024 [0 0 0 0] ------- [4:1 1:0 32 0] [0] 0 0

r 13.050000000 _4_ RTR --- 34 cbr 1024 [0 0 0 0] ------- [4:1 1:0 32 0] [0] 0 0

90

s 13.050000000 _4_ RTR --- 34 cbr 1044 [0 0 0 0] ------- [4:1 1:0 32 1] [0] 0 0

s 13.050055000 _4_ MAC --- 0 ARP 62 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/1]

r 13.050169403 _1_ MAC --- 0 ARP 28 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/1]

r 13.050169511 _5_ MAC --- 0 ARP 28 [0 ffffffff 4 806] ------- [REQUEST 4/4 0/1]

s 13.050224403 _1_ MAC --- 0 ARP 62 [3c 4 1 806] ------- [REPLY 1/1 4/4]

r 13.050338807 _4_ MAC --- 0 ARP 28 [3c 4 1 806] ------- [REPLY 1/1 4/4]

s 13.050348807 _4_ MAC --- 0 ACK 14 [0 1 4 0]

r 13.050399210 _1_ MAC --- 0 ACK 14 [0 1 4 0]

s 13.050588807 _4_ MAC --- 34 cbr 1078 [3c 1 4 800] ------- [4:1 1:0 32 1] [0] 0 0

r 13.052059210 _1_ MAC --- 34 cbr 1044 [3c 1 4 800] ------- [4:1 1:0 32 1] [0] 1 0

s 13.052069210 _1_ MAC --- 0 ACK 14 [0 4 1 0]

r 13.052084210 _1_ AGT --- 34 cbr 1044 [3c 1 4 800] ------- [4:1 1:0 32 1] [0] 1 0

r 13.052119613 _4_ MAC --- 0 ACK 14 [0 4 1 0]

s 13.056145536 _4_ AGT --- 35 cbr 1024 [0 0 0 0] ------- [4:1 1:0 32 0] [1] 0 0

r 13.056145536 _4_ RTR --- 35 cbr 1024 [0 0 0 0] ------- [4:1 1:0 32 0] [1] 0 0

s 13.056145536 _4_ RTR --- 35 cbr 1044 [0 0 0 0] ------- [4:1 1:0 32 1] [1] 0 0

s 13.056220536 _4_ MAC --- 35 cbr 1078 [3c 1 4 800] ------- [4:1 1:0 32 1] [1] 0 0

r 13.057690938 _1_ MAC --- 35 cbr 1044 [3c 1 4 800] ------- [4:1 1:0 32 1] [1] 1 0

s 13.057700938 _1_ MAC --- 0 ACK 14 [0 4 1 0]

r 13.057715938 _1_ AGT --- 35 cbr 1044 [3c 1 4 800] ------- [4:1 1:0 32 1] [1] 1 0

r 13.057751340 _4_ MAC --- 0 ACK 14 [0 4 1 0]

#Adicionalmente, uma transmissão extra ocorre entre o nó 3 e o nó 2. Isso ocorre já que

o nó 3 ainda possui uma cópia do agregado e o nó 2 ainda não havia recebido uma cópia.

Não há nenhum outro nó escutando a transmissão, então apenas os dois nós interagem:

M 18.00000 3 (1000.00, 1900.00, 0.00), (1000.00, 2400.00), 100.00

M 18.00000 4 (950.00, 100.00, 0.00), (950.00, 100.00), 100.00

M 18.00000 5 (1000.00, 945.00, 0.00), (1000.00, 2400.00), 100.00

s 18.050000000 _3_ AGT --- 68 cbr 1024 [0 0 0 0] ------- [3:1 2:0 32 0] [0] 0 0

r 18.050000000 _3_ RTR --- 68 cbr 1024 [0 0 0 0] ------- [3:1 2:0 32 0] [0] 0 0

s 18.050000000 _3_ RTR --- 68 cbr 1044 [0 0 0 0] ------- [3:1 2:0 32 2] [0] 0 0

s 18.050055000 _3_ MAC --- 0 ARP 62 [0 ffffffff 3 806] ------- [REQUEST 3/3 0/2]

r 18.050169523 _2_ MAC --- 0 ARP 28 [0 ffffffff 3 806] ------- [REQUEST 3/3 0/2]

s 18.050224523 _2_ MAC --- 0 ARP 62 [3c 3 2 806] ------- [REPLY 2/2 3/3]

r 18.050339047 _3_ MAC --- 0 ARP 28 [3c 3 2 806] ------- [REPLY 2/2 3/3]

91

s 18.050349047 _3_ MAC --- 0 ACK 14 [0 2 3 0]

r 18.050399570 _2_ MAC --- 0 ACK 14 [0 2 3 0]

s 18.050529047 _3_ MAC --- 68 cbr 1078 [3c 2 3 800] ------- [3:1 2:0 32 2] [0] 0 0

r 18.051999570 _2_ MAC --- 68 cbr 1044 [3c 2 3 800] ------- [3:1 2:0 32 2] [0] 1 0

s 18.052009570 _2_ MAC --- 0 ACK 14 [0 3 2 0]

r 18.052024570 _2_ AGT --- 68 cbr 1044 [3c 2 3 800] ------- [3:1 2:0 32 2] [0] 1 0

r 18.052060093 _3_ MAC --- 0 ACK 14 [0 3 2 0]