Авторефераты по всем темам  >>  Авторефераты по техническим специальностям

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

БАКИН Евгений Александрович

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ СБОРА ИНФОРМАЦИИ В БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ НА ОСНОВЕ ОПТИМИЗАЦИИ РАСПИСАНИЯ

Специальность 05.13.01 Системный анализ, управление и обработка информации (в технике и технологиях)

АВТОРЕФЕРАТ

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

Санкт-Петербург 2012

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

Научный консультант: доктор технических наук, профессор Шепета Александр Павлович

Официальные оппоненты: доктор технических наук, доцент Тюрликов Андрей Михайлович кандидат технических наук, с. н. с.

Васильевский Александр Сергеевич

Ведущая организация: Институт проблем передачи информации РАН

Защита состоится 17 апреля 2012 г. в 14 часов на заседании диссертационного совета Д 212.233.02 при Федеральном государственном автономном образовательном учреждении высшего профессионального образования Санкт-Петербургский государственный университет аэрокосмического приборостроения по адресу: 190000, г. Санкт-Петербург, ул. Большая Морская, д.

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан 2012 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор Осипов Л. А.

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

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

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

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

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

Задачами диссертационного исследования являются 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. Алгоритм составления оптимального расписания передач для сетей с древовидной топологией.

3. Оценки длительности ПСИ для сетей с произвольной топологией.

4. Алгоритм составления оптимального расписания передач для сетей с топологией правильная решетка.

Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованных источников (наименования)и одного приложения. Диссертационная работа содержит 1страниц, включая 12 таблиц и 38 рисунков.

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

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

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

Типичная сенсорная сеть состоит из множества идентичных элементов, называемых сенсорами (другое название - интеллектуальный датчик), а так же базовой станции (БС). Назначением сенсора является контроль состояния объекта путем измерения его отдельных параметров (например, температуры, влажности окружающей среды и т. д.), первичная обработка результатов измерения, а так же передача соответствующих сообщений посредством беспроводной связи. Сообщения, передаваемые сенсорами, собираются базовой станций. Таким образом, логической структурой сенсорной сети является Увсе-к-одномуУ. Будем обозначать множество элементов сети как S = {s1, s2,..., sN}, где N - число сенсоров в сети, а базовую станцию в зависимости от удобства либо как BS, либо как s0.

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

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

В данной работе рассматриваются сети с циклическим сбором данных.

Время работы таких сетей можно условно поделить на периоды сбора информации (ПСИ). В начале каждого ПСИ каждый сенсор формирует сообщение, отражающее состояние контролируемого сенсором объекта. За оставшуюся часть ПСИ сформированные сенсорами сообщения поступают на БС. Пусть li - длина маршрута, соединяющего сенсор si и БС (под длиной маршрута в данном случае понимается количество ретрансляций в ходе коде которых сообщение поступает на БС). Тогда в ходе ПСИ должно осуществиться ровN но L = li успешных передач. Обозначим это множество передач как P i=(|P| = L).

Оперативность сети определяется длительностью ПСИ, T. Чем меньше длительность ПСИ, тем чаще обновляется на БС информация о состоянии контролируемых объектов, а значит можно контролировать более высокочастотные параметры.

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

В методе расписания ПСИ делится на слоты - отрезки времени, равные длительности передачи одного сообщения (считается, что все сообщения, формируемые сенсорами, имеют равную длительность). В каждом слоте сенсор может либо передавать сообщение, либо принимать сообщение, либо находиться в спящем режиме. Обозначим как Si, Si, Si множества сенсоров, прд прм сп соответственно передающих сообщение, принимающих сообщение или находящихся в спящем режиме в i-м слоте (Si Si Si = S, Si Si = ).

прд прм сп прд прм Каждой из L передач назначается строго определенный слот. Назначение осуществляется таким образом, чтобы в каждом слоте с номером i множество осуществляемых в нем передач pi было бесконфликтно. Обозначим число K слотов в ПСИ через K, тогда P = pi.

i=Может существовать множество бесконфликтных расписаний. Выбор конкретного расписания осуществляется на основании используемого критерия.

В данной работе основным критерием является минимизация длины расписания K. Знание минимально возможной длительности ПСИ позволяет выяснить возможность сети выполнять возложенные на нее функции еще на этапе проектирования.

Рассматриваемые сети описываются следующим набором параметров:

1. gi,j (i, j = 1, N, i = j) - набор коэффициентов передачи канала между всеми парами сенсоров;

2. di,j (i, j = 1, N, i = j) - набор расстояний между всеми парами сенсоров;

3. P (i = 1, N) - мощность передатчиков сенсоров;

4. N0 - средняя мощность внутреннего шума приемника сенсора;

5. q - отношение сигнал/помеха в приемнике сенсора, при котором прием сообщения происходит с заданной достоверностью.

