Two-tier end-edge collaborative computation offloading for edge computing

Abstract

Edge computing has emerged for meeting the ever-increasing computation demands from delay-sensitive Internet of Things (IoT) applications. However, the computing capability of an edge device, including a computing-enabled end user and an edge server, is insufficient to support massive amounts of tasks generated from IoT applications. In this paper, we aim to propose a two-tier end-edge collaborative computation offloading policy to support as much as possible computation-intensive tasks while making the edge computing system strongly stable. We formulate the two-tier end-edge collaborative offloading problem with the objective of minimizing the task processing and offloading cost constrained to the stability of queue lengths of end users and edge servers. We perform analysis of the Lyapunov drift-plus-penalty properties of the problem. Then, a cost-aware computation offloading (CACO) algorithm is proposed to find out optimal two-tier offloading decisions so as to minimize the cost while making the edge computing system stable. Our simulation results show that the proposed CACO outperforms the benchmarked algorithms, especially under various number of end users and edge servers.

Keywords

Edge computing computation offloading collaborative offloading Lyapunove drift theory queue stability

1. Introduction

With the surging applications of Internet of Things (IoT), e.g., smart grid, industrial automation, and so on, the requirements for high performance computing with low latency increase exponentially [1, 2]. Edge computing is a promising computing paradigm for the ever-increasing demands of these IoT applications. By deploying computing-enabled devices, including computing-enabled end users (e.g., intelligent terminals in smart grid) and edge servers [3, 4], at the network edge close to data source, the computation tasks could be performed quickly, since task upload delay in edge computing could be explicitly reduced in comparison with cloud computing.

However, due to the fact that, first, the computation resource of an edge device is quite smaller in comparison with a cloud, second, there are massive amounts of tasks generated from IoT applications over time and over space, task process at only a single edge device may be low efficient [5, 6]. Therefore, computation offloading, which allocates tasks among computing devices, would be more feasible. Recently, a few existing literature have come up with computation offloading algorithms [7, 5, 8]. Liu et al. in [7] explored the trade off between latency and reliability in task offloading in a mobile edge computing environment. Guo et al. in [5] considered offloading decisions among IoT devices and neighboring edge servers for energy efficiency. Chalapathi et al. in [8] has studied the task assignment problem in a multi-cloudlet network connected via a wireless software-defined networking (SDN) network for reducing the task latency. However, most of proposals are one-tier offloading policies. That is, they only make offloading decision at the lowest layer of an edge computing system. The collaboration of end user and edge server, edge server and edge server is not fully explored for edge computing capability maximization.

Indeed, computing capability of an end user is far smaller than that of an edge server, for example, one end user process one task per time while an edge server can process multiple tasks in parallel [1]. However, an end user is closer to data source than an edge server. Besides, task generated from end users are typically based on the usage of the users, the task generation rate from different users will be non-independent and identical distribution (non-IID). Some end users and edge servers closer to those busy end users would be heavily loaded while others may be idle. Therefore, a two-tier end-edge collaborative offloading, where the end user makes the first-tier offloading to demonstrate whether to compute the task locally or to offload it to the closest edge server, which makes the second-tier offloading decision on whether needs to further offload the task to a neighbor edge server, is deserved study for maximizing the resource utility of an edge computing system. However, at the same time, considering the heterogeneous computing capability and distinct processing and offloading cost of end users and edge servers, it becomes a challenging issue: how to make a two-tier offloading decisions in end users and edge servers in sequence for arrival tasks to satisfy the one-shot performance objective?

In this paper, our main objective is to minimize the cost of task processing and offloading while make the queues of both end users and edge servers stable. How to find the one-shot optimum two-tier offloading policies that minimizes the cost of task processing and offloading while making all distributed queues stable is studied in this paper. We first formulate the two-tier end-edge collaborative offloading problem with the goal of cost minimization, constrained to the stability of all queues, including queues of end users and edge servers in the edge computing system. Then, the Lyapunov drift-plus-penalty properties of the problem was dissected, where the drift is the queue vector and the penalty is the cost. In terms of the theoretical results, a two-tier cost-aware computation offloading (CACO) algorithm is proposed to achieve the one-shot objective of cost minimization with queue stability. The simulation studies have conclusively proved that our proposal is effective.

The remainder of this paper is organized as follows. Section 2 gives an overall description of the system, task offloading and queuing as well as cost models. The problem is then formulated and solved in Section 3. Section 4 carry out simulations which illustrate the advantage of the proposed algorithm. This paper is concluded in Section 5.

2. Model description

2.1 System model

