Universitatea Politehnica Bucuresti

Facultatea de Automatica si Calculatoare

Optimizarea traficului în aglomeraţii urbane

Student: Coordonatori:

Ichimescu Andrei Prof. Dr. Ing. Valentin Cristea,

Ing. Dr. Ciprian Dobre

2

Cuprins

Abstract ............................................................................................................................. 3

Introducere ....................................................................................................................... 4

Transportul in orasele mari .................................................................................... 4

Congestiile in trafic si impactul lor negativ ........................................................... 5

Confortul in trafic .................................................................................................. 7

Intelligent Transportation System .............................................................. 7

Vehicular ad-hoc Network ......................................................................... 9

Gasirea drumului optim ............................................................................. 9

Lucrari inrudite ............................................................................................................. 11

Simulatorul de trafic ...................................................................................................... 13

Modulul de mobilitate .......................................................................................... 17

Simulatorul de retea ............................................................................................. 20

Estimarea consumului de carburant si a emisiilor poluante ................................. 21

Vehicular Information Transfer Protocol ............................................................. 22

Generarea Scenariilor ........................................................................................... 23

Interfata Grafica ................................................................................................... 27

Arhitectura sistemului ................................................................................................... 32

Gradul de aglomerare ........................................................................................... 33

Semafoare inteligente ........................................................................................... 35

Server centralizat ................................................................................................. 36

Modulele aplicatiei ............................................................................................... 36

Detalii de design .................................................................................................. 38

Scenarii de test ................................................................................................................ 43

Rezultate ......................................................................................................................... 47

Concluzii si dezvoltari ulterioare .................................................................................. 60

Bibliografie ..................................................................................................................... 62

3

Abstract

In interiorul oraselor aglomerate, congestiile rutiere sunt des intalnite datorita

numarului mare de automobile. Imbunatatirea infrastructurii existente presupune costuri

prohibitive, de aceea este de dorit folosirea acesteia la capacitate maxima. Acest proiect

prezinta un model de optimizare a traficului prin modificarea in mod dinamic a traseelor

rutiere astfel incat durata de parcurgere a drumului pana la destinatie sa fie minima.

Folosind capabilitati de comunicare dedicate, automobilele pot comunica cu

infrastructura pentru a afla starea actuala a drumurilor sau daca pe unul din segmentele

de drum ce apartine traseului rutier stabilit a aparut o congestie. Aplicatia este o

extensie a platformei VNSim si este testata cu ajutorul simulatorului de trafic. In prima

parte a lucrarii voi prezenta simulatorul VNSim, dupa care voi descrie arhitectura si

metodele prin care va fi facuta optimizarea traficului. Ultima parte a lucrarii este

destinata rezultatelor si concluziilor.

4

Introducere

In ziua de azi, mijloacele de transport devin tot mai rapide si tot mai inteligente.

Intr-o lume a vitezei si pe o infrastructura (strazi, autostrazi) care nu s-a dezvoltat in

acelasi ritm, avand pe fond si eroarea umana, iminent apar accidentele si ambuteaje in

trafic.

Transportul in orasele mari

Transportul in orasele mari este influentat de mai multi factori: este influentat de

numarul de masini, de infrastructura existenta si depinde de transportul public.

Imbunatatirea infrastructurii (largirea strazilor, construirea de noi autostrazi si

pasaje) necesita costuri prohibitive iar autoritatile prefera sa amane cat mai mult acest

lucru. Un studiu in Statele Unite arata ca, in perioada 1980-1999, lungimea autostrazilor a

crescut cu 1.5% iar lungimea parcursa de masini a crescut cu 76% [1].

Solutii alternative, precum dezvoltarea transportului public, nu au avut succes in

statele din America de Nord, iar in Europa cresterea numarului de automobile nu s-a

atenuat conform asteptarilor.

Tarile nordice din Europa ofera subventii transportului public; Suedia a creat

sistemul Länstrafik pentru a dezvolta transportul public in zonele in care nu e profitabil

in termeni comerciali. In Finlanda, transportul public este extins in Helsinki, iar statul

ofera, asemeni Suediei, subventii in zonele rurale. In Marea Britanie, media utilizarii

autobuzelor a crescut din 1990 (desi a scazut cu 30% in Scotia, cu 28% in Tara Galilor, si

cu 22% in zonele rurale). Anglia a cunoscut o crestere cu 53% a rutelor feroviare intre

anii 1980 – 2006, iar in acelasi timp calatoriile cu metroul londonez au crescut cu 86%.

5

In Statele Unite, infrastructura oraselor s-a dezvoltat pentru masinile personale,

iar acum transportul public este non-existent, chiar si in orasele mari. Multe din sisteme

de transport existente pana la dominatia automobilului au fost dezafectate de industria

emergenta a masinilor intr-o miscare numita „Great American Streetcar Scandal”.

General Morors a reusit sa distruga 100 sisteme publice nationale de transport pana in

1950. Dupa aceasta data, au avut loc investigatii anti-trust [2]. Singura exceptie majora

este New York City, unde jumatate din locuitori nu detin o masina personala. O treime

din participantii la trafic locuiesc in New York si doua treimi in suburbii. S-au dezvoltat

doua companii feroviare care transporta locuitorii cu ajutorul metroului: New York City

Subway si PATH.

Congestiile in trafic si impactul lor negativ

Cresterea numarului de automobile si dezvoltarea insuficienta a infrastructurii

rutiere, precum si lipsa unui plan de dezvoltare urbana duc la formarea frecventa a

congestiilor.

Daca numarul de persoane care circula zilnic intre orase este relativ mic, in

interiorul oraselor lucrurile nu stau la fel. Fie ca mergem la servici, la facultate sau la

supermarket, avem nevoie de un mijloc de transport care, in mod inevitabil, contribuie la

aglomerarea strazilor. In orasele mari, datorita densitatii populatiei, apar deseori blocaje

rutiere, se formeaza cozi interminabile la semafoare, iar viteza medie de deplasare scade

drastic. De cele mai multe ori strazile se aglomereaza in timpul orelor de varf, insa exista

si alte cauze cum ar fi lucrarile publice, conditiile meteo nefavorabile (ceata, polei),

coliziuni neprevazute, etc. Toate aceste lucruri au un impact major asupra economiei

(Texas Transportation Institute de exemplu, a calculat o pierdere in productivitate de 67.5

miliarde de dolari din cauza traficului pentru cele mai mari 75 metropole), asupra

mediului (datorita poluarii si a gazelor de sera care contribuie la incalzirea globala) si

asupra soferilor (stres, scaderea confortului in trafic si costuri aditionale estimate la

1000$ pe an pentru orasele mari).

6

Figura 1: Congestie pe o strada din New York

Figura 2: congestie pe o strada din Moscova

7

Pe langa impactul negativ pe care il au asupra economiei, congestiile in trafic au

ca rezultat cresterea timpiilor de deplasare pana la destinatie si inabilitatea de a estima

timpul unei calatorii; cresterea consumului de combustibil; scaderea fiabilitatii

automobilelor datorita accelerarilor si franarilor frecvente; imposibilitatea vehiculelor de

urgenta (ambulanta, pompieri, politie) de a se deplasa urgent unde este nevoie.

Congestionarea arterelor principale duce la aglomerarea strazilor secundare din

jur si are efect negativ asupra zonelor rezindentiale datorita poluarii fonice.

Confortul in trafic

Intelligent Transportation System

Intelligent Transportation System (ITS) [4] se refera la efortul de a adauga

informatii si tehnologii de comunicare infrastructurii de transport si automobilelor in

vederea imbunatatirii sigurantei si a reducerii timpilor de transport, a consumului de

combustibili si a congestiilor din trafic.

Folosind camere de luat vederi in infrarosu sau de viteza, bucle inductive,

detectori de congestie si alti senzori inglobati in asfalt sau in semafoarele si in

indicatoarele din intersectii, sistemele ITS pot monitoriza traficul si lua decizii pentru

fluidizarea acestuia. Alte aplicatii care tin de Intelligent Transportation System includ

colectarea automata a taxelor de autostrada, recunoasterea automata a numerelor de

inmatriculare sau sisteme de notificare in caz de accident.

Pentru ITS au fost propuse tehnologii variate de comunicare. Pe distante scurte

(pana in 500m) comunicarea poate fi efectuata folosind protocolul IEEE 802.11. In

special standardul WAVE si standardul Dedicated Short Range Communications sunt

promovate de catre Intelligent Transportation Society of America si de catre United

States Department of Transportation. Pentru distante mari, au fost propuse infrastructuri

8

bazate pe WiMax (IEEE 802.16), Global System for Mobile Communications (GSM) si

3G. Aceste protocoale de comunicare sunt bine puse la punct, spre deosebire de cele cu

raza mica de actiune, in schimb implementarea unor astfel de infrastructuri este foarte

costisitoare.

Din punct de vedere computational, progresul inregistrat in electronica

automobilului determina o miscare catre procesoare mai putine ca numar dar mai

capabile. In anul 2000, un automobil avea de la 20 la 100 de microcontrolere

interconectate. Trendul curent este de a migra la microprocesoare cu managementul

memoriei integrat in hardware si sisteme de operare in timp real. Aceste platforme

integrate permit implementarea unor aplicatii software sofisiticate si a inteligentei

artificiale.

Buclele inductive sunt plasate in asfalt si detecteaza vehiculele care trec prin

dreptul lor masurand campul magnetic al acestora. Cei mai simplii detectori numara

vehiculele care trec intr-o unitate de timp (60 secunde in Statele Unite), in timp ce

senzorii mai sofisticati estimeaza viteza, lungimea, greutatea automobilelor precum si

distanta dintre ele. Buclele inductive pot fi plaste pe una sau mai multe benzi si

detecteaza atat vehiculele oprite sau care se misca cu viteza redusa, cat si vehiculele care

se deplaseaza cu viteza mare.

Masurarea traficului si detectarea in mod automatic al accidentelor se realizeaza

cu ajutorul camerelor video. Deoarece acestea nu se amplaseaza in interiorul strazilor, ci

pe stalpi sau pe structuri similare suspendate, sistemul este numit non-intrusiv. Imaginile

video alb-negru sau color sunt trimise unui procesor care poate analiza simultan date

provenite de la una pana la opt camere. In mod frecvent, un astfel de sistem de detectie

monitorizeaza viteza automobilelor, numarul lor si gradul de ocupare al benzilor. Alte

sisteme pot detecta automobilele oprite si pot masura distanta dintre vehicule.

9

Vehicular ad-hoc Network

Siguranta in trafic a capatat prioritate si, odata cu dezvoltarea tehnologiilor in

domeniul comunicatiilor si al retelelor wireless, au fost create si retelele VANET.

VANET sau Vehicular ad-hoc Network [5] asigura un protocol de comunicatie

intre vehiculele apropiate sau intre un automobil si infrastructura (indicator, semafor,

intersectie). Se asteapta ca intre entitati, comunicarea sa se realizeze wireless in banda de

5.9Ghz cu ajutorul tehnologiei Dedicated Short-Range Communications (DSRC).

Automobilele sunt folosite ca noduri mobile pentru a creea o retea ad-hoc. Fiecare nod

reprezinta de fapt un router wireless care permite altor noduri sa se conecteze la retea,

extinzandu-i raza de acoperire. Se estimeaza ca primele sisteme care vor implementa

aceasta tehnologie vor fi destinate pentru politie si pentru pompieri, pentru ca masinile sa

poate comunica intre ele din motive de siguranta.

Vehicular ad-hoc Network poate fi vazut ca o componenta a Sistemului Inteligent

de Transport (ITS). Principalul scop al acestor retele ramane siguranta pasagerilor si

confortul in trafic.

Prin dotarea automobilelor cu echipamente de comunicare, si prin organizarea

