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

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

КИСЛЯКОВ Максим Андреевич

АЛГОРИТМЫ И СРЕДСТВА АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ СО СТАТИЧЕСКОЙ ТОПОЛОГИЕЙ

Специальность 05.13.12 - Системы автоматизации проектирования (промышленность)

г 9 ноя 2013

Автореферат диссертации на соискание ученой степени кандидата технических наук

Владимир 2013

005540586

005540586

Работа выполнена на кафедре «Вычислительная техника» в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования (ФГБОУ ВПО) «Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых» (ВлГУ).

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

Официальные оппоненты

Ведущая организация

Мосин Сергей Геннадьевич, кандидат технических наук, доцент, доцент кафедры «Вычислительная техника» ВлГУ, г. Владимир.

Крылов Владимир Владимирович, доктор технических наук, профессор, профессор института радиоэлектроники и информационных технологий ФГБОУ ВПО «Нижегородский государственный технический университет им. P.E. Алексеева», г. Н. Новгород.

Руфицкий Михаил Всеволодович, доктор технических наук, профессор, профессор кафедры «Физика и прикладная математика» ВлГУ, г. Владимир.

ФГБОУ ВПО «Рязанский государственный радиотехнический университет», г. Рязань.

Защита состоится « 11 » декабря 2013 г. в 15 часов 30 минут на заседании диссертационного совета Д 212.025.01 при ВлГУ по адресу: 600000, г. Владимир, ул. Горького, 87, ауд. 335-1.

С диссертацией можно ознакомиться в научной библиотеке ВлГУ. Автореферат диссертации размещен на сайте ВАК vak.ed.gov.ru.

Автореферат разослан «11» ноября 2013 г.

Отзывы на автореферат в двух экземплярах, заверенных печатью, просим направлять по адресу университета: 600000, г. Владимир, ул. Горького, 87, ВлГУ, ученому секретарю диссертационного совета Д 212.025.01.

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

диссертационного совета Л .

д.т.н., доцент ¿рУ Н. Н. Давыдов

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

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

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

На протяжении ряда лет мировые аналитические агентства фиксируют рост объема рынка сенсорных сетей. В соответствии с «циклом зрелости» технологий аналитического агентства Gartner на 20)2 год беспроводные сенсорные сети преодолели свой «пик активности». На основе этого выявлены слабые стороны технологии, что стимулирует научное сообщество для поиска путей устранения недостатков таких систем. Спрогнозирован длительный период адаптации технологии, что вызвано недостаточным уровнем проработки сетей данного типа и отсутствием средств их проектирования. Спрогнозирована вторая волна инвестирования технологии, которая позволит вывести такие системы на новый уровень и уверенно закрепить их позиции на рынке. В соответствии со статистикой и прогнозами аналитического агентства IDTechEx на 2010-2014 г. зафиксирована тенденция ускорения темпа роста объемов производства компонентной базы и систем на основе данной технологии.

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

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

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

ботах И. М. Смурыгина, С. С. Баскакова, В. И. Оганова и др.; средства моделирования беспроводных сетей - в работах К. А. Жереб, Ю. Г. Карпова и др.; алгоритмы сшгтеза структур БСС - в работах В. Л. Мочалова, Е. Н. Туруты и др. Основы автоматизации проектирования изложены в работах В. Н. Ильина, Г. Г. Казеннова, И. П. Норенкова, В. П. Корячко, В. Н. Ланцова, И. Е. Жигалова и др. Среди зарубежных исследователей, внесших свой вклад в разработку алгоритмов и средств проектирования сенсорных сетей, следует выделить: М. Алберг, Б. Титзер, Д. К. Ли, Ф. Левис, В. Редди, М О. Фарук, Т. Кунц, П. Кумар, Д. Эс грин и др. Однако, несмотря на достигнутые успехи в настоящее время еще не сформирован маршрут и методология проектирования БСС, которые могли бы стать основой для построения САПР БСС.

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

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

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

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

1. Создать маршрут проектирования, позволяющий выполнить этап эскизного проектирования и являющийся методической основой для САПР БСС.

2. Разработать и исследовать алгоритмы построения базовой структуры БСС, обеспечивающие минимальную связность сети.

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

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

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

режиме реального времени.

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

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

1. Предложен маршрут проектирования беспроводных сенсорных сетей;

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

