Patent Publication Number: US-8983793-B2

Title: Compressive data gathering for large-scale wireless sensor networks

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of, and claims priority to, U.S. patent application Ser. No. 12/696,415, filed on Jan. 29, 2010, and entitled COMPRESSIVE DATA GATHERING FOR LARGE-SCALE WIRELESS SENSOR NETWORKS, the entirety of which is incorporated herein by reference. 
    
    
     BACKGROUND 
     A sensor network, such as a wireless sensor network, typically includes spatially distributed autonomous sensor nodes to monitor physical or environmental conditions, such as temperature, humidity, pressure, sound, vibration, motion or pollutants. Applications range from habitat monitoring and traffic control to surveillance. Each sensor node includes one or more sensors, and is typically equipped with a radio transceiver or other wireless communication device as well as a power source such as a battery. Sensor readings are transmitted by the sensor nodes and received by a data sink, or data collection device, either directly or via one or more other sensor nodes. The received sensor readings are processed by the data sink or forwarded on by the data sink to a network, computing device, or communication device. 
     In general, large scale sensor data gathering is accomplished through multi-hop routing from individual sensor nodes to the data sink. Successful deployment of such large scale sensor networks typically faces two major challenges, namely: reduction of global communication cost and energy consumption load balancing. 
     The need for global communication cost reduction arises from the fact that such sensor networks typically include hundreds to thousands of sensors, generating tremendous amount of sensor data to be delivered to the data sink. It is very much desired to take full advantage of the correlations among the sensor data to reduce the cost of communication. Existing approaches adopt in-network data compressions, such as entropy coding or transform coding, to reduce global traffic. However, these approaches tend to introduce significant computation and control overheads that often are not suitable for sensor network applications. 
     The need for energy consumption load balancing arises from the fact that large-scale sensor networks typically require multi-hop data transmission.  FIG. 1  illustrates a large-scale wireless sensor network  100  where sensors are densely deployed in the region of interest to monitor the environment on a regular basis. Suppose N sensors, denoted as s 1 , s 2 , s 3  . . . s N  form a multi-hop route to the data sink  102 , with d j  denoting the readings obtained by the sensor in node s j . A typical way of transmitting d j , j=1, 2, 3 . . . N to the data sink  102  is through multi-hop relay as depicted in  FIG. 1 . In particular, node s 1  transmits sensor reading d 1  to s 2 , node s 2  transmits sensor readings d 2  from its own sensor as well as the relayed reading d 1  to node s 3 , and so on. At the end of the route, node s N  transmits all N readings to the data sink  102 . It can be observed that the closer a sensor node is to the data sink, the more energy is consumed. This is because not only the node transmits the readings of its own sensor but also all the relayed sensor readings. As a result, the sensor nodes closer to the data sink  102  tend to run out of energy, and the lifetime of the sensor network will be significantly shortened. 
     SUMMARY 
     Techniques for data gathering in large-scale wireless sensor networks are described. In one aspect, a first sensor node transmits to a second sensor node a first value that is a product of a first pseudo-random number and the sensor reading of a first sensor. The second sensor node transmits a sum of the first value and a second value, where the second value is a product of a second pseudo-random number and the sensor reading of a second sensor. The transmitted sum of the first and second values will eventually be received and processed by a data collection device. 
     This summary is provided to introduce concepts relating to wireless sensor network data gathering. These techniques are further described below in the detailed description. This summary is not intended to identify essential features of the claimed subject matter, nor is it intended for use in determining the scope of the claimed subject matter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same reference numbers in different figures indicate similar or identical items. 
         FIG. 1  illustrates convention data gathering in a large-scale wireless sensor network. 
         FIG. 2  illustrates data gathering in a large-scale wireless sensor network according to one embodiment. 
         FIG. 3  illustrates a transmitted signal and its representation in discrete cosine transform domain. 
         FIG. 4  illustrates the transmitted signal of  FIG. 3  with two abnormal readings and its representation in discrete cosine transform domain. 
         FIG. 5  illustrates the transmitted signal of  FIG. 4  decomposed into two signals. 
         FIG. 6  illustrates the concept of data reordering according to the present disclosure. 
         FIG. 7  illustrates an exemplary diagram of data center temperature sensing. 
         FIG. 8  illustrates an exemplary diagram of temperature sensor readings at one point in time. 
         FIG. 9  illustrates an exemplary diagram of temperature sensor readings at another point in time. 
         FIG. 10  illustrates sensor transmission loads in baseline transmission and basic compressive data gathering schemes. 
         FIG. 11  illustrates an exemplary cluster-based routing structure. 
         FIG. 12  illustrates a block diagram of an illustrative computing device that may be used to perform data gathering in a wireless sensor network. 
         FIG. 13  illustrates a flow diagram of a process of data gathering in a large-scale wireless sensor network according to one embodiment. 
         FIG. 14  illustrates a flow diagram of a process of data gathering in a large-scale wireless sensor network according to another embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     Overview 
     The present disclosure describes techniques for compressive data gathering in large-scale wireless sensor networks and aims to address the two major challenges as outlined above. Firstly, it is believed the proposed compressive data gathering scheme is able to achieve substantial sensor data compression without introducing excessive computation and control overheads. Secondly, it is also believed the proposed scheme is able to disperse the communication costs to all sensor nodes along a given sensor data gathering route. This will result in a natural load balancing and thus prolong the lifetime of the sensor network. 
     By applying compressive data gathering, or compressive sampling, to in-network data compression, a number of benefits can be achieved. Such benefits include simple encoding process, less inter-node data exchange, and decoupling of compression from routing. In addition, compressive sampling can deal with abnormal sensor readings gracefully. Moreover, data reconstruction is not sensitive to packet losses. In compressive sampling, all data received by the data sink are equally important. This is different from distributed source coding, where received data are predefined as main or side information and thus loss of main information will cause serious errors in decoding. 
     While aspects of described techniques relating to data gathering in large-scale wireless sensor networks can be implemented in any number of different computing systems, environments, and/or configurations, embodiments are described in context of the following exemplary system architecture(s). 
     Illustrative Data Gathering in Large-Scale Wireless Sensor Networks 
     The basic idea of the proposed compressive data gathering is depicted in  FIG. 2 , which illustrates data gathering in a large-scale wireless sensor network  200  according to one embodiment. Rather than receiving relayed sensor readings, the data collection device  202  receives a number of weighted sums of all the readings. Each sensor node in the network transmits M weighted sums to its parent node, which is a neighboring node that is one hop closer to the data collection device  202 , and M is a positive integer. For example, to transmit the i th  sum to the data collection device  202 , sensor node s 1  multiplies its sensor reading d 1  with a pseudo-random coefficient φ i1  and transmits the product, φ i1 d 1 , to its parent node s 2 . Here, the index i denotes the i th  weighted sum ranging from 1 to M. Similarly, sensor node s 2  multiplies its sensor reading d 2  with a pseudo-random coefficient φ i2  and adds the product, φ i2 d 2 , to the received product φ i1 D 1 , and then transmits the aggregate result, φ i1 d 1 +φ i2 d 2 , to its parent node s 3 . Accordingly, each sensor node s j  contributes to the relayed message by adding its own product. Finally, the data collection device  202  receives a weighted sum of all the sensor readings, Σ j=1   N Φijdj. This process is repeated using M sets of different weights so that the data collection device  202  will receive M weighted sums. 
     Accordingly, all sensor nodes in the network transmit M messages and consume the same amount of energy. Each node only performs one addition and one multiplication in order to compute one weighted sum. Comparing  FIG. 1  and  FIG. 2 , it can be seen that although the first M nodes transmit more messages in the proposed compressive data gathering scheme than in a conventional scheme, the rest of nodes transmit less messages in the compressive data gathering scheme. When N, the number of nodes in a data gathering route, is large and M is much smaller than N, the proposed compressive data gathering scheme can significantly reduce the total number of transmissions and thereby save energy consumption. In general, the communication cost with a baseline transmission scheme as shown in  FIG. 1  is in the order of N(N+1)/2, whereas the communication cost with the proposed compressive data gathering scheme as shown in  FIG. 2  is in the order of NM. In addition, higher efficiency can be achieved if correlated sensor readings are transmitted jointly rather than separately. 
     In practice, as sensors are usually deployed in a two-dimensional area, the ensemble of routing paths tends to present a tree structure as shown in  FIG. 2 . In  FIG. 2 , the data collection device  202  has three children, each of which leading a sub-tree. Data gathering and reconstruction of compressive data gathering are performed on the sub-tree basis. In order to combine sensor readings while relaying the sensor readings, every sensor node needs to know its local routing structure. That is, each node knows whether or not a given node is a leaf node in the routing tree or how many children the node has if it is an inner node. In one embodiment, when a node selects a neighboring node to be its parent node, the node transmits a “subscribe notification” to the selected parent node. When a node changes parent, the node transmits an “unsubscribe notification” to the ex-parent node. 
     The compressive data gathering scheme can be described with reference to the routing tree in the dash-lined section of  FIG. 2 . After the sensors in the nodes ss 1 -ss 8  acquire their readings, the leaf nodes initiate the transmission. For example, the node ss 2  generates a pseudo-random number, or coefficient, φ i2 , computes φ i2 d 2 , and transmits the value to its parent node ss 1 . The node ss 4 , ss 5  and ss 6  transmit φ i4 d 4 , φ i5 d 5  and φ i6 d 6  to their parent node ss 3 . Once node ss 3  receives the three values from its children nodes, it computes φ i3 d 3 , adds it to the sum of relayed values and transmits Σ j=3   6 φijdj to its parent node ss 1 . Similarly, the node ss 8  transmits φ i8 d 8  to its parent node ss 2 , which adds φ i7 d 7  to the received data and transmits the sum to its parent node ss 1 . The node ss 1  computes φ i1 d 1  and subsequently transmits Σ j=1   8 Φijdj to its parent node. Finally, the data is forwarded to the data collection device  202 , which contains the weighted sum of all readings in the sub-tree. 
     Assuming that there are N nodes in a particular sub-tree, then the i th  weighted sum can be represented by:
 
 y   i =Σ j=1   N   Φijdj   (1)
 
     For this sub-tree, the data collection device  202  obtains M weighted sums {y i }, where i=1, 2 . . . M. Mathematically, equation (1) can be expressed as: 
     
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             y 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                         
                       
                       
                         
                           
                             y 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             2 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           yM 
                         
                       
                     
                     ) 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               11 
                             
                           
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               12 
                             
                           
                           
                             … 
                           
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               1 
                               ⁢ 
                               N 
                             
                           
                         
                         
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               21 
                             
                           
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               22 
                             
                           
                           
                             … 
                           
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               2 
                               ⁢ 
                               N 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               M 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               1 
                             
                           
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               M 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               2 
                             
                           
                           
                             … 
                           
                           
                             
                               Φ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               MN 
                             
                           
                         
                       
                       ) 
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             
                               d 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               1 
                             
                           
                         
                         
                           
                             
                               d 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             dN 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     In equation (2), each column of {φ ij } contains the series of pseudo-random numbers, or coefficients, each of which generated at a corresponding node. In order to avoid transmitting this pseudo-random matrix from the sensor nodes to the data collection device  202 , the data collection device  202  broadcasts a random seed to the entire network before data transmission by the sensor nodes. Each sensor node uses this random seed and its respective identification to generate the series of pseudo-random numbers. This generation process can be reproduced by the data collection device  202  to recover the {φ ij } matrix. 
     In equation (2), d i  (where i=1, 2 . . . N) is a scalar value. In a practical sensor network, each node may include one or more sensors with each sensor being of a type different from the other. For example, one sensor of a given sensor node may be a temperature sensor while another sensor of the given sensor node may be a pressure sensor. Accordingly, sensor readings from each sensor node can be seen as a multi-dimensional vector. In one embodiment, sensor readings of each type are separated out and processed respectively. In another embodiment, since the pseudo-random coefficients φ ij  are irrelevant to sensor readings, d i  may be treated as a vector. The weighted sums y i , in such case, become vectors of the same dimension as well. 
     Recovery of Spatially Correlated Data 
     According to compressive sampling theory, a K-sparse signal can be reconstructed from a small number of measurements with a probability close to 1. The weighted sums obtained in equation (2) are measurements of a typical type. Signal sparsity characterizes the correlations within a signal. Signal sparsity can be in one or more domains including temporal domain, frequency domain, and spatial domain. An N-dimensional signal is considered as a K-sparse signal if there exists a domain in which this signal can be represented by K (where K&lt;&lt;N) non-zero coefficients.  FIG. 3(   a ) shows an illustrative 100-dimensional signal in its original time domain and, as can be seen, the signal is not sparse in this domain. Because of the signal correlation, the signal can be described more compactly in transform domain such as wavelet and discrete cosine transform (DCT).  FIG. 3(   b ) shows a representation of the same signal in DCT domain. As can be seen, there are only five non-zero DCT coefficients. Therefore, this signal is a 5-sparse signal in the DCT domain. 
     In a densely deployed sensor network, sensors have spatial correlation in their readings. Let N sensor readings form a vector d=[d 1  d 2  . . . d N ] T , then d is a K-sparse signal in a particular domain ψ. Denote Ψ=[ψ 1  ψ 2  . . . ψ N ] as the representation basis with vectors {ψ i } as columns, and x=[x 1  x 2  . . . x N ] T  are the corresponding coefficients. The, d can be represented in the ψ domain as:
 
 d=Σ   i=1   N   xiψi,  
 
