Geographic Routing In Vanets

Liam Avella-Pisera

The following is a paper I wrote for a graduate networking class at the University of Melbourne. A link to the properly formatted pdf is available here. The title “Geographic Routing in VANETs” was inherited from the brief, I however choose to focus my discussion on a very specific area of interest. This work received 93% and was graded at a graduate coursework standard in the Faculty of Engineering.

I. Introduction

In Vehicular Ad-hoc Networks (VANETs) maintaining reliable communication is a challenge due to the high mobility of vehicles, frequent topology changes and intermittent connectivity. Traditional routing protocols assume stable and continuous connections and struggle in dynamic environments. Since geographic information is of relevance to fast moving vehicles, routing based on geographic location has become popular means by which route orientations can be determined. Vehicles manage their own location data and the locations of neighbouring vehicles with the aid GPS to make informed routing decisions about next hop rather than making use of tradition routing tables[1]. This approach creates many opportunities for constraint optimisation since most geographic-based protocols employ a heuristic.

II. Related Work

Vehicular Delay/Disruption Tolerant Networks (VDTNs) are a specialised form of Delay Tol- erant Networks (DTNs) designed to address the challenges peculiar to VANETs [2]. VDTN represents a special case of VANET research. VDTNs tolerate delays and disruptions in network connectivity by utilizing store-carry-forward mechanisms. Data packets are stored temporarily in a vehicle’s memory and carried until a connection can be established with the next node[3][4]. This approach ensures that messages eventually reach their destination even if an end-to-end path does not exist at all times. In order to understand the VDTN category within VANETs, a brief history of the routing failures in this space is rehearsed in this section. There are two main category schemes for VANETs. The first scheme separates based on the nature of the routingprotocol across categories: ad hoc, cluster-based, broadcast, geocast and geography-based [5] [6]. Within geographic routing there is a focus on delay tolerant networks with a putative correspondence of consumer needs over a beacon-less Vehicle-to-Vehicle environment [7]. The following will address the ontology of VDTN.
VANETs are decentralized networks that function independently of traditional networking infrastructure, with connections routed hop-by-hop, where users act as custodians of messages en route. This presents unique challenges compared to other networking protocols. Despite efforts to develop specific VANET routing protocols, the first generation of these protocols carried major assumptions from IP-based networks, implementing a store-and-forward approach. They assumed that a route could generally be found from a source to a destination if a delay was acceptable. Consequently, these protocols struggled with long disruptions and suffered significant efficiency losses as delays increased[1]. They failed to handle the extreme networking conditions common in vehicular networking.
DTN – To address the shortcomings, DTNs were applied to VANETs. DTNs are used in con- texts where intermittent connectivity is commonplace, such as interplanetary communications, and networking conditions where frequent and prolonged periods of disconnection between nodes is a consistent possibility[1]. This concern necessitates protocols that can adapt to rapid changes in network structure. Along with these constraints, nodes in DTNs often face resource constraints, including limited power and storage capacities, which demand energy-efficient and storage-efficient communication strategies. DTNs also often have high mobility, resulting in a highly dynamic network topology and variable node density, which is a putative concern in vehicular networking. They tolerate high latency, accommodating significant delays in data de- livery, making them suitable for delay-insensitive applications where immediate communication is not critical. The network’s heterogeneity further complicates the scenario, as DTNs often comprise diverse devices with varying capabilities, requiring interoperability and communication support across different types of nodes. Finally, Opportunistic communication is a common case of DTNs, where data transfer occurs opportunistically as nodes come into contact with each other. This necessitates adaptive routing decisions based on current network conditions and node availability. To handle frequent disruptions and ensure data delivery despite network fragmentation, DTNs employ robust protocols, redundancy, and replication techniques [3].
Store-Carry-and-Forward – (SCF) To address these problems, an SCF mechanism is im- plemented where nodes store data packets until a communication opportunity arises and then forward them to the next hop or destination [3]. Contrasting significantly with the store-and- forward operation used in Internet routing a DTN node can store a bundle permanently and carry it until a suitable forwarding opportunity arises. This allows data to be held and transported over long periods and distances until the node encounters another suitable node to relay the bundle.
The Bundle Protocol – In [4] the DTN Research Group (DTNRG) proposed an architecture and the Bundle Protocol for DTNs. A message-oriented overlay layer called the “Bundle Layer” is added above the particular layer(s) of the networks it interconnects. The Bundle Layer transforms application data units into protocol data units called “bundles,” which are then forwarded by DTN nodes according to the Bundle Protocol [8]. These bundles contain all the information needed by the destination to complete a transaction in one go, including protocol and authentication data, which is crucial since multiple round trips between nodes may not be feasible. The protocol allows bundles to be stored permanently and forwarded in a hop-by-hop scheme, rather than end-to-end, whenever a new transmission opportunity arises—such as when two DTN nodes come into contact. Notably, the protocol does not provide error detection or correction capabilities, which must be managed by upper layers[4]. This approach minimizes the number of round-trip exchanges by bundling all necessary transaction information, which benefits environments with large round-trip times. Bundles also contain metadata such as an originating timestamp, a useful life indicator, a class of service assignment, and a length indicator to aid in routing and scheduling decisions.
Custody Mechanism – Described in [3], a node is typically responsible for the bundles it carries until they are delivered or transferred to another node. The custody mechanism allows a DTN node to transfer responsibility for bundles to another node, enabling replication, modification, or deletion of the bundles by the new custodian. This is particularly useful when the current node is no longer suitable for forwarding the bundles and only one replica remains.