3. Разработан алгоритм оптимизации базовой структуры сенсорной сети, направленный на минимизацию количества узлов независимо от применяемого алгоритма синтеза;

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

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

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

1. Создавать эскизные модели сенсорных сетей с отказоустойчивой и энергоэффективной топологической структурой;

2. Сократить временные затраты на этапе разработки эскизных моделей;

3. Выполнять расчет и анализ надежности сенсорных сетей на стадии проектирования;

4. Выполнять расчет времени безотказной работы проектируемых систем при известных параметрах компонентной базы;

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

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

Основные положения, выносимые на защиту:

1. Маршрут проектирования беспроводных сенсорных сетей.

2. Алгоритмы синтеза базовой структуры БСС, основанные на использовании алгоритма ^-средних и кривых Гильберта.

3. Алгоритм оптимизации базовой структуры БСС, основанный на использовании алгоритма Дейкстры.

4. Алгоритмы обеспечения надежности и энергоэффективности структуры БСС, основанные на применении алгоритма Эдмондса-Карпа.

5. Подход к имитационному моделированию БСС, основанный на применении системы массового обслуживания.

Реализация и внедрение результатов работы. Работа по теме диссертации проводилась на кафедре «Вычислительная техника» ВлГУ в Центре микроэлектронного проектирования и обучения в рамках г/б НИР, проекта № 2973 аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009-2010)», проекта № 7.4151.2011 государственного задания Министерства образования и науки РФ. Полученные результаты исследований в виде методологии, моделей, алгоритмов, программного обеспечения САПР беспроводных сенсорных сетей внедрены в практическую деятельность коммерческих организаций ООО «Компания «Системный подход» (г. Владимир), ЗАО «ТехКрайт» (г. Владимир) и в научную деятельность Лаборатории ЦОСП ВлГУ, что подтверждено соответствующими актами внедрения.

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на следующих семинарах и конференциях: международная научно-техническая конференция «Информационные системы и технологии», Н. Новгород: 2010; международная научно-техническая конференция «Информационные управляющие системы и компьютерный мониторинг», Донецк: 2010; международная научно-техническая конференция «Физика и радиоэлектроника в медицине и экологии», Владимир-Суздаль: 2010; международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск: 2010, 2012, 2013; the 6,ь Spring/Summer Young Researchers' Colloquium on Software Engineering, Perm: 2012; международная научно-практическая конференция «Наука в современном информационном обществе», Москва: 2013.

Публикации по работе. Основные результаты диссертационной работы опубликованы в 3 статьях в изданиях, рекомендованных Высшей аттестационной комиссией РФ. Общее число публикаций по теме диссертации составляет 11.

Структура работы. Диссертация состоит из введения, четырех глав с выводами по каждой из них, заключения, списка сокращений и условных обозначений, списка использованных источников и приложения. Основная часть диссертации изложена на 146 страницах машинописного текста. Работа содержит 50 рисунков, 37 таблиц. Библиография включает 115 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе диссертации проведен анализ предметной области беспроводных сенсорных сетей и исследованы тенденции развития технологии в период с 1950 по 2010 гг. Определены структура и состав узла сенсорной сети. Параметры компонентов узла являются входными данными при проектировании БСС. Проведена классификация узлов БСС по назначению: оконечный узел (О-узел), узел-ретранслятор (М-узел) и узел-координатор (К-узел). Отмечена обширность сферы применения БСС.

Выполнен анализ аппаратного обеспечения БСС. Установлено, что на данный момент разработано два стандарта: IEEE 802.15.4 и ZigBee. Показано, что для обеспечения унификации процесса проектирования БСС необходимо использовать параметры двух уровней PHYn MAC сетевой модели OS/.

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

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

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

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

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

Рисунок 1 - Составные части системы САПР БСС

Предложен маршрут проектирования БСС и выделено семь проектных процедур (рисунок 2). Начальные требования к БСС представлены множеством Х1п = {ТС,ХС,5С,0С}, где Тс - время безотказной работы, Хс - зона покрытия,

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

Тс -ттип(2^,), ^ = {^1,...,^}, =

М

где / = {!,...,«} - порядковый номер узла БСС, /да- - длительность одного периода работы узла в у-ом режиме, тр] - число периодов для /-го узла в у-ом режиме.

