This thesis considers mobile computation offloading where task completion times are subject to hard deadline constraints. Hard deadlines are difficult to meet in conventional computation offloading due to the stochastic nature of the wireless channels involved. Rather than using binary offload decisions, we permit concurrent remote and local job execution when it is needed to ensure task completion deadlines. The thesis addresses this problem for homogeneous Markovian wireless channels. Two online energy-optimal computation offloading algorithms, OnOpt and MultiOpt, are proposed. OnOpt uploads the job to the server continuously and MultiOpt uploads the job in separate parts, each of which requires a separate offload initiation decision. The energy optimality of the algorithms is shown by constructing a time-dilated absorbing Markov process and applying dynamic programming. Closed form results are derived for general Markovian channels. The Gilbert-Elliott channel model is used to show how a particular Markov chain structure can be exploited to compute optimal offload initiation times more efficiently. The performance of the proposed algorithms is compared to three others, namely, Immediate Offloading, Channel Threshold, and Local Execution. Performance results show that the proposed algorithms can significantly improve mobile device energy consumption compared to the other approaches while guaranteeing hard task execution deadlines. / Thesis / Master of Applied Science (MASc)

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)

Os dispositivos móveis passaram por grandes transformações na última década e tornaram-se complexos computadores dotados de grande poder de processamento e memória, além de prover aos usuários diversos recursos como sensores e câmeras de alta resolução. O uso de dispositivos móveis para diversas tarefas aumentou consideravelmente, o que levantou uma grande preocupação com o o alto consumo de energia desses dispositivos. Portanto, estudos tem sido realizados no sentido de encontrar soluções para diminuir o custo de energia das aplicações que executam em dispositivos móveis. Uma das alternativas mais utilizadas é o \\textit{computation offloading}, cujo objetivo é transferir a execução de uma tarefa para uma plataforma externa com o intuito de aumentar desempenho e reduzir consumo de recursos, como a bateria, por exemplo. Decidir sobre usar ou não esta técnica implica entender a influência de fatores como a quantidade de dados processados, a quantidade de computação envolvida, e o perfil da rede. Muitos estudos tem sido realizados para estudar a influência de diversas opções de rede wireless, como 3G, 4G e Wifi, mas nenhum estudo investigou a influência das escolhas de comunicação no custo de energia. Portanto, o objetivo deste trabalho é apresentar uma investigação sobre a influência da quantidade de dados, da quantidade de computação e dos protocolos de comunicação ou estilo arquitetural no consumo de energia quando a técnica de \\textit{computation offloading} é utilizada. Neste estudo, foram comparados REST, SOAP, Socket e RPC na execução de algoritmos de ordenação de diferentes complexidades aplicados sobre vetores de diversos tamanhos e tipos de dados. Os resultados mostram que a execução local é mais econômica com algoritmos menos complexos, pequeno tamanho de entrada e tipo de dados menos complexos. Quando se trata de execução remota, o REST é a escolha mais econômica seguida por Socket. Em geral, REST é mais econômico com vetores do tipo Object, independentemente da complexidade do algoritmo e tamanho do vetor, enquanto Socket é mais econômico com entradas maiores e com vetores de tipos primitivos, como Int e Float / Mobile devices have significantly changed in the last decade and they become complex computer machines equipped with large processing power and memory. Moreover, they provide users with several resources such as sensors and high resolution cameras. The usage of mobile devices has significantly increased in the past years, which raised an important concern regarding the high energy consumption. Therefore, several investigations have been conducted aiming at finding solutions to reduce the energy cost of mobile applications. One of the most used strategy is called computation offloading, whose main goal is to transfer the execution of a task to an external platform aiming at increasing performance and reducing resource consumption, including the battery. Deciding towards offloading certain tasks requires to understand the influence of the amount of data, amount of computation, and the network profile. Several studies have investigated the influence of different wireless flavours, such as 3G, 4G and wifi, but no study has investigated the influence of the communication choices on the energy cost. Therefore, the purpose of this research project is to present an investigation on the influence of the amount of data, amount of computation and the communication protocols and architectural style on the energy consumption in the context of the computation offloading technique. In this study, we compare REST, SOAP, Socket and RPC when executing algorithms of different complexities and different input sizes and types. Results show that local execution is more economic with less complex algorithms and small input data. When it comes to remote execution, REST is the most economic choice followed by Socket. In general, REST is the most economic choice when applied on Object type arrays, regardless the complexity and size, while Socket is the most economic choice with large arrays and primitive types such as integers and floats

