Junction Based on Demand Routing Protocol for Vanets

Junction Based on Demand Routing Protocol for Vanets

Ann Mary Jacob

Dept of Information Technology Rajagiri School of Engineering & Technology

Kochi, India

Saritha S

Dept of Information Technology Rajagiri School of Engineering & Technology

Kochi, India

AbstractVehicular network is a futuristic technology in which the smart and moving vehicles form a network.These vehicles form a network to communicate some useful information such as chances of accidents,local information like parking lots , present road conditions. Even though MANET and VANET comes under the same category of Ad hoc networks,due to the peculiar characteristics of VANET

,using the protocols of MANET will not give efficient results.This paper proposes an On Demand routing protocol for VANET which make use of Vehicle to Infrascture (V2I) communication.The proposed routing protocol is simulated using Vanet Mobisim and ns2 to study the efficiency of the protocol.

KeywordsVANETs;junctions;on-demand;reliability

1. INTRODUCTION

   VANET is an emerging technology that falls under the category of Ad hoc network. Many researches are going on in this area and the major players in this field of research include Audi,Toyota,Nissan,Ford and BMW. The VANET is a special case of Mobile Ad hoc Network (MANET) with frequent changes in the topology and a highly self organizing form of network [1].There are mainly three factors that differentiate VANET from that of MANET[2].

   1. Large number and high mobility

      Unlike other network,one cannot predict the number of vehicles on the road at any point in time. There are certain peak times at which the number of vehicles on the road is very large and there are also cases where there are very few vehicles on the road. Thus one should consider both extreme cases when designing protocols for vanet. Also the vehicles move at a very high speed and so the position of the vehicles is very difficult to identify.

   2. Restricted Topology

      On the road,as we know there are certain restrictions to the vehicular movement. The vehicles can move only on the roads which are surrounded by restrictions like buildings and trees.

   3. Unconstrained power consumption

   Power consumption is a serious factor in designing protocols for mobile networks. However this factor does not affect the vehicular communication as vehicles run on fuel and power consumption therefore not a big deal.

   Table 1 shows a comparison between VANET and MANET. From the table it can be inferred that both are different in many aspects. All these factors points to development of new routing protocols for VANET. Further more authors of [3] conclude that using routing protocols of MANET in VANET shows poor performance.

   Table 1: Comparison of Manet and Vanet

   PARAMETER	MANET	VANET
   Mobility	Low	High
   No. of Nodes	Medium	Huge & Frequently Changing
   Range	Up to 100m	Up to 500m
   Power Consumption	Critical	Non critical
   Reliability	Can be achieved	Difficult to achieve
   Position Identification	Ultrasonic Sensing	GPS system

   Developing routing protocols for VANET is challenging because of the following reasons:

   1. Scalability

      As specified earlier , one of the characteristics of vanet is the number of vehicles forming a network. The protocols should be designed so as to support very small number of vehicles and also large number of vehicles.

   2. Reliability

      Due to the high mobility of vehicles, its always very difficult to achieve a reliable communication. One can say that a communication is reliable only if the delivery of data packet can be guaranteed.

   3. Confidentiality and Integrity

   These two are concerned with the security of communication. Confidentiality of data ensures that the data is not leaked or disclosed to unauthorized nodes and integrity is the assurance

   that the data received are exactly the same sent by the authorised node without any modification, deletion, insertion or replay. There should be some mechanism by which the security can be ensured in communication.

   Due to high mobility, frequent changes in topology and limited life time routing decisions becomes more challenging in VANETs. Compared to MANET,in vanet the position of nodes are explored in designing routing protocols. Some of the position based routing protocols in VANET include Greedy Perimeter Stateless Routing (GPSR) , Geographic Source Routing- GSR and Anchor-based Street and Traffic Aware Routing- A-STAR.

   Due to the high mobility and rapid position change the researchers were compelled to the development of position based routing. Such method in which geographical positions of nodes are used to perform data routing from source to destination is called position based routing[12].In position based routing approach it is assumed that each node is equipped with a GPS or position identification system so that it is aware of the position and also the neighbours position. A position based routing protocol consists of many major components such as beaconing, location service and servers and recovery and forwarding strategies .Beaconing messages are sent periodically among the vehicles to pass the location information about itself to the neighbouring nodes. Location service is used by a node when it does not have the information about a particular node in its table. In such a case it will send a request with the unique id of the vehicle and waits for the reply. It updates the table according to the reply message. Recovery and forwarding strategies are used to send data to the desired destination and also to maintain the available routes.

   There are three forwarding mechanisms available in VANETs:

   Restricted directional flooding

   In this source node send the data packet to the zone to forward till destination. Restricted directed flooding uses broad based protocols such as Mobility-centric data dissemination algorithm for vehicular networks (MDDV) [4].

   Hierarchical forwarding

   Protocols hierarchy is used in different steps of forwarding and geodesic packet forwarding (GPF) is used in this system.

   Greedy forwarding

   In this system the data packet is forwarded to a node which is more close to the destination. The sending node chooses the minimum number of hops to reach the destination as the route.

   In this paper ,we propose an algorithm Reliable Junction based On Demand Routing Protocol For Vanets a new routing protocol which consider road side units as intermediate nodes. Efforts are made to reduce the packet drop. The remaining of this paper is divided as follows. Section II discuss some of the existing systems. Section III includes the characteristics and design of the proposed algorithm. Section IV demonstrates the performance evaluation and finally section V concludes the paper.

