Mobile computation offloading (MCO) can alleviate the hardware limitations of mobile devices by migrating heavy computational tasks from mobile devices to more powerful cloud servers. This can lead to better performance and energy savings for the mobile devices. This thesis considers MCO over stochastic wireless channels when task completion times are subject to hard deadline constraints. Hard deadlines, however, are difficult to meet in conventional computation offloading due to the randomness caused by the wireless channels. In the proposed offloading policies, concurrent local execution (CLE) is used to guarantee task execution time constraints. By sometimes allowing simultaneous local and remote execution, CLE ensures that job deadlines are always satisfied in the face of any unexpected wireless channel conditions. The thesis introduces online optimal algorithms that reduce the remote and local execution overlap so that energy wastage is minimized. Markov processes are used to model the communication channels. MCO is addressed for three different job offloading schemes: continuous, multi-part, and preemptive. In the case of continuous offloading, referred to as 1-Part offloading, the mobile device will upload the entire job in one piece without interruption, when the scheduler decides to do so. In multi-part computation offloading, the job is partitioned into a known number (K) of parts, and each part is uploaded separately. In this offloading mechanism, which is referred to as K-Part Offloading, the upload initiation times of each part must be determined dynamically during runtime, and there may be waiting time periods between consecutive upload parts. Preemptive offloading is a generalization of K-Part Offloading where the number of task upload parts is unknown. In this scheme, a decision to either continue offloading or to temporarily interrupt the offload is made at the start of each time slot. Compared to the conventional contiguous computation offloading, interrupted offloading mechanisms (i.e., K-Part and preemptive offloading) allow the system to adapt when channel conditions change and therefore may result in lower mobile device energy consumption. This energy reduction will be obtained at the expense of having higher computational complexity. In this thesis, for each offloading scheme, an online computation offloading algorithm is introduced by constructing a time-dilated absorbing Markov chain (TDAMC) and applying dynamic programming (DP). These algorithms are shown to be energy-optimal while ensuring that the hard task deadline constraints are always satisfied. The optimality of these algorithms is proved using Markovian decision process stopping theory. Since the computational complexity of the proposed online algorithms, especially in the case of preemptive offloading, can be significant, three simpler and computationally efficient approximation methods are introduced: Markovian Compression (MC), Time Compression (TC), and Preemption Using Continuous Offloading (Preemption-CO). MC and TC reduce the state space of the offloading Markovian process by using a novel notion of geometric similarity or by running an optimal online offloading algorithm in periodic time steps. In Preemption-CO, while a task is offloaded preemptively, the offloading decision at every time-slot is based on non-preemptive calculations. These methods are used alone or in combination to construct practical offloading algorithms. A variety of results are presented that show the tradeoffs between complexity and mobile energy-saving performance for the different algorithms. / Thesis / Doctor of Philosophy (PhD)

Mobile computation offloading (MCO) is a way of improving mobile device (MD) performance by offloading certain task executions to a more resourceful edge server (ES), rather than running them locally on the MD. This thesis first considers the problem of assigning the wireless communication bandwidth and the ES capacity needed for this remote task execution, so that task completion time constraints are satisfied. The objective is to minimize the average power consumption of the MDs, subject to a cost budget constraint on communication and computation resources. The thesis includes contributions for both soft and hard task completion deadline constraints. The soft deadline case aims to create assignments so that the probability of task completion time deadline violation does not exceed a given violation threshold. In the hard deadline case, it creates resource assignments where task completion time deadlines are always satisfied. The problems are first formulated as mixed integer nonlinear programs. Approximate solutions are then obtained by decomposing the problems into a collection of convex subproblems that can be efficiently solved. Results are presented that demonstrate the quality of the proposed solutions, which can achieve near optimum performance over a wide range of system parameters. The thesis then introduces algorithms for static task class partitioning in MCO. The objective is to partition a given set of task classes into two sets that are either executed locally or those classes that are permitted to contend for remote ES execution. The goal is to find the task class partition that gives the minimum mean MD power consumption subject to task completion deadlines. The thesis generates these partitions for both soft and hard task completion deadlines. Two variations of the problem are considered. The first assumes that the wireless and computational capacities are given and the second generates both capacity assignments subject to an additional resource cost budget constraint. Two class ordering methods are introduced, one based on a task latency criterion, and another that first sorts and groups classes based on a mean power consumption criterion and then orders the task classes within each group based on a task completion time criterion. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solutions. The thesis then considers the use of digital twins (DTs) to offload physical system (PS) activity. Each DT periodically communicates with its PS, and uses these updates to implement features that reflect the real behaviour of the device. A given feature can be implemented using different models that create the feature with differing levels of system accuracy. The objective is to maximize the minimum feature accuracy for the requested features by making appropriate model selections subject to wireless channel and ES resource availability. The model selection problem is first formulated as an NP-complete integer program. It is then decomposed into multiple subproblems, each consisting of a modified Knapsack problem. A polynomial-time approximation algorithm is proposed using dynamic programming to solve it efficiently, by violating its constraints by at most a given factor. A generalization of the model selection problem is then given and the thesis proposes an approximation algorithm using dependent rounding to solve it efficiently with guaranteed constraint violations. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solutions. / Thesis / Doctor of Philosophy (PhD) / Mobile devices (MDs) such as smartphones are currently used to run a wide variety of application tasks. An alternative to local task execution is to arrange for some MD tasks to be run on a remote non-mobile edge server (ES). This is referred to as mobile computation offloading (MCO). The work in this thesis studies two important facets of the MCO problem. 1. The first considers the joint effects of communication and computational resource assignment on task completion times. This work optimizes task offloading decisions, subject to task completion time requirements and the cost that one is willing to incur when designing the network. Procedures are proposed whose objective is to minimize average mobile device power consumption, subject to these cost constraints. 2. The second considers the use of digital twins (DTs) as a way of implementing mobile computation offloading. A DT implements features that describe its physical system (PS) using models that are hosted at the ES. A model selection problem is studied, where multiple DTs share the execution services at a common ES. The objective is to optimize the feature accuracy obtained by DTs subject to the communication and computation resource availability. The thesis proposes different approximation and decomposition methods that solve these problems efficiently.