Содержание к диссертации
Введение
1. Маршрутизация в сетях с переменной топологией. современное состояние проблемы 10
1.1 Введение 10
1.2 Алгоритмы маршрутизации для сетей с переменной топологией 12
1.3 Алгоритм tora 15
1.4 Сенсорные сети 17
1.5 Вероятностный подход к управлению информационными потоками 20
1.6 Сети с ограниченной мобильностью 25
1.6.1 Определение 25
1.6.2 Лавинная рассылка в сетях с ограниченной мобильностью 27
1.6.3 Случайные блуждания в сетях с ограниченной мобильностью 28
1.7 Мобильные сети с ограниченно-подвижными отключаемыми узлами (мо-сети) 30
1.7.1 Определение 30
1.7.2 Задачи маршрутизации в МО-сети 31
Выводы по ГЛАВЕ 34
2. Анализ задачи маршрутизации данных в мо-сети 36
2.1 Концепция самоорганизации в мо-сети 36
2.1.1 Определение самоорганизации сети 36
2.1.2 Общие положения 36
2.1.3 Уровни самоорганизации 37
2.1.4 Работа сети в начальный период времени 40
2.2 Математическая модель мо-сети (мо-модель) 42
2.2.1 Назначение модели 42
2.2.2 Общее описание МО-модели 43
2.2.3 Частные случаи МО-моделей 46
2.2.4 Функции узла-координатора 47
2.2.5 История наблюдений узла 48
2.2.6 Вычисление параметров МО-модели 50
2.2.7 Метрики применимые с МО-моделью 56
2.3 О технико-экономическом обосновании предложенной концепции, математической модели и алгоритмов на их основе 66
Выводы по ГЛАВЕ 68
3. Применение мо-модели для управления медленным трафиком 69
3.1 Основные положения 69
3.1.1 Задача доставки медленного трафика 69
3.1.2 Методика самоорганизации 69
3.1.3 Функционирование сети с «медленным трафиком», агрегирование 71
3.1.4 Маршрутизация в условиях выхода из строя части узлов 74
3.2 Служебные алгоритмы, структуры данных и особенности реализации 76
3.2.1 Требования к оборудованию 76
3.2.2 Структуры данных. 77
3.2.3. Процедуры сбора данных для истории наблюдений 80
3.2.4. Лавинные процессы 83
3.2.5 Алгоритмы доставки данных, ограниченного ожидания, агрегирования 86
3.3. Разработка имитационной модели мобильной сети 91
3.4. Методики численных экспериментов 97
3.5. Результаты численных экспериментов 99
Выводы по главе 107
4. Разработка алгоритмов установления устойчивого канала связи и межкластерной маршрутизации 108
4.1. Установление устойчивого канала связи для непрерывной трансляции потока данных 108
4.1.1 Постановка задачи 108
4.1.2 Характеристики связей, существенные при построении УКС. 109
4.1.3 Определение параметров стабильности связей 110
4.1.4 Построение УИС 111
4.1.5 Методики и результаты численных экспериментов 115
4.2. Межкластерная маршрутизация 126
4.2.1 Особенности задачи межкластерной маршрутизации 126
4.2.2 Лавинная рассылка 127
4.2.3 Случайные блуждания 128
4.2.4 Ветвящиеся случайные блуждания 130
4.2.5 «Гибридный» алгоритм RWSM + BRW5M в составе модифицированного алгоритма EBAS 131
4.2.6 Результаты моделирования 136
Выводы по главе 143
Заключение 144
Список использованных источников
- Алгоритмы маршрутизации для сетей с переменной топологией
- Работа сети в начальный период времени
- Функционирование сети с «медленным трафиком», агрегирование
- Определение параметров стабильности связей
Введение к работе
В последние несколько лет происходит активное развитие сетей с переменной топологией. В первую очередь это относится к различным видам беспроводных мобильных и сенсорных сетей. Беспроводные мобильные сети, сети MESH внедряются и в военные технологии и во многие сферы гражданского применения, производя в некоторых случаях в этих областях буквально революцию. Примером могут служить сенсорные сети, позволившие обеспечить контроль над различными объектами наблюдения с такой оперативностью и на таких территориях, которые ещё недавно казались принципиально недостижимыми (разумеется, при использовании прежних технологий). И при этом обеспечивается непревзойдённая надёжность, позволяющая таким сетям успешно функционировать буквально годами без малейшего внимания со стороны обслуживающего персонала.
Ещё одним достижениям стала беспрецедентная лёгкость развёртывания. Если для обычных проводных сетей как правило требовалось в той или иной мере конфигурирование, подчас требующее внимания специалистов, то большинство беспроводных работают по принципу «Включил и работай».
Причины столь бурного прогресса в области сетей с переменной топологией очевидны: развитие микроэлектроники неизбежно приводит к удешевлению, облегчению и повышению надёжности и функциональности устройств, предназначенных для функционирования в таких сетях.
Хотя с аппаратной точки зрения очевидных препятствий к дальнейшему развитию не наблюдается, развитие беспроводных сетевых технологий во многом сдерживается отставанием в сфере программного обеспечения, а именно в области алгоритмов маршрутизации для сетей с переменной топологией, которые должны реализовывать управление информационными потоками в таких сетях с целью их эффективного использования. Дело в том, что созданный за десятилетия задел в виде десятков и сотен алгоритмов маршрутизации для обычных сетей, а во многом
и соответствующие математические методы, лежащие в их основе, оказываются совершенно неприменимы, или, по крайней мере, не применимы в исходном виде, без доработки, для использования в сетях с переменной, особенно с быстро изменяющейся топологией.
В свете вышеуказанных причин перспективность и актуальность работ в области маршрутизации в сетях с переменной топологией в настоящее время не вызывает сомнений. Именно поэтому автор выбрал для выполнения своих исследований данную тематику.
Целью данной диссертационной работы является разработка и апробация эффективных алгоритмов маршрутизации для сетей с переменной, в том числе быстро изменяющейся топологией.
Разрабатываемые алгоритмы должны быть способны решать различные, в том числе и специфические (создание устойчивого канала связи, маршрутизация в неорганизованной среде, доставка медленного трафика) задачи маршрутизации в существующих и перспективных беспроводных сетях различны типов. В первую очередь речь идёт о сетях с ограниченной мобильностью.
Для достижения поставленной цели в ходе выполнения работы были решены следующие основные задачи:
обзор и классификация существующих алгоритмов для маршрутизации в сетях с переменной топологией, выявления их слабых мест;
выявление методик эффективного управления информационными потоками в сетях с быстроизменяющейся топологией;
выявление и классификация задач маршрутизации, которые требуется решить;
уточнение особенностей архитектуры класса сетей, в которых предполагается решение задач маршрутизации;
разработка концепции многоуровневой самоорганизации сети, выявление задач маршрутизации, эффективно решаемых на каждом уровне;
разработка математической модели сетей с переменной топологией рассматриваемой архитектуры;
разработка алгоритмов маршрутизации для каждого уровня самоорганизации сети;
апробация разработанных алгоритмов и проверка их результативности, а также эффективности использования ими ресурсов сети.
Методы исследования. В работе использованы методы имитационного моделирования с использованием специально разработанного программного симулятора сети с переменной топологией. Кроме того, проводились эксперименты с реальным беспроводным компьютерным оборудованием, использующим технологию беспроводной передачи данных Bluetooth.
Научная новизна работы обусловлена созданием новых алгоритмов маршрутизации потоков данных в рамках целостной многоуровневой концепции самоорганизации сети с целью решения поставленных задач маршрутизации. В ходе работы получены следующие новые результаты:
построена многоуровневая концепция самоорганизации сети, включающая последовательные шаги самоорганизации, на основе которой решается задача многоцелевой маршрутизации;
разработана математическая модель для специфического класса сетей с ограниченной мобильностью;
в рамках построенной концепции с использованием разработанной математической модели создан ряд алгоритмов маршрутизации для сетей с ограниченной мобильностью.
Практическая ценность состоит в непосредственной пригодности разработанных алгоритмов для использования в управляющем программном
обеспечении узлов специализированных ограниченно-мобильных беспроводных сетей с отключаемыми узлами с целью эффективного использования их ресурсов. Создан прототип программного обеспечения для узлов стационарной беспроводной сети, позволяющий улучшить работу сети в случае приобретения узлами локальной мобильности.
Наиболее перспективным видится применение разработанных алгоритмов в зарождающихся сенсорных сетях с подвижными узлами, практическое внедрение которых в различные сферы жизнедеятельности ожидается в ближайшее время.
Кроме того, непосредственное применение предложенных алгоритмов возможно практически в любых мобильных сетях, действующих на ограниченной территории, например, в сетевом оборудовании офисных зданий.
Реализация и внедрение результатов
Разработанные в диссертации принципы, алгоритмы, программные и методические средства использовались при выполнении госбюджетных и хоздоговорных научно-исследовательских работ с участием автора в рамках ряда ФЦП Минобразования.
В ходе работы над диссертацией разработано управляющее программное обеспечение для узла сети с переменной топологией, на которое получено свидетельство о государственной регистрации программы для ЭВМ: «Управляющее программное обеспечение для узла гетерогенной беспроводной сети», зарегистрированная программа для ЭВМ (Номер гос. регистрации №2008610134) / Правообладатель ГОУ ВПО ВлГУ; Авторы: Голубев Андрей Сергеевич, Шамин Павел Юрьевич, Батаев Роман Алексеевич и др.
Прототип программного обеспечения был внедрен в тестовом режиме в следующих организациях:
Владимирский государственный университет.
ООО "ФС Сервис".
- ФГУ ГНИЙ ИТТ «Информика». Апробация работы
Основные результаты работы докладывались и экспонировались на следующих научно-технических совещаниях и конференциях:
Международная конференция «Телекоммуникационные и информационные системы», Санкт-Петербург, 2007 г.
Международный форум по проблемам науки, техники и образования, Москва, 04-12.12.2007 г.
XIV Всероссийская научно-методическая конференция «Телематика-2007», Санкт-Петербург, 18-21.06.2007 г.
Международная научная конференция «Информационные технологии и телекоммуникации в образовании и науке IT&T ES'2007», Турция, Фетхие, Май 2007 г.
Международная научно-техническая конференция «Перспективные технологии в средствах передачи информации», Владимир, 10-12.10.2007 г.
Выставка-ярмарка «Современная образовательная среда», Москва, ВВЦ 03.10-06.10.2007 г.
На защиту выносятся:
механизм многоуровневой самоорганизации сети и математическая модель сети с ограниченной мобильностью;
алгоритм доставки медленного трафика в сети с ограниченной мобильностью с опциональной агрегацией;
алгоритм организации устойчивого канала связи в сети с ограниченной мобильностью с опциональной синхронизацией;
алгоритм межкластерных пересылок данных в самоорганизовавшейся с сети ограниченной мобильностью.
Публикации
Основные результаты работы представлены в 9 публикациях, в том числе 1 статья в журнале из перечня ВАК, а также в научно-технических отчетах НИР, выполняемых по заданию Рособразования и Роснауки.
Объем и структура диссертации
Диссертация изложена на 173 страницах машинописного текста. Состоит из введения, четырех глав, заключения и приложений. Список литературы содержит 95 наименований. Таблиц 3, рисунков 32. В конце каждой главы перечислены основные полученные в ней результаты.
Алгоритмы маршрутизации для сетей с переменной топологией
На текущий момент существует уже более семидесяти специализированных алгоритмов маршрутизации, предназначенных для использования в сетях с переменной топологией. Вот только некоторые из них: AODV (Ad-hoc On Demand Distance Vector) PWRP (Predictive Wireless Routing Protocol) DSR (Dynamic Source Routing) OLSR (Optimized Link State Routing protocol) TORA (Temporally-Ordered Routing Algorithm) HSLS (Hazy-Sighted Link State) Описание этих и некоторых других алгоритмов маршрутизации данной категории можно найти в [35-47].
Однако, несмотря на многочисленность этих алгоритмов, каждый из них, в зависимости от способа реакции на изменения топологии, может быть отнесён к одной из двух категорий: реактивные алгоритмы (reactive, on-demand routing) и проактивные (proactive).
Реактивные алгоритмы маршрутизации прокладывают маршрут для пакета данных от узла-отправителя к узлу-получателю только в тот момент, когда требуется отправка этого пакета. Разумеется, это создаёт некоторую задержку при отправке пакета, но эта задержка может быть нивелирована путём кэширования найденных маршрутов для последующего использования. Определение: Кэширование - накопление данных в доступном хранилище, с целью их быстрого извлечения по мере надобности.
Основным преимуществом реактивных алгоритмов маршрутизации является отсутствие фоновой нагрузки на сеть. Пока не требуется отправка пакетов данных, никакие служебные пакеты по сети не рассылаются, поэтому можно практически не опасаться перегрузки сети служебным трафиком.
Определение: Трафик - совокупность данных, передаваемых по сети.
Алгоритмы второй категории - проактивные - основываются на постоянном поддержании в актуальном состоянии таблиц маршрутизации в узлах сети, на основе которых осуществляется пересылка пакетов данных.
Определение: Таблица маршрутизации - в данной работе - таблица, состоящая из пар вида ( целевой узел , шлюз ) или троек вида ( целевой узел , шлюз , метрика ) для алгоритмов маршрутизации на основе метрики.
Поддержание таблиц осуществляется за счёт постоянного фонового обмена узлами об изменениях топологии сети или периодических рассылок специальных служебных пакетов, позволяющих отследить имеющиеся маршруты. В первом случае кратчайшие маршруты определяются на основе алгоритма Дейкстры, во втором - естественным образом по принципу «кратчайший маршрут - тот, по которому первым дошёл пакет».
Так как проактивный алгоритм всегда имеет готовый маршрут до любого потенциально достижимого узла-адресата, то задержки при отправке пакетов данных исключаются. Но достигается это преимущество путём значительного фонового трафика, что может при недостаточно высокой пропускной способности сети (а мобильные сети, как правило, по техническим причинам имеют значительно меньшую пропускную способность, чем стационарные) привести к тому, что итоговая производительность сети окажется ниже, чем в случае использования реактивного алгоритма.
Однако эффективность работы и проактивных и реактивных алгоритмов резко снижается (вплоть до полной неприменимости) в случае, когда скорость изменения топологии сети возрастает.
Снижение эффективности работы реактивных алгоритмов в этой ситуации объясняется тем, что кэшированные маршруты транспортировки пакетов будут быстро устаревать ввиду разрушения составляющих их связей, поэтому часто при отправке пакета придётся строить новый маршрут, что приведёт к большим задержкам в доставке данных, недопустимым, например, при трансляции мультимедиа-потока в реальном времени.
В предельном же случае применение реактивного алгоритма станет невозможным, ввиду того, что маршруты доставки пакетов будут успевать разрушаться за время их нахождения.
Применение же проактивного алгоритма в сети с высокой скоростью изменения топологии приведёт к резкому повышению объёма служебного трафика, предназначенного для поддержания актуальности маршрутных таблиц. Это неминуемо приведёт к коллапсу сети ввиду исчерпания пропускной способности каналов связи.
И даже если полного прекращения работы сети не произойдёт, эффективность её работы (в смысле отношения объёма полезного трафика к суммарному) окажется очень низкой. Столь же низкой будет и её пропускная способность.
Работа сети в начальный период времени
Работа сети по сценарию, изображённому на рис. 2.1 происходит следующим образом: Сразу после включения узлы начинают сбор «истории наблюдений» и продолжают его на протяжении всей работы сети. График, изображённый на рис. 2.1, - это график потенциального расхода служебного трафика, если бы узлы высылали свои результаты наблюдения. Если поток событий изменения топологии сети является относительно стационарным, то в некий момент времени tcr результаты измерений стабилизируются.
В момент времени t„ координатор начинает настройку сети - сбор «историй наблюдения» узлов, рассылку инструкций (подробнее см. параграфы 3.2.3 - 3.2.5). Этот процесс требует нескольких лавинных рассылок и заканчивается в момент времени tK Прямоугольный «всплеск» на графике служебного трафика - это лавинные рассылки, зависящие только от топологии сети. Для сети с топологией квадратной решётки 23x23 это около 15000 пересылок.
Затем сеть с момент времени tp входит в рабочий режим, служебный трафик при этом не исчезает (см. серое выделение на рис. 2.1), так как узлы, в зависимости от сценария работы, продолжают снабжать координатор информацией об изменившихся параметрах работы связей.
Наши эксперименты на имитационной модели, проведённые после прозвучавшего на предзащите вопроса по поводу времени входа сети в рабочий режим, показали, что tCT составляет около 30 периодов переключения связей. Значение tp можно взять таким же.
Однако нами был разработан ещё один вариант инициализации сети, обеспечивающий ускоренный вход в рабочий режим в случае, когда мы готовы пожертвовать некоторым объёмом служебного трафика (см. рис. 2.2).
В этом сценарии начала работы сети сбор параметров сети в координатор начинается практически сразу - до их стабилизации. А сразу после раздачи инструкций узлам сеть начинает функционировать в рабочем режиме. Но за ускорение инициализации мы платим значительным служебным трафиком возникающим при передаче узлами обновлённой информации о параметрах связей (см. серую область под графиком от tK до tCT). При этом t„ по результатам моделирования оказывается около 4 периодов переключения связей (чтобы получить значение tp следует добавить время двух лавинных рассылок, которое мало, если в среднем сеть связна).
Таким образом, если период переключения связей составляет 1 минуту, то для первого сценария инициализации МО-сети время инициализации составит 30 минут, для второй - 4-5 минут.
В этом параграфе описывается математическая модель мобильной сети с ограниченно подвижными отключаемыми узлами (МО-сети), которая в дальнейшем будет именоваться просто МО-моделью. Основное предназначение предлагаемой математической модели - использование в программном обеспечении узла-координатора МО-сети. На основании данной математической модели узел-координатор будет управлять узлами сети, а также снабжать их необходимыми для маршрутизации инструкциями. Остальным узлам в этом случае отводится роль поставщиков параметров модели. На основании поступающих от них данных узел-концентратор составляет своё представление о структуре и функционировании МО-сети в виде МО-модели (см. рис. 2.3.).
Определение: Генератор расписания (включения/выключения узла) -алгоритм (программа), выполняемая узлом и определяющая моменты его включения и выключения.
Генератор расписания узла а генерирует поток событий ha с ограниченным последействием, образованный последовательным применением двух независимых случайных величин - Х$ и X", определяющих длительность интервалов пребывания узла в неактивном и активном состояниях соответственно. Случайная величина Х имеет математическое ожидание 5Т0 - среднее время пребывания узла а в неактивном состоянии. Аналогично случайная величина X" имеет математическое ожидание ST" — среднее время пребывания узла а в активном состоянии. Замечание: Можно также рассмотреть работу узла и в терминологии случайных процессов: Поток событий На порождает случайный процесс На со значениями 0 (узел неактивен) и 1 (узел активен).
Функционирование сети с «медленным трафиком», агрегирование
Функционирование сети разбивается на четыре этапа. На первом этапе узлы сети производят сбор истории наблюдений. Этот этап заканчивается либо при выполнении некоторых условий на стабилизацию параметров, либо в фиксированный момент времени. Затем узел-координатор инициирует лавинную рассылку с целью первоначального заполнения маршрутных таблиц. Узел, до которого доходит лавинный процесс, модифицирует свою таблицу и отсылает узлу-координатору собранную историю наблюдений. Третий этап начинается после того, как узел-координатор получит историю наблюдений от всех узлов, либо от установленной их части. На этом этапе он рассчитывает оптимальные маршруты и инициирует вторую лавинную рассылку для доведения сведений об оптимальных маршрутах в виде пары шлюз-метрика. И наконец, когда узлы получили эти инструкции, они начинают периодически отсылать полезную информацию. Посылка полезной информации может продолжаться в течение всего функционирования сети и не выделяться в отдельный этап, но при этом об интеллектуальности можно будет говорить только при получении узлом информации об оптимальных маршрутах.
Определение: Под оптимальным маршрутом в данной работе понимается маршрут, являющийся кратчайшим в выбранной метрике. Замечание: Приведённый вариант видится лучшим среди нескольких прочих, однако при необходимости реализация вышеописанного алгоритма может быть несколько другой.
Например, узлы сети могут пересылать узлу-координатору вместо истории наблюдений уже вычисленные параметры, однако это накладывает ограничения на глубину анализа ситуации в сети (узел может оперировать лишь собственной историей наблюдений) и повышает вычислительную нагрузку на сравнительно слабые в этом смысле рядовые узлы сети. Преимуществом этой методики является разгрузка каналов сети. Очевидно, что передача истории наблюдений узла требует значительно большего сетевого трафика, чем передача нескольких параметров, вычисленных на её основе.
Замечание: Упомянутая выше лавинная рассылка выполняется в варианте, адаптированном для использования в МО-сетях. Описание этого модифицированного варианта лавинной рассылки приведено в параграфе 1.6.2. Такой механизм обеспечивает доведение информации до каждого узла и снимает с узлов потенциальную задачу о самостоятельном поиске информации.
Процесс доставки информации в узел-координатор является основной задачей маршрутизации медленного трафика. Как уже было сказано, для его организации используются две метрики dx и d2. Первая метрика позволяет определить самые надежные маршруты, вторая - маршруты с наименьшим временем на ожидание. Процесс пересылки зависит от принятой стратегии и может использовать любую метрику из имеющуюся в маршрутных таблицах или обе одновременно с некоторыми коэффициентами. Рассмотрим возможные дополнительные задачи (помимо основной — доставки пакета данных узлу-адресату), которые могут быть решаемы при маршрутизации медленного трафика.
Первая дополнительная задача - минимизация времени пересылки. В сетях с фиксированной топологией для решения этой дополнительной задачи может эффективно использоваться подход, известный под названием географической маршрутизации. Он заключается в том, что пакет данных пересылается в тот доступный узел, который реализует уменьшение некоторой естественной метрики, например, городской или евклидовой. Такой подход носит «жадный» характер и, обеспечивая локальную выгоду, не всегда обеспечивает глобальный выигрыш. Кроме того, существуют ситуации, когда такой подход может вообще не обеспечивать доставку части информации. Подход, использующий статистику для снижения времени доставки, заключается в использовании вероятностной таблицы, построенной по первой метрике. Шлюзом для пересылки становится узел, имеющий наименьшую первую метрику. Если он не активен, то происходит его ожидание.
Первая дополнительная задача - минимизация числа операций пересылки. Согласно описанной выше стратегии каждый пакет ведется и пересылается отдельно. Однако часто возникает потребность объединения (агрегирования) пакетов, за счет чего сокращается общее число пересылок. Дело в том, что во многих технических реализациях беспроводных сетей пересылка одного крупного пакета данных выполняется значительно эффективнее (с меньшим использованием ресурсов сети), чем отправка нескольких меньших, равных ему по суммарному объёму. Пакеты принимаются группами, накапливаются узлом, переупорядочиваются и пересылаются в новых блоках.
Определение: Описанный процесс объединения пакетов в группы с целью снижения суммарного количества пересылок называется агрегированием.
Определение параметров стабильности связей
Количественная оценка степени стабильности связи, на основании которой может быть принято решении о включении или не включении данной связи в состав УКС, определяется двумя параметрами: вероятностью пребывания связи в активном состоянии при условии активности обоих узлов —fab; средним периодом активного состояния связи, при условии активности обоих узлов — tx.
Если поток событий, описывающий МО-модель (см. параграф 2.2) стационарен, то обе эти величины для каждой связи являются константами. Для полностью стабильной связи fab=l, tx= +00. Отметим, что одного лишь знания величины fab недостаточно для определения степени стабильности связи, так как могут существовать связи, которые при включенном состоянии соединяемых узлов имеют короткий период активного состояния, несмотря на высокую вероятность активности.
Замечание: Возможность управления расписаниями включения и выключения узлов позволяет значительно увеличить вероятность активного состояния связи, так как в типичном случае fab » Fab.
Важной и наиболее сложной частью задачи построения УКС является задача получения указанных параметров связей на основании истории наблюдений. Следующие параграфы посвящены решению этой подзадачи.
Как уже указывалось, отключение связи может произойти по двум причинам - вследствие удаления узлов, которые соединяет связь, за пределы радиуса действия их приёмо-передающей аппаратуры и вследствие выключения одного или обоих узлов. Для определения параметров стабильности связей на основании истории наблюдений необходимо иметь возможность в каждом случае определить причину изменения состояния связи: вызвано ли оно включением/выключением узлов или их движением.
Определение причины изменения состояния связи возможно только при наличии истории наблюдениях обоих узлов, которые она соединяет. Поэтому все смежные узлы должны периодически обмениваться накопленной историей наблюдения или периодически высылать историю наблюдения узлу-координатору (например, с помощью алгоритмов доставки медленного трафика), если все вычислительные функции возложены на него. Однако более предпочтительным выглядит первый вариант, так как отправка истории наблюдений координатору требует пересылки по сети значительно большего количества пакетов данных, чем отправка ему же уже вычисленных узлами сети параметров стабильности связей.
Пусть мы организовали тем или иным образом доставку истории наблюдений двух смежных узлов до узла, производящего вычисления. Будем считать, что история наблюдений представлена в формате, описанном в параграфе 2.2.5.
Тогда при наличии информации, о том, что связей с коротким циклом в сети нет (или их количество пренебрежимо мало) используем s-метрику, в противном случае метрики d2 и d3 в составе той или иной целевой функции.
Алгоритм вычисления необходимых значений приведён в параграфе 2.2.6, упомянутые метрики рассмотрены в параграфе 2.2.7.
Определим критерии качества для алгоритма построения УКС. Будем считать, что качество алгоритма может быть оценено двумя параметрами: - время установления УКС; - время жизни УКС;
Определение: Время установления УКС — это промежуток времени от момента инициирования процесса поиска канала до момента доведения служебного пакета до центрального узла.
Определение: Время жизни УКС - это промежуток времени от момента установления УКС до момента обрыва УКС.
Отметим, что данное определение допускает отрицательную величину времени жизни УКС. Это возможно в том случае, если обрыв УКС происходит раньше завершения процесса его установления. Очевидно также, что установление УКС с приемлемым временем жизни может быть вообще невозможным в сети с крайне нестабильными связями.
