#
Optimal Task Offloading Policy in Edge Computing Systems with Firm Deadlines

Khai Doan1, Wesley Araujo1, Evangelos Kranakis2, Ioannis Lambadaris1, Yannis
Viniotis3

Email: {khaidoan@sce  1Carleton University, Department of Systems and Computer
Engineering, Ottawa, ON, Canada.  2Carleton University, School of Computer
Science, Ottawa, ON, Canada.  3North Carolina State University, Department of
Electrical and Computer Engineering, Raleigh, NC, USA.  wesleyaraujo@cmail
kranakis@scs  <EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The recent drastic increase in mobile data traffic has pushed the mobile edge
computing systems to the limit of their capacity. A promising solution is the
task migration to remote servers. Key factors to be considered in the design
of offloading schemes must include the number of tasks waiting in the system
as well as their corresponding deadlines. An appropriate system cost which is
used as an objective function to be minimized comprises two parts. First, an
offloading cost which can be interpreted as the cost of using computational
resources at the external server. Second, a penalty cost due to potential task
expiration. In order to minimize the expected (time average) cost over a time
horizon, we formulate a Dynamic Programming (DP) equation and analyze it to
describe properties of a candidate optimal offloading policy. The DP equation
suffers from the well-known “Curse of Dimensionality” that makes computations
intractable, especially when the state space is infinite. In order to reduce
the computational burden, we identify three important properties of the
optimal policy. Based on these properties, we show that it suffices to
evaluate the DP equation on a finite subset of the state space only. We then
show that the optimal task offloading decision associated with a state can be
inferred from the decision taken at its “adjacent” states, further reducing
the computational load. Finally, we provide numerical results to evaluate the
influence of different parameters on the system performance as well as verify
the theoretical results.

##  I Introduction

Mobile-Edge Computing (MEC) and Mobile Cloud Computing (MCC) are important
paradigms in addressing the limited computational capability of mobile
devices. In MEC, a remote server is placed physically near the device for
computational tasks to be offloaded to the MEC-server for remote computation.
MEC is similar to MCC, however the server in the latter case, is not
necessarily physically close to the device. MEC is more appropriate if the
network latency or network congestion is a problem. In general, there are two
scenarios when MEC is most appropriate: when the application has real-time
constraints or when the user/wireless device has limited resources such as
memory, storage, CPU, etc. Surveys on MEC and MCC can be found in [1] and in
[2], respectively.

###  I-A Motivation and Related Works

Exploiting the advantage of offloading systems, computational services
requested by users can be either processed at local servers (e.g., MEC) or
offloaded onto remote servers (e.g., MCC) that have more computational
capability. This feature not only improves users’ quality of experience by
reducing the processing, latency and power consumption, but also allows
different types of applications and services to be deployed on devices with
low computational capability. Due to significant advances in practical
applications, analyzing MEC and MCC systems has been attracting a lot of
attention in the research literature. For example, [3] proposed an optimal
task offloading algorithm by maximizing an appropriate utility function. Such
a function increases with users’ satisfaction characterized by tasks processed
remotely, and decreases with respect to the total amount of computation and
energy consumption overhead. In [4], the authors study the computational
complexity of task offloading policies in a MCC context where tasks have hard
deadlines. In [5], they study the problem of computational offloading in a MCC
context with the goal of minimizing energy consumption of the user device by
taking into account its multi-core architecture.

In practical systems, the task offloading feature may suffer from uncertainty
due to certain factors such as network congestion and limited computational
resources of remote servers. Such factors may impose randomness in the
availability of task migration. Systems that have firm task deadlines require
more attention when task migration is not always available. These issues have
not been adequately addressed in existing works which typically assume that
task offloading can always be controlled. In [6], the authors study the
problem of offloading tasks to a cloud computing infrastructure aiming at
minimizing the energy consumption of the offloading device and meeting the
task deadlines. In [7], the authors consider computational offloading in a
real-time MEC setting in which tasks have hard deadlines. In [8], the authors
study the problem of computational offloading in the context of a mixed MEC
and MCC system with the goal of minimizing the weighted cost of task
processing delay and energy consumption of the devices.

Furthermore, despite several offloading algorithms proposing improvements for
the system performance under different contexts, to the best of our knowledge,
there is a lack of studies for the the characterization of the optimal policy
for task offloading to enhance the system performance. In [9, 10], the authors
consider the problem of a user offloading tasks to multiple moving edge
devices so as to maximize the utility of the task execution and minimize the
energy consumption. In the first paper, a Deep Reinforcement Learning based
method is used to solve the problem, while in the second paper, Q-learning is
used.

###  I-B Model Novelty and Main Contributions

What differentiates our model from previous studies is the combination of: (a)
the randomness in the connection between both the remote server and local
device, (b) tasks that have firm deadlines, and, (c) the formulation of the
problem in the context of an optimal stochastic control (DP) framework. As is
well-known in DP formulations, computing the solution of the DP equation may
become computationally prohibitive (also known as the “dimensionality curse”
of DP). With this motivation, our contributions can be summarized as follows.

  * •

Our main contribution is the mathematical characterization of the structure of
the optimal policy. The findings are presented in Theorems 1 and 2. The
properties we prove in these theorems help reduce the computational burden
associated with the DP equation.

  * •

Our second contribution is a further reduction in the computational effort for
determining the minimum expected (time average) cost. In Proposition 1 we
derive a mathematical property of this cost. This will enable us to compute it
by applying the computationally heavy DP equation to only a finite number of
states (the so-called lean states); the cost for an arbitrary state can then
be calculated via a much simpler algebraic computation.

The rest of this article is organized as follows. In the next section, we
describe the system model under consideration. In Section III, we formulate
the DP equation to minimize the expected (time average) cost. In Section IV,
we introduce the notions of reduced and lean state space and show how they are
used to reduce the computational load for the calculation of the optimal cost
of our model. Next, we study properties of the optimal policy and the minimum
expected time-average (ETA) cost in Section V. The optimal policy is
explicitly presented in Section VI. Subsequently, we illustrate numerical
results in Section VII. We conclude our work with Section VIII. Finally, we
provide proofs for all the theorems, lemmas, and propositions in Appendices
presented in Sections IX, X, and XI, respectively.

##  II System Model

Figure 1: System model.

The system we consider is depicted in Fig. 1; it consists of a base station
(BS) operating in discrete-time over $T$ time slots. Tasks sent by users in
the area will be buffered at the BS. We assume that the maximum deadline for
any task is $N$, a fixed positive integer. The deadline represents the number
of time slots (including the current one) within which the tasks need to be
processed, otherwise they will expire and result in a penalty $C_{p}$ per
expired task.

We define the system state vector at a given time slot $t$ by

$\displaystyle\mathbf{s}_{t}=\left(n_{1}^{(t)},n_{2}^{(t)},\ldots,n_{N}^{(t)}\right),t\in\left\\{0,1,\ldots,T-1\right\\}$
(1)

where $n_{i}^{(t)}\in\mathds{Z}_{+}$ represents the number of tasks having
deadline $i=1,2,\ldots,N$, buffered at the BS at time slot $t$. The state
space for this system is $\mathds{Z}_{+}^{N}$, which is an $N$-dimensional
infinite state space. In this system, a number of different events takes place
and triggers the system to transit to a different state in the next time slot.
Those events can be listed in order as follows.

  1. 1.

Connection to a remote server: A task offloading service is provided by an
external server that is outside the communication distance of the BS. The
server is accessible by means of an autonomous mobile agent (AMA). The AMA
randomly arrives in the area and behaves as an intermediate node to connect
the BS and the server. With the AMA, the BS can offload tasks to the server at
cost $C_{o}>0$ per task. Let $p_{u}$ be the probability that the AMA arrives
in each time slot. The remote server is assumed to be capable of processing
all tasks instantly without delay. In addition, we also assume that the task
transferring from the BS to the AMA, and then, to the remote server incurs no
delay.

  2. 2.

The deadline shifting: The deadlines of all tasks are reduced by one when
transitioning from a time slot to the next. The deadlines are strict: a
penalty of $C_{p}$ is incurred for every task whose deadline has dropped to 0.
In this model, we assume that $C_{p}>C_{o}$.

  3. 3.

The arrival of a new task: During our system operation, there will be new
tasks sent by users; we assume at most one new task can arrive per time slot.
We use $p_{i}$ to denote the probability that a new task will have deadline
$i$; $p_{0}$ denotes the probability of no task arrival. Thus, the task
arrival probability vector is given by
$\mathbf{p}=\left(p_{0},p_{1},p_{2},\ldots,p_{N}\right).$ We will assume that
task arrivals in different time slots are independent.

  4. 4.

The local processing service: We assume that the BS has limited computational
capability. Therefore, the local processing service provided by the BS is
assumed to be available at random with probability $\mu$ in each time slot.
When it is available, at most one task can be processed per slot.

The sequence of the above events for our model is illustrated in Fig. 2. The
randomness in local processing and in the appearance of the AMA accounts for
the uncertainty in the task processing.

The system cost is described by the offloading and task expiration penalty
costs. To be more specific, assume that state $\mathbf{s}_{t}$ (as defined in
Eq. (1)) is encountered at time slot $t$. By $L_{t}$ we denote the number of
tasks that are offloaded when the system is in state $\mathbf{s}_{t}$. $L_{t}$
is also called the offloading decision; determining its optimal value (to be
defined shortly) is the subject of this work. $L_{t}$ can take values in the
set

$\displaystyle\mathbb{L}\left(\mathbf{s}_{t}\right)=\left\\{0,1,2,\ldots,\sum_{i=1}^{N}n_{i}^{(t)}\right\\}.$
(2)

In our model, all tasks share the same offloading cost $C_{o}$, and result in
the same penalty $C_{p}$ when expire. Trivially, it is optimal to locally
process and offload tasks with the most imminent deadlines first. In this
work, when the AMA is available and $L\geq 1$ tasks are defined to be
offloaded, we offload $L$ tasks with the smallest deadlines. Whenever the
local processing is available, we process the task with the smallest deadline.
The proof for this optimality property is presented in Lemma 2.

Based on the strategy introduced above, given state $\mathbf{s}_{t}$ and the
offloading decision $L_{t}$, we define
$\mathcal{C}\left(\mathbf{s}_{t},L_{t}\right)$, the expected instantaneous
cost incurred at time slot $t$ by:

$\displaystyle\mathcal{C}\left(\mathbf{s}_{t},L_{t}\right)=p_{u}\mathcal{C}^{\text{A}}\left(\mathbf{s}_{t},L_{t}\right)+\left(1-p_{u}\right)\mathcal{C}^{\overline{\text{A}}}\left(\mathbf{s}_{t}\right)$
(3)

in which

$\displaystyle\mathcal{C}^{\text{A}}\left(\mathbf{s}_{t},L_{t}\right)=C_{o}L_{t}+C_{p}\max\left(n_{1}^{(t)}-L_{t},0\right)$
(4)

is the instantaneous cost when the AMA arrives and $L_{t}$ tasks are
offloaded. Similarly,

$\displaystyle\mathcal{C}^{\overline{\text{A}}}=C_{p}n_{1}^{(t)}$ (5)

is the cost when AMA is not available, thus, does not depend on the offloading
decision $L_{t}$.

For a given time horizon $T$, an offloading policy $\pi$ is a rule that
determines the offloading parameter $L_{t}$ for every state $\mathbf{s}_{t}$
at $t$, i.e., $L_{t}=\pi(\mathbf{s}_{t})$.

$\mathbf{s}_{t}$$\mathbf{s}_{t+1}$time slot$t$$t+1$ (Offloading Cost) AMA &
Offloading (Penalty Cost) Deadline Shifting Task ArrivalLocal Processing
Figure 2: Events taking place in a time slot.

##  III Dynamic Programming Formulation

Consider the expected time-average cost given by

$\frac{1}{T}\sum_{t=0}^{T-1}\mathds{E}[\mathcal{C}\left(\mathbf{s}_{t},L_{t}\right)].$
(6)

For the rest of this work, we will refer to the cost defined above as the
average cost. We wish to determine the optimal offloading policy that
minimizes the above average cost for a given time horizon.

Consider a state $\mathbf{s}$, in which the decision is to offload $L$ tasks.
Suppose a new task arrives with a deadline $k$. If local processing is
available, the system will transit to a new state $\mathbf{s}^{\prime}_{Lk}$;
if not, the new state will be $\mathbf{s}^{\prime\prime}_{Lk}$. These state
definitions facilitate the analysis of the Dynamic Programming equation that
will follow. They are formally defined in Eqs. (13) in this section. We need
to introduce some additional, detailed notation to that effect.

Before doing this, we provide an example, let $\mathbf{s}=(0,1,2,0,1)$, the
next event according to Fig. 2 is offloading, the AMA is available and $L=2$
tasks with the most imminent deadlines are to be offloaded, therefore the
intermediate state is $(0,0,1,0,1)$. The next event is deadline shifting to
account for the new deadlines of the tasks in the next time slot, resulting in
$(0,1,0,1,0)$. Following Fig. 2, we assume a new task with deadline 3 arrives,
resulting in the intermediate state $(0,1,1,1,0)$. The next event is local
processing, which processes the most imminent task, resulting in system state
$\mathbf{s}^{\prime}_{23}=(0,0,1,1,0)$.

Vector $\mathbf{o}\left(\mathbf{s},L\right)=\left(o_{1},\ldots,o_{N}\right)$
represents the task offloading. Let $d^{\prime}$ be the deadline of the most
imminent task after $L$ tasks have been offloaded from $\mathbf{s}$. If
$L<n_{1}$, $d^{\prime}=1$. Otherwise, $d^{\prime}$ satisfies the inequalities

$\displaystyle L\leq\sum_{j=1}^{d^{\prime}}n_{j}\text{ and
}L>\sum_{j=1}^{d^{\prime}-1}n_{j}.$ (7)

Then, $\mathbf{o}\left(\mathbf{s},L\right)$ is defined as follows.

  * •

If $d^{\prime}=1$:

$\displaystyle o_{i}=\begin{cases}L,&\text{ if }i=1,\\\ 0,&\text{ if }i\geq
2.\end{cases}$ (8)

  * •

If $d^{\prime}$ satisfies inequalities (7):

$\displaystyle o_{i}=\begin{cases}n_{i},&\text{ if }i\leq d^{\prime}-1,\\\
L-\sum_{j=1}^{d^{\prime}-1}n_{j},&\text{ if }i=d^{\prime},\\\ 0,&\text{ if
}i\geq d^{\prime}+1.\end{cases}$ (9)

Let $\mathbf{a}_{k}=\left(a_{1},\ldots,a_{N}\right)$ represent the task
arrival vector defined as:

$\displaystyle a_{i}=\begin{cases}1&,\text{ if }i=k,\\\ 0&,\text{ if }i\neq
k.\end{cases}$ (10)

Then, the intermediate state of the system after $L$ most imminent tasks have
been offloaded from $\mathbf{s}$, the deadline shifting has been performed,
and the task arrival event has been realized, can be defined as follows:

$\displaystyle\mathbf{s}^{inte}=f_{ds}\left(\mathbf{s}-\mathbf{o}\left(\mathbf{s},L\right)\right)+\mathbf{a}_{k}$
(11)

where the function $f_{ds}\left(\cdot\right)$ performs deadline shifting on
the given vector. If $\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$,
$f_{ds}\left(\mathbf{s}\right)$ is an $N$-dimensional vector
$\left(n_{2},\ldots,n_{N},0\right)$ in which the component $n_{1}$ is removed,
representing task expiration.

Let $\mathbf{l}=\left(l_{1},\ldots,l_{N}\right)$ represent the local
processing vector. If $\mathbf{s}^{inte}\neq(0,\ldots,0)$, we assume $d$ is
the deadline of the most imminent task in $\mathbf{s}^{inte}$, then elements
of $\mathbf{l}$ is given by:

$\displaystyle l_{i}=\begin{cases}1,&\text{ if }i=d,\\\ 0,&\text{ if }i\neq
d.\end{cases}$ (12)

Otherwise, $\mathbf{l}=(0,\ldots,0)$.

Then the system state transition is defined as:

$\displaystyle\mathbf{s}^{\prime}_{Lk}=\mathbf{s}^{inte}-\mathbf{l},\text{ and
}\mathbf{s}^{\prime\prime}_{Lk}=\mathbf{s}^{inte}.$ (13)

To this end, let $J_{T}\left(\mathbf{s}\right)$ denotes the minimum average
cost over $T$ time slots for a given initial state $\mathbf{s}$. We have the
following Dynamic Programming Equation.

$\displaystyle\begin{split}&J_{T}\left(\mathbf{s}\right)=~{}\underset{L\in\mathbb{L}\left(\mathbf{s}\right)}{\min}~{}\left\\{\mathcal{C}\left(\mathbf{s},L\right)+G_{T-1}\left(\mathbf{s},L\right)\right\\},\end{split}$
(14)

with

$\displaystyle
G_{T}\left(\mathbf{s},L\right)=\begin{cases}p_{u}G_{T}^{{\text{A}}}\left(\mathbf{s},L\right)+\left(1-p_{u}\right)G_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right),&T\geq
1,\\\ 0,&T=0.\end{cases}$ (15)

