tailieunhanh - Electromagnetism metaheuristic algorithm for solving the strong minimum energy topology problem

In this paper electromagnetism (EM) metaheuristic is used for solving the NPhard 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. | Yugoslav Journal of Operations Research 23 (2013), Number 1, 43-57 DOI: ELECTROMAGNETISM METAHEURISTIC ALGORITHM FOR SOLVING THE STRONG MINIMUM ENERGY TOPOLOGY PROBLEM Aleksandar KARTELJ Faculty of Mathematics, University of Belgrade, Serbia kartelj@ Received: June 2011 / Accepted: August 2012 Abstract: In this paper electromagnetism (EM) metaheuristic is used for solving the NPhard 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. Keywords: Electromagnetism, Metaheuristic, The strong minimum energy topology, Wireless networks. MSC: 90C59, 05C40, 68M10. 1. INTRODUCTION . Wireless sensor networks Wireless sensor network (WSN) can be consisted of geographically distributed autonomous sensors which cooperatively measure some phenomena like temperature, intensity of sound, vibrations, pressure etc. (for example seismic network instruments). Evolution of such networks was motivated by development of military devices for battle field surveillance, and today they are also used for different civil and industry matters, transport and pollution control (for other usages see [1]). The basic unit of the network is the wireless sensor, which is usually equipped with a measurement instrument, the radio 44 Aleksandar Kartelj / EM metaheuristic algorithm for solving SMETP used for communication with the rest of the network, a little programmable microcontroller and a battery. One of the problems in WSN is to reduce the amount of energy used for power supply. One way to address this problem is to .