319

ITHEA

ОПЫТ ИСПОЛЬЗОВАНИЯ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ВЫБОРА

В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ И РИСКА

ПРИ ПРОЕКТИРОВАНИИ КОМПЬЮТЕРНЫХ СЕТЕЙ

Максим Соломицкий, Оксана Болотина

Аннотация: На основе анализа, касающегося возможных методов выбора оптимального варианта, определен универсальный метод, для проектирования компьютерных сетей. Построена математическая модель выбора оптимального критерия при заданных параметрах задачи выбора и модель реализации решения. Разработан и внедрен в учебный процесс комплекс лабораторных работ на базе обучающей компьютерной программы «SMPR» с целью повышения эффективности обучения студентов специальности «Компьютерные системы и сети».

Ключевые слова: компьютерная сеть, проектирование, метод выбора, критерий выбора.

Ключевые слова классификации ACM: H. Information Systems - H.1 MODELS AND PRINCIPLES, C.

Computer Systems Organization - C.2 COMPUTER-COMMUNICATION NETWORKS, E. Data - E.0 GENERAL.

« … ничто не дается даром в этом мире, и приобретение знания – труднейшая из всех задач, с какими человек может столкнуться … »

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

Именно поэтому в данной работе проведен анализ методов решения задач выбора в условиях неопределенности и риска. Представлен соответствующий опыт при проектировании компьютерных сетей, которому уделяется большое внимание при подготовке специалистов по компьютерным системам и сетям направления обучения «Компьютерная инженерия». Разработана математическая модель выбора оптимального метода решения задачи выбора и модель реализации решения этой задачи, а также комплекс лабораторных работ для решения инженерных задач выбора при проектировании компьютерных сетей. Для этого был использован программный продукт «SMPR», предложенный и любезно предоставленный профессором Киевского национального университета им. Т.Г. Шевченко д.т.н.

А.Ф. Волошиным. Программа «SMPR» позволяет лицу, принимающему решение (ЛПР), выбрать альтернативу автоматически, для чего рассчитывается приемлемость каждого из вариантов в зависимости от состояний внешней среды и составляется матрица решений, согласно которой программа определяет оптимальную альтернативу.

320 Problems of Computer Intellectualization Анализ этапов проектирования компьютерной сети Прежде чем начать анализ этапов проектирования напомним суть понятия «компьютерная сеть». Под компьютерной сетью понимается совокупность компьютеров и объединяющих их аппаратных средств, работающих под управлением сетевой операционной системы и прикладного программного обеспечения.

Компьютерные сети объединяют отдельные компьютеры для обеспечения их взаимодействия и позволяют распределять ресурсы при помощи каналов связи [1].

При этом к компьютерным сетям предъявляются такие требования:

– способность обрабатывать и передавать данные – основной и наиболее характерный для них тип трафика;

– обеспечение скоростей передачи данных до сотен мегабит и десятков гигабит в секунду;

– простота управления, т.к. операторами сетей зачастую являются пользователи, а не специалисты телекоммуникаций [2].

Приведем пример последовательности этапов и варианты выбора при проектировании компьютерной сети (КС). Проблема выбора вариантов при проектировании КС является основной, при этом выбор затрудняет необходимость учитывать требования, иногда противоречащие друг другу, например, в процессе эксплуатации спроектированная КС должна обеспечивать максимальное качество обслуживания. Это значит, что передача необходимых объемов данных в КС должна осуществляться своевременно и безошибочно. Для реализации таких требований необходимо применение надежных, высокопроизводительных, близких к безынерционным, и поэтому дорогостоящих систем передачи.

Однако, при этом же перед инженером-проектировщиком может стоять задача минимизации затрат на разработку КС, что существенно усложняет выбор оптимальных, с точки зрения качества обслуживания, вариантов.

При построении новой сети учитываются следующие факторы.

1. Необходимый масштаб сети в настоящее время, и в перспективе, где под масштабом сети понимается количество компьютеров, которые объединяются в сеть и расстояния между ними.

