# Temporal complex networks modeling applied to vehicular ad-hoc networks

Fillipe Santos<EMAIL_ADDRESS>Andre L. L. Aquino
<EMAIL_ADDRESS>Edmundo R. M. Madeira<EMAIL_ADDRESS>Raquel S.
Cabral<EMAIL_ADDRESS>University of Campinas. Campinas, SP,
Brazil  Federal University of Alagoas - Campus Arapiraca. Arapiraca, AL,
Brazil  Federal University of Alagoas. Maceió, AL, Brazil

###### Abstract

VANETs solutions use aggregated graph representation to model the interaction
among the vehicles and different aggregated complex network measures to
quantify some topological characteristics. This modeling ignores the temporal
interactions between the cars, causing loss of information or unrealistic
behavior. This work proposes the use of both temporal graphs and temporal
measures to model VANETs applications. To verify the viability of this model,
we initially perform a comparative analysis between the temporal and
aggregated modeling considering five different real datasets. This analysis
shows that the aggregated model is inefficient in modeling the temporal
aspects of networks. After that, we perform a network evaluation through a
simulation by considering the impact of temporal modeling applied to the
deployment of RSUs. First, we compare a solution based on our temporal
modeling with a greedy algorithm based on an aggregated model to choose the
positions of RSUs. In a scenario with 70 RSUs, we have 77% and 65% of coverage
in the temporal and aggregated model (greedy algorithm), respectively. Second,
we evaluate the use of aggregated and temporal measures applied as features in
a genetic algorithm. The approach with temporal betweenness had the better
result with 90% of the coverage area against 61% of aggregated one applied to
the same scenario.

###### keywords:

VANETs, Complex Networks, Temporal Centrality Measures

##  1 Introduction

A Vehicular ad hoc network (VANET) [1] consists of groups of moving or
stationary vehicles connected by a wireless network. According to their
communication radius, the communication occurs among the cars or through a
fixed infrastructure along the roads. In both cases, the connection patterns
between their elements have a dynamic behavior with the insertion and removal
of links over time. It is usual to use a graph representation to model the
interaction among the vehicles and different complex network measures to
quantify some topological characteristics [2]. These measures represent a
mathematical and computational framework to understand better non-trivial
topological features, like the dynamics of growing a network over time, and to
enable the characterization, analysis, and modeling of the network topology
based on different features like connectivity centrality, cycles, and
distances.

Several VANETs applications and network infrastructure solutions use graph
modeling and its measures as a static representation called aggregated
modeling [3, 4, 5]. In this modeling, all quick contacts among the vehicles
are permanent connections. For example, consider that we observed three
vehicles $v_{1}$, $v_{2}$, and $v_{3}$ on a VANET for ten minutes at one-
minute intervals and obtained the following sequence of contacts between them:
i) $v_{1}$ with $v_{2}$ only during minute 1, ii) $v_{1}$ with $v_{3}$ between
minutes 2 and 5, and iii) $v_{2}$ with $v_{3}$ between minutes 6 and 10. In
this case, the aggregated modeling produces a complete graph among the three
vehicles, and, consequently, we calculate the aggregated measures directly
over this aggregated graph. This modeling ignores the temporal interactions
between the vehicles, causing loss of information or unrealistic behavior.

Some applications and infrastructure solutions adopt temporal modeling to
represent the graph and preserve the temporal characteristics [6]. In this
case, quick contacts among the vehicles generate connections in a time
interval $t$, getting different graphs. Considering the previous example with
three vehicles, the sequence of contacts in the temporal modeling produces
temporal graphs with three disjoint edges $(v_{1},v_{2})$ at minute 1,
$(v_{1},v_{3})$ during minutes 2 and 5 and $(v_{2},v_{3})$ during minutes 5
and 10. However, the solutions calculate the average aggregated measures for
all graphs in time interval t, losing global time information about the
network.

In this way, the novelty of our proposal is the use of temporal models in
conjunction with temporal measures to model and evaluate VANETs. To the best
of our knowledge, we are the only ones that use these measures in VANETs
scenarios. We use the temporal measures proposed by Kim et al. [7]: Degree,
Betweenness, and Closeness. These measures relate node’s position and its
ability to disseminate information efficiently in the network. In addition,
they preserve the temporal relationships of the network. We perform a
comparative analysis between the complete temporal (graph and measures) and
aggregated modeling based on these measures.

To quantify the impact of temporal modeling compared with the aggregated one,
we consider four static analyses: i. Quantification of the number of vertices
and edges; ii. Kolmogorov-Smirnov test (KS-test) [8]; iii. Hellinger distance
[9]; and iv. Visual scatter plot behavior. In all cases, we apply the temporal
model to follow real scenarios: Cologne dataset [10] representing the car
traffic in an urban area of Cologne, Germany; Motorway M40 [11] representing
part of the intermediate layer of the Madrid city; Autovía A6 [12]
representing the Motorway that connects the city of A Corunã to the city of
Madrid; Créteil 7am-9am and Creteil 5pm-7pm Lébre et al. [12] representing
Créteil, Val-de-Marne (94) in France. The results show that the aggregated
model is inefficient in modeling the network’s temporal aspects.

We also perform a network evaluation through a simulation by considering the
deployment of Road Side Units (RSU) application [13]. In this evaluation, we
use both temporal and aggregated models to extract the features used by each
algorithm evaluated and compare them using the temporal and aggregated
modeling. We use only the Cologne scenario to perform this evaluation because
it is a large-scale dataset that comprises more than 250.000 vehicle routes
with varied road traffic conditions. We first compare our strategy with a
greedy algorithm to choose the RSUs’ positions. This algorithm uses a contact
matrix $\mathcal{T}$ to perform the solution. Thus, we generate $\mathcal{T}$
based on aggregated and temporal graphs. In a scenario with 70 RSUs, we have
77% and 65% of coverage in the temporal and aggregated model, respectively.
After that, we compare aggregated modeling against the temporal ones as
features in the genetic algorithm proposed by Moura et al. [13]. This
algorithm considers a preprocessing based on different centrality measures.
Thus, we evaluate both aggregated and temporal measures in specifics
scenarios. The approach with temporal betweenness had the best result with 90%
of the coverage area against 61% of aggregated one applied to the same
scenario. The evaluation showed that the temporal model is adequate because it
truly captures the network behavior.

We organized the remainder of this paper as follows: Section 2 gives an
overview of the main related work. Section 3 describes the temporal VANETs
topology modeling. Section 4 shows the evaluations and experiments. Finally,
Section 5 presents the conclusion and future work.

##  2 Related Work

Researchers using a complex network framework in VANETS show the deficiency of
availability, connectivity, reliability, and navigability of these networks
and reveal the risks of relying on simplistic models for vehicular mobility.
These studies generally use models that do not consider the vehicular
networks’ temporal relationships, showing the need to use more realistic
models for these networks is necessary. Additionally, centrality measures are
crucial for understanding the structural properties of complex relational
networks and are also relevant for various spatial factors affecting human
life and behaviors in cities [14]. Other studies use the measures information
to improve the application infer, for instance, using clustering measure in
Quality of Service(QoS) or Security decision [15, 16]. These theoretical
analyses are helpful to understand the structural characteristics of these
networks.

As mentioned previously, several VANETs applications and network
infrastructure solutions use graph modeling and its measures to represent
their behavior or extract application features. In this way, some works model
the VANETs as an aggregated graph without considering any complex network
measures. Elaraby et al. [17] study the problem of estimating the probability
of connectivity in vehicular ad hoc networks (VANETs). They discuss the
Laplacian eigenvalue and Adjacency exponent approaches to model VANETs
connectivity analysis. Fiore et al. [18] provide helpful guidelines for
evaluating and predicting the performance of vehicular networks using an
aggregated graph. They analyzed a real-world GPS trajectory dataset in a
vehicle to vehicle networks. Feng et al. [19] and Chen et al. [20] empirically
investigate the evolution of spatial-temporal characteristics vehicular
environments using mobility data from Shanghai.

