Анализ работоспособности беспроводной сети

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Краснодар 2013

Содержание

Введение

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

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

.2 Технология

.3 Платформы

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

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

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

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

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

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

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

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

.3 Система Castalia.

. Анализ работоспособности беспроводных сенсорных сетей

.1 Модель надежности беспроводной сенсорной сети

.1.1 Модель надежности передачи пакета данных между двумя узлами

.1.2 Модель надежности узла

.1.3 Модель надежности коммуникации между узлами

.2 Исследование надежности передачи пакета данных между двумя узлами в системе Castalia.

.2.1 Влияние помех на надежность коммуникационной среды между двумя узлами в системе Castalia

.2.2 Влияния мощности радио-модуля на надежность коммуникационной среды между двумя узлами в системе Castalia

.3 Исследование надежности сбора информации сетью в системе Castalia

.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

(рисунок 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.(рисунок 2):

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

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

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

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

·              UART;

·              SPI шина;

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

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

·              радио: ChipCon CC2420;

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

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

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

·              JTAG порт;

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

·              питание от двух батарей AA.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.

·        Рассмотрим наиболее популярные.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]:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Используемые алгоритмы являются важным фактором, для принятия во внимание при выборе алгоритма маршрутизации. Если используются местные алгоритмы, то важна высокая коммуникационная связность близкорасположенных узлов. При централизованных алгоритмах объединение сообщений является большим плюсом. Распределенные алгоритмы должны обеспечивать надежную связь между любыми двумя узлами сети. При выборе местных алгоритмов следует учитывать, что использование дополнительных средств определения положения (например, 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.

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

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

Основные элементы Directed Diffusion

·        Naming. Данные обозначаются с помощью атрибутов.

·        Interests. Узел запрашивает данные посылая запрос (interest) на определенные данные.

·        Gradients. Градиенты (gradients) установлены в пределах сети, чтобы доставлять данные совпадающие с запросом.

·        Reinforcement БС «устанавливает» (reinforce) определенные маршруты, чтобы доставлять данные с большей скоростью (данные о быстро меняющихся событиях).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.: Threshold sensitive Energy Efficient Network., event-driven protocol for time-critical applications.

·        Узел постоянно мониторирует среду, но передает информацию только если значение меняется значительно.

·        Нет переодической передачи.

·        Критические данные передаются незамедлительно. посылает своим узлам «жесткий» (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.-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разработана в 1989 году, используется в качестве симулятора реальной сети. NS-2 является дискретно-событийным симулятором, построен в объектно-ориентированном стиле. Разработан на языке C++. Работает на операционной системе Linux. Может использоваться как для проводных, так и для беспроводных сетей. Это система с открытым исходным кодом.

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

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

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

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

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

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

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

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

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

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

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

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

Система Castalia

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

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

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

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

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

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

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

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

Система 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.

Чем Castalia не является это ориентированной на конкретную платформу. Castalia обеспечивает общий надежный и реалистичный способ проверки алгоритма прежде чем перейти к реализации на конкретной платформе.использует OMNeT++ в качестве своей базы поэтому предполагается, что у вас есть четкое понимание основных понятий OMNeT хотя это и не требуется, особенно если вы хотите использовать Castalia без создания собственных протоколов / приложенийоснован на понятиях модулей и сообщений. Простой модуль является основной единицей исполнения. Он принимает сообщения от других модулей или непосредственно, и в соответствии с сообщением, он выполняет часть кода. Этот код может хранить состояние, которое изменяется при приеме сообщений и может отправить новые сообщения. Есть также составные модули. Составной модуль просто способ построения простых и / или других композитных модулей

Рисунок 9 Структура модулей в Castalia

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

Модуль узла является составным. На рисунке 10 показана внутренняя структура узла. Сплошные стрелки означают передачу сообщений и пунктирные стрелки означают просто вызываемые функции. Например, большинство из модулей вызывают функции менеджера ресурсов, чтобы сигнализировать, что энергия израсходована. Castalia предлагает поддержку для создания пользовательских протоколов и приложений, определяя соответствующие абстрактные классы[3]. Все существующие модули хорошо настраиваемы по многим параметрам.

Рисунок 10 Структура модуля узла

Описание модулей осуществляется с использованием языка OMNeT++ NED. С помощью этого языка мы можем легко определить модули, т. е. определить имя модуля, параметры модуля и модуля интерфейса и возможную структуру подмодуля (если это композитный модуль). Сам код модуля пишется на языке C++.

4.     
Анализ работоспособности беспроводных сенсорных сетей

В данной главе описываются модели надежности для беспроводной сенсорной сети. Проводится исследование в системе Castalia.

4.1 Модель надежности беспроводной сенсорной сети

Наибольшее распространение в последнее время получили беспроводные сенсорные сети, параметры которых регламентируются стандартом IEEE 802.15.4 [11]. Далее будем вести речь именно о таких сетях.

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

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

Подход к оцениванию надежности основан на представлении функционирования беспроводной сенсорной сети как марковского процесса[16,23], и предполагает использование математической модели надежности передачи данных между двумя узлами такой сети, которая, в свою очередь, представляет собой композицию моделей надежности узлов, коммуникаций между ними и механизма их доступа к среде.

4.1.1 Модель надежности передачи пакета данных между двумя узлами

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

Здесь и далее предполагается, что отправка пакетов  -ым узлом в процессе работы сети образует простейший поток событий с интенсивностью , а прием пакетов этим же узлом - простейший поток с интенсивностью , где  - множество узлов, которые могут передать пакет в адрес -го узла;  - множество узлов, которым может быть передан пакет от -го узла (см. Рис. 11)

Рисунок 11 Потоки событий на i -ом узле сети

Величиной  на Рис. 11 обозначена интенсивность потока событий, соответствующих безуспешным попыткам передачи пакета -ым узлом. Эту величину можно определить следующим образом[21]:

где  - математическое ожидание количества попыток передачи пакета от  -го узла  -му, необходимое для успешного его приема:

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

Таким образом, можно записать:

Алгоритм расчета вероятности  основан на одном из возможных принципов работы механизма маршрутизации в беспроводных сенсорных сетях [16]. Пусть на каждом  -ом узле имеется ограниченная таблица маршрутизации (определяющая множество  соседних с  -ым узлов, которым им может быть передан пакет данных). Записи в этой таблице ранжированы по предпочтительности использования каждого направления при передаче пакета. Для каждого нового пакета, поступающего на  -ый узел и нуждающегося в дальнейшей ретрансляции, делается максимум  попыток его передачи  -му узлу из множества , указанному первым в таблице маршрутизации  -го. Если все попытки оказались неудачными, то из множества  выбирается  узел, соответствующий следующей записи в таблице маршрутизации, и  -ый узел пытается передать пакет ему, и т.д. Пакет, который до поступления на  -ый узел следующего пакета не удалось передать ни одному из узлов, указанных в таблице, удаляется из системы (теряется).

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

Таким образом, выражение для расчета  может быть записано следующим образом:

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

 - максимальное количество неудачных попыток передачи пакета одному узлу;  - вероятность передачи пакета с  -ой попытки:

где  - вероятность передачи пакета с первой попытки:

где  - вероятность работоспособности (надежность)  -го узла беспроводной сенсорной сети;  - надежность коммуникации между узлами, определяемая параметрами радиоканала;  - вероятность коллизии, обусловленной эффектом «скрытого узла»[29].

 - вероятность того, что узел сможет осуществить  попыток передачи пакета за время . Эта вероятность определяется механизмом конкурентного доступа к среде, используемым в беспроводных сенсорных сетях и регламентированным стандартом IEEE 802.15.4 [11].

Очевидно, что успешная передача пакета может быть осуществлена только при выполнении условия[23]:

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

 - время, затрачиваемое узлом непосредственно на процесс передачи (приема) пакета фиксированной длинны  байт, , где  - скорость передачи данных, байт/сек;

 - период времени, в течение которого возможна передача очередного пакета  -ым узлом в адрес  -го. Величина  различна для каждого  -го узла из множества  (таблицы маршрутизации  -го узла) и определяется на основе интенсивности потоков приема и передачи пакетов на  -ом узле, длины пакетов, допустимого количества попыток передачи и среднего времени ожидания узлом возможности выхода в эфир:

где  - среднее значение времени, которое может быть затрачено  -ым узлом на передачу одного из пакетов ретранслируемого им потока:

где  - интенсивность передачи пакетов  -ым узлом в адрес узлов из множества ; - среднее значение времени ожидания узлом начала передачи пакета.

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

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

Далее будет рассмотрено описание математических моделей, количественно определяющих вероятности , , ,.

 

.1.2 Модель надежности узла

Определим регламент обслуживания сети как регулярный с периодом  контроль и замену неисправных узлов. Ограничение на надежность узлов беспроводной сенсорной сети обусловлено разрядом их батареи в процессе работы сети, а также возможностью случайного выхода их из строя, вызванного отказом аппаратного или программного обеспечения, внешними воздействиями и т.д.[20,21,23]

Запишем выражение для определения вероятности работоспособности  -го узла на заданный момент времени  в виде[16]:

где  - вероятность случайных отказов  -го узла, закон распределения которых можно в первом приближении принять экспоненциальным [21]:

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

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

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

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

Будем полагать, что по истечении времени . с момента замены батареи узел теряет работоспособность с вероятностью 1. Замена разряженных батарей узлов осуществляется с периодичностью  (одновременно для всех узлов)[16]. Таким образом, для величины можно записать:

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

 

.1.3 Модель надежности коммуникации между узлами

В связи с особенностями эксплуатации беспроводных сенсорных сетей имеют место потери пакетов из-за наличия шумов, вызванных как другими устройствами в конкурирующем диапазоне, так и наличием собственных эхо-сигналов. Вероятность успешной передачи сообщения длиной байт от  -го узла  -му можно определить из соотношения: , где  - вероятность безошибочного приема символа данных. Зависимость от вероятности битовой ошибки может быть получена путем интерполирования расчетных значений для диапазона частот в 2.45 ГГц[16], где используется избыточное кодирование в соответствии со стандартом IEEE 802.15.4 [11]:

где  - вероятность битовой ошибки, которая может быть определена из следующего соотношения:

где  - энергия бита трансляции, равна произведению мощности на приемной антенне  -го узла  и продолжительности трансляции бита  , что определяется скоростью передачи данных [16];

 - спектральная плотность шумов (ее положительная часть) на приемной антенне  -го узла, складывается не только из собственных тепловых шумов приемника и шумов других источников излучения (BlueTooth, Wi-Fi, GSM и др.), но еще и суммы эхо-сигналов[27];

 - гауссов интеграл ошибок:

Отношение  можно представить как: , где  - амплитуда принимаемого сигнала,  - амплитуда шума,  - ширина частотной полосы,  - скорость передачи данных. При  =5Мгц и  =250кб/с [16].

Амплитуда принимаемого сигнала  определяется из следующего соотношения: , где  - сопротивление антенны (50 Ом)[24].

Так как сигнал, с которым синхронизируется узел - это, как правило, прямой (наиболее мощный) сигнал для условия прямой видимости и квази-сферичности диаграммы направленности антенны, его мощность можно определить из известного соотношения[16]:

где ,  - мощности принимаемого и излучаемого сигнала соответственно,  -расстояние между узлами,  - длина волны ( 0,125m ≈ ),  - коэффициент усиления канала связи ( 0.8 ≈ ).

Амплитуда шума  является случайной величиной, и может быть описана распределением Рэлея [29], плотность распределения которого имеет вид:

где параметр этого распределения , зависящий от  - средней амплитуды шумового сигнала, и  - числа когерентно суммируемых сигналов на приемнике. В нулевом приближении средняя амплитуда и число когерентно суммируемых лучей зависит от размеров помещения и его загроможденности предметами, представляющими собой «зеркала» для радиосигналов. Таким образом, помещение, в котором функционирует сенсорная сеть, может быть охарактеризовано параметром , который выбирается при помощи методики, описанной в [16].

 

.2 Исследование надежности передачи пакета данных между двумя узлами в системе Castalia

Рассмотрим на практике надежность передачи пакета данных между двумя узлами, рассмотренную в 4.1.

Для простоты рассмотрения надежности передачи пакета между двумя узлами будем рассматривать беспроводную сенсорную сеть из девяти узлов (рисунок 12). Будем считать, что узлы расположены в пространстве на одной плоскости в области размера 30м. на 30м. Расположены по сетке.

Рисунок 12 Схема простой сети из девяти узлов

Для задания параметров моделирования в системе Castalia используются конфигурационные файлы[3] (обычно такой файл принято называть omnetpp.ini), располагаться такой файл должен в папке данного моделирования (у нас interNodes), которая в свою очередь должна находиться в папке Simulations системы Castalia. Полный текст приведён в приложении А.

Для задания данной пространственной конфигурации используются параметры: SN.field_x = 30, SN.field_y = 30, SN.numNodes = 9, SN.deployment = "3x3"

Время моделирования задаем в 100с. (параметр sim-time-limit = 100s), стоит отметить, что моделирование в системе Castalia происходит не в реальном времени, то есть реальное время проведения эксперимента будет не 100с.

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

Для моделирования надежности передачи пакета данных между двумя узлами разработан модуль приложения InterNodes, представленный файлами interNodes.ned, interNodes.h, interNodes.cc. Исходный код приведён в приложении А.

Каждый узел с интервалом 100мс. (в приложении заведен соответствующий таймер) отправляет сообщение на щироковещательный адрес (равномерный поток сообщений образуется), всего отправляет 100 таких сообщений.

При этом у каждого узла заведена таблица соседей, имеющая структуру, представленную на рисунке 13. Где id - идентификатор узла, timesRx - количество пакетов пришедших от него.

newRec.timesRx = 1;

Рисунок 13 Структура таблицы соседей

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

В настройках моделирования указываем приложение (параметр SN.node[*].ApplicationName = "interNodes")

Отметим, что для идеализации коммуникационной среды между узлами мы отключим параметры, отвечающие за помехи канала (параметр SN.wirelessChannel.sigma = 0).

Система Castalia позволяет в файле с параметрами моделирования задавать различные конфигурации (различаться будут значениями параметров). Каждая конфигурация задается секцией, которые разделяются именем секции в квадратных скобках. Конфигурация General (задается [General]) является обязательной.

Для запуска моделирования используется команда Castalia. На рисунке 14 представлен запуск моделирования с конфигурацией General и выводом в файл res.txt. Как видно, моделирование не заняло много времени.

Рисунок 14 Запуск моделирования в системе Castalia

Для обработки данных полученных в процессе моделирования в системе Castalia используется команда CastaliaResults. На рисунке 15 выводится общая информация о собранных в ходе моделирования данных, сохраненных в файле res.txt. Каждый модуль системы может собирать различные данные. Например, в нашем модуле Application мы собирали данные о полученных пакетах от соседей и записывали как Packets received, что и отражено здесь. Величина Dimensions характеризует сколько узлов и данные какой размерности писали.

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

Рисунок 15 Вывод общих сведений о результатах моделирования в системе Castalia

Рисунок 16 Среднее число пакетов полученных каждым узлом

Рисунок 17 Число пакетов полученных каждым узлом

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

Последовательно проводя моделирование можно заметить, что результаты его будут отличаться, что обусловлено случайным характером многих факторов. Можно повторять многократно моделирование для снижения погрешности. Система Castalia позволяет проводить повтор моделирования заданное число раз с помощь опции -n <число повторений>. При этом результаты берутся средние.

Проведя наше моделирование сто раз, на рисунке 18 видно, что в целом полученные данные практически идентичны тем, что получены без многократного повторения. Поэтому подробнее рассмотрим первые.

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

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

Рисунок 18 Количество пакетов полученных узлами при стократном повторении моделирования

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

Таким образом мы рассмотрели модель надежности передачи пакетов между двумя узлами в среде без помех.

Рисунок 19 Вероятности доставки сообщении между узлами

 

.2.1 Влияние помех на надежность коммуникационной среды между двумя узлами в системе Castalia

Рассмотрим теперь случай, когда присутствуют помехи.

Помехой называется стороннее возмущение, действующее в системе передачи и препятствующее правильному приёму сигналов[24,29].

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

Величина помех в системе Castalia задается параметром SN.wirelessChannel.sigma, а сама величина помех рассчитывается по формуле[3]:

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

Для рассмотрения влияния помех мы определили в настройках моделирования конфигурацию varySigma, при которой будет запущено моделирование (рисунок 20) с вариацией этого параметра (SN.wirelessChannel.sigma = ${Sigma=0,1,3,5})

На рисунке 21 видно, что с увеличением параметра sigma вероятность доставки пакета уменьшается, а значит и надежность, однако же резкого роста снижения надежности нет.

Рисунок 20 Моделирование с вариациями уровня помех

Рисунок 21 Количество пакетов, полученных при разном уровне помех

Для визуализации полученных данных в системе Castalia есть команда CastaliaPlot, которая позволяет строить различные визуальные представления (графики, диаграммы и т. д.) из данных, что были получены командой CastaliaResults[3].

Рисунок 22 Влияние помех на число полученных пакетов

работоспособность беспроводной сенсорный сеть

На рисунке 22 представлена диаграмма, иллюстрирующая сколько пакетов получил пятый узел от остальных. Где Sigma - параметр, отвечающий за уровень помех; node - узлы, пронумерованные от 0 до 8 и обозначенные разными цветами; число на оси ординат соответствует общему числу полученных сообщений пятым узлом, каждый цветной сегмент показывает сколько пакетов получено от соответствующего цвету узла. Видно, что при отсутствии помех было получено около семисот пакетов. С возрастанием величины помех начиная с 3 видно, что число полученных пакетов не падает значительно, то есть можем говорить, что надёжность здесь уже не зависит от уровня помех, что может быть обусловлено хорошим протоколом канального уровня.

 

.2.2 Влияния мощности радио-модуля на надежность коммуникационной среды между двумя узлами в системе Castalia

Рассмотрим влияние мощности радио-модуля при передаче сообщений.

Для рассмотрения влияния мощности радио-модуля мы определили в настройках моделирования конфигурацию varyTxPower, при которой будет запущено моделирование с вариацией этого параметра (SN.node[*].Communication.Radio.TxOutputPower = ${TXpower="0dBm","-1dBm","-3dBm","-5dBm"})

На рисунке 23 представлена диаграмма, иллюстрирующая сколько пакетов получил пятый узел от остальных. Где TXpower - параметр, отвечающий за уровень мощности радио-модуля; node - узлы, пронумерованные от 0 до 8 и обозначенные разными цветами; число на оси ординат соответствует общему числу полученных сообщений пятым узлом, каждый цветной сегмент показывает сколько пакетов получено от соответствующего цвету узла. Видно, что при уровне мощности в -5dBm было получено около семисот пакетов. С возрастанием величины мощности начиная с -3dBm видно, что число полученных пакетов возросло до восьмисот и стабильно, то есть можем говорить, что надёжность здесь уже не зависит от уровня мощности радио-модуля.

Рисунок 23 Влияние уровня мощности радио-модуля на число полученных пакетов

 

.3 Исследование надежности сбора информации сетью в системе Castalia

Для простоты рассмотрения надежности сбора информации сетью будем рассматривать беспроводную сенсорную сеть из 36 узлов (рисунок 24). Будем считать, что узлы расположены в пространстве на одной плоскости в области размера 100м. на 100м. Расположены по сетке.

Рисунок 24 Схема простой сети из 36 узлов

Для задания параметров моделирования в системе Castalia используются конфигурационные файлы[3] (обычно такой файл принято называть omnetpp.ini), располагаться такой файл должен в папке данного моделирования (у нас reliabilityFullNet), которая в свою очередь должна находиться в папке Simulations системы Castalia. Полный текст приведён в приложении Б.

Для задания данной пространственной конфигурации используются параметры: SN.field_x = 100, SN.field_y = 100, SN.numNodes = 36, SN.deployment = "6x6"

Время моделирования задаем в 600с. (параметр sim-time-limit = 600s), стоит отметить, что моделирование в системе Castalia происходит не в реальном времени, то есть реальное время проведения эксперимента будет не 600с.

Говоря о сборе данных беспроводной сенсорной сетью, мы подразумеваем, что один из узлов сети является шлюзом между БСС и внешними системами, куда попадают собранные данные. Пусть шлюзом будет четвёртый узел (параметр SN.node[3].Application.isSink = true).

Для того чтобы собирать данные нам необходима модель функционирования узла, для этого был разработан модуль приложения DataToSink, представленный файлами DataToSink.ned, DataToSink.h, DataToSink.cc. Исходный код приведён в приложении Б.

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

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

В настройках моделирования указываем приложение (параметр SN.node[*].ApplicationName = " DataToSink ")

Для того, чтобы информация от узлов шла к шлюзу был разработан модуль простой маршрутизации MultipathRingsRouting, представленный файлами MultipathRingsRouting.ned, MultipathRingsRouting.h, MultipathRingsRouting.cc. Исходный код приведён в приложении Б.

Структура пакета для маршрутизации представлена на рисунке 25. Здесь Source - адрес отправителя; Destination - адрес получателя; Level - уровень маршрутизации, с которого отправлен пакет; Data - полезная информация для уровня приложения; Type - тип пакета.

Алгоритм состоит из двух фаз, которые разделяются типом пакета.

Первая фаза. Установление уровней. Для этого шлюз шлет в канал пакет с типом MPRINGS_TOPOLOGY_SETUP_PACKET. Узел получая такой пакет, если его собственный уровень не установлен, ставит уровень на единицу больше, запоминает как свой уровень и передает пакет дальше. Аналогично остальные узлы. Таким образом вокруг шлюза формируются «кольца уровней» как показано на рисунке

Рисунок 25 Структура пакета для маршрутизации

Рисунок 26 «Круговые» уровни вокруг шлюза

Запустим моделирование (рисунок 26).

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

В настройках моделирования указываем протокол маршрутизации (параметр SN.node[*].Communication.RoutingProtocolName = "MultipathRingsRouting")

Как говорилось в 4.1, надежность БСС определяется надежностью обмена пакетами между узлами. Здесь под надежностью сбора информации сетью мы будем понимать надежность получения пакетов шлюзом и рассматриваем вероятность получения пакетов.

Используя ранее рассмотренный аппарат и запустив моделирование c конфигурацией General, получили данные, на основе которых построен график на рисунке 27. Здесь видна информация, по доставке пакетов к четвертому узлу (шлюзу). По оси абсцисс состояния доставки, а по оси ординат их вероятности. Видно, что состояния Failed превалируют, а Received составляют примерно около 0,3. На первый взгляд это может показаться плохим результатом, однако же в силу специфики собираемой информации и других факторов, таких как долгая автономная работа сети, вполне приемлемо.

Рисунок 27 Количество пакетов, полученных шлюзом

На рисунке 28 отображена информация о вероятностях доставки сообщений для всех узлов сети. По оси абсцисс номера узлов, по оси ординат вероятности, а цветами обозначены состояния пакетов. Отсюда видно, что наибольшая надежность доставки пакетов 0,5 обнаруживается для узла 27. Что может послужить предпосылкой использовать в качестве шлюза именно такие узлы.

Рисунок 28 Информация о полученных пакетах для всех узлов

 

.3.1 Влияние помех на надежность сбора информации сетью в системе Castalia

Для рассмотрения влияния помех мы определили в настройках моделирования конфигурацию varySigma, при которой будет запущено моделирование с вариацией этого параметра (SN.wirelessChannel.sigma = ${Sigma=0,1,3,5})

На рисунках 29-32 показано как меняется надежность доставки пакетов в зависимости от уровня помех. По оси абсцисс номера узлов, по оси ординат вероятности, а цветами обозначены состояния пакетов. Видна тенденция, что с возрастанием уровня помех возрастает вероятность доставки пакетов. Это может быть обусловлено хорошими алгоритмами канального уровня.

Рисунок 29 Количество пакетов при Sigma 0

Рисунок 30 Количество пакетов при Sigma 1

Рисунок 31 Количество пакетов при Sigma 3

Рисунок 32 Количество пакетов при Sigma 5

Заключение

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

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

Полученные результаты в целом соответствуют результатам других исследователей. [16].

В процессе работы были подготовлены и приняты в печать тезисы доклада «Исследование энергоэффективности алгоритмов маршрутизации в беспроводных сенсорных сетях» на объединенную научную конференцию студентов и аспирантов факультета компьютерных технологий и прикладной математики «Прикладная математика XXI века», проходившую в Краснодаре, 9-12 апреля 2013 г.

Библиографический список

1.      Castalia Installation Guide URL: http://castalia.research.nicta.com.au/pdfs/Castalia%20-%20Installation.pdf

.        Castalia official site URL: http://castalia.research.nicta.com.au/

.        Castalia User's manual URL:http://castalia.research.nicta.com.au/pdfs/Castalia%20-%20User%20Manual.pdf

.        Chandra T.D., Toueg S. Unreliable failure detectors for reliable distributed systems. // J. ACM. 1996. V. 43. P. 225-267.

.        Delporte-Gallet C., Devismes S., Fauconnier H. Stabilizing leader election in partial synchronous systems with crash failures. // J. Parallel Distrib. Comput. - 2010. - 70. - P. 45 - 58.

6.      E. Egea-López, J. Vales-Alonso, A. S. Martínez-Sala, P. Pavón-Mariño, J. García-Haro Simulation Tools for Wireless Sensor Networks // Summer Simulation Multiconference - SPECTS 2005 // - 2005. - P. 2 - 9.

7.      Ezio Biglieri Coding for Wireless Channels (Information Technology: Transmission, Processing and Storage) -2005. - P. 428.

.        Fei Yu A Survey of Wireless Sensor Network Simulation Tools URL: http://www1.cse.wustl.edu/~jain/cse567-11/ftp/sensor/index.html

.        Fischer M.J., Lynch N.A., Paterson M.S. Impossibility of distributed consensus with one faulty process. // J. ACM. 1985. V 32. P. 374-382.

.        Garay J.A., Perry K.J. A continuum of failure models for distributed computing. // Proc. 6nd Int. Workshop on Distributed Algorithms (Haifa, 1992) / S. Zaks, A. Segall (eds.). P. 153-156.

.        IEEE Standards 802.15.4. Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs). - IEEE Computer Society, 2003.

12.    Luis Javier García Villalba , Ana Lucila Sandoval Orozco, Alicia Triviño Cabrera, Cláudia Jacy Barenco Abbas Routing Protocols in Wireless Sensor Networks // Sensors // - 2009 - 9 - P. 399 - 421.

.        Pease M., Shostak R., Lamport L. Reaching agreement in the presence of faults. // J. ACM. 1984. V. 27. P. 228-234.

.        Roya N., Gub T., Das S.K. Supporting pervasive computing applications with active context fusion and semantic context delivery. // Pervasive and Mobile Computing - 2010. - 6. - P. 21 - 42.

.        Zhang M., Chan M.C., Ananda A.L. Connectivity monitoring in wireless sensor networks. // Pervasive and Mobile Computing - 2010. - 6. - P. 112 - 127.

16.    Акимов Е.В., Кузнецов М.Н. Вероятностные математические модели для оценки надежности беспроводных сенсорных сетей // Электронный журнал «Труды МАИ». Выпуск № 40// URL: http://www.mai.ru/science/trudy/

.        Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. - М.: Вильямс, 2000. - 384 с.

.        Гейер Дж. Беспроводные сети. Первый шаг. / Пер. с англ. - М.: Вильямc, 2005. - 192 с.

.        Дейтел Х., Дейтел П. Как программировать на С++. - М.: Бином-Пресс, 2008. - 1446 с.

.        Нечаев Д.Ю., Чекмарев Ю.В. Надежность информационных систем. - М.: ДМК Пресс, 2012. - 64 с.

.        Острейковский В.А. Теория надежности. - М.: Высшая школа, 2000. - 464 с.

.        Острейковский В.А. Теория надежности. Учебник для вузов. - М.: Высшая школа, 2003. - 457 с.

.        Половко А.М., Гуров С. В. Основы теории надежности. - СПб.: БХВ-Петербург 2006. - 560 с.

.        Смелянский Р. Л. Компьютерные сети. В 2 томах. Том 1. Системы передачи данных. - М.: Академия, 2011. - 304 с.

.        Страуструп Б. Язык программирования С++. - М.: Бином, 2008. - 1104 с.

.        Тель Ж. Введение в распределенные алгоритмы. Пер. с англ. В. А. Захарова. - М.: МЦНМО, 2009. - 616 с.

.        Ушаков И.А. Вероятностные модели надежности информационно-вычислительных систем. - М.: Радио и связь 1991. - 132 с.

.        Хьюз К., Хьюз Т. Параллельное и распределенное программирование на С++. Пер. с англ. - М.: Издательский дом Вильямс, 2004. - 672 с.

.        Шахнович И.А. Современные технологии беспроводной связи. - М.: Техносфера, 2006. - 288 с.

.        Шубин В.И., Красильникова О. С. Беспроводные сети передачи данных. - М.: Вузовская книга, 2012. - 104 с.

.        Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. Пер. с англ. - М.: Издательский дом Вильямс, 2003. - 512 с.

Приложение А

Текст файла omnetpp.ini.

[General]../Parameters/Castalia.initime-limit = 100s.field_x = 30 # meters.field_y = 30 # meters.numNodes = 9.deployment = "3x3"

# Removing variability from wireless channel.wirelessChannel.bidirectionalSigma = 0.wirelessChannel.sigma = 0

# Select a Radio and a default Tx power.node[*].Communication.Radio.RadioParametersFile = "../Parameters/Radio/CC2420.txt".node[*].Communication.Radio.TxOutputPower = "-5dBm".node[*].ApplicationName = "interNodes"

[Config varyTxPower].node[*].Communication.Radio.TxOutputPower = ${TXpower="0dBm","-1dBm","-3dBm","-5dBm"}

[Config varySigma].wirelessChannel.sigma = ${Sigma=0,1,3,5}

Текст файла interNodes.ned

simple interNodes like node.application.iApplication {:applicationID = default ("interNodes");collectTraceInfo = default (false);packetHeaderOverhead = default (8);priority = default (1);constantDataPayload = default (8);packetSpacing = default (100); // mspacketsPerNode = default (100);packetSize = default (32); // bytes:toCommunicationModule;toSensorDeviceManager;fromCommunicationModule;fromSensorDeviceManager;fromResourceManager;

}

Текст файла interNodes.h

#ifndef _INTERNODES_H_

#define _INTERNODES_H_

#include "VirtualApplication.h"namespace std;neighborRecord {id;timesRx;receivedPackets;

};interNodesTimers {_PACKET = 1,

};interNodes: public VirtualApplication {:

};

