Efficient Data Gathering based on Linear Regression in Wireless Multivariate Monitoring Sensor Networks

INTRODUCTION

---

In Wireless Sensor Networks (WSNs), one of the main challenging research topics is to save severely constrained energy resources and effectively extend the lifetime of the network (Anastasi et al., 2009). The power consumption in a sensor node can be divided into three parts: sensing consumption, data processing consumption and transmission consumption. Most of power consumption in WSN is used for data transmission (Kimura and Latifi, 2005). Thus, minimizing the size of data will reduce transmission consumption (Ciancio and Ortega, 2004, 2005; Shan et al., 2011; Guo et al., 2010; Wei et al., 2010). Due to the redundant sensor node deployment for fault tolerance of communication connectivity, WSNs exhibit naturally high redundancy in spatio-temporal sampling. The sampled redundant attributes allow a significant reduction of communication overhead by data compression (Tulone and Madden, 2006; Mehmet et al., 2004). The reduction of power consumption directly bring into lifetime extension by using the data compression for the network nodes (Kolo et al., 2012; Srisooksai et al., 2012; Marco et al., 2012). The studies of Chou et al. (2003), Zixiang et al. (2004) give examples of applying the Slepian-Wolf theorem to compress collecting data in WSNs where correlated data streams are physically separated or each sensor node has limited computation capability. The compression schemes allow sensor nodes to compress their sensed data without collaboration and negotiation but need to know prior knowledge of the precise correlation in the data. However, many civil applications of WSNs, such prior knowledge is usually vague. Therefore, the compressive sensing techniques are presented by exploiting compressibility without relying on any specific prior knowledge or assumption on signals (Donoho, 2006; Zheng et al., 2012). These schemes provide decentralized compression in WSNs, but they cannot support multi-resolution compression. Wavelet-based compression support multi-resolution storage in a WSN by organizing the network into multiple levels. The Ganesan et al. (2003) adopt the three-dimensional discrete wavelet transform (3D-DWT) to generate spatio-temporal summarization of sensing data in each level. The different resolutions of sensing readings are obtained from different levels via drill-down queries. Although DIMENSIONS meets the data compression requirement, it is too complicated for sensor nodes because wavelet-based compression would incur high computation and storage complexity. Also, such complicated wavelet operations are performed at each level of the DIMENSIONS hierarchy. Ciancio and Ortega (2004) analyze the energy consumption of data compression and data reconstruction accuracy in using distributed and non-distributed wavelet transform mode. From the energy point of view, the literature (Ciancio and Ortega, 2004) studies local coefficient quantization distortion of data reconstruction and local coefficient quantization rules. Ciancil et al. (2006) based on a DWT propose an energy efficient data representation and routing scheme. Wagner et al. (2005, 2006) propose WSN distributed irregular wavelet transform schemes. The program take into account the sensor nodes deployed in space distribution is irregular, uneven and therefore can not be directly applied traditional wavelet transform.

Marcelloni and Vecchio (2009) introduced Huffman coding into wireless sensor nodes. Their simple lossless entropy compression algorithm which was based on static Huffman coding exploits the temporal correlation that exist in sensor data to compute a compressed version using a small dictionary, the size of the ADC resolution. The algorithm was particularly suitable for computational and memory resource constrained sensor nodes. The algorithm is static. Hence, the algorithm cannot adapt to changes in the source data statistics. Tharini and Ranjan (2009) proposed algorithm was a modified version of the classical adaptive Huffman coding. The algorithm does not require prior knowledge of the statistics of the source data and compression is per for med adaptively based on the temporal correlation that exists in the source data. The draw back of this algorithm is that it is computationally intensive. Maurya et al. (2011) proposed a compression algorithm that uses median predictor to decorrelate the sensed data. The proposed algorithm is simple and can be implemented in a few lines of code and uses the LEC compression table. The algorithm has similar compression complexity as LEC but lower compression efficiency. Since the LEC algorithm outperforms it, the algorithm will not be used for comparison with our algorithm. Liang and Peng (2010), proposed a scheme called two-modal transmission for predictive coding. In the first modal transmission which is called compressed mode, the compressed bits of error terms falling inside the interval [-R, R].

