Введение к работе
Актуальность темы. На сегодняшний день существует значительное количество прикладных задач, для решения которых необходим контроль состояния большого числа объектов. Особой привлекательностью обладают системы контроля, использующие для передачи сообщений радиоканал. Миниатюризация элементной базы и прогресс технологий связи создали предпосылки для появления особого типа беспроводных систем передачи информации - сенсорных сетей. Как видно из названия, такая сеть состоит из множества автономных элементов - сенсоров. Сенсор включает в себя чувствительный элемент, регистрирующий изменение какого-либо физического параметра среды, блок обработки, приемопередатчик и элемент питания. Важной особенностью сенсорных сетей является то, что каждый сенсор может быть как источником сообщения, так и ретранслятором сообщений, поступающих от других сенсоров. Таким образом, использование сенсорных сетей позволяет передавать информацию на значительное расстояние при малой мощности передатчиков. Конечным пунктом доставки сообщений является базовая станция (БС).
На данный момент сенсорные сети успешно применяются в промышленности, сельском хозяйстве, медицине и во многих других областях.
Существует большое количество приложений, в которых одним из важнейших параметров системы контроля является оперативность доставки сообщений. В сенсорных сетях с циклическим сбором данных оперативность доставки определяется в первую очередь длительностью периода сбора информации (ПСИ). Сложность в организации ПСИ заключается в наличии коллизий - ситуаций, когда несколько сенсоров создают в эфире друг для друга помехи, приводящие к потере сообщения. При возникновении коллизий необходимы повторные передачи, что существенно увеличивает длительность ПСИ. Одним из способов борьбы с коллизиями является введение расписания передач. Расписание составляется таким образом, чтобы не допустить одновременное возникновение мешающих передач. Таким образом задача разработки алгоритмов составления расписания передач, минимизирующих длительность ПСИ, является актуальной.
Целью работы является анализ граничных значений длительности ПСИ для сетей с различной топологией, а так же разработка алгоритмов составления бесконфликтного расписания передач, обеспечивающих минимальную длительность ПСИ.
Задачами диссертационного исследования являются
Анализ нижней границы длительности ПСИ для сети с древовидной топологией.
Разработка алгоритмов составления оптимального расписания передач для сетей с древовидной топологией.
Анализ нижней границы длительности ПСИ для сети с произвольной (недревовидной) топологией.
Разработка алгоритмов составления оптимального расписания передач для сетей с топологией "правильная решетка".
Разработка и анализ подоптимальных алгоритмов составления расписания передач для сетей с различными моделями коллизий.
Методы исследования. Для решения поставленных задач были использованы общие методы системного анализа, комбинаторный анализ, теория дискретной оптимизации, теория графов и методы имитационного моделирования.
Научная новизна диссертационной работы заключается в следующем.
Предложенные оценки длительности ПСИ для сенсорных сетей с древовидной топологией отличаются от известных тем, что применимы для произвольной древовидной сети, а не только для некоторых частных случаев.
Разработанные алгоритмы позволяют составить оптимальное расписание передач для любой сенсорной сети с древовидной топологией, в то время, как существующие алгоритмы позволяют составлять оптимальное расписание передач только для частных случаев древовидной топологии.
Рассчитанные верхние и нижние границы длительности ПСИ для сенсорных сетей с произвольной топологией позволяют осуществлять оценку качества различных алгоритмов составления расписания передач. Показана точность предложенных границ.
Разработанные алгоритмы составления оптимального расписания передач для сенсорных сетей с топологией "правильная решетка" позволяют существенно повысить оперативность сбора информации в таких сетях.
Практическая ценность полученных результатов. Предложенные граничные значения длительности ПСИ позволяют оценить оперативность сенсорной сети еще на этапе ее проектирования, и, как следствие, оценить способность сети выполнять возложенную на нее задачу. Полученные в ходе диссертационной работы алгоритмы позволяют существенно повысить оперативность доставки сообщений, что обосновывает их ценность для высокоскоростных приложений, где оперативность доставки сообщений является ключевым параметром. Предложенные алгоритмы могут служить базовыми при разработке протоколов работы скоростных сенсорных сетей.
Апробация работы. Основные результаты работы докладывались на научно-технических конференциях: X международная конференция для молодых ученых "Wave Electronics and Its Application in the Information and Telecommunication Systems", Научные Сессии ГУАП 2008-2011 гг, международных форумах "Information And Communication Technologies: Problems,
Perspectives - 2008", "Information And Communication Technologies And Higher Education - Priorities of Modern Society Development - 2009", "Modern Information Society Formation - Problems, Perspectives, Innovation Approaches - 2010", "Modern Information Society Formation - Problems, Perspectives, Innovation Approaches - 2011", '16-я Всероссийская межвузовская конференция аспирантов "Микроэлектроника и информатика - 2009", Круглый стол победителей конкурса грантов Правительства Санкт-Петебурга ддля студентов и аспирантов - 2010, 54-я научная конференция Московского физико-технического института «Проблемы фундаментальных и прикладных, естественных и технических наук в современном информационном обществе».
Внедрение результатов. Теоретические и практические результаты были использованы в учебном процессе кафедры моделирования вычислительных и электронных систем ГУАП, а так же при выполнении ряда проектов в ОАО "ВНИИРА".
Публикации. Результаты, представленные в диссертационной работе, опубликованы в 8 печатных работах. В том числе три работы опубликованы в журналах, утвержденных в перечне ВАК.
