Age of Information in Reservation Multi-Access Networks with Stochastic Arrivals

Recent years have witnessed increasing research interest in a new performance metric, Age of Information (AoI), thanks to its capability of quantifying the timeliness of data transmission in status update systems [1, 2]. The timeliness of data transmission plays an important role in various Internet of Thing (IoT) applications, particularly in real-time monitoring systems. In these systems, the dynamics of the monitored process should be grasped at the monitor in a timely manner to ensure in-time responses. AoI is defined as the time elapsed since the generation time of the latest received status update at the receiver[1]. According to its definition, AoI is jointly determined by the transmission interval, transmission delay, and status generation process.

The trend of massive connectivity of IoT networks [3] and the importance of information freshness have recently attracted considerable efforts in optimizing information freshness of multi-access networks. In this context, how to dynamically schedule the data transmission of users in multi-access networks to minimize the network-wide average AoI becomes a critical problem. Polling-based centralized scheduling schemes [4, 5, 6, 7] and contention-based random access schemes [8, 9, 10, 11, 12, 13, 14] are two major research branches. The sporadic IoT traffic makes contention-based random access schemes more preferable in large-scale networks. This is because centralized scheduling is usually associated with excessive overhead and high operation complexity. In contrast, contention-based multi-access schemes have acceptable overhead with simple operation, and can flexibly adapt to the networks with a varying number of devices.

Previous studies on contention-based multi-access schemes have explored the average AoI of ALOHA and CSMA protocols. The average AoI of slotted ALOHA systems was first characterized in [8]. Specifically, the ALOHA-alike policy, in which each user transmits its status updates with a fixed transmission probability was analyzed and compared with the centralized scheduling policy [8]. Inspired by this seminal work, age-dependent slotted ALOHA policy was devised and analyzed in [9, 10], where each user randomly accesses the shared channel only when its instantaneous AoI exceeds a predetermined threshold. Different from previous studies considering generate-at-will status generation model, the authors in [11, 12, 13] investigated the contention-based multi-access schemes with stochastic arrival models for status updates. In [11, 12], status generation at each user is modeled by independent and identically distributed (i.i.d.) Bernoulli process. The analytical AoI performance of a stationary randomized policy was derived, and the asymptotic optimality of slotted ALOHA with small status arrival rate in the regime of infinite users was analyzed in [11]. An age-based thinning method was proposed in [11] to further improve the AoI performance of the slotted ALOHA systems. The authors in [12] derived approximate expressions for the average AoI of both slotted ALOHA and CSMA schemes by developing a discrete-time model. The AoI performance of CSMA was also studied in [13], where the stochastic hybrid system was applied to derive the accurate average AoI expression for generate-at-will model and a tight upper bound of average AoI for stochastic arrival model, respectively. Very recently, the AoI performance of irregular repetition slotted ALOHA was studied and compared with that of slotted ALOHA in [14].

Apart from the polling-based and contention-based multi-access schemes, there is another type of dynamic allocation schemes, called reservation-based multi-access (R-MA) [15]. In each frame of R-MA, one reservation slot, consisting of multiple mini-slots, is introduced for users to contend for the data slots. Only those users made successful reservations are allowed to transmit in their reserved data slots of the said frame, leading to non-conflicting data transmission [16, 17, 18]. Furthermore, R-MA schemes squeeze the potential collisions among users into the shorter mini-slots, reducing the time overhead for contention. In light of these features, R-MA scheme have a great potential to reduce the network-wide AoI. Nevertheless, to the best of the authors’ knowledge, the AoI performance of R-MA protocols has not been thoroughly characterized in open literature.

As an attempt to fill the gap, in this paper we investigate the average AoI performance of Frame Slotted ALOHA with Reservation and Data slots (FSA-RD), which is an representative R-MA protocol [16, 17, 18]. Specifically, we consider a symmetric multi-access network, where each user transmits its randomly generated status updates to an access point (AP) in a framed manner. The stochastic arrivals of status updates, the randomness in reservation attempts and reservation slot selection (i.e., which slot to reserve), as well as the tangled reservation results (i.e., whether the reservation is successful) altogether make the theoretical analysis of the average AoI (AAoI) for the considered system non-trivial. To provide insights in optimizing the information freshness of FSA-RD, we manage to derive a closed-form expression of the AAoI. Specifically, we focus on evaluating AoI evolution of a particular user to analyze the network-wide AAoI. A recursive method is applied to characterize all possible combinations of status generations, packet preemptions, and reservation attempts for deriving AAoI under FSA-RD. Numerical results are provided to validate the analytical expression of AAoI, and to evaluate the influence of frame size and reservation probability on AAoI. We finally perform a comparison between AAoI of FSA-RD with optimized frame size and reservation probability, and that of slotted ALOHA with optimized transmission probability. Our results show that FSA-RD can substantially reduce the AAoI of multi-access networks, especially when the status arrival rate of the network becomes large.

We note that the AoI of each user is identically distributed due to the symmetric network setup. As such, in this section we focus on analyzing the AAoI of one particular user to represent the network-wide AAoI performance and omit user index for brevity. To derive the analytical expression of AAoI, we first elaborate some useful definitions for the considered system, inspired by the analytical framework presented in [19].

We define $t_{i}^{*}$ as the end of the frame within which the $i$th status update is successfully received at the AP, which is also the beginning of the next frame after $i$th reception of status updates. As the status updates randomly arrive at each user and are transmitted in the next frame, we define the waiting time $W_{i}$ as the time elapsed from $t_{i-1}^{*}$, until the beginning of the first frame when the user has a status update to transmit after $t_{i-1}^{*}$, denoted by $G_{i}$. We thus have $W_{i}=G_{i}-t_{i-1}^{*}$. Due to the frame-based transmission structure, $W_{i}$ takes value from $\{0,M,2M,...\}$. Recall that whether a user has a status update for transmission in each frame follows a Bernoulli distribution with parameter $p=1-(1-\rho)^{M}$. We then can obtain the probability mass function (PMF) of $W_{i}$, given by $\mathrm{Pr}\{W_{i}=xM\}=(1-p)^{x}p$, and we further have

We also define $K_{i}$ as the time interval from $G_{i}$ until the end of the frame within which the $i$th status update is received at the AP, i.e., $K_{i}=t_{i}^{*}-G_{i}$. We further define $Y_{i}$ as the time interval between the ends of two frames within which the $(i-1)$th and $i$th status updates are received at the AP, respectively, i.e., $Y_{i}=t_{i}^{*}-t_{i-1}^{*}$. Together with the definitions of $W_{i}$ and $K_{i}$, we have $Y_{i}=W_{i}+K_{i}$.

Let $X_{i}$ denote the inter-departure time of two successive correctly received status updates at the AP, i.e., $X_{i}=t_{i}^{{}^{\prime}}-t_{i-1}^{{}^{\prime}}$. Let $N_{t}$ denote the number of status updates that have been successfully received by the AP until time $t$. Similar to [1, Eq 2], AAoI can be expressed as

where $Q_{i}$ is the polygon area as depicted in Fig. 2. The area of $Q_{i}$ can be calculated as

By taking the expectations on both sides of (4) and substituting the expectations into (3), we have

According to the status generation model and transmission model, $S_{i-1}$ consists of two time intervals that a successfully received status update has experienced in its non-preemptive generation frame and transmission frame until its reception, denoted by $l_{i-1}$ and $\alpha_{i-1}$, respectively. Mathematically, $S_{i-1}=l_{i-1}+\alpha_{i-1}$, where $l_{i-1}$ describes the status generation process while $\alpha_{i-1}$ characterizes the status transmission process. As such, $l_{i-1}$ and $\alpha_{i-1}$ are independent. Meanwhile, the inter-departure time ($X_{i}$) between the $(i-1)$th and $i$th receptions of status updates consists of three parts: the remaining time slots in the transmission frame of the $(i-1)$th received status update since its reception (i.e., $M-\alpha_{i-1}$); the frames without successful status transmission since the $(i-1)$th reception of status updates (i.e., $Y_{i}-M$); and the time slots in the transmission frame of the $i$th received status update until its reception (i.e., $\alpha_{i}$). That is, $X_{i}=M-\alpha_{i-1}+Y_{i}-M+\alpha_{i}$. Recall that $\alpha_{i-1}$ and $\alpha_{i}$ are the time intervals that the $(i-1)$th and $i$th received status updates spent in their transmission frame until reception, and thus they are i.i.d. Thus, we have $\mathbb{E}[X_{i}]=\mathbb{E}[Y_{i}]$.

Besides, each status update can be transmitted at most once in the next frame after its generation and all transmissions of one user are independent. As such, the unsuccessful frame interval $Y_{i}-M$ is also independent of $\alpha_{i-1}$ and $\alpha_{i}$ as well as $l_{i-1}$. Together with the i.i.d. property of the sequence of random variable $\{\alpha_{i}\}$, we have

where $\mathrm{Var}(\alpha)$ is the variance of random variable $\alpha_{i}$ ($\alpha_{i-1}$ also). By substituting (6) and (7) into (5), together with $\mathbb{E}[X_{i}]=\mathbb{E}[Y_{i}]$, we have

Due to the i.i.d. property of the two sequences of random variables $\{S_{i}\}$ and $\{Y_{i}\}$, we hereafter omit the subscripts of $S_{i-1}$ and $Y_{i}$, and calculate $\mathbb{E}[S]$, $\mathbb{E}[Y]$ and $\mathbb{E}[Y^{2}]$ for brevity.

In this section, both numerical and analytical results of AoI performance of the considered system are presented. We first evaluate the derived analytical expression of AAoI by comparing it with Monte Carlo simulation results. Fig. 3 plots the AAoI curves versus reservation probability $\gamma$, considering a multi-access system with $N=30$ and $V=4$. Firstly, we can see from Fig. 3 that our analytical results coincide well with the corresponding simulation results, which validates our derivation of $\bar{\Delta}$. Secondly, we can find that when the status generation probability goes large, the optimal reservation probability should be neither too large nor too small for better AoI performance. This is understandable as a larger reservation probability is more likely to cause reservation failures (i.e., more reservation collisions), while a smaller reservation probability makes users less likely to make a reservation. In both cases, fewer users transmit status updates in data slots and some unreserved data slots are wasted, leading to larger network-wide AAoI performance. Besides, when the status generation probability is considerably small, the reservation probability should be as large as possible. The rationale is that when status updates are rarely generated, it is less likely to cause collision even when all users make reservations once they have a status update to transmit. In contrast, small reservation probability may lead to the drop of rarely generated status updates, resulting in larger AoI. Moreover, by comparing the performance of different frame length $M$, we observe that larger $M$ in some cases may cause performance degradation in FSA-RD. This is because when only small number of users make successful reservations, after these users transmitting their status updates, the rest data slots in the frame will be wasted. In this sense, the choice of $M$ should take the successful reservation rate into consideration.

Table I compares the of FSA-RD under the optimal frame length $M$ and optimal reservation probability $\gamma$, with the simulation results of the optimized AAoI performance of slotted ALOHA. Specifically, given the network setups, we exhaustively search all values of $M$ and $\gamma$ to achieve the minimum value of $\eqref{age}$ for RSA-RD. As for slotted ALOHA, we simulate the age evolution with different values of transmission probability to find its optimal AAoI performance. We can see that when the product $\rho N$ is small, the slotted ALOHA has smaller AAoI than FSA-RD. As $\rho N$ increases through either increasing $N$ or $\rho$, the optimal performance of FSA-RD improves and becomes better than that of slotted ALOHA with up to $29\%$ AAoI reduction. The observation could be caused by the joint effect of the one slot reservation overhead and the frame-based transmission (i.e., status update will be transmitted at the next frame and dropped after its transmission frame). Besides, it is obvious that a larger number of mini-slots (i.e., the value of $V$) in reservation slot leads better AAoI performance in FSA-RD scheme as the larger the value of $V$, the higher the successful reservation probability.

We investigated the average age of information (AAoI) performance of Frame Slotted ALOHA with Reservation and Data slots (FSA-RD). A symmetric multi-access network was considered, where each user transmits its randomly generated status updates to an access point in a framed manner. To gain insights in optimizing the AAoI of FSA-RD, we derived a closed-form expression of the AAoI under FSA-RD. The correctness of the analytical AAoI was verified by comparing with the simulated AAoI in numerical results. Numerical results showed that when the status arrival rate of the network becomes large, FSA-RD with optimized reservation probability and frame size can achieve up to $29\%$ AAoI reduction, compared with optimized slotted ALOHA. Future work will include the investigation of the AAoI of FSA-RD with variable frame length and different contention schemes for making reservations.