Towards Carbon-Neutral Edge Computing: Greening Edge AI by Harnessing Spot and Future Carbon Markets

The considered situation is shown in Fig. 1, where multiple Internet of Things (IoT) devices are offloading their machine learning (ML) tasks to edge servers and the cloud server. In analogy with the assumption in work [30][31], edge servers may have multiple energy supplies including the power of grid and green. Thus carbon intensity in edge servers may be cheaper and lower than in the cloud server and changes dynamically because it relatives to the weather. According to the resource capacity of edge servers, we assume that there is a tiny neural network (TNN) model maintained at each edge server to process ML tasks, and a deep neural network (DNN) model is placed in the cloud server to achieve higher inference accuracy. Intuitively, processing ML tasks at the cloud server may incur higher carbon emissions due to the high carbon intensity, and high energy consumption of transmission and processing energy. Although executing ML tasks in edge servers causes less carbon emission, the accuracy loss may be higher which reduces the performance. Besides, to reduce carbon emission, the operator has its carbon emission rights (CER) issued by the government or government agency which is not free of charge and would be bought in a timely manner (in the carbon spot market with a higher price) or in a specified period (in the carbon future market with a relatively cheaper price) ¹¹1https://en.wikipedia.org/wiki/Carbon emission trading.

The operator is assumed to run the system in a discrete-time horizon $\{0,1,...,KT\}$ in which $K\in\{0,1,2,...\}$ is the number of time frames (e.g., minutes or hours) each of which contains $T(T>0)$ time slots (e.g., seconds or minutes). Therefore, the operator can purchase CER at each time slot on demand and at the beginning of each time frame on preserved. Generally, each ML task arrives in each time slot $\tau$. Similar to the study [32], we construct each computation-intensive ML tasks $i\in\mathcal{N}(\tau)$ ($N(\tau)$ is the set of arriving tasks at $\tau$ with $|N(\tau)|\leq N_{max}$) with a two-parameter tuple, i.e., $<H_{i}(\tau),F_{i}(\tau)>$. Specifically, $H_{i}(\tau)$ represents the input data size, and $F_{i}(\tau)$ denotes the computation workload. Through respective wireless channels, devices offload their tasks to edge servers and the cloud server, here we denote $\mathcal{M}=\{0,1,2,...,M\}$ as the total offloading locations, in which 0 denotes the cloud server and others denote edge servers. For each server, i.e., location $j\in\mathcal{M}$, we denote $A_{j}$ as the processed accuracy loss. Note that $A_{j}$ is the accuracy loss processed by the TNN model in edge server $j~{}(j>0)$ or by the DNN model in the cloud server $j~{}(j=0)$, and each location only maintains one model. As we have illustrated above, the accuracy loss achieved by the cloud server is lower than in edge servers. Besides, $P_{j}^{E}(\tau)$ and $P^{C}(\tau)$ are denoted to illustrate the energy consumption for ML task processing (in terms of processing per input data bit) in the edge server $j$ and the cloud server. The carbon intensity of edge server $j$ is denoted as $C_{j}^{E}(\tau)$ while the carbon intensity of the cloud server is denoted as $C^{C}(\tau)$. We use $R_{lt}(\tau)$ and $R_{rt}(\tau)$ to denote the price of CER purchased on-preserved and on-demanded accordingly. Furthermore, we introduce $r_{lt}(t)$, $r_{rt}(\tau)$ to illustrate the multi-timescale purchased CER amount in our collaboration system, respectively. We summarize the notations used in Table I.

