1

Timely Status Update in Massive IoT Systems:
Decentralized Scheduling for Wireless Uplinks

arXiv:1801.03975v1 [cs.IT] 11 Jan 2018

Zhiyuan Jiang, Bhaskar Krishnamachari, Xi Zheng, Sheng Zhou, Zhisheng Niu, Fellow, IEEE

Abstract—In a typical Internet of Things (IoT) application
where a central controller collects status updates from multiple
terminals, e.g., sensors and monitors, through a wireless multiaccess uplink, an important problem is how to attain timely status
updates autonomously. In this paper, the timeliness of the status
is measured by the recently proposed age-of-information (AoI)
metric; both the theoretical and practical aspects of the problem
are investigated: we aim to obtain a scheduling policy with
minimum AoI and, meanwhile, still suitable for decentralized
implementation on account of signalling exchange overhead.
Towards this end, we first consider the set of arrival-independent
and renewal (AIR) policies; the optimal policy thereof to minimize the time-average AoI is proved to be a round-robin policy
with one-packet (latest packet only and others are dropped)
buffers (RR-ONE). The optimality is established based on a
generalized Poisson-arrival-see-time-average (PASTA) theorem.
It is further proved that RR-ONE is asymptotically optimal
among all policies in the massive IoT regime. The AoI steadystate stationary distribution under RR-ONE is also derived. A
fully decentralized implementation of RR-ONE is proposed which
can accommodate dynamic terminal appearances. In addition,
considering scenarios where packets cannot be dropped, the
optimal AIR policy thereof is also found with parameters given
by the solution to a convex problem.
Index Terms—Internet of Things, status update, age-ofinformation, wireless multiaccess channel, queuing theory

I. I NTRODUCTION
Internet of Things (IoT) represents one of the biggest
paradigm shifts recently which can revolutionize the information technology and several aspects of everyday-life such
as living, e-health and driving; it envisions to transform every
physical object into an intelligent individual that is capable
of sensing, communicating and computing. By 2021, Ericsson
predicts that there will be around 28 billion IoT devices and a
large share of them are empowered by wireless communication
technologies [2]. The wireless communication community has
dedicated a significant amount of efforts to accommodate such
a massive number of emerging IoT devices; in particular, it is
one of the main targets of the 5G system that 100-fold more
connected devices per geographical area should be supported
compared with current LTE systems [3]. In addition to the
Z. Jiang, X. Zheng, S. Zhou and Z. Niu are with Tsinghua National
Laboratory for Information Science and Technology, Tsinghua University,
Beijing 100084, China. Emails: {zhiyuan@, zhengx14@mails., sheng.zhou@,
niuzhs@}tsinghua.edu.cn.
B. Krishnamachari is with the Ming Hsieh Department of Electrical
Engineering, University of Southern California, Los Angeles, CA 90089,
USA. Email: bkrishna@usc.edu.
This work is sponsored in part by the Nature Science Foundation of China
(No. 61701275, No. 91638204, No. 61571265, No. 61621091), the China
Postdoctoral Science Foundation, and Hitachi Ltd. Part of the work has been
submitted to IEEE International Symposium of Information Theory 2018 [1].

AoI

Monitoring pkts./
Data samples

Delay of
Sample 3
Packet queue

Destination

Fig. 1. A status update example with one source (sampler), one destination
and a single queue to illustrate AoI.

sheer amount of IoT devices, it is also desired to enhance the
timeliness of services for time-critical applications whereby
the service quality depends heavily on the freshness of the
monitoring data collected from IoT devices, e.g., the Tactile
Internet and autonomous driving [4].
Age-of-information (AoI) is a recently proposed metric
specifically to quantify such timeliness [5]–[11]; it is a constantly evolving information monitoring delay at a destination
node, or simply put, time elapsed since the last-updated
packet’s generation. This definition jointly accounts for the
delay introduced by sampling the information source and data
communication, which distinguishes AoI from the conventional end-to-end communication (queuing and transmission)
delay metric [12], [13]. Consider a concrete example in Fig.
1. The AoI only coincides with the communication delay at
the time when a status update packet is delivered; another
distinct difference is that the communication delay is defined
for each packet; in contrast, the AoI is a constantly evolving
measurement at the destination. The AoI characterizes the
knowledge freshness of remote information sources at the destination. This knowledge and its timeliness are both essential
for real-time applications. The wireless communication system
is therefore well motivated to optimize the AoI, however, this
objective may deviate from the conventional throughput- or
delay-oriented paradigms since it has been shown that the
optimization of AoI leads to distinctively different system
designs, e.g., sampling strategy and service principle [6].
One of the fundamental restrictions of wireless communication systems is that transmissions are subject to interference
due to the broadcast nature of electromagnetic waves, leading
to the fact that IoT terminals cannot transmit simultaneously;
otherwise collisions happen and transmissions fail with no data
delivered. Therefore, terminals should be carefully scheduled
to avoid such collisions; as a result, delay is introduced.
For instance, a simple scheduling strategy is that terminals
take turns to update their status data to avoid collisions.
Intriguingly, we will show that taking turns (a round-robin
scheduling policy with proper packet management) is, to some

𝑡

2

extent, the optimal policy without entailing a large amount of
signalling overhead.
The overhead issue touches upon another important design
principle in wireless multiaccess uplinks, especially with massive distributed IoT devices, that is the policy design is preferably decentralized, i.e., decisions are made autonomously at
terminals and require only local information. For instance, the
carrier-sensing-medium-access (CSMA) protocol is a widelyused and successful application of decentralized protocol in
wireless networks [14]. In particular, terminals transmit based
on a contention protocol and scheduling decisions are made
in a decentralized manner. However, the CSMA protocol is
designed only for throughput maximization and may face
severe challenges in status update systems.
Concerning the aforementioned scenario and corresponding
challenges, the contributions of this paper include:
•

•

•

•

Among arrival-independent renewal (AIR) scheduling
policies, whose decisions are independent with packetarrival processes and hence decentralization-friendly, a
round-robin policy with one-packet buffers (only retains
the most up-to-date packet and others are discarded) at
terminals (RR-ONE) is proved optimal. The proof technique leverages a generalized Poisson-arrival-see-timeaverage (PASTA) theorem which, as far as we know, has
not been adopted in the related literature before.
RR-ONE is proved asymptotically optimal among all
policies with a massive number of terminals. It is shown
that the optimum time-average AoI is proportional to the
number of terminals asymptotically; the optimum linear
scaling factor is 21 . RR-ONE is proved to achieve the
optimum scaling factor. The CSMA protocol is however
shown to have (at least) a scaling factor of 1; hence
its time-average AoI is arbitrarily larger than RR-ONE
asymptotically. In addition, the AoI steady-state stationary distribution under RR-ONE is also derived.
A full-fledged decentralized implementation of RR-ONE
is described; it is capable of adapting to dynamic terminal appearances which is essential for decentralized
algorithms. Thereby, the only global information required
for each terminal is the total number of terminals; this
is obtained by a common broadcast message from the
central controller.
Considering scenarios wherein arrival packets are queued
and first-come-first-served (FCFS) at terminals without
any packet management, e.g., packet dropping, the optimal AIR policy thereof is also found: it schedules every
terminal based on deterministic intervals, with intervals
given as the solution to a convex optimization problem;
an approximate closed-form solution, which is shown to
be optimal with heavy traffic, is also derived.

The remainder of the paper is organized as follows. In
Section II, the system model is introduced; the problem of
AoI minimization is then formulated; for clarity, we present
our main results here and detailed proofs and explanations
are conveyed in the subsequent sections. In Section III, we
show that RR-ONE is the optimal AIR policy. In Section IV,
the asymptotic optimality is proved. In Section V, the station-

Coverage
Area

Terminal 3

Terminal 2
Packet queue (PM)

Packet queue
(PM)

Subject to
collisions

Terminal 1

Terminal 4

Central
Controller
Packet queue (PM)

Decision (sched. and
packet management (PM))

…

Update and
transmit

