4%..

’73.!
o)
e

‘4“
mm”;
.
5| .fl .- .
3.5:... lit .
‘34- 1...!

3.;
..
2...:
..
1 a than.“
53.
a3

w‘.

i‘m I
”iii“, .

)J..I.lxs 2:...
«H r 2;. i123. ..
v.) iifiaa-flsr... "flag
. nfldnflkflh 5
5,4351er
. “$3.3:

1. .. 11V

1.“

.1
, I.«Lh'y.
1.512%...
.Ifif I“!
.f

3.1.3.
«.3! Ln¢nflwn
I. I a.

. N5
1.9193}. .1

S4 :43 r .
P. .51....rfi...‘
2;; tritiii
.uu ”d that“;
Ln%. .

ii
I

an

 

madam

I. .5

3 . .

. (31.1 .t. 2 . R

UID.I!£.\.5)1!| I)
A .5: !

up. 1.1T!

M:

z...

 

2 " LIBRARY
QM Michigan State
University

This is to certify that the
thesis entitled

INFRASTRUCTURE-LESS URBAN TRAFFIC MANAGEMENT
USING VEHICULAR AD HOC NETWORKS

presented by

HOWARD VANLUE HARDIMAN

has been accepted towards fulfillment
of the requirements for the

Master of degree in Electrical and Computer
Science Engineering

 

 

92/4” l. QM

 

Major Professor’s Signature
M 1‘: MW ) .2003

Date

 

MSU is an affirmative-action, equal-opportunity employer

_ _...u-._._._A-._.—.g..-.-.-.-.-o—-0-,L’7!!'.._.'9'-

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE a DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5/08 KlProj/Acc8Pres/ClRC/DaleDueindd

INFRASTRUCTURE-LESS URBAN TRAFFIC MANAGEMENT USING
VEHICULAR AD HOC NETWORKS

By

Howard Vanlue Hardiman

A THESIS
Submitted to
Michigan State University

in partial fulfillment of the requirements
for the degree of

MASTER OF SCIENCE
Electrical and Computer Engineering

2008

ABSTRACT

IN FRASTRUCTURE-LESS URBAN TRAFFIC MANAGEMENT USING
VEHICULAR AD HOC NETWORKS

By
Howard Vanlue Hardiman

This thesis develops an urban traffic management framework using distributed
vehicle-to-vehicle communication and computing. Most of the existing vehicle
navigation and route guidance systems rely on GPS-enabled location information,
coupled with FM radio or cellular facilitated centralized content services. However, this
mode of traffic management is expected to suffer from long term business scalability and
reliability issues, due to its reliance on centralized paid services. As a consequence, the
evolving technology of wireless vehicular ad hoc networks (VANET) is currently being
perceived as a plausible communication platform for this application. Guided by this
industry and research trend, this thesis proposes an infrastructure-less framework
designed specifically for the purpose of traffic congestion alleviation and avoidance. In
specific, the application layer algorithms have been developed, along with the underlying
wireless VANET schemes suited for distributing the application layer induced traffic
management information. The designed architectural components include mechanisms
for congestion detection, broadcast based VANET routing for efficient congestion
notification, vehicular transport oriented VANET routing used for connecting network
partitions in sparse vehicular scenarios, and a constrained vehicle navigation algorithm
for congestion mitigation. Extensive simulation studies have been performed, and the
results indicate that the system is able to successfully manage vehicular traffic, while

delicately handling the wireless broadcast medium.

Copyright by
Howard Vanlue Hardiman

2008

To My Family, Both On Earth And In Heaven,
For All Their

Love, Support, And Prayers

iv

Acknowledgements

I would like to thank my advisor, Dr. Subir Biswas, for his unwavering patience
throughout this project. Without your expertise and never-ending support, completing
this work would have been impossible. As for my committee members, Dr. Percy Pierre
and Dr. Jian Ren, thank you for being flexible in terms of organizing the defense aspect
of my requirements.

I would also like to thank the CSE department and HPCC staff for providing and up
keeping the HPCC. The HPCC definitely allowed the computationally intense vehicular
simulations performed for this thesis to be run in a much more efficient manner.

I would also like to thank Dr. Percy Pierre and Dr. Barbara O’kelly for all that
they have done, in terms of my existence here at Michigan State University. Without
their efforts within the realms of providing graduate education and assistance to
underrepresented students, I am unsure how this portion of my career would have gone.
Also, I would like to especially thank Dr. O’kelly for all her efforts and administrative
support.

As for my close friends who have stood by me, thanks for the support and
companionship throughout my work and life.

Lastly, I acknowledge and thank the EB Aggies who made the trip up to East
Lansing in the fall of 2005. Although things got rough and distance has come between

us, each person has indirectly contributed to the completion of this work.

TABLE OF CONTENTS

List of Tables ........................................................................................ ix
List of Figures ....................................................................................... x
Key to Symbols or Abbreviations ............................................................... xiii
Chapter 1: Introduction ....................................................................................................... 1
1.1 Travel Choices in Vehicular Environments ................................................ 2

1.1.1 Delay vs. Distance Examination ......................................................... 5

1.2 VANET Basics and Applications ............................................................. 1 1

1.2.1 Travel Improvement and Safety ........................................................ 12

1.2.2 Leisure Applications ......................................................................... 13

1.3 VAN ET Oriented Route Guidance System .............................................. 13

1.4 Current Route Guidance Systems ............................................................. 14
Chapter 2: Related Work .................................................................................................. 15
2.1 Onset of in-Vehicle Devices ..................................................................... 15

2.1.1 The Need for Position Information ................................................... 15

2.1.2 In Car Devices and Driver Interaction .............................................. 16

2.1.3 An Early Driver Information System ................................................ 17

2.2 VANET Networking Challenges and Solutions ....................................... 18

2.3 WiNDCC Contributing Protocols and Considerations ............................. 22

2.3.1 Application Layer Functionality ....................................................... 22

2.3.2 Network Layer Functionality ............................................................ 25

2.4 Agent-network Based Route Guidance System ........................................ 30
Chapter 3: WiNDCC Framework ..................................................................................... 32
3.1 Problem Discussion With Respect to VANET Oriented Solution ........... 32

3.1.1 Network Overhead ............................................................................ 33

3.1.2 Delay Message Propagation Needs ................................................... 33

3.2 WiNDCC Architectural Perspective ......................................................... 34

3.2.1 Functional Entities and Data Exchange ............................................ 35

3.2.2 WiNDCC Network Architecture ....................................................... 38

3.2.3 Architectural Summary ..................................................................... 40

3.3 WiNDCC Operational Assumption .......................................................... 40

3.4 Path Computation Function ...................................................................... 41

3.5 WiNDCC Packet Contents ........................................................................ 44

3.6 Delay Message Generation ....................................................................... 45

3.6.1 Message Generation Based on Initial Congestion Indicator ............. 47

3.6.2 Delay Message Generation during Times of Event .......................... 51

3.7 WiNDCC Message Forwarding Algorithms ............................................. 53

3.7.1 Relevant Areas for Message Forwarding .......................................... 53

3.7.2 Receive Module: Forwarding Decision ............................................ 58

vi

3.7.3 Fast Path Message Forwarding ......................................................... 62

3.7.4 Fast Path Message Forwarding with Partition Bridging ................... 65

3.7.5 Cache and Carry Message Forwarding ............................................ 66

Chapter 4: Experimental Setup ......................................................................................... 69
4.] Macro Vehicular Simulator ....................................................................... 69

4.1.1 Pre-installed Ns-2 Dependencies ...................................................... 70

4.1.2 Input Simulation Script ..................................................................... 71

4.1.3 Topology Interaction and Position Awareness ................................. 72

4.1.4 Vehicular Interaction ........................................................................ 73

4.2 WiNDCC Implementation ........................................................................ 74

4.3 External Components ................................................................................ 74

4.4 Commonalities between Experimental Scenarios ..................................... 75

4.4.1 Experimental Topology and Characteristics ..................................... 76

4.4.2 Wireless Networking ........................................................................ 79

Chapter 5: WiNDCC Performance for Handling Traffic Congestion .............................. 80
5.1 Simulation Setup ....................................................................................... 81

5.2 User On'ented Performance Metrics ......................................................... 82

5.2.1 Travel Delay Improvement ............................................................... 83

5.2.2 Travel Distance Degradation ............................................................ 88

5.2.3 Delay vs. Distance Representation ................................................... 93

5.3 Operator Oriented Performance Metrics ................................................... 94

5.3.1 Lane Utilization and Delay ............................................................... 95

5.3.2 Vehicular Throughput ....................................................................... 98

5.4 Effects of Initial Congestion Indicator on End to End Delay ................... 99

5.5 Results with Partition Bridging and Varying Traffic Input Rates .......... 101
Chapter 6: WiNDCC Performance for Handling Traffic Events .................................... 102
6.1 Simulation Setup ..................................................................................... 103

6.2 User Oriented Performance Measures .................................................... 104

6.2.1 Travel Delay Improvements ........................................................... 105

6.2.2 Travel Distance Degradation .......................................................... 107

6.3 Operator Oriented Performance Measures .............................................. 108

6.3.1 Lane Utilization and Delay ............................................................. 109

6.4 Vehicular Throughput ............................................................................. 1 l l

6.5 Results with Partition Bridging and Varying Traffic Input Rate ............ 1 12
Chapter 7: WiNDCC Performance with Cache and Carry Message Forwarding .......... 1 13
7.1 Simulation Setup ..................................................................................... 1 14

7.2 Target Flow Delay .................................................................................. 117

7.3 Target Flow Travel Distance .................................................................. 1 19
Chapter 8: Performance of WiNDCC-enabling Wireless Network ................................ 121
8.1 Simulation Setup ..................................................................................... 121

8.2 Network Overhead .................................................................................. 122

vii

8.2.1 Generated Delay Packets ................................................................ 123

8.3 Fast Forwarding Benefits ........................................................................ 126

8.4 WiNDCC Performance with Varying Packet Error Rate ....................... 129

8.5 WiNDCC Performance with Varying Penetration Rate ......................... 131
Chapter 9: Conclusions and Future Work ....................................................................... 132
9.1 Conclusions ............................................................................................. 132

9.2 Future Work ............................................................................................ 134

9.2.1 Simulation and Algorithmic Fine Tuning ....................................... 134

9.2.2 Lower Layer Considerations ........................................................... 134

9.2.3 Topology Specific WiNDCC Parameterization .............................. 135
Bibliography .................................................................................................................. 1 36

viii

LIST OF TABLES

Table 3-1: WiNDCC packet contents ...................................................................... 44
Table 4-1: Traffic network parameters .................................................................... 77
Table 5-1: Vehicular input rates ............................................................................. 82
Table 5-2: Vehicular flow specifications ............................................................... 82
Table 7-1: Experimental flow properties .............................................................. 1 14

ix

LIST OF FIGURES

Figure 1-1: Sample traffic grid .................................................................................. 2
Figure 1—2: Incident with possible travel re-routes ................................................... 4
Figure 1-3: Delay vs. distance perspectives for vehicle A and B .............................. 8
Figure 1-4: Generalized delay vs. distance perspective .......................................... 10
Figure 2-1: Distance based back off scheme of [22, 23] ......................................... 27
Figure 2-2: Sufficient transmission interval from [29] ........................................... 29
Figure 3-1: Basic functional entities and their interaction ...................................... 35
Figure 3-2: Service management and WiNDCC data exchange ............................. 37
Figure 3-3: WiNDCC network architecture ............................................................ 38
Figure 3—4: Overall system architectural summary ................................................. 40
Figure 3-5: Path computation module ..................................................................... 43
Figure 3-6: Calculation of RCI ................................................................................ 47
Figure 3-7: Link exit strategy .................................................................................. 49
Figure 3-8: Link exit strategy (continued) .............................................................. 50
Figure 3-9: Event notification procedure ................................................................ 51
Figure 3-10: ZOR for info from darkened link, marked with stripes ...................... 55
Figure 3-11: ZOR for info from striped links, darkened ......................................... 57
Figure 3-12: Logic for receive module ................................................................... 59
Figure 3-13: DET computation ............................................................................... 59
Figure 3-14: FAT definition .................................................................................... 62
Figure 3-15: Fast forwarding logic ......................................................................... 64
Figure 3-16: Cache and carry functionality ........................................................... 68

Figure 4-1: Simulated traffic network with relevant markings .............................. 76
Figure 5-1: Simulated traffic network with relevant markings .............................. 81
Figure 5-2: Travel delay benefits, highly congested traffic network ...................... 84
Figure 5-3: Overall travel delay distribution, highly congested traffic network.... 86
Figure 5-4: Flow 1 travel delay distribution, highly congested traffic network 86
Figure 5—5: Flow 2 travel delay distribution, highly congested traffic network 87

Figure 56: Flow 3 travel delay distribution, highly congested traffic network ...... 87

Figure 5-7: Travel distance degradation, highly congested traffic network ........... 89
Figure 5-8: Overall distance distribution, highly congested traffic network ......... 90
Figure 5-9: Flow 1 distance distribution, highly congested traffic network .......... 90
Figure 5-10: Flow 2 distance distribution, highly congested traffic network ........ 91
Figure 5-1 1: Flow 3 distance distribution, highly congested traffic network ........ 91

Figure 5-12: Delay vs. distance distribution, highly congested traffic network 93
Figure 5-13: Per lane utilization for highly congested network ............................. 95

Figure 5-14: Per lane service percentage for highly congested traffic network ...... 95

Figure 5-15: Per lane delay for highly congested network .................................... 96
Figure 5-16: Vehicular throughput for highly congested traffic network .............. 98
Figure 5-17: Effects of ICI on overall travel delay ................................................ 99

Figure 5-18: Delay with varying vehicular input rates and mitigation schemes. 101

Figure 6-1: Simulated traffic network with relevant markings ............................ 103
Figure 6-2: Average travel delay with event present ........................................... 105
Figure 6-3: Travel delay distribution with event present ..................................... 106
Figure 6-4: Average travel distance with event present ....................................... 107

xi

Figure 6-5: Travel distance distribution with event present ................................. 107
Figure 6-6: Per lane utilization with event present .............................................. 109
Figure 6-7: Per lane service percentage ............................................................... 109
Figure 6-8: Per lane delay with event present ...................................................... 1 10
Figure 6-9: Vehicular throughput with event present .......................................... I 1 1
Figure 6-10: Delay with varying vehicular input rates and event present ............ 1 12
Figure 7-1: Simulated traffic network with relevant markings ............................ 1 14
Figure 7-2: Average travel delay for target flow .................................................. l 17
Figure 7-3: Delay distribution for target flow ...................................................... 118
Figure 7-4: Average travel distance for target fiow ............................................. 1 19
Figure 7-5: Distance distribution for target flow ................................................. 120
Figure 8-1: Delay packet generation .............................................................. ..... 123
Figure 8-2: Total packet generation ..................................................................... 125
Figure 8-3: Fast forwarding travel delay comparison .......................................... 127
Figure 8-4: Fast forwarding packet delivery delay comparison ........................... 128
Figure 8-5: Travel delay with varying packet error rates ...................................... 130
Figure 8-6: Travel delay with varying penetration rates ....................................... 131

xii

KEY TO SYMBOLS OR ABBREVIATIONS
ADI: Adaptive Dissemination Interval
ASTM: American Society for Testing and Materials
DET: Data Expiration Time
DSRC: Dedicated Short Range Communications
DTA: Dynamic Traffic Assignment
EBT: Event Backoff Time
EWT: Event Wait Time
FAT: Forward Attempt Time
FM: Frequency Modulation
GPS: Global Positioning System
ICI: Initial Congestion Indicator
IEEE: Institute of Electrical and Electronics Engineers
MAC: Media Access Control
NTCC: No Traffic Congestion Control
RC1: Relative Congestion Index
TDV: Typical Delay Value
UDV: Updated Delay Value
VANET: Vehicular Ad Hoc Network
WiNDCC: Wireless Network assisted Distributed Congestion Control
ZOF: Zone Of Forwarding

ZOR: Zone Of Relevancy

xiii

Chapter 1: Introduction

The primary issue addressed in this project is one that affects most people and the
modern society whose development is intricately predicated on the performance of the
roadways they travel. For many years, the primary mode of transportation in the United
States and various countries world wide has been the automobile. In other countries,
automobile usage is rising steadily, just as it has in many of the ever growing US.
markets. To account for the gradual increase that has taken place in terms of automobile
usage and municipality development, roadways are built to connect people with places.
As a consequence, the primary reason for the creation and upkeep of roads is to insure
drivers a selection of viable paths to travel. This is especially so in urban areas, where
the number of drivers, along with the increased amount of unique destinations to travel, is
sometimes such that the existing roadways can not effectively accommodate all of them.
Also, roads are built to connect newer areas to ones that are more established.
Nevertheless, no matter the specific reason for developing a new road, circumventing the
traffic congestion that takes place on all roadways is critical to the travel times and

happiness of the motorists who use them.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

21 22. 23. 24.

W m [11
-1=? 1 —-F-— I a 4 =21]
20 1L } 25
El: 5 6 l 7 l 8 =17
Il: 9~ .1 :l=i :77]
18 + J[ 27
13 —i—— 14 1 15 l 16 ~ :2:

 

 

 

 

Figure 1—1: Sample traffic grid

1.1 Travel Choices in Vehicular Environments

To help illustrate and put into perspective the work done in this thesis, consider the
basic grid traffic network found in Figure 1-1. For this discussion, consider the outer
most squares, labeled 17 through 32, sources or destinations for drivers using this
arrangement of roads. The inner labels, 1 through 16, represent intersections in which
normal traffic light logic applies. Although simple in nature, a driver utilizing this
network will face a problem similar to motorists traveling in any realistic traffic setting;
that is, at each intersection a driver has a choice as to which direction to continue, based
on their perception or knowledge of the potential roadways and the destination location.

This perception is usually dependent on what one can visually see while traveling or his

general understanding of which routes are most efficient. For certain drivers, a path is
usually set in stone regardless of the current traffic conditions. For others, consideration
of the time of day or events is given, and a route is selected based on these observations.
Some drivers use logic that involves aspects from both perspectives. As a consequence,
these motorists use hard wired paths for traveling and only deviate from them when they
can visually verify congestion taking place on the links they originally intend to travel.
In this case, a certain degree of familiarity is required to execute efficient travel.
Therefore, in instances when a driver is travelling in areas in which they are not familiar,
these types of approaches can not be used since drivers do not know the exact
consequence of making a particular travel decision. Nevertheless, for each of these types
of motorists, there is an issue of whether or not the perceived traffic conditions represent
those actually present on the roadways. As a consequence, the overall travel delay
experienced by travelers is sometimes greatly increased, when there is some activity
within the desired path that prohibits traffic flow at a normal rate.

For example, consider a vehicle utilizing the grid in Figure 1-1 traveling from
intersection 31 to 22. Assume the driver of this vehicle will be taking the path he or she
thinks is the best, traveling north at each intersection until reaching the destination
labeled 22. This path is also highlighted in Figure 1-1. On an average, assume the travel
time for this particular path is 4 minutes. That is, under the typical best case
circumstances in which this network operates, 4 minutes is how long a motorist should
expect to travel the road between intersections 31 and 22 in the northern direction.
Furthermore, suppose this is also the optimal or fastest path for a driver destined for

intersection 22, from the intersection marked 31.

 

 

int
uh
Ihi
101]
mu
[ha
quf
0f I]

ma}

 

 

32 31 29

 

 

- From Original Route - - Re-route #1
Slowed/Stopped Link m Re-route #2

 

Figure 1-2: Incident with possible travel re-routes

Now, think about an event that slows or stops traffic within the link between
intersections 10 and 6, Figure 1-2. If the traveler reaches this link between the time in
which this event happens and that it is cleared up, he will be delayed during his trip; and,
this vehicle will potentially arrive at the destination intersection after traveling a much
longer time than the average, 4 minutes. Also, highlighted in Figure 1-2 are two of the
many alternate paths a driver may well choose to utilize, based on its current position and
that of the destination. However, depending on a motorist’s knowledge of this particular
traffic environment, they may not realize the available detours. Also, while utilizing one
of these paths may allow the driver an opportunity to avoid the congestion issue, the path

