# PoPeC: PAoI-Centric Task Offloading with Priority over Unreliable Channels

Nan Qiao, , Sheng Yue, , Yongmin Zhang, , Ju Ren, Nan Qiao and Yongmin Zhang
are with the School of Computer and Engineering, Central South University,
Changsha, Hunan, 410083 China. E-mails: {nan.qiao<EMAIL_ADDRESS>Sheng Yue and Ju Ren are with the Department of Computer Science and
Technology, BNRist, Tsinghua University, Beijing, 100084 China. E-mails:
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>Corresponding author:
Dr. Ju Ren.

###### Abstract

Freshness-aware computation offloading has garnered great attention recently
in the edge computing arena, with the aim of promptly obtaining up-to-date
information and minimizing the transmission of outdated data. However, most of
the existing work assumes that wireless channels are reliable and neglect the
dynamics and stochasticity thereof. In addition, varying priorities of
offloading tasks along with heterogeneous computing units also pose
significant challenges in effective task scheduling and resource allocation.
To address these challenges, we cast the freshness-aware task offloading
problem as a multi-priority optimization problem, considering the
unreliability of wireless channels, the heterogeneity of edge servers, and
prioritized users. Based on the nonlinear fractional programming and ADMM-
Consensus method, we propose a joint resource allocation and task offloading
algorithm to solve the original problem iteratively. To improve communication
efficiency, we further devise a distributed asynchronous variant for the
proposed algorithm. We rigorously analyze the performance and convergence of
the proposed algorithms and conduct extensive simulations to corroborate their
efficacy and superiority over the existing baselines.

###### Index Terms:

distributed task offloading, edge computing, channel allocation, system
freshness

##  I Introduction

Edge computing is an attractive computing paradigm in the era of the Internet
of Things (IoT) [1, 2, 3]. By enabling end devices to offload computation-
intensive tasks to nearby edge nodes, edge computing is envisioned to provide
real-time computing services, thereby facilitating the deployment of a wide
range of intelligent applications (e.g., smart homes, smart cities, and
autonomous vehicles) [4]. For these applications, it is of paramount
importance to promptly obtain up-to-date information and minimize the
transmission of outdated and worthless data [5]. To this end, a great number
of offloading solutions have been proposed to achieve timely status updates
and rapid delivery of tasks from information sources, in order to enhance the
freshness performance [6, 7, 8, 9, 10].

Recently, the Age of Information (AoI) and Peak Age of Information (PAoI) have
been recognized as important metrics for evaluating information freshness,
which characterizes the elapsed time since the reception of a user’s most
recent data packet [11]. Based on AoI and PAoI, recent research has been
focused on freshness-aware offloading methods. Some works aim to optimize the
allocation of wireless channels for efficient and concurrent transmission of
freshness-sensitive information to a local server [12, 8, 13, 14, 15, 10, 5,
7, 6, 9]. Other studies investigate offloading strategies for distributing
fresh tasks from multiple sources to a collection of edge servers [16, 17, 18,
19].

Unfortunately, several obstacles still need to be overcome for achieving
effective freshness-aware offloading. First, many existing works assume
channel homogeneity [20, 9] or perfect knowledge of channel states [10, 21],
overlooking the dynamics and stochasticity of the limited wireless channels in
the real world. As a result, such methods easily suffer from package loss or
failure due to unreliable communication [15]. Second, computing resources on
edge servers are typically constrained and heterogeneous. It is of importance
to appropriately assign heterogeneous computing units to offloading tasks,
whereas often being neglected in literature [9, 22, 23, 24]. More importantly,
designing a prioritized offloading strategy is crucial since users may have
diverse freshness requirements. For example, safety-sensitive devices like
temperature sensors in the Industrial Internet of Things and Automatic
Emergency Braking (AEB) in autopilot require prompt offloading and processing
to meet their high freshness demands. However, most existing methods struggle
with measuring and handling the situations where the offloading tasks have
different priorities. In light of these considerations, this work seeks to
answer the key question: “How to design an efficient task offloading algorithm
that can optimize the system information freshness while effectively handling
prioritized users, unreliable channels, and heterogeneous edge servers?”

To this end, we cast the freshness-aware task offloading problem as a multi-
priority optimization problem, considering the unreliability of wireless
channels, the heterogeneity of edge servers, and the interdependence of
multiple users with varying priorities. As optimizing this problem directly is
highly nontrivial, we first examine two special cases of the original problem.
We exploit nonlinear fractional programming to transform the problems into
tractable forms and then develop ADMM-Consensus-based solutions for both
cases. Built upon these solutions, an iterative algorithm is devised for
resolving the original problem effectively. We further discuss a distributed
asynchronous variant of the proposed algorithm, capable of alleviating the
overhead caused by unreliable iterations during the offloading policy
acquisition process. Theoretical analysis is carried out to establish the
convergence property of the proposed algorithm and demonstrate the improvement
in performance brought by the multi-priority mechanism. In a nutshell, our
main contributions can be summarized as follows.

  * •

We consider an M/G/1 offloading system and derive the precise Peak Age of
Information (PAoI) expression for each user to characterize their information
freshness. Then, we formulate the freshness-aware multi-priority task
offloading problem under heterogeneous users and unreliable channels.

  * •

Based on nonlinear fractional programming and ADMM-Consensus method, we
propose a joint resource allocation, service migration, and task offloading
algorithm to solve the original problem effectively. We further devise a
distributed asynchronous variant for the proposed algorithm to improve the
communication efficiency.

  * •

We establish theoretical guarantees for the proposed algorithms, in terms of
performance and convergence. Extensive experiments are carried out and show
that our algorithm can significantly improve the performance over the existing
methods.

The remainder of the paper is organized as follows: Section II briefly reviews
the related work. Section III introduces the system model, including relevant
definitions and models. In Section IV, we describe some special cases and
propose algorithms to tackle the PoPeC problem. Section V proposes an
asynchronous parallel algorithm to improve communication efficiency and
discusses the benefits of the multi-class priority mechanism. Section VI
presents the simulation results, followed by a conclusion drawn in Section
VII.

##  II Related Work

A great number of task offloading methods have been proposed to minimize the
response delay in edge computing [25, 26, 27, 28, 29]. However, reducing delay
solely may not be sufficient for effective real-time computation offloading as
it hardly guarantees the information freshness for users [30, 11]. Recently,
many freshness-aware methods have been developed based on the metrics of AoI
and PAoI [13, 14, 31, 5, 6, 7, 8, 9, 10], which can be divided into the
following two aspects.

Part of the recent work focus on computation offloading with regard to various
user types and needs. [10, 6, 5, 7, 32, 33, 34, 35, 36, 37, 38, 39]. Zou et
al. [5] address the accurate specification of indexing problems in
heterogeneous multi-user multi-channel systems by introducing a unique
partial-index approach. They also propose SWIM, which employs maximum weights
to obtain the allocation strategy of heterogeneous resources. Sun et al. [7]
design an age-aware scheduling strategy for diverse users based on the
Lyapunov optimization method and provide upper and lower bounds on the age
that can satisfy the throughput constraint. Nevertheless, these works overlook
the priorities of users, which is crucial for practical prioritized systems
[10, 6, 5, 7, 32, 33]. Liu et al. [35] improve the performance of message
state freshness from a single server queue considering preemptive and priority
message scheduling. Maatouk et al. [37] propose three scheduling strategies
for AoI, a measure of information freshness, and propose optimization schemes
such as advanced AoI strategies for preemption, strategies for service
preemption, and strategies for information update. Xu et al. [39] investigated
the system using four different service rules with different priorities and
determined the exact PAoI values or upper bounds for various users. By
conducting theoretical analysis, they identified the optimal service rule.
However, most of these studies lack analysis of heterogeneous users and focus
on the case of a single edge server, which cannot meet the individual
heterogeneous computing needs [34, 35, 36, 37, 38, 39].

Existing works also provide several comprehensive descriptions of various
channel features. The majority of earlier analyses have assumed a homogeneous
channel or the unloading of two separate channels in the broadcast network
with random arrival [20, 10, 9]. This assumption only offers a few expansions
to the case of a single channel, hence it was not the best choice for
heterogeneous channels, in practice. In addition, Adb et al. [40] and Hse et
al. [22] investigate real-time monitoring systems in reliable multiple
channels. The aforementioned suggest methods did not work for systems with
unstable channel circumstances, which were formerly brought on by antenna
beamforming, position-dependent fading, and frequency selectivity [23, 24]. To
replace the setting of the unreliable channel, Pan et al. [10] and Sombabu et
al. [21] propose the ON/OFF strategy in the system. This technique made the
harsh assumption that the channels were trustworthy and that the conditions of
the channel had been understood prior to the decision being made. More
notably, many similar studies believe that the distributed method would make
the procedure less time-consuming, whereas they all disregard the synchronous
parallel iterative algorithm’s substantial communication cost on the
unreliable channel [7, 5, 6]. This paper differs from [20, 10, 9] in that we
focus on multiple heterogeneous channels system, from [40, 22] in that we
consider the channel is unreliable, from [10, 21] in that we address the
scheduling decision when the channel states were unknown, and from [7, 5, 6]
in that we analyze how the synchronous parallel algorithm’s significant
iteration overhead in the unreliable channel might be resolved and offer an
asynchronous parallel algorithm as a possible alternative.

##  III System Model

In this section, we focus on the Mobile Edge Computing (MEC) architecture,
including task offloading, transmission models, capacity models, and
confidence evaluation. Based on this, we present the information freshness
model and problem formulation.

Figure 1: System Model

###  III-A MEC Architecture

As shown in Fig.1, we consider a wireless network system consisting of a set
of $M$ mobile edge servers (denoted by $\mathcal{M}$). Each server
$m\in\mathcal{M}$ can serve a set of $N_{m}$ users ($\mathcal{N}_{m}$). Each
user $n\in\mathcal{N}$ can offload their tasks to its corresponding server
$m_{n}$ via a limited number of wireless channels (denoted by
$\mathcal{C}\doteq\\{1,\dots,C\\}$). Considering the effects of frequency-
selective fading [5], we define $p_{n,c}$ as the probability of a successful
transmission from user $n$ through channel $c$ to server $m_{n}$. In this
context, users have varying offloading priorities, which we represent as
$\Delta\doteq\\{1,2,\dots,\delta_{\mathit{max}}\\}$. Let
$\mathcal{N}^{\delta}_{m}$ denote the set of users served by server $m$ with
priority $\delta\in\Delta$. It satisfies
$\bigcup_{m\in\mathcal{M}}\bigcup_{\delta\in\Delta}\mathcal{N}^{\delta}_{m}=\bigcup_{m\in\mathcal{M}}\mathcal{N}_{m}=\mathcal{N}$.
In addition, we represent
$\mathcal{N}^{\delta}\doteq\bigcup_{m\in\mathcal{M}}\mathcal{N}^{\delta}_{m}$
as the set of users with priority $\delta$ across all servers. To simplify
notation, we denote the priority of user $n$ as $\delta(n)$ and the set of
users with a same or higher priority as $\Delta(\delta(n))$.

####  III-A1 Task Offloading

Each user has a set of offloading tasks, which arrive according to a Poisson
process with an expected arrival rate of $\lambda_{n}$. We use
$\eta^{u}_{n,c}$ to denote the probability of user $n$ accessing channel $c$
for offloading the tasks, which should satisfy the following constraint:

$0\leq\eta^{u}_{n,c}\leq 1,\quad\forall n\in\mathcal{N},~{}c\in\mathcal{C}.$
(1)

It is clear that the number of tasks offloaded by user $n$ through channel $c$
follows a Poisson progress with an expected value of
$\eta^{u}_{n,c}\cdot\lambda_{n}$. Besides, the following constraint must be
met:

$\sum_{c\in\mathcal{C}}\eta^{u}_{n,c}\leq 1,\quad\forall n\in\mathcal{N}.$ (2)

The inequality in Eq. (2) being true indicates that user $n$ does not offload
any tasks.

Edge servers are connected to each other via a wired network and can
collaborate to execute offloaded tasks by assigning a portion of tasks from
one server to another. We use $\eta^{s}_{m,m^{\prime}}$ to denote the
proportion of tasks delivered from server $m$ to server $m^{\prime}$, and we
have

$0\leq\eta^{s}_{m,m^{\prime}}\leq 1,\quad\forall m,m^{\prime}\in\mathcal{M}.$
(3)

It is easy to see the following constraint should also be met:

$\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m,m^{\prime}}=1,\quad\forall
m\in\mathcal{M}.$ (4)

Accordingly, the number of computational tasks with priority $\delta$
delivered from server $m$ to $m^{\prime}$ can be expressed as
$\eta^{s}_{m,m^{\prime}}\cdot\lambda^{s}_{\delta,m}$, where

$\lambda^{s}_{\delta,m}\doteq\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in\mathcal{C}}p_{n,c}\lambda_{n,c}$
(5)

denotes the total number of received tasks with priority $\delta$ at server
$m$. Since the total number of tasks arrived at each server cannot exceed its
maximum capacity (denoted by $\lambda^{s,\mathit{max}}_{m}$), we have

$\sum_{\delta\in\Delta}\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m^{\prime},m}\lambda^{s}_{\delta,m^{\prime}}\leq\lambda^{s,\mathit{max}}_{m},\quad\forall
m\in\mathcal{M}.$ (6)

####  III-A2 Transmission Model

We assume that the channel contention and waiting time follow the M/M/1
queuing model, as in [41].111The contention and queuing process for multiple
tasks for each channel can be modeled as an M/M/1 process, where task arrivals
to a certain channel follow a Poisson process, and the channel transmission
time (service time) for each task follows an exponential distribution. The
arrival rate of channel $c$ is denoted as $\lambda_{c}$, which is calculated
as the sum of the offloading arrival rates of all users accessing channel $c$,
i.e., $\lambda_{c}=\sum_{n\in\mathcal{N}}\eta^{u}_{n,c}\lambda_{n}$. The
service rate of channel $c$ is $r_{c}/S$, where $r_{c}$ and $S$ represent the
communication rate and the size of each package transmitted through channel
$c$, respectively. As the wireless communication rate approaches the Shannon
limit [42, 43], the achievable rate can be expressed as
$r_{c}=B_{c}\log\bigl{(}R_{c}+1\bigr{)}$, where $B_{c}$ and $R_{c}$ are the
bandwidth and the signal-to-noise ratio of channel $c$, respectively. Thus, if
user $n$ accesses channel $c$, the induced transmission time is

$T^{\mathit{tr}}_{n,c}=\left\\{\begin{array}[]{ll}\frac{1}{r_{c}/S-\lambda_{c}}+t_{n,c},&\quad\frac{r_{c}}{S}-\lambda_{c}>0,\\\
\infty,&\quad\mathit{otherwise},\end{array}\right.$ (7)

where $\frac{1}{r_{c}/S-\lambda_{c}}$ is the channel contention time, and
$t_{n,c}$ is the transmission delay of the offloading tasks [44]. As in [45],
since MEC servers are linked via wired core networks, we assume that the
transmission delay between servers $m$ and $m^{\prime}$ is a constant, denoted
by $t^{\mathit{tr}}_{m,m^{\prime}}$.

###  III-B Limited Capacity Model with Confidence Evaluation

####  III-B1 Channel Capacity

Due to the limited channel capacity, the total number of tasks transmitted
through a channel cannot exceed its maximum capacity ($M_{c}^{\mathit{max}}$).
Based on the properties of the cumulative distribution function of the Poisson
distribution [46], we use the following constraint to ensure that each channel
is conflict-free with confidence level $1-\alpha$ [47, 6]:

$\frac{z^{2}_{1}}{2}+z_{2}\cdot\left(\sum_{n\in\mathcal{N}}\eta^{u}_{n,c}\lambda_{n}+\frac{z^{2}_{2}}{4}\right)^{\frac{1}{2}}+\sum_{n\in\mathcal{N}}\eta^{u}_{n,c}\lambda_{n}\leq
M_{c}^{\mathit{max}},$ (8)

where $z_{1}$ and $z_{2}$ are two statistics standardized from a normal
distribution, satisfying
$z_{1}=(\alpha/2-\lambda^{\mathit{chl}}_{c})/\sqrt{\lambda^{\mathit{chl}}_{c}}$
and
$z_{2}=(1-\alpha/2-\lambda^{\mathit{chl}}_{c})/\sqrt{\lambda^{\mathit{chl}}_{c}}$,
respectively. Here,
$\lambda^{\mathit{chl}}_{c}\doteq\sum_{n\in\mathcal{N}}\eta^{u}_{n,c}\lambda_{n}$
represents the total number of tasks transmitted through channel $c$.

$\displaystyle\mathbb{E}[W_{n}]=\,$
$\displaystyle\frac{\frac{1}{2}\sum_{\delta\in\Delta}\sum_{n^{\prime}\in\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}\nu_{n^{\prime}}}{\left(1-\sum_{\delta\in\Delta(\delta(n))}\sum_{n^{\prime}\in\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\frac{\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}}{\mu_{n^{\prime}}}\right)\left(1-\sum_{\delta\in\Delta(\delta(n)-1)}\sum_{n^{\prime}\in\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\frac{\lambda_{n^{\prime},c}}{\mu_{n^{\prime}}}\right)}$
(9) $\displaystyle\pi_{n,m}(\bm{\eta}^{s})\doteq\,$
$\displaystyle\frac{\sum_{\delta\in\Delta}\eta^{s}_{m_{n},m}\lambda^{s}_{\delta,m_{n}}}{\sum_{\delta\in\Delta}\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m_{n},m^{\prime}}\lambda^{s}_{\delta,m_{n}}}\cdot\left(t^{\mathit{tr}}_{m_{n},m}+\frac{1}{\mu_{n,m}}+\frac{1}{1-\sum_{\delta\in{\Delta(\delta(n))}}\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m^{\prime},m}\lambda^{s}_{\delta,m^{\prime}}\frac{1}{\mu_{n,m}}}\right.$
$\displaystyle\left.\cdot\frac{\frac{1}{2}\sum_{\delta\in\Delta}\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m^{\prime},m}\lambda^{s}_{\delta,m^{\prime}}\nu_{n,m}}{1-\sum_{\delta\in{\Delta(\delta(n)-1)}}\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m^{\prime},m}\lambda^{s}_{\delta,m^{\prime}}\frac{1}{\mu_{n,m}}}\right)$
(10)

####  III-B2 Computation Capacity

Due to the fluctuation in servers’ computing capacity, we assume that server
$m$’s processing time for user $n$’s tasks follows a general distribution with
mean $1/\mu_{n,m}$ and second moment $\nu_{n,m}$ [34]. To simplify notations,
we use $1/\mu_{n}$ and $\nu_{n}$ to represent $1/\mu_{n,m_{n}}$ and
$\nu_{n,m_{n}}$, respectively. We impose the following constraint to ensure
that each task can be executed with a confidence level of $1-\beta$:

$\begin{split}\frac{z^{2}_{3}}{2}&+z_{4}\cdot\left(\sum_{n\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n,c}\cdot\frac{\eta^{u}_{n,c}\lambda_{n}}{\mu_{n}}+\frac{z^{2}_{4}}{4}\right)^{\frac{1}{2}}\\\
&+\sum_{n\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n,c}\cdot\frac{\eta^{u}_{n,c}\lambda_{n}}{\mu_{n}}<1,\end{split}$
(11)

