Введение к работе
Актуальность работы. В настоящее время беспроводные технологии занимают важное место в информационном обществе. Расширение областей их применения стимулирует рост потребностей в построении новых беспроводных систем. Одним из наиболее перспективных направлений является создание систем контроля и мониторинга параметров объектов. Передовая технология в данном направлении - беспроводные сенсорные сети (БСС).
БСС используют для организации низкоскоростных сетей с ячеистой структурой, что позволяет свободно проектировать их топологию в зависимости от требуемой конфигурации системы. Появление новых интегральных технологий стало определяющим фактором при разработке малогабаритной, энергоэффективной и дешевой компонентной базы, что обеспечило переход БСС на уровень востребованного коммерческого продукта.
На протяжении ряда лет мировые аналитические агентства фиксируют рост объема рынка сенсорных сетей. В соответствии с «циклом зрелости» технологий аналитического агентства Gartner на 2012 год беспроводные сенсорные сети преодолели свой «пик активности». На основе этого выявлены слабые стороны технологии, что стимулирует научное сообщество для поиска путей устранения недостатков таких систем. Спрогнозирован длительный период адаптации технологии, что вызвано недостаточным уровнем проработки сетей данного типа и отсутствием средств их проектирования. Спрогнозирована вторая волна инвестирования технологии, которая позволит вывести такие системы на новый уровень и уверенно закрепить их позиции на рынке. В соответствии со статистикой и прогнозами аналитического агентства IDTechEx на 2010-2014 г. зафиксирована тенденция ускорения темпа роста объемов производства компонентной базы и систем на основе данной технологии.
Построение технически сложных и многоразмерных систем мониторинга, состоящих из 100-1000 узлов, невозможно без использования средств вычислительной техники. В связи с этим наиболее значимый вопрос - автоматизация проектирования беспроводных сенсорных сетей.
Применение систем автоматизированного проектирования (САПР) позволяет сократить временные затраты на этапе разработки изделий, повысить качество проектирования и, как следствие, получить более надежные и высокотехнологичные решения в короткие сроки. Однако на данный момент САПР для комплексного анализа и синтеза сенсорных сетей на рынке не представлены.
Отечественная прикладная наука добилась ряда успехов в разработке алгоритмов и средств проектирования БСС. Основы построения БСС изложены в ра-
ботах И. М. Смурыгина, С. С. Баскакова, В. И. Оганова и др.; средства моделирования беспроводных сетей - в работах К. А. Жереб, Ю. Г. Карпова и др.; алгоритмы синтеза структур БСС - в работах В. А. Мочалова, Е. Н. Туруты и др. Основы автоматизации проектирования изложены в работах В. Н. Ильина, Г. Г. Казеннова, И. П. Норенкова, В. П. Корячко, В. Н. Ланцова, И. Е. Жигалова и др. Среди зарубежных исследователей, внесших свой вклад в разработку алгоритмов и средств проектирования сенсорных сетей, следует выделить: М. Алберг, Б. Титзер, Д. К. Ли, Ф. Левис, В. Редди, М. О. Фарук, Т. Кунц, П. Кумар, Д. Эстрин и др. Однако, несмотря на достигнутые успехи в настоящее время еще не сформирован маршрут и методология проектирования БСС, которые могли бы стать основой для построения САПР БСС.
Развитие алгоритмов и средств автоматизации проектирования беспроводных сенсорных сетей, позволяющих сократить время разработки, обеспечить надежность и энергетическую эффективность проектируемых систем - актуальная проблема в области беспроводного мониторинга.
Объект исследования - системы автоматизированного проектирования беспроводных сенсорных сетей, обеспечивающие автоматизацию проектных процедур анализа и синтеза топологических структур и параметров БСС.
Предмет исследования - алгоритмы анализа и синтеза топологических структур и параметров беспроводных сенсорных сетей, средства их моделирования, маршрут проектирования БСС.
Цель работы - развитие алгоритмов и средств автоматизации проектирования беспроводных сенсорных сетей со статической топологией, направленных на сокращение временных затрат на этапе разработки, обеспечение надежности и энергоэффективности проектируемых систем. Для достижения поставленной цели необходимо решить следующие задачи:
-
Создать маршрут проектирования, позволяющий выполнить этап эскизного проектирования и являющийся методической основой для САПР БСС.
-
Разработать и исследовать алгоритмы построения базовой структуры БСС, обеспечивающие минимальную связность сети.
-
Разработать и исследовать алгоритм построения отказоустойчивой структуры БСС, позволяющий сформировать структуру сети с требуемым уровнем надежности.
-
Разработать и исследовать алгоритм построения энергоэффективной структуры и расчета расписания доступа БСС с учетом требований к минимальному времени безотказной работы.
-
Разработать подсистему имитационного моделирования БСС, позволяющую выполнить анализ основных параметров эскизной модели сенсорной сети в
режиме реального времени.
6. Реализовать пакет прикладных программ САПР БСС, обеспечивающих автоматизацию предложенных алгоритмов и маршрута проектирования БСС.
Научная новизна работы. Новые научные результаты, полученные в работе, состоят в следующем:
-
Предложен маршрут проектирования беспроводных сенсорных сетей;
-
Разработаны два алгоритма синтеза базовой структуры сенсорной сети, основанные на алгоритме ^-средних и кривых Гильберта, позволяющие снизить количество задействованных узлов в сравнении с существующими решениями;
-
Разработан алгоритм оптимизации базовой структуры сенсорной сети, направленный на минимизацию количества узлов независимо от применяемого алгоритма синтеза;
-
Разработаны алгоритмы обеспечения надежности и энергетической эффективности сенсорной сети, позволяющие модифицировать структуру и параметры сети с учетом требований к отказоустойчивости системы и времени ее безотказной работы.
-
Предложен подход к имитационному моделированию сенсорных сетей, основанный на представлении сети в виде системы массового обслуживания и позволяющий выполнить анализ параметров проектируемой системы.
Практическая ценность диссертационной работы определяется тем, что применение разработанной системы автоматизированного проектирования беспроводных сенсорных сетей позволит:
-
Создавать эскизные модели сенсорных сетей с отказоустойчивой и энергоэффективной топологической структурой;
-
Сократить временные затраты на этапе разработки эскизных моделей;
-
Выполнять расчет и анализ надежности сенсорных сетей на стадии проектирования;
-
Выполнять расчет времени безотказной работы проектируемых систем при известных параметрах компонентной базы;
-
Выполнять имитационное моделирование эскизных моделей сенсорных сетей в режиме реального времени.
Методы исследования. Для решения поставленных задач в диссертационной работе использованы методы теории САПР, системного анализа, теории графов, теории надежности технических систем, элементы теории вероятностей и математической статистики, вычислительной математики и программирования, методы теории массового обслуживания и имитационное моделирование. Основные положения, выносимые на защиту: 1. Маршрут проектирования беспроводных сенсорных сетей.
-
Алгоритмы синтеза базовой структуры БСС, основанные на использовании алгоритма ^-средних и кривых Гильберта.
-
Алгоритм оптимизации базовой структуры БСС, основанный на использовании алгоритма Дейкстры.
-
Алгоритмы обеспечения надежности и энергоэффективности структуры БСС, основанные на применении алгоритма Эдмондса-Карпа.
-
Подход к имитационному моделированию БСС, основанный на применении системы массового обслуживания.
Реализация и внедрение результатов работы. Работа по теме диссертации проводилась на кафедре «Вычислительная техника» ВлГУ в Центре микроэлектронного проектирования и обучения в рамках г/б НИР, проекта № 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.
Публикации по работе. Основные результаты диссертационной работы опубликованы в 3 статьях в изданиях, рекомендованных Высшей аттестационной комиссией РФ. Общее число публикаций по теме диссертации составляет 11.
Структура работы. Диссертация состоит из введения, четырех глав с выводами по каждой из них, заключения, списка сокращений и условных обозначений, списка использованных источников и приложения. Основная часть диссертации изложена на 146 страницах машинописного текста. Работа содержит 50 рисунков, 37 таблиц. Библиография включает 115 наименований.
