# Age of Information Aware VNF Scheduling in Industrial IoT Using Deep
Reinforcement Learning ††thanks: Mohammad Akbari is with Communication
Department, ICT Research Institute, Tehran, Iran (e-mail:
m.akbari@itrc.ac.ir)††thanks: Mohammad Reza Abedi is with the Department of
Electrical Engineering, Tarbiat Modares University, Tehran, Iran (e-mail:
<EMAIL_ADDRESS>††thanks: Roghayeh Joda is with
Communication Department, ICT Research Institute, Tehran, Iran (e-mail:
r.joda@itrc.ac.ir). She is currently a visiting researcher at the School of
Electrical Engineering and Computer Science, University of Ottawa, Ottawa K1N
6N5, Canada (e-mail<EMAIL_ADDRESS>††thanks: Mohsen Pourghasemian is
Research Assistant at the Department of Electrical Engineering, Tarbiat
Modares University, Tehran, Iran.††thanks: N. Mokari is with the Department of
Electrical Engineering, Tarbiat Modares University, Tehran, Iran (e-mail:
nader.mokari@modares.ac.ir). The work of Nader Mokari, Mohammad Reza Abedi,
and Mohsen Pourghasemian was supported by the Iran National Science Foundation
under Grant No. 98025206.††thanks: Melike Erol-Kantarci is with the School of
Electrical Engineering and Computer Science, University of Ottawa, Ottawa K1N
6N5, Canada (e-mail<EMAIL_ADDRESS>
Mohammad Akbari, Mohammad Reza Abedi, Roghayeh Joda, Member, IEEE, Mohsen
Pourghasemian, Nader Mokari, Senior Member, IEEE, and Melike Erol-Kantarci,
Senior Member, IEEE

###### Abstract

In delay-sensitive industrial internet of things (IIoT) applications, the age
of information (AoI) is employed to characterize the freshness of information.
Meanwhile, the emerging network function virtualization provides flexibility
and agility for service providers to deliver a given network service using a
sequence of virtual network functions (VNFs). However, suitable VNF placement
and scheduling in these schemes is NP-hard and finding a globally optimal
solution by traditional approaches is complex. Recently, deep reinforcement
learning (DRL) has appeared as a viable way to solve such problems. In this
paper, we first utilize single agent low-complex compound action actor-critic
RL to cover both discrete and continuous actions and jointly minimize VNF cost
and AoI in terms of network resources under end-to-end Quality of Service
constraints. To surmount the single-agent capacity limitation for learning, we
then extend our solution to a multi-agent DRL scheme in which agents
collaborate with each other. Simulation results demonstrate that single-agent
schemes significantly outperform the greedy algorithm in terms of average
network cost and AoI. Moreover, multi-agent solution decreases the average
cost by dividing the tasks between the agents. However, it needs more
iterations to be learned due to the requirement on the agents’ collaboration.

###### Index Terms:

Industrial Internet of Things, Network Function Virtualization, Age of
information, Deep Reinforcement Learning, Compound actions, Multi-agent

##  I Introduction

###  I-A Background and Motivation

####  I-A1 Industrial Internet of Things

Future applications of Industrial Internet of things (IIoT) such as autonomous
cars, virtual reality, and traffic control will increasingly focus on the
exchange of delay-sensitive information for monitoring and control. In the
application of virtual reality, the user’s position and service information
must be exchanged immediately between the server and users [1, 2, 3].
Therefore, in such applications, information must be kept fresh and outdated
information is not valuable.

####  I-A2 Age of Information

Traditional metrics, such as packet delay and inter-delivery times used for
real-time applications, are not sufficient to measure the freshness of
information at the destination. Hence, the age of information (AoI) is
considered as a criterion for evaluating the freshness of information received
at the destination [2, 4]. AoI increases linearly over time until next fresh
packet is arrived, at which point AoI takes the value of the end-to-end packet
delay [5]. AoI can be used to characterize the information freshness since it
is a powerful metric to capture the randomness of state updates. Meanwhile,
the management of distributed, intelligent, and autonomous machines in a
reliable and robust manner is the use of Network Function Virtualization
(NFV). The NFV virtualizes network services and abstracts them from any
dedicated hardware. It enables rapid service provisioning and chaining in IIoT
[6].

####  I-A3 Network Function Virtualization

NFV is an emerging network architecture which gives flexibility and agility to
networks by realizing virtual network functions (VNFs) in software and
adaptively placing virtualized services on physical resources. To provide an
end-to-end service between two hosts, multiple VNFs might be used in sequence
each of which deliver a specific network function. Suitable placements of VNFs
and their routing over the available NFV infrastructure are important problems
and must optimally be determined. Moreover, VNF placement should be
dynamically adjusted to adopt to the network traffic and load changes over
time [7]. NFV significantly improves scalability of networks, and at the same
time enhances the robustness and agility in managing network components and
makes them easy to deploy. In addition to these advantages of implementing
network functions as VNFs, there is a tradeoff between flexible management and
the imposed delay in placement and scheduling process of VNFs in emerging
dense and complex networks composed of several VNFs. In IIoT applications,
this issue is much more crucial [8, 6, 9]. In our proposed IIoT NFV-enabled
model, we address the robust and flexible management of very delay sensitive
applications by distributing the functions of these applications into several
virtualized servers. Accordingly, more delay will be imposed to the network by
VNF placement and scheduling of the service functions. Therefore, AoI as a
comprehensive metric for quantifying the freshness of information in an end-
to-end manner, when it is formulated correctly to reflect all the components
affecting information aging, can support the restrict delay requirements of
IIoT applications in an efficient manner.

####  I-A4 Machine Learning

The VNF placement and routing can be expressed as a mathematical optimization
problem with a constraint set that should be satisfied to meet the network
infrastructure’s restrictions and the service requirements. Nevertheless, such
problems are NP-hard and finding globally optimal solutions is very difficult,
especially in large scale networks [10, 11]. Today, deep reinforcement
learning (DRL) appears as a viable way to solve NP-hard and non-convex
problems like VNF placement. However, these methods suffer from capacity
limitation for learning, i.e., single-agent methods [12, 13], and can only
handle the environment with only discrete actions (like Deep Q network (DQN))
or continuous ones (like Deep Deterministic Policy Gradient)[14, 15].
Accordingly, some DRL methods are needed in order to handle the network
environment with both discrete and continuous actions, while have less
capacity limitation for learning to satisfy the network constraint.

Notations: Matrices and vectors are denoted by Bold upper-case characters and
bold lower-case characters, respectively. $|\mathcal{A}|$ is the cardinality
of a set $\mathcal{A}$. $\mathbb{E}[X]$ indicates expected value of $X$.

##  II Related Works

Generally speaking, traditional specific-purpose network architectures cannot
provide enough flexibility to adapt to future changes in capacity requirement
and very dynamic interconnection of IIoT services and devices. To overcome
these problems, NFV can provide efficient resource management and flexible
network architecture for IoT [16, 17]. Using this architecture, communication
service providers (CSPs) can provide dynamic and adaptive service function
chain (SFC) embedding schemes to handle the massive flows of IIoT users in
NFV-enabled IIoT networks [18, 19].

####  II-1 VNF Placement and Scheduling

In the literature, the authors propose several solutions for VNF placement and
the SFC mapping. In [20], the authors employ an efficient coordination
algorithm to allocate VNFs into physical networks and route between the VNFs
based on reinforcement learning (RL). Although their proposed model adaptively
changes the VNF placement based on the network condition, they do not focus on
the QoS parameters as well as AoI and the VNF placement cost. In [21], VNF
placement is formulated as an integer linear program and the main goal is to
minimize cost of service providers while guaranteeing the QoS requirements.
However, they do not consider joint function placement and VNF scheduling in
the NFV enabled networks. In [22], a heuristic algorithm is proposed for
dynamic placement and scheduling of VNFs and the goal is to minimize the
global cost. However, the meta-heuristic search based method cannot optimally
handle the stochastic environment with restrict latency requirement since
these environments are NP-hard and non-convex and cannot be solved by general
Integer Linear Programming (ILP). The VNF Forward Graph Embedding problem is
considered in [14], in which the goal is to efficiently map a set of network
service VNFs on the physical infrastructure to maximize the remaining
resources, while minimizing the power consumption and guaranteeing a specific
QoS to each user. They focus on the maximum tolerable latency for services,
rather to consider minimizing that. A DRL approach is used in [15] to jointly
minimize the operational cost and maximize the total network throughput for
NFV-based networks. However, there are a few works that consider the
adaptability of NFV placement and service scheduling in NFV-based IIoT
networks.

####  II-2 Age of Information

Most previous works deal with minimizing the power consumption, minimizing
delay [5], minimizing service scheduling cost or maximizing network throughput
of VNF placement and service chaining [5]. However, in most IoT applications
such as vehicles, UAVs, health, and sensor monitoring, the real-time updates
and fresh data are very important. Therefore, AoI can be a useful metric to
measure the freshness of such information [23, 24]. In [25], the authors
propose a DRL-based algorithm to determine UAVs trajectories during sensing
and transmission while guaranteeing the freshness of the sensory data.
However, this work is not directly related to VNF placement, hence does not
address the issues of VNF placement. In [2, 4], joint optimal uniform/non-
uniform sampling and updating is designed to minimize the average AoI for IoT
applications with respect to energy constraint of IIoT devices. Although their
proposed model for IIoT network mitigates AoI of the users, considering VNF
placement for such a network to decompose network services in order to handle
very low latency services would be difficult.
In the IIoT systems, the large amounts of data generated by smart devices are
transmitted over wireless communication networks for analysis and control. To
meet the high reliability and real-time demands of IIoT applications, rapid,
and frequent data transmission is needed and its performance depends on
freshness of status updates [8]. In [9], the authors consider an IIoT system,
in which randomly generated status updates are sent to the destination through
an unreliable channel. Their aim is to minimize the long-term average AoI
subject to the average transmission power constraint at the source. In [26],
the authors consider a marine IoT system with multiple unmanned surface
vehicles (USVs) to monitor the marine environment, while the collected data by
sensors on USVs is used to achieve the ubiquitous situation awareness of
marine environment. For this purpose, the authors use AoI metric to satisfy
freshness of data. The real-time monitoring scenario is also considered in
[27], where the collected data is transmitted to the controller and the goal
is to minimize the network energy consumption given the constraint on AoI
value.

Motivated by these considerations, in this paper we propose a new data flow
scheduling and VNF placement framework in IIoT networks, in order to minimize
the average AoI of the end users as well as transmission and VNF placement
cost. Different from the previous works, focusing on the services latency as
well as network and radio resource limitation, our proposed model addresses
the IIoT challenges more conveniently. More precisely, we formulate the VNF
placement, subcarrier and transmit power allocation as a NP-hard and non-
convex problem, aiming to minimize the average AoI in IIoT network, then we
utilize DRL method to solve our problem. However, the environment of our
proposed model consists of both discrete and continuous actions as VNF
placement, subcarrier and transmit power allocation. On the other hand, the
state-of-the-art DRL methods like DQN and DDPG can only handle discrete and
continuous actions, respectively. Therefore, we apply compound action actor
critic (CA2C) DRL method which supports both discrete and continuous actions,
simultaneously. Finally, we extend our DRL solution to multi-agent method in
which multiple agents are cooperating with each other to manage the diverse
traffic request in IIoT network with very restrict delay requirement.

###  II-A Our Contributions and Works

To the best of our knowledge, our work is the first study to propose a novel
AI-based solution to joint radio and NFV cost and AoI minimization problem in
IIoT networks by using compound action actor critic algorithm to handle both
discrete and continuous optimization variables such as power allocation,
subcarrier assignment, and VNF placement. The main contributions of our paper
are summarized as follows:

  * •

We propose a novel framework for the optimal end-to-end data flow scheduling
in IIoT applications that jointly minimizes AoI at the destination and total
cost of the network.

  * •

We formulate a VNF placement and scheduling optimization problem in an IIoT
network under multiple important constraints such as power budget, bandwidth,
QoS and AoI metric.

  * •

Since our formulated problem is NP-hard and consists of discrete and
continuous actions, we employ a single agent (SA) compound-action actor-critic
(CA2C) approach which can handle both discrete and continuous actions and
achieve near optimal solution for VNF placement and scheduling under the
network and user’s constraints.

  * •

Furthermore, to overcome the single-agent capacity limitation for learning, we
propose a multi-agent DRL method as (MA-CA2C) in which there are multiple
agents that are collaborating with each other to satisfy the network
constraints.

  * •

To show the effectiveness of our proposed solution, we conduct simulation
using TensorFlow. The simulation results show that the VNF placement and
scheduling policy that is obtained by applying the proposed approach provides
significant improvement in terms of total network cost and data freshness
compared to the Greedy approaches.

The remainder of this paper is organized as follows: Section II and Section
III describe system and AoI models used in this paper. Section IV presents
problem definition and formulation. Section V presents the baseline DRL
algorithms and the proposed MA-CA2C method. Section VI describes the
computational complexity and convergence analysis of the proposed solution.
The performance evaluation of the proposed scheme is demonstrated in Section
VII. Finally, conclusions of this paper are discussed in Section VIII.

##  III System Model

###  III-A System Model Definition

We consider a real-time IIoT system in which a set of IIoT devices collect
information from a physical process and send packets to destination users. A
hypervisor allows multiple virtual machines to run on physical layer by
virtually sharing their resources, like memory and processing. We consider an
SDN controller to manage flow control to improve network management and
application performance. $\mathcal{M}$ indicates the set of $M$ IIoT devices.
We model a virtual network as a directed graph
$\mathcal{G}(\mathcal{N},\mathcal{L})$, where $\mathcal{N}$ is the set of
virtual nodes and $\mathcal{L}$ is the set of virtual links, as shown in Fig.
1. The number of virtual nodes and virtual links in the network are denoted by
$|\mathcal{N}|=N$ and $|\mathcal{L}|=L$, respectively. The virtual nodes set
consists of source virtual node set, $\mathcal{N}^{\text{S}}$, middle virtual
node set, $\mathcal{N}^{\text{R}}$, and destination virtual node set,
$\mathcal{N}^{\text{D}}$. There are $M$ IIoT devices that can be connected to
every source virtual node and send information to its destination users
through middle virtual nodes. There are $\mathcal{J}$ destination users that
can be connected to any destination virtual node. The available amount of
resources at node $n\in\mathcal{N}$ is indicated by $C_{n}$ (in Hz) and
$B_{n}$ (in Byte), where $C_{n}$ and $B_{n}$ denote the computing and memory
capacity at node $n\in\mathcal{N}$, respectively. We define
$(\acute{n},n)\in\mathcal{L}$ as a link from virtual node
$\acute{n}\in\mathcal{N}^{\text{S}}\cup\mathcal{N}^{\text{R}}$ to virtual node
$n\in\mathcal{N}^{\text{R}}\cup\mathcal{N}^{\text{D}}$, where $\acute{n}$ and
$n$ are the origin node and the destination node of the link $(\acute{n},n)$,
respectively. The available bandwidth on each virtual link
$(\acute{n},n)\in\mathcal{L}$ is $W_{\acute{n}n}$ (in Hz).

Figure 1: System model with several candidate VNFs for each service between
multiple sources and destinations.

Each service provider can provision $\tilde{F}_{n}$ types of VNFs at virtual
node $n$. Let $\mathcal{N}_{f}$ denote a set of nodes that can run function
$f$. There is a service request set
$\mathcal{X}=\\{\mathcal{X}_{1},\mathcal{X}_{2},\dots,\mathcal{X}_{k},\dots,\mathcal{X}_{K}\\}$
with $|\mathcal{X}|=K$, in which service $\mathcal{X}_{k}$ consisting of
several VNFs that must be performed sequentially on the packet stream of that
service. A SFC for service $k$ is described by the sequence of VNFs as
$\mathcal{X}_{k}=\left(o^{1}_{k},o^{2}_{k},\dots,o^{f}_{k},\dots,o^{F_{k}}_{k}\right)$
in which $o^{f}_{k}$ is $f^{\text{th}}\in\\{1,\dots,f,\dots,F_{k}\\}$ VNF of
the chain and $F_{k}$ is the total number of VNFs for service $k$. The
computing, memory, and bandwidth resources required to the $f^{\text{th}}$ VNF
of service $k$ are denoted by $c^{fk}_{\acute{n}}$, $b^{fk}_{\acute{n}}$, and
$w^{fk}_{\acute{n}n}$, respectively and are defined as,
$c^{fk}_{\acute{n}}=\bar{R}_{k}c_{f},\leavevmode\nobreak\
b^{fk}_{\acute{n}}=\bar{R}_{k}b_{f},\leavevmode\nobreak\
w^{fk}_{\acute{n}n}=\bar{R}_{k}/\eta_{\acute{n}n}$, where $\bar{R}_{k}$
denotes the bit rate of service $k$, $c_{f}$ is the required CPU cycle to
execute function $f$ for one bit per second, $b_{f}$ is the required memory to
execute function $f$ for one bit per second, and $\eta_{\acute{n}n}$ indicates
the spectral efficiency of link $(\acute{n},n)$. We consider a discrete-time
system in which all time slots (TSs) have unit length and is indexed by
$t=1,2,\dots$. For service $k$, the updated packets are generated by a source,
they are then dispersed throughout the network from one node to the next.
After entering the packet of service $k$ at node $n$ and performing the
required processing on it, the packet is ready to be sent to next node. In
each TS, the network must schedule which IIoT service updates its packets at
the destination, and which nodes handle the selected services. In other words,
in each TS, we allocate the proper VNF to each function of each service and
schedule the run time of that function.

######  Definition 1.

For function $f$ of service $k$ of IIoT device $m$, we define
$u^{fkm}_{\acute{n}n}(t)$ as the scheduling action at slot $t$, where
$u^{fkm}_{\acute{n}n}(t)=1$ denotes device $m$ is planned to transmit its
packet of function $f$ of service $k$ at TS $t$ from node $\acute{n}$ to node
$n$ and $u^{fkm}_{\acute{n}n}(t)=0$, otherwise.

Therefore, to guarantee the QoS, which is defined as a satisfaction measure of
the QoS parameters including the bit rate as well as the AoI, the following
constraint should be satisfied for service $k$ of IIoT device $m$:

$\bar{R}^{k}_{m}\leq\sum_{\acute{n}\in\mathcal{N}_{f}}\sum_{n\in\mathcal{N}_{f}}u^{fkm}_{\acute{n}n}(t)w^{fk}_{\acute{n}n}(t)\eta_{\acute{n}n},\forall
f,k,m,$ (1)

where $\bar{R}^{k}_{m}$ is the bit rate of service $k$ of IIoT device $m$.

###  III-B VNF Placement

In NFV resource allocation, there are two phases: 1) the VNF placement, 2) the
VNF scheduling. In the first phase, the goal is to optimally map SFC requests
in NFV-enabled networks. In other words, in the VNF placement, the aim is to
choose the optimal locations for a chain of VNFs according to an SFC under
limited network resource constraints. We divide all services at TS $t$,
$\mathcal{K}(t)$, into three categories: 1) current arrived services, 2)
current terminated services and 3) active services. Current arrived service,
$\mathcal{K}_{R}(t)$, are those that arrive in current TS,
$\mathcal{K}_{R}(t)=\left\\{k\in\mathcal{K}(t):\psi^{km}(t)=1\right\\}$, where
$\psi^{km}(t)$ is admission control for service $k$ of IIoT device $m$ at TS
$t$. We assume that the time is divided into several TSs with equal duration
$\delta$ indexed by one integer value, e.g., $t\in\mathbb{N}_{+}$, where
$\mathbb{N}_{+}$ denotes the set of positive integers. $\mathcal{K}_{T}(t)$
are services that their running time is terminated in TS $t$,
$\mathcal{K}_{T}(t)=\left\\{k\in\mathcal{K}^{t}:\delta\sum_{f\in\mathcal{F}_{k}}\sum_{n\in\mathcal{N}_{f}}\sum_{\acute{t}=t-T^{\text{max}}}^{t}v^{fkm}_{n}(\acute{t})\geq
T^{km}\right\\}$, where $T^{km}$ is run-time duration of service $k$ of IIoT
device $m$, and $T^{\text{max}}$ indicates the maximum service time among all
services which defined as $T^{\text{max}}=\max_{km}\\{T^{km}\\}$. The binary
variable $v^{fkm}_{n}(t)$ indicates whether function $f$ of service $k$ of
IIoT device $m$ is assigned to virtual node $n$ at TS $t$. Active services,
$\mathcal{K}_{A}(t)$ are those that are currently running,
$\mathcal{K}_{A}(t)=\mathcal{K}(t)\setminus\mathcal{K}_{R}(t)\cup\mathcal{K}_{T}(t)$.
We assume that multiple VNFs of the same type can be run on the same node.
However, the bandwidth utilization of the links and the utilization of memory
and CPU at nodes cannot exceed the available resources, which are ensured as:

$\displaystyle\sum_{t=1}^{\acute{t}}\sum_{m\in\mathcal{M}}\sum_{k\in\mathcal{K}}\sum_{f\in\mathcal{F}_{k}}w^{fk}_{\acute{n}n}u^{fkm}_{\acute{n}n}(t)\leq
r^{\text{BW}}_{\acute{n}n}(\acute{t}),$ (2)
$\displaystyle\forall\acute{n}n\in\mathcal{L},\acute{n}\in\mathcal{N},\acute{t}=1,2,\dots,T,$

where $r^{\text{BW}}_{\acute{n}n}(t)$ denotes the remaining bandwidth on link
$(\acute{n},n)$ at TS $t$ which can be updated as:

$\displaystyle
r^{\text{BW}}_{\acute{n}n}(t+1)=\min\Bigg{\\{}r^{\text{BW}}_{\acute{n}n}(t)-\sum_{m\in\mathcal{M}}\sum_{f\in\mathcal{F}_{k}}\Big{[}$
$\displaystyle\sum_{k\in\mathcal{K}_{R}}w^{fk}_{\acute{n}n}u^{fkm}_{\acute{n}n}(t)-\sum_{k\in\mathcal{K}_{T}}w^{fk}_{\acute{n}n}u^{fkm}_{\acute{n}n}(t)\Big{]},W_{\acute{n}n}\Bigg{\\}}.$
(3)

The allocated memory space on a node cannot exceed the total amount of
available memory on that node. As a result:

$\displaystyle\sum_{t=1}^{\acute{t}}\sum_{m\in\mathcal{M}}\sum_{k\in\mathcal{K}}\sum_{f\in\mathcal{F}_{k}}b^{fk}_{n}v^{fkm}_{n}(\acute{t})\leq
r^{\text{B}}_{n}(\acute{t}),\forall n\in\mathcal{N},$ (4)
$\displaystyle\acute{t}=1,2,\dots,T,$

where $r^{\text{B}}_{n}(t)$ represents the remaining memory in node $n$ at TS
$t$ and can be updated as