may also be blocked or there may be an advantage in using one path over the other.

There could also, amongst the set of possible diversions not highlighted on the map and
the position of a vehicle needing to be diverted, be another route that could be superior.
This blockage or link slowdown represents an inevitable and frequent aspect of vehicular
travel.

The goal of this project is to create a completely distributed and infrastructure free
vehicular ad hoc networking based application, network protocol, and specification to
solve problems such as the aforementioned. Utilizing the basic principles discussed here,

the motivation of this work can be found.

1.1.1 Delay vs. Distance Examination

When considering the issues presented in section 1.1 and the example traffic grid
given, a key challenge associated with real time vehicular route modification system
development can be realized. That is, assuming the system at hand is able to compute
and deliver routes with the shortest travel delay under optimal traffic network
performance, the vehicles that are taken away from that primary path to a secondary one
will travel, in general, a longer distance than those remaining on the primary. It is an
inherent issue associated with this problem, although travel delay mitigation can be
achieved by moving vehicles away from congested areas. That can be seen by examining
the distance of the highlighted secondary paths of Figure 1-2 and comparing the distance
to that of the primary path, Figure 1-1. On the other hand, there may be instances where
vehicles travel a shorter distance. In this case the secondary path is slower than the
primary, resulting in the primary path being longer in distance but shorter in estimated
travel time than a secondary route. For the sake of this discussion, assume that the

primary path is not only faster in regard to time but also is shorter. However, the ideas

 

 

 

 

“I

intent.
Once :1
F1 gurc
perspc.
notice
lht lra
mechur
the sci
benefit
lilting 1

 

fmm [
SNem
Mule
lrumc
de‘lln;
Ihan ll
they b
Perm...

than “

 

and arguments still apply and will be briefly discussed for cases when a secondary path is
shorter than the primary.

Reconsider Figure l-2 and the scenario depicted, vehicles traveling from
intersection 31 to 22 with a congested or stopped link between intersections 10 and 6.
Once again, the primary travel path for this source and destination pair is as outlined in
Figure 1-1, north at each intersection until the destination is reached. Now, to help put in
perspective the delay versus distance tradeoff and its relationship to system performance,
notice the vehicles marked A and B found in the link before the congested roadway. If
the travel of these vehicles is under the influence of a route modification system, the
mechanism may intend for them to be directed away from the primary path onto one of
the secondary ones to evade the traffic congestion. However, it may also be most
beneficial for them to remain on the primary path; in this case, the traffic congestion
along the indicated link may not degrade the travel delay enough to warrant switching to
a longer path. Dealing with the issue of whether or not a vehicle should switch away
from the primary travel route, during times of slowed or stopped traffic, is key to overall
system success. To understand why, assume that vehicle A remains on the primary path,
while vehicle B switches to the path west of the congested link in an effort to avoid the
traffic congestion ahead. Now, vehicle B will definitely travel a longer path to reach the
destination. On the other hand, it is not guaranteed that it arrives at the destination sooner
than the vehicle who has maintained the congested primary travel path, A. However, if
they both exit their current link at relatively the same time, from an individual user
perspective especially, it is most desirable for vehicle B to arrive at the destination sooner

than vehicle A. That is, in order to completely warrant the switching of vehicle B to a

 

 

 

longer ‘

immcd

 

 

 

longer travel path, vehicle B should be awarded with a smaller travel delay than a vehicle

immediately in front of it utilizing the congested. primary travel path.

 

 

C(md
del
\‘ehjc'
apcrll‘

8' m0

 

 

_B(i) -_Secondary Path B(2)I- Secondary—Path
O O

 

 

Normal Operation A - Primary Path

 

 

 

 

‘f r 1

End to End Travel Delay

 

V

 

 

 

Figure 1-3: Delay vs. distance perspectives for vehicle A and B

Figure 1-3 helps put this idea into perspective. In this figure, the primary purpose
is to determine if switching travel paths is justified based on the end-to-end delay and
distance experienced by switched vehicles and those directly before them that don’t
switch. In the case of this example, it refers to vehicle B and A respectively. The x axis
represents end-to-end travel delay while the y denotes end to end travel distance, and
each of the data points represents the end to end delay and distance for the indicated
vehicle. Farthest to the left, the normal operation data point represents the typical delay
and distance of a vehicle utilizing the prescribed travel route under optimal traffic
conditions. Notice it is located along the black dashed line, which indicates the travel
distance of the primary path denoted in Figure 1-1. Compared to the data point for
vehicle A, it is shifted to the left signifying that vehicle A utilizes the primary path during
a period of congestion, as the example suggests. In regard to the possibilities for vehicle

B, two potential points are included to highlight the importance of appropriate switching,

B(l) and B(2). Both points are located above the dashed line, representing switching to a
longer path to avoid the congestion that vehicle A experiences. However, point B(l) is to
the left of A and B(2) is to the right. Since this indicates a smaller travel delay for
vehicle B, point B(l) would represent a justified instance in which vehicle B changes to a
longer travel path. B(2) signifies an unjustified or inefficient switch since B would travel
a longer distance and have a greater travel delay than vehicle A. The analysis of path

switching during times of congestion can be analyzed by viewing a diagram such as this.

 

 

, Justified Switching , Unjustified
Region __ Switching Region

 

 

 

 

 

 

 

 

 

 

 

 

 

End to End Travel Delay

 

Figure 1-4: Generalized delay vs. distance perspective

To summarize the consequences of switching away from a primary path during
instances of congestion, examine Figure 1-4 and assume each data point pertains to
vehicles sharing the same starting and destination link. Here, point A represents the
optimal average delay and distance of a vehicle traveling the primary path, denoted again
by the dashed line. As a result of a vehicle B traveling the primary path with congestion
present, its data point is moved farther along the delay axis while remaining on the same
dashed line as A. Points C, D, E, and F are possible representations of a vehicle that
immediately follows vehicle B, but switches away from the primary patch due to
perceived traffic congestion. If point C or F represents the distance and delay of this
vehicle, the vehicle has arrived within the unjustified switching region, since it has
switched paths and arrived at the destination later than vehicle B. If point D or E is
representative of the distance and delay of this vehicle, then switching is justified since

the vehicle in question arrives at the destination sooner than vehicle A. Note that points

10

C and F indicate paths that are shorter than the primary path but longer, on average, in
terms of delay. Nevertheless, the main goal of a traffic route adjusting system should be
to only switch vehicles away from the primary path when the mechanism is most sure the
vehicle will be delivered within the justified region, in comparison to a non- switched
vehicle. By utilizing the depicted quantities a and A the argument can be furthered as
follows. For vehicles with characteristics similar to D, taking a longer path than the
primary but showing delay improvement, the mechanism should look to decrease the
angle a while increasing A. In the case of an arrival like C, the goal is also to decrease a
but A should be decreased. For vehicles like E, taking a shorter path than the primary but
showing delay improvements, the goal is to increase both a and A. The goal for a
vehicle, such as F, traveling a shorter distance than the primary path but a longer time
than the reference vehicle A, is to increase a and decrease A. By utilizing these
principles, one can see the importance of switching vehicles during appropriate times
when designing a system meant to choreograph traffic during times of congestion or

otherwise.

1.2 VANET Basics and Applications

The Vehicular Ad hoc Network (VANET) has developed into a mature research
space. In regard to vehicular technology in general, the idea of incorporating ad hoc
networking principles and capabilities adds to an already rich set of application
capabilities being offered by auto makers. In short and as opposed to current
communication tactics used by vehicle and in car communication device manufacturers,
ad hoc networks will allow high speed connectivity on a vehicle to vehicle and vehicle to

roadside station basis [1]. That is, intelligent vehicular communication devices will be

11

able to communicate with roadside stations and other vehicles on a one or multi-hop basis
[1, 2], while current wireless vehicular communication exists strictly between vehicles
and centralized entities [3]; As a consequence, the vehicular devices do not communicate
directly with one another. A brief look at the applications enabled by vehicle to vehicle

communication is as follows.

1.2.1 Travel Improvement and Safety

For obvious reasons, a healthy amount of VANET applications fall into the
category of safety or travel improvement. To clarify, the travel improvement breakdown
describes applications that assist motorists in the day to day situations encountered while
driving [4-8]. Also, included are safety applications designed specifically with the safety
of drivers in mind [4, 9, 10]. In terms of implementation, most of these services are
accomplished by vehicle to vehicle communication as opposed to vehicle to roadside
[11], although some utilize the aid of base stations. This is due to the time pertinent
nature of the messages being exchanged. By extending some of the one hop sensor based
safety applications currently found within the vehicular industry, the advantage of using
VANET travel improvement technology can be found. For example, currently sensors
can alert drivers of vehicles exhibiting sudden decreases in speed directly in front of
them. However, under a VANET based scheme [6, 9, 10], motorists can be alerted of
stopping or rapidly slowing vehicles much farther ahead of the car preceding it. Other
systems assist groups of vehicles by indicating collective travel speeds to assist in
vehicular smoothing or cruise control [5, 7, 12]. In fact, the topic of works such as this

thesis is also included within the range of travel improvement and safety and will be

12

discussed in greater detail in the related works section. In regard to travel improvement

and safety, the VANET space provides various relevant applications.

1.2.2 Leisure Applications

Aside from the travel improvement and safety applications implemented by the
VANET framework, leisure applications are also relevant. Most of them include
providing internet access to drivers via the VANET enabled in car devices. Therefore, it
can be understood why internet gateways or roadside stations usually accompany the
implementation of these sorts of systems [1 1]. Additionally, other applications utilizing
vehicle to vehicle and vehicle to roadside functionality include shopping, gaming, and
marketing for business and other services relevant to travelers [13, 14]. Although not the
category relating to the work presented in this thesis, internet and other leisure services
are actively being considered from an application and lower layer networking

perspective.

1.3 VANET Oriented Route Guidance System

The topic of this thesis combines the abovementioned principles to create a system
capable of detecting and correcting traffic congestion issues. As previously mentioned,
this system would fall into the application arena of travel improvement and safety.
Regarding the basic implementation principles for the system developed in this thesis,
Wireless Network enabled Distributed Congestion Control (W iNDCC), the mechanisms
and protocols do not require the assistance of any infrastructure or centralized entities.
Instead, traffic delay mitigation is achieved by utilizing the VANET on a strictly vehicle

to vehicle basis. That is, the gateways utilized by most applications within the leisure

l3

subset will be unneeded by WiNDCC. Therefore, with respect to the traditional wireless
network system architecture components, WiNDCC protocols reside within the network
and application layer. In the related work section, similar VANET oriented systems will

be discussed.

1.4 Current Route Guidance Systems

In regard to the current offerings of automobile and in car navigation device
manufacturers, route guidance or congestion avoidance packages are available. Unlike
WiNDCC and other VANET based solutions, these systems rely on centralized data
locations to store and relay the traffic information to equipped vehicles. Also, they do
not utilize other vehicles to assist in the probing and transmitting of data. Instead, the
centralized entities communicate directly with subscribing vehicles. In terms of the
communication mediums utilized, there are a few that are used to transmit traffic data to
users [3]. Traditional cellular networks, newer FM radio links, and satellite connections,
are the current standards used to get the traffic updates to drivers. As noted in the article,
the performance of these systems is sometimes unpredictable and subject to high delay,
with respect to the timeliness of receiving the traffic status of a particular link.

With respect to VANET solutions for the problem of traffic congestion mitigation,
the delay and accuracy of information could be greatly improved. That is, since vehicles
communicate with one another, traffic congestion can be readily identified and broadcast
specifically to the relevant devices that need them. However, the current offerings,

although somewhat limited, prove to be useful to the motorists who equip the devices.

14

Chapter 2: Related Work

In general, the literature related to this work is directly in line with the multi layer
solution proposed in WiNDCC. Since the overall system is enabled by utilizing
navigation devices, presented first are a class of papers that relate to the evolution of in
car hardware systems and challenges in general. Then, in accordance with the main
system goal of alleviating travel delay in vehicular environments, works that deal
specifically with this task are discussed; here, VANET principles are not incorporated.

Finally, since the route guidance system presented in this thesis is implemented by
the VANET framework, manuscripts particular to VANET principles and challenges will
be discussed. Relating to the layers in which WiNDCC operates, VANET network layer
papers particular to WiNDCC operation will be covered, along with VANET oriented

application layer systems designed for route modification and travel delay mitigation.

2.1 Onset of in-Vehicle Devices

In regards to the current product offerings within the realm of vehicular navigation
systems, both manufacturers installed and off the shelf navigation units are becoming
more readily available and used within the end user domain. However at the onset of
their development, work was committed to understand the hardware, software,

application capabilities, and other design issues characteristic to such a device.

2.1.1 The Need for Position Information

One of the core requirements of any vehicular navigation or service device is that
the devices understand and use the information relating to its own geographical position.

This need is common in various application domains, not only within vehicular context.

15

In [15], the integration of two position determining implementation schemes is combined
to form an accurate method of determining position within the vehicular context. The
two methods are Global Positioning System (GPS) and dead—reckoning; GPS uses
satellites as reference positions to determine position, and dead-reckoning uses heading
and distance sensors to measure displacement vectors that are used in a recursive manner
to determine vehicle position. Discussed in the manuscript are the various limitations of
each scheme and the way in which combining the two results in superior performance.
Results and analysis relate to the efficiency of each individual position acquirement
method. Other results show how the combined system is able to recover from the errors
in which the two schemes present individually. From an implementation perspective, the
topic and conclusions from a work such as this are seen on a wide scale basis, especially

within the in car navigation device domain.

2.1.2 In Car Devices and Driver Interaction

In [16], one of the initial perspectives into the viability of in car systems is given,
with respect to human interaction. This sort of report is important because, while striving
to improve driver satisfaction by using visual or auditory navigation devices to assist with
certain tasks, designers must be aware of the consequences associated with actual
motorist interaction. That is, although navigation devices may aid drivers at certain
driving tasks, the usage of such devices could produce severe hazards within the traffic
environment by taking the attention of motorists away form the road. By way of an
intense simulation study, several performance indices were measured including heart rate,
speed, and navigational errors seen when subjects were utilizing one of a few navigation

interfaces. Overall, the age of subjects affected their performance, with younger people

16

faring better than older, in terms of safely using their assigned navigational device. Also,
of the navigation devices used, subjects tested with the more complex of the devices
drove more slowly; This is to be expected since most drivers typically slow down to
process information when driving, and the more complex device differed from the others
by introducing much more navigational messages to the test subjects. In terms of
understanding how drivers of different ages will react to navigational devices of varying
complexity, with respect to various performance indices, this work presents some

preliminary data that encouraged the deve10pment for the devices available today.

2.1.3 An Early Driver Information System

As a basis for the FM radio based [3] dynamic traffic routing systems seen today,
this work creates a hardware and software framework, called TravTek, capable of
utilizing the communication medium for the purpose of probing traffic information and
guiding vehicles according to it [17]. As a consequence, the goals of the TravTek driver
information system are very similar to those of the WiNDCC framework presented in this
thesis. The study involves the implementation of 100 vehicles within Orlando Florida,
and investigates the usage of a centralized traffic management center connected to the in
vehicle devices via the FM radio link. At the time of this effort and especially from a
hardware perspective, the design is obviously restricted to the usage of the technology of
its time. However, the built upon principles are very much at the heart of current route
guidance systems and WiNDCC, although WiNDCC incorporates additional logic meant
to assist in determining when delay information should be extracted. That is, vehicles
begin by utilizing nominal travel time information to determine the suggested travel

route, depending on a vehicles current position and that of the destination; particular to

17

the task of position awareness, this is accomplished by using global positioning satellites,
just as it is in newer navigation systems. Then, as updates are received regarding relevant
travel links, the system re-computes travel routes based on them. In terms of a functional
breakdown, the authors describe each component individually including route selection,
driver interface, data logging, route guidance, and a data base responsible for storing
establishment destination specific information for a particular geographic region.
Considering the system goals and implementation scheme of such a system, this
translates to a centralized dynamic route computation framework with GPS and FM radio
at its position awareness and communication backbone. The main ideas of this work are
important and are being utilized today in terms of the delay mitigation and route
notification tactics utilized in today’s navigation devices [3]. In addition, one can find

similarities between TravTek and the proposed mechanism, WiNDCC.

2.2 VANET Networking Challenges and Solutions

A work outlining some of the challenges of VANET design and implementation is
as follows [18]. The authors begin by highlighting a few typical issues associated with
random waypoint induced mobile ad hoc networking in general, the superclass in which
the VANET is based. Then they compare the applicability of these issues within the
context of the VANET or inter-vehicle communication (IVC) realm. Finally, the paper
discussed the design implications associated with the VANET. A close look at this work
will be given, as it describes the difficulties and challenges associated with designing a

system such as WiNDCC.

18

Some of these issues, from the perspective of the link layer, include the hidden
and exposed terminal problem. Here, because of the positions of communicating nodes,
connectivity and throughput is adversely affected.

From the routing or network layer outlook, three broad classes of ad hoc
networking routing protocols are identified. Table—driven, source—driven, and position-
based routing strategies are the identified breakdowns. Table—driven routing protocols
are proactive in the sense that each node attempts to maintain a current representation of
the network topology. Contrarily, source—driven protocols are reactive in the sense that
routes are requested by source nodes only when needed. In terms of position-based
routing protocols, a location service may be needed to find the location of a destination
node. These protocols, the authors mention, naturally support services in which the set of
recipients is defined as nodes located in some target region of space.

In reference to security, the authors note that because the mobile ad hoc network
lacks infrastructure, securing it is very difficult. However, by way of cryptographic
routing techniques, redundancy based secure message transport, and intrusion detection
paradigms, the mobile ad hoc network research space contains various works intending
on securing the networks. Cryptographic routing techniques increase network overhead
by including cryptographic information responsible for validating routing messages.
Secure message transport takes advantage of multiple paths between source and
destination nodes to ensure data messages are not compromised. Intrusion detection
schemes use packet overheating to be sure malicious information is not propagated

throughout the mobile ad hoc network.

19

After describing the principles pertaining to the mobile ad hoc network, a
simulation study was performed based on a sample traffic scenario to understand some of
the differences between the mobile ad hoc network and the VANET. The primary
differences are described in full detail.

The first fundamental difference relates to the rapid changes in the network
topology seen within VANETS. These changes occur despite the fact that vehicles must
remain on the roadways and cannot venture completely randomly in a particular
geographic area, therefore somewhat restricting their mobility. In addition, the
topological inconsistencies are caused by the high relative speed of vehicles and can be
predictive when considering the traveling direction of vehicles. That is, the links created
by vehicles moving in the opposite directions are shorter lived than those between
vehicles traveling in the same direction. The authors also mention that, although this
degrades performance in relation to other metrics, increasing radio range helps increase
the connectivity and decrease the changes within topology.

The second highlighted difference between the mobile ad — hoc network and
VANET deals with the frequent fragmentation of the network, in which chunks of the
network are unable to reach nodes in nearby regions. This effect is motivated by the slow
introduction and penetration rate associated with the onset of VANET technologies; the
scenarios presented are based on the optimistic goal of having VANET enablement in
20% of vehicles. Once again, the costly practice of increasing radio range does decrease
the fragmentation.

Thirdly, the effective network diameter in a VANET will typically be very small, in

comparison to the traditional ad hoc network. This is because the routing paradigms used

20

within the mobile ad hoc networking realm are rendered much less effective within the
VANET, because of the topological inconsistencies and rapid changes involved with this
system. Therefore, the effective network diameter is inconsistent and decreased. That is,
since proactive routing keeps data relating to the full network topology, it is very difficult
to do so in the every changing topology of the VANET. Also, reactive routing suffers
since a path may cease to exist almost as quickly as it was discovered.

The fourth difference speaks about the lack of redundancy found within the
VANET. Since multiple paths cannot be readily had between sources and destinations,
the abovementioned security mechanisms, and other protocols utilizing this requirement,
would not be relevant in this sort of network. As a result and as previously mentioned,
increasing the radio range could assist in this effort. However, doing so will increase the
number of exposed nodes and decrease throughput by introducing a larger interference
radius.

Finally, when considering the abovementioned issues, the authors discuss some of
the design implications that must be addressed when working within the VANET space.
At each layer, considerations must be made in order to establish and maintain usable
connectivity for the applications implemented by the VANET. At the physical layer,
different frequency bands, the usage of roadside infrastructure, and directional antennae
are mentioned as ways to assist in the design of these networks. At the link layer, it is
suggested that decentralized time slots or spectrum be used. Routing layer operations
would be benefited by using location based schemes, which must be specially tailored for
the VANET. In terms of security, it is suggested that adding roadside receivers could

allow for the VANET to utilize some of the security schemes seen within the mobile ad

21

hoc network. However, it is acknowledged that the security issue is one that is very
difficult to solve within the VANET.
With respect to these challenges, the WiNDCC system is designed to work amidst

in as efficient manner as possible.

2.3 WiNDCC Contributing Protocols and Considerations

In terms of the WiNDCC system presented in this thesis, it has flavors from various
route guidance, link travel time estimation, and VANET routing and application layer
paradigms. This section is broken down in terms of the main WiNDCC operational

components and the relevant literature contributing to each will be discussed.

2.3.1 Application Layer Functionality

In terms of the WiNDCC system developed for this thesis, the high layer
application layer goals have been described in section 1.1 and relate to mitigating
congestion and traffic delays in vehicular environments. In reference to how the system
aims to solve these problems, a few works should be referenced.

In [19], a simple Dynamic Traffic Assignment (DTA) model based on real-time
local-feedback information is introduced. When considering the goals of this system,
they are very similar to WiNDCC. However, the traffic sensing and transmission
schemes are much different. The specification uses information collected from lane
embedded sensors to determine the status of the traffic environment. In addition, the
authors suggest three main assignment techniques for the purpose of rerouting traffic
during instances of congestion or otherwise. The first, a stochastic assignment method,

perturbs the link costs within predefined limits to randomize the route selection process

22

for a vehicle. The second uses global feedback assignment, a scheme which assumes that
drivers who are familiar with the road network will reroute if information on the present
state of traffic conditions is fed back to them. Lastly, the local feedback assignment
model presented is based on real-time local information that is designed to produce
reasonably accurate results with a minimal number of parameters and computational
effort. That is, the model acquires only the real-time data on link costs for the next links
out of the current intersection and decides which turn to take based on this localized
information. As for simulation setup, the authors use a mock traffic network and track
the end to end travel delay associated with each vehicle. Since the information is
assumed to be acquired by way of sensors embedded within the lanes and the traffic
information would then need to be gathered, edited, and relayed back to vehicles, the
effect of time lag is studied.

The results show by comparing the feedback and stochastic assignment methods,
the random assignment method fares better than the global feedback when the time lag is
greater than 2 minutes. However, the local feedback fares better than the stochastic
regardless of the time lag quantity. Then as a second experiment, the effects of incidents
are examined according to the three assignment methods. It can be seen that the delay
values under the feedback assignment methods converge, while the stochastic method
brings the traffic network to unstable. As a conclusion and under the typical 5 minute
time lag associated with gathering information from lane sensors, the local feedback
assignment method proves to be the more effective of the assignment methods used. As a

result, WiNDCC along with other dynamic route modifications systems also inherit a

23

feedback oriented traffic response paradigm. However, the effect of time lag is much less
than that assumed in this paper.

In [20], the authors examine how much individual traffic data is needed in order to
obtain reliable traffic information for a certain road link within the VANET. The authors
examine works that exploit the central limit theorem to develop minimum sample sizes.
However according to the central limit theorem definition, data would either need to be
normally distributed or there must be a very large amount of non-normal data. However,
travel time data are unlikely to be normally distributed, although during uncongested
times this may be so. Therefore, during times of congestion, these methods may
invalidate the central limit theorem and produce incorrect sampling sizes. This work
introduces an acceptance probability that operates independent of a distribution, unlike
the central limit based schemes. It uses the median of all individual data within a time
window centered on the time instant in question as a proxy for actual information. The
results of a simulation study show that the acceptance probability based extractions better
represented the actual traffic conditions during times of congestion than the central limit
theorem based schemes. Otherwise, both methods performed similarly. WiNDCC takes
into account the spirit of the arguments and results obtained in this paper in its own
sampling and delay message creation scheme. However, the system uses much less
complex foundations to determine when to sample a links estimated delay time, while
looking to minimize the overall number of extractions.

Another work which contributes to WiNDCC application layer functionality is as
follows [21]. Here the authors examine the problem of forecasting future link travel and

network congestion conditions. The authors argue that under the influence of a dynamic

24

traffic assignment scheme that uses perceived traffic network information to influence the
travel of vehicles, the original free flow forecasts used to compute routes are invalidated.
As will be seen in the WiNDCC formulation, this phenomenon is inevitable and is not
necessarily a problem with respect to overall system operation. If fact, it will be hinged
in terms of overall system operation and performance. Also presented in this paper is a
key concept in regard to WiNDCC system operation. The authors compare by simulation
the effects of forecasting link travel times as a function of vehicles entering a link or the
exit delay values associated with vehicles exiting a link. Their results Show that when
considering the link exit delay measurements, the delay performance is better behaved
and improved. Therefore, in Chapter 3 it will be seen that WiNDCC uses this results in

its system development.

2.3.2 Network Layer Functionality

Simply stated, the WiNDCC network layer goal is to propagate the information
generated and received as efficiently as possible to the vehicles that need it. In terms of
the resulting implementation, there are a few works that contribute to the WiNDCC
routing layer solution.

It will be revealed in Chapter 3 that certain generated packets will be forwarded
away from the origination point as fast as possible by the WiNDCC network layer. In
[22, 23], a mechanism is introduced and used that tailors specifically to this goal.
Presented is an approach to distributing messages among highly mobile hosts in ad hoc
networks. The approach focuses on using direct radio communication between moving
vehicles on the road that requires no additional infrastructure. To better understand the

strategy, consider the broadcasting nature of radio waves. Multiple receivers can receive

25

the same packets simultaneously. Therefore, determining when and how to forward
messages is important, as various issues arise if this is not carefully handled, as seen in
[24]. The authors of this work assume that any received packet contains the position of
its sender, by way of navigation system. Then, by knowing its own position, a receiver
determines the amount of time it will wait before forwarding a packet based on its

distance from the sender.

26

 

MaxWT
Range

WT(d) =— Oci +MaxWT

d = min{d,Range}
MaxWT: maximum waiting time
(1: distance

Range: transmission range

 

 

 

Figure 2-1: Distance based back off scheme of [22, 23]

This determination is made according to the equation listed in Figure 2-1.
According to this formula, the waiting time, WT, is shorter for more distant receivers and
longer for farther ones. The aim of using this mechanism allows their proposed system to
disseminate messages quickly and efficiently around the area surrounding the vehicle.
WiNDCC uses the concept of distance based back off to assist in propagating its own
delay notification messages. Other works acknowledging a distance based back off
scheme to assist in message forwarding operations within the VANET are [25] and [26].

Aside from moving messages as far from the origination as fast as possible, the
WiNDCC mechanism also calls for vehicles to store and forward messages. This is done
to assist in moments where there are network partitions prohibiting the movement of a
piece of data beyond a certain vehicle. In [27], the authors make use of the concept of
carry and forward, where a moving vehicle carries a packet until a new vehicle moves
into its vicinity and forwards the packet. The mechanism developed is different from
existing carry and forward solutions by making use of the predictable vehicle mobility,
which is limited by the traffic pattern and road layout. They present several vehicle

assisted data delivery protocols and results for each one. In terms of the WiNDCC

27

system presented in this thesis, the routing layer functionality calls for a geographical
aware store and forward functionality, a simplistic rendition of [27]. Other works
utilizing a trajectory aware store and forward approach are as follows [26-28].

Another contribution is important to WiNDCC network layer functionality. In
terms of wireless network efficiency, one will find various WiNDCC protocol and system
nuances designed to keep the wireless channel useable and free from the effects of

redundancy, contention, and collision [24].

28

 

2R
k 0 (v] + V2)

Upper bound on transmission interval =
R: transmission range
It: a value greater than the ratio of maximum velocity to average

velocity of a road segment

v], v2 .' average velocity for each travel direction

 

 

 

Figure 2-2: Sufficient transmission interval from [29]

This work [29] creates an adaptive dissemination mechanism for a decentralized
traffic information system that causes each vehicle to adapt their transmission interval
according to the current traffic speed. The specification also disseminates the traffic
information of different segments at different rates according to the distance from its
current position. In terms of network capacity and utilization, the scheme ensures
efficient distribution of information within the vehicular network. The authors assume,
similar to WiNDCC, that vehicles calculate their own link travel times and periodically
broadcast its travel time spatio-temporal database to other vehicles. Other vehicles will
receive this information and will include new data into their own spatio-temporal
database. In particular, WiNDCC borrows an expression from this work primarily
responsible for the efficient dissemination goals, Figure 2-2. Given R, k, V], and v2, a
vehicle can calculate the maximum transmission interval needed to inform passing
vehicles of any information it has. That is, if a vehicle transmits at intervals less than that
indicated by the expression, it will be possible to communicate with any mechanism

