Сенсорні мережі. Маршрутизація БСМ 2024 (лекція 5)

1.

СЕНСОРНІ МЕРЕЖІ
ЛЕКЦІЯ 5 «МАРШРУТИЗАЦІЯ БСМ»

2.

РЕЖИМИ РОБОТИ БСМ
Бездротові сенсорні мережі можна розділити на
класи в залежності від виду їх функціонування і типу
цільового програми:
1. Проактивні мережі. Вузли такої мережі періодично
включають свої сенсори і передавачі, знімають
показання і передають їх на базову станцію.
Таким
чином,
вони
роблять
"моментальну
фотографію" свого оточення з певною періодичністю і
використовуються зазвичай для додатків, що
вимагають регулярного моніторингу деяких значень.

3.

2. Реактивні мережі. Вузли реактивних мереж з
певною періодичністю знімають показання, однак
залишають поза передачею їх, якщо отримані дані
потрапляють в певну область нормальних показань.
У той же час відомості про несподівані і різкі зміни в
показаннях датчиків або їх виході за діапазон
нормальних значень негайно передаються на базову
станцію. Цей вид мережі призначений для роботи з
додатками реального часу.
3.
Гібридні
мережі.
Це
комбінація
двох
перерахованих вище типів, де сенсорні вузли не
тільки періодично відправляють зняті дані, але і
реагують на різкі зміни в значеннях.

4.

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

5.

Для визначення маршруту передачі інформації в БСМ від кінцевого
вузла до вузла координатора, а також між кінцевими вузлами,
використовуються спеціальні протоколи маршрутизації.
Протоколи маршрутизації в БСМ вирішують наступні завдання:
1.
Самоорганізація
вузлів
самовідновлення та оптимізація).
мережі
(самоконфігурування,
2. Маршрутизація пакетів даних і адресація вузлів.
3. Мінімізація енергоспоживання вузлів мережі і збільшення
загального часу життя всієї мережі.
4. Збір і агрегація даних.
5. Регулювання швидкості передачі і обробки даних в мережі.
6. Максимізація зони покриття мережі.
7. Забезпечення заданої якості обслуговування (QoS).
8. Захист від несанкціонованого доступу.

6.

При виборі шляху передачі інформації в мережі в
якості метрик в них можуть бути використані
наступні параметри:
• довжина шляху (кількість ділянок переприйому
інформації);
• надійність;
• затримка;
• пропускна здатність;
• завантаження;
• вартість передачі трафіку і ін.

7.

КЛАСИФІКАЦІЯ ПРОТОКОЛІВ
МАРШРУТИЗАЦІЇ
Установка
шляху
Структура
мережі
Операції
протоколів
Ініціатор
зв’язку
Проактивні
Плоска
На базі шляху
Вихідний
вузол
Реактивні
Ієрархічна
На базі запитів
Вхідний
вузол
Гібридні
На базі
місцезнахо
дження
На базі
«переговорів»
На базі QoS
Когерентні та
некогерентні

8.

Протоколи, що враховують структури мережі, діляться на:
1)
протоколи
однорівневої
(плоскої)
(flat-based)
маршрутизації
всі
вузли
БСМ
мають
однакову
функціональність, приклади: SPIN (Sensor Protocols for Information
via Negotiation), Direct Diffusion, Rumor Routing;
2) протоколи ієрархічної (hierarchical-based) маршрутизації
- вузли мережі виконують різні функції, вони можуть бути і
фізично різними, приклади: LEACH (LowEnergy Adaptive Clustering
Hierarchy), PEGASIS (Power-Efficient GAthering in Sensor Information
Systems), TEEN і APTEEN (Threshold-sensitive Energy Efficient Protocols),
СОП (Self-Organization Protocol);
3) протоколи маршрутизації на основі інформація про
місцезнаходження вузла (Location-based), приклади протоколів:
GAF (Geographic Adaptive Fidelity), GEAR (Geographic and Energy
Aware Routing).

