# Status Update Control and Analysis under Two-Way Delay

Mohammad Moltafet, Markus Leinonen, Marian Codreanu, and Roy D. Yates Mohammad
Moltafet is with the Department of Electrical and Computer Engineering,
University of California Santa Cruz (UCSC), Santa Cruz, CA 95064, USA (e-mail:
mmoltafe@ucsc.edu), Markus Leinonen, deceased, was with Centre for Wireless
Communications–Radio Technologies, University of Oulu, Oulu, Finland, Marian
Codreanu is with the Department of Science and Technology, Linköping
University, Linköping 58183, Sweden (e-mail: marian.codreanu@liu.se), and Roy
D. Yates is with the Wireless Information Network Laboratory, ECE Department,
Rutgers University, North Brunswick, New Jersey 08902, USA (e-mail:
ryates@winlab.rutgers.edu).

###### Abstract

We study status updating under two-way delay in a system consisting of a
sampler, a sink, and a controller residing at the sink. The controller drives
the sampling process by sending request packets to the sampler. Upon receiving
a request, the sampler generates a sample and transmits the status update
packet to the sink. Transmissions of both request and status update packets
encounter random delays. We develop optimal control policies to minimize the
average age of information (AoI) using the tools of Markov decision processes
in two scenarios. We begin with the system having at most one active request,
i.e., a generated request for which the sink has not yet received a status
update packet. Then, as the main distinctive feature of this paper, we
initiate pipelined-type status updating by studying a system having at most
two active requests. Furthermore, we conduct AoI analysis by deriving the
average AoI expressions for the Zero-Wait-1, Zero-Wait-2, and Wait-1 policies.
According to the Zero-Wait-1 policy, whenever a status update packet is
delivered to the sink, a new request packet is inserted into the system. The
Zero-Wait-2 policy operates similarly, except that the system can hold two
active requests. According to the Wait-1 policy, whenever a status update
packet is delivered to the sink, a new request is sent after a waiting time
which is a function of the current AoI. Numerical results illustrate the
performance of each status updating policy under varying system parameter
values.

_Index Terms–_ AoI, two-way delay, status updating control, Markov decision
process.

##  I Introduction

A key enabler for emerging time-critical applications (e.g., industrial
automation or drone control) in wireless sensor networks (WSNs) and Internet
of things (IoT) is the timely delivery of status updates of real-world
physical processes. The age of information (AoI) is a relatively new
destination-centric metric for the information freshness in status update
systems [1, 2, 3]. A status update packet contains a measured value of a
monitored process and a time stamp for when the sample was generated. For each
source node, the AoI at a destination measures the difference between the
current time and the time stamp of the most recent received status update [1,
4].

In this paper, we study status updating under two-way delay in the discrete-
time system depicted in Figure 1. A sampler monitors a random process and
sends updates through a “forward link” service facility to a sink/monitor. At
the sink, a controller drives the sampling process by sending request packets
to the sampler on a “reverse link” control channel.

This system is subject to two-way delays in that packets on both forward and
reverse links experience random delays. In particular, each request packet on
the reverse link requires a random time to be delivered to the sampler. Upon
receiving a request, the sampler immediately generates a sample and initiates
the transmission of the corresponding status update packet which requires a
random time to arrive at the sink. This model arises in many applications,
where the monitor (sink) is responsible for controlling the sampling process
of a remote source (e.g., a wireless sensor); accordingly, the monitor sends
sampling control messages (i.e., packets) over the wireless links, which
arrive at the source after a random delay. Such delayed control messaging is
not present in the majority of the existing literature on AoI analysis and
control; the few exceptions are elaborated in Section II.

###  I-A Contributions

The delayed control channel opens up a framework to study status updating
under pipelining-type packet flow, where multiple requests are concurrently
being processed in the system. In this setting, we define an active request as
a request that the controller has created, but for which the sink has not yet
received the corresponding status update packet. As the main contribution, we
take a step towards improving the timeliness of status updates in pipelining-
based status update systems as follows. We initially consider a system with at
most one active request, thus operating in a stop-and-wait fashion. Then,
initiating pipelining-type status updating, we consider a system that supports
two active requests. As this system leads to queued packets when a server is
busy, waiting buffers are introduced at both forward and reverse links.

The first part of this paper deals with AoI-optimal status updating control in
the two scenarios regarding the number of active requests. Assuming that the
controller has global knowledge of the system state (i.e., the existence of
packets at the waiting buffers and servers and their age values), our
objective is to find the optimal times to send request messages, i.e., the
optimal control policy, that minimize the average AoI. For each scenario, we
formulate a Markov decision process (MDP) problem that we subsequently solve
via the relative value iteration (RVI) algorithm.

The second part of this paper focuses on AoI analysis. Since, in practice, the
global system state is oftentimes not available at the controller, we analyze
the performance of two control policies that operate solely based on the
controller’s local information: 1) the zero-wait policy with one active
request (Zero-Wait-1 policy), and 2) the zero-wait policy with two active
requests (Zero-Wait-2 policy). According to the Zero-Wait-1 policy, whenever a
status update packet is delivered to the sink, a new request packet is
immediately inserted into the system. The Zero-Wait-2 policy operates
similarly; except the system always maintains two active requests. We derive
the closed-form expression of the average AoI under the Zero-Wait-1 and Zero-
Wait-2 policies.

Furthermore, driven by the fact that the zero-wait discipline is not
necessarily age-optimal [5, 6], we modify the Zero-Wait-1 policy by
introducing a waiting time in the controller’s update request process. Under
this Wait-1 policy, whenever a status update packet is delivered to the sink,
a new request is sent after a waiting time which is a function of the current
AoI. We derive the closed-form expression of the average AoI under the Wait-1
policy.

Finally, numerical results are presented to show the performance of each
status updating policy under different system parameter values. Moreover, the
threshold-type structure of an optimal status updating policy is illustrated.

###  I-B Organization

The paper is organized as follows. Related work is discussed in Section II.
The system model and AoI performance metric are presented in Section III.
Optimal control policies to minimize the average AoI are presented in Section
IV. Average AoI analysis for Zero-Wait-1, Zero-Wait-2, and Wait-1 policies is
provided in Section V. Numerical results are presented in Section VI. Finally,
concluding remarks are made in Section VII.

##  II Related Work

Analysis of AoI in various status update systems has witnessed great interest.
The first analytical results were derived in [4], where the authors
characterized the average AoI for M/M/1, D/M/1, and M/D/1 first-come first-
served queueing models. In [7], the authors proposed the peak AoI as an
alternative metric for information freshness. Since then, average AoI and peak
AoI have extensively been studied in various queueing models. The average
(peak) AoI for various queueing models with exponentially distributed service
time and Poisson arrivals has been studied in, e.g., [8, 9, 7, 10, 11, 12].
Besides exponentially distributed service time and Poisson arrivals, AoI has
also been studied under various arrival processes and service time
distributions in, e.g., [13, 14, 15, 16, 17, 10, 18, 19, 20]. Using the
framework of stochastic hybrid systems [21], the average AoI and moment
generating functions of the AoI have been characterized under various queueing
models and packet management policies in, e.g., [22, 23, 24, 25, 26, 27, 28,
29, 30, 31, 32, 33, 34, 35]. AoI has also been studied in various discrete-
time queueing systems [36, 37, 38, 39, 40].

Besides the age analysis, numerous works have focused on devising AoI-optimal
status updating control procedures. Indeed, the optimization of, e.g., the
sampling times of the sensors, scheduling, and resource management plays a
critical role in the performance of status update systems. The works [41, 42,
43, 44, 45, 46, 47, 48, 49, 50, 6, 51, 52, 53, 54, 55, 56, 57, 58]
investigated the optimal sampling problem in status update systems, whereas
the works [5, 59, 60, 61, 62, 63, 64, 65] studied the optimal sampling problem
with energy harvesting sources. A comprehensive literature review of recent
works in AoI can be found in [3].

An efficient status update system optimally balances between too infrequent
updates and excessively frequent updates that induce queueing delays. To this
end, an intuitive approach is to send new updates as the system becomes empty.
However, the work [5] established a new notion for optimal status update
control by showing that a lower average AoI value may be achieved by purposely
asking the sensor to wait before taking and transmitting a fresh sample. The
work [6] generalized the idea in [5] and studied optimal sampling with respect
to different age penalty functions, where a source communicates over a Markov
channel (imposing correlated packet transmission times) subject to a sampling
rate constraint. The work [48] proposed a new mutual-information-based metric
to quantify information freshness and subsequently studied a sampling problem,
where a Markov source sends updates through a queue to the sink. The authors
proved that the optimal sampling policy is a threshold policy and found the
optimal threshold. The work [49] further extended the study of the sampling
problem in [6] by considering more general non-linear functions of AoI and
investigating both continuous-time and discrete-time systems.

In [58], the authors considered a status update system consisting of an
information source, a server, and multiple users. The server communicates with
the information source to update its data, whereas users submit requests to
the server to retrieve the updated data. The main goal of the server is to
provide users with fresh information about the information source. However,
maintaining fresh data at the server requires the server to update its
database frequently, which incurs an update cost. They studied the tradeoff
between the AoI and the update cost at the server. The work [59] considered an
energy harvesting sensor and derived the optimal threshold, in terms of the
current energy state and estimated age, to trigger a new sample to minimize
the average AoI. Therein too, the threshold policy conforms to the idea of
intentionally waiting prior to sampling, as in [5].

Extending beyond mere sampling, status update control has also been studied in
more general network optimization frameworks. The authors of [66, 50]
considered a multi-source status update system in which the different sources
send their updates through a shared channel causing random delays. They
studied joint sampling and transmission scheduling for optimizing the
information freshness. The authors of [51] considered two source nodes
generating heterogeneous traffic with different power supplies and studied the
peak-age-optimal status update scheduling. In [60], the authors considered an
energy harvesting source sending status updates over a noisy channel and
derived the optimal status updating policy to minimize the average AoI. In
[52], the authors studied transmission scheduling of status updates over an
error-prone communication channel via automatic repeat request (ARQ) protocols
to minimize the average AoI subject to the constraint on the average number of
transmissions. The work [53] studied the problem of optimal scheduling and
radio resource allocation in a WSN to minimize the average total transmit
power subject to an average AoI constraint. The work in [54] studied the AoI-
optimal sampling and scheduling in a relay-based multi-source status update
system under an average number of transmissions constraint. None of the
aforementioned works, however, considers a delayed control channel.

The most closely related works to this paper are [55, 56, 57]; these
contributions all incorporate a delayed feedback/ACK channel in a status
update system. The work in [55] considered a system consisting of a sensor, a
controller, a forward sensor-to-controller channel, and a backward controller-
to-sensor channel. A transmission in both the forward and backward channels
experiences a random delay. A sensor can generate a new packet only after
receiving a confirmation message of the previous packet from the controller,
thus conforming to a stop-and-wait ARQ mechanism. The authors introduced
waiting times (in line with [5, 6]) at both the sensor and controller ends and
derived optimal status updating policies to minimize the average AoI or to
perform remote estimation of a Wiener process.

The works [56] and [57] considered a system where status updates are
transmitted through an unreliable channel and upon delivery of a packet, a
feedback message is sent to the sampler, which experiences a random delay. In
[56], similarly to [55], a stop-and-wait packet flow is assumed, and the
authors derived an optimal sampling policy that minimizes a long-term average
age penalty under a sampling rate constraint. In [57], the authors considered
a controller at the sampler that decides to stay idle or send a fresh update
in each slot according to delayed ACK messages. They studied two scenarios to
derive bounds on the optimal average AoI:  1. in some specific slots, a genie
temporarily takes over the queue in the backward channel and delivers all the
queued ACK messages to the sampler instantaneously, and  2. the system can
contain at most two packets, including both status updates and ACK messages.
They showed that the optimal policy in the first scenario provides a lower
bound on the optimal average AoI of the system and the optimal status update
policy in the second one provides an upper bound on the optimal average AoI of
the system.

In contrast to [55, 56], this paper relaxes the restriction to stop-and-wait
mechanisms. As conjectured in [55, Remark 2] and [56, Footnote 2], this paper
shows that, instead of working in a stop-and-wait fashion, requesting status
updates anticipatively is, in general, beneficial. Indeed, the consideration
of pipelining (in the form of two active requests) in a status update system
under two-way delay is the most distinctive feature of this paper. Also,
different from [55, 56, 57], we consider a strictly obedient sampler such that
once it receives a request message, it is not allowed to wait prior to
sampling. Overall, our analysis is quite different and is conducted for a
discrete-time system, as opposed to the continuous-time systems in [55, 56].
The work in [57] is a parallel work to this paper, but in contrast to [57], we
derive closed-form expressions of the average AoI for three different control
policies.

Figure 1: The considered status update system with two-way delay.

##  III System Model and AoI Definition

###  III-A System Model

We consider a status update system consisting of one sampler and one sink, as
depicted in Fig. 1. We assume slotted communication with normalized slots
${t\in\\{0,1,\dots\\}}$; slot $t$ indicates the time interval $[t,t+1)$. The
sampler monitors a random process and the sink is interested in timely
information about the status of the process.

####  III-A1 Request Messaging

We consider that the sampler can be commanded to take a sample of the process
at will. More precisely, we consider a controller at the sink who sends
request messages (i.e., request packets) to the sampler; once the sampler
receives the request, it takes a sample. We consider that each request packet
requires a random time to be successfully delivered to the sampler. We model
this as a controller server residing at the link from the controller to the
sampler. We assume that the controller server serves request packets according
to a geometrically distributed service time with mean $1/\gamma$. Moreover,
the controller server is associated with a controller buffer that stores
arriving request packets whenever the server is busy.

####  III-A2 Status Updating

If the sampler receives a request packet at the end of slot $t-1$, it
generates a sample at the beginning of slot $t$. The samples are sent to the
sink as status update packets, each containing the measured value of the
monitored process and a time stamp representing the time when the sample was
generated. We consider that each status update packet requires a random time
to arrive at the sink. We model this as a server residing at the link from the
sampler to the sink, henceforth called the sampler server. We assume that the
sampler server serves the packets according to a geometrically distributed
service time with mean $1/\mu$. The sampler server is associated with a
sampler buffer that stores an arriving status update packet if the server is
busy.

####  III-A3 System Capacity

