Minimizing Moments of AoI for Both Active and Passive Users through Second-Order Analysis

Recently, there has been a significant increase in the use of time-sensitive applications such as Internet of Things, vehicular networks, sensor networks, and drone systems for surveillance and reconnaissance. While traditional research has focused on optimizing the reliability and throughput of communication, these efforts often fall short in meeting the demands for fresh data. To address this, a performance metric known as age-of-information (AoI) was introduced [1] and has received increasing attention in recent literature [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32].

Previous studies on AoI have commonly considered centralized control over transmission decisions [8, 9, 7, 10, 11, 12, 13] and queuing problems without transmission collisions [15, 18, 16, 19, 17]. However, centralized policies and collisions can lead to large overhead or extra communication, which can be a significant drawback in delay-sensitive applications such as the Internet of Things and transmission-sensitive applications like satellite communications.

To address this issue, we consider a random access network, where active users broadcast sensed data and multiple transmissions at the same time can cause collisions. Since there are no acknowledgements in broadcast, active users do not have any feedback information on collisions. This makes recent feedback-based algorithms for AoI optimization [22, 23, 24, 25, 21, 26] inapplicable.

Additionally, we consider that the network has silent observers, referred to as passive users, who share the same channel as active users. Passive users aim to observe out-of-network radio activities in the same channel but do not make any transmissions. Examples of passive users include sensors detecting malicious jammers, receivers of satellite communications, and radio telescopes tracking celestial objects. The coexistence of passive and active users can improve channel utilization, as passive users can obtain valuable observations when no active user is transmitting.

As AoI depends on previous successful transmissions, memoryless random access algorithms, such as slotted ALOHA, are not suitable for optimizing AoI. Therefore, we consider that each active user follows a Markov process to determine its transmission activities. Furthermore, instead of only considering the mean of AoI, we consider the moments of AoI, which can offer insights into the variance and the maximum value of AoI.

The goal of this paper is to minimize the weighted sum of any moment of AoI for both active users and passive users. There are several challenges that need to be addressed. First, since the transmission strategy of an active user is Markovian instead of i.i.d., the temporal correlation of its transmission activities needs to be explicitly taken into account. Second, active users and passive users have different behavior, which leads to different definitions of AoI between the two types of users. Third, most existing studies on moments of AoI, such as [17, 18, 19], focus only on simple queueing systems and are not applicable to random access networks. Finally, most existing studies on AoI in random access networks only focus on the first moment of AoI and can only obtain the optimal solution in the asymptotic sense.

To address above challenges and solve the optimization problem, we propose to investigate the system behavior through a second-order analysis. We analyze the mean and temporal variance of delivery process to characterize the system. Then, we formulate the expressions of moments of AoI based on these mean and temporal variance, and then further formulate them as functions of state change probabilities in Markov process. By revealing special properties in expressions of moments of AoI for both active and passive users, we find that the optimal action for an active user, under some minor conditions, is to become silent immediately after one attempt of transmission. The simulation results show that our formulation of moments of AoI is valid and our solution outperforms other baseline algorithms that have different active user activity models.

The rest of the paper is organized as follows. Section II introduces our system model and the optimization problem. Section III formulates expressions of moments of AoI based for both active and passive users based on a second-order model. Section IV solves the optimal transmission strategies. Some simulation results are presented in Section V. Finally, Section VI concludes the paper.

We consider a wireless system with one channel and two types of users, active users and passive users. Each active user monitors a particular field of interest and uses the wireless channel to transmit its surveillance information to its neighboring receivers. Passive users do not make any wireless transmissions and instead monitor the radio activities in the wireless channel. For example, in a battlefield scenario, an active user can be a surveillance drone that monitors a certain area in the battlefield and broadcasts its video feed to all nearby units. A passive user can be a signal detector that aims to identify and locate enemy jammers or communication devices operating in the same channel.

Next, we discuss the interference relationship among users. We assume that active users are grouped into $C$ clusters and each cluster has $N$ ($N\geq 2$) active users. Active users in the same cluster interfere with each other but do not suffer from interference from other clusters. An active user can successfully deliver a packet if it is the only device in the cluster that is transmitting. If multiple active users in the same cluster transmit at the same time, then a collision occurs and none of the packets are received. On the other hand, since passive users need to detect enemy devices that are potentially far away, we assume that a passive user is interfered by all active users and it can only detect radio activities if no active user is transmitting.