We also find additional works using combined aggregated graphs and aggregated
complex network measures to model and evaluate VANETs. Moura et al. [13] and
Wang et al. [21] present different strategies to the RSU problem based on
centrality measures. Naboulsi et al. [1] present a topology analysis of two
networks from Colony in Germany and Zurique in Switzerland. They show that
these networks are poorly connected and, with availability and reliability,
very weak. Youji et al. [22] use the average degree, clustering coefficient,
and global efficiency to analyze the topology and verify that the edge
perturbations have an immediate effect on the characteristics of the topology.
Loulloudes et al. [23] provide a “higher-order” knowledge in the time-evolving
dynamics of vehicular networks in large-scale urban environments through
complex network analysis. Fiore et al. [3] present an in-depth analysis of the
topological properties of a vehicular network, unveiling the physical reasons
behind the peculiar connectivity dynamics generated by some mobility models.
Crucitti et al. [14] compare samples of various world cities, presenting a
study of the centrality distributions over geographic networks of urban
streets with five measures: centrality, degree, closeness, betweenness,
straightness, and information.

On the other hand, different VANETs applications analyze the topology
characteristics of mobility from a temporal perspective using temporal graph
modeling with aggregated measures. Diniz et al. [4] use three approaches to
model the vehicular networks: instantaneous, aggregated, and time-varying
analysis to verify which method can achieve the highest reliability and
accuracy. They explore two real traces from Rome and San Francisco city and
discussed different aggregated metrics that can reveal the fundamental
properties of the network. They verify that instantaneous and time-varying
models have the same behavior for the aggregated measures evaluated. Qu et al.
[24] apply complex network theory to capture the dynamics of the VANET and
obtain the analytic definitions of the degree distribution (aggregated). Celes
et al. [25] present a comparison of graphs used in modeling mobility showing
the strengths and weaknesses of current approaches in the characterization and
analysis of vehicular network topology. Glacet et al. [5] show that storage
and transport mechanisms share the information efficiently. Several studies
explore the temporal aspects of VANETs, for instance, vehicle mobility [26,
27].

The only work that uses, discretely, temporal measures in a specific
application is the proposed by Qiao et al. [6]. They explore structural
features on a taxi dataset in Beijing with 2927 vehicles. They use a temporal
model based on the shortest time-ordered path to calculate efficiency and
closeness measures. They conclude that the results can help create protocols
and algorithms to achieve reliability and low latency of communications
networks. However, they do not present a complete analysis of the impact of
temporal modeling. Additionally, our work evaluates five different datasets
with distinct characteristics (speed, lane, or congestion levels), allowing us
to analyze different views of traffic conditions, and applies the temporal
measures in a well-established solution presenting its better performance.

Table 1 present a qualitative comparison of the literature review with our
proposal. It lists the manuscripts that consider graphs (aggregated and
temporal) and metrics of complex networks (aggregated and temporal) in their
applications, evaluations, or comparison. In Table, we list the real (R) and
synthetic (S) scenarios; aggregated (A) and temporal (T) graphs; degree (D),
closeness (C) and betweenness (B) aggregated measures; and degree (TD),
closeness (TC) and betweenness (TB) temporal measures.

Table 1: Qualitative comparison of presented works with our proposal.

Literature Scen. Graph Measures R S A T D C B TD TC TB Elaraby et al. [17] ✓ –
✓ – – – – – – – Fiore et al. [18] – ✓ ✓ – – – – – – – Feng et al. [19] – ✓ ✓ –
– – – – – – Chen et al. [20] – ✓ ✓ – – – – – – – Moura et al. [13] ✓ – ✓ – – –
✓ – – – Wang et al. [21] – ✓ ✓ – ✓ ✓ – – – – Naboulsi et al. [1] ✓ – ✓ – ✓ – ✓
– – – Youji et al. [22] – ✓ ✓ – ✓ – – – – – Loulloudes et al. [23] ✓ – ✓ – ✓ –
✓ – – – Fiore et al. [3] – ✓ ✓ – ✓ – – – – – Crucitti et al. [14] – ✓ ✓ – ✓ ✓
✓ – – – Diniz et al. [4] ✓ – ✓ ✓ ✓ ✓ ✓ – – – Qu et al. [24] ✓ – – ✓ ✓ – – – –
– Celes et al. [25] ✓ – ✓ ✓ ✓ ✓ – – – – Glacet et al. [5] – ✓ – ✓ ✓ – – – – –
Ho et al. [26] – ✓ – ✓ ✓ – – – – – Shioda et al. [27] – ✓ – ✓ ✓ – – – – – Qiao
et al. [6] ✓ – – ✓ – – – – ✓ – Present work ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

##  3 Temporal VANETs modeling

We are modeling the vehicular topology as a temporal graph and characterize it
with temporal centrality measures. The centrality measures are suitable to
relate the position of a node in the VANETs with its ability to disseminate
information efficiently. In our model, the vehicular network is a temporal,
undirected, and unweighted graph. The temporal characteristic defines that the
vehicular network is alive from the start time $t_{initial}=1$ until the end
time $t_{final}=T$. Let $\mathcal{G}=(V,\mathcal{E})$ be a series of static
graphs ${G^{1},G^{2},\ldots,G^{T}}$; $V=\\{v_{1},v_{2},\ldots,v_{M}\\}$ is the
set of vehicles; and $\mathcal{E}=\\{E^{1},E^{2},\ldots,E^{T}\\}$ is the set
of disjoint subsets $E^{t}=\\{e^{t}_{1},e^{t}_{2},\ldots,e^{t}_{N}\\}$. Each
$E^{t}$ is the set of edges in $G^{t}$, with $t\in{[1,T]}$; and
$e_{a}^{t}=(v_{i},v_{j})$ is a temporal edge. The $e_{a}^{t}=(v_{i},v_{j})$
exists, if we have a path between $v_{i}$ and $v_{j}$ in the instant $t$, thus
edges are added and/or removed over time [7]. The size of $\mathcal{E}$, or
the number of temporal edges, is $|\mathcal{E}|=\sum_{i=1}^{T}|E^{i}|$. Based
on this description, an aggregated graph $G=(V,\mathbf{E})$ is the composition
$G^{1}\cup G^{2}\cup\ldots\cup G^{T}$ of static ones [7], i.e.,
$V=\\{v_{1},v_{2},\ldots,v_{M}\\}$ is the set of vehicles; and
$\mathbf{E}=\\{E^{1}\cup E^{2}\cup\ldots\cup E^{T}\\}$ is the set of
aggregated edges. Figure 1 illustrates an aggregated graph and the statics
used to compose the temporal ($\mathcal{G}$).

Figure 1: Aggregate Graph $G$ obtained from the graphs $G^{1}$, $G^{2}$, and
$G^{3}$ of $\mathcal{G}$ with time interval $[1,3]$.

Over $\mathcal{G}$, we apply different temporal measures (degree, closeness,
and betweenness). In all definitions of temporal measures, we always consider
a generic time interval $[t_{x},t_{y}]$, and we use the aggregated measures as
reference [28].

Temporal degree centrality is the number of edges incident to the vertex $v$
in the time interval $[t_{x},t_{y}]$, defined by [7]

$\displaystyle\kappa(v)^{[t_{x},t_{y}]}$ $\displaystyle=$
$\displaystyle\sum_{i=t_{x}}^{t_{y}}\kappa(v)^{i}.$ (1)

Figure 2 shows the edges considered to calculate the temporal degree the
centrality of vertex $v_{1}$ in temporal graph $\mathcal{G}$ in the time
interval $[1,3]$, in this case $\kappa(A)^{[1,3]}=5$.

Figure 2: Temporal edges to calculate the degree of vertex $v_{1}$ in temporal
graphs in the interval time $[1,3]$.

Temporal closeness centrality is a way of detecting nodes that can spread
information efficiently through a graph and quantify its average distance to
all other nodes. Nodes with a high closeness score have the shortest distances
to all other nodes. Kim et al. [7] defined as:

$\displaystyle C(v)^{[t_{x},t_{y}]}$ $\displaystyle=$
$\displaystyle\sum_{i=t_{x}}^{t_{y}}\sum_{u\in
V}\frac{1}{l(v,u)^{[i,t_{y}]}},$ (2)

where $l(u,v)^{[i,t_{y}]}$ is a temporal shortest path between $u,v\in V,$
i.e., is a sequence of temporal edges which connect $u$ and $v$ in the time
interval $[t_{x},t_{y}]$ such that no shorter path exists.

If there is not temporal path from $v$ to $u$ on a time interval $[t,j]$, we
consider $l(v,u)^{[i,t_{y}]}=\infty$ and we assume $1/\infty=0$. The
normalization factor is $(|V|-1)\cdot m$, where $m$ is the number of time
interval, so $m=3$.

Figure 3 shows the edges considered to calculate closeness of vertex $v_{4}$.
To calculate $C(v_{4})^{[1,3]}$ we consider the intervals $[1,3],[2,3]$ and
$[3,3]$. In the interval $[1,3]$ the minimum paths are $l(v_{4},v_{1})=2$,
$l(v_{4},v_{2})=3$, $l(v_{4},v_{3})=1$ and $l(v_{4},v_{5})=4$, in interval
$[2,3]$ node $v_{4}$ is disconnected so we have a loop at vertex $v_{4}$ and
the minimum paths are $l(v_{4},v_{1})=2$, $l(v_{4},v_{2})=\infty$,
$l(v_{4},v_{3})=3$ and $l(v_{4},v_{5})=\infty$ and in the last interval
$[3,3]$ we have $l(v_{4},v_{1})=1$, $l(v_{4},v_{2})=\infty$,
$l(v_{4},v_{3})=2$ and $l(v_{4},v_{5})=\infty$. In this way $C(v_{4})=0.63$

Figure 3: Temporal edges to calculate the closeness and betweenness in the
interval time $[1,3]$.

Temporal betweenness centrality quantifies the extent to which a vertex lies
on paths between other vertices. Thus, vertices with high betweenness may have
considerable influence over the information passing between nodes. Besides
that, removing these nodes from the network can disrupt communications between
other vertices [2]. Kim et al. [7] defined as:

$\displaystyle B(v)^{[t_{x},t_{y}]}$ $\displaystyle=$
$\displaystyle\sum_{i=t_{x}}^{t_{y}}\,\sum_{u,w\in
V}\frac{{\sigma(u,w,v)^{[i,t_{y}]}}}{\sigma(u,v)^{[i,t_{y}]}},$ (3)

where $\sigma(u,v)^{[i,t_{y}]}>0$ is the set of temporal shortest paths
between $u$ and $v$ in the interval $[i,t_{y}]$ and
$\sigma(u,w,v)^{[i,t_{y}]}$ is the number of temporal shortest paths that pass
through vertex $w$. The normalization factor is $(sv\,dv\,m)$, where
$m=t_{y}-t_{x}$, $sv$ is the number of nodes $s$ that has the shortest path
start in $s$ passing through $v$, and $dv$ is the number of nodes $d$ with the
shortest path that finishes in $d$ and passes through $v$.

Figure 3 shows the edges considered to calculate Betweenness of vertex
$v_{1}$. To calculate $B(v_{1})^{[1,3]}$ we consider the intervals
$[1,3],[2,3]$ and $[3,3]$. In this case, $B(v_{1})^{[1,3]}=7$,
$B(v_{1})^{[2,3]}=2$ and $B(v_{1})^{[3,3]}=1$, so $B(v_{1})=0.67$, where the
normalization factor to vertex $v_{1}$ is $36$.

##  4 Evaluations and experiments

We show the temporal modeling impact by representing the VANETs connectivity
with temporal graphs and characterize them with temporal centrality measures.
Initially, we directly apply the temporal modeling in five real data and
evaluate it statically. After that, to perform a dynamic evaluation through a
simulation, we consider the deployment of Road Side Units (RSU) application.

###  4.1 Scenarios description

In our evaluations, we use five different real datasets. The datasets have
distinct characteristics (speed, lane, or congestion levels), allowing us to
analyze different views of traffic conditions. Table 2 shows the general
properties of each scenario: number of vehicles($|V|$), number of aggregated
edges($|\mathbf{E}|$), number of temporal edges($|\mathcal{E}|$). The datasets
represent four different scenarios described as follows.

Table 2: The general properties of each scenario.

Scenario | $|\textbf{V}|$ | $|\textbf{E}|$ | $|\mathcal{E}|$
---|---|---|---
Cologne | 3 558 | 54 268 | 59 769
Motorway M4 | 2 012 | 33 731 | 93 336
Autovía A6 | 1 507 | 24 098 | 68 128
Créteil 7-9AM | 3 129 | 35 700 | 71 412
Créteil 5-7PM | 2 968 | 30 347 | 60 694

Cologne:

Naboulsi et al. [10] present a realistic synthetic dataset that reproduces the
car traffic in the greater urban area of Cologne, Germany. The synthetic data
closely matches real-world road traffic, both in terms of volume and locality.
They extracted the street layout and features from the OpenStreetMap (OSM)
repository111Available in https://www.openstreetmap.org/; the Simulation of
Urban Mobility (SUMO)222 Available in http://sumo.dlr.de/ software used to
simulate the microscopic behavior of individual drivers [10]. The dataset
spans over 2 hours (6 am-8 am) of a typical workday and encompasses 4 500
$\mathrm{km}$ of roads in an area of 400 km2, with per-second information on
the position and speed of vehicles involved in more than 700 000 trips. We
generated 25 static graphs every 288 seconds (over two hours) for temporal
network modeling.

Motorway M40:

It is part of the intermediate layer of Madrid city [11, 12]. It has an
average distance of 10,7 $\mathrm{km}$ from the city center and traverses both
the municipality’s peripheral areas and several surrounding minor cities. The
synthetic traces are composed of one day-long trace describing road traffic
over sixteen traces (with 30 min) of vehicular mobility along the road for
different days and hour combinations. The traces record the position of each
vehicle at every 500 ms. In this scenario, we generated 20 static graphs every
60 seconds for temporal network modeling.

Autovía A6:

It is a Motorway that connects the city of La Corunã to Madrid. It enters the
urban area from the northwest, collecting the traffic demand of the
conurbation built along with it [11, 12]. Also, as the M40 trace, the A6
describes road traffic over sixteen traces of 30 min, for different days and
hour combinations. The traces record the position of each vehicle at every 500
ms over a 10 km road stretch. We generated 20 static graphs every 60 seconds
for temporal network modeling.

Créteil 7am-9am and 5pm-7pm:

It based on real traffic of Créteil in France [12].It is a synthetic trace
that includes a roundabout with six entrances/exits, two or three lanes roads,
one bus road, four changing-lane spots, 15 traffic lights. It comprises around
10 000 trips, over rush hour periods of two hours in the morning (7 am to 9
am) and two hours in the evening (5 pm to 7 pm). We study each period
separately, i.e., each period is a different scenario in our study. The
authors used the OpenStreetMap database to obtain the street layout. They
derived the traffic demand information on the traffic flow from counting and
camera video analysis. The traffic assignment of the vehicular flows is
performed by Gawron’s dynamic user assignment algorithm [29], included in the
SUMO. We generated 25 static graphs every 90 seconds for temporal network
modeling.

Each scenario presents different characteristics useful in our analyses: i.
Based on complex network analysis, Cologne presents low connectivity,
availability, reliability, and navigability [10]. Also, the structure of this
vehicular network has small cliques loosely connected; ii. Motorway M40 and
Autovía A6 have a significant variability of vehicular connectivity over time
and space and their invariant correlation with vehicular density. The network
is more fragmented on A6 than on M40 [12]; and iii. Créteil 7am-9am and
Créteil 5pm-7pm present different traffic characteristics in traffic measures
(i.e., density, flow, and speed).

