АЛГОРИТМ ВИБОРУ ЦЕНТРАЛЬНОГО ВУЗЛА В ОДНОРАНГОВІЙ МЕРЕЖІ ІЗ СКЛАДНОЮ ВИПАДКОВОЮ ТОПОЛОГІЄЮ

Вихідні дані збірника:

АЛГОРИТМ ВИБОРУ ЦЕНТРАЛЬНОГО ВУЗЛА В ОДНОРАНГОВІЙ МЕРЕЖІ З СКЛАДНОЮ ВИПАДКОВОЮ ТОПОЛОГІЄЮ

Власова Ганна Михайлівна

студент Володимирського державного університету імені О.Г. та Н.Г. Столетових, РФ, м. Володимир

Голованов Андрій Євгенович

студент Володимирського державного університету імені О.Г. та Н.Г. Столетових, РФ, м. Володимир

Монахов Юрій Михайлович

канд. техн. наук, доцент кафедри інформатики та захисту інформації

Володимирського державного університету імені О.Г. та Н.Г. Столетових, РФ, м. Володимир

ЦЕНТРОВИЙ NODE SELECTION ALGORITHM IN AN AD HOC NETWORK WITH COMPLEX RANDOM TOPOLOGY

Student, Vladimir State University, Росія, Vladimir

PhD, Associate Profesor of Informatics and IT Security Dept., Vladimir State University, Russia, Vladimir

Мета дослідження — розробити спосіб пошуку головного вузла, який з низьким ступенем ймовірності призведе до вибору як центр прийняття рішення атакованого та/або захопленого зловмисником вузла.

У процесі роботи ми розробили алгоритм пошуку центру прийняття рішень (головного вузла мережі) — консенсусний алгоритм пошуку головного вузла, заснований на рекомендаціях. Шляхом моделювання даного алгоритму ми плануємо дослідити його збіжність за умов атак та децентралізованості самого процесу голосування.

З огляду на дослідження, це залежить від того, як центральний номер вибору, який буде показувати низьку ймовірність вибору, щоб відісантинський номер є рішенням-відповідним центром.

Під час нашого дослідження ми розробили selectionalgorithm for electing the node that will perform the decision-making — consensual recommendation-based central node selection algorithm. При здійсненні цих algoritms в agent-based model буде планування для дослідження їх конвергенції під впливом нападів і децентралізації повноцінних процесів.

Ключові слова: складні мережі; довільна топологія; кластеризація мережі; оцінка рівня довіри; голосування; вибір головного вузла; алгоритм ухвалення рішення; моделювання.

Keywords: complex networks; random topology; network clustering; evaluation of trust; election; main node selection; decision-making algorithm; modeling.

Виходячи з вищесказаного, мета дослідження визначена як розробка способу пошуку головного вузла в мережі, який з низьким ступенем ймовірності призведе до вибору центру прийняття рішення атакованого і/або захопленого зловмисником вузла.

Відповідно до мети ми визначили об'єкт та предмет дослідження. Предметом дослідження є процес голосування в одноранговій мережі, спрямований на вибір головного вузла з-поміж подібних вузлів в умовах атак або вразливостей, а об'єктом дослідження є однорангові мережі зі складною випадковою топологією.

Перш ніж докладно описати сам алгоритм, необхідно кілька слів сказати про саму модель мережі. Ми розглядаємо статичну мережу, в якій присутні області підвищеного зв'язку, так звані кліки. Під клікою будемо мати на увазі подраграфи, ймовірність наявності зв'язків між двома сусідніми вершинами в яких близька до одиниці.

У цій роботі ми враховуємо, що захоплений зловмисником вузол виявлятиме різного роду зловмисну активність і в процесі голосування: чи то зрив, чи затримка процесуголосування, поширення хибної інформації про себе та/або про сусідні вузли, тому для процесу голосування принципове значення має місце розташування голосуючого вузла.

Ми виділили три можливі варіанти розташування вузла в мережі: у кліку (рис. 1), на краю кліки (рис. 2) та між двома або більше кліками (рис. 3). Вузол, розташований між кількома кліками, умовно називатимемо мостом.

Механізм визначення типу кожного вузла мережі пропонуємо ґрунтувати на обчисленні кластерного коефіцієнта — показника взаємопов'язаності сусідів вузла та на обчисленні власної центральності вузла, що дозволить визначити ступінь «важливості» вузла, тобто кількість сусідів вузла та зв'язків у його сусідів.

Малюнок 1. Атакований вузол у кліку

Малюнок 2. Атакований вузол на краю кліки

Малюнок 3. Атакований вузол являє собою місце з'єднання декількох клік

Відношення реальної кількості ребер, які з'єднують найближчих сусідів даного вузла до максимально можливого, називається коефіцієнтом кластерності вузла. Таке визначення дає Watts та Strogatz у роботі [5]. Формула для розрахунку кластерного коефіцієнта може бути подана наступним чином:

С(i) = , (1)

де: k - Число ребер, що виходить з вузла i;

m — число ребер між сусідніми вузлами вузла i.

