Age of Information in NOMA-IoT Networks: A Temporal Queuing Model Perspective

Abstract

The Internet of Things (IoT) with non-orthogonal multiple access (NOMA) has been anticipated to offer diverse real-time applications, wherein the crux is to guarantee the age of information (AoI) for dynamic traffic. However, the traffic temporal variation provokes the interdependence between queue status and interference, in which context the AoI performance remains to be further explored. In this paper, an analytical framework is established to characterize the AoI performance in NOMA-IoT networks with random Bernoulli and deterministic periodic arrivals. Particularly, a numerical algorithm is devised to obtain the queue service rate, and tractable expressions for AoI violation probability and average AoI under both the first-come first-served (FCFS) and the preemptive last-come first-served (LCFS-PR) service disciplines are derived. Simulations are conducted to validate the proposed analysis. The results unveil that LCFS-PR conduces to better AoI performance than FCFS, and yet the gain diverges for each device with different traffic arrival configurations. In addition, the result shows that with sporadic traffic arrival, the periodic pattern outperforms the Bernoulli pattern, whereas this advantage gradually diminishes with more frequent packet arrival.

1. Introduction

By connecting billions of devices to the Internet, the Internet of Things (IoT) merges the physical and digital universes, thus making our lives more responsive and more intelligent [1]. Benefiting from IoT, data of our concern can be precisely collected and further utilized to provide fine-grained mastery in diverse real-time applications, e.g., industrial manufacturing, quality monitoring, and transportation control [2,3,4]. One distinctive feature of these applications is the strict constraint on information freshness since the obsolescence of acquired information inevitably results in deterioration in the system decision accuracy and reliability. Therefore, evaluating the freshness of the sensed information is of utmost importance for network design [5,6]. In this regard, Age of Information (AoI) has been introduced as a performance metric to quantify information freshness [7]. Specifically, AoI gives the time elapsed since the newest delivered packet was generated at the source. Different from the conventional time delay metric, AoI places particular emphasis on the latency experienced by the destination, which is jointly affected by packet generation and packet transmission.

The conflict between massive communication devices and scarce communication resources is becoming increasingly prominent. Several spectrum-sharing techniques are proposed to solve this key problem in various network scenarios, such as heterogeneous networks and cognitive relay networks [8,9]. In addition, non-orthogonal multiple access (NOMA) is also perceived as a potent solution since NOMA, which is different from orthogonal multiple access (OMA), allows multiple devices to transmit on the same resource. By NOMA, devices are multiplexed in the power domain, and meanwhile, the intended signal for each device is extracted from the superimposed signals by utilizing successive interference cancellation (SIC) at the destination. Therefore, NOMA offers the potential to enhance resource utilization efficiency and reduce access delay [10,11]. The mature application of NOMA in wireless networks is regarded to be promising, which paves the way for future B5G/6G systems. In the context of information freshness gathering spiraling attention, it is necessary to explore and understand the AoI performance in NOMA-IoT networks.

Since the concept of AoI was introduced, AoI has sparked enormous research interest due to its effectiveness. Specifically, AoI-oriented scheduling strategies have been devised to guarantee timely information delivery [12,13,14]. In addition, several pioneering works have been dedicated to studying the AoI performance in the field of queuing theory. Expressions for time-average AoI in status update systems with different packet management policies at the source node are obtained in [15]. In [16], the authors consider the AoI stationary distribution in a single-server information update system under both first-come first-served (FCFS) and last-come first-served (LCFS) queue service disciplines. Apart from the continuous-time queuing models, the AoI performance in the discrete-time queuing model has also come into sight by taking note of the broad deployment of slotted-operated IoT infrastructures. In this line of research, the authors in [17] consider the AoI minimization problem under general interference constraints and derive the peak and average AoI expressions for discrete-time queues with FCFS. Resorting to the temporal properties of the AoI sample path, the generating function of AoI in a single-server queuing system is provided in [18], while taking into account FCFS and LCFS with preemptive (LCFS-PR) disciplines. Moreover, the impacts of bufferless and single buffer sources on the AoI distribution are analyzed in [19] under the Bernoulli arrival assumption. The average AoI of a status update system with size 2 is studied in [20], where probabilistic packet preemption is considered by constituting a three-dimensional age process.

However, the above-mentioned works rely on abstract queuing models and overlook the impact of mutual interference. More explicitly, the packet departure process is assumed to be a certain distribution and hence falls short of capturing the impact of wireless transmissions. Recognizing this, several attempts have been made to mimic the packet departure according to the tightly entangled transmissions resulting from the fact that the mutual interference hinges upon the time-varying queue status of each node. Considering such a model, the authors in [21] demonstrate that with different deployment density configurations, the Poisson bipolar networks under LCFS-PR can achieve better average AoI performance than those under FCFS. Moreover, the effect of packet arrival patterns on the AoI performance is analyzed in [22,23]. Specifically, the average AoI and its violation probability in Poisson bipolar networks with sources having different buffer size, together with different arrival patterns, are derived in [22]. Accounting for the mutual interference in the macroscopic network scale and the queue evolution in the microscopic network scale, the authors in [23] characterize the peak AoI in uplink IoT networks for randomly and periodically generated traffic.

The benefit of NOMA has attracted attention in the literature in the study of information freshness in NOMA networks, and a number of works have been conducted recently. The time-average AoI performance considering a typical two-user NOMA network is investigated in [24]. By leveraging the stochastic hybrid system (SHS) method, the authors show the potential of NOMA in reducing AoI. An adaptive NOMA/OMA transmission policy is proposed in [25] to minimize the system AoI. Moreover, the system AoI performance in IoT networks with OMA and NOMA scheduling schemes is compared in [26]. The authors in [27] show that AoI reduction can be achieved by using a new design of cognitive radio-inspired NOMA.

Albeit enlightening in understanding the fundamental AoI performance in NOMA networks, the aforementioned works are based on the generate-at-will model [28] and thereby lack the ability to characterize the dynamic packet arrivals and departures. In the foreseen IoT networks with diverse applications, update packets can be generated according to different event detection modes, such as random detection of burst status updates and periodic detection of regular meter readings. Therefore, it is necessary to consider the packet arrival type arising in various scenarios. In addition, queue service discipline that may potentially lead to AoI reduction is worth revisiting in NOMA networks. As such, it calls for additional efforts to further explore the AoI performance in NOMA-IoT networks while accounting for different arrival types and queue service disciplines.

In this paper, AoI performance in a NOMA-IoT network with two variants of traffic arrival models, i.e., Bernoulli and periodic arrivals, is characterized under two different queue service disciplines, i.e., FCFS and LCFS-PR. Capitalizing on the temporal queuing perspective, the service rates of different links are tightly entangled in their temporal queuing evolutions due to the wireless NOMA transmission. To overcome such difficulty, an iteration algorithm is proposed to decouple the intertwined service rate. Then, the AoI violation probability and average AoI for Bernoulli and periodic arrivals are analyzed under FCFS and LCFS-PR service disciplines. In summary, the main contributions of this paper can be summarized as follows:

• An analytical framework for evaluating AoI in the depicted network model is developed. The devised framework is eligible for encompassing both random Bernoulli and deterministic periodic arrivals and, meanwhile, incorporating the impact of FCFS and LCFS-PR disciplines on the AoI performance.
• The entangled transmission induced by the interdependence between queue buffer length and mutual interference is taken into consideration. Accordingly, an iterative numerical algorithm is proposed to deduce the queue service rate, and tractable expressions for the AoI violation probability and average AoI are derived.
• It follows from the results that by operating under LCFS-PR, better AoI violation probability and average AoI can be achieved than that under FCFS, whereas the gain is more prominent when there are more frequent arrivals. Moreover, there exists an evident disparity among the attained AoI enhancement triggered by LCFS-PR for each device. In addition, the periodic arrival pattern is preferable to the Bernoulli arrival pattern in terms of network average AoI for sporadic arrival, while this advantage gradually vanishes as the packet arrival becomes more intensive.

The rest of the paper is organized as follows. The system model is described in Section 2. The queuing model and the service rate are elaborated in Section 3. The detailed analysis of AoI performance under FCFS and LCFS-PR is presented in Section 4 and Section 5, respectively. Simulation results and discussions are provided in Section 6. Finally, Section 7 concludes this paper.

Mathematical Notations: Throughout this paper, the uppercase and lowercase bold letters are used to denote a matrix and a vector, respectively. ${\mathbf{I}}_k$ is the $k\times k$ identity matrix. ${\mathbf{1}}_k$ and ${\mathbf{0}}_k$ is a $k\times 1$ all ones and all zeros vector, respectively. The $L_1$ and $L_{\infty }$ norm of a vector $\mathbf{a}\in {\mathbb{R}}^{k\times 1}$ is given by ${∥\mathbf{a}∥}_1={\displaystyle \sum _{i=1}^k}\left|a_i\right|$ and ${∥\mathbf{a}∥}_{\infty }=\underset{1⩽i⩽k}{\max }\left|a_i\right|$, respectively. The superscript ${ }^{\mathrm{T}}$ represents the transpose operation. $\overline{x}$ denotes its complementary value, i.e., $1-x$. $\mathbb{E}\left[·\right]$ is the expectation function.

2. System Model