2. Структура, иерархия и основные элементы сети по подразделениям предприятия, комнатам, этажам и помещениям здания, где под структурой сети понимается способ распределения сети на сегменты и способ объединения этих сегментов. Структура сети должна отвечать структуре помещения или комплекса помещений предприятия. Рабочие места группы работников, которые занимаются одной задачей, желательно размещать в одной или в смежных комнатах.

3. Основные направления и интенсивность информационных потоков в сети по состоянию на данное время и на перспективу.

4. Характер информации, передаваемой по сети (данные, оцифрованная речь, изображения, т.д.).

5. Технические характеристики оборудования и его стоимость.

6. Возможности прокладки кабельных линий в помещениях и между ними, обеспечение целостности кабеля.

7. Обслуживание сети.

8. Контроль безотказности и безопасности.

9. Требования к программным средствам по допустимому масштабу сети, скорости, гибкости, разграничении прав доступа, стоимости, а также по возможностям контроля обмена информацией.

ITHEA Последовательность действий при проектировании и построении сети представлена в виде блок-схемы, изображенной на рисунке 1.

1. Входные данные:

- цели использования сети;

- необходимые характеристики сети и ее составляющих;

- характеристики существующих компьютеров;

обеспечение.

2. Основные сетевые решения:

- выбор размера и структуры сети;

- выбор оборудования;

- выбор сетевых программных средств;

- сетевое управление.

3. Выбор с учетом стоимости:

- анализ основных направлений финансовых затрат.

4. Проектирование кабельной системы:

- прокладка кабеля;

- установка розеток.

- активных сетевых устройств; - проверка и поиск неисправностей в кабельной - программного обеспечения. - анализ сетевых протоколов.

Рис.1 Последовательность действий при проектировании компьютерной сети Решение задачи и математическая модель выбора критерия сравнения альтернатив, при выборе оптимальной структуры компьютерной сети, при заданных параметрах Существует ряд задач выбора, с которыми сталкивается инженер при проектировании КС. Это выбор типа сети, технологии, топологии, количества и основных характеристик оборудования, емкости сети и т.д. Все эти задачи имеют некоторую схожесть с точки зрения теории принятия решений. Определим, какие из методов сравнения альтернатив можно использовать при проектировании КС. Как известно, каждый из методов имеет ряд условий, при которых можно его использовать. Такими условиями могут быть:

– допустимость или недопустимость риска;

– реализация решения один или бесконечное количество раз;

– известна или нет вероятность проявления состояний внешней среды.

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

Неопределенность в данном случае может касаться увеличения потребностей, необходимости масштабирования сети, квалификации пользователей, даже погодных условий, которые, в свою очередь, также влияют на среду передачи данных. Допустим, что используемый метод сравнения альтернатив должен учитывать то, что вероятность проявлений состояний внешней среды неизвестна, поскольку в ходе проектирования могут возникнуть новые условия, которые нельзя предусмотреть заранее.

Для того чтобы учесть все возможные события, исправить ошибки, можно реализовать решение несколько раз для проверки метода и анализа полученных результатов. Главным параметром, согласно которому будем делать выбор при решении поставленной задачи в данном случае, является наличие риска. Именно этот фактор определяет решительность ЛПР, уверенность в получении оптимального результата, возможность доказать то, что пожертвовав какими-то материальными средствами в настоящий момент, в будущем будет извлечена большая выгода.

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

Построим математическую модель, состоящую из двух частей. Первая часть определяет метод выбора, наиболее подходящий для решения конкретной задачи. Входными данными в этом случае будут целевые функции методов выбора, критерием выбора – допустимость риска, учет состояний внешней среды, возможность реализации решения бесконечное множество раз. Ограничения формулируются самой постановкой задачи. Так как поставлена задача выбора в условиях неопределенности, то ограничениями являются: осведомленность ЛПР в конкретной предметной области; возможность получения дополнительных сведений. В таком случае для решения задачи используются методы, не учитывающие коэффициент риска. Если же поставлена задача выбора в условиях риска, то ограничением будет готовность ЛПР к риску и степень применимости критериев, учитывающих риск. Вне зависимости от типа задачи обязательным ограничением будет наличие временных ресурсов и возможность проведения решения несколько раз. Результатом работы модели является выбор метода, оптимального для конкретной задачи. Представим модель наглядно (рисунок 2). Для выбора оптимальной альтернативы, используя математическую модель, необходимо, в первую очередь, определиться с задачей, для которой она будет использоваться, и сформулировать цель. В конкретной задаче необходимо определиться с ограничениями, допущениями и предполагаемыми результатами. В зависимости от выдвинутых требований к методу выбора определяется множество ограничений. Под ограничениями в данном случае понимается тип задачи:

– в условиях неопределенности;

– в условиях риска.

Допущениями в таком случае будут такие предположения:

– об осведомленности ЛПР;

– о состояниях внешней среды и возможности их проявлений;

– предположение о том, что ЛПР хорошо владеет предметной областью, в которой необходимо принять решение;

– необходим ли сбор дополнительной информации.

Заданные значения:

Критерий Байеса-Лапласа:

Критерий максимизации вероятности:

Модальный критерий:

x * Arg min ESE ( x ) = Arg min max(max u( z, x ) u( x, s )).

Критерий стабильности:

Критерий Гурвица:

Критерий Ходжа-Лемана:

Критерий Гермейера:

x * Arg max EGE ( x ) = Arg max min p(s )u( x, s ) Критерий произведений:

Рис. 2 Модель выбора оптимального критерия для задачи с заданными условиями Определим основные характеристики анализируемых методов. Каждый метод можно применять в конкретных нижеприведенных условиях.

1. Допустимость риска (обозначим его R).

2. Учет проявлений состояний внешней среды (обозначим как S).

3. Возможность реализации решений бесконечное количество раз (обозначим как N).

В модели обозначения X характеризуют множество альтернатив, т.е. возможных вариантов. Множество S – множество проявлений состояний внешней среды. Множество Y характеризует возможные последствия от реализации выбранной альтернативы. В зависимости от сформированных множеств и решающих правил выбирается оптимальная альтернатива.

В зависимости от требований и условий, выдвинутых задачей, выбираем метод для дальнейшего выбора альтернативы. Для наглядности распределим критерии выбора альтернативы на несколько групп, в зависимости от условий в которых их можно применять (таблица 1). В результате анализа условий применения методов сформировано пять групп. Каждая группа содержит несколько методов, соответственно результатом выбора может быть множество методов.

Таблица 1 – Формальное представление критериев выбора альтернативы Опишем детально процесс определения критерия выбора оптимальной альтернативы. На первом этапе стоит постановка задачи, выделение основных аспектов критерия. На втором этапе осуществляется процесс полного перебора альтернатив (рисунок 3).

Если в условии задачи оговорена возможность допустить определенный риск, то список методов выбора альтернатив сокращается, т.е., если R = 1, то 5 группа методов отбрасывается.

Если ЛПР известны возможные проявления состояний внешней среды, т.е., если s S, S = 1, то для выбора альтернативы лучше использовать 1 и 2 группы методов.

Если реализовать решение можно бесконечное количество раз, т.е., если N, N = 1, то можно использовать 1-4 группы методов.

вероятности, – минимизации дисперсии оценки, – Байеса-Лапласа.

Для выбора метода, который даст наиболее точный результат необходимо рассмотреть все комбинации условий.

1. Если R = 1, s S, S = 1, N, N = 1, то на выходе получим целевые функции 1 группы методов:

– модальный критерий EMOD ( x ) = max u( x,s*);

– критерий максимизации вероятности – критерий минимизации дисперсии оценки – критерий Байеса-Лапласа Какой критерий из приведенного множества использовать решает ЛПР.

2. Если R = 1,s S,S = 1,N = 1 / 0, т.е. возможное количество реализаций N на результат не влияет и приведенные критерии можно использовать как при множестве решений, так и при малом их количестве, то на выходе получим целевые функции 2 группы методов:

– критерий Гермейера x* Arg max EGE ( x ) = Arg max min p( s )u( x,s ).

