BAHG: Back-Bone-Assisted Hop Greedy Routing for VANET’s City Environments

BAHG: Back-Bone-Assisted Hop Greedy Routing for VANET’s City Environments


Using advanced wireless local area network technologies, vehicular ad hoc networks (VANETs) have become viable and valuable for their wide variety of novel applications, such as road safety, multimedia content sharing, commerce on wheels, etc. Multihop information dissemination in VANETs is constrained by the high mobility of vehicles and the frequent disconnections. Currently, geographic routing protocols are widely adopted for VANETs as they do not require route construction and route maintenance phases. Again, with connectivity awareness, they perform well in terms of reliable delivery. To obtain destination position, some protocols use flooding, which can be detrimental in city environments? Further, in the case of sparse and void regions, frequent use of the recovery strategy elevates hop count. Some geographic routing protocols adopt the minimum weighted algorithm based on distance or connectivity to select intermediate intersections. However, the shortest path or the path with higher connectivity may include numerous intermediate intersections. As a result, these protocols yield routing paths with higher hop count. In this paper, we propose a hop greedy routing scheme that yields a routing path with the minimum number of intermediate intersection nodes while taking connectivity into consideration. Moreover, we introduce back-bone nodes that play a key role in providing connectivity status around an intersection. Apart from this, by tracking the movement of source as well as destination, the back-bone nodes enable a packet to be forwarded in the changed direction. Simulation results signify the benefits of the proposed routing strategy in terms of high packet delivery ratio and shorter end-to-end delay.


In a city network, intersections place a unique challenge to routing protocols. A routing protocol has to key on some parameters to decide the routing path. When the routing path is the shortest distance path, it may involve a very high number of change of directions, resulting in higher hop counts. If the connectivity is chosen as the parameter, the most connected road segment would be overcrowded by frequently routing data packets through the same path.


    Apparently, the multi constrained optimal path finding problems are known to be NP-hard problems.

    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.



In this paper, we introduce a back-bone mechanism in which some specialized nodes perform functions such as tracking the movement of end nodes, detecting void regions on road segments, storing packets on unavailability of forwarding nodes, and selecting the most suitable intersection node as the forwarding node. Since the routing algorithm selects a path using destination position, we employ a unicast request-reply-based destination probing mechanism. To implement this approach, we divide the city into many zones that are outlined by the multilane road structures. Some dense intersections (identified as the meeting point of multiple road segments) on the boundary of the zones are chosen as the boundary intersections. As the position of each boundary intersection is known, the unicast request messages initiated by the source can be easily sent to each boundary intersection. The back-bone nodes stationed at boundary intersections then take the responsibility to spread the request messages within the respective zones. The fact that unicast packets do not provide burst traffic and is shielded by request to send/clear to send (RTS/CTS) handshake is the basic motivation to adopt unicast to carry out all control packet transmissions. Once the destination receives the request message, it finds a suitable path to the source and sends the reply. On receiving the reply message, the source forwards data on a routing path computed by the hop greedy routing algorithm. Finally, the routing protocol includes an update mechanism that takes care of inter-zone movement of end nodes.


ü We have explored crucial problems such as unreliable location service, intersection node probing problem, etc., experienced by VANET routing protocols.

ü We then propose a hop greedy routing protocol that aims to reduce the end-to-end delay by yielding a routing path that includes the minimum number of intermediate intersections.

ü To address connectivity issues such as void regions and unavailability of forwarders, the concept of back-bone node is introduced.

ü We also propose an update procedure that is very effective to deal with destination movements.



ü Processor             –        Pentium –III

ü Speed                             –         1.1 Ghz

ü RAM                    –        256 MB(min)

ü Hard Disk            –        20 GB

ü Key Board            –        Standard Windows Keyboard

ü Mouse                  –        Two or Three Button Mouse

ü Monitor                –        SVGA


v   Operating System          : LINUX

v   Tool                               : Network Simulator-2

v   Front End                      : OTCL (Object Oriented Tool Command  Language)



Pratap Kumar Sahu, Eric Hsiao-Kuang Wu,Member, IEEE, Jagruti Sahoo, and Mario Gerla “BAHG: Back-Bone-Assisted Hop Greedy Routing for VANET’s City Environments”- IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, VOL. 14, NO. 1, MARCH2013.


About the Author