close

Вход

Забыли?

вход по аккаунту

?

Классификация методов маршрутизации в беспроводных сенсорных сетях.

код для вставкиСкачать
ИЗВЕСТИЯ ВолгГТУ
181
УДК 681.3
А. М. Бершадский, Л. С. Курилов, А. Г. Финогеев
КЛАССИФИКАЦИЯ МЕТОДОВ МАРШРУТИЗАЦИИ
В БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ
Пензенский государственный университет
bam@pnzgu.ru, kleon@nextmail.ru, finogeev@sura.ru
В статье описывается специфика маршрутизации в беспроводных сенсорных сетях и параметры узлов
для расчета маршрутов. Приводятся требования к методам маршрутизации и дается классификационная
схема методов на основе наиболее значимых признаков.
Ключевые слова: беспроводные сенсорные сети, распределенные системы, методы маршрутизации,
классификация, терминология.
A. M. Bershadsky, L. S. Kurilov, A. G. Finogeev
CLASSIFICATION OF METHODS FOR ROUTING IN WIRELESS SENSOR NETWORKS
Penza State University
The article describes some details of routing technique in wireless sensor networks and node’s parameters using for
route calculations. The requirements for routing methods are considered, the taxonomy of the routing methods is given.
Keywords: wireless sensor networks, distributed systems, methods, routing, classification, and terminology.
Современная беспроводная сенсорная сеть
(БСС) представляет собой программно-технический комплекс, реализующий в полной мере
концепцию распределенных систем (РС) и характеризующийся особенной архитектурой и
сложным коммуникационным поведением узлов, и является, по сути, конгломератом различных технологий сбора, передачи и обработки данных, подобранных и разработанных для
оптимального выполнения специфических задач. Соответственно, методы маршрутизации в
подобных сетях также характеризуются определенной спецификой.
Как правило, сенсорные сети проектируются специально для конкретного приложения,
поэтому нет единой универсальной схемы построения БСС, все зависит от области применения и архитектура БСС разрабатывается с учетом достижения конкретных целей и оптимизации необходимых параметров. Соответственно,
отсутствует и универсальный, общеупотребительный метод маршрутизации, все методы в
той или иной степени направлены на определенные задачи (цели) РС или архитектуру БСС,
либо на оптимизацию заданных параметров
при заданных условиях.
Из-за специфики БСС, которая заключается
в основных особенностях ее построения и
функционирования, а именно: преимущественная ограниченность энергоресурсов (вследствие автономности узлов), возможность динамического изменения конфигурации (вследствие мобильности узлов), большие накладные
расходы на передачу и прием (вследствие ис-
пользования радиоэфира в качестве среды передачи), ресурсные ограничения в узлах по
объему памяти, скорости обработки, времени
реакции и т. п. (вследствие требований миниатюризации, низкой стоимости узлов), многозвенная топология и т. д., методы маршрутизации в БСС могут существенно отличаться от
методов маршрутизации в обычных проводных
сетях, а также беспроводных сетях с использованием стационарных маршрутизаторов типа WiFi.
Перечислим основные параметры узла, которыми могут оперировать алгоритмы маршрутизации при выборе того или иного пути
ретрансляции сообщения: 1) текущий уровень
энергозапасов узла; 2) пространственное расположение узла; 3) список соседних узлов (тех
узлов, с которыми данный узел находится в непосредственной близости и имеет прямой доступ в зоне действия радиосигнала) и их параметров; 4) уровень радиосигнала до соседних
узлов; 5) загруженность узла; 6) доступный
объем памяти для хранения данных маршрутизации, истории, кэша, для буферизации очереди
ретранслируемых сообщений и т. д. Некоторые
из перечисленных параметров (а также их совокупность) можно использовать в качестве
метрик или критериев для выполнения процедуры маршрутизации.
Необходимо привести также основные требования к алгоритмам маршрутизации в БСС.
Следует отметить, что отдельные требования
могут противоречить другим требованиям, и в
общем случае может потребоваться компро-
182
ИЗВЕСТИЯ ВолгГТУ
мисс по удовлетворению целого ряда противоречивых требований, который обусловливается
конечной целью или приложением БСС.
Список требований в общем случае включает:
1) учет энергозатрат (из-за автономности питания узлов);
2) минимизацию вычислительных затрат
(так как имеется ограничение по вычислительной мощности процессоров узлов; данные затраты также влияют на задержки передачи и
расход энергии узлов);
3) минимальный объем используемой памяти (из-за ресурсного ограничения узлов);
4) максимальную скорость доставки сообщений между двумя произвольными узлами
(повышение производительности сети);
5) равномерную загруженность сети (предотвращение перегрузок и последующих блокировок на отдельных участках сети);
6) максимальную надежность работы сети
(выбор альтернативных маршрутов при отказе/выключении узлов, смене топологии);
7) экономическую эффективность (должна
быть обеспечена минимальная совокупная
стоимость сети, стоимость ее разворачивания и
поддержания в жизнеспособном состоянии);
8) минимизацию управляющего трафика в
сети (или максимизацию полезной пропускной
способности сети – соотношения объема информационной доли трафика к доле служебных
управляющих сообщений);
9) адаптивность к динамическим изменениям конфигурации и топологии БСС;
10) обеспечение безопасности сети (подразумевает учет таких аспектов, как защита передаваемых данных, защита от несанкционированного подключения к сети, аутентификация
и аудит и т. д.).
Прежде чем приступить к классификации
методов маршрутизации, следует отметить одну характерную особенность, присущую большинству БСС. Учитывая низкие показатели узлов по производительности вычислений и объему памяти, а также тот факт, что количество
узлов в БСС может достигать многих сотен и
тысяч, и топология может постоянно динамически меняться, очевидно, что хранить и поддерживать в актуальном состоянии информацию о текущей конфигурации всей сети в каждом узле на практике не представляется возможным. То есть, в отличие от традиционных
вычислительных сетей, в БСС зачастую нет
доступных ресурсов для хранения, обработки и
циркуляции по сети большого массива управляющих данных маршрутизации в условиях
обычно низкой пропускной способности самой
сети. Отсюда следует вывод о преимущественном использовании в БСС децентрализованных
локальных схем маршрутизации, в которых каждый узел в отдельности принимает решение о
перенаправлении сообщений, опираясь на сведения о ближайших соседях (т. е. на основе локальных, а не глобальных данных).
Вследствие такой специфики БСС, узкой
специализации и многообразия областей применения, таксономические схемы методов
маршрутизации также характеризуются большим разнообразием классификационных признаков. Трудно выделить среди них группу
наиболее приоритетных, все зависит от целей
проектирования БСС. Проведем классификацию по ряду наиболее значимых признаков, с
указанием англоязычной терминологии, принятой в зарубежной литературе [1–3].
1. П о с п о с о б у о п р е д е л е н и я м а р шрутов:
– проактивные («proactive»), в которых первоначально заранее определяются возможные
маршруты и составляются таблицы маршрутизации;
– реактивные («reactive»), в которых определение маршрутов происходит в реальном
времени, т. е. динамически, по конкретному запросу на маршрутизацию («по требованию»);
– смешанные схемы, когда имеются предварительные расчеты возможных маршрутов, и
далее, при необходимости, с каждым запросом
маршруты могут корректироваться.
2. П о у ч е т у и э к о н о м и и э н е р г о ресурсов сети («energy-conservation»):
– без учета;
– направленные на повышение энергоэффективости отдельных узлов либо всей сети в
целом (подразумевает равномерное распределение энергонагрузки в зависимости от энергозапасов в конкретном узле с целью максимизировать время жизни всей сети, а не отдельных
узлов). В последнем случае для выравнивания
загруженности сети необходим последовательный перебор различных маршрутов для одного
и того же узла-приемника («multipath»), что наряду с оптимизацией общего энергопотребления БСС может привести к росту задержек при
передаче.
ИЗВЕСТИЯ ВолгГТУ
3. П о п р и з н а к у с т р у к т у р н о й о р ганизации сети:
– плоские «flat», т. е. с одноранговыми («равноправными») узлами с одинаковой функциональностью;
– иерархические «hierarchical», т. е. с разделением между узлами коммуникационных
функций; подразумевают построение иерархий
нескольких уровней с различными обязанностями в плане маршрутизации. Классическим
походом в организации управляющей иерархии
для передачи данных в БСС является схема
маршрутизации, основанная на кластеризации
узлов. Узлы объединяются в группы (кластеры), в которые входят близко расположенные
узлы. Участники группы общаются непосредственно только с выделенным центром группы,
который отвечает за коммуникацию с другими
центрами. Таким образом, для реализации данной схемы необходимо включение механизмов
«голосования» по выбору кластерных центров
и их динамической смены в случае изменения
конфигурации или обеспечения равномерной
энергозагрузки. Можно провести некоторую
аналогию между подобными центрами и базовой станцией в сотовых сетях связи.
4. П о п р и з н а к у ц е н т р а л и з а ц и и
сбора данных:
– с централизованным сбором («data-centric»), когда информация со всех узлов собирается в единый центр сбора, обработки и/или
хранения данных.
– схема с множеством центров сбора, которые
могут, в принципе, взаимодействовать друг с
другом, осуществлять распределение задач сбора
и обработки, синхронизацию и коопе-рацию;
– децентрализованная схема («peer-to-peer»),
когда узлы могут общаться друг с другом произвольно и доставка в общем случае производится от любого произвольного узла к другому
произвольному узлу (как, например, при голосовой коммуникации).
5. П о п р и з н а к у в а р и а б е л ь н о с т и
топологии сети:
– ориентированные на статическую топологию, когда структуру сети образуют неподвижные («fixed») узлы, имеющие долговременную
жесткую позицию на местности. Для данного
случая структура БСС проектируется изначально и в дальнейшем, как правило, существенно
не изменяется;
– ориентированные на динамическую топологию, когда топология сети меняется с тече-
183
нием времени за счет перемещения мобильных
(«mobile») узлов. В данном контексте следует
отделять понятие «топология» от понятия
«конфигурация». Топология задает взаимное
расположение узлов и общую структуру связей
сети, конфигурация означает возможность изменения топологии за счет периодического
включения/выключения узлов, выхода их из
строя, потери связи между ними. В случае статической топологии (т. е. узлы не перемещаются друг относительно друга) конфигурация сети
также может быть динамической (допускается
динамическое добавление и исключение узлов
в структуру сети).
В ряде случаев мобильность может быть
ограничена (так, например, в некоторых видах
БСС допускается перемещение узлов только в
пределах ограниченной зоны, контролируемой
центральным узлом).
6. П о у ч е т у с п е ц и ф и к и с е т е в о г о
трафика и обеспечению качества
услуг:
– без учета;
– с учетом и с дифференциацией схем маршрутизации для разных видов трафика (например, таких как потоковое видео, аудио, голосовые потоки, телеметрия, неотложные сообщения). Существуют различные приложения БСС,
и для некоторых требуется обеспечить доставку
данных в реальном времени; для других допустима отложенная доставка и задержки при передаче не имеют решающего значения; для
третьих данные собираются в режиме «off-line»
по запросу из центров сбора. Таким образом,
методы ретрансляции разнородного трафика
могут основываться на таких критериях, как
минимум задержек, гарантия поддержания постоянной полосы пропускания, учет текущей
загруженности маршрутов, а не только опираться на простые метрики типа количества
промежуточных узлов в маршруте, пространственное расстояние между узлами и т. п. Безусловно, при обеспечении качества обслуживания
могут пострадать другие аспекты маршрутизации. Например, для уменьшения задержек требуется выбирать кратчайшие маршруты, что
может противоречить требованию обеспечения
равномерного расхода энергии БСС, при котором маршруты выбираются исходя из необходимости равномерного распределения нагрузки.
7. П о и с п о л ь з о в а н и ю д о п о л н и тельной информации о местоположении узла («location»):
184
ИЗВЕСТИЯ ВолгГТУ
– без использования;
– с использованием информации о географическом расположении узла («geographic routing»). Как правило, дополнительные данные о
положении узлов в пространстве повышают
эффективность маршрутизации, однако требуют дополнительных затрат. К примеру, точное
определение положения может осуществляться
с помощью дополнительного оборудования в
узле (такого, как GPS-приемник), а приблизительное определение относительного положения – с применением специальных методов
расчета на основе данных об уровне радиосигнала от ближайших соседних узлов, находящихся в зоне радиодоступа исходного узла.
8. П о с п о с о б у в з а и м о д е й с т в и я
узлов:
– поддержка связи «один к одному» («unicast»);
– поддержка связи «один ко многим» («multicast»), когда общение исходного узла происходит с множеством других узлов;
–
широковещательное
взаимодействие
(«broadcast»); имеет место в тех случаях, когда
данные из одного узла распространяются во все
остальные узлы сети (в БСС обычно посредством техники «flooding»).
9. П о у ч е т у п е р и о д и ч е с к о й а к тивности узлов («sleeping time»):
– без учета;
– с учетом. В данном случае БСС состоит из
узлов, не имеющих возможности постоянно
прослушивать радиоэфир с постоянной готовностью к ретрансляции данных и обладающих
ограниченным период активации, возобновляемой через определенные временные интервалы.
Это обусловлено необходимостью сохранения
энергии для увеличения времени жизни сети.
Здесь требуется особый подход, обеспечивающий доставку в условиях возникновения временных «дыр» в топологии сети.
10. П о и с п о л ь з о в а н и ю у н и к а л ь ной идентификации узла:
– с использованием идентификатора узла
(сетевого адреса);
– без использования. Методы, в которых
адресация на основе уникальных адресов оказывается излишней, применяются в БСС, состоящей из большого числа узлов, плотно распределенных по небольшой территории. Обычно, наряду с сенсорными данными от таких
узлов для ряда приложений, достаточно передавать информацию о месте расположения узла
(географическую метку).
11. П о с т е п е н и н а д е ж н о с т и д о с тавки данных:
– ненадежные, работающие без подтверждения о доставке. Посланные сообщения по
разным причинам могут теряться в процессе
передачи от узла-источника к приемнику;
– надежные, с подтверждением доставки отправителю, т. е. обеспечивающие гарантию доставки. Проблема повышения надежности передачи влечет за собой множество накладных
расходов, связанных с увеличением объема
служебного трафика. Так, например, если получать подтверждение при каждом прыжке
(«multihop») между промежуточными узлами
маршрута от очередного узла цепочки, то наблюдается значительный рост управляющих
сообщений и снижение полезной нагрузки сети.
Если же получать подтверждение только от
приемника (конечного узла в цепочке маршрута), то из-за частых сбоев при передаче, характерных для беспроводных сетей, возможно значительное замедление процесса передачи (время на отслеживание тайм-аутов, на повторную
пересылку, ожидание ответа и т. д.).
12. П о у ч е т у м е т о д о в с б о р а и п е редачи данных:
– без учета;
– с учетом.
Среди х а р а к т е р н ы х м е т о д о в и н тероперабельности, влияющих на
выбор средств коммуникации и
м а р ш р у т и з а ц и и , можно выделить следующие:
– управляемые по таймеру («time-driven»);
здесь передача данных с узлов осуществляется
через определенные временные интервалы, например, с определенной частотой дискретизации;
– управляемые по событию («event-driven»),
когда коммуникация происходит при возникновении некоторых событий. Например, узел
может не передавать постоянно измеряемые
параметры среды (объекта), а контролировать
параметры локально и генерировать сообщения
только в тех случаях, когда происходит изменение параметра в заданных пределах. Такая
предварительная обработка не требует существенных вычислительных ресурсов, однако значительно снижает нагрузку на сеть;
– управляемые по запросу («query-driven»),
когда передача сенсорных данных, генерируемых узлом, инициируется со стороны центра
сбора данных (узлом-коллектором) специальным запросом.
185
ИЗВЕСТИЯ ВолгГТУ
Сюда также можно отнести другие методы,
например, с использованием агрегации данных
(«data aggregation») по маршруту доставки, когда в процессе маршрутизации к данным исходного узла поочередно добавляются собственные данные всех промежуточных узлов.
В заключение необходимо отметить, что
при решении задач маршрутизации в БСС, т. е.
фактически при конкретной оптимальной реализации сетевого уровня взаимодействия, приходится принимать во внимание множество
смежных проблем, влияющих непосредственно
на качество процесса доставки сообщений – таких как адресация сетевых узлов, синхронизация узлов с соседями, устранение и минимизация коллизий, обеспечение промежуточной обработки данных и т. д. Грамотный и адекватный выбор метода маршрутизации с учетом
множества факторов и технических условий позволяет значительно увеличить производительность БСС, либо существенно сократить требования к аппаратным ресурсам узлов, что, в свою
очередь, приводит к снижению стоимости.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Acs G., Buttyan L. A Taxonomy of Routing Protocols
for Wireless Sensor Networks. Laboratory of Cryptography
and Systems Security, Department of Telecommunications,
Budapest University of Technology and Economics. Hiradastechnika. Scientific Association for Infocommunications,
H-1055 Budapest, Hungary. January 12, 2007.
2. Al-Karaki J. N., Kamal A. E. Routing Techniques in
Wireless Sensor Networks: A Survey // IEEE Wireless Communications, Vol. 11, 2004, pp. 6–28.
3. K. Akkaya, M. Younis. A Survey of Routing Protocols
in Wireless Sensor Networks // Ad Hoc Networks Journal,
Vol. 3(3), 2005, pp. 325–349.
УДК 004.724.4
Д. В. Кутузов, В. А. Филин
СТРУКТУРА И МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНОЙ
ПРОСТРАНСТВЕННОЙ КОММУТАЦИОННОЙ СИСТЕМЫ
Астраханский государственный университет
d_kutuzov@aspu.ru, kachestvo@aspu.ru
В работе представлены результаты синтеза параллельных пространственных коммутационных систем,
описан элемент коммутации этих систем. Представлена математическая модель функционирования параллельных пространственных систем коммутации.
Ключевые слова: коммутация, параллельная коммутация, пространственная коммутация, математическое моделирование, элементы коммутации, ячейки коммутации.
D. V. Kutuzov, V. A. Filin
THE STRUCTURE AND MATHEMATICAL MODEL
OF PARALLEL SPATIAL SWITCHING SYSTEM
Astrakhan State University
The paper presents the results in the synthesis of parallel spatial switching systems, switching element described
for these systems. The paper presents the mathematical model of the parallel spatial switching systems.
Keywords: switching, parallel switching, space switching, mathematic modeling, elements of switching, cells of
switching.
При реализации различных режимов коммутации значительную роль играют механизмы
настройки коммутационных схем. Настройка
коммутационной системы – это процесс установления составляющих ее коммутационных
элементов в определенные состояния, для того
чтобы реализовать необходимые соединения.
Чтобы установить необходимые соединения
источников и приемников информации в системе пространственной коммутации или передать пакет в системе пакетной коммутации, не-
обходимо изменить состояния некоторых или
всех элементов схемы.
Параллельные пространственные системы
коммутации обычно реализуются как системы с
самонастройкой. В подобных системах ячейки
коммутации должны иметь собственное локальное управляющее устройство [1].
Наиболее простой коммутационной ячейкой
является схема [2], представленная на рис. 1. Она
состоит из элемента сложения по модулю два,
RS-триггера и ключевого элемента И.
Документ
Категория
Без категории
Просмотров
62
Размер файла
319 Кб
Теги
сетях, методов, маршрутизация, беспроводные, сенсорными, классификация
1/--страниц
Пожаловаться на содержимое документа