Multi-Start and Tabu Search Algorithms in Base Station Location Problem
Purpose: The synthesis of a topological structure for a wireless data network implies planning territorial distribution of the base transceiver stations on potential sites, and connecting to the clients. The existing approaches to this problem have shortcomings: using solution methods with low computing speed (branch and bound method, heuristic method of Lagrange, etc.); lack of restrictions which would take into account the level of signal fading during its propagation from the base station to the client and back and also the level of inter-cell interference; using only one type of base stations. The goal of this research is creating a model for base station location which would be free from the above-mentioned drawbacks. Results: The problem of base station location has been formulated, taking into account the signal-to-interference ratio for the network clients. A problem solution is represented as a vector of structures, each storing the information about one potential site (the installed base station type, the list of connected clients). Modified algorithms of probabilistic tabu search and multi-start have been developed, based on the concept of current solution neighborhood. A new solution from the neighborhood of the current solution can be obtained using one of the following six operations: changing the type of a station to a more cheap/expensive one, reconnecting a client, removing a base station, addind a station, moving a base station. In order to avoid getting stuck in local optima during the tabu search, the algorithm is disabled to browse solutions from the tabu list. The novelty of the approach is that the tabu list is filled not with real decisions made in the past, but with operations to change the network configuration which can bring us back to old local optima. The essence of the modified multi-start algorithm is as follows: only two operations are used to obtain a new solutions (removing a base station and changing the type of a station to a cheaper one); only a part of the neighborhood is browsed; the transition to a new solution is performed on the "first improvement" principle; the algorithm of finding the best solutions runs several times. The developed algorithms are implemented in Delphi programming environment. It has been shown that the new algorithms show better results than the local search method. Practical relevance: The developed modifications of tabu search and multi-start methods help to find the solution for the base station location problem in a reasonable time, many orders of magnitude faster than the exact method of exhaustive search. It has been found that the quality of the problem solution obtained by probabilistic tabu search depends on the length of the tabu list and on the value of the neighborhood randomization parameter.