# Timely Multi-Process Estimation Over Erasure Channels With and Without
Feedback††thanks: This work was supported by the U.S. National Science
Foundation under Grants CNS 21-14537 and ECCS 21-46099.

Karim Banawan  Department of Electrical Engineering, Alexandria University,
Egypt. Ahmed Arafa  Department of Electrical and Computer Engineering,
University of North Carolina at Charlotte, USA  Karim G. Seddik  Electronics
and Communications Engineering Department, American University in Cairo,
Egypt.

###### Abstract

We consider a multi-process remote estimation system observing $K$ independent
Ornstein-Uhlenbeck processes. In this system, a shared sensor samples the $K$
processes in such a way that the long-term average sum mean square error (MSE)
is minimized. The sensor operates under a total sampling frequency constraint
$f_{\max}$. The samples from all processes consume random processing delays in
a shared queue and then are transmitted over an erasure channel with
probability $\epsilon$. We study two variants of the problem: first, when the
samples are scheduled according to a Maximum-Age-First (MAF) policy, and the
receiver provides an erasure status feedback; and second, when samples are
scheduled according to a Round-Robin (RR) policy, when there is no erasure
status feedback from the receiver. Aided by optimal structural results, we
show that the optimal sampling policy for both settings, under some
conditions, is a _threshold policy_. We characterize the optimal threshold and
the corresponding optimal long-term average sum MSE as a function of $K$,
$f_{\max}$, $\epsilon$, and the statistical properties of the observed
processes. Our results show that, with an exponentially distributed service
rate, the optimal threshold $\tau^{*}$ increases as the number of processes
$K$ increases, for both settings. Additionally, we show that the optimal
threshold is an _increasing_ function of $\epsilon$ in the case of _available_
erasure status feedback, while it exhibits the _opposite behavior_ , i.e.,
$\tau^{*}$ is a _decreasing_ function of $\epsilon$, in the case of _absent_
erasure status feedback.

##  1 Introduction

We study the problem of timely tracking of multiple random processes using
shared resources. This setting arises in many practical situations of remote
estimation and IoT applications. Recent works have drawn connections between
the quality of the estimates at the destination, measured through mean square
error (MSE), and the age of information (AoI) metric that assesses timeliness
and freshness of the received data, see, e.g., the survey in [1, Section VI].
We extend these results to multi-process estimation settings in this work.

AoI is defined as the time elapsed since the latest received message has been
generated at its source. It has been studied extensively in the past few years
in various contexts, see, e.g., [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]. Relevant to this work is
the fact that AoI can be closely tied to MSE in random processes tracking
applications. The works in [28, 29, 30] characterize implicit and explicit
relationships between MSE and AoI under different estimation contexts.
References [31, 32], however, consider the notion of the value of information
(mainly through MSE) and show that optimizing it can be different from
optimizing AoI. Lossy source coding and distorted updates for AoI minimization
is considered in [33, 34, 35]. The notion of age of incorrect information
(AoII) is introduced in in [36], adding more context to AoI by capturing
erroneous updates. The works in [37, 38] consider sampling of Wiener and
Ornstein-Uhlenbeck (OU) processes for the purpose of remote estimation, and
draw connections between MSE and AoI. Our recent work in [39] also focuses on
characterizing the relationship of MSE and AoI, yet with the additional
presence of coding and quantization. Reference [40] shows the optimality of
threshold policies for tracking OU processes under rate constraints.

Reference [38] is closely related to our setting, in which optimal sampling
methods to minimize the long-term average MSE for an OU process is derived. It
is shown that if sampling times are independent of the instantaneous values of
the process (signal-independent sampling) the minimum MSE (MMSE) reduces to an
increasing function of AoI (age penalty). Then, threshold policies are shown
optimal in this case, in which a new sample is acquired only if the expected
age-penalty by the time it arrives surpasses a certain value. This paper
extends [38] (and the related studies in [39, 40]) to multiple OU processes.

Figure 1: System model.

In this paper, we study a remote sensing problem consisting of a shared
controlled sensor, a shared queue, and a receiver (see Fig. 1) to track $K$
independent, but not necessarily identical, OU processes.111The OU process is
the continuous-time analog of the first-order autoregressive process [41, 42],
and is used to model various physical phenomena, and has relevant applications
in control and finance. The sensor transmits the collected samples over an
erasure channel with probability $\epsilon$ after being processed for a random
delay with service rate $\mu$. The sensor generates the samples _at will_ ,
subject to a total sampling frequency constraint $f_{\max}$. The goal is to
minimize the long-term average sum MSE of the $K$ processes.

In this work, we investigate two variants of the problem, which are different
based on the _availability of erasure status update_ at the transmitter222We
use the words sensor and transmitter interchangeably.. In the first setting,
the receiver sends an erasure status update to the transmitter. We focus on
_maximum-age-first_ (MAF) scheduling, where the transmitter chooses the
process with the largest AoI to be sampled. MAF scheduling results in
obtaining a _fresh_ sample from the _same_ process until an unerased sample
from that process is conveyed to the receiver. The erasure status update
enables the use of MAF scheduling as the transmitter can accurately estimate
the AoI of each process. In the second setting, the erasure status feedback is
absent at the transmitter. In this setting, we focus on _round-robin_ (RR)
scheduling, where the transmitter acquires samples from the processes in a
_fixed order_ irrespective of the experienced erasure events. In both problem
variants, we concentrate on _stationary deterministic policies_ , where the
sampling policy needs to induce a stationary distribution across transmission
epochs. Based on this, the optimal sampling policy reduces to optimizing a
_stationary waiting policy_.

We show that, for both problem settings, we can _aggregate_ the waiting times
without affecting the sum MSE value, with a subtle difference between the two
problem variants. Specifically, in the presence of erasure status feedback,
the waiting times are aggregated at the beginning of the transmission _epoch_
, defined as the inter-delivery time between successful samples, which
includes the _successful_ transmission of a sample from each process. In the
absence of erasure status feedback, however, the transmitter aggregates the
waiting times at the beginning of the transmission _round_ , which includes a
transmission _trial_ of a sample from each process irrespective of the erasure
outcome. We show that, for both problems, the optimal stationary deterministic
policy is a _threshold policy_. We characterize the optimal threshold
$\tau^{*}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma})$ and the corresponding
long-term average sum MSE in terms of the processes’ statistical properties
($\bm{\theta},\bm{\sigma}$), $\epsilon$, and $f_{\max}$. In both cases, the
threshold is a maximum of two threshold values: one due to a nonbinding
sampling frequency constraint scenario, and another due to a binding scenario.

Surprisingly, our results show that _optimal threshold $\tau^{*}$ behaves
differently based on the availability erasure status feedback_. Specifically,
our numerical results show that 1) the optimal threshold $\tau^{*}$ is an
_increasing_ function in the erasure probability $\epsilon$ in the presence of
erasure status feedback, 2) the optimal threshold $\tau^{*}$ is an
_decreasing_ function in the erasure probability $\epsilon$ in the _absence_
of erasure status feedback, and 3) the optimal threshold is an increasing
function in the number of the observed processes $K$ for both problem
variants.

##  2 System Model

We consider a sensing system in which $K$ independent, but not necessarily
identical, OU processes are remotely monitored using a shared sensor that
transmits samples from the processes over an erasure channel to a receiver.
Denote the $k$th process value at time $s$ by $X_{s}^{[k]}$. Given
$X_{s}^{[k]}$, the $k$th OU process evolves, for $t\geq s$, as [41, 42]

$\displaystyle
X_{t}^{[k]}=X_{s}^{[k]}e^{-\theta_{k}(t-s)}+\frac{\sigma_{k}}{\sqrt{2\theta_{k}}}e^{-\theta_{k}(t-s)}W_{e^{2\theta_{k}(t-s)}-1},$
(1)

where $W_{t}$ denotes a Wiener process, while $\theta_{k}>0$ and
$\sigma_{k}>0$ are fixed parameters that control how fast the process evolves.
We study the system in steady-state, hence, we assume that the processes are
initiated as
$X_{0}^{[k]}\sim\mathcal{N}\left(0,\sigma_{k}^{2}/2\theta_{k}\right)$.333This
way, the variance of $X_{t}^{[k]}$ is $\sigma_{k}^{2}/2\theta_{k},~{}\forall
t$, and the autocorrelation function is
$\frac{\sigma_{k}^{2}}{2\theta_{k}}e^{-\theta_{k}|\tau|},~{}\tau\in\mathbb{R}$.
Thus, large values of $\sigma_{k}$ or $\theta_{k}$ indicate a fast-varying
process.

To estimate $\left\\{X_{t}^{[k]}\right\\}$ at the receiver, the sensor
acquires samples from the $k$th OU process at specific time instants
$\left\\{S_{i}^{[k]}\right\\}$ and sends them to the receiver. Sampling
instants are fully-controlled, i.e., samples are generated-at-will. We focus
on _signal-independent_ sampling policies, in which the optimal sampling
instants depend on the statistical measures of the processes and not on exact
processes’ values444We focus on the case in which the OU processes are non-
observable prior to sampling. The case in which the processes are fully
observable is to be studied in follow-up works..

The sensor must obey a total sampling frequency constraint $f_{\max}$. Let
$\ell_{i}$ denote the $i$th sampling instant regardless of the identity of the
process being sampled. For example, if process $1$ is sampled two times
consecutively and then process $2$ is sampled, then we have
$\ell_{1}=S_{1}^{[1]}$, $\ell_{2}=S_{2}^{[1]}$, and $\ell_{3}=S_{1}^{[2]}$.
Hence, it holds that
$\left\\{\ell_{i}\right\\}_{i=1}^{\infty}\supseteq\cup_{k}\left\\{S_{i}^{[k]}\right\\}_{i=1}^{\infty}$.
Therefore, the sampling constraint is expressed as follows:

$\displaystyle\liminf_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}\left[\sum_{i=1}^{n}\ell_{i+1}-\ell_{i}\right]\geq\frac{1}{f_{\max}},$
(2)

i.e., the long-term average inter-sampling time $\ell_{i+1}-\ell_{i}$ is
constrained to be no smaller than $\frac{1}{f_{\max}}$, which indicates that
the sensor shares the sampling budget $f_{\max}$ among the $K$ processes.
Samples go through a shared processing queue, whose service model follows a
Poisson process with service rate $\mu$, i.e., service times are independent
and identically distributed (i.i.d.) $\sim\exp(\mu)$ across samples. Served
samples are prune to erasures with probability $\epsilon$, also occuring
independently across samples.

Samples are time-stamped prior to transmissions, and successfully-received
samples from process $k$ determine the age-of-information (AoI) of that
process at the receiver, denoted $\texttt{AoI}^{[k]}(t)$. AoI is defined as
the time elapsed since the latest successfully received sample’s time stamp.

In this work, we investigate the effect of the presence/absence of the
_erasure status feedback_ on specifying the sampling time instants
$\left\\{S_{i}^{[k]}\right\\}$. Specifically, we study the following sampling
scenarios:

  1. 1.

_Erasure status feedback is available:_ In this case, an immediate erasure
status feedback is available at the sensor. We focus, in this case, on
_Maximum-Age-First (MAF) scheduling_ , in which the processes are sampled
according to their relative AoI’s, with priority given to the process with
highest AoI. Hence, at time $t$, process

$\displaystyle\kappa(t)\triangleq\arg\max_{k}\texttt{AoI}^{[k]}(t)$ (3)

is sampled. Observe that the value of $\kappa(t)$ will not change unless a
successful transmission occurs. Therefore, in case of erasure events, a fresh
sample is generated from the same process being served and transmission is re-
attempted.

  2. 2.

_Erasure status feedback is unavailable:_ In this case, the receiver does not
provide any feedback signaling to the sensor about the erasure status. In this
case, MAF scheduling is not a viable scheduling policy as the sensor cannot
identify the AoI of each process. Alternatively, we employ in this case the
_round-robin (RR) scheduling_ with new samples, i.e., the sensor acquires a
new sample from process 1, followed by a new sample from process 2, $\cdots$,
etc., irrespective of the erasure events.

Although both MAF and RR policies schedule the processes’ samples in the same
order $1,2,\cdots,K$, the two scheduling policies differ in the erasure
counter-measure. Specifically, the MAF scheduling keeps re-attempting to
sample the _same_ process until being successful. This is in contrast to RR
scheduling, which _keeps the order_ of the processes regardless of the erasure
events due to the absence of erasure status feedback.