#endif

Текст файла interNodes.cc

#include "interNodes.h"_Module(interNodes);interNodes::startup()

{= (double)par("packetSpacing") / 1000.0;= par("packetsPerNode");= par("packetSize");.clear();= 0;= getParentModule()->getParentModule()->par("numNodes");_perNode = packetsPerNode * packetSpacing;_total = (txInterval_perNode * totalSNnodes);(strtod(ev.getConfig()->getConfigValue("sim-time-limit"), NULL) < txInterval_total) {() << "ERROR: Total sim time should be at least = " << txInterval_total;_error("\nError: simulation time not large enough for the conectivity map application\n");

}startTxTime = txInterval_perNode * self;(SEND_PACKET, startTxTime);

}interNodes::fromNetworkLayer(ApplicationPacket * rcvPacket, const char *source, double rssi, double lqi)

{(atoi(source), rcvPacket->getSequenceNumber());

}interNodes::timerFiredCallback(int timerIndex)

{(timerIndex) {SEND_PACKET:{(packetsSent >= packetsPerNode);(createGenericDataPacket(0.0, packetsSent, packetSize), BROADCAST_NETWORK_ADDRESS);++;(SEND_PACKET, packetSpacing);;

}

}

}interNodes::finishSpecific()

{("Packets received");(int i = 0; i < (int)neighborTable.size(); i++) {("Packets received", neighborTable[i].id,

"Success", neighborTable[i].receivedPackets);

}

}interNodes::updateNeighborTable(int nodeID, int serialNum)

