skip to main content
article

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

Published: 01 December 2007 Publication History

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]
{3} P. von Rickenbach and R. Wattenhofer, "Gathering correlated data in sensor networks," presented at the DialM-POMC, Philadelphia, PA, Oct. 2004.
[4]
{4} A. Goel and D. Estrin, "Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk," presented at the ACM/SIAM Symp. Discrete Algorithms, Baltimore, MD, 2003.
[5]
{5} C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, "Directed diffusion for wireless sensor networking," IEEE/ACM Trans. Netw., vol. 11, no. 1, pp. 2-16, Feb. 2003.
[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]
{7} G. Pottie and W. Kaiser, "Wireless sensor networks," Commun. ACM, vol. 43, no. 5, pp. 51-58, May 2000.
[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]
{13} A. Scaglione and S. Servetto, "On the interdependence of routing and data compression in multi-hop sensor networks," presented at the ACM/IEEE Mobicom, Atlanta, GA, 2002.
[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]
{15} W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient communication protocol for wireless microsensor networks," in Proc. 33rd Hawaii Int. Conf. System Sciences, Maui, HI, Jan. 2000, p. 8020.
[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]
{19} M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: W. H. Freeman, 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]
{21} S. Singh, M. Woo, and C. S. Raghavendra, "Power-aware routing in mobile ad-hoc networks," in Proc. ACM/IEEE Mobicom, Dallas, TX, 1998, pp. 181-190.
[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]
{25} S. Haldar, "An 'all pairs shortest paths' distributed algorithm using 2n 2 messages," J. Algorithms, vol. 24, pp. 20-36, 1997.
[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.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 6
December 2007
400 pages

Publisher

IEEE Press

Publication History

Published: 01 December 2007
Published in TON Volume 15, Issue 6

Author Tags

  1. NP-hardness
  2. Steiner tree
  3. data-centric routing
  4. maximum weight branching
  5. shortest path tree
  6. source coding

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 230
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media