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

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

005020337

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

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 3 [.!АР 2012

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

005020337

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

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

Шепета Александр Павлович

Официальные оппоненты: доктор технических наук, доцент

Тюрликов Андрей Михайлович

кандидат технических наук, с. н. с. Васильевский Александр Сергеевич

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

Защита состоится « Г?» Ог>рел& 2012 г. в (Ч_ часов на заседании диссертационного совета Д 212.233.02 при Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, г. Санкт-Петербург, ул. Большая Морская, д. 67

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

Автореферат разослан » клйр \0> 2012 г.

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

диссертационного совета Jj bi, ^

доктор технических наук, профессор QCIinoB А.

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

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

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

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

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

Задачами диссертационного исследования являются

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", "Modem 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. Алгоритм составления оптимального расписания передач для сетей с топологией «правильная решетка».

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

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

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

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

Типичная сенсорная сеть состоит из множества идентичных элементов, называемых сенсорами (другое название - интеллектуальный датчик), а так же базовой станции (БС). Назначением сенсора является контроль состояния объекта путем измерения его отдельных параметров (например, температуры, влажности окружающей среды и т. д.), первичная обработка результатов измерения, а так же передача соответствующих сообщений посредством беспроводной связи. Сообщения, передаваемые сенсорами, собираются базовой станций. Таким образом, логической структурой сенсорной сети является "все-к-одному". Будем обозначать множество элементов сети как 5 = {.$1, «2, ...,5^}, где N - число сенсоров в сети, а базовую станцию в зависимости от удобства либо как ВБ, либо как во-

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

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

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

N

но Ь = и успешных передач. Обозначим это множество передач как Р

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

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

В методе расписания ПСИ делится на слоты - отрезки времени, равные длительности передачи одного сообщения (считается, что все сообщения, формируемые сенсорами, имеют равную длительность). В каждом слоте сенсор может либо передавать сообщение, либо принимать сообщение, либо находиться в спящем режиме. Обозначим как 5"прд, 5прм, множества сенсоров, соответственно передающих сообщение, принимающих сообщение или находящихся в спящем режиме в г-м слоте (551рди5'|1рни5{'.п = 5, ¿>пРДП5прм = 0). Каждой из Ь передач назначается строго определенный слот. Назначение осуществляется таким образом, чтобы в каждом слоте с номером г множество

осуществляемых в нем передач р, было бесконфликтно. Обозначим число

к

слотов в ПСИ через К, тогда Р = и р*.

¿=1

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

Рассматриваемые сети описываются следующим набором параметров: 91,} (ЬЗ — 1) М, г Ф з) - набор коэффициентов передачи канала между всеми парами сенсоров;

2. (г,_7 = 1, г ф у) - набор расстояний между всеми нарами сенсоров;

3. Р (г = 1, ./V) - мощность передатчиков сенсоров;

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

5. д - отношение сигнал/помеха в приемнике сенсора, при котором прием

сообщения происходит с заданной достоверностью. Тогда для бесконфликтности расписания для любой передачи Sj з,

должно выполняться условие (1).

В диссертации рассмотрены две модели. Базовая модель (БМ)

В данной модели ключевым параметром является радиус действия передатчика гпрд. Коэффициенты передачи канала оцениваются по следующей формуле.

_ Г 0сл , если ¿у < г„т ,2>

\ 0 , если йц > гпрд, 1

где г/,.;, - некоторая константа большая или равная ^. Таким образом считается, что если два сенсора находятся друг от друга на расстоянии меньшем,

ми может быть установлена надежная связь. Мощность передаваемого сигнала за пределами радиуса действия считается пренебрежимо малой.

Сеть описывается графом слышимости, узлы которого соответствуют сенсорам. Если пара сенсоров s¿ и Sj находится друг от друга на расстоянии ¿¡j, меньшем чем дальность действия передатчика г1фд, то пара соответствующих им узлов в графе соединяется ребром е,;¿. Обозначим граф слышимости как Ссл = (S,Ea,), где S - множество сенсоров сети (мощность множества |S| = N), Ea¡ - множество ребер сети (Есл С SxS, е ECJI если d¡j < гпрд). Обозначим множество соседей сенсора s¿ в графе GCj1 как

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