The algorithm of distributed regression has been addressed by many researchers till date. The problem of performing global regression is considered in a vertically partitioned data distribution scenariod (Hershberger and Kargupta, 2001). The authors propose a wavelet transform of the data such that, after the transformation, effect of the cross terms can be dealt with easily. The local regression models are then transmitted to the central station and combined to form the global regression model. The drawback of the algorithm is the need to the synchronization techniques that are unlikely to scale in large, asynchronous systems. Guestrin et al. (2004) presented a linear regression framework in a network of sensors using in-network processing of messages (Guestrin et al., 2004). Instead of transmitting the original data, the proposed technique transmits regression coefficients only, thereby reducing the communication energy consumption drastically. However, the major drawback is that their algorithm is not suitable for dynamic data. An algorithm based on multivariate correlation is proposed by Zhu et al. (2009). The algorithm can effectively reduce spatial-temporal and multivariate correlations, but all the raw data of cluster members in a cluster must be transmitted directly to the Cluster-Head (CH) and be compressed in the CH. The readings with different attributes but from different nodes are not differentiated and abstracted into a column of the processed data matrix. Before sending data, the CH must perform data preprocessing algorithm to analyze and find out the attribute pairs between which the correlation is large. Song et al. (2012) presented a distributed linear regression-based data gathering framework in clustered WSNs. The raw readings can be approximately represented under less than a prespecified threshold while the communication energy consumption can be significantly reduced by the framework. CH nodes perform linear regression operations and use historical sensory data to complete estimation of the actual monitoring measurements. Rather than transmitting original measurements to the sink station, CH nodes transmit constraints on the regression parameters.

In this study, we take into account the data collected by different sensing units in the same sensor node that is, multivariate data or multi-attribute data. In our method, all non-CH nodes collect the original data and select one variable as the base function of the other variables. Each node calculates the regression coefficients of the base variable by using the time as independent variable and the regression coefficients of the non-base variable by using the base variable as independent variable. Non-CH nodes transmit their coefficients to the CH. While the CH receives the coefficients from the active cluster members and sends the model coefficients to the remote sink node.

REGRESSION MODELS IN SENSOR NETWORKS

A wireless sensor network is composed by a set of N energy-constrained sensor nodes that are randomly deployed in two-dimensional field. Nodes can simultaneously a set of environmental attributes, such as temperature, humidity, light intensity, sound intensity, acceleration, video, etc., in which certain correlation universally exists.

Simple linear regression model: The current solutions of data reduction by means of linear regression are performed by using simple linear regression based on the least squares 7. In that case, each sensor node calculates regression coefficients by using the epoch/time as independent variable. Then, the sensor node sends its coefficients to the sink, instead of sending the readings.

Over time, a sensor node measures a function at some time t (e.g., temperature). Then, it collects a set of data points (t₁, x₁), (t₂, x₂),..., (t_m, x_m). Assume a set of basis functions B = (b₁, b₂,…, b_k) are given, the measurements can be approximated by these basis functions. That is, to find basis function coefficients w = (w₁, w₂,…, w_k)^T such that the measurements are approximated as:

where:

and k is the number of coefficients. When the number of coefficients is equal to the number of sampling (k = m), each x_j can be calculated exactly. However, such high-degree fit the noise into the monitoring data and generally generates poor results when used to predict unseen data points (t,x). When the number of coefficients is far smaller than the number of sampling (k = m), the coefficient vector w becomes a compressed representation of the sampling data.

Let X = (x(t₁), x(t₂),…, x(t_m))^T denotes the actual measurements vector with one row for each measurement. The basis matrix of the basis functions at the corresponding sampling time points was defined as matrix B:

(1)

where, B is an mxk matrix and x is an mx1 vector. Let denote the mx1 vector with one row for each approximation values at t_i sampling time points, then:

(2)

To guarantee the error bound of each approximation data and the corresponding sampling data, the approximation errors δ on Root Mean Squared error (RMS) are defined:

(3)

To minimize approximation errors, the optimization problem is stated as:

(4)

Setting the gradient of this quadratic objective to zero gives the optimal coefficients in matrix form:

(5)

Let A = B^TB and c = B^TX. The equations are following as:

We can transform the Eq. 5 to w* = (A)^-1 c, namely:

(6)

where, A denotes the dot-product matrix, where each element is the dot product between two basis functions. c is the projected measurement vector, where each element denotes simply the projection of the measurement vector into the space of a particular basis function. When the measurement vector and the basis functions are given, the optimal regression weights can be computed with simple matrix operations.

Over time, it is necessary to update the linear regression model for reconstruction of sampling data. We fit the coefficients of our basis functions with respect to the sampling data collected in the last T minutes. Suppose that the matrix A and c have been computed for the sampling data at times t₁,…, t_m-1 and a new measurement at time t_m are obtained as the following:

So, the matrix A of the basis functions and the projected measurement vector c are updated by the increment operation expression 7:

(7)

Similar to the operation expression (7), if measurement t₁ falls outside the time sliding window, the linear regression model is updated according to the Eq. 8:

(8)