{i = 0, pos = -1;tblSize = (int)neighborTable.size();(i = 0; i < tblSize; i++)(neighborTable[i].id == nodeID)= i;(pos == -1) {newRec;.id = nodeID;.timesRx = 1;((serialNum >= 0) && (serialNum < packetsPerNode)).receivedPackets = 1;.push_back(newRec);

} else {[pos].timesRx++;((serialNum >= 0) && (serialNum < packetsPerNode))[pos].receivedPackets++;

}

}

Приложение Б

Текст файла DataToSink.ned

package node.application.DataToSink;DataToSink like node.application.iApplication {:applicationID = default ("DataToSink");collectTraceInfo = default (true);priority = default (1);packetHeaderOverhead = default (8); // in bytesconstantDataPayload = default (12); // in bytesmaxSampleInterval = default (60000);// in msecminSampleInterval = default (1000); // in msecisSink = default (false);:toCommunicationModule;toSensorDeviceManager;fromCommunicationModule;fromSensorDeviceManager;fromResourceManager;

}

Текст файла DataToSink.h

#ifndef _DATATOSINK_H_

#define _DATATOSINK_H_

#include "VirtualApplication.h"

#include "Packet_m.h"namespace std;DataToSinkTimers {_SAMPLE = 1,_DATA = 2,

};DataToSink: public VirtualApplication {:maxSampleInterval;minSampleInterval;routingLevel;lastSensedValue;currSentSampleSN;randomBackoffIntervalFraction;sentOnce;:startup();fromNetworkLayer(ApplicationPacket *, const char *, double, double);handleSensorReading(SensorReadingMessage *);timerFiredCallback(int);

};

