Wireless and Service Allocation for Mobile Computation Offloading with Task Deadlines

Mobile computation offloading (MCO) can be used to improve mobile device (MD) performance by running computational tasks on a remote cloud server rather than executing them locally [1, 2, 3]. Since the energy needed for task execution is incurred by the cloud server, a reduction in mobile device energy consumption can often be obtained [4, 5, 6, 7, 8, 9, 10]. During MCO, wireless communications is used by the MD to communicate with the cloud server. This interaction incurs MD energy use that would not otherwise exist if the task were executed at the MD. MCO also incurs added latency due to the time needed for the MD to interact with the cloud server [11, 12]. An edge server (ES) located close to the network base stations is typically used to reduce this delay by providing high interconnection bandwidth between the base station (BS) and the ES [13].

The question of whether a given task should be offloaded has been studied extensively [14, 15, 16, 17, 18, 19, 20, 21, 22, 23]. It is clear from this work that in order to obtain good performance, the offloading decisions should incorporate both the limited edge server computational capacity [21, 22, 23], and the temporal evolution of the system during the computation offload. This includes the queueing behaviour experienced by offloaded tasks awaiting execution at the ES [18, 19, 20]. Prior work has also considered the question of how best to configure system resources so that MCO is best accommodated [14, 18, 19, 20, 24, 25]. These are the issues that are considered in our paper and involve the tradeoffs between wireless communication and edge server capacity assignment and how these affect the delay performance experienced by the MDs.

The wireless and execution capacity assignment problem in MCO can be informally stated as follows. A network leaseholder (NL) purchases both wireless channel capacity and edge server execution services, subject to a cost budget constraint. The leased resources are then used to provide MCO to a large set of mobile devices [26]. When an MD generates a task for execution, there is an associated deadline, which gives the time by which task execution should be completed with a high degree of certainty [27]. The objective is to find a joint wireless and ES resource assignment that minimizes the mean MD power consumption subject to the budget constraint and constraints on the task completion times. Note that this problem is different than that of network slice creation [28]. In this case, the NL simply purchases services from the network owner (NO), who prices the cost of unit wireless channel and computational resources. Due to the edge server placement, we consider the case where the dominant latencies are that of wireless access and edge server execution [13].

The paper is novel in that it includes formulations for both soft and hard task completion time deadlines. In the soft deadline case, the wireless and edge server capacity assignments are designed so that the probability of task completion time deadline violation is upper bounded. In the hard deadline case, task execution deadlines must always be respected, which is accomplished by including concurrent local execution (CLE) [29] into the problem formulation. In CLE, local execution of the task may be initiated while offloading is ongoing, so that the task completion time deadline is always met.

The inclusion of task deadline constraints significantly increases the difficulty of the problem compared to that of prior work with no completion time requirements or that uses a mean delay criterion [30, 31]. In order to obtain solutions to the problem, a queuing model is used to obtain the delay distribution experienced by tasks that are offloaded to the ES [32, 31]. This model is incorporated into the resulting optimization problems, which are formulated as mixed integer nonlinear programming problems (MINLPs) that are computationally hard to solve exactly. Approximate solutions are obtained by decomposing the non-convex non-linear formulation into a collection of convex subproblems that can be solved efficiently, and then picking the best of these solutions.

A variety of results are presented that characterize the tradeoffs between task deadline violation, average MD power consumption and the cost budget. Our results show the quality of the proposed solutions, which can achieve close-to-optimum performance for a wide range of system parameters. The results also show that with CLE, the proposed solution not only guarantees respecting all hard task completion deadlines, but does so with only slightly higher MD power consumption when compared to the soft task completion deadlines solution with a small deadline violation probability. On the other hand, we show that there is an apparent trade-off in the case of soft task completion deadlines between the average power consumption and the deadline violation probability. Namely, the average MD power consumption of our solution is significantly reduced when a higher deadline violation probability is tolerable.

The main contributions of the paper are summarized below.