This paper considers an edge computing network formed a set of end-users (e.g., smart grid terminals) and a set of edge servers, which are represented by $\mathcal{K}=\{1,2,\ldots,K\}$ and $\mathcal{N}=\{1,2,\ldots,N\}$ separately. The end users and edge servers are randomly distributed over the entire network. The end user generates computation-intensive tasks that are independently and identically distributed (i.i.d) over time. However, the task generation rate among end users are independent and could be non-identical.

As illustrated in Fig. 1, a two-tier computation offloading decision is considered. For any task, the end user that generates it makes the first-tier decision on whether to compute the task locally or offload it to the primary edge server, where the primary edge server refers to the edge server that has the shortest communication distance from that end user. If offloading, then the primary edge server would make the second-tier decision on local computing or offloading to a neighbor edge. Accordingly, all users who choose the $n$ th edge server as their primary edge server form a set $\mathcal{K}_{n}=\{1,2,\ldots,K_{n}\}$ , $\sum_{n=1}^{N}K_{n}=K$ .

Figure 1.

Two-tier offloading model.

Assume that end users and edge servers have distinct task service capabilities. Let $R_{n,k}^{\textsf{M}}$ and $R_{n}^{\textsf{E}}$ ([tasks/slot]) be the task processing rate of the $k$ th end user in $\mathcal{K}_{n}$ and the $n$ th edge server, respectively. Thus, $R_{n,k}^{\textsf{M}}<R_{n}^{\textsf{E}}$ holds.

2.2 Task offloading and queuing model

Consider a system which is time-slotted and indexed by $T=\{1,2,\ldots,t,\ldots\}$ , where the length of each time slot is $\Delta t$ . The system is idle while both end users queue’ and edge servers’ queue are empty when $t\leqslant 0$ .

Let $A_{n,k}(t)=\{0,1\}$ be a tasks generation indicator at the $k$ th end user whose primary edge server is $n$ during time interval $[t,t+1)$ . $A_{n,k}(t)=1$ indicates there is a task; $A_{n,k}(t)=0$ , otherwise. The corresponding task generation rate is defined as $\lambda_{n,k}=\mathbb{E}[A_{n,k}(t)]$ . Denote $I_{n,k}(t)=\{0,1\}$ as the first-tier binary computation decision variable for the task generated in time slot $t$ . When it determines to local computing, we have $I_{n,k}(t)=0$ ; $I_{n,k}(t)=1$ , otherwise. Let $\gamma_{n,k}(t)=\{n,\mathcal{N}_{n^{-}}\}$ be an offloading decision variable of edge server $n$ for the tasks arrived from the $k$ th user in slot $t$ , where $\mathcal{N}_{n^{-}}$ is the subset of $\mathcal{N}$ that excludes $n$ . When $\gamma_{n,k}(t)=n$ , the task is computed in the primary edge server. Otherwise, $\gamma_{n,k}(t)=n^{\prime}$ where $n^{\prime}\in\mathcal{N}_{n^{-}}$ indicates that, the task will be offloaded to the $n^{\prime}$ th edge server for computing. We consider that each user as well as edge server maintains a virtual queue.

The queue evolution of the $k$ th user for $k\in\mathcal{K}_{n}$ is expressed as follows.

$\displaystyle Q_{n,k}^{\textsf{M}}(t+1)=\max\left[Q_{n,k}^{\textsf{M}}(t)+A_{n% ,k}(t)(1-I_{n,k}(t))-R_{n,k}^{\textsf{M}},0\right].$ (1)

The queue evolution of the $n$ th edge server is expressed as follows.

$\displaystyle Q_{n}^{\textsf{E}}(t)=\max\left[Q_{n}^{\text{E}}(t)+A_{n}^{% \textsf{M}}(t)+A_{n}^{\textsf{O}}(t)-R_{n}^{\textsf{E}},0\right],$ (2)

where $A_{n}^{\textsf{M}}(t)$ is the amount of task offloaded from end users, which is derived by

$\displaystyle A_{n}^{\textsf{M}}(t)=\sum_{k=1}^{K_{n}}A_{n,k}(t)I_{n,k}(t){1}(% \gamma_{n,k}=n),$ (3)

where ${1}(X)=1$ if $X$ is true; ${1}(X)=0$ , otherwise.

$A_{n}^{\textsf{O}}(t)$ is the amount of task offloaded from other edge servers, which is calculated by

$\displaystyle A_{n}^{\textsf{O}}(t)=\sum_{i=1,i\neq n}^{N}\sum_{j=1}^{K_{i}}A_% {i,j}(t)I_{i,j}(t){1}(\gamma_{i,j}=n).$ (4)

2.3 Local processing and offloading cost