#endif

Текст файла DataToSink.cc

#include "DataToSink.h"_Module(DataToSink);DataToSink::startup()

{= ((double)par("maxSampleInterval")) / 1000.0;= ((double)par("minSampleInterval")) / 1000.0;= 0;= genk_dblrand(0);= false;(REQUEST_SAMPLE, maxSampleInterval * randomBackoffIntervalFraction);

}DataToSink::timerFiredCallback(int index)

{(index) {REQUEST_SAMPLE:{();(REQUEST_SAMPLE, maxSampleInterval);;

}

}

}DataToSink::fromNetworkLayer(ApplicationPacket * genericPacket,char *source, double rssi, double lqi)

{*rcvPacket = check_and_cast<DataToSinkDataPacket*>(genericPacket);theData = rcvPacket->getExtraData();(isSink)() << "Sink received from: " << theData.nodeID << " \tvalue=" << rcvPacket->getData();

}DataToSink::handleSensorReading(SensorReadingMessage * rcvReading)

{

// int sensIndex = rcvReading->getSensorIndex();

// string sensType(rcvReading->getSensorType());sensValue = rcvReading->getSensedValue();

// schedule the TX of the value() << "Sensed = " << sensValue;tmpData;.nodeID = (unsigned short)self;.locX = mobilityModule->getLocation().x;.locY = mobilityModule->getLocation().y;*packet2Net =DataToSinkDataPacket("Value reporting pck", APPLICATION_PACKET);Net->setExtraData(tmpData);Net->setData(sensValue);Net->setSequenceNumber(currSentSampleSN);++;(packet2Net, SINK_NETWORK_ADDRESS);= true;

}