Thus, when new measurements are received at any time, the dot-product matrix A of the basis functions and the projected measurement vector c can be updated by implementing the increment operations as well as the basis function coefficients of linear regression model can be computed by solving the linear system c = Aw*.

Multivariable linear regression model: In wireless multivariate monitoring Sensor Networks, a sensor node is able to perform monitoring of more than one variable. Moreover, the multivariate correlation is usually strong. The correlation happens due to the fact that each sensor node gathers correlated data from one or more attributes at a given time. It is observed in the nature of physical phenomena (Mehmet et al., 2004). The simple linear regression model is able to work over correlation, but it is not able to work over the multivariate correlation (more than one variable). In our solution, we use multivariate linear regression model to work over the multivariate correlation. The purpose of our paper is to apply the multivariate correlation method to improve prediction accuracy on WSN data reduction.

Suppose that a sensor node has P sensing units, the collected attribute is x_j, j = 1, 2,…, P. The overall operation of the regression-based compression scheme is as follows:

(9)

where, y_i denotes an attribute called response value and x_i,1, x_i,2,…, x_i,p-1 are the remaining p-1 attributes at a given time i. We can pack all response values for all actual measurements into an m-dimensional vector:

We can pack all predictors into a mx( p-1)+1 matrix:

We can pack the regression coefficients into a p-dimensional vector:

Using linear algebra notation, the model 9 can be compactly written:

In order to estimate β, we take a least squares approach to minimize Eq. 10:

(10)

And the regression coefficients can be determined by Eq. 11 through the least square evaluation:

(11)

Then, the missing sense data can be predicted according to Eq. 11.

Distributed algorithm using regression: The network model was assumed that a set of energy-constrained sensor nodes were randomly deployed in MxM two-dimensional field. The following assumptions are made for the sensor network. All sensor nodes are not mobile and unaware of their location. The immobile sink node is only and considered to be a powerful node endowed with enhanced communication and computation capabilities and no energy constraints. Sensor nodes can adjust the transmitting power according to the distance, namely, radio transmitting power of nodes is controllable. Sensor nodes are fitted with the same radio communication model. The radio channel is symmetric so that the energy required to transmit m-bit message from node i to node j is identical to the energy required to transmit m-bit message from j to i.

The existence of the temporal as well as spatial correlations brings the potential to significantly develop and implement the efficient communication protocols well-suited for the WSN paradigm. Here, the distributed algorithm is presented to exploit the spatio-temporal correlation characteristics of the clustered sensor network based on regression model that can approximate the raw data while significantly reducing the communication energy consumption.

In order to take advantage of the existence of nodes of different abilities inside a WSN, data gather processing makes use of the classical LEACH protocol (Heinzelman et al., 2002; Heinzelman et al., 2000). The nodes organize themselves into local clusters, with one node acting as the CH. All non-CH nodes collect the original data, calculate the coefficients by performing regression for original measurements and transmit their coefficients to the CH. While the CH receives the coefficients from the active cluster members and sends the model coefficients to the remote sink node. The processing principle of the distributed solution is derived as following.

Suppose that a sensor node has N sensing units, the collected attribute is A_j, j = 1, 2, L, N. Initially, each node selects an attribute as the base attribute according to the correlation coefficient matrix of multivariate sampling data. The correlation coefficient of the attribute between X and Y is denoted as Eq. 12:

(12)

Where:

and:

When the absolute value of is 1, the relationship between X1 and X2 is complete correlation. If sensor node uses attribute X₁ as independent variable, all the data points of attribute X₂ lie on the regression line. The smaller the absolute value of is, the lower the correlation is and the more scattered the data points are.

Fig. 1:	Regression algorithm

If each node can collect H attributes, the relationship among all attributes is defined as the correlation coefficient matrix R with the size H×H, in which the element of the jth column in the ith row denotes correlation coefficient between the i-th and the jth attribute. The best attribute Xj as independent variable is selected by Eq. 13:

(13)

If the estimate error of the attribute opt_fit_j using the time as independent variable is higher than the threshold, a node will re-selected sub-optimal attribute Xj as independent variable.

When the base attribute has been chosen, the node performs the regression algorithm, shown in Fig. 1. Each node N_i maintains a matrix A(i) and a vector c(i) that summarize, respectively the effect of this node’s measurements in the dot-product matrix and the projected easurement vector for its base attribute. When the node collects a new value, its local matrix and vector are updated using the incremental rule and an event is scheduled to delete this value when it falls outside the time window. The node computes the non-base attributes on the base attribute and transmits the calculated regression coefficients to the CH. The raw data of nodes is no longer required to be transmitted.

