Analyzing Age of Information in Multiaccess Networks with Time-Varying Channels: A Fluid Limits Approach

I. INTRODUCTION

AGE of information (AoI) [2] is defined as a timeliness metric to quantify the time elapsed since the generation of the freshest information received at a destination. In a timecritical networked system, it is desirable to maintain a low level of AoI at a node that depends heavily on the specific information [3], [4]. Therefore, the minimization of AoI is a systematic task, encompassing lowering the communication delay, sensing delay, data processing delay and considering their interplay. In this paper, we focus on the part of AoI that is attributed to wireless network scheduling, especially scenarios with a large number of users and time-varying channels.

In wireless networks, two fundamental challenges exist for AoI optimization: Collisions and channel fading. To circum- vent collisions among user transmissions, a carefully designed scheduling algorithm is necessary. Assuming only one user can occupy the channel at any time instance, the scheduler needs to arrange the order and frequency of user transmissions, which inevitably introduces aging of information maintained by each user. On the other hand, channel fading results in a time-varying transmission environment, wherein not only the user packets can be lost due to erroneous transmissions, but also the error probability changes over time. Regarding these, many works have been dedicated to analyzing and optimizing AoI in wireless networks, which are discussed below.

A. Related Work

Considering active sources in a wireless multiaccess network, i.e., the transmitted information is always fresh, the AoI is in fact identical with time-since-last-service [5]. With users having heterogeneous i.i.d. transmission successful probabilities, denoted by [TeX:] $$q_n \forall n \in[1, \cdots, N]$$, and one of them is scheduled each time, Kadota et al. [6] found that the timeaverage AoI is lower bounded by

The authors subsequently propose several optimization algorithms. The age-greedy policy is shown to be optimal in homogeneous networks when [TeX:] $$q_n=q, \forall .$$ The stationary randomized policy with optimal randomization is shown to be within 2-times the optimum. Neither greedy and stationary policy achieves as good performance as the Whittle’s index policy and Lyapunov-based max-weight policy, which are essentially identical regarding their scheduler criterion— they achieve very close-to-optimal performance in simulations, however can only be proven with loose bounds due to their non-renewal policy nature. Several other works also derive the Whittle’s index policy in different scenarios that show similarly good performance, and again, without theoretical optimality guarantees [7], [8]. A recent work by Maatouk et al. [9] proved that Whittle’s index policy is asymptotically optimal, when the number of scheduled users scales with the total number of users and they both go to infinity. Talak et al.showed that the stationary randomized policy is peak-AoI optimal even in a general network topology, wherein peak-AoI denotes the AoI right before delivery [10].

The majority of existing AoI research focuses on the case with complete channel state information. However, in real- world communication systems, these are challenging to meet. Ref. [11] and [12] consider the AoI minimization problem for a network with general interference constraints and time varying channels, with perfect CSI and unknown channel state, respectively. The case with perfect CSI demonstrates a significant age improvement compared to the case with unknown channel state. Ref. [13] proposes a scheduling policy for heterogeneous and unreliable multi-channel systems where the channel states are unknown when scheduling decisions are made. Ref. [14] studies the minimum-age scheduling problem, wherein AoI is not directly observable to the scheduler, and proposes a policy that is an approximation to the greedy policy. Ref. [15] analyzes a class of information freshness metrics in the setting where a large number of terminals access the channel via a slotted ALOHA (SA) policy and each wireless user-sink link is modelled as a Gilbert-Elliot channel. A relevant work is presented in [16] and [17]. The work in [16] derives the Whittle index for AoI minimization in a system having iid/Markovian channels and multiple information settings (without CSI/ with CSI/ delayed CSI). Ref. [17] analyzes three scenarios with an i.i.d. ON-OFF channel, namely systems without CSI, systems with CSI, and systems with partial CSI, and derives the corresponding Whittle index-based scheduling policies. Nevertheless, neither of these two papers considers the AoI minimization problem in the scenario with Markov channels and partial CSI, and it has not been demonstrated theoretically that the given policies can achieve optimal performance.

Summarizing existing works, four key problems still remain to be solved. P1: Is the lower bound in (1) tight or at least asymptotically tight? What policy can be proved to achieve the optimum? P2: Most works focus on AoI scheduling policy design but analytical results are less available. How to analyze the AoI performance of scheduling policies? P3: Considering practical signaling concerns, how to decentralize the scheduler operation? P4: In a time-varying channel environment, how to design a scheduling policy. Which percentage of CSI should be known to achieve optimum?

B. Our Contributions

In this paper, we address P1–P4 by adopting the fluid limits approach. Our contributions include:

· We demonstrate that the AoI occupancy measure of a broad range of threshold-based policies with a large number of users converges to a fluid limit. This limit is expressed as a partial derivative equation (PDE). We also prove that the PDE has a globally stable equilibrium point, which can be used to describe the stationary distribution of AoI.

· We demonstrate that the lower bound in (1) is asymptotically accurate, and a straightforward threshold-based policy can achieve the optimal result, with the thresholds explicitly determined from the fluid limits. We also derive the AoI probability distribution function under the threshold-based policy, which allows us to quickly calculate AoI statistics such as moments and tail distribution.

· We further investigate the age performance of wireless multiaccess networks with time-varying channels. By utilizing partial CSI available at the start of each time slot, we derive the optimal thresholds and long-term average AoI. Our theoretical and experimental results demonstrate that optimal AoI performance can be achieved even with only a limited amount of channel state information.

C. Organization

The rest of the paper is organized as follows. In Section II, an illustration example is given to highlight the idea of fluid limits. Section III introduces the system model and modeling language. Section IV lays down the mathematical tool that is used. Section V and VI use the tool to analyze the timeinvariant and time-varying channel, respectively. The simulation results are shown in Section VII. Finally, in Section VIII, conclusions are drawn with future work discussed.

II. ILLUSTRATING EXAMPLE OF AOI FLUID LIMITS

Consider a network of N users where each user is scheduled with a constant rate of μ, and the scheduling events happen based on a Poisson process in continuous time. The transmission is reliable. Fig. 1 shows an exemplary occupancy measure of AoI at a certain time t, which is assumed to admit a probability distribution function. Assume that the system is in equilibrium and let us consider the balance equation of age flows, the left-hand side of which represents the expected inflow to a specific AoI h during a time duration of dh, and the right-hand side the expected out-flow from h:

The in-flow denotes the aging from h−dh, and the first term of the out-flow is due to aging from h. The second term of out-flow represents the expected amount of agents that are scheduled and returns to AoI of zero. This formulation resembles fluids flow in continuous time and the dynamic is characterized by an Ordinary Differential Equation (ODE). When dh is sufficiently small, we obtain

The initial condition is obtained by considering the flow at h = 0. This yields a solution which reads