2. EXSISTING SYSTEM

   Routing Protocols are a set of rules that specify how the data get transmitted across the network. It will include route discovery,data forwarding,route maintainable and route recovery. Three important routing protocols for VANET designed so far are:

   1. Greedy Perimeter Coorinator Routing -GPCR

      This algorithm takes the advantage of the junctions on the street and the idea that the junctions form a planar graph. Two parts of GPCR are a restricted greedy forwarding procedure and a repair strategy. Greedy algorithms are used for forwarding of data packet. In greedy forwarding mechanism a node nearer to the destination is selected and then the data is send to that node. Thus always minimum number of nodes is given priority in routing the packet. When the greedy approach fails,i.e. when there is no next hop closest neighbour to the destination is available then perimeter forwarding is used. In perimeter forwarding approach it uses a right hand rule.

   2. Geographic Source Routing- GSR

      Due to deficiencies of GPSR in presence of radio obstacles, network demanded new routing strategies that can compete with challenges occurred due to radio obstacles. Therefore,Geographic Source Routing (GSR) is proposed [11]. It deals with high mobility of nodes on one hand, on the other hand it uses roads layout to discover routes. GSR finds the destination node using Reactive Location Service (RLS). GSR combines both geographic routing and road topology knowledge to ensure promising routing in the presence of radio obstacles [11].

   3. Anchor-based Street and Traffic Aware Routing- A-STAR This is a position based protocol which takes into consideration all the obstacles on the road sides like building,speed breaker etc. It is an anchor based routing in the sense that the entire route information is injected into the data packet by the source. Spatial awareness is used to get topology information and different nodes position in the network. The difference between A-STAR and GSR is that even though both uses junctions as intermediate nodes,A- STAR also consider the road situations. For that it uses both statistical map and dynamic map of the city. Using the statistical map it gets information about the scheduled timing of buses as the buses provide more connectivity. Using the dynamic map it takes the current road status to decide the route.

