Designing routes for source coding with explicit side information in sensor networks

ABSTRACT

In this paper, we study the problem of designing routes for source coding with explicit side information (i.e., with side information at both the encoder and the decoder) in sensor networks. Two difficulties in constructing such data-centric routes are the lack of reasonably practical data aggregation models and the high computational complexity resulting from the coupling of routing and in-network data fusion. Our data aggregation model is built upon the observation that in many physical situations the side information providing the most coding gain comes from a small number of nearby sensors. Based on this model, we formulate an optimization problem to minimize the communication cost, and show that finding the exact solution of this problem is NP-hard. Subsequently, two suboptimal algorithms are proposed. One is inspired by the balanced trees that have small total weights and reasonable distance from each sensor to the fusion center [6]. The other separately routes the explicit side information to achieve cost minimization. Bounds on the worst-case performance ratios of two methods to the optimal solution are derived for a special class of rate models, and simulations are conducted to shed light on their average behaviors.

REFERENCES

• 1: [1] B. Krishnamachari, D. Estrin, and S. Wicker, "Modelling data-centric routing in wireless sensor network," Univ. of Southern California, Los Angeles, Tech. Rep. CENG 02-14, 2002.
• 2: [2] R. Cristescu, B. Beferull-Lozano, and M. Vetterli, "On network correlated data gathering," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 2571-1582.
• 3: Pascal von Rickenbach , Roger Wattenhofer, Gathering correlated data in sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022640]
• 4: 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
• 5: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 6: [6] S. Khuller, B. Raghavachari, and N. Young, "Balancing minimum spanning trees and shortest-path trees," Algorithmica, vol. 14, pp. 305-321, 1995.
• 7: 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]
• 8: [8] R. Zamir and T. Berger, "Multiterminal source coding with high resolution," IEEE Trans. Inf. Theory, vol. 45, no. 1, pp. 106-117, Jan. 1999.
• 9: [9] S. S. Pradhan, J. Kusuma, and K. Ramchandran, "Distributed compression in a dense microsensor network," IEEE Commun. Mag., vol. 19, no. 3, pp. 51-60, Mar. 2002.
• 10: [10] Z. Xiong, A. D. Liveris, and S. Cheng, "Distributed source coding for sensor networks," IEEE Signal Process. Mag., vol. 21, no. 5, pp. 80-94, Sep. 2004.
• 11: [11] H. Luo, Y. Tong, and G. Pottie, "A two-stage DPCM scheme for wireless sensor networks," in Proc. IEEE Int. Conf. Accoustic, Speech, and Signal Processing, Philadelphia, PA, 2005, pp. iii/661-iii/664.
• 12: [12] J. Chen, L. Yip, J. Elson, H. Wang, D. Maniezzo, R. E. Hudson, K. Yao, and D. Estrin, "Coherent acoustic array processing and localization on wireless sesnor networks," Proc. IEEE, vol. 91, no. 8, pp. 1154-1162, Aug. 2003.
• 13: Anna Scaglione , Sergio D. Servetto, On the interdependence of routing and data compression in multi-hop sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570663]
• 14: [14] S. Bandyopadhyay and E. J. Coyle, "An energy efficient hierarchical clustering algorithm for wireless sensor networks," in Proc. IEEE INFOCOM , 2003, pp. 1713-1723.
• 15: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 16: [16] K. Bharath-Kumar and J. M. Jaffe, "Routing to multiple destinations in computer networks," IEEE Trans. Commun., vol. COM-31, no. 3, pp. 343-351, Mar. 1983.
• 17: [17] H. Luo and G. J. Pottie, "Routing explicit side information for data compression in wireless sensor networks," in Proc. Int. Conf. Distributed Computing in Sensor Systems, Marina del Rey, CA, Jun. 2005, pp. 75-88.
• 18: [18] H. Luo and G. Pottie, "Balanced aggregation trees for routing correlated data in wireless sensor networks," in Proc. IEEE Int. Symp. Information Theory, Adelaide, Australia, Sep. 2005, pp. 14-18.
• 19: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 20: [20] J. H. Chang and L. Tassiulas, "Energy conserving routing in wireless ad-hoc networks," in Proc. IEEE INFOCOM, 2000, pp. 22-31.
• 21: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 22: [22] Y. J. Chu and T. H. Liu, "On the shortest arborescence of a directed graph," Science Sinica, vol. 14, pp. 1396-1400, 1965.
• 23: [23] J. Edmonds, "Optimum branchings," J. Res. National Bureau of Standards , vol. 71B, pp. 233-240, 1967.
• 24: [24] H. Takahashi and A. Matsuyama, "An approximate solution for the steiner problem in graphs," Math. Japonica, vol. 24, no. 6, pp. 573-577, 1980.
• 25: S. Haldar, An “all pairs shortest paths” distributed algorithm using 2n2 messages, Journal of Algorithms, v.24 n.1, p.20-36, July 1997 [doi>10.1006/jagm.1996.0842]
• 26: [26] P. A. Humblet, "A distributed algorithm for minimum weight directed spanning trees," IEEE Trans. Commun., vol. COM-31, no. 6, pp. 756-762, Jun. 1983.
• 27: [27] F. K. Hwang, D. S. Richards, and P. Winter, The Steiner Tree Problem. Amsterdam: North-Holland, 1992.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Trees

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design

Keywords:
NP-hardness, Steiner tree, data-centric routing, maximum weight branching, shortest path tree, source coding