Packet queue (PM)

Packet arrival

AoI ← AoI + 1

Time Slot

Fig. 2. Considered system architecture and status update procedure.

ary distribution under RR-ONE is derived. In Section VI, a
decentralized protocol is presented. Section VII presents the
optimal AIR policy without performing packet management.
Section VIII presents simulation results. Finally, in Section IX,
conclusions are drawn and discussions are made. The proofs
of several lemmas are shown in the appendix.
A. Related Work
An AoI optimization problem can be posed as minimizing the time-average AoI at the receiver by controlling the
sampling rate at the terminal. All the sampled data packets
go through an M/M/1 queue as shown in Fig. 1.1 There is a
subtle, in most cases tradeoff, relationship between throughput
and AoI: Sampling frequently results in a high throughput
and a low sampling delay but may introduce a large queuing
delay; on the other hand, sampling at a low rate introduces a
large sampling delay, whereas the queuing delay is reduced.
Queuing analysis reveals that there exists an optimal sampling
rate, assuming the generated packets are queued and the
service is FCFS [6]; M/D/1 and D/M/1 queues are also
considered therein.
Since its inception, AoI has received wide research attentions and there have been several extensions. Regarding
multiple sources sharing one queue, and hence multiple corresponding AoIs, Yates and Kaul [7], [8] derive the minimum
time-average AoI region under M/M/1 queuing model and
different service disciplines, e.g., FCFS, last-come-fist-served
(LCFS), LCFS with preemption. The service process can be
extended to obey general distributions; in this regard, the
average peak-AoI (PAoI) for multiple sources is obtained,
and the problem of optimizing update rates is considered by
Huang and Modiano [15]. The scheduling problem for multiple
servers and a single queue with job replication is considered
by Bedewy et al. [16]. The AoI performance is shown to
be improved by proper packet management, e.g., LCFS with
preemption [17] and packet dropping mechanism [18], based
on the intuition that the last-arrived packet has the least age.
However, considering service interruption, always prioritizing
1 The AoI evolution in this paper is based on discrete time slots; whereas
the AoI changes continuously in Fig. 1 and Fig. 4 for ease of exposition.

3

a new packet may result in performance degradation [19]. The
optimization of sampling time without considering queuing
delay is studied by Sun et al. [20]; they show that even without
queuing delay the source should wait a certain time before
sampling again to minimize time-average AoI due to service
time uncertainty.
The study of the multi-queue scheduling problem is the most
relevant work to ours [9], [10], [21]. Hsu et al. approach this
problem in the wireless broadcast channel where the scheduling decisions are centralized; they prove the optimal policy
is age-threshold-based. The scheduling problem of multiple
sources inside a finite-length transmission frame to minimize
AoI is proved NP-hard [10]. Joo and Eryilmaz propose that the
status updates from multiple sources should be synchronized
in applications such as network monitoring and distributed
sensing; they develop a drift-based approach to address the
issue [11]. The Whittle’s index [22] is leveraged by Kadota et
al. [9] based on a restless multi-armed-bandit formulation; it
is shown that an age-greedy policy is optimal in the symmetric
case and the Whittle’s index is derived for asymmetric cases.
The major distinction between our formulation and existing work is that we consider the following scenario: 1)
status packets arrive at random time slots at terminals; 2)
limited information is available for the policy decisions to
facilitate decentralized implementation. The considered scenario is justified in massive IoT status update systems: status
variation is unpredictable, and hence update packets, which
are used to monitor status variation, are randomly generated;
transmissions happen in a wireless multiaccess uplink where
scheduling decisions are preferably decentralized to avoid
overhead explosion. As far as we know, no existing work on
AoI optimization has addressed a practical scenario involving
both aspects.