equipped vehicle running in the opposite direction and the required bandwidth will be

29

much lower than the channel capacity. It will be seen in Chapter 3 that WiNDCC takes

advantage of this expression in its own dissemination practices.

2.4 Agent-network Based Route Guidance System

In this paper [30], the authors introduce an intelligent route guidance system based
on agent-network, which can automatically guide vehicles by voice. The work is
presented in a section separate from the others because it presents results similar to those
produced for this study. That is, the primary results deal with the delay mitigation
associated with system usage and the distance trade off that occurs due to this mitigation.
However, the implementation of their system is very different from WiNDCC.
Particularly because this system utilizes, in each road segment, an agent which is
responsible for fusing the data collected from sensors, calculating routes and segment
costs, and communication with other agents to gather global traffic information.
Contrarily, WiNDCC operates strictly on a vehicle to vehicle basis, eliminating the need
for any agent or traffic network infrastructure. Nevertheless, the agents create a
wirelessly or fiber optic enabled back bone computing platform that is responsible for
receiving the information from road sensors, receiving the request from vehicular
devices, and calculating the travel routes to be reported to drivers, as well as transmitting
them via the author recommended Bluetooth links. The paper describes a simulation
scenario that uses a grid network. Results are shown proving, that without their
mechanism and system in place, the overall travel delay is worsened. It can also be seen
that when the mechanism is equipped, the end to end distance is degraded, subject to the

argument presented in section 1.1.1. This work is important because it presents results

30

similar to those found in this work, while also suggesting the usage of wireless devices

and principles to assist with the process.

31

Chapter 3: WiNDCC Framework

In this chapter, the Wireless Network Distributed Congestion Control (WiNDCC)
algorithms and system specifications will be discussed. In short, WiNDCC is a
completely distributed, infrastructure and hello message free, vehicle to vehicle system
designed for the purpose of meeting the traffic network goals explained in section 1.1.
Here, a detailed description of the distributed wireless mechanism responsible for
generating and propagating the protocol messages, needed to attain overall system
responsiveness, will be given.

The chapter is organized in the following manner. First, a generalized look at
WiNDCC goals and objectives will be discussed. Then, a system and network
architectural view will be given. Next, details will be presented about the way the
utilized navigation function computes paths based on the acquired information. Finally
the core of the WiNDCC system will be detailed, which corresponds to the message

generation and forwarding procedures.

3.1 Problem Discussion With Respect to VANET Oriented Solution

In terms of the system goals outlined in section 1.1, the WiNDCC system must be
able to solve those issues, subject to the typical design barriers associated with the
VANET [18]. As a result, the WiNDCC design exhibits careful treatment of the wireless
channel in order to maximize its usage and maintain its integrity for other applications

using the channel.

32

3.1.1 Network Overhead

The amount of packets generated by any protocol existing within the VANET
domain is important to maintaining the health of the underlying wireless network. As a
consequence, WiNDCC only transmits messages as needed within the vehicular
environment. The basic rationale behind this action is as follows. If there is not traffic
congestion in the traffic network, by some definition of congestion, then it is not
necessary to transmit information about it. Because, in line with the system assumptions
to be discussed in a subsequent section, the superior travel path under optimal network
performance is available to each equipped vehicle. Therefore, if there are not issues
within the roadway network, the vehicles should always follow this path. The primary
question then becomes when to broadcast information about a link and how to do so. By
using this principle, the WiNDCC system differs form others that demand vehicles have
constant knowledge of the velocity, direction, and travel plans of neighboring vehicles,
by way of hello message exchange [8]. Also, since the WiNDCC mechanism uses the
communication medium in a broadcast only fashion, there is not a need for any routing
overhead. Sending broadcast messages is more efficient than unicast messages, gaining
even more with increasing network density, as a single transmission can reach more
vehicles; even if a particular piece of information is not useful for a node, it can assist in
further dissemination of the data unit [31]. WiNDCC works to reduce network overhead,

while meeting the overall system goals.

3.1.2 Delay Message Propagation Needs

In the abovementioned section, the main issue is when to generate and broadcast

information about the links within the traffic network. In terms of propagation needs, the

33

question is where and how to transmit the generated messages. Again, because the area
in which a message is propagated interferes with the channel within that area, this is
important as it relates to network overhead. The WiNDCC system addresses this issue by
only transmitting delay messages to the vehicles within the areas of the traffic topology
that need them most. Therefore, upon the initialization of a delay packet and based on
the position and direction of the link being reported, the general propagation area is set.
This assists in terms of wireless network utilization by limiting the area in which delay
messages travel. When considering all of the potential delay messages extracted from
vehicles using a severely congested traffic network, this simple action proves to save
bandwidth on the wireless channel. In reference to how the messages are broadcast to
these areas, a method is hinged to move the information amongst the prescribed relevant
areas as fast and with as few packets as possible [22]. However, if the network is
partitioned and this path is incomplete, other methods [22, 28] are manipulated to assist
with propagation. WiNDCC propagates messages in a way that uses radio
communication to initially and expeditiously move messages away from origination

points and targeted message carrying and forwarding otherwise.

3.2 WiNDCC Architectural Perspective

From an architectural point of view and aside from any networking principles, there
are a few components involved in WiNDCC operation. Also according to the traditional
wireless network architecture, WiNDCC has its own specification that highlighted the

functional entities responsible for the networking operations.

34

3.2.1 Functional Entities and Data Exchange

 

 

 

 

 

Traffic Congestion Control WiNDCC
Service Management ENABLEMENT
- Township, State DOT'S - VANET Appllcatlon/Network
Layer Technology
. Vehicular Navigation Device _’
Manufacturers . Distributed Operation

- WiNDCC Agents utilized on

0 Traffic Congestion Contro| _ an IHdIVIdual VGhICIG baSIS

Enabling Entities

i i

In Vehicle Navigation Device

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 3-1: Basic functional entities and their interaction

In terms of the functional entities and devices responsible for influencing and
implementing the WiNDCC system, they are highlighted in Figure 3-1. The diagram
helps put into perspective the conceptual operation of VANET applications in general, as
typically there is an entity that manages or enables the technologies implemented via
wireless networking. The leftmost box designates this service management entity
particular to this system, which includes all system participants besides the end users
themselves. That is, the service management breakdown describes the groups
responsible for enabling the application, in this case WiNDCC. For the purpose of
supplying system critical inputs, state and local municipalities are included within the
service management category. Indicated by the arrows, the service management and
WiNDCC enablement exchange information in regards to the task of traffic delay
mitigation. The WiNDCC enablement represents the in car VANET enhancements,

protocols, system specifications, and definitions presented in this thesis. The in-vehicle

35

navigation device makes use of the information from both the service manager and
WiNDCC to instruct drivers of the most viable travel paths given the current vehicular

position and destination.

36

 

 

 

 

 

 

Tr ffl on s l n ntr I WiNDCQ
grvlce Management ENABLEMENT
- Geographical/1' apology Specific - Sensed/current Traffic Situations
""0 (Map) - Per link travel times
— Per link characteristics . Average speed
- Length/position l estimation
- Speed Limit . Link stoppages
. Known Traffic issues — Regionalized traffic
— Construction _ conditions
_ Event discharge — End to end travel times for
- Desired topology utilization various sources and
and traffic manipulation destinations
- Vehicular position awareness
(GPS)

 

 

 

 

 

 

ale

 

 

 

in Vehicle Navigation Device

 

 

 

 

Figure 3-2: Service management and WiNDCC data exchange

To better understand the possible information exchange between the service
management and WiNDCC system, examine Figure 3-2. In this diagram, the data
exchange is summarized and overall system interaction can be seen. Namely, the service
management entity is responsible for supplying the map data, free flow traffic times,
traffic events, and the positioning information needed in order to make WiNDCC and the
navigational aspect work. In return, the WiNDCC system can report traffic conditions
back to the service management layer for analysis and forecasting purposes.
Nevertheless, as will be seen in the mechanism description, the information WiNDCC
receives from the service management entity is important to the systems operational

goals.

37

3.2.2 WiNDCC Network Architecture

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Delay Sensing and Relevancy, Caching WiNDCC
Packet Generation and Forwarding ‘—' Application Layer
, , Functionality:
__Decfisron__ Send/Receive
, l ,
W'NDCC
Fast Path Message Cache and Carry Netxork Layer
Fonrvardrng Message Forwardin Functionality
DSRC Recommended MAC Protocol __
(802-11 asz) MAC/PHY
' Functionality
Physical Layer

 

 

 

Figure 3-3: WiNDCC network architecture

With regard to the traditional networking architecture used when describing
wireless systems, WiNDCC operation can also be discussed in this way. Figure 3-3
depicts this architecture. By viewing it, one realizes the research contributions made in
this thesis. From an application layer perspective, the primary purposes are to generate
delay messages and determine what to do when delay messages are received. The details
of these actions will be described in this chapter. At the network or routing layer, the two
forwarding mechanisms can be seen. The details of the two will be covered next, along
with an explanation of when they are used. However, as mentioned within the WiNDCC
problem specification, the fast forwarding specification is based upon [22], and the cache
and carry paradigm upon ideals form [27]. Additionally, note that when nodes receive
information from the MAC layer it is relayed directly to the application layer. That is, in
the WiNDCC system the network layer serves the application layer, not the other way

around. This is a result of the broadcast nature of system operation. Also in the

38

WiNDCC specification presented in this thesis, the IEEE and ASTM-adopted Dedicated

Short Range Communication (DSRC) recommended MAC layer protocol is used.

39

3.2.3 Architectural Summary

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

WiNDCC ENABLEMENT
Sent Delay Received Delay
, Messages Messages
Traffic Congestion
Control Service
Management: In Vehicle Navigation Device
Map and Topology _
Info "—" Overall Path Computation

 

 

 

 

 

 

 

v

Travel Decision

 

 

 

 

 

 

 

 

 

 

Figure 3-4: Overall system architectural summary

In summary, the overall system operation can be seen in Figure 3-4. In short, the
service management layer provides mapping information to WiNDCC and the navigation
device. In addition, WiNDCC supplies the information sensed from other enabled
vehicles to the navigation device, which then calculates the travel route based on this
information. WiNDCC is also responsible for sensing and relaying the information it
knows about the traffic network. Finally, the navigation entity outputs the next travel
decision to the driver based on the route it has calculated. To be examined as future
work, the WiNDCC system can also provide information to the service manager, for the

purpose of enhanced traffic monitoring and control.

3.3 WiNDCC Operational Assumption

In order for WiNDCC to operate under the premises described in this thesis, a few

assumptions or system inputs are needed. Firstly, as with all navigational and route

40

computation devices, the position of the equipped vehicle is vital to system operation and
performance. WiNDCC also uses position data for not only for route computation but for
overall protocol functionality as well. For instance, the system constantly measures a
vehicle’s current time spent in a link. Therefore, it is imperative that the system be able
to stamp the appropriate time in which a vehicle has entered a link. This sort of
functionality, along with a few other mechanism nuances, depends heavily on accurate
position data. As a consequence, for the remainder of this document, assume that

