Содержание к диссертации
Введение
Глава 1. Состояние вопроса и постановка задачи исследования . 18
1.1. Введение 18
1.2. Модель беспроводной сети 24
1.3. Задачи маршрутизации 27
1.4. Обзор методов маршрутизации 31
1.5. Цель и задачи исследования 44
Глава 2. Маршрутизация по виртуальным координатам 46
2.1. Введение 46
2.2. Общее описание метода 52
2.3. Алгоритм поиска маршрута 54
2.4. Свойства алгоритма поиска маршрута 59
2.5. Оценка расстояния по виртуальным координатам 66
2.6. Распределенные хэш-таблицы на основе виртуальных координат . 68
2.7. Распределенная база данных виртуальных координат узлов . 78
2.8. Выводы 80
Глава 3. Выбор опорных узлов 82
3.1. Введение 82
3.2. Централизованный алгоритм выбора опорных узлов 87
3.3. Распределенный алгоритм выбора опорных узлов 89
3.4. Примеры работы алгоритма выбора опорных узлов 95
3.5. Оценка сложности алгоритма выбора опорных узлов 96
3.6. Выводы 104
Глава 4. Модель канала связи и метрики маршрутизации 106
4.1. Введение 106
4.2. Модель беспроводного канала связи 107
4.3. Метрики стоимости соединения 131
4.4. Метрики виртуального расстояния 140
4.5. Метрики прогресса 142
4.6. Выводы 148
Глава 5. Результаты имитационного моделирования 150
5.1. Введение 150
5.2. Среда и условия имитационного моделирования 151
5.3. Модель энергопотребления узла 156
5.4. Критерии оценки эффективности маршрутизации 159
5.5. Маршрутизация при идеальном канале связи 164
5.6. Маршрутизация при реальном канале связи 172
5.7. Сравнение с другими методами маршрутизации 181
5.8. Оценка расстояния по виртуальным координатам 197
5.9. Выводы 200
Выводы и заключение 204
Список литературы 207
- Обзор методов маршрутизации
- Распределенные хэш-таблицы на основе виртуальных координат
- Распределенный алгоритм выбора опорных узлов
- Модель беспроводного канала связи
Введение к работе
Актуальность темы. В последнее время активное развитие получили технологии беспроводной связи, что в сочетании с достижениями в области микропроцессорной и измерительной техники сделало возможным создание нового класса систем передачи данных - беспроводных сенсорных сетей. Беспроводная сенсорная сеть (БСС) представляет собой распределенную, самоорганизующуюся и устойчивую к отказу сеть большого числа (до нескольких десятков тысяч) автономных электронных узлов, способных обмениваться сообщениями и ретранслировать их по беспроводному каналу связи.
Беспроводные сенсорные сети могут быть эффективно использованы для решения различных прикладных задач, связанных с распределенным сбором, обработкой и анализом информации в таких областях, как автоматизация зданий, промышленная автоматика, безопасность и оборона, мониторинг окружающей среды, здравоохранение и т.п. Поскольку в общем случае БСС являются одноранговыми сетями с многоячейковой топологией, в которых все узлы равноправны, имеют автономные источники питания и могут выступать в роли ретранслятора пакетов информации, для БСС чрезвычайно актуальным является решение следующих двух задач:
Задача поиска оптимальных маршрутов. Оптимальным считается маршрут доставки пакетов информации от узла-отправителя до узла-назначения, требующий минимальных суммарных затрат ресурсов (например, энергии) входящих в него узлов.
Задача маршрутизации с обеспечением максимального времени жизни сети. Под временем жизни сети понимается срок ее эксплуатации до первого выхода из строя одного из узлов по причине истощения автономного источника питания. Решение этой задачи заключается в балансировке сетевого трафика в процессе передачи пакетов по всем необходимым маршрутам по всей сети в целом и направлено на исключение образования точек повышенной нагрузки в узлах, входящих одновременно в несколько маршрутов.
Методы решения указанных задач должны поддерживать типы трафика «многие-к-одному» (отправителями данных могут быть все узлы сети, а получателем является только один из них) и «многие-ко-многим» (отправителями и получателями информации могут быть любые узлы сети), иметь распределенную реализацию с низкой алгоритмической сложностью и обладать высокой масштабируемостью (объем служебного трафика и требования к памяти узлов должны минимально или совсем не зависеть от общего размера сети).
Проблеме маршрутизации в БСС посвящено множество исследований, но предложенные в них подходы либо не решают сформулированные задачи при типах трафика «многие-к-одному» и «многие-ко-многим», либо не обладают свойством масштабируемости и имеют высокую алгоритмическую сложность. В области БСС одним из наиболее перспективных считается принцип маршрутизации по виртуальным координатам (ВК-маршрутизации), который был предложен относительно недавно и показал высокую эффективность, но из-
вестные основанные на нем методы предназначены только для решения первой задачи маршрутизации и имеют ряд недостатков, что ограничивает их практическое применение. Следовательно, крайне актуальной является разработка нового метода ВК-маршрутизации для решения обеих задач маршрутизации в БСС, лишенного недостатков существующих подходов.
Цель исследования - создание нового метода маршрутизации по виртуальным координатам для поиска оптимальных маршрутов и маршрутизации с обеспечением максимального времени жизни сети в реальном масштабе времени в беспроводных сенсорных сетях высокой размерности со стационарной многоячейковой топологией.
Задачи исследования. Для достижения поставленной цели необходимо выполнить следующее:
Проанализировать достоинства и недостатки известных методов маршрутизации пакетов в БСС. Показать новизну поставленных задач и выбранного подхода к решению на основе использования виртуальных координат. Теоретически обосновать свойства предлагаемого подхода к ВК-маршрутизации.
Исследовать влияние количества опорных узлов, принципа их распределения по площади покрытия сети и параметров метрики виртуального расстояния на эффективность ВК-маршрутизации и предложить способы ее повышения.
Разработать алгоритм автоматического выбора опорных узлов как при начальной инициализации сети, так и при возможном выходе из строя одного или нескольких опорных узлов в процессе ее эксплуатации.
Разработать метод организации сетевой службы установки соответствия между адресами узлов и их виртуальными координатами.
Разработать метрики стоимости соединений, которые более адекватно отражают особенности применяемых в БСС маломощных радиоканалов, для вычисления виртуальных координат при ненадежных каналах связи.
Разработать метрики прогресса для оптимизации затрат ресурсов узлов как для каждого маршрута в отдельности, так и с балансировкой сетевой нагрузки, применение которых повысит эффективность принципа ВК-маршрутизации при сохранении его преимуществ.
С помощью имитационного моделирования выполнить анализ свойств и характеристик разработанного метода в условиях ненадежных каналов связи, а также сравнить его эффективность с другими известными подходами.
Объектом исследования являются беспроводные сети передачи информации.
Предметом исследования является маршрутизация пакетов в беспроводных сенсорных сетях со стационарной топологией.
Методы исследования. Для решения поставленных задач в работе используются методы теории вероятности, математической статистики, теории графов, теории связи и имитационного моделирования.
Научная новизна. При проведении исследования были получены следующие новые научные результаты:
Теоретически доказаны основные свойства созданного метода маршрутизации по виртуальным координатам, согласно которым он имеет высокую масштабируемость и гарантирует отсутствие циклов при поиске маршрутов. Получены теоретические оценки зависимости надежности ВК-марш-рутизации от качества связи между узлами, количества и вида распределения опорных узлов, а также размера сети.
Предложен новый алгоритм автоматического выбора произвольного количества опорных узлов, отличающийся тем, что позволяет получать различные виды распределения опорных узлов по площади покрытия сети и имеет низкую алгоритмическую сложность. Показано, что по критериям сложности алгоритм является оптимальным для ВК-маршрутизации в сетях крупных размеров.
Разработан новый метод организации распределенных хэш-таблиц на основе виртуальных координат. Предложенная на его базе реализация сетевой службы определения соответствия между адресом узла и его виртуальными координатами отличается низкими затратами памяти узлов.
Разработан набор из четырех метрик стоимости соединений, две из которых являются модификацией ранее известных, а остальные получены впервые. Предложенные метрики более точно оценивают накладные расходы ресурсов узлов из-за возможных потерь пакетов в реальных маломощных цифровых радиоканалах, отличающихся значительной вариацией и асимметрией качества связи. Следствием этого является повышение надежности ВК-маршрутизации.
Предложены новые метрики прогресса, применение которых повышает эффективность режима минимизации расстояния при ВК-маршрутизации по ненадежным каналам связи. В результате обеспечивается более точное решение задачи поиска оптимальных маршрутов в реальных условиях эксплуатации БСС.
Впервые поставлена задача максимизации времени жизни сети при маршрутизации по виртуальным координатам и предложено ее эвристическое решение с помощью метрики прогресса, использующей только локально доступную информацию, что обеспечивает высокую масштабируемость и низкую алгоритмическую сложность.
На базе разработанных имитационных моделей экспериментально исследовано влияние различных параметров на характеристики ВК-маршрутизации, а также предложен ряд практических рекомендаций по повышению ее эффективности, для оценки которой используется 8 критериев, описывающих надежность, латентность и длину маршрутов, полноту использования энергетических ресурсов узлов, нагрузку на каналы связи и общий срок службы сети. Экспериментально подтверждены эффективность разработанных метрик при ненадежных каналах связи и преимущества разработанного метода по сравнению с известными аналогами.
Основные положения, выносимые на защиту:
Теоретическое обоснование свойств созданного метода маршрутизации по виртуальным координатам.
Алгоритм автоматического выбора опорных узлов, обладающий низкой сложностью по времени и по памяти.
Метод организации распределенных хэш-таблиц на основе виртуальных координат и его применение для децентрализованного хранения виртуальных координат узлов.
Набор метрик стоимости соединений и прогресса для поиска оптимальных маршрутов и маршрутизации с обеспечением максимального времени жизни сети по виртуальным координатам.
Результаты экспериментального обоснования эффективности разработанного метода и его преимуществ по сравнению с известными аналогами. Практическая ценность и реализация результатов работы. На основе
разработанного метода ВК-маршрутизации могут быть созданы новые протоколы маршрутизации для БСС крупных масштабов. Один из вариантов подобного протокола маршрутизации реализован в виде встроенного программного обеспечения беспроводных узлов и используется на практике в стеке сетевых протоколов российской аппаратно-программной платформы 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 таблиц.
Обзор методов маршрутизации
В первую очередь выполним обзор основных подходов к решению задачи поиска оптимальных маршрутов, для удобства разделив их на 3 группы по аналогии с [28, 29], а затем - варианты решения задачи максимизации времени жизни сети.
Маршрутизация без иерархии ориентирована на применение в сетях из равноправных узлов, в которых отсутствует какая-либо инфраструктура или узлы со специальными функциями.
Одни из первых алгоритмов маршрутизации (например, DSDV [4]), разработанные для мобильных эпизодических сетей, использовали специальные таблицы, которые хранились в каждом из узлов сети и содержали информацию об оптимальных маршрутах между данным узлом и любым другим. Так как топология сети и свойства среды передачи постоянно изменяются, содержимое таблиц маршрутизации периодически обновляется путем обмена специальными пакетами. Достоинство подобных алгоритмов заключается в-том, что информация о возможных маршрутах доступна в любой момент времени и поддерживаются произвольные типы трафика. Однако первоначальная инициализация таблиц маршрутов требует передачи 0(п2) сообщений, а также постоянного хранения каждым узлов служебных данных в объеме 0(п), что делает невозможным применение этих алгоритмов «в БСС крупных размеров.
Методы маршрутизации реактивного типа (например, AODV [5], DSR [6]), также изначально созданные для мобильных эпизодических сетей, выполняют поиск оптимального маршрута (1.5) между заданными узлами s и t только при возникновении необходимости (по запросу). Однако первоначальное обнаружение маршрута и его восстановление вхлучае изменения топологии сети приводят к передаче 0(2п) сообщений [31], поэтому их эффективность очень сильно зависит от типа трафика, а также количества источников и потребителей информации. Следовательно, они также не отвечают требованию масштабируемости.
Для создания ряда специализированных методов маршрутизации в БСС была учтена следующая их особенность: узлы БСС выполняют одинаковый набор функций и взаимодействуют друг с другом для выполнения единой задачи сбора показаний от множества датчиков. Если, например, сенсорные узлы измеряют какие-либо физические параметры окружающей среды (температура, влажность и т.д.), то велика вероятность того, что близко расположенные узлы зафиксируют похожие значения, поэтому передавать базовой станции показания от каждого отдельного узла нецелесообразно из-за избыточности данных. В результате была предложена новая концепция маршрутизации - data-centric (маршрутизация, ориентированная на информацию), которая отличается от традиционного node-centric (маршрутизация, ориентированная на устройства) подхода следующим. Базовая станция передает в определенные области территории покрытия сети запросы, в которых описано какого рода информация или события ее интересуют. Находящиеся в этих областях узлы, собрав необходимую информацию или зафиксировав событие нужного типа, на локальном уровне обмениваются друг с другом имеющимися данными для повышения достоверности и уменьшения избыточности, а затем передают базовой станции только одно сообщение с обобщенными показаниями. Такой принцип позволяет значительно сократить объем сетевого трафика и, как следствие, уменьшить энергопотребление. Классическими примерами реализации этого подхода являются группа протоколов Sensor Protocols for Information via Negotiation (SPIN) [1] и Directed Diffusion [2].
Очевидно, что области применения методов маршрутизации на основе data-centric подхода ограничены приложениями с типом трафика «многие-к-одному», и их можно рассматривать как специализированные решения для сетей распределенного сбора данных с большой избыточностью сенсорных узлов. Применение их в одноранговых сетях с типом трафика «многие-ко-многим», а также в системах, в которых сообщения от каждого узла важны, нецелесообразно.
Таким образом, существующие методы маршрутизации в сетях без иерархии позволяют находить пути с минимальной стоимостью, но либо не поддерживают оба типа трафика («многие-к-одному» и «многие-ко-многим»), либо не обладают высокой масштабируемостью.
Методы маршрутизации этого типа создают иерархическую структуру сети, что является известным способом обеспечения масштабируемости системы. Идею иерархической маршрутизации опишем на примере одной из первых реализаций этого подхода в БСС - Low-Energy Adaptive Clustering Hierarchy (LEACH) [3].
Сеть разделяется на множество групп узлов (кластеров), которые состоят из оконечных узлов и головных узлов кластера. Головные узлы кластера выбираются среди обычных узлов случайным образом в количестве порядка 5% от п, при этом периодически выполняется смена головных узлов для равномерного распределения нагрузки по всем узлам сети. Маршрутизация выполняется в 2 этапа: оконечные узлы передают пакеты головному узлу своего кластера, а тот уже выполняет объединение пакетов (агрегацию данных) и отправляет результат непосредственно базовой станции, что позволяет значительно сократить количество передаваемых базовой станции пакетов. Дополнительная экономия энергии достигается использованием внутри кластера множественного доступа с временным разделением каналов1, для которого расписание составляет головной узел кластера, а для уменьшения коллизий между кластерами применяется кодовое разделение каналов2.
Распределенные хэш-таблицы на основе виртуальных координат
При этом вместо непосредственного использования ключа к в качестве индекса элемента массива адрес ячейки вычисляется по значению ключа к с помощью специальной хэш-функции.
В БСС хэш-таблицы могут использоваться для хранения различного рода информации (например, собранные показания датчиков или отчеты о зафиксированных событиях). Однако централизованное хранение хэш-таблицы на некотором выделенном узле имеет ряд существенных недостатков, в частности: низкая устойчивость к отказам, плохая масштабируемость и высокая вероятность перегрузки системы. Следовательно, более целесообразным решением является организация распределенной хэш-таблицы на основе сети из множества узлов, которые выступают в роли ячеек памяти. В этом случае задача хэш-функции заключается в определении соответствия между ключом к и узла, ответственного за хранение значения d.
Системы распределенных хэш-таблиц CAN [56], Chord [57], Tapestry [58] и другие (Pastry, Viceroy, Koorde, D2B, TOPLUS [59]) были разработаны с целью создания децентрализованных пиринговых сетей для хранения и обмена различного рода информацией в масштабах сети Интернет. Основная их идея заключается в том, что поверх физической сети организуется логическая сеть, между узлами которой и выполняется распределение пар (ключ, значение), а отличие этих систем между собой определяется структурой (топологией) логической сети и способом маршрутизации в ней.
В перечисленных выше схемах распределенных хэш-таблиц логическая топология сети не имеет ничего общего с физической и никак не учитываются особенности поиска маршрутов в физической сети, поэтому применение этих систем в беспроводных эпизодических и сенсорных сетях приведет высоким накладным расходам и, следовательно, к снижению их эффективности. Тем не менее, вопрос организации распределенных хэш-таблиц именно в бес- проводных сенсорных и эпизодических сетях, существенно отличающихся от сети Интернет, не получил серьезного внимания исследователей; фактически единственными исключениями являются работы [26, 27, 60, 61].
Для,устранения указанного недостатка в [26, 27] предложено использовать связь между географическими координатами узлов и топологией сети -организовать распределенную географическую хэш-таблицу, опираясь на метод географической маршрутизации GPSR [7]. С помощью хэш-функции значение ключа к преобразуется їв координаты h(k), которые в общем случае не соответствуют ни одному из узлов сети, поэтому узлом-хранилищем назна-чается ближайший к точке h(k) узел, а периметром хранилища - множество окружающих точку h{k) узлов планарного подграфа сети.
Идея географических хэш-таблиц получила дальнейшее развитие в системе Cell Hash Routing [60]; в которой площадь покрытия сети разбивается на множество кластеров, и между ними выполняется распределение хранимой информации с помощью GPSR.
Однако географические хэш-таблицы имеют те же недостатки, что и. лежащий в их основе принцип маршрутизации, поэтому в настоящей работе предлагается система распределенных хэш-таблиц на основе виртуальных координат. Для построения распределенной хэш-таблицы на основе виртуальных координат необходима хэш-функция, преобразующая значение ключа к в вектор виртуальных координат h(k) = { г(&)К=і- Таким образом, в общем случае хэш-функция Н представляет собой отображение пространства ключей К с размерностью \К\ = пк в гг-мерное пространство виртуальных координат: По аналогии с системами географических распределенных хэш-таблиц, узлом, ответственным за хранение информации, связанной с ключом к, на значается узел, наиболее близко расположенный к точке h(k). Очевидно, что выходом хэш-функции могут быть координаты узла, которого реально в сети не существует, поэтому в механизм обработки пакета маршрутизации (алгоритм 1) необходимо внести следующие изменения (алгоритм 3): если адрес узла-получателя t не задан, но его виртуальные координаты t совпадают с виртуальными координатами v текущего узла, то узел v прекращает процесс маршрутизации и приступает к обработке принятого пакета (строки 6-9); если пакет находится в режиме ограниченного широковещательного распространения, на границе которого лежит текущий узел v, то v обрабатывает принятый пакет (строки 14-18). Если сеть находится в стационарном состоянии, то при операциях записи, чтения и удаления данных в хэш-таблице обращение выполняется к одному и тому же узлу, так как операторы Put(fc, d), Get(A;; d) и Delete(&) используют одну и туже хэш-функцию с одинаковыми входными значениями. Очевидно; что возможно отображение нескольких ключей в одну точку пространства виртуальных координат (коллизия), поэтому в ячейках таблицы (узлах сети) сохраняются как значения, так и соответствующие ключи для установки однозначного соответствия. Следующая теорема описывает основные свойства, которыми должна обладать «идеальная»1 система распределенных хэш-таблиц на основе виртуальных координат.
Распределенный алгоритм выбора опорных узлов
Распределенная версия алгоритма заключается в том, что каждый узел v Є V выполняет одинаковый набор действий, то есть какого-либо централизованного управления не требуется. Именно этот вариант алгоритма предназначен для применения на практике.
После включения каждый узел v присваивает своему вектору виртуальных координат начальное значение v = {vt = oo} rl5 очищает таблицу сетевого окружения1 и запускает таймеры для двух независимых периодических процессов: процесс «локальный обмен сигнальными пакетами» с периодом ti; процесс «выбор опорных узлов» с периодом tis. На данном этапе всех узлы сети эквивалентны и должны распределенным способом выбрать среди себя пь опорных узлов.
В ходе «локального обмена сигнальными пакетами» каждый узел с периодом t[ передает специальный широковещательный пакет, в котором содержатся его собственные координаты и координаты узлов из его таблицы сете 1 Специальная служебная таблица, в которой узел хранит необходимую информацию о своих непосредственных соседях и, возможно, о соседях второго уровня вого окружения. Данная процедура является типичной для БСС, поскольку в процессе такого обмена узлы поддерживают в актуальном состоянии информацию о сетевом окружении. В данном случае эти пакеты используются также для вычисления и обновления виртуальных координат, как и во всех других методах ВК-маршрутизации, но включают небольшой объем дополнительной информации, описанной ниже.
Величина периода ti определяет скорость реакции на локальные изменения в топологии сети, поэтому может рассматриваться как независящий от масштаба сети параметр метода ВК-маршрутизации. Процесс «выбор опорных узлов» заключается в том, что с периодом tis узел проверяет необходимость назначения одного из опорных узлов. При каждом срабатывании таймера узел v EV выполняет.следующую последовательность действий. Если узел v уже является опорным узлом или узлом-инициатором, то текущая итерация процесса прекращается. Если Ь( ) = пс, то есть узлу v известны все опорные узлы и они находятся в активном состоянии, то данная итерация алгоритма также завершается. Если узлу v не известно ни одного опорного узла, то есть L{v) = 0, то он назначает себя узлом-инициатором процесса выбора опорных узлов. На этом текущая итерация алгоритма завершается. Если узел-инициатор или один (или более) опорных узлов уже присутствуют в сети, то порядковый номер очередного выбираемого опорного узла равен Далее узел v вычисляет свое количество «голосов» на получение статуса Если узлы v и и обладают одинаковым количество «голосов», то неоднозначность разрешается описанным выше способом на основе их адресов. Заметим, что при принятии решения о назначении себя опорным узел сравнивает свое количество «голосов» с максимальным количеством «голосов» среди его соседей. Следовательно, если нет необходимости хранить информацию о сетевом окружении для других задач (например, для маршрутизации пакетов), то узлу достаточно в ходе локального обмена сигнальными пакетами запоминать информацию только о соседнем узле, имеющем максимальное значение функции голосования. Тогда требования к объему памяти значительно сокращаются, что будет показано ниже. Если v назначил себя к-ым опорным узлом, то в своих последующих сигнальных пакетах он также сообщает количество «голосов» и множество L(y), которые действовали на момент его назначения опорным узлом. Обозначим эти величины как p(v) и L(v) соответственно. Описанная процедура выбора опорного узла может выполняться периодически или асинхронно при.обнаружении отказа одного из опорных узлов. При этом минимальное допустимое значение периода tis определяется величиной задержки распространения сигнального пакета от опорного узла до остальных узлов сети в наихудшем случае. Очевидно, что неизбежна проблема присутствия в сети нескольких опорных узлов с одинаковыми порядковыми номерами, поскольку узлы опираются только на локальную информацию при принятии решения о своем назначении. Поэтому предлагается алгоритм установки приоритетов для устранения избыточных опорных узлов распределенным способом. При приеме очередного сигнального пакета от соседнего узла w узел v получает следующую информацию об узле w: вектор виртуальных координат w = {wi} ; множество номеров известных опорных узлов L(w); информацию об известных опорных узлах с номерами г Є L(w): количество «голосов» Pi{w), полученное при назначении k(w); множество номеров активных опорных узлов Li(w), использованных при вычислении Рі(ги). Получив сигнальный пакет от w, узел v выполняет алгоритм 5 относительно каждого г-го опорного узла (г = 1 : п). Прокомментируем выполняемые действия. В строках 2-6 указано, что если узел v, как и k{w), является опорным узлом с номером г и в момент своего назначения имел меньшее количество «голосов», то он прекращает функционировать в качестве опорного узла. Если у обычного узла v нет информации по г-ому опорному узлу, то он «соглашается» принять узел k(w) в качестве опорного только, если у него (узла v) меньше «голосов». При этом-для расчета используется множество узлов Li{w) (строки 7-10).
Модель беспроводного канала связи
В большинстве работ задачи маршрутизации в БСС рассматриваются с использованием упрощенной модели беспроводного канала связи, согласно которой пакет успешно принимается только при условии, что расстояние между передатчиком и приемником меньше некоторого фиксированного радиуса радиосвязи г, в противном случае пакет игнорируется. Назовем данную модель бинарной, так как в ней вероятность успешного приема пакета принимает только одно из двух возможных дискретных значений: 0 или 1.
Однако многочисленные экспериментальные исследования (в частности, [66-70]) характеристик маломощных беспроводных каналов связи показали, что диапазон приема условно разделен на 3 области: область надежного приема; переходная область; область отсутствия связи. В области надежного приема соединения обеспечивают высокое и стабильное качество связи, в то время как переходная область отличается значительной вариацией и асимметрией показателей надежности. При этом протяженность переходной области может быть значительно больше диапазона надежного приема, поэтому возможно проявление указанных эффектов в большинстве беспроводных соединений.
В [68, 71-73] показано, что переходная область может оказать существенное негативное влияние на характеристики верхних сетевых уровней, в первую очередь - на эффективность маршрутизации. Например, в [72] обнаружено, что при неравномерности свойств канала в различных направлениях передачи географическая маршрутизация (например, GPSR [7]) демонстрирует худшие характеристики, чем традиционная маршрутизация реактивного типа (например, AODV [5] и DSR [6]), опирающаяся исключительно на топологию, сети и длину кратчайших путей в количестве промежуточных соединений. С другой стороны, использование информации о качестве связи в переходной области может дать и преимущества. Например, в работе [74] предложена метрика «ожидаемое количество передач» ЕТХ1, которая обеспечивает большую пропускную способность по сравнению с обычной метрикой «минимальное количество переходов» в стационарных беспроводных сетях, в которых узлы неподвижны или мобильны в минимальной степени [75].
Таким образом, крайне важно использовать адекватную модель беспроводного канала связи на этапе разработки и исследования методов решения задач маршрутизации в БСС. На основе этой модели следует разработать метрики стоимости соединений, которые будут более полно отражать их особенности и, следовательно, обеспечивать высокую эффективность ВК-маршрути-зации в реальных условиях эксплуатации. Кроме того, применение при моделировании реалистичной модели радиоканала позволит более точно предсказывать свойства и показатели качества обслуживания сети, которые будут иметь место при развертывании системы в полевых условиях.
Множество исследований было проведено с целью создания методов моделирования и инструментов проектирования систем сотовой связи и сетей передачи данных (например, проекты COST 207 и COST 259). Однако в данных проектах предметом изучения являются строго определенные частотные диапазоны, методы модуляции, способы кодирования и т.д. При этом критерии проектирования и условия эксплуатации систем персональной радиосвязи Expected transmission count таковы, что эффекты переходной области не оказывают на них существенного влияния. Следовательно, эти модели,неприменимы для исследования БСС.
В работах [67, 72, 76] предлагаются различные эмпирические модели-описания характеристик радиочастотного канала, основанные на экспериментальных данных. Несомненно, эти модели повышают реалистичность выполненных оценок, но они не предлагают фундаментального объяснения базовых причин наблюдаемых явлений. Кроме того, применимость подобных моделей во многом ограничена пределами параметров конкретных приемопередатчиков- и условий окружения, которые имели место при снятии эмпирических характеристик для построения моделей.
Более системный анализ перечисленных эффектов содержится в работах [77, 78], в которых с помощью аналитических выражений описана зависимость надежности и асимметричности соединений от параметров приемопередатчика (значения и разброс выходной мощности и уровня шума, тип манипуляции, метод кодирования и др.) и среды распространения радиоволн (показатель степени потерь в тракте, величина замираний и др.). Используемая в настоящей диссертации модель беспроводного канала основана именно на работах [77, 78], но расширена рядом дополнительных параметров и адаптирована для описания физического уровня стандарта IEEE 802.15.4 вусловиях замирания и при наличии случайных отклонений параметров приемопередатчиков от номинальных значений. Кроме того, в настоящей работе получены более точные выражения для математического ожидания и дисперсии, вероятности успешного приема пакета, а также впервые приведены формулы для параметров распределения величины асимметрии качества связи в зависимости от отношения сигнал/шум на входе приемника узла.
Как уже было сказано, большинство беспроводных соединений в БСС может быть подвержено влиянию эффектов переходной! области. Вариация надежности соединений в различных направлениях передачи вызвана неравномерностью затухания сигнала, причинами которой являются: крупномасштабные и мелкомасштабные замирания; неравномерность диаграмм направленности антенн; препятствия на пути прохождения сигнала, вызывающие различное поглощение сигнала. Асимметрия качества связи означает, что вероятность успешного приема узлом v пакета от узла w не равна вероятности успешной передачи в обратном направлении. Асимметрия соединений обусловлена тем, что узлы имеют различные значения выходной мощности и уровня шума. При этом отклонения параметров приемопередатчиков от номинальных значений описываются случайным законом распределения, характеристики которого зависят от технологических особенностей производства приемопередатчиков и аппаратной реализации узлов. Кроме того, в процессе функционирования уровень шума может изменяться в соответствии с локальной помеховой обстановкой,и температурой окружающей среды.