Os dispositivos móveis passaram por grandes transformações na última década e tornaram-se complexos computadores dotados de grande poder de processamento e memória, além de prover aos usuários diversos recursos como sensores e câmeras de alta resolução. O uso de dispositivos móveis para diversas tarefas aumentou consideravelmente, o que levantou uma grande preocupação com o o alto consumo de energia desses dispositivos. Portanto, estudos tem sido realizados no sentido de encontrar soluções para diminuir o custo de energia das aplicações que executam em dispositivos móveis. Uma das alternativas mais utilizadas é o \\textit{computation offloading}, cujo objetivo é transferir a execução de uma tarefa para uma plataforma externa com o intuito de aumentar desempenho e reduzir consumo de recursos, como a bateria, por exemplo. Decidir sobre usar ou não esta técnica implica entender a influência de fatores como a quantidade de dados processados, a quantidade de computação envolvida, e o perfil da rede. Muitos estudos tem sido realizados para estudar a influência de diversas opções de rede wireless, como 3G, 4G e Wifi, mas nenhum estudo investigou a influência das escolhas de comunicação no custo de energia. Portanto, o objetivo deste trabalho é apresentar uma investigação sobre a influência da quantidade de dados, da quantidade de computação e dos protocolos de comunicação ou estilo arquitetural no consumo de energia quando a técnica de \\textit{computation offloading} é utilizada. Neste estudo, foram comparados REST, SOAP, Socket e RPC na execução de algoritmos de ordenação de diferentes complexidades aplicados sobre vetores de diversos tamanhos e tipos de dados. Os resultados mostram que a execução local é mais econômica com algoritmos menos complexos, pequeno tamanho de entrada e tipo de dados menos complexos. Quando se trata de execução remota, o REST é a escolha mais econômica seguida por Socket. Em geral, REST é mais econômico com vetores do tipo Object, independentemente da complexidade do algoritmo e tamanho do vetor, enquanto Socket é mais econômico com entradas maiores e com vetores de tipos primitivos, como Int e Float / Mobile devices have significantly changed in the last decade and they become complex computer machines equipped with large processing power and memory. Moreover, they provide users with several resources such as sensors and high resolution cameras. The usage of mobile devices has significantly increased in the past years, which raised an important concern regarding the high energy consumption. Therefore, several investigations have been conducted aiming at finding solutions to reduce the energy cost of mobile applications. One of the most used strategy is called computation offloading, whose main goal is to transfer the execution of a task to an external platform aiming at increasing performance and reducing resource consumption, including the battery. Deciding towards offloading certain tasks requires to understand the influence of the amount of data, amount of computation, and the network profile. Several studies have investigated the influence of different wireless flavours, such as 3G, 4G and wifi, but no study has investigated the influence of the communication choices on the energy cost. Therefore, the purpose of this research project is to present an investigation on the influence of the amount of data, amount of computation and the communication protocols and architectural style on the energy consumption in the context of the computation offloading technique. In this study, we compare REST, SOAP, Socket and RPC when executing algorithms of different complexities and different input sizes and types. Results show that local execution is more economic with less complex algorithms and small input data. When it comes to remote execution, REST is the most economic choice followed by Socket. In general, REST is the most economic choice when applied on Object type arrays, regardless the complexity and size, while Socket is the most economic choice with large arrays and primitive types such as integers and floats

Mobile devices are increasingly being relied on for computation intensive and/or communication intensive applications that go beyond simple connectivity and demand more complex processing. This has been made possible by two trends. First, mobile devices, such as smartphones and tablets, are increasingly capable devices with processing and storage capabilities that make significant step improvements with every generation. Second, many improved connectivity options (e.g., 3G, WiFi, Bluetooth) are also available to mobile devices. In the rich computing and communication environment, it is promising but also challenging for mobile devices to take advantage of various available resources to improve the performance of mobile applications. First, with varying connectivity, remote computing resources are not always accessible to mobile devices in a predictable way. Second, given the uncertainty of connectivity and computing resources, their contention will become severe. This thesis seeks to address the connectivity challenges for mobile computing and communication. We propose a set of techniques and systems that help mobile applications to better handle the varying network connectivity in the utilization of various computation and communication resources. This thesis makes the following contributions: We design and implement Serendipity to allow a mobile device to use other encountered, albeit intermittently, mobile devices to speedup the execution of parallel applications through carefully allocating computation tasks among intermittently connected mobile devices. We design and implement IC-Cloud to enable a group of mobile devices to efficiently use the cloud computing resources for computation offloading even when the connectivity is varying or intermittent. We design and implement COSMOS to provide scalable computation offloading service to mobile devices at low cost by efficiently managing and allocating cloud computing resources. We design and implement CoAST to allow collaborative application-aware scheduling of mobile traffic to reduce the contention for bandwidth among communication-intensive applications without affecting their user experience.

