Abstract
We study the integer maximum flow problem on wireless sensor networks with energy constraint. In this problem, sensor nodes gather data and then relay them to a base station, before they run out of battery power. Packets are considered as integral units and not splittable. The problem is to find the maximum data flow in the sensor network subject to the energy constraint of the sensors. We show that this integral version of the problem is strongly NP-complete and in fact APX-hard. It follows that the problem is unlikely to have a polynomial time approximation scheme. Even when restricted to graphs with concrete geometrically defined connectivity and transmission costs, the problem is still strongly NP-complete. We provide some interesting polynomial time algorithms that give good approximations for the general case nonetheless. For networks of bounded treewidth greater than two, we show that the problem is weakly NP-complete and provide pseudo-polynomial time algorithms. For a special case of graphs with treewidth two, we give a polynomial time algorithm.
This work was supported by BSIK grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications, Upper Saddle River. Prentice-Hall, Englewood Cliffs (1993)
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11, 1–23 (1993)
Bodlaender, H.L., Tan, R.B., van Dijk, T.C., van Leeuwen, J.: Integer maximum flow in wireless sensor networks with energy constraint. Technical Report UU-CS-2008-005, Department of Information and Computing Sciences, Utrecht University (2008)
Chang, J., Tassiulas, L.: Fast approximate algorithms for maximum lifetime routing in wireless ad-hoc networks. In: Pujolle, G., Perros, H.G., Fdida, S., Körner, U., Stavrakakis, I. (eds.) NETWORKING 2000. LNCS, vol. 1815, pp. 702–713. Springer, Heidelberg (2000)
Chang, J., Tassiulas, L.: Maximum lifetime routing in wireless sensor networks. IEEE/ACM Transaction on Networking 12(4), 609–619 (2004)
Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713–728 (2005)
Floréen, P., Kaski, P., Kohonen, J., Orponen, P.: Exact and approximate balanced data gathering in energy-constrained sensor networks. Theor. Comp. Sc. 344(1), 30–46 (2005)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York (1979)
Garg, N., Könemann, J.: Faster and simpler algorithms for multi-commodity flow and other fractional packing problems. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 300–309 (1998)
Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings 33rd Hawaii International Conference on System Sciences HICSS-33 (2000)
Hong, B., Prasanna, V.K.: Maximum lifetime data sensing and extraction in energy constrained networked sensor systems. J. Parallel and Distributed Computing 66(4), 566–577 (2006)
Kalpakis, K., Dasgupta, K., Namjoshi, P.: Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. Computer Networks 42(6), 697–716 (2003)
Ordonez, F., Krishnamachari, B.: Optimal information extraction in energy-limited wireless sensor networks. IEEE Journal on Selected Areas in Communications 22(6), 1121–1129 (2004)
Xue, Y., Cui, Y., Nahrstedt, K.: Maximizing lifetime for data aggregation in wireless sensor networks. Mobile Networks and Applications 10, 853–864 (2005)
Zhao, F., Guibas, L.: Wireless Sensor Networks: An Information Processing Approach. Morgan Kaufmann, San Francisco (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodlaender, H.L., Tan, R.B., van Dijk, T.C., van Leeuwen, J. (2008). Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint. In: Gudmundsson, J. (eds) Algorithm Theory – SWAT 2008. SWAT 2008. Lecture Notes in Computer Science, vol 5124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69903-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-69903-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69900-2
Online ISBN: 978-3-540-69903-3
eBook Packages: Computer ScienceComputer Science (R0)