An alternative to transmitting all of the measurements is to build a regression model of this data in the network and transmit only the model coefficients. These lead to lesser packet transmissions and reduce redundancy, thereby helping in prolonging the network lifetime.

Table 1:	Ten successive measurements for different environmental attributes

Table 2:	Coefficient of the correlation analysis

Fig. 2:	Voltage regression curve of ten sampling time points

For example, instead of extracting the original measurement from node Ni every 10 sec, suppose that we have ten raw readings for every attribute during the sampling time, shown in Table 1. The correlation coefficient r results in Table 2 show that there is a greater correlation between the voltage variable and other variables gathered by the sensor nodes than with the time variable. Thus, we select the voltage variable as the base attribute. In order to perform simple computing, we wish to fit the last 10 sampling points with a degree-three polynomial: f(t) = w₀+w₁t+w₂t²+w₃t³ and only need to extract 4 parameters from the voltage readings: w₀, w₁, w₂ and w₃. More generally, given a set of basis functions of the voltage readings (e.g., 1, t, t² and t³), we would like to continuously fit their parameters and thereby reduce the dimensionality of the voltage readings. The model coefficient vector was computed by Eq. 6 that is, -0.1340, 1.7494, -5.9044, 382.4667. Therefore, the degree-three polynomial is Eq. 14. The real line denotes the regression prediction curve of ten voltage values in Fig. 2:

(14)

The other variables use voltage as independent variable to extract 2 parameters from temperature readings: β₁ and β₂ which was computed by Eq. 11. The red lines denote the regression estimate curves of ten prediction values other than voltage readings in Fig. 3.

EXPERIMENTS AND EVALUATION

Here, to analyze the validity of the regression strategy, we implemented it in a small WSN which contains frequency, power, current, voltage, panel temperature, pipe temperature, tank temperature and tank level readings gathered by multisensors in a solar water pressure monitoring system at intervals of 10 sec. These readings were held during the day, between 1 February and 5 April 2013. Thus, the data gathered for our simulation comes from a reality scenario. We compare the distributed linear regression-based strategy against the standard clustered LEACH and regression algorithm presented above.

Fig. 3(a-h):	Regression curves of different environmental attributes under voltage variable as independent variable

We provide a particular analysis of the proposed algorithm for the energy consumption and the prediction accuracy. The NS-2 software is used to implement and simulate the network system.

Evaluation of the energy consumption: For power consumption used for transmitting and receiving, we adopt a simple radio model by Heinzelman et al. (2002). Specifically, each node needs to run the circuitry for the power amplifier. Let e^r_l (J bit^-1) be the power consumption over the link l, when it receives one unit of data and e^t_l (J bit^-1) be the power consumption when one unit of data is sent over the link l. We have:

where, ε_elec is a distance-independent constant that denotes the energy consumption to run the transmitter or receiver radio electronics and ε_amp is the coefficient of the distance-dependent term that denotes the transmit amplifier. α is the path loss exponent which is usually between 2 and 4 for free-space and short-to-medium-range radio communication. For the experiments described in this study, the main simulation of the WSN are set as Table 3.

For these experiments, each node begins with only 0.5 J initial energy and 200 bytes control packets to send to the sink node. The CH node was determined at the beginning of each round which lasts for 20 sec. Node will generate energy consumption whenever a sensor in network transmits or receives data or performs regression operation. Figure 4 shows how the total energy consumption of the network at each round varies as the simulation time runs on for the proposed protocol and LEACH protocols. The simulation results demonstrate that the CH nodes of the proposed algorithm required less energy in the simulation time than LEACH protocol.

Table 3:	System parameters of the simulation scenarios

This is because a much smaller amount of packets was transmitted to the sink by CH using the regression estimate model to provide a structured prediction of the original data. The energy consumption increased slightly in each regression period for computing the model coefficients. The number of dead nodes in the network at each round is shown in Fig. 5. It can be seen from the figure that the number of dead nodes in our scheme is less than leach protocol. The reason is that each node just transmits the coefficients whose amounts are far less than the original amounts of data. So, the proposed algorithm saves energy and belongs the network lifetime.

Figure 6 shows that the base attribute regression estimate curve deviates from the actual measurements spot. The absolute value error between the measurements and regression prediction values are shown in Fig. 7.

Fig. 4:	Total energy consumption of the network at each round

Fig. 5:	Number of dead nodes in the network at each round

Fig. 6:	Base attribute regression curve at the varied sampling time points

Fig. 7:	Absolute value error between the measurements and regression prediction values

The variations in the absolute value error per round over time are small for each attributes. For the power sampling, the absolute value error of the last sampling time point is the biggest up to 9.5% which is below the certain prespecified error threshold.