We will study two scenarios regarding the system capacity, i.e., the maximum
number of packets (either request or status update packets) concurrently in
the system. We define an active request as a request that the controller has
created, but for which the sink has not yet received the corresponding status
update packet. In the first scenario, there is at most one active request
concurrently in the system. This corresponds to the typical stop-and-wait
transmission policy, where a new request packet can be inserted only after the
preceding requested status update packet is delivered to the sink. To give
insights to the queueing dynamics, the system holds at most one status update
packet at a time while the buffers are always empty. In the second scenario,
we consider a system with at most two active requests. This takes a step
toward pipelining, where the system is simultaneously processing multiple
packets. This leads to more intricate queueing dynamics: for example, the
system may have two requests or two status update packets so that one packet
is waiting in a buffer.

###  III-B AoI Definition

The AoI at the sink is defined as the time elapsed since the last successfully
received status update packet was generated. Formally, let $t_{i}$ denote the
time slot at which the $i$th request message is generated. This request
message completes service at the controller server at time slot
$t^{\prime}_{i}-1$ and is delivered to the sampler server at time slot
$t^{\prime}_{i}$, which is also the time slot that the $i$th status update
packet is both generated at the sampler and arrives at the sampler server. To
close the round trip passage of update $i$, let $\bar{t}_{i}$ denote the time
slot at which the $i$th status update packet arrives at the sink. At time slot
$\tau$, the index of the most recently received status update packet is

$N(\tau)=\max\\{i\colon\bar{t}_{i}\leq\tau\\},$ (1)

and the time stamp of the most recently received status update packet is
${U^{\tau}=t^{\prime}_{N(\tau)}}$. The (discrete) AoI at the sink is defined
as the random process ${\delta^{t}=t-U^{t}}$. The evolution of the AoI is
given as

$\displaystyle\delta^{t}=\begin{cases}t-t^{\prime}_{N(t)},&\mbox{if}\leavevmode\nobreak\
{t=\bar{t}_{N(t)}}\\\ \delta^{t-1}+1,&\mbox{otherwise.}\end{cases}$ (2)

A sample path of the AoI is exemplified in Fig. 2, which illustrates the
staircase pattern of the AoI evolution.

To evaluate the AoI, we use the most commonly used metric, the average AoI
[67, 3], which is defined in the following. Let $(0,\tau)$ denote an
observation interval. Accordingly, the time average AoI at the sink, denoted
as $\Delta_{\tau}$, is defined as

$\Delta_{\tau}=\dfrac{1}{\tau}\textstyle\sum_{t=1}^{\tau}\delta^{t}.$ (3)

The summation in (3) is equal to the area under $\delta^{t}$, which can be
expressed as a sum of disjoint areas determined by polygons $\underline{Q}$,
${\\{Q_{i}\\}_{i=2}^{N(\tau)}}$, and $\bar{Q}$, as illustrated in Fig. 2.
Following the definition of $N(\tau)$ in (1), $\Delta_{\tau}$ can be
calculated as

$\displaystyle\Delta_{\tau}$
$\displaystyle=\dfrac{1}{\tau}\bigg{(}\underline{Q}+\textstyle\sum_{i=2}^{N(\tau)}Q_{i}+\bar{Q}\bigg{)}$
$\displaystyle=\dfrac{\underline{Q}+\bar{Q}}{\tau}+\dfrac{N(\tau)-1}{\tau}\dfrac{1}{N(\tau)-1}\sum_{i=2}^{N(\tau)}Q_{i}.$
(4)

In our analysis, we use a transition between the discrete AoI process defined
in (2) and the AoI process, which is equivalent to (2) except that the age
increases continually during a slot. To this end, let $Q^{+}_{i}$ denote a
trapezoid associated with $Q_{i}$ so that $Q_{i}$ is inscribed in $Q^{+}_{i}$,
as illustrated in Fig. 2 for $i=2$. The trapezoids $\underline{Q}^{+}$ and
$\bar{Q}^{+}$ are defined similarly. Thus, we can rewrite $\Delta_{\tau}$ in
(III-B) as

$\displaystyle\\!\\!\Delta_{\tau}\\!=\\!\dfrac{\underline{Q}^{+}+\bar{Q}^{+}}{\tau}+\dfrac{N(\tau)-1}{\tau}\dfrac{1}{N(\tau)-1}\textstyle\sum_{i=2}^{N(\tau)}Q^{+}_{i}-\dfrac{1}{2},$
(5)

because by considering $\underline{Q}^{+}$, $\\{Q^{+}_{i}\\}_{i\geq 1}$, and
$\bar{Q}^{+}$, a triangle of area $1/2$ has been added in each slot to the
area under $\delta^{t}$, and thus, we need to subtract the average area of
these triangles, which is $1/2$.

Figure 2: An example of the evolution of the AoI.

Let $T_{i}=\bar{t}_{i}-t^{\prime}_{i}$ denote the system time of status update
packet $i$, defined as the time duration between the generation time at the
sampler and the reception time at the sink. Let
${I_{i}=t^{\prime}_{i}-t^{\prime}_{i-1}}$ denote the interarrival time between
status update packets $i-1$ and $i$ at the sampler server. Since $Q^{+}_{i}$
can be calculated by subtracting the area of the isosceles triangle with sides
$T_{i}$ from the area of the isosceles triangle with sides ${I_{i}+T_{i}}$
(see Fig. 2),

$Q^{+}_{i}=\frac{1}{2}I_{i}^{2}+I_{i}T_{i}.$ (6)

The (time) average AoI, denoted by $\Delta$, is defined as
${\Delta=\lim_{\tau\to\infty}\Delta_{\tau}}$. With the assumption that
$\left\\{(I_{i},T_{i})\right\\}_{i\geq 1}$ is a stationary ergodic random
process,111Such ergodicity assumptions are common in the AoI literature [4,
67]. For the controller policies considered in this work, explicit
verification can be nontrivial but not especially interesting. the limit
$\lambda=\lim_{\tau\to\infty}({N(\tau)-1})/{\tau}$ exists and is given as
$\lambda=1/\mathbb{E}[I_{i}]$ and the sample average
$\frac{1}{N(\tau)-1}\textstyle\sum_{i=2}^{N(\tau)}Q^{+}_{i}$ in (5) converges
to the stochastic average $\mathbb{E}[Q^{+}_{i}]$. Since the term
$({\underline{Q}^{+}+\bar{Q}^{+}})/{\tau}$ in (5) goes to zero as
${\tau\to\infty}$, it then follows from (5) and (6) that the average AoI is

$\displaystyle\Delta$
$\displaystyle=\dfrac{1}{\mathbb{E}[I_{i}]}\mathbb{E}\left[\frac{1}{2}I_{i}^{2}+I_{i}T_{i}\right]-\dfrac{1}{2}.$
(7)

Going forward, we will use the average AoI (7) to compare controller policies.

##  IV Optimal Control for Average AoI Minimization

In this section, we study and design optimal control policies for the
considered status updating system. More precisely, our goal is to determine
the optimal times for the controller to send request messages to minimize the
average AoI at the sink. We split the control design into two cases. In
Section IV-A, we consider the system with at most one active request,
hereinafter referred to as 1-Packet system. In Section IV-B, we consider the
system with at most two active requests, hereinafter referred to as 2-Packet
system.

In this section, we use a common assumption (see e.g., [68, 69, 70, 52]) that
the AoI is upper-bounded by a sufficiently large value $\bar{\Delta}$ so that
$\delta^{t}\in\\{1,2,\ldots,\bar{\Delta}\\}$. This enables tractable design of
optimal control policies by making the state spaces finite, while
acknowledging that when the status information becomes excessively stale by
reaching $\bar{\Delta}$, a time-critical end application would not be affected
if counting further. How $\bar{\Delta}$ is chosen in practice is discussed in
the numerical results of Section VI.

###  IV-A 1-Packet System

In this section, we formulate the optimal status update control problem as a
Markov decision process (MDP) problem and propose a relative value iteration
(RVI) algorithm to find an optimal control policy.

####  IV-A1 State

Let ${s^{t}\in\mathcal{S}}$ denote the state of the system in slot $t$, where
${\mathcal{S}}$ is the state space. We define the system state as
${s^{t}=(\delta^{t},e_{\mathrm{s}}^{t},E_{\mathrm{s}}^{t},\Delta^{t}_{\mathrm{s}})}$
with the following four elements:  1. $\delta^{t}$is the AoI at the sink,  2.
$e^{t}_{\mathrm{s}}\in\\{0,1\\}$is an occupancy indicator for the controller
server; ${e^{t}_{\mathrm{s}}=1}$ indicates222The same convention is used for
all binary occupancy indicators throughout the paper. that there is a packet
at the controller server, and ${e^{t}_{\mathrm{s}}=0}$ otherwise,  3.
$E^{t}_{\mathrm{s}}\in\\{0,1\\}$is an occupancy indicator for the sampler
server, and  4. $\Delta^{t}_{\mathrm{s}}$is the age of the status update
packet at the sampler server.

####  IV-A2 Action

The action taken in slot $t$ is ${a^{t}\in\mathcal{A}=\\{0,1\\}}$, where
${a^{t}=1}$ indicates that the controller generates a request packet at the
beginning of slot $t$, and ${a^{t}=0}$ otherwise.

####  IV-A3 Policy

A policy $\pi$ is a (possibly randomized) mapping from the state space
$\mathcal{S}$ to action space $\mathcal{A}$. It determines an action $a^{t}$
taken in the current state $s^{t}$. Note that according to the 1-Packet system
constraint, an admissible policy $\pi\in\Pi_{\textrm{1-Packet}}$ must satisfy
${a^{t}=0}$ if there is an active request in the system, i.e., if either
${e_{\mathrm{s}}^{t}=1}$ or ${E_{\mathrm{s}}^{t}=1}$.

####  IV-A4 Problem Formulation

Given an initial state ${s^{0}\in\mathcal{S}}$, the long-term average AoI,
obtained by following a policy $\pi$, is defined as

$\displaystyle
J_{\pi}(s^{0})=\limsup_{T\rightarrow\infty}\dfrac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\delta^{t}\mid
s^{0}\right].$ (8)

where the expectation is with respect to the action taken in each slot and the
randomness in the service times, i.e., required time to serve each packet in
the controller and sampler servers. For the 1-Packet system, the objective is
to find the optimal policy $\pi^{*}$ that provides the minimum long-term
average AoI

$\displaystyle(\textbf{PI})\quad\pi^{*}(s^{0})=\operatorname*{arg\,min}_{\pi\in\Pi_{\textrm{1-Packet}}}J_{\pi}(s^{0}),$
(9)

Next, we recast problem (PI) as an MDP problem and solve it (i.e., find the
optimal policy) using the RVI algorithm.

####  IV-A5 MDP Modeling of Problem (PI)

The MDP of the 1-Packet system is defined by the tuple
${(\mathcal{S},\mathcal{A},\Pr\left\lparen
s^{t+1}|s^{t},a^{t}\right\rparen,C(s^{t},a^{t}))}$, with $C(s^{t},a^{t})$
denoting the (immediate) cost of taking action $a^{t}$ in state $s^{t}$.
Specifically, we define $C(s^{t},a^{t})=\delta^{t+1}$, the AoI at slot $t+1$.
The state transition probability $\Pr\left\lparen
s^{\prime}|s,a\right\rparen=\Pr\left\lparen s^{t+1}|s^{t},a^{t}\right\rparen$
gives the probability of moving from the current state ${s=s^{t}}$ to the next
state ${s^{\prime}=s^{t+1}}$ under an action ${a=a^{t}}$.

To facilitate a compact description of $\Pr\left\lparen
s^{\prime}|s,a\right\rparen$, we employ the shorthand notations
${\bar{\gamma}\triangleq 1-\gamma}$ and ${\bar{\mu}\triangleq 1-\mu}$, as well
as the operator

$[\xi]^{\bar{\Delta}}\triangleq\min\\{\xi+1,\bar{\Delta}\\}.$ (10)

We also adopt the convention that $\star$ indicates an irrelevant age value
when the sampler server is idle. Then, considering the system dynamics, the
transition probability from state
${s=(\delta,e_{\mathrm{s}},E_{\mathrm{s}},\Delta_{\mathrm{s}})}$ to the next
state
${s^{\prime}=(\delta^{\prime},e_{\mathrm{s}}^{\prime},E_{\mathrm{s}}^{\prime},\Delta^{\prime}_{\mathrm{s}})}$
under an action $a$, is characterized as:

$\displaystyle\Pr\left\lparen s^{\prime}|s=(\delta,0,0,\star),a\right\rparen$
$\displaystyle\quad=\begin{cases}1,&a=0,\leavevmode\nobreak\
s^{\prime}=([\delta]^{\bar{\Delta}},0,0,\star);\\\
\gamma,&a=1,\leavevmode\nobreak\
s^{\prime}=([\delta]^{\bar{\Delta}},0,1,0);\\\
\bar{\gamma},&a=1,\leavevmode\nobreak\
s^{\prime}=([\delta]^{\bar{\Delta}},1,0,\star);\\\
0,&\text{otherwise.}\end{cases}$ (11a) $\displaystyle\Pr\left\lparen
s^{\prime}|s=(\delta,1,0,\star),a\right\rparen$
$\displaystyle\quad=\begin{cases}\gamma,&a=0,\leavevmode\nobreak\
s^{\prime}=([\delta]^{\bar{\Delta}},0,1,0);\\\
\bar{\gamma},&a=0,\leavevmode\nobreak\
s^{\prime}=([\delta]^{\bar{\Delta}},1,0,\star);\\\
0,&\text{otherwise.}\end{cases}$ (11b) $\displaystyle\Pr\left\lparen
s^{\prime}|s=(\delta,0,1,\Delta_{\mathrm{s}}),a\right\rparen$
$\displaystyle\quad=\begin{cases}\mu,&a=0,\leavevmode\nobreak\
s^{\prime}=([\Delta_{\mathrm{s}}]^{\bar{\Delta}},0,0,\star);\\\
\bar{\mu},&a=0,\leavevmode\nobreak\
s^{\prime}=([\delta]^{\bar{\Delta}},0,1,[\Delta_{\mathrm{s}}]^{\bar{\Delta}});\\\
0,&\text{otherwise.}\end{cases}$ (11c)

Based on the MDP construction above, problem (PI) is equivalently cast as an
MDP problem

$\pi^{*}(s^{0})\\!=\\!\operatorname*{arg\,min}_{\pi\in\Pi_{\textrm{1-Packet}}}\left\\{\limsup_{T\rightarrow\infty}\dfrac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[C(s^{t},a^{t})\mid
s^{0}\right]\\!\right\\}.$ (12)

####  IV-A6 Optimal Policy

According to [71, Proposition 4.2.1], for a given initial state $s^{0}$, if we
can find a scalar $\bar{V}$ and values $V^{*}_{s}$ for all $s\in\mathcal{S}$
that satisfy