slots. Denote time-average AoI over infinite time horizon as
)
h̄π(∞,N ) , lim h̄(T,N
.
π
T →∞

(2)

The evolution of AoI can be written as
Y
hn,π (t + 1) = hn,π (t) − Un,π (t)
(1 − Um,π (t))gn (t) + 1,
m6=n

(3)
where gn (t) denotes the AoI reduction with a successful
update from terminal n. Consequently, we have gn (t) = 0
when queue-n is empty at time t. The AoI for each terminal
always increases by one after each time slot. Based on this
definition (3), whenever a collision happens, i.e., more than
one terminals transmit in the same time slot, no status is
updated. Note that transmission failures only happen with
collisions, otherwise the transmission is always assumed successful; this corresponds to the interference-limited regime
which is emerging to be the main application scenario in the
future ultra-dense networks [23], and therein failures due to
noise is negligible. In addition, denote the time-average AoI
of terminal-n under policy π as
)
h̄(T
n,π ,

T
1X
hn,π (t).
T t=1

(4)

(1)

The status update procedure is described in Fig. 2. We
assume the following sequence of events in each time slot.
At the beginning of each time slot, scheduling decisions are
made, including:
• Terminal scheduling: Decide which terminal, or a set of
terminals2 , updates and transmits in this time slot.
• Packet management: Once scheduled, the terminal can
apply a packet management scheme, e.g., it can choose
a packet from its queue to update in the time slot, or
drop several packets. In contrast, packets are queued and
served based on an FCFS manner without any packet
management.
Based on the decision, the scheduled terminal transmits its
update packet (assuming one packet is transmitted in each time
slot), and thereby the AoI is refreshed at the BS. Afterwards,
packets arrive randomly at terminals (the age of newly arrived
packets is zero) and then the ages of all packets and all AoIs
increase by one. This marks the end of a time slot in our
model. The AoI at one time slot is defined as the AoI at the
end of the time slot after status update and natural growth.
The objective considered in this paper is to minimize the
infinite-horizon time-average AoI (2) over all policies.3 As a
first step, the following definition and Lemma 1 (cf. proof
in Appendix B) enable us to only consider work-conserving
non-collision (WCNC) policies without loss of optimality.
Definition 1 (WCNC policy): A WCNC policy is defined as
a policy that is not idle when there is at least one packet
in terminal queues, nor schedule more than one terminals
simultaneously.


where the AoI at the t-th time slot for terminal n based on
policy π is denoted by hn,π (t), and the time horizon is T time

2 This case is described only for completeness and not considered in this
paper since it results in a collision.
3 Hereinafter, we refer to (2) as time-average AoI for simplicity.

II. S YSTEM M ODEL , P ROBLEM F ORMULATION AND M AIN
R ESULTS
Consider a base station (BS), alternatively referred to as
central controller, which is responsible for collecting status
update packets from a large number of IoT devices as shown
in Fig. 2. A time-slotted system is considered. The status
update packets are generated and stored at terminal queues.
The queue buffer size for every terminal is assumed to be
identical and denote by B. The number of packets generated
at time t of terminal n is denoted by Ln (t) and Ln (t) is
assumed to be a Bernoulli random variable with parameter λn ;
the arrival processes {Ln (t), t = 1, 2, ...}, n ∈ {1, ..., N } are
independent over terminals and time. The number of terminals
is denoted by N . Let Un,π (t) denote the scheduling decision
of terminal n at time t for a given policy π, i.e., Un,π (t) = 1
if terminal n is scheduled and Un,π (t) = 0 otherwise.
The T -horizon time-average AoI is denoted by
h̄π(T,N ) ,

T
N
1 XX
hn,π (t),
T N t=1 n=1

4

0.01

and only retains the last-arrival packet at each terminal. The
time since last update from terminal m is denoted by τm . 
Theorem 1: RR-ONE is the optimal AIR policy to minimize
the time-average AoI, with

Steady-state probability

0.008

0.006

(∞,N )

h̄RR

=

0.004

0.002

0
0

20

40

60

80

100

120

140

160

N
N −1
1 X 1
+
.
N n=1 λn
2

(6)


Theorem 2: RR-ONE is asymptotically optimal among all
policies in the massive IoT regime; it achieves the optimum
asymptotic scaling factors, i.e.,

AoI (time slots)
(∞,N )

(∞,N )

h̄RR
N →∞
N

Fig. 3. Steady-state stationary distribution of AoI under RR-ONE. The blue
dotted curve represents a uniform distribution on {1, ..., N } when λ = 1
since in this case the AoI evolves periodically from 1 to N (Lemma 4).

lim

h̄opt
N →∞
N

= lim

=

1
, ∀λi ,
2

(7)

and
Lemma 1: For a non-WCNC policy, there exists at least one
WCNC policy that achieves lower AoI.

For practical concerns that the policy decisions should be
decentralized, and also mathematical tractability, consider AIR
policies defined as follows. Denote the resultant scheduling
(k)
interval process of terminal-n based on policy π as Xn,π ,
k = 1, 2, ... where k is the scheduling interval index. Define
Rn,π (t) as the counting process of scheduling times before
Pr
(k)
time t for terminal n, i.e., Rn,π (t) , sup{r : k=0 Xn,π ≤
t}.
Definition 2 (AIR policy): A policy π is an AIR policy if
the following conditions are both met.
(k)

(i) The scheduling interval processes {Xn,π , n = 1, ..., N }
are independent with the packet arrival processes at terminals, with finite first and second raw moments denoted
by mn and vn respectively.
(ii) The counting processes Rn,π (t), n = 1, ..., N are renewal
processes.

By definition, the set of AIR policies is essentially a subset
of all policies. The condition (i) is in fact reflecting the
practical perspective that the scheduling decisions are desired
to be independent of the packet arrival processes to enable
decentralized implementation and reduce signalling exchange
overhead. The condition (ii) does enforce an additional constraint that the scheduling intervals are i.i.d.; however the
distributions can be arbitrary as long as they have finite
first and second moments. Note that, notwithstanding these
conditions, it is found (Theorem 2) that the optimal AIR policy
with proper packet management is asymptotically optimal
among all policies in the massive IoT regime.

(∞,N )

lim λi h̄RR

1
λi

→∞

(∞,N )

= 1lim λi h̄opt
λi

→∞

∀λj,j6=i and N,

=

1
,
N
(8)

(∞,N )

where h̄opt
denotes the minimum time-average AoI.

Corollary 1: The minimum time-average AoI is proportional
to the number of terminals asymptotically, and the optimum

scaling factor is 12 .
We emphasize that the asymptotic optimality of RR-ONE
is among all policies, including policies requiring global
information, e.g., terminals’ queue lengths, age of all packets,
and even non-causal policies which know future packet arrivals
(by observing that the proof of Theorem 2 also applies in this
case).
Theorem 3: The AoI evolution of terminal-n based on
RR-ONE follows a Markov renewal process with a fixed
renewal time of N time slots, and the steady-state stationary
distribution is

A. Main Results


j

 1 − (1 − λn ) ,

1 ≤ j ≤ N;
N
µn (j) =
j−N

 (1 − λn )

(1 − (1 − λn )N ), j ≥ N + 1,
N
(9)
where µn (j) denotes the probability that the steady state AoI
of terminal-n is j.

The steady-state stationary distribution in (9) is instantiated,
and an insight is described in Fig. 3.
Theorem 4: The optimal AIR policy without packet management to minimize the time-average PAoI (35) is to schedule
each terminal based on a deterministic scheduling interval4 .

Definition 3 (RR-ONE): RR-ONE, denoted by RR in the
subscript, is defined as a policy that schedules the nRR -th
terminal at each time slot which satisfies


nRR = min n : τn = max τm ,
(5)

4 This may not be possible given the fact that the optimal scheduling
intervals can be fractional numbers, and that different terminals’ scheduling
arrangements may conflict with each other. Nevertheless, this complication can
be addressed by adopting a policy that approximately satisfies the conditions
with minimal performance degradation.

m=1,...,N

5

The scheduling interval for terminal-n is given by m∗n = β1∗
n
where βn∗ is the solution of the convex optimization problem:


N 
1 X 1
1
1
1
P2:
minimize
+
+
βn n=1,...,N N
λn
2 βn − λn
βn
n=1
s.t., βn > λn , ∀n = 1, ..., N,
N
X

βn = 1.

(10)

n=1

The corresponding policy is referred to as RR-λ.

An important note is that both RR-ONE and RR-λ can
be easily adapted for decentralized implementation. Roughly
illustrated for RR-ONE, each terminal is assigned a unique
time slot to transmit in a frame of length N , and only retains
the most up-to-date packet in its buffer. A detailed protocol
which accounts for variable N , i.e., random terminal appearances, is described in Section VI. Although RR-λ requires the
statistical knowledge of packet arrival rates of terminals, it is
independent with the instantaneous system state and therefore
the overhead is acceptable. In the following sections, we will
prove our main results and elaborate on their implementations
and implications.
III. P ROOF OF T HEOREM 1: O PTIMAL AIR P OLICY
The quest for the optimal policy, among all policies with
any given N , to minimize the time-average AoI seems elusive,
because the problem can be essentially viewed as a restless
multi-armed bandit problem with time- and arm-correlated
reward functions [24]. Besides, there is a strong probability
that the optimal policy requires global information exchange
and hence decentralization-unfriendly. Therefore, in this section, we resolve to derive the optimal AIR policy to minimize
the time-average AoI in (2) following a generalized Poissonarrival-see-time-average (PASTA) theorem, i.e., the arrivalsee-time-average (ASTA) property with a Markov state process
as the observed process and an independent outside observer
[25]. First, consider the queue evolution of terminal-n based
on AIR policies; it is similar with an M/G/1 queue given
the definition of AIR policies, with a subtle, but important,
difference that the service (in this case the service time is
the scheduling interval) begins immediately after a packet
departure, even if there is no packet waiting in the queue. In
the case that there is no packet is in the queue, the service
proceeds independently till the end, i.e., scheduled, during
which period two possible circumstances can occur: 1) there
are (at least one) packet arrivals and thereby one of the packets
is updated under a certain packet management policy; 2) there
is no packet arrival and consequently no packet is updated.
It is clear that under this queue model, the optimal packet
management, under arbitrary scheduling policy, is to always
update the most up-to-date packet, i.e., the packet that arrives
the last; the resultant queue is equivalent to having a buffer
size of one and storing only the latest arrival packet. Note
that this packet management policy is not necessarily optimal
with preemptive service model due to service interruption [26].
Without loss of optimality, we only consider the one-packet
buffer packet management policy in the rest of the section.

The age of the packet in queue-n (buffer size is one) is
denoted by An (t), t = 1, 2, ..., a sample path of which is
shown in the left of Fig. 4. Upon a packet arrival, e.g., ai in
Fig. 4, the age An (t) drops to one (measured at the end of the
time slot) based on the procedure in Fig. 2. When terminal-n
is scheduled at the time of si , the AoI at the BS is updated
to the age of the packet at terminal n, i.e., An (si ). Note that
we prescribe a generalized age of An (si ) that between each
update and next packet arrival, e.g., between s1 and a1 , An (t)
equals the AoI of terminal n at the BS although there is no
packet in the queue during the time. By doing this, we make
An (t) evolve independently with hn,π (t) while not affecting
the AoI update procedure; this is crucial for the ASTA property
to apply.
Based on the renewal process condition of AIR policies, and
following the same arguments in, e.g., [26], the time-average
AoI can be readily calculated by the sum of the geometric
areas Qk,n in Fig. 4:
(∞,N )
h̄n,π

K
K
K
1 X
K 1 X
Qk,n = lim
lim
Qk,n
= lim
T →∞ T K→∞ K
T →∞ T K
k=1

k=1

E[Qk,n ]
=
.
mn

(11)

The last equality is based on the elementary renewal theorem
[27]. It then follows that
#
"

 X (k)
1
n,π
(∞,N )
(k)
(k)
h̄n,π
=
E Xn,π An (sk ) + Xn,π − 1
mn
2

 h
