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

• Бакин, Евгений Александрович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Бакин, Евгений Александрович

СОДЕРЖАНИЕ

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

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

Введение

1. Постановка задачи

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

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

1.3 Модели коллизий в сенсорных сетях

1.3.1 Базовая модель

1.3.2 Модель с двумя графами

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

1.4 Маршрутизация

1.5 Анализ существующих алгоритмов составления расписания и оценок длительности ПСИ

1.6 Выводы по разделу

2. Составление расписания передач в сенсорных сетях с древовидной

топологией ,

2.1 Определения и вспомогательные утверждения

2.2 Алгоритмы составления оптимального расписания передач для сетей с древовидной топологией

2.3 Выводы по разделу

3. Составление расписания передач в сенсорных сетях с недревовидной

топологией

3.1 Верхние оценки длительности периода сбора информации для сети с произвольной топологией

3.2 Нижние оценки длительности периода сбора информации для сети с произвольной топологией

3.3 Оценка для сетей с топологией типа "правильная двумерная решетка"

3.3.1 Треугольная решетка

3.3.2 Квадратная решетка

3.3.3 Гексагональная решетка

3.4 Алгоритм составления подоптимального расписания для произвольной сенсорной сети

3.4.1 Алгоритмы маршрутизации

3.4.2 Алгоритм назначения передач слотам

3.4.3 Анализ алгоритма для древовидных сетей и сетей с топологией "правильная решетка"

3.4.4 Алгоритм генерации графов слышимости сетей

3.4.5 Анализ алгоритма для случайных графов

3.5 Выводы по разделу

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

законом затухания

4.1 Оценки длительности ПСИ для линейной сети

4.2 Алгоритм управления передачей сообщений для произвольной сети

4.3 Выводы по разделу

Заключение

Список использованных источников

Приложение

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

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

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

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

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

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

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

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

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

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

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

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

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

д^ - коэффициент передачи канала между г-м и 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 - Период сбора информации

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

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

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

сивностью. Это делает метод случайного доступа непригодным для использования в рассматриваемых сетях сбора данных [49].

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

ства сенсоров, соответственно передающих сообщение, принимающих сообщение и находящихся в спящем режиме в г-м слоте (5,''1|)Л и ¿>прм и = 5дрд П <!?прМ = 0)- Каждой из Ь передач назначается определенный слот. Назначение осуществляется таким образом, чтобы в г-м слоте (г = 1, 2, • • •)

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

к

длина расписания - К слотов. Тогда множество передач Р = Pi.

1=1

Длительность ПСИ равна Т = Кт, где г - длительность слота (см. рисунок 1.4).

(^передач^)

Р\ Р2 Р1 ... Рк

^ Слот 1 Слот 2 Слот I Слот К ,

Период сбора информации

Рисунок 1.4 - Структура ПСИ

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

1. максимизация живучести сети за счет оптимизации энергопотребления

сенсоров;

2. минимизация длительности ПСИ для увеличения оперативности сбора данных.

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

Существует также ряд публикаций, в которых рассматриваются гибридные алгоритмы сбора данных, основанные как на расписании так и на случайном доступе [45,53,60]. Они в основном используются в сетях, разные устройства которых порождают разные типы потоков сообщений: и случайные, и регулярные. В данной же диссертационной работе рассматриваются сети, все устройства которых формируют регулярные потоки равной интенсивности и применение гибридных решений в таких сетях нецелесообразно.

1.3 Модели коллизий в сенсорных сетях

При решении задачи составления расписания необходимо задаться моделью сети, которая бы позволяла формализовать понятие "коллизия" и, соответственно, сформулировать условия бесконфликтности передач, осуществляемых в слоте. В общем случае сенсорная сеть описывается следующим набором параметров:

1. дг(г, ] — 1, N, г ^ у) - набор коэффициентов передачи канала между всеми парами сенсоров (в общем случае меняется во времени);

2. (м = 1, А^, г ]) - набор расстояний между всеми парами сенсоров (в общем случае меняется во времени);

3. (г = 15 ]\Г) - мощность передатчика сенсора

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

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

Как правило все сенсоры сети построены на одной элементной базе и Р\ = р2 = ... = рн = Р} Щг = N02 = ... = = N0 и = д2 = ••• = Ям = Я- В данной работе рассматриваются сети с неподвижными сенсорами, т.е. =

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

**=^ 6 : е 9 (1л)