Тогда для бесконфликтности расписания для любой передачи sj si должно выполняться условие (1).

P gj,i k = 1, K, si Sk : q (1) прм P gm,i + Nsm Sk \sj ( ) прд В диссертации рассмотрены две модели.

Базовая модель (БМ) В данной модели ключевым параметром является радиус действия передатчика rпрд. Коэффициенты передачи канала оцениваются по следующей формуле.

gсл, если di,j < rпрд, gi,j = (2) 0, если di,j rпрд, N0q где gсл - некоторая константа большая или равная. Таким образом считаP ется, что если два сенсора находятся друг от друга на расстоянии меньшем, чем rпрд, то при отсутствии помех от других передающих сенсоров между ними может быть установлена надежная связь. Мощность передаваемого сигнала за пределами радиуса действия считается пренебрежимо малой.

Сеть описывается графом слышимости, узлы которого соответствуют сенсорам. Если пара сенсоров si и sj находится друг от друга на расстоянии di,j, меньшем чем дальность действия передатчика rпрд, то пара соответствующих им узлов в графе соединяется ребром ei,j. Обозначим граф слышимости как Gсл = (S, Eсл), где S - множество сенсоров сети (мощность множества |S| = N), Eсл - множество ребер сети (Eсл S S, ei,j Eсл если di,j < rпрд).

Обозначим множество соседей сенсора si в графе Gсл как C.

слi Для данной модели условия бесконфликтной передачи 1 сводятся к следующему: у каждого принимающего сообщение сенсора должен быть ровно один передающий соседний сенсор.

k = 1, K, si Sk : Sk C = 1 (3) слi прм прд Расширенная модель (РМ) В данной модели коэффициент передачи канала между двумя сенсорами рассчитывается по формуле (4).

gi,j = (4) d i,j Здесь и - коэффициенты, учитывающие параметры антенны, затухание на тракте распространения, уровень переотражений и т. д. Так, например, набор коэффициентов = (здесь 0 обозначает длину волны), = 2 соответ16ствует случаю работы с изотропными антеннами в свободном пространстве.

Соответственно выражение (1) можно переписать следующим образом.

-N0 k = 1, K, si Sk : d- + q (5) прм m,i P sm Sk \sj ( ) прд По результатам обзора литературы, посвященной задаче составления расписания для сенсорной сети были сформулированы задачи для диссертационного исследования.

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

Введено следующее вспомогательное определение.

Определение (u,v)-деревом называется дерево, содержащее u сенсоров на первом ярусе и v сенсоров на втором ярусе. DN(u, v), будем обозначать (u,v)-дерево, содержащее N сенсоров (см. рисунок 1).

Б С БС Б С 1 ярус С2 С1 С2 СС1 С2 ярус С2 С3 С3 С4 С5 С6 СС4 СD4(3,1)-дерево D5(1,2)-дерево D6(2,4)-дерево Рисунок 1 - Примеры древовидных сетей Последовательно рассмотрены 3 типа деревьев: (1,1)-дерево, (1,v)-дерево (v > 1) и (u,v)-дерево (u > 1). Доказаны следующие утверждения.

Утверждение Для сенсорной сети с топологией (1,1)-дерево длительность ПСИ:

K 3N - 3 (6) Сформулирован алгоритм D1, позволяющий составить расписание, при котором длительность ПСИ строго равна 3N - 3 слота для любой древовидной сети. Таким образом алгоритм D1 является оптимальным для (1,1)деревьев.

Утверждение Пусть задана сенсорная сеть с топологией (1,v)-дерево (v 2). Выделим v (1,1)-поддеревьев сформированных из БС, являющейся корнем каждого из этих поддеревьев, сенсора первого яруса и множества потомков по линии каждого из узлов второго яруса (см. рисунок 2, где приведен пример древовидной сети с выделенными поддеревьями). Отсортируем поддеревья в порядке уменьшения числа содержащихся в них сенсоров. Пусть в большем поддереве содержится n1 +1 сенсор, в меньшем, соответственно, nv +1 сенсор v ( nk + 1 = N). Для такой сенсорной сети длительность ПСИ:

k=K max (2N - 1, N + 2n1 - 1) (7) BS ss2 s6 s9 ssss3 s4 s5 s7 sss14 s15 sBS BS BS BS s1 ss1 sss2 sssss3 s4 ss7 sss14 s15 sРисунок 2 - Пример (1,v) древовидной сети с выделенными поддеревьями Сформулирован алгоритм D2, позволяющий составить оптимальное расписание для (1,v)-дерева (v > 1).

