Constructing minimum-energy broadcast trees in wireless ad hoc networks

ABSTRACT

In this paper we assume that a multihop wireless network (also called a wireless ad hoc network) consists of nodes whose transmitting powers are finitely adjustable. We consider two fundamental problems related to power consumption in this kind of network. One is the minimum-energy broadcast tree problem, which broadcasts a message from a source node to all the other nodes in the network such that the summation of transmission powers at all nodes is minimized; and another is the minimum-energy multicast tree problem, which multicasts a message from a source node to the nodes in a given subset of nodes such that the summation of the transmission powers at all involved nodes is minimized.We first show the minimum-energy broadcast tree problem is NP-complete. We then present an approximate algorithm for the problem in a general setting, which delivers an approximate solution with a bounded performance guarantee. The algorithm takes O((k+1)^1/&egr;n^3/&egr; time, where n is the number of nodes in the wireless network, k is the number of power levels at each node, and &egr; is constant with 0⁢&egr;&xie; 1. For a special case of the problem where every node is equipped with the same type of battery, we propose an approximate algorithm which has a better performance ratio than that in the general case setting, and the algorithm takes O(kn² log n) time. We finally extend the technique for the minimum-energy broadcast tree problem to solve the minimum-energy multicast tree problem, which leads to a similar result. The technique adopted in this paper is to reduce the minimum-energy broadcast (multicast) tree problem on a wireless ad hoc network to an optimization problem on an auxiliary weighted graph, and solve the optimization problem on the auxiliary graph which in turn gives an approximate solution for the original problem.

REFERENCES

• 1: D. J. Baker and A. Ephremides. The architectural organization of a mobile radio network via distributed algorithm. IEEE Trans. Commun, Vol. COM-29, pp. 56--73, 1981.
• 2: Jae-Hwan Chang , Leandros Tassiulas, Fast Approximate Algorithms for Maximum Lifetime Routing in Wireless Ad-hoc Networks, Proceedings of the IFIP-TC6 / European Commission International Conference on Broadband Communications, High Performance Networking, and Performance of Communication Networks, p.702-713, May 14-19, 2000
• 3: Imrich Chlamtac , András Faragó, A new approach to the design and analysis of peer-to-peer mobile networks, Wireless Networks, v.5 n.3, p.149-156, May 1999 [doi>10.1023/A:1019186624837]
• 4: V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, Vol. 4(3), pp. 233--235, 1979.
• 5: Moses Charikar , Chandra Chekuri, Approximation algorithms for directed Steiner problems, Journal of Algorithms, v.33 n.1, p.73-91, Oct. 1999 [doi>10.1006/jagm.1999.1042]
• 6: Ching-Chuan Chiang , Mario Gerla , Lixia Zhang, Forwarding Group Multicast Protocol (FGMP) for multihop, mobile wireless networks, Cluster Computing, v.1 n.2, p.187-196, 1998 [doi>10.1023/A:1019037500012]
• 7: A. Ephremides, J. E. Wieselthier, and D. J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling. Proceedings of the IEEE, Vol. 75, pp. 56--58, 1987.
• 8: A. Farago, I. Chlamtac, and S. Bassagni. Virtual path network topology optimization using random graphs. Proc. of INFOCOM'99, pp. 491--496, 1999.
• 9: J.J. Garcia-Luna-Aceves and E. L. Madruga. A Multicast routing protocol for ad-hoc networks. Proc. of INFOCOM'99, New York, 1999.
• 10: S. Khanna and K. Kumaran. On wireless spectrum estimation and generalized graph coloring. Proc. of INFOCOM'98, pp. 1273--1283, 1998.
• 11: Sung-Ju Lee , Mario Gerla, Routing and multicasting strategies in wireless mobile ad hoc networks, 2000
• 12: Márton Nagy , Suresh Singh, Multicast scheduling algorithms in mobile networks, Cluster Computing, v.1 n.2, p.177-185, 1998 [doi>10.1023/A:1019085415942]
• 13: Kia Makki , Niki Pissinou , Ophir Frieder, Efficient solutions to multicast routing in communication networks, Mobile Networks and Applications, v.1 n.2, p.221-232, Oct. 1996 [doi>10.1007/BF01193338]
• 14: C. Perkins and E. M. Royer. Ad Hoc on Demand Distance Vector (AODV) routing. Internet Draft, http://www.ietf.org/internet-drafts/draft--ietf--manet--aodv--01.txt, Aug., 1998.
• 15: R. Ramanathan and R. Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. Proc. of INFOCOM'00, 2000.
• 16: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 17: V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. Proc. of ICC'98, Vol. 3, pp. 1633--1639, 1998.
• 18: 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]
• 19: J.E. Wieselthier, G. D Nguyen and A. Ephremides. On construction of energy-efficient broadcast and multicast trees in wireless networks. Proc. of INFOCOM'00, 2000.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Performance

Keywords:
ad hoc networks, approximate algorithm, broadcast and multicast algorithm, energy consumption optimization, power awareness, wireless network