Consider an uplink NOMA IoT system composed of K devices, denoted by ${\mathrm{D}}_1,\dots ,{\mathrm{D}}_K$, and an access point (AP), as illustrated in Figure 1. All devices collect ambient information and encapsulate it into equal-sized packets. The pending packets are then sent to AP by utilizing NOMA. The transmissions are organized into discrete time slots, where the slot duration is the packet transmission period. Assuming power-law path-loss, the received signal power from ${\mathrm{D}}_k$ attenuates at rate $\kappa d_k^{-\alpha }$, in which $d_k$ is the distance from ${\mathrm{D}}_k$ to AP, $\alpha$ denotes the path-loss exponent, and $\kappa$ is the path-loss constant. Wireless channels are also subjected to shadow fading and small-scale fading. More specifically, the instantaneous channel gain from ${\mathrm{D}}_k$ to AP at the t-th time slot is determined by $h_k\left(t\right)=\kappa d_k^{\alpha }{\xi }_k{\left|g_k\left(t\right)\right|}^2$, where ${\xi }_k$ is the shadow fading gain with log-normal distribution, and $g_k\left(t\right)\sim \mathcal{CN}\left(0,1\right)$ characterizes the Rayleigh fading, which remains constant within one time slot and varies independently across time slots.

In this work, two variants of arrival patterns, i.e., Bernoulli arrival and periodic arrival, are considered. Despite the difference, both arrival processes can be modeled by the discrete phase-type distribution due to its versatility and flexibility. In general, the phase-type distribution gives the probability of hitting times until absorption in a Markov process with one absorbing state [29]. In order to characterize the packet arrival process of ${\mathrm{D}}_k$, we consider an absorbing discrete-time Markov chain (DTMC) with state space $\left\{0,1,\cdots ,{\tau }_k\right\}$, where state 0 represents the absorbing state and states $\left\{1,\cdots ,{\tau }_k\right\}$ are the transient states. In the context of packet arrival, the absorbing state implies packet arrival, whereas the transient states are represented by ${\tau }_k$ different phases. The transition matrix can be expressed as

$${\mathbf{\Phi }}_k=\left[\begin{array}{cc}1& \mathbf{0}\\ {\mathbf{v}}_k& {\mathbf{V}}_k\end{array}\right],$$

(1)

where ${\mathbf{V}}_k\in {\mathbb{R}}^{{\tau }_k\times {\tau }_k}$ is the substochastic transient matrix, and ${\mathbf{v}}_k={\mathbf{1}}_{{\tau }_k}-{\mathbf{V}}_k{\mathbf{1}}_{{\tau }_k}\in {\mathbb{R}}^{{\tau }_k\times 1}$ represents the absorption probability from a given transient state. The probability of starting from any of its transient state is formulated as an initialization vector ${\beta }_k=\left[{\beta }_1,\cdots ,{\beta }_{{\tau }_k}\right]\in {\mathbb{R}}^{1\times {\tau }_k}$, in which ${\beta }_i$ is the probability that the DTMC starts from the transient state i. Hence, the parameter tuple $\left({\beta }_k,{\mathbf{V}}_k\right)$ determines a phase-type distribution.

The phase-type distribution provides generalization across multiple traffic arrival models. The periodic arrival for ${\mathrm{D}}_k$ with deterministic generation cycle ${\tau }_k$ can be characterized by setting ${\mathbf{V}}_k$ as

$${\mathbf{V}}_k=\left[\begin{array}{ccccc}0& 1& 0& \cdots & 0\\ 0& 0& 1& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 0& 1\\ 0& 0& \cdots & 0& 0\end{array}\right],$$

(2)

where the transition probability between transient states is equal to 1 because the packet arrival process is deterministic.

The generation cycle for periodic arrival is fixed as ${\tau }_k$, which also corresponds to ${\tau }_k$ phases. Without loss of generality, the initialization vector is given by ${\beta }_k=\left[1,{\mathbf{0}}_{{\tau }_k-1}^{\mathrm{T}}\right]$. Concerning the Bernoulli arrival at ${\mathrm{D}}_k$, we have ${\tau }_k=1$ because there exists only one phase. As such, the parameter tuple characterizing the Bernoulli arrival degenerates into $\left({\beta }_k,{\mathbf{V}}_k\right)=\left(1,1-{\nu }_k\right)$, where ${\nu }_k$ denotes the packet arrival probability at each time slot.

Each device has an infinite-size buffer to accommodate the arrived update packets. In addition, we consider the following two queue service disciplines:

• FCFS: All packets are served in the order of arrivals. If the queue is not empty, then a newly arrived packet has to wait until the transmission of the foregoing packet completes. Otherwise, a newly arrived packet can be served directly.
• LCFS-PR: The newest packet is given priority. It can immediately enter service upon arrival, whereas the ongoing service will be interrupted and postponed. Only when the newest packet completes its service, the suspended packet with the latest arrival timestamp restarts transmission.

Assume that only when the signal-to-interference-plus-noise ratio (SINR) received by AP exceeds the decoding threshold, i.e., ${\theta }_k$, the transmission of ${\mathrm{D}}_k$ is successful. Upon successful delivery, AP feeds back an ACK. While in the case of transmission failure, a NACK is sent by AP and the undelivered packet is stored in the buffer waiting to be retransmitted. In particular, the ACK/NACK message is fed back instantaneously and error-freely. Without loss of generality, the queuing activities are assumed to be followed with the early-arrival late-departure model. That is to say, packets arrive at and depart from the queue at the beginning and the end of each time slot, i.e., $t^{+}$ and $t^{-}$, respectively.

In uplink NOMA networks, SIC is utilized at AP to successively extract each device’s signal. The link quality metric that is used for ordering devices in this work is the mean signal power. Without loss of generality, we index each device based on the descending order of its link distance, i.e., $d_1>d_2>\cdots >d_K$. Let $Q_k\left(t\right)$ represent ${\mathrm{D}}_k$’s queue length at time slot t. Since no packet is sent when the transmission queue is empty, we can write the SINR of ${\mathrm{D}}_k$ as follows

$$\begin{array}{cc}\hfill {\mathrm{SINR}}_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)& =\frac{P_{\mathrm{tx}}{h}_k\left(t\right)\mathbb{1}\left(Q_k\left(t\right)>0\right)}{{\displaystyle \sum _{j=1}^{k-1}}{P}_{\mathrm{tx}}{h}_j\left(t\right)\mathbb{1}\left(Q_j\left(t\right)>0\right)+N_0},\hfill \end{array}$$

(3)

where $\mathbb{1}\left(·\right)$ is a binary indicator function, that takes a value of 1 under the condition and 0 otherwise, $P_{\mathrm{tx}}$ and $N_0$ are the transmit power and the noise power, respectively. The superscript ${\psi }_1\in \left\{\mathrm{F},\mathrm{L}\right\}$ represents the FCFS (${\psi }_1=\mathrm{F}$) and the LCFS-PR (${\psi }_2=\mathrm{L}$) queue discipline, respectively. And ${\psi }_2\in \left\{\mathrm{B},\mathrm{P}\right\}$ represents the Bernoulli (${\psi }_2=\mathrm{B}$) and periodic (${\psi }_2=\mathrm{P}$) arrival pattern, respectively.

Throughout this paper, information freshness is measured by AoI, which is formally defined as the time difference from the generation time of the latest received (freshest) update packet to the current system time. Let ${\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)$ denote ${\mathrm{D}}_k$’s AoI at time slot t, in which the queue discipline and the packet arrival pattern are specified by the superscript $\left({\psi }_1,{\psi }_2\right)$. ${\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)$ evolves based on the dynamic packet arrival and delivery, which can be mathematically described as

