Interest in vehicular ad hoc networks (VANETs) has grown over the last few years, particularly in the context of emerging intelligent transportation systems (ITS). Vehicular ad hoc networks (VANETs) are highly mobile wireless networks that are designed to support vehicular safety, traffic monitoring, and other commercial applications. However, efficient routing in VANETs remains challenging for many reasons, e.g., the varying vehicle density over time, the size of VANETs (hundreds or thousands of vehicles), and wireless channel fading due to high motion and natural obstructions in urban environments (e.g., buildings, trees, and other vehicles). Within VANETs, vehicle mobility will cause the communication links between vehicles to frequently be broken. Routing becomes an important issue in VANET. If the network has very less vehicle then it becomes more challenging to send a packet from source to destination. In such scenarios efficient routing plays an important role. With efficient routing technique we can provide communication in network even if the density of vehicles in the network is low. We provide a routing algorithm which works on a hybrid scenario, i.e. it will have both static and dynamic infrastructure. The approach used is Cluster based routing which will help in transmitting packets even in a network with low vehicle density.
Keywords |
| Routing, VANET, Cluster Based Routing, Multipath flooding. |
I. INTRODUCTION |
| The automotive industry is currently undergoing a phase of revolution. Today, a vehicle is not just a
thermomechanical machine with few electronic devices; rather, recent advancement in wireless communication
technologies has brought a major transition of vehicles from a simple moving engine to an intelligent system carrier. A
wide spectrum of novel safety and entertainment services are being driven by a new class of communications that are
broadly classified as vehicle-to-vehicle communication and vehicle-to-infrastructure communication. |
| Currently, intelligent transportation system components provide a wide range of services such as freeway
management, crash prevention and safety, driver assistance, and infotainment of drivers and/or passengers [1]. Recent
trends swing toward advertisement, marketing, and business of services and products on wheels. Consequently, these
applications appear to be very lucrative and promising in terms of commerce and research. The significant use of
vehicular communications in safety and infotainment applications has resulted in the development of a new class of
media access control and network layer protocols. |
| The current domain of vehicular research includes routing, congestion control, collision avoidance, safety message
broadcast, vehicular sensing, security, etc. Different terrains pose separate challenges to vehicular routing. The issues in
a city network would not be exactly the same as in a highway or in a delay torrent network. The outskirts may have
sparse vehicular density, whereas downtown has to deal with vehicular congestion. The evening may have the highest
vehicular traffic, and midnight may be seen as the most silent period of the day. It is a most difficult job to predict the
exact traffic density of a region. The structure of the road (i.e., straight or curved), number of intersections, number of
lanes, length of the road (i.e., based on road ID), availability of public transport, and driver behaviour have a great
impact on the node density and network connectivity of a vehicular network. |
| We worked on a network in which density of vehicle is very low i.e. the number of cars in the network is very less.
A cluster based approach is used to solve the problem of communication. There is a hybrid network i.e. it has both kind
of nodes static as well as dynamic. We propose a method to solve the issue of low communication in scarce network. |
II. RELATED WORK |
| A lot of work has been done in the field of Vehicular Ad-hoc Network. Routing has been one of the main issues in
VANET because of dynamic nature of the network. So many authors have worked on routing issue in VANET. |
| Jamal Toutouh, José García-Nieto, and Enrique Alba have proposed in [5] that optimal parameter tuning of the
OLSR routing protocol can be used in VANETs by using an automatic optimization tool. For this task, they defined an
optimization strategy based on coupling optimization algorithms (PSO, DE, GA, and SA) and the ns − 2 network
simulator. In addition, they have compared the optimized OLSR configurations with the standard one in RFC 3626 as
well as with human expert configurations found in the current state of the art. |
| In [6] Mohammad Al-Rabayah and Robert Malaney combined the features of reactive routing with location-based
geographic routing in a manner that efficiently uses all location information available. The protocol is designed to
gracefully exit to reactive routing as the location information degrades. A significant reduction in the routing overhead
was achieved in HLAR compared to standard reactive and geographic routing protocols. It effectively obtains optimal
scalability performance. |
| Hanan Saleet, Rami Langar, Kshirasagar Naik, Raouf Boutaba, Amiya Nayak and Nishith Goel worked on
Intersection-Based Geographical Routing Protocol for VANETs in order to improve Quality of service [7]. IGRP is
based on an effective selection of road intersections through which a packet must pass to reach the gateway to the
Internet. The selection is made in a way that guarantees, with high probability, network connectivity among the road
intersections while satisfying quality-of-service (QoS). Geographical forwarding is used to transfer packets between
any two intersections on the path, reducing the path‟s sensitivity to individual node movements. |
| In Back-Bone-Assisted Hop Greedy Routing for VANET‟s City Environments, Pratap Kumar Sahu, Eric Hsiao -
Kuang Wu, Jagruti Sahoo, and Mario Gerla [9], choose hop count as the metric to find the routing paths. The hop
greedy routing protocol exploits the transmission. It is ensured that the selected intersections have enough connectivity.
BAHG adopt an indirect method to compute the connectivity parameter for each intersection. It introduces a back-bone
mechanism in which some specialized nodes perform functions such as tracking the movement of end nodes. |
| In [10] D.Rajini Girinath , S.Selvan worked on Cluster based approach for VANET. Clustering was used for routing
in the city scenario. Multipath flooding algorithm was proposed for Cluster formation. They tried to group vehicles
with low mobility with respect to each other into the same cluster. |
III. PROPOSED WORK |
| All The research on real-time communication in Vehicular Ad Hoc Networks enables distributed applications among
vehicular nodes in infrastructure-less areas. Cluster based Routing in VANET is particularly useful for applications that
require better routing and scalability to hundreds or thousands of vehicles. Location based clustering techniques can aid
in improving the routing performance under different mobility scenarios. Vehicular Ad Hoc Network
(VANET) is characterized by vehicles with relatively high mobility and has become a promising field of research
paving way to safety of Traffic Management. VANET enables communication between the Vehicles (V2V
communications) and the road-side infrastructure (V2I communications). |
| Static and dynamic cluster heads are responsible for coordination among the nodes within their clusters, and between
the clusters. Periodic re-clustering can select nodes with longer travel time and more number of stops like buses act as
cluster heads. Network lifetime is prolonged through (i) choosing the optimal path with minimal interference of nodes,
(ii) periodic updation in clusterhead regarding the routing and cluster information, and (iii) routing through the nodes
with average speed of nodes. A stand-alone cluster based approach that considers a hybrid and dynamic mobility
model. Based on this approach, we present a Location based Multipath Flooding algorithm, which have three primary
goals: (i) reducing delay, (ii) prolonging network lifetime and (iii) maximal data delivery ratio at high mobility.
Stability in this context implies the need for load balancing and efficient resource utilization. Routing protocols can
also employ clustering [2], [3]. |
| In [4], clustering was proposed as a useful tool for locating the destinations. In a complete distributed system like
VANET, every node can act as a source or a relay node, which motivates the need for efficient algorithms to select
servers according to the outlined system goals. Each vehicle should store the information related to the cluster within
the transmission range of source node. In our model, a fixed number of dynamic and static sources are known to every
vehicle of the system, and a static source is always available for processing large amount of data. |
| In our integrated approach the information pertaining to traffic is maintained in both sources, lesser time in dynamic
source and longer duration in static sources for future purpose. If the distance between two cluster head nodes is found
to be less than the threshold, the cluster with fewer members is dismissed to reduce communication overheads and its members join other clusters [6]. During high mobility conditions the process of reclustering increases the
communication cost. Locating the position of nodes, relative speed predictions and effective communication distance
between nodes according to mobility are dealt in our approach. |
| Grouping the vehicles can be differentiated in different mobility models according to their spatial and temporal
dependencies. For example, two nodes moving in same direction are having high spatial dependency [9]. Temporal
dependency is a measure of the relationship between current and previous velocities. High temporal dependency would
be spotted between the nodes having the same velocity. VANET‟s are characterized by high mobility communication
in infrastructure-less environments and dynamic topology situations [8], which lead to frequent network partition.
VANET‟s dependency on external parameters like type of the roads, driver‟s decision, timing, weekdays, and speed of
the vehicle and location of the vehicles make it difficult to monitor and manage the entire network. Mobility aware
ripple free clusters are used for maintaining stable vehicular infrastructure and inter cluster routing. Thus network can
adaptively adjust its dominant routing mechanism based on its mobility features [13]. |
| A. CLUSTER BASED ROUTING |
| Cluster based Routing combines the features of static and dynamic clustering together. Static clusters are formed
around the static sources located at the road signals, street corners and congested places known as static clusterhead.
However buses are chosen as dynamic sources in our algorithm, having the predefined path and time chart to handle the
high mobility situations known as dynamic clusterhead. Hierarchical clustering creates a layering environment that
poses some of the main challenges in such ad hoc networks. Top layer consists of static clusterhead, middle layer
consists of dynamic clusterhead and lower layer consists of ordinary vehicles. Because of highly dynamic vehicles
network topology also changes. This in turn affects the performance of the network and also invokes protocol
mechanisms to react to such dynamics. Mobility awareness deals with sudden changes in topology by responding
against malfunctions in routing. Some of mobility metrics are considered for cluster construction in order to form a
stable cluster structure thereby decreasing its influence on cluster topology. Vehicles Mobility behaviour determines
the architecture of the cluster. Vehicles are grouped in two different ways either by those vehicles which are in the
communication ranges of dynamic sources or by those vehicles which are in the ranges of static sources mounted at
traffic signals and road junctions. |
| Dynamic clustering attempts to partition a number of nodes into multi-hop clusters based on the following
parameters (VID,LID,s,VLT) we defined in Algorithm 1. The(VID,LID,s,VLT) criteria indicate that every vehicle node
in a cluster has it own unique VID and Location ID representing the road in a particular area of the city it belongs. The
symbol „s‟ indicates the speed of the vehicle and VLT indicates the vehicles life time in a particular cluster. |
| Dynamic clustering scheme, our parameterized clustering scheme requires no periodic re-clustering. As soon as a
vehicle enters into the clustering zone its unique VID is registered into the clusterhead and becomes a member of that
cluster. Any unclustered vehicle joins a cluster by sending out CJReq message. Mobility also affects the size of the
cluster, low mobility increases the size of the cluster compared to high mobility, leading to increase in the number of
clusters. A Vehicle can join a cluster if it has a valid VID and its speed is also an important criterion, if any new vehicle
other than ambulance or rescue vehicle enters into the cluster with the speed more than an average speed it is not
necessary to update it everywhere. If a vehicle does not receive a response message after a certain period of time, it
creates a new cluster and it will become the head for itself, even after that it will send and receive message to become a
cluster member or it will continue as a cluster head. |
| In the algorithm CJM (Cluster Join Messages) for cluster formation is suitable for a network with high mobility,
where mobility of vehicles affects the cluster topology. Cluster formation depends only on CJM and not by any other
messages thereby overheads are avoided; similar to the idea proposed in [10]. Once the vehicle enters into a cluster
region it periodically broadcasts CCM (Cluster Connect Messages) before passing the data, once it receives the
response it will start data transmission. In our approach ripple effect of reclustering is reduced by choosing known and
defined vehicles like buses as clusterheads and this effect has been reduced in some places by mounting static
clusterheads, hence cluster structure and topology has to be maintained smoothly without any force alternations [12].
One advantage of Static clusterhead is gathering accurate neighbour information and cluster structure is promised with
specific attributes. Another metric is the duration of each vehicle to become a member of the cluster. By sending a
message to all neighbours (n), each vehicle can help each of its neighbours to decide the distance between them. Then
each neighbour should send reply information(r), including the VID, CID, distance, speed and direction. Hence, each
vehicle needs to send out (n+r) messages for cluster construction. During cluster construction phase, one should
consider how to reduce the amount of clustering-related message exchanged for the cluster formation. |
| From time to time each unclustered vehicle seeks a cluster to join after sending CJM messages periodically, and
creates a singlenode cluster to cover itself when there is no proper cluster to join. A too-small cluster, however, may
produce large number of clusters and thus increase the length of hierarchical routes, resulting in longer end-to-end
delay. To avoid this, two clusters are integrated based on clusterhead speed and by choosing slow speed clusterhead as
new head. In our non-overlapping multihop structure, data transmission is more flexible and do not have a hop limit
between two neighbouring clusterheads. |
| B. ALGORITHMS |
| 1. LOCATION BASED MULTIPATH FLOODING: |
| At source |
| a) flood (CJReq) all Immediate Neighbours(NVID) |
| b) VC = # (NV) |
| for each relay node |
| { |
| for each CJReq received |
| { |
| if new NVID =old NVID |
| drop(RREQ) to avoid repeation |
| if (current node(CVID = DVID) |
| then DVID is set to nodes id |
| else |
| {i)CJReq to IMVID add(CVID) |
| ii)Find VC1 = # (NV) |
| } |
| At Destination |
| For each CJReq received, send (CJRep) to source |
| If (speed>thresholdspeed) |
| update only VID in Clusterhead |
| else |
| sort(CJRep IMVID) |
| update details of vehicle to all nodes |
| At source { |
| till(timestamp< threshold time) |
| { |
| link = SORT(CJRep IMVID) |
| for each link |
| { find SP= MIN(CJRep VC) |
| send (data) to DV through SP |
| } |
| SORT(CJRep IMVID) |
| for each IMVID in CJRRep |
| { |
| calculate VD |
| SORT( IMVID) in ascending order of VD |
| calculate SP # elements whose VD |
| store all VID in an array in each cluster |
| } |
| 2. CLUSTER HEAD SELECTION ALGORITHM: |
 |
 |
| C) ENVIRONMENT GENERATION |
| For environment generation we have used OMNET++ simulator. The environment was generated for different
scenarios with each scenario having different number of static and dynamic nodes. The area considered is of 4 km by 4
km. The speed and the direction of the vehicles are kept random. |
IV. EXPERIMENTS AND RESULTS |
| A) 100 messages were sent in each and every scenario so as to calculate number of successful messages reaching
the destination. |
| The result of the test is shown below: |
 |
| B) The time was checked for 100 successful messages in each and every scenario. Using this data the time
analysis was done. |
| The result of the test is shown below: |
| a. For 4 cars the average amount of time required to deliver a successful message is 81.3ms |
| b. For 8 cars the average amount of time required to deliver a successful message is 65.35ms |
| c. For 12 cars the average amount of time required to deliver a successful message is 54.65ms |
| d. For 16 cars the average amount of time required to deliver a successful message is 42.25 ms |
| C) The time required for first 20 successful message delivery is shown below: |
V. CONCLUSION AND FUTURE SCOPE |
| The Clustering based system was used for routing in VANET. The technique has worked efficiently on scarce
network in VANET. Different scenarios were generated using OMNET++ simulator and messages were send for
testing and analysis purpose. The analysis showed that with increase in number of cars and Road Side Units probability
of message reaching the destination increases. Also the average time required for successful message transmission
reduces with increase in number of cars. |
| In future different technique for selection of cluster head can be used. There are many ways in which clusterheads
can be selected. Different criteria can be used for head selection. The analysis of these techniques can be done. Also the
network can be expanded with respect to area, number of cars, and number of Road Side Units. The testing and
analysis for the same can be done. |
Figures at a glance |
 |
 |
 |