2.3.1 First-tier local task processing at end user

Generally, the long the queue length, the long queueing delay a task experiences, and the cost would also increase with the increasing queuing delay. Accordingly, we define the cost of local processing at an end user as the following

$\displaystyle\mathcal{C}_{n,k}^{\textsf{1st-L}}(t)=\alpha(A_{n,k}(t))^{2}Q_{n,% k}^{\text{M}}(t)(1-I_{n,k}(t)),$ (5)

where $\alpha>0$ is a cost factor.

2.3.2 First-tier offloading

When a task is determined to offload, it has to be uploaded from the data source to one-hop distant primary edge server, which consumes transmission resource. Accordingly, we denote the cost of first-tier offloading as

$\displaystyle\mathcal{C}^{\textsf{1st-O}}_{n,k}(t)=\beta A_{n,k}(t)I_{n,k}(t),$ (6)

where $\beta>0$ is a cost factor.

2.3.3 Second-tier offloading

Generally, the less time of offloading, the less waste of network transmission resource. However, if the workload of the primary edge server are too heavy, the offloaded tasks may experience intolerable queuing delay. In this case, second-tier offloading would be a good choice. Accordingly, we define the cost of second-tier offloading to edge server $n^{\prime}$ from primary edge server $n$ as the following

$\displaystyle\mathcal{C}^{\textsf{2nd-O}}_{n^{\prime},(n,k)}(t)=\sigma_{o}A_{n% ,k}(t)I_{n,k}(t)Q_{n^{\prime}}^{\text{E}}(t){1}(\gamma_{n,j}(t)=n^{\prime}),$ (7)

where $\sigma_{o}>0$ is a cost factor.

We also denote the cost of local processing at primary edge server $n$ as the following

$\displaystyle\mathcal{C}^{\textsf{2nd-L}}_{n^{\prime},(n,k)}(t)=\sigma_{p}A_{n% ,k}(t)I_{n,k}(t)Q_{n}^{\text{E}}(t){1}(\gamma_{n,j}(t)=n),$ (8)

where $\sigma_{p}$ is a cost factor.

3. Proposed algorithm

3.1 Problem formulation

The cost of the task $A_{n,k}(t)$ generated from the $k$ th end user where $k\in\mathcal{K}_{n}$ in slot $t$ is expressed as

$\displaystyle\mathcal{C}_{n,k}(t)=\mathcal{C}_{n,k}^{\textsf{1st-L}}(t)+% \mathcal{C}^{\textsf{1st-O}}_{n,k}(t)+\mathcal{C}_{n^{\prime},(n,k)}^{\textsf{% 2nd-L}}(t)+\sum_{n^{\prime}=1,n^{\prime}\neq n}^{N}\mathcal{C}^{\textsf{2nd-O}% }_{n^{\prime},(n,k)}(t).$ (9)

This paper aims to find out the optimal two-tier offloading decisions $I^{*}=(I_{n,k}^{*}:n\in\mathcal{N},k\in\mathcal{K}_{n})$ , $\gamma^{*}=(\gamma_{n,k}^{*}:n\in\mathcal{N},k\in\mathcal{K}_{n})$ to minimize the long term cost under the constrains of the queue stability. Thus, the problem is formulated as

Minimize:

$\displaystyle\mathcal{C}_{I^{*},\gamma^{*}}=\lim_{T\rightarrow\infty}\frac{1}{% T}\sum_{t=1}^{T}\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}\mathcal{C}_{n,k}(t)$ (10)

Subject to:

$\displaystyle(1)-(9)$ (11) $\displaystyle\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}\lambda_{n,k}\leqslant\sum_{n=1}^% {N}\sum_{k=1}^{K_{n}}R_{n,k}^{\textsf{M}}+\sum_{n=1}^{N}R_{n}^{\textsf{E}}$ (12) $\displaystyle\mathbb{E}[Q_{n,k}^{\textsf{M}}(t)]\!\!=\!\!\lim_{T\rightarrow% \infty}\frac{1}{T}\sum_{t=1}^{T}Q_{n,k}^{\textsf{M}}(t)\!\!<\!\!\infty,\forall n% \!\!\in\!\!\mathcal{N},k\!\!\in\mathcal{K}_{n}$ (13) $\displaystyle\mathbb{E}[Q_{n}^{\textsf{E}}(t)]=Q_{n}^{\textsf{E}}(t)<\infty,% \forall n\in\mathcal{N}$ (14) $\displaystyle I_{n,k}(t)\in\{0,1\},\forall n\in\mathcal{N},k\in\mathcal{K}_{n}$ (15) $\displaystyle\gamma_{n,k}(t)\in\{n,\mathcal{N}_{n^{-}}\},\forall n\in\mathcal{% N},k\in\mathcal{K}_{n}$ (16) $\displaystyle\sum_{n=1}^{N}K_{n}=K$ (17)

