# Research on EfficientTop-k Query Based on ARIMA Time Series Model

Authors: Fenfei Gu; Xiande Hu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In wireless sensor networks,Top-k query is often used to query the first k values which can satisfy the user’s criteria. In the process of query, in order to reduce the transmission of redundant data, different filtering windows are set for each sensor node. However, the filter windows often update because of the dynamic change of the data which will cause the huge consumption of the node energy. In order to solve this problem, a new algorithm based on ARIMA is proposed called AAFU (ARIMA approach based on the filter updating) in this paper. With this algorithm which is based on the FILA algorithm and ARIMA model, the base node can use time series model to predict the future data according to the collected historical data. This algorithm can reduce energy consumption that can make the sensor network effectively deal with the node window updating through comparison to decide whether update the filtering windows. The simulation results show that AAFU algorithm is superior FAPU algorithm with ensuring the accuracy of query.


---

## Body

## 1. Introduction

With the rapid development of computer and wireless communication technologies, wireless sensor networks have become one of the hot research topics [1]. Each node of a wireless sensor network communicates in ad hoc mode [2]. Top-k query can return the first k results which is closest to the query conditions to user that is the reason why this method is called Top-k query [3, 4]. In Top-k query, the sensor node cannot judge whether the final k results on the network structure contain its own sensor data, so it must upload the data to the base station which can form k data sets after unified processing. Top-k can meet the requirements of inexact query, but the centralized data processing brings huge energy consumption and high communication cost. At the same time, the limited energy of the sensor node itself also greatly limits the processing, storage, and communication of data by the senor nodes. How to reduce the energy consumption of the sensor nodes in the process of Top-k query is an important topic in the sensor data query algorithm.At present, some algorithm combines the filtering idea andTop-k to reduce the energy consumption by reducing the upload of redundant data, such as FILA [5, 6] and DAFM [7–9]. Among them, the FILA algorithm reduces the transmission of redundant data at the expense of window update by setting the filter window; although the DAFM algorithm reduces the energy consumption of window update, the data of the sensing node does not conform to the characteristics of linear regression. Based on the above researches, this paper proposes a Top-k query processing algorithm AAFU (ARIMA approach based on filter updating), based on the differential autoregressive moving average model. By perceiving the future t-step data, the update cost can be calculated, and the energy can be saved by reducing invalid window update. The experimental results show that the AAFU algorithm has better accuracy and energy efficiency than FAPU algorithm, both in terms of prediction accuracy and communication traffic.


## 2. Related Works

ATop-k query is aimed at finding the extreme values within a data set, and it has been widely studied in database processing and management for distributed systems [10, 11]. For Top-k query in WSNs [12–14], the main challenge is to reduce the communication overhead by avoiding transmissions that are unnecessary for constructing the Top-k data set. The direct method of implementing the Top-k query algorithm in the sensor network is to collect all the data of sensor nodes to the base station before centralized processing. This unified processing method will consume most of the energy of the sink node and base station. In order to reduce the energy loss caused in the process of data collection, Madden et al. proposed an aggregation technology called TAG [15]. To a certain degree, this method can save some energy compared with centralized processing of sensor node data, but the effect is little. Wu et al. proposed FILA algorithm as shown in Figure 1, the base station collects the data sent by sink node A, and sink node A collects the data of sensor nodes B and C. Filter windows set by sink node A and sensor nodes B and C are 35,54, 54,62, and 62,95, respectively. At T1 and T2, the data of nodes A, B, and C are in the filtering window. At T3, node C does not send, and node A receives 63 from node B and then sends it to the base station.Figure 1
FILA algorithm.To some extent, the FILA algorithm still has the possibility of redundant data upload. As shown in Figure2, the filter window installed on node v1, v2, and v3 at time t. In Figure 2(a), the data sequence collected by Top-k is v1,v4,v3. The data sequence collected is v1,v3,v4 in (b). v3 jumps into the filter window of v4. Because the filter windows of all nodes must be able to form a contiguous area, the v3 node needs to adjust the filter window at this point. After the base station operation reestimation method, the filter window installed for each node is shown in (c). However, according to (d), when sampling at ti+1, the value of v3 changes again and returns to the filtering window shown in (a). If the FILA algorithm is applied in the above scenarios, nodes will meaningless update node windows every time due to frequently fluctuating data; it will bring huge energy consumption to all relevant nodes.Figure 2
Fluctuation of node V3 at ti and ti+1.For the energy consumption of window update, Mai et al. proposed DAFM algorithm to reduce the cost of window update. As the data sequence of most sensor nodes does not conform to the linear regression characteristics, DAFM algorithm is difficult to meet the application requirement. Zhang et al. proposed aTop-k query processing algorithm FAPU (filter approach based on predicted updating) [16]. According to the cost of predicting the future t-step updating window, it can decide whether to send the updating window to the sensor node. However, difference, the core step of ARIMA [17] model, is not discussed in this paper, so it is still difficult to achieve the ideal prediction effect and thus cannot achieve high-efficiency energy saving.The progress of using mathematical models and statistical methods provides strong support for the rapid development of computer science. Tulone and Madden [18] and Liu et al. [19] applied the time series model in statistics to the data collection process of sensor network, and the algorithm model running at any node and base station was the same. Although time series model has been applied in the sensor network, its purpose is almost to minimize the energy of data collection, and the application of time series model in Top-k is still lacking. So, this paper uses the method of combining the statistical modeling and experiment and proposes a FILA filtering model based on ARIMA. After difference processing of nonstationary data, in order to predict the data at the next t moments, this algorithm uses the ARMA model and updates the cost and evaluates the window on the basis of updating algorithm, so as to choose a better method to reduce the energy consumption of nodes.


## 3. Methodology

### 3.1. Network Model

The basic framework of wireless sensor network [20] is composed of base station, sink node, Internet, and other components. The mobility and convenience brought by the random distribution of sensor nodes in wireless sensor network promotes its wide application in life. Sensor nodes in the wireless sensor network need to process the collected data all the time and collect and analyze the data transmitted by other nodes, so the energy consumption of sensor nodes is huge.


### 3.2. Autoregressive Integrated Moving Average Model (ARIMA)

