Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Composition and Scaling Challenges in Sensor Networks: An Interaction-Centric View Kapitel lesen Erstes Kapitel lesen

2011 | OriginalPaper | Buchkapitel

7. Networked Distributed Source Coding

verfasst von : Shizheng Li, Aditya Ramamoorthy

Erschienen in: Theoretical Aspects of Distributed Computing in Sensor Networks

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The data sensed by different sensors in a sensor network is typically correlated. A natural question is whether the data correlation can be exploited in innovative ways along with network information transfer techniques to design efficient and distributed schemes for the operation of such networks. This necessarily involves a coupling between the issues of compression and networked data transmission that have usually been considered separately. In this work we review the basics of classical distributed source coding and discuss some practical code design techniques for it. We argue that the network introduces several new dimensions to the problem of distributed source coding. The compression rates and the network information flow constrain each other in intricate ways. In particular, we show that network coding is often required for optimally combining distributed source coding and network information transfer and discuss the associated issues in detail. We also examine the problem of resource allocation in the context of distributed source coding over networks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Theoretical Aspects of Graph Models for MANETs
Nächstes Kapitel The Spatial Smoothing Method of Clock Synchronization in Wireless Networks
Fußnoten
1
In this chapter, assume that the size of the finite field is a power of 2 so addition and subtraction are the same.
 
2
\(H_b(p)\) is the binary entropy function defined as \(H_b(p) = -p \log_2 p - (1-p) \log_2 (1-p)\).
 
3
A directed spanning tree (also called arborescence) of a directed graph \(G=(V,A)\) rooted at vertex \(r \in V\) is a subgraph T of G such that it is a spanning tree if the orientation of the edges is ignored and there is a path from r to all \(v \in V\) when the direction of edges is taken into account. The minimum weight directed spanning tree can be found by a greedy algorithm in polynomial time [54].
 
4
“Mixed” graph refers to a graph with directed edges and undirected edges.
 
5
A length r vector with elements from \(G\!F(2)\) can be viewed as an element from \(G\!F(2^r)\).
 
6
We could also simply perform random linear network coding on these edges.
 