or
 
 d=Ψ   x   (3)
 
     According to the compressive sampling theory, a K-sparse signal can be reconstructed from M measurements if M satisfies the following condition:
 
 M≧c·μ   2 (Φ,Ψ)· K ·log  N   (4)
 
where c is a positive constant, Φ is the sampling matrix as defined in equation (2), and μ(Φ,Ψ) is the coherence between sampling basis Φ and representation basis Ψ. The coherence metric measures the largest correlation between any two elements of Φ and Ψ, and is defined as:
 
μ(Φ,Ψ)=√{square root over ( N )}·max 1≦i,j≦N   |     Φi,ψi     |   (5)
 
     From equation (5), it can be seen that the smaller the coherence between Φ and Ψ is, the fewer measurements are needed to reconstruct the signal. In practice, it is a convenient choice to use random measurement matrix, since a random basis has been shown to be largely incoherent with any fixed basis, and M=3K˜4K is usually sufficient to satisfy equation (4). 
     With sufficient number of measurements, the data collection device  202  is able to reconstruct sensor readings by solving an l 1 -minimization problem: 
     
       
         
           
             
               
                 
                   
                     
                       
                         min 
                         
                           x 
                           ⁢ 
                           
                               
                           
                           ∈ 
                           
                             ℝ 
                             N 
                           
                         
                       
                       ⁢ 
                       
                         
                           
                              
                             x 
                              
                           
                           
                             l 
                             1 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           s 
                           . 
                           t 
                           . 
                           
                               
                           
                           ⁢ 
                           y 
                         
                       
                     
                     = 
                     
                       Φ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       d 
                     
                   
                   , 
                   
                     d 
                     = 
                     
                       Ψ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       x 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     In addition, for sparse signals whose random projections are contaminated with noise, reconstruction can be achieved by solving a relaxed l 1 -minimization problem, where ε is a predefined error threshold: 
     
       
         
           
             
               
                 
                   
                     
                       
                         min 
                         
                           x 
                           ⁢ 
                           
                               
                           
                           ∈ 
                           
                             ℝ 
                             N 
                           
                         
                       
                       ⁢ 
                       
                         
                           
                              
                             x 
                              
                           
                           
                             l 
                             1 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           s 
                           . 
                           t 
                           . 
                           
                               
                           
                           ⁢ 
                           
                             
                                
                               
                                 y 
                                 - 
                                 
                                   Φ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   d 
                                 
                               
                                
                             
                             
                               l 
                               2 
                             
                           
                         
                       
                     
                     &lt; 
                     ε 
                   
                   , 
                   
                     d 
                     = 
                     
                       Ψ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       x 
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     Suppose  x  is the solution to this convex optimization problem, the proposed reconstruction of the original signal is  d =Ψ x . Hence, the Ψ matrix describes the correlation pattern among sensor readings. For example, if sensor readings are piece-wise smooth, wavelet transform matrix such as Ψ may be used. It shall be noted that sensors do not use the correlation pattern during data gathering process. The correlation pattern is used by the data collection device  202  or another computing device during data recovery. 
     Recovery of Data with Abnormal Sensor Readings 
     When abnormal events take place, the sparsity of sensor readings tends to be compromised. As an example,  FIG. 4(   a ) differs with  FIG. 3(   a ) only by two abnormal readings. The corresponding DCT coefficients shown in  FIG. 4(   b ) are not sparse. Therefore, the signal in  FIG. 4  is not sparse in either the time domain or the transform domain. In this situation, conventional compression techniques require transmission of significantly more data by the sensor nodes in order to reconstruct the original signal. However, as a result, distributed source coding techniques will have considerable degradation. 
     To address the issue with abnormal readings, in one embodiment, sensor data readings are decomposed into two vectors:
 
 d=d   0   +d   s   (8)
 
