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

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

Баскаков Сергей Сергеевич

Маршрутизация по виртуальным координатам в беспроводных сенсорных сетях

05.13.15 - Вычислительные машины, комплексы и компьютерные сети

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

Москва - 2011

3 1 МА? 2011

4841583

Работа выполнена в Московском государственном техническом университете им. Н.Э. Баумана

Научный руководитель:

доктор технических наук, профессор Девятков Владимир Валентинович

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

Вишневский Владимир Миронович

кандидат технических наук, доцент Ващенко Борис Иванович

Ведущая организация:

Институт проблем управления РАН

Защита диссертации состоится « 14 » апреля 2011 г. в 16:30 назаседа-нии диссертационного совета Д 212.141.10 при Московском государственном техническом университете имени Н.Э. Баумана по адресу: 105005, Москва, 2-я Бауманская ул., д. 5.

С диссертацией можно ознакомиться в библиотеке МГТУ им. Н.Э. Баумана.

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

105005, Москва, 2-я Бауманская ул., д. 5, МГТУ им. Н.Э. Баумана, ученому секретарю диссертационного совета Д 212.141.10.

Автореферат разослан « » М.А-РТ2011 г.

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

диссертационного совета, кандидат технических наук, доцент

С.Р. Иванов

Общая характеристика работы

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

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

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

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

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

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

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

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

Задачи исследования. Для достижения поставленной цели необходимо выполнить следующее:

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

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

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

4. Разработать метод организации сетевой службы установки соответствия между адресами узлов и их виртуальными координатами.

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

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

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

Объектом исследования являются беспроводные сети передачи информации.

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

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

Научная новизна. При проведении исследования были получены следующие новые научные результаты:

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

1. Теоретическое обоснование свойств созданного метода маршрутизации по виртуальным координатам.

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

3. Метод организации распределенных хэш-таблиц на основе виртуальных координат и его применение для децентрализованного хранения виртуальных координат узлов.

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

5. Результаты экспериментального обоснования эффективности разработанного метода и его преимуществ по сравнению с известными аналогами. Практическая ценность и реализация результатов работы. На основе

разработанного метода ВК-маршрутизации могут быть созданы новые протоколы маршрутизации для БСС крупных масштабов. Один из вариантов подобного протокола маршрутизации реализован в виде встроенного программного обеспечения беспроводных узлов и используется на практике в стеке сетевых протоколов российской аппаратно-программной платформы MeshLogic, предназначенной для разработки БСС под различные прикладные задачи.

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

• 30-я и 31-я конференция молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (Россия, Звенигород, 2007; Россия, Геленджик, 2008).

• The 3rd international conference on wireless algorithms, systems and applications (USA, Dallas, 2008).

• The 2nd IEEE international conference on self-adaptive and self-organizing systems (Italy, Venice, 2008).

• Всероссийская конференция с международным участием «Технические и программные средства систем управления, контроля и измерения» (Россия, Москва, 2008).

• 4-й международная конференция по проблемам управления (Россия, Москва, 2009).

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы, включающего 94 наименования. Работа изложена на 218 страницах, содержит 43 рисунка и 7 таблиц.

Содержание работы

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

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

Беспроводную сенсорную сеть представим в виде взвешенного сильно связного ориентированного графа G = (V, Е, ф), в котором множество вершин V соответствует узлам сети в количестве \V\ — п, а дуга е = (w; w) 6 Е обозначает беспроводное соединение (канал связи), по которому возможна передача информации только от v к w. В работе синонимами являются следующие пары терминов: «граф» - «сеть», «вершина» - «узел» и «дуга» - «соединение».

Считаем, что задана максимальная возможная дальность радиосвязи между узлами равная г ми узлы могут передавать пакеты только по одному полудуплексному цифровому радиочастотному каналу связи, поэтому вершины соединены между собой только двумя противоположно направленными дугами. Качество связи между соседними узлами v и w описывается двумя параметрами: Pvw - вероятность битовой ошибки при передаче данных от и к го, f3wv - вероятность битовой ошибки при передаче в обратном направлении.

Весовая функция для дуг графа <р : Е -> [1; +оо) называется метрикой стоимости соединения, ее значение для дуги е = (v,w) является мерой затрат ресурсов узлов (например, энергии) на передачу пакета от v к w.

Каждый узел сети v способен поддерживать в актуальном состоянии информацию о собственном сетевом окружении - множестве соседних узлов J\f{v) = {w е V : (v;w) £ Е}, в частности: их адреса, качество связи с ними, их остаточный запас энергии и другие служебные данные, но при этом объем этой информации фиксирован и не зависит от п.

Все узлы расположены случайно и равномерно на двухмерной плоскости и покрывают площадь А м2. Тогда плотностью размещения узлов в пространстве (или плотностью сетевого окружения) является среднее количество соседей у каждого из них, то есть р = М [|Л/"(г>)|] = пят2/А узлов, а диаметр сети (максимальное расстояние между всевозможными парами узлов, измеренное как длина кратчайшего пути на графе G) - D к = dh„p(P) \J*f>

где dhop{p) = 1 + ехр(—р) — J* х exp [-^(arceosх - ху/1 - х2)] dx.

При распределении узлов в трехмерном пространстве изменяется только вид выражений, описывающих соотношение между п, р и D, а все приве-

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

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

Маршрут p(s, t) между узлом-отправителем s и узлом-получателем t - это путь на графе G в виде конечной последовательности вершин {s = vq, •••, vi = t}, a P(s, t) - множество всевозможных маршрутов между s и t. Количество соединений I в пути p{s,t) называется длиной маршрута l(p), а стоимость маршрута p{s, t) равна C\p(s, i)] = </>[(и*; ui+i)].

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

Popt{s,t) = argmin C\p(s, i)], для \fs,t <E V. (1)

p(s,t)eP(s,t)

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

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

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

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

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

для решения задачи поиска оптимальных маршрутов в БСС крупных разме-

ров.

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

Е0М

тахтш —-—--(2)

при условии Чгоу + Чу = 1]цеЛ» qvчУv 6 У\Т, где Е0(у) - начальный

запас энергии узла у; - интенсивность генерации трафика узлом и; еьь, -количество энергии, требуемое на передачу одного пакета от V к ад; <уиш -поток пакетов от узла у к узлу q = {д,,и,} - общий сетевой трафик; Т -множество узлов-получателей.

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

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

Разработанный метод ВК-маршрутизации предполагает выполнение следующих действий:

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

• Анализируя полученные сигнальные пакеты, все узлы сети вычисляют стоимость оптимальных путей до каждого из опорных узлов. В результате каждый узел у £ V получает вектор виртуальных координат у = {и,}"^, в котором Уг = С\рщЛ(у, /¿)], где Рор1(у,и) - путь с минимальной стоимостью между V и г-ым опорным узлом При этом ^ = 0, если узел у является г-ым опорным узлом.

