# Optimizing Age of Information in Wireless Uplink Networks with Partial
Observations

Jingwei Liu, Rui Zhang, Aoyu Gong, and He Chen The work of H. Chen and J. Liu
are supported in part by the Innovation and Technolgy Fund (ITF) under Project
ITS/204/20 and the CUHK direct grant for research under Project 4055126. The
work of R. Zhang is supported in part by the Research Talent Hub PiH/380/21
under Project ITS/204/20. This article was presented in part at GLOBECOM 2020.
J. Liu, R. Zhang and H. Chen are with Department of Information Engineering,
The Chinese University of Hong Kong, Hong Kong SAR, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>he.chen@ie.cuhk.edu.hk). A. Gong is with the School of Computer and
Communication Sciences, École Polytechnique Fédérale de Lausanne, Lausanne
1015, Switzerland (e-mail: aoyu.gong@epfl.ch).

###### Abstract

This paper considers a wireless uplink network consisting of multiple end
devices and an access point (AP). Each device monitors a physical process with
randomly generated status updates and sends these update packets to the AP in
the uplink. The AP aims to schedule the transmissions of these devices to
optimize the network-wide information freshness, quantified by the age of
information (AoI) metric. Due to the stochastic arrival of the status updates
at end devices, the AP only has partial observations of system times of the
latest status update packets at end devices when making scheduling decisions.
Such a decision-making problem can be naturally formulated as a partially
observable Markov decision process (POMDP). We reformulate the POMDP into an
equivalent belief Markov decision process (belief-MDP), by defining fully
observable belief states of the POMDP as the states of the belief-MDP. The
belief-MDP in its original form is difficult to solve as the dimension of its
states can go to infinity and its belief space is uncountable. Fortunately, by
carefully leveraging the properties of the status update arrival processes
(i.e., Bernoulli processes), we manage to simplify the belief-MDP
substantially, where every feasible state is characterized by a two-
dimensional vector. Based on the simplified belief-MDP, we devise a low-
complexity scheduling policy, termed Partially Observing Max-Weight (POMW)
policy, for the formulated AoI-oriented scheduling problem. We derive upper
bounds for the time-average AoI performance of the proposed POMW policy. We
analyze the performance guarantee for the POMW policy by comparing its
performance with a universal lower bound available in the literature.
Numerical results validate our analyses and demonstrate that the performance
gap between the POMW policy and its fully observable counterpart is
proportional to the inverse of the lowest arrival rate of all end devices.

###### Index Terms:

Age of information, multiuser scheduling, partially observable Markov decision
process, and belief Markov decision process.

##  I Introduction

The rapid development of wireless communication technologies in the past
decades has stimulated their ubiquitous applications in time-critical systems,
such as vehicular networks and industrial control networks [1, 2, 3]. In these
applications, information (e.g., velocity and position of a vehicle) needs to
be delivered to targeted receivers as timely as possible. The stale
information could cause severe consequences, e.g., damages to facilities or
even losses of human lives. Hence, the information timeliness or freshness in
these networks is of great importance. To quantify the information freshness,
the age of information (AoI) metric has been proposed and extensively
investigated in the literature (e.g., see [4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19] and references therein). More specifically, AoI is
defined as the time elapsed since the generation of the last successfully
received message at destination [4]. Many efforts have been made on tackling
transmission scheduling problems to minimize the time-average AoI of various
network settings. Early work focused on the AoI-based transmission scheduling
problem in single-user networks, see e.g., [20, 21, 22, 23, 24, 25], where the
AoI performance of the single user was optimized by determining when to
transmit a status update packet. Recent work has shifted to design the AoI-
based scheduling policies for multiuser networks, see e.g., [26, 27, 28, 29,
30, 31, 32]. In these work, the network-wide time-average AoI was optimized by
determining how to schedule the transmission sequence of multiple users.

In downlink multiuser networks, an access point (AP) monitors multiple
information sources and schedules transmissions of the generated status update
packets from itself to the corresponding end devices, respectively. In this
context, the AP can completely know the evolution of AoI when acknowledgements
are provided by end devices. The AoI-based scheduling problems in downlink
multiuser networks were thoroughly studied in [33, 26, 28]. The authors in
[26] considered the “generate-at-will” model for the generation of status
updates. In this model, the AP generates a status update for an information
source whenever the transmission to its targeted end device is scheduled. As
such, the AP only needs to consider the instantaneous AoI values of all end
devices when making scheduling decisions. Authors in [26] first proved that in
symmetric networks, a greedy policy, which schedules the end device with the
highest value of instantaneous AoI, is optimal for minimizing the long-term
average AoI. For more general networks, three low-complexity scheduling
policies were proposed and compared, including a Max-Weight policy derived
from the Lyapunov optimization framework [34], a randomized policy, and a
Whittle’s Index policy. Ref. [28] extended the Max-Weight policy to the
downlink networks with the “stochastic arrival” model, and an upper bound for
the network-wide time-average AoI was derived. On the other hand, [27]
developed a Whittle’s Index policy for the same scenario as in [28]. In the
“stochastic arrival” model, the generation of status update packets for each
information source follows a stochastic process. In this case, the system
times of update packets at the AP and the instantaneous AoI values of all end
devices need to be jointly considered when designing the scheduling policies
for the AP.

In uplink multiuser networks, on the other hand, each end device monitors the
statuses of a separate information source and sends status update packets to a
common AP. The AP aims to maintain a low network-wide AoI performance by
carefully scheduling the transmissions of status update packets in the uplink.
As the information destination, the AP has a full track of the AoI values of
all streams of status updates. For the “generate-at-will” model, each node
will generate a new status update packet once granted to transmit. As such,
the system times of status update packets are always equal to 1 and thus are
perfectly known to the AP.

In this case, the AoI-oriented scheduling problems in uplink networks are
mathematically equivalent to those in downlink networks when the scheduling
constraints of the two types of networks are the same. By contrast, when it
comes to the “stochastic arrival” model, the scheduling problems in uplink
multiuser networks are largely different from those in downlink networks. This
is because in uplink networks, the AP may need to make scheduling decisions
under partial observations of the system times of randomly generated status
update packets at end device side. The complete observations of the system
times of all status update packets requires end devices to report the arrivals
of new status updates to the AP before each scheduling decision-making. Such a
reporting procedure could lead to considerable network overhead, especially
when status update packets are short. Therefore, it is of practical
significance to devise scheduling policies for the AP that can be executed
without the need of complete knowledge of the system times of status update
packets at the end device side. In that case, the AP only has an observation
of the system time of status update of a certain end device only when the
device is scheduled to transmit and the transmission is successful. To the
best knowledge, such an AoI-based scheduling problem for uplink multiuser
networks with partial observations has not been thoroughly studied in open
literature. We note that [27] developed a Whittle’s Index policy for
optimizing AoI in an uplink multiuser network with the “stochastic arrival”
model. However, the system times of status update packets at all nodes are
assumed to be fully observed, making the scheduling problem mathematically
equivalent to that in [28].

As an attempt to fill the gap, in this paper we aim to optimize the expected
weighted sum AoI for an uplink multiuser network with stochastic arrivals of
status updates at end devices. The arrivals of status update packets at end
devices are assumed to follow independent Bernoulli processes, which is
commonly used in the literature (see e.g., [26, 28, 27, 34]). We consider that
the end devices will not report the random arrivals of the status updates to
the AP for minimizing the network overhead. As such, the designed scheduling
policy needs to make decisions with partial observations. The main
contributions of this paper are summarized as follows.

  * •

We formulate our AoI-oriented scheduling problem as a POMDP problem
considering the incomplete knowledge of status update arrivals of end devices
at the AP. The instantaneous system times of status update packets at the end
devices and the instantaneous AoI at the AP are jointly defined as the states
of the POMDP. We reformulate the POMDP to an equivalent belief Markov decision
process (belief-MDP), where the states of the belief–MDP, termed belief
states, are defined as the posterior distributions of the states of the POMDP.
We remark that computing the optimal policy for the belief-MDP (or the POMDP)
is a PSPACE-complete problem [35], which is not practically computable.
Nevertheless, such a belief-MDP reformulation benefits the policy design and
the theoretical analysis since the belief states characterize sufficient
statistics of the system.

  * •

To solve the formulated belief-MDP, we propose an effective simplification to
characterize all feasible infinite-dimensional belief states as two-
dimensional vectors. This is achieved by analyzing how Bernoulli arrival
processes of status updates at end devices affect the evolution of the belief
states. By doing so, we reduce the continuous spaces of the belief states to
discrete ones. That is, we extract the feasible belief spaces from the
corresponding distribution spaces. The simplification of belief updates in
belief-MDP largely facilitate the design of scheduling policies as well as the
theoretical analysis of the scheduling policies’ performance.

  * •

We devise a low-complexity Partially Observable Max-Weight (POMW) policy,
inspired by the Lyapunov optimization framework [34]. The POMW policy aims to
minimize a Lyapunov Drift function, defined as the expectation of the sum of
weighted instantaneous AoI, in each time slot under condition of the current
belief states. Based on the simplified belief-MDP model and a Randomized
Scheduling policy proposed in [28], we derive upper bounds for the expected
weighted sum AoI performance of the POMW policy. Further, we evaluate the
performance guarantee for the POMW policy, which is defined as the ratio
between the AoI performance of the POMW policy and that of a universal lower
bound. Simulation results validate our theoretical analysis. Simulation
results also show that the performance gap between the POMW policy and its
fully observable counterpart is inversely proportional to the lowest arrival
rate of all end devices. Moreover, the proposed POMW policy is superior to the
baseline policies, which do not use the statistical information of the system
times of the status update packets at end devices.

We notice a handful of efforts on designing AoI-oriented scheduling policies
that also considered networks with partial observations [21, 36, 37, 38]. Leng
and Yener investigated the AoI minimization in a time-slotted cognitive radio
energy harvesting network [21]. In [21], a secondary user decides whether to
send a status update in each time slot with the partially observable
occupation status of the spectrum. In this context, the AoI minimization
problem was formulated as a POMDP. The optimal policy with threshold structure
was sought by dynamic programming (DP). In [36], the authors formulated the
AoI optimization problem of a status update system with a partially observable
Gilbert–Elliott Channel as a belief-MDP. The authors developed an efficient
structure-aware algorithm that is shown to be near-optimal. Sert and Elif et
al. [37] investigated an AoI-based minimization on real-life TCP/IP
connections with unknown delay and service time distributions. They trained a
Deep Q-network (DQN) algorithm to perform actions on the network and obtained
a near-optimal AoI performance. Shao and Liew et al. [38] focused on the
minimum-age scheduling for a time-slotted wireless uplink network, where
multiple sensors are used to monitor one common physical process. The authors
formulated a POMDP and analyzed the performance of a greedy policy where an AP
schedules the sensor with the minimum system time in each slot. All of the
above work considered the AoI-based scheduling problem with one stream of
status update. As such, the developed methods cannot be directly applied to
solve our scheduling problem with multiple streams of status updates, where we
need to deal with the intricate interactions of the AoI evolutions of multiple
end devices.

We remark that part of the results presented in this work has been published
in the conference version [29]. In [29], we formulated the considered
scheduling design problem as a POMDP and solved it by directly applying the
classical DP method. A low-complexity myopic policy was also proposed.
However, the complication of the problem in its default form stopped us from
conducting any theoretical analysis. In the current work, we reformulate the
POMDP into a belief-MDP and put forth an effective simplification of the
belief-MDP. Such simplification substantially facilitate the design of the
POMW policy as well as the theoretical analysis of its performance.

Notations: In this paper, $\mathbb{Z}^{+}$ denotes the set of non-negative
integers, $\mathbb{E}[\cdot]$ denotes the operator of expectation, $[\cdot]$
denotes the representation of a vector containing the same type of elements,
$\left\langle\cdot\right\rangle$ denotes a tuple containing different types of
elements, and $\rVert\cdot\rVert_{1}$ denotes the $l_{1}$-norm of a vector.
For two vectors, $\bm{v}=[v_{l}]_{l=1}^{L}$ and $\bm{w}=[w_{l}]_{l=1}^{L}$,
with the same dimension $L$, $\bm{v}\geq\bm{w}$ represents $v_{l}\geq
w_{l},\forall l$.

##  II System Model and POMDP Formulation

###  II-A System Model