Выделено шесть режимов узла БСС: сон, ожидание, съем, прием, передача и обработка данных. Зона покрытая определена пространственным расположением О-узлов и представлена тремя векторами координат X, У и 2. Параметр скорости передачи данных определяет максимальную скорость потока, генерируемого О-узлом КСС. Параметр уровня надежности равен вероятности безотказной работы сети, рассчитьюаемой с использованием значений Ру - вероятность отказа узла, Ре - вероятность отказа канала связи.

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

Процедуру синтеза базовой структуры БСС в работе предложено выполнять с использованием четырех алгоритмов: алгоритм линейного размещения М-узлов (БС1), алгоритм цепного размещения М-узлов (БС2), алгоритм группового размещения М-узлов с использованием алгоритма ¿-средних (БСЗ) и алгоритм группового размещения М-узлов с применением кривых Гильберта (БС4). Два последних алгоритма предложены автором.

Для выполнения синтеза сенсорную сеть представляют в виде графа С-(У,Е), где V — узлы БСС, Е- связи между узлами. Множество V = {Уа,Ук,Ут), где Уа - множество О-узлов, Ук - множество К-узлов, Ут - множество М-узлов. Наборы Уа и Ук определены зоной покрытия Xс. Множества Ут и Е изначально пустые. Цель процедуры синтеза - сформировать такие множества ¥т и Е, чтобы обеспечить минимальную связность сети.

При линейном размещении М-узлов (БС1) обеспечивается связность для каждой пары О-узел-К-узел независимо от структуры БСС. По прямой линии между О-узлом и К-узлом устанавливают М-узлы с учетом радиусов их действия. При цепном размещении М-узлов (БС2) обеспечивается связность для каждой па-

Обслуживающая подсистема обработки входных и выходных данных

Проектирующая подсистема структурного и параметрического синтеза БСС

Проектирующая подсистема моделирования БСС

Обслуживающая подсистема обработки входных и выходных данных

Рисунок 2 - Маршрут проектирования БСС

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

Алгоритм группового размещения (БСЗ) заключается в предварительном выделении групп О-узлов, расположенных рядом. При этом задача сводится к кластеризации узлов сети из множества У0. В работе кластеризацию узлов предложено выполнять с применением алгоритма к-средних, который позволяет выделить группы с минимальным квадратичным отклонением между узлами каждого кластера и его центром. В результате итерационного выполнения алгоритма происходит перераспределение узлов сети и расчет координат центров кластеров /и,-. Критерий оптимизации выражен следующими формулами.

где к - количество кластеров, - вектор индексов О-узлов, принадлежащих кластеру /, от, = (х„Л,ут1,гт1) - центр / -го кластера.

В алгоритме группового размещения (БС4) предложен альтернативный способ кластеризации БСС, основанный на применении кривых Гильберта. Особенность кривых Гильберта - обеспечение минимального расстояния между точками в «-мерном пространстве при близости их проекций на кривой. Пространство разделяют на зоны, являющиеся потенциальными кластерами. Принадлежность узла г к кластеру у предложено определять на основе следующего выражения:

где с= {су,...,ск} - кривая Гильберта, Ус ={у£.1,...,устг} - множество проекций вершин графа на кривую, п - количество О-узлов, к — количество кластеров. Связность центров кластеров в алгоритмах БСЗ и БС4 обеспечивается на основе применеття алгоритма БС2.

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

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

к

X -ипт, хш

'«И1.---»«}» ..,*:}

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

'¡«А А-1

где - множество длин независимых путей между / -ым О-узлом и К-узлом. Если расчетное значение вероятности не удовлетворяет начальному требованию ()с, то на основе незадействованных и новых М-узлов выполняется построение дополнительных независимых путей в графе.

Энергетическую эффективность БСС предложено обеспечивать с использованием алгоритма синтеза энергоэффективной структуры БСС (ЭЭ), основанного на поиске независимых путей с применением алгоритма Эдмондса-Карпа. Для каждого М-узла устанавливается значение потока передаваемых данных. При построении НП потоки задействованных М-узлов увеличивают. Если поток превышает максимально допустимое значение 5ГС, то на основе незадействованных и новых М-узлов выполняют построение дополнительных путей в графе. Методика расчета энергетической эффективности БСС основана па анализе пропускной способности узла с использованием следующего выражения.

