Online power-aware routing in wireless Ad-hoc networks

ABSTRACT

This paper discusses online power-aware routing in large wireless ad-hoc networks for applications where the message sequence is not known. We seek to optimize the lifetime of the network. We show that online power-aware routing does not have a constant competitive ratio to the off-line optimal algorithm. We develop an approximation algorithm called max-min zPmin that has a good empirical competitive ratio. To ensure scalability, we introduce a second online algorithm for power-aware routing. This hierarchical algorithm is called zone-based routing. Our experiments show that its performance is quite good.

REFERENCES

• 1: Jon Agre , Loren Clare, An Integrated Architecture for Cooperative Sensing Networks, Computer, v.33 n.5, p.106-108, May 2000 [doi>10.1109/2.841788]
• 2: A.D. Amis, R. Prakash, T.H.P. Vuong, and D.T. Huynh. Max-min d-cluster formation in wireless ad hoc networks. In Proceedings IEEE INFOCOM 2000. Conference on Computer Communications, March 2000.
• 3: Jae-Hwan Chang and Leandros Tassiulas. Energy conserving routing in wireless ad-hoc networks. In Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000.
• 4: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 5: Yu Chen , Thomas C. Henderson, S-NETS: Smart Sensor Networks, Experimental Robotics VII, p.81-90, December 11-13, 2000
• 6: Imrich Chlamtac , Chiara Petrioli , Jason Redi, Energy-conserving access protocols for identification networks, IEEE/ACM Transactions on Networking (TON), v.7 n.1, p.51-59, Feb. 1999 [doi>10.1109/90.759318]
• 7: A. Chockalingam and M. Zorzi. Energy efficiency of media access protocols for mobile data networks. IEEE Transactions on Communications, 46(11):1418-21, Nov. 1998.
• 8: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 9: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 10: Laura Maria Feeney and Martin Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In INFOCOM 2001, April 2001.
• 11: M. Gerla, X. Hong, and G. Pei. Landmark routing for large ad hoc wireless networks. In Proceedings of IEEE GLOBECOM 2000, San Francisco, CA, Nov. 2000.
• 12: Piyush Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, pages 547-566, 1998.
• 13: Z. J. Haas. A new routing protocol for the reconfigurable wireless network. In Proceedings of the 1997 IEEE 6th International Conference on Universal Personal Communications, ICUPC'97, pages 562 -566, San Diego, CA, October 1997.
• 14: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 15: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 16: Mario Joa-Ng and I-Tai Lu. A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks. IEEE Journal on Selected Areas in Communications, 17, Aug. 1999.
• 17: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad-hoc wireless networks. In T. Imielinski and H. Korth, editors, Mobile Computing, pages 153 -181. Kluwer Academic Publishers, 1996.
• 18: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 19: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 20: P. Krishna , N. H. Vaidya , M. Chatterjee , D. K. Pradhan, A cluster-based approach for routing in dynamic networks, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.49-64, Apr. 1997 [doi>10.1145/263876.263885]
• 21: Range LAN. http://www.proxim.com/products/rl2/7410.shtml.
• 22: A.B. McDonald and T.F. Znati. A mobility-based framework for adaptive clustering in wireless ad hoc networks. IEEE Journal on Selected Areas in Communications, 17, Aug. 1999.
• 23: Shree Murthy , J. J. Garcia-Luna-Aceves, An efficient routing protocol for wireless networks, Mobile Networks and Applications, v.1 n.2, p.183-197, Oct. 1996 [doi>10.1007/BF01193336]
• 24: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 25: M.R. Pearlman and Z.J. Haas. Determining the optimal configuration for the zone routing protocol. IEEE Journal on Selected Areas in Communications, 17, Aug. 1999.
• 26: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 27: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 28: Ram Ramanathan , Martha Steenstrup, Hierarchically-organized, multihop mobile wireless networks for quality-of-service support, Mobile Networks and Applications, v.3 n.1, p.101-119, June 1998 [doi>10.1023/A:1019148009641]
• 29: Volkan Rodoplu and Teresa H. Meng. Minimum energy mobile wireless networks. In Proc. of the 1998 IEEE International Conference on Communications, ICC'98, volume 3, pages 1633-1639, Atlanda, GA, June 1998.
• 30: Elizabeth Royer and C-K. Toh. A review of current routing protocols for ad hoc mobile wireless networks. In IEEE Personal Communication, volume 6, pages 46 - 55, April 1999.
• 31: 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]
• 32: Adcon Telemetetry. http://www.adcon.com.
• 33: Ya Xu, John Heidemann, and Deborah Estrin. Adaptive energy-conserving routing for multihop ad hoc networks. Research Report 527 USC/Information Sciences Institute, October 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication; Network communications

General Terms:
Algorithms, Design, Experimentation