Текст файла MultipathRingsRouting.ned

package node.communication.routing.multipathRingsRouting;MultipathRingsRouting like node.communication.routing.iRouting {:collectTraceInfo = default (false);maxNetFrameSize = default (0); // bytes, 0 means no limitnetBufferSize = default (32); // number of messagesnetDataFrameOverhead = default (14); // bytesmpathRingsSetupFrameOverhead = default (13); // bytesnetSetupTimeout = default (50); // msec:toCommunicationModule;toMacModule;fromCommunicationModule;fromMacModule;fromCommModuleResourceMgr;

}

Текст файла MultipathRingsRouting.h

#ifndef _MULTIPATHRINGSROUTING_H_

#define _MULTIPATHRINGSROUTING_H_

#include <map>

#include "VirtualRouting.h"

#include "MultipathRingsRoutingPacket_m.h"

#include "MultipathRingsRoutingControl_m.h"

#define NO_LEVEL -110

#define NO_SINK -120namespace std;MultipathRingsRoutingTimers {_SETUP_TIMEOUT = 1,

};MultipathRingsRouting: public VirtualRouting {:mpathRingsSetupFrameOverhead; // in bytesnetSetupTimeout;

// multipathRingsRouting-related member variablescurrentSequenceNumber;currentSinkID;currentLevel;tmpSinkID;tmpLevel;isSink; //is a .ned file parameter of the Application moduleisConnected; //attached under a parent nodeisScheduledNetSetupTimeout;:startup();fromApplicationLayer(cPacket *, const char *);fromMacLayer(cPacket *, int, double, double);sendTopologySetupPacket();sendControlMessage(multipathRingsRoutingControlDef);timerFiredCallback(int);processBufferedPacket();

};