acestora in retele ad-hoc, nu ne mai ramane decat un pas pentru proiectarea de servicii si

aplicatii care sa imbunatateasca experienta conducerii automobilului.

Gasirea drumului optim

Gasirea drumului optim intr-un oras a luat nastere o data cu aparitia

navigatoarelor GPS. Un drum optim poate fi drumul cel mai scurt din punct de vedere al

distantei. Poate fi drumul cel mai scurt din punct de vedere al timpului parcurs in trafic

sau poate fi drumul cel mai ieftin economic. Cea mai intalnita solutie este gasirea

drumului cel mai scurt. Aceasta se bazeaza pe informatii statice (drumurile orasului) si de

pozitia automobilului in trafic. Insa strazile unui oras au un caracter dinamic. Ele pot fi

inchise pentru lucrari de reabilitare, se pot intampla blocaje rutiere, pot fi aglomerate sau

pot fi libere. Avand aceste informatii la dispozitie, putem calcula drumul drumul cel mai

10

scurt (din perspectiva temporala). Traseul astfel gasit va avea in plus mai multe beneficii:

se vor reduce numarul de franari si accelerari ale automobilului rezultand un consum de

combustibil mai mic; de altfel se reduce si gradul de uzura al vehicolului si se micsoreaza

riscul de a fi prins intr-un ambuteaj rutier.

In acest document voi prezenta un serviciu pentru gasirea drumului optim,

serviciu bazat pe modificarea dinamica a traseelor. Proiectul este destinat in special

oraselor aglomerate, unde confortul de trafic este minim datorita numarului mare de

automobile care depaseste capacitatea infrastructurii. De asemenea serviciul poate fi

implementat si in orasele care nu sunt in general aglomerate, dar in care fenomenul de

„ore de varf” este prezent. Solutia foloseste tehnologia VANET pentru transferul de

informatii intre automobile si intre automobile si infrastructura.

Pentru modificarea dinamica a traseelor avem nevoie de harta orasului impreuna

cu starea curenta a fiecarei strazi (inaccesibila, aglomerata, libera). Aceste date sunt

culese din comunicarea automobil-infrastructura si trimise unui server centralizat. In

acest moment putem crea online si in timp real o harta a orasului cu gradul de aglomerare

al drumurilor. Serverul centralizat va tine ulterior in memorie si starea medie de

aglomerare a fiecarei strazi. Din diferenta celor doua putem determina deopotriva atat

drumurile aglomerate cat si pe cele libere. Noua informatie va putea fi trimisa in sens

invers inapoi la computerul de bord al automobilelor, care impreuna cu modulul GPS va

putea calcula dinamic traseul catre destinatia finala.

11

Lucrari inrudite

Problema gasirii drumului optim intr-un oras aglomerat a fost abordata in mai

multe lucrari.

Unele solutii sunt bazate pe tehnica invatarii din experienta [7]. Dupa parcurgerea

drumului, conducatorul auto va introduce manual durata acestuia, urmand ca pe viitor sa

se selecteze drumul optim. Aplicatiile de acest gen sunt oarecum limitate, deoarece

considera mediul de transport ca fiind unul static. Astfel, nu sunt luate in calcul

accidentele neprevazute sau conditiile meteo nefavorabile care pot avea un impact major

asupra starii strazilor. In plus, in cazul deplasarii intr-un oras necunoscut, nu vom

beneficia de nici un fel de informatii care sa ne ajute in determinarea drumului optim.

Alte solutii folosesc datele captate de diversi senzori (camere in infrarosu, bucle

inductive inglobate in asfalt). O astfel de aplicatie a fost implementata de G. Eggenkamp

si L.J.M. Rothkrantz [8]. Un sistem expert este folosit pentru a calcula drumul optim in

locul clasicului algoritm Dijkstra. Rezultatele au aratat ca sistemul expert gaseste mai

repede drumul cel mai scurt, in schimb necesita un timp foarte mare pentru programarea

regulilor de inferenta. De asemenea integrarea senzorilor in fiecare intersectie a unui oras

mare este extrem de costisitoare. Momentan aplicatiile bazate pe acest tip de senzori sunt

destinate autostrazilor iar serviciile oferite se limiteaza la regularea traficului rutier.

Collaborating Route Planning in Vehicular Ad-hoc Networks [9] este o aplicatie

in care se analizeaza doua variante: Greedy si hybrid. Este folosita platforma TraficView

pentru simularea mobilitatii automobilelor precum si pentru simularea protocolului

VANET. Spatiul de cautare este redus la strazile si arterele principale pentru a imbunatati

timpul de executie al algoritmului Dijkstra (folosit pentru determinarea drumului minim

pe grafuri cu arce de cost non-negativ). Aceasta reducere a spatiului a fost posibila

deoarece conducatorii auto prefera arterele principale in locul celor secundare pentru

deplasarea prin oras. Algoritmul de cautare in acest caz este de pana la 3 ori mai rapid,

12

pentru orasele a caror diametru este intre 40 si 100km. Varianta Greedy presupune ca

doar o parte din participantii la trafic foloseste drumurile principale pentru a ajunge la

destinatie in timpul cel mai scurt, cealalta parte utilizand abordarea clasica – drumul cel

mai scurt din punct de vedere al distantei (include si strazile secundare). Automobilul, in

drumul sau pana la destinatie, intreaba participantii la trafic, printr-un mecanism querry-

reply, despre conditiile de drum. In cazul in care este reportata o anomalie, se va cauta un

nou traseu. Rezultatele cele mai bune pentru abordarea Greedy sunt obtinute cand 60%

din participantii la trafic folosesc drumul minim si 40% din participantii la trafic folosesc

drumul cel mai scurt. Distributia 60-40 asigura o ocupare mai uniforma atat a strazilor

principale cat si a celor secundare. Varianta hybrid adauga la nodurile retelei VANET si

intersectiile semaforizate. Conectate la o retea de mare viteza, semafoarele vor avea acces

la o baza de date cu toate segmentele rutiere, impreuna cu timpii lor de parcurgere. In

acest caz, un automobil va primi de la fiecare semafor drumul optim, considerand toate

conditiile posibile de trafic. Timpii pana la destinatie obtinuti in acest caz, desi sunt cu

putin mai mari decat minimele din varianta Greedy, sunt cu 20-30% mai mici, deoarece

se aplica pentru toate automobilele.

13

Simulatorul de trafic

Simulator VNSim [10] a fost dezvoltat in cadrul Universitatii Politehnica din

Bucuresti si are ca obiectiv testarea performantelor unei game largi de tehnologii

caracteristice sistemelor VANET. In cadrul aplicatiei de simulare sunt modelate atat

componente de retea wireless ce asigura comunicatia intre participantii la trafic, cat si

mobilitatea soferilor ce circula pe emulari ale unor sosele reale.

Figura 3: Difuzarea datelor de la un automobil la altul.

Pentru a ilustra mecanismul de difuzare, presupunem ca in Figura 3, vehiculele 2

si 3 se afla in raza de transmisie a automobilului 1. De asemenea, vehiculul 4 se afla in

raza vehicului 3, iar vehiculul 3 se afla la randul lui in raza lui 2. La inceput fiecare

automobil isi cunoaste propria pozitie si viteza. Dupa prima perioada de difuzare,

vehiculele 2 si 3 primesc mesajul automobilului 1 si ii stocheaza informatiile. La fel se

intampla si pentru vehiculul 4 care primeste mesajul lui 3. Dupa urmatoarea perioada de

difuzare, autmobilul 4 primeste inca o data mesajul lui 3 care, mai nou, include informatii

si despre 1 si 2.

14

Fiecare vehicul retine date despre celelalte automobile in baza de date locala.

Cand o intrare este primita pentru prima oara, ea este memorata intr-un set non-validat,

din moment ce poate contine informatii conflictuale. Dupa ce aceste date sunt examinate

pentru validitate, ele vor fi adaugate setului valid.

Figura 4: Screenshot cu simularea unei intersectii in VNSim

VNSim este scris in Java si se bazeaza pe simularea bazata pe evenimente

discrete. Fiecare nod simulat contine cateva module care lucreaza pe cate un set de date.

Fiecare inregistrare a unui automobil contine urmatoarele campuri:

Identification (ID): Identificator unic pentru inregistrarile diverselor vehicule.

Position (POS): Pozitia curenta estimativa a automobilului.

Speed (SPD): Folosita pentru determinarea pozitiei automobilului, daca nu mai

exista mesaje receptionate.

15

Broadcast Time (BT): Timpul global la care autmobilul difuzeaza propriile

informatii catre ceilalti participanti la trafic.

Figura 5: Structura unui nod din VNSim.

Modulul GPS/OBD actualizeaza in mod periodic datele automobilului propriu.

Intrarile GPS sunt ajustate prin modulul de navigare (care depinde de formatul hartilor si

de celelalte intrari GPS), inainte de a fi stocate.

Modulul Receive asculta mesajele difuzate de vehiculele invecinate si stocheaza

inregistrarile primite in setul de date non-validat. Vor fi ignorate mesajele difuzate de

propriul automobil.

Modulul Validation valideaza si rezolva conflictele din inregistrarile setului de

date non-validat. Apoi adauga noile date la versiunea validata de inregistrari. De

exemplu, acest modul sterge inregistrarile automobilelor aflate in spatele vehicului

propriu. VNSim nu lucreaza cu date ce apartin automobilelor din spate. Un alt exemplu

este testarea pemtru inregistrarile multiple ce apartin aceluias autmobil. In acest caz este

tinuta cea mai recenta inregistrare, celelalte fiind inlaturate din setul de date. Acest modul

16

actualizeaza periodic si pozitia estimativa a automobilului folosind viteza acestuia. Mai

mult, modulul este responsabil pentru invalidarea inregistrarilor vechi.

Modulul Aggregation ruleaza algoritmi de agregare peste inregistrarile din setul

de date validat, in scopul de a plasa cat mai multa informatie in mesajele de difuzare.

Acest modul poate sa actualizeze setul de date inlocuind inregistrarile originale cu

versiunea lor noua, agregata.

Modulul Send incapsuleaza continutul setului de date validat intr-un mesaj pe

care il va trimite canalului wireless, folosind o placa de retea.

Modulul Display/UI este responsabil pentru afisarea inregistrarilor pe ecran. De

asemenea se ocupa cu interactia cu utilizatorul (grafic si/sau sonor).

VNSim nu sufera de limitari ale memoriei datorita inregistrarilor de dimensiune

mica. Marimea medie a acestor inregistrari este de 50bytes. Daca consideram o strada

foarte densa cu 5 benzi in care distanta dintre automobilele consecutive este de 5 metrii,

avem nevoie de aproximativ 5Kbytes pentru a stoca informatia necesara a tuturor

automobilelor pe o raza de 100metrii. Pentru a stoca informatia automobilelor pe o raza

de 20km avem nevoie de 1Mbyte.

Pe de alta parte, daca distanta de transmisie/receptie a placii de retea wireless este

de 250 metri, vor fi 50 de automobile pe fiecare banda care vor concura pentru acelasi

mediu. Daca consideram strada cu 5 benzi, vom obtine 250 automobile. Astfel datele

transmise vor contoriza 250Mbytes, lucru care depaseste capabilitatile tehnologiei

wireless actuale. Pentru a face fata limitarii de banda, fiecare automobil ii este permis sa

transmita un pachet de difuzare mic (cativa kbytes) la un moment specific de timp. Se

folosesc de altfel si algoritmi de agregare si compresie.

Simulatorul [11] este bazat pe evenimente discrete, timpul simularii avansand de

fiecare date cu un interval fix, dupa ce s-a executat tot codul pentru timpul curent. Mai

17