###  4.2 Static evaluation of temporal modeling

To quantify the impact of temporal modeling compared with the aggregated one,
we consider four static analyses: i. Quantification of the number of vertices
and edges; ii. Kolmogorov-Smirnov test (KS-test) [8]; iii. Hellinger distance
[9]; and iv. visual scatter plot behavior. In all cases, we model the real
scenarios presented above.

In all cases, we use V2V communication among vehicles within a fixed
communication radius of 100 $\mathrm{m}$ [30]. We perform the static
evaluations in Fedora 18 (Spherical Cow), with 32 processors Intel(R) Xeon(R)
CPU $E5-2670$ $$2.60\text{\,}\mathrm{G}$Hz$, and $128\text{\,}\mathrm{GB}$
RAM. We use the programming languages R [31] and Python (Available on
https://www.python.org/) to perform the statistical analysis. We use the
packages plyr [32], igraph3 [33], and time-ordered [34]. They have efficient
R/Python modules for manipulation and statistical analysis of graphs and offer
methods to incorporate time into network analysis and the construction of
temporal graphs.

In the first analysis, we observe the variations of the network topology.
Figure 4 illustrates the variation of the number of vertices and edges for the
Cologne scenario (denser) in a temporal graph in the interval time $[1,25]$.
The aggregated modeling presents a higher number of edges
($\mathbf{E}=\\{E^{1}\cup E^{2}\cup\ldots\cup E^{2}5\\}$). However, this
number has a high variation along time, as observed in the temporal graph in
Figure 4(b). This observation indicates that aggregated modeling does not
identify topological temporal information.

(a) Number of vertices

(b) Number of edges

Figure 4: Number of static vertices and edges for Cologne scenario in the
interval $[0,25]$.

Based on this initial observation, we perform the second and third analyses.
The KS-test is a non-parametric test to compare two samples, quantifying a
distance between two samples’ empirical distribution functions. It verifies if
the local measures’ distributions ($\kappa$, $C$, and $B$) of the aggregated
and temporal modeling are the same. The null hypothesis is

$H_{0}:p_{G}(.)=p_{G^{[0,T]}}(.).$

In this test, we found a $p$-value $<$2.2\text{\times}{10}^{-16}$$ for all
cases, so we rejected the null hypotheses. In detail, the Kolmogorov-Smirnov
test, $H_{0}$, the null hypothesis is rejected at the $\alpha$ level if [8]
$\mathcal{D}_{measure}(M)>\delta$, where

$\displaystyle\delta$ $\displaystyle=$ $\displaystyle
c(\alpha)\sqrt{\frac{2\times M}{M^{2}}},$ (4)

$M$ is the samples’ size of each distribution, i. e., the number of nodes of
networks. The value of $c(\alpha)$ is $1.36$ [8] representing a $\alpha=0.05$
(95% of confidence). Table 3 shows the distance values between aggregated and
temporal models for the degree ($\mathcal{D}_{\kappa}$), closeness
($\mathcal{D}_{C}$), and betweenness ($\mathcal{D}_{B}$) measures; and the
value of factor $\delta$ for the five evaluates scenarios. As we can see,
$\mathcal{D}_{measure}(M)$ is greater than the factor $\delta$ in all cases.

Table 3: Kolmogorov-Smirnov Distance values between aggregated and temporal
graph for the degree ($\mathcal{D}_{\kappa}$), closeness ($\mathcal{D}_{C}$),
and betweenness ($\mathcal{D}_{B}$) measures for the five evaluate scenarios.

Scenario | $\mathcal{D}_{\kappa}$ | $\mathcal{D}_{C}$ | $\mathcal{D}_{B}$ | $\delta$
---|---|---|---|---
Cologne | 0.9229 | 1.0000 | 0.7745 | 0.0322
Motorway M40 | 0.9950 | 1.0000 | 0.4602 | 0.0428
Autovía A6 | 0.9827 | 1.0000 | 0.4731 | 0.0495
Créteil 7am-9am | 0.9041 | 1.0000 | 0.8590 | 0.0343
Créteil 5pm-7pm | 0.9154 | 1.0000 | 0.8679 | 0.0353

The KS-test statistic is cumulative, i.e., it accentuates low-frequency
differences between the measures of aggregated and temporal models. In the
betweenness case, we can distinguish this difference among the presented
scenarios. For example, the aggregated vs. temporal ($\mathcal{D}_{B}$)
representation of the Motorway is more similar than Cologne one.

The other analysis performed, the Hellinger distance, is a distance used to
identify the similarity between two probability distributions based on
information theory concepts. This measure quantifies the similarity between
two probability distributions. Thus it ensures that the distance value is
always between 0 and 1 and got a more precise result. Consider the discrete
random variables $X$ and $Y$ defined on the same sample space
$\Omega=\\{\xi_{1},\xi_{2},\dots,\xi_{n}\\}$. The distributions are
characterized by their probability functions $p,q\colon\Omega\to[0,1]$, where
$p(\xi_{i})=\Pr(X=\xi_{i})$ and $q(\xi_{i})=\Pr(Y=\xi_{i})$. The Hellinger
distance is

$\displaystyle\mathcal{H}^{2}(p,q)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{\xi\in\Omega}\Big{(}\sqrt{p(\xi)}-\sqrt{q(\xi)}\Big{)}^{2}.$
(5)

By definition, the Hellinger distance is a metric satisfying triangle
inequality. The $\sqrt{2}$ in the definition ensure that $\mathcal{H}(p,q)\leq
1$ for all probability distributions. In this work, our sample is the
centrality measures probabilities. To get a probability for each measure, we
generate a histogram of proportions with 100 bins for each measure evaluated.
We choose the number of bins empirically by testing with 20, 40, 60, 100 (the
best fit), 150, and 200 bins. Table 4 presents the values of Hellinger
distance for all scenarios and measures evaluated. In general, we observe that
the distance captured differences between the models with the measures
evaluated.

Table 4: Hellinger distance values between aggregated and temporal graph for
the degree ($\mathcal{H}^{2}_{\kappa}$), closeness ($\mathcal{H}^{2}_{C}$) and
betweenness ($\mathcal{H}^{2}_{B}$) measures for the five evaluates scenarios.

Scenario | $\mathcal{H}^{2}_{\kappa}$ | $\mathcal{H}^{2}_{C}$ | $\mathcal{H}^{2}_{B}$
---|---|---|---
Cologne | 0.2524 | 0.4373 | 0.0905
Motorway M40 | 0.2533 | 0.4654 | 0.5370
Autovía A6 | 0.3580 | 0.9603 | 0.4897
Créteil 7am-9am | 0.0077 | 0.7351 | 0.2382
Créteil 5pm-7pm | 0.0000 | 0.7407 | 0.3665

Values for the degree ($\mathcal{H}^{2}_{\kappa}$) were smaller than $0.5$ for
all scenarios. Results for the Créteil present lower values ($0.0077$ and
$0.0000$) than the previous scenarios. This scenario has a high traffic demand
and represents a small part of the street. Such features affect the network
structure and the direct connectivity of vehicles, i.e., high connectivity.
Based on this measure, the aggregated and temporal models are similar. Values
for the closeness ($\mathcal{H}^{2}_{C}$) were over $0.7$ for the Autovía A6
and Créteil 7am-9am and Créteil 5pm-7pm scenarios. The highest value was
$0.9603$ in Autovía A6, and this scenario has a small number of vehicles and a
significant number of edges distributed in a small area, so the number of
edges in the aggregated graph is approximately three times more than a
temporal graph. The smallest values for the betweenness
($\mathcal{H}^{2}_{B}$) was $0.0905$ for Cologne. This scenario has a very
different topology from other ones, where the shortest paths in the temporal
graph have a similarity to the shortest paths in the aggregated graph.

It is essential to point out that the measure used to characterize vehicular
networks depends not only on the network topology but on the traffic density
and network size. Another critical point is the information that we can assess
from distributions and their correlation with topological structures. The
network’s average degree is immediately obtained from the degree distribution,
while closeness and betweenness use the distance distribution. Different from
KS-test, we can distinguish better the impact of the aggregated model in the
presented scenarios.

Finally, we analyze our modeling through a scatter plot. It shows the
measures’ correlation between aggregated and temporal modeling. We are not
interested in whether the correlation between the two measures is positive or
negative, but only how strongly the two given measures are numerically related
to each other. Figure 5 presents the correlation between the aggregated model
(represented on the X-axis) and the temporal one (represented on the Y-axis)
regarding degree, closeness, and betweenness, respectively.

(a) Cologne

(b) Autovia A6

(c) Creteil 7am-9am

(d) Cologne

(e) Autovia A6

(f) Creteil 7am-9am

(g) Cologne

(h) Autovia A6

(i) Creteil 7am-9am

Figure 5: Scatterplot of temporal vs. aggregated models: (a)-(c) Degree;
(d)-(f) Closeness; and (g)-(i) Betweenness.

As presented in Figures 5(a)-5(c), there is a positive correlation, but it is
not more durable, showing a difference between the aggregated and temporal
models regarding degree. Otherwise, as we can see in Figure 5(c), Créteil
7am-9am has a strong positive correlation. When the aggregated degree
increases, the temporal degree increases as well, so we can show that in this
case, the temporal and aggregated networks have the same behavior, stating the
result obtained by Hellinger distance. It is essential to highlight that the
degree is a straightforward measure in studying the topology of networks, and
its calculation in both models lost much information (Equation. 1). Some works
use degree nodes to determine route strength [35, 36, 37]. In the aggregated
graph, a vertex can be identified with a high connection in the wrong way
since, by considering the temporal order of the edges, the high link is in a
single moment. Thus, by aggregating the network, temporal relations are
ignored, and we consider weak vertices as a great disseminator of information.

Figures 5(d)-5(f) present the correlation between the aggregated and temporal
closeness. A vehicle with a high value of temporal closeness centrality
indicates that we can quickly reach other vehicles from it. Thus, vehicles
that have high closeness centrality values can be selected as influence nodes
to forward information. In this case, we identify no relationship between
aggregated and temporal closeness because there is no clear relationship
between two quantitative variables; this is because the shortest paths in an
aggregated graph are entirely different in the temporal dimension. The paths
are shortest in the aggregated graph because they abstract the time and
interaction between the vertices. Also, the paths are shorter because the
temporal interaction between the vertices is overlapping. Thus, we can
conclude that the shortest paths in a temporal graph follow the links’
chronological order, which does not coincide with the shortest paths in an
aggregated graph.

Figures 5(g)-5(i) illustrate a relationship between the aggregated and
temporal betweenness to Cologne, Autovía A6, and Créteil 7am-9am,
respectively. In this case, the scatter plot’s non-structural appearance leads
to the summary conclusion that there is no apparent correlation between
aggregated and temporal betweenness. Nodes with high betweenness have greater
control and considerable influence over the network, as more information will
pass through these nodes, making them essential for directing network
information exchange. Note, in Figure 5(g), the behavior of betweenness in the
Cologne scenario. There is no relationship between variables, but Hellinger’s
distance is $0.0905$, which contradicts the result seen graphically; this
happens because, in this scenario, there are a tiny amount of nonzero values.
This behavior impacts the speed of the information dissemination process that
we overlooked when network aggregation occurs, i.e., a node can always take
part in all the shortest paths in the graph. On the other hand, in the
temporal graph, this iteration can occur in a short time. Thus, the aggregated
graph abstracts temporal edges that influence the network’s topology and are
only visible when modeled as a temporal one.

###  4.3 Dynamic evaluation of temporal modeling

We hypothesize that the temporal model is more efficient than the aggregated
model. In this way, this work considers the deployment of Road Side Units
(RSU) application to quantify the impact of temporal modeling compared with
the aggregated one in a dynamic and simulated environment. A solution to
deploy RSUs provides affordable Internet access to connected vehicles and
extends the vehicular network coverage (VANETs) [1]. The deployment of RSUs is
essential to design an efficient dissemination system for vehicular
environments. Several solutions use the vehicular network topology to decide
where to install the RSUs. The vehicular topology is naturally temporal, i.e.,
it changes at each instant time. However, the vehicular topologies are
modeling as an aggregated graph. We identify previously that this assumption
does not allow an adequate representation. Thus, we evaluate this application
modeling the topology as a temporal graph instead of the usual one.

There are different strategies adopted in the literature to find RSUs
positioning in VANETs [13]. Generally, they want to choose a set of
intersections that optimize the vehicles’ coverage time at the dissemination
points. This problem considers an area of an urban road topology, a set of
vehicles that transit over the area considered during a given period, a group
of intersections between the roads, a subset of vehicles passing each
intersection with a minimum contact time of $\tau$. The goal is to select $k$
intersections to install a set of RSUs to maximize the number of vehicles
covered during a time threshold.

We apply the classical greedy algorithm to deploy the RSUs problem [38]
considering temporal modeling. Our goal is to show the greedy algorithm
robustness when we model the VANET topology as a temporal graph. We use only
the Cologne scenario to perform the analysis because it is a large-scale
dataset that comprises more than 250.000 vehicle routes with varied road
traffic conditions.

####  4.3.1 Greedy solution overview

Many solutions are available in the literature to maximize the number of
vehicles covered by $k$ RSUs. We use the traditional approach proposed by
Trullos et al. [38]. The authors model the problem as a Maximum Coverage with
Time Threshold Problem (MCTTP). Let $V=\\{v_{1},\ldots,v_{M}\\}$ be a set of
vehicles that transit over the area considered during a given period;
$\Im=\\{S_{1},S_{2},\ldots,S_{I}\\}$ is a collection of $I$ sets, where $I$ is
the number of intersections between the roads; each set $S_{i}\subset V$
includes all vehicles that cross intersection $i$ at least once over the
observation period. Let $\mathcal{T}$ be a matrix $I\times M$, where $I$ is
the number of intersections, and $M$ is the vehicle number. We generate the
contact matrix $\mathcal{T}$ in different ways to aggregated ($G$) and
temporal ($\mathcal{G}$) graphs.

  * •

We generate the $\mathcal{T}_{G}$ based on the sum of contact times between
vehicles and intersection over a set of aggregated graphs. We aggregated a set
of static graphs every 320 seconds and calculated the sum of contact times
considering V2I communication.

  * •

We generate the $\mathcal{T}_{\mathcal{G}}$ considering the entire time
interval (7 200 $\mathrm{s}$), so each element
$\mathcal{T}_{\mathcal{G}}(i,j)\geq 0$ is the sum of all contact times that
the vehicle $j$ remained at the intersection $i$, i.e.,

$\mathcal{T}^{[t_{x},t_{y}]}_{\mathcal{G}}(i,j)=\sum_{t_{x}\leq i\leq
t_{y}}{\tau^{i}_{ij}}.$

Figures 6-7 show the contact matrices $\mathcal{T}_{\textbf{G}}$ and
$\mathcal{T}^{[1,3]}_{\textbf{G}}$ for aggregated and temporal graph,
respectively, with $\tau$ = 5 seconds. In this example, we generate the matrix
$\mathcal{T}_{G}$ by aggregating the entire time interval from 1 to 3 seconds.
Otherwise, the matrix $\mathcal{T}^{[1,3]}_{\mathcal{G}}$ is generated
consider all contact time in the interval from 1 to 3 seconds. As a result,
the contact time to vertex $A$ considering the intersection $I_{1}$ is
$\mathcal{T}_{G}(v_{1},I_{1})=1$ and
$\mathcal{T}^{[1,3]}_{\mathcal{G}}(v_{1},I_{1})=2$.

Figure 6: Contact matrix to the aggregated and the temporal graph. Figure 7:
Vehicles and intersections interactions in the time interval $[1,3]$.

Trullols et al. [38] formulate an integer linear problem named Maximum
Coverage with Time Threshold Problem (MCTTP). The MCTTP selects $k$
intersections to install a subset of RSUs in order to maximize the number of
vehicles covered during a time threshold:

$\displaystyle
max\sum_{j=1}^{M}\Bigg{[}min\Bigg{(}\tau,\sum_{i=1}^{I}\mathcal{T}_{ij}\mathcal{Y}_{i}\Bigg{)}\Bigg{]}$
(6)

s.t.:

$\displaystyle\sum_{i=1}^{n}\mathcal{Y}_{i}\leq
k;\quad\mathcal{Y}_{i}\in\\{0,1\\}\forall_{i},$ (7)

Where $\mathcal{Y}_{i}$ is one if there is an RSU in the intersection i, and 0
otherwise (Equation 6). We place an RSU at an intersection to maximize the
number of covered vehicles, taking into account a contact time of vehicle up
to a maximum value equal to $\tau$ (in this work, we consider $\tau\leq 20s$
[38]). The constraint in Equation 7 instead limits the number of RSUs to $k$.
One or more RSUs may cover the vehicles; in the first case, we have only one
contact time; in the second, the vehicle contact time is fragmented, i.e., the
total contact time is the sum of the contacts among the vehicle and the RSUs.

The greedy algorithm 1, denoted by MCTTP-g, solves the MCTTP problem. It picks
an intersection at each step to maximize the provided coverage time [38]. The
algorithm’s input is the number of RSUs $k$ to install, a candidate set $\Im$,
the contact time $\tau$, and the matrix of contact time $\mathcal{T}$. The
output is the set of RSUs to install $\mathcal{G}$.

Algorithm 1 MCTTP-g

0: k, $\Im$, $\tau$, $\mathcal{T}$,

0: $\mathcal{G}$

1: $\mathcal{G}\leftarrow\emptyset$

2: $t_{j}\leftarrow 0,j=\\{1,\ldots,M\\}$

3: repeat

4: $W_{i}\leftarrow\sum_{j=1}^{M}min(\tau-
t_{j},\mathcal{T}_{ij}),i=\\{1,\ldots,I\\}$

5: Select $S_{i}\in\textbf{S}$ that maximizes $W_{i}$

6: $\Im\leftarrow\Im\setminus S_{i}$

7: $\mathcal{G}\leftarrow\mathcal{G}\cup S_{i}$

8: $t_{j}\leftarrow min(\tau,t_{j}+\mathcal{T}_{ij}),j=\\{1,\ldots,M\\}$

9: $k\leftarrow k-1$

10: until $k=0$ or $\Im=\emptyset$

Let $W_{i}$ be the total contact time provided by intersection $i$,
considering for each vehicle an amount such that the vehicle’s coverage time
does not exceed the threshold. Lines 5–7 select $S_{i}$ that maximizes
$W_{i}$, removing from $\Im$ and adding a greedy solution $\mathcal{G}$. The
algorithm ignores the vehicles that have reached the minimum time and complete
the transmission in time $\tau$. If the vehicle stays time in intersection $i$
not sufficient for transmission, we stored this value in a vector $t_{j}$
(Line 8), and we calculate the time to complete the transmission ($\tau-
t_{j}$) in the next iteration (Line 4).

After $k$ intersections selected, or when $\Im=\emptyset$, the algorithm
returns the set of selected RSUs $\mathcal{G}$. Thus, we consider this
algorithm to solve the MCTTP problem and analyze the positioning and coverage
of RSUs positioned using the aggregated and temporal graphs.

Figure 8 shows the map view of Cologne’s central region and the installed RSUs
for the aggregated model (blue circles) and the temporal model (red diamonds).
It is the result of the execution of the algorithm 1. As we can see, the
positioning of the RSUs when we model the scenario with an aggregated graph is
concentrated in the central part of the area, covering the same region and the
identical vehicles. Otherwise, when we model with a temporal graph, the RSUs
are more distributed, ensure better coverage.

Figure 8: Map view of the central region of Cologne and the installed RSUs to
aggregated and temporal models.

Similar to static evaluation, we also use a scatterplot to show the
correlation between the aggregated and local temporal measures. In this case,
we regard $k=500$ RSUs deployed by Algorithm 1 in Cologne scenarios
considering the modeling details of both models. As mentioned before, we are
interested in how strongly the temporal and aggregated measures are
numerically related. Figure 9 illustrates the correlation between the
aggregated model (represented on the X-axis) and temporal one (represented on
the Y-axis) regarding degree, closeness, and betweenness, respectively.

(a) Degree

(b) Closeness

(c) Betweenness

Figure 9: Scatterplot of temporal vs. aggregated models.

As presented in Figure 9(a), there is a positive correlation, but it is not
more durable, showing a difference between the aggregated and temporal models
regarding degree. In the aggregated graph, a vertex can be identified with a
high connection in the wrong way since, by considering the temporal order of
the edges, the high link is in a single moment. Thus, by aggregating the
network, temporal relations are ignored, and we consider weak vertices as a
great disseminator of information.

Figure 9(b) presents the correlation between the aggregated and temporal
closeness. In this case, we identify no relationship between aggregated and
temporal closeness because there is no clear relationship between two
quantitative variables; this is because the shortest paths in an aggregated
graph are entirely different in the temporal dimension. The paths are shortest
in the aggregated graph because they abstract the time and interaction between
the vertices. Also, the paths are shorter because the temporal interaction
between the vertices is overlapping. Thus, we can conclude that the shortest
paths in a temporal graph follow the links’ chronological order, which does
not coincide with the shortest paths in an aggregated graph.

Figure 9(c) illustrates a relationship between the aggregated and temporal
betweenness. In this case, the scatter plot’s non-structural appearance leads
to the summary conclusion that there is no apparent correlation between
aggregated and temporal betweenness. Nodes with high betweenness have greater
control and considerable influence over the network, as more information will
pass through these nodes, making them essential for directing network
information exchange. Observe the case for the betweenness in the Cologne
scenario. There is an impact on the speed of the information dissemination
process that we overlooked when network aggregation occurs, i.e., a node can
always take part in all the shortest paths in the graph. On the other hand, in
the temporal graph, this iteration can occur in a short time. Thus, the
aggregated graph abstracts temporal edges that influence the network’s
topology and are only visible when modeled as a temporal one.

####  4.3.2 Network behavior simulation

This section evaluates the impact of temporal modeling (graph and measures)
over the RSUs’ deployment. We conducted the experiments to assess the proposed
system using Veins 5.0, an open-source framework for running vehicular network
simulations. Network simulation was performed by OMNeT++ 5.5.1, a discrete
event simulator for modeling communication networks, multiprocessors, and
other distributed or parallel systems. Road traffic simulation was performed
by SUMO 1.6.0, which is well-established in traffic engineering, designed to
handle large networks. The Physical (PHY) and Medium Access Control (MAC)
layers are implemented in Veins and based on the IEEE 802.11p (WAVE) standard.
All the simulators are free-source under the Academic Public License.

In this simulation, we choose only a central submap of the city of Cologne.
The submap displays a higher incidence of traffic jams, as illustrated in
Figure 10. Also, we consider that only vehicles send packages. The residual
distance objective is to compute the stability of the network [39]. We conduct
all experiments thirty-three times on different traffic conditions with a
confidence interval of 95%. Table 5 summarizes the simulation parameter
settings.

(a) Cologne topology.

(b) Cologne heat-map - adapted [10].

Figure 10: Cologne urban area. Table 5: Simulation parameters settings.

Parameter | Value
---|---
Beacon transmission frequency | 1Hz
Total number of vehicles | 13716
Transmission range | 287m
Density of vehicles | [40–150] vehicles/$km^{2}$
Bandwidth | 10MHz
Speed (average) [15] | 60.27 mph (96.9 km/h)
Residual distance [15] | 63%
Channel | 178 (5.89 GHz)
MAC | layerIEEE 802.11p PHY
$\alpha$ | 0.5

Figure 11 presents the average vehicle coverage and total package loss with
different $k$ values for both models. As we can see in Figure 11(a), for any
RSU number, the coverage was higher when we use the temporal model. For
example, when $k=110$, the coverage is about $\approx 65\%$ with the
aggregated model and $\approx 77\%$ with the temporal one using the same greed
algorithm. For all cases, the greedy algorithm, in the aggregated model,
selects the sets of RSUs, not considering the network dynamics and timing of
temporal relationships. In contrast, in the temporal model, the greedy
algorithm selects the sets of RSUs, considering paths that are non-
instantaneous between vehicle and RSU. They respect the network dynamics and
timing of temporal relationships.

Figure 11(b) shows the number of packet losses according to the RSU insertion
rate. One factor that causes the rising of packet loss is improper RSUs
placement [40]. For example, when $k=110$, the packet loss rate is $\approx
27\%$ with the aggregated and $\approx 8\%$ with the temporal model. In the
aggregated model, the RSUs are concentrated in the central part of the
scenario, covering a few regions and vehicles. In contrast, in the temporal
model, the RSUs are dispersed in the scenario, covering different regions and
more vehicles than the aggregated model. Therefore, the temporal model has a
higher road coverage ratio and packet delivery than the aggregated model.

(a) Coverage percentage.

(b) Total package loss.

Figure 11: Coverage and Total package loss.

####  4.3.3 Temporal measures based solution

Note that previous greedy heuristics provide a good approximation of the
optimal solution but require global knowledge of the road topology and the
vehicles that cross the intersections during the observation period. We also
compare the aggregated model and measures against the temporal ones using the
genetic algorithm proposed by Moura et al. [13]. They present a genetic
algorithm strategy for the deployment of roadside units in VANETs and show
that using a simple genetic algorithm with a betweenness centrality
preprocessing could find a suitable solution when compared with other
strategies. The preprocessing uses the aggregated betweenness centrality.

We use the temporal model and measures in the preprocessing step of the
genetic algorithm proposed by Moura et al.. The objective is to find the best
intersection to install an RSU. The algorithm considers the intersections with
the highest betweenness centrality (aggregated vs. temporal) to install an
RSU. The original algorithm [13] considers the aggregated Betweenness measure
$B(v)$. In this work, we also evaluate the degree $\kappa(v)$ and closeness
$C(v)$ (aggregated vs. temporal).

We consider the aggregated, and temporal graphs of the interval from
$7am$-$8am$ (rush hour), in the Cologne scenario, with the 300 RSUs and
contact time is $30\,\mathrm{seconds}$. The temporal graph represents
intervals of $30\,\mathrm{seconds}$, totaling ten-time graphs. The results
with the temporal model and measures were always superior to the aggregated
ones.

  * •

$\kappa(v)$ presents coverage of 41.6% with the aggregated model vs. 59.2%
with the use of temporal one. This behavior occurs because, different of
aggregated degree, the temporal one choose the RSUs based a degrees balance
and consistent during the time observed.

  * •

$C(v)$ presents coverage of 39.8% with the aggregated model vs. 79.6% with the
use of temporal one. This behavior occurs because the temporal one chooses the
RSUs based on an actual vehicle’s proximity. The aggregated model could
identify nonexistent proximity. For example, a node is present only in the
first moment, but new proximity interactions will happen with future nodes
present in the same area.

  * •

$B(v)$ presents coverage of 61.4% with the aggregated model vs. 91.3% with the
use of temporal one. This difference occurs because of the same reasons given
previously.

In summary, the approach with betweenness had the best result, more than 90%
of the coverage area. In this way, we could see the differences between the
models and how they influence this decision.

##  5 Conclusion and future work

In this work, we provide an essential analysis regarding the impact of
modeling the VANETs as an aggregated and temporal graph. To do so, we use
centrality measures for temporal networks and discuss how the results can be
affected by the topology modeling approach.

In the first analysis, we observe the variations of the network topology. We
realized that the aggregated modeling does not identify topological temporal
information. In the second analysis, we quantify the aggregated model’s impact
compared to the temporal one using the Kolmogorov-Smirnov test and Hellinger
distance. We found a $p$-value $<$2.2\text{\times}{10}^{-16}$$ for all cases
in Kolmogorov-Smirnov test, so we rejected the null hypotheses:
$H_{0}:p_{G}(.)=p_{G^{[0,T]}}(.)$. Unlike KS-test, Hellinger distance can
better distinguish the impact of the aggregated model in the presented
scenarios. We presumed that the shortest paths in the temporal graph and an
aggregated graph are similar because the smallest value for the
$\mathcal{H}^{2}_{B}$ was $0.0905$ in the Cologne scenario. Finally, we
analyzed our modeling through a scatter plot and showed how strongly the
temporal measures are numerically related to each other.

To quantify the impact of temporal modeling in a dynamic and simulated
environment, we consider the RSU allocation problem in Cologne’s city’s
central submap. First, we compare our strategy with a greedy algorithm to
choose the RSUs’ positions. The results show that for all $k$ values, the
temporal model is always superior to the aggregated one using the same
placement strategy. For instance, in a scenario with 70 RSUs, we have 77% and
65% of coverage in the temporal and aggregated model, respectively. Second, we
compare aggregated modeling against the temporal ones as features in a genetic
algorithm based on complex network measures. The approach with temporal
betweenness had the better result with 90% of the coverage area against 61% of
aggregated one applied to the same scenario.

An essential contribution of this work is to use temporal measures providing
better solutions in a vehicular network environment. To the best of our
knowledge, we are the only ones that use these measures in VANETs scenarios.
As future work, we want to study more relationships in the vehicle
environment, such as vehicle connectivity, traffic optimization, location of
points of dissemination to maximize vehicle coverage, and analyze vehicle
environments with V2X communication. Moreover, we intend to use temporal
centrality measures to identify the most viable anchor zones to spread
floating contents in VANETs.

## Software availability

The information about the modeling package software are the follows:

  * •

Name of software: TC-VANETs.

  * •

Developer contact: Fillipe dos Santos Silva
<EMAIL_ADDRESS>
  * •

Address: Cidade Universitária Zeferino Vaz, s/n - Barão Geraldo. CEP:
13083-970. Campinas - SP - Brazil.

  * •

Phone number: +55 (19) 3521-7000.

  * •

Year first available: 2019.

  * •

Hardware suggested: Processor 2.6 GHz Intel Core i7, with 16 GB 1600 MHz DDR3
and HD 1 TB. However, we performed the simulations under a computer model SGI
Rackable Standard-Depth Servers, with 56 cores in 2 sockets of 2.00 GHz
Intel(R) Xeon(R) CPU E5-2660 v4, 1352 MHz 256 GB DDR3 Memory (32 $\times$ 8
GB), and Linux operating system.

  * •

Software required: All project is running over Ubuntu 16.04 (recommended) or
18.04.

  * •

Availability: Available on Github
333https://github.com/fillipesansilva/VANETs-topology-modeling-based-on-
temporal-complex-networks

  * •

Cost: All free tools.

We implemented the project in Statistical R444https://www.r-project.org and
Python 2555https://www.python.org/.

## Acknowledgments

The authors acknowledge support from the Brazilian research agency CNPq, and
INCT of the Future Internet for Smart Cities (CNPq 465446/2014-0 and CAPES
88887.136422/2017-00).

## References

  * [1] D. Naboulsi, M. Fiore, Characterizing the instantaneous connectivity of large-scale urban vehicular networks, IEEE Transactions on Mobile Computing 16 (5) (2017) 1272–1286.
  * [2] M. Newman, Networks: An Introduction, Oxford University Press, Inc., New York, NY, USA, 2010.
  * [3] M. Fiore, J. Härri, The networking shape of vehicular mobility, in: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, ACM, 2008, pp. 261–272.
  * [4] G. R. Diniz, F. D. Cunha, A. A. F. Loureiro, Improving the vehicular mobility analysis using time-varying graphs, in: 2020 16th International Conference on Distributed Computing in Sensor Systems (DCOSS), 2020, pp. 197–204.
  * [5] C. Glacet, M. Fiore, M. Gramaglia, Temporal connectivity of vehicular networks: the power of store-carry-and-forward, in: Vehicular Networking Conference (VNC), 2015 IEEE, IEEE, 2015, pp. 52–59.
  * [6] L. Qiao, Y. Shi, S. Chen, An empirical study on the temporal structural characteristics of vanets on a taxi gps dataset, IEEE Access 5 (2017) 722–731.
  * [7] H. Kim, R. Anderson, Temporal node centrality in complex networks, Physical Review E 85 (2) (2012) 026107.
  * [8] F. J. M. Jr., The kolmogorov-smirnov test for goodness of fit, Journal of the American Statistical Association 46 (253) (1951) 68–78.
  * [9] A. Basu, A. Mandal, L. Pardo, Hypothesis testing for two discrete populations based on the hellinger distance, Statistics & Probability Letters” 80 (3) (2010) 206–214.
  * [10] D. Naboulsi, M. Fiore, On the instantaneous topology of a large-scale urban vehicular network: the cologne case, in: Proceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing, ACM, 2013, pp. 167–176.
  * [11] M. Gramaglia, O. Trullols-Cruces, D. Naboulsi, M. Fiore, M. Calderon, Mobility and connectivity in highway vehicular networks: A case study in madrid, Computer Communications 78 (2016) 28–44.
  * [12] M.-A. Lébre, F. L. Mouël, E. Ménard, Vehicular networks on two madrid highways, in: 14th International Conference on ITS Telecommunications (ITST’15), 2015, pp. 423–431.
  * [13] D. L. Moura, R. S. Cabral, T. Sales, A. L. Aquino, An evolutionary algorithm for roadside unit deployment with betweenness centrality preprocessing, Future Generation Computer Systems (2018).
  * [14] P. Crucitti, V. Latora, S. Porta, Centrality in networks of urban streets, Chaos: an interdisciplinary journal of nonlinear science 16 (1) (2006) 015113\.
  * [15] O. A. Wahab, H. Otrok, A. Mourad, Vanet qos-olsr: Qos-based clustering protocol for vehicular ad hoc networks, Computer Communications 36 (13) (2013) 1422–1435.  doi:https://doi.org/10.1016/j.comcom.2013.07.003.
URL https://www.sciencedirect.com/science/article/pii/S0140366413001710

  * [16] O. A. Wahab, A. Mourad, H. Otrok, J. Bentahar, Ceap: Svm-based intelligent detection model for clustered vehicular ad hoc networks, Expert Systems with Applications 50 (2016) 40–54.  doi:https://doi.org/10.1016/j.eswa.2015.12.006.
URL https://www.sciencedirect.com/science/article/pii/S0957417415008088

  * [17] S. Elaraby, S. M. Abuelenin, Connectivity analysis of directed highway vehicular ad hoc networks using graph theory, International Journal of Communication Systems 34 (5) (2021) e4745.  doi:https://doi.org/10.1002/dac.4745.
  * [18] L. Bedogni, M. Fiore, C. Glacet, Temporal reachability in vehicular networks, in: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, 2018, pp. 81–89.
  * [19] H. Feng, Y. Xu, An empirical study on evolution of the connectivity for vanets based on taxi gps traces, International Journal of Distributed Sensor Networks 12 (2) (2016) 2580465.
  * [20] Y. Chen, M. Xu, Y. Gu, P. Li, L. Shi, X. Xiao, Empirical study on spatial and temporal features for vehicular wireless communications, EURASIP Journal on Wireless Communications and Networking 2014 (1) (2014) 180.
  * [21] Z. Wang, J. Zheng, Y. Wu, N. Mitton, A centrality-based rsu deployment approach for vehicular ad hoc networks, in: 2017 IEEE International Conference on Communications (ICC), IEEE, 2017, pp. 1–5.
  * [22] X. Youji, F. Huifang, L. Chunfeng, Dynamic topology characteristics of vanets in fading channels, in: Information Technology, Networking, Electronic and Automation Control Conference, IEEE, IEEE, 2016, pp. 524–528.
  * [23] N. Loulloudes, G. Pallis, M. D. Dikaiakos, The dynamics of vehicular networks in large-scale urban environments, in: Collaboration and Internet Computing (CIC), 2015 IEEE Conference on, IEEE, 2015, pp. 192–199.
  * [24] X. Qu, E. Liu, R. Wang, H. Ma, Complex network analysis of vanet topology with realistic vehicular traces, IEEE Transactions on Vehicular Technology 69 (4) (2020) 4426–4438.
  * [25] C. Celes, A. Boukerche, A. A. F. Loureiro, On the temporal analysis of vehicular networks, in: 2018 IEEE Symposium on Computers and Communications (ISCC), 2018, pp. 01074–01079.
  * [26] I. W. H. Ho, K. K. Leung, Node connectivity in vehicular ad hoc networks with structured mobility, in: Local Computer Networks, 2007. LCN 2007. 32nd IEEE Conference on, IEEE, 2007, pp. 635–642.
  * [27] S. Shioda, J. Harada, Y. Watanabe, T. Goi, H. Okada, K. Mase, Fundamental characteristics of connectivity in vehicular ad hoc networks, in: 2008 IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications, 2008, pp. 1–6.
  * [28] L. D. F. Costa, F. A. Rodrigues, G. Travieso, P. R. Boas, Characterization of complex networks: A survey of measurements, Advances in Physics 56 (1) (2008) 167–242.  arXiv:0505185.
  * [29] C. Gawron, An iterative algorithm to determine the dynamic user equilibrium in a traffic simulation model, International Journal of Modern Physics C 9 (3) (1998) 393–407.
  * [30] S. Basagni, M. Conti, S. Giordano, I. Stojmenovic, Mobile ad hoc networking, John Wiley & Sons, 2004.
  * [31] R Core Team, R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing, Vienna, Austria (2016).
  * [32] H. Wickham, The split-apply-combine strategy for data analysis, Journal of Statistical Software 40 (1) (2011) 1–29.
  * [33] G. Csardi, T. Nepusz, The igraph software package for complex network research, InterJournal Complex Systems (2006) 1695.
  * [34] B. Blonder, timeordered: Time-ordered and time-aggregated network analyses, r package version 0.9.8 (2015).
  * [35] W. W. Hashim, A. M. Shariff, S. I. Fadilah, A new hop-count and node-degree based routing protocol for vehicular ad-hoc networks (vanets), in: 2013 IEEE 11th Malaysia International Conference on Communications (MICC), IEEE, 2013, pp. 310–315.
  * [36] S.-S. Wang, Y.-S. Lin, Passcar: A passive clustering aided routing protocol for vehicular ad hoc networks, Computer communications 36 (2) (2013) 170–179.
  * [37] J. Zheng, Y. Wu, Z. Xu, X. Lin, A reliable routing protocol based on qos for vanet, in: The 7th IEEE/International Conference on Advanced Infocomm Technology, IEEE, 2014, pp. 21–28.
  * [38] O. Trullols, M. Fiore, C. Casetti, C.-F. Chiasserini, J. B. Ordinas, Planning roadside infrastructure for information dissemination in intelligent transportation systems, Computer Communications 33 (4) (2010) 432–442.
  * [39] O. A. Wahab, H. Otrok, A. Mourad, Vanet qos-olsr: Qos-based clustering protocol for vehicular ad hoc networks, Computer Communications 36 (13) (2013) 1422–1435.
  * [40] W. Viriyasitavat, O. K. Tonguz, F. Bai, Network connectivity of vanets in urban areas, in: 2009 6th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, 2009, pp. 1–9.