Energy Efficient Offloading Policies in Multi-Access Edge Computing Systems with Task Handover

Recent studies on offloading policies in MEC systems have explored various aspects of this problem, including time-varying nature of transmission channels [13], partially offloading policies [14], and the combination of offloading and dispatching processes [15]. Additionally, joint planning of MEC and other techniques, such as edge server deployment [16], network slicing [17], and 3D rendering [18], have been investigated to enhance system performance. While many of these works aim to improve performance metrics like latency or throughput, some also consider energy efficiency as an additional objective.

Task offloading in MEC systems is often a non-convex optimization problem due to conflicting objectives and constraints. To tackle this, many studies have adopted deep reinforcement learning (DRL) approaches to obtain optimal task offloading policies [7, 19]. Common DRL methods include deep Q-network (DQN) [20], deep deterministic policy gradient (DDPG) [21], TD3 [22] etc. Despite the potential of these methods, their high computational complexity and convergence challenges often make them less suitable for real-time and energy-efficient decision-making in dynamic MEC environments, where reliable system performance is critical.

In contrast, several low-complexity heuristic algorithms have been proposed to overcome these computational challenges. For example, a dependency-aware edge-cloud collaboration strategy was introduced in [23] to minimize task completion time by mitigating tasks in an energy-efficient order. The Lyapunov optimization technique was applied in [24] to balance energy efficiency and queue length under unknown channel conditions. Other approaches, including game theory [25] and auction theory [26], were also proposed to maximize the net profit of MTs by allowing them to bid for communication or computation resources.

The impact of task handovers in MEC systems, particularly when MTs move between different network zones, has been a growing focus in recent research. While several works (e.g. [2, 4, 6, 3, 5, 27, 25]) considered the effect of MT handovers on offloading decisions, many of these studies concentrate on re-allocation of computational resources rather than the full offloading process. For example, constraints on MT computational capacities and CPU frequencies were examined in [4, 2]. Some studies focused on the availability of transmission channels, considering bandwidth limitations [27, 25]. However, the unpredictable nature of wireless transmissions, such as random fading, has been less studied in the context of task offloading during handovers.

More recent research aimed to improve the overall performance of resource allocation by incorporating handover prediction [28, 29]. For example, a machine learning based prediction mechanism was applied in [27] to forecast future specifications of offloaded tasks and reassign offloading destinations after a set number of time slots. While such methods improve resource allocation performance, they often rely on fixed periodic reassignment intervals, limiting their flexibility in real-time scenarios.

To address the computational and scalability challenges of MEC offloading in dynamic environments, recent studies have proposed the use of multi-armed bandit (MAB) algorithms [30, 31]. These algorithms are particularly well-suited to balancing exploration and exploitation in resource-constrained environments. For example, a contextual online vehicular task offloading policy was explored in [32] using an online bandits approach to improve energy efficiency and reduce delays in vehicular networks. Our approach builds on these concepts by using a RMAB framework, which is more appropriate for dynamic environments where resource availability and task requirements change over time. This RMAB-based method incorporates real-time predictions of task handovers and prioritizes resources based on marginal costs, achieving scalable and energy-efficient resource allocation in large-scale MEC systems.

To summarize, compared with existing studies aiming at improving energy efficiency in MEC, our study offers a more comprehensive, holistic and nuanced approach. We address key limitations in current research by explicitly modeling the dynamic and heterogeneous nature of MEC systems, particularly in scenarios with frequent task handovers and real-time adaptability. Our proposed RMAB-based framework optimizes energy efficiency by leveraging predictive information about MT handovers and dynamically allocating resources. This newly proposed low-complexity algorithm effectively bridges the gap in previous studies and enhances the scalability and practicality of energy-efficient resource management in large-scale MEC environments.

Consider a wireless network with orthogonal sub-channels, which establishes connections between MTs and communication nodes (CNs), such as base stations and access points. Computing tasks generated by MTs can be appropriately offloaded to CNs through the sub-channels. As CNs are equipped and/or connected (through wired connections) with more storage, computing and networking resources (CPU, GPU, RAM, disk I/O, etc.), they are generally considered preferable for executing computationally intensive tasks than personal MTs. This offloading operation can liberate MTs from being overloaded and achieve higher energy efficiency in the network. We refer to all these storage, computing and networking equipped and/or connected with the CNs as the service components (SCs), which are classified in groups (referred to as SC groups thereafter) based on their functionalities and geographical locations. We denote $K$ as the number of SC groups at the network edge, and let $C_{k}\in\mathbb{N}_{+}$ represent the capacity of SC groups $k\in[K]$, which is the total number of SC units in the SC group. CNs are connected to the central cloud via wired connections, enabling additional task offloading when required. Tasks offloaded by MTs can eigher be processed at the network edge by SC groups or forwarded to the cloud for completion. We assume that the cloud has infinite capacity for all SC groups.