where d 0  contains the normal readings that are sparse in a certain transform domain, and d s  contains the deviated values of abnormal readings. Since abnormal readings are sporadic in nature, d s  is a sparse signal in the time domain. Suppose the normal readings are sparse in the Ψ domain, then equation (8) can be rewritten as:
 
 d=Ψx   0   +Ix   s   (9)
 
where I is the identical matrix, and both x 0  and x s  are sparse. Thus, signal d is decomposed into two signals which are sparse in different domains. An overcomplete basis Ψ′=[Ψ I] can be constructed, and d is sparse in the Ψ′ domain:
 
 d=Ψ′x,  
 
 x=[x   0   T   x   0   T ] T   (10)
 
     By incorporating equation (10) into equation (6) or (7), signal recovery with abnormal readings can be solved similarly by the l 1 -norm optimization. Existing research can show that stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system is possible. Moreover, existing research can also show that stable recovery of sparse signal in an overcomplete dictionary also works for noisy data, and the optimally-sparse approximation to the noisy data, to within the noise level. The result differs from the optimally-sparse decomposition of the ideal noiseless signal by at most a constant multiple of the noise level. 
     Suppose  x  is a vector of length 2N, and is the solution to the l 1 -minimization problem defined in equation (7) when an overcomplete dictionary is used. Similarly, the original sensor readings can be reconstructed by  d =Ψ′ x . Denote  x   s  as an N-dimensional vector composed of the last N elements of  x , then the non-zero values in  x   s  indicate the positions of abnormal readings. 
     For example, as shown in  FIG. 5 , the signal d of  FIG. 4(   a ) with two abnormal readings may be decomposed into two vectors d 1  and d 2 , where d 1  represents the signal of  FIG. 3(   a ) without the two abnormal readings and d 2  represents the two abnormal readings. That is, d 1  is a 5-sparse signal in the DCT domain as previously discussed with reference to  FIG. 3(   b ) and d 2  is a 2-sparse signal in the time domain. Consequently, the signal d of  FIG. 4(   a ) can be represented as a 7-sparse signal as d=d 1 +d 2 =+Ψx 1 +Ix 2 =[Ψ I][x 1   T  x 2   T ] T  as shown in  FIG. 5 . 
     Recovery of Data without Sparsity in any Intuitively Known Domain 
     If a signal is not sparse in any intuitively known domain, data recovery is still possible by reshuffling, or reordering, data points of the signal. The basic concept is illustrated in  FIG. 6 .  FIG. 6(   a ) shows an original collection of data points over time without sparsity in any intuitively known domain. In this example, the data points represent sensor reading values at different points in time. By reordering the data points in the time domain t, the data points can be re-organized in a descending order in values to result in an apparently sparse signal as shown in  FIG. 6(   b ). To further illustrate the point, an experiment of temperature readings in a data center was carried out and will now be discussed. 
     A contemporary application of wireless sensor networks is the monitoring of server temperatures in data centers. The temperature of a server is generally indicative of server load and, thus, abnormal temperature readings tend to indicated warning.  FIG. 7(   a ) shows rack and temperature sensor locations in a data center, where each rectangular shape represents a rack and each oval shape indicates a sensor placed at the top, middle, or bottom of a respective rack. As shown in  FIG. 7(   a ), most of the racks are equipped with three sensors while some racks are not monitored and a few other ones have only one or two sensors. In this experiment, there are 498 temperature sensors total. Temperature data are measured every 30 seconds and transmitted to a data sink through a baseline scheme. In this network, each node only communicates with adjacent nodes. For simplicity, it is assumed that all 498 sensors form one sub-tree to the data sink. The energy gain over baseline scheme is similar if sensors form two or more sub-trees. 
       FIG. 7(   b ) shows a snapshot of sensor readings from the temperature sensors. For clarity, only the sensor readings from the bottom of each rack (167 sensors total) are shown and the data of each column are placed side by side. One observation on this set of data is that the sensor readings exhibit little or no apparent spatial correlations. In other words, these data are not sparse in any intuitively known domain. Although the racks are physically close to one another, temperature readings are dominated by server loads rather than by ambient temperature. The entire data set containing sensor readings from all 498 sensors were checked and they are not apparently sparse either. Therefore, conventional compression mechanisms will fail in this situation. 
     With data reordering, the sensor readings d i  can be re-organized into an apparently sparse signal. In particular, the sensor readings d i  are sorted in ascending order according to their respective values at a particular moment t 0 . The resulting vector d is piece-wise smooth and sparse in wavelet domain. Moreover, since server temperatures do not change violently, sensor readings collected within a relatively short time period can also be regarded as piece-wise smooth if organized in the same order.  FIG. 8(   a ) and  FIG. 9(   a ) show the ordered sensor readings 10 minutes and 30 minutes after t 0 , respectively. They are generally in ascending order with only some small fluctuations. There are also a few significant spikes indicating abnormal temperature readings. 
     Based on the proposed compressive data gathering scheme, the noisy sparse signals with spikes can be reconstructed from M random measurements, where M&lt;N.  FIGS. 8(   b ) and  8 ( c ) and  FIGS. 9(   b ) and  9 ( c ) show the reconstruction results from M=0.5N and M=0.3N measurements at two time instances. The average reconstruction precision is over 98%. More importantly, the abnormal readings are accurately captured. 
     To cope with the situation that temporal correlation becomes weak when the time interval increases, in one embodiment the ordering of d i  is refreshed periodically. For example, for every one or two hours, the data sink requests M random measurements, where M=N, in one data gathering process. When M=N, the variables in equation (2) are solvable and the data sink is able to obtain the exact values of d i . Afterwards, the data sink can re-sort d i  and use this new ordering for data reconstruction in the subsequent hour or two. 
     Both conventional compression and distributed source coding are unable to exploit this type of sparsity which is observed only at certain reshuffled ordering. In conventional compression, explicit data communication is required between correlated nodes. If correlated nodes are not physically close to each other, the communication between them may take multiple hops. This introduces high overheads and makes compression procedure costly. In distributed source coding, nodes are classified into main nodes and side nodes. The data sink allocates appropriate number of bits to each node according to the correlation pattern. However, if the correlation pattern is based on changing sensor ordering, the data sink needs to carry out these two tasks and communicate the results to every single node periodically. In contrast, the data gathering process in compressive data gathering is unaffected, even when the ordering of d i  changes. The knowledge of correlation is only used in the data reconstruction procedure. 
     Chain-Type Topology 
     As described above,  FIG. 1  illustrates the baseline transmission scheme while the upper portion of  FIG. 2  illustrates the basic compressive data gathering (CDG) scheme in a chain-type topology. The graph in  FIG. 10  compares the communication costs of the two schemes. The horizontal axis represents sensor nodes from leaf to the data sink, and the vertical axis represents the number of messages sent by each node. It can be seen that the basic compressive data gathering scheme tends to have a small bottleneck load M. Yet, when the required number of measurements increases (e.g., from M to M′), the global communication cost of the basic compressive data gathering scheme could be even higher than that of the baseline transmission scheme. To overcome such drawback, in one embodiment, without additional sparsity assumption over partial sensor readings, the lower-bound communication cost of each sensor node is the smaller of the number of messages transmitted in the two schemes shown in  FIG. 10 . In other words, the baseline transmission scheme is adopted for the first M sensor nodes, while the compressive data gathering scheme is adopted for the remaining N−M sensor nodes in a chain, where M and N are positive integers and M is less than N. Thus, M of the N sensor nodes transmit their sensor readings in accordance with the baseline transmission scheme as shown in  FIG. 1  while the remaining N−M sensor nodes transmit sensor readings (including sensor readings from their own sensors and those from their child nodes, if any) in accordance with the compressive data gathering scheme as shown in  FIG. 2 . 
     In terms of mathematical expression, Φ is split into two parts, denoted as Φ=[Φ 1 Φ 2 ], where Φ 1  is an M×M sub-matrix, and Φ 2  is an N×(N−M) sub-matrix. The entries in Φ 2  can still be drawn according to (0, 1/M), i.e., Φ 2 =R, but the entries in Φ 1  need to be re-designed. 
     The second choice for Φ 1  is the identity matrix. With Φ denoted as Φ=[I R], the transmission scheme can be named IR-CDG. The Φ matrix can be written as follows: 
                   Φ   =     (         1       0       …       0       ❘           Φ   ⁢           ⁢   1   ⁢   M     +   1         …         Φ   ⁢           ⁢   1   ⁢   N             0       1       …       0       ❘           Φ   ⁢           ⁢   2   ⁢   M     +   1         …         Φ   ⁢           ⁢   2   ⁢   N             ⋮       ⋮       ⋱       ⋮       ❘       ⋮       ⋮       ⋮           0       0       …       1       ❘           Φ   ⁢           ⁢   MM     +   1         …         Φ   ⁢           ⁢   MN           )             (   11   )               
