# Centralized and Distributed Age of Information Minimization with non-linear
Aging Functions in the Internet of Things

Taehyeun Park1, Walid Saad1, and Bo Zhou1
1Wireless@VT, Bradley Department of Electrical and Computer Engineering,
Virginia Tech, Blacksburg, VA, USA,
Emails:{taehyeun, walids<EMAIL_ADDRESS>
###### Abstract

Resource management in Internet of Things (IoT) systems is a major challenge
due to the massive scale and heterogeneity of the IoT system. For instance,
most IoT applications require timely delivery of collected information, which
is a key challenge for the IoT. In this paper, novel centralized and
distributed resource allocation schemes are proposed to enable IoT devices to
share limited communication resources and to transmit IoT messages in a timely
manner. In the considered system, the timeliness of information is captured
using non-linear age of information (AoI) metrics that can naturally quantify
the freshness of information. To model the inherent heterogeneity of the IoT
system, the non-linear aging functions are defined in terms of IoT device
types and message content. To minimize AoI, the proposed resource management
schemes allocate the limited communication resources considering AoI. In
particular, the proposed centralized scheme enables the base station to learn
the device types and to determine aging functions. Moreover, the proposed
distributed scheme enables the devices to share the limited communication
resources based on available information on other devices and their AoI. The
convergence of the proposed distributed scheme is proved, and the
effectiveness in reducing the AoI with partial information is analyzed.
Furthermore, the proposed resource management schemes with different number of
devices, activation probabilities, and outage probabilities are analyzed in
terms of the average instantaneous AoI. Simulation results show that the
proposed centralized scheme achieves significantly lower average instantaneous
AoI when compared to simple centralized allocation without learning, while the
proposed distributed scheme achieves significantly lower average instantaneous
AoI when compared to random allocation. The results also show that the
proposed centralized scheme outperforms the proposed distributed scheme in
almost all cases, but the distributed approach is more viable for a massive
IoT.

###### Index Terms:

Age of Information, Internet of Things, Radio Resource Management

##  I Introduction

††This research was supported by the Office of Naval Research (ONR) under MURI
Grant N00014-19-1-2621.

The Internet of Things (IoT) is arguably the most important technology of the
coming decade [1]. However, the effective operation of several IoT services,
such as industrial monitoring [2], health monitoring [3], drones [4], virtual
reality [5], and vehicular network [6], requires timely and frequent
communications. To maintain the proper performance of such diverse IoT
applications, the base station (BS) must maintain the most relevant
information gathered from the IoT devices at any given time.
In addition to timely transmissions from the devices to the BS, another key
challenge is to account for the distinctive characteristics of an IoT and its
devices. One prominent property of an IoT is its massive scale as the number
of devices greatly outnumbers the available communication resources [7].
Therefore, an appropriate allocation of the limited communication resources
among numerous IoT devices is necessary for the deployment of an IoT and its
services [8]. Furthermore, the IoT exhibits a high heterogeneity in terms of
device types, functions, messages, transmission requirements, and resource
constraints [9]. The aforementioned IoT properties pose challenges for timely
uplink transmission in an IoT. To ensure the performance of time-sensitive IoT
applications despite the aforementioned challenges, a new information
timeliness performance metric is needed as an alternative to conventional
delay, reliability, and data rate.
To evaluate the communication between the BS and the devices, the age of
information (AoI), which is a metric that can quantify the relevance and the
freshness of the information, is used [10, 11]. However, the AoI has different
characteristics compared to delay [10], because it explicitly considers packet
generation time. The problem of AoI minimization in an IoT has unique
challenges due to the characteristics of an IoT, including massive scale,
limited communication resources, and IoT device heterogeneity. Largely, AoI
minimization can be done in a centralized way or in a distributed way.
However, a centralized AoI minimization approach is not always viable for an
IoT, because the energy constrained IoT devices may not be able to communicate
frequently with BS. On the other hand, a distributed AoI minimization approach
may require extensive device-to-device communication and could perform worse
than a centralized solution for some IoT scenarios. Therefore, both
centralized and distributed AoI minimization must be investigated to compare
their applicability and performances in an IoT.

###  I-A Existing Works

A number of recent works studied the problem of AoI minimization in wireless
networks [11, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
27, 28, 29, 30, 31, 32, 33, 34]. These studies use various approaches to
minimize the AoI under different constraints and conditions. For instance, the
works in [11, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
27, 28, 29, 30, 31, 32, 33] study a variety of scheduling policies for AoI
minimization in different networks, including single hop broadcast network
[12], single-hop uplink communication [13], multi-hop uplink communication
[14], ad-hoc networks [15], and ALOHA-like random access [16]. The authors in
[17] and [18] propose and analyze scheduling policies for the wireless
networks with known and unknown channel state information. The works in [10],
[13], [15], and [19] introduce effective scheduling policies to minimize the
average AoI with network constraints, such as throughput requirement, physical
constraint for sensing, spectrum sharing, and varying packet sizes. In [15],
[20], and [21], the authors use online techniques, such as reinforcement
learning to perform AoI-minimal scheduling. Moreover, the authors in [21] and
[22] analyze the performance of user scheduling for minimizing the average AoI
in presence of multiple sources of information and propose a hybrid queueing
system. The authors in [23] analyze the coexistence of DSRC and WiFi networks
as a game, in which the DSRC network minimizes the AoI and the WiFi network
maximizes the throughput. For CSMA networks, the work in [24] optimizes the
backoff time of each communication link to minimize the total average AoI, and
the authors in [25] propose a sleep-wake scheduling to optimize the tradeoff
between AoI minimization and energy consumption.
The works in [26, 27, 28, 29] address the problem of AoI minimization using
queueing-theoretic approaches. In [26], the authors analyze the peak AoI in a
multi-class queueing system with packets having heterogeneous service times
and requirements. The authors in [27, 28, 29] derive closed-form solutions for
the average AoI and the peak AoI for different queueing models, including
M/M/1, M/G/1, and M/G/1/1. In [30], the authors consider a vehicular network
with ultra-reliable low-latency communication and minimize the tail of the AoI
distribution. The peak AoI considering the packet delivery failure is analyzed
in [31]. Moreover, the non-orthogonal multiple access is compared against the
conventional orthogonal multiple access in terms of AoI minimization in [32].
The authors study the sampling policies to minimize the average AoI with the
joint status sampling in IoT [11] or with the non-linear aging functions [33].
Despite being interesting, the existing solutions in [11, 10, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34] do
not consider some of the unique properties of an IoT, such as limited
communication resources, massive scale, and high device heterogeneity. One of
the key challenges in IoT is the massive scale of IoT coupled with highly
limited available communication resources. However, the works in [10, 12, 13,
14, 15, 16, 20], and [31, 32, 33] do not investigate the realistic IoT
scenario in which the number of devices greatly outnumbers the communication
resources. Furthermore, the inherent heterogeneity among IoT devices and the
presence of non-linear aging functions are not considered in [11, 12, 13, 14,
15, 16, 17, 18, 19, 20], and [27, 28, 29, 30, 31, 32]. Moreover, most of the
prior works for AoI minimization in [10, 12, 13, 14, 15, 16, 17, 18, 21, 22,
23, 24, 25, 26, 27, 28, 29], and [33] only considers a centralized approach.
Moreover, in [34], we studied centralized AoI minimization with non-linear
aging functions and proposed a centralized resource allocation scheme to
enable the BS to consider different aging functions. However, the work in [34]
only investigates a centralized approach for AoI minimization and does not
introduce a distributed resource allocation framework for an IoT with non-
linear aging functions. A centralized approach may not always be suitable for
an IoT, because the frequent communication with BS is not viable for the
energy constrained IoT devices. These important challenges for enhancing the
AoI in an IoT have been largely overlooked in prior works [11, 10, 12, 13, 14,
15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,
34].

###  I-B Contributions

The main contributions of this paper are novel centralized and distributed
resource allocation frameworks that can be used to minimize the average
instantaneous AoI for a massive IoT with heterogeneous devices and non-linear
aging functions. In particular, we capture the heterogeneity among IoT devices
using _non-linear aging functions_. Typically, the AoI is defined only in
terms of time, and it is assumed to increase linearly with a slope of $1$
[10]. However, the definition of the AoI can be broader such that the AoI can
be a function of completeness, validity, accuracy, currency, and utility [35,
36]. Under such a broader definition of the AoI, the aging function can be
defined as an age penalty function or an age utility function [33], which can
be an exponential, linear, or step function [35]. As such, we propose to
capture the heterogeneity among IoT devices and messages by assigning
different aging functions based on the devices types, the IoT application, the
message content, and the transmission requirement.
For centralized AoI minimization, we propose a new priority scheduling scheme
with a learning perspective such that the device types and the aging functions
can be determined. For non-linear aging functions, we show that using the
future AoI for priority scheduling achieves a lower average instantaneous AoI
than using the current AoI. Simulation results for the centralized approach
show that the proposed priority scheduling scheme achieves $26.7\%$ lower
average instantaneous AoI with high activation probability and $31.7\%$ lower
average instantaneous AoI with high outage probability than a simple priority
scheduling. In particular, our approach outperforms a simple priority
scheduling and performs similar to a priority scheduling with complete
information on device types and aging functions.
For the distributed AoI minimization, we formulate a minority game [37], such
that massive number of IoT devices can share the limited available
communication resources autonomously. Furthermore, a payoff function is
designed to allow the messages with the highest AoI to transmit first in a
self-organizing manner. We then show the conditions that a resource allocation
among IoT devices must satisfy to achieve a Nash equilibrium (NE). We propose
a stochastic crowd avoidance algorithm for the resource allocation game and
prove that the resource allocation using our proposed algorithm converges to
an NE with sufficient information and under certain network parameters.
Simulation results for the distributed case show that the proposed algorithm
is effective in minimizing the AoI even if the devices only have the partial
information about other devices. The results show that our game-based approach
achieves $63.6\%$ lower average instantaneous AoI with limited information and
$45.8\%$ lower average instantaneous AoI with high outage probability than a
random resource allocation. Moreover, after convergence, our game-based
approach performs similar to the pre-determined resource allocation with
complete information.
The centralized and the distributed AoI minimization schemes are compared in
terms of overhead, implementation, and requirements. In particular, the
centralized AoI minimization has an overhead of uplink communication request,
while the distributed AoI minimization has an overhead of device-to-device
communication. Simulation results show that the distributed AoI minimization
achieves $40$-fold higher average instantaneous AoI than the centralized AoI
minimization in a massive IoT, where the communication resources are highly
limited and the devices only have partial information. In a less constrained
IoT, simulation results show that the distributed AoI minimization achieves
$8$-fold higher average instantaneous AoI than the centralized AoI
minimization. Although the centralized AoI minimization outperforms the
distributed AoI minimization in terms of average instantaneous AoI, the
distributed approach may be more suitable for an IoT, because the centralized
approach may not be practical or viable for an IoT. As such, our analysis
clearly showcases the contrasts between the two solutions.
The rest of this paper is organized as follows. Section II introduces the
system model and the non-linear aging functions. Section III analyzes the AoI
minimization with coexistence of linear and non-linear aging functions.
Section IV presents the centralized and the distributed resource allocations
in an IoT. Section V analyzes the simulation results, while Section VI draws
conclusions.

##  II System Model

Consider the uplink of a wireless IoT system consisting of one BS serving $N$
IoT devices. The IoT devices can transmit their messages to the BS using the
communication resources allocated by either a centralized or distributed
resource allocation scheme. To transmit to the BS, the IoT devices use time-
slotted orthogonal frequency-division multiple access (OFDMA). Here, $R$ time-
frequency resource blocks (RBs) are allocated to the IoT devices at each time
slot. If more than one IoT device use a given RB, none of the messages
transmitted using the given RB can be successfully decoded, which leads to
transmission failures. This implies that at most $R$ devices can transmit
successfully to the BS at a time slot. In an IoT where the number of devices
$N$ greatly outnumbers the number of RBs $R$, RB allocation is critical for
the operation of IoT, and RB allocation can be done in a centralized or in a
distributed way.
Under a centralized resource allocation scheme, the BS allocates the RBs to
the IoT devices such that a given RB is used by only one device. Therefore,
duplicate RB usage will not occur when using a centralized resource
allocation. However, centralized resource allocation incurs an overhead
related to the need that the devices request their uplink communication
resources via a random access channel (RACH) [38]. Furthermore, the uplink
communication resource request using RACH can fail resulting in transmission
failure. In contrast, when using a distributed resource allocation scheme, the
devices decide which RB to use autonomously without any intervention from the
BS and without RACH. Although there is no overhead related to the need for
requesting uplink communication resources, distributed resource allocation
incurs an overhead related to the devices cooperating to avoid duplicate RB
usage. Since there is no RACH request when performing distributed resource
allocation, no RACH request failures will happen. However, the uplink
transmission may fail because of a duplicate RB usage.
For both centralized and distributed resource allocations, the uplink
transmission can also fail because of the RB outage. The RB outage is based on
the signal-to-noise ratio (SNR) such that the transmission is considered to be
a failure if the SNR is less than a given threshold $\epsilon\geq 0$. We
consider a stationary Rayleigh fading channel with additive white Gaussian
noise (AWGN), such that the statistical properties of channel do not change
over time. Therefore, the SNR outage probability is
$\Pr\left(\nicefrac{{S^{2}}}{{\sigma^{2}}}\leq\epsilon\right)$, where the
received signal power $S^{2}$ is an exponentially distributed random variable
and $\sigma^{2}$ is the variance of the AWGN. We assume that the IoT devices
only know the distributional properties of the channel and the AWGN at the
receiver. Furthermore, we assume that all devices transmit with the same
transmit power as the devices do not know exact channel gain [5, 8], and [39,
40, 41]. Since we consider a Rayleigh fading channel, the received signal
power $S^{2}$ is exponentially distributed, and the devices know the mean
$\lambda^{-1}$ of $S^{2}$. We assume that the transmit powers of all IoT
devices are equal, and, thus, the mean of the received signal power will be
the same for all devices. When an IoT device uses multiple RBs simultaneously,
then the transmit power will be equally divided among those RBs. For instance,
if an IoT device $i$ uses $R_{i,t}$ RBs simultaneously at time slot $t$, then
the received signal power is $\nicefrac{{S^{2}}}{{R_{i,t}}}$. For an IoT
device $i$ using $R_{i,t}$ RBs simultaneously at time slot $t$, the outage
probability $p_{i,t}$ for device $i$ at time slot $t$ will be:

$p_{i,t}=\Pr\left(\frac{\nicefrac{{S^{2}}}{{R_{i,t}}}}{\sigma^{2}}\leq\epsilon\right).$
(1)

Since $S^{2}$ is exponentially distributed with mean $\lambda^{-1}$,
$\frac{\nicefrac{{S^{2}}}{{R_{i,t}}}}{\sigma^{2}}$ is exponentially
distributed with mean $(R_{i,t}\sigma^{2}\lambda)^{-1}$ for a given $R_{i,t}$
and a known $\sigma^{2}$. Moreover, the outage probability $p_{i,t}$ can be
interpreted as a cumulative distribution function of an exponential
distribution. Since an exponential random variable $S^{2}$ with mean
$\lambda^{-1}$ has a cumulative distribution function of
$\Pr\left(S^{2}\leq\epsilon\right)=1-\exp\left(-\lambda\epsilon\right)$ for
$\epsilon\geq 0$, the outage probability $p_{i,t}$ in (1) will be:

$p_{i,t}=1-\exp\left(-\left(R_{i,t}\sigma^{2}\lambda\right)\epsilon\right).$
(2)

For a successful uplink transmission, an RB must be used by only one device,
and the SNR must be higher than a given threshold $\epsilon$.
One prominent feature of an IoT is its massive scale. In particular, the
number of IoT devices $N$ greatly outnumbers the number of RBs $R$. For an IoT
scenario where $N>R$, the problem of RB allocation among the IoT devices
becomes more challenging. Another prominent feature of an IoT is the
heterogeneity among the IoT devices. The IoT devices are heterogeneous in
terms of message types, transmission requirements, and packet content. A
metric that can be used to determine which $R$ out of the $N$ devices will
transmit and to quantify the freshness of the information in perspective of
the destination is AoI. Furthermore, the heterogeneity among the IoT devices
and their messages can be captured by extending the definition of AoI to
include the quality of information and introducing non-linear aging functions.

###  II-A Age of Information

The AoI is a metric that quantifies the freshness of the information in the
perspective of a destination [11], and the definition of the AoI is the time
elapsed since the generation of a message that is most recently received at
the BS. In prior art on the AoI, devices are commonly assumed to generate the
messages at will [42] and to update BS with a new message just in time [43].
The generate-at-will model for AoI implies that IoT devices can have messages
to transmit to the BS at any time, and the just-in-time model for AoI implies
that IoT devices transmit new message to the BS immediately after the
successful transmission of the current message. However, for an IoT, the
devices are not always active and do not always have the messages to transmit
to the BS. In our model, a device has a message to transmit to the BS at a
given time slot with an activation probability $v_{a}$. If a device transmits
to the BS unsuccessfully at a given time slot, then the device retransmits the
message immediately at following time slot without a random backoff time. For
the distributed RB allocation, the proposed game is designed to give incentive
to devices with low AoI to not transmit. The RACH phase of the centralized RB
allocation can use the game formulated for distributed RB allocation to
achieve a lower average instantaneous AoI. Meanwhile, the random backoff time
used in [23] and [44] does not consider different aging functions, when the
backoff time is determined for each device. For instance, a long backoff time
can be assigned to a device with higher AoI and exponential aging function,
while a short backoff time can be assigned to a device with low AoI and linear
aging function.
Minimizing the AoI implies that the destination maintains fresh information
from the source. However, minimizing the AoI is different from simply
minimizing delay[10]. The AoI is measured by an aging function, and it is
typically assumed that all devices have the same, linear aging function with a
slope of $1$[10]. However, by using different aging functions for different
messages, the AoI can naturally capture the inherent heterogeneity among IoT
devices and messages. For instance, depending on the device type and the
message characteristics, the aging function can be assigned appropriately. If
the device is a simple sensor transmitting a time-insensitive update messages,
the appropriate aging function is a linear aging function. On the other hand,
if the device is an industrial monitoring sensor transmitting a time-sensitive
status report, the appropriate aging function is an exponential aging
function. By using different aging functions, the AoI captures both the
freshness of information and the value of information [33, 35, 36].
To model the heterogeneous messages, we consider the coexistence of linear
aging function and exponential aging function. In particular, with a linear
aging function, the AoI from IoT device $i$ at the beginning of time slot
$t\in\mathbb{Z}_{+}$ is:

$a_{i}(t)=t-\delta_{i}(t),$ (3)

where $\delta_{i}(t)$ is time slot at which the most recent message from
device $i$ received by the BS was generated. With an exponential aging
function, the AoI from IoT device $i$ at the beginning of time slot
$t\in\mathbb{Z}_{+}$ is:

$b_{i}(t)=2^{t-\delta_{i}(t)-1}.$ (4)

Although a specific linear and exponential aging functions are considered, our
proposed centralized and distributed approaches to minimize the AoI are not
limited to these aging functions only, and any type of aging function can be
used.
In a scenario where all IoT devices have the same linear aging function with
slope $1$, the IoT devices and the BS can easily determine the AoI of the
messages by simply counting the number of time slots passed since the most
recently received message was generated [10]. However, in our system model
where different aging functions coexist, the aging function of a given message
is determined by the content of the message[35]. For instance, the aging
function of a message whose content is critical would be the exponential aging
function $b_{i}(t)$, while the aging function of a message whose content is
normal would be the linear aging function $a_{i}(t)$ [33]. This implies that
the BS cannot determine the aging function directly before receiving it, and,
thus, the BS cannot compute the AoI of the messages. Therefore, the devices
determine the aging function of their own message and compute the current AoI.
To capture the heterogeneity among the IoT devices, the IoT devices are
classified into different types based on the probabilistic properties of their
messages. A typical IoT device would not always have a time-sensitive message
to send to BS. Additionally, a device that usually sends time-insensitive
messages may sometimes have a critical message to send. In our model, we
consider two types of devices. Type $1$ devices are more likely to have
linearly aging messages than exponentially aging messages. In other words,
type $1$ devices have the messages with aging function $a_{i}(t)$ with
probability $m_{1}$ and have messages with aging function $b_{i}(t)$ with
probability $(1-m_{1})$ with $1>m_{1}>0.5$. Type $2$ devices are more likely
to have exponentially aging messages than linearly aging messages. In other
words, type $2$ devices have messages with aging function $b_{i}(t)$ with
probability $m_{2}$ and have messages with aging function $a_{i}(t)$ with
probability $(1-m_{2})$ with $1>m_{2}>0.5$. We assume that the characteristics
of devices types, such as $m_{1}$ and $m_{2}$, are known to the BS, but the BS
does not know the type of a given device. Although having different types of
messages realistically models the heterogeneity of the IoT devices, this makes
the RB allocation more challenging, because the messages transmitted by a
given device may have different aging functions. With non-linear aging
functions and heterogeneous device types, the problem of AoI minimization is
different from AoI minimization with only linear aging function and
homogeneous devices. Hence, next we investigate the problem of non-linear AoI
minimization with coexistence of different aging functions and heterogeneous
devices.

##  III Non-linear AoI Minimization

To minimize the average instantaneous AoI, the devices with highest AoI are
permitted to transmit to the BS, and the AoI of different devices are compared
to decide which devices are allocated the RBs in a massive IoT. Without
coexistence of different aging functions, comparing AoI from different devices
to allocate the limited RBs is simple. If all devices have same linear aging
function $a_{i}(t)$, then $a_{i}(\tau)>a_{h}(\tau)$ implies
$a_{i}(\tau+\beta)>a_{h}(\tau+\beta)$ for any positive integers $\tau$ and
$\beta$ given that devices $i$ and $h$ do not transmit successfully to the BS.
Therefore, in a massive IoT with $N>R$, comparing current AoI with $t=\tau$ at
time slot $\tau$ can be used to decide which $R$ out of $N$ devices transmit
and to minimize the average instantaneous AoI. Furthermore, using current AoI
with $t=\tau$ or using future AoI with $t=\tau+\beta$ at time slot $\tau$ is
equivalent, when all devices have same linear aging function $a_{i}(t)$.
When a linear aging function $a_{i}(t)$ and an exponential aging function
$b_{i}(t)$ coexist, it is insufficient to only compare the AoI of different
devices to minimize the average instantaneous AoI, and RBs must be allocated
considering the aging functions to minimize the average instantaneous AoI. For
instance, even if a device $i$ with $b_{i}(t)$ has lower AoI than a device $h$
with $a_{h}(t)$, device $i$ will eventually have higher AoI than device $h$,
because $b_{i}(t)$ increases faster than $a_{h}(t)$. Therefore, the AoI
comparison must take aging functions into account, and one way to consider the
aging functions is to compare the future AoI.
The optimization problem to minimize the average instantaneous AoI at time
slot $\tau$ is:

$\displaystyle\min_{\boldsymbol{n}}$ $\displaystyle\ \
\frac{1}{N}\left(\sum_{i\in\boldsymbol{n}}z_{i}^{\prime}(\tau)+\sum_{i\not\in\boldsymbol{n},i\in\boldsymbol{N}}z_{i}(\tau)\right)$
(5) s.t. $\displaystyle\ \ \boldsymbol{n}\subseteq\boldsymbol{N},$ (6)
$\displaystyle\ \ |\boldsymbol{n}|=R,$ (7)

where $\boldsymbol{N}=\\{1,\cdots,N\\}$ is set of all devices,
$z_{i}^{\prime}(\tau)$ is aging function of device $i$ such that
$\delta_{i}(\tau)\neq\delta_{i}(\tau-1)$ is updated, and $z_{i}(\tau)$ is
aging function of device $i$ such that $\delta_{i}(\tau)=\delta_{i}(\tau-1)$.
$\boldsymbol{n}$ is a set of all devices allocated the RBs at $(\tau-1)$,
while $\boldsymbol{N}-\boldsymbol{n}$ is a set of all devices not allocated
the RBs at $(\tau-1)$. Next, for the problem of instantaneous AoI
minimization, we prove that performing RB allocation based on the future AoI
achieves a lower average instantaneous AoI than an alternative that is based
on the current AoI.

######  Proposition 1.

In a massive IoT where $N>R$, if there are different aging functions
$a_{i}(t)$ and $b_{i}(t)$, comparing the future AoI with $t=\tau+\beta$ for
some positive integer $\beta$ at time slot $\tau$ to determine the RB
allocation achieves a lower average instantaneous AoI than comparing the
current AoI with $t=\tau$.

###### Proof.

See Appendix -A. ∎

From Proposition 1, we observe that allocating RBs to the devices with highest
future AoI results in a lower overall average instantaneous AoI of all devices
at all time slots than allocating RBs to the devices with highest current AoI.
It is important to note that the current AoI at the time slot of successful
transmission is used to compute the average instantaneous AoI, and the future
AoI is only used to determine the RB allocation. In Proposition 1, the value
of the positive integer $\beta$ in determining which future AoI to use for the
RB allocation is a design parameter, and different values of $\beta$ have
different effects. If higher values of $\beta$ are used, devices with
exponentially aging messages are more likely to be allocated the RBs than
devices with linearly aging messages. This implies that devices with
exponentially aging messages are allocated the RBs even when their current AoI
is low, while devices with linearly aging messages are not allocated the RBs
even when their current AoI is high. Therefore, the exponentially aging
messages are being transmitted before the linearly aging messages. In other
words, with higher values of $\beta$, the average instantaneous AoI of IoT
devices with exponentially aging messages is lower, while the average
instantaneous AoI of IoT devices with linearly aging messages is higher.
Furthermore, using higher values of $\beta$ for the future AoI does not
necessarily achieve a lower average instantaneous AoI, and $\beta$ can be
chosen depending on how much the exponentially aging messages are prioritized
over the linearly aging messages. In our system model, the centralized and the
distributed RB allocations use future AoI with $\beta=1$.
We consider that the IoT devices may have messages requiring multiple RBs to
successfully transmit to the BS. When the messages take multiple RBs to
successfully transmit, $\delta_{i}(t)$ in (3) and (4) will represent the time
slot during which the most recent message from device $i$, which is fully
received by BS, was generated. In this case, the devices must determine how to
transmit the messages taking multiple RBs. In particular, if a device $i$ has
a message that requires $n_{i}$ RBs to transmit, then the message may be
transmitted simultaneously by using $n_{i}$ RBs at a given time slot,
consecutively by using $1$ RB each time for $n_{i}$ time slots, or jointly by
using both simultaneous and consecutive transmissions. The simultaneous
transmission may complete the transmission at once reducing the AoI, but it
has high $R_{i,t}$ and outage probability $p_{i,t}$ (2). A consecutive
transmission achieves its lowest outage probability $p_{i,t}$ with
$R_{i,t}=1$, but it takes the largest number of time slots to completely
transmit increasing the AoI. Therefore, the problem of AoI minimization must
consider the outage probability. The optimization problem to minimize the
average instantaneous AoI for a device $i$ with a linearly aging message
requiring $n_{i}$ RBs at time slot $\tau$ is:

$\displaystyle\min_{\boldsymbol{R}}$ $\displaystyle\ \
a_{i}\left(\tau+\sum_{j=\tau}^{\tau+n_{i}-1}(1-p_{i,j})^{-1}\right),$ (8) s.t.
$\displaystyle\ \ \sum\nolimits_{j=\tau}^{\tau+n_{i}-1}R_{i,j}=n_{i},$ (9)
$\displaystyle\ \ 0\leq R_{i,j}\leq R\ \forall\ j,$ (10)

where $\boldsymbol{R}=[R_{i,\tau},...,R_{i,\tau+n_{i}-1}]$. Since
$R_{i,\tau}\in\mathbb{Z}_{+}$, $|\boldsymbol{R}|=n_{i}$, and $n_{i}$ is
typically small for the IoT devices [45], the solution space of optimization
problem (8) is finite and small. Therefore, the optimization problem can be
solved easily using any discrete optimization method, such as combinatorial
optimization. In particular, for any $n_{i}$, the optimization problem (8) can
be mapped as a directed graph with $(1-p_{i,j})^{-1}$ as weights to find a
shortest path. When a device uses $R_{i,t}$ RBs simultaneously, $(1-p_{i,t})$
is the probability of successful transmission given that duplicate RB
selection did not occur. Taking $(1-p_{i,t})$ as the success probability in a
geometric distribution, the expected number of time slots needed for the
successful transmission when using $R_{i,t}$ RBs simultaneously is
$(1-p_{i,t})^{-1}$, which is the mean of the geometric distribution.
Therefore, $\sum_{j=\tau}^{\tau+n_{i}-1}(1-p_{i,t})^{-1}$ is the expected
number of time slots needed to transmit a message requiring $n_{i}$ RBs. If a
device $i$ has an exponentially aging message, $b_{i}(t)$ replaces $a_{i}(t)$
in (8). The solution to the optimization problem (8) determines the number of
RBs $R_{i,\tau}$ that a device $i$ should be allocated with at time slot
$\tau$ so that the average instantaneous AoI is minimized. Furthermore, the
solution to the optimization problem is used for centralized and distributed
approaches for the RB allocation.

##  IV Resource Block Allocation

In a massive IoT with $N>R$, RB allocation is a challenging problem especially
given the high heterogeneity among IoT devices and the messages. RB allocation
in an IoT can be done in a centralized way or in a distributed way. Moreover,
RB allocation schemes can achieve a lower average instantaneous AoI by
allocating the limited RBs to IoT devices with higher future AoI. Centralized
RB allocation scheme is based on a priority scheduling improved with maximum
likelihood to determine the aging functions and to learn the device types. The
proposed distributed RB allocation scheme in Algorithm 1 is designed to enable
only the devices with sufficiently high future AoI to transmit, and the
proposed stochastic crowd avoidance algorithm is proved to converge to an NE
of the formulated game.

###  IV-A Centralized RB Allocation

For centralized RB allocation, the BS allocates the RBs to the IoT devices. In
a time slot. the centralized approach has two phases. The active devices
request for the RB using RACH in the first phase. If an active device is
allocated an RB, the active device transmits its message to the BS in the
second phase. Although there will be no duplicate RB usage causing a
transmission failure in the second phase, there may be RACH preamble collision
causing an RB request failure in the first phase. Therefore, using centralized
RB allocation scheme, a device fails to transmit to the BS because of the RACH
preamble collision, the outage based on SNR, and the lack of RB allocation.
We let $P$ be the number of RACH preambles and $N_{t}$ be the number of active
devices at time slot $t$. The probability of the RACH preamble collision
$c_{t}$ at time slot $t$ is:

$c_{t}=1-\left(\frac{P-1}{P}\right)^{N_{t}-1},$ (11)

which is the probability of more than one active device using a given RACH
preamble. If a device fails to request for an RB at time $t$ with probability
$c_{t}$, then this is equivalent to a transmission failure. However, if a
device $i$ successfully requests for an RB at time $t$, IoT device $i$ sends
the information about its current AoI $C_{i}$ and the necessary number of RBs
$R_{i,t}$ at time slot $t$. After gathering the information from the devices,
the BS determines the RB allocation based on the future AoI of devices to
minimize the average instantaneous AoI.
In the second phase, the BS allocates the RBs to the active devices using a
priority scheduling based on the future AoI. The priority scheduling allocates
the $R$ RBs to at most $R$ active devices with the highest future AoI,
minimizing the average instantaneous AoI. If a device $i$ with high future AoI
has $R_{i,t}>1$, then IoT device $i$ may be allocated more than $1$ RB at time
slot $t$. The problem in the second phase is determining the future AoI using
the received current AoI because of the coexistence of different aging
functions. In other words, the BS does not know the aging function of an
active device $i$, and the BS must determine the aging function to compute the
future AoI $F_{i}$, which is used for the priority scheduling scheme to
achieve a lower average instantaneous AoI as shown in Proposition 1. However,
the BS can determine the current aging function of an active device $i$ from
$C_{i}$.
The BS can determine that the aging function of an active device $i$ is
$a_{i}(t)$, when $C_{i}$ cannot be derived using $b_{i}(t)$. The possible
values of AoI using $a_{i}(t)$ are $\\{1,2,3,4,...\\}$, and the possible
values of the AoI using $b_{i}(t)$ are $\\{1,2,4,8,...\\}$. Therefore, the
values of AoI that are only possible using $a_{i}(t)$ are $\\{3,5,6,7,...\\}$.
If the received current age $C_{i}$ from an active device $i$ is one of
$\\{3,5,6,7,...\\}$, then the aging function is $a_{i}(t)$, and, thus, the
future AoI $F_{i}$ of device $i$ is $C_{i}+1$. The BS can also determine the
aging functions of active devices by using regression. For an active device
$i$, the BS can use the AoI from the most recently received uplink request
from device $i$ and $C_{i}$ to determine if the aging function is $a_{i}(t)$
or $b_{i}(t)$. After determining the aging functions of active devices, the BS
can compute the future AoI $F_{i}$ of active devices and learn the device
types, which are used for the priority scheduling scheme with learning. The BS
can use either of the two methods to accurately determine the current aging
functions, but it is not always possible to use these methods. When both
methods are not possible to use in a given time slot due to RACH preamble
collision, the BS uses the expected value of $F_{i}$ for the priority
scheduling scheme.
The BS can compute the expected value of $F_{i}$ of an active device $i$ by
learning the device type of device $i$. The BS can learn the type of a device
$i$ by using the previous data from the instances that the BS was able to
determine the aging function of messages from device $i$. In particular, the
BS can use a maximum likelihood to determine the device types. We let
$\mathcal{S}$ be a set of all device types and $\boldsymbol{O}_{i}$ be a
vector of aging functions that a device $i$ had that the BS was able to
determine exactly. Furthermore, we let $k_{i,f}$ be the number of times that
the BS determined device $i$ to have aging function $f$. Assuming that the
aging functions of a device $i$ are determined independently, the learned type
$H_{i}\in\mathcal{S}$ of a device $i$ is:

$\displaystyle H_{i}$
$\displaystyle=\operatorname*{\arg\\!\max}\limits_{s\in\mathcal{S}}\Pr(\boldsymbol{O}_{i}\mid
s)=\operatorname*{\arg\\!\max}\limits_{s\in\mathcal{S}}\prod\limits_{f\in\mathcal{F}}{\Pr(f\mid
s)}^{k_{i,f}},$ (12)
$\displaystyle=\operatorname*{\arg\\!\max}\limits_{s\in\mathcal{S}}\sum\limits_{f\in\mathcal{F}}{k_{i,f}}\ln(\Pr(f\mid
s)),$ (13)

where $\mathcal{F}$ is a set of all aging functions. For our model, the values
of $\Pr(f\mid s)$ for any $f\in\mathcal{F}$ and $s\in\mathcal{S}$ are known.
In particular, $\Pr(a_{i}\mid s=1)=m_{1}$, $\Pr(b_{i}\mid s=1)=1-m_{1}$,
$\Pr(a_{i}\mid s=2)=1-m_{2}$, and $\Pr(b_{i}\mid s=2)=m_{2}$. Therefore, the
maximum likelihood in (13) can be solved by the BS directly.
Once the device type of a device $i$ is learned, the expected future AoI
$\mathbb{E}[F_{i}]$ of device $i$ can be computed. For our model, if
$H_{i}=1$, then the expected future AoI $\mathbb{E}[F_{i}\mid H_{i}=1]$ is:

$\mathbb{E}[F_{i}\mid H_{i}=1]=m_{1}(C_{i}+1)+(1-m_{1})(2C_{i}).$ (14)

If $H_{i}=2$, then the expected future AoI $\mathbb{E}[F_{i}\mid H_{i}=2]$ is:

$\mathbb{E}[F_{i}\mid H_{i}=2]=(1-m_{2})(C_{i}+1)+m_{2}(2C_{i}).$ (15)

The expected value of $F_{i}$ is used for the priority scheduling scheme only
if the exact value of $F_{i}$ cannot be determined.
Priority scheduling determines the RB allocation among the active IoT devices
based on the future AoI $F_{i}$. In a time slot $\tau$, the RBs are allocated
first to the devices with the highest $F_{i}$. Furthermore, for a device $i$
with highest $F_{i}$ at time slot $\tau$, the number of RBs allocated to
device $i$ is $R_{i,\tau}$. If some of the active devices have same $F_{i}$,
then the RBs are allocated first to the devices whose type is more likely to
have a faster aging function. For instance, if a device $i$ is device type
$1$, a device $j$ is device type $2$, and $F_{i}=F_{j}$, then device $j$ has a
priority over device $i$, because device $j$ is more likely to have
exponentially aging messages. The RBs are allocated to the active devices
until all RBs are allocated or all active devices are allocated the RBs.

Algorithm 1 Priority scheduling based on future AoI at time slot $t$.

1: Receive values $C_{i}$ and $R_{i,t}$, and initialize $R$.

2: Compute $F_{i}$ or $\mathbb{E}[F_{i}]$ for each $C_{i}$.

3: for $j=1,2,\cdots$

4: $\mathcal{Z}_{1}\leftarrow$ set of type $1$ devices with $j$-th highest
value among $F_{i}$.

5: $\mathcal{Z}_{2}\leftarrow$ set of type $2$ devices with $j$-th highest
value among $F_{i}$.

6: for all $i\in\mathcal{Z}_{2}$

7: if $R>0$,

8: Allocate $\textrm{min}(R,R_{i,t})$ RBs to device $i$.

9: $R\leftarrow R-\textrm{min}(R,R_{i,t})$. end if

10: end for

11: for all $i\in\mathcal{Z}_{1}$

12: if $R>0$,

13: Allocate $\textrm{min}(R,R_{i,t})$ RBs to device $i$.

14: $R\leftarrow R-\textrm{min}(R,R_{i,t})$. end if

15: end for

16: end for

One of the major problems with priority scheduling is the infinite blocking of
low-priority tasks. However, since the priority depends on the future AoI, the
priority of low-priority messages increases with time. Therefore, regardless
of the aging function or the device type, the messages will eventually be
allocated the RBs to transmit to the BS. One of the limitations of centralized
RB allocation scheme is the overhead related to the RB request via RACH. With
the higher number of active devices $N_{t}$ at time $t$, the probability of
the RACH preamble collision $c_{t}$ becomes significant, and, thus, more
transmission failures occur. Furthermore, with centralized RB allocation
scheme, a frequent communication between the devices and the BS is required,
which may not be viable for the IoT devices [46]. However, the main advantage
of centralized RB allocation scheme is that the RBs are fully utilized.

###  IV-B Distributed RB Allocation

Distributed RB allocation enables the devices to allocate the RBs in a self-
organizing manner without any intervention from the BS. Since a duplicate RB
selection results in transmission failures, the active devices must choose the
RBs such that no other device is choosing the same RB. Furthermore, the
distribution RB allocation can be modeled as one-to-one association between
the RBs and the devices. The behavior of the devices wanting to choosing an RB
alone can be formulated as a minority game [47].
A suitable minority game for distributed RB allocation in an IoT is the
Kolkata paise restaurant (KPR) game [37]. The KPR game is a repeated game in
which the customers simultaneous go to one of the restaurants, which can only
serve one customer each. Additionally, the cost of going to a restaurant is
the same for all restaurants, and a customer can only go to one restaurant at
any given time. In the KPR game, the players are the customers, whose action
in each iteration is to choose one of the restaurants. The payoff of a given
player depends on the utility of the chosen restaurants and the number of
players choosing the same restaurant. Given players, actions, and payoffs in a
game, one important stable solution is an NE. A vector of actions is an NE if
no player can achieve a higher payoff by a unilateral change of action. For
the KPR game, the existence of an NE depends on the utilities of the
restaurants [37], and an NE is when all customers go to different restaurants
and none of the customers have the utility of $0$. If an NE exists in the KPR
game, it coincides with the socially optimal solution, which is when all
restaurants are being utilized.
The fundamental structure of the KPR game can be readily extended for our IoT
model. The customers can be modeled as IoT devices, and the restaurants can be
modeled as the RBs. Furthermore, the cost of using any of the RBs is same.
However, there are significant differences between the KPR game and the IoT
game. In the KPR game, the number of customers and the number of restaurants
are the same, and each customer goes to one of the restaurants at every
iteration. In the IoT game, the number of devices $N$ and the number of RBs
$R$ may not be the same, and not all devices are active and need to use the
RBs at each time slot. The most significant difference is the payoff in the
case of duplicate RB selection. When multiple customers choose the same
restaurant in the KPR game, one of those customers is randomly chosen to get
the full payoff, while other customers with duplicate selection get a zero
payoff. However, in the IoT game, all devices that choose the same RB get a
zero payoff because of the transmission failures.
For our AoI minimization, the players are the $N$ IoT devices, and their
action is to transmit using the RBs or not to transmit. We let $\mathcal{R}$
be the set of $R$ RBs and let $x_{i}(t)$ be the action of device $i$ at time
slot $t$. If $x_{i}(t)\in\mathcal{R}$, then device $i$ transmits using the RB
in $x_{i}(t)$ at time slot $t$. If $x_{i}(t)=0$, then device $i$ does not
transmit at time slot $t$. at each time slot, the payoff of each device
depends on the actions of all devices. If a device transmits successfully by
using an RB alone, then the payoff is $\rho$. Furthermore, a successful
transmission using any of the RBs has the same payoff of $\rho$. If a device
transmits unsuccessfully due to a duplicate RB usage, then the payoff is
$-\gamma$. The transmission failure has a negative payoff, because the energy
is consumed for the transmission without success. Additionally, the
transmission failure using any of the RBs has the same payoff of $-\gamma$,
and $\rho$ and $\gamma$ are positive numbers such that $\rho>\gamma$.
To minimize the AoI of the devices, active devices with lower AoI must not
transmit, while the active devices with high AoI need to transmit. Using a
distributed RB allocation scheme, the devices must know the AoI of other
devices to determine if their own AoI is high enough to transmit. We assume
that the active devices broadcast their own future AoI $F_{i}$ to other
devices within the communication range $r_{c}$, and the communication resource
for this broadcast is pre-allocated. Moreover, we assume that device-to-device
communication links are orthogonal to the uplink communication as done in [48,
49, 50, 51, 52]. Similar to the overhead related to the RACH uplink request
for centralized RB allocation scheme, the communication between the devices to
share the AoI can be seen as the overhead for distributed RB allocation
scheme. However, depending on $r_{c}$, the active devices may not know $F_{i}$
of all other active devices. We let $\alpha_{i}$ be the active status of a
device $i$ such that $\alpha_{i}=0$ implies that device $i$ is inactive and
$\alpha_{i}=1$ implies that device $i$ is active. We let $\boldsymbol{A}$ be a
vector that captures the future AoI $F_{i}$ of all active devices, and
$\boldsymbol{A}_{i}$ be a vector of the future AoI $F_{i}$ of the active
devices within $r_{c}$ of an active device $i$. With $r_{c}$ sufficiently
large, $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for all devices, where
$|\boldsymbol{A}|$ is the cardinality of $\boldsymbol{A}$. For an active
device $i$, if $F_{i}$ is higher than $\kappa$-th highest AoI in
$\boldsymbol{A}_{i}$, then the active device $i$ transmits. $\kappa$
determines if $F_{i}$ is sufficiently higher than the future AoI of other
active devices, and we let $\boldsymbol{A}_{i}(\kappa)$ be the $\kappa$-th
highest AoI in $\boldsymbol{A}_{i}$. Moreover, $\kappa$ should ensure that the
number of transmitting devices $T_{t}$ at time slot $t$ is equal to $R$ such
that all transmitting devices can be allocated with the RB. If $T_{t}$ is
higher than $R$, then there are at least two active devices with transmission
failure, which causes the average instantaneous AoI to increase. If $T_{t}$ is
less than $R$, then there are some of the RBs not used by any of the active
devices, which may cause the average instantaneous AoI to increase. However,
$T_{t}=R$ is difficult to achieve when $r_{c}$ is not sufficiently large and
$|\boldsymbol{A}_{i}|<|\boldsymbol{A}|$.
When $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$, the devices have full
information on the future AoI $F_{i}$ of the active devices. Moreover, the
devices know all active devices. Since the devices have full information of
$F_{i}$, an active device $i$ transmits if $F_{i}\geq\boldsymbol{A}_{i}(R)$,
and an active device $i$ does not transmit if $F_{i}<\boldsymbol{A}_{i}(R)$.
Therefore, $\kappa=R$ when $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for all
$i$. This ensures that $R$ active devices transmit, while $|\boldsymbol{A}|-R$
devices do not transmit. Therefore, the number of transmitting devices $T_{t}$
at time slot $t$ is equal to $R$. To formulate this decision to transmit or
not to transmit into the payoff, the payoff $y_{\textrm{full}}$ when an active
device $i$ does not transmit is:

$y_{\textrm{full}}(\boldsymbol{A}_{i})=(\rho+\eta)\theta_{\mathbb{R}_{+}}(\boldsymbol{A}_{i}(R)-F_{i}-\eta)\\\
-(\gamma+\eta)\theta_{\mathbb{R}_{+}}(F_{i}-\boldsymbol{A}_{i}(R)),$ (16)

where $\eta$ is a real number in $(0,1)$ and $\theta_{\mathbb{R}_{+}}$ is an
indicator function such that:

$\theta_{\mathbb{R}_{+}}(x)=\left\\{\begin{array}[]{ll}1\hfill&\text{if}\
x\in[0,\infty),\\\ 0\hfill&\text{if}\ x\not\in[0,\infty).\end{array}\right.$
(17)

The function of $\eta$ in payoff functions is to ensure that the payoff
functions are used as intended and only appropriate indicator function is
activated. It is important to note that
$y_{\textrm{full}}(\boldsymbol{A}_{i})$ does not depend on actions of the
players, because the decision to transmit or not to transmit only depends on
future AoI. Given the payoff in (16), the $R$ active devices with
$F_{i}\geq\boldsymbol{A}_{i}(R)$ transmit, because their payoff of not
transmitting is $-(\gamma+\eta)$. The $|\boldsymbol{A}|-R$ active devices with
$F_{i}<\boldsymbol{A}_{i}(R)$ do not transmit, because their payoff of not
transmitting is $\rho+\eta$. Therefore, IoT devices with $R$ highest future
AoI transmit, while other devices do not transmit.
In a more realistic scenario where IoT devices do not have full information of
$F_{i}$, $|\boldsymbol{A}_{i}|<|\boldsymbol{A}|$, and the devices do not know
all active devices. It is difficult to make only $R$ active devices to
transmit at time slot $t$, and, thus, $\kappa$ is designed to make
$T_{t}\approx R$. For the case of $|\boldsymbol{A}_{i}|<|\boldsymbol{A}|$,
$\kappa$ is:

$\kappa=\left\lceil\frac{R}{|\boldsymbol{A}|}|\boldsymbol{A}_{i}|\right\rceil,$
(18)

where $\kappa=R$ in the case of $\boldsymbol{A}=\boldsymbol{A}_{i}$. However,
with partial information, the active devices do not know $\boldsymbol{A}$ in
(18). $|\boldsymbol{A}|$ is the number of active devices, and the expected
number of newly active devices is $Nv_{a}$. However, with previously active
devices yet to transmit successfully, $|\boldsymbol{A}|$ is typically greater
than $Nv_{a}$. Therefore, in (18), $|\boldsymbol{A}|$ can be estimated with
$Nv_{a}\zeta$, where $\zeta$ is a design parameter to consider the number of
previously active devices yet to transmit successfully. With higher values of
$\zeta$, the number of transmitting devices $T_{t}$ at time slot $t$ is
smaller, while $T_{t}$ is bigger with smaller values of $\zeta$. Therefore,
with approximation for $|\boldsymbol{A}|$, $\kappa$ is:

$\kappa=\left\lceil\frac{R}{Nv_{a}\zeta}|\boldsymbol{A}_{i}|\right\rceil.$
(19)

For an active device $i$, $\kappa$ in (19) approximates if $F_{i}$ is
sufficiently higher than the future AoI of other active devices based on the
percentile of $F_{i}$ on the known vector of future AoI $\boldsymbol{A}_{i}$.
With $|\boldsymbol{A}_{i}|<|\boldsymbol{A}|$, the payoff $y_{\textrm{act}}$
when an active device $i$ does not transmit is:

$y_{\textrm{act}}(\boldsymbol{A}_{i})=(\rho+\eta)\theta_{\mathbb{R}_{+}}(\boldsymbol{A}_{i}(\kappa)-F_{i}-\eta)\\\
-(\gamma+\eta)\theta_{\mathbb{R}_{+}}(F_{i}-\boldsymbol{A}_{i}(\kappa)).$ (20)

It is important to note that $y_{\textrm{act}}(\boldsymbol{A}_{i})$ is equal
to $y_{\textrm{full}}(\boldsymbol{A}_{i})$, when the active devices have full
information with $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ and $\kappa=R$.
Similar to $y_{\textrm{full}}(\boldsymbol{A}_{i})$ (16), with the payoff
$y_{\textrm{act}}(\boldsymbol{A}_{i})$, the active devices with sufficiently
high $F_{i}$ satisfying $F_{i}\geq\boldsymbol{A}_{i}(\kappa)$ transmit, while
the active devices with $F_{i}$ such that $F_{i}<\boldsymbol{A}_{i}(\kappa)$
do not transmit. Moreover, $y_{\textrm{act}}(\boldsymbol{A}_{i})$ also does
not depend on actions of the players.
In the IoT game, the payoff needs to consider the inactive devices. The
inactive devices with $\alpha_{i}=0$ do not transmit as they do not have
messages to transmit. The payoff $y_{\textrm{nt}}$ when an device $i$ does not
transmit is:

$y_{\textrm{nt}}(\boldsymbol{A}_{i},\alpha_{i})=(1-\alpha_{i})(\rho+\eta)+\alpha_{i}y_{\textrm{act}}(\boldsymbol{A}_{i}).\vspace{-1mm}$
(21)

With payoff $y_{\textrm{nt}}(\boldsymbol{A}_{i},\alpha_{i})$ for not
transmitting, the inactive devices with $\alpha_{i}=0$ do not transmit as they
get payoff of $\rho+\eta$. The active devices with $\alpha_{i}=1$ decide to
transmit or to not transmit based on $\kappa$ and future AoI. We let
$\boldsymbol{x}(t)=[x_{1}(t),x_{2}(t),\cdots,x_{N}(t)]$ be a vector of all
actions of $N$ devices at time slot $t$. For a given $\boldsymbol{x}(t)$, the
payoff function $y_{i}(\boldsymbol{x}(t),\boldsymbol{A}_{i},\alpha_{i})$ for a
device $i$ at time slot $t$ is:

$y_{i}(\boldsymbol{x}(t),\boldsymbol{A}_{i},\alpha_{i})\\\
=\left\\{\begin{array}[]{ll}\rho\hfill&\text{if}\ x_{i}(t)\neq x_{j}(t)\
\forall\ j\neq i,x_{i}(t)\neq 0,\\\ -\gamma\hfill&\text{if}\ \exists\ j\neq i\
\text{s.t.}\ x_{j}(t)=x_{i}(t)\neq 0,\\\
y_{\textrm{nt}}(\boldsymbol{A}_{i},\alpha_{i})\hfill&\text{if}\ x_{i}(t)=0.\\\
\end{array}\right.\vspace{-2mm}$ (22)

In a simple game where $N=R=2$ with $v_{a}=1$, the payoffs of two devices at
each time slot is summarized in Table I. NE in this IoT game is
$\boldsymbol{x}(t)=[1,2]$ or $\boldsymbol{x}(t)=[2,1]$. For simple IoT game,
NE is when two devices choose different RBs and get the payoff of $\rho$. If
one device deviates from NE and the other device does not deviate from NE, the
device deviating from NE gets the lower payoff of $-\gamma$ or
$-(\gamma+\eta)$. Furthermore, in the IoT game, NE implies that a duplicate RB
selection does not occur. An NE for a more general case of the IoT game can be
found with certain conditions.

Table I: IoT game with $N=R=2$. | $x_{1}(t)=1$ | $x_{1}(t)=2$ | $x_{1}(t)=0$
---|---|---|---
$x_{2}(t)=1$ | $(-\gamma,-\gamma)$ | $(\rho,\rho)$ | $(-(\gamma+\eta),\rho)$
$x_{2}(t)=2$ | $(\rho,\rho)$ | $(-\gamma,-\gamma)$ | $(-(\gamma+\eta),\rho)$
$x_{2}(t)=0$ | $(\rho,-(\gamma+\eta))$ | $(\rho,-(\gamma+\eta))$ | $(-(\gamma+\eta),-(\gamma+\eta))$

######  Theorem 1.

For the IoT game with $N$ players with action
$x_{i}(t)\in\\{0,\mathcal{R}\\}$, payoff function $y_{i}(\boldsymbol{x}(t))$,
and $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for all $i$, any vector of actions
$\boldsymbol{x}(t)$ such that at most $R$ active devices with
$F_{i}\geq\boldsymbol{A}_{i}(R)$ transmit, the rest of the devices do not
transmit, and each of the RBs is used by at most one device is an NE.

###### Proof.

See Appendix -B. ∎

There are many sets of actions that satisfy the conditions described in
Theorem 1, and, thus, NE in the IoT game is not unique. For instance, when the
number of devices is equal to the number of RBs with $v_{a}=1$ in an IoT, an
NE is when each RB is used by one device, and, thus, the number of NEs in that
particular IoT game is $N!$. There are many NEs, because the payoff of
successful transmission does not depend on which RB is used. _Although there
are many NEs, the expected payoffs of devices at any given NE are the same,
and, thus, one of those NEs is chosen with distributed RB allocation algorithm
discussed in Section IV-B1._ Similar to the simple IoT game in Table I, an NE
for our IoT game implies that the number of transmitting devices $T_{t}$ is
equal to the number of RBs $R$ and that a duplicate RB selection does not
occur. Furthermore, at an NE, a transmitting device has one of the $R$ highest
AoI, and a device that is not transmitting is inactive or has low AoI. This is
because the payoff function with $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ is
designed to only allow the messages having the $R$ highest AoI to transmit.
Therefore, the convergence of a distributed RB allocation algorithm to an NE
reduces the average instantaneous AoI. However, when the devices only have
partial information such that $|\boldsymbol{A}_{i}|<|\boldsymbol{A}|$,
$\boldsymbol{x}(t)$ described in the Theorem 1 is not necessarily an NE,
because $\kappa$ is not necessarily equal to $R$.
In addition to the NE, another solution concept is a socially optimal solution
in which the overall payoff of an IoT game is maximized. In other words, a
vector of actions is a socially optimal solution when the sum of payoffs of
all devices is maximized. In an IoT game, a socially optimal solution is when
the devices with highest future AoI $F_{i}$ fully utilize RBs without any
duplicate RB selection. Therefore, similar to an NE in KPR game [37], an NE in
IoT game coincides with a socially optimal solution. A performance metric that
can be used to describe an NE and a socially optimal solution is a service
rate $s_{r}$, which is the percentage of RBs that are used by one device. NE
in Theorem 1 has a service rate of $1$, which implies that all RBs are used by
one device, or the highest possible service rate of $\nicefrac{{T_{t}}}{{R}}$.
With the number of transmitting devices $T_{t}$ approximately equal to $R$ via
IoT game design, a distributed RB allocation algorithm is necessary to enable
the transmitting devices to share RBs autonomously. Moreover, with existence
of a socially optimal NE in our IoT game, the convergence of a distributed RB
allocation algorithm to an NE is crucial in minimizing the average
instantaneous AoI. Therefore, to evaluate different RB allocation algorithms,
the convergence to an NE and the service rates are analyzed. The service rate
is an important metric to determine convergence to an NE, because a vector of
actions must achieve service rate of $1$ or highest service rate to be an NE.
Furthermore, the service rate is an important performance metric for the AoI,
because the higher service rate implies that more devices are transmitting
successfully at each time slot, reducing the average instantaneous AoI.
Therefore, a distributed RB allocation algorithm must achieve a service rate
of $1$ or increase the service rate as high as possible, because a high
service rate is required to achieve a low average instantaneous AoI.

####  IV-B1 Stochastic Crowd Avoidance

We propose a stochastic crowd avoidance (SCA) algorithm that enables the
devices to avoid using the RBs that are used by many devices stochastically
and to choose an RB for a successful transmission, as shown in Algorithm 2.
For the SCA algorithm, the devices need to share more information in addition
to their $F_{i}$ and can perform a channel sensing to determine the RBs that
were not used at a previous time slot [23, 24, 25], and [53]. At time slot
$t$, the devices that transmitted at the time slot $t-1$ share their previous
actions $x_{i}(t-1)\in\mathcal{R}$ and the previous payoff
$y_{i}(\boldsymbol{x}(t-1))$ of their transmission. We let
$\boldsymbol{X}_{i}$ be the vector of actions of the transmitting devices at
time slot $t-1$ that a device $i$ knows and $\boldsymbol{P}_{i}$ be the vector
of payoffs of the transmitting devices at time slot $t-1$ that a device $i$
knows. Furthermore, we let $\boldsymbol{X}_{i}(x)$ with $x\in\mathcal{R}$ be
the number of $x$ in $\boldsymbol{X}_{i}$. In other words,
$\boldsymbol{X}_{i}(x)$ is the number of devices that chose the RB $x$ at time
slot $t-1$ that a device $i$ knows. Learning from $\boldsymbol{X}_{i}$ and
$\boldsymbol{P}_{i}$, the proposed SCA algorithm enables a transmitting device
$i$ at time slot $t$ to not use the RBs that are being used successfully by
other devices and to avoid using the contended RBs stochastically.

Algorithm 2 SCA for device $i$ at time $t$.

1: Receive $\boldsymbol{X}_{i}$, $\boldsymbol{P}_{i}$, $\boldsymbol{A}_{i}$,
and $\mathcal{L}$.

2: if $x_{i}(t-1)\in\mathcal{R}$, $y_{i}(\boldsymbol{x}(t-1))=\rho$, and
$\alpha_{i}=1$,

3: $x_{i}(t)\leftarrow x_{i}(t-1)$.

4: else if $x_{i}(t-1)\in\mathcal{R}$, $y_{i}(\boldsymbol{x}(t-1))=\rho$, and
$\alpha_{i}=0$,

5: $j\leftarrow$ one neighboring device chosen with
$\frac{F_{j}}{\sum_{F_{h}\in\boldsymbol{A}_{i}}F_{h}}$.

6: $x_{j}(t)\leftarrow x_{i}(t-1)$.

7: else if $x_{i}(t-1)\in\mathcal{R}$ and
$y_{i}(\boldsymbol{x}(t-1))=-\gamma$,

8: $z\leftarrow 1$ with probability $\boldsymbol{X}_{i}(x_{i}(t-1))^{-1}$.

9: if $z=1$, $x_{i}(t)\leftarrow x_{i}(t-1)$.

10: else $x_{i}(t)\leftarrow$ randomly chosen from $\mathcal{L}$. end if.

11: else if $x_{i}(t-1)=0$,

12: $x_{i}(t)\leftarrow$ randomly chosen from $\mathcal{L}$.

13: end if.

Using SCA algorithm, at time slot $t$, a transmitting device $i$ determines
its RB usage based on $x_{i}(t-1)$ and $y_{i}(\boldsymbol{x}(t-1))$. If the
transmission at time slot $t-1$ is successful such that
$x_{i}(t-1)\in\mathcal{R}$ and $y_{i}(\boldsymbol{x}(t-1))=\rho$, then
transmitting device $i$ uses the same RB $x_{i}(t)=x_{i}(t-1)$. If the
transmission at time slot $t-1$ is unsuccessful such that
$x_{i}(t-1)\in\mathcal{R}$ and $y_{i}(\boldsymbol{x}(t-1))=-\gamma$, then
transmitting device $i$ uses the same RB $x_{i}(t)=x_{i}(t-1)$ with
probability $\boldsymbol{X}_{i}(x_{i}(t-1))^{-1}$ or chooses an RB from a set
$\mathcal{L}$ uniformly randomly. $\mathcal{L}$ is a set of the RBs that were
not used by any of the device at time slot $t-1$ determined with channel
sensing. If there is no transmission at time slot $t-1$ such that
$x_{i}(t-1)=0$, then the transmitting device $i$ chooses an RB from
$\mathcal{L}$ uniformly randomly. In the case where $v_{a}<1$, a device that
transmitted successfully at time slot $t-1$ may no longer be active at time
slot $t$. In this case, a device $i$ with $\alpha_{i}=0$ and
$y_{i}(\boldsymbol{x}(t-1))=\rho$ chooses a neighboring device $j$ with
$\alpha_{j}=1$ with a probability proportional to $F_{j}$, such that the
probability is $\nicefrac{{F_{j}}}{{\sum_{F_{h}\in\boldsymbol{A}_{i}}F_{h}}}$.
In our SCA algorithm, the RB that is used successfully at time slot $t-1$ is
also used successfully at time slot $t$ if $v_{a}=1$ or if there is an active
neighboring device. Moreover, with $r_{c}$ sufficiently large, the expected
number of transmitting devices using an RB that is used by more than one
device at the previous time slot $t-1$ is $1$ at the current time slot $t$.
This is because the probability of choosing the same RB after a transmission
failure is $\nicefrac{{1}}{{\boldsymbol{X}_{i}(x_{i}(t-1))}}$. The devices
avoid to use the same RB stochastically even after a transmission failure,
because the strict crowd avoidance causes the crowding in other RBs resulting
in more transmission failures. Furthermore, when a device $i$ chooses some
other RB such that $x_{i}(t)\neq x_{i}(t-1)$, device $i$ chooses from a set of
RBs $\mathcal{L}$ that were not used at time slot $t-1$. This is to avoid
using the RBs that are either used successfully or crowded, both of which
cause the transmission failures. With SCA algorithm design to avoid duplicate
RB selection, next we prove that the proposed SCA algorithm converges to an NE
under certain IoT system parameters.

######  Theorem 2.

When $N$ devices are always active with full information and use $1$ out of
$N$ RBs to transmit with negligible outage probability $p_{i,t}$ at each time
slot, the vector of actions $\boldsymbol{x}(t)$ converges to an NE using SCA.

###### Proof.

See Appendix -C. ∎

Under the conditions in Theorem 2, $\boldsymbol{x}(t)$ converges to an NE, and
this implies that the service rate increases to $1$. In general, SCA algorithm
increases the service rate, because an RB, which is used by $1$ device at
previous time slot $t-1$, is still used by $1$ device at current time slot
$t$. Therefore, SCA algorithm is effective in reducing the average
instantaneous AoI. However, SCA is susceptible to the high outage probability
$p_{i,t}$ based on the SNR. This is because SCA cannot distinguish the
transmission failure due to the duplicate RB selection and the transmission
failure due to the outage based on the SNR. Furthermore, with partial
information $|\boldsymbol{A}_{i}|<|\boldsymbol{A}|$, the devices also have
partial information of $\boldsymbol{X}_{i}$ and $\boldsymbol{P}_{i}$, and,
thus, the devices cannot choose $x_{i}(t)$ accurately in the case of
transmission failure.
In a massive IoT with $N>R$ and partial information, the vector of actions
$\boldsymbol{x}(t)$ does not converge to an NE using SCA, because it is not
possible to achieve service rate of $1$. The service rate cannot be $1$,
because the transmitting devices are changing every time slot and a duplicate
RB selection is inevitable. Since the service rate cannot be $1$, the average
instantaneous AoI in a massive IoT is higher than the average instantaneous
AoI in an ideal IoT described in Theorem 2. However, in a massive IoT, the
proposed SCA algorithm still enables the transmitting devices to
stochastically avoid duplicate RB selection with available information.
Therefore, the proposed SCA algorithm still increases the service rate and
reduces the average instantaneous AoI. However, in that case, it does not
reach an NE but rather a sub-optimal, heuristic solution. To evaluate
performance of the proposed SCA algorithm, next we study a random RB selection
for distributed RB allocation scheme.

####  IV-B2 Random RB Selection

One way for the transmitting devices to determine their RB usage is via random
selection. In other words, the actions $x_{i}(t)$ of the transmitting devices
are chosen uniformly random in $\mathcal{R}$. This random RB selection is used
as a baseline. Even with $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for all $i$,
the random RB selection is highly unlikely to achieve $\boldsymbol{x}(t)$ such
that each of the RBs is used by at most one device, which is the requirement
of $\boldsymbol{x}(t)$ to be an NE. Furthermore, the service rate $s_{r}$
using random RB selection for the transmitting devices is low.

######  Proposition 2.

At a time slot $t$, the service rate $s_{r}$ with $T_{t}$ transmitting devices
using random RB selection is:

$s_{r}=\frac{T_{t}}{R}\left(\frac{R-1}{R}\right)^{T_{t}-1},$ (23)

and, for a massive IoT with $N$ increasing to infinity, the service rate
$s_{r}$ is:

$\lim_{N\rightarrow\infty}s_{r}=\frac{T_{t}}{R-1}\exp\left(\frac{-T_{t}}{R}\right)$
(24)

###### Proof.

See Appendix -D. ∎

Under the conditions in Theorem 2, when $N$ devices are always active and use
$1$ out of $N$ RBs, the number of transmitting devices $T_{t}$ is equal to
$N$. In this case, the service rate using random RB selection is always less
than $1$ even with $N=R\geq 2$. On the other hand, for a massive IoT with
$N>R$, the service rate using random RB selection exponentially decreases to
$0$ as $N$ increases. Therefore, the random RB selection is not suitable for a
massive IoT in which the number of devices $N$ outnumbers the number of RBs
$R$, Furthermore, with low service rate, the probability of a successful
transmission is low for a device, and, thus, the average instantaneous AoI is
high.

##  V Simulation Results and Analysis

For our simulations, we consider a rectangular area with width $w$ and length
$l$ within which the $N$ devices are deployed following a Poisson point
process. We let $w=l=10$ m and $R=50$ with a $10$ MHz frequency band [54],
while the number of devices $N$ will be varied for analysis. We choose a time
slot duration of $1$ ms [55] and expected value of SNR of $20$ dB with
$\lambda=.1$ and $\sigma^{2}=0.001$. To vary outage probability $p_{i,t}$,
different values of $\epsilon$ are used. Moreover, a device is assumed to be
of type $1$ with probability $0.6$ with $m_{1}=0.75$, while a device is
assumed to be of type $2$ with probability $0.4$ with $m_{2}=0.75$. The
average of the current AoI $C_{i}$ at the time slot of successful transmission
is the performance metric for different RB allocation schemes, and their
performances are analyzed with varying $v_{a}$ and $p_{i,t}$.
For the centralized RB allocation scheme, the number of RACH preambles $P$ for
the uplink transmission request is $64$ [56]. Three different kinds of
priority scheduling are analyzed. Priority scheduling without learning [12,
13, 14, 15] does not learn the device types, and, hence, this scheme is used
for baseline comparison. The proposed priority scheduling with learning learns
the device types using maximum likelihood and information on $F_{i}$. Priority
scheduling with full information assumes that the BS always knows the types of
all devices, and, hence, this scheme is used for optimal performance
comparison. All three priority scheduling algorithms are analyzed with
$N=500$, while varying $v_{a}$ and $p_{i,t}$.

Figure 1: Average instantaneous AoI using centralized RB allocation schemes
while varying $v_{a}$.

Fig. 1 shows the average instantaneous AoI of the devices using centralized RB
allocation schemes for different values of the activation probability $v_{a}$
with $p_{i,t}=0.01$ and $\epsilon=1$. The average instantaneous AoI for the no
learning case quickly increases to $27.88$ and then increases slowly above
$30$, while the average instantaneous AoI for both learning and full
information quickly increases to $19.62$ and then increases slowly above $20$.
As $v_{a}$ increases, the average instantaneous AoI increases for all priority
scheduling algorithms, because more devices are transmitting and RACH preamble
collisions are more likely to occur. However, for $v_{a}>0.2$, the average
instantaneous AoI flattens and increases at a much slower rate with increasing
$v_{a}$ for all priority scheduling algorithms, because all RBs are fully
saturated. Moreover, there is a significant difference between priority
scheduling with learning and without learning. After the average instantaneous
AoI flattens, the difference of the average instantaneous AoI between priority
scheduling with learning and without learning is constantly about $8$. This
implies that the proposed priority scheduling scheme with learning achieves
about $26.7\%$ lower average instantaneous AoI when compared to simple
priority scheduling scheme. Hence, learning the device types is important to
decrease the average instantaneous AoI for priority scheduling. However, there
is an insignificant difference between priority scheduling with learning and
with full information, which implies that the learning is effective in
learning the device types.

Figure 2: Average instantaneous AoI using centralized RB allocation schemes
with different transmit powers while varying $v_{a}$.

Fig. 2 shows the average instantaneous AoI of the devices with different
transmit powers using centralized RB allocation schemes for different values
of the activation probability $v_{a}$ with $p_{i,t}=0.01$ and $\epsilon=1$.
The devices have different transmit powers such that their SNR values are
uniformly distributed random variables from $17.0$ dB to $21.8$ dB, and the
only difference between Fig. 1 and Fig. 2 is assumption on the transmit powers
of devices. The overall trends of the average instantaneous AoI for all three
centralized RB allocation schemes are similar to the trends shown in Fig. 1.
However, a notable difference is the average instantaneous AoI after the
curves flatten. After the average instantaneous AoI flattens, the average
instantaneous AoI increases slowly above $30$ for priority scheduling without
learning, increases slowly to $25$ for priority scheduling with learning, and
increases slowly to $23.5$ for priority scheduling with full information. With
different SNR values randomly assigned to the devices, some devices have
higher outage probability and other devices have lower outage probability
compared to the devices in Fig. 1. With exponentially aging messages, an
increase in the average instantaneous AoI from devices with higher outage
probability outweighs a decrease in the average instantaneous AoI from devices
with lower outage probability. Therefore, there is a slight increase in
average instantaneous AoI when the devices have different transmit powers.
However, similar to Fig. 1, the learning can still effectively decrease the
average instantaneous AoI, and priority scheduling with learning performs
similar to priority scheduling with full information even when the devices
have different transmit powers.

Figure 3: Average instantaneous AoI using centralized RB allocation schemes
while varying $p_{i,t}$.

Fig. 3 shows the average instantaneous AoI of the devices using centralized RB
allocation schemes for different values of the SNR outage probability
$p_{i,t}$ with $v_{a}=0.2$ and varying $\epsilon$ from $1$ to $20$. Unlike in
Fig. 1, the average instantaneous AoI does not flatten and increases at about
the same rate. With $p_{i,t}=0.02$, the average instantaneous AoI without
learning is $24.34$, and the average instantaneous AoI with learning is
$18.41$. With $p_{i,t}=0.16$, the average instantaneous AoI without learning
is $40.17$, and the average instantaneous AoI with learning is $27.45$.
Therefore, the difference between the average instantaneous AoI with learning
and without learning increases as $p_{i,t}$ increases. Furthermore, with high
$p_{i,t}$, the proposed priority scheduling scheme with learning achieves
about $31.7\%$ lower average instantaneous AoI when compared to simple
priority scheduling scheme. For a higher $p_{i,t}$ and more frequent
transmission failures, the AoI of the exponentially aging messages becomes
much higher than the AoI of the linearly aging messages. In this case, the
learning scheme, which enables the BS to accurately identify the messages
aging faster, becomes more crucial in reducing the average instantaneous AoI.
Furthermore, the difference between the average instantaneous AoI with
learning and with full information also increases as $p_{i,t}$ increases. This
is because it becomes increasingly difficult to learn the device types as
$p_{i,t}$ increases.
For the distributed RB allocation scheme, the communication range $r_{c}$
determines the information $\boldsymbol{A}_{i}$ that the devices have. For the
given dimensions of the deployment area, $r_{c}\geq 15$ m is sufficiently
large such that $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for any device $i$.
SCA algorithm is compared against two algorithms, which are the random RB
selection and the pre-determined RB selection. The pre-determined RB selection
scheme [37] is known as the dictator’s solution in the KPR game, and the RB
usage for a device $i$ is pre-determined based on the rank of $F_{i}$. For
instance, if $F_{i}$ is $\kappa$-th highest in $\boldsymbol{A}_{i}$ for
$\kappa\leq R$, device $i$ uses a specific RB as previously agreed among IoT
devices. The pre-determined RB allocation scheme requires full information
$|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for all $i$ and always achieves a
service rate $s_{r}$ of $1$. While the pre-determined RB selection is used for
optimal performance comparison, the random RB selection is used for baseline
comparison. To analyze different distributed RB allocation schemes, the
activation probability $v_{a}$, the SNR outage probability $p_{i,t}$, and the
communication range $r_{c}$ are varied. In addition to the average
instantaneous AoI, the service rate $s_{r}$ is evaluated for different
distributed RB allocation schemes.

Figure 4: Average instantaneous AoI and service rate using distributed RB
allocation schemes while varying $v_{a}$.

Fig. 4 shows the average instantaneous AoI and the service rate of the devices
using distributed RB allocation schemes for different values of the activation
probability $v_{a}$ with $p_{i,t}=0.01$, $\epsilon=1$, $r_{c}=10$ m, and
$N=200$. It is important to note that the expected number of newly active
devices at a given time slot is $Nv_{a}$, and, thus, the number of active
devices $N_{t}$ outnumbers the number of RBs $R$ for high values of $v_{a}$,
simulating a massive IoT. Moreover, with $r_{c}=10$ m, SCA only has partial
information such that $|\boldsymbol{A}_{i}|<|\boldsymbol{A}|$ for all $i$. The
service rate converges to $0.42$ for SCA with $v_{a}=0.25$, $0.41$ for SCA
with $v_{a}=0.35$, $0.39$ for SCA with $v_{a}=0.45$, and $0.35$ for random RB
allocation with $v_{a}=0.35$. As $v_{a}$ increases from $0.25$ to $0.45$, the
average instantaneous AoI increases from $22.16$ to $38.82$ using SCA. As
$N_{t}$ increases with increasing $v_{a}$, the transmission failure is more
likely to occur due to the duplicate RB selection, because $R$ is fixed.
Therefore, as $v_{a}$ increases, $s_{r}$ decreases, and the average
instantaneous AoI increases. The pre-determined RB allocation scheme achieves
a much lower average instantaneous AoI compared to SCA, because the pre-
determined RB allocation scheme requires and uses the full information.
Furthermore, the average instantaneous AoI with random RB allocation is
multiple orders of magnitude higher than the average instantaneous AoI with
SCA. Therefore, in a massive IoT with partial information, the proposed SCA
algorithm is the most suitable algorithm to achieve low average instantaneous
AoI as it balances between having full information and performing arbitrary
allocations.

Figure 5: Average instantaneous AoI and service rate using distributed RB
allocation schemes with different transmit powers while varying $v_{a}$.

Fig. 5 shows the average instantaneous AoI and the service rate of the devices
with different transmit powers using distributed RB allocation schemes for
different values of the activation probability $v_{a}$ with $p_{i,t}=0.01$,
$\epsilon=1$, $r_{c}=10$ m, and $N=200$. The devices have different transmit
powers such that their SNR values are uniformly distributed random variables
from $17.0$ dB to $21.8$ dB, and the only difference between Fig. 4 and Fig. 5
is assumption on the transmit powers of devices. The difference in the service
rates between Fig. 4 and Fig. 5 is insignificant. However, there is a notable
increase in the average instantaneous AoI in Fig. 5 compared to Fig. 4. Some
devices have higher outage probability and other devices have lower outage
probability, because the devices have different transmit powers. With an
exponential aging function, an increase in the average instantaneous AoI with
higher outage probability is more significant than a decrease in the average
instantaneous AoI with lower outage probability. Therefore, similar to Fig. 2,
there is a slight increase in the average instantaneous AoI when the devices
have different transmit powers. Even when the devices have different transmit
powers, the proposed SCA algorithm is still the most suitable algorithm to
achieve low average instantaneous AoI in a massive IoT with partial
information.

Figure 6: Average instantaneous AoI and service rate using distributed RB
allocation schemes while varying $p_{i,t}$.

Fig. 6 shows the average instantaneous AoI and the service rate of the devices
using distributed RB allocation schemes for different values of the SNR outage
probability $p_{i,t}$ with $r_{c}=10$ m, $v_{a}=1$, $N=R=50$, and varying
$\epsilon$ from $1$ to $5$. It is important to note that the number of active
devices $N_{t}$ is equal to $R$ with $N=R$ and $v_{a}=1$, and this is the
condition considered in Theorem 2. The service rate converges to $0.98$ for
SCA with $p_{i,t}=0.01$, $0.92$ for SCA with $p_{i,t}=0.03$, $0.88$ for SCA
with $p_{i,t}=0.05$, and $0.37$ for random RB allocation. As $p_{i,t}$
increases from $0.01$ to $0.05$, the average instantaneous AoI increases from
$1.25$ to $4.14$ using SCA, while the average instantaneous AoI increases from
$5.73$ to $7.64$ using random RB allocation. With high $p_{i,t}$, the proposed
SCA algorithm achieves about $45.8\%$ lower average instantaneous AoI when
compared to random RB allocation. Since $T_{t}=N$ with $v_{a}=1$ and $N=R$,
the theoretical value of $s_{r}$ (23) for random RB allocation case matches
the simulated value of $s_{r}$ in Fig. 6. As $p_{i,t}$ increases, the
converged value of $s_{r}$ for SCA decreases, because the proposed SCA assumes
that the transmission failures are caused by duplicate RB selection.
Therefore, using SCA, a device $i$ stochastically avoids to use an RB even
when there was no duplicate RB selection and the transmission failure is
caused by SNR outage. Furthermore, the difference between the average
instantaneous AoI using SCA and random RB allocation decreases as $p_{i,t}$
increases, because increasing $p_{i,t}$ has a more negative impact on SCA than
on random RB allocation. However, it is important to note that SCA with low
$p_{i,t}$ converges quickly to the service rate of $1$ with low $p_{i,t}$ as
discussed in Theorem 2.

Figure 7: Average instantaneous AoI and service rate using distributed Rb
allocation schemes while varying $r_{c}$.

Fig. 7 shows the average instantaneous AoI and the service rate of the devices
using distributed RB allocation schemes for different values of the
communication range $r_{c}$ with $p_{i,t}=0.01$, $\epsilon=1$, $v_{a}=1$, and
$N=R=50$. The communication range $r_{c}$ determines the amount of information
$\boldsymbol{A}_{i}$ that the devices have, and $r_{c}=15$ m implies that the
devices have full information $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for all
$i$. The service rate converges to $0.981$ for SCA with $r_{c}=15$ m, $0.978$
for SCA with $r_{c}=10$ m, $0.967$ for SCA with $r_{c}=5$ m, $0.939$ for SCA
with $r_{c}=1$ m, and $0.374$ for random RB allocation. As $r_{c}$ increases
from $2$ m to $15$ m, the average instantaneous AoI decreases from $2.62$ to
$1.21$ using SCA, while the average instantaneous AoI decreases from $7.19$ to
$5.07$ using random RB allocation. With low $r_{c}$, the proposed SCA
algorithm achieves about $63.6\%$ lower average instantaneous AoI when
compared to random RB allocation. Similar to the Fig. 6. the theoretical and
simulated values of $s_{r}$ for random RB allocation are matched. As $r_{c}$
increases, the convergence value of $s_{r}$ for SCA increases, because the
devices have more information $\boldsymbol{A}_{i}$ with higher $r_{c}$. As
$r_{c}$ increases sufficiently such that
$|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for all $i$, the service rate
converges to $1$ as discussed in Theorem 2. However, SCA with only partial
information can still achieve $s_{r}$ close to $1$. Moreover, as $r_{c}$
increases, the average instantaneous AoI using SCA converges to the average
instantaneous AoI using pre-determined RB allocation scheme.
Next, the proposed centralized and distributed RB allocation schemes are
compared in a massive IoT with $N>R$ and in an ideal IoT described in Theorem
2. To analyze different RB allocation schemes, the activation probability
$v_{a}$ and the SNR outage probability $p_{i,t}$ are varied,

Figure 8: Average instantaneous AoI using centralized and distributed RB
allocation schemes while varying $\beta$ in a massive IoT.

Fig. 8 shows the average instantaneous AoI of the devices using centralized
and distributed RB allocation schemes for different values of $\beta$ with
$p_{i,t}=0.01$, $\epsilon=1$, $r_{c}=10$ m, $N=100$, and $v_{a}=1$. This
simulates a massive IoT as the number of devices $N$ greatly outnumbers the
number of RBs $R$. For the centralized RB allocation scheme, as $\beta$
increases, the average instantaneous AoI with learning decreases from $3.6$ to
$3.13$, and the average instantaneous AoI with full information decreases from
$3.34$ to $3.05$. However, the average instantaneous AoI without learning does
not change significantly. With many type $2$ devices frequently transmitting
exponentially aging messages, high values of $\beta$ can effectively reduce
the average instantaneous AoI of type $2$ devices as BS learns the device
types. However, without learning the device types, high values of $\beta$ are
ineffective in reducing the average instantaneous AoI. For the distributed RB
allocation scheme, as $\beta$ increases, the average instantaneous AoI with
random selection decreases from $79.5$ to $25.1$, and the average
instantaneous AoI with proposed SCA decreases from $13.4$ to $5.1$. This is
because high values of $\beta$ enable the exponentially aging messages to be
transmitted before their AoI increases greatly due to duplicate RB selection.
However, the average instantaneous AoI with pre-determined selection does not
change significantly, because most duplicate RB selection can be avoided with
given $r_{c}$ and pre-determined selection. $\beta$ affects centralized and
distributed RB selection schemes differently depending on other parameters of
the IoT.

Figure 9: Average instantaneous AoI using centralized and distributed RB
allocation schemes while varying $v_{a}$ in a massive IoT.

Fig. 9 shows the average instantaneous AoI of the devices using centralized
and distributed RB allocation schemes for different values of the activation
probability $v_{a}$ with $p_{i,t}=0.01$, $\epsilon=1$, and $N=200$. This
simulates a massive IoT as the number of devices $N$ greatly outnumbers the
number of RBs $R$. As $v_{a}$ increases, the average instantaneous AoI
converges to $200$ for SCA with $r_{c}=5$ m, $157$ for SCA with $r_{c}=10$ m,
and $145$ for SCA with $r_{c}=15$ m. On the other hand, for priority
scheduling, the average instantaneous AoI increases from $1.14$ to $6.03$ as
$v_{a}$ increases from $0.1$ to $0.5$. With high $v_{a}$, the proposed SCA
algorithm with $r_{c}=15$ m achieves about $24$-fold higher average
instantaneous AoI when compared to the proposed priority scheduling with
learning. For almost any values of $v_{a}$, centralized RB allocation with
priority scheduling performs much better than distributed RB allocation with
SCA in terms of the average instantaneous AoI. However, centralized RB
allocation scheme requires the BS to dictate the RB allocation for all
devices, and, thus, centralized RB allocation scheme may not be viable for
some of the IoT. Moreover, similar to Fig. 1, the average instantaneous AoI
flattens after a certain value of $v_{a}$, because all RBs are fully
saturated. There is a performance gap between SCA with different values of
$r_{c}$, because $r_{c}$ is directly related to the amount of information that
the devices have. With higher $r_{c}$ and more information for the devices,
SCA is more effective in reducing the average instantaneous AoI.

Figure 10: Average instantaneous AoI using centralized and distributed RB
allocation schemes while varying $p_{i,t}$ in a massive IoT.

Fig. 10 shows the average instantaneous AoI of the devices using centralized
and distributed RB allocation schemes for different values of the SNR outage
probability $p_{i,t}$ with $v_{a}=0.5$, $N=200$, and varying $\epsilon$ from
$1$ to $20$. Similar to Fig. 9, this simulates a massive IoT. When
$p_{i,t}=0.18$. the average instantaneous AoI is $585.59$ using SCA with
$r_{c}=5$ m, $529.94$ using SCA with $r_{c}=10$ m, $472.81$ using SCA with
$r_{c}=15$ m, and $11.90$ using priority scheduling. With high $p_{i,t}$, the
proposed SCA algorithm with $r_{c}=15$ m achieves about $40$-fold higher
average instantaneous AoI when compared to the proposed priority scheduling
with learning. Similar to Fig. 9, centralized RB allocation with priority
scheduling performs much better than distributed RB allocation with SCA in
terms of the average instantaneous AoI for all values of $p_{i,t}$. It is
interesting to note that the difference in the average instantaneous AoI
between SCA algorithms increases as $p_{i,t}$ increases. This implies that SCA
with less information is more severely affected by increasing $p_{i,t}$ than
SCA with more information.

Figure 11: Average instantaneous AoI using centralized and distributed RB
allocation schemes while varying $p_{i,t}$ in an ideal IoT.

Fig. 11 shows the average instantaneous AoI of the devices using centralized
and distributed RB allocation schemes for different values of the SNR outage
probability $p_{i,t}$ with $v_{a}=1$, $N=R=50$, and varying $\epsilon$ from
$1$ to $20$. This simulates an ideal IoT for SCA as some of the conditions for
NE convergence in Theorem 2 are satisfied. When $p_{i,t}=0.18$. the average
instantaneous AoI is $25.53$ using SCA with $r_{c}=5$ m, $19.96$ using SCA
with $r_{c}=10$ m, $17.27$ using SCA with $r_{c}=15$ m, and $2.21$ using
priority scheduling. With high $p_{i,t}$, the proposed SCA algorithm with
$r_{c}=15$ m achieves about $8$-fold higher average instantaneous AoI when
compared to the proposed priority scheduling with learning. It is interesting
to note that even in an ideal IoT for SCA, priority scheduling with learning
performs better than SCA in terms of the average instantaneous AoI for most
values of $p_{i,t}$. Moreover, similar to Fig. 10, the difference in the
average instantaneous AoI between SCA algorithms increases as $p_{i,t}$
increases.
From our simulations, we observe that both priority scheduling and SCA are
susceptible to high SNR outage probability $p_{i,t}$ as the average
instantaneous AoI increases without flattening as $p_{i,t}$ increases. This is
because the SNR outage probability is directly related to the transmission
failures. However, the average instantaneous AoI increases slowly after a
certain value of the activation probability $v_{a}$, because the RBs are fully
saturated. Since increasing $v_{a}$ with fixed $N$ is equivalent to increasing
$N$ with fixed $v_{a}$, the average instantaneous AoI also flattens for the
case in which only the number of devices $N$ increases. Although centralized
RB allocation scheme outperforms distributed RB allocation scheme in most
cases, SCA can still achieve a high service rate $s_{r}$ and low average
instantaneous AoI only with partial information. Furthermore, communication
range $r_{c}$ and information availability are critical to the performance of
SCA.

##  VI Conclusion

In this paper, we have proposed centralized and distributed approaches for
allocating the limited communication resources based on the aging function and
the current AoI of IoT devices. In the presence of both linear and exponential
aging functions, we have shown that comparing the future AoI achieves a lower
average instantaneous AoI at the BS than comparing the current AoI. For the
centralized approach, we have introduced a priority scheduling scheme with
learning, which enables the BS to allocate the limited RBs to the
heterogeneous devices based on their future AoI. For the distributed approach,
we have formulated the problem of autonomously allocating the limited RBs to
the devices using game theory, and we have designed payoff functions to
encourage the devices with high AoI to transmit, while discouraging the
devices with low AoI to not transmit. Furthermore, we have proposed a novel
SCA algorithm such that the heterogeneous devices can allocate the RBs in a
self-organizing manner to avoid the duplicate RB selection and to minimize the
AoI. We have proved the conditions that a vector of actions in the IoT game
must satisfy to achieve an NE. Furthermore, we have proved that the actions of
devices using our proposed SCA algorithm converge to an NE, if the devices
have sufficient information under certain network parameters. Simulation
results have shown that the average instantaneous AoI is an increasing
function of the activation probability and the SNR outage probability.
Moreover, the simulation results have shown that the service rate is an
increasing function of the communication range and a decreasing function of
the activation probability and the SNR outage probability. We have compared
our centralized and distributed RB allocation schemes, and we have shown that
our centralized RB allocation scheme outperforms our distributed RB allocation
scheme in most cases. However, our proposed SCA algorithm has shown to be
effective in reducing the AoI and increasing the service rate only with
partial information. With high SNR outage probability, the proposed priority
scheduling scheme with learning has shown to achieve about $31.7\%$ lower
average instantaneous AoI when compared to simple priority scheduling scheme.
Furthermore, with high SNR outage probability, the proposed SCA algorithm has
shown to achieve about $45.8\%$ lower average instantaneous AoI when compared
to random RB allocation.

## Acknowledgment

This research was supported by the U.S. Office of Naval Research (ONR) under
Grant N00014-19-1-2621.

###  -A Proof of Proposition 1

Without a loss of generality, let there be an IoT device $i$ with aging
function $a_{i}(t)$ and an IoT device $h$ with aging function $b_{h}(t)$.
Moreover, the proof only considers the case with $N=2$ and $R=1$. It is
sufficient to only consider $N=2$, because comparing the AoI of $N>2$ devices
is equivalent to doing pairwise AoI comparison $\nicefrac{{N(N-1)}}{{2}}$
times. It is unnecessary to consider the cases of $R=0$ and $R\geq 2$. If
$N=2$ and $R=0$, none of the devices can be allocated an RB. If $N=2$ and
$R\geq 2$, all devices can be allocated the RBs. Therefore, the AoI comparison
to determine RB allocation is unnecessary.
At time slot $\tau$, the current AoI of devices $i$ and $h$ must be one of the
following cases: $a_{i}(\tau)>b_{h}(\tau)$, $a_{i}(\tau)=b_{h}(\tau)$, or
$a_{i}(\tau)<b_{h}(\tau)$. If $a_{i}(\tau)\leq b_{h}(\tau)$, then
$a_{i}(\tau+\beta)\leq b_{h}(\tau+\beta)$ for any positive integer $\beta$. At
time slot $\tau$, the current AoI comparison with $t=\tau$ and the future AoI
comparison with $t=\tau+\beta$ are equivalent, because device $h$ is allocated
with an RB for both. However, if $a_{i}(\tau)>b_{h}(\tau)$, the future AoI of
devices $i$ and $h$ can be any of the following cases:
$a_{i}(\tau+\beta)>b_{h}(\tau+\beta)$, $a_{i}(\tau+\beta)=b_{h}(\tau+\beta)$,
or $a_{i}(\tau+\beta)<b_{h}(\tau+\beta)$. For the case of
$a_{i}(\tau)>b_{h}(\tau)$ and $a_{i}(\tau+\beta)\geq b_{h}(\tau+\beta)$, the
current AoI comparison with $t=\tau$ and the future AoI comparison with
$t=\tau+\beta$ are equivalent, because device $i$ is allocated with an RB for
both.
Comparing the current AoI and the future AoI are different if
$a_{i}(\tau)>b_{h}(\tau)$ and $a_{i}(\tau+\beta)<b_{h}(\tau+\beta)$, because
comparing the current AoI allocates the RB to device $i$, while comparing the
future AoI allocates the RB to device $h$. When one device is allocated an RB
at time slot $\tau$ and the other device is allocated an RB at time slot
$\tau+\beta$, the RB allocation based on current AoI achieves the average
instantaneous AoI of $0.5(a_{i}(\tau)+2^{\beta}b_{h}(\tau))$, and the RB
allocation based on future AoI achieves the average instantaneous AoI of
$0.5(a_{i}(\tau)+\beta+b_{h}(\tau))$. For any $\beta\in\mathbb{Z}_{+}$,
comparing the average instantaneous AoI of two cases is:

$\displaystyle\frac{a_{i}(\tau)+2^{\beta}b_{h}(\tau)}{2}$
$\displaystyle>\frac{a_{i}(\tau)+\beta+b_{h}(\tau)}{2},$ (25)
$\displaystyle(2^{\beta}-1)b_{h}(\tau)$ $\displaystyle>\beta,$ (26)
$\displaystyle b_{h}(\tau)$ $\displaystyle>\frac{\beta}{2^{\beta}-1}.$ (27)

Even when one device is allocated with an RB at time slot $\tau$ and the other
device is allocated with an RB one time slot later at time slot $\tau+1$, the
current AoI comparison yields higher average instantaneous AoI than the future
AoI comparison. Since $\frac{\beta}{2^{\beta}-1}=1$ with $\beta=1$,
$b_{h}(\tau)$ cannot be less than or equal to 1, because the condition of
$a_{i}(\tau)>b_{h}(\tau)$ and $a_{i}(\tau+1)<b_{h}(\tau+1)$ cannot be
satisfied. Therefore, at time slot $\tau$, comparing the future AoI with
$t=\tau+\beta$ to determine the RB allocation achieves lower average
instantaneous AoI than comparing the current AoI with $t=\tau$.

###  -B Proof of Theorem 1

With $\boldsymbol{x}(t)$ satisfying the given conditions, then at most $R$
active devices with sufficiently high values of $F_{i}$ are transmitting
successfully, while rest of the devices are not transmitting. Assuming that
all other devices do not change their action, an active device $i$ that is
transmitting successfully with sufficiently high $F_{i}$ cannot change its
action $x_{i}(t)$ to get higher payoff than its current payoff of $\rho$. If
device $i$ uses some other RB, then its transmission may fail due to the
duplicate RB usages, getting the payoff of $-\gamma$, or its transmission may
succeed, getting the same payoff of $\rho$. If device $i$ does not transmit,
then the payoff is $-(\gamma+\eta)$ as $F_{i}$ is greater than
$\boldsymbol{A}_{i}(R)$. Therefore, the active devices that are transmitting
successfully with sufficiently high $F_{i}$ do not change their action.
The devices that are not transmitting may be active or inactive. An inactive
device that is not transmitting has a payoff of $(\rho+\eta)$, which is higher
than the payoff of transmitting successfully. Therefore, the inactive devices
do not transmit. With $\boldsymbol{x}(t)$ satisfying the given conditions,
then active devices with $F_{i}<\boldsymbol{A}_{i}(R)$ are not transmitting.
With $y_{i}(\boldsymbol{x}(t))$, the active devices with
$F_{i}<\boldsymbol{A}_{i}(R)$ have the payoff of $(\rho+\eta)$, which is
higher than the payoff of transmitting successfully. Therefore, the active
devices with $F_{i}<\boldsymbol{A}_{i}(R)$ do not change their action from not
transmitting.
With the design of payoff function $y_{i}(\boldsymbol{x}(t))$ (22), inactive
devices and active devices with $F_{i}<\boldsymbol{A}_{i}(R)$ have the highest
payoff of $(\rho+\eta)$ by not transmitting. Moreover, with
$|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$, at most $R$ active devices with
$F_{i}\geq\boldsymbol{A}_{i}(R)$ have higher payoff from transmitting
successfully than from not transmitting. With $\boldsymbol{x}(t)$ such that
each of the RBs is used by at most one device, the active devices with
$F_{i}\geq\boldsymbol{A}_{i}(R)$ have the highest payoff of $\rho$ by
transmitting successfully. Therefore, with $y_{i}(\boldsymbol{x}(t))$, any
vector of actions $\boldsymbol{(}x)(t)$ such that at most $R$ active devices
with $F_{i}\geq\boldsymbol{A}_{i}(R)$ transmit, rest of the devices do not
transmit, and each of the RBs is used by at most one device is an NE.

###  -C Proof of Theorem 2

At time slot $t=1$, $\boldsymbol{x}(t)$ is initialized as a random RB
selection. For $N=R$ and $v_{a}=1$, $T_{t}=N$ and the service rate $s_{r}$ is
$\left(\nicefrac{{(R-1)}}{{R}}\right)^{N-1}$. Therefore, from the initial RB
allocation, the expected number of RBs that are used by one device is
$Rs_{r}$. With SCA and $v_{a}=1$, an RB that is used by one device at time
slot $t=1$ is used by the same device at time slot $t=2$. Furthermore, with
SCA, the RBs that are used by more than one device at the time slot $t=1$ are
expected to be used by one device at the time slot $t=2$. Therefore, at time
slot $t=2$,
$\mathbb{E}[|\mathcal{L}|]=R\left(\nicefrac{{(R-1)}}{{R}}\right)^{N}$, which
is the expected number of RBs that are used by none of the devices at time
slot $t=1$. $\mathbb{E}[|\mathcal{L}|]$ also is the expected number of devices
that are competing to use the RBs in $\mathcal{L}$, because the devices use at
most $1$ RB at each time slot. Since the devices choose the RBs in
$\mathcal{L}$ randomly, the RB selection at time slot $t=2$ is equivalent to
the random RB selection with the number of devices and RBs equal to
$R\left(\nicefrac{{(R-1)}}{{R}}\right)^{N}$. Moreover, the same analysis done
for $t=1$ can be done with $t=2$.
Expanding to the general case, at time slot $t$, the expected number of RBs
that are used by none of the devices and the expected number of devices
competing to use the RBs in $\mathcal{L}$ is
$R\left(\nicefrac{{(R-1)}}{{R}}\right)^{N(t-1)}$. As $t$ increases to
infinity, the expected number of RBs that are used by none of the devices and
the expected number of devices competing to use the RBs in $\mathcal{L}$
decrease to $0$. With SCA, this implies that the number of RBs each used by
one device increases to $R$ as $t$ increases to infinity. Furthermore, with
$N=R$ and $|\boldsymbol{A}_{i}|=|\boldsymbol{A}|$ for all $i$, any active
device $i$ satisfies $F_{i}\geq\boldsymbol{A}_{i}(R)$. The action space
$\boldsymbol{x}(t)$ converged using SCA is such that all $R$ active devices
transmit and each of the RBs is used by one device. Therefore,
$\boldsymbol{x}(t)$ converged using SCA is an NE.

###  -D Proof of Proposition 2

When the $T_{t}$ transmitting devices use random RB selection, the service
rate is equivalent to the probability of an RB being used by only one
transmitting device. Therefore, the service rate $s_{r}$ is:

$s_{r}=\binom{T_{t}}{1}\frac{1}{R}\left(1-\frac{1}{R}\right)^{T_{t}-1}=\frac{T_{t}}{R}\left(\frac{R-1}{R}\right)^{T_{t}-1}.$
(28)

When the number of IoT devices $N$ increases to infinity in a massive IoT, the
number of transmitting devices $T_{t}$ also increases to infinity with fixed
$v_{a}$, and the service rate $s_{r}$ is:

$\displaystyle\lim_{T_{t}\rightarrow\infty}s_{r}=\lim_{T_{t}\rightarrow\infty}\frac{T_{t}}{R}\left(1+\frac{\nicefrac{{-T_{t}}}{{R}}}{T_{t}}\right)^{T_{t}-1},$
(29) $\displaystyle\ \ \
=\lim_{T_{t}\rightarrow\infty}\frac{T_{t}}{R-1}\left(1+\frac{\nicefrac{{-T_{t}}}{{R}}}{T_{t}}\right)^{T_{t}}=\frac{T_{t}}{R-1}\exp\left(\frac{-T_{t}}{R}\right).$
(30)

## References

  * [1] W. Saad, M. Bennis, and M. Chen, “A vision of 6G wireless systems: Applications, trends, technologies, and open research problems,” _IEEE Network_ , pp. 1–9, Oct. 2019.
  * [2] L. D. Xu, W. He, and S. Li, “Internet of things in industries: A survey,” _IEEE Transactions on Industrial Informatics_ , vol. 10, no. 4, pp. 2233–2243, Nov. 2014.
  * [3] M. Hassanalieragh, A. Page, T. Soyata, G. Sharma, M. Aktas, G. Mateos, B. Kantarci, and S. Andreescu, “Health monitoring and management using internet of things (IoT) sensing with cloud-based processing: Opportunities and challenges,” in _Proc of IEEE International Conference on Services Computing_ , New York, USA, Jun. 2015, pp. 285–292.
  * [4] M. Mozaffari, A. T. Z. Kasgari, W. Saad, M. Bennis, and M. Debbah, “Beyond 5G with UAVs: Foundations of a 3D wireless cellular network,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 1, pp. 357–372, Jan. 2019.
  * [5] M. Chen, W. Saad, and C. Yin, “Echo-liquid state deep learning for $360^{\circ}$ content transmission and caching in wireless VR networks with cellular-connected UAVs,” _IEEE Transactions on Communications_ , vol. 67, no. 9, pp. 6386–6400, Sep. 2019.
  * [6] Y. Zhang, M. Chen, N. Guizani, D. Wu, and V. C. M. Leung, “SOVCAN: Safety-oriented vehicular controller area network,” _IEEE Communications Magazine_ , vol. 55, no. 8, pp. 94–99, Aug. 2017.
  * [7] Z. Dawy, W. Saad, A. Ghosh, J. G. Andrews, and E. Yaacoub, “Toward massive machine type cellular communications,” _IEEE Wireless Communications_ , vol. 24, no. 1, pp. 120–128, Feb. 2017.
  * [8] S. F. Abedin, M. G. R. Alam, S. M. A. Kazmi, N. H. Tran, D. Niyato, and C. S. Hong, “Resource allocation for ultra-reliable and enhanced mobile broadband IoT applications in fog network,” _IEEE Transactions on Communications_ , vol. 67, no. 1, pp. 489–502, Jan. 2019.
  * [9] T. Park and W. Saad, “Distributed learning for low latency machine type communication in a massive internet of things,” _IEEE Internet of Things Journal_ , vol. 6, no. 3, pp. 5562–5576, Jun. 2019.
  * [10] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _Proc. of IEEE International Conference on Computer Communications_ , Florida, USA, Mar. 2012, pp. 2731–2735.
  * [11] B. Zhou and W. Saad, “Joint status sampling and updating for minimizing age of information in the internet of things,” _IEEE Transactions on Communications_ , vol. 67, no. 11, pp. 7468–7482, Nov. 2019.
  * [12] 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, Dec. 2018.
  * [13] I. Kadota, A. Sinha, and E. Modiano, “Scheduling algorithms for optimizing age of information in wireless networks with throughput constraints,” _IEEE/ACM Transactions on Networking_ , vol. 27, no. 4, pp. 1359–1372, Aug. 2019.
  * [14] R. Talak, S. Karaman, and E. Modiano, “Minimizing age-of-information in multi-hop wireless networks,” in _Proc. of 55th Annual Allerton Conference on Communication, Control, and Computing_ , Illinois, USA, Oct. 2017, pp. 486–493.
  * [15] S. Leng and A. Yener, “Age of information minimization for wireless ad hoc networks: A deep reinforcement learning approach,” in _Proc. of IEEE Global Communications Conference_ , Hawaii, USA, Dec. 2019, pp. 1–6.
  * [16] R. D. Yates and S. K. Kaul, “Status updates over unreliable multiaccess channels,” in _Proc. of International Symposium on Information Theory_ , Aachen, Germany, Jun. 2017, pp. 331–335.
  * [17] R. Talak, I. Kadota, S. Karaman, and E. Modiano, “Scheduling policies for age minimization in wireless networks with unknown channel state,” in _Proc. of IEEE International Symposium on Information Theory_ , Colorado, USA, Jun. 2018, pp. 2564–2568.
  * [18] R. Talak, S. Karaman, and E. Modiano, “Optimizing age of information in wireless networks with perfect channel state information,” in _Proc. of 16th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks_ , Shanghai, China, May 2018, pp. 1–8.
  * [19] B. Zhou and W. Saad, “Minimum age of information in the internet of things with non-uniform status packet sizes,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 3, pp. 1933–1947, Mar. 2020.
  * [20] R. Talak, S. Karaman, and E. Modiano, “Distributed scheduling algorithms for optimizing information freshness in wireless networks,” in _Proc. of IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications_ , Kalamata, Greece, Jun. 2018, pp. 1–5.
  * [21] Y. Sun, E. Uysal-Biyikoglu, and S. Kompella, “Age-optimal updates of multiple information flows,” in _Proc. of IEEE Conference on Computer Communications Workshops_ , Hawaii, USA, Apr. 2018, pp. 136–141.
  * [22] R. D. Yates and S. K. Kaul, “The age of information: Real-time status updating by multiple sources,” _IEEE Transactions on Information Theory_ , vol. 65, no. 3, pp. 1807–1827, Mar. 2019.
  * [23] S. Gopal and S. K. Kaul, “A game theoretic approach to DSRC and WiFi coexistence,” in _Proc. of International Conference on Computer Communications Workshops_ , Hawaii, USA, Apr. 2018, pp. 565–570.
  * [24] A. Maatouk, M. Assaad, and A. Ephremides, “On the age of information in a CSMA environment,” _IEEE/ACM Transactions on Networking_ , vol. 28, no. 2, pp. 818–831, Apr. 2020.
  * [25] A. M. Bedewy, Y. Sun, R. Singh, and N. B. Shroff, “Optimizing information freshness using low-power status updates via sleep-wake scheduling,” _arXiv preprint arXiv:1910.00205_ , 2019.
  * [26] L. Huang and E. Modiano, “Optimizing age-of-information in a multi-class queueing system,” in _Proc. of IEEE International Symposium on Information Theory_ , Hong Kong, China, Jun. 2015, pp. 1681–1685.
  * [27] 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, Apr. 2016.
  * [28] Y. Inoue, H. Masuyama, T. Takine, and T. Tanaka, “The stationary distribution of the age of information in FCFS single-server queues,” in _Proc. of IEEE International Symposium on Information Theory_ , Aachen, Germany, Jun. 2017, pp. 571–575.
  * [29] E. Najm, R. Yates, and E. Soljanin, “Status updates through m/g/1/1 queues with harq,” in _Proc. of IEEE International Symposium on Information Theory_ , Aachen, Germany, Jun. 2017, pp. 131–135.
  * [30] M. K. Abdel-Aziz, C. Liu, S. Samarakoon, M. Bennis, and W. Saad, “Ultra-reliable low-latency vehicular networks: Taming the age of information tail,” in _Proc. of IEEE Global Communications Conference_ , Abu Dhabi, UAE, Dec. 2018, pp. 1–7.
  * [31] K. Chen and L. Huang, “Age-of-information in the presence of error,” in _Proc. of IEEE International Symposium on Information Theory_ , Barcelona, Spain, Jul. 2016, pp. 2579–2583.
  * [32] A. Maatouk, M. Assaad, and A. Ephremides, “Minimizing the age of information: NOMA or OMA?” in _Proc. of IEEE Conference on Computer Communications Workshops_ , Paris, France, Apr. 2019, pp. 102–108.
  * [33] Y. Sun and B. Cyr, “Sampling for data freshness optimization: Non-linear age functions,” _Journal of Communications and Networks_ , vol. 21, no. 3, pp. 204–219, Jun. 2019.
  * [34] T. Park, W. Saad, and B. Zhou, “On the minimization of non-linear age of information in the internet of things,” _submitted to Proc. of IEEE International Conference on Communications_ , pp. 1–6, Jun. 2021.
  * [35] A. Even and G. Shankaranarayanan, “Utility-driven assessment of data quality,” _SIGMIS Database_ , vol. 38, no. 2, p. 75–93, May 2007.
  * [36] S. Ioannidis, A. Chaintreau, and L. Massoulie, “Optimal and scalable distribution of content updates over a mobile social network,” in _Proc. of IEEE International Conference on Computer Communications_ , Rio de Janeiro, Brazil, Apr. 2009, pp. 1422–1430.
  * [37] A. S. Chakrabarti, C. B. K, A. Chatterjee, and M. Mitra, “The Kolkata Paise Restaurant Problem and Resource Utilization,” _Physica A: Statistical Mechanics and its Applications_ , vol. 388, no. 12, pp. 2420–2426, Jun. 2009.
  * [38] 3GPP, “Evolved universal terrestrial radio access (E-UTRA) and evolved universal terrestrial radio access network (E-UTRAN) (release 15),” TS 36.300 v15.8.0, Jan. 2020.
  * [39] X. Liu, Z. Qin, Y. Gao, and J. A. McCann, “Resource allocation in wireless powered iot networks,” _IEEE Internet of Things Journal_ , vol. 6, no. 3, pp. 4935–4945, Jun. 2019.
  * [40] G. Hattab and D. Cabric, “Energy-efficient massive iot shared spectrum access over uav-enabled cellular networks,” _IEEE Transactions on Communications_ , vol. 68, no. 9, pp. 5633–5648, Sep. 2020.
  * [41] Q. Abbas, S. Zeb, S. A. Hassan, R. Mumtaz, and S. A. R. Zaidi, “Joint optimization of age of information and energy efficiency in iot networks,” in _Proc. of IEEE Vehicular Technology Conference_ , Antwerp, Belgium, May 2020, pp. 1–5.
  * [42] 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, Nov. 2017\.
  * [43] R. D. Yates, E. Najm, E. Soljanin, and J. Zhong, “Timely updates over an erasure channel,” in _Proc. of IEEE International Symposium on Information Theory_ , Aachen, Germany, Jun. 2017, pp. 316–320.
  * [44] A. Mazin, M. Elkourdi, and R. D. Gitlin, “Comparison of slotted aloha-NOMA and CSMA/CA for M2M communications in iot networks,” in _Proc. of IEEE Vehicular Technology Conference_ , Illinois, USA, Aug. 2018, pp. 1–5.
  * [45] A. Sivanathan, D. Sherratt, H. H. Gharakheili, A. Radford, C. Wijenayake, A. Vishwanath, and V. Sivaraman, “Characterizing and classifying iot traffic in smart cities and campuses,” in _Proc. of International Conference on Computer Communications Workshops_ , Georgia, USA, May 2017, pp. 559–564.
  * [46] W. Ejaz, M. Naeem, A. Shahid, A. Anpalagan, and M. Jo, “Efficient energy management for the internet of things in smart cities,” _IEEE Communications Magazine_ , vol. 55, no. 1, pp. 84–91, Jan. 2017.
  * [47] T. Park and W. Saad, “Kolkata paise restaurant game for resource allocation in the internet of things,” in _Proc. of Asilomar Conference on Signals, Systems, and Computers_ , California, USA, Nov. 2017, pp. 1774–1778.
  * [48] O. Bello and S. Zeadally, “Intelligent device-to-device communication in the internet of things,” _IEEE Systems Journal_ , vol. 10, no. 3, pp. 1172–1182, Sep. 2016.
  * [49] J. Lianghai, B. Han, M. Liu, and H. D. Schotten, “Applying device-to-device communication to enhance IoT services,” _IEEE Communications Standards Magazine_ , vol. 1, no. 2, pp. 85–91, Jul. 2017.
  * [50] T. Zhang, H. Fan, J. Loo, and D. Liu, “User preference aware caching deployment for device-to-device caching networks,” _IEEE Systems Journal_ , vol. 13, no. 1, pp. 226–237, Mar. 2019.
  * [51] I. O. Sanusi, K. M. Nasr, and K. Moessner, “A device to device (D2D) spectrum sharing scheme for wireless industrial applications,” in _European Conference on Networks and Communications_ , Valencia, Spain, Jun. 2019, pp. 353–357.
  * [52] J. Li, G. Lei, G. Manogaran, G. Mastorakis, and C. X. Mavromoustakis, “D2d communication mode selection and resource optimization algorithm with optimal throughput in 5g network,” _IEEE Access_ , vol. 7, pp. 25 263–25 273, Feb. 2019.
  * [53] S. Gopal, S. K. Kaul, R. Chaturvedi, and S. Roy, “A non-cooperative multiple access game for timely updates,” _arXiv preprint arXiv:2001.08850_ , 2020.
  * [54] K. L. V. S. P. Sakuru and M. Visali, “Power control based resource allocation in LTE uplinks,” in _Proc. of International Conference on Communications and Signal Processing_ , Melmaruvathur, India, Apr. 2015, pp. 579–582.
  * [55] G. Hampel, C. Li, and J. Li, “5G ultra-reliable low-latency communications in factory automation leveraging licensed and unlicensed bands,” _IEEE Communications Magazine_ , vol. 57, no. 5, pp. 117–123, May 2019.
  * [56] M. Ali, E. Hossain, and D. Kim, “LTE/LTE-A random access for massive machine-type communications in smart cities,” _IEEE Communications Magazine_ , vol. 55, no. 1, pp. 76–83, Jan. 2017.