Age of Information with Hybrid-ARQ: A Unified Explicit Result

In recent ten years since Kaul et al. proposed a framework to quantify the timeliness of information in 2012 [1], one of the most popular ideas in timely update system design has been how to keep information as fresh as possible and ensure timely information delivery. For timely update systems such as vehicle networks where the vehicle’s velocity and location are disseminated to ensure safe transportation [2], environmental sensor networks where the updates of a time-varying phenomenon are collected for large-scale monitoring [3], and wireless communication networks where adaptive scheduling algorithms are adopted based on the time-varying channel state information [4], achieving timely delivery can freshen the monitor’s awareness of the sources and thus assist correct and efficient decision making.

This has aroused new interest in analyzing Age of Information (AoI) performance metrics. AoI has been broadly used to capture the freshness of a monitor’s knowledge of an entity or process. Different from conventional performance metrics such as delay and throughput, AoI comprehensively measures the effects of update rate, latency, and system utilization. Initial works on this issue were mainly based on queue analysis, which originated from single-source single-server queues [5, 6, 7, 1], and subsequently developed to multiple-sources single-server queues [8, 9, 10, 11] and wireless queuing networks [12, 13, 14, 15, 16, 17]. These works are based on an ideal assumption that the status update is transmitted through a perfect channel without packet errors and losses. In practice, however, packet errors and losses are inevitable due to ubiquitous noises, signal interference, and channel fading. As the incorrectly decoded message does not bring about fresh awareness, the packet errors and losses will result in staleness of information, leading to uncontrollable residual errors, system instability, and wrong decisions. Therefore, it is imperative to analyze the AoI over unreliable channels.

Some recent works have noticed the above limitation and have extended the AoI analyses to the physical (PHY) layer. One pioneering work concerning this issue was accomplished by Chen, et al. in 2016 [18], in which the update is delivered over an erasure channel and the Peak Age of Information (PAoI) is studied. This work has aroused extensive research interest in understanding the effect of system reliability on AoI. From then on, including but not limited to the follow-up works that also analyzed AoI over the erasure channel [19, 20, 21], various transmission protocols, ranging from conventional protocols like non-ARQ, classical ARQ and truncated ARQ protocols, to state-of-the-art protocols such as HARQ with Chase Combing (HARQ-CC) and HARQ with Incremental Redundancy (HARQ-IR) protocols, have been investigated under different types of noisy channels [22, 23, 24, 25, 26].

We notice that the above AoI analyses focus on the transmission delay, and neglect other types of system delay such as coding delay, propagation delay, decoding delay and feedback delay. An exception work is [27], which considers non-trivial propagation delay and studies the AoI of HARQ-IR with a fixed number of retransmitted packets $m=2$ under Satellite-IoT Systems, but also assumes negligible coding delay and decoding delay. Nevertheless, in practical communication systems, especially the short-packet communication, the coding delay and decoding delay are also nontrivial compared to the transmission delay, resulting in the staleness of information by nature. Thus, we focus on a more realistic (or general) scenario where different types of delay elements naturally exist and the number of retransmitted packets is not fixed to $m=2$. In this regard, we would like to provide a basic framework to comprehensively study the trade-off among coding complexity, decoding complexity, code length, number of retransmitted packets and error probability from the AoI perspective.

Up to this point, we have only introduced AoI research based on conventional reactive HARQ (also known as stop-and-wait HARQ), which allows for retransmissions only upon the reception of a Negative ACKnowledgment (NACK). As such, the retransmission process is not truly automatic. In the Release-16 5G NR specifications by the $3^{rd}$ Generation Partnership Project (3GPP), a new HARQ protocol named proactive HARQ is designated for the Up-Link Grant-Free communication to enable the potential for meeting the stringent requirements for URLLC [28]. Some recent works have shown the superiority of proactive HARQ in terms of latency and throughput compared to reactive HARQ [29, 30, 31]. Inspiringly, these available studies also witness the potential for proactive HARQ to be applied in the freshness-critical status update system. To this end, we would like to theoretically analyze the AoI performance of reactive HARQ and proactive HARQ to investigate whether proactive HARQ will facilitate timeliness of information in the freshness-critical status update system.

