Minimum energy disjoint path routing in wireless ad-hoc networks

ABSTRACT

We develop algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Our major results include a novel polynomial time algorithm that optimally solves the minimum energy 2 link-disjoint paths problem, as well as a polynomial time algorithm for the minimum energy k node-disjoint paths problem. In addition, we present efficient heuristic algorithms for both problems. Our results show that link-disjoint paths consume substantially less energy than node-disjoint paths. We also found that the incremental energy of additional link-disjoint paths is decreasing. This finding is somewhat surprising due to the fact that in general networks additional paths are typically longer than the shortest path. However, in a wireless network, additional paths can be obtained at lower energy due to the broadcast nature of the wireless medium. Finally, we discuss issues regarding distributed implementation and present distributed versions of the optimal centralized algorithms presented in the paper.

REFERENCES

• 1: L. M. Feeney, M. Nilson, "Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment," Proc. 20th IEEE INFOCOM, pp. 1548-1557, 2001
• 2: J. E. Wieselthier, G. D.Nguyen, and A. Ephremides, "On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks," Proc. IEEE INFOCOM 2000, Tel Aviv, Isreal, Mar. 2000, pp. 585-94.
• 3: Andrea E. F. Clementi , Pierluigi Crescenzi , Paolo Penna , Gianluca Rossi , Paola Vocca, On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.121-131, February 15-17, 2001
• 4: Mario Ζagalj , Jean-Pierre Hubaux , Christian Enz, Minimum-energy broadcast in all-wireless networks:: NP-completeness and distribution issues, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570667]
• 5: Weifa Liang, Constructing minimum-energy broadcast trees in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513815]
• 6: A. Ahluwalia, E. Modiano, and L. Shu, "On the Complexity and Distributed Construction of Energy-Efficient Broadcast Trees in Static Ad Hoc Wireless Networks," Proc. 36th Annual Conference on Information Sciences and Systems (CISS 2002), Princeton University, March 2002.
• 7: W. T. Chen and N. F. Huang, "The Strongly Connecting Problem on Multihop Packet Radio Networks," IEEE Transactions on Communications, vol. 37, no. 3, pp. 293-295.
• 8: Errol L. Lloyd , Rui Liu , Madhav V. Marathe , Ram Ramanathan , S. S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513816]
• 9: R. Ramanathan and R. Rosales-Hain. "Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment," Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000, pp. 404--413.
• 10: J. W. Suurballe, "Disjoint Paths in a Network," Networks, 4 (1974) pp. 125-145
• 11: J. W. Suurballe and R.E. Tarjan, "A Quick Method for Finding Shortest Pairs of Disjoint Paths," Networks, 14 (1984) pp. 325-336.
• 12: Ramesh Bhandari, Optimal Physical Diversity Algorithms and Survivable Networks, Proceedings of the 2nd IEEE Symposium on Computers and Communications (ISCC '97), p.433, July 01-03, 1997
• 13: S. J. Lee and M. Gerla, "Split Multipath Routing with Maximally Disjoint Paths in Ad Hoc Networks," Proc. IEEE ICC 2001, pp. 3201-3205, 2001.
• 14: A. Nasipuri and S.R. Das, "On-demand multi-path routing for mobile ad hoc networks," Proc. IEEE ICCCN 1999, pp. 64-70, 1999.
• 15: S. Vutukury and J. J. Garcia-Luna-Aceves, "MDVA: A Distance-Vector Multipath Routing Protocol," Proc. IEEE INFOCOM 2001, pp. 557--564, 2001.
• 16: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 17: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 18: J. E. Wieselthier, G. D.Nguyen, and A. Ephremides, "The Energy Efficiency of Distributed Algorithms for Broadcasting in Ad Hoc Networks," Proc. The 5th International Symposium on Wireless Personal Multimedia Communications, Oct. 2002, pp. 499--503.
• 19: Anand Srinivas, "Reliability and Energy Efficiency in Wireless Ad-Hoc Networks," Master's Thesis, Massachusetts Institute of Technology, 2003.
• 20: Gruia Calinescu , Ion I. Mandoiu , Alexander Zelikovsky, Symmetric Connectivity with Minimum Power Consumption in Radio Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.119-130, August 25-30, 2002
• 21: A. Ephremides, "Energy Concerns in Wireless Networks," IEEE Wireless Communications, Vol. 9, no. 4, 48--59, August 2002.
• 22: Suman Banerjee , Archan Misra, Minimum energy paths for reliable communication in multi-hop wireless networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513818]
• 23: Richard G. Ogier and Nachum Shacham, "A Distributed Algorithm for Finding Shortest Pairs of Disjoint Paths," Proc. IEEE INFOCOM 1989, pp. 173--182
• 24: Deepinder Sidhu , Raj Nair , Shukri Abdallah, Finding disjoint paths in networks, Proceedings of the conference on Communications architecture & protocols, p.43-51, September 03-06, 1991, Zurich, Switzerland
• 25: R. G. Ogier, V. Rutenburg, and N. Shacham, "Distributed algorithms for computing shortest pairs of disjoint paths," IEEE Transaction on Information Theory, vol. 39, no. 2, pp. 443--455, 1993.
• 26: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 27: C. Cheng, S. Kumar, and J.J. Garcia-Luna-Aceves, "An Efficient Distributed Algorithm for Routing over K-Disjoint Paths of Minimum Total Length," Proc. 28th Annual Allerton Conference on Communication, Control, and Computing, Urbana, Illinois, October 1990.
• 28: J.H. Chang and L. Tassiulas, "Energy Conserving Routing in Wireless Ad-hoc Networks", Proc. IEEE INFOCOM 2000, Tel Aviv, Isreal, Mar. 2000.
• 29: R. Wattenhofer, L. Li, P. Bahl and Y. Wang, "Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad-Hoc Networks," Proc. IEEE INFOCOM 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
disjoint paths, distributed algorithms, energy efficiency, minimum energy, multipath routing, wireless ad-hoc networks