Alternatively, one can solve for the solution of an embedded Markov chain describing the evolution of AoI and obtain the exactly same AoI stationary distribution, which is omitted here due to brevity. The rationality of this fluid approach is that, with growing number of agents, one expects that the law of large numbers takes effect, such that the expected flow in (2), which takes expectation in the probability sense, coincides with the actual fraction of agents that are scheduled. This is called the fluid limits. Consequently, the calculation of AoI statistics follows immediately.

Three key questions exist in applying this idea. Q1: What are the conditions allowing the limiting ODE or PDE (partial DE), as well as its equilibrium, to exist? Q2: In this example, the expected scheduled agents per time unit is [TeX:] $$\mu N$$ which also goes to infinity. In practice, it is more reasonable to consider a finite number of scheduled agents. Does the fluid limit also exist? Q3: Can we use this to solve particular problems in AoI? In following sections, we endeavor to answer these questions. which also goes to infinity. In practice, it is more reasonable to consider a finite number of scheduled agents. Does the fluid limit also exist? Q3: Can we use this to solve particular problems in AoI? In following sections, we endeavor to answer these questions.

III. FLUID LIMIT MODELING LANGUAGE FOR AOI

In this section, fluid limit modeling specifications for AoI evolution of many users (hereinafter we use agents) are introduced, which are described in a general setting such that they can be adopted in as many scenarios as possible. We first describe a continuous time Markov chain (CTMC)-based formulation, which is also known as the Markov processes of pure jump type. However, this formulation is problematic in considering the convergence of the AoI occupancy measure. Therefore, it is transformed to a rescaled time domain. Connections to the widely-used discrete time Markov chain (DTMC)-based AoI model [ 6], [ 18], which is inconvenient to apply the fluid limits, are also discussed.

A. Multi-Class CTMC-Based AoI Model

We assume that agents in the system belong to a finite number of classes, which are prescribed based on their features, e.g., channel conditions, packet arrival patterns, performance metrics. Agents within each class are considered exactly the same and hence interchangeable, i.e., agents having identical state evolution dynamics. In practice, this assumption can be relaxed to be approximately the same. The total number of agents and classes are denoted by N and C respectively, with [TeX:] $$N_c$$ denotes the total number of agents in class-c, hence [TeX:] $$\sum_{c=1}^C N_c=N .$$ The evolution of the system is captured by a CTMC, which is described as follows.

Definition 1: A CTMC model for AoI is a tuple [TeX:] $$\mathcal{H}=\left(\boldsymbol{H}, \mathcal{T}, \boldsymbol{d}_0\right),$$ where:

1) [TeX:] $$\boldsymbol{H}=\left(\boldsymbol{h}_1, \cdots, \boldsymbol{h}_C\right)$$ denotes the vector of AoI of N terminals categorized by C classes, wherein [TeX:] $$\boldsymbol{h}_c=\left(h_{c, 1}, \cdots, h_{c, N_c}\right).$$ Each [TeX:] $$h_{c, i}$$ takes value in [TeX:] $$\mathbb{R}_{\geq 0} . \boldsymbol{d}_0 \in \mathbb{R}_{\geq 0}$$ is the initial state of the model.

2) [TeX:] $$\mathcal{T}=\left\{\tau_1, \cdots, \tau_M\right\}$$ denotes the set of transitions of the form [TeX:] $$\tau_j=(a, \phi(\boldsymbol{H}), \boldsymbol{v}(\boldsymbol{H}), r(\boldsymbol{H})),$$ where:

a) The label of the transition is denoted by a.

b) [TeX:] $$\phi(\boldsymbol{H})$$ denotes the set of inequalities that need to be satisfied by the transition, indicating the conditions that such a transition happens. c) The update vector is denoted by [TeX:] $$\boldsymbol{v}(\boldsymbol{H}) \in \mathbb{R}^N,$$ representing the net change on the state by the transition. It is required that [TeX:] $$\boldsymbol{H}+\boldsymbol{v}(\boldsymbol{H}) \in \mathbb{R}_{\geq 0}$$ whenever [TeX:] $$\phi(\boldsymbol{H})$$ is true. d) The transition rate function is denoted by [TeX:] $$r(\boldsymbol{H}):\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0},$$ which specifies the transition as a function of the current state and is required to be Lipschitz continuous and bounded in general. The time interval between successive transitions is assumed to be exponentially distributed with rate [TeX:] $$r(\boldsymbol{H}).$$

This definition is described in a quite general way. To give a concrete example, let us consider an AoI scheduling problem based on the Whittle’s index [7], [8], wherein the index for agent-n at time-t is [TeX:] $$w_n(t)$$ and the agent with the highest index is scheduled at every time slot. The transmission is assumed to be successful with probability [TeX:] $$p_{\mathrm{s}} \in(0,1]$$ due to channel error, and in the case of success, the AoI decreases to zero. The mean time interval between successive scheduling events is set to [TeX:] $$1 / r_0.$$ The corresponding transitions can be described as (using agent-1 as a representative):

1) [TeX:] $$\tau_1$$ = (Scheduled and successful update, [TeX:] $$w_1(t)\gt \left.w_i(t)(\forall i \neq 1),\left(-h_{1,1}(t), \Delta(t), \cdots, \Delta(t)\right), p_{\mathrm{s}} r_0\right);$$

2) [TeX:] $$\tau_1$$ = (Scheduled and unsuccessful update, [TeX:] $$w_1(t) \gt \left.w_i(t)(\forall i \neq 1),(\Delta(t), \cdots, \Delta(t)),\left(1-p_{\mathrm{s}}\right) r_0\right) \text {, }$$

where [TeX:] $$\Delta(t)$$ denotes the time elapsed since the last scheduling event.

Define the occupancy measure among all agents, with AoI of [TeX:] $$\boldsymbol{H}(t)$$ in class-c by

where [TeX:] $$\delta_y(x)$$ denotes the Dirac delta distribution which is a linear mapping: [TeX:] $$D(\mathbb{R}) \rightarrow \mathbb{R}$$ that satisfies [TeX:] $$\int \delta_y(x) f(x) \mathrm{d} x=f(y) \text { and } D(\mathbb{R})$$ denotes the set of test functions. Denote the faction of agents that are in class c and with AoI lower than h as

Remark 1: One critical issue of this formulation, making it inapplicable for the fluid limits, is that when the system size grows large, i.e., N is large, the resultant occupancy measure of agents’ AoI is not tight (definition of tightness of measure is given in (27)), in fact it has support approaching infinity, and therefore not convergent to any probability measure. This shall be made evident in the proof of the main theorem. To address this, a time-rescaled CTMC formulation is introduced as follows.

B. Transformation to Rescaled CTMC