9.

Робота
протоколу
маршрутизації
ґрунтуватися на різних принципах:
може
1) протоколи маршрутизації з багатьма маршрутами
(multipath routing) - використовуються кілька маршрутів від
джерела до точки призначення, що підвищує надійність
з'єднання, але збільшує накладні витрати і енерговитрати;
2) протоколи маршрутизації «на замовлення» (query-based) вузол посилає запит на дані в мережу і інший вузол, який має
запитувані дані, відповідає на запит;
3) протоколи маршрутизації, засновані на «переговорах»
(negotiation routing) між вузлами;
4) протоколи, які враховують якість обслуговування (QoSbased), що дозволяє забезпечити певний рівень послуг в
мережі.

10.

SPIN
(SENSOR PROTOCOLS FOR INFORMATION VIA EGOTIATION)
• Відноситься до методів маршрутизації для мереж з одноранговими
вузлами. Добре підходить для мереж з динамічною топологією (і
мобільними вузлами).
Це сімейство протоколів спрямоване на агрегацію даних.
У тому випадку, коли базовій станції потрібно визначити
характеристику для якої-небудь ділянки мережі, один з сенсорів
цієї ділянки призначається агрегатором (пристрій виконує
функцію збору даних).
Він збирає з інших вузлів цієї ділянки значення необхідної
характеристики, обчислює агрегатную функцію від них (середнє,
мінімум, максимум і т.д.) і передає це значення базовій станції.
При цьому загальні витрати на передачу інформації істотно
нижче, ніж при відсутності агрегатора.
Якщо кількість сенсорів в мережі досить велика, мережа зазвичай
розбивається на кластери і агрегація виконується в кожному кластері
незалежно.

11.

Протоколи SPIN засновані на процедурі переговорів
і дозволяють сенсорам виробляти узгодження один з
одним перед передачею даних в мережі.
Взаємодія заснована на трьох типах повідомлень:
ADVERTISE (ADV) - повідомлення про наявність
нових даних у вузлі, містить їх опис (метадані);
REQUEST (REQ) - запит даних;
DATA - безпосередньо дані.
А
C
D
B
G
E
F
Механізм взаємодії протоколу SPIN
При отриманні нових
даних
вузлом
А
надсилається
повідомлення
ADV
сусідньому вузлу В

12.

Протоколи SPIN засновані на процедурі переговорів
і дозволяють сенсорам виробляти узгодження один з
одним перед передачею даних в мережі.
Взаємодія заснована на трьох типах повідомлень:
ADVERTISE (ADV) - повідомлення про наявність
нових даних у вузлі, містить їх опис (метадані);
REQUEST (REQ) - запит даних;
DATA - безпосередньо дані.
А
C
Отримавши від вузла А
повідомлення ADV, вузол
В направляє запит REQ
на передачу
D
B
G
E
F
Механізм взаємодії протоколу SPIN

13.

Протоколи SPIN засновані на процедурі переговорів
і дозволяють сенсорам виробляти узгодження один з
одним перед передачею даних в мережі.
Взаємодія заснована на трьох типах повідомлень:
ADVERTISE (ADV) - повідомлення про наявність
нових даних у вузлі, містить їх опис (метадані);
REQUEST (REQ) - запит даних;
DATA - безпосередньо дані.
А
C
D
B
G
E
F
Механізм взаємодії протоколу SPIN
Отримавши від нього
запит REQ на передачу,
вузол А передає дані
(DATA)

14.

Протоколи SPIN засновані на процедурі переговорів
і дозволяють сенсорам виробляти узгодження один з
одним перед передачею даних в мережі.
Взаємодія заснована на трьох типах повідомлень:
ADVERTISE (ADV) - повідомлення про наявність
нових даних у вузлі, містить їх опис (метадані);
REQUEST (REQ) - запит даних;
DATA - безпосередньо дані.
Після
отримання
потрібних даних вузол В
А
аналогічно
посилає
C
повідомлення ADV для
своїх сусідів
ADV
D
B
ADV
E
G
F
Механізм взаємодії протоколу SPIN

