Anand Srinivas
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.
- 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]]Google Scholar
- 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.]]Google ScholarCross Ref
- A. E. F. Clementi, P. Crescenzi, P. Penna, and P. V. G. Rossi, "On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs," Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science, volume 2010 of LNCS, pp. 121-131, 2001.]] Google ScholarDigital Library
- M. Cagali, J.P. Hubaux, C. Enz, "Minimum Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues," In The Eighth ACM International Conference on Mobile Networking and Computing (MOBICOM), Atlanta, September 2002.]] Google ScholarDigital Library
- W. Liang, "Constructing minimum energy broadcast trees in wireless ad hoc networks," Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Lausanne, Switzerland, June 2002.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google ScholarCross Ref
- E. Lloyd, R. Liu, M. Marathe, R. Ramanathan, and S.S. Ravi, "Algorithmic Aspects of Topology Control Problems for Ad hoc Networks," Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Lausanne, Switzerland, June 2002.]] Google ScholarDigital Library
- 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.]]Google Scholar
- J. W. Suurballe, "Disjoint Paths in a Network," Networks, 4 (1974) pp. 125-145]]Google ScholarCross Ref
- J. W. Suurballe and R.E. Tarjan, "A Quick Method for Finding Shortest Pairs of Disjoint Paths," Networks, 14 (1984) pp. 325-336.]]Google ScholarCross Ref
- R. Bhandari, "Optimal physical diversity algorithms and survivable networks," Proc. Second IEEE Symposium on Computers and Communications 1997 , Alexandria, Egypt, July 1997, pp. 433--441.]] Google ScholarDigital Library
- 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.]]Google Scholar
- A. Nasipuri and S.R. Das, "On-demand multi-path routing for mobile ad hoc networks," Proc. IEEE ICCCN 1999, pp. 64-70, 1999.]]Google Scholar
- S. Vutukury and J. J. Garcia-Luna-Aceves, "MDVA: A Distance-Vector Multipath Routing Protocol," Proc. IEEE INFOCOM 2001, pp. 557--564, 2001.]]Google ScholarCross Ref
- T.S. Rappaport, Wireless Communications: Principles and Practices, Prentice Hall, 1996.]] Google ScholarDigital Library
- S. Singh, M. Woo and C.S. Raghavendra, "Power-Aware Routing in Mobile Ad Hoc Networks," Proc. ACM MOBICOM 1998, Oct. 1998, pp. 181-190.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- Anand Srinivas, "Reliability and Energy Efficiency in Wireless Ad-Hoc Networks," Master's Thesis, Massachusetts Institute of Technology, 2003.]]Google Scholar
- G. Calinescu, I.I. Mandoiu, and A. Zelikovsky, "Symmetric Connectivity with Minimum Power Consumption in Radio Networks", Proc. 2nd IFIP International Conference on Theoretical Computer Science,Montreal, Canada, August 2002.]] Google ScholarDigital Library
- A. Ephremides, "Energy Concerns in Wireless Networks," IEEE Wireless Communications, Vol. 9, no. 4, 48--59, August 2002.]]Google ScholarDigital Library
- S. Banerjee and A. Misra, "Minimum energy Paths for Reliable Communication in Multi-Hop Wireless Networks," Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Lausanne, Switzerland, June 2002.]] Google ScholarDigital Library
- Richard G. Ogier and Nachum Shacham, "A Distributed Algorithm for Finding Shortest Pairs of Disjoint Paths," Proc. IEEE INFOCOM 1989, pp. 173--182]]Google Scholar
- D. Sidhu, R. Nair, and S. Abdallah, "Finding Disjoint Paths in Networks," Proc. ACM SIGCOMM 1991, pp. 43-51, 1991.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- D. Bertsekas and R. Gallager, Data Networks, Prentice Hall, 1992.]] Google ScholarDigital Library
- 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.]]Google Scholar
- J.H. Chang and L. Tassiulas, "Energy Conserving Routing in Wireless Ad-hoc Networks", Proc. IEEE INFOCOM 2000, Tel Aviv, Isreal, Mar. 2000.]]Google Scholar
- 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.]]Google ScholarCross Ref
Index Terms
- Minimum energy disjoint path routing in wireless ad-hoc networks
Recommendations
Finding minimum energy disjoint paths in wireless ad-hoc networks
Special issue: Selected papers from ACM MobiCom 2003We 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 ...
Mitigating path diminution in disjoint multipath routing for mobile ad hoc networks
Design of a disjoint multipath routing protocol in an ad hoc environment is a challenging task. In this paper, we propose a protocol named Vertex Disjoint Multipath Routing (VDMR) to discover multiple node disjoint paths between a given pair of nodes. A ...
Path diminution in node-disjoint multipath routing for mobile ad hoc networks is unavoidable with single route discovery
In an ad hoc network, identification of all node-disjoint paths between a given pair of nodes is a challenging task. The phenomena that a protocol is not able to identify all node-disjoint paths that exist between a given pair of nodes is called path ...
Comments