Definition 2: A time-rescaled CTMC model for AoI is a tuple [TeX:] $$\hat{\mathcal{H}}=\left(\hat{\boldsymbol{H}}, \hat{\mathcal{T}}, \hat{\boldsymbol{d}_0}\right),$$ which is defined identically with Definition 1, except that [TeX:] $$\hat{r}(\boldsymbol{H})=N r(\boldsymbol{H}), \forall \boldsymbol{H} .$$ In essence, [TeX:] $$\hat{\mathcal{H}}$$ can be viewed as an accelerated version of [TeX:] $$\mathcal{H},$$ in the sense that time intervals between scheduling events are scaled down with the number of agents. By a stochastic coupling argument, it is clear that the following lemma is true because everything happens sooner.

Lemma 1: The occupancy measure of [TeX:] $$\hat{\mathcal{H}}$$ satisfies

and consequently, if [TeX:] $$\hat{X}_{c, t}^N(h)$$ converges weakly to a probability measure [TeX:] $$\hat{x}_{c, t}(h)$$ with [TeX:] $$N \rightarrow \infty$$ (later formalized), the mean AoI of [TeX:] $$\hat{\mathcal{H}} \text { (i.e., } \mathbb{E}[\hat{h}] \text {) and } \mathcal{H} \text { (i.e., } \mathbb{E}[h] \text {) }$$ satisfy

Fortunately, by this definition, we can prove in many practical cases the occupancy measure [TeX:] $$\hat{X}_{c, t}^N(h)$$ is tight in the fluid limit regime, and hence converges weakly to a continuous probability measure, which facilitates our subsequent analysis.

On the flip side, by making this time rescaling, we are unable to analyze the AoI exactly. As we shall see in the next section, by adopting the fluid limit approximation, the approximation error is [TeX:] $$\mathcal{O}(1 / N).$$ Combined with (8), it is clear that we can only solve for the linear scaling factor with N, i.e., asymptotic optimality—which is sufficient in many cases because AoI indeed scales linearly with N, and when N gets large, the error becomes infinitesimal.

C. Connection with DTMC Formulation

In most previous works on AoI scheduling, e.g., [6], [8], [9], [18], the AoI evolution is modeled by a DTMC. In this paper, we adopt CTMC, whereas it is desired to draw the connection between them. In fact, the DTMC can be viewed as the embedded DTMC of the CTMC. More specifically, denote the infinitesimal generator matrix [TeX:] $$Q \text { of } \mathcal{H}$$ as

and set the transition rate out of each state to one, i.e., the mean scheduling interval is 1, that is

Leveraging the rescaling technique, we obtain [TeX:] $$\hat{\mathcal{H}}.$$ The total number of update attempts (i.e., scheduling events) with rescaled CTMC is hence [TeX:] $$\mathcal{N}(t N)$$ where [TeX:] $$\mathcal{N}$$ is a Poisson random variable with mean rate of [TeX:] $$r_{-\boldsymbol{H}},$$ and the number is [TeX:] $$\lfloor t N\rfloor$$ for the DTMC. We obtain

which is attributed to the law of large numbers. In other words, this equation shows that by adjusting the rate functions of CTMC, with N growing large, the same number of scheduling events have happened for both CTMC and DTMC at any time t, making them statistically equivalent. Using the uniformization technique [19] can also leads to this conclusion.

IV. DETERMINISTIC FLUID LIMIT OF AOI AND STATIONARY REGIME

In this section, we develop our main result on the fluid limit of AoI based on the time-rescaled CTMC model. We consider a specific but widely-adopted type of scheduling policies for AoI, which is threshold-type policies. In particular, we assume

1) At every scheduling event, one agent ¹ is randomly chosen from the agents with AoI greater than their (possibly different) thresholds with equal probabilities. In the case of no agent has AoI above its threshold, the system stays idle. ¹ Generalization to a finite number of agents is straightforward. However, an infinite number of scheduled agents [ 9], [ 20] needs a different formulation.

2) Agents in each class have the same threshold [TeX:] $$H_c.$$

Note that the threshold-type policy is adopted by many papers [9], [21]–[23]. It is both intuitive, in the sense that AoI higher than a threshold should be prioritized, and proven optimal in many scenarios. However, usually the exact thresholds cannot be solved explicitly. In fact, we will show that even in scenarios wherein threshold-type polices are not considered optimal, and index-based policies [6]–[8] have superior performance, an optimized threshold-type policy can achieve asymptotically optimal AoI with proven and closedform performance expressions.

A. Fluid Limit

When N gets large, the evolution of the time-rescaled CTMC becomes close to a deterministic fluid limit, characterized by differential equations.

Theorem 1: Assume that the initial occupancy measure c converges weakly to a deterministic distribution [TeX:] $$\hat{\boldsymbol{x}}_0$$ which admits a density [TeX:] $$\left\{\hat{f}_{c, 0} \mid c=1, \cdots, C\right\} .$$ Then as N approaches infinity, [TeX:] $$\hat{X}_{c, t}^N$$ of each class converges in distribution to a deterministic fluid limit processes [TeX:] $$\left\{\hat{x}_{c, t} \mid t \in \mathbb{R}_{\geq 0}\right\}$$ which admits a density for all t denoted by c and CDF by [TeX:] $$\hat{F}_c(t, h),$$ is the unique solution of the following PDE:

where [TeX:] $$\eta_c=N_c / N.$$

Proof: The proof is based on previous works on fluid limits and mean-field approximations [24]–[27]. First, define the characteristic function, i.e., [TeX:] $$\\varphi_{\hat{H}, c}^N(\omega, t): \mathbb{R} \times \mathbb{R}_{\geq 0} \rightarrow \mathbb{C},$$ of the occupancy measure as

For ease of notation, we use [TeX:] $$\varphi_c^N(t) \text { for } \varphi_{\hat{H}, c}^N(\omega, t).$$ Note that by definition and (5)–(7), [TeX:] $$\varphi_c^N(t)=\frac{1}{N} \sum_{i=1}^{N_c} e^{j \omega h_{c, i}(t)},$$ which is the sample average. Consider the generator of [TeX:] $$\varphi_c^N(t)$$:

where [TeX:] $$\mathcal{F}_t$$ is the natural filtration of [TeX:] $$\hat{X}_{c, t}^N(h) .$$

Lemma 2: Define

then [TeX:] $$M_t^N$$ is a zero-mean [TeX:] $$\mathcal{F}_t$$-martingale.

Proof: For any t > s,

The mean follows directly from the definition.

Then we calculate [TeX:] $$\mathcal{G}\left(\varphi^N(t)\right)$$ specifically as:

wherein [TeX:] $$\Lambda(N, \mathrm{~d} t)$$ denotes a Poisson distributed random variable with rate N and time of dt, and [TeX:] $$N_{h_t>H_c}$$ denotes the number of agents in class c that have AoI larger than the threshold. The last equality in (20) is because when [TeX:] $$\mathrm{d} t \rightarrow 0,$$ the Poisson distributed [TeX:] $$\Lambda(N, \mathrm{~d} t)$$ is closely approximated by a Bernoulli random variable with parameter c. The calculation above derives the expected infinitesimal change in [TeX:] $$\varphi_c^N(t).$$ Specifically, with probability [TeX:] $$\frac{p_{\mathrm{s}, c}}{\beta_t N \mathrm{~d} t}$$ which represents that an agent is chosen uniformly randomly from all eligible agents with AoI larger than their thresholds, an agent is scheduled and updates successfully with AoI returning to zero—such an event happens with a mean rate of N in the time-rescaled CTMC.

