Analysis of Hierarchical AoII over unreliable channel: A Stochastic Hybrid System Approach

Following [40], SHSs are defined by a set of stochastic differential equations

where the system states are partitioned into the discrete state $\mathbf{q}\in\mathbb{Q}$ consistent with the ordinary jump process, and a $\mathit{k}$-dimensional stochastic process $\mathbf{x}$ with piecewise continuous sample paths called the continuous state.²²2For notation simplicity, we here omit the parameter $t$ associated with the joint system state $(\mathbf{q}(t),\mathbf{x}(t))$ at time $t$. Given a discrete state space $\mathbb{Q}$ and a $\mathit{k}$-dimensional vector $\mathbf{z}$ of independent Brownian motion processes, the continuous state $\mathbf{x}$ evolves with two state-dependent functions $f^{\prime}$ and $g^{\prime}$. Moreover, there is a family of discrete transition maps that tracks possible changes of the joint system state $(\mathbf{q},\mathbf{x})$, i.e.,

where $(\mathbf{q}^{+},\mathbf{x}^{+})$ denotes the joint state right after the transition map $\phi_{\mathit{l}}$ takes place, and $\mathit{l}\in\mathcal{L}=\{1,2,...,m\}$ denotes a set of transitions with transition intensities $\lambda_{\mathit{l}}(\mathbf{q},\mathbf{x})$.

Based on the general settings of SHSs above, the continuous state can be defined as the age processes for our AoII models, i.e., $\mathbf{x}(t)=[x_{1}(t),x_{2}(t)]$. We denote $x_{2}(t)$ as the AoII of $X_{t}$ at the monitor, and $x_{1}(t)$ is what the AoII at the monitor would become if an update in service were to complete transmission at time $t$. Since the AoII evolves deterministically at each state $\mathbf{q}$, we have $g^{\prime}(\mathbf{q},\mathbf{x},t)=0$ and $\mathbf{z}=0$. Moreover, the transition rates $\lambda_{l}$ of SHSs are all constant Poisson rates defined above according to the M/M/1/1 queue discipline.

Above all, the hierarchy of AoII of $X_{t}$ can be demonstrated by a piecewise age function $f$, whose derivative is denoted as $f^{\prime}$ in (4). The discrete state $\mathbf{q}$ of SHSs is the system state. Both would be later specified for each case.

To begin, we first need to characterize the system state, i.e., $\mathbf{q}\in\mathbb{Q}=\{0_{c},0_{e},1_{m},1_{u}\}$. State $0_{c}$ is defined as the correct (content-matched) state, where the AoII would not increase hence $\mathbf{\dot{x}}=[0,0]=\mathbf{0}_{n}$. State $1_{m}$ is defined as the mismatched state, where a content-changed update arrives and starts transmission. The AoII $\mathbf{x}(t)$ grows as the traditional AoI in this state, i.e., $\mathbf{\dot{x}}=[1,1]=\mathbf{1}_{n}$. State $0_{e}$ is defined as the error state, where no update is on transmission yet the content between ends is mismatched due to the channel noise. Hence, the age processes $\mathbf{x}(t)$ keep growing in $0_{e}$. State $1_{u}$ is the urgent state, where the transmitter is delivering a more important update. According to the model assumptions, $1_{u}$ can be reached when:

i). a newly sampled update with changed content preempts transmission. In that case, the content of $\hat{X}_{t}$ would lag at least two versions behind the transmitting update;

ii). a newly sampled update recovers the system from the error state. In that case, the monitor needs the update to fix the error as soon as possible.

The hierarchy of (2) can be implemented by adopting different age functions $f$ in each state, where the level of age dissatisfaction at states $0_{e}$ and $1_{u}$ is considered to be severer for the following two reasons.

$\bullet$ The content mismatch between ends cannot be directly eliminated from the error state $0_{e}$ since there is no update on transmission. Being away from $0_{c}$ compared to the other states exacerbates the ageing of $\hat{X}_{t}$ at the monitor.

$\bullet$ The content of update being transmitting at $1_{u}$ is urged by the monitor due to conditions i) and ii) above, which also exacerbates the ageing of $\hat{X}_{t}$.

Consequently, we construct hierarchy schemes with four levels through the state-dependent derivative $f^{\prime}$ using two distinct piecewise functions.

- Linear hierarchy:

The parameters $m_{1}\geqslant 1$ and $m_{2}\geqslant 1$ are slopes representing two different levels of age dissatisfaction in the linear case.

- Quadratic hierarchy:

The parameters $k_{1}$ and $k_{2}$, where $k_{1}<k_{2}$, are the growth constants controlling the stability of SHSs, which would later be constrained by the state transition rates.

To move forward, we now explain each transition $l$ with a constant intensity $\lambda_{\mathit{l}}(\mathbf{q},\mathbf{x})=\lambda_{l}$, which is illustrated in Fig. 3 with the pre-defined SHSs states.