$\displaystyle\bar{V}+V^{*}_{s}=\min_{a\in\mathcal{A}}\left\\{C(s,a)+\sum_{s^{\prime}\in\mathcal{S}}\Pr(s^{\prime}|s,a)V^{*}_{s^{\prime}}\right\\},$
(13)

then $\bar{V}$ is the optimal average cost for problem (PI),
$J_{\pi^{*}}(s^{0})$, and the actions $a\in\mathcal{A}$ that attain the
minimum in (13) constitute an optimal policy, $\pi^{*}(s^{0})$.

Next, we define a condition under which the Bellman’s equation in (13) has a
solution and the optimal average cost is independent of the initial state
$s^{0}$ [71, Proposition 4.2.3].

######  Definition 1 (Weak accessibility condition).

The weak accessibility condition holds for an MDP problem if the states can be
divided into two subsets $\mathcal{S}_{\mathrm{c}}$ and
$\mathcal{S}_{\mathrm{t}}$ such that: I) for any two states $s$ and
$s^{\prime}$ in subset $\mathcal{S}_{\mathrm{c}}$, there exists a stationary
policy such that the probability of moving from state $s$ to state
$s^{\prime}$ after some slots is non-zero, and II) all states in
$\mathcal{S}_{\mathrm{t}}$ are transient under every stationary policy [71,
Definition 4.2.2].

In the following lemma, we prove that the weak accessibility condition holds
for the MDP problem defined in (12).

######  Lemma 1.

For any $(\mu,\gamma)\in\\{(\theta_{1},\theta_{2})\mid
0<\theta_{1},\theta_{2}\leq 1,\leavevmode\nobreak\
(\theta_{1},\theta_{2})\neq(1,1)\\}$, the weak accessibility condition holds
for the MDP problem (12).

###### Proof.

If all deterministic policies in $\Pi_{\textrm{1-Packet}}$ are unichain, the
weak accessibility condition holds [71, Proposition 4.2.5]. A policy is
unichain if in the Markov chain induced by the policy, there exists a state
that can be reached from any other states with a non-zero probability [72,
Exercise 4.3]. In the MDP problem (12), under any deterministic policy: I) for
${\gamma\neq 1}$ and ${0<\mu\leq 1}$, the state $(\bar{\Delta},1,0,\star)$ is
accessible from any other states and II) for ${\gamma=1}$ and ${0<\mu<1}$, the
state $(\bar{\Delta},0,1,\bar{\Delta})$ is accessible from any other states.
The justification for case I is that when there is a packet at the controller
server, the probability of the event of having unsuccessful transmissions in
$\bar{\Delta}$ consecutive slots is non-zero. A similar argument can be stated
for case II. Thus, every deterministic policy is unichain and consequently,
the weak accessibility condition holds. ∎

Given that the weak accessibility condition holds, we can find an optimal
deterministic policy $\pi^{*}$ and the optimal average cost $J^{*}$, which are
independent of the initial state $s^{0}$, by solving the Bellman’s equation in
(13) [71, Proposition 4.2.6]. We solve it using the RVI algorithm [71, Section
4.3], which turns the Bellman’s equation into an iterative procedure. The
steps of the RVI algorithm are summarized in Algorithm 1. As specified in
lines 1 and 1, the optimal deterministic action $\pi^{*}_{s}$ and the scalar
$V^{*}_{s}$ are updated for each state ${s\in\mathcal{S}}$ in each iteration,
where ${s_{\text{ref}}\in\mathcal{S}}$ is an arbitrary chosen reference state.
Once the iterative process has converged, the algorithm provides an optimal
policy $\pi^{*}$ and the optimal value of the average AoI, obtained as
$J_{\pi^{*}}=V^{*}_{s_{\text{ref}}}$. The following theorem shows that the RVI
algorithm presented in Algorithm 1 converges to an optimal deterministic
policy.

1 Input: 1) State transition probabilities $\Pr(s^{\prime}|s,a)$, 2) Stopping
criterion threshold $\epsilon$;

2Initialization: 1) Set ${V^{*}_{s}=0}$, ${\forall s\in\mathcal{S}}$, 2)
determine an arbitrary reference state ${s_{\text{ref}}\in\mathcal{S}}$, and
3) set $\phi>\epsilon$;

3

4while  _$\phi >\epsilon$_ do

5 for  _$s\in\mathcal{S}$_ do

6
$\pi^{*}_{s}\leftarrow\arg{\displaystyle\min_{a\in\mathcal{A}}}\\{C(s,a)+\sum_{s^{\prime}\in\mathcal{S}}\Pr(s^{\prime}|s,a)V^{*}_{s^{\prime}}\\}$;

7 $V_{s}\leftarrow
C(s,\pi^{*}_{s})+\sum_{s^{\prime}\in\mathcal{S}}\Pr(s^{\prime}|s,\pi^{*}_{s})V^{*}_{s^{\prime}}-V^{*}_{s_{\text{ref}}}$;

8

9 end for

10 $\phi\leftarrow\max_{s\in\mathcal{S}}\\{|V_{s}-V^{*}_{s}|\\}$;

11 $V^{*}_{s}\leftarrow V_{s}$, $\forall s\in\mathcal{S}$;

12

13 end while

Output: 1) Optimal policy $\pi^{*}$, 2) optimal objective function value
${J_{\pi^{*}}=V^{*}_{s_{\text{ref}}}}$.

Algorithm 1 RVI algorithm

######  Theorem 1.

The RVI algorithm presented in Algorithm 1 converges to an optimal
deterministic policy and returns the optimal value of the average AoI.

###### Proof.

According to [71, Page 209], it is sufficient to show that the Markov chain
induced by every deterministic policy is unichain and aperiodic. In the proof
of Lemma 1, we showed that any deterministic policy induces a unichain Markov
chain. According to [73, Exercise 4.1], since the recurrent states
$(\bar{\Delta},1,0,\star)$ (for ${\gamma\neq 1}$ and ${0<\mu\leq 1}$) and
$(\bar{\Delta},0,1,\bar{\Delta})$ (for ${\gamma=1}$ and ${0<\mu<1}$) have
self-transitions, the Markov chain induced by every deterministic policy is
aperiodic. ∎

###  IV-B 2-Packet System

Here, we extend the MDP construction of the 1-Packet system (described in
Section IV-A) for the 2-Packet system and subsequently derive the optimal
status update control policy.

For the 2-Packet system, the action space and the cost function are the same
as for the 1-Packet system. However, the system state needs to be redefined to
account for the two active requests.

####  IV-B1 State

Let ${\underline{s}^{t}\in\mathcal{\underline{S}}}$ denote the system state in
slot $t$, where ${\mathcal{\underline{S}}}$ is the state space. We define the
system state as
${\underline{s}^{t}=(\delta^{t},e_{\mathrm{b}}^{t},e_{\mathrm{s}}^{t},E_{\mathrm{b}}^{t},E_{\mathrm{s}}^{t},\Delta^{t}_{\mathrm{b}},\Delta^{t}_{\mathrm{s}})}$
with the following seven elements:  1. $\delta^{t}$is the AoI at the sink,  2.
${e^{t}_{\mathrm{b}}\in\\{0,1\\}}$is the occupancy indicator for the
controller buffer,  3. ${e^{t}_{\mathrm{s}}\in\\{0,1\\}}$is the occupancy
indicator for the controller server,  4. ${E^{t}_{\mathrm{b}}\in\\{0,1\\}}$is
the occupancy indicator for the sampler buffer,  5.
${E^{t}_{\mathrm{s}}\in\\{0,1\\}}$is the occupancy indicator for the sampler
server,  6. $\Delta^{t}_{\mathrm{b}}$is the age of the status update packet at
the sampler buffer, and  7. $\Delta^{t}_{\mathrm{s}}$is the age of the status
update packet at the sampler server.

######  Remark 1.

Having the four occupancy indicators $e^{t}_{\mathrm{b}}$,
$e^{t}_{\mathrm{s}}$, $E^{t}_{\mathrm{b}}$, and $E^{t}_{\mathrm{s}}$ in the
state implies that the controller (i.e., the decision-maker) has global
knowledge of the system occupancy. This consideration may not always be
practical, and thus, the derived control policy establishes a performance
bound for policies operating under local/imperfect knowledge.

####  IV-B2 Problem Formulation

Given an initial state $\underline{s}^{0}$, the average AoI, obtained by
following a policy $\pi$, is defined as

$\displaystyle\underline{J}_{\pi}(\underline{s}^{0})=\limsup_{T\rightarrow\infty}\dfrac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\pi}\left[\delta^{t}\mid\underline{s}^{0}\right].$
(14)

Note that according to the 2-Packet system constraint, the set of admissible
policies must satisfy that if there are two active requests in the system,
i.e., ${(e_{\mathrm{b}}^{t},e_{\mathrm{s}}^{t})=(1,1)}$ or
${(e_{\mathrm{s}}^{t},E_{\mathrm{s}}^{t})=(1,1)}$ or
${(E_{\mathrm{b}}^{t},E_{\mathrm{s}}^{t})=(1,1)}$, then ${a^{t}=0}$. The
problem of finding the optimal policy $\pi^{*}$ that provides the minimum
long-term average AoI in the 2-Packet system is formulated as

$\displaystyle(\textbf{PII})\leavevmode\nobreak\
\pi^{*}(\underline{s}^{0})=\operatorname*{arg\,min}_{\pi\in\Pi_{\textrm{2-Packet}}}\underline{J}_{\pi}(\underline{s}^{0}),$
(15)

where $\Pi_{\textrm{2-Packet}}$ is the set of all admissible policies subject
to the 2-Packet system constraint. Next, we recast problem (PII) as an MDP
problem and solve it using the RVI algorithm.

####  IV-B3 MDP Modeling for Problem (PII)

The MDP of the 2-Packet system is defined by the tuple
$(\mathcal{\underline{S}},\mathcal{A},\Pr(\underline{s}^{t+1}|\underline{s}^{t},a^{t}),C(\underline{s}^{t},a^{t}))$.
The (immediate) cost function is defined as
$C(\underline{s}^{t},a^{t})=\delta^{t+1}$ (similarly as for problem (PI)). The
transition probability $\Pr(\underline{s}^{\prime}|\underline{s},a)$ of moving
from state
$\underline{s}=(\delta,e_{\mathrm{b}},e_{\mathrm{s}},E_{\mathrm{b}},E_{\mathrm{s}},\Delta_{\mathrm{b}},\Delta_{\mathrm{s}})$
to the next state
$\underline{s}^{\prime}=(\delta^{\prime},e_{\mathrm{b}}^{\prime},e_{\mathrm{s}}^{\prime},E_{\mathrm{b}}^{\prime},E_{\mathrm{s}}^{\prime},\Delta_{\mathrm{b}}^{\prime},\Delta_{\mathrm{s}}^{\prime})$
under an action $a$ is characterized as:

$\displaystyle\mathrlap{\Pr(\underline{s}^{\prime}|\underline{s}=(\delta,0,0,0,0,\star,\star),a)}$
(16a) $\displaystyle=$ $\displaystyle\begin{cases}1,&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,0,0,0,\star,\star);\\\
\gamma,&a=1,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,0,0,1,\star,0);\\\
\bar{\gamma},&a=1,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,1,0,0,\star,\star);\\\
0,&\text{otherwise.}\end{cases}$
$\displaystyle\mathrlap{\Pr(\underline{s}^{\prime}|\underline{s}=(\delta,1,1,0,0,\star,\star),a)}$
(16b) $\displaystyle=$
$\displaystyle\begin{cases}\gamma,&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,1,0,1,\star,0);\\\
\bar{\gamma},&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},1,1,0,0,\star,\star);\\\
0,&\text{otherwise.}\end{cases}$
$\displaystyle\mathrlap{\Pr(\underline{s}^{\prime}|\underline{s}=(\delta,0,1,0,0,\star,\star),a)}$
(16c) $\displaystyle=$
$\displaystyle\begin{cases}\gamma,&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,0,0,1,\star,0);\\\
\bar{\gamma},&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,1,0,0,\star,\star);\\\
\gamma,&a=1,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,1,0,1,\star,0);\\\
\bar{\gamma},&a=1,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},1,1,0,0,\star,\star);\\\
0,&\text{otherwise.}\end{cases}$
$\displaystyle\mathrlap{\Pr(\underline{s}^{\prime}|\underline{s}=(\delta,0,1,0,1,\star,\Delta_{\mathrm{s}}),a)}$
(16d) $\displaystyle=$
$\displaystyle\begin{cases}\bar{\gamma}\bar{\mu},&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,1,0,1,\star,[\Delta_{\mathrm{s}}]^{\bar{\Delta}});\\\
\gamma\bar{\mu},&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,0,1,1,0,[\Delta_{\mathrm{s}}]^{\bar{\Delta}});\\\
\bar{\gamma}\mu,&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\Delta_{\mathrm{s}}]^{\bar{\Delta}},0,1,0,0,\star,\star);\\\
\gamma\mu,&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\Delta_{\mathrm{s}}]^{\bar{\Delta}},0,0,0,1,\star,0);\\\
0,&\text{otherwise.}\end{cases}$
$\displaystyle\mathrlap{\Pr(\underline{s}^{\prime}|\underline{s}=(\delta,0,0,1,1,\Delta_{\mathrm{b}},\Delta_{\mathrm{s}}),a)}$
(16e) $\displaystyle=$
$\displaystyle\begin{cases}\mu,&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\Delta_{\mathrm{s}}]^{\bar{\Delta}},0,0,0,1,\star,[\Delta_{\mathrm{b}}]^{\bar{\Delta}});\\\
\bar{\mu},&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,0,1,1,[\Delta_{\mathrm{b}}]^{\bar{\Delta}},[\Delta_{\mathrm{s}}]^{\bar{\Delta}});\\\
0,&\text{otherwise.}\end{cases}$
$\displaystyle\mathrlap{\Pr(\underline{s}^{\prime}|\underline{s}=(\delta,0,0,0,1,\star,\Delta_{\mathrm{s}}),a)}$
$\displaystyle=$
$\displaystyle\begin{cases}\bar{\mu},&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,0,0,1,\star,[\Delta_{\mathrm{s}}]^{\bar{\Delta}});\\\
\mu,&a=0,\leavevmode\nobreak\
\underline{s}^{\prime}=([\Delta_{\mathrm{s}}]^{\bar{\Delta}},0,0,0,0,\star,\star);\\\
\bar{\gamma}\bar{\mu},&a=1,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,1,0,1,\star,[\Delta_{\mathrm{s}}]^{\bar{\Delta}});\\\
\bar{\gamma}\mu,&a=1,\leavevmode\nobreak\
\underline{s}^{\prime}=([\Delta_{\mathrm{s}}]^{\bar{\Delta}},0,1,0,0,\star,\star);\\\
\gamma\bar{\mu},&a=1,\leavevmode\nobreak\
\underline{s}^{\prime}=([\delta]^{\bar{\Delta}},0,0,1,1,0,[\Delta_{\mathrm{s}}]^{\bar{\Delta}});\\\
\gamma\mu,&a=1,\leavevmode\nobreak\
\underline{s}^{\prime}=([\Delta_{\mathrm{s}}]^{\bar{\Delta}},0,0,0,1,\star,0);\\\
0,&\text{otherwise}.\end{cases}$ (16f)