Consider a case where MTs, with similar hardware/software profiles, in the same geographical area have homogeneous channel conditions for transmitting to and from CNs in a certain destination area, labeled by $\ell$, which locates a set of SC groups $\mathscr{K}_{\ell}\subset[K]$. There are in total $L\in\mathbb{N}_{+}$ such destination areas (that is, $\ell\in[L]$) at the network edge, and we assume without loss of generality that all $\mathscr{K}_{\ell}$ are non-empty and mutually exclusive for different $\ell\in[L]$. We label all such channels used to connect the $L$ areas, each of which is equipped with SC groups $\mathscr{K}_{\ell}$ ($\ell\in[L]$), as $i=1,2,\ldots,I$. Each channel $i\in[I]$ can support at most $N_{i}\in\mathbb{N}_{+}$ orthogonal sub-channels due to technical constraints such as total bandwidth limits. When an MT wishes to utilize computational/storage resources in area $\ell$, a subset of the $I$ channels are eligible to support the connection between the MT and the CNs in area $\ell$. If this MT is too far away and cannot be connected to any CN in area $\ell$, then none of the $I$ channels can be used between the MT and any SC group in $\mathscr{K}_{\ell}$. We assume that $I\geq L$ - for each area $\ell$, the SC groups may be connected via more than one wireless channels.

Consider a simple example of the network model in Figure 1, where there are $K=2$ SC groups (SC1 and SC2) locate in the same area $\ell=1$ (with $L=1$) with $I=2$ channels, used by two base stations (CN1 and CN2). For MTs with similar hardware/software profiles, if they are in the coverage of CN 1, or equivalently the coverage of Channel 1, they can connect to both SC groups in the area $\ell=1$ through Channel 1. Similarly, the connections can be established between the SC groups and the MTs through Channel 2. In this case, both channels are eligible to establish connections to the SC groups in the area $\ell=1$.

Consider $J\in\mathbb{N}_{+}$ classes of moving MTs that can be classified by the differences in their locations, moving speeds and directions, application styles and relevant requirements on computing resources. In particular, we consider a scenario where MTs in the same class can upload/download data through the same set of eligible channels and potentially connect to the same set of SC groups. In this context, a moving MT may change its class from time to time. For instance, in Figure 1, all MTs, belonging to the same class when they start moving from the left circle, may be assigned to different classes after they have arrived in the right circle. The MTs can be classified manually by the service provider and/or automatically through conventional techniques, such as signature matching [33], based on historical features of the network traffic and mobility prediction techniques (for handover), such as [34].

We refer to the offloaded tasks generated by MTs in class $j\in[J]$ as $j$-tasks. We consider tasks of the same type to be those generated by MTs in the same class, with similar moving directions and speeds, with the same application styles, and with the same requirements on SCs. For a certain type of task, not all SC groups at the network edge are necessarily able to serve it due to geographical or functional dis-match. If a $j$-task is accommodated by an SC in group $k\in[K]$ that is able to serve it at the network edge, $w_{j,k}\in[C_{k}]$ units of the SC are occupied by this task until it is completed. Occupied SC units will be simultaneously released upon the completion of the task, and can be reused for future tasks [35]. If a $j$-task cannot be served by units in SC group $k$, because of un-matched geographical locations or required functions, define $w_{j,k}\rightarrow+\infty$, or any other integer greater than $C_{k}$, to prohibit these tasks from being assigned there.

With $I$ channels in total, an MT offloading a $j$-task transmits through a sub-channel of channel $i\in[I]$ at an achievable rate

where $p_{i,j}\in\mathbb{R}_{0}$, $h_{i,j}\in\mathbb{R}_{+}$, $B_{i}\in\mathbb{R}_{+}$ and $N_{0}\in\mathbb{R}_{+}$ are the transmission power, channel gain, bandwidth of each channel and the noise power, respectively [36, 37]. If the signal-to-noise-ratio (SNR) $(p_{i,j}h_{i,j})/N_{0}$ is smaller than $20$dB, then reliable connections cannot be established, and the channel is regarded as not available.