where $z_{3}$ and $z_{4}$ are two statistics standardized from a normal
distribution, satisfying
$z_{3}=(\beta/2-\lambda^{\mathit{comp}}_{c})/\sqrt{\lambda^{\mathit{comp}}_{c}}$
and
$z_{4}=(1-\beta/2-\lambda^{\mathit{comp}}_{c})/\sqrt{\lambda^{\mathit{comp}}_{c}}$,
respectively. Here,
$\lambda^{\mathit{comp}}=\sum_{n\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n,c}\cdot\eta^{u}_{n,c}\lambda_{n}/\mu_{n}$
represents the total number of reliable tasks that actually arrive at the
server $m(n)$.

###  III-C Freshness Model and Problem Formulation

We characterize the information freshness using the PAoI metric. The PAoI of
user $n$’s message, denoted by $A_{n}$, is determined by four key factors:
transmission time $T_{n}$, arrival interval $I_{n}$, waiting time $W_{n}$, and
processing time $Y_{n}$ [5], i.e.,

$\displaystyle\mathbb{E}[A_{n}]$
$\displaystyle=\mathbb{E}[T_{n}]+\mathbb{E}[I_{n}]+\mathbb{E}[W_{n}]+\mathbb{E}[Y_{n}].$
(12)

It is evident that
$\mathbb{E}[T_{n}]=\sum_{c\in\mathcal{C}}\eta^{u}_{n,c}T^{\mathit{tr}}_{n,c}$
and
$\mathbb{E}[I_{n}]=1/\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}$.
However, the expressions of $\mathbb{E}[W_{n}]$ and $\mathbb{E}[Y_{n}]$ depend
on the way in which user $n$’s tasks are executed. To establish their precise
expressions, we first use binary variable $y_{m}$ to denote the migration
decision of server $m$, i.e.,

$y_{m}\in\\{0,1\\},\quad\forall m\in\mathcal{M}.$ (13)

If $y_{m}$ comes to 0, server $m$ will execute its tasks locally; otherwise,
server $m$ will resort to the other servers for collaboration. When
$y_{m_{n}}$ is equal to 0, it is evident that
$\mathbb{E}[Y^{p}_{n}]=1/\mu_{n}$. Due to the M/G/1 queuing model, the
expectation of waiting time $\mathbb{E}[W_{n}]$ can be expressed as (9)
(please see Appendix A of technical report [48] for more details). When
$y_{m_{n}}$ comes to 1, some tasks from user $n$ will be migrated from server
$m_{n}$ to other servers. According to Little’s Law222Little’s law in queuing
theory states that the average number of customers in a stationary system
equals the product of arrival rate and waiting time [49]., we can derive:

$\mathbb{E}[W^{s}_{n}]+\mathbb{E}[Y^{s}_{n}]=\sum_{m\in\mathcal{M}}\pi_{n,m}(\bm{\eta}^{s}),$
(14)

where
$\bm{\eta}^{s}\doteq\\{\eta^{s}_{m,m^{\prime}}\\}_{m,m^{\prime}\in\mathcal{M}}$
and $\pi_{n,m}(\bm{\eta}^{s})$ is defined in (10). Based on this, the expected
PAoI of user $n$ can be specified as follows:

$\displaystyle\mathbb{E}[A_{n}]=(1-y_{m_{n}})\cdot\mathbb{E}[A_{n}|y_{m_{n}}=0]+y_{m_{n}}\cdot\mathbb{E}[A_{n}|y_{m_{n}}=1]$
(15)

Given the aforementioned constraints, our objective is to find the optimal
offloading decision for users and collaboration decision for servers to
minimize the average expected PAoI across all users. Consequently, the problem
of PAoI-Centric Task Offloading with Priority over Unreliable Channels (PoPeC)
is described below:

$\begin{split}&\textbf{(PoPeC)}~{}\mathop{\min}_{\bm{\eta}^{u},\bm{\eta}^{s},\bm{y}}\frac{1}{N}\sum_{n\in\mathcal{N}}\mathbb{E}[A_{n}]\\\
&\qquad\quad\text{s.t.}~{}\eqref{eq:c1}\textrm{--}\eqref{eq:c4a},\eqref{eq:c7a},\eqref{eq:c8a},\eqref{eq:c-y}\end{split}$
(16)

where
$\bm{\eta}^{u}\doteq\\{\eta^{u}_{n,c}\\}_{n\in\mathcal{N},c\in\mathcal{C}}$
denotes the offloading decision, and
$\bm{\eta}^{s}=\\{\eta^{s}_{m,m^{\prime}}\\}_{m,m^{\prime}\in\mathcal{M}}$
along with $\bm{y}\doteq\\{y_{m}\\}_{m\in\mathcal{M}}$ is the collaboration
decision.

##  IV PoPeC: PAoI-Centric Task Offloading with Priority over Unreliable
Channels

In light of the difficulty in directly solving the offloading problem, this
section begins by examining two special cases in Sections IV-A and IV-B, i.e.,
priority-free and multi-priority task scheduling with no server collaboration.
Based on their solutions, we devise the algorithm for optimizing the original
problem in Section IV-C.

###  IV-A Priority-Free Task Scheduling

####  IV-A1 Problem Transformation

The antecedent problem of the original problem pertains to a special case,
where tasks belong to the same type with no priorities, and solely focus on
the tasks offloading to the local server. To tackle this problem, we first
determine the expected PAoI of each user in this case. Since each user’s task
arrivals follow a Poisson distribution and task execution times follow a
general distribution, we can re-evaluate the waiting time based on (9) as
follows:

$\mathbb{E}[W_{n}]=\frac{\sum_{n\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}\nu_{n}}{2\cdot\left(1-\sum_{n\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n,c}\cdot\frac{\eta^{u}_{n,c}\lambda_{n}}{\mu_{n}}\right)}$
(17)

We introduce an auxiliary variable, denoted by $\hat{t}^{\mathit{tr}}_{n}$
($\hat{t}^{\mathit{tr}}_{n}>0$), to represent the upper bound of user $n$’s
transmission time through all the available channels, i.e.

$\hat{t}^{\mathit{tr}}_{n}\geq T^{\mathit{tr}}_{n,c},\quad\forall
c\in\mathcal{C}.$ (18)

Similar to [50, 51], we can transform the original problem into a tractable
form, i.e., optimizing a tight upper bound of user $n$’s expected PAoI:

(P1)
$\displaystyle\mathop{\min}_{\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u}}\frac{1}{N}\sum_{n\in\mathcal{N}}f_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})$
(19) s.t.
$\displaystyle~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c7a},\eqref{eq:c8a},\eqref{eq:c6}$

where $f_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})$ is defined as:

$\displaystyle f_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})\doteq\,$
$\displaystyle\frac{\sum_{n\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}\nu_{n}}{2\cdot\left(1-\sum_{n\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n,c}\cdot\frac{\eta^{u}_{n,c}\lambda_{n}}{\mu_{n}}\right)}$
$\displaystyle+\hat{t}^{\mathit{tr}}_{n}+\frac{1}{\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}}+\frac{1}{\mu_{n}}$
(20)

In the same spirit of min-max optimization, we can increase the communication
efficiency across all channels by minimizing $\hat{t}^{\mathrm{tr}}_{n}$
instead of $\mathbb{E}[T_{n}]$, thereby enhancing the robustness of our
proposed solution.

The nature of (8) and (11) suggests that P1 is a non-convex problem. To
identify well-structured solutions, we first transform this constraints into
equivalent convex ones.

######  Lemma 1.

In Problem P1, Constraints (8) and (11) are equivalent to Constraints (21) and
(22), i.e.,

$\displaystyle\sum_{n\in\mathcal{N}}\eta^{u}_{n,c}\lambda_{n}\leq
M_{c}^{\mathit{max}}+\frac{z^{2}_{2}}{2}-\frac{z^{2}_{1}}{2}-z_{2}\cdot\left(M_{c}^{\mathit{max}}+\frac{z^{2}_{2}}{2}-\frac{z^{2}_{1}}{2}\right)^{\frac{1}{2}},$
(21)
$\displaystyle\sum_{n\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n,c}\frac{\eta^{u}_{n,c}\lambda_{n}}{\mu_{n}}\leq
1+\frac{z^{2}_{4}}{2}-\frac{z^{2}_{3}}{2}-z_{4}\cdot\left(1+\frac{z^{2}_{4}}{2}-\frac{z^{2}_{3}}{2}\right).$
(22)

###### Proof.

The detailed proof can be found in Appendix B of technical report [48]. ∎

According to Lemma 1, Constraints (21) and (22) restrict the decision
variables to convex sets. Therefore, Problem P1 can be rewritten as:

(P1-1)
$\displaystyle\mathop{\min}_{\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u}}\frac{1}{N}\sum_{n\in\mathcal{N}}\left(\hat{t}^{\mathit{tr}}+\frac{1}{\Psi_{n}(\bm{\eta}^{u})}+\frac{\upsilon_{n}(\bm{\eta}^{u})}{\phi_{n}(\bm{\eta}^{u})}+\frac{1}{\mu}\right)$
(23) s.t.
$\displaystyle~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b}$

where we denote
$\upsilon_{n}(\bm{\eta}^{u})\doteq\frac{1}{2}\sum_{n^{\prime}\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\cdot\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}\nu$,
$\phi_{n}(\bm{\eta}^{u})\doteq
1-\sum_{n^{\prime}\in\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\cdot\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}/\mu$,
and
$\Psi_{n}(\bm{\eta}^{u})\doteq\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}$.

######  Theorem 1.

Problem P1-1 is a convex problem.

###### Proof.

The constraints of P1-1 are convex sets because they are affine sets.
Furthermore, we demonstrate the convexity of all sub-functions in Appendix C
of technical report [48]. ∎

Based on the convexity of Problem P1-1, we can employ the ADMM technique to
solve this problem, which is discussed in the following section.

####  IV-A2 Problem Decomposition and Solving

Built upon the transformed problem P1-1, we define $g_{n}(\bm{x})$ as follows:

$\displaystyle
g_{n}(\bm{x})\doteq\left\\{\begin{array}[]{ll}\hat{t}^{\mathit{tr}}+\frac{1}{\Psi_{n}(\bm{\eta}^{u})}+\frac{\upsilon_{n}(\bm{\eta}^{u})}{\phi_{n}(\bm{\eta}^{u})}+\frac{1}{\mu},&\bm{x}\in\Omega,\\\
\infty,&\text{otherwise.}\end{array}\right.$ (26)

where $\bm{x}\doteq\\{\hat{t}^{\mathit{tr}},\bm{\eta}^{u}\\}$ denotes the
decision variables, and
$\Omega\doteq\\{\bm{x}|\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b}\\}$
is the feasible set of Problem P1-1. Thus, P1-1 is equivalent to the following
consensus problem:

$\displaystyle\textbf{(P1-2)}~{}\mathop{\min}_{\\{\bm{x}_{n}\\}}~{}~{}$
$\displaystyle\sum_{n\in\mathcal{N}}g_{n}(\bm{x}_{n})$ (27) s.t.
$\displaystyle~{}\bm{x}_{n}=\bm{x}_{o}$ (28)

According to Theorem 1, it is clear that the well-known ADMM-Consensus
algorithm can be used to obtain the optimal solution of Problem P1-2[52]. For
a detailed description of the algorithm, please refer to Appendix D of
technical report [48].

###  IV-B Multi-Priority Task Scheduling

####  IV-B1 Problem Transformation with Nonlinear Fractional Programming

Different from priority-free task scheduling in the previous section, we delve
deeper into the multi-priority task scheduling problem in this section. In
this case, according to the priorities of received tasks, servers will execute
the tasks with higher priorities more promptly. Since the multi-priority task
scheduling in this case is indeed NP-Hard (see [53]), similar to Problem P1,
we aim to minimize a tight upper bound for the average expected PAoI of multi-
priority users, as follow:

(P2)
$\displaystyle\mathop{\min}_{\bm{x}}\frac{1}{N}\sum_{n\in\mathcal{N}}f^{p}_{n}(\bm{x})$
(29) s.t.
$\displaystyle~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c7a},\eqref{eq:c8a},\eqref{eq:c6},$

where
$f^{p}_{n}(\bm{x})=\hat{t}^{\mathit{tr}}+\frac{1}{\mu_{n}}+\frac{1}{\Psi_{n}(\bm{x})}+\frac{\Upsilon(\bm{x})}{\Phi_{\delta(n)}(\bm{x})\Phi_{\delta(n)-1}(\bm{x})}$
is the upper bound of $\mathbb{E}[A_{n}]$,
$\bm{x}=\\{\hat{t}^{\mathit{tr}},\bm{\eta}^{u}\\}$ denotes the decision
variables,
$\Phi_{\delta(n)}(\bm{x})=1-\sum_{\delta\in\Delta(\delta(n))}\sum_{n^{\prime}\in\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}/\mu_{n^{\prime}}$,
$\Upsilon(\bm{x})=\frac{1}{2}\sum_{\delta\in\Delta}\sum_{n^{\prime}\in\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}\nu_{n^{\prime}}$,
and $\Psi_{n}(\bm{x})=\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}$.
To obtain the effective offloading decision in this case, we next transform
the original problem and decouple users’ offloading decisions.

First, we define $\theta_{n}\doteq
f^{p,u}_{n}(\bm{x}_{n})/f^{p,l}_{n}(\bm{x}_{n})=f^{p}_{n}(\bm{x}_{n})-1/\mu_{n}$,
and thus we obtain:

$\displaystyle\mathop{\min}_{\bm{\theta}}\sum_{n\in\mathcal{N}}\theta_{n}=\mathop{\min}_{\bm{x}}\sum_{n\in\mathcal{N}}\frac{f^{p,u}_{n}(\bm{x}_{n})}{f^{p,l}_{n}(\bm{x}_{n})}=\sum_{n\in\mathcal{N}}\frac{f^{p,u}_{n}(\bm{x}_{n}^{*})}{f^{p,l}_{n}(\bm{x}_{n}^{*})},$
(30)

where $\bm{x}_{n}^{*}$ is the optimal solution and $f^{p,u}_{n},f^{p,l}_{n}$
are defined by

$\displaystyle f^{p,u}_{n}(\bm{x}_{n})=\;$
$\displaystyle\Phi_{\delta(n)}(\bm{x}_{n})\Phi_{\delta(n)-1}(\bm{x}_{n})+\Upsilon(\bm{x}_{n})\Psi_{n}(\bm{x}_{n})$
$\displaystyle+\hat{t}^{\mathit{tr}}\Psi_{n}(\bm{x}_{n})\Phi_{\delta(n)}(\bm{x}_{n})\Phi_{\delta(n)-1}(\bm{x}_{n}),$
(31) $\displaystyle f^{p,l}_{n}(\bm{x}_{n})=\;$
$\displaystyle\Psi_{n}(\bm{x}_{n})\Phi_{\delta(n)}(\bm{x}_{n})\Phi_{\delta(n)-1}(\bm{x}_{n}).$
(32)

######  Proposition 1.

Problem P2 can be recast into an equivalent problem as follows:

$\begin{split}\textbf{{(P2-1)}}~{}&\mathop{\min}_{\\{\bm{x}_{n}\\}}\sum_{n\in\mathcal{N}}f^{p,u}_{n}(\bm{x}_{n})-\theta^{*}_{n}f^{p,l}_{n}(\bm{x}_{n})\\\
\text{s.t.}&~{}~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b}\end{split}$
(33)

where $\theta^{*}_{n}$ is the minimum value of
$f^{p,u}_{n}(\bm{x}_{n})/f^{p,l}_{n}(\bm{x}_{n})$ with regard to $\bm{x}_{n}$.

###### Proof.

The detailed proof can be found in Appendix E of technical report [48]. ∎

Proposition 1 demonstrates that problem transformation can be employed to
address nonlinear fractional programming problems such as P2-1. Specifically,
the iterative Dinkelbach technique, outlined in Algorithm 1, can be applied to
solve these types of problems effectively, as shown in [54]. Algorithm 1
updates the value of $\tilde{\theta}_{n}$ in each iteration based on the
current $\tilde{\bm{x}}^{k}_{n}$, i.e.,

$\tilde{\theta}^{k+1}_{n}=\frac{f^{p,u}_{n}(\tilde{\bm{x}}^{k+1}_{n})}{f^{p,l}_{n}(\tilde{\bm{x}}^{k+1}_{n}))}.$
(34)

This process continues until:

$f^{p,u}_{n}(\tilde{\bm{x}}^{k+1}_{n})-\tilde{\theta}^{k}_{n}f^{p,l}_{n}(\tilde{\bm{x}}^{k+1}_{n}))>\epsilon^{ck},$
(35)

where $\epsilon^{ck}$ represents the stop criteria for iterations.

// CheckPointing Algorithm - NFP

Input: $\epsilon^{ck}$, $\\{\tilde{\theta}^{0}_{n}\\}$, $k$

1 for  _$n=1$ to $N$_ do

2 Convergence = False

3 while  _Convergence = False_ do

4 Apply Algorithm 2 or 4 with $\tilde{\bm{x}}^{k}_{n}$ and
$\tilde{\theta}^{k}_{n}$ to obtain the solution $\tilde{\bm{x}}^{k+1}_{n}$

5 if
_$f^{p,u}_{n}(\tilde{\bm{x}}^{k+1}_{n})-\tilde{\theta}^{k}_{n}f^{p,l}_{n}(\tilde{\bm{x}}^{k+1}_{n}))
>\epsilon^{ck}$_ then

6 Select
$\tilde{\theta}^{k+1}_{n}=\frac{f^{p,u}_{n}(\tilde{\bm{x}}^{k+1}_{n})}{f^{p,l}_{n}(\tilde{\bm{x}}^{k+1}_{n}))}$

7 Convergence = True

8 else

9 Convergence = False

10 end if

11 Update $s=s+1$

12

13 end while

14 Select $\bm{x}^{p,*}_{n}=\tilde{\bm{x}}^{k}_{n}$

15 Select $\theta^{p,*}_{n}=\tilde{\theta}^{k}_{n}$

16 Calculate PAoI according to (29)

Output: $\bm{x}^{p,*}_{n}$ and PAoI

17

18 end for

Algorithm 1 Nonlinear fractional programming based on ADMM-Consensus (NFPA)

####  IV-B2 ADMM-Consensus Based Solution

The procedure mentioned above can be considered as a checkpointing algorithm.
We employ non-convex ADMM-Consensus methods to determine the new value of
$\\{\bm{x}_{n}\\}$. As discussed in section IV-A, the consensus problem for
P2-1 can be expressed as:

$\begin{split}\textbf{(P2-2)}~{}\mathop{\min}_{\\{\bm{x}_{n}\\}}~{}~{}&\sum_{n\in\mathcal{N}}g^{p}_{n}(\bm{x}_{n})\\\
\text{s.t.}&~{}\bm{x}_{n}=\bm{x}_{o}\end{split}$ (36)

where