where

$\displaystyle
G_{T}^{{\text{A}}}\left(\mathbf{s},L\right)=\mu\sum_{k=0}^{N}p_{k}J_{T}\left(\mathbf{s}^{\prime}_{Lk}\right)+\left(1-\mu\right)\sum_{k=0}^{N}p_{k}J_{T}\left(\mathbf{s}^{\prime\prime}_{Lk}\right)$
(16)

is the average future cost given that the AMA arrives at the current time slot
and $L$ tasks are offloaded, and

$\displaystyle
G_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)=\mu\sum_{k=0}^{N}p_{k}J_{T}\left(\mathbf{s}^{\prime}_{0k}\right)+\left(1-\mu\right)\sum_{k=0}^{N}p_{k}J_{T}\left(\mathbf{s}^{\prime}_{0k}\right)$
(17)

is that without the AMA, and hence, does not depend on $L$.

Eq. (14) is equivalent to

$\displaystyle
J_{T+1}\left(\mathbf{s}\right)=p_{u}J_{T+1}^{\text{A}}\left(\mathbf{s}\right)+\left(1-p_{u}\right)J_{T+1}^{\overline{\text{A}}}\left(\mathbf{s}\right)$
(18)

in which

$\displaystyle
J_{T+1}^{\text{A}}\left(\mathbf{s}\right)=\underset{L\in\mathbb{L}\left(\mathbf{s}\right)}{\min}\left\\{\mathcal{C}^{\text{A}}\left(\mathbf{s},L\right)+G_{T}^{\text{A}}\left(\mathbf{s},L\right)\right\\}$
(19)

and

$\displaystyle
J_{T+1}^{\overline{\text{A}}}\left(\mathbf{s}\right)=\mathcal{C}^{\overline{\text{A}}}\left(\mathbf{s}\right)+G_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right).$
(20)

To facilitate our analysis in the subsequent sections, we define the minimum
average cost attained by offloading exactly $L$ most imminent tasks from an
initial state $\mathbf{s}$ given the AMA’s presence by

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s},L\right)=\mathcal{C}^{\text{A}}\left(\mathbf{s},L\right)+G_{T}^{\text{A}}\left(\mathbf{s},L\right).$
(21)

We denote $\bar{\mathbf{s}}_{dL}$ the state obtained by offloading, from
$\mathbf{s}$, $L$ most imminent tasks having deadline greater than or equal to
$d$. The following example is to provide more intuition about this notation.

###### Example 1

Given state $\mathbf{s}=\left(0,5,6,7,8\right)$, the state
$\bar{\mathbf{s}}_{37}$ is obtained by offloading 7 most imminent tasks
starting from deadline 3, thus,
$\bar{\mathbf{s}}_{37}=\left(0,5,0,6,8\right)$. Now, if we offload 7 most
imminent tasks starting from deadline 5, the resulted state would be
$\bar{\mathbf{s}}_{57}=\left(0,5,6,7,1\right)$.

We have mentioned in the previous section that whenever offloading is
possible, and $L$ tasks need to be offloaded from a given state $\mathbf{s}$,
it is optimal to offload $L$ most imminent tasks. This offloading behaviour
results in state $\bar{\mathbf{s}}_{1L}$ which is always associated with
$d=1$. However, the properties we studied in Subsection V-B are associated
with a general context where tasks can be offloaded starting from an arbitrary
deadline $d$. Therefore, for consistency, we introduce a general notation
$\bar{\mathbf{s}}_{dL}$ where $d$ is used in the subscript instead of 1.

For the rest of this article, the terms offloading states and non-offloading
states will be used. Therefore, they are specified in the following
definition.

###### Definition 1

For a given state $\mathbf{s}$ and a time horizon $T$, $\mathbf{s}$ is called
an offloading state if the associated optimal offloading decision is a
positive integer. State $\mathbf{s}$ is called a non-offloading state if the
associated optimal offloading decision is 0.

##  IV Computational Load Reduction

###  IV-A Reduced State Space

For a given $N$-dimensional state vector $\mathbf{s}$, since there are at most
$N-1$ tasks that can be processed in $N$ time slots. This is because the
deadline shifting happens at the beginning of every time slot as presented in
Fig 2. Therefore, tasks having deadline 1 cannot be processed. This means that
there might be certain tasks that are guaranteed to expire if not offloaded
within the next $N$ time slots; we will call such tasks excessive tasks. We
define the reduced states as the ones having no excessive tasks.

In the remainder of this sub-section we will provide a characterization and
properties of reduced states. For such a state
$\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$ and from Fig. 2, all tasks having
deadline 1 will expire if not offloaded, hence, we must have $n_{1}=0$. Next,
at most one task can be processed in the next slot, therefore, we must have
$n_{1}+n_{2}\leq 1$. Subsequently, at most two tasks can be processed in the
next two time slots, leading to $n_{1}+n_{2}+n_{3}\leq 2$, otherwise at least
one task will expire after two slots, and so on. Finally, at most $N-1$ tasks
can be processed in $N$ time slots including the current one, so we must have
$\sum_{i=1}^{N}n_{i}\leq N-1$. The definition for a reduced states follows.

###### Definition 2

A state $\mathbf{s}_{r}=\left(n^{r}_{1},\ldots,n^{r}_{N}\right)$ is a reduced
state if and only if the following inequalities hold:

$\displaystyle\sum_{i=1}^{m}n_{i}^{r}\leq m-1,m=1,2,\ldots,N.$ (22)

As elements of a reduced state vector is bounded, the number of reduced
vectors is finite. Moreover, the next lemma states that the number of reduced
state vectors is equal to the Catalan number [11].

###### Lemma 1

The number of reduced states having dimension $N$ is finite and equals to the
Catalan number $C_{N}=\binom{2N}{N}/(N+1)$.

Proof: Please see Appendix X-A.

Abusing the notation slightly, for the sake of simplicity, we can associate a
corresponding reduced state
$\mathbf{s}_{r}=\left(n^{r}_{1},\ldots,n^{r}_{N}\right)$ for any given state
$\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$, in the infinite state space,
using Algorithm 1. For $\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$, it can be
seen from Eq. (14) and Eqs. (3)-(5) that $n_{i},i\geq 2$ do not contribute to
the cost $J_{1}\left(\mathbf{s}\right)$. Similarly, $n_{i},i\geq 3$ do not
contribute to the cost $J_{2}\left(\mathbf{s}\right)$. Observe, therefore that
in general, tasks having deadline greater than the considered time horizon
will not contribute to the cost in Eq. (14). Therefore, these tasks will not
be considered, which is reflected by line 4 of this algorithm.

Algorithm 1 Derivation of Reduced States

1:Input: $\mathbf{s}=\left(n_{1},n_{2},\ldots,n_{N}\right)$, $N$, $T$.

2:Output: $\mathbf{s}_{r}$, $L_{g}$.

3:Initialize: $t_{\text{idle}}\leftarrow 0$, $L_{g}\leftarrow 0$,
$\tilde{s}\leftarrow\left(\tilde{n}_{1},\ldots,\tilde{n}_{N}\right)$ where
$\tilde{n}_{i}\leftarrow n_{i},i\leq T$, and $\tilde{n}_{i}\leftarrow 0,i>T$.

4:$n_{i}\leftarrow 0$, for $i>\min\left(N,T\right).$

5:for $i=1,2,\ldots,N$ do

6: for $j=1,2,\ldots,\min\left(N,T\right)$ do

7:
$a\leftarrow\sum_{d=1}^{j}\tilde{n}_{d}-\max\left(n_{i}-i+t_{\text{idle}}+1,0\right)$.

8: if $a\geq 0$ then

9: if $j\geq 2$ then

10: $\tilde{n}_{d}\leftarrow 0,d=1,\ldots,j-1$.

11: $\tilde{n}_{j}\leftarrow\tilde{n}_{j}-a$.

12: $L_{g}\leftarrow L_{g}+\max\left(n_{i}-i+t_{\text{idle}}+1,0\right)$.

13: $t_{\text{idle}}\leftarrow\sum_{d=1}^{i}\tilde{n}_{d}$.

14:$\mathbf{s}_{r}\leftarrow$ Offloading $L_{g}$ most imminent tasks from
$\mathbf{s}$.

15:return $\mathbf{s}_{r}$, $L_{g}$.

Determining the reduced states is the first step in reducing the computational
burden of the DP equation (14). The next step is the determination of a new
concept know as the lean states, which also constitute a finite set and are
directly used to compute the optimal cost $J_{T}\left(\mathbf{s}\right)$
according to the forthcoming Proposition 1.

###  IV-B Lean State Space

The definition of lean states is given as below:

###### Definition 3

For a given state $\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$, we call
$\mathbf{s}_{r}=\left(n_{1}^{r},\ldots,n_{N}^{r}\right)$ a reduced state
obtained from $\mathbf{s}$ following Algorithm 1. We define the parameters
$\gamma_{j},j=1,\ldots,N$ as follows:

$\displaystyle\gamma_{j}=\begin{cases}0&,\text{ if }j=1\text{ or
}j>\min\left(N,T\right),\\\
\min\left\\{n_{j},j-1-\sum_{i=1}^{j-1}\gamma_{i}\right\\}&,\text{
otherwise}.\end{cases}$ (23)

Then, the lean state
$\mathbf{s}_{\text{m}}=\left(n_{1}^{m},\ldots,n_{N}^{m}\right)$ corresponding
to $\mathbf{s}$ is given by

$\displaystyle
n^{\textit{m}}_{i}=\max\\{\gamma_{i},n^{\textit{r}}_{i}\\},~{}i=1,2,\ldots,N.$
(24)

The relation in the minimum average cost of a given state $\mathbf{s}$ and
that of its corresponding lean state is presented in Proposition 1.

###### Proposition 1

Given state $\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$ and its lean state
$\mathbf{s}_{m}=\left(n_{1}^{m},\ldots,n_{N}^{m}\right)$. Let $P_{t}$ be the
probability that the AMA is available for the first time at time slot $t$.
Then, the following equality holds.

$J_{T}\left(\mathbf{s}\right)=J_{T}\left(\mathbf{s}_{m}\right)+C_{g2m}$ (25)

where

$C_{g2m}=C_{o}\sum_{i=1}^{N}\left(n_{i}-n_{i}^{m}\right)\sum_{j=0}^{i-1}P_{t=j}+C_{p}\sum_{i=1}^{N-1}P_{t=i}\sum_{j=1}^{i}\left(n_{j}-n_{j}^{m}\right)+C_{p}P_{t\geq
N}\sum_{j=1}^{N}\left(n_{j}-n_{j}^{m}\right)$

with the probabilities $P_{t=j}$ and $P_{t\geq N}$ are computed by

$\displaystyle P_{t=j}$ $\displaystyle=p_{u}\left(1-p_{u}\right)^{j},$
$\displaystyle P_{t\geq N}$ $\displaystyle=\left(1-p_{u}\right)^{N}.$

Proof: Please see Appendix XI-A.

As the lean state space is finite, if $J_{T}\left(\mathbf{s}_{m}\right)$ is
computed for all lean states via the DP equation (14),
$J_{T}\left(\mathbf{s}\right)$ can be computed for every $\mathbf{s}$ via the
simple algebraic manipulation of equation (25).

##  V Properties of Optimal Policy and Cost Function

###  V-A Optimality of the Most-Imminent Offloading Method

The first property of an optimal offloading policy is offloading the most
imminent tasks first. This property will be proved based on another property
presented in the next proposition.

###### Proposition 2

Given state
$\mathbf{s}=\left(n_{1},n_{2},\ldots,n_{N}\right)\not\equiv\left(0,\ldots,0\right)$.
Assuming that $d$ is the deadline of the most imminent task of $\mathbf{s}$,
we define the set $\mathbb{S}_{pp}\left(\mathbf{s}\right)$ as follows. If
$\tilde{\mathbf{s}}=\left(\tilde{n}_{1},\ldots,\tilde{n}_{N}\right)\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$,
state $\tilde{\mathbf{s}}$ satisfies the following conditions:

  * •

If $N=1$: $\tilde{\mathbf{s}}\equiv\mathbf{s}$.

  * •

If $N\geq 2$: either $\tilde{\mathbf{s}}\equiv\mathbf{s}$, or
$\tilde{\mathbf{s}}$ is defined by

$\displaystyle\tilde{n}_{i}=\begin{cases}n_{d}-1,&\text{ if }i=d,\\\
n_{j}+1,&\text{ if }i=\tilde{d}\text{ for a deadline
}\tilde{d}\in\left\\{d+1,\ldots,N\right\\},\\\ n_{i},&\text{
otherwise.}\end{cases}$ (26)

Then, the following inequality holds:

$\displaystyle J_{T}\left(\mathbf{s}\right)\geq
J_{T}\left(\tilde{\mathbf{s}}\right),\text{ for all
}T,\mathbf{s},\tilde{\mathbf{s}}\in\mathbb{S}_{pp}\left(\mathbf{s}\right).$
(27)

Proof: Please see Appendix XI-B.

As a result of Proposition 2, the first property of the optimal policy can be
proved, and formally presented in Lemma 2.

###### Lemma 2

When processing is possible, it is optimal to process the most imminent task.
When it is optimal to offload $L$ tasks, the $L$ most imminent tasks should be
offloaded.

Proof: Please see Appendix X-B.

###  V-B Convexity of the Minimum average cost with respect to the Offloading
Decision

For a given time horizon $T$, and an initial state
$\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$, we define the following function

$\displaystyle
F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)=J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{dL}\right)+LC_{o},$
(28)

in which we recall that $\bar{\mathbf{s}}_{dL}$ is the state obtained by
offloading, from $\mathbf{s}$, $L$ most imminent tasks having deadline greater
than or equal to $d$. Function
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ is characterized by
parameters $T,\mathbf{s}$, and $d$. This function takes $L$ as variable. We
define the domains of $F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$
as follows.

$\displaystyle\mathbb{L}_{1}\left(\mathbf{s}\right)$
$\displaystyle=\left\\{n_{1},\ldots,\sum_{i=1}^{N}n_{i}\right\\},$ (29)
$\displaystyle\mathbb{L}_{d}\left(\mathbf{s}\right)$
$\displaystyle=\left\\{0,1,\ldots,\sum_{i=d}^{N}n_{d}\right\\},\text{ for
}d=2,\ldots,N.$ (30)

$\mathbb{L}_{d}\left(\mathbf{s}\right)$ can be interpreted as the set of valid
offloading decisions associated with state $\mathbf{s}$ and deadline $d$. In
the definition of $\mathbb{L}_{1}\left(\mathbf{s}\right)$, because all tasks
having deadline 1 are excessive tasks and must be offloaded, the optimal
offloading decision must be conveyed in the set
$\left\\{n_{1},\ldots,\sum_{i=1}^{N}n_{i}\right\\}$. Hence, $L<n_{1}$ can be
removed from the domains of
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ when $d=1$.

###### Example 2

As an example, let us consider a 3-dimensional state vector
$\mathbf{s}=\left(2,3,4\right)$. In this example, we have

$\displaystyle\mathbb{L}_{1}\left(\mathbf{s}\right)$
$\displaystyle=\left\\{2,3,\ldots,9\right\\},$ (31)
$\displaystyle\mathbb{L}_{2}\left(\mathbf{s}\right)$
$\displaystyle=\left\\{0,1,\ldots,7\right\\},$ (32)
$\displaystyle\mathbb{L}_{3}\left(\mathbf{s}\right)$
$\displaystyle=\left\\{0,1,\ldots,4\right\\}.$ (33)

We have the following convexity property stated in the next lemma.

