Рейтинг
+2.28
голосов:
2
avatar

Статьи конференции ITHEA vol1  

ЕЛЛЕКТУАЛЬНОГО ПОИСКА, КЛАССИФИКАЦИИ И РЕФЕРИРОВАНИЯ ДОКУМЕНТОВ ДЛЯ ИНТЕРНЕТ-ПОРТАЛА часть 2

СИСТЕМА ИНТЕЛЛЕКТУАЛЬНОГО ПОИСКА, КЛАССИФИКАЦИИ И РЕФЕРИРОВАНИЯ ДОКУМЕНТОВ ДЛЯ ИНТЕРНЕТ-ПОРТАЛА

ЕЛЛЕКТУАЛЬНОГО ПОИСКА, КЛАССИФИКАЦИИ И РЕФЕРИРОВАНИЯ ДОКУМЕНТОВ ДЛЯ ИНТЕРНЕТ-ПОРТАЛА часть 1
ЕЛЛЕКТУАЛЬНОГО ПОИСКА, КЛАССИФИКАЦИИ И РЕФЕРИРОВАНИЯ ДОКУМЕНТОВ ДЛЯ ИНТЕРНЕТ-ПОРТАЛА часть 2
Подход к семантическому индексированию
На результативность процесса поиска необходимых документов оказывает большое влияние и человеческий фактор: зачастую пользователь не готов к долгому ожиданию результатов поиска, к просмотру и анализу большого объема результирующей выборки. Кроме того, большинство пользователей неэффективно используют поисковое программное обеспечение и, как правило, они игнорируют расширенные поисковые возможности и ограничиваются короткими типовыми запросами.
Для повышения эффективности обработки электронных документов требуется наличия метаданных, описывающих структуру и семантику документов. Одним из возможных подходов к описанию информации, заложенной в документе, является подход на основе онтологий. Под онтологией понимается база знаний специального типа, которая может «читаться» и пониматься, отчуждаться от разработчика и/или физически разделяться ее пользователями [4].

( Читать дальше )

СИСТЕМА ИНТЕЛЛЕКТУАЛЬНОГО ПОИСКА, КЛАССИФИКАЦИИ И РЕФЕРИРОВАНИЯ ДОКУМЕНТОВ ДЛЯ ИНТЕРНЕТ-ПОРТАЛА часть 1

СИСТЕМА ИНТЕЛЛЕКТУАЛЬНОГО ПОИСКА, КЛАССИФИКАЦИИ И РЕФЕРИРОВАНИЯ ДОКУМЕНТОВ ДЛЯ ИНТЕРНЕТ-ПОРТАЛА

ЕЛЛЕКТУАЛЬНОГО ПОИСКА, КЛАССИФИКАЦИИ И РЕФЕРИРОВАНИЯ ДОКУМЕНТОВ ДЛЯ ИНТЕРНЕТ-ПОРТАЛА часть 1
ЕЛЛЕКТУАЛЬНОГО ПОИСКА, КЛАССИФИКАЦИИ И РЕФЕРИРОВАНИЯ ДОКУМЕНТОВ ДЛЯ ИНТЕРНЕТ-ПОРТАЛА часть 2