гс Гс(54+55+0.3-56-2.3-5,) где Р - емкость батареи, {5,1,54,55,56} - значения токов потребления в соответствующих режимах работы, 5Г - пропускная способность канала.

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

На последней стадии маршрута проектирования формируется проект эскизной модели БСС, включающий координаты М-узлов и временные интервалы доступа к среде.

В третьей главе диссертации представлено информационное и программное обеспечение САПР БСС. Программное обеспечение реализовано в виде пакета прикладных программ сложной структуры в системе МАТЬАВ (рисунок 3).

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

Рисунок 3 - Структура программных модулей САПР БСС

Проведены исследования предложенных алгоритмов автоматизации проектирования БСС. Эксперименты проводились на тестовой задаче: на объекте квадратной формы случайным образом размещались О-узлы. Длина стороны - 400 м., радиус действия О-узлов - 15 м., М-узлов -30 м. Количество выборок - 50. Оценка результатов синтеза базовой структуры БСС с учетом оптимизации в двумерном режиме показала эффективность применения алгоритмов БСЗ и БС4, которые обеспечивают снижение количества М-узлов БСС на 72% в сравнении с алгоритмом БС1 и на 68% в сравнении с алгоритмом БС2 (при плотности размещения 6,3 ■ 1СГ3 уз/м2). Оценка результатов синтеза базовой структуры БСС с учетом оптимизации в трехмерном режиме показала эффективность применения алгоритмов БС2 и БСЗ, которые позволяют сократить количество М-узлов БСС на 35% в сравнении с алгоритмом БС1 и на 8% в сравнении с алгоритмом БС4 (при плотности размещения 1,55 ■ 10~5 уз/м3).

Выполнено исследование программной модели обеспечения надежности БСС. Установлено, что в двумерном режиме при выполнении алгоритма ОТС размещается равное количество М-узлов независимо от применяемого алгоритма синтеза БСЗ и БС4. При использовании алгоритма БСЗ зафиксировано снижение времени выполнения процедуры на 12%. В трехмерном режиме количество до-

бавлснных М-узлов и время выполнения процедуры равны независимо от алгоритма синтеза БС2 и БСЗ. Степень увеличения количества узлов — в 2,3-2,5 раза.

Выполнено исследование программных моделей обеспечения эиергоэффек-тивности БСС. Установлено, что в двумерном режиме алгоритм ЭЭ при использовании алгоритма БСЗ позволяет сократить количество М-узлов на 7% и время выполнения - в 2 раза в сравнении с алгоритмом БС4. В трехмерном режиме обеспечение энергоэффективности БСС следует выполнять с первоначальным синтезом базовой структуры на основе алгоритма БСЗ, что позволяет сократить количество М-узлов на 7% в сравнении с алгоритмом БС2. Степень увеличения количества М-узлов - на 5-21%.

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

В четвертой главе приведены экспериментальные результаты использования разработанной системы автоматизированного проектирования беспроводных сенсорных сетей на примере системы беспроводного мониторинга климата серверных помещений компании ООО «Владимир КЭТИС» (С,1) и системы беспроводного мониторинга состояния промышленного оборудования производственного цеха строительных металлоконструкций (С2) г. Первоуральск.

Построены эскизные модели систем С1 и С2. Экспериментально подтверждена эффективность применения САПР БСС, которая позволила сократить временные затраты на этапе разработки в 126 и 360 раз в сравнении с проектированием БСС без использования автоматизированных средств. Отмечены трудоемкость и высокие квалификационные требования к персоналу при построении эскизных моделей без использования предложенной САПР.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО РАБОТЕ

Статьи в изданиях, рекомендованных ВАК:

1. Кисляков, М. А. Проектирование беспроводных сенсорных сетей [Текст] / М. А. Кисляков, С. Г. Мосин, В. В. Савенкова // Приборостроение. - 2012. - №8. -С. 15-18 (соискатель - 75%).

2. Кисляков, М. А. Применение кривых Гильберта для решения задачи кластеризации топологии сенсорной сети [Текст] / М. А. Кисляков, С. Г. Мосин // Научно-технический вестник Поволжья.- 2013. - №1. - С. 213-216 (соискатель - 85%).

3. Кисляков, М. А. Автоматизированный синтез отказоустойчивой структуры беспроводной сенсорной сети [Текст] / М. А. Кисляков, С. Г. Мосин // Проектирование и технология электронных средств. - 2013. - №3. - С. 25-29 (соискатель -85%).

Статьи в сборниках и трудах конференций:

4. Кисляков, М. А. Методы обеспечения начальной синхронизации беспроводных сенсорных сетей [Текст] / М. А. Кисляков // Материалы 1-ой межд. науч,-техн. конференции «информационные управляющие системы и компьютерный мониторинг». - Донецк, 2010. - С. 81-82.

5. Кисляков, M. А. Модель взаимодействия узлов беспроводной сенсорной сети [Текст] / М. А. Кисляков // Материалы 16-ой межд. науч.-техн. конференции «Информационные системы и технологии». — Н. Новгород, 2010. - С. 108.

6. Кисляков, М. А. Синхронизация беспроводной сенсорной сети на основе метода вероятностного доступа [Текст] / М. А. Кисляков // Материалы 9-ой межд. науч.-техн. конференции «Физика и радиоэлектроника в медицине и экологии». — Владимир-Суздаль, 2010. - С. 381-383.

7. Кисляков, М. А. Сравнительная характеристика методов синхронизации беспроводных сенсорных сетей [Текст] / М. А. Кисляков // Материалы 48-ой межд. науч. студ. конференции «Студент и научно-технический прогресс»: Информационные технологии. - Новосиб. гос. ун-т. Новосибирск, 2010. - С. 59.

8. Кисляков, М. А. Классификация беспроводных сенсорных сетей по типу топологической структуры [Текст] / М. А. Кисляков, В. В. Савенкова // Материалы

50-ой межд. науч. студ. конференции «Студент и научно-технический прогресс»: Информационные технологии. - Новосиб. гос. ун-т. Новосибирск, 2012. - С. 40 (соискатель - 75%).

9. Kislyakov, M. Formalization of Initial Requirements for the Design of Wireless Sensor Networks [Text] / M. Kislyakov, S. Mosin // Proceedings of the 6th Spring/Summer Young Researchers Colloquium on Software Engineering. — Perm, Russia, 2012. - P. 119-121 (aspirant - 70%).

10. Кисляков, M. А. Метод построения базовой структуры сенсорной сети с применением алгоритма A-средних [Текст] / М. А. Кисляков // Материалы межд. науч.-прак. конференции «Наука в современном информационном обществе». — Москва, 2013.-С. 120-121.

11. Кисляков, М. А. Подход к автоматизации процесса проектирования беспроводных сенсорных сетей [Текст] / М. А. Кисляков, В. В. Савенкова // Материалы

51-ой межд. науч. студ. конференции «Студент и научно-технический прогресс»: Информационные технологии. - Новосиб. гос. ун-т. Новосибирск, 2013. - С. 176 (соискатель - 85%).

Подписано в печать 07.11.13 Формат 60x84/16. Бумага для множит, техники. Гарнитура Тайме. Печать на ризографе. Усл. печ. л. 0,93. Тираж 100 экз.

Издательство ООО «Печатный Двор» 600001, Владимир, ул. Студеная гора, д.34, офис 705.

Тел. (4922) 44-31-52, (4922) 44-31-62

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых»

АЛГОРИТМЫ И СРЕДСТВА АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ СО СТАТИЧЕСКОЙ ТОПОЛОГИЕЙ

Специальность 05.13.12 - Системы автоматизации проектирования

(промышленность)

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

Научный руководитель: кандидат технических наук, доцент Мосин Сергей Геннадьевич

Владимир 2013

/

СОДЕРЖАНИЕ

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

ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ. ПРОБЛЕМЫ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ............10

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

1.1.1. Тенденции развития БСС ............................................................................11

1.1.2. Состав и структура БСС ..............................................................................13

1.1.3. Области применения БСС ...........................................................................15

1.2. Аппаратное обеспечение беспроводных сенсорных сетей............................16

1.3. Программное обеспечение беспроводных сенсорных сетей.........................20

1.3.1. Операционные системы БСС ......................................................................20

1.3.2. Средства моделирования БСС ....................................................................24

1.4. Актуальность и проблемы автоматизации проектирования БСС.................29

