# Deep Reinforcement Learning Based Power Allocation for Minimizing AoI and
Energy Consumption in MIMO-NOMA IoT Systems

Hongbiao Zhu, Qiong Wu, , Qiang Fan, Pingyi Fan, ,
Jiangzhou Wang, and Zhengquan Li  This work was supported in part by the
National Natural Science Foundation of China under Grant No. 61701197, in part
by the open research fund of State Key Laboratory of Interatory Services
Networks under Grant No. ISN23-11, in part by the 111 project under Grant No.
B12018, in part by the Future Network Scientific Research Fund Project
(FNSRFP-2021-YB-11). Hongbiao Zhu and Qiong Wu are with the School of Internet
of Things Engineering, Jiangnan University, Wuxi 214122, China, and also with
the State Key Laboratory of Integrated Services Networks (Xidian University),
Xi’an 710071, China (e-mail<EMAIL_ADDRESS>qiongwu@jiangnan.edu.cn). Qiang Fan is with Qualcomm, San Jose, CA 95110, USA
(e-mail: qf9898@gmail.com). Pingyi Fan is with the Department of Electronic
Engineering, Beijing National Research Center for Information Science and
Technology, Tsinghua University, Beijing 100084, China (Email:
fpy@tsinghua.edu.cn). Jiangzhou Wang is with the School of Engineering,
University of Kent, CT2 7NT Canterbury, U.K. (Email: j.z.wang@kent.ac.uk).
Zhengquan Li is with the School of Internet of Things Engineering, Jiangnan
University, Wuxi 214122, China, and also with Jiangsu Future Networks
Innovation Institute, Nanjing 211111, China (Email: lzq722@jiangnan.edu.cn).

###### Abstract

Multi-input multi-out and non-orthogonal multiple access (MIMO-NOMA) internet-
of-things (IoT) systems can improve channel capacity and spectrum efficiency
distinctly to support the real-time applications. Age of information (AoI) is
an important metric for real-time application, but there is no literature have
minimized AoI of the MIMO-NOMA IoT system, which motivates us to conduct this
work. In MIMO-NOMA IoT system, the base station (BS) determines the sample
collection requirements and allocates the transmission power for each IoT
device. Each device determines whether to sample data according to the sample
collection requirements and adopts the allocated power to transmit the sampled
data to the BS over MIMO-NOMA channel. Afterwards, the BS employs successive
interference cancelation (SIC) technique to decode the signal of the data
transmitted by each device. The sample collection requirements and power
allocation would affect AoI and energy consumption of the system. It is
critical to determine the optimal policy including sample collection
requirements and power allocation to minimize the AoI and energy consumption
of MIMO-NOMA IoT system, where the transmission rate is not a constant in the
SIC process and the noise is stochastic in the MIMO-NOMA channel. In this
paper, we propose the optimal power allocation to minimize the AoI and energy
consumption of MIMO-NOMA IoT system based on deep reinforcement learning
(DRL). Extensive simulations are carried out to demonstrate the superiority of
the optimal power allocation.

###### Index Terms:

deep reinforcement learning, age of information, MIMO-NOMA, internet of things

##  I Introduction

With the development of Internet-of-Things (IoT)[1, 2, 3], the base station
(BS) can support the real-time applications such as disaster management,
information recommendation, vehicle network, smart city, connected health and
industrial internet through collecting the data sampled by IoT devices[4, 5,
6, 7, 8]. However, the amount of sampled data is enormous and the number of
IoT devices is usually numerous, thus the realization of these IoT
applications need large bandwidth and spectrum access. The multi-input multi-
out and non-orthogonal multiple access (MIMO-NOMA) IoT can transmit data
through the MIMO-NOMA channel to solve these problems, where multiple antennas
are deployed at the BS to improve the channel capacity and multiple IoT
devices access the common bandwidth simultaneously to improve the spectrum
efficiency[9, 10].

The BS collects data during discrete slots in the MIMO-NOMA IoT system. In
each slot, a BS first determines the sample collection requirements and
allocates the transmission power for each IoT device and then sends the
corresponding sample collection requirements and transmission power to each
IoT device. Afterwards, each IoT device determines whether to sample data from
physical world according to its sample collection requirements. Then each IoT
device would adopt its allocated power to transmit the sampled data to the BS
over the MIMO-NOMA channel. In the transmission process, multiple IoT devices
transmit the signals of data by using a common bandwidth and thus a signal of
an IoT device will be interfered by the signals of other devices. To eliminate
the interference, the BS adopts the successive interference cancelation (SIC)
technique to decode the received signal transmitted by each device[11].
Specifically, the BS sorts the power of all received signals in descending
order and decodes the signal with the highest received power by considering
other signals as interferences. Then the BS removes the decoded signal from
the received signals and resorts the received signals to decode the next
signal. The process is repeated until all signals are decoded.

The age of information (AoI) is a metric to measure the freshness of data,
which is defined as the time from the data sampling to the time when the
sampled data are received. In the MIMO-NOMA IoT system, the BS needs to
receive data, i.e., decode the signals of data, timely after they are sampled
to provide the real-time applications, thus the MIMO-NOMA IoT system should
keep low AoI [12][13]. Furthermore, the IoT devices are energy-limited, thus
the MIMO-NOMA IoT system should also keep low energy consumption to prolong
the working time of IoT devices[9]. Hence, the AoI and energy consumption are
two important performance metrics of the MIMO-NOMA IoT system. The sample
collection requirements and power allocation would affect the AoI and energy
consumption of the system[14]. Specifically, for the sample collection
requirements, if the BS selects more IoT devices to sample, the system will
consume more energy because more IoT devices consume energy to sample data.
However, if the BS selects less IoT devices to sample, the data transmitted
from the unselected IoT devices become obsolete, which would increase the AoI
of the system. Hence the sample collection requirements affects both AoI and
energy consumption of the MIMO-NOMA IoT system. For the power allocation, if
an IoT device transmits with high power, the signal transmitted by the IoT
device will be decoded where lots of signals with lower power act the
interferences in the SIC process, which would lead to a low signal-to-
interference-plus-noise ratio (SINR). Otherwise, if an IoT device transmits
data with low power, the SINR would also be deteriorated due to the low
transmission power. The low SINR causes a low transmission rate, which would
cause a long transmission delay and a high AoI of the MIMO-NOMA IoT system.
Hence the power allocation affects the AoI of the MIMO-NOMA IoT system.
Moreover, the power allocation affects the energy consumption directly. Thus,
the transmission power affects both the AoI and energy consumption of the
MIMO-NOMA IoT system. As mentioned above, it is critical to determine the
optimal policy including sample collection requirements and power allocation
to minimize the AoI and energy consumption of the MIMO-NOMA IoT system. To the
best of our knowledge, there is no work to minimize the AoI in the MIMO-NOMA
IoT system, which motivates us to conduct this work.

In the MIMO-NOMA IoT system, the different allocated transmission powers will
impact transmission rate in the SIC process. Moreover, there is the inevitable
stochastic noise in the MIMO-NOMA channel. Deep reinforcement learning (DRL)
can learn the near optimal policy through considering the sample collection
requirements and power allocation as action to interact with the dynamic
stochastic MIMO-NOMA IoT system[15]. In general, the DRL algorithm is suitable
to solve the problem with the continuous or discrete action space exclusively.
However, the space of the sample collection requirements is discrete while the
space of the transmission power is continuous, which poses a challenge to the
problem by DRL. In this paper, we present the relationship between the sample
collection requirements and transmission power, and propose a DRL based
optimal power allocation to minimize the AoI and energy consumption of the
MIMO-NOMA IoT system. 111The source code has been released at:
https://github.com/qiongwu86/MIMO-NOMA_AoI_GA.gitThe main contributions are
summarized as follows.

  * 1)

We formulate the joint optimization problem to minimize the AoI and energy
consumption of the MIMO-NOMA IoT system by determining the sample selection
and power allocation.

  * 2)

In the formulated optimization problem, the sample selection is discrete and
power allocation is continuous, which can not be solve by traditional DRL
method. We substitute energy model and AoI model into optimization problem,
merge the homogeneous terms containing sample selection, and simplify the
formulated problem to make it suitable to be solved by deep deterministic
policy gradient (DDPG).

  * 3)

We design the DRL framework including the state, action and reward function,
then adopt the DDPG algorithm to obtain the optimal power allocation to
minimize the AoI and energy consumption of the MIMO-NOMA IoT system.

  * 4)

Extensive simulations are carried out to demonstrate the superiority of the
optimal power allocation by the DDPG algorithm to the power allocation by the
baseline algorithm.

The rest of this paper is organized as follows. Section II reviews the related
work. Section III introduces the system model and formulates the optimization
problem. Section IV simplifies the formulated optimization problem and
presents the near optimal solution by DRL. We carry out some simulation to
demonstrate the effectiveness of our proposed DRL method in Section VI, and
conclude this paper in Section VII.

##  II Related Work

In this section, we first review the studies about the AoI in the IoT system,
and then survey the state of the arts on the MIMO-NOMA IoT system.

###  II-A AoI in IoT

In [16], Grybosi _et al._ proposed the SIC-aided age-independent random access
(AIRA-SIC) scheme (i.e., a slotted ALOHA fashion) for IoT system, where the
receiver operates SIC to reconstruct collisions of various devices. In [17],
Wang _et al._ focused on the problem that minimizes the weighted sum of AoI
cost and energy consumption in the IoT systems by adjusting sample policy, and
proposed a distributed DRL algorithm based on the local observation of each
device. In [18], Elmagid _et al._ aimed to minimize the AoI at the BS and the
energy consumption of generate status at the IoT devices, and formulated an
optimization problem based on the Markov decision process (MDP), then proved
the monotonicity property of the value function associated with the MDP. In
[19], Li _et al._ designed a resource block (RB) allocation, modulation
selecting and coding selecting scheme for each IoT device based on its channel
condition to minimize the long-term AoI of IoT system. In [20], Hatami _et
al._ employed the reinforcement learning to minimize the average AoI for users
in an IoT system consisting of users, energy harvesting sensors, and a cache-
enabled edge node. In [21], Sun _et al._ aimed to minimize the weighted sum of
the expected average AoI of all IoT devices, propulsion energy of unmanned
aerial vehicle (UAV) and transmission energy of IoT devices by determining the
UAV flight speed, UAV placement and channel resource allocation in the UAV-
assisted IoT system. In [22], Hu _et al._ considered an IoT system where the
UAVs take off from a data center to deliver energy and collect data from
sensor nodes, and then fly back to the data center. They minimized the AoI of
the collected data by dynamic programming (DP) and ant colony (AC) heuristic
algorithms. In [23], Emara _et al._ developed a spatiotemporal framework to
evaluate the peak AoI (PAoI) of the IoT system, and compared the PAoI under
the time-triggered traffic with event-triggered traffic. In [24], Lyu _et al._
considered a marine IoT scenario, where AoI is utilized to represent the
impact of of the packet loss and transmission delay. They investigated the
relationship between AoI and state estimation error, and minimized the state
estimation error by decomposition method. In [25], Wang _et al._ investigated
the impact of AoI on the system cost which consists of control cost and
communication energy consumption of the industrial-internet-of-things (IIoT)
system. They proved that the upper bound of cost is affected by AoI. In [26],
Hao _et al._ maximized the sum of the energy efficiency of the IoT devices
under the constraints of AoI by optimizing transmission power and channel
allocation in a cognitive radio based IoT system. However, none of these works
have taken the MIMO-NOMA channel into account.

###  II-B MIMO-NOMA IoT System