For each time frame $kT$ $(k=0,1,...,K-1)$, in the beginning, i.e., $t=kT$, the operator will adopt the system information including the energy consumption metrics $P_{j}^{E}(\tau)$ of each edge server $j$ and $P^{C}(\tau)$ of the cloud server, the carbon intensity $C_{j}^{E}(\tau)$ of each edge server $j$ and $C^{C}(\tau)$ of the cloud server, and the on-preserved CER purchasing price $R_{lt}^{C}(t)$, then makes the decisions of CER purchasing on-preserved for the running of $T$ real-time slots in carbon future market. To avoid complicated deployment based on accurate but cost-significant forecast methods for on-preserved CER usage planning over multiple time slots in each time frame, the on-preserved CER in a time frame will be divided evenly, which means at time slot $\tau\in[t+1,t+T-1]$, there is $r_{lt}(\tau)=r_{lt}(t)/T$ preserved CER. The purchased amount of on-preserved CER $r_{lt}(t)$ can be optimized adaptively over time frames and the CER in need at each time slot can also be well supplemented by optimizing the on-demanded CER purchase. After the operator gets the information mentioned above and the on-demanded CER purchasing price $R_{rt}(\tau)$, it decides how much amount of CER $r_{rt}(\tau)$ purchased in the carbon spot market. Note that, the price of CER at different timescales is not the same, i.e., $R_{rt}(\tau)>R_{lt}^{C}(t)$, and it is difficult to maintain the right scale of CER in advance because of the difficulty of accurately capturing future demand.

Let $x_{ij}(\tau)$ be the binary indicator of ML task offloading ($x_{ij}(\tau)=1$) the task arriving at the beginning of $\tau$ to edge server $j>0$ or the cloud server $j=0$.

In each time slot $\tau\in[t+1,t+T-1]$, for edge servers, according to the ML task $i$’s input size $H_{i}(\tau)$, the energy consumption is given by $P_{total}^{e}(\tau)=\sum_{i}\sum_{j}x_{ij}(\tau)H_{i}(\tau)P_{j}^{E}(\tau)$; while for the cloud server, the energy consumption is given by $P_{total}^{c}(\tau)=\sum_{i}x_{i0}(\tau)H_{i}(\tau)P^{C}(\tau)$. As we have mentioned, we use $C_{j}^{E}(\tau)$ and $C^{C}(\tau)$ to denote the carbon intensity of edge server $j$ and the cloud server, respectively. So the carbon emission is

And the cost of purchasing CER can be expressed as

The inference accuracy loss of all ML tasks can be expressed as

Our objective mathematical problem P1 is

And the constraints are shown below:

Constraint (5) denotes that $x_{ij}(\tau)$ is a binary variable that is one if and only if task $i$ is offloaded to location $j$ in time slot $\tau$. Constraint (6) indicates that each ML task can be offloaded to only one location and constraint (7) shows that the physical resources in the edge server $j$ are restricted by $W_{j}(\tau)$. Constraint (8) indicates that the real needed CER cannot surplus the available CER. Besides, the cost of buying CER should not be beyond the following constraint:

However, it is not easy to minimize the inference accuracy loss (4) under the long-term time-averaged CER purchasing budget due to the unknown future system information and the coupling influence caused by the budget. Also, both the computing resource and CER constraints in (7) and (8) make the combinatorial nature of the ML task offloading decisions much more involved. Hence, an online algorithm is designed to coordinate the on-demanded and on-preserved CER purchasing methods in our work of minimizing problem P1, i.e., minimizing (4) subject to (5), (6), (7), (8) and (9) only using the current known information. Moreover, an efficient approximate scheme based on resource-restricted randomized dependent rounding is integrated into the two-timescale Lyapunov optimization to gain a near-optimal solution.

We first apply the Lyapunov optimization technique [16] to satisfy the carbon emission rights (CER) purchasing cost constraint in (9). Introducing a virtual queue $Q(\tau)$ for the operator:

Obviously, a larger value of $Q(\tau)$ means that the cost of purchasing CER exceeded the budget $R_{bug}$. Then we introduce the quadratic Lyapunov function

To further preserves system stability, the $T$-slot conditional Lyapunov drift is defined as

Inspired by the Lyapunov optimization technique [16] which minimizes $T$-slot drift-plus-penalty term, we further get:

