Пошук маршруту передачі даних у безпровідній сенсорній мережі із використанням генетичного алгоритму

Abstract

Висвітлено застосування генетичного алгоритму для визначення оптимального марушруту в безпровідній сенсорній мережі. Наведено класифікацію стратегій маршрутизації даних на основі: способу визначення маршрутів, структури мережі, мережевих операцій, орга- нізатора комунікацій. Генетичний алгоритм зараховано до багатошляхової маршрутизації, оскільки його використання дає змогу отримати множину маршрутів. Відповідно, коли передавання даних по найкращому маршруту неможливе, доступна інформація із множини маршрутів, що дає змогу отримати альтернативні рішення у випадку відмови основного. Наведено основні етапи роботи генетичного алгоритму: відбір, схрещування та мутація. Значну увагу звернено на налаштування його параметрів, зокрема розміру популяції, кількості поколінь, імовірності схрещування та імовірності мутації. Для визначення маршруту в безпровідній сенсорній мережі використано сукупність таких генетичних операторів: турнірний оператор відбору, впорядкований оператор схрещування та оператор мутації перемішування, та сформовано функцію для оцінювання пристосованості кожної особини (маршруту). Для перевірки працездатності пропонованого генетичного алгоритму розроблено програмний продукт на мові програмування Python із використанням бібліотеки DEAP. Змодельовано мережу із 25 вузлів, розміщених довільно на ділянці розміром 100×100, радіус дії кожного із них 30 метрів. Щоб урахувати неможливість передавання даних між вузлами із радіусом дії, більшим за заданий, використано штраф на відстань 1000 м, що спонукає генетичний алгоритм шукати коротші маршрути. Представлено матрицю вузлів розглянутої мережі, що містить інформацію про топологію та взаємозв’язки між вузлами. На основі результатів імітаційного моделювання показано, що найкоротший маршрут між двома розглянутими вузлами встановлено для кількості поколінь 150 та розміру популяції 300. Також отримані результати демонструють лінійне зростання часу пошуку маршруту зі збільшенням кількості поколінь та розміру популяції.The article is devoted to the application of a genetic algorithm for determining the optimal route in a wireless sensor network. The paper presents a classification of data routing strategies based on: the method of determining routes, network structure, network operations, and communication organiser. The genetic algorithm is classified as a multi-path routing strategy, since its use allows obtaining a set of routes. Accordingly, when data transmission via the best route is not possible, information from a set of routes is available, which allows obtaining alternative solutions in case of failure of the main route. The main stages of the genetic algorithm are presented: selection, crossing and mutation, with considerable attention paid to setting its parameters, in particular, population size, number of generations, crossover probability and mutation probability. To determine the route in a wireless sensor network, the following set of genetic operators is used: a tournament selection operator, an ordered crossover operator, and a mixing mutation operator, and a function is formed to assess the fitness of each individual (route). To test the performance of the presented genetic algorithm, a software product in the Python programming language was developed using the DEAP library. A network of 25 nodes was modelled, randomly placed on a 100 by 100 area, with each node having a range of 30 metres. To take into account the impossibility of data transmission between nodes with a greater range than the specified one, a distance penalty of 1000 metres is used, which encourages the genetic algorithm to search for shorter routes. The matrix of nodes of the considered network is presented, which contains information about the topology and relationships between nodes. Based on the results of simulation modelling, it is shown that the shortest route between the two considered nodes is established at a number of generations of 150 and a population size of 300. The results also demonstrate a linear increase in the route search time with an increase in the number of generations and population size.