# V-GRADIENT: A Density-Aware Geocast Routing Protocol for Vehicular Delay-Tolerant Networks

Henrique Nascimento, Paulo Rogério Pereira

► To cite this version:

Henrique Nascimento, Paulo Rogério Pereira. V-GRADIENT: A Density-Aware Geocast Routing Protocol for Vehicular Delay-Tolerant Networks. 10th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), May 2019, Costa de Caparica, Portugal. pp.296-304, 10.1007/978-3-030-17771-3_26 . hal-02295228

HAL Id: hal-02295228

https://inria.hal.science/hal-02295228v1

Submitted on 24 Sep 2019

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# V-GRADIENT: A Density-Aware Geocast Routing Protocol for Vehicular Delay-Tolerant Networks

Henrique Nascimento¹, Paulo Rogério Pereira¹,

¹ INESC-ID, Instituto Superior Técnico, Universidade de Lisboa, Portugal
henrique.nascimento@tecnico.ulisboa.pt, prbp@inesc.pt

**Abstract.** Vehicular Delay-Tolerant Networks (VDTNs) are networks of vehicles that communicate wirelessly, where there are no permanent end-to-end connections. VDTNs have a highly variable topology, with frequent partitions, and possibly low node density. Thus, delay-tolerant routing adopts a store-carry-and-forward message transfer paradigm, where messages have a useful Time To Live (TTL) and are stored until a good contact opportunity arises. Multiple message replicas can be generated to improve delivery probability at the cost of increasing network congestion. In this paper, we propose the V-GRADIENT geocast routing protocol that monitors node density and buffer occupancy, to adapt dynamically the forwarding techniques used to disseminate messages within the geographic region of interest. Simulation results show that V-GRADIENT is capable of controlling network congestion and efficiently deliver messages resulting in better delivery ratios (13-99%) and lower latencies when compared with existing protocols.

**Keywords:** wireless communications, geocast routing, vehicular delay-tolerant networks.

## 1 Introduction

Delay Tolerant Networks (DTNs) are characterized by long or variable delays, intermittent connectivity, asymmetric data rates and high error rates. In this type of networks, routing strategies rely on the store-carry-and-forward paradigm, i.e, on the dissemination of messages to intermediate nodes that can retain them, transport them and deliver them either to the final destination or to other intermediate nodes. The complexity of the routing decisions is, for that reason, closely related with the selection of a proper message replication mechanism.

The geocast concept refers to a delivery scheme that filters the eligibility of the network's target nodes using their location as a criterion. With this in mind, the diversity of geocast environments encompassed by DTNs suggests the demarcation of the strategies according to generic properties such as the definition of regions of interest or the replication mechanisms applied.

Moreover, the coupling between the advances in wireless communications technologies and the car industry makes Vehicle-to-Vehicle connectivity an enabler for a broad range of applications that can be grouped into two categories: safety-related
and commercial-related. Therefore, in light of the advances mentioned, this communication paradigm has received a lot of research attention and has motivated the design of routing strategies in Vehicular Delay Tolerant Networks (VDTNs) that can properly handle the following challenges of such distinguishable environment.

In this sense, the design of strategies in VDTNs that can efficiently deliver messages to a group of recipients that would particularly benefit from the reception of such messages has become a widespread topic of discussion. To that extent, the implementation of algorithms that exploit information from the vehicles' navigation system to route messages within specific Regions of Interest (ROIs) motivates the development of the V-GRADIENT protocol.

## 2 Contribution to Industrial and Service Systems

The proposed V-GRADIENT geocast routing protocol is the basis for a message dissemination service within a ROI in vehicular highly dynamic or sparse networks. Applications include Vehicle-to-Vehicle (V2V) commercial of safety-related message dissemination. Examples are disseminating fuel prices, current weather or incident warnings. The protocol provides the following contributions: mechanisms to monitor node density and node's buffer occupancy; mechanisms to control message replication avoiding network congestion and buffer exhaustion; efficient message delivery within the ROI.

## 3 State of the Art

### 3.1 Unicast Routing

As described in [1], the Direct Delivery protocol is the simplest way to conceive a unicast delivery scheme. The node that carries the message forwards it if and only if it establishes a direct contact opportunity with the target node.

