Evolution Of The Intelligent Transportation Systems Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In the beginning of the 1990s, the concept of Telematics was mass-introduced in automobiles, creating state-of-the-art vehicles with applications ranging from simple information systems to advanced management information systems. Through these applications, drivers were able to exchange useful information like traffic situation at specific times, and Internet access based on cellular technologies. However, rapid development in wireless communication networks in recent years has made Inter-Vehicular Communications and Road-Vehicle Communications possible in Mobile Ad Hoc Networks (MANETs), giving birth to a new type of MANET, known as the Vehicular Ad Hoc Network (VANET) [1]. This chapter gives an overview of current research challenges and future applications for these VANET networks.


The Japanese Comprehensive Automobile Traffic Control System (CACS) program from 1973 to 1979 was the first effort to test an interactive route guidance system with an in-vehicle display unit in urban areas. This early research was soon followed by the Electronic Route Guidance System (ERGS) in the United States, sharing a common emphasis on route guidance and based on central processing systems with huge central computers and communications systems [2]. A two-way exchange of digital information occurs between instrumented vehicles and roadside equipment. The driver, based on current traffic conditions and other information required for safe driving, received a visual display of routing information. Drivers of non-instrumented vehicles were provided with the routing information through newly developed roadside displays. A roadside radio system was also developed providing the driver with traffic information and instructions in an emergency [3]. Due to limitations, these systems were never implemented in practical applications.

By the 1980s, conditions for Intelligent Transportation Systems (ITS) development had improved. Technological reforms such as the advent of mass memory, and new research and development efforts directed at practical use, made processing cheaper. In Japan, work on the Road/Automobile Communication System (RACS) project was initiated in 1984 by the governmental Highway Industry Development Organization (HIDO). The concept was to investigate the requirements of a system to provide two-way, real-time data exchange between vehicles and road-side units. This system was intended to use three microwave type beacons, these being location beacons, traffic information beacons and individual communication beacons [4].

Two projects were going on in Europe at the same time, these were the Program for a European Traffic System with Higher Efficiency and Unprecedented Safety (PROMETHEUS) (led by 18 European automobile companies, state authorities, and over 40 research institutions), and the Dedicated Road Infrastructure for Vehicle Safety in Europe (DRIVE) (under the control of the Commission of European Communities (CEC)) [5]. Although the projects were separate, close cooperation between the two was required to reach the common goal of Integrated Road Transport Environment, improvement in traffic efficiency and safety, while reducing the adverse environmental effects of the motor vehicle. The idea was to have every vehicle equipped with an on-board computer to monitor vehicle operation whilst providing the driver with road information and assistance. A centralised communications network was proposed to provide two-way communication between each vehicle and a control centre.

Early in the 1990's, the Intelligent Vehicle-Highway Systems (IVHS) project started progressing in the U.S. The general objectives of IVHS were to use advanced technologies to reduce traffic congestions, accidents and energy costs, thus improving the safety and efficiency of automobile transportation. This concept followed in line with earlier programs in Europe and Japan. Figure 2.1 presents a summary architecture of an operational IVHS program.

In the late 1990s, research in the field of inter-vehicular communication gained considerable momentum. With the availability of low-cost global-positioning system (GPS) receivers and wireless local area network (WLAN) transceivers, there was an explosion in the number of projects and consortia set up around the world to explore the potential of VANETs. These consortia projects involve several constituencies, including the automotive industry, the road operators, tolling agencies and other service providers, most of which funded by National governments. Figure 2.2 depicts a non-exhaustive list of pioneering activities and milestones showing the evolution of the VANET research around the globe.

Fig. 2.1 Advanced Traffic Management and Driver Information System of an IVHS [6]

Fig 2.2 Overview of pioneering activities and research around the world [7]


There are several issues related to vehicular networking systems from distant fields of expertise ranging from applications development up to economical issues. Some of the core research challenges include:

- Physical and Media Access Control (MAC) layers for vehicular communications

Wireless Access Technologies

Spectrum issues

Transmission Power Management

- Communications architectures for ITS

Broadcasting techniques

Message Dissemination

- Privacy Issues

- Security Trust and Counter Measures

- Routing Techniques

- Modeling and Simulations.

2.2.1 Wireless Access Technologies

There are several emerging wireless access standards that can provide the physical and MAC layers for VANET connectivity. The aim is to provide a set of air interface protocols and parameters for high-speed vehicular communications using one or more of several available media [8]. Cellular Technology

