Keep It Fresh: Reducing the Age of Information in V2X Networks

Keep It Fresh:

Reducing the Age of Information in V2X Networks

Luca Baldesi

DISI – University of Trento

Trento, Italy

[email protected]

Leonardo Maccari

DISI – University of Trento

Trento, Italy

[email protected]

Renato Lo Cigno

DISI – University of Trento

Trento, Italy

[email protected]

ABSTRACT

The freshness of information is of the utmost importance in many contexts, including V2X networks and applications. One measure of this metric is the Age of Information (AoI), a notion recently introduced and explored by several authors, often with specific reference to vehicular networks. With this work, we explore the possibility of reducing the AoI of multi-hop information flooding in V2X networks exploit-ing the properties of the Eigenvector Centrality (EvC) of nodes in the topology, and the possibility that each node computes it exploiting only local information and very easy computations, so that each node can autonomously adapt its own networking parameters to redistribute information more efficiently. Starting from theoretical bounds and results, we explore how they hold in urban-constrained topologies and compare the AoI achieved exploiting EvC with the AoI achievable without this optimization of the nodes’ behavior. Simulation results show a meaningful improvement with-out using additional resources and withwith-out the need of any global coordination.

CCS CONCEPTS

• Networks → Network performance analysis; Routing protocols; Packet scheduling;

ACM Reference Format:

Luca Baldesi, Leonardo Maccari, and Renato Lo Cigno. 2019. Keep It Fresh: Reducing the Age of Information in V2X Networks. In Pro-ceedings of 1st ACM Workshop on Technologies, mOdels, and Protocols for Cooperative Connected Cars (TOP-Cars’19). ACM, New York, NY, USA, 6 pages. https://doi.org/10.475/nnnnn

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).

TOP-Cars’19, July 2019, Catania, Italy © 2019 Copyright held by the owner/author(s). ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. https://doi.org/10.475/nnnnn

1

INTRODUCTION

The concept of Age of Information (AoI), different from delay and latency, was introduced in the early ’2010s as a measure of the efficiency of information distribution, especially for ap-plications that require periodic updates in mesh networks [8]. A recent survey [9] provides the background necessary on this novel concept, while some recent works [6, 7, 12, 13] explore optimization and minimization techniques on sin-gle channel and multi-channels environments. As noted in [7], AoI “captures the freshness of the information from the perspective of the destination". Needless to say, in V2X networks periodic updates like Cooperative Awareness Mes-sage (CAM) mesMes-sages are of paramount importance and their fast delivery to many vehicles, e.g., for cooperative driving, is fundamental [4], and the performance is driven by the perspective of the destination.

Recently we have proposed and developed a methodology to optimize the streaming of information in generic mesh networks [1], and we have also successfully applied it to sporadic flooding of messages in low duty-cycle networks [2]. The optimization takes, as the metric AoI, the perspective of the destination, imposing a “receiver equal” policy, which means that it tries to equalize the amount of information that destinations periodically receive. We call this policy Receiver Equal flooding (REf). The technique devised is based on the

notion of Eigenvector Centrality [3], which, as we have shown in [1] can be computed very easily and locally at each node when the network is described by a stochastic adjacency matrix. We also recall that the eigenvector centrality is the base of the PageRank algorithm initially used by Google, albeit this has no relation with the properties we use here.

The contribution of this work is showing that the receiver equal policy leads to a reduction of the AoI in generic graphs. To show this property we derive a generic stochastic bound for the expectation of the AoI mediated on every source and destination of the network, and we show that in realistic urban topologies not only the mean of the AoI measured in simulations is below this bound, but also the 90th percentile is below this bound. Furthermore, the Empirical Cumulative

Density Function (ECDF) measured with our policy is a sto-chastic inferior of the ECDF measured without the use of the receiver equal policy.

2

BACKGROUND AND MODEL

We briefly recall here key results and notation from the literature, defining AoI and REf.

2.1

Age of Information on Networks

We mainly refer to [8] for the definitions, and we consider a flow of generated packets labeled 1, 2 . . . ,z, . . .. Without loss of generality, but differently from [8], we consider a discrete time system1with time indexk, and we focus on the case of periodic information generation with inter-arrival timeD, leaving the analysis of stochastic inter-arrivals for future work. The age of information at noded at time k with respect to a given source of informations is:

∆sd(k) = k − usd(k)

whereusd(k) is the generation time of the last packet received

byd from s. We call kz

sd the reception time of packetz from

nodes by node d, and we call Fsd the random variable (RV)