The Spray and Wait protocol [2], in its turn, is based on the dissemination of a limited set of replicas of a given message to distinct contacted nodes during a first phase called spray phase. Afterwards, during the wait phase, relay nodes assume the responsibility of delivering the message to the final recipient directly. However, with regard to the spray phase, several heuristics can be envisioned to distribute properly the messages.

Finally, the Epidemic [3] protocol is classified as a flooding-based scheme, since the idea behind it is based on the provision of unlimited message replication throughout the network by exchanging all possible messages whenever contact opportunities arise.
## 3.2 Geocast Routing

On the one hand, protocols such as the GSAF [4] and the Geoopp [5] focus on distributing messages by all nodes located inside a region set remotely, relatively to the position of the nodes that generate such messages. This implies, however, that these algorithms break down the routing process into the two following phases: (1) forwarding (and carrying) the messages to the destination region; (2) delivering the message to all nodes inside the ROI. While, regarding the latter phase, both protocols mentioned follow an epidemic-based behaviour, their strategy differs with respect to the first phase. For instance, when using the GSAF protocol a spraying procedure is applied in a first phase. Messages are assigned a predetermined number of tickets T that denote the number of times a given message can be forwarded to encountered nodes outside the destination region. Thus, each time a message is replicated, the T field is sequentially decreased on both messages until T equals zero.

On the other hand, geocast protocols can be applied to distribute content in ROIs whose center is defined by the position of the nodes responsible for creating the respective messages at the generation instant. In this sense, the authors of the Floating Content algorithm [6] include in the messages' headers not only the center coordinates and radius of the circularly shaped ROI but also an additional radius parameter to determine the extension of a buffer zone. The buffer zone is defined as an extension of the ROI where carrier nodes may keep the messages storage beyond the boundaries of the ROI.

# 4 Geocast Strategies Comparison

This work focuses on distributing messages, during a specified Time To Live (TTL), by all nodes that come across an invariant circularly shaped ROI defined around the node which creates the messages. Moreover, the development of the intended message dissemination algorithm is performed by grasping which features of the considered schemes yield better results under a broad variety of simulations.

In this study, in order to drive such conclusions, the following routing strategies are taken into account, which result from the extension of the definitions regarding the aforementioned unicast routing protocols to a geocast context: Multiple Copy GeoDirectDelivery (MC-GeoDirectDelivery), GeoSpray-and-Wait (GeoS&W), GeoEpidemic and GeoEpidemic Constrained.

Firstly, when using the MC-GeoDirectDelivery protocol, on the one hand, messages are delivered to and kept by nodes residing inside the respective ROI at the delivery instant. On the other hand, messages are retained when nodes leave the ROI, as they may return to the ROI in the future. Because messages are only dropped when their TTL expires or the nodes' buffers are filled up, all nodes that receive a message also become responsible to deliver it to the remaining recipients, enabling the presence of multiple copies of the same message in the network.

Secondly, the GeoS&W scheme couples the principles of the Spray and Wait and the GSAF protocols. In this sense, during the spray phase, messages are replicated, even when nodes are located outside the ROI, using the spraying heuristic adopted by the
GSAF protocol. Regarding the wait phase, the GeoS&W behaves as the MC-GeoDirectDelivery protocol.

The Epidemic Protocol nature may assist message distribution in a geocast context as it already distributes an unbounded number of copies of the same messages by multiple receivers. However, to distinguish the protocol's operation in unicast scenarios from its operation in a geocast routing paradigm, this protocol will be referred as the GeoEpidemic protocol throughout the article. Likewise, the GeoEpidemic Constrained scheme follows the Epidemic protocol's principles as well. However, in this case, the routing scheme under consideration constrains the dissemination of messages within the boundaries of the ROI, since messages are dropped as soon as the nodes carrying them leave this region.

Additionally, in this line of reasoning, it is also crucial to make explicit the following performance assessment metrics utilized: delivery ratio and delivery latency. The delivery ratio is computed using the formulation developed in [4]. By monitoring the recipients that reside inside a given message's ROI during its TTL, it is possible to compute a ratio between the number of successful receivers and total number of nodes belonging to the list of recipients. Obviously, this ratio only translates itself into a per message result. For that matter, to obtain an overall delivery ratio estimation, the per message metric is extended to all created messages through an average operation. Latency is also monitored, in a first instance, taking into account a single message. However, in this case, the per-message metric is computed by summing the amount of time it takes for the message under consideration to reach each one of its successful receivers and, then, by dividing this outcome by the same number of recipients.

