AN OPTIMAL SENSOR NODE PLACEMENT METHOD BASED ON GENETIC EVOLUTION

Abstract

The paper is devoted to solving the problem of optimal placement of nodes in a wireless sensor network. The reasons for adding new nodes to an existing network are described. The mesh topology is chosen as one of the most popular and effective topologies for WSNs due to its flexibility, reliability, and ability to provide a high degree of network connectivity. A method for optimal node placement, taking into account the features of the mesh topology, has been developed based on the use of genetic evolution. A block diagram of the genetic algorithm is presented, the main stages of which are selection, mutation and crossing. To determine the suitability of each individual, a fitness function is calculated, which evaluates the ‘overflow’ of squares on the considered plane. Accordingly, the number of nodes in each square is determined by adding the matrices for new and existing nodes. The fit-non function is formed, which is advisable to use for the problem of distributing objects where it is necessary to avoid their accumulation in one place, i.e. to maximise the uniformity of distribution. To test the performance of the proposed solution for determining the optimal placement of nodes in a mesh topology, a software product in the Python programming language was created. Based on the results of simulation modelling, the intermediate results of the developed algorithm, the best solution obtained, characterised by uniform placement of nodes, and the dependence of the fitness function value on the number of generations are presented. It is shown that the use of genetic evolution leads to stabilisation of the node placement, while an increase in the number of generations brings the algorithm closer to the global optimum. The best result of placing 75 new nodes in the presence of 25 existing ones was obtained when the population size was 1000 and the number of generations was 260. The obtained results demonstrate rapid convergence in the early stages, which demonstrates the ability of the algorithm to quickly find high-quality solutions. The stabilisation of the fitness function indicates the achievement of a certain level of optimality. This can be used to set a criterion for stopping the algorithm, which will reduce computational costs by stopping the evolution after reaching a stable state.