###### Lemma 3

For every given time horizon $T$, an initial state $\mathbf{s}$, and a
deadline $d$, the function
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ as defined in Eq. (28)
is a discrete convex function with respect to
$L\in\mathbb{L}_{d}\left(\mathbf{s}\right)$ where
$\mathbb{L}_{d}\left(\mathbf{s}\right)$ is defined in Eqs. (29) and (30).

Proof: Please see Appendix X-C.

The next lemma states the relation between function
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ and the optimal
offloading decision associated with state $\mathbf{s}$ and a time horizon $T$.

###### Lemma 4

Assuming that the function
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ attains its minimum at
$L^{*}$ for $d=1$, then, $L^{*}$ is the optimal offloading decision of
$\mathbf{s}$ for a time horizon $T$.

Proof: Please see Appendix X-D.

Other important properties of the optimal offloading decisions will be
presented in the next subsection based on the concept of adjacent states.

###  V-C Adjacent States

The goal of this subsection is introducing the concept of adjacency among
states, and related properties. These properties facilitate the design of the
optimal policy presented later on. The definition of adjacent states is given
below.

###### Definition 4

Consider a state
$\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)\neq\left(0,\ldots,0\right)$, with
$d$ as the smallest deadline such that $n_{d}>0$. Then, state
$\mathbf{s}_{a}=\left(n^{a}_{1},\ldots,n^{a}_{N}\right)$ is an adjacent state
to $\mathbf{s}$ if there exists a deadline $j\in\left\\{1,\ldots,d\right\\}$
such that:

$\displaystyle n_{i}^{a}=\begin{cases}n_{i}+1,&\text{ if }i=j,\\\
n_{i},&\text{ if }i\neq j.\end{cases}$ (34)

If a state $\mathbf{s}_{a}$ has only one task with arbitrary deadline, it is
adjacent to state $\left(0,\ldots,0\right)$.

Let us consider the following two examples.

###### Example 3

In the first example, we assume that a state
$\mathbf{s}=\left(0,0,1,4,4\right)$ is given in which the deadline of the most
imminent task in $\mathbf{s}$ is 3. Therefore, an adjacent state
$\mathbf{s}_{a}$ of $\mathbf{s}$ can be obtained by adding a task with
deadline less than or equal to 3, e.g.,
$\mathbf{s}_{a}=\left(0,1,1,4,4\right)$.

In the second example, assuming that $\mathbf{s}_{a}=\left(0,2,1,3,3\right)$.
A state $\mathbf{s}$ for which $\mathbf{s}_{a}$ is adjacent, can be obtained
by offloading the most imminent task in $\mathbf{s}_{a}$, i.e.,
$\mathbf{s}=\left(0,1,1,3,3\right)$.

We denote by $\mathbb{S}_{adj}\left(\mathbf{s}\right)$ the set of all adjacent
states of $\mathbf{s}$. For a given time horizon, the optimal offloading
decision of $\mathbf{s}$ can be inferred from that of
$\mathbf{s}_{a}\in\mathbb{S}_{adj}\left(\mathbf{s}\right)$ and vice versa, as
described in Theorem 1.

###### Theorem 1

Given two states $\mathbf{s}$,
$\mathbf{s}_{a}\in\mathbb{S}_{adj}\left(\mathbf{s}\right)$, and a time horizon
$T$. We call $L^{*}$ and $L^{*}_{a}$ the optimal offloading decision of
$\mathbf{s}$ and $\mathbf{s}_{a}$, respectively, for the time horizon $T$. We
have the following relations:

  1. 1.

If $L_{a}^{*}\geq 1,L^{*}=L_{a}^{*}-1$.

  2. 2.

If $L_{a}^{*}=0$, $L^{*}=0$.

  3. 3.

If $L^{*}\geq 1$, $L^{*}_{a}=L^{*}+1$.

Proof: Please see Appendix IX-A.

###  V-D Offloading and Non-Offloading Conditions

We have defined the notion of offloading and non-offloading states in
Defnition 1. In this subsection, we mathematically identify the conditions for
a state to be an offloading and non-offloading state for a given time horizon.
This is formally stated in Proposition 3.

###### Proposition 3

Assuming that two states $\mathbf{s}$,
$\mathbf{s}_{a}\in\mathbb{S}_{adj}\left(\mathbf{s}\right)$, and a time horizon
$T$ is given. $\mathbf{s}_{a}$ is a non-offloading state if and only if the
following inequality holds

$\displaystyle
J_{T}\left(\mathbf{s}_{a}\right)-J_{T}\left(\mathbf{s}\right)<C_{o}.$ (35)

Otherwise, $\mathbf{s}_{a}$ is an offloading state.

Proof: Please see Appendix XI-C.

Assume we are given a state $\mathbf{s}$ and a time horizon $T$ with $L^{*}$
as the optimal offloading decision. We recall that $\bar{\mathbf{s}}_{1L}$ is
the state that resulted by removing the first $L$ most imminent tasks from
$\mathbf{s}$. Then, the next property of the optimal offloading policy is
stated as follows.

###### Theorem 2

The optimal offloading decision is the smallest offloading decision $L$ such
that $\bar{\mathbf{s}}_{L}$ is a non-offloading state.

Proof: Please see Appendix IX-B.

##  VI Optimal Offloading Policy

###  VI-A Optimal Policy Description

Given an initial state $\mathbf{s}$ and a time horizon $T$, whenever local
processing is available to process a task, the most imminent task will be
processed. When a AMA is present, the optimal policy consists of two steps.

Step 1. Tasks are offloaded from $\mathbf{s}$ following Algorithm 1 to reach a
reduced state $\mathbf{s}_{r}$. Moreover the value of $L_{g}$, the number of
offloaded tasks is determined.

Step 2. In this step, the DP equation is solved recursively and

$L_{r}={\operatorname*{arg\,min}_{L\in\mathbb{L}\left(\mathbf{s}_{r}\right)}}\left\\{\mathcal{C}\left(\mathbf{s}_{r},L\right)+G_{T-1}\left(\mathbf{s}_{r},L\right)\right\\}$

tasks are offloaded from $\mathbf{s}_{r}$. Note that as described in equation
(25), the recursion involves evaluation of only a finite number states in each
one of the terms $J_{T-1}\left(\cdot\right),J_{T-2}\left(\cdot\right)$ etc.
for any state $\mathbf{s}$. The optimal number of tasks that are offloaded
from $\mathbf{s}$ is $L^{*}=L_{g}+L_{r}$.

The computational load required to solve the recursive DP equation (14) can be
further reduced by the following strategy. Every time the optimal decision
$L_{r}$ associated with a reduced state $\mathbf{s}_{r}$ is computed for a
given $T$, the triplet $\left(\mathbf{s}_{r},L^{*},T\right)$ is saved. This
can be done for all the reduced states, as the number of reduced states is
finite. Then, for every $\mathbf{s}_{r}$ obtained from Step 1 for a given $T$,
the corresponding $L^{*}$ can be retrieved instantly.

By exploiting the properties presented in Theorem 1, the computational burden
can be further reduced as follows. Let us consider a sequence of adjacent
states: $\mathbf{s}_{1},\ldots,\mathbf{s}_{i},\ldots$ in which
$\mathbf{s}_{i+1}\in\mathbb{S}_{adj}\left(\mathbf{s}_{i}\right)$. Assume the
optimal decision of state $\mathbf{s}_{i},i\geq 1$ is known, and denoted by
$L^{*}_{i}$. From Theorem 1, the optimal decisions $L^{*}_{i-u}$ of states
$\mathbf{s}_{i-u},u=1,\ldots,i-1$, can be inferred as follows

$\displaystyle L^{*}_{i-u}$
$\displaystyle=\max\left(L^{*}_{i}-u,0\right),u=1,\ldots,i-1.$ (36)

In the case when $L^{*}_{i}\geq 1$ for state $\mathbf{s}_{i}$, the optimal
decision for states $\mathbf{s}_{i+v},v=1,2,\ldots$ are computed by

$\displaystyle L^{*}_{i+v}$ $\displaystyle=L^{*}_{i}+v,v=1,2\ldots$ (37)

In general, the optimal offloading decisions of all the states
$\mathbf{s}_{i+v}$ and $\mathbf{s}_{i-u}$ mentioned above can be obtained
without relying on the DP equation (14).

In the next section, we provide numerical results to verify the results
presented in this paper thus far.

##  VII Numerical Results

In this section, we present numerical examples that help visualize some of the
properties and equations as well as show the memory savings of the numerical
computations of the DP equation (14) with the aid of Eq. (25) described in
Sec. IV-B. Some of the examples utilize different sets of parameters to
illustrate the performance of the system under different parameter
configurations.

$T$ | $p_{u}$ | $C_{p}$ | $C_{o}$ | $\mu$ | $p_{0}$ | $N$ | $p_{i}\;\forall i\colon 1\leq i\leq N$
---|---|---|---|---|---|---|---
$1,000$ | $0.7$ | $3$ | $1$ | $0.7$ | $0.5$ | $3$ | $1/6$
TABLE I: System Parameters for Section VII-A

###  VII-A Optimal Offloading Decision Visualization

In this example, we illustrate the idea presented in Theorem 2 visually for a
system with the dimension of state vector to be $N=3$, i.e.
$\mathbf{s}=(n_{1},n_{2},n_{3})$. We represent states as coordinates in a 3-D
state space. Then, for $n_{3}=0,1,2,3$, we consider the 2-D slices of this
space and depict them as Figs. 3(a)-3(c) correspondingly. We use the system
parameters described in Table I. The cases when $n_{3}\geq 3$ would result in
similar figures as Fig. 3(c) except that the optimal offloading decision for
each offloading state would increase by $n_{3}-2$. In these figures, red dots
represent offloading states, and black dots represent non-offloading states.
From states with component $n_{2}\geq 1$ in Fig. 3(a), such as
$\left(0,2,0\right)$, $\left(1,2,0\right)$, $\left(1,1,0\right)$,
$\left(2,1,0\right)$, etc., we can reach the non-offloading state
$\left(0,1,0\right)$ with a smaller number of offloaded tasks than state
$\left(0,0,0\right)$. A similar argument applies for states with component
$n_{2}=0$, like $\left(1,0,0\right)$, $\left(2,0,0\right)$, etc., whose
“nearest” non-offloading state is $\left(0,0,0\right)$.

In Fig. 3(b), only the state $\left(0,0,1\right)$ is non-offloading. The
optimal offloading decisions of all the offloading states shown are the
smallest number of most imminent tasks to be offloaded to reach state
$\left(0,0,1\right)$. Fig. 3(c) does not have any non-offloading state. For
example, the optimal offloading decision for the state $\left(0,0,3\right)$ is
1 to reach the non-offloading state $\left(0,0,2\right)$ which is shown in
Fig. 3(b).

(a) $n_{3}=0$

(b) $n_{3}=1$

(c) $n_{3}=2$

Figure 3: Offloading states for varying $n_{3}$ values

###  VII-B Optimal Offloading Decisions for Adjacent States

In Fig. 4(a)-4(c) we visualize the results of equations (36), (37) and Theorem
1. The figures show the optimal offloading decisions marked with a star symbol
in adjacent states. For these examples, all figures have a state size $N=5$
over a time horizon $T=1,000$. Fig. 4(a), 4(b) and 4(c) use the parameters
listed in Tables II, III and IV, respectively. On the vertical axis, we graph
the minimum cost
$\mathcal{C}^{\text{A}}\left(\mathbf{s}_{i},L\right)+G_{T}^{\text{A}}\left(\mathbf{s}_{i},L\right)$
attained by offloading $L$ most imminent tasks from state $\mathbf{s}_{i}$
given that the AMA is available. This is introduced in Eq. (21).

In these three figures, for $i=1,2,3,4$, we consider the states
$\mathbf{s}_{1}=\left(0,0,0,0,1\right)$,
$\mathbf{s}_{2}=\left(0,0,0,0,2\right)$,
$\mathbf{s}_{3}=\left(0,0,1,0,2\right)$, and
$\mathbf{s}_{4}=\left(0,1,1,0,2\right)$. These states are chosen such that
$\mathbf{s}_{i}$ is adjacent to $\mathbf{s}_{i+1},i=1,2,3$. The presented
results indicate that the optimal offloading decision of a state differs from
that of its adjacent state by 1, or both are capped at 0, as Eqs. (36)-(37)
and Theorem 1 suggest. For example, in Fig. 4(a), the optimal decision of
$\mathbf{s}_{4}$ is 2, and that of $\mathbf{s}_{3}$ is 1, hence, the
difference is 1. The same observation applies for the pair $\mathbf{s}_{3}$
and $\mathbf{s}_{2}$. The optimal decision of $\mathbf{s}_{2}$ is 0,
therefore, that of $\mathbf{s}_{1}$ is also 0. Figs 4(b) and 4(c) present the
same properties.

$p_{u}$ | $C_{p}$ | $C_{o}$ | $\mu$ | $p_{0}$ | $p_{i}\;\forall i\colon 1\leq i\leq N$
---|---|---|---|---|---
$0.5$ | $3$ | $1$ | $0.5$ | $0.5$ | $0.1$
TABLE II: System Parameters for Fig. 4(a) $p_{u}$ | $C_{p}$ | $C_{o}$ | $\mu$ | $p_{0}$ | $p_{i}\;\forall i\colon 1\leq i\leq N$
---|---|---|---|---|---
$0.4$ | $4$ | $1$ | $0.3$ | $0.3$ | $0.14$
TABLE III: System Parameters for Fig. 4(b) $p_{u}$ | $C_{p}$ | $C_{o}$ | $\mu$ | $p_{0}$ | $p_{i}\;\forall i\colon 1\leq i\leq N$
---|---|---|---|---|---
$0.7$ | $2$ | $1$ | $0.6$ | $0.6$ | $0.08$
TABLE IV: System Parameters for Fig. 4(c)

(a) Adjacent states using parameters in Table II

(b) Adjacent states using parameters in Table III

(c) Adjacent states using parameters in Table IV

Figure 4: Visual interpretation of Eqs. (36)-(37) and Theorem 1.

###  VII-C Memory Savings Using Equation (25)

In order to numerically compute the DP equation (14), we store the computed
value of $J_{T}(\mathbf{s})$ in memory for a given arbitrary state
$\mathbf{s}$ and time horizon $T$. By using Eq. (25), the size of memory
required is reduced. This is because saving $J_{T}(\cdot)$ values is only
required for lean states $\mathbf{s}_{m}$ where the number of lean states is
smaller than that of “generic” states. Note that these savings are achieved at
the expense of calculating the term $C_{g2m}$ in Eq. (25).

In Fig. 5(a), 5(b), and Fig. 5(c), we show the resulting difference in the
number of $J_{T}(\cdot)$ values saved for 2 cases when $N=5$, $N=4$ and $N=3$,
respectively. Note that different parameters other than the system parameters
$N$ and $T$ will not affect the memory savings. In the first case, Eq. (14) is
used, while in the second case, Eq. (14) is used with the aid of Eq. (25). The
line in blue represents the values saved using only Eq. (14), while the line
in red utilizes both Eqs. (14) and (25).

(a) Memory savings with $N=5$

(b) Memory Saving with $N=4$

(c) Memory Saving with $N=3$

Figure 5: Memory Savings using Eq. (25)

##  VIII Conclusion

In this work, we studied a mobile edge computing system with dynamic user
demand. In the context of an optimal stochastic control framework for serving
user tasks, we considered the following features: tasks with firm deadlines,
their random offloading to a remote server (AMA) or their processing by a
local server (BS) with intermittent service. We considered an expected time-
average cost over a finite time horizon and formulated a Dynamic Programming
problem towards the minimization of this cost. In order to tackle the “Curse
of Dimensionality”, we studied important characteristics of the optimal policy
and reduced the computational load for its calculation. In particular, we
proved that the DP equation can be evaluated for every given state (in the
infinite state space of our model) by considering a specific finite space
called lean state space. Further reduction in the computational load was
achieved by using the concept of “adjacent states”. This allowed us to
evaluate the optimal cost for all such states from knowledge of the cost in
only one state. Finally, based on these properties, we described an optimal
task offloading policy.

##  IX Appendix A: Proofs of Theorems

