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)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/28962 |
| Date | January 2023 |
| Creators | Manouchehrpour, Mohammad Amin |
| Contributors | Davidson, Timothy, Electrical and Computer Engineering |
| Source Sets | McMaster University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0181 seconds