$\displaystyle
g^{p}_{n}(\bm{x}_{n})=\left\\{\begin{array}[]{ll}f^{p,u}_{n}(\bm{x}_{n})-\theta^{*}_{n}f^{p,l}_{n}(\bm{x}_{n}),&\bm{x}\in\Omega,\\\
\infty,&\text{otherwise.}\end{array}\right.$ (39)

It means that if the solution and $\bm{x}\in\Omega$ are feasible, then the
augmented Lagrangian for Problem P2-2 can be expressed as:

$\displaystyle
L^{p}(\\{\bm{x}_{n}\\},\bm{x}_{o},\\{\bm{\sigma}_{n}\\})=\sum_{n\in\mathcal{N}}L^{p}_{n}(\bm{x}_{n},\bm{x}_{o},\bm{\sigma}_{n})$
$\displaystyle=\sum_{n\in\mathcal{N}}\left(g^{p}_{n}(\bm{x}_{n})+\langle\bm{\sigma}_{n},\bm{x}_{n}-\bm{x}_{o}\rangle+\frac{\rho_{n}}{2}\|\bm{x}_{n}-\bm{x}_{o}\|^{2}_{2}\right)$
(40)

where $\rho_{n}$ is a positive penalty parameter with respect to Problem P2-2.
Based on the non-convex ADMM-Consensus algorithm, we update the variables in
each iteration $t$ as follows:

$\displaystyle\bm{x}^{t+1}_{n}$
$\displaystyle=\arg\min_{\bm{x}_{n}}L^{p}_{n}(\\{\bm{x}_{n}\\},\bm{x}^{t}_{o},\\{\bm{\sigma}^{t}_{n}\\})$
(41) $\displaystyle\bm{x}^{t+1}_{o}$
$\displaystyle=\frac{\sum_{n\in\mathcal{N}}(\rho_{n}\bm{x}^{t+1}_{n}+\sigma^{t}_{n})}{\sum_{n\in\mathcal{N}}\rho_{n}}$
(42) $\displaystyle\sigma^{t+1}_{n}$
$\displaystyle=\sigma^{t}_{n}+\rho_{n}(\bm{x}^{t+1}_{n}-\bm{x}^{t+1}_{o}).$
(43)

######  Proposition 2.

The first-order derivative of $g^{p}_{n}$ is Lipschitz continuous with
constant $\ell_{n}$, which is defined as

$\displaystyle\ell_{n}=\frac{\lambda^{2}_{max}}{\mu^{2}_{\mathit{min}}}\Big{(}\sum_{n_{1}\in\mathcal{N}}\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}+(1+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}})|\mathcal{N}_{1}|+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|\mathcal{N}_{2}|\Big{)},$
(44)

where $\mu_{\mathit{min}}=\mathop{\min}_{n}\\{\mu_{n}\\}$,
$\lambda_{max}=\mathop{\max}_{n}\lambda_{n}$,
$\mathcal{N}_{1}=\\{\mathcal{N}^{\delta}|\delta<\delta(n)\\}\bigcup\\{n\\}$,
$\mathcal{N}_{2}=\\{\mathcal{N}^{\delta}|\delta\leq\delta(n)\\}$.

###### Proof.

The detailed proof can be found in Appendix F of technical report [48]. ∎

According to the fact in Proposition 2, we adopt the non-convex ADMM-Consensus
method to solve Problem P2-2, with given
$\left(\\{\bm{x}^{0}_{n}\\},\\{\theta^{*}_{n}\\}\right)$ (as outlined in
Algorithm 1).

Input: $\epsilon^{ac}$, $t$ and
$\left(\\{\bm{x}^{0}_{n}\\},\\{\theta^{*}_{n}\\}\right)$ from Algorithm 1

// Internal Circulation - ADMM

1 do

2 Calculate $\bm{x}^{t+1}_{o}$ in MEC, according to (42)

3 Calculate $\bm{x}^{t+1}_{n}$ in user, simultaneously according to (41)

4 Calculate $\sigma^{t+1}_{n}$ in user, simultaneously according to (43)

5 Update $t=t+1$

6

7while  _$\eta\left(\bm{x}^{t},\bm{\sigma}^{t}\right)\geq\epsilon^{ac}$_ ;

Output: $\bm{x}^{t}_{n}$

Algorithm 2 Non-Convex ADMM-Consensus (NAC)

It is worth mentioning that the value of $\rho_{n}$ and convergence of the
Algorithm 2 differ from those in the Convex ADMM-Consensus method. Since
Algorithm 2 is for problems with non-convex objective functions, we design a
special gap functions that can characterize the convergence of NAC as follows:

$\eta\left(\bm{x}^{t},\bm{\sigma}^{t}\right)=\left\|\tilde{\nabla}L^{p}\left(\left\\{\bm{x}^{t}_{n}\right\\},\bm{x}^{t}_{o},\bm{\sigma}^{t}\right)\right\|^{2}+\sum_{n\in\mathcal{N}}\left\|\bm{x}^{t}_{n}-\bm{x}^{t}_{o}\right\|^{2},$
(45)

where

$\displaystyle\tilde{\nabla}L^{p}\left(\left\\{\bm{x}_{n}\right\\},\bm{x}_{o},\bm{\sigma}^{t}\right)=\left[\begin{array}[]{c}\nabla_{\bm{x}_{o}}L^{p}\left(\left\\{\bm{x}_{n}\right\\},\bm{x}_{o},\bm{\sigma}^{t}\right)\\\
\nabla_{\bm{x}_{1}}L^{p}\left(\left\\{\bm{x}_{n}\right\\},\bm{x}_{o},\bm{\sigma}^{t}\right)\\\
\vdots\\\
\nabla_{\bm{x}_{N}}L^{p}\left(\left\\{\bm{x}_{n}\right\\},\bm{x}_{o},\bm{\sigma}^{t}\right)\end{array}\right].$

When $\eta\left(\bm{x}^{t},\bm{\sigma}^{t}\right)<\epsilon^{ac}$, the limit
solution is a stable solution, where $\epsilon^{ac}$ is the criterion for
stopping the iterations of Algorithm 2.

######  Theorem 2.

If $\rho_{n}>2\ell_{n}$, Algorithm 2 converge to an $\epsilon^{ac}$-stationary
point within $O(1/(p^{\mathit{sysn}}\epsilon^{\mathit{ac}}))$, where
$\epsilon^{ac}$ is a positive iteration factor and
$p^{\mathit{sysn}}=\Pi_{n\in\mathcal{N}}(\frac{1}{C}\sum_{c\in\mathcal{C}}p_{n,c})$
is the probability of successfully completing a synchronous update.

###### Proof.

The detailed proof can be found in Appendix G of technical report [48]. ∎

Since the iteration will continue if the parameters given by Algorithm 2 do
not satisfy the stop condition of Algorithm 1, we can use Algorithm 1 as a
condition for Algorithm 2 to terminate.

###  IV-C Multi-Priority Task Scheduling and Multi-Server Collaboration

####  IV-C1 Problem Decomposition

Different from Section IV-A and Section IV-B, which concentrate solely on a
single server, we further study multi-priority and multi-server collaboration-
based offloading in this subsection. In order to resolve the original problem,
we first derive the expression of the optimal migration decision variable
$\bm{y}^{*}$.

######  Theorem 3.

The optimal migration decision is

$y_{m_{n}}=\left\\{\begin{array}[]{ll}1,&\quad\phi^{in}(\bm{\eta}^{s})+\phi^{out}(\bm{\eta}^{s})>0,\\\
0,&\quad otherwise,\end{array}\right.$ (46)

where
$\phi^{in}(\bm{\eta}^{s})=\sum_{m^{\prime}\in\mathcal{M}/m_{n}}\eta^{s}_{m^{\prime},m_{n}}\sum_{\delta\in\Delta}\lambda^{s}_{\delta,m^{\prime}}$
and $\phi^{out}(\bm{\eta}^{s})$
$=\sum_{m^{\prime}\in\mathcal{M}/m_{n}}\eta^{s}_{m_{n},m^{\prime}}\sum_{\delta\in\Delta}\lambda^{s}_{\delta,m_{n}}$.

###### Proof.

The detailed proof can be found in Appendix H-A of technical report [48]. ∎

Combining Theorem 3 and Appendix H-B [48], one alternative for (PoPeC) is

$\begin{split}\textbf{(P3)}~{}&\mathop{\min}_{\bm{x},\bm{z}}\frac{1}{N}\sum_{n\in\mathcal{N}}F^{1}_{n}(\bm{x},\bm{z})\\\
\text{s.t.}&~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c3a},\eqref{eq:c5a},\eqref{eq:c4a},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},\end{split}$
(47)

where
$F^{1}_{n}(\bm{x},\bm{z})=\hat{t}^{\mathit{tr}}_{n}+\frac{1}{\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}}+\sum_{m\in\mathcal{M}}\pi_{n,m}(\bm{z})$,
$\bm{x}=\\{\hat{t}^{\mathit{tr}},\bm{\eta}^{u}\\}$ and $\bm{z}=\bm{\eta}^{s}$.
The main challenge in resolving the P3 is that the function
$\sum_{n\in\mathcal{N}}F^{1}_{n}(\bm{x},\bm{z})$ is a non-convex and the
variable $\bm{x}$ is intricately connected to $\bm{z}$.

######  Lemma 2.

Problem P3 can be equivalently transformed into the Channel Allocation
subproblem, P3-1, and the Server Collaboration subproblem, P3-2, which are
shown as follow:

(P3-1)
$\displaystyle\mathop{\min}_{\bm{x}}\frac{1}{N}\sum_{n\in\mathcal{N}}F^{2}_{n}(\bm{x})$
s.t.
$\displaystyle~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},$
$\displaystyle\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in
C}p_{n,c}\eta^{u}_{n,c}\lambda_{n}\leq\lambda^{s}_{\delta,m},$ (48)
$\begin{split}\textbf{(P3-2)}~{}&\mathop{\min}_{\bm{z}}\frac{1}{N}\sum_{n\in\mathcal{N}}F^{3}_{n}(\bm{z},\bm{\lambda}^{s})\\\
\text{s.t.}&~{}\eqref{eq:c3a},\eqref{eq:c5a},\eqref{eq:c4a},\end{split}$ (49)

where we define
$F^{2}_{n}(\bm{x})\doteq\hat{t}^{\mathit{tr}}_{n}+\frac{1}{\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}}$,
$F^{3}_{n}(\bm{z},\bm{\lambda}^{s})\doteq\sum_{m\in\mathcal{M}}\pi_{n,m}(\bm{z})$,
and
$\lambda^{s}_{\delta,m}\doteq\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m,m^{\prime}}\lambda^{s}_{\delta,m}$.

###### Proof.

The detailed proof can be found in Appendix I of technical report [48]. ∎

Next, we develop solutions to these problems that iteratively address the
Channel Allocation P3-1 on the user side and Server Collaboration P3-2
problems on the server side.

####  IV-C2 Channel Allocation

The goal of the Channel Allocation problem is to address the problem of
channel allocation for each local server and each user it serves, Based on
Lemma 2, this sub-problem is transformed and we can obtain the optimal
solution

$\begin{split}\bm{x}^{*}=\\{\bm{x}^{*}_{m}\\},\end{split}$ (50)

where $\bm{x}^{*}_{m}$ can be derived from

$\displaystyle\textbf{(P3-3)}\mathop{\min}_{\bm{x}_{m}}\sum_{n\in\mathcal{N}_{m}}F^{2}_{n}(\bm{x}_{m},\bm{\lambda}^{s})~{}$
$\displaystyle\text{s.t.}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},\eqref{eq:DataMigration-
AuxiliaryInequality}.$ (51)

######  Lemma 3.

Problem P3-2 is a convex problem.

###### Proof.

We can easily obtain the convexity of $F^{1}_{n}$ from Appendix C of technical
report [48]. Thus, this is a convex problem where both the sub-function and
the constraints are convex. ∎

Based on Lemma 3 and the solution of IV-A, P3-2 can be resolved by the
existing method AC in Algorithm 5. The details can be found in Section IV-A2
and Appendix D of technical report [48]. Each local server first finds an
optimal solution $\bm{x}^{*}_{m}$ for all users it covers, and then the
collection of these $\bm{x}^{*}_{m}$ is the optimal channel allocation
solution $\bm{x}^{*}$, which is shown by (50).

####  IV-C3 Server Collaboration

Problem P3-2 seeks to address the problem of multi-server collaboration
between various servers in order to lessen the load on overhead servers and
speed up task execution to decrease PAoI for multi-priority users, which has
been shown to be an NP-Hard problem in section IV-B. However, we develop an
effective migration strategy, based on Lemma 3, the server collaboration
strategy is
$\bm{z}^{*}=\mathop{\arg\min}_{\bm{z}}\\{\frac{1}{N}\sum_{n\in\mathcal{N}}\sum_{m\in\mathcal{M}}\pi_{n,m}(\bm{z})~{}\text{s.t.}~{}\eqref{eq:c3a},\eqref{eq:c5a},\eqref{eq:c4a}\\}$.

######  Proposition 3.

Given $\bm{\lambda}^{s}$, Problem P3-2 is equivalent to the following problem:

(P3-4)
$\displaystyle\mathop{\min}_{\\{\bm{z}_{n,m}\\}}\sum_{n\in\mathcal{N}}\sum_{m\in\mathcal{M}}\\{\pi^{u}_{n,m}(\bm{z}_{n,m})-\vartheta^{*}_{n,m}\pi^{l}_{n,m}(\bm{z}_{n,m})\\}$
s.t.
$\displaystyle~{}~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c7a},\eqref{eq:c8a},\eqref{eq:c6},$
(52)

Given $\bm{z}_{n,m}$, $\vartheta^{*}_{n,m}$ is the minimum of
$\frac{\pi^{u}_{n,m}(\bm{z}_{n,m})}{\pi^{l}_{n,m}(\bm{z}_{n,m})}$, where
$\pi^{l}_{n,m}(\bm{z})$
$=\Phi^{\pi}_{\delta(n),m}(\bm{z})\Phi^{\pi}_{\delta(n)-1,m}(\bm{z})\sum_{m^{\prime}\in\mathcal{M}}\Psi_{n,m^{\prime}}^{\pi}(\bm{z})$
and
$\pi^{u}_{n,m}(\bm{z})=\Lambda_{n,m}\Psi_{n,m}^{\pi}(\bm{z})\Phi^{\pi}_{\delta(n),m}(\bm{z})\Phi^{\pi}_{\delta(n)-1,m}(\bm{z})+\Psi_{n,m}^{\pi}(\bm{z})\Upsilon^{\pi}(\bm{z})$.
Here,
$\Upsilon^{\pi}_{n,m}(\bm{z})=\frac{1}{2}\sum_{\delta\in\Delta}\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m^{\prime},m}\lambda^{s}_{\delta,m^{\prime}}\nu_{n,m}$,
$\Lambda_{n,m}=t^{\mathit{tr}}_{m_{n},m}+\frac{1}{\mu_{n,m}}$,
$\Phi^{\pi}_{\delta(n),m}(\bm{z})=1-\sum_{\delta\in{\Delta(\delta(n))}}\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m^{\prime},m}\lambda^{s}_{\delta,m^{\prime}}\frac{1}{\mu_{n,m}}$,
and
$\Psi_{n,m}^{\pi}(\bm{z})=\sum_{\delta\in\Delta}\eta^{s}_{m_{n},m}\lambda^{s}_{\delta,m_{n}}$.

###### Proof.

Due to ${\pi^{u}_{n,m}(\bm{z})}$ and ${\pi^{l}_{n,m}(\bm{z})}$ as the
polynomial functions of the numerator and denominator on the fraction
$\pi_{n,m}(\bm{z})$, problem P3-2 with given $\bm{\lambda}^{s}$ from can be
recast into an equivalent problem as P3-4, with applying nonlinear fractional
programming. For more detailed problem tranformation, please refer to Appendix
J-1 of technical report [48]. ∎

Combining Proposition 3 and Section IV-B1, we can apply NFP in Algorithm 1 to
convert P3-2 to P3-4. After transforming the problem in Proposition 3, we
obtain problem P3-4, which has a cubic polynomial objective function.
Nevertheless, deriving the closed-form solution for P3-4 is still challenging,
we instead provide an iterative algorithm as follows.

######  Lemma 4.

In P3-4, the first-order derivative of
$\pi^{u}_{n,m}(\bm{z}_{n,m})-\vartheta^{*}_{n,m}\pi^{l}_{n,m}(\bm{z}_{n,m})$
is Lipschitz continuous.

###### Proof.

The detailed proof can be found in Appendix J-2 of technical report [48]. ∎

Based on Lemma 4 and Section IV-B2, we use NAC and NFP in Algorithm 2 to gain
an efficient solution of P3-4. In this case, the complexity of the method is
$O(1/\epsilon^{ac})$, which can be proved by Appendix J-3 [48].

####  IV-C4 Iterative Solution

We design an iterative solution algorithm that first obtains the initial
$\bm{x}_{o}$ inside each local server with a given $\bm{y}$. In the algorithm,
$\bm{x}^{t}$ and $\bm{z}^{t}$ are solved alternately to obtain the solution.
In the following, we establish the convergence guarantee for the proposed
algorithm.

Input: $t=0$, $\lambda^{s,0}_{\delta,m}=\lambda^{s,\mathit{max}}_{m}$

1 while  _not done_ do

2 Compute $\bm{x}^{t+1}$ according to (50) by Lemma 3

3 Compute $\bm{\lambda}^{s,t+1}$ according to (5)

4 Compute $\bm{z}^{t+1}$ according to (52) by Lemma 4

5 Update $t=t+1$

6

7 end while

8Compute $\bm{y}^{*}$ by (46);

Output: $\bm{x}^{*}=\bm{x}^{t}$,$\bm{y}^{*}$,$\bm{z}^{*}=\bm{z}^{t}$

Algorithm 3 Iterative Solution (IS)

######  Theorem 4.

If we solve P3 by Algorithm 3, $F_{n}(\bm{x}^{t},\bm{z}^{t})$ monotonically
decreases and converges to a unique point.

###### Proof.

The detailed proof can be found in Appendix K of technical report [48]. ∎

##  V Discussion

###  V-A Asynchronous Parallel Algorithm

1 /* MEC Side */

Input: $\epsilon^{ac}$, $\tau_{o}$ and
$\left(\\{\bm{x}^{0}_{n}\\},\\{\theta^{*}_{n}\\}\right)$ from Algorithm 1

2 Convergence = False

3 while  _Convergence == False_ do

4 Calculate
$\bm{x}^{\tau_{o}+1}_{o}=\arg\min_{\bm{x}_{o}\in\Omega}L^{p}\left(\\{\bm{x}^{0}_{n}\\},\bm{x}_{o},\\{\bm{\sigma}^{0}_{n}\\}\right)$
if  _$\eta\left(\bm{x}^{\tau_{o}},\bm{\sigma}^{\tau_{o}}\right)
<\epsilon^{ac}$_ then

5 Convergence = True

6 Send $\bm{x}^{\tau_{o}+1}_{o}$ and Convergence to all users

7 else

8 Send $\bm{x}^{\tau_{o}+1}_{o}$ and Convergence to all users

9 Wait for some fixed period of time

10 Receive all the gradients $\\{x^{\tau^{r}_{n}}_{n}\\}$ and all the local
time $\\{\bm{\tau}^{r}_{n}\\}$ from users

11 Record the received users in $\mho^{\tau_{o}+1}$

12 if  _$n\in\mho^{\tau_{o}+1}$_ then

13 Select $\tau_{n}=\min\\{\bm{\tau}^{r}_{n}\\}$ and $\nabla
G^{p,\tau_{o}+1}_{n}=x^{\tau^{r}_{n}}_{n}$

14 else

15 Select $\nabla G^{p,\tau_{o}+1}_{n}=\nabla G^{p,\tau_{o}}_{n}$

16 end if

17

18 Calculate
$\bm{x}^{\tau_{o}+1}_{n}=\bm{x}^{\tau_{o}+1}_{o}-\frac{1}{\rho_{n}}(\nabla
G^{p,\tau_{o}+1}_{n}+\bm{\sigma}^{\tau_{o}}_{n})$

19 Calculate
$\bm{\sigma}^{\tau_{o}+1}_{n}=\bm{\sigma}^{\tau_{o}}_{n}+\rho_{n}(\bm{x}^{\tau_{o}+1}_{n}+\bm{x}^{\tau_{o}+1}_{o})$

20 Update $\tau_{o}=\tau_{o}+1$

21 end if

22

23 end while

Output: $\bm{x}^{\tau_{o}}_{o}$

24

