Correlation Coefficient Analysis of the Age of Information in Multi-Source Systems

This paper studies the age of information (AoI) on an information updating system such that multiple sources share one server to process packets of updated information. In such systems, packets from different sources compete for the server, and thus they may suffer from being interrupted, being backlogged, and becoming stale. Therefore, in order to grasp structures of such systems, it is crucially important to study a metric indicating a correlation of different sources. In this paper, we aim to analyze the correlation of AoIs on a single-server queueing system with multiple sources. As our contribution, we provide the closed-form expression of the correlation coefficient of the AoIs. To this end, we first derive the Laplace-Stieltjes transform of the stationary distribution of each AoI for the multiple sources. Some nontrivial properties on the systems are revealed from our analysis results.


I. INTRODUCTION
In recent years, we can see the real-time information updating systems in many places because of the ever-increasing demand of controlling time-critical information throughout network systems. The typical examples are monitoring systems of weather reports, vehicular status update systems that assist self-driving of cars, remote controlling of construction machinery, etc. In such systems, various kinds of status are displayed on equipped monitors (e.g., temperature, humidity, and air pressure in weather reports; position, velocity, and acceleration in vehicular status). When updated status of one kind is captured by a sensor, a packet is generated by the associated source of an updated information. Thereafter, it is processed by one of servers, and then displayed on the corresponding monitor. In addition, while all the servers are busy with processing, a newly arriving packet is backlogged and becomes outdated. Note that these situations occur in practice if the arrival frequency of packets is beyond the processing power of servers. Owing to the above properties of the systems, the information displayed on the monitor is not always up-to-date. Therefore, the freshness of the displayed information should be quantified and managed for those information updating systems.
From such backgrounds, a performance metric called the age of information (AoI) was proposed [1]. To define the AoI, let η(t) denote the timestamp of the generation time of the information displayed on the monitor at time t. Then, the AoI at time t is defined by The AoI defined by ∆ t can indicate the freshness, because the above expression means the elapsed time from the generation of the information displayed on the monitor. We note that, in a system with multiple sources, the AoI is defined for each source.
The AoI in queueing systems have been studied in recent years. We here focus on previous studies which investigated the AoIs in queueing systems with multiple information sources. Yates and Kaul provided the pioneering study in [2]. They considered single-server queueing systems where two sources share one server to process updated information, and derived the userful expression of the average AoI of each information source. They also studied the first-come-firstserved (FCFS) M/M/1 system as a special case, and derived the closed-form expression of the average AoI of each source. Kaul and Yates [3] showed that two-source M/M/1/1 systems with preemption outperform two-source FCFS M/M/1 systems in terms of the average AoI, which triggered further studies for such without-queue systems. Najm and Telatar [4] derived the average AoI and the peak AoI of each source in two-source M/G/1 systems with preemption. The systems with general multiple information sources were investigated by Yates and Kaul [5]. They considered the average AoI on M/M/1/1 and M/M/1/2 systems, in both of which multiple sources share one server. In case of M/M/1/2, they utilized stochastic hybrid systems to discard waiting packets, and then they successfully reduced complexity of their analysis.
As described above, most of the works handling multiple information sources have been devoted to analyzing the average AoI of each source. To the best of our knowledge, no previous works try analytical studies about the correlation of the AoIs from different information sources. In order to grasp structures of the information updating systems with the multiple sources, it is crucially important to study a metric indicating a correlation of different sources in addition to the AoIs of the individual sources. Considering the correlation leads to a better management of an information updating system with multiple sources.
In this paper, we study the correlation of AoIs of a status updating system with multiple sources, which is modeled by an M/M/1/1 queueing system with preemption. Our model is assumed to consist of multiple information sources and the corresponding monitors and to share one server. Our model described above is defined in detail in Section II.
The contribution of this paper is as follows. We first derive the Laplace-Stieltjes transform (LST) of the stationary distribution of each AoI in our model. The LST enables to obtain the mean and the variance of the AoI. Next, assuming that the number of sources is two, we provide the closed-form expression of the correlation coefficient of the AoIs, which is the main contribution of this paper. Furthermore, using this result, we reveal some nontrivial properties on our model. The rest of this paper is organized as follows. In Section II, we describe the model of our investigating information updating systems. Sections III and IV present analysis results. In Section III, we derive the LST for each AoI. In Section IV, assuming that the number of sources is two, we obtain the correlation coefficient of the AoIs. Numerical experiments are conducted in Section V. Finally, this paper is concluded in Section VI.

