Алгоритмы маршрутизации и самоорганизации Садков Александр Аспирант РФ Сайт курса:

План Введение Классификация протоколов маршрутизации Flat протоколы Hierarchical протоколы Location based протоколы Заключение

Введение Маршрутизация в сенсорных сетях

Маршрутизация в сенсорных сетях При разработки протоколов маршрутизации для сенсорных сетей необходимо учитывать ряд их особенностей: Node Deployment Может быть как случайным так и регулярным. Распределение неравномерное.Multi-hop. Energy Consumption Узел может быть как источником так и посредником при передачи информации. Изменения топологии. Data Reporting Model Зависит от приложения. Time-driven, event-driven, query-driven and hybrid. Node/Link Heterogeneity Узлы могут отличаться по своим свойствам.

Fault Tolerance Выход из строя отдельных узлов не должен влиять на работу сети в целом. Scalability Количество узлов в сети может варироваться от нескольких десятков до десятков тысяч. Network Dynamics Возможна мобильность узлов или базовой станции. Дикамика отслеживаемого явления. Transmission Media Беспроводные каналы. Высокий уровень ошибок. Низкие скорости. Маршрутизация в сенсорных сетях

Connectivity Плотность сети. Изолированные узлы или группы узлов. Coverage Каждый узел может «чувствовать» только ограниченную область пространства. Data Aggregation Удаление избыточной информации и концентрация информации может улучшить энергетическую эффективность. Quality of Service Зависит от приложений. Скорость доставки vs энергия. Маршрутизация в сенсорных сетях

Классификация протоколов маршрутизации

Классификация Flat-based Каждый узел имеет одинаковые роли и функциональность. Hierarchical - based Каждый узел играет разные роли в сети. Узлы могут быть физически разными. Location - based Информация о местонахождении узла может быть использована для маршрутизации.

Классификация Multipath-based Существуют несколько маршрутов от источника до точки назначения. Повышается надежность, но увеливаются накладные расходы и энергозатраты. Query - based. Узел посылает запрос на данные, узел который имеет запрашиваемые данные отвечает на запрос. Negotiation – based Используются «переговоры» и высокоуровневое описание данных. QoS-based Сеть должна обеспечить определенный уровень сервиса. Coherent and non-coherent based. Обработка данных происходит на разных уровнях.

Классификация Proactive protocols Все пути расчитываются заранее, до того как они будут нужны. Reactive protocols. Пути расчитываются по требованию Hybrid protocols Комбинация двух подходов.

Flat routing protocols

SPIN Direct Diffusion Rumor Routing Flat routing protocols

