Бездротові сенсорні мережі
Бездротова сенсорна мережу (БСМ) - це бездротова система, яка являє собою розподілену, самоорганізовану і стійку до
відмов окремих елементів мережу, вузлами якої є спеціальні пристрої - моти. БСМ - це бездротова мережа, передача інформації в
якій проводиться від одного вузла до іншого до тих пір поки пакет даних не досягне віддаленого шлюзу. Від шлюзу інформація надходить на
головний комп'ютер, який виконує обробку інформації або передає її далі.
Мот являє собою плату розміром звичайно не більше одного кубічного дюйма. На платі розміщуються процесор, пам'ять - флеш і оперативна,
цифроаналогові і аналого-цифрові перетворювачі, радіочастотний приймач, джерело живлення і датчики. Датчики можуть бути
найрізноманітнішими; вони підключаються через цифрові та аналогові коннектори. Частіше за інших використовуються датчики температури, тиску, вологості,
освітленості, вібрації, рідше - магнітоелектричні, хімічні (наприклад, які вимірюють вміст CO, CO2), звукові і деякі інші [1]. Набір
застосованих датчиків залежить від функцій, які виконоють бездротові сенсорні мережамі. Живлення мота здійснюється від невеликої батареї. Моти
використовуються тільки для збору, первинної обробки та передачі сенсорних даних. Зовнішній вигляд мотів, що випускаються різними виробниками,
наведено на рис. 6.1
Рисунок 6.1 – Зовнішній вигляд мотів.
Основна функціональна обробка даних, що збираються мотами, здійснюється на вузлі, або шлюзі, який являє собою досить потужний
комп`ютер.Проблема отримання сенсорної інформації, яка збирається мотами, вирішується таким чином. Моти можуть обмінюватися між собою інформацією
за допомогою прийомопередатчиков, що працюють у радіодіапазоні. Це, по-перше, сенсорна інформація,яка прочитується з датчиків, а по-друге, - інформація
про стан пристроїв і результати процесу передачі даних. Інформація передається від одних мотів іншим по ланцюжку, і в підсумку найближчі до шлюзу
моти скидають йому всю акумульовану інформацію. Якщо частина мотів виходить з ладу, робота сенсорної мережі після реконфігурації повинна продовжуватися.
Але в цьому випадку, природньо, зменшується число джерел інформації[2].
Переваги технологій бездротових сенсорних мереж можуть бути ефективно використані для вирішення різних прикладних задач, пов'язаних з
розподіленим збором, аналізом і передачею інформації [3]. Бездротові сенсорні мережі - це нова перспективна технологія, і всі пов'язані з нею
проекти в основному знаходяться у стадії розробки. Зазначимо основні сфери застосування даної технології:
- системи оборони і забезпечення безпеки;
- контроль навколишнього середовища;
- моніторинг промислового обладнання;
- охоронні системи;
- моніторинг стану сільськогосподарських угідь;
- управління енергопостачанням;
- контроль систем вентиляції, кондиціонування і освітлення;
- пожежна сигналізація;
- складський облік;
- спостереження за транспортуванням вантажів;
- моніторинг фізіологічного стану людини;
- контроль персоналу і т.д.
Представлений список мізерно малий і практично не обмежений. З досить великої кількості прикладів використання бездротових сенсорних мереж виділимо два.
Виробництво вина - заняття, що вимагає обліку величезної кількості різноманітної інформації. Вино купується і продається не на вагу або обсяг (як, наприклад,
зернові або овочі), і його ціна багато в чому залежить від місця, років вирощування і збору. На якість вина впливає безліч чинників, і досвідчені винороби
скурпульозно враховують при цьому найменші нюанси, щоб домогтися найкращого смаку напою. Але якщо використовувати сенсорні мережі, то можна «засіяти» виноградник
бездротовими датчиками і безперервно відстежувати температуру, вологість та інші параметри, важливі для дозрівання кожної лози. У кількох господарствах у долині
Вілламет (штат Орегон) дослідники Intel розгорнули дослідну сенсорну мережу. Керує проектом професійний психолог Річард Беквіт (Richard Bechwith),який
використовує дослідницьку технологію, відому як «спостереження за учасниками». Він спостерігає, з одного боку, за експертами, які збирають інформацію
з сенсорів, розміщених на плантації, а з іншого - за самими виноградарями, щоб зрозуміти, які критерії в області виноградарства важливі для тих та інших і як
ця інформація ув'язується воєдино [4].
Прикладом ще одного реалізованого проекту є розгортання сенсорної мережі на базі військово-повітряних сил США у Флориді. Система продемонструвала
хороші можливості по розпізнаванню різних металевих об'єктів, в тому числі рухомих. Застосування сенсорної мережі дозволило виявляти проникнення
людей і автомобілів в контрольовану зону і відслідковувати їх переміщення. Для вирішення цих завдань використовувалися моти, оснащені магнітоелектричними та
температурними датчиками. В даний час масштаби проекту розширюються, і бездротова сенсорна мережа встановлюється вже на полігоні розміром 10 000x500 м.
Відповідне прикладне програмне забезпечення розробляється кількома американськими університетами [2].
Однією з основних проблем БСМ є обмежена ємність батарей, встановлених на мотах. Замінювати батареї на мотах, в більшості випадків - завдання досить
складне. Саме тому питаннями зменшення енерговитрат займається велика кількість людей. Тематика робіт простягається від вузькоспеціальних питань,
пов'язаних зі створенням окремих компонентів об'єктів мережі (прийомопередатчиков, мікроконтролерів, датчиків і т.д.) з низькою ціною і низьким енергоспоживанням до проблем,
які виникають при експлуатації сенсорних мереж (питання пов'язані з організацією роботи мережі, розробка програмного забезпечення тощо) [5]. Однак найбільш важливою
проблемою є задача передачі даних. Основними проблемами в цій області є:
- зменшення циклу прийому і передачі даних;
- знаходження оптимальних маршрутів передачі даних;
- вибір топології мережі;
- стійкість до зміни топології;
- і т.д..
Хоча на даний момент вже існує велика кількість розробок, але всі вони не є повноцінними, оскільки їх не можна застосувати для будь-якого кола завдань.
Для кожної конкретної задачі, необхідно організувати свій підхід до вирішення. Саме тому суть даної роботи полягає в розробці нового протоколу, який
буде заснований на мурашиних алгоритмах. Основним завданням для даного протоколу є пошук оптимального маршруту передачі даних від мотів до основного комп'ютера,
а також можливість вибору оптимального маршруту у випадку виходу одного або декількох мотів з ладу.
Протокол СТР
Даний протокол забезпечує передачу даних одному з кількох можливих приймачів даних, тим самим забезпечуючи зв'язок багато до одного на мережевому рівні.
БСМ зазвичай утворює деревоподібну структуру, корінням якої є шлюзи, а листям - моти. CTP використовує кадри маршрутизації для оновлення та побудови
дерев мережі.
На рис.6.2 наведено приклад дерева мережі. Шлюз є коренем, а інші вузли утворюють безлічі маршрутів, які підключаються до цього кореня. У СТР не використовується
адресація, тому вузол не відправляє пакет певного кореня, а неявно вибирає корінь дерева, за допомогою вибору адресата наступного пересилання.
Рисунок 6.2 – Приклад дерева колекції.
Протокол CTP використовує 2 формата кадру: кадр даних та кадр маршрутизації. CTP спроектований для мереж з відносно низьким трафіком, тому що смуги пропускання
каналу має бути достатньо для пересилання кадрів маршрутизації в той час, коли передаються кадри даних.
CTP використовує очікувану кількість пересилань (ETX) як градієнт маршрутизації. Корінь дерева має ETX 0. ETX вузла дорівнює ETX батьків плюс ETX зв'язку з
батьком. У кінцевому підсумку СТР, враховуючи поточний маршрут, вибирає маршрут з меншим значення ETX. ETX - представляється як 16-розрядне десяткове речове
число з фіксованою крапкою з точністю до десятих. Наприклад ETX зі значенням 45, представляється як ETX 4.5, а ETX зі значенням 10 представляється як ETX 1.
Протокол Tymo
Tymo - це реалізація протоколу Dymo в TinyOS [3], який є протоколом маршрутизації для мобільних пристроїв у однорангових мережах. Спершу протокол розроблявся
для пошуку маршрутів поверх IP рівня. Оскільки, протокол Dymo, є реактивних протоколом, то він явно не зберігає топологію мережі. У разі необхідності відправлення
даних вузол встановлює маршрут до місця призначення. За рахунок малого обміну інформацією про маршрутизації, скорочується мережевий трафік, що дозволяє економити смугу
пропускання. За рахунок малих обсягів збереженої інформації про маршрутизації, Dymo легко вбудовується в обмежену пам'ять мотів.
Коли вузлу необхідно отримати маршрут, він поширює Route Request (RREQ) - пакет запитучий маршрут між відправником та одержувачем. Цей пакет
поширюється по всій мережі або в межах деякого числа сусідніх вузлів. Коли пакет досягає мети (або вузол має новий маршрут до мети), вузол відправляє
Route Replay (RREP). Ця відповідь дуже схожа на Route Request, відмінність полягає лише в тому, що пакет має одноадресний маршрут і не потребує відповіді.
Коли вузли отримують RREQ або RREP, вони зберігають в кеші інформацію про відправника, таким чином вони знають дорогу до джерела отриманого пакету, який може бути
використаний пізніше (якщо шлях не застарілий), без відправлення RREQ. Вузли мають можливість накопичувати шлях супроводжуваний пакетом у пакеті безпосередньо. Таким
чином коли вузли відправляють RREQ або RREP в пакеті відповіді можуть отримати інформацію більше ніж шлях між двома вузлами.
Коли маршрути не використовуються протягом тривалого часу, вони видаляються. Якщо вузол запитує відправку пакету через віддалений маршрут, то генерується Route
Error (RERR) повідомлення, щоб попередити вузол відправник (та інші вузли), що запитаний маршрут більше не доступний. В якості ще одного механізму
обслуговування маршруту, Dymo використовує порядкові номери та лічильники переходів для визначення повноцінності та якості маршруту.
Огляд систем моделювання БСМ
Кожна мережа вимагає свого підходу до розробки. Саме тому при розробці сенсорних мереж і програмного забезпечення до неї велике значення мають системи
моделювання. Системи моделювання дозволяють розробляти апаратне і програмне забезпечення для мотів зі значно меншими витратами, ніж у випадку
використання реальних пристроїв. Так само вони дозволяють варіювати різними параметрами, що надає інформацію, необхідну для прийняття рішення про
переваги тих або інших параметрів в заданій обстановці. Ще більш корисними є системи моделювання при розробці та тестуванні протоколів передачі
даних.
На сьогоднішній час існує велика кількість систем моделювання як спеціалізованих (TOSSIM, SWAN, Em *, GloMoSim і т.д.), так і систем загального призначення
(NS2, OMNet + + і т.д.).
TOSSIM - це симулятор додатків TinyOS. Він є бібліотекою TinyOS. Tossim - симулятор дискретних подій. Подія повідомляє про отримання даних від сенсора,
про спрацьовування таймера, про передачі пакетів даних або про завершення обчислень. Звідси випливає, що TOSSIM - емулює події для бездротових сенсорних систем,
в яких моти працюють під управлінням TinyOS.
TOSSIM встановлюється на комп'ютер разом з набором інструментальних засобів, необхідних для створення, компіляції, встановлення та налагодження програм для бездротових
сенсорних мереж. Робота з даними інструментальними засобами здійснюється через командний рядок.
Основною перевагою TOSSIM є те, що емулятор дозволяє моделювати роботу додатків, які написані для реальних мотів. Компілятор TOSSIM `а замінює
кілька низькорівневих компонентів програми, які взаємодіють з апаратними ресурсами реального мота, компонентів, що взаємодіють з програмними
реалізаціями цих пристроїв в емуляторі.
TOSSIM перетворює переривання комп'ютера в події емулятора і вибудовує їх у чергу; ця черга подій емулятора управляє виконанням програми TinyOS для
окремо змодельованого мота. Виникаючі події викликає обробник переривання, який посилає сигнали подіям і викликає команди TinyOS, імітуючи те, що
відбувається в реальних мотах. Ці події і команди TinyOS запускають завдання та ініціюють подальшу генерацію подій емулятора.
Ще одна з широко відомих середовищ моделювання - це середовище AnyLogic. Середа AnyLogic дозволяє використовувати різні парадигми моделювання (безперервне і
дискретно-подієве моделювання, багатоагентний підхід), а також комбінувати їх. Важливими перевагами системи є:
- Об'єктно-орієнтований підхід до моделювання;
- Візуальне середовище розробки з багатою функціональністю;
- Можливість використання мови Java.
У системі AnyLogic введено поняття активного об'єкта (АО) - розширення класичних об'єктів, які використовуються в об'єктно-орієнтованих мовах
програмування. У AnyLogic активний об'єкт може включати також інші елементи.
Якщо стандартних засобів AnyLogic не вистачає для побудови моделі (або їх використання незручно), є можливість використання мови Java. У найпростішому випадку,
це зводиться до опису дій, вчинених при переході в інший стан, спрацюванні таймера або прихіді повідомлення. Крім того, можна додавати власний
код на Java до активного об'єкту, а також використовувати сторонні бібліотеки. Це робить систему AnyLogic легко розширюваною. [6]
NS2 - відомий симулятор мереж з відкритим кодом. Це система дискретного моделювання подій мережі. NS широко використовується для моделювання протоколів, а також
наукових дослідженнях мереж. Система підтримує ряд популярних мережевих протоколів. Дозволяє створювати моделі дротових і бездротових мереж. Дана система
дозволяє реалізувати практично будь-яку модель за рахунок можливості дописати симулятор. [9]
На основі всього викладеного можна зробити висновок, що на даний момент існує велика кількість засобів, для моделювання БСМ. Всі мають свої плюси і мінуси. Для
поставленої задачі найбільш прийнятним є симулятор TOSSIM. Даний варіант обраний з наступних причин:
- симулятор розроблений спеціально для БСМ;
- емуліруер роботу додатків написані для реальних мотів;
- безкоштовне поширення;
- дозволяє емулювати роботу БСМ під управлінням TinyOS, яка є фактично стандартом для БСМ.
Огляд методів забезпечення взаємодії вузлів БСМ
Для забезпечення взаємодії вузлів БСМ можна використовувати достатньо велику кількість методів, наприклад:
- теорії ймовірності;
- обчислювальної математики;
- теорії стохастичних процесів;
- оптимізаційні алгоритми і т.д.
Розглянемо декілька існуючих методів.
Метод колективної передачі даних. Суть методу полягає в наступному. Після того, як зв'язність мережі різко падає в результаті виходу з ладу вузлів навколо
базової станції вузли, що залишилися, об'єднуються в кластери і передають зібрану інформацію колективно, використовуючи принцип когерентної передачі інформації. Це
значно збільшує відстань, на яку можуть передати вузли і, таким чином, можна очікувати підвищення зв'язності мережі та продовження часу життя. Під часом
життя мережі розуміється період часу до падіння зв'язності нижче певного порогу [10].
Алгоритм багатоланкової передачі даних. Суть алгоритму полягає в тому, що відправка повідомлень з однієї точки мережі до іншої по ланцюжку проміжних вузлів замість
прямої далекої радіопередачі. Для синхронізації вузлів пропонується використовувати періодично повторювану хвилю на розповсюдження повідомлень,яка розходиться
з центру мережі, на додаток до збіжної хвилі передачі даних. Зустрічні хвилі повинні бути рознесені в часі для запобігання перетинів. Оптимальним
є режим, коли управляюча хвиля випромінюється базовою станцією відразу ж після приходу хвилі з даними, бо таким чином максимізується можлива ширина
мережі. Мінімальний допустимий період проходження хвиль залежить від ширини мережі і часу проходу хвилі через один рівень [11].
Метод визначення координат в БСМ. Суть методу полягає в пошуку географічного розташування об'єктів бездротової мережі, що в свою чергу дозволяє спростити
формування, в стандарті ZigBee, таблиць маршрутизації. Для реалізації даного методу використовувалися методи Колмановського фільтрації і методи теорії стохастичних
процесів.
Мурашині алгоритми. Такі алгоритми є широко відомими. Цей метод дає добрі результати при вирішенні задач оптимізації великих розмірів. Досить
добре зарекомендували себе для розрахунків телекомунікаційних та комп'ютерних мереж. В даний час отримані гарні результати для вирішення таких складних завдань,
як задача комівояжера, розфарбування графа, задача оптимізації мережевих трафіків і т.д [12].
Мурашині алгоритми
Ідея мурашиного алгоритму - моделювання поведінки мурах, пов'язаного з їх здатністю швидко знаходити найкоротший шлях від мурашника до джерела їжі і
адаптуватися до мінливих умов, знаходячи новий найкоротший шлях.
1. Перший мураха знаходить джерело їжі (F) будь-яким способом (а), а потім повертається до гнізда (N), залишивши за собою стежку з феромонів (b).
2. Потім мурашки вибирають один з чотирьох можливих шляхів, потім зміцнюють його і роблять привабливим.
3. Мурахи вибирають найкоротший маршрут, бо у більш довгих феромони сильніше випарувалися.
Описане вище представлено на рис.6.3.
Рисунок 6.3 – Приклад пошуку мурахами найкоротшого маршруту(Анімація: об'єм - 29,5 КБ; розмір -114x279; кількість кадрів - 7; затримка між кадрами -
1000 мс; затримка між останнім і першим кадрами - 2000 мс; кількість циклів повторення - 6).
Серед експериментів з вибору між двома шляхами нерівній довжини, що ведуть від колонії до джерела живлення, біологи помітили, що, як правило, мурашки використовують
найкоротший маршрут[6]. Модель такої поведінки полягає в наступному:
* Мураха (так званий «Бліц») проходить випадковим чином від колонії.
* Якщо він знаходить джерело їжі, то повертається в гніздо, залишаючи за собою слід з феромона.
* Ці феромони привертають інших мурах що знаходяться поблизу, які найімовірніше підуть по цьому маршруту.
* Повернувшись у гніздо вони зміцнять феромонних стежку.
* Якщо існує 2 маршрути, то по більш короткомму, за той же час, встигнуть пройти більше мурашок, ніж по довгому.
* Короткий маршрут стане більш привабливим.
* Довгі шляхи, в кінцевому підсумку, зникнуть через випаровування феромонів.
Етапи вирішення задачі за допомогою мурашиних алгоритмів
Для того щоб побудувати відповідний мурашиний алгоритм для рішення якого-небудь завдання, потрібно:
1) представити завдання у вигляді набору компонентів і переходів або набору неорієнтованих зважених графів, на яких мурашки можуть будувати рішення;
2) визначити значення сліду феромона;
3) визначити евристику поведінки мурашки, коли будуємо рішення;
4) якщо можливо, то реалізувати ефективний локальний пошук;
5) вибрати специфічний ACO алгоритм і застосувати для розв'язання задачі;
6) настроїти параметр ACO алгоритму.
Також визначальними є:
- кількість мурашок;
- баланс між вивченням і використанням;
- поєднання з жадібними евристиками або локальним пошуком;
- момент, коли оновлюється феромон.
Передбачається, що надалі реалізація описаного вище алгоритму дозволить створити новий протокол передачі даних у бездротових сенсорних мережах, який дозволить
знаходити найкоротші маршрути доставки пакета, при цьому оптимально розподіляючи потоки інформації по мережі.