The performance of each user is determined by its associated AoI. We assume that time is slotted and the duration of one time slot is the time needed to transmit one packet. Each active user generates a new surveillance packet in each slot. Hence, the AoI of an active user $n$ at time $t$ is defined by following recursion:

Since passive users can only detect radio activities when no active users are transmitting, the AoI of passive user $j$ at time $t$ is defined by

We now discuss the transmission strategy of each active user. We assume that the strategy of an active user is governed by a Markov process with two states, a TX state and an Idle state. An active user will transmit a packet at time $t$ if and only if it is in the TX state. If an active user is in the TX state at time $t$, then its state will change to Idle at time $t+1$ with probability $s$. If an active user is in the Idle state at time $t$, then its state will change to TX at time $t+1$ with probability $r$. Fig. 1 presents this Markov process. We note that this strategy generalizes the ALOHA network. In particular, if $r+s=1$, then an active user will transmit in each time slot with probability $r$ independently.

We aim to minimize the moments of AoI for both active users and passive users. Specifically, let $AoI_{a}$ be the random variable of an active user’s AoI and let $AoI_{p}$ be the random variable of a passive user’s AoI in steady state. For a fixed integer $z$ and a fixed real number $w\in[0,1]$, we aim to find $r$ and $s$ that solve the following optimization problem:

where $E[\cdot]$ is the expectation function.

A key challenge in solving the optimization problem (1)-(2) is that it is hard to express $E[AoI_{a}^{z}]$ and $E[AoI_{p}^{z}]$ as functions of $r$ and $s$. We propose to adopt the framework of second-order network optimization in Guo et al. [30] to address this challenge. The framework in [30] is only applicable to centrally scheduled systems and the mean of AoI. In this section, we will extend this framework to model random access networks and moments of AoI.

We first define the second-order model that describes the performance of both active and passive users. For an active user $n$, Let $S_{n}(t)$ be the indicator function that $n$ successfully delivers a packet at time $t$, that is, $n$ is the only active user in its cluster that transmits at time $t$. We call $[S_{n}(1),S_{n}(2),\dots]$ the delivery process of $n$. Due to symmetry, the delivery processes of all active users follow the same distribution. We then define the mean and temporal variance of the delivery process of an active user by

respectively, where the expectation is taken over all sample paths.

For a passive user $j$, we let $S_{j}(t)$ be the indicator function that no active user transmits, and hence the passive user can monitor radio activities without interference, at time $t$. We call $[S_{j}(1),S_{j}(2),\dots]$ the passive detection process. The mean and temporal variance of the passive detection process are defined as $m_{p}:=\lim_{T\xrightarrow{}\infty}\frac{\sum_{t=1}^{T}S_{j}(t)}{T}$ and $v_{p}^{2}:=E[(\lim_{T\xrightarrow{}\infty}\frac{\sum_{t=1}^{T}S_{j}(t)-Tm_{p}}{\sqrt{T}})^{2}]$, respectively.

The second-order model uses the means and temporal variances to capture and approximate all aspects of the system. To show its utility, we first derive the closed form expressions of $m_{a}$, $m_{p}$, $v_{a}^{2}$, and $v_{p}^{2}$. Let $\lambda:=\frac{r}{r+s}$ and $\theta=1-r-s$, we have the following theorem:

Next, we show that the moments of AoI of both active users and passive users can be approximated as functions of $(m_{a},v_{a}^{2})$ and $(m_{p},v_{p}^{2})$, respectively.

Due to space limitation, we focus on discussing the derivation of moments of AoI of active users.

Let $t_{i}$ be the $i$-th time that an active user $n$ successfully deliveries its packet, and define $l_{n}(i):=t_{i}-t_{i-1}$. For active user $n$, its AoI from $t_{i-1}$ to $t_{i}-1$ is from $1$ to $l_{n}(i)$. So, the summation of $z$-th moment of AoI from $t_{i-1}$ to $t_{i}-1$ is $\sum_{k=1}^{l_{n}(i)}k^{z}$. Let $L_{n}$ be the total number of deliveries for active user $n$. Then, summing over all $l_{n}(i)$, we have the sum of all $z$-th moment of AoI for active user $n$, $\sum_{i=1}^{L_{n}}\sum_{k=1}^{l_{n}(i)}k^{z}$. Next, divided by the whole time $\sum_{i=1}^{L_{n}}l_{n}(i)$ and choosing the expectation, we have $E[AoI_{a}^{z}]=E\Big{[}\lim_{L_{n}\xrightarrow{}\infty}\frac{\sum_{i=1}^{L_{n}}\sum_{k=1}^{l_{n}(i)}k^{z}}{\sum_{i=1}^{L_{n}}l_{n}(i)}\Big{]}$. By using the Faulhaber’s formula, we have

