Lossy network correlated data gathering with high-resolution coding

ABSTRACT

Sensor networks measuring correlated data are considered, where the task is to gather data from the network nodes to a sink. A specific scenario is addressed, where data at nodes are lossy coded with high-resolution, and the information measured by the nodes has to be reconstructed at the sink within both certain total and individual distortion bounds. The first problem considered is to find the optimal transmission structure and the rate-distortion allocations at the various spatially located nodes, such as to minimize the total power consumption cost of the network, by assuming fixed nodes positions. The optimal transmission structure is the shortest path tree and the problems of rate and distortion allocation separate in the high-resolution case, namely, first the distortion allocation is found as a function of the transmission structure, and second, for a given distortion allocation, the rate allocation is computed. The second problem addressed is the case when the node positions can be chosen, by finding the optimal node placement for two different targets of interest, namely total power minimization and network lifetime maximization. Finally, node placement solution that provides tradeoff between the two metrics is proposed.

REFERENCES

• 1: S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
• 2: [2] J. Barros, C. Peraki, and S. D. Servetto, "Efficient network architectures for sensor reachback, "in Proc. IEEE Int. Zurich Seminar on Commun., 2004.
• 3: [3] T. Berger, Multiterminal Source Coding: Lectures presented at CISM Summer School on the Information Theory Approach to Communications, 1977.
• 4: [4] D. Bertsekas, Network Optimization: Continuous and Discrete Models. Belmont, MA: Athena Scientific, 1998.
• 5: [5] C. Chong and S. P. Kumar, "Sensor networks: Evolution, opportunities and challenges," Proc. IEEE, vol. 91, no. 8, 2003.
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: [7] N. Cressie, Statistics for Spatial Data. New York: Wiley, 1991.
• 8: [8] R. Cristescu, B. Beferull-Lozano, and M. Vetterli, "Networked Slepian-Wolf: Theory, algorithms and scaling laws," IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4057-4073, Dec. 2005.
• 9: [9] R. Cristescu, B. Beferull-Lozano, M. Vetterli, and R. Wattenhofer, "Network correlated data gathering with explicit communication: NP-completeness and algorithms," IEEE Trans. Netw., vol. 14, no. 1, pp. 41-54, Feb. 2006.
• 10: [10] R. Cristescu, B. Beferull-Lozano, and M. Vetterli, "On network correlated data gathering, "in Proc. INFOCOM, Hong-Kong, China, 2004.
• 11: [11] M. Enachescu, A. Goel, R. Govindan, and R. Motwani, "Scale free aggregation in sensor networks," Algosensor, 2004.
• 12: [12] M. Franceschetti, J. Bruck, and L. J. Schulman, "A random walk model of wave propagation," IEEE Trans. Antennas Propag., vol. 52, May 2004.
• 13: [13] D. Ganesan, R. Cristescu, and B. Beferull-Lozano, "Power-efficient sensor placement and transmission structure for data gathering under distortion constraints," ACM Trans. Sensor Netw., 2005, to be published.
• 14: Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 15: [15] D. Marco, E. Duarte-Melo, 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," in Proc. IEEE/ACM IPSN, Palo Alto Research Center (PARC), Palo Alto, CA, 2003.
• 16: [16] A. Pandya, A. Kansal, G. Pottie, and M. Srivastava, "Bounds on the rate-distortion of multiple cooperative Gaussian sources," Univ. Calif. Los Angeles, Tech. Rep., 2003.
• 17: Sundeep Pattem , Bhaskar Krishnamachari , Ramesh Govindan, The impact of spatial correlation on routing with compression in wireless sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984627]
• 18: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 19: [19] D. Slepian and J. K. Wolf, "Noiseless coding of correlated information sources," IEEE Trans. Inf. Theory, vol. IT-19, pp. 471-480, 1973.
• 20: [20] R. Zamir, "The rate loss in the Wyner-Ziv problem," IEEE Trans. Inf. Theory, vol. 42, pp. 2073-2084, Nov. 1996.
• 21: [21] R. Zamir and T. Berger, "Multiterminal source coding with high resolution," IEEE Trans. Inf. Theory, vol. 45, pp. 106-117, Jan. 1999.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Design, Performance

Keywords:
energy efficiency, high-resolution rate-distortion, sensor networks, shortest path tree