Текст файла MultipathRingsRouting.cc

#include "MultipathRingsRouting.h"_Module(MultipathRingsRouting);MultipathRingsRouting::startup()

{= (double)par("netSetupTimeout") / 1000.0;= par("mpathRingsSetupFrameOverhead");

// check that the Application module used has the boolean parameter "isSink"*appModule = getParentModule()->getParentModule()->getSubmodule("Application");(appModule->hasPar("isSink"))= appModule->par("isSink");_error("\nMultiPathRings routing has to be used with an application that defines the parameter isSink");= tmpLevel = isSink ? 0 : NO_LEVEL;= tmpSinkID = isSink ? self : NO_SINK;= (isSink) ? true : false;= false;= 0;(isSink)();

}MultipathRingsRouting::sendTopologySetupPacket()

{*setupPkt =MultipathRingsRoutingPacket("Multipath rings routing setup packet", NETWORK_LAYER_PACKET);>setMultipathRingsRoutingPacketKind(MPRINGS_TOPOLOGY_SETUP_PACKET);>setSource(SELF_NETWORK_ADDRESS);>setDestination(BROADCAST_NETWORK_ADDRESS);>setSinkID(currentSinkID);>setSenderLevel(currentLevel);(setupPkt, BROADCAST_MAC_ADDRESS);

}MultipathRingsRouting::sendControlMessage(multipathRingsRoutingControlDef kind)