Автор: Вячеслав Ланин
Abstract: В статье представлено описание предполагаемых подходов к реализации подсистемы обработки информации на Интернет-портале. Основные проблемы связаны с экспоненциальным ростом числа документов, отсутствием семантического индексирования и неструктурированным характером информации. При реализации предлагаемого подхода пользователь получает эффективные интеллектуальные средства поиска электронных документов на основе семантической индексации, автоматической классификации и каталогизации документов с построением семантических связей между ними и автоматического реферирования документов с использованием знаний. Эффективность работы с электронными документами предлагается значительно увеличить за счет их интеллектуального анализа, для которого применяются агентный и онтологический подходы. В соответствии с предлагаемым подходом онтология используется для описания семантики данных документа и его структуры. В процессе анализа документа онтология является центральным понятием – благодаря использованию онтологий из документа можно получить требуемые данные: известно, где искать данные и как они могут быть интерпретированы. Репозитарий онтологий содержит три уровня онтологий: на первом уровне расположены онтологии, описывающие объекты, используемые в конкретной системе и учитывающие ее особенности; на втором в терминах объектов первого уровня описываются объекты, инвариантные к предметной области; объекты третьего уровня описывают наиболее общие понятия и аксиомы, с помощью которых описываются объекты нижележащих уровней. Третий и второй уровни можно разделить на две составляющие: описание структур и описание самих документов.
Keywords: онтология, агент, мультиагентные системы, интеллектуальный поиск, семантическое индексирование, анализ документов, адаптируемые информационные системы, CASE-технология.
ACM Classification Keywords: H.2 Database Management: H.2.3 Languages – Report writers; H.3.3 Information Search and Retrieval – Query formulation.
Conference: The paper is selected from XVth International Conference «Knowledge-Dialogue-Solution» KDS 2009, Varna, Bulgaria, June-July 2009

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

( Читать дальше )

РАБОТА С АНАЛИТИЧЕСКИМИ ОТЧЁТАМИ В ИССЛЕДОВАТЕЛЬСКОМ ПОРТАЛЕ “ИННОВАЦИОННОЕ РАЗВИТИЕ РЕГИОНОВ”

РАБОТА С АНАЛИТИЧЕСКИМИ ОТЧЁТАМИ В ИССЛЕДОВАТЕЛЬСКОМ ПОРТАЛЕ “ИННОВАЦИОННОЕ РАЗВИТИЕ
РЕГИОНОВ”


Автор: Павел Мальцев
Аннотация: Рассмотрена архитектура и базовые концепции подсистемы представления отчётов в программном комплексе BiP. Программный комплекс BiP предназначен для многомерного анализа данных, получаемых из гетерогенных источников. Он позволяет упростить разработку приложений Business Intelligence. Программный комплекс BiP включает набор готовых компонентов, которые могут быть использованы при разработке приложений. В частности, в комплексе BiP реализована подсистема представления отчётов. В данной работе приводится описание этой подсистемы и пример её использования при разработке исследовательского портала “Инновационное развитие регионов”.
Keywords: Business Intelligence, BI, бизнес-анализ, OLAP, Reporting, системы поддержки принятия решений, DSS, информационно-аналитические системы.
ACM Classification Keywords: H.4 Information Systems Applications: H.4.2 Types of Systems – Decision support (e.g., MIS).
Conference: The paper is selected from Seventh International Conference on Information Research and Applications – i.Tech 2009, Varna, Bulgaria, June-July 2009

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

( Читать дальше )

ИССЛЕДОВАТЕЛЬСКИЙ ПОРТАЛ «ИННОВАЦИОННОЕ РАЗВИТИЕ РЕГИОНОВ»

ИССЛЕДОВАТЕЛЬСКИЙ ПОРТАЛ «ИННОВАЦИОННОЕ РАЗВИТИЕ РЕГИОНОВ»