For a given initial state $\mathbf{s}$, and a time horizon $T$, we recall that
$\bar{\mathbf{s}}_{1L}$ is the state obtained by offloading $L$ most imminent
tasks from state $\mathbf{s}$. Combining this definition with that of
$J_{T}^{\text{A}}\left(\mathbf{s},L\right)$ in Eq. (21), we have the following
relation

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s},L\right)=J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{1L},0\right)+LC_{o},\text{
for }L\in\mathbb{L}\left(\mathbf{s}\right)$ (38)

which can be explained as follows. We note that by offloading $L$ most
imminent tasks from $\mathbf{s}$, we pay a cost $LC_{o}$, and arrive at state
$\bar{\mathbf{s}}_{1L}$. Therefore, if we wish to describe the offloading of
$L$ tasks on the left hand side of Eq. (38), this is equivalent to removing
the $L$ most imminent tasks from state $\mathbf{s}$ to reach state
$\bar{\mathbf{s}}_{1L}$, and offloading 0 task from $\bar{\mathbf{s}}_{1L}$.
Finally, we further add the offloading cost $LC_{o}$ to the overall cost. The
right hand side of Eq. (38) describes this idea.

Since the minimum average cost when offloading no task is the same regardless
of the presence of the AMA’s availability, i.e.,

$\displaystyle
J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{1L},0\right)=J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{1L}\right),\text{
for }L\in\mathbb{L}\left(\mathbf{s}\right),$ (39)

we have

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s},L\right)=J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{1L}\right)+LC_{o},\text{
for }L\in\mathbb{L}\left(\mathbf{s}\right).$ (40)

Furthermore, considering two offloading decisions $L_{1}$ and $L_{2}$ where
$L_{1}+L_{2},L_{1},L_{2}\in\mathbb{L}\left(\mathbf{s}\right)$, we note that
offloading $L_{1}+L_{2}$ tasks from the original state $\mathbf{s}$ would
result in the same state that is obtained by offloading $L_{2}$ tasks from
$\bar{\mathbf{s}}_{1L_{1}}$. An example for this point is as follows:

###### Example 4

Assume $\mathbf{s}=\left(0,1,2,2,3\right),L_{1}=2,L_{2}=3$, then, the
resulting states by offloading $L_{1}+L_{2}=5$ and $L_{1}=2$ tasks from
$\mathbf{s}$, respectively, are

$\displaystyle\bar{\mathbf{s}}_{1\left(L_{1}+L_{2}\right)}=\left(0,0,0,0,3\right),$
(41) $\displaystyle\bar{\mathbf{s}}_{1L_{1}}=\left(0,0,1,2,3\right).$ (42)

Now, offloading $L_{2}=3$ tasks from $\bar{\mathbf{s}}_{1L_{1}}$ would give us
the same state as in Eq. (41).

From Eq. (40), we have

$\displaystyle J^{\text{A}}_{T}\left(\mathbf{s},L_{1}+L_{2}\right)$
$\displaystyle=J^{\overline{\text{A}}}_{T}\left(\bar{\mathbf{s}}_{1\left(L_{1}+L_{2}\right)}\right)+\left(L_{1}+L_{2}\right)C_{o},$
(43) $\displaystyle
J^{\text{A}}_{T}\left(\bar{\mathbf{s}}_{1L_{1}},L_{2}\right)$
$\displaystyle=J^{\overline{\text{A}}}_{T}\left(\bar{\mathbf{s}}_{1\left(L_{1}+L_{2}\right)}\right)+L_{2}C_{o}.$
(44)

The above two expressions result in the following one:

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s},L_{1}+L_{2}\right)=J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{1L_{1}},L_{2}\right)+L_{1}C_{o}.$
(45)

###  IX-A Proof of Theorem 1

From Lemma 3, we have that function
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ is discrete convex with
respect to $L$ for every given $T$, $d$, and
$\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$. Let us consider the case when
$d=1$, and we call $L^{*}\in\mathbb{L}_{1}\left(\mathbf{s}\right)$ the value
at which $F^{\overline{\text{A}}}\left(T,\mathbf{s},1,L\right)$ attains its
minimum. From Lemma 4, $L^{*}$ is also the optimal offloading decision for
$\mathbf{s}$. Hence,

$\displaystyle J_{T}^{\text{A}}\left(\mathbf{s},L\right)\geq
J_{T}^{\text{A}}\left(\mathbf{s},L^{*}\right),\text{ for all
}L\in\mathbb{L}_{1}\left(\mathbf{s}\right),$ (46)

Let us consider the following cases:

  * •

If $L^{*}\geq 1$ which means that
$\mathbf{s}\not\equiv\left(0,\ldots,0\right)$, the set of inequalities (46)
can be re-written as

$\displaystyle J_{T}^{\text{A}}\left(\mathbf{s},1+L-1\right)\geq
J_{T}^{\text{A}}\left(\mathbf{s},1+L^{*}-1\right),\text{ for all
}L\in\mathbb{L}_{1}\left(\mathbf{s}\right)\backslash\left\\{0\right\\}.$ (47)

Applying Eq. (45) with $L_{1}=1$, $L_{2}=L-1$ to the left-hand side of Ineqs.
(47), and with $L_{2}=L^{*}-1$ to the right-hand side of Ineqs. (47), we have

$\displaystyle J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},L-1\right)\geq
J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},L^{*}-1\right),\text{ for all
}L,L^{*}\in\mathbb{L}_{1}\left(\mathbf{s}\right)\backslash\left\\{0\right\\},$
(48)

in which we recall that $\bar{\mathbf{s}}_{11}$ is obtained by offloading the
most imminent task from $\mathbf{s}$, thus,
$\mathbf{s}\in\mathbb{S}_{adj}\left(\bar{\mathbf{s}}_{11}\right)$.

Since
$L,L^{*}\in\mathbb{L}_{1}\left(\mathbf{s}\right)\backslash\left\\{0\right\\}$,
we have $L-1,L^{*}-1\in\mathbb{L}_{1}\left(\bar{\mathbf{s}}_{11}\right)$
111Note: The set $\mathbb{L}_{1}\left(\mathbf{s}\right)$ is the same as
$\mathbb{L}_{1}(\bar{\mathbf{s}}_{11})$ except that
$\mathbb{L}_{1}\left(\mathbf{s}\right)$ contains an element which is the total
number of tasks in $\mathbf{s}$, while $\mathbb{L}_{1}(\bar{\mathbf{s}}_{11})$
does not contain that element.. Therefore, Ineqs. (48) suggests that $L^{*}-1$
is the optimal offloading decision for $\bar{\mathbf{s}}_{11}$. This proves
the first point of Theorem 1.

  * •

If $L^{*}=0$, i.e., $\mathbf{s}$ is a non-offloading state. Then, if
$\mathbf{s}$ has only one task, we have
$\bar{\mathbf{s}}_{11}\equiv\left(0,\ldots,0\right)$. Therefore,
$\bar{\mathbf{s}}_{11}$ is a non-offloading state trivially.

If $\mathbf{s}$ has at least 2 tasks. From the convexity of the function
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)=J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{dL}\right)+LC_{o}$,
and the condition that $L^{*}=0$, we have

$\displaystyle\begin{split}&J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)\leq
J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{11}\right)+C_{o},\text{ for
all
}L\in\mathbb{L}_{1}\left(\mathbf{s}\right)\backslash\left\\{0,1\right\\},\\\
&J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{11}\right)+C_{o}\leq
J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{1L}\right)+LC_{o},\text{
for all
}L\in\mathbb{L}_{1}\left(\mathbf{s}\right)\backslash\left\\{0,1\right\\}.\end{split}$
(49)

where the two inequalities in Ineq. (49) are from the optimality of $L^{*}$,
and the convexity of cost functions proven in Subsec. X-C, respectively.

Applying Eq. (39) to the second inequality of Ineqs. (49), we have

$\displaystyle J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},0\right)+C_{o}\leq
J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{1L},0\right)+LC_{o},\text{ for all
}L\in\mathbb{L}_{1}\left(\mathbf{s}\right)\backslash\left\\{0,1\right\\}.$
(50)

Using Eq. (45) with $L_{1}=1$ and $L_{2}=L-1$ gives us

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s},L\right)=J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},L-1\right)+C_{o}.$
(51)

Also, using Eq. (45) with $L_{1}=L$ and $L_{2}=0$ yields

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s},L\right)=J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{1L},0\right)+LC_{o}.$
(52)

From Eqs. (51) and (52), we have

$\displaystyle
J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},L-1\right)+C_{o}=J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{1L},0\right)+LC_{o}.$
(53)

Combining Eq. (53) with Ineqs. (50) gives the following set of inequalities:

$\displaystyle J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},0\right)\leq
J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},L-1\right),\text{ for all
}L\in\mathbb{L}_{1}\left(\mathbf{s}\right)\backslash\left\\{0,1\right\\}.$
(54)

By replacing $L-1$ with $\tilde{L}$ in the above inequalities, we have

$\displaystyle J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},0\right)\leq
J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{11},\tilde{L}\right),\text{ for all
}\tilde{L}\in\mathbb{L}_{1}\left(\bar{\mathbf{s}}_{11}\right)\backslash\left\\{0\right\\},$
(55)

indicating that $\bar{\mathbf{s}}_{11}$ is a non-offloading state. This proves
the second point of Theorem 1.

Finally, from the first two points of Theorem 1, we can conclude that, for
given time horizon $T$, if $L^{*}\geq 1$ is the optimal offloading decision
for state $\mathbf{s}$, $L^{*}_{a}=L^{*}+1$ is optimal for every state
$\mathbf{s}_{a}\in\mathbb{S}_{adj}\left(\mathbf{s}\right)$. This is because if
$L^{*}_{a}\neq L^{*}+1$ and $L^{*}_{a}\geq 1$, from the first point of Theorem
1, the optimal decision for $\mathbf{s}$ must be $L^{*}_{a}-1\neq L^{*}$ which
is a contradiction. Moreover, if $L^{*}_{a}=0$, from the second point of
Theorem 1, $\mathbf{s}$ must be a non-offloading state, leading to another
contradiction. This proves the third point of Theorem 1.

###  IX-B Proof of Theorem 2

We recall that given an current state $\mathbf{s}$, $\bar{\mathbf{s}}_{1L}$
denotes the resulting state by offloading $L$ most imminent task from
$\mathbf{s}$. If $L^{*}=0$ is the optimal offloading decision of state
$\mathbf{s}$, then, $\mathbf{s}$ is a non-offloading state. It is trivially
that $L^{*}=0$ is the smallest offloading decision to reach a non-offloading
state.

Let us consider the sequence of states
$\bar{\mathbf{s}}_{10}=\mathbf{s},\bar{\mathbf{s}}_{11},\bar{\mathbf{s}}_{12},\ldots,\bar{\mathbf{s}}_{1i},\ldots$.
By definition of the notation $\bar{\mathbf{s}}_{1i}$, state
$\bar{\mathbf{s}}_{1\left(i+1\right)}$ is obtained by offloading the most
imminent task from state $\bar{\mathbf{s}}_{1i}$ in the sequence. Therefore,
state $\bar{\mathbf{s}}_{1i}$ is adjacent to
$\bar{\mathbf{s}}_{1\left(i+1\right)}$. Assume $L^{*}>0$ is the optimal
offloading decision for $\mathbf{s}$. From the first point of Theorem 1, the
optimal offloading decision of state $\bar{\mathbf{s}}_{11}$ would be
$L^{*}_{1}=L^{*}-1$. By alternatively applying this property, the optimal
offloading decisions $L^{*}_{i}$ of states $\bar{\mathbf{s}}_{1i}$ for
$i=1,\ldots,L^{*}$ can be derived as

$\displaystyle L^{*}_{i}=L^{*}-i,\text{ for }i=1,\ldots,L^{*}.$ (56)

The above result suggests that the optimal offloading decision of the state
$\bar{\mathbf{s}}_{1L^{*}}$ would be $L^{*}_{i}=0$ for $i=L^{*}$. From the
second point of Theorem 1, the optimal offloading decision of
$\bar{\mathbf{s}}_{1\left(L^{*}+1\right)}$ would also be 0. Repeatedly
applying this property allows us to derive the optimal decisions for state
$\bar{\mathbf{s}}_{1i},i>L^{*}$ as follows:

$\displaystyle L^{*}_{i}=0,\text{ for }i>L^{*}.$ (57)

In conclusion, states $\bar{\mathbf{s}}_{1i}$ for $i\leq L^{*}-1$ are
offloading states, and states $\bar{\mathbf{s}}_{1i}$ for $i\geq L^{*}$ are
non-offloading states. Therefore, $L^{*}>0$ is the smallest offloading
decision to reach a non-offloading state $\bar{\mathbf{s}}_{1L^{*}}$.

##  X Appendix B: Proofs of Lemmas

###  X-A Proof of Lemma 1

A sequence $(a_{1},a_{2},\ldots,a_{N})$ of non-negative integers is called
Catalan if

$\displaystyle 1\leq a_{1}\leq a_{2}\leq\cdots\leq a_{N}\mbox{ and }a_{i}\leq
i,\mbox{ for all $1\leq i\leq N$.}$ (58)

In the proof we show that there is a one-to-one correspondence betweeb reduced
sequences and Catalan sequences of the same length $N$. The correspondence is
defined as follows.

Given a reduced sequence $(n_{1},n_{2},\ldots,n_{N})$, which satisfies
inequalities (22), define a sequence $(a_{1},a_{2},\ldots,a_{N})$ as follows

$a_{i}=(n_{1}+1)+n_{2}+\cdots+n_{i}.$

It is clear that the resulting sequence satisfies the Catalan sequence
property (58).

Conversely, given a Catalan sequence $(a_{1},a_{2},\ldots,a_{N})$, which
satisfies property (58), define the sequence $(n_{1},n_{2},\ldots,n_{N})$ as
follows

$n_{i}=\left\\{\begin{array}[]{ll}0&\mbox{ if $i=1$}\\\ a_{i}-a_{i-1}&\mbox{
if $2\leq i\leq N$}\end{array}\right.$

The resulting sequence contains elements of a reduced state vector because

$\displaystyle n_{1}+n_{2}+n_{3}+\cdots+n_{i}$
$\displaystyle=0+a_{2}-a_{1}+a_{3}-a_{2}+\cdots+a_{i}-a_{i-1}$
$\displaystyle=a_{i}-a_{1}$ $\displaystyle\leq i-1,$

since $a_{1}=1$. Also observe that the resulting correspondence between
reduced and Catalan sequences of the same length $N$ is one-to-one.

The proof of this lemma is now complete since in exercise 78 from [11], the
number of Catalan sequences of length $N$ is equal to the Catalan number
$C_{N}$.

###  X-B Proof of Lemma 2

We assume that an offloading state
$\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$ is given with $d$ is the deadline
of the most imminent task. It is trivially that when
$\mathbf{s}=\left(0,\ldots,0\right)$, the optimal decision is offloading 0
task. When $N\geq 2$, in the following two cases, the optimal decision is
offloading the most imminent task:

  * •

$d\leq N-1$, and $n_{i}=0$ for $i=d+1,\ldots,N$.

  * •

$d=N$.

Examples for these cases are given below:

###### Example 5

In the following two examples, it is trivially that the optimal policy
offloads the most imminent tasks:

  * •

$\mathbf{s}=\left(0,0,4,0,0\right)$ where $N=5$, $d=3$, and $n_{i}=0,i=4,5$.

  * •

$\mathbf{s}=\left(0,0,0,0,7\right)$ where $d=N=5$.

Now, we will consider the remaining case which is: $N\geq 2$, and $d\leq N-1$,
and there exists a deadline $d^{\prime}\in\left\\{d+1,\ldots,N\right\\}$ such
that $n_{d^{\prime}}>0$. This indicates that $n_{i}=0,i=1,\ldots,d-1$,
$n_{d}\geq 1$, and $n_{d^{\prime}}\geq 1$. Let us recall the following
notation:

  * •

$\bar{\mathbf{s}}_{d1}$ is the state obtained by offloading a task at deadline
$d$ from state $\mathbf{s}$.

  * •

$\bar{\mathbf{s}}_{d^{\prime}1}$ is the state obtained by offloading a task at
deadline $d^{\prime}$ from state $\mathbf{s}$.

We notice that the $i^{\text{th}}$ elements of state $\bar{\mathbf{s}}_{d1}$
is defined by

$\displaystyle\begin{cases}n_{d}-1,&\text{ if }i=d,\\\ n_{i},&\text{ if }i\neq
d.\end{cases}$ (59)

The $i^{\text{th}}$ elements of state $\bar{\mathbf{s}}_{d^{\prime}1}$ is
defined by

$\displaystyle\begin{cases}n_{d^{\prime}}-1,&\text{ if }i=d^{\prime},\\\
n_{i},&\text{ if }i\neq d^{\prime}.\end{cases}$ (60)

Therefore, we have:
$\bar{\mathbf{s}}_{d1}\in\mathbb{S}_{pp}\left(\bar{\mathbf{s}}_{d^{\prime}1}\right)$.
From Proposition 2, we have

$\displaystyle J_{T}\left(\bar{\mathbf{s}}_{d1}\right)\leq
J_{T}\left(\bar{\mathbf{s}}_{d^{\prime}1}\right),\text{ for every given time
horizon }T.$ (61)

This indicates that state $\bar{\mathbf{s}}_{d1}$ is associated with a lower
average cost than that of state $\bar{\mathbf{s}}_{d^{\prime}1}$ for every
deadline $d^{\prime}\in\left\\{d+1,\ldots,N\right\\}$. Therefore, if
$\mathbf{s}$ is an offloading state, it is optimal to offload the most
imminent task from $\mathbf{s}$. Moreover, from the above proof, we can also
conclude that whenever the local processing is available, it is optimal to
process the most imminent task in $\mathbf{s}$.

To this end, by considering state $\bar{\mathbf{s}}_{d1}$ in the place of
state $\mathbf{s}$ and repeating the proof above, we have that: If
$\bar{\mathbf{s}}_{d1}$ is an offloading state, it is optimal to offload the
most imminent task from $\bar{\mathbf{s}}_{d1}$. Therefore, we can conclude
that: If $\mathbf{s}$ is an offloading state and the corresponding optimal
offloading decision is 2, it is optimal to offload 2 most imminent tasks from
$\mathbf{s}$. Keeping repeating the same analysis leads us to the final
conclusion as follows: If $\mathbf{s}$ is an offloading state, and the
corresponding optimal offloading decision is $L^{*}$, it is optimal to offload
the $L^{*}$ most imminent tasks from $\mathbf{s}$.

###  X-C Proof of Lemma 3

From the definition of function
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ in Eq. (28), we notice
that $LC_{o}$ is discrete linear, and hence, discrete convex with respect to
$L$. Therefore, in order to prove that
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ is discrete convex with
respect to $L$, we need to prove that

$\displaystyle
f^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)=J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{dL}\right)$
(62)