#### 3.2.1. Series Stationarity

A sequence whose value at any time can be accurately predicted is called a deterministic sequence, such as cosine function and linear function. In general, we can roughly get the probability of a particular number in a sequence but cannot accurately predict the number at a given moment.If each value of some time seriesXtt=1,2,⋯ is randomly obtained from a probability distribution, and the sequence satisfies the following requirements: mean value EXt, variance VarXt, and covariance CovXt,Xt+k, all of which are functions unrelated to time t, so it is called a stationary random time series.Whether the data series appear stationary is an important basis for deciding which model to use. Usually, a nonstationary sequence can be changed into a stationary sequence by difference, and the unit root test can be used to detect whether the data sequence is stationary [16].Zhang et al. introduced an analysis method of stationary time series in their paper, but lack of research on the difference of nonstationary data. The data collected by sensor network nodes are not completely stable, so it is very important to analyze and process the nonstationary data.


#### 3.2.2. Introduction of ARIMA Model

Although there is a great volatility of the nature data, these data have a strong time sequence. The upcoming data usually depend on the previous historical data in some “unknown” way, and this dependence makes it possible to predict the future by using the past.Autoregressive integrated moving average (ARIMAp,d,q model) usually has the following structure:
(1)ΦB∇dXt=ΘBεt,Eεt=0,Varεt=σ2,Eεtεs=0,s≠t,EXsεt=0,∀s<t.In the formula∇d=1−Bd, ΦB=1−ϕB−⋯−ϕpBp is the polynomial of autoregressive coefficients. ΘB=1−θ1B−⋯−θqBq is the moving smoothing coefficient polynomial.Equation (1) can be abbreviated as
(2)∇dXt=ΘBΦBεt.In the formula, {εt} is the white noise sequence, and its mean value is 0.According to (2), the combination of difference operation and ARMA is ARIMA, which also indicates that any nonstationary sequence can be transformed into stationary sequence by difference operation of appropriate order. In modern statistical mathematics, the technology of ARMA modeling and analyzing time series to predict future development trend has been mature. This also shows that nonstationary sequences can be easily processed.If a time seriesXt obeys ARIMAp,d,q:
(3)ΦB∇dXt=ΘBεt.In the formula,(4)∇d=1−Bd,ΦB=1−Φ1B−⋯⋯−ΦpBp,ΘB=1−θqB−⋯⋯−θqBq.LetψB=ΦB∇d, ψB be a polynomial of generalized autoregressive coefficients. Obviously, the root of ψB=0 determines whether the ARIMA model is stationary. If the sequence Xt is stable after the difference of order D, it obeys the ARMAp,q model. Set ΦB∇d=∏i=1p1−λiB,λi<1;i=1,2,⋯,p. Then,
(5)ψB=ΦB∇d=∏i=1p1−λiB1−Bd.


#### 3.2.3. ARIMA Model Modeling

According to the principle of least variance prediction, the modeling methods of ARIMA model and ARMA model are very similar. It includes the following steps.Algorithm 1: ARIMA modeling process.
(1) Obtain the original data sequenceXt;(2) Verify the stationarity of time series according to the Unit root test method;(3) while (! {Xt} smooth) {d=d+1; Compute the difference sequence};(4) ARMA modeling:ΦB=∇dXt=ΘBεt.(5) Obtain ARIMA model.Generally, the ARIMAp,d,q model can be expressed as ΦB1−BdXt=ΘBεt, and the linear function of historical observation value can be expressed as
(6)Xt=εt+Ψ1εt−1+Ψ2εt−2+⋯+ΨBεt.In the formulaΦB1−BdΨB=ΘB, if denoted Θ∗B as a generalized autocorrelation function, then: Θ∗B=ΦB1−Bd=1−ϕ1B−ϕ2B2−⋯.Verifiable.Ψ1,Ψ2⋯values can satisfy the following recursion:
(7)Ψ1=ϕ1−θ1,Ψ2=ϕ1Ψ1+ϕ2−θ2,⋯Ψj=ϕ1Ψj−1+⋯+ϕp+dΨj−p−d−θj.In the formula,Ψj=0,j<1,1,j=1,θj=0,j>q. Then, the real value of Xt+1 is
(8)Xt+1=εt+1+Ψ1εt+l−1+⋯+Ψl−1εt+1+Ψlεt+Ψl+1εt−1⋯.Due to the unavailability ofεt+l,εt+l−1,⋯,εt−1, the estimated value of Xt+1 can only be
(9)X^t1=Ψ0∗εt+Ψ1∗εt−1+Ψ2∗εt−2+⋯.


## 3.1. Network Model

The basic framework of wireless sensor network [20] is composed of base station, sink node, Internet, and other components. The mobility and convenience brought by the random distribution of sensor nodes in wireless sensor network promotes its wide application in life. Sensor nodes in the wireless sensor network need to process the collected data all the time and collect and analyze the data transmitted by other nodes, so the energy consumption of sensor nodes is huge.


## 3.2. Autoregressive Integrated Moving Average Model (ARIMA)

### 3.2.1. Series Stationarity

A sequence whose value at any time can be accurately predicted is called a deterministic sequence, such as cosine function and linear function. In general, we can roughly get the probability of a particular number in a sequence but cannot accurately predict the number at a given moment.If each value of some time seriesXtt=1,2,⋯ is randomly obtained from a probability distribution, and the sequence satisfies the following requirements: mean value EXt, variance VarXt, and covariance CovXt,Xt+k, all of which are functions unrelated to time t, so it is called a stationary random time series.Whether the data series appear stationary is an important basis for deciding which model to use. Usually, a nonstationary sequence can be changed into a stationary sequence by difference, and the unit root test can be used to detect whether the data sequence is stationary [16].Zhang et al. introduced an analysis method of stationary time series in their paper, but lack of research on the difference of nonstationary data. The data collected by sensor network nodes are not completely stable, so it is very important to analyze and process the nonstationary data.


### 3.2.2. Introduction of ARIMA Model