As shown in Fig. 1, we consider a multiuser wireless uplink network consisting
of one access point (AP) and $N$ status-updating end devices. Those end
devices are also called nodes hereafter, and indexed by $i\in\\{1,\dots,N\\}$.
The considered system is time-slotted, and the time slot is indexed by
$t\in\mathbb{Z}^{+}$. We consider a stochastic arrival model for the status
update packets at each node. Specifically, the status update arrival at node
$i$ in each slot follows an independent and identically distributed (i.i.d.)
Bernoulli process111The extension to the case with Markovian packet arrival
processes will be discussed in Remark 1. with an arrival rate $\lambda_{i}$.
Each node maintains a single buffer to store the latest status update. That
is, the current status update in the buffer will be replaced once a new one
arrives. Such a single-buffer configuration, equivalent to the last-come-
first-served (LCFS) queuing model, has been shown to achieve the best
information freshness performance in stochastic arrival models [11, 28]. All
nodes share a common wireless channel, and their transmissions of the status
update packets in the uplink are coordinated by the AP. Specifically, at the
beginning of each slot, the AP grants one node to transmit its latest status
update packet. We denote the scheduling indicator for node $i$ in slot $t$ by
$a_{t,i}\in\left\\{0,1\right\\}$, which is equal to 1 when node $i$ is
scheduled to transmit in slot $t$, and $a_{t,i}=0$ otherwise. Only one node is
scheduled to transmit in each slot, thus the transmission collision among
nodes is avoided. The transmission of each status update packet takes one time
slot. We further assume that the transmission from node $i$ to the AP is
error-prone with a time-invariant successful rate $p_{i}$.

Figure 1: The multiuser uplink system with stochastic arrival of status
updates.

###  II-B Information Freshness Metric

We adopt the AoI metric, originally proposed in [10], to quantify the
information freshness of all nodes at the AP. To characterize the AoI
mathematically, we first define the local age $d_{t,i}$, which measures the
system time of the last arrived status update packet at node $i$ in slot $t$.
If there is no arrival of status update at node $i$ in the current slot, the
local age of the $i$-th node will increase by $1$ at the beginning of next
slot. Otherwise, the packet stored at the node is replaced by the newly
arrived one, and its local age is reset to $1$ at the beginning of next slot.
Therefore, the evolution of $d_{t,i}$ is given by

$d_{t+1,i}=\begin{cases}1,&\text{if status update arrives at node}\ i\\\
&\text{in slot}\ t,\\\ d_{t,i}+1,&\text{otherwise}.\end{cases}$ (1)

If node $i$ is scheduled to transmit at the beginning of slot $t$ and its
transmission is successful, the local age of node $i$ will be observed by the
AP. As such, the destination AoI of node $i$, denoted by $D_{t,i}$, will be
set to $d_{t,i}+1$ at the beginning of the next slot. Otherwise, if node $i$
is not scheduled or the transmission fails, $D_{t,i}$ will increase by $1$ at
the beginning of the next slot. Mathematically, the evolution of $D_{t,i}$ is
given by

$\begin{split}&D_{t+1,i}\\\ &=\begin{cases}d_{t,i}+1,&\text{if the status
update of node $i$ is}\\\ &\text{successfully received by the AP in slot}\
t,\\\ D_{t,i}+1,&\text{otherwise}.\end{cases}\end{split}$ (2)

In this paper, we assume that the local age and the destination AoI of each
node are initialized as $1$ , i.e., $d_{0,i}=D_{0,i}=1,\forall i$.

We remark that the local age $d_{t,i}$ and the destination AoI $D_{t,i}$
evolve independently across nodes. We consider that the AP does not grasp the
specific evolutions of the local ages at all nodes and it only has the
statistical arrival information (i.e., the values of $\lambda_{i}$’s).
Otherwise, the nodes need to notify each of their status update arrivals to
the AP, which will lead to considerable network overhead, especially when the
status update packets are relatively short. In this context, the AP only has
an observation of the local age of a particular node once the node is
scheduled and the transmission succeeds. Nevertheless, the AP can track the
destination AoI values of all nodes, no matter whether they are scheduled or
not. Overall, the AP has full information of the AoI $D_{t,i}$’s and partial
observations of the local age $d_{t,i}$’s when making scheduling decisions.

###  II-C POMDP Formulation

In this work, we adopt the long-term expected weighted sum AoI (EWSAoI) as the
performance metric, which is mathematically defined as

$\lim_{T\to\infty}\frac{1}{NT}\mathbb{E}\left[\sum^{T}_{t=1}\sum^{N}_{i=1}\omega_{i}D_{t,i}\Big{|}\pi\right],$
(3)

where $\omega_{i}\in(0,\infty)$ denotes the weight coefficient of node $i$,
the expectation is taken over all system dynamics, and $\pi$ denotes a given
multiuser scheduling policy. We aim to devise a scheduling policy $\pi$ for
the AP to minimize the long-term EWSAoI while fulfilling the scheduling
constraint. Mathematically, we have the following optimization problem

$\begin{split}\min_{\pi}\quad&\lim_{T\to\infty}\frac{1}{NT}\mathbb{E}\left[\sum^{T}_{t=1}\sum^{N}_{i=1}\omega_{i}D_{t,i}\Big{|}\pi\right],\\\
\mbox{s.t.,}\quad&\sum^{N}_{i=1}a_{t,i}\leq 1,\forall t,\end{split}$ (4)

where the scheduling constraint is that the AP can schedule at most one node
in each slot. In our design, the AP makes the scheduling decision at the
beginning of each time slot. The information available at the AP for decision
making includes the values of $\lambda_{i}$’s, $p_{i}$’s, $\omega_{i}$’s, the
full observations of the destination AoI $D_{t,i}$’s, and the partial
observations of the local age $d_{t,i}$’s. Such a decision-making problem with
partial observations is naturally formulated as a POMDP with the following
components:

  * •

States. The state of node $i$ in slot $t$ is denoted by
$\bm{s}_{t,i}\triangleq\left\langle d_{t,i},D_{t,i}\right\rangle$, where
$d_{t,i},D_{t,i}\in\mathbb{Z}^{+}$. Then, the network-wide state in slot $t$
is denoted by
$\bm{s}_{t}\triangleq\left\langle\bm{d}_{t},\bm{D}_{t}\right\rangle$, where
$\bm{d}_{t}\triangleq\left[d_{t,1},d_{t,2},\dots,d_{t,N}\right]\in\bm{\mathcal{D}}\triangleq\left(\mathbb{Z}^{+}\right)^{N}$
and
$\bm{D}_{t}\triangleq\left[D_{t,1},D_{t,2},\dots,D_{t,N}\right]\in\bm{\mathcal{D}}$,
respectively. In addition, we denote the spaces of $\bm{s}_{t,i}$ and
$\bm{s}_{t}$ by
$\bm{\mathcal{S}}_{i}\triangleq\left\\{\bm{s}_{t,i}|D_{t,i}\geq
d_{t,i}\right\\}$ and
$\bm{\mathcal{S}}\triangleq\left\\{\bm{s}_{t}|\bm{D}_{t}\geq\bm{d}_{t}\right\\}$,
respectively.

  * •

Actions. The network-wide action in slot $t$ is denoted by
$\bm{a}_{t}\triangleq\left[a_{t,1},a_{t,2},\dots,a_{t,N}\right]$. Recall that
AP schedules at most one node in each slot, hence we have
$\left|\bm{a}_{t}\right|\leq 1$. Denote by $\bm{\mathcal{A}}$ the space of all
actions, we have $\bm{a}_{t}\in\bm{\mathcal{A}}$.

  * •

Observations. We denote the network-wide observation of the state of the nodes
by
$\bm{o}_{t}\triangleq\left[\bm{o}_{t,1},\bm{o}_{t,2},\dots,\bm{o}_{t,N}\right]\in\bm{\mathcal{O}}$,
where $\bm{\mathcal{O}}$ is the space of all observations. Specifically,
$\bm{o}_{t,i}\triangleq\left\langle D_{t,i},\hat{d}_{t,i}\right\rangle$ is the
observation of node $i$ in slot $t$, consisting of the full-observed
destination AoI, $D_{t,i}$, and the partial-observed local age
$\hat{d}_{t,i}$. We have
$\hat{d}_{t,i}\in\mathbb{Z}^{+}\bigcup\left\\{X\right\\}$, where $X$ denotes
no observation of the local age of node $i$ when the node is not scheduled or
the node is scheduled but the transmission fails. With these new notations,
$\bm{o}_{t}$ can be denoted by
$\left\langle\bm{D}_{t},\hat{\bm{d}}_{t}\right\rangle$, where
$\hat{\bm{d}}_{t}=\left[\hat{d}_{t,1},\dots,\hat{d}_{t,N}\right]$.

  * •

Transition Function. We define the transition probability of network-wide
states as $\Pr\left(\bm{s}_{t+1}|\bm{s}_{t},\bm{a}_{t}\right)$, which denotes
the conditional probability of state $\bm{s}_{t+1}$ given state $\bm{s}_{t}$
and action $\bm{a}_{t}$. We note that the transitions of $\bm{D}_{t}$ and
$\bm{d}_{t}$ are conditionally independent of each other and the transition of
the local age $d_{t}$ is independent of the action $a_{t}$. We then have

$\Pr\left(\bm{s}_{t+1}|\bm{s}_{t},\bm{a}_{t}\right)=\Pr\left(\bm{D}_{t+1}|\bm{s}_{t},\bm{a}_{t}\right)\Pr\left(\bm{d}_{t+1}|\bm{d}_{t}\right),$
(5)

where

$\Pr\left(\bm{D}_{t+1}|\bm{s}_{t},\bm{a}_{t}\right)=\prod_{i=1}^{N}\Pr\left(D_{t+1,i}|\bm{s}_{t,i},a_{t,i}\right),$
(6)

and

$\Pr\left(\bm{d}_{t+1}|\bm{d}_{t}\right)=\prod_{i=1}^{N}\Pr\left(d_{t+1,i}|d_{t,i}\right).$
(7)

We can further express each term on the right-hand side of (6) as

$\begin{split}&\Pr\left(D_{t+1,i}|\bm{s}_{t,i},a_{t,i}\right)\\\
&=\begin{cases}p_{i},&\text{if}\ a_{t,i}=1,\text{and}\ D_{t+1,i}=d_{t,i}+1,\\\
1-p_{i},&\text{if}\ a_{t,i}=1,\text{and}\ D_{t+1,i}=D_{t,i}+1,\\\
1,&\text{if}\ a_{t,i}=0,\text{and}\ D_{t+1,i}=D_{t,i}+1,\\\
0,&\text{otherwise}.\end{cases}\end{split}$ (8)

Similarly, for each term on the right-hand side of (7), we have

$\Pr\left(d_{t+1,i}|d_{t,i}\right)=\begin{cases}\lambda_{i},&\text{if}\
d_{t+1,i}=1,\\\ 1-\lambda_{i},&\text{if}\ d_{t+1,i}=d_{t,i}+1,\\\
0,&\text{otherwise.}\end{cases}$ (9)

  * •

Observation Function. Denote by
$\Pr\left(\bm{o}_{t}|\bm{s}_{t},\bm{a}_{t}\right)$ the network-wide
observation function, which is defined as the probability of observation
$\bm{o}_{t}$ conditioned on state $\bm{s}_{t}$ and action $\bm{a}_{t}$. Note
that $\bm{D}_{t}$ is fully observable at the AP and the evolution of
$\hat{d}_{t,i}$ with different $i$ are independent from each other. We thus
have

$\begin{split}\Pr\left(\bm{o}_{t}|\bm{s}_{t},\bm{a}_{t}\right)&=\Pr\left(\hat{\bm{d}}_{t}|\bm{d}_{t},\bm{a}_{t}\right)\\\
&=\prod_{i=1}^{N}\Pr\left(\hat{d}_{t,i}|d_{t,i},a_{t,i}\right),\end{split}$
(10)

where we term

$\begin{split}&\Pr\left(\hat{d}_{t,i}|d_{t,i},a_{t,i}\right)\\\
&=\begin{cases}p_{i},&\text{if}\ \hat{d}_{t,i}=d_{t}\ \text{and}\
a_{t,i}=1,\\\ 1-p_{i},&\text{if}\ \hat{d}_{t,i}=X\ \text{and}\ a_{t,i}=1,\\\
1,&\text{if}\ \hat{d}_{t,i}=X\ \text{and}\ a_{t,i}=0,\\\
0,&\text{otherwise.}\end{cases}\end{split}$ (11)

as the local age observation function of node $i$.

  * •

Immediate Reward. We target to optimize the long-term EWSAoI. Based on that,
We define the immediate reward of state $\bm{s}_{t}$ as
$r\left(\bm{s}_{t}\right)\triangleq\sum^{N}_{i=1}\omega_{i}D_{t,i}$.

We remark that due to the partially observed network-wide state $\bm{s}_{t}$,
the formulated POMDP problem cannot be solved by directly applying the
existing AoI-oriented scheduling frameworks designed for the scenarios with
full observation of network-wide states (e.g., [22, 28, 26]). To circumvent
the problem, we will leverage the sufficient posterior probability
distribution of $\bm{s}_{t}$ with the observation $\bm{o}_{t}$ at the AP. Such
probability distributions are also named as the belief states of the POMDP
[35]. In the following, we will reformulate our POMDP as a belief-MDP, where
the belief states of the POMDP are regarded as the states of the belief-MDP.

##  III Belief-MDP Formulation and Simplification

In this section, we first reformulate the POMDP introduced in Section II as a
belief-MDP and then simplify the belief-MDP to gain more insights.

###  III-A Reformulation of the POMDP