25/* USER Side */

26 for  _user $n\in\mathcal{N}$_ do

27 Initialize $\tau_{n}=0$

28 while  _Receive $\bm{x}^{r}$ and Convergence from MEC_ do

29 if  _Convergence == False_ then

30 Select $\bm{x}^{\tau_{n}+1}_{n}=\bm{x}^{r}$

31 Calculate $\nabla g^{p}_{n}(\bm{x}^{\tau_{n}+1}_{n})$

32 Send $\nabla g^{p}_{n}(\bm{x}^{\tau_{n}+1}_{n})$ and $(\tau_{n}+1)$ to MEC
via the most reliable channel

33 Update $\tau_{n}=\tau_{n}+1$

34 else

35 Select $\bm{x}_{n}=\bm{x}^{r}$

Output: $\bm{x}_{n}$

36

37 end if

38

39 end while

40

41 end for

42

Algorithm 4 Asynchronous Non-Convex ADMM-Consensus (ANAC)

In the previous study, we proposed several synchronous parallel algorithms.
Nevertheless, the reliability and effectiveness of these algorithms can be
severely affected by communication failures and chaos resulting from faulty
communication networks. Theorem 2 reveals that Algorithm 2 has a slow
convergence speed, highlighting the need to replace it with a more
communication-efficient alternative.

First, the channel with the highest reliability rate is chosen to make sure
that the iteration achieves the highest success rate
(i.e.$p^{\mathit{max}}_{n}=\max_{c}\\{p_{n,c}\\}$), in new Algorithm. In doing
so, the risk of communication iteration loss is intuitively reduced. To ensure
successful iterations in an asynchronous algorithm, there needs to be a limit
on the number of communications required for each communication unit. In order
to satisfy the delay bound of iterations needed for successful communication
$\Gamma_{n}$, we have $(1-p^{\mathit{max}}_{n})^{\Gamma_{n}}<\epsilon^{a}$,
where $\epsilon^{a}$ is the maximum tolerance for asynchronous iterative
communication. Both sides are logarithmic at the same time, it is
$\Gamma_{n}\geq\frac{ln(\epsilon^{a})}{ln(1-p^{\mathit{max}}_{n})}$.

######  Assumption 1.

The upper bound on the number of communications to complete a successful
iteration satisfies

$\Gamma_{n}=\left\lceil\frac{ln(\epsilon^{a})}{ln(1-p^{\mathit{max}}_{n})}\right\rceil$
(53)

where $\lceil x\rceil$ is the ceiling function of $x$.

Furthermore, we present an asynchronous variant of Algorithm 2 as Algorithm 4.
In each iteration, each user computes the gradient based on the most recently
received information from the server and sends it to the local server. The
server collects all available iterations, updates the value of $\bm{x}$, and
passes the latest information back to the user. This asynchronous approach can
help reduce communication overhead and improve convergence speed. In addition,
we recognize that users may have limited computational resources, and thus, we
suggest assigning a minimal number of computational tasks or designing the
tasks to be as simple as possible.

Convergence Analysis: If Assumption 1 is satisfied and we set
$\rho_{n}>\max\\{7\ell_{n},\ell_{n}(\Gamma^{2}_{n}+\frac{3}{7}(\Gamma_{n}+1)^{2})\\}$,
the sequence $\\{\\{\bm{x}_{n}\\},\bm{x}\\}$ in Algorithm 4 converges to the
set of stationary solutions of problem, based on [55, Theorem 3.1]. Moreover,
for $\epsilon^{ac}>0$, we obtain

$p^{\mathit{asysn}}\Gamma^{\mathit{asysn}}\epsilon^{ac}<k^{\Gamma}(L^{p}\left(\left\\{\bm{x}_{n}^{1}\right\\},\bm{x}_{o}^{1},\bm{\sigma}^{1}\right)-\underline{G}^{p}),$
(54)

where $\epsilon^{ac}$ is a positive iteration factor, $k^{\Gamma}$ is a
constant, $\underline{G^{p}}$ is the lower bound of
$\sum_{n\in\mathcal{N}}g^{p}_{n}(\bm{x}_{n})$, $\Gamma^{sysn}$ is number of
iterations, i.e.,
$\Gamma^{sysn}=\min\left\\{t\mid\eta\left(\bm{x}^{t},\bm{\sigma}^{t}\right)\leq\epsilon,t\geq
0\right\\}$,
$p^{\mathit{asysn}}=1-\Pi_{n\in\mathcal{N}}(1-p^{\mathit{max}}_{n})$ denote
the probability that at least one communication unit communicates successfully
in an iteration and $p^{\mathit{asysn}}\Gamma^{\mathit{asysn}}$ represents the
number of successful iterations. Thus, we have

$\Gamma^{\mathit{asysn}}<\frac{k^{\Gamma}(L^{p}\left(\left\\{\bm{x}_{n}^{1}\right\\},\bm{x}_{o}^{1},\bm{\sigma}^{1}\right)-\underline{G}^{p})}{\epsilon^{ac}p^{\mathit{asysn}}},$
(55)

which means Algorithm 4 converge to an $\epsilon^{ac}$-stationary point within
$O(1/(p^{\mathit{asysn}}\epsilon^{\mathit{ac}}))$. Therefore, we derive that
the asynchronous parallel algorithm is approximately
$p_{\mathit{asysn}}/p_{\mathit{sysn}}$ times faster, in comparison to the
synchronous parallel approach according to Theorem 2. The value of
$p_{\mathit{asysn}}/p_{\mathit{sysn}}$ is greater than 1, and it increases as
the channel quality declines.

Convergence analysis shows that Algorithm 4 converges faster than Algorithm 2,
particularly when transmission reliability is low. Furthermore, we demonstrate
the effectiveness of the asynchronous algorithm through numerous simulation
experiments.

###  V-B Why Multi-Class Priority?

Many multi-priority systems focus on scenarios where each user has a
predetermined priority level, which can lead to the unjust treatment of users
with similar priorities [34, 39, 37]. This may undermine the principles of
fairness and equality that these systems are intended to uphold. However, our
multi-priority model can extend to handle different scenarios to promote fair
allocation, including cases where users have unequal priorities or where
multiple users share the same priority level. This model, known as a multi-
class priority, aims to prevent unfair treatment of users with similar
priorities by allocating resources equitably. Next, we intend to discuss what
are the benefits of our proposed multi-class priority mechanism compared to
the common multi-priority and no-priority mechanisms.

The PAoI of user $n*$, who are set to the highest priority, has more optimal
information freshness than the priority-free case under the same offloading
strategy, which is

$\displaystyle\mathbb{E}[A_{n^{*}}]-\mathbb{E}[A^{p}_{n^{*}}]$
$\displaystyle=$
$\displaystyle\Upsilon(\bm{\eta}^{u})\frac{\zeta_{\Delta}(\bm{\eta}^{u})-\zeta_{\delta(n^{*})}(\bm{\eta}^{u})}{(1-\zeta_{\Delta}(\bm{\eta}^{u}))(1-\zeta_{\delta(n^{*})}(\bm{\eta}^{u}))}\geq
0.$ (56)

where
$\zeta_{\delta(n^{*})}(\bm{\eta}^{u})=\sum_{\delta\in\Delta(\delta(n^{*}))}\sum_{n^{\prime}\in\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\frac{\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}}{\mu_{n^{\prime}}}$,
$\zeta_{\Delta}(\bm{\eta}^{u})=\sum_{\delta\in\Delta}\sum_{n^{\prime}\in\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\frac{\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}}{\mu_{n^{\prime}}}$,
and
$\Upsilon(\bm{\eta}^{u})=\frac{1}{2}\sum_{\delta\in\Delta}\sum_{n^{\prime}\in\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}\nu_{n^{\prime}}$.
Similarly, the PAoI of user $n_{*}$, who is set to have the lowest priority,
has a worse PAoI than the priority-free case. Thus, we gain

$\displaystyle\mathbb{E}[A_{n_{*}}]-\mathbb{E}[A^{p}_{n_{*}}]$
$\displaystyle=$
$\displaystyle\frac{\Upsilon(\bm{\eta}^{u})}{1-\zeta_{\Delta}(\bm{\eta}^{u})}(1-\frac{1}{1-\zeta_{\delta(n)-1}(\bm{\eta}^{u})})\leq
0.$ (57)

Furthermore, multiple users are assumed to have the same priority level, but
are instead assigned priorities of $\delta^{0}$ and $\delta^{0}-\hat{\delta}$
in the multi-priority scenario, the resulting difference in freshness can be
substantial and unfair:

$\displaystyle\mathbb{E}[A^{p}_{n}|\delta(n)=\delta^{0}]-\mathbb{E}[A^{p}_{n}|\delta(n)=\delta^{0}-\hat{\delta}]$
$\displaystyle\geq$
$\displaystyle\frac{\Upsilon(\bm{\eta}^{u})(\zeta_{\delta^{0}}(\bm{\eta}^{u})-\zeta_{\delta^{0}-\hat{\delta}-1}(\bm{\eta}^{u}))}{(1-\zeta_{\delta^{0}}(\bm{\eta}^{u}))(1-\zeta_{\delta^{0}-1}(\bm{\eta}^{u}))(1-\zeta_{\delta^{0}-\hat{\delta}-1}(\bm{\eta}^{u}))}$
$\displaystyle\geq$ $\displaystyle 0.$ (58)

For more proof details, please refer to Appendix L of technical report [48].
This subsection shows that user $n$ can get superior performance as compared
to priority-free by allocating it a high priority. Giving user $n$ a greater
priority in multi-class priority also enhances its performance.

##  VI Simulation

In this section, we evaluate our proposed algorithm by answering the following
questions:

  1. 1.

What is its achievable utility in task scheduling?

  2. 2.

Can it schedule multi-priority tasks effectively?

  3. 3.

Can it deal with heterogeneous and unreliable channels effectively?

###  VI-A Experimental Setup

Experimental setup. In this section, we carry out simulations to evaluate the
effectiveness, performance, and computational efficiency of our proposed
method. In the priority-free case, we consider 10 servers and 200 users within
their respective coverage areas. For the multi-priority case, we examine at
least three priorities, allocating users to different priority levels.
Moreover, we model the transmission success probability of the channel as a
Gaussian distribution $N(0.5,1)$, following [56]. We set the number of
available channels $C$ to be 30, with a bandwidth of $B=5MHz$, and channel
gains were set to unity as in [57]. To account for the heterogeneity of users
and servers, the service time of tasks followed a general distribution, where
the mean and variance of the distribution are determined by the types of users
and servers. Specifically, we set the value of the mean and variance of the
general distribution to follow the uniform distribution $U(1,5)$ and
$U(1,25)$, respectively.

TABLE I: Parameters in Simulation

Parameter | Value
---|---
# users ($N$) | an integer varying between $[1,200]$
# channels ($C$) | an integer varying between $[1,30]$
# servers ($M$) | an integer varying between $[1,10]$
the channel condition |  | channel bandwidth ($B$) as 5MHz
---
channel gains ($R_{c}$) as 1
the service time |  | obey the general distribution
---
with the mean $\mu$ following $U(1,5)$,
and the variance $\nu$ following $U(1,25)$, respectively
the transmission rates | real numbers (Mbit/slot) varying between $[0,0.5]$
task generation rates | real numbers (Mbit/slot) following $U(0.5,1.5)$

Baselines. We compare our proposed algorithm with existing algorithms in the
literature to perform a comprehensive analysis. Specifically, we compare our
method with the Age-Aware Policy (AAP) algorithm which utilizes throughput
constraints through the Lyapunov optimization method [7]. We also consider the
Greedy Control Algorithm (GA), which selects the most reliable channel among
the unreliable channels. Additionally, to account for the lack of priority
mechanism in AAP and GA, we compare our algorithm with the Priority Scheduling
method of Peak Age of Information in Priority Queueing Systems (PAUSE) [39]
and the Rate and Age of Information (RAI) method [58]. To ensure a fair
comparison, we assume that each user sends the maximum possible number of
tasks to the edge server, and the edge server completes the tasks in a First-
Come-First-Serve (FCFS) manner.

Implementation. The simulation platform is Matlab R2019a and all the
simulations are performed on a laptop with 2.5 GHz Intel Core i7 and 16 GB
RAM.

###  VI-B Overall Utility

In the assessment of the overall utility, we conducted an analysis of various
metrics, such as PAoI and throughput, under different methods, and examined
their performance in various settings, including priority allocation and
server collaboration.

Firstly, as depicted in Fig.2(a) and 2(b), our evaluation shows that the
number of users $N$ and channel capacity $M$ significantly impact the PAoI
value and throughput. Our proposed algorithm (OUR) outperforms both the Greedy
Control Algorithm (GA) and the Age-Aware Policy (AAP) algorithm, especially in
terms of PAoI. However, in resource-constrained environments, specifically in
Fig.2(b), our algorithm’s throughput performance is slightly inferior since it
does not have the same higher needs and throughput constraints as the (AAP)
algorithm.

(a) PAoI & Throughout vs. $N$

(b) PAoI & Throughout vs. $M$

Figure 2: Impact of different methods on various metrics.

In the second analysis, we conducted a simulation for the multi-priority case,
as illustrated in Fig.3(a). Here, $\Delta$ denotes the degree of priority
breakdown, with $\Delta=1$ indicating no priority distinction and $\Delta=6$
indicating six priority classes. The simulation results show that the average
PAoI of the system is mainly determined by the computing power of the server
($\mu$, task execution time), and the priority division level has little
influence on it. Furthermore, we investigated multi-server collaboration cases
and found that multi-server coordination is feasible and can significantly
reduce the task execution time without affecting the update frequency.
Fig.3(b) presents the results for both single-server execution and multi-
server collaboration cases, showing that multi-server collaboration
outperforms the single-server case regardless of the number of users. This
advantage is more prominent as the number of users increases.

(a) PAoI vs. $\mu$ in different priority allocation case

(b) PAoI vs. $N$ in the case of whether servers are collaborating

Figure 3: The performance in various settings.

###  VI-C Performance of Priority Users

Simulation results show that the proposed algorithm can be extended to multi-
class priority scenarios. We set three priority classes ($\delta$ lower,
higher priority) and randomly assigned them to a number of users in our
simulation Fig.4(a). As the iterations of our algorithm proceed, the average
PAoI values of users with various priority levels steadily increase and
eventually tend to stabilize, and the offloading rate gradually decreases and
eventually tends to be stable. We discover that users with higher priority
always receive more channel allocations, which results in higher offloading
rates. Additionally, high-priority users’ PAoI values are lower since they are
more likely to finish their tasks promptly.

(a) Performance of users with different priorities

(b) Comparison of high priority users in different algorithms

Figure 4: Performance of Priority Users

With three types of priorities (high priority, medium priority, low priority),
we compare the proposed multi-class priority method (OUR) with other
algorithms (GA, PAUSE, RAI), and we pay special attention to the promotion
effect of our algorithm for high-priority users, as shown in Fig.4(b). The
(GA) algorithm is one that does not consider priorities, the (PAUSE) algorithm
focuses on the discussion of multiple priorities rather than multiple classes
of priorities, and the (RAI) algorithm only considers two classes of
priorities. The PAoI values of the high-priority users all decrease in the
simulation as the server processing rate $\mu$ rises, clearly stating that the
suggested strategy (OUR) is the best one.

###  VI-D Convergence Rate of the Algorithm in Unreliable Channels

In this part, our experiments study the influence of the unreliable channel on
the PAoI value and the convergence performance of different algorithms
including (NFPA-NAC) and (NFPA-ANAC) in the unreliable channel.

Both NFPA-NAC in Fig.5(a) and NFPA-ANAC in Fig.5(b) are advantageous for
implementing powerful edge servers due to their ability to allocate channel
and task scheduling resources efficiently. However, the lack of communication
resources can prevent the development of more efficient systems. We show the
performance of algorithms NFPA-NAC and NFPA-ANAC in different channel
conditions ($p=0.3,0.5,0.7,0.9$) in Fig.5(a) and Fig.5(b) without repeated
experiments. We observe that the PAoI values gradually decline and eventually
stabilize as the iterations proceed. Moreover, the lower the value of channel
condition $p$, the slower the convergence rate. Additionally, it can be
observed that PAoI can be more optimal with better channel conditions because
users have more options for offloading. We note that in our simulations the
algorithm NFPA-NAC cannot successfully iterate in each iteration, while NFPA-
ANAC can successfully iterate using the limited information in each iteration.

(a) NFPA-NAC

(b) NFPA-ANAC

Figure 5: The influence of the unreliable channel on the PAoI

To illustrate the difference between the two algorithms NFPA-NAC and NFPA-ANAC
more systematically, Fig.6 with various channel conditions
($p=0.7,0.8,0.9,0.99$) compares the convergence of the two algorithms. In
contrast to Fig.5, we choose a better initial value, more users, and a large
number of repeated experiments to help explain the convergence
characteristics. Both methods have similar rates of convergence in acceptable
channels ($p=0.9,0.99$). However, the convergence rate advantage of algorithm
NFPA-ANAC, however, is fairly apparent in the ($p=0.7,0.8$) channel because of
the poorer channel quality.

Figure 6: Compare with different algorithms

##  VII Conclusion

In this paper, we proposed a scheduling method that considered multi-priority
users and multi-server collaboration to address the limitations of unreliable
channels in current real-time systems and the individual needs of users. We
derived the utility function of priority scheduling based on PAoI and designed
a set of distributed optimization methods. Specifically, we first consider two
simplified problems for the original problem and employ the fractional
programming as well as ADMM to obtain their solutions. Building upon these
solutions and conclusions drawn therein, we develop an iterative algorithm to
solve the original problem. Furthermore, we proposed an distributed
asynchronous approach with a sublinear rate of communication defects and
discuss the theoretical performance improvement due to the multi-priority
mechanism. We implemented the method and conducted extensive simulations to
compare it with the existing age-based scheduling strategies. Our results
demonstrated the effectiveness and superiority of our method in addressing the
requirements of freshness-sensitive users over unreliable channels.