• Для начала процедуры ВК-маршрутизации узел-отправитель 5 определяет виртуальные координаты узла-назначения Ь по его адресу аг с помощью специальной сетевой службы.

• Процесс обнаружения пути и доставки по нему пакета данных от 5 к I заключается в последовательном сокращении виртуального расстояния до t по описанному ниже алгоритму поиска маршрутов. Значение метрики виртуального расстояния 5(у, ги) для ги £ V является мерой близости этих узлов и вычисляется по их виртуальным координатам.

В общем случае заголовок пакета Р состоит из следующих полей: а3 - ад-

рес узла-отправителя в; аг и £ - адрес и виртуальные координаты узла-получателя ¿„аП - текущее минимальное виртуальное расстояние до Р1оос1Мос1е и Р1оойЯа(Ииз - признак и радиус (пределы) лавинообразной (волновой) широковещательной передачи пакета.

При начале доставки пакета в инициализирует поля заголовка пакета Р соответствующими значениями и запускает алгоритм поиска маршрута, который представляет собой итерационную процедуру, выполняемую всеми промежуточными узлами до тех пор, пока пакет не дойдет до £ или не будет превышен предел Р1оо<Ша<Ии8:

1. На каждом этапе в первую очередь задача заключается в доставке пакета в режиме минимизации расстояния. Текущий узел V формирует из М{у) подмножество Л/г = {и) € : 6(ги, Р.Р) < 6(у, Р.Р)}, из которого выбирается узел и с максимальным значением метрики прогресса К (и = Щу, ги, Р£)) и делается попытка доставить ему пакет Р в адресном режиме. Если попытка завершилась успешно, то роль узла V в поиске данного маршрута завершена и следующим звеном является узел и, который будет выполнять аналогичные действия. В противном случае и исключается из Л/г и попытка повторяется.

2. Если не удалось выполнить итерацию в жадном режиме (А/} = 0), то вычисляется к = Если текущий узел V не является то он передает пакет своему родительскому узлу Рк(у) по к-ой оси координат.

3. Если же пакет дошел до ближайшего к Ь опорному узлу, то начинается широковещательная передача пакета с радиусом Р1оо<Ша<Иив =

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

1. Объем служебной информации, передаваемой в пакете ВК-маршрутиза-ции, равен Э(п^).

2. Объем служебной информации, хранимой каждым из узлов сети, равен 0{рпь).

3. Алгоритм гарантирует отсутствие циклов при поиске маршрута.

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

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

. п (р0(°

\rmin

успешность которого составляет то есть определяется надежностью

каналов связи и расположением опорных узлов в топологии сети. Следовательно, при абсолютной надежности каналов связи (ртт = 1) алгоритм гарантирует обнаружение маршрута независимо от количества опорных узлов п^, хотя из этого не следует, что можно обойтись сколь угодно малым птак как эта гарантия не означает автоматическое удовлетворение заданным критериям оптимальности. При ртг„ < 1 повысить надежность ВК-маршрутизации возможно, в частности, уменьшением Д^ за счет повышения П£ и выбора вида распределения опорных узлов по сети.

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

= П пРи распределении пь опорных узлов по пери-

метру (границе) сети;

' ^ {Рты^^ ~ ^ {^Рпйп ^ ^ ^ при равномерном распределении пь опорных узлов по площади (объему) покрытия сети,

где рГПт - минимальная вероятность успешной передачи широковещательного пакета, (1 - размерность физического пространства, в котором размещены узлы (й = 2 при распределении на плоскости, (1 = 3 при распределении в трехмерном объеме).

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

В параграфе 2.5 описана новая система распределенных хэш-таблиц (ассоциативных массивов, ячейками которых являются узлы сети) на основе виртуальных координат для децентрализованного хранения в сети различного рода информации.

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

1. Среднее количество элементов, хранящихся в одном узле, (средняя нагрузка) равно

2. Математическое ожидание максимального количества элементов, хранящихся в одном узле, (максимальная нагрузка) равно 0 (^р).

Для построения распределенной хэш-таблицы с указанными в теореме 3 свойствами могут использоваться различные эвристические хэш-функции Н(к), реализующие отображение Я : К —»• К"' пространства ключей К (\К\ = пк) в п^-мерное пространство виртуальных координат. В работе хэш-функция Н{к) задана в следующем виде.

Без потери общности можно считать, что пространство ключей К представлено в виде множества положительных целых чисел N = {1,2,...}. Тогда хэш-функция Н(к) преобразования ключа к в вектор виртуальных координат К представляет собой последовательный вызов генератора псевдослучайных чисел, инициализированного значением ключа к, для получения массива К = {/г;}^! такого, что /г; б [0; О] при Уг = 1 : пь и удовлетворяется система из П1(п1 — 1)/2 неравенств:

+ й2 > 1щ Ь>ПЬ-1 + Ьщ. >

где - ]-ът элемент вектора виртуальных координат г-го опорного узла Ц.

В разработанном методе ВК-маршрутизации распределенная хэш-таблица применяется для организации сетевой службы установки соответствия между адресами узлов и их виртуальными координатами, поэтому для ее работы каждому узлу в среднем потребуется 9 (п^) памяти, а в наихудшем случае -в(рпь), что значительно меньше, чем при других подходах.

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

При случайном распределении опорных узлов, предлагаемом в большинстве работ по ВК-маршрутизации, необходимо увеличивать пь для достижения высокой эффективности, но тогда возрастают накладные расходы на хранение и передачу виртуальных координат. Из теоремы 2 и результатов, приведенных в главе 5 работы, следует, что более целесообразно применение равномерного распределения опорных узлов или их размещение по периметру. Поэтому в работе разработан распределенный алгоритм выбора любого заданного количества опорных узлов пь (пь < тг) из исходного множества V, при этом узлы из полученного в результате множества опорных узлов V/, = Я V

распределены по одному из указанных вариантов.

При инициализации сети формирование Уь выполняется последовательно, и базовая идея алгоритма заключается в том, что

1к = а^тах ¡{у, Ьк), 2 < к < щ, (3)

v<=V\VL

где Ь], = {1,2,...,к- 1}.

Выбор опорных узлов основан на использовании в выражении (3) эвристической функции голосования, значение которой для узла определяет его приоритет в получении статуса опорного. Для равномерного распределения опорных узлов предназначена функция /т;„(г7, Ь) — тт^^г/,}, а для распре-

деления по периферии (на границе) сети - функция fprod{v, L) ~ Y\ieL и,-. При этом обе функции применимы как при размещении узлов V на плоскости, так и в трехмерном объеме.

Однако в процессе эксплуатации сети возможно изменение ее топологии, поэтому требуется обновление Vj, для адаптации к текущим условиям. При выходе из строя 1т поиск замены выполняется подстановкой в процедуру (3) множества L = {1,2,... ,т — 1,тп + 1, Кроме того, если сеть функционирует в течение длительного времени, топология сети может измениться насколько значительно, что действующее распределение опорных узлов не будет соответствовать ей, поэтому необходимо периодическое их переназначение путем последовательного выполнения (3) относительно Lk = {1,2,..., nL}\{k} для Vfc = 1 : nL.

Теорема 4. Разработанный распределенный алгоритм выбора опорных узлов имеет сложность по времени © (niD) и сложность по памяти 0 {til), а для сетей крупных масштабов оценки сложности равны 0(D) и 0(1) соответственно. При этом по критериям сложности алгоритм является наилучшим из всех возможных для маршрутизации по виртуальным координатам в сетях крупных масштабов.

Из теоремы 4. следует, что алгоритм отличается высокой масштабируемостью и по критериям сложности является оптимальным для крупномасштабных БСС, которые характеризуются тем, что ni п при р = const и пь = const. При этом © (n^D) и 0(D) являются оценками скорости сходимости алгоритма при любой статической топологии сети и произвольном (не только равномерном) распределении узлов.

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

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

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

• модифицированная метрика «ожидаемое количество передач»

ММЕТХ (и, ад) = —-- .-—; (4)

• модифицированная метрика «ожидаемая длительность передачи»

Мметт^,!») =-^-—-X-; (5)

• метрика «ожидаемое общее количество передач»

ы / ^ 1 + Ф(Дм,А0

МеттхЬ),™) =—;-;—--; (6)