With reference to [39], a POMDP can be converted to an equivalent belief-MDP
based on the belief states of the system. To that end, we now introduce the
definitions of the belief states and other components of the belief-MDP
version of our POMDP problem as follows:

  * •

Belief States. The belief state of node $i$ is defined as the current
probability distribution over $\bm{\mathcal{S}}_{i}$ on condition of the
history so far. Mathematically, the belief state of node $i$ in slot $t$ is
denoted by

$\bm{B}_{t,i}\triangleq\left[B_{t,i}(\bm{s}_{t,i})\right]_{\bm{s}_{t,i}\in\bm{\mathcal{S}}_{i}}$
(12)

with $\rVert\bm{B}_{t,i}\rVert_{1}=1$, where
$B_{t,i}(\bm{s}_{t,i})\triangleq\Pr\left(\bm{s}_{t,i}|\bm{h}_{t,i}\right)$
denotes the probability assigned to state $\bm{s}_{t,i}$ with the current
history
$\bm{h}_{t,i}\triangleq\left\langle\bm{B}_{1,i},a_{1,i},\bm{o}_{1,i},a_{2,i},\dots,a_{t-1,i},\bm{o}_{t-1,i}\right\rangle$
of node $i$. As mentioned in Section II-B, ${D}_{t,i}$ is deterministic for a
given history profile $\bm{h}_{t,i}$ since $\bm{h}_{t,i}$ includes
$\bm{o}_{t-1,i}$. Therefore, $\bm{B}_{t,i}$ can also be represented by
$\left\langle{D}_{t,i},\bm{b}_{t,i}\right\rangle$, where
$\bm{b}_{t,i}\triangleq\left[b_{t,i}(d_{t,i})\right]_{d_{t,i}\in\mathbb{Z}^{+}}$
denotes the belief state of the local age of node $i$, and
$\rVert\bm{b}_{t,i}\rVert_{1}=1$. Furthermore,
$b_{t,i}\left({d}_{t,i}\right)\triangleq\Pr\left(d_{t,i}|\bm{h}_{t,i}\right)$
denotes the probability assigned to ${d}_{t,i}$. Hence, we have
$B_{t,i}\left(\bm{s}_{t,i}\right)=b_{t,i}\left({d}_{t,i}\right)$ given
${D}_{t,i}$.

The network-wide belief state is defined as the current probability
distribution over $\bm{\mathcal{S}}$ on condition of
$\bm{h}_{t}\triangleq\left\langle\bm{B}_{1},a_{1},\bm{o}_{1},\bm{a}_{2},\dots,\bm{a}_{t-1},\bm{o}_{t-1}\right\rangle$,
and it is also the state of the belief-MDP. We denote the network-wide belief
state in slot $t$ by

$\bm{B}_{t}\triangleq\left[B_{t}(\bm{s}_{t})\right]_{\bm{s}_{t}\in\bm{\mathcal{S}}}=\left\langle\bm{D}_{t},\bm{b}_{t}\right\rangle,$
(13)

where
$\bm{b}_{t}\triangleq\left[b_{t}(\bm{d}_{t})\right]_{\bm{d}_{t}\in\bm{\mathcal{D}}}$
is the belief state of all local ages in slot $t$ with
$b_{t}\left(\bm{d}_{t}\right)\triangleq\Pr\left(\bm{d}_{t}|\bm{h}_{t}\right)$
denoting the probability222We omitted $\bm{h}_{t,i}$ in the definition of the
belief state for concise notation. assigned to $\bm{d}_{t}$, and with
$B_{t}(\bm{s}_{t})\triangleq\Pr\left(\bm{s}_{t}|\bm{h}_{t}\right)$ denoting
the probability assigned to $\bm{s}_{t}$. Thus, we have
$\rVert\bm{B}_{t}\rVert_{1}=\rVert\bm{b}_{t}\rVert_{1}=1$. With a given
$\bm{D}_{t}$, the belief state of the local age of each node evolves
independently in our POMDP framework, and thus we have
${B}_{t}\left(\bm{s}_{t}\right)=b_{t}\left(\bm{d}_{t}\right)=\prod_{i=1}^{N}{b}_{t,i}\left(d_{t,i}\right)$.
Besides, we denote $\bm{\mathcal{B}}$ as the belief space, i.e., the
collection of all possible $\bm{B}_{t}$. $\bm{\mathcal{B}}$ is also called
belief simplex [40].

  * •

Belief Update. AP can update $\bm{B}_{t+1}$ from $\bm{B}_{t}$ at the end of
slot $t$ after receiving new observations once the last action $\bm{a}_{t}$ is
executed. Recall that
$\bm{B}_{t}=\left\langle\bm{D}_{t},\bm{b}_{t}\right\rangle$, both $\bm{D}_{t}$
and $\bm{b}_{t}$ need to be updated. Specifically, the destination AoI of node
$i$ , i.e., the $i$-th component of $\bm{D}_{t}$, can be updated by

$\begin{split}D_{t+1,i}=\begin{cases}D_{t,i}+1,&\text{if}\ \hat{d}_{t,i}=X,\\\
\hat{d}_{t,i}+1,&\text{otherwise}.\end{cases}\end{split}$ (14)

The update of $D_{t,i}$ is deterministic and independent from node to node.
Moreover, $\bm{b}_{t+1}$ can be updated from $\bm{b}_{t}$ through the Bayes’
theorem as

$\begin{split}&b_{t+1}(\bm{d}_{t+1})\\\
&=\rho\sum_{\bm{d}_{t}\in\bm{\mathcal{D}}}b_{t}\left(\bm{d}_{t}\right)\Pr\left(\bm{d}_{t+1}|\bm{d}_{t}\right)\Pr\left(\hat{\bm{d}}_{t}|\bm{d}_{t},\bm{a}_{t}\right),\end{split}$
(15)

where

$\rho=\\\
1/\sum_{\bm{d}_{t+1},\bm{d}_{t}\in\bm{\mathcal{D}}}b_{t}\left(\bm{d}_{t}\right)\Pr\left(\bm{d}_{t+1}|\bm{d}_{t}\right)\Pr\left(\hat{\bm{d}}_{t}|\bm{d}_{t},\bm{a}_{t}\right)$
(16)

is the Bayes normalizing factor. Considering the independent evolutions of
$d_{t,i}$’s across nodes, we can also update $\bm{b}_{t}$ via updating
$\bm{b}_{t,i}$ of each node $i$ individually. We omit the update equation of
$\bm{b}_{t,i}$ here for brevity.

  * •

Actions. The action of the belief-MDP in slot $t$ is denoted by
$\bm{a}_{t}\in\bm{\mathcal{A}}$, which is exactly same as that of the POMDP.

  * •

Transition Function. The transition function of the belief-MDP is given by

$\begin{split}&\Pr\left(\bm{B}_{t+1}|\bm{B}_{t},\bm{a}_{t}\right)\\\
&=\sum_{\bm{o}_{t}\in\bm{\mathcal{O}}}\Pr\left(\bm{B}_{t+1}|\bm{B}_{t},\bm{a}_{t},\bm{o}_{t}\right)\Pr\left(\bm{o}_{t}|\bm{B}_{t},\bm{a}_{t}\right),\end{split}$
(17)

where

$\begin{split}&\Pr\left(\bm{o}_{t}|\bm{B}_{t},\bm{a}_{t}\right)\\\
&=\sum_{\bm{s}_{t+1},\bm{s}_{t}\in\bm{\mathcal{S}}}B_{t}\left(\bm{s}_{t}\right)\Pr\left(\bm{s}_{t+1}|\bm{s}_{t},\bm{a}_{t}\right)\Pr\left(\bm{o}_{t}|\bm{s}_{t},\bm{a}_{t}\right),\end{split}$
(18)

and

$\begin{split}&\Pr\left(\bm{B}_{t+1}|\bm{B}_{t},\bm{a}_{t},\bm{o}_{t}\right)\\\
&=\begin{cases}1,&\text{if the belief update with arguments}\\\
&\bm{B}_{t},\bm{a}_{t},\bm{o}_{t}\text{ returns}\ \bm{B}_{t+1},\\\
0,&\text{otherwise}.\end{cases}\end{split}$ (19)

  * •

Policy. We adopt a deterministic stationary scheduling policy $\pi$ for the
belief-MDP. The policy maps the belief space $\bm{\mathcal{B}}$ to the action
space in each slot.

  * •

Reward. Since the destination AoI is deterministic for the AP, the immediate
expected reward on condition of belief state $\bm{B}_{t}$ is the same as that
in the POMDP, i.e.,
$R\left(\bm{B}_{t}\right)\triangleq\mathbb{E}\left[r(\bm{s}_{t})|\bm{B}_{t}\right]=\sum^{N}_{i=1}\omega_{i}D_{t,i}$.
On this basis, the objective problem can be rewritten as

$\begin{split}\min_{\pi}\quad&\lim_{T\to\infty}\frac{1}{NT}\mathbb{E}\left[\sum^{T}_{t=1}R(\bm{B}_{t})\Big{|}\bm{B}_{1},\pi\right],\\\
\mbox{s.t.,}\quad&\rVert\bm{a}_{t}\rVert_{1}\leq 1,\forall t,\end{split}$ (20)

where $\bm{B}_{1}$ is a predefined initial belief state. Recall that we assume
$d_{0,i}=D_{0,i}=1,\forall i$, before running the network, and thus
$\bm{B}_{1,i}=\left\langle
2,\left[\lambda_{i},1-\lambda_{i},0,\cdots\right]\right\rangle,\forall i$.

We remark that the belief update is computationally complicated when the
dimension of the belief states is high, and is impractical when the dimension
goes to infinity. Moreover, the continuousness of the belief space
$\bm{\mathcal{B}}$ leads to a PSPACE hardness of optimizing the EWSAoI of the
belief-MDP optimally [35]. Thus, it is intractable to optimize the EWSAoI of
the network exactly. As such, we are motivated to further analyze the belief-
MDP to find a more feasible solution.

###  III-B Belief-MDP Simplification

We subsequently show the existence of a simplified representation of the
belief-MDP with the given $\bm{B}_{1}$. To start, we have the following
definition:

######  Definition 1.

Assume AP schedules node $i$ in slot $t$ with observation $d_{t,i}=k_{i}$, and
then does not receive any packet from node $i$ in the following $m_{i}$ slots.
Define the local age belief state of node $i$ in slot $t+m_{i}$ by
$\bm{c}(k_{i},m_{i})$, namely, the belief of node $i$ with the last
observation $k_{i}$ followed by $m_{i}$ elapsed slots.

For convenience, we ignore index $i$ for nodes and introduce the following
proposition.

######  Proposition 1.

The distribution vector of the local age belief state $\bm{c}(k,m)$ of node
$i$ in slot $t$ can be given by

$\begin{split}\bm{c}(k,m)&=\left[c_{k,m}\left(d_{t}\right)\right]_{d_{t}\in\mathbb{Z}^{+}}\\\
&=\left[\lambda,\lambda\gamma,\lambda\gamma^{2},\cdots,\lambda\gamma^{m-1},0,\cdots,0,\gamma^{m},0,\cdots\right],\end{split}$
(21)

where $k,m\in\mathbb{Z}^{+}$, $\gamma=1-\lambda$, and
$c_{k,m}\left({d}_{t}\right)$ denotes the probability assigned to ${d}_{t}$.
The position of entry $\gamma^{m}$ is $k+m$, and this denotes that the
corresponding destination AoI of entry $\gamma^{m}$ is $k+m$.

###### Proof.

See Appendix A. ∎

Notice that Proposition 1 follows the evolution branch of local age belief
state in [38, Proposition 4]. However, the belief state in [38] is the
distribution of the local age only, while that in this paper also involves the
destination AoI. Moreover, a truncation was given to the local age in [38] but
not used in this paper.

Define a group of belief states that have the AoI equal to $k+m$ together with
$\bm{c}(k,m)$ defined in Proposition 1 as $\bm{C}(k,m)\triangleq\left\langle
k+m,\bm{c}(k,m)\right\rangle$ for $m,k\in\mathbb{Z}^{+}$. Denote by
$\bm{\mathcal{C}}$ the collection of all possible $\bm{C}(k,m)$. Then, we have
the following corollary.

######  Corollary 1.

Suppose the network has a certain belief state, i.e.,
$\bm{b}_{0,i}=\bm{e}_{1},D_{0,i}=1,\forall i$ before running, then
$\bm{B}_{t,i}\in\bm{\mathcal{C}}$ for $t=1,2,\cdots,T,\forall i$.

###### Proof.