II. SYSTEM MODEL
We consider an information updating system such that multiple sources generate information packets of updated status. Generated packets are immediately transmitted to an M/M/1/1 queueing system, which is illustrated in Fig. 1. Note that an M/M/1/1 queueing system has only one server and no buffer space. After being processed in the server, the packets are directly sent to monitors, and then the monitors display the updated information. Each source has the corresponding monitor, and updated information of a source is displayed on its corresponding monitor. The number of sources is denoted as K ∈ N, and K := {1, 2, . . . , K} denotes the set of type indexes of sources.
Packets are generated from source k (k ∈ K) according to the time-homogeneous Poisson process with rate λ k . Service times of packets are assumed to be independent and identically distributed (i.i.d.) with the exponential distribution having mean 1/µ; that is, packets from all sources have the same service time distribution. Besides, preemption is assumed in our system; that is, the packet which currently occupies the server will be pushed out if a new packet arrives before its service completion. We refer to a packet which completes its service without being pushed out as the valid packet. Henceforth, we refer to generation times of packets as arrival times. In addition, we define λ := k∈K λ k as the total arrival rate of the K sources.

III. AOI FOR EACH SOURCE
In this section, we derive the LST of stationary AoI of each source. For k ∈ K and n ∈ Z := {0, ±1, ±2, . . . }, let α k,n denote the nth arrival time of the packet of source k, and S k,n denote the service time of the packet of source k which arrives at α k,n . We define A k (t) as the AoI of source at time t ∈ R. Using these notations, we have the following expression, for k ∈ K and t ∈ R.
where β k,n := α k,n + S k,n . Samples paths of A k (t) are illustrated in Figs. 2 and 3. {(α k,n , S k,n )} n∈Z is the stationary and ergodic marked point process. Thus, we define A k , k ∈ K, as the random variable following the stationary distribution of In addition, we define some notations related to valid packets. For k ∈ K and n ∈ Z, we define α * k,n and S * k,n as the arrival time and service time of the nth valid packet of source k, respectively. We also define β * k,n as the nth departure times of the valid packet; that is, β * k,n = α * k,n + S * k,n . Without loss of generality, we assume that The service time distribution of valid packets is obtained as follows The service time of a valid packet of source k ∈ K follows the exponential distribution having mean 1/(λ + µ).

Proof.
Let X a denote a random variable following the exponential distribution with mean 1/a for a > 0. Note that packets arrive according to the Poisson process with rate λ if we ignore types of sources. In addition, a packet is valid if no other packets arrive until its service is completed. Thus, it follows that, for k ∈ K and n ∈ Z, ✷ Using this lemma, we obtain the LST of each source.

Theorem 1 The Laplace-Stieltjes transform of the stationary
AoI of source k ∈ K, denoted by A k (s), is given by

Proof.
We define A + k,n (resp. A − k,n ) as the AoI of the immediately after (resp. before) the nth update of source k.
where λ * k denotes the arrival rate of valid packets of source k. Note here that A + k,n is equivalent to the service time of the valid packet arriving at α * k,n . Thus, from Lemma 1, we obtain We define R k,n as the interval time of nth and (n+1)st updates of source k; that is, R k,n = β * k,n+1 − β * k,n . The following relation holds for k ∈ K and n ∈ Z.
We also have which is shown in Appendix A. Applying (2) and (4) to (3) yields Furthermore, a packet of source k ∈ K is valid with probability µ/(λ + µ), independently other packets. We then have Consequently, applying (2), (5), and (6) to (1), we obtain Theorem 1. ✷ Furthermore, using Theorem 1, we can easily obtain the expectation and variance of each AoI.

