Article

Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas

Authors:

Ariel Orda,

Ben-Ami YassourAuthors Info & Claims

MobiHoc '05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing

Pages 426 - 437

https://doi.org/10.1145/1062689.1062742

Published: 25 May 2005 Publication History

Get Access

Abstract

A major problem in wireless networks is how to route either broadcast, unicast or multicast traffic so as to maximize the lifetime, i.e., the time until the battery of a transmitting node drains out. Focusing on the fundamental single-session problem, our solution approach is based on the employment of multi-topology routing schemes. Such a scheme consists of a set of routing topologies, which are employed sequentially, for some prescribed duration times.First, we consider the standard wireless environment of multiple recipients, which correspond to omnidirectional antennas. For the cases of either single-topology schemes or unicast sessions, we establish optimal solutions of polynomial complexity. For the general (multi-topology) cases of broadcast and multicast, which are NP-hard, we derive a novel heuristic scheme, and demonstrate its efficiency by way of simulations.We then consider an alternative, single-recipient wireless environment, which corresponds to the important case of directional antennas. While the employment of directional antennas is known to posses significant advantages over the traditional omnidirectional transmission, the problem of lifetime maximization under this environment has received only limited attention.We demonstrate that the change from the traditional (multiple-recipients) environment to the single-recipient environment is of major significance in terms of computational complexity and produces an interesting twist of difficulty: namely, for the standard model, the single-topology broadcast problem is computationally solvable and the multi-topology problem is NP-hard, while the opposite holds for the single-recipient model. Finally, we discuss the extension of our results to the case of multiple sessions.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Networks Flows. Prentice-Hall, New Jersey, 1993.

Google Scholar

[2]

A. Borodin and R. El-Yaniv. Online computation and competitive analysis. Cambridge University Press, New York, NY, USA, 1998.

Digital Library

Google Scholar

[3]

M. Cagalj, J. Hubaux, and C. Enz. Minimum-Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues. In Proceedings of ACM MobiCom, Atlanta, Georgia,USA, September 2002.

Digital Library

Google Scholar

[4]

G. Calinescu, S. Kapoor, A. Olshevsky, and A. Zelikovsky. Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks. In Proceedings of ESA'03, 2003.

Crossref

Google Scholar

[5]

J. Chang and L. Tassiulas. Energy conserving routing in wireless ad-hoc networks. In Proceedings IEEE Infocom, Tel Aviv, Israel, March 2000.

Google Scholar

[6]

M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li. Approximation Algorithms for Directed Steiner Problems. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 192--200, San Francisco, California, January 1998.

Digital Library

Google Scholar

[7]

R. R. Choudhury and N. H. Vaidya. Performance of Ad Hoc Routing using Directional Antennas. Journal of Ad Hoc Networks, 2004.

Google Scholar

[8]

T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT press, Cambridge, 2nd edition, 1990.

Digital Library

Google Scholar

[9]

J. Edmonds. Edge-disjoint branchings. Combinatorial Algorithms, R. Rustin ed. Algorithmics Press, pages 91--96, 1972.

Google Scholar

[10]

D. Estrin, R. Govindan, J. Heidemann, and S. Kumar. Next century challenges: Scalable coordination in sensor networks. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, pages 263--270, Seattle, Washington, USA, August 1999.

Digital Library

Google Scholar

[11]

P. Floren, P. Kaski, J. Kohonen, and P. Orponen. Multicast time maximization in energy constrained wireless networks. In Proceedings of the 2003 joint workshop on Foundations of mobile computing, San Diego, CA, USA, September 2003.

Digital Library

Google Scholar

[12]

H. N. Gabow and K. S. Manu. Packing algorithms for arborescences (and spanning trees) in capacitated graphs. Math. Program., 82:83--109, 1998.

Crossref

Google Scholar

[13]

M. Garey and D. Johnson. Computers and Intractability. Freeman, San Francisco, 1979.

Digital Library

Google Scholar

[14]

N. Garg and J. Konemann. Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems. FOCS, 1997.

Digital Library

Google Scholar

[15]

A. V. Goldberg and R. E. Tarjan. A New Approach to the Maximum Flow Problem. Journal of the ACM, 35:921--940, 1988.

Digital Library

Google Scholar

[16]

W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of Hawaii International Conference on System Sciences, Maui, Hawaii, January 2000.

Digital Library

Google Scholar

[17]

C. Hu, Y. Hong, and J. Hou. On Mitigating the Broadcast Storm Problem with Directional Antennas. In Proceedings of IEEE ICC'03, 2003.

Google Scholar

[18]

