АлгоритмSPIN: Sensor Protocols for Information via Negotiation.
Базовые идеи протоколов SPIN Обмен измеряемыми данными может быть затратным, но обмен данными об измеряемых данных (мета-данными) может быть и нет. Узлы должны мониторировать и адаптироваться к изменениям их собственных энергетических ресурсов.
Потенциально каждый узел является базовой станцией и доставка информации происходит от каждого к каждому. Протокол использует мета-данные и систему «переговоров». Семантика мета-данных не специфицируется протоколом и зависит от конкретных приложений. Протокол может адаптироваться в зависимости от количества энергии оставшейся на узлах. Протокол работает по time-driven манере, и доставляет информацию до всех узлов сети, даже если они ее не запрашивали.
Алгоритм SPIN имеет три стадии работы и соответственно могут передаваться три типа сообщений ADV, REQ, DATA.
· ADV – используется для распространения информации о новых данных. Содержит мета-данные.
· REQ – для запроса этих данных
· DATA – это сами данные.
Если узел хочет послать новые данные, он сначала посылает ADV сообщение своим соседям, если кто-то из соседей заинтересован в получении этих данных то он посылает REQ сообщение, и далее получает данные(DATA-сообщение).
Существует несколько протоколов семейства SPIN:
· SPIN-1 : стандартный протокол.
· SPIN-2 : протокол использующий информацию об оставшейся энергии.
· SPIN-BC : для распространения broadcast сообщений.
· SPIN-PP : для передачи сообщений точка-точка(point-to-point).
· SPIN-EC: подобен предыдущему но с использованием информации об энергии (energyheuristic).
· SPIN-RL: разработан для нестабильных каналов (lossychannels).
Протоколы семейства SPIN хорошо подходят для приложений, где узлы мобильны, так как им требуется только локальная информация о соседях.
Недостатком SPIN протоколов является то, что они не гарантируют доставку данных.
Алгоритм DirectedDiffusion.
Сенсорная сеть рассматривается как виртуальная база данных. Реализована обработка запросов от БС. Запрос распространяется по всей сети (флудинг) либо передается выбранной группе узлов. В ответ узлы, имеющие запрашиваемые данные, посылают их обратно на БС. Промежуточные узлы могут объединять данные.
Directed Diffusion – это data-centric и application-aware протокол в котором все данные генерируемые сенсорными узлами обозначаются парами атрибутов.
Основная идея протокола Directed Diffusion – это комбинирование данных от различных источников на промежуточном узле (in-network aggregation) устраняя избыточность и уменьшая количество передач, таким образом продлевая время жизни сети.
Основные элементы Directed Diffusion
· Naming. Данные обозначаются с помощью атрибутов.
· Interests. Узел запрашивает данные посылая запрос (interest) на определенные данные.
· Gradients. Градиенты (gradients) установлены в пределах сети, чтобы доставлять данные совпадающие с запросом.
· Reinforcement БС «устанавливает» (reinforce) определенные маршруты, чтобы доставлять данные с большей скоростью (данные о быстро меняющихся событиях).
Content based naming
· Задачи обозначаются списком атрибутов – парами значений.
· Описание задачи определяет запрос(interest) на данные, которые совпадают с атрибутами.
БС периодически посылает (broadcast) запрос (interest) на данные всем своим соседям.
Каждый узел хранит interestcache. Каждая запись соответствует индивидуальному запросу. Не содержит информации о БС. Объединение (aggregation) совпадающих запросов.
Каждая запись в кеше имеет несколько полей. Отметка о времени приема последнего совпадающего запроса. Несколько градиентов: скорость данных, продолжительность, направление.
Использует обработку/объединение данных внутри сети. Достигает желаемого глобального поведения посредством локального взаимодействия. Эмпирически адаптируется к окружающей обстановке.
Алгоритм RumorRouting
Вариант Directed Diffusion. Используется когда количество событий (events) малое, а количество запросов (queries) большое. С помощью флудинга распространяются не запросы, а информация о событиях. Долго живущие пакеты, называемые агентами, распространяют (flood) информацию о событиях по сети. Когда узел обнаруживает событие, он добавляет его в таблицу событий и генерирует агента. Агенты путешествуют по сети, распространяя информацию о локальном событии. Время жизни агента (Time-To-Live)
Когда узел генерирует запрос, узел знающий маршрут до соответствующего события может ответить заглядывая в свою таблицу событий. Нет необходимости использовать флудинг для распространения запросов. Только один путь между источником и приемником. Rumor Routing работает хорошо только когда количество событий мало. Затраты на поддержание большого количества агентов и таблицы событий.
АлгоритмLEACH: Low-Energy Adaptive Clustering Hierarchy
Узлы самоорганизуются в кластеры и выбирают cluster head.Все узлы, которые не являются cluster head’ами, передают информацию cluster head’у. Cluster head принимает данные, производит их обработку и передает на базовую станцию. Периодически происходит случайная смена cluster head’а и перекластеризация.
Две фазы (рисунок 4):
· организация кластеров;
· передача данных clusterhead’у и на базовую станцию.
Рисунок 4 Схема работы алгоритма LEACH
На начальном этапе каждый узел предлагает себя в качестве cluster-head’а с определённой вероятностью. Узлы, которые не стали cluster-head’ами могут стать ими впоследствии. Решение принимается на основе заданной плотности cluster-head’ов в сети Для распределения энергетической нагрузки по сети, cluster-head’ы переодически переизбераются.
Узел cluster-head рассылает свой статус другим узлам сети. Каждый узел выбирает к какому кластеру он хочет присоединиться на основе энергетической эффективности. Когда все узлы организовались в кластеры, cluster-head создает расписание для каждого узла.
Формирование кластера.
Каждый cluster head посылает ADV сообщение, с помощью CSMA/CA протокола. Сообщение содержит ID узла и заголовок, показывающий, что это ADV сообщение. На основе силы сигнала от каждого cluster-head’а, каждый узел выбирает к какому кластеру присоединиться. Каждый узел посылает (с помощью CSMA/CA) join-request сообщение своему cluster-head’у. Сообщение содержит ID cluster-head’а и самого узла. Каждый cluster-head создает TDMA расписание. Это гарантирует избежание коллизий при передаче сообщений и экономию энергии.
Фаза передачи (рисунок 5).
Узлы передают данные в свое отведенное время. После получения сообщений от всех узлов, cluster-head формирует свои сообщения. Затем cluster-head передает эти сообщения на базовую станцию. Для уменьшения коллизий, cluster-head’ы используют CDMA коды. Перед началом передачи узел-cluster-head прослушивает канал. Если канал свободен, он передает информацию на базовую станцию.
Рисунок 5Алгоритм LEACH: Фаза передачи
Достоинства.
· Использование адаптивного самоорганизующегося протокола позволяет распределить энергетическую нагрузку по всей сети.
· Позволяет проводить обработку данных на cluster-head’е, что может уменьшить количество данных передаваемых по сети.
· Оптимальное количество кластеров может быть определено заранее в зависимости от топологии сети и отношения затрат на обработку/передачу информации.
· Первая «смерть» узла происходит в восемь раз позже, чем при использовании прямой передачи и статическиз кластерных протоколов.
PEGASIS : Power-Efficient GAthering in Sensor Information Systems.
Улучшение LEACH. Формирует не кластера, а цепочки. Данные передаются по цепочке и один узел их посылает. Превосходит LEACH по энергетическим показателям. Большие задержки для узлов на концах цепочки. Иерархический PEGASIS: Использование CDMA.
TEEN: Threshold sensitive Energy Efficient Network.
Reactive, event-driven protocol for time-critical applications.
· Узел постоянно мониторирует среду, но передает информацию только если значение меняется значительно.
· Нет переодической передачи.
· Критические данные передаются незамедлительно.
CH посылает своим узлам «жесткий» (hard) и «мягкий» (soft) порог.
· Жесткий порог: Узел посылает информацию CH только если значение находится в интересуемых пределах.
· Мягкий порог: Узел посылает информацию CH только когда значение изменилось как минимум на значение порога.
· Каждый узел в кластере периодически становиться CH.
Иерархическая кластеризация (рисунок 6).
Рисунок 6 Иерархия узловв алгоритме TEEN
Хорошо подходит для приложений критичных ко времени. Меньшие энергетические затраты. Меньшие затраты, чем проактивные протоколы. «Мягкая» граница может адаптироваться. «Жесткая» граница может варьироваться в зависимости от приложений. Не подходит для периодического мониторинга.
Алгоритм APTEEN: AdaptiveThresholdsensitiveEnergyEfficientNetwork.
Расширение TEEN для поддержки и периодического мониторинга так и для реакции на критические события. В отличии от TEEN узел должен собрать и передать данные, если они не были посланы за определенный период времени (counttime), который устанавливается CH.По сравнению с алгоритмом LEACH, TEEN&APTEEN потребляют меньшее количество энергии.
Недостатки. Накладные расходы и сложность формирования многоуровневых кластеров и организации пороговых функций.
АлгоритмSOP: Self – Organization Protocol.
Архитектуры поддерживает разнотипные узлы. Стационарные узлы роутеры используются как основа сети. Мобильные или стационарные сенсорные узлы посылают информацию на роутеры. Сенсорный узел может быть частью сети только в случае если он может передать информацию на роутер напрямую. Данная архитектура требует возможности адресации каждого узла.
Достоинства:
· Подходит для приложений где нужна связь с определенным узлом.
· Небольшие затраты на поддержание таблицы маршрутизации.
· Сохранение сбалансированной маршрутной иерархии.
· Сохранение энергии: использование ограниченного подмножества узлов.
Недостатки:
· Данный протокол не является протоколом «по требованию» особенно, что касается организационной фазы.
· Существование множества разрывов повышает вероятность реорганизации сети (затратная операция).
АлгоритмGAF: Geographic Adaptive Fidelity.
Location-based протокол учитывающий энергетические ресурсы узла.
Каждый узел знает свои координаты через GPS. Ассоциирует себя с точкой на виртуальной решетке. Узлы которые считают что находятся в одной точки равнозначны в терминах «стоимости» маршрутизации пакета.
Узел 1 может достичь любой из узлов 2,3 или 4 следовательно узлы 2,3,4 эквивалентны(рисунок 7). Любые 2 могут находиться в спящем режиме без влияния на маршрутизацию.
Рисунок 7Достижимые узлы в алгоритмеGAF
Разработан преимущественно для MANET, но может быть использован и для сенсорных сетей.
Три состояния:
· Обнаружение (Discovery): Определяет соседей в решетке.
· Активное
· Спящее
При учете мобильности каждый узел оценивает время своего «оставления» решетки и посылает это время соседям. Соседние узлы регулируют время для сна, чтобы обеспечить маршрутизацию.
Протокол плохо масштабируемый. Только активные узлы посылают информацию, поэтому точность информации не очень высока.
АлгоритмGEAR: Geographic and Energy Aware Routing.
Ограничивает число пересылаемых запросов в directed diffusion. Рассматривает только определенный район сети, вместо всей сети в целом. Каждый узел хранит estimated cost & learning cost на достижение БС через своих соседей. Estimated cost = f(оставшаяся энергия, расстояние до точки назначения)
Фаза 1: Пересылка пакетов в определенный район:
· Пересылка пакета соседнему узлу с минимальной функцией f (ближайший к БС и имеющий наибольшую энергию)
· Если все узлы находяться дальше чем сам узел отправитель, то выбирается один из соседей с на основе learned cost.
Фаза 2: Пересылка пакета в пределах нужной области.
Применяется любое рекурсивное отправление сообщений.Район делиться на 4 подобласти и посылается 4 копии пакета (рисунок 8). Повторяется до тех пор пока не останутся районы с одним узлом.Применяется ограниченный флудинг. Применяется когда плотность узлов мала.
Рисунок 8Отправка сообщения в алгоритме GEAR
Протоколы маршрутизации со многими маршрутами (Multipathrouting)
· Повышение надежности передачи информации, за счет существования нескольких маршрутов.
· Увеличивает энергетические затраты.
· Увеличивает количество трафика в сети.
Поэтому рассматривать не будем.
Дата: 2019-05-29, просмотров: 200.