• •

  This paper addresses the problem of assigning computational and wireless channel resources for MCO, subject to task execution completion time deadlines. The work is the first that generates joint resource assignments for both soft and hard task deadlines using very general system modelling assumptions compared to prior work. The soft deadline case aims to create assignments so that the probability of task completion time deadline violation is upper bounded. In the hard deadline case, the paper is also unique in that it creates resource assignments where task completion time deadlines are always satisfied. This is done by incorporating CLE into the problem formulations. For this reason, this is the first paper that obtains system resource assignments for MCO that ensure that task completion time deadlines are always satisfied.

• •

  Modeling both soft and hard job completion time targets significantly increases the difficulty of the problem compared to prior work with no completion time requirements or that uses a mean delay criterion [30] [31]. In both deadline cases, the paper addresses this by incorporating an ES queueing system into the problem formulation that models the delay distribution experienced by arriving tasks. The assignment problem is addressed by inverting the estimated probability density function (PDF) of the task completion time and incorporating it into the optimizations. These resource assignments are obtained under very general modeling assumptions, where the wireless channels are modeled as arbitrary base station specific sets of Markov processes and task execution times have a general probability distribution.

• •

  The problems are first formulated as MINLPs, with integral decision variables for the number of wireless channels reserved, and a continuous decision variable for the portion of ES reserved. Even the relaxations of these MINLPs are difficult to solve, since they are non-convex. Hence, instead of following the common practice of solving the relaxation and rounding the fractional solution, we observe that the discretization of the continuous variable and the replacement of the discrete channel variables by approximate functions of the continuous blocking probabilities, allows us to break the original non-convex MINLPs into collections of convex subproblems, that can be solved efficiently. Our solutions are approximate, and their accuracy depends on both the discretization granularity and the approximation functions used for blocking probabilities. On the other hand, they are based on very general assumptions, i.e., the existence of convex upper bound approximations of the inversion of blocking probabilities. The more restricted the system model is, the better these approximations are.

The remainder of the paper is organized as follows. In Section II the prior work most related to our paper is reviewed. The system model and problem formulation is then described in Section III. In Section III-A, the general design problem is first considered assuming soft task completion time deadlines, where the probability of deadline violation is bounded. Following this, in Section III-B a formulation is described when task completion times are subject to hard deadlines. The problem formulations in both cases are non-convex and difficult to deal with directly using conventional optimization approaches. In Section IV, approximation solutions are proposed where the original problems are decomposed into convex subproblems that can be efficiently solved. Both the soft and hard deadline cases are considered in Sections IV-A and IV-B. Section V then introduces some common system assumptions used in the remainder of the paper when solving the optimizations. Both the soft and hard deadline cases are then treated in detail in Sections V-A and V-B. In Section VI simulation results that demonstrate the proposed designs are given. Both the single class and multiple classes of tasks cases are considered in Sections VI-A and VI-B. Finally, we present our conclusions of the work in Section VII.

A large amount of prior MCO work considers the problem based on system state inputs sampled at task generation times, i.e., the models assume that the system is static throughout the offload period [14, 18, 19, 20, 24, 25, 21, 22, 15, 17, 33, 34, 23]. As in our paper, task offloading decisions become more complex when the MD interacts with the network over wireless channels that may change randomly during the offload. Reference [32] studies a distributed computation offloading problem with delay constraints using stochastic communication channels but does not take into account the energy consumption incurred during task offloading. The work in [30] uses a Markov decision process that analyzes the mean task delay and the average system throughput. Unlike our paper, a throughput maximization problem is formulated with constraints on the average task delay, rather than using the delay distribution. In [31], task offloading is modeled as a game using a network of queues to obtain the end-to-end delay. The problem is transformed into one with a generalized Nash equilibrium solution that captures the conflicting interests in resource allocation among mobile network operators and computing resource providers. In references [30] and [31] the average delay is considered rather than the stringent types of soft and hard delay constraints considered in our paper. Reference [35] considers task offloading with statistical QoS guarantees (i.e., tasks are allowed to complete before a given deadline with a probability above a given threshold) to maximize the MD energy efficiency. The energy efficiency is defined as the ratio of the overall executed (transmitted) bits of tasks to the total energy consumption of the MDs. Statistical computation and transmission models are introduced to quantify the correlation between the statistical quality of service (QoS) guarantee and task offloading process. Unlike the models used in [31] and [35], our paper uses a task offloading and resource allocation formulation that uses very general system model assumptions, including base station specific sets of Markov processes for channel modelling.