I. Kang and R. Poovendran. Maximizing Network Lifetime of Broadcasting Over Wireless Stationary Adhoc Networks. In Proceedings of IEEE International Conference on Communications (ICC), Anchorage, Alaska, USA, May 2003.

Google Scholar

[19]

L. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc. Power consumption in packet radio networks. In Proceedings of 14th Symp. on Theoretical Computer Science (STACS'97), ser. Lecture Notes in Computer Science, R. Reischuk and M. Morvan, Eds., volume 1200, pages 363--374, Berlin, Germany, February 1997.

Digital Library

Google Scholar

[20]

T. Moscibroda and R. Wattenhofer. Maximizing the Lifetime of Dominating Sets. In Proceedings of WMAN, 2005.

Digital Library

Google Scholar

[21]

G. Nemhauser and L. A.Wolsey. Integer and Combinatorial Optimization. A Wiley-Interscience Publications, New York, NY, USA, 1988.

Digital Library

Google Scholar

[22]

A. Orda and B. Yassour. Maximum-lifetime routing algorithms for wireless networks. CCIT Pub. No. 493, Dept. of Electrical Engineering, Technion, June 2004. Available from: ftp://ftp.technion.ac.il/pub/supported/ee/Network/oy04.pdf.

Google Scholar

[23]

V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. IEEE Journal on Selected Areas in Communications, 17:1333--1344, August 1999.

Digital Library

Google Scholar

[24]

K. Wang, J. G. Proakis, and R. R. Rao. Energy-Efficient Routing Algorithms Using Directional Antennas for Mobile Ad Hoc Networks. International Journal of Wireless Information Networks, 9:83--109, 2002.

Crossref

Google Scholar

[25]

J. Wieselthier, G. Nguyen, and A. Ephremides. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proceedings of IEEE Infocom, pages 585--594, Tel Aviv, Israel, March 2000.

Crossref

Google Scholar

[26]

J. E. Wieselthier, G. D. Nguyen, and A. Ephremides. Energy-Aware Wireless Networking with Directional Antennas: The Case of Session-Based Broadcasting and Multicasting. IEEE Transactions on Mobile Computing, 1, 2002.

Digital Library

Google Scholar

Cited By

View all

Lin HChen W(2017)An Approximation Algorithm for the Maximum-Lifetime Data Aggregation Tree Problem in Wireless Sensor NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2017.268844216:6(3787-3798)Online publication date: Jun-2017
https://doi.org/10.1109/TWC.2017.2688442
Zhu X(2016)Lifetime maximization of connected differentiated target coverage in energy harvesting directional sensor networks2016 IEEE Online Conference on Green Communications (OnlineGreenComm)10.1109/OnlineGreenCom.2016.7805401(21-26)Online publication date: Nov-2016
https://doi.org/10.1109/OnlineGreenCom.2016.7805401
Han KHu ZLuo JXiang L(2015)RUSH: Routing and scheduling for hybrid data center networks2015 IEEE Conference on Computer Communications (INFOCOM)10.1109/INFOCOM.2015.7218407(415-423)Online publication date: Apr-2015
https://doi.org/10.1109/INFOCOM.2015.7218407
Show More Cited By

Index Terms

Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols
  2. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

A location prediction based routing protocol and its extensions for multicast and multi-path routing in mobile ad hoc networks

This paper discusses a new location prediction based routing (LPBR) protocol for mobile ad hoc networks (MANETs) and its extensions for multicast and multi-path routing. The objective of the LPBR protocol is to simultaneously minimize the number of ...
Investigating upper bounds on lifetime for target tracking sensor networks

The distinctive characteristic of target tracking sensor networks is that the delay of data transmission is constrained, which poses a difficult problem for predicting the application lifetime for such sensor networks. In this paper, we first map the ...
Extended Lifetime Routing in Wireless Sensor Network
GIT4NDM '13: Proceedings of the 2013 Fifth International Conference on Geo-Information Technologies for Natural Disaster Management

A Wireless Sensor Network (WSN) consists of some wireless nodes which are known with these characteristics: small size and constrained energy source. Considering the energy constraints of nodes in Wireless Sensor Networks (WSNs), routing by efficient ...

Reviews

Reviewer: Ami Marowka

This paper presents a broad theoretical analysis of power-aware routing algorithms in wireless networks that maximize their lifetime. The complexity analysis is done for omnidirectional-based (multiple recipients model) and directional-based (single recipient model) networks. Each model is analyzed for the static (single topology) and dynamic (multiple topologies) cases. The unicast, broadcast, and multicast routing schemes are analyzed for the cases of single and multiple sessions. It is very hard to follow all of the details and assumptions in a single reading of the paper. This is the first paper, as far as I know, that defines the lifetime of a network accurately (up to the time the battery of a transmitting node drains out and inhibits a routing to be completed) and establishes a comprehensive algorithmic methodology for maximizing lifetime in wireless networks. Most of the findings are not surprising, such as the proofs that multicast and broadcast problems are nondeterministic polynomial-time (NP) hard in the case of multiple topologies/multiple recipients, and have optimal solutions in the case of a single topology/single recipient. For multiple topology broadcast and multicast problems, the authors introduce a novel heuristic scheme. However, it is surprising to discover that for a directional-based antenna network, the broadcast problem has an optimal solution in the case of multiple topologies, while it is shown to be NP-hard in the case of the multicast problem. The findings in this paper and those that appear in the extended technical report are important and deserve a survey paper. However, the algorithms analyzed in this paper are centralized solutions, and thus have important theoretical results; for practical use, distributed solutions are more appropriate. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MobiHoc '05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing

May 2005

470 pages

ISBN:1595930043

DOI:10.1145/1062689

General Chair:
P. R. Kumar
University of Illinois at Urbana-Champaign, Urbana, IL
,
Program Chairs:
Andrew T. Campbell
Columbia University
,
Rogert Wattenhofer
ETH Zurich, Switzerland

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MobiHoc05

Sponsor:

MobiHoc05: The Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing 2005

May 25 - 27, 2005

IL, Urbana-Champaign, USA

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
929
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lin HChen W(2017)An Approximation Algorithm for the Maximum-Lifetime Data Aggregation Tree Problem in Wireless Sensor NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2017.268844216:6(3787-3798)Online publication date: Jun-2017
https://doi.org/10.1109/TWC.2017.2688442
Zhu X(2016)Lifetime maximization of connected differentiated target coverage in energy harvesting directional sensor networks2016 IEEE Online Conference on Green Communications (OnlineGreenComm)10.1109/OnlineGreenCom.2016.7805401(21-26)Online publication date: Nov-2016
https://doi.org/10.1109/OnlineGreenCom.2016.7805401
Han KHu ZLuo JXiang L(2015)RUSH: Routing and scheduling for hybrid data center networks2015 IEEE Conference on Computer Communications (INFOCOM)10.1109/INFOCOM.2015.7218407(415-423)Online publication date: Apr-2015
https://doi.org/10.1109/INFOCOM.2015.7218407
Xu XSong M(2015)Delay Efficient Real-Time Multicast Scheduling in Multi-Hop Wireless Sensor Networks2015 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2015.7417418(1-6)Online publication date: Dec-2015
https://doi.org/10.1109/GLOCOM.2015.7417418
Xu XSong M(2014)Delay Efficient Real-Time Multicast Scheduling in Multi-Hop Wireless Sensor Networks2015 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2014.7417418(1-6)Online publication date: Dec-2014
https://doi.org/10.1109/GLOCOM.2014.7417418
Xu KWang FJia X(2014)Secure the Internet, One Home at a Time2015 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2014.7417086(1-6)Online publication date: Dec-2014
https://doi.org/10.1109/GLOCOM.2014.7417086
Li HSun ZLu K(2014)Real-Time Tracking for Moving Target in WSN with Uncovered HolesHuman Behavior Understanding in Networked Sensing10.1007/978-3-319-10807-0_4(75-97)Online publication date: 7-Nov-2014
https://doi.org/10.1007/978-3-319-10807-0_4
Sun ZLi H(2013)Using Directional Antenna for Continuous Moving Object Tracking in WSN with Uncovered HolesProceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems Workshops10.1109/ICDCSW.2013.23(274-279)Online publication date: 8-Jul-2013
https://dl.acm.org/doi/10.1109/ICDCSW.2013.23
Nunes BBarboza FAssis F(2013)Maximum Lifetime Broadcast in Mobile Sensor NetworksAd-hoc, Mobile, and Wireless Network10.1007/978-3-642-39247-4_3(26-37)Online publication date: 2013
https://doi.org/10.1007/978-3-642-39247-4_3
Nutov ZSegal M(2012)Improved approximation algorithms for maximum lifetime problems in wireless networksTheoretical Computer Science10.1016/j.tcs.2011.08.001453(88-97)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1016/j.tcs.2011.08.001
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A location prediction based routing protocol and its extensions for multicast and multi-path routing in mobile ad hoc networks

Investigating upper bounds on lifetime for target tracking sensor networks

Extended Lifetime Routing in Wireless Sensor Network

Reviews

Access critical reviews of Computing literature here