15.

Протоколи SPIN засновані на процедурі переговорів
і дозволяють сенсорам виробляти узгодження один з
одним перед передачею даних в мережі.
Взаємодія заснована на трьох типах повідомлень:
ADVERTISE (ADV) - повідомлення про наявність
нових даних у вузлі, містить їх опис (метадані);
REQUEST (REQ) - запит даних;
DATA - безпосередньо дані.
А
C
D
B
G
E
F
Механізм взаємодії протоколу SPIN
Вузли, зацікавлені в цих
даних, в свою чергу
відправляють
запити
REQ назад до B

16.

Протоколи SPIN засновані на процедурі переговорів
і дозволяють сенсорам виробляти узгодження один з
одним перед передачею даних в мережі.
Взаємодія заснована на трьох типах повідомлень:
ADVERTISE (ADV) - повідомлення про наявність
нових даних у вузлі, містить їх опис (метадані);
REQUEST (REQ) - запит даних;
DATA - безпосередньо дані.
На завершення вузол В
розсилає необхідні дані
А
C
D
B
G
E
F
Механізм взаємодії протоколу SPIN
Метадані
служать
описом
реальних даних, спираючись на
які, вузли уникають повторної
передачі одних і тих же даних
(наприклад, самого джерела).
Отже, знижується надмірність
мережевого
трафіку
і
зменшується витрата енергії

17.

DD
(DIRECTED DIFFUSION)
• Метод дозволяє здійснювати централізований збір даних з
доставкою по запиту. Розвинений для БСМ, в яких число подій
мале, а число запитів дуже велике.
Цей протокол також спрямований на агрегацію даних.
Він орієнтований на централізовану модель збору з
доставкою даних на вимогу.
Передбачає
наявність
центрального
вузла
Sink,
і
відповідно, маршрутизацію від безлічі джерел до одного
приймача.
Процес передачі даних в такому протоколі описується як
спрямована дифузія.

18.

Алгоритм роботи DD складається з трьох основних фаз:
a) розсилка вузлом Sink повідомлення запиту Interest;
b) первісна настройка градієнтів Gradients;
c) зміцнення шляху і передача даних
Sink
Джерело
інформації
D
B
E
F
Interest
C
G
Взаємодія протоколу DD (a)
Спочатку
приймач
визначає
низьку
швидкість передачі даних
для
всіх
вхідних
повідомлень.

19.

Алгоритм роботи DD складається з трьох основних фаз:
a) розсилка вузлом Sink повідомлення запиту Interest;
b) первісна настройка градієнтів Gradients;
c) зміцнення шляху і передача даних
Sink
Джерело
інформації
D
B
E
F
Gradients
C
G
Взаємодія протоколу DD (b)
Надалі він може «зміцнити»
один
певний
сенсор,
відправивши
йому
повідомлення
Interest,
збільшивши, таким чином,
швидкість
передачі.
Аналогічно, якщо сусідній
сенсор
отримає
це
повідомлення і більш високу
швидкість передачі ніж
раніше (вище ніж у будьякого існуючого градієнта),
то це «зміцнить» один або
більше його сенсорів-сусідів.
Градієнт вказує можливий напрямок
маршрутизації і може мати свою вагу.

20.

Алгоритм роботи DD складається з трьох основних фаз:
a) розсилка вузлом Sink повідомлення запиту Interest;
b) первісна настройка градієнтів Gradients;
c) зміцнення шляху і переда даних
Sink
Джерело
інформації
C
D
B
E
F
Взаємодія протоколу DD (c)
G
В
результаті
для
передачі
даних
вибирається найбільш
підходящий
шлях
(наприклад,
найкоротший
або
більш
енергоефективний).
Запити
Interest,
періодично
повторюються вузлом
Sink для забезпечення
працездатності
та
надійності всієї БСМ.