We consider the situation where offloaded tasks with relatively small sizes are dominant in the network, so that the computing power of SCs located at the edge of the network or in the central cloud are sufficient to complete the services of the requests in a relatively short period of time. In this sense, the duration of computational operations of offloaded tasks is generally much shorter than the transmission time between the MTs and the CNs or the cloud; that is, the processing time of an offloaded task is dominated by the transmission time between the MT and the CN for tasks completed at the network edge, and the transmission time between the MT and the central cloud via the network edge for tasks offloaded to the central cloud. In this context, a wireless sub-channel between the MT and the CN needs to be reserved for data transmission for the entire period of the offloaded task, no matter whether the task is addressed at the network edge or in the central cloud [38]. If no such an available sub-channel (all sub-channels are fully occupied), the MT cannot offload this task to any CN, and the task has to be computed locally. In this case, the task never reaches the network edge, and any scheduling policies employed at the network edge will not affect the power consumption.

In a MEC network, MTs move across different areas, requiring connections to different CNs through different sub-channels. When an MT is sending data to or receiving results from an SC, it may change the connected CNs when moving into different places covered by different CNs, leading to task handover between CNs, as illustrated in Figure 1. For the tasks generated by such MTs, other CNs with available sub-channels in their moving directions should be prepared and reserved to ensure the quality of the connections. For instance, in Figure 1, CNs 1 and 2, some SC units, and a sub-channel in each of the channels are highlighted in red, meaning that they are occupied/reserved by a task generated by the moving MTs.

For the tasks that are offloaded to the cloud, two transmission segments, namely from the MT to the network edge and from the network edge to the cloud, are requested. For notational consistency, define a special SC group $K+1$, which has infinite capacity $C_{K+1}\to+\infty$, for the SC units in the cloud. As the CNs and the cloud are usually connected by a cable backbone network, we can assume that the transmission time between the network edge and the cloud, denoted by $D_{0}$, is the same for all tasks of the same class. Therefore, we denote the expected duration of $j$-tasks computed in the cloud and transmitted via an CN in destination area $\ell$ through a sub-channel in channel $i$ as $1/\mu_{i,j}+D_{0}$ [39]. Note that $K+1$ does not belong to any destination area $\ell\in[L]$ located at the network edge.

Power consumption of the network edge consists of static and operational power. Static power is the essential consumption incurred when an SC group is activated (which means the hardware components associated with the SC group must be powered on and connected to the network); while the operational power is consumed when SC units are engaged in processing offloading tasks. In a dynamic system such as a wireless network, the amount of operational power consumption is affected by the real-time utilization rate of the SCs. Let $\varepsilon_{k}^{0}\in\mathbb{R}_{+}$ and $\varepsilon_{k}\in\mathbb{R}_{+}$ represent the amounts of the static power and the operational power consumption per SC unit in group $k\in[K]$, and define the expected power consumption of an SC unit for computing a $j$-task in the cloud as $\bar{\varepsilon}_{j}\in\mathbb{R}_{+}$. Similar power consumption models have been empirically justified and widely applied in existing research [40]. Because of its dependencies on the dynamic states of the network, a detailed discussion about the power consumption of the network edge will be provided in Section IV.

Along with the Whittle relaxation technique [11], we randomize the action variables and relax Constraints (5), (2) and (3) to

and

respectively. For $i,i^{\prime}\in[I]$, $j\in[J]$, $k\in\mathscr{K}$, define

and for $x\in\mathscr{X}_{i,i^{\prime},j,k}$, define

which takes values in $[0,1]$. Let $\bm{\alpha}^{\phi}_{i,i^{\prime},j,k}\coloneqq(\alpha^{\phi}_{i,i^{\prime},j,k}(x):x\in\mathscr{X}_{i,i^{\prime},j,k})$, and let $\tilde{\Phi}$ represent the set of all the policies determined by the randomized action variables $\bm{\alpha}^{\phi}_{i,i^{\prime},j,k}$ for all $i,i^{\prime}\in[I]$, $j\in[J]$, and $k\in\mathscr{K}$. We refer to the problem

subject to Constraints (8), (9) and (10) as the relaxed problem. Objective (13) is derived from Objective (6) by replacing $\Phi$ with $\tilde{\Phi}$. Since $\Phi\subset\tilde{\Phi}$ and Constraints (5), (2) and (3) are more stringent than Constraints (8), (9) and (10), any policy applicable to the TOSP will also be applicable to the relaxed problem; while, a policy for the relaxed problem is not necessarily applicable to the TOSP. It follows that the relaxed problem achieves a lower bound for the minimum of TOSP.

