Optimization of mobile flow routing in a wireless sensor network using heuristic algorithms

Abstract

The subject of the study is a wireless sensor network (WSN) with a mobile sink. The purpose of the work is to improve the performance of the WSN, increase its lifetime and functionality by reducing the data transmission delay time in the process of polling routers by optimizing the mobile sink route using the most efficient algorithm. To achieve this goal, the following tasks must be performed: optimize the route of the WSN mobile stock by solving the traveling salesman problem using the branch and bound method and comparing the conditional average route length of a set of solutions without optimization and with optimization using the Robbins–Monroe procedure; conduct a comparative analysis of the exact solution of the traveling salesman problem obtained by the branch and bound method and the approximate solution obtained by heuristic methods; formulate practical recommendations for the selection of algorithms for optimizing the mobile flow route depending on the size of the sensor network. The following methods were used: simulation modeling, optimization methods, mathematical data processing. Results achieved. The solution of the mobile flow route optimization problem in BSM using heuristic algorithms was investigated in order to formulate practical recommendations for selecting mobile flow route optimization algorithms depending on the size of the sensor network. A comparative analysis was performed of the exact solution of the traveling salesman problem, performed using the branch and bound method, and the approximate solution, performed using heuristic methods. To obtain an approximate solution, two heuristic algorithms were implemented: the ant colony optimization (ACO) algorithm and the simulated annealing (SA) algorithm. These algorithms were implemented for the traveling salesman problem with specific coordinates for each problem. The effectiveness of the algorithms is evaluated on networks of various sizes, from 10 to 500 nodes. The simulation results show that ACO is highly effective on small and medium-sized networks (up to 50 nodes), providing shorter routes and faster computation times. SA is determined to be the best scalable on large networks (100 nodes and more), offering stable performance under high computational load. Conclusions. It has been demonstrated that introducing optimization in the selection of the mobile flow route in BSM leads to a reduction in the length of the mobile flow bypass contour in the range of 30–40% depending on the network size and the distances between routers. Reducing the polling time of routers in a sensor network leads to an increase in the residual power of power supplies, and thus extends the life of the network. It has been proven that the use of heuristic algorithms is only appropriate when a high speed of calculating a new mobile flow route is required. If the speed of calculating a new route is not critical, then it is better to use accurate calculation algorithms. For each algorithm, parameters must be selected depending on the task at hand, since these parameters affect the speed of the algorithm and can reduce the range of possible routes that can be obtained during calculations. The study proves the importance of individual parameter tuning of algorithms to improve the accuracy and adaptability of solutions in mobile flow routing tasks.