Under both MAF and RR scheduling, and since the channel behaves similarly for
all processes, each process will eventually be given an equal share of the
allowed sampling budget, i.e., each process will be sampled at a rate of
$f_{\max}/K$, and the sampling constraint in (2) becomes

$\displaystyle\liminf_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}\left[\sum_{i=1}^{n}S_{i+1}^{[k]}-S_{i}^{[k]}\right]\geq\frac{K}{f_{\max}},\quad\forall
k.$ (4)

Let $\tilde{S}_{i}^{[k]}$ denote the sampling instant of the $i$th
successfully-received (unerased) sample from the $k$th process, and
(re-)define $S_{i}^{[k]}(m)$ as the sampling instant of the $m$th attempt to
convey the $i$th sample of the $k$th process, $m=1,\dots,M_{i}^{[k]}$, with
$M_{i}^{[k]}$ denoting the number of trials. Hence, we have
$S_{i}^{[k]}(m)\leq\tilde{S}_{i}^{[k]},~{}\forall m$, with equality at
$m=M_{i}^{[k]}$. Our channel model indicates that $M_{i}^{[k]}$’s are i.i.d.
$\sim\text{geometric}(1-\epsilon)$. Each sample $X_{S_{i}^{[k]}(m)}^{[k]}$
incurs a service time of $Y_{i}^{[k]}(m)$ time units with $Y_{i}^{[k]}(m)$’s
being i.i.d. $\sim\exp(\mu)$. The successfully-received sample,
$X_{\tilde{S}_{i}^{[k]}}^{[k]}$, arrives at the receiver at time
$D_{i}^{[k]}$, i.e.,

$\displaystyle
D_{i}^{[k]}=\tilde{S}_{i}^{[k]}+Y_{i}^{[k]}\left(M_{i}^{[k]}\right).$ (5)

Based on this notation, one can characterize the AoI of the $k$th OU process
as follows:

$\displaystyle\texttt{AoI}^{[k]}(t)=t-\tilde{S}_{i}^{[k]},\qquad
D_{i}^{[k]}\leq t<D_{i+1}^{[k]}.$ (6)

The receiver collects the unerased samples from all processes and uses them to
construct minimum mean square error (MMSE) estimates. Since the processes are
independent, and by the strong Markov property of the OU process, the MMSE
estimate for the $k$th process at time $t$, denoted $\hat{X}_{t}^{[k]}$, is
based solely on the latest successfully-received sample from that process.
Thus, for $D_{i}^{[k]}\leq t<D_{i+1}^{[k]}$, we have [38, 39]

$\displaystyle\hat{X}_{t}^{[k]}=$
$\displaystyle\mathbb{E}\left[X_{t}^{[k]}\Big{|}\tilde{S}_{i}^{[k]},X_{\tilde{S}_{i}^{[k]}}\right]$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq_ou_evol})}}{{=}}$ $\displaystyle
X_{\tilde{S}_{i}^{[k]}}e^{-\theta_{k}(t-\tilde{S}_{i}^{[k]})}.$ (7)

Let $\pi$ denote the scheduling policy, with $\pi\equiv\text{MAF}$ and
$\pi\equiv\text{RR}$ in the presence and absence of erasure status feedback,
respectively. Hence, the instantaneous mean square error (MSE) in estimating
the $k$th process at time $t\in\left[D_{i}^{[k]},D_{i+1}^{[k]}\right)$ is [38,
39]

$\displaystyle\texttt{mse}_{\pi}^{[k]}\left(t,\tilde{S}_{i}^{[k]}\right)$
$\displaystyle\triangleq{\mathbb{E}}\left[\left(X_{t}^{[k]}-\hat{X}_{t}^{[k]}\right)^{2}\right]$
(8)
$\displaystyle=\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-e^{-2\theta_{k}\left(t-\tilde{S}_{i}^{[k]}\right)}\right),$
(9)

which is an increasing function of the AoI in (6) as we have
$\texttt{mse}_{\pi}^{[k]}=\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-e^{-2\theta_{k}\texttt{AoI}^{[k]}(t)}\right)$.
Note that the MSE under MAF scheduling is different from that under RR
scheduling, and hence the distinction using the subscript $\pi$. Next, we
define the long-term time average MSE of the $k$th process as

$\displaystyle\overline{\texttt{mse}_{\pi}^{[k]}}\\!\triangleq\\!\limsup_{T\rightarrow\infty}\frac{\sum_{i=1}^{T}{\mathbb{E}}\left[\int_{D_{i}^{[k]}}^{D_{i+1}^{[k]}}\texttt{mse}_{\pi}^{[k]}\left(t,\tilde{S}_{i}^{[k]}\right)dt\right]}{\sum_{i=1}^{T}\mathbb{E}\left[D_{i+1}^{[k]}-D_{i}^{[k]}\right]}.$
(10)

Our goal is to choose the sampling instants to minimize a penalty function
$g(\cdot)$ of $\left\\{\overline{\texttt{mse}_{\pi}^{[k]}}\right\\}$ under the
sampling frequency constraint. More specifically, to solve the following
problem in the presence/absence of erasure status feedback:

$\displaystyle\min_{\\{S_{i}^{[k]}(m)\\}}$ $\displaystyle\quad
g\left(\overline{\texttt{mse}_{\pi}^{[1]}},\cdots,\overline{\texttt{mse}_{\pi}^{[K]}}\right)$
s.t.
$\displaystyle~{}~{}\liminf_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}\left[\sum_{i=1}^{n}S_{i+1}^{[k]}-S_{i}^{[k]}\right]\geq\frac{K}{f_{\max}},~{}\forall
k.$ (11)

##  3 Stationary Policies: Problem Re-Formulation

In this section, we re-formulate problem (2) in terms of a stationary waiting
policy for each process. In the sequel, we provide the details of such re-
formulation for both cases of erasure feedback availability.

###  3.1 Problem Re-Formulation in the Presence of Erasure Feedback

In this subsection, we focus on the case in which the erasure status feedback
is available. We define $W_{i}^{[k]}(m)$ as the $m$th waiting time before the
$m$th transmission attempt towards conveying the $i$th sample from the $k$th
process, $1\leq m\leq M_{i}^{[k]}$. Without loss of generality, let the MAF
schedule be in the order $1,2,\dots,K$. Thus, we have (see Fig. 2)

$\displaystyle S_{i}^{[k]}(m)=D_{i}^{[k-1]}$
$\displaystyle+\sum_{j=1}^{m-1}Y_{i}^{[k]}(j)+\sum_{j=1}^{m}W_{i}^{[k]}(j),$
(12)

with $D_{i}^{[0]}\triangleq D_{i-1}^{[K]}$. Problem (2) now reduces to
optimizing the waiting times $\left\\{W_{i}^{[k]}(m)\right\\}$. We now define
the $i$th _epoch_ of the $k$th process, denoted $\Gamma_{i}^{[k]}$, as the
inter-reception time in between its $i$th and $(i+1)$th unerased samples,
i.e.,

$\displaystyle\Gamma_{i}^{[k]}=D_{i+1}^{[k]}-D_{i}^{[k]}.$ (13)

Figure 2: Timing diagram of a typical epoch for $K=3$ processes in the
presence of erasure feedback and MAF scheduling. In this example, process 1
(in blue) is successful after one trial, process 2 (in green) is successful
after 3 trials, and process 3 (in red) is successful after 2 trials.

In this work, we focus on stationary waiting policies in which the waiting
policy $\left\\{W_{i}^{[k]}(m)\right\\}$ has the same distribution across all
processes’ epochs. Note that under MAF scheduling, each process epoch entails
a successful transmission of every other process. This, together with the fact
that service times and erasure events are i.i.d., induces a stationary
distribution across all processes’ epochs. Therefore, dropping the indices $i$
and $k$, we have $\Gamma_{i}^{[k]}\sim\Gamma,~{}\forall i,k$, where

$\displaystyle\Gamma=\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}W^{[k]}(m)+Y^{[k]}(m).$
(14)

Now consider a typical epoch for the $k$th process. By stationarity, one can
write (10) as

$\displaystyle\overline{\texttt{mse}_{\text{MAF}}^{[k]}}=\frac{{\mathbb{E}}\left[\int_{D^{[k]}}^{D^{[k]}+\Gamma}\texttt{mse}_{\text{MAF}}^{[k]}\left(t,\tilde{S}^{[k]}\right)dt\right]}{\mathbb{E}\left[\Gamma\right]}.$
(15)

where $D_{i}^{[k]}\sim D^{[k]}$ and $\tilde{S}_{i}^{[k]}\sim\tilde{S}^{[k]}$,
$\forall i$. In the sequel, we treat the $K$th (last) process’s epoch as the
typical epoch.

In the next lemma, we prove an important structural result, which asserts that
the positions of the waiting times do not matter. Specifically, we show that
one can achieve the same long-term average MSE penalty by grouping all the
waiting times at the beginning of the (typical) epoch (see Fig. 3).

###### Lemma 1

Under signal-independent sampling with MAF scheduling, problem (2) is
equivalent to the following optimization problem for stationary waiting
policies:

$\displaystyle\min_{W\geq 0}$ $\displaystyle\qquad
g\left(\overline{\texttt{mse}_{\text{MAF}}^{[1]}},\cdots,\overline{\texttt{mse}_{\text{MAF}}^{[K]}}\right)$
s.t.
$\displaystyle\qquad{\mathbb{E}}\left[(1-\epsilon)W+\sum_{k=1}^{K}Y^{[k]}\right]\geq\frac{K}{f_{\max}},$
(16)

where $W\triangleq\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}W^{[k]}(m)$ and the
waiting is only performed at the _beginning_ of the epoch.

Figure 3: Illustration of Lemma 1. The waiting times are grouped to the
beginning of the epoch without affecting the long-term average MSE penalty.

Proof:  By inspection of the average MSE function in (15), since
$\Gamma=\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}W^{[k]}(m)+\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}Y^{[k]}(m)$,
the waiting times appear in the numerator and denominator as the sum

$\displaystyle\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}W^{[k]}(m).$ (17)

Thus, for the optimal waiting times $\left\\{W^{[k]^{*}}(m)\right\\}$ that
solve the optimization problem in (2), the waiting time
$W^{*}=\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}W^{[k]^{*}}(m)$ achieves the same
$\overline{\texttt{mse}_{\text{MAF}}^{[k]}}$. Conversely, starting with
$W^{*}$ in the objective function of (1) and breaking it arbitrarily to any
waiting times such that
$W^{*}=\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}W^{[k]^{*}}(m)$ gives the same
objective function in (2).

As for the sampling constraint, by observing the telescoping sum in (4), we
have that for process $k$,

$\displaystyle\liminf_{n\rightarrow\infty}\frac{1}{n}{\mathbb{E}}\left[\sum_{i=1}^{n}S_{i+1}^{[k]}-S_{i}^{[k]}\right]$
$\displaystyle=\liminf_{n\rightarrow\infty}\frac{1}{n}{\mathbb{E}}\left[S_{n+1}^{[k]}\right].$
(18)

Now define $e(n)$ to be the index of the epoch corresponding to the $n$th
successfully-received sample. With
$W=\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}W^{[k]^{*}}(m)$, we can write the
sampling constraint as

$\displaystyle\liminf_{n\rightarrow\infty}\frac{e(n)}{n}$
$\displaystyle\cdot\frac{{\mathbb{E}}[S_{n+1}^{[k]}]}{e(n)}$ $\displaystyle=$
$\displaystyle\frac{1}{{\mathbb{E}}[M^{[k]}]}\cdot\liminf_{n\rightarrow\infty}\frac{1}{e(n)}\Bigg{(}\sum_{i=1}^{e(n)-1}{\mathbb{E}}\Bigg{[}\sum_{k=1}^{K}\sum_{m=1}^{M_{i}^{[k]}}W_{i}^{[k]}(m)+Y_{i}^{[k]}(m)\Bigg{]}+o\left(e(n)\right)\Bigg{)}$
(19) $\displaystyle=$
$\displaystyle\frac{1}{{\mathbb{E}}[M^{[k]}]}\cdot\liminf_{n\rightarrow\infty}\frac{1}{e(n)}\\!\\!\sum_{i=1}^{e(n)-1}\left({\mathbb{E}}[W]+{\mathbb{E}}\left[M_{i}^{[k]}\right]\cdot{\mathbb{E}}\left[\sum_{k=1}^{K}Y_{i}^{[k]}\right]\right)$
(20) $\displaystyle=$
$\displaystyle{\mathbb{E}}\left[(1-\epsilon)W+\sum_{k=1}^{K}Y^{[k]}\right],$
(21)