• метрика «ожидаемая общая длительность передачи»

МЕТгт(у, ю) = ^ + , (7)

ВЩ^ЬлЩРпнЬа) где Ф(0, Ь) - функция вероятности успешного приема пакета длиной Ь байт при вероятности битовой ошибки /?; /3„ю и /?ю„ - статистические оценки качества связи между узлами V и ги; и Ьа - длина пакетов данных и подтверждения, байт; В - техническая скорость передачи данных, байт/с.

В параграфе 4.5 рассматривается метрика прогресса на ис-

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

пи, Л - х [¿(^-¿К*)] ш

щу,и):г) —--г-х—- ^— Л , (8)

а метрика виртуального расстояния в общем случае имеет вид

Гад, ] ур

где р - порядок (степень) нормы (1 < р < оо); IV ¿¡) - некоторая весовая функция, \У(Уг,и) > 0.

Для решения задачи поиска оптимальных маршрутов в функции (8) применяются метрики стоимости перехода СМЕТХ, СМЕТТ, СЕТТХ И СЕТТТ, которые соответственно заданы выражениями (4)-(7), а для эвристического приближенного решения задачи маршрутизации с обеспечением максимального времени жизни сети за счет динамической балансировки сетевой нагрузки используется метрика «ожидаемая остаточная емкость»

сеяс(у, и>) =

е(у, т) Е(т)

ЕгеЛН«) е(У> х) Их&Ы^) Е(х)

где е(у,ги) = [егх4 + 1,<г)]/[Ф(Дто, Ь£г)Ф(/0шг), - ожидаемые об-

щие затраты энергии принимающего узла ги, Дж; еТХ4 и егх,а - затраты энергии на прием пакета данных и передачу пакета подтверждения, Дж; Е(ы) - нор-

мированная мера текущего запаса энергии узла w, E[w) g (0; 1].

В пятой главе приведены результаты имитационного моделирования, в ходе которого исследовалось влияние различных факторов на эффективность ВК-маршрутизации и выполнено экспериментальное сравнение характеристик созданного метода относительно известных аналогов. Исследование проведено в системе моделирования дискретных событий OMNeT++ версии 3.2 с пакетом Mobility Framework 2.0.

Для оценки эффективности маршрутизации предложено 8 критериев:

• общий коэффициент доставки пакетов t]dr =

• коэффициент доставки пакетов в жадном режиме t/org — 7p1;

• коэффициент длины маршрута i]PS = jf- £¿=1

нормированная латентность маршрута щ =

ЩО)

относительное энергопотребление узла т]ес = £

T,U[EM-EM/Ei{üY = (Ld+La)Y:tf MsuU)}

tx,a

• коэффициент эффективности по энергии tjee = —NriLi_

• коэффициент эффективности по трафику tjte