1.5. Постановка цели и задач работы ......................................................................32

1.6. Выводы ................................................................................................................33

ГЛАВА 2. СТРУКТУРА САПР БСС. МАТЕМАТИЧЕСКОЕ И МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ...........................................................................................................35

2.1. САПР и жизненный цикл БСС .........................................................................36

2.2. Состав и структура САПР БСС ........................................................................38

2.2.1. Подсистемы САПР БСС ..............................................................................39

2.2.2. Виды обеспечений САПР БСС ...................................................................41

2.2.3. Уровни проектирования БСС .....................................................................43

2.3. Маршрут проектирования БСС ........................................................................44

2.3.1. Формализация начальных требований к БСС...........................................46

2.3.2. Определение параметров компонентной базы БСС.................................51

2.3.3. Синтез базовой структуры БСС..................................................................54

2.3.4. Обеспечение надежности БСС ...................................................................67

2.3.5. Обеспечение энергоэффективности БСС ..................................................73

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

2.3.7. Формирование проекта эскизной модели БСС.........................................81

2.4. Выводы ................................................................................................................84

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

3.1. Программное обеспечение САПР БСС............................................................86

3.2. Информационное обеспечение САПР БСС.....................................................94

3.3.1. Представление эскизной модели БСС .......................................................94

3.2.2. Библиотеки САПР БСС ...............................................................................97

3.3. Исследование программных моделей САПР БСС .........................................98

3.3.1. Характеристики алгоритмов синтеза базовой структуры БСС...............98

3.3.2. Результаты обеспечения надежности БСС..............................................106

3.3.3. Результаты обеспечения энергоэффективности БСС ............................110

3.3.4. Результаты моделирования эскизной модели БСС ................................114

3.4. Выводы..............................................................................................................117

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ ИСПОЛЬЗОВАНИЯ САПР БСС ..............................................................................................................................119

4.1. Система беспроводного мониторинга климата серверных помещений.....119

4.2. Система беспроводного мониторинга состояния промышленного оборудования ..........................................................................................................................127

4.3. Выводы..............................................................................................................131

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

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ..............................134

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

ПРИЛОЖЕНИЕ А.......................................................................................................147

ВВЕДЕНИЕ

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

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

На протяжении ряда лет мировые аналитические агентства фиксируют рост объема рынка сенсорных сетей. В соответствии с «циклом зрелости» технологий аналитического агентства Gartner на 2012 год беспроводные сенсорные сети преодолели свой «пик активности», что позволяет сделать следующие выводы [78]:

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

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

3. Спрогнозирована вторая волна инвестирования технологии, которая позволит вывести такие системы на новый уровень и уверенно закрепить их позиции на рынке.

В соответствии со статистикой и прогнозами аналитического агентства IDTechEx на 2010-2014 гг. зафиксирована тенденция ускорения темпа роста объемов производства компонентной базы и систем на основе технологии БСС [112].

Построение технически сложных и многоразмерных систем мониторинга,

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

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

Отечественная прикладная наука добилась ряда успехов в разработке алгоритмов и средств проектирования БСС. Основы построения БСС изложены в работах И. М. Смурыгина, С. С. Баскакова, В. И. Оганова и др.; средства моделирования беспроводных сетей - в работах К. А. Жереб, Ю. Г. Карпова и др.; алгоритмы синтеза структур БСС - в работах В. А. Мочалова, Е. П. Туруты и др. Основы автоматизации проектирования изложены в работах В. II. Ильина, Г. Г. Казеннова, И. П. Норенкова, В. П. Корячко и др. Среди зарубежных исследователей, внесших свой вклад в разработку алгоритмов и средств проектирования сенсорных сетей, следует выделить: М. Алберг, Б. Титзер, Д. К. Ли, Ф. Левис, В. Редди, М. О. Фарук, Т. Кунц, П. Кумар, Д. Эстрип и др. Однако, несмотря па достигнутые успехи в настоящее время еще не сформирован маршрут и методология проектирования БСС, которые могли бы стать основой для построения САПР БСС.

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

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

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

ния, маршрут проектирования БСС.

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

1. Создание маршрута проектирования, позволяющего выполнить этап эскизного проектирования и являющегося методической основой для САПР БСС.

2. Разработка и исследование алгоритмов построения базовой структуры БСС, обеспечивающих минимальную связность сети.

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

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

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

