International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 2, No. 1, 8 Nov. 2010
Cover page and Table of Contents: PDF (size: 201KB)
A Two-Phase Constructive Heuristic for Minimum Energy Broadcasting in Wireless Ad Hoc Networks
Full Text (PDF, 201KB), PP.31-37
Views: 0 Downloads: 0
Author(s)
Index Terms
Static ad hoc network, minimum energy broadcast, heuristics, combinatorial optimization, fuzzy sets
Abstract
Wireless ad hoc networks are usually composed of autonomous nodes, which are powered by batteries only. The energy-efficiency is perhaps one of the most important factors for each operation in terms of networks. Broadcast, for example, is one of the fundamental operations in modern telecom networks. In this paper a broadcast tree, which is rooted at a source and spans all the destination nodes, has been constructed in a way that the total transmission energy consumption is minimized. This paper describes two polynomial-time heuristics for the energy-efficient broadcasting in static ad hoc wireless networks. Both of the developed approaches are on the basis of a fuzzy greedy evaluation function, which prioritize the network nodes. According to the prioritized order of the nodes, each new node is selected for incorporation in the construction of a solution. Computational experiments indicate that our algorithms improve the well-known Broadcast Link-based Minimum Spanning Tree (BLiMST) and Broadcast Least-Unicast-cost (BLU) heuristics. It will be seen that the BLiMST and the BLU methods are a special case of our more general heuristics.
Cite This Paper
Nastaran Rahmani, Kaveh Sheibani, "A Two-Phase Constructive Heuristic for Minimum Energy Broadcasting in Wireless Ad Hoc Networks", International Journal of Computer Network and Information Security(IJCNIS), vol.2, no.1, pp.31-37 , 2010. DOI:10.5815/ijcnis.2010.01.05
Reference
[1] M. Min and A. Chinchuluun. In: M. G. C. Resende and P. M. Pardalos (eds), Handbook of Optimization in Telecommunications. Springer, Berlin, 2006, pp. 493-915.
[2] A. Ephremides, "Energy concerns in wireless networks," IEEE Wireless Communications, vol. 9, no. 4, pp. 48-59, 2002.
[3] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "Algorithms for energy-efficient multicasting in static ad hoc wireless networks," ACM Mobile Networks and Applications (MONET), vol. 6, Issue 3, pp. 251-263, June 2001.
[4] M. Cagalj, J. –P. Hubaux, and C. Enz, "Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues," in Proc. 8th annual international conference on Mobile computing and networking, pp. 172-182, 2002.
[5] A. E. F. Clementi, A. Ferreira, P. Penna, S. Perennes, and R. Silvestri, "The minimum range assignment problem on linear radio networks," in Proc. 8th Annual European Symposium on Algorithms (ESA 2000), pp. 143-154, September 2000.
[6] K. Sheibani, "A fuzzy greedy heuristic for permutation flow-shop scheduling," Journal of the Operational Research Society, vol. 61, pp. 813-818, 2010.
[7] K. Pahlavan and A. Levesque. Wireless Information Networks. Wiley-Interscience, 1995.
[8] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "Energy-efficient broadcast and multicast trees in wireless networks," Mobile Networks and Applications, vol. 7, Issue 6, pp. 481-492, December 2002.
[9] 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, pp. 586-594, Tel Aviv, Israel, 2000.
[10] A. K. Das, R. J. Marks, M. El-Sharkawi, P. Arabshahi, and A. Gray, "A cluster-merge algorithm for solving the minimum power broadcast problem in large scale wireless networks," MILCOM 2003, IEEE, vol. 1, pp. 416-421, October 2003.
[11] V. Rodoplu and T. H. Meng, "Minimum energy mobile wireless networks," IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1333-1344, Aug. 1999.
[12] R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless networks using transmit power adjustment," Proc. IEEE INFOCOM 2000, pp. 404-413, Mar. 2000.
[13] R. Wattenhofer, L. Li, P. Bahl, and Y. M. Wang, "Distributed topology control for power efficient operations in multihop wireless ad hoc networks," Proc. IEEE INFOCOM , April 2001.
[14] S. Singh, C. S. Raghavendra, and J. Stepanek, "Power-aware broadcasting in mobile ad hoc networks," Proc. IEEE 10th Int'l Symp. Personal Indoor and Mobile Radio Comm., Sept. 1999.
[15] W. Lou and J. Wu, "Efficient broadcast with forward node set in clustered mobile ad hoc networks," Proc. IEEE 11th Conf. Computer Comm. and Networks, pp. 398-403, October 2002.
[16] J. Wu, "Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links," IEEE Trans. Parallel and Distributed Systems, vol. 13, pp. 866-881, 2002.
[17] P.–J. Wan, G. Calinescu, X. Li, O. Frieder, "Minimum-energy broadcast routing in static ad hoc wireless networks," Wireless Networks, vol. 8, pp. 607-617, 2002.
[18] M. X. Cheng, J. Sun, M. Min, and D.-Z. Du, "Energy efficient broadcast and multicast routing in ad hoc wireless networks," Proc. 22nd IEEE Int'l Performance, Computing, and Comm. Conf., 2003.
[19] E. W. Dijkstra, "A note on two problems in connection with graphs," Numerische Mathematik, vol. 1, pp. 269-271, 1959.
[20] R. C. Prim, "Shortest connection networks and some generalizations," Bell System Technical Journal, vol. 36, pp. 1389-1401, 1957.
[21] I. Kang, and R. Poovendran, "A novel power-efficient broadcast routing algorithm exploiting broadcast efficiency," Vehicular Technology Conference 2003, vol. 5, pp. 2926-2930, October 2003.
[22] M. X. Cheng, J. Sun, M. Min, Y. Li, and W. Wu, "Energy-efficient broadcast and multicast routing in multihop ad hoc wireless networks," Wireless Communications and Mobile Computing, vol. 6. pp. 213-223, 2006.
[23] M. Min and P. M. Pardalos, "OMEGa: an optimistic most energy gain method for minimum energy multicasting inwireless ad hoc networks," J. Comb. Optim., vol. 16, no. 1, pp. 81-95, 2008.
[24] O. Egecioglu and T. F. Gonzalez, "Minimum-energy broadcast in simple graphs with limited node power," Proc. IASED Int'l Conf. Parallel and Distributed Computing and Systems (PDCS'01), pp. 334-338, Aug. 2001.
[25] W. Liang, "Constructing minimum-energy broadcast trees in wireless ad hoc networks," Proc. MOBIHOC '02, 2002.
[26] F. Li, and I. Nikolaidis, "On minimum-energy broadcasting in all wireless networks," IEEE Conference on Local Computer Networks, pp. 14-16, Tampa, November 2001.
[27] S. Guo and O. Yang, "A dynamic multicast tree reconstruction algorithm for minimum energy multicasting in wireless ad hoc networks," IEEE IPCCC, pp. 637-642, Phoenix, USA, 2004.
[28] M. Min and P. M. Pardalos, "Total energy optimal multicasting in wireless ad hoc networks," J. Comb. Optim., vol. 13, no. 4, pp. 365-378, 2007.
[29] A. K. Das, R. J. Marks, M. El-Sharkawi, P. Arabshahi, and A. Gray, "r-shrink: A heuristic for improving minimum power broadcast trees in wireless networks," IEEE GLOBECOM, pp. 523-527, December 2003.
[30] I. Kang, and R. Poovendran, "Broadcast with heterogeneous node capability," IEEE GLOBECOM, pp. 4114-4119-527, December 2004.
[31] M. Min, "Iterated Algorithms for the Minimum Energy Broadcast Tree Problem in Wireless Ad Hoc Networks," Proc. International Conference on Wireless Algorithms, Systems and Applications (WASA 2007), pp. 260-268, 2007.
[32] S. Guo and O. W. W. Yang, "Energy-aware multicasting in wireless ad hoc networks: A survey and discussion," Computer Communications, vol. 30, Issue 9, pp. 2129-2148, June 2007.
[33] N. Rahmani and K. Sheibani, "A heuristic for energy-efficient broadcasting in static ad hoc wireless networks," Proceedings of the 2nd IEEE International Symposium on Computer Network and Multimedia Technology, Wuhan, China, 2010.
[34] K. Sheibani, “Fuzzy greedy evaluation in search, optimisation, and learning,” PhD dissertation, London Metropolitan University, London, UK, 2005.
[35] K. Sheibani, "Fuzzy greedy search in combinatorial optimisation," Tadbir Institute for Operational Research, Systems Design and Financial Services: Tehran, 2008.