Содержание к диссертации
Введение
ГЛАВА 1. Беспроводные сети 8
1.1. Беспроводные сенсорные сети 8
1.2. Обзор и сравнение беспроводных технологий 10
ГЛАВА 2. Стек протоколов zigbee/ieee 802.15.4 15
2.1. Основные характеристики ZigBее 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. Сетевой симулятор NS-2 35
4.1. Архитектура симулятора 35
4.2. Принцип работы ядра ns-2 37
4.3. Протоколы и трафик 39
4.4. Моделирование ZigBee в ns-2 40
ГЛАВА 5. Разработка оптимизационных алгоритмов управления работой сети ZIGBEE 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
Список использованных источников
- Обзор и сравнение беспроводных технологий
- Принцип работы протокола канального уровня
- Дискретно-событийное моделирование
- Задача минимизации времени доставки сообщений координатору
Введение к работе
Актуальность работы
Для изучения протоколов передачи данных в компьютерных сетях широко используется метод дискретно-событийного имитационного моделирования, позволяющий представить процесс функционирования системы как последовательность событий. Каждое событие происходит в определенный момент времени и может изменять состояние системы. Сегодня для решения задач дискретно-событийного имитационного моделирования сетей связи существует достаточно широкий спектр программных средств: от библиотек функций для стандартных компиляторов до специализированных языков программирования.
Однако имитационное моделирование не может учесть всех аспектов реальной моделируемой системы. Всегда вводятся предположения, позволяющие упростить и, как следствие, ускорить вычислительные расчёты. Интуитивно понять, какие предположения не повлекут за собой расхождения модели и реальной системы, сложно. Поэтому в данной работе для верификации модели используется стендовое моделирование. Это экспериментальное исследование небольшой реальной системы, позволяющее учесть все аспекты взаимодействия её частей и влияние внешних факторов. Так как стендовые исследования проводятся с небольшим числом устройств, то для обобщения результатов на системы большей размерности необходим переход к имитационной модели. В работе используется имитационная модель, построенная с использованием дискретно-событийного сетевого симулятора ns-2.
Рассматриваются беспроводные сети, для которых характерно сверхнизкое энергопотребление и большое количество миниатюрных устройств, обменивающихся относительно небольшим количеством информации по протоколу ZigBee. Принципиальной отличительной особенностью беспроводных сенсорных сетей, т.е. сетей датчиков, является принцип ретрансляции данных по цепи. Это позволяет собирать информацию со значительных объектов, превосходящих по своим размерам радиус связи одного элемента. Элементы сенсорной сети являются автономными, содержат датчики для контроля внешней среды, микрокомпьютер и маломощный радио-приёмо-передатчик.
Возможности использования сенсорных сетей простираются во многие сферы деятельности. В качестве наиболее очевидных областей их применения эксперты называют промышленный мониторинг, автоматизацию строений («умный дом»), логистику, здравоохранение, системы безопасности и оборону.
Цели и задачи работы
Целью данной работы являлось комплексное исследование маломощной беспроводной сенсорной сети на основе математического и имитационного моделирования работы данной сети с помощью созданного комплекса программ.
Задачи работы:
-
Построение математической модели беспроводной сенсорной сети.
-
Построение дискретно-событийной имитационной модели беспроводной сенсорной сети, позволяющей определять время доставки пакетов.
-
Построение непрерывной имитационной модели беспроводной сенсорной сети, позволяющей прогнозировать расход энергии устройств.
-
Разработка комплекса программ для пакетного дискретно -событийного имитационного моделирования поведения сети.
-
Разработка нового эффективного высокоточного численного метода решения систем обыкновенных дифференциальных уравнений в виде комплекса программ для непрерывного имитационного моделирования поведения сети на длительные временные интервалы.
-
Разработка алгоритмов и соответствующего программного обеспечения, модифицирующего стек протоколов для работы сети в режиме со сверхнизким энергопотреблением и ускоренной доставкой пакетов.
-
Проведение ряда сравнительных стендовых экспериментов с использованием модифицированного и стандартного стеков протоколов c целью измерения и сравнения характеристик работы сети, в частности, типичного времени жизни устройств в различных режимах работы сети и времени доставки сообщений.
-
Проведение ряда сравнительных вычислительных экспериментов с использованием моделей модифицированного и стандартного стека протоколов для исследования эффективности разработанных алгоритмов оптимизации при увеличении числа узлов сети.
Научная новизна
В работе предложен новый подход к решению проблем энергосбережения в сенсорных сетях (сети датчиков), позволяющем одновременно сократить как энергопотребления сетевых устройств, так и время доставки сообщений. Подход основан на модификации стека протоколов ZigBee. Предлагаемые модификации стека основаны на алгоритмах централизованного управления сетью, включающих: сбор информации о топологии сети, динамическое изменение ролей устройств и установку оптимального расписания. Централизованное управление в области беспроводных сетей в настоящее время не пользуется большой популярностью в силу высокой мобильности устройств и возникновения шума в радиоканале, который приводит к изменениям графа связности сети. Однако в нише сенсорных сетей, например для промышленного мониторинга, данные обстоятельства не существенны. Как правило, датчики остаются неподвижными, а радиоканал чаще всего не меняет свойств на протяжении долгого времени. Именно эти факторы позволили задействовать не использовавшуюся ранее в беспроводных сетях возможность централизованного управления.
Научная и практическая ценность
Наиболее значимым достижением диссертационной работы являются результаты комплексного исследования поведения сенсорной сети. Проведённые стендовые и вычислительные эксперименты показали что латентность сети и энергопотребление устройств могут быть одновременно снижены. Для верификации имитационная модель была сверена с результатами стендового эксперимента и показала приемлемую ошибку менее 5% для времени доставки сообщений. Хорошее соответствие между результатами вычислительного и натурного экспериментов позволяет говорить о высокой степени их достоверности.
Данные результаты позволяют говорить, что разработанные алгоритмы могут быть использованы в различных областях применения сенсорных сетей при условии неподвижности датчиков и относительно постоянного уровня помех в радиоканале. Методология и разработанные алгоритмы могут лечь в основу новых протоколов для централизованного управления быстрой сенсорной сетью с низким энергопотреблением.
Вторым по значимости результатом работы является новый эффективный численный метод высокого порядка точности, основанный на использовании продолженных систем ОДУ. Данный метод позволяет эффективно решать системы ОДУ, особенностью которых является простота производных правых частей уравнений, что имеет место для исследуемой в диссертации системы.
Соответствие паспорту специальности 05.13.18
Работа содержит все необходимые компоненты специальности 05.13.18:
-
-
Математическое моделирование. Разработаны модели различной степени детальности: математическая модель сети с применением теории графов, пакетная дискретно-событийная имитационная модель сети и непрерывная имитационная модель, описывающая поведение сети на длительном отрезке времени.
-
Численные методы. На основе непрерывной имитационной модели получена система дифференциальных уравнений, для решения которой был разработан новый эффективный численный метод высокого порядка точности, основанный на использовании продолженных систем ОДУ.
3. Комплексы программ. Для проведения как натурного, так и имитационного моделирования был разработан комплекс программ: SNMS, SNOPT, SNRKSOLVER, LOGANALYZER, NSTRAN, а также выполнены модификации исходного кода дискретно-событийного сетевого симулятора ns-2.
Апробация работы
Результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих научных конференциях:
50-я и 51-я научные конференции МФТИ, Москва-Долгопрудный, 2007 и 2008;
V Всероссийская межвузовская конференция молодых ученых, Санкт-Петербургский государственный университет информационных технологий, механики и оптики, 2008.
Международная конференция «Опыт и результаты исследований, проводимых под руководством приглашенных ученых-соотечественников», Москва, 2011.
Публикации
По теме диссертации автором опубликовано семь работ, три из которых [1,2,3] - в изданиях из списка, рекомендованного ВАК РФ.
Личный вклад автора
Все научные результаты, вынесенные на защиту, получены лично автором. Постановка задачи, результаты расчетов и стендовых экспериментов обсуждались с научным руководителем Холодовым Я.А.
Объём и структура диссертации
Диссертация состоит из введения, семи глав, заключения, списка использованных источников и трех приложений. Работа изложена на 101 странице текста, содержит 12 таблиц, 19 рисунков. Библиография включает 54 наименования.
Обзор и сравнение беспроводных технологий
Технология 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 в таком режиме привело бы к накладным расходам, для поддержания соединения, превышающим расходы на передачу полезной части данных - как в терминах объема передаваемой информации, так и в терминах энергии, необходимой для передачи. Эта особенность делает Wi-Fi неприменимым в области сенсорных сетей, поскольку к устройствам выполняющим функцию сенсора предъявляется требование максимально долгой автономной работы.
Спецификация Bluetooth [19] была разработана группой Bluetooth Special Interest Group (Ericsson, IBM, Intel, Toshiba и Nokia) и позже стала частью стандарта IEEE 802.15.1. Основная цель технологии - предоставление универсального беспроводного протокола взаимодействия различных устройств. Радиосвязь осуществляется в диапазоне свободном от лицензирования: 2,4 - 2,4835 ГГц. В Bluetooth применяется метод расширения спектра со скачкообразной перестройкой частоты [9] (Frequency Hopping Spread Spectrum, FHSS). Метод FHSS прост в реализации, обеспечивает устойчивость к широкополосным помехам, а оборудование недорого. Согласно алгоритму FHSS, в Bluetooth несущая частота сигнала скачкообразно меняется 1600 раз в секунду [10] (всего выделяется 79 рабочих частот шириной в 1 МГц. Последовательность переключения между частотами для каждого соединения является псевдослучайной и известна только передатчику и приёмнику, которые каждые 625 мкс (один временной слот) синхронно перестраиваются с одной несущей частоты на другую. Таким образом, если рядом работают несколько пар приёмник-передатчик, то они не мешают друг другу. Этот алгоритм является также составной частью системы защиты конфиденциальности передаваемой информации: переход происходит по псевдослучайному алгоритму и определяется отдельно для каждого соединения.
Bluetooth поддерживает соединения «pointo-point» и «pointo-multipoint». В более поздних версиях спецификации появилась поддержка Enhanced Data Rate (EDR) для ускорения передачи данных. Номинальная скорость при использовании EDR составляет примерно 3 Мбит/с. В версии 3.0+HS принятой в апреле 2009 года били приняты дальнейшие шаги по увеличению скорости передачи данных. Модули с поддержкой этой спецификации соединяют в себе две радиосистемы: первая обеспечивает передачу данных в 3 Мбит/с (стандартная для Bluetooth 2.0) и имеет низкое энергопотребление; вторая совместима со стандартом 802.11 и обеспечивает возможность передачи данных со скоростью до 24 Мбит/с. Выбор радиосистемы для передачи данных зависит от размера передаваемого файла.
Однако в версии Bluetooth 4.0 от 30 июня 2010 года тенденция увеличения скорости прекратилась. В спецификацию был добавлен режим работы с низким энергопотреблением. Протокол Bluetooth с низким энергопотреблением предназначен, прежде всего, для миниатюрных электронных датчиков. Низкое энергопотребление достигается за счёт использования специального алгоритма работы. Передатчик включается только на время отправки данных, что обеспечивает возможность работы от одной батарейки типа CR2032 в течение нескольких лет. Стандарт предоставляет скорость передачи данных в 250 кбит/с при размере пакета данных 8-27 байт. В целом Bluetooth с низким энергопотреблением копирует протоков IEEE 802.14.5, на котором основана спецификация ZigBee. Один из существенных недостатков, ограничивающих использование Bluetooth в области сенсорных сетей — это отсутствие четкой специфицированной схемы для построения сложных топологий сети, требующих ретрансляции данных. То есть спецификация определяет способ построение топологии «звезда» и не более того. Данное обстоятельство не позволяет использовать Bluetooth без применения протоколов более высокого уровня для построения масштабных сенсорных сетей.
Стек устройства ZigBee соответствует двум спецификациям. Физический и канальный уровень описывается стандартом IEEE 802.15.4, а сетевой и прикладной уровни — спецификацией ZigBee. Спецификация ZigBee ориентирована на приложения, требующие гарантированной безопасной передачи данных при относительно небольших скоростях и возможности длительной работы сетевых устройств от автономных источников питания.
Основная особенность технологии ZigBee заключается в том, что она при малом энергопотреблении поддерживает не только простые топологии сети («точка-точка», «дерево» и «звезда»), но и самоорганизующуюся и самовосстанавливающуюся ячеистую (mesh) топологию с ретрансляцией и маршрутизацией сообщений. Кроме того, спецификация ZigBee содержит возможность выбора алгоритма маршрутизации, в зависимости от требований приложения и состояния сети, механизм стандартизации приложений — профили приложений, библиотека стандартных кластеров, конечные точки, привязки, гибкий механизм безопасности, а также обеспечивает простоту развертывания, обслуживания и модернизации. Применение сетей ZigBee в Российской Федерации в частотном диапазоне 2,405-2,485 ГГц не требует получения частотных разрешений и дополнительных согласований. Эти обстоятельства делают ZigBee единственным подходящим кандидатом для использования в области сенсорных сетей.
Принцип работы протокола канального уровня
Дискретно-событийное моделирование используется для построения модели, отражающей развитие системы во времени, когда состояния переменных меняются мгновенно в конкретные моменты времени. В такие моменты времени происходят события, при этом событие определятся как мгновенное возникновение, которое может изменить состояние системы.
Динамическая природа дискретно-событийных имитационных моделей требует, чтобы мы следили за текущим значением имитационного времени по мере функционирования имитационной модели. Необходим также механизм для продвижения имитационного времени от одного значения к другому. В имитационной модели переменная, обеспечивающая текущее значение модельного времени, называется часами модельного времени.
Есть два основных подхода к продвижению модельного времени: продвижение времени от события к событию и продвижение времени с постоянным шагом. Большинство существующих пакетов программ для дискретно-событийного моделирования использует первый подход.
Согласно [31] дискретно-событийные имитационные модели, использующие механизм продвижения времени от события к событию, включают ряд общих компонентов: состояние системы — совокупность переменных состояния, необходимых для описания системы в определенный момент времени; часы модельного времени — переменная, указывающая текущее значение модельного времени; список событий — список, содержащий время возникновения каждого последующего типа событий; статистические счетчики — переменные, предназначенные для хранения статистической информации о характеристике системы; программа инициализации — подпрограмма, устанавливающая в исходное состояние имитационную модель в момент времени, равный 0; синхронизирующая программа — подпрограмма, которая отыскивает следующее событие в списке событий и затем переводит часы модельного времени на время возникновения этого события; программа обработки событий — подпрограмма, обновляющая состояние системы, когда происходит событие определенного типа (для каждого типа событий существует отдельная программа обработки событий); библиотечные программы — набор подпрограмм, применяемых для генерации случайных наблюдений из распределений вероятностей, которые были определены как часть имитационной модели; генератор отчетов — подпрограмма, которая считывает оценки (со статистических счетчиков) критериев оценки работы и выдает отчет по окончании моделирования; основная программа — подпрограмма, которая вызывает синхронизирующую программу, для того чтобы определить следующее событие, а затем передаёт управление соответствующей событийной программе с целью обеспечения заданного обновления состояния системы. Основная программа может также контролировать необходимость прекращения моделирования и вызывать генератор отчетов по его окончании.
Моделирование сетей связи
Особенность имитационного моделирования сетей связи заключается в наличии большого числа независимых моделируемых объектов — узлов, которые имеют внутреннее состояние и могут создавать события, влияющие на состояния других устройств.
Наиболее распространённый способ моделирования сетей связи — это пакетное моделирование. За неделимую единицу информации, которая может быть передана между двумя моделируемыми устройствами, принимается пакет данных. Причём рассматривается каждый пакет данных. Как правило, моделируются только заголовки пакетов и длина данных, сами данные содержащиеся в пакете, очевидно, не моделируются. Пакеты данных напрямую связаны с событиями: событие получения пакета, событие отправки пакеты данных. Каждый узел, сам по себе, является сложной системой, состоящей из нескольких подсистем. Согласно модели OSI, описывающей взаимодействие открытых систем, существует семь уровней протоколов взаимодействия: прикладной, представительский, сеансовый, транспортный, сетевой, канальный и физический.
Прикладной уровень — верхний уровень модели, обеспечивающий взаимодействие пользовательских приложений с сетью.
Представительский уровень обеспечивает преобразование протоколов и шифрование/дешифрование данных. Запросы приложений, полученные с прикладного уровня, на уровне представления преобразуются в формат для передачи по сети, а полученные из сети данные преобразуются в формат приложений. На этом уровне может осуществляться сжатие/распаковка или кодирование/декодирование данных, а также перенаправление запросов другому сетевому ресурсу, если они не могут быть обработаны локально.
Сеансовый уровень модели обеспечивает поддержание сеанса связи, позволяя приложениям взаимодействовать между собой длительное время. Уровень управляет созданием/завершением сеанса, обменом информацией, синхронизацией задач, определением права на передачу данных и поддержанием сеанса в периоды неактивности приложений.
Транспортный уровень модели предназначен для обеспечения надёжной передачи данных через виртуальный поток от отправителя к получателю. При этом уровень надёжности может варьироваться в широких пределах. Протокол транспортного уровня может также обеспечивать управление характеристиками потока, такими как, например, скорость передачи данных.
Сетевой уровень модели предназначен для определения пути передачи данных. Протокол данного уровня отвечает за трансляцию логических адресов в физические, определение маршрутов, коммутацию и отслеживание неполадок в сети. Протоколы сетевого уровня маршрутизируют данные от источника к получателю. Работающие на этом уровне устройства называют маршрутизаторами. Канальный уровень предназначен для обеспечения взаимодействия сетей на физическом уровне и контроля за ошибками, которые могут возникнуть. Полученные с физического уровня данные он упаковывает в кадры, проверяет на целостность, если нужно, исправляет ошибки (формирует повторный запрос поврежденного кадра) и отправляет на сетевой уровень. Канальный уровень может взаимодействовать с одним или несколькими физическими уровнями, контролируя и управляя этим взаимодействием.
Физический уровень — нижний уровень модели, предназначенный непосредственно для передачи потока данных. Осуществляет передачу электрических или оптических сигналов в кабель или в радиоэфир и, соответственно, их приём и преобразование в биты данных в соответствии с методами кодирования цифровых сигналов.
Дискретно-событийное моделирование
Для управления сенсорной сетью в соответствии с вышеописанным алгоритмом требуется механизм определения момента переключения сети на очередную топологию, а также механизм выбора этой топологии из списка возможных топологий. Переключения не должны быть частыми, так как в переходный период время доставки пакетов от некоторых узлов может значительно увеличиваться, поскольку все узлы входят в режим высокого энергопотребления для сканирования сети. Для принятия решения координатор использует имеющуюся информацию о текущем состоянии батарей устройств.
Возможный оптимальный алгоритм переключения топологий может выполнять циклическую смену топологий Тт, где m = m(t) — текущий номер топологии — есть функция времени. Один цикл включает последовательное переключение всех доступных топологий, начиная с т = 1 и заканчивая т = М. Причём времена пребывания 9т в каждой из топологий различны и их сумма составляет общую длительность цикла
В целях исследования поведения системы на всём интервале жизни сети, при выполнении условий BI«: 0 «с Т, где Т — время жизни сети, можно абстрагироваться от дискретной природы событий переключения. Можно сказать, что каждая топология получает свою долю времени wm =0m/&, а средняя сила тока на всех координаторах входящих в набор Rm определяется по формуле
Оптимальный алгоритм выбора долей времени основан на следующем наблюдение. Каждый набор маршрутизаторов содержит одно устройство лимитирующее возможность применения всего набора. В предположении, что средняя сила тока всех маршрутизаторов набора одинакова. Лимитирующее устройство обладает наименьшим запасом энергии q m = min qt и выходит из строя первым. Существует другая возможность. Может существовать конечное устройство не входящее ни в один из наборов Rm, которое разряжается до выхода из строя лимитирующих устройств. В этом случае сеть продолжает нормальную работу без данного устройства, так как оно не выполняло роли маршрутизатора.
Возможность выбора долей времени используется для того чтобы расходовать энергию каждого лимитирующего устройства пропорционально запасу энергии Таким образом, можно добиться равномерной разрядки батарей и практически одновременного их выключения. Подставив (5.7) в (5.9) и, учитывая (5.8), получим систему /77 + 1 уравнений для вычисления оптимальных долей времени
Выражение (5.11) показывает, что решение действительно является оптимальным. Поскольку IR + IE(M-l) есть суммарный средний ток всех лимитирующих устройств, a общий заряд их батарей, то получается, что Т определяется как время необходимое для разрядки батарей всех лимитирующих устройств.
Однако данное аналитическое решение не учитывает, что частые переключения могут потреблять значительную долю энергии, поскольку узлы входят в режим сканирования сети и должны продолжительное время прослушивать эфир в поисках нового родительского узла. Подробное описание переходного процесса дано в следующем разделе. Процесс перехода сети к новой топологии сложен, но здесь достаточно сделать оценку средней силы тока устройств в переходный момент 1Т и оценку длительности перестроения вт . Чтобы избавиться от дискретности событий переключения, вычислим долю времени wT, затрачиваемую на переходные процессы, по формуле
Воспользовавшись уравнениями (5.7) и (5.12), и сделав необходимые преобразования, получим систему разрешимую относительно q m Полученная система является автономной и нелинейной, поэтому для ещё решения разработан новый эффективный численный метод высокого порядка точности, основанный на использовании продолженных систем обыкновенных дифференциальных уравнений (ОДУ) [13]. В случае задачи Коши для общей системы нелинейных уравнений где r = 0, если / явно не зависит от t, т.е. в случае автономной системы. Увеличивая дальше размерность вектора w (т.е. вычисляя в точках t = t" не только и, ut = /, но и йи - df I dt + д/1 дй f и т.д.), этот процесс можно продолжить (конечно, если /задается аналитически и соответствующие производные от / не очень громоздки) и таким образом получить нужную точность вычисления вектора и исходной системы (5.16). Получившийся метод, как и метод Рунге-Кутты, будет явным и одношаговым, но в отличие от него не требует многократных вычислений правой части / в промежуточных точках t" t t"+ , которые потом не используются при переходе к новой точке. 5.2.3. Модификация протоколов канального и сетевого уровней
Для реализации вышеописанной идеи требуется централизованное управление распределением ролей. Эту задачу решает координатор. При этом ему необходимы полные данные о графе G.
Для получения этих данных после построения в стандартном режиме ZigBee, произвольной топологии сети, включающей все устройства, нужно чтобы каждое устройство в течение хотя бы одного интервала между маяками прослушивало эфир. Поскольку в стандартном режиме ZigBee все устройства посылают маяки, то таким образом будет установлена полная матрица смежности графа G. Остаётся только отправить данные с каждого из узлов на координатор.
После чего на координаторе запускается алгоритм распределения ролей. Он указывает координатору топологию сети, которая должна быть построена.
Дальнейший принцип поведения справедлив как для координатора, так и для любого маршрутизатора, который узнаёт структуру поддерева, за которую он отвечает.
Зная набор адресов А узлов, которые должны быть подчинены маршрутизатору, и набор адресов В своих текущих подчинённых, маршрутизатор делит узлы на 4 категории: узлы из А П В, которые остаются подчинёнными; узлы из А/В, которые необходимо подсоединить к себе; узлы из В/А, с которыми необходимо разорвать соединение; все остальные узлы, которые не следует присоединять к себе.
Далее маршрутизатор разрывает связи с узлами из В/А, при помощи сообщения о переходе сети в режим построения фиксированной топологии. Если узел получает такое сообщение, то он передаёт его своим подчинённым, отсоединяется и начинает сканировать эфир в поисках маяка, в котором указан его адрес.
Задача минимизации времени доставки сообщений координатору
Основной сценарий эксперимента scene.tcl (приведён в приложении 3) содержит описание основных параметров сети, генерирует координаты расположения устройств и осуществляет процедуру развертывания сети. Развертывание сети включает в себя: запуск координатора, поочередный запуск устройств, ожидание их ассоциации с имеющейся топологией, запуск трафика от устройств координатору. Скрипт интерпретируется с помощью ns-2.
Как было указано выше, ns-2 взаимодействует и SNOPT посредством передачи файлов формата DOT, описывающих некоторые графы. Также для визуализации этих графов используется пакет программ Graphviz [53].
Также в результате симуляции создаётся файл два трассировочный файла output.tr и output.nam различных форматов, каждый из них содержит подробное описание происходящих в эксперименте событий. Первый файл используется для машинной обработки и построения гистограмм распределения сообщения по временам их доставки (например, рис. 14 и рис. 17). Второй файл используется для визуального представления событий сети.
Машинную обработку осуществляет программа NSTRAN созданная автором на языке Python. Он выполняет функцию аналогичную программе LOGANALYZER, но работает с другим форматом данных и имеет более широкие возможности: отдельный анализа пакетов каждого из соединений координатор-устройство и вывод статистической информации по каждому из таких соединений (доля потерянных пакетов, среднее, минимальное и максимальное время доставки пакета и количество пакетов). Результаты, полученные с помощью NSTRAN, визуализируются с программой gnuplot [17].
Графическое представление событий записанных в трассировочном файле выполняется программой nam [48], входящей в пакет ns-2.
Автоматизация взаимодействия процессов обеспечивается shell-скриптом, созданным автором. Скрипт осуществляет последовательное выполнение серии экспериментов по вышеописанной схеме. Для каждого эксперимента серии заранее подготавливаются параметры запуска и анализа результатов. Это механизм позволяет проводить достаточно сложные исследования по множеству параметров и сделал возможным получение результатов приводимых в следующем разделе (рис. 18, табл. 12).
Ниже представлены результаты ряда экспериментов по изучению работы оптимизационных алгоритмов, проведенных с помощью стенда сети. Целью этих экспериментов являлось измерение энергопотребления и времени доставки сообщений.
В основу экспериментальных измерений положен тот факт, что имея экспериментально установленные осциллограммы суперфреймов устройств можно измерить энергопотребление устройства за один собственный суперфрейм и один родительский суперфрейм. А также исследовать, как эти энергопотребления зависят от событий, происходящих во время соответствующих суперфреймов.
Необходимо было получить осциллограммы и вычислить площадь под ними для следующих типов суперфреймов: 1. Пустой родительский суперфрейм (предполагаем, что он одинаковый для конечных устройств и маршрутизаторов). 2. Пустой собственный суперфрейм маршрутизатора. 3. Родительский суперфрейм с передачей одного типичного сообщения (предполагаем, что он одинаковый для конечных устройств и маршрутизаторов). 4. Собственный суперфрейм маршрутизатора, получающего одно типичное сообщение. 5. Родительский суперфрейм с получением одного типичного сообщения (предполагаем, что он одинаковый для конечных устройств и маршрутизаторов). 6. Собственный суперфрейм маршрутизатора, отправляющего одно типичное сообщение.
Для определения погрешностей делалось несколько замеров для каждого типа. Измеренные осциллограммы энергопотребления устройств, показаны для пустого суперфрейма на рис. 10 (сверху) и суперфрейма в течение которого происходит передача пакета родительским узлом и его прием на дочернем на рис. 10 (снизу).
Похожие диссертации на Оптимизация работы маломощной беспроводной сенсорной сети на базе её имитационной модели
-