where (19) follows from the strong law of large numbers and the fact that the
time spent in the $e(n)$th epoch,
$\Delta=\sum_{\tilde{k}=1}^{k-1}\sum_{m=1}^{M^{[\tilde{k}]}}W_{i}^{[\tilde{k}]}(m)+Y_{i}^{[\tilde{k}]}(m)+\sum_{m=1}^{\tilde{m}}W_{i}^{[k]}(m)+Y_{i}^{[k]}(m)$,
is $o(e(n))$ and hence $\liminf_{n\rightarrow\infty}\frac{\Delta}{e(n)}=0$;
equation (20) follows from Wald’s identity.  $\blacksquare$

We now have the following remark:

###### Remark 1

Observe that the sampling constraint in problem (1) will not be active if
$f_{\max}>\mu$. This is intuitive since the inter-sampling time, on average,
would be larger than the minimum allowable sampling time, controlled by the
maximum allowable sampling frequency, in this case.

If the sampling constraint is binding, which occurs only if $f_{\max}<\mu$,
the average waiting time would monotonically increase with the erasure
probability $\epsilon$. This is true because no waiting is allowed in between
unsuccessful transmissions, whose rate increases with $\epsilon$. Hence, to
account for the expected large number of back-to-back sample transmissions in
the epoch, one has to wait for a relatively larger amount of time at its
beginning so that the sampling constraint is satisfied.

###  3.2 Problem Re-Formulation in the Absence of Erasure Feedback

In this subsection, we turn our attention to the other case, in which the
erasure status feedback is not available. Throughout our treatment, we
highlight the main differences compared to the re-formulation in Section 3.1.

Similar to Section 3.1, we define the $i$th epoch of the $k$th process
$\Gamma_{i}^{[k]}$ as the inter-reception time in between its $i$th and
$(i+1)$th successfully received samples. Despite the identical definition, we
note that the epoch $\Gamma_{i}^{[k]}$, in this case, consists of multiple
_transmission rounds_. Each round implies transmitting a _new sample_ from
each process in a round-robin fashion, i.e., in the order of $1,2,3,\cdots,K$
irrespective of the erasure outcome of transmission at the receiver.

The transmitter introduces stationary waiting times $\\{W_{i}^{[k]}(m)\\}$
between successive samples in each transmission round, i.e., the transmitter
waits for $W_{i}^{[k]}(m)$ time units after transmitting a sample from the
$(k-1)$th process before taking a new sample from the $k$th process at the
$m$th transmission round (see Fig. 4). With a slight abuse of notation, let
$Y_{i}^{[k]}(m)$ be the service time of the sample from the $k$th process in
the $i$th epoch at the $m$th transmission round. We have that
$Y_{i}^{[k]}(m)$’s are i.i.d. such that $Y_{i}^{[k]}(m)\sim\text{exp}(\mu)$.
Let $M_{i}^{[k]}$ denote the total number of transmission rounds needed to
convey the $i$th sample of the $k$th process. Consequently,
$M_{i}^{[k]}\sim\text{geometric}(1-\epsilon)$. We note that $M_{i}^{[k]}$
controls the epoch length $\Gamma_{i}^{[k]}$ irrespective of the other
processes’ erasure statuses. Without loss of generality, we focus on the $K$th
process. Under RR scheduling, we can express the sampling instant
$S_{i}^{[K]}(m)$, for $m=1,\cdots,M_{i}^{[K]}$ as

$\displaystyle
S_{i}^{[K]}(m)=S_{i}^{[K]}(m-1)+Y_{i}^{[K]}(m-1)+\sum_{k=1}^{K-1}Y_{i}^{[k]}+\sum_{k=1}^{[K]}W_{i}^{[k]}(m).$
(22)

Figure 4: Timing diagram of a typical epoch for $K=3$ processes in the absence
of erasure feedback and RR scheduling. In this example, we focus on
characterizing the epoch of process 3, which is successful after 2
transmission rounds. The erasures experienced by the remaining of the
processes is irrelevant to the epoch of process 3.

Based on the aforementioned description, we can write the $i$th epoch length
corresponding to the $k$th process as

$\displaystyle\Gamma_{i}^{[k]}=\sum_{m=1}^{M_{i}^{[k]}}\sum_{k=1}^{K}W_{i}^{[k]}(m)+Y_{i}^{[k]}(m).$
(23)

By imposing the stationarity restriction of the waiting policy, the i.i.d.
statistics of the service times and the erasure events, and the fact that
epoch corresponding to the $k$th process entails repeating the same cycle of
transmissions $M_{i}^{[k]}\sim\text{geometric}(1-\epsilon)$ times, we can drop
the indices $i$ and $k$ as we have done in Section 3.1 to have555It is worth
noting that the epoch definitions in (14) and (24) differ only in the order of
summation. This signifies the fact that in the presence of erasure status
feedback, the transmitter takes $M_{i}^{[k]}$ samples from the $k$th process
until being successful before sampling the $(k+1)$th process. This is in
contrast to passing by all processes _once_ and repeating this cycle $M$ times
to complete the epoch in the absence of erasure status feedback.

$\displaystyle\Gamma=\sum_{m=1}^{M}\sum_{k=1}^{K}W^{[k]}(m)+Y^{[k]}(m)$ (24)

Consequently, despite the subtle differences and the slight abuse of notation,
we can still write the long-term average MSE of the $k$th process as that in
(15) (after replacing MAF with RR).

Now, similar to Lemma 1, we can aggregate all waiting times in the $m$th round
at the _beginning of each transmission round_ , i.e., the transmitter waits
for

$\displaystyle W_{i}(m)=\sum_{k=1}^{K}W_{i}^{[k]}(m)$ (25)

time units in the $m$th round. Specifically, the transmitter waits for
$W_{i}(1)=\sum_{k=1}^{K}W_{i}^{[k]}(1)$ at the first round, after which the
transmitter acquires and transmits a sample from process 1, followed by a
sample from process 2, $\cdots$, followed by a sample from process $K$,
without any waiting times in between. Then the transmitter waits for
$W_{i}(2)=\sum_{k=1}^{K}W_{i}^{[k]}(2)$ before completing the second round-
robin cycle (second round) of sampling across all processes, $\cdots$, etc.
Similar to Lemma 1, this aggregation does not affect the long-term average MSE
and results in a simpler equivalent optimization problem (see Fig. 5). This is
summarized in the following lemma:

Figure 5: Illustration of Lemma 2. The waiting times are grouped to the
beginning of each transmission round without affecting the long-term average
sum MSE.

###### Lemma 2

Under signal-independent sampling with RR scheduling, problem (2) is
equivalent to the following optimization problem for stationary waiting
policies:

$\displaystyle\min_{W\geq 0}$ $\displaystyle\qquad
g\left(\overline{\texttt{mse}_{\text{RR}}^{[1]}},\cdots,\overline{\texttt{mse}_{\text{RR}}^{[K]}}\right)$
s.t.
$\displaystyle\qquad{\mathbb{E}}\left[W(m)+\sum_{k=1}^{K}Y^{[k]}\right]\geq\frac{K}{f_{\max}},$
(26)

where $W(m)\triangleq\sum_{k=1}^{K}W^{[k]}(m)$ and the waiting is only
performed at the beginning of the $m$th transmission round.

The proof of Lemma 2 follows the exact steps of the proof of Lemma 1 while
noting that the waiting time here is at the beginning of _every transmission
round_ and not at the beginning of the epoch as in Lemma. 1. Hence, the proof
is removed to avoid unnecessary repetitions.

###### Remark 2

We note that, in the absence of erasure status feedback, the transmitter
cannot aggregate all waiting times at the beginning of the epoch. This is due
to the fact that the epoch beginning time $D_{i}^{[k]}$ and end time
$D_{i+1}^{[k]}$ are only visible at the receiver side due to the absence of
the erasure status feedback.

###### Remark 3

The sampling constraint in (2) lacks the erasure effect in (1). This is due to
the fact that the number of samples at each transmission round is $K$ samples,
which is independent of the erasure events. This is in contrast to the number
of samples in an epoch in (1), which is significantly dependent on the erasure
probability.

###### Remark 4

We note that when $\epsilon=0$, $\text{MAF}\equiv\text{RR}$ scheduling, and
the optimization problems (2) with and without erasure status feedback are
indeed the same (i.e., problems (1) and (2) are the same) as the transmitter
acquires one sample only from each process during any epoch.

We discuss optimal solutions of problems (1) and (2) over the next two
sections, respectively, for specific MSE penalty functions.

##  4 Optimal Waiting Threshold and Minimum Sum MSE Characterization with
Erasure Feedback

In this section, we provide the optimal solution of problem (1) for a sum MSE
penalty

$\displaystyle
g\left(\overline{\texttt{mse}_{\text{MAF}}^{[1]}},\cdots,\overline{\texttt{mse}_{\text{MAF}}^{[K]}}\right)=\sum_{k=1}^{K}\overline{\texttt{mse}_{\text{MAF}}^{[k]}},$
(27)

together with a stationary deterministic waiting policy, in which the waiting
value at the beginning of an epoch is given by a deterministic function
$w(\cdot)$ of the previous epoch’s total service time, denoted $\tilde{Y}$,
i.e.,

$\displaystyle\tilde{Y}\sim\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}Y^{[k]}(m).$ (28)

Note that such choice of waiting policies emerges naturally since the MSE is
an increasing function of the AoI, whose value at the start of the epoch is,
in turn, an increasing function of $\tilde{Y}$. Stationary deterministic
policies have been used extensively in similar contexts in the literature,
see, e.g., [37, 38, 39], and have been shown to perform optimally.

Formally, substituting the above into problem (1), we now aim at solving the
following functional optimization problem:

$\displaystyle\min_{w(\cdot)\geq 0}$
$\displaystyle\quad\frac{\sum_{k=1}^{K}{\mathbb{E}}\left[\int_{D^{[k]}}^{D^{[k]}+\Gamma}\texttt{mse}_{\text{MAF}}^{[k]}\left(t,\tilde{S}^{[k]}\right)dt\right]}{\mathbb{E}\left[\Gamma\right]}$
s.t.
$\displaystyle\quad{\mathbb{E}}\left[w\left(\tilde{Y}\right)\right]\geq\frac{1}{1-\epsilon}\left(\frac{K}{f_{\max}}-\frac{K}{\mu}\right).$
(29)

Theorem 1 below provides the optimal solution of problem (4). We use the
compact vector notation
$\bm{\theta}\triangleq[\theta_{1}\>\>\theta_{2}\>\cdots\>\theta_{K}]$ and
$\bm{\sigma}\triangleq[\sigma_{1}^{2}\>\>\sigma_{2}^{2}\>\cdots\>\sigma_{K}^{2}]$.

###### Theorem 1

The optimal waiting policy $w^{*}(\cdot)$ that solves problem (4) is given by
the _threshold_ policy

$\displaystyle
w^{*}(z)=\left[\tau^{*}_{\text{MAF}}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma})-z\right]^{+},$
(30)

where the optimal threshold
$\tau^{*}_{\text{MAF}}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma})$ is given
by

$\displaystyle\tau^{*}_{\text{MAF}}=\max\left\\{G_{\bm{\theta},\bm{\sigma}}^{-1}\left(\beta^{*}\right),H^{-1}\left(\frac{1}{(1-\epsilon)}\left[\frac{K}{f_{\max}}-\frac{K}{\mu}\right]^{+}\right)\right\\},$
(31)

in which

$\displaystyle
G_{\bm{\theta},\bm{\sigma}}(x)\triangleq\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]e^{-2\theta_{k}x}\right),$
(32)

and $\beta^{*}$ corresponds to the optimal long-term average sum MSE in this
case, and is given by the unique solution of