We use induction to prove it. First, it is clear that
$\bm{b}_{1,i}=\bm{c}(1,1),D_{1,i}=2$, and hence
$\bm{B}_{1,i}\in\bm{\mathcal{C}}$. Suppose $\bm{B}_{t,i}=\left\langle
k_{t,i}+m_{t,i},\bm{c}(k_{t,i},m_{t,i})\right\rangle\in\bm{\mathcal{C}},\forall
i$, where $k_{t,i}$ and $m_{t,i}$ denote the last observation of local age and
the number of slots elapsed since the last observation of node $i$ in slot
$t$, respectively. Then, if node $i$ is scheduled and the status update is
successfully received by the AP, we have
$\bm{b}_{t+1,i}=\bm{c}(\hat{k}_{t,i},1)$ and $D_{t+1,i}=\hat{k}_{t,i}+1$,
where $\hat{k}_{t,i}$ is the local age observation of node $i$ in slot $t$ and
$\hat{k}_{t,i}\in\left\\{1,2,\cdots,m_{t,i}\right\\}\cup\left\\{k_{t,i}+m_{t,i}\right\\}$.
This means that $\bm{B}_{t+1,i}\in\bm{\mathcal{C}},\forall i$. If node $i$ is
not scheduled or the transmission fails, $\bm{B}_{t+1,i}=\left\langle
k_{t,i}+m_{t,i}+1,\bm{c}(k_{t,i},m_{t,i}+1)\right\rangle\in\bm{\mathcal{C}},\forall
i$. This completes the proof.

∎

Based on Corollary 1, each infinite dimensional belief state
$\bm{B}_{t,i}\in\bm{\mathcal{C}}$ can be sufficiently represented by two
positive integers $k_{t,i}$ and $m_{t,i}$, with $D_{t,i}=k_{t,i}+m_{t,i}$ and
$\bm{b}_{t,i}=\bm{c}(k_{t,i},m_{t,i})$. Hence, the belief-MDP framework in
Section III can be characterized in a much simpler form. We name this
simplified representation of belief MDP as Last-Observation-Characterized
(LOC) belief-MDP. The actions of the LOC belief-MDP are the same as that of
the original belief-MDP. The other components of the LOC belief-MDP are
presented as follows.

  * •

States. The state of node $i$ in slot $t$ is denoted by
$\bm{z}_{t,i}\triangleq\left[k_{t,i},m_{t,i}\right]$, where
$k_{t,i},m_{t,i}\in\mathbb{Z}^{+}$ are defined in Corollary 1. Then, the
network-wide state in slot $t$ is denoted by
$\bm{z}_{t}\triangleq\left[\bm{k}_{t},\bm{m}_{t}\right]$, where
$\bm{k}_{t}\triangleq\left[k_{t,1},k_{t,2},\dots,k_{t,N}\right]\in\bm{\mathcal{D}}$
and
$\bm{m}_{t}\triangleq\left[m_{t,1},m_{t,2},\dots,m_{t,N}\right]\in\bm{\mathcal{D}}$.
Define $\bm{\mathcal{Z}}\triangleq\bm{\mathcal{D}}\times\bm{\mathcal{D}}$ as
the space set of $\bm{z}_{t}$. $\bm{\mathcal{Z}}$ also corresponds to the
feasible part of the belief space $\bm{\mathcal{B}}$ for belief states with
the initialization in Corollary 1.

  * •

Transition Function. We define the transition function of the LOC belief-MDP
as $\Pr\left(\bm{z}_{t+1}|\bm{z}_{t},\bm{a}_{t}\right)$, which is given by

$\Pr\left(\bm{z}_{t+1}|\bm{z}_{t},\bm{a}_{t}\right)=\prod_{i=1}^{N}\Pr\left(\bm{z}_{t+1,i}|\bm{z}_{t,i},a_{t,i}\right),$
(22)

where

$\begin{split}&\Pr\left(\bm{z}_{t+1,i}|\bm{z}_{t,i},a_{t,i}=1\right)\\\
&=\begin{cases}p_{i}\lambda_{i}(1-\lambda_{i})^{d-1},&\text{if}\
k_{t+1,i}=d\text{ and}\\\ &m_{t+1,i}=1,\\\
p_{i}(1-\lambda_{i})^{m_{t,i}},&\text{if}\ k_{t+1,i}=k_{t,i}+m_{t,i}\\\
&\text{and }m_{t+1,i}=1,\\\ 1-p_{i},&\text{if}\ k_{t+1,i}=k_{t,i}\text{
and}\\\ &m_{t+1,i}=m_{t,i}+1,\\\ 0,&\text{otherwise},\end{cases}\end{split}$
(23)

with $d\in\left\\{1,2,\cdots,m_{t,i}\right\\}$. Furthermore,
$\Pr\left(\bm{z}_{t+1,i}|\bm{z}_{t,i},a_{t,i}=0\right)=1$ if
$k_{t+1,i}=k_{t,i}$ and $m_{t+1,i}=m_{t,i}+1$.

  * •

Reward. The expected immediate reward given a state $\bm{z}_{t}$ is rewritten
as
$R\left(\bm{z}_{t}\right)\triangleq\sum^{N}_{i=1}\omega_{i}(k_{t,i}+m_{t,i})$.

  * •

Policy. The policy for the LOC belief-MDP framework is the same as that in
Section III with a different domain $\bm{\mathcal{Z}}$. It can be equivalently
denoted by $\pi:\bm{\mathcal{Z}}\longmapsto\bm{\mathcal{A}}$.

In typical work on solving a belief-MDP, one need to use the Backup operation
[40, 41] to repeatedly find more feasible belief states and update the
feasible belief space horizon by horizon. It is computationally complicated,
and unlikely to reach most of feasible belief states in the belief simplex.
However, with the above simplification, we reduce the space of belief states
sharply from the continuous space $\bm{\mathcal{B}}$ to a discrete space
$\bm{\mathcal{Z}}$. That enables us to directly obtain the full feasible space
of the belief states without using the inefficient Backup operation.
Furthermore, the completed transition probabilities of belief states can be
obtained by (22).

Figure 2: The sub-region of $\bm{\mathcal{B}}$ and its reduced feasible space,
i.e., points $[0.4,0.6,0,\cdots]$,$[0.4,0,0.6,0,\cdots]$, and
$[0.4,0.24,0.36,0,\cdots]$ in the three-dimensional space with $N=1$ and
$\lambda=0.4$.

Fig.2 illustrates one example of the space reduction, where we have one node
with its status update arrival rate $\lambda=0.4$. The gray triangle plane is
the sub-region of $\bm{\mathcal{B}}$ in the three-dimensional space, on which
each point is associated with a possible local age belief state. After the
simplification, the sub-region of the belief space $\bm{\mathcal{B}}$ can be
reduced to three feasible belief states, i.e., the three points plotted on the
sub-region.

######  Remark 1.

We can extend the above LOC belief-MDP simplification process to the scenario
with Markovian arrival processes. Specifically, the belief states of a node
can still be characterized by two-dimensional vectors. More details can be
found in Appendix D.

##  IV POMW Policy

Based on the LOC belief-MDP, we can use the conventional DP approach to solve
the AoI scheduling problem. However, the LOC belief-MDP is formulated for a
multiuser model, thus the DP would suffer from the curse of the dimensionality
as the number of end devices increases. To circumvent such a problem, we
propose a low-complexity policy for the EWSAoI optimization in the considered
network with partial observations, named POMW policy.

We remark that a downlink network with the same status update traffic model as
ours was investigated in [28]. Different from our network, the local age of
the status update packets are fully observable at the AP due to the downlink
setting. The authors devised an Age-based Max-Weight policy by leveraging the
Lyapunov Optimization [34]. This policy minimizes a defined Lyapunov drift on
condition of the fully observable local age and destination AoI in each slot.
Hereafter, we call it Fully Observable Max-Weight (FOMW) policy. Moreover, for
brevity, we use “FON” to represent the network with the fully observable
states in [28] and “PON” to represent our considered network with partial
observations in the rest of this paper.

Inspired by [28], we apply the Lyapunov Optimization to devise a low-
complexity policy, i.e., the POMW policy, which extends the FOMW policy
developed in [28]. To that end, we will define a Lyapunov Function based on
the EWSAoI of the network. The POMW policy attempts to minimize the expected
drift of the Lyapunov Function under condition of the current belief state and
destination AoI in each slot $t$. Therefore, the EWSAoI of the network can be
optimized with lower computational complexity.

We define the linear Lyapunov Function as

$L(t)=\frac{1}{N}\sum^{N}_{i=1}\beta_{i}D_{t,i},$ (24)

where $\beta_{i}>0$ is an hyper-parameter that can be used to tune the POMW
policy to different network configurations. The Lyapunov Drift is defined as

$\Delta\left[\bm{B}_{t}\right]=\mathbb{E}\left[L(t+1)-L(t)|\bm{B}_{t}\right].$
(25)

The Lyapunov Drift $\Delta\left[\bm{B}_{t}\right]$ refers to the expected
increase of the Lyapunov Function $L(t)$ in one slot. Hence, by minimizing the
drift in (25), the POMW policy equivalently reduces $L(t)$. Consequently, the
EWSAoI of the network is kept low.

To develop the POMW policy for the Lyapunov Drift minimization, we analyze the
expression for the drift in (25). Recall the definition of $\bm{B}_{t}$, we
realize that the value of $L(t)$ is fixed with a given $\bm{B}_{t}$. Thus
minimizing the Lyapunov Drift in (25) is equivalent to minimizing
$\mathbb{E}[L(t+1)|\bm{B}_{t}]$. Recall the evolution of $D_{t,i}$ given in
(2), and we have

$\begin{split}&\mathbb{E}[L(t+1)|\bm{B}_{t}]\\\
=&\sum_{i=1}^{N}\dfrac{1}{N}\mathbb{E}\left[\beta_{i}D_{t+1,i}\Bigg{|}\bm{B}_{t}\right]\\\
=&\sum_{i=1}^{N}\dfrac{\beta_{i}}{N}\left[p_{i}a_{t,i}\sum_{d\in\mathbb{Z}^{+}}b_{t,i}(d)(d+1)+(1-p_{i}a_{t,i})(D_{t,i}+1)\right]\\\
=&\dfrac{1}{N}\left[-\sum_{i=1}^{N}a_{t,i}\beta_{i}p_{i}G_{t,i}+\sum_{i=1}^{N}\beta_{i}(D_{t,i}+1)\right],\end{split}$
(26)

where

$G_{t,i}:=D_{t,i}-\sum_{d\in\mathbb{Z}^{+}}b_{t,i}(d)d.$ (27)

Eq. (26) leads to following proposition:

######  Proposition 2.

To minimize the Lyapunov Drift in slot $t$, the POMW policy should schedule
node $i$ with the maximal $\beta_{i}p_{i}G_{t,i}$.

The proof of Proposition 2 is straightforward and hence is omitted. Before the
POMW policy making the scheduling decision, the belief probabilities
$b_{t,i}(d)$ need to be updated based on the observations of the previous
slot.

######  Remark 2.

Note that when local age is fully observed, we have

$\sum_{d\in\mathbb{Z}^{+}}b_{t,i}(d)d=d_{t,i},\forall t,i.$ (28)

In this case, the POMW policy will schedule node $i$ with the maximal
$\beta_{i}p_{i}\left(D_{t,i}-d_{t,i}\right)$ in each slot, which exactly
coincides with the criterion of the FOMW policy presented in [28]. This
observation indicates that the POMW policy is a generalization of the FOMW
policy.

However, it is hard to implement this online policy on the fly due to the high
computational complexity. In each slot, the POMW policy selects an action
$\bm{a}_{t}$ by minimizing (26). This step requires
$O\left(N|\bm{\mathcal{A}}||\mathbb{Z}^{+}|\right)$ operations. Subsequently,
the policy updates the local age belief states for the next slot by the Bayes’
theorem. Such an update step requires $O\left(N|\mathbb{Z}^{+}|^{2}\right)$
operations. Those two steps are computationally intractable since
$\mathbb{Z}^{+}$ is an infinite set333One can truncate the maximum value of
AoI to make the computation feasible. However, a sufficiently large cap of the
AoI should be applied to ensure the accuracy of the truncation, which still
leads to unacceptably high computational complexity.. Thus, the
straightforward application of the FOMW policy to our problem could be
impractical.

Thanks to the LOC belief-MDP framework proposed in Proposition 1, we are able
to simplify the expression of $G_{t,i}$ from complex expectation calculation
to a closed-form expression of only three parameters. More specifically, it
can be expressed as

$\begin{split}G_{t,i}&=k_{t,i}+m_{t,i}-\bm{c}(k_{t,i},m_{t,i})\bm{n}\\\
&=m_{t,i}+\left[1-\left(1-\lambda_{i}\right)^{m_{t,i}}\right]\left(k_{t,i}-\frac{1}{\lambda_{i}}\right),\end{split}$
(29)

where $\bm{n}=\left[1,2,3,\cdots\right]^{T}$. By now, we can formally describe
the POMW policy in Algorithm 1. The POMW policy can minimize the Lyapunov
Drift with low computational complexity, and consequently optimize the EWSAoI
of the network.

Initialization: $t=1,m_{t,i}=1,k_{t,i}=1,\forall i$444To ease understanding
and simplify expressions, we set such an initialization. Without loss of
generality, we can also select any $\bm{b}_{1}\in\bm{\mathcal{B}}$ for the
initialization. In that case, when $m_{t,i}$ and $k_{t,i}$ do not exist for
some $i,t$, we can update belief states by (15) and calculate $G_{t,i}$ by
(27).;

