Clustering-Based Energy-Efficient Broadcast Tree in Wireless Networks

  • Jiguo Yu School of Computer Science, Qufu Normal University, Rizhao, 276826, P.R. China
  • Honglu Jiang School of Computer Science, Qufu Normal University, Rizhao, 276826, P.R. China
  • Guanghui Wang School of Mathematics, Shandong University, Jinan, 250100, P.R. China
  • Qiang Guo Key Laboratory for Computer Networks of Shandong Province Shandong Computer Science Center, Jinan, 250014, P.R. China

Abstract

The characteristics of wireless networks present formidable challenges to the study of broadcasting problem. A crucial issue in wireless networks is the energy consumption, because of the nonlinear attenuation properties of radio signals. Another crucial issue is the trade-off between reaching more nodes in a single hop by using higher power versus reaching fewer nodes in that single hop by using lower power. Given a wireless network with a specified source node that broadcasts messages to all other nodes in the network, the minimum energy broadcast (MEB) problem is NP-hard. In this paper, we propose a hybrid approach CBEEB(clustering-based energy-efficient broadcast) for the MEB problem based on clustering. Theoretical analysis indicates the efficiency and effectiveness of CBEEB. Simulation results show that CBEEB has better performance compared with the existing heuristic approaches.

Author Biography

Jiguo Yu, School of Computer Science, Qufu Normal University, Rizhao, 276826, P.R. China
Department of Mathematics and Computer Science

References

[1] J. E. Wieselthier, G. D. Nguyen, A. Ephremides, On the construction of energy efficient broadcast and multicast trees in wireless networks, in: Proc. of INFOCOM 2000, 585-594, 2000.

[2] S. M. Hashemi, Mohsen Rezapour, Ahmad Moradi, Two new algorithms for the Min-power Broadcast problem in static ad hoc networks, Applied Math. and Compu., Vol.190, pp. 1657-1668, 2007.
http://dx.doi.org/10.1016/j.amc.2007.02.062

[3] A. K. Das, R. J. Marks, M. EI-Sharkawi, P. Arabshi, A. Gray, A cluster-merge algorithm for solving the minimum power broadcast problem in large scale wireless networks, in Proc. of the Milcom conference, 13-16, 2003.

[4] A. K. Das, R. J. Marks, M. EI-Sharkawi, P. Arabshi, A. Gray, The minimum power broadcast problem in wireless networks: a simulated annealing approach, in Proc. of WCNC, 2057-2062, 2005.

[5] P. J. Wan, G. Calinescu, X. Y. Li, O. Frieder, Minimum-energy broadcast routing in static ad hoc wireless networks, in Proc. of INFOCOM, 1162-1171, 2001.

[6] A. K. Das, R. J. Marks, M. EI-Sharkawi, P. Arabshai, A. Gray, r-shrink: a heuristic for improving minimum power broadcast trees in wireless networks, in Proc. of GLOBECOM 523-527, 2003.

[7] M. Cagalj, J. P. Hubaux, C. Enz, Minimum-energy broadcast in all-wireless networks: NPcompleteness and distribution issues, in Proc. of MobiCom'02, 172-182, 2002.

[8] I. Kang, R. Poovendran, Broadcast with heterogeneous node capability, in Proc. of GLOBECOM 4114-4119, 2004.

[9] A. K. Das, R. J. Marks, M. EI-Sharkawi, P. Arabshi, A. Gray, The minimum power broadcast problem in wireless networks: an ant colony system approach, in Proc. of the IEEE CAS Workshop on Wireless Communications and Networking, 5-6, 2002.

[10] I. Kang, R. Poovendran, Iterated local optimization for minimum energy broadcast, in: Proc. of WiOpt, 332-341, 2005.

[11] R. Montemanni, L. M. Gambardella, A. K. Das, The minimum power broadcast in wireless networks: a simulated annealing approach, in Proc. of WCNC, 2057-2062, 2005.

[12] S. Al-Shihabi, P. Merz, S. Wolf, Nested portioning for the minimum energy broadcast problem,in Proc. of LION 2, LNCS 5313, 1-11, 2008.

[13] S. Wolf, P. Merz, Evolutionary local search for the minimum energy broadcast problem,in Proc. of EvoCOP'08, LNCS 4972, 61-72, 2008.

[14] X. Wu, X. Wang, R. Liu, Solving minimum power broadcast problem in wireless ad hoc networks using genetic algorithm,in Proc. of CNSR, 203-207, 2008.

[15] Alok Singh, Wilson Naik Bhukya, A hybrid genetic algorithm for the minimum energy broadcast problem in wireless ad hoc networks, Applied Soft Computing, Vol.11, pp. 667-674, 2011.
http://dx.doi.org/10.1016/j.asoc.2009.12.027
Published
2014-09-16
How to Cite
YU, Jiguo et al. Clustering-Based Energy-Efficient Broadcast Tree in Wireless Networks. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 7, n. 4, p. 785-790, sep. 2014. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/1376>. Date accessed: 16 july 2020. doi: https://doi.org/10.15837/ijccc.2012.4.1376.

Keywords

Wireless Network, Energy-Efficient, Broadcast, Clustering