$\displaystyle
p(\beta^{*})=\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(H(\tau^{*}_{\text{MAF}})+\frac{K}{\mu(1-\epsilon)}-\frac{1}{2\theta_{k}}\cdot\frac{\mu}{2\theta_{k}+\mu}(1-F_{k}(\tau^{*}_{\text{MAF}}))\right)$
$\displaystyle\hskip
216.81pt-\beta^{*}\left(H(\tau^{*}_{\text{MAF}})+\frac{K}{\mu(1-\epsilon)}\right)=0,$
(33)

in which $H(\cdot)$ and $F_{k}(\cdot)$ are defined as follows:

$\displaystyle
H(\tau)=\sum_{\rho=K}^{\infty}\binom{\rho-1}{K-1}\epsilon^{\rho-K}(1-\epsilon)^{K}\left[\tau\gamma(\mu\tau,\rho)-\frac{\rho}{\mu}\gamma(\mu\tau,\rho+1)\right],$
(34) $\displaystyle
F_{k}(\tau)=\sum_{\rho=K}^{\infty}\binom{\rho\\!-\\!1}{K\\!-\\!1}\epsilon^{\rho-K}(1\\!-\\!\epsilon)^{K}\left[e^{-2\theta_{k}\tau}\gamma(\mu\tau,\rho)\\!+\\!\left(\frac{\mu}{2\theta_{k}+\mu}\right)^{\rho}(1\\!-\\!\gamma((2\theta_{k}\\!+\\!\mu)\tau,\rho)\right],$
(35)

where $\gamma(x,y)$ is the normalized incomplete Gamma function:
$\gamma(x,y)=\frac{1}{(y-1)!}\int_{0}^{x}t^{y-1}e^{-t}dt$.

Proof:  We follow Dinkelbach’s approach [43] to solve the optimization problem
in (4). We start by defining an auxiliary function $p(\beta)$, for $\beta\geq
0$, such that:

$\displaystyle p(\beta)=\min_{w(\cdot)\geq 0}$
$\displaystyle\quad\sum_{k=1}^{K}{\mathbb{E}}\left[\int_{D}^{D+\Gamma(K,\epsilon,w)}\texttt{mse}_{\text{MAF}}^{[k]}(t,\tilde{S}_{i}^{[k]})dt\right]-\beta{\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]$
s.t.
$\displaystyle\quad{\mathbb{E}}\left[(1-\epsilon)w\left(\tilde{Y}\right)+\sum_{k=1}^{K}Y^{[k]}\right]\geq\frac{K}{f_{\max}}$
(36)

The optimal solution of our original optimization problem (4) is the solution
of $p(\beta^{*})=0$ of the auxiliary problem above [43].

The Lagrangian corresponding to the auxiliary problem can be written as:

$\displaystyle\mathcal{L}=$
$\displaystyle\sum_{k=1}^{K}{\mathbb{E}}\left[\int_{D}^{D+\Gamma(K,\epsilon,w)}\texttt{mse}_{\text{MAF}}^{[k]}(t,\tilde{S}_{i}^{[k]})dt\right]-\beta{\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]-\int_{0}^{\infty}\eta(y)w(y)dy$
$\displaystyle-\zeta\left({\mathbb{E}}\left[(1-\epsilon)w\left(\tilde{Y}\right)+\sum_{k=1}^{K}Y^{[k]}\right]-\frac{K}{f_{\max}}\right)$
(37)

Now, denoting $\tilde{Y}=\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}Y^{[k]}(m)$, we
calculate the expected epoch length as:

$\displaystyle{\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]=$
$\displaystyle{\mathbb{E}}\left[w(\tilde{Y})+\sum_{k=1}^{K}\tilde{Y}\right]$
(38) $\displaystyle=$
$\displaystyle{\mathbb{E}}\left[w(\tilde{Y})\right]+\sum_{k=1}^{K}{\mathbb{E}}\left[M^{[k]}\right]{\mathbb{E}}\left[Y^{[k]}\right]$
(39) $\displaystyle=$
$\displaystyle{\mathbb{E}}\left[w(\tilde{Y})\right]+\frac{K}{\mu(1-\epsilon)}$
(40)

where (39) follows from Wald’s identity. The expected total MSE in the epoch
can be calculated as:

$\displaystyle{\mathbb{E}}\left[\int_{D_{i}}^{D_{i}+\Gamma(K,\epsilon,w)}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-e^{-2\theta_{k}\left(t-\tilde{S}_{i}^{[k]}\right)}\right)dt\right]$
$\displaystyle\hskip
36.135pt=\frac{\sigma_{k}^{2}}{2\theta_{k}}\left({\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]-\frac{1}{2\theta_{k}}{\mathbb{E}}\left[e^{2\theta_{k}\tilde{S}_{i}^{[k]}}\left(e^{-2\theta_{k}D}-e^{-2\theta_{k}(D+\Gamma(K,\epsilon,w))}\right)\right]\right)$
(41) $\displaystyle\hskip
36.135pt=\frac{\sigma_{k}^{2}}{2\theta_{k}}\left({\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]-\frac{1}{2\theta_{k}}{\mathbb{E}}\left[e^{-2\theta_{k}Y_{0}}\left(1-e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right)\right]\right)$
(42) $\displaystyle\hskip
36.135pt=\frac{\sigma_{k}^{2}}{2\theta_{k}}\left({\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]-\frac{1}{2\theta_{k}}{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]\left(1-{\mathbb{E}}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right)\right]\right).$
(43)

We note the following functional derivatives with respect to $w(\cdot)$ (at
realization $\tilde{Y}=z$),

$\displaystyle\frac{\partial}{\partial
w(\cdot)}{\mathbb{E}}[w(\tilde{Y})]=f_{\tilde{Y}}(z),$ (44)
$\displaystyle\frac{\partial}{\partial
w(\cdot)}{\mathbb{E}}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right]=\frac{\partial}{\partial
w(\cdot)}{\mathbb{E}}\left[e^{-2\theta_{k}(w(\tilde{Y})+\tilde{Y})}\right]=-2\theta_{k}e^{-2\theta_{k}(w(z)+z)}f_{\tilde{Y}}(z),$
(45) $\displaystyle\frac{\partial}{\partial
w(\cdot)}\int_{0}^{\infty}\eta(y)w(y)dy=\eta(z).$ (46)

By substituting in (4) and use the stationarity condition of the Lagrangian
with respect to the functional $w(\cdot)$, i.e.,
$\frac{\partial\mathcal{L}}{\partial w(z)}=0$, we get

$\displaystyle\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(f_{\tilde{Y}}(z)-{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]e^{-2\theta_{k}(w^{*}(z)+z)}f_{\tilde{Y}}(z)\right)-\beta
f_{\tilde{Y}}(z)-\eta(z)-\zeta(1-\epsilon)f_{\tilde{Y}}(z)=0,$ (47)

which leads to

$\displaystyle\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]e^{-2\theta_{k}(w^{*}(z)+z)}\right)=\beta+\zeta(1-\epsilon)+\frac{\eta(z)}{f_{\tilde{Y}}(z)}.$
(48)

Now define the function $G_{\bm{\theta},\bm{\sigma}^{2}}(\cdot)$ as

$\displaystyle
G_{\bm{\theta},\bm{\sigma}^{2}}(x)=\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]e^{-2\theta_{k}x}\right).$
(49)

Such function is monotonically increasing. Consequently, the equation
$G_{\bm{\theta},\bm{\sigma}^{2}}(w^{*}(z)+z)=\beta+\zeta(1-\epsilon)+\frac{\eta(y)}{f_{\tilde{Y}}(z)}$
has a unique solution, which is given by

$\displaystyle
w^{*}(z)+z=G_{\bm{\theta},\bm{\sigma}^{2}}^{-1}\left(\beta+\zeta(1-\epsilon)+\frac{\eta(y)}{f_{\tilde{Y}}(z)}\right).$
(50)

Using the complementary slackness for the constraint $w(\cdot)\geq 0$ [44], we
have,

$\displaystyle
w^{*}(z)=\left[G_{\bm{\theta},\bm{\sigma}^{2}}^{-1}\left(\beta+\zeta(1-\epsilon)\right)-z\right]^{+}.$
(51)

This proves the first part of the theorem, which states that the optimal
waiting function is in fact a threshold policy with a threshold

$\displaystyle\tau^{*}_{\text{MAF}}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma}^{2})=G_{\bm{\theta},\bm{\sigma}^{2}}^{-1}\left(\beta+\zeta(1-\epsilon)\right)$
(52)

Now, we focus on characterizing the Lagrange multiplier $\zeta$. First, if
$f_{\max}\geq\mu$, then ${\mathbb{E}}[w(\tilde{Y})]\geq 0$, which is feasible
for any $w(\cdot)\geq 0$. Consequently, in this case the sampling constraint
is never active and $\zeta^{*}=0$, i.e.,

$\displaystyle\tau^{*}_{\text{MAF}}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma}^{2})=G_{\bm{\theta},\bm{\sigma}^{2}}^{-1}\left(\beta\right),\quad\text{if
$f_{\max}\geq\mu$}.$ (53)

Next, we consider the other case, i.e., when $f_{\max}<\mu$. In this case, we
need to evaluate the expected value of the waiting function
${\mathbb{E}}[w(\tilde{Y})]$ with an arbitrary threshold $\tau$. We denote
this expected value by $H(\tau)$:

$\displaystyle
H(\tau)={\mathbb{E}}\left[w(\tilde{Y})\right]={\mathbb{E}}\left[(\tau-\tilde{Y})^{+}\right].$
(54)

To evaluate (54), we need to characterize the statistical distribution of
$\tilde{Y}$. By the law of total probability, we can write,

$\displaystyle
f_{\tilde{Y}}(z)=\sum_{\rho=K}^{\infty}f_{\tilde{Y}|\sum_{k=1}^{K}M^{[k]}}\left(z\left|\sum_{k=1}^{K}M^{[k]}=\rho\right.\right)\mathbb{P}\left(\sum_{k=1}^{K}M^{[k]}=\rho\right).$
(55)

Conditioned on $\sum_{k=1}^{K}M^{[k]}=\rho$, then
$\tilde{Y}=\sum_{k=1}^{K}\sum_{m=1}^{M^{[k]}}Y^{[k]}(m)$ is a sum of $\rho$
i.i.d. exponential random variables. Hence,
$\tilde{Y}|\rho\sim\text{Erlang}(\rho,\mu)$, i.e.,

$\displaystyle
f_{\tilde{Y}|\sum_{k=1}^{K}M^{[k]}}\left(z|\rho\right)=\frac{\mu^{\rho}z^{\rho-1}e^{-\mu
z}}{(\rho-1)!},\quad z\geq 0.$ (56)

Further, the distribution of $\sum_{k=1}^{K}M^{[k]}$ is given by

$\displaystyle\mathbb{P}\left(\sum_{k=1}^{K}M^{[k]}=\rho\right)=\binom{\rho-1}{K-1}\epsilon^{\rho-K}(1-\epsilon)^{K},\quad\rho\geq
K.$ (57)

Substituting the above in (54) leads to

$\displaystyle H(\tau)$
$\displaystyle=\int_{0}^{\tau}(\tau-z)f_{\tilde{Y}}(z)dz$ (58)
$\displaystyle=\sum_{\rho=K}^{\infty}\binom{\rho-1}{K-1}\epsilon^{\rho-K}(1-\epsilon)^{K}\frac{\mu^{\rho}}{(\rho-1)!}\left[\tau\int_{0}^{\tau}z^{\rho-1}e^{-\mu
z}dz-\int_{0}^{\tau}z^{\rho}e^{-\mu z}dz\right]$ (59)
$\displaystyle=\sum_{\rho=K}^{\infty}\binom{\rho-1}{K-1}\epsilon^{\rho-K}(1-\epsilon)^{K}\frac{\mu^{\rho}}{(\rho-1)!}\left[\tau\frac{(\rho-1)!}{\mu^{\rho}}\gamma(\mu\tau,\rho)-\frac{\rho!}{\mu^{\rho+1}}\gamma(\mu\tau,\rho+1)\right]$
(60)
$\displaystyle=\sum_{\rho=K}^{\infty}\binom{\rho-1}{K-1}\epsilon^{\rho-K}(1-\epsilon)^{K}\left[\tau\gamma(\mu\tau,\rho)-\frac{\rho}{\mu}\gamma(\mu\tau,\rho+1)\right],$
(61)

