Назад в библиотеку

Энергоэффективное сжатие данных в беспроводных сенсорных сетях

Авторы статьи: Ranganathan Vidhyapriya,Ponnusamy Vanathi

Автор перевода фрагмента статьи: Е.Г. Краморенко

Описание: Статья описывает разработки и реализацию двух алгоритмов сжатия данных без потерь

Источник: Международный журнал арабских информационных технологий, том 6, № 3, июль 2009 г.

Аннотация

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

Ключевые слова: Беспроводные сенсорные сети; сжатие, маршрутизация, эффективность использования энергии, время жизни, кратчайший путь

1. Введение

Интерес в сфере достижений в области сенсорных технологий и связи был сосредоточен на использовании беспроводных сенсорных сетей, которые образуются множеством небольших неуправляемых сенсорных устройств, которые располагаются бессистемным образом для того, чтобы совместно зондировать физические явления, делая выводы и передавая данные [12]. Энергопотребление является главным препятствием при построении сенсорных сетей. Это фундаментальное ограничение по энергии в дальнейшем накладывает лимиты на все, начиная от скорости зондирования данных и связующей полосы пропускания до размера и веса узла. Большие объемы данных, генерируемые датчиком, делают передачу данных в пределах сети к одному приемнику информации с минимальной задержкой и энергозатратами очень сложной задачей. Агрегация методик, таких как TinyDB [5] и TAG [6], обрабатывает и потребляет собранные данные в пределах сенсорной сети, пересылая лишь небольшое подмножество данных к приемнику. Методики, основанные на запросах, такие как идея направленного распространения с целью фильтрации данных в сети и получения только того, что требуется приложению. Низкоуровневые сетевых технологий были предложены для того, чтобы помочь маршрутизировать данные в сенсорной сети с надеждой на минимизацию дублированных пакетов и минимизация количества хопов, необходимых для доставки данных. Наконец, методы компрессии данных возникают для таких сенсорных сетей [1, 9], при использовании которых, посредством сжатия, уменьшается объем данных и требуется меньшая полоса пропускания, необходимая для передачи данных. В следующем разделе мы рассматриваем другие работы, имеющие отношение к нашей системе. В разделе 3 мы описываем наш алгоритм. Раздел 4 представляет собой анализ наших экспериментальных результатов. В разделе 5 находятся выводы.

2. Работы по теме. Прадхан и соавт. [7] предложили критерий для распределенного сжатия, использующий объединенные источники и канальное кодирование. Этот подход минимизирует количество межузловых сообщений для сжатия с использованием как квантованных источников информации, так и коррелированную стороннюю информацию в каждом отдельном узле. Рабат и соавт. [10] предлагают распределенную сопоставимую архитектуру канала источника сообщений и метод реконструкции, компенсирующий влияние шумовых случайных проекций. Аналогичный подход можно найти в [13], который использует схему сплетенной связи. Хотя утверждается, что он универсален, есть компромисс между задержкой мощностного искажения. Кроме того, они не учитывают корреляцию самих данных. Предлагаемая Вагнером [14, 11] архитектура для распределенного вейвлет-анализа, который устраняет предположение о регулярности сетки. Кроме того, не ясно, как выбрать оптимальный путь для сжатия и не полностью изучена пространственная корреляция. В [2, 3] могут быть найдены некоторые другие работы по распределенному сжатию аудио и видео в беспроводных сенсорных сетях. Другие подходы [13] пытаются разрешить несколько целей, такие как маршрутизация, агрегация, индексирование и хранение и баланс энергии с компрессией. Тем не менее, предыдущие работы не решают проблему сжатия данных с использованием любого протокола маршрутизации в беспроводных сенсорных сетях. Ключевая разница между нашей работой и этими предшествующими исследованиями заключается в том, что мы сосредотачиваем внимание на сжатии данных и на развертывании, например, время жизни сенсорных сетей, которое идентифицирует кратчайший путь в сети для передачи сжатых данных от сенсорных узлов к приемнику.

3. Предложенный метод. Сенсорные узлы распределены случайным образом в области зондирования. Всем узлам в сети назначаются уникальные идентификаторы. Мы предполагаем, что каждый сенсорный узел стационарен после развертывания и способен получать собственную информацию о местоположении с использованием системы глобального позиционирования (GPS). Каждый узел имеет ограниченную энергию батарей, в то время как доступная энергия на стороне приемника может быть относительно неограничена. Методы сжатия данных могут быть классифицированы на две группы, такие как методы сжатие без потерь, который не допускает никаких потерь данных при сжатии, большинстве случаев подходит для таких приложений, как мониторинг состояния здоровья, выполнения программ и исходных кодов и т.д., и методы сжатия с потерями, которые справляются с небольшим количеством потерь данных при сжатии, подходит для некритичных приложений.