$\displaystyle
r^{\text{B}}_{n}(t+1)=\min\Big{\\{}r^{\text{B}}_{n}(t)-\sum_{m\in\mathcal{M}}\sum_{k\in\mathcal{K}_{R}}\sum_{f\in\mathcal{F}_{k}}b^{fk}_{n}v^{fkm}_{n}(t)$
$\displaystyle+\sum_{k\in\mathcal{K}_{T}}\sum_{f\in\mathcal{F}_{k}}b^{fk}_{n}v^{fkm}_{n}(t),B_{n}\Big{\\}}.$
(5)

The allocated CPU cycles on a node cannot exceed the total amount of available
CPU on that node. As a result:

$\sum_{t=1}^{\acute{t}}\sum_{m\in\mathcal{M}}\sum_{k\in\mathcal{K}}\sum_{f\in\mathcal{F}_{k}}c^{fk}_{n}v^{fkm}_{n}(\acute{t})\leq
r^{\text{C}}_{n}(\acute{t}),\forall n\in\mathcal{N},$ (6)

where $r^{\text{C}}_{n}(t)$ represents the remaining computing cycle in node
$n$ at TS $t$ and can be updated as

$\displaystyle
r^{\text{C}}_{n}(t+1)=\min\Big{\\{}r^{\text{C}}_{n}(t)-\sum_{m\in\mathcal{M}}\sum_{k\in\mathcal{K}_{R}}\sum_{f\in\mathcal{F}_{k}}c^{fk}_{n}v^{fkm}_{n}(t)+$
$\displaystyle\sum_{m\in\mathcal{M}}\sum_{k\in\mathcal{K}_{T}}\sum_{f\in\mathcal{F}_{k}}c^{fk}_{n}v^{fkm}_{n}(t),C_{n}\Big{\\}}.$
(7)

Function $f$ can only be run by nodes belong to $\mathcal{N}_{f}$, thus, we
have:

$\sum_{\acute{n}\in\mathcal{N}\setminus\mathcal{N}_{f}}\sum_{n\in\mathcal{N}}u^{fkm}_{\acute{n}n}(t)=0,\leavevmode\nobreak\
\sum_{n\in\mathcal{N}\setminus\mathcal{N}_{f}}v^{fkm}_{n}(t)=0.$ (8)

The VNF nodes can not fragment their flows into multiple links. The following
condition must be met to ensure that only one link is assigned to the output
of each function:

$\sum_{\acute{n}\in\mathcal{N}_{f}}\sum_{n\in\mathcal{N}}u^{fkm}_{\acute{n}n}(t)=1.$
(9)

To ensure that for each function of a service, either none or exactly one
instance of VNF is assigned to a node, the following constraint must be
satisfied:

$\sum_{n\in\mathcal{N}_{f}}v^{fkm}_{n}(t)\leq 1,\forall f,k,m,t.$ (10)

###  III-C Routing

Each service $k\in\mathcal{K}$ is characterized by a source IIoT device $m$
that wants to transmit a flow of data toward a destination user $j$. To impose
a single path flow balance, the following flow conservation constraint must be
satisfied:

$\displaystyle\sum_{f\in\mathcal{F}_{k}}\sum_{n\in\mathcal{N}}u^{fkm}_{\acute{n}n}(t)-\sum_{f\in\mathcal{F}_{k}}\sum_{n\in\mathcal{N}}u^{fkm}_{n\acute{n}}(t)=$
(11) $\displaystyle\begin{cases}1,&\text{if
$\acute{n}\in\mathcal{N}^{\text{S}}$},\\\ -1,&\text{if
$\acute{n}\in\mathcal{N}^{\text{D}}$},\\\
0,&\text{otherwise}.\end{cases}\hskip 14.22636pt\forall k,m,t,\acute{n}.$

To guarantee that if function $f$ of service $k$ of IIoT device $m$ is placed
at node $\acute{n}$ then the traffic flow will be routed through that node,
the following constraints must be always satisfied:

$\sum_{n\in\mathcal{N}}u^{fkm}_{\acute{n}n}(t)\geq
v^{fkm}_{\acute{n}}(t),\forall f,k,\acute{n},t.$ (12)

###  III-D The VNF Scheduling

The VNF scheduling is done in the second phase and is based on the first phase
results, i.e, VNF placement. Therefore, a different placement scheme will lead
to a different solution for VNF scheduling. Based on a given placement, VNF
scheduling aims to find the best scheduling scheme to execute VNFs at the
corresponding virtual nodes. We assume that $\tau^{(f+1)km}_{n}$ is starting
time of VNF $(f+1)$ of the $k^{\text{th}}$ service for IIoT device $m$ which
is allocated to node $n$. VNF $(f+1)$ of service $k$ in node $n$ can start its
service if and only if execution of its preceding VNF $f$ is finished. Let
$\tilde{\tau}^{fkm}_{\acute{n}n}$ denote the propagation delay between virtual
nodes $\acute{n}$ and $n$ and it can be calculated as,
$\tilde{\tau}^{fkm}_{\acute{n}n}=d_{\acute{n}n}/c$, where $c$ is light speed
and $d_{\acute{n}n}$ is distance between nodes $\acute{n}$ and $n$. Since the
virtualized nodes are mapped to the physical ones, where they can be far from
each other, the propagation delay can be notable [19, 28]. The time it takes
to upload data through the link (transmission delays) and the processing time
of each VNF denoted by $\bar{\tau}^{fkm}_{\acute{n}n}(t)$ and
$\hat{\tau}^{fkm}_{\acute{n}}(t)$, respectively. They can be calculated as
$\bar{\tau}^{fkm}_{\acute{n}n}(t)=\bar{R}_{k}/w^{fk}_{\acute{n}n}\eta_{\acute{n}n}$
and
$\hat{\tau}^{fkm}_{\acute{n}}(t)=\bar{R}_{k}c^{fk}_{\acute{n}}/C_{\acute{n}}$.
Therefore, the run-time of VNF $f$ of service $k$ for IoT device $m$ at
virtual node $n$ can be determined as:

$\displaystyle\tau^{(f+1)km}_{n}(t+1)=\sum_{\begin{subarray}{c}\acute{n}\in\mathcal{N},\acute{n}\neq
n\end{subarray}}v^{fkm}_{\acute{n}}(t)\tau^{fkm}_{\acute{n}}(t)+$ (13)
$\displaystyle\sum_{\begin{subarray}{c}\acute{n}\in\mathcal{N},\acute{n}\neq
n\end{subarray}}v^{fkm}_{\acute{n}}(t)\hat{\tau}^{fkm}_{\acute{n}}(t)+\sum_{\begin{subarray}{c}\acute{n}\in\mathcal{N},\acute{n}\neq
n\end{subarray}}u^{fkm}_{\acute{n}n}(t)\tilde{\tau}^{fkm}_{\acute{n}n}+$
$\displaystyle\sum_{\begin{subarray}{c}\acute{n}\in\mathcal{N},\acute{n}\neq
n\end{subarray}}u^{fkm}_{\acute{n}n}(t)\bar{\tau}^{fkm}_{\acute{n}n}(t),$

To guarantee that VNF $f$ of service $k$ of device $m$ completes its process
in the allocated TS, the summation of the propagation delay
$\tilde{\tau}^{fkm}_{\acute{n}n}$, the processing time
$\hat{\tau}^{fkm}_{\acute{n}}(t)$, and transmission delay,
$\bar{\tau}^{fkm}_{\acute{n}n}(t)$ with $\tau^{fkm}_{n}(t)$ should not exceed
duration time of one slot, $\delta$:

$\displaystyle\tau^{fkm}_{n}(t)+\hat{\tau}^{fkm}_{n}(t)+\bar{\tau}^{fkm}_{\acute{n}n}(t)+\tilde{\tau}^{fkm}_{\acute{n}n}(t)\leq\delta,$
(14)

An example for three services, indexed by $k=\\{1,2,3\\}$ correspond to IIoT
devices indexed by $m=\\{1,2,3\\}$, is illustrated in Fig. 2. First service
arrives at the time $\tilde{t}_{1}$ and requests VNFs
$\\{o^{1}_{1},o^{2}_{1},o^{3}_{1},o^{4}_{1}\\}$ as shown in Fig. 2. As can be
seen from Fig. 2, the VNFs $o^{1}_{1},o^{2}_{1},o^{3}_{1}$, and $o^{4}_{1}$
are assigned to nodes $2,3,4$, and $5$, respectively.

Figure 2: Scheduling of services 1, 2 and 3: At beginning of each TS, the
scheduler assigns optimal node to each function in order to guarantee the QoS
of all services.

Similarly, second service arrives at a time $\tilde{t}_{2}$ with VNFs
$\\{o^{1}_{2},o^{2}_{2},o^{3}_{2}\\}$ which were assigned to nodes $1,2$, and
$4$, respectively. Finally, third service arrives at a time $\tilde{t}_{3}$
with VNFs $\\{o^{1}_{3},o^{2}_{3}\\}$ which were assigned to nodes $3$, and
$4$, respectively.

###  III-E Access Networks

####  III-E1 Uplink Access Network

We assume that the total bandwidth of uplink (UL) access network is divided
into $H$ subcarriers where $\mathcal{H}=\\{1,\dots,h,\dots,H\\}$ indicates the
index set of all subcarriers [29, 30]. The total allocated bandwidth does not
exceed a given total bandwidth budget, e.g.
$\sum_{m\in\mathcal{M}}\sum_{n\in\mathcal{N}}\sum_{h\in\mathcal{H}}\sum_{k\in\mathcal{K}}\rho^{hk}_{mn}\bar{w}_{h}\leq\bar{W}$
where $\bar{w}_{h}$ denotes the bandwidth of subcarrier $h$, $\bar{W}$ is
total bandwidth budget at UL access network. $\rho^{hk}_{mn}$ denotes an
integer variable for assigning subcarriers to service $k$ and link between
IIoT device $m$ and node $n$, where $\rho^{hk}_{mn}=1$ if subcarrier $h$ is
allocated to service $k$ and link between IIoT device $m$ and node $n$, and
otherwise $\rho^{hk}_{mn}=0$. To guarantee the end-to-end QoS, the following
constraints should be satisfied for bit rate of service $k$ of IIoT device
$m$, $R^{k}_{m}$ in UL access network, as well:

$\bar{R}^{k}_{m}\leq
R^{k}_{m}=\sum_{m\in\mathcal{M}}\sum_{n\in\mathcal{N}}\sum_{h\in\mathcal{H}}\rho^{hk}_{mn}\bar{w}_{h}\log_{2}(1+\frac{p^{hk}_{mn}g^{h}_{mn}}{\sigma^{2}}),$
(15)

where $p^{hk}_{mn}$ and $g^{h}_{mn}$ denote the power allocated to the service
$k$ of IIoT device $m$ on subcarrier $h$ and channel gain between IIoT device
$m$ and node $n$ on subcarrier $h$, respectively. $\sigma^{2}$ denotes the
variance of additive white Gaussian noise. Each subcarrier can only be
assigned to at most one IIoT device:

$\sum_{m\in\mathcal{M}}\sum_{n\in\mathcal{N}}\sum_{k\in\mathcal{K}}\rho^{hk}_{mn}\leq
1,\forall h.$ (16)

The access network delay consists of transmission and propagation delays,
which are calculated as
$\bar{\pi}^{k}_{mn}=\bar{R}^{k}_{m}/\sum_{h\in\mathcal{H}}\rho^{hk}_{mn}\bar{w}_{h}R^{k}_{m},\hat{\pi}_{mn}=d_{mn}/c$.
The access delay should not exceed the threshold value, $\epsilon^{k}_{m}$

$\displaystyle\hat{\pi}_{mn}+\bar{\pi}^{k}_{mn}\leq\epsilon^{k}_{m}.$ (17)