while  _each new slot $t$_ do

for  _each node $i$_ do

$G_{t,i}=m_{t,i}+\left[1-\left(1-\lambda_{i}\right)^{m_{t,i}}\right]\left(k_{t,i}-\frac{1}{\lambda_{i}}\right)$;

end for

Schedule node $j$ in the current slot, where

$j=\arg\max\limits_{i}\beta_{i}p_{i}G_{t,i}$;

Obtain the local age observation $\hat{d}_{t,j}$ of node $j$;

if  _$\hat{d}_{t,j}=X$_ then

$m_{t+1,j}=m_{t,j}+1$;

else if  _$\hat{d}_{t,j}=d\in\mathbb{Z}^{+}$_ then

$m_{t+1,j}=1,k_{t+1,j}=d$;

end if

$m_{t+1,i}=m_{t,i}+1,\forall i\neq j$;

$t=t+1$;

end while

Algorithm 1 POMW Policy

Note that in Algorithm 1, the updates of $k_{t,i}$ and $m_{t,i}$ are based on
the transition function of the LOC belief-MDP given in (23).

Thanks to the proposed simplification, the complexity of the step to select an
action is reduced from $O\left(N|\bm{\mathcal{A}}||\mathbb{Z}^{+}|\right)$ to
$O\left(N|\bm{\mathcal{A}}|\right)$. The complexity of updating states is
reduced from $O\left(N|\mathbb{Z}^{+}|^{2}\right)$ to $O\left(2N\right)$.
Moreover, we do not need to set a truncation on destination AoI or local age
when implementing Algorithm 1.

##  V Performance Analyses

In this section, we first introduce a low-complexity policy named Randomized
Scheduling (RS) policy and analyze its EWSAoI performance. Based on its
performance, we derive the upper bounds for the EWSAoI performance of the POMW
policy. We also analyze the performance guarantee of the POMW policy by
comparing its EWSAoI performance with a universal lower bound in the
literature.

###  V-A RS Policy

In [28], an RS policy was proposed to optimize the AoI of the network. In the
RS policy, node $i$ is scheduled with probability $\mu_{i}\in\left(0,1\right]$
in each slot. The scheduling probabilities are time-invariant and satisfy
$\sum_{i=1}^{N}\mu_{i}\leq 1$. Notice that the actions of the RS policy is
independent of the network states, thus this policy can also be adopted in the
considered PON. With reference to the proof of [28, Prop. 4], we give the
EWSAoI performance of the RS policy, denoted by $R^{RS}$, in Proposition 3.

######  Proposition 3.

The EWSAoI of the network under the RS policy with scheduling probabilities
$\left\\{\mu_{i}\right\\}^{N}_{i=1}$ is

$R^{RS}=\frac{1}{N}\sum_{i=1}^{N}\omega_{i}\left(\dfrac{1}{\lambda_{i}}+\dfrac{1}{p_{i}\mu_{i}}\right).$
(30)

Note that the EWSAoI in (30) is slightly different from that in [28] due to
the difference in the local age evolution of two systems. Denote by
$\left\\{\mu^{*}_{i}\right\\}^{N}_{i=1}$ the optimal scheduling probabilities
of all node, the optimal RS policy is given as follows [28, Th. 5].

######  Theorem 1.

Consider the network under the RS policy. The optimal scheduling probabilities
are

$\mu^{*}_{i}=\dfrac{\sqrt{\omega_{i}/p_{i}}}{\sum_{j=1}^{N}\sqrt{\omega_{j}/p_{j}}},$
(31)

and correspondingly,

$R^{{RS}^{*}}=\frac{1}{N}\left[\sum_{i-1}^{N}\dfrac{\omega_{i}}{\lambda_{i}}+\left(\sum_{i-1}^{N}\sqrt{\dfrac{\omega_{i}}{p_{i}}}\right)^{2}\right].$
(32)

According to [28, Th.10], $R^{RS*}$ is the upper bound of the EWSAoI
performance of the FOMW policy, denoted by $R^{FOMW}$. The FOMW policy can be
regarded as the full-observed counterpart of the POMW policy.

###  V-B Upper Bounds of the POMW Policy

Built upon the proposed LOC belief-MDP, we now derive two upper bounds for the
POMW policy. One of them is the EWSAoI performance of a particular RS policy,
as stated in the following theorem:

######  Theorem 2.

The EWSAoI performance of the POMW policy with
$\beta_{i}=\omega_{i}/\lambda_{i}\mu^{\prime}_{i}p_{i},\forall i$, denoted by
$R^{POMW}$, is upper bounded by

$R^{POMW}\leq\frac{1}{N}\sum_{i=1}^{N}\omega_{i}\left(\dfrac{1}{\lambda_{i}\mu^{\prime}_{i}p_{i}}+1\right)\leq
R^{RSM},$ (33)

where

$\mu^{\prime}_{i}=\dfrac{\sqrt{\omega_{i}/\lambda_{i}p_{i}}}{\sum_{j=1}^{N}\sqrt{\omega_{j}/\lambda_{j}p_{j}}},\forall
i,$ (34)

are a series of scheduling probabilities of all nodes in the network.
$R^{RSM}$ is the EWSAoI of an RS policy with the corresponding scheduling
probabilities

$\mu^{M}_{i}=\dfrac{\sqrt{\omega_{i}\lambda_{i}/p_{i}}}{\sum_{j=1}^{N}\sqrt{\omega_{j}/\lambda_{j}p_{j}}},\forall
i.$ (35)

###### Proof.

We prove it by leveraging the introduced RS policy. See Appendix B for
details. ∎

Note that the value assigned to $\beta_{i}$, which depends on
$\mu^{\prime}_{i}$, can be attained by minimizing the upper bound of the
EWSAoI, given by
$\frac{1}{N}\sum_{i=1}^{N}\omega_{i}\left(1/(\lambda_{i}\mu^{\prime}_{i}p_{i})+1\right)$.
A similar method was used in [34].

###  V-C Performance Guarantee of the POMW Policy

Based on Theorem 2, we can analyze the performance guarantee of the POMW
policy theoretically. Firstly, we introduce a universal lower bound given in
[28, Th.3]. This lower bound applies to any feasible scheduling policy, and is
applicable to both FONs and PONs. The universal lower bound of the EWSAoI
performance of any policies is given by

$\displaystyle L_{B}=\min\limits_{\left\\{q_{i}\right\\}^{N}_{i=1}}\quad$
$\displaystyle\frac{1}{2N}\sum_{i=1}^{N}\omega_{i}\left(\frac{1}{q_{i}}+3\right),$
(36) s.t., $\displaystyle\sum_{i=1}^{N}q_{i}/p_{i}\leq 1,$ (37) $\displaystyle
q_{i}\leq\lambda_{i},\forall i.$ (38)

The solution $q^{*}_{i}$ of the above problem can be obtained following [28,
Algorithm 1], and the lower bound is

$L_{B}=\frac{1}{2N}\sum_{i=1}^{N}\omega_{i}\left(\frac{1}{q^{*}_{i}}+3\right).$
(39)

######  Corollary 2.

The performance of the POMW policy with
$\beta_{i}=\omega_{i}/\lambda_{i}q^{*}_{i}$ follows that

$\dfrac{R^{POMW}}{L_{B}}<\dfrac{2}{\lambda_{min}},$ (40)

where $\lambda_{min}\triangleq\min\left\\{\lambda_{i}\right\\}^{N}_{i=1}$.

###### Proof.

See Appendix C ∎

######  Remark 3.

We use the ratio between $R^{POMW}$ and $L_{B}$ to evaluate the performance
guarantee of the POMW policy. Corollary 2 indicates that the ratio is
inversely proportional to the packet arrival rates of nodes $\lambda_{i}$ in
the network. When the network is close to the “generate-at-will”, i.e.,
$\lambda_{i}\to 1,\forall i$, the ratio of $R^{POMW}$ and $L_{B}$ with
$\beta_{i}=\omega_{i}/\lambda_{i}q^{*}_{i}$ is smaller than $2$. This
coincides with the performance guarantee of a counterpart FOMW policy devised
for the “generate-at-will” system in [13].

##  VI Numerical Results

In this section, we first compare the proposed POMW policy with its fully
observable counterparts. We then verify the theoretical analyses on the POMW
policy. Finally, we compare the performance of the POMW policy with that of
two baseline policies in PONs.

###  VI-A Comparisons with Fully Observable Counterparts

The EWSAoI performances of the POMW and FOMW policies are obtained via $2000$
Monte-Carlo simulation runs. $\beta_{i}$ is set as
$\omega_{i}/\lambda_{i}\mu^{\prime}_{i}p_{i}$ for both of the two policy. The
AoI performance of the RS policies, the universal lower bound $L_{B}$, and the
upper bound of $R^{POMW}$ are computed using (30), (36), and (52),
respectively.

Figure 3: EWSAoI performance versus an increasing packet arrival rate, where
$N=2$, $p_{1}=p_{2}=0.8$, and $\omega_{1}=\omega_{2}=1$.

In Fig. 3, we illustrate the EWSAoI of the POMW policy, its corresponding
upper bounds, and the universal lower bound $L_{B}$ with increasing packet
arrival rate. The $R^{FOMW}$ in the FON and its corresponding upper bound,
i.e., the optimal RS policy, are given as benchmarks. We set $N=2$,
$\omega_{1}=\omega_{2}=1$, $p_{1}=p_{2}=0.8$,
$\lambda_{1}=\lambda_{2}=\lambda$, $D=20$, and $T=100$. Fig. 3 shows that all
curves decrease as $\lambda$ increases. This is intuitive because the EWSAoI
decreases when the status update packets arrive at nodes more frequently.
Furthermore, the value of the universal lower bound is the smallest, the value
of $R^{RSM}$ is the largest, and $R^{POMW}$ and $R^{FOMW}$ are lower than
their corresponding upper bounds, respectively. These relationships validate
the analysis given in the previous section. Fig. 3 also shows that $R^{POMW}$
is larger than $R^{FOMW}$, and the upper bound of $R^{POMW}$ is larger than
that of $R^{FOMW}$. This is intuitive because the POMW policy in the PON only
knows the packet arrival rate and some occasional observations, while the FOMW
policy in the FON can utilize the fully observed state information.
Furthermore, the gap between the $R^{FOMW}$ and its upper bound decreases
slowly as $\lambda$ increases, while the gap between the $R^{POMW}$ and its
upper bound decreases much quickly. This phenomenon can be explained by
refering to the expressions of the upper bounds, given by (30) and (33). It is
obvious that $1/\lambda_{i}$ in (33) always has larger coefficient than that
of (30). Hence, the upper bound of $R^{POMW}$ increases faster than that of
$R^{FOMW}$ with the decrease of $\lambda$. Moreover, the EWSAoI performances
of the POMW and FOMW polices and their corresponding upper bounds converge to
the same value when $\lambda=1$. This is because both the PON and FON approach
to the “generate-at-will” model when $\lambda$ tends to $1$.

Figure 4: $R^{POMW}$ and $R^{FOMW}$ versus transmission successful rate with
different combinations of $\lambda_{i}$ in PON and FON, where $N=2$, and
$\omega_{1}=\omega_{2}=1$.

In Fig. 4, we compare $R^{FOMW}$ and $R^{POMW}$ versus transmission successful
rate $p$ with three pairs of packet arrival rates
$\\{\lambda_{1},\lambda_{2}\\}$. We set $p_{1}=p_{2}=p$,
$\omega_{1}=\omega_{2}=1$, and three pairs of packet arrival rates
$\lambda_{1}=\lambda_{2}=0.5$; $\lambda_{1}=0.25$, $\lambda_{2}=0.75$; and
$\lambda_{1}=0.1$, $\lambda_{2}=0.9$. Fig. 4 shows that the gap between
$R^{FOMW}$ and $R^{POMW}$ becomes larger when the gap between two
$\lambda_{i}$s increase. This can be explained by combining Corollary 2 and
[28, Th.5]. Corollary 2 indicates that the performance guarantee of $R^{POMW}$
is inversely proportional to $\lambda_{min}$, and [28, Th.5] indicates that
the performance guarantee of the fully observed counterpart is a constant. A
larger arrival rate gap results in a smaller $\lambda_{min}$, and consequently
a larger gap between the $R^{POMW}$ and $R^{FOMW}$. Fig. 4 also shows that
$R^{POMW}$ and $R^{FOMW}$ decreases in all cases when the packet transmission
rate $p$ increases. This is because the destination AoI $D_{t,i}$ drops to the
local age $d_{t,i}+1$ more frequently with larger $p$.

Figure 5: EWSAoI performance as the number of nodes increases, where
$\lambda_{1}=\lambda_{2}=0.1$, $p_{1}=p_{2}=0.8$, and
$\omega_{1}=\omega_{2}=1$. Figure 6: EWSAoI performance as the number of nodes
increases, where $\lambda_{1}=\lambda_{2}=0.5$, $p_{1}=p_{2}=0.8$, and
$\omega_{1}=\omega_{2}=1$.