where interchanging sum and integral in (59) follows from the dominated
convergence theorem and $\gamma(x,y)$ is the normalized incomplete Gamma
function:

$\displaystyle\gamma(x,y)=\frac{1}{(y-1)!}\int_{0}^{x}t^{y-1}e^{-t}dt$ (62)

Now observe that the sampling constraint in (18) can be written as:

$\displaystyle(1-\epsilon)H(\tau)\geq\frac{K}{f_{\max}}-\frac{K}{\mu}.$ (63)

Thus, if
$(1-\epsilon)H\left(G_{\bm{\theta},\bm{\sigma}^{2}}^{-1}\left(\beta\right)\right)>\frac{K}{f_{\max}}-\frac{K}{\mu}$,
then $\zeta^{*}=0$ and the threshold for the unconstrained problem (without
the sampling constraint) is optimal.

Otherwise, the constraint is satisfied with equality,
i.e.,$(1-\epsilon)H(\tau)=\frac{K}{f_{\max}}-\frac{K}{\mu}$, and hence,

$\displaystyle\tau^{*}=\frac{1}{(1-\epsilon)}H^{-1}\left(\frac{K}{f_{\max}}-\frac{K}{\mu}\right).$
(64)

All this put together implies that

$\displaystyle\tau^{*}_{\text{MAF}}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma}^{2})=\max\left\\{G_{\bm{\theta},\bm{\sigma}^{2}}^{-1}\left(\beta\right),\frac{1}{(1-\epsilon)}H^{-1}\left(\frac{K}{f_{\max}}-\frac{K}{\mu}\right)\right\\}.$
(65)

Finally, we solve for the optimal long-term MMSE, $\beta^{*}$. Denote
${\mathbb{E}}[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}]$ by $F(\tau)$. By
observing that

$\displaystyle F_{k}(\tau)$
$\displaystyle={\mathbb{E}}[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}]$ (66)
$\displaystyle=\int_{0}^{\tau}e^{-2\theta_{k}\tau}f_{\tilde{Y}}(z)dz+\int_{\tau}^{\infty}e^{-2\theta_{k}z}f_{\tilde{Y}}(z)dz$
(67)
$\displaystyle=\sum_{\rho=K}^{\infty}\binom{\rho-1}{K-1}\epsilon^{\rho-K}(1-\epsilon)^{K}\frac{\mu^{\rho}}{(\rho-1)!}\left[e^{-2\theta_{k}\tau}\\!\\!\\!\int_{0}^{\tau}\\!\\!\\!z^{\rho-1}e^{-\mu
z}dz\\!+\\!\\!\int_{\tau}^{\infty}\\!\\!\\!z^{\rho-1}e^{-(2\theta_{k}+\mu)z}dz\right]$
(68)
$\displaystyle=\sum_{\rho=K}^{\infty}\binom{\rho-1}{K-1}\epsilon^{\rho-K}(1-\epsilon)^{K}\left[e^{-2\theta_{k}\tau}\gamma(\mu\tau,\rho)\\!+\\!\left(\frac{\mu}{2\theta_{k}+\mu}\right)^{\rho}(1\\!-\\!\gamma((2\theta_{k}\\!+\\!\mu)\tau,\rho)\right],$
(69)

$\beta^{*}$ can be obtained by solving the auxiliary problem $p(\beta^{*})=0$,
i.e., solving (1).

This concludes the proof.  $\blacksquare$

###### Remark 5

We observe that the optimal threshold $\tau^{*}$ in (31) is increasing with
the erasure probability $\epsilon$. This is indeed the case since both
$G^{-1}_{\bm{\theta},\bm{\sigma}}(\cdot)$ and $H^{-1}(\cdot)$ are increasing
functions, and both of their arguments are increasing with $\epsilon$ (the
optimal long-term average sum MSE $\beta^{*}$, for instance, can only increase
with higher erasure rates). This can be attributed to the fact that for higher
erasure probabilities, the average samples’ inter-delivery time increases.
This, in turn, causes the transmitter to wait more before sending a new sample
to make sure that the new sample is sufficiently different from the previously
delivered sample; this new sample will be used to estimate the signal over a
large period of time because of the large expected inter-delivery time caused
by the high erasure probability. In this case, the transmitter will be blocked
from generating new samples waiting for the previous sample to be delivered.
On the other hand, and for smaller erasure probabilities, we can see that the
waiting time decreases. Again, this can be attributed to the fact that for
smaller erasure probabilities, the average samples’ delivery time decreases.
This means that when the transmitter has a chance to transmit a sample, it
would be better to do so as this sample will be delivered quickly and it will
not block the transmitter from sending new samples.

Note that the fact that second term in the $\max$ function, $H^{-1}$, is
increasing with $\epsilon$ is consistent with the observation in Remark 1; the
higher the erasure rate, the larger the waiting time should be to compensate
for the high rate of back-to-back transmissions under MAF scheduling that
takes a toll on the sampling frequency in this case.

##  5 Optimal Waiting Threshold and Minimum Sum MSE Characterization without
Erasure Feedback

In this section, we consider the setting in which the receiver does not
provide erasure status feedback to the transmitter. As in Section 4, we focus
on the sum MSE penalty together with stationary deterministic waiting
policies.

With a slight abuse of notation, let
$\tilde{Y}_{i}(m)=\sum_{k=1}^{K}Y_{i}^{[k]}(m)$ be the sum of the service
times during the $m$th transmission round. To develop a stationary
deterministic waiting policy, we cannot rely on the starting MSE of the epoch
(or the starting AoI) since the transmitter does not know of its exact
starting time due to the absence of the erasure feedback. Alternatively, we
focus our attention on a waiting time that is a function $w(\cdot)$ of the sum
of service times of all processes in the preceding transmission round, as
opposed to the preceding epoch, i.e., we set

$\displaystyle
W_{i}(m)=w\left(\tilde{Y}_{i}(m-1)\right)=w\left(\sum_{k=1}^{K}Y_{i}^{[k]}(m-1)\right),$
(70)

with $\tilde{Y}_{i}(0)\triangleq Y_{i-1}(M_{i-1})$ by definition. This policy
is realizable in the absence of erasure feedback since the start and end of
transmission rounds are known at the transmitter side. Note that this policy
is a stationary deterministic waiting policy since $\tilde{Y}_{i}(m)$’s are
i.i.d across all transmission rounds.

Similar to Section 4, problem (2) in Lemma 2 can be written in the following
functional form:

$\displaystyle\min_{w(\cdot)\geq 0}$
$\displaystyle\quad\frac{\sum_{k=1}^{K}{\mathbb{E}}\left[\int_{D^{[k]}}^{D^{[k]}+\Gamma}\texttt{mse}_{\text{RR}}^{[k]}\left(t,\tilde{S}^{[k]}\right)dt\right]}{\mathbb{E}\left[\Gamma\right]}$
s.t.
$\displaystyle\quad{\mathbb{E}}\left[w\left(\tilde{Y}\right)\right]\geq\frac{K}{f_{\max}}-\frac{K}{\mu}.$
(71)

Theorem 2 below provides the solution of problem (5).

###### Theorem 2

The optimal waiting policy $w^{*}(\cdot)$ that solves problem (5) is given by
the _threshold_ policy

$\displaystyle
w^{*}(z)=\left[\tau_{\text{RR}}^{*}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma})-z\right]^{+},$
(72)

where the optimal threshold
$\tau_{\text{RR}}^{*}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma})$ is given
by

$\displaystyle\tau_{\text{RR}}^{*}(K,f_{\max},\epsilon,\bm{\theta},\bm{\sigma}^{2})=\max\left\\{\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon}^{-1}(\beta),\tilde{H}^{-1}\left(\frac{K}{f_{\max}}-\frac{K}{\mu}\right)\right\\}$
(73)

in which

$\displaystyle\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon}(x)\triangleq\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]\frac{(1-\epsilon)^{2}e^{-2\theta_{k}x}}{\left(1-\epsilon
L_{k}(x)\right)^{2}}\right),$ (74)

with $L_{k}(\cdot)$ being

$\displaystyle L_{k}(x)\triangleq e^{-2\theta_{k}x}\gamma(\mu
x,K)+\left(\frac{\mu}{\mu+2\theta_{k}}\right)^{K}(1-\gamma\left((2\theta_{k}+\mu)x,K\right),$
(75)

and $\beta^{*}$ corresponds to the optimal long-term average sum MSE in this
case, and is given by the unique solution of

$\displaystyle\tilde{p}(\beta)=\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(\frac{\tilde{H}(\tau^{*}_{\text{RR}})+\frac{K}{\mu}}{1-\epsilon}-\frac{1}{2\theta_{k}}\cdot\frac{\mu}{\mu+2\theta_{k}}\cdot\left(1-\tilde{F}_{k}(\tau^{*}_{\text{RR}})\right)\right)-\beta\left(\frac{\tilde{H}(\tau^{*}_{\text{RR}})+\frac{K}{\mu}}{1-\epsilon}\right)=0,$
(76)

in which $\tilde{H}(\cdot)$ and $\tilde{F}_{k}(\cdot)$ are defined as follows:

$\displaystyle\tilde{H}(\tau)=\tau\gamma\left(\mu\tau,K\right)-\frac{K}{\mu}\gamma\left(\mu\tau,K+1\right),$
(77)
$\displaystyle\tilde{F}_{k}(\tau)=\frac{(1-\epsilon)L_{k}(\tau)}{1-\epsilon
L_{k}(\tau)}$ (78)

where $\gamma(x,y)$ is the normalized incomplete Gamma function.

Proof:  Similar to the proof of Theorem 1, we follow the Dinkelbach’s approach
to solve the optimization problem in (5). We start by defining the auxiliary
function $\tilde{p}(\beta)$ for $\beta\geq 0$, such that:

$\displaystyle\tilde{p}(\beta)=\min_{w(\cdot)\geq 0}$
$\displaystyle\quad\sum_{k=1}^{K}{\mathbb{E}}\left[\int_{D}^{D+\Gamma(K,\epsilon,w)}\texttt{mse}_{\text{RR}}^{[k]}(t,\tilde{S}_{i}^{[k]})dt\right]-\beta{\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]$
s.t.
$\displaystyle\quad{\mathbb{E}}\left[w\left(\tilde{Y}\right)+\sum_{k=1}^{K}Y^{[k]}\right]\geq\frac{K}{f_{\max}}$
(79)

Hence, the Lagrangian function corresponding the auxiliary problem above is
given by

$\displaystyle\mathcal{L}=$
$\displaystyle\sum_{k=1}^{K}{\mathbb{E}}\left[\int_{D}^{D+\Gamma(K,\epsilon,w)}\texttt{mse}_{\text{RR}}^{[k]}(t,\tilde{S}_{i}^{[k]})dt\right]-\beta{\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]-\int_{0}^{\infty}\eta(y)w(y)dy$
$\displaystyle-\zeta\left({\mathbb{E}}\left[w\left(\tilde{Y}\right)+\sum_{k=1}^{K}Y^{[k]}\right]-\frac{K}{f_{\max}}\right).$
(80)

Without loss of generality, we focus on the epoch of the $K$th process. In
this case, we can write $\Gamma_{i}^{[K]}$ as

$\displaystyle\Gamma_{i}^{[K]}=w\left(\tilde{Y}_{i-1}(M_{i-1}^{[K]})\right)+\sum_{m=1}^{M_{i}^{[K]}-1}\tilde{Y}_{i}(m)+w\left(\tilde{Y}_{i}(m)\right)+\tilde{Y}_{i}\left(M_{i}^{[K]}\right),$
(81)

where $M_{i}^{[K]}\geq 2$. Note that
$\Gamma_{i}^{[1]}\sim\cdots\sim\Gamma_{i}^{[K]}\sim\Gamma(K,w,\epsilon)$.
Moreover, due to the stationarity of the waiting policy, we can drop the
indices $i$, and $K$, and re-define
$\tilde{Y}_{i-1}^{[K]}(M_{i-1}^{K})=\tilde{\underline{Y}}$, and
$\tilde{Y}_{i}^{[K]}(M_{i}^{K})=\tilde{\bar{Y}}$. Hence, we have the expected
epoch length given by

$\displaystyle\mathbb{E}\left[\Gamma(K,\epsilon,w)\right]$
$\displaystyle=\mathbb{E}\left[\Gamma_{i}^{[K]}\right]$ (82)
$\displaystyle=\mathbb{E}[w(\tilde{\underline{Y}})]+\mathbb{E}[M-1]\cdot\mathbb{E}[\tilde{Y}+w(\tilde{Y})]+\mathbb{E}[\tilde{\bar{Y}}]$
(83)
$\displaystyle=\mathbb{E}[M]\cdot\left(\mathbb{E}[\tilde{Y}]+\mathbb{E}[w(\tilde{Y})]\right)$
(84) $\displaystyle=\frac{\frac{K}{\mu}+\mathbb{E}[w(\tilde{Y})]}{1-\epsilon}$
(85)

where (83) follows from Wald’s equation, (84) follows from the fact that the
aggregate service times
$\tilde{\underline{Y}}\sim\tilde{Y}\sim\tilde{\bar{Y}}\sim\text{Erlang}(K,\mu)$
as the individual service times are i.i.d. $\sim\text{exp}(\mu)$, and (85)
follows from the fact that the number of transmission rounds
$M\sim\text{geometric}(1-\epsilon)$. From (43), we have the expected MSE in
the epoch given by

$\displaystyle{\mathbb{E}}$
$\displaystyle\left[\int_{D_{i}}^{D_{i}+\Gamma(K,\epsilon,w)}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-e^{-2\theta_{k}\left(t-\tilde{S}_{i}^{[k]}\right)}\right)dt\right]$
$\displaystyle\qquad\qquad\qquad\qquad=\frac{\sigma_{k}^{2}}{2\theta_{k}}\left({\mathbb{E}}\left[\Gamma(K,\epsilon,w)\right]-\frac{1}{2\theta_{k}}{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]\left(1-{\mathbb{E}}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right)\right]\right).$
(86)