####  III-E2 Downlink Access Network

We assume that the total bandwidth of downlink (DL) access network is divided
into $\check{H}$ subcarriers where
$\check{\mathcal{H}}=\\{1,\dots,h,\dots,\check{H}\\}$ denotes the index set of
all subcarriers. The total allocated bandwidth do not exceed a given total
bandwidth budget, e.g.
$\sum_{j\in\mathcal{J}}\sum_{n\in\mathcal{N}}\sum_{\check{h}\in\mathcal{\check{H}}}\sum_{k\in\mathcal{K}}\rho^{\check{h}k}_{nj}{\color[rgb]{0,0,0}\check{w}_{\check{h}}}\leq\check{W}$
where $\check{w}_{\check{h}}$ denotes the bandwidth of subcarrier $\check{h}$,
$\check{W}$ is total bandwidth budget at access network and
$\rho^{\check{h}k}_{nj}$ denotes the integer variable for assigning
subcarriers to service $k$ and link between destination node $n$ and
destination user $j$, where $\rho^{\check{h}k}_{nj}=1$ if subcarrier
$\check{h}$ is allocated to service $k$ and link between destination node $n$
and destination user $j$, and otherwise $\rho^{\check{h}k}_{nj}=0$. To
guarantee the end-to-end QoS, the following constraints should be satisfied
for bit rate of service $k$ of destination user $j$, $\check{R}^{k}_{j}$ in
access network, as well:

$\bar{R}^{k}_{j}\leq\check{R}^{k}_{j}=\sum_{j\in\mathcal{J}}\sum_{n\in\mathcal{N}}\sum_{\check{h}\in\mathcal{\check{H}}}\rho^{\check{h}k}_{nj}\check{w}_{\check{h}}\log_{2}\left(1+\frac{p^{\check{h}k}_{nj}g^{\check{h}}_{nj}}{\sigma^{2}}\right),$
(18)

where $\bar{R}^{k}_{j}$ is the bit rate of service $k$ of user $j$,
$p^{\check{h}k}_{nj}$ and $g^{\check{h}}_{nj}$ denote the power allocated to
the service $k$ of destination user $j$ on subcarrier $\check{h}$ and channel
gain between destination node $n$ and destination user $j$ on subcarrier
$\check{h}$, respectively. Each subcarrier can only be assigned to at most one
IIoT device:

$\sum_{j\in\mathcal{J}}\sum_{n\in\mathcal{N}}\sum_{k\in\mathcal{K}}\rho^{\check{h}k}_{nj}\leq
1,\forall\check{h},$ (19)

The access network delay consists of transmission and propagation delays,
which are calculated similar to (17).

##  IV AoI Model for the Proposed System

In this section, the AoI is adopted to formulate the freshness of the sensing
data collected by the IIoT devices.

######  Definition 2.

For service $k$ of IIoT device $m$, let $X_{n}^{km}(t)$ and $Y_{n}^{km}(t)$ be
the AoI of the packet of service $k$ of IIoT device $m$ at source node $n$ and
destination node $n$ at TS $t$, respectively. We define $\Delta_{j}^{km}(t)$
as the AoI of the packet of service $k$ of IIoT device $m$ at the destination
user $j$ at TS $t$. Let $\hat{X}_{n}^{km}$ and $\hat{\Delta}_{j}^{km}$ denote
the upper limits of the AoI of the packet of service $k$ of IIoT device $m$ at
node $n$ and the destination user $j$, respectively. Considering the real-time
application of the proposed scheme, it is clear that $\hat{X}_{n}^{km}$ and
$\hat{\Delta}_{j}^{km}$ are finite.

Note that $X_{n}^{km}(t)$, $Y_{n}^{km}(t)$, and $\Delta_{j}^{km}(t)$ depend on
how the scheduling is done. We assume that $X_{n}^{km}(t)$ is equal to $0$ at
$t=0$. For service $k$ of IIoT device $m$, if there is a packet arriving at
source node $n$ at TS $t$, $X_{n}^{km}(t)$ will be equal to sum of propagation
and transmission delay from node $m$ to node $n$, i.e
$\hat{\pi}_{mn}+\bar{\pi}^{k}_{mn}$, otherwise, it will increase by $\delta$
(due to the one slot transmission). Therefore, the AoI of the packet of
service $k$ of device $m$ at source node $n$, $X_{n}^{km}(t+1)$, can be
updated as follows:

$\displaystyle X_{n}^{km}(t+1)=$ (20)
$\displaystyle\begin{cases}\hat{\pi}_{mn}+\bar{\pi}^{k}_{mn},&\text{If}\rho^{hk}_{mn}(t)=1,\\\
\min\\{X_{n}^{km}(t)+\delta,\hat{X}_{n}^{km}\\},&\text{otherwise},\end{cases}$

where $\rho^{hk}_{mn}(t)=1$ means in the previous slot $t$, subcarrier $h$ was
allocated to service $k$ of IIoT device $m$ to deliver the updated packet to
source node $n$. Similarly, for service $k$ of IIoT device $m$, if there is a
packet arriving at destination node $n$ at TS $t$, $Y_{n}^{km}(t)$ will be
$\hat{\pi}_{mn}+\bar{\pi}^{k}_{mn}+\delta$, since in the previous TS $t-1$, a
successful transmission from IIoT device $m$ to source node $n$ has happened
and the term $\delta$ is also added because the service routing has happened
in TS $t$. If in the TS $t-1$ no packet is transmitted to source node $n$ from
IIoT device $m$ and a successful VNF placement occurs, then the AoI of
destination node $n$ will be equal to one TS plus $X_{n}^{km}(t)$, otherwise,
it will increase by $\delta$. Therefore, the AoI of the packet of service $k$
of device $m$ at destination node $n$, $Y_{n}^{km}(t+1)$, can be updated as
follows:

$\displaystyle
Y_{n}^{km}(t+1)=\begin{cases}\hat{\pi}_{mn}+\bar{\pi}^{k}_{mn}+\delta,&\text{If}\leavevmode\nobreak\
\Theta_{1},\\\
\min\\{X_{n}^{km}(t)+\delta,\hat{X}_{n}^{km}\\},&\text{If}\leavevmode\nobreak\
\Theta_{2},\\\
\min\\{Y_{n}^{km}(t)+\delta,\hat{Y}^{n}_{km}\\},&\text{otherwise},\end{cases}$
(21)

where $\Theta_{1}=\rho^{hk}_{mn}(t-1)\varrho_{km}(t)=(F_{k})^{2}$,
$\Theta_{2}=\rho^{hk}_{mn}(t-1)=0$. $\rho^{hk}_{mn}(t-1)=1$ means in the two
previous slots $t-1$, subcarrier $h$ was allocated to service $k$ of IIoT
device $m$ to deliver its updated packet to source node $n$ and
$\varrho_{km}(t)=\left(\sum_{f\in\mathcal{F}_{k}}\sum_{\acute{n}\in\mathcal{N}\setminus\mathcal{N}_{f}}\sum_{n\in\mathcal{N}}u^{fkm}_{\acute{n}n}(t)\right)\\\
\left(\sum_{f\in\mathcal{F}_{k}}\sum_{n\in\mathcal{N}}v^{fkm}_{n}(t)\right)$
where $\varrho_{km}(t)=(F_{k})^{2}$ means in the previous slot $t$, $F_{k}$
nodes and $F_{k}$ links were allocated to $F_{k}$ functions of service $k$ of
IIoT device $m$ to deliver the update packet to destination node $n$. Finally,
at destination user $j$, for the AoI of service $k$ of device $m$, if no
destination node delivers a fresh packet to destination user $j$ at TS $t$,
then the AoI of service $k$ of device $m$, $\Delta_{j}^{km}(t+1)$ will
increase by $\delta$, otherwise, the information of service $k$ of device $m$
is updated according to how we receive a packet from destination node $n$, as
depicted in (22).

$\displaystyle\Delta_{j}^{km}(t+1)=\begin{cases}\hat{\pi}_{mn}+\bar{\pi}^{k}_{mn}+\delta+\check{\pi}^{k}_{nj}+\tilde{\pi}_{nj},&\text{If}\leavevmode\nobreak\
\rho^{hk}_{mn}(t-2)\varrho_{km}(t-1)\rho^{\check{h}k}_{nj}(t)=(F_{k})^{2},\\\
\min\\{X_{n}^{km}(t)+\delta+\check{\pi}^{k}_{nj}+\tilde{\pi}_{nj},\hat{\Delta}_{km}\\},&\text{If}\leavevmode\nobreak\
\rho^{hk}_{mn}(t-2)=0\&\varrho_{km}(t-1)\rho^{\check{h}k}_{nj}(t)=(F_{k})^{2},\\\
\min\\{Y_{n}^{km}(t)+\check{\pi}^{k}_{nj}+\tilde{\pi}_{nj},\hat{\Delta}_{km}\\},&\text{If}\rho^{hk}_{mn}(t-2)=0\&\varrho_{km}(t-1)=0\&\rho^{\check{h}k}_{nj}(t)=1,\\\
\min\\{\Delta_{km}(t)+\delta,\hat{\Delta}_{km}\\},&\text{otherwise},\end{cases}$
(22)

where $\Delta_{km}(t)=t-U(t)$, $U(t)$ denotes the timestamp of the most
recently received status packet at time $t$, $\rho^{hk}_{mn}(t-2)=1$ means in
the three previous slots $t-2$ a subcarrier was allocated to service $k$ of
IIoT device $m$ at UL network to deliver the update packet to source node $n$,
$\varrho_{km}(t-1)=(F_{k})^{2}$ means in the two previous slots $t$, $F_{k}$
nodes and $F_{k}$ links were allocated to $F_{k}$ functions of service $k$ of
IIoT device $m$ to deliver the update packet to destination node $n$, and
$\rho^{\check{h}k}_{nj}(t)=1$ means in the previous slot $t$, subcarrier
$\check{h}$ was allocated to service $k$ of IIoT device $m$ at DL network to
deliver the update packet to destination $j$.

##  V Problem Definition and Formulation

We aim to manage VNFs of all services of IoT devices, so as to jointly
minimize the VNF placement, scheduling cost and the maximum of AoIs of
devices.

######  Definition 3.

Let $\beta^{fkm}_{\acute{n}n}(t)$ denote the cost for forwarding the
information of function $f$ of service $k$ of device $m$ over virtual link
$(\acute{n},n)$ and $\alpha^{fkm}_{n}(t)$ the cost for processing the
information of function $f$ of service $k$ of device $m$ at node $n$. We also
define $\zeta^{hk}_{mn}(t)$, and $\zeta^{\check{h}k}_{nj}(t)$ as the cost for
forwarding the information of service $k$ of device $m$ to node $n$ over
wireless link $h$ at TS $t$, the cost for forwarding the information of
service $k$ of device $n$ to user $j$ over wireless link $\check{h}$ at TS
$t$, respectively.

We formulate the optimization problem as the minimization of the sum of VNF
placement and scheduling cost in addition to the average of AoIs of devices in
respect to total transmit power at each node and device, each link bandwidth
and CPU and memory capacity of each node constraints:

$\displaystyle\min_{\boldsymbol{u},\boldsymbol{v},\boldsymbol{\rho}}\xi\bar{\Delta}+\xi_{1}\Lambda_{1}+\xi_{2}\Lambda_{2}+\xi_{3}\Lambda_{3}+\xi_{4}\Lambda_{4}$
(23) $\displaystyle\bar{\Delta}=\sum_{k,m}{\bar{\Delta}_{km}}$
$\displaystyle\bar{\Delta}_{km}=\lim_{\acute{\tau}\to\infty}\frac{1}{\acute{\tau}}\int_{0}^{\acute{\tau}}{\Delta}_{km}(t)dt$
$\displaystyle\Lambda_{1}=\sum_{t}\sum_{k\in\mathcal{K}}\sum_{f\in\mathcal{F}_{k}}\sum_{m\in\mathcal{M}}\sum_{(\acute{n},n)\in\mathcal{L}}u^{fkm}_{\acute{n}n}(t)\beta^{fkm}_{\acute{n}n}(t)$
$\displaystyle\Lambda_{2}=\sum_{t}\sum_{k\in\mathcal{K}}\sum_{f\in\mathcal{F}_{k}}\sum_{m\in\mathcal{M}}\sum_{(\acute{n},n)\in\mathcal{L}}v^{fkm}_{n}(t)\alpha^{fkm}_{n}(t)$
$\displaystyle\Lambda_{3}=\sum_{t}\sum_{k\in\mathcal{K}}\sum_{h\in\mathcal{H}}\sum_{m\in\mathcal{M}}\sum_{n\in\mathcal{N}}\zeta^{hk}_{mn}(t)\rho^{hk}_{mn}(t)(\bar{\omega}_{h}+p^{hk}_{mn})$
$\displaystyle\Lambda_{4}=\sum_{t}\sum_{k\in\mathcal{K}}\sum_{\check{h}\in\mathcal{\check{H}}}\sum_{j\in\mathcal{J}}\sum_{n\in\mathcal{N}}\zeta^{\check{h}k}_{mn}(t)\rho^{\check{h}k}_{mn}(t)(\check{\omega}_{\check{h}}+p^{\check{h}k}_{mn})$
$\displaystyle
s.t.(\ref{eq-u-1}),(\ref{eq-u-2}),(\ref{eq-2}),(\ref{eq-3}),(\ref{eq-u-4})$

where $\bar{\Delta}$ is the average AoI of destination users, and
$\bar{\Delta}_{km}$ is the average AoI of service $k$ of IIoT device $m$,
$\Lambda_{1}$ indicates cost for executing all functions of services,
$\Lambda_{2}$ denotes cost for forwarding all functions of services,
$\Lambda_{3}$ indicates the cost for forwarding the information of service $k$
of device $m$ over link $h$ and $\Lambda_{4}$ denotes the cost for forwarding
the information of service $k$ of device $m$ over link $\check{h}$,
$\xi,\xi_{1},\dots,\xi_{4}$ are the weights which act as balancing parameters
among various parts of our objective function.
Since the remaining resources and the channel conditions are dynamically
varying (i.e., stochastic environment), (23) is a dynamic optimization problem
which can be formulated as the Markov decision process (MDP). Moreover, due to
the non-convexity of some constraints and the discrete sets in the
constraints, this problem is a non-convex and NP-hard optimization problem.
Traditional methods such as static optimization and game theory can not obtain
the optimal solutions, especially in large scale networks. In addition,
heuristic algorithms can not necessarily reach close-to-optimal results due to
lack of strict theoretical proof. To overcome these drawbacks, the DRL-based
algorithms can be utilized to obtain the near-optimal solution for such
problems.

##  VI DRL-based Solution

Except in a few cases in wireless resource allocation, where the optimization
problems can be formulated as a convex optimization problem, most optimization
problems are non-convex and NP-hard because they include joint power
allocation and spectrum assignment. Therefore, the traditional algorithms such
as convex optimization cannot optimally solve these problems with polynomial
time complexity, especially in large scale networks. In the case of heuristic
algorithms, it is difficult to reach close-to-optimal results due to lack of
strict theoretical proof. To tackle these challenges, DRL-based algorithms can
be effectively used to solve such problems. Many recent works show that the
machine-learning-based resource allocation outperforms conventional methods
[31, 5, 32]. In this section, we first introduce some basics about DRL and
then introduce the proposed MA-CA2C algorithm. In the traditional RL, agents
interact with the environment and learn to take the action that would yield
the most cumulative reward. A typical RL problem is modeled as an MDP. An MDP
mainly consists of a tuple as $\big{\\{}s(t),a(t),r(t),s(t+1)\big{\\}}$. At
each decision epoch (TS) $t$, agent is at state $s(t)$ and takes an action
$a(t)$ based on a policy and causes the environment transitions to new state
$s(t+1)$ while it receives an immediate reward $r(t)$. Basically, the aim of
MDP is to train an agent to find a policy $\pi$ which maps the state $s(t)$ to
action $a(t)$, i.e., $a(t)=\pi(s(t))$, and returns the maximum expected
cumulative discounted future reward as
$r(t)=\mathbb{E}\\{\sum_{l=t}^{T}\gamma(l-t)r(t+l)\\}$ by taking a series of
actions in one or more states, where $\gamma\in[0,1]$ is a discount factor
indicating how future rewards is important and $T$ is the number of decision
TSs. In traditional Q-learning, the Q-table is used to store state-action
values pairs. In large scale systems, like the considered system model in this
paper, the state and action spaces are very large and it leads to a large
$Q$-table, therefore, using one table to store all action values is
impractical.

###  VI-A Baseline Algorithms

####  VI-A1 Deep Q-Network

Recently, DRL is introduced as a promising technique to overcome the mentioned
challenges in RL. In this algorithm, deep neural networks (DNNs) are used as
the function approximators to predict Q-values. Therefore, DRL not only
enhances the performance of traditional RL schemes, but also can manage
continuous state and action spaces. The $Q$-function estimated by the neural
network is represented by $Q(s(t),a(t);\boldsymbol{\theta}(t))$ where the
parameter $\boldsymbol{\theta}(t)$ has the weights for the neural network and
its updated value is used to train the neural network and approximate the real
values of $Q$ [25, 18]. By minimizing the loss function
$L(\boldsymbol{\theta}(t))$ at each iteration, the deep $Q$-function is
trained to learn the best fitting, where the loss function is the expectation
of mean squared error of estimated value from the target value and can be
expressed as
$L(\boldsymbol{\theta}(t))=\mathbb{E}[(y(t)-Q(s(t),a(t);\boldsymbol{\theta}(t)))^{2}]$
[25], where
$y(t)=R(t)+\gamma\max_{a(t+1)}Q(s(t+1),a(t+1);\boldsymbol{\theta}(t))$ is the
target value and $a(t+1)$ indicates the action generated by the DNN in TS
$t+1$, given the state $s(t+1)$. Although, the DNN provides accurate
approximation, it may lead to the divergence of the learning algorithm or very
ineffective learning because of the non-stationary target values and samples
correlation. To overcome the non-stationary and samples correlation
challenges, a pair of techniques, namely Fixed Target Network [33] and
Experience Replay [34] are utilized, respectively. By adopting these
techniques, the loss function can be written as

$\displaystyle
L(\boldsymbol{\theta}(t))=\mathbb{E}_{D}[(R(t)+\gamma\max_{a(t+1)}Q(s(t+1),a(t+1);\acute{\boldsymbol{\theta}}(t))$
$\displaystyle-Q(s(t),a(t);\boldsymbol{\theta}(t)))^{2}],$ (24)

where $\acute{\boldsymbol{\theta}}(t)$ denotes the parameters of the target
network, and the expectation is taken over the mini-batches sampled from $D$.
The DQN with target network and experience replay can only handle the
environment with discrete action spaces [33]. Since the proposed scheme in
this paper consists of continuous and discrete actions as power allocation and
VNF placement, respectively, the DQN method can not optimally solve our
proposed problem.

####  VI-A2 Deep Deterministic Policy gradient Deep RL Algorithm

Model-free deep RL approaches like DQN, dueling DQN and double DQN are value-
based algorithms in which the Q-values are estimated with lower variance.
These solutions can not handle the problems with continuous action spaces. To
overcome this challenge, policy gradient-based RL approaches can be used,
which can deal with problems with continuous action space by learning
deterministic/stochastic policies. In these methods, the aim is to optimize a
policy based on the gradient of the expected reward. However, these methods
have very slow convergence [35]. To tackle this problem, the Deep
Deterministic Policy Gradient abbreviated as DDPG is utilized to integrate
both properties of policy-based and value-based algorithms in order to deal
with continuous and large state/action spaces[36, 35]. In this algorithm,
there are two separated neural networks, an actor and a critic network with
parameters $\boldsymbol{\omega}$ and $\boldsymbol{\theta}$, respectively. The
actor outputs continuous actions via a deterministic policy
$\pi(a(t)|s(t);\boldsymbol{\omega}(t))$, and the critic evaluates the action
taken by the actor via a $Q(s(t),a(t);\boldsymbol{\theta}(t))$. Since
obtaining the explicit expressions of $\pi(a(t)|s(t);\boldsymbol{\omega}(t))$
and $Q(s(t),a(t);\boldsymbol{\theta}(t))$ is difficult, the actor approximates
a deterministic policy $\pi(a(t)|s(t);\boldsymbol{\omega}(t))$ and the critic
approximates value function $Q(s(t),a(t);\boldsymbol{\theta}(t))$. For the
current state $s(t)$, the actor generates an action $a(t)$ based on a
deterministic policy $\pi(a(t)|s(t);\boldsymbol{\omega}(t))$. Then, critic
calculates the loss function based on the estimated Q-value with
$Q(s(t),a(t);\boldsymbol{\theta}(t))=\mathbb{E}_{a(t)\sim\pi(a(t)|s(t);\boldsymbol{\omega}(t))}[R(t)|s(t),a(t)]$.
The expectation is taken over the action $a(t)$ based on the deterministic
policy $\pi$, i.e., $a(t)\sim\pi(a(t)|s(t);\omega(t))$. The loss function of
the actor is defined as
$-J(\boldsymbol{\omega}(t))=-\mathbb{E}[Q(s(t),a(t);\boldsymbol{\theta}(t))]$.
The actor is updated by applying the policy gradient method as
$\nabla_{\boldsymbol{\omega}}J(\boldsymbol{\omega}(t))=\mathbb{E}[\nabla_{\boldsymbol{\omega}}\log\pi(a(t)|s(t);\boldsymbol{\omega}(t))Q(s(t),a(t);\boldsymbol{\theta})]$.
Then, the gradient descent is used to update $\boldsymbol{\omega}(t)$:

$\displaystyle\boldsymbol{\omega}(t+1)=\boldsymbol{\omega}(t)-\alpha_{a}(-\nabla_{\boldsymbol{\omega}}J(\boldsymbol{\omega}(t))),$
(25)

where $\alpha_{a}$ indicates the learning rate of the actor. For the
continuously differentiable loss function with respect to
$\boldsymbol{\theta}$, the gradients of the loss function can be used for
updating the parameters $\boldsymbol{\theta}$ of the critic DNN as follows:

$\displaystyle\Delta\boldsymbol{\theta}=\alpha_{c}[R(t)+\gamma\max_{a(t+1)}Q(s(t+1),a(t+1);\acute{\boldsymbol{\theta}})-$
$\displaystyle
Q(s(t),a(t);\boldsymbol{\theta})]\nabla_{\boldsymbol{\theta}}Q(s(t),a(t);\boldsymbol{\theta}),$
(26)

where $\alpha_{c}$ is critic learning rate. Moreover, since a mini-batch of
size $I$ is used to update the parameter $\boldsymbol{\theta}$, we have

$\displaystyle\Delta\boldsymbol{\theta}=\frac{\alpha_{c}}{I}\sum_{i=1}^{I}[R^{i}(t)+\gamma\max_{a^{i}(t+1)}Q(s^{i}(t+1),a^{i}(t+1);\acute{\boldsymbol{\theta}})$
$\displaystyle-Q(s^{i}(t),a^{i}(t);\boldsymbol{\theta})]\nabla_{\boldsymbol{\theta}}Q(s^{i}(t),a^{i}(t);\boldsymbol{\theta}),$
(27)