Although there is a great volatility of the nature data, these data have a strong time sequence. The upcoming data usually depend on the previous historical data in some “unknown” way, and this dependence makes it possible to predict the future by using the past.Autoregressive integrated moving average (ARIMAp,d,q model) usually has the following structure:
(1)ΦB∇dXt=ΘBεt,Eεt=0,Varεt=σ2,Eεtεs=0,s≠t,EXsεt=0,∀s<t.In the formula∇d=1−Bd, ΦB=1−ϕB−⋯−ϕpBp is the polynomial of autoregressive coefficients. ΘB=1−θ1B−⋯−θqBq is the moving smoothing coefficient polynomial.Equation (1) can be abbreviated as
(2)∇dXt=ΘBΦBεt.In the formula, {εt} is the white noise sequence, and its mean value is 0.According to (2), the combination of difference operation and ARMA is ARIMA, which also indicates that any nonstationary sequence can be transformed into stationary sequence by difference operation of appropriate order. In modern statistical mathematics, the technology of ARMA modeling and analyzing time series to predict future development trend has been mature. This also shows that nonstationary sequences can be easily processed.If a time seriesXt obeys ARIMAp,d,q:
(3)ΦB∇dXt=ΘBεt.In the formula,(4)∇d=1−Bd,ΦB=1−Φ1B−⋯⋯−ΦpBp,ΘB=1−θqB−⋯⋯−θqBq.LetψB=ΦB∇d, ψB be a polynomial of generalized autoregressive coefficients. Obviously, the root of ψB=0 determines whether the ARIMA model is stationary. If the sequence Xt is stable after the difference of order D, it obeys the ARMAp,q model. Set ΦB∇d=∏i=1p1−λiB,λi<1;i=1,2,⋯,p. Then,
(5)ψB=ΦB∇d=∏i=1p1−λiB1−Bd.


### 3.2.3. ARIMA Model Modeling

According to the principle of least variance prediction, the modeling methods of ARIMA model and ARMA model are very similar. It includes the following steps.Algorithm 1: ARIMA modeling process.
(1) Obtain the original data sequenceXt;(2) Verify the stationarity of time series according to the Unit root test method;(3) while (! {Xt} smooth) {d=d+1; Compute the difference sequence};(4) ARMA modeling:ΦB=∇dXt=ΘBεt.(5) Obtain ARIMA model.Generally, the ARIMAp,d,q model can be expressed as ΦB1−BdXt=ΘBεt, and the linear function of historical observation value can be expressed as
(6)Xt=εt+Ψ1εt−1+Ψ2εt−2+⋯+ΨBεt.In the formulaΦB1−BdΨB=ΘB, if denoted Θ∗B as a generalized autocorrelation function, then: Θ∗B=ΦB1−Bd=1−ϕ1B−ϕ2B2−⋯.Verifiable.Ψ1,Ψ2⋯values can satisfy the following recursion:
(7)Ψ1=ϕ1−θ1,Ψ2=ϕ1Ψ1+ϕ2−θ2,⋯Ψj=ϕ1Ψj−1+⋯+ϕp+dΨj−p−d−θj.In the formula,Ψj=0,j<1,1,j=1,θj=0,j>q. Then, the real value of Xt+1 is
(8)Xt+1=εt+1+Ψ1εt+l−1+⋯+Ψl−1εt+1+Ψlεt+Ψl+1εt−1⋯.Due to the unavailability ofεt+l,εt+l−1,⋯,εt−1, the estimated value of Xt+1 can only be
(9)X^t1=Ψ0∗εt+Ψ1∗εt−1+Ψ2∗εt−2+⋯.


## 3.2.1. Series Stationarity

A sequence whose value at any time can be accurately predicted is called a deterministic sequence, such as cosine function and linear function. In general, we can roughly get the probability of a particular number in a sequence but cannot accurately predict the number at a given moment.If each value of some time seriesXtt=1,2,⋯ is randomly obtained from a probability distribution, and the sequence satisfies the following requirements: mean value EXt, variance VarXt, and covariance CovXt,Xt+k, all of which are functions unrelated to time t, so it is called a stationary random time series.Whether the data series appear stationary is an important basis for deciding which model to use. Usually, a nonstationary sequence can be changed into a stationary sequence by difference, and the unit root test can be used to detect whether the data sequence is stationary [16].Zhang et al. introduced an analysis method of stationary time series in their paper, but lack of research on the difference of nonstationary data. The data collected by sensor network nodes are not completely stable, so it is very important to analyze and process the nonstationary data.


## 3.2.2. Introduction of ARIMA Model

Although there is a great volatility of the nature data, these data have a strong time sequence. The upcoming data usually depend on the previous historical data in some “unknown” way, and this dependence makes it possible to predict the future by using the past.Autoregressive integrated moving average (ARIMAp,d,q model) usually has the following structure:
(1)ΦB∇dXt=ΘBεt,Eεt=0,Varεt=σ2,Eεtεs=0,s≠t,EXsεt=0,∀s<t.In the formula∇d=1−Bd, ΦB=1−ϕB−⋯−ϕpBp is the polynomial of autoregressive coefficients. ΘB=1−θ1B−⋯−θqBq is the moving smoothing coefficient polynomial.Equation (1) can be abbreviated as
(2)∇dXt=ΘBΦBεt.In the formula, {εt} is the white noise sequence, and its mean value is 0.According to (2), the combination of difference operation and ARMA is ARIMA, which also indicates that any nonstationary sequence can be transformed into stationary sequence by difference operation of appropriate order. In modern statistical mathematics, the technology of ARMA modeling and analyzing time series to predict future development trend has been mature. This also shows that nonstationary sequences can be easily processed.If a time seriesXt obeys ARIMAp,d,q:
(3)ΦB∇dXt=ΘBεt.In the formula,(4)∇d=1−Bd,ΦB=1−Φ1B−⋯⋯−ΦpBp,ΘB=1−θqB−⋯⋯−θqBq.LetψB=ΦB∇d, ψB be a polynomial of generalized autoregressive coefficients. Obviously, the root of ψB=0 determines whether the ARIMA model is stationary. If the sequence Xt is stable after the difference of order D, it obeys the ARMAp,q model. Set ΦB∇d=∏i=1p1−λiB,λi<1;i=1,2,⋯,p. Then,
(5)ψB=ΦB∇d=∏i=1p1−λiB1−Bd.