Now let us consider the quadratic variation of [TeX:] $$M_{t, c}^N.$$ The generator of [TeX:] $$\left\|\varphi_c^N(t)\right\|^2$$ is

Note that we obtain the second term in (23) as

where the last inequality follows from [TeX:] $$\beta_t\gt \frac{N_{h_t>H_c}}{N}, \forall c .$$ The term goes to zero with N getting large, i.e., define

It follows that

is also a [TeX:] $$\mathcal{F}_t$$-martingale. The following lemma establishes the limiting behavior of the occupancy measure [TeX:] $$X_{c, t}^N(h).$$

Lemma 3: When N goes to infinity, any sequence [TeX:] $$X_{c, t}^N(h)$$ has a convergent subsequence whose limit is denoted by [TeX:] $$\hat{f}_{c, t}(h), \text { and } \hat{f}_{c, t}(h)$$ has continuous sample path.

Proof: Let us first prove the tightness of [TeX:] $$X_{c, t}^N(h).$$ From [27, Lemma 4.6], it is sufficient to show the tightness of AoI measure of agent-1, i.e., [TeX:] $$\hat{h}_{c, 1}(t)=h_{c, 1}(t) / N.$$ Based on [28, Corollary 4.3], the following needs to uphold: For every [TeX:] $$\epsilon, T\gt 0,$$ there exists H > 0 such that

In the threshold-based algorithm, agent-1 is scheduled and the update is successful with a rate no less than [TeX:] $$p_{\mathrm{s}, c} / N$$ when its AoI is larger than the threshold, i.e., [TeX:] $$\hat{h}_{c, 1}(t)\gt H_c .$$ Denote [TeX:] $$T_0(t)$$ as the last time agent-1 is scheduled and the transmission is successful. Then [TeX:] $$\hat{h}_{c, 1}(t)=t-T_0(t)$$ is stochastic-dominated by a random variable [TeX:] $$\hat{h}^{\prime}=H_c+\hat{z}$$ where [TeX:] $$\hat{z} \sim \exp \left(p_{\mathrm{s}, c}\right)$$ (in the rescaled time domain) because the scheduling event happens with a rate of N. Therefore,

Letting the right-hand side be larger than [TeX:] $$1-\epsilon$$ gives us the conclusion that [TeX:] $$X_{c, t}^N(h)$$ is tight. Then based on the Prokhorov’s Theorem, [TeX:] $$X_{c, t}^N(h)$$ is relatively tight, which means that for any sequence [TeX:] $$X_{c, t}^N(h)$$, there exists a subsequence that is convergent. Let us denote such a subsequence by [TeX:] $$X_{c, t}^{N_k}(h) .$$ Consider its characteristic function,

When the time changes from t to t + dt, the change in characteristic function is

Choose an arbitrary [TeX:] $$\varepsilon \gt 0.$$ Based on (27), choose H so large that [TeX:] $$\operatorname{Pr}\left(\hat{h}_{c, 1}(t)\gt H\right)\lt\frac{\varepsilon}{4},$$ and [TeX:] $$N_k\gt \frac{4 H}{\varepsilon},$$ then

The last inequality is based on the fact that the jump of [TeX:] $$X_{c, t}^{N_k}(h)$$ in a small time interval is at most [TeX:] $$\frac{\delta_x}{N_k}.$$ This concludes the proof.

Now we know that any sequence [TeX:] $$X_{c, t}^N(h)$$ has a convergent subsequence with continuous sample path. Let us see if such a limit, i.e., [TeX:] $$\hat{f}_{c, t}(h),$$ is uniquely determined. It follows from (26) that when N is large,

Applying the Ito’s formula to [TeX:] $$f\left(\varphi_c^{\infty}(t)\right)$$ wherein [TeX:] $$f(x)=x^2$$ is twice continuously differentiable and [TeX:] $$\varphi_c^{\infty}(t)$$ is a continuous semimartingale, we obtain

wherein [TeX:] $$\langle X(t)\rangle \triangleq \lim _{\|P\| \rightarrow 0} \sum_{k=1}^n\left(X_{t_k}-X_{t_{k-1}}\right)^2$$ denotes the quadratic variation of X(t) and [TeX:] $$P \triangleq \sup _k\left|t_k-t_{k-1}\right| .$$ Comparing (32) and (33), and by the uniqueness of the Doob–Meyer decomposition, we know that

Based on the definition,

Therefore [TeX:] $$M_{s, c}^{\infty}$$ is a zero-mean martingale with zero variance, hence it is zero almost surely. Thus we obtain

Take the inverse characteristic function transform and derivative with t on both ends, we obtain exactly the PDE in (12). Based on the Cauchy-Lipschitz theorem, (12) has one unique solution. Because any solution of (36) must also satisfy (12), hence [TeX:] $$\hat{f}_{c, t}(h)$$ is uniquely determined. Based on the following corollary of the Prokhorov’s theorem, we have concluded the proof.

Lemma 4: If [TeX:] $$\mu_n$$ is a tight sequence of probability measure such that every weakly convergent subsequence [TeX:] $$\mu_{n_k}$$ has the same limit μ, then the sequence [TeX:] $$\mu_n$$ converges weakly to μ.

The intuition behind (12) is clear. As the time passes, the AoI gets larger which is denoted by the first term on the righthand side of the equation. When the AoI is below the threshold of this class, the agents are never scheduled, resulting in the bottom equation; otherwise, the agents with AoI higher than the threshold are scheduled and flow back to zero AoI with rate the proportional between the number of agents with this AoI and the total number of agents with AoI beyond their individual thresholds.

B. Stationary Regime

In (12), the AoI distribution and evolution of the system is characterized by a PDE. Let us first search for its solution. Define [TeX:] $$\hat{g}_c(x, y) \triangleq \hat{f}_c(x+y, x),$$ wherein we use the change of variable x = h and y = t − h.

Therefore the PDE in (12) is rewritten as

wherein [TeX:] $$\hat{G}_c(x, y) \triangleq \int_0^x \hat{g}_c(s, y) \mathrm{d} s .$$ The derivative of [TeX:] $$\hat{g}_c(s, y)$$ is hence shown to be only related to x and y affects the initial conditions for various x. This helps us to derive the solution of (12). The following theorem describes the limiting behavior of AoI.

Theorem 2: With probability 1, when [TeX:] $$t \rightarrow \infty,$$ the solution of (12) converges to a globally-stable equilibrium that is irrelevant with t and [TeX:] $$\hat{f}_{c, 0},$$ which reads

wherein β is the unique positive solution of