where index $i$ refers to sample $i$.

####  VI-A3 Compound-Action Actor Critic DRL Algorithm

DRL algorithms are suitable for finding the optimal policies in problems with
high-dimensional state spaces and purely discrete or purely continuous action
spaces. Therefore, these algorithms cannot be applied directly to the problems
with actions involving both continuous and discrete variables. Since our
optimization problem includes both continuous and discrete optimization
variables, we can not directly use these algorithms. To overcome this
challenge, we utilize compound algorithm proposed by [37] which consists of
both DDPG and DQN algorithm for handling continuous and discrete actions,
respectively. The environment of our proposed model consists of both discrete
and continuous actions as VNF placement, subcarrier and transmit power
allocation, while the state-of-the-art DRL methods like DQN and DDPG can only
handle discrete and continuous actions, respectively. To overcome this
challenge, we apply CA2C which supports both discrete and continuous actions
simultaneously. Considering our optimization problem, we define the state
space $\mathcal{S}$, the action space $\mathcal{A}$, and the reward function
$R$ as follows:

  * •

State: We define the state space as a vector of residual resources in VNF
nodes, residual bandwidth on the links, the UL/DL channel conditions, the
number of requested services and the desired bit rate of requested services.
As a result, the state $s(t)\in\mathcal{S}$ at decision TS $t$ can be written
as
$s(t)=\left\\{\textbf{r}^{BW}(t),\textbf{r}^{M}(t),\textbf{r}^{C}(t),\textbf{g}(t),\bar{\textbf{R}}(t)\right\\}$
where
$\textbf{r}^{BW}(t)=[r^{BW}_{\acute{n}n}(t)],\textbf{r}^{M}(t)=[r^{M}_{n}(t)],\textbf{r}^{C}(t)=[r^{C}_{n}(t)],\textbf{g}(t)=[g^{h}_{mn}(t)],\bar{\textbf{R}}(t)=[\bar{R}^{k}_{m}(t)]$.

  * •

Action: The action space is defined as all possible placement and scheduling
policies for each VNF of an incoming service at decision TS $t$,
$u_{\acute{n}n}^{fkm}(t)$ and $v_{n}^{fkm}$, the transmit power and subcarrier
allocation for UL/DL access networks at decision TS $t$, $\rho^{hk}_{mn}$ and
$p^{hk}_{mn}$. Let $\mathcal{A}$ denote the system action space, the action
executed in the TS $t$, $a(t)\in\mathcal{A}$ is a vector defined as
$a(t)=\left\\{\textbf{u}(t),\textbf{v}(t),\boldsymbol{\rho}(t),\textbf{p}(t)\right\\}$,
where
$\textbf{u}(t)=[u_{\acute{n}n}^{fkm}(t)],\textbf{v}(t)=[v_{n}^{fkm}(t)],\boldsymbol{\rho}(t)=[\rho^{hk}_{mn}(t)],\textbf{p}(t)=[p^{hk}_{mn}(t)]$.

  * •

Reward: Since our objective in this paper is to jointly minimize the network
cost and average AoI of the destination users, so we define the reward
function as negative sum of total network cost and average AoI as follows:

$\displaystyle R(t)=\begin{cases}-\Theta_{3},&\text{if
(\ref{eq-u-1})-(\ref{eq-3}) are satisfied.}\\\
-\infty,&\text{otherwise}.\end{cases}$ (28)

Where
$\Theta_{3}={\xi\bar{\Delta}+\xi_{1}\Lambda_{1}+\xi_{2}\Lambda_{2}+\xi_{3}\Lambda_{3}+\xi_{4}\Lambda_{4}}$.
The negative infinity in reward function used in order to tell the agent how
much is important to choose actions in order to satisfy constraints (1) to
(6). In other words, if agent cannot satisfy the mentioned constraints, it
will be punished with very big negative reward. To handle the discrete VNF
placement and subcarrier allocation with the continuous transmit power
allocation, the optimal resource allocation selection policy is divided into
two parts, i.e., a policy for joint selecting the optimal node and proper
subcarriers (discrete actions), and a policy for selecting the optimal
transmit power allocation (continuous actions) [37]. The optimal selected node
and subcarriers, which maximizes the Q-function value for the current state
$s$ is determined as

$a(t)=\arg\max_{a(t)}Q^{*}(s(t),a(t);\boldsymbol{\theta};\pi^{*}(a(t)|s(t);\boldsymbol{\omega})),$
(29)

where policy $\pi^{*}(a(t)|s(t);\boldsymbol{\omega})$ provides the optimal
transmit power given state $s(t)$, selected node and subcarriers. The exact
estimation of policy functions, $Q^{*}(s(t),a(t);\boldsymbol{\theta})$ and
$\pi^{*}(a(t)|s(t);\boldsymbol{\omega})$ is time-consuming due to the high
dimensional state and action spaces. Therefore, neural networks are adopted to
approximate policy functions $Q^{*}$ and $\pi^{*}$. Moreover, the training of
the neural networks is done by combining the training methods used in the DQN
and DDPG algorithms. The DDPG algorithm is one of the policy-based RL
algorithms and is more compatible for large and continuous state and action
spaces. Under actor-critic architecture, this algorithm utilizes DNNs as
function approximators for finding deterministic policies that can map large
discrete or continuous states into continuous actions.

###  VI-B Proposed Multi-Agent Compound Action Actor-Critic Algorithm

Although the centralized single-agent (SA) methods can provide better
performance than distributed multi-agent (MA) methods, but they lead to large
signaling overhead specially in the environment with large state space.
However, in some environments like the proposed one in this paper, using
multiple copies of the same agents while cooperating with each other to solve
the shared problem may lead to get better results since each SA has limited
capacity to learn [12, 13]. In this section, we extend our solution to
distributed method in which there are $N$ agents which must cooperate with
each other to serve the arrived requested services and obtain maximum
cumulative shared reward. More precisely, we have multiple agents which have
access to all resources in the environment, i.e., each agent has options to
consume all network resources to serve it’s assigned service requests. Their
shared goal is serving as maximum number of services as possible while
satisfying their quality of service requirements and minimizing joint network
cost and average AoI of destination users. Fig. 3 shows an illustrating
example of the proposed MA scheme. As depicted in Fig. 3, three agents consume
the network resources in order to serve the service requests. Each service
request is assigned an agent with the same index, i.e., IoT1, IoT2 and IoT3
services are assigned to agent1, agent2 and agent3, respectively. The colors
are indicating that how much resource is used by each agent. For example, a
few amount of resource from the node number 4 in the Fig. 3 is just utilized
by agent2 (red color) and has high residual free resource (black color). It
should be mentioned that sometimes the agents may exceed the network resources
in order to serve the services and consequently, get negative rewards. Let
$\mathcal{S}_{n}(t)$ denote the n$th$ agent local observation defined as
$\mathcal{S}_{n}(t)=\left\\{\textbf{r}^{\text{BW}}_{n}(t),\textbf{r}^{\text{M}}_{n}(t),\textbf{r}^{\text{C}}_{n}(t),\textbf{g}_{n}(t),\bar{\textbf{R}}_{n}(t)\right\\}$,
and $\mathcal{A}_{n}(t)$ denotes the n$th$ agent local action at TS $t$ given
by
$\mathcal{A}_{n}(t)=\left\\{\textbf{u}_{n}(t),\textbf{v}_{n}(t),\boldsymbol{\rho}_{n}(t),\textbf{p}_{n}(t)\right\\}$.
Each agent interacts with the environment and takes its own action
$\mathcal{A}_{n}(t)$ based on its own observation
$s_{n}(t)\in\mathcal{S}_{n}(t)$ independent of the other agents and gets a
reward $r_{n}(t)$.

Figure 3: The proposed MA scenario. The colors show the resource usage by each
agent.

Therefore, in the proposed approach, agents do not need global information
which significantly reduces the signaling overhead. It should be noted that
each agent is considered as compound action actor-critic (CA2C) that is
defined in previous section. The proposed MA scheme is based on centralized
training and distributed execution. In the training phase, each agent sends
its own action and observation to the critic network, and then the critic
network uses all states including other agent’s observations and actions for
its own training. However, in the execution phase, each agent executes its
action according only receiving its own observation in order to maximize the
accumulated reward. To prevent the network from getting stuck in a bad local
optimum trap near the initial point, we use ornstein-uhlenbeck process to add
noise $\mathcal{M}_{n}(t)$ to the selected action to ensure that all actions
are explored [34]. The details of the MA-CA2C algorithm is described in
Algorithm 1.

Algorithm 1 MA-CA2C Algorithm

1:Initialize critic network $Q_{n}(s_{n}(t),a_{n}(t);\boldsymbol{\theta}_{n})$
and actor network $\pi_{n}(a_{n}(t)|s_{n}(t);\boldsymbol{\omega}_{n})$

2:Initialize target networks
$\acute{Q}_{n}(s_{n}(t+1),a_{n}(t+1);\acute{\boldsymbol{\theta}}_{n})$, and
$\acute{\pi}_{n}(a_{n}(t+1)|s_{n}(t+1);\acute{\boldsymbol{\omega}}_{n})$

3:Initialize reply buffer length with $D$

4:for episode from 1 to number of episodes do

5: Receive initial state $\textbf{s}(t)$

6: for Cycle from 1 to number of cycles do

7: for from 1 to the required samples do

8: Based on the current policy, select an action for agent

9: $n$ by
$a_{n}(t)=\pi_{n}(a_{n}(t)|s_{n}(t);\boldsymbol{\omega}_{n})+\mathcal{M}_{n}(t)$

10: Execute the action and observe the reward $r_{n}(t)$ by (28)

11: and the next state $s_{n}(t+1)$

12: if all the optimization problem constraints are satisfied

13: in states $s_{1}(t+1),\dots,s_{N}(t+1)$ then

14: save transition
$\textbf{s}(t),\textbf{a}(t),\textbf{s}(t+1),r_{1}(t),\dots,r_{N}(t)$ in $D$

15: end if

16: end for

17: for from 1 to number of train steps do

18: Sample a random minibatch of $M$ transitions from

19: replay buffer $D$

20: Update critic network by minimizing the loss function

21: Update actor network by the sampled policy gradient

22: Update the target networks.

23: end for

24: end for

25:end for

##  VII Computational Complexity and Convergence Analysis

The computational complexity of our proposed algorithm consists of two main
parts, i.e, the computational complexity of action selection and the
computational complexity of training process. The training processes of the
DLR methods are done in the offline mode, which is a widely used approach in
systems that requires low response time from learning algorithms. Similar to
the most recent papers in this era [38, 39, 40], all the results and values in
the figures of this paper are the ones that the agents converged after several
training episodes.

###  VII-A Computational Complexity of Action Selection

We assume that our neural network is a fully connected neural network with
fixed numbers of hidden layers and fixed numbers of neurons in each hidden
layer. The computational complexity of calculating the output of such neural
network for given an input is equal to the sum of the sizes of input and
output [41]. For our proposed algorithm, based on the states and actions
defined, for each agent, the sizes of the inputs of the critic and actor
networks are $N+1+M+MK$ and $(N-1)FKM+FKM+2HKM$, respectively. Thus, the
computational complexity of action selection and estimation of the Q-function
value for a state-action pair is $\mathcal{O}(NFKM)$. The estimation of the
Q-function values should be done at all $N$ agents, thus, the computational
complexity of action selection is $\mathcal{O}(N^{2}FKM)$.