## 3.2.3. ARIMA Model Modeling

According to the principle of least variance prediction, the modeling methods of ARIMA model and ARMA model are very similar. It includes the following steps.Algorithm 1: ARIMA modeling process.
(1) Obtain the original data sequenceXt;(2) Verify the stationarity of time series according to the Unit root test method;(3) while (! {Xt} smooth) {d=d+1; Compute the difference sequence};(4) ARMA modeling:ΦB=∇dXt=ΘBεt.(5) Obtain ARIMA model.Generally, the ARIMAp,d,q model can be expressed as ΦB1−BdXt=ΘBεt, and the linear function of historical observation value can be expressed as
(6)Xt=εt+Ψ1εt−1+Ψ2εt−2+⋯+ΨBεt.In the formulaΦB1−BdΨB=ΘB, if denoted Θ∗B as a generalized autocorrelation function, then: Θ∗B=ΦB1−Bd=1−ϕ1B−ϕ2B2−⋯.Verifiable.Ψ1,Ψ2⋯values can satisfy the following recursion:
(7)Ψ1=ϕ1−θ1,Ψ2=ϕ1Ψ1+ϕ2−θ2,⋯Ψj=ϕ1Ψj−1+⋯+ϕp+dΨj−p−d−θj.In the formula,Ψj=0,j<1,1,j=1,θj=0,j>q. Then, the real value of Xt+1 is
(8)Xt+1=εt+1+Ψ1εt+l−1+⋯+Ψl−1εt+1+Ψlεt+Ψl+1εt−1⋯.Due to the unavailability ofεt+l,εt+l−1,⋯,εt−1, the estimated value of Xt+1 can only be
(9)X^t1=Ψ0∗εt+Ψ1∗εt−1+Ψ2∗εt−2+⋯.


## 4. AAFU Algorithm

The improvement of FILA algorithm is as follows:(a)
This paper adopts the predictive update algorithm to decide whether to send the new filterwindowlinew,uinew to relevant nodes(b)
Since data such as light and temperature usually change as time and do not change much within fixed intervals, this paper proposes an algorithm AAFU (ARIMA approach based on filter updating) to calculate the updating window


### 4.1. Problem Definition

According to the data collected by the sensor network, aTop-k algorithm based on time series is modeled to effectively make the base station run the Top-k query algorithm and consume energy as low as possible, through a lot of data calculation, and model fitting to get this algorithm, and finally through the comparison of the algorithm to verify the accuracy of the algorithm.


### 4.2. Model Prediction

#### 4.2.1. Modeling

In this paper, we use MATLAB and Eviews software to verify the effectiveness of the algorithm. Sensor data from Intel Berkeley Lab from February 28, 2004 to April 5, 2004 were used as test data, which included temperature, humidity, and light; they were collected every 31 seconds by 54 sensor nodes [21].Taking node 37 as an example, the average value of every two sampling data of temperature data sensed by sensor 37 from February 28, 2004 to April 5, 2004 is treated as one sampling. The time series diagram of this node is shown in Figure3:Figure 3
Sequence diagram of sensor node 37 data.Figure3 shows that this sequence is relatively stable in t∈0,18000 with a small fluctuation range but fluctuates greatly in the range 18001,29358. However, we cannot identify whether a data sequence is stable only through eye observation. Instead, we need to use a method to determine whether the sequence is stable—unit root test [11]. The stationarity test results of this time series are shown in Table 1. Table 1 shows that t-statistic (-0.305837) is significantly greater than 1% level, 5% level, and 10% level. The null hypothesis is valid, that is, the sequence is not stable.Table 1
Unit root test for original data.
t-statisticProb.∗Augmented Dickey-Fuller test statistic-0.2407300.9309Test critical value1% level-3.430452N/A5% level-2.861469N/A10% level-2.566773N/AWhen the sequence is not stationary, the difference method is needed to collect data, that is, the gradient of the change value of adjacent data is used as the model data.The first-order difference methodd1=tentor37t−tentor37t−1, and the original data sequence is differential to obtain the new sequence d1, and the d1 sequence diagram is shown in Figure 4.Figure 4
Sequence diagram of dataD after first-order difference.Intuitively, Figure4 shows that the sequence is very stable, and the fluctuation range is within −10,5. Similarly, in order to verify the stationarity, the unit root test is required, and the verification results are shown in Table 2 as below.Table 2
Unit root test for differential data.
t-statisticProb.∗Augmented Dickey-Fuller test statistic-18.30130.0000Test critical value1% level-3.430452N/A5% level-2.861469N/A10% level-2.566773N/AThe analysis shows thatt-statistic (-18.30513) is significantly less than 1% level, 5% level, and 10% level, indicating that the null hypothesis is untenable, that is, the sequence is stable. Table 2 shows that after the first-order difference, a very stable sequence can be obtained, which has a better prediction advantage than the undifferentiated sequence.For the obtained first-order difference datad, we need to use the least square estimation and maximum likelihood estimation to verify the model fitting effect under different order p and q. The results are shown in Table 3. In the table, ARMA(1,1) and others represent the model abbreviations; c is constant; ar(1) ~ ar(3) represent first-order, second-order, and third-order autoregressive processes, respectively [11]; ma(1) ~ ma(3) represent the first-order, second-order, and third-order moving average processes, respectively [11]. The parameters of autoregression process and moving average process are determined by whether the data parameters after the first-order difference are truncated or trailed.Table 3
Table of parameters for different models.
Modelcar(1)ar(2)ar(3)ma(1)ma(2)ma(3)ARMA(1,1)0.0041210.692415NANA-0.18698NANAARMA(1,2)0.0040810.839944NANA-0.33063-0.161NAARMA(2,2)0.0040021.42368-0.44794NA-0.919780.024312NAARMA(2,1)0.0040071.389679-0.41745NA0.01098NANAARMA(3,1)0.0040031.394954-0.41115-0.00933-0.89037NANAARMA(3,2)0.0040110.72322-0.478535-0.25278-0.20928-0.57754NAARMA((1,3),3)NA1.254673NA-0.25881-0.74749-0.359050.13454


#### 4.2.2. Model Fitting