is discrete convex with respect to $L$. To begin with, let us define two other
functions as follows:

$\displaystyle
f\left(T,\mathbf{s},d,L\right)=J_{T}\left(\bar{\mathbf{s}}_{dL}\right),$ (63)
$\displaystyle
f^{\text{A}}\left(T,\mathbf{s},d,L\right)=J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{dL}\right).$
(64)

The three functions $f\left(T,\mathbf{s},d,L\right)$,
$f^{\text{A}}\left(T,\mathbf{s},d,L\right)$, and
$f^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ are characterized by
the parameters $T$, $\mathbf{s}$, and $d$. All of them take $L$ as variable.
The domains of these three functions are the same as that of
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ which are given in Eqs.
(29) and (30).

The definitions of $J^{\text{A}}_{T}\left(\cdot\right)$ and
$J^{\overline{\text{A}}}_{T}\left(\cdot\right)$ are given in Eqs. (19) and
(20). In this subsection, we re-express
$J^{\text{A}}_{T}\left(\bar{\mathbf{s}}_{dL}\right)$ and
$J^{\overline{\text{A}}}_{T}\left(\bar{\mathbf{s}}_{dL}\right)$ as follows:

$\displaystyle
J^{\text{A}}_{T}\left(\bar{\mathbf{s}}_{dL}\right)=\underset{L^{\prime}\in\mathbb{L}\left(\bar{\mathbf{s}}_{dL}\right)}{\min}\left\\{\mathcal{C}^{\text{A}}\left(\bar{\mathbf{s}}_{dL},L^{\prime}\right)+G^{\text{A}}\left(\bar{\mathbf{s}}_{dL},L^{\prime}\right)\right\\},$
(65) $\displaystyle
J^{\overline{\text{A}}}_{T}\left(\bar{\mathbf{s}}_{dL}\right)=\mathcal{C}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{dL}\right)+G^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{dL}\right)=\mathcal{C}^{\text{A}}\left(\bar{\mathbf{s}}_{dL},0\right)+G^{\text{A}}\left(\bar{\mathbf{s}}_{dL},0\right).$
(66)

By denoting $M_{d}=\sum_{i=d}^{N}n_{i}$. We can express the functions
$f^{\text{A}}\left(T,\mathbf{s},d,L\right)$ and
$f^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ as follows:

$\displaystyle\underset{L\in\mathbb{L}_{d}\left(\mathbf{s}\right)}{f^{\text{A}}\left(T,\mathbf{s},d,L\right)}$
$\displaystyle=\underset{\hat{L}\in\left\\{0,\ldots,M_{d}-L\right\\}}{\min}\left\\{\left(L+\hat{L}\right)C_{o}+G_{T-1}\left(\mathbf{s},d,L+\hat{L}\right)\right\\}+\mathds{1}_{d\geq
2}n_{1}C_{p},$ (67)
$\displaystyle\underset{L\in\mathbb{L}_{d}\left(\mathbf{s}\right)}{f^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)}$
$\displaystyle=G_{T-1}\left(\mathbf{s},d,L\right)+\mathds{1}_{d\geq
2}n_{1}C_{p}.$ (68)

In (67), we denote $\bar{L}=L+\hat{L}$. Then, the average future cost function
$G_{T}\left(\mathbf{s},d,\bar{L}=L+\hat{L}\right)$ is given by

$\displaystyle
G_{T-1}\left(\mathbf{s},d,\bar{L}\right)=\mu\sum_{k=0}^{N}p_{k}J_{T-1}\left(\mathbf{s}_{d\bar{L}k}^{{}^{\prime}}\right)+\left(1-\mu\right)\sum_{k=0}^{N}p_{k}J_{T-1}\left(\mathbf{s}_{d\bar{L}k}^{{}^{\prime\prime}}\right)$
(69)

where $\mathbf{s}_{d\bar{L}k}^{{}^{\prime}}$ is the state transited from
$\mathbf{s}$ with the following steps: offloading $\bar{L}=L+\hat{L}$ most
imminent tasks starting from deadline $d$, deadline shifting, a task arrives
with deadline $k$ ($k=0$ implies no task arrival), and local processing.
$\mathbf{s}_{d\bar{L}k}^{{}^{\prime\prime}}$ is defined similarly but without
the local processing at the end.

Subsequently, we will show that each term $J_{T-1}\left(\cdot\right)$ on the
right-hand side of Eq. (69) can be presented by the family of function $f$.
Let us consider an initial state
$\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)\not\equiv\left(0,\ldots,0\right)$.
First of all, we need to find states $\mathbf{s}^{1}$ and $\mathbf{s}^{2}$
such that $\mathbf{s}^{1}_{d\bar{L}}\equiv\mathbf{s}_{d\bar{L}k}^{\prime}$ and
$\mathbf{s}^{2}_{d\bar{L}}\equiv\mathbf{s}_{d\bar{L}k}^{\prime\prime}$ where
$\mathbf{s}^{1}_{d\bar{L}}$ and $\mathbf{s}^{2}_{d\bar{L}}$ are obtained by
removing $\bar{L}$ most imminent tasks having deadline greater than or equal
to $d$ from $\mathbf{s}^{1}$ and $\mathbf{s}^{2}$, respectively. Then, we will
have the followings:

$\displaystyle f\left(T-1,\mathbf{s}^{1},d^{\prime},L^{\prime}\right)$
$\displaystyle=J_{T-1}\left(\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}\right)=J_{T-1}\left(\mathbf{s}_{d\bar{L}k}^{\prime}\right),$
(70) $\displaystyle
f\left(T-1,\mathbf{s}^{2},d^{\prime\prime},L^{\prime\prime}\right)$
$\displaystyle=J_{T-1}\left(\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}\right)=J_{T-1}\left(\mathbf{s}_{d\bar{L}k}^{\prime\prime}\right).$
(71)

Hereafter, we will defined $\mathbf{s}^{1}$, $\mathbf{s}^{2}$, $d^{\prime}$,
$d^{\prime\prime}$, $L^{\prime}$, and $L^{\prime\prime}$ in different cases,
and provide examples to support interpretation.

  * •

When $k+1<d$ which implies $d\geq 2$, we have:
$\mathbf{s}^{1}\equiv\mathbf{s}^{\prime}_{k}$,
$\mathbf{s}^{2}\equiv\mathbf{s}^{\prime\prime}_{k}$,
$d^{\prime}=d^{\prime\prime}=d-1$, and $L^{\prime}=L^{\prime\prime}=\bar{L}$.
The state $\mathbf{s}^{\prime}_{k}$ is obtained from $\mathbf{s}$ by:
performing deadline shifting, adding a new task with deadline $k$ ($k=0$
implies no new task is added), and removing the most imminent task. State
$\mathbf{s}^{\prime\prime}_{k}$ is defined similarly as state
$\mathbf{s}^{\prime}_{k}$, but without removing the most imminent task at the
end.

###### Example 6

As an example for the case “$k+1<d$”, we consider an initial state
$\mathbf{s}=\left(0,6,0,5,7\right)$, and a time horizon $T>5$. We assume that
$d=3$, and $\bar{L}=7$ most imminent tasks having deadline greater than or
equal to $d$ are offloaded, and $k=1$ implying that a new task arrives with
deadline 1 in the next time slot. Then, we have

$\displaystyle\mathbf{s}^{\prime}_{d\bar{L}k}=\mathbf{s}^{\prime}_{371}=\left(6,0,0,5,0\right),$
(72)
$\displaystyle\mathbf{s}^{\prime\prime}_{d\bar{L}k}=\mathbf{s}^{\prime\prime}_{371}=\left(7,0,0,5,0\right).$
(73)

The states $\mathbf{s}^{\prime}_{k}$ and $\mathbf{s}^{\prime\prime}_{k}$ in
this example are

$\displaystyle\mathbf{s}^{\prime}_{k}=\mathbf{s}^{\prime}_{1}=\left(6,0,5,7,0\right),$
(74)
$\displaystyle\mathbf{s}^{\prime\prime}_{k}=\mathbf{s}^{\prime}_{1}=\left(7,0,5,7,0\right).$
(75)

With $\mathbf{s}^{1}\equiv\mathbf{s}^{\prime}_{k}$,
$\mathbf{s}^{2}\equiv\mathbf{s}^{\prime\prime}_{k}$,
$d^{\prime}=d^{\prime\prime}=d-1=2$, and
$L^{\prime}=L^{\prime\prime}=\bar{L}=7$ as presented above, the states
$\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}$ and
$\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}$ are given by

$\displaystyle\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}=\mathbf{s}^{1}_{27}=\left(6,0,0,5,0\right),$
(76)
$\displaystyle\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}=\mathbf{s}^{2}_{27}=\left(7,0,0,5,0\right).$
(77)

This shows that state $\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}$ in Eq.
(76) is the same as state $\mathbf{s}^{\prime}_{d\bar{L}k}$ in Eq. (72). Also,
state $\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}$ in Eq. (77) is
the same as state $\mathbf{s}^{\prime\prime}_{d\bar{L}k}$ in Eq. (73).
Therefore, Eqs. (70) and (71) can be achieved.

  * •

When $k+1\geq d$, let $\beta_{dk}=\sum_{i=d}^{k+1}n_{i}$, we have:

    * –

If $d\geq 2$: For $\bar{L}\leq\beta_{dk}$,
$\mathbf{s}^{1}\equiv\mathbf{s}^{\prime}_{k}$,
$\mathbf{s}^{2}\equiv\mathbf{s}^{\prime\prime}_{k}$,
$d^{\prime}=d^{\prime\prime}=d-1$, and $L^{\prime}=L^{\prime\prime}=\bar{L}$.
For $\bar{L}>\beta_{dk}$,
$\mathbf{s}^{1}\equiv\mathbf{s}^{\prime}_{d\beta_{dk}k}$,
$\mathbf{s}^{2}\equiv\mathbf{s}^{\prime\prime}_{d\beta_{dk}k}$,
$d^{\prime}=d^{\prime\prime}=k+1$, and
$L^{\prime}=L^{\prime\prime}=\bar{L}-\beta_{dk}$.

    * –

If $d=1$: For $\bar{L}\leq\beta_{dk}$,
$\mathbf{s}^{1}\equiv\mathbf{s}^{\prime}_{k}$,
$\mathbf{s}^{2}\equiv\mathbf{s}^{\prime\prime}_{k}$,
$d^{\prime}=d^{\prime\prime}=d$, and
$L^{\prime}=L^{\prime\prime}=\bar{L}-n_{1}$. For $\bar{L}>\beta_{dk}$,
$\mathbf{s}^{1}\equiv\mathbf{s}^{\prime}_{d\beta_{dk}k}$,
$\mathbf{s}^{2}\equiv\mathbf{s}^{\prime\prime}_{d\beta_{dk}k}$,
$d^{\prime}=d^{\prime\prime}=k+1$, and
$L^{\prime}=L^{\prime\prime}=\bar{L}-\beta_{dk}$.

We note that state $\mathbf{s}^{\prime}_{d\beta_{dk}k}$ is obtained following
the steps: offloading $\beta_{dk}$ most imminent tasks having deadline greater
than or equal to $d$ from the initial state $\mathbf{s}$, performing deadline
shifting, adding a task with deadline $k$, and removing the most imminen task.
State $\mathbf{s}^{\prime\prime}_{d\beta_{dk}k}$ is defined in the same way
but without removing the most imminent task at the end.

###### Example 7

Two examples for this case corresponding to $d\geq 2$ and $d=1$ are as
follows. Let us consider an initial state $\mathbf{s}=\left(0,3,0,7,5\right)$,
a time horizon $T>5$, and $\bar{L}=9$. For the first example, we assume that
$d=2$, and $k=2$. We have $\beta_{dk}=\beta_{22}=3$. The states
$\mathbf{s}^{\prime}_{d\bar{L}k}$ and $\mathbf{s}^{\prime\prime}_{d\bar{L}k}$
are computed as

$\displaystyle\mathbf{s}^{\prime}_{d\bar{L}k}=\mathbf{s}^{\prime}_{292}=\left(0,0,1,5,0\right),$
(78)
$\displaystyle\mathbf{s}^{\prime\prime}_{d\bar{L}k}=\mathbf{s}^{\prime\prime}_{292}=\left(0,1,1,5,0\right).$
(79)

Since $L=9>\beta_{dk}=3$, we compute states
$\mathbf{s}^{\prime}_{d\beta_{dk}k}$ and
$\mathbf{s}^{\prime\prime}_{d\beta_{dk}k}$ as follows:

$\displaystyle\mathbf{s}^{\prime}_{d\beta_{dk}k}=\mathbf{s}^{\prime}_{232}=\left(0,0,7,5,0\right),$
(80)
$\displaystyle\mathbf{s}^{\prime\prime}_{d\beta_{dk}k}=\mathbf{s}^{\prime\prime}_{232}=\left(0,1,7,5,0\right).$
(81)

As presented above, we have $\mathbf{s}^{1}\equiv\mathbf{s}^{\prime}_{k}$,
$\mathbf{s}^{2}\equiv\mathbf{s}^{\prime\prime}_{k}$,
$d^{\prime}=d^{\prime\prime}=k+1=3$, and
$L^{\prime}=L^{\prime\prime}=\bar{L}-n_{d}=9-3=6$. Therefore, states
$\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}$ and
$\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}$ are computed as

$\displaystyle\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}=\mathbf{s}^{1}_{19}=\left(0,0,1,5,0\right),$
(82)
$\displaystyle\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}=\mathbf{s}^{2}_{19}=\left(0,1,1,5,0\right).$
(83)

Then, state $\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}$ in Eq. (82) is the
same as state $\mathbf{s}^{\prime}_{d\bar{L}k}$ in Eq. (78). State
$\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}$ in Eq. (83) is the
same as state $\mathbf{s}^{\prime\prime}_{d\bar{L}k}$ in Eq. (79). Therefore,
we obtained Eqs. (70) and (71).

