[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

  • Published:
Wireless Networks Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Ahluwalia, E. Modiano and L. Shu, On the complexity and distributed construction of energy-efficient broadcast trees in static ad hoc wireless networks, in: Proc. 36th Annual Conference on Information Sciences and Systems (CISS) (March 2002).

  2. S. Banerjee and A. Misra, Minimum energy paths for reliable communication in multi-hop wireless networks, in: Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (June 2002) pp. 146–156.

  3. D. Bertsekas and R. Gallager, Data Networks (Prentice-Hall Upper Saddle River, NJ, 1992).

    Google Scholar 

  4. R. Bhandari, Optimal physical diversity algorithms and survivable networks, in: Proc. Second IEEE Symposium on Computers and Communications (July 1997) pp. 433–441.

  5. M. Cagali, J.P. Hubaux and C. Enz, Minimum energy broadcast in all-wireless networks: NP-completeness and distribution issues, in: Proc. Ninth ACM International Conference on Mobile Networking and Computing (MOBICOM) (September 2002) pp. 172–182.

  6. G. Calinescu, I.I. Mandoiu and A. Zelikovsky, Symmetric connectivity with minimum power consumption in radio networks, in: Proc. 2nd IFIP International Conference on Theoretical Computer Science (August 2002) pp. 119–130.

  7. J.H. Chang and L. Tassiulas, Energy conserving routing in wireless ad-hoc networks, in: Proc. IEEE INFOCOM (March 2000) pp. 22–31.

  8. W.T. Chen and N.F. Huang, The strongly connecting problem on multihop packet radio networks, IEEE Transactions on Communications 37 (1989) 293–295.

    Article  Google Scholar 

  9. C. Cheng, S. Kumar and J.J. Garcia-Luna-Aceves, An efficient distributed algorithm for routing over k-disjoint paths of minimum total length, in: Proc. 28th Annual Allerton Conference on Communication, Control, and Computing (October 1990).

  10. A.E.F. Clementi, P. Crescenzi, P. Penna and P.V.G. Rossi, On the complexity of computing minimum energy consumption broadcast subgraphs, in: Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (February 2001) pp. 121–131.

  11. A. Ephremides, Energy concerns in wireless networks, IEEE Wireless Communications 9 (August 2002) 48–59.

  12. L.M. Feeney and M. Nilson, Investigating the energy consumption of a wireless network interface in an ad hoc networking environment, in: Proc. IEEE INFOCOM (April 2001) pp. 1548–1557.

  13. S.J. Lee and M. Gerla, split multipath routing with maximally disjoint paths in ad hoc networks, in: Proc. IEEE ICC (June 2001) pp. 3201–3205.

  14. W. Liang, Constructing minimum energy broadcast trees in wireless ad hoc networks, in: Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (June 2002) pp. 112–122.

  15. E. Lloyd, R. Liu, M. Marathe, R. Ramanathan and S.S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks, in: Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (June 2002) pp. 123–134.

  16. A. Nasipuri and S.R. Das, On-demand multi-path routing for mobile ad hoc networks, in: Proc. IEEE ICCCN (October 1999) pp. 64–70.

  17. R.G. Ogier, V. Rutenburg and N. Shacham, Distributed algorithms for computing shortest pairs of disjoint paths, IEEE Transaction on Information Theory 39 (May 1993) 173–182.

    Google Scholar 

  18. Richard G. Ogier and Nachum Shacham, A distributed algorithm for finding shortest pairs of disjoint paths, in: Proc. IEEE INFOCOM (April 1989) pp. 173–182.

  19. R. Ramanathan and R. Rosales-Hain, Topology control of multihop wireless networks using transmit power adjustment, in: Proc. IEEE INFOCOM (March 2000) pp. 404–413.

  20. T.S. Rappaport, Wireless Communications: Principles and Practices (Prentice-Hall Upper Saddle River, NJ, 1996).

    Google Scholar 

  21. D. Sidhu, R. Nair and S. Abdallah, Finding disjoint paths in networks, in: Proc. ACM SIGCOMM (September 1991) pp. 43–51.

  22. S. Singh, M. Woo and C.S. Raghavendra, Power-aware routing in mobile ad hoc networks, in: Proc. Fifth ACM International Conference on Mobile Networking and Computing (MOBICOM) (Oct. 1998) pp. 181–190.

  23. A. Srinivas and E. Modiano, Minimum energy disjoint path routing in wireless ad hoc networks, in: Proc. Ninth ACM International Conference on Mobile Networking and Computing (MOBICOM) (September 2003) pp. 122–133.

  24. J.W. Suurballe, Disjoint paths in a network, Networks 4 (1974) 125–145.

    Google Scholar 

  25. J.W. Suurballe, The single-source, all terminals problem for disjoint paths, Unpublished technical memorandum, Bell Laboratories (1982).

  26. J.W. Suurballe and R.E. Tarjan, A quick method for finding shortest pairs of disjoint paths, Networks 14 (1984) 325–336.

    Google Scholar 

  27. S. Vutukury and J.J. Garcia-Luna-Aceves, MDVA: A distance-vector multipath routing protocol, in: Proc. IEEE INFOCOM (April 2001) pp. 557–564.

  28. R. Wattenhofer, L. Li, P. Bahl and Y. Wang, Distributed topology control for power efficient operation in multihop wireless ad-hoc networks, in: Proc. IEEE INFOCOM (April 2001) pp. 1388–1397.

  29. J.E. Wieselthier, G.D. Nguyen and A. Ephremides, On the construction of energy-efficient broadcast and multicast trees in wireless networks, in: Proc. IEEE INFOCOM (March 2000) pp. 585–594.

  30. J.E. Wieselthier, G.D. Nguyen and A. Ephremides, The energy efficiency of distributed algorithms for broadcasting in ad hoc networks, in: Proc. The 5th International Symposium on Wireless Personal Multimedia Communications (Oct. 2002) pp. 499–503.

Download references

Author information

Authors and Affiliations

  1. Massachusetts Institute of Technology, Cambridge, MA, 02139

    Anand Srinivas & Eytan Modiano

Authors
  1. Anand Srinivas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eytan Modiano
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anand Srinivas.

Additional information

Anand Srinivas is currently a PhD candidate in the Laboratory for Information and Decision Systems (LIDS) at MIT. He recieved his Masters of Science in EECS from MIT in 2004, and his Bachelors of Applied Science in Computer Engineering from the University of Toronto in 2001. In 2004 he also received a Masters of Science in Aerospace Engineering from MIT. His current research interests include reliability and energy-efficiency in wireless ad-hoc networks, routing and network optimization, graph theory, and the design of efficient algorithms. E-mail: anand3@mit.edu

Eytan Modiano received his B.S. degree in Electrical Engineering and Computer Science from the University of Connecticut at Storrs in 1986 and his M.S. and Ph.D. degrees, both in Electrical Engineering, from the University of Maryland, College Park, MD, in 1989 and 1992 respectively. He was a Naval Research Laboratory Fellow between 1987 and 1992 and a National Research Council Post Doctoral Fellow during 1992–1993 while he was conducting research on security and performance issues in distributed network protocols.

Between 1993 and 1999 he was with the Communications Division at MIT Lincoln Laboratory where he designed communication protocols for satellite, wireless, and optical networks and was the project leader for MIT Lincoln Laboratory’s Next Generation Internet (NGI) project. He joined the MIT faculty in 1999, where he is presently an Associate Professor in the Department of Aeronautics and Astronautics and the Laboratory for Information and Decision Systems (LIDS). His research is on communication networks and protocols with emphasis on satellite, wireless, and optical networks.

He is currently an Associate Editor for Communication Networks for IEEE Transactions on Information Theory and for The International Journal of Satellite Communications. He had served as a guest editor for IEEE JSAC special issue on WDM network architectures; the Computer Networks Journal special issue on Broadband Internet Access; the Journal of Communications and Networks special issue on Wireless Ad-Hoc Networks; and for IEEE Journal of Lightwave Technology special issue on Optical Networks. He is the Technical Program co-chair for Wiopt 2006 and vice- chair for Infocom 2007. E-mail: modiano@mit.edu

Rights and permissions

Reprints and permissions

About this article

Cite this article

Srinivas, A., Modiano, E. Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks. Wireless Netw 11, 401–417 (2005). https://doi.org/10.1007/s11276-005-1765-0

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-005-1765-0

Search

Navigation