For the comparison and selection of models, it is necessary to consider all factors comprehensively and then choose an optimal model.(1)
R-squared: the size of this indicator indicates the degree of information extracted from the data by the fitted model, which is an important reference indicator for the quality of model fitting(2)
AIC criterion: the smaller the AIC index is, the better(3)
D.W. value: the D.W. value represents whether there is a first-order autocorrelation between residual sequences after model fitting. When the D.W. value is close to 2, the model fits well(4)
Number of model parameters: in general, fewer parameters are more suitable for calculation and analysis, so the fewer parameters the betterFor each comparison item, Eviews software is used to calculate and obtain Table4.Table 4
Table of fitting effect parameters of different models.
ModelR-squaredAICD.W.ARMA(1,1)0.328284-1.6595561.980631ARMA(1,2)0.333397-1.6671121.991708ARMA(2,2)0.337582-1.6733231.998345ARMA(2,1)0.33753-1.6733282.004726ARMA(3,1)0.337572-1.6733081.999612ARMA(3,2)0.337889-1.6737032.015676ARMA((1,3),3)0.339305-1.6759222.001192


#### 4.2.3. Model Choosing

According to the above reasons and the data in the table, model ARMA((1,3),3) is selected, that is, model ARMA((1,3),3) is expressed as follows:(10)ΦBXt=ΘBεt1−0.1254673B+0.25881B3Xt=1+0.74749B+0.35905B2+0.13454B3εt.Thus, the original sequence ARIMA((1,3),1,3) model expression can be deduced as follows:(11)ΦB∇dXt=ΘBεt1−1.254673B+0.25881B31−BXt=1+0.74749B+0.35905B2+0.13454B3εt.


### 4.3. Cost Analysis

The cost of implementing AAFU algorithm includes the following two situations, which are analyzed as follows.First, when the window needs to be updated.If the window needs to be updated, data must be uploaded. Therefore, the energy consumed by uploading data is set asCup. At the same time, when the base station is running AAFU algorithm, its energy consumption is set as Ccal. After the run, the window for the node should be sent and installed, and the energy consumed is Csend. So, the energy consumed during the whole process is
(12)Cupdate=Cup+Ccal+Csend.Second, when the window is not updated, there is no need to consume additional energy.Algorithm 2: Update the cost evaluation algorithm.
(1) Query(Top-k); //Run the Top-k query on all nodes(2) if base station get new values//If base station get new values of a node(3) reevaluation(); //Execute the re-estimate algorithm(4) ComputeCsend,Ccal,Cup,CUpdate(5) ifCUpdate<Cold(6) Updating window; //Send window update to nodes in Nu(7) end if


## 4.1. Problem Definition

According to the data collected by the sensor network, aTop-k algorithm based on time series is modeled to effectively make the base station run the Top-k query algorithm and consume energy as low as possible, through a lot of data calculation, and model fitting to get this algorithm, and finally through the comparison of the algorithm to verify the accuracy of the algorithm.


## 4.2. Model Prediction

### 4.2.1. Modeling

In this paper, we use MATLAB and Eviews software to verify the effectiveness of the algorithm. Sensor data from Intel Berkeley Lab from February 28, 2004 to April 5, 2004 were used as test data, which included temperature, humidity, and light; they were collected every 31 seconds by 54 sensor nodes [21].Taking node 37 as an example, the average value of every two sampling data of temperature data sensed by sensor 37 from February 28, 2004 to April 5, 2004 is treated as one sampling. The time series diagram of this node is shown in Figure3:Figure 3
Sequence diagram of sensor node 37 data.Figure3 shows that this sequence is relatively stable in t∈0,18000 with a small fluctuation range but fluctuates greatly in the range 18001,29358. However, we cannot identify whether a data sequence is stable only through eye observation. Instead, we need to use a method to determine whether the sequence is stable—unit root test [11]. The stationarity test results of this time series are shown in Table 1. Table 1 shows that t-statistic (-0.305837) is significantly greater than 1% level, 5% level, and 10% level. The null hypothesis is valid, that is, the sequence is not stable.Table 1
Unit root test for original data.
t-statisticProb.∗Augmented Dickey-Fuller test statistic-0.2407300.9309Test critical value1% level-3.430452N/A5% level-2.861469N/A10% level-2.566773N/AWhen the sequence is not stationary, the difference method is needed to collect data, that is, the gradient of the change value of adjacent data is used as the model data.The first-order difference methodd1=tentor37t−tentor37t−1, and the original data sequence is differential to obtain the new sequence d1, and the d1 sequence diagram is shown in Figure 4.Figure 4
Sequence diagram of dataD after first-order difference.Intuitively, Figure4 shows that the sequence is very stable, and the fluctuation range is within −10,5. Similarly, in order to verify the stationarity, the unit root test is required, and the verification results are shown in Table 2 as below.Table 2
Unit root test for differential data.
t-statisticProb.∗Augmented Dickey-Fuller test statistic-18.30130.0000Test critical value1% level-3.430452N/A5% level-2.861469N/A10% level-2.566773N/AThe analysis shows thatt-statistic (-18.30513) is significantly less than 1% level, 5% level, and 10% level, indicating that the null hypothesis is untenable, that is, the sequence is stable. Table 2 shows that after the first-order difference, a very stable sequence can be obtained, which has a better prediction advantage than the undifferentiated sequence.For the obtained first-order difference datad, we need to use the least square estimation and maximum likelihood estimation to verify the model fitting effect under different order p and q. The results are shown in Table 3. In the table, ARMA(1,1) and others represent the model abbreviations; c is constant; ar(1) ~ ar(3) represent first-order, second-order, and third-order autoregressive processes, respectively [11]; ma(1) ~ ma(3) represent the first-order, second-order, and third-order moving average processes, respectively [11]. The parameters of autoregression process and moving average process are determined by whether the data parameters after the first-order difference are truncated or trailed.Table 3
Table of parameters for different models.
Modelcar(1)ar(2)ar(3)ma(1)ma(2)ma(3)ARMA(1,1)0.0041210.692415NANA-0.18698NANAARMA(1,2)0.0040810.839944NANA-0.33063-0.161NAARMA(2,2)0.0040021.42368-0.44794NA-0.919780.024312NAARMA(2,1)0.0040071.389679-0.41745NA0.01098NANAARMA(3,1)0.0040031.394954-0.41115-0.00933-0.89037NANAARMA(3,2)0.0040110.72322-0.478535-0.25278-0.20928-0.57754NAARMA((1,3),3)NA1.254673NA-0.25881-0.74749-0.359050.13454


