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

• Баскаков, Сергей Сергеевич
• кандидат технических наук
• 2011

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

Введение.

Глава 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

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

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