The week's pick
Reseach Article
Multicast Routing with Minimum Energy Cost in Ad Hoc Wireless Networks
| 2nd National Conference on Innovative Paradigms in Engineering and Technology (NCIPET 2013) |
| Foundation of Computer Science USA |
| NCIPET - Number 12 |
| March 2012 |
| Authors: Abhishek Pandey, Lok Ranjan Das |
| cced7844-a5cb-4938-9165-bc2f4098fa02 |
Abhishek Pandey, Lok Ranjan Das . Multicast Routing with Minimum Energy Cost in Ad Hoc Wireless Networks. 2nd National Conference on Innovative Paradigms in Engineering and Technology (NCIPET 2013). NCIPET, 12 (March 2012), 39-43.
Abstract
In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network and a multicast request, to find a multicast tree such that the total energy cost of the multicast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove the problem is NP-hard, and then propose three heuristic algorithms, namely Steiner tree based heuristic, Node-Join-Tree and Tree-Join-Tree greedy algorithms. Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.
References
- Volkan Rodoplu and Teresa Meng, “Minimum Energy Mobile Wireless Networks”, IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, Aug 1999, pp.1333-1344.
- Ram Ramanathan and Regina Rosales-Hain, “Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment”, IEEE INFOCOM 2000, Tel-Aviv, Mar 2000, pp. 404-413.
- Roger Wattenhofer, Li Li, Paramvir Bahl and Yi-Min Wang, “Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks”, IEEE INFOCOM 2001, Alaska, USA, April, 2001.
- J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “Algorithm for Energy-Efficient Multicasting in Static Ad Hoc Wireless Networks”, Mobile Networks and Applications 6, 2001, pp. 251-263.
- J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks”, IEEE Infocom’2000.
- J. E. Wieselthier, G. D. Nguyen and A. Ephremides, “Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” Mobile Networks and Applications 7, 2002, pp. 481-492.
- P. J. Wan, G. Calinescu, X. Y. Li and O. Frieder, “ Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks”, IEEE Infocom’2001.
- Maggie Xiaoyan Cheng, Jianhua Sun, Manki Min, Ding-Zhu Du, "Energy Efficient Broadcast and Multicast Routing in Ad Hoc Wireless Networks", 22nd IEEE International Performance, Computing, and Communications Conference, Phoenix, Arizona, USA, 2003.
- Omer Egecioglu and Teofilo F. Gonzalez, “Minimum-Energy Broadcast in Simple Graphs with Limited Node Power”, In Proc. IASED International Conference on Parallel and Distributed Computing and Systems (PDCS 2001), Anaheim, CA, August 2001, pp. 334-338.
- M. Cagalj, JP Hubaux, C. Enz, “Minimum-Energy Broadcast in All- wireless Networks: NP-Completeness and Distribution Issues”, MOBICOM’02.
- W. Liang, “Constructing Minimum-Energy Broadcast Trees in Wireless Ad Hoc Networks”, MOBIHOC’02.
- Deying Li, Xiaohua Jia and Hai Liu, “Energy Efficient Broadcast Routing in Ad Hoc Wireless Networks”, IEEE Trans. On Mobile Computing, vol.3, no.1, 2004.
- D. S. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, 1997.
- L. Zosin, S. Khuller, “On Directed Steiner Trees”, Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp.59-63
Index Terms
Keywords