Based on the above definitions, the MDP formulation of problem (PII) is
formulated as

$\displaystyle\\!\\!\pi^{*}(\underline{s}^{0})\\!=\\!\operatorname*{arg\,min}_{\pi\in\Pi_{\textrm{2-Packet}}}\Bigl{\\{}\limsup_{T\rightarrow\infty}\dfrac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[C(\underline{s}^{t},a^{t})\mid\underline{s}^{0}\right]\Bigr{\\}}.$
(17)

####  IV-B4 Optimal Policy

First, similar to the proof of Lemma 1 for the 1-Packet system, one can show
that the weak accessibility condition holds for the 2-Packet MDP problem in
(17) for any $(\mu,\gamma)\in\\{(\theta_{1},\theta_{2})\mid
0<\theta_{1},\theta_{2}\leq 1,\leavevmode\nobreak\
(\theta_{1},\theta_{2})\neq(1,1)\\}$. Here, the recurrent states are
$(\bar{\Delta},1,1,0,0,\star,\star)$ for ${\gamma\neq 1}$ and ${0<\mu\leq 1}$,
and $(\bar{\Delta},0,0,1,1,\bar{\Delta},\bar{\Delta})$ for ${\gamma=1}$ and
${0<\mu<1}$.

By the weak accessibility condition, the optimal average cost
$\underline{J}_{\pi^{*}}$ and optimal policy $\pi^{*}$ are derived by solving
the following equation for each $\underline{s}\in\mathcal{\underline{S}}$ (cf.
(13)):

$\displaystyle\underline{J}_{\pi^{*}}+V^{*}_{\underline{s}}=\min_{a\in\mathcal{A}}\Bigl{\\{}C(\underline{s},a)+\sum_{\underline{s}^{\prime}\in\mathcal{\underline{S}}}\Pr(\underline{s}^{\prime}|\underline{s},a)V^{*}_{\underline{s}^{\prime}}\Bigr{\\}}.$
(18)

The RVI algorithm presented in Algorithm 1 is used to iteratively solve for
$\underline{J}_{\pi^{*}}$ and $V^{*}_{\underline{s}}$ in (18).

##  V Average AoI Analysis

In this section, we derive the average AoI expressions for the following three
policies:  1. a zero-wait policy for the 1-Packet system, hereinafter referred
to as the Zero-Wait-1 policy,  2. a zero-wait policy for the 2-Packet system,
hereinafter referred to as the _Zero-Wait-2_ policy (Section V-B), and  3. a
waiting-based policy for the 1-Packet system, hereinafter referred to as the
_Wait-1_ policy (Section V-C).

###  V-A Zero-Wait-1: AoI Analysis

In this section, we derive the average AoI under the Zero-Wait-1 policy. Since
the Zero-Wait-1 policy conforms to the zero-wait serving discipline (also
known as work-conserving or just-in-time policy [6]), the controller sends a
new request message immediately after receiving a status update packet. That
is, if status update packet $i-1$ is received by the end of slot $t-1$, the
controller generates request packet $i$ at the beginning of slot $t$, which
enters an empty system. The AoI evolution under Zero-Wait-1 is illustrated in
Fig. 3.

To characterize the average AoI as given by (7), we need to calculate
$\mathbb{E}[I_{i}]$, $\mathbb{E}[I_{i}^{2}]$, and $\mathbb{E}[I_{i}T_{i}]$. As
preliminaries, let $X_{i}$ be the random variable representing the required
time to serve the $i$th request packet by the controller server. Similarly,
let $Y_{i}$ be the random variable representing the required time to serve the
$i$th status update packet by the sampler server. Because the service times of
all request messages are stochastically identical and the service times of all
status update packets are stochastically identical, ${X_{i}=^{\mathrm{st}}X}$
and ${Y_{i}=^{\mathrm{st}}Y}$ for all ${i=\\{1,2,\ldots\\}}$, and
${X\sim\mathrm{Geo}(\gamma)}$ and ${Y\sim\mathrm{Geo}(\mu)}$. Now we delve
into calculations of $\mathbb{E}[I_{i}]$, $\mathbb{E}[I_{i}^{2}]$, and
$\mathbb{E}[I_{i}T_{i}]$.

####  V-A1 Derivation of $\mathbb{E}[I_{i}]$ and $\mathbb{E}[I^{2}_{i}]$

As it can be seen in Fig. 3, the interarrival time between status update
packets $i-1$ and $i$ at the sampler server is

$I_{i}=Y_{i-1}+X_{i}.$ (19)

The mean and second moment of the interarrival time, $\mathbb{E}[I_{i}]$ and
$\mathbb{E}[I_{i}^{2}]$, are

$\displaystyle\mathbb{E}[I_{i}]$
$\displaystyle=\mathbb{E}[Y_{i-1}]+\mathbb{E}[X_{i}]=\dfrac{1}{\mu}+\dfrac{1}{\gamma},$
(20) $\displaystyle\mathbb{E}[I^{2}_{i}]$
$\displaystyle=\mathbb{E}[(Y_{i-1}+X_{i})^{2}]$
$\displaystyle=\mathbb{E}[Y^{2}_{i-1}]+\mathbb{E}[X^{2}_{i}]+2\mathbb{E}[Y_{i-1}]\mathbb{E}[X_{i}]$
(21)
$\displaystyle=\dfrac{2-\mu}{\mu^{2}}+\dfrac{2-\gamma}{\gamma^{2}}+\dfrac{2}{\mu\gamma},$
(22)

where (21) follows from independence of $X_{i}$ and $Y_{i-1}$.

####  V-A2 Derivation of $\mathbb{E}[I_{i}T_{i}]$

As it can be seen in Fig. 3, the system time of packet $i$, $T_{i}$, equals
$Y_{i}$, the service time of update packet $i$. Thus,

$\displaystyle\mathbb{E}[I_{i}T_{i}]$
$\displaystyle=\mathbb{E}[(Y_{i-1}+X_{i})Y_{i}]$
$\displaystyle\overset{(a)}{=}\mathbb{E}[Y_{i}]\mathbb{E}[Y_{i-1}+X_{i}]=\dfrac{1}{\mu}\left(\dfrac{1}{\mu}+\dfrac{1}{\gamma}\right),$
(23)

where $(a)$ follows from independence of $Y_{i}$ and $X_{i},Y_{i-1}$.

Figure 3: AoI as a function of time under the Zero-Wait-1 policy.

Substituting (20), (22), and (23) into (7) yields Theorem 2.

######  Theorem 2.

The average AoI under the Zero-Wait-1 policy is

$\displaystyle\Delta^{\mathrm{\text{Zero-
Wait-{1}}}}=\frac{2}{\mu}+\frac{\mu}{\gamma(\mu+\gamma)}-1.$ (24)

###  V-B Zero-Wait-2: AoI Analysis

To evaluate the AoI of the Zero-Wait-2 system using (7), we need to track the
event $B_{i}$ that the sampler server is busy (serving update packet $i-1$)
when request message $i$ arrives at the sampler and update packet $i$ is
generated. In particular, with ${\overline{B}}_{i}$ denoting the complement of
$B_{i}$, the two-step partition
$\left\\{{\overline{B}}_{i-1}{\overline{B}}_{i},{\overline{B}}_{i-1}B_{i},B_{i-1}{\overline{B}}_{i},B_{i-1}B_{i}\right\\}$
is needed to evaluate the AoI of the Zero-Wait-2 system. The proof in Appendix
VIII-A verifies the following result.

######  Theorem 3.

The average AoI under the Zero-Wait-2 policy is

$\displaystyle\Delta^{\text{Zero-Wait-{2}}}$
$\displaystyle=\frac{1}{\gamma}+\frac{1}{\mu}-1+\frac{2\gamma^{2}\bar{\mu}}{\mu(\gamma\bar{\mu}(\gamma+\mu)+\mu^{2})}.$
(25)

By applying algebraic manipulations to the difference
${\Delta^{\mathrm{\text{Zero-Wait-{2}}}}-\Delta^{\mathrm{\text{Zero-
Wait-{1}}}}}$, we obtain the following corollary that specifies the ranges of
service time parameters $\gamma$ and $\mu$ for which Zero-Wait-2 outperforms
the Zero-Wait-1.

######  Corollary 1.

The Zero-Wait-2 policy outperforms the Zero-Wait-1 policy, i.e.,
${\Delta^{\mathrm{\text{Zero-Wait-{2}}}}\leq\Delta^{\mathrm{\text{Zero-
Wait-{1}}}}}$, if the service rates satisfy

$\displaystyle\mu$
$\displaystyle\geq\frac{\gamma\big{(}\bar{\gamma}+\sqrt{(\gamma+1)^{2}+4}\big{)}}{2(\gamma+1)}\quad\text{or}$
(26a) $\displaystyle\gamma$
$\displaystyle\leq\frac{\mu\big{(}-\bar{\mu}+\sqrt{\bar{\mu}(5-\mu)}\big{)}}{2+\bar{\mu}}.$
(26b)

The specified regions are illustrated in Fig. 4. As one observation from
(26a), when $\mu\geq\frac{\sqrt{2}}{2}\approx 0.7071$, we have
$\Delta^{\mathrm{\text{Zero-Wait-{2}}}}\leq\Delta^{\mathrm{\text{Zero-
Wait-{1}}}}$ for any value of $\gamma$.

Figure 4: Average AoI performance comparison between the Zero-Wait-1 policy
and the Zero-Wait-2 policy with respect to different service rate pairs
$(\mu,\gamma)$.

###  V-C Wait-1: AoI Analysis

In this section, we derive the average AoI under the Wait-1 policy.
Differently to the zero-wait policies, when the controller receives status
update packet ${i-1}$, the Wait-1 policy permits the controller to assign a
waiting time prior to sending request message $i$. Such appropriately placed
waiting time has potential to lead to lower average AoI than that of the zero-
wait policy333This is not unforeseen: a waiting-based policy, instead of a
zero-wait policy, has been shown to realize optimal status updating in various
other systems, as detailed in Remark 2., as will be shown by our subsequent
analysis.

Formally, let ${Z_{i}}$ be a random variable for the waiting time assigned to
request message $i$ after receiving update ${i-1}$. In this work, in line with
[5], we consider that ${Z_{i}=f(Y_{i-1})}$, i.e., the waiting time is a
deterministic function of the service time of status update packet $i-1$ (at
the sampler server). AoI evolution under the Wait-1 policy is illustrated in
Fig. 5.

Figure 5: AoI as a function of time under the Wait-1 policy.

We restrict to threshold-type waiting functions of form

$\displaystyle Z_{i}=f(Y_{i-1})=(\beta-Y_{i-1})^{+},$ (27)

where $\beta$ is a positive integer; ${\beta=1}$ corresponds to the Zero-
Wait-1 policy. While we have not been able to prove the optimality of this
waiting function for our considered system, the structure of an optimal policy
(obtained by the MDP approach), as visualized in Section VI, has such
threshold-type structure.

######  Remark 2.

This is consistent with prior works on the optimality of waiting policies for
various status updating systems. The threshold-type waiting function (27) with
appropriately adjusted $\beta$, was proven to be the optimal waiting function
in a stop-and-wait continuous-time system with a non-delayed control channel
in [5, Theorem 1] and [6, Theorem 4] and in its discrete-time equivalent in
[49, Theorem 3]. Under a delayed control channel, the optimality of the
threshold-type waiting in continuous-time systems has been shown in [55,
Proposition 2] and [56, Theorem 1].

To characterize the average AoI as given by (7), we need to calculate
$\mathbb{E}[I_{i}]$, $\mathbb{E}[I_{i}^{2}]$, and $\mathbb{E}[I_{i}T_{i}]$. As
it can be seen in Fig. 5, the interarrival time of status update packets $i-1$
and $i$ is the summation of the service time of status update packet $i-1$,
$Y_{i-1}$, the waiting time of request message $i$, $Z_{i}$, and the service
time of request message $i$, $X_{i}$, i.e., ${I_{i}=Y_{i-1}+Z_{i}+X_{i}}$. The
mean interarrival time, $\mathbb{E}[I_{i}]$, is given as

$\displaystyle\mathbb{E}[I_{i}]=\mathbb{E}[Y_{i-1}]+\mathbb{E}[Z_{i}]+\mathbb{E}[X_{i}]=\dfrac{1}{\mu}+\mathbb{E}[Z_{i}]+\dfrac{1}{\gamma},$
(28)

where $\mathbb{E}\left[Z_{i}\right]$ is given by the following lemma.

######  Lemma 2.

The mean waiting time $\mathbb{E}\left[Z_{i}\right]$ is given as

$\begin{array}[]{ll}\mathbb{E}\left[Z_{i}\right]=\displaystyle\frac{1}{\mu}\left(\beta\mu+\bar{\mu}^{\beta}-1\right).\end{array}$
(29)

###### Proof.

See Appendix VIII-C. ∎

The second moment of the interarrival time, $\mathbb{E}[I_{i}^{2}]$, is
derived as

$\displaystyle\mathbb{E}[I^{2}_{i}]$
$\displaystyle=\mathbb{E}[(Y_{i-1}+Z_{i}+X_{i})^{2}]$
$\displaystyle=\mathbb{E}[(Y_{i-1}+X_{i})^{2}]+2\mathbb{E}[Z_{i}(Y_{i-1}+X_{i})]+\mathbb{E}[Z_{i}^{2}]$
$\displaystyle\overset{(a)}{=}\mathbb{E}[Y^{2}]+\mathbb{E}[X^{2}]+2\mathbb{E}[X]\mathbb{E}[Y]+2\mathbb{E}[Z_{i}Y_{i-1}]$
$\displaystyle\qquad+2\mathbb{E}[Z_{i}]\mathbb{E}[X_{i}]+\mathbb{E}[Z_{i}^{2}],$
(30)

