article

Network correlated data gathering with explicit communication: NP-completeness and algorithms

Authors:

Razvan Cristescu,

Baltasar Beferull-Lozano,

Martin Vetterli,

Roger WattenhoferAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 14, Issue 1

Pages 41 - 54

https://doi.org/10.1109/TNET.2005.863711

Published: 01 February 2006 Publication History

Abstract

We consider the problem of correlated data gathering by a network with a sink node and a tree-based communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. For source coding of correlated data, we consider a joint entropy-based coding model with explicit communication where coding is simple and the transmission structure optimization is difficult. We first formulate the optimization problem definition in the general case and then we study further a network setting where the entropy conditioning at nodes does not depend on the amount of side information, but only on its availability. We prove that even in this simple case, the optimization problem is NP-hard. We propose some efficient, scalable, and distributed heuristic approximation algorithms for solving this problem and show by numerical simulations that the total transmission cost can be significantly improved over direct transmission or the shortest path tree. We also present an approximation algorithm that provides a tree transmission structure with total cost within a constant factor from the optimal.

References

[1]

{1} I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Commun. Mag., vol. 40, no. 8, pp. 102-116, Aug. 2002.

[2]

{2} B. Awerbuch, A. Baratz, and D. Peleg, "Cost-sensitive analysis of communication protocols," in Proc. 9th Annu. ACM Symp. Principles of Distributed Computing, 1990, pp. 177-187.

[3]

{3} J. Barros, C. Peraki, and S. D. Servetto, "Efficient network architectures for sensor reachback," in Proc. Int. Zurich Seminar on Communications, Zurich, Switzerland, 2004, pp. 184-187.

[4]

{4} D. Bertsekas, Network Optimization: Continuous and Discrete Models. Belmont, MA: Athena Scientific, 1998.

[5]

{5} K. Bharat-Kumar and J. Jaffe, "Routing to multiple destinations in computer networks," IEEE Trans. Commun., vol. COM-31, no. 3, pp. 343-351, Mar. 1983.

[6]

{6} T. M. Cover and J. A. Thomas, Elements of Information Theory. New York: Wiley, 1991.

[7]

{7} 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.

[8]

{8} R. Cristescu, B. Beferull-Lozano, and M. Vetterli, "On network correlated data gathering," in Proc. IEEE INFOCOM , 2004, pp. 2571-2582.

[9]

{9} M. Enachescu, A. Goel, R. Govindan, and R. Motwani, "Scale free aggregation in sensor networks," in Proc. 1st Int. Workshop on Algorithmic Aspects of Wireless Sensor Networks, 2004, pp. 71-84.

[10]

{10} M. R. Garey and D. S. Johnson, Computers and Intractability. San Francisco, CA: W. H. Freeman, 1979.

[11]

{11} A. Goel and D. Estrin, "Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk," in ACM-SIAM Symp. Discrete Algorithms, 2003, pp. 499-507.

[12]

{12} G. M. Guisewite and P. M. Pardalos, "Algorithms for the single-source uncapacitated minimum concave-cost network flow problem," J. Global Optimization, vol. 1, no. 3, pp. 245-265, 1991.

[13]

{13} B. Hajek, "Cooling schedules for optimal annealing," Math. Oper. Res., no. 13, pp. 311-329, 1988.

[14]

{14} W. Rabiner Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient communication protocol for wireless microsensor networks," in Proc. 33rd Annu. Hawaii Int. Conf. System Sciences (HICSS'00), Jan. 2000, pp. 3005-3014.

[15]

{15} 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.

[16]

{16} S. Khuller, B. Raghavachari, and N. Young, "Balancing minimum spanning and shortest path trees," in Proc. 4th Annu. ACM-SIAM Symp. Discrete Algorithms, 1993, pp. 243-250.

[17]

{17} B. Krishnamachari, D. Estrin, and S. Wicker, "Modeling Data Centric Routing in Wireless Sensor Networks," Dept. Comput. Eng., Univ. Southern California, Los Angeles, CA, Tech. Rep. 02-14, 2002.

[18]

{18} E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, Eds., The Traveling Salesman Problem. New York: Wiley, 1990.

[19]

{19} S. Lindsey, C. S. Raghavendra, and K. Sivalingam, "Data gathering in sensor networks using the energy^* delay metric," in Proc. IPDPS Workshop on Issues in Wireless Networks and Mobile Computing, San Francisco, CA, Apr. 2001.

[20]

{20} M. Lundy and A. Mees, "Convergence of an annealing algorithm," Math. Programming, no. 34, pp. 111-124, 1986.

[21]

{21} S. Pattem, B. Krishnamachari, and R. Govindan, "The impact of spatial correlation on routing with compression in wireless sensor networks," in Proc. Information Processing in Sensor Networks (IPSN), 2004, pp. 28-35.

[22]

{22} C. Perkins, Ad Hoc Networking. Reading, MA: Addison-Wesley, 2000.

[23]

{23} G. J. Pottie and W. J. Kaiser, "Wireless integrated sensor networks," Commun. ACM, vol. 5, no. 43, pp. 51-58, 2000.

[24]

{24} S. Pradhan and K. Ramchandran, "Distributed Source Coding Using Syndromes (DISCUS): design and construction," in Proc. IEEE Data Compression Conf., Mar. 1999, pp. 158-167.

[25]