In Fig. 5, we depict the EWSAoI of the POMW and FOMW policies with increased
number of nodes, and compare them with corresponding upper bounds. We also
include $R^{RSM}$ and the universal lower bound as benchmarks. We set
$\lambda_{i}=0.1$ and $p_{i}=0.8$ for all nodes, and increase the number of
nodes from $10$ to $30$. It is shown in Fig. 5 that all curves increase as
number of nodes increases. This is because each node has fewer chances to be
scheduled when the number of nodes increases, thus its AoI has fewer chances
to decrease. Fig. 6 plots the same set of curves as in Fig. 5, where the
values of $\lambda_{1}$ and $\lambda_{2}$ are both set to be $0.5$. Fig. 6
shows similar phenomenon observed in Fig. 5. Furthermore, the performance of
all schemes improves from Fig. 5 to Fig. 6, which is expected since the packet
arrival rates are increased.

###  VI-B Comparison with Baseline Policies

In the following, we show the advantages of the proposed POMW policy in PONs
over two baseline policies. The baseline policies are described as follows:

  * 1)

Round Robin (RR) policy: In the RR policy, nodes are scheduled by the AP in a
circular order to ensure a fair scheduling opportunity among the nodes.

  * 2)

Max weighted AoI (MWA) policy: The MWA policy does not need the knowledge of
nodes’ local age. Specifically, the AP always schedules the node $j$ with
$j=\arg\max\limits_{i}\omega_{i}p_{i}D_{t,i}$.

In the following figures, the EWSAoI performance of all policies are obtained
via $10000$ Monte-Carlo simulation runs.

Figure 7: EWSAoI performance versus packet arrival rate $\lambda$ in the PON
with $N=10$, and $\omega_{i}=1$, $p_{i}=0.5$, $\forall i$.

Fig. 7 shows the EWSAoI performance of the POMW policy, the MWA policy, and
the RR policy in a symmetric PON. The weight coefficients $\omega_{i}$ and
transmission successful rates $p_{i}$ of all nodes are the same. We can
observe from Fig. 7 that the RR policy has the worst performance. This is
intuitive because the RR policy does not use the observations of the network
states, while the MWA and POMW policies make decisions depending on the
observations. Moreover, the POMW policy is superior to the MWA policy when
$\lambda$ is small, but the EWSAoI performances of these two policies tend to
coincide when $\lambda\geq 0.25$. This is owing to the fact that the MWA
policy only leverages the observations of the destination AoI, while the POMW
policy uses the observations of both the destination AoI and local age.
Furthermore, in a symmetric PON, the expected local ages of all nodes tend to
be symmetric as $\lambda$ grows. In this case, the POMW policy and the MWA
policy becomes equivalent.

Figure 8: EWSAoI performance versus packet arrival rate $\lambda$ in the PON
with $N=10$, and $\omega_{i}\sim\mathcal{U}(0.1,1.9)$,
$p_{i}\sim\mathcal{U}(0.1,0.9)$, $\forall i$. Note that the notation
$\mathcal{U}(a,b)$ denotes a uniform distribution over the real number
interval $[a,b]$.

Fig. 8 plots the long-term EWSAoI curves of all three policies as in Fig. 7
over asymmetric PONs. The transmission successful rates and weight
coefficients of all nodes are randomly drawn from uniform distributions in
each simulation run. We can see that in this case, the performance of POMW
policy clearly outperforms that of the RR and MWA policies. Furthermore, the
performance of the MWA policy cannot approach to that of the POMW policy even
when the arrival rate increases to $0.3$. This is because the expected local
ages are not symmetric in an asymmetric PON and the MWA policy does not
consider this information.

##  VII Conclusions

In this paper, we investigated the AoI-oriented scheduling problem for a
wireless multiuser uplink network. Due to the partial observations of the
local ages at end devices, we formulated the scheduling decision-making
problem as a partially observable Markov decision process (POMDP). The POMDP
was first reformulated to an equivalent belief-MDP, and then simplified to an
Last-Observation-Characterized (LOC) belief-MDP by adequately leveraging the
properties of the status update arrival processes. With the simplification,
the infinite dimensional belief states can be characterized by two-dimensional
vectors, and thus the complexity of belief updates is significantly reduced.
On this basis, we devised the Partially Observable Max-Weight (POMW) policy
that minimizes the expected weighted sum AoI of the next slot on condition of
the current belief state. Based on the LOC belief-MDP, we derived upper bounds
for the performance of the proposed POMW policy. Moreover, we evaluated the
performance guarantee of the POMW policy by comparing its performance with a
universal lower bound available in the literature. Finally, simulation results
validated our analyses, illustrating that the performance gap between the
proposed POMW policy and its fully observable counterpart is proportional to
the inverse of the lowest arrival rate. The simulation results also validated
the superiority of the POMW policy over the baseline policies.

Future work includes the development of a Whittle’s index-based policy for the
considered scheduling problem, the extension to the scenarios where the packet
arrival rates at end nodes are not known a priori, as well as the extension to
more recent information freshness metrics (e.g., AoI at Query [42]).

##  Appendix A Proof of Proposition 1

Proposition 1 can be proved by induction. First, we show that

$\bm{c}(k,1)=\left[\lambda,0,\cdots,0,1-\lambda,0,\cdots\right],$ (41)

where $(1-\lambda)$ is the $(k+1)$-th entry if we suppose $\hat{d}_{t}$ equals
to $k$. Then, according to (2), the destination AoI $D_{t+1}=k+1$ because
there is no packet received from the node in slot $t$ and $d_{t}=k$. This
satisfies Proposition 1.

Suppose $\bm{c}(k,m)$ satisfies (21), i.e.,

$\bm{c}(k,m)=\left[\lambda,\lambda\gamma,\lambda\gamma^{2},\cdots,\lambda\gamma^{m-1},0,\cdots,0,\gamma^{m},0,\cdots\right],$
(42)

where $\gamma^{m}$ is the $(k+m)$-th entry, and $D_{t+m}=k+m$. Then, on one
side, according to (9), we have

$\begin{split}&\bm{c}(k,m+1)\\\
&=\left[b_{t+m+1}(1),\lambda\gamma,\lambda\gamma^{2},\cdots,\lambda\gamma^{m},0,\cdots,0,\gamma^{m+1},0,\cdots\right]\end{split}$
(43)

with $\gamma^{m+1}$ being the $(k+m+1)$-th entry. Because (43) is a
probability distribution, we have

$\begin{split}b_{t+m+1}(1)&=1-\sum_{d>1}b_{t+m+1}(d)\\\
&=1-\left(\lambda\sum^{m}_{l=1}\gamma^{l}+\gamma^{m+1}\right)\\\
&=1-\gamma=\lambda.\end{split}$ (44)

On the other side, $D_{t+m+1}=k+m+1$, since there is no packet received from
the node in slot $t+m$. Thus, the local age belief state and AoI in slot
$t+m+1$ still satisfy Proposition 1. The proposition is proved.

##  Appendix B Proof of Theorem 2

According to the definition, the Max-Weight policy minimizes the expected sum
AoI of the next slot under the condition of $\bm{B}_{t}$. Thus, the Randomized
Scheduling policy with arbitrary feasible scheduling probabilities
$\left\\{\mu_{i}\right\\}^{N}_{i=1}$ yields a higher (or equal) value of the
expected sum AoI of the next slot. We then have

$\begin{split}&\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left[\beta_{i}\left(D_{t+1,i}-D_{t,i}\right)\Bigg{|}\bm{B}_{t}\right]\\\
&\leq\frac{1}{N}\sum_{i=1}^{N}\beta_{i}+\frac{1}{N}\sum_{i=1}^{N}\mu_{i}p_{i}\beta_{i}\left(\sum_{d\in\mathcal{D}}b_{t,i}(d)d-D_{t,i}\right),\forall
t.\end{split}$ (45)

Now, we analyze the RHS of (45). Given $\lambda_{i}$, $p_{i}$, $\beta_{i}$ and
$\bm{B}_{t}$, according to the LOC belief-MDP, we have

$\begin{split}\sum_{d\in\mathcal{D}}b_{t,i}(d)d&=\frac{1}{\lambda_{i}}+\left(k_{t,i}-\frac{1}{\lambda_{i}}\right)\left(1-\lambda_{i}\right)^{D_{t,i}-k_{t,i}},\\\
\end{split}$ (46)

where $k_{t,i}\in\left\\{1,2,\cdots,D_{t,i}-1\right\\}$. Define

$X(k)\triangleq\left(k-\frac{1}{\lambda_{i}}\right)\left(1-\lambda_{i}\right)^{D_{t,i}-k},$
(47)

where $k$ denotes a possible value of $k_{t,i}$. Clearly,
$\left(1-\lambda_{i}\right)^{D_{t,i}-k}$ is always positive, we hence discuss
the sign of the term $k-\frac{1}{\lambda_{i}}$.

When $k-\frac{1}{\lambda_{i}}>0$, $X(k-1)<X(k)$ is equivalent to

$\dfrac{X(k-1)}{X(k)}=\left(1-\lambda_{i}\right)\left(1-\dfrac{1}{k-1/\lambda_{i}}\right)<1.$
(48)

Manipulating (48) and considering $k-\frac{1}{\lambda_{i}}>0$, we find that
(48) holds if $k>\frac{1}{\lambda_{i}}$. As $k\in\mathbb{Z}^{+}$, $X(k)$
increases on
$k=\left\lfloor\frac{1}{\lambda_{i}}\right\rfloor,\left\lceil\frac{1}{\lambda_{i}}\right\rceil,\left\lceil\frac{1}{\lambda_{i}}\right\rceil+1,\cdots$.

When $k-\frac{1}{\lambda_{i}}<0$, $X(k-1)<X(k)$ is equivalent to

$\left(1-\lambda_{i}\right)\left(1-\dfrac{1}{k-1/\lambda_{i}}\right)>1.$ (49)

Similarly, we obtain that $X(k)$ increases on
$k=1,2,\cdots,\left\lfloor\frac{1}{\lambda_{i}}\right\rfloor$. Therefore, for
any given $D_{t,i}>1$, $X(1)<X(2)<\cdots<X(D_{t,i}-1)$. This property also
holds when $1/\lambda_{i}$ is an integer. Substituting $k_{t,i}=D_{1,i}-1$
into (45) and (46) yields

$\begin{split}&\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left[\beta_{i}\left(D_{t+1,i}-D_{t,i}\right)\Bigg{|}\bm{B}_{t}\right]\\\
&\leq\frac{1}{N}\sum_{i=1}^{N}\beta_{i}+\frac{1}{N}\sum_{i=1}^{N}\mu_{i}p_{i}\beta_{i}\left(\lambda_{i}-\lambda_{i}D_{t,i}\right),\forall
t.\end{split}$ (50)

Taking the expectation of both sides of (50) with respect to $\bm{B}_{t}$,
taking a sum over $t\in\left\\{1,2,\cdots,T\right\\}$, and then taking the
time-average, we have

$\begin{split}&\frac{1}{NT}\sum_{i=1}^{N}\mathbb{E}\left[\beta_{i}D_{t+1,i}\right]-\frac{1}{NT}\sum_{i=1}^{N}\mathbb{E}\left[\beta_{i}D_{1,i}\right]\\\
&\leq\frac{1}{N}\sum_{i=1}^{N}\beta_{i}+\frac{1}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}\mu_{i}p_{i}\beta_{i}\mathbb{E}\left[\lambda_{i}-\lambda_{i}D_{t,i}\right].\end{split}$
(51)

Rearranging (51), we take the limit as $T\to\infty$ and assign
$\beta_{i}=\omega_{i}/\lambda_{i}\mu_{i}p_{i}$. Then, we have

$\begin{split}\lim_{T\to\infty}\frac{1}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}\omega_{i}\mathbb{E}\left[D_{t,i}\right]&\leq\frac{1}{N}\sum_{i=1}^{N}\dfrac{\omega_{i}}{\lambda_{i}\mu_{i}p_{i}}+\frac{1}{N}\sum_{i=1}^{N}\omega_{i}\\\
&\overset{(a)}{\leq}\frac{1}{N}\sum_{i=1}^{N}\dfrac{\omega_{i}}{\lambda_{i}\mu_{i}p_{i}}+\frac{1}{N}\sum_{i=1}^{N}\frac{\omega_{i}}{\lambda_{i}},\end{split}$
(52)

where the inequality $(a)$ follows as $\lambda_{i}\in\left(0,1\right],\forall
i$.

The left hand side (LHS) of (52) is the long-term EWSAoI of the network under
the Max-Weight policy. Following the Lyapunov optimization, to minimize the
upper bound, i.e., RHS of (52), with respect to $\mu_{i}$, we equivalently
need to solve

$\begin{split}\min\limits_{\left\\{\mu_{i}\right\\}^{N}_{i=1}}\quad&\sum_{i=1}^{N}\dfrac{\omega_{i}}{\lambda_{i}\mu_{i}p_{i}},\\\
\mbox{s.t.}\quad&\sum_{i=1}^{N}\mu_{i}\leq 1.\end{split}$ (53)