where Eq. (10) follows Eq. (9); Eq. (12) is the constraint of system stability, where $\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}\lambda_{n,k}$ is the total task generation rate, $\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}R_{n,k}^{\textsf{M}}$ and $\sum_{n=1}^{N}R_{n}^{\textsf{E}}$ are the total task processing rate at all end users and edge servers, respectively; Eqs (13) and (14) are queue stability of the end user and edge server, respectively; Eq. (15) is the constraint of the first-tier offloading decision variable; Eq. (16) is the constraint of the second-tier offloading decision variable.

3.2 Lyapunov drift-plus penalty

Let $Q(t)=\left(Q_{1,1}^{\textsf{M}}(t),\ldots,Q_{N,K_{N}}^{\textsf{M}}(t),Q_{1}^{% \textsf{E}}(t),\ldots,Q_{N}^{\textsf{E}}(t)\right)$ be the queue-length vector of $K$ end users and $N$ edge servers in slot $t$ . Similar to [9, 10], we define the Lyapunov function of the queue length as the following

$\displaystyle L(t)\triangleq\frac{1}{2}\left[\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q% _{n,k}^{\textsf{M}}(t)^{2}+\sum_{n=1}^{N}Q_{n}^{\textsf{E}}(t)^{2}\right].$ (18)

The one-step conditional Lyapunov drift is calculated by

$\displaystyle\Delta L(t)\triangleq\mathbb{E}\left[L(t+1)-L(t)|Q(t)\right].$ (19)

.

Every slot $t$ , the Lyapunov drift satisfies the following inequality regardless of the value of $Q(t)$ and the two-tier offloading policy.

where $B$ is a finite constant.

Proof..

According to Eq. (1), we have

$\displaystyle Q_{n,k}^{\textsf{M}}(t+1)^{2}-Q_{n,k}^{\textsf{M}}(t)^{2}% \leqslant\left(Q_{n,k}^{\textsf{M}}(t)+A_{n,k}(t)(1-I_{n,k}(t))-R_{n,k}^{% \textsf{M}}\right)^{2}-Q_{n,k}^{\textsf{M}}(t)^{2}=\left(A_{n,k}(t)(1-I_{n,k}(% t))-R_{n,k}^{\textsf{M}}\right)^{2}{}+2Q_{n,k}^{\textsf{M}}(t)\left(A_{n,k}(t)% (1-I_{n,k}(t))-R_{n,k}^{\textsf{M}}\right).$ (21)

Similarly, according to Eq. (2), we have

$\displaystyle Q_{n}^{\textsf{E}}(t+1)^{2}-Q_{n}^{\textsf{E}}(t)^{2}\leqslant% \left(Q_{n}^{\textsf{E}}(t)+A_{n}^{\textsf{M}}(t)+A_{n}^{\textsf{O}}(t)-R_{n}^% {\textsf{E}}\right)^{2}-Q_{n}^{\textsf{E}}(t)^{2}=\left(A_{n}^{\textsf{M}}(t)+% A_{n}^{\textsf{O}}(t)-R_{n}^{\textsf{E}}\right)^{2}+2Q_{n}^{\textsf{E}}(t)% \left(A_{n}^{\textsf{M}}(t)+A_{n}^{\textsf{O}}(t)-R_{n}^{\textsf{E}}\right).$ (22)

Substituting Eqs (21) and (22) into Eq. (19), we have

$\displaystyle\Delta L(t)\leqslant\frac{1}{2}\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}% \mathbb{E}\left[\left(A_{n,k}(t)(1-I_{n,k}(t))-R_{n,k}^{\textsf{M}}\right)^{2}% |Q(t)\right]{}+\frac{1}{2}\sum_{n=1}^{N}\mathbb{E}\left[\left(A_{n}^{\textsf{M% }}(t)+A_{n}^{\textsf{O}}(t)-R_{n}^{\textsf{E}}\right)^{2}|Q(t)\right]{}+\sum_{% n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n,k}^{\textsf{M}}(t)\mathbb{E}\left[A_{n,k}(t)(1-% I_{n,k}(t))-R_{n,k}^{\textsf{M}}|Q(t)\right]{}+\sum_{n=1}^{N}Q_{n}^{\textsf{E}% }(t)\mathbb{E}\left[A_{n}^{\textsf{M}}(t)+A_{n}^{\textsf{O}}(t)-R_{n}^{\textsf% {E}}|Q(t)\right]$ (23)