Reducing both mobile energy consumption and task execution time is a common objective in mobile computation offloading. The work in [36] investigates a latency minimization problem in a multi-user time-division multiple access system with joint communication and computation resource allocation. Our paper, instead, uses a soft task deadline criterion based on modelling the distributions of both upload and execution time delays. Hard completion time constraints are considered in references [17, 21, 22, 33, 32, 23]. However, unlike our work, they consider the hard completion time requirement as a constraint in the problem formulation. For this reason, if the provided network resources or the MD transmit power are insufficient, the hard completion time constraints may not be satisfied. In our work, we avoid this infeasibility by applying CLE that ensures that hard completion time constraints are always satisfied. A benefit from integrating CLE into the problem formulation is that we no longer require the hard completion time constraints in the problem formulation. The objective in [21] is to minimize the energy consumption of the entire system, and in references [22] and [33], the objective is to minimize the total energy consumption of all MDs. Instead of satisfying delay constraints, the work in [24, 25, 34] optimize a utility function that is a weighted sum of task completion time and energy consumption. Unlike the above work, two different kinds of delay constraints are introduced in our paper, i.e., soft deadlines captured by the statistics of the completion time of the tasks and hard deadlines that are always satisfied by CLE.

Prior work has considered the optimization of wireless network and computational server resources to improve MCO performance [14, 18, 19, 20, 24, 25]. In particular, offloading decisions and base station associations are optimized with transmission power and channel assignments in a cellular network to minimize the total energy consumption of all MDs, subject to task’s latency constraints [17]. Reference [21] studies the problem of task offloading and channel resource allocation for ultra-dense networks and minimizes the total energy consumption of the system with a limited delay tolerance. The work in [22] studies MCO by considering application latency fairness and minimizes MD energy consumption by jointly optimizing the offloading ratio, channel assignments, and channel time allocations. Reference [23] investigates the power minimization problem for meeting the service delay requirements in multi-cell multi-user mobile edge computing networks. Channel assignment and power allocation problems are considered jointly. The work in [26] studies the joint resource management of link scheduling, channel assignment and power control for device-to-device communication assisted multi-tier fog computing with the objective of maximizing the network operator profit under deadline requirements. It considers the service charge collected from all end users, total expense in renting third-party fog nodes, and the energy cost of the ES. All of this work [21, 22, 17, 23, 26] optimizes radio resources and offloading decisions without considering edge server computational capability. The work in [24] investigates relay-assisted computation offloading to minimize the weighted sum of task execution delay and the energy consumption by jointly optimizing the offloading ratio, bandwidth allocation, processor speeds, and transmit power.

Table I summarizes the work described above that is most related to our paper, and compares it to this paper on five key properties: {LaTeXdescription}

The column denotes work where both channel and computation resource assignments are jointly generated. Our work differs from the rest in that we assign aggregate channel resources from the network operator to each base station so that it can support its associated mobile device population, i.e., we do not allocate channel and computation resources of each BS and ES to individual MDs.

The work selected in this column considers some form of soft (i.e., statistical) task deadlines. However, the models we use in this paper are quite different with more general underlying assumptions. Since our soft deadline model aims to set bounds on the probability of task deadline violation, we model the complete delay distribution experienced by executed tasks. This includes the base station channel delay (which is modeled by base station specific Markov processes) and the queueing delay experienced at the ES, where execution times can have a general distribution.

Although there is other work selected in this column, a significant difference exists compared with our paper, which we have already discussed above. Namely, our work can always satisfy all hard task deadlines by incorporating the CLE mechanism into the modeled system. The related work, instead, considers the existence of hard deadlines as a problem constraint that may result in problem infeasibility, which can never happen in our case.

This column denotes work where the resources provided to the MDs are charged by a third-party (e.g., network operator). The work selected considers computational resource expense but not on the wireless base station side. A network profit maximization problem is studied where an expense budget is not considered, unlike the case in our work.