3. JUNCTION BASED ON DEMAND ROUTING PROTOCOL

   So far many researches are going on in the field of VANET and many protocols have been proposed for routing. Almost all the protocols explore the advantage of positions. It may include position of vehicles as well as position of RSUs. Almost all the protocols designed so far are position based. Most of the studies suggested that using vehicles as intermediate nodes cannot achieve reliability due to its mobility. There are studies done which uses junctions as

   intermediate nodes[5].The benefit of using junctions is that the paths become more reliable. Junctions denote road side units which are stationary objects. Analysis of different routing protocols in VANET shows that using proactive routing approach will not provide an efficient system. Hence a reactive routing protocol is required. Further due to the limited memory size it is always better to use on demand routing protocol were the route is identified as and when a data is to be send. Hence this protocol is not designed for beaconing or geo multicast data transmission[6]. This protocol aims to propose a novel unicast routing algorithm in VANETs. This algorithm could be used in such situations were the source

   needs to send a data to a particular destination. The destination may or may not be in the transmission range of the source node. If the source and destination are not in the same transmission range , it uses RSUs as intermediate nodes to transmit the data.

   Thus whenever there is a need to send a data , the source node generates the data packet and will look for an intermediate RSU to send the data packet to. It is assumed that all the vehicles have a GPS system to identify its position. Each vehicle gets connected to an RSU based on some threshold value. The value of threshold depends on the type of application. The threshold value may be calculated based on the number of nodes connected to an RSU,capability of RSU or the shortest distance to an RSU. In this proposal only the distance criteria has been chosen to establish a connection to the RSU. Once the source identifies a RSU , it send the data packet to the RSU. Now the RSU will check for the next RSU to transfer the data packet .This continuous until the destination is reached.

   A.Characteristics

   JDRP is a position based protocol in the sense that the position of junctions is of higher importance than the position of vehicles. This consideration will make the protocol more reliable. The vehicles are highly mobile and if these vehicles are considered as intermediate nodes ,route breakage occurs very often. Junctions represent road side units ,which are stationary and hence the chances of route breakage occurs only if the source or destination vehicle changes its position. To locate the road side units , each vehicle is equipped with a GPS system. Almost all the modern vehicles comes up with a GPS system today and so the cost incurred will not matters. Further it is assumed that each vehicle is provided with a city map by the Road Side Unit whenever the vehicle enters a city. Hence each vehicle will have an idea about the number and position of road side units.

   Further the protocol also adopts a recovery mechanism to reduce the packet drop. Packet drop occurs when the two nodes are not in the same range. The mechanism adopted is specified in the following sections. A model of how the protocol works is as shown in fig1.Here the figure shows a simple road scenario where the first red car denotes the source car which needs to send some data to the second red car. The intermediate nodes which help in the communication are the road side units and the blue cars. Whenever the source car needs to send a data ,it will identify a RSU along its path and will forward the data to the RSU. Now the car will find next

   RSU to forward the data through. Once the RSU is identified the information is send to that RSU with the help of a vehicle along its path. This process goes on until the information reaches the destination car.

   1. Routing Technique Used

      As specified earlier an On Demand Routing technique is used for forwarding the data. Since On demand routing technique is used source need not find the entire route but is the responsibility of the intermediate nodes to find the next intermediate node. Using the GPS system each vehicle will know its own position and also about the neighbouring node. Hop count as in AODV protocol cannot be used in VANET because it is not possible to predict the number of vehicles o n the road. Fig 2 shows the fields of the routing table used. Here the shortest distance is considered as a factor for forwarding the data. Algorithm 1 specifies the proposed routing algorithm.

      Fig 2: Structure of Routing Table

      NODE

      TIME

      NEXT HOP

      DESTINATIO N

      DISTANC E

      Algorithm 1:Routing and Forwarding

      1. Generate the data packet

      2. Send hello packets to identify the neighbours

      3. Calculate the distance between all its neighbours

      4. Find the one with shortest distance and add it to Routing Table

      5. Forward the packet according to Routing Table

      6. Receive the data packet

      7. if packet-id= vehicle-id then

      8. Read the data packet.

      9. else

      10. GOTO step 2

   2. Recovery Scheme used

   Once a route is identified using the routing table ,the first node sends the data to the next node and it goes on until the data reaches the destination. However when a node receives a data and found that there are no intermediate nodes within its range

   , then that node will simply discard the packet. Thus whenever there are no nodes within the range packet drop occurs and it results in poor performance. An idea propose in [7] could be used to reduce the packet drop. According to [7] , whenever a node receives a packet to be forwarded and if there are no intermediate nodes ,then the node will have to hold the packet for quite some time until an intermediate node appears in its range.

   Holding the packet for an undefined time period will not be an efficient technique to reduce the packet drop. Thus each node should be programmed in such a way that a time limit should be set. The algorithm 2 explains the idea.

   Algorithm 2: Recovery Scheme 1.Receive the data packet.

   1. Read the packet-id.

   2. if packet-id= vehicle-id then Read the data packet.

      else

   3. Check the routing table to find an intermediate node.

   4. If a node is available send the data packet to it. else

   5. Hold the data packet for 20ms.

   6. Update the routing table.

   7. Check the routing table to find an intermediate node.

   8. If a node is available send the data packet to it. else

   9. Drop the packet.