Vfc =ЛГК, Vs¡ G Ska¡„ : ¡5„рд П Сы | = 1 (3)

Расширенная модель (РМ)

В данной модели коэффициент передачи канала между двумя сенсорами рассчитывается по формуле (4).

9ч ' у (4)

"У

Здесь а и /3 - коэффициенты, учитывающие параметры антенны, затухание на тракте распространения, уровень переотражений и т. д. Так, например, набор коэффициентов а = j^j (здесь Ао обозначает длину волны), /3 = 2 соответствует случаю работы с изотропными антеннами в свободном пространстве. Соответственно выражение (1) можно переписать следующим образом.

Vfc= l.JC.Vs, е

к

при

Е а. и

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

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

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

Определение 1

(и,ь)-дерееом называется дерево, содержащее и сенсоров на первом ярусе и V сенсоров на втором ярусе. Ду(м, и), будем обозначать (г/,и)-дерево, содержащее N сенсоров (см. рисунок 1).

06(1,2)-дереао 06(2,4)-дерево 04(3,1)-дерево

Рисунок 1 - Примеры древовидных сетей

Последовательно рассмотрены 3 типа деревьев: (1,1)-дерево, (1,г»)-дерево (у > 1) и (и,и)-дерево (и > 1). Доказаны следующие утверждения.

Утверждение 1

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

К > Ш - 3 (6)

Сформулирован алгоритм 01, позволяющий составить расписание, при котором длительность ПСИ строго равна ЗЛГ — 3 слота для любой древовидной сети. Таким образом алгоритм Ш является оптимальным для (1,1)-деревьев.

Утверждение 2

Пусть задана сенсорная сеть с топологией (1,«)-дерево (и > 2). Выделим у (1,1)-поддеревьев сформированных из ВС, являющейся корнем каждого из этих поддеревьев, сенсора первого яруса и множества потомков по линии каждого из узлов второго яруса (см. рисунок 2, где приведен пример древовидной сети с выделенными поддеревьями). Отсортируем поддеревья в порядке уменьшения числа содержащихся в них сенсоров. Пусть в большем поддереве содержится 721 +1 сенсор, в меньшем, соответственно, п„ +1 сенсор (£/¿=1 пк + 1 — Для такой сенсорной сети длительность ПСИ:

К > тах (2Ы — 1,Н + 2щ — 1) (7)

(вэ}

Рисунок 2 - Пример (1,и) древовидной сети с выделенными поддеревьями

Сформулирован алгоритм Б2, позволяющий составить оптимальное расписание для (1,г>)-дсрева (и > 1).

Утверждение 3

Путь дано дерево и) (и > 2). Выделим и поддеревьев, содержащих БС, являющуюся корнем каждого из этих поддеревьев, и множество потомков по линии каждого из узлов первого яруса (см. рисунок 3, где приведен пример древовидной сети с выделенными поддеревьями). Составим для этих поддеревьев по алгоритму Б2 расписания г = 1,и. Упорядочим поддеревья по уменьшению длины расписания. Тогда у первого поддерева будет самое длинное расписание, содержащее К\ слотов. Количества сенсоров, содержащихся в поддеревьях соответственно равны Л?ь Л^, ...Ли. Для такого дерева длительность периода сбора информации удовлетворяет неравенству

д, > Г тах(/^1, Л') , если Л'1 > Къ ~ | тах(А"1 + 1, Лг) , если К\ = 1<2

/ / \ \

. S12 } [ S16 )

Рисунок 3 - Пример (и,?;)-дерева с выделенными поддеревьями

Сформулирован алгоритм .03, позволяющий составить оптимальное расписание для (и,и)-дерева (и > 1).

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

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

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

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

Утверждение 4

Для любой сенсорной сети всегда можно построить расписание длины

к < т - з.

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

Определение 2

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

Определение 3

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

Утверждение 5

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

К = тах(./У, 3п1 - 3) (9)

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

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

Выпишем все задачи, выполняемые сенсорами за время ПСИ в виде списка, записи которого имеют следующий формат: : з,- -4 8]. Здесь г^ - к-я задача, - передающий сенсор, ь^ - приемный, Лгу - количество сообщений, передаваемых сенсором Sj сенсору в, за время ПСИ. Например, для графа, изображенного на рисунке 4 список задач будет следующим:

21 : вх Л ВБ

22 : 1 1

23 : ¿з 51

24 : : 54 1 В5

2з : : 5з 3 2

2С : : 1 ->

27 : : я7 5е

Составим граф задач '¿, узлы которого соответствуют задачам. Количество передач, осуществляемых в задании, является весом узла. Два узла в графе Z соединяются ребром в случае, если соответствующие данным узлам задачи не могут осуществляться одновременно по причине коллизии (см. рисунок 5).

Утверждение 6

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

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

О—< >—Ч 1—< 1—< >—9

1 й

# 1

О—1 1—< I—1 >—< 1—< 1—1»

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

Утверждение 7

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

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

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

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

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

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

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

Рисунок 8 - Зависимость длительности ПСИ от среднего числа соседей й (ЛГ = 100)

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

К > тах

ЛГ'=1,ЛГ

1 я Г<» к V «ЛЛ„

2 тах | к

_лл_

(10)

Здесь кптх =

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

Рисунок 9 - Зависимость длины расписания от числа сенсоров для линейной сети

Для произвольной сети предложен алгоритм составления расписания (Алгоритм 4.2), являющийся обобщением алгоритма составления подоптималь-ного расписания, приведенного в разделе 3 на случай расширенной модели. Моделированием показано, что для сенсорных сетей, устройства которых расположены в узлах правильной двумерной решетки, длительность ПСИ не превышает « 1.25ЛГ слотов при типовых параметрах модели (см. рисунок 10).

N. сенсоров

Рисунок 10 - Зависимость средне!'! длины расписания от числа сенсоров, рас-положеных в узлах правильной двумерной решетки

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

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

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

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

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

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

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

на 4%. Методом моделирования показано, что подоптимальный алгоритм формирует оптимальные расписания для сетей с древовидной топологией и топологией "правильная решетка".

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Бакип, Е. А. Метод организации сбора данных в беззапросной системе связи. / Е. А. Бакин, Г. С. Евсеев, В. Т. Яковлев, С. В. Кудряшев // М.: Вопросы радиоэлектроники, сер. ЭВТ.-2009.- Vol. 1.- С. 113.

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

3. Бакин, Е. А. Нижняя граница длительности периода сбора информации в сенсорной сети. / Е. А. Бакин, Г. С. Евсеев, А. П. Шепета // СПб.: Информационно-управляющие системы.-2011.- № 6.- С. 64.

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

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

6. Бакип, Е. А. Нижние границы длительности цикла опроса для сенсорных сетей с различной топологией. / Е. А. Бакин, Г. С. Евсеев // Научная сессия ГУАП: Сб. докл.: Б 4 ч. Ч. II. Технические науки/СПбГУАП. СПб. 2010,- С. 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. Balcin, 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 экз. Заказ №102

Отпечатано в редакционно-издательском центре ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

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

Список использованных сокращений

БС - базовая станция;

БМ - базовая модель;

МГЗ - модель с гиперболическим затуханием;

МДГ - модель с двумя графами;

ОСП - отношение сигнал/помеха;

ПСИ - период сбора информации;

СП - список приоритетов;

СПП - список приоритетов передач;

СПС - список приоритетов сенсоров;

СС - сенсорная сеть;

Условные обозначения

- расстояние между г-м и ^'-м сенсорами сети;

д^ - коэффициент передачи канала между г-м и j-м сенсорами сети;

1г - - длина маршрута, соединяющего г-й сенсор и базовую станцию;

Ь - число передач, которое должно осуществиться в ходе ПСИ;

N - число сенсоров в сети;

Д/д - средняя мощность внутренних шумов приемника сенсора;

Р - мощность передатчика сенсора;

q - требуемое отношение сигнал/помеха;

в г - г-й сенсор;

$ - множество сенсоров сети;

£гпрд - мн-во сенсоров, осуществляющее передачу сообщения в г-м слоте