III. Routing Protocols

Early research in vehicular ad hoc networks applied well-known Mobile Ad-Hoc Network routing protocols such as AODV and DSR[9]. These protocols were initially considered due to their applicability in dynamic environments. However, they struggled to perform adequately in VANETs due these protocols insistence on maintaining complete end-to-end paths which is difficult under conditions of frequent topology changes and high maintenance costs [9]. This led to the development of VANET-specific protocols like GPSR relied on assumptions of stableconnections typical of traditional internet protocols[10]. DTNs were introduced to address the shortcomings of traditional network protocols in environments with intermittent connectivity and high latency[3]. The store-carry-forward mechanism central to DTNs allows data packets to be stored temporarily and forwarded opportunistically, ensuring eventual delivery even in the absence of a continuous end-to-end path[2][3]. Protocols such as Epidemic Routing, Spray and Wait and PRoPHET demonstrate DTN strategies and offer varying trade-offs between delivery probability, resource usage and delay[2].
Numerous routing protocols have been proposed in the literature, utilising various different forwarding approaches and replication strategies, each requiring distinct types of information to make forwarding decisions. However only a few operational use cases exist for VANETs with a dominant protocol filling a particular niche nor large-scale implementations have been applied [11][7]. Industrial standards have yet to be sufficiently cohered and owing largely to commercial interests, architecture and protocols are often kept under trade secret[7]. Additionally, while there has been a sustained effort to formalise a benchmark process for VANET simulation it remains a matter of active contention [7][11][9].
VADD –Proposed in [12], VADD uses predictable vehicle mobility constraints of traffic patterns and road layouts in order to choose the next route. Along with this, [12] also proposed several other VADD protocols have been proposed in order to identify the best route for reducing data-delivery delay.
MaxProp – prioritizes packet delivery likelihood and manages storage constraints by discard-ing less probable packets [13]. Authors proposed using VDTN architecture to supply internet access and other services to remote communities. The authors introduce a metric they call “trend of delivery”.
Greedy Perimeter Stateless Routing – (GPSR) is a stateless approach that uses location information to make forwarding decisions, reducing overhead but requiring accurate positioning data [10]. GPSR makes forwarding decisions based on node geography. Initially, GPSR uses a greedy algorithm to forward packets to the neighbor closest to the destination. If greedy forwarding fails if it is not possible to locate a neighbour node that is closer to the packet’s destination than itself. This may happen if the node is geographically closer to the destination than an immediate neighbour. If forwarding fails, the protocol routes packets around the perimeter of the failure area using a right-hand rule until greedy forwarding can resume. GPSR is usually applied to ad-hoc networks [1].
GeoDTN+Nav – proposed in [16] uses direct routing to location when it is available. Oth- erwise, a store-carry-forward approach is employed until a forwarding opportunity arises. It accomplishes this by leveraging GPS data and historic traffic data. By switching between geographic routing and DTN strategies, GeoDTN+Nav is able to retain best-case efficiency in immediate routing scenarios. The purported use-case is urban and highway scenarios.
GeoDTN-NDN – proposed in [17], Geographic data, DTN and is a data retrieval protocol. Data is requested by name across an ad-hoc network and returned using a reverse path.
GeoSpray – [14] uses geographic data to inform routing decisions and store-carry-forward to opportunistically bundle and forward messages. It sends multiple copies that intermediate nodes can clear in order to avoid node spam.
Fastest-ferry routing in DTN-enabled VANET – In [15] FFRDV collects and relays data between disconnected ends and considers the velocity of a given vehicle relative to the final destination in order to improve route times with a purported benefit to emergency services.
Efficient Deterministic Bundle Relaying Scheme with Bulk Bundle Release – Authors of [20] propose Efficient Deterministic Bundle Relaying Scheme with Bulk Bundle Release (DBRS- BBR), an improved data transmission approach for VDTNs using the Railway Transport System to address the limitations posed by selfish nodes in traditional schemes. Stationary nodes called Track Side Units with large memory and mobile nodes (trains) with significant buffer capacity are used for message relaying. The proposed Efficient Deterministic Bundle Relaying Scheme with Bulk Bundle Release leverages these nodes to enhance message storage and transfer. A mathematical queuing model and deterministic scheduling are employed to validate this approach. Performance measures such as Mean Queueing Delay, Mean Transit Delay, and Mean End-To-End Delay indicate that DBRS-BBR outperforms the existing Probabilistic Bundle Relaying Scheme.
Routing using Ant Colony Optimization in DTN – [18] proposes a bio-inspired algorithm modeled after the foraging behavior of ants, which can be effectively applied to routing in DTNs. In this approach, nodes in the network leave virtual pheromones on the paths they traverse, similar to ants leaving pheromone trails. These virtual pheromones help guide subsequent data packets along the most promising paths. Over time, pheromone intensity decreases to prevent outdated information from dominating routing decisions and to adapt to changes in network topology. Nodes make forwarding decisions based on the intensity of pheromone trails, with higher pheromone concentrations indicating more reliable and frequently used paths. Heuristic information, such as distance to the destination, node mobility patterns, and encounter histories, is also considered to enhance decision-making. ACO balances exploration and exploitation by occasionally forwarding packets along less-pheromone-rich paths to discover new and potentially better routes, while most packets follow established pheromone trails for reliable and efficient data delivery. Pheromone levels are dynamically updated based on successful deliveries and network conditions, allowing the algorithm to learn and adapt over time.
ACO-based routing can scale well to large and dynamic network environments[18]. It is robust in the face of network topology and node mobility changes due to its adaptive nature, and it finds efficient paths that balance delivery probability and resource usage. However, implementing ACO can be computationally intensive, requiring careful management of pheromone information. In highly dynamic networks, the time required for pheromone information to stabilize can introduce latency, and maintaining and updating pheromone trails across nodes can introduce additional overhead. When compared with Epidemic Routing and PRoPHET, RACOD routing offers higher delivery probability due to the adaptive nature of pheromone trails and heuristic information, lower overhead compared to flooding-based approaches, and improved latency by finding more efficient paths[18].
SecureSIS-DTN – [19] proposes a Service Priority-based Incentive Scheme (SIS), using service priority as an incentive instead of credits. In SIS, nodes that relay more bundles gain higher service priority, improving their bundle delivery ratio. To safeguard against potential attacks on SIS, authors introduce three security measures: signature chains, cooperation fre- quency statistics, and combination clearance. Evaluating SIS using an opportunistic network environment simulator. Results showed that SIS enhances the bundle delivery ratio for honest nodes and effectively curbs selfish behaviors compared to credit-based schemes.
Beyond The Scope – Other areas of interest involve the following. [21] proposed a novel solution involving stratospheric drones to improve data transfer performance of VANETs. [11] identified that although DTNs outperform other VANET routing protocols under conditions of high node density, worst-case performance was only assessed sporadically amongst the literature. Routing involving social metrics is an avenue of future research that fell outside of the scope of this work.

