Дослідження розміщення сенсорних вузлів на площині на основі генетичного алгоритму

Abstract

У роботі досліджено ефективність використання методу розташування сенсорних вузлів на основі генетичного алгоритму для випадкової топології. Основна мета полягає у визначенні конфігурації вузлів, яка мінімізує кількість “сліпих зон” та забезпечує максимально ефективне покриття заданої області. У разі випадкового розміщення вузлів кожен вузол матиме зв’язки з іншими вузлами, що створює складний простір пошуку. Для цього випадку у роботі досліджено 25 вузлів із однаковим радіусом дії. На основі авторських досліджень із використанням розробленого програмного забезпечення визначено оптимальні значення основних параметрів генетичного алгоритму та подано результати імітаційного моделю- вання. Оцінено ефективність методу розміщення сенсорів зі збільшенням кількості поколінь, що відображає його здатність знаходити оптимальні розв’язки. Якщо є 25 поколінь, кількість зон “перекриття” вузлів велика, проте у разі збільшення значення спостерігається оптималь- ніше розміщення вузлів. Для аналізу роботи алгоритму використано залежність значення фітнес-функції від кількості поколінь. Показано, що за початкових значень кількості поко- лінь спостерігається найбільше зростання максимального значення фітнес-функції, що характерно для початкової фази еволюційного процесу. Надалі якість рішень (максимальне / середнє значення фітнес-функції) істотно поліпшується зі збільшенням кількості поколінь. Отже, найоптимальніше розташування 25 вузлів із радіусом дії 30 м на площині розміром 100 на 100 м отримано для кількості поколінь 152. Подано хромосому із 25 вузлів, яка відповідає їх найкращому розміщенню на досліджуваній площині. Для досягнення синергії між топологією та алгоритмом маршрутизації побудовано маршрут між двома сенсорними вузлами. Наведено матрицю відстаней вузлів, графову модель мережі та утворений маршрут. Викладені результати дослідження мають практичне значення для проєктування та функ- ціонування сенсорних мереж з довільною топологією, що дасть змогу підвищити їхню на- дійність і продуктивність в умовах невизначеності розташування вузлів.

The study focuses on investigating the efficiency of a genetic algorithm-based sensor node placement method for a random topology. The primary objective is to identify a node configuration that minimizes the number of “blind spots” and ensures the most efficient coverage of a given area. Random node placement is characterized by the potential for each node to establish connections with other nodes, resulting in a complex search space. For this study,25 nodes with identical sensing radii were analyzed. Based on the authors’ research and the use of custom-developed software, optimal parameter values for the genetic algorithm were determined, and simulation results were presented. The effectiveness of the sensor placement method was evaluated with an increasing number of generations, reflecting the algorithm's ability to identify optimal solutions. In scenarios with 25 generations, there were numerous overlapping zones between nodes. However, as the number of generations increased, a more optimal node placement was observed. To analyze the algorithm’s performance, the relationship between the fitness function value and the number of generations was used. The results demonstrated that the maximum fitness function value increased most significantly during the initial phase of the evolutionary process. Subsequently, the quality of the solutions (maximum and average fitness values) improved substantially with an increasing number of generations. The most optimal placement of 25 nodes with a sensing radius of 30 meters on a 100×100 m plane was achieved with 152 generations. A chromosome representing the optimal placement of the 25 nodes on the studied area was provided. To achieve synergy between topology and the routing algorithm, a route was constructed between two sensor nodes. The distance matrix for the nodes, a graph model of the network, and the generated route were presented. The research findings hold practical significance for the design and operation of sensor networks with arbitrary topology, enhancing their reliability and performance under uncertain node placement conditions.