i
1
(a) 1
(k)
=
E Xn,π E [An (sk )] + (vn − mn )
mn
2
vn − m n
= E [An (sk )] +
2mn
(b)
mn − 1
≥ E [An (sk )] +
,
(12)
2
where the equality (a) is based on the arrival-independent
condition of AIR policies, and the inequality (b) follows from
vn ≥ m2n ; note that the equality holds when the scheduling
interval is a constant mn .
It is now clear that the main challenge is to calculate
E [An (sk )]. First we have Lemma 2 (cf. proof in Appendix
B) which shows that {An (t), t = 1, 2...} is a Markov state
process and its stationary distribution is given in (13).
Lemma 2: {An (t), t = 1, 2...} is a Markov state process
with the steady-state stationary distribution given as
µn (j) = λn (1 − λn )j−1 ,

(13)

where µn (j) denotes the probability that the steady state of
terminal n is state j (age of packet at terminal-n equals j). 
Then the challenge of calculating E [An (sk )] is tackled by
treating E [An (sk )] as the average state value of a Markov
state process by an independent outside observer. Armed with
this, we invoke the ASTA property [25] which can be seen as
a generalization of the well-known PASTA theorem to nonPoisson observers.
Lemma 3: [25, Theorem 3.14] Let U be a Markov state
process and N be a counting process. Then ASTA holds for

6

the pair (U, N ) if U is left-continuous and the pair (U, N ) is
forward-pointwise independent, i.e., for all t > 0, U (t) and
{N (t + s) − N (s) : s ≥ 1} are independent.

Let U be {An (t), t = 1, 2...}, and N in Lemma 3 be the
counting process of the number of scheduling times before
time t. Then based on the AIR policy conditions, U and N
are independent. The continuous condition follows by design
of update sequence described in Fig. 2. Therefore, we obtain
K
1 X
1
An (sk ) = E [An (t)] =
. (14)
K→∞ K
λn

E [An (sk )] = lim

k=1

In other words, the time-average of random sampling (sk )
of the Markov process {An (t), t = 1, 2...} equals the steadystate average. Combining with (12), the time-average AoI is

N
N 
1 X
mn − 1
1 X (∞,N )
)
h̄
≥
E
[A
(s
)]
+
h̄(∞,N
=
n k
π
N n=1 n,π
N n=1
2


N
1 X 1
mn − 1
. (15)
=
+
N n=1 λn
2
The update rate of all terminals equals one packet per time
slot for WCNC policies; therefore, according to the elementary
renewal theorem,
N
X
1
= 1.
(16)
m
n
n=1
It follows from the arithmetic-harmonic-mean inequality
(equality holds when mn = N , ∀n = 1, ..., N ) and (15) that
)
h̄(∞,N
π

N
N −1
1 X 1
.
+
≥
N n=1 λn
2

(17)

The equality holds in (17) under two conditions: 1) mn =
N , ∀n = 1, ..., N ; 2) the scheduling interval is a constant mn .
These two conditions can be both satisfied with RR-ONE. For
a sanity check, RR-ONE is indeed an AIR policy. With this,
we can conclude the proof of Theorem 1.
Remark 1: Alert readers may be curious about the optimal
policy in general. In particular, since a myopic policy (minimize the AoI in the next time slot) is optimal [9, Theorem 1]
when we eliminate the randomness of arrival packets (λ = 1),
i.e., the AoI is updated to one (or zero) every time, is it optimal
in general? A counter example is given in Appendix A to
show that the myopic policy is not optimal even with global
state information (GSI), e.g., queue length, age of packets
and arrival rates information, at least with finite horizon.
Nevertheless, we conjecture that the myopic policy with GSI
is close to optimal with infinite horizon, and it is adopted as
a performance benchmark in Section VIII to investigate the
value of GSI.
IV. P ROOF OF T HEOREM 2: A SYMPTOTIC O PTIMALITY
In IoT systems, one major challenge is to accommodate
a large number of terminals while maintaining timely status
updates. Hence, it is of central interest to consider the problem
in the asymptotic regime. Towards this end, it will be shown
in the following that RR-ONE, given its simple structure,

is asymptotically optimal among all policies with arbitrary
information and even non-causal packet arrival knowledge.
First, we obtain two performance bounds and compare these
with the achievable performance by RR-ONE; the conclusion
follows by showing that they have identical asymptotic scaling
factors.
First, we introduce two lower bounds of the time-average
AoI of any policies in Lemma 4 and Lemma 5 (cf. proof in
Appendix B).
Lemma 4: The time-average AoI in (2) cannot be less than
N +1
2 , i.e.,
N +1
, ∀N = 1, 2, ..., λn ∈ [0, 1], n ∈ {1, ..., N }.
2
(18)

Lemma
5:
The
time-average
AoI
in
(1)
cannot
be
less
than
PN 1
1
n=1 λn , i.e.,
N