IV. Conclusion

VANETs have shown the capacity to play a central role in critical Smart City (SC) and Intelligent Transport Systems (ITS). My discussion covered various geographic routing protocols in order to expose problems sought solutions. After which, VANET geographic routing research is likely to be a place of increased focus owing in large part to the heuristic nature of geographic route solutions as well as the enthusiasm surrounding Intelligent Transport Systems and Smart City.

References

[1] S. Sharma, A. Kaul, S. Ahmed, and S. Sharma, “A detailed tutorial survey on vanets: Emerging architectures, applications, security issues, and solutions,” International Journal of Communication Systems, vol. 34, no. 14, e4905, 2021.

[2] A. Hamza-Cherif, K. Boussetta, G. Diaz, and F. Lahfa, “Performance evaluation and comparative study of main VDTN routing protocols under small- and large-scale sce- narios,” Ad Hoc Networks, vol. 81, pp. 122–142, Dec. 2018, ISSN: 1570-8705. DOI: 10.1016/j.adhoc.2018.07.008.

[3] RFC 4838: Delay-Tolerant Networking Architecture, [Online; accessed 24. May. 2024], Jun. 2024. [Online]. Available: https : / / datatracker . ietf . org / doc / html / rfc4838.

[4] RFC 5050: Bundle Protocol Specification, [Online; accessed 24. May. 2024], Jun. 2024. [Online]. Available: https://datatracker.ietf.org/doc/html/rfc5050.