###  VII-B Complexity of Training Process

In accordance to (29), the Q-function values of the K services should be
calculated and compared by the agents before the training step. Based on
previous section, the computational complexity of this step is
$\mathcal{O}(MBRK)$ where $M$ is the size of the training batch. In addition,
for a fully connected neural network in which the number of hidden layers and
neurons are fixed, the back-propagation algorithm complexity is related to the
product of the input size and the output size. For each node, the sizes of the
inputs of the critic and actor networks are $RK+K$ and $2RK$, respectively.
Moreover, for each agent, the sizes of the outputs of the critic and actor
networks are 1 and 2, respectively. Thus, the back-propagation algorithm
complexity is $\mathcal{O}(MBRK)$. Finally, the training process complexity is
$\mathcal{O}(MBRK)$.

###  VII-C Convergence Analysis

Our proposed algorithm is an extended version of Q-learning algorithm. For
Q-learning algorithm, if $\sum_{t=0}^{\infty}\alpha^{t}=\infty$ and
$\sum_{t=0}^{\infty}(\alpha^{t})^{2}<\infty$ are satisfied and
$|r^{t}(s^{t},a^{t})|$ be bounded, the Q-function converges to the optimal
Q-function as $t\rightarrow\infty$ with probability 1 [42]. An effective
approach to train neural networks is using of the inverse time decaying
learning rate in which using of the large learning rate in the first training
epochs prevents the network from getting stuck in a bad local optimum trap
near the initial point. Whereas, using the small learning rate in the last
training epochs converge the network to a good local optimum and prevents the
network from oscillation. We also analyze the convergence of our proposed
algorithm through simulations in Section VIII.

##  VIII Simulation Results and Discussion

In this section, the performance of our proposed algorithm is evaluated and
compared with two Greedy algorithms; Greedy-AoI and Greedy-cost. In Greedy-AoI
algorithm, the paths consisting of nodes and links, are sorted in ascending
order based on the latency that they can add to the services, and the arriving
service requests are placed on the paths which have lowest latency. Also, the
packets of the services are sorted based on their AoI in descending order and
the service with maximum AoI will be scheduled with highest priority. In
Greedy-cost algorithm, the paths consisting of nodes and links are sorted in
ascending order based on the average network cost that they can impose to the
network. The paths that result in lowest network cost will be used for
function placement. In the simulation, the impact of agent cooperation, the
number of nodes and the number of arrival services are evaluated on the
performance of the proposed model in terms of both cost and AoI minimization.
For performance evaluation, four different topologies consisting of 25, 50, 75
and 100 virtual nodes and 135, 270, 405 and 540 links are created and IIoT
devices are uniformly distributed in 1000$\times$1000 $m^{2}$ area. The other
simulation parameters are summarized in Table I.

Table I: Network Parameters Parameter | Description | Value
---|---|---
$M$ | Number of IIoT devices | 5
$N$ | Number of source/midle/destination vitual nodes | 5/15/5, 10/30/10, 15/45/15 ,20/60/20
$L$ | Number of virtual links | 135, 270, 405, 540
$C_{n}$ | The computing cpu resource in virtual node $n$ | Randomly between 1 to 2 GHz
$B_{n}$ | The storage capacity in virtual node $n$ | Randomly between 50 to 100 GB
$W_{l}$ | The available bandwidth on link $l$ | Randomly between 100 to 1000 Mbps
$K$ | Number of services | 5, 10, 15, 20
$H/\check{H}$ | Number of subcarriers | 10
$\bar{R}^{k}_{m}$ |  Minimum bit rate required for service $k$ of IIoT device $m$ | 50 Mbps
$N/A$ | Number of function(s) per service | Random (4 to 7)
$N/A$ | Number of packet(s) per service | Random (2 to 6)
$P_{\text{max}}$ | Maximum transmit power | 30 Watt
$\iota$ | TS interval | 0.5 s
$\alpha_{c}/\alpha_{a}$ | Critic/Actor initial learning rate | 0.005/0.001
$\gamma$ | Discount factor | 0.99
$N/A$ | Batch-size | 64
$B$ | Bandwidth | 15 MHz
$N_{0}$ | Noise power spectral | -170 dBm/Hz
$\kappa$ | Path loss component | 3.5
$\varepsilon$ | Exploration rate for DQN | 0.001
$\mathcal{M}_{t}$ | Exploration noise for Actor Critic | Ornstein-Uhlenbeck
$N/A$ | Activation function | ReLU
$N/A$ | Number of episodes | 60000
$N/A$ | Target network update frequency | 1000
$N/A$ | Number of hidden layers | 4
$N/A$ | Number of neurons in each layer | 512

The average episodic reward for our proposed model considering 25 total
virtual nodes, 135 total links and average 5 service request arrival rate is
depicted in Fig. 4 for different methods. As can be seen, by MA, our proposed
model can achieve better episodic reward compared to the other methods. The
reason is that in MA, we use multiple copies from SA to be trained in the
environment and therefore we have more capacity of training. On the other
hand, in early episodes, SA, i.e., CA2C has higher episodic reward and it
learns faster than MA-CA2C, because in early episodes in MA, the agents need
more training steps to cooperate. Also, CA2C can learn faster and obtain
higher episodic reward than DDPG, because we have both continuous and discrete
actions in the environment and DDPG only supports continuous actions. On the
other hand, DQN only supports discrete actions and since we use quantization
for supporting continuous actions, DQN has worst performance compared to the
other SA methods. As shown in Fig. 4, the convergence training episode for DQN
is lower than DDPG, i.e., DQN converges after 230 training episodes while DDPG
converges after 290 training episodes. This is expected since in DDPG agent
has infinite number of continuous actions rather than DQN that has finite
number of discrete actions. The high oscillation in the episodic reward for
DQN is because of quantization of the actions. Fig. 4 and Fig. 5 show the
average AoI of the destination user and average network cost for each training
episodes considering 25 total virtual nodes, 135 total links and average 5
service request arrival rate, respectively. From Fig. 4 and Fig. 5 it could be
observed that the DRL methods can significantly outperform the greedy
algorithms since they learn to predict the behavior of the network and
incoming service requests.

Figure 4: (a) Average episodic reward for our proposed model with different RL
methods. (b) Average AoI for the proposed model with different RL methods
compare to baseline Greedy. Figure 5: Average cost for our proposed model with
different RL methods compare to baseline Greedy.

Fig. 6 and Fig. 6 demonstrate the average AoI and network cost versus the
arrival rate of service requests with total virtual nodes equals to 25. As
observed from Fig. 6 and Fig. 6, increasing the service request rate, while
maintaining the total virtual nodes and links fixed to 25 and 135, compels the
agent to consume more network resources. Fig. 7 shows the acceptance rate
versus the number of service request with 25 virtual nodes and 135 links.
Although, as depicted the Greedy-AoI algorithm had accepted more service
requests than other RL methods, but it increases the network cost drastically
as shown in Fig. 6. It should be noted that our proposed solution jointly
minimizes the AoI and the network cost, so some service requests will be
rejected in order to decrease the network cost.

Figure 6: (a) Average AoI VS. The number of services arrived per TS with 25
virtual nodes and 135 links. (b) Average network cost VS. The number of
services arrived per TS with 25 virtual nodes and 135 links.

Fig. 7 and Fig. 8 show the AoI and network cost for 50 virtual nodes and 270
links, respectively. As expected, increasing the number of service request
from 5 to 20 causes to increase the AoI and network cost. Fig. 8 depicts the
acceptance rate comparison for 50 nodes and 270 links, while the service
request rate increases from 5 to 20. Since the capacity of SDN increases, the
acceptance rate improves, as well. For the sake of brevity, the other
simulation results for other nodes and service requests are not provided.

Figure 7: (a) Acceptance rate VS. The number of services arrived per TS with
25 virtual nodes and 135 links. (b) Average AoI VS. The number of services
arrived per TS with 50 virtual nodes and 270 links.

Figure 8: (a) Average cost VS. The number of services arrived per TS with 50
virtual nodes and 270 links. (b) Acceptance rate VS. The number of services
arrived per TS with 50 virtual nodes and 270 links.

##  IX Conclusion and Future Work

In this paper, we developed single-agent and cooperative multi-agent CA2C DRL-
based VNF placement and scheduling for virtualized IIoT network to minimize
VNF placement cost, scheduling cost, and average AoI. Our proposed single-
agent CA2C DRL-based VNF placement methods significantly outperform DDPG and
DQN methods and greedy algorithms in terms of average network cost and age of
information. In addition, due to the capacity limitation in the single agent
scheme, proposed cooperative multi-agent DRL is able to achieve higher reward.
As our future work, we plan to extend our proposed solutions to network
slicing where each type of user belongs to one slice. Network slicing
structure allows the creation of multiple virtual networks with different rate
and latency requirements atop a shared physical infrastructure.