Визначення власної центральності необхідне і для того, щоб можна було дати приблизну оцінку часу на голосування та передачу рекомендацій кожним вузлом.

Оскільки кожен із вузлів у мережі знає топологію лише у межах своєї локальності, тому й центральність будемо обчислювати для кожного вузла лише з урахуванням його сусідніх вузлів та їх безпосередніхсусідів. Відома формула 2 дає нам таке співвідношення: множення матриці на власний вектор дає колінеарний вектор - той же вектор, помножений на деяке скалярне значення, що називається власним числом матриці.

де: A - матриця суміжності вузла з його сусідами та сусідами сусідів;

x - Власний вектор матриці;

λ - власне значення матриці;

З 2 отримуємо формулу 3 для власного центрального значення вузла:

xk = (3)

А тепер перейдемо безпосередньо до рекомендаційного консенсусного алгоритму пошуку головного вузла. Спочатку кожен вузол у мережі повинен самостійно розрахувати свій кластерний коефіцієнт і такий параметр, як власна центральність вузла.

Перед запуском самого процесу голосування кожен вузол в мережі отримує інформацію про «локальність», тобто інформацію про сусідів та сусідів своїх сусідів, що містить значення їх кластерного коефіцієнта та власної центральності. Після відбувається обробка отриманих відомостей кожним вузлом, в результаті якої вузол отримує наближену оцінку топології області навколо нього та екзистенційно приймає рішення на основі величин кластерних коефіцієнтів про своє місцезнаходження (визначає свій тип).

На наступному етапі алгоритму безпосередньо ініціюємо процес голосування: всі вузли широкомовно розсилають усім своїм сусідам інформації про себе (вектор характеристик: рівень довіри до вузла, кількість ресурсів тощо) як про кандидата на висування на роль головного вузла в мережі. У цій роботі ми не загострюємо увагу на перерахуванні точного переліку використовуваних показників.

Далі в залежності від власної центральності вузла йому виділяється певний час на обробку відомостей про кандидатів з-поміж сусідніх вузлів, якізберігаються на вузлі як черги з пріоритетом. Кожен вузол формує свій голос за найкращого кандидата по всьому вектору отриманих показників. Кластерний коефіцієнт та величину власної центральності вузла необхідно також враховувати, щоб уникнути нелегітимного завищення своїх характеристик якимось із вузлів, тобто ми повинні враховувати до якого з трьох типів вузлів відносить себе наш сусід і до якого типу на основі кластерних коефіцієнтів його сусідів ми відносимо його.

Варто зазначити, що вузол, що є мостом, не обробляє списки кандидатів, а лише передає рекомендації від сусідів до сусідів, щоб відстежити завантаженість моста та визначити, чи запускає цей вузол механізм фальсифікації голосування.

Після закінчення виділеного проміжку часу кожному вузлу необхідно видалити всіх кандидатів з черги, за винятком лідируючого кандидата, що знаходиться відповідно на початку черги, а також надіслати всім своїм сусідам інформацію про цього кандидата, щоб не давати можливості зловмиснику затримувати процес голосування скільки завгодно довго, т.е. о. На всіх вузлах відбувається асинхронна передача рекомендації обраного кандидата своїм сусідам.

Як тільки на вузол надходять нові рекомендації від сусідів, він знову заносить їх у свою чергу з пріоритетом і знову йому виділяється ліміт часу на обробку цих даних. Причому вузол враховує лише характеристики кандидатів, а чи не кількість відданих них голосів (кількість отриманих рекомендацій). І в результаті нової ітерації зі списку видаляються всі кандидати, окрім лідера, котрий знову рекомендується своїм сусідам.

Збір, обробку та передачу рекомендацій повторюють доти, доки не буде досягнуто консенсусу в рамках локальності, тобто не оновлюватиметься список кандидатівна кожному вузлі протягом тривалого часу. Необхідна кількість таких ітерацій може бути визначена в ході експерименту поставленого на моделі, збіжність даного процесу, очевидно, буде залежати від розмірів клік і розміру самої мережі. Вищеописаний алгоритм представлений у нотації UML як діаграми діяльності малюнку 4.

Малюнок 4. Консенсусний рекомендаційний алгоритм пошуку головного вузла

На сьогоднішній день як результати проведення даного наукового дослідження на тему: «Алгоритм вибору центрального вузла в одноранговій мережі зі складною випадковою топологією» виступає розроблений нами алгоритм голосування для пошуку центру прийняття рішень — «Консенсусний алгоритм пошуку головного вузла, заснований на рекомендаціях».

Тестування роботи даного алгоритму на моделі дозволить виявити необхідну кількість турів голосування та остаточного прийняття рішення щодо вибору головного вузла, а також це дасть можливість визначити, чи досягається збіжність даного процесу на випадковому графі. У зв'язку з цим першорядними напрямами нашого подальшого дослідження вважаємо: розробку моделі складної мережі та моделювання процесу голосування, згодом її тестування на випадковому графі з досить великою кількістю вузлів та опрацювання результатів емуляції процесів голосування.