In the second example, we assume that $d=1$ and $k=3$. We have
$\beta_{dk}=\beta_{13}=10$. The states $\mathbf{s}^{\prime}_{d\bar{L}k}$ and
$\mathbf{s}^{\prime\prime}_{d\bar{L}k}$ are

$\displaystyle\mathbf{s}^{\prime}_{d\bar{L}k}=\mathbf{s}^{\prime}_{193}=\left(0,0,0,6,0\right),$
(84)
$\displaystyle\mathbf{s}^{\prime\prime}_{d\bar{L}k}=\mathbf{s}^{\prime\prime}_{193}=\left(0,0,1,6,0\right)..$
(85)

Now $\bar{L}=9\leq\beta_{dk}=10$, we define state $\mathbf{s}^{\prime}_{k}$
and $\mathbf{s}^{\prime\prime}_{k}$ as follows:

$\displaystyle\mathbf{s}^{\prime}_{k}=\left(2,0,7,6,0\right),$ (86)
$\displaystyle\mathbf{s}^{\prime\prime}_{k}=\left(3,0,7,6,0\right).$ (87)

We have $\mathbf{s}^{1}\equiv\mathbf{s}^{\prime}_{k}$,
$\mathbf{s}^{2}\equiv\mathbf{s}^{\prime\prime}_{k}$,
$d^{\prime}=d^{\prime\prime}=d=1$, and
$L^{\prime}=L^{\prime\prime}=\bar{L}-n_{1}=9$. Thus, states
$\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}$ and
$\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}$ are computed as

$\displaystyle\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}=\mathbf{s}^{1}_{19}=\left(0,0,0,6,0\right),$
(88)
$\displaystyle\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}=\mathbf{s}^{2}_{19}=\left(0,0,1,6,0\right).,$
(89)

which suggests that state $\bar{\mathbf{s}}^{1}_{d^{\prime}L^{\prime}}$ in Eq.
(88) is the same as state $\mathbf{s}^{\prime}_{d\bar{L}k}$ in Eq. (84). State
$\bar{\mathbf{s}}^{2}_{d^{\prime\prime}L^{\prime\prime}}$ in Eq. (89) is the
same as state $\mathbf{s}^{\prime\prime}_{d\bar{L}k}$ in Eq. (85). As a
result, we achieve Eqs. (70) and (71).

From the presented cases, the terms
$J_{T-1}\left(\mathbf{s}^{\prime}_{d\bar{L}k}\right)$ and
$J_{T-1}\left(\mathbf{s}^{\prime\prime}_{d\bar{L}k}\right)$ are expressed by
functions $f$ as follows:

  * •

If $k+1<d$:

$\displaystyle J_{T-1}\left(\mathbf{s}^{\prime}_{d\bar{L}k}\right)$
$\displaystyle=f\left(T-1,\mathbf{s}^{\prime}_{k},d-1,\bar{L}\right),$ (90)
$\displaystyle J_{T-1}\left(\mathbf{s}^{\prime\prime}_{d\bar{L}k}\right)$
$\displaystyle=f\left(T-1,\mathbf{s}^{\prime\prime}_{k},d-1,\bar{L}\right).$
(91)

  * •

If $k+1\geq d$ and $d\geq 2$:

$\displaystyle
J_{T-1}\left(\mathbf{s}^{\prime}_{d\bar{L}k}\right)=g^{\prime}_{dk}\left(\bar{L}\right)=\begin{cases}f\left(T-1,\mathbf{s}^{\prime}_{k},d-1,\bar{L}\right),&\text{
if }\bar{L}\leq\beta_{dk},\\\
f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,\bar{L}-\beta_{dk}\right),&\text{
if }\bar{L}>\beta_{dk},\end{cases}$ (92)

$\displaystyle
J_{T-1}\left(\mathbf{s}^{\prime\prime}_{d\bar{L}k}\right)=g^{\prime\prime}_{dk}\left(\bar{L}\right)=\begin{cases}f\left(T-1,\mathbf{s}^{\prime\prime}_{k},d-1,\bar{L}\right),&\text{
if }\bar{L}\leq\beta_{dk},\\\
f\left(T-1,\mathbf{s}^{\prime\prime}_{d\beta_{dk}k},k+1,\bar{L}-\beta_{dk}\right),&\text{
if }\bar{L}>\beta_{dk},\end{cases}$ (93)

where $\beta_{dk}=\sum_{i=d}^{k+1}n_{i}$.

  * •

If $k+1\geq d$ and $d=1$:

$\displaystyle
J_{T-1}\left(\mathbf{s}^{\prime}_{1\bar{L}k}\right)=g^{\prime}_{1k}\left(\bar{L}\right)=\begin{cases}f\left(T-1,\mathbf{s}^{\prime}_{k},1,\bar{L}\right),&\text{
if }\bar{L}\leq\beta_{1k},\\\
f\left(T-1,\mathbf{s}^{\prime}_{1\beta_{1k}k},k+1,\bar{L}-\beta_{1k}\right),&\text{
if }\bar{L}>\beta_{1k},\end{cases}$ (94)

$\displaystyle
J_{T-1}\left(\mathbf{s}^{\prime\prime}_{1\bar{L}k}\right)=g^{\prime\prime}_{1k}\left(\bar{L}\right)=\begin{cases}f\left(T-1,\mathbf{s}^{\prime\prime}_{k},1,\bar{L}\right),&\text{
if }\bar{L}\leq\beta_{1k},\\\
f\left(T-1,\mathbf{s}^{\prime\prime}_{1\beta_{1k}k},k+1,\bar{L}-\beta_{1k}\right),&\text{
if }\bar{L}>\beta_{1k},\end{cases}$ (95)

where $\beta_{1k}=\sum_{i=1}^{k+1}n_{i}$.

In the above, $g^{\prime}_{dk}\left(\bar{L}\right)$ and
$g^{\prime\prime}_{dk}\left(\bar{L}\right)$ are functions characterized by
parameters $d$ and $k$, and take $\bar{L}$ as their variables.

Next, we will prove the convexity of functions $f$ using induction, starting
with an initial case.

Initial case: We consider state $\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$,
and a time horizon $T=1$.

In this case, if $N=1$, we have $\mathbf{s}=\left(n_{1}\right)$, then, there
is only one valid offloading decision
$\mathbb{L}_{1}\left(\mathbf{s}\right)=\left\\{n_{1}\right\\}$. For $N\geq 2$,
it is trivially that all tasks having deadline 1 are excessive tasks, and
should be offloaded whenever the AMA is available, which results in a cost
$n_{1}C_{o}$. If the AMA is not available at the initial time slot, tasks with
deadline 1 will expire and result in a cost $n_{1}C_{p}$. Since in this case,
we are considering a time horizon with only one time slot, the minimum average
cost can be computed straightforwardly. Thus, we have the following

$\displaystyle f\left(1,\mathbf{s},1,L\right)$
$\displaystyle=J_{1}\left(\mathbf{s}_{1L}\right)=\left(p_{u}C_{o}+\left(1-p_{u}\right)C_{p}\right)n_{1}+\left(L-n_{1}\right)C_{o},\text{
for }L\in\mathbb{L}_{1}\left(\mathbf{s}\right),$ (96) $\displaystyle
f\left(1,\mathbf{s},d,L\right)$
$\displaystyle=J_{1}\left(\mathbf{s}_{dL}\right)=n_{1}C_{p}+LC_{o},\text{ for
}d\geq 2\text{ and }L\in\mathbb{L}_{d}\left(\mathbf{s}\right).$ (97)

We recall that the smallest offloading decision in the set
$\mathbb{L}_{1}\left(\mathbf{s}\right)$ is $n_{1}$. From Eqs. (96) and (97),
$f\left(1,\mathbf{s},d,L\right),d=1,\ldots,N$ are discrete linear function
with respect to $L$, hence, they are discrete convex function with respect to
$L$. Next is an inductive step where we prove the convexity of
$f\left(T,\mathbf{s},d,L\right)$ gven that of
$f\left(T-1,\mathbf{s},d,L\right)$ for every parameters $\mathbf{s}$ and $d$.

Inductive step: Let us make the following assumption: The functions
$f\left(T-1,\mathbf{s},d,L\right)$ is discrete convex with respect to $L$ for
every given state $\mathbf{s}$ and deadline $d$.

Now, we consider Eqs. (90)-(95) with $\bar{L}$ is replaced by $L+\hat{L}$.
From the above assumption,
$f\left(T-1,\mathbf{s}^{\prime}_{k},d-1,L+\hat{L}\right)$ in Eq. (90), and
$f\big{(}T-1,\mathbf{s}^{\prime\prime}_{k},d-1,L+\hat{L}\big{)}$ in Eq. (91)
are discrete convex with respect to $L$. Next, we will prove that
$g^{\prime}_{dk}\left(L+\hat{L}\right)$ in Eq. (92) is discrete convex with
respect with respect to $L$. Then, the convexity of functions
$g^{\prime\prime}_{dk}\left(L+\hat{L}\right)$ in Eq. (93),
$g^{\prime}_{1k}\left(L+\hat{L}\right)$ in Eq. (94), and
$g^{\prime\prime}_{1k}\left(L+\hat{L}\right)$ in Eq. (95) can also be proved
in a very similar way.

Let us consider function $g^{\prime}_{dk}\left(L+\hat{L}\right)$ in Eq. (92).
With our assumption above,
$f\big{(}T-1,\mathbf{s}^{\prime}_{k},d-1,L+\hat{L}\big{)}$ for
$L+\hat{L}\leq\beta_{dk}$, and
$f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,L+\hat{L}-\beta_{dk}\right)$
for $L+\hat{L}>\beta_{dk}$ are discrete convex with respect to $L$. Therefore,
in order to prove the convexity of $g^{\prime}_{dk}\left(L+\hat{L}\right)$ we
will prove that the discrete Jensen’s inequality holds at the connecting point
of $f\big{(}T-1,\mathbf{s}^{\prime}_{k},d-1,L+\hat{L}\big{)}$ and
$f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,L+\hat{L}-\beta_{dk}\right)$,
i.e., at $\bar{L}=\beta_{dk}$. To be more specific, we will prove the
following:

$\displaystyle
f\left(T-1,\mathbf{s}^{\prime}_{k},d-1,\beta_{dk}\right)+f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,2\right)\geq
2f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,1\right).$ (98)

From the definition of function $f$ in Eq. (63), we have

$\displaystyle
f\left(T-1,\mathbf{s}^{\prime}_{k},d-1,\beta_{dk}\right)=J_{T-1}\left(\mathbf{s}^{\prime}_{d\beta_{dk}k}\right),$
(99)

and also

$\displaystyle
f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,0\right)=J_{T-1}\left(\mathbf{s}^{\prime}_{d\beta_{dk}k}\right).$
(100)

Hence,

$\displaystyle
f\left(T-1,\mathbf{s}^{\prime}_{k},d-1,\beta_{dk}\right)=f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,0\right).$
(101)

Moreover, since
$f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,L+\hat{L}\right)$ is
discrete convex with respect to $L$ due to our assumption, we have

$\displaystyle
f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,0\right)+f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,2\right)\geq
2f\left(T-1,\mathbf{s}^{\prime}_{d\beta_{dk}k},k+1,1\right).$ (102)

By combining Eq. (101) and Ineq. (102), we prove that Ineq. (98) is true.
Therefore, $g^{\prime}_{dk}\left(L+\hat{L}\right)$ in Eq. (92) is discrete
convex with respect to $L$. Similarly,
$g^{\prime\prime}_{dk}\left(L+\hat{L}\right)$ in Eq. (93),
$g^{\prime}_{1k}\left(L+\hat{L}\right)$ in Eq. (94), and
$g^{\prime\prime}_{1k}\left(L+\hat{L}\right)$ in Eq. (95) are also discrete
convex with respect to $L$.

By using Eqs. (90)-(95), we can express
$G_{T-1}\left(\mathbf{s},d,L+\hat{L}\right)$ defined in Eq. (69) (where
$\bar{L}$ is replaced by $L+\hat{L}$) by the sum of multiple functions $f$
having $T-1$ as the first argument. Furthermore, these functions are discrete
convex with respect to $L$ according to our assumption at the beginning of
this Inductive step. Therefore, $G_{T-1}\left(\mathbf{s},d,L+\hat{L}\right)$
is a discrete convex function with respect to $L$.

Now, we will refer to the constant term $\mathds{1}_{d\geq 2}n_{1}C_{p}$ in
(67) as $constant$, and denote

$\displaystyle
g\left(L+\hat{L}\right)=\left(L+\hat{L}\right)C_{o}+G_{T}\left(\mathbf{s},d,L+\hat{L}\right).$
(103)

where $G_{T}\left(\mathbf{s},d,L+\hat{L}\right)$ has been proved to be a
discrete convex function. In addition, $\left(L+\hat{L}\right)C_{o}$ is
discrete linear, hence, also discrete convex. As a result,
$g\left(L+\hat{L}\right)$ is a discrete convex function with respect to $L$.
Then, Eq. (67) becomes

$\displaystyle\underset{L\in\mathbb{L}_{d}\left(\mathbf{s}\right)}{f^{\text{A}}\left(T,\mathbf{s},d,L\right)}=\underset{\hat{L}\in\left\\{0,1,\ldots,M_{d}-L\right\\}}{\min}\left\\{g\left(L+\hat{L}\right)\right\\}+constant.$
(104)

Assuming that $g\left(L+\hat{L}\right)$ attains its minimum
$g^{\min}\left(L^{*}\right)$ at $L^{*}\geq n_{1}$. Note that the condition
$L^{*}\geq n_{1}$ holds because all tasks having deadline 1 are excessive
tasks, and will result in a penalty $C_{p}$ per task if not offloaded.
Therefore, given that $C_{p}>C_{o}$, the optimal offloading decision cannot be
less than $n_{1}$. Then, we have

$\displaystyle\underset{L\in\mathbb{L}_{d}\left(\mathbf{s}\right)}{f^{\text{A}}\left(T,\mathbf{s},d,L\right)}=\begin{cases}g^{\min}\left(L^{*}\right)+constant,&\text{
if }L\leq L^{*},\\\ g\left(L\right)+constant\text{ where }\hat{L}=0,&\text{ if
}L>L^{*}.\end{cases}$ (105)

As a results, $f^{\text{A}}\left(T,\mathbf{s},d,L\right)$ are discrete convex
functions with respect to $L\in\mathbb{L}_{d}\left(\mathbf{s}\right)$ for all
states $\mathbf{s}$ and deadlines $d$.

$G_{T-1}\left(\mathbf{s},d,L\right)$ in Eq. (68) can be expressed in a similar
fashion as Eq. (69) with $\bar{L}$ is replaced by $L$, since without the AMA,
$\hat{L}=0$. Thus, $G_{T-1}\left(\mathbf{s},d,L\right)$ in Eq. (68) can also
be written as the sum of several functions $f$, each has $T-1$ as its first
argument. This suggests that in Eq. (68), $G_{T-1}\left(\mathbf{s},d,L\right)$
is a discrete convex function with respect to $L$ for every given $\mathbf{s}$
and $d$, and so is $f^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$.
Afterwards, by combining our definitions presented in Eqs. (62)-(64) with the
following equation:

$\displaystyle
J_{T}\left(\bar{\mathbf{s}}_{dL}\right)=p_{u}J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{dL}\right)+\left(1-p_{u}\right)J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{dL}\right),$
(106)

we have

$\displaystyle
f\left(T,\mathbf{s},d,L\right)=p_{u}f^{\text{A}}\left(T,\mathbf{s},d,L\right)+\left(1-p_{u}\right)f^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right).$
(107)

Therefore, $f\left(T,\mathbf{s},d,L\right)$ is also a discrete convex function
with respect to $L$ for every given state $\mathbf{s}$ and deadline $d$.

This result together with the presented Initial case lead us to a conclusion
that $f\left(T,\mathbf{s},d,L\right)$ are discrete convex functions with
respect to $L$ for all parameters $T$, $\mathbf{s}$, and $d$. As
$G_{T}\left(\mathbf{s},d,L\right)$ is expressed by the sum of multiple
functions $f$, so is $f^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$,
which is shown in Eq. (68). Therefore,
$f^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ is also discrete convex
functions with respect to $L$. Then, from our discussion at the beginning of
this subsection, we can conclude that
$F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$ are discrete convex
functions with respect to $L$ for all parameters $T$, $\mathbf{s}$, and $d$.
This completes our proof.