## References

  * [1] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “Mobile edge computing: Survey and research outlook,” _arXiv preprint arXiv:1701.01090_ , 2017.
  * [2] Q. Luo, S. Hu, C. Li, G. Li, and W. Shi, “Resource scheduling in edge computing: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 23, no. 4, pp. 2131–2165, 2021.
  * [3] F. Liu, G. Tang, Y. Li, Z. Cai, X. Zhang, and T. Zhou, “A survey on edge computing systems and tools,” _Proceedings of the IEEE_ , vol. 107, no. 8, pp. 1537–1562, 2019.
  * [4] T. X. Tran and D. Pompili, “Joint task offloading and resource allocation for multi-server mobile-edge computing networks,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 1, pp. 856–868, 2018.
  * [5] Y. Zou, K. T. Kim, X. Lin, and M. Chiang, “Minimizing age-of-information in heterogeneous multi-channel systems: A new partial-index approach,” in _Proceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing_ , 2021, pp. 11–20.
  * [6] D. Guo and I.-H. Hou, “Scheduling real-time information-update flows for the optimal confidence in estimation,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 5, pp. 1339–1351, 2021.
  * [7] J. Sun, L. Wang, Z. Jiang, S. Zhou, and Z. Niu, “Age-optimal scheduling for heterogeneous traffic with timely throughput constraints,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 5, pp. 1485–1498, 2021\.
  * [8] S. Li, C. Li, Y. Huang, B. A. Jalaian, Y. T. Hou, and W. Lou, “Task offloading with uncertain processing cycles,” in _Proceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing_ , 2021, pp. 51–60.
  * [9] A. M. Bedewy, Y. Sun, R. Singh, and N. B. Shroff, “Optimizing information freshness using low-power status updates via sleep-wake scheduling,” in _Proceedings of the Twenty-First International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing_ , 2020, pp. 51–60.
  * [10] J. Pan, A. M. Bedewy, Y. Sun, and N. B. Shroff, “Minimizing age of information via scheduling over heterogeneous channels,” in _Proceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing_ , 2021, pp. 111–120.
  * [11] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 5, pp. 1183–1210, 2021.
  * [12] H. Hu, Y. Dong, Y. Jiang, Q. Chen, and J. Zhang, “On the age of information and energy efficiency in cellular iot networks with data compression,” _IEEE Internet of Things Journal_ , 2022.
  * [13] Q. Liu, C. Li, Y. T. Hou, W. Lou, and S. Kompella, “Aion: A bandwidth optimized scheduler with aoi guarantee,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_. IEEE, 2021, pp. 1–10.
  * [14] C. Li, Q. Liu, S. Li, Y. Chen, Y. T. Hou, and W. Lou, “On scheduling with aoi violation tolerance,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_. IEEE, 2021, pp. 1–9.
  * [15] J. Moon and T. Başar, “Minimax control over unreliable communication channels,” _Automatica_ , vol. 59, pp. 182–193, 2015.
  * [16] H. Lv, Z. Zheng, F. Wu, and G. Chen, “Strategy-proof online mechanisms for weighted aoi minimization in edge computing,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 5, pp. 1277–1292, 2021.
  * [17] R. D. Yates, “Status updates through networks of parallel servers,” in _2018 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 2281–2285.
  * [18] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Optimizing data freshness, throughput, and delay in multi-server information-update systems,” in _2016 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2016, pp. 2569–2573.
  * [19] F. Li, Y. Sang, Z. Liu, B. Li, H. Wu, and B. Ji, “Waiting but not aging: Optimizing information freshness under the pull model,” _IEEE/ACM Transactions on Networking_ , vol. 29, no. 1, pp. 465–478, 2020.
  * [20] J. Sun, Z. Jiang, B. Krishnamachari, S. Zhou, and Z. Niu, “Closed-form whittle’s index-enabled random access for timely status update,” _IEEE Transactions on Communications_ , vol. 68, no. 3, pp. 1538–1551, 2019\.
  * [21] B. Sombabu and S. Moharir, “Age-of-information based scheduling for multi-channel systems,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 7, pp. 4439–4448, 2020.
  * [22] Y.-P. Hsu, E. Modiano, and L. Duan, “Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals,” _IEEE Transactions on Mobile Computing_ , vol. 19, no. 12, pp. 2903–2915, 2019.
  * [23] U. Karabulut, A. Awada, I. Viering, M. Simsek, and G. P. Fettweis, “Spatial and temporal channel characteristics of 5g 3d channel model with beamforming for user mobility investigations,” _IEEE Communications Magazine_ , vol. 56, no. 12, pp. 38–45, 2018.
  * [24] Y. Zeng and R. Zhang, “Optimized training for net energy maximization in multi-antenna wireless energy transfer over frequency-selective channel,” _IEEE Transactions on Communications_ , vol. 63, no. 6, pp. 2360–2373, 2015\.
  * [25] J. Zhang, X. Zhou, T. Ge, X. Wang, and T. Hwang, “Joint task scheduling and containerizing for efficient edge computing,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 8, pp. 2086–2100, 2021.
  * [26] S. Halder, A. Ghosal, and M. Conti, “Dynamic super round based distributed task scheduling for uav networks,” _IEEE Transactions on Wireless Communications_ , 2022.
  * [27] U. Saleem, Y. Liu, S. Jangsher, Y. Li, and T. Jiang, “Mobility-aware joint task scheduling and resource allocation for cooperative mobile edge computing,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 1, pp. 360–374, 2020.
  * [28] A. A. Al-Habob, O. A. Dobre, A. G. Armada, and S. Muhaidat, “Task scheduling for mobile edge computing using genetic algorithm and conflict graphs,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 8, pp. 8805–8819, 2020.
  * [29] X. Wang, Z. Ning, and S. Guo, “Multi-agent imitation learning for pervasive edge computing: A decentralized computation offloading algorithm,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 2, pp. 411–425, 2020.
  * [30] 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, 2017.
  * [31] P. Zou, O. Ozel, and S. Subramaniam, “Optimizing information freshness through computation–transmission tradeoff and queue management in edge computing,” _IEEE/ACM Transactions on Networking_ , vol. 29, no. 2, pp. 949–963, 2021\.
  * [32] M. A. Abd-Elmagid and H. S. Dhillon, “Age of information in multi-source updating systems powered by energy harvesting,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 3, no. 1, pp. 98–112, 2022.
  * [33] R. Li, Q. Ma, J. Gong, Z. Zhou, and X. Chen, “Age of processing: Age-driven status sampling and processing offloading for edge-computing-enabled real-time iot applications,” _IEEE Internet of Things Journal_ , vol. 8, no. 19, pp. 14 471–14 484, 2021.
  * [34] L. Huang and E. Modiano, “Optimizing age-of-information in a multi-class queueing system,” in _2015 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2015, pp. 1681–1685.
  * [35] Z. Liu, L. Huang, B. Li, and B. Ji, “Anti-aging scheduling in single-server queues: A systematic and comparative study,” _Journal of Communications and Networks_ , vol. 23, no. 2, pp. 91–105, 2021.
  * [36] A. Maatouk, Y. Sun, A. Ephremides, and M. Assaad, “Status updates with priorities: Lexicographic optimality,” in _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. IEEE, 2020, pp. 1–8.
  * [37] A. Maatouk, M. Assaad, and A. Ephremides, “Age of information with prioritized streams: When to buffer preempted packets?” in _2019 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2019, pp. 325–329.
  * [38] S. K. Kaul and R. D. Yates, “Age of information: Updates with priority,” in _2018 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 2644–2648.
  * [39] J. Xu and N. Gautam, “Peak age of information in priority queuing systems,” _IEEE Transactions on Information Theory_ , vol. 67, no. 1, pp. 373–390, 2020\.
  * [40] M. A. Abd-Elmagid, H. S. Dhillon, and N. Pappas, “A reinforcement learning framework for optimizing age of information in rf-powered communication systems,” _IEEE Transactions on Communications_ , vol. 68, no. 8, pp. 4747–4760, 2020.
  * [41] J. Ren, J. Liu, Y. Zhang, Z. Li, F. Lyu, Z. Wang, and Y. Zhang, “An efficient two-layer task offloading scheme for mec system with multiple services providers,” in _IEEE INFOCOM 2022-IEEE Conference on Computer Communications_. IEEE, 2022, pp. 1519–1528.
  * [42] W. R. Ghanem, V. Jamali, Y. Sun, and R. Schober, “Resource allocation for multi-user downlink miso ofdma-urllc systems,” _IEEE Transactions on Communications_ , vol. 68, no. 11, pp. 7184–7200, 2020.
  * [43] Y. Zhang, C. Ji, N. Qiao, J. Ren, Y. Zhang, and Y. Yang, “Distributed pricing and bandwidth allocation in crowdsourced wireless community networks,” _IEEE Transactions on Mobile Computing_ , 2022.
  * [44] R. Lin, Z. Zhou, S. Luo, Y. Xiao, X. Wang, S. Wang, and M. Zukerman, “Distributed optimization for computation offloading in edge computing,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 12, pp. 8179–8194, 2020.
  * [45] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” _IEEE communications surveys & tutorials_, vol. 19, no. 4, pp. 2322–2358, 2017.
  * [46] V. Patil and H. Kulkarni, “Comparison of confidence intervals for the poisson mean: some new aspects,” _REVSTAT–Statistical Journal_ , vol. 10, no. 2, pp. 211–227, 2012.
  * [47] X. Zhou, C. Wang, R. Tang, and M. Zhang, “Channel estimation based on statistical frames and confidence level in ofdm systems,” _Applied Sciences_ , vol. 8, no. 9, p. 1607, 2018.
  * [48] N. Qiao, S. Yue, Y. Zhang, and J. Ren, “Popec: Paoi-centric task offloading with priority over unreliable channels,” https://drive.google.com/file/d/1G1w3ujpr3EPF4PX2z78LOVFyMo9cumRY/view?usp=sharing, Tech. Rep., 2023.
  * [49] S.-H. Kim and W. Whitt, “Statistical analysis with little’s law,” _Operations Research_ , vol. 61, no. 4, pp. 1030–1045, 2013.
  * [50] Q. He, D. Yuan, and A. Ephremides, “On optimal link scheduling with min-max peak age of information in wireless systems,” in _2016 IEEE International Conference on Communications (ICC)_. IEEE, 2016, pp. 1–7.
  * [51] J. Du, L. Zhao, J. Feng, and X. Chu, “Computation offloading and resource allocation in mixed fog/cloud computing systems with min-max fairness guarantee,” _IEEE Transactions on Communications_ , vol. 66, no. 4, pp. 1594–1608, 2017.
  * [52] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein _et al._ , “Distributed optimization and statistical learning via the alternating direction method of multipliers,” _Foundations and Trends® in Machine learning_ , vol. 3, no. 1, pp. 1–122, 2011\.
  * [53] F. M. Moghadas and H. T. Kakhki, “Queueing maximal covering location-allocation problem: An extension with m/g/1 queueing systems,” _Advances in Decision Sciences_ , vol. 2011, 2011.
  * [54] W. Dinkelbach, “On nonlinear fractional programming,” _Management science_ , vol. 13, no. 7, pp. 492–498, 1967.
  * [55] M. Hong, “A distributed, asynchronous, and incremental algorithm for nonconvex optimization: An admm approach,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 3, pp. 935–945, 2017.
  * [56] G. Scutari, D. P. Palomar, and S. Barbarossa, “Asynchronous iterative water-filling for gaussian frequency-selective interference channels,” _IEEE Transactions on Information Theory_ , vol. 54, no. 7, pp. 2868–2878, 2008.
  * [57] N. Balasubramanian, A. Balasubramanian, and A. Venkataramani, “Energy consumption in mobile phones: a measurement study and implications for network applications,” in _Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement_ , 2009, pp. 280–293.
  * [58] M. P. Abdollahi, H. Azarhava, A. Haghrah, and J. M. Niya, “On the rate and age of information for non-preemptive systems with prioritized arrivals and deterministic packet deadlines in iot networks,” _Ad Hoc Networks_ , vol. 124, p. 102717, 2022.
  * [59] X. Zhang, M. Hong, S. Dhople, W. Yin, and Y. Liu, “Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data,” _arXiv preprint arXiv:2005.11418_ , 2020.
  * [60] M. Hong, Z.-Q. Luo, and M. Razaviyayn, “Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems,” _SIAM Journal on Optimization_ , vol. 26, no. 1, pp. 337–364, 2016.

|  Nan Qiao received the B.Sc. in Computer Science from Central South
University, China. Since Sept. 2021, he has been pursuing the Ph.D. degree in
Computer Science from Central South University, China. His research interests
include wireless communications, distributed optimization, and Internet-of-
Things.
---|---
|  Sheng Yue received his B.Sc. in mathematics (2017) and Ph.D. in computer
science (2022), from Central South University, China. Currently, he is a
postdoc with the Department of Computer Science and Technology, Tsinghua
University, China. His research interests include network optimization,
distributed learning, and reinforcement learning.
---|---
|  Yongmin Zhang (Senior Member, IEEE) received the PhD degree in control
science and engineering in 2015, from Zhejiang University, Hangzhou, China.
From 2015 to 2019, he was a postdoctoral research fellow in the Department of
Electrical and Computer Engineering at the University of Victoria, BC, Canada.
He is currently a Professor in the School of Computer Science and Engineering
at the Central South University, Changsha, China. His research interests
include IoTs, Smart Grid, and Mobile Computing. He won the best paper award of
IEEE PIMRC 2012 and the IEEE Asia-Pacific (AP) outstanding paper award 2018.
---|---
|  Ju Ren (Senior Member, IEEE) received the B.Sc. (2009), M.Sc. (2012), Ph.D.
(2016) degrees all in computer science, from Central South University, China.
Currently, he is an associate professor with the Department of Computer
Science and Technology, Tsinghua University, China. His research interests
include Internet-of-Things, edge computing, edge intelligence, as well as
security and privacy. He currently serves as an associate editor for many
journals, including IEEE Transactions on Cloud Computing and IEEE Transactions
on Vehicular Technology, etc. He also served as the general co-chair for IEEE
BigDataSE’20, the TPC co-chair for IEEE BigDataSE’19, the publicity co-chair
for IEEE ICDCS’22, the poster co-chair for IEEE MASS’18, a symposium co-chair
for IEEE/CIC ICCC’23&19, I-SPAN’18 and IEEE VTC’17 Fall, etc. He received many
best paper awards from IEEE flagship conferences, including IEEE ICC’19 and
IEEE HPCC’19, etc., the IEEE TCSC Early Career Researcher Award (2019), and
the IEEE ComSoc Asia-Pacific Best Young Researcher Award (2021). He was
recognized as a highly cited researcher by Clarivate (2020-2022).
---|---

## Appendix A

The previous have investigated $\mathbb{E}[T^{p}_{n}]$,
$\mathbb{E}[I^{p}_{n}]$ and $\mathbb{E}[Y^{p}_{n}]$ too much, with
$\mathbb{E}[Y^{p}_{n}]=1/\mu_{n}$ being the processing time,
$\mathbb{E}[T^{p}_{n}]=T^{\mathit{tr}}_{n,c}$ the maximum transmission time
over all possible channels, and
$\mathbb{E}[I^{p}_{n}]=1/\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}$
the arrival interval [11]. Also, some studies discuss the waiting time
$\mathbb{E}[W]$ in the condition multi-class M/G/1[34] or M/G/1 with
priority[39]. However, we focus more on the value of $\mathbb{E}[W]$ in multi-
class M/G/1 with priority, which means there are a number of different types
of users in a unified priority in the M/G/1 system. According to Little’s Law,

$\displaystyle\mathbb{E}[L_{i}]=\lambda_{i}\mathbb{E}[W_{i}].$ (59)

For the highest priority users i.e.$\delta=1$, it holds

$\displaystyle\mathbb{E}[W_{\delta=1}]$
$\displaystyle=\sum_{i\in\mathcal{N}^{1}}\frac{\mathbb{E}[L_{i}]}{\mu_{i}}+\sum_{i\in\mathcal{N}}\rho_{i}\mathbb{E}[\nu^{2}_{i}]$
$\displaystyle=\sum_{i\in\mathcal{N}^{1}}\rho_{i}\mathbb{E}[W_{i}]+\sum_{i\in\mathcal{N}}\rho_{i}\mathbb{E}[\nu^{2}_{i}]$
(60)

where $\mathbb{E}[W_{\delta=1}]=\mathbb{E}[W_{i}],~{}\forall~{}\delta(i)=1$.
Accordingly, we obtain

$\displaystyle\mathbb{E}[W_{\delta=1}]=\frac{\sum_{i\in\mathcal{N}}\rho_{i}\mathbb{E}[\nu^{2}_{i}]}{1-\sum_{i\in\mathcal{N}^{1}}\rho_{i}}$
(61)

We separate $\mathbb{E}[W]$ into different components in order to break it
down into smaller parts. The first component consists of all high-priority or
identically prioritized jobs that are in the queue when the current task
arrives. The waiting time for this component is $\mathbb{E}[S^{1}]$. The
second component, consisting of all high-priority users who arrived at the
same time as the first component was executed, has a waiting time of
$\mathbb{E}[S^{2}]$. We continue to split the remaining portions in the same
way.

$\displaystyle\mathbb{E}[W_{i}]=\mathbb{E}[S^{1}_{i}+S^{2}_{i}+S^{3}_{i}+\cdots]=\sum^{\infty}_{k}\mathbb{E}[S^{k}_{i}]$
(62)

Based on the above discussion, we derive the waiting time for the first part,

$\displaystyle\mathbb{E}[S^{1}_{i}]=\sum_{p=1}^{\delta(i)}\sum_{j\in\mathcal{N}^{p}}\rho_{j}\mathbb{E}[W_{j}]+\sum_{j\in\mathcal{N}}\rho_{j}\mathbb{E}[\nu^{2}_{j}]$
(63)

The waiting time for the other part is as follows,

$\displaystyle E[S^{k+1}_{i}]$
$\displaystyle=\int_{s=0}^{\infty}E[S^{k+1}_{i}\mid S^{k}_{i}=s]f_{k}(s)ds$
$\displaystyle=\int_{s=0}^{\infty}\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j}sf_{k}(s)ds$
$\displaystyle=\left(\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j}\right)E[S^{k}_{i}]$
$\displaystyle=\left(\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j}\right)^{k}E[S^{1}_{i}]$
(64)

Thus, we derive

$\displaystyle\mathbb{E}[W_{i}]$
$\displaystyle=\frac{\mathbb{E}[S^{1}_{i}]}{1-\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j}}$
$\displaystyle=\frac{\sum_{p=1}^{\delta(i)}\sum_{j\in\mathcal{N}^{p}}\rho_{j}\mathbb{E}[W_{j}]+\sum_{j\in\mathcal{N}}\rho_{j}\mathbb{E}[\nu^{2}_{j}]}{1-\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j}}$
(65)

which can be transformed into

$\displaystyle\mathbb{E}[W_{i}](1-\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j})$
$\displaystyle=\sum_{p=1}^{\delta(i)}\sum_{j\in\mathcal{N}^{p}}\rho_{j}\mathbb{E}[W_{j}]+\sum_{j\in\mathcal{N}}\rho_{j}\mathbb{E}[\nu^{2}_{j}]$
(66)

and

$\displaystyle\mathbb{E}[W_{\delta=\delta(i)}](1-\sum_{p=1}^{\delta(i)}\sum_{j\in\mathcal{N}^{p}}\rho_{j})$
$\displaystyle=\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j}\mathbb{E}[W_{j}]+\sum_{j\in\mathcal{N}}\rho_{j}\mathbb{E}[\nu^{2}_{j}]$
$\displaystyle=\mathbb{E}[W_{\delta=\delta(i)-1}](1-\sum_{p=1}^{\delta(i)-2}\sum_{j\in\mathcal{N}^{p}}\rho_{j})$
(67)

In other words, it holds,

$\displaystyle\mathbb{E}[W_{\delta=\delta(i)}](1-\sum_{p=1}^{\delta(i)}\sum_{j\in\mathcal{N}^{p}}\rho_{j})(1-\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j})$
(68) $\displaystyle=$
$\displaystyle\mathbb{E}[W_{\delta=\delta(i)-1}](1-\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j})(1-\sum_{p=1}^{\delta(i)-2}\sum_{j\in\mathcal{N}^{p}}\rho_{j})$

Combine with (61), we obtain

$\displaystyle\mathbb{E}[W_{\delta=\delta(i)}]=\frac{\mathbb{E}[W_{\delta=1}](1-\sum_{j\in\mathcal{N}^{1}}\rho_{j})}{(1-\sum_{p=1}^{\delta(i)}\sum_{j\in\mathcal{N}^{p}}\rho_{j})(1-\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j})}$
$\displaystyle=\frac{\sum_{i\in\mathcal{N}}\rho_{j}\mathbb{E}[\nu^{2}_{j}]}{(1-\sum_{p=1}^{\delta(i)}\sum_{j\in\mathcal{N}^{p}}\rho_{j})(1-\sum_{p=1}^{\delta(i)-1}\sum_{j\in\mathcal{N}^{p}}\rho_{j})}$
(69)