Due to the stationary policy $w(\cdot)$, and the fact that all service times
are i.i.d., we can evaluate the expectation
$\mathbb{E}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right]$ as follows:

$\displaystyle\mathbb{E}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right]=$
$\displaystyle\mathbb{E}\left[\mathbb{E}\left[e^{-2\theta_{k}\sum_{m=0}^{M-1}w(\tilde{Y}(m))+\tilde{Y}(m)}|M\right]\right]$
(87) $\displaystyle=$
$\displaystyle\sum_{m=1}^{\infty}\left(\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})+\tilde{Y})}\right]\right)^{m}\epsilon^{m-1}(1-\epsilon)$
(88) $\displaystyle=$
$\displaystyle\frac{(1-\epsilon)\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})+\tilde{Y})}\right]}{1-\epsilon\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})+\tilde{Y})}\right]}$
(89)

where (87) follows from iterated expectation over the number of transmission
rounds $M$ with $\tilde{Y}(0)=\tilde{\underline{Y}}\sim\tilde{\bar{Y}}$. This
leads to the following functional derivative of the expectation
$\mathbb{E}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right]$ with respect to
$w(\cdot)$ (at realization $\tilde{Y}=z$),

$\displaystyle\frac{\partial}{\partial
w(\cdot)}\mathbb{E}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right]=\frac{-2\theta_{k}(1-\epsilon)e^{-2\theta_{k}(w(z)+z)}f_{\tilde{Y}}(z)}{\left(1-\epsilon\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})+\tilde{Y})}\right]\right)^{2}}.$
(90)

Applying the stationarity condition of the Lagrangian with respect to the
functional $w(\cdot)$, $\frac{\partial\mathcal{L}}{\partial w(z)}=0$, we get
the following optimality condition:

$\displaystyle\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1\\!-\\!{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]\frac{(1-\epsilon)^{2}e^{-2\theta_{k}(w(z)+z)}}{\left(1-\epsilon\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})\\!+\\!\tilde{Y})}\right]\right)^{2}}\right)=\beta\\!+\\!\frac{(1-\epsilon)\eta(z)}{f_{\tilde{Y}}(z)}\\!+\\!(1-\epsilon)\zeta.$
(91)

Define the function
$\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon,w}(\cdot)$ as

$\displaystyle\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon,w}(x)=\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1\\!-\\!{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]\frac{(1-\epsilon)^{2}e^{-2\theta_{k}x}}{\left(1-\epsilon\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})\\!+\\!\tilde{Y})}\right]\right)^{2}}\right)$
(92)

Observe that the function $G_{\bm{\theta},\bm{\sigma}^{2},\epsilon,w}$ is a
monotonically increasing function in $x$ (given that
$\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})\\!+\\!\tilde{Y})}\right]$ for
any specific choice of $w(\cdot)$ is fixed, irrespective of the realizations).
Thus, using the complementary slackness condition, the optimal waiting
function is indeed a threshold waiting policy in the form of 666The optimal
threshold seems to be _self-dependent_ through the expectation term
$\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})\\!+\\!\tilde{Y})}\right]$. This
does not affect the claim that the optimal waiting policy is a threshold
policy, as the function
$\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon,w}(\cdot)$ is a monotone
function for any choice of $w(\cdot)$, which further implies the existence of
a unique solution. Nevertheless, finding this threshold numerically would
require iterating back and forth between the expectation term $L_{k}(\tau)$
(see (94)) and the inverse function
$\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon,w}^{-1}(\cdot)$ as we show
later on in the proof.

$\displaystyle
w^{*}(z)=\left[\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon,w}^{-1}\left(\beta\\!+\\!(1-\epsilon)\zeta\right)-z\right]^{+}.$
(93)

Now that the threshold behavior has been established, we note that the
threshold policy maintains the monotonicity behavior of $\tilde{G}(\cdot)$
since $\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y})\\!+\\!\tilde{Y})}\right]$
would be a monotone decreasing function in the threshold value.

Considering a threshold waiting policy of the form
$w(\tilde{y})=\left[\tau-\tilde{y}\right]^{+}$, and since
$\tilde{Y}\sim\text{Erlang}(K,\mu)$, we can evaluate the expectation in
$\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y}+\tilde{Y}))}\right]$, denoted by
$L_{k}(\tau)$, as follows:

$\displaystyle
L_{k}(\tau)\triangleq\mathbb{E}\left[e^{-2\theta_{k}(w(\tilde{Y}+\tilde{Y}))}\right]$
$\displaystyle=\int_{0}^{\tau}e^{-2\theta_{k}\tau}\frac{\mu^{K}\tilde{y}^{K-1}e^{-\mu\tilde{y}}}{(K-1)!}d\tilde{y}+\int_{\tau}^{\infty}e^{-2\theta_{k}\tilde{y}}\frac{\mu^{K}\tilde{y}^{K-1}e^{-\mu\tilde{y}}}{(K-1)!}d\tilde{y}$
(94)
$\displaystyle=e^{-2\theta_{k}\tau}\gamma(\mu\tau,K)+\frac{\mu^{K}}{(K-1)!}\int_{\tau}^{\infty}\tilde{y}^{K-1}e^{-(2\theta_{k}+\mu)}d\tilde{y}$
(95)
$\displaystyle=e^{-2\theta_{k}\tau}\gamma(\mu\tau,K)+\left(\frac{\mu}{\mu+2\theta_{k}}\right)^{K}(1-\gamma\left((2\theta_{k}+\mu)\tau),K\right).$
(96)

In this case, the function
$\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon}(\cdot)$ (we dropped the
$w(\cdot)$ dependence as we deal with a threshold structure) can be re-written
as:

$\displaystyle\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon}(x)=\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1\\!-\\!{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]\frac{(1-\epsilon)^{2}e^{-2\theta_{k}x}}{\left(1-\epsilon
L_{k}(x)\right)^{2}}\right).$ (97)

We also evaluate the expected waiting time function, $\tilde{H}(\tau)$, as

$\displaystyle\tilde{H}(\tau)\triangleq\mathbb{E}[w(\tilde{Y})]$
$\displaystyle=\mathbb{E}\left[\left[\tau-\tilde{Y}\right]^{+}\right]$ (98)
$\displaystyle=\int_{0}^{\tau}(\tau-\tilde{y})f(\tilde{y})d\tilde{y}$ (99)
$\displaystyle=\tau\int_{0}^{\tau}\frac{\mu^{K}\tilde{y}^{K-1}e^{-\mu\tilde{y}}}{(K-1)!}d\tilde{y}-\int_{0}^{\tau}\tilde{y}\frac{\mu^{K}\tilde{y}^{K-1}e^{-\mu\tilde{y}}}{(K-1)!}d\tilde{y}$
(100)
$\displaystyle=\tau\gamma\left(\mu\tau,K\right)-\frac{K}{\mu}\gamma\left(\mu\tau,K+1\right).$
(101)

Finally, for compactness, we define

$\displaystyle\tilde{F}_{k}(\tau)\triangleq{\mathbb{E}}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right]=\frac{(1-\epsilon)L_{k}(\tau)}{1-\epsilon
L_{k}(\tau)}.$ (102)

Plugging all these quantities into the long-term average MSE penalty, we get

$\displaystyle\sum_{k=1}^{K}\overline{\texttt{mse}_{\text{RR}}^{[k]}}$
$\displaystyle=\frac{\sum_{k=1}^{K}{\mathbb{E}}\left[\int_{D^{[k]}}^{D^{[k]}+\Gamma}\texttt{mse}_{\text{RR}}^{[k]}\left(t,\tilde{S}^{[k]}\right)dt\right]}{\mathbb{E}\left[\Gamma\right]}$
(103)
$\displaystyle=\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-\frac{1}{2\theta_{k}}\cdot\frac{{\mathbb{E}}\left[e^{-2\theta_{k}Y}\right]}{{\mathbb{E}}[\Gamma(K,\epsilon,w)]}\left(1-{\mathbb{E}}\left[e^{-2\theta_{k}\Gamma(K,\epsilon,w)}\right]\right)\right)$
(104)
$\displaystyle=\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(1-\frac{1}{2\theta_{k}}\cdot\frac{\mu}{\mu+2\theta_{k}}\cdot\frac{1-\epsilon}{\tilde{H}(\tau)+\frac{K}{\mu}}\cdot\left(1-\tilde{F}_{k}(\tau)\right)\right)$
(105)

Hence, the optimal solution the auxiliary problem, $\tilde{p}(\beta^{*})=0$,
is given by solving

$\displaystyle\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(\frac{\tilde{H}(\tau)+\frac{K}{\mu}}{1-\epsilon}-\frac{1}{2\theta_{k}}\cdot\frac{\mu}{\mu+2\theta_{k}}\cdot\left(1-\tilde{F}_{k}(\tau)\right)\right)-\beta^{*}\left(\frac{\tilde{H}(\tau)+\frac{K}{\mu}}{1-\epsilon}\right)=0$
(106)

as stated in the theorem.

Focusing on the sampling frequency constraint, one can rewrite it as

$\displaystyle\tilde{H}(\tau)\geq\frac{K}{f_{\max}}-\frac{K}{\mu}.$ (107)

Hence, similar to the proof of Theorem 1, if the sampling constraint is non-
binding, i.e., if
$\tilde{H}(\tilde{G}_{\bm{\theta},\bm{\sigma}^{2},\epsilon}^{-1}(\beta))>\frac{K}{f_{\max}}-\frac{K}{\mu}$,
the unconstrained solution of the threshold is optimal. Otherwise, we satisfy
the constraint with equality, i.e., we set

$\displaystyle\tau_{\text{RR}}^{*}=\tilde{H}^{-1}\left(\frac{K}{f_{\max}}-\frac{K}{\mu}\right).$
(108)

Combining the above two cases gives (73), and completes the proof.
$\blacksquare$

###### Remark 6

Different from Theorem 1, the function
$\tilde{G}_{\bm{\sigma},\bm{\theta},\epsilon}$ is not necessarily increasing
in $\epsilon$ as the numerator and denominator are both monotonically
decreasing functions in $\epsilon$. Consequently, the optimal threshold in the
absence of an erasure status feedback cannot be always increasing in
$\epsilon$ as in Theorem 1. In fact, our numerical evaluation of the optimal
threshold in the absence erasure status feedback shows that the optimal
threshold is indeed decreasing as the erasure probability $\epsilon$
increases. This is intuitive as the transmitter, in this case, has no
knowledge about the current age of the processes’ at the receiver other than
it is on average increasing in $\epsilon$. Consequently, waiting less is more
conservative and leads to a reduction in the overall long-term average of the
sum MSE.

