Abstract
In wireless ad-hoc networks, nodes are generally equipped with batteries, making energy a scarce resource. Therefore, power consumption of network operations is critical and subject to optimization. One of the fundamental problems in ad-hoc networks is broadcasting. In this work we consider the so-called minimum energy broadcast (MEB) problem, which can be stated as a combinatorial optimization problem. We develop an ant colony optimization algorithm for two scenarios: networks in which nodes are equipped with omni-directional, respectively directional, antennas. The results show that our algorithm consistently outperforms other methods for this problem.
This work was supported by grants TIN2005-08818 (OPLINK) and TIN2007-66523 (FORMALISM) of the Spanish government, and by the EU project FRONTS (FP7-ICT-2007-1). Christian Blum acknowledges support from the Ramón y Cajal program of the Spanish Ministry of Science and Technology, whereas Guillem Francès acknowledges support from a UPC research grant.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rapport, T.: Wireless Communications: Principles and Practices. Prentice Hall, Englewood Cliffs (1996)
Wieselthier, J.E., Nguyen, G.D., Ephremides, A.: Energy-aware wireless networking with directional antennas: the case of session-based broadcasting and multicasting. IEEE Trans. on Mobile Computing 1(3), 176–191 (2002)
Cagalj, M., Hubaux, J.P., Enz, C.: Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues. In: Proc. of ACM MobiCom, pp. 172–182. ACM press, New York (2002)
Wieselthier, J.E., Nguyen, G.D., Ephremides, A.: On the construction of energy-efficient broadcast and multicast trees in wireless networks. Proc. of INFOCOM 2000 2, 585–594 (2000)
Wan, P.J., Calinescu, G., Li, X.Y., Frieder, O.: Minimum-energy broadcast routing in static ad hoc wirless networks. ACM Wireless Networks 8(6), 607–617 (2002)
Liang, W.: Constructing minimum-energy broadcast trees in wireless ad hoc networks. In: Proc. of ACM MobiHoc 2002, pp. 112–122. ACM press, New York (2002)
Li, F., Nikolaidis, I.: On minimum-energy broadcasting in all-wireless networks. In: Proc. of IEEE LCN, pp. 14–16. IEEE press, Los Alamitos (2001)
Guo, S., Yang, O.: A dynamic multicast tree reconstruction algorithm for minimum-energy multicasting in wireless ad hoc networks. In: Proc. of IEEE IPCCC, pp. 637–642. IEEE press, Los Alamitos (2004)
Das, A.K., Marks, R.J., El-Sharkawi, M., Arabshahi, P., Gray, A.: r-shrink: A heuristic for improving minimum power broadcast trees in wireless networks. In: Proc. of GLOBECOM 2003, pp. 523–527. IEEE press, Los Alamitos (2003)
Das, A.K., Marks, R.J., El-Sharkawi, M., Arabshahi, P., Gray, A.: The minimum power broadcast problem in wireless networks: an ant colony system approach. In: Proc. of the IEEE CAS Wshp. on Wireless Communications and Networking (2002)
Kang, I., Poovendran, R.: Iterated local optimization for minimum energy broadcast. In: Proc. of WiOpt 2005, pp. 332–341. IEEE press, Los Alamitos (2005)
Al-Shihabi, S., Merz, P., Wolf, S.: Nested partitioning for the minimum energy broadcast. In: Proc. of LION 2007. Springer, Berlin (2007)
Wolf, S., Merz, P.: Evolutionary local search for the minimum energy broadcast problem. In: van Hemert, J., Cotta, C. (eds.) EvoCOP 2008. LNCS, vol. 4972, pp. 61–72. Springer, Heidelberg (2008)
Cartigny, J., Simplot-Ryl, D., Stojmenovic, I.: An adaptive localized scheme for energy-efficient broadcasting in ad hoc networks with directional antennas. In: Niemegeers, I.G.M.M., de Groot, S.H. (eds.) PWC 2004. LNCS, vol. 3260, pp. 399–413. Springer, Heidelberg (2004)
Guo, S., Yang, O.: Improving energy efficiency for multicasting in ad-hoc networks with directional antennas. In: Proc. of IEEE WiMob 2005, pp. 344–351. IEEE press, Los Alamitos (2005)
Guo, S., Yang, O.: Minimum-energy multicast in wireless ad hoc networks with adaptive antennas: MILP formulations and heuristic algorithms. IEEE Trans. on Mobile Computing 5(4), 333–346 (2006)
Guo, S., Yang, O.W.W.: Energy-aware multicasting in wireless ad hoc networks: A survey and discussion. Computer Communications 30, 2129–2148 (2007)
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)
Hansen, P., Mladenović, N.: Variable neighborhood search: Principles and applications. European Journal of Operational Research 130, 449–467 (2001)
Blum, C., Dorigo, M.: The hyper-cube framework for ant colony optimization. IEEE Trans. on Systems, Man anc Cybernetics – Part B 34(2), 1161–1172 (2004)
Hernández, H., Blum, C., Francès, G.: Ant colony optimization for energy-efficient broadcasting in ad-hoc networks. Technical Report LSI-08-13, LSI, Univeristat Politècnica de Catalunya (2008)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hernández, H., Blum, C., Francès, G. (2008). Ant Colony Optimization for Energy-Efficient Broadcasting in Ad-Hoc Networks. In: Dorigo, M., Birattari, M., Blum, C., Clerc, M., Stützle, T., Winfield, A.F.T. (eds) Ant Colony Optimization and Swarm Intelligence. ANTS 2008. Lecture Notes in Computer Science, vol 5217. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87527-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-87527-7_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87526-0
Online ISBN: 978-3-540-87527-7
eBook Packages: Computer ScienceComputer Science (R0)