###  X-D Proof of Lemma 4

We assume that function $F^{\overline{\text{A}}}\left(T,\mathbf{s},d,L\right)$
attains its minimum at $L^{*}$ for $d=1$, the following set of inequalities
hold

$\displaystyle
J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{1L^{*}}\right)+L^{*}C_{o}\leq
J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{1L}\right)+LC_{o},\text{
for all }L\in\mathbb{L}_{1}\left(\mathbf{s}\right).$ (108)

From Eq. (40) and Ineqs. (108), we have

$\displaystyle J_{T}^{\text{A}}\left(\mathbf{s},L^{*}\right)\leq
J_{T}^{\text{A}}\left(\mathbf{s},L\right),\text{ for all
}L\in\mathbb{L}_{1}\left(\mathbf{s}\right).$ (109)

Equivalently,

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s},L^{*}\right)=\underset{L\in\mathbb{L}_{1}\left(\mathbf{s}\right)}{\min}\left\\{J_{T}^{\text{A}}\left(\mathbf{s},L\right)\right\\}.$
(110)

We recall a fact that the optimal offloading decision must not be less than
the number of tasks having deadline 1 which are all excessive tasks. Thus,
$L^{*}$ is the optimal offloading decision of $\mathbf{s}$ for the time
horizon $T$.

##  XI Appendix C: Proofs of Propositions

###  XI-A Proof of Proposition 1

Considering a state $\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$ and a time
horizon $T$. Let $\mathbf{s}_{r}=\left(n^{r}_{1},\ldots,n^{r}_{N}\right)$ be
the corresponding reduced state obtained via Algorithm 1, and let
$\mathbf{s}_{m}=\left(n^{m}_{1},\ldots,n^{m}_{N}\right)$ denote the
corresponding lean state obtained according to Definition 3. As $n_{i}^{m}$,
$i=1,\ldots,N$, are defined by Eq. (24) with the parameters $\gamma_{i}$,
$i=1,\ldots,N$, are given in Eq. (23), we have

$\displaystyle n_{i}^{r}\leq n_{i}^{m}\leq n_{i},~{}i=1,\ldots,N.$ (111)

Moreover, we recall that $n_{i}-n^{r}_{i}$ tasks having deadline $i$ in
$\mathbf{s}$, $i=1,\ldots,N$ are excessive tasks, i.e., they are guaranteed to
expire if not offloaded within the first $i$ time slots. Therefore,
$n_{i}-n^{m}_{i}$ tasks having deadline $i$ in $\mathbf{s}$, $i=1,\ldots,N$
are also excessive tasks. In other words, for each deadline, tasks that
$\mathbf{s}$ has more than $\mathbf{s}_{m}$ are excessive tasks.

###### Example 8

For example, with $\mathbf{s}=\left(0,3,4,0,5\right)$, the corresponding lean
state would be $\mathbf{s}_{r}=\left(0,1,1,0,4\right)$. Then, for deadline 1,
there are $3-1=2$ excessive tasks. For deadline 2, there are $4-1=3$ excessive
tasks. For deadline 4 and 5, there is $0$ excessive task.

Now let us consider the following cases in which we use the notations
$J_{T}\left(\mathbf{s}\right)\big{|}_{j}$ and
$J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{j}$ to denote the minimum average
cost of $\mathbf{s}$ and $\mathbf{s}_{m}$, respectively, given that the AMA
arrives for the first time at time slot $t$. Then, there are following cases.

  * •

Case 0: The AMA is available for the first time at the current time slot,
$t=0$. As we mentioned, for every deadline, tasks that state $\mathbf{s}$ has
more than state $\mathbf{s}_{m}$ are excessive tasks which should be offloaded
by the optimal policy whenever the AMA is available. Therefore, in this case,
if $L^{*}_{m}$ denotes the optimal number of tasks to offload of
$\mathbf{s}_{m}$, that of $\mathbf{s}$ will be $L^{*}_{m}+y$, where
$y=\sum_{i=1}^{N}(n_{i}-n_{i}^{m})$ is the partial number of excessive tasks
in $\mathbf{s}$. Hence,

$\displaystyle
J_{T}\left(\mathbf{s}\right)\big{|}_{0}=J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{0}+C_{o}\sum_{i=1}^{N}\left(n_{i}-n_{i}^{m}\right).$
(112)

  * •

Case 1: If the AMA is available for the first time at time slot 1, the number
of tasks having deadline 1 expiring from $\mathbf{s}$ is more than that from
$\mathbf{s}_{m}$ by $n_{1}-n_{1}^{m}$. All the other remaining excessive tasks
can be offloaded from both states $\mathbf{s}$ and $\mathbf{s}_{m}$. Hence,

$\displaystyle
J_{T}\left(\mathbf{s}\right)\big{|}_{1}=J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{1}+C_{o}\sum_{i=2}^{N}\left(n_{i}-n_{i}^{m}\right)+\left(n_{1}-n_{1}^{m}\right)C_{p}.$
(113)

The same logic can be applied to other cases when the AMA first arrives at
time slot $2,3,\ldots,N$. Therefore, we present next the last case.

  * •

Case $N$: If the AMA is available for the first time at time slot $N$, the
number of tasks having deadline $i$ expiring from $\mathbf{s}$ is more than
that from $\mathbf{s}_{m}$ by $n_{i}-n_{i}^{m}$. Therefore, we have

$\displaystyle
J_{T}\left(\mathbf{s}\right)\big{|}_{N}=J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{N}+C_{p}\sum_{i=1}^{N}\left(n_{i}-n_{i}^{m}\right).$
(114)

The probability that the AMA arrives for the first time at time slot $t$ is
computed as

$\displaystyle P_{t}=p_{u}\left(1-p_{u}\right)^{t}.$ (115)

Also, the probability that the AMA does not arrive within the first $N$ time
slots is

$\displaystyle P_{t\geq N}=\left(1-p_{u}\right)^{N}.$ (116)

From the above logic, $J_{T}\left(\mathbf{s}\right)$ can be expressed in terms
of $J_{T}\left(\mathbf{s}_{m}\right)$ as follows:

$\displaystyle\begin{split}J_{T}\left(\mathbf{s}\right)&=P_{t=0}\left(J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{0}+C_{o}\sum_{i=1}^{N}\left(n_{i}-n_{i}^{m}\right)\right)\\\
&+P_{t=1}\left(J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{1}+C_{o}\sum_{i=2}^{N}\left(n_{i}-n_{i}^{m}\right)+C_{p}\left(n_{1}-n_{1}^{m}\right)\right)\\\
&+\ldots\\\
&+P_{t=N-1}\left(J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{N-1}+C_{o}\left(n_{N}-n_{N}^{m}\right)+C_{p}\sum_{i=1}^{N-1}\left(n_{i}-n_{i}^{m}\right)\right)\\\
&+P_{t\geq N}\left(J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{t\geq
N}+C_{p}\sum_{i=1}^{N}\left(n_{i}-n_{i}^{m}\right)\right).\end{split}$ (117)

$J_{T}\left(\mathbf{s}_{m}\right)$ is the minimum cost averaged over all
cases, hence, can be expressed by

$\displaystyle
J_{T}\left(\mathbf{s}_{m}\right)=\sum_{i=0}^{N-1}P_{t=i}J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{i}+P_{t\geq
N}J_{T}\left(\mathbf{s}_{m}\right)\big{|}_{t\geq N}.$ (118)

In conclusion, with the aid of Eq. (118), the equation (117) can be simplified
to Eq. (25).

###  XI-B Proof of Proposition 2

Given an initial state
$\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)\not\equiv\left(0,\ldots,0\right)$,
and a time horizon $T$. We call $d$ the deadline of the most imminent task of
$\mathbf{s}$, i.e., $d$ is the smallest deadline such that $n_{d}>0$. Denoting
$\tilde{\mathbf{s}}=\left(\tilde{n}_{1},\ldots,\tilde{n}_{N}\right)\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$.
Trivially, we have

$\displaystyle
J_{T}\left(\tilde{\mathbf{s}}\right)=J_{T}\left(\mathbf{s}\right),\text{ if
}N=1.$ (119)

If $N\geq 2$, by definition of set $\mathbb{S}_{pp}\left(\mathbf{s}\right)$,
there must be a deadline $\tilde{d}\in\left\\{d,\ldots,N\right\\}$ such that

$\displaystyle\tilde{n}_{i}=\begin{cases}n_{i},&\text{ if
}i\neq\tilde{d}\text{ and }i\neq d,\\\ n_{d}-1,&\text{ if }i=d,\\\
n_{\tilde{d}}+1,&\text{ if }i=\tilde{d}.\end{cases}$ (120)

If $\tilde{d}=d$, $\mathbf{s}\equiv\tilde{\mathbf{s}}$. It is trivially that

$\displaystyle
J_{T}\left(\tilde{\mathbf{s}}\right)=J_{T}\left(\mathbf{s}\right),\text{ if
}N\geq 2\text{ and }\tilde{d}=d.$ (121)

For the rest of this part, we will prove that

$\displaystyle J_{T}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}\left(\mathbf{s}\right),\text{ when }\tilde{d}\geq d+1,d\leq N-1,N\geq
2.$ (122)

We conduct our proof via induction starting with an initial case.

Initial case: Given $\mathbf{s}=\left(n_{1},\ldots,n_{N}\right)$,
$\tilde{\mathbf{s}}=\left(\tilde{n}_{1},\ldots,\tilde{n}_{N}\right)\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$,
and $T=1$.

  * •

If $n_{1}=0$, $\tilde{n}_{1}=0$ according to Eq. (120). Therefore,

$\displaystyle
J_{1}\left(\tilde{\mathbf{s}}\right)=J_{1}\left(\mathbf{s}\right)=0.$ (123)

  * •

If $n_{1}\geq 1$, $\tilde{n}_{1}=n_{1}-1$ according to Eq. (120). We have

$\displaystyle J_{1}\left(\mathbf{s}\right)$
$\displaystyle=\left(p_{u}C_{o}+\left(1-p_{u}\right)C_{p}\right)n_{1},$ (124)
$\displaystyle J_{1}\left(\tilde{\mathbf{s}}\right)$
$\displaystyle=\left(p_{u}C_{o}+\left(1-p_{u}\right)C_{p}\right)\left(n_{1}-1\right).$
(125)

Therefore,

$\displaystyle J_{1}\left(\tilde{\mathbf{s}}\right)\leq
J_{1}\left(\mathbf{s}\right).$ (126)

The subsequent part is an inductive step.

Inductive step: In this step, we make the following assumption: For every
given state $\mathbf{s}$ and
$\tilde{\mathbf{s}}\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$, the following
holds

$\displaystyle J_{T-1}\left(\tilde{\mathbf{s}}\right)\leq
J_{T-1}\left(\mathbf{s}\right),$ (127)

Initially, we highlight an observation in the following remark.

###### Remark 1

Given two states $\mathbf{s}$ and $\tilde{\mathbf{s}}$ which are assumed to
transit to $\mathbf{s}^{\prime}$ and $\tilde{\mathbf{s}}^{\prime}$ in the next
time slot, respectively, if no offloading is performed. If
$\tilde{\mathbf{s}}\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$ and the number
of tasks having deadline 1 of $\mathbf{s}$ is 0, then,
$\tilde{\mathbf{s}}^{\prime}\in\mathbb{S}_{pp}\left(\mathbf{s}^{\prime}\right)$.

Remark 1 can be proved as follows. Given state $\mathbf{s}$ and
$\tilde{\mathbf{s}}\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$ as above with
$n_{1}=0$. We assume that no offloading is performed, and that $\mathbf{s}$
and $\tilde{\mathbf{s}}$ becomes
$\mathbf{s}_{ds}=\left(n^{ds}_{1},\ldots,n^{ds}_{N}\right)$ and
$\tilde{\mathbf{s}}_{ds}=\left(\tilde{n}^{ds}_{2},\ldots,\tilde{n}^{ds}_{N}\right)$,
respectively, after the deadline shifting, in which

$\displaystyle n^{ds}_{i}=\begin{cases}n_{i+1},&\text{ if }i\neq N,\\\
0,&\text{ if }i=N,\end{cases}$ (128)

and

$\displaystyle\tilde{n}^{ds}_{i}=\begin{cases}n^{ds}_{i},&\text{ if
}i\neq\tilde{d}-1\text{ and }i\neq d-1,\\\ n^{ds}_{d}-1,&\text{ if }i=d-1,\\\
n^{ds}_{\tilde{d}}+1,&\text{ if }i=\tilde{d}-1,\\\ 0,&\text{ if
}i=N.\end{cases}$ (129)

Eqs. (128) and (129) indicate that
$\tilde{\mathbf{s}}_{ds}\in\mathbb{S}_{pp}\left(\mathbf{s}_{ds}\right)$.
Therefore, with the same realizations of task arrival and local processing,
$\mathbf{s}_{ds}$ and $\tilde{\mathbf{s}}_{ds}$ would transit to states
$\mathbf{s}^{\prime}$ and $\tilde{\mathbf{s}}^{\prime}$, respectively, where
$\tilde{\mathbf{s}}^{\prime}\in\mathbb{S}_{pp}\left(\mathbf{s}^{\prime}\right)$.

Based on the emphasized observation above, let us consider the following two
cases:
Case 1: $\mathbf{s}$ is a non-offloading state.
Case 2: The AMA does not presents at the initial time slot, and $n_{1}=0$.

We note that in Case 1, $\mathbf{s}$ is a non-offloading state, implying that
$n_{1}=0$. This is because tasks having deadline 1 are all excessive tasks and
must be offloaded whenever the AMA is available. Applying the DP equation (14)
in Case 1, we have

$\displaystyle J_{T}\left(\mathbf{s}\right)$
$\displaystyle=\mu\sum_{k=0}^{N}p_{k}J_{T-1}\left(\mathbf{s}^{\prime}_{0k}\right)+\left(1-\mu\right)\sum_{k=0}^{N}p_{k}J_{T-1}\left(\mathbf{s}^{\prime\prime}_{0k}\right),$
(130) $\displaystyle J_{T}\left(\tilde{\mathbf{s}}\right)$
$\displaystyle=\mu\sum_{k=0}^{N}p_{k}J_{T-1}\left(\tilde{\mathbf{s}}^{\prime}_{0k}\right)+\left(1-\mu\right)\sum_{k=0}^{N}p_{k}J_{T-1}\left(\tilde{\mathbf{s}}^{\prime\prime}_{0k}\right).$
(131)

Applying Eq. (20) to Case 2 yields

$\displaystyle J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)$
$\displaystyle=\mu\sum_{k=0}^{N}p_{k}J_{T-1}\left(\mathbf{s}^{\prime}_{0k}\right)+\left(1-\mu\right)\sum_{k=0}^{N}p_{k}J_{T-1}\left(\mathbf{s}^{\prime\prime}_{0k}\right),$
(132) $\displaystyle
J_{T}^{\overline{\text{A}}}\left(\tilde{\mathbf{s}}\right)$
$\displaystyle=\mu\sum_{k=0}^{N}p_{k}J_{T-1}\left(\tilde{\mathbf{s}}^{\prime}_{0k}\right)+\left(1-\mu\right)\sum_{k=0}^{N}p_{k}J_{T-1}\left(\tilde{\mathbf{s}}^{\prime\prime}_{0k}\right)..$
(133)

As both Case 1 and Case 2 match the condition mentioned in Remark 1 that
$\tilde{\mathbf{s}}\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$ and $n_{1}=0$,
we have:
$\tilde{\mathbf{s}}^{\prime}_{0k}\in\mathbb{S}_{pp}\left(\mathbf{s}^{\prime}_{0k}\right)$
and
$\tilde{\mathbf{s}}^{\prime\prime}_{0k}\in\mathbb{S}_{pp}\left(\mathbf{s}^{\prime\prime}_{0k}\right)$.
Combining this with our assumption in Eq. (127), we have

$\displaystyle J_{T-1}\left(\tilde{\mathbf{s}}^{\prime}_{0k}\right)\leq
J_{T-1}\left(\mathbf{s}^{\prime}_{0k}\right),$ (134) $\displaystyle
J_{T-1}\left(\tilde{\mathbf{s}}^{\prime\prime}_{0k}\right)\leq
J_{T-1}\left(\mathbf{s}^{\prime\prime}_{0k}\right).$ (135)

Combining Ineqs. (134)-(135) with Eqs. (130)-(131) gives

