On the interdependence of routing and data compression in multi-hop sensor networks

ABSTRACT

We consider a problem of broadcast communication in a multi-hop sensor network, in which samples of a random field are collected at each node of the network, and the goal is for all nodes to obtain an estimate of the entire field within a prescribed distortion value. The main idea we explore in this paper is that of jointly compressing the data generated by different nodes as this information travels over multiple hops, to eliminate correlations in the representation of the sampled field. Our main contributions are: (a) we obtain, using simple network flow concepts, conditions on the rate/distortion function of the random field, so as to guarantee that any node can obtain the measurements collected at every other node in the network, quantized to within any prescribed distortion value; and (b), we construct a large class of physically-motivated stochastic models for sensor data, for which we are able to prove that the joint rate/distortion function of all the data generated by the whole network grows slower than the bounds found in (a). A truly novel aspect of our work is the tight coupling between routing and source coding, explicitly formulated in a simple and analytically tractable model---to the best of our knowledge, this connection had not been studied before.

REFERENCES

• 1: R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network Information Flow. IEEE Trans. Inform. Theory, 46(4):1204--1216, 2000.
• 2: T. Berger. Rate distortion Theory, Prentice Hall, Englewood Cliffs, NJ.
• 3: J. H. Conway , N. J. A. Sloane , E. Bannai, Sphere-packings, lattices, and groups, Springer-Verlag New York, Inc., New York, NY, 1987
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• 7: U. Grenander and G. Szegö. Toeplitz Forms and their Applications. University of California Press, 1958.
• 8: P. Gupta and P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. In W. M. McEneany, G. Yin, and Q. Zhang, editors, Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming. Birkhauser, 1998.
• 9: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Inform. Theory, 46(2):388--404, 2000.
• 10: H. B. Keller Numerical Methods For Two-Point Boundary-Value Problems. Dover Publications Inc., 1992.
• 11: S. Sandeep Pradhan , Kannan Ramchandran, Distributed Source Coding: Symmetric Rates and Applications to Sensor Networks, Proceedings of the Conference on Data Compression, p.363, March 28-30, 2000
• 12: Sergio D. Servetto, Lattice Quantization with Side Information, Proceedings of the Conference on Data Compression, p.510, March 28-30, 2000
• 13: C. E. Shannon, Coding Theorems for a Discrete Source With a Fidelity Criterion Institute of Radio Engineers, International Convention Record, Vol. 7 (Part 4), pp. 142--163, 1959.
• 14: V. A. Vaishampayan, N. J. A. Sloane, and S. D. Servetto. Multiple Description Vector Quantization with Lattice Codebooks: Design and Analysis. IEEE Trans. Inform. Theory, 47(5):1718--1734, 2001.
• 15: Qian Zhao , Michelle Effros, Optimal Code Design for Lossless and Near Lossless Source Coding in Multiple Access Networks, Proceedings of the Data Compression Conference (DCC '01), p.263, March 27-29, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Design, Performance, Theory

Keywords:
cross-layer interactions, multi-hop networks, routing, sensor networks, source coding