IV. CORRELATION COEFFICIENT
In this section, assuming that K = 2, we derive the correlation coefficient of stationary AoIs. For n ∈ Z, let α n denote the nth arrival time of packets of either sources 1 or 2, and let S n denote the service time of the packet arriving at α n .
In addition we define some notations related to valid packets. We define α * n and S * n as the arrival time and service time of the nth valid packet of either sources 1 or 2, respectively. We also define β * n as the nth departure times of the valid packet of either sources 1 or 2; that is, β * n = α * n + S * n . Without loss of generality, we assume that We define R n as the interval time of nth and (n+1)st updates; that is, R n = β * n+1 − β * n . We obtain the following lemma.
Lemma 2 R n follows the convolution of two independent random variables following exponential distributions having mean 1/λ and 1/µ.

The proof of Lemma 2 is shown in Appendix B.
We first consider the AoI of source k ∈ {1, 2} immediately after source 1 or 2 is updated. We define A † k,n := A k (β * n ) for k = 1, 2 and n ∈ Z. We obtain the following lemma.
Proof. For n ∈ Z, let C n denote the type of the valid packet arriving at α * n . For k = 1, 2 and n ∈ Z, we define D k,n := min {m ≤ n; C m = k} , which means that the D k,n th valid packet is the last packet which arrives from source k before the nth update. Note that D k,n = n if the valid packet arriving at α * n is generated by source k. Using this notation, we have A † k,n = S * D k,n + n−1 j=D k,n R j , which implies that {A † 1,n }, {A † 2,n } and {A † 1,n A † 2,n } are stationary and ergodicity.
Since all packets have the same service time distribution, {C n } are the i.i.d. random variables such that P(C n = 1) = λ 1 /λ and P(C n = 2) = λ 2 /λ. We then have Note that {D k,n } is independent of {S * n } and {R n }. It then follows from (7) and (8) that, for n ∈ Z and k = 1, 2, Applying Lemmas 1 and 2 to the above, we obtain In addition, we have, for m, ℓ ∈ Z, Note that S * n does not depend on S * n−m and R ℓ for ℓ = n − 1, but depends on R n−1 . Thus, from (7) and (9), we obtain By definitions of R n , we have Thus, it follows from Lemma 1 and (6) that (10) Applying Lemmas 1, 2 and (10) to the above, we obtain Using Lemma 3, we obtain the main theorem of this paper.

Theorem 2 The correlation coefficient of AoIs in 2-source M/M/1/1 push-out queue, denoted by ρ, is given by
Proof. Using the pointwise ergodic theorem (see, e.g., [6, Theorem 1.6.4]) yields Dividing the integral in (12) by update times {β n }, we have where N (t) denotes the total number of updates in [0, t) and Note that, for t ∈ [β * n , β * n+1 ), We estimate the right-hand side of (13). From (15), we have It follows from Lemmas 2 and 3 that R n and A k (β * n ) are finite w.p.1. Thus, it follows from (16) that Furthermore, {R n } is the i.i.d. random variables, because the system becomes empty at time β * n , n ∈ Z. Thus, it follows from the elementary renewal theorem and Lemma 2 that Furthermore, using the pointwise ergodic theorem, we have where the first equation holds because it follows from (18) that lim T →∞ N (T ) = ∞. Substituting (17)-(19) into (13) yields Next, we calculate E[F 0 ]. Applying (15) to (14), we have Using Lemmas 2 and 3, it follows from the above that Combining the above and (20), we obtain Consequently, from the above and Corollary 1, we obtain ✷ From Theorem 2, we can see some nontrivial properties on the systems as follows. The proof of Corollary 2 is omitted due to the page restriction.