Авторы: Людмила Лядова, Жанна Мингалева, Наталья Фролова
Аннотация: Представлен проект, направленный на создание информационно-аналитической системы, предназначенной для решения задачи организации коллективной работы исследователей, поддержки их оперативного взаимодействия по одной из актуальных проблем в области экономики – проблеме инновационного развития регионов. В рамках проекта создается портал, обеспечивающий возможность публикации, поиска, анализа и каталогизации материалов по заданной тематике, обмен информацией. В системе должны быть размещены не только публикации, полученные из различных источников, но и результаты работы исследователей, участвующих в проекте, в частности, предлагаемые ими модели инновационного развития предприятий, отраслей, регионов, количественной и качественной оценки уровня их инновационного развития в условиях, с одной стороны, интеграции, а с другой – усиления конкуренции. Особое внимание в проекте уделяется использованию современных информационных технологий для проведения исследований. Программное обеспечение портала включает средства поиска информации в различных источниках, ее аналитической обработки в соответствии с разработанными методиками. Доступ к порталу будет обеспечен для пользователей различных категорий (ученых, преподавателей, студентов, специалистов органов власти и управления). Первый этап – создание исследовательского прототипа системы. Первоначальное наполнение предлагается выполнить на основе материалов, предоставленных участниками проекта (в частности, методика комплексной оценки инновационного развития региона, основой которой являются экономико-математические методы и модели; модель предметной области, построенная на основе онтологий, используемая для поиска и анализа документов и данных; и пр.).
Keywords: инновации; модели инновационного развития; онтология; интеллектуальный поиск; аналитическая обработка данных; Web-технологии.
ACM Classification Keywords: H. Information Systems. H.3 Information storage and retrieval: H.3.5 Online
Information Services – Web-based services; H.3.6 Library Automation – Large text archives.
Conference: The paper is selected from Seventh International Conference on Information Research and Applications – i.Tech 2009, Varna, Bulgaria, June-July 2009

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

( Читать дальше )

ПРИМЕНЕНИЕ ОЦЕНОЧНОЙ МОДЕЛИ ДЛЯ АНАЛИЗА УСЛОВИЙ ДОСТУПА К КЛАСТЕРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ часть 2

ПРИМЕНЕНИЕ ОЦЕНОЧНОЙ МОДЕЛИ ДЛЯ АНАЛИЗА УСЛОВИЙ ДОСТУПА К КЛАСТЕРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ

ПРИМЕНЕНИЕ ОЦЕНОЧНОЙ МОДЕЛИ ДЛЯ АНАЛИЗА УСЛОВИЙ ДОСТУПА К КЛАСТЕРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ часть 1
ПРИМЕНЕНИЕ ОЦЕНОЧНОЙ МОДЕЛИ ДЛЯ АНАЛИЗА УСЛОВИЙ ДОСТУПА К КЛАСТЕРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ часть 2

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

( Читать дальше )

ПРИМЕНЕНИЕ ОЦЕНОЧНОЙ МОДЕЛИ ДЛЯ АНАЛИЗА УСЛОВИЙ ДОСТУПА К КЛАСТЕРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ часть 1

ПРИМЕНЕНИЕ ОЦЕНОЧНОЙ МОДЕЛИ ДЛЯ АНАЛИЗА УСЛОВИЙ ДОСТУПА К КЛАСТЕРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ

ПРИМЕНЕНИЕ ОЦЕНОЧНОЙ МОДЕЛИ ДЛЯ АНАЛИЗА УСЛОВИЙ ДОСТУПА К КЛАСТЕРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ часть 1
ПРИМЕНЕНИЕ ОЦЕНОЧНОЙ МОДЕЛИ ДЛЯ АНАЛИЗА УСЛОВИЙ ДОСТУПА К КЛАСТЕРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ часть 2

Автор: Вячеслав Чумаченко
Аннотация: Рассмотрены вопросы построения информационного обеспечения территориального кластера и создания сети доступа для его участников. Рассмотрена проблема оценивания сети доступа как сложной развивающейся системы на примере использования векторной оценочной модели.
Ключевые слова: территориальный кластер, векторная оценочная модель, информационная система, сеть доступа, оценка набора параметров.
ACM Classification Keywords: С.2. Computer-communication networks, H. Information Systems — H.1 Models and Principles, K. Computing Milieux — K.6 Management of computing and information system
Conference: The paper is selected from XVth International Conference «Knowledge-Dialogue-Solution» KDS 2009, Varna, Bulgaria, June-July 2009

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

( Читать дальше )

МУЛЬТИАГЕНТНАЯ СИСТЕМА ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ИМИТАЦИОННОЙ МОДЕЛИ С УДАЛЕННЫМ ДОСТУПОМ часть 2

