Реферат

Введение

Беспроводная сенсорная сеть — распределённая, самоорганизующаяся сеть множества устройств с датчиками (сенсорами), объединенных между собой посредством радиоканала. Область действия таких сетей может составлять от нескольких метров до нескольких километров за счет способности ретрансляций сообщений от одного элемента к другому. Сенсорные данные — данные, полученные с сенсоров (датчиков). Основной их особенностью является то, что чаще всего они имеют численный вид и изменяются в некотором фиксированном диапазоне. В данный момент происходит активное развитие этой технологии, т.к. число потребителей непрерывно увеличивается: в промышленности, жилищно-коммунальном комплексе, домашних хозяйствах, транспорте, охране.

1. Актуальность темы

Основными ограничениями при использовании сенсорных сетей являются:

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

Ограничение по автономности и времени жизни можно решить как техническими средствами (увеличение емкости аккумуляторов, использование компонентов, потребляющих меньше энергии), так и программными (определение времени включения передачи, многозвенная передача, предварительная обработка и сокращение объема данных, необходимых для передачи). Одним из способов решения этой проблемы является компрессия данных.

2. Цель и задачи исследования, планируемые результаты

Целью исследования является повышение эффективности хранения и передачи информации, полученной с сенсоров.

Основные задачи исследования:

  • Рассмотреть алгоритмы сжатия чисельних данных и выбрать наиболее эффективные для компрессии сенсорных данных.
  • Изучить параметры входных данных и их влияние на результат выбранных методов.
  • Разработать автоматизированную систему, которая на основании краткого анализа входных данных будет определять наилучшие параметры алгоритмов для сжатия.

3. Научная новизна в области применения

На данный момент существует достаточно большое количество алгоритмов компрессии данных. Но основным критерием работы этих алгоритмов является коэффициент сжатия. Стоит отметить, что большинство мобильных устройств, выполняющих функции узлов сенсорной сети, не имеют сопроцессора для выполнения операций с вещественными числами. Таким образом, необходимо разработать алгоритм, использующий только целочисленные операции, работающий за приемлемое время и обеспечивающий сжатие данных без их существенного искажения. На текущем этапе данная проблема малоизучена: существуют исследования, показывающие эффективность данного подхода, но работ, занимающихся именно исследованием алгоритмов, — единицы.

4. Общая постановка проблемы

Рассмотрим формальную постановку проблемы. Пусть дана исходная последовательность вида

, (1)

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

, (2)

причем максимальная погрешность такого преобразования не должна превышать некоторый заданный порог E:

, (3)

В качестве функционала F будет выступать наш алгоритм компрессии. Основными проблемами при определении алгоритма являются:

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

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

Перед выбором алгоритма необходимо провести анализ существующих методов компрессии числовых данных. Их можно разбить на 3 группы:

  • словарное сжатие;
  • статистическое кодирование;
  • различные методы предварительной обработки данных [2].

Рассмотрим каждую группу подробнее.

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

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

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

Хотя этот метод достаточно прост, его применение затруднено тем фактом, что составление словаря частоты появления слов в источнике данных так же связано с использованием дополнительной памяти. Более того, при распаковке таких данных придется хранить таблицу статистики для каждого узла сенсорной сети. Использование единой, заранее заданной, таблицы частот нерационально, т.к., скорее всего, это обеспечит плохой коэффициент сжатия ввиду неравномерности входных данных.

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

4.2. Рассмотренные алгоритмы сжатия

Для дальнейшего исследования было выбрано 3 алгоритма:

  • упаковка бит. Основная идея упаковки бит заключается в том, что для кодирования значений элементов последовательности можно использовать меньшее количество бит. Новая битовая длина для значений вычисляется по следующей формуле:
    , (4)

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

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

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

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

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

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

Как уже было замечено выше, сенсорная сеть состоит из узлов, к каждому из которых может быть присоединено несколько датчиков. Основными параметрами выступают количество датчиков, от которых получены значения, и количество этих значений. Таким образом, можно выделить два режима работы:

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

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

Выводы

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

На рис.3 изображена общая блок-схема алгоритма работы такой автоматизированной системы.

Общая блок-схема алгоритма работы автоматизированной системы,
Рис.3 Общая блок-схема алгоритма работы автоматизированной системы

На основании вышеизложенного можно сделать вывод, что применение алгоритмов компрессии может уменьшить энергопотребление сенсорных узлов. Показано, что в зависимости от исходных данных необходимо использовать различные параметры алгоритмов компрессии. Таким образом, направлением дальнейшей работы является разработка и реализация правил выбора алгоритма и его параметров для различных алгоритмов компрессии сенсорных данных, а также их проверка на реальных данных.

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

  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.

Резюме Автобиография Библиотека Ссылки Отчет о поиске Индивидуальный раздел