The area supplied with the radio service is divided into regular shaped cells and each of these cells is assigned multiple frequencies which have corresponding radio base stations. Cells can be macro, micro, pico, femto or umbrella. The group of frequencies is reused in other cells, provided that they are not reused in adjacent neighboring cells due to co-channel interference. To distinguish signals from several different transmitters, frequency division multiple access (FDMA) and code division multiple access (CDMA) are employed.

Cellular technologies can be split up in four generations as follows:

1G: - voice signals are modulated to higher frequencies in the 150MHz range

2G: - voice signals are digitally encrypted, compressed and multiplexed

- the introduction of packet switched domain (2.5G) provided data rates between 56 kbit/s and 115 kbit/s (General Packet Radio Service GPRS)

- Enhanced Data rates for GSM Evolution (EDGE) networks introduced 8PSK encoding, and achieved data rates of up to 236.8 kbit/s

3G: - simultaneous use of speech and data services at speeds of up to 14.0 Mbit/s downlink, and 5.8 Mbit/s uplink (includs the Universal Mobile Telecommunications System (UMTS) and IMT Multi‑Carrier (IMT‑MC))

4G: - IP packet switched networks

- target peak data rates of up to 100 Mbit/s for high mobility access and up to 1 Gbit/s for low mobility access

- Frequency-domain equalization schemes, such as OFDMA are employed, combined with Multiple in Multiple out (MIMO) antennas, dynamic channel allocation and channel-dependent scheduling

- actively being researched [9].

Figure 2.3 plots the data rate against mobility and communication range trade-off.

Fig 2.3 Data Speed against Mobility for wireless systems [10]

Benefits of cellular technologies include nationwide coverage and reliable security, however suffer from bandwidth constraints, and have high latency with increased accesses. Since the spectrum under use is a licensed band, there is an increased cost per bit thereby making Internet accesses expensive [10]. IEEE Technology

IEEE 802.11p is a draft amendment to the IEEE 802.11 standard defining enhancements required to support both vehicle to vehicle (V2V) and vehicle to infrastructure (V2I) communication operating at speeds of up to 200 km/hr [7]. The 802.11p Task Group was formed in September 2004 and in an official work plan has scheduled the approved 802.11p amendment to be published within the fourth quarter of 2010 [11]. The main challenges for the 802.11p standard are frequency spectrum availability and channel fading.

The 802.11p standard outlines the Physical (PHY) and MAC (lower part of the Data Link) layers of the Open System Interconnection Reference Model (OSI Model) as depicted in figure 2.4. Both layers have been derived from the IEEE 802.11a standard with small modifications in order to achieve a robust connection and a fast setup for moving vehicles.

The IEEE 1609 Family of Standards for Wireless Access in Vehicular Environments (WAVE) defines the architecture and a complementary, standardised set of services and interfaces which make use of the 802.11p layers. WAVE provides the communication model foundation required for a broad range of applications in the transportation environment, such as vehicle safety, traffic management, enhanced navigation, and automated tolling [13].

Fig 2.4 WAVE Protocol Stack [12]. 802.11p standard defined in ASTM E2213 ISO 21215 IEEE 802.11p PHY Layer

The PHY layer of the 802.11p has been derived from the 802.11a standard, and uses orthogonal frequency-division multiplexing (OFDM). It employs 64-subcarrier OFDM, 52 of which used for actual transmission consisting of 48 data sub-carriers and 4 pilot sub-carriers, used for tracing the frequency offset and phase noise [14]. The short and long training symbols, located in the preamble of every data packet, are used for signal detection, coarse frequency offset estimation, time synchronisation, and channel estimation. In order to eliminate the Inter Symbol Interference introduced by the multi-path propagation, a guard time is attached to each OFDM data symbol. As a countermeasure against the fading channel, information bits are coded and interleaved before being modulated on the sub-carriers [14]. Figure 2.5 provides an overview of the packet format as used in both the 802.11a and the 802.11p standards.

In order to increase the tolerance for fading and multi-path propagation effects in vehicular environments, 802.11p uses a 10 MHz frequency bandwidth. By having a smaller frequency bandwidth, the effects of Doppler spread are reduced. Since the frequency is halved, the guard interval and symbol length are doubled and the carrier spacing is reduced by half, reducing the inter-symbol interference caused by multi-path propagation [15].

Fig 2.5 Packet format for both 802.11a and 802.11p standards [15]

Table 2.1 compares the PHY layer implementation values of the 802.11p with the 802.11a standard.

Table 2.1 Comparison of physical layer implementations in 802.11a and 802.11p [15]