enabled vehicles are always position aware.

3.4 Path Computation Function

In the abovementioned system breakdown, it can be seen that the navigation device
or function is responsible for using the initial and learned information about the traffic
network to supply the travel decisions to drivers. In the WiNDCC system presented in
this thesis, the travel routes are computed using the following rationale.

With respect to the way in which vehicular navigation and route guidance systems
acquire the actual travel routes reported to users, a shortest path algorithm is equipped.
Particular to the mechanisms and system specifications for WiNDCC, the Dijkstra’s
shortest path algorithm is constantly invoked throughout travel to compute the guidance
messages reported to drivers. In order to use the algorithm according to the WiNDCC
mechanism, the traffic network first needs to be represented in graphical form, by
representing intersections as vertices, or nodes, and roadways as links, or edges. Link
costs are also utilized in order to judge the quality, effectiveness, or any other designer
specified quantity associated with links. The link costs associated with WiNDCC are the

travel times associated with each link. Initially, they are set to the optimal or free flow

41

travel times, so that vehicles always use these paths when no other knowledge has been
obtained about travel links. As a consequence, the broadcast and received delay
messages will pertain to the travel times of the vehicles sending them. Nevertheless,
these details will be discussed in the next section. With respect to other required inputs
to the algorithm, the source or current position of a vehicle is required, along with the
intended destination; however in regard to general algorithm specifications, a destination
is not required as the original algorithm computes routes to each graphical destination.
As a consequence, based on the indicated inputs, the algorithm provides a directed graph
as output that corresponds to the shortest paths associated with the traffic network. Here
[32], the authors present the Dijkstra’s algorithm, along with another search technique
called bidirectional A*, which will not be used in this work. However, the work does
discuss and analyze the ability to use the Dijkstra’s algorithm within vehicular navigation
contexts to find all paths between a source and destination. It can be seen that Dijkstra’s

is effectively able to compute the various paths within the road network.

42

 

Path Computation Procedure at Navigation/WiNDCC enabled node - 5'
pertaining to traffic topology T:

While( Vehicle i has not reached destination)
//Create directed graph G, in which Dijkstra 's algorithm will use to compute
//shortest path tree S (G is restricted such that u-turns are eliminated from
//next hop consideration)
For(Every link, j, in T)
If( Vehicle i has an Updated Delay Value ( UDV) for j ){
Vehicle i will place link j into G using UDV
}Else{
Vehicle i will place link j into G using Typical Delay
Value (TDV)
}
//Run Dijkstra's algorithm on G, given current position and destination, to
//compute S

//Vehicular navigation device associated with i will then determine its next

//travel decision based on S, its current position within T and the desired

//destination

 

 

 

Figure 3-5: Path computation module
In terms of the algorithmic description of the path computation process, Figure 3-5
is given. In it, the Typical Delay Values (TDV) are the delay values for any link under
optimal travel conditions, and Updated Delay values (UDV) are those learned from other
WiNDCC enabled devices. Therefore, if there is not any learned information about the

traffic topology, vehicles will use the theoretical best path.

43

3.5 WiNDCC Packet Contents

 

 

 

 

 

 

Reporting . .
Back Rep orting Front Reporting X Position Reporting
. Intersection Y Posrtron
Intersection
Senders Senders Front . . Senders Y
Back . Senders X Posrtron . .
. Intersection Posrtron
Intersection
. . Cache and Carry
Delay Time Time Stamp Identifier

 

 

 

 

 

Table 3-1: WiNDCC packet contents

The packets exchanged for WiNDCC operation are very simple in nature and will
be described in this section. In terms of the information that is needed for system
operation, it can be found within the packet contents. For a visual perspective of the
packet contents, examine Table 3-1.

To begin with, the first row of content deals with the positioning of the link being
reported by the packet. The reporting back and front fields combine to represent the road
in which the packet describes; while the reporting x and y designate the exact position of
the vehicle when reporting this data. The second row pertains to the same information,
but relating to the node sending the packet. In a subsequent section that describes
message forwarding, it will be seen the purpose of including this information within
WiNDCC packets. Nevertheless, these two rows of information will be the same, when
considering the packets being generated by nodes originating protocol messages.
However when the packet is being forwarded, the sender information is replaced by that
of the node forwarding the packet, corresponding to the reporting information. Finally,
the last row of data includes the actual delay information relating to the road segment,

which is identified in row one. In terms of the individual components, the delay time

44

field contains the delay value for the segment, and the time stamp equates to the moment
of time the extraction takes place. To be explained in the forwarding principles section,
the background identifier is a Boolean piece of data, which indicates the forwarding
status of a message.

By examining the abovementioned packet contents, some WiNDCC characteristics
can be noticed outright. To begin with, there is not any indication of which node has
originated the data packet, beyond the position data included in the first row. This is
because the WiNDCC system operates via a broadcast dissemination scheme, where the
originator of protocol information is negligible compared to the actual information itself.
Additionally, there is no destination information included in the header. However, it will
be seen in the forwarding section the traffic network regions in which packets are
destined within the WiNDCC framework. Therefore to understand the purpose of

WiNDCC packet data, consider the remaining system specification and description.

3.6 Delay Message Generation

In this section, details will be given pertaining to the way in which WiNDCC
enabled vehicular devices will generate the delay messages to be broadcast around the
network. With respect to this task, there are two operational modes. The first operational
mode works during times when travel links are congested, not completely stopped. The
second comes into play when links are stopped due to accidents or other traffic events.
Nevertheless, no matter the operational mode, a vehicle will only generate delay
messages about the link it is currently residing. That is, vehicles will not generate delay

messages about other links in the traffic topology. However, it is an acceptable part of

45

system operation for vehicles to forward messages about other links. This will be

described in the message forwarding sub section of this chapter.

46

3.6.1 Message Generation Based on Initial Congestion Indicator

 

R C I = (Time _ spent _ m _ lmk — Typical _ Delay _ Value)

 

Typical _ Delay _ Value

 

 

 

Figure 3-6: Calculation of RCI

During times when links are moving but could possibly be displaying congested
conditions, WiNDCC uses an Initial Congestion Indicator (ICI) to determine if
congestion is present. In other words, the ICI helps the system determine a definition for
congestion. Additionally, this definition is adjustable and can be a function of time or
other system aspects, according to the specifications set forth by system management.
Generally speaking, the ICI and Relative Congestion Index (RCI) are compared to
determine when it is appropriate to begin broadcasting information about a road link. To
clarify, the RC1 is 3 vehicles current time spent in a link, relative to the free flow travel
time or TDV described in the original path computation procedure. By utilizing this
quantity, a snapshot of the delay characteristic of a link can be gathered. The RC1
computation is found in Figure 3—6. As a consequence, the comparison of RC1 and ICI
allows system operators to determine how much traffic congestion to accept before
broadcasting messages via WiNDCC, which could potentially begin to redirect traffic.
That is, when the RC1 is greater than the 1C1, the condition for declaring traffic
congestion has been met. However, until this criterion has been met, it is unnecessary to
broadcast information about a link and the channel should remain clear. This concept
supports vehicles using the optimal paths when congestion is not present or is not above
the threshold determined by the ICI. For this study the ICI is the same for each link in

the entire traffic network. However in a study left for future work, it may prove to be

47

advantageous to attach various ICI values on a per link basis, to assist with meeting
network wide traffic goals determined by service management.

Now that the ICI concept has been discussed, it is now appropriate to describe
when the actual link delay times will be broadcast. As prescribed in [21, 29], an effective
strategy when implementing a dynamic route guidance system is to use the delay times
experienced by vehicles when they exit travel links, as link costs or references in route
computation. As a consequence and since the system uses actual or typical delay values
to compute routes, WiNDCC borrows this concept and has vehicles broadcast delay
information as they exit links; That is, during times of congestion or slowed links,
vehicles broadcast the delay it has experienced in that travel link. Additionally, other
logic is introduced to assist in minimizing the wireless channel usage and to assist in

delay notification and smoothing.

48

 

 

Link Exit Procedure at WiNDCC enabled node - 5' exiting Road Link-l:

//Vehicle i determines the total time it has spent in link I: tot_time
//By using tot_time and typical delay value for link I (TDV), vehicle i
//computes relative congestion index ( RC I - Figure 3-6 )
If( Vehicle i does not have an Updated Delay Value ( UDV) for link I)!
lf(RCI is greater than Initial Congestion Identifier (ICI) ){
Vehicle i Sends Delay Packet about link 1, indicating the tot_time.
Set UDV to tot_time
Return; l
[Else l

If( The vehicle i has received a delay message about I in last 20 seconds ){

Return;
}
tdiff = tot_time — UDV //Determine difi‘erence between
//tot_time and UDV
lf(tdifi < 0){ //Congestion could be improving
If(abs(tdiff)<20){
Return; //Not as sure if congestion improving

 

Figure 3—7: Link exit strategy

49

 

 

fink Exit Procedure at WiNDCC enabled node - 5' exiting Road Link-l:
(Continued)

Vehicle i Sends Delay Packet about link 1, indicating the tot_time.
Set UDV to tot_time

Exit

 

 

 

Figure 3-8: Link exit strategy (continued)

As a reference, the link exit broadcast strategy is described in Figure 3-7 and Figure
3-8. As previously mentioned, the ICI dictates when the broadcasting will begin or cease
for a certain link. As a consequence, the algorithm exits if the RC1 is not greater than the
ICI and the vehicle invoking the exit strategy has not already received an update for the
link. Then in instances when updates have been received, efforts are made to keep the
wireless channel free and minimally used, while also keeping the delay information fresh
within the network. To achieve this, a guard time is applied that disallows multiple
information originations within that time, in this case 20 seconds. That is, during times
of increasing congestion, messages will be generated no less then 20 seconds apart. Also,
delay broadcasts for values lower than those currently cached within a node will be
filtered. This is done to be sure the delay time is being adequately decreased about the
link, before broadcasting it. That is, to smooth the data as congestion is potentially being
relieved in a link, the reduced delay value must be at least 20 seconds less then the
current one being used in route computation in order to be broadcast. If not, the routine

exits and a message is not sent.

50

3.6.2 Delay Message Generation during Times of Event

 

Event Noti tcation Procedure at WiNDCC enabled node - ' residin in Road
Link-l:

//Vehicle i determines the total time it has spent in link I: tot_time
//E WT set based on delay reception about I or entry time into I
If( Vehcile i has not heard a delay message in E WT or has not exited l){
If( E WT has expired ) {
Set Event Backofl Timer (EBT)
l
//* *****EBT has expired
If( Vehicle i has not heard a delay message about 1)]

//Vehicle i Sends Delay Packet about link 1, indicating the tot_time

//every 20 seconds until it or another vehicle or itself moves out of l.

UDV = tot_time }

 

 

 

Figure 3-9: Event notification procedure
When links are stopped due to traffic collision, a vehicle malfunctioning on the
road, or any other unforeseen traffic event, WiNDCC instructs a vehicle near the event
region to send protocol messages, notifying the network of stopped traffic flow. The
logic for such activity is found in Figure 3-9.
In this procedure each stopped WiNDCC enabled node waits a predetermined

amount of time, in reference to the time when it has entered the link or received the last

51

delay message about it, before broadcasting any information. This is to be sure that an
event is taking place and that the link is not slowed but still moving. That is, the Event
Wait Time (EWT) is equal to the sum of the TDV of the link in question and the smallest
of the TDV values for the other links using the intersection, traveling in a perpendicular
direction. For example, if a vehicle is stopped in a link that is travelling north, its
WiNDCC enablement will wait a time period equal to the sum of the TDV for the lane it
is residing and the shorter TDV of the lanes traveling east and west into the intersection it
is using. Then, if a node in the lane hears a delay message about the link within this time
period, it stops waiting and will not send any delay messages about the link. In this case,
either the link is still moving or another vehicle has controlled the broadcast channel for
the purpose of event notification. If the latter is the case, this vehicle will dominate the
broadcast channel and deliver all messages about this event until it exits the link.

As previously mentioned, a vehicle will either wait for the EWT in reference to the
time when it has entered the link or, if it has received a delay notification about the road
in question, the time it has received the most recent delay message about the link. In both
cases and in terms of the event broadcast scheme in general, the most important aspect of
this notification is ensuring than an even has actually taken place and that only one
vehicle controls the broadcast channel. Therefore, as it can be seen in the algorithmic
description, a shorter wait time is applied after the EWT. This timer guarantees,
especially in the case of a group of vehicles who have received a delay message at the
same time and are waiting to broadcast an event message after waiting the EWT, that
only one vehicle sends information. That is, the Event Backoff Time (EBT) is simply the

reciprocal of a vehicle’s current distance from the previous intersection or back of the

52

link. By applying this time, the mechanism pledges to only allow one vehicle to report
the even that is happening. And as a consequence of the distance basis for this timer,
vehicles towards the front of the event area are favored for event notification.

Finally, it can be seen that the event message is re—sent by the EWT and EBT
designated vehicle every 20 seconds, with the updated amount of time this vehicle has
spent in the link. This is done to keep other vehicles from commenting on the status of
the link in question and to refresh the traffic information around the network, while not
clogging the wireless channel in an effort to do so. Once a vehicle'exits a link and

updates the information for the link at hand, the event notification status ceases.

3.7 WiNDCC Message Forwarding Algorithms

In the previous section, the delay message generation schemes utilized within the
WiNDCC system specification were discussed. Briefly stated, the framework generates
delay messages under two circumstances. The first classification is link exit, and the
second is during times of events. Also, it can be seen in their algorithmic descriptions
that attempts are made to maintain the health of the wireless channel while introducing
fresh information within the traffic network. Similarly, the WiNDCC forwarding
procedures are designed with the same principles in mind, forwarding fresh information
and doing so in a manner that uses the wireless communication channel effectively. In

the following sections, those schemes are introduced and described to the reader.

3.7 .1 Relevant Areas for Message Forwarding

According to the established design principles, WiNDCC is a completely

distributed, infrastructure free, traffic delay mitigation mechanism; therefore it is very

53

important, for wireless channel and overall mechanism competence, to forward messages
in an efficient manner. Obviously, an important aspect of reliable forwarding is the
forwarding scheme itself. However, an equally important question in relation to this task
is where within the traffic network the messages are being forwarded. That is, when
delay messages are generated, it is in the best interest of the wireless channel and system
goals for them to be forwarded to the areas of the traffic topology that can use them, not
to areas that the information is irrelevant. The discussion about WiNDCC message
forwarding will begin with this idea in mind, with a description of geographic
information relevancy. Additionally, in [25] two definitions are introduced that relate to
describing this situation. The first is zone of relevance (ZOR), which is the set of
geographic criteria a node must satisfy in order for a message to be relevant to it; the
second is zone of forwarding (ZOF), which is the set of geographic criteria a node must
satisfy in order to forward a message. One will find various mentioning of these terms

within the forwarding description.

54

 

5

cm»

i

m

.. m
lb-Ji—g—H—ALJ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

”‘7"? r“: rm F E

 

 

 

 

 

 

 

 

 

 

 

 

”DIEM If

it

Figure 3-10: ZOR for info from darkened link, marked with stripes

 

 

 

Considering the message generation paradigm, discussed in the abovementioned
sections for link exit or event notification, the generated information is relevant to a
particular area within the traffic environment. That is, the ZOR is a defined set of links,
as it relates to the messages generated by nodes in a particular roadway within the
topology. Simply stated, the relevant links are those that could potentially be input for
the link in question. For an example, consider Figure 3-10 and delay messages originated
form the darkened incident link. According to the WiNDCC paradigm, and intuitive
driving logic, the links marked with stripes are potential input roads for the darkened link
and vehicles using them would need the information about this link. Also according to
intuitive driving logic, the links closest to the darkened one would need the information
before the ones farther away. A verbal definition, of the ZOR for messages originating
from a particular link, is as follows. That is, the ZOR for a roadway includes all roads

parallel to the one in question, but opposite in direction, and each link that serves as

55

eventual input to it. To be examined as future work and particular to an individual road
network, the depth or distance from the incident link associated with a ZOR should be
determined particular to the topology in question. It will be shown in the next section
how the ZOR associated with links within the WiNDCC framework is used within the

forwarding mechanism.

56

 

 

 

 

 

Figure 3-1 1: ZOR for info from striped links, darkened

Also, considered within the WiNDCC framework is the question of what
information is relevant to a traveling vehicle. Contrary to the previous issue, this one
deals with information about the potential links a vehicle may travel, not the roads that
serve as input to an exact one. Simply stated, the problem and solution are an inversion
of the one mentioned earlier and the following statements are made with respect to this
new vantage point. Therefore, the ZOR is a single link, as opposed to the previous case
where the ZOR was a group of links. And, the incident area is considered to be a group
of links, the prospective roadways a vehicle may use. For a visual aid, consider Figure
3—11. For a vehicle traveling in the darkened link, the messages generated about the
striped links are relevant. A verbal definition, for the incident area according to particular
link, is as follows. That is, the incident area for a roadway includes all roads parallel to
the one in question, but opposite in direction, and each link that serves as eventual output

from it. Additionally, to be examined as future work, the size or distance associated with

57

the incident area will be left as future work and is particular to the traffic network
topology at hand.

The ideas presented in this section are important, in terms of the WiNDCC
forwarding operations. It will be revealed in the next section the role of information
relevancy within this framework. As an additional note, the information has been

presented in this order to assist the reader in understanding the schematics.

3.7.2 Receive Module: Forwarding Decision

An appropriate place, to begin describing the interworking of the WiNDCC
forwarding module, is at the receive module. By reexamining the wireless networking
architecture found in Figure 3-3, one can see that the receive module makes a decision
about the forwarding status of a packet. When considering the nature of WiNDCC
operation, it is clear why this is so. That is, the only time a device will forward a piece of
information is if it receives it from another node, via the broadcast communication
channel equipped for this framework. The receive module will be explained here, while

the details of the forwarding modules themselves will be left for the next sections.

58

 

 

Receive/Forward Decision Module at WiNDCC enabled node - iI residing in
Road Link-l:

//Receive delay packet from MAC layer about link j: packet

//Be sure information is fresher than that cached for 1

//Record all relevant information from packet

//Set Data Expiration Time

If( link I is within the ZOR for j )or( I and j are the same){
//Mark packet for fast path forwarding
F ast_Path_F orwa rd( packet )
[else]
//Mark packet as cache and carry packet
C ache__and_C a rry_F o rwa rd( packet )
l
//After this, a packet has been labeled as background
If( Packet is labeled as a background packet ){
//Cancel current forwarding choice

C ache_and_C arry_F orward( packet )

 

Figure 3-12: Logic for receive module

 

 

Data _ Expiration _ Time = Time _ Stamp +
2 * (Delay _ Time + RC1 _ for _ packet * Delay _ Time)

 

Figure 3-13: DET computation

59

 

 

The receive module logic can be plainly explained, when considering the ideas
presented within the WiNDCC general algorithmic description and the previous section,
3.7.1. An algorithmic perspective for it can be found in Figure 3-12. First, if the
received information is fresher than what the node already has for the indicated link, then
the procedure logs the relevant information found within the packet and determines the
Data Expiration Time (DET). The DET is a quantity describing how long it is
permissible for a device to forward or use a piece of data in route computation. It is
based upon the reported delay value, the time stamp for which the data was recorded, and
the TDV for the link. That is, the TDV and the recorded delay value are used to compute
an RC] and DET for the message. In essence, the term is designed such that information
from packets reporting a high RCI remains in the network longer. Its computation can be
found in Figure 3-13.

Then, if a vehicle is within the ZOR for a protocol message about a link, it marks
this packet for the fast path message forwarding procedure found within the routing layer
of the network architecture. It will also perform this operation if the receiving vehicle
resides within the link in which the message is generated That is, in reference to the
scenario depicted in Figure 3-10, a vehicle inside of any highlighted roadways will mark
a packet for the fast path message forwarding mechanism, if it is generated within the
darkened link. Otherwise, if a vehicle that is not inside the ZOR receives the packet, the
data is marked as cache and carry; now, the corresponding forwarding principles are
ready to be invoked. Additionally, logic is found within the receive module for the

reception of a cache and carry packet, which will be explained later.

60

Although simple in nature, the receive module plays an important role in
WiNDCC. Next, the forwarding modules that combine to create the WiNDCC network

layer will be discussed.

61

3.7.3 Fast Path Message Forwarding

 

(25)
Distance _ From _ Sender

Seconds

 

Forward _ Attempt _ Time =

 

 

 

Figure 3-14: FAT definition

The purpose of the fast path message forwarding paradigm is straightforward and is
as follows. Namely, the mechanism aims to get the information to the ZOR for the
reported link as fast as possible, while maintaining as much integrity as possible over the
wireless channel. Therefore as previously mentioned in the related works section, an idea
from the mechanism described in [22] is used to assist in this process. In short, the
mechanism uses a distance based backoff scheme that expeditiously moves messages as
away from an origination node. This is done by applying the distance based backoff time
of Figure 2-1, upon packet reception. As a consequence, that gives vehicular devices
farther away from the sending node forwarding priority. Then by taking advantage of the
broadcast medium in which all nodes in radio range of a transmission hear it, other
vehicles waiting to forward this message cancel this operation. Therefore, as a function
of the underlying network topology, this allows messages to move as far away as possible
while minimizing the amount of wireless transmissions.

WiNDCC combines this concept with the ZOR to create the backbone of its fast
forwarding function. However, the Forward Attempt Time (FAT) used for this
mechanism is different from the one shown in Figure 2-1, but it serves the same purpose.
The FAT definition is found in Figure 3-14 and it uses the sender information described

in the packet contents, section 3.5. By viewing it, one can see that vehicles closer to the

62

sender wait a longer time to forward packets, as described in [22]. This promotes the

overall goal of fast path message forwarding, to move messages far away fast.

63

 

Fast Forwarding Module at WiNDCC enabled node — i:

//Packet has already been identified and passed into the function
//Set FAT
If (FAT has expired before hearing message reply ){

F o rwa rd_Packet( )

}

 

 

 

Figure 3-15: Fast forwarding logic

The fast path message forwarding scheme is described in Figure 3-15. In summary,
anytime a vehicle receives a packet for which it is among the ZOR and the fast path
forwarding routine is invoked, the FAT is set and the vehicle waits to hear a reply for the
message. Then, if it does not hear a reply before the FAT expires, it forwards the delay
notification reply. To conclude the fast forwarding process, when a vehicle sends a reply
message and does not hear it rebroadcast from another node within 5 seconds, the fast
forwarding for that packet stops and the network is said to partitioned in that
geographical area. 5 seconds is used because it describes the longest forward time
allowed by the FAT, assuming vehicles stop around 6 meters from one another. By
utilizing this principle, a message is able to traverse as many of the striped links in Figure
3-10 as possible, until the network is partitioned. Two schemes used to counter the

effects of a partitioned vehicular network are shown in the final sections of this chapter.

64

3.7 .4 Fast Path Message Forwarding with Partition Bridging

To deal with partitioning within the traffic network, the fast forwarding algorithm
may be used in a mode offering partition bridging. This mode is very simple and will be
described in this section.

As a basis for this algorithmic nuance, [29] is referenced and the dissemination
interval from it is used, Figure 2-2. In WiNDCC, this term will be called the Adaptive
Dissemination Interval (ADI). Given R, k, V], and v2 as described within the term
definition, a WiNDCC enabled vehicle can calculate the maximum transmission interval
needed to inform passing vehicles of any information it has. This term is used in the
partition bridging addition to the fast path message forwarding algorithm in the following
manner. That is, for a vehicle that has not heard a retransmission of a reply message it
has sent, it rebroadcasts it at an interval less than the ADI to try and bridge the partition
in the network. In terms of the ADI computation, the quantity v] + v2 is equal to the sum
of the forwarding vehicles velocity and the speed limit of the roadway in the opposite
direction. This is because WiNDCC does not exchange velocity information. Therefore,
a node has no knowledge of the velocity in the opposite direction; so it uses the speed
limit for that link. Upon reception by a vehicle within the link of the forwarding vehicle
or the ZOR for the forwarded message, the fast forwarding algorithm is then invoked by
the receiving node. That is, the previously discussed receive module logic is adhered to.

When this mechanism is used, a packet will live in the network as long as the DET
constraint is valid. As a consequence, the partition bridging allows a packet to move as
far as possible, by forwarding it at the edge of a partition until it hears a reply that it has

been received by another device.

65

3.7.5 Cache and Carry Message Forwarding

The final subcomponent of the WiNDCC network layer is the cache and carry
forwarding mechanism. As was mentioned within the related work section, several
VANET oriented routing mechanisms sometimes use a cache and carry, or store and
forward, approach to forwarding packets [26-28]. Like those works, WiNDCC also
incorporates a store and forward methodology to forwarding packet. As previously
mentioned, the purpose of this activity within the WiNDCC framework is to assist in
areas where the traffic network is partitioned, and messages are unable to effectively
traverse the network beyond this point of partitioning by way of the fast forwarding
method. The most effective way, to begin describing the operation of the cache and
carry paradigm, is by reexamining the above mentioned discussion about information
relevancy.

By reconsidering the receive module logic, it can be seen that when a message is
generated or forwarded about a certain link and a receiving vehicle is not within the ZOR
for the reported link, the function marks the packet for cache and carry; then it calls the
routine. Simply stated, the cache and carry mechanism will rebroadcast certain cached
information, according to its current position within the topology. The rebroadcasted
information is intended for vehicles traveling in links that are traveling in the opposite
direction and are using the intersection that is directly in the rear of the broadcasting
vehicle.

By viewing Figure 3-1 1, the abovementioned concepts and the overall operation of
the cache and carry algorithm can be understood. Consider the darkened and any vehicle

traveling within it. As previously mentioned, the information about the striped links is

66

relevant to this vehicle, because they are the potential links the vehicle could travel. An
additional nuance of this scenario is as follows; it can be seen that the darkened link is
within the ZOR for each of the striped links. However due to the partitioning within the
network, information may not make it from the striped links to the darkened one;
although, this information could be useful to any of the traveling vehicles using the
darkened roadway. As a consequence and according to the pictured example, the cache
and carry procedure instructs vehicles to broadcast the cache and carry information they

have learned about the striped links, when they are in the link beside the darkened one.

67

 

Cache and Car_ry Forwarding Module at WiNDCC enabled node - 5'
entering link 1':

//Determine cached information regarding potential incident links for the road
//traveling in the opposite direction

//Set randomized start time for each potential piece of data

If(DET for a broadcasted message has not expired )or( i has not received
fresher info about a link being broadcast){

//Broadcast potential incident link information every ADI

 

 

 

Figure 3-16: Cache and carry functionality

The details of this procedure are outlined in Figure 3-16. In specific, at the moment
a vehicle enters a new link, it calls the cache and carry function to determine if it has any
relevant information stored that could be of use to a vehicle using the lane opposite of it.
In the event that it does, a random timer is for each piece of data the vehicle may
broadcast. This random value is selected such that the vehicle is able to move away from
the intersection before broadcasting information, so that the communication channel can
remain as clear as possible for the link exit delay generation activities. Then, until the
DET expires for the data or fresher information about the information is received, then

the information is broadcast according to the ADI.

68

Chapter 4: Experimental Setup

In this chapter, a discussion of the simulation setup is given. Performance of
WiNDCC was evaluated using the ns-2 network simulator version 2.30. In terms of its
high level operation, Ns-2 is an event-driven C++ and TCL language based network
simulator. Particular to its usage within industrial and research realms, it is open source
and can be extended to implement many wired and wireless network protocols and
scenarios. Additionally, the simulator comes with various components pre installed.
Currently ns-2 does not support vehicular or traffic network oriented simulation
environments; therefore, a macro vehicular simulator was designed and implemented
using ns-2 to support the type of experiments depicted in this thesis. Also in this chapter,

other aspects of the experimental setup are discussed.

4.1 Macro Vehicular Simulator

Here, a description will be given of the macro vehicular simulator used as a testbed
for the WiNDCC system. To clarify, the term macro is used because the simulator is not
intended to measure the low level interaction between vehicles. Instead, the design is
meant to measure the overall movement of vehicles and track the end to end and per link
travel delay associated with the simulated nodes. Also according to the macro mobility
nature of the simulator, vehicles are able to stop and accelerate instantaneously.
Nevertheless, in an effort to gain a perspective on WiNDCC algorithmic relevance and
performance, the traffic network implemented by the simulator has roadways with one

lane of travel in each direction and implements traffic light logic at intersections. As

69

future work, WiNDCC should be analyzed with a more realistic vehicular simulator.
However, to gather preliminary results, the macro vehicular simulator serves its purpose.

In terms of the workload and time required to complete this thesis, the macro
vehicular simulator design, implementation, and intense debugging constituted a majority
of the initial effort. Nevertheless, in order to begin development and testing of the
WiNDCC system, a way to test its effectiveness had to be obtained. As a consequence, a
large portion of the macro vehicular simulator was developed before the start of
WiNDCC design.

Particular to the vehicular simulator design, a few components are responsible for
its implementation; some of them are already built into the ns-2 network simulator. In
terms of the programming language and ns-2 usage in general, most exterior and pre
installed components are written in C++. However, the TCL scripting language is
involved with inputting initial simulator state at runtime, allowing interaction between
unrelated simulator objects, low layer simulator functionality. Nevertheless, the system

description is as follows.

4.1.1 Pre-installed Ns-2 Dependencies

In ns-2, there are functions that can be called to control nodal movements within
the simulated environment. In terms of the macro vehicular simulator operation, these
functions are at the core of its functionality and are used to make the nodes or vehicles
move. The functions are a component of the ns-2 preinstalled mobilenode object. Also,
anything dealing with the position or velocity of a node is enabled by invoking its
mobilenode routines. It will be seen in the following descriptions the usage of

mobilenode routines.

70

Especially characteristic to network protocols, timing is a critical component of
mechanism design and operation. As a consequence, ns-2 uses timers to allow protocol
designers a way to schedule events during the simulation time. In terms of usage, a timer
is a function that allows the designer to specify when it will expire and the corresponding
code that will be ran at this time. Depending on the application or simulation operation, a
programmer can vary the expiration time as well as disable the timer. As with traditional
networking protocols, the macro vehicular simulator and WiNDCC implementation is

highly dependant on the ns-2 timer capabilities.

4.1.2 Input Simulation Script

Here, insight will be given as to the inputs for traffic simulation via the macro
vehicular simulator. Since the macro vehicular simulator implements vehicles traveling
within a specific traffic network topology, the physical characteristics of the roadway
network must be first inputted into the simulation space so that each vehicle can be aware
of it. Along with the intersections in which they are connected, the x and y coordinates
of all simulated links are fed into the simulation space with the input or configuration
script. As a consequence, the graphical representation of the traffic topology, to be used
within the vehicular route computation module, is obtained. Additionally, the speed limit
and length of the segments are given to complete the traffic road link topology input.

In addition, the traffic light information is given in the configuration script. In
accordance with the type of traffic lights used within the experimental setup, lights are
green, yellow, or red. The timing for each traffic light state is given as well as the
simulation time in which the traffic light will begin to operate. Of course, the logic for

this device is the same as what is seen in actual stoplight implementations. That is, the

71

light goes from yellow to red, then from red to green. The process continuously repeats
itself, according to the timer specifications which enable it.

Finally, the information about each simulated vehicle is provided in the initial
simulation script. This information includes the x and y position of the node and other
simulator and WiNDCC specific variable initiations. Also the type of traffic decision
module the vehicle will use is set. The options for this model are random, best path, and
WiNDCC assisted. The random module instructs a vehicle to make a random decision at
each traffic light; a best path vehicle always uses the theoretical best path for travel, and
the WiNDCC assisted vehicles use the logic described for WiNDCC. For the last two
cases, the destination is also set for a vehicle. Lastly, the start time for a vehicle is

prescribed as input.

4.1.3 Topology Interaction and Position Awareness

In terms of a vehicle traveling within the simulation environment, it must react and
be aware of the topology. This functionality is implemented by three timers residing
within each vehicle.

The first timer is the position awareness and intersection behavior function. For
each node, this timer expires rapidly during the simulation time. This is so that vehicles
always have an accurate understanding of their position. As will be seen in the next
section, the sanity of other modules also depends on the vehicle having an accurate
understanding of its position at all times. Also, according to the WiNDCC application
and network layer goals, position information is vital to system operation. In addition,

this function also calls the mobilenode routines that move the node when a node enters

72

and exits an intersection. It also, upon entry into a new link, sets the state variables
needed for simulator operation and WiNDCC functionality.

Another timer assisting with topology interaction allows vehicles to be aware of the
state of traffic lights as they approach them. For the vehicle in the front of a lane, the
traffic light timer instructs this vehicle to periodically get the light status from the traffic
light object serving it. Also, included within the traffic light timer are instructions about
where and when to stop due to the traffic light state.

Finally, as mentioned in section 3.4, WiNDCC uses the Dijkstra’s shortest path
algorithm to compute travel paths. This module interacts with the topology by using the
inputted road link profile. This profile, along with the current position and destination of
the node, is used by the described route computation module to dictate a vehicles travel
decisions. If WiNDCC is enabled, then the information learned about the traffic topology
can also be used as input to this process. If not and a vehicle is a best path traveler, the

theoretical travel times are used.

4.1.4 Vehicular Interaction

The last module responsible for the macro vehicular simulator operation is the
vehicle reaction timer. In specific, this timer is responsible for vehicle to vehicle
interaction. Like the position awareness timer, this timer expires constantly and uses the
position of not only the vehicle calling the function but the position of the vehicle
immediately in front of it. The function instructs a vehicle of when and where to stop due
to a stopped leading vehicle, and it also tells the vehicle when to proceed after the leading

vehicle resumes travel. In addition, the module also adjusts a vehicles traveling velocity

73

according to that of the front vehicle. This module is important to guaranteeing vehicular

sanity throughout the simulation process.

4.2 WiNDCC Implementation

According to the specifications set forth in chapter 3, each aspect of the WiNDCC
system is implemented within the simulated vehicles. The system uses a built in ns-2
module called the pingagent. This skeleton object is simply equipped with a send and
receive module that allows interaction with the specified MAC layer. Most designers use
this space for protocol development on the ns-2 system. According to the WiNDCC
design principles, both network and application layer functionality is implemented in this
object. As previously mentioned, several timers, C++ functions, and TCL backbone
interaction calls are used to implement the system. The algorithms have been described

in chapter 3 and are tested for effectiveness in the following chapters.

4.3 External Components

With regard to the results that will be presented in the following chapters, the act of
getting them into a usable form was as important as the actual results themselves. That
is, within the macro vehicular simulator and WiNDCC implementation code, there are
several cout statements that allow the designer to understand what and when certain
events are happening within the simulation time. These output statements are analyzed to
produce the results. However before they can be understood, the trace file that contains
all of the generated output statements produced within the simulation must be parsed and
put into a format that is conducive to plotting. Due to the extreme amount of data

presented during each simulation run, this was a very important aspect of the end to end

74

process associated with simulator design and experimental evaluation. To perform this
task, several scripts were written and used. The involved languages were awk and sed,
along with additional shell scripts used to creatively call the various programs. By using
the two scripting paradigms, routines were created that were responsible for identifying,
extracting, and tabulating each performance metric. In summary, the external scripting

components are vital to gathering the performance metrics the reader will see.

4.4 Commonalities between Experimental Scenarios

Here, some insight will be given into the experimental scenarios that will be
described in the following chapters. The settings and characteristics that are shared

between each experimental setup are found below.

75

4.4.1 Experimental Topology and Characteristics

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

__ Desi. " T
12
6030 l—-——* ’ I 2 l . F 4 —l
16 : 2 17
.1.. r- in
13
5020 ‘ 5 141 , § ’ 11
$ 18L_8
- Traffic Light ’ E
tfit - Lane ID
3; Flow Start 5 g
i=>Travel Path identifier 1 0 ‘
F1 l E'wii ”-
19
3000 .l:-— m j. , J. - 3——T
1 ‘ ->‘ .1“ 1
F3
QB} IN
3,000 4,010 5,020 6,030

 

 

Figure 4-1: Simulated traffic network with relevant markings
In terms of the simulation scenarios used to test the effectiveness of the WiNDCC
system, they each use the same traffic network topology and it can be found in Figure
4-1. In this figure, the intersections marked 1 through 13 use the abovementioned traffic
light logic. As previously mentioned, the topological, traffic light, and geographical
aspects of this topology are enabled with the functions and modules mentioned. A
general perspective regarding this topology and the commonalities between the

experiments is as follows.

76

 

Traffic Network Characteristic Setting

Per-Link Speed Limit 20 m/s:
Random value selected between 16.75 and 23.25
m/s

 

 

Traffic Light Timing Road from 30 to 23:
NS Green: 505
EW Green: 1005
All others:
NS Green: 535
EW Green: 505
All:
Yellow: 35

 

Segment Lengths Shorter Segments:
1000 m
Longer Segment:
2010 m

 

 

 

 

Table 4-1: Traffic network parameters

As for the experiments, there are three different classifications designed to test the
various aspects of the WiNDCC system. However, the details of each experiment will be
left for the individual chapters in which the results are presented. Nevertheless, there are
certain traffic network characteristics that will be similar to all experiments. Some are
found in Table 4-1; they correspond to the speed limit, traffic light timing, and segment
lengths associated with the traffic network. Additionally, there are other markings on this
figure that will relate to each of the experimental setups.

To begin with, the shaded squares on the map represent the origination place for the
three flows of vehicles that will be used in the experiments and the destination. In the
following chapters, the word flow refers to a group of vehicles sharing a common starting
and destination point, one of the highlighted origination squares marked 1, 2, or 3 and the
highlighted destination. Nevertheless, the box towards the top of the topology denotes

the common destination in which vehicles from all flows will look to arrive.

77

In terms of finding the traffic network wide TDV values needed for route
computation, a simulation study was deployed. After running some test scenarios with
minimal traffic and the three flows operating individually, it could be seen that the
average travel time value for each link was very close to the approximate travel time for a
link plus the red time for the traffic light serving the link. Therefore, these quantities are
used for the TDV of each roadway. As a consequence the highlighted arrows, which
extend beyond each of the flow origination links, represent the theoretical best path that a
vehicle will take based on the calculated TDV values and the destination intersection.
This determination was made using the path computation procedure, Figure 3-5, with the
TDV for each link used as the cost. Consequently, if a vehicle from one of the
designated flows travels from source to destination based on the best path logic, it will
always take the path indicated by the arrows. Looking ahead to some of the experiments,
the input traffic rate for the indicated flows will be varied.

It will also be seen during the presentation of the results, some metrics are
presented with respect to the overall performance of the WiNDCC enabled network, and
others will be in terms of the individual drivers using WiNDCC. This perspective can be
realized by reexamining the architectural walkthrough presented in section 3.2. The
service manager is interested in overall mechanism performance, and any vehicle using
WiNDCC is concerned with how the system performs subject to its individual travel
experience. Nevertheless, to assist with some to the overall system performance metrics,
each of the lanes potentially used during the simulation time are labeled with numbers.
This will help identify them, as results pertaining to their utilization and individual delay

times are examined.

78

4.4.2 Wireless Networking

In terms of the wireless networking specifications, the IEEE and ASTM-adopted
Dedicated Short Range Communication (DSRC) recommended MAC layer protocol is
used for each experiment. This protocol is the familiar 802.1 1 MAC layer specification
operating in the distributed, base station-less, mode. In terms of the transmission and
interference ranges particular to the ns-2 implementation of 802.11, all nodes use the
preset values of 250m and 550m range respectively. Therefore, in terms of the ADI used
in WiNDCC operation, a slight change must be considered in regard to the ns-2
implementation of the formula. In specific, the authors of [29] assume that a nodes
interference range is equal to two times its transmission range, hence the 2R found within
the numerator of Figure 2-2. However, in the ns-2 implementation the interference range
is slightly more than this value. Therefore when a vehicle is using the ADI within the
below mentioned experiments, the 2R found within the numerator of the computation is

replaced by 550.

79

Chapter 5: WiNDCC Performance for Handling Traffic

Congestion

In this chapter, the performance of the WiNDCC system will be presented as it
relates to congestion within the traffic network. The simulations used in this chapter do
not include any traffic events, only the three abovementioned flows with varying traffic
input rates. With respect to the algorithms, the link exit logic discussed in section 3.6.1 is
responsible for generating the delay messages. The performance due to traffic events or

link stoppages is found within the next chapter.

80

5.1 Simulation Setup

 

 

 

 

 

__ Dest. " T
12
6030 l _ i J. g : r 4__i
16 z 17
_ "1 5 2 F2 E‘ '— 93"
5020 14 13
l - jI ., 11

 

 

 

 

 

 

 

E. Traffic Light
## - Lane ID

f: Flow Start
r:'>Travel Path Identifier

 

 

 

 

 

 

m @211;
5
m

 

 

-—l—| ml—-l——'°~ 41313331 N
ll:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

F1
”OOPn i .L '2 3-—-l
1- ' —4» .1: 1
F3
5E: IN
3,000 4,010 5,020 6,030

 

 

Figure 5-1: Simulated traffic network with relevant markings
As previously seen in section 4.4, the topology used for the traffic congestion
oriented simulations is found in Figure 5-1 and operates subject to the specifications
given in Table 4-1. Also, the networking settings for the layers operating below the

WiNDCC implementation can be found there.

81

 

| High Medium | Low
I .5 Vehicles/Second .167 Vehicles/Second I .l Vehicles/Second

 

 

 

 

Table 5-1: Vehicular input rates

 

Flow ID Number of Vehicles Flow Start Time

 

 

 

l 200 75 s
2 1 80 6508
3 200 4508

 

 

 

 

 

Table 5-2: Vehicular flow specifications

The purpose of the experiments is to determine how well WiNDCC is able to clear
up the traffic congestion caused by the three specified input flows, with varying traffic
input rates and 100% WiNDCC enablement. Simulations are performed with three traffic
input rates, which are denoted by the terms high, medium, and low. To clarify, the traffic
input rate for a particular simulation run applies to all flows within the simulated
atmosphere and are described in Table 5-1. Also, there is other relevant information
relating to the three vehicular flows. This information can be found in Table 5-2 and
relates to the amount of simulated vehicles in each flow and the simulation time in which
the flow becomes operational. Now, it can be understood the three experimental setups

used to gather the results for this chapter.

5.2 User Oriented Performance Metrics

Although the per vehicle end to end travel time and distance are certainly important
quantities to the system operator, the results are more user driven and are presented
within this section. The results include the average distance and delay, along with

distributions for both quantities. Also, another result is plotted that highlights the delay

82

vs. distance tradeoff associated with traffic congestion mitigation, subject to the
arguments presented in section 1.1.1.

In addition, to avoid redundancy while presenting the results, the majority of the
findings will be in terms of the high traffic input rate, while considering WiNDCC
without partition bridging. Additionally, with regard to the WiNDCC system quantity of
ICI, a value of .25 is used for the initial results. Then, results will be shown that depict

the effects of partition bridging, varying traffic input rates, and various ICI values.

5.2.1 Travel Delay Improvement

The WiNDCC overall system goals, as described in Chapter 1, relate to travel delay
mitigation. Therefore, the first result will deal with the average end to end travel delay
mitigation. As previously mentioned, these experiments use the high traffic input value
and an ICI value of .25. The primary comparisons are made between No Traffic

Congestion Control (NTCC) and WiNDCC.

83

 

 

1400

1 200

A
O
O
O

l NTCC - All
Flows

Avg. Travel Delay (3)
on
O
O

8 0)
o 8
41* I

200 —

 

 

 

Ove Flow 1 Flow 2
Set of Vehicles

 

 

 

Figure 5-2: Travel delay benefits, highly congested Uaffic network

The average end to end travel delay can be found in Figure 5-2; in terms of the plot
axes, the x axis represents the set of vehicles being described and the y axis denotes the
average travel delay. A vehicles delay value corresponds to the time when it leaves the
first intersection it encounters minus the time when it enters intersection 3. To clarify,
the data series and results description is as follows.

The first series (NTCC — Single Flow) represents the single flow experiments,
when only the indicated flow is residing in the traffic network and the travel is dictated
by the best case delay numbers. These data points represent the best case travel operation
for that flow, since it is the only one using the network. In addition, when considering
the single flow data point within the overall vehicle breakdown, this corresponds to all

simulated vehicles when their respective flow inhabits the traffic network alone. It can

84

be clearly seen that the average delay for this data series is much lower than the others,
on an overall and per flow basis, which is to be expected.

The second series (NTCC — All Flows) corresponds to when all flows are operating
in the network at the same time and the travel is dictated only by the best case delay
numbers. That is, the series considers all flows using the theoretical best paths as marked
in Figure 4-1. As one can see, the average delay values associated with this series are
much higher than the NTCC alone, on an overall and per flow basis. This is a
straightforward result of the increased traffic along the links in which multiple flows
share.

Finally, the last series indicates the WiNDCC enabled traffic congestion mitigation
that is applied to the scenario. It can be clearly seen that by using WiNDCC, the
accumulated traffic delay due to all flows being present in the traffic environment is
reduced. In other words, after congestion is detected in the traffic network and vehicles
begin to use the other travel paths to reach the destination. That is the goal of the
WiNDCC system and it is being achieved by way of the designed application and

network layer protocols, combined with the route computation process.

85

 

 

 

 

Cl NTCC - Single Flow

I NTCC - All Flows
WiNDCC - All Flows

 

\\\\\\\\V\\\\\\\\\\\\\\\\\\\\\\\\\N

comm - cccm

   

occm - covm

§m-comm

comm - ccom

ocom-cccp

coop -ocop

 

§

    

och .8:

. ccvw-ccmp
ss\\\\\\\\\\§

   

comp -ocow

  

s\\\\\\\s
oooToow

§§

  

ccc-oco

 

coo-ccv

 

 

 

ccv-ocm

 

n|._ 8~-8o

 

 

60

50

u22...o> .0 ax.

 

Delay Range (3)

 

 

 

 

 

 

 

Cl NTCC - Single Flow

I NTCC - All Flows

  

cccm-ccop

WiNDCC - All Flows

ooow -ocop

   

§\\\\\k\\\\\\5

 

  

89-83
.\\\\\\\x

 

83-8w.
.8368?
.8258

.8m-o8

 

 

 

ccc-co.v

 

ccv-ccm

ccm-ooo

 

Figure 5-3: Overall travel delay distribution, highly congested traffic network
60

 

O 0 0
4. 3 2

3.0.:o> .0 .x.

1

 

Delay Range (s)

 

Figure 5-4: Flow 1 travel delay distribution, highly congested traffic network

86

 

 

 

 

El NTCC - Single Flow

1

 

I NTCC - All Flows
WiNDCC - All Flows

      

 

l
l
l
l
l
l

   

S\\\\\\\\\\\\.

\\\\\\\\

  

\\\\\\\\\\\\\\\\\\\\\§

  

 

 

 

 

 

 

 

u0.2...0> .0 .x.

 

oomm-coom

ccom - com.

com. -coc.

coo. -co...

co: -com.

Delay Range (s)

ocm.-coo.

coo. - coo

ccc-cco

occ-ccv

ocv-com

com - coo

 

 

 

 

 

 

 

 

    

 

  

      

 

 

 

 

m i - -
W cccm - occm
a l I

m m cocm - cocm
fi w -

.m m m m 88. - Sam
I. e I t

d l I l

w .m. M A. 8mm - 88
9%». S A C i

g . . m

m m m N ooom - cow.
w. m m m

We a I a cow. - coo.
..m i 89 - 83
n,

o

.w co: - com.
um s\\\\\\.

.3... 8m. - 89
d .\\\\\\\.

M. coo. - com
d s\\\\s

M 8m - 8m

W“ s\\\\\\\\\\\\\\\\\\\\\\

n _ ....................... s o8 - 8e
2 ...... -

nwU cov . com
H

: 8m - 8o
6 q a 4i 4i .— _

5 0 0 0 0 0 0 0

m mi. N 8 6 4 2

.WS 3.0_5> .0 .x.

F F i l

 

Delay Range (s)

 

 

 

 

Figure 5-6: Flow 3 travel delay distribution, highly congested traffic network

87

Another result that highlights the user oriented delay mitigation capabilities of
WiNDCC is the end to end delay distribution. From this perspective, the recorded delay
values used to compute the abovementioned averages can be better visualized. The
overall and per flow delay distributions can be found in Figure 5-3 through Figure 56
On the x axis is the delay categories and the y contains the percentage of vehicles arriving
during that breakdown. Also, the data series relate to the same quantities as previously
mentioned.

' By viewing the results, it can be seen that the WiNDCC system improves the delay
distribution on an overall and per flow basis, with respect to the NTCC all flows case. In
specific, WiNDCC moves the delay distribution closer to the left in comparison to the
congested case, indicating that vehicles are able to avoid the longer delay times
associated with using the traffic network without the mechanisms in place. Additionally,
the NTCC for the single flow cases is shown to give the reader an understanding of the

distribution under the best case operation.

5.2.2 Travel Distance Degradation

As mentioned within section 1.1.1, in most cases delay mitigation results in the
assisted vehicles traveling a longer distance to arrive at the destination, compared to those
who remain on the more congested theoretical best paths. It is an unavoidable aspect of
delay mitigation within traffic networks. In this section, results are shown that highlight

this activity within the given experimental setup.

88

 

 

    

 

 

 

 

s i \\ 5*” .iiiliiiif’iiw. ;
g 4000i § Present 7i
5 3000 , \
. s
s - N
S, 2000 \
< 1000 §

 

 

 

Figure 5-7: Travel distance degradation, highly congested traffic network

The average travel distance, under the identical simulation parameters for the
previous results, is shown in Figure 5-7. As for calculating the travel distance, a vehicles
traveled distance corresponds to the distance it has traveled from when it leaves the first
intersection to intersection 3. Unlike the average travel delay, both the NTCC with each
flow acting individually and NTCC with all flows display equal average travel distance.
By considering the principles of the two scenarios, the reason behind this is very basic.
That is, both definitions require vehicles to travel via the theoretical best paths the traffic
network allows, and these paths are the same regardless of the traffic conditions found
within the network. Therefore, the average travel distance for the NTCC cases are
exactly the same. As for the travel average distance when WiNDCC is applied, it
increases in comparison to the other cases. That is because longer alternate paths are

being used by vehicles to avoid the induced traffic congestion.

89

 

 

 

 

 

 

 

 

 

 

 

 

 

70
60 i if; EINTCC-Single Flow l
E-f INTCC-All Flows i
50 ~ !
m ).n !
2 ' WiNDCC-All Flows ]
2 40 _ l
g _
o t
>
'6 30 ‘
a?
20 .
10 ~ §
V
0 t . . s, I, , s1
2000- 3100- 4200- 5300- 6400- 7500- 8600-
‘ 3100 4200 5300 6400 7500 8600 9700
L Distance Range (m)

 

 

 

Figure 5-8: Overall distance distribution, highly congested traffic network

 

 

7

 

 

 

 

 

 

 

 

120
i DNTCC-Si leFlow ]
100‘ ‘ n9 .
INTCC-All Flows *
a so1 .
% WiNDCC - All Flows
s
> 60“
'6
32 -
40
s
0 g , j g ,