with [TeX:] $$\sum_{c=1}^C \frac{\eta_c}{\hat{H}_c p_{\mathrm{s}, c}}\gt1.$$

Proof: First, we will show that the system enters the stage wherein y = t−h > 0 eventually with probability one. Denote [TeX:] $$\hat{H}_{\mathrm{m}}=\max _c\left\{\hat{H}_c\right\}$$ and [TeX:] $$p_{\mathrm{m}}=\min _c\left\{p_{\mathrm{s}, c}\right\}.$$ Then for [TeX:] $$t\gt \hat{H}_{\mathrm{m}},$$ every agent successfully transmits an update with a rate no less than [TeX:] $$p_{\mathrm{m}}.$$ Denote the first time agent-i transmits an update successfully as [TeX:] $$t_{i, 0},$$ then [TeX:] $$\forall T\gt 0,$$

which approaches 1 with large T. After [TeX:] $$\hat{t}_{i, 0}$$, AoI returns to zero and we have t > h for every [TeX:] $$t\gt \hat{t}_{i, 0}$$ afterwards.

Therefore, with probability one, the solution of (38) converges to one given by the initial condition (40) with y > 0. Solving that gives

where [TeX:] $$\kappa_c=\frac{\eta_c-\hat{G}_c\left(\hat{H}_c, y\right)}{1-\sum_{j=1}^C \hat{G}_j\left(\hat{H}_j, y\right)} p_{\mathrm{s}, c}, \forall c .$$ Note that

Denote [TeX:] $$\beta=1-\sum_{j=1}^C \hat{G}_j\left(\hat{H}_j, y\right)\gt 0$$ as the total fraction of agents with AoI larger than thresholds, then

Observing (41), it follows that [TeX:] $$\nu(0)=0, \nu(\infty)=\infty,$$ and

Hence as long as [TeX:] $$\nu^{\prime}(0)=1-\sum_{c=1}^C \frac{\eta_c}{\hat{H}_c p_{s_s, c}}$$ is strictly negative, there is a unique positive solution of (41); otherwise there is no positive solution. This concludes the proof.

The equilibrium also satisfies the traditional equation

which gives the exact same solution as in (41). It is not difficult to check the local-stability of the solution.

Proposition 1: For every [TeX:] $$\epsilon \gt 0,$$ there exists [TeX:] $$\delta \gt 0,$$ such that, if [TeX:] $$\left\|\hat{f}_{c, 0}(h)-\hat{d}_c(h)\right\|\lt \delta,$$ then for every [TeX:] $$t \geq 0, \| \hat{f}_{c, t}(h)-\hat{d}_c(h) \|\lt\epsilon,$$ i.e., the equilibrium [TeX:] $$\hat{d}_c(h)$$ is asymptotically stable in the local sense.

Proof: Let us check the Jacobian matrix [TeX:] $$\boldsymbol{J}\left(\hat{d}_c(h)\right) \in \mathbb{H} \times \mathbb{H}$$, where [TeX:] $$\mathbb{H}$$, is a Hilbert space with inner product defined as [TeX:] $$\langle f, g\rangle=\int_{\hat{S}} f(x) g(x) \mathrm{d} x.$$ In this case [TeX:] $$J\left(\hat{d}_c(h)\right)$$ is a the derivative of the right-hand side of (12) with respect to [TeX:] $$\hat{f}_c(t, h),$$ taken on the value of [TeX:] $$\hat{d}_c(h)$$:

with the only eigenvalue being [TeX:] $$-\frac{p_{\mathrm{s}, c}}{1-\sum_{c=1}^C \hat{F}_j\left(t, \hat{H}_j\right)} \kappa_c$$ which is strictly negative. Therefore, we can conclude that the equilibrium is locally asymptotically stable based on the Hartman–Grobman Theorem [29].

V. AOI IN TIME-INVARIANT CHANNELS

Next, to compare with the time-varying channels scenario, we first apply the fluid limit tool to analyze the AoI in time-invariant channels and solve a well-known but open AoI scheduling problem.

A. System Model

Consider a one-hop wireless network wherein a central node communications with N distributed agents. The agents share the wireless channel based on a scheduling policy denoted by π. First assume a time-slotted status update system is considered. Later, we will analyze it using the fluid limits which exist in the continuous time domain. The status packet generation is assumed to be generate-at-will, i.e., a fresh status for agent-n is generated whenever it is scheduled. We are interested in average AoI. Concretely, the long time-average AoI of the system is defined by

where T is the time horizon length, and [TeX:] $$h_{n, \pi}(t)$$ denotes the AoI of terminal-n at the t-th time slot under policy π. The c-th class of agents are those who transmit with a channel reliability of [TeX:] $$p_{\mathrm{s}, c} \in(0,1], c=1, \cdots, C .$$ which denotes the successful delivery probability. In each time slot, only one agent can transmit. Over time, the AoI increases by one every time slot.

Such a system model has been studied extensively in the literature [6], [8]–[10], [23]. In [6, Theorem 6], it is found that there exist a lower bound of the average AoI, i.e.,

² A slight difference with [6] is that we assume, aligned with the system model in this paper, there are a finite number of C classes of agents and, without loss of generality, each class has N/C agents. In contrast, each agent can be different in [6], i.e., C = N.

However, as far as we know, it is still an open problem whether this lower bound is (asymptotically) tight. On the other hand, several Whittle’s index based solutions, as well as Lyapunov-drift based ones which essentially gives similar algorithms and performance, have been proposed as a heuristic to solve the problem. These solutions exhibit near-optimal AoI by simulations, but only very loose performance bounds can be proved, e.g., in [6, Theorem 17], due to the non-renewal nature of the scheduler. Note that Ref. [9] considers a different scenario wherein the number of scheduled agents (i.e., M) scales with the total number of agents (i.e., N) and goes to infinity with M/N = α fixed. The authors proved asymptotic optimality without specific performance expressions.

B. Fluid Limits Results

Powered by the results in Section IV, we will solve this problem. we will show that the lower bound in (50) is indeed asymptotically tight, i.e.,

In the meantime, we will show that a threshold-based scheduling policy derived from our analysis achieves the lower bound.

Considering the scheduling policy in Algorithm 1, the following theorem is true.

Theorem 3: Algorithm 1 achieves a long time-average AoI of [TeX:] $$\bar{\Delta}_{\text {Alg. } 1} \text {, }$$ and

Proof: We apply Theorem 1 to this application. Because we are interested in the time-average AoI, it is sufficient to consider the stationary regime. With (41) and notice [TeX:] $$\int_0^{\hat{H}_c} \hat{d}_c(h) \mathrm{d} h=\hat{H}_c \kappa_c\lt \eta_c,$$ the average AoI of class-c is hence