where $B_{k}$ is the Bernoulli number.

To approximate $E[l_{n}(i)^{k}]$, we construct an alternative sequence $S^{\prime}_{n}(t)$ that have the same mean and temporal variance as $S_{n}(t)$. Let $D_{n}(t)$ be a Brownian motion random process with mean $m_{a}$ and variance $v_{a}^{2}$. The sequence $\{S^{\prime}_{n}(1),S^{\prime}_{n}(2),\dots\}$ is defined as

where $t^{-}=\max\{\tau|\tau<t,S^{\prime}_{n}(\tau)=1\}$. Intuitively, we assume that a packet delivery occurs in the alternative sequence every time $D_{n}(t)$ increases by one since the last packet delivery in this sequence. Hence, $\sum_{\tau=1}^{t}S_{n}^{\prime}(\tau)$ is close to $D_{n}(t)$, and the process $[S^{\prime}_{n}(1),S^{\prime}_{n}(2),...]$ has mean $m_{a}$ and temporal variance $v_{a}^{2}$.

Let $l_{n}^{\prime}(i):=t^{\prime}_{n,i}-t^{\prime}_{n,i-1}$, where $t^{\prime}_{n,i}$ is the $i$-th time that $S^{\prime}_{n}(t)=1$. Since $S^{\prime}_{n}(t)$ has the same mean and temporal variance as $S_{n}(t)$, we propose to approximate $E[l_{n}(i)^{k}]$ by $E[l^{\prime}_{n}(i)^{k}]$. Moreover, $l^{\prime}_{n}(i)$ can be regarded as the time needed for $D_{n}(t)$ to increase by $1$, which is equivalent to the first-hitting time for the Brownian motion random process with level $1$. Thus, $l_{n}^{\prime}(i)$ follows the inverse Gaussian distribution $IG(\frac{1}{m_{a}},\frac{1}{v_{a}^{2}})$ ([33, 34]). By using the moment generating function of inverse Gaussian distribution in [35], we have $E[l^{\prime}_{n}(i)^{k}]=\frac{1}{m_{a}^{k}}\sum_{\zeta=0}^{k-1}\frac{(k-1+\zeta)!}{\zeta!(k-1-\zeta)!}(\frac{2m_{a}}{v_{a}^{2}})^{-\zeta}$.

For a passive user $j$, let $\bar{t}_{i}$ be the $i$-th time that $S_{j}(t)=1$ and $l_{j}(t):=\bar{t}_{i}-\bar{t}_{i-1}$. By combining the derivations above, we obtain the following:

For example, we have $E[AoI_{a}]=\frac{1}{2}(\frac{v_{a}^{2}}{m_{a}^{2}}+\frac{1}{m_{a}})+\frac{1}{2}$ and $E[AoI_{a}^{2}]=\frac{v_{a}^{4}}{m_{a}^{4}}+\frac{v_{a}^{2}}{m_{a}^{3}}+\frac{3v_{a}^{2}+2}{6m_{a}^{2}}+\frac{1}{2m_{a}}+\frac{1}{6}$.

With the help of Theorem 2, $F(r,s)$ can now be approximated as a function of $(m_{a},v_{a}^{2},m_{p},v_{p}^{2})$, which, as stated in Theorem 1, can be expressed as functions of $r$ and $s$.

In the previous section, we approximate $E[AoI_{a}^{z}]$ and $E[AoI_{p}^{z}]$ as functions of $r$ and $s$. In this section, we further study the optimal behavior of active users and solve the optimal $r$ and $s$. We find the interesting property that, when $N>C+4$, the optimal solution requires an active user to the Idle state every time it makes a transmission, i.e., $s=1$. This result is formally stated below.

In addition to showing the interesting behavior that, under the optimal solution, an active user will never transmit in two consecutive slots, this theorem also simplifies the search for the optimal solution. In particular, it shows that one only needs to find the optimal $\lambda$, which can be done through a simple line search, in order to obtain the optimal solution.

Recall that $\lambda=\frac{r}{r+s}$ and $\theta=1-r-s$, or, equivalently, $r=\lambda(1-\theta)$ and $s=(1-\lambda)(1-\theta)$. Before proving Theorem 3, we first establish some properties about the optimal $\lambda$ and $\theta$. We start by the following lemma:

Based on Lemma  1, we further have