В камерных сенсорных сетях, некоторые форматы файлов изображений, в частности, PNG, используют только сжатие без потерь, а другие, как TIFF и MNG, могут использовать либо компрессию с потерями или методы без потерь. GIF использует метод сжатия без потерь, но большинство реализаций GIF не способны представлять полный цвет, поэтому они квантуют изображение (часто со сглаживанием) до 256 или меньшим количеством цветов перед сжатием. Цветовое квантование – это процесс с потерями, но реконструкция цветного изображения, а затем повторное квантование его не производит дополнительных потерь. В случае камерных сенсорных сетей, изображения, сжатые без потерь, занимают меньше места, чем оригинальные, но результаты компрессии скромны, с отношением сжатия в диапазоне 2,5:1. Декомпрессия восстанавливает исходное изображение без потери качества. Изображения, сохраненные в GIF и PNG форматах, сжимаются автоматически, в то время как для файлов TIFF и BMP, пользователь решает, следует ли сжимать файл. Сжатие с потерями позволяет достичь более высокого отношение сжатия, чем без потерь, но за счет качества изображения, с потерями под контролем пользователя.

Сжатие с потерями зависит от схемы сжатия и того, как она реализуется. Методы сжатия, которые используются в этой статье, основаны на методах сжатия без потерь, таким образом, облегчая полное извлечение данных. Мы предложили два метода сжатия, а именно – энтропийное кодирование с помощью кодовой книги (Entropy Encoded Codebook Compression, EECC) и конвейерное сжатие кодовой книги (Pipelined Codebook Compression, PCC), которые в основном построены на методах сжатия кодовой книги.

Постановка задачи исследования.Пусть дана исходная последовательность вида

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

3.1. Кратчайший путь маршрутизации. Перед отправкой данных к приемнику, узел должен начать процесс обнаружения соседа, который является адресом всех узлов, которые способны передавать данные к источнику. Специальный механизм флудинга принимается при обнаружении соседа. Решение состоит в том, чтобы объединить скорость вещания с доступной энергией на промежуточных узлах. Когда промежуточный узел получает широковещательное сообщение, он сначала проверяет доступную энергию. Если доступная энергия меньше энергии операции (например, двойная энергии передачи пакета), это означает, что узел не имеет достаточно энергии, чтобы брать больше задач передачи. Узел просто отбрасывает широковещательное сообщение, если узел имеет достаточно энергии; узел передает широковещательно сообщение соседним узлам.

3.1.1. Алгоритм кратчайшего пути. Алгоритм Дейкстры поиска кратчайшего маршрута используется для расчета пути между приемником и источником. Пусть имеется граф G = (N, E), с положительным весом Dij всех ребер (i, j є N), начальным узлом S и множеством P перманентно отмеченных узлов, кратчайший путь от начального узла S до любого другого узла j показан на рисунке 1:

Инициализируем P = {S}, DS = 0, и Dj =dSj для jєN
Найти i є P, такое что Di = min Dj, j є P
Устанавливаем Р = PU{i}.
Если P содержит все узлы, то
останов, алгоритм завершен.
Для всех jєP
Устанавливаем Dj = min [Dj, Di + dij]
Перейти к шагу 1.
Рисунок 1. Алгоритм поиска кратчайшего пути

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

ID узла n-битное сенсорное измерение Метка времени
Рисунок 2. Элемент данных, производимых сенсорным узлом.

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

3.2.1. Размер словаря. Метод сжатия по кодовой книге заменяет строки символов отдельными кодами. На старте, кодовая книга инициализируется 256 записями. Наши эксперименты сосредоточены на кодовых книгах 256, 512 и, для сравнения, неограниченным количеством записей. Строки кодируются 9 битами, а кодовая книга имеет менее 512 записей, 10 битов, пока она имеет меньше 1024 записей, и т.д. При небольших блоках данных, нет почти никакой разницы между размерами словаря.

Для адаптации методики кодовой книги для сенсорного узла, сбалансированы три основных взаимосвязанных пункта: размер словаря, размер данных, которые будут сжаты, а также протокол, по которому проводится заполнение словаря. Во-первых, ограничения по памяти требуют, чтобы размер словаря был настолько мал, насколько это возможно. Кроме того, как уже упоминалось, требуется сжимать и распаковывать относительно небольшие, независимые блоки данных, так что если пакет потерян, это повлияет только на следующие за ним данные в его собственном блоке. Сжатие псевдокода кодовой книги в его простейшем виде показано на рисунке 3. Этот алгоритм не имеет переполнения передачи и вычислительно прост. Так как отправитель и получатель должны иметь исходный словарь и все новые записи словаря создаются на основе существующих словарных записей, получатель может воссоздать словарь на лету по мере получения данных.