# 5 V-GRADIENT Design

The major points of improvement attained by benchmarking the different geocast strategies relate not only with a moderated replication process applied outside the messages' regions of interest but also with a dropping policy that can dynamically estimate if it is beneficial to keep messages being carried by nodes located outside the ROI. With this in mind, on the one hand, with regard to the replication process, the V-GRADIENT algorithm incorporates the principles of the Spray-and-Wait protocol [2] in a geocast context and, during the spray phase, the methodology adopted by the GSAF protocol [4]. On the other hand, the deployed strategy follows the idea behind the Floating Content Algorithm [6], i.e., defines a buffer zone whose range varies according to the network conditions.

For such purposes, to select dynamically the buffer zone range, the V-GRADIENT algorithm takes advantage of estimations of the network density level and of the buffer occupation level, updated periodically. Because in this study it is assumed that nodes do not have access to any knowledge oracles, vehicles rely only on information exchanged during contact opportunities to perceive the surrounding network conditions and, for that reason, both awareness metrics are kept as dictionaries in the nodes' buffers in a decentralized manner. Moreover, the mathematical formulation used to compute both metrics follow an Exponentially Weighted Moving Average (EWMA). For the
density level metric $\rho_t$, the EWMA is performed every 30 seconds taking into account the number of distinct contacts $n_c$ established, as shown in Eq. 1. $\alpha$ was set to 0.25.

$$ \rho_t = \alpha \cdot n_c + (1-\alpha) \cdot \rho_{t-1}. \qquad (1) $$

The buffer occupation metric $\beta_t$ is determined by averaging the fractions of the buffer occupancy $\beta_{level}$, varying from zero to one, retrieved from neighbouring nodes in 30 seconds intervals with an EWMA, as shown in Eq. 2, where $\gamma$ was set to 0.7.

$$ \beta_t = \gamma \frac{\sum^{n_c} \beta_{level}}{n_c} + (1 - \gamma) \beta_{t-1}. \qquad (2) $$

In order to carry out a reliable implementation of the mechanism responsible for adjusting the extent of the buffer zone, a wide variety of simulations were executed using the ONE simulator [7] under different density scenarios, considering ROIs with different radius values, and in environments that led to serious buffer congestion issues, as shown in Table 1. Accordingly, in each simulation an additional dropping policy was included that periodically removed messages from storage if the nodes were located outside of the buffer zone range, defined as the product between the ROI radius, $R_{ROI}$, value and a threshold $R_{+ratio}$.

<table><caption>**Table 1.** Assigned parameters during the simulation procedure.</caption><tr><td>Map</td><td>Downtown part of the city of Helsinki [4500m x 3400m]</td></tr><tr><td>Simulation time</td><td>12 hours</td></tr><tr><td>Movement model</td><td>Shortest Path Map-Based Movement</td></tr><tr><td>Type of nodes</td><td>Vehicles (cars)</td></tr><tr><td>Nodes' speed interval</td><td>10-50 km/h</td></tr><tr><td>Nodes' buffer size</td><td>5 MB</td></tr><tr><td>Nodes' wait time</td><td>5-30 seconds</td></tr><tr><td>Message size interval</td><td>500 kB-1 MB</td></tr><tr><td>Message generation interval</td><td>30-90 seconds</td></tr><tr><td>Interfaces' data rate</td><td>250 kbps</td></tr><tr><td>Interfaces' transmission range</td><td>50 meters</td></tr><tr><td>Initial Number of Copy Tickets</td><td>3</td></tr><tr><td>Message's TTL</td><td>150 minutes</td></tr><tr><td>Number of nodes</td><td>[50;100;200;400] nodes</td></tr><tr><td>ROI Radius</td><td>[250;500;750;1000] meters</td></tr><tr><td>R<sub>+ratio</sub></td><td>Vector of 100 evenly spaced points between 1 and 10</td></tr></table>