## References

  * [1] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, “Internet of things (IoT): A vision, architectural elements, and future directions,” _Future generation computer systems_ , vol. 29, no. 7, pp. 1645–1660, September 2013.
  * [2] B. Zhou and W. Saad, “Joint status sampling and updating for minimizing age of information in the internet of things,” _IEEE Transactions on Communications_ , vol. 67, no. 11, pp. 7468–7482, July 2019.
  * [3] A. Al-Fuqaha, M. Guizani, M. Mohammadi, M. Aledhari, and M. Ayyash, “Internet of things: A survey on enabling technologies, protocols, and applications,” _IEEE communications surveys & tutorials_, vol. 17, no. 4, pp. 2347–2376, June 2015.
  * [4] B. Zhou and W. Saad, “Minimum age of information in the internet of things with non-uniform status packet sizes,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 3, pp. 1933–1947, March 2019.
  * [5] R. I. M. G. B. Vincent Francois-Lavet, Peter Henderson and J. Pineau, “An introduction to deep reinforcement learning,” _Foundations and Trends in Machine Learning_ , vol. 11, no. 4, pp. 219–354, December 2018.
  * [6] G. Marchetto, R. Sisto, J. Yusupov, and A. Ksentinit, “Formally verified latency-aware VNF placement in industrial internet of things,” in _Proceedings of IEEE International Workshop on Factory Communication Systems (WFCS)_ , Imperia, Italy, June 2018, pp. 1–9.
  * [7] J. Pei, P. Hong, K. Xue, and D. Li, “Efficiently embedding service function chains with dynamic virtual network function placement in geo-distributed cloud system,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 10, pp. 2179–2192, November 2018.
  * [8] 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_ , pp. 1–1, December 2020.
  * [9] Q. Wang, H. Chen, Y. Li, Z. Pang, and B. Vucetic, “Minimizing age of information for real-time monitoring in resource-constrained industrial IoT networks,” in _Proceedings of IEEE International Conference on Industrial Informatics (INDIN)_ , vol. 1, Helsinki, Finland, July 2019, pp. 1766–1771.
  * [10] A. Marotta, F. D’Andreagiovanni, A. Kassler, and E. Zola, “On the energy cost of robustness for green virtual network function placement in 5G virtualized infrastructures,” _Computer Networks_ , vol. 125, pp. 64–75, October 2017.
  * [11] J. Liu, Y. Li, Y. Zhang, L. Su, and D. Jin, “Improve service chaining performance with optimized middlebox placement,” _IEEE Transactions on Services Computing_ , vol. 10, no. 4, pp. 560–573, November 2015.
  * [12] M. Bowling, “Multi-agent learning in the presence of agents with limitations,” Computer Science, Tech. Rep., 2003.
  * [13] L. Panait and S. Luke, “Cooperative multi-agent learning: The state of the art,” _Autonomous agents and multi-agent systems_ , vol. 11, no. 3, pp. 387–434, November 2005.
  * [14] R. Solozabal, J. Ceberio, A. Sanchoyerto, L. Zabala, B. Blanco, and F. Liberal, “Virtual network function placement optimization with deep reinforcement learning,” _IEEE Journal on Selected Areas in Communications_ , vol. 38, no. 2, pp. 292–303, December 2019.
  * [15] Y. Xiao, Q. Zhang, F. Liu, J. Wang, M. Zhao, Z. Zhang, and J. Zhang, “NFVdeep: adaptive online service function chain deployment with deep reinforcement learning,” in _Proceedings of the International Symposium on Quality of Service_ , AZ, USA, June 2019, pp. 1–10.
  * [16] X. Shao, C. Yang, D. Chen, N. Zhao, and F. R. Yu, “Dynamic IoT device clustering and energy management with hybrid NOMA systems,” _IEEE Transactions on Industrial Informatics_ , vol. 14, no. 10, pp. 4622–4630, July 2018.
  * [17] I. Farris, T. Taleb, Y. Khettab, and J. Song, “A survey on emerging SDN and NFV security mechanisms for IoT systems,” _IEEE Communications Surveys & Tutorials_, vol. 21, no. 1, pp. 812–837, August 2018.
  * [18] X. Fu, F. R. Yu, J. Wang, Q. Qi, and J. Liao, “Service function chain embedding for NFV-enabled IoT based on deep reinforcement learning,” _IEEE Communications Magazine_ , vol. 57, no. 11, pp. 102–108, November 2019\.
  * [19] C. Pham, N. H. Tran, S. Ren, W. Saad, and C. S. Hong, “Traffic-aware and energy-efficient VNF placement for service chaining: Joint sampling and matching approach,” _IEEE Transactions on Services Computing_ , vol. 13, no. 1, pp. 172–185, January 2020.
  * [20] A. Suzuki, R. Kawahara, M. Kobayashi, S. Harada, Y. Takahashi, and K. Ishibashi, “Extendable NFV-integrated control method using reinforcement learning,” in _Proceedings of IEEE International Conference on Communications (ICC)_ , MO, USA, May 2018, pp. 221–226.
  * [21] M. Dieye, S. Ahvar, J. Sahoo, E. Ahvar, R. Glitho, H. Elbiaze, and N. Crespi, “CPVNF: Cost-efficient proactive VNF placement and chaining for value-added services in content delivery networks,” _IEEE Transactions on Network and Service Management_ , vol. 15, no. 2, pp. 774–786, March 2018.
  * [22] M. Abu-Lebdeh, D. Naboulsi, R. Glitho, and C. W. Tchouati, “On the placement of vnf managers in large-scale and distributed nfv systems,” _IEEE Transactions on Network and Service Management_ , vol. 14, no. 4, pp. 875–889, July 2017.
  * [23] A. Kosta, N. Pappas, V. Angelakis _et al._ , “Age of information: A new concept, metric, and tool,” _Foundations and Trends® in Networking_ , vol. 12, no. 3, pp. 162–259, November 2017.
  * [24] C. Xu, H. H. Yang, X. Wang, and T. Q. Quek, “Optimizing information freshness in computing enabled IoT networks,” _IEEE Internet of Things Journal_ , vol. 7, no. 2, pp. 971–985, October 2019.
  * [25] F. Wu, H. Zhang, J. Wu, L. Song, Z. Han, and H. V. Poor, “UAV-to-device underlay communications: Age of information minimization by multi-agent deep reinforcement learning,” _arXiv preprint arXiv:2003.05830_ , 2020.
  * [26] 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_ , pp. 1–1, 2020.
  * [27] Y.-L. Hsu, C.-F. Liu, S. Samarakoon, H.-Y. Wei, and M. Bennis, “Age-optimal power allocation in industrial iot: A risk-sensitive federated learning approach,” _arXiv preprint arXiv:2012.06860_ , 2020.
  * [28] A. Leivadeas, M. Falkner, I. Lambadaris, and G. Kesidis, “Resource management and orchestration for a dynamic service chain steering model,” in _Proceedings for IEEE Global Communications Conference (GLOBECOM)_ , Washington, USA, December 2016, pp. 1–6.
  * [29] K. T. K. Cheung, S. Yang, and L. Hanzo, “Achieving maximum energy-efficiency in multi-relay OFDMA cellular networks: A fractional programming approach,” _IEEE Transactions on Communications_ , vol. 61, no. 7, pp. 2746–2757, July 2013.
  * [30] M. R. Abedi, N. Mokari, M. R. Javan, and H. Yanikomeroglu, “Limited rate feedback scheme for resource allocation in secure relay-assisted OFDMA networks,” _IEEE Transactions on Wireless Communications_ , vol. 15, no. 4, pp. 2604–2618, April 2016.
  * [31] L. Liang, H. Ye, G. Yu, and G. Y. Li, “Deep-learning-based wireless resource allocation with application to vehicular networks,” _Proceedings of the IEEE_ , vol. 108, no. 2, pp. 341–356, February 2020.
  * [32] K. Arulkumaran, M. P. Deisenroth, M. Brundage, and A. A. Bharath, “Deep reinforcement learning: A brief survey,” _IEEE Signal Processing Magazine_ , vol. 34, no. 6, pp. 26–38, November 2017.
  * [33] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, no. 7540, pp. 529–533, February 2015.
  * [34] Y. Hou, L. Liu, Q. Wei, X. Xu, and C. Chen, “A novel DDPG method with prioritized experience replay,” in _Proceedings for IEEE International Conference on Systems, Man, and Cybernetics (SMC)_ , Banff, Canada, October 2017, pp. 316–321.
  * [35] 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 preprint arXiv:1509.02971_ , 2015.
  * [36] M. Yang, N. Liu, L. Zuo, Y. Feng, M. Liu, H. Gong, and M. Liu, “Dynamic charging scheme problem with actor-critic reinforcement learning,” _IEEE Internet of Things Journal_ , vol. 8, no. 1, pp. 370–380, January 2021\.
  * [37] J. Hu, H. Zhang, L. Song, R. Schober, and H. V. Poor, “Cooperative internet of UAVs: Distributed trajectory design by multi-agent deep reinforcement learning,” _IEEE Transactions on Communications_ , vol. 68, no. 11, pp. 6807–6821, November 2020.
  * [38] V. Saxena, J. Jalden, and H. Klessig, “Optimal UAV base station trajectories using flow-level models for reinforcement learning,” _IEEE Transactions on Cognitive Communications and Networking_ , vol. 5, no. 4, pp. 1101–1112, October 2019.
  * [39] H. A. Shah and L. Zhao, “Multi-agent deep reinforcement learning based virtual resource allocation through network function virtualization in internet of things,” _IEEE Internet of Things Journal_ , vol. 8, no. 5, pp. 3410–3421, September 2020.
  * [40] R. Li, Z. Zhao, Q. Sun, I. Chih-Lin, C. Yang, X. Chen, M. Zhao, and H. Zhang, “Deep reinforcement learning for resource management in network slicing,” _IEEE Access_ , vol. 6, pp. 74 429–74 441, November 2018.
  * [41] M. Sipper, “A serial complexity measure of neural networks,” in _Proceedings for IEEE International Conference on Neural Networks_ , CA, USA, March 1993, pp. 962–966.
  * [42] C. J. Watkins and P. Dayan, “Q-learning,” _Machine learning_ , vol. 8, no. 3-4, pp. 279–292, 1992.

|  Mohammad Akbari received his B.Sc. in Electrical Engineering in 2008 from
Tabriz University, Tabriz, Iran and the M.Sc. and Ph.D. degrees both from Iran
University of Science and Technology (IUST), Tehran, Iran in 2010 and 2016
respectively. During 2010-2017, he was a senior system designer at Afratab R&D
group, Tehran, Iran. In 2017, he joined as a research assistant professor to
the Department of Communication Technology, ICT Research Institute (ITRC),
Tehran, Iran. His current research interests span topics in telecommunication
system and networks including Self-Organizing Networks, 5G and 6G Networks and
application of Machine Learning techniques in wireless communication.
---|---
|  Mohammad Reza Abedi received the M.Sc. degree in electrical engineering
from AmirKabir University, Tehran, Iran. He is currently working as a Research
Assistant and phD student with Tarbiat Modares University, Tehran. He was a
Reviewer for several IEEE journals such as, the IEEE TRANSACTIONS ON SIGNAL
PROCESSING and IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS. He has been
involved in a number of large scale network design and consulting projects in
the telecom industry as a principle investigator or consultant. He was also a
Member of Technical Program Committees for the IEEE Conferences. His research
interests include multiple access techniques, energy harvesting and wireless
power transfer, cooperative and adaptive wireless communications, wireless
edge caching, mobile edge computing, multibitrate video transcoding, software
defined networking, wireless network virtualization, and optimization theory.
---|---
|  Roghayeh Joda (M’14) received the B.Sc. degree in electrical engineering
from Sharif University of Technology, Tehran, Iran, in 1998, and the M.Sc. and
the Ph.D. degrees in electrical engineering from University of Tehran, Tehran,
in 2001 and 2012, respectively. She was a Post-Doctoral Fellow at University
of Padua, Padua, Italy from September 2013 to August 2014. In November 2014,
she joined ICT research institute, Tehran, Iran as a research assistant
professor where she was the manager of two mega projects on 5G networks. She
is currently a visiting researcher at University of Ottawa, Ottawa, Canada.
Her current research interests include communication theory, information
theory, resource allocation, optimization and machine learning with
application to wireless networks, 5G and 6G networks
---|---
|  Mohsen Pourghasemian received the B.Sc. degree in electrical engineering
from Bu-Ali Sina University, Hamedan, Iran, and the M.Sc. degree in electrical
engineering from IRIB University, Tehran, Iran. From August 2016 to June 2018,
he has participated in 5G IoT projects as a consultant at ICT Research
Institute. He has been a lecturer at IRIB University from September 2018 to
present. He is currently working as a Research Assistant at Tarbiat Modares
University, Tehran, Iran. His research interests include wireless networks,
machine learning, autonomous driving, Internet of Things, wireless sensor
networks, and information theory.
---|---
|  Nader Mokari Yamchi completed his PhD studies in electrical Engineering at
Tarbiat Modares University, Tehran, Iran in 2014. He joined the Department of
Electrical and Computer Engineering, Tarbiat Modares University as an
assistant professor in October 2015. He was also involved in a number of large
scale network design and consulting projects in the telecom industry. His
research interests include design, analysis, and optimization of
communications networks.
---|---
|  Melike Erol-Kantarci is Tier 2 Canada Research Chair in AI-enabled Next-
Generation Wireless Networks and Associate Professor at the School of
Electrical Engineering and Computer Science at the University of Ottawa. She
is the founding director of the Networked Systems and Communications Research
(NETCORE) laboratory. She is also a Faculty Affiliate at the Vector Institute,
Toronto. She has received many awards and recognitions, delivered 50+
keynotes, plenary talks and tutorials around the globe. She is on the
editorial board of the IEEE Transactions on Cognitive Communications and
Networking, IEEE Internet of Things Journal, IEEE Communications Letters, IEEE
Networking Letters, IEEE Vehicular Technology Magazine and IEEE Access. She
has acted as the general chair and technical program chair for many
international conferences and workshops. Her main research interests are AI-
enabled wireless networks, 5G and 6G wireless communications, ORAN, smart
grid, and Internet of Things. She is a senior member of the IEEE and the ACM,
and a ComSoc Distinguished Lecturer.
---|---