Т. е. отношение мощности полезного сигнала на входе приемника к суммарной мощности помехи и внутреннего шума приемника должна быть не меньше заданной величины д. Помеха в рассматриваемых моделях сети определяется только наводками от сигналов, излучаемых другими сенсорами. Однако, решение задачи минимизации Т в общем виде для произвольного графа при заданном ограничении (1.1) является КР-трудной задачей [44]. В частности в [38] приводится алгоритм составления оптимального расписания для сетей, содержащих не более 15 сенсоров.

На практике для работы с большими сетями используются более простые модели. Главное упрощение заключается в том, что коэффициенты передачи каналов считаются постоянными во времени = . Обзор литературы

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

1.3.1 Базовая модель

Данная модель анализируется в работах [21,29,32,42,46,55,70,71] и др. В ней ключевым параметром является радиус действия передатчика гпрд. Коэффициенты передачи канала оцениваются по следующей формуле.

9сл , если < гпрд,

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Бакин, Евгений Александрович

4.3 Выводы по разделу

В данном разделе были получены следующие результаты.

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

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

3. Для сенсорной сети, устройства которой расположены в узлах правильной решетки показано, что длительность ПСИ не превышает ^ 1.25N слотов при типовых параметрах модели.

Заключение

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Бакин, Евгений Александрович, 2012 год

Список использованных источников

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.

11. Коффман, Э. Теория расписаний и вычислительные машины / Э. Коффман, — М.: «Наука», 1984.

12. Куприянов, А. Стек протоколов защищенной вероятностной маршрутизации в беспроводных сенсорных сетях / А. Куприянов // Сборник конференции "Современные информационные технологии и ИТ-образование Москва. — 2005.

13. Лугу ев, Т. Определение продллжительности оптимального расписания передачи сообщений в tdma-сетях. / Т. Лугуев // Вопросы современной науки и практики. — 2010. — Vol. 4. — Pp. 87-92.

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

15. Мочалов, В. Построение расписания доступа в беспроводную сенсорную сеть. / В. Мочалов // Электросвязь. — 2009. — Vol. 10. — Pp. 36-40.

16. Наградов, Е. Задача построения расписания конфигураций для беспроводных сенсорных сетей / Е. Наградов // Проблемы управления. — 2011. — Vol. l.-Pp. 68-73.

17. Ротхаммелъ, К. Антенны / К. Ротхаммель; Ed. by А. Киршке. — Данвел, 2005.

18. Селиверстов, Е. Обзор методов роя частиц для задачи глобальной оптимизации / Е. Селиверстов, А. Карпенко // Наука и Образование. — 2009. - Vol. 3.

19. Феллер, В. Введение в теорию вероятностной и ее приложения.Том 1. /

B. Феллер; Ed. by Ю. Хиггинс. - "МИР 1967.

20. Харари, Ф. Теория графов / Ф. Харари. - М.: УРСС, 2003. - Р. 300.

21. ADF7023. High performance, low power, ISM band FSK/GFSK/OOK/MSK/GMSK Transceiver 1С. Analog Devices.

22. Amouris, K. N. Spacetime divivsion multiple access (sdma) for mobile, mul-tihop broadcast packet radio networks /K.N. Amouris // MILKOM. — 2000. - Pp. 517-523.

23. Arikan, E. Some complexity results about packet radio networks / E. Arikan // IEEE Transactions on Information Theory. — 1984. — Vol. 30(4).-Pp. 681-685.

24. 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.

25. 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. - P. 112.

26. Berfield, A. Efficient scheduling for sensor networks / A. Berfield, D. Mosse // Proceedings of the 1st International workshop on Advances in Sensor Networks (IWASN'06). — 2006.

27. Bollobas, B. Random Graphs, 2nd edition. / B. Bollobas. — Cambridge University Press, 2001.

28. Bron, C. Finding all cliques of an undirected graph / C. Bron, J. Kerbosh // Comm. of ACM. 1973. - Pp. 575-577.

29. Cagalj, M. Tdma scheduling in competitive wireless networks / M. Cagalj, H. Zhang // EPFL - I&C - LCA. - 2005.

30. Capacity of data collection in arbitrary witreless sensor network / S. Chen, M. Huang, S. Tang, Y. Wang // IEEE Transactions on parallel and distributed systems. — 2011.

31. CC1010: Single Chip Very Low Power RF Transciever with 8051-compatible microcontroller. Texas Intstruments. SWRS047A.

32. Chlamatic, I. Tree-based broadcasting in multihop radio network / I. Chla-matic, S. Kutten // IEEE Transactions on Computers. — 1987.— Vol. C36, №10.-Pp. 1209-1223.