МУЛЬТИАГЕНТНАЯ СИСТЕМА ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ИМИТАЦИОННОЙ МОДЕЛИ С УДАЛЕННЫМ ДОСТУПОМ
МУЛЬТИАГЕНТНАЯ СИСТЕМА ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ИМИТАЦИОННОЙ МОДЕЛИ С УДАЛЕННЫМ ДОСТУПОМ часть 1
МУЛЬТИАГЕНТНАЯ СИСТЕМА ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ИМИТАЦИОННОЙ МОДЕЛИ С УДАЛЕННЫМ ДОСТУПОМ часть 2

Агент выявления атаки
Агент выявления атаки, несомненно, является самым важным компонентом всей подсистемы обнаружения вторжений, ведь именно ему предстоит решить самую сложную задачу – обнаружить попытку вторжения в систему Triad.NET (множество G целей агента). Этот агент реализуется как когнитивный агент c развитой моделью внешнего мира, у него должна быть своя внутренняя память, но главное – он должен уметь вести сложные и рефлексивные рассуждения. Основным компонентом агента выявления атаки является специальная база сигнатур атак. Под сигнатурой мы будем понимать некоторый признак трафика, определяющий одну из известных атак. База сигнатур состоит из правил. В базе сигнатур атак агент выявления атак хранит правила, описывающие различные виды атак, известные подсистеме обнаружения вторжений. Естественно, с появлением новых атак база сигнатур атак должна пополняться.

( Читать дальше )

МУЛЬТИАГЕНТНАЯ СИСТЕМА ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ИМИТАЦИОННОЙ МОДЕЛИ С УДАЛЕННЫМ ДОСТУПОМ часть 1

МУЛЬТИАГЕНТНАЯ СИСТЕМА ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ИМИТАЦИОННОЙ МОДЕЛИ С УДАЛЕННЫМ ДОСТУПОМ
МУЛЬТИАГЕНТНАЯ СИСТЕМА ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ИМИТАЦИОННОЙ МОДЕЛИ С УДАЛЕННЫМ ДОСТУПОМ часть 1
МУЛЬТИАГЕНТНАЯ СИСТЕМА ЗАЩИТЫ РАСПРЕДЕЛЕННОЙ ИМИТАЦИОННОЙ МОДЕЛИ С УДАЛЕННЫМ ДОСТУПОМ часть 2

Авторы: Александр Миков, Елена Замятина, Михаил Панов
Аннотация: В работе рассматривается распределенная система имитации Triad.Net с удаленным доступом. Обсуждаются программные средства, позволяющие исследователям удаленно и совместно с другими исследователями через Internet взаимодействовать с имитационной моделью, а также наблюдать за поведением модели во время имитационного эксперимента. Реализация удаленной системы диктует необходимость разработки подсистемы защиты, которая осуществляет обнаружение вторжений и противодействует злоумышленникам. Для реализации подсистемы защиты был выбран мультиагентный подход, позволяющий осуществить эффективную работу в компьютерной сети.
Keywords: Имитационное моделирование; системы защиты от вторжений; мультиагентная система.
ACM Classification Keywords: I.6 Simulation and Modelling – I.6.2 Simulation Languages; I.2 Artificial
Intelligence – I.2.5 Programming Languages and Software – Expert system tools and techniques.
Conference: The paper is selected from Seventh International Conference on Information Research and Applications – i.Tech 2009, Varna, Bulgaria, June-July 2009

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

( Читать дальше )

СТРУКТУРНЫЙ СИНТЕЗ СЕТЕЙ С ТЕХНОЛОГИЕЙ MPLS

СТРУКТУРНЫЙ СИНТЕЗ СЕТЕЙ С ТЕХНОЛОГИЕЙ MPLS

Авторы: Елена Зайченко, Юрий Зайченко
Abstract: The problem of MPLS computer networks structural synthesis under constraints is considered. The method of network structure optimization is suggested which utilizes ideas of genetic algorithm. The experimental investigations of the suggested algorithm are presented and discussed.
Keywords: MPLS network, structure synthesis, quality of service (QoS), network optimization
ACM Classification Keywords: C2. Computer-communication networks
Conference: The paper is selected from XVth International Conference «Knowledge-Dialogue-Solution» KDS 2009, Varna, Bulgaria, June-July 2009

