## 4 ARIMA-BP-Based Selective Offloading Strategy
### Estimation for Computation Capacity of Edge Cloud by ARIMA-BP
#### 4.2.1 Time Series Prediction  
The Auto-Regressive Integrated Moving Average (ARIMA) model is composed of the auto-regressive model (AR) and the moving average model (MA). It is the most commonly used non-stationary time-series prediction model. The basic idea of the modeling is to use the difference method to smooth the non-stationary time-series. The time-series is predicted and analyzed by observing the three parameters of the correlation function truncation and trailing characteristic auto-regressive order (p), difference frequency (d) and moving average order (q). The structure of the ARIMA model is as follows:  
\[x_{t+1}^{\prime}=\sum_{i=0}^{p-1}a_{i}x_{t-i}+\sum_{i=0}^{q-1}b_{i}\epsilon_{ t-i} \tag{9}\]  
where \(x_{i}\) is the real value of time slot \(i\). \(p\) is the number of autoregressive terms, and \(q\) represents the order of moving average. \(a,b\) are the relevant weights of this model. The term \(\epsilon\) are the error terminologies relevance to the model.  
Prediction of Resource Usage Using Fractional Differencing  
PRESS [24] uses the Markov model and the signature-driven methods for resource prediction. They divided the use of resource measures into different intervals, then further calculate the conversion probability matrix. Finally they estimated the probability of the next interval by exploiting the Chapman-Kolmogorov equations:  
\[\pi_{t}=\pi_{t-1}P \tag{10}\]  
where \(\pi_{t}\) and \(\pi_{t-1}\) indicate the probability at time instant \(t\) and \(t-1\). Moreover, AGILE [29] improves PRESS through exploiting wavelets to predict usage of resources in cloud. Also, ARIMA is used to estimate the resource usage in the cloud.  
The methods introduced above suppose that time-series are not dynamically changing, and there is no memory. Neverless, cloud environments is constantly changing, and its workloads are highly dynamic. The real workload conditions cannot be catched efficiently by traditional time-series models. It creates a need for a complicate time-series model that can be memorized over time. Thus, the method of rescaled range analysis [30] can be employed for fractional difference [31] in this paper. Fractional difference can be expressed as the following formula.  
\[x_{t}^{\prime}=x_{t}-dx_{t-1}+\frac{d(d-1)}{2!}x_{t-2}-\frac{d(d-1)(d-2)}{3!} x_{t-3} \tag{11}\]  
where \(x_{i}\) denotes the value during interval \(i\), \(x_{t}^{\prime}\) represents the value of \(x_{t}\) which is obtained after fractional difference. \(d\) denotes the parameter related to the difference. Then the method is applied to the analysis for multi-step ahead prediction of the above-mentioned methods.  
The different models will be validated on Google cluster trace. Google cluster trace is a cluster usage dataset and is divided into six tables. Among them, the table of task resource usage offers the usage of various resources (such as memory, disk, and CPU) during different time intervals. Here, we analyze CPU usage at different time intervals.  
Table 1 shows the RMSE (Root Mean Squared Error) for the multi-step ahead predictions of the above methods (PRESS, AGILE and ARIMA) without and with fractional difference. We can observe that fractional difference contributes to a significant improvement in the prediction results for all models. As the increase of prediction horizon, the RMSE of the prediction for CPU usage increases. Because errors accumulate gradually in the process of prediction. We can also observe that ARIMA has smaller RMSE than other models. Figure 2. shows the results of predictions of PRESS, AGILE and ARIMA on CPU usage. It can be seen from the figure that ARIMA reflects the trend of changes inCPU usage more accurately than PRESS and AGILE. Thus we adopt ARIMA model using fractional difference for time-series prediction.