• условное время жизни сети щт = L(iNtx, байт, где NTX и Nrx g - количество пакетов, доставленных узлам-получателям и доставленных только в режиме жадного поиска; Ntx - количество пакетов, отправленных узлами-отправителями; p(si, ti) и ps(si, U) - обнаруженный и кратчайший пути между г-ми отправителем и получателем; Tlxd и Т/х а - общее количество пакетов данных и подтверждения, переданных г-ым узлом; £"¿(0) и Ei(t) - начальный и конечный запас энергии г-го узла.

В соответствии с принятой моделью сети было создано множество экземпляров многоячейковых топологий при г = 50 м, п от 50 до 1000 узлов и р от 5 до 30 узлов. Для оценки энергопотребления узлов использована упрощенная модель, в которой учитываются затраты энергии только на передачу и прием пакетов данных и подтверждения.

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

На втором этапе моделирования была разработана имитационная модель радиоканала стандарта IEEE 802.15.4 диапазона частот 2,4 ГГц в условиях крупномасштабного замирания и случайного разброса параметров приемопередатчиков. Используя ее и опираясь на выработанные ранее рекомендации, исследована эффективность разработанных метрик стоимости соединения и перехода при ненадежных каналах связи и выполнено сравнение созданного метода с двумя наиболее показательными методами ВК-маршрутизации (Hybrid Geographic and Virtual Coordinate Greedy Routing и Logical Coordinate

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

Основные результаты и выводы

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

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

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

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

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

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

по ненадежным каналам связи. В итоге обеспечивается более точное решение задачи поиска оптимальных маршрутов в реальных условиях эксплуатации БСС.

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

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

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

Список работ по теме диссертации

1. Баскаков С. С. Распределенный алгоритм автоматического выбора опорных узлов в беспроводных многоячейковых (mesh) сетях // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2008. № 4. С. 15-29.

2. Баскаков С. С. Надежность радиочастотного цифрового канала связи при крупномасштабном замирании и случайном разбросе параметров приемопередатчиков // Успехи современной радиоэлектроники. 2008. № 12. С. 47-54.

3. Баскаков С. С. Исследование способов повышения эффективности маршрутизации по виртуальным координатам в беспроводных сенсорных сетях // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2009. № 2. С. 112-124.

4. Baskakov S. Landmarks selection algorithm for virtual coordinates routing // Proceedings of the 3rd international conference on wireless algorithms, systems and applications. Dallas (USA), 2008. Vol. 5258 of Lecture notes in computer science. P. 17-28.

5. Baskakov S. Landmarks selection algorithm for wireless sensor networks // Proceedings of the 2nd IEEE international conference on self-adaptive and self-organizing systems. Venice (Italy), 2008. P. 361-369.

6. Баскаков С. С., Оганов В. И. Передача данных на базе технологии WirelessUSB // Электронные компоненты. 2005. № 3. С. 109-113.

7. Баскаков С. С., Оганов В. И. Беспроводные сенсорные сети на базе платформы MeshLogic // Электронные компоненты. 2006. № 8. С. 65-69.

8. Баскаков С. С. Алгоритм автоматического выбора опорных узлов в беспроводных сенсорных сетях // Информационные технологии и системы: Сборник трудов Всероссийской конференции. Звенигород, 2007. С. 2-8.

9. Баскаков С. С. Беспроводные сенсорные сети: вопросы и ответы // Автоматизация в промышленности. 2008. № 4. С. 34-35.

10. Баскаков С. С. Стандарт ZigBee и платформа MeshLogic: эффективность маршрутизации в режиме «многие к одному» // Первая миля. 2008. № 2-3. С. 32-37.

11. Баскаков С. С. Эффективность метрик стоимости соединений стандарта ZigBee // Информационные технологии и системы: Сборник трудов Всероссийской конференции. Геленджик, 2008. С. 30-34.

12. Баскаков С. С. Модель беспроводного канала связи в условиях крупномасштабного замирания и случайного разброса параметров приемопередатчиков // Информационные технологии и системы: Сборник трудов Всероссийской конференции. Геленджик, 2008. С. 161-166.

13. Баскаков С. С. Методы увеличения срока службы распределенных беспроводных сетей сбора данных // Технические и программные средства систем управления, контроля и измерения: Сборник трудов Всероссийской конференции с международным участием. Москва, 2008. С. 930-936.

14. Баскаков С. С. Аппаратно-программная платформа MeshLogic для разработки беспроводных сенсорных сетей // Технические и программные средства систем управления, контроля и измерения: Сборник трудов Всероссийской конференции с международным участием. Москва, 2008. С. 937-939.

15. Баскаков С. С. Управление случайным доступом к среде с низкопотребляющим прослушиванием канала на базе стандарта IEEE 802.15.4 // Сборник трудов IV Международной конференции по проблемам управления. Москва, 2009. С. 1736-1743.

16. Баскаков С. С. Беспроводные системы сбора данных на базе радиочастотных модулей ML-Module-Z // Беспроводные технологии. 2009. № 1. С. 46—49.

17. Баскаков С. С. Опыт применения радиочастотных модулей MeshLogic для разработки беспроводных систем сбора данных // Беспроводные технологии. 2009. № 3. С. 44-47.

18. Баскаков С. С. Встраиваемые модули MeshLogic для построения беспроводных сенсорных сетей // Встраиваемые системы. 2009. № 3. С. 30-32.

19. Баскаков С. С. Оценка энергопотребления беспроводных узлов в сетях MeshLogic // Беспроводные технологии. 2010. № 1. С. 28-31.

20. Баскаков С. С. Беспроводная система мониторинга состояния строительных конструкций // Беспроводные технологии. 2010. № 3. С. 52-54.

Подписано к печати 9.03.11. Заказ №145 Объем 1,0 печ.л. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 (499) 263-62-01

Введение.

Глава 1. Состояние вопроса и постановка задачи исследования

1.1. Введение.

1.2. Модель беспроводной сети

1.3. Задачи маршрутизации.

1.4. Обзор методов маршрутизации.

1.5. Цель и задачи исследования.

Глава 2. Маршрутизация по виртуальным координатам.

2.1. Введение.

2.2. Общее описание метода.

2.3. Алгоритм поиска маршрута.

2.4. Свойства алгоритма поиска маршрута.

2.5. Оценка расстояния по виртуальным координатам.

2.6. Распределенные хэш-таблицы на основе виртуальных координат

2.7. Распределенная база данных виртуальных координат узлов

2.8. Выводы

Глава 3. Выбор опорных узлов.

3.1. Введение.

3.2. Централизованный алгоритм выбора опорных узлов.

3.3. Распределенный алгоритм выбора опорных узлов

3.4. Примеры работы алгоритма выбора опорных узлов

3.5. Оценка сложности алгоритма выбора опорных узлов.

3.6. Выводы

Глава 4. Модель канала связи и метрики маршрутизации.

4.1. Введение.

4.2. Модель беспроводного канала связи.

4.3. Метрики стоимости соединения.

4.4. Метрики виртуального расстояния.

4.5. Метрики прогресса.

4.6. Выводы

Глава 5. Результаты имитационного моделирования.

5.1. Введение.

5.2. Среда и условия имитационного моделирования.

5.3. Модель энергопотребления узла.

5.4. Критерии оценки эффективности маршрутизации.

5.5. Маршрутизация при идеальном канале связи.

5.6. Маршрутизация при реальном канале связи.

5.7. Сравнение с другими методами маршрутизации

5.8. Оценка расстояния по виртуальным координатам.

5.9. Выводы

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

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

• отсутствие необходимости в прокладке кабелей для электропитания и передачи данных;

• низкая стоимость монтажа, пуско-наладки и технического обслуживания системы;

• удобство размещения автономных беспроводных узлов в самых различных точках пространства;

• возможность внедрения и модификации сети на эксплуатируемом объекте при минимальном вмешательстве в процесс его функционирования;

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

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

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

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

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

Решению задачи поиска оптимальных маршрутов в БСС посвящено множество исследований. Однако подходы, аналогичные предложенным в работах [1-3], предназначены для узкоспециализированных сетей только с типом трафика «многие-к-одному» и неприменимы при трафике «многие-ко-многим». Алгоритмы маршрутизации реактивного типа (например, [4-6]) более универсальны и обеспечивают оптимальное решение, но не обладают свойством маештабируемости. Принцип географической маршрутизации (например, [7-11]) поддерживает оба типа трафика и обладает высокой масштабируемостью, но найденные маршруты лишь близки к оптимальным и на практике его эффективность значительно ухудшается из-за неоднородности топологии* сети при ненадежных каналах связи и наличии препятствий, а также из-за погрешностей определения координат узлов в физическом пространстве.

Маршрутизация с максимизацией времени жизни сети рассматривается в таких работах, как [12-19], при этом в [13] доказана ИР-трудность этой задачи. Однако описанные в литературе эвристические подходы к приближенному ее решению предполагают либо выполнение централизованных вычислений, что плохо реализуемо на практике в крупномасштабных сетях, либо-ориентированы на частный случай сети с типом трафика «многие-к-одному».

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

В настоящей работе решение задач поиска оптимальных маршрутов и маршрутизации с балансировкой сетевой нагрузки основано на использовании принципа маршрутизации по виртуальным координатам (ВК-маршрути-зации), предложенного относительно недавно в работах [20-25]. В исходном варианте виртуальные координаты узла представляют собой вектор, элементами которого являются значения минимального количества элементарных передач между данным узлом и фиксированным набором опорных узлов, которые выбираются среди обычных при инициализации сети и периодически начинают широковещательную передачу специальных сигнальных пакетов, а остальные узлы эти пакеты только ретранслируют. Виртуальные координаты используются для вычисления виртуального расстояния между узлами с помощью некоторой метрики (например, Евклидовой нормы), и процесс ВК-маршрутизации заключается в последовательной минимизации виртуального расстояния до узла-получателя» пакета. В ходе жадного поиска маршрута возможно обнаружение локального минимума (ситуация, при которой очередной-узел- не имеет узла-соседа, расположенного ближе к узлу-назначению), для выхода из которого используются различные варианты бектрекинг-режима, полностью или с высокой вероятностью гарантирующие доставку пакета ценой увеличения длины пути. Хотя при ВК-маршрутизации не обеспечивается строгая оптимальность маршрутов и одним из критериев эффективности является степень близости' найденного пути и наилучшего, применение принципа ВК-маршрутизации позволяет обеспечить следующие свойства:

• поддержка типов трафика «многие-к-одному» и «многие-ко-многим»;

• ' высокая масштабируемость;

• локальная устойчивость (способность прокладывать маршрут в обход вышедших из строя узлов и нарушенных связей без специального алгоритма восстановления);

• отсутствие жесткой привязки к инфраструктуре и топологии сети;

• отсутствие необходимости в системе локализации узлов;

• адаптация-к изменениям топологии сети.

Однако для успешного решения поставленных задач за счет применения ВК-маршрутизации необходимо разрешить следующие проблемы:

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

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

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

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

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

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

Задачи исследования. Для достижения поставленной цели необходимо выполнить следующее:

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

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

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

4. Разработать метод организации сетевой службы установки соответствия между адресами узлов и их виртуальными координатами.

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

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

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

Объектом исследования являются беспроводные сети передачи информации.

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

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

Научная новизна. При проведении исследования были получены следующие новые научные результаты:

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

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

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

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

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

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

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

1. Теоретическое обоснование свойств созданного метода маршрутизации по виртуальным координатам.

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

3. Метод организации распределенных хэш-таблиц на основе виртуальных координат и его применение для децентрализованного хранения виртуальных координат узлов.

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

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

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

Апробация результатов исследования. Основные результаты диссертации докладывались и обсуждались на:

• 30-й и 31-й конференциях молодых ученых и специалистов ИППИ* РАН «Информационные технологии и системы» (Россия, Звенигород, 2007; Россия, Геленджик, 2008).

• The 3rd international conference on wireless algorithms, systems and applications (USA, Dallas, 2008).

• > The 2nd IEEE international conference on self-adaptive and self-organizing systems (Italy, Venice, 2008).

• Всероссийской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (Россия, Москва, 2008).

• 4-й международной конференции по проблемам управления (Россия, Москва, 2009).

• Международном форуме «Высокие технологии XXI века» (Россия, Москва, 2006).

• Выставке информационных технологий и компьютеров «SofTool» (Россия, Москва, 2006).

• Международной выставке «Интертехсалон» (Россия, Москва, 2006).

• Международных выставках «Беспроводные и мобильные технологии» (Россия, Москва, 2006, 2007, 2008).

• Международных выставках «Передовые технологии автоматизации» (Россия, Москва, 2007, 2008).

• Международных выставках «ChipEXPO» (Россия, Москва, 2009, 2010).

• Международной выставке «Строительный сезон» (Россия, Москва, 2010). Публикации. По теме диссертации опубликовано 20 работ, в том числе 4 статьи в журналах из Перечня изданий, рекомендованных ВАК:

1. Баскаков С. С. Распределенный алгоритм автоматического выбора опорных узлов в беспроводных многоячейковых (mesh) сетях // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2008. № 4. С. 15-29.

2. Баскаков С. С. Надежность радиочастотного цифрового канала связи при крупномасштабном замирании и случайном разбросе параметров приемопередатчиков // Успехи современной радиоэлектроники. 2008. № 12. С. 47-54.

3. Баскаков С. С. Исследование способов повышения эффективности маршрутизации по виртуальным координатам в беспроводных сенсорных сетях Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2009. № 2. С. 112-124.

4. Baskakov S. Landmarks selection algorithm for virtual coordinates routing // Proceedings of the 3rd international conference on wireless algorithms, systems and applications. Dallas (USA), 2008. Vol. 5258 of Lecture notes in computer science. P. 17-28.

5. Baskakov S. Landmarks selection algorithm for wireless sensor networks // Proceedings of the 2nd IEEE international conference on self-adaptive and self-organizing systems. Venice (Italy), 2008. P. 361-369.

6. Баскаков С. С., Оганов В. И. Передача данных на базе технологии WirelessUSB//Электронные компоненты. 2005. №3. С. 109-113.

7. Баскаков С. С., Оганов В. И. Беспроводные сенсорные сети на базе платформы MeshLogic // Электронные компоненты. 2006. № 8. С. 65-69.

8. Баскаков С, С. Алгоритм автоматического выбора опорных узлов в беспроводных сенсорных сетях // Информационные технологии и системы: Сборник трудов Всероссийской конференции. Звенигород, 2007. С. 2-8.

9. Баскаков С. С. Беспроводные сенсорные сети: вопросы и ответы // Автоматизация в промышленности. 2008. № 4. С. 34-35.

10. Баскаков С. С. Стандарт ZigBee и платформа MeshLogic: эффективность маршрутизации в режиме «многие к одному» // Первая миля. 2008. № 2-3. С. 32-37.

11. Баскаков С. С. Эффективность метрик стоимости соединений стандарта ZigBee // Информационные технологии и системы: Сборник трудов Всероссийской конференции. Геленджик, 2008. С. 30-34.

12. Баскаков С. С. Модель беспроводного канала связи в условиях крупномасштабного замирания и случайного разброса параметров приемопередатчиков // Информационные технологии и системы: Сборник трудов Всероссийской конференции. Геленджик, 2008. С. 161-166.

13. Баскаков С. С. Методы увеличения срока службы распределенных беспроводных сетей сбора данных // Технические и программные средства систем управления, контроля и измерения: Сборник трудов Всероссийской конференции с международным участием. Москва, 2008. С. 930-936.

14. Баскаков С. С. Аппаратно-программная платформа MeshLogic для разработки беспроводных сенсорных сетей // Технические и программные средства систем управления, контроля и измерения: Сборник трудов Всероссийской конференции с международным участием. Москва, 2008. С. 937-939.

15. Баскаков С. С. Управление случайным доступом к среде с низкопотребляющим прослушиванием канала на базе стандарта IEEE 802.15.4 // Сборник трудов IV Международной конференции по проблемам управления. Москва, 2009. С. 1736-1743.

16. Баскаков С. С. Беспроводные системы сбора данных на базе радиочастотных модулей ML-Module-Z // Беспроводные технологии. 2009. № 1. С. 46-49.

17. Баскаков С. С. Опыт применения радиочастотных модулей MeshLogic для разработки беспроводных систем сбора данных // Беспроводные технологии. 2009. № 3. С. 44-47.

18. Баскаков С. С. Встраиваемые модули MeshLogic для построения беспроводных сенсорных сетей // Встраиваемые системы. 2009. № 3. С. 30-32.

19. Баскаков С. С. Оценка энергопотребления беспроводных узлов в сетях МеэИЕодю// Беспроводные технологии;, 2010. № 1. С. 28-31.

20. Баскаков С. С. Беспроводная система, мониторинга состояния; строительных конструкций//Беспроводные технологии. 2010. № 3. С. 52-54. Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы, включающего 94 наименования.

Выводы и заключение

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

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

2. Предложен новый алгоритм автоматического выбора произвольного количества опорных узлов, как при начальной инициализации сети, так и. I в процессе эксплуатации в случае возможного выхода из строя опорных узлов или- существенного изменения топологии" сети. Два- варианта' алгоритма позволяют получить равномерное распределение опорных узлов по площади (объему) покрытия сети или распределение по ее периметру (границе). Алгоритм имеет низкую сложность по времени и по памяти, а для сетей крупных масштабов является оптимальным по критериям сложности.

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

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

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

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

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

По результатам экспериментов сделаны следующие выводы:

1. Выполнение сформулированных в разделе 5.9 рекомендаций по выбору параметров метода позволяет обеспечить его высокую эффективность даже при малом количестве опорных узлов (порядка 4-8 штук).

2. При ненадежных каналах связи применение предложенных метрик стои-!< мости соединения и- перехода обеспечивает более точное решение задачи поиска оптимальных маршрутов по сравнению с методами на основе

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

3. Применение модифицированной метрики «ожидаемое количество передач» Мметх и метрики «ожидаемое общее количество передач» Меттх приводит примерно к одинаковым результатам по эффективности маршрутизации, но целесообразно применение последнего варианта, как более универсального.

4. Использование метрики стоимости перехода «ожидаемая остаточная емкость» Cerc, предназначенной для приближенного решения задачи маршрутизации с обеспечением максимального времени жизни сети, существенно увеличивает срок службы сети за счет динамической балансировки сетевой нагрузки, но при этом коэффициенты эффективности по энергии и по трафику снижаются незначительно по сравнению с показателями, полученными при поиске оптимальных маршрутов. При этом эффект от применения данной метрики увеличивается по мере повышения плотности размещения узлов в пространстве, так как возрастает удельная энергетическая емкость, приходящаяся на единицу площади (объема) покрытия сети.

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

207

1. Heinzelman W., Kulik J., Balakrishnan H. Adaptive protocols for information dissemination in wireless sensor networks // Proceedings of the 5th annual ACM/IEEE international conference on mobile computing and networking. Seattle (USA), 1999. P. 174-185.

2. Intanagonwiwat C., Govindan R., Estrin D. Directed diffusion: a scalable and robust communication paradigm for sensor networks // Proceedings of the 6th annual international conference on mobile computing and networking. Boston (USA), 2000. P. 56-67.

3. Heinzelman W., Chandrakasan A., Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks // Proceedings of the 33rd Hawaii international conference on system sciences. Maui (USA), 2000. P. 8020-8029.

4. Perkins C., Bhagwat P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers // ACM SIGCOMM computer communication review. 1994. Vol. 24, no. 4. P. 234-244.

5. Perkins C., Royer E. Ad-hoc on-demand distance vector routing // Proceedings of the 2nd IEEE workshop on mobile computing systems and applications. New Orleans (USA), 1999. P. 90-100.

6. Johnson D., Maltz D. Dynamic source routing in ad hoc wireless networks // Mobile computing / Ed. by T. Imielinski, H. Korth. 1996. Vol. 353. P. 153-181.

7. Karp B., Kung H. GPSR: greedy perimeter stateless routing for wireless networks // Proceedings of the 6th annual ACM/IEEE international conference on mobile computing and networking. Boston (USA), 2000. P. 243-254.

8. Ko Y., Vaidya N. Location-aided routing (LAR) in mobile ad hoc networks // Proceedings of the 4th ACM/IEEE international conference on mobile computing and networking. Dallas (USA), 1998. P. 66-75.

9. Routing with guaranteed delivery in ad.hoc wireless networks / P. Bose et al. //Wireless Networks. 2001. Vol. 7. P. 609-616.

10. Kuhn F., Wattenhofer R., Zollinger A. Worst-case optimal and average-case efficient geometric ad-hoc routing // Proceedings of the 4th ACM international symposium on mobile ad hoc networking and computing. Annapolis (USA), 2003. P. 267-278.

11. Geographical and energy-aware routing: a recursive data dissemination protocol for wireless sensor networks: Technical report 01-0023 / University of California (Los Angeles); Yu Y., Estrin D., Govindan R. 2001. lip.

12. Chang J.-H., Tassiulas L. Maximum lifetime routing in wireless sensor networks // IEEE/ACM transactions on networking. 2004. Vol. 12, no. 4. P. 609-619.

13. Park J., Sahni S. An online heuristic for maximum lifetime routing in wireless sensor networks // IEEE transactions on computers. 2006. Vol. 55, no. 4. P. 1048-1056.

14. Aslam J., Li Q., Rus D. Three power-aware routing algorithms for sensor networks // Wireless communications and mobile computing. 2003. Vol. 3, no. 2. P. 187-208.

15. Routing for network capacity maximization in energy-constrained ad-hoc networks / K. Kar et al. // Proceedings of the 22th annual joint conference of the IEEE computer and communications societies. San Francisco (USA), 2003. Vol. 1, no. 30. P. 673-681.

16. Misra A., Banerjee S. MRPC: maximizing network lifetime for reliable routing in wireless environments // Proceedings of the IEEE wireless communications and networking conference. Orlando, (USA), 2002. P. 800-806.

17. Distributed energy adaptive routing for wireless sensor networks / C. Ok et al. // Proceedings of the IEEE international conference on automation science and engineering. Scottsdale (USA), 2007. P. 905-910.

18. Puccinelli D., Sifakis E., Haenggi M. A cross-layer approach to energy balancing in wireless sensor networks // Workshop on networked embedded sensing and control. Notre Dame (USA), 2005. P. 1-17.

19. Dai H., Han R. A node-centric load balancing algorithm for wireless sensor networks // Proceedings of the IEEE global telecommunications conference. San Francisco (USA), 2003. Vol. 1. P. 548-552.

20. Beacon vector routing: scalable point-to-point routing in wireless sensornets / R. Fonseca et al. // Proceedings of the 2nd symposium on networked systems design and implementation. Boston (USA), 2005. P. 329-342.

21. Cao Q., Abdelzaher T. A scalable logical coordinates framework for routing in wireless sensor networks // Proceedings of the 25th IEEE international realtime systems symposium. Lisbon (Portugal), 2004. P. 349-358.

22. Cao Q., Abdelzaher T. Scalable logical coordinates framework for routing in wireless sensor networks // ACM transactions on sensor networks. 2006. Vol. 2, no. 4. P. 557-593.

23. Efficient hop ID based routing for sparse ad hoc networks / Y. Zhao et al. // Proceedings of the 13th IEEE international conference on network protocols. Boston (USA), 2005. P. 179-190.

24. GPS free coordinate assignment and routing in wireless sensor networks

25. A. Caruso et al. // Proceedings of the 24th annual joint conference of the IEEE computer and communications societies. Miami (USA), 2005. Vol. 1. P. 150-160.

26. Liu K., Abu-Ghazaleh N. Virtual coordinate backtracking for void traversal in geographic routing // Proceedings of the 5th international conference on ad-hoc networks and wireless. Ottawa (Canada), 2006. P. 46-59.

27. Data-centric storage in sensornets with GHT, a geographic hash table / S. Rat-nasamy et al. // Mobile networks and applications. 2003. Vol. 8, no. 4. P. 427-442.

28. GHT: a geographic hash table for data-centric storage / S. Ratnasamy et al. // Proceedings of the 1st ACM international workshop on wireless sensor networks and applications. Atlanta (USA), 2002. P. 78-87.

29. Al-Karaki J., Kamal A. Routing techniques in wireless sensor networks: a survey // IEEE wireless communications. 2004. Vol. 11, no. 6. P. 6-28.

30. Akkaya K., Younis M. A survey of routing protocols in wireless sensor networks // Ad hoc networks. 2005. Vol. 3, no. 3. P. 325-349.

31. Kleinrock L., Silvester J. Optimum transmission radii for packet radio networksjor why six is a magic number // Proceedings of national telecommunications conference. Birmingham (USA), 1978. P. 4.3.1-4.3.5.

32. Royer E., Toh C.-K. A review of current routing protocols for ad hoc mobile wireless networks // IEEE personal communications. 1999. Vol. 6, no. 2. P. 46-55.

33. Langendoen K., Reijers N. Distributed localization in wireless sensor networks: a quantitative comparison // Computer networks: the international journal of computer and telecommunications networking. 2003. Vol. 43, no. 4. P. 499-518.

34. Ad-hoc positioning system: Technical report 435 / Rutgers University; Nicules-cu D., Nath B. 2001. 11 p.

35. Relative location estimation in wireless sensor networks / N. Patwari et al. // IEEE transactions on signal processing. 2003. Vol. 51, no. 8. P. 2137-2148.

36. Seada K., Helmy A., Govindan R. On the effect of localization errors on geographic face routing in sensor networks // Proceedings of the 3rd international symposium on information processing in sensor networks. Berkeley (USA), 2004. P. 71-80.

37. Geographic routing made practical / Y.-J. Kim et al. // Proceedings of the USENIX symposium on networked systems design and implementation. Boston (USA), 2005. P. 217-230.

38. Geographic routing without location information / A. Rao et al. // Proceedings of the 9th annual international conference on mobile computing and networking. San Diego (USA), 2003. P. 96-108.

39. Liu K., Abu-Ghazaleh N. Aligned virtual coordinates for greedy routing in

40. WSNs // Proceedings of the 3rd IEEE international conference on mobile ad-hoc and sensor networks. Vancouver (Canada), 2006. P. 377-386.

41. Demoracski L. Fault-tolerant beacon vector routing for mobile ad hoc networks // Proceedings of the 19th IEEE international parallel and distributed processing symposium. Denver (USA), 2005. P. 279.2-279.9.

42. Virtual-coordinate-based delivery-guaranteed routing protocol in wireless sensor networks with unidirectional links / C.-H. Lin et al. // Proceedings of the 27th IEEE conference on computer communications. Phoenix (USA), 2008. P. 351-355.

43. Ng T., Zhang H. Predicting Internet network distance with coordinates-based approaches // Proceedings of the 21th annual joint conference of the IEEE computer and communications societies. New York (USA), 2002". P. 170-179.

44. Tang L., Crovella M. Virtual landmarks for the Internet // Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement. Miami Beach (USA), 2003. P. 143-152.

45. Distance labeling in graphs / C. Gavoille et al. // Journal of algorithms. 2008. Vol. 53, no. 1. P. 85-112.

46. Kleinberg J., Slivkins A., Wexler T. Triangulation and embedding using small sets of beacons // Proceedings of the 45th annual IEEE symposium on foundations of computer science. Rome (Italy), 2004. P. 444-453.

47. Metric embeddings with relaxed guarantees / I. Abraham et al. // Proceedings of the 46th annual IEEE symposium on foundations of computer science. Pittsburgh (USA), 2005. P. 83-100.

48. Robust routing for dynamic wireless networks based on stable embeddings / D. Tschopp et al. // Proceedings of information theory and applications workshop. La Jolla (USA), 2007. P. 124-131.

49. Robust geo-routing on embeddings of dynamic wireless networks / D. Tschopp et al. // Proceedings of the 26th IEEE conference on computer communications. Anchorage (USA), 2007. P. 124-131.

50. Papadimitriou C., Ratajczak D. On a conjecture related to geometric routing // Theoretical computer science. 2005. Vol. 334, no. 1. P. 3-14.

51. Kleinberg R. Geographic routing using hyperbolic space // Proceedings of the 26th IEEE conference on computer communications. Anchorage (USA), 2007. P. 1902-1909.

52. A scalable content addressable network / S. Ratnasamy et al. // Proceedings of the 2001 conference on applications, technologies, architectures, and protocols for computer communications. San Diego (USA), 2001. P. 161-172.

53. Tapestry: an infrastructure for fault-tolerant wide-area location and routing: Technical report 01-1141 / University of California (Berkeley); Zhao В., Kubi-atowicz J., Joseph A. D. 2001. 28 p.

54. Survey on distributed hash tables: Technical report 05 / Universidade de Coim-bra and Universidade de Lisboa; Araujo F., Rodrigues L. 2005. 23 p.

55. CHR: a distributed hash table for wireless ad hoc networks / F. Araujo et al. // Proceedings of the 25th IEEE international conference on distributed computing systems workshops. Columbus (USA), 2005. Vol. 6, no. 10. P. 407-413.

56. Landsiedel O., Lehmann K., Wehrle K. T-DHT: topology-based distributed hash tables // Proceedings of the 5th IEEE international» conference on peer-to-peer computing. Konstanz (Germany), 2005. P. 143-144.

57. Кнут Д. Э. Искусство программирования, томЗ. Сортировка и поиск: Пер. с англ. 2-е изд. М.: Издательский дом «Вильяме», 2007. 824 с.

58. Алгоритмы: построение и анализ: Пер. с англ. / Т. X. Кормен и др.. 2-е изд. М.: Издательский дом «Вильяме», 2007. 1296 с.

59. Q-NiGHT: adding QoS to data centric storage in non-uniform sensor networks: Technical report 06-16 / Universita di Pisa dipartimento di informatica; M. Al-bano et al.. 2006. 21 p.

60. Q-NiGHT: adding QoS to data centric storage in non-uniform sensor networks / M. Albano et al. // Proceedings of the 8th international conference on mobile data management. Mannheim (Germany); 2007. P. 166-173.

61. Zhao J., Govindan R. Understanding packet delivery performance in dense wireless sensor networks // Proceedings of the 1st international conference on embedded networked sensor systems. Los Angeles (USA), 2003. P. 1-13.

62. Woo A., Tong T., Culler D. Taming the underlying challenges of reliable mul-tihop routing in sensor networks // Proceedings of the 1st international conference on embedded networked sensor systems. Los Angeles (USA), 2003. P. 14-27.

63. Complex behavior at scale: an experimental study of low-power wireless sensor networks: Technical report 02-0013 / University of California (Los Angeles); D. Ganesan et al.. 2002. 11 p.

64. Reijers N., Halkes G., Langendoen K. Link layer measurements in sensor networks // Proceedings of the IEEE international conference on mobile ad-hoc and sensor systems. Fort Lauderdale (USA), 2004. P. 224-234.

65. The mistaken axioms of wireless-network research: Technical report 2003-467 / Dartmouth College; Kotz D., Newport C., Elliott C. 2003. 14 p.

66. Impact of radio irregularity on wireless sensor networks / G. Zhou et al. // Proceedings of the 2nd international conference on mobile systems, applications, and services. Boston (USA), 2004. P. 125-138.

67. Stepanov I., Rothermel K. On the impact of a more realistic physical layer on MANET simulations results // Ad hoc networks. 2008. Vol. 6, no. 1. P. 61-78.

68. A high-throughput path metric for multi-hop wireless routing / D. De Couto et al. // Proceedings of the 9th ACM international conference on mobile computing and networking. San Diego (USA), 2003. P. 134-146.

69. Draves R., Padhye J., Zill B. Routing in multi-radio, multi-hop wireless mesh networks // Proceedings of the 10th annual international conference on mobile computing and networking. Philadelphia (USA), 2004. P. 114-128.

70. Statistical model of lossy links in wireless sensor networks / A. Cerpa et al. // Proceedings of the 4th international symposium on information processing in sensor networks. Los Angeles (USA), 2005. P. 81-88.

71. Zuniga M., Krishnamachari B. Analyzing the transitional region in low power wireless links // Proceedings of the 1st annual IEEE communications society conference on sensor and ad hoc communications and networks. Santa Clara(USA), 2004. P. 517-526.

72. Zuniga M., Krishnamachari B. An analysis of unreliability and asymmetry in low-power wireless links // ACM transactions on sensor networks. 2007. Vol. 3, no. 2. P. 7.1-7.34.

73. Channel model at 868 MHz for wireless sensor networks in outdoor scenarios / J. Molina-Garcia-Pardo et al. // Proceedings of the international workshop on wireless ad-hoc networks. London (UK), 2005. P. 1-4.

74. Models and solutions for radio irregularity in wireless sensor networks / G. Zhou et al. // ACM transactions on sensor networks. 2006. Vol. 2, no. 2. P. 221-262.

75. Evaluation of efficient link reliability estimators for low-power wireless networks: Technical report 03-1270 / University of California (Berkeley); Woo A., Culler D. 2003. 20 p.

76. Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks / K. Seada et al. // Proceedings of the 2nd international conference on embedded networked sensor systems. Baltimore (USA), 2004. P. 108-121.

77. OMNeT-н- network simulation framework: сайт. URL: http://www.omnetpp.org/ (дата обращения: 14.10.2007).

78. Mobility framework for OMNeT++: сайт. URL: http://mobility-fw.sourceforge.net/ (дата обращения: 18.01.2007).

79. Kleinrock L., Tobagi F. Packet switching in radio channels: part I carrier sense multiple-access modes and their throughput-delay characteristics // IEEE transactions on communications. 1975. Vol. 23, no. 12. P. 1400-1416.

80. Прокис Дж. Цифровая связь: Пер. с англ. М.: Радио и связь, 2000. 800 с.

81. Ye W., Heidemann J., Estrin D. Medium access control with coordinated adaptive sleeping for wireless sensor networks // IEEE/ACM transactions on networking. 2004. Vol. 12, no. 3. P. 493-506.

82. Polastre J., Hill J., Culler D. Versatile low power media access for wireless sensor networks // Proceedings of the 2nd ACM conference on embedded networked sensor systems. Baltimore (USA), 2004. P. 95-107.

83. Performance of multihop wireless networks: shortest path is not enough / D. De Couto et al. // Proceedings of the first workshop on hot topics in networks. Princeton (USA), 2002. P. 83-88.

84. ZigBee specification 2006 Электронный ресурс.: ZigBee Alliance [сайт]. 2006. URL: http://www.zigbee.org/ (дата обращения: 16.01.2007).

85. EmberZNet application developer's guide Электронный ресурс.: Ember Corporation [сайт]. 2007. URL: http://www.ember.com/ (дата обращения: 11.01.2008).