By applying similar procedures presented in the proof of [28, Th. 5], we can
obtain the optimal solution to the problem (53) given by

$\mu^{\prime}_{i}=\dfrac{\sqrt{\omega_{i}/\lambda_{i}p_{i}}}{\sum_{j=1}^{N}\sqrt{\omega_{j}/\lambda_{j}p_{j}}},\forall
i.$ (54)

Substituting (54) makes the RHS of (52), we can arrive at (54) after some
necessary manipulations. This completes the proof.

##  Appendix C Proof of Corollary 2

According to the constraint (37), $\mu_{i}=q^{*}_{i}/p_{i}$ satisfies the
inequality (45). Thus, substituting $\mu_{i}=q^{*}_{i}/p_{i}$ and
$\beta_{i}=\omega_{i}/\lambda_{i}\mu_{i}p_{i}$ into (52) gives

$\begin{split}R^{POMW}&\leq\frac{1}{N}\sum_{i=1}^{N}\omega_{i}\left(\frac{1}{\lambda_{i}q^{*}_{i}}+1\right)\\\
&<\frac{1}{N}\sum_{i=1}^{N}\omega_{i}\left(\frac{1}{\lambda_{min}q^{*}_{i}}+\frac{3}{\lambda_{min}}\right)=\dfrac{2L_{B}}{\lambda_{min}},\end{split}$
(55)

where the second inequality follows as $\lambda_{min}\leq\lambda_{i}\leq 1$,
and this completes the proof.

##  Appendix D Extension to Markovian Arrivals

We extend our framework to the scenario with Markovian arrival processes in
this appendix. The packet arrival process at each node is characterized by a
Markov chain, where the probability of a packet arrival in the current slot
depends on the packet arrival situation in the previous slot. Let
$A_{t,i}\in\left\\{0,1\right\\}$ denote the indicator of the packet arrival
situation of node $i$ in slot $t$, $A_{t,i}=1$ when there is a packet arrival
at node $i$ in slot $t$, and $A_{t,i}=0$ otherwise. The transition functions
of $A_{t,i}$ can be written as

$\Pr\left(A_{t+1,i}|A_{t,i}\right)=\begin{cases}\overline{\Lambda}_{i},&\text{if}\
A_{t,i}=1,A_{t+1,i}=1,\\\ \overline{\Gamma}_{i},&\text{if}\
A_{t,i}=1,A_{t+1,i}=0,\\\ \Lambda_{i},&\text{if}\ A_{t,i}=0,A_{t+1,i}=1,\\\
\Gamma_{i},&\text{if}\ A_{t,i}=0,A_{t+1,i}=0,\\\
0,&\text{otherwise},\end{cases}$ (56)

where $\Gamma_{i}\triangleq 1-\Lambda_{i}$ and
$\overline{\Gamma}_{i}\triangleq 1-\overline{\Lambda}_{i}$. The Markov chain
diagram of the status update arrivals is shown in Fig. 9.

Figure 9: The Markov chain of the status update arrival process at node $i$.

Recall that the status update arrival situation of each time slot is known to
each node at the end of the said slot. In this case, the update packet
transmitted from the scheduled node to the AP only contains the status update
arrived in the previous slot. We note that the value of the local age of each
node in the current slot implies the packet arrival situation in the previous
time slot. Specifically, $d_{t+1,i}=1$ represents that a status update arrived
at node $i$ in slot $t$, and $d_{t+1,i}>1$ otherwise. Therefore, the
transition functions of the local age can be expressed as

$\Pr\left(d_{t+1,i}|d_{t,i}\right)=\begin{cases}\overline{\Lambda}_{i},&\text{if}\
d_{t,i}=1\text{ and }d_{t+1,i}=1,\\\ \overline{\Gamma}_{i},&\text{if}\
d_{t,i}=1\text{ and }d_{t+1,i}=2,\\\ \Lambda_{i},&\text{if}\ d_{t,i}>1\text{
and }d_{t+1,i}=1,\\\ \Gamma_{i},&\text{if}\ d_{t,i}>1\text{ and
}d_{t+1,i}=d_{t,i}+1,\\\ 0,&\text{otherwise.}\end{cases}$ (57)

To characterize the belief state of the local age of a node mathematically, we
artificially introduce a local observer at each node that can decide to
observe whether a status update arrives at the said node or not. Note that
such observers do not exist in practice, and are introduced to facilitate the
characterization of the belief state of the local age of a node. The
observation of the arrival of the status update at node $i$ in slot $t$ is
denoted by $\hat{A}_{t,i}\in\left\\{0,1,X\right\\}$, where $\hat{A}_{t,i}=1$
when an arrival of a status update is observed at node $i$ in slot $t$,
$\hat{A}_{t,i}=0$ when no arrival is observed at node $i$ in slot $t$, and
$\hat{A}_{t,i}=X$ when no observation is made at node $i$ in slot $t$. Let
$\omega_{t,i}\triangleq\Pr(A_{t,i}=1|\bm{h}_{t,i})$ denotes the belief
probability that a new status update arrives at node $i$ in slot $t$ given
$\bm{h}_{t,i}\triangleq\left\langle\omega_{1,i},\hat{A}_{1,i},\dots,\hat{A}_{t-1,i}\right\rangle$.
Hence, the belief state of the arrival of the status update at node $i$ can be
expressed as
$[\Pr(A_{t,i}=0|\bm{h}_{t,i}),\Pr(A_{t,i}=1|\bm{h}_{t,i})]=[1-\omega_{t,i},\omega_{t,i}]$,
which is a two-dimension simplex. Given $\hat{A}_{t,i}$, $\omega_{t+1,i}$ can
be updated by

$\omega_{t+1,i}=\eta(\omega_{t,i},\hat{A}_{t,i})=\begin{cases}\overline{\Lambda}_{i},&\text{if}\
\hat{A}_{t,i}=1,\\\ \Lambda_{i},&\text{if}\ \hat{A}_{t,i}=0,\\\
\mathcal{T}(\omega_{t,i}),&\text{if}\ \hat{A}_{t,i}=X,\end{cases}$ (58)

where
$\mathcal{T}(\omega_{t,i})=\omega_{t,i}\overline{\Lambda}_{i}+(1-\omega_{t,i})\Lambda_{i}$
denotes the one step belief update of $\omega_{t,i}$. Additionally, we define
the one step belief update of $1-\omega_{t,i}$ as
$\mathcal{G}(1-\omega_{t,i})\triangleq 1-\mathcal{T}(\omega_{t,i})$. Let
$\mathcal{T}^{m}(\omega_{t,i})\triangleq\Pr(A_{t+m,i}=1|\omega_{t,i})$ denote
the $m$-step belief update of $\omega_{t,i}$ when the arrival situation is
unobserved for $m$ consecutive slots, where $m\in\left\\{0,1,\cdots\right\\}$
and $\mathcal{T}^{0}(\omega_{t,i})=\omega_{t,i}$.
$\mathcal{G}^{m}(1-\omega_{t,i})\triangleq\Pr(A_{t+m,i}=0|\omega_{t,i})=1-\mathcal{T}^{m}(\omega_{t,i})$
denotes the $m$-step belief update of $1-\omega_{t,i}$ in the same case, where
$\mathcal{G}^{0}(1-\omega_{t,i})=1-\omega_{t,i}$. Further,

$\begin{split}\mathcal{T}^{m}(\omega)&=\frac{\Lambda-(\overline{\Lambda}-\Lambda)^{m}(\Lambda-(1+\Lambda-\overline{\Lambda})\omega)}{1+\Lambda+\overline{\Lambda}}\\\
&\in[0,1],{\ \ \ \ }\forall\omega\in[0,1].\end{split}$ (59)

We remark that we follow a method in [43] to derive (59) by formulating a
partially observable two-state Markov chain. For brevity, we refer the readers
to the proof of Lemma 1 of [43] for the derivation details.

We subsequently show the existence of a simplified representation of the
belief states of the local age with the given $\bm{B}_{1}$. To start, we have
the following definition:

######  Definition 2.

Assume AP schedules node $i$ in slot $t$ with observation $d_{t,i}=k_{i}$, and
then does not receive any packet from node $i$ in the following $m_{i}$ slots.
Define the local age belief state of node $i$ in slot $t+m_{i}$ by
$\bm{e}(k_{i},m_{i})$, namely, the local age belief of node $i$ with the last
observation $k_{i}$ followed by $m_{i}$ elapsed slots.

For convenience, we ignore index $i$ for nodes and introduce the following
proposition to show the simplified representation of the belief state of the
type given in Definition 2.

######  Proposition 4.

The distribution vector of the local age belief state $\bm{e}(k,m)$ of node
$i$ in slot $t$ can be given by (60) and (61) given on top of next page,

$\begin{split}&\bm{e}(1,m)=\left[e_{1,m}\left(d_{t}\right)\right]_{d_{t}\in\mathbb{Z}^{+}}\\\
&=\left[\mathcal{T}^{m-1}(\overline{\Lambda}),\mathcal{G}^{m-1}(\overline{\Gamma})\mathcal{T}^{m-2}(\overline{\Lambda}),\mathcal{G}^{m-1}(\overline{\Gamma})\mathcal{G}^{m-2}(\overline{\Gamma})\mathcal{T}^{m-3}(\overline{\Lambda}),\cdots,\overline{\Lambda}\prod^{m-1}_{d=1}\mathcal{G}^{d}(\overline{\Gamma}),\prod^{m-1}_{d=0}\mathcal{G}^{d}(\overline{\Gamma}),0,\cdots\right],\end{split}$
(60)

$\begin{split}&\bm{e}(k>1,m)=\left[e_{k,m}\left(d_{t}\right)\right]_{d_{t}\in\mathbb{Z}^{+}}\\\
&=\left[\mathcal{T}^{m-1}(\Lambda),\mathcal{G}^{m-1}(\Gamma)\mathcal{T}^{m-2}(\Lambda),\mathcal{G}^{m-1}(\Gamma)\mathcal{G}^{m-2}(\Gamma)\mathcal{T}^{m-3}(\Lambda),\cdots,\Lambda\prod^{m-1}_{d=1}\mathcal{G}^{d}(\Gamma),0,\cdots,0,\prod^{m-1}_{d=0}\mathcal{G}^{d}(\Gamma),0,\cdots\right].\end{split}$
(61)

where $k,m\in\mathbb{Z}^{+}$, and $e_{k,m}\left({d}_{t}\right)$ denotes the
belief probability assigned to ${d}_{t}$. The position of the entry
$\prod^{m-1}_{d=0}\mathcal{G}^{d}(\Gamma)$ is $k+m$, indicating that the
corresponding destination AoI of entry
$\prod^{m-1}_{d=0}\mathcal{G}^{d}(\Gamma)$ is $k+m$.

###### Proof.

Proposition 4 can be proved by induction. First, we show that

$\bm{e}(1,1)=\left[\overline{\Lambda},\overline{\Gamma},0,\cdots,0,\cdots\right].$
(62)

Assume the corresponding slot of this belief state is $t+1$. $k=1$ and $m=1$
imply that the AP observed $d_{t}=1$. According to the Markovian arrival
process, we have $A_{t-1}=1$, which represents that the probability of
$A_{t}=1$ is $\overline{\Lambda}$. Thus, by (57), the probability of
$d_{t+1}=1$ is $\overline{\Lambda}$ and the probability of $d_{t+1}=d_{t}+1=2$
(i.e., no packet arrival in slot $t$) is $\overline{\Gamma}$. This satisfies
Proposition 4.

Suppose $\bm{e}(1,m)$ satisfies (60). We first verify that $\bm{e}(1,m)$ is a
probability distribution. Following the fact that
$\mathcal{T}^{d}(\overline{\Lambda})+\mathcal{G}^{d}(\overline{\Gamma})=1,\forall
d\in\mathbb{N}$, the summation of the non-zero entries of $\bm{e}(1,m)$ from
the second one to the last one can be derived and simplified as follows

$\begin{split}&\mathcal{G}^{m-1}(\overline{\Gamma})\mathcal{T}^{m-2}(\overline{\Lambda})+\cdots+\mathcal{T}(\overline{\Lambda})\prod^{m-1}_{d=2}\mathcal{G}^{d}(\overline{\Gamma})\\\
&+\overline{\Lambda}\prod^{m-1}_{d=1}\mathcal{G}^{d}(\overline{\Gamma})+\prod^{m-1}_{d=0}\mathcal{G}^{d}(\overline{\Gamma})\\\
&=\mathcal{G}^{m-1}(\overline{\Gamma})\mathcal{T}^{m-2}(\overline{\Lambda})+\cdots+\mathcal{T}(\overline{\Lambda})\prod^{m-1}_{d=2}\mathcal{G}^{d}(\overline{\Gamma})+\prod^{m-1}_{d=1}\mathcal{G}^{d}(\overline{\Gamma})\\\
&=\mathcal{G}^{m-1}(\overline{\Gamma})\mathcal{T}^{m-2}(\overline{\Lambda})+\cdots+\prod^{m-1}_{d=2}\mathcal{G}^{d}(\overline{\Gamma})\\\
&\cdots\\\
&=\mathcal{G}^{m-1}(\overline{\Gamma})\mathcal{T}^{m-2}(\overline{\Lambda})+\mathcal{G}^{m-1}(\overline{\Gamma})\mathcal{G}^{m-2}(\overline{\Gamma})\\\
&=\mathcal{G}^{m-1}(\overline{\Gamma}).\end{split}$ (63)