Temporal evolution means that the offload periods may include stochastic changes to the wireless channels and the ES, so that this information must be modeled in the problem formulation, as in our paper. The randomness modeled in the selected work has different underlying assumptions compared to our paper.

As shown in Fig. 1, we consider a network that consists of $N$ BSs that are owned and operated by a NO. The set of BSs is denoted by $\mathcal{N}=\{1,2,\ldots,N\}$ and indexed by $n\in\mathcal{N}$. The network also contains an ES. Tasks generated by an MD can be offloaded through the wireless network and executed on the ES.

The NO permits a NL to rent wireless communication and ES computational capacity that the NL can use for mobile computation offloading for its MDs. When this is done, for each BS $n$, there are up to $K_{n}$ available channels that can be selected by the NL. The cost of renting a channel from BS $n$ is set by the NO to $\alpha_{n}$. When a channel is included in the agreement, the NO agrees to provision its network so that sufficient resources are available to allow the traffic generated on the channel to be carried to the ES with an acceptable delay with a high degree of certainty. Since the ES is located at the edge of the network, we focus on the dominant sources of delay, i.e., wireless access at the BSs and task execution at the ES [13].

In order to use the computing resources at the ES, the NL must also lease CPU resources at the ES. The cost (based on the number of CPU cycles per second) for leasing on the CPU resource is denoted by $\beta$. The maximum available CPU speed for rental is $f^{\rm{C}}$ CPU cycles per second.

When an agreement is made between the NO and NL, $x_{n}$ is defined as the number of channels from BS $n$ that are included, and $y\in\left[{0,1}\right]$ is defined as the fraction of maximum CPU speed at the ES that is included, i.e., the CPU speed available for the NL will be $yf^{\rm{C}}$. It is assumed that the NL has a cost budget, denoted by $B^{\text{max}}$. Accordingly, the total rent must satisfy the following constraint:

There are $J$ classes of tasks generated by the MDs, which may need to be offloaded to the ES. Let $\mathcal{J}=\{1,2,\ldots,J\}$ be the set of task classes. The class $j$ of a task is defined by parameters $s_{j}$, $q_{j}$, and $d_{j}$, where $s_{j}$ is the input data size in bits, $q_{j}$ is the computation load in number of CPU cycles, and $d_{j}$ is the deadline of the task in seconds. In what follows, $\tilde{d}_{j}=\left\lfloor{d_{j}/\tau}\right\rfloor$ is the task deadline rounded down to time slots of the same duration $\tau$ as the wireless transmission time slots (see below). The probability of a task generated by an MD belonging to class $j$ is denoted by $P_{j}^{\rm{C}}$; we assume that this probability is known, e.g., by observing the past history of offloading requests.

Our objective is to create a NO/NL contract for MCO. In MCO, tasks generated by an MD can be executed either locally (at the MD itself) or offloaded through the network and executed on the ES. We focus on two goals, each depending on how hard the task deadline constraint is. Our first goal is to accomplish this so that the mean mobile power consumption is minimized subject to the cost budget constraint and such that the probability that task execution deadline violation is bounded, i.e., the deadline constraints can be violated, albeit rarely. Our second goal is to create a power-efficient, budget-respecting assignment which respects all task deadlines, i.e., deadline constraints are hard; for that purpose we will employ CLE [29].

We model the wireless channels between the MDs and the BSs as discrete-time Markov processes. It is assumed that there are $I_{n}$ channel models for BS $n$, which are a function of the radio propagation environment that the MDs experience at that BS. $\mathcal{I}_{n}=\{1,2,\ldots,I_{n}\}$ is the set of all wireless channel models in BS $n$. For each of the channel models, the Markovian transition probabilities are defined in the usual way, i.e., given the channel state in the current time slot, there is a probability associated to its transition to another state in the next time slot. The time slot duration is defined to be $\tau$ seconds. A class $j$ task, offloaded to BS $n$ by the MD, encounters channel model $k$ with probability $P^{\rm{G}}_{n,j,k}$; as with task generation probabilities $P_{j}^{\rm{C}}$ above, we assume that this probability is also known, e.g., by observing the past history of offloading requests.

