Embed Size (px)
Citation preview
Universidade Federal do Rio de Janeiro
Escola Politecnica
Departamento de Eletronica e de Computacao
Um Sistema de Localizacao e Previsao de Chegada dos
Veıculos de Transporte Publico Usando Redes IEEE 802.11
Autor:
Vitor Borges Coutinho da Silva
Orientador:
Prof. Miguel Elias Mitre Campista, D.Sc.
Coorientador:
Prof. Luıs Henrique Maciel Kosmalski Costa, Dr.
Examinador:
Prof. Marcelo Goncalves Rubinstein, D.Sc.
Examinador:
Prof. Marcelo Luiz Drumond Lanza, M.Sc.
DEL
Agosto de 2013
UNIVERSIDADE FEDERAL DO RIO DE JANEIRO
Escola Politecnica - Departamento de Eletronica e de Computacao
Centro de Tecnologia, bloco H, sala H-217, Cidade Universitaria
Rio de Janeiro - RJ CEP 21949-900
Este exemplar e de propriedade da Universidade Federal do Rio de Janeiro, que
podera incluı-lo em base de dados, armazenar em computador, microfilmar ou adotar
qualquer forma de arquivamento.
E permitida a mencao, reproducao parcial ou integral e a transmissao entre bibli-
otecas deste trabalho, sem modificacao de seu texto, em qualquer meio que esteja
ou venha a ser fixado, para pesquisa academica, comentarios e citacoes, desde que
sem finalidade comercial e que seja feita a referencia bibliografica completa.
Os conceitos expressos neste trabalho sao de responsabilidade do(s) autor(es) e
do(s) orientador(es).
ii
DEDICATORIA
A minha famılia.
iii
AGRADECIMENTO
Agradeco a meu pai Julio e minha mae Ieda por sempre me apoiarem e por
investirem em minha formacao. Agradeco ainda a meus pais por minha educacao
como pessoa, pelos conselhos e pelo carinho. Agradeco a minha irma Patricia por
nao ter me ensinado a fazer brigadeiro. Brincadeiras a parte, agradeco a minha irma
por todos os conselhos e brincadeiras. Agradeco a toda minha famılia pela atencao
e carinho.
Agradeco a todos os amigos da faculdade, em especial Vitor Rosa, Vitor Antu-
nes, Nilson Carvalho, Jonathan Gois, e Alan Dantas, por tornarem a graduacao
mais divertida e agradavel. Agradeco a todos os amigos de fora da faculdade pelo
apoio e pela diversao, em especial Cristiano Barbosa, Luiza Ferreira, Pedro Freitas
e Ubirajara Ribeiro.
Agradeco a todos os professores que me deram aula, sem excecao, todos foram
essenciais a minha formacao. Agradeco a equipe do Grupo de Teleinformatica e
Automacao pelo apoio durante este trabalho. Em especial agradeco aos meus ori-
entadores Miguel Campista e Luıs Costa pela dedicacao e auxılio neste projeto.
Agradeco tambem a banca avaliadora pela atencao.
Por fim, agradeco a Deus por estar presente em minha vida.
iv
RESUMO
Atualmente, as grandes cidades sofrem com os engarrafamentos gerados pelo cres-
cente volume de veıculos nas ruas. A principal causa desse problema se deve ao uso
excessivo de meios de transporte particulares, em detrimento ao uso dos transpor-
tes publicos de massa, como onibus e trens. Esse comportamento ocorre, pois as
pessoas julgam os transportes de massa desconfortaveis e nao confiaveis o sufici-
ente. Portanto, a baixa qualidade de servico oferecida aos usuarios, os repele do
uso dos transportes publicos de massa. Com isso, cada vez mais pessoas utilizam
veıculos particulares, agravando a situacao do transito nas cidades. Uma solucao
para resolver o problema do transito e prover o alargamento das vias mais utiliza-
das, aumentando a capacidade de escoamento do transito. Contudo, essa solucao
e temporaria, visto que soluciona o sintoma do problema e nao o problema em si.
Para efetivamente solucionar o problema do transito nas grandes cidades, uma al-
ternativa e estimular a utilizacao dos transportes de massa. Todavia, para isso e
necessario aumentar a qualidade de servico oferecida aos usuarios. O presente pro-
jeto atua em favor desse aumento atraves do desenvolvimento de um sistema que
calcula e entrega informacoes de horario de chegada de onibus aos pontos de parada
aos usuarios. Os usuarios ao receberem essa informacao podem se programar para
ir ao ponto de parada apenas quando estiver perto de seu meio de transporte che-
gar, aumentando o conforto dos usuarios. Para estimar o horario de chegada dos
onibus nos pontos de parada, o sistema desenvolvido utiliza informacoes recentes do
transito. Os resultados obtidos mostram que o sistema criado e capaz de atender as
demandas de uma cidade grande como o Rio de Janeiro.
Palavras-Chave: Sistemas de Transporte Inteligente, Estimativa de Hora de Che-
gada, Localizacao Automatica de Veıculo.
v
ABSTRACT
Currently, major cities suffer from congestion generated by the growing volume of
vehicles on the streets. The main cause of this problem is due to the excessive use of
private means of transportation, rather than the use of mass public transportation
such as buses and trains. This behavior occurs because people judge mass transpor-
tation uncomfortable and not reliable enough. Therefore, the low quality of service
offered to users, repels them from the use of mass public transportation systems.
With this, more and more people use private vehicles, worsening the traffic situa-
tion in the cities. A solution to solve the traffic problem is to provide the extension
of the most used routes, increasing the flow capacity of the transit. However, this
solution is temporary, since it addresses the symptom of the problem and not the
problem itself. To effectively solve the traffic problem in big cities, an alternative is
to encourage the use of public mass transportation. However, to achieve this goal, it
is necessary to increase the quality of service offered to users. This project operates
in favor of this increase through the development of a system that calculates and
delivers bus arrival time information to users. With users recieving this informa-
tion, they can plan to go to the bus stop only when the buses are close to arrive,
increasing users comfort. To estimate the time of arrival of buses in bus stops, the
developed system uses the latest information about the traffic. The results show that
the system created is able to meet the demands of a big city like Rio de Janeiro.
Key-words: Intelligent Transportation Systems, Bus Arrival Time Estimation,
Automatic Vehicle Location.
vi
SIGLAS
API - Application Programming Interface;
APTS - Advanced Public Transportation Systems;
ARP - Analisador de Redes de Petri;
ARM - Advanced RISC Machine;
AVL - Automatic Vehicle Location;
GB - Gigabyte;
GPS - Global Positioning System;
GTA - Grupo de Teleinformatica e Automacao;
ITS - Intelligent Transportation Systems;
MB - Megabyte;
RAM - Random Access Memory;
SSID - Service Set IDentifier;
UA - Unidade de Acostamento;
UFRJ - Universidade Federal do Rio de Janeiro;
USB - Universal Serial Bus;
V2I - Vehicle-to-Infrastructure.
vii
Sumario
1 Introducao 1
1.1 Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Delimitacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.6 Organizacao do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Sistemas de Transporte Inteligente nos Meios de Transporte Publicos 5
2.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Entidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Servicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Localizacao Automatica de Veıculos . . . . . . . . . . . . . . . 7
2.3.2 Informacao ao Passageiro . . . . . . . . . . . . . . . . . . . . . 12
2.3.3 Gerenciamento de Sinalizacao de Transito . . . . . . . . . . . 13
2.3.4 Contagem Automatica de Passageiros . . . . . . . . . . . . . . 13
2.3.5 Sistema Eletronico de Cobranca . . . . . . . . . . . . . . . . . 14
2.3.6 WiFi para o Passageiro . . . . . . . . . . . . . . . . . . . . . . 14
2.3.7 TV nos Transportes . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Trabalhos Relacionados 16
3.1 Localizacao de Veıculos . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Previsao de Tempo de Chegada . . . . . . . . . . . . . . . . . . . . . 17
viii
4 Arquitetura do Sistema 20
4.1 Visao Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Entidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.1 Central . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.2 Unidade de Acostamento . . . . . . . . . . . . . . . . . . . . . 23
4.2.3 Onibus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.4 Cliente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3 Comunicacoes entre Entidades . . . . . . . . . . . . . . . . . . . . . . 24
4.4 Modelo em Rede de Petri . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Implementacao do Sistema 31
5.1 Localizacao Automatica de Veıculos . . . . . . . . . . . . . . . . . . . 32
5.1.1 Informacao dos Onibus . . . . . . . . . . . . . . . . . . . . . . 36
5.1.2 Mapa das Linhas de Onibus . . . . . . . . . . . . . . . . . . . 37
5.1.3 Intervalos entre UAs . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 Previsao de Chegada de Veıculos . . . . . . . . . . . . . . . . . . . . 45
5.2.1 Pagina de Requisicao de Estimativas . . . . . . . . . . . . . . 45
5.2.2 Calculo de Estimativas . . . . . . . . . . . . . . . . . . . . . . 45
5.2.3 Resposta aos Clientes . . . . . . . . . . . . . . . . . . . . . . . 52
5.3 Linguagens e Bibliotecas . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.4 Exemplos do Funcionamento do Sistema . . . . . . . . . . . . . . . . 54
5.4.1 Construcao Inicial de uma Linha de Onibus . . . . . . . . . . 54
5.4.2 Mudanca de Rota . . . . . . . . . . . . . . . . . . . . . . . . . 56
6 Resultados 63
6.1 Ambiente de Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2 Linhas COPPEAD e Estacao UFRJ . . . . . . . . . . . . . . . . . . . 64
6.3 Tempo de Tratamento de Mensagens de Localizacao . . . . . . . . . . 67
6.3.1 Variacao da Quantidade de Onibus . . . . . . . . . . . . . . . 68
6.3.2 Variacao da Quantidade de Linhas de Onibus . . . . . . . . . 69
6.3.3 Variacao da Quantidade de UAs em uma Linha de Onibus . . 70
6.3.4 Cenario Rio de Janeiro . . . . . . . . . . . . . . . . . . . . . . 72
7 Conclusoes e Trabalhos Futuros 74
ix
Bibliografia 76
A Propriedades da Rede de Petri 80
A.1 Descricao da Rede de Petri para Simulador ARP . . . . . . . . . . . . 80
A.2 Saıda da Analise da Rede . . . . . . . . . . . . . . . . . . . . . . . . 81
x
Lista de Figuras
2.1 Exemplo de trilateracao bidimensional. . . . . . . . . . . . . . . . . . . 9
2.2 Exemplo de triangulacao bidimensional. . . . . . . . . . . . . . . . . . . 10
4.1 Entidades do sistema na arquitetura. . . . . . . . . . . . . . . . . . . . . 22
4.2 Comunicacoes entre entidades na arquitetura. . . . . . . . . . . . . . . . 24
4.3 Rede de Petri do servico de localizacao automatica de veıculos. . . . . . . 27
4.4 Rede de Petri do servico de previsao de chegada de onibus. . . . . . . . . 28
5.1 Mensagem enviada pela UA para o onibus. . . . . . . . . . . . . . . . . 32
5.2 Mensagem enviada pelo onibus para a UA. . . . . . . . . . . . . . . . . 33
5.3 Mensagem enviada pelo onibus para a Central. . . . . . . . . . . . . . . 34
5.4 Estruturas principais simplificadas do programa da Central. . . . . . . . . 35
5.5 Fluxograma do procedimento de atualizacao dos mapas das linhas de onibus. 38
5.6 Visualizacao de mapa criado pelo programa. . . . . . . . . . . . . . . . . 42
5.7 Pagina de solicitacao de estimativa. . . . . . . . . . . . . . . . . . . . . 46
5.8 Ponto de onibus e linha de onibus selecionados. . . . . . . . . . . . . . . 47
5.9 Estimativa devolvida ao Cliente. . . . . . . . . . . . . . . . . . . . . . . 48
5.10 Mensagem de requisicao enviada pelo Cliente para a Central. . . . . . . . 48
5.11 Mudanca de rota em curso. . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.12 Linha com ciclo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.13 Criacao do mapa da linha com primeira UA. . . . . . . . . . . . . . . . . 54
5.14 Mapa apos insercao da segunda UA. . . . . . . . . . . . . . . . . . . . . 55
5.15 Mapa apos insercao da terceira UA. . . . . . . . . . . . . . . . . . . . . 55
5.16 Mapa apos insercao da quarta UA. . . . . . . . . . . . . . . . . . . . . . 56
5.17 Mapa final da linha de onibus. . . . . . . . . . . . . . . . . . . . . . . . 56
5.18 Rota inicial da linha de onibus. . . . . . . . . . . . . . . . . . . . . . . 57
xi
5.19 Onibus se move ate a UA-2. . . . . . . . . . . . . . . . . . . . . . . . . 57
5.20 Onibus alcanca a UA-5. . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.21 Onibus retorna ao ponto inicial. . . . . . . . . . . . . . . . . . . . . . . 58
5.22 Onibus chega na UA-2. . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.23 Onibus se move ate UA-5. E a mudanca na rota e concretizada. . . . . . . 59
5.24 Onibus na UA-1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.25 Onibus na UA-2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.26 Onibus na UA-5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.27 Onibus na UA-1. E exclusao de UAs 3 e 4. . . . . . . . . . . . . . . . . 61
5.28 Onibus na UA-2. Atualizacao de peso para novo maximo. . . . . . . . . . 61
5.29 Rota final da linha de onibus. . . . . . . . . . . . . . . . . . . . . . . . 61
6.1 Ambiente de testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2 Rota da linha de onibus universitaria COPPEAD. . . . . . . . . . . . . . 65
6.3 Rota da linha de onibus universitaria Estacao UFRJ. . . . . . . . . . . . 66
6.4 Variacao da quantidade de onibus no sistema. . . . . . . . . . . . . . . . 69
6.5 Variacao da quantidade de linhas de onibus no sistema. . . . . . . . . . . 70
6.6 Variacao da quantidade de UAs no sistema. . . . . . . . . . . . . . . . . 71
6.7 Cenario Rio de Janeiro. . . . . . . . . . . . . . . . . . . . . . . . . . . 72
xii
Lista de Tabelas
3.1 Tecnicas de previsao de tempo de chegada. Adaptado de [1]. . . . . . 18
6.1 Estatısticas do teste das linhas COPPEAD e Estacao UFRJ. . . . . . 67
xiii
Capıtulo 1
Introducao
As grandes metropoles mundiais vem sofrendo com engarrafamentos gerados pelo
aumento de volume de veıculos. Um numero crescente de pessoas escolhe, diaria-
mente, se locomover pela cidade atraves de meios de transporte particulares, como
carros e motos. Ao menos no Brasil, a principal justificativa e que os meios de
transporte publicos nao sao confortaveis o suficiente e que os transportes particula-
res sao mais rapidos. O problema e que essa escolha aumenta o volume do transito,
gerando mais engarrafamentos e fazendo com que mais pessoas optem pelo uso de
transportes particulares, agravando mais ainda o problema.
O problema do transito nas grandes metropoles pode ser resolvido de maneira
paliativa atraves do aumento das vias, o que ja vem sendo feito nas principais cidades
do mundo. Contudo, essa solucao nao resolve o problema, mas sim os sintomas
criados em um primeiro momento, ja que o numero de veıculos particulares continua
aumentando. De maneira mais efetiva, uma solucao que agiria sobre a fonte dos
problemas, isto e, sobre o excesso de veıculos particulares, e o estımulo do uso
dos meios de transporte publicos. Entretanto, para atrair mais passageiros para
os sistemas de transporte publicos, estes devem ser melhorados, de forma a atingir
uma qualidade maior dos servicos prestados aos usuarios, bem como uma maior
confiabilidade. Uma vez que mais pessoas utilizem os veıculos de transporte publicos,
por exemplo, os onibus, os problemas do transito na cidade serao reduzidos. Essa
melhoria e consequencia direta da maior capacidade de transporte de pessoas por
unidade de area ocupada de via, se comparado aos veıculos particulares.
1
1.1 Tema
O presente trabalho esta inserido na area de Sistemas Inteligentes de Transporte
(Intelligent Transportation Systems - ITS), mais especificamente na area de
Sistemas Avancados de Transporte Publico (Advanced Public Transportation
Systems - APTS). Os APTS vem sendo pesquisados e desenvolvidos com a intencao
de aumentar a qualidade de servico dos transportes publicos. O objetivo e atrair
mais passageiros para esses meios de transporte, reduzindo o volume de veıculos no
transito.
1.2 Delimitacao
Os meios de transporte publico usualmente seguem rotas predefinidas, exceto em
caso de acidentes, interdicao de vias ou desvios de rota realizados pelo condutor,
sejam esses intencionais ou por erro humano. Portanto, em condicoes normais de
operacao, efetuar o monitoramento dos veıculos a fim de estimar o tempo de chegada
em pontos de interesse futuros e computacionalmente viavel.
Este projeto final possui como premissa a existencia de meios de transporte publico
com rotas previamente definidas. Mais especificamente, os testes e simulacoes reali-
zados avaliam o caso dos onibus. O modelo computacional foca no monitoramento
dos veıculos em pontos de interesse. Nesses pontos, assume-se que existam equi-
pamentos IEEE 802.11 para coleta de dados e que o sistema realize a previsao de
chegada apenas para esses pontos. No caso dos onibus, os pontos de interesse sao
os pontos de onibus, onde os usuarios embarcam e desembarcam.
1.3 Justificativa
O presente projeto visa melhorar a qualidade dos transportes publicos atraves
da entrega de mais informacao acerca desses transportes aos seus usuarios. Ao
disponibilizar informacoes sobre o tempo que os proximos onibus levam para chegar
aos pontos de onibus, pode-se minimizar o tempo de espera dos usuarios. A pessoa,
ciente do horario do onibus, se programara para ir ate o ponto de onibus apenas
2
quando estiver perto do onibus desejado chegar, provendo um melhor atendimento
ao usuario.
Em outros paıses, os sistemas de previsao de chegada de transporte publico sao
comuns. No Brasil, entretanto, ainda sao poucas as cidades com iniciativas seme-
lhantes. Logo, o presente projeto visa preencher essa lacuna.
1.4 Objetivos
O objetivo e propor e desenvolver um sistema que, utilizando roteadores sem-fio
de baixo custo instalados nos onibus e nos pontos de onibus, seja capaz de rastrear
e estimar os horarios de chegada dos onibus nos pontos requisitados pelos usuarios.
Mais especificamente, sao desenvolvidos:
1. um programa para roteadores sem-fio com baixa capacidade de processamento
que informe a posicao do onibus na infraestrutura da rede;
2. um programa que centralize as informacoes dadas pelos onibus monitorando
a trajetoria e estimando os tempos nos trechos das trajetorias, e;
3. uma interface para disponibilizar a informacao gerada aos usuarios dos meios
de transporte publico.
Ao final deste projeto, pretende-se oferecer uma alternativa para solucionar o
problema da espera prolongada dos usuarios por transportes publicos nos pontos de
parada devido a falta de informacao do servico.
1.5 Metodologia
Para atender os objetivos do projeto, inicialmente, foi necessario avaliar se a arqui-
tetura proposta funcionaria corretamente. Para realizar a avaliacao, foi desenvolvido
um modelo em redes de Petri que representa, simplificadamente, a arquitetura do
sistema. Em seguida, a rede desenvolvida foi submetida a um simulador, para que
as suas propriedades, assim como possıveis problemas, fossem identificados.
3
Apos a analise, a implementacao do sistema foi iniciada, comecando pela criacao
de uma versao simplificada do programa que centralizaria a informacao dos onibus,
onde somente os envios e recebimentos de mensagem foram programados. Em se-
guida, foram criados os programas para os roteadores sem-fio necessarios para in-
formar a posicao dos veıculos. Entao, para verificar se o programa central recebia
as mensagens que indicavam a posicao dos veıculos, testes preliminares foram reali-
zados.
Apos verificar que a comunicacao entre os roteadores e o programa central estava
funcionando, o programa central foi incrementado para tratar as mensagens recebi-
das dos onibus, de forma que os onibus fossem monitorados e os tempos nos trechos
das rotas estimados.
Ao final de tudo, criou-se uma pagina da Internet. Essa pagina e a interface
grafica do sistema, na qual os usuarios podem solicitar os calculos de estimativa que
eles desejarem e ainda receber as respostas as suas solicitacoes.
Apos a realizacao das etapas anteriores, o funcionamento do sistema foi avali-
ado por meio de simulacoes. Dentre as simulacoes, foi utilizado um prototipo com
roteadores, agregando as caracterısticas dos roteadores a simulacao e, portanto,
tornando-a mais realista. Os resultados mostram que o sistema e capaz de prover o
servico de estimativa de chegada dos onibus em metropoles como o Rio de Janeiro.
1.6 Organizacao do Texto
O Capıtulo 2 aborda os Sistemas Inteligentes de Transporte, sendo apresentados
os principais servicos visados por esses sistemas. O Capıtulo 3 apresenta trabalhos
relacionados do projeto. A arquitetura proposta bem como uma visao mais geral
do sistema sao apresentadas no Capıtulo 4. No Capıtulo 5, os detalhes da imple-
mentacao do sistema e exemplos de funcionamento sao explicitados. Ja o Capıtulo 6
mostra os testes aos quais o sistema foi submetido e seus resultados. Por fim, o
Capıtulo 7 apresenta as conclusoes e os trabalhos futuros.
4
Capıtulo 2
Sistemas de Transporte Inteligente
nos Meios de Transporte Publicos
2.1 Introducao
Na cidade do Rio de Janeiro, em 2011, aproximadamente dois milhoes e meio de
veıculos compunham a frota ativa [2]. Hoje, o controle e o monitoramento do trafego
criado por essa imensa frota sao realizados por agentes de transito auxiliados por
cameras espalhadas pela cidade. Os agentes dependem da existencia dessas cameras
para visualizar o panorama do transito na cidade e tomar decisoes baseadas no que
eles veem. Contudo, algumas vezes, situacoes que podem trazer complicacoes para o
transito da cidade ocorrem fora da abrangencia dessas cameras. Alem disso, muitas
vezes sao necessarias interferencias manuais para resolver os problemas de transito,
por exemplo, o destacamento de guardas de transito nas ruas para coordenar os
semaforos em perıodos de grande fluxo de veıculos.
Uma alternativa moderna as cameras para controle de transito sao os sistemas in-
teligentes de transporte (Intelligent Transportation Systems - ITS) que reunem
as tecnologias desenvolvidas nas ultimas decadas aplicadas no cenario dos sistemas
de transporte. Essas tecnologias incluem desde sensores ate comunicacoes sem-
fio [3]. O uso dessas novas tecnologias disponibiliza mais informacao, permitindo
que as decisoes sejam tomadas com maior seguranca. Alem disso, solucoes com-
putacionais estao sendo criadas para automatizar alguns processos do sistema de
5
transporte, por exemplo, o pagamento de passagens e a contagem de passageiros, o
que alem de permitir parcialmente o gerenciamento remoto do sistema, tambem fa-
cilita e agiliza seu monitoramento. No presente trabalho, somente as solucoes de ITS
voltadas para meios de transporte publicos sao avaliadas, ou seja, apenas as solucoes
para sistemas avancados de transporte publico (Advanced Public Transportation
Systems - APTS) sao abordadas.
2.2 Entidades
A separacao por entidades e uma forma de facilitar a visualizacao dos papeis que
existem no contexto dos APTS. As entidades podem oferecer servicos para as outras
entidades e consumir os servicos criados pelas outras entidades, ou por ela propria.
Nos APTS, tres entidades podem ser distinguidas [4]: Cliente, Operador e Veıculo.
O Cliente e o principal consumidor de servicos do APTS. Neste trabalho, o Cliente
e caracterizado como uma pessoa que tem a intencao de usar os meios de transporte
publico e os servicos disponibilizados pelos Operadores do APTS.
O Veıculo e a principal fonte de informacao dos APTS. O Veıculo e tambem o
local onde alguns dos servicos criados pelos Operadores sao disponibilizados para os
Clientes. Usualmente, os Veıculos realizam o sensoriamento de informacoes como
posicao geografica, numero de passageiros em seu interior, velocidade, quantidade
de combustıvel, consumo de combustıvel, entre outras.
Os Operadores sao as empresas publicas ou privadas que atraves do processamento
das informacoes recebidas dos Veıculos e de outras origens externas ao sistema ofere-
cem servicos ou monitoram e controlam o sistema de transporte. As fontes externas
sao necessarias, pois fatores fora do sistema podem influenciar muito no transito
urbano. Por exemplo, em dias de chuva intensa o transito geralmente fica mais
lento, ja que o condutor e forcado a reduzir a velocidade e aumentar a distancia de
seguranca frontal, ou seja, a distancia ate o veıculo a sua frente.
6
2.3 Servicos
De maneira geral, os ITS tratam o gerenciamento do transito como um todo.
Contudo, como ja mencionado, este trabalho se restringe a avaliar os ITS somente
no contexto dos meios de transporte publicos. Nesse cenario especıfico, os benefıcios
dos ITS se estendem desde os usuarios ate as empresas que realizam o transporte em
si. Os benefıcios sao fruto dos servicos prestados pelos operadores, sejam os servicos
para atender os requisitos dos usuarios, sejam eles para atender as demandas das
empresas. Nesta secao, os servicos mais importantes providos pelos sistemas de
transportes inteligentes sao brevemente descritos.
2.3.1 Localizacao Automatica de Veıculos
Quando nao se utilizam sistemas de localizacao automatica de veıculos, o monito-
ramento dos veıculos, e consequentemente do transito, e realizado tendo como base
imagens obtidas por cameras espalhadas pela cidade em um processo nao automa-
tizado. Tal fato prejudica a granularidade da informacao obtida pelos sistemas de
monitoramento tradicionais sobre a distribuicao e posicionamento dos veıculos na
cidade. Um servico de Localizacao Automatica de Veıculos (Automatic Vehicle
Location - AVL), quando utilizado, possibilita uma granularidade superior da in-
formacao, permitindo aos ITS avaliar melhor a real situacao do transito na cidade,
e com isso tomar decisoes mais seguras e melhores.
O conhecimento da posicao de cada veıculo cria, ainda, a possibilidade de novos
servicos serem oferecidos aos usuarios dos transportes publicos, por exemplo, um
servico de distribuicao de conteudos baseado na posicao dos veıculos. Nesse sistema
seriam transmitidos notıcias do bairro ou outros assuntos de interesse da regiao
ao onibus, onde poderiam ser vistos pelos usuarios em televisores instalados nos
veıculos.
O primeiro passo para a construcao de um sistema AVL e determinar a localizacao
geografica do veıculo. Existem diversos metodos para localizar um dado objeto no
espaco, e eles se dividem basicamente em tres grandes areas [5] que serao explicadas
posteriormente:
7
• radio localizacao;
• dead reckoning ;
• localizacao por proximidade.
O segundo passo para a construcao de um sistema de localizacao automatica de
veıculos para sistemas inteligentes de transporte e enviar a informacao da localizacao
do veıculo obtida para os Operadores, para que estes usem a informacao para moni-
torar os veıculos ou ainda criar novos servicos com base na informacao disponıvel. As
redes mais usadas para disponibilizar essa informacao sao as redes celulares moveis,
atraves do uso do 3G e do 4G; e as redes sem-fio, atraves do uso de pontos de acesso
com o padrao IEEE 802.11 distribuıdos pela cidade.
2.3.1.1 Radio localizacao
Os sistemas de localizacao via radio podem ser classificados como unilaterais e
multilaterais.
Os sistemas de localizacao via radio unilaterais, de maneira geral, utilizam si-
nais de radiofrequencia de diferentes fontes conhecidas para determinar a posicao
geografica de um no em relacao as fontes. Os sinais de radio sao recebidos pelo no
a ser localizado, e quando isso ocorre, ele calcula a distancia dele ate cada uma das
fontes emissoras dos sinais recebidos. Apos o calculo das distancias, sera realizado
um processamento conhecido como trilateracao para determinar de fato a posicao
do no em relacao as fontes dos sinais.
A tecnica de trilateracao se baseia em um princıpio geometrico e nas distancias
entre o no a ser localizado e as fontes de sinal. O princıpio geometrico usado na
trilateracao se baseia na ideia da circunferencia, que e o lugar geometrico em que
todos os pontos de um plano que se localizam a uma mesma distancia de um ponto
fixo, denominado o centro da circunferencia, recaem.
Usando o princıpio citado e a informacao da distancia entre o no e a fonte de
um sinal, pode-se tracar uma circunferencia com raio igual a distancia calculada e
8
Fonte 1
R1
Fonte 2
R2
Fonte 3
R3
Figura 2.1: Exemplo de trilateracao bidimensional.
o centro na posicao da fonte de sinal. A circunferencia tracada representa, entao,
todos os possıveis pontos que o no pode estar em relacao a posicao da fonte do
sinal. Se o procedimento anterior for aplicado para duas fontes de sinal distintas,
passam a existir duas circunferencias interceptando a posicao real do no. Como
as circunferencias nao sao coincidentes, existirao no maximo dois pontos possıveis
nos quais as circunferencias se interceptam, esses pontos representam os pontos do
espaco onde o no pode estar. Entao, para determinar com certeza a posicao do no
no espaco bidimensional, e necessario aplicar o procedimento mais uma vez, para
uma terceira fonte distinta, o que ira determinar qual dos dois pontos anteriores
era a localizacao real do no. Como existem erros associados as distancias medidas,
no final do procedimento ao inves de obter-se um ponto exato, obtem-se uma area
na intersecao das tres circunferencias, representando as posicoes geograficas mais
provaveis de se encontrar o no, como ilustrado na Figura 2.1.
O processo descrito anteriormente se trata da localizacao de um objeto em um
plano para um sistema unilateral. Entretanto, o processo pode ser facilmente es-
tendido para a localizacao de um objeto no espaco tridimensional, bastando para
isso utilizar esferas ao inves de circunferencias e quatro fontes distintas de sinal ao
inves de tres. A localizacao efetuada e em relacao as fontes de sinal usadas, no
caso especıfico em que essas fontes estao fixas em uma posicao conhecida do espaco,
como latitude e longitude, ou se movem em uma trajetoria pre-estabelecida. Ao
9
Receptor 1
Receptor 2
Receptor 3
Figura 2.2: Exemplo de triangulacao bidimensional.
determinar-se a posicao em relacao as fontes, determina-se tambem a posicao em
relacao a Terra.
Nos sistemas de localizacao via radio multilaterais, ao inves de o no a ser localizado
receber sinais de diferentes fontes conhecidas para determinar sua posicao geografica,
diversos receptores de posicao geografica conhecida recebem um sinal transmitido
pelo no e atraves das diferencas na recepcao desse sinal os receptores calculam a
posicao do no. A tecnica usada nesses sistemas para localizar o no no espaco e a
triangulacao.
A triangulacao se baseia na medicao de angulos ao inves da medicao de distancias.
Na triangulacao, os receptores devem descobrir a direcao de onde o sinal recebido
partiu. Duas linhas de direcao distintas definem um ponto, mas como sempre exis-
tem erros nas medicoes, uma terceira linha de direcao deve ser usada para definir a
posicao do no como uma area, um triangulo, que abrange os locais mais provaveis
do no estar, como ilustrado na Figura 2.2.
Diversos processos conhecidos e estabelecidos usam a radio localizacao, entre eles
estao o GPS e sistemas de localizacao usando torres de telefonia movel. O GPS e
um exemplo de sistema unilateral, enquanto que os sistemas que usam as torres de
telefonia movel sao multilaterais.
10
2.3.1.2 Dead reckoning
Nessa tecnica, a posicao do ponto de origem do objeto rastreado e conhecida, ela
e a condicao inicial do sistema. A partir desse ponto, sensores no proprio objeto
rastreiam os movimentos. Assim, as informacoes de distancia percorrida e direcao
sao sensoriadas permitindo que a localizacao do objeto seja conhecida em relacao a
origem a todo o momento.
A vantagem dessa abordagem e que o objeto nao depende de nenhum elemento
externo alem da condicao inicial para se localizar. A condicao inicial, por sua vez,
geralmente e dada por um sistema de radio localizacao, como o GPS. O grande
problema desses sistemas e o acumulo de erro. Especificamente para o caso de um
veıculo, se a distancia percorrida for calculada no veıculo usando um odometro, o
raio das rodas deve ser constante. Todavia, isso nao acontece sempre, pois o raio das
rodas varia com mudancas de temperatura, com mudancas no peso dos veıculos e
com o esvaziamento das proprias rodas, que acontece com o tempo. Essas variacoes
se acumulam a cada rotacao das rodas, produzindo erros no calculo da distancia.
Mesmo no caso de serem utilizados acelerometros, a acumulacao de erro acontece.
Os erros citados podem ser reduzidos se existirem outras referencias no percurso
dos veıculos. Referencias adicionais limitam o acumulo dos erros de integracao ao
trecho entre duas referencias, ja que ao alcancar uma nova referencia descarta-se o
erro acumulado.
Sistemas de navegacao inercial sao sistemas que se baseiam na tecnica Dead rec-
koning e que utilizam giroscopios em conjunto com os acelerometros. Esses sistemas
estao presentes em avioes modernos e sao usados quando os sistemas dependentes
de fatores externos param de funcionar. Isso e realizado para que ainda seja possıvel
estimar a posicao dos avioes em casos de pane.
2.3.1.3 Localizacao por proximidade
Nos sistemas que efetuam localizacao por proximidade a posicao do objeto e deter-
minada descobrindo qual e o dispositivo de controle mais proximo do objeto. Nesses
sistemas, dispositivos de controle sao espalhados estrategicamente pela cidade, nos
11
pontos de interesse onde se quer descobrir a localizacao do objeto. Os dispositivos
de controle podem ser ativos ou passivos, variando desde sensores magneticos ou
oticos espalhados pela cidade, ate radios transmissores e receptores.
Os metodos de localizacao por proximidade podem funcionar de formas distintas.
O objeto pode possuir um papel ativo ou passivo na sua localizacao. Quando o
objeto possui papel ativo, ele determina sua propria posicao em relacao a rede de
sensores espalhada. Nesse caso os sensores da rede emitem periodicamente algum
tipo de mensagem com sua identificacao, e o objeto descobre sua posicao na rede de
sensores ouvindo o canal de comunicacao em busca dessas mensagens. No caso de
o objeto possuir papel passivo na sua localizacao, e o objeto que emite mensagens
periodicamente com sua identificacao, sendo a rede de sensores responsavel por
escutar o canal em busca dessas mensagens, localizando o objeto.
A forma de localizacao utilizada neste trabalho e a localizacao por proximidade,
com o veıculo possuindo papel ativo na sua localizacao. A localizacao por proximi-
dade e escolhida por possibilitar o uso de um mesmo tipo de dispositivo na fase de
localizacao do veıculo e na fase do envio de informacao aos Operadores. Isso reduz
a complexidade e o custo do sistema em relacao as outras formas de localizacao,
que precisam de um tipo de dispositivo na fase de localizacao e outro na fase do
envio de informacao aos Operadores. Escolheu-se fazer o veıculo possuir papel ativo
em sua localizacao, pois essa forma e mais simples de ser aplicada no cenario deste
trabalho. Neste projeto os dispositivos utilizados sao roteadores sem-fio.
2.3.2 Informacao ao Passageiro
Os clientes dos transportes publicos, hoje, nao tem informacoes acerca do trans-
porte a sua disposicao. Utilizando os APTS, os clientes podem ter acesso a in-
formacoes como estimativa para o transporte desejado chegar onde o cliente esta ou
mesmo no destino e numero de passageiros nos veıculos. As estimativas sao possıveis
gracas ao servico de localizacao automatica de veıculos, que permite que os clientes
saibam quando o transporte ira chegar e nao percam tempo desnecessariamente.
O numero de passageiros nos veıculos pode ser usado pelos clientes para decidir se
12
devem ir para o ponto de onibus ou se devem aguardar um transporte mais vazio.
Essas informacoes ajudam o cliente a se programar, e aumentam a confiabilidade
dos sistemas de transporte publicos.
2.3.3 Gerenciamento de Sinalizacao de Transito
O gerenciamento de sinalizacao de transito entrega aos operadores um poder maior
para atacar os problemas do transito. Nesse tipo de controle, os operadores podem
modificar os intervalos de abertura e fechamento de semaforos, aumentando ou di-
minuindo a prioridade dos fluxos de veıculos das vias. Por exemplo, suponha que
em um cruzamento, uma via esteja com trafego maior que o da outra via do cru-
zamento. Nesse caso, os operadores podem modificar os intervalos de abertura e
fechamento dos semaforos do cruzamento, aumentando o tempo que a via congesti-
onada permanece com o sinal aberto. Como consequencia, o intervalo de tempo que
a via com transito menos intenso permanece fechada aumenta, permitindo um maior
escoamento do trafego. Outro possıvel uso para esse servico seria no caso da pre-
senca de um veıculo com prioridade, por exemplo, ambulancias, carros do corpo de
bombeiros ou da polıcia. Nesse cenario, o operador poderia controlar os semaforos
de forma a agilizar a chegada desses veıculos em seus destinos. De forma similar, o
presente servico tambem pode ser utilizado para priorizar vias com maior numero
de veıculos de transporte publico. O servico de gerenciamento das sinalizacoes de
transito pode ser automatizado, sendo os intervalos de abertura e fechamento dos
sinais controlados por computadores [6].
2.3.4 Contagem Automatica de Passageiros
Atraves de sensores dentro dos veıculos, e possıvel contabilizar o numero de pes-
soas dentro deles de forma automatica. Esse servico e interessante tanto para as
empresas que oferecem transportes publicos quanto para o publico que utiliza essa
forma de transporte. Para o primeiro grupo, o servico oferece uma forma de controlar
os ganhos e obter estatısticas, como o numero de pessoas que utilizam as diferentes
linhas de onibus da empresa nas diferentes horas do dia. Com isso a empresa poderia
realocar seus onibus para as linhas mais usadas no momento, aumentando sua qua-
lidade de servico. O aumento da qualidade beneficia diretamente o segundo grupo,
13
ou seja, os usuarios. Alem disso, se o numero de passageiros dentro dos veıculos for
divulgado, os usuarios poderao escolher esperar por onibus mais vazios.
2.3.5 Sistema Eletronico de Cobranca
O servico de cobranca eletronica ja esta disponıvel em todos os onibus da cidade
do Rio de Janeiro. Com esse servico, o usuario compra ou recarrega um cartao
inteligente com um determinado saldo, e ao entrar no veıculo, passa o cartao em um
dispositivo eletronico que desconta o valor da passagem do saldo presente no cartao.
Esse servico facilita o controle financeiro das empresas de onibus; torna os onibus
menos suscetıveis a assaltos para roubo do dinheiro em posse do trocador; aumenta
a velocidade da cobranca dos passageiros, pois o passageiro nao precisa receber o
troco; viabiliza a existencia de sistemas como o Bilhete Unico Carioca, que prove
descontos aos usuarios que precisam utilizar mais de um onibus num curto intervalo
de tempo; e ainda permite ao usuario visualizar o historico de operacoes que ele
efetuou [7].
2.3.6 WiFi para o Passageiro
As pessoas desejam estar conectadas em rede a todo o momento e em qualquer
lugar. Essa premissa nao deve ser diferente no interior de meios de transporte
publicos. Atualmente, alguns passageiros ja acessam a Internet por meio de redes
celulares 3G ou 4G. Porem, ao oferecer o servico de internet sem-fio ao passageiro
usando o padrao IEEE 802.11, pode-se aumentar a razao dado obtido por energia
consumida [8], o que e de primordial importancia para o usuario caso ele esteja
usando um smartphone ou um tablet para acessar a Internet. Alem da vantagem
energetica para o usuario, com a disponibilizacao desse servico gratuitamente, o
custo do acesso a Internet dos usuarios diminuiria. Logo, oferecer servico de acesso
a Internet dentro dos veıculos, aumenta a qualidade do servico prestado e o conforto
do passageiro, o que atrai mais pessoas para o transporte publico.
14
2.3.7 TV nos Transportes
Outro servico voltado para o aumento da qualidade de servico e do conforto do
passageiro e o uso de televisoes nos meios de transporte. Inserir televisoes nos
meios de transportes e uma forma de manter o cliente informado, entrete-lo, tornar
seu tempo gasto no transito uma experiencia menos estressante. Esse servico pode
ser financiado por propagandas veiculadas no proprio televisor, inclusive algumas
empresas de onibus da cidade do Rio de Janeiro ja oferecem esse servico [9].
2.4 Conclusao
Neste capıtulo foram apresentados os principais servicos dos ITS relacionados aos
meios de transporte publicos. Este projeto propoe um servico de informacao ao
passageiro, onde a previsao de chegada dos onibus e divulgada. Alem disso, como o
calculo da previsao de chegada de um veıculo requer o conhecimento da localizacao
dele, um sistema de localizacao automatica de veıculo tambem e desenvolvido. O
proximo capıtulo apresenta os trabalhos relacionados ao projeto.
15
Capıtulo 3
Trabalhos Relacionados
Neste capıtulo, os trabalhos relacionados ao projeto sao apresentados.
3.1 Localizacao de Veıculos
A localizacao de veıculos e um tema estudado ha muitos anos no contexto de ITS.
Como ja enunciado no capıtulo anterior, existem diversas tecnicas de rastreamento
de veıculos.
Muitos trabalhos na area de sistemas de transporte inteligentes utilizam a loca-
lizacao por meio de GPS, devido a grande acuracia alcancada por esses sistemas.
Contudo, sistemas de GPS exigem equipamentos especializados, e no contexto de
ITS, exigem que alguma tecnologia de comunicacao seja acoplada ao modulo GPS
para que a informacao da posicao do veıculo seja divulgada. Essa combinacao torna
o sistema mais complexo e custoso.
Em oposicao ao uso comum do GPS, tecnicas de localizacao que utilizam as
proprias tecnologias de comunicacao para localizar os veıculos vem sendo estudadas.
Uma das vantagens do uso desses sistemas e que, alem de prover a localizacao dos
veıculos, as redes criadas poderiam ser utilizadas para outros fins. Os sistemas mais
simples de localizacao desse tipo funcionam como sistemas de localizacao por proxi-
midade, sendo a localizacao do veıculo dada apenas pela informacao sobre qual no
da rede ele esta conectado. Em [10], e proposto um sistema que utiliza a tecnologia
de comunicacao sem-fio ZigBee para localizar onibus. A vantagem da proposta e
16
o custo da tecnologia ZigBee ser baixo. Porem, para disseminar a informacao da
localizacao dos onibus utilizou-se outra rede, a GPRS, o que acaba por tornar o
sistema mais complexo e custoso. O ideal seria utilizar a tecnologia de comunicacao
escolhida para localizar e disseminar a informacao criada.
A precisao dos sistemas de localizacao que usam tecnologias de comunicacao des-
critos ate agora e inferior a apresentada pelos sistemas de posicionamento via satelite.
Contudo, tecnicas para aumentar a precisao desses sistemas vem sendo propostas.
Por exemplo, em [11], o veıculo alvo mede a potencia do sinal recebido de varios
pontos de acesso em seu entorno, e atraves de uma rede neural criada e calibrada no
trabalho, realiza o posicionamento do veıculo. Os resultados do trabalho mostram
que o sistema criado obteve erros medios quadraticos de 7,02 metros. Esse resultado
se aproxima do alcancado por sistemas de posicionamento via satelite, que e de 4
metros [12]. O ponto fraco dessa forma de posicionamento esta na calibracao da
rede neural, que e um processo longo para uma cidade inteira.
3.2 Previsao de Tempo de Chegada
A partir dos dados entregues por sistemas de localizacao, pode-se prever o tempo
que um dado veıculo chegara a um lugar especıfico. As tecnicas para o calculo das
previsoes vem sendo amplamente estudadas, ja que essas previsoes sao usadas em
sistemas inteligentes de transporte, aumentando a confiabilidade desses sistemas.
As principais tecnicas para calcular as previsoes podem ser vistas na Tabela 3.1.
Os metodos baseados em dados de historico preveem o tempo de chegada de
acordo com informacoes de dias anteriores, semanas e ate meses [13]. A partir des-
sas informacoes, uma media das informacoes passadas e realizada, de dados que
pertencem ao mesmo perıodo de um mesmo dia da semana. Essas estimativas fun-
cionam bem em circunstancias esperadas, mas nao modelam situacoes nao cıclicas,
como acidentes. Alem disso, um volume de informacoes passadas muito grande e
necessario para que essa tecnica seja implantada.
17
Tabela 3.1: Tecnicas de previsao de tempo de chegada. Adaptado de [1].
Tecnica Autor(es) Comentarios
Metodos comManolis e Kwstis [13]
Preve o tempo de viagem em um tempobase em dados particular como o tempo medio de viagemde historico para o mesmo perıodo historicamente.Abordagem de Lin e Zeng [14], Assume que o tempotempo real Karbassi e Barth [15] futuro de viagem sera o
mesmo que o do presente.Analise de D’Angelo et al. [16], Assume que padroes historicos seseries temporais Ishak e Al-Deek [17] manterao no futuro segundo um modelo.Modelos de Rice e van Zwet [18], Preve a variavel dependente baseadaregressao Frechette e Khan [19] numa funcao formada por um
conjunto de variaveis independentes.Tecnicas de Chien et al. [20], Previsao baseada em dadosinteligencia Vanajakshi e Rilett [21], de exemplo. Necessario um grandeartificial Jeong e Rilett [22] banco de dados para previsao acurada.Abordagem Vanajakshi et al. [23], Estabelece relacionamentos entre as variaveisbaseada Shalaby e Farhan [24] e corrobora usando observacoes em campo.em modelo Nao e especıfico para regiao ou dados.
Ao contrario dos metodos baseados em dados de historico, as abordagens de tempo
real utilizam apenas as informacoes do proprio dia, modelando melhor situacoes
particulares do dia, como acidentes. As abordagens de tempo real basicamente
assumem que o tempo que um dado veıculo leva em um dado percurso e igual ao
tempo que um outro veıculo que ja fez esse trajeto levou [14]. A desvantagem desses
metodos e que eles sao muito afetados por perdas dos dados, por exemplo, devido a
falha de equipamentos ou perdas na recepcao[1].
Assim como os metodos baseados em dados de historico, modelos de series tem-
porais assumem que o padrao do transito se mantera historicamente. Contudo, essa
forma de previsao relaciona os dados de historico com as estimativas atraves de mo-
delos [16], possivelmente nao lineares, e nao atraves de medias. Com isso, variacoes
nos dados historicos ou mudancas no relacionamento entre os dados historicos e o
tempo real podem causar pouca precisao nas previsoes resultantes [16].
Diferentemente das tecnicas citadas anteriormente, as tecnicas que utilizam mo-
delos de regressao nao assumem que o transito depende de dados passados. Essas
tecnicas realizam a previsao atraves de um conjunto de variaveis independentes es-
colhidas para modelar o transito. O problema desses modelos e que nos sistemas
18
de transporte as variaveis sao muito intercorrelacionadas, limitando a aplicacao da
tecnica [20].
Outros metodos baseados em modelos tem sido estudados bastante por nao serem
especıficos para uma regiao. Dentre esses metodos, se destacam os que utilizam
filtros de Kalman, pois estes tem o potencial de se adaptar as flutuacoes do transito
com parametros dependentes do tempo [25]. Contudo quando os dados de localizacao
sao temporalmente esparsos, essa abordagem nao funciona bem [15].
Por ser difıcil modelar matematicamente o comportamento do transito, metodos
que usam inteligencia artificial vem sendo desenvolvidos. Esses metodos geralmente
utilizam redes neurais criadas para realizar as previsoes. Isso e feito devido as suas
habilidades de resolver relacionamentos nao lineares complexos e emular o processo
de aprendizagem do cerebro humano [25]. O principal problema dessas tecnicas e
a necessidade de enormes quantidades de informacao no processo de aprendizagem
das redes [1].
Neste projeto de conclusao de curso, os dados de localizacao sao esparsos, ja que
a posicao dos veıculos somente e conhecida nos pontos de acesso espalhados pela
via. Alem disso, nao ha uma base de dados com informacoes de localizacao antigas.
Devido a essas restricoes, neste projeto, a tecnica usada para previsao de tempo de
chegada e a de tempo real.
19
Capıtulo 4
Arquitetura do Sistema
4.1 Visao Geral
O trabalho desenvolvido divide-se em duas partes. A primeira e um servico de ITS
de localizacao automatica, ja que nao precisa de uma ordem explıcita para localizar
um veıculo. A segunda e um servico de ITS de estimativa de chegada de onibus aos
pontos de parada que se baseia em informacoes da primeira parte.
A localizacao automatica de veıculos desenvolvida tem foco em veıculos de trans-
portes publicos, mais especificamente em onibus, mas pode ser estendida para outros
veıculos. O cenario da aplicacao e o de redes veiculares e o servico se baseia na tecnica
de localizacao por proximidade, onde a localizacao por proximidade e realizada em
relacao a pontos de acesso espalhados pela via. O onibus ao se aproximar de um
desses pontos de acesso, se conecta a ele. Em seguida, ocorre uma troca de men-
sagens, onde o onibus se identifica para o ponto de acesso e vice-versa. Terminada
a troca de mensagens anterior, o onibus envia uma mensagem a um computador
central informando a qual ponto de acesso ele esta conectado.
Ao localizarem-se os onibus em relacao aos pontos de onibus e sabendo a rota que
os onibus de uma determinada linha percorrem, pode-se oferecer o servico de estima-
tiva de horario de chegada de onibus em todos os pontos de onibus. Basta, para isso,
criar um mapa das linhas de onibus, a partir das informacoes da posicao dos onibus
em relacao aos pontos de parada, e usar esse mapa em conjunto com o historico de
perıodos que os onibus demoram entre dois pontos de parada consecutivos da linha.
20
O conhecimento do mapa da linha de onibus e essencial para o servico de estimacao
de hora de chegada. A abordagem inicial, para suprir essa necessidade, e supor que
a rota dos onibus nao se altera nunca, e com isso a rota das linhas de onibus e
armazenada em um arquivo que e lido sempre que necessario. Porem, essa suposicao
pode falhar, caso mudancas temporarias na rota ocorram, por exemplo, em caso
de fechamento de uma via devido a um acidente. Esse problema ja havia sido
percebido nos trabalhos [26] e [27] anteriores e nao havia sido abordado. Por isso,
neste trabalho, os mapas das linhas de onibus serao criados dinamicamente, com o
intuito de evitar os problemas levantados nos trabalhos anteriores.
4.2 Entidades
No sistema, existem quatro entidades, sao elas:
• Central;
• Unidade de Acostamento (UA);
• Onibus;
• Cliente.
Pode-se estabelecer uma relacao entre as entidades do sistema, mencionadas acima,
e as entidades dos APTS citadas no Capıtulo 2. As entidades do sistema Central e
Unidade de Acostamento sao gerenciadas por um Operador, por exemplo, a secreta-
ria de transporte da cidade onde o sistema esta sendo instalado, outra organizacao
governamental ou ainda uma empresa privada. A entidade Onibus do sistema cor-
responde a entidade Veıculo caracterizada no Capıtulo 2, e a entidade Cliente do
sistema corresponde a entidade Cliente do Capıtulo 2. As entidades do sistema estao
ilustradas na Figura 4.1.
4.2.1 Central
A Central e um computador que executa o programa principal do sistema. A
Central possui todas as informacoes do sistema, os mapas criados dinamicamente,
os dados da localizacao de cada veıculo e os historicos dos tempos entre dois pontos
21
Internet
Central Unidade de Acostamento
ClienteÔnibus
Figura 4.1: Entidades do sistema na arquitetura.
consecutivos. Historicos esses que sao usados para oferecer estimativas sobre as che-
gadas dos onibus aos Clientes. O pseudocodigo simplificado do programa executado
na Central pode ser visto a seguir:
Entrada: mensagem "m" recebida do onibus "b" servindo a linha "l"
Lista de Onibus: B
// Cada linha de onibus contem o seu mapa, que e uma sequencia de UAs.
Lista de Linhas de Onibus: L
// T associa um trecho da linha de onibus ao tempo gasto para percorre-lo
Mapa Associativo <Trecho, Tempo> T
Busca b em B
Se achou b E b n~ao mudou de linha E mensagem anterior foi recebida
Armazena tempo gasto no trecho entre a UA anterior e a UA atual em T
Se n~ao achou b
Cria onibus e adiciona em B
Atualiza informac~ao de localizac~ao do onibus b com as UAs de m
Busca linha de b em L
Se achou a linha l
Atualiza o mapa da linha l usando as UAs de m
Sen~ao
Cria mapa da linha l usando a UA atual como ponto inicial
Se a linha l n~ao e circular
Para cada onibus cadastrado b’ servindo a linha l faca
Enquanto o onibus b’ n~ao esta no ponto final faca
Acumule o tempo gasto por b’ no trecho da ultima UA ate a atual
// No fim do calculo a estimativa de cada UA deve ser a mınima,
// representando o tempo para o onibus mais proximo chegar na UA.
Se estimativa do onibus b’ chegar < estimativa da UA atual
estimativa da UA atual = estimativa do onibus b’ chegar
Move o onibus b’ para a proxima UA da linha l
22
4.2.2 Unidade de Acostamento
No sistema existem varias Unidades de Acostamento. As UAs sao os pontos de
acesso posicionados na cidade, oferecendo redes sem-fio com identificadores (Service
Set Identifier - SSID) pre-fixados e iguais. Essa premissa e necessaria para que os
roteadores inseridos dentro dos onibus possam facilmente identificar e se conectar
a rede de acesso. As UAs tem papel fundamental tanto na localizacao dos onibus,
quanto no envio dessa informacao ate a Central. No sistema proposto, os onibus
sao localizados por proximidade em relacao as UAs, e a informacao da posicao dos
onibus e encaminhada a Central atraves das UAs. Para o caso especıfico dos onibus,
os pontos de parada sao locais interessantes para a instalacao de UAs, fazendo com
que as estimativas sejam calculadas para esses locais.
4.2.3 Onibus
Os onibus sao os veıculos automotores de transporte publico abordados neste
trabalho. Para que o veıculo possa ser rastreado, ele deve possuir um roteador ou
outro dispositivo com interface IEEE 802.11. Tal roteador deve ser instalado no
interior do veıculo e deve executar as aplicacoes criadas, que sao responsaveis pela
localizacao do onibus em relacao as UAs. O dispositivo instalado deve ser capaz de
se conectar as redes sem-fio criadas pelas UAs.
4.2.4 Cliente
O Cliente e caracterizado como uma pessoa, que pede informacoes da hora de
chegada dos onibus a um dado ponto de onibus ao servico de estimativas do sistema.
A requisicao e realizada pelo Cliente por meio de uma pagina da Internet, e a resposta
ao pedido alcanca o Cliente tambem atraves de uma pagina da Internet, utilizando
a tecnologia de acesso a Internet disponıvel para o Cliente.
23
4.3 Comunicacoes entre Entidades
As quatro entidades se comunicam de formas distintas, usando diferentes tecnolo-
gias para tal. Todas as entidades e as comunicacoes entre elas podem ser visualizadas
na Figura 4.2.
CentralCliente
UA Ônibus
Internet
3GEthernet
IEEE 802.11
Eth
ern
et
Ethernet
3G
Figura 4.2: Comunicacoes entre entidades na arquitetura.
A comunicacao entre o Cliente e a Central, ocorre atraves da Internet, o que
garante compatibilidade, esteja o cliente usando um celular com redes moveis, esteja
ele usando um computador de mesa conectado a um provedor de banda larga. A
comunicacao entre as UAs e a Central pode ser realizada de diferentes maneiras:
atraves de cabos Ethernet, atraves de um modem 3G instalado na porta USB da
UA, ou ainda, atraves de multiplos saltos entre as UAs ate que um contato direto
com a Central seja alcancado. Os saltos seriam realizados atraves de uma interface
de rede sem-fio secundaria, instalada na porta USB da UA.
A comunicacao entre os onibus e a Central, na realidade, e realizada atraves
das UAs. Portanto, resta apenas descrever a comunicacao entre um onibus e uma
UA. Essa comunicacao pode ser caracterizada como uma comunicacao do tipo V2I,
veıculo para infraestrutura, das redes veiculares. Assim, esse tipo de comunicacao
esta sujeita a desafios e problemas inerentes a essas redes, por exemplo, pode acon-
tecer de a comunicacao entre o onibus e a UA nao ocorrer, devido ao perıodo de
24
curto de contato entre onibus e UA.
Os principais problemas das redes veiculares decorrem do curto intervalo de con-
tato entre os nos da rede, pois os veıculos se movem rapidamente. Contudo, es-
tudos realizados observaram que um veıculo, trafegando a aproximadamente 96
quilometros por hora, e capaz de enviar a uma UA 19 megabytes de informacao
usando as redes sem-fio do padrao IEEE 802.11b [28]. Isso indica que mesmo a
uma velocidade superior a de um onibus, veıculo alvo do trabalho, uma quantidade
relevante de informacao pode ser transmitida.
No trabalho [26], mediu-se o tempo medio que os onibus permanecem ao alcance
de uma UA. Esse tempo medio e igual a 65 segundos, caso o onibus pare no ponto
para pegar passageiros, ou 36 segundos, caso contrario. Ja no trabalho [29], os
autores mostraram que o tempo de associacao dos roteadores inseridos nos veıculos
com as UAs foi de ate 9 segundos. Com base nesses valores, e considerando que
os pacotes usados na localizacao sao da ordem de uma centena de bytes, pode-se
supor que o movimento dos onibus nao e problematico para a aplicacao, podendo
ser usado o padrao IEEE 802.11b nas comunicacoes entre os onibus e as UAs.
4.4 Modelo em Rede de Petri
Como o sistema envolve a comunicacao de diversas entidades, optou-se por mo-
delar o sistema, utilizando metodos formais simplificadamente, antes da imple-
mentacao ser iniciada. A modelagem em rede de Petri foi escolhida, pois possui
a capacidade de representar bem sistemas distribuıdos discretos, o que e o caso do
sistema desenvolvido.
Como o sistema e formado por dois servicos diferentes, a rede de Petri completa
do sistema foi dividida em duas partes para facilitar a visualizacao: uma parte para
o servico AVL, na Figura 4.3, e a outra para o servico de previsao de chegada de
onibus, na Figura 4.4. Pelas figuras, nota-se que o servico de localizacao faz uso
de comunicacoes entre todas as entidades, excetuando-se a Cliente, enquanto o de
previsao de chegada de onibus depende apenas da comunicacao entre a Central e o
25
Cliente. Alem disso, observa-se que a Central e a entidade que une ambos os servicos
no sistema, sendo a unica que aparece nas duas partes da rede de Petri completa.
O comportamento do sistema esta descrito nas redes de Petri. O servico de
localizacao se inicia com o onibus se identificando a UA e vice-versa. Em seguida,
o onibus envia uma mensagem a Central informando a qual UA ele esta conectado,
a ultima UA que ele esteve conectado, a linha de onibus que ele esta servindo e o
seu proprio identificador. A partir dessa mensagem, a Central cria ou atualiza o
mapa da linha de onibus que o onibus esta realizando. Apos o processamento do
mapa da linha de onibus, as estimativas de horario de chegada dos proximos onibus
a todas as UAs do mapa sao calculadas. O servico de previsao de chegada de onibus
e oferecido aos Clientes. Neste servico os Clientes solicitam as estimativas a Central
enviando uma mensagem com as informacoes da solicitacao. A Central, ao receber
a solicitacao, envia uma mensagem ao Cliente contendo a estimativa solicitada.
A descricao dos lugares da rede de Petri completa criada encontra-se abaixo:
• P1 - representa o repouso da UA, e possui uma ficha, significando que a UA
sempre esta apta a receber e enviar mensagens para os onibus, desde que seja
uma por vez.
• P2 - denota as mensagens ja enviadas pelo onibus, porem ainda nao recebidas
pela UA.
• P3 - representa as mensagens enviadas pela UA, porem ainda nao recebidas
pelo onibus.
• P4 - e o estado inicial do comportamento dos onibus, pode conter N fichas,
cada uma representando um onibus, ainda desconectado.
• P5 - representa quando o onibus ja esta apto a enviar uma mensagem a UA,
quando ele se associou a UA.
• P6 - denota a espera do onibus pela chegada da mensagem enviada pela UA,
antes de enviar uma mensagem a Central.
26
Figura 4.3: Rede de Petri do servico de localizacao automatica de veıculos.
• P7 - e o estado onde o onibus espera a resposta da Central, antes de retornar
ao estado inicial.
• P8 - contem as mensagens enviadas pelo onibus a Central ainda nao entregues.
• P9 - contem as mensagens enviadas pela Central ao onibus ainda nao recebidas
por este.
• P10 - e o estado inicial da Central, possui duas fichas para representar que uma
mensagem de localizacao e uma requisicao de estimativa do Cliente podem ser
atendidas em simultaneo.
• P11 - representa o estado em que a mensagem recebida pela Central esta em
tratamento para localizar o veıculo e construir ou atualizar o mapa da linha
27
Figura 4.4: Rede de Petri do servico de previsao de chegada de onibus.
de onibus.
• P12 - demonstra que a estimativa da linha de onibus da mensagem esta sendo
calculada pela Central.
• P13 - indica o pedido de estimativa do Cliente em transito para a Central.
• P14 - indica a mensagem da Central com a estimativa pedida indo para o
Cliente.
• P15 - e o estado inicial do comportamento dos Clientes, pode conter N fichas,
esse estado representa o universo de Clientes.
• P16 - e o estado que indica que o Cliente esta no site de requisicao de estima-
tivas.
• P17 - indica o Cliente aguardando a resposta a sua requisicao.
28
A descricao das transicoes da rede de Petri completa desenvolvida pode ser vista
a seguir:
• T1 - indica as acoes de recebimento na UA de uma mensagem vinda do onibus
e envio de uma mensagem da UA para o onibus.
• T2 - indica a associacao do onibus a UA.
• T3 - corresponde ao envio de uma mensagem do onibus para a UA.
• T4 - corresponde ao recebimento de uma mensagem proveniente da UA pelo
onibus e envio de uma mensagem do onibus a Central.
• T5 - indica o recebimento pelo onibus de uma mensagem enviada pela Central.
• T6 - denota as acoes de recebimento na Central de uma mensagem vinda do
onibus e envio de uma mensagem da Central para o onibus.
• T7 - indica o fim do tratamento da mensagem enviada pelo onibus.
• T8 - indica o fim do calculo da estimativa da linha de onibus indicada na
mensagem recebida.
• T9 - corresponde ao recebimento de um pedido de estimativa vindo do Cliente
pela Central e envio da resposta desse pedido da Central ao Cliente.
• T10 - mostra a entrada do Cliente na pagina de requisicao de estimativas.
• T11 - indica o envio da requisicao de estimativa do Cliente a Central.
• T12 - denota o recebimento da resposta a requisicao enviada pela Central ao
Cliente.
A rede completa criada foi inserida em um simulador de redes de Petri, o Ana-
lisador de Redes de Petri (ARP) [30], para que as propriedades da rede fossem
levantadas e possıveis erros de logica fossem retirados. Para inserir a rede no simu-
lador, foi necessario descrever a rede em forma de texto. A descricao em texto da
rede e a saıda da analise da rede feita pelo simulador se encontram no Apendice A.
29
Dentre as propriedades obtidas, as mais importantes foram:
• A rede e viva, ou seja, nao ocorrem bloqueios na arquitetura.
• A rede e limitada, o que significa que a arquitetura nao cria um numero infinito
de mensagens a partir de um numero finito.
• A rede e reinicializavel, o que mostra que a arquitetura apos rastrear um
onibus, ou responder uma estimativa de um cliente, estara apta a realizar
qualquer das duas tarefas novamente.
Como as propriedades indicaram que a rede funcionava como esperado, entao o
desenvolvimento da aplicacao pode ser iniciado. O proximo capıtulo apresentara a
implementacao realizada do sistema.
30
Capıtulo 5
Implementacao do Sistema
Este capıtulo descreve o funcionamento do sistema do ponto de vista da imple-
mentacao. Neste projeto final foram criados os quatro programas, cujas tarefas sao
apresentadas, simplificadamente, abaixo:
• vbcsBusClientUA - Este programa recebe a mensagem enviada pelas UAs com
a identificacao delas e envia a mensagem com a identificacao do proprio onibus
as UAs.
• vbcsBusClientCentral - Este programa recebe a mensagem enviada pela
Central para criacao de historico de comunicacoes e envia a mensagem com as
informacoes sobre o proprio onibus e sobre sua localizacao na rede.
• vbcsUAServer - Este programa envia a mensagem com a identificacao da
propria UA para o onibus e recebe a mensagem com a identificacao do onibus
enviada por ele para criacao de historico de comunicacoes.
• vbcsCentralServer - Este programa envia uma mensagem ao onibus para
criacao de historico de comunicacoes e recebe a mensagem enviada pelo onibus
com as informacoes sobre o proprio onibus e sua posicao na rede. Este pro-
grama, a partir das mensagens recebidas vindas dos onibus, cria o mapa das
linhas de onibus, localiza os onibus e calcula as estimativas de tempo de che-
gada dos onibus. Alem disso, e este programa que recebe e responde os pedidos
de estimativa dos Clientes.
31
5.1 Localizacao Automatica de Veıculos
Desde o inıcio, cada UA executa um programa, chamado vbcsUAServer, que
aguarda as conexoes dos onibus ao socket da UA. Esse programa possui um ciclo in-
finito e e caracterizado como um servidor socket serial. Isso e, ele so trata a proxima
mensagem, quando termina de tratar a mensagem atual. Da mesma maneira, a Cen-
tral executa um programa servidor, chamado vbcsCentralServer, que tambem foi
desenvolvido com sockets, e aguarda as conexoes dos onibus ao socket especıfico do
servico de localizacao.
O processo de localizacao automatica e iniciado pelo onibus. No roteador sem-fio
instalado no onibus, um script busca continuamente pelas redes sem-fio criadas pelas
UAs, se conectando a UA mais proxima, definida como aquela que possuir maior
potencia de sinal. Assim que o onibus se conecta a uma UA, o script inicia um
programa, vbcsBusClientUA, que se conecta ao socket da UA. Com isso, o programa
servidor na UA, citado anteriormente, aceita a conexao e envia uma mensagem ao
onibus.
A mensagem enviada, mostrada na Figura 5.1, contem o identificador da UA.
Neste trabalho, escolheu-se utilizar como identificador as coordenadas geograficas
da UA, ou seja, longitude e latitude. No caso de um plano, como sao as ruas, a
latitude e a longitude identificam unicamente um objeto estatico no espaco. Alem
disso, a localizacao passa a ter um significado mais proximo do geografico, nao sendo
necessario verificar onde a UA esta para localizar o onibus.
<GTApfvbcsUFRJ>
<UAID>
#Identificador da Unidade de Acostamento
#Latitude;Longitude
-22.842709;-43.236139
</UAID>
</GTApfvbcsUFRJ>
Figura 5.1: Mensagem enviada pela UA para o onibus.
32
No sistema criado, o onibus armazena tanto a informacao da UA em que ele se
encontra no momento, quanto a informacao da ultima UA onde ele esteve. Sendo
assim, quando o onibus recebe a mensagem enviada pela UA, a informacao antiga
da UA atual e movida para o arquivo que representa a UA anterior, e o programa
sobrescreve o arquivo da UA atual com a informacao retirada da mensagem recebida
da UA. Terminada a etapa anterior, o onibus responde a UA com uma mensagem,
mostrada na Figura 5.2. Essa mensagem contem as informacoes que identificam e
caracterizam o onibus, o identificador do onibus em si e o identificador da linha de
onibus que ele esta realizando atualmente. Posteriormente, a UA recebe a mensagem
enviada pelo onibus, armazenando-a em um arquivo de log.
<GTApfvbcsUFRJ>
<BusLineID>
#Identificador da Linha do Ônibus
COPPEAD
</BusLineID>
<BusID>
#Identificador do Ônibus
BUS125
</BusID>
</GTApfvbcsUFRJ>
Figura 5.2: Mensagem enviada pelo onibus para a UA.
Assim que o programa vbcsBusClientUA termina sua execucao, o script do onibus
inicia o programa vbcsBusClientCentral, que se conecta ao socket especıfico do
servico de localizacao da Central. Entao, o programa presente na Central aceita
a conexao, enviando, em seguida, uma mensagem para o onibus. Essa mensagem
contem apenas a data que a comunicacao foi realizada, servindo para constituicao de
um historico de comunicacoes entre o onibus e a Central. Apos receber e armazenar
o conteudo da mensagem no historico, o onibus envia uma mensagem, semelhante
a mostrada na Figura 5.3, a Central. Essa mensagem contem todas as informacoes
acerca do onibus no momento, em qual UA o onibus se encontra, a ultima UA que
ele esteve, o identificador do onibus e o identificador da linha de onibus que ele esta
realizando. A Central ao receber essa mensagem, inicia o seu tratamento.
33
<GTApfvbcsUFRJ>
<BusLineID>
#Identificador da Linha do Ônibus
COPPEAD
</BusLineID>
<BusID>
#Identificador do Ônibus
BUS125
</BusID>
<PrevUAID>
#Identificador da UA anterior
#Latitude;Longitude
-22.840363;-43.237508
</PrevUAID>
<CurrUAID>
#Identificador da UA atual
#Latitude;Longitude
-22.842709;-43.236139
</CurrUAID>
</GTApfvbcsUFRJ>
Figura 5.3: Mensagem enviada pelo onibus para a Central.
As secoes a seguir dividem o tratamento das mensagens em funcao das estruturas
presentes no programa e finalidade do tratamento. Apesar de nao ser essencial para
o servico de localizacao, a criacao e manutencao do mapa dinamico das linhas de
onibus, assim como o calculo do intervalo de tempo gasto para o onibus percorrer
o trecho entre duas UAs e realizado nessa parte. Para facilitar o entendimento, as
principais estruturas presentes no programa da Central podem ser visualizadas, de
forma simplificada, na Figura 5.4.
• Bus - cada objeto da classe Bus armazena as informacoes, identificador do
onibus, linha de onibus que ele esta servindo, UA onde o onibus se encontra e
ultima UA onde ele esteve, de um onibus presente no sistema. A lista de ob-
jetos Bus contem as informacoes de todos os onibus cadastrados no programa.
• BusLine - um objeto BusLine e a representacao no programa de uma linha
de onibus real. As informacoes da linha de onibus, como o mapa da linha de
onibus, identificador dela e o numero de onibus realizando-a, estao contidas
nesse objeto. O mapa da linha de onibus e representado pela lista de BusStops
no interior do objeto BusLine. A lista de objetos BusLine armazena todas as
34
busID, busLineID, prevBusStopID, currBusStopID
Lista de BusStopCount nextBusStop
Lista de BusStopCount prevBusStop
BusStop
BusLine
Lista de BusLine
Lista de BusStop
Bus
Lista de Bus
vbcsCentralServer
Mapa Associativo <Trecho,Time>
Lista de TimeBusLine
BusLineID
timeElapsed
TimeBusLine
Figura 5.4: Estruturas principais simplificadas do programa da Central.
linhas de onibus cadastradas no sistema.
• BusStop - cada objeto BusStop representa uma unidade de acostamento in-
serida no mapa de uma linha de onibus, o que significa que uma UA fısica
existira mais de uma vez no programa se o mapa de mais de uma linha de
onibus contiver a UA. Cada objeto BusStop contem duas listas de objetos
BusStopCount, sendo que uma delas indica os BusStops imediatamente apos
o atual no mapa da linha de onibus e a outra os BusStops imediatamente an-
tes do atual no mapa. Isso e necessario em situacoes como linhas com ciclo e
mapas em processo de mudanca, que sera detalhado posteriormente.
• BusStopCount - cada objeto da classe BusStopCount contem um identificador,
semelhante ao contido na classe BusStop; e um contador, que serve como peso.
Os objetos da classe BusStopCount funcionam como arcos pesados, indicando
objetos BusStop.
35
• Time - cada objeto Time esta associado a um trecho UA de origem e UA de
destino. Esse objeto contem uma lista de objetos TimeBusLine para armaze-
nar os intervalos de tempo necessarios para percorrer um dado trecho e uma
variavel que controla o numero maximo de objetos nessa lista. A lista contem
inclusive intervalos de tempo de linhas de onibus diferentes que passem pelo
mesmo trecho.
• TimeBusLine - um objeto TimeBusLine armazena a informacao do intervalo de
tempo necessario para percorrer um dado trecho e a linha de onibus responsavel
por essa informacao. A ultima informacao serve para distinguir intervalos de
tempo de linhas de onibus diferentes que passem pelo mesmo trecho.
A princıpio, pode nao ser intuitivo a necessidade de uma lista de BusStopCount
para representar os BusStops que vem antes e depois do atual, ao inves de apenas
um ponteiro para o anterior e para o proximo. Contudo, deseja-se que o mapa da
linha de onibus seja gradualmente dinamico. Isto e, o mapa nao deve ser alterado
instantaneamente a cada modificacao que aparecer na linha de onibus, pois podem
haver mudancas devido a comportamento inadequado de um motorista, por exemplo.
Esse dinamismo gradual exige que por certo perıodo de tempo exista mais de uma
possibilidade de BusStop anterior ou proximo na rota. Alem disso, a estrutura em
questao e absolutamente necessaria para representar rotas de onibus com ciclos, isto
e, rotas que passam no mesmo ponto duas vezes.
5.1.1 Informacao dos Onibus
Para reunir as informacoes de todos os onibus do sistema, uma lista de objetos
da classe Bus existe no programa da Central. Cada objeto da classe Bus possui
variaveis para armazenar as informacoes da mensagem mais recente recebida. Alem
disso, uma variavel guarda a data que a ultima mensagem desse onibus foi recebida
e outra variavel guarda a data que a penultima mensagem foi recebida.
Quando uma mensagem proveniente de um onibus e recebida, suas informacoes
sao extraıdas e o programa busca na lista de objetos Bus pelo objeto que tem o
mesmo identificador do onibus que o contido na mensagem. Caso nao encontre
36
nenhum objeto correspondente, um novo objeto Bus e criado e adicionado na lista
contendo as informacoes da mensagem recebida e a data de recebimento. Porem,
caso um objeto seja encontrado, o programa verifica possıveis situacoes que possam
ter acontecido com o onibus. Por exemplo, ele pode ter mudado de linha de onibus ou
ter saltado uma ou mais UAs. Essas verificacoes influenciam a criacao do mapa das
linhas de onibus, e serao vistas posteriormente. Apos as verificacoes, as informacoes
do objeto encontrado sao atualizadas com as da mensagem e as datas modificadas
de acordo. Apos esse processo, pode-se dizer que a lista de objetos da classe Bus
armazena todas as informacoes necessarias para se localizar um onibus.
5.1.2 Mapa das Linhas de Onibus
Neste trabalho, como ja foi dito, escolheu-se criar um mapa e mante-lo dinamica-
mente. Em outras palavras, o sistema aprende a lista de pontos de onibus de cada
linha dinamicamente. Para isso ser possıvel, tres classes sao utilizadas: BusLine;
BusStop; e BusStopCount.
Para facilitar o acompanhamento da descricao do procedimento de atualizacao
dos mapas das linhas de onibus, pode-se ver o fluxograma simplificado desse proce-
dimento na Figura 5.5.
As verificacoes realizadas durante a atualizacao das informacoes dos onibus influ-
enciam nesse momento. As verificacoes indicam se o onibus esta sendo visto pela
primeira vez, se ele mudou de linha em relacao a ultima vez que foi visto ou se
ele nao conseguiu enviar a mensagem de localizacao em alguma UA anterior. Para
saber se o onibus mudou de linha, basta comparar o identificador da linha de onibus
contido na mensagem recebida com o contido no objeto Bus do onibus em questao,
antes da atualizacao. Para verificar se o onibus foi capaz de enviar uma mensagem
de localizacao a Central em um ponto anterior, deve-se comparar o identificador
da UA anterior contido na mensagem com o identificador do BusStop atual do ob-
jeto Bus antes da atualizacao. Caso sejam diferentes, pode-se afirmar que alguma
mensagem de localizacao nao foi recebida pela Central.
37
Início
Recebeu mensagem de
localização anterior
Fim
Não
Ônibus mudou de linha de ônibus
Sim
Busca BusLine da
linha anteriorSim
Busca BusLine da
linha de ônibus
atual
Achou
Incrementa
contador de
ônibus da BusLine
Achou
Decrementa
contador de
ônibus da BusLine
Sim
Sim
Não
Ônibus visto pela primeira vez
Não
Sim
Busca BusLine da
linha de ônibus da
mensagem
Não
Achou
Cria BusStop da
UA da mensagem
Cria BusLine da
linha de ônibus da
mensagem com o
novo BusStop
Não
Busca UA da
mensagem na
lista de BusStops
da BusLine
Sim
Achou
Cria BusStop da
UA da mensagem
dentro da BusLine
Não
Atribui valor
máximo ao peso de
todos os BusStops
da BusLine
Cria
BusStopCount
para a UA anterior
no BusStop atual
Atualiza lista de
BusStopCounts das
UAs anteriores da
UA atual
Sim
Atualiza peso de
todos os BusStops
da BusLine
Atualiza lista de
BusStopCounts das
próximas UAs da
UA anterior
Limpa lista de
BusStops da
BusLine
Figura 5.5: Fluxograma do procedimento de atualizacao dos mapas das linhas de onibus.
38
Caso se verifique que a Central nao recebeu alguma mensagem de localizacao
anterior, o procedimento de atualizacao do mapa da linha nao e executado e o
tratamento da mensagem recebida termina. Caso contrario, diz-se que o onibus age
normalmente, o tratamento da mensagem recebida continua e o procedimento de
atualizacao do mapa da linha sera realizado.
Se tiver sido verificado que o onibus mudou de linha, o programa procurara a
linha de onibus antiga na lista de BusLines e retirara uma unidade do contador de
onibus daquela linha. Em seguida, a nova linha de onibus sera procurada e, caso
exista, uma unidade sera adicionada ao contador de onibus dessa linha. Da mesma
maneira, se o onibus estiver sendo visto pela primeira vez, a linha do novo onibus
sera encontrada se existir, e uma unidade sera adicionada ao contador de onibus
dessa linha.
Apos as verificacoes anteriores e com o onibus agindo normalmente, busca-se a
linha de onibus atraves do identificador contido na mensagem recebida. Nao havendo
nenhum objeto BusLine referente a linha especificada na mensagem, um objeto
BusStop e criado e inserido na nova linha sendo criada. Esse BusStop representa
o ponto de partida da linha de onibus, e e criado a partir do identificador da UA
atual contido na mensagem. Ja no caso de a linha de onibus ter sido encontrada,
o programa ira procurar dentro da lista de BusStops, da BusLine encontrada, pela
UA atual da mensagem.
Se a UA nao for encontrada na lista, um objeto BusStop e criado para ela e
inicializado com o peso maximo. O valor maximo do peso dos BusStops varia com
o numero de BusStops na linha, conforme mostrado na Equacao 5.1:
maxWeightBusStop = 2 ∗ qtBusStopInBusLine ∗ qtBusInBusLine, (5.1)
onde maxWeightBusStop e o valor maximo permitido para o peso dos BusStops,
qtBusStopInBusLine representa a quantidade de BusStops no objeto BusLine e qt-
BusInBusLine representa o numero de objetos Bus percorrendo a BusLine. Entao,
39
para ser justo com os BusStops adicionados anteriormente, decidiu-se que quando
um novo BusStop for acrescentado em uma BusLine, apos o peso maximo ser atu-
alizado, o peso de todas as UAs cadastradas na linha e igualado a ele. Terminado
o ajuste dos pesos dos BusStops, cria-se um objeto BusStopCount para referenciar
a UA anterior da mensagem com peso do arco maximo, o peso do arco maximo e
regido pela Equacao 5.2:
maxWeightBusStopCount = 2 ∗ qtBusStopInBusLine, (5.2)
onde maxWeightBusStopCount e o valor maximo permitido para o peso do arco
e qtBusStopInBusLine representa a quantidade de BusStops no objeto BusLine.
Entao, esse objeto BusStopCount e inserido na lista de UAs que aparecem antes da
UA atual na rota, no interior do objeto BusStop.
Contudo, se a UA for encontrada na lista de BusStops da linha, a lista de BusStop-
Counts que representa os pontos anteriores ao BusStop e atualizada. Na atualizacao,
subtrai-se uma unidade do peso do arco de todos os elementos da lista. Em seguida,
somam-se duas unidades no peso do arco referente a UA anterior da mensagem re-
cebida, se o valor apos a soma for superior ao maximo, ele sera igualado ao maximo.
Caso algum objeto BusStopCount alcance peso do arco igual a zero apos esse pro-
cesso, ele sera removido, significando que aquele BusStop nao e mais utilizado como
anterior do atual. O passo seguinte e a atualizacao do peso do BusStop. Nessa
atualizacao, o peso de todos os BusStops da lista e decrementado de uma unidade.
Apos a subtracao, soma-se ao peso do BusStop o valor da Equacao 5.3:
weightBusStopIncrement = 2 ∗ qtBusStopInBusLine, (5.3)
onde weightBusStopIncrement e o valor do incremento somado ao peso do BusStop e
qtBusStopInBusLine representa a quantidade de BusStops no objeto BusLine. Caso
apos a soma o valor do peso do BusStop ultrapasse o valor maximo estipulado pela
Equacao 5.1, o peso do BusStop sera igualado ao maximo.
Como visto, dois tipos distintos de pesos sao usados no trabalho, esses pesos tem
funcoes diferentes. O peso do arco associado ao BusStopCount e o peso que rege a
40
dinamicidade do mapa, ou seja, quao rapido o mapa aceita uma modificacao na rota
como verdadeira e intencional. Esse peso no trabalho e uma constante independente
que pode ser ajustada no codigo. Entretanto, o valor escolhido deve respeitar a
restricao de ser no maximo duas vezes o numero de onibus servindo a linha, como
visto na Equacao 5.2. Essa restricao e necessaria, pois em uma mudanca de rota,
obrigatoriamente, o peso do arco, que indica que o BusStop em processo de remocao
faz parte da rota, deve alcancar o valor zero antes do peso do BusStop em remocao.
Caso isso nao seja respeitado, o objeto do BusStop em remocao e removido antes
de ser retirado do mapa da linha de onibus, gerando uma falha no programa. Nos
testes, o valor usado foi o maximo permitido.
Ja o peso dos BusStops e usado apenas para fins de liberacao de memoria, o que
fica claro no exemplo de funcionamento de mudanca de rota. O valor desses pesos
deve ser grande o suficiente para que nenhum BusStop seja excluıdo antes da hora, o
que levaria a inconsistencias na rota de onibus. Por isso, o valor inicial atribuıdo e o
maximo contido na Equacao 5.1. A ideia por tras do valor maximo desses pesos e que
seria necessario que todos os onibus realizando a linha percorressem todos os pontos
da linha pelo menos duas vezes, para que um ponto nao utilizado fosse excluıdo. Da
mesma maneira, o incremento dado quando o BusStop e usado deve garantir que
o BusStop utilizado nao sera excluıdo enquanto o onibus percorre normalmente os
outros BusStops da linha. Por isso, o incremento e funcao apenas do numero de
BusStops contido na linha de onibus, como visto na Equacao 5.3.
O proximo passo na atualizacao do mapa da linha e atualizar a lista de proximas
UAs da UA anterior. Para isso, busca-se na lista de BusStops da BusLine pelo
BusStop com identificador igual ao da UA anterior contido na mensagem. Quando
o BusStop for encontrado, atualiza-se a lista de BusStopCounts que representa as
proximas UAs do BusStop seguindo os mesmos criterios da atualizacao feita para a
lista de UAs anteriores.
Apos todas as atualizacoes nos pesos terem sido realizadas, o mapa da linha de
onibus esta pronto. Porem, pode haver UAs nao utilizadas na lista de UAs da linha
de onibus. E importante notar que apesar da existencia das UAs nao utilizadas, de
41
fato elas ja nao pertencem a rota da linha de onibus, pois partindo do ponto inicial,
elas nao sao alcancaveis. Para remover essas UAs inuteis, inicia-se o processo de
limpeza da rota da linha de onibus, ou seja, da lista de BusStops dentro da BusLine.
Nesse processo, os BusStops podem ser eliminados por dois criterios, sao eles:
1. O BusStop nao e mais referenciado como anterior ou proximo BusStop por
nenhum outro BusStop contido na linha.
2. O peso do BusStop alcancou o valor zero.
Inicialmente, utilizava-se apenas o primeiro criterio, mas em casos onde varias UAs
em sequencia deixam de ser usadas na rota, essas UAs continuam se referenciando,
nao sendo possıvel remove-las pelo primeiro criterio, por isso o segundo criterio e
necessario.
Realizados todos os procedimentos acima, o mapa da linha de onibus e construıdo
e atualizado dinamicamente, e as UAs nao utilizadas sao excluıdas da lista das linhas
de onibus. Um exemplo de mapa construıdo pelo programa pode ser visualizado na
Figura 5.6. Nas figuras que representam os mapas de linhas de onibus desse projeto
final, as circunferencias representam as UAs, ou seja, os BusStops. O numero no
interior do retangulo em cada UA e o peso da UA usado em um criterio de exclusao.
Ja os numeros nas setas representam os pesos dos arcos associados as informacoes
de proxima UA e UA anterior da UA de origem da seta.
UAUAPeso=5
UA
Peso=2 Peso=2
Peso=2Peso=2
Peso=6 Peso=4
Figura 5.6: Visualizacao de mapa criado pelo programa.
42
5.1.3 Intervalos entre UAs
Os intervalos de tempo gastos entre duas UAs devem ser conhecidos para, poste-
riormente, as estimativas de previsao de chegada serem calculadas. Para criar esses
tempos, sao usadas as informacoes armazenadas nos objetos da classe Bus. Nesses
objetos foram armazenados os horarios de chegada das duas ultimas mensagens,
bem como os identificadores das duas ultimas UAs que o onibus passou. Porem,
somente quando o onibus estiver agindo normalmente, segundo as verificacoes ja
citadas, essas informacoes serao usadas para o calculo do intervalo de tempo entre
as UAs.
As classes Time e TimeBusLine sao usadas para armazenar e lidar com os dados
relativos as estimativas. No programa principal, uma estrutura map contem objetos
da classe Time. Nessa estrutura, a concatenacao dos identificadores das UAs do
trecho separados por um asterisco e utilizada como ındice identificador de cada
objeto, seguindo a forma origem*destino. Por exemplo, o trecho da mensagem 5.3
e identificado como: -22.840363;-43.237508*-22.842709;-43.236139.
Pode-se observar que da maneira que a estrutura de armazenamento e construıda
todas as linhas que passam pelo mesmo par de UAs origem*destino tem seus tempos
armazenados no mesmo objeto Time. Isso acontece pois os tempos sao diferenciados
quanto a linha de onibus apenas no objeto TimeBusLine. A estrutura de armazena-
mento dos tempos e construıda dessa forma para que a media dos intervalos gastos
no trecho possa ser calculada de duas formas distintas. Uma das formas de calculo
utiliza as informacoes de todas as linhas de onibus que passam no trecho enquanto
a outra usa apenas as informacoes pertencentes a linha de onibus sendo estimada.
Os dois metodos para o calculo de media estao presentes no objeto Time, e sao
discutidos na secao de estimativas.
O calculo do tempo gasto para percorrer o trecho consiste em subtrair os dois
horarios contidos no objeto Bus, obtendo como resultado o intervalo de tempo gasto
entre as duas UAs. Apos a subtracao, cria-se um objeto TimeBusLine com o tempo
calculado e com o identificador da linha de onibus do objeto Bus. Em seguida, o
identificador do trecho e criado usando os identificadores das UAs anterior e atual
43
contidas no objeto Bus. Entao, realiza-se uma busca no map pelo objeto Time
correspondente ao identificador criado. Caso o objeto do trecho nao exista na es-
trutura, ele e inicializado com o primeiro TimeBusLine inserido e incluıdo no map.
Entretanto, caso o objeto do trecho exista, o objeto TimeBusLine criado e inserido
no final da lista de TimeBusLines do objeto Time encontrado. Caso o numero de
elementos nessa lista ultrapasse o maximo permitido pela variavel de controle do
objeto Time, remove-se o primeiro elemento, como uma FIFO. A lista ser FIFO
garante que os elementos existentes nela sao sempre os mais recentes. A exclusao
leva em consideracao o numero de elementos totais e nao o numero de elementos de
cada linha de onibus. Com isso, e possıvel que uma linha de onibus monopolize os
tempos gastos armazenados para um determinado trecho. Por exemplo, caso duas
linhas de onibus com numeros diferentes de onibus compartilhem um determinado
trecho em suas rotas. Para reduzir o problema, fez-se o tamanho maximo da lista
ser variavel e proporcional ao numero de linhas de onibus total no programa, como
mostrado na Equacao 5.4:
maxTimeBusLineListSize = qtBusLine ∗K, (5.4)
onde maxTimeBusLineListSize e o tamanho maximo da lista de objetos TimeBus-
Line, qtBusLine representa o numero de objetos BusLine existentes no sistema e K
e um parametro que controla a proporcao entre as variaveis maxTimeBusLineList-
Size e qtBusLine. Neste projeto K foi ajustado para 10, podendo ser alterado se
necessario.
Nao impedir um monopolio esta associado a ideia de se armazenar as informacoes
mais recentes para os trechos. Contudo, o monopolio pode ser malefico caso existam
linhas de onibus que passam pelas mesmas duas UAs seguidas, caracterizando o
trecho origem*destino, mas por caminhos geograficos muito distintos. Esse problema
e um problema de amostragem. A solucao proposta e a insercao entre as UAs que o
problema ocorre de uma nova UA na rota da linha de onibus que percorre o maior
caminho do trecho.
44
5.2 Previsao de Chegada de Veıculos
A previsao de chegada de veıculos e um servico de ITS oferecido aos usuarios dos
meios de transporte publicos. De posse do mapa da linha de onibus e da informacao
dos tempos gastos pelos onibus entre duas UAs, pode-se calcular o tempo que um
onibus leva para alcancar os pontos seguintes da sua rota. Esse servico e oferecido
pela Central aos Clientes.
5.2.1 Pagina de Requisicao de Estimativas
O Cliente precisa informar uma linha e um ponto de onibus para receber uma
estimativa de hora de chegada do proximo onibus. Para esse fim, criou-se uma
pagina na Internet que pode ser vista na Figura 5.7.
Na pagina criada, o Cliente deve selecionar uma das linhas de onibus disponıveis
no sistema. Em seguida, o Cliente deve clicar em uma das figuras dos pontos de
onibus no mapa. Com isso, o ponto de onibus selecionado ficara vermelho, indicando
a escolha feita, como pode ser visto na Figura 5.8. Apos o Cliente selecionar as
informacoes necessarias, ele deve clicar no botao “Estimar”. Caso o Cliente se
esqueca de selecionar o ponto ou a linha de onibus, uma janela o informa e pede
para que os campos sejam preenchidos corretamente. Caso contrario, o Cliente e
direcionado para uma pagina onde ele recebe a resposta a sua requisicao, como pode
ser visualizado na Figura 5.9.
A pagina onde o Cliente recebe a resposta possui um codigo em PHP que cria
uma mensagem similar a da Figura 5.10. Em seguida, a pagina envia a mensagem
criada para o socket especıfico do servico de estimativa da Central. A mensagem
contem as informacoes da requisicao do usuario: linha e ponto de onibus escolhidos.
A Central recebe o pedido e responde com a estimativa desejada via socket.
5.2.2 Calculo de Estimativas
O calculo das estimativas e realizado apos o servico de localizacao automatica de
veıculos ter terminado o tratamento da mensagem recebida. E importante notar
que apesar do servico de previsao depender do Cliente, o calculo das estimativas e
45
Figura 5.7: Pagina de solicitacao de estimativa.
independente das requisicoes do Cliente. Essa escolha e feita para evitar a sobrecarga
do processador. A sobrecarga aconteceria caso os calculos fossem efetuados a cada
requisicao de Cliente e muitos Clientes pedissem estimativas simultaneamente. O
resultado caso a sobrecarga acontecesse seria uma especie de negacao de servico.
Toda vez que a Central recebe uma mensagem, apos o servico de localizacao au-
tomatica de veıculos, a linha de onibus identificada na mensagem tem as estimativas
calculadas para todos os BusStops. A unica restricao para o calculo das estimativas
ser realizado e que a linha de onibus em questao deve ter os pontos inicial e final
diferentes, isso e, nao deve ser uma linha circular. Isso se deve pois para o caso de
46
Figura 5.8: Ponto de onibus e linha de onibus selecionados.
linhas circulares o algoritmo utilizado no calculo de estimativas segue o mapa da
linha de onibus eternamente. Entretanto, para usar o servico em casos de linhas
circulares basta dividir a linha de onibus em duas. Por exemplo, de acordo com o
sentido que a linha esta sendo percorrida em relacao a algum ponto de referencia,
como, em direcao a qual bairro o onibus esta indo. Apesar de linhas circulares nao
segmentadas nao serem estimadas, linhas que contenham ciclos em seu interior sao
estimadas normalmente.
Alem das variaveis descritas na secao anterior, a classe BusStop possui ainda
quatro variaveis para armazenar as estimativas de tempo. Cada variavel guarda
estimativas calculadas de maneiras diferentes. As quatro estimativas sao resul-
47
Figura 5.9: Estimativa devolvida ao Cliente.
<GTApfvbcsUFRJ>
<ReqBusLineID>
#Identificador da Linha do Ônibus requisitada
COPPEAD
</ReqBusLineID>
<ReqUAID>
#Identificador da UA requisitada
#Latitude;Longitude
-22.842709;-43.236139
</ReqUAID>
</GTApfvbcsUFRJ>
Figura 5.10: Mensagem de requisicao enviada pelo Cliente para a Central.
tado da existencia de duas formas diferentes de calcular as medias dos trechos ori-
gem*destino. Uma das formas calcula a media de todos os elementos TimeBusLine
da lista contida na classe Time do trecho, nao importando se os tempos usados na
media pertencem a mesma linha de onibus. A outra forma calcula a media con-
siderando apenas os objetos TimeBusLine que pertencem a linha de onibus sendo
estimada.
A primeira forma e necessaria pois podem existir situacoes onde os tempos da linha
de onibus sendo estimada sao antigos. Com isso, eles ja nao representam as atuais
condicoes de transito do trecho, o que resulta em uma estimativa errada. Como
a primeira forma nao restringe os tempos usados na media, misturando tempos de
diferentes linhas, o uso de tempos mais recentes no calculo da media e privilegi-
ado. Caso o problema, ja citado, de duas rotas que passam pelas mesmas UAs em
sequencia, mas por caminhos muito discrepantes, nao ocorra, esse metodo pode ser
usado sem nenhuma ressalva.
48
Com os dois tipos de media citados para cada trecho, escolheu-se incrementar as
estimativas de quatro maneiras distintas para cada BusStop. A primeira maneira
utiliza como incremento entre a estimativa do ponto anterior e do ponto atual a
media apenas dos intervalos de tempo do trecho que pertencam a propria linha. A
segunda utiliza a media de todos os tempos no trecho como incremento. Ja a terceira
usa como incremento o valor mınimo entre as duas medias anteriores, enquanto a
quarta usa como incremento o valor maximo entre elas. O uso da terceira maneira
resulta em uma estimativa otimista do tempo de chegada do proximo onibus, ou seja,
resulta no menor tempo possıvel que o sistema preve a chegada do proximo onibus.
Por outro lado, o uso da quarta maneira resulta em uma estimativa pessimista do
tempo de chegada do proximo onibus, ou seja, resulta no maior tempo possıvel que
o sistema preve a chegada do proximo onibus. No sistema, as quatro maneiras de
incrementar as estimativas sao realizadas. A escolha da maneira de estimar que sera
enviada aos usuarios fara parte de um trabalho futuro.
No calculo da estimativa, busca-se o menor tempo necessario para que um onibus
qualquer da linha sendo estimada alcance cada um dos pontos do mapa. Como
condicao inicial, todas as variaveis de estimativa de todos os BusStops armazenados
no mapa da linha sao igualadas a um valor de referencia negativo. Em seguida,
para cada onibus realizando a linha, procura-se o BusStop onde ele foi visto pela
ultima vez, e faz-se com que esse BusStop receba o valor de estimativa zero. A seguir
inicia-se um procedimento que simula o percurso do onibus pela linha, a partir do
ponto onde o onibus estava.
Devido a forma como o mapa e construıdo, escolheu-se fazer o procedimento
que percorre a linha ser recursivo. O procedimento desenvolvido tem como unica
condicao de parada que o ponto sendo avaliado nao possua nenhum proximo ponto
cadastrado.
Durante o percurso, um BusStop em analise pode ter mais de um BusStop proximo
possıvel. Isso pode ocorrer devido a uma mudanca de rota em andamento, como
pode ser visto na Figura 5.11, ou devido a rota possuir um ciclo, como na Figura 5.12.
No exemplo da Figura 5.11, o onibus que normalmente percorre a rota UA-1, UA-2,
49
UA-3, UA-4 e UA-5 comeca a realizar uma nova rota, onde vai diretamente da UA-2
para a UA-5. Ja no exemplo da Figura 5.12, o trajeto da linha de onibus e UA-1,
UA-2, UA-3, UA-4, UA-2, UA-3 e UA5. O fato de um BusStop em analise poder ter
mais de um BusStop proximo possıvel exige que um mecanismo de controle exista.
Esse mecanismo deve existir para que o algoritmo que percorre a linha decida qual
dos proximos pontos e o seguinte da rota. O mecanismo de controle deve funcionar
tanto para o caso de uma mudanca de rota em curso quanto para o caso de uma
linha com ciclos na rota.
UA-1 UA-2
2
2
UA-3
1
2
UA-4
2
2
UA-5
2
1
2
2
8 10779
Figura 5.11: Mudanca de rota em curso.
UA-1 UA-2 UA-3 UA-5
UA-4
1010 10 10
10
22
21 2
22 2
12
Figura 5.12: Linha com ciclo.
O mecanismo de controle so atua caso o BusStop em analise possua mais de
um proximo BusStop. Para definir se o onibus percorrendo a linha esta passando
no BusStop pela primeira ou segunda vez, cria-se uma lista dentro de cada objeto
BusStop. Assim que um onibus chega ao BusStop em questao, verifica-se se o
identificador dele existe na lista do BusStop. Se nao existir, o identificador do
50
onibus e inserido na lista. Nesse caso o onibus esta passando pela primeira vez no
BusStop. Ja caso o identificador exista na lista, retira-se o identificador da lista para
restaurar a configuracao inicial. Nesse caso o onibus esta passando pela segunda vez
no BusStop. No primeiro caso, o onibus e direcionado para o primeiro BusStop
cadastrado na sua lista de proximos BusStops. Ja no segundo caso, o onibus e
direcionado para o segundo BusStop cadastrado em sua lista de proximos.
Nos casos de mudanca de rota que nao constituem um ciclo, como no exemplo
da Figura 5.11, o mecanismo de controle sempre indica para o onibus seguir para o
primeiro BusStop cadastrado na lista de proximos. Isso ocorre pois para esse caso em
um mesmo calculo de estimativa, o mesmo onibus so passa por esses BusStops uma
vez. Nos casos de rotas com ciclo, como o exemplo da Figura 5.12, o mecanismo faz o
onibus percorrer a rota corretamente. Com isso, o algoritmo desenvolvido soluciona
o problema de definir qual o proximo BusStop para ambos os casos problematicos.
Apos a definicao do proximo BusStop, o identificador origem*destino do trecho e
gerado. Em seguida, busca-se por esse identificador na estrutura que armazena os
intervalos de tempo dos trechos, encontrando as informacoes de intervalo de tempo
do trecho.
De posse das informacoes, os dois tipos de medias citados anteriormente sao re-
alizados. Contudo, as quatro estimativas do proximo BusStop so sao atualizadas
caso os valores das estimativas do BusStop atual somados aos incrementos do trecho
sejam menores que os valores das estimativas presentes no proximo BusStop. Isso
e feito para garantir que as variaveis de estimativa guardem os tempos necessarios
para a chegada do onibus mais proximo, ou seja, as estimativas mınimas.
Toda vez que as variaveis de estimativas do proximo BusStop sao atualizadas, e
modificada tambem uma variavel que indica qual o onibus mais perto do BusStop
seguinte ate o momento. Em seguida, o proprio procedimento que simula o percurso
do onibus e chamado, indicando como BusStop atual o proximo BusStop. Isso simula
o movimento do onibus na rota.
51
Apos todos os onibus terem o percurso simulado, recalcula-se as estimativas dos
BusStops que possuem estimativa igual a zero. Isso e necessario pois a estimativa
ser igual a zero significa que o onibus acabou de passar ou que ele esta nesse exato
momento no ponto de interesse. Essas informacoes nao sao relevantes para o Cliente.
Entao, as estimativas desses BusStop sao modificadas de maneira a conter as esti-
mativas para o proximo onibus alcanca-lo. Isso e realizado, retornando pela rota ate
os BusStops anteriores a eles e somando as estimativas dos anteriores com as medias
do respectivo trecho BusStop anterior BusStop atual. Os resultados dos calculos sao
armazenados como as novas estimativas dos BusStops que tinham estimativa zero.
5.2.3 Resposta aos Clientes
No programa que executa na Central, ha um thread responsavel pelo servidor
socket que recebe as requisicoes de estimativas dos Clientes. Esse servidor e seme-
lhante ao do recebimento de mensagens, todavia utiliza outra porta. Quando uma
mensagem de requisicao e recebida, as informacoes contidas nela, ponto de onibus
alvo e linha de onibus desejada, sao retiradas. Em seguida, busca-se o objeto cor-
respondente a linha de onibus requisitada na lista de linhas de onibus do programa.
Caso esta nao exista uma mensagem e enviada indicando o problema ao Cliente. De
posse do objeto da linha de onibus, o ponto de onibus e buscado no mapa da linha.
Caso nao seja encontrado, uma mensagem e enviada ao Cliente indicando que a rota
nao passa pelo ponto indicado. Caso o ponto de onibus seja encontrado no mapa
da linha, obtem-se a estimativa do ponto em questao. Em seguida, a estimativa e
atualizada e, apos a atualizacao, enviada ao Cliente atraves de uma mensagem.
A referida atualizacao e necessaria pois, como dito anteriormente, o calculo das
estimativas e independente das requisicoes dos Clientes. Portanto, uma vez que
as estimativas de uma linha de onibus tenham sido calculadas, elas somente sao
recalculadas quando um onibus daquela linha enviar outra mensagem. Ou seja, as
estimativas presentes nos BusStops nao decrescem com o tempo, mas somente com
novas mensagens de onibus da linha. Isso significa que as estimativas caem em saltos
ao inves de continuamente, o que pode ser ruim para o Cliente.
52
Para que as estimativas caiam continuamente para o Cliente, guarda-se no mo-
mento do calculo das estimativas, a data que elas foram alteradas. As estimativas
so sao alteradas de fato nos BusStops em que o onibus mais proximo e tambem o
onibus que enviou a mensagem que iniciou o calculo das estimativas. Entao, usando
a data de alteracao da estimativa presente no BusStop, e a data de recebimento
da requisicao, calcula-se o tempo decorrido entre as duas situacoes. Em seguida, o
tempo decorrido e subtraido da estimativa do BusStop, antes que esta seja enviada
ao Cliente. Com isso o Cliente enxerga a estimativa decrescendo continuamente, o
que lhe e mais util e agradavel.
5.3 Linguagens e Bibliotecas
Todos os programas usados nos roteadores, seja nas Unidades de Acostamento ou
nos onibus, sao escritos em C, e a compilacao desses programas e realizada atraves
de compilacao cruzada, ou seja, e gerado codigo executavel para um processador
diferente daquele em que a compilacao era realizada. Compila-se em um PC codigo
a ser executado em um processador ARM, presente nos roteadores sem-fio utilizados.
O procedimento para realizar essa compilacao encontra-se em [31].
A Central e escrita parte em C e parte em C++. Isso ocorre pois o C++ nao
lida diretamente com sockets como o C faz. Por isso o C e usado somente na parte
de manipulacao de sockets e no thread responsavel por responder as requisicoes de
estimativa do Cliente, enquanto o C++ e utilizado no restante do programa.
As paginas acessadas pelo Cliente sao desenvolvidas em PHP com parte em Ja-
vascript. Alem disso, e utilizada a API versao 3 do Google Maps [32] para o usuario
visualizar no mapa da cidade os pontos de onibus cadastrados no sistema. Isso e
feito para facilitar ao Cliente a escolha do ponto de onibus. O PHP e usado devido
a sua semelhanca com o C e o suporte a sockets. Ja o Javascript e usado devido a
API do Google Maps ser em Javascript.
53
5.4 Exemplos do Funcionamento do Sistema
Nessa secao dois exemplos do funcionamento do sistema sao apresentados passo
a passo. Nas figuras dessa secao, a linha da circunferencia que representa uma UA
estar mais espessa significa que ha um onibus nessa UA no momento.
5.4.1 Construcao Inicial de uma Linha de Onibus
Nesse teste, considerou-se uma linha fictıcia de onibus que realiza uma rota per-
correndo UAs numeradas de um a cinco em ordem ascendente. O ponto inicial da
rota e a UA-1 e o ponto final a UA-5. Para facilitar a compreensao, apenas um
onibus percorre a rota sendo construıda, mas essa limitacao nao existe na aplicacao
desenvolvida.
No inıcio, a linha de onibus nao existe. A linha de onibus, e consequentemente
seu mapa, so e criada quando, ao menos uma vez, um onibus informa a Central
que esta realizando aquela linha. Portanto, quando a Central recebe a mensagem
de uma dada linha pela primeira vez, ela cria essa linha. A linha ao ser criada ja
contem a UA onde o onibus se encontra como UA inicial da linha de onibus. A UA
inicial recebe o peso maximo, cujo valor pode ser obtido pela Equacao 5.1; ou seja,
duas vezes o numero de UAs no mapa da linha de onibus multiplicado pelo numero
de onibus servindo a linha de onibus. O resultado da operacao descrita pode ser
visualizado na Figura 5.13.
UA-12
Figura 5.13: Criacao do mapa da linha com primeira UA.
O proximo passo na construcao da rota e tomado quando o onibus alcanca a
proxima UA da rota da linha de onibus. Ao alcancar a proxima UA da rota o onibus
envia uma mensagem a Central. A Central ao receber essa mensagem, verifica que
a linha de onibus ja existe, mas que a UA informada pelo onibus ainda nao existe
54
na rota. A Central, entao, cria um objeto associado a essa nova UA e o insere na
rota. Ao uma nova UA ser adicionada na rota, os pesos de todas as UAs da rota sao
atualizados para o novo valor maximo, dado pela Equacao 5.1, ja considerando a
nova UA na rota. Como a UA-2 nao e a primeira da linha, a Central associa a UA-2
como proxima UA da rota em relacao a UA inicial (UA-1). Da mesma maneira, a
Central indica na UA-2 que a UA-1 vem antes dela na rota. Essas informacoes sao
inicializadas com peso do arco igual a dois, valor obtido atraves da Equacao 5.2. O
mapa apos essas operacoes pode ser visto na Figura 5.14.
UA-1 UA-2
2
24 4
Figura 5.14: Mapa apos insercao da segunda UA.
Em seguida, o onibus alcanca a terceira UA da rota, avisando a Central. A
Central verifica que a UA informada nao existe na rota, precisando ser criada e
inserida. Com isso, a Central cria um objeto associado a essa nova UA e o insere na
rota. Como ja visto anteriormente, os pesos de todas as UAs sao atualizados segundo
a Equacao 5.1 ja considerando a nova UA na rota. Em seguida, a Central associa
a nova UA como proxima UA da UA anterior. Da mesma forma, a Central indica
na nova UA que a segunda UA e anterior a ela. Essas informacoes sao inicializadas
com valor dado pela Equacao 5.2. O mapa atualizado pode ser visto na Figura 5.15.
UA-1 UA-2
2
2
UA-3
2
26 6 6
Figura 5.15: Mapa apos insercao da terceira UA.
O processo descrito anteriormente e repetido para as quarta e quinta UAs da
rota. Com os pesos das UAs sendo alterados e as informacoes de proxima UA e UA
55
anterior das UAs sendo preenchidas toda vez que uma nova UA e inserida na rota.
O mapa apos a insercao da quarta UA pode ser visualizado na Figura 5.16, e apos
a insercao da quinta e ultima UA da linha na Figura 5.17.
UA-1 UA-2
2
2
UA-3
2
2
UA-4
2
288 8 8
Figura 5.16: Mapa apos insercao da quarta UA.
UA-1 UA-2
2
2
UA-3
2
2
UA-4
2
2
UA-5
2
210 10 1010 10
Figura 5.17: Mapa final da linha de onibus.
5.4.2 Mudanca de Rota
O exemplo de funcionamento atual demonstra como o sistema lida com mudancas
na rota de uma linha de onibus. Mudancas de rota podem ser devido a diversos
fatores, por exemplo, vias interditadas ou mau funcionamento de UAs na rota. Esses
eventos podem gerar uma diminuicao do numero de UAs na rota ou um aumento
de UAs. Nao importa se a rota aumenta ou diminui, o sistema lida com a mudanca
das rotas da mesma forma, alterando as informacoes de proxima UA e UA anterior
das UAs da linha.
Neste exemplo de funcionamento e demonstrado o exemplo em que a rota da linha
de onibus diminui. Fez-se essa escolha pois ela permite demonstrar a necessidade da
existencia dos dois tipos de peso. Um para controlar a dinamicidade do mapa e outro
para controlar a exclusao de UAs da rota. A dinamicidade do mapa e controlada
pelo peso dos arcos e a exclusao de UAs da rota e controlada pelo peso das UAs.
56
Neste exemplo, considerou-se a linha fictıcia de onibus criada no exemplo anterior.
Apenas um onibus percorre a rota sendo modificada durante o teste. O teste se inicia
com o onibus se movendo ate a UA-1. Isso atualiza o peso da propria UA para o
maximo, e reduz em uma unidade o peso de todas as outras UAs da linha. Essa
situacao se encontra na Figura 5.18.
UA-1 UA-2
2
2
UA-3
2
2
UA-4
2
2
UA-5
2
210 9999
Figura 5.18: Rota inicial da linha de onibus.
Em seguida, o onibus se movimenta ate a UA-2, o que nao causa alteracao nos
pesos dos arcos entre as UAs 1 e 2, que continuam com valor maximo permitido.
Entretanto, o peso de todas as outras UAs da linha de onibus e decrementado de
uma unidade, enquanto o peso da UA-2, onde o onibus se encontra, e incrementado
de acordo com a Equacao 5.3. Apos o incremento o peso da UA-2 atinge o peso
maximo permitido, regido pela Equacao 5.1. O mapa atualizado pode ser visto na
Figura 5.19.
UA-1 UA-2
2
2
UA-3
2
2
UA-4
2
2
UA-5
2
28 88109
Figura 5.19: Onibus se move ate a UA-2.
Se a rota fosse seguida normalmente, o proximo passo seria o onibus ir ate a
UA-3. Todavia, nesse exemplo de funcionamento, supoe-se que as UAs 3 e 4 estao
defeituosas. Com isso, a Central nao recebe as mensagens referentes a esses dois
pontos de acesso. Portanto, a proxima UA funcionando na rota e a UA-5. Ao
chegar na UA-5, o onibus envia uma mensagem a Central, informando que ele esta
57
la e que antes esteve na UA-2. Quando a Central recebe essa mensagem, ela atualiza
os pesos de todas as UAs da linha.
Apos a atualizacao dos pesos das UAs da linha, a UA-5 e cadastrada na lista de
proximas UAs da UA-2. Da mesma maneira, a UA-2 e cadastrada na lista de UAs
anteriores da UA-5. Ambos os arcos sao inicializados com peso igual a Equacao 5.2.
Em seguida, as outras informacoes da lista de proximas UAs da UA-2 e da lista
de UAs anteriores da UA-5 sao decrementadas de uma unidade. O resultado desse
processo pode ser observado na Figura 5.20.
UA-1 UA-2
2
2
UA-3
1
2
UA-4
2
2
UA-5
2
1
2
2
107798
Figura 5.20: Onibus alcanca a UA-5.
Continuando o exemplo, o onibus percorre a rota alcancando a UA-1 e depois a
UA-2. Com isso, as atualizacoes nos pesos das UAs da linha sao realizadas. As
alteracoes no mapa podem ser observadas nas Figuras 5.21 e 5.22, respectivamente.
Pode-se notar na Figura 5.22 que os pesos das UAs 3 e 4 ja estao na metade do peso
maximo permitido na linha de onibus.
UA-1 UA-2
2
2
UA-3
1
2
UA-4
2
2
UA-5
2
1
2
2
966810
Figura 5.21: Onibus retorna ao ponto inicial.
58
UA-1 UA-2
2
2
UA-3
1
2
UA-4
2
2
UA-5
2
1
2
2
855109
Figura 5.22: Onibus chega na UA-2.
No momento que o onibus se aproxima da UA-5 novamente, a atualizacao nos
pesos se encarrega de decrementar novamente os pesos de todas as UAs. Em se-
guida o peso da UA-5 e incrementado e atinge o maximo permitido. Realizada a
atualizacao dos pesos das UAs, o sistema verifica que, novamente, a UA anterior a
UA-5 e a UA-2. Por consequencia a UA seguinte a UA-2 e a UA-5. Com isso, o
peso desses arcos se mantem, enquanto o peso dos outros arcos decresce novamente
de uma unidade.
Quando os arcos que indicam que a proxima UA da UA-2 e a UA-3 e que a anterior
a UA-5 e a UA-4, sao decrementados, eles atingem o valor zero. Por isso, esses dois
arcos sao excluıdas da lista. A exclusao desses arcos representa a concretizacao da
modificacao da rota. Isso pode ser afirmado pois apesar de as UAs 3 e 4 existirem
na lista de UAs da linha, elas ja nao sao alcancaveis a partir do ponto inicial da
linha de onibus. As modificacoes realizadas podem ser vistas na Figura 5.23.
UA-1 UA-2
2
2
UA-3
0
2
UA-4
2
2
UA-5
2
0
2
2
104498
Figura 5.23: Onibus se move ate UA-5. E a mudanca na rota e concretizada.
59
Com a rota do onibus concretizada, nao ocorre mais nenhuma alteracao nas in-
formacoes de proxima UA e UA anterior de nenhuma UA da rota. Todavia, o onibus
continua realizando a sua rota normalmente, e os pesos das UAs da linha sao atua-
lizados de acordo. Na Figura 5.24 esta o resultado da movimentacao do onibus ate
a UA-1, na Figura 5.25 o resultado da continuacao do movimento ate a UA-2 e na
Figura 5.26 o mapa resultante do movimento ate o ponto final da rota.
UA-1 UA-2
2
2
UA-3
2
UA-4
2
2
UA-5
2
2
2
3 93810
Figura 5.24: Onibus na UA-1.
UA-1 UA-2
2
2
UA-3
2
UA-4
2
2
UA-5
2
2
2
822109
Figura 5.25: Onibus na UA-2.
UA-1 UA-2
2
2
UA-3
2
UA-4
2
2
UA-5
2
2
2
101198
Figura 5.26: Onibus na UA-5.
60
Ao continuar o seu trajeto, o onibus chega na UA-1, e os pesos das UAs 3 e 4 ao
serem subtraıdos chegam a zero. Isso faz com que o mecanismo de limpeza da linha
de onibus exclua esses objetos da lista de UAs da linha. Portanto, pode-se observar
a funcao dos dois tipos de peso na aplicacao criada. O processo descrito pode ser
visto na Figura 5.27.
UA-30
UA-1 UA-2
2
2 2
UA-4
2
2
UA-5
2
2
2
90810
Figura 5.27: Onibus na UA-1. E exclusao de UAs 3 e 4.
Com a exclusao das UAs 3 e 4 da lista de UAs da linha de onibus, o valor maximo
dos pesos das UAs diminui, segundo a Equacao 5.1. Porem, o peso de cada UA so
sera atualizado, obedecendo o novo limite, quando o onibus alcancar cada UA. Esse
processo pode ser visto na Figura 5.28, onde o peso da UA-2 e atualizado para o
novo maximo. Apos os pesos de todas as UAs terem sido atualizados, a rota final
da linha de onibus, que pode ser vista na Figura 5.29, e alcancada.
UA-1 UA-2
2
2
UA-5
2
29 6 8
Figura 5.28: Onibus na UA-2. Atualizacao de peso para novo maximo.
UA-1 UA-2
2
2
UA-5
2
2546
Figura 5.29: Rota final da linha de onibus.
61
Com esse exemplo mostra-se que os mapas das linhas de onibus podem ser altera-
dos dinamicamente. Vale lembrar que a velocidade de concretizacao das alteracoes
pode ser configurada escolhendo o valor maximo dos pesos dos arcos das UAs.
62
Capıtulo 6
Resultados
Nesse capıtulo os resultados obtidos atraves de emulacao sao apresentados.
6.1 Ambiente de Testes
Figura 6.1: Ambiente de testes.
63
A Central e um computador de mesa, que possui o sistema operacional Debian
instalado, 8 GB de memoria RAM e processador Intel Core i7 860. Por outro lado, as
UAs e os onibus sao representados por roteadores sem-fio da marca D-Link, modelo
DIR-320. A Central e as UAs estao conectadas atraves de um roteador, tambem da
marca D-Link e modelo DIR-320, que foi configurado para funcionar como comuta-
dor. Ja a conexao das UAs e da Central com esse comutador e realizada por cabo
Ethernet. Esse modelo possui processador ARM de 240 MHz e 32 MB de memoria
RAM. Alem disso, possui uma entrada USB que pode ser usada para aumentar a
capacidade de armazenamento do roteador, que originalmente e de apenas 4 MB, ou
para instalar uma segunda interface de rede sem-fio. O sistema operacional usado
nos roteadores e o OpenWRT versao Backfire 10.03.1, uma distribuicao Linux para
dispositivos embarcados.
6.2 Linhas COPPEAD e Estacao UFRJ
Nesse teste, as rotas das linhas de onibus universitarias COPPEAD (Figura 6.2)
e Estacao UFRJ (Figura 6.3) foram simuladas. Essas linhas de onibus sao de cir-
culacao interna da UFRJ e servem alunos e funcionarios dessa universidade. Para
isso, definiu-se que no cenario do teste cada ponto de onibus das rotas, tem uma UA
instalada, nao existindo outras UAs fora desses pontos. Para que os testes realizados
se aproximassem da realidade, o roteador que representava os onibus estava conec-
tado via rede sem-fio ao roteador que fazia o papel das UAs, incluindo os possıveis
problemas causados pela rede sem-fio no teste. Porem, sem o agravante de um dos
roteadores estar em movimento.
A movimentacao do onibus pelas rotas foi simulada com o uso de um script no rote-
ador que representava os onibus. Esse script modificava os arquivos que armazenam
as informacoes dos onibus, UA atual, UA anterior, linha de onibus e identificador
do onibus, de forma programada. Em seguida, o script chama a aplicacao que envia
a mensagem de localizacao a Central. A Central, entao, recebe as mensagens dos
onibus como se eles realmente estivessem realizando as rotas.
64
Figura 6.2: Rota da linha de onibus universitaria COPPEAD.
As duas linhas juntas possuem um total de 22 pontos de onibus, e para o teste
condizer com a realidade das linhas, o tempo que um onibus gastava entre dois
pontos de onibus consecutivos das duas linhas foi medido experimentalmente com
um cronometro. Essa medicao foi realizada apenas uma vez, servindo apenas como
referencia para o teste ter conexao com a realidade. Esses tempos medidos foram
usados no script citado anteriormente, de maneira que a simulacao levasse em conta
nao so as rotas das linhas, mas tambem os intervalos de tempo inerentes a elas.
No teste, considerou-se a existencia de cinco onibus, todos eles iniciavam o tra-
jeto na linha COPPEAD, realizando a linha Estacao UFRJ em seguida. Um onibus
entrava no teste 5 minutos apos o anterior ter iniciado seu percurso. Uma vez que o
onibus iniciava o percurso do teste, este percurso era repetido indefinidamente. Os
onibus apos terminarem a linha Estacao UFRJ realizavam novamente a linha COP-
PEAD e assim sucessivamente. Isso e plausıvel, pois as duas linhas sao circulares,
isto e, o ponto final de uma e o ponto de origem da outra e vice-versa.
65
Figura 6.3: Rota da linha de onibus universitaria Estacao UFRJ.
O teste foi interrompido apos 11 mil mensagens terem sido enviadas pelos onibus,
o que equivale a cada um dos 5 onibus ter percorrido o trajeto com 22 pontos de
onibus 100 vezes. O teste durou 64 horas e 28 minutos e todas as mensagens foram
recebidas pela Central. As estimativas realizadas nao continham erros, como era
de se esperar, ja que os tempos de percurso do onibus nao variavam no teste, pois
eram previamente programados. As estatısticas coletadas do teste encontram-se
na Tabela 6.1. E interessante observar que o fato do tamanho das mensagens ser
pequeno evita os problemas decorrentes do movimento do onibus e do tempo de
contato entre onibus e UA ser limitado. O tempo de tratamento de mensagem tem
relacao direta com o numero de mensagens que o sistema desenvolvido e capaz de
tratar por segundo, e essa metrica sera melhor avaliada nos testes seguintes.
66
Tabela 6.1: Estatısticas do teste das linhas COPPEAD e Estacao UFRJ.
Estatısticas Media Desvio padrao
Tamanho de152,59 bytes 4,52 bytes
mensagens de localizacao
Tempo de tratamento2,039 ms 0,769 ms
de mensagens
6.3 Tempo de Tratamento de Mensagens de Lo-
calizacao
Para avaliar a metrica de tempo de tratamento de mensagens de localizacao,
varios testes foram realizados. Os testes tem a intencao de mostrar como essa
metrica, do programa da Central, se comporta perante a variacao dos parametros
do cenario. Para que os resultados avaliassem somente o programa, as simulacoes
foram feitas executando os scripts que realizavam o papel de onibus dentro do proprio
computador onde a Central executa, eliminando a influencia da rede nos testes.
Avaliar o tempo de tratamento de uma mensagem e importante pois esse tempo
tem relacao direta com o numero de mensagens que o sistema desenvolvido e capaz
de tratar por segundo. A partir desse numero, e possıvel avaliar se o sistema e capaz
ou nao de atender as exigencias de uma cidade, o que foi avaliado no ultimo teste
realizado.
Ao todo quatro simulacoes foram feitas, sendo tres delas avaliando a influencia
das caracterısticas do cenario de forma isolada e uma simulando as condicoes da
cidade do Rio de Janeiro. As caracterısticas do cenario que influenciam o sistema
foram:
1. Quantidade de onibus cadastrados no sistema;
2. Quantidade de linhas de onibus cadastradas no sistema;
3. Quantidade de UAs em uma linha de onibus do sistema.
Os graficos de todas as simulacoes mostram, para cada variacao do parametro da
simulacao, a media e o desvio padrao dos tempos de tratamento das mensagens.
67
6.3.1 Variacao da Quantidade de Onibus
No teste em que se avaliou a influencia da quantidade de onibus cadastrados no
sistema sobre o tempo de tratamento de mensagem, variou-se o numero de onibus
cadastrados no sistema de 1000 ate 8000 onibus, incrementando de 1000 em 1000. O
valor maximo foi definido por se aproximar do numero de onibus medio em operacao
na cidade do Rio de Janeiro em 2011, que era de 8413 [33].
Os onibus foram cadastrados por um script que enviava uma mensagem contendo
o identificador do novo onibus, a linha pre-estabelecida usada no teste e a primeira
UA da linha como ponto atual. A Central ao receber essa mensagem cadastrava os
onibus no sistema. Apos todos os onibus terem sido cadastrados, escolheu-se um
deles para realizar a rota da linha pre-estabelecida. A rota da linha possuıa 5 UAs
cadastradas e o onibus percorreu a rota 10 vezes seguidas. Quando o onibus chegava
a proxima UA ele enviava a mensagem de localizacao a Central, que entao tratava
a mensagem e media o tempo do tratamento dela.
Todo o processo foi realizado tres vezes para cada quantidade de onibus escolhida,
resultando em 150 mensagens para cada valor. E interessante notar que o teste visa
avaliar a influencia do parametro variado no tempo de tratamento de mensagens dos
onibus ja cadastrados, e nao o tempo para cadastrar um novo onibus no sistema.
Os resultados do teste podem ser observados na Figura 6.4.
Pode-se notar pelo grafico na Figura 6.4 que a media e o desvio padrao do tempo
de tratamento por mensagem aumentam com o numero de onibus cadastrados. Alem
disso, a curva obtida se assemelha a uma reta com as variacoes nos tempos medios
entre dois pontos consecutivos simulados em torno de 5 ms. Esse teste apesar de
demonstrar o comportamento do sistema, nao e de senso pratico, pois os mais de
1000 onibus foram cadastrados na mesma linha de onibus, o que nunca acontece
na vida real. O resultado foi o alongamento do calculo da estimativa da linha de
onibus, ja que a estimativa ao ser calculada durante o tratamento das mensagens
avalia todos os onibus cadastrados na linha sendo estimada.
68
0
10
20
30
40
50
60
0 1000 2000 3000 4000 5000 6000 7000 8000 9000
T
e
m
p
o
d
e
T
r
a
t
a
m
e
n
t
o
p
o
r
M
e
n
s
a
g
e
m
(
m
s
)
Número de Ônibus
Figura 6.4: Variacao da quantidade de onibus no sistema.
6.3.2 Variacao da Quantidade de Linhas de Onibus
No teste em que se avaliou a influencia da quantidade de linhas de onibus cadas-
tradas no sistema, variou-se o numero de linhas de onibus cadastradas de 100 ate
800, incrementando de 100 em 100. O valor maximo foi definido por se aproximar
do numero de linhas de onibus em operacao na cidade do Rio de Janeiro em 2011,
que era de 822 [33].
Durante esse teste, somente um onibus foi cadastrado no sistema para eliminar a
influencia desse parametro. As linhas foram cadastradas por um script que enviava
uma mensagem contendo o identificador do onibus pre-estabelecido, a nova linha
que o onibus estava realizando e a primeira UA da nova linha como ponto atual. A
Central ao receber essa mensagem identificava que o onibus havia mudado de linha
e cadastrava as novas linhas de onibus no sistema. Apos todas as linhas terem sido
cadastradas, escolheu-se uma para o onibus percorrer. A rota da linha possuıa 5 UAs
cadastradas e o onibus realizou a rota 10 vezes consecutivas. Da mesma forma que
no teste anterior, quando o onibus alcancava a proxima UA ele enviava a mensagem
de localizacao a Central, que tratava a mensagem e media o tempo do tratamento
dela.
69
Assim como no teste anterior, todo o processo foi realizado tres vezes para cada
quantidade de linhas de onibus, resultando em 150 mensagens para cada valor.
Assim como o teste anterior, o teste tem a intencao de avaliar como a alteracao
do numero de linhas de onibus inseridas no sistema afeta o tempo de tratamento
de mensagens dos onibus percorrendo a rota, e nao o tempo para cadastrar uma
nova linha de onibus no sistema. Os resultados do teste podem ser observados na
Figura 6.5.
0.05
0.1
0.15
0.2
0.25
0.3
0 100 200 300 400 500 600 700 800 900
T
e
m
p
o
d
e
T
r
a
t
a
m
e
n
t
o
p
o
r
M
e
n
s
a
g
e
m
(
m
s
)
Número de Linhas de Ônibus
Figura 6.5: Variacao da quantidade de linhas de onibus no sistema.
Pelo grafico na Figura 6.5, observa-se que a media e o desvio padrao aumentam
com o numero de linhas de onibus cadastradas no sistema, contudo para os valores
simulados o crescimento apresentado nao impediu a escalabilidade.
6.3.3 Variacao da Quantidade de UAs em uma Linha de
Onibus
Nesse teste, variou-se o numero de UAs numa linha de 10 ate 100, com incrementos
de 10 em 10. Durante o teste, para eliminar da melhor forma possıvel a influencia
dos outros parametros, apenas uma linha de onibus e um onibus foram cadastrados.
70
As UAs foram inseridas na linha atraves do envio das mensagens do onibus per-
correndo a rota pela primeira vez. Apos a rota da linha ficar pronta, fez-se o onibus
percorrer a rota criada 10 vezes seguidas. Quando o onibus aparecia na proxima
UA ele enviava a mensagem de localizacao a Central, que tratava a mensagem e
cronometrava seu tempo do tratamento.
Assim como nos dois testes anteriores, todo o processo foi realizado tres vezes para
cada variacao de UAs por linha. Como o numero de UAs na rota percorrida varia,
o numero de mensagens, e consequentemente de tempos medidos, para cada valor
tambem se modifica, aumentando com o numero de UAs na rota. Assim como os
testes anteriores, o objetivo do teste e avaliar a influencia da variacao do parametro
em questao no tempo de tratamento de mensagens dos onibus percorrendo a rota, e
nao o tempo necessario para inserir uma UA numa linha de onibus. Os resultados
do teste podem ser observados na Figura 6.6.
0
0.5
1
1.5
2
2.5
0 20 40 60 80 100
T
e
m
p
o
d
e
T
r
a
t
a
m
e
n
t
o
p
o
r
M
e
n
s
a
g
e
m
(
m
s
)
Número de Unidades de A ostamento
Figura 6.6: Variacao da quantidade de UAs no sistema.
Na Figura 6.6, observa-se que a media dos tempos de tratamento de mensagem
aumenta com o numero de UAs presentes em uma dada linha de onibus. Entretanto,
para os valores simulados, o crescimento apresentado nao impediu a escalabilidade,
71
com o tempo medio de tratamento por mensagem permanecendo abaixo de 2,5 ms.
6.3.4 Cenario Rio de Janeiro
O ultimo teste simula as condicoes da cidade do Rio de Janeiro, sendo cadastradas
no sistema 800 linhas de onibus, cada uma com 10 onibus, totalizando os 8000 onibus
que se aproximam do numero de onibus da cidade. Como o numero de UAs inseridas
em uma linha pode variar, por exemplo, devido a variacao de pontos de onibus nas
linhas, decidiu-se variar o numero de UAs como no teste anterior, de 10 a 100 UAs
em uma linha de onibus variando de 10 em 10.
Como nos testes anteriores, cadastraram-se as linhas de onibus e os onibus, e
em seguida uma das linhas de onibus teve sua rota criada com o numero de UAs
estabelecido. Apos a criacao da rota, um dos onibus percorreu a mesma 10 vezes
consecutivas, enviando mensagens para a Central ao trocar de UA. A Central tratou
as mensagens e mediu o tempo gasto no tratamento delas.
O processo foi repetido tres vezes para cada variacao de UAs. Os resultados do
teste podem ser observados na Figura 6.7.
1
2
3
4
5
6
7
8
0 20 40 60 80 100
T
e
m
p
o
d
e
T
r
a
t
a
m
e
n
t
o
p
o
r
M
e
n
s
a
g
e
m
(
m
s
)
Número de Unidades de A ostamento
Figura 6.7: Cenario Rio de Janeiro.
72
Pelo grafico observa-se que a media dos tempos de tratamento de mensagem au-
menta com o numero de UAs presentes numa dada linha de onibus. Com os dados
obtidos no grafico, pode-se inferir que apenas um computador semelhante ao usado
executando a aplicacao desenvolvida e suficiente para monitorar e estimar toda a
cidade do Rio de Janeiro dado que o tempo de tratamento por mensagem nao passou
de 7 ms. Essa inferencia e realizada atraves da suposicao de que os aproximada-
mente 8000 onibus da cidade levam pelo menos um minuto para alcancar a proxima
UA da rota. Com isso, o programa teria 60 segundos para tratar as 8000 mensagens.
Considerando o pior caso do grafico da Figura 6.7, ou seja, cada linha de onibus com
100 UAs, o tratamento de cada mensagem levaria em media, aproximadamente, 7
milissegundos. Dividindo-se os 60 segundos por esse tempo de tratamento, obtem-se
uma taxa de aproximadamente 8500 mensagens tratadas por minuto. Portanto, to-
das as mensagens que fossem enviadas a Central conseguiriam ser tratadas, mesmo
considerando o pior caso para todas as linhas de onibus da cidade, o que mostra a
capacidade da aplicacao criada.
73
Capıtulo 7
Conclusoes e Trabalhos Futuros
O objetivo deste projeto final foi propor e desenvolver um sistema que, utilizando
roteadores sem-fio instalados nos onibus e nos pontos de onibus, fosse capaz de
rastrear e estimar os horarios que os onibus passam nos pontos requisitados pelos
usuarios. Para isso, foi desenvolvido um servico de ITS de localizacao automatica
de veıculos para rastrear os onibus, no qual se utilizou a tecnica de localizacao
por proximidade, considerando os pontos de acesso do padrao IEEE 802.11 como
referencia. Apesar de o sistema AVL criado ser focado no rastreamento de veıculos
de transporte publico, a aplicacao de localizacao projetada tambem pode ser usada
para veıculos de uso pessoal.
O servico proposto de estimativa de chegada de onibus aos pontos de onibus
pode ser desenvolvido a partir de quatro formas de calculo, sendo todas elas basea-
das em medias de informacoes anteriores. Uma pagina na Internet foi criada para
disponibilizar as estimativas calculadas para os usuarios dos meios de transporte
publico.
Neste projeto de fim de curso, uma forma de criacao e manutencao de mapas digi-
tais dinamicos, que se adaptam a modificacoes nas rotas monitoradas, para cenarios
semelhantes tambem foi proposta e desenvolvida. O funcionamento do mecanismo
proposto foi descrito passo a passo em dois exemplos, um descrevendo a criacao de
um mapa digital dinamico e outro descrevendo a reacao do mapa a uma modificacao
na rota.
74
As simulacoes realizadas incluıram um teste de longa duracao, mostrando a inte-
gridade do sistema como um todo. Alem disso, o tempo de tratamento das mensa-
gens de localizacao, que inclui desde a localizacao do veıculo, passando pela criacao e
manutencao do mapa, ate o calculo das estimativas, foi avaliado frente as principais
variaveis do sistema. Para concluir os testes, uma simulacao com parametros simila-
res aos encontrados na cidade do Rio de Janeiro foi realizada. Nessa simulacao havia
8000 onibus e 800 linhas de onibus cadastrados no sistema, e variou-se entre 10 e 100
o numero de unidades de acostamento por linha de onibus. Os resultados obtidos
mostraram que a aplicacao criada atenderia, mesmo no pior caso, as exigencias de
uma cidade grande como o Rio de Janeiro.
Como trabalhos futuros, seria interessante obter mais dados praticos dos tempos
gastos pelos onibus para percorrer trechos das linhas de onibus. De posse de mais
dados seria possıvel avaliar a precisao dos diferentes mecanismos de estimativa cri-
ados, e tambem como esses mecanismos reagem a diferentes condicoes de transito,
como um engarrafamento. Alem disso, seria interessante colocar o sistema em fun-
cionamento, instalando UAs nos pontos de onibus e roteadores sem-fio nos onibus
internos da UFRJ para, alem de avaliar o funcionamento do sistema criado em um
cenario real, aumentar a qualidade de servico dos onibus internos, beneficiando os
usuarios.
75
Referencias Bibliograficas
[1] PADMANABAN, R. P. S., DIVAKAR, K., VANAJAKSHI, L., et al., “Develop-
ment of a real-time bus arrival prediction system for Indian traffic conditions”,
Intelligent Transport Systems, IET, v. 4, n. 3, pp. 189–200, 2010.
[2] Instituto Municipal de Urbanismo Pereira Passos, “Total de veıculos terrestres
automotores (frota ativa) - Municıpio do Rio de Janeiro - 1994 - 2011 (Tabela
No 1253)”, Armazem de Dados - Informacoes sobre a cidade do Rio - http:
//www.armazemdedados.rio.rj.gov.br/, 2011, (Acesso em 12 Junho 2013).
[3] WEILAND, R. J., PURSER, L. B., “Intelligent transportation systems”, Trans-
portation in the New Millennium, p. 3, 2000.
[4] Bus Standards Program and Bus Rapid Transit Working Group, Recommended
Practice for Implementing BRT Intelligent Transportation Systems, Report,
American Public Transportation Association, 2010.
[5] RITER, S., MCCOY, J., “Automatic vehicle location - An overview”, Vehicular
Technology, IEEE Transactions on, v. 26, n. 1, pp. 7–11, 1977.
[6] SKABARDONIS, A., “Traffic Signal Control Systems”. In: Assessing the Be-
nefits and Costs of ITS, v. 10, Transportation Research, Economics and Policy,
Springer US, pp. 131–144, 2004.
[7] AMPELAS, A., “Automatic fare collection”. In: Intelligent Transportation Sys-
tems, 2001. Proceedings. IEEE, pp. 1164–1166.
[8] BALASUBRAMANIAN, N., BALASUBRAMANIAN, A., VENKATARA-
MANI, A., “Energy consumption in mobile phones: a measurement study and
76
implications for network applications”. In: Proceedings of the 9th ACM SIG-
COMM conference on Internet measurement conference, IMC ’09, pp. 280–293,
2009.
[9] BusTV, “A Rede BusTV”, http://bustv.com.br/portal/a-rede-bustv,
2013, (Acesso em 9 Julho 2013).
[10] FENG, H., LULU, L., HENG, Y., et al., “Bus Monitoring System Based on
ZigBee and GPRS”. In: Computer Distributed Control and Intelligent Environ-
mental Monitoring (CDCIEM), 2012 International Conference on, pp. 178–181,
2012.
[11] CACERES, M., SOTTILE, F., SPIRITO, M., “WLAN-Based Real Time Vehi-
cle Locating System”. In: Vehicular Technology Conference. VTC Spring 2009.
IEEE 69th, pp. 1–5.
[12] DOD, U., “Global positioning system standard positioning service performance
standard”, 2008.
[13] MANOLIS, K., KWSTIS, D., “Intelligent transportation systems - travelers’
information systems the case of a medium size city”. In: Mechatronics. ICM
’04. Proceedings of the IEEE International Conference on, pp. 200–204, 2004.
[14] LIN, W.-H., ZENG, J., “Experimental study of real-time bus arrival time pre-
diction with GPS data”, Transportation Research Record: Journal of the Trans-
portation Research Board, v. 1666, n. 1, pp. 101–109, 1999.
[15] KARBASSI, A., BARTH, M., “Vehicle route prediction and time of arrival
estimation techniques for improved transportation system management”. In:
Intelligent Vehicles Symposium, 2003. Proceedings. IEEE, pp. 511–516, 2003.
[16] D’ANGELO, M. P., AL-DEEK, H. M., WANG, M. C., “Travel-time prediction
for freeway corridors”, Transportation Research Record: Journal of the Trans-
portation Research Board, v. 1676, n. 1, pp. 184–191, 1999.
[17] ISHAK, S., AL-DEEK, H., “Performance Evaluation of Short-Term Time-Series
Traffic Prediction Model”, Journal of Transportation Engineering, v. 128, n. 6,
pp. 490–498, 2002.
77
[18] RICE, J., VAN ZWET, E., “A simple and effective method for predicting travel
times on freeways”, Intelligent Transportation Systems, IEEE Transactions on,
v. 5, n. 3, pp. 200–207, 2004.
[19] FRECHETTE, L. A., KHAN, A. M., “Bayesian regression-based urban traffic
models”, Transportation Research Record: Journal of the Transportation Rese-
arch Board, v. 1644, n. 1, pp. 157–165, 1998.
[20] CHIEN, S., DING, Y., WEI, C., “Dynamic Bus Arrival Time Prediction with
Artificial Neural Networks”, Journal of Transportation Engineering, v. 128,
n. 5, pp. 429–438, 2002.
[21] VANAJAKSHI, L., RILETT, L., “Support Vector Machine Technique for the
Short Term Prediction of Travel Time”. In: Intelligent Vehicles Symposium,
2007 IEEE, pp. 600–605, 2007.
[22] JEONG, R., RILETT, L., “Bus arrival time prediction using artificial neural
network model”. In: Intelligent Transportation Systems, 2004. Proceedings. The
7th International IEEE Conference on, pp. 988–993, 2004.
[23] VANAJAKSHI, L., SUBRAMANIAN, S., SIVANANDAN, R., “Travel time
prediction under heterogeneous traffic conditions using global positioning sys-
tem data from buses”, IET intelligent transport systems, v. 3, n. 1, pp. 1–9,
2009.
[24] SHALABY, A., FARHAN, A., “Bus travel time prediction model for dynamic
operations control and passenger information systems”, Transportation Rese-
arch Board, p. 16, 2003.
[25] CHENG, S., “Bus arrival time prediction model based on APC data”, 6th
Advanced Forum on Transportation of China (AFTC 2010), pp. 165–169(4),
2010.
[26] DA SILVA, V. B., DA SILVA, F. O., CAMPISTA, M. E. M., et al., “Roteamento
Baseado na Trajetoria para Redes Veiculares Desconectadas com Multiplos Ga-
teways”, XXXI Simposio Brasileiro de Redes de Computadores e Sistemas Dis-
tribuıdos - SBRC, pp. 1038–1051, 2013.
78
[27] DA SILVA, V. B., DA SILVA, F. O., CAMPISTA, M. E. M., et al., “A
Trajectory-Based Approach to Improve Delivery in Drive-Thru Internet Sce-
narios”, Workshop on Emerging Vehicular Networks: V2V/V2I and Railroad
Communications - IEEE International Conference on Communications, pp.
499–504, 2013.
[28] SIM, M. L., NEKOVEE, M., KO, Y. F., “Throughput analysis of Wi-Fi based
broadband access for mobile users on the highway”. In: Networks, 2005. Jointly
held with the 2005 IEEE 7th Malaysia International Conference on Communi-
cation., 2005 13th IEEE International Conference on, v. 1, p. 6, 2005.
[29] JUNIOR, J. G. R., QUINTANILHA, I. M., CAMPISTA, M. E. M., et al.,
“Sistema para Monitoramento Descentralizado de Transito Baseado em Redes
Veiculares Infraestruturadas”, XXXI Simposio Brasileiro de Redes de Compu-
tadores e Sistemas Distribuıdos - SBRC, pp. 863–876, 2013.
[30] Carlos A. Maziero, “The ARP tool”, http://dainf.ct.utfpr.edu.br/
~maziero/doku.php/software:arp_tool, 2009, (Acesso em 3 Julho 2013).
[31] apaloczi, “OpenWRT c,c++ programing”, http://fleshandmachines.
wordpress.com/2011/08/22/openwrt-cc-programing/, 2011, (Acesso em 3
Julho 2013).
[32] Google, “Google Maps Javascript API V3”, https://developers.google.
com/maps/documentation/javascript/reference, 2013, (Acesso em 03 Ju-
lho 2013).
[33] Instituto Municipal de Urbanismo Pereira Passos, “Total de linhas, frota ope-
rante, passageiros transportados, viagens realizadas,quilometragem coberta,
combustıvel utilizado e pessoal ocupado pelo sistema de onibus - Municıpio
do Rio de Janeiro - 1994 - 2011 (Tabela No 1736)”, Armazem de Dados - In-
formacoes sobre a cidade do Rio - http://www.armazemdedados.rio.rj.gov.
br/, 2011, (Acesso em 12 Junho 2013).
79
Apendice A
Propriedades da Rede de Petri
A.1 Descricao da Rede de Petri para Simulador
ARP
Para inserir a rede de Petri no simulador utilizado, e necessario representar a rede
em forma de texto. Essa representacao encontra-se abaixo:
NET TRABALHO;
NODES
P2, P3, P5, P6, P7, P8, P9, P11, P12, P13, P14, P16, P17 : PLACE;
P1: PLACE(1);
P4: PLACE(1);
P10: PLACE(2);
P15: PLACE(2);
T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12: TRANSITION;
STRUCTURE
T1: (P1,P2) ,(P1,P3);
T2: (P4) ,(P5);
T3: (P5) ,(P2,P6);
T4: (P3,P6) ,(P7,P8);
T5: (P7,P9) ,(P4);
T6: (P8,P10) ,(P9,P11);
T7: (P11) ,(P12);
80
T8: (P12) ,(P10);
T9: (P10,P13) ,(P10,P14);
T10: (P15) ,(P16);
T11: (P16) ,(P13,P17);
T12: (P14,P17) ,(P15);
ENDNET.
A.2 Saıda da Analise da Rede
A rede e limitada:
Net under analysis is limited.
Null places (M = 0): {}
Binary places : {P2, P3, P5, P6, P7, P8, P9, P1, P4}
k-Bounded places : {2* P11, 2* P12, 2* P13, 2* P14, 2* P16, 2* P17, 2*
P10, 2* P15}
Unbounded places : {}
A rede nao e estritamente conservativa.
A rede e viva, ou seja, nao possui bloqueios.
Net under analysis is live.
Live Tr. : {all}
"Almost-live" Tr.: {all}
Non-fired Tr. : {}
No live-locks detected.
No deadlocks detected.
A rede e reinicializavel, isto e, partindo de qualquer marcacao valida, ela sempre
pode voltar para a marcacao inicial.
Invariantes de transicao:
Transition invariant basis:
BI1 :{T1, T2, T3, T4, T5, T6, T7, T8}
BI2 :{T10, T11, T12, T9}
81
Invariantes de lugar:
Place invariant basis:
BI1 :{P2, P3, -P6}
BI2 :{P13, P14, -P17}
BI3 :{P7, -P8, -P9}
BI4 :{P1}
BI5 :{P2, P3, P5, P7, P4}
BI6 :{P11, P12, P10}
BI7 :{P13, P14, P16, P15}
Minimum positive place invariants for this net:
IL1 :{P11, P12, P10}
IL2 :{P13, P14, P16, P15}
IL3 :{P16, P17, P15}
IL4 :{P2, P3, P5, P8, P9, P4}
IL5 :{P5, P6, P8, P9, P4}
IL6 :{P5, P6, P7, P4}
IL7 :{P1}
IL8 :{P2, P3, P5, P7, P4}
82