where equality $(a)$ comes from the fact that $X_{i}$ and $Y_{i-1}$ are
independent and $Z_{i}$ and $X_{i}$ are independent; the expectations
$\mathbb{E}[Z_{i}Y_{i-1}]$ and $\mathbb{E}\left[Z_{i}^{2}\right]$ are given by
the following lemmas.

######  Lemma 3.

The expectation $\mathbb{E}\left[Z_{i}Y_{i-1}\right]$ is given as

$\displaystyle\mathbb{E}\left[Z_{i}Y_{i-1}\right]$
$\displaystyle=\frac{1}{\mu^{2}}\big{(}\mu+\beta\mu+\bar{\mu}^{\beta}(2-\mu+\beta\mu)-2\big{)}$
(31)

###### Proof.

See Appendix VIII-D. ∎

######  Lemma 4.

The second moment of the waiting time, $\mathbb{E}\left[Z_{i}^{2}\right]$, is
given as

$\begin{array}[]{ll}\mathbb{E}\left[Z_{i}^{2}\right]&\\!=\\!\displaystyle-\frac{1}{\mu^{2}}\big{(}\mu+2\beta\mu+\bar{\mu}^{\beta}(2-\mu)-\beta^{2}\mu^{2}-2\big{)}.\end{array}$
(32)

###### Proof.

See Appendix VIII-E. ∎

As it can be seen in Fig. 5, the system time of packet $i$, $T_{i}$, is equal
to the service time of status update packet $i$, $Y_{i}$. Thus, the
expectation $\mathbb{E}[I_{i}T_{i}]$ is derived as

$\displaystyle\mathbb{E}[I_{i}T_{i}]$
$\displaystyle=\mathbb{E}[(Y_{i-1}+Z_{i}+X_{i})Y_{i}]$
$\displaystyle\overset{(a)}{=}\mathbb{E}[Y_{i}]\mathbb{E}[Y_{i-1}+Z_{i}+X_{i}]$
$\displaystyle=\\!\dfrac{1}{\mu}\\!\left(\dfrac{1}{\mu}+\mathbb{E}[Z_{i}]+\dfrac{1}{\gamma}\\!\right),$
(33)

where equality $(a)$ follows from $Y_{i}$ being independent of $Y_{i-1}$,
$Z_{i}$, and $X_{i}$. Substituting (28), (V-C), and (33) into (7), we have
Theorem 4.

######  Theorem 4.

For waiting functions ${Z_{i}=(\beta-Y_{i-1})^{+}}$, the average AoI under the
Wait-1 policy is given as

$\displaystyle\Delta^{\mathrm{\text{Wait-1}}}=$
$\displaystyle\quad\frac{\beta\mu(-\beta\gamma+\gamma-2)-2(\beta\gamma+1)}{2(\gamma(\bar{\mu}^{\beta}+\beta\mu)+\mu)}+\beta+\frac{1}{\gamma}+\frac{2}{\mu}-1.$
(34)

Next, we provide an upper bound on the optimal $\beta$.

######  Lemma 5.

For a given service rate pair $(\gamma,\mu)$, $\beta^{*}$, the optimal value
of $\beta$ for the Wait-1 policy, satisfies $\beta^{*}\leq\beta^{\max}$, where

$\displaystyle\beta^{\text{max}}$ $\displaystyle=$
$\displaystyle\bigg{\lfloor}{\dfrac{2\gamma+\sqrt{(\mu^{2}+\gamma\mu-2\gamma)^{2}+8(\mu^{2}+\gamma\mu)}}{2(\mu^{2}+\gamma\mu)}-\frac{1}{2}}\bigg{\rfloor}.$
(35)

###### Proof.

See Appendix VIII-F. ∎

From Lemma (5), the optimal Wait-1 policy is easily found by searching for the
$\beta\in\\{1,\ldots,\beta^{\text{max}}\\}$ that minimizes (34). We also note
that from the bound $\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$ for non-negative $x,y$,
it can be shown that

$\displaystyle\beta^{\max}$
$\displaystyle\leq\biggl{\lfloor}\Bigl{[}\frac{2\gamma}{\mu^{2}+\gamma\mu}-1\Bigr{]}^{+}+\sqrt{\frac{2}{\mu^{2}+\gamma\mu}}\biggr{\rfloor}$
(36)

From (36), we see that $\beta^{\max}$ grows as $O(1/\mu)$ as $\mu\to 0$. By
applying algebraic manipulations to the difference
${\Delta^{\mathrm{\text{Wait-1}}}-\Delta^{\mathrm{\text{Zero-Wait-{1}}}}}$, we
obtain the following corollary.

######  Corollary 2.

In the 1-Packet system, it is optimal to wait, i.e., to set ${\beta\geq 2}$
for the waiting function ${Z_{i}(Y_{i-1})=(\beta-Y_{i-1})^{+}}$, if the
service rates $\mu$ and $\gamma$ satisfy

$\mu\leq\displaystyle\frac{-\gamma+\sqrt{\gamma^{2}+2\gamma}}{2}\quad\text{or}\quad\gamma\geq\displaystyle\frac{2\mu^{2}}{1-2\mu}.$
(37)

Corollary 2 reveals a threshold: a Wait-1 policy that reduces the average AoI
cannot be realized if ${\mu>\frac{\sqrt{3}-1}{2}\approx 0.366}$, regardless of
the value of $\gamma$.

##  VI Numerical Results

In this section, we evaluate the performance of the optimal and fixed control
policies proposed for the 1-Packet and 2-Packet systems as well as visualize
the structure of the optimal policies. The optimal policies are obtained via
the MDP-based approaches presented in Section IV-A and IV-B. The fixed
policies are the Zero-Wait-1 policy (Section V-A), Zero-Wait-2 policy (Section
V-B), and Wait-1 policy (Section V-C). Algorithm 1 is run with the maximum
value of the AoI $\bar{\Delta}=50$ and the stopping criterion threshold
${\epsilon=0.0005}$, unless otherwise stated.

###  VI-A Structure of the Optimal Policies

In this section, the structure of the optimal policy for the 1-Packet and
2-packet systems for service rate values
$\mu\in\\{0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1\\}$ and $\gamma\in\\{0.4,0.7,1\\}$
are illustrated.

####  VI-A1 1-Packet System

Fig. 6 illustrates the structure of the optimal policy in the 1-Packet system
by showing the optimal action in state ${s=(\delta,0,0,\star)}$ (i.e., empty
system) for the different values of $\mu$ and $\gamma$. The figure reveals a
threshold structure with respect to the AoI, $\delta$: when the current AoI
has a low value (e.g., when $\delta\leq 2$ for ${\gamma=0.4}$ and $\mu=0.2$),
the optimal action is to stay idle (${a=0}$). Similarly, when the AoI exceeds
this threshold, the optimal action is to send a request packet. When the
reverse link service rate $\gamma$ increases, the AoI threshold increases.
These behaviors are due to the fact that sending a new request packet would
put the same burden on the network, regardless of its contribution to reducing
the AoI, as any other request packet. Thus, if sending a new request packet
cannot significantly reduce the AoI, it is optimal to wait. Finally, we
observe that Corollary 2 holds in Fig. 6: for the sampler server’s service
rate $\mu$ exceeding $\frac{\sqrt{3}-1}{2}\approx 0.366$, the optimal action
is always ${a=1}$.

(a) $\gamma=0.4$

(b) $\gamma=0.7$

(c) $\gamma=1$

Figure 6: Structure of the optimal policy for the 1-Packet system in state
${s=(\delta,0,0,\star)}$ and for the 2-Packet system in state
${\underline{s}=(\delta,0,0,0,0,\star,\star)}$; ${a=1}$ indicates that the
optimal action is to generate a request packet, whereas ${a=0}$ indicates that
the optimal action is to stay idle.

To further analyze the threshold structure, Fig. 7 illustrates the average AoI
obtained by the Wait-1 policy (Theorem 4) as a function of $\beta$ for
different values of $\gamma$ with ${\mu=0.1}$. The average AoI obtained by the
optimal policy in the 1-Packet system (obtained with RVI parameters
${\bar{\Delta}=100}$ and $\epsilon=10^{-6}$) is also depicted. As it can be
seen, when the value of $\gamma$ increases, the optimal value of $\beta$
increases, i.e., the optimal policy induces longer waiting times. This is
because when the request packets are served faster in the reverse link, the
corresponding generated status update packets will provide small AoI reduction
if the AoI upon sending the new request was already small. Thus, it is
beneficial to purposely postpone sending the requests. Note that the same
trend is visible in Fig. 6. Importantly, Fig. 7 shows that the average AoI
obtained by the optimal Wait-1 policy (i.e., the Wait-1 policy with the
optimal $\beta$) and the optimal policy in the 1-Packet system coincide. This
shows evidence on the optimality of the waiting-based scheme, as conjectured
in Section V-C.

(a) $\gamma=0.4$

(b) $\gamma=0.7$

(c) $\gamma=1$

Figure 7: Average AoI under the Wait-1 policy as a function of $\beta$ for
different values of $\gamma$ with $\mu=0.1$.

####  VI-A2 2-Packet System

In the 2-Packet system, the three states of interest where the optimal action
needs to be determined are: 1) ${\underline{s}=(\delta,0,0,0,0,\star,\star)}$
(i.e., empty system), 2)
${\underline{s}=(\delta,0,0,0,1,\star,\Delta_{\mathrm{s}})}$ (i.e., there is a
status update packet at the sampler server), and 3)
${\underline{s}=(\delta,0,1,0,0,\star,\Delta_{\mathrm{s}})}$ (i.e., there is a
request packet at the controller server). Regarding the first case, the
structure of the optimal policy in the 2-Packet system in state
$\underline{s}=(\delta,0,0,0,0,\star,\star)$ is the same as that for the
1-Packet system; this threshold-type policy with respect to the AoI was
illustrated in Fig. 6. Regarding the third case, the optimal action in state
$\underline{s}=(\delta,0,1,0,0,\star,\star)$ is to stay idle ($a=0$),
regardless of the current value of the AoI. This stems from the perfect
knowledge on the system’s occupancy; see Remark 1. As the controller will
immediately know when the reverse link server becomes empty, it can send a new
request message just in time, should this action be optimal. The second case
is elaborated next.

Interestingly, we observe in Fig. 8 that in states
${\underline{s}=(\delta,0,0,0,1,\star,\Delta_{\mathrm{s}})}$, the optimal
policy has a threshold with respect to the age $\Delta_{\mathrm{s}}$ of the
packet at the sampler server. This behavior can be interpreted as follows.
First, due to the memoryless property of the geometric random variable, the
average residual service time of the packet in the sampler server is
${\mathbb{E}[Y]=1/\mu}$, regardless of $\Delta_{\mathrm{s}}$. Consequently, a
newly inserted request message will lead its associated status update packet
to enter the sampler queue with the same probability, regardless of
$\Delta_{\mathrm{s}}$. Thus, when in state
${\underline{s}=(\delta,0,0,0,1,\star,\Delta_{\mathrm{s}})}$, the controller
cannot take measures to avoid queueing delays in the sampler server, which
always are detrimental to the age performance. However, the controller can
look at the value of $\Delta_{\mathrm{s}}$ to optimize its action. If the
status update packet under service has a low value of $\Delta_{\mathrm{s}}$,
it will provide large age reduction once completing service. If a new request
was sent in such state, it would, in turn, provide relatively low age
reduction, because the preceding packet set the AoI to a low value. In this
case, it is better to wait prior to sending a request, and hence the threshold
in Fig. 8. Furthermore, based on the same grounds as for Fig. 6, when the
value of $\gamma$ increases, the optimal policy induces longer waiting times
before sending a new request in state
${\underline{s}=(\delta,0,0,0,1,\star,\Delta_{\mathrm{s}})}$.

(a) $\gamma=0.4$

(b) $\gamma=0.7$

(c) $\gamma=1$

Figure 8: Structure of the optimal policy for the 2-Packet system in state
$\underline{s}=(\delta,0,0,0,1,\star,\Delta_{\mathrm{s}})$.

In practice, we select the AoI upper-bound $\bar{\Delta}$ by increasing its
value until the average AoI of an optimal policy does not change. To
illustrate this behavior, Fig. 9 shows the average AoI of an optimal policy
for the 1-Packet system as a function of $\bar{\Delta}$ for different service
rate values $\mu$ and $\gamma$. As it can be seen, if we set $\bar{\Delta}$ to
a too small value, the average AoI value will substantially change – more
precisely, decrease. In consequence, one would draw wrong conclusions about
the system’s performance. To give some numbers, the figure shows that for the
service rates $\mu=0.2,\leavevmode\nobreak\ \gamma=0.4$, an age upper-bound
value $\bar{\Delta}>45$ provides sufficient accuracy for practical purposes.
Similarly, for $\mu=0.4,\leavevmode\nobreak\ \gamma=0.4$, this saturation
point occurs for age upper-bound values $\bar{\Delta}>25$.

Figure 9: Average AoI of the optimal policy for the 1-Packet system as a
function of $\bar{\Delta}$ under different values of ${\mu}$ and ${\gamma}$.

###  VI-B Average AoI Value for Different Policies

Fig. 10 illustrates the value of the average AoI as a function of $\mu$ for
different values of $\gamma$ under the Zero-Wait-1 policy, the Zero-Wait-2
policy, and the optimal policies in the 1-Packet and 2-packet systems. As it
can be seen, the optimal policy in the 2-Packet system, in general,
outperforms the other policies, or, for certain service rates, coincides with
another policy. This is as expected, because the policy optimization is over a
set of policies for the 2-Packet system includes these other policies.

Fig. 10 shows that for ${\mu\geq\sqrt{2}/2\approx 0.7071}$, Zero-Wait-2
outperforms Zero-Wait-1 regardless of the value of $\gamma$, as shown in
Corollary 1. Moreover, we can see that for
${\mu\geq\frac{\sqrt{3}-1}{2}\approx 0.366}$, the Zero-Wait-1 policy and the
optimal policy in the 1-Packet system provide the same average AoI regardless
of the value of $\gamma$, as shown in Corollary 2.

We can also see from Fig. 10 that as $\mu$ increases, the average AoI
decreases for all policies, as expected, because the status update packets are
served faster. However, maybe a bit surprisingly, such monotonic behavior is
not seen with respect to $\gamma$; increasing the value of $\gamma$ is not
always beneficial. As it can be seen, for the low values of $\mu$, the Zero-
Wait-2 policy results in a higher average AoI value when the value of $\gamma$
increases. This occurs because a large value of $\gamma$ causes the requests
to be served too fast in relation to the sampler service rate $\mu$, leading
to queueing of update packets in the sampler buffer, deteriorating the AoI
performance.