Consider a stable system with existing stationary distribution $\boldsymbol{\pi}^{\phi}\in[0,1]^{|\mathscr{X}|}$ in the long-run case under a given policy $\phi\in\tilde{\Phi}$, we write the dual function of the relaxed problem as

where $\boldsymbol{\nu}\in\mathbb{R}_{0}^{J}$, $\boldsymbol{\gamma}\in\mathbb{R}_{0}^{K}$, and $\bm{\eta}\in\mathbb{R}_{0}^{I}$ are the Lagrange multipliers for Constraints (8), (9), and (10), respectively. Following the Whittle relaxation [11] and the restless bandit technique for resource allocation [12], the minimization in Eq. (14) can be decomposed into $I^{2}J(K+1)$ independent sub-problems that are, for $(i,i^{\prime},j,k)\in[I]^{2}\times[J]\times[K]$,

and, for $(i^{\prime},i,j)\in I^{2}\times[J]$,

where recall that each policy $\phi\in\tilde{\Phi}$ is determined by the action variables $\alpha^{\phi}_{i,i^{\prime},j,k}(x)$ for $x\in\mathscr{X}_{i,i^{\prime},j,k}$. In particular,

In this context, the computational complexity of each sub-problem is linear to the size of $\mathscr{X}_{i,i^{\prime},j,k}$ - alternatively, $\min\bigl{\{}\lfloor C_{k}/w_{j,k}\rfloor,N_{i},N_{i^{\prime}}\bigr{\}}$. Together with the independence between those sub-problems, the computational complexity to achieve the minimum in Eq. (14) is linear in $I^{2}$, $J$ and $K$. We have the following corollaries of [12, Proposition 1].

Corollary 1 indicates the existence of a threshold-style policy, satisfying Eq. (18), that is optimal to the sub-problem associated with $(i,i^{\prime},j,k)$. Although there also exists a threshold-style policy that achieves the minimum of the sub-problems, the minimum of the sub-problems is only a lower bound of the minimum of the original TOSP described in Objective (6), Constraints (5), (2) and (3), and the threshold-style policy described in Eq. (18) is in general not applicable to the TOSP. The key is to establish a connection between the sub-problems and the TOSP, and then we can translate the threshold-style policy to those applicable, scalable and near-optimal to the original TOSP.

Following the tradition of the restless bandit studies in the past decades, we refer to the real number $\psi_{j}(i,i^{\prime},k)$ as the index associated with the bandit process $\{X^{\phi}_{i,i^{\prime},j,k}(t),t\geq 0\}$, which intuitively represents the marginal cost of selecting the tuple $(i,i^{\prime},k)$ to serve a $j$-task. For the threshold-style, optimal policy, tuples $(i,i^{\prime},k)$ with smaller indices are prioritized to have $a^{\phi}_{i,i^{\prime},j,k}(X^{\phi}_{i,i^{\prime},j,k}(t))=1$ than those with larger indices.

In [11], Whittle proposed the well-known Whittle index policy that always prioritizes bandit processes with the highest/lowest indices and conjectured asymptotic optimality of the Whittle index policy to the original problem. In subsequent studies such as [12, 43], the Whittle index policy has been proved to be asymptotically optimal in special cases and/or numerically demonstrated to be near-optimal.

However, unlike the past work, exempli gratia, [42, 43], the index $\psi_{j}(i,i^{\prime},k)$ described in Eq. (19) is not directly computable. It is dependent on the unknown multipliers $\gamma_{k}$, $\eta_{i}$ and $\eta_{i^{\prime}}$ due to the inevitable capacity constraints described in Constraints (2) and (3). These capacity constraints substantially complicate the analysis of the TOSP, and, more importantly, prevent existing theorems related to bounded performance degradation from being directly applied to the TOSP.

In Section V-B, we will discuss the methods to approximate the indices. Based on the approximated indices (representing the marginal costs), we propose heuristic policies applicable and scalable to the original TOSP, and demonstrate their effectiveness with respect to energy efficiency in Section VI.

Let $\bm{\nu}=\bm{\nu}^{\textup{*}}$, $\boldsymbol{\gamma}=\boldsymbol{\gamma}^{\textup{*}}$ and $\bm{\eta}=\bm{\eta}^{\textup{*}}$ represent the optimal dual variables of the relaxed problem described in Objective (13), Constraints (8), (9) and (10). Based on [12, Theorem EC.1] and Corollary 1, we have the following proposition.

The proof of Proposition 1 is provided in Appendix B. We say such a policy $\varphi$ is asymptotically optimal to TOSP. Asymptotic optimality is appropriate for large-scale systems with highly dense and heterogeneous mobile users, MEC servers/service components, base stations, access points, et cetera.