| Figure 1 |
Figure 2 |
Figure 3 |
|
| |
References |
- A J. Bernsern and D. Manivannan, “Unicast routing protocols for vehicular ad hoc networks: A critical comparison andclassification,” Pervasive Mob. Computing., vol. 5, no. 1, pp. 1–18, Feb. 2009.
- Chunhung Richard Lin and Mario Gerla,” Adaptive Clustering for Mobile Wireless Networks”, IEEE Journal on SelectedAreas in Communications, Vol. 15, No. 7, pp.1265-275, Sep 1997.
- S. Banerjee and S. Khuller, “A Clustering Scheme for Hierarchical Control in Multi-hop Wireless Networks,” inProceedings of IEEE INFOCOM, April 2001.
- A D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next Century Challenges: Scalable Coordination in SensorNetworks,” in Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking(MOBICOM), August 1999.
- Jamal Toutouh, José García-Nieto, and Enrique Alba, “Intelligent OLSR Routing Protocol Optimization for VANETs”,IEEE Transactions on Vehicular Technology, Vol. 61, No. 4, May 2012
- d Mohammad Al-Rabayah and Robert Malaney,” A New Scalable Hybrid Routing Protocol for VANETs”, IEEETransactions on Vehicular Technology, Vol. 61, NO. 6, JULY 2012
- HananSaleet, Rami Langar, KshirasagarNaik, RaoufBoutaba, AmiyaNayak, and NishithGoel, “Intersection-BasedGeographical Routing Protocol for VANETs: A Proposal and Analysis”, IEEE Transactions on Vehicular Technology,Vol. 60, No. 9, November 2011.
- Marios D. Dikaiakos, Andreas Florides, Tamer Nadeem, and LiviuIftode,” Location-Aware Services over Vehicular Ad Hoc Networks using Car-to-Car Communication”, IEEE Journal on Selected Areas in Communications, Vol. 25, No. 8,pp.1590-1602, Oct 2007.
- C. Lochert, “A routing strategy for vehicular ad hoc network in the city environments,” in Proc. IEEE Intell. Veh.Symp.,2003, pp. 156–161 and Philip S. Yu (2008), „A Survey of Association Rule Hiding Methods for Privacy‟, A hand book ofPrivacy- preserving data mining: models and algorithms, Kluwer Academic Publishers, London, pp.32-39.
- C D.RajiniGirinath ,S.Selvan, ”A Novel Cluster based Routing Algorithm for Hybrid Mobility Model in VANET.” 2010 International Journal of Computer Applications (0975 - 8887)
- D V. Naumov, R. Baumann, and T. Gross, “An evaluation of intervehicle ad hoc networks based on realistic vehiculartraces,” in Proc. ACM MOBIHOC, 2006, pp. 108–119.
- KejunLiu,Jing Deng, Pramod K. Varshney and KashyapBalakrishnan,” An Acknowledgement-Based Approach for theDetection of Routing Misbehavior in MANETs”, IEEE Transactions on Mobile Computing, Vol. 6, No.5,pp.488-501, May2007.
- Jane Y.Yu and Peter H.J. Chong, ”A Survey of Clustering Schemes For Mobile Ad Hoc Networks”, IEEECommunications& Surveys ,Vol. 7, No.1,pp.32-48,2005.
|
Menu