Утверждение Путь дано дерево DN(u, v) (u 2). Выделим u поддеревьев, содержащих БС, являющуюся корнем каждого из этих поддеревьев, и множество потомков по линии каждого из узлов первого яруса (см. рисунок 3, где приведен пример древовидной сети с выделенными поддеревьями). Составим для этих поддеревьев по алгоритму D2 расписания Ri, i = 1, u. Упорядочим поддеревья по уменьшению длины расписания. Тогда у первого поддерева будет самое длинное расписание, содержащее K1 слотов. Количества сенсоров, содержащихся в поддеревьях соответственно равны N1, N2,...Nu. Для такого дерева длительность периода сбора информации удовлетворяет неравенству 8.

max(K1, N), если K1 > KK (8) max(K1 + 1, N), если K1 = KBS s1 s2 s3 ssss5 s6 s7 s8 sss14 ss12 sBS BS BS BS sss1 ssss5 s6 s7 s8 ss13 s14 ss12 sРисунок 3 - Пример (u,v)-дерева с выделенными поддеревьями Сформулирован алгоритм D3, позволяющий составить оптимальное расписание для (u,v)-дерева (u > 1).

В разделе 3 в рамках БМ исследуются сети с недревовидной топологией.

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

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

Предложены следующие верхние границы длительности ПСИ для произвольной сенсорной сети.

Утверждение Для любой сенсорной сети всегда можно построить расписание длины K 3N - 3.

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

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

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

Утверждение Если сенсорную сеть можно разделить на I независимых подсетей, содержащих n1, n2,..., nI сенсоров (в порядке убывания числа содержащихся в них сенсоров), то для такой сети всегда можно построить расписание длительности K такое, что:

K = max(N, 3n1 - 3) (9) Для доказательства утверждения был сформулирован алгоритм 3.2, позволяющий составить расписание периода сбора информации длины, указанной в (9).

Получена следующая нижняя границы длительности ПСИ для произвольной сенсорной сети.

Выпишем все задачи, выполняемые сенсорами за время ПСИ в виде списNi,j ка, записи которого имеют следующий формат: zk : si sj. Здесь zk - k-я задача, si - передающий сенсор, sj - приемный, Ni,j - количество сообщений, передаваемых сенсором sj сенсору si за время ПСИ. Например, для графа, изображенного на рисунке 4 список задач будет следующим:

z1 : s1 BS z2 : s2 BS z3 : s3 sz4 : s4 BS z5 : s5 BS z6 : s6 sz7 : s7 sss1 sss3 BS ssРисунок 4 - Пример сенсорной сети Составим граф задач Z, узлы которого соответствуют задачам. Количество передач, осуществляемых в задании, является весом узла. Два узла в графе Z соединяются ребром в случае, если соответствующие данным узлам задачи не могут осуществляться одновременно по причине коллизии (см. рисунок 5).

z2 zzzzzzРисунок 5 - Пример графа задач Z Утверждение Для сенсорной сети невозможно составить расписание длительностью меньше, чем максимальный вес клики графа задач для данной сети.

Рассмотрен важный частный случай топологии сети - сеть типа Управильная двумерная решеткаУ. Граф такой сети является планарным. Все ячейки решетки являются правильными многоугольниками с равным числом вершин. Узлами решетки являются сенсоры. Рассмотрим три возможных типа подобных решеток (см. рисунок 6): решетки, ячейки которых являются треугольниками (треугольные решетки), четырехугольниками (квадратные решетки), и шестиугольниками (гексагональные решетки).

Рисунок 6 - Треугольная, квадратная и гексагональная решетки. Черные точки - сенсоры, черно-белые точки - БС.

Утверждение Для сети с топологией Управильная двумерная решеткаУ можно составить расписание длительности N слотов.

Для доказательства утверждения 7 сформулированы алгоритмы R3, Rи R6, позволяющие составить расписание длины N слотов для треугольной, квадратной и гексагональной решеток, соответственно.

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

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

Моделированием показано, что для случая древовидных сетей и сетей с топологией Управильная решеткаУ подоптимальный алгоритм составляет расписание длина которого совпадает с оптимальным. Методом имитационного моделирования получено, что для произвольной сети данный алгоритм формирует расписание передач, длина которого отличается от нижней границы не более чем на 4% (см. рисунок 7). Это говорит о качестве сформулированного алгоритма с одной стороны и о точности предложенной нижней границы с другой.

Рисунок 7 - Результат моделирования для случайных сетей.

Так же методом моделирования была исследована зависимость длительности ПСИ от среднего числа соседей у сенсоров в графе слышимости (см.

рисунок 8).

Рисунок 8 - Зависимость длительности ПСИ от среднего числа соседей d (N = 100) В четвертом разделе рассмотрена расширенная модель коллизий.

Для линейной сети, узлы которой расположены вдоль одной линии с шагом в h метров получена нижняя граница длительности ПСИ.