$l=0,3,7$: Since the content of a newly sampled update remains unchanged with probability $q$ in the self-transition at state $0_{c}$, we assume that this kind of update would be maintained at the transmitter subject to an exponential random interval with rate $\mu$ (then dropped) instead of being transmitted. In the self-transition at state $1_{m}$, the preemption of an unchanged update also has no effect on the AoII. Moreover, since we consider the four-level hierarchy in the measure of timeliness for the noisy channel case, the state $1_{u}$ would stay under any preemption while the ageing process reaches the fourth level, which is the highest, at $1_{u}$.

$l=1,5$: An update with changed content leads to the second-level dissatisfaction between ends and the AoII starts to grow after the state is transferred into $1_{m}$ by $l=2$. Similarly, the update under transmission would also be preempted (then discarded) by a newly sampled update with changed content, which leads to the fourth-level dissatisfaction after the state is transferred into $1_{u}$ by $l=5$.

$l=2,6$: The content between ends is correctly matched after a successful transmission over the noisy channel. Meanwhile, the AoII is reset to zero by transitions $2,6$, respectively.

$l=4,8$: If the update is not successfully decoded by the monitor due to noise, the system state would be transferred into the error state $0_{e}$ by $l=4,8$. Then, $\hat{X}_{t}$ at the monitor suffers from a severer age dissatisfaction, namely, the third level in our consideration, due to the mismatch of content.

$l=9$: Any newly sampled update $X_{t}$ starts a transmission in $1_{u}$ when the system was in the error state before. Without loss of generality, we assume that the system goes through different out-of-sync situation between $1_{u}$ and $0_{s}$.

These state transitions are summarized in Table I, along with the possible changes of AoII after mappings $\{\phi_{\mathit{l}}:l\in\mathcal{L}\}$.

To quantify the average AoII, we first need to employ a test function to track the dynamics of AoII at each state $\overline{\mathbf{q}}\in\mathbb{Q}$,

where $\delta_{\overline{\mathbf{q}},\mathbf{q}}$ is the Kronecker delta function that equals to one only if $\overline{\mathbf{q}}=\mathbf{q}$, otherwise it is zero. We also define

as the expected value of AoII in each state $\overline{\mathbf{q}}$ at time $t$, where $\mathbf{v}_{\overline{\mathbf{q}}}(t)=[v^{1}_{\overline{\mathbf{q}}}(t),v^{2}_{\overline{\mathbf{q}}}(t)]$ tracks two different AoII process. Furthermore, we define the stationary solution (if exists) when $t\to\infty$ to be $\mathbf{v}_{\overline{\mathbf{q}}}=[v^{1}_{\overline{\mathbf{q}}},v^{2}_{\overline{\mathbf{q}}}]=\lim\nolimits_{t\to\infty}\mathbf{v}_{\overline{\mathbf{q}}}(t)$,

Given that $\psi$ is specified and $g(\mathbf{q},\mathbf{x},t)=0$, we introduce one more definition of an operator $L$ on the test function $\psi$[42], that is,

which is called the extended generator for our SHSs. $f^{\prime}(\mathbf{q},\mathbf{x},t)$ is in the form of (5) or (6), and $\lambda_{l}$ for the noisy channel case is given in Table I. Note that the extended generator $(L\psi)_{0_{c}}=(L\psi)_{0_{c}}(\mathbf{q},\mathbf{x},t)$ at state $0_{c}$ is zero since the AoII at $0_{c}$ never grows at all.³³3 As noted in [9], $0_{c}$ is called the irrelevant state to AoII. However, this kind of states does affect the stationary distributions.

With these quantities defined, we are able to introduce the main tool of SHSs in Lemma 1, known as Dynkin formula.

Lemma 1 in fact tells that the dynamics of the test function are on average characterized by its extended generator $L\psi$, whose expected value is the expected rate of $\psi$.

We now can leverage (10) to derive the closed-form expressions of average AoII for the M/M/1/1 queue under linear hierarchy $f_{1}^{\prime}(\mathbf{q})$, which is concluded as [1, Theorem 1]. However, in order to calculate the average AoII under quadratic hierarchy $f_{2}^{\prime}(\mathbf{q})$, we need to modify the aforementioned theorem. Hence, we summarize our first result in the following.

The matrix $\mathbf{A}_{l}$ in (13) and (14) is the transition matrix associated with the mapping $\phi_{\mathit{l}}$, which is also given in Table I. Since the first two parts of Theorem 1 have been proved in [1], we omit here for simplicity. The proof of (iii) appears in Appendix A. Note that (14) is only valid under some constrained parameters $k_{1}$ and $k_{2}$, which is called the stability conditions for quadratic hierarchy and is discussed later in Section III-D.

Following Theorem 1, the stationary distributions of the SHSs Markov chain in Fig. 3 are calculated as:

where $a=p+p\rho+p_{c}q$, and $\rho=\lambda/\mu$ is known as the utilization factor of the queue. Then we can use (13) and (15) to obtain the following results.

