Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues

ABSTRACT

In all-wireless networks a crucial problem is to minimize energy consumption, as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. Several authors have conjectured that the problem of power-optimal broadcast is NP-complete. We provide here a formal proof, both for the general case and for the geometric one; in the former case, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. We then describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed.

REFERENCES

• 1: J. Chang and L. Tassiulas. "Energy Conserving Routing in Wireless Ad-hoc Networks". In Proceedings of IEEE INFOCOM 2000. ACM, 2000.
• 2: Andrea E. F. Clementi , Pierluigi Crescenzi , Paolo Penna , Gianluca Rossi , Paola Vocca, On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.121-131, February 15-17, 2001
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: 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]
• 5: O. Egecioglu and T. Gonzalez. Minimum-energy broadcast in simple graphs with limited node power. In Proceedings of IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2001), pages 334--338, Anaheim, CA, August 2001.
• 6: A. Faragó and V. Syrotiuk. Algorithmic problems in power controlled ad hoc networks. In Proceedings of the 14th International Conference on Parallel and Distributed Computing Systems (PDCS 2001), Dalas, Texas, August 2001.
• 7: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: 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
• 10: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 11: J.-P. Hubaux, T. Gross, J.-Y. L. Boudec, and M. Vetterli. Towards self-organized mobile ad hoc networks: the terminodes project. IEEE Communications Magazine, 39(1), January 2001.
• 12: Fulu Li , Ioanis Nikolaidis, On Minimum-Energy Broadcasting in All-Wireless Networks, Proceedings of the 26th Annual IEEE Conference on Local Computer Networks, p.193, November 14-16, 2001
• 13: L. Li, V. Bahl, Y. Wang, and R. Wattenhofer. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In Proceedings of IEEE INFOCOM 2001, April 2001.
• 14: Qun Li , Javed Aslam , Daniela Rus, Online power-aware routing in wireless Ad-hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.97-107, July 2001, Rome, Italy [doi>10.1145/381677.381687]
• 15: Weifa Liang, Constructing minimum-energy broadcast trees in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513815]
• 16: D. Lichtenstein. Planar formulae and their uses. SIAM Journal on Computing, 11(2):329--343, May 1982.
• 17: 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]
• 18: Jan M. Rabaey , M. Josie Ammer , Julio L. da Silva , Danny Patel , Shad Roundy, PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking, Computer, v.33 n.7, p.42-48, July 2000 [doi>10.1109/2.869369]
• 19: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 20: V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. IEEE Journal on Selected Areas in Communications, 17(8), August 1999.
• 21: E. M. Royer and C.-K. Toh. A review of current routing protocols for ad hoc mobile wireless networks. IEEE Personal Communications, 6(2):46--55, April 1999.
• 22: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Optimizing Sensor Networks in the Energy-Latency-Density Design Space, IEEE Transactions on Mobile Computing, v.1 n.1, p.70-80, January 2002 [doi>10.1109/TMC.2002.1011060]
• 23: S. Singh, C. Raghavendra, and J. Stepanek. Power-aware broadcasting in mobile ad hoc networks. In Proceedings of IEEE PIMRC'99, Osaka, Japan, September 1999.
• 24: P.-J. Wan, G. Calinescu, and O. F. X.-Y. Li. Minimum-energy broadcast routing in static ad hoc wireless networks. In IEEE INFOCOM 2001, Anchorage, Alaska, April 2001.
• 25: J. E. Wieselthier, G. D. Nguyen, and A. Ephremides. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In IEEE INFOCOM 2000, pages 586--594, Tel Aviv, Israel, 2000.
• 26: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Algorithms for energy-efficient multicasting in static ad hoc wireless networks, Mobile Networks and Applications, v.6 n.3, p.251-263, June 2001 [doi>10.1023/A:1011478717164]
• 27: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]

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:
broadcast algorithms, distributed algorithms, energy efficiency, minimum-energy networks, wireless ad hoc networks