33. Chou, A.-M. Slot allocation strategies for tdma protocols in multihop packet radio networks / A.-M. Chou, V. O. K. Li // INFOCOM'92. 1992. - Vol. 5C.4.1.- Pp. 710-716.

34. Christophides, F. Iterative hybrid graph and interference aware scheduling algorithm for stdma networks / F. Christophides, V. Friderikos // Electronic letters. - 2008. - Vol. 44.

35. Cruz, R. L. Optimal routing, link scheduling and power control in multihop wireless networks / R. L. Cruz, A. V. Santhanam // IEEE INFOCOM'03. -2003.

36. Energy and performance considerations for smart dust / L. Doherty,

B. A. Warneke, B. E. Boser, K. S. J. Pister // International Journal on Parallel and Distributed Systems and Networks. — 2001.— Vol. 4 №3. — Pp. 121-133.

37. Energy efficient tdma sleep scheduling in wireless sensor networks / J. Ma, W. Lou, Y. Wu et al. // INFOCOM'09. - 2009.

38. Ephremides, A. Control and optimization methods in communication networks problems / A. Ephremides, S. Verdu // IEEE Transactions on Automatic Control. 1989. - Vol. 34 (9). - Pp. 930-942.

39. Erg en, S. C. Tdma scheduling algorithms for wireless sensor networks / S. C. Ergen, P. Varaiya // Wireless Netw, Springer. — 2009. — Pp. 985-997.

40. Fast data collection in tree-based wireless sensor nework / O. D. Incel, A. Ghosh, B. Krishnamachari, K. Chintalapudi // IEEE Transactions on mobile computing. — 2011. — Pp. 1-15.

41. Florens, C. Lower bounds on data collection time in sensory networks /

C. Florens, M. Franceschetti, R. J. McEliece // IEEE Journalon selected areas in communications. — 2004, — Vol. 22(6).— Pp. 1110-1120.

42. Gandham, S. Link scheduling in sensor networks: Distributed edge coloring revisited / S. Gandham, M. Dawande, R. Prakash // Proceedings of INFO-COM'05. — 2005.

43. Gandham, S. Distributed minimal time convergecast scheduling in wireless sensor networks / S. Gandham, Y. Zhang, Q. Huang // IEEE ICDCS06. — 2006.

44. Gronkvist, J. Comparison between scheduling models for spatial reuse tdma / J. Gronkvist 11 VTC Spring.- 2007.-Pp. 1066-1070.

45. Havinga, P. J. Energy-efficient tdma medium access control protocol scheduling / P. J. Havinga, G.J. Smit / / Proceedings Asian International Mobile Computing Conference (AMOC 2000). - 2000.

46. Ju, J.-H. An optimal topology-transparent scheduling method in multihop packet radio networks / J.-H. Ju, V. O. K. Li // IEEE/ACM Transactions on Networking. - 1998. - Vol. 6. - Pp. 298-306.

47. Karlof, C. Secure routing in wireless sensor networks: Attacks and coun-termeasures / C. Karlof, D. Wagner // First IEEE International Workshop Sensor Network Protocols and Applications (SNPA'03. — 2003.

48. Karp, B. Gpsr: Greedy perimeter stateless routing for wireless networks. / B. Karp, H. Kung // Proc. ACM/IEEE MobiCom'00. - 2000.

49. Lee, W. C. Y. Mobile cellular telecommunications, Analog and Digital systems / W. C. Y. Lee. - New-York: McGraw-Hill, 1995.

50. LOTUS.High performance wireless sensor network platform. MEMSIC.

51. Mao, J. A tdma scheduling scheme for many-to-one communications in wireless sensor networks / J. Mao, Z. Wu, X. Wu // Computer Communications. - 2007. - Vol. 30(4). - Pp. 863-872.

52. McKay, B. Uniform generation of random regular graphs of moderate degree / B. McKay, N. Wormald // Journal of Algorithms. — 1990. — Vol. 11. — Pp. 52-67.

53. Nuclear power comeback sure to deploy wireless tools. / R. J. Jarrett, H. M. Hashemian, G. W. Morton et al. // InTech. - 2009. - Vol. January. -P. 38.

54. Onat, F. A. Generating random graphs for simulation of wireless ad hoc, actuator, sensor, and wireless networks / F. A. Onat, I. Stojmenovic, H. Yanikomeroglu // Pervasive and Mobile Computing. — 2008. — Vol. 4. — Pp. 597-615.