To obtain the design, the decision to offload the execution of a task is made using a local execute on blocking (LEB) mechanism as follows. When an MD in BS $n$ generates a class $j$ task, the MD offloads the task if at least one of the $x_{n}$ channels is available for immediate use. Otherwise, the MD executes the task locally. When a channel is available, the MD begins the offload by uploading the $s_{j}$ task bits needed for execution on the ES. The LEB mechanism is useful in that either local execution or remote offloading is initiated immediately at task release time, which may be advantageous when task deadlines are tight. It also provides a simple mechanism for assessing when the current level of local congestion is high, which would suggest that local execution is beneficial.

Tasks arrive at BS $n$ according to a stationary process with average arrival rate $\lambda_{n}$ tasks per second. According to the LEB mechanism, a new task is blocked from BS channel access if all the $x_{n}$ channels are busy with uploading other tasks. We denote the task blocking probability at BS $n$ by $P_{{\rm{B}}n}(x_{n})$, which is a function of $x_{n}$. For the sake of notation simplicity, we use $P_{{\rm{B}}n}$ in the rest of the paper. Let $p^{\text{L}}$ be the power needed in the MD to process tasks. When a class $j$ task is blocked from offloading and executed locally, the local execution time is given as $L_{j}={q_{j}}/f$, where $f$ is the MD’s execution speed in number of CPU cycles per time slot¹¹1$L_{j}$ is normally measured in CPU cycles, but in order to apply CLE and to simplify the system, we round it up to a multiple of $\tau$.. Define $\bar{L}$ as the average local execution time of tasks. Since the task blocking is caused by channel access, which is the same for all task classes, we have $\bar{L}=\sum_{j=1}^{J}P_{j}^{\rm{C}}L_{j}$. The average energy consumption for executing a task locally is given by $p^{\rm{L}}{\bar{L}}$. Consider all the tasks that are generated in BS $n$ and blocked from offloading in one second, then the mean energy for executing these tasks locally is

which is the average power consumption of the MDs.

The wireless upload transmission time $t_{n,j,k}^{\text{W}}$ of a $j$th class task in BS $n$ when the wireless channel model is $k$, is measured in time slots. The mean wireless upload transmission time $\bar{t}^{\rm{W}}_{n,j,k}$ for $j$th class tasks in BS $n$ according to channel model $k$ can be calculated, since $\Pr[{t_{n,j,k}^{\rm{W}}=l}]$ can be computed for all $l$ from channel model $k$. Moreover, the mean wireless transmission time $\bar{t}_{n}^{\rm{W}}$ for BS $n$ is

Under the stated assumptions, the aggregate mean task arrival rate $\lambda$ at the ES is given by

As is normally the case for stability in a single server queueing system, the following constraint must always be satisfied,

where ${\mu^{\rm{C}}}$ denotes the mean service rate at the ES, i.e, ${\mu^{\rm{C}}}=yf^{\rm{C}}/\sum_{j=1}^{J}P_{j}^{\rm{C}}q_{j}$. As will become clear later, we can relax this constraint to $\lambda\leq yf^{\rm{C}}/\sum_{j=1}^{J}P_{j}^{\rm{C}}q_{j}$ without affecting our proposed solutions.

Let $t_{n,j,k}^{\rm{C}}$ be the delay (including both queueing and execution time) experienced by a $j$th class task from BS $n$ at the ES, under wireless channel model $k$. It takes continuous values, and $\Pr[{{t_{n,j,k}^{\rm{C}}}\leq t}]$, for any $t\geq 0$, is a function of $\lambda$ and $\mu^{\rm{C}}$. In what follows, ${\tilde{t}}_{n,j,k}^{\rm{C}}$ is the discretization of $t_{n,j,k}^{\rm{C}}$, measured in time slots; its distribution is calculated by

for any number of time slots $b\geq 0$. Table II lists the related notation and their associated meanings.

In this section, we propose approximate solutions for optimization problems (10)-(15) and (20)-(24), by decomposing them into convex optimization subproblems which can be solved efficiently.

