Maximum flow-life curve for a wireless ad hoc network

ABSTRACT

This paper proposes a new power aware routing objective for an ad hoc network of battery-limited wireless nodes---the maximum flow-life curve --- that maximizes the traffic flow utility over time. The objective improves upon related objectives such as minimizing the total power or maximizing the time to network partition. To find a routing that maximizes the flow-life curve, we prove an equivalence with a simpler problem and present an algorithm based on linear programming. The efficiency and fairness of the objective are demonstrated on several examples

REFERENCES

• 1: T.X Brown, "Low power wireless communication via reinforcement learning, Advances in NIPS 12, S.A. Solla and T.K. Leen and K.-R. Miiller eds., MIT Press, 2000, pp. 893-899.
• 2: T.X Brown, S. Doshi, and Q. Zhang, "Optimal Power Aware Routing in a Wireless Ad Hoc Network, " LANMAN 2001: 11th IEEE Workshop on Local and Metropolitan Area Networks, pp 102-105, March 2000.
• 3: J.H. Chang and L. Tassiulas, "Routing for Maximum System Lifetime in Wireless Ad Hoc Networks," Proceedings of 37th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, September 1999.
• 4: J.H. Chang and L. Tassiulas, "Energy Conserving Routing in Wireless Ad Hoc Networks," Proceedings of IEEE INFOCOM 2000, pp. 22-31, 2000
• 5: V., Chvatal, Linear Programming, W.H. Freeman and Co., New York, 1983.
• 6: C. Elliot, B. Heile, "Self-Organizing, Self-Healing Wireless Networks," Proc. IEEE Int. Conf. on Personal Wireless Communication, pp. 355-362, 2000.
• 7: D. Johnson and D. Maltz, Dynamic source routing in ad hoc wireless networks," Mobile computing, pp. 153-181 1996.
• 8: Paul Lettieri , Curt Schurgers , Mani Srivastava, Adaptive link layer strategies for energy efficient wireless networking, Wireless Networks, v.5 n.5, p.339-355, Oct. 1999 [doi>10.1023/A:1019123700246]
• 9: 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]
• 10: M. Perkins, ed., Ad Hoc Networking, Addison Wesley, Upper Saddle River, NJ. 370p.
• 11: R. Ramanathan, R. Rosales-Hain, "Topology control of Multihop Wireless Networks using transmit power adjustment," IEEE INFOCOM 2000 pp. 404-413.
• 12: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 13: V. Rodoplu and T.H. Meng, "Minimum energy mobile wireless networks," IEEE JSAC, v. 17, n. 8, pp. 1333-44, Aug. 1999.
• 14: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 15: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 16: 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]
• 17: K.M. Sivalingam, M.B. Srivastava, P. Agrawal, Low-power link and access protocols for wireless multimedia networks," Proc. of IEEE Vehicular Technology Conference, Phoenix, AZ, May, 1997.
• 18: M.W. Subbarao, "Dynamic Power-Conscious Routing for MANETs: An Initial Approach," Proc. IEEE VTC, Amsterdam, The Netherlands, Sept. 1999.

INDEX TERMS

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

Additional Classification:
  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
          Subjects: Network problems

General Terms:
Algorithms, Performance, Theory, Verification