where the right-hand-side of the inequality can be approached with [TeX:] $$\hat{H}_c^* \rightarrow \frac{\eta_c}{\kappa_c}.$$ In other words, for any [TeX:] $$\varepsilon\gt 0,$$ let [TeX:] $$\hat{H}_c^*=\frac{\eta_c-\varepsilon}{\kappa_c},$$ then [TeX:] $$\overline{\hat{h}_c}=\frac{\eta_c^2+\varepsilon^2}{2 \kappa_c}.$$ Note that with (44), the average AoI across all classes satisfies

The last inequality is based on the Cauchy-Schwarz Inequality, and the equality holds when [TeX:] $$\frac{\kappa_c^2}{\left(\eta_c^2+\varepsilon^2\right) p_{\mathrm{s}, c}}=C_0, \forall c.$$ Together with [TeX:] $$\hat{H}_c^*=\frac{\eta_c-\varepsilon}{\kappa_c},$$ we solve for the following problem:

with the solution of

Now let us check the legitimacy of the solution against the requirement [TeX:] $$\sum_{c=1}^C \frac{\eta_c}{\hat{H}_c p_{\mathrm{s}, c}}\gt 1$$ in Theorem 2. Indeed,

Because [TeX:] $$\varepsilon$$ can be arbitrarily small³ and the fluid limits bring in an approximation error of [TeX:] $$\mathcal{O}\left(\frac{1}{N}\right),$$ the AoI of Algorithm 1 is

² In the sequel, we omit [TeX:] $$\varepsilon$$ for brevity since it does not affect the result.

With [TeX:] $$\eta_c=1 / C,$$ we obtain the thresholds in Algorithm 1 and its average AoI, which concludes the proof.

Corollary 1: Algorithm 1 is asymptotically optimal.

Proof: Taking the limit [TeX:] $$N \rightarrow \infty$$ with (52) and (50), the conclusion follows immediately.

Remark 2: We would like to draw a connection of Algorithm 1 and the index policies in [6]. The Whittle’s index policy and Lyapunov drift-based max-weight policy share the same structure. They both schedule the agent with the maximum value of [TeX:] $$p_{\mathrm{s}, c} h_{c, i}^2(t),$$ with a slight difference in the linear term of [TeX:] $$h_{c, i}(t)$$ which is insignificant when AoI is large. Essentially, since only relative value is important, this is equivalent to an index of approximately [TeX:] $$\sqrt{p_{\mathrm{s}, c}} h_{c, i}(t).$$ Furthermore, this is analogues to having a clock for agenti that is scaled by [TeX:] $$\sqrt{p_{\mathrm{s}, c}} .$$ In comparison, the AoI threshold of agent-i in Algorithm 1 is [TeX:] $$\frac{1}{C \sqrt{p_{\mathbf{s}, c}}} \sum_{j=1}^C \frac{1}{\sqrt{p_{\mathbf{s}, j}}},$$ which in fact scales with AoI by the same coefficient. After all, only agents with AoI larger than the threshold are eligible for being scheduled. Hence, the connection between Algorithm 1 and index policies is very strong.

Remark 3 (Decentralized implementation): One additional merit of Algorithm 1, compared with index policies, is that it is convenient for decentralized protocols. Index policies need to compare the indices of all agents which are difficult to implement in a decentralized system setting. Fortunately, in Algorithm 1, the central node only needs to broadcast a set of thresholds which do not change over time, and agents can access the channel based upon the thresholds and a contentionbased multi-access protocol such as standard carrier-sensing multiple-access (CSMA).

VI. AOI IN TIME-VARYING CHANNELS

In this section, we will analyze the scenario wherein the wireless channels are time-varying, which are more practical.

A. System Model

Consider a one-hop wireless network which is similar with that in Section V, except for the following differences. The wireless channel is modelled as a Gilbert-Elliot channel, which is also called the burst-noise channel. At the end of each time slot, the wireless channel is either in a good or bad state with different transmission success probabilities, i.e., the state of the wireless channel is time-varying. The agents with a good wireless channel state can successfully deliver the status packet with a probability [TeX:] $$p_{\mathrm{s}, \mathrm{G}} \in(0,1],$$ whereas the transmission would be erased while having a bad wireless channel state, i.e., [TeX:] $$p_{\mathrm{s}, \mathrm{B}}=0 .$$ In more general terms, the channel state transition process can be described by a Markov chain which has two states: Good and Bad. Therefore, the agents can transfer from one class to another over time. The transfer probability between different channel states can be denoted by [TeX:] $$\rho_{c, c^{\prime}} .$$ In the continuous-time domain, it represents the transfer rate per unit time. Moreover, as N approaches infinity, the transition process between each class reaches stability, i.e.,

In the rescaled time domain, the rescaled transfer rate is

The transfer rate also reflects the time-varying extent of the wireless channel. For example, in the high-speed mobile communication scenario, it is obvious that the value of the transfer rate is relatively large. While in the almost static communication scenario such as indoor environment, the transfer rate can be regarded as close to 0. When the transfer rate is [TeX:] $$\hat{\rho}_{c, c^{\prime}}=0, \forall c \neq c^{\prime}$$ and all channel states are known, and this is the scenario considered in the Section V. Therefore, the system model in the Section V can be regarded as a special case of the system model in this Section.

To analyze the effects of only knowing part of the CSI on the overall performance, assume we have partial CSI at the beginning of each time slot. By combining the previous conditions, the agents can be classified into two classes: ones with good channel status and with bad channel status. In more details, each class of agents is divided into two parts: those with known channel states and with unknown channel states.

B. Fluid Limits Results

Taking into account the above time-varying channel conditions, the PDE (12) can be rewritten as:

The initial conditions are the same as (14). Compared with (12), there is an additional term of [TeX:] $$\hat{e}_c$$ which greatly increases the complexity of the PDE. In (62), the first term stems the proportion of agents transferred from c-th class to other classes, and the second term stems the proportion of agents transferred from other classes to c-th class.

Powered by the results in Section IV-B, when time goes to infinity, the above PDE also exists a stationary regime, i.e., an equilibrium point of the PDE which is locally stable and [TeX:] $$\hat{f}_c(t, h)$$ satisfies (47). In this regard, the PDE can be simplified to an ODE. In the following, we will discuss the detailed PDEs in general scenarios. For extreme scenarios, such as the PDE where all channel states are unknown or all channel states are known, it can be derived from the general scenario, that is, a simplified special form.

1) Partially known channel states:

In the general scenario, i.e., partial channel states are known, the agents are divided into three classes: good, bad and unknown, which are respectively indexed by [TeX:] $$c=1, \cdots, 3.$$ It is worth noting that in this case, all packets delivered by agents with bad channel state are always erased. Therefore, for a class of agents with bad channel state, the optimal threshold should be [TeX:] $$\hat{H}_2=\infty .$$ The ratio of the number of agents with known channel states to the total number of agents is denoted by [TeX:] $$\gamma \in(0,1).$$ Note that, agents of unknown channel states, however, are still either with good or bad channels physically, therefore the actual ODE is as follows:

where [TeX:] $$M_1=\gamma \hat{F}_1\left(\hat{H}_1\right), M_2=(1-\gamma) \hat{F}_1\left(\hat{H}_3\right), M_3=(1-\gamma) \hat{F}_2\left(\hat{H}_3\right),$$ and [TeX:] $$M_4=\gamma \hat{F}_2\left(\hat{H}_2\right)=\gamma \eta_2.$$

Solving this ODE, we obtain the solution of (65) at [TeX:] $$0 \leq h \leq \hat{H}_1$$

where [TeX:] $$\hat{\rho}^{\prime}=\left(\hat{\rho}_{1,2}+\hat{\rho}_{2,1}\right),$$ and

Note with (59) and (60), as [TeX:] $$N \rightarrow \infty,$$ we have [TeX:] $$\hat{\rho}_{c, c^{\prime}} \rightarrow \infty$$ and [TeX:] $$\frac{\hat{\rho}_{2,1}}{\hat{\rho}_{1,2}+\hat{\rho}_{2,1}}=\eta_1, \frac{\hat{\rho}_{1,2}}{\hat{\rho}_{1,2}+\hat{\rho}_{2,1}}=\eta_2 \text {, }$$ then for (66), we have

Next, we obtain the solution of (65) at [TeX:] $$\hat{H}_1\lt h \leq \hat{H}_2$$

where

Given γ, as [TeX:] $$N \rightarrow \infty,$$ we have [TeX:] $$\Upsilon_2 \rightarrow \infty,$$ and [TeX:] $$\lim _{N \rightarrow \infty} Q=\hat{\rho}_{1,2}+\hat{\rho}_{2,1},$$ then for (69), we have

Similarly, as [TeX:] $$N \rightarrow \infty,$$ we obtain the solution of (65) at [TeX:] $$h>\hat{H}_3$$

Considering the aforementioned conditions and the scheduling strategy in Algorithm 2, the following theorem is true.

Theorem 4: In a partially observable time-varying channel environment, i.e., [TeX:] $$\gamma \in(0,1),$$ Algoritnm 1 achieves a long time-average AoI of [TeX:] $$\bar{\Delta}_{\mathrm{Alg} .1} \text {, }$$ and

Proof: According to

it gives [TeX:] $$\hat{H}_1\lt \frac{1}{\kappa_1+\kappa_2}.$$ There exists an arbitrary [TeX:] $$\varepsilon\gt 0,$$ let [TeX:] $$\hat{H}_1^*=\frac{1-\varepsilon}{\kappa_1+\kappa_2},$$ then [TeX:] $$\left(1-\sum_{j=1}^4 M_j\right) \rightarrow 0,$$ thus [TeX:] $$\hat{f}_1(h) \rightarrow 0,$$ [TeX:] $$\hat{f}_2(h) \rightarrow 0 \text { at } h\gt \hat{H}_1 \text {. }$$ Therefore, the average AoI of each class is

and the average AoI across all classes satisfies

With [TeX:] $$\frac{\kappa_1}{p_{\mathrm{s}, \mathrm{G}}}+\frac{\kappa_2}{p_{\mathrm{s}, \mathrm{B}}}=1, \kappa_1 \geq 0, \kappa_2 \geq 0,$$ then

It is obvious that [TeX:] $$\overline{\hat{h}} \geq 0 \text {. }$$ Since [TeX:] $$p_{\mathrm{s}, \mathrm{B}}=0 \text {, }$$ to minimize [TeX:] $$\hat{h} \text {, }$$ then [TeX:] $$\kappa_1$$ should be maximized or [TeX:] $$\kappa_2$$ should be minimized, i.e.,

According to (67), the above equation holds when [TeX:] $$\hat{H}_3=\infty,$$ then

Because [TeX:] $$\varepsilon$$ can be arbitrarily small and the fluid limits bring in an approximation error of [TeX:] $$\mathcal{O}(1 / N),$$ the AoI of Algorithm 1 is

2) Known all channel states:

In the case where all channel states are known, i.e., γ = 1, there are only two classes of agents: Good and Bad, and the ODE is

where [TeX:] $$M_1=\hat{F}_1\left(\hat{H}_1\right) \text {, and } M_2=\hat{F}_2\left(\hat{H}_2\right)=\eta_2 \text {. }$$

Considering the aforementioned conditions and the scheduling strategy in Algorithm 3, the following theorem is true.

Theorem 5: In the fully observable time-varying channel environment, i.e., γ = 1, Algorithm 3 achieves a long time-average [TeX:] $$\text { Aol of } \bar{\Delta}_{\text {Alg. } 3} \text {, and}$$

Proof: The proof procedure is similar to the case where partial channel states are known, and is simpler since [TeX:] $$\kappa_2=0.$$ For the sake of brevity, the specific proof procedure is omitted.

3) Unknown all channel states:

In the case where all channel states are unknown, i.e., γ = 0. there are only one classes of agents: Unknown, and the ODE is

where [TeX:] $$M_1=\hat{F}_1(\hat{H}) \text {, and } M_2=\hat{F}_2(\hat{H}).$$

Considering the aforementioned conditions and the scheduling strategy in Algorithm 4, the following theorem is true.

Theorem 6: In the blind time-varying channel environment, i.e., γ = 0, Algorithm 4 achieves a long time-average AoI of [TeX:] $$\bar{\Delta}_{\text {Alg. } 1},$$ and

Proof: In this case, the other partial proof procedures are similar to the case where partial channel states are known, but (77) is different, and the specific process is as follows. According to (74),

Since

and [TeX:] $$\frac{\kappa_1}{p_{\mathrm{s}, \mathrm{G}}}+\frac{\kappa_2}{p_{\mathrm{s}, \mathrm{B}}}=1, \kappa_1 \geq 0, \kappa_2 \geq 0,$$ then

Therefore, (77) can be rewritten as

With [TeX:] $$p_{\mathrm{s}, \mathrm{B}}=0 \text {, }$$ the optimal threshold is

Because [TeX:] $$\varepsilon$$ can be arbitrarily small and the fluid limits bring in an approximation error of [TeX:] $$\mathcal{O}\left(\frac{1}{N}\right),$$ the AoI of Algorithm 1 is

Combined with the previous analysis, it is evident that the following inference holds.

Remark 4: In a partially observable time-varying channel scenario, by applying Algorithm 2, the optimal AoI performance is almost the same as when all channel states are known as long as a fraction of the channel states are known. That is, when γ > 0, the optimal threshold and the optimal long-time average AoI are independent of γ. This is intuitive since we only schedule agents with good channel states, and for those with bad or unknown channel states, it is better to wait until the channel state is known to be good.

VII. SIMULATIONS

In this section, we provide the simulation results corresponding to the analysis in Section V and Section VI. The simulation results are discussed in two parts: AoI in timeinvariant channels and AoI in time-varying channels, respectively.