(a) $\gamma=0.4$

(b) $\gamma=0.7$

(c) $\gamma=1$

Figure 10: Average AoI as a function of $\mu$ for different values of
$\gamma$.

##  VII Conclusions

We studied status updating under two-way delay in a discrete-time system. We
developed AoI-optimal control policies using the tools of MDPs in two
scenarios. We began with the system having at most one active request. Then,
we initiated pipelining-type status updating by studying a system having at
most two active requests. In addition, we conducted AoI analysis by deriving
closed-form expressions of the average AoI under the Zero-Wait-1, Zero-Wait-2
and Wait-1 policies which employ only the controller’s local information.

Numerical results showed that for both 1-Packet and 2-Packet systems, the
optimal policy is a threshold-type policy. In addition, it was seen that for
high values of the update service rate $\mu$, Zero-Wait-1 is an optimal policy
for the 1-Packet system, and Zero-Wait-2 is an optimal policy for the 2-Packet
system, regardless of the service rate of the controller server. Moreover, the
results showed that increasing the request message service rate $\gamma$ is
not necessarily beneficial for all policies, e.g., when the update service
rate $\mu$ is low, the average AoI under the Zero-Wait-2 policy is increasing
$\gamma$.

The interesting future work would include the study of i) optimal policies to
minimize non-linear functions of the AoI for arbitrary service time
distributions for controller and sampler servers, ii) the structure of optimal
policies in the 1-Packet and 2-Packet systems (our numerical results showed
that the optimal policies appear to have a threshold-based structure, which,
however, remains to be proven), and iii) the performance of the two-way delay
system using real-world data sets.

Figure 11: AoI as a function of time under the Zero-Wait-2 policy.

##  VIII Appendix

###  VIII-A Proof of Theorem 3

Referring to the Zero-Wait-2 AoI sample path depicted in Figure 11, we start
with the arrival of update packet $i-1$ at the sampler server and we use the
partition $\left\\{B_{i-1},{\overline{B}}_{i-1}\right\\}$ to describe what can
follow:

  * •

If ${\overline{B}}_{i-1}$, then update $i-1$ immediately goes into service at
the sampler server, starting service time $Y_{i-1}$. Request message $i$
simultaneously starts service time $X_{i}$ at the controller server.

    * –

If $X_{i}\geq Y_{i-1}$, then event ${\overline{B}}_{i}$ occurs since update
$i$ arrives at the sampler server after update $i-1$ departs. Thus, update
packet $i$ arrives at an idle sampler server and immediately starts service
time $Y_{i}$. In this case, $I_{i}=X_{i}$ and $T_{i}=Y_{i}$.

    * –

If $B_{i}=\left\\{X_{i}<Y_{i-1}\right\\}$ occurs, then update $i$ waits for
the residual service time $R_{i-1}$ of update $i-1$ before starting its own
service time $Y_{i}$. In this case, $I_{i}=X_{i}$ and $T_{i}=R_{i-1}+Y_{i}$.

  * •

If $B_{i-1}$, update $i-1$ arrives when the sampler server is busy and waits
for the residual service time $R_{i-2}$ of update $i-2$. After this waiting
time, update $i-2$ is delivered to the sink, request $i$ is generated at the
controller and starts service time $X_{i}$, and update $i-1$ simultaneously
starts service time $Y_{i-1}$ at the sampler server.

    * –

If ${\overline{B}}_{i}=\left\\{X_{i}\geq Y_{i-1}\right\\}$ occurs, update
packet $i$ arrives at an empty sampler server and immediately starts service
time $Y_{i}$. In this case, $I_{i}=R_{i-2}+X_{i}$ and $T_{i}=Y_{i}$.

    * –

If $B_{i}=\left\\{X_{i}<Y_{i-1}\right\\}$ occurs, update $i$ arrives at the
sampler server before update $i-1$ departs. In this case, update $i$ waits at
the sampler server for the residual service time $R_{i-1}$ of update $i-1$,
implying $I_{i}=R_{i-2}+X_{i}$ and $T_{i}=R_{i-1}+Y_{i}$.

To summarize this two-step partitioning, we see that

$\displaystyle\text{if ${\overline{B}}_{i-1}{\overline{B}}_{i}$:}\quad I_{i}$
$\displaystyle=X_{i},$ $\displaystyle T_{i}$ $\displaystyle=Y_{i};$ (38a)
$\displaystyle\text{if ${\overline{B}}_{i-1}B_{i}$:}\quad I_{i}$
$\displaystyle=X_{i},$ $\displaystyle T_{i}$ $\displaystyle=R_{i-1}+Y_{i};$
(38b) $\displaystyle\text{if $B_{i-1}{\overline{B}}_{i}$:}\quad I_{i}$
$\displaystyle=R_{i-2}+X_{i},$ $\displaystyle T_{i}$ $\displaystyle=Y_{i};$
(38c) $\displaystyle\text{if $B_{i-1}B_{i}$:}\quad I_{i}$
$\displaystyle=R_{i-2}+X_{i},$ $\displaystyle T_{i}$
$\displaystyle=R_{i-1}+Y_{i}.$ (38d)

Note that the memoryless property of geometric random variables implies that
conditioned on $B_{j}$, each $R_{j-1}$ is a geometric $(\mu)$ random variable,
independent of all $X_{i}$ and $\left\\{Y_{i}\colon i\neq j-1\right\\}$.

Furthermore, careful reading of this two-step partitioning shows that $B_{i}$
and $B_{i-1}$ are independent events since
${B_{i}=\left\\{X_{i}<Y_{i-1}\right\\}}$, whether
${B_{i-1}=\left\\{X_{i-1}<Y_{i-2}\right\\}}$ occurred or not in the prior
cycle. Since the $X_{i}$ and $Y_{i}$ sequences are independent (and iid within
each sequence),

$\displaystyle\Pr\left\lparen B_{i}\right\rparen=\Pr\left\lparen
B_{i}|B_{i-1}\right\rparen=\Pr\left\lparen X_{i}<Y_{i-1}\right\rparen.$ (39)

We further observe that the occurrence of $B_{i}$ suggests that $X_{i}$ is
shorter than usual. In Appendix VIII-B, we verify the following properties.

######  Lemma 6.

In the Zero-Wait-2 system:

  1. (a)

Update $i$ arrives at a busy sampler server with probability

$\Pr\left\lparen
B_{i}\right\rparen=P_{B}\triangleq\Pr(X_{i}<Y_{i-1})=\displaystyle\frac{\gamma\bar{\mu}}{\mu+\gamma\bar{\mu}}.$
(40a)

  2. (b)

Given event $B_{i}$,

$\operatorname{\mathbb{E}}\left[X_{i}|B_{i}\right]=\frac{1}{\mu+\gamma\bar{\mu}}=\frac{P_{B}}{\gamma\bar{\mu}}.$
(40b)

Since (38) shows that $I_{i}$ depends only on the partition
$\left\\{B_{i-1},{\overline{B}}_{i-1}\right\\}$, it follows from the law of
total expectation that

$\displaystyle\operatorname{\mathbb{E}}\left[I_{i}\right]=\operatorname{\mathbb{E}}\left[I_{i}|{\overline{B}}_{i-1}\right]\Pr\left\lparen{\overline{B}}_{i-1}\right\rparen+\operatorname{\mathbb{E}}\left[I_{i}|B_{i-1}\right]\Pr\left\lparen
B_{i-1}\right\rparen$
$\displaystyle=\operatorname{\mathbb{E}}\left[X_{i}|{\overline{B}}_{i-1}\right]\Pr\left\lparen{\overline{B}}_{i-1}\right\rparen+\operatorname{\mathbb{E}}\left[R_{i-2}+X_{i}|B_{i-1}\right]\Pr\left\lparen
B_{i-1}\right\rparen$
$\displaystyle=\operatorname{\mathbb{E}}\left[X_{i}\right]+\operatorname{\mathbb{E}}\left[R_{i-2}|B_{i-1}\right]\Pr\left\lparen
B_{i-1}\right\rparen$ $\displaystyle=\frac{1}{\gamma}+\frac{P_{B}}{\mu}.$ (41)

Similarly for the second moment,

$\displaystyle\operatorname{\mathbb{E}}\left[I_{i}^{2}\right]$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}\left[I^{2}_{i}|{\overline{B}}_{i-1}\right]\Pr\left\lparen{\overline{B}}_{i-1}\right\rparen+\operatorname{\mathbb{E}}\left[I^{2}_{i}|B_{i-1}\right]\Pr\left\lparen
B_{i-1}\right\rparen$ (42) $\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}\left[X_{i}^{2}|{\overline{B}}_{i-1}\right]\Pr\left\lparen{\overline{B}}_{i-1}\right\rparen$
$\displaystyle\quad+\operatorname{\mathbb{E}}\left[R_{i-2}^{2}+2X_{i}R_{i-2}+X_{i}^{2}|B_{i-1}\right]\Pr\left\lparen
B_{i-1}\right\rparen$ $\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}\left[X^{2}_{i}\right]+\operatorname{\mathbb{E}}\left[R_{i-2}^{2}+2X_{i}R_{i-2}|B_{i-1}\right]\Pr\left\lparen
B_{i-1}\right\rparen.$

Since $X_{i}$ is geometric $(\gamma)$, independent of the event $B_{i-1}$, and
$R_{i-1}$ is geometric $(\mu)$ given $B_{i-1}$, it follows from (41) and (42)
that

$\displaystyle\operatorname{\mathbb{E}}\left[I_{i}^{2}\right]$
$\displaystyle=\frac{2-\gamma}{\gamma^{2}}+\left\lparen\frac{2-\mu}{\mu^{2}}+\frac{2}{\gamma\mu}\right\rparen
P_{B}$
$\displaystyle=\left\lparen\frac{2}{\gamma}-1\right\rparen\left\lparen\frac{1}{\gamma}+\frac{P_{B}}{\mu}\right\rparen+2\frac{P_{B}}{\mu^{2}}$
$\displaystyle=\left\lparen\frac{2}{\gamma}-1\right\rparen\operatorname{\mathbb{E}}\left[I\right]+2\frac{P_{B}}{\mu^{2}}.$
(43)

We employ the partition
$\left\\{{\overline{B}}_{i-1}{\overline{B}}_{i},{\overline{B}}_{i-1}B_{i},B_{i-1}{\overline{B}}_{i},B_{i-1}B_{i}\right\\}$
and the law of total expectation to evaluate

$\displaystyle\operatorname{\mathbb{E}}\left[I_{i}T_{i}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[I_{i}T_{i}|{\overline{B}}_{i-1}{\overline{B}}_{i}\right]\Pr\left\lparen{\overline{B}}_{i-1}{\overline{B}}_{i}\right\rparen$
$\displaystyle\qquad+\operatorname{\mathbb{E}}\left[I_{i}T_{i}|{\overline{B}}_{i-1}B_{i}\right]\Pr\left\lparen{\overline{B}}_{i-1}B_{i}\right\rparen$
$\displaystyle\qquad+\operatorname{\mathbb{E}}\left[I_{i}T_{i}|B_{i-1}{\overline{B}}_{i}\right]\Pr\left\lparen
B_{i-1}{\overline{B}}_{i}\right\rparen$
$\displaystyle\qquad+\operatorname{\mathbb{E}}\left[I_{i}T_{i}|B_{i-1}B_{i}\right]\Pr\left\lparen
B_{i-1}B_{i}\right\rparen.$ (44)

It follows from (38) and the law of total expectation that

$\displaystyle\mathrlap{\operatorname{\mathbb{E}}\left[I_{i}T_{i}\right]}$
(46) $\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}\left[X_{i}Y_{i}|{\overline{B}}_{i-1}{\overline{B}}_{i}\right]\Pr\left\lparen{\overline{B}}_{i-1}{\overline{B}}_{i}\right\rparen$
$\displaystyle+\operatorname{\mathbb{E}}\left[X_{i}(R_{i-1}+Y_{i})|{\overline{B}}_{i-1}B_{i}\right]\Pr\left\lparen{\overline{B}}_{i-1}B_{i}\right\rparen$
$\displaystyle+\operatorname{\mathbb{E}}\left[(R_{i-2}+X_{i})Y_{i}|B_{i-1}{\overline{B}}_{i}\right]\Pr\left\lparen
B_{i-1}{\overline{B}}_{i}\right\rparen$
$\displaystyle+\operatorname{\mathbb{E}}\left[(R_{i-2}+X_{i})(R_{i-1}+Y_{i})|B_{i-1}B_{i}\right]\Pr\left\lparen
B_{i-1}B_{i}\right\rparen$ $\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}\left[X_{i}Y_{i}\right]+\operatorname{\mathbb{E}}\left[R_{i-1}X_{i}|{\overline{B}}_{i-1}B_{i}\right]\Pr\left\lparen{\overline{B}}_{i-1}B_{i}\right\rparen$
$\displaystyle+\operatorname{\mathbb{E}}\left[R_{i-2}Y_{i}|B_{i-1}{\overline{B}}_{i}\right]\Pr\left\lparen
B_{i-1}{\overline{B}}_{i}\right\rparen$
$\displaystyle+\operatorname{\mathbb{E}}\left[R_{i-2}(R_{i-1}\\!+\\!Y_{i})\\!+\\!R_{i-1}X_{i}|B_{i-1}B_{i}\right]\Pr\left\lparen
B_{i-1}B_{i}\right\rparen.$

Note that $Y_{i}$ is independent of $B_{i-1}$ and $B_{i}$ while $X_{i}$ is
independent of $B_{i-1}$ but influenced by the occurrence of $B_{i}$. Since
$\operatorname{\mathbb{E}}\left[X_{i}Y_{i}\right]=1/(\gamma\mu)$, it follows
from (46) that