Recall that, from Corollary 1, the threshold-style policy $\phi$ satisfying Eq. (18) minimizes the right-hand side of the dual function in Eq. (14) (that is, minimize all the sub-problems), but such a policy is in general not applicable to the TOSP, and this minimum is only a lower bound of the minimum of the TOSP. The threshold-style policy $\phi$ reveals intrinsic features of the bandit processes and quantifies them through the indices, $\psi_{j}(i,i^{\prime},k)$, representing the marginal costs of selecting certain bandit processes. These indices can then be utilized to construct effective policices, such as the $\varphi$ in Proposition 1, applicable to the original TOSP. However, the exact values of the indices that are able to lead to asymptotic optimality remain an open question because of the unknown $\boldsymbol{\gamma}$ and $\bm{\eta}$.

Intuitively, the Lagrange multipliers $\boldsymbol{\gamma}$ and $\bm{\eta}$ represent the marginal budgets for running out the network capacities described in Constraints (9) and (10), respectively. When an SC or a communication channel exhibits heavy traffic, it should become less popular to incoming tasks, which can be adjusted by the attached multipliers $\boldsymbol{\gamma}$ or $\bm{\eta}$ to the indices. In other words, the multiplier associated with a capacity constraint of an SC or a channel with heavy traffic is expected to be large; while for those SCs or channels with light traffic or sufficiently large capacities, the corresponding multipliers should remain zero. We refer to $\boldsymbol{\gamma}\in\mathbb{R}_{0}^{K}$ and $\bm{\eta}\in\mathbb{R}_{0}^{I}$ as the capacity coefficients attached to the indices.

On the other hand, observing $\psi_{j}(i,i^{\prime},k)$ in Eq. (19), apart from the items related to $\boldsymbol{\gamma}$ and $\bm{\eta}$, the remaining item is, for $i,i^{\prime}\in[I]$, $j\in[J]$, and $k\in\mathscr{K}$

which is in fact the expected power consumption per unit service rate on SC $k$ contributed by the $j$-tasks, or equivalently the reciprocal of the achieved service rate per unit power consumption. We refer to the achieved service rate per unit power consumption of a certain SC as its energy efficiency. Less marginal costs of selecting certain tuples $(i,i^{\prime},k)$ imply SCs with higher energy efficiencies. The phenomenon coincides with a special case of the RMAB process studied in [43] but further considers the heterogeneous task requirements and complex capacity constraints over heterogeneous network resources.

In this context, for the TOSP described in Objective (6), Constraints (5), (2) and (3), we propose a policy that always prioritizes tuples $(i,i^{\prime},k)$ with higher $\psi_{j}(i,i^{\prime},k)$ for the $j$-tasks, for which the capacity coefficients $\boldsymbol{\gamma}$ and $\bm{\eta}$ are given a prior through sensible algorithms. We refer to this policy as the Highest Energy Efficiency with Adjusted Capacity Coefficients (HEE-ACC). More precisely, for $j\in[J]$ and $\bm{x}\in\mathscr{X}$, define a subset of tuples $\mathscr{T}_{j}(\bm{x})\subset[I]^{2}\times\mathscr{K}$ such that, for any $(i,i^{\prime},k)\in\mathscr{T}_{j}(\bm{x})$, $u_{j}(i,i^{\prime},k)>0$,

and

The set $\mathscr{T}_{j}(\bm{x})$ is the set of available tuples $(i,i^{\prime},j)$ that can serve a new $j$-task with complied capacity constraints (2) and (3) when $\bm{X}^{\phi}(t)=\bm{x}$. The action variables for HEE-ACC are given by

where if $\arg\min$ returns more than one tuples $(i,i^{\prime},k)$, then we select the one with the highest $u_{j}(i,i^{\prime},k)$. In Algorithm 1, as an example, we provide the pseudo-code of implementing HEE-ACC. Note that Algorithm 1 is a possible but not unique way of implementing HEE-ACC. The computational complexity of implementing HEE-ACC is at most linear logarithmic to the number of possible tuples $|\{(i,i^{\prime},k)\in I^{2}\times\mathscr{K}|u_{j}(i,i^{\prime},k)>0\}|$, mainly dependent on the complexity of finding the tuple with smallest index and checking tuples’ availability with respect to the capacity constraints.

It remains to adjust the values of the capacity coefficients $\boldsymbol{\gamma}$ and $\bm{\eta}$, which should be adversely affected by the SCs and channels’ remaining capacities.