that describes the dissemination delay of a message from a sources to node d, hence,

kz sd = zD + Fsd and usd(k) = max z {zD, ∀ z | k z sd ≤k}

InterpretingFsd as the service time of a D/G/1/∞/FIFO

queuing station, with the same reasoning of AoI [8], the steady state AoI between nodess and d is

¯

∆sd = lim

k →∞∆sd(k) =

DE[Fsd]+ E[D2]/2

D (1)

Given a sources, mediating over all destinations d we get ¯ ∆s = 1 (N − 1) Õ d ,s ¯ ∆sd (2)

and mediating over alls ¯ ∆ = _N1 Õ s ¯ ∆s = E[Fc]+ D 2 (3)

whereN is the number of nodes in the network, and Fc is

the RV obtained by the superposition of allFsd.

Unfortu-natelyFsd are not i.i.d RV so we cannot in principle make

approximations based on the central limit theorem; however, it can be interesting in the future to explore how such an ap-proximation remains close to measured results as a function of the network topology. In the derivation of Eq. (3), there

1_{The reason of the discrete time modeling is due to the mathematical}

frame-work that allows the derivation of REf, but we are confident that results

holds in continuous time too.

is the implicit assumption that the network maintains the ordering of packets, which is not necessarily true in reality. Simulation results, where this assumption is not verified, show that the approximation in the model does not hamper its validation.

2.2

A Bound on Receiver Equal flooding

In [1] and [2] we have derived the conditions that guarantee an optimal performance in streaming/flooding given that the overall resources allocated to the process remains constant and minimal, i.e., the the total number of times a packet is propagated by any node is not changed from one flooding strategy to another. We briefly summarize here these results and a stochastic upper bound for the flooding delay that is valid independently from the network topology given some basic properties are guaranteed. A cycleT in the following can be interpreted as the elementary time step of a discrete time model.

LetA′be a stochastic transition matrix for an undirected graphG(V , E), |V | = N , so that the element A_{i j}′ ∈ [0, 1] ⇐⇒ (i, j) ∈ E. A′

i j represents the probability for nodej to send

a packet to nodei during a cycle T and ®1TA′ = ®1T. LetΘi

be the throughput (in terms of packets sent per cycle) that nodej sustains on average in a cycle and Θ the resulting column vector. We start from a condition in which flooding in a network is obtained by having each node sending one packet per cycle (Θ = ®1) to one of its neighbors at random (represented byA′_{). We can call this strategy Sender Equal}

flooding (SEf), and we improve it introducingΘ and A as

follows, (from Theorem 1 in [1]): Θj = xj N Õ l=1 A′ l j xl , Ai j= A′_{i j} xi ÍN l=1 A′ l j xl (4) such that: ® 1= AΘ (5) |Θ| = |®1| = N (6) ® 1TA = ®1T (7) A′ i j = 0 ⇐⇒ Ai j = 0 (8)

wherexi ∈ R is the PageRank centrality of node i. The

theorem states that the new stochastic transition matrixA describes the same links asA′but with different probabilistic weights (Eqs. (7) and (8)), and Θj represents the number

of packets nodej sends during a cycle T . In other words starting from a condition in which flooding in a network is obtained by having each node sending one packet to one of its neighbors at random we obtain a condition where nodes send more or less packets per cycle depending on their centrality, and they send them to neighbors with a probability

0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 0 5 10 15 20 Pr obabilit y time PMF(FΩ)

Figure 1: Distribution of flooding delay according to the upper bound with 100 nodes.

that depends, again, on centrality. As a result we equalize the probability of reception while the overall amount of resources used remains the same. It is important to stress that this optimization can be performed locally, through neighbour gossiping. Moreover, if transition probabilities are uniform, only one-hop neighbour information is required and convergence is reached immediately [1].

As reported in [2], it is possible to compute a stochastic upper bound Ω(k) for the probability of reception under REf that holds independently from the network topology,

namely:  Ω(k + 1) = 2Ω(k) −3 2Ω2(k) + Ω3_{(k )} 2 Ω(0) = 1 N (9) Eq. (9) express the Cumulative Density Function (CDF) of the upper bound of the flooding delay. As we work in discrete time this is a step function, and its derivative is a Probability Mass Function (PMF). By way of example, Fig. 1 reports the PMF of this upper bound for any network with 100 nodes.

LetFΩbe the RV that describes the stochastic bound in Eq. (9), then by substitutingFc = FΩin Eq. (3) we obtain

an upper boundγ of the average AoI independent from the network topology:

γ = E[FΩ]+D

2 (10)

3

V2X NETWORK MODEL

The theoretical framework derived in Section 2 is valid for (almost) any topology, but clearly introduces approximations and assumption that need some form of validation. In partic-ular, REf optimizes the average AoI, but does not guarantee

that the average is not reduced penalizing marginal nodes, thus we need to verify distributions and different sources and topologies. Another interesting analysis regards the bound γ defined in Eq. (10): again it is a bound on the average, so how often it is violated by outliers? Or, in other words, can

Figure 2: Portion of the map of the city of Trento. we use this bound safely for dimensioning V2X multi-hop communication systems?

Furthermore, as we already noted the theory assumes that packets are delivered in order, while in a network there might be mis-ordering due to packets that follow different routes. This probability may be minimized ifD >> 1, however to test how much reordering may affect our results we set, in simulations,D = 1. Finally, we want to test our results in topologies that are somewhat realistic in terms of Vehicular Communications. Being our department based in Trento, Italy, we focus on the local street map, which can be eas-ily obtained through OpenStreetMap2and is represented in Fig. 2.

The street map is centered at the GPS coordinate (46.0585, 11.1228) and has a radius of 1 km. On this map we randomly place 100 nodes (vehicles or road side units is irrelevant) uniformly with respect the street lengths and the number of street lanes in an area of radius 500 m. Different placements results in different topologies, all characterized by the same “urban” constraint. With 100 nodes andD = 1 Eq. (10) yields γ ≃ 6.93 +1

2 = 7.43, and this will be our base reference for

analysis.

To fix ideas we can imagine that this number refers to some standard message inter-arrival time, like the 100 ms of CAMs, and the multi-hop distribution system piggy-backs information to be disseminated on the same periodic mes-sage3. Other scenarios include TDMA-based technologies, 5G CV2X [5] where resources are allocated to nodes (vehicles)

2_{https://www.openstreetmap.org}

3_{We are aware that sticking to standards CAMs do not work like described,}

but these are just examples to help mapping the theoretic framework on real scenarios.

Figure 3: Vehicular network randomly generated for the map of the city of Trento with 100 nodes.

by the base station, or networks of fixed V2X nodes (Road Side Unit (RSU), traffic lights, etc.). Also Visible Light Com-munications (VLC) networking, where clearly information need multi-hop to disseminate [10, 11].

To keep the scenario simple, once the vehicles or RSUs are placed randomly on the street topology respecting street lengths and width to modulate density, the simulator create bidirectional links among all nodes that are less than 300 m apart. An example of graph generated through our model is presented in Fig. 3. For the time being we do not consider buildings, so the network we derive is not representative of technolgies that require strict line of sight, an analysis left for future work.

During simulations, we consider each node as a data pro-ducer with rateD = 1, and all nodes are interested in receiv-ing all information, thus requirreceiv-ing floodreceiv-ing in the network. Data multiplexing into aggregated packets and creation of node clusters with a backbone to orchestrate the distribu-tion can be considered, but they can only improve the basic performance gains we discuss here, obviously reducing the bound in Eq. (10).

4

RESULTS

We use an event driven simulator4_{computing ¯∆}

sd for all

the receiving vehiclesd ∈ V given a sender s and we iterate over all nodes as senders as well as repeating the distribution for 100 messages, so that every simulation yields 9.9 × 105

message delivery delays. As already mentioned we setD = 1 which is the worst case scenario, sample simulations with differentD confirm the results.

4_{https://github.com/AdvancedNetworkingSystems/IFloodS} 2 4 6 8 10 12 14 1 2 3

-

Δ (c ycle s) Graph ID

-Δ, SEf

-

Δ, REf γ

Figure 4: Boxplots of the AoI ¯∆s simulated using three

different graphs.

We report data with boxplots, with minimum and maxi-mum at the whiskers and 10th and 90th percentiles for the boxes. We are interested to compare the REf flooding

strat-egy we have proposed with the theoretical boundγ that we have found and with the “traditional” flooding strategy, where every node sends the same amount of information and that we call SEf. The two strategies use, for the entire

network, exactly the same amount of transmission resources, so that the comparison is fair, and they also use similarly “blind” scheduling policies based only on a weighted random selection of the neighbors based on the stochastic adjacency matrix. Heuristic scheduling optimizations are easy for both schemes (e.g., do not send the message to the node that has sent you the information and blacklist nodes that you have already sent the message to), but would make the results not coherent with the boundγ . For this reason we do not explore heuristics here, though we are confident that they leave the relative performance of REf and SEf unaltered, or

even improve the relative REf performance because of the

additional knowledge on the topology that is inherent to the Receiver Equal strategy.

Out goal is to answer these questions:

(1) How do REf and SEf strategies perform in terms of

mean AoI?

(2) What are the advantages of the REf?

(3) How does the performance of REf compare with the

stochastic bound of Eq. (10)?

For the same map area of Trento, we consider three possi-ble vehicular networks, one of them is represented in Fig. 3. Fig. 4 reports AoI ¯∆s mediated over all destinations given a

senders. Simulations iterate over all the vehicles as senders generating 100 different messages per sender, so each boxplot includes 9900 points.

As can be easily noted, REf performs consistently

in terms of the absolute maxima and in terms of distribu-tion mass, while the absolute minima remains comparable as expected. These results show that, keeping constant the overall amount of allocated resources, REf grants a

distri-bution boost and a consequent improvement in the AoI. In-deed, these initial measures hints to the possibility that REf

stochastically dominates SEf, an interesting possibility that

might be proven in the future.

The stochastic bound of Eq. (10) states that, on average, the AoI ¯∆ achieved using REf on a network of 100 nodes is

lower than 7.43. The results of Fig. 4 not only corroborates this theoretical result, but indicate that, at least for these networks, more than 90% of the values of ¯∆s using REf

re-main below the threshold, indicating that boundγ in Eq. (10) is an extremely powerful means to dimension with great simplicity complex dynamic distribution systems.

In other words, these results indicates that not only REf

performs consistently better than SEf, but it also comes with

a theoretical framework that yields a stochastic bound that is not available for SEf and that can be of paramount

impor-tance for designing and realizing real-time soft-constrained flooding systems in vehicular networks.

Although the aggregated mean AoI ¯∆s allows a good

in-sight in the overall performance on the entire network, we are also interested in studying if any receiver or any sender may be penalized by REf. To do this we aggregate the

simu-lation measures for one of the scenarios in sender or receiver specific boxplots. Namely, we collect ¯∆sd(see Eq. (1)) so as

to build a boxplot of all ¯∆s (see Eq. (2)) as a function of the

receiver, or all ¯∆das defined in Eq. (11).

¯ ∆d = 1 (N − 1) Õ s ,d ¯ ∆sd (11)

We start analyzing ¯∆s. Figure 5 reports the boxplots of the

AoI ¯∆sas a function of the receiver vehicle. Thex axis reports

50 out of 100 vehicles ordered by increasing AoI to improve readability, results for the other vehicles are stochastically identical to those reported, and we were careful to avoid “cutting” possible outliers. Again REf performs consistently

better than SEf and we can see that the stochastic boundγ

of Eq. (10) is valid for all vehicles, and for most vehicles the 90th percentile is belowγ . This result is due to the Reception-Equal property which optimizes the network resources so to grant a propagation of data across the network as uniform as possible. This results are fundamentally the same presented in Fig. 4, but here it is possible to appreciate that no receiver is penalized in any way, while in Fig. 4 there is no way to see if all the outliers of the boxplot belong to the same vehicle or not.

Now we want to analyze if REf penalizes any sender. To

this end Fig. 6 reports the boxplots of the AoI ¯∆das a function

of the sender vehicle. Also in this case REf performs

consis-tently better than SEf both in terms of mean AoI maxima

and mass. The stochastic bound of Eq. (10) still holds for all the nodes, although for the nodes with worst performance, probably located in a peripheral fringe of the network, the 90th percentile is aboveγ , which is perfectly consistent with the theory, albeit maybe a bit annoying from a dimensioning point of view. Recall, however, that no optimization heuristic is applied here, and we deem that a properly crafted heuristic will not only reduce ¯∆sdon average, but also “compact” the

distribution, improving the performance for outliers (topo-logically peripheral nodes) more than that of central nodes.

5

DISCUSSION AND FUTURE WORK

AoI has been introduced to capture the concept of informa-tion freshness from the receiver point of view. In the context of vehicular networks this metric can have significant im-portance due to the existing communication applications that require periodic updates. Our proposed flooding strat-egy, called Receiver Equal flooding, optimizes the network resources for data flooding and it can grant performance improvements on the AoI for vehicular networks compared to traditional strategies that do not exploit topological prop-erties of the network. We remark that REf achieves this with

zero signalling and without building a specific distribution overlay (e.g., a tree) on top of the network, so it is perfectly suited for a highly dynamic and time-varying environment as V2X communications. In this work, we derived and vali-dated through simulations a stochastic boundγ on the mean AoI ¯∆, a bound that depends only on the number of nodes in the network and is entirely independent from the topology. Moreover, we have shown experimentally that REf is

supe-rior to the more wide-spread SEf in terms of performance.

This contribution is just a first step in exploiting the Eigen-vector Centrality in the management of V2X communica-tions, and much work lies ahead to improve the bound, pos-sibly finding ways of fine-tuning it either to some network properties (e.g., average number of links per node) or to scheduling heuristics, for instance finding a deterministic worst-case bound that can be used for hard real-time appli-cations and not a stochastic one that discounts the lack of a worst case dissemination delay inherent to a blind random choice of the nodes’ neighbors. We stress that this limitation is due to the theoretical analysis to obtain the bound and is by no way inherent to REf strategy, which can be computed

and used with any scheduling strategy.

REFERENCES

[1] Luca Baldesi, Leonardo Maccari, and Renato Lo Cigno. 2017. On the Use of Eigenvector Centrality for Cooperative Streaming. IEEE Comm. Letters 21 (June 2017), 1953–1956.

2 3 4 5 6 7 8 9 10 11 12 0 10 20 30 40 50 Receiver

-Δ, SEf

-

Δ, REf γ

Figure 5: Boxplots of ¯∆s as a function of the receiver vehicle.

2 3 4 5 6 7 8 9 10 11 12 0 10 20 30 40 50 Sender

-Δ, SEf

-

Δ, REf γ

Figure 6: Boxplots of ¯∆ddistribution as a function of sender vehicle.

[2] Luca Baldesi, Leonardo Maccari, and Renato Lo Cigno. 2019. On the Properties of Infective Flooding in Low-Duty-Cycle Networks. In 15th IFIP/IEEE Conf. on Wireless On demand Network Systems and Services (WONS 2019). Wengen, CH, 1–8.

[3] P. Bonacich. 2007. Some unique properties of eigenvector centrality. Social Networks 29, 4 (2007), 555–564.

[4] Falko Dressler, Florian Klingler, Michele Segata, and Renato Lo Cigno. 2019. Cooperative Driving and the Tactile Internet. Proceedings of the IEEE 107, 2 (Feb 2019), 436–446.

[5] M. Gonzalez-Martín, M. Sepulcre, R. Molina-Masegosa, and J. Gozalvez. 2019. Analytical Models of the Performance of C-V2X Mode 4 Vehicular Communications. IEEE Transactions on Vehicular Technology 68, 2 (Feb 2019), 1155–1166.

[6] Q. He, D. Yuan, and A. Ephremides. 2018. Optimal Link Scheduling for Age Minimization in Wireless Systems. IEEE Trans. on Information Theory 64, 7 (Jul. 2018), 5381–5394.

[7] I. Kadota, A. Sinha, and E. Modiano. 2018. Optimizing Age of Informa-tion in Wireless Networks with Throughput Constraints. In 37th IEEE Conference on Computer Communications (INFOCOM 2018). 1844–1852. [8] S. Kaul, R. Yates, and M. Gruteser. 2012. Real-time status: How often should one update?. In 31st Annual IEEE Int. Conf. on Computer Comm. (INFOCOM): Mini-Conference. Orlando, FL, USA, 2731–2735. [9] A. Kosta, N. Pappas, and V. Angelakis. 2017. Age of Information: A

New Concept, Metric, and Tool. Foundations and Trends in Networking

12, 3 (2017), 162–259.

[10] Michele Segata, Renato Lo Cigno, Hsin-Mu Tsai, and Falko Dressler. 2016. On Platooning Control using IEEE 802.11p in Conjunction with Visible Light Communications. In 12th IEEE/IFIP Conf. on Wire-less On demand Network Systems and Services (WONS 2016). Cortina d’Ampezzo, Italy, 124–127.

[11] W. Shen and H-M Tsai. 2017. Testing vehicle-to-vehicle visible light communications in real-world driving scenarios. In 2017 IEEE Vehicular Networking Conference (VNC). 187–194.

[12] A. A. Simiscuka and G. Muntean. 2018. Age of Information as a QoS Metric in a Relay-Based IoT Mobility Solution. In 14th Int. Wireless Comm. Mobile Computing Conference (IWCMC). 868–873.

[13] R. Talak, S. Karaman, and E. Modiano. 2018. Distributed Scheduling Al-gorithms for Optimizing Information Freshness in Wireless Networks. In 19th IEEE Int. Workshop on Signal Processing Advances in Wireless Communications (SPAWC). 1–5.