отправить стартовый код
для каждого символа {
если новая запись добавляется с символом не из словаря
{
отправить код для новой записи
добавить новую запись, к которой присоединен символ
новой записи словаря
сделать новую запись пустой
}
добавить символ к новой записи
}
отправить код для новой записи
отправить стоп-код
Рисунок 3. Конвейерный алгоритм сжатия кодовой книги

3.3. Энтропийное кодированное сжатие кодовой книги. Первоначально сжатие осуществляется посредством проверки наиболее значимых битов (MSB) пакетов, пакеты объединены, если они имеют такие же биты MSB, для оставшихся данных следует выполнение метода энтропийного кодирования. Энтропийное кодирование – это схема сжатия данных, которая присваивает коды символам так, чтобы соответствовать кодовой длине с вероятностями символов. Энтропийный метод сжимает данные путем замены данных символами, представленными равными по длине кодовыми словами, где длина пропорциональна отрицательному логарифму вероятности. Методика реализуется, создавая бинарное дерево узлов. Они могут храниться в виде регулярной матрицы, размер которой зависит от количества символов (n). Алгоритм, как показано на рис.4, работает следующим образом:

Вход
A = {a1, a2, ....,an} - символ размера алфавита n
W = {w1, w2, ...,wn} – множество символьных весов.
т.о. Wi = вес (ai), 1 Выход
C(A,W) = {c1, c2, ...., cn} - множество двоичных кодовых слов
где ci - кодовое слово
для ai, 1 Пусть L(C) = i=1∑nWi х длина (ci) взвешенной длины маршрута кода C.
Условие L(C)
Рисунок 4. Алгоритм энтропийного кодирования.

Узел может быть либо конечным узлом или внутренним узлом. Изначально все узлы являются конечными узлами, внутренние узлы содержат символьный вес, ссылки на два дочерних узла и опциональную ссылку на родительский узел. В качестве общего соглашения, бит '0 'представляет следующего левого потомка и бит '1 'представляет следующего правого потомка. Законченное дерево имеет N конечных узлов и N-1 внутренних узлов. Результирующие сжатые данные снова сжимаются при помощи метода кодового словаря, который объяснен в предыдущем разделе, а затем данные передаются на приемный узел, на котором данные распаковываются.

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

4.1. Модель симуляцииОколо 100 сенсорных узлов равномерно распределены на области более 1000m на 1000m. Первоначально 10 джоулей энергии приписывается каждому узлу, а затем мы вводим сеть с 1000 случайно сгенерированными пакетами. Значения параметров, используемые для моделирования, показаны в таблице 1. Источники и приемники каждого пакета выбираются случайным образом и размеры пакетов взяты из равномерного распределения в диапазоне от 1 до 100 единиц. Эффективный радиодиапазон находится в 250 метрах. Используется модель входных расстояний с потерями на маршруте и показатель потерь на маршруте установлен в 4.0. Пакеты данных генерируются с интервалом в 1 секунду. Симуляция выполняется на протяжении 750 секунд, следовательно, каждый протокол имеет достаточно времени для того, чтобы открыть маршрут от приемника к источнику и произвести значительное количество трафика данных. Мощности расхода для передачи одного блока данных – 660 МВт, потребление электроэнергии для приема данных 35 мВт, а энергопотребление в режиме ожидания, т.е. когда сенсорный узел не находится в отправке или получении данных 35 мВт.

Таблица 1. Параметры допущения
Параметры Значение Параметры Значение
Полоса пропускания 2 Мбит / с Диапазон передачи 250
Мощность передачи 660 МВт Размер топологии 1000 х 1000
Мощность приема 395 МВт Количество датчиков 100
Мощность в режиме ожидания 35 мВт Скорость передачи пакетов 5 пакетов / с
Начальная энергия батарей 10 джоулей Размер пакета 512 байт

4.2. Оценка энергии. Модель энергопотребления радиомодуля во встроенных устройствах должна принимать во внимание энергопотребление приемопередатчика и начальное энергопотребление наряду с точной моделью усилителя. Суммарная энергия, потребляемая для передачи и приема (ETC) пакета из 6 бит за один хоп беспроводной связи расстояния d, может быть выражена как:

,

где ЕТ — энергия, используемая схемой передатчика и усилителя мощности, ER — энергия, используемой в схеме приемника, PT является энергопотреблением схемы передатчика, PR является энергопотреблением схемы приемника, Tst является временем запуска трансивера, Еenc является энергией, используемой для кодирования и Edec — это энергия, которая используется для декодирования. Так как эффект запуска компонента не учитывается для мультихопового сценария, и также предполагается, что энергией кодирования / декодирования можно пренебречь, уравнение 1 может быть упрощено:

,

где n — число переходов между источником и приемником, ETE — энергия, используемая передатчиком, ЕТА — энергия, используемая усилителем, D является общим расстоянием между источником и приемником, β является показателем потерь на маршруте канала. В этом уравнении, расстояние между любыми двумя соседними узлами маршрута данных предполагается произвольными. Энергия, используемой передатчиком, может быть в дальнейшем вычислена с помощью уравнения 3:

,

где (S /N)r есть отношение сигнал-шум приемника, NFRE является коэффициентом шума приемника, No является термальным уровнем шума в полосе частот 1 Гц, BW является каналом шумовой полосы пропускания, λ — это длина волны, Gant является усилением антенны. ηamp — усилитель эффективности передатчика и mbit является скоростью передачи битов. Следующие значения используются для расчета потребления энергии в мультихоповой передаче данных, как показано в таблице 2.

Таблица 2. Параметры оценки энергии.
Параметр Значение Параметр Значение
Β 2 (S / N)r 11 дБ
Gant -20дБ NFRE 10дБ
ηamp 0,2 No 4.17e-21J
mbit 2.50E +05 BW 2.50E +05 HZ
ETE 2.50E +05 λ 2.50E +05 HZ

Заключение. Производительность беспроводной сенсорной сети (БСС) для различных схем сжатия проанализирована в данной статье. Методика сжатия, которая хорошо работает для данной беспроводной сенсорной сети может не подойти другой БСС с другими требованиями. Дальнейшие улучшения, которые могут быть включены в БСС, - это внедрение многочисленных распределенных устройств для мониторинга и взаимодействия с физическими явлениями мира и для использования пространственного и временного плотного зондирования и приведения в действие сенсорных устройств.

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

  1. Bajwa W., Haupt J., Sayeed A., and Nowak R., Compressive Wireless Sensing, in Proceedings of Information Processing in Sensor Networks, USA, pp. 134—142, 2006.

  2. Gehrig N. and Dragotti L., Distributed Compression in Camera Sensor Networks, in Proceedings of International Conference on Image Processing, UK, pp. 82—85, 2001.

  3. Karvonen H., Shelby Z., and Pomalaza-Raez C., Coding for Energy Efficient Wireless Embedded Networks, in Proceedings of International Workshop on Wireless Ad Hoc Networks, Finland, pp. 300—304, 2004.

  4. Madden S., Franklin M., Hellerstein J., and Hong W., TinyDB: An Acquisitional Query Processing System for Sensor Networks, Computer Journal of ACM Transaction Database Systems, vol. 30, no. 1, pp. 122—173, 2005.

  5. Madden S., Franklin M., and Hellerstein J., TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks, in Proceedings of Annual Symposium on Operating System Design and Implementation (OSDI), USA, pp. 131—1462, 2002.

  6. Magli E., Mancin M., and Merello L., Low Complexity Video Compression for Wireless Sensor Networks, in Proceedings of International Conference on Multimedia and Expo, vol. 3, USA, pp. 585—590, 2003.

  7. Petrovic D., Shah C., Ramchandran K., and Rabaey J., Data Funneling: Routing with Aggregation and Compression for Wireless Sensor Networks, in Proceedings of the IEEE International Workshop on Sensor Network Protocols and Applications, USA, pp. 156—162, 2003.

  8. Pradhan S., Kusuma J., and Ramchandran K., Distributed Compression in a Dense Microsensor Network, IEEE Signal Processing Magazine, vol. 19, no. 2, pp. 51—60, 2002.

  9. Rabbat M., Haupt J., Singh A., and Nowak D., Decentralized Compression and Pre-distribution via Randomized Gossiping, in Proceedings of International Conference on Information Processing in Sensor Networks, USA, pp. 51—59, 2006

  10. Roy O. and Vetterli M., Distributed Compression in Acoustic Sensor Networks Using Oversampled A/D Conversion, in Proceedings of IEEE International Conference on Acoustic, Speech and Signal Processing, vol. 4, France, pp.165—168, 2006.

  11. Tilak S., Abu-Ghazaleh N., and Heinzelman W., A Taxonomy of Wireless Microsensor Network Models, Computer Journal of ACM Mobile Computing and Communication Review (MC2R), vol. 6, no. 2, pp. 1—8, 2002.

  12. Wagner R., Choi H., Baraniuk R., and Delouille V., Distributed Wavelet Transform for Irregular Sensor Network Grids, in Proceedings of IEEE Workshop on Statistical Signal Processing, USA, pp. 1196—1201, 2005.

Назад в библиотеку