автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Оптимизация работы маломощной беспроводной сенсорной сети на базе её имитационной модели

На правах рукописи

Трифонов Сергей Владимирович ^

ОПТИМИЗАЦИЯ РАБОТЫ МАЛОМОЩНОЙ БЕСПРОВОДНОЙ СЕНСОРНОЙ СЕТИ НА БАЗЕ ЕЁ ИМИТАЦИОННОЙ МОДЕЛИ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2013

2 * ДПР ¿013

005057830

Работа выполнена на кафедре вычислительной математики Московского физико-технического института (государственного университета)

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

Холодов Ярослав Александрович

Официальные оппоненты: доктор физико-математических наук,

доцент

Суриков Владимир Николаевич, Институт точной механики и вычислительной техники им. С.А. Лебедева РАН, заместитель генерального директора института

кандидат физико-математических наук, доцент

Евдокимов Алексей Витальевич, учебно-научный центр инфокоммуникационных технологий Московского физико-технического института

(государственного университета), старший научный сотрудник

Ведущая организация: НИИ прикладной акустики (НИИПА)

3 &

Защита состоится 2013г. в ¿(7 час. на заседании

диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

Автореферат разослан СО^^Ъ^^С1- 201 Зг.

Ученый секретарь

диссертационного совета Д 212.156.05

О.С. Федько

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

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

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

Рассматриваются беспроводные сети, для которых характерно сверхнизкое энергопотребление и большое количество миниатюрных устройств, обменивающихся относительно небольшим количеством информации по протоколу ZigBee. Принципиальной отличительной особенностью беспроводных сенсорных сетей, т.е. сетей датчиков, является принцип ретрансляции данных по цепи. Это позволяет собирать информацию со значительных объектов, превосходящих по своим размерам радиус связи одного элемента. Элементы сенсорной сети являются автономными, содержат датчики для контроля внешней среды, микрокомпьютер и маломощный радио-приёмо-передатчик.

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

Цели и задачи работы

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

Задачи работы:

1. Построение математической модели беспроводной сенсорной сети.

2. Построение дискретно-событийной имитационной модели беспроводной сенсорной сети, позволяющей определять время доставки пакетов.

3. Построение непрерывной имитационной модели беспроводной сенсорной сети, позволяющей прогнозировать расход энергии устройств.

4. Разработка комплекса программ для пакетного дискретно-событийного имитационного моделирования поведения сети.

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

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

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

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

Научная новизна

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

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

Научная и практическая ценность

Наиболее значимым достижением диссертационной работы являются результаты комплексного исследования поведения сенсорной сети. Проведённые стендовые и вычислительные эксперименты показали что латентность сети и энергопотребление устройств могут быть одновременно снижены. Для верификации имитационная модель была сверена с результатами стендового эксперимента и показала приемлемую ошибку менее 5% для времени доставки сообщений. Хорошее соответствие между результатами вычислительного и натурного экспериментов позволяет говорить о высокой степени их достоверности.

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

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

Соответствие паспорту специальности 05.13.18

Работа содержит все необходимые компоненты специальности 05.13.18:

1. Математическое моделирование. Разработаны модели различной степени детальности: математическая модель сети с применением теории графов, пакетная дискретно-событийная имитационная модель сети и непрерывная имитационная модель, описывающая поведение сети на длительном отрезке времени.

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

3. Комплексы программ. Для проведения как натурного, так и имитационного моделирования был разработан комплекс программ: SNMS, SNOPT, SNRKSOLVER, LOGANALYZER, NSTRAN, а также выполнены модификации исходного кода дискретно-событийного сетевого симулятора ns-2.

Апробация работы

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

• 50-я и 51-я научные конференции МФТИ, Москва-Долгопрудный, 2007 и 2008;

• V Всероссийская межвузовская конференция молодых ученых, Санкт-Петербургский государственный университет информационных технологий, механики и оптики, 2008.

• Международная конференция «Опыт и результаты исследований, проводимых под руководством приглашенных ученых-соотечественников», Москва, 2011.

Публикации

По теме диссертации автором опубликовано семь работ, три из которых [1,2,3] — в изданиях из списка, рекомендованного ВАК РФ.

Личный вклад автора

Все научные результаты, вынесенные на защиту, получены лично автором. Постановка задачи, результаты расчетов и стендовых экспериментов обсуждались с научным руководителем Холодовым Я.А.

Объём и структура диссертации

Диссертация состоит из введения, семи глав, заключения, списка использованных источников и трех приложений. Работа изложена на 101 странице текста, содержит 12 таблиц, 19 рисунков. Библиография включает 54 наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

Описана структура стека протоколов и даны ссылки на спецификации, определяющие каждый из протоколов.

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

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

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

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

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

§3.4 посвящен проблеме дискретно-событийного моделирования сетей связи. Описан принцип пакетного моделирования. Рассмотрена проблема сложности моделей с несколькими взаимодействующими узлами, каждый из которых должен быть промоделирован, во-первых, сам по себе, и, во-вторых,

при взаимодействии с другими узлами. Представлена информация о стандартной модели взаимодействия открытых систем 081.

В §3.5 обсуждаются особенности моделей беспроводных сетей и проблемы связанные с построением и использованием данных моделей.

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

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

В §5.1 сформулированы исходные предположения о топологии и организации работы сети:

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

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

3. Объем информации, генерируемый сетью в единицу времени, не превышает ее пропускной способности.

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

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

Дальнейшее уменьшение энергопотребления сети связано с возможностью конечного устройства засыпать сразу же после родительского маяка, не слушая суперфрейм, при условии, что устройству не адресовано данных и у него нет данных для отправки. Эта оптимизация позволяет снизить энергопотребление ещё в 3—4 раза. Результаты теоретического расчёта приведены на рис. 1.

i

2 4 в в 18 12 1<

Рис. 1. Зависимость отношений средних сил токов от ВО (/' — сила тока для 1-й оптимизации, I" — для обоих, /— без них).

Рассмотрим сеть, состоящую из N узлов. Обозначим через V = {al,a2,...,aN) множество узлов. Два узла, находящиеся в области прямой видимости друг друга, образуют ребро. Таким образом, мы получим граф смежности G = {V,E}. Пусть граф не ориентирован. Узел а0 — координатор

сети. Построим все подграфы Тк, к е 1, К графа G, являющиеся деревьями с корневым элементом а0 и содержащие все его узлы, при этом Rk — набор всех маршрутизаторов графа Тк.

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

Решим задачу максимизации времени жизни сети. Рассмотрим произвольное подмножество {Rk }"=i множества {Rk . Имеем М, —

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

, Т(МЛ Т(М-М,Л r ir r SM. „

где IR — средняя сила тока маршрутизатора; 1Е— средняя сила тока конечного устройства. Время жизни сети будет

Т = min — -» шах , (3.2)

где q. — заряд устройства ah Пусть в начальный момент времени g, = Q. Тогда условие (3.2) переходит в условие

max Л/.

max /,. =IE+ (lR ~ 1Е) Чг:--(3.3)

■ м

Если наборы {Rk независимы, тогда шах М,- = 1 и

М —» шах . (3.4)

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

М<ттк,. (3.5)

/б/

где / — множество индексов вершин, не являющихся соседями координатора; к,— число соседей узла а,.

Алгоритм распределения ролей позволяет решить задачу о поиске максимального количества М независимых наборов маршрутизаторов {-Rm}m=i- Точное решение этой задачи для больших графов требует больших затрат времени. Поэтому используется простая схема распределения ролей на графе (рис. 2), которая даёт достаточно большое М. Алгоритм является «жадным».

Рис. 2. Схема алгоритма распределения ролей.

Чтобы получить Тт соответствующее полученным [{т:

• Соединяем координатор со всеми его соседями.

• К маршрутизаторам подсоединяем их соседей.

• Повторяем пункт 2 пока все узлы не будут соединены.

В §5.3 изучается задача минимизации среднего времени доставки сообщения координатору сети. Предлагается алгоритм установки централизованного расписания маяков для маршрутизаторов и алгоритм распределения слотов суперфреймов, позволяющий найти данное расписание.

Рассчитаем время доставки Аа сообщений от узла а к координатору. Сообщения передаются по цепочке {Ь,Уыа, где Ь0 = а0 и Ьа= а. Время между возникновением события и передачей сообщения о нём от к Ьал есть некоторая случайная величина г,, распределённая в интервале [0,57 — ££)).

Дальнейшая часть времени доставки определяется задержками на маршрутизаторах. Задержка на маршрутизаторе равна промежутку времени между собственным суперфреймом и родительским суперфреймом на этом маршрутизаторе. Цепочка содержит (1-2 маршрутизаторов, г^ — задержки

на них.

Последнее слагаемое определяется моментом времени, когда произошла передача сообщения координатору. Будем считать его случайной величиной г2, распределённой в интервале [0, £0). Итак,

Будем считать случайные величины равномерно распределёнными на своих интервалах. Тогда £(г, + т2) = ВП 2 . Среднее по узлам время доставки сообщений

(3.6)

Раскрыв скобки и сгруппировав члены, получим

где уИТ, а) — размер поддерева с корнем а. То есть задача минимизации время доставки сообщений сводится к задаче:

• измерение времени доставки сообщений в модели аналогичной натурному эксперименту с сетью топологии типа «цепочка»;

• измерение времени доставки сообщения в больших сетях с помощью пэ-2;

• определение эффективности алгоритма распределения ролей на квадратных сетках из узлов с помощью пэ-2.

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

¿С ¿1

- /^И!,

Цк+1Е{М-\))дт

А/

С начальным условием #¡,(0) = 2* для т = \,М . Для её решения был разработан новый эффективный численный метод высокого порядка точности, основанный на использовании продолженных систем ОДУ. Использовалась реализация метода со вторым порядком аппроксимации.

Было проведено исследование влияния частоты переключений на время жизни сети. Полученные результаты представлены на рисунке ниже.

г <

без переключений

переключение переключение

раз в час А раз в день

1500 2000 2500

время, ч

Рис. 4. Изменение заряда батарей лимитирующих устройств при различных параметрах переключения топологий сети.

Исследовались сети, в которой существует три независимых набора маршрутизаторов, при ВО = 4 и БО = 0. При этом, использовались силы токов полученные в натурных экспериментах. Проведены прогоны для переключений раз в час, раз в день и без переключений. Вариант без переключений является недостижимым пределом, и соответствующее время жизни берётся за 100%.

время доставки сообщений, с

Рис. 8. Гистограммы распределения сообщений по временам их

доставки.

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

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

ооооо ооооо

ооооо оо©оо

оо#®о о©#©о

ооооо ооооо

ооооо ооооо

А В

ооооо ооооо

о®@@о ооооо

©©•о© ©©•©©

о@©оо о®®©©

ооооо ооооо

с и

Рис. 9. Исследованные шаблоны связности узла.

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

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

N31 на рис. 7. Но даже при неполной информации о графе связности, в оптимальном режиме узлам удалось присоединиться (рис. 6).

Табл. 1. Число независимых наборов маршрутизаторов

N 9 16 25 36 49 64 81 100 121 тах

Шаблон А 2 1 1 1 1 1 1 1 1 2

Шаблон В 0 2 2 2 2 2 2 2 2 3

Шаблон С 0 4 4 3 4 4 3 4 4 5

Шаблон Б 0 7 7 5 6 6 6 5 6 7

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

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

В заключении приведены основные результаты работы.

Приложение 1 содержит список всех использованных в тексте диссертации аббревиатур.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Построены математическая и имитационные (дискретно-событийная, непрерывная) модели беспроводной сенсорной сети.

2. Разработан комплекс программ для пакетного дискретно-событийного имитационного моделирования поведения сети на основе сетевого симулятора пб-2.

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

использовании продолженных систем ОДУ. На базе нового метода создан комплекс программ для непрерывного имитационного моделирования поведения сенсорной сети на длительные временные интервалы.

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

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

6. С помощью имитационной модели на квадратных сетках проведены исследования алгоритма распределения ролей. Показано, что алгоритм может давать 2-7 независимых наборов маршрутизаторов, обеспечивающих связность топологии. Это позволяет, в конечном счете, увеличить время жизни сети в 1,7-3,8 раза.

7. Для ускорения доставки сообщений предложен алгоритм распределения слотов суперфреймов.

8. Проведены натурные и вычислительные эксперименты для измерения времени доставки сообщений. Результаты измерений хорошо согласуются между собой. Показано, что применение алгоритма уменьшает среднее время доставки сообщений в 2-4 раза в зависимости от размера топологии сети и особенностей её построения.

Публикации автора по теме диссертации.

1. Трифонов C.B., Холодов Я.А. Исследование и оптимизация работы беспроводной сенсорной сети на основе протокола ZigBee // Компьютерные исследования и моделирование — М., 2012. — Т.4, №4 — С. 855-869.

2. Трифонов C.B., Холодов Я.А., Миненко М.И., Истомин Т.Е., Чечендаев A.B. Алгоритмы оптимизации работы беспроводной сенсорной сети на базе протокола ZigBee // Научно-технический вестник СПбГУ ИТМО - СПб, 2008. - № 56 - С. 86-95.

3. СеверовД.С., Трифонов C.B., Миненко М.И., Холодов Я.А. Численное моделирование IP-сетей передачи данных в рамках уравнений сплошной

среды // Научно-технический вестник СПбГУ ИТМО - СПб, 2008. - № 46 -С. 218-227.

4. Трифонов C.B., Васильев М.О., Миненко М.И., ХолодовЯ.А., Истомин Т.Е., Чечендаев A.B. Оптимизация работы беспроводных сенсорных сетей на примере протокола ZigBee // Сборник научных трудов МФТИ, Моделирование и обработка информации. - М., 2008. - С. 246-257.

5. Трифонов C.B., Холодов Я.А. Исследование распространения мощных сверхширокополосных радиоимпульсов на дальние расстояния в атмосфере // Сборник трудов молодежной научной конференции "Физика и прогресс - 2008" - СПб, 2008. - С. 264-268.

6. Трифонов C.B. Об исследование распространения мощных сверхширокополосных радиоимпульсов на дальние расстояния в атмосфере П Современные проблемы фундаментальных и прикладных наук. Часть III. Аэрофизика и космические исследования: Труды 51-й научной конференции МФТИ — М., 2008. — Т.2. — С.72-74.

7. Трифонов C.B. Оптимизационные алгоритмы управления работой беспроводной сенсорной сети на основе протокола ZigBee // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды 50-й научной конференции МФТИ. - М., 2007.-Т. 2.-С. 144-146.

Трифонов Сергей Владимирович

ОПТИМИЗАЦИЯ РАБОТЫ МАЛОМОЩНОЙ БЕСПРОВОДНОЙ СЕНСОРНОЙ СЕТИ НА БАЗЕ ЕЁ ИМИТАЦИОННОЙ МОДЕЛИ

АВТОРЕФЕРАТ

Подписано в печать 12.04.2013 Формат 60 х 84 '/¡6. Усл. печ. л. 1,0. Тираж 100 экз. Заказ №Ф273. Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Московский физико-технический институт (государственный университет) Кафедра вычислительной математики

На правах рукописи

04201356197

УДК 519.876.5+519.622, ТРИФОНОВ Сергей Владимирович

Оптимизация работы маломощной беспроводной сенсорной сети на базе её имитационной модели

Специальность 05.13.18 «Математическое моделирование, численные методы и комплексы программ»

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель

кандидат физико-математических наук

Я.А. Холодов

МОСКВА-2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..........................................................................................................................4

Актуальность работы..................................................................................................4

Цели и задачи работы..................................................................................................5

Научная новизна..........................................................................................................6

Научная и практическая ценность.............................................................................7

Соответствие специальности 05.13.18.......................................................................8

ГЛАВА 1. БЕСПРОВОДНЫЕ СЕТИ.................................................................................8

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

1.2. Обзор и сравнение беспроводных технологий................................................10

ГЛАВА 2. СТЕК ПРОТОКОЛОВ гЮВЕЕЛЕЕЕ 802.15.4............................................15

2.1. Основные характеристики ....................................................................15

2.2. Принцип работы протокола канального уровня..............................................17

2.3. Протокол сетевого уровня.................................................................................26

ГЛАВА 3. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ БЕСПРОВОДНЫХ СЕТЕЙ...26

3.1. Имитационное моделирование..........................................................................26

3.2. Классификация имитационных моделей..........................................................27

3.3. Дискретно-событийное моделирование...........................................................28

3.4. Моделирование сетей связи...............................................................................30

3.5. Особенности моделей беспроводных сетей.....................................................33

ГЛАВА 4. СЕТЕВОЙ СИМУЛЯТОР N8-2.....................................................................35

4.1. Архитектура симулятора...................................................................................35

4.2. Принцип работы ядра пз-2.................................................................................37

4.3. Протоколы и трафик...........................................................................................39

4.4. Моделирование ZigBee в пб-2...........................................................................40

ГЛАВА 5. РАЗРАБОТКА ОПТИМИЗАЦИОННЫХ АЛГОРИТМОВ УПРАВЛЕНИЯ РАБОТОЙ СЕТИ гЮВЕЕ................................................................................................41

5.1. Постановка задачи оптимизации......................................................................41

5.2. Задача минимизации энергопотребления........................................................42

5.3. Задача минимизации времени доставки сообщений координатору..............53

ГЛАВА 6. ПОСТАНОВКА И ПРОВЕДЕНИЕ НАТУРНЫХ И ВЫЧИСЛИТЕЛЬНЫХ

ЭКСПЕРИМЕНТОВ..........................................................................................................57

6.1. Работы выполненные для подготовки и проведения натурных экспериментов............................................................................................................57

6.2. Работы выполненные для подготовки и проведения вычислительных экспериментов............................................................................................................60

ГЛАВА 7. АНАЛИЗ РЕЗУЛЬТАТОВ ЭКСПЕРИМЕНТОВ.........................................64

7.1. Анализ результатов натурных экспериментов................................................64

7.2. Анализ результатов численных экспериментов..............................................70

ЗАКЛЮЧЕНИЕ..................................................................................................................77

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ........................................................79

ПРИЛОЖЕНИЕ 1. ИСПОЛЬЗУЕМЫЕ АББРЕВИАТУРЫ...........................................84

ПРИЛОЖЕНИЕ 2. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ.......................................................87

ПРИЛОЖЕНИЕ 3. КОД СЦЕНАРИЯ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА.. 89

ВВЕДЕНИЕ

Актуальность работы

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

Однако имитационное моделирование не может учесть всех аспектов реальной моделируемой системы. Всегда вводятся предположения, позволяющие упростить и, как следствие, ускорить вычислительный расчёт. Но интуитивно понять, какие предположения не повлекут за собой расхождения модели и реальной системы, сложно. Поэтому в данной работе для проверки модели используется стендовое моделирование. Это экспериментирование с небольшой, но реальной системой, позволяющее учесть все аспекты взаимодействия её частей и влияние внешних факторов. После получения результатов такого эксперимента появляется задача их масштабирования и последующего прогнозирования поведения систем больших размеров, а также оптимизации характеристик системы по одному или нескольким параметрам. Для решения этой задачи в данной работе используется открытый пакет программ — дискретно-событийный сетевой симулятор ns-2 [47].

В работе рассматриваются беспроводные сети, для которых характерно

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

обменивающихся относительно небольшим количеством информации.

Существующие протоколы беспроводной связи, такие как Bluetooth и Wi-Fi, не

учитывают эту специфику рассматриваемых сетей. Например, энергопотребление

протокола Wi-Fi слишком велико, а попытка обеспечить универсальность протокола

Bluetooth привела к его усложнению и неприменимости к широкому кругу задач,

4

требующих дешевизны передающих устройств. Именно поэтому был разработан протокол ZigBee, учитывающий недостатки более ранних протоколов.

Сегодня тема моделирования и оптимизации работы беспроводных сенсорных сетей вызывает интерес многих ученых [14,21,23,24,26,27,29,32,33,35,39,40,45,49]. Это вызвано в первую очередь тем, что протоколы, лежащие в основе таких сетей как и сфера их применения достаточно новы и бурно развиваются. К примеру, первая версия спецификации IEEE 802.15.4 была создана в 2003 году и в неё постоянно вносятся изменения (2006, 2007,2009). Однако большинство работ склоняются в сторону использования децентрализованных и реактивных протоколов, а тема централизованного управления работой сети осталась не достаточно хорошо проработанной, что автор и пытается исправить.

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

Цели и задачи работы

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

Задачи работы:

1. Построение математической модели беспроводной сенсорной сети.

2. Построение дискретно-событийной имитационной модели беспроводной сенсорной сети, позволяющей определять время доставки пакетов.

3. Построение непрерывной имитационной модели беспроводной сенсорной сети, позволяющей прогнозировать расход энергии устройств.

4. Разработка комплекса программ для пакетного дискретно-событийного имитационного моделирования поведения сети.

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

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

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

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

Научная новизна

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

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

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

долгого времени. Именно это обстоятельство даёт ранее не использовавшуюся в беспроводных сетях возможность централизации управления сетью.

Научная и практическая ценность

Наиболее значимым достижением диссертационной работы являются результаты комплексного исследования поведения сенсорной сети. Проведённые стендовые и вычислительные эксперименты показали, что для из 8 устройств выстроенных в цепочку модифицированный стек значительно (в 3-4 раза) уменьшает латентность сети по сравнению со стандартным. Для разветвленной топологии время доставки уменьшается в 2-3 раза. Более обширное численное исследование показывает, что данный результат масштабируется на сети, состоящие из сотен устройств. Для верификации имитационная модель была сверена с результатами стендового эксперимента и показала приемлемую ошибку менее 5% для времени доставки сообщений. Хорошее соответствие между результатами вычислительного и натурного экспериментов позволяет говорить о высокой степени их достоверности.

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

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

Соответствие специальности 05.13.18

Работа содержит все необходимые компоненты специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»:

1. Математическое моделирование. Описана математическая модель работы сети ZigBee с применением теории графов.

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

3. Комплексы программ. Для проведения как натурного, так и имитационного моделирования был разработан ряд программ: 8ЫМ8, 81\ЮРТ, 8Ы0БЕ80ЬУЕК, ЬООАЫАЬУгЕЯ, ^ТКАИ, а также выполнены модификации исходного кода сетевого симулятора пз-2.

Глава 1. Беспроводные сети 1.1. Беспроводные сенсорные сети

1.1.1. Преимущества технологии

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

Другими важными свойствами сенсорных сетей являются самовосстановление, и самоорганизация. После установки элементов они

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

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

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

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

1.1.2. Использование сенсорных сетей

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

• Промышленный мониторинг [34]

о Технический надзор и профилактическое обслуживание оборудования о Эффективное использование оборудования о Мониторинг производственных процессов [44] о Прецизионное сельское хозяйство о Удаленный мониторинг имущества/ценностей

• Автоматизация строений («умный дом») [21]

о Управление энергоснабжением

о Контроль НУ АС (кондиционирование, вентиляция, отопление) о Системы безопасности

о Мониторинг состояния окружающей среды внутри и снаружи о Контроль освещения

о Системы пожарной сигнализации

о Ретрансляторы для счетчиков газа, воды, электроэнергии

• Логистика

о Отслеживание грузов, контейнеров о Мониторинг упаковки, определение о Обеспечение складского учета при перемещении товаров о Экология и чрезвычайные ситуации о Мониторинг загрязнений окружающей среды о Миграция животных [28], насекомых о Лесные пожары и т.д.

о Спасение людей при чрезвычайных ситуациях

• Здравоохранение

о Физиологический мониторинг — сердечный ритм, кровяное давление,

температура, уровень стресса и другие параметры жизнедеятельности о Неотложная помощь о Мониторинг персонала

• Системы безопасности и оборона

о Коммерческие и домашние системы безопасности о Мониторинг персонала

о Отслеживание маршрутов движения войск, соединений о Средства связи и боевой разведки о Охрана промышленных и военных объектов

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

Ниже автор приводит обзор существующих беспроводных технологий. На основе этого обзора, делается выбор технологии наиболее подходящей для применения в области сенсорных сетей. Рассматриваются спецификации Wi-Fi, Bluetooth и ZigBee.

1.2.1. Wi-Fi

Технология Wi-Fi базируется на стандарте IEEE 802.11. Обычно схема Wi-Fi сети содержит не менее одной точки доступа и не менее одного клиента. Также возможно подключение двух клиентов в режиме точка-точка, когда точка доступа не используется, а клиенты соединяются напрямую посредством сетевых адаптеров. Точка доступа передаёт свой идентификатор сети (SSID) с помощью специальных сигнальных пакетов на скорости 0,1 Мбит/с каждые 100 мс. Поэтому 0,1 Мбит/с — наименьшая скорость передачи данных для Wi-Fi. Стандарт Wi-Fi даёт клиенту полную свободу при выборе критериев для соединения.

Основные области применения Wi-Fi - обеспечение доступа в Интернет с мобильных устройств, передача файлов. Также пропускная способность Wi-Fi канала обеспечивает возможность передачи звука и видео.

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