Введение
Одной из наиболее перспективных телекоммуникационных технологий является технология многопротокольной коммутации меток (MPLS). Эта технология предоставляет унифицированный транспортный механизм для передачи разнотипной информации – аудио, видео и данных на высоких скоростях и обеспечивает заданное качество обслуживание (QoS).
Одной из важных задач, которые стоят перед проектировщиками сетей с технологией MPLS есть задача структурного, или топологического синтеза сети, под заданную входную нагрузку, в результате которой определяется общая структура сети, типы каналов связи, их пропускные способности, распределение потоков при ограничениях на заданный уровень QоS для потоков разных классов обслуживания (Class of Service) по критерию стоимости. При этом как дополнительные ограничения могут выступать показатели надежности и живучести сети.
В рамках решения задачи построения сети, кроме задачи выбора топологии, стоит задача выбора оптимальных пропускных способностей будущей сети при априори неизвестных, то есть нераспределенных потоках, базируясь лишь на требованиях к объему данных, которые должны передаваться между узлами сети. Решение этой задачи является необходимым для оценки стоимости построенной структуры, следовательно, и для выбора оптимальной.
Ранее задачи структурного синтеза сети с перспективными технологиями рассматривались для сетей с технологией ATM (Asynchronous Transfer Mode) и был разработан и исследован достаточно эффективный алгоритм оптимизации структурного синтеза, который учитывает специфику технологии ATM в частности наличие нескольких категорий сервиса CBR, VBR и ABR [Зайченко Е.Ю., 2003].
Целью настоящей работы является постановка и формализация задачи синтеза структуры сетей с технологией MPLS, разработка соответствующего метода ее решения и его исследования.

Математическая модель задачи структурного синтеза сетей Задано множество узлов сети X? ?x j? j? 1, n — маршрутизаторов MPLS (так называемых LRS – Label Switching Routers), их размещение по территории региона, набор пропускных способностей каналов связи D? ?d1, d2, ..., dk? из которых ведется синтез их удельных стоимостей на длины C c1, c2, ..., ck?, определены классы обслуживания CoS (Class of Service), известны матрицы входящих требований для k-го класса H (k )? hij (k ) i, j? 1, n; k? 1, 2,..., K, где hij (k ) – интенсивность k-го класса, которых необходимо передавать из узла i в узел j за единицу времени (Кбит/с).
Кроме того, введены ограничения на показатели качества QoS для каждого класса k в виде ограничения на среднюю задержку Tзад,k, k? 1, K
Требуется найти структуру сети в виде набора каналов связи (КС) E? ?(r, s)?, выбрать пропускные способности (ПС) каналов связи ??rs и найти распределение потоков всех классов F (k )? [ frs (k )], таким образом, чтобы обеспечить передачу требований всех классов H (k ) в полном объеме и с задержками Tср, не превышающими заданные Tзад, к и при этом бы выполнялись ограничения на долю потерянных пакетов CLPk, а стоимость сети была бы минимальной [Зайченко Е.Ю., 2006].
Составим математическую модель данной задачи синтеза.
Требуется найти такую структуру сети E, для которой: СLPk ({? rs };{ f rs }) frs rs для всех (r, s), (.3) rs? D, (4) СLPk ({? rs };{ f rs })? CLPk зад, (5) — доля потерянных пакетов для потока к –го класса (приоритета), CLPk зад — заданное ограничение на эту величину.
В работе [Зайченко Е.Ю., 2007] было получено следующее выражение для средней задержки Tср ,k: K rs при условии, что i ?1 f (i ) f где f (i ) — величина потока класса i в КС ( r, s ).
В работах [Зайченко Е.Ю., 2007] получено следующее выражение для величины доли потерянных пакетов в каналах ( r, s ): нормирующий множитель, nrs — число цифровых каналов базовой пропускной способности (1.544 Mбит/с) в линии связи ( r, s ); класса. N rs — размер буфера коммутатора MPLS, выделенного для потока к-го Тогда вероятность отсутствия потерь пакетов в сети из множества каналов Е равна P (1? CLPrs ), а средняя вероятность, (доля) потерянных пакетов К-го класса в целом по сети (r ,s)?E
Данная задача синтеза структуры относится к ьклассу комбинаторных задач дискретного программирования и является NP — полной задачей. Поэтому для ее решения предлагается генетический метод структурного синтеза.

