Реферат

Вступ

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

1. Актуальнiсть теми

Основними обмеженнями при використанні сенсорних мереж є:

  • Автономнiсть — бездротові сенсорні мережі повинні розгортатися на віддалених важкодоступних територіях, де неможливо забезпечити доставку електроенергії.
  • Час життя — замінити батареї на сенсорних вузлах багато коштує та вимагає багато часу.
  • Вартість — бездротові сенсорні мережі можуть складатися із тисяч та десятків тисяч вузлів.
  • Форм-фактор — розміри сенсорних вузлів повинні бути невеликими [1].

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

2. Мета та завдання дослідження, заплановані результати

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

Основні завдання дослідження:

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

3. Наукова новизна в області застосування

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

4. Загальна постановка проблеми

Розглянемо формальну постановку проблеми. Нехай дана початкова послідовність виду

, (1)

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

, (2)

причому максимальна похибка такого перетворення не повинна перевищувати деякий заданий порігE:

, (3)

В якості функціоналу F буде виступати наш алгоритм компресії. Основними проблемами при визначенні алгоритму є:

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

4.1 Основні алгоритми стиснення чисельних даних

Перед вибором алгоритму необхідно провести аналіз існуючих методів компресії числових даних. Їх можна розбити на 3 групи:

  • словникове стиснення;
  • статистичне кодування;
  • різні методи попередньої обробки даних [2].

Розглянемо кожну групу докладніше.

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

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

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

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

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

4.2. Розглянуті алгоритми стиснення

Для подальшого дослідження було обрано 3 алгоритми:

  • пакування біт. Основна ідея пакування біт полягає в тому, що для кодування значень елементів послідовності можна використовувати меншу кількість біт. Нова бітова довжина для значень обчислюється за такою формулою:

    , (4)

    де max — максимальне значення в послідовності, min — мінімальне значення в послідовності, dx — крок зміни елементів.

    • Схема роботы механiзму пакування бiт
    Рис.1 Схема роботы механiзму пакування бiт

    Припустимо необхідно закодувати послідовність чисел short, причому відомо, що числа варіюються від 100 до 200. Таким чином, замість стандартних 16 біт нам досить використовувати тільки 7.

  • цілочисельне вейвлетне перетворення 5/3. Був обраний саме цей вид вейвлетних перетворень, тому що він дозволяє оперувати тільки цілими числами, а також добре працює в більшості випадків [5]. Вихідна послідовність (1) поділяється на дві: — що містить непарні елементи; — що містить парні. Після цього формуються дві нових послідовності и за такими формулами:
    , (5)
    , (6)
  • алгоритм Рамера-Дугласа-Пеккер. Сутнiсть алгоритму полягає в тому, щоб зменшити число точок кривої, апроксимованої великою серією точок. Стиснення даних осягається за рахунок відкидання точок, які можуть бути відновлені iз заданою точністю E [6].
Демонстрацiя роботы алгоритму Рамера-Дугласа-Пеккера
Рис.2 Демонстрацiя роботы алгоритму Рамера-Дугласа-Пеккера
Розмiр аниiмацiї: 8 Кбайт
Кількість кадрiв: 5
Експозиція кадру: 1,5 сек на кадр
Кількість циклів повторення: 7

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

4.3. Параметри сенсорних даних

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

  • передається безліч значень (50-100) від декількох датчиків (3-5). У цьому випадку доцільно стискати послідовність від кожного датчика окремо.
  • передається кілька значень (2-5) від великої кількості датчиків (10-20). У цьому випадку стискати дані кожного  датчика окремо неможливо через дуже маленьку довжину вихідної послідовності. Велику ефективність дає підхід,  при якому послідовності будуть формуватися з одноразових вимірювань різних датчиків [7].

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

Висновки

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

На рис.3 зображено загальну блок-схема алгоритму роботи такої автоматизованої системи.

Загальна блок-схема алгоритму роботи автоматизованої систем
Рис.3 Загальна блок-схема алгоритму роботи автоматизованої системи
На підставі вищевикладеного можна зробити висновок, що застосування алгоритмів компресії може зменшити енергоспоживання сенсорних вузлів. Показано, що в залежностi від вихідних даних необхідно використовувати різні параметри алгоритмів компресії. Таким чином, напрямком подальшої роботи є розробка та реалізація правил вибору алгоритму і його параметрів для різних алгоритмів компресії сенсорних даних, а також їх перевірка на реальних даних.

Список літератури:

  1. Садков А.В. Беспроводные сенсорные сети. Курс лекций, 2007 [Электронный ресурс]. Режим доступа: http://www.sumkino.com/wsn/course/

  2. Смирнов М.А., Обзор применения методов безущербного сжатия данных в СУБД, 2003 [Электронный ресурс]. — Режим доступа: http://compression.ru/download/articles/db/smirnov_2003_database_compression_review.pdf

  3. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: ДИАЛОГ—МИФИ, 2002. — 384 с.

  4. Статистическое двоичное кодирование источника [Электронный ресурс]. — Режим доступа: http://edu.dvgups.ru/METDOC/GDTRAN/YAT/TELECOMM/TEOR_PERED_SIGN/METOD/HARAK_SV/Stroev_3.htm

  5. Michael D. Adams, Faouzi Kossentini Reversible Integer-to-Integer Wavelet Transforms for Image Compression: Performance Evaluation and Analysis, 1999 [Электронный ресурс]. — Режим доступа: http://www.ece.uvic.ca/~frodo/publications/phdthesis.pdf

  6. David Douglas & Thomas Peucker, Algorithms for the reduction of the number of points required to represent a digitized line or its caricature [Электронный ресурс]. — Режим доступа: http://utpjournals.metapress.com/content/fm576770u75u7727/?genre=article&id=doi%3a10.3138%2fFM57-6770-U75U-7727

  7. Е.Г. Краморенко, М.В. Привалов, "Понижение энергопотребления сенсорных сетей за счет предварительной обработки данных", Информационные управляющие системы и компьютерный мониторинг 2013/ Сборник материалов к IV Всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых. — Донецк, ДонНТУ — 2013, с. 364 — 369.

Резюме Автобіографія