V. NUMERICAL RESULTS
In this section, we provide numerical results of the correlation coefficient presented in Theorem 2, and confirm the statements presented in Corollary 2 through the numerical results. Fig. 4 shows the correlation coefficients which is numerically computed with several cases using Theorem 2, where the x-axis represents the value of λ 1 , the arrival rate of source 1. Note that the parameter µ is fixed for each curve in Fig. 4, and λ 2 is fixed as λ 2 = 2.
From Fig. 4, we observe that ρ is always negative, that is, the two AoIs in our model always have a negative correlation, which implies (i) in Corollary 2. We also find that the curves in the figures are all convergent to zero, so that (ii) in Corollary 2 is likely to hold with respect to λ 1 . Moreover, we see that the correlation coefficient has a minimum value with respect to λ 1 . This means that a certain arrival rate of packets from one source gives the strongest negative correlation with the other source. Furthermore, we see from the figure that the smallest minimum value of ρ is seen when µ = 4. Actually, the smallest value in the figure is −1/6, and is achieved when (λ 1 , λ 2 , µ) = (2, 2, 4), which corresponds to (iii) in Corollary 2.

VI. CONCLUSION
In this paper, we considered a correlation of the AoIs of two sources sharing one server to process information, and derived the closed form expression of the correlation coefficient, on the model of M/M/1/1 queueing systems. In addition, we also derived the expression of the LST of the stationary distribution of each AoI on the assumption that multiple K sources share the one server. From our analysis, we found that the correlation coefficient is always negative, and that the correlation coefficient has a certain minimum value. This indicates that there is always a negative correlation between the two AoIs, and the strongest negative correlation is achieved by adjusting the parameters introduced in our model.
For further study, it would be expected that the correlation coefficient is investigated with more generalized assumptions for modeling the systems because our model adopts an elemental M/M/1/1 queueing systems with the common service rate for all the sources. To consider the correlation among several sources is also an interesting research point.

APPENDIX A
This appendix is devoted to the proof of (4). For k ∈ K and n ∈ Z, let N k,n denote the number of arriving packets of source k in (0, β * n ]. We define M k,n as the number of arriving packets of source k in (β * n , β * n+1 ]; that is, M k,n = N k,n+1 − N k,n . In addition, we define U k,n := α k,n+1 − α k,n . Let also J k,n denote the length from the time that the nth valid packet departs to the time that a new packet arrives from source k; that is J k,n = U k,N k,n − S k,N k,n . We have the following relation (see Fig. 2). R k,n = J k,n + M k,n −1 ℓ=1 U k,N k,n +ℓ + S k,N k,n+1 . which leads to E e −sR k,n M k,n = E e −sJ k,n · E e −sS k,N k,n+1 × M k,n −1 ℓ=1 E e −sU k,N k,n +ℓ M k,n .(21) For ℓ = 1, . . . , M k,n − 1, the (N k,n + ℓ)-th arrival packet is not valid. We then have, for ℓ = 1, . . . , M k,n − 1, where X a denotes a random variable following the exponential distribution with mean 1/a for a > 0. Furthermore, it follows from the memoryless property that Note that S k,N k,n+1 is the service time of a valid packet. Thus, it follows from Lemma 1 that E[e −sS k,N k,n+1 ] = λ + µ s + λ + µ . (24) Applying (22)-(24) to (21), we obtain E e −sR k,n |M k,n = λ + µ s + λ + µ λ k s + λ k × λ + µ s + λ + µ λ k s + λ k s + λ λ M k,n −1 .

(25)
Finally, we show the distribution function of M k,n . A packet is valid if no packets (of all sources) arrive before its service completion. It then follows from the independence of {α k,n } and {S k,n } that a packet is valid with probability µ/(λ + µ), independently other packets. Therefore, for any n ∈ N and k ∈ K, M k,n follows the geometric distribution on N with parameter µ/(λ + µ). Thus, from (25), we obtain E[e −sR k,n ] = λ k µ (s + λ)(s + µ) − (λ − λ k )µ .
As similar to (21), for any n ∈ N, M n follows the geometric distribution on N with parameter µ/(λ + µ). Thus, from (31), we obtain E[e −sRn ] = λ s + λ µ s + µ , which means that R n follows the convolution of X λ and X µ .