Статья на тему Методы маршрутизации в беспроводных сетях.

Введение:

Исследования в области беспроводных сенсорных сетей (BSS) на сегодняшний день являются одними из самых приоритетных и популярных в мире. Несмотря на обилие публикаций в зарубежных изданиях, в русскоязычной научной литературе по этой тематике все еще существует значительный пробел. Данная статья представляет обзор о методах и принципах маршрутизации в БСС на примере десяти наиболее характерных и известных алгоритмов SPIN, DD, RR, GBR, GPSR, MCF, LEACH, TEEN, GAF, TTDD, для которых приводится краткое описание с библиографической ссылкой на источник.
1. SPIN (Sensor Protocols for Information through Negotiation). SPIN представляет собой семейство протоколов, обеспечивающих доставку данных на основе процедуры «переговоров»[1]. Относится к одноранговым методам маршрутизации без гарантированной доставки сообщений. Он хорошо подходит для динамических топологий с мобильными узлами. Используется адаптивная версия простого метода распространения лавины («флуд»), что повышает эффективность маршрутизации по сравнению с прототипом. Сообщение от каждого узла распространяется по всей сети, что позволяет достаточно просто получать информацию от любого узла по запросу с немедленной доставкой. Механизм взаимодействия основан на трех типах сообщений: ADV — информирует о наличии новых данных в узле, содержит их описание в виде так называемых «метаданных»; REQ — для запроса данных; DATA — для отправки непосредственно самих данных.

Фрагмент текста работы:

DD (Directed Diffusion). Основные характеристики метода DD: ориентирован на централизованную модель сбора данных (data-centric) с доставкой по запросу (query-driven); взаимодействие узлов локальное; использует высокоуровневые средства именования данных [2]. Централизованная модель составляет наличие в сети центрального узла сбора данных (sink) и маршрутизацию от нескольких источников данных к одному приемнику. Процесс маршрутизации начинается с того, что центральный узел посылает запрос (interest).
Поскольку данные в узле представлены в виде пар атрибут-значение, запрос указывает на интересующие центральный узел параметры и их возможные значения (или диапазон значений). Каждый узел ведет локальный кэш запросов, в котором хранятся записи о состоянии активных запросов. Для каждого запроса в кэше хранятся дополнительные данные, такие как метка времени (timestamp), т.е. значение таймера, фиксирующее момент получения запроса; градиенты (gradient) для каждого соседнего узла, указывающие на скорость обмена (data rate), длительности существования по таймеру (duration) и время жизни (expiresAt). Описанная структура кэша запросов является основой для оптимальной маршрутизации. Запросы с «интересом» периодически повторяются центральным узлом для обеспечения надежности доставки и работоспособности общей схемы маршрутизации в случае сбоев в сети.
3. RR (Rumor Routing)
RR является разновидностью предыдущего алгоритма [3]. Оптимизирует схему маршрутизации для сетей, где количество событий невелико, а количество запросов велико. Каждый узел ведет свою собственную таблицу событий. При возникновении событий информация о них заносится в таблицу и генерируются специальные сообщения, называемые «агентами», которые содержат информацию о локальном событии узла. Сообщения такого типа отправляются в сеть, по которой они «путешествуют», распространяя информацию о произошедших событиях на другие узлы. При получении этих сообщений удаленные узлы пополняют свою таблицу событий и передают агента соседним узлам до тех пор, пока не закончится его время жизни (TTL-TimeToLive). Когда узел Central передает запрос на данные, которые уже были получены в результате события, узлы, через которые посылается запрос, просматривают свои таблицы событий и, если найдено совпадение, информируют центр о результате. Таким образом, информация о событии поступает к запрашивающему до того, как запрос достигает требуемого источника данных. Если вся цепочка промежуточных узлов, переданных агентом к данному узлу, сохраняется в таблице событий, то задача определения местоположения исходного узла в сети гораздо проще.