{*ctrlMsg =MultipathRingsRoutingControlMessage("Multipath routing control message",NETWORK_CONTROL_MESSAGE);>setMultipathRingsRoutingControlMessageKind(kind);>setLevel(currentLevel);>setSinkID(currentSinkID);(ctrlMsg);

}MultipathRingsRouting::timerFiredCallback(int index)

{(index != TOPOLOGY_SETUP_TIMEOUT);= false;(tmpLevel == NO_LEVEL) {(TOPOLOGY_SETUP_TIMEOUT, netSetupTimeout);= true;

} else if (currentLevel == NO_LEVEL) {

//Broadcast to all nodes of currentLevel-1= tmpLevel + 1;= tmpSinkID;(!isConnected) {= true;(MPRINGS_CONNECTED_TO_TREE);() << "Connected to " << currentSinkID << " at level " << currentLevel;(!TXBuffer.empty())();

} else {(MPRINGS_TREE_LEVEL_UPDATED);() << "Reconnected to " << currentSinkID << " at level " << currentLevel;

}();

}= isSink ? 0 : NO_LEVEL;= isSink ? self : NO_SINK;

}MultipathRingsRouting::processBufferedPacket()

{(!TXBuffer.empty()) {(TXBuffer.front(), BROADCAST_MAC_ADDRESS);.pop();

}

}MultipathRingsRouting::fromApplicationLayer(cPacket * pkt, const char *destination)

