This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Wireless communication is used to transfer information between two or more points that have no physical connection. The distance between communicating points can be short, such as a few meters for AC remote control, or even millions of kilometers for deep space radio communications. It encompasses various types of personal digital assistants (PDAs), portable two-way radios, cellular telephones and wireless networking. Some other examples of wireless technology are cordless telephones, garage door openers, wireless computer mice, keyboards and headset, radio receivers, satellite television etc. Wireless operations allow services such as long range communications. These types of communications are impossible or impractical to implement with the use of wires.
1.1.1 Common examples of wireless equipments include:
Telemetry and traffic control systems.
Remote control devices using infrared and ultrasonic waves technology.
Modulated laser light systems used for point-to-point communications.
SMR (Specialized Mobile Radio) and professional LMR (Land Mobile Radio) used by industrial, business and public safety systems.
Consumer two way radio including GMRS (General Mobile Radio Service), FRS Family Radio Service, and Citizens Band ("CB") radios etc.
The Amateur Radio Service (Ham radio).
Consumer & professional Marine VHF radio.
Radio navigation equipments that are used by aviators and air traffic control systems.
Cellular telephones and pagers.
Connectivity for portable and mobile applications.
Global Positioning System (GPS)  that allows drivers of cars, captains of ships, and pilots of aircraft to ascertain their location anywhere on earth.
Cordless computer peripheral devices. For example the cordless mouse, keyboards and printers can be linked to a computer via wireless using technology such as bluetooth.
Limited-range devices such as cordless telephones.
Satellite television which broadcasts from satellites in geostationary orbit. Typical services use direct broadcast satellite that is used to provide multiple television channels to viewers.
1.2 What are Ad hoc Networks?
The networks without any centralized or pre-established infrastructure are known as Ad hoc networks. Ad hoc networks are a collection of self-governing mobile nodes . Self-configuration and self- healing are the key characteristics of ad hoc networks.
1.2.1 Characteristics of ad hoc networks
The characteristics of these networks are as follows:
They communicate via wireless means.
Nodes act both as hosts and routers.
There is no centralized controller and infrastructure.
Network topology is dynamic and frequent routing updates occur.
They are autonomous and no infrastructure is required.
Can be set up anywhere in short time.
More energy constraints.
Security is limited.
Self-configuring nodes also serve as routers.
Self-healing through re-configuration process.
Scalable (accommodates addition of nodes).
1.2.3 Limitations of Ad Hoc Networks:
Some limitations of ad hoc networks are:
Every node of the network must have full performance
System loading effects throughput
Reliability requires a sufficient density of nodes. Sparse networks can have problems
Large networks can have latency.
1.3 What are MANETs?
A Mobile Ad hoc Network (MANET) is an autonomous collection of mobile nodes that can communicate over relatively bandwidth-constrained wireless links. Nodes in the network are mobile and network topology may change unpredictably over time. The network is decentralized. Nodes perform all network activities including discovering the topology. Messages delivery is also executed by the nodes themselves. This means that routing functionality is incorporated into mobile nodes.
1.4 What are VANETs?
Vehicular ad hoc Network (VANET) is a type of ad hoc network in which moving vehicles act as nodes of the network. Vehicles communicate wirelessly through multi-hop paths. Vehicles use intermediate vehicles as relays to carry data to final destinations. Higher node mobility, rapidly changing network topology are the main characteristics of VANETs. This means that network topology is highly dynamic .
Fig. 1.1 vehicle to vehicle communication in VANETs
Main objective of VANETs is safety and handling of emergency situations. VANETs assist drivers to communicate among themselves to avoid any critical situation e.g. road side accidents, traffic jams and speed control etc. In case of an accident or sudden hard breaking, a notification is sent to the preceding cars. Cooperative driver assistance system may be used for message propagation. It exploits the exchange of sensor data or some status information among cars. The drivers thus get information about obstacles and hazards. Besides safety applications VANET also provide comfort applications to the road users. For example, weather information, mobile e-commerce, Internet access and other multimedia applications . VANETs do not use any telecommunication infrastructure. However, infrastructure is used in intelligent transportation systems (ITS) [5, 6].
VANET is a special type of MANET where vehicles act as nodes. Unlike MANET, vehicles move on predefined roads/paths. There are many challenges in VANET which need to be solved to provide reliable services.
Reliable routing in VANET is one of the major issues. Vehicles have dynamic behavior in VANETs and high speed of vehicles make routing more challenging. Routing in MANETs (Mobile Ad hoc Networks) is not as difficult as in VANETs. This is due to less mobility of nodes. Many routing protocols such as AODV , DSR  have been developed for MANETs. These protocols fail to perform for VANETs due to high mobility of vehicles. Frequently changing network topology of VANETs hinders path determination as well as path maintenance process.
Scarcity of bandwidth in wireless communication is another issue. Available bandwidth may be wasted by the unnecessary rebroadcast of data and control packets. Simple broadcasts use flooding where every node in the network forwards the packet each time it is received. This creates broadcast redundancy. When nodes density in the network is high, more collisions and contentions are triggered as a result of redundant transmission. Furthermore network bandwidth is also wasted due to such redundant transmissions. This is a broadcast storm problem. In case of VANETs, congestion (e.g. congestion at junctions) intensifies the problem which may collapse the entire network. Ad hoc routing protocols like AODV  experience overhead and consume a large portion of bandwidth during route discovery, routing table updating and route error reporting phases. These protocols therefore, cannot be applied to VANETs.
1.4.1 Characteristics of VANETs
VANETs have some unique characteristics which make them different from MANET as well as challenging.
188.8.131.52 Highly dynamic topology
The topology of VANET changes frequently because vehicles move at a high speed.
184.108.40.206 Frequent disconnected network
Highly dynamic topology results in frequent disconnection occur between two vehicles when they are exchanging information. In sparse networks, disconnection occurs frequently.
220.127.116.11 Mobility modeling
The mobility pattern of vehicles is dependent upon traffic environment, roads structures, driver's driving behavior and the speed of vehicles.
18.104.22.168 Battery power
Vehicles have battery power that can be used for communication and processing.
1.4.2 Applications of VANETs
Examples of some of the VANET's applications are given below.
Cooperative assistance: distribution of data (warning of accidents).
Car-to-Mobile devices: applications used for communication between the car and mobile devices (e.g. mobile phone, laptop etc).
Car-to-Enterprise: communications between the car and companies (e.g. gas stations, restaurants, parking areas etc) which provide services on road.
Car-to-infrastructure: Hot spots send information to cars giving road and traffic information and car access to Internet etc.
Car-to-Car: exchange of information between car users such as files, traveling, chat, games and entertainment etc.
1.4.3 Categories of routing protocols in VANETs
Routing protocols in VANET can be categorized into following types :
22.214.171.124 Topology based routing
These protocols use route discovery process and maintain it in a table. The sender then starts transmitting data. These protocols are further divided into:
These protocols are also known as table driven routing protocols. These protocols periodically exchange the knowledge of topology among all the nodes of the network. These protocols consume a lot of bandwidth for periodic updates of topology. Proactive protocols monitor peer connectivity periodically to ensure the availability of any path amongst active nodes. Because these protocols periodically update topology information, a lot of band width is consumed. This makes them unsuitable for VANETs.
"On demand" or reactive routing protocols were designed to overcome the overhead created by proactive routing protocols. These protocols maintain only those routes that are currently active. Routes are discovered as well as maintained for only those nodes that are currently being used to send data from source to the destination.
Route discovery in reactive routing is done by sending RREQ (Route Request message) from a source node when some data is to be sent to a particular destination. After sending RREQ, source node waits for the RREP (Route Reply) message. If it does not receive any RREP within a given time period, it is assumed that either route is not available or it is expired.
Reactive routing can either be source routing or hop-by-hop routing. In source routing, complete route information from source to destination is present in data packets. When these data packets are forwarded to other intermediate nodes in the network, each node uses route information present in the data packet. Here intermediate nodes do not need to update all route information in order to send packets to the destination.
However, main drawback of source routing is that it is not suitable for large scale networks. Further, these protocols do not have good performance in highly dynamic environment such as VANETs.
Hop-by-hop reactive routing works better than on demand source routing. Here each data packet contains next hop and destination addresses. Intermediate nodes from source to destination contain routing table information to send data packet to a destination. This is more helpful for accommodating sudden changes in topology. When topology changes nodes receives fresh routing table information and new routes are selected accordingly. The selected routes will now be used to send data packets to destination.
The Hybrid protocols
The design aim of hybrid protocols was to reduce the control overhead of proactive routing protocols and decrease initial route discovery delay in reactive routing protocols.
126.96.36.199 Position based protocols
These protocols make use of geographic positioning information to select the next hop.
Global route or hop-by-hop route between source and destination are created and maintained.
188.8.131.52 Geo-cast based protocols
These protocols are used to send messages to all vehicles present in a pre-defined geographical region.
184.108.40.206 Cluster-based routing protocols
In these routing protocols, vehicles in neighborhood of each other form a cluster. Each cluster has one cluster-head. The cluster-head is responsible for intra as well as inter-cluster management functions. Intra-cluster nodes can communicate each other via direct links. Inter-cluster communication is performed using cluster-heads. In cluster-based routing protocols, formation of clusters and the selection of the cluster-head is a critical issue.
220.127.116.11 Broadcast based protocols
These protocols use simple broadcasting to send data packets to destinations.
18.104.22.168 Infrastructure based protocols
These protocols are infrastructure based and use some infrastructure for routing. This means that routing in these protocols is not done in purely ad hoc mode.
1.5 Problem statement of the Thesis
Vehicular Ad hoc Networks (VANETs) are highly dynamic networks because of high mobility of vehicles. Highly dynamic network topology of VANETs hinders path determination as well as path maintenance process. High mobility of nodes results in more links breakages and degrades network performance in a proportionate way. This means that the frequency of change in topology is too high to determine a reliable path to the destination. This makes routing in VANETs a challenging task. This project addresses the routing issue in VANETs and proposes position and mobility parameter-based (PAMP) VANET routing protocol.
1.6 Aims and objectives
Aim of this research work is to develop an efficient routing protocol for VANETs and evaluate its performance in terms of different performance metrics.
1.7 Outline of the thesis
Chapter 2 discusses different VANET routing protocols. Here drawbacks of these protocols are also identified.
Chapter 3 gives the description of position and mobility parameters based (PAMP) VANET routing protocol. This chapter describes how the proposed will improve performance in terms of different performance metrics.
Chapter 4 is based upon simulation environment and performance analysis. It discusses simulation results in terms of different performance metrics.
Chapter 5 gives the summary of the research work and describes future work.
Review of the Existing Routing Schemes in VANETs
Routing of data in VANETs is a challenging task due to highly dynamic topology of the network. This causes routing complexity in these networks. This Chapter gives a survey of existing routing schemes in vehicular networks.
2.2 GSR (Geographic Source Routing)
Initially, GSR  was developed to be used in MANET. Later on some improvements were made to use it in VANET scenario. It was modified by incorporating greedy forwarding of messages toward the destination in it. GSR utilizes a recovery strategy if there are no nodes in the direction of destination at any hop. This strategy is known as perimeter mode. This mode has two components. One is known as distributed polarization algorithm. This makes local conversion of connectivity graph into planar graph by removing redundant edges. Second component is known as online routing algorithm. This component operates on planer graphs.
In VANETs perimeter mode of GSR is used. It starts sending the message to intermediate neighbor rather than to farthest node. This method introduces long delays due to greater number of hop counts. Rapid movement of vehicles introduces routing loops which causes dissemination of messages to long path. It uses static street map and location information about each node. It does not consider vehicle density. So it is not an efficient method.
Long delays due to greater number of hops.
Tries to establish end-to-end connections which are difficult at low traffic density. Further, end-to-end connection scheme doesn't work in a highly dynamic environment.
2.3 GPCR (Greedy Perimeter Coordinator Routing)
Lochert et al. designed GPCR  in an attempt to deal with the challenges of city scenarios. This protocol makes use of a restricted greedy forwarding procedure along a preselected path. When next hop is chosen, a coordinator (the node on a junction) is preferred to a non coordinator node. The preferred coordinator may not the geographically closest node to the destination.
cannot work without static street maps
Establishes end-to-end connections which are difficult when traffic density is low.
2.4 A-STAR (Anchor-based Street and Traffic Aware Routing)
This protocol was proposed by Seet et al. The proposed A-STAR  was an attempt to guarantee end-to-end connection in a vehicular network when traffic density is low.
In A-STAR , the number of junctions to reach the destination is computed. This protocol also uses traffic information and street awareness in path finding. It uses street awareness to get the anchor information according to the street map. This makes use of dynamically and statically rated maps to find the number of junctions. In statistically rated maps, A-STAR uses schedule of buses to ensure high connectivity. For example, some streets are served by regular city buses and their connectivity can be high due to presence of buses. In dynamically rated maps, the protocol collects the latest traffic information in order to find the anchors/junctions to compute the path. Some roads are wider than other and have more traffic. That is why connectivity is high on wider roads with high traffic (more vehicles). Using such type of traffic information, A-Star assigns the weight to the street. This is a dynamic process that helps this protocol to calculate anchors more accurately.
Establishes and uses routing paths. This approach for packet forwarding cannot work in a frequently changing network topology. Further, the routing paths established are not optimal and result in delay of packet transmission.
2.5 MDDV (Mobility-Centric Data Dissemination Algorithm for Vehicular Networks)
This protocol was proposed by Wu et al. MDDV  tries to achieve reliable and efficient routing. It combines opportunistic forwarding, trajectory-based forwarding and geographical forwarding. This protocol takes into account the traffic density. It specifies a forwarding trajectory that extends from the source to the destination (trajectory-based forwarding). A message will move along this trajectory and will get geographically closer to the destination (geographical forwarding). The forwarding trajectory is selected based upon the geographical knowledge and traffic density. In MDDV it is assumed that traffic density is static. Forwarding trajectory is used to forward the messages through intermediate nodes which are used to store and forward messages.
Main drawback of this approach is that it uses trajectory-based forwarding which fails when mobility of vehicles is very high.
2.6 VADD (Vehicle-Assisted Data Delivery)
This protocol  was proposed by Zhao and Cao .The aim of this protocol was to guarantee an end-to-end connection in a sparse network with low delay. This protocol is based upon the idea of carry and forward by using predicable mobility specific to sparse network. The protocol does not use any pre-defined path for routing. It chooses next hop based on the some pre-defined direction priority by selecting the closest one to destination. This protocol does not predict the environment change in the future.
Enough time required for connection setup & route establishment.
Intermediate nodes can lead to inconsistency in the route if they contain old entries.
Because of periodic beaconing it consumes extra bandwidth.
Fails to work at high mobility.
2.7 DGRP (Directional Greedy Routing Protocol)
It's a position based greedy routing protocol . It uses the two forwarding strategies greedy and perimeter. It predicts the nodes positions within the beacon interval whenever a data packet needs to be forwarded. This prediction is done using previous knowledge about position, speed, and direction of motion of node. If link between the forwarding node and its neighbor node is not stable, possibility of packet loss is high in DGRP. Further the prediction of position information is not always reliable.
packet delivery ratio is very low
large delay at high traffic density
uses to many hops to reach the destination
2.8 Greedy Perimeter Stateless Routing (GPSR)
GPSR  is a routing protocol for mobile wireless networks. Many other routing algorithms before GPSR used graph-theoretic notions of shortest paths and transitive reachability to find routes. GPSR however exploits the correspondence between geographic position and connectivity in a wireless network. For this purpose it uses positions of nodes to make packet forwarding decisions. It uses greedy forwarding to forward packets to nodes that are closer to the destination. In some regions of the network, a greedy path may not exist. In this case, GPSR recovers by forwarding in perimeter mode. In this mode a packet traverses successively planar sub-graph of the full radio network connectivity graph until a node closer to the destination is reached. Here greedy forwarding resumes.
It uses a longer path to the destination causing more transmission delay. Further, it can work when network is dense enough and may fail otherwise.
2.9 PDGR (Predictive Directional Greedy Routing)
In PDGR  the weighted score is calculated for current neighbors and possible future neighbors. In PDGR, the weighted scores for immediate nodes 2-hops away are also calculated. Here next hop selection is made based upon the prediction and it is not reliable in all situations. It does not provide guarantee that the delivery of packet to the node present in the edge of the transmission range of node considered as next hop. In high dynamics of vehicles, this has low packet delivery ratio, high delay and an increased routing overhead.
large delay when traffic density is high.
low packet delivery ratio and increased routing overhead.
2.10 Potential Edge Node Based Greedy Routing Algorithm (EBGR)
Potential Edge Node Based Greedy Routing Algorithm (EBGR)  is a uni-cast and position based greedy routing algorithm. It was designed for sending messages from a node to any other node in a vehicular ad hoc network (VANET). The aim of the EBGR algorithm is to optimize the packet behavior for VANETs with high mobility and deliver messages with high reliability. The algorithm for EBGR has six basic functional units. (1) Neighbor Node Identification (NNI), (2) Distance Calculation (DC) (3) Direction of Motion Identification (DMI), (4) Reckoning Link Stability (RLS), (5) Potential score calculation (PS) and (6) Edge Node Selection (ENS).
The NNI is used for collecting information of all neighbor nodes present within the transmission range of source/forwarder node at any time. The DC is responsible for calculating the closeness of the next hop using information from GPS system. DMI is responsible to identify the direction of motion of neighbor nodes which is moving towards destination. The RLS is responsible for identifying link stability between the source/packet carrier node and its neighbor nodes. The PS is responsible to calculate potential score and it also identifies the neighbor node having a higher potential for further forwarding of a particular packet to the destination. The ENS is responsible to select an edge node having higher potential score in different levels of transmission range.
Its ENS unit tries to identify edge nodes that more likely to be out of a node's range. This scheme fails when there are vehicles moving with variable speeds.
2.11 Fisheye state routing (FSR)
In FSR , a topology table (TT) is used. This table is maintained by a node based upon the latest information received from neighbors. Table information is periodically exchanged with local neighbors. In the case of large networks size of message should be reduced. For this purpose, FSR uses the different exchange period for different entries in routing tables. The problem with the FSR routing is that size of routing table increases with the increase in network size. With the increase in mobility, route to remote destination also become less accurate.
Size of routing table increases with the increase in network size
With the increase in mobility, route to remote destination also become less accurate.
It has very poor performance in large ad hoc networks.
Less or no knowledge about distant nodes.
With the increase in network, the processing overhead of routing table also increases.
Information for route establishment is not sufficient.
2.12 Temporally Ordered Routing Algorithm (TORA)
In TORA  , routing is based on directed acyclic graphs. These graphs direct the flow of packets and ensure its reachability to all nodes. A node constructs the directed graph by broadcasting query packets. On receiving a query packet, node having a downward link to destination broadcasts a reply packet. Otherwise packet is simply dropped. TORA has the advantage that it gives a route to all the nodes in the network. The problem for TORA is that maintenance of all these routes is very difficult in VANETs.
Maintenance of all routes is very difficult in VANETs.
It is not scalable.
2.13 Greedy Traffic Aware Routing protocol (GyTAR)
Greedy Traffic Aware Routing protocol  has given a new concept of intersection-based routing protocol. The main purpose of this protocol was to reduce the control message overhead & end-to-end delay with low packet loss.
This depends upon roadside units which have their own drawbacks.
2.14 CAR (Connectivity-Aware Routing)
For city and highway environment Connectivity-Aware Routing (CAR)  has been designed. It is based on AODV for path discovery but uses Preferred Group Broadcasting (PGB) for data dissemination mode.
Path discovery process used by AODV cannot be used in VANETs.
Unnecessary nodes can be selected as anchor nodes.
Path discovery process does not work in a rapidly changing network topology.
2.15 Street Topology Based Routing (STBR)
The proposed protocol Street Topology-Based Routing (STBR)  is based upon the following idea. Elucidate a given street map as a planar graph which has three valid states (1) master (2) slave (3) forwarder for a node. In this protocol, one node is selected as a master on a junction and other nodes act as slaves. The intermediate nodes between junctions serve as forwarders.
In STBR complexity increases due to some special cases. For example, transferring the neighbor table to new master when old master leaves the junction.
2.16 Greedy Routing with Abstract Neighbor Table (GRANT)
GRANT  applies an extended greedy routing algorithm concept. Abstract Neighbor Table of GRANT performs division of the plane into areas and includes only one representative neighbor per area.
Performance evaluation of GRANT has been done on static traces but VANET has a high mobility characteristics.
There is overhead of beacons. Further the inaccuracy in packet delivery has not been measured.
2.17 Direction-based AODV routing protocol (DAODV)
Working of this protocol  is as follows.
1- Discovers paths to the destination using route request message (RREQ). Sender multi-casts RREQ to the nodes selected based upon their position and direction.
2-Uses routing tables for packets forwarding.
4- Performs route maintenance.
5- Routing tables are frequently updated due to change in network topology.
The approach used in DAODV is similar to that used in AODV. The only difference between this scheme and AODV is that DAODV uses position and direction during path discovery process.
Like AODV, Route discovery process of DAODV uses RREQ (route request) message.
When a source node wants to communicate destination node, DAODV multi-casts RREQ message to selected neighbor nodes. This selection is made upon their position and direction. Neighbors receiving the request (RREQ) forward RREQ further and so on. The source acquires route reply (RREP) message when route is successfully discovered.
Packets are forwarded to the destination using routing tables. When routing error occurs during packet forwarding, route error message (RERR) is sent back to the sender. The sender then initiates route discovery process again.
1- It uses path discovery process as used in AODV routing protocol.
2 - Like AODV, it uses routing tables which fail to update a high frequency of link breakages.
3- Parameters used for next hop selection are not sufficient to select best next hops.
4- It fails to work when mobility of nodes is high. At high mobility, frequency of change in topology is too high to determine a reliable path to the destination.
2.18 Cluster Based Location Routing (CBLR)
CBRL  is a reactive and cluster based routing protocol. During cluster formation every node broadcasts a hello message and then waits for a predefined time. When the node receives a reply from a cluster header before the timer expires, it becomes a cluster member. It becomes a cluster header, otherwise.
Each cluster header maintains a table which contains the addresses and geographic locations of cluster members and gateways nodes. It also maintains a Cluster Neighbor Table to store the information about the neighboring clusters. When a source wants to send data packet to a destination, it first checks whether the destination is in same cluster. If destination is in same cluster, the source sends the packet to the neighbor closest to the destination. Otherwise, data packet is stored in the buffer of source which starts a timer and broadcasts Location Request (LREQ) packets. In order to minimize number of transmissions, only gateways and cluster-heads can retransmit the LREQ packet.
After receiving a request, each cluster-head checks whether the destination is member of its own cluster or not. If destination is a cluster member, then cluster header sends a Location Reply (LREP) packet to the sender based upon the information present in LREQ packet and cluster neighbor table.
Otherwise it retransmits LREP to adjacent cluster-headers. CBLR is more suitable for networks having high mobility because the location of the source and destination is updated every time before data transmission starts.
Use flooding. This results in wastage of bandwidth.
Cluster-head may be a single point of failure.
2.19 Robust Vehicular Routing (ROVER)
ROVER  is a geographical multicast protocol where control packets are broadcasted and the data packets are uni-casted in the network. The purpose of this protocol is to send messages to all other vehicles within a specified Zone of Relevance (ZOR). Zone of Relevance is defined as a rectangular area specified by its corner coordinates. A message is defined by the [A, M, Z] triplet which indicates the specified application, message and identity of a zone respectively. When a vehicle receives a message, it will accept message if it is within the ZOR. Robust Vehicular Routing protocol also defines a Zone of Forwarding (ZOF). This zone includes the source and the ZOR. All nodes in ZOF are used in the routing process. The protocol uses a reactive route discovery process within a ZOR. This creates lot of redundant messages in the network which leads to wastage of bandwidth, congestion and high delay in data transfer. To overcome this issue, two Zone Dissemination Protocol for VANETs was proposed. This protocol uses hop-count in packet. The counter is decremented when the packet is forwarded. When the hop-count counter reaches to zero, the packet is discarded. This may cause the nodes near to the sender forward same packet multiple times. This problem is avoided by introducing sequence number for every packet to find whether a packet has been already received or not.
Use flooding which results in wastage of bandwidth.
Zone of Relevance (ZOR) and Zone of Forwarding (ZOF) change very soon when vehicles are moving at high speed. This requires new specifications of these zones. Re-specification of these zones at a high frequency may be problematic.
There are many other protocols proposed for VANETs. But all of them have one or more deficiencies. For example the proposed protocols in [28, 29, 30] are based on static map of cities and their function is restricted by knowledge of road topology. These protocols have poor performance in terms of one or more performance metrics also.
VANETs have a highly dynamic network topology. This makes routing a challenging task in VANETs. Due to routing complexity in VANETS, none of the proposed protocol can be considered as ideal one. Every protocol has one or more drawbacks associated with it.
Simulation Environment & Performance Analysis
4.1 What is a simulation?
Simulation is an important research modeling tool used in science, engineering and other applications for different purposes. Computer assisted simulations are used to model hypothetical and real-life objects or activities on a computer. This helps to study system functions. Different variables can be used to describe the behavior of the system. Computer simulations assist in modeling and analysis of many natural systems. Its application areas include physics, chemistry, biology and human-involved systems. Other applications are in the engineering such as mechanical engineering, structural engineering and computer engineering. Application of simulation technology in networking area such as network traffic simulation however, is very important.
Network simulations may be concerned with the performance or validity of a distributed protocol or algorithm. Moreover, network technologies are developing very fast. Therefore, network simulations require open platforms which should be scalable enough to include different modules and packages in the simulations of an entire network. Internet is also structured with a uniformed network stack (TCP/IP) that all the different layers technologies can be implemented differently but with an interface connecting it with their neighbored layers. Thus the network simulation tools should be able to incorporate this feature and allow new packages to be included and run without harming existing components. In this way there would be no or little negative impact of some packages on the other packages.
Network simulators are used in different areas such as academic researchers, industrial developers to design, simulate, verify, and analyze results. They are used to study the effect of the different parameters on the protocols being evaluated. Generally a network simulator comprises of a wide range of networking technologies and protocols. This helps the users to build complex networks from building blocks like clusters of nodes and links. User can emulate different network topologies using various types of nodes such as end-hosts, hubs, routers, optical link-layer devices.
4.2 Two types of network simulators:
Commercial : OPNET, QualNet
Open source: NS2, NS3, OMNeT++, SSFNet, J-Sim
4.2.1 Network Simulator (NS2)
NS2  is one of the popular open source network simulators. The original NS is a discrete event simulator used for networking research. NS2 is the second version of NS (Network Simulator). The first version of NS was developed in 1989. Current NS project is supported through DARPA. Second version NS2 is widely used in research and it possess a lot of packages contributed by different non-benefit groups.
22.214.171.124 Main features
NS2  is an object-oriented, discrete event driven network simulator originally developed at University of California-Berkely. It uses C++ and OTcl (Tcl script language with Object-oriented extensions developed at MIT). The use of these two languages has its own reason. The major reason is the internal characteristics of these two languages. C++ is good to implement a design but it is not suitable to be visual and graphically shown. It is difficult to modify and assembly different components. Moreover, for efficiency reason, NS2 uses separate control path implementations from the data path implementation. The objects for event scheduler and the basic network component in the data path are written and compiled using C++ to reduce packet and event processing time. OTcl has many features that C++ lacks. So the combination of these two languages is used for effectiveness. C++ implements the detailed protocol and OTcl helps the users to control the simulation scenario and schedule the events. A simplified user's view of NS2 is shown in figure 4.1. The OTcl script initiates the event scheduler, sets up the topology, and instructs traffic source when to start and stop sending packets through event scheduler. The scenarios can be changed easily by programming in the OTcl script. When a user wants to make a new network object, he can write a new object or assemble a new object from the existing library, and plumb the data path through the object. This feature makes NS2 very powerful.
1 Event scheduler
2 Network component
3 Plumbing module
Fig: 4.1 User's View o f NS2 
NS2 is the event scheduler. In NS2, the events schedulers are used to keep track of simulation time and release the events in the event-queue by invoking appropriate network components. All the network components use this scheduler by issuing an event for the packet and waiting for the event to be released before further action on the packet takes place.
Fig: 4.2 Working of NS2 
4.3 Traffic Simulators
A large number of traffic simulators are available. Names of some of them are:
Open source: SUMO , VanetMobisim 
Commercial: CORSIM , PARAMICS 
Traffic simulator used in this research work is VanetMobisim .
VanetMobiSim  is a freely available generator of realistic vehicular movement traces for networks simulators. It is one of the vehicular mobility simulators fully validated and freely available to the vehicular networks research community.
VanetMobiSim is an extension to CanuMobiSim  which is a generic mobility simulator. CanuMobiSim  is a platform and simulator-independent software. It has been coded in SUN Java  and produces mobility traces for a number of network simulators such as ns-2 , GloMoSim , and QualNet . It can also integrate user-defined or Geographic Data File (GDF) map  topologies. It contains a number of mobility models and also provides easily extensible mobility architecture. CanuMobiSim  however, suffers from a limited level of detail. This makes it unsuitable for modeling of vehicular motion.
VanetMobiSim extends the vehicular mobility support of CanuMobiSim to a higher degree of realism. VanetMobiSim inherits all the features of CanuMobiSim but also contains the new features. These new feature include Integration of TIGER maps  and Voronoi topologies, a complete road topology characterization, intersection modeling, overtaking capabilities, traffic light management, the IDM-IM, the IDM-LC, and the MOBIL mobility models.
Like CanuMobiSim, VanetMobiSim is a modular discrete event simulator. It is based on SUN Java. The software architecture of VanetMobiSim is structured around two extension objects (1) the Universe (2) the Node. The Universe is used for static objects modeling, while the Node models movable objects. Each feature present in VanetMobiSim is implemented as a module and is loaded at start-up from an .xml scenario file. Modular structure of VanetMobisim makes it easy to add new features.
Vanet scenario definition
CBR source file
Fig. 4.3 User view of VanetMobisim and NS2
126.96.36.199 Macro-mobility Features
Macro-mobility consists of the following features:
Road topology, the road structure (unidirectional or bidirectional, single- or multi-lane), the presence of traffic signs (stop signs, traffic lights, etc.) and the road characteristics (speed limits, vehicle classes restrictions).
The concept of macro-mobility also includes the effects of the presence of points of interests. These points influence movement patterns of vehicles. VanetMobiSim defines the road topology in the following ways:
TIGER map: the road topology is extracted from a map of the TIGER database .
Clustered Voronoi graph: road topology is created randomly by creating a Voronoi tessellation on a set of non-uniformly distributed points. This creates configurable random graphs.
The concept of vehicular macro-mobility is not limited to motion constraints but it also includes all aspects related to the road structure characterization. VanetMobiSim also contains:
â€¢ Physical separation of opposite traffic flows on roads.
â€¢ Roads with multiple lanes in both directions.
â€¢ Speed constraints imposed at each road segment.
â€¢ Traffic signs at each road intersection.
188.8.131.52 Micro-mobility Features
Micro-mobility includes the aspects related to an individual car's speed and acceleration modeling.
VanetMobiSim adds two microscopic mobility models to include the management at intersections regulated by traffic signs and roads with multiple lanes. Two original microscopic mobility models present in VanetMobisim are:
Intelligent Driver Model with Intersection Management (IDM- IM):
This model adds intersection handling capabilities to the behavior of vehicles. IDM-IM models two different intersection scenarios: a crossroad regulated by stop signs and a road junction ruled by traffic lights.
Intelligent driver model with lane change (IDM-LC):
This model extends IDM-IM model where vehicles can change lane and can overtake each other.
4.3.2 Mobility Model categories
There are a number of mobility model categories present in VanetMobisim. Names of some of these are given below.
This category includes the following models
-Random Waypoint Model
This category includes the following models
Temporal dependent models
Models in this category are:
-Probabilistic Random Walk
-Exponential correlated model
This category includes the following models:
-Reference Point Group Model
- User graph model
-random graph model
4.4 Simulation scenarios description
Graph model (user graph model) of VanetMobisim has been used to create road topology. The road created is multi-lane road. The road was populated with varying number of cars. Vehicles can move on different lanes with different speeds. Vehicles can overtake each other. This emulates a highway scenario. Number of nodes communicating each other is 75 % of total number of nodes in a simulation scenario. Remaining 25 % are just serving as intermediate nodes. Simulation parameters used are given in the table 4.1.
Number of cars
Speed of cars
Two ray ground
UDP packet size
Table 4.1 Simulation parameters
4.5 Performance metrics
Different performance metrics are used to check the performance of routing protocols. Packet delivery ratio, average end-to-end delay, packets drop ratio percentage and Jain's fairness index  are selected metrics to check the performance of PAMP and compare it with the existing DAODV  routing protocol. The selected metrics for protocols evaluation are defined as follows:
Packet delivery ratio percentage (PDR %) = (Packets Received / Packets Sent) 100
Average end-to-end delay = average of the times taken for all packet to be transmitted
across a network from a source to its destination.
Packets drop ratio percentage = (packets dropped / packets sent) 100
Number of collisions = number of collisions occurred during channel access contentions.
Fairness: fairness of a protocol is its ability to allocate the channel bandwidth equally.
Jain's fairness index  is defined as follows.
Where fraction of packets sent by sender i to the destinations.
= square of fraction of packets received at all destinations during simulation time
N= number of senders contending for sending data to destinations.
Figure: 4.4 packet delivery ratio percentage of PAMP and DAODV
4.5.1 Packet delivery ratio (PDR percentage)
Figure 4.4 shows performance of PAMP and DAODV in terms of PDR percentage. PAMP starts with a higher PDR value. It outperform DAODV almost through out the simulation time. Initially, PDR percentage is low for both protocols. This is because the network has a low vehicular density. PDR increases with the increase in number of nodes but then decreases dramatically.
Better PDR value of PAMP is due to two main characteristics of this protocol.
Firstly, it uses single hop approach to forward the packets. Here routing tables are not used for routing the packets. In the case of DAODV, routing tables are used and maintained. Highly dynamic network topology of VANETs hinders path determination as well as path maintenance process. High mobility of nodes results in more links breakages and degrades network performance in a proportionate way. This means that the frequency of change in topology is too high to determine a reliable path to the destination. Routing tables may fail to update because of high frequency of links breakages. High mobility causes routing errors to occur again and again. Hence, the packets are dropped and PDR is decreased.
Secondly, PAMP uses "relative speed" as an additional parameter during the process of next hop selection. Relative speed is the speed of next node with respect to its sender. Here the next hop is selected with a possible lower relative speed value of a node. This increase the reliability and durability of link between sender/forwarder and the next hop.
On the other hand, link reliability will be decreased when no relative speed is considered or a next hop with larger value of relative speed is selected. Particularly, when the node is at the edge of sender's transmission range, it cannot be regarded as suitable next hop without considering its relative speed. High mobility may cause next hop to be out of sender's range just after the packet has been transmitted. As a result of this, next hop would fail to receive the packet resulting in a packet drop.
Packet delivery ratio drops dramatically when number of nodes is increased to 100. This kind of drop has been observed in the case of both protocols. Packet drop may occur at network layer as well as MAC layer. When a packet reaches the network layer, the routing protocol forwards it to next hop if possible. The packet is otherwise, buffered for some time. When a large number of nodes are sending the packets, packets may be dropped because the following situations may arise.
1- The buffer is full and no more packets can be buffered.
2- The time that the packet has been buffered for, exceeds the limit.
Packet loss also occurs at the MAC layer. When CSMA/CA is used as medium access mechanism, packets may be dropped due to the following reasons:
When a large number of nodes are contending for medium access, the wireless channel gets so busy that the number of back offs exceed the limit. This may causes the newly arrived packets to drop and decrease PDR.
Figure 4.5 End-to-End delay of PAMP and DAODV
4.5.2 End-to-End delay
Figure 4.5 shows performance of PAMP and DAODV in terms of average end-to-end delay. PAMP starts with a lower value of end-to- end delay. It outperform DAODV almost through out the simulation time. End-to-End delay tends to increase with the increase in number of nodes.
End-to-End delays incurred can be attributed to the following main sources:
1. Multi-hop nature of network: a message needs to traverse several hops to reach its destination. The message incurs channel access delay , processing, aggregation delays and queuing delay at each hop. So, the delay incurred by a message increases as the number of hops to the destination increases.
2. Channel access delay: Contention based nature of wireless channel forces the nodes to contend for channel access. Channel access delays are usually functions of the number of nodes and load on each node in the network. It is also a function of the transmission power.
3. Aggregation at intermediate nodes: Nodes aggregate information before transmitting the data to the next hop.
PAMP implements single hop approach and has a lower aggregation time and channel access delay. DAODV  uses routing tables for forwarding packets. It takes significant amount of time to update and maintain routing tables and use them for packet forwarding. When routing errors occur, routing tables need to be updated. This occurs frequently because the frequency of links breakages is very high. That is why, value of End-to-End delay in DAODV is larger than that of PAMP.
Figure 4.6 Packet drop ratio percentage of PAMP and DAODV
4.5.3 Packets drop ratio percentage
Fig. 4.6 shows performance of PAMP and DAODV in terms of packets drop ratio percentage. Initially, packet drop ratio for the both protocols is high because network is less populated. Packet drop ratio decreases with the increase in number of nodes but then increases again.
In AODV, routing tables are used and maintained. Routing tables fail to update because of frequent disconnection of links. This causes the routing errors to occur frequently. Packets are dropped due to frequent occurrence of routing errors.
Packets are also dropped if next hop selection criteria is not suitable. When next hop is selected without considering its relative speed with respect to sender, durability of link between sender and next hop will be decreased and next hop may be out of sender's range before it receives a transmitted packet.
Graph shows that packet drop ratio increases when number of nodes increase to 100. When number of transmissions increase, packet may be dropped due to buffering size and time restrictions.
Figure 4.7 Number of collisions for PAMP and DAODV
4.5.4 Number of collisions
Figure 4.7 shows performance of PAMP and DAODV in terms of number of collisions. Both of the protocols show almost equal performance at low contention. PAMP outperforms DAODV at higher contention.
Low performance of DAODV at a high value of number of nodes can be explained as follows. In DAODV, an attempt is made to discover more than one paths to the destination so that upon failure of one path, other may be used. Hence, the sender multi-casts RREQ message to a large number of selected nodes. Every node receiving the RREQ, multi-casts in the similar fashion. Here contention increases because a large number of nodes want to transmit simultaneously resulting in a large number of collisions. This is not the case in PAMP where single-hop based approach for packet forwarding is used.
Figure 4.8 Jain's fairness index of PAMP and DAODV
4.5.5 Jain's fairness index
Figure 4.8 shows the behavior of both protocols in terms of Jain's fairness index. Graph shows that value of fairness index decreases with the increase in number of nodes. This means that fairness of protocol decreases with the increase in contention. This is due to the drawback of 802.11 regarding it channel access mechanism.
DAODV has less fairness value as shown in figure 4.8. In DAODV, sender multi-casts RREQ message to a large number of selected nodes. Every node receiving the RREQ, multi-casts in the similar fashion. Here contention increases because a large number of nodes want to transmit simultaneously. PAMP, on the other hand uses single-hop based approach for packet forwarding. This decreases the contention level in PAMP. Hence, PAMP outperforms DAODV in terms of fairness index also.
PAMP is a VANET routing protocol that uses single hop approach for packet forwarding. Here next hop is selected based upon its relative velocity with respect to sender and its position. Neither route discovery phase nor routing tables are used. On the other hand, DAODV uses RREQ messages to discover the route to destination. Here routing tables are used to store routing information. These overheads degrade the performance of DAODV in term of different performance metrics.