Описание метода структурного синтеза
Метод состоит из двух этапов: предварительного и основного [Зайченко Е.Ю., 2006].
Цель предварительного этапа: синтезировать начальную структуру сети, удовлетворяющую условиям заданной связности.
На основном этапе, состоящем из однотипных итераций, осуществляем оптимизацию структуры текущей сети по стоимости при ограничениях на заданные значения показателей качества QoS.
На предварительном этапе, используя алгоритм Исау-Вильямса, сначала строим кратчайшее связывающее дерево из исходных узлов, а затем дополняем его до заданной связности 2.
Переходим на первую итерацию оптимизации основного этапа.
На этом этапе используется генетический алгоритм структурного синтеза. При этом генерируется случайным образом популяция из N начальных структур необходимо для реализации генетического метода. E1 ?0?, E2 ?0?,…, E N ?0?, что

Основной этап.
Этот этап состоит из однотипных итераций, на каждой из которых осуществляется оптимизация текущей структуры в памяти по критерию стоимости при ограничениях на среднюю задержку. (k+1) итерация.
Допустим, что в результате k-й итерации построена текущая популяци П E1 (k ),..., Ei (k ),..., EN (k )?. Обозначим через i (k ) C? (Ei (k )) — величину критерия для структуры
1.С вероятностью модификации. pi (k ) обратно пропорциональной C (Ei ) выбираем структуру
2.Для структуры Ei (k ) определяем множество КС — претендентов на удаление R сохранения заданной связности и множество КС — претендентов на ввод Rвв ,i (k ). удi (k ) по условиям
3.Для КС (r, s)? R вычисляем показатель неэффективности и с вероятностями qrs выбираем канал (r*, s* ), удаляем его из структуры Ei (k ) и ( r ,s ) Pуд получим E ( н ) (k )? E (k ) \ (r*, s* ).
4.Для структуры E ( н ) (k ) решаем задачу анализа сети, а именно ВПС РП, используя алгоритм ВПС и РП, описанные в [Зайченко Е.Ю., 2007], и находим новые ПС ?? ( н ) (k )? и распределение потоков F k frs k. Вычисляем её стоимость C
5.Сравнение. Если C ( н ) (k )? С Ei (k )?, (12) то полагаем E (k? 1)? E ( н ) (k ) и записываем структуру Ei (k? 1) вместо Ei (k ) в популяцию П. И конец итерации (k+1). Иначе на шаг 6.
6.Анализируем множество КС претендентов на ввод — Rвв ,i (k ), для них рассчитываем показатели эффективности от ввода в структуру КС (i, j) вв Crs ( frs ). rs frs — стоимость передачи информации между узлами i и j по маршруту Пij в структуре Ei (k ); Cij — стоимость введения нового КС (i, j); (i, j ) f( r ,s ) — доля трафика в КС (r, s) между узлами (i, j); frs — суммарный трафик в КС (r, s).
7.С вероятностями вв Gij Gij выбираем из множества Rвв (k ) КС (i*, j* ) и вводим его в (i, j )?Pвв структуру Ei (k ). Получим структуру K ( H )Ei(k )? Ei (k )? (i*, j *) \ (r *, s* ).
8.Для структуры ( н ) E i решаем задачу ВПС РП, используя алгоритмы ВПС и РП, находим новые ПС
9.Проверяем условие: если C ( н ) (k )? С? Ei (k )?, (14) ( н ) то фиксируем структуру E i (k )? Ei (k? 1), записываем структуру Ei (k? 1) вместо Ei (k ) в текущую популяцию П. Конец итерации.
10.В противном случае восстанавливаем прежнюю структуру Ei (k ) и удаляем КС (i*, j* ) из списка претендентов: Rвв (k )? Rвв (k ) \ (i*, j* ) и переходим на шаг 11.
11.Проверка условия Pвв (k ) ??.. Если да, то на шаг 6. Иначе на шаг 12.
12.Удаляем КС (r*,s*) из списка претендентов на удаление P (н ) (к )? Р уд (к ) \ (r *, s * ).
13.Проверка условия P (н) (k ) ??.. Если да, то восстанавливаем структуру Ei (k ). Восстанавливаем исходное множество претендентов на ввод Pвв (k ) и на шаг 2. Повторяем шаги 2-13. Иначе на шаг 14.
14.Востанавливаем прежнюю структуру Ei (k ). Она не может быть улучшена и зафиксируем ее в популяции ?(k ). Выбор другой структуры E j (k ) из популяции ?(k ).
Повторяем с ней шаги 1?13 до тех пор, пока один либо из них не закончится исходом (14), и тогда конец (k+1)-й итерации, либо фиксируем в популяции структуру E j (k ) как такую, которая не может оптимизирована и выбираем очередную структуру и из популяции для ?(k ) оптимизации.
Метод прекращает работу, когда все текущие структуры некоторой популяции ?(r ) будут зафиксированы, как невозможные для улучшения. Тогда выбираем из популяции структуру минимальным значением критерия C? и конец работы метода. Ei (k )
Как следует из приведенного описания, данный метод использует идеи генетического алгоритма вместе с направленным перебором вариантов.
Поскольку используется механизм селекции, то на каждой итерации значение критерия улучшается. Этим обеспечивается сходимость к оптимальному решению.
В данном случае получаемая структура является локально-оптимальной. Но вместе с тем, при некотором усложнении механизмов генерации новых структур (потомков) и увеличении числа итераций можно обеспечить сходимость к глобально-оптимальному решению

