Online Offloading Scheduling for NOMA-Aided MEC Under Partial Device Knowledge

Meihui Hua, Hui Tian, Xinchen Lyu, Wanli Ni, Gaofeng Nie

Abstract

By exploiting the superiority of nonorthogonal multiple access (NOMA), NOMA-aided mobile-edge computing (MEC) can provide scalable and low-latency computing services for the Internet of Things (IoT). However, given the prevalent stochasticity of wireless networks and sophisticated signal processing of NOMA, it is critical but challenging to design an efficient task offloading algorithm for NOMA-aided MEC, especially under a large number of devices. This article presents an online algorithm that jointly optimizes offloading decisions and resource allocation to maximize the long-term system utility (i.e., a measure of throughput and fairness). Since the optimization variables are temporary coupled, we first apply Lyapunov technique to decouple the long-term stochastic optimization into a series of per-slot deterministic subproblems, which does not require any prior knowledge of network dynamics. Second, we propose to transform the nonconvex per-slot subproblem of optimizing NOMA power allocation equivalently to a convex form by introducing a set of auxiliary variables, whereby the time-complexity is reduced from the exponential complexity to $O(M^{3/2})$. The proposed algorithm is proved to be asymptotically optimal, even under partial knowledge of the device states at the base station. Simulation results validate the superiority of the proposed algorithm in terms of system utility, stability improvement, and the overhead reduction.

Introduction

As IoT networks scale toward massive connectivity, devices with limited battery and processing power increasingly rely on Mobile-Edge Computing (MEC) to offload computationally intensive tasks. Traditional Orthogonal Multiple Access (OMA) schemes, which assign dedicated frequency or time slots to each user, struggle to support the high density of devices required in modern industrial and urban environments.

Non-Orthogonal Multiple Access (NOMA) has emerged as a superior alternative, allowing multiple users to share the same frequency simultaneously. However, NOMA introduces significant complexity in managing interference and power levels, often resulting in non-convex optimization problems. Furthermore, real-world networks are characterized by stochastic task arrivals and time-varying channel conditions. Most existing research assumes the Base Station (BS) possesses perfect, real-time knowledge of every device—an assumption that is impractical for large-scale networks due to the massive signaling overhead required. This paper addresses these challenges by proposing an online scheduling algorithm that operates effectively even with partial, delayed device state information.

System Architecture and Methodology

The proposed framework considers a NOMA-aided MEC system where multiple IoT devices compete for limited wireless and computational resources at a base station. The system architecture, including the interaction between device-side queues and the BS-side processing modules, is illustrated in Figure 1.

System model of NOMA-aided MEC with multiple devices and a base station.

To manage the complexity and stochasticity of the network, the researchers developed a three-pillar approach:

  1. Lyapunov Optimization: This technique converts the long-term stochastic utility maximization problem into a series of per-slot deterministic subproblems. This allows the system to balance the tradeoff between high throughput and stable data queues (low latency) without requiring prior knowledge of network statistics.
  2. Convex Transformation: The per-slot NOMA power allocation problem is originally non-convex and computationally expensive. By introducing auxiliary variables, the authors transformed it into a convex form, reducing computational complexity from exponential to a manageable $O(M^{3/2})$, where $M$ is the number of devices.
  3. Partial Knowledge Modeling: Recognizing the overhead of constant feedback, the algorithm is designed to work with "approximate state information." Devices provide periodic feedback, and the BS schedules resources based on these slightly stale snapshots.

As shown in Figure 2, this methodology fills a critical gap in existing literature by addressing both stochasticity and partial device knowledge while maintaining asymptotic optimality.

Comparison of the proposed algorithm with existing literature across various optimization criteria.

Key Insights and Results

A central innovation of the algorithm is its queue-aware offloading decision. A device decides to offload or compute locally by comparing the lengths of its local versus offloading queues. If the offloading queue is congested, the device switches to local processing to maintain stability. Furthermore, the algorithm utilizes a control parameter, $V$, which allows network operators to tune the system toward either maximum theoretical throughput or lower queue latency based on application needs.

Simulation results, modeled after standard industrial IoT specifications with up to 500 devices, validate the algorithm's performance:

  • Throughput Gains: The NOMA-based approach outperformed traditional OFDMA-based scheduling by up to 85% in average system throughput.
  • Overhead Reduction: By utilizing the partial knowledge framework, signaling overhead was reduced by 50% compared to full-feedback schemes, with performance loss remaining bounded.
  • Scalability: Unlike competing algorithms that become unusable as device counts grow, the polynomial complexity of this approach ensures smooth scaling to hundreds of users.

Conclusion

This research provides a robust solution for managing massive connectivity in NOMA-aided MEC systems. By effectively decoupling long-term optimization and simplifying complex power allocation, the proposed algorithm achieves near-optimal utility with significantly reduced signaling requirements. Future work will focus on addressing hardware constraints in Successive Interference Cancellation (SIC) and the impact of high-speed device mobility on partial knowledge bounds.

Summary updated

Abstract

By exploiting the superiority of non-orthogonal multiple access (NOMA), NOMA-aided mobile edge computing (MEC) can provide scalable and low-latency computing services for the Internet of Things. However, given the prevalent stochasticity of wireless networks and sophisticated signal processing of NOMA, it is critical but challenging to design an efficient task offloading algorithm for NOMA-aided MEC, especially under a large number of devices. This paper presents an online algorithm that jointly optimizes offloading decisions and resource allocation to maximize the long-term system utility (i.e., a measure of throughput and fairness). Since the optimization variables are temporary coupled, we first apply Lyapunov technique to decouple the long-term stochastic optimization into a series of per-slot deterministic subproblems, which does not require any prior knowledge of network dynamics. Second, we propose to transform the non-convex per-slot subproblem of optimizing NOMA power allocation equivalently to a convex form by introducing a set of auxiliary variables, whereby the time-complexity is reduced from the exponential complexity to $\mathcal{O} (M^{3/2})$. The proposed algorithm is proved to be asymptotically optimal, even under partial knowledge of the device states at the base station. Simulation results validate the superiority of the proposed algorithm in terms of system utility, stability improvement, and the overhead reduction.
BibTeX
@article{hua2021online,
  author = {Meihui Hua and Hui Tian and Xinchen Lyu and Wanli Ni and Gaofeng Nie},
  title = {{Online Offloading Scheduling for NOMA-Aided MEC Under Partial Device Knowledge}},
  journal = {IEEE Internet of Things Journal},
  year = {2021},
  doi = {10.1109/jiot.2021.3091849},
}
Figure