The research on the HARQ-based timely status update system is still in the ascendant, and some open issues remain to be addressed. First, there have been a lot of works providing explicit average age results under different types of protocols and systems. Examples include the average AoI expressions under fixed-length non-ARQ protocols, truncated-ARQ, classical ARQ, and the explicit results of some advanced ARQ-based techniques like HARQ-CC and HARQ-IR. However, there has not been a unified expression that can unify the aforementioned expressions in a single closed-form formula. By providing such a unified result, the comparative insights and the intrinsic relationships among different protocols will be further investigated. Second, the existing literature only considers certain types of delay in the status update system and assumes others to be negligible. However, as the delay exists by nature and plays as a critical part in affecting the freshness of information, to comprehensively consider the coding delay (or processing delay), propagation delay, transmission delay, decoding delay and feedback delay in the status update system and provide a unified closed-form result will provide a systematic understanding in analyzing the age of a realistic freshness-critical status update system. Third, the age performance has been extensively studied over erasure channels. However, little research considers the short-packet AoI analysis over the AWGN channel. Finally, the majority of existing works mainly focus on AoI analysis of conventional reactive HARQ. Some recent works analyzing the performance of proactive HARQ are based on some conventional performance metrics, such as throughput and latency. Thus, to analyze the AoI of proactive HARQ will fill this research gap and may further facilitate new system advancement of a status update system.

Motivated by the above, this work achieves several key contributions and we summarize them as follows:

• •

  We derive unified closed-form average AoI and average Peak AoI expressions for reactive HARQ, wherein: $i$) different kinds of delay elements (i.e., coding delay, transmission delay, propagation delay, decoding delay, and feedback delay) are comprehensively considered; $ii$) the number of repeated packets is not fixed as $m=2$, but is relaxed to a variable value; $iii$) different types of protocols are unified to a single expression.

• •

  We investigate the AoI explicit expressions and comparative insights for proactive HARQ, which is the first work analyzing proactive HARQ from the AoI perspective. Theoretical and numerical comparisons are given to show the superiority of proactive HARQ in enabling timely information delivery.

• •

  We also try to further optimize the AoI for both reactive HARQ and proactive HARQ. By formulating an AoI minimization problem in the FBL regime, we solve out the age-optimal block assignment strategy for reactive HARQ and proactive HARQ, respectively. The results show that the optimal strategy for proactive HARQ turns out to be the finest grained symbol-by-symbol transmission, while that for reactive HARQ is highly dependent on the propagation delay and SNR.

The rest of this paper is organized as follows. In Section II, we briefly introduce the considered system model. The generalized closed-form expressions of average AoI and average Peak AoI for reactive HARQ and proactive HARQ are provided in Section III, where the effect of different delay elements is added into the analysis. In Section IV, we design an optimization problem to reduce the average AoI of reactive HARQ and proactive HARQ, respectively. Numerical results and discussions are given in Section V, followed by conclusions in Section VI.

We consider an E2E communication setup leveraging a power-limited AWGN model:

where $P$ is the average transmit power, $X$ is the unit-variance coded symbol and $Z\sim\mathcal{N}\left(0,1\right)$ is the independent and identically distributed (i.i.d) AWGN.