It becomes clear that $\left\|\bm{e}(1,m)\right\|_{1}=1$ and
$e_{1,m}(d)\in[0,1],\forall d\in\mathbb{Z}^{+}$ , i.e., $\bm{e}(1,m)$ is a
distribution. According to Definition 2, $\bm{e}(1,m)$ reveals the expression
of the belief state of the local age of a node when the AP observed a status
update arrives $m$ consecutive unobserved slots after slot $t$ (i.e., in slot
$t+m$). Hence, in slot $t+m$, the belief probabilities of a packet arrival and
no packet arrival are $\mathcal{T}^{m}(\overline{\Lambda})$ and
$\mathcal{G}^{m}(\overline{\Gamma})$, respectively.

Now, we consider $\bm{e}(1,m+1)$, i.e., the local age belief state in slot
$t+m+1$. The value of $d_{t+m}$ could be equal to one of the positions of the
non-zero entries in $\bm{e}(1,m)$. Despite of the value of $d_{t+m}$,
$d_{t+m}$ transits to $d_{t+m+1}=1$ with probability
$\mathcal{T}^{m}(\overline{\Lambda})$. As such,
$e_{1,m+1}\left(1\right)=\left\|\bm{e}(1,m)\right\|_{1}\mathcal{T}^{m}(\overline{\Lambda})=\mathcal{T}^{m}(\overline{\Lambda})$.
On the other hand, the probability $d_{t+m}$ transits to $d_{t+m+1}=d_{t+m}+1$
is $\mathcal{G}^{m}(\overline{\Gamma})$, and hence
$e_{1,m+1}\left(d\right)=e_{1,m}\left(d-1\right)\mathcal{G}^{m}(\overline{\Gamma}),\forall
d>1$. Thus, the expression of $\bm{e}(1,m+1)$ is given by (64),

$\begin{split}\bm{e}(1,m+1)=\left[\mathcal{T}^{m}(\overline{\Lambda}),\mathcal{G}^{m}(\overline{\Gamma})\mathcal{T}^{m-1}(\overline{\Lambda}),\mathcal{G}^{m}(\overline{\Gamma})\mathcal{G}^{m-1}(\overline{\Gamma})\mathcal{T}^{m-2}(\overline{\Lambda}),\cdots,\overline{\Lambda}\prod^{m}_{d=1}\mathcal{G}^{d}(\overline{\Gamma}),\prod^{m}_{d=0}\mathcal{G}^{d}(\overline{\Gamma}),0,\cdots\right].\end{split}$
(64)

which follows Proposition 4.

Similarly, we can also prove (61), which is omitted for brevity. This
completes the proof.

∎

The belief state in Definition 2 is the distribution of the local age only,
while the completed belief state of a node also involves the destination AoI.
To this end, we define a group of belief states that have the destination AoI
equal to $k+m$ together with $\bm{e}(k,m)$ defined in Proposition 4 as
$\bm{E}(k,m)\triangleq\left\langle k+m,\bm{e}(k,m)\right\rangle$ for
$m,k\in\mathbb{Z}^{+}$. Denote by $\bm{\mathcal{E}}$ the collection of all
possible $\bm{E}(k,m)$. Then, we have the following corollary.

######  Corollary 3.

Suppose the network with the MAP has a belief state
$\bm{B}_{t,i}\in\bm{\mathcal{E}}$, then
$\bm{B}_{t^{\prime},i}\in\bm{\mathcal{E}}$ for any $t^{\prime}>t$.

The proof of Corollary 3 is similar to that of Corollary 1, and hence is
omitted for brevity.

## Acknowledgment

The authors would like to thank Tong Zhang and Yijin Zhang for their helpful
discussions on establishing the network model and problem formulation.

## References

  * [1] Y. Sun and K. R. Chowdhury, “Enabling emergency communication through a cognitive radio vehicular network,” _IEEE Communications Magazine_ , vol. 52, no. 10, pp. 68–75, 2014.
  * [2] J. Wan, S. Tang, Z. Shu, D. Li, S. Wang, M. Imran, and A. V. Vasilakos, “Software-defined industrial internet of things in the context of industry 4.0,” _IEEE Sensors Journal_ , vol. 16, no. 20, pp. 7373–7380, 2016.
  * [3] R. Talak, S. Karaman, and E. Modiano, “Speed limits in autonomous vehicular networks due to communication constraints,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_ , 2016, pp. 4998–5003.
  * [4] A. Kosta, N. Pappas, and V. Angelakis, “Age of information: A new concept, metric, and tool,” _Foundations and Trends in Networking_ , vol. 12, no. 3, pp. 162–259, 2017.
  * [5] M. A. Abd-Elmagid, N. Pappas, and H. S. Dhillon, “On the role of age of information in the internet of things,” _IEEE Communications Magazine_ , vol. 57, no. 12, pp. 72–77, 2019.
  * [6] X. Chen, C. Wu, T. Chen, H. Zhang, Z. Liu, Y. Zhang, and M. Bennis, “Age of information aware radio resource management in vehicular networks: A proactive deep reinforcement learning perspective,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 4, pp. 2268–2281, 2020.
  * [7] J. Liu, X. Wang, B. Bai, and H. Dai, “Age-optimal trajectory planning for uav-assisted data collection,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 553–558.
  * [8] M. A. Abd-Elmagid, A. Ferdowsi, H. S. Dhillon, and W. Saad, “Deep reinforcement learning for minimizing age-of-information in uav-assisted networks,” in _2019 IEEE Global Communications Conference (GLOBECOM)_ , 2019, pp. 1–6.
  * [9] R. D. Yates, “Age of information in a network of preemptive servers,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 118–123.
  * [10] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of information in vehicular networks,” in _2011 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks_ , 2011, pp. 350–358.
  * [11] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _2012 Proceedings IEEE INFOCOM_ , 2012, pp. 2731–2735.
  * [12] M. Desai and A. Phadke, “Internet of things based vehicle monitoring system,” in _2017 Fourteenth International Conference on Wireless and Optical Communications Networks (WOCN)_ , 2017, pp. 1–3.
  * [13] Y. Sun, I. Kadota, R. Talak, and E. Modiano, “Age of information: A new metric for information freshness,” _Synthesis Lectures on Communication Networks_ , vol. 12, no. 2, pp. 1–224, 2019.
  * [14] B. T. Bacinoglu and E. Uysal-Biyikoglu, “Scheduling status updates to minimize age of information with an energy harvesting sensor,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 1122–1126.
  * [15] Q. Wang, H. Chen, Y. Li, Z. Pang, and B. Vucetic, “Minimizing age of information for real-time monitoring in resource-constrained industrial iot networks,” in _2019 IEEE 17th International Conference on Industrial Informatics (INDIN)_ , vol. 1, 2019, pp. 1766–1771.
  * [16] J. Pan, A. M. Bedewy, Y. Sun, and N. B. Shroff, “Minimizing age of information via scheduling over heterogeneous channels,” in _Proceedings of the Twenty-Second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing_ , ser. MobiHoc ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 111–120. [Online]. Available: https://doi.org/10.1145/3466772.3467040
  * [17] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,” _IEEE Transactions on Information Theory_ , vol. 62, no. 4, pp. 1897–1910, 2016.
  * [18] Q. He, D. Yuan, and A. Ephremides, “On optimal link scheduling with min-max peak age of information in wireless systems,” in _2016 IEEE International Conference on Communications (ICC)_ , 2016, pp. 1–7.
  * [19] B. Dedhia and S. Moharir, “You snooze, you lose: Minimizing channel-aware age of information,” in _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. IEEE, 2020, pp. 1–8.
  * [20] 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 Transactions on Information Theory_ , vol. 63, no. 11, pp. 7492–7508, 2017.
  * [21] S. Leng and A. Yener, “Age of information minimization for an energy harvesting cognitive radio,” _IEEE Transactions on Cognitive Communications and Networking_ , vol. 5, no. 2, pp. 427–439, 2019.
  * [22] I. Kadota, A. Sinha, and E. Modiano, “Optimizing age of information in wireless networks with throughput constraints,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications_ , 2018, pp. 1844–1852.
  * [23] S. Farazi, A. G. Klein, and D. R. Brown, “Average age of information for status update systems with an energy harvesting server,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 112–117.
  * [24] E. T. Ceran, D. Gündüz, and A. György, “Reinforcement learning to minimize age of information with an energy harvesting sensor with harq and sensing cost,” in _IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2019, pp. 656–661.
  * [25] J. P. Champati, H. Al-Zubaidy, and J. Gross, “Statistical guarantee optimization for age of information for the d/g/1 queue,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 130–135.
  * [26] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Scheduling policies for minimizing age of information in broadcast wireless networks,” _IEEE/ACM Transactions on Networking_ , vol. 26, no. 6, pp. 2637–2650, 2018\.
  * [27] J. Sun, Z. Jiang, B. Krishnamachari, S. Zhou, and Z. Niu, “Closed-form whittle’s index-enabled random access for timely status update,” _IEEE Transactions on Communications_ , vol. 68, no. 3, pp. 1538–1551, 2020\.
  * [28] I. Kadota and E. Modiano, “Minimizing the age of information in wireless networks with stochastic arrivals,” _IEEE Transactions on Mobile Computing_ , vol. 20, no. 3, pp. 1173–1185, 2021.
  * [29] A. Gong, T. Zhang, H. Chen, and Y. Zhang, “Age-of-information-based scheduling in multiuser uplinks with stochastic arrivals: A pomdp approach,” in _GLOBECOM 2020 - 2020 IEEE Global Communications Conference_ , 2020, pp. 1–6.
  * [30] Y.-P. Hsu, E. Modiano, and L. Duan, “Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals,” _IEEE Transactions on Mobile Computing_ , vol. 19, no. 12, pp. 2903–2915, 2020.
  * [31] Z. Chen, N. Pappas, E. Björnson, and E. G. Larsson, “Age of information in a multiple access channel with heterogeneous traffic and an energy harvesting node,” in _IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2019, pp. 662–667.
  * [32] E. T. Ceran, D. Gündüz, and A. György, “A reinforcement learning approach to age of information in multi-user networks with harq,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 5, pp. 1412–1426, 2021.
  * [33] Q. Wang, H. Chen, C. Zhao, Y. Li, P. Popovski, and B. Vucetic, “Optimizing information freshness via multiuser scheduling with adaptive noma/oma,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 3, pp. 1766–1778, 2022.
  * [34] M. J. Neely, “Stochastic network optimization with application to communication and queueing systems,” _Synthesis Lectures on Communication Networks_ , vol. 3, no. 1, pp. 1–211, 2010.
  * [35] C. H. Papadimitriou and J. N. Tsitsiklis, “The complexity of markov decision processes,” _Mathematics of operations research_ , vol. 12, no. 3, pp. 441–450, 1987.
  * [36] G. Yao, A. M. Bedewy, and N. B. Shroff, “Age-optimal low-power status update over time-correlated fading channel,” in _2021 IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 2972–2977.
  * [37] E. Sert, C. Sönmez, S. Baghaee, and E. Uysal-Biyikoglu, “Optimizing age of information on real-life tcp/ip connections through reinforcement learning,” in _2018 26th Signal Processing and Communications Applications Conference (SIU)_ , 2018, pp. 1–4.
  * [38] Y. Shao, Q. Cao, S. C. Liew, and H. Chen, “Partially observable minimum-age scheduling: The greedy policy,” _IEEE Transactions on Communications_ , pp. 1–1, 2021.
  * [39] D. A. McAllester and S. Singh, “Approximate planning for factored pomdps using belief state simplification,” _arXiv preprint arXiv:1301.6719_ , 2013.
  * [40] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra, “Planning and acting in partially observable stochastic domains,” _Artificial intelligence_ , vol. 101, no. 1-2, pp. 99–134, 1998.
  * [41] N. L. Zhang and W. Zhang, “Speeding up the convergence of value iteration in partially observable markov decision processes,” _Journal of Artificial Intelligence Research_ , vol. 14, pp. 29–51, 2001.
  * [42] F. Chiariotti, J. Holm, A. E. Kalør, B. Soret, S. K. Jensen, T. B. Pedersen, and P. Popovski, “Query age of information: Freshness in pull-based communication,” _IEEE Transactions on Communications_ , vol. 70, no. 3, pp. 1606–1622, 2022.
  * [43] K. Liu and Q. Zhao, “Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access,” _IEEE Transactions on Information Theory_ , vol. 56, no. 11, pp. 5547–5567, 2010.