An intersection based traffic aware routing with low overhead in VANET.
During the last few years vehicular communication is attracting growing attention from both academic and industrial point of view. This is because of applications ranging from road safety to traffic control and up to infotainment.
Vehicular ad-hoc networks (VANETs) are self organized networks built up from moving vehicles. Fig. 1 gives an overview of VANET. VANETs are instantiation of Mobile Ad-hoc Networks (MANETs). As in MANETs packet forwarding in VANET takes place through multi hop relaying. There are certain features that distinguish VANETs from MANETs. These include high mobility of nodes, frequent network partition; constraints on roadways etc. These characteristics pose technical challenges to implement a high performance VANET.
Vehicular networks can be used to facilitate the service customization to the needs of individual nodes. Possible applications  for such network can be generally classified as safety and non safety applications. Safety applications include cooperative driving, accident avoidance etc. Non-safety applications include traffic information, toll service, internet access, games, entertainment etc.
The main component for success of VANET applications is its routing. The history of VANET routing protocols starts with MANET routing protocols such as Ad-hoc On Demand Distance Vector routing (AODV) , Dynamic Source Routing  etc. But these protocols fail to address certain peculiar characteristics of VANET. Various routing protocols especially for VANET were proposed to make routing more efficient and reliable.
In this article we consider the vehicular communication in highly dense urban environment. Intersection based routing protocols are highly reliable in such environment. In intersection based routing, when vehicles move on straight road, they forward by greedy forwarding. When they reach an intersection a decision is made whether to forward in same direction or to perpendicular direction.
Many intersection based routing protocols have been proposed to carry efficient routing in VANET. But only few protocols consider traffic lights. The existing protocols that consider traffic lights are having high overhead. This paper proposes a new routing protocol having low overhead. The remaining of this paper is organized in to following sections: Section II gives related works, Section III describe the problem with traffic lights, Section IV gives the new approach and finally Section V concludes the paper.
2 RELATED WORKS
VANET routing protocols can be categorized in to two: topology based and geographic (position based) routing protocols. In topology based routing protocols each node is expected to know the entire network topology. In Geographic or position based routing protocols the decision on routing is based on the position of the sender, position of the destination and position of the senders one hop neighbors using GPS. It is assumed that each node knows its position and the position of the destination. The position of its one hop neighbors is obtained from periodically exchanged beacons. In geographic routing the messages can be forwarded to destination without knowing the topology and without prior route discovery. This section briefly describes some prominent geographic routing protocols.
2.1 Greedy Perimeter Coordinator Routing (GPCR)
Greedy Perimeter Coordinator Routing  makes use of street and junctions to forward packets. GPCR consists of 2 parts: a restricted greedy forwarding procedure and a repair strategy.
In all intersection based routing protocols the actual routing decision is made on junctions. In GPCR nodes on junctions are called coordinators. Packets are always forwarded to these coordinators rather than to nodes across the junction. If coordinators are not present, the packets are forwarded to node with the largest distance from the forwarding node. If more than one coordinator is present then one is taken randomly and packet is forwarded to this coordinator. In this protocol a decision is made greedily so that a node with great progress to destination is always selected. When packet reaches a local optimum, Right Hand Rule is used to see to which street the packet should follow as the repair strategy.
GPCR is effective as it does not need any external information and graph planarization algorithms. But first part of GPCR fails on curve road and second approach fails on sparse road. It selects street without understanding whether there are sufficient nodes to carry the packet.
2.2 Improved Greedy Traffic Aware Routing (GyTAR)
GYTAR  is an intersection based routing protocol. It consists of 2 modules: dynamic junction selection through which a packet must reach destination and an improved greedy strategy used for forwarding. A forwarding node looks for the neighboring junctions in digital map. Then it assigns a score to each of these junctions considering the traffic density and curve metric distance to destination. The score is calculated as in Eq. 1.
ScoreJ = [alpha] [1-Dp] + [beta] [min([N.sub.avg]/[N.sub.con],1)] (1)
[D.sub.j]: curve metric distance from candidate junction j to destination
[D.sub.i]: curve metric distance from junction I to destination.
[D.sub.p]: ([D.sub.j]/[D.sub.i]) closeness of candidate junction to destination point Between junction I and J:
[N.sub.v]: number of vehicles between I and J
[N.sub.c]: no of cell between I and J
[N.sub.avg]: average number of vehicles per cell ([N.sub.v]/[N.sub.c])
[N.sub.con]: constant that gives ideal connectivity within a cell.
[alpha], [beta]: weighting factors for distance and vehicular traffic ([alpha] + [beta] = 1).
The junction with highest score is selected to forward the packet. Once junction is selected the next phase is to forward the packet between these junctions. Each vehicle maintains a neighbor table which is updated using periodically exchanged HELLO messages. When a node receives a packet it computes the new predicted position of each neighbor using the information recorded and then selects the next hop. In case of local optimum recovery strategy used in GyTAR is Carry and forward. In carry and forward recovery mechanism the node carries the packet until next junction or another vehicle closer to the destination comes to its transmission range.
Advantages of GyTAR are: it reduces control message overhead and efficiently handle often occurring network partitions. The disadvantage is higher neighbor table overhead in highly dynamic environment.
2.3 Vehicle Assisted Data Delivery (VADD)
VADD  aims at improving routing in disconnected networks by using the idea of carry and forward together with vehicular mobility prediction. This protocol relies mainly on 3 basic principles: First, whenever possible transmit through wireless link. Second, roads with highest speed should be chosen if the packet need to be forwarded along road. And at last dynamic path selection is carried during the entire packet forwarding process. VADD defines three packet models: Straight road, Intersection and Destination.
In intersection mode it uses protocols like L-VADD, D-VADD, and H-VADD. Location First Probe VADD (L-VADD) selects a node closest to the next forwarding path. Direction First Probe VADD (D-VADD) selects a node that is going towards the next forwarding path. Hybrid VADD (H-VADD) combines LVADD and D-VADD. Out of these, H VADD has higher performance.
Advantage of VADD is its high delivery ratio compared to other routing protocols. At each intersection VADD takes the best path available. But when density is low optimal path may not be always available. VADD estimates delay based on statistical data. As vehicle density changes with time, the shortest delay may not be the real optimal one.
2.4 Static Node Assisted Adaptive Routing Protocol In Vehicular Networks (SADV)
Static Node Assisted Adaptive Routing Protocol  in Vehicular Networks deploys a static node at intersections. This static node stores packet and wait until there are vehicles within communication. The static notes have a digital street map. SADV have 3 modules: Static Node Assisted Routing (SNAR), Link Delay Update (LDU) and Multi Path Data Dissemination (MPDD). SNAR: SNAR utilizes the static nodes deployed at intersections to store and forward through optimal paths.
LDU measures delay from Static node si to static node sj by inserting a single field stime in to packet head. When si receives a packet, it records current time in stime. When packet reaches sj it calculates delay as in Eq. 2.
d (si, sj) = current time - stime (2)
MPDD: When the load in network is not too high multi path routing is used to decrease delay by hitting a faster path than single path.
The advantages of SADV are: SNAR module stores and forwards packet through the best available path, LDU module effectively calculates the real time delay and MPDD reduces the delay. But practically, deployment of static module at each intersection is not feasible.
2. 5 Virtual Vertex Routing (VVR)
Virtual Vertex Routing  introduces a new concept called virtual vertex that is proximity of a vertex and uses the information about lines. Proximity of a vertex refers to the area within the circle with vertex as centre and radius is half the radio range. An intermediate node in the proximity uses Floyd Algorithm to forward packet to the destination. In VVR edge connectivity is maintained by exchanging HELLO messages.
The basic VVR mechanism includes two parts: Initialization and Vertex Change. VVR model consists of vertices (junctions), edges (straight-line between 2 junctions) and nodes (vehicles). During initialization the shortest path between all pairs of vertices is calculated using Floyd's algorithm. Vertex change: Packets in VVR is forwarded from one vertex to another vertex. When a packet arrives at a vertex, intermediate destination vertex is selected. Here comes the proximity of vertex. That is any node in the proximity of geographical location of vertex acts as a vertex. This process continues until the packet reaches the proximity of last vertex. When the last vertex proximity is reached the packet is greedily forwarded to the destination.
The advantage of VVR is that, it rarely falls in to routing holes. This is because of prior knowledge to distribution of nodes. The disadvantage is its high overhead.
2. 6 Shortest Path Based Traffic Aware Routing (STAR)
Shortest path based Traffic Aware Routing  is an intersection based routing protocol proposed for urban areas where traffic density is high and intersections are deployed with traffic lights. In urban areas with traffic lights, the routing path will be alternating with red and green light segments. The vehicles will be moving in a stop-and-go pattern. Due to red light the vehicles may be gathered at the intersections and as a result of this the segment connectivity is disconnected. The segment is reconnected by vehicles moving from green light to red light segment. STAR makes use of these connected red light segments.
In STAR, before reaching an intersection the packets are forwarded greedily with carry and forward recovery mechanism. When a packet reaches an intersection it checks whether the red light segment close to the destination is connected. If connected, the packet is forwarded to this red light segment. If no red light segments are available the packet is forwarded to green light segment. The segment connectivity is learned by broadcasting connectivity information. Each vehicle approaching the intersection broadcasts its connectivity information. All nodes hearing this, rebroadcasts the information. This is repeated until the vehicles on the other segment hear this connectivity information.
3 PROBLEMS WITH TRAFFIC LIGHTS
In urban areas the intersections are employed with traffic lights. These traffic lights divide the road in to different segments. The vehicles move smoothly on a green light segment and when light turns to red they slow down and wait at intersections until the light turns green. Thus the vehicles tend to cluster at both directions in a red light segment. The figure 2 shows a disconnected segment. In the figure vertical line shows green light segment and horizontal line shows red light segment. Thus traffic lights frequently create disconnected links on a red light segment.
In this paper the above problem is tackled by the vehicles turning right from a green light segment to red light segment. These vehicles ensure connectivity on a red light segment.
4 RED LIGHT FIRST FORWARDING
Shortest Path Based Traffic Aware Routing (STAR) protocol is an intersection based routing protocol that takes traffic light in to consideration. STAR also makes use of the vehicles turning right from green light segment to red light segment to ensure end to end connectivity on a red light segment. In STAR the segment connectivity is measured by broadcasting connectivity information. This broadcast mechanism leads to serious problems like redundancy, contention and collision of messages. This problem is referred as broadcast storm problem . Thus STAR protocol introduces much overhead in the network.
In this paper we tackle this problem by introducing a new intersection based routing protocol with low overhead. This paper proposes a protocol "Red Light First Forwarding (RLFF)" which avoids blind flooding to measure connectivity. In Red Light First Forwarding, it is assumed that each vehicle is employed with GPS and each node knows its position, position of its neighbours and position of destination.
On a straight road, the vehicles forward packets by greedy forwarding together with carry and forward recovery mechanism. In greedy forwarding when a node wants to send a message to destination, it checks whether the destination is reachable. If the destination is in its transmission range the message is forwarded directly. If destination is not reachable, it forwards the packet to an intermediate node which is near to the destination than itself. When it reaches an intersection, it checks whether the red light segment near to destination is available. The connected red light segment is given prior importance than green light segment. Thus the packets always stay on connected links.
In RLFF segment connectivity is measured by broadcasting connectivity information. Each vehicle approaching an intersection sends out broadcast messages. In RLFF only vehicles having maximum progress from broadcasting source is allowed to rebroadcast.
In new approach relative distance between hosts is used to decide whether to drop a rebroadcast. This approach eliminates the broadcast storm problem. Suppose a host 'H' hears a broadcast message from a source 'S' for the first time. Say 'd' be the distance between H and S. If the distance d is small, the rebroadcast can provide only a small additional coverage. If d is large it provides larger additional coverage area. This idea is used in this approach.
Let [d.sub.min] measures the distance between host and the source from which the broadcast message is heard and D be the threshold distance.
Step 1: When a message is heard for first time, initialize [d.sub.min] as distance to the broadcasting host. If [d.sub.min] < D go to step 4.
Step 2: Wait for random number of slots. Then submit the message for retransmission and wait for retransmission to start. If the message is heard again, go to step 3. Otherwise the message is retransmitted and exits the procedure.
Step 3: Update [d.sub.min] if distance to host from which message is heard is smaller.
If [d.sub.min] < D go to step 4. Otherwise resume the interrupted waiting.
Step 4: Cancel retransmission. Exit the procedure.
RLFF is designed to have low network overhead, minimum delay and high delivery ratio.
VANET have recently been the topic of extensive research due to its wide range of application. Routing is the main component for success of VANET applications. There are lots of routing protocols designed especially for VANET. But most promising for urban scenario is intersection based routing protocols. This paper deals with an intersection based routing protocol that consider traffic lights and having low overhead. Designing of routing protocols that handle all applications is not at all practical.
This approach will be simulated in ns2  by generating mobility models using VanetMobiSim . The performance of new protocol will be measured in terms of network overhead, delivery ratio and delay and will be compared with existing protocols like STAR and GyTAR.
[1.] Yasser Toor, Paul Muhlethaler, Anis Laoutti and Arnaud De La Fortelle "Vehicular Ad-hoc Networks: Applications and related technical issues", IEEE Communications Surveys, 3rd Quarter 2008, Vol 10, No.3.
[2.] Perkins, C.; Belding Royer, E.; Das, S" Ad-hoc On Demand Distance Vector Routing", IETF RFC, 3561, July 2003.
[3.] D. B. Johnson and D. A. Maltz, "Dynamic Source Routing In Ad-hoc Wireless Networks, in Mobile Computing, chapter 5, 1996.
[4.] Christian Lochert, Martin Mauve, Holger Fubler and Hannes Hartenstein "Geographic Routing in City Scenarios! MobiCom 2004 Poster Abstract.
[5.] Moer Jerbi, Sidi-Mohammed Senouci, Rabah Meraihi and Yacine Ghamri-Doudane, "An Improved Vehicular AdHoc Routing Protocol for City Environments", IEEE ICC'07, pp.3972-79.
[6.] Jing Zhao and Guohong Cao, "VADD: Vehicle-Assisted Data Delivery in Vehicular Ad-Hoc Networks", IEEE Transactions on Vehicular Technology, Vol. 57, No. 3, May 2008.
[7.] H.Lee, Youndo Lee, Taekyoung Kwon and Yanghee Choi "Virtual Vertex Routing (VVR) for Course Based Vehicular Ad-Hoc Networks", IEEE WCNC'07, pp.4405-10.
[8.] Y.Ding, C.Wang and L.Xiao "A Static -Node Assisted Adaptive Routing Protocol in Vehicular Networks", ACM VANET '07, pp.59-68.
[9.] Rupesh Kumar and S.V Rao "Directional Greedy Routing Protocol (DGPR) in Mobile Ad-hoc Networks" ,International Conference on Information Technology, 2008.
[10.] Jin-Jia-Chang, Yi-Hua Li, Wanjiun Liao, Ing-Chau Chang "Intersection Based Routing in Urban Vehicular Communication with Traffic Light Considerations", IEEE Wireless Communication, Feb 2012.
[11.] Yu Chee Tseng, Sze Yao Ni, Yuh Shyan Chen ang Jang ping Sheu, "The Broadcast storm problem in Mobile Ad-hoc Network", wireless networks 2002.
[12.] Ns-2. http://www.isi.edu/nsnam/ns.
[13.] M. Fiore and J. Harri, "The Networking Shape of Vehicular Mobility", ACM MobiHoc '08, pp. 261-72.
Lakshmi Ramachandran (1), Sangheethaa Sukumaran (2), Surya Rani Sunny (3)
(1,3) M.Tech Computer Science & Engineering, Calicut University, India
(2) Associate Professor, Calicut University, India
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||vehicular ad-hoc networks|
|Author:||Ramachandran, Lakshmi; Sukumaran, Sangheethaa; Sunny, Surya Rani|
|Publication:||International Journal of Digital Information and Wireless Communications|
|Date:||Apr 1, 2013|
|Previous Article:||An optimized energy aware chaining technique for data gathering in wireless sensor networks.|
|Next Article:||Peer knowledge assisted search using community search logs.|