[5] M. S. Hossen, “DTN Routing Protocols on Two Distinct Geographical Regions in an Opportunistic Network: An Analysis,” Wireless Pers. Commun., vol. 108, no. 2, pp. 839– 851, Sep. 2019, ISSN: 1572-834X. DOI: 10.1007/s11277-019-06431-w.

[6] A. M. Abdalla and S. H. Salamah, “Performance Comparison between Delay-Tolerant and Non-Delay-Tolerant Position-Based Routing Protocols in VANETs,” International Journal of Communications, Network and System Sciences, vol. 15, no. 1, pp. 1–14, Jan. 2022. DOI: 10.4236/ijcns.2022.151001.

[7] S. Joerer, C. Sommer, and F. Dressler, “Toward reproducibility and comparability of ivc simulation studies: A literature survey,” IEEE Communications Magazine, vol. 50, no. 10, pp. 82–88, Oct. 2012, ISSN: 1558-1896. DOI: 10.1109/MCOM.2012.6316780.

[8] S. Martínez Tornell, “Delay Tolerant Networks for Efficient Information Harvesting and Distribution in Intelligent Transportation Systems,” Universitat Politècnica de València, Nov. 2020. DOI: 10.4995/Thesis/10251/68486.

[9] L. Rivoirard, M. Wahl, P. Sondi, M. Berbineau, and D. Gruyer, “Performance evaluation of AODV, DSR, GRP and OLSR for VANET with real-world trajectories,” in ITST 2017 - 15th International Conference on ITS Telecommunications, ITST 2017 - 15th International Conference on ITS Telecommunications, Warsaw, POLOGNE, 29-/05/2017 - 31/05/2017, Warsaw, Poland, May 2017, 7p. [Online]. Available: https://hal.science/hal-01556408.