The 802.11p standard operates in the 5.8 GHz and 5.9 GHz frequency bands. In order to support larger communication range in vehicular environments, the 802.11p defines four classes of maximum allowable Effective Isotropic Radiated Power (EIRP) up to 44.8 dBm (30W). The largest value is reserved for use by approaching emergency vehicles [14]. IEEE 802.11p MAC Layer

The 802.11p standard uses the Enhanced distributed channel access (EDCA) mechanism for prioritised channel access, including the 'listen before talk' (LBT) and a random back-off algorithm. This algorithm uses both a fixed and random waiting times, consisting of number of slots, each slot being 8μs long. The random waiting time parameter is drawn from a Contention Window (CW), and is doubled on every failed transmission, until a specified limit is reached. Prioritisation is provided through four defined channels with different access parameters. Packets are prioritised as either background traffic, best effort traffic, voice traffic or video traffic [14]. Table 2.2 lists the parameters defined by the 802.11p standard for the EDCA mechanism, while figure 2.6 plots the waiting time for the different access categories.





















Table 2.2 EDCA Parameter Set as used by the IEEE 802.11p [14]

where: AC - access category

BK - background traffic

BE - best effort traffic

VO - voice traffic

VI - video traffic

CWmin - initial size of CW

CWmax - maximum possible value for CW

AIFSN - fixed waiting time

In order to make optimal use of the short period of time during which vehicles are within communication distance, communication overhead is kept low be removing the frame exchange. A WAVE service announcement frame (WSA) is periodically transmitted by a provider station (STA). This management frame has no transmission interval restriction, and does not contain any authentication. Synchronisation is provided from an external time reference (see figure 2.7). WAVE's STAs use the clear channel assessment (CCA) busy fraction to determine the channel occupancy percentage. This value is required as base for congestion control mechanisms [16].

Fig 2.6 Wait-times for the access categories caused by contention [17]

Fig 2.7 WAVE channel Synchronisation [23] IEEE 1609 Family of Standards for WAVE

The lack of homogeneous communications interfaces between different automotive manufacturers was the initiative behind the IEEE 1609 Family of Standards for WAVE. WAVE standards provide a sufficient foundation regarding the organisation of management functions and modes of operation of system devices and define the architecture and a complementary, standardised set of services and interfaces that collectively enable secure V2V and V2I wireless communications.

WAVE standards consist of four trail use standards which have full use drafts under development:

- IEEE P1609.1 standard - Resource Manager [18]

- specifies the services and interfaces of the resource manager application;

- describes the data and management services offered within the WAVE architecture;

- defines command message formats and the appropriate responses to those messages, data storage formats that must be used by applications to communicate between architecture components, and status and request message formats.

- IEEE P1609.2 standard - Services for Applications and Management Messages [18]

- defines secure message formats and processing;

- defines the circumstances for using secure message exchanges and how to process these messages based upon the purpose of the exchange.

- IEEE P1609.3 standard - Networking Services [18]

- defines network and transport layer services, including addressing and routing, in support of secure WAVE data exchange;

- defines Wave Short Messages, providing an efficient WAVE-specific alternative to IPv6 (Internet Protocol version 6) that can be directly supported by applications;

- defines the Management Information Base (MIB) for the WAVE protocol stack.

- IEEE P1609.4 standard - Multi-Channel Operation [18]

- provides enhancements to the IEEE 802.11 Media Access Control (MAC) to support WAVE operations.

Figure 2.8 shows the architecture of WAVE's Services

Fig 2.8 WAVE Architecture Integration Component Services [19] ISO TC204 WG16 Technology

ISO TC204 WG16 is formally authorised to write CALM standards (Communications Architecture for Land Mobile environment, and Continuous Air Interface for Long and Medium range). The aim of CALM is to provide a standardised set of air interface protocols for the best use of resources available for:

- short, medium and long range communications;

- high speed guaranteed response time;

- V2V and V2I communication using one or more of several media including 802.11p, GSM/GPRS, UMTS, Infrared Communication and wireless systems in the 60 GHz band with multipoint (mesh) transfer;

- lower layer protocols to enable seamless transfer between point to point sessions;

- upper layer protocols to enable transfer between media [20].

The CALM family of International Standards is explicitly designed to support large volumes of data required for information and entertainment by handling quasi-continuous communications from one fixed station to another (heterogeneous handovers), communications of protracted duration, and short messages and sessions of high priority with stringent time constraints [21].

The network layer supports the following networking protocols:

- Internet Protocol Networking (including IPv6 kernel and header compression);

- non-IP mobile connectivity and routing in fast ad-hoc situations;

