skip to main content
article

Power-efficient sensor placement and transmission structure for data gathering under distortion constraints

Published: 01 May 2006 Publication History

Abstract

We consider the joint optimization of sensor placement and transmission structure for data gathering, where a given number of nodes need to be placed in a field such that the sensed data can be reconstructed at a sink within specified distortion bounds while minimizing the energy consumed for communication. We assume that the nodes use either joint entropy coding based on explicit communication between sensor nodes, where coding is done when side information is available, or Slepian-Wolf coding where nodes have knowledge of network correlation statistics. We consider both maximum and average distortion bounds. We prove that this optimization is NP-complete since it involves an interplay between the spaces of possible transmission structures given radio reachability limitations, and feasible placements satisfying distortion bounds.We address this problem by first looking at the simplified problem of optimal placement in the one-dimensional case. An analytical solution is derived for the case when there is a simple aggregation scheme, and numerical results are provided for the cases when joint entropy encoding is used. We use the insight from our 1-D analysis to extend our results to the 2-D case and compare it to typical uniform random placement and shortest-path tree. Our algorithm for two-dimensional placement and transmission structure provides two to three fold reduction in total power consumption and between one to two orders of magnitude reduction in bottleneck power consumption. We perform an exhaustive performance analysis of our scheme under varying correlation models and model parameters and demonstrate that the performance improvement is typical over a range of data correlation models and parameters. We also study the impact of performing computationally-efficient data conditioning over a local scope rather than the entire network. Finally, we extend our explicit placement results to a randomized placement scheme and show that such a scheme can be effective when deployment does not permit exact node placement.

References

[1]
Cheng, P., Liu, X., and Chuah, C. N. 2004. Energy-aware node placement in wireless sensor networks. In IEEE Globecom.
[2]
Cover, T. and Thomas, J. 1991. Elements of Information Theory. Wiley.
[3]
Cressie, N. 1991. Spatial Statistics. John Wiley and Sons.
[4]
Cristescu, R., Beferull-Lozano, B., and Vetterli, M. 2005. Networked Slepian-Wolf: Theory, algorithms and scaling laws. IEEE Trans. Info. Theory.
[5]
Cristescu, R., Beferull-Lozano, B., and Vetterli, M. 2004. On network correlated data gathering. In INFOCOM.
[6]
Dasgupta, K., Kukreja, M., and Kalpakis, K. 2003. Topology--aware placement and role assignment for energy-efficient information gathering in sensor networks. In IEEE ISCC.
[7]
Eidenbenz, S. 2002. Approximation algorithms for terrain guarding. IPL.
[8]
Ganesan, D., Cristescu, R., and Beferull-Lozano, B. 2004. Power efficient node placement and transmission structure for data gathering under distortion constraints. In IPSN.
[9]
Goel, A. and Estrin, D. 2003. Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. In ACM-SIAM SODA.
[10]
Hamilton, M. Center for Embedded Networked Sensing (CENS): James Reserve Data Management System. http://dms.jamesreserve.edu/.
[11]
Heinzelman, W., Chandrakasan, A., and Balakrishnan, H. 2000. Energy-efficient communication protocols for wireless microsensor networks. In HICSS.
[12]
Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In ACM/IEEE Mobicom. Boston, MA.
[13]
Lindsey, S., Raghavendra, C., and Sivalingam, K. 2001. Data gathering in sensor networks using the energy delay metric. In IPDPS.
[14]
Marco, D., Duarte-Melo, E., Liu, M., and Neuhoff, D. 2003. On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data. In IPSN.
[15]
Pottie, G. and Kaiser, W. 2000. Wireless integrated network sensors. Comm. ACM 43, 5 (May), 51--58.
[16]
Rappaport, T. S. 1996. Wireless Communications, Principles and Practice. Prentice Hall.
[17]
Slepian, D. and Wolf, J. 1973. Noiseless coding of correlated information sources. In IEEE Trans. Information Theory. Vol. IT-19. 471--480.
[18]
Ye, W., Heidemann, J., and Estrin, D. 2002. An energy-efficient mac protocol for wireless sensor networks. In IEEE Infocom.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks
ACM Transactions on Sensor Networks  Volume 2, Issue 2
May 2006
141 pages
ISSN:1550-4859
EISSN:1550-4867
DOI:10.1145/1149283
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication History

Published: 01 May 2006
Published in TOSN Volume 2, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Sensor networks
  2. data gathering
  3. energy efficiency
  4. information theory
  5. sensing distortion
  6. sensor node placement

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Fixed-parameter tractable algorithms for Tracking Shortest PathsTheoretical Computer Science10.1016/j.tcs.2020.09.006846(1-13)Online publication date: Dec-2020
  • (2020)Tracking PathsDiscrete Applied Mathematics10.1016/j.dam.2019.11.013282(22-34)Online publication date: Aug-2020
  • (2019)BuildSenseACM Transactions on Sensor Networks10.1145/334117115:3(1-23)Online publication date: 9-Aug-2019
  • (2019)The Impact of Nodes Distribution on Energy Consumption in WSN2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT)10.1109/JEEIT.2019.8717473(590-595)Online publication date: Apr-2019
  • (2019)Structural transition in interdependent networks with regular interconnectionsPhysical Review E10.1103/PhysRevE.99.01231199:1Online publication date: 7-Jan-2019
  • (2018)Genetic Algorithm for the Nodes Deployment Problem in Industrial Wireless Sensor Networks2018 IEEE International Conference on Automation/XXIII Congress of the Chilean Association of Automatic Control (ICA-ACCA)10.1109/ICA-ACCA.2018.8609779(1-6)Online publication date: Oct-2018
  • (2018)Environmental Underground Sensing and MonitoringUnderground Sensing10.1016/B978-0-12-803139-1.00004-7(203-246)Online publication date: 2018
  • (2018)Fixed-Parameter Tractable Algorithms for Tracking Set ProblemsAlgorithms and Discrete Applied Mathematics10.1007/978-3-319-74180-2_8(93-104)Online publication date: 16-Jan-2018
  • (2017)Deployment-based lifetime optimization for linear wireless sensor networks considering both retransmission and discrete power controlPLOS ONE10.1371/journal.pone.018851912:11(e0188519)Online publication date: 29-Nov-2017
  • (2017)Energy Conservation in Progressive Decentralized Single-Hop Wireless Sensor Networks for Pervasive Computing EnvironmentIEEE Systems Journal10.1109/JSYST.2014.233931111:2(823-834)Online publication date: Jun-2017
  • Show More Cited By

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