The overall system model is shown in Fig. 1. The considered system is in close-up fashion with perfect HARQ feedback²²2In this article, we assume that the feedback is error-free. The research with erroneous feedback can be extended following this work.. At the transmitter end, the update generator (source) generates a $k$-bit short-packet update $u$ and encodes it to a parent codeword with length $\sum\nolimits_{i=1}^{m}{{\ell_{i}}}$ channel uses, which is then divided into $m$ sub-codeblocks with length $\ell_{i},i\in\left[m\right]$ and stored in a buffer waiting to be transmitted. The coding process above will take up $\tau_{\rm c}$ channel uses, and we call it as coding delay. Next, the stored sub-codeblocks are transmitted over a noisy channel sub-codeblock by sub-codeblock, with each transmission taking a transmission delay $\ell_{i},i\in\left[m\right]$ channel uses. The transmitted sub-blocks will take $\tau_{\rm p}$ channel uses to arrive at the receiver end. At the receiver end, we assume that the decoding process is conducted once receiving any complete sub-codeblock. The decoding delay in each transmission round is assumed to be the same and is denoted by $\tau_{\rm d}$. If the update is decoded correctly such that $\hat{u}=u$, an ACKnowledgment (ACK) will be fed back to the transmitter; otherwise, a NACK will be sent back. The feedback, similar to the forwarding information propagation, generally takes time and results in delay by nature, and we denote the delay as $\tau_{\rm f}$ channel uses.

The generate-at-will model is adopted in the considered E2E status update system. That is, when the transmitter receives an ACK, the process of sensing and sampling will be performed, and a new update will be generated. In such a case, we mainly focus on two types of HARQ schemes: reactive HARQ and proactive HARQ. The detailed processes are shown in Fig. 2(a) and Fig. 2(b), respectively.

We focus on AoI analysis and optimization in this paper. Here we simply review the definition of instantaneous AoI as in Definition 1. For more intuitive and visualized results, Fig. 2 also gives the instantaneous age evolutions of reactive HARQ and proactive HARQ respectively.

Corollary 1 demonstrates that $\bar{\Delta}_{\rm Reactive}\geq\bar{\Delta}_{\rm Proactive}$, where the equivalence happens only if $i$) $m=1$, in such a case, both the reactive HARQ and the proactive HARQ turns to a open-loop fashion non-ARQ system, and the system does not send any incremental redundancy; $ii$) $\mathcal{T}=0$, this condition infers to an ideal assumption where the propagation delay, decoding delay and feedback delay are negligible. In this regard, the RTT issue of reactive HARQ does not exist any more, and thus the considered reactive scheme is the same as the proactive one.

With the above closed-form results, we observe that the average AoI of a HARQ-based system can be directly evaluated by determining the error probability vector e and the block assignment vector n. The error probability $\epsilon_{i}$ is affected by three factors, which are, $i$) the channel condition; $ii$) the coding and decoding technique; $iii$) the message length $k$ and the code length $n_{i}$. As such, the framework given in this paper is general-purpose, enabling potential AoI research under different coding schemes and channel conditions.

For instance, the given generalized expressions allow us to adopt the FBL results in [32] to evaluate the AoI of the considered HARQ protocols. Over the power-limited AWGN channel with SNR $\gamma$, the error probability $\epsilon_{i}$ can be approximated by the Theorem 54 of [32] as:⁴⁴4Here we focus on FBL analysis as a case study. Note that $\epsilon_{i}$ can also be characterized by other specific error-correcting techniques.

where $C$ is the channel capacity with $C=\log_{2}\left(1+\gamma\right)$, $V$ is the channel dispersion with $V=(1-\frac{1}{\left(1+\gamma\right)^{2}})\log_{2}^{2}e$, and $Q\left(\cdot\right)$ denotes the $Q$ function with

Substitute (24) into (14) and (20), we obtain the average AoI closed-form expressions in the FBL regime.

We establish an average AoI minimization problem here to further explore the age-optimal transmission mechanism in the FBL regime with non-trivial delay:

1) Objective function: To minimize the average age $\bar{\Delta}$.

2) Decision variable: The block assignment vector ${\bf n}=\left(n_{1},n_{2},\cdots,n_{m}\right)$.

Note that the decision variable $\bf n$ is a variable-length vector with infinite solution space, we introduce $n_{\min}$ and $n_{\max}$ as constraints of the solution space, which denotes the lower bound and the upper bound of the range of block length, respectively.

Problem 1 is a nonlinear integer problem. To solve the optimal solution of Problem 1, an auxiliary vector ${\bf p}\in\mathcal{S}\triangleq\left\{0,1\right\}^{n_{\max}-n_{\min}+1}$ can be introduced here.

Lemma 9 illustrates that the introduced auxiliary vector $\bf p$ can be regarded as an index of the solution space of Problem 1, which can help us traverse the entire solution space efficiently and find the optimal solution. The detailed algorithm process is provided in Algorithm 1.

Fig. 3 gives some detailed examples of the solved optimal block assignment vector ${\bf n}_{\rm optimal}$ under different protocols, SNRs, and propagation delays. For example, under SNR$=0.7$ dB and $\tau_{\rm p}=0$, the optimal block assignment vector for reactive HARQ is ${\bf n}_{\rm optimal}=\left(105,120\right)$; under SNR$=1.9$ dB and $\tau_{\rm p}=20$, the optimal block assignment vector for reactive HARQ is ${\bf n}_{\rm optimal}=\left(100,112,120\right)$.

Fig. 3. leads to the following conclusions:

• •

  For proactive HARQ, the finest grained symbol-by-symbol strategy always minimizes the average AoI.

• •

  For reactive HARQ, the age-optimal block assignment varies among different SNRs and propagation delays. As the propagation delay increases, the number of retransmissions will monotonically decrease and finally converge to $m=1$. In such a case, the transmission scheme turns an open-loop fashion without any retransmission. This indicates that there exists a threshold of the propagation delay, only within which retransmission is beneficial to AoI.

• •

  From a perspective of channel coding, we can see that the trade-off between reliability and effectiveness can be well evaluated by the new metric, AoI. It is well known that a longer code length can improve the reliability while sacrificing the effectiveness; however, what is not fully explored is that an appropriate choice of code length can minimize the AoI.

For proactive HARQ, it has been empirically shown that the finest grained strategy minimizes the average AoI; however, for reactive HARQ, the age-optimal strategies vary along with channel conditions and propagation delay. Thus, to repeatedly determine the age-optimal scheme requires amounts of calculations. It is also pertinent to note that the implementation of Algorithm 1 aims to exhaustively search the whole solution space to find an age-optimal block assignment strategy. As such, the complexity of such an Algorithm is exponentially increasing with the range of code length $n_{\max}-n_{\min}+1$. For a broader range of code length, here we heuristically provide a sub-optimal algorithm to circumvent the high-complexity issue. Specifically, the heuristic sub-optimal algorithm is given in Algorithm 2.

The design of such an algorithm is based on the empirical observation that the age-optimal $m$ is always monotonically decreasing with propagation delay (see Fig. 3). Meanwhile, the age-optimal $m$ for reactive HARQ tends to remain small since large $m$ will lead to multiple RTT and thus result in staleness of information. Attributed to the above factors, heuristically, we denote the minimal age under a fixed $m$ as $\bar{\Delta}_{\min,m}$ and recursively search the solution space $\mathcal{J}_{m}\triangleq\left\{\left(n_{1},\cdots,n_{i}\right):i=m,n_{\min}<n_{1}<n_{2}\cdots<n_{i}<n_{\max}\right\}$ with increasing value of $m$. The on-the-fly searching process will terminate only if $\bar{\Delta}_{\min,m}>\bar{\Delta}_{\min,m-1}$. By this means, the algorithm outputs $\bar{\Delta}_{\min,m-1}$ as the optimal age. In such a case, this algorithm eliminates the need for searching the sub-space $\cup_{i=m+1}^{n_{\max}-n_{\min}+1}\mathcal{S}_{i}\subseteq\mathcal{S}$, thereby bypassing the calculations required for searching for the whole solution space.