Multiple-Time-Slot Multiple Access Binary Computation Offloading in the $K$-User Case

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. For a system with heterogeneous tasks, we adopt a time-slotted signaling architecture in which different numbers of devices transmit in each slot, subject to individual power constraints. We consider the problem of jointly selecting the devices that will offload, along with optimizing their communication resources (their powers and rates in each time slot, and the time slot lengths) so as to minimize the a weighted sum of the energy expended by the devices. We employ a customized tree search algorithm for the offloading decisions in which a resource allocation problem is solved at each node. For time-division multiple access (TDMA) and “rate optimal” multiple access, we obtain reduced-dimension convex formulations of the resource allocation problem. For non-orthogonal multiple access (NOMA) with independent decoding (ID) or fixed-order sequential decoding (FOSD) we show that the resource allocation problem has a difference-of-convex structure and we develop a successive convex approximation 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. Our results capture the inherent tradeoffs between the complexity of a multiple access scheme (and its resource allocation algorithm), and its performance in the computation offloading application.