A. AoI in Time-Invariant Channels

About the AoI in time-invariant channels, computer simulations are conducted. Two classes of agents (equal number of agents in each class) are tested, with [TeX:] $$p_{\mathrm{s}, \mathrm{G}}=0.9 \text { and } p_{\mathrm{s}, \mathrm{B}}=0.2$$ respectively. In Fig. 2, the convergence of empirical CDF of rescaled AoI to the limiting equilibrium of (41) based on applying Algorithm 1 is shown. The initial AoI distribution is generated based on a Gaussian distribution with mean of N/2 and variance N. The simulation is ran in slotted time domain and lasts for [TeX:] $$10^6$$ time slots. Each slot corresponds to a scheduling event in CTMC. It is observed that when N grows, the match between empirical and theoretical CDF results by fluid limits is evident. Note that it takes longer to converge with larger N because our rescaled AoI requires the time is accelerated by a factor of N, which can be seen by comparing the (2, 2) and (3, 2) figures. In Fig. 3, we also compare the time-average AoI performance of Algorithm 1, the Whittle’s index approach [6] and the theoretical fluid limits (without the [TeX:] $$\mathcal{O}(1)$$ term and thus is also the AoI lower bound in (50)). It is found that the three are very close to each other. Note that Theorem 3 gives the performance of Algorithm 1 within an error term of [TeX:] $$\mathcal{O}(N)$$, but the error can still be dependent on N with lower order than 1, e.g., [TeX:] $$\mathcal{O}(\sqrt{N})$$—this explains the widened gap when N grows.

B. AoI in Time-Varying Channels

About the AoI in time-varying channels, computer simulations are conducted in two scenarios: known partial channel states and unknown all channel states. To facilitate the analysis, in both cases, considering the same number of agents for both Good and Bad classes, we show the theoretical PDF of the rescaled AoI and a comparison of the empirical and theoretical CDFs of the rescaled AoI.

1) Known partial channel states:

In Fig. 4, to better represent the variation details of AoI, we show the theoretical PDF of rescaled AoI when N = 2000, [TeX:] $$\rho_{c, c^{\prime}}=0.1, \gamma=0.1, p_{\mathrm{s}, \mathrm{G}}=1, \hat{H}_1=0.5, \hat{H}_2=1.5.$$ It is shown that the PDFs of the two classes of agents have different initial values at h = 0, but as h increases, a transfer process occurs between different classes of agents due to the characteristics of the time-varying channel, and the transfer rate tends to infinity in the rescaled time domain. Therefore, the PDFs of the two classes of agents rapidly converge to steady state. Starting from [TeX:] $$h=\hat{H}_1,$$ the PDFs of both classes of agents start to decrease almost simultaneously because the class of agents with good channel state is scheduled. Starting from [TeX:] $$h=\hat{H}_2,$$ the PDFs of both classes of agents start to decrease again because the class of agents with unknown channel state is scheduled.

In Fig. 5, we present the empirical and theoretical CDFs of the rescaled AoI at the optimal threshold when N = 2000, [TeX:] $$\rho_{c, c^{\prime}}=0.1, \gamma=0.1, p_{\mathrm{s}, \mathrm{G}}=0.5.$$ As can be seen from the figure, the empirical CDF of rescaled AoI gradually converges to equilibrium and is in perfect consistency with the theoretical CDF.

2) Unknown all channel states:

In Fig. 6, we present the empirical and theoretical CDFs of the rescaled AoI at the optimal threshold when N = 2000, [TeX:] $$\rho_{c, c^{\prime}}=0.1, \gamma=0, p_{\mathrm{s}, \mathrm{G}}=1.$$ As can be seen from the figure, the empirical CDF of rescaled AoI gradually converges to equilibrium and is in perfect consistency with the theoretical CDF.

C. Average AoI Comparison

About the AoI in channels with different time-varying degrees, i.e., γ , computer simulations are conducted. Two classes of agents (equal number of agents in each class) are tested, with [TeX:] $$p_{\mathrm{s}, \mathrm{G}}=1 \text{ and } p_{\mathrm{s}, \mathrm{B}}=0,$$ respectively. Since there have been no previous studies on the Whittle’s index policy under partially observable time-varying channels, we assume that the probability of successful transmission of the unknown channel is [TeX:] $$p_{\mathrm{s}, \text { Unknown }}=\frac{\eta_1}{\eta_1+\eta_2} p_{\mathrm{s}, \mathrm{G}}+\frac{\eta_2}{\eta_1+\eta_2} p_{\mathrm{s}, \mathrm{B}}.$$ Consequently, we show the AoI performance under [16, Theorem 5] with γ = 1 and the AoI performance under [6, Theorem 17] with γ = 0.1, γ = 0. In Fig. 7, we compare the time-average AoI performance of Fluid Limits, the Whittle’s index approach [6], [16], both with γ = 1, γ = 0.1, γ = 0 and the theoretical fluid limits with [TeX:] $$\rho_{c, c^{\prime}}=1, \eta_1=1$$ (without the [TeX:] $$\mathcal{O}(1)$$ term and thus is also the AoI lower bound in (50)). It is found that the fluid limits with [TeX:] $$\gamma \neq 0$$ are very close to the Lower Bound with all channel states are good and outperforms the Whittle’s index policy at any γ, which consistent with our previous theoretical analysis results.

VIII. CONCLUSIONS AND OUTLOOK

In this paper, the system asymptotic behavior with a large number of agents, i.e., the fluid limits, is developed for AoI occupancy measure in wireless multiaccess networks. It is shown that, under a simple threshold-based policy, the system limiting behavior converges to a fluid limit within an error inversely proportional to the number of agents. Moreover, the fluid limit has a provable asymptotically local stable equilibrium that can be used to solve for the stationary AoI distribution.

Leveraging this framework, we solve an AoI scheduling problem with heterogeneous i.i.d. user channel conditions. A well-known existing lower bound, yet with unknown tightness, is shown to be asymptotically tight. The achievability is proved by optimizing the thresholds in our proposed thresholdbased policy. The resultant scheduling policy is asymptotically optimal with explicitly derived thresholds, and is much easier to decentralize compared with the index-based policy. Users in the proposed policy only need to know its fixed individual threshold, whereas users have to compare their indices every time by the index policy.

Furthermore, we show that the AoI with partially observable time-varying channels can be solved by the fluid limit framework. We analyzed the optimal long-time average AoI with different proportions of observable channel states and show that the optimal AoI performance can be achieved as long as only a small fraction of the channel states are known. Simulations reveal that our analysis matches the reality closely, and that the convergence to the fluid limit is evident with a moderate number of users.

Essentially, we believe a large scope of AoI scheduling problems can be solved leveraging this powerful analysis tool. The crux is the convergence of AoI occupancy measure to the fluid limit. As long as this is upheld, which is often the case in AoI scheduling, the rest follows conveniently. Generalization to other applications is our ongoing work.