In Algorithm 1, we illustrate how to evaluate the optimal policy in Theorem 2
using a _nested bisection_ method. Specifically, we run an outer bisection
search over the sum MSE value, $\beta$, and an inner bisection search over the
threshold value, $\tau$. For the inner bisection, we efficiently evaluate the
inverse function $\tilde{G}^{-1}(\cdot)$ or $\tilde{H}^{-1}(\cdot)$, while the
outer bisection solves for the unique solution of the auxiliary problem
$\tilde{p}(\beta)=0$.

###### Remark 7

Algorithm 1 can be used to evaluate Theorem 1 as well after replacing
$\tilde{G}(\cdot)$ by $G(\cdot)$, $\tilde{H}(\cdot)$ by $H(\cdot)$,
$\tilde{F}(\cdot)$ by $F(\cdot)$, $\tilde{p}(\cdot)$ by $p(\cdot)$, and the
condition for satisfying the sampling frequency constraint from
$\tilde{H}(\tau_{0})<\frac{K}{f_{\max}}-\frac{K}{\mu}$ to
$H(\tau_{0})<\frac{1}{1-\epsilon}\left(\frac{K}{f_{\max}}-\frac{K}{\mu}\right)$.

Algorithm 1 Nested Bisection Search for Evaluating the Optimal Policy in
Theorem 2

$K$, $\bm{\sigma}$, $\bm{\theta}$ $f_{\max}$, $\mu$, $\epsilon$, $\delta$,
$\tau_{\max}$

$\beta_{\ell}\leftarrow 0$, and
$\beta_{h}\leftarrow\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}$

while $\beta_{h}-\beta_{\ell}>\delta$ do$\triangleright$ Outer bisection over
the sum MSE value

$\beta\leftarrow\frac{\beta_{h}+\beta_{\ell}}{2}$

$\tau_{\ell}\leftarrow 0$, and $\tau_{h}\leftarrow\tau_{\max}$

while $\tau_{h}-\tau_{\ell}>\delta$ do$\triangleright$ Inner bisection over
the unconstrained threshold

$\tau\leftarrow\frac{\tau_{h}+\tau_{\ell}}{2}$

$\mathcal{O}_{\tau}\leftarrow\tilde{G}(\tau)-\beta$

if $\mathcal{O}_{\tau}>0$ then

$\tau_{h}\leftarrow\tau$

else

$\tau_{\ell}\leftarrow\tau$

end if

end whilereturn $\tau_{0}\leftarrow\tau$$\triangleright$ Unconstrained
solution of the threshold

if $\tilde{H}(\tau_{0})<\frac{K}{f_{\max}}-\frac{K}{\mu}$ then
$\triangleright$ Checking the sampling frequency constraint

$\tau_{\ell}\leftarrow\tau_{0}$, and $\tau_{h}\leftarrow\tau_{\max}$

while $\tau_{h}-\tau_{\ell}>\delta$ do$\triangleright$ Inner bisection over
the constrained threshold

$\tau\leftarrow\frac{\tau_{h}+\tau_{\ell}}{2}$

$\mathcal{O}_{\tau}\leftarrow\tilde{H}(\tau)-\left(\frac{K}{f_{\max}}-\frac{K}{\mu}\right)$

if $\mathcal{O}_{\tau}>0$ then

$\tau_{h}\leftarrow\tau$

else

$\tau_{\ell}\leftarrow\tau$

end if

end while

else

$\tau\leftarrow\tau_{0}$

end ifreturn $\tau^{*}=\tau$
$\mathcal{O}_{\beta}\leftarrow\tilde{p}(\beta)=\sum_{k=1}^{K}\frac{\sigma_{k}^{2}}{2\theta_{k}}\left(\frac{\tilde{H}(\tau)+\frac{K}{\mu}}{1-\epsilon}-\frac{1}{2\theta_{k}}\cdot\frac{\mu}{\mu+2\theta_{k}}\cdot\left(1-\tilde{F}_{k}(\tau)\right)\right)-\beta\left(\frac{\tilde{H}(\tau)+\frac{K}{\mu}}{1-\epsilon}\right)$

if $\mathcal{O}_{\beta}>0$ then

$\beta_{h}\leftarrow\beta$

else

$\beta_{\ell}\leftarrow\beta$

end if

end whilereturn $\beta^{*}=\beta$

##  6 Numerical Results: Optimal Threshold Behavior

In this section, we present our numerical results concerning Theorem 1 and
Theorem 2. We study the effects of the erasure probability, the number of
users, and the speed of the processes on the optimal waiting threshold and the
MMSE with and without erasure status feedback.

###  6.1 Effect of Erasure Probability

(a) erasure status feedback is present.

(b) erasure status feedback is absent.

Figure 6: The optimal threshold ($\tau^{*}_{\text{MAF}}$ (right) and
$\tau^{*}_{\text{RR}}$ (left)) versus the erasure probability ($\epsilon$) for
different sampling frequency constraints ($f_{\max}$).

We study a 2-process system with $\bm{\theta}=[0.1\quad 0.5]$, and
$\bm{\sigma}=[1\quad 2]$. The exponential service rate is $\mu=1$. In case of
the presence/absence of the erasure status feedback, we study how the optimal
threshold $\tau^{*}_{\text{MAF}}/\tau^{*}_{\text{RR}}$ behaves versus the
erasure probability $\epsilon$ for $f_{\max}=0.5$, $0.95$, and $1.5$.

First, we consider the case with erasure status feedback in Fig. 6(a). Our
results show that for all sampling frequency constraints, the optimal
threshold increases as the erasure probability increases. This is due to the
fact that the functions $G_{\bm{\theta},\bm{\sigma}}^{-1}(\cdot)$ and
$H^{-1}(\cdot)$ are increasing functions in their argument, which are, in
turn, increasing functions of $\epsilon$ (see Remark 5). Nevertheless, we have
three different cases. First, when $f_{\max}=0.5$, the sampling frequency
constraint is binding even at $\epsilon=0$. Hence, the optimal threshold is
given by

$\displaystyle
H^{-1}\left(\frac{1}{1-\epsilon}\left[\frac{K}{f_{\max}}-\frac{K}{\mu}\right]\right)=H^{-1}\left(\frac{2}{1-\epsilon}\right).$
(109)

We see that the optimal threshold is higher than the other two cases and has a
much steeper curve versus $\epsilon$. On the other hand, when $f_{\max}=1.5$,
the sampling frequency constraint is inactive since $f_{\max}>\mu$, and the
optimal threshold is given by $G^{-1}_{\bm{\theta},\bm{\sigma}}(\beta^{*})$
for all $\epsilon$. Finally, for the case when $f_{\max}=0.95$, we observe an
interesting behavior: when $\epsilon<\epsilon^{*}=0.7$, the threshold
corresponding to $G^{-1}_{\bm{\theta},\bm{\sigma}}(\beta^{*})$ is (slightly)
higher than the threshold corresponding to
$H^{-1}\left(\frac{1}{1-\epsilon}\left[\frac{K}{f_{\max}}-\frac{K}{\mu}\right]\right)$
(which is shown as a dotted curve in Fig. 6(a)); while for
$\epsilon>\epsilon^{*}=0.7$, the sampling frequency constraint becomes binding
and therefore, the optimal threshold is characterized by $H^{-1}(\cdot)$ and
becomes steeper.

Figure 7: Comparison between the optimal threshold behavior versus erasure
probability in both cases of the presence/absence of erasure status feedback
with $f_{\max}=1.5$.

In Fig. 6(b), we consider the case without erasure status feedback. Our
results show that the optimal threshold exhibits the _opposite behavior_
compared to the case with feedback (see Remark 6). Specifically, when the
sampling frequency constraint is never binding, i.e., in the case of
$f_{\max}=1.5>\mu=1$, the optimal threshold $\tau^{*}_{RR}$ is decreasing as
the erasure probability increases. Furthermore, when $\epsilon>0.6$, the
transmitter employs a zero-wait policy and sends its samples immediately after
acquiring them, since $\tau_{RR}^{*}=0$ in this case. Second, we note that the
optimal threshold in the case of $f_{\max}=0.5$ is constant irrespective of
the erasure probability. This is due to the fact that the waiting time needed
to satisfy the sampling constraint is _independent_ of $\epsilon$ in the case
of absent erasure status feedback as the waiting appears at the beginning of
each transmission round regardless of the erasure events. Finally, we see that
for $f_{\max}=0.95$, the optimal threshold is decreasing (following the
unconstrained solution of the problem) until it saturates at $\tau_{RR}^{*}=1$
starting from $\epsilon=0.2$ to satisfy the sampling frequency constraint.

In Fig. 7, we show the optimal threshold for both cases of erasure status
feedback availability at $f_{\max}=1.5$ (non-binding sampling frequency
constraint) on the same figure. Fig. 7 shows that both thresholds begin from
the same value at $\epsilon=0$. This is due to the fact that both settings are
equivalent when there are no erasure events. The optimal thresholds then part
their way as the erasure probability increases and behave oppositely as stated
above.

In Fig. 8, we show the resultant sum MSE versus the erasure probability for
both cases of erasure status feedback availability at $f_{\max}=1.5$ (non-
binding sampling frequency constraint) on the same figure. We compare the
resultant MSE values with their counterparts if the zero-wait policy is
employed. Fig. 8 shows that the sum MSE in the presence of erasure status
feedback is smaller than that in the absence of erasure status feedback.
Furthermore, the sum MSE with optimal waiting for both cases outperforms the
zero-wait policy, as expected. In the case of no erasure status feedback, the
sum MSE with optimal waiting converges to its counterpart with zero-waiting
policy, as the optimal threshold converges to zero as $\epsilon$ increases.
Surprisingly, Fig. 8 shows that for small erasure probability (up to $\approx
0.07$), employing _optimal waiting with RR scheduling_ outperforms _zero-
waiting with MAF scheduling_.

Figure 8: Comparison between the sum MSE with optimal waiting (in solid lines)
versus the erasure probability in both cases of the presence/absence of
erasure status feedback with $f_{\max}=1.5$. For each case, we compare the
resultant sum MSE with its counterpart if the zero-wait policy is employed (in
dotted lines).

###  6.2 Effect of the Number of Processes

(a) erasure status feedback is present.

(b) erasure status feedback is absent.

Figure 9: The optimal threshold ($\tau^{*}_{\text{MAF}}$ (right) and
$\tau^{*}_{\text{RR}}$ (left)) versus the number of processes ($K$) for
different sampling frequency constraints ($f_{\max}$).

We now consider a symmetric system with $K$ processes, each having
$\sigma_{k}^{2}=1$ and $\theta_{k}=0.5$, for all $k$, communicating through a
channel with $\epsilon=0.3$. In Fig. 9(a), We study the optimal threshold
variation with increasing the number of processes $K$ in the presence of
erasure status feedback. We observe that the long-term average sum MMSE
increases with $K$ (as expected, since more processes need to be conveyed
through a shared channel). Fig. 9(a) shows that as $K$ increases, the optimal
threshold increases as well. The slope of the curve depends on $f_{\max}$.
When $f_{\max}=0.5$, the sampling frequency constraint is binding, and
$\tau^{*}$ appears to linearly increase with $K$ with a steeper slope. When
$f_{\max}=1.5>\mu=1$, i.e., for an unconstrained version of the problem, the
optimal threshold is slowly increasing with $K$. For $f_{\max}=0.95$, the
optimal threshold matches the unconstrained solution for $K=1,2$.
Nevertheless, when $K>2$, the sampling frequency constraint becomes binding
and the linear-like profile of the optimal threshold prevails.

The exact general patterns hold for the case of the absence of erasure status
feedback in Fig. 9(b). We note, however, that the slopes of curves in Fig.
9(a) are relatively higher than their counterparts in Fig. 9(b). This is
consistent with the results of the previous subsection, where larger waiting
(at the same erasure probability) is employed if erasure feedback is present.

