Abstract:
Systems and methods for telescopic data compression in sensor networks are disclosed herein. An exemplary method of the disclosed subject matter for telescopically compressing data received from a plurality of sensors in a network adapted to detect a field includes broadcasting a first set of sampling positions to sensors, forming a first set of clusters of sensors based on the sampling positions, receiving data from the sensors contained within the clusters, performing local interpolation of the received data, reconstructing a representation of the field using the interpolated data, and determining areas of interest based on the reconstructed representation of the field.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of International Application No. PCT/US2008/063302 entitled “Systems And Methods For Telescopic Data Compression In Sensor Networks”, filed May 9, 2008, which claims priority to U.S. Provisional Application No. 60/917,466 entitled “Telescopic Data Compression for Dense Sensor Networks”, filed on May 11, 2007 and U.S. Provisional Application No. 60/941,201 entitled “Telescopic Data Compression for Dense Sensor Networks”, filed on May 31, 2007, which are incorporated by reference in their entirety herein. 
     
    
     STATEMENT REGARDING FEDERALLY-SPONSORED RESEARCH 
       [0002]    This invention was made with government support under CNS-0435168 awarded by the National Science Foundation. The government has certain rights in the invention. 
       BACKGROUND 
       [0003]    1. Field 
         [0004]    The present application relates to systems and methods for telescopic data compression in sensor networks. 
         [0005]    2. Background Art 
         [0006]    The primary goal of sensor networks is to collect data of a physical phenomenon over a region. Sensor networks come in a wide variety, covering different geographical areas, using devices with different energy constraints, and implementing an assortment of applications. Some such networks have a large number of energy constrained sensors randomly distributed over a large area. The sensors forward data to nearby sensors until it reaches a sink, which is a collection point connected to the data processing center through a wired network. Such a network may be useful for measuring many different kinds of physical phenomena. 
         [0007]    The field of most physical phenomena can be described by a smooth continuous signal. Even though spikes may occasionally occur, they are mostly confined to sporadic patches in a greater region of a smooth profile. This can be readily illustrated by simple examples, like the temperature distribution over a heated surface, the intensity of seismic vibrations decreasing gradually away from the epicenter, and in the case of a chemical leakage, the chemical concentration thinning out as the distance from the leak increases. 
         [0008]    Many sensor network applications are characterized by an uneven distribution of information content, with useful information concentrated in isolated target regions. In such cases, data collection can be improved if target regions can be identified by sampling sparsely at a low energy cost, and then raising the sampling density progressively only in those regions of interests until the desired resolution is reached. There are several major technical challenges that inhibit the direct application of existing sampling-theoretic techniques to the compression of data in sensor networks, including: (i) random placement of sensors, (ii) noise in sensor measurements, (iii) limitations in the computational capacity of individual sensors, making complicated non-uniform sampling techniques unpractical, and (iv) the need that compression be done in a distributed manner. Thus there is a need for technique which overcomes these challenges. 
       SUMMARY 
       [0009]    Systems and methods for telescopic data compression in sensor networks are disclosed herein. 
         [0010]    An exemplary method of the disclosed subject matter for telescopically compressing data received from a plurality of sensors in a network adapted to detect a field includes broadcasting a first set of sampling positions to sensors, forming a first set of clusters of sensors based on the sampling positions, receiving data from the sensors contained within the clusters, performing local interpolation of the received data, reconstructing a representation of the field using the interpolated data, and determining areas of interest based on the reconstructed representation of the field. 
         [0011]    In some embodiments, a method for telescopically compressing data received from a plurality of sensors in a network adapted to detect a field further includes broadcasting a second set of new sampling positions to sensors within the areas of interest, forming a second set of clusters based on the second set of new sampling positions, and utilizing the second set of clusters to re-receive data from the sensors, repeat local interpolation of the re-received data, repeat reconstruction of the representation of the field using the interpolated data, and re-determine the areas of interest. 
         [0012]    In some embodiments, forming clusters of sensors includes designating sensors as cluster heads. In some embodiments, forming clusters of sensors includes selecting sensors within a fixed range from the sampling positions. Forming clusters of sensors can further include limiting the number of sensors selected by use of a probability algorithm, or selecting a predetermined number of sensors that are closest to the sampling positions, or both. 
         [0013]    In some embodiments, performing local interpolation includes forwarding data of the sensors contained within the clusters to cluster heads, and using the cluster heads to estimate the value of the field at the sampling positions. The cluster heads can be used to apply a digital low-pass filter algorithm to the data. 
         [0014]    In some embodiments, estimating the value of the representation of the field and applying the digital low-pass filter algorithm are performed utilizing the same scattered data interpolation algorithm. In some embodiments, the scattered data interpolation algorithm is a Gaussian-weighted averaging algorithm. In some embodiments, the local interpolation is performed simultaneously for all of the clusters. In some embodiments, reconstructing the representation of the field includes transmitting the local interpolated data to sensors closest to a wireless access point, transmitting the local interpolated data from that wireless access point to a processing center, and processing the local interpolated data to reconstruct the representation of the field. In some embodiments, transmitting the local interpolated data to sensors closest to a wireless access point is performed utilizing a shortest path algorithm. 
         [0015]    An exemplary system of the disclosed subject matter for telescopically compressing data received from a plurality of sensors in a network adapted to detect a field includes a processor, a wireless connection device operatively coupled to the processor, sensors operatively connected to the wireless connection device, and a memory operatively coupled to the processor. The memory stores program instructions that when executed by the processor, cause the processor to utilize the wireless connection device to broadcast a first set of sampling positions to the sensors, form a first set of clusters of sensors based on the sampling positions, receive data from the sensors contained within the clusters, perform local interpolation of the received data, reconstruct a representation of the field using the interpolated data, and determine areas of interest based on the reconstructed representation of the field. 
         [0016]    In some embodiments, the execution by the processor of the memory storing program instructions causes the processor to utilize the wireless connection device to further broadcast a second set of new sampling positions to sensors within the areas of interest, form a second set of clusters based on the second set of new sampling positions, re-receive data from the sensors, and utilize the second set of clusters to re-receive data from the sensors, repeat local interpolation of the re-received data, repeat reconstruction of the representation of the field using the interpolated data, and re-determine the areas of interest. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0017]    The accompanying drawings, which are incorporated and constitute part of this disclosure, illustrate some embodiments of the disclosed subject matter. 
           [0018]      FIG. 1  illustrates a chart of a method in accordance with an embodiment of the disclosed subject matter. 
           [0019]      FIG. 2  is a diagram of a sensor network in accordance with an embodiment of the disclosed subject matter. 
           [0020]      FIG. 3  is a diagram of an interpolation cluster in accordance with an embodiment of the disclosed subject matter. 
           [0021]      FIG. 4  is a diagram of a shortest path tree for a sensor network in accordance with an embodiment of the disclosed subject matter. 
           [0022]      FIG. 5  is a diagram of a representation of a field after application of a global signal reconstruction in accordance with an embodiment of the disclosed subject matter. 
           [0023]      FIG. 6  is a diagram of a sampling position gird after telescoping in accordance with an embodiment of the disclosed subject matter. 
           [0024]      FIGS. 7(   a )-( b ) are a contour plot and a corresponding three dimensional graph, respectively, of the temperature distribution for a fire detection application in accordance with an embodiment of the disclosed subject matter. 
           [0025]      FIGS. 8(   a )-( b ) are a contour plot and a corresponding three dimensional graph, respectively, of the temperature distribution for a fire detection application after one iteration in accordance with an embodiment of the disclosed subject matter. 
           [0026]      FIGS. 9(   a )-( b ) are a contour plot and a corresponding three dimensional graph, respectively, of the temperature distribution for a fire detection application after two iterations in accordance with an embodiment of the disclosed subject matter. 
           [0027]      FIGS. 10(   a )-( b ) are a contour plot and a corresponding three dimensional graph, respectively, of the temperature distribution for a fire detection application after three iterations in accordance with an embodiment of the disclosed subject matter. 
           [0028]      FIGS. 11(   a )-( b ) are a contour plot and a corresponding three dimensional graph, respectively, of the temperature distribution from a commercially available fire simulation application in accordance with an embodiment of the disclosed subject matter. 
           [0029]      FIG. 12  is a schematic of a system in accordance with an embodiment of the disclosed subject matter. 
       
    
    
     DETAILED DESCRIPTION 
       [0030]    The emergence of dense sensor networks in recent years has created a brand new paradigm for distributed sensing. Small-size, low-cost sensors of poor precision are distributed randomly in bulk to carry out a sensing task. Though individual sensor readings are inaccurate, aggregating multiple readings in a neighborhood can improve the accuracy. The disclosed subject matter utilizes this advantage of regional cooperative processing to generate virtual samples, which are sent to the destination for global signal reconstruction. An application can then gradually zoom in on certain target regions by instructing the network to raise the sampling resolution in those regions in successive rounds of data collection. 
         [0031]    An exemplary data compression framework includes two levels of operation. The first level is to obtain a set of virtual samples {f({right arrow over (x)} v )} at regular sampling positions {{right arrow over (x)} v }. Each virtual sample f({right arrow over (x)} v ) is computed by locally interpolating the cluster of sensor measurements around {right arrow over (x)} v . Within each cluster, one sensor is chosen as the cluster head which collects sensor readings and performs interpolation. In this way, the many sensor readings in a cluster are compressed to one sample value. At the second level, the processing center collects the virtual samples {f({right arrow over (x)} v )} from all the cluster heads and then reconstructs a representation of the physical field by applying a smoothing filter on the samples. The accuracy of the reconstructed signal largely depends on the regular sampling density and the cluster size. 
         [0032]      FIG. 1  illustrates an exemplary method  100  according to the disclosed subject matter. To initiate the formation of interpolation clusters  110 , the set of sampling positions {{right arrow over (x)} v } are broadcast  112  to the sensors by a base station. The density of the sampling positions can determine the signal bandwidth to be captured by the network: e.g., a higher density can mean a wider detection bandwidth and a smaller overall compression ratio. Sensors can then be formed  114  into clusters around each of the sampling positions {right arrow over (x)} v  based on clustering rules, for example, by grouping all sensors within a range R from {right arrow over (x)} v . One sensor from each cluster can then be selected  116  as the cluster head. 
         [0033]    A good clustering rule should result in clusters having the right size, striking a balance between interpolation accuracy and computational efforts. A large cluster size is on one hand good for accuracy, but on the other hand stressful for computation. In addition, clusters should be formed with data points spread as evenly as possible for a better interpolation quality. 
         [0034]    A simple rule that all sensors within a fixed range R from the position of a virtual sample {right arrow over (x)} v  are grouped into the same cluster can also be used, where R is a measure of distance. Alternatively, a rule that chooses the N sensors closest to the position of a virtual sample {right arrow over (x)} V  can be used, where N is a whole number. Utilizing a fixed range method, a sensor can decide its cluster affiliation by checking only its own distance to {right arrow over (x)} v  without knowing the locations of others. The value of R can be chosen such that only data points significantly correlated to the value at {right arrow over (x)} v  are included. For interpolation based on low-pass filtering, R can be made dependent on the filter bandwidth. 
         [0035]      FIG. 2  shows an exemplary layout of sensors at random positions in relation to sampling positions {right arrow over (x)} v .  FIG. 2  further shows the distance between sampling positions is T s  and the R is the radius of each cluster.  FIG. 2  illustrates an exemplary embodiment where sampling positions {right arrow over (x)} v  are regularly spaced. 
         [0036]    In an exemplary embodiment, T s  is equal to 7.2 meters and R is equal to 3.6 meters. In an exemplary embodiment utilizing a Gaussian algorithm, σ (the standard deviation) can equal at least 0.38T s  to avoid aliasing, as described in detail below. By choosing R=0.5T s  (in other words half the distance between sampling positions {right arrow over (x)} v ), which is the maximum range for non-overlapping clusters, data of weightings smaller than 0.42 are excluded. If that value of R results in too large a cluster size, measured by 
         [0000]      N=πR 2 ρ sensor   (1) 
         [0000]    for a circular cluster, where ρ sensor  is the sensor density, random suppression of sensors can be enforced by applying a probability algorithm, e.g., a turn-off probability algorithm such as 
         [0000]        P   b (Suppression)=1− N   interp   /πR   2 ρ sensor   (2) 
         [0000]    where N interp  is the desired number of sensors involved in the interpolation. 
         [0037]    Returning to  FIG. 1 , local interpolation  120  can be performed by sensors in a cluster forwarding  122  their measurements to the cluster head, which can estimate  124  the virtual sample f({right arrow over (x)} v ), i.e., the estimated value of the field at the center {right arrow over (x)} v  of the cluster, using a scattered data interpolation algorithm. 
         [0038]    A digital low-pass filter algorithm can be applied  126  to reduce the white noise from the sensor readings and further to prevent aliasing during global signal reconstruction. In one embodiment, sensors can utilize a shortest path algorithm, e.g., Dijkstra&#39;s Algorithm, to determine the route to forward  122  data to the cluster head. Sensors which are not located in any cluster can be rendered non-transmitting. 
         [0039]      FIG. 3  illustrates an exemplary interpolation cluster with a sampling position {right arrow over (x)} v  located at the center of the cluster.  FIG. 3  further illustrates the sensors making use of a shortest path algorithm to forward their respective data to the cluster head. 
         [0040]    A wide variety of scattered data interpolation algorithms are suitable for use in the estimation 124 of virtual samples f({right arrow over (x)} v ). The choice of interpolation model depends largely on factors, like the type of data, the required accuracy, the distribution of data points, the quality of measurements, and the affordable amount of computation. An example of a simple algorithm is the nearest neighbor method, which estimates a point simply by its closest sample. Distance-weighting methods, based on the principle of assigning more weights to sample points closer to the target, can also be utilized and can be fairly simple and yet yield reasonably good results in most cases. Examples of weighting functions include averaging, inverse distance (w=d −k ) and Gaussian (w=e −d     2     /2σ     2   ) weightings. 
         [0041]    In an exemplary embodiment, the estimate  124  of the virtual sample f({right arrow over (x)} v ) and the application  126  of a digital low-pass filter may be performed utilizing the same scattered data interpolation algorithm. In the same or another embodiment, a Gaussian-weighted averaging algorithm can be utilized, with weighting function 
         [0000]        w=e   −d     2     /2σ     2     (3) 
         [0000]    where d is the distance between a sensor and the point being interpolated and σ is the standard deviation. The spatial variance of this digital low-pass filter can be related to its 3 dB (decibel) bandwidth by the expression σ 2 =ln 2/(2π 2 B 3dB   2 ) or σ=0.19/B 3dB . As referenced above, where the regular interval of the sampling positions {right arrow over (x)} v  is T s , the filter bandwidth can then be set to be smaller than ½T s , and resulting in a σ value of 0.38T s . In the same or another embodiment, every cluster may perform the estimate  124  and the application  126  of a digital low-pass filter utilizing the same scattered data interpolation algorithm simultaneously. 
         [0042]    Referring again to  FIG. 1 , global signal reconstruction  130  can be performed by each cluster head transmitting  132  its estimated virtual sample f({right arrow over (x)} v ) to the closest sink, which transmits  134  the virtual sample data to a wireless access point, which in turn transmits  136  the data to a processing center where a signal reconstruction algorithm can be utilized  138  to reconstruct the signal (i.e., the physical field). In one embodiment, the virtual sample data can be routed directly to the sink utilizing a shortest path tree, i.e., the path determined utilizing a shortest path algorithm, e.g., Dijkstra&#39;s Algorithm. 
         [0043]    In an exemplary embodiment, the field reconstruction is done at the processing center by applying a low-pass filter. In one exemplary embodiment, the processing center can apply a box-like low-pass filter, denoted by the equation 
         [0000]        H ( u,v )= T   s   2 rect( uT   s )rect( vT   s )  (4) 
         [0000]    where u and  v  are the dimensions in the frequency domain, T s  is the distance between sampling intervals, and rect( ) is the rectangular function. The corresponding filter function in the spatial domain can be described by the equation 
         [0000]        h ( x,y )=sinc( x/T   s )sinc( y/T   s )  (5) 
         [0000]    where x and y are coordinates of the sampling positions and sinc( ) is the sinc function. The original signal, i.e., the representation of the detected field, can be reconstructed using the equation 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       f 
                       ^ 
                     
                      
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       i 
                     
                      
                     
                       ( 
                       
                         
                           z 
                           i 
                         
                          
                         sin 
                          
                         
                             
                         
                          
                         
                           c 
                            
                           
                             ( 
                             
                               
                                 ( 
                                 
                                   x 
                                   - 
                                   
                                     x 
                                     i 
                                   
                                 
                                 ) 
                               
                               / 
                               
                                 T 
                                 s 
                               
                             
                             ) 
                           
                         
                          
                         sin 
                          
                         
                             
                         
                          
                         
                           c 
                            
                           
                             ( 
                             
                               
                                 ( 
                                 
                                   y 
                                   - 
                                   
                                     y 
                                     i 
                                   
                                 
                                 ) 
                               
                               / 
                               
                                 T 
                                 s 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where s i =(x i , y i , z i ) are sample points: x i  and y i  are the coordinates of the sampling position and z, is the value of the field at position (x i , y i ). 
         [0044]      FIG. 4  illustrates an exemplary shortest path tree for the sensor network depicted in  FIG. 2 . As illustrated in  FIG. 4 , the various cluster heads can forward their data packet(s) along the shortest path to a sink point. In one embodiment, the sink can be the nearest sensor to a wireless access point. 
         [0045]      FIG. 5  illustrates a perspective graph according to an exemplary global signal reconstruction of the sensor network depicted in  FIG. 2 .  FIG. 5  further illustrates an area of interest  510  enclosing the highest virtual sample value. An area of interest  510  may be selected according to various criteria, including areas with virtual sample values above and/or below a certain threshold value. 
         [0046]    Referring again to  FIG. 1 , in an exemplary embodiment, telescoping  140  can be performed by determining  142  an area of interest (such as area  510  in  FIG. 5 ), then re-broadcasting  112  a new set of sampling positions {{right arrow over (x)} u }. In one embodiment, the new sampling positions {right arrow over (x)} u  can be more closely spaced in and around areas of interest (such as area  510  in  FIG. 5 ). The telescoping  140  can be further performed by re-forming  114  clusters around each of the new sampling positions {right arrow over (x)} u  based on the same or different clustering rules, as detailed above. The telescoping  140  can be further performed by repeating the local interpolation  120  and the global signal reconstruction  130 , one or more times. The telescoping  140  process, including the repetition of position broadcasting, cluster forming, local interpolation, and global signal reconstruction, can be repeated until a desired resolution of the physical field is obtained. 
         [0047]    In an exemplary embodiment, the initial uniform sampling density is high enough to extract the frequency spectrum of the target physical field. After the first round of data collection, an overall signal profile can be reconstructed (e.g., as illustrated in  FIG. 5 ), so that an application can identify areas of interest and increase the uniform sampling density in those regions.  FIG. 6  illustrates an example of increasing sampling density around an area of interest  510 , such as that depicted in  FIG. 5 , according to the telescoping method. 
         [0048]      FIGS. 7(   a ) through  10 ( b ) illustrate the use of an exemplary method in accordance with the disclosed subject matter for a fire detection application. In the sensing of a fire, a sensor network can first obtain a rough temperature distribution.  FIG. 7(   a ) illustrates a contour plot of that rough temperature distribution.  FIG. 7(   b ) illustrates the corresponding three dimensional graph of the same temperature distribution, emphasizing the relatively high signal to noise ratio (SNR), e.g., 6 dB for this example. 
         [0049]      FIGS. 8(   a ) and  8 ( b ) illustrate the reconstructed physical field after one iteration of an exemplary method in accordance with the disclosed subject matter. The application can then request a higher uniform sampling density in the potential areas of interest, so as to obtain finer details for the estimation of fire size and its spread rate. The refinement process is repeated for several rounds until the desired level of details is reached. 
         [0050]      FIGS. 9(   a ) and  9 ( b ) illustrate the model after a second iteration and  FIGS. 10(   a ) and  10 ( b ) show the model after a third iteration. The zoom-in strategy is a choice of the application, e.g., an area of interest could simply be defined as any region of temperature above a threshold. Sampling densities in different regions can be controlled by broadcasting instructions from the processing center via wireless access points.  FIGS. 11(   a ) and  11 ( b ) illustrate the actual physical field as produced using the National Institute of Standards and Technology (NIST) Fire Dynamics Simulator. 
         [0051]      FIG. 12  is an exemplary embodiment of a system  1200 , with a computing device  1210 . The device includes at least a processor  1212  operatively connected to a memory  1214 . The computing device  1210  is operatively connected to a wireless connection device  1216 , that can be running a wireless standard, e.g., a name-brand wireless access point running the 802.11 standard connected to the computing device  1210  by means of a wired connection. The device  1216  is operatively connected to a network of sensors  1218 , e.g., by means of a wireless connection. The computing device  1210 , can be a standard personal computer or a laptop. The network of sensors  1218  can be any sensors capable of running a wireless standard, e.g., the 802.11 standard. Software running on computing device  1210  can be used to coordinate the operation of the wireless connection device  1216  and sensors  1218 , e.g., commercially available software for controlling devices running the 802.11 standard. The same or a different software running on computing device  1210  can be used to perform the reconstruction of the field. In an exemplary embodiment, the software can be a custom designed program. 
         [0052]    It will be understood that the foregoing is only illustrative of the principles described herein, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the disclosed subject matter. For example, the system and methods described herein are used for telescopic data compression in sensor networks. It is understood that that techniques described herein are useful in connection with telescopic data compression of any network. Moreover, features of embodiments described herein may be combined and/or rearranged to create new embodiments.