SPIN: Sensor Protocols for Information via Negotiation W. Heinzelman, J. Kulik, and H. Balakrishnan, "Adaptive Protocols for Information Dissemination in Wireless Sensor Networks," Proc. 5th ACM/IEEE Mobicom Conference (MobiCom '99), Seattle, WA, August, pp

SPIN: Sensor Protocols for Information via Negotiation Базовые идеи протоколов SPIN Обмен измеряемыми данными может быть затратно, но обмен данными об измеряемых данных (мета-данными) может быть нет. Узлы должны мониторировать и адаптироваться к изменениям их собственных энергетических ресурсов.

SPIN: Sensor Protocols for Information via Negotiation Потенциально каждый узел является базовой станцией и доставка информации происходит от каждого к каждому. Протокол использует мета-данные и систему «переговоров». Семантика мета-данных не специфицируется протоколом и зависит от конкретных приложений. Протокол может адаптироваться в зависимости от количества энергии оставшейся на узлах. Протокол работает на time-driven манер, и доставляет информацию до всех узлов сети, даже если они ее не запрашивали.

SPIN: Sensor Protocols for Information via Negotiation SPIN имеет три стадии работы и соответственно могут передаваться три типа сообщений ADV, REQ, DATA. ADV – используется для распространения информации о новых данных. Содержит мета-данные. REQ – для запроса этих данных DATA – это сами данные. Если узел хочет послать новые данные, он сначала посылает ADV сообщение своим соседям, если кто-то из соседей заинтересован в получении этих данных то он посылает REQ сообщение, и далее получает данные(DATA-сообщение).

SPIN: Sensor Protocols for Information via Negotiation

Существует несколько протоколов семейства SPIN: SPIN-1 : стандартный протокол. SPIN-2 : протокол использующий информацию об оставшейся энергии. SPIN-BC : для распространения broadcast сообщений. SPIN-PP : для передачи сообщений точка-точка(point-to-point). SPIN-EC: подобен предыдущему но с использованием информации об энергии (energy heuristic). SPIN-RL: разработан для нестабильных каналов (lossy channels). Протоколы семейства SPIN хорошо подходят для приложений, где узлы мобильны, так как им требуется только локальная информация о соседях. Недостатком SPIN протоколов является то, что они не гарантируют доставку данных.

Directed Diffusion C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed di®usion: a scalable and robust communication paradigm for Sensor networks," Proceedings of ACM MobiCom '00, Boston, MA, 2000, pp

Data-centric routing Сенсорная сеть рассматривается как виртуальная база данных. Реализована обработка запросов от БС. Запрос распространяется по всей сети (флудинг) либо передается выбранной группе узлов. В ответ узлы, имеющие запрашиваемые данные, посылают их обратно на БС. Промежуточные узлы могут объеденять данные. Event Sensor sources Sensor sink Directed Diffusion A sensor field

Directed Diffusion Directed Diffusion – это data-centric и application-aware протокол в котором все данные генерируемые сенсорными узлами обозначаются парами атрибутов. Основная идея протокола Directed Diffusion – это комбинирование данных от различных источников на промежуточном узле (in-network aggregation) устраняя избыточность и уменьшая количество передач, таким образом продлевая время жизни сети.

Directed Diffusion Основные элементы Directed Diffusion Naming. Данные обозначаются с помощью атрибутов. Interests. Узел запрашивает данные посылая запрос (interest) на определенные данные. Gradients. Градиенты (gradients) установлены в пределах сети, чтобы доставлять данные совпадающие с запросом. Reinforcement. БС «устанавливает» (reinforce) определенные маршруты, чтобы доставлять данные с большей скоростью (данные о быстро меняющихся событиях).

Directed Diffusion Naming Content based naming Задачи обозначаются списком атрибутов – парами значений. Описание задачи определяет запрос(interest) на данные, которые совпадают с атрибутами. Отслеживание животных: Описание запроса Type = four-legged animal Interval = 20 ms Duration = 1 minute Location = [-100, -100; 200, 400] Запрос Данные узла Type =four-legged animal Instance = elephant Location = [125, 220] Confidence = 0.85 Time = 02:10:35 Ответ

Directed Diffusion Interests БС периодически посылает (broadcast) запрос (interest) на данные всем своим соседям. Кадый узел хранит interest cache. Каждая запись соответствует индивидуальному запросу. Не содержит информации о БС. Объединение (aggregation) совпадающих запросов. Каждая запись в кеше имеет несколько полей. Отметка о времени приема последнего сопадающего запроса. Несколько градиентов: скорость данных, продолжительность, направление.

Directed Diffusion Установление градиента Source Sink Interest = Заспрос Gradient = Кто запрашивает (data rate, duration, direction) Выбор соседа : 1. Флудинг 2. Географический роутинг 3. Использование данных кеша

Directed Diffusion Распространение данных Сенсорный узел вычисляет наивысшую запрашиваемую «скорость событий» (event rate) среди всех своих исходящих градиентов. Когда узел получает данные: Находит совпадающий запрос в своем кеше. Просматривает свой gradient list и отсылает данные по скорости (rate). В кеше хранится информация о недавно посланных данных (для избежания зацикливания). Сообщение данных является unicast сообщением и посылается только определенным соседям.

Directed Diffusion Определение лучшего маршрута Source Sink Low rate event Узел является участником маршрута: 1. Есть хотя бы один сосед 2. Choose the one from whom it first received the latest event (low delay) 3. Choose all neighbors from which new events were recently received Reinforcement = повышенный интерес

Directed Diffusion Моделирование Приложение для мониторинга 5 источников случайно распределены по площади 70m x 70m в углу поля 5 БС случайно распределены по всей площади Высокая скорость данных 2 события/сек Низкая скорость данных 0.02 события/сек Размер данных: 64 bytes Размер запроса: 36 bytes Все источники посылают информацию об одной и той же области наблюдения.

Average Dissipated Energy (Joules/Node/Received Event) Network Size Diffusion Omniscient Multicast Flooding Directed Diffusion Результаты Directed Diffusion превосходит как флудинг так и идеальный (маршруты расчитаны априорно) алгоритмы.

Directed Diffusion Выводы Использует обработку/объединение данных внутри сети. Достигает желаемого глобального поведения посредством локального взаимодействия. Эмпирически адаптируется к окружающей обстановке.

Rumor Routing Вариант Directed Diffusion. Используется когда количество событий (events) малое, а количество запросов (queries) большое. С помощью флудинга распространяются не запросы, а информация о событиях. Долго живущие пакеты, называемые агентами, распространяют (flood) информацию о событиях по сети. Когда узел обнаруживает событие, он добавляет его в таблицу событий и генерирует агента. Агенты путешествуют по сети, распространяя информацию о локальном событии. Время жизни агента (Time-To-Live)

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

Hierarchical based protocols

LEACH: Low-Energy Adaptive Clustering Hierarchy PEGASIS : Power-Efficient GAthering in Sensor Information Systems TEEN and APTEEN: Threshold-sensitive Energy Efficient Protocols SOP : Self-Organization Protocol Hierarchical based protocols

LEACH: Low-Energy Adaptive Clustering Hierarchy M.J. Handy, M. Haase, D. Timmermann

LEACH: Low-Energy Adaptive Clustering Hierarchy Узлы самоорганизуются в кластеры и выбирают cluster head. Все узлы, которые не являются cluster headами, передают информацию cluster headу. Cluster head принимает данные, производит их обработку и передает на базовую станцию. Периодически происходит случайная смена cluster headа и перекластеризация.

LEACH: Low-Energy Adaptive Clustering Hierarchy Две фазы Организация кластеров. Передача данных cluster headу и на базовую станцию

На начальном этапе каждый узел предлагает себя в качестве cluster-headа с определнной вероятностью. Узлы которые не стали cluster-headами могут стать ими впоследствии. Решение принимается на основе заданной плотности cluster- headов в сети Для распределения энергетической нагрузки по сети, cluster- headы переодически переизбераются. LEACH: Выбор 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 расписание. Это гарантирует избежание коллизий при передаче сообщений и экономию энергии. LEACH: Фаза самоорганизации

LEACH: Фаза передачи Узлы передают данные в свое отведенное время. После получения сообщений от всех узлов, cluster-head формирует свои сообщения. Затем cluster-head передает эти сообщения на базовую станцию. Для уменьшения коллизий, cluster-headы используют CDMA коды. Перед началом передачи узел-cluster-head прослушивает канал. Если канал свободен, он передает информацию на базовую станцию.

LEACH: Достоинства Использование адаптивного самоорганизующегося протокола позволяет распределить энергетическую нагрузку по всей сети. Позволяет проводить обработку данных на cluster-headе, что может уменьшить количество данных передаваемых по сети. Оптимальное количество кластеров может быть определено заранее в зависимости от топологии сети и отношения затрат на обработку/передачу информации. Первая «смерть» узла происходит в восемь раз позже, чем при использовании прямой передачи и статическиз кластерных протоколов.

PEGASIS : Power-Efficient GAthering in Sensor Information Systems S. Lindsey, C. Raghavendra, \PEGASIS: Power-E±cient Gathering in Sensor Information Systems", IEEE Aerospace Conference Proceedings, 2002, Vol. 3, 9-16 pp

PEGASIS : Power-Efficient GAthering in Sensor Information Systems Улучшение LEACH. Формирует не кластера, а цепочки. Данные передаются по цепочке и один узел их посылает. Превосходит LEACH по энергетическим показателям. Большие задержки для узлов на концах цепочки. Иерархический PEGASIS: Использование CDMA.

TEEN: Threshold sensitive Energy Efficient Network protocol A. Manjeshwar and D. P. Agarwal, "TEEN: a routing protocol for enhanced e±ciency in wireless sensor networks," In 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, April 2001.

TEEN: Threshold sensitive Energy Efficient Network Reactive, event-driven protocol for time-critical applications. Узел постоянно мониторирует среду, но передает информацию только если значение меняется значительно. Нет переодической передачи. Критические данные передаются незамедлительно. CH посылает своим узлам «жесткий» (hard) и «мягкий» (soft) порог. Жесткий порог: Узел посылает информацию CH только если значение находится в интересуемых пределах. Мягкий порог: Узел посылает информацию CH только когда значение изменилось как минимум на значение порога. Каждый узел в кластере периодически становиться CH. Иерархическая кластеризация.

TEEN: Threshold sensitive Energy Efficient Network

Хорошо подходит для приложений критичных ко времени. Меньшие энергетические затраты. Меньшие затраты, чем проактивные протоколы. «Мягкая» граница может адаптироваться. «Жесткая» граница может варьироваться в зависимости от приложений. Не подходит для периодического мониторинга.

APTEEN: Adaptive Threshold sensitive Energy Efficient Network Расширение TEEN для поддержки и периодического мониторинга так и для реакции на критические события. В отличии от TEEN узел должен собрать и передать данные, если они не были посланы за определенный период времени (count time), который устанавливается CH. По сравнению с алгоритмом LEACH, TEEN&APTEEN потребляют меньшее количество энергии. Недостатки Накладные расходы и сложность формирования многоуровневых кластеров и организации пороговых функций.

SOP: Self – Organization Protocol L. Subramanian and R. H. Katz, An Architecture for Building Self Configurable Systems", in the Proceedings of IEEE/ACM Workshop on Mobile Ad Hoc Networking and Computing, Boston, MA, August 2000.

SOP: Self – Organization Protocol Архитектуры поддерживает разнотипные узлы. Стационарные узлы роутеры используются как основа сети. Мобильные или стационарные сенсорные узлы посылают информацию на роутеры Сенсорный узел может быть частью сети только в случае если он может передать информацию на роутер напрямую. Данная архитектура требует возможности адресации каждого узла.

SOP: Self – Organization Protocol Достоинства: Подходит для приложений где нужна связь с определенным узлом. Небольшие затраты на поддержание таблицы маршрутизации. Сохранение сбалансированной маршрутной иерархии. Сохранение энергии : использование ограниченного подмножества узлов. Недостатки: Данный протокол не является протоколом «по требованию» особенно, что касается организационной фазы. Существование множества разрывов повышает вероятность реорганизации сети (затратная операция).

Location based protocols

GAF: Geographic Adaptive Fidelity GEAR: Geographic and Energy Aware Routing Location based protocols

GAF: Geographic Adaptive Fidelity Y. Xu, J. Heidemann, D. Estrin, Geography-informed Energy Conservation for Ad-hoc Routing," In Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking 2001, pp

GAF: Geographic Adaptive Fidelity Location-based протокол учитывающий энергетические ресурсы узла. Каждый узел знает свои координаты через GPS. Ассоциирует себя с точкой на виртуальной решетке. Узлы которые считают что находятся в одной точки равнозначны в терминах «стоимости» маршрутизации пакета. Узел 1 может достичь любой из узлов 2,3 или 4 следовательно узлы 2,3,4 эквивалентны. Любые 2 могут находиться в спящем режиме без влияния на маршрутизацию.

GAF: Geographic Adaptive Fidelity Разработан преимущественно для MANET, но может быть использован и для сенсорных сетей. Три состояния: Обнаружение (Discovery): Определяет соседей в решетке. Активное Спящее При учете мобильности Каждый узел оценивает время своего «оставления» решетки и посылает это время соседям. Соседние узлы регулируют время для сна, чтобы обеспечить маршрутизацию.

Base Station GAF: Geographic Adaptive Fidelity

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

GEAR: Geographic and Energy Aware Routing Y. Yu, D. Estrin, and R. Govindan, Geographical and Energy-Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks", UCLA Computer Science Department Technical Report, UCLA-CSD TR , May 2001.

GEAR: Geographic and Energy Aware Routing Ограничивает число пересылаемых запросов в directed diffusion. Рассматривает только определенный район сети, вместо всей сети в целом. Каждый узел хранит estimated cost & learning cost на достижение БС через своих соседей. Estimated cost = f(оставшаяся энергия, расстояние до точки назначения) Learned cost is propagated one hop back every time a packet reaches the sink. Route setup for the next packet can be adjusted

GEAR: Geographic and Energy Aware Routing Фаза 1: Пересылка пакетов в определенный район: Пересылка пакета соседнему узлу с минимальной функцией f (ближайший к БС и имеющий наибольшую энергию) Если все узлы находяться дальше чем сам узел отправитель, то выбирается один из соседей с на основе learned cost.

GEAR: Geographic and Energy Aware Routing Фаза 2: Пересылка пакета в пределах нужной области. Применяется любое рекурсивное отправление сообщений. Район делиться на 4 под-области и посылается 4 копии пакета. Повторяется до тех пор пока не остануться районы с одним узлом. Применяется ограниченный флудинг. Применяется когда плотность узлов мала.

Base Station Region of Interest GEAR: Geographic and Energy Aware Routing

Routing Protocols based on Protocol Operations

Протоколы маршрутизации со многими маршрутами (Multipath routing) Протоколы маршрутизации «по запросу» (Query based routing) Протоколы маршрутизации основанные на «переговорах» (Negotiation routing) QoS-based протоколы Когерентная и некогерентная обработка данных. Routing Protocols based on Protocol Operations

Multipath Routing Protocols Протоколы маршрутизации со многими маршрутами (Multipath routing) Повышение надежности передачи информации, за счет существования нескольких маршрутов. Увеличивает энергетические затраты. Увеличивает количество трафика в сети.

Выбор маршрута на основе информации об наибольшей оставшейся энергии на узлах. J.-H. Chang and L. Tassiulas, Maximum Lifetime Routing in Wireless Sensor Networks. Выбор наименне энергетически затратного маршрута C. Rahul, J. Rabaey, \Energy Aware Routing for Low Energy Ad Hoc Sensor Networks Разбор сообщения на части, и передача этих частей по разным маршрутам. S. Dulman, T. Nieberg, J. Wu, P. Havinga, Trade-Off between Traffic Overhead and Reliability in Multipath Routing for Wireless Sensor Networks" Multipath Routing Protocols

Query-based routing В данном типе протоколов, БС инициирует сообщение-запрос необходимых данных, данный запрос распространяется по сети и узел имеющий необходимые данные отправляет эти данные узлу, инициирующему запрос. Rumor Routing. Direct Diffusion

Negotiation-based routing Протоколы этого типа используют высокоуревневое описание данных, чтобы устранить передачу избыточной информации. Основная идея таких протоколов состоит в использовании пердварительных «переговоров», для избежания передачи повторной передачи. SPIN протокол. Распространение информации от одного узла ко всем остальным, предполагая что они являются потенциальной базовой станцией. J. Kulik, W. R. Heinzelman, and H. Balakrishnan, "Negotiation-based protocols for disseminating information in wireless sensor networks

QoS-based routing Такие протоколы обеспечивают баланс между энергозатратами и качеством передачи информации. SAR: Sequential Assignment Routing Выбор маршрута зависит от трех факторов: энергетические ресурсы, QoS на каждый маршрут и уровень приоритета пакета. SPEED: A stateless protocol for real-time communication in sensor networks Каждый узел хранит информацию о своих соседях и использует географическую информацию для нахождения путей. Стремиться гарантировать постоянную скорость доставки. Маршрутный модуль: Stateless Geographic Non-Deterministic forwarding (SNFG) Выбирает маршрут на основе задержки ответа на запрос.

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

Когерентная и некогерентная обработка данных K. Sohrabi, J. Pottie, "Protocols for self-organization of a wireless sensor network" Single winner algorithm (SWE) Алгоритм для некогерентной обработки Один узел выбирается для сложной обработки данных. Выбор узла основан на вычислительных способностях и энергетических резервов этого узла. Multiple winner algorithm (MWE) Алгоритм для когерентной обработки Большие задержки, высокие накладные расходы, меньшая масштабируемость чем у некогерентной обработки.

Классификация протоколов маршрутизации

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

Протоколы маршрутизации: перспективы. Эффективное использование In-network обработки данных Временная и пространственная синхронизация. Локализация. Самоконфигурация и переконфигурация. Безопасная маршрутизация. Взаимодействие с глобальными сетями

Протоколы маршрутизации: заключение. Маршрутизация в беспроводных сенсорных сетях это новое направление которое активно развивается. В рамках данной лекции ма рассмотрели основные протоколы маршрутизации в сенсорных сетях, их классификацию и требования которые к ним предъявляются, а также основные направления будущих исследований.

Литература Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Modelling Data-Centric Routing in Wireless Sensor Networks Bhaskar Krishnamachari, Deborah Estrin, Stephen Wicker Modelling Data-Centric Routing in Wireless Sensor Networks Adaptive Protocols for Information Dissemination in Wireless Sensor Networks Wendi Rabiner Heinzelman, Joanna Kulik, and Hari Balakrishnan Adaptive Protocols for Information Dissemination in Wireless Sensor Networks Building Efficient Wireless Sensor Networks with Low-Level Naming J.Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan, SOSP 2001 Building Efficient Wireless Sensor Networks with Low-Level Naming

The End