which merges the value of $\mathbb{E}[T^{p}_{n}]$, $\mathbb{E}[I^{p}_{n}]$ and
$\mathbb{E}[Y^{p}_{n}]$ to complete the proof

##  Appendix B A Proof of Lemma 1

First, we should prove that (8) and (11) are not convex sets. Take (8) as an
example, if it was a convex set, we should have obtained

$(1-r)h(\bm{\eta}^{u}_{c_{1}})+rh(\bm{\eta}^{u}_{c_{2}})\mathop{\geq}^{(a)}h((1-r)\bm{\eta}^{u}_{c_{1}}+r\bm{\eta}^{u}_{c_{2}}),$
(70)

where
$h(\bm{\eta}^{u}_{c})=\langle\bm{\lambda},\bm{\eta}^{u}_{c}\rangle+z_{2}\sqrt{\langle\bm{\lambda},\bm{\eta}^{u}_{c}\rangle+z^{2}_{2}/4}+z^{2}_{1}/2-M_{c}^{\mathit{max}}$,
$\bm{\lambda}:=\\{\lambda_{n}\\}_{n\in\mathcal{N}}$,
$\bm{\eta}^{u}_{c}:=\\{\eta^{u}_{n,c}|\\}_{n\in\mathcal{N}}$, $\forall
r\in[0,1]$, $\\{c1,c2\in\mathcal{C}\\}$, $h(\bm{\eta}^{u}_{c_{1}})\leq 0$ and
$h(\bm{\eta}^{u}_{c_{2}})\leq 0$. Moreover, inequality (a) is equivalent to

$r(r-1)(\sqrt{\langle\bm{\lambda},\bm{\eta}^{u}_{c_{1}}\rangle}+\sqrt{\langle\bm{\lambda},\bm{\eta}^{u}_{c_{2}}\rangle})^{2}\geq
2r(1-r)z^{2}_{2}/4.$ (71)

However, if $r\neq 0~{}or~{}1$, inequality (71) does not hold since the right
term is higher than zero and the left term of the inequality is less than
zero. Hence, (8) is a nonconvex set. A comparable procedure in (11) can lead
to the same conclusion.

Next, we will demonstrate that (8) and (11) are comparable to (21) and (22)
and are convex sets. Again, let’s take the example of (8), which is equivalent
to

$\displaystyle\langle\bm{\lambda},\bm{\eta}^{u}_{c}\rangle+z^{2}_{1}/2+z_{2}\sqrt{\langle\bm{\lambda},\bm{\eta}^{u}_{c}\rangle+z^{2}_{2}/4}\leq
M_{c}^{\mathit{max}},$
$\displaystyle(z_{2}/2+\sqrt{\langle\bm{\lambda},\bm{\eta}^{u}_{c}\rangle+z^{2}_{2}/4})^{2}\leq
M_{c}^{\mathit{max}}-z^{2}_{1}/2+z^{2}_{2}/4,$
$\displaystyle\langle\bm{\lambda},\bm{\eta}^{u}_{c}\rangle\leq
M_{c}^{\mathit{max}}+\frac{z^{2}_{2}}{2}-\frac{z^{2}_{1}}{2}-z_{2}\sqrt{M_{c}^{\mathit{max}}+\frac{z^{2}_{2}}{2}-\frac{z^{2}_{1}}{2}},$
(72)

which means that the constraint (8) is transformed mathematically into (21),
which is an affine set and a kind of convex set. (22) can be obtained in a
similar way.

##  Appendix C A Proof of Theorem 1

The objective function that needs to be proven convexity is

$f_{n}(\hat{t}^{\mathit{tr}},\bm{\eta}^{u})=F^{T}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})+F^{I}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})+F^{W}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})+F^{Y}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u}),$

where
$F^{I}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})=F^{I}_{n}(\bm{\eta}^{u})=\frac{1}{\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}}$,
$F^{T}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})=\hat{t}^{\mathit{tr}}_{n}$,
$F^{Y}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})=\frac{1}{\mu}$, and
$F^{W}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})=F^{W}_{n}(\bm{\eta}^{u})=(\frac{1}{2}\sum_{n^{\prime}=1}^{\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}\nu)/(1-\sum_{n^{\prime}=1}^{\mathcal{N}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\frac{\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}}{\mu})$.

  1. 1.

Due to properties of linear functions, it is obvious that
$\nabla^{2}F^{T}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})\succeq 0$.

  2. 2.

Due to properties of constant functions, it holds that
$\nabla^{2}F^{Y}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})\succeq 0$.

  3. 3.

Furthermore, we have $\\{n,m,m_{1},m_{2}\in\mathcal{N}|n=m\&n\neq m_{1}\&n\neq
m_{2}\\}$ , $\\{c,d,d_{1},d_{2}\cdots d_{\mathit{max}}\in\mathcal{C}\\}$,
$\bm{p}_{n}=\\{p_{n,1}\cdots p_{n,C}\\}$, and
$\bm{p}=\\{\bm{p}_{n}|n\in\mathcal{N}\\}$. We list some key second-order
derivatives.

$\displaystyle\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda^{2}_{m,c}}$
$\displaystyle=\frac{2p^{2}_{m,c}}{(\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n})^{3}},$
(73)
$\displaystyle\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda_{m,d_{1}}\partial\lambda_{m,d_{2}}}$
$\displaystyle=\frac{2p_{n,d_{1}}p_{n,d_{2}}}{(\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n})^{3}},$
(74)
$\displaystyle\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda_{m,c}\partial\lambda_{m_{1},c}}$
$\displaystyle=\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda_{m_{1},c}\partial\lambda_{m_{2},c}}=\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda^{2}_{n_{1},c}}=0.$
(75)

Combining Eq.(73), Eq.(74), and Eq.(75), the Hessian matrix of
$F^{I}_{n}(\bm{\eta}^{u})$ is described as

$\displaystyle\mathbf{H}^{I}_{n}(\bm{\eta}^{u})=\left[\begin{array}[]{c|c}\bm{A}&\bm{B}\\\
\hline\cr\bm{C}&\bm{D}\end{array}\right]$ (78)

where $\bm{D}=\bm{O}^{(N-1)C}$, $\bm{B}=\bm{C}^{T}=\bm{O}^{C\times(N-1)C}$ and
$\bm{A}=\left[\begin{array}[]{ccc}\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda^{2}_{m,d_{1}}}&\cdots&\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda_{m,d_{1}}\partial\lambda_{m,d_{\mathit{max}}}}\\\
\vdots&\ddots&\vdots\\\
\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda_{m,d_{\mathit{max}}}\partial\lambda_{m,d_{1}}}&\cdots&\frac{\partial^{2}F^{I}_{n}(\bm{\eta}^{u})}{\partial\lambda^{2}_{m,d_{\mathit{max}}}}\end{array}\right]^{C\times
C}=\frac{\bm{p}^{T}_{n}\times\bm{p}_{n}}{(\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n})^{3}}$
denotes second-order derivative matrix at $m=n$, i.e.$\bm{A}\succeq 0$. The
leading Principle Submatrix of $\mathbf{H}^{I}_{n}(\bm{\eta}^{u})$ are all
greater than 0,
i.e.$\nabla^{2}F^{I}_{n}(\hat{t}^{\mathit{tr}},\bm{\eta}^{u})\succeq 0$.

  4. 4.

As for $F^{W}_{n}(\bm{\eta}^{u})$, it holds

$\displaystyle\frac{\partial^{2}F^{W}_{n}(\bm{\eta}^{u})}{\partial\lambda_{m_{1},d_{1}}\partial\lambda_{m_{2},d_{2}}}=\bm{p}_{m_{1},d_{1}}\bm{p}_{m_{2},d_{2}}\frac{\nu/\mu}{(1-\sum_{m=1}^{\mathcal{N}}\sum_{c\in\mathcal{C}}p_{m,c}\frac{\lambda_{m,c}}{\mu})^{3}}$
(79)

The hessian matrix is described as

$\displaystyle\nabla^{2}F^{W}_{n}(\bm{\eta}^{u})=\bm{p}^{T}\times\bm{p}\frac{\nu/\mu}{(1-\sum_{m=1}^{\mathcal{N}}\sum_{c\in\mathcal{C}}p_{m,c}\frac{\lambda_{m,c}}{\mu})^{3}}$
(80)

Thus, we derive
$\nabla^{2}F^{W}_{n}(\hat{t}^{\mathit{tr}},\bm{\eta}^{u})\succeq 0$.

Above all, $\nabla^{2}f_{n}(\hat{t}^{\mathit{tr}},\bm{\eta}^{u})\succeq 0$.
The proof is completed.

##  Appendix D Details of Optimal Solution to P1-3

The augmented Lagrangian for problem P1-3 can be expressed as,

$\displaystyle L_{\rho}(\\{\bm{x}_{n}\\},\bm{x}_{o},\\{\bm{\sigma}_{n}\\})$
$\displaystyle=\sum_{n\in\mathcal{N}}(g_{n}(\bm{x}_{n})+\langle\bm{\sigma}_{n},\bm{x}_{n}-\bm{x}_{o}\rangle$
$\displaystyle+(\rho/2)\|\bm{x}_{n}-\bm{x}_{o}\|^{2}_{2}$ (81)

where $\bm{\sigma}_{n}=\\{\sigma^{n}_{m,c}|c\in\mathcal{C},m\in\mathcal{N}\\}$
are the associated Lagrangian multiplier with respect to the problem P3 and
$\rho$ is a positive penalty parameter.

$\displaystyle\Longrightarrow\bm{x}^{t+1}_{n}$
$\displaystyle=\arg\min_{\bm{x}_{n}}(G_{n}(\bm{x}_{n})+\langle\bm{\sigma}^{t}_{n},\bm{x}_{n}-\bm{x}_{o}\rangle$
$\displaystyle+(\rho/2)\|\bm{x}_{n}-\bm{x}^{t}_{o}\|^{2}_{2})$ (82)
$\displaystyle\bm{x}^{t+1}_{o}$
$\displaystyle=\frac{1}{N}\sum_{n\in\mathcal{N}}(\bm{x}^{t+1}_{n}+(\frac{1}{\rho}\bm{\sigma}^{t}_{n}))$
(83) $\displaystyle\bm{\sigma}^{t+1}_{n}$
$\displaystyle=\bm{\sigma}^{t}_{n}+\rho(\bm{x}^{t+1}_{n}-\bm{x}^{t+1}_{o})$
(84)

The specific method is described in Algorithm 5

1 for  _$n=1$ to $N$_ do

Input: $\epsilon^{Primal}$, $\epsilon^{Dual}$, $\theta$, $\bm{x}_{n}$, $s$,
$k$

2 while  _$\|\bm{x}^{t+1}_{n}-\bm{x}^{t+1}_{o}\|^{2}_{2} >\epsilon^{Primal}$
or $\rho\|(\bm{x}^{t+1}_{o})-\bm{x}^{t}_{o})\|^{2}_{2}>\epsilon^{Dual}$_ do

3 Calculate $\bm{x}^{t+1}_{n}$, simultaneously according to (D)

4 Calculate $\bm{x}^{t+1}_{o}$, according to (83)

5 Calculate $\sigma^{t+1}_{n}$, according to (84)

6 Update $k=k+1$

7

8 end while

9 Set $\bm{x}^{*}_{n}=\bm{x}^{t+1}_{n}$

Output: $\bm{x}^{*}_{n}$

10

11 end for

Algorithm 5 ADMM-Consensus (AC)

##  Appendix E A Proof of Proposition 1

A brief idea of the proof is given as follows. According to nonlinear
fractional programming [54], $\theta^{*}_{n}$ is achieved if and only if

$\displaystyle\mathop{\min}_{\bm{x}_{n}}f^{p,u}_{n}(\bm{x}_{n})-\theta^{*}_{n}f^{p,l}_{n}(\bm{x}_{n})$
$\displaystyle=f^{p,u}_{n}(\bm{x}_{n}^{*})-\theta^{*}_{n}f^{p,l}_{n}(\bm{x}_{n}^{*})=0.$
(85)

which outlines the necessary and sufficient criteria in order to reach
$\theta^{*}_{n}$. In light of this, $\\{\bm{x}_{n}\\}$ can be acquired by
resolving the following transformation problem.

##  Appendix F A Proof of Proposition 2

Here is a concise proof followed by a comprehensive one.

###  F-A A Concise Proof

  1. 1.

Given the complexity of the proof, we will only provide a brief overview of
the main idea here. We begin by computing the Hessian matrix of the entire
function. Due to differing priority attributes ($\delta(n_{1})>\delta(n_{2})$,
$\delta(n_{1})=\delta(n_{2})$, n1=n2,$\delta(n_{1})<\delta(n_{2})$), we need
to examine the second derivative of the function in at least 16 cases.

  2. 2.

Through analyzing the properties of the Hessian matrix, we observe that the
function is Lipschitz smooth or gradient Lipschitz continuous as long as the
values in the Hessian matrix are finite.

  3. 3.

We can also obtain the value of $\ell_{n}$in $\ell_{n}I\succeq\nabla^{2}F$
based on the characteristics of the Hessian matrix.

###  F-B A Comprehensive Proof

For computational convenience, we present some functions, where
$\Phi_{\delta(n)}(\bm{x})=1-\sum_{\delta=1}^{\delta(n)}\sum_{n^{\prime}=1}^{\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\frac{\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}}{\mu_{n^{\prime}}}$,
$\Phi_{0}(\bm{x})=1$,
$\Upsilon(\bm{x})=\frac{1}{2}\sum_{\delta=1}^{\Delta}\sum_{n^{\prime}=1}^{\mathcal{N}^{\delta}}\sum_{c\in\mathcal{C}}p_{n^{\prime},c}\eta^{u}_{n^{\prime},c}\lambda_{n^{\prime}}\nu_{n^{\prime}}$,
and $\Psi_{n}(\bm{x})=\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}$.
We also give some useful parameters in advance, where
$\\{n_{1},n_{2}\in\mathcal{N}\\}$, $\\{c_{1},c_{2}\in\mathcal{C}\\}$,
$\kappa_{1}=\frac{p_{n_{1},c_{1}}}{\mu_{n_{1}}}>0$,
$\kappa^{1}_{\mathit{max}}=\frac{1}{\mu_{\mathit{min}}}>0$, and
$p_{n,c}\in[0,1]$. Additionally, since
$\nabla_{\\{t^{\mathit{tr}}\in\bm{x}\\}}g^{p}_{n}(\bm{x})=0$, we just ignore
it. Due to
$\nabla^{2}_{\eta_{n_{1},c_{1}}\eta_{n_{2},c_{2}}}g^{p}_{n}(\bm{x})=\lambda_{n_{1}}\lambda_{n_{2}}\nabla^{2}_{\lambda_{n_{1},c_{1}}\lambda_{n_{2},c_{2}}}g^{p}_{n}(\bm{x})$,
we have

####  F-B1 Hessian Matrix

We first analyze the function $f^{p,u}_{n}(\bm{x})$,

$\displaystyle f^{p,u}_{n}(\bm{x})$
$\displaystyle=\Phi_{\delta(n)}(\bm{x})\Phi_{\delta(n)-1}(\bm{x})+\Upsilon(\bm{x})\Psi_{n}(\bm{x}).$
(86)

Case I) If $\delta(n_{1})<\delta(n)$, we obtain first-order derivative.

$\displaystyle\frac{\partial
f^{p,u}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}}$
$\displaystyle=-\frac{p_{n_{1},c_{1}}}{\mu_{n_{1}}}(\Phi_{\delta(n)}(\bm{x})+\Phi_{\delta(n)-1}(\bm{x}))$
$\displaystyle+\frac{1}{2}p_{n_{1},c_{1}}\nu_{n_{1}}\Psi_{n}(\bm{x})$ (87)

We obtain some second-order derivatives.

$\frac{\partial^{2}f^{p,u}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}\partial\lambda_{n_{2},c_{2}}}\\\
=\left\\{\begin{array}[]{ll}2\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}},\quad\delta(n_{2})<\delta(n)\\\
\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}+\frac{1}{2}p_{n_{1},c_{1}}p_{n_{2},c_{2}}\nu_{n_{1}},\quad
n_{2}=n\\\
\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}},\quad\delta(n_{2})=\delta(n),\quad
n_{2}\neq n\\\ 0,\quad\delta(n_{2})>\delta(n)\\\ \end{array}\right..$ (88)

Case II) If $\delta(n_{1})=\delta(n)~{}\&~{}n_{1}=n$, we obtain first-order
derivative.

$\displaystyle\frac{\partial
f^{p,u}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}}$
$\displaystyle=-\frac{p_{n_{1},c_{1}}}{\mu_{n_{1}}}\Phi_{\delta(n)-1}(\bm{x})+p_{n_{1},c_{1}}\Upsilon(\bm{x})$
$\displaystyle+\frac{1}{2}p_{n_{1},c_{1}}\nu_{n_{1}}\Psi_{n}(\bm{x})$ (89)

We obtain some second-order derivatives.

$\frac{\partial^{2}f^{p,u}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}\partial\lambda_{n_{2},c_{2}}}=\left\\{\begin{array}[]{ll}&\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}+\frac{1}{2}p_{n_{1},c_{1}}p_{n_{2},c_{2}}\nu_{n_{2}},\\\
&\quad\delta(n_{2})<\delta(n)\\\
&\frac{1}{2}p_{n_{1},c_{1}}p_{n_{2},c_{2}}\nu_{n_{1}}+\frac{1}{2}p_{n_{1},c_{1}}p_{n_{2},c_{2}}\nu_{n_{2}},\\\
&\quad n_{2}=n\\\
&\frac{1}{2}p_{n_{1},c_{1}}p_{n_{2},c_{2}}\nu_{n_{2}},\quad\delta(n_{2})=\delta(n),\\\
&\quad n_{2}\neq n\\\
&\frac{1}{2}p_{n_{1},c_{1}}p_{n_{2},c_{2}}\nu_{n_{2}},\quad\delta(n_{2})>\delta(n)\\\
\end{array}\right..$

Case III) If $\delta(n_{1})=\delta(n)~{}\&~{}n_{1}\neq n$, we obtain first-
order derivative.

$\displaystyle\frac{\partial
f^{p,u}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}}=-\frac{p_{n_{1},c_{1}}}{\mu_{n_{1}}}\Phi_{\delta(n)-1}(\bm{x})+\frac{1}{2}p_{n_{1},c_{1}}\nu_{n_{1}}\Psi_{n}(\bm{x})$
(90)

We obtain some second-order derivatives.

$\frac{\partial^{2}f^{p,u}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}\partial\lambda_{n_{2},c_{2}}}=\left\\{\begin{array}[]{ll}&\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}},\quad\delta(n_{2})<\delta(n)\\\
&\frac{1}{2}p_{n_{1},c_{1}}p_{n_{2},c_{2}}\nu_{n_{1}},\quad n_{2}=n\\\
&0,\quad\delta(n_{2})=\delta(n),\quad n_{2}\neq n\\\
&0,\quad\delta(n_{2})>\delta(n)\\\ \end{array}\right..$ (91)

Case IV) If $\delta(n_{1})>\delta(n)$, we obtain first-order derivative.

$\displaystyle\frac{\partial
f^{p,u}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}}=\frac{1}{2}p_{n_{1},c_{1}}\nu_{n_{1}}\Psi_{n}(\bm{x})$
(92)

We obtain some second-order derivatives.