With an ever-increasing percentage of the human population connected to the internet, the amount of data produced and processed is at an all-time high. Edge Computing has emerged as a paradigm to handle this growth and, combined with 5G, enables complex time-sensitive applications running on resource-restricted devices. This master thesis investigates the use of WebAssembly in the context of computa¬tional offloading at the Edge. The focus is on utilizing WebAssembly to move computa¬tional heavy parts of a system from an end device to an Edge Server. An objective is to improve program performance by reducing the execution time and energy consumption on the end device. A proof-of-concept offloading system is developed to research this. The system is evaluated on three different use cases; calculating Fibonacci numbers, matrix multipli¬cation, and image recognition. Each use case is tested on a Raspberry Pi 3 and Pi 4 comparing execution of the WebAssembly module both locally and offloaded. Each test will also run natively on both the server and the end device to provide some baseline for comparison.

In this thesis we consider a set of mobile users that employ cloud-based computation offloading. In computation offloading, user energy consumption can be decreased by uploading and executing jobs on a remote server, rather than processing the jobs locally. In order to execute jobs in the cloud however, the user uploads must occur over a base station channel which is shared by all of the uploading users. Since the job completion times are subject to hard deadline constraints, this restricts the feasible set of jobs that can be remotely processed, and may constrain the users ability to reduce energy usage. The system is modelled as a competitive game in which each user is interested in minimizing its own energy consumption. The game is subject to the real-time constraints imposed by the job execution deadlines, user specific channel bit rates, and the competition over the shared communication channel. The thesis shows that for a variety of parameters, a game where each user independently sets its offloading decisions always has a pure Nash equilibrium, and a Gauss-Seidel method for determining this equilibrium is introduced. Results are presented which illustrate that the system always converges to a Nash equilibrium using the Gauss-Seidel method. Data is also presented which show the number of Nash equilibria that are found, the number of iterations required, and the quality of the solutions. We find that the solutions perform well compared to a lower bound on total energy performance. / Thesis / Master of Applied Science (MASc)

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.

The limited energy and computing power of small smart devices restricts their ability to support a wide range of applications, especially those needing quick responses. Mobile edge computing offers a potential solution by providing computing resources at the network access points that can be shared by the devices. This enables the devices to offload some of their computational tasks to the access points. To make this work well for multiple devices, we need to judiciously allocate the available communication and computing resources among the devices. The main focus of this thesis is on (near) optimal resource allocation in a K-user offloading system that employs the time division multiple access (TDMA) scheme. In this thesis, we develop effective algorithms for the resource allocation problem that aim to minimize the overall (cost of the) energy that the devices consume in completing their computational tasks within the specified deadlines while respecting the devices' constraints. This problem is tackled for tasks that cannot be divided and hence the system must make a binary decision as to whether or not a task should be offloaded. This implies the need to develop an effective decision-making algorithm to identify a suitable group of devices for offloading. This thesis commences by developing efficient communication resource algorithms that incorporate the impact of integer finite block length in low-latency computational offloading systems with reserved computing resources. In particular, it addresses the challenge of minimizing total energy consumption in a binary offloading scenario involving K users. The approach considers different approximations of the fundamental rate limit in the finite block length regime, departing from the conventional asymptotic rate limits developed by Shannon. Two such alternatives, namely the normal approximation and the SNR-gap approximation, are explored. A decomposition approach is employed, dividing the problem into an inner component that seeks an optimal solution for the communication resource allocation within a defined set of offloading devices, and an outer component aimed at identifying a suitable set of offloading devices. Given the finiteness of the block length and its integer nature, various relaxation techniques are employed to determine an appropriate communication resource allocation. These include incremental and independent roundings, alongside an extended search that utilizes randomization-based methods in both rounding schemes. The findings reveal that incremental randomized rounding, when applied to the normal approximation of the rate limits, enhances system performance in terms of reducing the energy consumption of the offloading users. Furthermore, customized pruned greedy search techniques for selecting the offloading devices efficiently generate good decisions. Indeed, the proposed approach outperforms a number of existing approaches. In the second contribution, we develop efficient algorithms that address the challenge of jointly allocating both computation and communication resources in a binary offloading system. We employ a similar decomposition methodology as in the previous work to perform the decision-making, but this is now done along with joint computation and communication resource allocation. For the inner resource allocation problem, we divide the problem into two components: determining the allocation of computation resources and the optimal allocation of communication resources for the given allocation of computation resources. The allocation of the computation resources implicitly determines a suitable order for data transmission, which facilitates the subsequent optimal allocation of the communication resources. In this thesis, we introduce two heuristic approaches for allocating the computation resources. These approaches sequentially maximize the allowable transmission time for the devices in sequence, starting from the largest leading to a reduction in total offloading energy. We demonstrate that the proposed heuristics substantially lower the computational burden associated with solving the joint computation--communication resource allocation problem while maintaining a low total energy. In particular, its use results in substantially lower energy consumption than other simple heuristics. Additionally, the heuristics narrow the energy gap in comparison to a fictitious scenario in which each task has access to the whole computation resource without the need for sharing. / Thesis / Master of Applied Science (MASc)