6. Реализация пакета прикладных программ САПР БСС, обеспечивающих автоматизацию предложенных алгоритмов и маршрута проектирования БСС.

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

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

1. Предложен маршрут проектирования беспроводных сенсорных сетей;

2. Разработаны два алгоритма синтеза базовой структуры сенсорной сети, основанные на алгоритме ^-средних и кривых Гильберта, позволяющие снизить

количество задействованных узлов в сравнении с существующими решениями;

3. Разработан алгоритм оптимизации базовой структуры сенсорной сети, направленный на минимизацию количества узлов независимо от применяемого алгоритма синтеза;

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

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

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

1. Создавать эскизные модели сенсорных сетей с отказоустойчивой и энергоэффективной топологической структурой;

2. Сократить временные затраты на этапе разработки эскизных моделей;

3. Выполнять расчет и анализ надежности сенсорных сетей на стадии проектирования;

4. Выполнять расчет времени безотказной работы проектируемых систем при известных параметрах компонентной базы;

5. Выполнять имитационное моделирование эскизной модели сенсорной сети в режиме реального времени.

Работа по теме диссертации проводилась на кафедре «Вычислительная техника» ВлГУ в Центре микроэлектронного проектирования и обучения в рамках г/б НИР, проекта № 2973 аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009-2010)», проекта № 7.4151.2011 государственного задания Министерства образования и науки РФ. Полученные результаты исследований в виде методологии, моделей, алгоритмов, программного обеспечения САПР беспроводных сенсорных сетей внедрены в практическую

деятельность коммерческих организаций ООО «Компания «Системный подход» (г. Владимир), ЗАО «ТехКрайт» (г. Владимир) и в научную деятельность Лаборатории ЦОСП ВлГУ, что подтверждено соответствующими актами внедрения (Приложение А).

Основные положения и результаты работы докладывались и обсуждались на следующих семинарах и конференциях: международная научно-техническая конференция «Информационные системы и технологии», Н.Новгород: 2010; международная научно-техническая конференция «Информационные управляющие системы и компьютерный мониторинг», Донецк: 2010; международная научно-техническая конференция «Физика и радиоэлектроника в медицине и экологии», Владимир-Суздаль: 2010; международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск: 2010, 2012, 2013; the 6th Spring/Summer Young Researchers' Colloquium on Software Engineering, Perm: 2012; международная научно-практическая конференция «Наука в современном информационном обществе», Москва: 2013.

Основные положения, выносимые на защиту.

1. Маршрут проектирования беспроводных сенсорных сетей.

2. Алгоритмы синтеза базовой структуры БСС, основанные на использовании алгоритма ^-средних и кривых Гильберта.

3. Алгоритм оптимизации базовой структуры БСС, основанный на использовании алгоритма Дейкстры.

4. Алгоритмы обеспечения надежности и энергоэффективности структуры БСС, основанные на применении алгоритма Эдмондса-Карпа.

5. Подход к имитационному моделированию БСС, основанный на применении системы массового обслуживания.

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

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

ванных источников и приложения. Основная часть диссертации изложена на 146 страницах машинописного текста. Работа содержит 50 рисунков, 37 таблиц. Библиография включает 115 наименовании.

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

Во второй главе предложено математическое и методическое обеспечение системы автоматизированного проектирования БСС. Установлено место разрабатываемой САПР в жизненном цикле БСС. Предложен маршрут проектирования сенсорных сетей на этапе эскизного проектирования. Выделены проектные процедуры и предложен математический аппарат в виде набора подходов и алгоритмов проектирования БСС.

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

В четвертой главе представлены экспериментальные результаты использования разработанной системы автоматизированного проектирования беспроводных сенсорных сетей на примере системы беспроводного мониторинга климата серверных помещений компании ООО «Владимир КЭТИС» и системы беспроводного мониторинга состояния промышленного оборудования производственного цеха строительных металлоконструкций г. Первоуральск.

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

ПРОЕКТИРОВАНИЯ

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

Рассмотрено аппаратное обеспечение БСС в соответствии со стандартом IEEE 802.15.4 [79, 80] и спецификацией ZigBee [66, 115]. Выполнена декомпозиция и проведен анализ программного обеспечения сенсорных сетей. Выделено две