The derivation of (17) appears in Appendix B. The ergodicity of the SHSs Markov chain is established by (16). Hence, it is easy to verify that (17) always exists for any finite $m_{1}$ and $m_{2}$ based on the invertibility of matrix associated with (43), namely, $\det(\mathbf{B})=1-p_{e}>0$ for matrix $\mathbf{B}$ defined in (43).⁴⁴4A general proof can be found in [9, Section V]. The simplified version (18) would later be used to compare with the AoI results in Section V.

Moreover, we note that (17) and (18) can be further specified to the results under metric AoS proposed in [21] by setting $p=1$. To be clearer, since the AoS metric is defined as the time since the content between two ends are out-of-sync, it is exactly the case of the proposed AoII metric where every newly sampled update changes its content with probability one. Hence, the expressions of average AoS in a preemptive M/M/1/1 queue over the noisy channel are given by

The average AoII under the quadratic hierarchy is more complex since it involves a hybrid of two kinds of differential equations. The closed-form expression is summarized below.

The derivation of (20) appears in Appendix C. However, we are more interested in the stability conditions of (20) since the invertibility of matrix $\mathbf{C}$ defined in (46) depends on the values of $k_{1}$ and $k_{2}$. These conditions are given below, the proof of which can be found in Appendix D.

Theorem 2 can be extended to other multi-level (more than four) hierarchies with finer state definitions by going through the same proof procedure as long as the hybrid only consists of linear and quadratic functions. For example, one can split the state $0_{e}$ into two states $0^{1}_{e}$ and $0^{2}_{e}$ representing different levels of error, where $0^{1}_{e}$ is defined the same as the original error state directly connected to $1_{m}$ and $0^{2}_{e}$ is defined as a severer error state that can only be reached by $1_{u}$. Meanwhile, we must point out that the above conditions are actually sufficient and necessary, as proved in Appendix D.

We need to redefine the system states based on the collision nature of channel, where the state space $\mathbb{Q}_{c}$ consists of eight different states $\mathbf{q}\in\mathbb{Q}_{c}=\{0_{c},0_{e},1_{c},1_{m},1_{u},1_{e},2_{m},2_{u}\}$. States $0_{c},0_{e},1_{m}$ and $1_{u}$ are defined the same as the noisy channel case. However, we have to added four more states due to the existence of $X^{c}_{t}$, namely, $1_{c},1_{e},2_{m},2_{u}$. State $1_{c}$ is defined as the other correct (content-matched) state while the contender utilizes the channel to transmit $X^{c}_{t}$ alone. Hence, the AoII in $1_{c}$ would also not increase as in $0_{c}$. On the contrary, state $1_{e}$ is defined as the other error state while the contender utilizes the channel yet the content between ends is mismatched, where we assume that the AoII in $1_{e}$ grows the same as in $0_{e}$. States $2_{m}$ and $2_{u}$ are defined as two distinct collision states under different ageing processes when $X_{t}$ and $X^{c}_{t}$ both occupy the channel. To be clear, the former collision state $2_{m}$ can be directly reached by $1_{m}$ and $1_{c}$, which means the content of $\hat{X}_{t}$ at the monitor only lags one version behind the collision update $X_{t}$. However, the collision update $X_{t}$ in $2_{u}$ is considered to be more urgent for the same two reasons i) and ii) given in III-A, so the ageing process of $\hat{X}_{t}$ is severer than $2_{m}$ at the monitor.

Moreover, since we are only interested in the AoII behavior of $X_{t}$, the continuous states of our SHSs are defined the same as the noisy channel case, i.e., $\mathbf{x}(t)=[x_{1}(t),x_{2}(t)]$ due to the independence between $X_{t}$ and $X^{c}_{t}$.

Based on the above state definitions, the quadratic hierarchy scheme considered here also has four levels, which is characterized by the state-dependent derivative $f_{3}^{\prime}(\mathbf{q},\mathbf{x},t)$.

- Quadratic hierarchy:

The parameters $k_{1}$ and $k_{2}$ are the growth constants controlling the stability of SHSs, where $k_{1}<k_{2}$. Given that the collision channel is noise-free, state $2_{u}$ is assumed to be the only urgent state with the highest age dissatisfaction (the fourth level) since it is the only state that suffers from both collision and a severer out-of-sync situation. Note that this assumption can be easily generalized by adapting the growth rate constant $k_{1}$ and $k_{2}$.

The SHSs states and corresponding transition set $\mathcal{L}_{c}$ are depicted in Fig. 4. For clarity, we now explain each transition $l\in\mathcal{L}_{c}$.

$l=0,6,9,13,16,20,24$: First, the assumption of the self-transition at state $0_{c}$ remains the same as the noisy channel case. In the remaining self-transitions, states $1_{c}$, $1_{m}$ and $2_{m}$ would stay unchanged when the transmission of updates is preempted either by a content-unchanged update (maintained) $X_{t}$ or the contender $X^{c}_{t}$. Moreover, states $1_{u}$, $1_{e}$ and $2_{u}$ would stay unchanged under any preemption.