3. Если R = 1,S = 0,N,N = 1, то получим целевые функции 3 группы методов:

– оптимистический критерий – критерий Ходжа-Лемана 4. Если R = 1, s S, S = 0, N = 1 / 0, т.е. возможное количество реализаций N на результат не влияет и при этом нужно исключить риск, то на выходе получим целевые функции 4 группы методов:

– критерий произведений – критерий Гурвица x* Arg max EGW ( x ) = Arg max( max u( x,s ) + (1 )minu( x,s ));

– аддитивный критерий 5. Если же любой риск нужно исключить, про состояния внешней среды ничего не известно и решение реализуется лишь один раз, т.е. R = 0, S = 0, N = 0, то на выходе получим целевые функции 5 группы методов:

– критерий Севиджа x* Arg minESE ( x ) = Arg min max( max u( z,x ) u( x,s ));

– критерий стабильности x* X* = Arg minEST ( x ) = Arg min max( max u( x,t ) u( x,s ));

– минимаксный критерий Вальда x* Arg max EMM ( x ) = Arg max minu( x,s ).

Следующим этапом будет применение полученного критерия в задаче выбора альтернативы. Допустим, нам необходимо выбрать модель мобильного телефона, модификация предложенной модели для этого примера примет вид, показанный на рис. 4. Сформируем исходное множество данных для поставленной задачи. Заданными значениями будут модели телефонов. Множеством ограничений в данном случае будут характеристики телефонов. Основным критерием выбора для данной задачи будет цена. Если на первом этапе получена четвертая группа методов сравнения альтернатив, значит следует использовать критерии: произведений, Гурвица и аддитивный. Выбор конкретного метода осуществляет ЛПР. Для выбора телефона будем использовать целевую функцию сравнения альтернатив критерия Гурвица. В результате его работы получим модель телефона, оптимальную для заданных ограничений.

Чтобы показать возможность использования построенной модели при проектировании КС рассмотрим еще один пример. Необходимо выбрать технологию работы КС (рисунок 5).

– двухэтажное строение общей площадью 2000 м2;

– необходимо предусмотреть возможность масштабирования;

– на проектирование и построение сети выделено 7 дней;

– стоимость проектирования и построения не должна превышать 45000 грн.

Заданные значения:

– Frame Relay;

– X.25;

– ATM;

– Token Ring.

Заданными значениями в данном случае будут различные технологии компьютерных сетей. Одной их них является Ethernet – пакетная технология передачи данных, предназначенная преимущественно для локальных КС. Стандарты Ethernet определяют проводные соединения и электрические сигналы на физическом уровне, формат кадров и протоколы управления доступом к среде – на канальном уровне модели взаимодействия открытых систем (МВОС). В настоящее время Ethernet является самой распространённой технологией локальных КС. Еще одной является технология стандарта X.25 – семейства протоколов канального уровня МВОС, предназначенного для организации технологии транспортировки пакетов в КС на основе линий телефонных сетей с достаточно высокой частотой ошибок, поэтому содержит развитые механизмы коррекции ошибок. Протокол Х.25 ориентирован на работу с установлением соединений и является предшественником канальных технологий Frame Relay, АТМ, IP. Технология ретрансляции кадров Frame Relay представляет собой протокол канального уровня МВОС для организации в КС службы коммутации пакетов. Реализуя технологию транспортировки КС, Frame Relay обеспечивает множество независимых виртуальных каналов в одной физической линии связи, и, в основном, применяется при построении территориально распределённых корпоративных сетей, а также в составе технических решений, связанных с обеспечением гарантированной пропускной способности канала передачи данных. ATM – асинхронный способ передачи данных – сетевая высокопроизводительная технология коммутации и мультиплексирования, основанная на передаче данных в виде ячеек фиксированного размера. Технология реализуется как в локальных, так и в глобальных КС для совместной передачи различных видов информации при обеспечении требований пользователя к качеству обслуживания. Для передачи данных от отправителя к получателю в сети ATM создаются виртуальные каналы. Технология локальных КС в виде кольца с «маркёрным доступом» Token Ring реализует протокол локальной сети, который находится на канальном уровне МВОС и использует специальный трёхбайтовый фрейм, названный маркёром, который перемещается вокруг кольца. Сетевые рабочие станции на локальной КС Token Ring логически организованы в кольцевую топологию с данными, передаваемыми последовательно от одной кольцевой станции до другой с управляющим маркером, циркулирующим вокруг кольцевого доступа управления.

