Содержание к диссертации
Введение
Глава 1. Технологии распределенного моделирования .. 10
1.1. Аналитический обзор архитектур распределенного моделирования 10
1.1.1. Развитие архитектур распределенного моделирования 10
1.1.2. Отечественные разработки в области распределенного моделирования 16
1.1.3.Сравнение архитектуры с HLA cDISuALSP. 17
1.2. Архитектура распределенного моделирования hla и формирование требований по ее доработке 20
1.2.1. Общая структура системы на базе архитектуры высокого уровня. Основные понятия и определения 21
1.2.4. Система исполнения 29
1.2.5. Механизм управления обменом данными 34
1.2.4.2 Механизм управления ходом времени в процессе моделирования 38
1.3. Задачи по доработке архитектуры высокого уровня 44
Выводы по главе 1 46
Глава 2 Модернизация механизма управления обмена данными в ходе распределенного моделирования 49
2.1 . Аппроксимация информационных полей и сигнатур ограничивающими объемами 53
2.2.Формальная постановка задачи аппроксимации 54
2.3.Аппроксимации сложных пространственных объемов параллелепипедом с минимальным объемом 57
2.4.Эффективный алгоритм аппроксимации 58
2.4.1 .Аппроксимация диаметра 58
2.4.2.Вычисление аппроксимирующего параллелепипеда 60
2.4.4.Алгоритм для вычисления Bopl(S) 65
2.4.5.Алгоритм аппроксимации множества точек ограничивающим параллелепипедом с минимальным объемом 67
2.5.Алътернативный реализованный алгоритм 67
2.5.1. Алгоритм расчета ограничивающего параллелепипеда по методу сетки 72
2.6. Экспериментальные исследования разработанного механизма аппроксимации 72
2.7. Эксперименты, демонстрирующие преимущества от использования модернизированного метода представления областей подписки и обновления по сравнению со стандартной службой ddm 78
Выводы по главе 2 80
Глава 3. Оптимизация групп многоточечной рассылки в системах распределенного моделирования 82
3.1 . Методы представления соединений в ходе распределенного моделирования 84
3.2.Формальная постановка задачи опимизации 87
3.2.1 Схожесть задачи с «проблемой упаковки рюкзака» 89
3.2.2. Описание задачи 90
3.2.3. Анализ применимости различных методов оптимизации 90
3.2.4. Функция затрат 92
3.3 .Вычисление времени простоя сообщения в очереди и передачи сообщения по сети 95
3.4 Различные ситуации, возникающие при группировке 99
3.5. Алгоритм замера производительности 102
3.6.Алгоритмы группировки 107
3.6.1.Алгоритм наибольшего исходящего соединения (НИС) 108
3.6.2. Алгоритм наибольшего исходящего соединения с ограничением на входе (НИСОВ) 115
3.6.3.Результаты, показывающие эффективность НИС и НИСОВ 116
Выводы по главе 3 123
Глава 4. Механизм синхронизации хода времени в различных программно-аппаратных реализациях 125
4.1. Анализ архитектур синхронизации времени 125
4.2. Синхронизация времени в ходе распределенного моделирования на основе протокола ntp 127
4.2.1. Сетевой протокол времени NTP. 127
4.2.2. Архитектура системы синхронизации времени 128
4.2.3. Реализация модели синхронизации времени 130
4.2.4.Конфигурации сети 737
4.2.5.Форматы данных 132
4.2.6. Временная шкала NTP и ее хронометрия 133
4.2.7. Первичная частота и стандарты времени 133
4.2.8. Передача времени ичастоты 135
4.2.9. Определение частоты 137
4.3. Эксперимент по применению предложенной архитектуры временной синхронизации 137
Выводы по главе 4 139
Заключение 140
Список литературы 142
Приложение 1 149
Приложение 2 150
Приложение 3 154
- Аналитический обзор архитектур распределенного моделирования
- Аппроксимация информационных полей и сигнатур ограничивающими объемами
- Методы представления соединений в ходе распределенного моделирования
- Анализ архитектур синхронизации времени
Введение к работе
Одной из основных тенденций в разработке систем моделирования является переход от идеологии построения изолированной системы к системам распределенного моделирования. В соответствии с данным подходом, даже тот тренажер (или модель), функционирование которого не требует взаимодействия с другими тренажерами и внешними моделями, должен создаваться с; учетом возможности его включения в будущем в систему распределенного моделирования. Основным преимуществом от использования подобного подхода является возможность соединения независимо разработанных тренажеров и моделей в моделирующие комплексы с качественно новыми возможностями. При этом объединяемые тренажеры и модели могут находиться не только на разных компьютерах, но и даже в разных городах, необходимым условием при этом является только наличие компьютерной сети между ними, например Интернет.
Применение систем распределенного моделирования позволяет:
Проводить обучение операторов для отработки совместных действий в критических ситуациях (например, отрядов МЧС, службы управления воздушным движением, служб управления транспортными перевозками).
Осуществлять поддержку принятия решений при выборе метода проведения операций (например, спасательных операций при стихийных бедствиях).
Принимать решения по логистической поддержке.
Осуществлять проведение научно-исследовательских экспериментов, в которых задействованы территориально удаленные моделирующие комплексы.
Основными преимуществами от использования систем распределенного моделирования являются:
I 5
Возможность многократного использования разработанных моделей в составе различных моделирующих комплексов для решения различных задач;
Снижение затрат на организацию тренингов и совместных учений различных масштабов;
Снижение затрат на эксплуатацию реальной техники (Для отработки групповых действий нет необходимости использовать реальную технику);
Снижение загрязнения окружающей среды продуктами технической деятельности;
Повышение безопасности процесса обучения совместным действиям.
Поэтому актуальной является задача разработки методов и средств
построения моделирующих комплексов и обучающих систем на основе
технологий распределенного моделирования. Основой практической
реализации любой архитектуры распределенного моделирования является
I среда обмена данными между участниками распределенного
моделирования. В качестве базовой среды передачи данных в настоящее
время используются локальные и глобальные компьютерные сети.
Современным компьютерным сетям присущ ряд ограничений, которые
необходимо учитывать при построении систем распределенного
моделирования.
Целью диссертационной работы является разработка методов и
средств построения систем распределенного моделирования на базе
современных сетевых технологий.
В соответствии с поставленной целью в работе решаются следующие
задачи:
анализ существующих технологий и архитектурных решений
создания систем распределенного моделирования и выбор
архитектуры на базе сформулированных критериев.
определение направлений модернизации выбранной архитектуры для обеспечения ее практической реализуемости на существующих компьютерных сетях.
модернизация механизма управления обменом данными в ходе распределенного моделирования.
разработка метода построения систем распределенного моделирования с большим количеством участников.
разработка механизма обеспечения низкоуровневой временной синхронизации при проведении распределенного моделирования.
Методы исследования и примененный математический аппарат: При работе над диссертацией использовались методы передачи данных в сетях, прикладные методы теории построения вычислительных систем и сетей, теория графов, вычислительная геометрия, алгоритмы прикладной математики, аппарат математической статистики и прикладное программирование.
Научная новизна состоит в следующем:
1. Предложен новый подход к построению распределенных
моделирующих комплексов и обучающих систем на базе универсальной
стандартизованной архитектуры, основанный на выборе одной из
существующих архитектур распределенного моделирования на основе
сформулированных функциональных критериев и модернизации
выбранной архитектуры для обеспечения ее практической реализуемости
на существующих компьютерных сетях.
2. Разработан метод модернизации служб логической фильтрации
данных, передаваемых в ходе распределенного моделирования, выбранной
архитектуры, позволяющий проводить распределенное моделирование
сложных информационных систем на низкоскоростных каналах связи, и
проведена экспериментальная оценка результатов, подтверждающая
эффективность предложенного метода.
Разработан метод решения задачи рационального распределения участников распределенного моделирования по группам многоточечной рассылки, позволяющий минимизировать объем передаваемых данных по каналам связи, а также увеличить количество участников моделирования. Проведенные эксперименты показали эффективность разработанных методов группировки по сформулированным критериям.
Предложен механизм корректной низкоуровневой временной синхронизации в информационных системах для выбранной архитектуры распределенного моделирования, позволяющий устранить дополнительный сетевой трафик, связанный с несвоевременной посылкой данных.
Практическая ценность. Разработанные методы и алгоритмы реализованы в виде программного обеспечения и позволяют создавать системы распределенного моделирования на основе предложенной архитектуры наиболее эффективно в условиях сложившихся ограничений, накладываемых существующим аппаратным и программным обеспечением вычислительных систем.
На защиту выносятся следующие основные результаты:
подход к построению моделирующих комплексов.
методы и средства реализации систем распределенного моделирования на базе существующих сетей.
В рамках данного подхода разработаны:
метод управления обменом данными в ходе распределенного моделирования на основе логической фильтрации данных.
метод снижения загрузки сети за счет использования групп многоточечной рассылки.
механизм низкоуровневой временной синхронизации в ходе моделирования.
8 Содержание работы:
Первый раздел содержит аналитический обзор существующих архитектур распределенного моделирования, выбор архитектуры отвечающей поставленным требованиям и формирование предложений по доработке выбранной архитектуры для обеспечения ее практической реализуемости на существующих компьютерных сетях.
Второй раздел данной диссертации посвящен модернизации механизма управления обмена данными за счет доработки механизма логической фильтрации данных, передаваемых в ходе распределенного моделирования.
В третьем разделе приводится описание разработанных методов снижения загрузки сети за счет использования групп многоточечной рассылки.
В четвертом разделе излагается выработанный подход к низкоуровневой временной синхронизации в ходе распределенного моделирования.
Реализация и внедрение результатов исследований. Разработанные в диссертационной работе алгоритмы и реализация их в виде программного обеспечения, а также материалы проведенных исследований были использованы в ряде работ, выполненных ФГУП ГосНИИАС по заказам Министерства Обороны РФ и сводного департамента оборонной промышленности Минпромнауки России, в том числе: НИР «Мультипликатор», «Мультипликация-2000», ОКР «Интеграф», ОКР «Репитер».
Апробация работы:
Основные положения диссертационной работы докладывались на: 1. Третьем научно-техническом семинаре "Технические средства и технологии для построения тренажеров", ЦПК им. Ю.А.Гагарина, Звездный городок, 1998г.
Научно-технической конференции студентов, аспирантов и молодых специалистов МГИЭМ, Москва 1999 г.
Научно-технической конференции студентов, аспирантов и молодых специалистов МГИЭМ, Москва 2000 г.
Восьмой международной студенческой школе-семинаре «Новые информационные технологии» Крым, 2000 г.
XlXth Congress of the International Society for Photogrammetry and Remote Sensing (ISPRS) Amsterdam, The Netherlands, 16-23 July 2000
Научно-технической конференции студентов, аспирантов и молодых специалистов МГИЭМ, Москва 2001 г.
Четвертом научно-практическом семинаре «Новые информационные технологии», МГИЭМ, Москва, 2001г.
Международной конференции «Тренажерные технологии и обучение: Исследования, разработки и потребности рынка» г.Жуковский Московская область 24-25 мая 2001 г.
9. Научно-технической конференции студентов, аспирантов и молодых
специалистов МГИЭМ, Москва 2002 г.
Аналитический обзор архитектур распределенного моделирования
До 1983 года все тренажеры, применявшиеся министерством обороны США, представляли собой изолированные системы. Тренажер предназначался для подготовки одного человека или одного экипажа, и связь с другими тренажерами не предусматривалась. Исключение составляли сдвоенные тренажеры пилотов истребителей, позволявшие вести пилотам бой между собой. Однако, такая система не может рассматриваться как система распределенного моделирования, так как предполагает единственную жесткую структуру связи и не позволяет подключать новых участников. Необходимость разработки более дешевой и безопасной альтернативы войсковым учениям и маневрам для подготовки личного состава к групповым действиям привела к созданию в 1983 году проекта SIMNET. Проект SIMNET (Simulation Network -компьютерная сеть для моделирования) был разработан основной научно-исследовательской организацией министерства обороны США агентством DARPA (Defense Advanced Research Projects Agency -агентство по перспективным оборонным исследованиям), при участии STRICOM (Simulation, Training, and Instrumentation Command -управление МО США по моделированию, подготовке и оснащению). Основной целью проекта SIMNET было обеспечение связи и взаимодействия в единой виртуальной среде территориально разнесенных тренажеров. Взаимодействие должно было обеспечиваться практически в реальном времени (в описании проекта SIMNET использован термин near-realime, то есть "почти реальное время")- Первоначально в рамках SIMNET предполагалось объединение однотипных танковых тренажеров, однако, по мере развития проекта, акцент сместился в сторону обеспечения взаимодействия разнотипных тренажеров.
С 1986 года проект SIMNET переименован в DIS (Distributed Interactive Simulation). Целью проекта DIS являлась разработка структуры и методологии для объединения разнотипных территориально разнесенных тренажеров, с целью обеспечения их взаимодействия в реальном времени в едином реалистичном виртуальном окружении. В рамках данного проекта были разработаны стандарты на архитектуру взаимосвязи между участниками моделирования и на интерфейс обмена информацией между ними. Организация IEEE (Institute of Electrical and Electronic Engineers - институт инженеров по электротехнике и электронике - организация, разрабатывающая и публикующая стандарты, в частности, многие стандарты для компьютерных сетей) разработала стандарт, посвященный DIS - IEEE Standard 1278. [3]
Принцип работы DIS-системы состоит в следующем. Несколько тренажеров (а точнее рабочих станций, входящих в их состав) связаны между собой локальной сетью. Все участники моделирования, разделяющие единое виртуальное пространство, взаимодействуют своими протоколами между собой. Каждый участник с заранее оговоренной частотой посылает в сеть свой DIS-протокол и принимает все протоколы, посланные другими участниками. Протокол может быть адресован одному или многим участникам моделирования, но, независимо от адресации, он передается всем участникам моделирования. После анализа адреса отправителя и содержимого принятого протокола управляющая программа тренажера производит обновление виртуального окружения, которое наблюдает обучаемый. В простейшем случае DIS протокол состоит из 27 различных пакетов PDU (Protocol Data Unit - элемент протокола данных), а по стандарту IEEE 1278 из 127 пакетов, которые пересылаются между узлами, представляющими тренажеры. Пакеты могут пересылаться по любым типам компьютерных сетей. Пакеты содержат описание состояний динамических объектов, событий в процессе взаимодействия (взрыв, выстрел, движение объекта и т.д.). Каждый участник моделирования сообщает свой тип, координаты, скорость, ориентацию и другие свойственные ему параметры.
С 1983 по 1995 на основе технологий SIMNET и DIS в интересах МО США создано более 300 типов тренажеров для объединения в системы распределенного моделирования. По мере развития систем распределенного моделирования, требования, предъявляемые к ним, привели к необходимости разработки более гибкой и многофункциональной архитектуры, чем DIS. Основными задачами, не решенными стандартизированной архитектурой DIS, явились:
1. Эффективная работа с большим числом участников, динамически присоединяющихся к процессу распределенного моделирования и отключающихся от него;
2. Объединение не только тренажеров, но и реальных образцов техники, и компьютерных моделей;
3. Объединение тренажеров разного уровня: тренажеров отдельных видов техники и тренажеров низшего, среднего и высшего командных звеньев;
4. Объединение участников с различным типом хода времени (реальное, "по шагам", "по событиям").
Для решения этих задач в начале 90-х годов по инициативе DARPA была начата разработка концепции ADS (Advanced Distributed Simulation -перспективное распределенное моделирование)[4]. В рамках этого проекта были разработаны несколько архитектур, являющихся надстройками и дополнениями стандарта DIS. Это, в первую очередь, ADIS (Advanced DIS - перспективный DIS). Данная схема организации распределенного моделирования использует ряд усовершенствований DIS-архитектуры:
1. Различная частота отправки протокола. В зависимости от типа объекта (малоподвижный/высокоподвижный) устанавливается частота отправки протокола. Например, тренажер самолета должен отправлять свой протокол каждую 1/30 секунды, а тренажер танка один раз в три секунды;
2. Предсказание положения. Механизм предсказания положения основан на предположении, что, зная текущие координаты объекта и его вектор скорости в данный момент, можно спрогнозировать его положение через небольшой промежуток времени, в течение которого вектор скорости считается неизменным. Это позволяет снизить частоту обмена протоколами между малоподвижными объектами (танками, кораблями и т.д.).[5,б]
Начиная с 1989, параллельно с DIS-технологиями, по заказу МО США разрабатывалась технология, предназначенная для объединения моделей отдельных единиц и (или) группировок с пошаговым ходом времени и тактических тренажеров высшего командного звена на основе их взаимодействия на общем синтетическом поля боя. С 1991 года данная архитектура получила название ALSP (Aggregate Level Simulation Protocol - протокол моделирования для объединенного уровня). ALSP основывается на классификации форм взаимодействия между моделями и стандартизации подхода к написанию новых моделей в целом, а не только модуля обмена данными. Модели могут находится на одной вычислительной машине, либо на территориально разнесенных, но объединенных единой сетью. ALSP предусматривает наличие управляющей программы, в функции которой входит обеспечение интерфейса между моделями, входящими в состав системы распределенного моделирования.[7]
Аппроксимация информационных полей и сигнатур ограничивающими объемами
При аппроксимации информационных полей и сигнатур объектов необходимо использовать ограничивающие фигуры, так как в противном случае (при использовании вписанных фигур) механизм фильтрации будет отсеивать цели, которые на практике могли быть обнаружены. Тем самым будет нарушена адекватность моделирования, что недопустимо. Существует множество алгоритмов, которые вычисляют ограничивающие фигуры. Данные алгоритмы характеризуются различными требованиями к производительности вычислительной системы и используемому объему оперативной памяти. Для приложений, в которых расчеты производятся в реальном времени особенно важно, чтобы вычисления производились за фиксированное время, которое должно быть достаточно мало, чтобы не создавать задержки в цикле выполнения программы. Исходя из этого, был выбран метод построения осепараллельных ограничивающих п-мерных параллелепипедов, так как метод фильтрации данных DDM, который основан на определении пересечений осепараллельных параллелепипедов, и предлагается усовершенствование данного метода, не выходя за рамки архитектуры HLA.
Данное решение позволит обеспечить совместимость приложений, разработанных на основе стандартного подхода HLA, с приложениями, использующими разработанный модернизированный метод фильтрации. Таким образом, модернизация сервисных служб HLA не повлечет за собой необходимость радикальной переработки уже созданных HLA приложений. Вместе с тем, выигрыш в снижении сетевого трафика от использования служб управления обмена данными будет тем выше, чем будет больше часть участников моделирования, использующих модернизированные службы обмена данными.
Формальная постановка задачи аппроксимации Дано:
множество S содержащее п точек в R, определяющее информационное поле (сигнатуру).
параметр аппроксимации с, задаваемый на основе требований точности моделирования.
Требуется найти:
ограничивающий параллелепипед B(S) с объемом (1+Е) от минимального объема Bopt(S), определяющий соответствующую область подписки(обновления).
С этой целью решения поставленной задачи был разработан метод аппроксимации областей действия информационных каналов и сигнатур осепараллельными n-мерными параллелепипедами. Параллелепипеды, которые ограничивают множества точек, используются для иерархического представления занимаемых им объемов, а также это одни из наиболее эффективных в смысле вычислительной сложности примитивов, которые могут описывать объемы. Например, в компьютерной графике (для быстрой визуализации сцены или для вычисления столкновений с объектами) и в статистике (для хранения и выполнения больших запросов в многомерных базах банных).
Так же еще одно обстоятельство говорит в пользу выбора этих примитивов, что данный примитив (n-мерный параллелепипед) является стандартизованным средством описания областей подписки/обновления в HLA. Данная проблема вычисления ограничивающего параллелепипеда разделяется на две подзадачи, а именно: найти рациональное разбиение единого множества точек на подмножества, при этом минимизируя максимальный диаметр подмножеств и вычислить для данного подмножества ограничивающий параллелепипед (или другую фигуру). В связи с тем, что в процессе распределенного моделирования возникают некоторые ограничения на количество регионов подписки/обновления, о которых будет изложено далее, было принято решение сосредоточиться на аппроксимации сигнатур и зон действия сенсоров единым осепараллельным параллелепипедом.
Для вычисления ограничивающих объемов используются различные подходы. Самым простым в смысле вычислительной сложности является вычисление осепараллельного ограничивающего параллелепипеда (axis-aligned bounding box (ААВВ)) Двумерные варианты этого алгоритма используют иерархические декомпозиции, например R-дерево (Rree) или упакованное R-дерево. [16], R+ дерево [17] и R дерево [18]. В работе [19] авторы используют осепараллельный ограничивающий параллелепипед с минимальным объемом ориентированный по определенным направлениям Gottschalk и др. [20] создали систему проверки столкновений RAPID на основе дерева ориентированных ограничивающих параллелепипедов (OBBree) для каждого параллелепипеда, который сонаправлен с заранее выбранным направлением множества. Похожая идея заложена в алгоритмы BOXTREE [21]. Последний метод допускает множество вариантов, в которых вычисляемый параллелепипед выровнен не только по одному направлению множества точек (то есть, которое отвечает за наибольшее или наименьшее собственное значение ковариантной матрицы координат точек) и двумя другими направлениями по другому методу (вычисляя ограничивающий прямоугольник с минимальной площадью проекции точек на плоскость по первому выбранному направлению). Другие геометрические примитивы, такие как сфера [22], конус [23], и призма [21,24] также используются для иерархического представления множества точек. Большинство из этих методов требуют для вычисления ограничивающего параллелепипеда 0(п) времени и памяти, но не обеспечивают решение данной задачи с допустимым уровнем аппроксимации.
Алгоритм, изложенный в работе [25] решает схожую проблему, в котором множество из п точек содержится в двух осепараллельных ограничивающих параллелепипедах и целью алгоритма является минимизация объема (или другого параметра) наибольшего параллелепипеда. Данный алгоритм требует 0(п2) времени. O Rourke представил только алгоритм для вычисления точного произвольно-ориентированного ограничивающего параллелепипеда с минимальным объемом для множества п точек в R . Его алгоритм требует 0(n ) времени и О(п) памяти. В диссертационной работе был разработан метод построения ограничивающих параллелепипедов, который основан на использовании алгоритмов, изложенных в работе [26], которые являются (l+є) аппроксимацией множества точек в R3. Время выполнения этих алгоритмов 0(П+1/Е4 5) И 0(nlogn+n/e3) соответственно. На основании изложенных алгоритмов была сделана программная реализация на языке С и проведены эксперименты.
Входными данными для алгоритмов является множество точек, описывающих зону действия сенсоров или сигнатуру объекта.
Методы представления соединений в ходе распределенного моделирования
Анализ архитектур синхронизации времени
Предположим, что федерация состоит из 10 федератов, в каждом из которых 10 объектов и у каждого объекта 10 атрибутов. Данная федерация может иметь до 10 10 10 соединений. С максимальным количеством доступных групп многоточечной рассылки равным 3000 количество возможных вариантов группировки достигает (30001О0О/3000!). Оптимизированный эвристический подход позволяет добиться повышения производительности. При использовании регионов подписки и обновления, методы обновления атрибутов объекта известны до того, как они будут посланы подписчикам. Рассмотрим расположение регионов, показанное на рисунке 3.1. Из рисунка видно, что федерат f1? который владеет регионом обновления Ш, будет посылать обновления атрибутов связанных с регионом Ш федератам f2 и fj, так как они владеют регионами подписки S2 и S3 соответственно.
По данному входному набору регионов можно построить граф соединений, который показан на рисунке 3.2. Федерат fj посылает обновление атрибутов, которое представлено соединением сг к федерату f2 и f3. Федерат f3 посылает обновление атрибутов представленных соединением с2 к федератам f2 и f4. Федерат f} также посылает данные через соединение с3 к f4. Альтернативно данное множество соединений может быть представлено графом f c wi ) fi,C3,W3,(f4) !. :f3jC2,W2l)(f2l.f4) } Путь передачи сообщения по сети в данном случае не отражает коммуникации. Путь соединения не представляет собой передачу единичного сообщения по сети, он в свою очередь представляет передачу всех обновлений атрибутов объекта. Коммуникация свою очередь отражает единичное обновление атрибута или передачу сообщений. Соединение Cj всегда имеет в качестве источника посылки одного федерата и одного или более федератов в качестве приемника соединения. Оно также имеет вес, который показывает, насколько часто происходят обновления. Поэтому соединение сі посылается с частотой wt. Целью данной оптимизации является: включить соединение в группу многоточечной рассылки так, что время доставки сообщения не будет превышать конкретный лимит. На рисунке 2.6. представлен граф соединений для рассматриваемого примера.
Считаем что, все соединения, которые не включены в группу многоточечной рассылки будут посылать сообщения по типу «точка-точка». С учетом этого, полное решение этой проблемы имеет вычислительную сложность 0((m+l)S(n,m+l)) для п соединений в m группах многоточечной рассылки, где S(n,m) - это число Стирлинга второго рода как описано в Выражении (3.1). Число Стирлинга второго рода определяет, сколькими способами можно разбить п элементное множество на m непересекающихся подмножеств [49]
Существуют два фактора, влияющие на количество всех возможных комбинаций соединений. Во-первых, для любого набора соединений и групп комбинация может не использовать все доступные группы многоточечной рассылки. Это приводит к тому, что сумма всего возможного количества групп многоточечной рассылки равна т. Во вторых, любое соединение может быть удалено из группы, то есть может быть вырождено к типу «точка-точка». В добавлении к 8(п,ш), которое распределяет любые соединения по доступным группам многоточечной рассылки, С должно добавить возможность другой группировки соединений «точка-точка», но это может быть заменено для каждой реальной группы. Для того, чтобы понять поведение нераспределенной группы, возьмем следующий пример. Распределение четырех соединений (с1,с2,Сз»С4) в Две группы многоточечной рассылки (gi,g2) может выглядеть как (с, є gY,c2 є gj,c3 є g2,c4 є g2), и это эквивалентно (с, є g2,c2 є g2,c3 є gi,ci є g-,), так как в обоих случаях Сі и с2 группируются вместе, так же как и с3 и с4. Если группа gt представляет соединение «точка-точка», то Сі и с2 будут тоже «точка-точка», тогда как сз и сц будут сгруппированы вместе, то такая ситуация отличается от той, при которой С] и с2 будут сгруппированы вместе, тогда как с3 и с4 будут посылаться по типу «точка-точка». Схожесть задачи с «проблемой упаковки рюкзака».
Проблема группировки узлов по группам многоточечной рассылки может быть рассмотрена как «проблема упаковки рюкзака» [50]. Описательная постановка, которой формулируется так:
Есть предметы п различных весов (количество предметов каждого веса не ограничено) и есть рюкзак, который выдерживает вес N. Требуется найти такую комбинацию предметов, которая бы максимально заполнила рюкзак. В других вариантах этой задачи имелось по одному предмету (либо некоторое количество) каждого веса.
Алгоритм решения классического варианта с помощью динамического программирования следующий:
1) Предполагаем, что рюкзак «резиновый» и вместимость его равна минимуму из всех весов предметов. Находим комбинацию предметов (здесь он будет один) заполняющую этот рюкзак максимально.
2) Увеличиваем вместимость рюкзака на единицу.
3) Среди всех предыдущих комбинаций (пока она одна) ищем такую, которая при добавлении одного предмета (все это должно естественно влезать в рюкзак) даст большую заполненность рюкзака текущего объема. Таким образом, для каждого веса будут получаться наиболее оптимальные комбинации и для большего веса перебор будет только по ним). Пі, п2, п3,... - значения различных весов предметов; kj, кг,... - список найденных комбинаций. Идем по списку всех комбинаций. Для каждой комбинации идем по списку всех предметов и среди таких сумм: ki+щ, кі+П2, k;+n3, ... ищем ту, которая умещается в рюкзаке (у него на этом шаге соответственно размер) и является наибольшей среди других.
4) Повторяем пункт 3 до объема рюкзака.