{dst(destination);*netPacket =MultipathRingsRoutingPacket("Multipath rings routing data packet", NETWORK_LAYER_PACKET);>setMultipathRingsRoutingPacketKind(MPRINGS_DATA_PACKET);>setSource(SELF_NETWORK_ADDRESS);>setDestination(destination);>setSinkID(currentSinkID);>setSenderLevel(currentLevel);(netPacket, pkt);(dst.compare(SINK_NETWORK_ADDRESS) == 0 || dst.compare(PARENT_NETWORK_ADDRESS) == 0) {>setSequenceNumber(currentSequenceNumber);++;(bufferPacket(netPacket)) {(isConnected)();(MPRINGS_NOT_CONNECTED);

} else {

//Here we could send a control message to upper layer informing that our buffer is full

}

} else { //++++ need to control flooding(netPacket, BROADCAST_MAC_ADDRESS);

}

}MultipathRingsRouting::fromMacLayer(cPacket * pkt, int macAddress, double rssi, double lqi)

{*netPacket = dynamic_cast <MultipathRingsRoutingPacket*>(pkt);(!netPacket);(netPacket->getMultipathRingsRoutingPacketKind()) {MPRINGS_TOPOLOGY_SETUP_PACKET:{(isSink);(!isScheduledNetSetupTimeout) {= true;(TOPOLOGY_SETUP_TIMEOUT, netSetupTimeout);= NO_LEVEL;= NO_SINK;

}(tmpLevel == NO_LEVEL || tmpLevel > netPacket->getSenderLevel()) {= netPacket->getSenderLevel();= netPacket->getSinkID();

};

}MPRINGS_DATA_PACKET:{dst(netPacket->getDestination());src(netPacket->getSource());senderLevel = netPacket->getSenderLevel();sinkID = netPacket->getSinkID();(dst.compare(BROADCAST_NETWORK_ADDRESS) == 0 ||.compare(SELF_NETWORK_ADDRESS) == 0) {

// We are not filtering packets that are sent to this node directly or to

// broadcast network address, making application layer responsible for them(pkt->decapsulate());

} else if (dst.compare(SINK_NETWORK_ADDRESS) == 0) {(senderLevel == currentLevel + 1) {(self == sinkID) {

// Packet is for this node, if filter passes, forward it to application(isNotDuplicatePacket(pkt))(decapsulatePacket(pkt));() << "Discarding duplicate packet from node " << src;

} else if (sinkID == currentSinkID) {

// We want to rebroadcast this packet since we are not its destination

// For this, a copy of the packet is created and sender level field is

// updated before calling toMacLayer() function*dupPacket = netPacket->dup();>setSenderLevel(currentLevel);(dupPacket, BROADCAST_MAC_ADDRESS);

}

}

} else if (dst.compare(PARENT_NETWORK_ADDRESS) == 0) {(senderLevel == currentLevel + 1 && sinkID == currentSinkID) {

// Packet is for this node, if filter passes, forward it to application(isNotDuplicatePacket(pkt))(decapsulatePacket(pkt));() << "Discarding duplicate packet from node " << src;

}

};

}

}

}

Текст файла omnetpp.ini.

[General]../Parameters/Castalia.initime-limit = 600s.field_x = 100 # meters.field_y = 100 # meters.numNodes = 36.deployment = "6x6".node[*].Communication.Radio.RadioParametersFile = "../Parameters/Radio/CC2420.txt".node[*].Communication.RoutingProtocolName = "MultipathRingsRouting".node[*].Communication.MACProtocolName = "TMAC".node[*].ApplicationName = "DataToSink".node[*].Communication.Routing.collectTraceInfo = true.node[3].Application.isSink = true

[Config varyTxPower].node[*].Communication.Radio.TxOutputPower = ${TXpower="0dBm","-1dBm","-3dBm","-5dBm"}

[Config varySigma].wirelessChannel.sigma = ${Sigma=0,1,3,5}