By using [I R] as the measurement matrix, the first M sensor nodes simply transmit their original sensor readings to sensor node s M+1 . Upon receiving the reading from sensor node s i , sensor node s M+1  computes the i th  product and transmits d i +Φ M+1i d M+1  to the next node. In IR-CDG, the first M sensor nodes do not have any computation load, and the rest of the sensor nodes, or the remaining N−M sensor nodes, have the same computation and communication load as in the basic compressive data gathering scheme.
 
     As can be seen in equation (11), the measurement matrix is composed of the weights, or coefficients, with which sensor nodes multiply their readings. In one embodiment, all the entries of the measurement matrix are drawn from Gaussian distribution N(0, 1/M). In another embodiment, a maximum of M columns can be drawn from the identity matrix of dimension M, and the entries of the rest of the columns are drawn from Gaussian distribution N(0, 1/M). 
     Tree-Type Topology 
     In many sensor networks, such as wireless sensor networks, sensors spread out in a two-dimensional area, and the routing paths from sensors to the data sink may present a tree structure. In a first scenario, sensor nodes are similarly equipped, so load balancing in measurement generation is a critical issue. In a second scenario, certain nodes are more powerful than others in terms of storage, computation capability, and power supply. Accordingly, the application of compressive data gathering can be more flexible in the second scenario. 
     When the compressive data gathering scheme is applied to homogeneous networks with tree-type routing structure, compressive data gathering is performed on sub-tree basis, i.e., the data sink solves the set of linear equations from each direct neighbor separately. Assuming that the i th  sub-tree contains N i  sensor nodes, the readings can be recovered from M i  measurements. Every node in this sub-tree transmits M i  messages. 
     Similar to the chain-type topology, matrix [I R] can be used for measurement generation in each sub-tree. In other words, at most M i  nodes can send one original reading instead of M i  weighted sums. Different from the chain-type topology, the nodes which send original readings do not have to be the first M i  nodes in vector d. Since shuffling the columns of the measurement matrix does not change its RIP, we can freely choose these nodes, and assign them with a different sequence number between 1 and M i . for the sake of communication cost reduction, it is preferred that these nodes are leaf nodes or close to the periphery of the routing tree. Ideally, IR-CDG can reduce M i (M i −1) transmissions in the i th  sub-tree when compared to the basic compressive data gathering scheme. 
     It is very common in wireless sensor nodes that certain number of power nodes or transmission units are deployed in strategic locations to relieve the transmission loading on other nodes.  FIG. 11  illustrates a typical two-tier network in which common sensor nodes communicate with respective cluster heads C 1 -C 7  either directly or through a few relays. The cluster heads C 1 -C 7  form a second-tier relay network, either chain-type or tree-type, to transmit data to the data sink. Although seven cluster heads are shown in  FIG. 11 , different number of cluster heads may be employed. 
     In such heterogeneous networks, the sensor nodes can be divided into sub-trees, and [I R] can be used as the measurement matrix in each sub-tree. However, since routing trees are quite shallow in this case, the number of leaf nodes are usually larger than M i  in each sub-tree. More efficiently, the additional storage and computational power of the cluster heads C 1 -C 7  can be utilized to reduce the communication costs of the common nodes. In particular, each common node may transmit original sensor readings to its respective cluster head, and each of the cluster heads C 1 -C 7  generates random coefficients and computes weighted sums for all nodes in its cluster. In the second tier network, the cluster heads add up the weighted sums from different clusters while relaying the sums to the data sink. As shown in  FIG. 11 , for example, the leaf nodes of the cluster heads C 1 -C 7  transmit sensor readings to the respective cluster heads which in turn transmit the sensor readings (including those from the sensors associated with the cluster heads) either directly to the data sink or to another one of the cluster heads C 1 -C 7 . It is clear that the measurement matrix formed in this way is also a full Gaussian random matrix. It has exactly the same RIP as the random measurement matrix formed in the basic compressive data gathering scheme. 
     Illustrative Computing Device 
       FIG. 12  illustrates a representative computing device  1200  that may implement the techniques for data gathering and recovery. However, it will be readily appreciated that the techniques disclosed herein may be implemented in other computing devices, systems, and environments. In one embodiment, the data collection device  202  of  FIG. 2  may be implemented with the computing device  1200 . In another embodiment, any one of the sensor node of  FIG. 2  may be implemented with the computing device  1200 . The computing device  1200  shown in  FIG. 12  is only one example of a computing device and is not intended to suggest any limitation as to the scope of use or functionality of the computer and network architectures. 
     In at least one configuration, computing device  1200  typically includes at least one processing unit  1202  and system memory  1204 . Depending on the exact configuration and type of computing device, system memory  1204  may be volatile (such as random-access memory, or RAM), non-volatile (such as read-only memory, or ROM, flash memory, etc.) or some combination thereof. System memory  1204  may include an operating system  1206 , one or more program modules  1208 , and may include program data  1210 . The computing device  1200  is of a very basic configuration demarcated by a dashed line  1214 . Again, a terminal may have fewer components but may interact with a computing device that may have such a basic configuration. 
     The program module  1208  includes a data gathering and recovery module  1212 . When the data collection device  202  is implemented with the computing device  1200 , the module  1212  is configured to recover sensor readings received from the sensor nodes of the network  200 . For example, the module  1212  is capable of recovering sensor reading d i  received from sensor node s i , where i=1, 2 . . . N, as described above. In one embodiment, the module  1212  is configured to carry out the process  600  as described below. 
     When a sensor node s i  is implemented with the computing device  1200 , the module  1212  is configured to generate a pseudo-random coefficient φ i  using the random seed received from the data collection device  202 , multiply sensor reading d i  by the pseudo-random coefficient φ i . If the particular sensor node s i  is a parent node, the module  1212  is further configured to add the received data from its child node to the product φ i d i , and transmit the resultant aggregate data so that the aggregate data is eventually received by the data collection device  202 . In one embodiment, the module  1212  is configured to carry out the process  700  as described below. 
     Computing device  1200  may have additional features or functionality. For example, computing device  1200  may also include additional data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Such additional storage is illustrated in  FIG. 12  by removable storage  1216  and non-removable storage  1218 . Computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. System memory  1204 , removable storage  1216  and non-removable storage  1218  are all examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device  1200 . Any such computer storage media may be part of the computing device  1200 . Computing device  1200  may also have input device(s)  1220  such as keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s)  1222  such as a display, speakers, printer, etc. may also be included. 
     Computing device  1200  may also contain communication connections  1224  that allow the computing device  1200  to communicate with other computing devices  1226 , such as over a network which may include one or more wired networks as well as wireless networks. Communication connections  1224  are some examples of communication media. Communication media may typically be embodied by computer readable instructions, data structures, program modules, etc. 
     It is appreciated that the illustrated computing device  1200  is only one example of a suitable device and is not intended to suggest any limitation as to the scope of use or functionality of the various embodiments described. Other well-known computing devices, systems, environments and/or configurations that may be suitable for use with the embodiments include, but are not limited to, personal computers (PCs), server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-base systems, set top boxes, game consoles, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and/or the like. 
     Illustrative Operations 
       FIG. 13  illustrates a process  1300  of data gathering by a data collection device in a large-scale wireless sensor network according to one embodiment. 
     At  1302 , aggregate data from at least one sensor node of a group of N sensor nodes is received by the data collection device. The aggregate data includes M weighted sums of sensor readings from the N sensor nodes. Each of the M weighted sums includes a respective sum of N products from the N sensor nodes. Each of the N products of each of the M weighted sums is a product of a respective coefficient and a sensor reading from a respective one of the N sensor nodes. Here, M and N are both positive integers greater than zero and M is less than N. At  1304 , computation is performed on the aggregate data to recover the sensor readings from the N sensor nodes. 
     For example, a data sink such as the data collection device  202  of  FIG. 2  receives aggregate data from a sensor node, such as s N , of a group of N sensor nodes. The aggregate data is a result of each of the N sensor nodes generating M pseudo-random coefficients with a random seed, multiplying its respective sensor reading with the M coefficients to produce M respective products. If a sensor node has not child node, it transmits its respective M respective products to its parent node. On the other hand, if a sensor node is a parent node of at least one other sensor node, the parent node adds the respective M products received from the child node to the respective M products of the parent node to arrive at a set of M values and then transmits those M values to its parent node. Accordingly, M different weighted sums of N products, constituting the aggregate data, will be transmitted by the last sensor node of a sub-tree of N sensor nodes to the data sink. In order for the sensor readings to be recoverable, M needs to be smaller than N but larger than K, which is the degree of sparsity of the sensor readings. 
     In one embodiment, the data sink receives the aggregate data as one data packet. Alternatively, the data sink receives the aggregate data as M data packets each having one of the M weighted sums. 
     After the data sink receives the aggregate data, the data sink performs computation on the aggregate data to recover the data collected by the N sensor nodes. Alternatively, the data sink forwards on the aggregate data to a network, computing device or communication device where computation is performed to recover the data collected by the first and the second sensors. 
     In one embodiment, in order to overcome the problem of data sparsity being compromised by abnormal sensor readings, the data sink or a computing device decomposes the received aggregate data into a first vector and a second vector. The first vector contains normal readings of the respective sensor that are sparse in a first transform domain. The second vector contains abnormal readings of the respective sensor that are sparse in a time domain. 
     For example, the sensor data d may be decomposed by the data sink into two vectors d 0  and d s , or  d =d 0 +d s , where d 0  contains the normal readings which are sparse in a certain transform domain and d s  contains the deviated values of abnormal readings. Given that abnormal readings are typically sporadic, d s  is a sparse signal in the time domain. Suppose the normal readings are sparse in Ψ domain, then sensor data d can be expressed as d=Ψx 0 +Ix s , where I is the identical matrix and both x 0  and x s  are sparse. Thus, the sensor data is a composed of two signals that are sparse in different domains. Accordingly, the sensor data can be expressed as d=Ψ′x, where x=[x 0   T  x s   T ] T  and Ψ′=[Ψ I]. It can be shown that stable recovery is possible under a combination of sufficient sparsity and favorable structure of the overcomplete system. 
     In one embodiment, when performing computation on the aggregate data, the coefficients used in the received aggregate data are reproduced. For example, the data collection device  202  may reproduce the M×N coefficients if the computation is performed by the data collection device  202  in order to recover sensor readings from N sensors. As the sensor readings are spatially correlated, the computation performed includes a discrete cosine transform computation using a spatial correlation between the first sensor and the second sensor to recover the data collected by the first sensor and the data collected by the second sensor. 
     In one embodiment, the data collection device  202  transmits the random seed to the sensor nodes before each of the sensor nodes starts transmitting data collected by the respective sensor. This way, each sensor node can generate its respective coefficient using the random seed. In one embodiment, at least one of the sensor nodes generates its respective pseudo-random coefficient using the random seed and the sensor node&#39;s identification, such as a serial number, a media access control (MAC) address, or any information that can be used to identify the respective sensor node. In one embodiment, data transmitted by each of the sensor nodes includes the identification of the respective sensor node, so the data collection device  202  can reproduce the coefficients with the random seed and the received identifications of the sensor nodes. 
     In one embodiment, the data collection device  202  further receives second aggregate data from a sensor node of a group of T sensor nodes. The second aggregate data is a result of each of the T sensor nodes generating Q pseudo-random coefficients with a random seed, multiplying its respective sensor reading with the Q coefficients to produce Q respective products. If a sensor node has not child node, it transmits its respective Q respective products to its parent node. On the other hand, if a sensor node is a parent node of at least one other sensor node, the parent node adds the respective Q products received from the child node to the respective Q products of the parent node to arrive at a set of Q values and then transmits those Q values to its parent node. Accordingly, Q different weighted sums of T products, constituting the aggregate data, will be transmitted by the last sensor node of a sub-tree of T sensor nodes to the data sink. In order for the sensor readings to be recoverable, Q needs to be smaller than T but larger than K, which is the degree of sparsity of the sensor readings. 
       FIG. 14  illustrates a process  1400  of data gathering in a large-scale wireless sensor network according to another embodiment. 
     At  1402 , first data from a first sensor node is received, where the first data includes a product of a first coefficient and a sensor reading of a first sensor. At  1404 , second data is generated to include a product of a second coefficient and a sensor reading of a second sensor. At  1406 , the first data and the second data are summed together to produce aggregate data. At  1408 , the aggregate data is transmitted. For example, a second sensor node is the parent node of the first sensor node. The second sensor node receives the first data from the first sensor node and combines the first data with the second data that is generated by the second sensor node to provide the aggregate data. The second sensor node then transmits the aggregate data for it to eventually be received by a data sink for further processing. 
     In one embodiment, in order to recover the sensor readings from the sensor nodes, the aggregate data is treated as having two vectors. The first vector contains normal readings of the sensors that are sparse in a first transform domain. The second vector contains abnormal readings of the sensors that are sparse in a time domain. 
     For example, the respective sensor data d may be treated by the data collection device  202  as consisting of two vectors d 0  and d s , or  d =d 0 +d s , where d 0  contains the normal readings which are sparse in a certain transform domain and d s  contains the deviated values of abnormal readings. Given that abnormal readings are typically sporadic, d s  is a sparse signal in the time domain. Suppose the normal readings are sparse in Ψ domain, then sensor data d can be expressed as d=Ψx 0 +Ix s , where I is the identical matrix and both x 0  and x s  are sparse. Thus, the sensor data is a composed of two signals that are sparse in different domains. Accordingly, the sensor data can be expressed as d=Ψ′x, where x=[x 0   T  x s   T ] T  and Ψ′=[Ψ I]. 
     In one embodiment, the first coefficient is generated by the first sensor node using the random seed and an identification of the first sensor node. Likewise, the second coefficient is generated by the second sensor node using the random seed and an identification of the first sensor node. 
     In one embodiment, at least one of the first sensor node or the second sensor node includes a plurality of sensors, at least one sensor of the plurality of sensors being of a first type, at least one other sensor of the plurality of sensors being of a second type different from the first type. For example, the first sensor node may include a sensor that senses temperature and another sensor that senses pressure. Further, the second sensor may include a sensor that senses motion, which is different from the conditions or parameters sensed by the sensors of the first sensor node. 
     In one embodiment, a random seed is received from the data sink before the sensor nodes transmit data. This way, each of the sensor nodes can compute one or more coefficients using the random seed and the identification of the respective sensor node. 
     In one embodiment, the second sensor receives third data from a third sensor node. The third data includes a product of a third coefficient and data collected by a third sensor, where the third coefficient is generated by the third sensor node using a random seed, such as a random seed provided by the data sink. For example, the second sensor node may also be the parent node of the third sensor node. Accordingly, the aggregate data transmitted by the second sensor node includes not only the first data from the first sensor node and the second data from the second sensor node, but also the third data from the third sensor node. 
     In one embodiment, a fourth sensor node is selected to be a parent node by the second sensor node between the fourth sensor node and a fifth sensor node. Subsequently, the second sensor node transmits a subscribe notification to the fourth sensor node before transmitting the second data from the second sensor to the fourth sensor node. This way, both the second sensor node and the fourth sensor node are aware of their respective relationship to each other in the wireless sensor network. 
     In another embodiment, to change the parent node, the second sensor node transmits an unsubscribe notification to a fourth sensor node. Subsequently, the second sensor node transmits a subscribe notification to a fifth sensor node before transmitting the second data from the second sensor node to the fifth sensor node. Accordingly, the fifth sensor node becomes the new parent node of the second sensor node. 
     CONCLUSION 
     The above-described techniques pertain to data gathering in large-scale wireless sensor networks. Although the techniques have been described in language specific to structural features and/or methodological acts, it is to be understood that the appended claims are not necessarily limited to the specific features or acts described. Rather, the specific features and acts are disclosed as exemplary forms of implementing such techniques. Furthermore, although the techniques have been described in the context of data gathering in large-scale wireless sensor networks, the techniques may be applied in any other suitable context such as, for example, electrical power grid sensor networks.