$\frac{\partial^{2}f^{p,u}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}\partial\lambda_{n_{2},c_{2}}}=\left\\{\begin{array}[]{ll}&0,\quad\delta(n_{2})<\delta(n)\\\
&\frac{1}{2}p_{n_{1},c_{1}}p_{n_{2},c_{2}}\nu_{n_{1}},\quad n_{2}=n\\\
&0,\quad\delta(n_{2})=\delta(n),\quad n_{2}\neq n\\\
&0,\quad\delta(n_{2})>\delta(n)\\\ \end{array}\right..$ (93)

As for $f^{p,l}_{n}(\bm{x})$, we have some different cases, as follows.

$\displaystyle f^{p,l}_{n}(\bm{x})$
$\displaystyle=\Psi_{n}(\bm{x})\Phi_{\delta(n)}(\bm{x})\Phi_{\delta(n)-1}(\bm{x}).$
(94)

Case I) If $\delta(n_{1})<\delta(n)$, we obtain first-order derivative.

$\displaystyle\frac{\partial
f^{p,l}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}}=-\frac{p_{n_{1},c_{1}}}{\mu_{n_{1}}}(\Phi_{\delta(n)}(\bm{x})+\Phi_{\delta(n)-1}(\bm{x}))\Psi_{n}(\bm{x})$
(95)

We obtain some second-order derivatives.

$\noindent\frac{\partial^{2}f^{p,l}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}\partial\lambda_{n_{2},c_{2}}}$
$=\left\\{\begin{array}[]{ll}&2\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}\Psi_{n}(\bm{x}),\quad\delta(n_{2})<\delta(n)\\\
&\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}(\Psi_{n}(\bm{x})-\frac{\nu_{n_{2}}}{2\mu_{n_{2}}}\Phi_{\delta(n)}(\bm{x})-\frac{\nu_{n_{2}}}{2\mu_{n_{2}}}\Phi_{\delta(n)-1}(\bm{x})),\\\
&~{}~{}~{}\quad n_{2}=n\\\
&\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}\Psi_{n}(\bm{x}),\quad\delta(n_{2})=\delta(n),\quad
n_{2}\neq n\\\ &0,\quad\delta(n_{2})>\delta(n)\\\ \end{array}\right..$ (96)

Case II) If $\delta(n_{1})=\delta(n)~{}\&~{}n_{1}=n$, we obtain first-order
derivative.

$\displaystyle\frac{\partial
f^{p,l}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}}$
$\displaystyle=p_{n_{1},c_{1}}\Phi_{\delta(n)}(\bm{x})\Phi_{\delta(n)-1}(\bm{x})$
$\displaystyle-\frac{p_{n_{1},c_{1}}}{\mu_{n_{1}}}\Psi_{n}(\bm{x})\Phi_{\delta(n)-1}(\bm{x})$
(97)

We obtain some second-order derivatives.

$\frac{\partial^{2}f^{p,l}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}\partial\lambda_{n_{2},c_{2}}}$
$=\left\\{\begin{array}[]{ll}&\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}(\Psi_{n}(\bm{x})-\frac{\nu_{n_{2}}}{2\mu_{n_{2}}}\Phi_{\delta(n)}(\bm{x})-\frac{\nu_{n_{2}}}{2\mu_{n_{2}}}\Phi_{\delta(n)-1}(\bm{x})),\\\
&\quad\delta(n_{2})<\delta(n)\\\
&-\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}(\frac{\nu_{n_{1}}}{2\mu_{n_{1}}}+\frac{\nu_{n_{2}}}{2\mu_{n_{2}}})\Phi_{\delta(n)-1}(\bm{x}),\quad
n_{2}=n\\\
&-\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}\frac{\nu_{n_{2}}}{2\mu_{n_{2}}}\Phi_{\delta(n)-1}(\bm{x}),\quad\delta(n_{2})=\delta(n),\quad
n_{2}\neq n\\\ &0,\quad\delta(n_{2})>\delta(n)\\\ \end{array}\right..$ (98)

Case III) If $\delta(n_{1})=\delta(n)~{}\&~{}n_{1}\neq n$, we obtain first-
order derivative.

$\displaystyle\frac{\partial
f^{p,l}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}}=-\frac{p_{n_{1},c_{1}}}{\mu_{n_{1}}}\Psi_{n}(\bm{x})\Phi_{\delta(n)-1}(\bm{x})$
(99)

We obtain some second-order derivatives.

$\frac{\partial^{2}f^{p,l}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}\partial\lambda_{n_{2},c_{2}}}=\left\\{\begin{array}[]{ll}&\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}\Psi_{n}(\bm{x}),\quad\delta(n_{2})<\delta(n)\\\
&-\frac{p_{n_{1},c_{1}}p_{n_{2},c_{2}}}{\mu_{n_{1}}\mu_{n_{2}}}\frac{\nu_{n_{2}}}{2\mu_{n_{2}}}\Phi_{\delta(n)-1}(\bm{x}),\quad
n_{2}=n\\\ &0,\quad n_{2}\neq n\\\ &0,\quad\delta(n_{2})>\delta(n)\\\
\end{array}\right..$ (100)

Case IV) If $\delta(n_{1})>\delta(n)$, we obtain first and second-order
derivative.

$\displaystyle\frac{\partial
f^{p,l}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}}=0$
$\displaystyle\frac{\partial^{2}f^{p,l}_{n}(\bm{x})}{\partial\lambda_{n_{1},c_{1}}\partial\lambda_{n_{2},c_{2}}}=0.$
(101)

Above all, we have the first-order derivative and the second-order derivative
information of
$g^{p}_{n}(\bm{x})=f^{p,u}_{n}(\bm{x})-\theta^{*}_{n}f^{p,l}_{n}(\bm{x})$.

####  F-B2 The Relationship between Hessian Matrix and Lipschitz Smooth

Obviously, for any $n$, $g^{p}_{n}(\bm{x})$ is a smooth function.

On the other hand, the twice differentiable function $g^{p}_{n}(\bm{x})$ has a
Lipschitz continuous gradient with modulus $\ell_{n}$ if and only if its
Hessian satisfies $\ell_{n}I\succeq\nabla^{2}g^{p}_{n}(\bm{x})$. We have
$\ell_{n}$ is equal to the maximum eigenvalue of
$\nabla^{2}g^{p}_{n}(\bm{x})$,[59].

In order to obtain the maximum eigenvalue, we ought to get the maximum value
of the sum of the absolute values of the elements of the column of the matrix
$\nabla^{2}g^{p}_{n}(\bm{x})$, which is because that if $\xi$ is the
eigenvector of matrix $\mathcal{A}$ with respect to eigenvalue $\omega$.

According to the basic property, we have
$\sum_{j=1}^{n}A_{ij}\xi_{j}=\omega\xi_{i}$,
i.e.$\sum_{j=1}^{n}\left|A_{ij}\right|\left|\xi_{j}\right|\geq|\omega|\left|\xi_{i}\right|$.

Summing over both sides, it is

$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}\left|A_{ij}\right|\left|\xi_{j}\right|\geq\sum_{i=1}^{n}|\omega|\left|\xi_{i}\right|$
(102)

Let $M=\max_{1\leq j\leq n}\sum_{i=1}^{n}\left|A_{ij}\right|$, we have

$\displaystyle
M\sum_{j=1}^{n}\left|\xi_{j}\right|\geq\sum_{j=1}^{n}\left|\xi_{j}\right|\sum_{i=1}^{n}\left|A_{ij}\right|\geq\sum_{i=1}^{n}|\omega|\left|\xi_{i}\right|\geq|\omega|\sum_{i=1}^{n}\left|\xi_{i}\right|$
(103)

Since $\xi$ is not a zero vector, we obtain

$\displaystyle|\omega|\leq\max_{1\leq j\leq
n}\sum_{i=1}^{n}\left|A_{ij}\right|$ (104)

####  F-B3 Solve for the value of $\ell_{n}$

Upper bound on the sum of the absolute values of the elements in the columns
of the matrix $\nabla^{2}_{\bm{\eta}^{u}}g^{p}_{n}(\bm{x})$ is expressed as
$\varphi(\bm{x})\lambda^{2}_{max}$ with
$\lambda_{max}=\mathop{\max}_{n}{\lambda_{n}}$:

$\displaystyle\varphi(\bm{x})$
$\displaystyle\leq\mathop{\max}\Big{\\{}\inf|\varphi_{1}(\bm{x})|,\inf|\varphi_{2}(\bm{x})|,\inf|\varphi_{3}(\bm{x})|,\inf|\varphi_{4}(\bm{x})|\Big{\\}}$
$\displaystyle\mathop{\leq}^{(a)}\mathop{\max}\Big{\\{}\inf|\varphi_{1}(\bm{x})|,\inf|\varphi_{2}(\bm{x})|,\inf|\varphi_{3}(\bm{x})|\Big{\\}}$
$\displaystyle\mathop{\leq}^{(b)}\mathop{\max}\Big{\\{}\inf|\varphi_{1}(\bm{x})|,\inf|\varphi_{3}(\bm{x})|\Big{\\}}$
$\displaystyle\mathop{\leq}^{(c)}\mathop{\max}\Big{\\{}\inf|\varphi_{3}(\bm{x})|\Big{\\}}$
$\displaystyle\mathop{\leq}^{(d)}\frac{1}{\mu^{2}_{\mathit{min}}}\Big{(}\sum_{n_{1}\in\mathcal{N}}|\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}|+\sum_{n_{1}\in\\{<\delta(n)\\}\bigcup\\{n\\}}|1+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|$
$\displaystyle~{}~{}~{}~{}+\sum_{n_{1}\in\\{\leq\delta(n)\\}}|\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|\Big{)},$
(105)

where $\varphi_{1}(\bm{x})$, $\varphi_{2}(\bm{x})$, $\varphi_{3}(\bm{x})$, and
$\varphi_{4}(\bm{x})$ are

Case I) If $\delta(n_{2})<\delta(n)$, we have

$\displaystyle\varphi_{1}(\bm{x})$
$\displaystyle=\overbrace{\sum_{n_{1}\in\\{<\delta(n)\\}}\mid
2\kappa_{1}\kappa_{2}(1-\theta^{*}_{n}\Psi_{n}(\bm{x}))\mid}^{\varphi_{1a}(\bm{x})}$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{n\\}}\mid\kappa_{1}\kappa_{2}(1+\frac{\nu_{n}}{2\mu_{n}\mu_{n_{2}}}+\theta^{*}_{n}(\frac{\nu_{n}}{2\mu_{n}}\Phi_{\delta(n)}(\bm{x})\mid}^{\varphi_{1b}(\bm{x})}$
$\displaystyle+\frac{\nu_{n}}{2\mu_{n}}\Phi_{\delta(n)-1}(\bm{x}))-\Psi_{n}(\bm{x}))$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{=\delta(n)\\}/n}\mid\kappa_{1}\kappa_{2}(1-\theta^{*}_{n}\Psi_{n}(\bm{x}))\mid}^{\varphi_{1c}(\bm{x})}$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{>\delta(n)\\}}0}^{\varphi_{1d}(\bm{x})}.$
(106)

Case II) If $\delta(n_{2})=\delta(n)~{}\&~{}n_{2}\neq n$, we derive

$\displaystyle\varphi_{2}(\bm{x})$
$\displaystyle=\overbrace{\sum_{n_{1}\in\\{<\delta(n)\\}}\mid\kappa_{1}\kappa_{2}(1-\theta^{*}_{n}\Psi_{n}(\bm{x}))\mid}^{\varphi_{2a}(\bm{x})}$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{n\\}}\mid\kappa_{1}\kappa_{2}(\frac{\nu_{n}}{2\mu_{n}\mu_{n_{2}}}+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}\Phi_{\delta(n)}(\bm{x}))\mid}^{\varphi_{2b}(\bm{x})}$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{=\delta(n)\\}/n}\mid\kappa_{1}\kappa_{2}(1-\theta^{*}_{n}\Psi_{n}(\bm{x}))\mid}^{\varphi_{2c}(\bm{x})}$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{>\delta(n)\\}}0}^{\varphi_{2d}(\bm{x})}.$
(107)

Case III) If $n_{2}=n$, we obtain

$\displaystyle\varphi_{3}(\bm{x})$
$\displaystyle=\overbrace{\sum_{n_{1}\in\\{<\delta(n)\\}}\mid\kappa_{1}\kappa_{2}(1+\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}+\theta^{*}_{n}(\frac{\nu_{n}}{2\mu_{n}}\Phi_{\delta(n)}(\bm{x})}^{\varphi_{3a}}$
$\displaystyle+\frac{\nu_{n}}{2\mu_{n}}\Phi_{\delta(n)-1}(\bm{x}))(\bm{x})-\Psi_{n}(\bm{x}))\mid$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{n\\}}\mid
2\kappa_{1}\kappa_{2}(1+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}\Phi_{\delta(n)-1}(\bm{x}))\mid}^{\varphi_{3b}(\bm{x})}$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{=\delta(n)\\}/n}\mid\kappa_{1}\kappa_{2}(\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}\Phi_{\delta(n)}(\bm{x}))\mid}^{\varphi_{3c}(\bm{x})}$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{>\delta(n)\\}}\mid\kappa_{1}\kappa_{2}\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}\mid}^{\varphi_{3d}(\bm{x})}.$
(108)

Case IV) If $\delta(n_{2})>\delta(n)$, we gain

$\displaystyle\varphi_{4}(\bm{x})$
$\displaystyle=\overbrace{\sum_{n_{1}\in\\{<\delta(n)\\}}0}^{\varphi_{4a}(\bm{x})}+\overbrace{\sum_{n_{1}\in\\{n\\}}\mid\kappa_{1}\kappa_{2}\frac{\nu_{n}}{2\mu_{n}\mu_{n_{2}}}\mid}^{\varphi_{4b}(\bm{x})}$
$\displaystyle+\overbrace{\sum_{n_{1}\in\\{=\delta(n)\\}/n}0}^{\varphi_{4c}(\bm{x})}+\overbrace{\sum_{n_{1}\in\\{>\delta(n)\\}}0}^{\varphi_{4d}(\bm{x})}.$
(109)

Eq.(F-B3) holds because:

  * •

(a) holds because $\varphi_{2}(\bm{x})>\varphi_{4}(\bm{x})$.

  * •

(b) holds because $\inf|\varphi_{2}(\bm{x})|<\inf|\varphi_{1}(\bm{x})|$

  * •

(c) holds because $\inf|\varphi_{1}(\bm{x})|<\inf|\varphi_{3}(\bm{x})|$

  * •

(d) holds because

$\displaystyle\inf|\varphi_{3}(\bm{x})|\leq|\kappa^{2}_{\mathit{max}}|\Big{(}\sum_{n_{1}\in\\{<\delta(n)\\}}|1+\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}+2\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|$
$\displaystyle+\sum_{n_{1}\in\\{n\\}}|2(1+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}})|+\sum_{n_{1}\in\\{=\delta(n)\\}/n}|\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|$
$\displaystyle+\sum_{n_{1}\in\\{>\delta(n)\\}}|\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}|\Big{)}$
$\displaystyle=\frac{1}{\mu^{2}_{\mathit{min}}}\Big{(}\sum_{n_{1}\in\mathcal{N}}|\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}|+\sum_{n_{1}\in\\{<\delta(n)\\}\bigcup\\{n\\}}|1+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|$
$\displaystyle+\sum_{n_{1}\in\\{\leq\delta(n)\\}}|\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|\Big{)}$
(110)

Let $\omega^{G}$ denote the the eigenvalue of $\nabla^{2}g^{p}_{n}$,

$\displaystyle|\omega^{G}|$ $\displaystyle\leq$
$\displaystyle\frac{\lambda^{2}_{\mathit{max}}}{\mu^{2}_{\mathit{min}}}\Big{(}\sum_{n_{1}\in\mathcal{N}}|\frac{\nu_{n}}{2\mu_{n}\mu_{n_{1}}}|+\sum_{n_{1}\in\\{<\delta(n)\\}\bigcup\\{n\\}}|1+\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|$
$\displaystyle+\sum_{n_{1}\in\\{\leq\delta(n)\\}}|\theta^{*}_{n}\frac{\nu_{n}}{2\mu_{n}}|\Big{)}$
$\displaystyle=$ $\displaystyle K_{n},$ (111)

where $\mu_{min}=\mathop{\min}_{n}\mu_{n}$ and
$\lambda_{max}=\mathop{\max}_{n}\lambda_{n}$. Thus, if $\ell_{n}=K_{n}$ are
limited, $\ell_{n}I\succeq\nabla^{2}g^{p}_{n}(\bm{x})$ and $g^{p}_{n}(\bm{x})$
is Lipschiz smooth.

##  Appendix G A Proof of Theorem 2

###  G-A convergence Analysis

First, we prove the convergence of Algorithm 2. There are some properties in
$g^{p}_{n}\left(\bm{\lambda}\right)$, as follows,

  1. 1.

there exists a positive constant $\ell_{n}>0$, it has $\left\|\nabla
g^{p}_{n}\left(\bm{\lambda}\right)-\nabla
g^{p}_{n}\left(\bm{x}^{{}^{\prime}}\right)\right\|\leq\ell_{n}\left\|\bm{\lambda}-\bm{x}^{{}^{\prime}}\right\|\quad\forall\bm{\lambda},\bm{x}^{{}^{\prime}}$

  2. 2.

for any $n$, the $\rho_{n}$ chosen is large enough,
$\rho_{n}>\max\left\\{\frac{2\ell_{n}^{2}}{\varepsilon_{n}},\ell_{n}\right\\}$,
where $\varepsilon_{n}$ satisfies
$\varepsilon_{n}I\preceq\nabla^{2}L^{p}_{n}(\bm{x})$

  3. 3.

$\mathop{\min}_{\bm{x}\in\Omega}g^{p}_{n}(\bm{x})>-\infty$

Proof of Property 1), Proposition 2 has proven there exists a positive
constant $\ell_{n}>0$ satisfies $\ell_{n}I\succeq\nabla^{2}g^{p}_{n}(\bm{x})$,
i.e.$\left\|\nabla g^{p}_{n}\left(\bm{\lambda}\right)-\nabla
g^{p}_{n}\left(\bm{x}^{{}^{\prime}}\right)\right\|\leq\ell_{n}\left\|\bm{\lambda}-\bm{x}^{{}^{\prime}}\right\|\quad\forall\bm{\lambda},\bm{x}^{{}^{\prime}}$.

Proof of Property 2), obviously, since
$\varepsilon_{n}I\preceq\nabla^{2}L^{p}_{n}(\bm{x})$,
$\varepsilon_{n}=-\ell_{n}+\rho_{n}$. Due to $\rho_{n}>2\ell_{n}$ and
$\rho_{n}>0$, $(\rho_{n}-2\ell_{n})(\rho_{n}+\ell_{n})>0$. Thus,
$\rho_{n}>\max\left\\{\frac{2\ell_{n}^{2}}{\varepsilon_{n}},\ell_{n}\right\\}$.

Proof of Property 3), when $\bm{x}\in\Omega$, we have,

$\displaystyle
g^{p}_{n}(\bm{x})=f^{p,u}_{n}(\bm{x})-\theta^{*}_{n}f^{p,l}_{n}(\bm{x})$
$\displaystyle=\Phi_{\delta(n)}(\bm{x})\Phi_{\delta(n)-1}(\bm{x})+\Upsilon(\bm{x})\Psi_{n}(\bm{x})$
$\displaystyle-\theta^{*}_{n}\Psi_{n}(\bm{x})\Phi_{\delta(n)}(\bm{x})\Phi_{\delta(n)-1}(\bm{x})$
$\displaystyle\geq-\theta^{*}_{n}\lambda_{n}>-\infty$ (112)

where $\theta^{*}_{n}$ and $\lambda_{n}$ are constant,
$\Phi_{\delta(n)}(\bm{x}),\Phi_{\delta(n)-1}(\bm{x})\in[0,1]$,
$\Psi_{n}(\bm{x})\in[0,\lambda_{n}]$ and $\Upsilon(\bm{x})>0$

  * •