Ограничениями при выборе технологии КС будут характеристики условий, в которых необходимо построить сеть, к которым могут быть отнесены: размеры здания, количество пользователей, выделенные средства, временные ресурсы – т.е. требования заказчика. Критерием выбора в данном случае выберем оптимальную цену при обеспечении технологией требований к качеству и своевременности доставки информации. А в результате получим оптимальную технологию для заданных ограничений. Для выбора оптимальной технологии воспользуемся критерием произведений. В результате получим технологию работы КС, оптимальную с противоречащих друг другу позиций минимизации стоимости технологии и максимизации обеспечиваемого ею качества, удовлетворяющую сформулированным ограничениям.

Комплекс лабораторных работ для получения навыков использования методов принятия решений в сфере компьютерных сетей На основе программного продукта «SMPR», предоставленного профессором Киевского национального университета имени Т.Г. Шевченко д.т.н. Волошиным А.Ф., разработан комплекс лабораторных работ для получения навыков использования методов решения инженерных задач выбора при проектировании компьютерных сетей. При разработке данного комплекса, используемого при подготовке студентов специальности «Компьютерные системы и сети», были применены материалы [3,4], являющиеся основополагающими по теории принятия решений при подготовке выпускников квалификации магистров и специалистов Киевского национального университета и Одесской государственной академии холода.

Обобщенная последовательность этапов работы с программой «SMPR» представлена на рисунке 6.

Целью первой лабораторной работы является получение навыков работы с программой «SMPR» и закрепление базовых знаний теории принятия решений. Студентами в ходе работы изучаются основные принципы и этапы процесса принятия решений, понятия неопределенности и риска, векторные и скалярные критериальные постановки, особенности эвристических методов. В программе «SMPR»

предлагается пройти тест для определения готовности к риску, результаты теста используются в следующей лабораторной работе для определения числового значения коэффициента риска. Также студентам необходимо предложить свои три варианта задач выбора из сферы КС. Например, постановка задачи звучит так: необходимо выбрать топологию КС для двухэтажного дома, площадью 1500 м2, количество компьютеров 32. В данном случае множеством альтернатив будут топологии сети: шина, звезда, кольцо, решетка, дерево, комбинированная, т.д. Каждый вариант может описываться набором внешних характеристик, которые условно разделяются на показатели приемлемости, условия и ограничения. Множество состояний сети задано условиями задачи – это площадь, количество компьютеров, размеры здания и т.д.

Определение достоверности и точности полученных результатов с помощью программы «SMPR»

является целью второй лабораторной работы. Студентам предлагается выполнить анализ возможности применения критериев: модального, максимизации вероятности, минимизации дисперсии, БайесаЛапласа, для решения задач выбора в ходе проектирования КС. Для этого в ходе выполнения работы необходимо описать основные входные положения принятия решений в условиях неопределенности и риска, проанализировать экстенсивную и нормальную формы взаимосвязи триады множеств, виды матриц решений, освоить критерии вышеуказанные критерии. Затем студентам предлагается решить реальную задачу выбора оборудования, например, маршрутизатора. Множеством альтернатив в данном случае будут разные модели сетевых маршрутизаторов, множеством состояний внешней среды – необходимые характеристики.

1. Начальная форма Студенты составляют матрицу решений и решают задачу тремя способами:

– выбирают альтернативу эвристически и объясняют свой выбор;

– выбирают альтернативу, используя критерий Парето или Слейтера, и определяют наиболее подходящий из векторных критериев;

– выбирают альтернативы, используя программу «SMPR» и делают выбор с помощью следующих критериев: модального, максимизации вероятности, минимизации дисперсии оценки, Байеса-Лапласа;

