easy-City: Sistema de pesquisa de trajectos em transportes

easy-City: Sistema de pesquisa de trajectos em
transportes colectivos por Bluetooth
Fábio Pereira
Instituto Superior Técnico
O sistema easy-City pretende resolver o problema da Optimização de Trajectos em Transportes Públicos. Para tal, o easy-City aproveita as propriedades de mobilidade dos utentes dos transportes públicos
para estabelecer uma rede tolerante a atrasos entre os seus telemóveis e
entre os telemóveis e uma infra-estrutura simples. Pretende-se disseminar informação sobre trajectos, de forma a esta estar disponível quando e
onde necessária, para informar os utentes daqueles trajectos que melhor
se adequam aos seus requisitos (por exemplo, origem, destino, rapidez,
custo monetário, etc.).
Resumo
Keywords:
Optimização de Trajectos em Transportes Públicos, Bluetooth, Delay-
Tolerant Networks, transportes públicos, Computação Ubíqua, disseminação de
informação
1
Introdução
Com o aumento da densidade populacional junto aos grandes centros urbanos, o
problema da mobilidade assume, hoje, maior impacto nos índices de qualidade
de vida de uma cidade. Aumentam as exigências no fornecimento de transportes
colectivos e a complexidade das redes metropolitanas, dicultando a sua utilização [8]. Por exemplo, na Figura 1 encontram-se traçados alguns dos percursos,
existentes entre a Praça do Comércio e a Praça Duque do Saldanha, em Lisboa [7, 18, 27, 33]. Como se pode ver, existem pelo menos 9 percursos possíveis
entre estes dois pontos da cidade de Lisboa. Estes percursos variam relativamente
ao meio de transporte (metro, autocarro, eléctrico, barco, etc.), previsão de duração, número de transbordos, operadores e preços de bilhetes/passes necessários.
Todos os aspectos referidos são importantes para os utentes dos transportes públicos e inuenciam as suas escolhas de uma forma decisiva. Uma escolha errada
causa transtorno ao utente, por exemplo, porque acabou por gastar mais dinheiro
do que o necessário, ou chegar atrasado a uma reunião.
O que se pretende neste trabalho é resolver o problema da
Trajectos em Transportes Públicos.
Optimização de
Esse problema descreve-se da seguinte
forma: dado um utente, num dado local A, que se quer deslocar por transportes
públicos (de vários modos e operadores) para um destino B, como permitir que
ele saiba qual melhor trajecto entre A e B? A solução deve cumprir os seguintes
objectivos:
2
Mapa da cidade de Lisboa com nove percursos entre a Praça do Comércio e
a Praça Duque do Saldanha traçados.
Figura 1.
o trajecto escolhido deve ser o mais rápido, ou barato, ou com o menor transbordo, ou uma conjugação apropriada destes factores, consoante as preferências do utente;
a informação deve ser facilmente acessível ao utilizador idealmente no local
A, obtida em tempo curto, e deve acompanhar o utente ao longo dos seus
trajectos usando hardware comum (por exemplo, telemóvel).
Para atingir estes objectivos é necessário ultrapassar alguns desaos associados à natureza da informação necessária para tomar uma boa decisão de trajecto.
Esta informação tem, tipicamente, as seguintes características:
complexa, consequência das características das redes de transportes;
dinâmica, devido a imprevistos (por exemplo, acidentes ou perturbações) e
auências pouco comuns (quer elevadas, quer reduzidas);
muitas vezes indisponível no local A, por escassez de fontes ou porque é
relacionada com um local distante de A, sendo necessário transportá-la;
disseminação pela rede de transportes cara (para o utilizador e para os operadores);
proveniente de diversos operadores, que tipicamente não cooperam entre si
e entre os quais os utentes podem fazer uma ponte.
Por exemplo, se um utente se encontrar na Praça do Comércio e se quiser
deslocar-se para a Praça Duque do Saldanha, o que se pretende é fornecer-lhe o
3
trajecto mais rápido, barato ou com menor transbordo (de acordo com os seus
requisitos) entre esses dois pontos da rede de transportes. Mais, pretende-se que
essa informação seja facilmente acessível ao utente no seu ponto de origem e, se
possível, que o acompanhe ao longo da sua viagem. Não é fácil cumprir esses
objectivos.
A complexidade e quantidade avultada de informação são desaos, visto que
existem no mínimo 9 alternativas neste exemplo, que ainda podem ser conjugadas.
O dinamismo dos acontecimentos é, igualmente, um desao. Por exemplo,
depois de escolhido o melhor trajecto pode ocorrer um acidente nesse percurso o
que poderá ter implicações negativas e poderá invalidar as suas características.
Relacionado, também, com o dinamismo e com as características da rede de
transportes, por vezes os alertas de imprevistos e informações de trajectos não
estão disponíveis no local de origem. Por exemplo, se recuarmos ao cenário de
acidente no trajecto mais rápido até à Praça Duque de Saldanha, tipicamente o
utente apenas tem conhecimento desse facto quando algo começa a correr mal
(por exemplo, se encontra num engarrafamento causado pelo acidente).
Ainda é importante que o utente, quando se encontre na Praça do Comércio,
conheça as diversas opções em termos de operadores para chegar à Praça Duque
de Saldanha. Isto é um grande desao porque as soluções existentes, muitas
vezes, são exclusivas de cada operador e fornecem informações apenas acerca
desse operador, falhando assim o objectivo de fornecer a melhor opção possível
ao utente.
1.1
Soluções Actuais
Uma solução genérica para o problema da Optimização de Trajectos em Transportes Públicos encontra-se na Figura 2. As principais entidades num sistema
que resolva o problema são: Cliente, Optimizador, Informação Estática, Informação Dinâmica, Agregador de Dados, Sensores e Localizador. O Cliente é a
plataforma de acesso ao Optimizador. O Optimizador é o subsistema responsável pelo cálculo do melhor trajecto, tomada de decisões e por respostas a pedidos
do Cliente. Informação Estática e Informação Dinâmica são duas fontes utilizadas pelo Optimizador responsáveis por, respectivamente, fornecer informação
estática e dinâmica.
Exemplo de informação estática são horários, trajectos, preços e durações
previstas. Este tipo está disponível de diversas formas. Algumas paragens ou
estações possuem placares para informar os seus utentes. Nos dias de hoje, a
Internet é outro meio de consulta possível, como é visível, por exemplo, nas páginas Web da Carris [7] e Metropolitano de Lisboa [18]. Informação dinâmica
consiste em informação em tempo real, como por exemplo, atrasos ou adiantamentos relativamente aos horários pré-denidos, auência pouco comum de
tráfego (excepcionalmente elevada ou reduzida), acidentes, etc..
A informação dinâmica é captada por Sensores espalhados geogracamente.
O Agregador de Dados organiza a informação recolhida pelos sensores para ser
utilizada pelo Optimizador. Finalmente, o Localizador fornece ao Cliente a sua
4
Solução genérica para o problema da Optimização de Trajectos em Transportes Públicos
Figura 2.
localização actual, bem como aos Sensores, isto pode ser importante para ns de
orientação, apoio ao utente, ou para cálculos algorítmicos de tempos de trajectos.
Já existem várias soluções em uso que seguem esta solução genérica ou variantes mais simplicadas da mesma.
Desde o surgimento das primeiras redes de transportes públicos, existem Optimizadores de Trajectos. O próprio
utente
é o Optimizador de Trajectos mais
antigo. As entidades Cliente e Optimizador podem ser associados a uma entidade
só: o cérebro humano. Quanto a fontes de informação estática são exemplos os
placares de horários, mapas de rede, etc. A informação dinâmica pode ser muitas
vezes inferida pelos nossos sensores: os sentidos (por exemplo, visionamento de
engarrafamentos ou acidentes, informação boca-a-boca, etc.).
Este sistema é falível pois não cumpre os objectivos estabelecidos e não consegue superar todos os desaos. Por exemplo, o trajecto escolhido pelo utente
pode não ser o mais rápido, barato ou com menor transbordo. Isto acontece devido à complexidade, dinamismo, ou, simplesmente, ausência de informação.
As operadoras aperceberam-se das limitações dos utentes como Optimizadores de Trajectos. Identicaram, então, que as principais causas de erros são
o dinamismo e a ausência de informação. Portanto, optaram por fornecer mais
e melhor informação através de
estruturas.
soluções implementadas nas suas infra-
Neste tipo de soluções, o utente continua a ser o Cliente e Optimi-
zador. A fonte de informação estática continua a estar relacionada com mapas
5
de rede, horários axados em paragens, etc. A diferença reside na fonte de informação dinâmica. Nesta abordagem, as operadoras distribuem Sensores pela
rede para captar e inferir informações em tempo real. O Agregador de Dados
é, tipicamente, uma entidade que faz o tratamento da informação gerada pelos
sensores e a sua distribuição para diversas fontes acessíveis ao Optimizador. As
fontes de informação dinâmica podem assumir bastantes formatos, por exemplo,
placares electrónicos ou serviços de informação por SMS ou email. Existem muitos sistemas implementados que seguem esta abordagem. Por exemplo, o SAEIP
(Sistema de Ajuda à Exploração e Informação aos Passageiros) e o SIP (Sistema
de Informação ao Passageiro) da Carris [7] utilizam infra-estrutura. A Régie Autonome des Transports Parisiens (ou RATP [26]) também faz uso deste género
de solução.
No entanto, esta abordagem falha, igualmente, em atingir os objectivos e ultrapassar os desaos estabelecidos. A optimização continua a ser realizada pelo
utente, o que mantém uma probabilidade alta de decisões erradas devido à complexidade das informações que têm de ser consideradas. Também é importante
notar que tipicamente estas soluções são exclusivas de cada operadora. Isto faz
com que as informações fornecidas sejam apenas sobre a sua oferta, ou seja,
não é fornecida toda a informação possível para ser tomada a melhor opção na
perspectiva do utente. Ainda, devido à necessidade de introdução de Sensores,
Agregadores de Dados e fontes de informação dinâmica (por exemplo, ecrãs), os
custos monetários destas soluções são elevados. Consequência deste custo elevado, muitas vezes estes sistemas não estão implementados em toda a rede ou
as fontes de informação dinâmica são reduzidas, falhando por isso no objectivo
de a informação ser facilmente acessível ao utente.
Com a evolução da tecnologia e a globalização da Internet, surgiram várias
soluções baseadas na Web.
Esta abordagem é consideravelmente diferente
das anteriores. O Cliente é uma aplicação (por exemplo, um navegador Web ou
um programa especico). Em algumas soluções o Cliente usa um Localizador
(por exemplo, GPS,
beacons
com infra-estrutura, etc.) para simplicar a sua
utilização. O Optimizador é um serviço Web público. Estas soluções utilizam
fontes de informação estática e/ou fontes de informação dinâmica. As soluções
que utilizam fontes de informação dinâmica são híbridas, na medida em que,
tipicamente, as informações são inferidas e agregadas por uma infra-estrutura.
Existem inúmeras soluções que seguem uma abordagem baseada na Web. Os
serviços oferecidos pelo RATP (página Web, aplicações para telemóveis) são um
exemplo claro de uma solução híbrida (Web+infra-estrutura). Enquanto que, o
Transporlis [33], o Google Maps [11] são exemplos de soluções Web que utilizam
apenas fontes de informação estática.
Contudo, este género de abordagem tem limitações consideráveis. A principal
desvantagem é consequência da natureza destes sistemas, isto porque a informação não está facilmente acessível aos utentes, sendo necessária uma ligação à
Internet para fazer o seu acesso. Mesmo com o aparecimento da Internet Móvel,
6
1
tipicamente este acesso é caro . Os sistemas baseados na Web que utilizam apenas fontes de informação estática falham por não contarem com o dinamismo da
informação nas suas predições, enquanto que os sistemas que utilizam as duas
diferentes fontes herdam algumas desvantagens das soluções de infra-estrutura.
Os Optimizadores de Trajectos não são ferramentas de utilidade exclusiva
nos transportes públicos. Interessa mencionar a existência de
res móveis (ou VANETs),
redes veicula-
pois o paradigma utilizado é interessante para a
resolução da Optimização de Trajectos em Transportes Públicos, embora com
objectivos, desaos e restrições diferentes. VANETs são redes ad-hoc móveis nas
quais os nós são veículos. Nos sistemas baseados neste tipo de redes, o Cliente
é, tipicamente, uma aplicação acedida pelo condutor, o Optimizador é uma unidade de processamento instalada no veículo, as fontes usadas são de Informação
Estática e Informação Dinâmica. A principal diferença para as abordagens anteriores consiste na natureza dos Sensores. Todos os veículos são consumidores
e também produtores de informação, ou seja, também são Sensores. Agregadores de Dados também podem existir nestes sistemas. Um aspecto importante
nas VANETs é que por vezes, em algumas soluções, são introduzidos Sensores
de infra-estrutura (ou
Road-Side Units )
para emissão de alertas de imprevistos
e para uma operação em ambientes mais esparsos em termos de Sensores móveis. Existe investigação em VANETs aplicadas a transportes públicos, como por
exemplo em [1, 10].
Porém, como foi já referido, estes sistemas não são apropriados para a resolução do problema. Isto acontece porque os objectivos e desaos são consideravelmente diferentes. Por exemplo, numa VANET os utentes deslocam-se sobre infra-estruturas xas (estradas, viadutos) que não mudam frequentemente,
logo existem padrões mais previsíveis de mobilidade, não existem limitações de
bateria, que caracterizam dispositivos móveis que os utentes carregam consigo
(e.g., telemóveis), e espaço físico ou portabilidade não são problemas, o que permite hardware maior e com mais capacidade. Ora, estes são desaos importantes
quando se quer desenvolver um sistema de fácil acesso aos utentes de transportes
públicos.
1.2
Solução
O easy-City é um optimizador de trajectos em transportes públicos baseado em
Bluetooth [29] em que informação é propagada automaticamente entre utilizadores através dos seus telemóveis aquando de aproximações entre os mesmos.
O objectivo do easy-City é aproveitar as vantagens dos dois modelos de comunicação: utilizador-utilizador, infra-estrutura-utilizador, para conseguir eliminar
as limitações e desvantagens de cada um deles, resolvendo o problema da Optimização de Trajectos em Transportes Públicos.
1
por exemplo, pacotes diários de Internet Móvel incluem 10MB por 0,91 euros e 5
euros mensais por 100MB (aproximadamente 3MB diários) na operadora Vodafone
Portugal (http://www.vodafone.pt)
7
O easy-City consiste num Cliente e Optimizador assistidos por um Localizador. O Optimizador do easy-City toma decisões sobre trajectos com base
em fontes de informação dinâmica. Esta informação dinâmica é proveniente
de outros utilizadores ou de unidades xas colocadas em determinadas paragens/estações/terminais. A inclusão de infra-estrutura (as unidades xas) é importante para o sistema operar com baixa densidade de utilizadores num dado
ponto, para emissão de alertas de imprevistos que acontecem na rede de transportes e para ser possível implementar um Localizador simples (baseado na troca
de
beacons
Bluetooth entre utilizadores e infra-estrutura). Pretende-se que as
unidades xas sejam muito simples, em termos de hardware e software, de forma
a evitar um custo elevado.
A opção pela utilização da norma Bluetooth para comunicação vem do facto
de esta tecnologia estar disponível na maioria dos telemóveis utilizados nos dias
2
de hoje , não comportar encargos monetários para o utilizador, e pelo baixo
consumo de energia relativamente a outras formas de comunicação.
Em termos arquitecturais, o sistema consistirá numa Rede Tolerante a Atrasos (ou Delay-Tolerant Networks, ou DTNs) formada por telemóveis dos utilizadores e por adaptadores Bluetooth Classe 1 instalados nas paragens. Uma
DTN é uma rede em que os contactos entre os dispositivos participantes são intermitentes. Desta forma, estabelecer e manter caminhos de comunicação entre
nós é muitas vezes difícil, se não mesmo impossível. Esta denição adapta-se,
igualmente, aos padrões de mobilidade dos utentes de uma rede de transportes.
É sobre esta arquitectura que se pretende encaminhar e disseminar informação
pelos utentes.
2
Trabalho Relacionado
Esta secção introduz o trabalho relacionado com o problema descrito anteriormente. Nas seguintes secções são descritas as abordagens possíveis para a resolução do problema da Optimização de Trajectos em Transportes Públicos, ou
problemas relacionados, indicando-se as vantagens e desvantagens de cada uma.
Tal como na secção anterior, são descritos alguns exemplos de sistemas reais que
fazem uso de cada abordagem. Dado o número elevado de soluções usadas nas
redes de transportes públicos mundiais, os exemplos não se pretendem exaustivos, antes ilustrativos. Ainda é feita uma descrição de várias tecnologias sem os
interessantes para a resolução do problema e de diferentes abordagens existentes
para a formulação de um Localizador (ou sistema de localização).
2.1
Optimizador Clássico
Na solução mais primitiva para o problema da Optimização de Trajectos em
Transportes Públicos é o próprio utente que desempenha grande parte das funções (para simplicidade, neste documento, este modelo é chamado de Optimizador Clássico). Através de fontes de informação estática ou dinâmica, o utente é
2
Fontes: Vodafone Portugal(http://www.vodafone.pt), TMN(http://www.tmn.pt/)
8
capaz de optimizar, de acordo com os seus objectivos, a utilização dos transportes
públicos através da capacidade cognitiva. A Figura 3 demonstra a organização
de um Optimizador Clássico. O cérebro humano reúne as capacidade de Cliente
Figura 3.
Estrutura do Optimizador Clássico
(plataforma de acesso ao Optimizador) e Optimizador. As fontes de informação
estática são diversas, por exemplo, os placares que informam que carreiras passam numa paragem, os horários, trajectos, tempos previstos estáticos, mapas
de rede, etc. As fontes de informação dinâmica são provenientes de percepções
do utente, provenientes de sentidos, como a visão e a audição. Por exemplo,
por vezes existem contactos entre utentes através de informação boca-a-boca
quando acontecem imprevistos. Outras situações são facilmente identicáveis
visualmente, como, por exemplo, alguns engarrafamentos próximos do utente.
Contudo, o Optimizador Clássico está longe de ser a melhor solução para
a Optimização de Trajectos em Transportes Públicos. Em [19], os autores concluem que os humanos não são bons a descobrir melhores caminhos entre dois
pontos e, ainda, que o problema é agravado quando a distância entre os pontos
(logo, a complexidade do universo de caminhos possíveis) aumenta. Para piorar
a situação, é necessário o Optimizador ter em conta uma grande quantidade de
informação, o que por vezes afecta as decisões tomadas negativamente. Ainda
é necessário referir que, muitas vezes, as fontes de informação dinâmica que o
Optimizador possuí são poucas ou nenhumas, logo muitas decisões são tomadas
com conhecimento parcial e incompleto do que se passa na rede de transportes.
Concluindo, o Optimizador Clássico precisa de lidar com informação complexa, em número elevado, dinâmica, muitas vezes de difícil acesso e proveniente
de diversos operadores e não consegue superar estes desaos do problema.
2.2
Optimizador Clássico com informação dinâmica proveniente de
infra-estrutura
Uma extensão ao Optimizador Clássico consiste na inclusão de fontes de informação dinâmica mais completas, provenientes da infra-estrutura de operadores.
O principal objectivo dos sistemas que seguem esta abordagem é fornecer informação em tempo real para ajudar a tomada de decisões dos utentes. A Figura
9
4 apresenta o esquema de um Optimizador Clássico com informação dinâmica
proveniente de infra-estrutura. Nesta abordagem o Cliente e o Optimizador conti-
Estrutura do Optimizador Clássico com informação dinâmica proveniente
de infra-estrutura
Figura 4.
nuam relacionados com o cérebro humano, surgem os Sensores de infra-estrutura
que podem ser xos ou móveis, sendo responsáveis por inferir informação acerca
da rede e enviar os dados a um Servidor Central, ou conjunto de servidores, que
tipicamente é responsável pela organização, armazenamento, agregação e publicação dessa informação. O Localizador é um módulo que permite aos sensores
móveis computar a sua localização e pode ser implementado de acordo com os
diferentes requisitos e características do cenário em que é aplicado. As fontes
de informação estática são, tipicamente, as mesmas que as da abordagem anterior. As fontes de informação dinâmica podem assumir diversas formas, tais
como, placares electrónicos, quiosques interactivos, serviços de consulta através
de email, mensagens escritas (ou
Short Message Service
ou SMS), etc. Os Sen-
sores podem ter mecanismos de comunicação entre si, ou apenas comunicarem
com o Servidor Central, dependendo das soluções.
No entanto, a sua complexidade e custos monetários limitam esta abordagem para a resolução da Optimização de Trajectos em Transportes Públicos. Os
sensores de infra-estrutura e as fontes de informação consistem em equipamento
complexo, com altos requisitos de disponibilidade, abilidade e resistividade, o
que os torna caros e, muitas vezes, de difícil instalação [28].
10
A optimização continua a ser efectuada pelo utente. O que faz desta abordagem uma versão melhorada da anterior é o facto deste dispor de mais informação.
Porém a probabilidade de erros devido à complexidade da informação mantém-se
elevada, o que pode levar à tomada de decisões erradas.
Outra das principais limitações deste tipo de soluções é de normalmente
serem propriedade de uma operadora em particular, isto é problemático porque
normalmente diferentes operadoras não colaboram. Ou seja, o utente consegue
das fontes, informação dinâmica acerca dos seus serviços, e esta pode não ser
a informação que mais lhe interessa. Por exemplo, um utente encontra-se numa
paragem de autocarro de uma operadora no ponto A, e actualmente o trajecto
mais rápido para B pode ser feito usando o metropolitano, de outra operadora.
A primeira não vai informar o utente que na segunda existe uma melhor opção,
devido à ausência de cooperação.
Ainda consequência do custo associado às soluções baseadas em infra-estrutura,
muitas vezes, estas não cobrem toda a rede, o que as faz falhar o objectivo de
fornecerem de forma acessível a informação ao utilizador.
Exemplos
Existem muitos sistemas que seguem esta abordagem de fornecer
melhores fontes de informação dinâmica aos Optimizadores Clássicos. Seguidamente, são descritos alguns exemplos para fornecer uma perspectiva de aplicações
reais do esquema e as suas limitações para a resolução do problema.
O primeiro exemplo é o SAEIP da Carris. O SAEIP é um sistema de ajuda
que tem como objectivo conhecer a posição dos autocarros, que constituem a
frota da Carris, em tempo real, ou seja, capturar informação dinâmica acerca
dos mesmos. Foi implementado com os objectivos de permitir uma gestão da
frota mais eciente, oferecer mais segurança aos passageiros e tripulantes e informar o público. Esta informação ao público é apresentada aos seus utentes
através de painéis presentes em algumas paragens da rede (em 350 das 2000
paragens da infra-estrutura). Na Figura 5, pode-se observar um painel electrónico do sistema SAEIP. Neste sistema existem dois tipos de Sensores, xos e
móveis: paragens e autocarros, respectivamente. A localização é feita através de
um sistema baseado em GPS, instalado na frota. Os Sensores comunicam com
um Centro de Controlo que no esquema anterior representa o Servidor Central.
A RATP possui um sistema semelhante com localização geográca para geração
de informação dinâmica, que suporta os sistema baseados em Internet oferecidos
(que serão descritos na secção seguinte). Encontra-se a desenvolver um projecto
teste que consiste na instalação de 3000 painéis [25].
As limitações do SAEIP e sistemas idênticos reectem as referidas anteriormente: informação exclusiva da operadora Carris, custo elevado para o operador,
cobertura limitada e a optimização continua a ser realizada pelo utente.
O SIP é um sistema de informação baseado em serviço de mensagens escritas
(SMS) e foi criado de forma a complementar o SAEIP. O utente envia uma SMS
para um número de telefone, com o código da paragem e com o número do
autocarro, obtendo uma resposta com o tempo de espera restante. Existe outro
serviço idêntico na Carris, mas usando email. No esquema apresentado, o SIP
11
Figura 5.
Painel electrónico da Carris [31]
é uma fonte de informação dinâmica acessível através de serviços de email ou
SMS.
A RATP possui uma aplicação de leitura de códigos de barras 2D. Cada
paragem possui um código de barras único na rede. Através de uma captura do
mesmo, é enviado um pedido de consulta dos próximos tempos de chegada na
paragem. Para a utilização deste sistema é necessário um telemóvel compatível
com a leitura de códigos de barras.
As principais desvantagens destes sistemas são obrigar o utilizador a custos
acrescidos (custo da SMS ou da ligação para envio do email) para obter as
informações, e mais uma vez o facto de a optimização ser efectuada pelo utente.
A Refer instalou quiosques multimédia em algumas estações do país [23].
Estes servem de interface entre o utilizador e o eTrainInfo. O eTrainInfo é um
sistema de informação geográca, que permite a consulta da posição dos comboios em tempo real, e informação sobre estações e apeadeiros. É possível a
visualização, num mapa 2D, da localização dos comboios e saber quais os que se
encontram atrasados em relação aos horários (assinalados a três cores diferentes,
de acordo com a situação de atraso).
A principal desvantagem do sistema é não acompanhar o utilizador, ao longo
da sua viagem, e exigir interacção directa com um dispositivo xo (o quiosque),
falhando, desta forma, o objectivo de a informação estar facilmente acessível ao
utilizador.
2.3
Optimizador Web
A Internet é, hoje, um recurso bastante popular. O surgimento de Optimizadores
de Tráfego em Transportes Públicos baseados na Web aconteceu naturalmente e
demonstra a importância deste problema para os utentes dos transportes colectivos. Optimizadores Web são serviços Web públicos que fazem optimização de
trajectos.
12
É importante fazer a distinção de dois tipos de Optimizadores Web diferentes:
Optimizadores Web Estáticos e Optimizadores Web Dinâmicos. Tal como o nome
indica, os Optimizadores Web Estáticos têm em conta, para os seus cálculos,
apenas fontes de informação estáticas, como por exemplo, bases de dados com
trajectos, tarifários, horários, que mudam poucas vezes ao longo do tempo. Na
Figura 6 encontra-se o esquema de um Optimizador Web Estático.
Figura 6.
Optimizador Web Estático
Os Optimizadores Web Dinâmicos têm em conta informação estática e informação dinâmica quando realizam a optimização. Na Figura 7 encontra-se o
esquema de um Optimizador Web Dinâmico. Num Optimizador Web o acesso
ao módulo Optimizador é efectuado através de um cliente que, tipicamente é
uma aplicação. Como já foi referido, o Optimizador consiste num serviço Web
público responsável por efectuar o cálculo do melhor trajecto tendo em conta
as fontes de informação e os requisitos do utilizador da aplicação. A Aplicação
pode ser um navegador Web ou uma aplicação especíca para interagir com o
Optimizador.
A existência de um Localizador a fornecer informação à aplicação é opcional
nestes sistemas. Porém, quando existe pode auxiliar o utilizador, pois este não
necessita de indicar a sua origem (é calculada pelo Localizador). A principal vantagem deste modelo consiste na computação de trajectos deixar de ser efectuada
pelo utente dos transportes, diminuindo desta forma a probabilidade de escolhas
incorrectas, resultantes do erro humano. Existem várias soluções, usando esta
abordagem, que reúnem informações de vários operadores.
Porém, estes sistemas possuem algumas limitações. Os Optimizadores Web
Estáticos, como já foi referido, usam apenas informação estática. Isto faz com
que as suas previsões sejam pouco áveis, pois não se adaptam a imprevistos e
alterações em tempo real.
13
Figura 7.
Optimizador Web Dinâmico
Os Optimizadores Web Dinâmicos são, tipicamente, soluções híbridas: infraestrutura+Web (tendo organizações com bastantes semelhanças, como se pode
observar comparando as Figuras 4 e 7). Os Sensores presentes na Figura 7, em
muitos sistemas, são integrantes da infra-estrutura dos operadores, sendo eles os
responsáveis pela geração das informações dinâmicas usadas pelos Optimizadores
Web. Isto faz com que herdem algumas das desvantagens das soluções baseadas
em infra-estrutura, como por exemplo, o custo de instalação e manutenção para
os operadores.
Outra limitação, esta comum aos optimizadores estáticos e dinâmicos, consiste na necessidade de comunicação através de uma ligação à Internet entre a
Aplicação e o Serviço Web. Ora, estes sistemas são de maior utilidade quando
o utilizador se encontra na sua origem e necessita de saber o melhor trajecto
até ao seu destino. O acesso móvel é, portanto, uma das formas mais importantes de acesso a estes sistemas, tipicamente, através de telemóveis. Para que tal
seja possível, é necessário que os utentes utilizem Internet Móvel ou pontos de
acesso públicos para conseguirem estabelecer uma ligação à Internet. Isto, normalmente acaba por resultar em custos monetários elevados para o utilizador
e/ou no consumo de bateria do telemóvel elevado.
14
Outro factor limitativo destas soluções vem do facto de alguns serviços Web
por vezes não se encontrarem optimizados para acesso móvel, o que torna o
sistema de difícil utilização em alguns telemóveis, principalmente em dispositivos
mais antigos.
Exemplos
Seguidamente apresentam-se alguns exemplos de soluções baseadas
em Optimizadores Web.
O primeiro exemplo é o Transporlis, um sistema desenvolvido através da cooperação entre diversos operadores de transportes públicos da Área Metropolitana
de Lisboa. Este sistema permite, através da sua página Web, o planeamento e
pesquisa de trajectos de acordo com os requisitos do utilizador. Indicando o
ponto de origem e destino da sua viagem, o sistema fornece ao utilizador uma
sugestão do melhor trajecto possível de acordo com o conhecimento que detêm
da rede de transportes (e.g., horários, tarifas, paragens). É possível, ao utilizador, indicar se prefere a opção menos pedonal, opção mais rápida, ou opção com
menos transbordo. Também existe a opção de escolha de operadora. O trajecto
seleccionado pelo sistema é apresentado num mapa e em modo textual detalhado por passos (este último modo ainda indica o preço, duração e a distância
do percurso). A principal vantagem do sistema é englobar informações de vários
operadores, o que permite ao utilizador escolher as opções que mais se adequam
às suas necessidades. As principais limitações são: é Optimizador Web Estático,
não possui uma versão optimizada ao acesso móvel.
Outro exemplo são as aplicações do RATP. Esta operadora francesa possui
um serviço bastante completo para os seus utentes fazerem a consulta do mapa
da sua rede, horários em tempo real, planeamento de trajectos e informação sobre
percursos em tempo real. Este serviço está disponível para qualquer telemóvel
com ligação à Internet, através das aplicações ou através da versão Wap da sua
página Web. A principal vantagem destes sistemas é a quantidade de informação
dinâmica fornecida. A principal desvantagem é o custo monetário, já referido
anteriormente, que uma solução híbrida, Web+Infra-estrutura, comporta para o
utilizador e para a operadora.
2.4
Optimizadores Ad-Hoc
Nesta secção são descritos Optimizadores Ad-Hoc. Antes de uma descrição de
sistemas baseados nesta abordagem, é necessário perceber o conceito de rede AdHoc móvel, os seus desaos, como o problema dos Optimizadores de Trajectos
em Transportes Públicos encaixa neste género de topologia.
Redes Ad-Hoc Móveis
Os Optimizadores Ad-Hoc têm o objectivo de dis-
seminar informação dinâmica capturada até ao utente, sem utilização de infraestrutura. Para tal, são construídas redes Ad-Hoc móveis, tipicamente formadas
por dispositivos transportados pelos utentes (por exemplo, telemóveis), recorrendo a tecnologias de comunicação sem os. Redes Ad-Hoc Móveis são redes
15
sem os caracterizadas pelas seguintes características e desaos no contexto do
problema dos Optimizadores de Trajectos em Transportes Públicos:
topologia muito dinâmica, consequência da alta mobilidade dos nós;
energia limitada, devido às características dos dispositivos usados para nós;
largura de banda reduzida;
alcance limitado, pois qualquer que seja a tecnologia de comunicação sem
os escolhida para implementar uma rede Ad-Hoc, terá um alcance limitado
o que condiciona as ligações entre nós;
a ausência de infra-estrutura pode levar à impossibilidade de se inferir algumas informações dinâmicas numa rede de transportes e pode ser problemática em caso de uma densidade de nós reduzida.
Problema aplicado às redes Ad-Hoc
O problema dos Optimizadores Ad-
Hoc pode ser denido da seguinte forma.
Os nós, tipicamente os telemóveis dos utentes dos transportes públicos, têm
capacidade de análise do meio físico para geração de informação importante
para outros utentes. Essa
informação tem de ser disseminada
de forma
a chegar a quem interessa. Devido às características particulares de uma rede
Ad-Hoc móvel, algoritmos clássicos de disseminação não são, muitas vezes, as
melhores opções. É importante, também, permitir uma forma de comunicação
directa entre os nós, baseada num
modelo pedido/resposta,
de forma a per-
mitir operações de consulta de informação. Devido às aglomerações de utentes
nos transportes públicos, alguns eventos que acontecem serão observados por vários utilizadores, o que consequentemente leva à geração de informação idêntica.
Interessa, portanto, detectar essa informação e agregá-la de forma a reduzir a
quantidade de informação duplicada disseminada.
Os contactos entre utilizadores das redes de transportes são esporádicos e
muitas vezes breves (por exemplo, cruzamentos em terminais, estações). E dada
a sua dimensão, se forem escolhidos dois utilizadores ao acaso, a probabilidade de
cruzamento entre eles a curto prazo é bastante reduzida. Por estas razões, existe
um tipo em particular de redes ad-hoc móveis que encaixa bem no problema que
se pretende solucionar: as
redes tolerantes a atrasos.
Este género de redes é caracterizado por contactos entre nós particularmente curtos e pela inexistência, na maioria dos casos, de caminhos entre pares
origem-destino, necessários para o modelo de comunicação pedido/resposta (ou
request/reply ).
Este é, portanto, um tipo de rede altamente desconectado e es-
parso. Tal topologia de rede, torna necessária a criação de
minhamento e disseminação
algoritmos de enca-
de mensagens diferentes das redes tradicionais,
de forma a complementar a pouca delidade dos caminhos estabelecidos (caso
existam). O desenvolvimento de mecanismos de armazenamentotransporte
encaminhamento (StoreCarryForward ) é necessário para conseguir taxas de
entrega de mensagens aceitáveis. Estes são mecanismos que permitem que uma
informação gerada, num local A, seja armazenada por alguns nós, transportada,
até um local B, e encaminhada quando necessário.
16
Modelo de comunicação Pedido/Resposta: algoritmos de encaminhamento Este é um modelo de comunicação para acesso a informação dinâmica
que corresponde a fazer pedidos de informação pela rede. Normalmente, nas redes
tolerantes a atrasos são mantidas algumas informações de rotas entre nós. Porém,
como já foi referido, estas informações são limitadas devido à topologia destas
redes. É necessária a utilização de algoritmos de encaminhamento adaptados.
Algumas das muitas soluções para este problema são: AODV [24], DSR [15],
GOSSIP [12], RAPID Protocol [5], PROPHET [17],
Spray and Wait
[30]. No
entanto, em alguns casos de redes tolerantes a atrasos são necessários mecanismos mais simples devido ao grau de desconexão dos nós, como por exemplo a
inundação, ou fazer pedidos apenas aos vizinhos directos. Isto porque, as rotas
estabelecidas não duram o suciente para ser proveitoso o seu armazenamento e
manutenção.
StoreCarryForward :
disseminação, armazenamento e transporte
desenvolvimento de um mecanismo de
StoreCarryForward
O
é fundamental para
a resolução do problema da Optimização de Trajectos em Transportes Públicos.
Este mecanismo separa-se em dois principais sub-problemas:
desenvolvimento de algoritmos de disseminação de mensagens, incluindo a
escolha dos nós que fazem o transporte;
criação de mecanismos de gestão de armazenamento de mensagens.
Relativamente aos
algoritmos de disseminação de mensagens, a solução
mais simples consiste na inundação (ou
Flooding )
para a troca de mensagens.
Porém, muita da investigação nesta área passa pela criação de algoritmos que se
adaptem à mobilidade dos nós e que tirem partido de padrões, para aumentar
taxas de entrega de mensagens e diminuir a carga na rede [2,6,17,32,34]. Em [2] é
denida uma métrica de popularidade de nós que inuencia o algoritmo de encaminhamento de mensagens. Em [34] são denidas duas métricas particularmente
interessantes:
Destination Matching
e
Arrival Time of Destination.
A primeira
está relacionada com a noção de destino de um nó e destino de uma mensagem.
Por exemplo, se um nó X gera uma mensagem que quer publicar na localização
A, X irá delegar o transporte da mensagem a nós que encontre com destino em
A. A segunda métrica, está relacionada com o tempo de chegada previsto de um
nó a uma dada localização. Por exemplo, se X encontrar muitos nós com destino
em A, irá delegar o transporte da mensagem aos nós que tiverem um menor
tempo de chegada previsto.
Quanto aos
mecanismos de armazenamento de mensagens,
tante a criação de
buers
é impor-
de transporte. Como tipicamente os nós das redes
tolerantes a atrasos têm restrições de armazenamento, quando o
buer
atinge a
sua capacidade máxima, é necessária substituição de mensagens. Alguns exemplos de políticas de substituição [9, 16] são:
Least Recently Used
temente;
(LRU) - substituída a mensagem menos utilizada recen-
17
Most Recently Used
(MRU) - substituída a mensagem mais utilizada recen-
temente;
First In First Out
(FIFO) - substituída a mensagem que se encontra à mais
tempo armazenada;
MOFO - substituída a mensagem mais enviada;
SHLI - substituída a mensagem com menor tempo de vida restante (ou
To-Live,
Time-
ou TTL);
LEPR - substituída a mensagem que o nó tem menor probabilidade de entregar.
Mais do que uma política pode ser utilizada conjuntamente.
Agregação de dados
dade dos
buers
Para poupar tráfego na rede e diminuir a probabili-
atingirem a capacidade máxima, tipicamente, são aplicados
mecanismos de agregação de dados para diminuir a quantidade de informação
duplicada disseminada. Estes mecanismos consistem, muitas vezes, em sumariar
informação através de algoritmos. Ahmed et al. [2] aplicam um mecanismo de
agregação de mensagens para resolver estes problemas baseado Network Coding,
o HubCode. Lochert et al. [20] especicaram um algoritmo probabilístico para
agregação de dados.
Como já foi referido, no contexto do problema da Optimização de Trajectos
em Transportes Públicos é gerada muita informação idêntica, devido à elevada
concentração de pessoas (que consequentemente poderão observar os mesmos
eventos), que interessa limitar. Como a informação é muito semelhante, apenas
diferindo em pequenos detalhes irrelevantes (como por exemplo, duração aproximada e tempo de criação da informação com diferenças na ordem de segundos)
os mecanismos de agregação podem ser simplicados, podendo-se optar, por
exemplo, por descartar as cópias semelhantes e car com a mais recente.
Redes Ad-Hoc Móveis e Optimizadores Ad-Hoc
Interessa, então, descre-
ver como um Optimizador Ad-Hoc pode ser implementado através de uma rede
Ad-Hoc móvel. Na Figura 8 encontra-se um esquema possível de uma solução
para o problema. O utilizador de um sistema deste género tem, tipicamente,
uma aplicação instalada num dispositivo móvel, por exemplo num telemóvel.
Cada dispositivo equipado é um nó da rede. Neste esquema cada nó é produtor e consumidor de informação. A aplicação é constituída por dois módulos,
uma Interface e o Optimizador. O acesso a informação dinâmica é feito através
de contactos com outros nós da rede Ad-Hoc móvel, através de tecnologias de
comunicação sem os, como por exemplo, Wi-Fi [3], Bluetooth [29] ou comunicação rádio. A informação estática pode estar incorporada na aplicação. Os
agregadores de dados são nós a quem é delegada a responsabilidade, permanente
ou esporádica, de agregar mensagens. O Localizador, mais uma vez, é um sistema
que permite aos nós inferir informações acerca do meio em que se encontram e
auxiliar a interacção do utilizador com o sistema.
18
Figura 8.
Optimizador de Trajectos Ad-Hoc numa rede Ad-Hoc móvel
No entanto, estas soluções possuem algumas limitações. Como já foi referido,
estas redes dependem da densidade de nós activos a gerar e transportar informação para funcionarem correctamente e serem úteis aos utilizadores. Também,
devido à ausência de uma infra-estrutura, algumas informações sobre a rede são
difíceis de inferir, tais como, alertas de perturbações, acidentes, etc..
Redes Ad-Hoc Veiculares e Optimizadores Ad-Hoc
Um subtipo de redes
Ad-Hoc móveis, as redes Ad-Hoc veiculares, são muito aplicadas a Optimizadores
de Trajectos, mas com desaos diferentes dos levantados no problema da Optimização de Trajectos em Transportes Públicos. Nas Redes Ad-Hoc Veiculares
os nós são veículos, o que agrava algumas restrições e elimina outras. Em [22]
faz-se uma distinção atendendo a várias características das quais se destacam as
seguintes:
questões energéticas não são tão problemáticas, devido à muito maior capacidade energética de um veículo;
grandes velocidades fazem com que contactos entre nós sejam mais breves;
veículos circulam em estradas, que são infra-estruturas pouco variáveis (ou
seja, os padrões de mobilidade são mais previsíveis);
soluções podem ser computacionalmente mais exigentes, pois os dispositivos
que constituem a rede, tipicamente, têm mais poder computacional.
19
Algumas soluções baseadas em redes Ad-Hoc veiculares, são particularmente
interessantes para a resolução do problema da Optimização de Trajectos em
Transportes Públicos, porque complementam a comunicação Ad-Hoc com unidades xas (Road-Side
Units ).
Na Figura 9 encontra-se o esquema de um Opti-
mizador Ad-Hoc, no contexto de uma rede Ad-Hoc veicular apoiada por infraestrutura.
Optimizador de Trajectos Ad-Hoc numa rede Ad-Hoc veicular apoiada por
infra-estrutura
Figura 9.
O utilizador interage com o Optimizador através de uma aplicação. O Optimizador é uma unidade de processamento instalada no veículo, com capacidade
de comunicação sem os, para fazer acesso à informação dinâmica. Neste tipo
de soluções, os veículos que circulam na estrada são os sensores. Estes possuem
ainda um Localizador para poderem participar na rede Ad-Hoc quer como consumidores, quer como produtores de informação. Existem soluções em que alguns
veículos actuam como agregadores de dados, tal como acontece nas redes Ad-Hoc
móveis.
20
Por exemplo, Lochert et al. [21] introduzem unidades xas para melhorar a
disseminação de informação na sua solução, principalmente numa baixa densidade de veículos.
2.5
Tecnologias de Comunicação Sem Fios
Nesta secção é feita a descrição das tecnologias de comunicação sem os mais
interessantes para a resolução do problema, Wi-Fi e Bluetooth, destacando-se as
vantagens e limitações de cada uma.
Tecnologia Wi-Fi
3
Wi-Fi é uma tecnologia, criada pela Wi-Fi Alliance , para
comunicação sem os a curtas distâncias. Esta, usa, principalmente, a frequência
rádio 2.4GHz e permite a formação de Redes Locais Sem Fios (ou Wireless Local
Area Networs, ou WLANs). Existem várias normas Wi-Fi, a mais popular é a
norma 802.11b/g, presente na maioria dos telemóveis equipados com tecnologia
4
Wi-Fi .
Esta norma tem um alcance teórico de 100 metros e uma potência de 100mW.
Esta é portanto, uma tecnologia que oferece um alcance satisfatório, porém os
seus índices de consumo de energia são elevados. Logo, uma utilização continua
em aplicações, como por exemplo, um Optimizador de Trajectos de Transportes
Públicos num telemóvel, é bastante penalizador para a duração da bateria do
dispositivo.
Tecnologia Bluetooth
Bluetooth é uma tecnologia que permite comunicação
sem os a curtas distâncias entre dispositivos com interface compatível com
a norma. Criada pelo Bluetooth Special Interest Group
5 (ou Bluetooth SIG),
permite a formação de Redes Pessoais (ou Personal Area Networks ou PANs).
A tecnologia Bluetooth usa a frequência rádio 2.4GHz, tal como a tecnologia
Wi-Fi.
A norma Bluetooth possui três classes diferentes. As diferenças entre as mesmas estão descritas na Tabela 1.
Tabela 1.
Classes Bluetooth
Classe Alcance(metros) Potência(miliWatts)
1
2
3
3
4
5
100m
10m
<10m
100mW
2.5mW
1mW
Organização fundada em 1999
Fontes: Vodafone Portugal(http://www.vodafone.pt), TMN(http://www.tmn.pt/)
Organização privada fundada em 1998
21
Os telemóveis actualmente comercializados usam, tipicamente, interfaces Bluetooth de Classe 2 e têm uma presença em quase todos os modelos comercializa-
6
dos actualmente . O facto possuírem interfaces de Classe 2 faz com que consigam
alcances teóricos máximos de 10 metros, com uma potência de 2.5mW.
Um dispositivo Bluetooth pode assumir dois papeis diferentes: mestre ou escravo. Quando desempenha o papel de mestre pode conectar-se com mais sete
dispositivos escravo. Este conjunto forma uma Piconet. Uma Piconet dene-se
como dois ou mais dispositivos que partilham o mesmo canal físico. Um dispositivo Bluetooth pode participar em mais do que uma Piconet. Este facto permite
a formação de Scatternets. Uma Scatternet consiste em duas ou mais Piconets
ligadas através de um dispositivo ponte (que participa em mais do que uma
Piconet).
Concluindo, o Bluetooth revela-se uma boa opção para tecnologia de comunicação sem os utilizada num Optimizador de Trajectos de Transportes Públicos
para telemóveis, devido ao baixo consumo de bateria.
2.6
Sistemas de Localização
A localização física de objectos ou pessoas é importante para muitos sistemas e
inclusive para um Optimizador de Trajectos de Transportes Públicos. Ao longo
dos anos, a investigação sobre técnicas e tecnologias para localização tem sido
grande. Existem vários modelos de acordo com os requisitos dos sistemas. Esses
requisitos estão relacionados com determinadas propriedades dos sistemas de
localização [14].
Propriedades
Posição física e Posição Simbólica
- A posição física é relativa a me-
didas de posição mensuráveis. O GPS é um sistema que fornece a Posição
Física de algo. Essas informações no caso do GPS são latitude, longitude e
altitude. Chão Inteligente(Smart Floor) fornece a posição física de algo num
dado espaço equipado com esta tecnologia. Sensores de pressão conseguem
detectar a posição de pessoas numa sala, por exemplo. A posição simbólica
representa ideias abstractas da posição de algo. Perto da estação uvial,
no escritório, no campus, são exemplos de posições simbólicas que um
sistema pode fornecer acerca de algo. Estas posições não são mensuráveis.
Active Badges, leitores de códigos de barras, leitores de etiquetas RFID são
alguns exemplos de tecnologias que fornecem a Posição Simbólica ao sistema.
Localização absoluta e Localização Relativa
- Localização absoluta
consiste na partilha de um referencial por todas as localizações efectuadas
pelo sistema. Por exemplo, o sistema Smart Floor identica vários objectos ou pessoas numa sala segundo o mesmo eixo de coordenadas. O mesmo
6
Fontes: Vodafone Portugal(http://www.vodafone.pt), TMN(http://www.tmn.pt/)
22
acontece com o GPS. Localização relativa acontece quando cada agente localizador possui o seu próprio referencial. Desta forma, um objecto localizado
pode ter diferentes localizações dependendo do agente que o localiza.
Exactidão e Precisão
- A exactidão delimita uma relação entre valores
medidos e valores reais. Precisão é o número de vezes que se prevê atingir
a exactidão. Por exemplo, quando se diz que um sistema nos fornece uma
posição com um erro de 1 a 6 metros 97% das vezes, estamos na realidade
a armar que conseguimos obter uma exactidão de 1-6 metros com uma
precisão de 97%. Existem sistemas com requisitos de exactidão muito diversos. Uns exigem um grau muito elevado de exactidão, outros relaxam na
exactidão para fornecer uma precisão mais elevada. Todas estas decisões estão relacionadas com o problema a ser resolvido por um dado sistema. Por
exemplo, um sistema de localização de vítimas de catástrofes naturais tem
requisitos de exactidão mais elevados do que um sistema de localização de
gestão de frotas, como o SAEIP. Um erro de 10 metros no primeiro sistema
pode ser fatal, enquanto que, no caso do segundo sistema, a maioria das
vezes, pode ser irrelevante.
Computação da localização(ou
Localized Location Computation ) -
Esta propriedade está relacionada com quem computa a posição do objecto.
Em alguns sistemas é o próprio objecto que computa a sua posição. Este modelo tem vantagens, como uma maior privacidade. O objecto só é localizado
neste modelo se publicar informação relativamente à sua posição. Outros
sistemas de localização recorrem à infra-estrutura para o cálculo da posição
dos objectos. Neste modelo, a infra-estrutura tem conhecimento acerca do
objecto, o que reduz a privacidade do sistema.
Custo
- É possível inferir o custo de um sistema de localização recorrendo a
várias informações. Custos monetários estão associados ao preço do sistema,
quer da infra-estrutura, quer da unidade móvel de localização. Por exemplo, o
custo monetário do Sistema de Posicionamento Global equivale ao custo dos
Satélites(infra-estrutura) e ao custo de um aparelho GPS (unidade móvel de
localização). Custos temporais estão relacionados com o tempo de instalação,
administração e manutenção do sistema. Este custos, estão intrinsecamente
ligados à infra-estrutura. Custos espaciais são os custos relacionados com
o tamanho da infra-estrutura e hardware. No caso das unidades móveis de
localização este custo pode relacionar-se com a portabilidade.
Escala
- A escala de um sistema mede-se através da área cobertura por uni-
dade de infra-estrutura e número de objectos que o sistema pode localizar
por unidade de infra-estrutura num intervalo de tempo. Por exemplo, no
sistema Active Badge é necessário um sensor por sala e esse sensor tem a
capacidade de localizar um objecto que possua uma unidade móvel de localização(Badge) a cada período de 10 segundos.
23
Reconhecimento
- Alguns sistemas necessitam, não apenas de localizar
um objecto, mas também de identicar que objecto foi localizado. O SAEIP
da Carris é um exemplo de um sistema que possui reconhecimento pois, é
possível a identicação dos autocarros localizados.
Técnicas de Localização
Os sistemas de localização usam técnicas para loca-
lizar os objectos. As principais técnicas de localização [13] são:
Proximidade;
Triangulação;
Análise de Cena.
Proximidade
mede a cercania de algo a um conjunto de pontos conhecidos.
Smart Floor e Active Badges são exemplo de tecnologias que usam proximidade.
Triangulação
usa as propriedades geométricas de triângulos para calcular a
posição de objectos. Existem dois subtipos de triangulação: lateração e angulação. Lateração usa distâncias entre pontos conhecidos. Angulação é um processo
idêntico à lateração mas, como o nome indica, usa as propriedades angulares do
triângulo para computar a posição em vez de distâncias. GPS é um exemplo de
tecnologia que usa triangulação.
Análise de Cena
usa informações observadas a partir de um ponto de vi-
são para inferir conclusões acerca da posição de objectos. MSR RADAR [4] é
um exemplo de um sistema que usa análise de cena.
Sumário
Existem várias alternativas para a implementação de um sistema de
localização. As opções por diferentes características são inuenciadas por requisitos a nível aplicacional e não é possível,
a priori, denir o sistema de localização
ideal. Por exemplo, alguns sistemas podem funcionar com uma localização pouco
precisa e exacta, outros sistemas têm restrições muito elevadas relativamente a
essas propriedades. Para cada sistema, é necessário encontrar um ponto de equilíbrio entre o custo e as características desejáveis.
No caso do problema de Optimização de Trajectos em Transportes Públicos,
os requisitos de exactidão e precisão não são muito rígidos. Um sistema com as
características:
posição simbólica;
localização absoluta;
computação da localização realizada pelo telemóvel;
pode formalizar um Localizador apropriado à resolução do problema. A técnica
de localização escolhida pode ser, por exemplo, proximidade a referenciais xos,
utilizando a tecnologia Bluetooth.
24
3
Arquitectura
O easy-City é um sistema de pesquisa de trajectos em transportes públicos por
Bluetooth. Através do seu telemóvel, os utilizadores do sistema indicam o seu
ponto de origem e destino. Podem, então, aguardar por sugestões de melhores trajectos para o par (origem-destino) indicado. Estas sugestões são criadas
pela aplicação cliente que corre nos telemóveis de outros utilizadores. Quando
a aplicação cliente de um utilizador detecta que este conseguiu fazer um trajecto entre dois pontos, num tempo menor que o habitual, gera uma sugestão
de trajecto. O sistema visa ser escalável. Todo o seu desenho tem em conta cenários de densidade elevada ou reduzida de utilizadores. Através da introdução
de infra-estrutura espera-se reduzir o impacto da variação dessa densidade no
desempenho do sistema. A infra-estrutura introduzida serve, ainda, para permitir a computação da localização dos nós e emitir avisos de imprevistos da rede
de transportes. A adopção da tecnologia Bluetooth para comunicação acontece
devido à presença desta norma nos telemóveis, hoje em dia.
3.1
Cenários a resolver
O sistema descrito neste documento tem como objectivo a resolução dos seguintes
cenários de utilização:
Cenário 1 O Pedro está no Marquês de Pombal e tem como destino o
Saldanha. Todos os dias apanha a carreira 53 para fazer este percurso entre
as 9:30 e as 10h, tendo registado um tempo médio (últimos 3 dias) de 20
minutos para efectuar o percurso. Cruza-se com outro utilizador do easyCity que faz todos os dias este percurso mas utilizando outro transporte,
com uma média de 10 minutos. O Pedro recebe uma noticação de novo
percurso mais rápido e aceita a sugestão.;
Cenário 2 O Carlos encontra-se em Alvalade. Para chegar ao seu destino possuí 3 hipóteses. Normalmente opta pelo metro, transporte pelo qual
regista melhor média temporal. Porém cruza-se com um utilizador do easyCity que se cruzou com alguém (à 10 minutos) que fez o mesmo percurso
num tempo menor que o registo do Carlos. O Carlos recebe a sugestão e
opta pela nova rota mais rápida.;
Cenário 3 O João está a chegar ao terminal do Caís do Sodré vindo
do transporte uvial que apanha todos os dias. Embora tenha o hábito de
utilizar o metro para chegar ao seu local de trabalho, hoje ao chegar a este
terminal recebe no seu telemóvel um alerta, de outro utilizador do easy-City,
informando-o que a circulação na linha verde se encontra interrompida. O
João decide então ir apanhar o autocarro..
Estes cenários são problemáticos para todas as abordagens existentes.
O Cenário 1 consiste num pedido directo de um utilizador e numa resposta
de outro que possui a informação pretendida. O Cenário 2 consiste na viagem
de uma sugestão observada num destino e transportada para uma origem através
25
do algoritmo de disseminação de mensagens. O Cenário 3 consiste na interoperabilidade oferecida pelo easy-City: um utilizador recebeu um aviso quando se
encontrava no metropolitano e transportou a informação para o terminal uvial.
3.2
O easy-City
A arquitectura e algoritmos descritos nesta secção, serão testados em ambiente
de simulação juntamente com outras soluções estudadas. Desta forma, pretendese inferir possíveis melhorias para construir um sistema melhor, que resolva o
problema da Optimização de Trajectos em Transportes Públicos.
O easy-City é um sistema que aproveita as vantagens das soluções baseadas
em infra-estrutura e das soluções baseadas em redes ad-hoc móveis. Desta forma,
é possível criar um sistema que funcione em ambientes mais esparsos, em termos
de utilizadores, e com um custo reduzido relativamente às soluções de infraestrutura descritas na Secção 2.
As paragens/estações/terminais estão equipadas com unidades xas. Estas
unidades são computadores com interface Bluetooth de Classe 1 (para alcance
máximo de 100 metros). A funcionalidade destas unidades, como já foi referido,
é enviar
beacons
aos dispositivos para estes últimos conseguirem computar a sua
localização. Também possuem a funcionalidade de emitir avisos sobre imprevistos na rede de transportes.
O easy-City é constituído, igualmente, pela aplicação cliente que é executada
no telemóvel do utilizador. Esta aplicação possui três módulos:
Localizador;
Módulo de Comunicação
Gestor de Informação;
O Localizador realiza a computação da posição do dispositivo. Desta forma,
evitam-se problemas de privacidade. Este módulo é activo quando é recebido
um
beacon
da infra-estrutura. Cada paragem possui um identicador único na
rede que se encontra no
beacon.
O Módulo de Comunicação é responsável pela
comunicação entre utilizadores e entre o utilizador e a infra-estrutura. O Gestor
de Informação é responsável pela execução dos algoritmos de disseminação e
encaminhamento de mensagens, pela gestão da memória e pela agregação de
dados. É assumido que todos os nós que correm a aplicação cliente possuem
uma interface Bluetooth de Classe 2.
Rede ad-hoc tolerante a atrasos
O easy-City constitui uma rede ad-hoc
tolerante a atrasos, formada por escassos nós xos e muitos nós móveis. São
necessários mecanismos de armazenamentotransporteencaminhamento, devido
escassez de caminhos estabelecidos entre nós. Os nós que realizam estas operações
são chamados de
transportadores.
26
Algoritmo de disseminação de mensagens
O algoritmo de disseminação
de mensagens tem em conta duas métricas diferentes:
Destino - Destino de um nó (métrica baseada no
Destination Matching
[34]);
Popularidade - uma medida de popularidade relacionada com o número de
partilhas realizadas pelo nó (métrica baseada na Popularidade introduzida
por Ahmed et al. [2]);
O algoritmo possui duas formas de funcionamento, de acordo com a categoria
da mensagem a ser disseminada.
Se a informação a disseminar for uma
sugestão,
o algoritmo funciona da se-
guinte forma:
s = geraSugestao()
for all y ∈ V IZIN HOS do
if sdestino ∈ yCAM IN HO then
envia(s, y)
end if
end for
Se a informação a disseminar for um
imprevisto,
o algoritmo funciona da se-
guinte forma:
i = imprevisto
for all y ∈ V IZIN HOS do
if ypopularidade ≥ N then
envia(i, y)
end if
end for
A utilização de uma métrica por algoritmo é justicável pela brevidade dos contactos aquando de cruzamentos. São necessários algoritmos computacionalmente
leves e breves.
Algoritmo de encaminhamento de mensagens
Quando é actualizada a lo-
calização de um nó transportador, o algoritmo de encaminhamento de mensagens
é executado. O algoritmo funciona da seguinte forma:
for all s ∈ SU GEST OES do
if sdestino = posicao then
dif unde(s)
drop(s, SU GEST OES)
end if
end for
Agregação de dados
Devido à natureza dos transportes públicos (e.g., agrupa-
mentos de pessoas em autocarros, comboios, metros) muitas sugestões poderão
ser geradas por mais do que um dispositivo com ligeiras diferenças (diferença
de segundos na duração do trajecto, por exemplo). De forma a poupar a rede a
27
mensagens duplicadas, estas deverão ser agregadas. O mecanismo de agregação
adoptado pelo easy-City é desempenhado pelos transportadores. Aquando da
recepção de mensagens para transporte, estes vericam se já possuem alguma
mensagem semelhante para transportar (mesmo caminho, tempos de criação próximos, duração aproximada). Se sim, o transportador opta pela informação mais
recente e substitui a mensagem mais antiga. Se não, adiciona simplesmente a
mensagem para transporte. Desta forma, reduz-se a taxa de ocupação das estruturas de dados, pois eliminam-se mensagens duplicadas. É, também, reduzida a
carga na rede, na fase de encaminhamento de mensagens.
Gestão de memória
A necessidade de transporte de mensagens para a sua
disseminação obriga a uma gestão das estruturas de dados onde estas cam
armazenadas. Principalmente, é necessário especicar o que acontece quando esse
espaço se esgota. É preciso adoptar uma política de substituição de mensagens.
A política que se propõe consiste em descartar a mensagem da qual o nó tem
conhecimento da existência de um maior número de cópias. Tal valor é conhecido
através presença de um campo na mensagem, número de réplicas, que consiste
na contagem feita pelo nó gerador do número de cópias por ele distribuídas.
4
Metodologia de Avaliação do Trabalho
Nesta secção descrevem-se as métricas e a metodologia usada para avaliar o
easy-City.
4.1
Métricas
Pretende-se avaliar o easy-City medindo as seguintes métricas:
latência de entrega das mensagens;
taxa de entrega de mensagens;
custo para a rede;
taxa de substituições de mensagens;
usando várias opções de algoritmos de disseminação e encaminhamento, bem
como de políticas de gestão de
buers, com principal incidência nas denidas na
Secção 3.
4.2
Avaliação
Devido à natureza do sistema, a avaliação do easy-City decorrerá num ambiente de simulação com várias densidades de nós. Pretende-se utilizar modelos de
mobilidade, para simular a movimentação dos nós do easy-City. A maximização
do realismo desses modelos é um objectivo a atingir, para se conseguir efectuar
medições mais aproximadas das que seriam obtidas num cenário real.
28
5
Conclusão
Neste relatório propôs-se uma solução para o problema da Optimização de Trajectos em Transportes Públicos. Para tal, apresenta-se o easy-City, um sistema
de pesquisa de trajectos em transportes colectivos. Através da análise de soluções existentes para o problema e problemas relacionados, propôs-se uma solução
genérica e uma arquitectura que tenta aproveitar vantagens de diferentes abordagens, para fornecer qualidade de serviço ao sistema, eliminando ou diminuindo
limitações. Desta forma, pretende-se atingir os objectivos propostos:
fornecer ao utilizador os trajectos que vão mais de encontro com os seus
requisitos;
ter essa informação facilmente acessível ao utilizador e presente quando necessária.
O próximo passo consiste em desenhar uma solução, para implementar a arquitectura denida e vericar adequabilidade da mesma à resolução do problema.
Seguir-se-à a fase de avaliação do easy-City, de forma a se obter resultados para
comparar com outros sistemas e algoritmos desenvolvidos, com o objectivo de se
melhorar a solução.
Referências
1. Ahmed, S., Kanere, S.S.: Skvr: scalable knowledge-based routing architecture for
public transport networks. In: Proceedings of the 3rd international workshop on
Vehicular ad hoc networks. pp. 9293. VANET '06, ACM, New York, NY, USA
(2006), http://doi.acm.org/10.1145/1161064.1161082
2. Ahmed, S., Kanhere, S.S.: Hubcode: message forwarding using hub-based network
coding in delay tolerant networks. In: Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems. pp. 288296. MSWiM '09, ACM, New York, NY, USA (2009),
http://doi.acm.org/10.1145/1641804.1641853
3. Alliance, W.F.: Wi- alliance. http://www.wi-.org/ (2010)
4. Bahl, P., Padmanabhan, V.N.: Radar: an in-building rf-based user location and
tracking system. pp. 775784 (2000)
5. Balasubramanian, A., Levine, B., Venkataramani, A.: Dtn routing as a resource allocation problem. In: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications. pp. 373384. SIGCOMM '07, ACM, New York, NY, USA (2007),
http://doi.acm.org/10.1145/1282380.1282422
6. Burns, B., Brock, O., Levine, B.: Mv routing and capacity building in disruption
tolerant networks. In: INFOCOM 2005. 24th Annual Joint Conference of the IEEE
Computer and Communications Societies. Proceedings IEEE. vol. 1, pp. 398 408
vol. 1 (2005)
7. Carris: Carris: Transportes públicos lisboa. http://www.carris.pt/ (2010)
8. Carro, M.U.: Amtl: "É necessário recentrar a discussão no software do sistema, e
não no hardware"
29
9. Chou, H.T., DeWitt, D.J.: An evaluation of buer management strategies for relational database systems. In: Proceedings of the 11th international conference on
Very Large Data Bases - Volume 11. pp. 127141. VLDB '1985, VLDB Endowment
(1985), http://portal.acm.org/citation.cfm?id=1286760.1286772
10. Doering, M., Pögel, T., Wolf, L.: Dtn routing in urban public transport systems. In: Proceedings of the 5th ACM workshop on Challenged
networks. pp. 5562. CHANTS '10, ACM, New York, NY, USA (2010),
http://doi.acm.org/10.1145/1859934.1859947
11. Google: Google maps. http://maps.google.com/ (2010)
12. Haas, Z., Halpern, J., Li, L.: Gossip-based ad hoc routing. In: INFOCOM 2002.
Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. vol. 3, pp. 1707 1716 vol.3 (2002)
13. Hightower, J., Borriello, G.: Location sensing techniques. Tech. rep., IEEE Computer (2001)
14. Hightower, J., Borriello, G.: Location systems for ubiquitous computing. Computer
34, 5766 (August 2001), http://dx.doi.org/10.1109/2.940014
15. Johnson, D.B., Maltz, D.A.: Dynamic source routing in ad hoc wireless networks.
In: Imielinski, T., Korth, H.F. (eds.) Mobile Computing, The Kluwer International
Series in Engineering and Computer Science, vol. 353, pp. 153181. Springer US
(1996)
16. Lindgren, A., Phanse, K.: Evaluation of queueing policies and forwarding strategies for routing in intermittently connected networks. In: Communication System
Software and Middleware, 2006. Comsware 2006. First International Conference
on. pp. 1 10 (2006)
17. Lindgren, A., Doria, A., Schelén, O.: Probabilistic routing in intermittently connected networks. SIGMOBILE Mob. Comput. Commun. Rev. 7, 1920 (July 2003),
http://doi.acm.org/10.1145/961268.961272
18. Lisboa, M.: Metropolitano de lisboa. http://www.metrolisboa.pt/ (2010)
19. Liu, B.: Intelligent route nding: Combining knowledge, cases and an ecient search algorithm. In: In Proceedings of the 12th European Conference on Articial
Intelligence. pp. 380384. Wiley and Sons, Ltd (1996)
20. Lochert, C., Scheuermann, B., Mauve, M.: Probabilistic aggregation for data dissemination in vanets. In: Proceedings of the fourth ACM international workshop
on Vehicular ad hoc networks. pp. 18. VANET '07, ACM, New York, NY, USA
(2007), http://doi.acm.org/10.1145/1287748.1287750
21. Lochert, C., Scheuermann, B., Wewetzer, C., Luebke, A., Mauve, M.: Data
aggregation and roadside unit placement for a vanet trac information system. In: Proceedings of the fth ACM international workshop on VehiculAr
Inter-NETworking. pp. 5865. VANET '08, ACM, New York, NY, USA (2008),
http://doi.acm.org/10.1145/1410043.1410054
22. Nadeem, T., Dashtinezhad, S., Liao, C., Iftode, L.: Tracview: Trac data dissemination using car-to-car communication. ACM SIGMOBILE Mobile Computing
and Communications Review 8 (2004)
23. Online, M.: Caso de estudo: Refer. Revista no 34 (Maio 2010)
24. Perkins, C.E., Royer, E.M.: Ad-hoc on-demand distance vector routing. In: Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications. pp. 90. WMCSA '99, IEEE Computer Society, Washington, DC, USA
(1999), http://portal.acm.org/citation.cfm?id=520551.837511
25. RATP: Image: real-time trac information. http://www.ratp.fr/
26. RATP: Ratp site. http://www.ratp.fr/ (2010)
30
27. Sapo: Sapo mapas. http://mapas.sapo.pt/ (2010)
28. Élio Serra, Castro, L., Moniz, J.: Um sitema de ajuda à exploração e informação
ao público "o sae xtran passenger da carris"
R technology info site. http://www.bluetooth.com/
29. SIG, B.: The ocial bluetooth
(2010)
30. Spyropoulos, T., Psounis, K., Raghavendra, C.S.: Spray and wait: an ecient routing scheme for intermittently connected mobile networks. In: Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking. pp. 252259. WDTN '05, ACM, New York, NY, USA (2005),
http://doi.acm.org/10.1145/1080139.1080143
31. Tecmic: Casos de sucesso - tecmic. http://www.tecmic.pt/por/clientes/carris.html
(2010)
32. Tmar, S., Fleury, E.: Towards a clustering based data diusion protocol in
delay tolerant networks. In: Proceedings of the 2007 ACM CoNEXT conference. pp. 57:157:2. CoNEXT '07, ACM, New York, NY, USA (2007),
http://doi.acm.org/10.1145/1364654.1364720
33. Transporlis: Transporlis. http://www.transporlis.sapo.pt/ (2010)
34. Ye, H., Chen, Z., Xia, Z., Zhao, M.: A data dissemination policy by using human mobility patterns for delay-tolerant networks. In: Communications and Mobile Computing (CMC), 2010 International Conference on. vol. 1, pp. 432 436
(2010)
31
A
Planeamento