Шановні члени Державної екзаменаційної комісії до Вашої уваги надається доповідь за темою бакалаврської дипломної роботи : «Вдосконалення алгоритмів синхронізації в мобільних сенсорних мережах».
Актуальність теми даної роботи обумовлена тим, що, cьогодні мобільні сенсорні мережі стали все більш популярними завдяки своїй гнучкості та можливостям збору та передачі даних з різних джерел, таких як акселерометри, гіроскопи, магнітні датчики та інші. Але одним з викликів при роботі з такими мережами є синхронізація даних, що отримуються з різних джерел, оскільки ці дані можуть мати різні затримки та рівні шуму.
Об’єктом дослідження є мобільна сенсорна мережа
Предметом дослідження: алгоритми синхронізації в мобільних сенсорних мережах
Мета роботи: розглянути різні підходи до синхронізації даних в мобільних сенсорних мережах та навести приклади їх використання. Також проаналізувати актуальність
Слайд 3 У першому розділі розглянуті особливості побудови сучасних бездротових сенсорних мереж, їх топологій, сфер застосування та обмежень, притаманних БСМ.
Бездротова сенсорна мережа з рухомими компонентами відома як мобільна сенсорна мережа (MSN). У цій бакалаврській роботі ми досліджуємо мобільність сенсорної мережі типу Квазімобільність. Протягом "часу мобільності" всі мобільні елементи мережі переміщуються в певній області, залишаючись нерухомими протягом "періоду передачі інформації". Це називається квазімобільністю. Час від часу відбувається рух і завмирання. Як наслідок, необхідно перераховувати координати датчика після кожного руху під час завмирання.
Загальне визначення бездротової сенсорної мережі (БСМ) - це мережа вузлів, які спільно виявляють і контролюють навколишнє середовище, забезпечуючи взаємодію між людьми або комп'ютерами і навколишнім середовищем. На сьогоднішній день у БСМ часто зустрічаються сенсорні вузли, виконавчі вузли, шлюзи та клієнти. Мережі створюються шляхом самоуправління великою кількістю сенсорних вузлів, які випадковим чином розміщуються в межах або поблизу регіону моніторингу (поля виявлення).
Типова процедура реалізації БСМ полягає в наступному: по-перше, вузли сенсорної мережі транслюють свій стан в навколишнє середовище і отримують стан від інших вузлів, щоб виявити один одного. По-друге, використовується певна топологія для організації вузлів сенсорної мережі у зв'язану мережу (лінійна, зірка, дерево, сітка тощо). Потім у побудованій мережі розраховуються відповідні шляхи для передачі даних зондування. Вузли сенсорної мережі часто живляться від батарейок, тому відстань передачі даних між вузлами БСМ обмежена. У відкритому зовнішньому середовищі з прямою видимістю відстань передачі може становити від 800 до 1000 метрів. У випадку захищеного приміщення вона значно зменшиться до кількох метрів. Для збільшення покриття сенсорна мережа використовує багатоступеневий механізм передачі даних. Іншими словами, вузли сенсорної мережі можуть передавати і приймати дані. Вузол-джерело, який є першим вузлом сенсорної мережі, доставляє дані до сусіднього вузла для передачі на шлюз. На шляху до шлюзу сусідній вузол передає дані іншому сусідньому вузлу. Поки дані не досягнуть шлюзу, місця призначення, пересилання повторюється. Існує можливість адаптувати протоколи і деякі методи реалізації БСМ до існуючих конструкцій і технологій бездротових і дротових комп'ютерних мереж. Тим не менш, самоорганізація, самоадаптація, низька енергія вузла і хиткі лінії передачі є характерними рисами БСМ.
слайд 4
У другому розділі розглядається необхідність синхронізації часу в бездротових сенсорних мережах, проблеми та обмеження, притаманні синхронізаціїї в БСМ, основні вимоги до неї.
Нестабільна природа бездротової передачі даних є однією з відмінностей бездротових мереж від звичайних дротових мереж. Зв'язок між вузлами в бездротових мережах схильний до перешкод і перекриття, що призводить до збоїв сигналу. Звичайна мережа - це надійна дротова мережа, в якій втрата даних відбувається лише внаслідок перевантаження. Передавач даних модифікує трафік, що передається, відповідно до сценарію втрати даних, згідно з принципом управління потоком. Відправник сповільнює передачу, коли відбувається втрата даних. І відправник збільшує швидкість передачі, коли дані не втрачені. Оскільки на перевантаження, перешкоди і блокування припадає більшість втрат даних в сенсорних мережах, такі стратегії управління потоком більше не підходять для БСМ. Зменшення швидкості передачі саме по собі не вирішить проблему; натомість, це погіршить продуктивність мережі. Адаптивне управління потоком пропонується як вирішення проблеми погіршення продуктивності мережі в ситуаціях нестабільної передачі. Адаптивне управління потоком досліджує першопричину втрати пакетів і змінює швидкість передачі. Для досягнення високої стабільності мережі, беручи до уваги відстань передачі та пропускну здатність, середній час, відповідно до якості зв'язку та кількості помилок передачі, пріоритетом є оптимальна швидкість передачі даних між вузлами. Вимоги до схем синхронізації для сенсорних мереж:
Обмеження, що накладаються бездротовою мережею, забезпечують дотримання ряду специфікацій при розробці методів синхронізації часу. Як правило, будь-який метод синхронізації оцінюється за допомогою параметрів, перелічених нижче:
Точність
Надійність
Масштабованість
Енергоефективність
Довговічність
Вартість,
Сфера застосування,
Затримка
слайд 5
Кілька алгоритмів синхронізації часу використовують обмін повідомленнями. Недетерміновані затримки, такі як тривалість доступу та поширення, ускладнюють точну синхронізацію вузла-одержувача з вузлом-джерелом, якщо один вузол доставляє пакет з часовою міткою.
Наступні компоненти зазвичай спричиняють помилки синхронізації:
- Час отримання
- Доступ
- Поширення
- Час передачі
У третьому розділі обговорюються методи синхронізації часу для бездротових сенсорних мереж, а також їх переваги та недоліки. Також розглянуто класифікацію цих протоколів.
Почнемо з розгляду підходів до синхронізації даних в мобільних сенсорних мережах. Один з найбільш поширених підходів - це метод часової синхронізації, що базується на синхронізації часових міток даних, отриманих з різних джерел. Цей метод використовується в багатьох дослідженнях та проектах, оскільки його можна легко реалізувати та забезпечити стабільну синхронізацію. Для реалізації цього методу використовуються різні алгоритми, такі як RBS (Reference Broadcast Synchronization) та TPSN (Timing-sync Protocol for Sensor Networks).
Інший підхід - це метод синхронізації за допомогою калібрування, що передбачає візуальне калібрування датчиків та корекцію затримок у зборі даних. Цей метод зазвичай використовують у тих випадках, коли потрібно синхронізувати дані з декількох датчиків, що знаходяться на одному пристрої. Прикладом цього можуть бути віртуальні тестові стенди для автомобілів, де використовуються датчики з різних частин автомобіля.
Ще один підхід - це метод синхронізації на основі аналізу сигналів, що передбачає аналіз часових сигналів, що отримані з різних джерел, та визначення затримок між ними. Для цього використовуються різні методи, такі як хвильова кореляція, спектральний аналіз та інші.
На наступних слайдах представлені деякі з протоколів синхронізації, їх переваги та недоліки
Слайд 6
Перший з протоколів про який йде мова це Довідкова синхронізація трансляції Reference Broadcast Synchronization, RBS.
RBS - це розподілений алгоритм, який використовує опорний вузол для синхронізації всіх вузлів мережі. У RBS еталонний вузол транслює повідомлення про синхронізацію, а всі інші вузли підлаштовують свої годинники на основі різниці в часі між отриманим повідомленням та їхнім локальним годинником. RBS масштабується і не вимагає стабільної деревоподібної структури, але вона вразлива до збоїв вузлів і затримок зв'язку.
RBS дозволяє вузлам синхронізувати свої годинники з роздільною здатністю, необхідною для таких додатків, як бездротова мережа. RBS дозволяє вузлам, які отримують пакети синхронізації, використовувати час прибуття пакета як точку відліку для синхронізації годинника, а не передавати часову мітку, як у випадку з такими протоколами, як Network Time Protocol. RBS усуває більшість невизначеностей затримки, пов'язаних зі звичайними протоколами синхронізації часу, передаючи мітку часу тільки на приймачі, оскільки більша частина недетермінованого часу поширення, пов'язаного з передачею пакета по бездротовому каналу, лежить між структурою пакета і передавачем відправника (наприклад, затримка в черзі відправника, затримка при з'ясуванні МАС-адреси і т.д.). Час прибуття цих маячків використовується як орієнтир для визначення часових зсувів між вузлами, що посилають маячки, і вузлами, що приймають. Основна мета цього алгоритму - позбутися недетермінованого часу передачі. Недетерміновані затримки розповсюдження та прийому є єдиним джерелом похибки в цьому підході. Припущення, що радіус дії радіостанції обмежений і що маяк передає сигнал на всі вузли одночасно, дозволяє нам ігнорувати помилки, спричинені затримкою поширення. Отже, єдиним джерелом неточності в цій системі є час прийому. За допомогою цієї техніки можна досягти точності в декілька мкс.
Слайд 7
Наступним протоколом є Протокол синхронізації таймінгів для сенсорних мереж (Timing-Sync Protocol for Sensor Networks, TPSN).
TPSN - це розподілений алгоритм, який використовує ієрархічну структуру для синхронізації вузлів. У TPSN вузли організовані в деревоподібну структуру, і кожен вузол синхронізується зі своїм батьківським вузлом. Кореневий вузол відповідає за трансляцію повідомлення про синхронізацію всім вузлам мережі. TPSN досягає високої точності та масштабованості, але вимагає стабільної деревоподібної структури, що може бути неможливим у MSN.
Ця техніка синхронізації складається з двох фаз; фаза виявлення рівня та фаза синхронізації.
• На фазі виявлення кожному вузлу присвоюється рівень; лише одному вузлу присвоюється рівень 0, і він називається кореневим вузлом.
• На другій фазі вузол рівня n синхронізується з вузлом рівня n-1, і до кінця цієї фази досягається загальномережева синхронізація. Знову ж таки, кореневий вузол починає фазу синхронізації, надсилаючи пакет time_sync. Вузол A рівня n синхронізується з вузлом B рівня n-1 за допомогою двостороннього обміну повідомленнями. Вузол A відправляє пакет разом із місцевим часом передачі T1. Вузол B приймає пакет в момент часу T2, який можна обчислити як вказано на формулі ліворуч де Td є затримкою розповсюдження, а Δ є відносним зміщенням тактової частоти між вузлами, і обидва вважаються постійними протягом часу обміну повідомленнями. Вузол B чекає випадковий час і відповідає назад на вузол A через пакет підтвердження в момент T3, який включає значення T1, T2, T3 і номер його рівня. Як тільки вузол A отримає цей пакет в T4 , він може обчислити Δ і Td наступним чином і синхронізуватися з вузлом В Цей метод синхронізації всіх вузлів на рівні n до вузлів на рівні n-1 триває до тих пір, поки всі вузли в мережі не синхронізуються. Порівнюючи TPSN з RBS, TPSN має більше накладних енергетичних витрат, ніж RBS. Пакети, надіслані для вибору кореневого вузла, і ті, що надіслані на фазі виявлення рівня, вважаються накладними витратами. Цей вид накладних витрат скорочує термін служби мережі, особливо якщо кореневі вузли так часто гинуть у мережі, і весь метод синхронізації повинен бути повторений. Ми виявили, що RBS та TPSN працюють дуже добре з точки зору точності. Точність їх становить кілька мікросекунд. Оскільки надсилання та отримання пакетів є найбільш енергоємним завданням при синхронізації мережі, кількість пакетів, необхідних для синхронізації пари вузлів, може бути використана для оцінки енергоефективності.
Слайд 8
FTSP - це інший тип синхронізації між відправником і одержувачем. Цей протокол схожий на TPSN, але вирішує деякі проблеми TPSN. Спільними рисами є структура кореневого вузла і синхронізація всіх вузлів з коренем.
Всі отримувачі отримують дані синхронізації часу від кореневого вузла через одиночну радіопередачу. Коли повідомлення надсилається відправником, воно має всесвітню позначку часу. Коли повідомлення отримано, одержувач записує місцевий час. Одержувач може визначити часовий зсув, отримавши як час передачі відправника, так і свій власний час. Як і в TPSN, сторони відправника і отримувача повідомлення позначаються часом MAC-рівня. Для забезпечення високої точності необхідна компенсація різниці в часі. FTSP використовує для цього лінійну регресію.
Великі багатокористувацькі мережі є цільовою аудиторією для FTSP. Корінь відповідає за підтримання загального часу мережі і динамічно обирається та переобирається на регулярній основі. Приймаючі вузли організовані спеціально для передачі даних про час між усіма вузлами і синхронізуються з кореневим вузлом. Замість деревовидної топології, як у TPSN, структура мережі є комірчастою.
Переваги FTSP
FTSP має низку переваг над TPSN, які вона вдосконалила. Хоча TPSN пропонував протокол для багатовузлової мережі, йому було важко адаптуватися до змін у топології. Якщо кореневий вузол або топологія змінювалися, TPSN повинен був перезапустити крок виявлення рівня. Це призведе до збільшення мережевого трафіку і накладних витрат.
Для того, щоб впоратися з відмовами каналів і вузлів, FTSP використовує переповнення повідомлень синхронізації, що робить його надійним. Крім того, переповнення дозволяє динамічні топологічні модифікації. Динамічна топологія необхідна, оскільки протокол передбачає, що кореневий вузол повинен періодично переобиратися. Подібно до TPSN, FTSP пропонує мітку часу на рівні MAC, що значно підвищує точність і знижує джиттер. Всі помилки будуть видалені, за винятком часу розповсюдження. Для обчислення дрейфу і зсуву синхронізації використовуються декілька міток часу і лінійна регресія.
Відображаються графіки пакетів даних FTSP. Спочатку йде преамбула, потім байти синхронізації, дані, а потім CRC. Суцільна лінія на рисунку представляє байти в буфері, а пунктирні лінії - фактичні байти в пакеті. Приймач налаштовується на несучу частоту, як тільки передавач надсилає байти преамбули. Отримавши біти синхронізації, приймач може визначити бітовий зсув, необхідний для точного відтворення повідомлення. На краях байтів синхронізації знаходяться мітки часу.
Основні переваги FTSP включають гнучкість у динамічній зміні топології, стійкість до відмов вузлів і з'єднань, а також точне відмічання часу на рівні MAC. Для полегшення мережевої синхронізації, коли всі вузли синхронізуються з кореневим вузлом, він пропонує протокол низько-швидкісного переповнення.
Слайд 9.
Корисність або доступність сенсорної мережі встановлюється для задоволення запитів користувачів шляхом об'єднання даних з кожного датчика для отримання єдиного результату. Для завершення цієї операції датчики повинні узгодити концепцію, наприклад, час, щоб виконати цю операцію. Шляхом синхронізації локальних годинників на кожному активному датчику (учаснику) або шляхом трансляції штампу, всі активні датчики (учасники) можуть бути обгорнуті в єдину часову шкалу. У таблиці нижче порівнюються різні методи синхронізації часу для БСМ на основі ряду важливих критеріїв, включаючи точність, енергоефективність, мобільність і складність.
Більшість бездротових мереж включають неявний критерій, відомий як енергоефективність, якого необхідно дотримуватися і який змінюється залежно від попиту. Ця вимога, наприклад, змушує вузли сенсорних мереж якомога частіше переходити в сплячий режим, різко обмежуючи енергію, доступну для синхронізації та інших операцій. Розмір датчиків на батареях є основною причиною цього обмеження. Як наслідок, менше енергії генерується і зберігається.
Точність мережевого часу визначається тим, як він порівнюється з еталонним часом. Іншими словами, це вимірювання точності синхронізації. У випадку абсолютної точності, високоточний протокол пропонує високу точність. Це означає, що час, синхронізований у мережі, відхиляється від зовнішнього еталонного часу лише незначно (наприклад, UTC). Коли мова йде про відносну точність, це стосується ситуації, коли вважається, що набір синхронізованих вузлів має відносно помірне максимальне відхилення.
Обчислювана складність: Бездротові мережі часто мають обмежені енергетичні ресурси та фізичні можливості. Отже, якщо розрізняти обчислювальну вартість протоколу (наприклад, вимоги до виконання та пам'яті) і складність повідомлень, то протокол синхронізації може виявитися корисним для багатьох застосувань (кількість повідомлень, якими обмінюються під час синхронізації).
Мобільні мережі: У мобільній мережі датчики можуть переміщатися і зв'язуватися з іншими датчиками лише тоді, коли вони перебувають у межах свого географічного діапазону. Діапазон зв'язку, який мобільний датчик може використовувати для успішного зв'язку та обміну повідомленнями з іншими датчиками, називається зоною досяжності. Змінити топологію може бути складно, оскільки це вимагає перерахунку околиць або кластерів і ресинхронізації вузлів.
Слайд 10.
Висновки
Різниця в часі надсилання, доступу, розповсюдження та отримання є основною проблемою для методів синхронізації в усіх бездротових мережах. Механізм синхронізації набагато ефективніший, якщо будь-яку з них можна уникнути або правильно передбачити. Після порівняння RBS, TPSN і FTSP було обговорено переваги кожної процедури. Насамкінець було наведено промисловий кейс та детальне пояснення протоколу.
У цьому дослідженні було розглянуто значення синхронізації, недоліки БСМ у синхронізації, основні методології синхронізації та принципи синхронізації.
За різними характеристиками методи синхронізації часу в БСМ класифікуються. З точки зору точності, надійності, енергоефективності та складності, представлено огляд та аналіз сучасних методів синхронізації часу для бездротових сенсорних мереж. Підкреслено їх переваги та недоліки. Згідно з дослідженням, залежно від особливостей та умов використання БСМ, замість оптимальних методів синхронізації у всіх ситуаціях застосовуються компромісні рішення.
Дякую за увагу !
Готовий вислухати Ваші питання.