Distributed ant colony optimization for minimum energy broadcasting in sensor networks with realistic antennas. (English) Zbl 1268.94004
Summary: One of the important tasks in wireless sensor networks is broadcasting, which arises when a sender node has to communicate information to all the other nodes of the network. In order to save energy, which is often a limited resource, broadcasting has to be done efficiently from an energy perspective. Energy efficiency can hereby be achieved by adjusting the transmission power levels of the sensor nodes’ antennas. This classical problem is known as the minimum energy broadcast (MEB) problem. In this work we deal with a generalization of this problem which is known as the minimum energy broadcast problem in sensor networks with realistic antennas (MEBRA). The difference to the classical MEB problem is to be found in a more realistic antenna model. In this work we propose a distributed ant colony optimization algorithm for solving the MEBRA problem. The experimental evaluation of the proposed algorithm shows that it generally improves over the centralized version of a classical heuristic. Moreover, depending on the exact antenna model used, the results of the distributed ant colony optimization algorithm are very close to the results of the centralized algorithm version.
MSC:
| 94A05 | Communication theory |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90B18 | Communication networks in operations research |
References:
| [1] | Akyildiz, I. F.; Su, W.; Sankarasubramaniam, Y.; Cayirci, E., A survey on sensor networks, IEEE Communications Magazine, 40, 8, 102-114 (2002) |
| [2] | Hernández, H.; Blum, C., Minimum energy broadcasting in wireless sensor networks: an ant colony optimization approach for a realistic antenna model, Applied Soft Computing, 11, 8, 5684-5694 (2011) |
| [3] | Guo, S.; Yang, O., Energy-aware multicasting in wireless ad hoc networks: a survey and discussion, Computer Communications, 30, 2129-2148 (2007) |
| [4] | Hernández, H.; Blum, C.; Francés, G., Ant colony optimization for energy-efficient broadcasting in ad-hoc network, (Proceedings of ANTS 2008—Sixth International Conference on Ant Colony Optimization and Swarm Intelligence. Proceedings of ANTS 2008—Sixth International Conference on Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, vol. 5217 (2008), Springer Verlag: Springer Verlag Berlin, Germany), 25-36 |
| [5] | Hernández, H.; Blum, C., Ant colony optimization for multicasting in static wireless ad-hoc networks, Swarm Intelligence, 3, 2, 125-148 (2009) |
| [6] | 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, (IEEE GLOBECOM 2003—Proceedings of the Global Communications Conference (2003), IEEE Press), 523-527 |
| [7] | Li, F.; Nikolaidis, I., On minimum-energy broadcasting in all-wireless networks, (Proceedings of the IEEE Conference on Local Computer Networks (2001), IEEE Press: IEEE Press Piscataway, NJ), 14-16 |
| [8] | Guo, S.; Yang, O., A dynamic multicast tree reconstruction algorithm for minimum-energy multicasting in wireless ad hoc networks, (Proceedings of IPCCC 2004—IEEE International Conference on Performance, Computing, and Communications (2004), IEEE Press: IEEE Press Piscataway, NJ), 637-642 |
| [9] | 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, (Proceedings of the IEEE CAS Workshop on Wireless Communications and Networking (2002), IEEE Press: IEEE Press Piscataway, NJ) |
| [10] | Kang, I.; Poovendran, R., Iterated local optimization for minimum energy broadcast, (Proceedings of WiOpt 2005—Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (2005), IEEE Press: IEEE Press Piscataway, NJ), 332-341 |
| [11] | Al-Shihabi, S.; Merz, P.; Wolf, S., Nested partitioning for the minimum energy broadcast, (Maniezzo, V.; Battiti, R.; Watson, J., LION 2007—Proceedings of the Workshop on Learning and Intelligent Optimization. LION 2007—Proceedings of the Workshop on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 5313 (2007), Springer Verlag: Springer Verlag Berlin, Germany), 1-11 |
| [12] | Wolf, S.; Merz, P., Evolutionary local search for the minimum energy broadcast problem, (Cotta, C.; van Hemert, J., VOCOP 2008—Proceedings of the 8th European Conference on Evolutionary Computation in Combinatorial Optimization. VOCOP 2008—Proceedings of the 8th European Conference on Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science, vol. 4972 (2008), Springer Verlag: Springer Verlag Berlin), 61-72 |
| [13] | J.E. Wieselthier, G.D. Nguyen, A. Ephremides, On the construction of energy-efficient broadcast and multicast trees in wireless networks, in: Proceedings of INFOCOM 2000—19th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, 2000, pp. 585-594.; J.E. Wieselthier, G.D. Nguyen, A. Ephremides, On the construction of energy-efficient broadcast and multicast trees in wireless networks, in: Proceedings of INFOCOM 2000—19th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, 2000, pp. 585-594. |
| [14] | Wieselthier, J. E.; Nguyen, G. D.; Ephremides, A., Energy-efficient broadcast and multicast trees in wireless networks, Mobile Networks and Applications, 7, 6, 481-492 (2002) |
| [15] | Qayyum, A.; Viennot, L.; Laouiti, A., Multipoint relaying for flooding broadcast message in mobile wireless networks, (HICSS 2002—Proceedings of the 35th Annual Hawaii International Conference on System Sciences (2002), IEEE Press), 3866-3875 |
| [16] | Lim, H.; Kim, C., Multicast tree construction and flooding in wireless ad hoc networks, (MSWIM 2000—Proceedings of the 3rd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (2000), ACM Press), 61-68 |
| [17] | Wieselthier, J. E.; Nguyen, G. D.; Ephremides, A., Energy-aware wireless networking with directional antennas: the case of session-based broadcasting and multicasting, IEEE Transactions on Mobile Computing, 1, 3, 176-191 (2002) |
| [18] | Wieselthier, J. E.; Nguyen, G. D.; Ephremides, A., The energy efficiency of distributed algorithms for broadcasting in ad hoc networks, (Stüber, G. L.; etal., WPMC 2002—-Proceedings of the 5th International Symposium on Wireless Personal Multimedia Communications, vol. 2 (2002), IEEE Press), 499-503 |
| [19] | Vellambi, B. N.; Rahnavard, N.; Fekri, F., FTS: a distributed energy-efficient broadcasting scheme using foutain codes for multihop wireless networks, IEEE Transactions on Communications, 58, 12, 3561-3572 (2010) |
| [20] | Chen, L.-S.; Chen, J.-H.; Wang, H.-C., An optimum branching-based efficient distributed broadcast scheme for wireless ad hoc networks, (AH-ICI 2009—Proceedings of First Asian Himalayas International Conference on Internet (2009), IEEE Press), 1-6 |
| [21] | Cagalj, M.; Hubaux, J. P.; Enz, C., Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues, (ACM MobiCom 2002—Proccedings of The Annual International Conference on Mobile Computing and Networking (2002), ACM Press), 172-182 |
| [22] | H. Hernández, C. Blum, Ant colony optimization for broadcasting in sensor networks under a realistic antenna model, in: B. Filipic, J. Silc (Eds.), BIOMA 2010—Proceedings of the 4th International Conference on Bio-Inspired Optimization Methods and their Applications, Jozef Stefan Institute, Ljubljana, Slovenia, 2010, pp. 153-162.; H. Hernández, C. Blum, Ant colony optimization for broadcasting in sensor networks under a realistic antenna model, in: B. Filipic, J. Silc (Eds.), BIOMA 2010—Proceedings of the 4th International Conference on Bio-Inspired Optimization Methods and their Applications, Jozef Stefan Institute, Ljubljana, Slovenia, 2010, pp. 153-162. |
| [23] | Blum, C.; Dorigo, M., The hyper-cube framework for ant colony optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 34, 2, 1161-1172 (2004) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