[10] B. Karp and H. Kung, “Gpsr: Greedy perimeter stateless routing for wireless networks,” English, Cited by: 6159; Conference name: 6th Annual International Conference on Mobile Computing and Networking (MOBICOM 2000); Conference date: 6 August 2000 through 11 August 2000; Conference code: 57709, ACM, 2000, pp. 243–254.

[11] A. Torres Amaya, M. S. Fonseca, A. Pohl, and R. Lüders, “Performance assessment of dtn and vanet protocols for transmitting periodic warning messages in high vehicular density networks,” Journal of Communication and Information Systems, vol. 37, no. 1, pp. 91–103, Jun. 2022. DOI: 10.14209/jcis.2022.10.

[12] J. Zhao and G. Cao, “Vadd: Vehicle-assisted data delivery in vehicular ad hoc networks,” IEEE Transactions on Vehicular Technology, vol. 57, no. 3, pp. 1910–1922, May 2008, ISSN: 1939-9359. DOI: 10.1109/TVT.2007.901869.

[13] A. Vieira, J. Filho, J. Jr, and A. Patel, “Vdtn-tod: Routing protocol vanet/dtn based on trend of delivery,” Advanced International Conference on Telecommunications, AICT, vol. 2013, pp. 135–141, Jan. 2013.

[14] V. N. Soares, J. J. Rodrigues, and F. Farahmand, “Geospray: A geographic routing protocol for vehicular delay-tolerant networks,” Information Fusion, vol. 15, pp. 102–113, 2014, Special Issue: Resource Constrained Networks, ISSN: 1566-2535. DOI: https: //doi.org/10.1016/j.inffus.2011.11.003.

[15] D. Yu and Y. -B. Ko, “Ffrdv: Fastest-ferry routing in dtn-enabled vehicular ad hoc net- works,” vol. 02, Mar. 2009, pp. 1410–1414.

[16] P.-C. Cheng, K. C. Lee, M. Gerla, and J. Härri, “GeoDTN+Nav: Geographic DTN Routing with Navigator Prediction for Urban Vehicular Environments,” Mobile Netw. Appl., vol. 15, no. 1, pp. 61–82, 2010, ISSN: 1572-8153. DOI: 10.1007/s11036-009-0181-6.

[17] B. Aldahlan and Z. Fei, “A geographic routing strategy with dtn support for vehicular named data networking,” in 2019 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC), Aug. 2019, pp. 361–366. DOI: 10.1109/CSE/EUC.2019. 00075.

[18] N. Singh and A. Singh, “RACOD: Routing Using Ant Colony Optimization in DTN,” International Journal of Sensors, Wireless Communications and Control, vol. 10, no. 2, pp. 262–275, 2024. DOI: 10.2174/2210327909666190404141124.

[19] Y. Xie and Y. Zhang, “A secure, service priority-based incentive scheme for delay tolerant networks,” Secur. Commun. Netw., vol. 9, no. 1, pp. 5–18, Jan. 2016, ISSN: 1939-0114. DOI: 10.1002/sec.1372.

[20] P. Kumar Tiwari, S. Prakash, A. Tripathi, et al., “A novel model for vehicular delay tolerant networks using deterministic bundle relaying scheme,” IEEE Access, vol. 12, pp. 68 916–68 925, 2024, ISSN: 2169-3536. DOI: 10.1109/ACCESS.2024.3400408.

[21] V. Kharchenko, A. Grekhov, and V. Kondratiuk, “Traffic modelling in stratospheric drone- assisted VANET,” Peer-to-Peer Networking and Applications, pp. 1–11, Feb. 2024, ISSN: 1936-6450. DOI: 10.1007/s12083-024-01631-z.