Approximating maximum integral flows in wireless sensor networks via weighted-degree constrained k-flows

ABSTRACT

We consider the Maximum Integral Flow with Energy Constraints problem: given a directed graph G=(V,E) with edge-weights w(e):e ∈ E and node battery capacities (b(v):v ∈ V), and two nodes r,s ∈ V, find a maximum integral rs-flow f so that for every node v its energy consumption sum_{vu ∈ E} f(vu)w(vu) is at most b(v). Let k be the maximum integral flow value. We give a polynomial time algorithm that computes a flow of value at least ⌊ k/16 ⌋. As checking whether k ≥ 1 can be done in polynomial time, this gives an approximation algorithm with ratio that approaches 1/16 when k is large, and is not worse than 1/31. This is the first constant ratio approximation algorithm for this problem, which solves an open question from [2]. This result is based on a bicriteria approximation algorithm for a more general problem, in which we seek a minimum cost set of k pairwise edge-disjoint rs-paths (that is, a k-flow) subject to weighted degree constraints. We give a polynomial time algorithm that computes a flow of value k and violates the weighted degrees by a factor at most 4. This result is of independent interest.

REFERENCES

• 1: Nikhil Bansal , Rohit Khandekar , Viswanath Nagarajan, Additive guarantees for degree bounded directed network design, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374486]
• 2: Hans L. Bodlaender , Richard B. Tan , Thomas C. Dijk , Jan Leeuwen, Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint, Proceedings of the 11th Scandinavian workshop on Algorithm Theory, July 02-04, 2008, Gothenburg, Sweden [doi>10.1007/978-3-540-69903-3_11]
• 3: Jae-Hwan Chang , Leandros Tassiulas, Maximum lifetime routing in wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.609-619, August 2004 [doi>10.1109/TNET.2004.833122]
• 4: Michael Elkin , Yuval Lando , Zeev Nutov , Michael Segal , Hanan Shpungin, Novel Algorithms for the Network Lifetime Problem in Wireless Settings, Proceedings of the 7th international conference on Ad-hoc, Mobile and Wireless Networks, p.425-438, September 10-12, 2008, Sophia-Antipolis, France [doi>10.1007/978-3-540-85209-4_34]
• 5: Patrik Floréen , Petteri Kaski , Jukka Kohonen , Pekka Orponen, Exact and approximate balanced data gathering in energy-constrained sensor networks, Theoretical Computer Science, v.344 n.1, p.30-46, 11 November 2005 [doi>10.1016/j.tcs.2005.06.024]
• 6: T. Fukunaga and H. Nagamochi. Network design with weighted degree constraints. TR 2006--012, Kyoto University, 2008.
• 7: Martin Fürer , Balaji Raghavachari, Approximating the minimum-degree Steiner tree to within one of optimal, Journal of Algorithms, v.17 n.3, p.409-423, Nov. 1994
• 8: Michel X. Goemans, Minimum Bounded Degree Spanning Trees, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.273-282, October 21-24, 2006 [doi>10.1109/FOCS.2006.48]
• 9: Teofilo F. Gonzalez, Handbook of Approximation Algorithms and Metaheuristics (Chapman & Hall/Crc Computer & Information Science Series), Chapman & Hall/CRC, 2007
• 10: Bo Hong , Viktor K. Prasanna, Maximum lifetime data sensing and extraction in energy constrained networked sensor systems, Journal of Parallel and Distributed Computing, v.66 n.4, p.566-577, April 2006 [doi>10.1016/j.jpdc.2005.10.009]
• 11: K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39--60, 2001.
• 12: Konstantinos Kalpakis , Koustuv Dasgupta , Parag Namjoshi, Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.42 n.6, p.697-716, 21 August 2003 [doi>10.1016/S1389-1286(03)00212-3]
• 13: J. Könemann , R. Ravi, A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees, SIAM Journal on Computing, v.31 n.6, p.1783-1793, 2002 [doi>10.1137/S009753970036917X]
• 14: Lap Chi Lau , Joseph (Seffi) Naor , Mohammad R. Salavatipour , Mohit Singh, Survivable network design with degree or order constraints, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250886]
• 15: Zeev Nutov, Approximating Directed Weighted-Degree Constrained Networks, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_18]
• 16: F. Ordonez and B. Krishnamachari. Optimal information extraction in energy-limited wireless sensor networks. IEEE Journal on Selected Areas in Communications, 22(6):1121--1129, 2004.
• 17: A. Schrijver. Combinatorial Optimization Polyhedra and Efficiency. Springer-Verlag Berlin Heidelberg New York, 2004.
• 18: Mohit Singh , Lap Chi Lau, Approximating minimum bounded degree spanning trees to within one of optimal, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250887]
• 19: Lap Chi Lau , Mohit Singh, Additive approximation for bounded degree survivable network design, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374485]
• 20: Yuan Xue , Yi Cui , Klara Nahrstedt, Maximizing lifetime for data aggregation in wireless sensor networks, Mobile Networks and Applications, v.10 n.6, p.853-864, December 2005 [doi>10.1007/s11036-005-4443-7]
• 21: Feng Zhao , Leonidas Guibas, Wireless Sensor Networks: An Information Processing Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design

Keywords:
integral flow, maximum flow, network design, weighted degree, wireless sensor networks