$${\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t+1\right)=\left\{\begin{array}{cc}min\left\{t+1-G_k\left(t\right),{\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)\right\}+1,\hfill & \hfill \mathrm{case}1,\\ {\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)+1,\hfill & \hfill \mathrm{case}2,\end{array}\right.$$

(4)

where $G_k\left(t\right)$ is the arrival time of the delivered packet by ${\mathrm{D}}_k$ at time slot t, case 1 represents that the packet is successfully delivered at ${\left(t+1\right)}^{-}$, and case 2 denotes that the transmission fails or there is no transmission at ${\left(t+1\right)}^{-}$. It is noteworthy that in case 1, the delivery of a preempted packet under the LCFS-PR discipline does not trigger the AoI performance reset because its information is obsolete.

In fact, ${\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)$ constructs a time-varying process. Therefore, we need to focus on some summary metrics for the system’s performance. A widely used fundamental metric is the AoI violation probability, which gives the probability that the AoI exceeds a certain age threshold and characterizes the information freshness fluctuation over time. In a stationary and ergodic queuing system, the AoI violation probability can be equated with the asymptotic frequency distribution [16], which is given by

$$P_k^{\left({\psi }_1,{\psi }_2\right)}\left(\delta \right)\triangleq \underset{t\to \infty }{lim\; sup}\mathbb{P}\left\{{\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)>\delta \right\}=\underset{\mathrm{\Omega }\to \infty }{lim\; sup}\frac{1}{\mathrm{\Omega }}\sum _{t=1}^{\mathrm{\Omega }}\mathbb{1}\left({\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)>\delta \right).$$

(5)

Aside from the AoI violation probability, we also evaluate the time-average AoI. Using the above, the time-average AoI at the destination AP from ${\mathrm{D}}_k$ is defined as

$${\overline{\Delta }}_k^{\left({\psi }_1,{\psi }_2\right)}\triangleq \underset{\mathrm{\Omega }\to \infty }{lim\; sup}\frac{1}{\mathrm{\Omega }}\sum _{t=1}^{\mathrm{\Omega }}{\Delta }_k^{\left({\psi }_1,{\psi }_2\right)}\left(t\right).$$

(6)

Considering all devices, the network time-average AoI can be expressed as

$${\overline{\Delta }}_{\mathrm{ntw}}^{\left({\psi }_1,{\psi }_2\right)}\triangleq \frac{1}{K}\sum _{k=1}^K{\overline{\Delta }}_k^{\left({\psi }_1,{\psi }_2\right)}.$$

(7)

3. Queue Analysis

3.1. Queuing Model

From the temporal evolution perspective, the queuing dynamics under both Bernoulli and periodic arrivals can be abstracted by a unified PH/G/1 queue. In particular, the queue service rate of ${\mathrm{D}}_k$, denoted by ${\mu }_k\left(t\right)$, is determined by the NOMA transmission success probability given below

$${\mu }_k\left(t\right)=\mathbb{P}\left\{\bigcap _{i=k,\mathbb{1}\left(Q_i\left(t\right)>0\right)}^K\left\{{\mathrm{SINR}}_i^{\left({\psi }_1,{\psi }_2\right)}\left(t\right)⩾{\theta }_i\right\}\right\}.$$

(8)

We use two binary variables $A_k\left(t\right)$ and $D_k\left(t\right)$ to represent the status of packet arrival and packet departure for ${\mathrm{D}}_k$ at time slot t, respectively, of which the value is set to 1 upon arrival or successful transmission, and 0 otherwise. As a result, the temporal evolution of $Q_k\left(t\right)$ can be given by

$$Q_k\left(t+1\right)=Q_k\left(t\right)-\mathbb{1}\left(Q_k\left(t\right)>0\right)D_k\left(t\right)+A_k\left(t\right).$$

(9)

We can infer from (3) and (8) that $D_k\left(t\right)$ depends on the queue length of all the other queues, i.e., $\left[Q_1\left(t\right),\dots ,Q_{k-1}\left(t\right),Q_{k+1}\left(t\right),\dots ,Q_K\left(t\right)\right]$. As a result, the temporal evolution of one particular queue depends on the queue status of all the others, thus consequently resulting in the interdependence between the service process and queue status. The problem is further exacerbated by the fact that the service rate of each device varies with the time slot index t, as we note from (8). Therefore, a temporal correlated queuing process is induced, complicating the subsequent analysis extremely. In that respect, we focus on the asymptotic stationary regime and regard the packet departure process from ${\mathrm{D}}_k$ as identical as its stationary distribution over time [21,23]. Specifically, under the Bernoulli arrival model, the packet departs the queue with success probability ${\mu }_k=\underset{t\to \infty }{lim}{\mu }_k\left(t\right)$. Note that under the periodic arrival model, a packet generation cycle for ${\mathrm{D}}_k$ contains ${\tau }_k$ time slots, with each equivalent to one phase. Accordingly, the stationary queue transition state can be classified into ${\tau }_k$ phases. Taking this point into account, we approximate the queue service rate under the periodic arrival model as ${\mu }_k={\mathbb{E}}_{{\tau }_k}\left[\underset{t\to \infty }{lim}{\mu }_k\left(t\right)\right]$, where the success probability is averaged across ${\tau }_k$ different phases within the same packet generation cycle to alleviate the dependence.

The probability transition matrix of the two-dimensional DTMC jointly constructed by ${\mathrm{D}}_k$’s queue length and its phase can be written as

$${\mathbf{P}}_k=\left[\begin{array}{cc}{\mathbf{B}}_{k,1}& {\mathbf{B}}_{k,0}\\ {\mathbf{A}}_{k,2}& {\mathbf{A}}_{k,1}& {\mathbf{A}}_{k,0}\\ & {\mathbf{A}}_{k,2}& {\mathbf{A}}_{k,1}& {\mathbf{A}}_{k,0}\\ & & \ddots & \ddots & \ddots \end{array}\right],$$

(10)

where ${\mathbf{B}}_{k,1}={\mathbf{V}}_k$ and ${\mathbf{B}}_{k,0}={\mathbf{v}}_k{\beta }_k$ are the boundary substochastic matrices with size ${\tau }_k\times {\tau }_k$. In addition, ${\mathbf{A}}_{k,2}={\mu }_k{\mathbf{V}}_k$, ${\mathbf{A}}_{k,1}={\mu }_k{\mathbf{B}}_{k,0}+{\overline{\mu }}_k{\mathbf{V}}_k$, and ${\mathbf{A}}_{k,0}={\overline{\mu }}_k{\mathbf{B}}_{k,0}$ are ${\tau }_k\times {\tau }_k$ substochastic matrices characterizing three potential queue length state transitions within all ${\tau }_k$ phases, i.e., the queue length minus 1, remains unchanged, and add 1, respectively.

The stationary distribution of ${\mathrm{D}}_k$’s queue length $Q_k\left(t\right)$ and its phase $J_k\left(t\right)$, i.e., ${\pi }_{kqj}\triangleq \underset{t\to \infty }{lim}\mathbb{P}\{Q_k\left(t\right)=q,J_k\left(t\right)=j\}$ ($q=0,1,\dots$, $j=1,\dots ,{\tau }_k$), can be uniquely derived by solving the following equations

$${\mathit{\pi }}_k{\mathbf{P}}_k={\mathit{\pi }}_k,{\mathit{\pi }}_k\mathbf{1}=1,$$

(11)

where ${\mathit{\pi }}_k$ is expressed in block form as ${\mathit{\pi }}_k=\left[{\mathit{\pi }}_{k0},{\mathit{\pi }}_{k1},\cdots \right]$ with ${\mathit{\pi }}_{kq}=\left[{\pi }_{kq1},\cdots ,{\pi }_{kq{\tau }_k}\right]$.

With Bernoulli arrival, we have ${\tau }_k=1$ and $\left({\beta }_k,{\mathbf{V}}_k\right)=\left(1,1-{\nu }_k\right)$. Hence, ${\mathbf{P}}_k$ degenerates into

$${\mathbf{P}}_k=\left[\begin{array}{cc}{\overline{\nu }}_k& {\nu }_k\\ {\overline{\nu }}_k{\mu }_k& {\lambda }_k& {\nu }_k{\overline{\mu }}_k\\ & {\overline{\nu }}_k{\mu }_k& {\lambda }_k& {\nu }_k{\overline{\mu }}_k\\ & & \ddots & \ddots & \ddots \end{array}\right],$$

(12)

in which ${\lambda }_k=1-{\nu }_k{\overline{\mu }}_k-{\overline{\nu }}_k{\mu }_k$. Therefore, from (11), we can explicitly derive that

$${\pi }_{kq}=\left\{\begin{array}{cc}1-\frac{{\nu }_k}{{\mu }_k},\hfill & q=0,\hfill \\ \frac{{\nu }_k}{{\mu }_k}\left(1-\frac{{\nu }_k{\overline{\mu }}_k}{{\mu }_k{\overline{\nu }}_k}\right){\left(\frac{{\nu }_k{\overline{\mu }}_k}{{\mu }_k{\overline{\nu }}_k}\right)}^{q-1},\hfill & q⩾1.\hfill \end{array}\right.$$

(13)

With periodic arrival, the queuing process is of the quasi-birth-death (QBD) type, resulting in a block tridiagonal structure for the probability transition matrix as shown in (10). By utilizing the matrix-analytic method (MAM), the stationary probability can be given in a matrix-geometric form as

$${\mathit{\pi }}_{kq}={\mathit{\pi }}_{k1}{\mathbf{R}}_k^{q-1},q⩾1,$$

(14)

where ${\mathbf{R}}_k$ is the non-negative rate matrix that can be determined by the unique minimal solution of the quadratic matrix equation given by [30]:

$${\mathbf{R}}_k^2{\mathbf{A}}_{k,2}+{\mathbf{R}}_k{\mathbf{A}}_{k,1}+{\mathbf{A}}_{k,0}={\mathbf{R}}_k.$$

(15)

In general, the rate matrix ${\mathbf{R}}_k$ can be obtained by several numerical algorithms including the basic linear progression algorithm and improved algorithms with quadratic convergence [29]. In view of the fact that ${\mathbf{A}}_{k,0}$ is the product of a column vector ${\overline{\mu }}_k{\mathbf{v}}_k$ and a normalized row vector ${\beta }_k$, ${\mathbf{R}}_k$ can be expressed as ${\mathbf{R}}_k={\mathbf{A}}_{k,0}{\left({\mathbf{I}}_{{\tau }_k}-{\mathbf{A}}_{k,1}-\mathrm{sp}\left({\mathbf{R}}_k\right){\mathbf{A}}_{k,2}\right)}^{-1}$, where $\mathrm{sp}\left({\mathbf{R}}_k\right)$ is the spectral radius of ${\mathbf{R}}_k$ which can be derived by solving the scalar equation $x={\beta }_k{\left({\mathbf{I}}_{{\tau }_k}-{\mathbf{A}}_{k,1}-x{\mathbf{A}}_{k,2}\right)}^{-1}{\overline{\mu }}_k{\mathbf{v}}_k$ for x in $\left(0,1\right)$. Once ${\mathbf{R}}_k$ is obtained, ${\mathit{\pi }}_{k0}$ and ${\mathit{\pi }}_{k1}$ can be further obtained by solving the following linear matrix equation

$$\left[{\mathit{\pi }}_{k0},{\mathit{\pi }}_{k1}\right]\left[\begin{array}{cc}{\mathbf{B}}_{k,1}& {\mathbf{B}}_{k,0}\\ {\mathbf{A}}_{k,2}& {\mathbf{R}}_k{\mathbf{A}}_{k,2}+{\mathbf{A}}_{k,1}\end{array}\right]=\left[{\mathit{\pi }}_{k0},{\mathit{\pi }}_{k1}\right],$$

(16)

with the normalization ${\mathit{\pi }}_{k0}{\mathbf{1}}_{{\tau }_k}+{\mathit{\pi }}_{k1}{\left({\mathbf{I}}_{{\tau }_k}{\mathbf{R}}_k\right)}^{-1}{\mathbf{1}}_{{\tau }_k}=1$.

3.2. Service Rate

In this subsection, we provide a step-by-step analysis of the service rate ${\mu }_k$. Due to the interdependence among all queues, ${\mu }_k$ depends on the queue statuses of the other $K-1$ queues. Therefore, there exist $2^{K-1}$ situations, with each corresponding to a specific combination of queue status of all other queues. Focusing on calculating ${\mu }_k$, we need to consider different situations of queue status combinations. Specifically, for situation m, where $m=1,2,\cdots ,2^K-1$, the queue status of ${\mathrm{D}}_j$ is represented by ${\zeta }_{k,j}^m\in \left\{0,1\right\}$. Therefore, the service rate ${\mu }_k$ can be written as

$${\mu }_k=\sum _{m=1}^{2^{K-1}}\prod _{j=1,j\ne k}^K\left|{\zeta }_{k,j}^m-{\chi }_j\right|{\mu }_{k,m}^{\mathrm{c}},$$

(17)

where ${\chi }_j={\parallel {\mathit{\pi }}_{j0}\parallel }_1$ is the empty probability of ${\mathrm{D}}_j$’s queue, ${\mu }_{k,m}^{\mathrm{c}}$ is the conditional service rate given in the m-th queue status situation. Without loss of generality, we assume that the number of queues with a non-empty buffer in the m-th situation is ${\rho }_m$, where ${\rho }_m\in \left\{1,\dots ,K\right\}$. The devices having non-empty queues are indexed as ${\sigma }_1<\cdots <{\sigma }_{\varrho }<\cdots <{\sigma }_{{\rho }_m}$, wherein ${\mathrm{D}}_k$’s index is particularly set as ${\sigma }_{\varrho }$. As such, ${\mu }_{k,m}^{\mathrm{c}}$ can be expressed as

$${\mu }_{k,m}^{\mathrm{c}}=\mathbb{P}\left\{\bigcap _{i=\varrho }^{L_m}{\mathrm{SINR}}_{{\sigma }_i}^{\left({\psi }_1,{\psi }_2\right)}⩾{\theta }_{{\sigma }_i}\right\}.$$

(18)

Apparently, the key to deriving ${\mu }_{k,m}^{\mathrm{c}}$ is to figure out the conditional joint probability, which is presented by the following proposition.

Proposition 1. 

In the depicted network, the conditional service rate of ${\mathrm{D}}_k$ with index ${\sigma }_{\varrho }$ conditioned on the m-th situation can be derived as

$${\mu }_{k,m}^{\mathrm{c}}=\exp \left(\omega {\mathbf{U}}^{-1}\gamma \right)\det {\mathbf{U}}^{-1}\prod _{i=1}^{{\rho }_m}{\omega }_i{\left(\omega {\mathbf{U}}^{-1}{\mathbf{e}}_i\right)}^{-1},$$

(19)

where ${\mathbf{e}}_i$ is an unit vector with size ${\rho }_m\times 1$, and its i-th element equals to 1, $\omega =\left[{\omega }_1,\dots ,{\omega }_{{\rho }_m}\right]$ is with size $1\times {\rho }_m$ and ${\omega }_i={\left(\frac{P_{\mathrm{tx}}}{N_0}\kappa {\xi }_{{\sigma }_i}{d}_{{\sigma }_i}^{-\alpha }\right)}^{-1}$, $\gamma ={\left[{\mathbf{0}}_{\varrho -1}^{\mathrm{T}},-{\gamma }_0^{\mathrm{T}}\right]}^{\mathrm{T}}$ is with size ${\rho }_m\times 1$ and ${\gamma }_0={\left[{\gamma }_{\varrho },\dots ,{\gamma }_{{\rho }_m}\right]}^{\mathrm{T}}$, wherein ${\gamma }_i=\frac{-{\theta }_{{\sigma }_i}}{1+{\theta }_{{\sigma }_i}}$ for $1⩽i⩽{\rho }_m$, and $\mathbf{U}$ is a ${\rho }_m\times {\rho }_m$ M-matrix [31] expressed in the following block form as

$$\mathbf{U}=\left[\begin{array}{cc}{\mathbf{I}}_{\varrho -1}& {\mathbf{0}}_{\left(\varrho -1\right)\times \left({\rho }_m-\varrho +1\right)}\\ {\gamma }_0{\mathbf{1}}_{\varrho -1}^{\mathrm{T}}& \mathbf{\Gamma }\mathbf{L}+{\mathbf{I}}_{{\rho }_m-\varrho +1}\end{array}\right],$$

(20)

in which Γ is a $\left({\rho }_m-\varrho +1\right)\times \left({\rho }_m-\varrho +1\right)$ diagonal matrix with the elements of ${\gamma }_0={\left[{\gamma }_{\varrho },\dots ,{\gamma }_{{\rho }_m}\right]}^{\mathrm{T}}$ on the diagonal, and $\mathbf{L}$ is a $\left({\rho }_m-\varrho +1\right)\times \left({\rho }_m-\varrho +1\right)$ lower triangular matrix with all elements equal to 1.

Proof. 

The proof is provided in Appendix A. □

According to Proposition 1, the expression of ${\mu }_k$ can be further derived by substituting (19) into (17). However, we find that ${\mu }_k$ still relates to the queue empty probability of other devices. More specifically, ${\mu }_k$ is a function of ${\mathit{\pi }}_{j0}$ ($j\ne k$). Similarly, ${\mathit{\pi }}_{k0}$ that can be obtained by solving the Markov chain with a probability transition matrix constructed by ${\mu }_k$ is also required for calculating the service rate of the other $K-1$ devices. In essence, this is an interdependent problem. By leveraging the fixed-point theory [32], an iterative algorithm is devised to calculate the service rate. The overall algorithm is demonstrated in Algorithm 1.

Algorithm 1: Numerical iterative algorithm

1:  Initialization: $l=0$; ${\mathit{\pi }}_{10}^{\left(l\right)},\dots ,{\mathit{\pi }}_{K0}^{\left(l\right)}$; 2:  repeat 3:     for $k=1$ to K do 4:        Enumerate the queue status combination, i.e., ${\zeta }_{k,j}^m,\forall j\ne k,\forall m\in \left\{1,\dots ,2^{K-1}\right\}$; 5:        Calculate the conditional service rate ${\mu }_{k,m}^{\mathrm{c}},\forall m\in \left\{1,\dots ,2^{K-1}\right\}$ by Proposition 1; 6:        Update ${\mu }_k^{\left(l+1\right)}$ by substituting ${\chi }_j={\parallel {\mathit{\pi }}_{j0}^{\left(l+\mathbb{1}\left(j<k\right)\right)}\parallel }_1$ into (17); 7:        Reconstruct the probability transition matrix ${\mathbf{P}}_k$ as (10) by using ${\mu }_k^{\left(l+1\right)}$; 8:        Update ${\mathit{\pi }}_{k0}^{\left(l+1\right)}$ by solving the equations given by (13) and (16) for Bernoulli and periodic arrival, respectively; 9:     end for 10:    Update $l\leftarrow l+1$; 11:    if ${\mu }_k^{\left(l\right)}<{\nu }_k$ for Bernoulli arrival $|{\mu }_k^{\left(l\right)}<\frac{1}{{\tau }_k}$ for periodic arrival, $\exists k\in \left\{1,\dots ,K\right\}$ then 12:        Break; 13:    end if 14:  until  $\parallel {\mathit{\pi }}_{k0}^{\left(l\right)}-{\mathit{\pi }}_{k0}^{\left(l-1\right)}{\parallel }_{\infty }<\epsilon ,\forall k\in \left\{1,\dots ,K\right\}$ 15:  Return: ${\mathit{\pi }}_{k0}\leftarrow {\mathit{\pi }}_{k0}^{\left(l\right)},\forall k\in \left\{1,\dots ,K\right\}$, and ${\mu }_k$ based on (17);

Within the proposed algorithm, the pre-defined error tolerance is given by $\epsilon$. In particular, we update ${\mu }_k^{\left(l+1\right)}$ by leveraging ${\mathit{\pi }}_{10}^{\left(l+1\right)},\dots ,{\mathit{\pi }}_{k-10}^{\left(l+1\right)},{\mathit{\pi }}_{k+10}^{\left(l\right)},\dots ,{\mathit{\pi }}_{K0}^{\left(l\right)}$ in the l-th iteration. The newly obtained service rate is then used to rebuild the probability transition matrix, based on which we can update ${\mathrm{D}}_k$’s stationary probability. This iteration procedure is applied for both Bernoulli and periodic arrival types, whilst the difference lies in solving the specific Markov chain. Loynes’s condition is verified to guarantee queue stability. After each iteration, we check the convergence threshold and end the iterations under the given precision. Finally, ${\mu }_k$ is derived by substituting the derived ${\mathit{\pi }}_{j0}$ ($j\ne k$) into (17). Note that the K-dimensional DTMC, which is built by the queue lengths of all devices, is homogeneous, irreducible, and aperiodic. Algorithm 1 converges after the fixed-point iteration due to the fact that there uniquely exists a steady-state solution. The temporal dynamic of each queue can be characterized by leveraging Algorithm 1. Based on this, we can present the analysis of AoI statistics in the following subsection.

4. AoI Analysis under FCFS

In this section, we delve into the analysis of AoI under the FCFS queue discipline. Based on the Bernoulli arrival and periodic arrival, analytical expressions for the AoI violation probability and time-average AoI are presented.

As an initial step, we first concentrate on the temporal evolution of AoI. Let $t_{k,i}$ and $t_{k,i}^{\prime }$ represent the arrival and departure time of the i-th packet of ${\mathrm{D}}_k$, respectively. It should be noted that the AoI sample path can be divided along the packet arrival boundary into a set of non-intersecting segments. Specifically, the i-th segment of ${\mathrm{D}}_k$’s AoI falls into the set $\left\{\left.{\Delta }_k^{\left(\mathrm{F},{\psi }_2\right)}\left(t\right)\right|t-t_{k,i}<{\Delta }_k^{\left(\mathrm{F},{\psi }_2\right)}\left(t\right)⩽t-t_{k,i-1}\right\}$ for $i=1,2,\dots$, as illustrated in Figure 2. With FCFS, $G_{k,i}^{\left(\mathrm{F},{\psi }_2\right)}$ is the time duration holding the condition that AoI exceeds a given age constraint $\delta$, i.e., ${\Delta }_k^{\left(\mathrm{F},{\psi }_2\right)}\left(t\right)>\delta$, in the i-th AoI segment. Moreover, we denote $X_{k,i}=t_{k,i}-t_{k,i-1}$ and $T_{k,i}=t_{k,i}^{\prime }-t_{k,i}$ as the inter-arrival time and the system time of the i-th packet of ${\mathrm{D}}_k$, respectively. Thus, we have

$$G_{k,i}^{\left(\mathrm{F},{\psi }_2\right)}=\left\{\begin{array}{cc}\max \left\{X_{k,i}-\left(\delta -T_{k,i}\right),0\right\},\hfill & \mathrm{if}{T}_{k,i}<\delta ,\hfill \\ X_{k,i},\hfill & \mathrm{if}{T}_{k,i}⩾\delta .\hfill \end{array}\right.$$

(21)

It can be inferred from the queuing evolution that the AoI process is stationary and ergodic [16]. Consequently, the AoI violation probability of ${\mathrm{D}}_k$ can be represented by

$$P_k^{\left(\mathrm{F},{\psi }_2\right)}\left(\delta \right)=\underset{\mathrm{\Omega }\to \infty }{lim\; sup}\frac{1}{\mathrm{\Omega }}\sum _{t=0}^{\mathrm{\Omega }}\mathbb{1}\left({\Delta }_k^{\left(\mathrm{F},{\psi }_2\right)}\left(t\right)>\delta \right)=\underset{\mathrm{\Omega }\to \infty }{lim\; sup}\frac{1}{\mathrm{\Omega }}\left(\sum _{i=1}^{N\left(\mathrm{\Omega }\right)}{G}_{k,i}^{\left(\mathrm{F},{\psi }_2\right)}+\iota \left(\mathrm{\Omega }\right)\right),$$

(22)

where $N\left(\mathrm{\Omega }\right)$ is the number of AoI segments before time $\mathrm{\Omega }$, and $\iota \left(\mathrm{\Omega }\right)$ denotes the residual time duration of which the condition ${\Delta }_k^{\left(\mathrm{F},{\psi }_2\right)}\left(t\right)>\delta$ holds after the $N\left(\mathrm{\Omega }\right)$-th segment and before timestamp $\mathrm{\Omega }$. Note that $\frac{\iota \left(\mathrm{\Omega }\right)}{\mathrm{\Omega }}$ approaches zero as $\mathrm{\Omega }$ goes to infinity, which further results in

$$\begin{array}{cc}& P_k^{\left(\mathrm{F},{\psi }_2\right)}\left(\delta \right)=\underset{\mathrm{\Omega }\to \infty }{lim\; sup}\frac{1}{\mathrm{\Omega }}\sum _{i=1}^{N\left(\mathrm{\Omega }\right)}{G}_{k,i}^{\left(\mathrm{F},{\psi }_2\right)}=\underset{\mathrm{\Omega }\to \infty }{lim\; sup}\frac{N\left(\mathrm{\Omega }\right)}{\mathrm{\Omega }}\frac{1}{N\left(\mathrm{\Omega }\right)}\sum _{i=1}^{N\left(\mathrm{\Omega }\right)}{G}_{k,i}^{\left(\mathrm{F},{\psi }_2\right)}\hfill \\ & \stackrel{\left(a\right)}{=}{\left(\underset{\mathrm{\Omega }\to \infty }{lim\; sup}\frac{{\sum }_{i=1}^{N\left(\mathrm{\Omega }\right)}{X}_{k,i}}{N\left(\mathrm{\Omega }\right)}\right)}^{-1}\underset{\mathrm{\Omega }\to \infty }{lim\; sup}\frac{1}{N\left(\mathrm{\Omega }\right)}\sum _{i=1}^{N\left(\mathrm{\Omega }\right)}{G}_{k,i}^{\left(\mathrm{F},{\psi }_2\right)},\hfill \end{array}$$

(23)

where $\left(a\right)$ is due to the fact that $N\left(\mathrm{\Omega }\right)$ goes to infinity almost surely with increasing $\mathrm{\Omega }$, and hence the time duration $\mathrm{\Omega }$ can be disassembled into the interarrival times. By noticing that the system is stationary and ergodic, the packet index subscript i can be omitted for simplification. As a result, we can finally express the AoI violation probability as

$$P_k^{\left(\mathrm{F},{\psi }_2\right)}\left(\delta \right)=\frac{\mathbb{E}\left[G_k^{\left(\mathrm{F},{\psi }_2\right)}\right]}{\mathbb{E}\left[X_k\right]}.$$

(24)

Following (24), it can be seen that both $\mathbb{E}\left[X_k\right]$ and $\mathbb{E}\left[G_k^{\left(\mathrm{F},{\psi }_2\right)}\right]$ play a role of paramount importance in characterizing the AoI violation probability. Nevertheless, the detailed derivations differ from each other under different arrival models. Specifically, $\mathbb{E}\left[X_k\right]$ is equal to $\frac{1}{{\nu }_k}$ and ${\tau }_k$ for Bernoulli and periodic arrivals, respectively. In the respect of $\mathbb{E}\left[G_k^{\left(\mathrm{F},{\psi }_2\right)}\right]$, we unfold the analysis as follows.

Under the Bernoulli arrival model, $\mathbb{E}\left[G_k^{\left(\mathrm{F},\mathrm{B}\right)}\right]$ can be calculated according to (21) as

$$\begin{array}{cc}\hfill \mathbb{E}\left[G_k^{\left(\mathrm{F},\mathrm{B}\right)}\right]& =\sum _{t=1}^{\infty }\mathbb{E}\left[\left.G_k^{\left(\mathrm{F},\mathrm{B}\right)}\right|T_k=t\right]\mathbb{P}\left\{T_{k,i}=t\right\}\hfill \\ & =\sum _{t=1}^{\delta -1}\sum _{x=\delta -t+1}^{\infty }\left(x-\delta +t\right)\mathbb{P}\left\{X_k=x,T_k=t\right\}+\sum _{t=\delta }^{\infty }\sum _{x=1}^{\infty }x\mathbb{P}\left\{X_k=x,T_k=t\right\}.\hfill \end{array}$$

(25)

Furthermore, the joint probability mass function (PMF) of $X_k$ and $T_k$ is given by the following lemma.

Lemma 1.

With the FCFS queue discipline, the joint PMF of the inter-arrival time $X_k$ and system time $T_k$ for ${\mathrm{D}}_k$, i.e., $\mathbb{P}\left\{X_k=x,T_k=t\right\}$, for $x⩾1,t⩾1$, under the Bernoulli arrival model is given by

$$\begin{array}{cc}& \mathbb{P}\left\{X_k=x,T_k=t\right\}=\hfill \\ & \left({\mu }_k{\overline{\mu }}_k^{t-1}\left(1-{\left(\frac{{\overline{\mu }}_k}{{\overline{\nu }}_k}\right)}^x\right)+\frac{{\mu }_k}{{\overline{\mu }}_k^2{\nu }_k}\left({\overline{\nu }}_k{\left(\frac{{\overline{\mu }}_k}{{\overline{\nu }}_k}\right)}^t-{\overline{\mu }}_k^t\right){\left(\frac{{\overline{\mu }}_k}{{\overline{\nu }}_k}\right)}^x\left({\mu }_k-{\nu }_k\right)\right){\left(1-{\nu }_k\right)}^{x-1}{\nu }_k.\hfill \end{array}$$

(26)

Proof. 

The proof is provided in Appendix B. □

By leveraging Lemma 1 together with (25), we can obtain $\mathbb{E}\left[G_k^{\left(\mathrm{F},\mathrm{B}\right)}\right]$ for the Bernoulli arrival model.

Under the periodic arrival model, the inter-arrival time of ${\mathrm{D}}_k$ is fixed as ${\tau }_k$. Based on the relation between the inter-arrival ${\tau }_k$ and the given age constraint $\delta$, $G_k^{\left(\mathrm{F},\mathrm{P}\right)}$ given in (21) consequently degenerates into different cases as follows

$$G_k^{\left(\mathrm{F},\mathrm{P}\right)}=\left\{\begin{array}{cc}0,\hfill & \mathrm{if}{T}_k<\delta -{\tau }_k,\hfill \\ {\tau }_k+T_k-\delta ,\hfill & \mathrm{if}\varsigma \left({\tau }_k\right)⩽T_k<\delta ,\hfill \\ {\tau }_k,\hfill & \mathrm{if}{T}_k⩾\delta .\hfill \end{array}\right.$$

(27)

where $\varsigma \left({\tau }_k\right)=\max \left\{\delta -{\tau }_k,0\right\}+\mathbb{1}\left(\delta ⩽{\tau }_k\right)$. Therefore, $\mathbb{E}\left[G_k^{\left(\mathrm{F},\mathrm{P}\right)}\right]$ can be derived by

$$\mathbb{E}\left[G_k^{\left(\mathrm{F},\mathrm{P}\right)}\right]=\sum _{t=\varsigma \left({\tau }_k\right)}^{\delta -1}\left({\tau }_k+t-\delta \right)\mathbb{P}\left\{T_k=t\right\}+\sum _{t=\delta }^{\infty }{\tau }_k\mathbb{P}\left\{T_k=t\right\}.$$

(28)

As mentioned in Section 3.1, the departures from the same device over time are considered to be temporally independent, and thus, the packet departure process can be characterized by a geometric distribution. Therefore, the system time $T_k$ under the periodic arrival model has the following PMF

$$\mathbb{P}\left\{T_k=t\right\}={\phi }_k{\left(1-{\phi }_k\right)}^t,t=1,2,\cdots ,$$

(29)

where ${\phi }_k$ can be determined by solving the equation ${\phi }_k={\mu }_k-{\mu }_k{\left(1-{\phi }_k\right)}^{{\tau }_k}$ with $0<{\phi }_k<{\mu }_k$ [17]. Combining (28) and (29), we have $\mathbb{E}\left[G_k^{\left(\mathrm{F},\mathrm{P}\right)}\right]$ for the periodic arrival model.

Armed with these results, we can concretely characterize the AoI violation probability under both Bernoulli and periodic arrival models when the FCFS queue discipline is applied. The details are given by the following proposition.

Proposition 2.

In the depicted network, the expression of AoI violation probability of ${\mathrm{D}}_k$ with Bernoulli arrival under FCFS is obtained as

$$\begin{array}{cc}\hfill P_k^{\left(\mathrm{F},\mathrm{B}\right)}\left(\delta \right)& =\frac{{\mu }_k^2{\overline{\nu }}_k^{\delta }-{\mu }_k^3{\overline{\nu }}_k^{\delta }-2{\overline{\mu }}_k^{\delta }{\mu }_k{\nu }_k+{\overline{\mu }}_k^{\delta }{\mu }_k^2{\nu }_k\left(1-\delta \right)+{\overline{\mu }}_k^{\delta }{\nu }_k^2\left(1+\delta {\mu }_k\right)}{{\mu }_k{\overline{\mu }}_k\left({\mu }_k-{\nu }_k\right)}\hfill \\ & +\frac{{\left({\overline{\mu }}_k/{\overline{\nu }}_k\right)}^{\delta }\left({\mu }_k{\overline{\nu }}_k+{\overline{\nu }}_k^{\delta }\left({\nu }_k-{\mu }_k{\overline{\nu }}_k\right)\right)}{{\mu }_k{\overline{\mu }}_k}.\hfill \end{array}$$

(30)

In addition, the AoI violation probability of ${\mathrm{D}}_k$ with periodic arrival under FCFS is obtained as

$$P_k^{\left(\mathrm{F},\mathrm{P}\right)}\left(\delta \right)=\left\{\begin{array}{cc}\frac{\left(1-{\left(1-{\phi }_k\right)}^{{\tau }_k}\right){\left(1-{\phi }_k\right)}^{\delta -{\tau }_k}}{{\phi }_k{\tau }_k},\hfill & \mathrm{if}{\tau }_k<\delta ,\hfill \\ 1-\frac{{\left(1-{\phi }_k\right)}^{\delta }+{\phi }_k\delta -1}{{\phi }_k{\tau }_k},\hfill & \mathrm{if}{\tau }_k⩾\delta .\hfill \end{array}\right.$$

(31)

Proof. 

By substituting (25) and (28) into (24), we can obtain (30) and (31), respectively. □

Note that ${\mathrm{D}}_k$’s AoI violation probability also gives its complementary cumulative distribution function (CCDF) on AoI, which can be used as AoI performance guarantees for the system design. From this point of view, ${\mathrm{D}}_k$’s average AoI for Bernoulli arrival and periodic arrival can be obtained by using (30) and (31), respectively, which is given by

$${\overline{\Delta }}_k^{\left(\mathrm{F},{\psi }_2\right)}=\sum _{\delta =1}^{\infty }\delta \left(P_k^{\left(\mathrm{F},{\psi }_2\right)}\left(\delta -1\right)-P_k^{\left(\mathrm{F},{\psi }_2\right)}\left(\delta \right)\right)=\left\{\begin{array}{c}\frac{{\overline{\nu }}_k}{{\mu }_k-{\nu }_k}+\frac{1}{{\nu }_k}+\frac{{\nu }_k}{{\mu }_k}-\frac{{\nu }_k}{{\mu }_k^2},\mathrm{for}{\psi }_2=\mathrm{B},\hfill \\ \frac{{\tau }_k+1}{2}+\frac{1}{{\phi }_k},\mathrm{for}{\psi }_2=\mathrm{P}.\hfill \end{array}\right.$$

(32)

5. AoI Analysis under LCFS-PR

In this section, we analyze the AoI performance when the packet transmissions are conducted by the LCFS-PR discipline. In particular, every packet may or may not complete its service depending on whether it would be preempted by a new packet arrival. The packet that enters service upon its generation and can complete its service without being preempted is referred to as an informative packet. As such, the informative packet always contains the freshest information, while packets generated prior to the informative packet become obsolete due to preemption. Let ${\eta }_k$ represent the probability that a coming arrival for ${\mathrm{D}}_k$ is an informative packet, which is equivalent to

$${\eta }_k=\mathbb{P}\left\{X_k⩾S_k\right\},$$

(33)

where $S_k$ is the service time of ${\mathrm{D}}_k$. In other words, ${\eta }_k$ corresponds to the probability that the undergoing service is not preempted by any new arrival. The number of service preemptions between the inter-arrival time of two sequential informative packets is denoted by H, which thereby follows a geometric distribution with the following PMF

$$\mathbb{P}\left\{H=h\right\}={\left(1-{\eta }_k\right)}^h{\eta }_k,h=0,1,\cdots .$$

(34)

With LCFS-PR discipline, only the successful delivery of an informative packet can trigger the AoI reset. As shown in Figure 3, the AoI process can also be divided into non-intersecting sets. This is similar to the analysis presented in Section 4, but the set boundary here is along the informative packet arrivals. As such, the time duration holding the condition that AoI is larger than a certain age constraint $\delta$ in the i-th informative packet inter-arrival, which is denoted by $G_{k,i}^{\left(\mathrm{L},{\psi }_2\right)}$, can be expressed as

$$G_{k,i}^{\left(\mathrm{L},{\psi }_2\right)}=\left\{\begin{array}{cc}\max \left\{{\tilde{X}}_{k,i}-\left(\delta -{\tilde{T}}_{k,i}\right),0\right\},\hfill & \mathrm{if}{\tilde{T}}_{k,i}<\delta ,\hfill \\ {\tilde{X}}_{k,i},\hfill & \mathrm{if}{\tilde{T}}_{k,i}⩾\delta ,\hfill \end{array}\right.$$

(35)

where ${\tilde{X}}_{k,i}$ and ${\tilde{T}}_{k,i}$ is the interarrival and system time of the i-th informative packet of ${\mathrm{D}}_k$, respectively.

Following along similar lines as in Section 4, the AoI violation probability under LCFS-PR queue discipline can be evaluated as

$$P_k^{\left(\mathrm{L},{\psi }_2\right)}\left(\delta \right)=\frac{\mathbb{E}\left[G_k^{\left(\mathrm{L},{\psi }_2\right)}\right]}{\mathbb{E}\left[{\tilde{X}}_k\right]}.$$

(36)

In the following, we proceed with our analysis on $P_k^{\left(\mathrm{L},{\psi }_2\right)}\left(\delta \right)$ by deriving $\mathbb{E}\left[G_k^{\left(\mathrm{L},{\psi }_2\right)}\right]$ and $\mathbb{E}\left[{\tilde{X}}_k\right]$ under different arrival models. Under the Bernoulli arrival model, the probability that a new arrival is informative, i.e., ${\eta }_k$ defined by (33), can be further derived as

$${\eta }_k\stackrel{\left(a\right)}{=}\sum _{n=1}^{\infty }\mathbb{P}\left\{X_k⩾n\right\}\mathbb{P}\left\{S_k=n\right\}=\frac{{\mu }_k}{1-{\overline{\nu }}_k{\overline{\mu }}_k},$$

(37)

where $\left(a\right)$ is due to the independence between the inter-arrival and service time. Next, we give the PMF of ${\tilde{X}}_k$ under Bernoulli arrivals and LCFS-PR discipline.

Lemma 2.

With the LCFS-PR queue discipline, the PMF of the informative packet inter-arrival time under the Bernoulli arrival model can be derived as

$$\mathbb{P}\left\{{\tilde{X}}_k=x\right\}=\frac{{\nu }_k{\mu }_k{\overline{\mu }}_k^x}{{\mu }_k-{\nu }_k}\left({\left(\frac{{\overline{\nu }}_k}{{\overline{\mu }}_k}\right)}^x-1\right),x=1,2,\cdots .$$

(38)

Proof. 

The proof is provided in Appendix C. □

As a direct corollary, we can obtain $\mathbb{E}\left[{\tilde{X}}_k\right]$ from Lemma 2 as

$$\mathbb{E}\left[{\tilde{X}}_k\right]=\frac{1-{\overline{\mu }}_k{\overline{\nu }}_k}{{\mu }_k{\nu }_k}.$$

(39)

When the LCFS-PR discipline is applied, the informative packet preempts the ongoing service if there is any, and thus, the system time of the informative packet is comprised only of its service time. In fact, the PMF of ${\tilde{T}}_k$ is a conditional probability under the condition that the service for the informative packet can be completed. As a result, for $t=1,2,\cdots$, we have

$$\mathbb{P}\left\{{\tilde{T}}_k=t\right\}=\mathbb{P}\left\{\left.S_k=t\right|S_k⩽X_k\right\}=\frac{{\mu }_k{\nu }_k}{{\eta }_k}{\overline{\mu }}_k^{t-1}\sum _{x=t}^{\infty }{\overline{\nu }}_k^{x-1}=\left(1-{\overline{\mu }}_k{\overline{\nu }}_k\right){\overline{\mu }}_k^{t-1}{\overline{\nu }}_k^{t-1}.$$

(40)

According to (35), the expression of $\mathbb{E}\left[G_k^{\left(\mathrm{L},\mathrm{B}\right)}\right]$ can be derived analogously to that in (25), which is detailedly given by

$$\mathbb{E}\left[G_k^{\left(\mathrm{L},\mathrm{B}\right)}\right]=\sum _{t=1}^{\delta -1}\sum _{x=\delta -t+1}^{\infty }\left(x-\delta +t\right)\mathbb{P}\left\{{\tilde{X}}_k=x,{\tilde{T}}_k=t\right\}+\sum _{t=\delta }^{\infty }\sum _{x=1}^{\infty }x\mathbb{P}\left\{{\tilde{X}}_k=x,{\tilde{T}}_k=t\right\},$$

(41)

where the joint PMF of ${\tilde{X}}_k$ and ${\tilde{T}}_k$ is the product of their marginal PMF due to the independence between each other under LCFS-PR.

Under the periodic arrival model, the packet inter-arrival is determined as a constant, i.e., ${\tau }_k$. Moreover, in line with the LCFS-PR discipline, the informative packet inter-arrival time is equivalent to

$${\tilde{X}}_k=\left(H+1\right){\tau }_k,$$

(42)

where H is the preemption number during the inter-arrival between two successive informative packets. We can deduce from the PMF of H given by (34) that ${\tilde{X}}_k$ is a discrete random variable with range $\mathcal{X}=\left\{{\tau }_k,2{\tau }_k,\cdots \right\}$. Moreover, ${\tilde{X}}_k$ has the following PMF

$$\mathbb{P}\left\{{\tilde{X}}_k=x\right\}={\left(1-{\eta }_k\right)}^{\frac{x}{{\tau }_k}-1}{\eta }_k,$$

(43)

where ${\eta }_k$, as defined by (33), can be derived in the periodic arrival model as

$$\begin{array}{cc}\hfill {\eta }_k=& \mathbb{P}\left\{{\tau }_k⩾S_k\right\}=1-{\overline{\mu }}_k^{{\tau }_k}.\hfill \end{array}$$

(44)

As a result, we have

$$\mathbb{E}\left[{\tilde{X}}_k\right]=\frac{{\tau }_k}{1-{\overline{\mu }}_k^{{\tau }_k}}.$$

(45)

In addition, the system time of any informative packet under the LCFS-PR discipline lasts no more than ${\tau }_k$ time slots. This implies that ${\tilde{T}}_k$ takes value randomly from the set $\mathcal{T}=\left\{1,2,\cdots ,{\tau }_k\right\}$. Therefore, we have

$$\mathbb{P}\left\{{\tilde{T}}_k=t\right\}=\mathbb{P}\left\{\left.S_k=t\right|S_k⩽{\tau }_k\right\}=\frac{{\mu }_k{\overline{\mu }}_k^{t-1}}{{\eta }_k}.$$

(46)

In essence, ${\tilde{T}}_k$ is the service time of the informative packet, and it is independent of the informative packet inter-arrival ${\tilde{X}}_k$. This results in

$$\mathbb{P}\left\{{\tilde{X}}_k=x,{\tilde{T}}_k=t\right\}=\left\{\begin{array}{cc}{\left(1-{\eta }_k\right)}^{\frac{x}{{\tau }_k}-1}{\mu }_k{\overline{\mu }}_k^{t-1},\hfill & \mathrm{if}\left(x,t\right)\in \mathcal{X}\times \mathcal{T},\hfill \\ 0,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(47)

According to the relation between the packet interarrival ${\tau }_k$ and the given age constraint $\delta$, we can evaluate $\mathbb{E}\left[G_k^{\left(\mathrm{L},\mathrm{P}\right)}\right]$ based on (35) under the periodic arrival model. Specifically, when ${\tau }_k⩾\delta$, we have

$$\mathbb{E}\left[G_k^{\left(\mathrm{L},\mathrm{P}\right)}\right]=\sum _{x\in \mathcal{X}}\left(\sum _{t=1}^{\delta -1}\left(x-\delta +t\right)\mathbb{P}\left\{{\tilde{X}}_k=x,{\tilde{T}}_k=t\right\}+\sum _{t=\delta }^{{\tau }_k}x\mathbb{P}\left\{{\tilde{X}}_k=x,{\tilde{T}}_k=t\right\}\right).$$

(48)

In addition, when ${\tau }_k<\delta$, we have

$$\mathbb{E}\left[G_k^{\left(\mathrm{L},\mathrm{P}\right)}\right]=\sum _{x\in {\mathcal{X}}^{\prime }}\sum _{t=\varsigma \left(x\right)}^{{\tau }_k}\left(x-\delta +t\right)\mathbb{P}\left\{{\tilde{X}}_k=x,{\tilde{T}}_k=t\right\},$$

(49)

where ${\mathcal{X}}^{\prime }=\left\{\left(⌈\frac{\delta }{{\tau }_k}⌉-1\right){\tau }_k,⌈\frac{\delta }{{\tau }_k}⌉{\tau }_k,\cdots \right\}\subseteq \mathcal{X}$, and $\varsigma \left(x\right)=\max \left\{\delta -x,0\right\}+\mathbb{1}\left(\delta ⩽x\right)\in \mathcal{T}$.

On the basis of these analyses, we arrive at the following proposition, which gives the AoI violation probability expression under LCFS-PR.

Proposition 3.

In the depicted network, the expression of AoI violation probability of ${\mathrm{D}}_k$ with Bernoulli arrival under LCFS-PR obtained as

$$P_k^{\left(\mathrm{L},\mathrm{B}\right)}\left(\delta \right)=\frac{{\mu }_k{\overline{\nu }}_k^{\delta }-{\nu }_k{\overline{\mu }}_k^{\delta }}{{\mu }_k-{\nu }_k}.$$

(50)

In addition, the AoI violation probability of ${\mathrm{D}}_k$ with periodic arrival under LCFS-PR is obtained as

$$P_k^{\left(\mathrm{L},\mathrm{P}\right)}\left(\delta \right)=\left\{\begin{array}{cc}\frac{\left(1-{\overline{\mu }}_k^{{\tau }_k}\right){\overline{\mu }}_k^{\delta -{\tau }_k}}{{\mu }_k{\tau }_k},\hfill & \mathrm{if}{\tau }_k<\delta ,\hfill \\ 1-\frac{{\overline{\mu }}_k^{\delta }+\delta {\mu }_k-1}{{\mu }_k{\tau }_k},\hfill & \mathrm{if}{\tau }_k⩾\delta .\hfill \end{array}\right.$$

(51)

Proof. 

The above expression (50) is attained by plugging (39) and (41) into (36). Analogously, (51) follows by substituting (45), (48) and (49) into (36). □

Likewise, we can obtain the average AoI of ${\mathrm{D}}_k$ for Bernoulli and periodic arrivals under LCFS-PR by leveraging (50) and (51), respectively, which leads us to

$${\overline{\Delta }}_k^{\left(\mathrm{L},{\psi }_2\right)}=\sum _{\delta =1}^{\infty }\delta \left(P_k^{\left(\mathrm{L},{\psi }_2\right)}\left(\delta -1\right)-P_k^{\left(\mathrm{L},{\psi }_2\right)}\left(\delta \right)\right)=\left\{\begin{array}{c}\frac{1}{{\nu }_k}+\frac{1}{{\mu }_k},\mathrm{for}{\psi }_2=\mathrm{B},\hfill \\ \frac{{\tau }_k+1}{2}+\frac{1}{{\mu }_k},\mathrm{for}{\psi }_2=\mathrm{P}.\hfill \end{array}\right.$$

(52)

6. Simulation Results and Discussion

In this section, we investigate the AoI performance through Monte Carlo simulations and verify our analysis by comparing the simulation and analytical results. In addition, the effects of different network parameters on the AoI performance are discussed. The simulation parameters are summarized in

Table 1. Simulation parameters.

Parameter	Notation	Value
number of device	K	3
path-loss exponent	$\alpha$	4
path-loss constant	$\kappa$	$-18\mathrm{dB}$
shadowing	${\xi }_k$	Log-normal distribution with standard deviation of $6\mathrm{dB}$
small-scale fading	$g_k\left(t\right)$	Rayleigh fading
transmit power	$P_{\mathrm{tx}}$	$23\mathrm{dBm}$
noise power	$N_0$	$-114\mathrm{dBm}$
decoding threshold	${\theta }_k$	$0\mathrm{dB}$
link distance	$\left(d_1,d_2,d_3\right)$	$\left(180\mathrm{m},150\mathrm{m},120\mathrm{m}\right)$
iteration precision	$\epsilon$	${10}^{-4}$

. In particular, the large-scale propagation model combines both path loss and shadowing to capture the power falloff with distance, and the small-scale fading is modeled using Rayleigh distribution, which is commonly used in the literature [22,33]. In addition, the successful decoding threshold for NOMA and the transmit power are set according to [34] and [35], respectively.

Figure 4 plots the AoI violation probability versus AoI constraint for each device with different arrival settings under FCFS and LCFS-PR disciplines. It follows from this figure that the analytical results provide a good match with the simulation results, thus confirming the accuracy of our analysis. Moreover, it can be observed that there exists an apparent discrepancy among the enhancement level by applying LCFS-PR for each device’s AoI violation probability. To be more specific, for ${\mathrm{D}}_1$ and ${\mathrm{D}}_2$, LCFS-PR queue discipline can ameliorate the AoI violation probability to a certain extent, while this gain vanishes for ${\mathrm{D}}_3$. This can be intuitively explained as follows. The queue service rates of ${\mathrm{D}}_1$ and ${\mathrm{D}}_2$ are improved by utilizing SIC. Therefore, fresh information can be more likely successfully delivered, thus refining the AoI violation probability. However, ${\mathrm{D}}_3$ suffers from the mutual interference induced by NOMA. Hence, the preempted fresh information may still become obsolete due to the degraded queue service rate, which substantially counteracts the benefits of LCFS-PR. Furthermore, we can conclude from this figure that for all devices, when their traffic arrivals are homogeneous, LCFS-PR can achieve relatively more distinct improvement in the AoI violation probability compared to the case that devices have heterogeneous traffic arrivals.

Figure 5 depicts the AoI violation probability of each device as a function of the Bernoulli arrival rate or periodic generation cycle, under a varying value of AoI constraints and different types of queue disciplines. In particular, we set homogeneous traffic arrivals for all devices. We immediately notice that the analytical results track the simulation results well, which validates the feasibility of our analysis. Moreover, we observe that more frequent arrivals can give LCFS-PR a significant role in reducing the AoI violation probability, while infrequent arrivals efface the benefit of LCFS-PR and result in the same AoI violation probability performance with FCFS. In addition, it follows from this figure that the benefit of the AoI violation probability of ${\mathrm{D}}_1$, ${\mathrm{D}}_2$, and ${\mathrm{D}}_3$, stemming from the LCFS-PR discipline, diminishes visibly. This observation also coincides with that drawn from Figure 4, showing the differentiated gain for each device attained by leveraging LCFS-PR.

Figure 6 shows the network average AoI for a varying value of Bernoulli arrival rate or periodic generation cycle, under FCFS and LCFS-PR service disciplines with both NOMA and OMA settings. From Figure 6, the close match between the analytical and simulation results further proves the accuracy of our analysis. Also, we find that under the FCFS discipline, there is a gradual decline in the network average AoI performance with light traffic, whereas the network average AoI performance contrastingly rises with a further increase in arrivals. This is due to the tradeoff between the frequent arrivals and the resulting interference, which plays a critical role in the transmission success probability. In contrast, the network average AoI under LCFS-PR exhibits a downtrend with respect to the packet arrivals since the preemption by the newest packet contributes to the information freshness. The effectiveness of LCFS-PR over FCFS in reducing the network average AoI notably emerges when there are more frequent arrivals. This result indicates that the traffic arrival intensity should be brought into the selection of queue service discipline. In addition, it can be seen from this figure that compared to the benchmarking OMA transmissions, NOMA enjoys a clear advantage with respect to network average AoI. More specifically, this superiority under FCFS enlarges with increasing arrival frequency, while it does not vary evidently with arrival frequency under LCFS-PR.

In order to further reveal the impact of traffic arrival patterns on the average AoI in NOMA-IoT networks, we plot the network average AoI as a function of the packet inter-arrival slot in Figure 7. It can be observed that under the same service discipline, the deterministic periodic pattern can achieve a better average AoI than the random Bernoulli pattern for sporadic arrival, whereas this advantage gradually diminishes with more intensive arrival. Since packets keep accumulating in the device’s queue for small inter-arrival slots, the networks under both Bernoulli and periodic arrival are influenced by severe interference incurred by transmissions and retransmissions. Note that interference under periodic arrival exhibits a regular style, while it has a certain abruptness under Bernoulli arrival. As a result, for large inter-arrival slots, the network under periodic arrival suffers from more moderate interference compared to that under Bernoulli arrival, thus leading to better AoI performance. This result sheds light on the impact of traffic arrival patterns on the network average AoI.

Figure 8 plots the ratio of average AoI under LCFS-PR and FCFS for each device versus the Bernoulli arrival rate or periodic generation cycle. In particular, we evaluate the average AoI ratio achieved by each device under NOMA. It follows from this figure that LCFS-PR can always provide a better guarantee of delivering fresh information than FCFS for all devices, thus indicating the effectiveness of the LCFS-PR discipline. However, the average AoI of each device under the LCFS-PR discipline is slightly better than that under the FCFS discipline for sporadic packet arrivals, i.e., ${\nu }_k<0.3$ for Bernoulli arrival and ${\tau }_k>7$ for periodic arrival. With increasing packet arrival intensity, the superiority of LCFS-PR becomes more pronounced, but the enhancement level differs from devices. The reason comes from the fact that the queue service rate of both ${\mathrm{D}}_1$ and ${\mathrm{D}}_2$ can benefit from the SIC, leading to higher transmission quality and more fresh updates. As for ${\mathrm{D}}_3$, the mutual interference devastates its link quality, consequently resulting in information staleness. This result again exhibits the AoI improvement disparity among each device. In this light, different devices may flexibly adopt their queue service disciplines to strike a good balance between their AoI performance enhancement and the implementation complexity.

7. Conclusions

In this paper, the AoI performance of a NOMA-based IoT network was investigated. Specifically, random Bernoulli and deterministic periodic arrivals, as well as FCFS and LCFS-PR service disciplines, were incorporated into the analytical study. From the perspective of the temporal queuing model, a numerical iterative algorithm was proposed to obtain the queue service rate while taking into account the wireless NOMA transmission. Furthermore, tractable expressions on AoI violation probability and time-average AoI for Bernoulli and periodic traffic arrivals are derived under the FCFS and LCFS-PR disciplines. Simulation results were presented to validate the proposed analytical framework. The results reveal that the LCFS-PR discipline outperforms the FCFS discipline in delivering fresh information, especially when there are more frequent arrivals. Meanwhile, different devices under LCFS-PR in the NOMA group can attain different extents of melioration of AoI performance. Another key takeaway from the results is that the deterministic periodic pattern can achieve better average AoI than the random Bernoulli pattern for sporadic arrival, whereas this advantage gradually diminishes with more frequent packet arrival. The derived results can provide helpful guidance in characterizing and understanding how the traffic arrivals and service disciplines affect the AoI performance in NOMA-IoT networks. As a further generalized extension, investigating up to the AoI performance in networks using a continuous-time queuing model is regarded as a concrete direction. Additionally, a variety of design options may stretch out from a more in-depth exploration of the impact of general arrival types and intelligent service disciplines on the AoI performance of NOMA-IoT networks.