{25} J. Rabaey, M. J. Ammer, J. L. da Silva, D. Patel, and S. Roundy, "Pico-Radio supports ad hoc ultra-low power wireless networking," IEEE Computer, vol. 33, no. 7, pp. 42-48, Jul. 2000.

[26]

{26} C. Reidys and P. Stadler, "Combinatorial landscapes," SIAM Rev., vol. 44, pp. 3-54, 2002.

[27]

{27} A. Scaglione and S. D. Servetto, "On the interdependence of routing and data compression in multi-hop sensor networks," in Proc. MobiCom, Atlanta, GA, 2002.

[28]

{28} D. Slepian and J. K. Wolf, "Noiseless coding of correlated information sources," IEEE Trans. Inf. Theory, vol. IT-19, no. 4, pp. 471-480, Jul. 1973.

[29]

{29} E. Tardos, "A strongly polynomial minimum cost circulation algorithm," Combinatorica, vol. 5, pp. 247-255, 1985.

Cited By

Wang XChen H(2022)A Reinforcement Learning-Based Dynamic Clustering Algorithm for Compressive Data Gathering in Wireless Sensor NetworksMobile Information Systems10.1155/2022/27367342022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2736734
Malathy SPorkodi VSampathkumar AHindia MDimyati KTilwari VQamar FAmiri I(2020)An optimal network coding based backpressure routing approach for massive IoT networkWireless Networks10.1007/s11276-020-02284-526:5(3657-3674)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s11276-020-02284-5
Tang B(2018)DAO²: Overcoming Overall Storage Overflow in Intermittently Connected Sensor NetworksIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8486237(135-143)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1109/INFOCOM.2018.8486237
Show More Cited By

Index Terms

Network correlated data gathering with explicit communication: NP-completeness and algorithms

Recommendations

Active node determination for correlated data gathering in wireless sensor networks

In wireless sensor network applications where data gathered by different sensor nodes is correlated, not all sensor nodes need to be active for the wireless sensor network to be functional. Given that the sensor nodes that are selected as active form a ...
Cross-Layer Optimization of Correlated Data Gathering in Wireless Sensor Networks

We consider the problem of gathering correlated sensor data by a single sink node in a wireless sensor network. We assume that the sensor nodes are energy constrained and design efficient distributed protocols to maximize the network lifetime. Many ...
Distributed data gathering in multi-sink sensor networks with correlated sources
NETWORKING'06: Proceedings of the 5th international IFIP-TC6 conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems

In this paper, we propose an effective distributed algorithm to solve the minimum energy data gathering (MEDG) problem in sensor networks with multiple sinks. The problem objective is to find a rate allocation on the sensor nodes and a transmission ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 14, Issue 1

February 2006

231 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2006

Published in TON Volume 14, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
579
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang XChen H(2022)A Reinforcement Learning-Based Dynamic Clustering Algorithm for Compressive Data Gathering in Wireless Sensor NetworksMobile Information Systems10.1155/2022/27367342022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2736734
Malathy SPorkodi VSampathkumar AHindia MDimyati KTilwari VQamar FAmiri I(2020)An optimal network coding based backpressure routing approach for massive IoT networkWireless Networks10.1007/s11276-020-02284-526:5(3657-3674)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s11276-020-02284-5
Tang B(2018)DAO²: Overcoming Overall Storage Overflow in Intermittently Connected Sensor NetworksIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8486237(135-143)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1109/INFOCOM.2018.8486237
Thanh C(2018)Modeling and Testing Power Consumption Rate of Low-Power Wi-Fi Sensor Motes for Smart Building ApplicationsFuture Data and Security Engineering10.1007/978-3-030-03192-3_34(449-459)Online publication date: 28-Nov-2018
https://dl.acm.org/doi/10.1007/978-3-030-03192-3_34
Song GZhang CLiu CChai Y(2017)A Framework for Overall Storage Overflow Problem to Maximize the Lifetime in WSNsCombinatorial Optimization and Applications10.1007/978-3-319-71150-8_2(18-32)Online publication date: 16-Dec-2017
https://dl.acm.org/doi/10.1007/978-3-319-71150-8_2
Ebrahimi DAssi C(2015)Network Coding-Aware Compressive Data Gathering for Energy-Efficient Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/282995311:4(1-24)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1145/2829953
Crary NTang BTaase SLi QXuan D(2015)Data Preservation in Data-Intensive Sensor Networks With Spatial CorrelationProceedings of the 2015 Workshop on Mobile Big Data10.1145/2757384.2757389(7-12)Online publication date: 21-Jun-2015
https://dl.acm.org/doi/10.1145/2757384.2757389
Jiang LLiu AHu YChen Z(2015)Lifetime maximization through dynamic ring-based routing scheme for correlated data collecting in WSNsComputers and Electrical Engineering10.1016/j.compeleceng.2014.04.00141:C(191-215)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.compeleceng.2014.04.001
Solomon SCheng SDevillers O(2014)Euclidean Steiner Shallow-Light TreesProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582160(454-463)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582160
Abrardo ABalucanti LMecocci A(2013)A game theory distributed approach for energy optimization in WSNsACM Transactions on Sensor Networks10.1145/2489253.24892619:4(1-22)Online publication date: 23-Jul-2013
https://dl.acm.org/doi/10.1145/2489253.2489261
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents