Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «КубГУ»)

Кафедра вычислительных технологий

МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

АНАЛИЗ РАБОТОСПОСОБНОСТИ БЕСПРОВОДНОЙ

СЕНСОРНОЙ СЕТИ

Работу выполнил - Бондарь Роман Александрович

Факультет компьютерных технологий и прикладной математики

Направление магистерской подготовки 010300.68

Фундаментальные информатика и информационные технологии

Научный руководитель, доктор ф.-м. наук, профессор - А.В. Смирнова

Научный руководитель, канд. ф.-м. наук, доцент - Е.В. Кособуцкая

Нормоконтролер, канд. физ.-мат. наук, доцент - Е.А. Данилов

Краснодар 2013

Содержание

• Введение
• 1. Беспроводные сенсорные сети
• 1.1 История и сфера использования
• 1.2 Технология
• 1.3 Платформы
• 1.4 Алгоритмы канального уровня
• 2. Алгоритмы маршрутизации в беспроводных сенсорных сетях
• 2.1 Требования к алгоритмам маршрутизации в БСС
• 2.2 Обзор алгоритмов маршрутизации в БСС
• 2.3 Сравнение алгоритмов маршрутизации в БСС
• 3. Имитационное моделирование беспроводных сенсорных сетей
• 3.1 Особенности моделирования БСС
• 3.2 Обзор систем моделирования БСС.
• 3.3 Система Castalia.
• 4. Анализ работоспособности беспроводных сенсорных сетей
• 4.1 Модель надежности беспроводной сенсорной сети
• 4.1.1 Модель надежности передачи пакета данных между двумя узлами
• 4.1.2 Модель надежности узла
• 4.1.3 Модель надежности коммуникации между узлами
• 4.2 Исследование надежности передачи пакета данных между двумя узлами в системе Castalia.
• 4.2.1 Влияние помех на надежность коммуникационной среды между двумя узлами в системе Castalia
• 4.2.2 Влияния мощности радио-модуля на надежность коммуникационной среды между двумя узлами в системе Castalia
• 4.3 Исследование надежности сбора информации сетью в системе Castalia
• 4.3.1 Влияние помех на надежность сбора информации сетью в системе Castalia
• Заключение
• Библиографический список
• Приложение А
• Приложение Б
• Введение
• В настоящее время распределенные системы все шире входят в нашу жизнь. Одним из направлений современных распределенных систем являются беспроводные сенсорные сети.
• Беспроводная сенсорная сеть - это распределённая, самоорганизующаяся сеть множества датчиков (сенсоров) и исполнительных устройств, объединенных между собой посредством радиоканала. Причем область покрытия подобной сети может составлять от нескольких метров до нескольких километров за счет способности ретрансляции сообщений от одного элемента к другому.
• Беспроводные сенсорные сети (БСС) получили большое развитие в последнее время. Такие сети, состоящие из множества миниатюрных узлов, оснащенных маломощным приемо-передатчиком, микропроцессором и сенсором, могут связать воедино глобальные компьютерные сети и физический мир. Концепция беспроводных сенсорных сетей привлекает внимание многих ученых, исследовательских институтов и коммерческих организаций, что обеспечивает большой поток научных работ по данной тематике. Большой интерес к изучению таких систем обусловлен широкими возможностями применения сенсорных сетей. Беспроводные сенсорные сети, в частности, могут использоваться для предсказания отказа оборудования в аэрокосмических системах и в системах автоматизации зданий. Из-за своей способности к самоорганизации, автономности и высокой отказоустойчивости такие сети активно применяются в системах безопасности и военных приложениях. Успешное применение беспроводных сенсорных сетей в медицине для мониторинга здоровья связано с разработкой биологических сенсоров совместимых с интегральными схемами сенсорных узлов. Но наибольшее распространение беспроводные сенсорные сети получили в области мониторинга окружающей среды и живых существ.
• Цели данной работы: рассмотреть математические методы оценки надежности БСС и программные продукты для имитационного моделирования БСС, провести их анализ с целью выбора системы, наиболее подходящей для оценки работоспособности БСС, с ее помощью оценить влияние помех и мощности передачи радиосигнала на работоспособность БСС.
• Магистерская диссертация состоит из введения, четырёх глав, заключения, библиографического списка и двух приложений.
• Первая глава содержит общий обзор БСС.
• Во второй главе приведено описание и сравнительный анализ некоторых алгоритмов маршрутизации в БСС.
• В третьей главе содержится обзор и сравнительный анализ современного программного обеспечения для имитационного моделирования БСС, подробно описывается система Castalia.
• Четвёртая глава посвящена рассмотрению математических методов оценки надежности БСС, в ней описываются функциональные возможности системы Castalia, также описаны модули, разработанные для проведения моделирования. Представлены результаты моделирования влияния помех и мощности передачи радиосигнала на работоспособность БСС, приводятся графики и таблицы для иллюстрации полученных результатов.
• В приложении А приводится исходный текст модулей, разработанных для моделирования надежности связи между двумя узлами.
• Приложение Б содержит исходный текст модулей, разработанных для моделирования надежности сбора данных беспроводной сенсорной сетью.

1. Беспроводные сенсорные сети

Беспроводная сенсорная сеть - распределённая, самоорганизующаяся сеть множества датчиков (сенсоров) и исполнительных устройств, объединенных между собой посредством радиоканала. Область покрытия подобной сети может составлять от нескольких метров до нескольких километров за счёт способности ретрансляции сообщений от одного элемента к другому.

1.1 История и сфера использования

Одним из первых прообразов сенсорной сети можно считать систему СОСУС, предназначенную для обнаружения и идентификации подводных лодок[8]. В середине 1990-х годов технологии беспроводных сенсорных сетей стали активно развиваться, в начале 2000-х годов развитие микроэлектроники позволило производить для таких устройств достаточно дешёвую элементную базу. Беспроводные сети начала 2010-х годов в основном базируются на стандарте ZigBee[6].

Многие отрасли и сферы деятельности (промышленность, транспорт, коммунальное хозяйство, охрана) заинтересованы во внедрении сенсорных сетей, и число потребителей непрерывно увеличивается. Тенденция обусловлена усложнением технологических процессов, развитием производства, расширяющимися потребностями частных лиц в сегментах безопасности, контроля ресурсов и использования товарно-материальных ценностей. С развитием микроэлектронных технологий появляются новые практические задачи и теоретические проблемы, связанные с применениями сенсорных сетей в промышленности, жилищно-коммунальном комплексе, домашних хозяйствах. Использование недорогих беспроводных сенсорных устройств контроля параметров открывает новые области для применения систем телеметрии и контроля, такие как:

· своевременное выявление возможных отказов исполнительных механизмов, по контролю таких параметров, как вибрация, температура, давление и т. п.;

· контроль доступа к удалённым системам объекта мониторинга в режиме реального времени:

· обеспечение охраны музейных ценностей;

· обеспечение учёта экспонатов;

· автоматическая ревизия экспонатов;

· автоматизация инспекции и технического обслуживания промышленных активов;

· управление коммерческими активами;

· применение как компонентов в энерго- и ресурсосберегающих технологиях;

· контроль экологических параметров окружающей среды.

Следует отметить, что несмотря на длительную историю сенсорных сетей, концепция построения сенсорной сети окончательно не оформилась и не выразилась в определенные программно-аппаратные (платформенные) решения. Реализация сенсорных сетей на текущем этапе во многом зависит от конкретных требований индустриальной задачи. Архитектура, программно-аппаратная реализация находится на этапе интенсивного формирования технологии, что обращает внимание разработчиков с целью поиска технологической ниши будущих производителей.

1.2 Технология

Беспроводные сенсорные сети (англ. WSN -- Wireless Sensor Network) состоят из миниатюрных вычислительных устройств -- мотов, снабжённых сенсорами (датчиками температуры, давления, освещенности, уровня вибрации, местоположения и т. п.) и трансиверами, работающими в заданном радиодиапазоне. Гибкая архитектура, снижение затрат при монтаже выделяют беспроводные сети интеллектуальных датчиков среди других беспроводных и проводных интерфейсов передачи данных, особенно когда речь идет о большом количестве соединенных между собой устройств, сенсорная сеть позволяет подключать до 65000 устройств[24]. Постоянное снижение стоимости беспроводных решений, повышение их эксплуатационных параметров позволяют постепенно переориентироваться с проводных решений в системах сбора телеметрических данных, средств дистанционной диагностики, обмена информации. «Сенсорная сеть» является сегодня устоявшимся термином (англ. Sensor Networks), обозначающим распределенную, самоорганизующуюся, устойчивую к отказу отдельных элементов сеть из необслуживаемых и не требующих специальной установки устройств. Каждый узел сенсорной сети может содержать различные датчики для контроля внешней среды, микрокомпьютер и радиоприемопередатчик. Это позволяет устройству проводить измерения, самостоятельно проводить начальную обработку данных и поддерживать связь с внешней информационной системой.

Технология ретранслируемой ближней радиосвязи 802.15.4/ZigBee[11], известная как «Сенсорные сети», является одним из современных направлений развития самоорганизующихся отказоустойчивых распределенных систем наблюдения и управления ресурсами и процессами. Сегодня технология беспроводных сенсорных сетей, является единственной беспроводной технологией, с помощью которой можно решить задачи мониторинга и контроля, которые критичны к времени работы датчиков. Объединенные в беспроводную сенсорную сеть датчики образуют территориально-распределенную самоорганизующуюся систему сбора, обработки и передачи информации. Основной областью применения является контроль и мониторинг измеряемых параметров физических сред и объектов.

Принятый стандарт IEEE 802.15.4[11] описывает контроль доступа к беспроводному каналу и физический уровень для низкоскоростных беспроводных персональных сетей, то есть два нижних уровня согласно сетевой модели OSI. «Классическая» архитектура сенсорной сети основана на типовом узле, который включает в себя:

· радиотракт;

· процессорный модуль;

· элемент питания;

· различные датчики.

Использование в типовом узле сенсорной сети в качестве датчика второго трансивера, соответствующего стандарту ISO 24730-5, позволяет использовать сенсорную сеть не только для мониторинга параметров сред и объектов, но и для определения местонахождения и мониторинга передвижений объектов, снабженных специальными радиочастотными метками. Построенная из таких узлов сенсорная сеть образует беспроводную инфраструктуру RTLS.

Типовой узел может быть представлен тремя типами устройств:

· сетевой координатор (FFD -- Fully Function Device);

· осуществляет глобальную координацию, организацию и установку параметров сети;

· наиболее сложный из трех типов устройств, требует наибольший объём памяти и источник питания;

· устройство с полным набором функций (FFD -- Fully Function Device);

· поддержка 802.15.4;

· дополнительная память и энергопотребление позволяет выполнять роль координатора сети;

· поддержка всех типов топологий («точка-точка», «звезда», «дерево», «ячеистая сеть»);

· способность выполнять роль координатора сети;

· способность обращаться к другим устройствам в сети;

· устройство с ограниченным набором функций (RFD -- Reduced Function Device);

· поддерживает ограниченный набор функций 802.15.4;

· поддержка топологий «точка-точка», «звезда»;

· не выполняет функции координатора;

· обращается к координатору сети и маршрутизатору;

1.3 Платформы

Из-за отсутствия четкой стандартизации в сенсорных сетях, существует несколько различных платформ. Все платформы отвечают основным базовым требованиям к сенсорным сетям: малая потребляемая мощность, длительное время работы, маломощные приемо-передатчики и наличие сенсоров. К основным платформам можно отнести MicaZ, TelosB, Intel Mote 2.

Рисунок 1 Типичный узел MicaZ

MicaZ (рисунок 1):

· микропроцессор: Atmel ATmega128L;

· 7.3728 Мгц частота;

· 128 Кб флеш-памяти для программ;

· 4 Кб SRAM для данных;

· 2 UART's;

· SPI шина;

· I2С шина;

· радио: ChipCon CC2420;

· внешняя флеш-память: 512 Кб;

· 51-pin дополнительный коннектор;

· восемь 10-битовых аналоговых I/O;

· 21 цифровых I/O;

· три программируемых LEDs;

· JTAG порт;

· питание от двух батарей AA.

TelosB (рисунок 2):

· микропроцессор: MSP430 F1611;

· 8 Мгц частота;

· 48 Кб флеш-памяти для программ;

· 10 Кб RAM для данных;

· UART;

· SPI шина;

· встроенный 12-битовый ADC/DAC;

· DMA контроллер

· радио: ChipCon CC2420;

· внешняя флеш-память: 1024 Кб;

· 16-pin дополнительный коннектор;

· три программируемых LEDs;

· JTAG порт;

· опционально: Сенсоры освещенности, влажности, температуры.;

· питание от двух батарей AA.

Intel Mote 2 (рисунок 3):

· 320/416/520 МГц PXA271 XScale микропроцессор;

· 32 Мбайта Флеш-памяти;

· 32 Мбайта ОЗУ;

· mini-USB интерфейс;

· I-Mote2 коннектор для внешних устройств(31+21 pin);

· radio: ChipCon CC2420;

· светодиодные индикаторы;

· питание от трех батарей AAA.

Рисунок 2 Типичная схема узла TelosB

Рисунок 3 Плата Intel Mote 2

Основным стандартом передачи данных в сенсорных сетях является IEE802.15.4, которые специально был разработан для беспроводных сетей с маломощными приемо-передатчиками.

Никаких стандартов в области программного обеспечения в сенсорных сетях нет. Существует несколько сотен различных протоколов обработки и передачи данных, а также систем управления узлами. Наиболее распространенной операционной системой является система с открытым кодом - TinyOs. Многие разработчики часто пишут свою систему управления, часто на языке Java. Программа управления сенсорного узла под управлением операционной системы TinyOs пишется на языке nesC.

1.4 Алгоритмы канального уровня

Любая среда передачи (радио эфир, Ethernet и т.д.) ограниченна в виду того, что одновременно ей может воспользоваться только один или ограниченное число пользователей.

Протоколы канального уровня (MAC - Medium Access Control) занимаются управлением доступа к единой среде передачи данных

Классификация MAC протоколов[3,7]:

· Протоколы на основе конкуренции

· Узлы конкурируют за доступ к среде передачи

· Примеры: ALOHA (Pure and Slotted), CSMA

· Протоколы по расписанию

· Узлы передают в различных подканалах

· Примеры: FDMA, TDMA, CDMA

Свойства MAC протоколов:

· Избежание коллизий - основная задача MAC протоколов;

· Энергетическая эффективность - важное свойство в сенсорных сетях. MAC контролирует трансивер;

· Масштабируемость и адаптивность - MAC протоколы должны уметь адаптироваться;

· Эффективность использования канала - yе так важно в сенсорных сетях.

· Задержка - важность зависит от конкретного приложения;

· Пропускная способность - зависит от приложений. Goodput;

· Справедливость - в сенсорных сетях может быть неоднородное распределение трафика.

Наиболее важными факторами в сенсорных сетях являются энергетическая эффективность, избежание коллизий и адаптивность.

Энергетическая эффективность один из самых главным факторов в сенсорных сетях. Основные источники потерь энергии:

· Коллизии - атрибут «конкурентных» протоколов;

· Пассивное прослушивание канала - для маломощных трансиверов, затраты энергии на прием сообщения могут быть больше чем на его передачу;

· Overhearing - может быть доминирующим фактором при большой нагрузки и плотности узлов;

· Control Packet Overhead - уменьшают эффективную goodput.

· Рассмотрим наиболее популярные.

S-MAC: Co-ordinated Adaptive Sleeping. Комбинирование основных достоинств протоколов «по расписанию» (TDMA) и «конкурентных» протоколов (CSMA). Синхронизированное расписание. Расписание подобрано таким образом, что когда узлы хотят передать информацию, они просыпаются синхронно. Несинхронизированная передача. Когда узел проснулся и хочет передать информацию, он делает это с помощью алгоритма CSMA/CA.

Основной компромисс: жертвуя задержками/справедливостью улучшаем энергетическую эффективность. S-MAC пытается уменьшить затраты энергии за счет:

· Пассивный прием - периодическое засыпание.

· Коллизии - использование RTS/CTS

· Overhearing - выключение радио, когда передача не предназначается для этого узла.

· Служебные пакеты - передача сообщений

Достоинства:

· Значительно более эффективный чем обычный CSMA/CA;

· Планирует время сна и время активности для обеспечения энергетически эффективной передачи при удоволетворительных задержках.

Недостатки:

· Алгоритмически сложнее;

· Существенные затраты на организацию (расписание);

· Комбинирует обнаружение несущей, RTS/CTS и засыпание по расписанию в один MAC протокол, что может помешать при оптимизации под конкретные приложения.

B-MAC: Versatile Low-power medium access for sensor networks.

Разделение канального уровня и контроля доступа к среде, дает лучшую оптимизацию под конкретные приложения. Сон без расписания (Unscheduled sleep). Уменьшает количество служебной информации. Но передатчику необходимо больше усилий, чтобы пробудить приемник от сна. Пробуждение без расписания (Unscheduled wakeup) Временные интервалы между просыпаниями очень короткие. Может быть использован CSMA/CA или другие app-specific алгоритмы.

2. Алгоритмы маршрутизации в беспроводных сенсорных сетях

В главе рассматриваются общие требования к алгоритмам маршрутизации, выполняется обзор и сравнение таких алгоритмов.

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

2.1 Требования к алгоритмам маршрутизации в БСС

В связи с необходимостью сокращения использования вычислительных ресурсов (радио, батарея, датчики), протоколы маршрутизации в беспроводных сенсорных сетях, должны удовлетворять следующим требованиям[12]:

1. Автономность. Удаление определенного узла сети не должно повлиять на ее работу. Так как в сети не должно быть центрального узла, любой может выполнять функции маршрутизации удаленного.

2. Энергоэффективность. Протоколы маршрутизации должны максимально эффективно использовать питание.

3. Масштабируемость. Беспроводные сенсорные сети состоят из сотен узлов, поэтому протоколы маршрутизации должны работать с этим количеством узлов

4. Устойчивость. Датчики могут внезапно прекратить работу из-за внешних причин или расхода заряда аккумулятора. Протоколы маршрутизации должны справиться с этой возможности так, когда ток в узлах пропадает, альтернативный маршрут должен быть использован.

5. Гетерогенность устройств. Хотя в большинстве случаев применения беспроводных сенсорных сетей полагаются на однородность узлов, введение различных видов датчиков может дать значительное преимущество.

6. Мобильность. В многих случаях узлы могут перемещаться в процессе функционирования. Протоколы маршрутизации должны учитывать это.

Особенности и ограничения беспроводных сенсорных сетей порождают особые требования к протоколам маршрутизации. Обычно выделяют следующие технические характеристики:

1. Основанность на атрибутах. В таких алгоритмах, узел отправляет запросы в определенные области сети и ждет ответа от датчиков, расположенные в этой области. Выбор атрибутов зависит от приложения. Важной особенностью этой схемы является то, что содержание сообщения с данными анализируется на каждом этапе маршрутизации.

2. Энергоэффективность. В таких алгоритмах выбираются те маршруты, которые, как ожидается, максимально способствуют сохранению энергии в сети. Для этого маршрут составляется из узлов с более высокими энергетическими ресурсами.

3. Агрегация данных. Относительно близко расположенные узлы могут давать схожие данные, которые могут быть объединены с некоторыми допустимыми потерями точности.

Сенсорные приложения значительно зависят от коммуникации между узлами, так как это необходимо для выполнения определенных процедур или алгоритмов. Фактически, существует три основных вида алгоритмов маршрутизации беспроводных сенсорных сетей:

· Централизованные алгоритмы: Они выполняются на узле, который обладает знанием обо всей сети. Эти алгоритмы довольно дороги в использовании из-за высокой стоимости передачи данных, для получения состояние всей сети.

· Распределенные алгоритмы: коммуникация осуществляется передачей сообщений.

· Местные алгоритмы: узлы используют данные, полученные из ближней области. С использованием этой информации, алгоритм может выполняться на одном узле.

Используемые алгоритмы являются важным фактором, для принятия во внимание при выборе алгоритма маршрутизации. Если используются местные алгоритмы, то важна высокая коммуникационная связность близкорасположенных узлов. При централизованных алгоритмах объединение сообщений является большим плюсом. Распределенные алгоритмы должны обеспечивать надежную связь между любыми двумя узлами сети. При выборе местных алгоритмов следует учитывать, что использование дополнительных средств определения положения (например, GPS) может повысить цену таклй сети значительно.

Классификация по способу расчёта путей.

· Proactive protocols - Все пути рассчитываются заранее, до того как они будут нужны;

· Reactive protocols - Пути рассчитываются по требованию;

· Hybrid protocols - Комбинация двух подходов.

2.2 Обзор алгоритмов маршрутизации в БСС

Алгоритм 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: подобен предыдущему но с использованием информации об энергии (energy heuristic).

· SPIN-RL: разработан для нестабильных каналов (lossy channels).

Протоколы семейства SPIN хорошо подходят для приложений, где узлы мобильны, так как им требуется только локальная информация о соседях.

Недостатком SPIN протоколов является то, что они не гарантируют доставку данных.

Алгоритм Directed Diffusion.

Сенсорная сеть рассматривается как виртуальная база данных. Реализована обработка запросов от БС. Запрос распространяется по всей сети (флудинг) либо передается выбранной группе узлов. В ответ узлы, имеющие запрашиваемые данные, посылают их обратно на БС. Промежуточные узлы могут объединять данные.

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) на данные всем своим соседям.

Каждый узел хранит interest cache. Каждая запись соответствует индивидуальному запросу. Не содержит информации о БС. Объединение (aggregation) совпадающих запросов.

Каждая запись в кеше имеет несколько полей. Отметка о времени приема последнего совпадающего запроса. Несколько градиентов: скорость данных, продолжительность, направление.

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

Алгоритм Rumor Routing

Вариант 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):

· организация кластеров;

· передача данных cluster head'у и на базовую станцию.



Рисунок 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: Adaptive Threshold sensitive Energy Efficient Network.

Расширение TEEN для поддержки и периодического мониторинга так и для реакции на критические события. В отличии от TEEN узел должен собрать и передать данные, если они не были посланы за определенный период времени (count time), который устанавливается 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

Протоколы маршрутизации со многими маршрутами (Multipath routing)

· Повышение надежности передачи информации, за счет существования нескольких маршрутов.

· Увеличивает энергетические затраты.

· Увеличивает количество трафика в сети.

Поэтому рассматривать не будем.

2.3 Сравнение алгоритмов маршрутизации в БСС

Сравним различные алгоритмы маршрутизации в беспроводных сенсорных сетях (таблица 1).

Таблица 1 Сравнение протоколов маршрутизации

протокол	Основан на атрибутах	Энергоээфективен	Местного типа	Multipath	QoS	Иерархический
SPIN	да
Directed Diffusion	да
Rumor	да
COUGAR	да
ACQUIRE	да
GAF		да	да
LEACH		да				да
PEGASIS		да			да	да
TEEN		да				да
DirQ						да
SHRP		да		Да	Да	да
SAR				Да	Да
Maximum Lifetime		Да		Да
Energy Aware		Да		Да
M-MPR		Да	Да	Да

Основными алгоритмами маршрутизации, оптимизированными для повышения энергоэффективности беспроводных сенсорных сетей являются: GAF, LEACH, PEGASIS, TEEN, SHRP, M-MPR.

3. Имитационное моделирование беспроводных сенсорных сетей

Стоит отметить, что из-за дороговизны оборудования и сложности настройки сенсорных сетей, широкое распространение получили различные системы имитационного моделирования БСС.

В настоящее время, БСС являются актуальной темой исследований. Многие аспекты работы и построения таких сетей не стандартизированы. Создание стенда для тестирования БСС является очень дорогостоящим. Запуск реальных экспериментов на стенде также является еще и сложным. Кроме того, стабильность в значительной степени непредсказуема, поскольку многие факторы влияют на результаты эксперимента. Трудно изолировать один аспект исследования от других. Кроме того, запуск реальных экспериментов всегда отнимает много времени. Поэтому в области БСС моделирование имеет большое значение для развития этой сферы. Протоколы, схемы, даже новые идеи могут быть оценены в очень больших масштабах. Системы имитационного моделирования БСС позволяют пользователям изолировать различные факторы параметрами настройки.

Следовательно, имитационное моделирование имеет важное значение для изучения БСС, будучи распространенным способом для тестирования новых приложений и протоколов в данной области. Это привело к бурному развитию систем моделирования БСС в последние годы[6].

Однако получение точных выводов из результатов моделирования не является тривиальной задачей. Есть два ключевых аспекта в моделировании БСС: правильность имитационной модели и пригодность конкретных инструментов для реализации данной модели. Фундаментальной проблемой является выбор между точностью модели и производительностью с масштабируемостью.

3.1 Особенности моделирования БСС

Моделирование начинается с описания реальной системы. Такое описание представляет собой имитационную модель, построенную на основе понимания величин, атрибутов, событий, каналов и т. д. Поэтому, разработчик модели описывает эти структуры моделирования в терминах сущностей и их отношений и реализует поведение этих субъектов и реакцию на события. Системы моделирования БСС четко отделяют реализацию процесса моделирования от описания модели и экземпляров исследуемой системы[6,8]:

· ядро процесса моделирования и основных объектов модели поставляются в виде набора программных библиотек на языке программирования высокого уровня, как правило, Java или C ++;

· некоторые виды скриптовых языков программирования (TCL, например) или языки разметки (XML, например), как правило, используются для описания модели, то есть установления (объявления) отношений между субъектами. Эти средства позволяют единообразный и эффективный подход к описанию модели и ее конфигурации;

· кроме того, некоторые библиотеки часто включают поддержки графического представления или сбора статистических данных и анализа.

Таким образом, система моделирования обычно состоит из базовой библиотеки для моделирования, библиотеки вспомогательных средств, и системы описания и конфигурации моделей. Сама форма развертывания пакета зависит от реализации. Некоторые пакеты предоставляют средства, которые переводят описания моделей в объекты языка реализации моделирования. Другие обеспечивают визуальный интерфейс.

Важнейшими свойствами пакетом моделирования БСС являются[6]:

· повторное использование и доступность;

· производительность и масштабируемость;

· поддержка скриптовых языков и других способов описания моделей;

· средства визуализации и отладки.

Повторное использование и доступность. Моделирование используется для тестирования новых методов в различных условиях реальной среды. Исследователи, как правило, заинтересованы в сравнении производительности новой техники от существующих предложений. Таким образом, два ключевых аспекта: включает ли инструмент моделирования реализацию разных общих моделей, насколько легко изменить или интегрировать новую модель с уже существующими.

Первый вопрос, в основном, зависит от того, как давно система существует, и как много люди используют ее[8]. Известные системы моделирования имеют много доступных моделей, и очень вероятно, что новые успешные модели будут добавлены в следующих выпусках. Второй аспект тесно связан с конструкцией пакета моделирования. Аккуратный, с чистой структурой интерфейсов и высокой модульности пакет позволяет пользователю легко добавлять или изменять функциональность. Готовые к использованию модели позволяют пользователям быстро создавать реалистичные сценарии моделирования и сосредоточиться на моделировании более конкретные детали БСС.

Производительность и масштабируемость. Производительность и масштабируемост являются серьезной проблемой систем моделирования БСС. Обычно ограничения накладывает эффективность языка программирования и аппаратные ресурсы компьютера.

Кроме того, тип моделирования подразумевает некоторые ограничения: Режим эмуляции подразумевает работу в реальном времени, поэтому оно не может быть сколь угодно долгим.

Такие вещи как взаимодействие с окружающей средой, распространение радиоволн, подвижность узлов увеличивают потребность в ресурсах для системы моделирования. Моделирование несколько сотен тысяч узлов остается сложной проблемой.[8]

Поддержка скриптовых языков и других способов описания моделей. Конфигурация БСС как минимум требует ответа на вопросы: сколько узлов есть, где каждый узел помещается, перемещаются ли они, как энергия используется, какова физическая сред, как генерируются события и т. д. Огромное количество переменных, участвующих в определении эксперимента БСС требует использования специальных языков описания с высоким уровнем семантики. Кроме того, вполне вероятно, что большое количество выходных данных образуются также через множество реплик экспериментов. Поэтому важен подходящий выходной язык, что позволяет получить результаты экспериментов точными и ясными.

Средства визуализации и отладки. Графическая поддержка для моделирования интересно в трех аспектах. В целях отладки. Практичный способ быстро обнаружить плохое поведение является визуальное наблюдение и слежение за выполнением моделирования. В качестве инструмента визуального моделирования. Эта особенность обычно облегчает и ускоряет разработку небольших экспериментов или состав основных модулей. Однако при больших масштабах моделирования, это не очень практично. Наконец, как результат моделирования, что позволяет быстро визуализировать результаты без дополнительной обработки данных.

3.2 Обзор систем моделирования БСС

В этом разделе показаны шесть основных инструментов моделирования, используемых в БСС: NS-2, TOSSIM, Emstar, Castalia, J-Sim, ATEMU, и анализируются преимущества и недостатки каждого инструмента моделирования.

Система NS-2

NS-2 разработана в 1989 году, используется в качестве симулятора реальной сети. NS-2 является дискретно-событийным симулятором, построен в объектно-ориентированном стиле. Разработан на языке C++. Работает на операционной системе Linux. Может использоваться как для проводных, так и для беспроводных сетей. Это система с открытым исходным кодом.

Достоинства и недостатки.

К достоинствам, во-первых, как неспецифический для БСС симулятор, NS-2 может поддерживать значительное спектр протоколов во всех слоях. Например, специальные и конкретные протоколы БСС предоставляются NS-2. Во-вторых, модель открытого исходного кода экономит затраты на моделирование и электронные документы позволяют пользователям легко изменять и улучшать систему.

Тем не менее, этот симулятор имеет некоторые ограничения. Во-первых, люди, которые хотят использовать этот симулятор должны быть знакомы с написанием программ на скриптовых языкахю Во-вторых, иногда использование NS-2 является более сложным и трудоемким, чем других систем моделирования. В-третьих, NS-2 обеспечивает плохую графическую поддержку, без графического интерфейса пользователя (GUI)

Система TOSSIM

TOSSIM является эмулятором, специально предназначенным для БСС, работающих на TinyOS, который распространяется с открытым исходным кодом. Разработан в 2003 году. Написан на языке Python и C++.Работает в операционной системе Linux. TOSSIM также распространяется в исходном коде.

Достоинства и недостатки.

К достоинствам относится, скорость эмуляции. Кроме того, TOSSIM имеет графический интерфейс, TinyViz, что очень удобно для того, чтобы взаимодействовать с электронными устройствами, поскольку она обеспечивает изображения вместо текста команд.

Кроме того, TOSSIM является очень простым, но мощным эмулятором для БСС. Каждый узел может быть оценен в идеальных условиях передачи, и с помощью этого эмулятора можно исследовать скрытые проблемы. Может поддерживать тысячи узлов.

Тем не менее, этот эмулятор имеет некоторые ограничения. Во-первых, TOSSIM предназначен для моделирования поведения и применения TinyOS, и он не предназначен для имитации показателей других новых протоколов. Поэтому TOSSIM не может правильно моделировать вопросы энергопотребления в БСС; люди могут использовать PowerTOSSIM, другой симулятор TinyOS. Во-вторых, каждый узел должен работать на Nesc коде, языке программирования, который управляется событиями на основе компонентов и реализован на TinyOS. В-третьих, TOSSIM разработан специально для моделирования только узлов.

Система Emstar

Emstar является эмулятором, специально предназначенным для БСС, построен на языке C.Работает на операционной системе Linux. Этот эмулятор поддерживает развитые возможности по работе с аппаратными датчиками.

Достоинства и недостатки

Достоинства, во-первых, модульная модель программирования в Emstar позволяет пользователям запускать каждый модуль отдельно без ущерба для повторного использования программного обеспечения. Emstar имеет графический интерфейс, который может быть очень полезным для пользователей для управления электронными устройствами.

Тем не менее, этот эмулятор содержит некоторые недостатки. Например, он не может поддерживать большое количество узлов и датчиков и ограниченную масштабируемость в итоге. Кроме того, Emstar может работать только в режиме реального времени.

Система Castalia

Castalia является событийно-дискретным симулятором. Написан на C++. Castalia распространяется по некоммерческой лицензии, для использоваться в учебных заведениях или некоммерческих исследовательских организациях, а также под коммерческой лицензией. Этот симулятор поддерживает подделживает написание модулей пользователем. Работает в операционной системе Linux, Unix-подобных операционных системах. Castalia является популярной системой моделирования БСС. Большинство исходного кода може быть доступно в исходном виде.

Достоинства и недостатки

Достоинства, во-первых, Castalia обеспечивает мощные средства трассировки и отладки. Поддерживаются широкие возможности работы с радиоканалом, поддерживает многие MAC протоколы. Кроме того, Castalia может имитировать проблемы энергопотребления в БСС.

Тем не менее, существуют некоторые ограничения. Например, количество доступных протоколов не является достаточно большим.

Система J-Sim

J-Sim является дискретно-событийным симулятором. Написан на Java. Есть, графический интерфейс. Распространяется в исходном коде. Обычно используется в физиологии и области биомедицины, но также может быть использован для моделирования БСС. Кроме того, J-Sim может имитировать процессы в реальном времени.

Достоинства и недостатки

Достоинства, во-первых, в модели J-Sim есть возможность повторного использования и взаимозаменяемости компонентов. Во-вторых, J-Sim содержит большое количество протоколов. В-третьих, J-Sim предоставляет графический интерфейс, который может помочь пользователям отслеживать и отлаживать программы. В-четвертых, по сравнению с NS-2, J-Sim может имитировать большое число узлов датчиков, около 500 и J-Sim может сэкономить много оперативной памяти.

Тем не менее, этот симулятор имеет некоторые ограничения. Время выполнения гораздо больше, чем у NS-2. Поскольку J-Sim изначально не предназначены для моделирования БСС.

Система ATEMU

ATEMU построен на С; заточен под платформу MICA. ATEMU предоставляет графический интерфейс. Работает в операционных системах Solaris и Linux. Распространяется в исходном коде.

Достоинства и недостатки

Достоинства, во-первых, ATEMU может имитировать несколько датчиков на узле. Во-вторых, ATEMU имеет большую библиотеку готовых устройств. В-третьих, ATEMU может обеспечить очень высокий уровень детализации эмуляции БСС. В-четвертых, графический интерфейс может помочь пользователям в отладке и мониторинге реализации модели.

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

Таблица 2 Сравнение шести основных систем моделирования БСС

Система	Дискретно-событийная система иначе основанная на трассировке	Графический интерфейс пользователя	Распространяется в исходном коде	Специально предназначен для БСС, иначе общий	Особенности
NS-2	Да	Нет	Да	Нет	1.не более 100 узлов, 2 не может имитировать проблемы пропускной способности или потребление электроэнергии в БСС
TOSSIM	Да	Да	Да	Да	1.около тысячи узлов 2. Только однородные приложения
Emstar	Нет	Да	Да	Да	1.не поддерживает большое количество узлов 2. Работает только в режиме реального времени и только узлы MICA2
Castalia	Да	Да	Некоммерческая и коммерческая лицензия	Да	1.поддержка протоколов MAC 2.симуляция потребляемой мощности и канала 3.расширеная эмуляция радиоканала
J-Sim	Да	Да	Да	Нет	1.может имитировать большое количество узлов датчиков, около 500 2.может имитировать радиоканалов и потребляемой мощности 3.время его работы гораздо больше,
ATEMU	Да	Да	Да	Да	1.может эмулировать различные узлы в однородных сетях или гетерогенных сетях 2.симуляция потребляемой мощности и радио каналов 3.время моделирования гораздо дольше

Мы рассмотрели шесть основных систем имитационного моделирования БСС: NS-2, TOSSIM, Emstar, Castalia, J-Sim, ATEMU. И сравнивает их достоинства и недостатки, результаты приведены в таблице 2.Выбор системы стоит проводить в зависимости от целей исследования, выбирая более эффективную для данного случая.

3.3 Система Castalia

В связи с обширными возможностями моделирования (в том числе радиоканала) в дальнейшем будем использовать систему Castalia.

Castalia является системой моделирования для беспроводных сенсорных сетей (БСС) и вообще сетей маломощных встроенных устройств. Она основана на платформе OMNeT++[2,3] и может быть использована исследователями и разработчиками, которые хотят испробовать свои алгоритмы и / или протоколы в реалистичной среде беспроводного канала с расширенной радио моделью, с реалистичным поведением узла. Castalia также может быть использован для оценки различных характеристик платформы для конкретных приложений, так как она очень гибка в настройке и может имитировать широкий диапазон платформ. Основными чертами Castalia являются[3]:

_ Усовершенствованная модель канала на основе эмпирических данных измерений:

· модель системы учитывает потери в канале передачи данных, а не просто соединений между узлами;

· комплексная модель для изменения потерь в канале;

· полностью поддерживает подвижность узлов;

· помехи учитываются уже на уровне принимаемого сигнала, а не в виде отдельной функции.

_ Усовершенствованная модель радио основан на реальных маломощных радио устройствах связи:

· вероятность получения зависит от SINR, размера пакета, типа модуляции. Модуляции PSK, FSK поддерживаются, пользовательские модуляции могут быть определены путем задания SNR-BER кривой;

· несколько уровней мощности передачи с индивидуальными вариациями могут задаваться;

· состояния с различным энергопотреблением и задержками переключения между ними поддерживаются;

· реалистичное моделирование RSSI несущей.

_ Расширенное моделирование измерительных устройств:

· очень гибкая физическая модель процесса измерения;

· поддержка шумов, смещений и потребления энергии для измерительного устройства.

_ MAC протоколы доступны.

_ Предназначена для адаптации и расширения.

Что касается последнего пункта, Castalia была разработана с самого начала, так что пользователи могут легко реализовать / импортировать свои алгоритмы и протоколы в то время как Castalia берет на себя особенности моделирования. Модульность, надежность и скорость Castalia частично заслуга OMNeT++, которая легла в основу Castalia.