### 4.2.2. Model Fitting

For the comparison and selection of models, it is necessary to consider all factors comprehensively and then choose an optimal model.(1)
R-squared: the size of this indicator indicates the degree of information extracted from the data by the fitted model, which is an important reference indicator for the quality of model fitting(2)
AIC criterion: the smaller the AIC index is, the better(3)
D.W. value: the D.W. value represents whether there is a first-order autocorrelation between residual sequences after model fitting. When the D.W. value is close to 2, the model fits well(4)
Number of model parameters: in general, fewer parameters are more suitable for calculation and analysis, so the fewer parameters the betterFor each comparison item, Eviews software is used to calculate and obtain Table4.Table 4
Table of fitting effect parameters of different models.
ModelR-squaredAICD.W.ARMA(1,1)0.328284-1.6595561.980631ARMA(1,2)0.333397-1.6671121.991708ARMA(2,2)0.337582-1.6733231.998345ARMA(2,1)0.33753-1.6733282.004726ARMA(3,1)0.337572-1.6733081.999612ARMA(3,2)0.337889-1.6737032.015676ARMA((1,3),3)0.339305-1.6759222.001192


### 4.2.3. Model Choosing

According to the above reasons and the data in the table, model ARMA((1,3),3) is selected, that is, model ARMA((1,3),3) is expressed as follows:(10)ΦBXt=ΘBεt1−0.1254673B+0.25881B3Xt=1+0.74749B+0.35905B2+0.13454B3εt.Thus, the original sequence ARIMA((1,3),1,3) model expression can be deduced as follows:(11)ΦB∇dXt=ΘBεt1−1.254673B+0.25881B31−BXt=1+0.74749B+0.35905B2+0.13454B3εt.


## 4.2.1. Modeling

In this paper, we use MATLAB and Eviews software to verify the effectiveness of the algorithm. Sensor data from Intel Berkeley Lab from February 28, 2004 to April 5, 2004 were used as test data, which included temperature, humidity, and light; they were collected every 31 seconds by 54 sensor nodes [21].Taking node 37 as an example, the average value of every two sampling data of temperature data sensed by sensor 37 from February 28, 2004 to April 5, 2004 is treated as one sampling. The time series diagram of this node is shown in Figure3:Figure 3
Sequence diagram of sensor node 37 data.Figure3 shows that this sequence is relatively stable in t∈0,18000 with a small fluctuation range but fluctuates greatly in the range 18001,29358. However, we cannot identify whether a data sequence is stable only through eye observation. Instead, we need to use a method to determine whether the sequence is stable—unit root test [11]. The stationarity test results of this time series are shown in Table 1. Table 1 shows that t-statistic (-0.305837) is significantly greater than 1% level, 5% level, and 10% level. The null hypothesis is valid, that is, the sequence is not stable.Table 1
Unit root test for original data.
t-statisticProb.∗Augmented Dickey-Fuller test statistic-0.2407300.9309Test critical value1% level-3.430452N/A5% level-2.861469N/A10% level-2.566773N/AWhen the sequence is not stationary, the difference method is needed to collect data, that is, the gradient of the change value of adjacent data is used as the model data.The first-order difference methodd1=tentor37t−tentor37t−1, and the original data sequence is differential to obtain the new sequence d1, and the d1 sequence diagram is shown in Figure 4.Figure 4
Sequence diagram of dataD after first-order difference.Intuitively, Figure4 shows that the sequence is very stable, and the fluctuation range is within −10,5. Similarly, in order to verify the stationarity, the unit root test is required, and the verification results are shown in Table 2 as below.Table 2
Unit root test for differential data.
t-statisticProb.∗Augmented Dickey-Fuller test statistic-18.30130.0000Test critical value1% level-3.430452N/A5% level-2.861469N/A10% level-2.566773N/AThe analysis shows thatt-statistic (-18.30513) is significantly less than 1% level, 5% level, and 10% level, indicating that the null hypothesis is untenable, that is, the sequence is stable. Table 2 shows that after the first-order difference, a very stable sequence can be obtained, which has a better prediction advantage than the undifferentiated sequence.For the obtained first-order difference datad, we need to use the least square estimation and maximum likelihood estimation to verify the model fitting effect under different order p and q. The results are shown in Table 3. In the table, ARMA(1,1) and others represent the model abbreviations; c is constant; ar(1) ~ ar(3) represent first-order, second-order, and third-order autoregressive processes, respectively [11]; ma(1) ~ ma(3) represent the first-order, second-order, and third-order moving average processes, respectively [11]. The parameters of autoregression process and moving average process are determined by whether the data parameters after the first-order difference are truncated or trailed.Table 3
Table of parameters for different models.
Modelcar(1)ar(2)ar(3)ma(1)ma(2)ma(3)ARMA(1,1)0.0041210.692415NANA-0.18698NANAARMA(1,2)0.0040810.839944NANA-0.33063-0.161NAARMA(2,2)0.0040021.42368-0.44794NA-0.919780.024312NAARMA(2,1)0.0040071.389679-0.41745NA0.01098NANAARMA(3,1)0.0040031.394954-0.41115-0.00933-0.89037NANAARMA(3,2)0.0040110.72322-0.478535-0.25278-0.20928-0.57754NAARMA((1,3),3)NA1.254673NA-0.25881-0.74749-0.359050.13454


## 4.2.2. Model Fitting