сравнивают полученные результаты работы программы.

После этого студентам предлагается проанализировать результаты, полученные тремя разными способами решения, и определить, какой из способов решения дает наиболее точный результат.

Третья лабораторная работа посвящена решению задачи выбора с использованием критериев:

оптимистичного, Ходжа-Лемана, произведений, Гурвица и аддитивного, а также анализу полученных результатов. Целью работы является определение достоверности и точности результатов, полученных с помощью программы «SMPR». Студенты анализируют модели принятия решений и особенности указанных критериев. В ходе выполнения работы студентам предлагается решить задачу выбора топологии КС.

Размеры здания и условия студенты выбирают сами, затем составляют множество альтернатив, определяют возможные состояния внешней среды и составляют матрицу решений. Решить поставленную задачу предлагается тремя способами: эвристически, используя векторный критерий Парето или Слейтера, используя программу «SMPR» с помощью следующих критериев: оптимистичного, ХоджаЛемана, произведений, Гурвица и аддитивного. Затем студентам необходимо проанализировать результаты, полученные тремя разными способами решения, и определить наиболее точный, с точки зрения полученного результата, способ решения.

Решению задачи выбора с использованием критериев: Севиджа, стабильности, минимаксного, Гермейера, а также анализу полученных результатов посвящена четвертая лабораторная работа, цель которой – оптимизация поставленной задачи под избранный критерий. Студентам предлагается проанализировать особенности указанных критериев, провести классификацию критериев, изученных в течение курса лабораторных работ, определить группы критериев и объяснить полученное в результате распределение критериев, а также определить наиболее универсальной критерий, согласно условиям, в которых он может использоваться. В ходе работы необходимо решить задачу выбора технологии работы КС, составить множество альтернатив, определить возможные состояния внешней среды, составить матрицу решений.

Выводы В результате выполненной работы предложен и обоснован способ выбора метода, который целесообразно использовать при проектировании КС. Проведена классификация критериев решения задач выбора, согласно условиям, в которых они могут использоваться, при этом сформировано 5 групп методов. Разработана математическая модель определения оптимального метода решения задачи выбора и модель реализации решения этой задачи.

Разработан комплекс лабораторных работ для решения инженерных задач выбора при проектировании КС, используемый при подготовке бакалавров, специалистов и магистров специальности «Компьютерные системы и сети» кафедры информационно-коммуникационных технологий Одесской государственной академии холода. Для выполнения лабораторных работ использован программный продукт «SMPR»

профессора Киевского национального университета имени Т.Г. Шевченко д.т.н. Волошина А.Ф.

Благодарности Работа опубликована при финансовой поддержке проекта ITHEA XXI Института информационных теорий и приложений FOI ITHEA Болгария www.ithea.org и Ассоциации создателей и пользователей интеллектуальных систем ADUIS Украина www.aduis.com.ua.

Литература 1. Гайворонская Г. С. Инфокоммуникации: Учеб. пособие / Гайворонская Г. С. – Одесса: ОГАХ, 2006. – 90 с.

2. Гайворонская Г.С. Сети и системы телекоммуникаций / Гайворонская Г.С., Захарченко М.В. – К.: Техника, 2000. – 304с.

3. Гайворонская Г. С. Оптимальный синтез информационных сетей: Пособие для магистров / Гайворонская Г. С. – Одесса: ОГАХ, 2011. – 94 с.

4. Волошин О.Ф. Моделі та методи прийняття рішень: навчальний посібник для студ. вищ. навч. закл. / Волошин О.Ф., Мащенко С.О. – 2-ге вид. – К.: Видавничо-поліграфічний центр «Київський університет», 2010.

Информация об авторах факультет информационных технологий; аспирант кафедры информационнокоммуникационных технологий; ул. Дворянская, 1/3, Одесса-26, 65026, Украина;

Главные области научных исследований: проблемы создания конвергентных Оксана Болотина – Одесская государственная академия холода, факультет информационных технологий; магистр кафедры информационнокоммуникационных технологий; ул. Дворянская, 1/3, Одесса-26, 65026, Украина;