Literatur
1.
D. Slepian and J. Wolf. Noiseless coding of correlated information sources. IEEE Transactions on Information Theory, 19:471–480, July 1973.CrossRefMathSciNetMATH
2.
R. Ahlswede, N. Cai, S.-Y. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204–1216, 2000.CrossRefMathSciNetMATH
3.
X. Lin and N. Shroff. Utility maximization for communication networks with multipath routing. IEEE Transactions on Automatic Control, 51(5):766–781, May 2006.CrossRefMathSciNet
4.
M. Chiang, S. Low, A. Calderbank, and J. Doyle. Layering as optimization decomposition: A mathematical theory of network architectures. Proceedings of the IEEE, 95(1):255–312, January 2007.CrossRef
5.
C. E. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal, 27:379–423, 623–656, July, October 1948.MathSciNetMATH
6.
7.
Z. Xiong, A. Liveris, and S. Cheng. Distributed source coding for sensor networks. Signal Processing Magazine, IEEE, 21(5):80–94, September 2004.CrossRef
8.
T. Cover. A proof of the data compression theorem of slepian and wolf for ergodic sources (corresp.), IEEE Transactions on Information Theory, 21(2):226–228, March 1975.CrossRefMathSciNetMATH
9.
V. Stankovic, A. Liveris, Z. Xiong, and C. Georghiades. On code design for the slepian-wolf problem and lossless multiterminal networks. IEEE Transactions on Information Theory, 52(4):1495–1507, April 2006.CrossRefMathSciNet
10.
C.-F. Lan, A. Liveris, K. Narayanan, Z. Xiong, and C. Georghiades. Slepian-wolf coding of multiple m-ary sources using ldpc codes. In: Data Compression Conference, 2004. Proceedings. DCC 2004, page 549, March 2004.
11.
A. Liveris, C. Lan, K. Narayanan, Z. Xiong, and C. Georghiades. Slepian-Wolf coding of three binary sources using LDPC codes. In: Proceedings of International Symposium on Turbo Codes and Related Topics, Brest, France, Sep. 2003.
12.
13.
S. S. Pradhan and K. Ramchandran. Distributed Source Coding using Syndromes (DISCUS): Design and Construction. IEEE Transactions on Information Theory, 49:626–643, March 2003.CrossRefMathSciNetMATH
14.
A. Liveris, Z. Xiong, and C. N. Georghiades. Compression of binary sources with side information at the decoder using LDPC codes. IEEE Communications Letters, 6(10):440–442, 2002.CrossRef
15.
D. Varodayan, A. Aaron, and B. Girod. Rate-adaptive codes for distributed source coding. Signal Processing, 86(11):3123–3130, 2006.CrossRefMATH
16.
P. Tan and J. L. Tiffany. A general and optimal framework to achieve the entire rate region for slepian-wolf coding. Signal Processing, 86(11):3102–3114, 2006.CrossRefMATH
17.
J. Muramatsu and T. Uyematsu, and T. Wadayama. Low-density parity-check matrices for coding of correlated sources. IEEE Transactions on Information Theory, 51(10):3645–3654, 2005.CrossRefMathSciNet
18.
M. Sartipi and F. Fekri. Distributed source coding in wireless sensor networks using LDPC coding: the entire Slepian-Wolf rate region. In: IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, LA, USA, March 2005.
19.
S. Pradhan and K. Ramchandran. Distributed source coding: symmetric rates and applications to sensor networks. In: Data Compression Conference, 2000. Proceedings. DCC 2000, pages 363–372, 2000.
20.
S. Lin and D. J. Costello. Error Control Coding: Fundamentals and Applications. Prentice Hall, New Jersey, 2004.
21.
R. Gallager. Information Theory and Reliable Communication, Wiley, New York, 1968.MATH
22.
T. Richardson and R. Urbanke. Modern Coding Theory, Cambridge University Press, Cambridge, 2008.CrossRefMATH
23.
J. Garcia-Frias, Y. Zhao, and W. Zhong. Turbo-like codes for transmission of correlated sources over noisy channels. Signal Processing Magazine, IEEE, 24(5):58–66, September 2007.CrossRef
24.
J. Garcia-Frias and Y. Zhao. Compression of correlated binary sources using turbo codes. IEEE Communications Letters, 5(10):417–419, October 2006.CrossRef
25.
A. Aaron and B. Girod. Compression with side information using turbo codes. In: Proceedings of IEEE Data Compression Conference(DCC), pages 252–261, 2002.
26.
T. P. Coleman, A. H. Lee, M. Medard, and M. Effros. Low-complexity approaches to Slepian-Wolf near-lossless distributed data compression. IEEE Transactions on Information Theory, 52(8):3546–3561, 2006.CrossRefMathSciNet
27.
B. Rimoldi and C. Urbanke. Asynchronous Slepian-Wolf coding via source-splitting. In: Proceedings of International Symposium on Information Theory, Ulm, Germany, page 271, Ulm, Germany, June–July 1997.
28.
S. Y. Tung, Multiterminal source coding, Ph.D. Dissertation, Cornell University, 1978.
29.
K. Housewright. Source coding studies for multiterminal systems. Ph.D. Dissertation, University of California, Los Angeles, 1977.
30.
T. Berger. Multiterminal source coding. In: CISM Courses and Lectures No. 229, The Information Theory Approach to Communications, Springer-Verlag, Berlin, 1980.
31.
W. Kang and S. Ulukus. An outer bound for the multi-terminal rate-distortion region. In: IEEE International Symposium on Information Theory, pages 1419–1423, Seattle, Washington, USA, July 2006.
32.
T. Berger. Multiterminal rate-distortion theory revisited. In Communication, Control, and Computing, 2008 46th Annual Allerton Conference, pages 1535–1537, September 2008.
33.
34.
Y. Oohama, Rate-distortion theory for gaussian multiterminal source coding systems with several side informations at the decoder. IEEE Transactions on Information Theory, 51(7):2577–2593, July 2005.CrossRefMathSciNet
35.
Y. Yang, V. Stankovic, Z. Xiong, and W. Zhao. On multiterminal source code design. In Data Compression Conference, 2005. Proceedings. DCC 2005, pages 43–52, Snowbird, Utah, USA, March 2005.
36.
Y. Zhang, Z. Xiong, and Y. Yang. Code design for quadratic gaussian multiterminal source coding: The symmetric case. In: IEEE International Symposium on Information Theory, 28:1458–1462, July 3, 2009.
37.
A. Wyner and J. Ziv. The rate-distortion function for source coding with side information at the decoder. IEEE Transactions on Information Theory, 22(1):1–10, January 1976.CrossRefMathSciNetMATH
38.
R. Zamir, S. Shamai, and U. Erez. Nested linear/lattice codes for structured multiterminal binning. IEEE Transactions on Information Theory, 48(6):1250–1276, June 2002.CrossRefMathSciNetMATH
39.
S. Servetto, Lattice quantization with side information: Codes, asymptotics, and applications in sensor networks. IEEE Transactions on Information Theory, 53(2):714–731, February 2007.CrossRefMathSciNet
40.
Z. Liu, S. Cheng, A. Liveris, and Z. Xiong. Slepian-wolf coded nested quantization (swc-nq) for wyner-ziv coding: performance analysis and code design. In: Data Compression Conference, 2004. Proceedings. DCC 2004, pages 322–331, March 2004.
41.
B. Girod, A. Aaron, S. Rane, and D. Rebollo-Monedero. Distributed video coding. Proceedings of the IEEE, 93(1):71–83, January 2005.CrossRef
42.
Y. Yang, S. Cheng, Z. Xiong, and W. Zhao. Wyner-ziv coding based on tcq and ldpc codes. IEEE Transactions on Communications, 57(2):376–387, February 2009.CrossRef
43.
T. Berger, Z. Zhang, and H. Viswanathan. The ceo problem [multiterminal source coding]. IEEE Transactions on Information Theory, 42(3):887–902, May 1996.CrossRefMathSciNetMATH
44.
H. Viswanathan and T. Berger. The quadratic gaussian ceo problem. IEEE Transactions on Information Theory, 43(5):1549–1559, September 1997.CrossRefMathSciNetMATH
45.
Y. Oohama. The rate-distortion function for the quadratic gaussian ceo problem. IEEE Transactions on Information Theory, 44(3):1057–1070, May 1998.CrossRefMathSciNetMATH
46.
V. Prabhakaran, D. Tse, and K. Ramachandran. Rate region of the quadratic gaussian ceo problem. In: IEEE International Symposium on Information Theory, page 119, June-2 July 2004.
47.
J.-H. Chang and L. Tassiulas. Maximum lifetime routing in wireless sensor networks. IEEE/ACM Transactions on Networking, 12(4):609–619, August 2004.CrossRef
48.
49.
J. Barros and S. Servetto. Network information flow with correlated sources. IEEE Transactions on Information Theory, (52):155–170, January 2006.
50.
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New Jersey, 1993.
51.
S. P. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, 2004.MATH
52.
A. Roumy and D. Gesbert, Optimal matching in wireless sensor networks. IEEE Journal of Selected Topics in Signal Processing, 1(4):725–735, December 2007.CrossRef
53.
S. Li and A. Ramamoorthy. Rate and power allocation under the pairwise distributed source coding constraint. IEEE Transactions on Communications, 57(12), December 2009.
54.
Y. J. Chu and T. H. Liu, On the shortest arborescence of a directed graph. Science Sinica, 14:1396–1400, 1965.MATH
55.
R. Cristescu and B. Beferull-Lozano. Lossy network correlated data gathering with high-resolution coding. IEEE Transactions on Information Theory, 52(6):2817–2824, June 2006.CrossRefMathSciNet
56.
57.
58.
R. Cristescu, B. Beferull-Lozano, and M. Vetterli. Networked slepian-wolf: theory, algorithms, and scaling laws. IEEE Transactions on Information Theory, 51(12):4057–4073, December 2005.CrossRefMathSciNet
59.
D. Tse and S. Hanly. Multiaccess fading channels. i. polymatroid structure, optimal resource allocation and throughput capacities. IEEE Transactions on Information Theory, 44(7):2796–2815, November 1998.CrossRefMathSciNetMATH
60.
J. Liu, M. Adler, D. Towsley, and C. Zhang. On optimal communication cost for gathering correlated data through wireless sensor networks. In: ACM MobiCom, Los Angeles, CA, USA, 2006.
61.
J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, New York, NY, 2005.
62.
63.
R. Koetter and M. Médard. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 11(5):782–795, 2003.CrossRef
64.
T. Ho, M. Medard, R. Koetter, D. Karger, M. Effros, J. Shi, and B. Leong. A random linear network coding approach to multicast. IEEE Transactions on Information Theory, 52(10):4413–4430, 2006.CrossRefMathSciNet
65.
P. A. Chou, Y. Wu, and K. Jain. Practical network coding. In: 41st Allerton Conference on Communication, Control, and Computing, 2003.
66.
67.
L. Song and R. W.Yeung. Network information flow – multiple sources. In: Proceedings of Intl Symp. Information Theory, Washington DC, USA, 2001.
68.
A. Ramamoorthy, K. Jain, P. A. Chou, and M. Effros. Separating Distributed Source Coding from Network Coding, IEEE Transactions on Information Theory, 52:2785–2795, June 2006.CrossRefMathSciNet
69.
Y. Wu, V. Stankovic, Z. Xiong, and S.-Y. Kung. On practical design for joint distributed source and network coding. IEEE Transactions on Information Theory, 55(4):1709–1720, 2009.CrossRefMathSciNet
70.
A. Ramamoorthy. Communicating the sum of sources over a network. In Proceedings of International Symposium Information Theory, pages 1646–1650, Toronto, ON, Canada, 2008.
71.
A. Ramamoorthy and M. Langberg. Communicating the sum of sources in a 3-sources/3-terminals network. In Proceedings of International Symposium Information Theory, pages 2121–2125, Seoul, Korea, 2009.
72.
73.
A. Ramamoorthy. Minimum cost distributed source coding over a network. In: IEEE International Symposium on Information Theory, pages 1761–1765, Nice, France, 2007.
74.
A. Ramamoorthy, Minimum cost distributed source coding over a network. In: IEEE Transactions on Information Theory
75.
D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Nashua, NH, 1999.MATH
76.
H. D. Sherali and G. Choi. Recovery of primal solutions when using subgradient optimization methods to solve lagrangian duals of linear programs. Operations Research Letters, 19(3):105–113, 1996.CrossRefMathSciNetMATH
Metadaten
Titel
Networked Distributed Source Coding
verfasst von
Shizheng Li
Aditya Ramamoorthy
Copyright-Jahr
2011
Verlag
Springer Berlin Heidelberg
Buch
Theoretical Aspects of Distributed Computing in Sensor Networks

Print ISBN: 978-3-642-14848-4

Electronic ISBN: 978-3-642-14849-1

Copyright-Jahr: 2011

DOI
https://doi.org/10.1007/978-3-642-14849-1_7

Premium Partner

    Bildnachweise