Furthermore, to exhibit the impact of the network density conditions and the ROIs' radius values on the additional dropping policy formulation, Table 2 includes the optimal $R_{+ratio}$ values, bearing in mind the delivery ratio results obtained. It can also be seen in the same table that, for a fixed number of nodes deployed in the network, the optimal $R_{+ratio}$ expression can be modeled by an equation obtained through a power regression. The profile of such equations, since it also follows a trend depending on the number of nodes and consequently on the density level, also suggests a mathematical formulation of a variable threshold value associated with the extension of the buffer zone as shown in Eq. 3.

$$ R_{+ratio}(R_{ROI}, \rho_t) = g(\rho_t) \cdot R_{ROI}^{h(\rho_t)}. \qquad (3) $$
With respect to the formulation of the $g(\rho_t)$ and the $h(\rho_t)$ expressions, by selecting their corresponding target parameters presented in Table 2, it can be observed, as depicted in Fig. 1, that both describe a well modeled decay relatively to the average density level $\rho_{avg}$ measured in simulations deploying a different number of nodes.

<table><caption>**Table 2.** Optimal $R_{+ratio}$ values obtained for simulations considering different density conditions and distinct radius values defining the ROI.</caption><thead><tr><th></th><th>50 Nodes<br>ρ<sub>avg</sub> = 0.3952</th><th>100 Nodes<br>ρ<sub>avg</sub> = 0.8329</th><th>200 Nodes<br>ρ<sub>avg</sub> = 1.6470</th><th>400 Nodes<br>ρ<sub>avg</sub> = 3.2884</th></tr></thead><tbody><tr><td>R<sub>ROI</sub> = 200 m</td><td>9.5</td><td>8.6</td><td>8.1</td><td>7.9</td></tr><tr><td>R<sub>ROI</sub> = 400 m</td><td>3.4</td><td>3</td><td>2.8</td><td>2.5</td></tr><tr><td>R<sub>ROI</sub> = 600 m</td><td>2</td><td>1.7</td><td>1.5</td><td>1.4</td></tr><tr><td>R<sub>ROI</sub> = 800 m</td><td>1.5</td><td>1.2</td><td>1.1</td><td>1.1</td></tr><tr><td>R<sub>ROI</sub> = 1000 m</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>R̂<sub>+ratio</sub></td><td>12872 · R<sub>ROI</sub><sup>-1.366</sup></td><td>10970 · R<sub>ROI</sub><sup>-1.360</sup></td><td>9460.3 · R<sub>ROI</sub><sup>-1.348</sup></td><td>7649.4 · R<sub>ROI</sub><sup>-1.320</sup></td></tr><tr><td>R<sup>2</sup> score</td><td>0.9964</td><td>0.9932</td><td>0.9827</td><td>0.9706</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Regression-based model for the $g(\rho_t)$ and the $h(\rho_t)$ expressions.</figcaption></figure>

In this sense, in scenarios characterized by extreme buffer congestion issues, the V-GRADIENT algorithm allows a dynamic adjustment of the range of the buffer zone for all messages carried by a particular node according to the estimated threshold expression presented in Eq. 4, as a result from the best fit from Fig. 1. Additionally, the buffer occupation level metric plays an important role on detecting the occurrence of congestion, providing nimbleness to the dropping policy operation. If we let ourselves picture a scenario where only a few messages are generated per hour, it can be concluded that, because no congestion issues arise, the drop policy should be less restrictive. For this reason, a logistic function $f(\beta_t)$ responsible for regulating the stringency of the policy, with $\beta_t = 0.5$ defining the sigmoid's midpoint, is included in the final definition of $R_{+ratio}$.

$$R_{+ratio}(R_{ROI}, \rho_t, \beta_t) = \frac{1}{f(\beta_t)} 10413 \cdot \rho_t^{-0.243} \cdot R_{ROI}^{1.3731-0.016 \cdot \rho_t} \quad (4)$$
# 6 Evaluation and Results

In this section, the results regarding the different strategies described in Section 3 are compared against the ones concerning the V-GRADIENT algorithm, considering a simulation scenario following most of the parameters' configuration presented in Table 1. However, in this case, different message generators are deployed in each simulation simultaneously. Additionally, the nodes' buffer size is doubled to 10 MB and four different seed values are used for the movement models' pseudo random number generator to reinforce the statistical significance of the results obtained. The corresponding 95% confidence intervals are presented in the following graphs.