h̄π(∞,N ) ≥

)
h̄(∞,N
≥
π

N
1 X 1
, ∀N = 1, 2, ..., λn ∈ [0, 1],
N n=1 λn

n ∈ {1, ..., N }.

(19)


It follows that the minimum time-average AoI, denoted by
(∞,N )
h̄opt
, cannot be less than either bound, i.e.,
#
"
N
N +1 1 X 1
(∞,N )
,
.
(20)
h̄opt
≥ max
2
N n=1 λn
After obtaining two lower bounds in Lemma 4 and 5, combining with the achievable AoI derived in (17), we can prove
the asymptotic optimality of RR-ONE; the optimum scaling
result follows immediately. Based on Lemma 4, Lemma 5 and
Theorem 2, it follows that ∀N, λ1 , ..., λN ,
"
#
N
N
N +1 1 X 1
1 X 1 N −1
(∞,N )
max
,
≤ h̄opt
≤
+
.
2
N n=1 λn
N n=1 λn
2
(21)
For any fixed λn , n = 1, ..., N , divide both sides of (21) by
N , and let N goes to infinity, we obtain
h
i
PN
max N2+1 , N1 n=1 λ1n
1
lim
= ,
N →∞
N
2
PN 1
1
N −1
+
1
n=1 λn
2
= ,
(22)
lim N
N →∞
N
2
and therefore (7) follows. The scaling results for RR-ONE
follows directly from (34). Similarly ∀n,
h
i
PN
max N2+1 , N1 n=1 λ1n
1
= ,
lim
1
1
N
→∞
λn
λn
PN 1
1
N −1
1
n=1 λn + 2
N
lim
= ,
(23)
1
1
N
→∞
λn
λn
and (8) follows, which concludes the proof of Theorem 2.
Remark 2: Theorem 2 shows that the optimum time-average
AoI scales linearly with the number of terminals N and
expected inter-arrival time, i.e., λ1n , ∀n. The optimum scaling

7

Peak
AoI

Scheduling
(Sampling)

1

Fig. 4. Age of the packet at terminal-n assuming one packet buffer (left) and AoI at the BS (right).

factors are also given. Moreover, we show that RR-ONE not
only can achieve linear scaling, but also achieves the optimum
scaling factors.
Remark 3: By setting λn = 1, ∀n in Theorem 2 which is
equivalent to a scenario wherein the age after every update is
always one, it is immediately obvious that RR-ONE is optimal
in this setting with arbitrary N .
Corollary 2: The time-average AoI achieved by a uniformly
random scheduling policy with one-packet buffers (UN-ONE)
is at least
(∞,N )
h̄UN
≥ N.
(24)
Proof: Consider running the UN-ONE policy in system
A0 (Lemma 4). Obviously this gives us a lower bound on the
UN-ONE performance. In this case, the system state is fully
characterized by the AoI of each terminal, and the AoI for each
terminal (omitting the terminal index for brevity) evolves as


1
1
, ph,1 = , ph,i = 0, ∀i 6= 1, h + 1.
ph,h+1 = 1 −
N
N
(25)
Note that although the AoI transitions of different terminals
are not independent by observing, e.g., only one terminal can
be scheduled at each time slot, the time-average AoI in (2)
only concerns with the marginal distribution of AoI for each
terminal. The AoI transition Markov chain of one terminal is
shown in Fig. 5.

1

2

…

H

V. P ROOF OF T HEOREM 3: AO I S TATIONARY
D ISTRIBUTION UNDER RR-ONE
Although the time-average AoI under RR-ONE has been
derived in Section III based on the ASTA property, the steadystate stationary distribution of AoI under RR-ONE is still
unclear. To address this issue, it is found that the AoI evolution
for each terminal follows a Markov renewal process with a
fixed renewal interval of N time slots. Therefore, the steadystate stationary distribution can be derived by first studying the
embedded Markov chain. Denote the time since last update of
the n-th terminal as τn , it follows that the age of the packet
at the n-th terminal, i.e., An (the time index is omitted for
brevity), conditioned on τn is distributed as (let An = hn
denote there is no packet in the n-th queue at the time and
thus the age after this update does not change)
Pr {An = a|τn = τ } = λn (1 − λn )a , a = 0, ..., τ − 1,
Pr {An = hn |τn = τ } = (1 − λn )τ .

If the terminal-n is scheduled in this time slot, then the AoI
of terminal-n, i.e., hn , is updated to the realization of An .
Consider N embedded Markov chains which describe the
AoI transition for N respective terminals between successive
scheduling based on RR-ONE. The state S of the n-th Markov
chain (the terminal index is omitted for brevity) is defined as
the AoI at the scheduled time slot. The transition probability
is therefore
pss0 , Pr {Sk+1 = s0 |Sk = s}

s0 −1
, if s0 ∈ {1, ..., N };

 λn (1 − λn )
= (1 − λn )N ,
if s0 = s + N ;


0,
otherwise,

…

Fig. 5. AoI transition Markov chain under UN-ONE in A0.

Therefore, the steady state AoI for each terminal is exponentially distributed with parameter N1 . The time-average AoI
by running the UN-ONE policy in system A0 is hence N .
Therefore, (24) follows immediately.
Remark 4: Based on Corollary 2, UN-ONE, which in
fact can be seen as a performance lower bound of CSMA
scheme without considering the contention time overhead, has
a much larger time-average AoI compared with RR-ONE. In
particular, when the number of terminals grows large, UNONE does not achieve the optimum scaling factor and thus is
arbitrarily worse than RR-ONE.

(26)

(27)

by noticing the fact that the AoI increases by N during
successive RR-ONE scheduling and then is updated to a
certain value given by (26). If no packet is present at the
terminal queue, then the AoI is updated to s0 = s + N . In
the following, the resultant steady-state stationary stationary
distribution of the Markov chain, denoted by µn (s) where
s = 1, 2, ... denotes state value, is derived. It follows that
X
µn (j) =
µn (i)pij .
(28)
i∈{1,2,...}

Since
pij = λn (1 − λn )j−1 , ∀i = {1, 2, ...}, j ∈ {1, ..., N }, (29)

8

the steady-state stationary distribution for the first N states is
µn (j) = λ(1 − λn )

j−1

, ∀j ∈ {1, ..., N }.

(30)

Algorithm 1: DRR
1
2

For the j-th state with j > N , its previous state must be state
j − N , and hence
µn (j) = µn (j − N )(1 − λn )N = ... = µn (l)(1 − λn )mN
j−1

= λn (1 − λn )

, ∀j = mN + l,

(31)

wherein m and l are integers larger or equal to one. Therefore,
it has been shown that the steady-state stationary distribution
of the Markov chain is a geometric distribution with parameter
λn .
After addressing the steady state of the embedded Markov
chains, we are ready to derive the steady-state stationary
distribution of the AoI evolution process {Yn (t), t = 1, 2...} at
all time slots. Notice that it is a Markov renewal process with
fixed renewal interval N based on RR-ONE. Moreover, the
state evolution between renewal (scheduling) is deterministic;
the AoI increases by one every time slot. Therefore, the steadystate stationary distribution of {Yn (t), t = 1, 2...} is derived
as
min[j,N ]

min[j,N ]

X

X

µn (j) =

qn,m,j =

m=1

m=1

1
λn (1 − λn )j−m , (32)
N

where qn,m,j is the fraction of time that the AoI state transits
to state-(j −m+1) at the scheduled time slot and then reaches
state-j before the next scheduling. Therefore

3

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

20
21
22
23

(33)

24

such that state-j is within reach, and hence m ≥ N ; this,
combining with m ≤ j, explains the minimum operation in
(32). The steady-state stationary distribution is hence given in
(9) after some mathematical manipulations. The time-average
AoI can be directly derived from this distribution, i.e.,

25

j − (j − m + 1) ≤ N − 1,

(∞,N )

h̄RR

N ∞
N
1 XX
1 X 1
N −1
µn (j)j =
+
.(34)
=
N n=1 j=1
N n=1 λn
2

26
27
28

Initialization:
(Terminals) Set γn = n mod N , wn = N .
(BS) Set N to the number of initial terminals and
W = 1.
(Newly appeared terminals) Set γn = 0, wn = 1.
At each terminal:
if Packet arrives then
Replace the current queued packet with the new one.
if γn = 0 then
Transmit the queued packet (a blank packet if none).
Set γn ← wn .
else
Keep silent in this time slot.
At the BS, after receiving updates:
if Successful update or a blank update then
Send an ACK.
else if Receive nothing then
Send a NACK.
else
(Collision) Set N ← N + 1. Send a packet indicating
a collision, containing information of N and W .
Set W ← (W − 1) mod N .
After receiving feedback at each terminal:
if Collision then
if Terminal is newly appeared then
wn ← N , γn ← W . γn ← γn − 1.
else
wn ← N , γn ← N . γn ← γn − 1.
else if NACK then
wn ← wn − 1. γn ← γn − 1.

30

else
ACK received. γn ← γn − 1.

31

Return to Step 5.

29

This coincides with (17).
VI. D ECENTRALIZED RR-ONE A LGORITHM
A fully decentralized RR-ONE-based scheduling algorithm
(DRR) is proposed in this section. The proposed algorithm is
described in Algorithm 1, where we assume dynamic terminal
appearance. However, we assume at each time slot at most
one event can happen: a terminal appears or disappears.
The essence of DRR can be summarized as follows. The
system always runs a round-robin status update protocol by
assigning each terminal a unique time slot (γn ) to update and
rotating among terminals. Without new terminal appearances
or disappearances, the system runs collision-free and every
time slot is utilized. The BS feeds an ACK back in this case.
Terminals dynamically appear at or disappear from the system.
With a new terminal appearance, it updates immediately by
design, and causing a collision inevitably since previously all
time slots are utilized. The BS then feeds back a common
message indicating a collision, with also the information

about the current number of terminals (including the newly
appeared), i.e., N , and the current spot of rotation, i.e., W .
The new terminal will occupy the newly created time slot at the
end of the rotation and the collided time slot still belongs to its
original owner, and therefore no collision will happen between
the two terminals in the next round. With a terminal (T0)
disappearance, the BS receives nothing in its time slot. Note
that a terminal that does not have any packet to update when it
is scheduled would transmit a special blank packet such that
the BS can distinguish between terminal disappearance and
no packet to update. When T0 disappears, the BS then feeds
back a NACK. Every terminal in the system then subtracts its
record of the number of terminals by one and the next-in-line
terminal (T1) will occupy T0’s spot in the next round.

9

VII. P ROOF OF T HEOREM 4: O PTIMAL AIR P OLICY
WITHOUT PACKET M ANAGEMENT FOR P EAK -AO I
M INIMIZATION
Without packet management, the status packets are assumed
to be queued with infinite buffers at terminals before transmissions and the service is based on FCFS discipline in this paper.
Therefore, all generated packets are eventually transmitted and
updated to the BS. This assumption is reasonable in scenarios
where not only the latest status is important, but also the BS
is interested in keeping all the status data, and their status
evolution processes, for analytic purposes. Another reasonable
scenario is that terminals cannot apply packet management due
to hardware limitations.
Note that the ASTA property does not apply in this case,
due to the fact that the age of the head-of-line packet at each
terminal changes to the next-in-line packet’s age when the
terminal is scheduled. Therefore, the independence property
does not hold in Lemma 3; this presents a difficulty in
analyzing the time-average AoI. Hence, we resolve to the PAoI
metric in this section, which is defined as the AoI just before
each update, i.e., the peaks of age evolution in Fig. 1. The
time-average PAoI is defined as
(T )

)
Λ̄(∞,N
π

Kn
N
1 X 1 X
Λn,π (kn ),
, lim
(T )
T →∞ N
n=1 Kn
kn =1

(35)

(T )

where Kn denotes the number of status updates of terminaln up to time T , and Λn,π (kn ) denotes the PAoI before the
kn -th update of terminal n under policy π. The PAoI metric
is used in many previous papers [15], [18] which show that
the time-average PAoI can well approximates the AoI when
the arrival processes have small second moments [15, Lemma
1]. The following optimization problem is considered.
P1:

)
minimize Λ̄(∞,N
π
π∈U

s.t., all queues are stable,

(36)

where U denotes the set of all policies. The queue stability
constraint is added for following reasons: first, queue stability
(T )
is sufficient to ensure that when T → ∞, Kn → ∞, ∀n =
1, ..., N , i.e., every terminal keeps updating its status; on the
other hand, it is straightforward that a necessary condition for
age stability is queue stability, by observing that when a queue
is not, e.g., strongly stable [13], the corresponding AoI also
goes to infinity since each queued packet increases the AoI at
least by one. Note that without the queue stability constraint,
optimizing the PAoI is problematic since totally abandoning
some terminals may obtain better performance because the
PAoI is only counted when updated. The queuing model for
each terminal is represented by M/G/1 with service process
Sn resulting from a policy π. Assume the service time of Sn
has finite first- and second-moments which are denoted by
mn and vn , respectively. Based on the P-K formula [28], the
time-average PAoI for terminal-n is
1
λ n vn
(a)
Λ̄(∞)
+ mn +
n,π = E[In + Jn ] =
λn
2(1 − λn mn )


(b) 1
1
1
1
≥
+
+
, (37)
λn
2 β n − λn
βn

where In and Jn denote the inter-arrival time and the sojourn
time of packets in queue-n, respectively. The equality in (a)
is based on the definition of PAoI [15]. The mean service
rate Sn is denoted by βn . The last inequality (b) is based
on the fact that vn ≥ m2n , which means that it is best to
have a deterministic service process to minimize the mean
delay; the same conclusion in fact hold for GI/G/1 queuing
models [22]. The PAoI minimization problem of P1 is thus
transformed to P2 presented
PN in Section II. Denote the objective
function as f (β) , N1 n=1 fn (βn ) where


1
1
1
1
fn (βn ) ,
+
+
.
(38)
λn
2 βn − λ n
βn
Then f (β) is a strictly convex function since
1
1
d2 fn (βn )
+ 3 > 0, ∀n = 1, ..., N.
=
2
3
(βn − λn )
βn
d βn

(39)

Combining with the fact that the constraints in P2 are all
linear constraints, therefore, P2 is a convex optimization [29]
problem which can be solved efficiently. After obtaining the
optimum service rates βopt , the optimal policy is then to
serve every terminal regularly with fixed intervals given by
βopt . Note that this may not be possible with given, possibly
irrational number, βopt .
Unfortunately, it seems that closed-form optimal solutions
are elusive for P2. We then find a reasonably good closedform solution in Lemma 6 (cf. proof in Appendix B) to shed
light on some insights.
Lemma 6: Define the traffic intensity of terminal n as ρn ,
λn
βn . The minimum time-average PAoI is upper bounded by

N 
1 X 1
1 N
f (βub ) =
+
+
N n=1 λn
2 
where  , 1 −

PN


N

1
+ λn


,

(40)

λn . This bound is achieved by

n=1

βn,ub =


+ λn , ∀n = 1, ..., N.
N

(41)

With heavy traffic, i.e., ρn → 1, ∀n = 1, ..., N , this solution
is asymptotically optimal.

Remark 5: By comparing the results in Theorem 2 and
Lemma 6 in the asymptotic regime, some insights can be
obtained. First, in the massive IoT regime, the optimum scaling
factor without packet management is
lim

N →∞

1
f (βub )
= .
N
2

(42)

Compared with the optimum scaling factor with packet management, i.e., 0.5, the packet waiting delay in the queue
introduces a multiplicative loss of 1/ which is related to traffic
intensity.
The optimum scaling laws with diminishing arrival rates are
actually identical with and without packet management. This
is intuitive since the bottleneck is arrival status update packets
in this regime, and packets are rarely queued with or without
packet management.

10

4.5

VIII. S IMULATION R ESULTS

(h1 , a1 ) × (h2 , a2 ),

(43)

where hi denotes the AoI at the BS for terminal i, ai denotes
the age of the packet at terminal i (assuming the terminal
adopts the one-packet buffer packet management policy), and
1 ≤ hi , ai ≤ hmax , i = 1, 2, where hmax is the age limit.
The transition probability matrix follows straightforwardly;
it is omitted here for brevity, along with the relative value
iteration procedure which is well known. The performance
of RR-ONE is obtained by running RR-ONE for 105 time
slots and calculating the time-average AoI. In addition, we
also simulate UN-ONE which schedules a terminal uniformly
random at each time slot, and an age-greedy policy which
chooses the terminal with the largest AoI. In fact, UN-ONE
can be regarded as the CSMA scheme which is shown to be
optimal to maximize throughput with greedy sources. The agegreedy policy is found optimal without considering random
packet arrivals [9].
It is observed from Fig. 6 that the performance gap between
RR-ONE and the optimum given by numerically solving the
MDP is larger with lower packet arrival rates; on the other
hand, RR-ONE achieves the optimum when λ approaches
one based on Remark 3. Since RR-ONE is proved optimal
among AIR policies, the optimal scheduling policy with low
packet arrival rates must be a non-AIR policy. Specifically, the
following intuition explains this. Suppose that the probability
of both terminals having arrival packets in the same time slot
is negligible when arrival rates are sufficiently low; then the
optimal policy is immediately obvious that it should schedule
the terminal with a packet arrival at each time slot; note
that this policy is not an AIR policy because the scheduling
decision depends on packet arrivals which violates Condition
1 of AIR policy definition. The optimum performance in this
case is also obvious; it should be the same with what is
shown in Lemma 5, i.e., completely determined by the interarrival time of packets and this can be observed from Fig 6.
Nevertheless, it is noted that the performance gap is bounded

Lower bound by Lemma 4
Lower bound by Lemma 5
Optimum by MDP
Age-greedy
UN-ONE
RR-ONE

Time average AoI (time slots)

4
3.5
3
2.5
2
1.5
1
0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Packet arrival rate (packets/time slot)

Fig. 6. Performance comparisons among lower bounds in Lemma 4 and 5,
MDP-based optimum, UN-ONE, age-greedy policy and RR-ONE. There are
2 terminals with identical packet arrival rate (x-axis).
4

Time average AoI (time slots)

In this section, computer simulation based experiments are
conducted to evaluate the AoI performance of scheduling
policies. This enables us to obtain the optimum performance
numerically by formulating the problem as an Markov decision
process (MDP) and solving it by relative value iterations for
average cost function [30]. Note that, similar with most practical applications, the MDP based approach suffers from the
curse of dimensionality and hence only small-scale problems
can be solved thereby. Specifically, it is observed that the state
space size grows exponentially with the number of terminals,
and hence the scalability is significantly limited. Nevertheless,
we obtain the minimum time-average AoI of a 2-terminal
case and compare its performance with RR-ONE. An finitestate approximation is made for the MDP which originally
has infinite state space; note that the AoI can grow to infinity.
However, the optimality is intact by arguing that the optimal
policy given by solving the finite state MDP does not allow
the AoI grows to our prescribed AoI limit. The state space of
the MDP is defined as

Optimum by MDP
Lower bound by Lemma 5
Lower bound by Lemma 4
Age-greedy
UN-ONE
RR-ONE

3.5

3

2.5

2

1.5

1
0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Packet arrival rate of terminal 1 (packets/time slot)

Fig. 7. Performance comparisons with heterogeneous arrival rates. There are
2 terminals; λ2 = 0.5 and λ1 is shown as the x-axis.

(within 0.5 time slots) in this 2-terminal case by observing the
RR-ONE performance and performance bound in Lemma 5.
Fig. 7 shows the performance with heterogeneous packet
arrival rates for terminals; the arrival rate λ1 is fixed to 0.5
packets per time slot and λ2 varies from 0.3 to 1. The bounded
gap is still within 0.5 time slots, despite the fact that RRONE disregards the heterogeneity of arrival rates completely.
Nonetheless, it is observable that the gap between optimum
and RR-ONE is larger compared with Fig. 6. Moreover, the
gap between RR-ONE and the age-greedy policy is relatively
larger when the arrival rates difference between terminals
increases, showing that the age-greedy is more sensitive to
arrival statistics heterogeneity.
We increase the number of terminals and enter the massive IoT regime in Fig. 8. The MDP-based optimal solution
is computationally intractable in this regime and hence we
adopt the myopic policy with GSI as an approximation of
the optimum. The myopic policy with GSI leverages all the
global information (though no future knowledge) to make a
scheduling decision that minimizes the one-step expected AoI

11

Time average AoI (time slots)

120

packet arrival randomness has much larger impact if all packets
are queued; therefore the GSI in this case is more valuable
compared with the case with packet management whereby
most randomness is eliminated. The performance advantage
of RR-λ over uniformly random scheduling is still evident.
Note that by setting all arrival rates to be identical and the
associated parameters in Fig. 9, all three policies can stabilize
the system; it is pointless to evaluate a policy that cannot
stabilize the system since it would lead to infinite AoI.

100
32.2
80

32
31.8

60

59.5

60

60.5

40
UN-ONE
RR-ONE
Myopic policy (GSI)

20

0
10

20

30

40

50

60

70

80

90

IX. C ONCLUSIONS AND D ISCUSSIONS
100

Number of terminals

Fig. 8. Performance comparisons with a large number of terminals; the arrival
rates are uniformly randomly generated from [0, 1].

Time average AoI (time slots)

1200

1000

Myopic policy (GSI)
RRUniform random scheduling

800

600

400

200

0
10

20

30

40

50

60

70

80

90

100

Number of terminals

Fig. 9. Performance comparisons with a large number of terminals and no
packet management; the arrival rates are identical for all terminals, and  =
0.1 in Lemma 6.

cost in the MDP formulation; by comparing it with RR-ONE
helps us to understand how much GSI benefits RR-ONE.
Based on Fig. 8, it is shown that the myopic policy with
GSI outperforms RR-ONE only slightly, due to the reason that
the packet management of using one-packet buffers eliminates
most of the randomness of packet arrivals; most packets are
dropped by packet management due to staleness and hence
their randomness has no effect. The performance of UN-ONE
is also shown; it has been proved in Corollary 2 that its linear
scaling factor is (at least) 1 compared with 1/2 for RR-ONE;
this can be observed in the figure.
In Fig.9, policies without packet management are simulated.
The arrival packets are queued at terminals and all arrived
packets have to be delivered to the BS. The optimal AIR
policy RR-λ in this case is compared with random scheduling
and myopic policy with GSI in the figure. It is observed
that, without packet management, the gap between the myopic
policy with GSI and the optimal AIR policy RR-λ is much
larger compared with that (between myopic policy with GSI
and RR-ONE) in Fig. 8; in fact different asymptotic scaling
factors are found in Fig. 9. The intuition behind this is that the

In this paper, it is found that with a number of terminals
sharing a common wireless uplink based on a collision model
and random packet arrivals at each terminal, the optimal
AIR policy to minimize the time-average AoI is RR-ONE,
i.e., scheduling terminals in a round-robin fashion and each
terminal only retains the most up-to-date packet. In the
asymptotic regime where the number of terminals is large, the
optimum (among all policies) time-average AoI is proved to
scale linearly with the number of terminals with the optimum
scaling factor of 21 , and RR-ONE achieves the optimum
asymptotically. The steady-state stationary distribution of the
AoI of each terminal under RR-ONE is also derived. In
addition to establishing the optimality, we propose a fullfledged decentralized algorithm to implement RR-ONE which
accounts for dynamic terminal appearances. Considering the
scenario where the entire procedure of status variation is
requested, i.e., packets cannot be dropped, the optimal AIR
policy without packet management, namely RR-λ, is also derived; it schedules terminals based on deterministic scheduling
intervals mn , n = 1, ..., N , with mn given by the solution of
a convex optimization problem.
Both RR-ONE and RR-λ are suitable for decentralized
implementation since they require minimal information for
scheduling decisions. Based on numerical simulations, it is
observed that extra global information hardly benefits RRONE; on the other hand, it benefits RR-λ much more evidently
(also linear scaling of AoI with the number of terminals but
with a smaller scaling factor). This stems from the fact that
the aggressive packet management by RR-ONE significantly
eliminates the randomness of packet arrivals since a considerable share of packets are dropped due to staleness; however
this randomness accumulates and has a more noticeable effect
without packet management by RR-λ. The extra global information for scheduling is mainly to deal with the arrival
randomness, and therefore it is less valuable to RR-ONE
compared with RR-λ. The packet management of RR-ONE
essentially “hardens” the packet arrival processes, i.e., making
them more deterministic, by observing that the performance of
RR-ONE is analogous with that of deterministic packet arrivals
(comparing Lemma 4, Lemma 5 and Theorem 1).
A PPENDIX A
M YOPIC P OLICY WITH GSI IS NOT O PTIMAL WITH F INITE
H ORIZON
In this section, we assume that the BS knows the current
ages of packets of all terminals and the arrival distributions,

12

i.e., λi , i ∈ {1, ..., N } to make a centralized scheduling
decision. In this case, it will be shown the myopic policy is
not optimal by constructing a counter example. Consider a
case with a time horizon T = 2, and the number of terminals
is N = 2. The arrival rates for terminal 1 and 2 are λ1 = δ
and λ2 = 1 − δ, respectively, and 0 < δ < 1. The initial
ages are set as hi (0), i = 1, 2, and the initial age gains of
the packets in the queues are gi (0), i = 1, 2. Assuming the
following conditions are met:

one; otherwise, with probability 1 − λ, the age increases by
one. The Markovian property holds obviously. The steady-state
stationary distribution is hence a geometric distribution with
parameter λ.
Proof of Lemma 4: Consider a system A0 wherein the
AoI after each update is fixed to one, instead of determined
by the random arrival packets. Then for any scheduling policy
π, we have
(T,N )
)
h̄(T,N
≥ h̄π,A0 ,
(49)
π

g2 (0)
< g1 (0) < g2 (0),
2
h2 (0) − g2 (0) > h1 (0),

where h̄π,A0 denotes the time-average AoI of policy π in
system A0. The proof for (49) is simply based on stochastic
dominance, and currently omitted for brevity. By [9, Theorem
1], the optimal policy in A0 is the age-greedy policy by
noticing that no asymmetric transmission failure or weights
are considered in this paper. Therefore it is straightforward
to derive the optimum time-average AoI in A0 since no
randomness exists. The optimum AoI in A0 is therefore

(44)
(45)

then the expected average age under the myopic policy, which
always schedules the terminal with the largest gn (t) at time t,
is shown here
1
(h1,mo (1) + h1,mo (2) + h2,mo (1) + h2,mo (2))
4
1
= C − (g2 (0) + δ(1 − δ)(h2 (0) + 1)
4
+δ 2 (g2 (0) + h1 (0) + 1) + δ(1 − δ)(g1 (0) + g2 (0))

+(1 − δ)2 (h2 (0) + 1)
1
= C − (g2 (0) + h2 (0) + 1 + δ(g1 (0) − g2 (0))
4

+δ 2 (h1 (0) + 1 − g1 (0)) ,
(46)
and the expected average age under the optimal policy, which
is not hard to figure out in this simple case, is
1
(h1,∗ (1) + h1,∗ (2) + h2,∗ (1) + h2,∗ (2))
4
1
= C − (g1 (0) + δ(1 − δ)(g1 (0) + h2 (0) + 1)
4
+δ 2 (g1 (0) + g2 (0)) + δ(1 − δ)(g1 (0) + g2 (0))

+(1 − δ)2 (g1 (0) + h2 (0) + 1)
1
= C − (2g1 (0) + h2 (0) + 1 − δ(h2 (0) + 1 − g2 (0))) ,
4
(47)
where

1
(h1 (0) + h2 (0)) + 1.5.
(48)
2
By setting the parameter δ sufficiently small, we can see that
the average age of the myopic policy is strictly smaller than
the optimal policy which schedules terminal 1 at the first time
slot although the current myopic choice is terminal 2.
C=

(T,N )

N +1
,
(50)
2
It is sufficient to consider the optimal scheduling scheme in
A0 to obtain a AoI lower bound since all scheduling schemes
perform better in A0 compared with a system with random
packet arrivals. The conclusion follows immediately.
Proof of Lemma 5: To prove this result, we consider
a collision-free system A1 wherein the uplink transmissions
can be multiplexed, i.e., an arbitrary number of terminals can
update successfully in the same time slot. It is obvious that,
similar with Lemma 4, for any policy π,
(∞,N )

h̄opt,A0 =

(T,N )

)
h̄(T,N
≥ h̄π,A1 .
π

(51)

It is also obvious that the time-average AoI in system A1 is
the time-average packet inter-arrival time at terminal queues.
Therefore, the conclusion follows immediately.
Proof of Lemma 6: Since P2 is minimizing the PAoI
over all βn , by setting βn = βn,ub we can obtain the upper
bound in Lemma 6. In the heavy traffic regime,


N
1 X 1
ρn
1
f (β) =
+
1+
N n=1 λn
2λn
1 − ρn
ρn →1

−→

N
1
1 X
.
N n=1 2λn (1 − ρn )

(52)

The optimum solution in the heavy traffic regime is therefore
βn,ub , ∀n = 1, ..., N by applying the arithmetic-harmonicmean inequality.

A PPENDIX B
P ROOF OF L EMMAS

R EFERENCES

Proof of Lemma 1: It is straightforward that the performance of a non-WCNC policy is stochastically dominated by
a WCNC policy which is identical to the non-WCNC policy,
except that the WCNC policy schedules an arbitrary terminal
(resp. schedules one of the terminals) when the non-WCNC
policy is idle (resp. schedules multiple terminals resulting in
collisions).
Proof of Lemma 2: At each time slot, the probability
of a packet arrival is λ and therein the age decreases to

[1] Z. Jiang, B. Krishnamachari, X. Zheng, S. Zhou, and Z. Niu, “Decentralized status update for age-of-information optimization in wireless
multiaccess channels,” in submission to IEEE Int’l Symp. Info. Theory,
2018.
[2] Ericsson, “Cellular networks for massive IoT,” tech. rep., Jan 2016.
[3] A. Osseiran, F. Boccardi, V. Braun, K. Kusume, P. Marsch, M. Maternia,
O. Queseth, M. Schellmann, H. Schotten, H. Taoka, H. Tullberg, M. A.
Uusitalo, B. Timus, and M. Fallgren, “Scenarios for 5G mobile and
wireless communications: The vision of the METIS project,” IEEE
Commun. Mag., vol. 52, pp. 26–35, May 2014.
[4] G. P. Fettweis, “The Tactile Internet: Applications and challenges,” IEEE
Veh. Tech. Mag., vol. 9, pp. 64–70, Mar 2014.

13

[5] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of
information in vehicular networks,” in IEEE SECON, pp. 350–358, Jun
2011.
[6] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should
one update?,” in IEEE INFOCOM, pp. 2731–2735, Mar 2012.
[7] R. D. Yates and S. Kaul, “Real-time status updating: Multiple sources,”
in IEEE Int’l Symp. Info. Theory, pp. 2666–2670, Jul 2012.
[8] R. D. Yates and S. K. Kaul, “The age of information: Real-time status
updating by multiple sources,” arXiv preprint arXiv:1608.08622, 2016.
[9] I. Kadota, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Minimizing
the age of information in broadcast wireless networks,” in Annu. Allerton
Conf. Commun., Control, Comput., pp. 844–851, Sep 2016.
[10] Q. He, D. Yuan, and A. Ephremides, “Optimal link scheduling for age
minimization in wireless systems,” IEEE Trans. Inform. Theory, in press.
[11] C. Joo and A. Eryilmaz, “Wireless scheduling for information freshness
and synchrony: Drift-based design and heavy-traffic analysis,” in IEEE
WiOpt, pp. 1–8, May 2017.
[12] Z. Jiang, S. Zhou, X. Guo, and Z. Niu, “Task replication for deadlineconstrained vehicular cloud computing: Optimal policy, performance
analysis and implications on road traffic,” IEEE Internet Things J., in
press.
[13] 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.
[14] G. Bianchi, “Performance analysis of the IEEE 802.11 distributed
coordination function,” IEEE J. Select. Areas Commun., vol. 18, pp. 535–
547, Mar 2000.
[15] L. Huang and E. Modiano, “Optimizing age-of-information in a multiclass queueing system,” in IEEE Int’l Symp. Info. Theory, pp. 1681–
1685, Jun 2015.
[16] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Optimizing data freshness,
throughput, and delay in multi-server information-update systems,” in
IEEE Int’l Symp. Info. Theory, pp. 2569–2573, Jul 2016.
[17] S. K. Kaul, R. D. Yates, and M. Gruteser, “Status updates through
queues,” in Annual Conference on Information Sciences and Systems,
pp. 1–6, Mar 2012.
[18] 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, pp. 1897–1910, April 2016.
[19] E. Najm and R. Nasser, “The age of information: The gamma awakening,” in IEEE Int’l Symp. Info. Theory, pp. 2574–2578, 2016.
[20] Y. Sun, E. Uysal-Biyikoglu, R. Yates, C. E. Koksal, and N. B. Shroff,
“Update or wait: How to keep your data fresh,” in IEEE INFOCOM,
pp. 1–9, April 2016.
[21] Y. P. Hsu, E. Modiano, and L. Duan, “Age of information: Design and
analysis of optimal scheduling algorithms,” in IEEE Int’l Symp. Info.
Theory, pp. 561–565, Jun 2017.
[22] W. Whitt, “Minimizing delays in the GI/G/1 queue,” Operations Research, vol. 32, no. 1, pp. 41–51, 1984.
[23] J. Andrews, S. Buzzi, W. Choi, S. Hanly, A. Lozano, A. Soong, and
J. Zhang, “What will 5G be?,” IEEE J. Sel. Areas Commun., vol. 32,
pp. 1065–1082, Jun 2014.
[24] S. H. A. Ahmad, M. Liu, T. Javidi, Q. Zhao, and B. Krishnamachari,
“Optimality of myopic sensing in multichannel opportunistic access,”
IEEE Trans. Inform. Theory, vol. 55, pp. 4040–4050, Sep 2009.
[25] B. Melamed and D. Yao, “The ASTA property,” Advances in Queueing:
Theory, Methods and Open Problems, pp. 195–224, 1995.
[26] E. Najm, R. Yates, and E. Soljanin, “Status updates through M/G/1/1
queues with HARQ,” in IEEE Int’l Symp. Info. Theory, pp. 131–135,
Jun 2017.
[27] D. R. Cox, Renewal theory, vol. 1. Methuen London, 1967.
[28] D. Bertsekas and R. Gallager, Data Networks. Prentice-Hall, Inc, 1992.
[29] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge
university press, 2009.
[30] D. P. Bertsekas, Dynamic programming and optimal control, vol. 1.
Athena scientific Belmont, MA, 1995.