specific la fiecare moment al simularii, toate evenimentele sunt extrase dintr-o coada si

procesate in ordine aleatoare.

Evenimentele din coada pot fi de 3 tipuri: send, receive sau GPS. Un eveniment

send al unui nod apeleaza procedura responsabila pentru pregatirea mesajului acelui nod.

De asemenea, planifica evenimentul receive corespunzator destinatarului/destinatarilor

conform modulului de retea. Evenimentul receive este asociat unui nod specific, sau unui

grup de noduri (pentru care mesajul va fi difuzat). Actiunea sa apeleaza procedura de

tratare a evenimentului in fiecare dintre nodurile destinatare. Evenimentul GPS este

programat la un interval regulat pentru fiecare nod, pentru a simula receptionarea datelor

GPS din lumea reala.

Modulul de mobilitate

Modulul de mobilitate actualizeaza periodic pozitia fiecarui nod (care reprezinta

un automobil) conform modelului de miscare. Acest model ia in calcul interactiunile

dintre automobile (depasire, urmarire a masinii din fata, etc), regulile de trafic si

comportamentul diferit al soferilor.

In aplicatiile VANET toate vehiculele sunt parti ale sistemului, sistem care trebuie

sa detina o harta digitala. Pentru VNSim au fost alese fisierele TIGER, care sunt

disponibile gratuit (http://www.census.gov/geo/www/tiger). Fisierele TIGER contin

informatii geografice detaliate despre toate strazile dintr-o regiune, de la strazi secundare

pana la autostrazi. Reprezentarea acestor date se face utilizand latitudinea si longitudinea,

iar pentru fiecare strada fisierele TIGER specifica coordonatele capetelor strazii, precum

si a punctelor intermediare ale acelei strazi (in functie de geometria ei). Mai mult decat

atat, pentru fiecare strada este specificat si tipul ei (mica, locala, nationala, autostrada

interstatala, etc).

Din pacate baza de date TIGER(Topologically Integrated Geographic Encoding

and Referencing system) nu ofera informatii specifice de trafic, cum ar fi numarul de

18

benzi, semafoare, indicatoare de prioritate sau cedeaza trecerea. Un simulator care nu ia

in calcul aceste informatii, nu este suficient de realist, iar VNSim permite introducerea

acestor extra-informatii.

Un simulator de trafic care ia in considerare actiunile fiecarui vehicul este un

simulator microscopic, spre deosebire de simulatorul macroscopic, care descrie evolutia

traficului folosind masuri globale cum ar fi marimea miscarii sau densitatea traficului.

Simulatoarele macroscopice sunt folosite pentru intelegerea dinamicii si pentru o mai

buna proiectare a infrastructurii (semafoare, indicatoare, numar de benzi pe fiecare sens,

etc). Un nivel mai mare de detaliu este necesar insa pentru studierea retelelor de vehicule,

si de aceea VNSim este dezvoltat la nivel microscopic.

Modelul de comportament al conducatorilor auto are un rol important in

modelarea traficului, iar VNSim implementeaza 4 moduri: free driving, approaching,

following si breaking.

In modul free driving nu exista nici o influenta din partea vehiculelor din fata,

aflate pe aceeasi banda de mers. In aceasta situatie soferul incearca sa mentina constanta

viteza dorita. Aceasta viteza depinde de personalitatea conducatorului auto si de

caracteristicile strazii.

In modul approaching exista in fata pe aceeasi banda un vehicul mai lent care va

influenta comportamentul soferului. Acesta va frana pentru a obtine aceeasi viteza ca si

cea a automobilului precedent. Intensitatea franarii este o functie care depinde de distanta

dintre cele doua vehicule, de viteza lor si de alti parametrii.

In modul following atat automobilul cat si vehiculul din fata au aproximativ

acceasi viteza si in aceasta situatie soferul va cauta sa pastreze viteza constanta.

19

Modul breaking presupune existenta unui vehicul lent in fata automobilului la o

distanta foarte mica. In acest mod, datorita pericolului iminent, conducatorul auto aplica

o rata de franare maxima.

VNSim implementeaza de asemenea si un model de schimbare a benzii de drum.

Acest model se bazeaza pe regulile europene. Astfel, folosirea primei benzi este

obligatorie in cazul in care nu este ocupata. Automobilele vor sta pe benzile inferioare si

vor schimba banda numai cand efectueaza depasiri. Nu sunt permise depasirie pe partea

dreapta. Aceste reguli nu se aplica in interiorul oraselor sau in apropierea intersectiilor,

unde banda este selectata conform directiei pe care conducatorul auto intentioneaza sa o

urmeze.

Modelul de schimbare al benzilor de drum tine cont de ierarhia celor 4 moduri de

condus. De fiecare data cand soferul auto este intr-un alt mod decat free driving, el va

testa daca trecerea pe o banda superioara ii va oferi un mod mai bun de condus. Pentru

cazul favorabil, automobilul va trece pe banda superioara. Similar, daca soferul auto se

afla in oricare alt mod in afara de braking, el va testa daca trecerea pe o banda inferioara

ii ofera cel putin aceleasi conditii de trafic; daca este cazul va trece pe banda inferioara.

Ordinea testelor este importanta, primul test fiind cel pentru banda superioara. Astfel,

daca un conducator auto se afla pe banda 2 si se apropie de un vehicul mai lent, el va

verifica daca banda 3 este libera, si daca e cazul se va deplasa pe aceasta banda (doar

daca nu exista alte automobile care sa vina din spate pe banda 3). Daca ar fi testat intai

banda 1, si ar fi descoperit-o libera, soferul ar fi incercat sa efectueze depasirea folosind

banda 1. Depasirea prin dreapta este interzisa in majoritatea statelor europene. In schimb

acest lucru este posibil in Statele Unite, unde orice banda poate fi folosita pentru depasiri.

Traficul din Statele Unite poate fi simulat usor prin alegerea in mod aleator a aplicarii

celor doua teste.

VNSim incorporeaza si un sistem de control al traficului. Automobilele simulate

tin cont de semafoarele existente, de indicatoarele de prioritate, cedeaza trecerea sau de

stop. Miscarea lor se face in concordanta cu aceste elemente de control.

20

Figura 6: Strada cu 4 benzi, 3a – vehiculele asteapta la semafor; 3b – vehiculele

traverseaza intersectia (semaforul e pe culoarea verde)

Profiluri diferite ale conducatorilor auto (aggressive, regular, calm) sunt modelate

usor, cu ajutorul parametrilor. Fiecare tip este reprezentat de un anumit set de parametrii.

Pentru a diferentia si mai mult soferii auto, exista o mica deviatie de la parametrii

standard, deviatie calculata aleator pentru fiecare sofer in parte.

Simulatorul de retea

Acest modul se ocupa cu trimiterea mesajelor de la un nod la altul. Ofera un set

de primitive de retea care pot fi apelate de catre nodurile aplicatiei dezvoltate peste

platforma de simulare. Ne intereseaza in mod special nivelurile fizic si legatura de date,

care influenteaza performanta aplicatiilor VANET.

La nivelul fizic, se foloseste un model cumulativ pentru calculul zgomotului, iar

receptia semnalului depinde de pragul semnal – zgomot (SNR signal-to-noise ratio).

Acest lucru inseamna ca la receptionarea unei unde radio cu o anumita putere a

semnalului, zgomotul este calculat ca suma celelaltor semnale de pe canal, iar raportul

21

celor doua valori reprezinta valoarea SNR. Daca aceasta valoare este mai mare decat

pragul SNR stabilit, atunci semnalul va fi receptionat cu succes.

Propagarea undelor radio poate fi afectata de trei fenomene independente: path

loss, fading si shadowing. Dintre acestea efectul cel mai mare il are path loss (atenuarea

de transmisie) si reprezinta reducerea puterii unei unde radio care se propaga prin spatiu.

VNSim are 2 modele de propagare: atenuarea in spatiu liber si atenuarea cu 2 raze pe

suprafata Pamantului. Primul model este unul idealizat, spre deosebire de al doilea care

tine cont de reflectiile care apar pe suprafata Pamantului, si in consecinta, este mai precis.

Simulatorul trimite mesajele la nodurile de destinatie aflate in raza intr-un mod

optim, folosind o cautare locala a nodurilor. Acest lucru este posibil datorita indexarii

eficiente a punctelor de pe harta, folosindu-se un mecanism PeanoKey (Dashtinezhad et.

al. 2004). Un PeanoKey este asociat unui punct din spatiul 2D si se obtine interclasand

cifrele celor 2 coordonate. De exemplu PeanoKey-ul asociat unui punct geografic avand

26.047 grade longitudine si 44.435 grade latitudine este 4246403057. Cand harta este

construita, este creat si un set sortat de PeanoKeys, asociat punctelor de pe harta.

PeanoKey-uri consecutive intr-un set corespund unor puncte de pe harta care sunt

apropiate. In aceasta maniera mediul wireless al unui nod este analizat rapid, vecinii sai

sunt descoperiti si o harta a semnalelor radio este construita.

La nivelul legaturii de date a fost implementat mecanismul CSMA/CA (Carrier

Sense Multiple Access Collision Avoidance), mecanism bazat pe standardul IEEE

802.11. Principiul de baza este „asculta inainte de a vorbi”. Daca un nod are de transmis

un pachet, va asculta mediul, si daca acesta e liber, va incepe transmisia. Daca mediul

este ocupat, nodul va astepta un timp aleator inainte de a reincerca sa trimita pachetul.

Estimarea consumului de carburant si a emisiilor poluante

Cand analizam traficul intr-o regiune, un rol important il are estimarea

consumului de carburant si a emisiilor poluante. Impactul aplicatiilor VANET asupra

22

consumului si a emisiilor poate fi studiat cu ajutorul simulatorului VNSim. Modelul

implementat este inspirat din lucrarea lui Akcelik si Besley (2003). Estimarile facute

depind de viteza si acceleratia autmobilului. Modelul este simplificat pentru a lua in

calcul numai vehiculele usoare. Fiind bazat pe miscarea automobilelor, simulatorul poate

calcula cu precizie consumul de carburant si emisiile pentru fiecare vehicul. Se pot obtine

usor statistici si marimi globale.

Vehicular Information Transfer Protocol (VITP)

VITP [12] este un protocol de comunicare la nivelul aplicatiei. VITP este o

infrastructura ad-hoc distribuita, peste reteaua VANET. Infrastructura poate fi folosita

pentru a oferi conducatorilor auto servicii de trafic bazate pe locatia fizica a

automobilului. Informatiile despre pozitia curenta a vehiculelor vin de la sistemul de

navigarie GPS si de la senzorii automobilului. Protocolul specifica sintaxa si semantica

mesajelor dintre nodurile VITP. Entitatile VITP stabilesc in mod dinamic grupuri ad-hoc

care colecteaza, comunica si combina informatia de la diversi senzori si de la alte

vehicule pentru a solutiona cererile primite. VITP este inspirat din HTTP HyperText

Transfer Protoocol, dar difera in cateva aspecte fundamentale, cum ar fi: semantica dintre

entitatile VITP care interactioneaza; functionalitatea si rolul componentelor software in

VITP vs clienti si servere in HTTP; suportul pentru comunicatia bazata pe „push”. Aceste

diferente sunt datorate in principal naturii dinamice, ad-hoc, si a lipsei de incredere

pentru retelele VANET.

VITP defineste doua tipuri de mesaje care pot fi initiate de un automobil: POST si

GET. Mesajul de tip POST este incapsulat intr-un pachet ce va fi rutat catre o destinatie,

si va fi periodic difuzat de catre vehiculele din regiune. Scopul este informarea

conducatorilor auto despre conditiile de drum prezente in acea zona. Mesajul de tip GET

este incapsulat intr-un pachet care va incearca sa gaseasca un anumit gen de informatie

despre o zona de destinatie. O data solutionata cererea, pachetul se va intoarce la

automobilul care l-a generat.

23

Generarea Scenariilor

Generarea scenariilor este procesul prin care o harta de tip tiger (fisier cu extensia

.rt1) este transformata intr-un scenariu numit Final Scenario File (extensia .smf) .

Figura 7: Configurarea scenariilor de simulat

Utilizatorul alege din lista Raw maps o harta in format tiger, iar prin apasarea

butonului Build Map, harta este transformata intr-un obiect de tip map. In lista Raw maps

sunt afisate doar fisierele cu extensia .rt1, insa VNSim incarca si fisierul cu extensia rt2,

cu acelasi nume. In fisierele .rt1 sunt definite capetele strazilor, prin coordonatele

latitudine si longitudine, iar fisierele .rt2 definesc forma strazilor si locul intersectiilor,

prin puncte intermediare.

Obiectul de tip map contine toate informatiile din fisierele .rt1 si .rt2. In plus sunt

adaugate mai multe puncte intermediare care formeaza segmente de strazi. Aceste

segmente sunt apoi imbinate, daca nu formeaza bucle.

Pentru ca fisierele tiger nu ofera informatii despre semafoare si indicatoare de

prioritate, VNSim adauga automat elementele de control a traficului. Daca strazile unei

24

intersectii sunt de acelasi tip (primare sau secundare), atunci un semafor va fi adaugat in

intersectie. Daca strazile sunt diferite, atunci in intersectie drumul principal va fi drumul

cu prioritate, iar pe drumul secundar se adauga un indicator de tip „cedeaza trecerea”.

Pentru scenarii aglomerate, cum ar fi strazile unui oras, este indicat sa se puna semafoare

in toate intersectiile, deoarece e posibil ca vehiculele de pe strazile secundare sa ramana

blocate, din cauza fluxului mare de vehicule de pe strazile cu prioritate.

Figura 8: Intersectie semaforizata

Figura 9: Intersectie cu indicatoare de prioritate

25

Informatiile din obiectul Map sunt serializate si salvate pe disk pentru accesari

ulterioare.

Un obiect de tip Map este incarcat la apasarea butonului Create Empty Scenarios

(Figura 7). Sunt adaugate doua liste, una cu locatiile de intrare ale vehiculelor in scenariu,

cealalta cu locatiile in care se indreapta vehiculele. Rute predefinite sunt generate intre

fiecare pereche intrare-iesire. Aceste date sunt serializate intr-un fisier cu extensia .smf

(Scenario Map File).

Scenario Designer configureaza numarul de masini care va fi generat pentru

fieacare ruta, precum si personalitatea conducatorilor auto. Scenario Designer are ca

rezultat crearea fisierelor Final Scenario (.fsc).

Primul pas este selectia scenariu specific (Figura 10) pentru a-l configura de la

zero, sau pentru a-l modifica. Fisierele se gasesc in directorul /maps/smf/. Designerul va

afisa toate scenariile si va permite utilizatorului sa aleaga unul din ele.

Figura 10: Selectia scenariului

26

Dupa selectia scenariului, urmeaza faza de configurare a acestuia (Figura 11).

Utilizatorului i se prezinta in coltul din stanga sus o lista cu toate intrarile disponibile.

Pentru fiecare intrare, se poate specifica numarul de vehicule pe ora pe fiecare banda care

vor fi generate. Campul vehicles/hour/lane se gaseste in dreapta sus. Sub acest camp se

afla distributia tipurilor de personalitati ale conducatorilor auto. Tipurile de personalitati

implementate pot fi very calm, regular si aggresive.

Figura 11: Configurarea fluxului de vehicule pentru fiecare ruta

Din numarul total de masini care sunt generate pentru o intrare, pentru fiecare

iesire in parte, doar un procent din vehicule va fi rutat catre acea iesire. Acest camp se

numeste PercentOfTraffic. Nu este necesar ca toate procentele specificate sa insumeze

100. La sfarsitul configurarii, valorile corespunzatoare se insumeaza si procentul fiecarei

iesiri este calculat.

Pentru ca rutele precalculate in „Scenario Map File” s-ar putea sa fie insuficiente,

utilizatorul isi poate defini singur rute proprii. Pentru a adauga o ruta, si implicit intrarea

si iesirea corespunzatoare, utilizatorul trebuie sa apese intai pe butonul „Add a route”.

Apoi poate selecta puncte de pe harta. Primul punct va fi punctul de intrare, urmatoarele

27

vor fi doar intersectii in care se schimba strada. In final se selecteaza punctul de iesire.

Toate aceste puncte vor fi salvate cand utilizatorul apasa butonul „Add it”, dupa ce

acestea au fost verificate pentru validitate.

Scenariul poate fi salvat sub un nume diferit specificat de utilizator, daca se

doreste acest lucru. Daca nu se specifica numele scenariului, implicit scenariul va avea

numele fisierului .smf.

Interfata Grafica

VNSim dispune de o interfata grafica, cu ajutorul careia utilizatorul poate

vizualiza simularea unui scenariu. In particular, este utila pentru identificarea cazurilor

particulare, care de altfel ar fi greu de detectat.

Interfata grafica este impartita in trei zone: intr-o zona este reprezentata harta si

vehiculele care care sunt simulate la momentul respectiv, o zona pentru controlul

simularii, si o zona in care sunt afisate statistici (Figura 12).

Zona in care este reprezentata harta permite utilizatorului sa schimbe zona

vizualizata, prin apasarea sagetilor de la marginea zonei. De altfel se poate mari sau

micsora o zona de interes prin folosirea butoanelor „zoomIn” respectiv „zoomOut”.

Vehiculele sunt reprezentate ca sfere, si pentru fiecare automobil doua tipuri de

sfere sunt afisate. Simulatorul genereaza automobile care se misca asemenea celor din

realitate, simuland o miscare continua (rezolutie de timp inalta). Pe de alta parte,

vehiculele simulate primesc pozitia lor prin mijloace de localizare GPS o data la fiecare

secunda (rezolutie a miscarii scazuta). De aceea sunt afisate doua tipuri de sfere.

28

Figura 12: Interfata grafica a simulatorului

Butonul „Switch view” permite utilizatorului sa schimbe rezolutia de timp a

simulatorului, de la o miscare fluida de rezolutie inalta, la miscarea de rezolutie joasa in

care pozitia vehiculelor este actualizata la fiecare secunda.

Din toate vehiculele afisate, utilizatorul poate selecta un automobil, caz in care

informatii specifice masinii sunt afisate. Selectarea unui automobil se face apasand de

doua ori pe harta. Primul click, va mari zona in care se afla masina, pentru o precizie mai

mare, urmand ca al doilea click sa selecteze automobilul.

Automobilul selectat va fi afisat ca o sfera de culoare alba, iar vehiculele pe care

acesta le cunoaste vor fi afisate ca sfere purpurii. Aceasta informatie este utila cand

29

utilizatorul doreste sa vizualizeze exact cat cunoaste automobilul despre ceilalti

participanti la trafic.

O data ce a fost selectat un automobil, utilizatorul poate schimba vederea

bidimensionala a hartii cu o vedere tridimensionala, vazuta din perspectiva soferului

vehiculului (Figura 13). Aceasta vedere este construita din informatia pe care o are

automobilul despre ceilalti participanti la trafic. Astfel aceasta vedere este interesanta,

deoarece poate afisa conducatorului auto informatii care pot fi de real ajutor in situatiile

caracterizate de vizibilitate redusa, datorita conditiilor meteo nefavorabile, sau pe timpul

noptii. Butonul „Driver mode” realizeaza schimbul intre vederi.

In vederea din perspectiva soferului, utilizatorul poate vedea si semafoarele din

zona inconjuratoare. Acest lucru este posibil deoarece informatia este prezenta direct in

motorul simulatorului. In situatiile reale de trafic acest lucru nu ar fi posibil decat daca

semafoarele sunt echipate cu dispozitive de comunicare wireless si ar schimba informatii

cu automobilele din jurul intersectiei. Aplicatia prezentata in aceasta lucrare contine

numai semafoare dotate cu astfel de dispozitive de comunicare.

Figura 13: Vedere din perspectiva conducatorilor auto

30

In zona din dreapta sus sunt afisate informatii starea curenta a simularii: timpul

real de la inceputul simularii; timpul simularii curente de la inceputul ei; numarul de pasi

discreti simulati; numarul de evenimente care asteapta sa fie simulate; numarul de

vehicule prezente pe harta.

Zona din dreapta jos este destinata consumului de carburant si a emisiilor

poluante. Daca modulul destinat emisiilor este activat, se vor afisa cantitatile de CO2,

CO, HC si NOx. Consumul de carburant este masurat in litrii/100km.

Utilizatorul are control deplin asupra simularii. El poate alege sa execute doar un

interval de timp apasand butonul „Step” sau poate rula in mod continuu toate

evenimentele apasand butonul „Run”. Dupa ce butonul „Run” a fost apasat, utilizatorul

poate suspenda simularea cu ajutorul lui „Pause”.

Butonul „Show route” va desena in zona destinata hartii orasului, ruta actuala a

unui automobil selectat. Butonul este util in special in situatiile in care traseul pana la

destinatie al unui automobil este generat in mod dinamic.

Informatii aditionale despre un automobil se pot afisa in zona statisticilor apasand

butonul „Trace Car”. Se va afisa viteza curenta a vehiculului, viteza sugerata, iar daca

automobilul se afla in raza de actiune a unui semafor, lungimea cozii formate pe banda de

mers, si durata in care semaforul sta pe culoarea rosie.

Utilizatorul poate selecta un automobil prin numarul lui de identificare. Deasupra

butonului „currentCar ID” se gaseste un camp in care poate fi scris ID-ul vehiculului, iar

prin apasarea butonului se selecteaza automobilul. Vor fi afisate aceleasi informatii ca si

in cazul selectarii automobilului printr-un click.

Desi interfata grafica este foarte utila in observarea situtatiilor, care in alte

conditii ar fi dificil de identificat, ea este o mare consumatoare de resurse. De aceea a fost

introdus butonul „GUI OFF/ON”. Daca utilizatorul vrea sa lase simularea sa avanseze

31

mai rapid in timp, prin apasarea butonului se intrerupe desenarea automobilelor pe harta,

urmand sa fie reluata la o apasare ulterioara a butonului.

In unele cazuri, ne intereseaza doar modulul de mobilitate (miscarea vehiculelor).

In aceste situatii simularea modulului de comunicare introduce calcule inutile si de aceea

butonul „COM OFF/ON” dezactiveaza sau activeaza comunicarea dintre vehicule.

32

Arhitectura sistemului

Aplicatia este o extensie a platformei VNSim si este dezvoltata in limbajul Java.

Limbajul de programare a fost ales datorita portabilitatii acestuia pe sistemele de operare

existente: „write once, run everywhere”.

Arhitectura sistemului este bazata pe o structura modulara, acest lucru

simplificand implementarea si testarea aplicatiei.

Figura 14: Entitatile sistemului (automobile, semafoare, server central) si modul

in care acestea interactioneaza

33

Dotate cu dispozitive de comunicare, automobilele vor transmite catre serverul

centralizat prin intermediul semafoarelor informatii care depind de starea actuala a

drumurilor pe care acestea circula.

Semafoarele monitorizeaza strazile principale si au un rol intermediar in

trimiterea si receptia datelor de la automobile la server si invers.

Serverul pastreaza pentru fiecare ora mediile cu gradule de aglomerare ale fiecarei

strazi monitorizate si o lista cu toate strazile care depasesc aceasta medie cu +/- θ , unde

θ reprezinta un prag.

Automobilele primesc de la server lista cu strazile care depasesc media de

aglomerare si isi reactualizeaza informatia, apoi isi gasesc drumul optim pana la

destinatie.

Gradul de aglomerare

Gradul de aglomerare al strazilor este foarte important pentru gasirea drumului

minim de la o sursa la destinatie. Un obiectiv este crearea in timp real a hartii orasului,

harta ce contine starea de aglomerarea a soselelor. Cunoscand gradul de aglomerare al

drumurilor, un automobil poate genera un traseu rutier optim.

Vom crea astfel un graf orientat, unde muchiile reprezinta segmente de strazi,

nodurile vor fi intersectiile iar costul arcelor va depinde de gradul de aglomerare al

segmentelor de drum monitorizate.

Deoarece conducatorii auto prefera sa circule pe strazile mari, vor fi monitorizate

doar strazile principale. Semafoarele inteligente care controleaza traficul in intersectii vor

comunica cu vehiculele care strabat strazile monitorizate pentru a stabili gradul de

34

aglomerare al fiecarei artere. Un server central are rolul de a pastra in memorie datele

venite in timp real de la semafoare.

Fiecarei strazi principale ii va fi asociata o valoare de tip (double) intre 0 si 255,

iar aceasta valoare va reprezenta gradul de aglomerare. Valorile sunt direct proportionale

cu acest grad de aglomerare, 0 reprezentand o strada complet goala pe care nu circula

vehicule, iar 255 reprezentand o strada impracticabila. Formula de calcul este

urmatoarea:

⎪⎩

⎪⎨⎧

=Γ≤−∗

>

MaxmMax

m

Maxm

vvvv

vv

),1(255

,0

unde:

Γ este gradul de aglomerare;

mv este viteza medie a automobilului pe un segment de drum;

Maxv este viteza maxima admisa pe acel segment de drum

Viteza medie este viteza medie pe acel segment pana la oprirea la semafor

corelata cu un factor care depinde de numarul de perioade la care automobilul asteapta la

culoarea rosie a semaforului. Acest factor este direct proportional cu frecventa de trecere

a vehiculelor prin intersectie, masurata in numar_de_automobile/s.

)*1(* min

FF

nn

tdv

RMax

Rm −=

unde:

d este distanta pana la oprirea la semafor sau distanta intregului segment daca

automobilul nu a stat la semafor (a „prins” culoarea verde);

t este timpul in care a fost parcursa distanta d;

Rn este numarul de cicluri de rosu la care vehiculul a asteptat;

RMaxn este numarul maxim de cicluri de rosu la care poate astepta un automobil pe

35

segmentul de drum respectiv;

F este frecventa de trecere a automobilelor prin intersectie la momentul respectiv;

minF este frecventa mimina de trecere a automobilelor prin intersectie inregistrata

pentru fiecare ora.

Se observa ca viteza medie are valoarea maxima tdvm = , daca semaforul este pe

culoarea verde cand se doreste traversarea intersectiei ( 0=Rn ). Viteza medie are

valoarea minima 0=mv atunci cand numarul de cicluri de rosu este maxim si frecventa

de trecerere a vehiculelor este minima (egalitatile maxRR nn = si minFF = sunt indeplinite

simultan). Viteza medie va creste daca numarul de de cicluri de rosu la care automobilul

asteapta scade sau daca frecventa de trecere a automobilelor prin intersectie creste.

Semafoare inteligente

Pentru aplicatia in cauza am considerat ca semafoarele dispun de capabilitati de

comunicare si de putere de calcul. Astfel ele pot comunica intre ele si cu automobilele din

jur. In mod uzual, intr-un oras aglomerat, cele mai multe semafoare sunt interconectate si

corelate iar instalarea unor echipamente de comunicare si de procesare nu este dificila.

Scopul acestor semafoare este de a calcula gradul de aglomerare pe segmentul de

drum monitorizat. La fiecare ciclu se calculeaza gradul de aglomerare corespunzator

fiecarui automobil care a trecut prin intersectie, iar media acestor grade este trimisa unui

server centralizat. Semafoarele vor transmite inapoi la automobile strazile care sunt

aglomerate peste sau sunt mai libere decat media normala pentru ora respectiva.

Pentru a face fata unui volum mare de trafic, pe procesoroarele semafoarelor nu se

vor executa algoritmi complecsi. Fiind intermediare intre server si vehicule, semafoarele

au rol in distributia strazilor aglomerate sau libere catre sistemul de navigatie al

vehiculelor si totodata ofera un nivel de securitate.

36

Server centralizat

Harta orasului va fi pastrata pe un server centralizat. Acesta va tine in memorie o

medie cu gradele de aglomerare ale tuturor strazilor precum si starea actuala a acestora.

Fiind conectat cu semafoarele din jur, serverul va primi de la acestea gradele de

aglomerare Γ pentru fiecare strada monitorizata. Cu aceste grade, din ora in ora se

calculeaza media mΓ fiecarei strazi. (Nota: termenul „strada” folosit pe parcursul acestui

capitol se refera la un segment de drum monitorizat de un semafor inteligent).

Atunci cand sistemul este instalat, in prima saptamana, serverul nu va face altceva

decat sa achizitioneze date. Dupa prima saptamana, pentru fiecare ora, serverul va

dispune de doua imagini ale orasului: una este media de saptamana trecuta, cealalta este

starea actuala a drumurilor. Din diferenta lor, obtinem cu cat s-au aglomerat sau eliberat

strazile in momentul respectiv fata de saptamana trecuta. Vom nota aceasta diferenta cu

δ . Se observa ca δ+Γ=Γ m .

Pentru a economisi banda de comunicare si pentru a face fata unui volum mare de

trafic, inapoi la semafoare vor fi raportate numai strazile al caror δ depaseste un prag θ .

Conditia este ca θδ > . Daca pentru o strada se indeplineste aceasta conditie, id-ul ei

impreuna cu gradul actual de aglomerare vor fi difuzate catre toate semafoarele.

Modulele aplicatiei

Aplicatia este impartita in 3 module, care pot fi implementate/imbunatatie

individual:

37

Achizitia datelor

Achizitia datelor se face dupa incheierea fiecarei perioade in care semafoarele se

afla pe culoarea verde. Datele circula de la automobile la semafoare si de la semafoare la

server. Dupa ce au trecut toate automobilele pe culoarea verde, se elimina erorile grosiere

si se calculeaza o medie a gradelor de aglomereare. Aceasta medie, impreuna cu ID-ul

strazii monitorizate este transmisa serverului.

Actualizarea informatiilor

Este procedeul prin care informatia existenta pe server ajunge la sistemul de

navigatie al automobilelor. Pentru a recrea aceasta imagine avem nevoie de gradele medii

de aglomerare mΓ si de modificarile reprezentate de δ . Din suma lor obtinem gradele de

aglomerare actuale ale strazilor δ+Γ=Γ m .

Daca moficarile fata de medie sunt transmise prin reteaua VANET catre vehicule,

de fiecare data cand acestea trec prin dreptul unui semafor inteligent, pentru gradul mediu

de aglomerare al strazilor vom folosi o alta abordare. Saptamanal serverul centralizat va

publica strazile orasului imreuna cu mediile lor de aglomerare pe saptamana anterioara.

Tot saptamanal, sistemul de navigatie al automobilelor va fi programat sa actualizeze

aceste medii in mod automat, dar prin intermediul unei conexiuni 3G.

Gasirea drumului optim

Pentru a beneficia de modificarea dinamica a traseelor rutiere, intr-un mod optim,

sistemul de navigatie al automobilelor trebuie sa cunoasca starea strazilor din interiorul

orasului.

Initial se genereaza un traseu rutier pe baza mediilor obtinute in saptamana

anterioara. Deoarece sunt monitorizate doar strazile principale, acest traseu va avea 3

subtrasee:

a. de la pozitia initiala pana la un drum principal

b. de la un drum principal pana la pozitia finala

c. un subtraseu care uneste drumurile principale de la a si b.

38

Pentru ca intreg traseul rutier sa fie optim, este necesar ca subtraseul care uneste

drumurile principale se fie minim. De aceea se vor genera toate subtraseele care unesc

drumurile principale din jurul sursei cu drumurile principale din jurul destinatiei. Dintre

acestea, drumul minim va fi selectat. Vom calcula apoi drumul cel mai scurt de la sursa la

drumul minim, si de la drumul minim la destinatie. Cele doua drumuri reprezinta

subtraseele a respectiv b.

In dreptul fiecarui semafor, dupa ce a primit lista cu strazile care s-au modificat

fata de medie, sistemul de navigatie poate gasi rute alternative pentru a ajunge la

destinatie. Daca un drum mai bun a fost gasit, el va fi considerat optim si afisat

conducatorului auto. Ca si in cazul drumului initial vor fi analizate toate drumurile din

pozitia curenta catre drumurile principale din jurul destinatiei, iar apoi drumul minim va

fi ales. De la acest drum pana la destinatie se va cauta drumul cel mai scurt.

In cazul in care apar congestii in trafic, de obicei sunt afectate mai multe

intersectii. Semafoarele care monitorizeaza aceste intersectii vor raporta serverului o

crestere a gradului de aglomerare. Aceasta crestere fiind peste media normala pentru ora

respectiva, va determina o difuzare de la serverul centralizat catre toate semafoarele

orasului. Din acest moment, toate automobilele vor afla despre congestia aparuta cand se

vor afla in raza unui semafor. Sistemul de navigatie al vehiculelor va gasi un traseu nou,

care sa ocoleasca zona congestionata.

Detalii de design

Automobilele sunt reprezentate ca obiecte de tipul CarInstance. Ele vor circula pe

strazile din scenariu pe o rute initial predefinite. Pentru fiecare segment de drum din ruta,

vehiculele vor calcula o viteza medie avgSpeed ca fiind raportul dintre distanta parcursa

pe acel segment distanceOnSegment si timpul in care acesta distanta a fost parcursa

timeOnSegment. Distanta parcursa pe segmentul de drum poate fi intreaga lungime a

segmentului, daca automobilul nu a asteptat la semafor (daca „a prins” culoarea verde),

sau poate fi doar distanta pana la oprirea automobilului la semafor pe culoarea rosie.

39

Exista o variabila avgSpeedStatus care indica starea variabilei avgSpeed. La trecerea pe

un nou segment, viteza medie va trebui recalculata pentru acel segment iar

avgSpeedStatus ia valoarea SPEED_RESET. Dupa ce automobilul a calculat viteza medie

(in cazul in care a oprit la semafor, sau doar ce a trecut pe un segment nou de drum),

variabila avgSpeedStatus ia valoarea SPEED_COMPUTED.

Semafoarele din intersectii ofera informatii utile automobilelor care se apropie de

intersectie. La fiecare secunda acestea vor difuza mesaje de tip PROT_TL_FEEDBACK.

Aceste mesaje contin date cu numarul de vehicule care asteapta la semafor, cu durata

unui ciclu complet al semaforului, si cu intervalul in care acesta este pe culoarea verde.

Cu aceste date un automobil poate calcula numarul de perioade de rosu la care va astepta la semafor. Formula este: nCycles = dischargeTime / greenTime; unde dischargeTime = (int) (queueSize * CARSPERKM / QUEUEDISCHARGEFLOW);

O data calculate viteza medie si numarul de perioade la care trebuie sa astepte

automobilul, aceata va trebui transmisa datele echipamentului de comunicare, in cazul

nostru un obiect de tip CityCarRunningDSRC. Sufixul DSRC vine de la Dedicated Short

Range Communications. Viteza medie este luata din CarInstance prin intermediul

metodei getAvgSpeed(), iar numarul de perioade de rosu prin intermediul metodei

getTLCycles(), si transmise mai departe in mediul wireless, prin metoda

broadcastRoadPacket() a echipamentului de comunicare CityCarRunningDSRC.

Mesajele transmise catre semafor au urmatorul format: "RM " + car.ID + " "+

avgSpeed + " " + nTLCycles + " " + segmentIndex. Initialele RM vin de la Road

Metrics, iar segmentIndex este indicele segmentului pentru care au fost calculate viteza

medie si numarul de cicluri. Tipul mesajelor transmise este ROAD_METRICS_PROT.

Informatiile asociate segmentelor de drum ajung la echipamentele de comunicare

ale semafoarelor, echipamente simulate prin obiecte IntersectionNode. Metoda

onReceive() a acestei clase va receptiona mesajele de tip ROAD_METRICS_PROT, si va

apela metoda parseMetrics() pentru procesarea acestora.

40

Functia parseMetrics() calculeaza gradul de aglomerare. Daca viteza medie e mai

mare decat viteza maxima stabilita prin kMaxAllowedSpeed, atunci gradul de

aglomerare va fi 0, altfel ea va fi: congestion = 255 * (1 - avgSpeed / kMaxAllowedSpeed);

Gradul de aglomerare va fi stocat intr-o structura de tip HashMap, avand drept

cheie ID-ul automobilului care a trimis pachetul de tip Road Metrics. Daca un vehicul

incerca sa trimita mai mult de un mesaj, datele acestuia vor fi ignorate.

Fiecare segment de drum ce apartine intersectiei are asociat cate un tabel hash.

Ori de cate ori semaforul devine rosu pentru un segment, toate gradele de aglomerare

memorate vor fi mediate (metoda mediateCost()), iar media lor va fi trimisa catre serverul

central.

La crearea obiectelor IntersectionNode, acestea se inregistreaza la server si

primesc un indice al intersectiei numit crossIndex. Pentru a trimite gradul de aglomerare

catre server se apeleaza metoda setCongestion() a acestuia. Functia primeste ca

parametrii indicele intersectiei crossIndex, indicele segmentului, timpul la care se

efectueaza trimiterea crtTime si gradul de aglomerare newCost.

Serverul este modelat ca un obiect ce apartine simulatorului si interactioneaza cu

restul aplicatiei prin apelarea de metode publice. In realitate, serverul va rula pe o masina

separata, insa va putea comunica cu celelalte entitati prin RMI (Remote Method

Invocation) sau prin alte mecanisme.

De fiecare data cand un semafor se inregistreaza la server, o structura de tipul

CrossRoadCongestion este adaugata in baza de date. Aceasta structura va contine, pentru

trimiterea raspunsurilor, obiectul IntersectionNode asociat semaforului. Pe langa acest

obiect, CrossRoadCongestion contine, pentru fiecare segment al intersectiei, o lista de

grade de aglomerare (realTimeCongestions) primite de la semafor si un obiect de tip

41

WeekCongestion numit lastWeek, care stocheaza mediile acumulate pentru saptamana

anterioara.

Obiectul de tip WeekCongestion este un tabel ce are ca linii zilele saptamanii (de

Luni pana Duminica), iar pe coloane se afla orele din zi (de la 0 la 23). Celulele tabelului

contin gradele de aglomerare medii inregistrate pe fiecare ora din zi. Obiectul contine

metode pentru accesarea si actualizarea informatiilor, precum si o metoda de clonare a

tabelului, utilizata de server pentru publicarea mediilor. Metoda toString() a clasei

WeekCongestion este utila pentru salvarea pe disk a congestiilor.

Funnctiile loadCongestions() respectiv saveCongestions() din clasa Server,

incarca sau salveaza mediile cu gradele de aglomerare pe saptamana anterioara de pe / pe

disk. Fisierele sunt in format text si au extensia .cng.txt. Functiile intorc rezultate

booleene, false pentru o incarcare sau o salvare a datelor nereusita.

Din server este apelata metoda step() care primeste ca argument timpul simularii

si defineste comportarea serverului. Mediile cu gradele de aglomerare se vor salva pe

disk din saptamana in saptamana. Tot la acelasi interval este apelata metoda

publishLastWeekCongestions(), care va face o copie a mediilor si le va oferi spre utilizare

automobilelor. Mediile vor fi astfel atribuite unei variabile publice globale numita

lastWeekCongestions.

La intervale mai mici, din ora in ora, sunt actualizate mediile cu gradele de

aglomerare. Astfel dupa ce a trecut o ora, pentru ora anterioara este apelata metoda

updateLastWeekCongestions() care va media toate datele primite in decursul orei care s-a

incheiat, iar noua medie o va inlocui pe cea veche din variabila lastWeek.

Serverul detine o lista cu segmentele de drum care sunt mai congestionate sau mai

libere decat media lor pe saptamana trecuta. Aceasta lista se numeste updatedCongestions

si contine obiecte de tipul RoadSegmentCongestions. In aceasta structura se afla ID-ul

42

unui segment dat prin indicele intersectiei crossRoadIndex si indicele segmentului

segmentIndex si gradul de aglomerare stocat in variabila de tip Double, congestion.

Cand un semafor actualizeaza gradul de aglomerare al unui segment, congestia

strazii e adaugata in structura realTimeCongestions. Daca mediile pe saptamana

anterioara au fost calculate sau incarcate de pe disk, atunci gradul de aglomerare actual

va fi comparat cu media pentru ora si ziua respectiva. In cazul in care diferenta intre cele

doua depaseste pragul definit in variabila kCongestionThresh, atunci segmentul de

dreapta va fi adaugat listei updatedCongestions. Pentru cazul in care diferenta intre

gradul de aglomerare actual si media este mai mica decat pragul definit, atunci segmentul

de dreapta va fi scos, daca e cazul, din lista updatedCongestions.

De fiecare data cand se modifica lista updatedCongestions, se va apela metoda

broadcastUpdatedCongestions(), care va difuza catre semafoare (IntersectionNode)

datele actualizate. broadcastUpdatedCongestions() va clona lista updatedCongestions iar

clona va fi trimisa ca parametru metodei updateCongestions() a semafoarelor (clasa

IntersectionNode).

Semafoarele in acest caz vor avea rol in distributia informatiilor actualizate. Ele

vor serializa informatia primita de la server, si la fiecare interval definit in variabila

kRouteMetricsInterval vor trimite in mediu un pachet cu strazile ale caror grade de

aglomerare sunt diferite fata de medie. Mesajul trimis este prefixat de „RMR”,

RoadMetricsReply. Pentru fiecare strada, in mesaj este scris indexul intersectiei din care

provine, indexul segmentului de drum, si gradul de aglomerare (double). Datele

segmentelor de drum sunt separate de caracterul „C”.

Informatiile trimise de semafoare vor fi receptionate de echipamentele de

comunicare ale automobilelor (CityCarRunningDSRC). Clasa contine metoda

onReceive() care va prelua mesajul si il va analiza cu ajutorul functiei changeRoute().

changeRoute() va iesi fara alte procesari daca mesajul nu este RoadMetricsReply, daca

automobilul se afla pe ultimul segment al traseului sau, sau daca mediile pe saptamana

43

anterioara nu au fost publicate. Obiectele de tip CityCarRunningDSRC detin un membru

numit lastMetrics, in care se retine ultimul mesaj analizat de vehicul. Daca mesajul nou

primit este identic cu ultimul mesaj analizat, nu mai este necesar sa modificam traseul

automobilului.

Lista de segmente impreuna cu gradele lor de congestie este refacuta si trimisa ca

parametru algoritmului dijkstra. Algoritmul apartine de clasa CityRouteComputingUtils

si se ocupa cu gasirea drumului minim pana la destinatie. Algoritmul formeaza un graf in

care nodurile sunt intersectiile, iar arcele sunt segmentele de drum.

Costul unui segment de drum se calculeaza in felul urmator: d*(1+f*Γ ). Unde d

este distanta segmentului de drum, f este o constanta (definita in

CityRouteComputingUtils ca o variabila double numita kCongestionRatio). Γ reprezinta

gradul de aglomerare, actual daca gradul de aglomerare actual difera de medie, segmentul

gasindu-se in lista updatedCongestions, sau gradul de aglomerare mediu pe saptamana

anterioara, daca congestia nu difera prea mult de medie. Pentru strazile nemonitorizate,

costul va fi distanta segmentului de drum.

44

Scenarii de test

Toate testele au fost realizate pe un computer cu procesor Intel Dual Core 2Ghz,

cu memoria de 2GB utilizand sistemul de operare Windows XP.

Pentru teste am ales doua scenarii, un scenariu simplu folosit pentru

implementarea aplicatiei (Figura 15), iar al doilea a fost folosit pentru evaluarea

performantelor (Figura 16).

Figura 15: Scenariu de test 1

In scenariul din figura de mai sus, exista doua strazi, una numita „Route”, cealalta

numita „Alternative”. Cele doua drumuri au cate 3 benzi pe sens. Automobilele vor

circula de la Sud catre Nord, numarul lor fiind de 400 vehicule/ora/banda.

45

Initial, (in prima saptamana), toate automobilele vor circula pe drumul cel mai

scurt, adica vor alege segmentul „Route”. In decursul primei saptamani semafoarele vor

trimite date despre gradul de congestie pe cele doua strazi. Dupa prima saptamana,

automobilele au acces la gradele de aglomerare medii ale strazilor si in consceinta vor

tine cont de ele alegand drumul cel mai putin congestionat, in cazul nostru segmentul

„Altenrative”. Pe masura ce se aglomereaza si drumul „Alternative” si avand la dispozitie

congestia actuala a strazilor (din comunicatia cu semafoarele), vehiculele vor alege una

din cele doua rute, in functie de costul strazilor la momentul respectiv.

Figura 16: Scenariu de test 2

Scenariul de test din Figura 16 contine in centru doua strazi mari (cu cate 3 benzi

pe sens) care formeaza o cruce. Automobilele apar pe harta pe strazile principale si se

indreapta catre celelalte extremitati (Nord, Sud, Est, Vest). Celelalte strazi care formeaza

46

grid-ul, au cate doua benzi pe sens si vor fi folosite de vehicule in cazul in care drumul

cel mai scurt catre destinatie este congestionat.

Pe acest scenariu au fost facute 18 simulari. In doua grupuri de cate 9 simulari am

modificat tipul semafoarelor: adaptive sau non-adaptive. Semafoarele non-adaptive au un

ciclu de succedare a fazelor constant in timp, pe cand semafoarele de tip adaptive se

ajusteaza in functie de numarul de automobile de pe fiecare segment al intersectiei. Astfel

daca o strada pe care circula un flux mare de vehicule se interesecteaza cu o strada pe

care circula un numar redus de vehicule, semaforul adaptive din intersectie va acorda

verde pentru un timp mai mic pe segmentul necongestionat, pe strada aglomerata verdele

„durand” mai mult.

Fiecare grup de 9 simulari se imparte in 3 grupuri de cate 3 simulari. Rata de

aparitie a automobilelor pentru fiecare banda a strazilor a fost variata de trei ori: 350, 425

si 500 vehicule/ora/banda.

In final, fiecare din cele 3 grupuri contine cate 3 simulari ce analizeaza traficul pe

o perioada de o zi (timpul serverului) sau 72 minute (timpul simulari). Prima simulare

este folosita pentru achizitia datelor de congestie iar automobilele folosesc rutarea

clasica, alegand drumul cel mai scurt pana la destinatie. In a doua simulare, s-a folosit

rutarea dinamica, automobilele alegand drumul optim, costul fiecarui segment fiind

proportional cu distanta segmentului si cu gradul de aglomerare al acestuia. In a treia

simulare s-a folosit tot rutarea dinamica, insa mediile de aglomerare au fost actualizate cu

cele din saptamana doi.

Rezultatele unei simulari contin numarul de automobile care au ajuns la

destinatie, distanta medie a unui traseu, timpul mediu de parcurgere a unui traseu,

consumul de carburant si consumul de carburant mediu pentru toate vehiculele. Am

calculat si beneficiul adus de rutarea dinamica, fata de rutarea clasica. Datele obtinute din

simulari sunt luate din 5 in 5 minute (timpul simularii) incepand cu minutul 5 si

terminand cu minutul 70.

47

Rezultate

Semafoare adaptive, 350 vehicule/ora/banda:

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance ShortestPath 0 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 Trip Time ShortestPath 0 232 227 223 223 226 231 230 241 248 248 253 258 258 265 Time Benefit ShortestPath 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Fuel Consumption ShortestPath 0 816 754 753 752 753 754 752 754 759 759 759 760 761 763 Avg Fuel Consumption ShortestPath 0 24.7 22.9 22.8 22.8 22.8 22.8 22.8 22.8 23 23 23 23 23.1 23.1 Total distance 0 79.2 716 1294 1792 2369 2953 3468 4052 4640 5164 5729 6283 6880 7451 Nb of cars 0 24 217 392 543 718 895 1051 1228 1406 1565 1736 1904 2085 2258

Tabelul 1: Timp: 70 min; semafoare: adaptive; flux de vehicule: 350 vehicule/ora/banda; rutare:

drumul cel mai scurt

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance DynamicRoute1 0 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 Trip Time DynamicRoute1 0 221 264 250 242 238 234 233 233 230 229 228 227 226 225 Time Benefit DynamicRoute1 0 4.74 -16 -12 -8.5 -5.3 -1.3 -1.3 3.32 7.26 7.66 9.88 12 12.4 15.1 Fuel Consumption DynamicRoute1 0 778 751 744 746 750 753 754 754 753 752 749 750 750 750 Avg Fuel Consumption DynamicRoute1 0 23.6 22.8 22.6 22.6 22.7 22.8 22.8 22.8 22.8 22.8 22.7 22.7 22.7 22.7 Total distance 0 36.3 689 1260 1871 2429 3056 3574 4221 4746 5369 5898 6538 7066 7693 Nb of cars 0 11 209 382 567 736 926 1083 1279 1438 1627 1787 1981 2141 2331

Tabelul 2: Timp: 70 min; semafoare: adaptive; flux de vehicule: 350 vehicule/ora/banda; rutare:

dinamica (saptamana 1)

48

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance DynamicRoute2 0 3.29 3.3 3.3 3.31 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 Trip Time DynamicRoute2 0 227 251 237 234 231 226 226 226 225 225 225 224 223 223 Time Benefit DynamicRoute2 0 2.16 -11 -6.3 -4.9 -2.2 2.16 1.74 6.22 9.27 9.27 11.1 13.2 13.6 15.8 Fuel Consumption DynamicRoute2 0 854 766 760 757 758 755 754 755 755 755 756 754 754 756 Avg Fuel Consumption DynamicRoute2 0 25.9 23.2 23 22.9 22.9 22.9 22.8 22.9 22.9 22.9 22.9 22.8 22.9 22.9 Total distance 0 62.6 676 1311 1888 2439 3066 3620 4188 4772 5356 5917 6494 7085 7672 Nb of cars 0 19 205 397 571 738 928 1096 1268 1445 1622 1792 1967 2146 2324

Tabelul 3: Timp: 70 min; semafoare: adaptive; flux de vehicule:

350 vehicule/ora/banda; rutare: dinamica (saptamana 2)

2220

2240

2260

2280

2300

2320

2340

1

Routing Type

Num

ber o

f Car

s

Shortest PathDynamic Route 1Dynamic Route 2

Numarul de vehicule care au ajuns la destinatie (minutul 70 al simularii)

Se observa o crestere a numarului de vehicule pentru rutarea dinamica de la 2231

in cazul rutari clasice la 2331 respectiv 2324 automobile. In cazul unui flux mic de

automobile 350 vehicule/ora/banda, aceasta crestere nu este mare insa ea exista.

Distanta medie, pentru toate rutarile se mentine constanta in jurul valorii 3.3km.

La fel ca distanta medie, consumul de carburant ramane relativ constant, situandu-se in

49

jurul valorii de 0.75 litrii pentru un traseu, insa exista mici variatii. Dupa minutul 40 al

simularii observam o scadere a consumului mediu pentru toate automobilele.

20

21

22

23

24

25

26

27

5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation time (min)

Avg

Fue

l Con

sum

ptio

n (l/

100k

m) Avg Fuel

Consumption (Shortest path)

Avg FuelConsumption(Dynamic Route1)Avg FuelConsumption(Dynamic Route2)

Consumul mediu de carburant

Timpul necesar parcurgerii unui traseu pana la destinatie a scazut, conform

asteptarilor, insa pana la minutul 30 al simularii, acesta este mai mare decat in cazul

rutarii pe drumul cel mai scurt. Explicatia este ca la inceputul fiecarei simulari, toate

strazile sunt goale si primele masini vor ajunge mult mai repede la destinatie. Acest lucru

nu se regaseste in cazul real, dar il regasim la inceputul fiecarei simulari.

Beneficiul adus de rutarea dinamica ajunge pana la valoarea de 22.9%, rutarea in

saptamana 2 de simulare fiind cu putin mai eficienta decat cea din saptamana precedenta.

50

0

50

100

150

200

250

300

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation Time (min)

Trip

Tim

e (s

) Trip Time (Shortest path)Trip Time (DynamicRoute 1)Trip Time (DynamicRoute 2)

Timpul necesar parcurgerii unui traseu

-20

-15

-10

-5

0

5

10

15

20

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation Time (min)

Tim

e B

enef

it (%

) Time Benefit (Shortestpath)Time Benefit (DynamicRoute 1)Time Benefit (CityDynamic Route 2)

Beneficiul adus de rutarea dinamica in comparatie cu rutarea clasica

51

Semafoare adaptive, 425 vehicule/ora/banda:

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance ShortestPath 0 3.29 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 Trip Time ShortestPath 0 238 242 239 235 237 244 254 260 267 276 290 312 320 327 Time Benefit ShortestPath 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Fuel Consumption ShortestPath 0 801 730 742 742 743 746 750 753 752 754 757 763 765 767

Avg Fuel Consumption ShortestPath 0 24.3 22.1 22.5 22.5 22.5 22.6 22.7 22.8 22.8 22.8 22.9 23.1 23.2 23.2 Total distance 79.1 838 1465 2039 2603 3191 3838 4445 5098 5748 6416 7102 7746 8461 Nb of cars 24 254 444 618 789 967 1163 1347 1545 1742 1944 2152 2347 2564

Tabelul 4: Timp: 70 min; semafoare: adaptive; flux de vehicule: 425 vehicule/ora/banda; rutare:

drumul cel mai scurt

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance DynamicRoute1 0 3.29 3.31 3.33 3.32 3.32 3.31 3.31 3.31 3.31 3.32 3.32 3.32 3.32 3.32 Trip Time DynamicRoute1 0 220 258 252 244 242 239 236 235 236 236 235 235 233 233 Time Benefit DynamicRoute1 0 7.56 -6.6 -5.4 -3.8 -2.1 2.05 7.09 9.62 11.6 14.5 19 24.7 27.2 28.7

Fuel Consumption DynamicRoute1 0 829 777 767 766 762 759 756 755 756 758 757 756 756 757

Avg Fuel Consumption DynamicRoute1 0 25.2 23.5 23 23.1 23 22.9 22.8 22.8 22.8 22.8 22.8 22.8 22.8 22.8 Total distance 0 65.8 807 1600 2293 2993 3666 4339 5061 5802 6455 7230 7907 8647 9290 Nb of cars 0 20 244 480 690 902 1106 1310 1528 1751 1946 2180 2383 2607 2799

Tabelul 5: Timp: 70 min; semafoare: adaptive; flux de vehicule: 425 vehicule/ora/banda; rutare:

dinamica (saptamana 1)

52

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance DynamicRoute2 0 3.3 3.3 3.31 3.34 3.34 3.33 3.33 3.32 3.32 3.32 3.32 3.32 3.32 3.31 Trip Time DynamicRoute2 0 228 260 255 255 253 247 242 239 236 233 233 232 232 231 Time Benefit DynamicRoute2 0 4.2 -7.4 -6.7 -8.5 -6.8 -1.2 4.72 8.08 11.6 15.6 19.7 25.6 27.5 29.4

Fuel Consumption DynamicRoute2 0 824 774 774 780 778 773 773 769 769 769 769 767 765 764

Avg Fuel Consumption DynamicRoute2 0 25 23.5 23.4 23.4 23.3 23.2 23.3 23.2 23.2 23.2 23.2 23.1 23.1 23 Total distance 0 75.8 742 1545 2209 2985 3722 4409 5155 5818 6535 7204 7937 8650 9326 Nb of cars 0 23 225 467 662 895 1118 1326 1552 1753 1970 2171 2393 2609 2814

Tabelul 6: Timp: 70 min; semafoare: adaptive; flux de vehicule: 425 vehicule/ora/banda; rutare:

dinamica (saptamana 2)

2400

2450

2500

2550

2600

2650

2700

2750

2800

2850

1

Routing Type

Num

ber

of C

ars

Shortest PathDynamic Route 1Dynamic Route 2

Numarul de vehicule care au ajuns la destinatie (minutul 70 al simularii)

In cazul in care fluxul de automobile creste, mai multe vehicule vor ajunge la

destinatie. Rutarea dinamica va mari numarul de automobile care ajung la destinatie cu

aproximativ 10% de la 2564 pana la 2814.

53

Pentru 2814 automobile distanta medie in cazul rutarii dinamice este cu 10 metrii

mai mare decat distanta cea mai scurta. Nu exista variatii mari, nici pentru consumul de

carburant, dar dupa minutul 55 al simularii, automobilele vor consuma mai putin

combustibil in cazul rutarii dinamice. Consumul mediu al tuturor vehiculelor este situat la

sfarsitul simularii in jurul valoarii 23 l/100km.

660

680

700

720

740

760

780

800

820

840

5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation Time (min)

Fuel

Con

sum

ptio

n (m

l)

Fuel Consumption (Shortestpath)Fuel Consumption (DynamicRoute 1)Fuel Consumption (DynamicRoute 1)

Consumul mediu al unui automobil pana la destinatie

Timpul mediu al unei calatorii inregistreaza valori mai mici (mai bune) decat

rutarea statica, de la minutul 30 al simularii. Semafoarele de tip adaptive fac ca la

inceputul simularii, drumul cel mai scurt sa fie si drumul optim, dar pe masura ce se

aglomereaza strazile, rutarea dinamica isi face simtita prezenta reducand in final timpul

calatoriilor de la 327 secunde la 231 secunde.

Beneficiile aduse de rutarea dinamica sunt mai mari decat in situatia in care

aveam o rata de aparitie de 350 vehicule/ora/banda ajungand pana la 29.4%. Diferentele

dintre cele 2 saptamani sunt mici, cu o usoara crestere a eficientei rutarii din saptamana 2

dupa minutul 45 al simularii.

54

0

50

100

150

200

250

300

350

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation Time (min)

Trip

Tim

e (s

) Trip Time (Shortestpath)Trip Time (DynamicRoute 1)Trip Time (DynamicRoute 2)

Timpul necesar parcurgerii unui traseu

-15

-10

-5

0

5

10

15

20

25

30

35

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation Time (min)

Tim

e B

enef

it (%

) Time Benefit (Shortestpath)Time Benefit (DynamicRoute 1)Time Benefit (DynamicRoute 2)

Beneficiul adus de rutarea dinamica in comparatie cu rutarea clasica

55

Semafoare adaptive, 500 vehicule/ora/banda:

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance ShortestPath 0 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.3 3.299 3.299 Trip Time ShortestPath 0 235 257 262 270 277 288 304 315 328 333 352 370 389 393 Time Benefit ShortestPath 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Fuel Consumption ShortestPath 0 852 756 749 745 741 741 745 745 747 748 755 758 764.4 765

Avg Fuel Consumption ShortestPath 0 25.9 22.9 22.7 22.6 22.4 22.5 22.6 22.6 22.6 22.7 22.9 23 23.17 23.19 Total distance 0 69.2 749 1392 2066 2732 3455 4124 4873 5596 6269 6889 7720 8450 9225 Nb of cars 0 21 227 422 626 828 1047 1250 1477 1696 1900 2088 2340 2561 2796

Tabelul 7: Timp: 70 min; semafoare: adaptive; flux de vehicule: 500 vehicule/ora/banda; rutare:

drumul cel mai scurt

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance DynamicRoute1 0 3.29 3.33 3.33 3.32 3.34 3.33 3.32 3.35 3.38 3.38 3.38 3.37 3.377 3.379 Trip Time DynamicRoute1 0 229 276 281 272 269 262 257 257 261 267 268 267 266 267 Time Benefit DynamicRoute1 0 2.55 -7.4 -7.3 -0.7 2.89 9.03 15.5 18.4 20.4 19.8 23.9 27.8 31.62 32.06

Fuel Consumption DynamicRoute1 0 794 777 776 767 770 763 760 766 772 772 771 769 770.2 770.2

Avg Fuel Consumption DynamicRoute1 0 24.1 23.4 23.3 23.1 23.1 22.9 22.9 22.9 22.9 22.8 22.8 22.8 22.81 22.79 Total distance 0 82.3 879 1769 2626 3430 4334 5103 5896 6694 7624 8497 9389 10176 11000 Nb of cars 0 25 264 531 790 1028 1302 1535 1762 1983 2255 2517 2784 3013 3255

Tabelul 8: Timp: 70 min; semafoare: adaptive; flux de vehicule: 500 vehicule/ora/banda; rutare:

dinamica (saptamana 1)

56

Simulation Time 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Trip Distance DynamicRoute2 0 3.29 3.3 3.3 3.3 3.3 3.3 3.3 3.31 3.31 3.31 3.31 3.31 3.308 3.308 Trip Time DynamicRoute2 0 231 269 262 255 254 254 254 254 251 250 249 248 247 245 Time Benefit DynamicRoute2 0 1.7 -4.7 0 5.56 8.3 11.8 16.4 19.4 23.5 24.9 29.3 33 36.5 37.66

Fuel Consumption DynamicRoute2 0 905 747 752 749 750 750 750 750 748 747 747 747 746.5 746.7

Avg Fuel Consumption DynamicRoute2 0 27.5 22.7 22.8 22.7 22.7 22.7 22.7 22.7 22.6 22.6 22.6 22.6 22.56 22.57 Total distance 0 49.4 887 1828 2596 3410 4231 5096 5957 6788 7617 8460 9242 10103 10912 Nb of cars 0 15 269 554 787 1032 1281 1543 1800 2052 2303 2556 2793 3054 3299

Tabelul 9: Timp: 70 min; semafoare: adaptive; flux de vehicule: 500 vehicule/ora/banda; rutare:

dinamica (saptamana 2)

2500

2600

2700

2800

2900

3000

3100

3200

3300

3400

1

Routing Type

Num

ber

of C

ars

Shortest PathDynamic Route 1Dynamic Route 2

Numarul de vehicule care au ajuns la destinatie (minutul 70 al simularii)

Pentru rata de 500 vehicole/ora/banda am obtinut rezultatele cele mai bune.

Numarul de automobile care au ajuns la destinatie a crescut cu 18% fata de cazul rutarii

clasice, ajungand la valoarea de 3299 fata de 2796 vehicule.

La fel ca in cazurile anterioare, distanta unui traseu nu s-a modificat prea mult, un

maxim inregistrandu-se pentru rutarea dinamica din prima saptamana diferenta fiind de

57

70m. Consumul de combustibil inregistreaza o scadere de la 0.765 l la 0.746 pentru

rutarea dinamica simulata in saptamana 2.

0

100

200

300

400

500

600

700

800

900

1000

5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation Time (min)

Fuel

Con

sum

ptio

n (m

l)

Fuel Consumption (Shortest path)Fuel Consumption(Dynamic Route 1)Fuel Consumption(Dynamic Route 1)

Consumul mediu al unui automobil pana la destinatie

Timpul necesar unui automobil pana la destinatie devine mai mic in cazul rutarii

dinamice de la minutul 15 al simularii pentru saptamana 2 si de la minutul 25 pentru

prima saptamana. Dupa minutul 25, timpul unei calatorii continua sa scada pana la

sfarsitul simularii, cand se inregistreaza un maxim: 245 secunde pentru rutarea din

saptamana 2 fata de 393 secunde pentru rutarea clasica.

Beneficiile rutarii dinamice ating un nou record, cu valori de pana la 37.6% mai

bune fata de rutarea pe drumul cel mai scurt. Exceptand zona dintre minutele 30 si 45,

rutarea dinamica efectuata in saptamana 2, este mai eficienta cu pana la 5.6% decat cea

efectuata in prima saptamana.

58

0

50

100

150

200

250

300

350

400

450

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation Time (min)

Trip

Tim

e (s

) Trip Time (Shortestpath)Trip Time (DynamicRoute 1)Trip Time (DynamicRoute 2)

Timpul necesar parcurgerii unui traseu

-10

-5

0

5

10

15

20

25

30

35

40

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70

Simulation Time (min)

Tim

e B

enef

it (%

) Time Benefit (Shortestpath)Time Benefit (DynamicRoute 1)Time Benefit (DynamicRoute 2)

Beneficiul adus de rutarea dinamica in comparatie cu rutarea clasica

59

Pentru cazul in care semafoarele sunt de tip non-adaptive, rezultatele pastreaza

acelasi trend, insa exista unele deosebiri. Distanta medie a unei calatorii ramane

constanta, consumul de combustibil pentru un automobil fiind cu 0.007 litirii mai mic in

cazul rutarii dinamice. Eficienta rutarii dinamice nu depaseste valoarea de 26.5% si este

inregistrata pentru un flux de 425 vehicule/ora/banda. Pentru scenariile in care fluxul de

automobile este de 500 respectiv 425 vehicule/ora/banda, rutarea dinamica realizata in

prima saptamana ofera rezultate mai bune decat cea din saptamana 2. Acest lucru se

explica prin faptul ca beneficiile ocolirii drumurilor congestionate sunt atenuate de timpii

mai mari de asteptare la semafor.

Din punct de vedere al performantei, timpul unei simulari este liniar cu numarul

de vehicule din scenariu, iar o secunda de simulare dureaza o secunda reala pentru 600

automobile.

60

Concluzii si dezvoltari ulterioare

Solutia prezentata ofera un model de optimizare a traficului in aglomeratiile

urbane prin gasirea in mod dinamic a drumului optim pana la destinatie. Am testat

aplicatia cu un scenariu care simuleaza miscarea automobilelor catre doua strazi

aglomerate. Simularile au fost facute variind fluxul de automobile. Fiecare simulare a

durat 70 minute, fiind testate rutarea pe drumul cel mai scurt si rutarea dinamica. In final

am analizat diferentele dintre scenariile care au semafoare adaptive si scenariile care au

semafoare clasice.

Aplicatia beneficiaza de ocuparea uniforma a strazilor monitorizate. Deoarece

automobilele vor selecta segmentele de drum cele mai putin aglomerate, strazile vor fi

ocupate in mod uniform iar in cazul unor aglomerari excesive, vor ajunge la capacitate

maxima dupa un timp mai lung.

Se observa o reducere a timpilor necesari deplasarilor cu pana la 37.6% fata de

rutarea pe drumul cel mai scurt. Timpul parcurgerii unui drum pana la destinatie este mai

mic, deoarece automobilele evita strazile congestionate.

Consumul de carburant pentru un automobil nu difera cu mult fata de rutarea

clasica, insa este mai mic cu pana la 0.019 litrii in cazul rutarii dinamice. Aparent

nesemnificativa, cantitatea de combustibil economisita capata alte proportii daca

raportam scenariul simulat la un oras mare sau la o metropola. Emisiile poluante se vor

reduce in consecinta, datorita scaderii numarului de accelerari si are efect benefic asupra

mediului inconjurator.

Reducerea frecventei accelerarilor si a franarilor va duce la cresterea fiabilitatii

automobilelor si in consecinta costuri de intretinere mai mici.

61

Aplicatia ofera un nivel de securitate crescut prin folosirea semafoarelor ca noduri

intermediare intre automobile si server. Serverul nu este accesat direct, iar datele eronate

ce pot fi transmise de catre vehicule vor fi filtrate la nivelul semafoarelor.

Dezvoltari ulterioare

Sistemul va putea fi imbunatatit actualizand mai rapid informatia despre starea

drumurilor. Folosind automobilele ca noduri de comunicare, o congestie de trafic poate fi

descoperita mai devreme. Un protocol de securitate este necesar, deoarece automobilele

nu pot fi considerate de incredere.

Pentru ca vehiculele prioritare (ambulante, pompieri, politie) sa ajunga cat mai

repede la destinatie, trebuie ca ele sa nu fie surprinse de ambuteajele ce pot aparea. In

acest sens, le putem acorda dreptul de a modifica temporar gradul de congestie al unui

traseu stabilit. Cu un grad de aglomerare mai mare, automobilele vor evita strazile pe care

urmeaza sa circule un vehicul prioritar.

62

Bibliografie

[1] Traffic Congestion, March 2008,

http://en.wikipedia.org/wiki/Traffic_congestion

[2] UK Government – „Transport Trends”, Section 3: Public Transport, 2007.

[3] LA Quake Displays Need for Mass Transit - The Tech,

http://www-tech.mit.edu/V114/N1/hove.01o.html

[4] Intelligent Transportation Systems - U.S. Department of Transportation.

http://www.its.dot.gov/index.htm

[5] Emerging Technologies – „VANET: The Vehicular Ad-Hoc Network” , 2007.

[6] Karen Zita Haigh, Jonathan Richard Shewchuk, Manuela Veloso –

“Route Planning and Learning from Execution”. AAAI Fall Symposium on Caring

Machines, Washington, D.C., November 2005.

[7] Bin Liu – „Using Knowledge to Isolate Search in Route Finding”. International

Joint Conference on Artificial Intelligence, pp.119-125, 1995.

[8] G. Eggenkamp, L.J.M. Rothkrantz – “Intelligent dynamic route planning”. KBS

& TRAIL Workshop, June 2001.

[9] Diaconescu St. Raluca – „Collaborating Route Planning in Vehicular Ad-hoc

Networks”, Diploma thesis, 2006.

63

[10] Liviu Iftode, Tamer Nadeem, Sasan Dashtinezhad, Chunyuan Liao – “TrafficView:

Traffic Data Dissemination using Car-to-Car Communication”, IEEE International

Conference on Mobile Data Managment, 2004.

[11] Diaconescu Raluca, Gorgorin Cristian, Gradinescu Victor – “Integrated Vehicular

Traffic Simulator”. Student’s Scientific Convention - Politechnica

University, May 2006.

[12] M.Dikaiakos, S.Iqbal, T.Nadeem, L.Iftode – “VITP: An Information Transfer

Protocol for Vehicular Computing”. In Proc. of the 2nd ACM International Workshop on

Vehicular Ad Hoc Networks (VANET), September 2005.