Next, we analyze the optimal $\theta$. The lemma below derives the optimal $\theta$ when $\lambda$ is given and fixed.

A limitation of Lemma 3 is that it requires $\lambda\in[0,\min\{\alpha,\beta\}]$. In the following lemma, we establish lower bounds of $\alpha$ and $\beta$.

We are now ready to prove Theorem 3.

This section presents simulation results for applying our solution of $r$ and $s$. The performance function is the optimization objective $F(r,s)$.

The results of our solution are compared with three other baseline policies. We provide descriptions of all four policies, along with necessary modifications to fit the simulation setting.

• •

  Our solution: Based on Theorem 3, we choose the optimal $\lambda$ and set $r=\frac{\lambda}{1-\lambda}$ and $s=1$ for all active users. This optimal $\lambda$ is obtained by plugging $r=\frac{\lambda}{1-\lambda}$ and $s=1$ into Theorem 2 and doing an exhaustive search over $\lambda$ for $F(r,s)$ with a precision $0.01$.

• •

  Slotted ALOHA: When $r+s=1$, our active user model is reduced to be slotted ALOHA, which is a famous and commonly used model for transmissions with no acknowledgment. According to solutions in [5], we choose $r=\frac{1}{N}$ and $s=1-\frac{1}{N}$.

• •

  Optimal ALOHA: After introducing passive users, the optimal $\lambda$ in slotted ALOHA is no longer $\frac{1}{N}$. Thus, we simulate all possible $\lambda$ with precision $0.01$, and then choose the best $\lambda$ to obtain optimal slotted ALOHA. It should be noticed that optimal ALOHA is impossible to implement in real world since its $\lambda$ is determined after the whole process is finished.

• •

  Age Threshold ALOHA (ATA): Age threshold ALOHA is proposed by Yavascan and Uysal [24], which is a slotted ALOHA algorithm with an age threshold. If the AoI of one active user is larger than a threshold, this active user will follow slotted ALOHA transmission with probability $r$. Otherwise, this active user will stay silent. Since there is no acknowledgment in the system, we let active users assume their transmissions are always successful. As suggested in [24], $r=4.69/N$ and the age threshold is $2.2N$.

We simulate different scenarios with varying values of $w$, where $w$ ranges from $0$ to $1$. We set $N=7$, $C=2$ or $4$, and $z=1$ or $2$. Once $N$, $C$ and $z$ are determined, we can set the values of $r$ and $s$ based on policy designs. The system is then simulated for $10$ individual runs, each with $100,000$ time slots. The final results are the average of these $10$ runs. We present the value of $\frac{\text{Actual }F(r,s)\text{ of one algorithm}}{\text{Theoretical }F(r,s)\text{ of our solution}}$ for all four algorithms under each setting. Simulation results are shown in Fig. 2. As some values are extremely large, only results that have ratio below $2.4$ are shown in figures.

The results show that the average mismatches between theoretical $F(r,s)$ and actual $F(r,s)$ of our solution are about $0.7\%$ when $z=1$ and $12\%$ when $z=2$. Furthermore, we notice the actual value is always lower than theoretical value. These results indicate that our approximation is useful in practice.

Comparing the performance of different algorithms in Figure 2a and Figure 2b, we can observe that our strategy outperforms other three policies in all settings. Even when compared to the optimal ALOHA, which is not practical in real-world scenarios, our strategy shows a $4\%$ reduction when $z=1$ and a $9\%$ reduction when $z=2$. Additionally, the increase in the reduction of our strategy between $z=1$ and $z=2$ indicates that our strategy can better optimize the variance of AoI.

In Figure 2c and Figure 2d, we simulate $C=4$ to evaluate the performance of our strategy when the condition $N>C+4$ is not met. The Results indicate that our strategy outperforms the other three algorithms in nearly all settings, even when the condition $N>C+4$ is not satisfied.

This paper studies an optimization problem of moments of AoI for both active and passive users in a random access network. In this network, active users broadcast their transmissions following a Markov process and will interfere with each other. By applying a second-order model, we formulate moments of AoI as functions of state change probabilities in the Markov process. Next, we reveal the special properties of these functions and optimize moments of AoI for both active and passive users. The optimal solution indicates that the best strategy for active users is to become silent immediately after one transmission. Simulations show that this transmission strategy outperforms three baseline algorithms under various settings.

This material is based upon work supported in part by NSF under Award Number ECCS-2127721, in part by ARL and ARO under Grant Number W911NF-22-1-0151, and in part by ONR under Contract N00014-21-1-2385.