- common service access points (SAP) towards the lower layers for management services [21].

The management services defined provides:

- quasi continuous, protracted and short term communication possibilities via different communication points within any specific medium;

- network layer handover using Internet Engineering Task Force's Network Mobility (IETF NEMO) functionality;

- management of Quality of Service (QoS) parameters required by user services;

- interpretation of high-level instructions onto media specific actions [21].

2.2.2 Frequency Spectrum

The intended usage period for V2V communication systems is estimated for a minimum of 20 years, and throughout this period, spectrum availability has to be guaranteed. Dedicated short-range communications (DSRC) was designed for automotive use utilizing cheap, short-range, two-way Line-of-Sight (LoS) communication with sufficiently high bandwidth. DSRC applications lend themselves to localized road communications with distributed decentralized deployment [22].

To benefit from its ad-hoc mode, the DSRC workgroup decided upon the 5 GHz wireless band due to its spectral environment and propagation characteristics and low weather dependence. Table 2.3 compares the DSRC band with other wireless technologies. Although the cellular and WiMax bandwidths appear to provide higher throughput, sharing that bandwidth over larger geographical area reduces the effective data rate. The limited low latency experienced in the DSRC band, and low mobile connectivity are due to the short-range nature of the technology, leading to frequent topological changes [23].

Table 2.3 DSRC compared to other wireless technologies [23]

Figure 2.9 plots the data rate performance against distance range for the DSRC technology.

DSRC operates in stringent environments having fast communications to maintain connection with vehicles at all times, has strict QoS committed to predefined threshold delays for safety messages, uses minimal transmission power, and maintains privacy and anonymity of roaming users.

In October 1999, the United States Federal Communication Commission (FCC) allocated 75 MHz DSRC spectrum at 5.9GHz for VANETs as outlined by the International Telecommunication Union Radio-communications sector's (ITU-R). The 75 MHz are divided in seven 10 MHz channels and a safety margin of 5 MHz at the lower end of the band. The center channel is the control channel, on which all safety relevant messages are broadcasted. The remaining channels are used as service channels, where lower priority communication is conducted after negotiation on the control channel. As an option, two adjacent service channels may be used as one 20 MHz channel [14]. Figure 2.10 shows the DSRC channel allocation.

Fig 2.9 DSRC Performance Envelope [24]

Unfortunately a continuous spectrum of 75 MHz in DSRC band was not available in Europe since the 5.9 GHz band is currently allocated for military radar applications such as missile and rocket tracking radar and surveillance radar, and fixed satellite services [25]. As such, in August 2008, the European frequency regulation Conférence Européenne des Administrations des Postes et des Télécommunications (CEPT) and the European Commission (EC) published a decision to harmonise the 5.9 GHz band whereby two 10 MHz channels are allocated between 5.875 and 5.925 GHz for safety critical applications (control channel) thus allowing for worldwide harmonisation. Non-safety critical and commercial applications are proposed to be allocated either in the 5 GHz Radio Local Area Network (RLAN) band, or in the 5.8 GHz Industrial, Scientific and Medical (ISM) band [8].

Fig 2.10 DSRC available channels [24]

In Japan, the development of ITS is considerably different. Japan's DSRC spectrum has been allocated in the 5.770 and 5.850 GHz band. At present, Electronic toll collections (ETC) uses 20 MHz of this band, and the remaining 60 MHz is currently under consideration for other ITS applications by the Japanese Ministry of Internal Affairs and Communications and Industry [25].

Figure 2.11 compares the frequency bands considered internationally for ITS.

Fig 2.11 Frequency bands allocated internationally for ITS, and ISM frequency band [25]

2.2.3 Transmission Power Management

Power management in VANETs is not concerned about energy efficiency since its nodes are energy-rich, but rather about the transmission power. If the transmitted energy, determined by transmission power, modulation and error coding, is too low, the wireless channel may attenuate the transmitted power so much that it is swamped by thermal noise. This is overcome by selecting the transmission energy to be high enough to reach all receivers within the message range with highest probability, assuming that in the process there are no collisions [26]

The point of using minimal power is important, since higher signal powers lead to other DSRC devices increasing their signal power as well. This leads to a communication environment full of interferences, with the result of hiding low power signals, such as the GPS signal [23]. There are several algorithms proposed to adjust the transmission power as necessary for the targeted range adapting to channel characteristics such as path loss and shadowing effect caused by buildings and vehicles intervening between vehicles. These power control algorithms results in a higher communication reliability since collisions are minimised [27]. Figure 2.12 compares the percentage packet loss as transmission power increases for an average packet sending time of 100 ms.