In [27], Yilmaz _et al._ proposed a user selection algorithm for MIMO-NOMA IoT
system to improve the sum data rate, and adopted the physical layer network
coding (PNC) to improve the spectral efficiency. In [28], Shi _et al._
considered the downlink of the MIMO-NOMA IoT networks and studied the outage
probability and goodput of the system with the Kronecker model. In [29], Wang
_et al._ proposed that the resource allocation problem consists of the optimal
beamforming strategy and power allocation in the MIMO-NOMA IoT system, where
the beamforming optimization is solved by the zero-forcing method, after that
the power allocation is solved by the convex functions. In [30], Han _et al._
proposed a novel milimeter wave (mmWave) positioning MIMO-NOMA IoT system and
proposed the position error bound (PEB) as a novel performance evaluation
metric. In [31], Zhang _et al._ considered the massive MIMO and NOMA to study
the performance of the IoT system, and calculated the closed form function for
spectral and energy efficiencies. In [32], Chinnadurai _et al._ considered the
heterogeneous cellular network and formulated a problem to maximize the energy
efficiency of the MIMO-NOMA IoT system, where the non-convex problem was
solved based on the branch and reduced bound (BRB) approach. In [33], Gao _et
al._ considered the mmWave massive MIMO and NOMA IoT system to maximize the
weighted sum transmission rate through optimizing the power allocation, then
solved the problem by convex method. In [34], Feng _et al._ considered an UAV
aided MIMO-NOMA IoT system and regarded an UAV as BS. They formulated the
problem to maximize the sum transmission rate of the downlink through
optimizing the placement of UAVs, beam pattern and transmission power, then
solved the problem by convex methods. In [35], Ding _et al._ designed a novel
MIMO-NOMA system consisting of two different users, where user one should be
served with strict quality-of-service (QoS) requirement, and user two accesses
channel by the no-orthogonal way opportunistically, thus the requirement that
small packets of user one in the IoT system should be transmitted in time can
be met. However, these works have not considered the AoI of the MIMO-NOMA IoT
system.

As mentioned above, there is no work considering the AoI in the MIMO-NOMA IoT
system, which motivates us to conduct this work.

##  III System Model And Problem Formulation

Figure 1: MIMO-NOMA IoT system. TABLE I: The summary for notations. Notation |  Description
---|---
$B$ |  Population size of genetic algorithm.
$C_{s}$ |  The energy consumption for sample fresh information and generate upload packet.
$c_{m,t}$ |  Complex data symbol with 1 as variance.
$d_{m}$ |  The communication distance between device $m$ and BS.
$E$ |  Number of episodes.
$F_{c}/F_{m}$ |  Probability of offsprings in genetic algoritm for crossover / mutation.
$G_{P}/U_{P}$ |  Complexity of the primary networks for computing gradients / updating parameters.
$\bm{h}_{m}(t)$ |  The channel vector between device $m$ and BS in slot $t$.
$i$ |  Index of transition tuples in mini-batch.
$I$ |  The number of transition tuples in a mini-batch.
$\mathcal{I}_{m}$ |  The set of devices of which the received power is weaker than device $m$.
$J(\mu)$ |  The long-term discounted reward under policy $\mu$.
$K$ |  The number of antennas equipped in BS.
$l_{m,t}$ |  The transmission delay of device $m$ in slot $t$.
$L$ |  Loss function.
$l_{m,t}$ |  The transmission delay of device $m$ in slot $t$.
$\bm{n}(t)$ |  Additive white Gaussian noise.
$N_{GA}$ |  Evolution times of genetic algorithm.
$m/M/\mathcal{M}$ |  Index / number / set of devices.
$\bm{o}_{t}/\bm{o}_{m,t}$ |  State in slot $t$ of all devices / device $m$.
$\bm{p}_{t}$ / $p_{m,t}$ |  Transmission power of all devices / device $m$.
$P_{m,t}$ |  Maximum transmission power device $m$.
$Q(\bm{o}_{t},\bm{p}_{t})$ |  Action-value function under $\bm{o}_{t}$ and $\bm{p}_{t}$.
$Q$ |  Packet size.
$r_{t}$ |  Reward function.
$\bm{s}_{t}$ / $s_{m,t}$ |  Indicator of sample or not for all devices / device $m$.
$S_{d}$ |  Complexity of calculating sample decisions based on power allocation.
$t$ / $\mathcal{T}$ |  Index / set of slot.
$\mathcal{U}$ |  The set of undecoded received power of BS.
$\bm{u}_{t}$ / $u_{m,t}$ |  Indicator of transmission success for all devices / device $m$.
$W$ |  Bandwidth of system.
$\alpha_{a}$ / $\alpha_{c}$ |  Learning rate of actor network / critic network.
$\beta$ |  Discouting factor.
$\gamma_{a}$, $\gamma_{c}$ |  Weighted factors of reward function.
$\Gamma_{m,t}$ |  Received power of BS for device $m$ in slot $t$.
$\Delta_{t}$ |  Exploration noise.
$\varepsilon_{m,t}$ |  The energy consumed by device $m$ in slot $t$.
$\overline{\varepsilon}$ |  The average sum energy consumption in slot $t$.
$\zeta$ / $\zeta^{\prime}$ |  Parameters of critic-network / target critic-network.
$\theta$ / $\theta^{\prime}$ / $\theta^{*}$ |  Parameters of actor-network / target actor-network / optimal policy.
$\kappa$ |  The constant for the update of target networks.
$\mu_{\theta}$ |  Policy approximated by actor-network with $\theta$.
$\pi_{m,t}$ |  Transmission rate of device $m$ in slot $t$.
$\rho_{m}$ |  Normalized channel correlation coefficient.
$\sigma_{R}^{2}$ |  Variance for the noise of received signal.
$\phi_{m,t}$ / $\Phi_{m,t}$ |  AoI of device $m$ in slot $t$ on device / BS.
$\overline{\Phi}$ |  The average sum AoI.

###  III-A Scenario description

The network scenario is illustrated in Fig. 1. We consider a MIMO-NOMA IoT
system consisting of a BS with $K$ antennas and a set
$\mathcal{M}=\\{1,\cdots,m,\cdots,M\\}$ of the single-antenna IoT devices.
Here, each IoT device is embedded with a sensor and a transmitter. The time
duration is devided into $T$ slots, each of which is $\tau$. The set of slots
is denoted as $\mathcal{T}=\\{1,\cdots,t,\cdots,T\\}$. At the beginning of
each slot $t$, the BS determines the policy (including the sample collection
requirements of each device $m$, denoted as $s_{m,t}$, and transmission power
of each device $m$, denoted as $p_{m,t}$) and then sends $s_{m,t}$ and
$p_{m,t}$ to each device $m$. If $s_{m,t}=1$, device $m$ will sample data in
slot $t$, and transmit the data to the BS with transmission power $p_{m,t}$
over the MIMO-NOMA channel. Otherwise, it does not sample data in slot $t$.
The key notations are listed in Table I. Next we will construct the MIMO-NOMA
channel model.

###  III-B MIMO-NOMA channel model

Let $c_{m,t}$ be the data symbol of device $m$ in slot $t$ with $1$ as
variance, thus the signal of the data transmitted by device $m$ is
$\sqrt{p_{m,t}}c_{m,t}$. Let $\bm{h}_{m}(t)\in\mathbb{C}^{K\times 1}$ be the
channel power gain between BS and device $m$ in slot $t$, thus the
corresponding signal received by BS is $\bm{h}_{m}(t)\sqrt{p_{m,t}}c_{m,t}$.
Note that $c_{m,t}$ is unknown for BS, so that it is difficult for the BS to
calculate the received signal. Hence, the BS needs to adopt the SIC technology
to decode the received signal transmitted by each device, which is expressed
as

$\begin{aligned}
\bm{y}(t)=\sum_{m\in\mathcal{M}}\bm{h}_{m}(t)\sqrt{p_{m,t}}c_{m,t}+\bm{n}(t)\\\
p_{m,t}\in{[0,P_{m,max}]},\forall m\in\mathcal{M},\forall
t\in\mathcal{T}\end{aligned}\quad,$ (1)

where $\bm{n}(t)\in\mathbb{C}^{K\times 1}$ is the complex additive white
Gaussian noise (AWGN) with variance $\sigma_{R}^{2}$ and $P_{m,max}$ is the
maximum transmission power of device $m$.

Similar to [36], it is assumed that $\bm{h}_{m}(t)$ is known by the BS. In
addition, the BS also knows $p_{m,t}$, thus the BS can calculate the power of
the received signal transmitted by device $m$ as

$\Gamma_{m,t}=p_{m,t}||\bm{h}_{m}(t)||^{2}.$ (2)

Then, the BS decodes the received signal transmitted by each device
sequentially with SIC mode of NOMA. For one iteration, the BS decodes the
signal with the highest received power from $\bm{y}(t)$ while considering the
other signals as interference, then removes the decoded signal from
$\bm{y}(t)$ and starts the next iteration until all signals are decoded.

For instance, in an iteration the received power of the signal transmitted by
device $m$ is the highest among the signals without being decoded. Denote
$\mathcal{I}_{m}=\\{k\in\mathcal{M}\mid\Gamma_{k,t}<\Gamma_{m,t}\\}$ as the
set of devices whose signals’ received powers is less than device $m$. Thus
the signal transmitted by each device $k\in\mathcal{I}_{m}$ is deemed as the
interference. In this case, $\bm{y}(t)$ is rewritten as

$\displaystyle\bm{y}(t)=\bm{h}_{m}(t)\sqrt{p_{m,t}}c_{m,t}+\sum_{k\in\mathcal{I}_{m}}\bm{h}_{k}(t)\sqrt{p_{k,t}}c_{k,t}+\bm{n}(t),$
(3)

where $\sum_{k\in\mathcal{I}_{m}}\bm{h}_{k}(t)\sqrt{p_{k,t}}c_{k,t}$ indicates
the interference, thus the signal-to-interference-plus-noise ratio (SINR) of
device $m$ is calculated as

$\begin{split}\gamma_{m,t}&=\frac{p_{m,t}||\bm{h}_{m}(t)||^{2}}{\sum\limits_{k\in\mathcal{I}_{m}}p_{k,t}||\bm{h}_{k}(t)||^{2}+\sigma_{R}^{2}}\\\
&=\frac{\Gamma_{m,t}}{\sum\limits_{k\in\mathcal{I}_{m}}\Gamma_{k,t}+\sigma_{R}^{2}}\\\
\end{split}\quad.$ (4)

The transmission rate of device $m$ in slot $t$ can be derived according to
Shannon capacity formula, i.e.,

$\pi_{m,t}=W\log_{2}(1+\gamma_{m,t}),$ (5)

where $W$ is the bandwidth of the MIMO-NOMA channel.

###  III-C AoI model

Denote $\phi_{m,t}$ as the AoI at device $m$ in slot $t$, which can be
calculated as