Finally, we study how the optimal threshold without feedback,
$\tau^{*}_{\text{RR}}$ behaves with $K$ over a set of different values of
$\epsilon$. Interestingly, despite the general increasing trend of the
$\tau^{*}_{\text{RR}}$ versus the number of processes $K$ for fixed
$\epsilon$, it is at the same time monotonically decreasing in $\epsilon$ for
fixed $K$. This is illustrated in Fig. 10. This implies that there exist a
specific number of processes $\underline{K}$, after which the transmitter
starts to wait before each transmission round. This is a contrasting behavior
comapred to the case of having erasure status feedback, in which increasing
$\epsilon$ always increases the $\tau^{*}_{\text{MAF}}$ for any number of
processes.

Figure 10: The optimal threshold ($\tau^{*}_{\text{RR}}$) versus the number of
processes ($K$) for different values of the erasure probability ($\epsilon$)
in the absence of erasure status feedback.

###  6.3 Effect of the Variation Speed of the Processes

(a) erasure status feedback is present.

(b) erasure status feedback is absent.

Figure 11: The optimal threshold ($\tau^{*}_{\text{MAF}}$ (left) and
$\tau^{*}_{\text{RR}}$ (right)) and the optimal long-term average MMSE versus
$\theta_{2}$ for tracking two processes with different sampling frequency
constraints ($f_{\max}$); the first process has fixed parameters
$\sigma_{1}^{2}=1$ and $\theta_{1}=1$.

We consider a 2-process system with $\sigma_{1}^{2}=2$, $\sigma_{2}^{2}=1$,
and $\theta_{1}=0.5$. We vary $\theta_{2}\in[0.1,1]$ and observe its effect on
the optimal threshold and the MMSE for the same service rate $\mu=1$.

In Fig. 11(a), in the case of available erasure status update, we observe that
when the sampling frequency constraint is binding, e.g., when $f_{\max}=0.5$,
the optimal threshold is independent of $\theta_{2}$ as the argument of
$H^{-1}(\cdot)$ is independent of $\theta_{2}$. The optimal threshold,
however, is a monotonically decreasing function in $\theta_{2}$ for
$f_{\max}=1.5$ as the process becomes faster, and thus the system needs to
wait less to track the variations in the process as long as the sampling
constraint is inactive. In both cases, the long-term average MMSE is
decreasing in $\theta_{2}$ since the sum of the processes’ variances
decreases.

Similar observations can be drawn for the case of the absence of erasure
status feedback in Fig. 11(b). Different from Fig. 11(a), it appears that the
optimal threshold is changing slightly with respect to $\theta_{2}$ even for
the unconstrained problem (under the considered system parameters).
Furthermore, as expected, we can observe that the MMSE function (versus
$\theta_{2}$) for the case of no erasure status feedback is higher than its
counterpart if the erasure status feedback is available.

##  7 Conclusion

In this paper, we investigated the problem of estimating $K$ independent OU
processes under a total sampling constraint $f_{\max}$, with the goal of
identifying the optimal sampling instants such that the long-term average sum
MSE is minimized. The acquired samples experience independent erasure events
with an erasure probability $\epsilon$. We focused on characterizing the
optimal sampling policy in two cases: first, when erasure status feedback is
available at the transmitter. In this case, we assume that the transmitter
acquires the samples according to the MAF scheduling policy. In the second
case, the erasure status feedback is non-existent at the transmitter, and the
transmitter employs an RR scheduling policy. We re-formulated both problems in
terms of optimizing a stationary waiting policy. In the case of available
erasure status feedback, we demonstrated that aggregating waiting at the
beginning of the epoch does not hurt the long-term average MSE. In the case of
absent erasure status feedback, however, this aggregation needs to be done at
the beginning of each RR transmission round. We showed that the optimal
waiting policy is indeed a threshold policy in both settings. We characterized
the optimal threshold in terms of $K$, $f_{\max}$, and $\epsilon$.

Our numerical evaluations and our structural results show an intriguing
behavior of the optimal threshold. While, the optimal threshold $\tau^{*}$ at
$\epsilon=0$ is identical for both settings, with increasing $\epsilon$, the
optimal threshold for both settings part ways: it _increases_ for the case of
_available_ erasure status feedback, and _decreases_ when the erasure status
feedback is _non-existent_. Furthermore, we show that for both settings, the
optimal threshold is an increasing function of the number of processes $K$.
Finally, we show the effect of the variation speed of the process on the long-
term average sum MSE.

Future directions of this work may include investigating fully-observable
processes (OU or otherwise), different age-dependent penalties other than the
sum MSE penalty, the behavior of the waiting policy for generalized
statistical models for the service queue other than the exponential
distribution, exogenous sampling with and without preemption rather than the
generate-at-will model, and signal-dependent sampling rather than signal-
independent sampling.

## References

  * [1] R. D. Yates, Y. Sun, D. R. Brown III, S. K. Kaul, E. Modiano, and S. Ulukus.  Age of information: An introduction and survey.  IEEE J. Sel. Areas Commun., 39(5):1183–1210, May 2021.
  * [2] S. K. Kaul, R. D. Yates, and M. Gruteser.  Real-time status: How often should one update?  In Proc. IEEE Infocom, March 2012.
  * [3] C. Kam, S. Kompella, and A. Ephremides.  Age of information under random updates.  In Proc. IEEE ISIT, July 2013.
  * [4] M. Costa, M. Codreanu, and A. Ephremides.  On the age of information in status update systems with packet management.  IEEE Trans. Inf. Theory, 62(4):1897–1910, April 2016.
  * [5] A. Kosta, N. Pappas, A. Ephremides, and V. Angelakis.  Age and value of information: Non-linear age case.  In Proc. IEEE ISIT, June 2017.
  * [6] R. D. Yates and S. K. Kaul.  The age of information: Real-time status updating by multiple sources.  IEEE Trans. Inf. Theory, 65(3):1807–1827, March 2019.
  * [7] R. Talak and E. Modiano.  Age-delay tradeoffs in single server systems.  In Proc. IEEE ISIT, July 2019.
  * [8] Y. Inoue, H. Masuyama, T. Takine, and T. Tanaka.  A general formula for the stationary distribution of the age of information and its application to single-server queues.  IEEE Trans. Inf. Theory, 65(12):8305–8324, December 2019.
  * [9] A. Soysal and S. Ulukus.  Age of information in G/G/1/1 systems: Age expressions, bounds, special cases, and optimization.  Available Online: arXiv:1905.13743.
  * [10] P. Zou, O. Ozel, and S. Subramaniam.  Waiting before serving: A companion to packet management in status update systems.  IEEE Trans. Inf. Theory.  To appear.
  * [11] Y. Hsu, E. Modiano, and L. Duan.  Age of information: Design and analysis of optimal scheduling algorithms.  In Proc. IEEE ISIT, June 2017.
  * [12] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff.  Update or wait: How to keep your data fresh.  IEEE Trans. Inf. Theory, 63(11):7492–7508, November 2017.
  * [13] B. Zhou and W. Saad.  Optimal sampling and updating for minimizing age of information in the internet of things.  In Proc. IEEE Globecom, December 2018.
  * [14] Y. Sun and B. Cyr.  Sampling for data freshness optimization: Non-linear age functions.  J. Commun. Netw., 21(3):204–219, June 2019.
  * [15] H. Tang, J. Wang, L. Song, and J. Song.  Minimizing age of information with power constraints: Opportunistic scheduling in multi-state time-varying networks.  Available Online: arXiv: 1912.05947.
  * [16] R. D. Yates.  Lazy is timely: Status updates by an energy harvesting source.  In Proc. IEEE ISIT, June 2015.
  * [17] X. Wu, J. Yang, and J. Wu.  Optimal status update for age of information minimization with an energy harvesting source.  IEEE Trans. Green Commun. Netw., 2(1):193–204, March 2018.
  * [18] A. Baknina, O. Ozel, J. Yang, S. Ulukus, and A. Yener.  Sending information through status updates.  In Proc. IEEE ISIT, June 2018.
  * [19] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor.  Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies.  IEEE Trans. Inf. Theory, 66(1):534–556, January 2020.
  * [20] B. T. Bacinoglu, Y. Sun, E. Uysal-Biyikoglu, and V. Mutlu.  Optimal status updating with a finite-battery energy harvesting source.  J. Commun. Netw., 21(3):280–294, June 2019.
  * [21] S. Leng and A. Yener.  Age of information minimization for an energy harvesting cognitive radio.  IEEE Trans. Cogn. Commun. Netw., 5(2):427–439, June 2019.
  * [22] B. Buyukates, A. Soysal, and S. Ulukus.  Age of information in multihop multicast networks.  J. Commun. Netw., 21(3):256–267, June 2019.
  * [23] A. M. Bedewy, Y. Sun, and N. B. Shroff.  The age of information in multihop networks.  IEEE/ACM Trans. Netw., 27(3):1248–1257, June 2019.
  * [24] P. Mayekar, P. Parag, and H. Tyagi.  Optimal lossless source codes for timely updates.  In Proc. IEEE ISIT, June 2018.
  * [25] M. Zhang, A. Arafa, J. Huang, and H. V. Poor.  How to price fresh data.  In Proc. WiOpt, June 2019.
  * [26] A. Arafa, R. D. Yates, and H. V. Poor.  Timely cloud computing: Preemption and waiting.  In Proc. Allerton, October 2019.
  * [27] H. H. Yang, A. Arafa, T. Q. S. Quek, and H. V. Poor.  Age-based scheduling policy for federated learning in mobile edge networks.  Available Online: arXiv:1910.14648.
  * [28] M. Klugel, M. H. Mamduhi, S. Hirche, and W. Kellerer.  AoI-penalty minimization for networked control systems with packet loss.  In Proc. IEEE Infocom, April 2019.
  * [29] A. Mitra, J. A. Richards, S. Bagchi, and S. Sundaram.  Finite-time distributed state estimation over time-varying graphs: Exploiting the age-of-information.  In Proc. ACC, July 2019.
  * [30] J. Chakravorty and A. Mahajan.  Remote estimation over a packet-drop channel with Markovian state.  IEEE Trans. Autom. Control, 65(5):2016–2031, May 2020.
  * [31] O. Ayan, M. Vilgelm, M. Klugel, S. Hirche, and W. Kellerer.  Age-of-information vs. value-of-information scheduling for cellular networked control systems.  In Proc. IEEE ICCPS, April 2019.
  * [32] S. Roth, A. Arafa, H. V. Poor, and A. Sezgin.  Remote short blocklength process monitoring: Trade-off between resolution and data freshness.  In Proc. IEEE ICC, June 2020.
  * [33] D. Ramirez, E. Erkip, and H. V. Poor.  Age of information with finite horizon and partial updates.  Available Online: arXiv:1910.00963.
  * [34] M. Bastopcu and S. Ulukus.  Age of information for updates with distortion: Constant and age-dependent distortion constraints.  Available Online: arXiv:1912.13493.
  * [35] M. Bastopcu and S. Ulukus.  Partial updates: Losing information for freshness.  Available Online: arXiv:2001.11014.
  * [36] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides.  The age of incorrect information: A new performance metric for status updates.  Available Online: arXiv:1907.06604.
  * [37] Y. Sun, Y. Polyanskiy, and E. Uysal-Biyikoglu.  Remote estimation of the Wiener process over a channel with random delay.  IEEE Trans. Inf. Theory, 66(2):1118–1135, February 2020.
  * [38] T. Ornee and Y. Sun.  Sampling and remote estimation for the ornstein-uhlenbeck process through queues: Age of information and beyond.  IEEE/ACM Transactions on Networking, 29(5):1962–1975, 2021.
  * [39] A. Arafa, K. Banawan, K. G. Seddik, and H. V. Poor.  Sample, quantize, and encode: Timely estimation over noisy channels.  IEEE Trans. Commun., 69(10):6485–6499, October 2021.
  * [40] N. Guo and V. Kostina.  Optimal causal rate-constrained sampling for a class of continuous Markov processes.  IEEE Trans. Inf. Theory, 67(12):7876–7890, December 2021.
  * [41] G. E. Uhlenback and L. S. Ornstein.  On the theory of the Brownian motion.  Phys. Rev., 36:823–841, September 1930.
  * [42] J. L. Doob.  The Brownian movement and stochastic equations.  Ann. Math., 43(2):351–369, 1942.
  * [43] W. Dinkelbach.  On nonlinear fractional programming.  Management Science, 13(7):492–498, 1967.
  * [44] S. P. Boyd and L. Vandenberghe.  Convex Optimization.  Cambridge University Press, 2004.