Since $0\leqslant A_{n,k}(t)(1-I_{n,k}(t))\leqslant A_{n,k}(t)$ , and $\mathbb{E}[A_{n,k}(t)]=\lambda_{n,k}$ , we have

$\displaystyle\mathbb{E}\left[\left(A_{n,k}(t)(1-I_{n,k}(t))-R_{n,k}^{\textsf{M% }}\right)^{2}|Q(t)\right]\leqslant\text{max}\left[\left(R_{n,k}^{\textsf{M}}% \right)^{2},\left(\lambda_{n,k}-R_{n,k}^{\textsf{M}}\right)^{2}\right].$ (24)

On the otherhand, we have

$\displaystyle\mathbb{E}\left[A_{n}^{M}(t)\right]\leqslant\mathbb{E}\left[\sum_% {k=1}^{K_{n}}A_{n,k}(t)\right]=\sum_{k=1}^{K_{n}}\lambda_{n,k}$

according to Eq. (3). Similarly,

$\displaystyle\mathbb{E}\left[A_{n}^{O}(t)\right]\leqslant\mathbb{E}\left[\sum_% {i=1,i\neq n}^{N}\sum_{j=1}^{K_{i}}A_{i,j}(t)\right]=\sum_{i=1,i\neq n}^{N}% \sum_{j=1}^{K_{i}}\lambda_{i,j}$

holds according to Eq. (4). Therefore,

$\displaystyle\mathbb{E}\left[\left(A_{n}^{\textsf{M}}(t)+A_{n}^{\textsf{O}}(t)% -R_{n}^{\textsf{E}}\right)^{2}|Q(t)\right]\leqslant\text{max}\left[\left(R_{n}% ^{\textsf{E}}\right)^{2},\left(\sum_{k=1}^{K_{n}}\lambda_{n,k}+\sum_{i=1,i\neq n% }^{N}\sum_{j=1}^{K_{i}}\lambda_{i,j}-R_{n}^{\textsf{E}}\right)^{2}\right]=% \text{max}\left[\left(R_{n}^{\textsf{E}}\right)^{2},\left(\sum_{i=1}^{N}\sum_{% j=1}^{K_{i}}\lambda_{i,j}-R_{n}^{\textsf{E}}\right)^{2}\right].$ (25)

Let

$\displaystyle B\triangleq\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}\text{max}\left[\frac% {1}{2}\left(R_{n,k}^{\textsf{M}}\right)^{2},\frac{1}{2}\left(\lambda_{n,k}-R_{% n,k}^{\textsf{M}}\right)^{2}\right]$ $\displaystyle{}+\sum_{n=1}^{N}\text{max}\left[\frac{1}{2}\left(R_{n}^{\textsf{% E}}\right)^{2},\frac{1}{2}\left(\sum_{i=1}^{N}\sum_{j=1}^{K_{i}}\lambda_{i,j}-% R_{n}^{\textsf{E}}\right)^{2}\right]$

and substituting into Eq. (23), we have

$\displaystyle\Delta L(t)\leqslant\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n,k}^{% \textsf{M}}(t)\mathbb{E}\left[A_{n,k}(t)(1-I_{n,k}(t))-R_{n,k}^{\textsf{M}}|Q(% t)\right]{}+\sum_{n=1}^{N}Q_{n}^{\textsf{E}}(t)\mathbb{E}\left[A_{n}^{\textsf{% M}}(t)+A_{n}^{\textsf{O}}(t)-R_{n}^{\textsf{E}}|Q(t)\right]+B.$

Since $R_{n,k}^{\textsf{M}}$ and $R_{n}^{\textsf{E}}$ are independent of $Q(t)$ , $\mathbb{E}\left[R_{n,k}^{\textsf{M}}|Q(t)\right]=R_{n,k}^{\textsf{M}}$ and $\mathbb{E}\left[R_{n}^{\textsf{E}}|Q(t)\right]=R_{n}^{\textsf{E}}$ hold. Therefore,

