Оптимизация работы маломощной беспроводной сенсорной сети на базе её имитационной модели тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Трифонов, Сергей Владимирович

• Трифонов, Сергей Владимирович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Трифонов, Сергей Владимирович

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Оптимизация работы маломощной беспроводной сенсорной сети на базе её имитационной модели»

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

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

Однако имитационное моделирование не может учесть всех аспектов реальной моделируемой системы. Всегда вводятся предположения, позволяющие упростить и, как следствие, ускорить вычислительный расчёт. Но интуитивно понять, какие предположения не повлекут за собой расхождения модели и реальной системы, сложно. Поэтому в данной работе для проверки модели используется стендовое моделирование. Это экспериментирование с небольшой, но реальной системой, позволяющее учесть все аспекты взаимодействия её частей и влияние внешних факторов. После получения результатов такого эксперимента появляется задача их масштабирования и последующего прогнозирования поведения систем больших размеров, а также оптимизации характеристик системы по одному или нескольким параметрам. Для решения этой задачи в данной работе используется открытый пакет программ — дискретно-событийный сетевой симулятор 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. Построены математическая и имитационные (дискретно-событийная, непрерывная) модели беспроводной сенсорной сети.

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

Список литературы диссертационного исследования кандидат физико-математических наук Трифонов, Сергей Владимирович, 2013 год

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

5. Боголюбов А.Н. Основы математического моделирования. 2003, 137 с.

6. Бителева А. Технологии мультимедийного доступа // Журнал «Теле-Спутник» 8(82), август 2002.

7. Ю.Вишневский В.М. Широкополосные беспроводные сети передачи данных. — М.: Техносфера, 2005. — 592 с. — ISBN 5-94836-049-0

8. Кучерявый Е.A. NS-2 как универсальное средство имитационного моделирования сетей связи. Tampere University of Technology, Telecommunications Laboratory, Tampere, Finland.

9. И.Павеловский Ю.Н., Белотелое H.B., Бродский Ю.И. Имитационное моделирование. Изд. «Академия», Москва, 2008.

10. Самарский А. А. Введение в численные методы. 5-е изд., Лань, 2009. — 228 с. — ISBN 978-5-8114-0602-9

11. Al-Karaki J.N., Kamal А.Е. Routing techniques in wireless sensor networks: a survey. IEEE Wireless Communications, vol. 11, no. 6, pp. 6-28, 2004.

12. FIPS Pub 197, Advanced Encryption Standard (AES), Federal Information Processing Standards Publication 197, US Department of Commerce/N.I.S.T, Springfield, Virginia, November 26, 2001.

13. CC2422 Data Sheet 2.4 GHz IEEE 802.15.4 / ZigBee-ready RF Transceiver, Texas Instruments, 2005.

14. Williams Т., Kelley C. gnuplot 4.6 — An Interactive Plotting Program. (http://gnuplot.sourceforge.net/).

15. Banks J., Carson J. S., Nelson B. L., Nicol D. M. Discrete-Event System Simulation, 5th Edition, Prentice Hall, 2009.

16. Bluetooth SIG, Bluetooth Specifications, V1.0, July 1999.

17. Koubaa A., Alves M., Tovar E. Time-Sensitive IEEE 802.15.4 Protocol, chapter of the book "Sensor Networks and Configurations: Fundamentals, Techniques, Platforms, and Experiments". Springer-Verlag, Germany, Jan. 2007.

18. Network Embedded Systems C nesC. (http://nescc.sourceforge.net//

19. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes in C. The Art of Scientific Computing, 2nd Edition. Cambridge University Press, 1992, Chapter 16, P. 707-722.

20. Perkins C., Belding-Royer E., Das S. Ad hoc on-demand distance vector (AODV) routing. US, 2003.

21. Ousterhout J. Scripting: High-level programming for the 21st century. IEEE Computer, March 1998, N31(3), P. 23-30.

22. A3.Santos S.T. Wireless Sensor Network inMonitoring and Control. Federal University of Rio de Janeiro, 2007.

23. Silva I., Guedes L., Vasques F. A New AODV-Based Routing Protocol Adequate for Monitoring Applications in Oil & Gas Production Environments. WFCS 2010, P. 283-292 , 2010.