Abstract:
Arrangements and methods for developing a software toolkit that can be used to design or obtain parameters for a sensor network. High-level guidelines on the basic relations between sensor network parameters like number of sensors, degree of quantization at each sensor, and the distortion requirements, based on a deep analysis on two basic coding possibilities (multiplexed point-to-point, distributed) are contemplated. By evaluating tradeoffs among the various parameters, an optimization framework to obtain the most cost-effective design with required quantization capabilities pertaining to given distortion criterion is provided.

Description:
CROSS-REFERENCE TO RELATED U.S. APPLICATION 
     This application claims priority from U.S. Provisional Patent Application Ser. No. 60/786,663, filed on Mar. 28, 2006, and which is fully incorporated by reference herein. 
    
    
     FIELD OF THE INVENTION 
     The present invention generally relates to the field of intelligent networks formed by sensors that can monitor physical phenomena over a large field. In particular, the invention relates to the design of a large scale sensor network that integrates data compression and network communication. 
     BACKGROUND OF THE INVENTION 
     Recent advances in wireless communications and micro-electro mechanical systems have enabled the development of small, low-cost sensors that possess sensing, signal processing and wireless communication capabilities. These sensors can be dispersed geometrically in large scale and be organized into networks that can monitor physical phenomena over a large field. Such distributed sensor networks can be applied to a wide range of potential applications, like large-scale reconnaissance, surveillance, environmental monitoring, anomaly detection and disaster recovery, etc. 
     Distributed sensing is faced with many challenges pertaining to the scarcity of power, bandwidth, and computing resources. A central problem is to find the most efficient way to deploy the sensors and use them to collect information and send data to the central data collector. Some natural questions include: how many sensors should be deployed; what degree of quantization power should each sensor possess; at what rate should data be sampled and how should they be encoded/decoded and be sent to the central collector in order to meet some distortion criteria; is the communication network formed by the sensing nodes capable of transferring the generated data rate; and more generally, is the proposed sensor network feasible. Effective design of distributed sensor networks requires fundamental understanding of the tradeoffs between sensor network parameters like number of sensors, degree of quantization at each sensor, and the distortion requirements, etc. 
     A standard technique for sending information from the sensors to a data fusion center would be to simply treat each sensor&#39;s observation as an independent measurement and then employ well understood techniques for its transmission, including standard quantization and channel coding. Independently of the type of channel coding performed, the standard quantization referred to in here can also be referred to as a very basic “point-to-point” coding scheme. While appropriate for some applications, this scheme becomes infeasible when the there are too many sensors sharing a resource-limited data transmission environment, such as the available wireless spectrum. 
     Consequently, limiting the sizes of the messages emitted by the stations without losing the quality of the sampled data is of significant interest. These stations are assumed to operate in isolation, this is, where no cooperation is allowed. A fundamental observation is that the efficiency of such networks cannot be better than a hypothetical network where such collaboration is allowed. In particular, in principle one would like to design sensor networks with performance close to a network with full collaboration; one may call the latter “joint coding” (alternatively referred to herein as “centralized coding”). 
     The class of techniques that attempt to capitalize on the correlations of the data to improve system performance are called “distributed coding”. Distributed coding has been the subject of many theoretical investigations in the past, for example, for a small number of sensors [T. Berger, “Multiterminal Source Coding,” Information Theory Approach to Communication, (CISM Courses and Lecture Notes No. 229), G. Longo, Ed., Wien and New York: Springer-Verlag, 1977]. More recent theoretical research addresses problems and characteristics of large sensor networks (D. Marco and E. J. Duarte-Melo and M. Liu and D. L. Neuhoff. On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data, Lecture notes in Computer Science, editor, L. J. Guibas and F. Zhao, Springer, 2003, 1-16. and P. Ishwar and A. Kumar and K. Ramchandran, On Distributed Sampling in Dense Sensor Networks: a “Bit-Conversation” Principle, IEEE Journal on Selected Areas in Communication, July, 2003). Practical research has lagged theoretical developments. The implementation of efficient distributed coding algorithms as conceived in most research relies on recent years&#39; algorithmic breakthroughs [Slepian, D., Wolf, J K: Noiseless Coding of Correlated Information Sources. IEEE Trans. Information Theory, IT-19, 1973, pp. 471-480.]. Most practical research follows the model established by the theoretical investigations, with significant results available only for two sensors [Z. Xiong, A. Liveris, and S. Cheng, “Distributed source coding for sensor networks”, IEEE Signal Processing Magazine, vol. 21, pp. 80-94, September 2004]. However, distributed coding schemes continue to present significant practical roadblocks as they are further developed. 
     In some situations, it is desirable to design sensor networks with many inexpensive sensors instead of fewer more expensive ones. A central question then is whether it is feasible to design very dense sensor networks in which the sum of the total amount of information broadcasted by each sensor does not grow in an unbounded manner as we add more sensors to the environment (this is, as we make the network denser). 
     Recent work by Kashyap et. al. have demonstrated that it is possible to use distributed coding as well as a simple multiplexed point-to-point coding technique to attain this goal. 
     Accordingly, in view of the foregoing, while research continues to advance different coding techniques, a need continues to be recognized in connection with providing and implementing more practical and effective techniques. 
     SUMMARY OF THE INVENTION 
     In view of the foregoing problems, drawbacks, and disadvantages of the conventional approaches, it is an exemplary feature of the present invention to employ deep understanding on the basic relations between various sensor network parameters to automate the process of design and optimization of sensor networks and related applications. 
     Generally, two approaches are broadly contemplated herein. In a first general approach, a distributed coding scheme may be employed to take advantage of distributed coding characteristics in the context of a large-scale sensor network. In a second general approach, a simple (“multiplexed point to point”) coding scheme can preferably be implemented using scalar quantization at the sensors, and this represents a vast improvement over traditional, “basic” point-to-point coding schemes. In both cases, bandwidth can be kept within a fixed maximum regardless of the number of sensors and/or density of the sensor network in question. 
     Generally, the present invention provides means to develop a software toolkit that can be used to design (obtain parameters for) a sensor network. A method according to the present invention requires as input the geographical location of the sensors, the field statistics, the desired field reconstruction error, and the cost of sensor with different capabilities. Taking the above measurement data as input, a method of present invention uses advanced optimization techniques to obtain the basic parameters for the sensor networks such as the minimum number of sensors required to achieve the desired reconstruction error, and suggests the efficient coding scheme accordingly. 
     To elaborate further, in a preferred embodiment of the present invention, high-level guidelines are provided on the basic relations between sensor network parameters like number of sensors, degree of quantization at each sensor, and the distortion requirements, based on a deep analysis of several basic coding possibilities (basic point-to-point; joint [or centralized], distributed coding and multiplexed point-to-point). 
     In summary, one aspect of the invention provides a method of managing a sensor network, said method comprising the steps of: obtaining input related to sensor network characteristics; optimizing a cost function on the basis of obtained input; based on the cost function, choosing a number of sensors from which to obtain data; partitioning the sensors into groups; accepting sensor measurement data at a predetermined location; and constructing a field data sample at the predetermined location. 
     Another aspect of the invention provides an apparatus for managing a sensor network, said apparatus comprising: an arrangement for obtaining input related to sensor network characteristics; an arrangement for optimizing a cost function on the basis of obtained input; a choosing arrangement which, based on the cost function, chooses a number of sensors from which to obtain data; a partitioning arrangement which partitions the sensors into groups; an accepting arrangement which accepts sensor measurements; and a constructing arrangement which constructs a field data sample. 
     Furthermore, an additional aspect of the invention provides a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a sensor network, said method comprising the steps of: obtaining input related to sensor network characteristics; optimizing a cost function on the basis of obtained input; based on the cost function, choosing a number of sensors from which to obtain data; partitioning the sensors into groups; accepting sensor measurement data at a predetermined location; and constructing a field data sample at the predetermined location. 
     For a better understanding of the present invention, together with other and further features and advantages thereof, reference is made to the following description, taken in conjunction with the accompanying drawings, and the scope of the invention will be pointed out in the appended claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a sensing field with sensors. 
         FIG. 2  sets forth an algorithm for establishing a minimum number of sensors. 
         FIGS. 3A and 3B  provide a flowchart for a preferred multiplexed point-to-point coding scheme in accordance with at least one embodiment of the present invention. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Very generally, as mentioned above, two approaches are broadly contemplated herein. In a first general approach, a distributed coding scheme may be employed to take advantage of distributed coding characteristics in the context of a large-scale sensor network. Essentially, if it is assumed that a correlation structure is known at each sensor in a network, it is possible to achieve a sum rate that is within a maximum independent of the number of sensors. In a second general approach, a simple (multiplexed point to point) coding scheme can preferably be implemented using scalar quantization at the sensors. In that sense, sensors would not need to have any information about a correlation structure, and would make use of an assumption that the sensors are synchronized. In this way, a sum rate can also be achieved that is within a maximum constant independent of the number of sensors. In both cases, it will be appreciated that bandwidth requirements remain bounded by a constant regardless of the number of sensors and/or density of the sensor network. 
     The disclosure first turns to a general discussion of sensor networks and their components as may be employed in accordance with at least one presently preferred embodiment of the present invention. Thence, some discussion is provided regarding conceivable, and preferred, distributed coding and multiplexed point to point coding schemes that may be utilized. Further background details that may be of assistance in appreciating ancillary or environmental aspects relating to the employment of at least one embodiment of the present invention may be found in the paper attached hereto as an Appendix, “Distributed source coding in dense sensor networks”, by A. Kashyap et al. 
     Generally, there are broadly contemplated herein, in accordance with at least one preferred embodiment of the present invention, methods and apparatus for a cost effective design of large scale sensor networks. Such sensor networks combine micro-sensor technology, signal processing, low power computation, low cost and low power wireless communication into an integrated system, and provide monitoring and control capabilities in many applications including large-scale reconnaissance, surveillance, anomaly detection and disaster recovery, etc. 
     One idea contemplated herein is based on the observation that data in a real sensing field becomes increasingly correlated as the distance between sensing locations decreases. Consequently, there is broadly contemplated herein a distributed source-coding scheme, which is shown to have the promise of very significant improvements in bandwidth requirements. However, in such a distributed scheme, practical challenges may also be present that will continue to require further study and experimentation. Though there likely exist commercially available sensors that could be equipped with enough memory and processing power can implement a distributed coding algorithm as broadly contemplated herein, challenges in developing and implementing software for managing distributed coding (as contemplated herein) of massive sensor networks are recognized as formidable. Accordingly, multiplexed point-to-point coding schemes, as broadly contemplated herein, present the advantage of being simple enough to be implemented in practical settings even with extremely resource-constrained sensors. 
     Turning to some basic concepts relating to sensor networks and their components and related parameters shall be discussed, as a matter of relevance to all conceivable coding schemes, reference may be made, as needed, to the Appendix (Kayshap, supra). Shown in  FIG. 1  is a sensing field G ( 100 ) with a plurality of sensors  102  distributed therethroughout, all commonly connected (via any suitable wired or wireless means) to a data collecting “hub”  104 . At hub  104 , measurements from the sensors  102  are taken in and calculated in a manner to effectively interpret the phenomena recorded by sensors  102 . Such a hub  104  is often referred to as a “fusion center” or “data fusion center”. 
     Generally, the following steps (as shown in  FIG. 2 ), may preferably be undertaken in accordance with at least one embodiment of the present invention:
         Obtain geographical locations of sensors from user input ( 202 ).   Obtain field statistics from field experiments ( 204 ).   Obtain total field error desired D net  from user input ( 206 ).   Choose or establish a minimum number of sensors N min  so as to make the sampling error sufficiently small ( 210 ).   For any coding technique, the total field reconstruction error can be upper bounded by the sum of a quantization error and a sampling error
 
 J   MSE   &lt;=E   Q   +E   S  
           Therefore, even with an infinite rate available (E Q =0), a minimum number of samples is required in order to give a total field error smaller than D net . For a better understanding of these variables, reference may be made to the Appendix (Kashyap, supra).   
           Obtain a maximum number of sensors N max  that the user can be expected to deploy ( 212 ).   For each compression algorithm “Alg” under consideration (e.g. point-to-point, distributed coding, multiplexed point-to-point), and for every N max &gt;=N&gt;=N mi , obtain each individual sensor&#39;s rate and quantization level of the sample required to meet the user distortion requirements D net . These parameters are called RATE(Alg,N) and DIST(Alg,N) ( 214 ).       

     We note that establishing the step of obtaining the maximum number of sensors N max  is preferably added for the purposes of limiting any computation that the last step above may entail. The present invention by no means places intrinsic limits on how large N max  is allowed to be since we show that our bandwidth requirements do not grow as the network becomes denser. 
     We associate with a sensor capable of signaling at rate RATE(Alg,N) and obtaining measurements with fidelity DIST(N) a cost using a cost function Cost(Alg,N, params). The cost reflects memory and processing power requirements to implement particular signal processing algorithms for the purposes of compression, signaling, etc. Other parameters “params” may be passed to the cost function say, to reflect the availability of different types of sensors and thus differing costs. 
     Preferably, a cost-effective coding technique will have been chosen to fulfill the following:
         minimize N Cost(N, params)   over all N such that Nmin&lt;=N&lt;=Nmax   and over all feasible params       

     We pause to comment on the fundamental insight that makes it feasible to design very dense networks without increasing the bandwidth requirements beyond a maximum independent of the density of the network. 
     As one deploys sensors closer to each other in a network, the sensor&#39;s measurements start to become more and more correlated. Correspondingly, it becomes feasible to have individual sensors take measurements with high distortion, which are then combined at a fusion center to improve each of the sensor&#39;s measurements. Moreover, these high distortion measurements may be further compressed via use of distributed coding techniques. The extent to which individual sensors can relax their distortion requirements is key to this invention; in the attached paper by Kashyap it is shown how such distortion can be increased as one increases the number of sensors while maintaining total field reconstruction distortion as well as total bandwidth requirements. 
     As also may be appreciated from the Appendix (Kayshap, supra), there are tradeoffs between various sensor network parameters like number of sensors, degree of quantization at each sensor, and the distortion requirements. 
     As discussed heretofore, there are essentially two coding schemes that may preferably be implemented in accordance with the embodiments of the present invention. One such scheme is multiplexed point to point coding, in which a coding scheme at the sensors does not make any use of correlation between samples for the goal of further compressing the measurements taken at the sensors. While at the other extreme is centralized (or joint) coding, which is an idealized case but not realistic (as it requires that an encoder having access to all the sample values be observed by all sensors), there is considered herewith, instead, a distributed coding scheme. As contemplated in accordance with at least one embodiment of the present invention, a distributed coding scheme makes use of a statistical correlation of the data so that the sensors can achieve better compression, while encoding their samples without any collaboration. 
     In the Appendix (Kashyap, supra), it is shown that for a given distortion requirement, the rate required by distributed coding stays no more than a constant away from the rate required by joint coding of all the samples as the number of sensors becomes large. More pertinently, as also discussed in the Appendix (Kashyap, supra), it has been proven (D. Slepian and J. Wolf, “Noiseless coding of correlated information sources,”  Transactions on Information Theory , vol. IT-19, pp. 471-480, July 1973) that the optimal sum rate of distributed source coding is the same as the optimal rate of joint coding: for noiseless coding of discrete sources there is no inherent loss in rate in distributed coding. A lossy distributed source coding (L-DSC) problem is, however, still unsolved. In general, it is possible that the minimum total rate required by the best lossy distributed coding is greater than the minimum total rate required by a joint encoding of the sources. Moreover, this rate loss might increase with the number of samples being coded. For example, the redundancy of a quantization scheme discussed in R. Zamir and T. Berger, “Multiterminal source coding with high resolution,” ( IEEE Transactions on Information Theory , vol. 45, pp. 106-117, January 1999) increases linearly with the number of samples. 
     Kashyap, supra (in the Appendix) does demonstrate the utility of distributed source coding as a way of reducing the sum rate. As the number of sensors increases, they are packed more densely, and the data of sensors located close together becomes increasingly correlated. Reducing this redundancy in data using the knowledge of the statistical correlation between sensor observations is therefore attractive. The increasing correlation between the data can be utilized in such a way that the rate-penalty of distributed coding does not grow unboundedly as the number of samples being coded grows. Further mathematical corroboration of this can be found in the paper. 
     Generally, it can be seen that for any given distortion requirement D net , the sum rate of distributed coding is no more than a constant away from the rate of joint coding. Therefore, as the number (and therefore the density) of samples increases, one can make do with increasingly coarsely quantized estimates of those samples at the fusion center (hub). 
     Inasmuch as a distributed coding scheme in theory has been demonstrated to provide significant advantages, practical implementation, as discussed heretofore, remains quite elusive. Accordingly, a simple, workable, multiplexed point to point coding scheme is broadly contemplated herein, in accordance with at least one embodiment of the present invention, by way of affording a practical implementation that itself presents significant advantages. Reference may continue to be made to the Appendix (Kashyap, supra) to appreciate detailed mathematical constructs of a preferred multiplexed point to point coding scheme, while  FIGS. 3A and 3B  provide a generalized flowchart (starting with  FIG. 3A  and continuing to  FIG. 3B ) for such a scheme. Generally, it can be shown that if sensors are synchronized and if a delay that increases linearly with the number of sensors is tolerable, then a desired tradeoff (of sensor numbers to sensor accuracy) can be achieved by a simple scheme in which encoding can be performed at sensors by using simple scalar or vector quantizers. 
     As shown in  FIG. 3A , a stationary field autocorrelation function is first preferably obtained or established ( 402 ), normalized so that each sample of the field has unit variance. Next, a desired reconstruction error D net  is preferably obtained or established ( 404 ). Subsequently, K is chosen to be an integer that minimizes the sum rate R(k) as shown in the figure ( 406 ). 
     Next, the quantity ε is preferably set equal to a desired bit rate penalty threshold (to control a tradeoff between rate and latency) ( 408 ), and the quality value D K  is then preferably set ( 410 ) with the quantity m′ (sensor reconstruction vector quantizer blocklength) then chosen as shown in the figure. Methods of designing vector quantizers in this context are well-known in the conventional literature. Then, a number of sensors N is preferably (though not necessarily) obtained as a multiple of K ( 412 ). 
     Preferably, a user is then communicated with ( 414 ) to the effect of imparting requirements on a sum bit rate R(K), sensor reconstruction vector quantizer blocklength m′ and quality D K . The sensors are then preferably partitioned into K contiguous groups of N/K sensors each ( 416 ). 
     Turning to step ( 418 ), during consecutive time units of N/K, within each group of sensors, each sensor preferably takes one measurement, with only one sensor in a group taking a measurement at any given time. Preferably, sensor measurement data is preferably taken at one sensor at a time, with multiple groups each taking one sample at the same time. Thus, data may be taken simultaneously by “Sensor 1” of “Group 1”, “Sensor 1” of “Group 2”, until the groups are exhausted. In the next time step, data is taken by “Sensor 2” of “Group 1”, “Sensor 2” of “Group 2”, etc. Of course, this is not meant to be restrictive, and any conceivable sequence may be implemented. After a sensor takes m′ measurements, the sensor preferably uses the vector quantizer to send data back to a data fusion center (e.g., hub  104  in  FIG. 1 ), as discussed and appreciated hereinabove and in Kashyap, supra (in the Appendix). 
     With the process continuing as shown in  FIG. 3B , the fusion center then preferably decodes information from each of the N sensors using N separate decoders of the vector quantizer ( 420 ). Finally ( 422 ), for each s in the interval (0,1), the fusion center preferably reconstructs the field value X(s) using the following algorithm:
         Find the sensor (active or inactive) closest to the location s. From the group to which this sensor belongs, select the sensor that is active (this is, has taken a direct measurement). The location of this sensor is s*.   Multiply the decoded value for location s* times ρ(s-s*) (this is the value of the autocorrelation function with lag s-s*).   The result of the multiplication is the fusion center reconstruction for the field sample X(s).       

     It is to be understood that the present invention, in accordance with at least one presently preferred embodiment, includes elements that may be implemented on at least one general-purpose computer running suitable software programs. These may also be implemented on at least one Integrated Circuit or part of at least one Integrated Circuit. Thus, it is to be understood that the invention may be implemented in hardware, software, or a combination of both. 
     If not otherwise stated herein, it is to be assumed that all patents, patent applications, patent publications and other publications (including web-based publications) mentioned and cited herein are hereby fully incorporated by reference herein as if set forth in their entirety herein. 
     Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be affected therein by one skilled in the art without departing from the scope or spirit of the invention.