(2N + 1)N - N K max (10) N =1,N N 2 max k k 1+ qP k=1,kmax P -qN0(kh) 1 P Здесь kmax =.

h qNПредложен Алгоритм 4.1 позволяющий составить для линейной сети расписание, близкое к оптимальному (см. рисунок 9).

9Нижняя граница 8Алгоритм 4.765432150 100 150 200 250 3N Рисунок 9 - Зависимость длины расписания от числа сенсоров для линейной сети Для произвольной сети предложен алгоритм составления расписания (Алгоритм 4.2), являющийся обобщением алгоритма составления подоптимального расписания, приведенного в разделе 3 на случай расширенной модели. Моделированием показано, что для сенсорных сетей, устройства которых расположены в узлах правильной двумерной решетки, длительность ПСИ не превышает 1.25N слотов при типовых параметрах модели (см. рисунок 10).

K Рисунок 10 - Зависимость средней длины расписания от числа сенсоров, расположеных в узлах правильной двумерной решетки В заключении приводятся основные результаты, полученные в диссертационной работе.

В приложении приведены формулировки и доказательства некоторых вспомогательных утверждений из раздела 2.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ В диссертационной работе были рассмотрены наиболее распространенные модели сенсорных сетей. Показано, что от выбранной модели существенно зависит подход к построению расписания и граничные значения длительности ПСИ. Основные результаты, полученные в диссертационной работе:

1. В рамках базовой модели были рассмотрены и проанализированы сети с топологией УдеревоУ, Управильная решеткаУ, а так же сети с произвольной топологией.

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

3. Для сети с произвольной топологией получена нижняя граница длительности ПСИ и алгоритм составления подоптимального расписания, длительность которого отличается от граничного значения не более чем на 4%. Методом моделирования показано, что подоптимальный алгоритм формирует оптимальные расписания для сетей с древовидной топологией и топологией Управильная решеткаУ.

4. В рамках расширенной модели получена нижняя граница длительности ПСИ для линейной сети, а также предложен алгоритм составления подоптимального расписания.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Бакин, Е. А. Метод организации сбора данных в беззапросной системе связи. / Е. А. Бакин, Г. С. Евсеев, В. Т. Яковлев, С.

В. Кудряшев // М.: Вопросы радиоэлектроники, сер. ЭВТ.2009.- Vol. 1.- C. 113.

2. Бакин, Е. А. Оценка длительности цикла работы в радиоканальной системе сбора данных с централизованным управлением. / Е. А. Бакин, Г. С. Евсеев, В. Т. Яковлев // М.: Вопросы радиоэлектроники, сер. РЛТ.- 2008.- Vol. 2.- C. 62.

3. Бакин, Е. А. Нижняя граница длительности периода сбора информации в сенсорной сети. / Е. А. Бакин, Г. С. Евсеев, А.

П. Шепета // СПб.: Информационно-управляющие системы.2011.- № 6.- C. 64.

4. Бакин, Е. А. Анализ времени сбора данных в системах контроля с древовидной структурой. / Е. А. Бакин, Г. С. Евсеев //Научная сессия ГУАП: Сб. докл.: В 3 ч. Ч. II. Технические науки/СПбГУАП. СПб.2008.- C. 197.

5. Бакин, Е. А. Анализ граничных значений периода опроса в распределенной системе контроля с древовидной структурой при работе по протоколу zigbee. / Е. А. Бакин, Г. С. Евсеев // Научная сессия ГУАП:

Сб. докл.: В 4 ч. Ч. II. Технические науки/СПбГУАП. СПб.- 2009.- C.

283.

6. Бакин, Е. А. Нижние границы длительности цикла опроса для сенсорных сетей с различной топологией. / Е. А. Бакин, Г. С. Евсеев // Научная сессия ГУАП: Сб. докл.: В 4 ч. Ч. II. Технические науки/СПбГУАП. СПб. 2010.- C. 292.

7. Bakin, E. Data exchange system in sensor networks. x international conference for young researchers. / E. Bakin // Wave Electronics and Its Applications in the Information and Telecommunication Systems:

Proceedings. 1Ц5 June, 2007, St.Petersburg/ St.Petersburg State University of Aerospace Instrumentation. St.Petersburg. - 2007.

8. Bakin, E. Algorithm of schedule calculation for centralized sensor network / E. Bakin // International Forum Modern information society formation - problems perspectives, innovation approaches: Proceedings of the Forum.

St. Petersburg, June 6 - 11 / SUAI, SPb.- 2010.- C. 112.

Формат бумаги 60 84 1/16. Бумага офсетная. Печ. л. 1,25.

Тираж 100 экз. Заказ №1Отпечатано в редакционно-издательском центре ГУАП 190000, Санкт-Петербург, Б. Морская ул., Авторефераты по всем темам  >>  Авторефераты по техническим специальностям