For the comparison and selection of models, it is necessary to consider all factors comprehensively and then choose an optimal model.(1)
R-squared: the size of this indicator indicates the degree of information extracted from the data by the fitted model, which is an important reference indicator for the quality of model fitting(2)
AIC criterion: the smaller the AIC index is, the better(3)
D.W. value: the D.W. value represents whether there is a first-order autocorrelation between residual sequences after model fitting. When the D.W. value is close to 2, the model fits well(4)
Number of model parameters: in general, fewer parameters are more suitable for calculation and analysis, so the fewer parameters the betterFor each comparison item, Eviews software is used to calculate and obtain Table4.Table 4
Table of fitting effect parameters of different models.
ModelR-squaredAICD.W.ARMA(1,1)0.328284-1.6595561.980631ARMA(1,2)0.333397-1.6671121.991708ARMA(2,2)0.337582-1.6733231.998345ARMA(2,1)0.33753-1.6733282.004726ARMA(3,1)0.337572-1.6733081.999612ARMA(3,2)0.337889-1.6737032.015676ARMA((1,3),3)0.339305-1.6759222.001192


## 4.2.3. Model Choosing

According to the above reasons and the data in the table, model ARMA((1,3),3) is selected, that is, model ARMA((1,3),3) is expressed as follows:(10)ΦBXt=ΘBεt1−0.1254673B+0.25881B3Xt=1+0.74749B+0.35905B2+0.13454B3εt.Thus, the original sequence ARIMA((1,3),1,3) model expression can be deduced as follows:(11)ΦB∇dXt=ΘBεt1−1.254673B+0.25881B31−BXt=1+0.74749B+0.35905B2+0.13454B3εt.


## 4.3. Cost Analysis

The cost of implementing AAFU algorithm includes the following two situations, which are analyzed as follows.First, when the window needs to be updated.If the window needs to be updated, data must be uploaded. Therefore, the energy consumed by uploading data is set asCup. At the same time, when the base station is running AAFU algorithm, its energy consumption is set as Ccal. After the run, the window for the node should be sent and installed, and the energy consumed is Csend. So, the energy consumed during the whole process is
(12)Cupdate=Cup+Ccal+Csend.Second, when the window is not updated, there is no need to consume additional energy.Algorithm 2: Update the cost evaluation algorithm.
(1) Query(Top-k); //Run the Top-k query on all nodes(2) if base station get new values//If base station get new values of a node(3) reevaluation(); //Execute the re-estimate algorithm(4) ComputeCsend,Ccal,Cup,CUpdate(5) ifCUpdate<Cold(6) Updating window; //Send window update to nodes in Nu(7) end if


## 5. Experimental Results

### 5.1. Experimental Setup

In this paper, sensor data from Intel Berkeley Lab from February 28, 2004 to April 5, 2004 are used as test data. This data set consists of temperature, light, and others sensed by 54 sensor nodes at every 31 seconds. Temperature data collected at node 37 is selected as test data. Eviews and MATLAB software were used to verify the effectiveness of the algorithm.This experiment is compared with FAPU algorithm. Under differentk values, the data transmission times generated in the query process were tested. With the same network structure, the number of data transmission under different K values is used as the measurement basis to compare the performance of the FAPU and AAFU algorithms.


### 5.2. Mode Predict

#### 5.2.1. Comparison of Predict Error Rates between ARIMA((1,3),3) and ARMA(2,2)

The experiment compares model ARIMA((1,3),3) with ARMA(2,2) model algorithm. The random function of C language was used to randomly select 18 time points from 23964 time axes and predict the sequence change values of the 18 time points in the next 5, 10, 15, and 20 steps, and then compare the predicted values with the actual values to obtain the error rates, so as to obtain the error rates in different groups with different predicted steps as shown in Figure5.Figure 5
Comparison of prediction error rate among different groups.
(a)
Forward five step forecast error rate(b)
Forward ten step forecast error rate(c)
Forward fifteen step forecast error rate(d)
Forward twenty step forecast error rate


#### 5.2.2.T Value Determination

The value oft is the threshold predicted by the experiment model. The value of t will directly affect the performance of AAFU algorithm, and this paper mainly determines it through the experiment. According to the relative error shown in Figure 5, when t is set to 5 or 10, the error between the predicted value and the real value is relatively small, and this result is in line with common sense. It is easy to predict the data in the nearest future, while it is difficult to predict the data in the distant future. Therefore, AAFU algorithm adopts forward 5 step prediction when updating Windows.


#### 5.2.3. Experimental Setup

Firstly, we consider the influence of differentk values in Top-k on algorithm performance under the same sensor network structure to verify the effectiveness of the algorithm. Secondly, under the same k value, the influence of different perceptive nodes on algorithm performance is considered. The experiment results were obtained under the premise of executing 1000 Top-k queries.


### 5.3. Result Analysis

According to Figure5, ARIMA((1,3),1,3) model has good prediction effect, and its accuracy exceeds ARMA(2,2) used by FAPU algorithm to a certain extent. According to the theory, in ARIMAp,d,q model, when d=0, it means that the model evolves into ARMA(2,2) model, so there is no accurate fitting effect. In ARIMA((1,3),1,3) model, the prediction performance is improved due to first-order difference processing of the original data, so that the sensor value at a certain future time can be accurately predicted and the error rate between the sensor value and the real value can be reduced.According to Figure6, when the number of sensor nodes is the same, different k values are set to verify the effectiveness of the algorithm. As known, with the increase of k value, the AFU algorithm is better than the FAPU algorithm gradually. This is because in the case of the same t step prediction, the prediction error rate of the AAFU algorithm model is lower and it can map to the cost update algorithm; it will get more accurate prediction, which will further reduce the number of update window, and reduce the relative traffic brought by the network update, and it can prolong the life cycle of sensor network.Figure 6
Commnication traffic base on the same number of nodes and differentk values.Figure7 shows that, when k=10, different n sensor nodes are selected to verify the effectiveness of the algorithm. The AAPU algorithm far exceeds algorithm FAPU. Even when the number of nodes in the network is 200, data transmission is reduced by 5000 times in 1000 Top-k queries, and the update transmission gap gradually increases with the increase of the number n of nodes. This is because under the same k value, the FILA-based filtering method only sets k+1 windows, and the number of windows is only related to K, not n. Therefore, the difference in the change of traffic is not big, but even so, AAPU algorithm reduces the traffic more than 5000 times compared with FAPU algorithm.Figure 7
Commnication traffic base on different numbers of nodes and the samek values.


## 5.1. Experimental Setup