2000 - 3100 - 4200 -
31 00 4200 5300

5300- 6400‘ 7500- 8600-

6400

7500 8600 9700

Distance Range (m)

 

 

4

Figure 5-9: Flow 1 distance distribution, highly congested traffic network

90

 

 

 

 

120

100l

% of Vehicles

80‘
sci E‘:
W E:

20* {1°

 

 

El NTCC - Single Flow

I NTCC - All Flows

 

WiNDCC - All Flows

 

 

 

S , .

I

 

 

2000 - 3100 - 4200 - 5300 - 6400 - 7500 - 8600 -
31 00 4200 5300 6400 7500 8600 9700

Distance Range (m)

 

 

 

Figure 5-10: Flow 2 distance distribution, highly congested traffic network

 

 

 

 

 

 

 

 

 

 

 

 

 

120
i D NTCC - Single Flow
. 100
l I NTCC - All Flows
8 80 .
a _ thDcc - All Flows
§ :
> 60 i :'
'5 z.
39 t.
40 ;;
I E3.
20 ‘ ;':
0 ii: I l r i § . f
2000 - 3100 - 4200 - 5300 - 6400 - 7500 - 8600 -
31 00 4200 5300 6400 7500 8600 9700
Distance Range (m)
Figure 5-11: Flow 3 distance distribution, highly congested traffic network

91

 

 

To add more understanding to the average distance numbers, the overall and per
flow distance distribution has also been plotted and can be found in Figure 5-8 through
Figure 5-11. On the plotting axes, the x axis represents the distance breakdown and y
denotes the percentage of vehicles arriving within this distance range. As expected, the
WiNDCC enabled experiments move each distance distribution to the right, indicating
that vehicles are deviating away from the pre computed best path and are traveling longer
distances to alleviate their end to end travel delay. Also by viewing the per flow distance
distributions, it can be seen how many vehicles from a particular flow switch to another
path or remain on the primary path. Additionally it can be understood which path the
vehicles have taken, when the topology and potential alternate paths are considered for
each flow. For example, for flow I the vehicles within the 6400 to 6500 breakdown
traverse intersections 10, l 1, 6, 5, l, 2, and then 3. While the remaining vehicles within
the 8600 to 9700 breakdown traverse intersections 10, ll, 6, 7, 8, 9, 4 and then 3. The

same can be deduced from the distance distribution for the other two flows.

92

5.2.3 Delay vs. Distance Representation

 

 

 

7000 __u i

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Overall
? .- I f-
l inoui1 [:Zj
5000: Flowz %___<> % '- Dr
'2‘ O
E 4000 -2. Flow3 '
1: Q
g 3000 w $ @ I g
D
- Al
5’ 2000 1% 0 one —%
E] Combined
1000 »—— ——————— ~-
(Z) \vnvruac
0 , . - - - - a
o 200 400 600 800 1000 1200 1400 1600 ;

Avg. Delay (s) '

 

 

Figure 5-12: Delay vs. distance plot, highly congested traffic network

To summarize the abovementioned, the average delay vs. average distance for
relevant simulation setups is shown in Figure 5-12. In this figure the diamonds represent
the case when the indicated flows use the traffic network alone. The squares represent
the congested case where all flows use the traffic network at the same time, and the
circles indicate WiNDCC influenced traffic behavior. Also, each highlighting pattern
indicates a vehicular breakdown. As it can be seen for both the overall and per flow
categories, the average travel distance is larger. Nevertheless, the average delay is also
decreased. Therefore, it can be seen in from another vantage point the effectiveness of
the WiNDCC system at mitigating the traffic congestion within the highly congested

traffic scenarios, subject to the arguments presented in section 1.1.1.

93

5.3 Operator Oriented Performance Metrics

In this section, system operator or management oriented results will be shown for
the highly congested traffic network. These results differ from the aforementioned ones,
because they consider operational aspects of the entire traffic network and the overall
performance of the WiNDCC enabled vehicles. Also, the data series are NTCC and

WiNDCC, both with all flows residing in the traffic network.

94

5.3.1 Lane Utilization and Delay

 

 

 

 

w\\\\.\\\\\\§\\\\\\\\.
\\\\\\\\\\\\\\\\\\.
§x~§

WiNDCC

EJ NTCC

V\\\\\\\\\\\\\\§

 

 

 

V\\\\\\\\\\\\\\\\\\x
§

1 0%

      

\\\\\\\\\\\\\\\\\\\\\\

§§

\\\\\\\\\\u\\\\\\\\\\\k

 

 

 

 

 

 

 

 

« 11 q q a _

6. 5. A 3. 2 1. 0
0 0 0 0 O 0

0:000m can. 32>..0m 00.0.:0>

1011 1213 1415 16171819

9
Lane ID

8

 

 

Figure 5-13: Per lane utilization for highly congested network

 

 

§

V\\\\\\\x

V\\\\\\\«

§

\\\\\§

 

 

§
\\\\\\\\\\\N\\\\\\\S

 

                                          

 

 

_ _ ...................
A C ..\\\\\\\\\\\\\\\\\\\s
C
W W s\\s\\\\s\\\\\\\\\\s
_ U E s
_ _ .s\\s\\.\\\\\\\\8
Lii . A \\\\\\\\\\\\\\\\\\s
0 O O 0 0 0 0
2 m 8 6 4 2
822$ 8.63.; .o s

2 3 4 5 6 7 8 910111213141516171819

1

 

Lane ID

 

EL

Figure 5-14: Per lane service percentage for highly congested traffic network
95

 

8
o

 

l DNTCC
uwmocc .

i l

”,8"

  

8
o

 

  

 

 
 

Average Travel Delay (3)

  

  

 

 

 

 

 

 

 

 

 

WW4

 

   

  

’////7////////A

  

V/////////////

 

     

 

12 3 4 5 6 7 8 910111213141516171819?
LaneiD l

 

Figure 5-15: Per lane delay for highly congested network

By considering the way WiNDCC and other traffic delay mitigation schemes
actually alleviate the travel delay, it is evident that traffic originally intended for a
particular path is distributed along other links in the traffic network. From an operator
perspective, this is desired since more of the tax payer supported roadways will be used
to deliver vehicles to destinations, while the overall traffic delay experienced by drivers is
decreased. For the scenario in which the previous results were found, a per lane
utilization plot can be found in Figure 5-13. To clarify, the utilization for a lane is the
amount of vehicles serviced by a lane divided by the amount of time that it serves
vehicles. In Figure 5-14, a plot is given that represents the percentage of total vehicles

that are serviced by a particular lane. And, a per lane average delay plot is found in

96

Figure 5-15. In the plots, the lane numberings and topology are relisted to assist the
reader with understanding the results.

The first 9 lanes are the ones found by best path computation and that are used in
the NTCC case. It can be seen that the utilization for the shared and more congested of
these links is improved when WiNDCC is equipped. It can also be seen by the
percentage of vehicles serviced, that with WiNDCC equipped congested roadways
experience a decrease in the amount of vehicles they service. As a result, the delay is
also dramatically improved, since vehicles are using other links instead of those for
travel. Also subject to the simulation setup and operational aspects of a route guidance
system, WiNDCC forces other lanes to be utilized within the simulation area, hence the
data values for lanes 10 through 18 that are not seen without traffic congestion control.
Therefore, one can see that WiNDCC effectively transfers the utilization and delay of the

links in the pre computed best path links to other roadways within the topology.

97

5.3.2 Vehicular Throughput

 

 

l 0.35

 

0.3 _ El NTCC

 

 

WiNDCC

 

0.25 -

0.2 —

0.15 —

0.1 ~

 

Vehicles Arriving Per Second

 

0.05 -

 

 

 

   

 

 

 

 

 

 

 

 

| Flow 1 Flow 2 Flow 3
l Set of Vehicles

 

 

Figure 5-16: Vehicular throughput for highly congested traffic network

Another operator quantity that is examined corresponds to the vehicular throughput
or destination arrival rate and is found in Figure 5-16. This quantity is simply the amount
of vehicles successfully delivered to the destination divided by the amount of time it
takes for them to be delivered, in seconds. Within the plot area, the x axis corresponds to
the set of vehicles and y denotes the amount of vehicles arriving per second. Although
the numerator of the computation remains the same for each experiment, the denominator
changes, since when mitigation is applied the vehicles arrive in a shorter amount of total
time. It can be seen that on an overall and per flow basis the destination arrival is

improved with WiNDCC enabled.

98

5.4 Effects of Initial Congestion Indicator on End to End Delay

 

 

1 400

 

1200 i ;
ElWiNDCC 3 T:
1000 - "

 

800]

_ ri- -- F F '1-
1 .‘ ’. . ‘.

600a

4001 :3 33 :l :j 1: E i: if 3E 3i 3:

Average Travel Delay (s)

200 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I a e u a e .

0j I:: T:: I:: I:: f. I I
«0" 9° it?” a” 3” 9° 13°39“

 

 

<6 0 00
\

0’
C)
ICI V6

 

 

Figure 5-17: Effects of ICI on overall travel delay

The next result demonstrates the effects of the ICI described in section 3.6.1, the
WiNDCC system quantity that describes when vehicles will begin broadcasting traffic
delay information about a particular link. In short, a large ICI value allows more
congestion to develop in a link before broadcasting any information. The results thus far
have used an ICI value of .25. Nevertheless, Figure 5-17 is included and shows the
overall end to end travel delay for various ICI values in the highly congested traffic
network. The main data series is WiNDCC, and it is evident that as ICI increases so does
the overall travel delays. However, three other data points are included that help put in
perspective WiNDCC performance. The first, listed on the far left is NTCC with all
flows present, and on the far right is the overall delay with each flow occupying the

network alone. It can be seen that as the ICI increases, the delay begins to look like that

99

for NTCC combined, as one would suspect due to the lack of information being broadcast
about the traffic network. The ICI equal to 0.00 data point represents an experimental
scenario where each vehicle broadcasts its delay information after exiting every link. As
one can see, the delay is not mitigated any better than WiNDCC with an ICI value of .25.
This finding validates the logic used in the link exit strategy, along with the ICI
utilization, since the congestion is being adequately mitigated with much less information
being broadcast into the network. This finding will be covered in more detail in Chapter

8.

100

5.5 Results with Partition Bridging and Varying Traffic Input Rates

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l 1400
i 1200 _ 1:1 Lambda High
1; I Lambda Med.
I 1000 J
g Lambda Low
_ 800 - - --
i
i- 600 -
i
it 400 ~
200 ~
0 t
NTCC WiNDCC WiNDCC - PB
Traffic Mitigation Scheme

 

 

 

Figure 5-18: Delay with varying vehicular input rates and mitigation schemes

In terms of the vehicular input rates seen in Table 5-1, results concerning them and
the partition bridging extension, described in section 3.7.4, of the forwarding algorithm
are plotted in Figure 5-18. In the figure, the x axis represents the various mitigation
schemes and the y axis is the average overall travel delay. By closely viewing the results,
it can be seen that partition bridging assists normal WiNDCC with medium and low
traffic input rates; although, the network is less congested as seen by the NTCC category.
This follows in line with the purpose of the partition bridging algorithm. That is, the
effect of the partition bridging is most evident when the network is more partitioned in
the traveling direction, such as the medium and low input rates. For the high input rate
the effect would be minimized because the network is much less partitioned than in the

other cases.

101

Chapter 6: WiNDCC Performance for Handling Ti'affic

Events

In this chapter, WiNDCC effectiveness will be evaluated with a traffic event in the
network. In terms of the WiNDCC application layer algorithms, this experiment will test
the event generation scheme of section 3.6.2. Results similar to those for the congested
case will be presented and discussed, along with an initial description of the revised
simulation setup. As was done earlier, most results will be in terms of the high traffic
input rate case. Then, perspective will be given in terms of each traffic input rate used in

this scenario.

102

6.1 Simulation Setup

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