$\displaystyle J_{T}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}\left(\mathbf{s}\right),\text{ when }\mathbf{s}\text{ is a non-offloading
state.}$ (136)

Combining Ineqs. (134)-(135) with Eqs. (132)-(133) gives

$\displaystyle J_{T}^{\overline{\text{A}}}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right),\text{ when }n_{1}=0.$
(137)

The other case without AMA’s presence is as follows:
Case 3: The AMA does not presents at the initial time slot, and $n_{1}\geq 1$.

In this case, assuming that $\mathbf{s}$ and $\tilde{\mathbf{s}}$ transit to
$\mathbf{s}^{\prime}=\left(n^{\prime}_{1},\ldots,n^{\prime}_{N}\right)$ and
$\tilde{\mathbf{s}}^{\prime}=\left(\tilde{n}^{\prime}_{1},\ldots,\tilde{n}^{\prime}_{N}\right)$
in the next time slot, respectively. Based on Eq. (120), we have

$\displaystyle\tilde{n}^{\prime}_{i}=\begin{cases}n^{\prime}_{i},&\text{ if
}i\neq\tilde{d}-1,\\\ n^{\prime}_{\tilde{d}}+1,&\text{ if
}i=\tilde{d}-1.\end{cases}$ (138)

We note that all tasks having deadline 1 cannot be processed and will expire,
since the deadline shifting happens before the local processing event as
presented in Fig. 2. Therefore, from Eq. (120), there is a fact that after the
first time slot, the number of tasks expiring from $\mathbf{s}$ is more than
that from $\tilde{\mathbf{s}}$ by 1. This observation leads to the following
equation.

$\displaystyle
J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)-J_{T}^{\overline{\text{A}}}\left(\tilde{\mathbf{s}}\right)=C_{p}+J_{T}^{\overline{\text{A}}}\left(\mathbf{s}^{\prime}\right)-J_{T}^{\overline{\text{A}}}\left(\tilde{\mathbf{s}}^{\prime}\right).$
(139)

From Eq. (138), we can also observe that $\tilde{\mathbf{s}}^{\prime}$ only
differs from $\mathbf{s}^{\prime}$ by an additional task having deadline
$\tilde{d}$. Furthermore, $C_{p}$ is the largest cost that can possibly be
incurred by a task. We have the following inequality.

$\displaystyle
C_{p}+J_{T}^{\overline{\text{A}}}\left(\mathbf{s}^{\prime}\right)-J_{T}^{\overline{\text{A}}}\left(\tilde{\mathbf{s}}^{\prime}\right)\geq
0.$ (140)

Applying Ineq. (140) to Eq. (139) gives us

$\displaystyle J_{T}^{\overline{\text{A}}}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)\text{ when }n_{1}\geq 1.$
(141)

From Ineqs. (137) and (141), we have

$\displaystyle J_{T}^{\overline{\text{A}}}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right).$ (142)

Finally, it remains to consider the following case.
Case 4: The AMA presents at the initial time slot, and $\mathbf{s}$ is an
offloading state.

In this case, we consider two contexts in which both are associated with a
time horizon $T$. In the first context, state $\mathbf{s}$ is given initially,
and $L^{*}$ is the corresponding optimal offloading decision. In the second
one, $\tilde{\mathbf{s}}$ is given as an initial state, and task offloading is
done according to a policy $\pi\left(L^{*}\right)$ in the first time slot. The
task offloading decision of policy $\pi\left(L^{*}\right)$ in the first time
slot is defined as follows.

  * •

Situation 1: $L^{*}\geq 1+\sum_{i=1}^{\tilde{d}-1}n_{i}$, then,
$\pi\left(L^{*}\right)$ offloads $L^{*}$ most imminent tasks from
$\tilde{\mathbf{s}}$.

  * •

Situation 2: $0<L^{*}<1+\sum_{i=1}^{\tilde{d}-1}n_{i}$, then,
$\pi\left(L^{*}\right)$ offloads $L^{*}-1$ most imminent tasks, and offloads a
task with deadline $\tilde{d}$ from $\tilde{\mathbf{s}}$.

For the two situations mentioned above, the policy $\pi\left(L^{*}\right)$
guarantees that in both contexts, we arrive at the same state after the
offloading step. For intuition, we consider the following example which
corresponds to Situation 1.

###### Example 9

Given $\mathbf{s}=\left(0,0,5,4,5\right)$ and
$\tilde{\mathbf{s}}=\left(0,0,4,4,6\right)\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$
where $\tilde{d}=5$. Assuming that 12 most imminent tasks are removed from
$\mathbf{s}$ resulting in state $\left(0,0,0,0,2\right)$. Since $12>1+5+4$, we
remove 12 most imminent tasks from $\tilde{\mathbf{s}}$, which also results in
state $\left(0,0,0,0,2\right)$.

The next example corresponding to Situation 2 is as follows.

###### Example 10

Given $\mathbf{s}=\left(0,0,5,1,1\right)$ and
$\tilde{\mathbf{s}}=\left(0,0,4,1,2\right)\in\mathbb{S}_{pp}\left(\mathbf{s}\right)$
where $\tilde{d}=5$. Assuming that 5 most imminent tasks are removed from
$\mathbf{s}$ resulting in state $\left(0,0,0,1,1\right)$. Since $0<5<1+5+1$,
we remove $5-1=4$ most imminent tasks, and a task with deadline $\tilde{d}=5$
from $\tilde{\mathbf{s}}$, which also gives state $\left(0,0,0,1,1\right)$.

With the AMA’s availability, we denote
$J_{T,\pi}^{\text{A}}\left(\tilde{\mathbf{s}}\right)$ the minimum average cost
associated with state $\tilde{\mathbf{s}}$ and time horizon $T$ given that the
task offloading is done according to policy $\pi\left(L^{*}\right)$ at the
initial time slot. Since in both contexts described above, we arrive at the
same state after the task offloading step by offloading the same number of
tasks, we have the following equality

$\displaystyle
J_{T,\pi}^{\text{A}}\left(\tilde{\mathbf{s}}\right)=J_{T}^{\text{A}}\left(\mathbf{s}\right).$
(143)

Trivially, $J_{T}^{\text{A}}\left(\tilde{\mathbf{s}}\right)\leq
J_{T,\pi}^{\text{A}}\left(\tilde{\mathbf{s}}\right)$. Thus, we have

$\displaystyle J_{T}^{\text{A}}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}^{\text{A}}\left(\mathbf{s}\right).$ (144)

We recall the following expression:

$\displaystyle
J_{T}\left(\mathbf{s}\right)=p_{u}J_{T}^{\text{A}}\left(\mathbf{s}\right)+\left(1-p_{u}\right)J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)\text{
for every state }\mathbf{s}.$ (145)

Combining Ineqs. (142) and (144) with (145) gives us

$\displaystyle J_{T}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}\left(\mathbf{s}\right),\text{ when }\mathbf{s}\text{ is an offloading
state.}$ (146)

Ineqs. (136) and (146) lead us to the following inequality

$\displaystyle J_{T}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}\left(\mathbf{s}\right).$ (147)

Combining Ineq. (147) with the presented Initial case allows us to conclude
that

$\displaystyle J_{T}\left(\tilde{\mathbf{s}}\right)\leq
J_{T}\left(\mathbf{s}\right),\text{ for every state }\mathbf{s}\text{ and
}\tilde{\mathbf{s}}\in\mathbb{S}_{pp}\left(\mathbf{s}\right).$ (148)

###  XI-C Proof of Proposition 3

Given a time horizon $T$, if $\mathbf{s}_{a}$ is a non-offloading state, the
corresponding optimal offloading decision is 0, thus,

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s}_{a},0\right)<J_{T}^{\text{A}}\left(\mathbf{s}_{a},1\right).$
(149)

From Eq. (40), the above inequality is equivalent to

$\displaystyle
J_{T}^{\overline{\text{A}}}\left(\mathbf{s}_{a}\right)<J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)+C_{o}.$
(150)

Here, we have $\mathbf{s}_{a}\in\mathbb{S}_{adj}\left(\mathbf{s}\right)$.
According to Theorem 1, if $\mathbf{s}_{a}$ is a non-offloading state,
$\mathbf{s}$ is also a non-offloading state. Hence, trivially, we have

$\displaystyle J_{T}^{\text{A}}\left(\mathbf{s}_{a}\right)$
$\displaystyle=J_{T}^{\overline{\text{A}}}\left(\mathbf{s}_{a}\right),$ (151)
$\displaystyle J_{T}^{\text{A}}\left(\mathbf{s}\right)$
$\displaystyle=J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right).$ (152)

Combining Eqs. (151) and (152) with Eq. (18) and Ineq. (150), we have

$\displaystyle
J_{T}\left(\mathbf{s}_{a}\right)-J_{T}\left(\mathbf{s}\right)<C_{o}.$ (153)

We make a conclusion at this point that: For two states $\mathbf{s}$ and
$\mathbf{s}_{a}\in\mathbb{S}_{adj}\left(\mathbf{s}\right)$, if
$\mathbf{s}_{a}$ is a non-offloading state, Ineq. (153) holds.

Now, we will prove the reverse in which there are two states $\mathbf{s}$ and
$\mathbf{s}_{a}\in\mathbb{S}_{adj}\left(\mathbf{s}\right)$, and the inequality
(153) holds. We assume, in contradict, that $\mathbf{s}_{a}$ is an offloading
state. By applying Eq. (18) to Ineq. (153), we have

$\displaystyle
p_{u}\left(J_{T}^{\text{A}}\left(\mathbf{s}_{a}\right)-J_{T}^{\text{A}}\left(\mathbf{s}\right)\right)+\left(1-p_{u}\right)\left(J_{T}^{\overline{\text{A}}}\left(\mathbf{s}_{a}\right)-J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)\right)<C_{o}.$
(154)

We denote $L_{a}^{*}\geq 1$ the optimal offloading decision of
$\mathbf{s}_{a}$. From Theorem 1, the optimal offloading decision of
$\mathbf{s}$ would be $L_{a}^{*}-1$. Combining this with Eq. (38), we have

$\displaystyle J_{T}^{\text{A}}\left(\mathbf{s}_{a}\right)$
$\displaystyle=J_{T}^{\text{A}}\left(\mathbf{s}_{a},L_{a}^{*}\right)=J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{a1L_{a}^{*}},0\right)+L_{a}^{*}C_{o},$
(155) $\displaystyle J_{T}^{\text{A}}\left(\mathbf{s}\right)$
$\displaystyle=J_{T}^{\text{A}}\left(\mathbf{s},L_{a}^{*}-1\right)=J_{T}^{\text{A}}\left(\bar{\mathbf{s}}_{1\left(L_{a}^{*}-1\right)},0\right)+\left(L_{a}^{*}-1\right)C_{o},$
(156)

where state $\bar{\mathbf{s}}_{a1L_{a}^{*}}$ is obtained by offloading
$L_{a}^{*}$ most imminent tasks from $\mathbf{s}_{a}$, and
$\bar{\mathbf{s}}_{1\left(L_{a}^{*}-1\right)}$ is obtained by offloading
$L_{a}^{*}-1$ most imminent tasks from $\mathbf{s}$.

We recall that

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s},L\right)=\mathcal{C}^{\text{A}}\left(\mathbf{s},L\right)+G_{T}^{\text{A}}\left(\mathbf{s},L\right)$
(157)

denotes the minimum average cost attained over $T$ time slots by offloading
$L$ most imminent tasks from $\mathbf{s}$ given the AMA’s availability. From
the definition of adjacent states in Definition 4, we have that
$\bar{\mathbf{s}}_{a1L_{a}^{*}}\equiv\bar{\mathbf{s}}_{1\left(L_{a}^{*}-1\right)}$.
As a result,

$\displaystyle
J_{T}^{\text{A}}\left(\mathbf{s}_{a}\right)-J_{T}^{\text{A}}\left(\mathbf{s}\right)=C_{o}.$
(158)

Combining the above equality with Ineq. (154), we have

$\displaystyle
J_{T}^{\overline{\text{A}}}\left(\mathbf{s}_{a}\right)-J_{T}^{\overline{\text{A}}}\left(\mathbf{s}\right)<C_{o}.$
(159)

Using the fact that $\mathbf{s}$ is obtained by offloading the most imminent
task from $\mathbf{s}_{a}$, the above inequality can be re-written as

$\displaystyle
J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{a10}\right)<J_{T}^{\overline{\text{A}}}\left(\bar{\mathbf{s}}_{a11}\right)+C_{o},$
(160)

in which state $\bar{\mathbf{s}}_{a10}$ and $\bar{\mathbf{s}}_{a11}$ are
obtained by offloading 0 task, and offloading the most imminent task from
$\mathbf{s}_{a}$, respectively. From the definition of function
$F^{\overline{\text{A}}}$ in Eq. (28), the above inequality is equivalent to

$\displaystyle
F^{\overline{\text{A}}}\left(T,\mathbf{s}_{a},1,0\right)<F^{\overline{\text{A}}}\left(T,\mathbf{s}_{a},1,1\right).$
(161)

Now, combining Ineq. (161) with the convexity of function
$F^{\overline{\text{A}}}$ presented in Lemma 3, we have

$\displaystyle
F^{\overline{\text{A}}}\left(T,\mathbf{s}_{a},1,0\right)<F^{\overline{\text{A}}}\left(T,\mathbf{s}_{a},1,L\right)+LC_{o},\text{
for all }L\in\mathbb{L}_{1}\left(\mathbf{s}_{a}\right).$ (162)

This suggests that 0 is the optimal offloading decision associated with state
$\mathbf{s}_{a}$ for the given time horizon $T$, which is contradict to our
assumption that $\mathbf{s}_{a}$ is an offloading state. Therefore, we can
make a conclusion that: As Ineq. (153) holds, $\mathbf{s}_{a}$ is a non-
offloading state.

To this end, the following has been proved: For two states $\mathbf{s}$ and
$\mathbf{s}_{a}\in\mathbb{S}_{adj}\left(\mathbf{s}\right)$, state
$\mathbf{s}_{a}$ is a non-offloading state if and only if Ineq. (153) holds.
As a consequence, $\mathbf{s}_{a}$ is an offloading state if and only if
$J_{T}\left(\mathbf{s}_{a}\right)-J_{T}\left(\mathbf{s}\right)\geq C_{o}$.

## References

  * [1] 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.
  * [2] H. T. Dinh, C. Lee, D. Niyato, and P. Wang, “A survey of mobile cloud computing: architecture, applications, and approaches,” _Wireless communications and mobile computing_ , vol. 13, no. 18, pp. 1587–1611, 2013.
  * [3] G. Fragkos, E. E. Tsiropoulou, and S. Papavassiliou, “Artificial intelligence enabled distributed edge computing for internet of things applications,” in _2020 16th international conference on distributed computing in sensor systems (DCOSS)_. IEEE, May 2020, pp. 450–457.
  * [4] P. Teymoori, T. D. Todd, D. Zhao, and G. Karakostas, “Efficient mobile computation offloading with hard task deadlines and concurrent local execution,” in _GLOBECOM 2020-2020 IEEE Global Communications Conference_. IEEE, 2020, pp. 1–6.
  * [5] Y. Geng, Y. Yang, and G. Cao, “Energy-efficient computation offloading for multicore-based mobile devices,” in _IEEE INFOCOM 2018-IEEE Conference on Computer Communications_. IEEE, 2018, pp. 46–54.
  * [6] W. Zhang, Y. Wen, and D. O. Wu, “Collaborative task execution in mobile cloud computing under a stochastic wireless channel,” _IEEE Transactions on Wireless Communications_ , vol. 14, no. 1, pp. 81–93, 2014.
  * [7] H. Huang, Q. Ye, and Y. Zhou, “Deadline-aware task offloading with partially-observable deep reinforcement learning for multi-access edge computing,” _IEEE Transactions on Network Science and Engineering_ , 2021\.
  * [8] 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.
  * [9] D. Van Le and C.-K. Tham, “An optimization-based approach to offloading in ad-hoc mobile clouds,” in _GLOBECOM 2017-2017 IEEE Global Communications Conference_. IEEE, 2017, pp. 1–6.
  * [10] ——, “A deep reinforcement learning based offloading scheme in ad-hoc mobile clouds,” in _IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 2018, pp. 760–765.
  * [11] R. P. Stanley, _Catalan numbers_. Cambridge University Press, 2015.