$\displaystyle\operatorname{\mathbb{E}}\left[I_{i}T_{i}\right]$
$\displaystyle=\frac{1}{\gamma\mu}+\frac{\operatorname{\mathbb{E}}\left[X_{i}|B_{i}\right]\Pr\left\lparen{\overline{B}}_{i-1}B_{i}\right\rparen}{\mu}+\frac{\Pr\left\lparen
B_{i-1}{\overline{B}}_{i}\right\rparen}{\mu^{2}}$
$\displaystyle\qquad+\left\lparen\frac{1}{\mu^{2}}+\frac{1}{\mu^{2}}+\frac{\operatorname{\mathbb{E}}\left[X_{i}|B_{i}\right]}{\mu}\right\rparen\Pr\left\lparen
B_{i-1}B_{i}\right\rparen$ (47)
$\displaystyle=\frac{1}{\gamma\mu}+\frac{2\Pr\left\lparen
B_{i-1}B_{i}\right\rparen+\Pr\left\lparen
B_{i-1}{\overline{B}}_{i}\right\rparen}{\mu^{2}}$
$\displaystyle\qquad+\frac{\operatorname{\mathbb{E}}\left[X_{i}|B_{i}\right](\Pr\left\lparen{\overline{B}}_{i-1}B_{i}\right\rparen+\Pr\left\lparen
B_{i-1}B_{i}\right\rparen)}{\mu}$ (48)
$\displaystyle=\frac{1}{\gamma\mu}+\frac{\Pr\left\lparen
B_{i-1}B_{i}\right\rparen+\Pr\left\lparen
B_{i-1}\right\rparen}{\mu^{2}}+\frac{\operatorname{\mathbb{E}}\left[X_{i}|B_{i}\right]P_{B}}{\mu}$
$\displaystyle=\frac{1}{\gamma\mu}+\frac{P_{B}(1+P_{B})}{\mu^{2}}+\frac{\operatorname{\mathbb{E}}\left[X_{i}|B_{i}\right]P_{B}}{\mu}.$
(49)

Applying Lemma 6 to (49) yields

$\displaystyle\operatorname{\mathbb{E}}\left[I_{i}T_{i}\right]$
$\displaystyle=\frac{1}{\gamma\mu}+\frac{P_{B}(1+P_{B})}{\mu^{2}}+\frac{P_{B}^{2}}{\gamma\mu\bar{\mu}}$
$\displaystyle=\frac{1}{\mu}\left\lparen\frac{1}{\gamma}+\frac{P_{B}}{\mu}\right\rparen+\frac{P_{B}^{2}}{\mu}\left\lparen\frac{1}{\mu}+\frac{1}{\gamma\bar{\mu}}\right\rparen$
$\displaystyle=\frac{\operatorname{\mathbb{E}}\left[I_{i}\right]}{\mu}+\frac{P_{B}^{2}}{\mu}\left\lparen\frac{1}{\mu}+\frac{1}{\gamma\bar{\mu}}\right\rparen$
$\displaystyle=\frac{\operatorname{\mathbb{E}}\left[I_{i}\right]}{\mu}+\frac{P_{B}^{2}}{\mu}\left\lparen\frac{\mu+\gamma\bar{\mu}}{\gamma\mu\bar{\mu}}\right\rparen=\frac{\operatorname{\mathbb{E}}\left[I_{i}\right]}{\mu}+\frac{P_{B}}{\mu^{2}}.$
(50)

Combining (7), (43) and (50), we obtain

$\displaystyle\Delta^{\text{Zero-Wait-{2}}}$
$\displaystyle=\frac{1}{\gamma}+\frac{1}{\mu}-1+2\frac{P_{B}}{\mu^{2}\operatorname{\mathbb{E}}\left[I\right]}.$
(51)

Applying Lemma 6(a) and (41) yields Theorem 3.

###  VIII-B Proof of Lemma 6

(a) The probability of event $B_{i}=\left\\{X_{i}<Y_{i-1}\right\\}$ is

$\displaystyle P_{B}$ $\displaystyle=\sum_{j=1}^{\infty}\Pr(X_{i}<Y_{i-1}\mid
X_{i}=j)\Pr(X_{i}=j)$
$\displaystyle\overset{(a)}{=}\sum_{j=1}^{\infty}\bar{\mu}^{j}\gamma\bar{\gamma}^{j-1}=\frac{\gamma}{\bar{\gamma}}\sum_{j=1}^{\infty}\big{(}\bar{\mu}\bar{\gamma}\big{)}^{j}\overset{(b)}{=}\dfrac{\gamma\bar{\mu}}{\mu+\gamma\bar{\mu}}.$
(52)

where $(a)$ holds because ${\Pr\left\lparen
X_{i}=j\right\rparen=\gamma\bar{\gamma}^{j-1}}$ and $\Pr\left\lparen
j<Y_{i-1}\right\rparen=\bar{\mu}^{j}$, and step $(b)$ follows from the
identities $\sum_{j=1}^{\infty}a^{j}={a}/{(1-a)}$ for $\left\lvert
a\right\rvert<1$, and $1-\bar{\mu}\bar{\gamma}=\mu+\gamma\bar{\mu}$.

(b) For the conditional expectation, similar facts imply

$\displaystyle\operatorname{\mathbb{E}}\left[X_{i}|B_{i}\right]$
$\displaystyle=\sum_{j=1}^{\infty}j\Pr\left\lparen
X_{i}=j|X_{i}<Y_{i-1}\right\rparen$
$\displaystyle=\frac{1}{P_{B}}\sum_{j=1}^{\infty}j\Pr\left\lparen
X_{i}=j,Y_{i-1}>j\right\rparen$
$\displaystyle=\frac{1}{P_{B}}\sum_{j=1}^{\infty}j\bar{\gamma}^{j-1}\gamma\bar{\mu}^{j}$
$\displaystyle=\frac{\gamma\bar{\mu}}{P_{B}(1-\bar{\gamma}\bar{\mu})}\sum_{j=1}^{\infty}j(\bar{\gamma}\bar{\mu})^{j-1}(1-\bar{\gamma}\bar{\mu})$
$\displaystyle=\frac{1}{1-\bar{\gamma}\bar{\mu}}=\frac{1}{\mu+\gamma\bar{\mu}}=\frac{P_{B}}{\gamma\bar{\mu}}.$
(53)

###  VIII-C Proof of Lemma 2

The mean waiting time $\mathbb{E}[Z_{i}]$ is derived as

$\displaystyle\mathbb{E}[Z_{i}]$
$\displaystyle=\displaystyle\sum_{j=1}^{\infty}j\Pr(Z_{i}=j)\overset{(a)}{=}\displaystyle\sum_{j=1}^{\beta-1}(\beta-j)\Pr(Y_{i-1}=j)$
$\displaystyle\overset{}{=}\displaystyle\beta\sum_{j=1}^{\beta-1}\bar{\mu}^{j-1}\mu-\sum_{j=1}^{\beta-1}j\bar{\mu}^{j-1}\mu$
$\displaystyle=\displaystyle\frac{\beta\mu}{\bar{\mu}}\sum_{j=1}^{\beta-1}\bar{\mu}^{j}-\frac{\mu}{\bar{\mu}}\sum_{j=1}^{\beta-1}j\bar{\mu}^{j}\overset{(b)}{=}\displaystyle\frac{1}{\mu}\left(\beta\mu+\bar{\mu}^{\beta}-1\right),$
(54)

where $(a)$ follows from ${Z_{i}=f(Y_{i-1})=(\beta-Y_{i-1})^{+}}$ and $(b)$
follows from the identities [74, Page 484]

$\displaystyle\sum_{j=1}^{m}\alpha^{j}$
$\displaystyle=\dfrac{\alpha(1-\alpha^{m})}{1-\alpha},$ (55)
$\displaystyle\sum_{j=1}^{m}j\alpha^{j}$
$\displaystyle=\dfrac{\alpha(1-\alpha^{m}(1+m(1-\alpha)))}{(1-\alpha)^{2}}.$
(56)

###  VIII-D Proof of Lemma 3

Since (27) implies $\Pr(Z_{i}=k\mid Y_{i-1}=j)=1_{\\{k=(\beta-j)^{+}\\}}$,

$\displaystyle\operatorname{\mathbb{E}}\left[Z_{i}Y_{i-1}\right]$
$\displaystyle=\sum_{j=1}^{\infty}\sum_{k=1}^{\infty}jk\Pr(Y_{i-1}=j)\Pr(Z_{i}=k\mid
Y_{i-1}=j)$ $\displaystyle=\sum_{j=1}^{\beta-1}j(\beta-j)\Pr(Y_{i-1}=j).$ (57)

This implies

$\displaystyle\operatorname{\mathbb{E}}\left[Z_{i}Y_{i-1}\right]$
$\displaystyle=\beta\sum_{j=1}^{\beta-1}j\bar{\mu}^{j-1}\mu-\sum_{j=1}^{\beta-1}j^{2}\bar{\mu}^{j-1}\mu$
$\displaystyle=\frac{\beta\mu}{\bar{\mu}}\sum_{j=1}^{\beta-1}j\bar{\mu}^{j}-\frac{\mu}{\bar{\mu}}\sum_{j=1}^{\beta-1}j^{2}\bar{\mu}^{j}$
$\displaystyle\overset{(a)}{=}\displaystyle\frac{1}{\mu^{2}}\left(\mu(1+\beta)+\bar{\mu}^{\beta}(2-\mu+\beta\mu)-2\right),$
(58)

where $(a)$ follows from (56) and the identity

$\displaystyle\sum_{j=1}^{m}j^{2}\alpha^{j}$
$\displaystyle=\dfrac{\alpha^{2}+\alpha+\alpha^{m+2}(2m^{2}+2m-1)}{(1-\alpha)^{3}}$
$\displaystyle\qquad-\frac{\alpha^{m+1}[(m+1)^{2}+m^{2}\alpha^{2}]}{(1-\alpha)^{3}}.$
(59)

Note that (59) can be verified by taking derivatives with respect to $\alpha$
of both sides of (56).

###  VIII-E Proof of Lemma 4

It follows from (27) that

$\displaystyle\mathbb{E}[Z_{i}^{2}]=\displaystyle\sum_{j=1}^{\infty}j^{2}\Pr(Z_{i}=j)\overset{(a)}{=}\displaystyle\sum_{j=1}^{\beta-1}(\beta-j)^{2}\Pr(Y_{i-1}=j)$
$\displaystyle\overset{}{=}\displaystyle\beta^{2}\sum_{j=1}^{\beta-1}\bar{\mu}^{j-1}\mu-2\beta\sum_{j=1}^{\beta-1}j\bar{\mu}^{j-1}\mu\sum_{j=1}^{\beta-1}j^{2}\bar{\mu}^{j-1}\mu$
$\displaystyle\overset{(a)}{=}\displaystyle-\frac{1}{\mu^{2}}\left(\mu(1+2\beta)+\bar{\mu}^{\beta}(2-\mu)-\beta^{2}\mu^{2}-2\right).$
(60)

Note that $(a)$ follows from (55), (56), and (59).

###  VIII-F Proof of Lemma 5

Let $\beta^{*}$ denote the optimal $\beta$ for the Wait-1 policy. To find an
upper bound on $\beta^{*}$, we observe that the Wait-1 policy with $\beta^{*}$
results in an average AoI not greater than that of the Zero-Wait-1 policy.
Thus $\beta^{*}$ satisfies the following inequality

$\displaystyle\Delta^{\text{Zero-
Wait-{1}}}-\Delta^{\text{Wait-1}}(\beta^{*})\geq 0,$ (61)

where $\Delta^{\text{Wait-1}}(\beta^{*})$ represents the average AoI under the
Wait-1 policy with ${\beta=\beta^{*}}$. By substituting the expressions for
$\Delta^{\text{Zero-Wait-{1}}}$ in (24) and
$\Delta^{\text{Wait-1}}(\beta^{*})$ in (34) into (61), some algebra shows that
$\beta^{*}$ must satisfy the constraint

$\displaystyle
q(\beta^{*})+\bar{\mu}^{\beta^{*}}[2\beta^{*}(\mu+\gamma)+2]\leq 0,$ (62)

where $q(\beta)$ denotes the quadratic function

$\displaystyle q(\beta)$
$\displaystyle\equiv\beta^{2}(\mu^{2}+\gamma\mu)+\beta(\mu^{2}+\gamma\mu-2\gamma)-2.$
(63)

We observe that $q(0)=-2$ and that $q(\beta)>0$ for sufficiently large
$\beta$. Since the term $\bar{\mu}^{\beta^{*}}[2\beta^{*}(\mu+\gamma)+2]$ on
the left side of (62) is positive, it follows from (62) that $\beta^{*}$ must
satisfy $\beta^{*}\leq\beta^{\max}$ where $\beta^{\max}$ is the maximum value
of $\beta$ satisfying $q(\beta)\leq 0$. With $a=\mu^{2}+\gamma\mu$, the
quadratic formula implies

$\displaystyle\beta^{\max}$ $\displaystyle=$
$\displaystyle\dfrac{2\gamma-a+\sqrt{(a-2\gamma)^{2}+8a}}{2a}.$ (64)

The claim follows with substitution of $a$ and the observation that
$\beta^{*}$ is an integer.