__ Best.
12
16 =: _2_ 17 -
_ F1 5 F2 EH— 93" — —.
14 13
5020 5 1 ti 1 7 Z: 11
__ $ 18__8 __
-Traffic Light _"""° E
## - Lane ID
if; Flow Start —~ 8 It I,
1::(>Travel Path Identifier 1 0
F1 g 7E l7
19
3000 F- 0 1 l 2 3——l
‘ ‘ —>" .13 1
F3
2 E I N
3,000 4,010 5,020 6,030

 

Figure 6-1: Simulated traffic network with relevant markings

For the event based experiment used to gather the results for this chapter, the same
topology and underlying characteristics are used from Figure 4-1, Table 4-1, Table 5-1,
and Table 5-2. In addition, the event scenario is as follows and the topology is relisted in
Figure 6-1. In terms of the geographic location of the event, it will happen 850 meters
into the link between intersection 7 and 3. As a visual aid, this area is marked by the line
near the indicated link in Figure 6-1. The event will affect the first vehicle to reach this
point and will last for about 690 seconds, equal to around 1 1.5 minutes. After the event

is concluded, the front vehicle will proceed as planned to the destination area. Also, in

terms of the traffic input rates, high and low were considered for the event case.

103

 

6.2 User Oriented Performance Measures

As previously discussed, the user oriented results highlight the ability of WiNDCC
to affect the travel quality of individual drivers. For the event case, with high traffic
input rate, the user results are as follows. However since the result is not as relevant for
the event case, the NTCC with flows acting individually will not be included in them.
Therefore, NTCC all flows will be compared to the data with all flows using the

WiNDCC system.

104

6.2.1 Travel Delay Improvements

 

 

 

 

 

 

 

 

2000

1800 « BNTCC

1600 -
:-:‘: IWiNDCc323:':?

1400 .J

 

 

1200~ EiEgEgSg

 

 

 

Avg. Travel Delay (3)
8
O

 

 

 

 

 

 

         

 

 

 

400 ~
j [:3
200 ._.
0 .
Overall Flow 1 Flow 2 Flow 3
Set of Vehicles

 

Figure 6-2: Average travel delay with event present

The average travel delay plot can be viewed in Figure 6-2 and has the same axes as
seen in the average delay for the congested case. By inspecting the delay values
associated with the NTCC case, the very high delay values are a result of the event
introduced into the traffic network. As one can see, the WiNDCC system is successfully
able to mitigate this delay on an overall and per flow basis. This is a testament to the
combined event generation algorithm and underlying network layer operations that guide
vehicles away from the congested area to ones that are moving within the traffic

topology.

105

 

 

 

D NTCC

 

 

I WiNDCC

 

% of Vehicles

 

 

 

 

 

 

 

 

 

 

 

 

. _ lit gijnapnn

i §§§§§§§§§§§§§§§§

. ,,.,v—v—v-w-v-NNNNNCOCO

' sssssag'sg'aaaaag"

°~M8§a§asssssa§
DelayRange(s)

 

 

Figure 6—3: Travel delay distribution with event present
The overall delay distribution further supports the numbers seen in the average
delay results and can be found in Figure 6-3. That is, based on the reported delay values,
much less vehicles experience the extreme delay values caused by the event within the

travel network when WiNDCC is equipped.

106

6.2.2 Travel Distance Degradation

 

 

    
    
   

 

 

 

 

 

 

 

 

 

 

7000

6000 1 El NTCC
E, 5000 A IWINDCC
d)
O
I:
g 4000 -
o
1’ 3000 -
8
I-
S 2000 -

1000 -

O < i .
Overall Flow 1 Flow 2 Flow 3
Set of Vehicles
Figure 6-4: Average travel distance with event present
_T L, 7, 7
60 . El NTCC
:3: ; lWiNDCC

50 < 3;; l

3
l s ,

d1 1
>
'6
32

 

 

 

 

 

2000 - 3100 - 4200 - 5300 - 6400 - 7500 - 8600 -
31 00 4200 5300 6400 7500 8600 9700

Distance Range (m)

 

 

Figure 6-5: Travel distance distribution with event present

107

The travel distance is also degraded, when compared to those corresponding to the
theoretical best paths, when travel delay mitigation is achieved due to the event within
the traffic network. The average travel distance and overall distance distribution can be
found in Figure 6-4 and Figure 6-5. They both support the arguments presented in this
thesis about the effects of alleviating the individual travel delay experienced by travelers.
That is, WiNDCC travelers travel a longer distance to avoid the event, from an overall
and per flow perspective. In fact, very few vehicles remain on the originally selected
travel paths, which can be understood by viewing the distribution and visualizing the
extreme shift to the right in the WiNDCC data, with respect to that of NTCC. This also is

in response to the event within the network.

6.3 Operator Oriented Performance Measures

Here, the results that would most interest the system enabler will be presented.

They are similar to those found within the same category of the congestion case.

108

6.3.1 Lane Utilization and Delay

 

 

 

 

   

 

 

 

 

 

 

 

 

 

0.7 , _
:1ch

g (ml lWiNDCC
i 0.5-
U)
3
g 0.4 -
E 0.3 r.
a)
8 .
.7.’ 0.2 —.
.C
0
> 0.1 -

0 -1

12 3 4 5 6 7 8 910111213141516171819
Lane 10
Figure 6-6: For lane utilization with event present
120 T
nnrcc ‘
10° ‘ lWiNDCC

 

 

on
O
I

A
C
r

 

 

% of Vehicles Serviced
O)
O

        

 

 

 

 

12 3 4 5 6 7 8 910111213141516171819!
LanelD

 

 

 

Figure 6-7: Per lane service percentage

109

 

'1000
900- “ DNTCC ‘ __

W'NDCC . '“
800 g I I ]

 

 

 

 

 

 

 

 

 

 

 

 

 

  

 

 

 

 

E

g 7001

a

8 600- _

a 1'

> 500—

E

Q 400*

3

Q 300‘

2
2001
1001
0-

] 123456789101112131415161718
LaneiD

 

 

Figure 6-8: Per lane delay with event present

The lane utilization and delay comparing the NTCC congested and WiNDCC
enabled cases can be found in Figure 6-6, Figure 6-7, and Figure 6-8. By viewing these
results, it can also be understood the per lane traffic network operation due to the event.
WiNDCC betters the utilization while also decreasing the delay. The system also, as a
result of rerouting vehicles around the event site, utilizes other lanes to help decrease the
end to end and per lane travel delay, which can be seen by examining the utilization and
percentage serviced results. These results are vital to a network operator, since the
effects of the delay are mitigated and the traffic network is more usable as a result of the

WiNDCC enablement.

110

6.4 Vehicular Throughput

 

 

 

0.6 - El NTCC

 

1. - WiNDCC

 

.9
A

 

Vehicles Arriving Per Second
.0
OJ

 

 

 

       

 

 

 

 

 

Overall Flow 1 Flow 2 Flow 3
Set of Vehicles

 

 

 

Figure 6-9: Vehicular throughput with event present

The vehicular throughput is greatly improved when applying WiNDCC logic to the
event induced simulation scenario. The result can be found in Figure 6-9 and shows that
the WiNDCC enabled vehicles arrive at the destination at a much faster rate than with the
event present in the network. This result holds true on an overall and per flow basis.
This improvement, from the network operator perspective, reemphasizes the
effectiveness of WiNDCC when events are present in the network that slow or stop traffic
flow. The throughput improvement happens due to the redirection of traffic within the
roadway system, which decreases the amount of time required to deliver vehicles to the

destination.

1]]

6.5 Results with Partition Bridging and Varying Traffic Input Rate

 

i600" 7' t

 

160° ‘ l a Lambda High

1400 1

   

i Lambda Low
1200 ~ .

1000 -
800 J

600 4

 

Average Travel Delay (3)

400 -

200 l

 

 

 

Traffic Mitigation Scheme

 

Figure 6-10: Delay with varying vehicular input rates and event present

Th

('0

results including high and low input traffic rates with partition bridging,
described in section 3.7.4, can be found in Figure 6-10. Just as was seen in the
congestion only case, the partition bridging assists more when the vehicular input rate is
lower. This is a result of increased partitioning within the traffic network. Therefore, the
effects of partition bridging can be better seen, since the goal of the algorithm is to assist
in instances when the underlying traffic network is partitioned. As a result, when the
input rate is low, partition bridging allows WiNDCC vehicular systems to find out about

the event sooner and adjust travel routes accordingly.

112

Chapter 7: WiNDCC Performance with Cache and Carry

Message Forwarding

Thus far and in terms of WiNDCC network layer functionality, WiNDCC equipped
vehicles in each of the previous experimental setups relied primarily on the fast path
message forwarding scheme described in section 3.7.3. Looking back, the fast path
message forwarding technique used the vehicles within the reported link and those
potentially traveling into the reported link to broadcast the delay information. Therefore
in the abovementioned scenarios, vehicles from each flow were responsible for both
broadcasting and forwarding the traffic information about links ahead of it, to allow the
vehicles behind it an opportunity to adjust travel if necessary and forward the necessary
traffic information. Most importantly, this scheme was adequately able to mitigate the
travel delay by taking advantage of the connectivity in which the underlying traffic
network allowed, although this may not always be so.

In terms of the overall network layer functionality attributed to the WiNDCC
system, another forwarding principal is vitally important to overall routing layer
functionality and system efficiency. That is, the WiNDCC cache and carry message
forwarding subcomponent described in section 3.7.5 also contributes to the delay
mitigating capabilities of WiNDCC. In fact, as will be seen in the experiment performed
in this chapter, sometimes traffic delay mitigation cannot effectively be achieved without
the aid of background traffic deploying the cache and carry message forwarding to
spread traffic information. As a consequence, this chapter presents a scenario in which

the cache and carry forwarding operation is necessary to delay mitigation.

113

7.1 Simulation Setup

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

T Dest. T
12
6030 l , l g l .1 Jfi ‘l‘—-—l
_—15 2 TF2 E, mg" ..
5020 14 g 13 _
l—-—~ 5 I it I ‘7 __ 11
_ & 18__8 _
@-Traffic Light F ‘ E L
#tf - Lane 10
3; Flow Start ——5 , J. ,,,
t:{>Travel Path identifier 1 0 '
F1 E" 7E i—
19
3000 .F-— i 1 l '2 3——l
‘ ' —>" .1“ 1
F3
34% IN
3,000 4,010 5,020 6,030

 

 

 

Figure 7-1: Simulated traffic network with relevant markings

 

 

 

 

 

Flow ID Number of Vehicles Flow Start Time Input Rate
1 — Dormant Flow 300 3003 .5 Vehicles/Second
2 — Dormant Flow 180 650s .5 Vehicles/Second
3 — Target Flow 200 4505 .06 Vehicles/Second
Background Flow 250 805 .1 Vehicles/Second
From Dest. to 3

 

 

 

 

 

 

Table 7-1: Experimental flow properties
The simulation setup for the scenario performed in this chapter is similar to the
ones seen in the previous chapters. That is, the three flows shown in Figure 7-1 remain,

with slight variation. Also, another background flow is added that will provide the cache

114

and carry functionality highlighted in this chapter. To begin understanding the new
simulation setup, examine Table 7-1.

In reference to the table, the three flows are slightly modified. To begin with, flow
1 and 2 are labeled as dormant flows, signifying that these flows will not be equipped
with WiNDCC or any other route guidance functionality. Therefore, they will adhere to
the theoretical best case logic and use paths outlined for them in Figure 4-1, with respect
to the destination. Also, flow 1 contains 300 vehicles and will become operational 300
seconds into the simulation, unlike the previous experiments. In terms of the vehicular
input rate, the high entry rate is used as earlier described.

As for flow 3, it is also modified and listed in the table as the target flow. This
naming is because it is the flow in which the results for this chapter are oriented. The
flow will be equipped with WiNDCC functionality and will have an entry rate as
mentioned in the table. This slow entry rate will make this flow unable to use WiNDCC
with fast path forwarding to alleviate the travel delay it will experience due to flow 1 and
2, due to the sever partitioning between vehicles. In the results section, this will be
clearly seen.

In addition, another flow is added that will implement the needed cache and carry
functionality required to effectively alleviate the travel delay experienced by the target
flow. This background flow originates from the common destination of flow 1, 2, and the
target flow labeled 3; and, the destination for the vehicles is the same as the origination of
the target flow. It also uses WiNDCC and uses the theoretical best path as outlined by
the arrows extending from the destination as seen in Figure 4-1. Therefore, the flow will

traverse the same roadways as the target flow but in the opposite direction. In terms of

115

the entry rate, this flow uses the low rate according to the previous experiments. Because
of this rate, and since the vehicles of this flow will be the only ones using the highlighted
travel links, any traffic congestion along the travel path will not be enough for the
WiNDCC route computation module to guide these vehicles away from the originally
computed primary path. It will be seen in the results that this flow enables delay
mitigation for the target flow.

To assist with summarizing the simulation setup, a description of the data series
that will be used in the results can be given. The first series is similar to the previously
encountered NTCC with all flows combined. However in this case, the heading is
reserved for describing the target flow performance without WiNDCC enabled. The
second series is the performance of the target flow under the guidance of WiNDCC with
partition bridging enabled. This result is used as a reference and proves that the target
flow will need other information to achieve end to end travel delay improvement. Since
the flow is partitioned, the partition bridging extension is used to achieve the best results
possible. The final data series will represent the target flow performance with the
WiNDCC enabled background flow in the traffic network. Results will be shown

supporting the claims made thus far.

116

7 .2 Target Flow Delay

 

 

 

    
   
 

 

 
 

 

 

 

 

 

1000
900.
8004 2§2§2§232§33232§2§2§:;
i 6°“ ~ .
:22; g .
g 300‘ lWiNDCC-PBOnly
200— gigigigigigigigigigigi w .vamfccgdpeand
. :szs:s:s:2:s:s:::::z:3 mm“ .
. 1°: 533333233323335533333‘ w e __ [W
Traffic Mitigation Scheme

 

 

 

 

Figure 7-2: Average travel delay for target flow
First, the average delay of the target flow will be examined with regard to the
abovementioned simulation scenarios and data series. The delay plot can be found in
Figure 7-2. In it, it can be seen that WiNDCC with the partition bridging extension
enabled is only able to partially mitigate the travel delay associated with the target flow.
However, with the background flow enabled the delay is further mitigated and the
advantage of the WiNDCC system can be better seen. As it will be seen when the target

flow distance is examined, the reasoning behind this is quite straightforward.

ll7

 

 

 

 

   

 

   

 

 

 

 

 

 

 

 

 

80
"NTCC
~——.. 1
l WiNDCC - PB Only
60 «
WiNDCC - PB and
I :3 50 « Background l
o _
.g
> 40 ‘
. ”6
l a! 30 J
20 i
10 «
. 0 f s . . .. .
l 200-400 400-600 600-800 800-10001000-12001200-1400
E Delay Range
L____ _ _ __ ._ ___- _- __

 

 

Figure 7-3: Delay distribution for target flow

As for the target flow travel delay distribution, it can be found in Figure 7-3 and
adds meaning to the average delay results. That is, with partition bridging enabled the
distribution is shifted to the left, a sign of delay improvement. However, one can see
that the WiNDCC with background traffic shifts the distribution farther to the left,
producing the superior average travel delay. Also, it can be seen that with partition
bridging alone that the distribution is actually slightly worse than the NTCC case. With
regard to the arguments presented in section 1.1.], this is due to a few vehicles switching
paths and experiencing a greater delay than if they would have remained on the pre
computed best path. In terms of the delay vs. distance discussion, these vehicles would
fall into the unjustified switching region, with respect to vehicles immediately before

them that remained on the primary travel path.

118

7.3 Target Flow Travel Distance

 

 

 

   
       

 

 

 

 

 

 

4500

4000 -
A 3500 -
5 D NTCC
9:3 300° ‘ lWiNDCC - PB Only ‘
8
g 2500 - lWiNDCC - PB and
E 2000* Background
2
"I 1500 -
2’
“ 1000

500 —
0 &
Traffic Mitigation Scheme

 

 

 

Figure 7-4: Average travel distance for target flow

By viewing the distance results for the target flow, more insight can be gained
about the simulated activity. To begin with, the average travel distance for the target
flow can be found in Figure 7-4. Similar to what has been discussed and seen with the
presented results, with delay mitigation comes increased distance. Also, it can see that
for the superior mitigation technique of WiNDCC with background traffic flow, the
average travel distance is the highest. To understand why and put into better perspective
the results presented in this chapter, consider the distance distribution which allows one

to understand the actual travel paths taken by vehicles.

119

 

 

120

 

DNTCC
100 «

I WiNDCC - PB Only

(D
O

 

 

l

i

WiNDCC - PB and l
Background A
|

% of Vehicles
0)
O

.h
0

20—

 

   

 

 

 

‘ 2000 - 3100 3100 - 4200 4200 - 5300 5300 - 6400 6400 - 7500
Distance Range

 

 

 

Figure 7-5: Distance distribution for target flow

The distance distribution is found in Figure 7-5. By considering it, one can see that
congestion corrected WiNDCC vehicles with partition bridging enabled take a longer
path to reach the destination. This is a result of those vehicles finding about the
congestion in the slowed link later than those WiNDCC enabled vehicles when the
background flow is added. Therefore, they take a longer path to try and avoid the slowed
link, by turning left and intersection 7 and proceeding to the destination. In terms of the
unjustified switching highlighted by the delay distribution, this reroute is responsible for
those findings. However with the background flow enabled, WiNDCC equipped vehicles
are notified about the congestion in the slowed link between intersections 12 and 8 by the
WiNDCC equipped background flow, which results in them taking a shorter and more

delay efficient path to the destination. This is also verified by the distance distribution.

120

Chapter 8: Performance of WiNDCC-enabling Wireless

Network

Thus far, all of the performance measures have been in terms of the delay
mitigation goals of WiNDCC. Although the results prove that WiNDCC has potential
within the realms of route guidance mechanisms, results have not been presented to
verify or examine the wireless networking principles WiNDCC is built upon. It is
important to do so, since within the WiNDCC design there are several nuances intended
to enhance the wireless networking capabilities of the system and maintain the health and
effectiveness of the wireless channel. Also, the overall research contributions of the
work are not only within the traffic engineering space, but there is also interest among
those studying traditional and vehicular ad hoc networks, based on the infrastructure-less
VANET system WiNDCC enables.

In this chapter, results are presented that reexamine some of the abovementioned
simulation scenarios from Chapter 5 and highlight some of the application and network
layer functions of the system. Results will be shown that will give the reader an

understanding about WiNDCC performance, from a wireless networking perspective.

8.1 Simulation Setup

In terms of the simulation setup, the wireless network oriented results will come
from the simulation runs responsible for the majority of the results in Chapter 5. Like
those simulations, the WiNDCC specific system parameter of ICI is set at .25, and the
traffic input rate is set to the high quantity. Therefore, the simulation setup presented in

this chapter mimics the one responsible for the results from Figure 5-2 through Figure

121

5-16. As for the results presented in this chapter, a brief description regarding the
relevancy and any simulation changes required to gather the numbers for the specific

quantity will be given, along with the graphical representation.

8.2 Network Overhead

In terms of the wireless network overhead associated with the WiNDCC system,
the generation and forwarding paradigms aim to reduce the amount of packets sent over
the broadcast medium while maintaining the traffic delay mitigating capabilities of the
system. In this section, the results relate to the packet generation associated with
WiNDCC under various protocol settings. In specific and as was seen in Figure 5-17
when the average end to end delay was examined, the ICI will be adjusted and the

corresponding wireless network overhead values will be recorded.

122

8.2.1 Generated Delay Packets

 

 

 

 

 

 

 

1, 0.01
C
O
0
<3 1»
it
2 0.0011
.2
.2
0
> .
g 1
0.0001~
3.
E
0
C
0
<5
1 22 0.00001
0
x
0
fl 1
“- l
> I
E i
30.000001 - i e . g
0.00 2.00 4.00 6.00 8.00 10.00 12.00

1 __ ICI

 

 

Figure 8—1: Delay packet generation

With regard to the generation scheme primarily responsible for the delay
extractions used within the WiNDCC framework, the ICI determines the when to
broadcast messages. To understand how this term affects the total number of delay
extractions for the abovementioned simulation scenarios, examine Figure 8-1. On the x
axis is the ICI value and the y axis is a logarithmic representation of the delay packets
generated per second per vehicle. In the diagram it can be seen that as the ICI increases,
the amount of delay extractions is decreased. This is a straightforward result of the ICI
design philosophy. Also, the point where ICI is equal to 0.00 is not WiNDCC, but
instead this represents a simulation run where each vehicle broadcasts its delay after
exiting each link. This point is included to verify the operational aspects of the ICI. That

is, since in Figure 5-17 the delay for this data point is very similar to when the ICI is

123

equal to .25, it can be seen that the filtering associated with the ICI and link exit routine
does not adversely affect the delay mitigating capabilities of the system. The 0.00 ICI
point of Figure 8-1 shows its affect, since it is much greater than that of any ICI assisted
data values. This further proves that there is not a need to broadcast information in this

manner, from a travel delay or wireless networking perspective.

124

 

l

 

 

 

 

 

 

0.1
'0

C

O

O

8 i

b b

a 0.01

2

.2

.C

0

>

g 0.001«

3..

9.

O

5

0 0.0001‘

2’.

0

X

0

(U

0.

0.00001 . . , , ,
0.00 2.00 4.00 6.00 8.00 10.00 12.00
ICI

 

 

Figure 8—2: Total packet generation
In terms of the overall amount of packets generated according to ICI, this result can
be seen in Figure 8-2. To clarify, the data includes all packets sent during the simulation
time, both delay extractions and forwards. Therefore, the numbers exhibit the same trend
as the generation numbers. The main difference is that the numbers are larger than
previously seen. This result is expected, since in order for a WiNDCC device to forward

a packet the data must first be generated.

125

8.3 Fast Forwarding Benefits

During the initial activities of the WiNDCC network layer operation, the fast
forwarding scheme attempts to broadcast a packet. This protocol looks to move delay
messages as fast as possible. In this section, a result is presented that highlights the
importance of such activity to WiNDCC operation. A look at the WiNDCC inspired end
to end traffic delay without fast forwarding will be given to show this. When fast
forwarding is not used, a randomized value is chosen in between 75% and 95% of the
ADI for a vehicle at packet reception time. This value is used in the place of the distance

based back off time found within the fast forwarding algorithm.

126

 

1200 .
u WiNDCC

   
  

1000 -

l WiNDCC Without Smart
Forwarding

8
o

 

Avg. Travel Delay (3)
§ §

  

    

 

 

 

 

 

 

 

 

Overall Flow 1 Flow 2 Flow 3
Set of Vehicles

 

|\)
O
O

 

Figure 8-3: Fast forwarding travel delay comparison
In Figure 8-3 the overall and per flow end to end travel delay is shown with fast
forwarding equipped and with the previously mentioned randomized forwarding. It can
be seen that the overall and per flow traffic delay is increased due to the elimination of

the fast forwarding scheme.

127

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

25. nwmocc T

E I WiNDCC Without Smart

320‘ FonNarding 4

2

g...

'6

9

gm.
1 £
i 5. €32333:3;isizizizizizizisisfzis
i *I-Z-I-I‘I-I{-35-2-2‘2-3-1-2-
i ::::::::::Z::::::::::::::::::::
l O ...............................
i Forwarding Scheme

Figure 8-4: Fast forwarding packet delivery delay comparison
To understand why the delay is worsened, Figure 8-4 is included. It shows the
packet delivery delay associated with any generated packet during the simulation time.
To clarify, a packet is considered to be delivered when it reaches a point where the
network is portioned. It can be seen that the delay is increased when fast forwarding is
eliminated. Therefore, vehicles learn about delay messages later than they would with
smart forwarding equipped. This explains the change in travel delay when the

randomized forwarding is introduced.

128

8.4 WiNDCC Performance with Varying Packet Error Rate

In the wireless networking domain, packet error rate is used to understand how a
mechanism will perform under less than ideal circumstances. This is done because under
normal operation a wireless radio device will not always successfully receive a particular
transmission, even if it is within the reception range of the sender. A random number,
with respect to the desired packet error rate, is used to determine if a packet will be

dropped according to this consideration.

129

 

1 400

 

1 200

1000 .

800 <

600 <

Avg. Travel Delay (8)

400 « 555

200

 

 

 

 

—
—
—
—
—
—
—
—
—
—
—
-
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
‘—

Flow 1
Set of Vehicles j

 

 

 

Figure 8—5: Travel delay with varying packet error rates

In Figure 8—5, the WiNDCC delay response according to various packet error rates
is seen. The mechanism fairs well against packet error rate, not exhibiting degradation
until about 75% of packets are dropped. This is because WiNDCC encourages vehicles
to send multiple delay messages about a link, especially if is becoming more congested.
Therefore, a vehicle is eventually able to learn about a particular roadway delay, even if it
has dropped one or more of the earlier messages about a link. This of course depends on
the underlying network topology, which in this case is fairly connected since the
experiments use the fastest traffic input rate. As a consequence, the WiNDCC enabled
vehicular devices are still able to receive information and make travel decisions after

information is received in an adequate amount of time.

130

8.5 WiNDCC Performance with Varying Penetration Rate

 

 

 

 

 

 

 

 

 

1 400
El 100%
I 95°/o
1200 90%
E 80°/o
’5? 1000 E 60%
; El 40°/o
2 I: NTCC
8 800 .
E
9 600
'—
g"
< 400
200
0
l Overall Flow 1 Flow 2 Flow 3

 

‘ Set of Vehicles

 

 

 

Figure 8-6: Travel delay with varying penetration rates

When implementing protocols and standards within the VANET domain, vehicular
penetration rate is very important. That is, at the onset of deploying a VANET system,
every vehicle on the road will not be equipped. Therefore, determining protocol
responsiveness according to penetration rate is needed. Figure 8-6, gives an idea of this
with respect to WiNDCC and the average end to end travel delay experienced by
vehicles. As is expected when considering the limiting effects of penetration rate, it can
be seen as less vehicles are made WiNDCC able, the end to end delay becomes
worsened. This is expected, since fewer equipped vehicles means more drivers will
remain on the pre computed best paths within the traffic network. However, these paths

are congested, resulting in an increase in travel delay.

131

Chapter 9: Conclusions and Future Work

9.1 Conclusions

In this thesis, a completely distributed, infrastructure free, broadcast oriented,
vehicular navigation framework was developed and evaluated via simulation study,
called Wireless Network Enabled Distributed Congestion Control or WiNDCC. The
system and the corresponding specifications are contained within the realms of the
Vehicular Ad Hoc Network or VANET. In short, the primary goal of the system is to
broadcast travel link delay information to the other WiNDCC enabled devices that need
them, in a fast and efficient manner. From an architectural perspective, the protocols
combining to form the WiNDCC paradigm reside within the application and network
layers, particular to the typical wireless networking protocol stack.

At the application layer, algorithmic activity includes the generation of delay
messages and the routine responsible for determining what network layer subcomponents
to use for received delay messages. As for the delay generation tasks, two different
routines were used to handle traffic congestion issues; the first is invoked when links are
moving slowly, and the second is used to detect a stopped travel link and broadcast the
information about it. In both cases, the primary goal of the generation scheme is to keep
the network aware of the traffic information on a certain link, while also aiming to not
over broadcast information from that link. Therefore, the system specification contains
several nuances particular to this goal. As for the delay packet reception module, it is
responsible for comparing the geographic positions of the sending and receiving nodes to
determine which of the two network layer message forwarding policies to use for a

message.

132

At the routing or network layer, the goal is to rebroadcast the received delay
messages according to the instructions it receives from the application layer packet
reception module. The receive module actually initiates the network layer operations by
deciding which of the two WiNDCC forwarding paradigms will be used to broadcast a
packet. The first network layer subcomponent uses the vehicles entering the link being
reported by the delay message to forward the packet fast and efficiently, to other vehicles
that could potentially enter that link. The primary component of this forwarding
technique, called fast forwarding, is a distance based backoff timer that aims to forward
packets as far as possible, with a minimal number of transmissions. This method is more
successful if the underlying traffic network topology is dense and fairly connected.
However during time when this is not so and the underlying vehicular network topology
is very partitioned, the second network layer subcomponent can be enlisted to ensure that
information is still able to be broadcast around the traffic network. That is, the cache and
carry forwarding method uses the vehicles who have received a delay message, to carry it
to other areas of the topology that could contain vehicles that can make use of the
information. This method helps when the fast forwarding message paradigm is unable to
deliver delay messages to certain geographical areas.

Finally, the received information about the traffic network in which a WiNDCC
enabled vehicle is traveling is used within its route computation function to provide travel
decisions the revised travel decisions to drivers, according to the amount delay
encountered on its currently selected travel route. This component completes the sensing
and reaction loop that WiNDCC enables, by allowing vehicles to use the traffic

information.

133

This work provides simulation examples that use a macro vehicular simulator,
designed and implemented as part of the work required to complete this thesis, to test the
effectiveness of the WiNDCC system against various traffic congestion issues. The
results show that WiNDCC enabled vehicles can avoid and help mitigate traffic delay by

utilizing the roadway network for alternate paths.

9.2 Future Work

Future work concerning the WiNDCC system includes a few different tasks, each
intending on understanding the effectiveness of the WiNDCC system in more realistic

traffic environments.

9.2.1 Simulation and Algorithmic Fine Tuning

Still in terms of the simulation phases of system design, WiNDCC should be tested
with a more realistic traffic simulator to understand how it performs. As a consequence,
algorithmic nuances of WiNDCC will need to be implemented. For example, slight
changes or additions will be needed to deal with multiple lanes of traffic and to handle
turning lanes. Also in this simulation study, the delay mitigating properties associated
with the mechanism should be explored, along with an examination of the wireless
networking performance. In addition, the algorithmic components of WiNDCC can

begin to be tailored in terms of a unique traffic environment.

9.2.2 Lower Layer Considerations

According to the WiNDCC system designed for this thesis, considerations where
not given in terms of the layers lower than the network. However as vehicular densities

increase, there may prove to be a need for MAC or physical layer assistance, to maintain

134

the sanity of the broadcast mechanism. Therefore, some cognitive radio or channel aware

lower layer designs can be hinged to improve performance.

9.2.3 Topology Specific WiNDCC Parameterization

In terms of a real world WiNDCC implementation within a particular geographic
region, it may be useful to adjust certain system parameters such as ICI, partition
bridging, and DET on a link by link, time, or travel event basis. This system
enhancement could prove to be the starting point for implementing real time or pre
planned system operator goals within the WiNDCC system. Another, topology specific
aspect that could be examined is using the data broadcast by WiNDCC devices to control

traffic lights, adding another aspect to WiNDCC oriented traffic choreography.

135

[1]

[2]

l3]

l4]

[5]

I6]

[71

I8]

[9]

[101

[11]

[121

Bibliography

Y. Liu, F. Dion, and S. Biswas, "Dedicated Short-Range Wireless
Communications for Intelligent Transportation System Applications,"
Transportation Research Record: Journal of the Transportation Research Board,

2005.

L. Yang and F. Wang, "Driving into Intelligent Spaces with Pervasive
Communications," IEEE Intelligent Systems, vol. 22, 2007.

J. Bartlett and F. Spinelli, "Understanding GPS navigation traffic services,"
http://blogs.consumerreports.org/cars/2007/l 2/gps-traffichtml.

S. P. Fekete, C. Schmidt, A. Wegener, and S. Fisher, "Recognizing Traffic Jams
with Hovering Data Clouds," 2007.

A. Chen, B. Khorashadi, C.-N. Chuah, D. Ghosal, and M. Zhang, "Smoothing
Vehicular Traffic Flow Using Vehicular-Based Ad Hoc Networking &
Computing Grid (VGrid)," " in Intelligent Transportation Systems Conference,
2006.

T. Nadeem, S. Dashtinezhad, C. Liao, and L. Iftode, "TrafficView: a scalable
traffic monitoring system," in IEEE International Conference on Mobile Data
Management, 2004.

J. Anda, J. LeBrun, D. Ghosal, C.-N. Chuah, and M. Zhang, "VGrid: Vehicular
AdHoc Networking and Computing Grid for Intelligent Traffic Control," in
Vehicular Technology Conference, 2005.

M. Jerbi, S.-M. Senouci, T. Rasheed, and Y. Ghamri-Doudane, "An
Infrastructure-Free Traffic Information System for Vehicular Networks," in
Vehicular Technology Conference, 2007.

R. Tatchikou, S. Biswas, and F. Dion, "Cooperative Vehicle Collision Avoidance
using Inter-Vehicle Packet Forwarding," in IEEE Globecom, 2005.

S. Biswas, R. Tatchikou, and F. Dion, "Vehicle-to-Vehicle Wireless
Communication Protocols for Enhancing Highway Traffic Safety," IEEE
Communications Magazine, 2006.

C. J. Merlin and W. B. Heinzelman, "A Study of Safety Applications in Vehicular
Networks," 2005.

"Advanced Cruise-Assist Highway System Research Association,"
http://www.ahsra.or._ip/index e.html.

136

[13]

[14]

[15]

[16]

[171

[181

[19]

[20]

[21]

[22]

[23]

[24]

[251

[26]

[27]

W. J. Franz, H. Hartenstein, and B. Bochow, "Internet on the Road via Inter-
Vehicle Communications," 2001.

J. Luo and J .-P. Hubaux, "A Survey of Inter-Vehicle Communication," 2004.

W.—W. Kao, "Integration of GPS and dead-reckoning navigation systems," in
Vehicle Navigation and Information Systems Conference, 1991.

J. Walker, E. Alicandri, C. Sedney, and K. Roberts, "In-vehicle navigation
devices: Effects on the safety of driver performance," in Vehicle Navigation and
Information Systems Conference, 1991

M. K. Krage, "The TravTek driver information system," in Vehicle Navigation
and Information Systems Conference, 1991.

J. J. Blum, A. Eskandarian, and L. J. Hoffman, "Challenges of Intervehicle Ad
Hoc Networks," IEEE Transactions on Intelligent Transportation Systems, 2004.

J. Dong, Z. Zhang, and D. Ma, "Emergent Phenomenon and The Local
Information Based DTA Model," in IEEE International Conference on Intelligent
Transportation Systems Shanghai, China, 2003.

H. Kim, D. J. Lovell, Y.-S. Kang, and W. Kim, "Data Quantity for Reliable
Traffic Information in Vehicular Ad Hoc Networks," in Vehicular Technology
Conference, 2007.

D. E. Kaufman, R. L. Smith, and K. E. Wunderlich, "An iterative
routing/assignment method for anticipatory real-time route guidance," in Vehicle
Navigation and Information Systems Conference, 1991.

L. Briesemeister, L. Schafers, and G. Hommel, "Disseminating Messages among
Highly Mobile Hosts based on Inter-Vehicle Communication."

L. Briesemeister and G. Hommel, "Role-Based Multicast in Highly Mobile but
Sparsely Connected Ad Hoc Networks," 2000.

S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, J .-P. Sheu, and "The broadcast storm problem
in a mobile ad hoc network," in ACM/IEEE international conference on Mobile
computing and networking, 1999.

H. P. Joshi, M. L. Sichitiu, and M. Kihl, "Distributed Robust Geocast: Multicast
Routing for Inter-Vehicle Communication," 2006.

D. Sormani and G. Turconi, "Towards Lightweight Information Dissemination in
Inter-Vehicular Networks," 2006.

J. Zhao and G. Cao, "VADD: Vehicle-Assisted Data Delivery in Vehicular Ad
Hoc Networks," in Conference on Computer Communications, 2006.

137

[28]

[29]

[301

[31]

[32]

H. Wu, R. Fujimoto, R. Guensler, and M. Hunter, "MDDV: A Mobility-Centric
Data Dissemination Algorithm for Vehicular Networks," 2004.

H. Xu and M. Barth, "An adaptive dissemination mechanism for inter-vehicle
communication-based decentralized traffic information systems," in IEEE
Intelligent Transportation Systems Conference, 2006.

X. Shi, J. Hu, Y. Xu, and J. Song, "A Simulation Study on Agent-network Based
Route Guidance System," in IEEE Conference on Intellegent Transportation
Systems Vienna, Austria, 2005.

A. Wegener, H. Hellbruck, S. Fischer, C. Schmidt, and S. Fekete, "AutoCast: An
Adaptive Data Dissemination Protocol for Traffic Information Systems," in
Vehicular Technology Conference, 2007.

N. Shigeki, H. Shimooura, T. Hashimoto, K. Tenmoku, and K. Mitoh, "A fast
algorithm for finding better routes by AI search techniques," in Vehicle
Navigation and Information Systems Conference, 1994.

138