Electromagnetism metaheuristic algorithm for solving the strong minimum energy topology problem
DOI:
https://doi.org/10.2298/YJOR110608018KKeywords:
electromagnetism, metaheuristic, the strong minimum energy topology, wireless networksAbstract
In this paper electromagnetism (EM) metaheuristic is used for solving the NP-hard strong minimum energy topology problem (SMETP). Objective function is adapted to the problem so that it effectively prevents infeasible solutions. Proposed EM algorithm uses efficient local search to speed up overall running time. This approach is tested on two sets of randomly generated symmetric and asymmetric instances. EM reaches all known optimal solutions for these instances. The solutions are obtained in a reasonable running time even for the problem instances of higher dimensions.References
Akyildiz, I., Su, W., Sankarasubramaniam, Y., and Cayirci, E., “Wireless sensor networks: A survey”, Computer Networks, 38 (2001) 393-422.
Aneja Y.P., R. Chandrasekaran, Xiangyong Li, and K.P.K. Nair, “A branch-and-cut algorithm for the strong minimum energy topology in wireless sensor networks”, European Journal of Operational Research, 204 (2009) 604-612.
Birbil, S.I. and Fang, S.C, “An electromagnetism-like mechanism for global optimization”, Journal of Global Optimization, 25 (2003) 263-282.
Chen, W.-T., and Huang, N.-F., “The strongly connecting problem on multihop packet radio networks”, IEEE Transaction on Communications, 37 (1989) 293-295.
Cheng, X., Narahari, B., Simha, R., Cheng, X., and Liu, D., “Strong minimum energy topology in wireless sensor networks: NP-completeness and heuristics”, IEEE Transactions on Mobile Computing, 2 (2003) 248-256.
Cheng, M.X., Cardei, M., Sun, J., Cheng, X., Wang, L., Xu, Y., and Du, D.Z., “Topology control of ad hoc wireless networks for energy efficiency”, IEEE Transactions on Computers, 53 (2004) 1629-1635.
Lloyd, E., Liu, R., Marathe, M., Ramanathan, R., and Ravi, S., “Algorithmic aspects of topology control problems for ad hoc networks”, in: Proceedings of ACM International Symposium on Mobile Ad Hoc Networking and Computing - MobiHoc2002, Lausanne, Switzerland, June 9-11, 2002, 123-134.
Rodoplu, V., and Meng, T.H., “Minimum energy mobile wireless networks”, IEEE Journal on Selected Areas in Communications, 17 (1999) 1333–1344.
Tarjan Robert, “Depth-first search and linear graph algorithms”, SIAM Journal on Computing, 1 (1972) 146-160.
Wattenhofer, R., Li, L., Bahl, P., and Wang, Y.-M., “Distributed topology control for power efficient operation in multihop wireless ad hoc networks”, in: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies - INFOCOM’2001, Anchorage, Alaska, April 22–26, 2001, 1388–1397.
Yang, K., Konstantinidis, A., Chen, H., and Zhang, Q., “Energy-aware topology control for wireless sensor networks using memetic algorithms”, Computer Communications, 30 (2007) 2753-2764.
Downloads
Published
Issue
Section
License
Copyright (c) 2013 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