55. Pardalos, P. Theory and Algorithms for Broadcast Scheduling / P. Pardalos, S. I. Buteno, C. W. Commander; Ed. by P. Pardalos, R. Murphey, D. Grun-del. - World Scientific, 2004.

56. Renner, C. Performance of energy-efficient tdma schemes in data gathering scenarios with periodic sources / C. Renner, V. Turau, C. Weyer // Proceedings of the 7th IEEE International Conference on Networked Society Systems (INSS'10). — 2010.

57. Revah, Y. improved lower bounds for data gathering time in sensor netwoks / Y. Revah, M. Segal // Third International Conference on Networking and Services (ICSN'07). - 2007.

58. Schill, F. Towards optimal tdma scheduling for robotic swarm communication / F. Schill, U. R. Zimmer, J. Trumpf // Proceedings of the TAROS international confernce. — 2005. — P. 215.

59. Sohraby, K. Wireless Sensor Networks: Technology, Protocols, and Applications. / K. Sohraby, D. Minoli, T. Znati. - Wiley-Interscience, 2007.

60. Somarriba, O. Evaluation of heuristic algorithms for scheduling, routing and power allocation in traf?c sensitive spatial tdma wireless ad hoc networks / O. Somarriba // 6th International ICST Symposium on Modeling and Optimization, IEEE. - 2008.

61. Tomita, E. The worst-case time complexity for generating all maximal cliques and computational experiments / E. Tomita, A. Tanaka, H. Takahashi // Theoretical Computer Science. - 2006. - Vol. 363. - Pp. 28-42.

62. Tze Huei Lai, D. Healthcare Sensor Networks: Challenges Toward Practical Implementation. / D. Tze Huei Lai, M. Palaniswami, R. Begg. — CRC Press, 2011.

63. Veeramachaneni, K. Optimal scheduling in sensor networks using swarm intelligence / K. Veeramachaneni, L. A. Osadciw // Proceedings of conference on Informaion sciences and system (CISS'04).— 2004.

64. Vergados, D. J. Optimizing end-to-end tdma scheduling in ad-hoc networks on random topologies / D. J. Vergados, K. Maria, V. D. D. // The Sixth Annual Mediterranean Ad Hoc Networking Workshop. — 2007. — Vol. 71-78.

65. Wang, L. A gradual noisy chaotic neural network for solving the broadcast scheduling problem in packet radio networks / L. Wang, H. Shi // IEEE Transactions on Networking. - 2008. - Vol. 17. - Pp. 989-1000.

66. Wang, T. A new method for multi-objective tdma scheduling in wireless sensor networks using pareto-based pso and fuzzy comprehensive judgement / T. Wang, Z. Wu, J. Mao // HPCC'07. - 2007.

67. Wang, T. Pso-based hybrid algorithm for multi-objective tdma scheduling in wireless sensor netwoks. / T. Wang, Z. Wu, J. Mao // ChinaCOM: 2nd International ICST Conference on Communication and Netwoking in China, IEEE. - 2007.

68. Warrier, A. Z-mac: a hybrid mac for wireless sensor networks / A. Warrier, J. Min, I. Rhee // SIGCOMM'05. - 2005.

69. Wen, Y.-F. A tdma-based scheduling and routing algorithm for data-centric wireless sensor networks / Y.-F. Wen, F. Y.-S. Lin, H.-S. Wang // Proceedings of IEEE, GLOBECOM'07.- 2007.

70. Whitman, E. C. Sosus: The "secret weapon"of undersea surveillance-/ E. C. Whitman // Undersea Warfare. - 2005. - Vol. 7. - P. 215.

71. Wormald, N. Models of random regular graphs / N. Wormald // Surveys in Combinatorics. 1999.-Pp. 239-298.

72. Yi Poe, W. Minimizing the maximum delay in wireless sensor networks by intelligent sink placement: Tech. rep. / W. Yi Poe, S. J. B.: disco: Distributed Computer Systems Lab, 2007.

73. Zhang, J. On fast optimal stdma scheduling over fading wireless channels / J. Zhang, S. C. Liew, F. Liqun // IEEE INFOCOM.- 2009,- Pp. 17101718.

74. Zhang, W. Integrated wireless sensor/actuator networks in an agricultural applications. / W. Zhang, G. Kantor, S. Singh // Second ACM International Conference on Embedded Networked Sensor Systems (.SenSys).— 2004,— P. 317.

75. Zhang, Y. Distributed minimal time convergecast scheduling for small or sparse data sources / Y. Zhang, S. Gandham, Q. Huang // 28th IEEE International Real-Time Systems Symposium. — 2007. — Pp. 301-310.