Dual variable convergence $L^{p}_{n}(x;y)$ will increase after each dual.[52]

  * •

Consensus convergence The consensus constraint is satisfied eventually
$\lim_{t\rightarrow\infty}\left\|\bm{x}_{n}^{t+1}-\bm{x}_{o}^{t+1}\right\|=0,\forall
n$.

  * •

Objective Function convergence Above the property 1) and 2), we have

$\displaystyle
L^{p}_{n}\left(\left\\{\bm{x}_{n}^{t+1}\right\\},\bm{x}_{o}^{t+1};y^{t+1}\right)-L^{p}_{n}\left(\left\\{\bm{x}^{t}_{n}\right\\},\bm{x}^{t}_{o};\bm{\sigma}^{t}\right)$
$\displaystyle\leq\sum_{n\in\mathcal{N}}\left(\frac{L_{n}^{2}}{\rho_{n}}-\frac{\varepsilon_{n}}{2}\right)\left\|\bm{x}_{n}^{t+1}-\bm{x}^{t}_{n}\right\|^{2}$
$\displaystyle-\frac{\sum_{n\in\mathcal{N}}\rho_{n}}{2}\left\|\bm{x}_{o}^{t+1}-\bm{x}^{t}_{o}\right\|^{2}<0$
(113)

according to [60]. Thus, $L^{p}_{n}(x;y)$ will decrease after each dual.
Furthermore, according to property 3), we obtain
$L^{p}_{n}\left(\left\\{\bm{x}_{n}^{t+1}\right\\},\bm{x}_{o}^{t+1};y^{t+1}\right)$
is limited.

Thus, the Algorithm 2 will converge to the set of stationary solutions.

###  G-B Convergence Rate

We have proven some properties in $g^{p}_{n}\left(\bm{\lambda}\right)$ and the
convergence of Algorithm 2. Based on [[60], Theorem 2.5.], we have

$\epsilon^{ac}<\frac{k^{\Gamma}(L^{p}\left(\left\\{\bm{x}_{n}^{1}\right\\},\bm{x}_{o}^{1},\bm{\sigma}^{1}\right)-\underline{G^{p}})}{p^{\mathit{sysn}}\Gamma^{sysn}},$
(114)

where $p^{\mathit{sysn}}\Gamma^{sysn}$ means the number of successful
iterations. Therefore, we have

$\Gamma^{sysn}<\frac{k^{\Gamma}(L^{p}\left(\left\\{\bm{x}_{n}^{1}\right\\},\bm{x}_{o}^{1},\bm{\sigma}^{1}\right)-\underline{G^{p}})}{\epsilon^{ac}p^{\mathit{sysn}}},$
(115)

where $\epsilon^{ac}$ is a positive iteration factor, $k^{\Gamma}$ is a
constant,
$p^{\mathit{sysn}}=\Pi_{n\in\mathcal{N}}(\frac{1}{C}\sum_{c\in\mathcal{C}}p_{n,c})$
probability of successfully completing a synchronous update,
$\underline{G^{p}}$ is the lower bound of
$\sum_{n\in\mathcal{N}}g^{p}_{n}(\bm{x}_{n})$, and $\Gamma^{sysn}$ is number
of iterations,
i.e.$\Gamma^{sysn}=\min\left\\{t\mid\eta\left(\bm{x}^{t},\bm{\sigma}^{t}\right)\leq\epsilon,t\geq
0\right\\}$.

Above all, we derive that Algorithm 2 converge to an
$\epsilon^{ac}$-stationary point within
$O(1/(p^{\mathit{sysn}}\epsilon^{\mathit{ac}}))$.

## Appendix H

###  H-A A Proof of Theorem 3

If the amount of migration tasks from the local server to other servers is 0,
i.e.$\phi^{out}(\bm{\eta}^{s})=\sum_{m^{\prime}\in\\{\mathcal{M}/m_{n}\\}}\eta^{s}_{m_{n},m^{\prime}}\sum_{\delta\in\Delta}\lambda^{s}_{\delta,m_{n}}$,
and the amount of migration tasks from other servers to the local server is 0,
i.e.$\phi^{in}(\bm{\eta}^{s})=\sum_{m^{\prime}\in\\{\mathcal{M}/m_{n}\\}}\eta^{s}_{m^{\prime},m_{n}}\sum_{\delta\in\Delta}\lambda^{s}_{\delta,m^{\prime}}$,
the migration decision variableis $y_{m_{n}}=0$. Otherwise, vice versa. Thus,
we obtain

$y_{m_{n}}=\left\\{\begin{array}[]{ll}1,&\quad\phi^{in}(\bm{\eta}^{s})+\phi^{out}(\bm{\eta}^{s})>0\\\
0,&\quad otherwise,\end{array}\right..$ (116)

###  H-B An Alternative Problem for (PoPeC)

If $\phi^{in}(\bm{\eta}^{s})+\phi^{out}(\bm{\eta}^{s})=0$, we derive
$f^{p}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u})=f^{s}_{n}(\hat{t}^{\mathit{tr}}_{n},\bm{\eta}^{u},\bm{\eta}^{s})$.
In other words, if $\phi^{in}(\bm{\eta}^{s})+\phi^{out}(\bm{\eta}^{s})=0$, we
can derive the obtained results can cover all the results of Server
Collaboration, no matter what $y_{m_{n}}$ is. That is
$\frac{1}{N}\sum_{n\in\mathcal{N}}F_{n}(\bm{x},\bm{y},\bm{z})\geq\frac{1}{N}\sum_{n\in\mathcal{N}}F_{n}(\bm{x},\bm{1},\bm{z})$,
where $F_{n}(\bm{x},\bm{y},\bm{z})=\mathbb{E}[A_{n}]$.

Combining Theorem 3 and discussion of constraints, there is a comparable
solution $\hat{\bm{y}^{*}}=\bm{1}$. which holds
$\sum_{n\in\mathcal{N}}F_{n}(\bm{x},\bm{y}^{*},\bm{z})=\sum_{n\in\mathcal{N}}F_{n}(\bm{x},\hat{\bm{y}^{*}},\bm{z})$.
Hence, we have

$\sum_{n\in\mathcal{N}}F_{n}(\bm{x},\hat{\bm{y}^{*}},\bm{z})\leq\sum_{n\in\mathcal{N}}F_{n}(\bm{x},\bm{y},\bm{z})\leq\sum_{n\in\mathcal{N}}F_{n}(\bm{x},\bm{y},\bm{z}).$
(117)

Similar to Problem P1 and P2, we aim to minimize a highly accurate upper bound
for the average expected PAoI of multi-priority users through the following
approach. Thus, one alternative for (PoPeC) is

$\begin{split}\textbf{(P3)}~{}&\mathop{\min}_{\bm{x},\bm{z}}\frac{1}{N}\sum_{n\in\mathcal{N}}F^{1}_{n}(\bm{x},\bm{z})\\\
\text{s.t.}&~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c3a},\eqref{eq:c5a},\eqref{eq:c4a},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},\end{split}$
(118)

where
$F^{1}_{n}(\bm{x},\bm{z})=\hat{t}^{\mathit{tr}}_{n}+\frac{1}{\sum_{c\in\mathcal{C}}p_{n,c}\eta^{u}_{n,c}\lambda_{n}}+\sum_{m\in\mathcal{M}}\pi_{n,m}(\bm{z})$,
$\bm{x}=\\{\hat{t}^{\mathit{tr}},\bm{\eta}^{u}\\}$ and $\bm{z}=\bm{\eta}^{s}$.

##  Appendix I A Proof of Lemma 2

P3 is

$\begin{split}&\mathop{\min}_{\bm{x},\bm{z}}\frac{1}{N}\sum_{n\in\mathcal{N}}F^{1}_{n}(\bm{x},\bm{z})\\\
=&\mathop{\min}_{\bm{x},\bm{z}}\frac{1}{N}\sum_{n\in\mathcal{N}}(F^{2}_{n}(\bm{x})+F^{3}_{n}(\bm{z},\bm{\lambda}^{s}))\\\
\text{s.t.}&~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c3a},\eqref{eq:c4a},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},\\\
\sum_{m^{\prime}\in\mathcal{M}}&\eta^{s}_{m,m^{\prime}}\lambda^{s}_{\delta,m}=\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in
C}p_{n,c}\eta^{u}_{n,c}\lambda_{n},\end{split}$ (119)

If you decompose the problem in terms of different variables,
$\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m,m^{\prime}}\lambda^{s}_{\delta,m}$
and $\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in
C}p_{n,c}\eta^{u}_{n,c}\lambda_{n}$ will always remain consistent due to the
presence of the constraint (4) which is equivalent to

$\lambda^{s}_{\delta,m}\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m,m^{\prime}}=\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in
C}p_{n,c}\eta^{u}_{n,c}\lambda_{n},,\quad\forall m\in\mathcal{M}.$ (120)

This makes it simpler to solve for the best $\bm{x}$ and $\bm{z}$ because
their values don’t change when they are solved iteratively. Therefore, in
addition to decomposing the objective functions and constraints as

(sp1)
$\displaystyle\mathop{\min}_{\bm{x}}\frac{1}{N}\sum_{n\in\mathcal{N}}F^{2}_{n}(\bm{x})$
s.t.
$\displaystyle~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c5a},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},$
(121)

$\begin{split}\textbf{(sp2)}~{}&\mathop{\min}_{\bm{z}}\frac{1}{N}\sum_{n\in\mathcal{N}}F^{3}_{n}(\bm{z},\bm{\lambda}^{s})\\\
\text{s.t.}&~{}\eqref{eq:c3a},\eqref{eq:c5a},\eqref{eq:c4a},\end{split}$ (122)

constraint (4) in sp1 is replaced by the auxiliary inequality (123) as shown
in P3-1,

$\displaystyle\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in
C}p_{n,c}\eta^{u}_{n,c}\lambda_{n}$
$\displaystyle\leq\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m,m^{\prime}}\lambda^{s}_{\delta,m}$
(123)

which leads to a better solution for $\bm{x}$, the reason is as follows

Denote $\bm{x}_{1}$, $\bm{x}_{2}$, $\bm{x}_{3}$ as

$\displaystyle\bm{x}_{1}=\mathop{\arg\min}_{\bm{x}}\Big{\\{}\sum_{n\in\mathcal{N}}F^{2}_{n}(\bm{x})~{}\text{s.t.}~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},$
$\displaystyle\\{\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in
C}p_{n,c}\eta^{u}_{n,c}\lambda_{n}\leq\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m,m^{\prime}}\lambda^{s}_{\delta,m}\\}\Big{\\}}$
$\displaystyle\bm{x}_{2}=\mathop{\arg\min}_{\bm{x}}\Big{\\{}\sum_{n\in\mathcal{N}}F^{2}_{n}(\bm{x})~{}\text{s.t.}~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},$
$\displaystyle\\{\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in
C}p_{n,c}\eta^{u}_{n,c}\lambda_{n}=\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m,m^{\prime}}\lambda^{s}_{\delta,m}\\}\Big{\\}}$
$\displaystyle\bm{x}_{3}=\mathop{\arg\min}_{\bm{x}}\Big{\\{}\sum_{n\in\mathcal{N}}F^{2}_{n}(\bm{x})~{}\text{s.t.}~{}\eqref{eq:c1},\eqref{eq:c2},\eqref{eq:c6},\eqref{eq:c7b},\eqref{eq:c8b},$
$\displaystyle\\{\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in
C}p_{n,c}\eta^{u}_{n,c}\lambda_{n}<\sum_{m^{\prime}\in\mathcal{M}}\eta^{s}_{m,m^{\prime}}\lambda^{s}_{\delta,m}\\}\Big{\\}}$

Obviously,

$\sum_{n\in\mathcal{N}}F_{n}(\bm{x}_{1})=\min\\{\sum_{n\in\mathcal{N}}F_{n}(\bm{x}_{2}),\sum_{n\in\mathcal{N}}F_{n}(\bm{x}_{3})\\}.$

Meanwhile, the constraint (4) in sp2 is unchanged as shown in P3-2, in order
to ensure that constraint (4) of P3 is satisfied.

## Appendix J

####  J-1 Problem Transform

First, $\bm{\lambda}^{s}$ can be obtained by
$\lambda^{s}_{\delta,m}=\sum_{n\in\mathcal{N}^{\delta}_{m}}\sum_{c\in\mathcal{C}}p_{n,c}\lambda_{n,c}$
according to system model. With given $\bm{\lambda}^{s}$, transforming the
problem from P3-2 to 3-5, a similar proof is already discussed in Proposition
1. $\theta^{*}_{n}$ is achieved if and only if

$\displaystyle\mathop{\min}_{\\{\bm{z}_{n,m}\\}}\\{\pi^{u}_{n,m}(\bm{z}_{n,m})-\vartheta^{*}_{n,m}\pi^{l}_{n,m}(\bm{z}_{n,m})\\}$
$\displaystyle=\pi^{u}_{n,m}(\bm{z}^{*}_{n,m})-\vartheta^{*}_{n,m}\pi^{l}_{n,m}(\bm{z}^{*}_{n,m})=0.$
(124)

This is a necessary and sufficient condition.

We can also use Algorithm 1 (NFPA) to transform this problem with a slight
modification.

####  J-2 Problem Solving

Problems P3–5 are challenging to solve since they are still non-convex, but it
is simple to identify that they are cubic function problems with a finite
range of independent variables taking values. Alternatively put, this is a
Lipschitz smooth function with constant $\ell_{n,m}$ satisfying

$\ell_{n,m}I\succeq\nabla^{2}\big{(}\pi^{u}_{n,m}(\bm{z}_{n,m})-\vartheta^{*}_{n,m}\pi^{l}_{n,m}(\bm{z}_{n,m})\big{)},$
(125)

which is like $g^{p}_{n}$ in Proposition 2.

As a result, we can likewise efficiently handle $\\{\bm{z}_{n,m}\\}$ using
Algorithm 2 with a few slight adjustments.

####  J-3 Convergence Analysis

A similar instead of the same result of Convergence Analysis can be obtained
by Theorem 2. If $\rho_{n}>2\ell_{n}$, Algorithm 2 converge to an
$\epsilon^{ac}$-stationary point within
$O(1/(p^{\mathit{sysn}}\epsilon^{\mathit{ac}}))$. However, in a network with
wired communication, the reliability rate of synchronous iterative
communication is $p^{\mathit{sysn}}=1$ Thus, we derive the NAC algorithm
converges within $O(1/\epsilon^{ac})inthiscase$.

##  Appendix K A Proof of Theorem 4

First, we see the equivalent optimal solution of the migration
$\hat{\bm{y}^{*}}$ from Theorem 3. Hence, we have these two inequalities as

$\displaystyle\begin{split}&\frac{1}{N}\sum_{n\in\mathcal{N}}F_{n}(\bm{x}^{t},\hat{\bm{y}^{*}},\bm{z}^{t})\\\
\mathop{=}^{(a)}&\frac{1}{N}\sum_{n\in\mathcal{N}}F^{1}_{n}(\bm{x}^{t},\bm{z}^{t})\\\
\mathop{=}^{(b)}&\frac{1}{N}\sum_{n\in\mathcal{N}}(F^{2}_{n}(\bm{x}^{t})+F^{3}_{n}(\bm{z}^{t},\bm{\lambda}^{s,t}))\\\
\mathop{\geq}^{(c)}&\frac{1}{N}\sum_{n\in\mathcal{N}}(F^{2}_{n}(\bm{x}^{t+1})+F^{3}_{n}(\bm{z}^{t},\bm{\lambda}^{s,t}))\\\
\mathop{\geq}^{(d)}&\frac{1}{N}\sum_{n\in\mathcal{N}}(F^{2}_{n}(\bm{x}^{t+1})+F^{3}_{n}(\bm{z}^{t},\bm{\lambda}^{s,t+1}))\\\
\mathop{\geq}^{(e)}&\frac{1}{N}\sum_{n\in\mathcal{N}}(F^{2}_{n}(\bm{x}^{t+1})+F^{3}_{n}(\bm{z}^{t+1},\bm{\lambda}^{s,t+1}))\\\
\mathop{=}^{(f)}&\frac{1}{N}\sum_{n\in\mathcal{N}}F^{1}_{n}(\bm{x}^{t+1},\bm{z}^{t+1})\\\
\mathop{=}^{(g)}&\frac{1}{N}\sum_{n\in\mathcal{N}}F_{n}(\bm{x}^{t+1},\hat{\bm{y}^{*}},\bm{z}^{t+1}).\end{split}$
(126)

where (a) and (g) hold according to (117), (b) and (f) hold according to Lemma
2, (c) holds according to Lemma 3, (e) holds according to Lemma 4 and the
convergence of the NAC algorithm, (d) holds and the reason is as follows.
According to (48), we obtain

$\lambda^{s,t}_{\delta,m}\geq\lambda^{s,t+1}_{\delta,m},\quad,\forall\delta\in\Delta,\forall
m\in\mathcal{M}.$ (127)

In addition, it is easy to get that

$\frac{\partial
F^{3}_{n}(\bm{z}^{t},\bm{\lambda}^{s,t})}{\partial\lambda^{s,t}_{\delta,m}}>0,\quad,\forall\delta\in\Delta,\forall
m\in\mathcal{M},$ (128)

in the domain of the definition of $\bm{\lambda}^{s}$. Thus, we have
$F^{3}_{n}(\bm{z}^{t},\bm{\lambda}^{s,t})\geq
F^{3}_{n}(\bm{z}^{t},\bm{\lambda}^{s,t+1})$.

Based on the inequalities, we obtain

$\displaystyle\frac{1}{N}\sum_{n\in\mathcal{N}}F_{n}(\bm{x}^{t},\hat{\bm{y}^{*}},\bm{z}^{t})\geq\frac{1}{N}\sum_{n\in\mathcal{N}}F_{n}(\bm{x}^{t+1},\hat{\bm{y}^{*}},\bm{z}^{t+1})$
(129)

$F_{n}(\bm{x},\bm{y},\bm{z})$ is a function with positive values and a lower
bound. Therefore, $F_{n}(\bm{x},\bm{y},\bm{z})$ monotonically decreases and
converges to a unique point.

##  Appendix L Why Multi-Class

For highest-class priority user $n^{*}$, we have

$\displaystyle\mathbb{E}[A_{n^{*}}]-\mathbb{E}[A^{p}_{n^{*}}]$
$\displaystyle=$
$\displaystyle(\mathbb{E}[T_{n^{*}}]+\mathbb{E}[I_{n^{*}}]+\mathbb{E}[W_{n^{*}}]+\mathbb{E}[Y_{n^{*}}])$
$\displaystyle-(\mathbb{E}[T^{p}_{n^{*}}]+\mathbb{E}[I^{p}_{n^{*}}]+\mathbb{E}[W^{p}_{n^{*}}]+\mathbb{E}[Y^{p}_{n^{*}}])$
$\displaystyle\mathop{=}^{(a)}$
$\displaystyle\mathbb{E}[W_{n^{*}}]-\mathbb{E}[W^{p}_{n^{*}}]$
$\displaystyle=$
$\displaystyle\Upsilon(\bm{\eta}^{u})\frac{\zeta_{\Delta}(\bm{\eta}^{u})-\zeta_{\delta(n^{*})}(\bm{\eta}^{u})}{(1-\zeta_{\Delta}(\bm{\eta}^{u}))(1-\zeta_{\delta(n^{*})}(\bm{\eta}^{u}))}$
$\displaystyle\mathop{\geq}^{(b)}$ $\displaystyle 0.$ (130)

where