here $V\geq 0$ evaluates how much attention is paid to the minimization of inference accuracy loss compared with the queue stability. The motivation for such a control parameter is as follows: Keeping $\Delta_{T}(\boldsymbol{\Theta}(t))$ towards a lower congestion state means to bug fewer CER, and consequently leads to a larger accuracy loss. On the contrary, keeping $\{\sum_{\tau=t}^{t+T-1}A(X(\tau))|\boldsymbol{\Theta}(t)\}$ at a smaller value to help us achieve a better performance in accuracy at the cost of the bigger value of queue. In the following, we will give Theorem 1 to further present the upper bound of (13).

Due to the page limit, we leave the proof of Theorem 1 in Appendix A of [33].

According to the deterministic bound shown in Theorem 1, therefore, solving our original problem equals minimizing the right hand of (13) subject to (5), (6), (7) and (8).

Unfortunately, solving this problem needs knowing future information, e.g., the resource’s price and carbon intensity as well as the queue length information. Though the operator can predict future statistics, the results may be less accurate and the prediction errors may degrade the operator’s achieved performance which may need to be considered. Looking deeper into the $\boldsymbol{\Theta}(t)$, it depends on the CER purchasing decisions $r_{lt}(\tau)$ and $r_{rt}(\tau)$. Hence, we propose to address the unknown information by making an approximation to set the future queue backlog values as the current value, i.e., $Q(\tau)=Q(t)$ when $\tau\in[t,t+T-1]$. After taking this approximation, the “loosened $T$-slot drift-plus-penalty bound” is shown in the following theorem.

We prove Theorem 2 in Appendix B of [33].

Substituting $A(X(\tau))$ and $C(R(\tau))$ into inequality (15), we finally get the final optimization objective P2

In the following, we first decompose problem P2 then design an online algorithm to deal with it.

Algorithm 1 presents our algorithm explicitly. We ignore the term $Q(t)R_{bug}$ in Eq. (17) and Eq. (18) because these terms are constants at each real-time slot and have no influence on decisions. Besides, the variable $r_{rt}(\tau)$ and the price $R_{rt}(\tau)$ are ignored in Eq. (17) since we assumed that the price of CER purchasing on-preserved is always lower than on-demanded. That is to say, the operator will buy enough on-preserved CER which is cheaper, and does not need to bug any on-demanded CER at time slot $t=kT$. Since each slot’s $\boldsymbol{\Theta}(t)$ is already known, and the expectation is conditioned on it, the expectation of Eq. (17) and Eq. (18) can be eliminated. As presented in Fig. 2, for each time frame $kT$ $(k\in\{0,1,..,K-1\})$, at the beginning $\tau=kT$, the operator devotes to solving problem P3 to obtain the on-preserved CER $r_{lt}(t)/T$ for each time slot in frame $kT$; while at each time slot $\tau\in[kT+1,kT+T-1]$, the operator intends to solve problem P4 to get the on-demanded CER $r_{rt}(\tau)$ at each time slot.

Unfortunately, problem P3 and P4 both can be proven are NP-hard [34], to solve it, we will introduce an efficient approximated algorithm to get the near-optimal solution.

There comes the idea that once the integral constraint (5) is relaxed into the linear constraint, the relaxed problem P3 (P4) becomes the standard linear programming (LP) problem and thus using simplex method [35] or other linear programming optimization technique such as [36] to easily solve. After getting the optimal fractional policies, we need a proper rounding method to get binary solutions while maintaining the capacity constraint (7) and CER constraint (8). Algorithm 2 shows our rounding algorithm in detail.

We first relax the integral constraint (5), and obtain the relaxed-P3 named problem $\tilde{\textbf{P3}}$ as follows:

In the same way, problem $\tilde{\textbf{P4}}$ (relaxed-P4) is presented by:

Then we invoke simplex method on solving $\tilde{\textbf{P3}}$ ($\tilde{\textbf{P4}}$) thus get fractional offloading decisions $\boldsymbol{\dot{X}}$ (i.e., $\dot{x}_{ij}$) and purchase amount of CER decisions $\boldsymbol{\dot{R}}$ (i.e., $\dot{r}_{lt}$ and $\dot{r}_{rt}$). For fractional offloading solutions $\boldsymbol{\dot{X}}$, a straightforward way is use Pr$[\tilde{x}_{ij}=1]=\dot{x}_{ij}$ to obtain binary decisions $\tilde{x_{ij}}$. However, using this method will sometimes incur infeasible solutions. For example, there may be a situation that all fractional solutions $\dot{x_{ij}}$ where $j$ equals all are rounded to 1, incurring the high cost of purchasing CER in cloud $j=0$ or violating constraint (7) of edge servers $j>0$. Considering this deficiency, we are encouraged to exploit the dependence of fractional solutions $\dot{x_{ij}}$ to improve optimally while obeying the computing resource and CER constraints in (7) and (8) to design a proper resource-restricted randomized dependent rounding algorithm (R3DRA). Therefore, we will explore the dependence of decisions randomly. The key idea of R3DRA is the existence of correspondence between one rounded-up variable and another rounded-down variable, which means that there exists a compensatory between these two random variables to ensure the capacity constraint in the edge server.

We give a simple illustration of R3DRA for solving problem $\tilde{\textbf{P3}}$ ($\tilde{\textbf{P4}}$). After we get the optimal fractional solutions $(\boldsymbol{\dot{X}},\boldsymbol{\dot{R}})$, then we denote two sets for each ML task $i$: one floating set $\tilde{K}_{i}^{-}=\{m|\dot{x}_{im}\in[0,1]\}$ and one rounded set $\tilde{K}_{i}^{+}=\{m|\dot{x}_{im}\in\{0,1\}\}$. We further denote a probability coefficient $p_{im}$ as well as a weight coefficient $s_{im}$ for each fractional $\dot{x}_{im}$. The probability coefficient $p_{im}$ is initialized as $\dot{x}_{im}$ while the weight coefficient $s_{im}$ is initialized as $F_{i}$. R3DRA runs in a series iteration to round each fractional element in set $\tilde{K}_{i}^{-}$. Specifically, in each iteration, there are two elements $m_{1}$ and $m_{2}$ randomly selected from set $\tilde{K}_{i}^{-}$, and we further introduce the coupled coefficient $\epsilon_{1}$ and $\epsilon_{2}$ in order to adjust the value of $p_{im_{1}}$ and $p_{im_{2}}$. Pay attention to that, after each adjustment, one of $p_{im_{1}}$ and $p_{im_{2}}$ is at least 0 or 1, and then we set $\tilde{x}_{im_{1}}=p_{im_{1}}$ or $\tilde{x}_{im_{2}}=p_{im_{2}}$. Therefore, in each round, fractional elements in set $\tilde{K}_{i}^{-}$ will at least decrease by 1. Eventually, when there is only one element in $\tilde{K}_{i}^{-}$, we set $p_{im}=1$ if the capacity $\sum_{i}x_{ij}F_{i}$ is not longer than $W_{j}$ and otherwise set $p_{im}=0$. As we have mentioned, the detailed expression can be seen in Algorithm 2.

It’s worth noting that R3DRA is cost-efficient because it avoids the occurrence to offload all ML tasks to clouds to avoid incurring the high cost of purchasing CER, and is computation-efficient with the complexity only of $O(N|\mathcal{M}|)$. Therefore, the complexity of TTOA is $O(N|\mathcal{M}|KT)$.

Due to space limits, the proof is given in Appendix C of our online technical report [33]. The theorem above indicates that our proposed R3RDA solution is efficient, and can guarantee an approximate solution within a bounded neighborhood of the optimal solution for problem P2.

We prove Theorem 3 and Theorem 4 in detail in Appendix C and D of [33], respectively. From the above theorems, we can adjust the value of $V$ thus to balance the performance gap of inference accuracy well. Next, we will give the performance evaluation driven by the real carbon intensity trace to verify our theoretical analysis.