## References

  * [1] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of information in vehicular networks,” in _Proc. Commun. Society. Conf. on Sensor, Mesh and Ad Hoc Commun. and Net._ , Salt Lake City, UT, USA, Jun. 27–30, 2011, pp. 350–358.
  * [2] Y. Sun, I. Kadota, R. Talak, and E. Modiano, _Age of Information: A New Metric For Information Freshness_. Synthesis Lectures on Communication Networks, 2019, vol. 12, no. 2.
  * [3] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” _IEEE J. Select. Areas Commun._ , vol. 39, no. 5, pp. 1183–1210, 2021.
  * [4] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _Proc. IEEE Int. Conf. on Computer. Commun. (INFOCOM)_ , Orlando, FL, USA, Mar. 25–30, 2012, pp. 2731–2735.
  * [5] R. D. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Hong Kong, China, Jun. 14–19, 2015, pp. 3008–3012.
  * [6] 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. Inform. Theory_ , vol. 63, no. 11, pp. 7492–7508, 2017.
  * [7] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,” _IEEE Trans. Inform. Theory_ , vol. 62, no. 4, pp. 1897–1910, Apr. 2016.
  * [8] S. K. Kaul, R. D. Yates, and M. Gruteser, “Status updates through queues,” in _Proc. Conf. Inform. Sciences Syst. (CISS)_ , Princeton, NJ, USA, Mar. 21–23, 2012, pp. 1–6.
  * [9] K. Chen and L. Huang, “Age-of-information in the presence of error,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Barcelona, Spain, Jul. 10–15, 2016, pp. 2579–2583.
  * [10] A. Soysal and S. Ulukus, “Age of information in G/G/1/1 systems,” in _Proc. Annual Asilomar Conf. Signals, Syst., Comp._ , Pacific Grove, CA, USA, Nov. 3–6, 2019, pp. 2022–2027.
  * [11] C. Kam, S. Kompella, G. D. Nguyen, and A. Ephremides, “Effect of message transmission path diversity on status age,” _IEEE Trans. Inform. Theory_ , vol. 62, no. 3, pp. 1360–1374, Dec. 2016.
  * [12] R. D. Yates and S. Kaul, “Real-time status updating: Multiple sources,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Cambridge, MA, USA, Jul. 1–6, 2012, pp. 2666–2670.
  * [13] N. Akar, O. Dogan, and E. U. Atay, “Finding the exact distribution of (peak) age of information for queues of PH/PH/1/1 and M/PH/1/2 type,” _IEEE Trans. Commun._ , vol. 68, no. 9, pp. 5661–5672, Jun. 2020.
  * [14] J. P. Champati, H. Al-Zubaidy, and J. Gross, “Statistical guarantee optimization for age of information for the D/G/1 queue,” in _Proc. IEEE Int. Conf. on Computer. Commun. (INFOCOM) Workshop_ , Honolulu, HI, USA, Apr. 15–19, 2018, pp. 130–135.
  * [15] E. Najm, R. Yates, and E. Soljanin, “Status updates through M/G/1/1 queues with HARQ,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Aachen, Germany, Jun. 25–30 2017, pp. 131–135.
  * [16] 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. Inform. Theory_ , vol. 65, no. 12, pp. 8305–8324, 2019.
  * [17] A. Soysal and S. Ulukus, “Age of information in G/G/1/1 systems: Age expressions, bounds, special cases, and optimization,” [Online]: https://arxiv.org/abs/1905.13743, 2019.
  * [18] B. Buyukates, A. Soysal, and S. Ulukus, “Age of information in multicast networks with multiple update streams,” in _Proc. Annual Asilomar Conf. Signals, Syst., Comp._ , Pacific Grove, CA, USA,, Nov. 3–6 2019, pp. 1977–1981.
  * [19] L. Huang and E. Modiano, “Optimizing age-of-information in a multi-class queueing system,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Hong Kong, China, Jun. 14–19, 2015, pp. 1681–1685.
  * [20] E. Najm, R. Nasser, and E. Telatar, “Content based status updates,” _IEEE Trans. Inform. Theory_ , vol. 66, no. 6, pp. 3846–3863, Oct. 2020.
  * [21] J. Hespanha, “Modelling and analysis of stochastic hybrid systems,” _IEE Proc. - Control Theory and Appl._ , vol. 153, pp. 520–535, Sep. 2006.
  * [22] R. D. Yates and S. K. Kaul, “The age of information: Real-time status updating by multiple sources,” _IEEE Trans. Inform. Theory_ , vol. 65, no. 3, pp. 1807–1827, Mar. 2019.
  * [23] R. D. Yates, “The age of information in networks: Moments, distributions, and sampling,” _IEEE Trans. Inform. Theory_ , vol. 66, no. 9, pp. 5712–5728, May 2020.
  * [24] S. K. Kaul and R. D. Yates, “Age of information: Updates with priority,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Vail, CO, USA, Jun. 17–22, 2018, pp. 2644–2648.
  * [25] R. D. Yates, “Age of information in a network of preemptive servers,” in _Proc. IEEE Int. Conf. on Computer. Commun. (INFOCOM)_ , Honolulu, HI, USA, Apr. 15–19 2018, pp. 118–123.
  * [26] ——, “Status updates through networks of parallel servers,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Vail, CO, USA, Jun. 17–22, 2018, pp. 2281–2285.
  * [27] A. Javani, M. Zorgui, and Z. Wang, “Age of information in multiple sensing,” in _Proc. IEEE Global Telecommun. Conf._ , Waikoloa, HI, USA, Dec. 9–13, 2019.
  * [28] S. Farazi, A. G. Klein, and D. Richard Brown, “Average age of information in multi-source self-preemptive status update systems with packet delivery errors,” in _Proc. Annual Asilomar Conf. Signals, Syst., Comp._ , Pacific Grove, CA, USA, Nov. 2019, pp. 396–400.
  * [29] M. Moltafet, M. Leinonen, and M. Codreanu, “Average AoI in multi-source systems with source-aware packet management,” _IEEE Trans. Commun._ , vol. 69, no. 2, pp. 1121–1133, Feb. 2021.
  * [30] M. Moltafet, M. Leinonen, and M. Codreanu, “Average age of information in a multi-source M/M/1 queueing model with LCFS prioritized packet management,” in _Proc. IEEE Int. Conf. on Computer. Commun. (INFOCOM) Workshop_ , Toronto, Canada, Jul. 6–9, 2020, pp. 303–308.
  * [31] M. Moltafet, M. Leinonen, and M. Codreanu, “Moment generating function of the AoI in a two-source system with packet management,” _IEEE Wireless Commun. Lett._ , vol. 10, no. 4, pp. 882–886, Apr. 2021.
  * [32] ——, “Average age of information for a multi-source M/M/1 queueing model with packet management,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Los Angeles, CA, USA, Jun. 21–26 2020, pp. 1765–1769.
  * [33] ——, “Source-aware packet management for computation-intensive status updating: MGF of the AoI,” in _Proc. Int. Symp. Wireless Commun. Systems_ , Berlin, Germany, Sep. 6–9 2021, pp. 1–6.
  * [34] M. A. Abd-Elmagid and H. S. Dhillon, “Closed-form characterization of the MGF of AoI in energy harvesting status update systems,” 2021. [Online]. Available: https://arxiv.org/abs/2105.07074
  * [35] M. Moltafet, M. Leinonen, and M. Codreanu, “Moment generating function of the AoI in multi-source systems with computation-intensive status updates,” in _Proc. IEEE Inform. Theory Workshop_ , Kanazawa, Japan, Oct. 17–21, 2021, pp. 1–6.
  * [36] N. Pappas, J. Gunnarsson, L. Kratz, M. Kountouris, and V. Angelakis, “Age of information of multiple sources with queue management,” in _Proc. IEEE Int. Conf. Commun._ , London, UK, Jun.8–12 2015, pp. 5935–5940.
  * [37] A. Kosta, N. Pappas, A. Ephremides, and V. Angelakis, “Age of information performance of multiaccess strategies with packet management,” _J. Commun. Netw._ , vol. 21, no. 3, pp. 244–255, 2019.
  * [38] M. Moradian and A. Dadlani, “Age of information in scheduled wireless relay networks,” in _Proc. IEEE Wireless Commun. and Networking Conf._ , Seoul, Korea, May25–28 2020, pp. 1–6.
  * [39] A. Kosta, N. Pappas, A. Ephremides, and V. Angelakis, “Non-linear age of information in a discrete time queue: Stationary distribution and average performance analysis,” in _Proc. IEEE Int. Conf. Commun._ , Dublin, Ireland, Jun.7–11 2020, pp. 1–6.
  * [40] J. Zhang and Y. Xu, “On age of information for discrete time status updating system with Ber/G/1/1 queues,” in _Proc. IEEE Inform. Theory Workshop_ , Kanazawa, Japan, Oct. 17–21 2021, pp. 1–6.
  * [41] D. Qiao and M. C. Gursoy, “Age-optimal power control for status update systems with packet-based transmissions,” _IEEE Wireless Commun. Lett._ , vol. 8, no. 6, pp. 1604–1607, Jul. 2019.
  * [42] R. V. Bhat, R. Vaze, and M. Motani, “Throughput maximization with an average age of information constraint in fading channels,” [Online]. https://arxiv.org/pdf/1911.07499.pdf, 2019.
  * [43] R. Talak, S. Karaman, and E. Modiano, “Optimizing information freshness in wireless networks under general interference constraints,” _IEEE/ACM Trans. Net._ , vol. 28, no. 1, pp. 15–28, Dec. 2019.
  * [44] A. E. Kalor and P. Popovski, “Minimizing the age of information from sensors with common observations,” _IEEE Wireless Commun. Lett._ , vol. 8, no. 5, pp. 1390–1393, May 2019.
  * [45] B. Yu, Y. Cai, and D. Wu, “Joint access control and resource allocation for short-packet-based mMTC in status update systems,” _IEEE J. Select. Areas Commun._ , Early Access, 2020.
  * [46] Y. Gu, Q. Wang, H. Chen, Y. Li, and B. Vucetic, “Optimizing information freshness in two-hop status update systems under a resource constraint,” https://arxiv.org/abs/2007.02531, 2020.
  * [47] Z. Qian, F. Wu, J. Pan, K. Srinivasan, and N. B. Shroff, “Minimizing age of information in multi-channel time-sensitive information update systems,” in _Proc. IEEE Int. Conf. on Computer. Commun. (INFOCOM)_ , Toronto, ON, Canada,, Jul. 6–9 2020, pp. 446–455.
  * [48] Y. Sun and B. Cyr, “Information aging through queues: A mutual information perspective,” in _Proc. IEEE Works. on Sign. Proc. Adv. in Wirel. Comms._ , Kalamata, Greece, Jun. 25–28, 2018, pp. 1–5.
  * [49] Y. Sun and B. Cyr, “Sampling for data freshness optimization: Non-linear age functions,” _Journal of Communications and Networks_ , vol. 21, no. 3, pp. 204–219, 2019.
  * [50] A. M. Bedewy, Y. Sun, S. Kompella, and N. B. Shroff, “Optimal sampling and scheduling for timely status updates in multi-source networks,” _IEEE Trans. Inform. Theory_ , vol. 67, no. 6, pp. 4019–4034, 2021.
  * [51] Z. Chen, N. Pappas, E. Björnson, and E. G. Larsson, “Optimizing information freshness in a multiple access channel with heterogeneous devices,” _IEEE Open Journal Comm. Soc._ , vol. 2, pp. 456–470, 2021.
  * [52] E. T. Ceran, D. Gündüz, and A. György, “Average age of information with hybrid ARQ under a resource constraint,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 3, pp. 1900–1913, 2019.
  * [53] M. Moltafet, M. Leinonen, M. Codreanu, and N. Pappas, “Power minimization for age of information constrained dynamic control in wireless sensor networks,” _IEEE Trans. Commun._ , vol. 70, no. 1, pp. 419–432, 2022.
  * [54] A. Zakeri, M. Moltafet, M. Leinonen, and M. Codreanu, “Dynamic scheduling for minimizing AoI in resource-constrained multi-source relaying systems with stochastic arrivals,” 2022. [Online]. Available: https://arxiv.org/abs/2203.05656
  * [55] C.-H. Tsai and C.-C. Wang, “Unifying AoI minimization and remote estimation—optimal sensor/controller coordination with random two-way delay,” _IEEE/ACM Trans. Networking_ , vol. 30, no. 1, pp. 229–242, 2022.
  * [56] J. Pan, A. M. Bedewy, Y. Sun, and N. B. Shroff, “Optimal sampling for data freshness: Unreliable transmissions with random two-way delay.” [Online]. Available: https://arxiv.org/abs/2201.02929
  * [57] C.-C. Wang, “How useful is delayed feedback in AoI minimization — A study on systems with queues in both forward and backward directions,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Helsinki, Finland, Jun.26–30 2022, pp. 3192–3197.
  * [58] Z. Liu, B. Li, Z. Zheng, Y. T. Hou, and B. Ji, “Towards optimal tradeoff between data freshness and update cost in information update systems,” in _Proc. Int. Conf. on Computer. Commun. and Net. (ICCCN)_ , Honolulu, HI, USA, Jul.25–28 2022, pp. 1–10.
  * [59] B. T. Bacinoglu and E. Uysal-Biyikoglu, “Scheduling status updates to minimize age of information with an energy harvesting sensor,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Aachen, Germany, Jun. 25–30, 2017.
  * [60] S. Feng and J. Yang, “Optimal status updating for an energy harvesting sensor with a noisy channel,” in _Proc. IEEE Int. Conf. on Computer. Commun. (INFOCOM) Workshop_ , Honolulu, HI, USA, Apr. 15–19 2018, pp. 348–353.
  * [61] B. T. Bacinoglu, Y. Sun, E. Uysal Bivikoglu, and V. Mutlu, “Achieving the age-energy tradeoff with a finite-battery energy harvesting source,” in _Proc. IEEE Int. Symp. Inform. Theory_ , Vail, CO, USA, Jun. 2018, pp. 876–880.
  * [62] X. Wu, J. Yang, and J. Wu, “Optimal status update for age of information minimization with an energy harvesting source,” _IEEE Trans. Green Commun. Net._ , vol. 2, no. 1, pp. 193–204, Mar. 2018.
  * [63] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor, “Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies,” _IEEE Trans. Inform. Theory_ , vol. 66, no. 1, pp. 534–556, Sep. 2020.
  * [64] I. Krikidis, “Average age of information in wireless powered sensor networks,” _IEEE Wireless Commun. Lett._ , vol. 8, no. 2, pp. 628–631, Apr. 2019.
  * [65] M. Hatami, M. Leinonen, and M. Codreanu, “AoI minimization in status update control with energy harvesting sensors,” _IEEE Trans. Commun._ , vol. 69, no. 12, pp. 8335–8351, 2021.
  * [66] A. M. Bedewy, Y. Sun, S. Kompella, and N. B. Shroff, “Age-optimal sampling and transmission scheduling in multi-source systems,” in _ACM Int. Symp. Mobile Ad Hoc Netw. Comput._ , Catania, Italy, Jul. 2–5 2019, pp. 121–130, https://arxiv.org/abs/1812.09463.
  * [67] A. Kosta, N. Pappas, and V. Angelakis, “Age of information: A new concept, metric, and tool,” _Foun. and Trends in Net._ , vol. 12, no. 3, pp. 162–259, 2017.
  * [68] A. Maatouk, S. Kriouile, M. Assad, and A. Ephremides, “On the optimality of the whittle’s index policy for minimizing the age of information,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 2, pp. 1263–1277, 2021.
  * [69] M. A. Abd-Elmagid, H. S. Dhillon, and N. Pappas, “A reinforcement learning framework for optimizing age of information in RF-powered communication systems,” _IEEE Trans. Commun._ , vol. 68, no. 8, pp. 4747–4760, 2020.
  * [70] B. Zhou and W. Saad, “Minimum age of information in the internet of things with non-uniform status packet sizes,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 3, pp. 1933–1947, 2020.
  * [71] D. Bertsekas, _Dynamic programming and optimal control, volume II, 3rd ed_. Athena Scientific, 2007.
  * [72] R. G. Gallager, _Stochastic Processes: Theory for Applications_. Cambridge University Press, 2013.
  * [73] R. Gallager, _Discrete Stochastic Processes_. New York: Springer Science+Business Media, LLC, 1996.
  * [74] R. D. Yates and D. J. Goodman, _Probability and stochastic processes_. John Willey & Sons, 1999.