$\displaystyle\Delta L(t)\leqslant B-\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n,k}^{% \textsf{M}}(t)R_{n,k}^{\textsf{M}}-\sum_{n=1}^{N}Q_{n}^{\textsf{E}}(t)R_{n}^{% \textsf{E}}{}+\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n,k}^{\textsf{M}}(t)\mathbb{E% }\left[A_{n,k}(t)(1-I_{n,k}(t))|Q(t)\right]{}+\sum_{n=1}^{N}Q_{n}^{\textsf{E}}% (t)\mathbb{E}\left[A_{n}^{\textsf{M}}(t)+A_{n}^{\textsf{O}}(t)|Q(t)\right]=B-% \sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n,k}^{\textsf{M}}(t)R_{n,k}^{\textsf{M}}-% \sum_{n=1}^{N}Q_{n}^{\textsf{E}}(t)R_{n}^{\textsf{E}}{}+\sum_{n=1}^{N}\sum_{k=% 1}^{K_{n}}Q_{n,k}^{\textsf{M}}(t)\mathbb{E}\left[A_{n,k}(t)(1-I_{n,k}(t))|Q(t)% \right]{}+\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n}^{\textsf{E}}(t)\mathbb{E}[A_{n% ,k}(t)I_{n,k}(t){1}(\gamma_{n,k}=n)|Q(t)]{}+\sum_{n=1}^{N}\sum_{i=1,i\neq n}^{% N}\sum_{j=1}^{K_{i}}Q_{n}^{\textsf{E}}(t)\mathbb{E}[A_{i,j}(t)I_{i,j}(t){1}(% \gamma_{i,j}=n)|Q(t)]$

∎

Then the statement follows.

The stability of the queues of both users and servers in the system satisfies the inequality in Eq. (20). However, it ignores the cost of task processing and offloading. Therefore, to consider the cost, the Lyapunov drift-plus penalty function is set as $\Delta L(t)+V\mathbb{E}[\mathcal{C}(t)|Q(t)]$ when $Q(t)$ is known, where $\mathcal{C}(t)=\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}\mathcal{C}_{n,k}(t)$ is the penalty function while $V$ is a non-negative control parameter that is relevant to the tradeoff between cost and the steady state of the queues. According to Lemma 1, we have the following lemma.

.

Under any two-tier offloading policy, the Lyapunov drift-plus-penalty satisfies the following for any $Q(t)$ as

$\displaystyle\Delta L(t)+V\mathbb{E}[\mathcal{C}(t)|Q(t)]\leqslant B+V\mathbb{% E}[\mathcal{C}(t)|Q(t)]-\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n,k}^{\textsf{M}}(t% )R_{n,k}^{\textsf{M}}{}-\sum_{n=1}^{N}Q_{n}^{\textsf{E}}(t)R_{n}^{\textsf{E}}+% \sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n,k}^{\textsf{M}}(t)\mathbb{E}\left[A_{n,k}% (t)(1-I_{n,k}(t))|Q(t)\right]{}+\sum_{n=1}^{N}\sum_{k=1}^{K_{n}}Q_{n}^{\textsf% {E}}(t)\mathbb{E}[A_{n,k}(t)I_{n,k}(t){1}(\gamma_{n,k}(t)=n)|Q(t)]{}+\sum_{n=1% }^{N}\sum_{i=1,i\neq n}^{N}\sum_{j=1}^{K_{i}}Q_{n}^{\textsf{E}}(t)\mathbb{E}[A% _{i,j}(t)I_{i,j}(t){1}(\gamma_{i,j}(t)=n)|Q(t)]$ (26)

where $B$ is the same constant used in Lemma 1.

[b] CACO Initialization: $Q(0)=0$ .

Every slot $t\geqslant 0$ , do

End user side:for $k\in\mathcal{K}_{n}$ , $n\in\mathcal{N}$ , do

Observe $A_{n,k}(t)$ , $Q(t)$

First-tier offloading decision:Choose $I_{n,k}^{*}(t)$ to minimize

$\displaystyle V\mathcal{C}_{n,k}(t)+Q_{n,k}^{\text{M}}(t)A_{n,k}(t)(1-I_{n,k}(% t))$ $\displaystyle{}+Q_{n}^{\text{E}}(t)A_{n,k}(t)I_{n,k}(t){1}(\gamma_{n,k}(t)=n)$ $\displaystyle{}+\sum_{n^{\prime}=1,n^{\prime}\neq n}^{N}Q_{n^{\prime}}^{\text{% E}}(t)A_{n,k}(t)I_{n,k}(t){1}(\gamma_{n,k}(t)=n^{\prime})$

where $\gamma_{n,k}(t)$ satisfies

$\displaystyle\gamma_{n,k}(t)=\text{min}[V(\mathcal{C}_{n^{\prime},(n,k)}^{% \text{2nd-L}}(t)+\mathcal{C}_{n^{\prime},(n,k)}^{\text{2nd-O}}(t)){}+Q_{n}^{% \text{E}}(t)A_{n,k}(t){1}(\gamma_{n,k}(t)=n){}+\sum_{n^{\prime}=1,n^{\prime}% \neq n}^{N}Q_{n^{\prime}}^{\text{E}}(t)A_{n,k}(t)){1}(\gamma_{n,k}(t)=n^{% \prime})]$