5дрм - мн-во сенсоров, осуществляющее прием сообщения в г-м слоте;

- мн-во сенсоров, находящихся в спящем режиме в г-м слоте.

Введение

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

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

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

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

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

Задачами диссертационного исследования являются

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

2. Разработка алгоритмов составления оптимального расписания передач для сетей с древовидной топологией.

3. Анализ нижней границы длительности ПСИ для сети с произвольной (недревовидной) топологией.

4. Разработка алгоритмов составления оптимального расписания передач

и о п П

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

5. Разработка и анализ алгоритмов составления подоптимального расписания передач для произвольных сетей с различными моделями коллизий.

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

Научная новизна диссертационной работы заключается в следующем.

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

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

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

4. Разработанные алгоритмы составления оптимального расписания пере-

^ tj и //

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

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

Апробация работы. Основные результаты работы докладывались на научно-технических конференциях: 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 Постановка задачи

Данный раздел посвящен постановке задачи составления расписания передач для сенсорных сетей с циклическим сбором данных.

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

1.1 Структура сенсорной сети

Сенсорные сети - это относительно новый вид беспроводных средств передачи информации, хотя первые примеры подобных сетей появились в середине 20 века. Они были дороги, сложны в эксплуатации и имели, как правило, военное назначение [59]. Лишь недавний прорыв технологий производства элементной базы для беспроводных устройств сделал возможным внедрение сенсорных сетей во многих областях народного хозяйства.

Типичная сенсорная сеть состоит из множества идентичных элементов, называемых сенсорами (другое название - интеллектуальный датчик), а также базовой станции (ВС). Назначением сенсора является контроль состояния объекта путем измерения отдельных параметров окружающей среды (например, температуры, влажности и т. д.), первичная обработка результатов измерения, а также передача соответствующих сообщений посредством беспроводной связи. Сообщения, передаваемые сенсорами, собираются базовой станций. Таким образом, логической структурой сенсорной сети явлется "все-к-одному". Будем обозначать множество элементов сети как # = {в!, в2,йдг}, где N - число сенсоров в сети, а базовую станцию в зависимости от удобства либо как ВБ, либо как во-

Для выполнения перечисленных выше задач каждый сенсор оборудован следующими элементами: чувствительный элемент, блок обработки (микроконтроллер), приемопередатчик, антенна и источник питания (см. рисунок 1.1). Аппаратная составляющая типичного сенсора обладает следующими характерными особенностями ( [51,62,72]):

1. Источником питания служит, как правило, автономная батарея, энергоресурс которой ограничен, а замена ее зачастую усложняется неудобным расположением сенсора.

2. Приемопередатчик сенсора маломощен (дальность связи не превышает, как правило, нескольких десятков метров).

3. Режим работы приемопередатчика - полудуплексный, т. е. сенсор не может одновременно передавать и принимать сообщения.

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

Рисунок 1.1 - Структура сенсора

На БС возложены более ресурсоемкие функции [22]:

• хранение результатов измерений, осуществленных сенсорами сети;

• анализ результатов измерений;

• визуализация актуальной информации для оператора;

• маршрутизация сообщений, поступающих из сенсорной сети, в другие сети (например, WAN).

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

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

Рисунок 1.2 - Сенсорная сеть

1.2 Организация сбора сообщений в сенсорных сетях

В данной работе рассматриваются сети с циклическим сбором данных. Время работы таких сетей можно условно поделить на периоды сбора информации (ПСИ). В начале каждого ПСИ каждый сенсор формирует по сообщению, которое отражает состояние контролируемого сенсором объекта. За оставшуюся часть ПСИ сформированные сенсорами сообщения поступают на БС (см. рисунок 1.3). Пусть ^ - длина маршрута, соединяющего сенсор и

базовую станцию, т.е. количество ретрансляций в ходе которых сообщение

n

поступает на БС. Тогда в ходе ПСИ должно осуществиться ровно Ь = ^ ^

¿=1

успешных передач. Обозначим это множество передач как Р (|Р| = Ь).

Каждый сенсор формирует сообщение

Сбор всех сообщений

на БС

ПСИ ПСИ ПСИ

Рисунок 1.3 - Период сбора информации

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

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