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

Короткий опис

Бакин, Евгений Александрович. Повышение эффективности сбора информации в беспроводных сенсорных сетях на основе оптимизации расписания : диссертация ... кандидата технических наук : 05.13.01 / Бакин Евгений Александрович; [Место защиты: С.-Петерб. гос. ун-т аэрокосм. приборостроения].- Санкт-Петербург, 2012.- 105 с.: ил. РГБ ОД, 61 12-5/2171

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего
профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
На правах рукописи
Бакин Евгений Александрович
ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ СБОРА ИНФОРМАЦИИ В БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ НА ОСНОВЕ ОПТИМИЗАЦИИ РАСПИСАНИЯ
Специальность 05.13.01 - Системный анализ, управление и обработка информации (в технике и технологиях)
Диссертация на соискание ученой степени кандидата технических наук
Научный руководитель
доктор технических наук, профессор А.П. Шепета
Санкт-Петербург — 2012
СОДЕРЖАНИЕ
Список использованных сокращений 4
Условные обозначения 5
Введение 6
1. Постановка задачи 10
1.1 Структура сенсорной сети 10
1.2 Организация сбора сообщений в сенсорных сетях 12
1.3 Модели коллизий в сенсорных сетях 15
1.3.1 Базовая модель 16
1.3.2 Модель с двумя графами 18
1.3.3 Модель с гиперболическим затуханием 19
1.4 Маршрутизация 20
1.5 Анализ существующих алгоритмов составления расписания и
оценок длительности ПСИ 23
1.6 Выводы по разделу 28
2. Составление расписания передач в сенсорных сетях с древовидной
топологией І 29
2.1 Определения и вспомогательные утверждения 29
2.2 Алгоритмы составления оптимального расписания передач для
сетей с древовидной топологией 31
2.3 Выводы по разделу 43
3. Составление расписания передач в сенсорных сетях с недревовидной
топологией 44
3.1 Верхние оценки длительности периода сбора информации для
сети с произвольной топологией 44
3.2 Нижние оценки длительности периода сбора информации для
сети с произвольной топологией 49
3.3 Оценка для сетей с топологией типа “правильная двумерная
решетка“ 52
3.3.1 Треугольная решетка 54
3.3.2 Квадратная решетка 56
3.3.3 Гексагональная решетка 57
3.4 Алгоритм составления подоптимального расписания для произвольной сенсорной сети 59
3.4.1 Алгоритмы маршрутизации 59
3.4.2 Алгоритм назначения передач слотам 62
3.4.3 Анализ алгоритма для древовидных сетей и сетей с топологией “правильная решетка“ 66
3.4.4 Алгоритм генерации графов слышимости сетей 74
3.4.5 Анализ алгоритма для случайных графов 75
3.5 Выводы по разделу 79
4. Составление расписания передач для модели с гиперболическим законом затухания 80
4.1 Оценки длительности ПСИ для линейной сети 80
4.2 Алгоритм управления передачей сообщений для произвольной
сети 87
4.3 Выводы по разделу 91
Заключение 93
Список использованных источников 94
Приложение 101
Список использованных сокращений
БС - базовая станция;
БМ - базовая модель;
МГЗ - модель с гиперболическим затуханием; МДГ - модель с двумя графами;
ОСП - отношение сигнал/помеха;
ПСИ - период сбора информации;
СП - список приоритетов;
СПП - список приоритетов передач;
СПС - список приоритетов сенсоров;
СС - сенсорная сеть;
Условные обозначения
dij - расстояние между г-м и j-м сенсорами сети;
gij - коэффициент передачи канала между г-м и j-м сенсорами сети;
li - - длина маршрута, соединяющего г-й сенсор и базовую станцию;
L - число передач, которое должно осуществиться в ходе ПСИ;
N - число сенсоров в сети;
No - средняя мощность внутренних шумов приемника сенсора;
Р - мощность передатчика сенсора;
q - требуемое отношение сигнал/помеха;
S{ - і-й сенсор;
S - множество сенсоров сети;
^прд - мн-во сенсоров, осуществляющее передачу сообщения в г-м слоте Slnрм - мн-во сенсоров, осуществляющее прием сообщения в г-м слоте;
S1 - мн-во сенсоров, находящихся в спящем режиме в г-м слоте.
Введение
Актуальность темы. На сегодняшний день существует значительное количество прикладных задач, для решения которых необходим контроль состояния большого числа объектов. Особой привлекательностью обладают системы контроля, использующие для передачи сообщений радиоканал. Ми-ниатюризация элементной базы и прогресс технологий связи создали предпо-сылки для появления особого типа беспроводных систем передачи информа¬ции - сенсорных сетей. Как видно из названия, такая сеть состоит из множе¬ства автономных элементов - сенсоров. Сенсор включает в себя чувствитель¬ный элемент, регистрирующий изменение какого-либо физического парамет¬ра среды, блок обработки, приемопередатчик и элемент питания. Каждый сенсор может быть как источником сообщения, так и ретранслятором сооб¬щений, поступающих от других сенсоров. Таким образом, использование сен¬сорных сетей позволяет передавать информацию на значительное расстояние при малой мощности передатчиков. Конечным пунктом доставки сообщений является базовая станция (БС).
На данный момент сенсорные сети применяются в промышленности [10], сельском хозяйстве [40], медицине [26] и во многих других областях [56].
Существует большое количество приложений, в которых одним из важ-нейших параметров системы контроля является оперативность доставки со-общений [63]. В сенсорных сетях с циклическим сбором данных оперативность доставки определяется в первую очередь длительностью периода сбора ин-формации (ПСИ). Сложность задачи повышения оперативности обусловлена наличием коллизий - ситуаций, когда несколько сенсоров создают в эфире друг для друга помехи, приводящие к потере сообщения. При возникнове¬нии коллизий необходимы повторные передачи, что существенно увеличивает длительность ПСИ. Одним из способов борьбы с коллизиями является введе-ние расписания передач. Расписание составляется таким образом, чтобы не допустить одновременное возникновение мешающих передач. Понятно, что может существовать множество таких расписаний.
Целью работы является анализ граничных значений длительности ПСИ для сетей с различной топологией, а так же разработка алгоритмов состав¬ів
ления бесконфликтного расписания передач, обеспечивающих минимальную длительность ПСИ.
Задачами диссертационного исследования являются
1. Анализ нижней границы длительности ПСИ для сети с древовидной топологией.
2. Разработка алгоритмов составления оптимального расписания передач для сетей с древовидной топологией.
3. Анализ нижней границы длительности ПСИ для сети с произвольной (недревовидной) топологией.
4. Разработка алгоритмов составления оптимального расписания передач для сетей с топологией “правильная решетка“.
5. Разработка и анализ алгоритмов составления подоптимального распи-сания передач для произвольных сетей с различными моделями колли-зий.
Методы исследования. Для решения поставленных задач были исполь-зованы общие методы системного анализа, комбинаторный анализ, теория дискретной оптимизации и теория графов.
Научная новизна диссертационной работы заключается в следую¬щем.
1. Предложенные оценки длительности ПСИ для сенсорных сетей с древо-видной топологией отличаются от известных тем, что применимы для произвольной древовидной сети, а не только для некоторых частных случаев.
2. Разработанные алгоритмы позволяют составить оптимальное расписа-ние передач для любой сенсорной сети с древовидной топологией, в то время, как существующие алгоритмы позволяют составлять опти¬мальное расписание передач только для частных случаев древовидной топологии.
3. Рассчитанные верхние и нижние границы длительности ПСИ для сен-сорных сетей с произвольной топологией позволяют осуществлять оцен¬ку качества различных алгоритмов составления расписания передач. Показана точность предложенных границ.
4. Разработанные алгоритмы составления оптимального расписания пере-дач для сенсорных сетей с топологией “правильная решетка“ позволяют существенно повысить оперативность сбора информации в таких сетях.
Практическая ценность полученных результатов. Предложенные граничные значения длительности ПСИ позволяют оценить оперативность сенсорной сети еще на этапе ее проектирования, и, как следствие, оценить способность сети выполнять возложенную на нее задачу. Полученные в ходе диссертационной работы алгоритмы позволяют существенно повысить опе-ративность доставки сообщений, что обосновывает их ценность для высо-коскоростных приложений, где оперативность доставки сообщений является ключевым параметром. Предложенные алгоритмы могут служить базовыми при разработке протоколов работы скоростных сенсорных сетей.
Апробация работы. Основные результаты работы докладывались на научно-технических конференциях: 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 печатных работах ( [1,2,4-6,8,36,37] ). В том числе три
Я
работы ( [1,2,8] ) опубликованы в журналах, включенных в список ВАК.
Основные положения выносимые на защиту.
1. Оценки длительности периода сбора информации для сетей с древовид-ной топологией.
2. Алгоритм составления оптимального расписания передач для сетей с древовидной топологией.
3. Оценки длительности периода сбора информации для сетей с произ-вольной топологией.
4. Алгоритм составления оптимального расписания передач для сетей с топологией «правильная решетка».
Объем и структура работы. Диссертационная работа состоит из введе-ния, четырех разделов, заключения, списка использованных источников (74 наименования) и одного приложения. Диссертационная работа содержит 105 страниц, включая 12 таблиц и 38 рисунков.
Работа имеет следующую структуру. Раздел 1 посвящен постановке за¬дачи составления расписания передач в сенсорных сетях. Раздел содержит модель сенсорной сети, описание типов коллизий, а также краткий обзор су-ществующих алгоритмов составления расписания. В разделе 2 приводятся оценки длительности ПСИ, а также алгоритмы составления расписания для сенсорных сетей с древовидной топологией. Раздел 3 посвящен анализу сетей с не древовидной топологией, в т. ч. сетей с топологией “правильная решет- ка“. Раздел 4 посвящен рассмотрению расписаний для расширенной модели сети, учитывающей мощности передатчиков, коэффициенты затухания в ка¬нале, а также требования к ОСП. В заключении кратко перечислены основ¬ные результаты, полученные в ходе диссертационной работы. Приложение содержит доказательства некоторых вспомогательных утверждений, исполь-зованных во втором разделе.

Список літератури

Заключение
В диссертационной работе рассмотрены наиболее распространенные моде¬ли сенсорных сетей. Показано, что от выбранной модели существенно зависит подход к построению расписания и оценки граничных значений длительности ПСИ. Основные результаты, полученные в диссертационной работе:
1. В рамках базовой модели были рассмотрены сети с топологией “дерево41, “правильная решетка41, а так же сети с произвольной топо¬логией.
2. Для сетей с древовидной топологией и топологией 41 правильная решет¬ка11 получены нижние границы длительности ПСИ, а так же предло¬жены алгоритмы составления расписаний, при которых эти границы достигаются.
3. Для сети с произвольной топологией получена нижняя граница дли¬тельности ПСИ и алгоритм составления подоптимального расписания, длительность которого отличается от граничного значения не более чем на 4%. Методом моделирования показано, что для сетей с древовидной топологией и топологией 44 правильная решетка41 подоптимальный алго¬ритм формирует оптимальные расписания.
4. В рамках модели с гиперболическим затуханием получена нижняя гра¬ница длительности ПСИ для линейной сети, а так же предложен алго¬ритм составления подоптимального расписания.
5. Сформулирован алгоритм составления расписания для произвольной сети, а так же предложена методика нахождения оптимальных пара¬метров данного алгоритма. Для некоторых классов сетей показано, что полученная длительность ПСИ отличается от абсолютной нижней гра¬ницы на величину, не превышающую 25%.

Список использованных источников
1. Аръков, В. Оптимизация сбора данных в беспроводной сенсорных сетях с использованием нейронной сети с градиентным алгоритмом обучения. / В. Арьков, А. Фридлянд, А. Жевак // Нейрокомпьютеры. Разработка. Применение. — 2007. — Vol. 10. — Pp. 47-49.
2. Бакин, Е. А. Анализ времени сбора данных в системах контроля с древовидной структурой. / Е. А. Бакин, Г. С. Евсеев // Научная сессия ГУАП: Сб. докл.: В 3 ч. Ч. II. Технические науки/СПбГУАП. СПб.—
2008. -Р. 197.
3. Бакин, Е. А. Анализ граничных значений периода опроса в распределенной системе контроля с древовидной структурой при работе по протоколу zigbee. / Е. А. Бакин, Г. С. Евсеев // Научная сессия ГУАП: Сб. докл.: В 4 ч. Ч. II. Технические науки/СПбГУАП. СПб. — 2009.— Р. 283.
4. Бакин, Е. А. Нижние границы длительности цикла опроса для сенсорных сетей с различной топологией. / Е. А. Бакин, Г. С. Евсеев // Научная сессия ГУАП: Сб. докл.: В 4 ч- Ч. II. Технические науки/СПбГУАП. СПб. — 2010. — Р. 292.
5. Бакин, Е. А. Нижняя граница длительности периода сбора информации в сенсорной сети. / Е. А. Бакин, Г. С. Евсеев, А. П. Шепета // Информационно-управляющие системы. — 2011. — Vol. 6. — Р. 64.
6. Бакин, Е. А. Оценка длительности цикла работы в радиоканальной системе сбора данных с централизованным управлением. / Е. А. Бакин, Г. С. Евсеев, В. Т. Яковлев // М.: Вопросы радиоэлектроники, сер. РЛТ. - 2008. - Vol. 2. - Р. 62.
7. Гурвиц, А. Теория функций / А. Гурвиц, Р. Курант, — М.: Наука, 1968.
8. Интеллектуальные системы на базе сенсорных сетей. — Институт точной механики и вычислительной техники им. С.А. Лебедева РАН., 2009.
9. Карацуба, Е. А. Быстрое вычисление значений дзета-функции гурвица и 1-рядов дирихле / Е. А. Карацуба // Проблемы передачи информации. —- 1998. - Vol. 34:4. - Pp. 62-75.
10. Колмогоров, А. Н. Основные понятия теории вероятностей, 2 изд. /
A. Н. Колмогоров. — М.: Наука, 1974.