Адаптивные протоколы для распространения информации в беспроводных сенсорных сетях
Автор статьи: Joanna Kulik, Wendi Rabiner, and Hari Balakrishnan
Перевод: Халыгов Артем
Источник (англ.): Источник оригинальной статьи
ОТ АВТОРА:
В этой статье мы представляем семейство адаптивных протоколов, называемых SPIN (Сенсорный протокол информации, работающий посредством взаимодействия). Которые эффективно распространяют информацию среди датчиков в энерго-ограниченных беспроводных сенсорных сетях. Узлы под управлением протокола связи SPIN называют данные с помощью дескрипторов данных высокого уровня, называемых метаданными. Они используют обмен метаданных, для устранения передачи избыточных данных по сети. Кроме того, SPIN узлы могут основывать связь как при конкретном запросе информации из данных так и на информации из ресурсов доступных ему. Это позволяет датчикам эффективно распределять данными в случае ограниченного энергоснабжения. Мы смоделировали и проанализировали производительность двух отдельных протоколов SPIN, сравнивая их с остальными подходящими и теоретически оптимальными протоколами. Мы обнаружили, что SPIN протокол может доставить на 60% больше данных для данного количества энергии, чем стандартные подходы. Мы также обнаружили, что, с точки зрения скорости распространения и использования энергии, SPIN протоколы работают близко к теоретическому оптимуму.
1 Введение
Беспроводная сенсорная сеть, вероятно, будет широко распространена в будущем, потому что она значительно расширяет наши возможности по мониторингу и контролю физической среды с удаленных мест. Такие сети могут значительно повысить точность информации, полученной с помощью взаимодействия между датчиками узлов и обработки информации в режиме реального времени на этих узлах. Беспроводные сенсорные сети позволяют улучшить точность измерения путем предоставления распределенной обработки огромного количество считанной информации (например, сейсмический данные, акустические данные, изображения с высоким разрешением и т.д.). Объединенные в сеть, датчики могут объединять данные, чтобы обеспечить качественный, всесторонний взгляд на окружающую среду. Кроме того, сетевые датчики могут сосредоточить свое внимание на критический событиях, которые отметили другие датчики в сети (например, злоумышленник вошел в здание). Наконец, сетевые датчики могут продолжать точно функционировать, несмотря на выход из строя отдельных датчиков; например, если какие-то датчики в сети потеряют часть важной информации, другие датчики могут прийти на помощь путем предоставления недостающих данных.
Беспроводные сенсорные сети могут также улучшить удаленный доступ к данным датчиков, обеспечивая стоковые узлы которые соединяют край с другими сетями, такими как Интернет, используя беспроводные глобальные связи. Если датчики открывают доступ к своим наблюдениям и обработке этих наблюдений, то важная и полезная информация доступна на стоковых узлах, пользователи могут получать информацию из этих узлов для мониторинга и контроля окружающей среды издалека.
Поэтому мы представляем себе будущее, в котором сенсорные узлы образуют специальную обработку распределенных сетей, которые предоставляют легкодоступную и высококачественную информацию о физической среде. Каждый сенсорный узел работает в автономном режиме без центральной контрольной точки в сети, а каждый узел основывает свое решение о его задаче, информации доступную в настоящее время и его знаниях этих вычислительных, коммуникационных и энергетических ресурсов. По сравнению с сегодняшними изолированным датчиками, завтрашние сетевые датчики имею потенциал, чтобы выполнять свои обязанности с большей точностью, надежностью и совершенностью.
Некоторые препятствия необходимо преодолеть, прежде чем это видение может стать реальностью. Эти препятствия возникают из-за ограниченной энергии, вычислительной мощностью и коммуникационных ресурсов доступных датчикам в сети.
Энергия: Поскольку сетевые датчики могут использовать свой ограниченный запас энергии просто выполняя вычисления и передачу информации в беспроводной среде, энергосбережение связи и вычислений являются существенными.
Вычисления: Датчики имеют ограниченные вычислительные мощности, и поэтому не в состоянии управлять сложными сетевыми протоколами.
Связь: Пропускная способность беспроводной связи соединяющий датчик узла часто ограничено, порядка несколько сотен Kbps, замедляющая дальнейшую связь между датчиками.
В этой статье мы представим SPIN(Сенсорные протоколы информации, работающие посредством взаимодействия)семейство информационных протоколов, основанное при взаимодействии и распространении данных по сети между абонентами пригодно для использования в беспроводных сенсорных сетях. Мы делаем ставку на эффективное распространение индивидуальных наблюдений датчика на все датчики в сети, рассматривая все датчики в качестве потенциальных узлов стока. Есть несколько преимуществ в решении этой проблемы. Во-первых, это даст нам возможность копировать информацию об окружающей среде по всей сети для повышения отказоустойчивости системы. Во-вторых, это даст нам возможность распространения критической части информации(например, что имплозия была обнаружена в сети наблюдения) для все узлов. Анализирую сильные и слабые стороны обычных протоколов для распространения данных в сенсорной сети, был спроектирован SPIN. Такие протоколы, которые мы характеризуем как классические, начинают передавать данные с исходного узла всем своим соседям. После получения части данных, каждый узел сохраняет и отправляет копию данных для всех своих соседей. Таким образом, простой протокол не требует протокол состояния узла, и он быстро распространяет данные в сети с не малой пропускной способностью и ссылки не подвержены потере.
Три недостатка этого простого подхода делают его недостаточным для протокола сенсорных сетей:
Имплозия: В классическом распространении пакетов, узел всегда отправляет данные своим соседям, независимо от того, получил ли сосед данные из другого источника или нет. Это приводит к уменьшению проблемы, изображенной на Рисунке 1. Здесь узел А начинает отправлять данные двум соседям, B и C. Эти узлы получают данные из узла A и отправляют копию их соседу D. Протокол тратит ресурсы отправляя две копии данных на D. Легко заметить, что имплозия линейна по отношению любого узла.
Наложение: Сенсорные узлы часто охватывают дублированные географические регионы и узлы часто собирают наложенные части сенсорных данных.На Рисунке 2 показано, что происходить когда два узла (A и B) собирают такие дублированные данные, а затем поток данных отправляют соседу (C). Опять же, алгоритм тратит энергию и канал связи отправляя две копии части данные на один узел. Наложение это более сложная проблема, требующая решения, чем проблема имплозии – она зависит только от топологии сети, в то время как наложение зависит и от топологии и отображения наблюдаемых данных в сенсорных узлах
Рисунок 1. Проблема вторжения.
В этом графе, узел A начинает распространение пакетов данных всем соседям. Две копии данных в конечном итоге приходит на узел D. Энергосистема тратит энергию и канал связи для одной ненужной отправке и приеме.
Рисунок 2. Проблема наложения.
Два сенсора покрывают наложенную географическую зону. Когда датчики начинают отправлять пакеты данных в узел C, то С получает две копии данных обозначенных r.
Слепые ресурсы: В классической отправке пакетов, узлы не изменяют свою активность основанную на количестве энергии доступной для них в определенный момент времени. Сеть встроенных сенсоров может быть «ресурсо-осведомленной» и адаптировать свои сообщения и вычисления с состоянием его энергоресурсов.
Семейство SPIN протокол включает в себя два ключевых новшества, которые преодолевают эти недостатки: переговоры и ресурсо-приспособление. Для преодоления проблемы вторжения и наложения, SPIN узлы взаимодействуют друг с другом, перед началом передачи данных. Взаимодействие помогает гарантировать, что только полезная информация будет передана. Для успешного взаимодействия, однако, узлы должны быть в состоянии описать или назвать данные, которые они наблюдают. Мы ссылаемся на дескрипторы, использованные в SPIN взаимодействиях в качестве метаданных.
В SPIN, узлы делают опрос своих ресурсов перед отправкой данных. Каждый датчик узла имеет свой собственный менеджер ресурсов, который следит за потреблением ресурсов; приложение исследует менеджер до передачи или обработки данных. Это позволяет датчикам сократить расход энергии когда ее запас мал, например, будучи более осторожным в пересылках сторонних данных.
Вместе, эти возможности преодолевают три недостатка классической отправки пакетов. Процесс взаимодействия, который предшествует фактической передачи данных исключает имплозию, так как устраняет передачу избыточных сообщений данных. Использование дескрипторов метаданных исключает возможность наложения, поскольку он позволяет узла именовать части данных, которые они заинтересованы получить. Зная о местных энергоресурсах датчики позволяют уменьшить активность, если их энергетические ресурсы на исходе, тем самым увеличивая срок службы. Чтобы оценить эффективность распространения информации через SPIN, мы выполним моделирование основанное на исследовании пяти распространенных протоколов. Два протокола это SPIN протоколы (которые мы называем SPIN-1 и SPIN-2); в нашем исследовании это экспериментальные протоколы. Три других протокола функционируют как протоколы сравнения: (1) отправка пакетов, которое мы изложили выше; (2) веерная отправка пакетов, вариант отправки пакетов который отправляет сообщения на случайные множества соседних узлов, и (3) идеал, идеализированный протокол маршрутизации, который предполагает совершенные знания и имеет лучшие характеристики.
Мы оцениваем эти протоколы путем измерения количества данных, которые они распространяют с течением времени и количество энергии которое было потрачено. SPIN протоколы распространяют информацию с низкой задержкой и в то же время экономят энергию. Наши результаты показывают преимущества использования метаданных, чтобы именовать данные и взаимодействовать при передачи данных. SPIN-1 использует взаимодействие для решения проблем имплозии и наложения; это уменьшает энергопотребление в 3.5 раза по сравнению с отправкой пакетов, в то время как распространение данных почти так же быстро, как это теоретически возможно. SPIN-2, который дополнительно включает в себя предел основанный на механизме ресурса-осведомленности в дополнение к взаимодействию, распространяет на 60% больше данных на единицу энергии, чем простая отправка пакетов и на самом деле очень близка к идеалу объема данных которые могут быть распространены на единицу энергии.
2. SPIN:Сенсорные протоколы информации, работающие посредством взаимодействия)
Семейство SPIN протоколов опирается на две основные идеи. Первая, для эффективной работы и экономии энергии, приложения датчика должны взаимодействовать с остальными о данных которые они уже имеют или данных которые нужно получить. Обмен данными датчиков может быть дорогостоящей сетевой операцией, но обмен данными о данных датчика не требуется. Второе, узлы в сети должны контролировать и адаптироваться к изменениям в их собственных энергоресурсах для продления срока эксплуатации системы.
Наш дизайн SPIN протокол мотивирован отчасти принципом Application Level Framing (Формирования кадров прикладного уровня (ALF)). С ALF, сетевые протоколы должны выбрать передаваемую единицу, которая является значимой для приложений, т.е. пакетирование лучше сделать в плане Application Data Unit (ADUs Элементы Данных Приложения).Одним из важных компонентов ALF протоколов это общее именование данных между протоколом передачи и приложением, которыми мы руководствуемся при разработке наших метаданных. Мы взяли ALF-идеи, как следующий шаг, утверждая, что решения о маршрутизации, также лучше всего сделать в контролируемых приложениях и специфический приложениях, используя знания не только топологии сети но и размещение элементов данных и состояние ресурсов в каждом узле. Мы считаем, что такие комплексные подходы к именованию и маршрутизации являются привлекательными для широкого спектра сетевых ситуаций, особенно в мобильных и беспроводных сетях, приборах и датчиках.
В этом разделе представлены отдельные элементы, которые составляют семейство SPIN протоколов и представлены два SPIN протокола, которые мы разработали, SPIN-1 и SPIN-2.
2.1 Метаданные
Датчики используют метаданные для сжатого и полного описания данных которые они собрали. Если x дескриптор метаданных для данных датчика X, то размер x в байтах должен быть короче, чем размер X, для SPIN, чтобы быть полезным. Если две части фактических данных различаются, то их соответствующие метаданные должны быть различимы. Кроме того, две части одинаковых данных должны использовать одни и те же метаданные. SPIN не определяет формат для метаданных; этот формат зависит от конкретного приложения. Датчики, которые охватывают непересекающиеся географические регионы, могут просто использовать свои собственные уникальные идентификаторы в виде метаданных. Метаданные x выступают за «все данные собранные датчиком x». Фото сенсор, напротив, могли бы использовать(x,y,z)в качестве метаданных, где (x,y) географические координаты, а z ориентация. Т.к. для каждого приложения формат метаданных может быть разным, SPIN полагается на каждое приложения для интерпретации и обобщение его собственные метаданные.
2.2 SPIN сообщения
SPIN узлы используют три типа сообщений для связи:
ADV – новое объявление данных. Когда SPIN узел имеет данные для обмена, он может оповещать этот факт передавая ADV сообщение содержащее метаданные.
REQ – запрос данных. SPIN узел отправляет REQ сообщения, когда он желает получить некоторые актуальные данные.
DATA – данные сообщения. DATA сообщения содержат актуальные данные датчика с заголовком метаданных.
Потому что ADV и REQ сообщения содержат только метаданные, они меньше и дешевле, для передачи и приема, чем их соответствующее сообщения DATA.
2.3 SPIN управление ресурсами
SPIN приложения являются ресурсо-осведомленными и ресурсо-приспосабливающимися. Они могут опрашивать свои системные ресурсы, чтобы узнать, сколько энергии доступно им. Они могут также рассчитать стоимость, в отношении энергии, для выполнения расчетов и передачи и приема данных по сети. Обладая этой информацией, SPIN узлы могут принимать обоснованные решения для эффективного использования своих ресурсов. SPIN не задает правила особенностей энергетического управления для этих протоколов. Скорее, он определяет интерфейс, который приложения могут использовать, чтобы исследовать имеющиеся у них ресурсы.
2.4 Реализация SPIN
SPIN это прикладной уровень относящийся к сетевой связи. Поэтому мы намерены реализовать SPIN в качестве промежуточных прикладных библиотек с хорошо определенным API. Эти библиотеки будут осуществлять основные типы сообщений SPIN, процедуру обработки сообщений и функции управления ресурсами. Приложения датчиков могут затем использовать эти библиотеки, чтобы построить свои собственные SPIN протоколы.
3. Другие алгоритмы распространения данных
В этом разделе, мы рассмотри три распространенных алгоритма, с которыми мы сравним производительность SPIN.
3.1 Классическая отправка пакетов.
В классической отправке пакетов, узел желающий распространить часть данных в сети, отправляет копию данных всем соседям. Всякий раз, когда узел получает новые данные, он создает копию данных и отправляет данные всем соседям, кроме узла который только что отправил данные. Количество времени, которое занимает отправка пакетов группе узлов, а затем отправляет эти данные по своим соседям, называется цикл. Алгоритм заканчивается, когда все узлы в сети получили копию данных.
3.2 Gossiping
Gossiping это альтернатива классическому методу отправки пакетов, который использует рандомизацию, чтобы сохранить энергию. Вместо того, чтобы без разбора выполнять пересылку данных на всех своих соседей, gossiping узел передает данные только на одного случайно выбранного соседа. Если gossiping узел получает данные от соседа, он может переслать данные обратно соседу, если он случайным образом выбрал его. На рисунке 3 показана причина, из-за которой происходит пересылка данных обратно к отправителю. Если узел D никогда не передаст данные обратно к узлу B, то узел C никогда не получит данных.
Рисунок 3. Gossiping.
На каждом шагу, каждый узел передает данные только на одного соседа, которого он выбирает случайным образом. После того как узел D получит данные,он должен направить данные обратно к отправителю B, в противном случае данные никогда не достигнут узла C.
4. Моделирование сенсорных сетей.
Для того, чтобы сравнить различные виды связей обсуждаемые в предыдущих разделах, мы разработали симулятор сенсорных сетей расширяющих функциональность пакета программного обеспечения ns. Используя структурное моделирование, мы сравнили SPIN-1 и SPIN-2 с классическим волновым методом отправки пакетов и gossiping и протокол идеального распределения данных. Мы обнаружили, что SPIN-1 обеспечивает более высокую пропускную способность, чем gossiping и такую же как и волновая отправка пакетов, и в тоже время использует значительно меньше энергии, чем оба этих протокола. SPIN-2 способен доставить еще больше данных на единицу энергии, чем SPIN-1 и близок к идеальному объему данных на единицу энергии, приспосабливаясь к ограничению энергии в сети. Мы обнаружили, что во всех наших симуляциях, узлы с высоким порядком, рассеивают больше энергии, чем узлы с низким порядком, что создает потенциально слабые места в батарейках сети.
4.1 ns Реализация
ns, управляемый событиями сети симулятор с расширенной поддержкой для моделирования TCP, маршрутизации и многоадресных протоколов. Для реализации семейства протоколов распределенных данных SPIN, мы добавили несколько функций для ns симулятора. Класс узла в ns был расширен для создания ресурсно-адаптивного узла, который показан на рисунке 4.
Рисунок 4. Блок-диаграмма ресурсно-адаптивного узла.
Основные компоненты Ресурсно-адаптивного узла – Ресурсы, Resourse Manager, Resource-Constrained Application (RCApplication), Resource-Constrained agent(RCAgent) и сетевой интерфейс. ResourseManager обеспечивает общий интерфейс между приложением и отдельными ресурсами. RCApplication, подкласс приложений класса ns, является отвественным за обновление состояния ресурсов узла, через ResourseManager. Кроме того, RCApplication реализует протокол связи SPIN и ресурсно-адаптивных принимающих решения алгоритмов. RCAgent пакетирует данные полученных в RCApplication и отправляет пакеты в узлы сетевого интерфейса для передачи одному или нескольким соседям.
4.2 Моделирование тестового стенда.
Для наших экспериментов мы создали 25-узловую сеть показанную на рисунке 5. Эта сеть была случайно сгенерирована с условием, что графы будут полностью соединены, имеет 59 граней, степенью 4.7, диаметром хопа 8, а средний кротчайший путь 3.2 хопа. Мощность сенсорного радиопередатчика устанавливается так, что любой узел в пределах 10 метров находится в пределах дальности связи и называется сосед датчика. Скорость радио (1мегабит/c) и рассеиваемая мощность (600мВт в режиме передачи, 200мВт в режиме према) была выбрана на основе данных из имеющихся в настоящее время радиопередатчиков. Задержка обработки передачи сообщений выбирается случайно между 5мс и 10 мс. Мы инициализируем каждый узле с 3-мя элементами данных, выбранный случайным образом из набора 25-ти возможных элементов данных. Это означает, что наложение в исходных данных различных датчиков, как это часто происходит в сенсорных сетях. Размер каждого элемента данных был установлен на уровне 500 байт и мы задали каждому элементу различные 16 байтовые имена метаданных. Наша тестовая сеть не несет потерь и не имеет задержек. В таблице 1 приведены характеристики сети.
Используя эту конфигурацию сети, мы прогнали каждый протокол и отследили его прогресс с точки зрения скорости распространения данных и использования энергии. Для каждого эксперимента, мы прогнали протоколы по 10 раз и составили среднее время распределение данных и потребление энергии к каждой записи для случайной вычислительной задержке.
Рисунок 5. Топология 25-ти узловой беспроводной тестовой сети. Грани показывают здесь взаимодействие соседей.
| Узлы | 25 |
| Грани | 59 |
| Средняя степень | 4.7 соседей |
| Диаметр | 8 хоп |
| Средний короткий путь | 3.2 хоп |
| Дальность приема антенны | 10 м |
| Задержка распространения сигнала | 3х108 m/s |
| Задержка обработки | 5-10 ms |
| Скорость радио | 1 Mbps |
| Мощность передачи | 600mW |
| Мощность приема | 200mW |
| Размер данных | 500 byte |
| Размер метаданных | 16 byte |
| Потери сети | Нет |
| Задержка очереди | Нет |
Таблица 1. Характеристики 25-узловой тестовой беспроводной сети.
4.3 Моделирование при неограниченной энергии
Для первого эксперимента, мы дали каждому узлу практически бесконечный запас энергии и отправляли каждый протокол распределения данных, пока они не сошлись. Поскольку энергия не ограничена, SPIN-1 и SPIN-2 являются идентичными протоколами. Таким образом, результаты в этом разделе будем сравнить только со SPIN-1 с волновым распределением пакетов, gossiping и идеальным распространением данных протокола.
4.3.1 Данные полученные в течение времени.
На рисунке 6 показано количество данных, полученных в сети в течение времени для каждого протокола. Эти графы наглядно показывают, что сплетение имеет самую медленную скорость сходимости. Тем не менее, интересно отметить, что используя сплетение, система получила более 85% от общего объема данных в течение небольшого количества времени; большинство времени уходит на распространение последних 15% данных в узлах. Это потому, что сплетенные узлы отправляют все данные, на случайно выбранных соседей. Так как узлы получают большое количество данных, то эта передача будет дорогостоящей, и, так как очень вероятно, что сосет уже получил большую часть данных, которые передаются, то это так же будет очень расточительно. Gossiping протокол поддерживает некоторые состояния соседних узлов, такие как отслеживание данных каждого узла, которые он отправил к каждому из своих соседей, будет работать гораздо лучше, уменьшая количество ненужных передач.
На рисунке 6 показано, то что SPIN-1 для схождения нужно на 80мс больше чем веерной отправке пакетов, в то время как веерной отправке нужно лишь на 10 мс дольше чем в идеале.
Рисунок 6. Процент общего количества полученных данных в системе в течении времени для каждого протокола.
5. Вывод:
В этой статье, мы представили SPIN (Сенсорный протокол информации, работающий посредством взаимодействия) семейство протоколов распространения данных в беспроводной сенсорной сети. SPIN использует обмен метаданными и ресурсную адаптивность для преодоления некоторых недостатков в стандартном подходе распространения данных. Именуя метаданные, узлы обмениваются информацией, которой они обладают, с остальными. Этот обмен при котором узлы передают информацию, только когда это необходимо, позволяет не тратить энергию для ненужных передач. Исходя из доступных ресурсов, узлы могут уменьшить свою активность, при их недостатке для продления дееспособности.