Экспериментальные исследования
С целью реализации предложенного метода структурного синтеза была разработана соответствующая программа синтеза сетей MPLS, которая вошла составной частью в инструментальный программный комплекс “MPLS NETBuilder”. Были проведены ее экспериментальные исследования в процессе проектирования глобальной сети с технологией MPLS Украины. В процессе экспериментов варьировались матрицы требований входящих потоков, ограничения на показатели качества обслуживания. Некоторые из результатов приводятся ниже.
В первой серии экспериментов исследовались зависимости получаемых структур сетей от величин матриц входящих требований Н®. При этом матрица требований для класса r умножалась на коэффициент k: Н?®= k Н0®.
В первом эксперименте принималось k=0,2.
Заключение

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

ФРАКТАЛЬНОЕ МОДЕЛИРОВАНИЕ И МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ КОМПЬЮТЕРНЫХ СЕТЕЙ

ФРАКТАЛЬНОЕ МОДЕЛИРОВАНИЕ И МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ КОМПЬЮТЕРНЫХ СЕТЕЙ

Автор: Адиль Тимофеев
Аннотация: Обсуждаются проблемы фрактального моделирования и многокритериальной оптимизации, возникающие при проектировании и системном анализе компьютерных сетей (КС). Предлагаемый подход основан на методе построения множества недоминируемых (наилучших на рассматриваемом множестве) альтернатив и методе построения логических функций переменной значности по базе данных, содержащей информацию об альтернативах, в роли которых выступают типовые топологические структуры КС.
Keywords: фрактальное моделирование, многокритериальная оптимизация, компьютерная сеть.
ACM Classification Keywords: E.4 CODING AND INFORMATION THEORY
Conference: The paper is selected from XVth International Conference «Knowledge-Dialogue-Solution» KDS 2009, Varna, Bulgaria, June-July 2009

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

( Читать дальше )