We consider there are $M\in\{5,10,15,20\}$ offloading locations consisting of $\{4,9,19,49\}$ edge servers and one cloud server and the number of ML tasks $N_{max}\in\{5,10,20,50\}$. Similar to many existing studies which researched the model compressing influenced the accuracy loss such as [37], the diverse inference accuracy loss of the TNN models of edge servers is set by randomly generating over the range $[10\%,15\%]$. In contrast, the inference accuracy loss of the DNN model in the cloud server is set as $2\%$. The input data of each ML task is set as $[1,10]*10^{8}$ bits, and the workload of each ML task is set to consist of $[5,10]*10^{11}$ cycles both of them can be referenced to [38]. We consider the resource price in each edge server to be in $[2,5]*10^{-5}$ bit/J while in the cloud server is in $[3,5]*10^{-4}$ bit/J both of which are similar to [39]. And the computation capacity of edge servers is assumed to be $[2,5]*10^{12}$ CPU cycles. The number of arriving ML tasks in the system is randomly generated over the range [1,10]. The carbon intensity of edge servers and the cloud server is according to the regional carbon intensity data in the UK (per 30 mins) of National Grid ESO [40], and we use the 5 regions’ data to represent the carbon intensity of edge servers and the cloud server. We assume the price of purchasing CER $R_{lt}(\tau)$ and $R_{rt}(\tau)$ are subject to uniform random distribution and satisfy $\mathbb{E}\{R_{rt}(\tau)\}>\mathbb{E}\{R_{lt}(\tau)\}$, we also assume that $\mathbb{E}\{R_{lt}(\tau)\}=1.5\$$, $\mathbb{E}\{R_{rt}(\tau)\}=3.0\$$. We evaluate our algorithms’ performance by setting the control parameter $V\in[1,10]*10^{8}$ under the long-term time-averaged CER purchasing budget $R_{bug}=3.25*10^{8}$ cost units. The simulation runs on Matlab, where a total of $KT=1500$ (in which $T=15$ and $K=100$) randomized realizations are averaged for the current given system information. Table II gives the simulation parameters in detail.

We compare our algorithm’s performance with three benchmarks which are shown below:

1. 1.

   All to Cloud algorithm (ACloud): Always choose the cloud server to execute ML tasks, which will achieve the best performance in inference accuracy loss but incur the highest CER purchasing cost and is an extreme contrast.

2. 2.

   One Time-scale algorithm (OTime): We zoom in on our smaller timescale, which means making our two-timescale time slot units into one. In our following experiments, the one-time slot is set as 30 minutes in this algorithm, and thus we need to decide the offloading decisions and each slot’s CER purchasing amount.

3. 3.

   Greedy algorithm (Greedy): The core idea of this algorithm is to achieve performance greedily while obeying the constraint of CER purchasing, which compares the cost of each possible offloading mode and then selects the better performance one greedily to offload the ML tasks under the CER purchasing constraint.

We first show the performance of our TTOA with different values of $V$ with $T=15$ (7.5 hours a time frame). As shown in Fig. 3(a), our proposed TTOA achieves excellent performance. For instance, it can reduce $15\%$ of the inference accuracy loss compared to Greedy and gets at most $3\%$ performance loss compared with ACloud when $V=8*10^{8}$. Besides, with the control parameter $V$ increasing, the accuracy loss will reduce, this verifies the analytical analysis in Eq. (22). From Fig. 3(b), we can see the average queue backlog is approximately proportional to the control parameter $V$ which verifies the analytical analysis in Eq. (23), and our TTOA achieves the lowest queue backlog size. Obviously, a larger value of $V$ means that we pay more attention to minimizing accuracy loss than obeying the purchasing CER cost budget. From Fig. 3(c), it is clearly seen that with a larger value of $V$, more ML tasks will be influenced by the cloud server hence achieving lower accuracy loss in Fig. 3(a) and higher queue backlog size in Fig. 3(b).

