Abstract
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 structure on the network graph, such that the data collected by the sink nodes can reproduce the field of observation, and the total energy consumed by the sensor nodes is minimized. We formulate the problem as a linear optimization problem. The formulation exploits data correlation among the sensor nodes and considers the effect of wireless channel interference. We apply Lagrangian dualization technique on this formulation to obtain a subgradient algorithm for computing the optimal solution. The subgradient algorithm is asynchronous and amenable to fully distributed implementations, which corresponds to the decentralized nature of sensor networks.
Chapter PDF
Similar content being viewed by others
Keywords
References
Clouqueur, T., Phipatanasuphorn, V., Ramanathan, P., Saluja, K.K.: Sensor Deployment Strategy for Detection of Targets Traversing a Region. In: ACM Mobile Networks and Applications, vol. 8, pp. 453–461 (2003)
Mainwaring, A., Polastre, J., Szewczyk, R., Culler, D.: Wireless Sensor Networks for Habitat Monitoring. In: Proc. of First ACM International Workshop on Wireless Sensor Network and Applications (2002)
Cristescu, R., Beferull-Lozano, B., Vetterli, M.: On Network Correlated Data Gathering. In: Proc. of IEEE INFOCOM (2004)
Gupta, P., Kumar, P.R.: The Capacity of Wireless Networks. IEEE Trans. Information Theory 46(2), 388–404 (2000)
Slepian, D., Wolf, J.K.: Noiseless Coding of Correlated Information Sources. IEEE Trans. on Information Theory 4(IT-19), 471–480 (1973)
Cristescu, R., Beferull-Lozano, B., Vetterli, M.: Networked Slepian-Wolf: Theory and Algorithms. In: Proc. of European Workshop on Wireless Sensor Networks (2004)
Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice Hall, Englewood Cliffs (1989)
Kelly, F.P., Maulloo, A.K., Tan, D.K.H.: Rate Control in Communication Networks: Shadow prices, Proportional Fairness and Stability. Journal of the Operational Research Society 49, 237–252 (1998)
Low, S.H., Lapsley, D.E.: Optimization Flow Control: Basic Algorithm and Covergence. IEEE/ACM Trans. on Networking 7, 861–874 (1999)
Xue, Y., Li, B., Nahrstedt, K.: Optimal Resource Allocation in Wireless Ad Hoc Networks: A Price-Based Approach. In: IEEE Transactions on Mobile Computing (2005) (to appear)
Sherali, H.D., Choi, G.: Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs. Operations Research Letter 19, 105–113 (1996)
Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, New York (1991)
Lotfinezhad, M., Liang, B.: Effect of Partially Correlated Data on Clustering in Wireless Sensor Networks. In: Proc. of the IEEE International Conference on Sensor and Ad hoc Communications and Networks, SECON (2004)
Kalpakis, K., Dasgupta, K., Namjoshi, P.: Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks. Computer Networks Journal (2002)
Krishnamachri, B., Estrin, D., Wicker, S.: Modelling Data-centric Routing in Wireless Sensor Networks. In: Proc. of IEEE INFOCOM (2002)
Rickenbach, P.V., Wattenhofer, R.: Gathering Correlated Data in Sensor Networks. In: Proc. of DIALM-POMC 2004: Proceedings of the 2004 joint workshop on Foundations of mobile computing, pp. 60–66 (2004)
Goel, A., Estrin, D.: Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk. In: Proc. of the 14th Symposium on Discrete Algorithms, SODA (2003)
Barros, J., Servetto, S.D.: Network Information Flow with Correlated Sources. Submitted to the IEEE Transactions on Information Theory, November 2003 (Original title: The Sensor Reachback Problem) Revised (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 IFIP International Federation for Information Processing
About this paper
Cite this paper
Yuen, K., Li, B., Liang, B. (2006). Distributed Data Gathering in Multi-sink Sensor Networks with Correlated Sources. In: Boavida, F., Plagemann, T., Stiller, B., Westphal, C., Monteiro, E. (eds) NETWORKING 2006. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems. NETWORKING 2006. Lecture Notes in Computer Science, vol 3976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11753810_72
Download citation
DOI: https://doi.org/10.1007/11753810_72
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34192-5
Online ISBN: 978-3-540-34193-2
eBook Packages: Computer ScienceComputer Science (R0)