Fig 2.12 Packet loss rate vs. power level (packet sending interval=100ms) [27]

2.2.4 Privacy Concerns

Communication between vehicles makes it possible to accurately track and estimate the location of a vehicle, threatening and breaching the privacy of the vehicle's user. Furthermore, the location tracking information can be misused by an adversary, and by identifying the location based services (LSB) applications access by the vehicle, private information about the vehicle's user are obtained.

To achieve adequate privacy [28]:

- pseudonyms should be used as identifiers instead of real-world identifiers;

- pseudonyms are changed, and the number of pseudonyms vary depending on application and its privacy threat model;

- pseudonyms are only mapped to real-world identifiers in special situations;

- properties and privileges are cryptographically bound to one of more pseudonyms.

Vehicles could reduce this threat by creating networks of trust and ignore information from distrusted senders. A trusted communication requires:

- sender is conclusively accepted as a trusted source;

- while in transit, the contents of the sender's message are not tampered.

2.2.5 Security Trust

Unlike the Internet, where security has been let to the application layer, the network architecture for vehicular networks can incorporate security protocols in the network stack from the beginning as displayed in figure 2.13. There are a number of security challenges [29]:

- Authentication versus Privacy:

To prevent one vehicle from claiming to be hundreds in order to create the illusion of a congested road, each vehicle should be bound to a single identity. However if the vehicle's permanent identity is spoofed, the driver's privacy is violated.

- Availability:

Vehicular networks will require real-time responses and guarantees. This will make applications vulnerable to Denial of Service (DoS) attacks.

- Low Tolerance for Errors:

Vehicular applications cannot rely on probabilistic schemes to provide security due to the life-or-death nature of the applications. Security must focus on prevention of attacks rather than detection and recovery.

- Mobility:

Mobility patterns of vehicles on the same road exhibit strong correlations. The transitory nature of interactions in a vehicular network does not permit the utility of reputation-based schemes.

- Key Distribution

Vehicles are manufactured by different manufacturers, so installing keys at factories require coordination and interoperability between manufacturers. Another option is to have a Certificate Authority certifying and authenticating each vehicle's public key.

Fig 2.13 Reference model view on the security system [30]

The IEEE 1609 Family of Standards define an architecture and a complementary, standardised set of services and interfaces that collectively enable secure V2V and V2I communications. The P1609.2 standard outlines the secure message formats and the processing of those secure messages within the WAVE architecture using the Public Key Infrastructure (PKI). Methods used to secure WAVE management messages and application messages are defined, including the administrative functions required to support core security functions, with the exception of vehicle originating safety messages. Each vehicle is issued a set of certificates in order to achieve anonymity [31]. Figure 2.14 shows the IEEE 1609 WAVE security architecture, while in figure 2.15, the message format is depicted. The 'Signer' block is responsible for the security header, while the 'Signature' is the security footer. The 'Target Application' is signed according to the specific application. The 'Generation Time', 'Expire Time', and 'Location' check the signed message location, time and expiration. They also verify the certificate scope against location of transmission, and check if the certificate expired.

Fig 2.14 IEEE 1609.x security architecture [32]

Fig 2.15 IEEE 1609.2 message format [32]

2.2.6 AD-HOC Routing Protocols

Routing in VANETS has attracted a lot of attention. This derivative of MANETs is characterised by a strong mobility of nodes, a high dynamic and specific topology, a significant loss rate, and a very short duration of communication. Many routing solutions have been proposed for MANETs to deal with the node's mobility including discovering routes, detecting stable clusters, using the node's movement for message transportation and using the broadcasting technique for message forwarding [33]. However the specific properties and environment of VANETs, including [34]:

- signal reception more difficult due to radio obstacles such as road-along distributed buildings;

- interference from noisy radio waves;

- rapid topological changes;

- frequent fragmentation, leading to a small effective network diameter;

- variable highly dynamic scale and network density;

- large scale network;

- network topology effected by driver's behavior reacting to data received from the network;

effect the performance of these routing solutions, and further studies are required to evaluate the suitability of existing protocols.

As presented in figure 2.16, ad-hoc routing protocols can be classified into five main categories:

- Pro-Active Routing

- Reactive Routing

- Flow-Oriented Routing

- Hierarchical Routing

- Geographical Routing

An example for each type of routing protocol has been included in figure 2.16.

Fig 2.16 Taxonomy of Routing Protocols in VANET together with an example of each Pro-Active Routing

Pro-active routing uses link information existing in the network to compute packet forwarding. All routing information is maintained in the background regardless of communication requests. Control packets are periodically broadcasted and flooded among nodes to maintain the paths and link states between any pair of nodes even though paths may never be used. A table is constructed and maintained by each node containing an entry to all possible reachable destinations [35].

Destination Sequenced Distance Vector Routing (DSDV) is an example of a pro-active algorithm. It makes use of the Bellman Ford algorithm to compute the single source shortest path between the source and the destination. DSDV uses sequence numbers to avoid routing loop issues. All nodes, periodically, broadcast routing information to their neighbors. In order to reduce overhead, nodes only broadcast full dumps of their routing tables infrequently, and periodically send small incremental updates [36]. Figure 2.17 shows a network with four nodes using DSDV, while table 2.4 contains the routing table for node A.

This algorithm is easy to implement, and benefits from the fact that there is no route discovery process required when a packet needs to be forwarded, which is a good property for low latency real-time applications since route to destination is maintained in the background and is always available upon lookup. However it is bandwidth hungry and highly inefficient (brute force approach) as it requires a very large overhead to maintain the tables and even fails to converge with high node mobility, as the case with VANETS. DSDV also has a low packet delivery ratio and has a limit on the number of nodes that can join the network [35].

Fig 2.17 Example of a network using DSDV routing algorithm [37]

Destination Address

Sequence Number

Next Hop

Hop Count






















Table 2.4 DSDV routing table for node A [37] Reactive Routing

Reactive routing also uses link information to compute packet forwarding, however it opens a route only when a node requires the link. This type of algorithm maintains only the routes currently in use, thus reducing the burden on the network. A route discovery phase is initiated upon request whereby packets are flooded in the network until a path is found and route computed [35].

Ad-Hoc On Demand Distance Vector (AODV) uses the Reactive algorithm. It is capable of both unicast and multicast routing. Local connectivity is checked on a regular basis by listening to retransmission or sending Hello messages. When a node requires sending data to a destination, it broadcasts Route Request (RREQ) packets to initiate the path discovery process. All nodes receiving the RREQ and are not the destination, re-transmit the packet, until it is eventually received by the destination. The destination receives the RREQ packet from different nodes and paths, and chooses the shortest path travelled by unicasting a Route Reply (RREP) along this best reverse path. Data packets are then sent containing the destination address only [38].

AODV benefits from the concept that data packets are forwarded over the latest route to destination; however there is no guarantee that when the RREP packet is sent, the intermediate nodes are still available and the path is still consistent, given the high mobility scenario. Also this algorithm suffers from heavy control overhead as the same RREQ packets are relayed multiple times by different nodes [35].

Fig 2.18 AODV Routing [35] Flow-Oriented Routing

Flow-oriented algorithms are unicast routing protocols, and find routes on demand by following current flows of controlled floods of unicast packets generated within the network.

Spatially Aware Packet Routing (SAR) can be categorized as a flow-oriented protocol. It takes advantage of the fact that although VANETs have high node mobility, they follow the road path infrastructure. When a source needs to send a packet to a destination, using Dijkstra's algorithm, the shortest route the packet needs to undertake is computed based on spatial information extracted from digital road maps, and a set of vertices at the intersections, called the Geographic Source Routes (GSR), are generated. The GSR, together with the coordinates of the source and destination are included in the packets sent from source node [39]. Figure 2.19 exhibits a scenario whereby the road information aids in predicting a permanent topological hole, making the correct decision in forwarding packet to neighbor node B.

Fig 2.19 Use of spatial awareness in data forwarding [39]

SAR was designed to overcome problems in networks experiencing frequent topology holes, however there is no guarantee that the path chosen by the routing algorithm is the optimal path as a forwarding node might not locate a suitable neighbor. Also SAR tends to be slow when exploring new routes especially in networks with a large number of intersections. This routing algorithm employs the store-carry-forward paradigm whenever a node has no neighbours closer to the destination than itself. This model may cause a temporary loop between two vehicles if the neighbour routing table is outdated [40]. Hierarchical Routing

Hierarchical routing protocols have the choice of proactive or of reactive routing concepts depending on the hierarchic level where a node resides. Nodes are divided into clusters, and initially establish some proactively prospected routes. Data packet forwarding uses reactive flooding on the lower levels. These types of algorithms require proper attribution for the respective levels.

Cluster Based Location Routing (CBLR) takes advantage of the hierarchical concept. The network is divided into a number of clusters, each having a cluster head node and a group of members within the heads range. Head node is periodically broadcasting hello beacons (keep-alive) to its members and keeps an up to date routing table of nodes within cluster. Within each cluster, head nominates a number of bridge nodes through which it can forward messages to other clusters. Head node also has the responsibility to maintain a routing table for neighbor clusters, and whenever the head needs to forward packets to a destination not within its routing tables, a Location Request (LREQ) packet is broadcasted to other clusters through the bridge nodes [41]. Figure 2.20 shows an ad-hoc network organised in the different clusters as specified by CBLR.

Fig 2.20 Cluster architectural concept

CBLR's pro-active updating of the routing tables by the head nodes induce an overhead in the system, and as node mobility increases, the algorithm performs very poor as nodes are constantly and quickly changing clusters and roles. CBLR also assumes that the transmissions of packets are synchronised [41], which is not always the case for real world scenarios. Geographic Routing

Geographic routing assumes that each node knows its location. Forwarding decisions of a node are primary based on the position of the packet's destination, and on the position of the node's one hop neighbors. The source node stores the destination's position in the packet's header. The location of the one hop neighbors is obtained through periodic broadcasting of beacons.

Geographic routing does not exchange link state information, and do not maintain established routes. Routes are determined based on geographic location of a node's neighbors. This property makes such protocols more robust to the highly dynamic environment of VANETs [35]. Non-Overlay Geographic Routing

The fundamental principle of the non-overlay concept is the greedy approach, whereby a node forwards packets to its neighbor closest to the destination. The forwarding strategy fails when no neighbor is closer to the destination than the node itself, i.e. the packet has reached a local maxima. At this point, a recovery algorithm is initiated [35].

Greedy Perimeter Stateless Routing (GPSR) implements the geographic non-overlay algorithm. Packets are greedily forwarded to nodes which are geographically progressively closest (shortest euclidean distance) to the destination node, as demonstrated in figure 2.21. This process is repeated until the packet reaches the destination or a local maximum is reached, at which point the system switches to the recovery Perimeter Forwarding Mode [42].

Fig 2.21 Greedy Forwarding [42]

In GPSR, all nodes periodically broadcast proactive hello messages to neighbor nodes in order to maintain a local routing table containing their one hop neighbors. As a measure to reduce overhead, sender nodes include their position in packet headers, thus replacing the next beacon message [42].

GPSR is a responsive routing algorithm, which makes it suitable in vehicular environments; however its performance is greatly reduced from the Neighbor Break Link (NBL) setback. NBL is experienced when a node would have moved out of a node's transmission range by the time a data packet is forwarded, and is the drawback of the greedy nature of the algorithm which forces nodes to forward to intermediate hosts which are in the limit of the transmission range. Another disadvantage of GPSR is the fact that perimeter forwarding's planar graph traversal requires strictly identical radio ranges, and may still fail since the assumption that any two nodes within threshold distance are connected is not always true due to obstacles and interferences [35]. Overlay Geographic Routing

Overlay routing has the distinctive characteristic that it operates on a set of illustrative nodes overlaid on top of the existing network at strategic places, typically at junctions, since packet routing decisions are made at intersections before turning into different road segments [35].

Anchor Based Street and Traffic Aware Routing (A-STAR) proposed in [43] and employs the geographic overlay procedure. It makes use of statistically weighted road maps, where streets served regularly by city buses are assigned a higher metric. A-STAR is based on the assumption that these main streets have better connectivity than other secondary roads due to denser traffic. The routing protocol then calculates the shortest path between source and destination through these weighted streets and computes a list of anchor points at each junction. Data packets are forwarded in a greedy manner, and whenever a local optima node is reached and greedy forwarding fails, a new anchor path is recomputed, and street is marked as temporary out of service [43]. Figure 2.22 shows A-STAR's computed shortest path to destination through statistically weighted roads.

Fig 2.22 A-STAR's packet trajectory to destination

Although A-STAR makes use of high connectivity streets, it causes flooding and severe bandwidth congestions on these main streets, while secondary roads may still offer good connectivity. Another setback for A-STAR is the fact that it makes use of statistically rated maps rather than dynamically weighted, which does not reflect actual real time traffic conditions [44].

Connectivity Aware Routing (CAR) is another example of an overlay geographic routing protocol presented in [45]. Nodes periodically broadcast a hello beacon with their velocity vector. The broadcast period adapts dynamically proportional to the number of registered neighbors (node density) to reduce the risk of flooding the network with the hello messages. When a node requires sending data packets to a destination, it first computes the path through a set of anchor points, and starts the Preferred Group Broadcast (PGB) path discovery request. Packets are then forwarded using the Advanced Greedy Forwarding (AGF) algorithm over the anchored path [45]. Figure 2.23 presents the anchor points created at strategic points where the velocity vector varies by an angle greater than 18o.