The performance of the cost of purchase with different values of control parameter $V$ can be seen in Fig. 4(a), in which we can see the cost of purchasing CER grows with the values of $V$ increasing, and our TTOA uses the lowest cost while the ACloud causes the highest cost. For instance, when $V=8*10^{8}$, our TTOA achieves an up to $57.3\%$ cost of purchase reduction over the ACloud. And we further evaluate the performance of the cost of purchasing CER with different time slots in Fig. 4(b). We can know that as the time slot increases, the cost of the CER purchase in our TTOA decreases and finally blows the long-term CER purchasing budget $R_{bug}$. Therefore, the performances as shown in Fig. 4(a) and Fig. 4(b) have verified the analytical analysis in Eq. (24), i.e., the time-average carbon emission purchasing cost bound is roughly proportional to $V$ and lower than CER purchasing budget $R_{bug}$. It is obvious to know that our TTOA achieves the lowest carbon emission. As can be seen in Fig. 4(c), to verify the robustness of our TTOA, we further evaluate the performance while the CER purchasing price is in the Gaussian distribution in which the mean emission right price equals the uniform distribution above. It is clear to know that TTOA still performs the best performance in terms of the accuracy loss of the implementation which is the same as in the uniform case above.

There is an intuition that a larger budget may supply more effort for ML tasks offloading. In Fig. 5(a), Low, Middle, and Large are set separately as $2.25*10^{8}$, $3.25*10^{8}$, and $4.25*10^{8}$ cost units while the control parameter $V=3*10^{8}$. We see that with the long-term CER purchasing budget $R_{bug}$ increasing, compared to OTime and Greedy, our TTOA is significantly improved. For example, given the long-term CER purchasing budget $R_{bug}=3.25*10^{8}$ cost units, the accuracy loss of TTOA is reduced by $55.2\%$.

In Fig. 5(b), we increase the value of each time frame $T$ from 2.5 hours to 15 hours with $V=3*10^{8}$ (i.e., $T\in\{5,10,15,20,25,30\}$ and each single time slot is set as 30min in coordinate with the carbon intensity data trace), finding out that though the fluctuation of accuracy loss is not large, our TTOA still gains better performance than OTime. Especially, in our simulation, the accuracy loss is minimized when $T=7.5h$. The accuracy loss of the OTime is always higher than TTOA no matter what $T$’s value is. This further evaluates TTOA which contains a two-timescale and is robust to the change of $T$. Therefore though setting the value of $T$ appropriately, we can as far as possible meet the on-preserved CER period and minimize the accuracy loss. We realize that although the values of $T$ are inappropriate, we can still make real-time CER purchasing $R_{rt(\tau)}$ to offset supply and demand nicely.

We conduct the performance of accuracy loss and queue backlog size under different CER purchasing prices $\mathbb{E}\{R_{lt}(\tau)\}$ and $\mathbb{E}\{R_{rt}(\tau)\}$ in Fig. 5(c) where $\mathbb{E}\{R_{lt}(\tau)\}=0.5*\mathbb{E}\{R_{rt}(\tau)\}$. Particularly, we increase the price of $\mathbb{E}\{R_{lt}(\tau)\}$ from $0.5\$$ to $2.5\$$ (i.e., increase the price of $\mathbb{E}\{R_{rt}(\tau)\}$ from $1\$$ to $5\$$). Obviously, when the price is small, we can not only get a lower accuracy loss but also gain a lower purchase cost. Besides, when $\mathbb{E}\{R_{lt}(\tau)\}$ changes from $0.5\$$ to $1.0\$$ the accuracy loss increase seriously, while $\mathbb{E}\{R_{lt}(\tau)\}$ changes from $2.0\$$ to $2.5\$$ the queue backlog increase a lot. This is due to the limitation of the pre-defined long-term CER purchasing budget.