MULTIPLE-TIME-SLOT COMMUNICATION RESOURCE ALLOCATION FOR MULTIPLE ACCESS COMPUTATION OFFLOADING

Abstract

The Mobile Edge Computing (MEC) framework has been proposed as a means to address the demand for extending the computational capabilities of small-scale mobile devices, especially in scenarios with tight latency requirements, or devices with limited available energy. This framework enables devices to offload computational tasks to their network access point. When multiple devices seek to offload computational tasks to their access point, the nature of the multiple access scheme plays a critical role in the system performance. The main focus of this thesis is to optimize the allocation of the available communication resources among the offloading devices, so as to minimize a weighted sum of their energy consumption. To effectively allocate the available communication resources, we adopt a multiple-time-slot (MTS) signalling architecture in which different numbers of devices transmit in each slot, according to a chosen multiple access scheme. We consider a common orthogonal multiple access scheme, namely time-division multiple access (TDMA), and various classes of non-orthogonal multiple access (NOMA), including NOMA with independent decoding(ID), NOMA with fixed-order sequential decoding (FOSD), and the “rate-region-optimal” NOMA scheme that is able to achieve any point in the capacity region. The problem is formulated as an optimization problem that involves jointly selecting the devices that will offload, along with optimizing the communication resources, namely the power and rate of each device in each time slot, and the time slot lengths. The solution strategy for this problem is to embed the resource allocation problem within a customized tree search algorithm, for the binary offloading decisions.

The thesis firstly explores the case in which the devices and access point are equipped with a single antenna. We show that the communication resource allocation problems for TDMA and the “rate-region-optimal” multiple access can be formulated as reduced-dimension convex optimizations. For NOMA with ID or FOSD, we show that the resource allocation problem has a difference-of-convex structure and we develop a successive convex approximation (SCA) algorithm with feasible point pursuit. Furthermore, for the FOSD scheme we obtain a closed-form expression that provides the optimal decoding order when it is feasible, and efficient algorithms for finding a good decoding order when it is not.

In the next step, we explore the case in which the devices and access point are equipped with multiple antennas. For the “rate-region-optimal” multiple access scheme, we show that the communication resource allocation problem can be formulated as a reduced-dimension convex optimization problem. For TDMA, we determine feasibility using the principles of waterfilling, and develop an iterative algorithm based on successive convex approximation (SCA) for feasible cases. For NOMA with ID or FOSD, we show that the resource allocation problem has a difference-of-convex structure and we develop an SCA algorithm with feasible point pursuit. Furthermore, for the FOSD scheme we develop an efficient algorithm for finding a good decoding order that often achieves the same performance as the “rate-region-optimal” multiple access. Our numerical results provide insight into tradeoffs between the complexity of a multiple access scheme (and its resource allocation algorithm), and its performance in computation offloading.

Finally, the thesis explores the communication resource allocation problem in computation offloading from an information theoretic perspective. To gain insight into how the choice of the multiple access scheme impacts the feasibility of offloading, we determine the regions of achievable average rates. These regions highlight the role played by the particular form of time sharing enabled by our MTS signalling architecture. To gain insight into the devices’ energy consumption, we consider the region of achievable energies, the boundary of which contains the set of Pareto optimal points for the minimum energy computation offloading problem. This region intuitively illustrates the scenarios in which suboptimal multiple access schemes can achieve the same energy consumption as the “rate-region-optimal” schemes and the gap between them when that is not the case. In particular, it inspires us to prove, analytically, that when the channel gains of the devices are equal, and their energy prices are equal, the minimum possible energy consumption over all multiple access schemes can be achieved using TDMA.