CAR routing has the advantage that it chooses paths with better connectivity and lower delays; however the selection rule of anchor points may add needles nodes in the path. Another problem experienced by CAR is that movement of the intermediate nodes may lead to disconnections due to the time lapse between path discovery and the actual packet sending, given the high node mobility of VANETs [46].

Fig 2.23 CAR anchor nodes

2.2.7 Modeling and Simulation

Real-life implementation and testing of protocols for VANET networks is not easily done, and thus performance and feasibility evaluation are computed through modeling and simulations. One of the main challenges posed by VANET's simulations is the faithful characterisation of vehicular mobility, leading to realistic non-uniform distribution of cars, velocity and unique connectivity dynamics [47].

Road traffic cannot be easily modeled as random node movement in a straight-forward way using the classical MANET approach, since traffic follows certain paths, rules, signs, and other traffic flow. Network density changes dynamically depending on location, events, or time of the day. A realistic mobility model implementation is as relevant as a realistic ad hoc network model in order to obtain good quality simulation results. One could either build a sophisticated road traffic mobility model on top of some network simulator, or use mobility traces from another source, although such traces would be static [8]. Figure 2.24 shows the historical evolution of mobility models strategies and techniques used in VANET protocol research and application simulations. Transportation and traffic science classifies traffic Simulation models into macroscopic, microscopic, or mesoscopic, depending on the granularity detail required.

Fig 2.24 Mobility modeling historical evolution [48]

Early approaches did not reflect actual car movements, and more complex solutions were developed. Recent simulation breakthrough was achieved in tightly bi-directional coupled road traffic micro simulation and network simulation, where it is possible to observe how VANET functionality affects driver's behavior, hence changing the network parameters [8]. Unfortunately such solution is rather complex due to the inherent intensive intercommunications involved between different simulation tools. Figure 2.25 depicts an architectural view on mobility modeling in VANET simulations.

Fig 2.25 VANET mobility modeling techniques [48] Random Movement

In the initial stages of ad hoc network research, node mobility movement was simulated in a completely random manner. In 1997, the European Telecommunications Standards Institute (ETSI) recommended mobile movement for the evaluation of radio transmission technologies of the Universal Mobile Telecommunications System (UMTS) along the Manhattan Grid [49]. This recommendation, however, was intended for pedestrian mobility modeling, and vehicle's mobility still used plain random node movement. These mobility models were very easy to implement, and allowed for straightforward adaptations [48]. Real World Mobility Traces

By 2003, real world vehicles were tracked using on-board and subsidiary devices, and the vehicles position recorded at regular intervals. These mobility traces were then post-processed, stored, and used as mobility models. Such patterns provide the most realistic vehicle movement possible in network simulations; however its use is limited to a small set of mobility parameters [48]. It is not possible, for example, to vary the node's model density. Artificial Mobility Traces

The restriction of fixed mobility parameters was overcome by generating movement traces artificially in [50]. The realism of node movement was only constrained by the simulator's complexity used. Artificial mobility models had the advantage of providing simulations with very realistic traces, and also allowing for parameters to be freely adjusted, with the benefit of observing the influence of such changes on the simulator's outcome. However through these simulations, it was not possible to observe how the network traffic is influencing the node mobility, since traces are still static [48]. Bidirectional Coupled Simulators

Bidirectional coupled simulators close the loop between road traffic simulation and network traffic generation. This requires intensive cooperation among the different simulation tools. More detailed insights can thus be derived on the effect of network traffic. An inherent property of such architecture is that the results of simulations cannot be re-used in the form of trace files, since these simulators compute node mobility on-the-fly [48]. Two inter-dependent processes are running concurrently, and both processes share updates about the simulated vehicles at regular intervals in two alternating phases [48]:

- Network simulation sends parameter changes to the road traffic simulation altering the driver's behavior or the road attributes and influencing vehicles routing decisions.

The simulation time advances only for the network simulator.

- Road traffic simulator performs traffic computations based on these new parameters and sends vehicle movement updates to the network simulator.

The simulation time advances only for the traffic simulator.

Table 2.5 illustrates the benefits and drawbacks of the different types of mobility models, and also includes the supported frameworks for the respective categories.

Table 2.5 Mobility Model categories, supported frameworks, and their advantages and setbacks [48]