Processing and queue update: Locally process the tasks and update queue according to Eq. (1).

Edge server side:for $n\in\mathcal{N}$ , if the server receives tasks from the $k$ th end user (which indicates that $I_{n,k}^{*}(t)=1$ ), do

Observe $Q(t)$

Second-tier offloading decision:Choose $\gamma_{n,k}^{*}(t)$ to minimize

$\displaystyle V(\mathcal{C}_{n^{\prime},(n,k)}^{\text{2nd-L}}(t)+\mathcal{C}_{% n^{\prime},(n,k)}^{\text{2nd-O}}(t))$ $\displaystyle{}+Q_{n}^{\text{E}}(t)A_{n,k}(t){1}(\gamma_{n,k}=n)$ $\displaystyle{}+\sum_{n^{\prime}=1,n^{\prime}\neq n}^{N}Q_{n^{\prime}}^{\text{% E}}(t)A_{n,k}(t)){1}(\gamma_{n,k}=n^{\prime})$

Processing and queue update: Process the tasks and update queue according to Eq. (2).

Lemma 2 follows by subtracting $V\mathbb{E}[\mathcal{C}(t)|Q(t)]$ into Lemma 1 from both sides.

3.3 CACO

Base on Lyapunov drift theory [9], when the Lyapunov drift-plus-penalty term $\Delta L(t)+V\mathbb{E}[\mathcal{C}(t)|Q(t)]$ described in inequality Eq. (26) is controlled towards negative, the queue $Q(t)$ would be stable while the optimal $\mathcal{C}=\mathbb{E}[\mathcal{C}(t)]$ is able to be approximated. Hence, derived from the results of Lemmas 1 and 2, we propose a cost-aware computation offloading (CACO) algorithm to figure out a sequential optimal two-tier offloading decisions $I^{*}(t)$ and $\gamma^{*}(t)$ for $t=1,2,\ldots,\infty$ in order to minimize the bound on the right-hand side of inequality Eq. (26) at each slot, so that the bound on $\Delta L(t)+V\mathbb{E}[\mathcal{C}(t)|Q(t)]$ can be minimized.

4. Performance evaluation

In section, the efficiency of the proposed CACO algorithm is evaluated. The default parameter settings are as follows: $N=3$ ; $K=50$ ; The $K$ number of end users and randomly and uniformly distributed around the $N$ edge servers. The expected computing rate of end users and edge servers are $R^{\text{M}}=1$ task/slot/end-user and $R^{\text{E}}=3$ tasks/slot/edge-server, respectively. Let $R_{\text{sum}}=\sum_{k=1}^{K}R_{k}^{\text{E}}+\sum_{n=1}^{N}R^{\text{E}}$ tasks/slot be the system capacity, then the normalized arrival rate is defined as $\lambda=\sum_{k=1}^{K}\lambda_{k}/R_{\text{sum}}$ , where $\lambda_{k}=\mathbb{E}[A_{k}(t)]$ tasks/slot. We take $\lambda=0.8$ . We take $\alpha=\sigma_{p}=1$ , $\beta=\sigma_{o}=2$ . The results are averaged over 10 different runs per scenario with 10,000 slots/run via Matlab simulator,all parameters show in Table 1.

Table 1
The main parameters and variables of evaluation

Name	Value
Edge servers N	3
End users K	50
Computing rate of end users $R^{\text{M}}$	1 task/slot/end-user
Computing rate of edge servers $R^{\text{E}}$	3 tasks/slot/edge-server
System capacity $R_{\text{sum}}$	1
Normalized arrival rate $\lambda$	0.8
Cost factor $\alpha,\sigma_{p},\beta,\sigma_{o}$	$\alpha=\sigma_{p}=1$ , $\beta=\sigma_{o}=2$

Figure 2.

The effect of $V$ on cost performance and queue stability.

Figure 2 evaluates the tradeoff between the queue length and the cost under CACO algorithm with control parameter $V$ . As illustrated in Fig. 2, when $V=0$ , the algorithm degenerates into a queue length based Lyapunov computation offloading policy. Thus, the average queue length of the system is the lowest in contrast to those under $V>0$ . When $V>0$ , the cost decreases quickly while the value of $V$ rises due to Lyapunov drift-plus-penalty, in tradeoff the increasing queue length. However, when the value of $V$ is relatively large (e.g., $V>50$ ), the cost-queue length tradeoff reaches a balance state.

Figure 3.