4. PERFORMANCE ANALYSIS

   The simulations are done using NS2[8] and VANET mobisim[9] .We simulated the city environment as a rectangular area which includes horizontal and vertical lanes. Each node has a radio range of 350 meter,and uses TwoRayGround as the radio propagation model. All the scenarios are based on the basic parameters as shown in table 2.

   Table 2: Simulation Parameters

   Size of Topology	100m X 100m
   Maximum Speed of each node	5 ms
   Simulation Time	30s
   No: of Nodes	50

   In this paper, we include two performance criteria : Packet delivery ratio(PDR) [10] which is the ratio of the number of delivered data packet to the destination and Packet drop which is the difference between number of packet send and number of packet received .Table 4 shows the simulation result of JDRP with reference to PDR and Packet drop.

   These factors have been compared with the existing on demand routing protocol AODV. Results shows better performance for the proposed system.

   QoS	AODV	JDRP	JDRP with Recovery
   PDR	0.81	0.84	0.91
   Packet Drop	56	56	48

5. CONCLUSION

   Vanet stands for Vehicular ad hoc network which falls under the category of ad hoc network.Vehicular network is a network of moving and smart cars.Many researches are going on in this field.Peculiar features of VANET makes the design of protocols highly challenging.In this paper a novel routing algorithm is proposed. Considering the behaviour of VANET due to high mobility an on demand routing protocol based on junction is proposed. Furthermore to improve the efficiency a recovery scheme based on scheduling time is also proposed. To analyse the proposed system and to learn its efficiency,it has been simulated and compared with AODV protocol. Results show better performance for JDRP protocol. As a future work we intend to add a encryption mechanism to improve the security of the system.

6. REFERENCES

1. D. Reichardt, M. Miglietta, P. M. L. Moretti, and W. Schulz,CarTALK 2000 – Safe and Comfortable Driving Based Upon IntervehicleCommunication. in IEEE Intelligent Vehicle Symposium, June 2002, vol. 2.2002.

2. Bijan Paul ,Md. Ibrahim and Md. Abu Naser Bikas,VANET Routing Protocols: Pros and Cons International Journal of Computer Applications (0975 8887) Volume 20No.3, April 2011.

3. Preetida Vinayakray-Jani1 and Sugata Sanyal , Routing Protocols for Mobile and Vehicular Ad Hoc Networks: A Comparative Analysis

4. H. Wu, Fujimoto, R., Guensler, R., and Hunter, M, MDDV: a mobility- centric data dissemination algorithm for vehicular network, Proceedings of the 1st ACM international Workshop on Vehicular Ad Hoc Networks pp. 47-56, October, 2004.

5. C. Lochert, M. Mauve, H. F ler, and H. Hartenstein, Geographic routing in city scenarios,ACM SIGMOBILE Mobile Computing and Commun. Rev., vol. 9, pp. 692, Jan. 2005.

6. C. Lochert, H. Hartenstein, J. Tian, H. Fuessler, D. Hermann, and M. Mauve,routing strategy for vehicular ad hoc networks in city environments,in Proc. 2003 IEEE Intelligent Vehicles Symposium, pp. 15661.

7. P Sermpezis, G Koltsidas, and F Pavlidou,Investigating a Junction-based Multipath Source Routing algorithm for VANETsCommunications IEEE,mar. 2013.

8. Network Simulator 2.Available: http://www.isi.edu/nsnam/ns.

9. J. Harri, F. Filali, C. Bonnet, and M. Fiore, anetMobiSim: generating realistic mobility patterns for VANETs,in Proc. 2006 ACM International Workshop on Vehicular Ad Hoc Networks.

10. http://harrismare.net/2011/07/14/packet-delivery-ratio-packet-lost-end- to-end-delay/

11. C. Lochert, H. Hartenstein, J. Tian, D. Herrmann, H. Füßler, and M. Mauve, A routing strategy for vehicular ad hoc networks in city environments, in Proceedings of IEEE Intelligent Vehicles Symposium (IV2003), pp. 156161, June 2003.

12. Bilal Mustafa,Umar Waqas Raja,Issues of Routing in VANET,School of Computing Blekinge Institute of Technology.