21.

Так як дані в вузлі представлені у вигляді пар «атрибут-значення»,
то запит містить певний «атрибут-значення» параметрів, що цікавлять
центральний вузол.
Кожен вузол підтримує локальний кеш запитів, в якому
зберігаються записи про стан активних запитів.
Для кожного запиту в кеші зберігаються додаткові дані:
тимчасова мітка (timestamp), тобто значення таймера, що фіксує
момент отримання запиту;
градієнти (gradient) на кожен сусідній вузол із зазначенням
швидкості обміну (data rate),
тривалості існування за таймером(Duration)
час життя (expiresAt).
Градієнт фактично вказує можливий напрямок маршрутизації і
може мати свою вагу, який використовується в залежності від
конкретних вимог щодо маршрутизації.
Описана структура кеша запитів є основою для оптимальної
маршрутизації.

22.

RUMOR ROUTING (RR)
Особливість протоколу - наявність в мережі повідомлення Agent з великим
часом життя Time to Live (TTL), яке передається по мережі і поширює
інформацію про події, що відбулися іншим вузлам.
Таким чином, вузли поповнюють свою таблицю подій і передають
повідомлення Agent сусіднім вузлам до тих пір, поки воно не вичерпає TTL.
У момент, коли центральним вузлом поширюється запит на отримання
даних, які вже є внаслідок події, що сталася, вузли переглядають свої таблиці
подій, і, при виявленні відповідності, інформують результат. Тому інформація
про подію доходить до вузла-ініціатора ще до того як запит дійде до джерела
даних.
Джерело
події
- Джерело запиту
- Вузол
- Вузол із записом
про подію

23.

Найбільш відомі
• GBR (Gradient-based routing)
У процесі поширення запиту з центру враховується кількість ретрансляцій від вузла до
вузла (hops) і обчислюється параметр (висота вузла), який вказує мінімально можливу
кількість ретрансляції. Адаптивний алгоритм (вузли можуть самостійно змінювати свою
висоту).
• LEACH (Low energy adaptive clustering hierarchy)
Алгоритм відноситься до класу ієрархічних. Вузли, що знаходяться в одній зоні
радіодоступу, об'єднуються в кластер. Кластер складається зі звичайних вузлів (CM,
cluster members) і одного вузла вищого рангу (CH, cluster head). Безліч CH утворює
комунікаційну інфраструктуру мережі.
• GAF (Geographic adaptive fidelity)
Алгоритм також заснований на кластерному розбитті мережі і використовує
інформацію про просторове розташування вузлів. Формується віртуальна сітка, що
покриває територію, зайняту БСМ. Усередині кластера вибирається вузол-лідер, який
відповідає за підтримання пов'язаності мережі в умовах, коли всі інші вузли
знаходяться в сплячому режимі. Вузол-лідер здійснює також моніторинг стану вузлів.

24.

GPRS (Greedy Perimeter Stateless Routing)
Клас
алгоритмів,
який
використовує
географічну
інформацію
про
місцезнаходження вузла в просторі. Кожен вузол знає про розташування
самого себе і найближчих сусідів. Пересилання повідомлення здійснюється
вузлом тому сусідові, який знаходиться найближче до адресата
• TTDD (Two-Tier Data Dissemination )
Протокол з ієрархічним методом передачі даних. Він орієнтований на
ефективну роботу в широкомасштабних БСМ з мобільними вузлами збору
даних і стаціонарними сенсорами. Маршрутизація базується на інформації про
місцезнаходження кожного вузла і побудові сітки ланок. Сенсори, які
розташовуються ближче всього до точок перетину сітки, називаються вузлами
поширення Dissemination nodes. Вони оновлюють таблицю маршрутизації,
постійно відстежуючи розташування приймача даних.