Cost performance, $\lambda=$ 0.9, $K=$ 50, and 5 primary edge servers.

Figure 4.

Cost performance, $[K_{2},K_{3},K_{4},K_{5}]=[7,12,9,12]$ .

To appraise the efficiency of the CACO algorithm in the aspects of cost efficiency and queue stability, we compare the performance of CACO with two benchmarked algorithms, including one-tier offload and queue-length-minimization greedy (queGreedy), which are variant offloading algorithms from reference [11]. Specifically, in one-tier offload, we only consider the collaboration among end users and their primary edge servers. That is, the task offloaded to a primary edge server is not allowed to further offload to other edge servers for computing. Under one-tier offload, $I_{n,k}(t)={1}(Q_{n}^{\text{E}}<Q_{n,k}^{\text{M}}(t))$ . Under queGreedy, $I_{n,k}(t)={1}(Q_{n}^{\text{E}}<Q_{n,k}^{\text{M}}(t))$ and $\gamma_{n,k}(t)=\text{min}[Q_{n}^{\text{E}}(t):n\in\mathcal{N}]$ .

We first evaluate the adaptation of the proposal to end user-edge server collaboration by fixing the end users of $K=50$ into 5 edge servers and then adding pure edge server (no end user choose it as primary edge server) into the system. Under one-tier offload, the offloading decisions are made between end user and its primary edge server. That is, no task would be offloaded to any pure edge server. Thus, the cost given by one-tier offload does not change with the increasing pure edge server, as shown in Fig. 3. Under queGreedy, the tasks second-tier offloading to pure edge servers increase with the increasing pure edge servers for reducing the queue length of end user and primary edge server, leading to the reduction of cost. By using cost as penalty and applying Lyapunov drift-plus-penalty, the CACO algorithm is more adaptive to end user-edge server two-tier collaboration by providing the lowest cost under various number of pure edge servers in comparison with the benchmarked algorithms, as illustrated in Fig. 3.

Finally, Fig. 4 shows how the number of end users affects the cost performance and thus the offloading decisions of the investigated schemes. Under all investigated algorithms, the cost increases with the increasing number of end users. This is because, the arrival tasks increase with the increasing number of end users. The cost efficiency of the proposed CACO is again illustrated by providing the lowest cost increasing rate and lowest cost under various number of end users, as shown in Fig. 4.

5. Conclusion

This paper has studied the end-edge collaborative computation offloading problem in the background of edge computing. The problem is constructed as a two-tier collaborative offloading problem. By analyzing the Lyapunov drift-plus-penalty properties, a CACO algorithm is put forward, which aims at minimizing the drift-plus-penalty so as to achieve the objective of cost minimization with queue stability. Results of the simulations clearly demonstrated the efficiency of the proposal in enhancing both cost efficiency and queue stability.

References

Guo

Guan

Chen

Peng

. Delay-Optimal Scheduling of VMs in a Queueing Cloud Computing System with Heterogeneous Workloads. IEEE Transactions on Services Computing. 2019; 1–1.

Premsankar

Di Francesco

Taleb

. Edge computing for the internet of things: A case study. IEEE Internet of Things Journal. 2018; 5(2): 1275–1284.

Zhu

Liu

You

Zhang

Huang

. Toward an intelligent edge: Wireless communication meets machine learning. IEEE Communications Magazine. 2020; 58(1): 19–25.

Wang

Tuor

Salonidis

Leung

Makaya

, et al. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications. 2019; 37(6): 1205–1221.

Guo

Guan

. Energy-Efficient and Delay-Guaranteed Workload Allocation in IoT-Edge-Cloud Computing Systems. IEEE Access. 2019; 7: 78685–78697.

Lin

Jia

Kingsley

. The research of power allocation algorithm with lower computational complexity for non-orthogonal multiple access. Applied Mathematics and Nonlinear Sciences. 2021; 0(0). Available from: doi: 10.2478/amns.2021.1.00027.

Liu

Zhang

. Offloading schemes in mobile edge computing for ultra-reliable low latency communications. IEEE Access. 2018; 6: 12825–12837.

G SSC Chamola

Tham

, S G Ansari

. An optimal delay aware task assignment scheme for wireless SDN networked edge cloudlets. Future Generation Computer Systems. 2020; 102: 862–875. Available from: http://www.sciencedirect.com/science/article/pii/S0167739X19301232.

Neely

. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan and Claypool Publishers; 2010.

10.

Meyn

Tweedie

. Stability of markovian processes III: Foster-lyapunov criteria for continuous-time processes. Advances in Applied Probability. 1993 Sep; 25(3): 518–548.

11.

Xiao

Dai

Jiang