Moreover, to assess the performance of the V-GRADIENT strategy under different density conditions, results are presented in parallel according to the number of nodes deployed in the network. Regarding the delivery ratio assessment, as depicted in Fig. 2, the V-GRADIENT algorithm yields better results than the remaining protocols. In fact, for the simulations executed with 150 nodes deployed, the V-GRADIENT algorithm shows a 13% increase on the delivery rate relatively to the GeoS&W protocol, 15% relative to the MC-GeoDirectDelivery, 39% relative to the GeoEpidemic Constrained and 99% relative to the GeoEpidemic. Furthermore, the remaining protocols' outcome also reinforce the choices related with the V-GRADIENT design. For instance, the pronounced upward trend shown by the GeoEpidemic Constrained protocol's results, as the density level increases, validates the exercise of a dropping policy that renders itself stricter in high density conditions.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Delivery ratio and delivery latency as a function of node density and protocol.</figcaption></figure>

When analyzing latency results, one should also bear in mind the delivery ratio results to draw respectable conclusions, since only the delivered messages are taken into account when it comes to measuring latency. Accordingly, in spite of the GeoEpidemic Constrained achieving better results, it can be assumed that, because messages are deleted from the nodes' buffers as soon the carrier nodes leave the ROI, they only live a fraction of their total assigned TTL, which compromises the delivery ratio efficiency. In this sense, the V-GRADIENT provides a moderate and adequate
solution, putting a limit on latency, by means of a dynamic dropping policy, while still
achieving good performance regarding the delivery ratio: 20% better than GeoS&W.

7 Conclusions and Future Work

We proposed the new V-GRADIENT geocast routing protocol for VDTNs that monitors node density and buffer occupation to disseminate efficiently messages within a ROI centered in the source node. The protocol achieves a better delivery ratio (13-99% with 150 nodes) and lower latency than the existing protocols by controlling network congestion. As future work, we intend to extend the operation of the V-GRADIENT protocol to an environment encompassing distinct geocast groups associated with several types of messages' applications, taking into account the penetration rate of such groups in the network. We also intend to test other scenarios and evaluate the protocol overhead.

**Acknowledgments.** This work was supported by national funds through Fundação para a Ciência e a Tecnologia (FCT) with reference UID/CEC/50021/2019.

References

1. Spyropoulos, T., Psounis, K., Raghavendra, C.S.: Single-copy routing in intermittently connected mobile networks. In: First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), pp. 235–244. IEEE (Oct 2004)

2. Spyropoulos, T., Psounis, K., Raghavendra, C.S.: Spray and wait: An efficient routing scheme for intermittently connected mobile networks. In: ACM SIGCOMM Workshop on Delay-tolerant Networking (WDTN), pp. 252–259. ACM, New York, NY, USA (2005)

3. Vahdat, A., Becker, D.: Epidemic Routing for Partially-Connected Ad Hoc Networks. Tech. rep., CS-200006. Department of Computer Science, Duke University, Durham, NC (2000)

4. Rajaei, A., Chalmers, D., Wakeman, I., Parisis, G.: GSAF: Efficient and flexible geocasting for opportunistic networks. In: IEEE 17th International Symposium on A World of Wireless, Mobile and Multimedia Networks (WoWMoM), pp. 1–9. IEEE (June 2016)

5. Lu, S., Liu, Y.: Geoopp: Geocasting for opportunistic networks. In: IEEE Wireless Communications and Networking Conference (WCNC), pp. 2582–2587. IEEE (2014)

6. Ott, J., Hyytiä, E., Lassila, P.E., Vaegs, T., Kangasharju, J.: Floating content: Information sharing in urban areas. In: IEEE International Conference on Pervasive Computing and Communications (PerCom), pp. 136–146. IEEE (2011)

7. Keränen, A., Ott, J., Kärkkäinen, T.: The ONE Simulator for DTN Protocol Evaluation. In: SIMUTools ’09: Proceedings of the 2nd International Conference on Simulation Tools and Techniques. ICST, New York, NY, USA (2009)