The limited energy and computational resources in small-scale smart devices impede the expansion of the range of applications that those devices can support, especially to applications with tight latency constraints. Mobile edge computing is a promising framework that provides shared computational resources in the access points in the network and provides devices in that network with the opportunity to offload (a portion of) their computational tasks to the access points. To effectively capture that opportunity in an offloading system with multiple devices, the available communication and computation resources must be efficiently allocated. The main focus of this thesis is on the optimal allocation of communication resources in a K-user offloading system. The resource allocation problem that is considered in this thesis captures minimizing the total energy consumption of users while the requirements of the users, and their computational tasks, are met. That problem is addressed for two of the most widely-considered classes of computational tasks in the literature, namely, indivisible tasks (binary offloading) and divisible tasks (partial offloading). This thesis begins with an exploration of the impact of the choice of multiple access scheme that is employed by the system on the total energy consumption of the users. In particular, the problem of minimizing the total energy consumption of a two-user binary offloading system is tackled under various multiple access schemes, namely time division multiple access (TDMA), sequential decoding without time sharing, independent decoding, and multiple access schemes that can exploit the full capabilities of the channel, which are referred to as full multiple access schemes (FullMA) in this thesis. Using a decomposition-based approach, closed-form solutions to the resource allocation problem are obtained. Those expressions show that by exploiting the full capabilities of the channel, a FullMA scheme can significantly reduce the total energy consumption of the users as compared to the other schemes. The closed-form expressions also show that when the channel gains of the two users are equal, the TDMA scheme can achieve the optimal energy consumption. For the case of partial offloading, an analogous analysis leads to a reduced-dimension design problem and an extension to the optimally result for TDMA. In the next step of the development, the insights obtained from the decomposition-based analysis of the two-user case are used to tackle the communication resource allocation problem for a K-user offloading system in which the users are assumed to be served over a single time slot. Based on their performance in the two-user case, FullMA and TDMA schemes are considered. The mixed-integer optimization problem that arises in the binary offloading case is addressed by employing a decomposition approach with a closed-form expression obtained for the optimal resource allocation for given offloading decisions, and a tailored pruned greedy search algorithm developed herein for the offloading decisions. By exploiting the maximum allowable latency of each individual user, the proposed algorithm is able to significantly reduce the energy consumption of the users in comparison to the existing algorithms in the literature that assume equal latency constraints for all users. Furthermore, with the closed-form optimal solution to the resource allocation problem obtained for given offloading decisions, the proposed algorithm has a significantly lower computational cost compared to the existing algorithms. In the partial offloading case, a quasi-closed- form solution is obtained for the resource allocation problem. Finally, a time-slotted signalling structure is proposed as an optimal transmission structure for a generic K-user offloading system. Furthermore, an optimal times-lotted structure that requires only K time slots is developed for a K-user offloading system that employs a FullMA scheme. The proposed time-slotted structure not only exploits the maximum latency constraint of each user, it also exploits the differences between the latency constraints of the users by taking advantage of the interference reduction that arises when a user finishes offloading. The proposed time-slotted FullMA signalling structure significantly reduces the energy consumption of the users compared to some existing methods that employ the TDMA scheme, and compared to those with FullMA, but sub-optimal single-time-slot signalling structures. Moreover, the computational cost of the proposed time-slotted algorithm is significantly lower than that of the existing algorithms in the literature. / Dissertation / Doctor of Philosophy (PhD) / The rapid increase in the number of smart devices in wireless communication networks, and the expansion in the range of computationally-intensive and latency sensitive applications that those devices are required to support, have highlighted their resource limitations in terms of energy, power, central processing unit (CPU), and memory. Mobile edge computing is a framework that provides shared computational resources at the access points of wireless networks and gives such devices the opportunity to offload (a portion of) their applications to be executed at the access points. In order to fully exploit such an opportunity when multiple devices seek to offload their applications, the available communication and computation resources must be efficiently allocated amongst those devices. The ultimate goal of this thesis is to obtain the optimal communication resource allocation in a K-user offloading system while different constraints on the devices and on the applications are satis ed. To that end, this thesis shows that the minimum energy consumption is obtained when the system exploits the full capabilities of the channel, the maximum allowable latency of each user, and the differences between the latency constraints of each user. Accordingly, this thesis proposes an optimized signalling structure and, based on that structure, low-complexity algorithms that achieve an energy-optimal resource allocation in a K-user offloading system.