$\phi_{m,t}=\left\\{\begin{array}[]{l}{0,\qquad\qquad\qquad s_{m,t}=1}\\\
\phi_{m,t-1}+\tau,\qquad otherwise\end{array}.\right.\\\ $ (6)

According to Eq. (6), at the beginning of slot $t$, if device $m$ samples
data, i.e., $s_{m,t}=1$, $\phi_{m,t}$ will be reset to $0$. Otherwise,
$\phi_{m,t}$ will be increased by $\tau$.

Device $m$ will transmit data with transmission power $p_{m,t}$ after sampling
data. If data volume transmitted within a slot is larger than the packet size
$Q$, i.e., $\pi_{m,t}\cdot\tau\geq Q$, device $m$ will transmit data
successfully; otherwise, the transmission is failed. Denote $u_{m,t}=1$ as a
successful transmission by device $m$ in slot $t$ and $u_{m,t}=0$ as an
unsuccessful transmission, we have

$u_{m,t}=\left\\{\begin{array}[]{l}{1,\qquad\pi_{m,t}\cdot\tau\geq Q}\\\
{0,\qquad otherwise}\end{array}.\right.\\\ $ (7)

If a transmission from device $m$ is successful, the AoI at the BS equals the
aggregation of AoI at device $m$ and the transmission delay. Otherwise, the
AoI at the BS is increased by a slot, thus we have

$\Phi_{m,t}=\left\\{\begin{array}[]{l}{\phi_{m,t}+l_{m,t},\qquad u_{m,t}=1}\\\
{\Phi_{m,t-1}+\tau,\qquad otherwise}\end{array},\right.\\\ $ (8)

where $l_{m,t}$ is the transmission delay of device $m$ in slot $t$, which is
calculated as

$l_{m,t}=\frac{Q}{\pi_{m,t}}.$ (9)

The AoI of the MIMO-NOMA IoT system is measured by averaging the AoI of all
devices at BS, i.e.,

$\overline{\Phi}=\frac{1}{T}\sum_{t\in\mathcal{T}}\sum_{m\in\mathcal{M}}\Phi_{m,t}.$
(10)

###  III-D Energy consumption model

Since each device consumes energy in data sampling and transmission, the
energy consumption of device $m$ in slot $t$ can be calculated as

$\varepsilon_{m,t}=s_{m,t}C_{s}+p_{m,t}l_{m,t},$ (11)

where $C_{s}$ is the energy consumption for data sampling[17], and
$p_{m,t}l_{m,t}$ is the energy consumption for transmission.

The BS has a stable power supply, hence the energy consumption of BS is
sufficient and thus it is not taken into account in the system. Hence the
energy consumption of the MIMO-NOMA IoT system is measured by averaging the
energy consumption of all devices, i.e.,

$\overline{\varepsilon}=\frac{1}{T}\sum_{t\in\mathcal{T}}\sum_{m\in\mathcal{M}}\varepsilon_{m,t}.$
(12)

###  III-E Problem formulation

In this work, our target is to minimize the AoI and energy consumption of the
MIMO-NOMA IoT system, which is impacted by $p_{m,t}$ and $s_{m,t}$. Therefore
the optimization problem is formulated as

$\displaystyle\min_{\bm{s}_{t},\bm{p}_{t}}\left[\gamma_{a}\overline{\Phi}+\gamma_{e}\overline{\varepsilon}\right]$
(13) $\displaystyle s.t.\qquad$ $\displaystyle p_{m,t}\in[0,P_{m,max}],\forall
m\in\mathcal{M},\forall t\in\mathcal{T},$ (13a) $\displaystyle
s_{m,t}\in\\{0,1\\},\forall m\in\mathcal{M},\forall t\in\mathcal{T},$ (13b)

where $\bm{s}_{t}=\\{s_{1,t},\cdots,s_{m,t},\cdots,s_{M,t}\\}$ and
$\bm{p}_{t}=\\{p_{1,t},\cdots,p_{m,t},\cdots,p_{M,t}\\}$, $\gamma_{a}$ and
$\gamma_{e}$ are the non-negative weighted factors. Next we will present a
solution to the problem based on DRL.

##  IV DRL Method for Optimization of Power Allocation

In this section, we solve the optimization problem based on the DRL. First, we
design the DRL framework including the state, action and reward function,
where the relationship between the sample collection requirements and
transmission power is derived to facilitate DRL algorithm to solve the
problem. Then we obtain a near optimal power allocation based on the DRL
algorithm.

###  IV-A DRL framework

The DRL framework consists of three significant elements: state, action and
reward function. For each slot, the agent observes the current state and takes
the current action according to policy $\mu$, where policy $\mu$ yields the
action based on the state. Then the agent calculates its corresponding reward
under the current state and action according to the reward function, while the
current state in the environment transits to the next state. Next, we will
design agent, state, action and reward function, respectively.

  * •

Agent: In each slot, the BS determines the transmission power and sample
collection requirements of each device based on its observation, thus we
consider the BS as the agent.

  * •

State: In the system model, the state $\bm{o}_{t}$ observed by the BS in slot
$t$ is defined as

$\bm{o}_{t}=[\bm{o}_{1,t},\cdots,\bm{o}_{m,t},\cdots,\bm{o}_{M,t}],$ (14)

where $\bm{o}_{m,t}$ represents the observation of device $m$, which is
designed as

$\bm{o}_{m,t}=[u_{m,t-1},\gamma_{m,t-1},\Phi_{m,t-1}].$ (15)

Here, $u_{m,t-1}$, $\gamma_{m,t-1}$ and $\Phi_{m,t-1}$ can be calculated by
the BS from the historical data in slot $t-1$.

  * •

Action: According to the problem formulated in Eq. (13), the action in slot
$t$ is set as

$\bm{a}_{t}=[\bm{s}_{t},\bm{p}_{t}].$ (16)

$\displaystyle\gamma_{a}\overline{\Phi}+\gamma_{e}\overline{\varepsilon}$ (17)
$\displaystyle=$
$\displaystyle\frac{1}{T}\sum_{t\in\mathcal{T}}\sum_{m\in\mathcal{M}}\Big{[}\gamma_{a}\Phi_{m,t}+\gamma_{e}\varepsilon_{m,t}\Big{]}$
(17a) $\displaystyle=$
$\displaystyle\frac{1}{T}\sum_{t\in\mathcal{T}}\sum_{m\in\mathcal{M}}\Big{[}\gamma_{a}\big{[}(1-u_{m,t})(\Phi_{m,t-1}+\tau)+u_{m,t}(\phi_{m,t}(s_{m,t})+l_{m,t})\big{]}+\gamma_{e}(s_{m,t}C_{s}+p_{m,t}l_{m,t})\Big{]}$
(17b) $\displaystyle=$
$\displaystyle\frac{1}{T}\sum_{t\in\mathcal{T}}\sum_{m\in\mathcal{M}}\Big{[}[\gamma_{a}u_{m,t}\phi_{m,t}(s_{m,t})+\gamma_{e}s_{m,t}C_{s}]+\gamma_{a}[(1-u_{m,t})(\Phi_{m,t-1}+\tau)+u_{m,t}l_{m,t}]+\gamma_{e}p_{m,t}l_{m,t}\Big{]}$
(17c)

$\displaystyle\gamma_{a}\Phi_{m,t}(s_{m,t},p_{m,t})+\gamma_{e}\varepsilon_{m,t}(s_{m,t},p_{m,t})$
(18) $\displaystyle=$
$\displaystyle\gamma_{a}u_{m,t}(1-s_{m,t})(\phi_{m,t-1}+\tau)+\gamma_{e}s_{m,t}C_{s}+\gamma_{a}[(1-u_{m,t})(\Phi_{m,t-1}+\tau)+u_{m,t}l_{m,t}]+\gamma_{e}p_{m,t}l_{m,t}$
(18a) $\displaystyle=$ $\displaystyle
s_{m,t}[\gamma_{e}C_{s}-\gamma_{a}u_{m,t}(\phi_{m,t-1}+\tau)]+\gamma_{a}[u_{m,t}(\phi_{m,t-1}+\tau)+(1-u_{m,t})(\Phi_{m,t-1}+\tau)+u_{m,t}l_{m,t}]+\gamma_{e}p_{m,t}l_{m,t}$
(18b) $\displaystyle=$ $\displaystyle s_{m,t}C_{m,t,1}+C_{m,t,2}$ (18c)

The traditional two DRL algorithms DDPG and Deep Q-Learning (DQN) are suitable
for continuous and discrete action space, respectively. However,
$s_{m,t}\in\\{0,1\\}$ and $p_{m,t}\in[0,P_{m,max}]$ in Eq. (16), thus the
space of $\bm{s}_{t}$ is discrete while the space of $\bm{p}_{t}$ is
continuous. Hence, the optimization problem can neither be solved by DQN nor
DDPG. Next, we will investigate the relationship between $p_{m,t}$ and
$s_{m,t}$ to handle this dilemma.

Substituting Eqs. (10) and (12) into Eq. (13), the optimization objective is
rewritten as Eq. (17a). Then substituting Eqs. (8) and (11) into Eq. (17a), we
can obtain Eq. (17b), where $\phi_{m,t}$ is denoted as $\phi_{m,t}(s_{m,t})$
to indicate that it is the function of $s_{m,t}$. Then reorganizing Eq. (17b),
we have Eq. (17c). The first term of Eq. (17c) is related with $s_{m,t}$, next
we rewrite the first term of Eq. (17c) as Eq. (18) to investigate the
relationship between $s_{m,t}$ and $p_{m,t}$. Substituting Eq. (6) into Eq.
(18), we have Eq. (18a). Then merge the homogeneous terms containing $s_{m,t}$
and $\gamma_{a}$ in Eq. (18a), respectively, we have Eq. (18b). Let
$C_{m,t,1}=\gamma_{e}C_{s}-\gamma_{a}u_{m,t}(\phi_{m,t-1}+\tau)$ and
$C_{m,t,2}=\gamma_{a}[u_{m,t}(\phi_{m,t-1}+\tau)+(1-u_{m,t})(\Phi_{m,t-1}+\tau)+u_{m,t}l_{m,t}]+\gamma_{e}p_{m,t}l_{m,t}$,
thus Eq. (18b) is rewritten as Eq. (18c), where $C_{m,t,1}$ is the coefficient
for homogeneous terms containing $s_{m,t}$ in Eq. (18b), and $C_{m,t,2}$
contains all terms without $s_{m,t}$ in Eq. (18b).

In $C_{m,t,1}$ and $C_{m,t,2}$, $\phi_{m,t-1}$ can be calculated by the BS
based on the historical data in slot $t-1$[17] and $\Phi_{m,t-1}$ is known for
the BS. In addition, BS can calculate $\gamma_{m,t}$ according to Eqs.
(4)-(5), thus $u_{m,t}$ and $l_{m,t}$ can be further calculated according to
Eqs. (7) and (9) given ${p}_{m,t}$, which means that $C_{m,t,1}$ and
$C_{m,t,2}$ depend on ${p}_{m,t}$ and are independent of $s_{m,t}$. Hence, the
optimal sample collection requirements to minimize
$s_{m,t}C_{m,t,1}+C_{m,t,2}$, denoted as $s^{*}_{m,t}$, is achieved when the
term $s_{m,t}C_{m,t,1}$ is minimum, thus we have

$s^{*}_{m,t}=\left\\{\begin{array}[]{l}{1,\qquad C_{m,t,1}<0}\\\ {0,\qquad
otherwise}\end{array}.\right.$ (19)

Hence, the optimal sample collection requirements can be determined according
to Eq. (19) when ${p}_{m,t}$ is given and Eq. (13) can be rewritten as

$\displaystyle\min_{\bm{p}_{t}}\left[\gamma_{a}\overline{\Phi}+\gamma_{e}\overline{\varepsilon}\right]$
(20) $\displaystyle s.t.\qquad$ $\displaystyle p_{m,t}\in[0,P_{m,max}],\forall
m\in\mathcal{M},\forall t\in\mathcal{T},$ (20a) $\displaystyle
s^{*}_{m,t}=\left\\{\begin{array}[]{l}{1,\qquad C_{m,t,1}<0}\\\ {0,\qquad
otherwise}\end{array}.\right.$ (20b)

According to Eq. (20), the action $\bm{a}_{t}$ is only reflected by
$\bm{p}_{t}$. Therefore, DDPG which is suitable for the continuous action
space can be employed as the desired algorithm to solve the optimization
problem in Eq. (20).

  * •

Reward function: The BS aims to minimize the AoI and energy consumption of the
MIMO-NOMA IoT system, and the target of the DDPG algorithm is to maximize the
reward function. Therefore the reward function in slot $t$ can be defined as

${r}_{t}(\bm{o}_{t},\bm{p}_{t})=-\sum_{m\in\mathcal{M}}[\gamma_{a}\Phi_{m,t}+\gamma_{e}\varepsilon_{m,t}].$
(23)

Furthermore, the expected long-term discounted reward of the system can be
defined as

$J(\mu)=\mathbb{E}\left[\sum_{t=1}^{T}\beta^{t-1}r_{t}(\bm{o}_{t},\bm{p}_{t})|_{\bm{p}_{t}=\mu(\bm{o}_{t})}\right],$
(24)

where $\beta\in[0,1]$ is the discounting factor, $\bm{p}_{t}=\mu(\bm{o}_{t})$
indicates the action under the state $\bm{o}_{t}$, which is derived through
policy $\mu$. Thus, our objective in this paper becomes finding the optimal
policy to minimize $J(\mu)$.

###  IV-B Optimizing power allocation based on DDPG

Figure 2: Flow diagram of DDPG

In this subsection, we will introduce the architecture of the DDPG algorithm
including primary networks (a actor network and a critic network) and target
networks (a target actor network and a target critic-network)[37], where the
actor network is adopted for policy approximation and improvement, the critic
network is adopted for policy evaluation and the target networks are adopted
to improve the stability of algorithm. Both primary and target networks are
neural networks (DNNs). Denote $\theta$, $\zeta$, $\theta^{\prime}$ and
$\zeta^{\prime}$ as parameters of the actor network, critic network, target
actor network and target critic network, respectively, $\mu_{\theta}$ as the
policy approximated by actor-network, and $\Delta_{t}$ as the noise added on
action for exploration in slot $t$. Next, we will present the training stage
of the DDPG algorithm in detail.

The parameters $\theta$ and $\zeta$ are first initialized randomly,
$\theta^{\prime}$ and $\zeta^{\prime}$ are set as $\theta$ and $\zeta$,
respectively. In addition, a replay experience buffer $\mathcal{R}$ is built
up to cache the state transitions (lines 1-3).

Next, the algorithm loops for $E$ episodes. At the beginning of each episode,
the simulation parameters of the system model is reset as $u_{m,0}=0$,
$p_{m,0}=1$ and $\Phi_{m,0}=0$ for each device $m$, $\bm{h}_{m}(0)$ is
initialized randomly. Given $p_{m,0}$ and $\bm{h}_{m}(0)$, the SINR
$\gamma_{m,0}$ is calculated according to Eqs. (2)-(4), then the state of each
device $m$, i.e., $\bm{o}_{m,1}=[u_{m,0},\gamma_{m,0},\Phi_{m,0}]$ is observed
by the agent (lines 4-6).

Afterwards, the algorithm iterates from slot $1$ to $T$. For slot $t$, the
actor network yields the output $\mu_{\theta}(\bm{o}_{t}|\theta)$ under the
observed state $\bm{o}_{t}$ and policy $\mu$ with parameters $\theta$. Then a
noise $\Delta_{t}$ is generated and the agent calculates the transmission
powers of all devices according to
$\bm{p}_{t}=\mu_{\theta}(\bm{o}_{t}|\theta)+\Delta_{t}$. After that the agent
calculates $u_{m,t}$, $s_{m,t}$ and $\gamma_{m,t}$ of each device $m$
according to Eqs. (7), (19) and (4), respectively. Afterwards, the agent
calculates $\Phi_{m,t}$ and $\varepsilon_{m,t}$ according to Eqs. (8) and
(11), respectively, and thus obtain the state of slot $t$, i.e.,
$\bm{o}_{t+1}$, then calculates $r_{t}$ according to Eq. (23). The above tuple
$[\bm{o}_{t},\bm{p}_{t},r_{t},\bm{o}_{t+1}]$ in the replay buffer. Then the
agent inputs $\bm{o}_{t+1}$ into the actor network and starts the next
iteration if the number of samples in replay buffer is not larger than $I$
(lines 7-10).

If the number of tuples in the replay buffer exceeds $I$, the parameters
$\theta$, $\theta^{\prime}$, $\zeta$, and $\zeta^{\prime}$ will be updated to
maximize $J(\mu_{\theta})$. Here, $\theta$ is updated toward the direction of
the gradient $\nabla_{\theta}J(\mu_{\theta})$. Specifically, the agent
uniformly retrieves a mini-batch consisting of $I$ tuples from the replay
buffer. For each tuple $i$, i.e.,
$(\bm{o}_{i},\bm{p}_{i},r_{i},\bm{o}_{i}^{\prime})$
$(i\in\\{1,2,\cdots,I\\})$, the agent inputs $\bm{o^{\prime}}_{i}$ into the
target actor network and outputs
$\bm{p}_{i}^{\prime}=\mu_{\theta^{\prime}}({\bm{o^{\prime}}_{i}}|\theta^{\prime})$,
then inputs $\bm{o}_{i}^{\prime}$ and $\bm{p}_{i}^{\prime}$ into the target
critic network and outputs
$Q^{\zeta^{\prime}}({\bm{o}_{i}^{\prime}},\bm{p}_{i}^{\prime})$, then
calculates the target value as

$y_{i}=r_{i}+\beta
Q^{\zeta^{\prime}}({\bm{o}_{i}^{\prime}},\bm{p}_{i}^{\prime})|_{\bm{p}_{i}^{\prime}=\mu_{\theta^{\prime}}({\bm{o^{\prime}}_{i}}|\theta^{\prime})}.$
(25)

While $\bm{o}_{i}$ and $\bm{p}_{i}$ are the input and
$Q^{\zeta}(\bm{o}_{i},\bm{p}_{i})$ is the output of critic-network, the loss
function can be expressed as

$L(\zeta)=\frac{1}{I}\sum_{i=1}^{I}\left[y_{i}-Q^{\zeta}(\bm{o}_{i},\bm{p}_{i})\right]^{2}.$
(26)

Then the critic network is updated by the gradient descending method with the
gradient of loss function $\nabla_{\zeta}L(\zeta)$ [38] (lines 11-13), i.e.,

$\zeta\leftarrow\zeta-\alpha_{c}\nabla_{\zeta}L(\zeta),$ (27)

where $\alpha_{c}$ is the learning rate of the critic network.

After that, the agent calculates the gradient $\nabla_{\theta}J(\mu_{\theta})$
as [39]

$\begin{split}&\nabla_{\theta}J(\mu_{\theta})\\\
&\approx\frac{1}{I}\sum_{i=1}^{I}\nabla_{\theta}Q^{\zeta}(\bm{o}_{i},\bm{p}_{\mu})|_{\bm{p}_{\mu}=\mu_{\theta}(\bm{o}_{i}|\theta)}\\\
&=\frac{1}{I}\sum_{i=1}^{I}\nabla_{\theta}\mu_{\theta}(\bm{o}_{i}|\theta)\cdot\nabla_{\bm{p}_{\mu}}Q^{\zeta}(\bm{o}_{i},\bm{p}_{\mu})|_{\bm{p}_{\mu}=\mu_{\theta}(\bm{o}_{i}|\theta)}\end{split},$
(28)

where chain rule is applied to derive the gradient of
$Q^{\zeta}(\bm{o}_{i},\bm{p}_{\mu})$ with respect to $\theta$ [39]. Given
$\nabla_{\theta}J(\mu_{\theta})$, actor-network can be updated by gradient
ascending to maximize $J(\mu_{\theta})$, i.e,

$\theta\leftarrow\theta+\alpha_{a}\nabla_{\theta}J(\mu_{\theta}),$ (29)

where $\alpha_{a}$ is the learning rate of actor network.

After the parameters of the primary networks are updated, the parameters of
the target networks are updated based on the parameters of primary networks,
i.e.,

$\begin{split}\zeta^{\prime}&\leftarrow\kappa\zeta+(1-\kappa)\zeta^{\prime}\\\
\theta^{\prime}&\leftarrow\kappa\theta+(1-\kappa)\theta^{{\prime}}\end{split}\quad,$
(30)

where $\kappa$ is a constant much smaller than 1, i.e., $\kappa\ll 1$. (line
15).

Up to now, the iteration for slot $t$ is finished and the agent starts the
next iteration until the number of slots reaches $T$. Then the agent starts
the next episode. When the number of episodes reaches $E$, the training stage
is finished and outputs the near optimal policy. The pseudocode of the
training stage is described in Algorithm 1.

Input: $\gamma$, $\tau$, $\theta$, $\zeta$

Output: optimized DNNs

1 Randomly initialize the $\theta$, $\zeta$;

2 Initialize target networks by $\zeta^{\prime}\leftarrow\zeta$,
$\theta^{\prime}\leftarrow\theta$;

3 Initialize replay experience buffer $\mathcal{R}$;

4 for  _episode from $1$ to $E$ _ do

5 Reset simulation parameters for the system model;

6 Receive initial observation state $\bm{o}_{1}$;

7 for  _slot $t$ from $1$ to $T$ _ do

8 Generate the transmission power of all devices according to the current
policy, state and exploration noise
$\bm{p}_{t}=\mu_{\theta}(\bm{o}_{t}|\theta)+\Delta_{t}$ ;

9 Execute action $\bm{p}_{t}$, observe reward $r_{t}$ and new state
$\bm{o}_{t+1}$ from the system model;

10 Store transition tuple $(\bm{o}_{t},\bm{p}_{t},r_{t},\bm{o}_{t+1})$ in
$\mathcal{R}$;

11 if  _number of tuples in $\mathcal{R}$ is larger than $I$ _ then

12 Randomly sample a mini-batch of $I$ transitions tuples from $\mathcal{R}$;

13 Update the critic network by minimizing the loss function according to Eq.
(27);

14 Update the actor network according to Eq. (29);

15 Update target networks according to Eqs. (30).

16

17

Algorithm 1 Training stage of the DDPG algorithm

Next, the testing stage is initialized to test the performance under the near
optimal policy. Compared with the training stage, the parameter updating
process is omitted in testing process and actions in each slot are generated
by the near optimal policy. The corresponding pseudocode is shown in Algorithm
2, where $\theta^{*}$ is the parameter to achieve the near optimal policy in
the training stage.

1 for  _episode from $1$ to $E$ _ do

2 Reset simulation parameters for the system model;

3 Receive initial observation state $\bm{o}_{1}$;

4 for  _slot $t$ from $1$ to $T$ _ do

5 Generate the transmission power of all devices according to the near optimal
policy and current state $\bm{p}_{t}=\mu_{\theta}(\bm{o}_{t}|\theta^{m*})$ ;

6 Execute the action $\bm{p}_{t}$;

7 Observe reward the $r_{t}$ and new state $\bm{o}_{t+1}$.

8

Algorithm 2 Testing stage of the DDPG algorithm

###  IV-C Complexity Investigation

In this subsection, we investigated the complexity of proposed algorithm.
Denote $G_{P}$ and $U_{p}$ as the computational complexity for computing
gradients and updating parameters of the primary networks, respectively. Since
the architecture of target networks are same as primary networks, the
computational complexity for updating parameters of the target networks are
the same as primary networks. The complexity of proposed algorithm is related
to the number of slots in training process. To be specific, during each slot
the primary networks calculate gradients and updating parameters, while the
target networks update parameters with the parameters of primary networks
according to Eq. (30). Moreover, denote the complexity of calculating sample
decisions based on power allocation as $S_{d}$. Thus the complexity of the
proposed algorithm in a slot is $O(G_{P}+2U_{P}+S_{d})$. Note that the
gradients calculating and parameters updating will be processed until number
of tuples cached in the replay buffer exceeds I, and the proposed algorithm
will loop $E$ episodes which each of episodes contains T slots, to this end
the complexity of proposed algorithm can be expressed as $O((E\cdot
T-I)(G_{P}+2U_{P}+S_{d}))$.

##  V Simulation Results and Analysis

In this section, we will conduct simulation to verify the effectiveness of our
proposed power allocation policy. The experiments consist of both the training
and testing stage. The simulation scenario is described in the system model
and the simulation tool is Python 3.6. In the simulation, both actor network
and critic network are the four-layer fully connected DNN with two hidden
layers which are equipped with $400$ and $300$ neurons, respectively. Adam
optimization method [40] is adopted to update the parameters of critic network
and actor network. The noise $\Delta_{t}$ (for exploration) follows the
Ornstein-Uhlenbeck (OU) process with decay-rate $0.15$ and variation $0.004$,
respectively [41]. The small scale fading of each device is initialized by
white Gaussian noise, and the Rayleigh block fading model is employed to
simulate the stochastic small scale fading[42]. The reference channel gain of
each device is $-30dB$ when the communications distance is $1$ meter, the
path-loss exponent is $2$, and the communication distances is randomly set
within a range $[50,100]$ meters. The parameters are summarized in TABLE II.

Figure 3: Learning curves under various number of devices. TABLE II: Values of
the parameters in the experiments. Parameters of system model[43]
---
Parameter | Value | Parameter | Value
$\tau$ |  $0.1$ s | $K$ | $4$
$W$ |  $18$ kHz | $C_{s}$ | 0.5 J
$P_{m,max}$ |  $2$ W | $T$ | $500$
Parameters of Agent[38]
Parameter | Value | Parameter | Value
$\kappa$ | $0.001$ | $I$ | $64$
$E$ | $800$ | $\beta$ | $0.99$
$|\mathcal{R}|$ | $2.5\times 10^{5}$ | $\gamma_{e}$ | $0.5$
$\gamma_{a}$ | $0.5$ | $\alpha_{a}$ | $10^{-3}$
$\alpha_{c}$ | $10^{-4}$ | $F_{c}/F_{m}$ | $0.8/0.5$
$B$ | $10$ | $N_{GA}$ | 50

###  V-A Training Stage

Fig. 3 shows the learning curves in the training stage, i.e., rewards in
different episode, for different numbers of IoT devices. It can be seen that
the rewards of different curves rise and fluctuate from episode $0$ to $150$,
which reflects that the agent is learning the policy to maximize the average
reward. After that the learning curves turn out to be stable, which indicates
that the near optimal policy has been learned by the agent. Note that there is
a litter jitters after episode $150$, it is because the agent is adjusting
slightly since the exploration noise prevents the agent from converging into
the local optima. It also can be seen that the large number of devices incurs
a low reward. It is attributed to the fact that each device will be affected
by more interference as the number of devices in the system increases, which
leads to the lower transmission rate. It will prolongs the transmission delay
and further increase the AoI of the system. Then the BS would inform the
devices to consume more energy to sample more frequently and transmit faster,
thus the lower AoI can be guaranteed.

###  V-B Testing Stage

In the testing stage, we check the performance of the near optimal policy
obtained in the training stage. Random power allocation policy and Genetic
Algorithm (GA) [44] are adopted for comparison, random power allocation policy
and GA are introduced as follow:

  * •

Random policy: Randomly allocates the power of each device $m$ within
$[0,P_{m,max}]$ and the sample collection requirements is obtained according
to Eq. (19).

  * •

Genetic Algorithm: In each time slot, BS randomly generates population vector
according to $P_{m,max}$ and population size $B$, which means that there are
$B$ individuals in the population vector, and each individual in the
population vector is the power allocation of all device. BS selects best
individuals in the population vector as offsprings according to fitness, i.e.,
reward function, of each individuals. Then offsprings will evolve for $N_{GA}$
times, for each evolution, the probabilities of crossover and mutation for
these offsprings are $F_{c}$ and $F_{m}$, respectively. Where crossover means
that two individuals in the offsprings exchange power allocation of a random
device, and mutation means that the power allocation of any device in the
offsprings sets in $[0,P_{m,max}]$ randomly. After that, selecting best
individuals from the offsprings that has experienced crossover and mutation as
next offsprings and start next evolution. After all evolutions, select best
individual from the last offsprings, which is the optimal power allocation
derived by GA. After that, BS calculates the optimal sample collection based
on the optimal power allocation according to Eq. (19), then executes the
optimal power allocation derived by GA and optimal sample collection. In the
end, BS iterates into the next time slot.

Figure 4: AoI of the system vs. number of devices.

Fig. 4 presents the AoI of near optimal policy with that of the random policy
and GA. It can be seen that the AoI of the system under the three policies
increases as the number of devices increases. This is because that each device
will suffer from the interference as the number of devices increases, and thus
degrades its transmission delay according to Eq. (9), which would further
increase the AoI of the system. Meanwhile, the near optimal policy and GA
always outperform the random policy, because optimal policy can adjust the
power allocation adaptively according to the observed state, and GA will find
the optimal power allocation according to fitness in the evolutions to ensure
low AoI, while random policy just generates power allocation randomly. It also
can be seen that the near optimal policy outperforms the GA, because GA may
converge into local optima, while DDPG has the exploration noise to prevent
the agent from converging into the local optima.

Figure 5: Energy consumption of the system vs. number of devices. Figure 6:
Average reward vs. number of devices.

Fig. 5 compares the energy consumption of three policies. It can be seen that
the energy consumption increases as the number of devices increases. It is
because that the interferences will increase the AoI of the system, which
imposes the agent to inform the devices to consume more energy to sample more
frequently and transmit faster. Moreover, the increasing number of devices
contributes to the increasing energy consumption according to Eq. (12).
Meanwhile, the near optimal policy and GA always outperform the random policy,
because DDPG and GA can allocate power adaptively to ensure low energy
consumption. Moreover, it also can be seen that the near optimal policy always
outperforms than GA, that is due to the fact that GA do not have the local
optima avoiding scheme like the exploration noise of DDPG.

Figure 7: AoI of the system vs. packet size. Figure 8: Energy consumption vs.
packet size.

Fig. 6 compares the average reward under the three policies, where the reward
is obtained by averaging the test results over all slots. This is shown that
the average reward increases as the number of devices increases. It is because
that the reward function consists of AoI and energy consumption of the system
according to Eq. (23), and both of them increase as the number of devices
increases. Moreover, the average reward under the near optimal policy and GA
are higher than that of random policy. It is attributed to the fact that the
near optimal policy allocates power according to observed state to maximize
the long-term discounted reward, and the GA obtain the optimal power
allocation according to the fitness to maximize the reward. It also can be
seen that near optimal policy is always outperforms than GA, it is because
that GA aim to find the optimal power allocation based on fitness, i.e.,
reward in each slot while lose the sight of long-term reward maximization.

Fig. 7 shows the relationship between the AoI of the system and packet size,
i.e., $Q$, under three policies. It can be seen that the AoI increases as the
packet size increases under the three policies. It is because that according
to Eq. (9), the transmission delay is long when the packet size is large,
which incurs a large AoI of the system. In addition, we can see that the AoI
of the system under the near optimal policy and GA are lower than the AoI
under the random policy. It is because the near optimal policy can adjust the
power allocation based on the observed state, and GA obtain optimal power
allocation according to fitness, which can significantly reduce the AoI of the
system. The gap between near optimal power allocation and GA is caused by the
local optima of GA.

Fig. 8 shows the relationship between the energy consumption of the system and
packet size under three policies. It can be seen that the energy consumption
increases for the three polices when the packet size increases. As shown in
Fig. 7, the transmission delay is long when the packet size is large, thus
incurring the increase of energy consumption of the system. We can see also
that the energy consumption under the near optimal policy and GA are lower
than that of random policy. It is because that the near optimal policy can
adaptively allocate power and GA can obtain optimal power allocation according
to fitness to ensure a lower energy consumption. However, GA may converge into
local optima, thus the energy consumption of GA is lower than the near optimal
policy obtained by DDPG.

##  VI Conclusions

In this paper, we formulated a problem to minimize the AoI and energy
consumption of the MIMO-NOMA IoT system. To solve it, we simplified the
formulated problem and proposed the power allocation scheme based on DDPG to
maximize the long-term discounted reward. Extensive simulations have
demonstrated the superiority of the near optimal policy as compared with the
baseline policy. According to the theoretical analysis and simulation results,
we have obtained the following conclusions:

  * •

A large number of devices would cause a high AoI of the system. To ensure a
lower AoI, the agent will inform the devices to consume more energy to sample
more frequently and transmit faster, thus incurring the increase of energy
consumption.

  * •

A large packet size will lead to long transmission delay, which will further
cause high AoI of the system. In order to reduce the AoI of the system, the
agent would inform the devices to consume more energy to sample more
frequently and transmit faster.

  * •

The near optimal policy trained by DDPG outperforms the baseline policy under
different number of users and packet sizes, which has a good capability to
suit the system dynamic variation.

## References

  * [1] Q. Wu, H. Liu, C. Zhang, Q. Fan, Z. Li, and K. Wang, “Trajectory protection schemes based on a gravity mobility model in iot,” _Electronics_ , vol. 8, no. 2, 2019. [Online]. Available: https://www.mdpi.com/2079-9292/8/2/148
  * [2] Z. Yao, J. Jiang, P. Fan, Z. Cao, and V. Li, “A neighbor-table-based multipath routing in ad hoc networks,” in _The 57th IEEE Semiannual Vehicular Technology Conference, 2003. VTC 2003-Spring._ , vol. 3, 2003, pp. 1739–1743 vol.3.
  * [3] J. Fan, S.-t. Yin, Q. Wu, and F. Gao, “Study on refined deployment of wireless mesh sensor network,” in _2010 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM)_ , 2010, pp. 1–5.
  * [4] Q. Wu, H. Liu, R. Wang, P. Fan, Q. Fan, and Z. Li, “Delay-sensitive task offloading in the 802.11p-based vehicular fog computing systems,” _IEEE Internet of Things Journal_ , vol. 7, no. 1, pp. 773–785, 2020.
  * [5] Q. Wang and Z. Wu, “Beamforming optimization and power allocation for user-centric mimo-noma iot networks,” _IEEE Access_ , vol. 9, pp. 339–348, 2021.
  * [6] S. Wan, J. Lu, P. Fan, and K. B. Letaief, “To smart city: Public safety network design for emergency,” _IEEE Access_ , vol. 6, pp. 1451–1460, 2018\.
  * [7] Q. Wu, Y. Zhao, and Q. Fan, “Time-dependent performance modeling for platooning communications at intersection,” _IEEE Internet of Things Journal_ , vol. 9, no. 19, pp. 18 500–18 513, 2022.
  * [8] Q. Wu and J. Zheng, “Performance modeling and analysis of ieee 802.11 dcf based fair channel access for vehicle-to-roadside communication in a non-saturated state,” _Wireless Networks_ , vol. 21, pp. 1 – 11, 2014.
  * [9] H. Zhu, Q. Wu, X.-J. Wu, Q. Fan, P. Fan, and J. Wang, “Decentralized power allocation for mimo-noma vehicular edge computing based on deep reinforcement learning,” _IEEE Internet Things J._ , pp. 1–1, 2021.
  * [10] X. Chen, J. Lu, P. Fan, and K. B. Letaief, “Massive mimo beamforming with transmit diversity for high mobility wireless communications,” _IEEE Access_ , vol. 5, pp. 23 032–23 045, 2017.
  * [11] Y. Gao, B. Xia, K. Xiao, Z. Chen, X. Li, and S. Zhang, “Theoretical analysis of the dynamic decode ordering sic receiver for uplink noma systems,” _IEEE Commun. Lett._ , vol. 21, no. 10, pp. 2246–2249, 2017.
  * [12] Z. Bo and W. Saad, “Joint status sampling and updating for minimizing age of information in the internet of things,” _IEEE Trans. Commun._ , vol. 67, no. 11, pp. 7468––7482, 2019.
  * [13] Q. Wu, Z. Wan, Q. Fan, P. Fan, and J. Wang, “Velocity-adaptive access scheme for mec-assisted platooning networks: Access fairness via data freshness,” _IEEE Internet Things J._ , vol. 9, no. 6, pp. 4229–4244, 2022.
  * [14] K. Wang, F. R. Yu, L. Wang, J. Li, N. Zhao, Q. Guan, B. Li, and Q. Wu, “Interference alignment with adaptive power allocation in full-duplex-enabled small cell networks,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 3, pp. 3010–3015, 2019.
  * [15] M. Volodymyr, K. Koray, S. David, A. A. Rusu, V. Joel, M. G. Bellemare, G. Alex, R. Martin, A. K. Fidjeland, and O. Georg, “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, no. 7540, pp. 529–33, 2019.
  * [16] J. F. Grybosi, J. L. Rebelatto, and G. L. Moritz, “Age-of-information of sic-aided massive iot networks with random access,” _IEEE Internet Things J._ , pp. 1–1, 2021.
  * [17] S. Wang, M. Chen, Z. Yang, C. Yin, W. Saad, S. Cui, and H. V. Poor, “Distributed Reinforcement Learning for Age of Information Minimization in Real-Time IoT Systems,” _arXiv e-prints_ , p. arXiv:2104.01527, 2021.
  * [18] M. A. Abd-Elmagid, H. S. Dhillon, and N. Pappas, “Aoi-optimal joint sampling and updating for wireless powered communication systems,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 11, pp. 14 110–14 115, 2020.
  * [19] C. Li, Y. Huang, S. Li, Y. Chen, B. A. Jalaian, Y. T. Hou, W. Lou, J. H. Reed, and S. Kompella, “Minimizing aoi in a 5g-based iot network under varying channel conditions,” _IEEE Internet Things J._ , vol. 8, no. 19, pp. 14 543–14 558, 2021.
  * [20] M. Hatami, M. Leinonen, and M. Codreanu, “Aoi minimization in status update control with energy harvesting sensors,” _IEEE Trans. Wireless Commun._ , pp. 1–1, 2021.
  * [21] M. Sun, X. Xu, X. Qin, and P. Zhang, “Aoi-energy-aware uav-assisted data collection for iot networks: A deep reinforcement learning method,” _IEEE Internet Things J._ , pp. 1–1, 2021.
  * [22] H. Hu, K. Xiong, G. Qu, Q. Ni, P. Fan, and K. B. Letaief, “Aoi-minimal trajectory planning and data collection in uav-assisted wireless powered iot networks,” _IEEE Internet Things J._ , vol. 8, no. 2, pp. 1211–1223, 2021\.
  * [23] M. Emara, H. Elsawy, and G. Bauch, “A spatiotemporal model for peak aoi in uplink iot networks: Time versus event-triggered traffic,” _IEEE Internet of Things Journal_ , vol. 7, no. 8, pp. 6762–6777, 2020.
  * [24] L. Lyu, Y. Dai, N. Cheng, S. Zhu, X. Guan, B. Lin, and X. Shen, “Aoi-aware co-design of cooperative transmission and state estimation for marine iot systems,” _IEEE Internet of Things Journal_ , vol. 8, no. 10, pp. 7889–7901, 2021.
  * [25] X. Wang, C. Chen, J. He, S. Zhu, and X. Guan, “Aoi-aware control and communication co-design for industrial iot systems,” _IEEE Internet of Things Journal_ , vol. 8, no. 10, pp. 8464–8473, 2021.
  * [26] X. Hao, T. Yang, Y. Hu, H. Feng, and B. Hu, “An adaptive matching bridged resource allocation over correlated energy efficiency and aoi in cr-iot system,” _IEEE Transactions on Green Communications and Networking_ , vol. 6, no. 1, pp. 583–599, 2022.
  * [27] S. S. Yilmaz, B. Özbek, M. İlgüy, B. Okyere, L. Musavian, and J. Gonzalez, “User selection for noma based mimo with physical layer network coding in internet of things applications,” _IEEE Internet Things J._ , pp. 1–1, 2021.
  * [28] Z. Shi, H. Wang, Y. Fu, G. Yang, S. Ma, F. Hou, and T. A. Tsiftsis, “Zero-forcing-based downlink virtual mimo–noma communications in iot networks,” _IEEE Internet Things J._ , vol. 7, no. 4, pp. 2716–2737, 2020\.
  * [29] Q. Wang and Z. Wu, “Beamforming optimization and power allocation for user-centric mimo-noma iot networks,” _IEEE Access_ , vol. 9, pp. 339–348, 2021.
  * [30] L. Han, R. Liu, Z. Wang, X. Yue, and J. S. Thompson, “Millimeter-wave mimo-noma-based positioning system for internet-of-things applications,” _IEEE Internet Things J._ , vol. 7, no. 11, pp. 11 068–11 077, 2020.
  * [31] S. Zhang, L. Wang, H. Luo, X. Ma, and S. Zhou, “Aoi-delay tradeoff in mobile edge caching with freshness-aware content refreshing,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 8, pp. 5329–5342, 2021.
  * [32] S. Chinnadurai and D. Yoon, “Energy efficient mimo-noma hcn with iot for wireless communication systems,” in _2018 International Conference on Information and Communication Technology Convergence (ICTC)_ , 2018, pp. 856–859.
  * [33] J. Gao, X. Wang, R. Shen, and Y. Xu, “User clustering and power allocation for mmwave mimo-noma with iot devices,” in _2021 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2021, pp. 1–6.
  * [34] W. Feng, N. Zhao, S. Ao, J. Tang, X. Zhang, Y. Fu, D. K. C. So, and K.-K. Wong, “Joint 3d trajectory and power optimization for uav-aided mmwave mimo-noma networks,” _IEEE Transactions on Communications_ , vol. 69, no. 4, pp. 2346–2358, 2021.
  * [35] Z. Ding, L. Dai, and H. V. Poor, “Mimo-noma design for small packet transmission in the internet of things,” _IEEE Access_ , vol. 4, pp. 1393–1405, 2016.
  * [36] H. Huang, Y. Yang, Z. Ding, H. Wang, H. Sari, and F. Adachi, “Deep learning-based sum data rate and energy efficiency optimization for mimo-noma systems,” _IEEE Trans. Commun._ , vol. 19, no. 8, pp. 5373–5388, 2020\.
  * [37] G. Qiao, S. Leng, S. Maharjan, Y. Zhang, and N. Ansari, “Deep reinforcement learning for cooperative content caching in vehicular edge computing and networks,” _IEEE Internet Things J._ , vol. 7, no. 1, pp. 247–257, 2020\.
  * [38] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” _arXiv e-prints_ , p. arXiv:1509.02971, Sep. 2015\.
  * [39] D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller, “Deterministic policy gradient algorithms,” in _2014 International Conference on Machine Learning(ICML)_ , 2014, pp. 387–395.
  * [40] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , vol. 9, 2015.
  * [41] G. E. Uhlenbeck and L. S. Ornstein, “On the theory of the brownian motion,” _Revista Latinoamericana De Microbiología_ , vol. 15, no. 1, pp. 29–35, 1973.
  * [42] H. Q. Ngo, E. G. Larsson, and T. L. Marzetta, “Energy and spectral efficiency of very large multiuser mimo systems,” _IEEE Trans. Commun._ , vol. 61, no. 4, pp. 1436–1449, 2013.
  * [43] S. Wang, M. Chen, Z. Yang, C. Yin, W. Saad, S. Cui, and H. V. Poor, “Distributed reinforcement learning for age of information minimization in real-time iot systems,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 16, no. 3, pp. 501–515, 2022.
  * [44] S. Rahnamayan, H. R. Tizhoosh, and M. M. Salama, “A novel population initialization method for accelerating evolutionary algorithms,” _Computers & Mathematics with Applications_, vol. 53, no. 10, pp. 1605–1614, 2007.


11institutetext: Computer Vision Center & Computer Science Department
Universitat Autònoma de Barcelona, Spain
11email: {sbiswas, priba<EMAIL_ADDRESS>22institutetext: CVPR Unit, Indian
Statistical Institute, India
22email<EMAIL_ADDRESS>
# Graph-based Deep Generative Modelling for Document Layout Generation

Sanket Biswas 11 0000-0001-6648-8270 Pau Riba 11 0000-0002-4710-0864 Josep
Lladós 11 0000-0002-4533-4739 Umapada Pal 22 0000-0002-5426-2618

###### Abstract

One of the major prerequisites for any deep learning approach is the
availability of large-scale training data. When dealing with scanned document
images in real world scenarios, the principal information of its content is
stored in the layout itself. In this work, we have proposed an automated deep
generative model using Graph Neural Networks (GNNs) to generate synthetic data
with highly variable and plausible document layouts that can be used to train
document interpretation systems, in this case, specially in digital mailroom
applications. It is also the first graph-based approach for document layout
generation task experimented on administrative document images, in this case,
invoices.

###### Keywords:

Document Synthesis Graph Neural Networks Document Layout Generation.

##  1 Introduction

The variability and diversity of complex layouts and graphical entities in
digital mailroom documents prevent us from tackling document understanding
problems separately, and that such specificity has been a great barrier
towards deriving off-the-shelf document analysis solutions, usable by
nonspecialists. Apparently, OCR-based engines are the most widely recognized
products in this research community. For instance, imagine a business firm
having thousands of documents to process, analyze, and transform to carry out
day-to-day operations. Examples of such documents might include receipts,
invoices, forms, statements, contracts, and many more pieces of data, which
are highly unstructured or semi-structured, and it is essential to be able to
quickly analyze and understand the information embedded within the unevenly
structured data in these cases. In most of these Document Image Analysis and
Recognition(DIAR) applications, the document content has been broadly
classified into two structural entities: (1) physical and (2) logical
structural entities. While the physical structure describes the visual aspect
of the document by representing the specific objects and their mutual
positions, the logical structure assigns a definite semantic meaning to each
of these objects.

In recent times, deep CNN-based methods have tried to deduct the visual
differences between object classes: while the visual characteristics of
certain graphical elements (e.g., plots, charts, figures) differ conspicuously
from text elements, the same cannot be said for tables, where the major
differences from the surrounding content lie mostly stored in the layout
information and its context. Moreover, trying to train these deep CNN models
from scratch may be quite impractical due to the requirement of a large amount
of training examples and the need of precisely annotated document datasets,
which are scarcely available in the community. The key reason may be that most
of these documents (administrative documents, for example) contain sensitive
information (identity name, bank details, health information and so on) and
are not publicly released by government agencies or business firms to be used
in cloud services. Hence, as in many other applications requiring intensive
training, data augmentation through synthetic generation is a solution. In the
case of document structure recognition, there is an important need to generate
synthetic document layouts that can encode the structural information of the
real data and can be used during training to transfer enough knowledge to the
model. Patil et. al. [9] formulated this task as Document Layout Generation
(DLG), where they used a recursive neural network approach to map the
structured representation of semi-structured documents (in the form of tree-
level hierarchies) to a code representation, the space of which is
approximated by a Gaussian. New hierarchies representing plausible 2D document
layouts were sampled from such distributions. In this work, we tackle the
problem by encoding the structured hierarchies in the form of graph
representation.

Graphs possess the ability to represent two types of contextual knowledge: (1)
geometric/intrinsic, spatial structure of the document with positional
information of object categories like tables, and (2) semantic/extrinsic,
conceptual connections between the different object categories in a document.
Therefore, graphs emerge as a suitable model to represent document layouts.
The revolution of deep learning has also seen considerable progress in the
area of graph-based representation and learning. Graph Neural Networks (GNNs)
[14, 6] as deep learning approaches have extended the power of CNNs to non-
Euclidean geometries to capture long distance / different levels semantics
based on the relations between objects. GNN’s eventually learn a state
embedding that contains the neighborhood information for each node (which can
represent different entities or objects). The embedding is constructed at
different graph convolution layers, so it encodes the information of a
subgraph centered at a node. In the scenario of document interpretation, GNNs
embed a description of a local layout as a context of a given document
element. A recent application example was the detection of tables in case of
administrative document images [21, 20].

In summary, the main contributions of this work are as follows: (1) a novel
approach has been proposed for DLG task using GNN’s to generate synthetic data
applied to administrative invoice documents where we render data in the form
of diverse graphs that can actually match the structural characteristics of
the target data. (2) The proposed graph-based generative modelling for such
administrative documents also helps to invoke anonymity for the sensitive
information (e.g. names, addresses, billing information, total amount etc.) it
might contain in the document images. As shown in Fig. 1, the nodes in the
graph represent the different entities (e.g. header, table, supplier etc.) in
the document, while the edges represent the visibility relations (horizontal
or vertical) between the neighbouring nodes. (3) All experiments of our model
have been performed on administrative invoices collection from the RVL-CDIP
[11] dataset. As a result, a new synthetic invoice dataset has been created
for augmenting the train data during table detection and layout analysis
tasks.

The rest of this paper is organized as follows. Section 2 provides a review of
the relevant state of the art. In section 3 we describe the main contribution
of our work. Section 4 provides experimental validation with some relevant
results of our proposed approach, both qualitatively and quantitatively.
Finally, Section 5 concludes the work throwing some light on its future scope
and benefits.

##  2 Related Work

Figure 1: Graph representation of the structure of an invoice image

###  2.1 Geometric Deep Learning

Geometric deep learning [6, 14] has emerged as an extension of deep learning
models to non-Euclidean domains, such as graphs and manifolds. To refer to
neural networks applied to graph-structured data, the term Graph Neural
Networks [23] was coined.

The GNN methods help to learn representations at the node, edge and graph
level considering the underlying topological information. Based on the
fundamental architecture, GNN methods can be aptly divided into two
categories: spatial and spectral methods. Spatial methods extend the idea of
Convolutional Neural Networks (CNNs) for images and define a set of operations
involving the local neighbourhood to compute a new representation [7, 17]. On
the other hand, spectral methods use the knowledge of spectral graph theory
[24] and consider graph Laplacians for defining convolution operations in
graph domain [6, 14]. Gilmer et al. [10] generalized both the domains of GNN,
and defined their approach in terms of a Neural Message Passing (NMP)
pipeline. These fundamental architectures have been further extended to new
tasks involving graphs, such as the generative variational graph autoencoder
[15], learning graph edit distance between a pair of graphs [22], graph
matching [28], etc.

###  2.2 Document Layout Generation

The study and analysis of the structural properties and relations between
entities in documents is a fundamental challenge in the field of information
retrieval. Although local tasks like the Optical Character Recognition (OCR)
have been addressed with a considerably high model performance, the global and
highly variable nature of document layouts has made their analysis some what
more ambiguous. Previous works on structural document analysis mostly relied
on the different kinds of specifically devised methods and applications [1, 4,
12, 19]. Recent works have shown that deep learning based approaches have
significantly improved the performance of these models in quality. A very
standard approach in this regard was proposed by Yang et al. [26] which uses a
joint visual and textual representation in a multimodal way of understanding,
viewing the layout analysis as a pixel-wise segmentation task. But such modern
deep learning based approaches typically require a very heavy amount of high-
quality training data, that often calls for suitable methods to synthetically
generate documents with real-looking layout [16] and content [18]. Our work
actually focuses on the direction of research on synthetic layout generation,
showing that our generated synthetic data can be extremely beneficial to
augment training data for document analysis tasks.

Preserving the reliable representation of layouts has shown to be very useful
in various graphical design contexts, which typically involve highly
structured and content-rich objects. One such recent intuitive understanding
was established by Li et al. [16] in their LayoutGAN, which aims to generate
realistic document layouts using Generative Adversarial Networks (GANs) with a
wireframe rendering layer. Zheng et. al. [29] used a GAN-based approach to
generate document layouts but their work focused mainly on content aware
generation, that primarily uses the content of the document as an additional
prior. Biswas et. al. [2] devised a generative GAN-based model to synthesize
realistic document images, guided by a spatial layout(bounding boxes with
object categories) given as a reference by the user. However to use a more
highly structured object generation, it is very important to focus operate on
the low dimensional vectors unlike CNN’s. Hence, in the most recent
literature, Patil et. al. [9] has exploited this highly structured positional
information along with content to generate document layouts. They have used
recursive neural networks which operate on the low dimensional vectors and
employ two-layer perceptrons to merge any two vectors, which make them
computationally cheaper and help them train with fewer samples. The recursive
neural networks are coupled with Variational Autoencoders (VAEs) in their
resulting model architecture and provides state-of-the-art results for
generating synthetic layouts for 2D documents. They have also introduced a
novel metric for measuring document similarity, called DocSim, and used this
metric to show the novelty and diversity of the generated layouts.

Using geometric relations between the different entities in documents can
actually help to preserve the structural information along with the content as
seen in the work by Riba et. al.[21] on table detection in invoice documents
using GNNs. Figure 1 clearly illustrates how they have used graph modelling
for document images to capture the geometrical structure of an invoice and
using this knowledge can help us to generate more realistic synthetic samples
for training. In this work we have used a similar kind of graph modelling for
exploiting the structural information of an invoice image. Carbonell et.
al.[5] also used GNNs for recognition of structural components like named
entities in semi-structured administrative documents. Traditional generative
models for graphs [25] are usually hand‐crafted to model a particular family
of graphs, and thus they do not have the capacity to directly learn the
generative model from observed data. To find a solution, one such graph-based
generative model using GNNs was proposed by You et. al. [27] on molecular data
generation. They used sequential generation with Recurrent Neural Networks
(RNNs) on top of graph based representations and get state-of-the-art results
on molecular data generation. But there has not been any substantial work in
the literature which has applied such graph-based generative models for
document layout analysis tasks. In this context, it is indeed a challenging
problem which we tackle in this work. As case study, we will work in the
context of administrative documents, primarily focusing on invoices. Automated
generation of synthetic document layouts will allow us to train document
interpretation systems in a more efficient way for all kinds of document
layout analysis tasks.

##  3 Method

Figure 2: The Graph Generation Process: Given figure illustrates the graph
generation process during inference time. The Node-level RNN update encodes
the graph hidden state $h$ , updated by the predicted adjacency vector
$S_{i}^{\pi}$ for every node. The Edge-level RNN updates the sequence of edges
when every new node is added. Figure 3: Qualitative analysis of our generative
model with figures (a), (c) and (e) representing the test graphs from real
invoice data and (b), (d) and (f) representing the generated graphs from our
model.

In this work, we have explored a new research direction in the DIAR domain
using the application of GNN. A hierarchical and scalable framework has been
designed and implemented to exploit highly powerful graph representations in
semi-structured administrative documents like invoices. Every document image
has been modelled as a visibility graph which is fed to our generative model
to synthesize meaningful document layouts. Figure 1 depicts the structure of
an invoice document and how it has been modelled as a visibility graph. We
considered a document graph whose nodes are graphical or named entities such
as tables, figures, header, date, etc. while the edges represent their spatial
relationships. We aim to learn a distribution $p(G)$ over an undirected graph
$G=(V,E)$ defined by the node set $V=\left\\{v_{1},\ldots,v_{n}\right\\}$ and
edge set $E=\left\\{\left(v_{i},v_{j}\right)\mid v_{i},v_{j}\in V\right\\}$
that has a node ordering $\pi$ to map nodes to rows/columns of adjacency
matrix $A^{\pi}$. This node ordering scheme has been adapted to enhance time
efficiency of our training model. An adjacency matrix $A_{i,j}^{\pi}$ under a
node ordering $\pi$ can be represented as
$A_{i,j}^{\pi}=\mathbb{1}\left[\left(\pi\left(v_{i}\right),\pi\left(v_{j}\right)\right)\in
E\right]$. So,in this work, we have proposed a graph generation framework
applied in context to document images, that learns to generate realistic
graphs by training on a representative set of graphs known as visibility
graphs modelled from documents.

The main idea is to represent graphs of different node orderings as sequences,
and then build a generative model on top of these sequences. As illustrated in
the graph generation framework in Fig. 2, we decomposed the entire process
into two parts: one that generates a sequence of nodes (Node-level update) and
then another process that generates a sequence of edges for every new
generated node (Edge-level update) which will be explained in more detail in
the below subsections in a step-wise manner.

###  3.1 Graph to Sequence Mapping

We aim to learn a distribution $p_{model}(G)$ over graphs , based on a set of
observed graphs $G={(G_{1},...,G_{s})}$, sampled from a data distribution
$p(G)$, where each graph, may have a different set of nodes and edges. During
training time instead of learning $p(G)$ directly, whose sample space is
really complex to define, we instead sample a node ordering $\pi$ to get a set
of sequences $S^{\pi}$ as our observations and learn $p(S^{\pi})$ instead.
This help us to learn a model autoregressively due to the $S^{\pi}$ . At
inference time, we can simply sample G directly by computing $p(G)$ without
this mapping. The mapping function $f_{S}$ from graphs to sequences, for a
graph $G\sim p(G)$ with $n$ nodes under node ordering $\pi$ can be determined
in equation 1.

$\begin{split}S^{\pi}=f_{S}(G,\pi)=\left(S_{1}^{\pi},\ldots,S_{n}^{\pi}\right)\end{split}$
(1)

Every element $S_{i}^{\pi}$ is actually an adjacency vector that represents
the edges between the present node $\pi(v_{i})$ and previous nodes
$\pi(v_{j})$ already in graph. This can be further represented by the equation
2.

$\begin{split}S_{i}^{\pi}=\left(A_{1,i}^{\pi},\ldots,A_{i-1,i}^{\pi}\right)^{T},\forall
i\in\\{2,3,4\ldots,n\\}\end{split}$ (2)

###  3.2 GRNN Framework

As a result of the graph to sequence mapping, our next step would be to
generate the adjacency matrix of a graph G by generating these adjacency
vectors $A_{i,i}^{\pi}$ of each node in a step by step sequential process.
This can output different networks with variable number of nodes, while
preserving the important topological properties of the generated graph. While
transforming the learning distribution from $p(G)$ to $p(S^{\pi})$, we can
further decompose $p(S^{\pi})$ as the product of conditional distributions
over the elements due to its sequential nature as shown in equation 3.

$\begin{split}p\left(S^{\pi}\right)=\prod_{i=1}^{n+1}p\left(S_{i}^{\pi}\mid
S_{1}^{\pi},\ldots,S_{i-1}^{\pi}\right)\end{split}$ (3)

Now to model this still complex distribution, we used recurrent neural
networks (RNNs) that consist of a state-transition function and an output-
function as shown in equations 4 and 5:

$\begin{split}h_{i}=f_{\text{trans
}}\left(h_{i-1},S_{i-1}^{\pi}\right)\end{split}$ (4)

$\begin{split}\theta_{i}=f_{\text{out }}\left(h_{i}\right)\end{split}$ (5)

where $h_{i}$ is a vector that encodes the updated generated graph
information, $S_{i-1}^{\pi}$ is the adjacency vector for the last updated node
$i-1$ and $\theta_{i}$ denotes the distribution of next node’s adjacency
vector i.e. $S_{i}^{\pi}\sim{P}_{\theta_{i}}$. So theoretically, the proposed
Graph Recurrent Neural Network (GRNN) framework utilizes a hierarchical RNN as
shown in figure 2, where the first (i.e. graph-level) RNN generates nodes and
update the state of the graph. The second RNN (i.e. edge-level) generates the
edges of a given node. To achieve a scalable modeling, we let these networks
share their weights across all the time steps $i$ during the training phase.

###  3.3 Learning via Breadth-First Search

A great insight in our proposed method is rather than learning to generate
graphs with using the Breadth-First Search (BFS) node orderings, instead of
random node permutations. The BFS function takes a random permutation $\pi$ as
input, picks $\pi(v_{1})$ as starting node and appends the node neighbours
into the BFS queue in an order defined by $\pi$. The modified equation for
mapping function from graphs to sequences can rewritten as shown in equation
6.

$S^{\pi}=f_{S}(G,\operatorname{BFS}(G,\pi))$ (6)

This technique helps the model to be trained on all possible BFS orderings,
instead of all possible node permutations. As the BFS function is
deterministic in nature and many-to-one, i.e. one same ordering can eventually
map multiple permutations, it reduces number of sequences we need to consider.
It also makes the learning much simpler by reducing the number of edge
predictions and adding possible edges only for the nodes that are considered
in the BFS queue itself.

##  4 Experimental Validation

For our experimental validation, we have used the RVL-CDIP dataset[11]. In
particular, the invoice subset has been split into 70 and 30 percent of the
samples for training and evaluation respectively. Additionally, two extra
datasets have been evaluated, namely, Protein [3] and Community[13], to
evaluate the robustness of our method on other domains.

###  4.1 Datasets

####  4.1.1 RVL-CDIP Invoices [11].

The RVL-CDIP (Ryerson Vision Lab Complex Document Information Processing) is a
well-known document information database containing 16 classes of documents
with about 400,000 images in grayscale. For evaluating our synthetic graph
generation framework, we chose the 518 images from the Invoice class,
annotated with 5 different regions belonging to class header, table, address
and so on. Here each invoice page is represented by a graph, with the nodes
corresponding to the entities of different class in the invoice.

####  4.1.2 Protein [3].

918 protein graphs have been used with every node representing an amino acid
and two nodes are connected if they are at a distance threshold of 6 Angstrom.

####  4.1.3 Community [13].

The community dataset contains a collection of 500 two-community graphs, where
each community generated by Erdos-Renyi model (E-R) [8], represents a node in
the graph.

###  4.2 Data Preparation for Graph Representation

In this stage, given the image of a document, we apply physical layout
techniques to detect the graphical regions. Given an invoice document, we
represent each detected entity corresponding to a 7-dimensional vector
containing the position of the bounding boxes and the histogram of its content
(numbers, alphabets or symbol). This encoded information will be used to
generate a visibility graph in order to represent the structural information
of the document. We consider $G=(V,E)$ to be a visibility graph. The set of
edges $E$ represent visibility relations between nodes. Two entities are said
to be connected with an edge if and only if the bounding boxes are vertically
or horizontally visible, i.e. a straight horizontal or vertical line can be
traced between the bounding box of two entities without crossing any other.
Also, long edges covering more than a quarter of the page height are
discarded. An example of a visibility graph sample with corresponding node
embedding is shown in Figure 1.

###  4.3 Training setup for Graph Recurrent Neural Network

Once the document has been processed and visibility graph has been generated,
we feed them to our Graph Recurrent Neural Network (GRNN) model framework with
the 7-dimensional node input space to get projected to a higher order space
encoding with individual node features preserving the structural content
information of the document. The graph-level RNN used in our work uses 4
layered GRU with 128 dimensional hidden state. To output the adjacency vector
prediction, the edge-level RNN uses 4 layered GRU cells with 16 hidden
dimensional state. To get the predicted adjacency vector in the output, the
edge-level RNN maps the 16 dimensional hidden state to a 8 dimensional vector
through a MLP and ReLU activation, then another MLP maps the vector to a
scalar with sigmoid activation. We initialize the the edge-level RNN by the
output of the graph-level RNN when generating the start of sequences
$S_{i-1}^{\pi}$. We use the highest layer hidden state of the graph-level RNN
to initialize with a linear layer to match the dimensionality. During the
training time, ground truth has been used rather than the model’s own
predictions. During the inference time, the model is allowed to use its own
predicted graph samples at each time step to generate a graph. The Adam
Optimizer has been used for minibatch size of 32. We set the learning rate to
be 0.001 which is decayed by 0.2 at every 100th epoch in all experiments.

###  4.4 Evaluation Schema

The evaluation of the quality of generated graphs is quite hard to estimate. A
fair comparison between the test graph and generated graph is required. By
visualizing the sets of test graphs and the generated graphs, a fair
qualitative comparison can be done. From Figure 3 we can infer a qualitative
comparison between the test and generated samples.

For a quantitative evaluation scheme, we have used the Maximum Mean
Discrepancy (MMD) measures to calculate the distance between the two sets of
graphs (in this case, the test sample and the generated sample). In our
experiments, the derived MMD scores between the graphs have been calculated
for degree and clustering coefficient distributions, along with the average
orbit count statistics as shown in Table 1. The lower the scores, the better
the real structure of the entities has been preserved.

###  4.5 Experiments on Administrative Invoice Documents

Experiments on the subset of administrative document (invoices) taken from
RVL-CDIP[11] has been conducted and we report the first baseline for document
layout generation using a Graph Neural Network(GNN) framework.

As illustrated in Figure 3, we illustrate some of the qualitative results with
the document graphs that we generated from our proposed GRNN model. The
visualizations of the graph samples suggest that the generated graphs visually
preserve the appearance of the reference one, so the model roughly learns to
preserve both syntactic and semantic information for different entities.
Eventually, we can create synthetic samples of invoices by generating more and
more graph samples and also providing them during the inference time. Since
this is the first baseline approach to use graph generative models in document
datasets.

However, Table 1 depicts the quantitative results we obtained for RVL-CDIP
Invoice dataset and we compared our model performance with some molecular
datasets like Protein [3] and Community [13] present in the graph literature.
Results clearly show that there is a huge room for improvement in the graph
generative framework for documents when compared to the performance in the
above mentioned benchmark molecular datasets. The ‘tables’ entity is a regular
structured entity and our model works well for generating table classes in
realistic positions. But the title, date and other entities in administrative
documents do not contain uniform information about its structural relations
and its quite difficult for the model to learn those semantic content.

Table 1: Summary of the final model results for Document Layout Generation Dataset | Degree ($\downarrow$) | Clustering ($\downarrow$) | Orbit ($\downarrow$)
---|---|---|---
Protein [3] | 0.014 | 0.002 | 0.039
Community [13] | 0.034 | 0.102 | 0.037
RVL-CDIP Invoices [11] | 0.373 | 0.166 | 0.188

##  5 Conclusion

In this work, we have presented a novel approach to automatically synthesize
document layouts structures. The proposed method is able to understand the
complex interactions among the different layout components and generate
plausible layouts for 2D documents. The graph-based generative approach also
explores the power of GNN’s towards the learning and generation of complex
structured layouts for administrative invoices as a case study.

The future scope of this work will be mainly focused on two research lines.
Firstly, there is a requirement for a more efficient evaluation of
synthetically generated layouts when compared to real document layout samples
both quantitatively and qualitatively. Secondly, exploiting this generated
layout samples for supervision purposes can enhance the performance on well-
defined tasks such as table detection or document layout analysis.

## Acknowledgment

This work has been partially supported by the Spanish projects
RTI2018-095645-B-C21, and FCT-19-15244, and the Catalan projects
2017-SGR-1783, the CERCA Program / Generalitat de Catalunya and PhD
Scholarship from AGAUR (2021FIB-10010). We are also indebted to Dr. Joan Mas
Romeu for all the help and assistance provided during the data preparation
stage for the experiments.

## References

  * [1] Baird, H.S., Bunke, H., Yamamoto, K.: Structured document image analysis. Springer Science & Business Media (2012)
  * [2] Biswas, S., Riba, P., Lladós, J., Pal, U.: Docsynth: A layout guided approach for controllable document image synthesis. In: International Conference on Document Analysis and Recognition (ICDAR) (2021)
  * [3] Borgwardt, K.M., Ong, C.S., Schönauer, S., Vishwanathan, S., Smola, A.J., Kriegel, H.P.: Protein function prediction via graph kernels. Bioinformatics 21(suppl_1), i47–i56 (2005)
  * [4] Breuel, T.M.: High performance document layout analysis. In: Proceedings of the Symposium on Document Image Understanding Technology. pp. 209–218 (2003)
  * [5] Carbonell, M., Riba, P., Villegas, M., Fornés, A., Lladós, J.: Named entity recognition and relation extraction with graph neural networks in semi structured documents. In: 2020 25th International Conference on Pattern Recognition (ICPR). pp. 9622–9627. IEEE (2021)
  * [6] Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in neural information processing systems. pp. 3844–3852 (2016)
  * [7] Duvenaud, D.K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru-Guzik, A., Adams, R.P.: Convolutional networks on graphs for learning molecular fingerprints. In: Advances in neural information processing systems (2015)
  * [8] Erdős, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5(1), 17–60 (1960)
  * [9] Gadi Patil, A., Ben-Eliezer, O., Perel, O., Averbuch-Elor, H.: Read: Recursive autoencoders for document layout generation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. pp. 544–545 (2020)
  * [10] Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.01212 (2017)
  * [11] Harley, A.W., Ufkes, A., Derpanis, K.G.: Evaluation of deep convolutional nets for document image classification and retrieval. In: 2015 13th International Conference on Document Analysis and Recognition (ICDAR). pp. 991–995. IEEE (2015)
  * [12] Kasturi, R., O’gorman, L., Govindaraju, V.: Document image analysis: A primer. Sadhana 27(1), 3–22 (2002)
  * [13] Kim, J., Lee, J.G.: Community detection in multi-layer graphs: A survey. ACM SIGMOD Record 44(3), 37–48 (2015)
  * [14] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)
  * [15] Kipf, T.N., Welling, M.: Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016)
  * [16] Li, J., Yang, J., Hertzmann, A., Zhang, J., Xu, T.: Layoutgan: Generating graphic layouts with wireframe discriminators. arXiv preprint arXiv:1901.06767 (2019)
  * [17] Li, Y., Tarlow, D., Brockschmidt, M., Zemel, R.: Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493 (2015)
  * [18] Liu, T.F., Craft, M., Situ, J., Yumer, E., Mech, R., Kumar, R.: Learning design semantics for mobile apps. In: Proceedings of the 31st Annual ACM Symposium on User Interface Software and Technology (2018)
  * [19] O’Gorman, L.: The document spectrum for page layout analysis. IEEE Transactions on pattern analysis and machine intelligence 15(11), 1162–1173 (1993)
  * [20] Qasim, S.R., Mahmood, H., Shafait, F.: Rethinking table recognition using graph neural networks. In: 2019 International Conference on Document Analysis and Recognition (ICDAR). pp. 142–147. IEEE (2019)
  * [21] Riba, P., Dutta, A., Goldmann, L., Fornés, A., Ramos, O., Lladós, J.: Table detection in invoice documents by graph neural networks. In: 2019 International Conference on Document Analysis and Recognition (ICDAR) (2019)
  * [22] Riba, P., Fischer, A., Lladós, J., Fornés, A.: Learning graph distances with message passing neural networks. In: 2018 24th International Conference on Pattern Recognition (ICPR) (2018)
  * [23] Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: The graph neural network model. IEEE Transactions on Neural Networks (2008)
  * [24] Shuman, D.I., Narang, S.K., Frossard, P., Ortega, A., Vandergheynst, P.: The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine (2013)
  * [25] White, D., Wilson, R.C.: Spectral generative models for graphs. In: 14th International Conference on Image Analysis and Processing (ICIAP 2007). pp. 35–42. IEEE (2007)
  * [26] Yang, X., Yumer, E., Asente, P., Kraley, M., Kifer, D., Lee Giles, C.: Learning to extract semantic structure from documents using multimodal fully convolutional neural networks. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 5315–5324 (2017)
  * [27] You, J., Ying, R., Ren, X., Hamilton, W.L., Leskovec, J.: Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint arXiv:1802.08773 (2018)
  * [28] Zanfir, A., Sminchisescu, C.: Deep learning of graph matching. In: Proceedings of the IEEE conference on computer vision and pattern recognition (2018)
  * [29] Zheng, X., Qiao, X., Cao, Y., Lau, R.W.: Content-aware generative modeling of graphic design layouts. ACM Transactions on Graphics (TOG) 38(4), 1–15 (2019)