In this paper, sensor data from Intel Berkeley Lab from February 28, 2004 to April 5, 2004 are used as test data. This data set consists of temperature, light, and others sensed by 54 sensor nodes at every 31 seconds. Temperature data collected at node 37 is selected as test data. Eviews and MATLAB software were used to verify the effectiveness of the algorithm.This experiment is compared with FAPU algorithm. Under differentk values, the data transmission times generated in the query process were tested. With the same network structure, the number of data transmission under different K values is used as the measurement basis to compare the performance of the FAPU and AAFU algorithms.


## 5.2. Mode Predict

### 5.2.1. Comparison of Predict Error Rates between ARIMA((1,3),3) and ARMA(2,2)

The experiment compares model ARIMA((1,3),3) with ARMA(2,2) model algorithm. The random function of C language was used to randomly select 18 time points from 23964 time axes and predict the sequence change values of the 18 time points in the next 5, 10, 15, and 20 steps, and then compare the predicted values with the actual values to obtain the error rates, so as to obtain the error rates in different groups with different predicted steps as shown in Figure5.Figure 5
Comparison of prediction error rate among different groups.
(a)
Forward five step forecast error rate(b)
Forward ten step forecast error rate(c)
Forward fifteen step forecast error rate(d)
Forward twenty step forecast error rate


### 5.2.2.T Value Determination

The value oft is the threshold predicted by the experiment model. The value of t will directly affect the performance of AAFU algorithm, and this paper mainly determines it through the experiment. According to the relative error shown in Figure 5, when t is set to 5 or 10, the error between the predicted value and the real value is relatively small, and this result is in line with common sense. It is easy to predict the data in the nearest future, while it is difficult to predict the data in the distant future. Therefore, AAFU algorithm adopts forward 5 step prediction when updating Windows.


### 5.2.3. Experimental Setup

Firstly, we consider the influence of differentk values in Top-k on algorithm performance under the same sensor network structure to verify the effectiveness of the algorithm. Secondly, under the same k value, the influence of different perceptive nodes on algorithm performance is considered. The experiment results were obtained under the premise of executing 1000 Top-k queries.


## 5.2.1. Comparison of Predict Error Rates between ARIMA((1,3),3) and ARMA(2,2)

The experiment compares model ARIMA((1,3),3) with ARMA(2,2) model algorithm. The random function of C language was used to randomly select 18 time points from 23964 time axes and predict the sequence change values of the 18 time points in the next 5, 10, 15, and 20 steps, and then compare the predicted values with the actual values to obtain the error rates, so as to obtain the error rates in different groups with different predicted steps as shown in Figure5.Figure 5
Comparison of prediction error rate among different groups.
(a)
Forward five step forecast error rate(b)
Forward ten step forecast error rate(c)
Forward fifteen step forecast error rate(d)
Forward twenty step forecast error rate


## 5.2.2.T Value Determination

The value oft is the threshold predicted by the experiment model. The value of t will directly affect the performance of AAFU algorithm, and this paper mainly determines it through the experiment. According to the relative error shown in Figure 5, when t is set to 5 or 10, the error between the predicted value and the real value is relatively small, and this result is in line with common sense. It is easy to predict the data in the nearest future, while it is difficult to predict the data in the distant future. Therefore, AAFU algorithm adopts forward 5 step prediction when updating Windows.


## 5.2.3. Experimental Setup

Firstly, we consider the influence of differentk values in Top-k on algorithm performance under the same sensor network structure to verify the effectiveness of the algorithm. Secondly, under the same k value, the influence of different perceptive nodes on algorithm performance is considered. The experiment results were obtained under the premise of executing 1000 Top-k queries.


## 5.3. Result Analysis

According to Figure5, ARIMA((1,3),1,3) model has good prediction effect, and its accuracy exceeds ARMA(2,2) used by FAPU algorithm to a certain extent. According to the theory, in ARIMAp,d,q model, when d=0, it means that the model evolves into ARMA(2,2) model, so there is no accurate fitting effect. In ARIMA((1,3),1,3) model, the prediction performance is improved due to first-order difference processing of the original data, so that the sensor value at a certain future time can be accurately predicted and the error rate between the sensor value and the real value can be reduced.According to Figure6, when the number of sensor nodes is the same, different k values are set to verify the effectiveness of the algorithm. As known, with the increase of k value, the AFU algorithm is better than the FAPU algorithm gradually. This is because in the case of the same t step prediction, the prediction error rate of the AAFU algorithm model is lower and it can map to the cost update algorithm; it will get more accurate prediction, which will further reduce the number of update window, and reduce the relative traffic brought by the network update, and it can prolong the life cycle of sensor network.Figure 6
Commnication traffic base on the same number of nodes and differentk values.Figure7 shows that, when k=10, different n sensor nodes are selected to verify the effectiveness of the algorithm. The AAPU algorithm far exceeds algorithm FAPU. Even when the number of nodes in the network is 200, data transmission is reduced by 5000 times in 1000 Top-k queries, and the update transmission gap gradually increases with the increase of the number n of nodes. This is because under the same k value, the FILA-based filtering method only sets k+1 windows, and the number of windows is only related to K, not n. Therefore, the difference in the change of traffic is not big, but even so, AAPU algorithm reduces the traffic more than 5000 times compared with FAPU algorithm.Figure 7
Commnication traffic base on different numbers of nodes and the samek values.


## 6. Conclusion

In wireless sensor networks,Top-k query is often used to query the first k values to meet user conditions. In the process of query, in order to reduce the transmission of redundant data, different filtering windows can be set for each sensor node. However, if the filtering window is constantly updated due to the dynamic change of data, it will still lead to a huge consumption of node energy. In this paper, AAFU algorithm (ARIMA approach based on filter updating) is proposed based on existing research. This algorithm uses FILA and ARIMA models. In this algorithm, base stations use time series models to predict future node data based on the historical data collected. By comparing the energy consumption cost caused by updating the window, the problem of node updating can be dealt with in a more energy efficient way. The experiment proves that the communication consumption between sensor nodes can be reduced under different k values or different numbers of network nodes; thus, the life cycle of wireless sensor network can be effectively extended.



---

*Source: 4510625-2022-04-29.xml*