In the remainder of this paper, we assume that tasks arrive from the MDs at BS $n$ according to a Poisson process with mean arrival rate $\lambda_{n}$. The Poisson process assumption is commonly made in this type of situation, since the number of mobile devices in a given coverage area is typically quite large, each contributing to a small fraction of the total load [37]. In this case, we can invoke the insensitivity property of the Erlang B formula, to compute the probability of blocking at each BS [38]. Note that, typically, the Erlang B result is derived using the $M/M/N/N$ Markovian queue, which assumes exponentially distributed channel upload (i.e., service) times [39]. Due to insensitivity, the result holds for any service time distribution with the same mean. Therefore, the blocking probability for a task arriving at BS $n$ is

where $\mu_{n}^{\text{W}}$ denotes the mean service rate, which can be calculated by $\mu_{n}^{\text{W}}=1/{{\bar{t}}_{n}^{\rm{W}}}$. Function (40) is convex in $x_{n}$ [40].

Note that due to the Poisson process task arrival assumption, the channel state sampled by arriving tasks is given by the steady-state equilibrium probability distribution of the Markovian channel at that MD. This follows from the PASTA rule [41].

We assume that the aggregate task arrival process at ES is Poisson [42], and, therefore, arriving tasks sample the asymptotic equilibrium state distribution of ES. This approximation is justified due to the mixing of arrivals at ES from BSs operating independently. In this case, ES can be modeled as an $M/G/1$ queue, whose waiting time is given by the random variable $w^{\rm{C}}$. Given $\lambda$ and knowledge of the data upload distribution, the distribution of $w^{\rm{C}}$ can be obtained by numerical inversion of the probability generating function of system waiting time for $M/G/1$ [37]. In this case, the execution time of a task at the ES depends only on which class it belongs to, i.e., $t_{n,j,k}^{\rm{C}}=t_{j}^{\rm{C}}$, for all $n$ and $k$, and $t_{j}^{\rm{C}}=w^{\rm{C}}+q_{j}/yf^{\rm{C}}$. Thus, ${\rm{Pr}}[{t_{n,j,k}^{\rm{W}}+t_{j}^{\rm{C}}\leq{d_{j}}}]$ can be easily obtained.

When applying algorithms GCASD (Algorithm 1) and GCAHD (Algorithm 2) in this case, the upper bound $F$ used in problem (28)-(31) and (36)-(39) becomes [43]:

In this section, we present simulation results to demonstrate the performance of our proposed algorithms GCASD (Algorithm 1) and GCAHD (Algorithm 2). We adopt the two-state Gilbert-Elliot channel model [44], i.e., the channel states change by following a Markov chain with two states, “Good” (G) and “Bad” (B). This model is commonly used to characterize the effects of burst noise in wireless channels, where the channel can abruptly transition between good and bad conditions [45]. The Gilbert-Elliot channel is a difficult one for computation offloading algorithms to deal with compared to those where there is much more correlation in the channel quality as the offloading progresses. Let $B_{g}$ and $B_{b}$, respectively, be the data transmission rate when the channel is in the G and B states. We consider that all channels have the same $B_{g}$ and $B_{b}$ values but differ in their state transition probabilities that result in different propagation models. The transition probabilities for propagation model $k$ in BS $n$ are denoted as ${{P_{n,k}^{\rm{GG}}}},{{P_{n,k}^{\rm{GB}}}},~{}{{P_{n,k}^{\rm{BG}}}}$, and ${{P_{n,k}^{\rm{BB}}}}$. In each time slot, the channel state Markov chain transitions in accordance with these probabilities. Denote $\pi_{n,k}^{\rm{G}}$ and $\pi_{n,k}^{\rm{B}}$, respectively, as the stationary probabilities of a channel in BS $n$ for propagation model $k$ being in the G and B states. Two sets of simulations are performed with set 1 for single class of tasks and set 2 for multiple classes of tasks. Default parameters used in the simulations are summarized in Table III. The parameter settings that we use were taken from the references [26, 23] and [32]. These references summarize parameter settings for various types of applications including those that are inherently delay sensitive, such as gaming, face recognition and healthcare use. We intentionally use a wide range of parameter values based on the referenced ranges so that we can make conclusions that apply in general settings.