авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 9 |

«5. Математическое моделирование УДК 517.977.54 Б.И. Ананьев, Н.В. Гредасова ...»

-- [ Страница 6 ] --

Кибирев Владимир Васильевич, кандидат физико-математических наук, профессор кафедры прикладной математики Бурятского государственного университета, тел. (8301-2) 217573, dekanat_imi@bsu.ru Kibirev Vladimir Vasilievich, candidate of physical and mathematical sciences, the professor of the applied mathematics department of the Buryat State University.

Д.Д. Кононов, С.В. Исаев. Организация защиты информации веб-сервисов для поддержки управления муниципаль ным заказом УДК 004. Д.Д. Кононов, С.В. Исаев ОРГАНИЗАЦИЯ ЗАЩИТЫ ИНФОРМАЦИИ ВЕБ-СЕРВИСОВ ДЛЯ ПОДДЕРЖКИ УПРАВЛЕНИЯ МУНИЦИПАЛЬНЫМ ЗАКАЗОМ В работе решается задача организации сетевой информационной среды и защиты информации для поддержки муниципального управления. Представлены алгоритмические и программные средства для решения задач интер нет-поддержки муниципального заказа. Особенностью решения задачи является применение модели безопасности, адаптированной для веб-сервисов, использование электронной цифровой подписи. Обеспечивается оперативное размещение информации, поддержка данных в актуальном состоянии, защита данных. Предложенные решения характеризуются универсальностью и кроссплатформенностью.

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

D.D. Kononov, S.V. Isaev INFORMATION SECURITY IN WEB-SERVICES FOR MUNICIPAL ORDERS SUPPORT This article describes network information environment and information security for municipal government. Algo rithmic and software tools for solving problems of municipal orders Internet support are presented. The feature of our work is a security model adapted for web-services, and using digital signatures. Rapid deployment of information, keeping data up-to-date, and data protection are ensured. The proposed solutions are flexible and cross-platform.

Keywords: software, web-services, database systems, management support, information security, security model.

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

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

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

Веб-сервисы поддержки муниципального заказа должны решать такие задачи, как:

• публикация подписанных документов и другой информации;

• функции поиска и фильтрация данных;

• проведение электронных аукционов;

• проведение электронных запросов котировок;

• прием документов о муниципальных контрактах от заказчиков;

• прием заявок в реестр муниципальных потребностей.

Особое внимание уделялось исследованию проблем безопасности и обеспечения кроссплатформен ного функционирования веб-сервисов.

Разработка и внедрение созданных подходов и методов выполнялись в рамках развития автоматизи рованной системы проведения муниципальных заказов (АСП МЗ) [1] для департамента муниципального заказа администрации города Красноярска.

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ Организация хранения данных Одним из требований, предъявляемых к веб-сервисам муниципального заказа, является обеспечение возможности синхронизации оперативной базы данных АСП МЗ и базы данных веб-сервисов, что вле чет регулярные обновления больших объемов структурированной информации.

Синхронизация информации производится посредством специального шлюза, принимающего данные с автоматизированных рабочих мест. Объем оперативной базы данных очень велик и не требует полной публикации. Модель базы данных веб-сервисов разработана с учетом возможностей быстрого доступа к данным, требований по полноте и неизбыточности содержащейся информации. Разработанная модель данных позволила уменьшить объемы передачи информации и обеспечила хранение на веб-сервере только данных, подлежащих размещению в сети Интернет.

База данных автоматизированных рабочих мест построена на СУБД Oracle, серверная база данных — на СУБД PostgreSQL.

Информационная безопасность При создании информационных систем важную роль играет обеспечение защиты информации. Ис следование вопросов обеспечения безопасности веб-систем проводилось в [2].

Режим функционирования веб-сервиса предполагает авторизованную работу пользователей. В каче стве модели безопасности системы выбрана модель Role-Based Access Control (RBAC) [3, 4], которая была модифицирована для учета специфики веб-приложений. В модель RBAC добавлены новые поня тия «токен» (token) и «запрос» (request). Запрос принадлежит сессии, в рамках одной сессии может вы полняться несколько запросов. На множестве запросов вводится отношение включения, которое на множестве запросов задает отношение строгого частичного порядка. Полученная модель отражает предметную область и позволяет эффективно разграничивать доступ в веб-системах. Политики безопас ности доступны для редактирования администратором системы.

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

При создании системы проведен детальный анализ возможностей несанкционированного доступа к данным [5], рассмотрены основные классы угроз. На основе полученных данных применялись специ альные технологии, позволяющие обеспечить защиту он несанкционированного доступа (фильтрация параметров, проверка идентификаторов и т.п.). Построены программные решения для предотвращения атак типа XSS, инъекций кода и SQL, подмены файлов и сессий.

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

Механизмы работы с ЭЦП Особенности применения электронной цифровой подписи (ЭЦП) при решении задач муниципального управления рассмотрены в [6]. Электронная цифровая подпись используется для подтверждения дейст вий пользователя при решении следующих задач:

• проведение электронных аукционов;

• проведение электронных запросов котировок;

• прием документов о муниципальных контрактах от заказчиков;

• прием заявок в реестр муниципальных потребностей.

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

Д.Д. Кононов, С.В. Исаев. Организация защиты информации веб-сервисов для поддержки управления муниципаль ным заказом Рис. 1. Подача ценового предложения На рисунке 1 приведен снимок экрана при подаче ценового предложения участником открытого электронного аукциона. Участник размещения заказа вводит цену и нажимает кнопку «Подать».

Рис. 2. Подписание электронного документа для подтверждения действия После этого происходит формирование электронного документа, содержащего информацию об объ екте, субъекте (пользователе) и производимом действии (рис. 2). Пользователь нажимает кнопку «Под ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ писать», выбирает сертификат (если их несколько) и подписывает документ. Полученная подпись про веряется на сервере и в случае ее корректности указанное действие разрешается, а все данные вносятся в журнал. Торги проводятся в режиме реального времени, поэтому новая информация сразу же отобража ется у других участников электронного аукциона.

Подписание электронных документов осуществляется непосредственно в браузере пользователя.

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

Особенности реализации При разработке системы применен метод декомпозиции, при котором система разделяется на ядро и набор модулей, обеспечивающих определенный функционал. Система имеет интерфейс API, позволяю щий другим программным продуктам взаимодействовать с системой (рис. 1).

Рис. 3. Структура модулей системы Ядро управляет модулями и осуществляет позднее связывание (lazy linking) модулей, что позволяет снизить затраты на обработку страниц. Также используются технологии XML, AJAX, Friendly URLs, шаблоны. Для определенного класса данных применяется кэширование.

Важной особенностью построенной системы является обеспечение требований кроссплатформенного функционирования. Это достигается за счет использования кроссплатформенных базовых инструмен тальных средств, платформенно независимой организации программных модулей и данных. Серверная часть системы работает на операционных системах Windows, FreeBSD, Linux.

В работе используется криптопровайдер КриптоПро CSP, который обеспечивает работу стандартов ГОСТ Р 34.10-94, ГОСТ Р 34.11-94, ГОСТ Р 34.10-2001, ГОСТ 28147-89.

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

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

Д.Д. Кононов, С.В. Исаев. Организация защиты информации веб-сервисов для поддержки управления муниципаль ным заказом Реализованные веб-сервисы обеспечивают защиту публикуемых данных, простоту и удобство рабо ты специалистов муниципального заказа, оперативность размещения информации в сети Интернет, а также защиту от несанкционированного использования. Система успешно эксплуатируется более четы рех лет и обеспечивает экономию бюджетных средств. За 2009–2010 гг. с использованием системы было проведено 354 электронных аукциона на общую сумму 238 660 934 р., экономия бюджета составила 42 443 682 р. Имеются свидетельства о регистрации программного обеспечения [7, 8].

Литература 1. Шербенин В.Ф., Ноженкова Л.Ф., Жучков Д.В., Исаева О.С. Перспективные задачи автоматизации муници пального заказа как основа повышения качества управленческих решений // «ПИР-2009»: материалы XI Всерос.

науч.-практ. конф. – Красноярск: РИЦ СибГТУ, 2009. – С. 26-33.

2. Кононов Д.Д., Исаев С.В. Обеспечение безопасности веб-приложений на примере веб-сервера ИВМ СО РАН // Вестник ТГУ. – 2006. – № 17. – С. 156–161.

3. Sandhu, R., Coyne, E.J., Feinstein, H.L. and Youman, C.E. Role-Based Access Control Models // IEEE Computer (IEEE Press). 1996. – Vol. 29. – No. 2. – P. 38–47.

4. Ferraiolo D.F., Kuhn D.R. Chandramouli R. Role-Based Access Control. – Norwood: Artech House, Computer Se curity Series, 2003. 316 p.

5. Кононов Д.Д. Организация защиты информации при создании веб-системы информационной поддержки муниципальных заказов администрации Красноярска // Проблемы информатизации региона: материалы 10-й все рос. науч.-практ. конф. в 2 т. – Красноярск: Сиб. федер. ун-т;

Политехн. ин-т, 2007. Т. 1. – С. 115-120.

6. Кононов Д.Д., Исаев С.В. Применение электронной цифровой подписи для создания защищенных веб сервисов поддержки муниципальных закупок // Инфокоммуникационные и вычислительные технологии и систе мы: материалы III Междунар. конф. – Улан-Удэ: Изд-во Бурят. гос. ун-та, 2010. – С. 174–177.

7. Ноженкова Л.Ф., Исаев С.В., Кононов Д.Д., Исаева О.С., Жучков Д.В. Система проведения электронных ин тернет-аукционов // Свидетельство об официальной регистрации в Реестре программ для ЭВМ № 2009612095 от 24.04.2009 (Федеральная служба по интеллектуальной собственности, патентам и товарным знакам). – 2009.

8. Ноженкова Л. Ф., Исаев С. В., Кононов Д. Д., Исаева О. С. Интернет-система поддержки муниципального заказа // Свидетельство об официальной регистрации в Реестре программ для ЭВМ № 2009612093 от 24.04. (Федеральная служба по интеллектуальной собственности, патентам и товарным знакам). – 2009.

Кононов Дмитрий Дмитриевич, научный сотрудник Института вычислительного моделирования СО РАН, 660036, г. Красноярск, Академгородок, 50/44, тел. (391) 2494767, e-mail: ddk@icm.krasn.ru Исаев Сергей Владиславович, кандидат технических наук, старший научный сотрудник Института вычисли тельного моделирования СО РАН, 660036, г. Красноярск, Академгородок, 50/44, тел. (391) 2494767, e-mail:

si@icm.krasn.ru Kononov Dmitry Dmitrievich, scientific researcher of Institute of Computational Modeling SB RAS.

Isaev Sergey Vladislavovich, candidate of technical sciences, senior scientific researcher of Institute of Computational Modeling SB RAS.

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ УДК 004.832. А.А. Ларионов, Е.А. Черкашин, И.Н. Терехин СИСТЕМНЫЕ ПРЕДИКАТЫ ДЛЯ УПРАВЛЕНИЯ ЛОГИЧЕСКИМ ВЫВОДОМ В СИСТЕМЕ АВТОМАТИЧЕСКОГО ДОКАЗАТЕЛЬСТВА ТЕОРЕМ ДЛЯ ИСЧИСЛЕНИЯ ПОЗИТИВНО ОБРАЗОВАННЫХ ФОРМУЛ В статье предлагается подход к реализации процесса управления поиском автоматического доказательства тео рем в исчислении позитивно-образованных формул. Управление выводом представляется в виде комбинации сис темных предикатов в оригинальном логическом языке представления формул. Предложены рекомендации по ис пользованию подхода.

Ключевые слова: исчисление позитивно-образованных формул, автоматическое доказательство теорем, логи ческий вывод.

A.A. Larionov, E.A. Cherkashin, I.N. Terehin SYSTEM PREDICATES FOR CONTROL OF LOGICAL INFERENCE IN AUTOMATED THEOREM PROVING SYSTEMS BASED ON CALCULI OF POSITIVELY CONSTRUCTED FORMULAE An approach for a control process implementation of search for automated theorem proof in the calculi of positively constructed formulae is described in the paper. The search process is represented as system predicates and their combina tions in the original logical language for formulae definition. Application recommendations of the approach are proposed.

Keywords: calculi of positively constructed formulae, automated theorem proving, logical inference.

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

В логических языках программирования, например Прологе [1], введены так называемые системные предикаты (встроенные предикаты, built-in predicates), особенность которых заключается в том, что они или выполняют некоторое побочное действие, например, вывод на экран, чтение файла и другое, или их истинность вычисляется из значений параметров, например var(X) в Прологе определяет, является ли терм X переменной.

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

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

1. Исчисление позитивно-образованных формул и его свойства Пусть Con – множество всех конъюнктов. Будем предполагать, что конъюнкт есть либо конечное множество обычных атомарных формул (атомов) языка логики предикатов первого порядка, либо F, где F удовлетворяет свойству: A F для каждого A Con. Пустой конъюнкт будем обозначать T. Атомы любого конъюнкта, за исключением T и F, могут содержать термы, построенные по общим правилам языка исчисления предикатов первого порядка на основе индивидных переменных, индивидных кон стант функциональных символов.

Язык LF позитивно-образованных формул определяется следующим образом:

1) если A Con, то KX:A есть K -формула, где K {, }, X – множество индивидных перемен ных, элементы X будем называть K -переменными, либо, соответственно, универсальными и эк Работа выполнена при финансовой поддержке РФФИ, грант 10-07-00051-а.

А.А. Ларионов, Е.А. Черкашин, И.Н. Терехин. Системные предикаты для управления логическим выводом в систе ме автоматического доказательства теорем для исчисления позитивно-образованных формул зистенциальными переменными;

2) B Con, – множество K -формул, то MY:B есть M -формула, где M {, }, M K, Y – множество индивидных переменных;

3) каждая ПО-формула есть либо -формула, либо -формула.

Таким образом, ПО-формула имеет древовидную структуру. Поэтому в дальнейшем иногда удобнее будет представлять ПО-формулы именно в виде дерева, а также пользоваться соответствующей терми нологией: узел (позитивный квантор), ветвление, корень, лист.

Без потери общности будем считать, что корень ПО-формулы (узел 0-го уровня) есть :T, а каждый лист есть -формула (узел).

Любой узел вида X:A, непосредственно следующий за корнем (узел 1-го уровня), называется базой данной ПО-формулы. Конъюнкт A будем называть базой фактов. Подформула, корень которой есть ба за, называется базовой подформулой. Любой непосредственный потомок Y:B базы X:A (узел 2-го уровня) называется вопросом к базе X:A.

Семантика ПО-формулы вводится на основе обычной семантики соответствующей формулы () ИП в исчислении предикатов первого порядка:

1) если A Con,A {F,T}, то A& = & { : A}, F & = False, T & = True (пропозициональные кон станты);

X = { x1 …, xm }, (X:A ) ИП = x1 … xm ( A& & ( ) ИП ), 2) пусть тогда (X:A ) ИП = x1 … xm ( A& ( ) ИП ), где ( ИП ) = &{( ИП ): }, ( ИП ) = {( ИП ): }.

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

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

Будем говорить, что вопрос Y:B к базе X:A имеет ответ тогда и только тогда, когда – ото бражение (подстановка) Y H и B A, где H – эрбрановский универсум, основанный на пере менных из X (заметим, что это только экзистенциальные переменные), константах и функциональных символах, встречающихся в A B. Если X = и в A B нет констант и функциональных символов, то H = {a}, где a – некоторая новая константа.

Теперь определим единственное правило вывода исчисления JF. Если ПО-формула имеет струк туру : T {, X : A}, где – список других базовых подформул (поддеревьев) формулы, а со держит подформулу Y : B {Z i : Ci i }i =1, k, тогда результатом применения унарного правила вывода Y:B к вопросу с ответом является следующая формула:

{ } = :T, {X Zi : A Ci i }i =1,k.

После последующего переименования некоторых связанных переменных внутри каждой подформу лы выражение будет удовлетворять всем требованиям к ПО-формулам. Будем подразумевать это переименование каждый раз при применении правила. То же самое относится и к следующим упро щающим заменам: X : F заменяется на : F, : T {, : F } заменяется на :T, если.

Любая конечная последовательность ПО-формул,,…, n, где n = : T : F, называется вы водом в исчислении JF= LF, : T : F, (с аксиомой : T : F ).

2. Системные предикаты и способы управления логическим выводом Будем называть системным предикатом такой предикат, атомы которого входят в конъюнкты дерева ПО-формулы, но не участвуют непосредственно в ЛВ. Системные предикаты не имеют прямого отно шения к формализации задачи, однако влияют на процесс ЛВ некоторыми побочными действиям, их истинностные значения вычисляются, выводят некоторую системную информацию. В языках логиче ского программирования, например Прологе, системные предикаты служат в основном для исполнения некоторых интерактивных действий: вывод информации на экран, чтение и запись файла, добавление и удаление фактов и др.

Введем следующие системные предикаты:

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ Next(L). Переход к вопросу, помеченному идентификатором L. Предикат помещается в коньюнкт корневой вершины консенквента вопроса. Если на данный вопрос будет произведен ответ, то следую щим вопросом, для которого будет производится выбор ответа, будет вопрос (множество вопросов), по меченный идентификатором L. Таким образом, при помощи данного предиката задаются варианты по рядка ответа на вопрос.

OffQuestion(L)/OnQuestion(L). Отключение/включение вопроса с идентификатором L. От ключенный вопрос объявляется неактивным, то есть не принимает участие в логическом выводе, при этом в любой момент может быть заново включен.

RemQuestion(L). Удаление вопроса с идентификатором L.

RemFact(L) и RemPatternFact(L). Удаление факта помеченного идентификатором L, а также удаление всех основных примеров L, в случае если L – терм.

OffFact(L)/OnFact(L). Отключение и включение факта с именем L. Поведение подобно вклю чению и отключению вопросов.

Write(T). Печать терма T.

Save(L). Пометить состояние процесса поиска ЛВ в данной базовой подформуле идентификатором L.

Rollback(L). Откатить (backtrack) состояние вывода в базовой подформуле до состояния L с уте рей более поздних по отношению к L маркировок.

Commit(L). Фиксировать состояние базы L как неоткатываемое, при этом фиксируются все состоя ния, помеченные ранее, чем L. Предикаты Commit и Rollback без параметров фиксируют или откатыва ют последнюю метку.

Для пометки выражений используется следующий синтаксис E’(L), где E – выражение, L – метка.

Кроме того, вводятся арифметические операции, используемые в конъюнкте вопроса и вычисляющие свои аргументы. Если арифметическая операция выполняется над полученными в подстановке аргумен тами, то подстановка используется в шаге вывода, иначе данная подстановка отвергается.

Рассмотрим некоторые ситуации, при которых перечисленные выше предикаты можно использовать и получать новые свойства процесса поиска ЛВ.

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

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

Улучшение эффективности вывода. Рассмотрим простую задачу вычисления n-го элемента ряда Фибоначчи. На языке ПО-формул данная задача вычисления 10-го элемента ряда формализуется сле дующим образом:

n, x,y:f(n,x),f(n + 1,y) - :f(n + 2,x + y) :T-:f(1,1),f(2,1)- x : f(10,x)-:F, где в процессе поиска подстановки операция «+» из значений ее аргументов вычисляется в константу (целое число), данная константа используется в вместо операции «+»;

в консеквенте вопроса опера ция «+» заменяется на вычисленную константу во время применения подстановки.

А.А. Ларионов, Е.А. Черкашин, И.Н. Терехин. Системные предикаты для управления логическим выводом в систе ме автоматического доказательства теорем для исчисления позитивно-образованных формул В ходе ЛВ база постепенно наполнится фактами и станет возможным ответ на целевой вопрос. При обычном выводе с каждым ответом на первый вопрос в базу помещаются ответы, некоторые из которых будут дублироваться и как следствие могут производиться излишние вычисления. Вычисления ряда Фи боначчи подразумевают, что для вычисления последующего элемента достаточно использовать лишь два предыдущих элемента ряда. Это значит, что базу можно ограничить двумя последними добавлен ными элементами. Поскольку ответ на первый вопрос приводит к добавлению базы только одного ново го факта, базу можно ограничить с помощью ввода системного предиката, удаляющего один самый ста рый элемент базы. Первый вопрос ПО-формулы с системным предикатом будет выглядеть так:

n, x,y:f(n,x),f(n + 1,y) - :f(n + 2,x + y)'(n + 2),remFact(n), при этом запись '( L ) означает «пометить терм меткой L». Соответственно база данной ПО-формулы вы глядит так:

:f(1,1)'(1),f(2,2)'(2).

Удаление элементов из базы можно организовать без использования меток атомов, если использовать RemPatternFact:

n, x,y:f(n,x),f(n + 1,y) - :f(n + 2,x + y)'(n + 2),remPatternFact(f(n,_)).

Символ подчеркивания интерпретируется, как и в Прологе, в качестве анонимной переменной. Из ба зы будут удалены все факты, являющиеся основными примерами f (n, _). Нетрудно заметить, что такой подход эквивалентен предыдущему, однако не требует дополнительных меток атомов.

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

3. Программная система Реализация системных предикатов в программной системе АДТ обладает следующими особенностя ми. Во-первых, теперь имеется несколько типов предикатов: простой предикат, вычислимый предикат, предикат с побочным действием, соответственно появляется необходимость различать их, например, либо помечать каждый предикат его типом, либо хранить специальную таблицу символов, в которой для каждого имени предиката задан его тип и способ обработки. Во-вторых, необходимо учитывать, что вы числимый предикат не участвует в процедуре унификации, а его истинность влияет на всю истинность конъюнкта. В-третьих, предикаты с побочным действием могут глобально влиять на систему логическо го вывода, а значит, необходимо предусмотреть соответствующие средства влияния.

На рис. 1 представлена архитектура системы АДТ. Выделяются три основных модуля, используемых в программной системе: модуль доступа к ПО-формуле, модуль поиска ответных подстановок, модуль управления ЛВ.

Модуль доступа отвечает за эффективный доступ к различным частям ПО-формулы: фактам, вопро сам, ответным подстановкам и др. В данном модуле реализованы механизмы: эффективное извлечение термов (term retrieving), основанное на методиках индексирования термов (term indexing) [6], в частности выбраны метод индексирования путями (path indexing) и метод индексирования деревом подстановок (substitution tree indexing);

разделение общих данных для экономии памяти. Некоторые методы данного модуля реализованы в более ранних версиях программной системы АДТ для исчисления ПО-формул, в частности в [4, 5].

Модуль поиска ответных подстановок представляет собой отдельный поток (thread), независящий от стратегии ЛВ. Это значит, что для стратегии подразумевается, что все возможные подстановки для дан ного вопроса уже найдены, при этом сам процесс поиска подстановок может производиться независимо (например, на предназначенных для этого специализированных вычислительных узлах).

Модуль управления ЛВ получает сигналы от различных источников, например от системных преди катов. Каждому системному предикату соответствуют сигналы: set_next_question, rem_fact, rem_question, write, mark_fact, enable_question, disable_question, enable_fact, disable_fact, save, rollback, commit. Кроме того, предусмотрены сигналы, получаемые от внешних источников, например, от пользователя или дру гой программы: pause – приостановить вывод, start – возобновить вывод, stop – завершить вывод.

Системная информация содержит данные о текущем состоянии вывода: количество прошедшего времени с начала ЛВ, история опровержения баз, история выбора вопросов и ответов, информация о бу дущем (что выбирать далее), состояние памяти и др.

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ Рис. 1. Архитектура системы АДТ Данная архитектура позволяет вводить новые виды предикатов, а также иные способы влияния на ло гический вывод (например, непосредственное вмешательство пользователя) путем реализации обработ ки новых видов сигналов.

Заключение В работе рассмотрены вопросы использования так называемых системных предикатов с точки зрения применения их для управления логическим выводом (ЛВ). Такой подход особенно интересен в купе с положительными свойствами формализма ПО-формул, позволяющих снабжать логический вывод до полнительными стратегиями, зависящими от конкретной решаемой задачи. Приведены примеры классов стратегий, описываемых данным подходом, показаны стратегии для некоторых конкретных задач.

Реализация системы на основе использования многопоточности и передачи сигналов позволяет рас ширять набор системных предикатов независимо от основного кода программы АДТ, а также создавать иные способы управления ЛВ.

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

Литература 1. Братко И. Алгоритмы искусственного интеллекта на языке PROLOG. Вильямс, 2004. 640 с.

2. Васильев С.Н., Жерлов А.К., Федунов Е.А., Федосов Б.Е. Интеллектное управление динамическими систе мами. М.: Физматлит, 2000. 352 с.

3. Васильев С.Н., Жерлов А.К. Об исчислении типово-кванторных формул // Докл. РАН. 1995. Т.343, № 5. С.

583-585.

4. Давыдов А.В., Ларионов А.А., Черкашин Е.А. Об исчислении позитивно-образованных формул для автома тического доказательства теорем // Моделирование и анализ информационных систем. 2010. Т.17, №4. С.60-69.

5. Черкашин Е.А. Разделяемые структуры данных в системе автоматического доказательства теорем КВАНТ/3.

// Вычислительные технологии. 2008. Т. 13. С. 102-107.

6. Robinson A., Voronkov A. Handbook of Automated Reasoning. The MIT Press. 2001. 2081 p.

Ларионов Александр Александрович, аспирант кафедры информационных технологий Института математики, экономики и информатики Иркутского государственного университета, тел. (395-2) 242210, e-mail: alexan der@prisnif.org Черкашин Евгений Александрович, кандидат технических наук, зав. лаб. в Учреждении Российской академии наук Институте динамики систем и теории управления СО РАН, тел. (395-2) 513013, e-mail: eugeneai@icc.ru Терёхин Иван Николаевич, студент кафедры информационных технологий Института математики, экономики и информатики Иркутского государственного университета, тел. (395-2) 242210, e-mail: i.terhin@gmail.com Larionov Alexander Alexandrovich, postgraduate student at Information Technology department of Institute of Math ematic, Economics and Computer Science at Irkutsk State University.

Cherkashin Evgeny Alexandrovich, Ph.D in technical science, chief of a laboratory in Institute for Systems Dynamics and Control Theory at SB RAS.

Terehin Ivan Nikolaevich, student at Information Technology department of Institute of Mathematic, Economics and Computer Science at Irkutsk State University.

Л.М. Макшанова, М.С. Содномова. Алгоритм прогнозирования объектов локализуемого трафика в сети Бурятского филиала ОАО «Ростелеком»

УДК Л.М. Макшанова, М.С. Содномова АЛГОРИТМ ПРОГНОЗИРОВАНИЯ ОБЪЕКТОВ ЛОКАЛИЗУЕМОГО ТРАФИКА В СЕТИ БУРЯТСКОГО ФИЛИАЛА ОАО «РОСТЕЛЕКОМ»

В статье собраны и обработаны данные объемов внешнего и внутреннего трафика сети Бурятского филиала за три года, рассмотрены вопросы локализации трафика, найдены оптимальные методы прогнозирования трафика сети.

L.M. Makshanova, M.S. Sodnomova THE ALGORITHM OF FORECASTING OF THE OBJECTS OF LOCALIZED TRAFFIC IN THE NET OF THE BYRYAT BRUNCH OAO “ROSTELEKOM” In the article the data of the external and internal volume of the traffic in the net of the Buryat Brunch have been collected and processed for the period of three years, the issues of traffic localization have been considered, the optimal methods of forecasting net traffic have been found.

Key words: traffic, localization.

Уровень локализации трафика – это показатель, позволяющий дать оценку эффективности деятельности филиала при предоставлении качественной услуги. Мы не можем достигать заданный показатель локализации путем массовой деградации сервиса за счет перегрузок на магистральных каналах. Снизить возможный негативный эффект от допускаемых перегрузок, а в дальнейшем и нормализовать ситуацию на магистральных портах предстоит только за счет повышения уровня локализации трафика. А также локализация трафика является одной из эффективных мер экономии затрат на закупку внешнего трафика.

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

На рисунке 1 представлены графики, на которых видно, что трафик сети имеет выраженный сезонный характер с возрастающим трендом. Понятие “сезон” в прогнозировании применим к любым систематическим колебаниям, например, если речь идёт об изучении трафика в течение недели, то под термином “сезон” понимается один день. Кроме того, цикл колебаний может существенно отличаться (как в большую, так и в меньшую сторону) от величины один год. И если удаётся выявить величину цикла этих колебаний, то такой временной ряд можно использовать для прогнозирования с использованием аддитивных и мультипликативных моделей.

Аддитивную модель прогнозирования можно представить в виде формулы:

F = T + S + E, где: F – прогнозируемое значение;

Т – тренд;

S – сезонная компонента;

Е – ошибка прогноза.

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

F = T х S x E.

На практике отличить аддитивную модель от мультипликативной можно по величине сезонной вариации. Аддитивной модели присуща практически постоянная сезонная вариация, тогда как у мультипликативной она возрастает или убывает [3].

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

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ Исходные данные/ Объем трафика сети БФ 450 000, 400 000, Трафик 350 000, внешний 300 000, Трафик 250 000, внутрений 200 000, Трафик 150 000, Сибнет 100 000, 50 000, 0, 2008- 2008- 2008- 2009- 2009- 2009- 2009- 2010- 2010- 2010- 2010- 2011- Рис. 1. Объем трафика филиала за период 2008 - 2011гг.

На рисунке 1 наглядно иллюстрируется рост потребляемого абонентами трафика. Причинами роста являются увеличение абонентской базы (по сравнению с 2008 г. в 4,4 раза), ввод высокоскоростных тарифных планов, развитие контент-ресурсов.

При увеличении трафика абонентов перед провайдерами стоит вопрос о закупке внешнего Интернет трафика и обеспечения работоспособности оборудования. Одним из мер по изменению текущего процесса является локализация трафика, которая достигается путем развития и популяризации собственных контент-ресурсов, увеличения доли внутреннего трафика. Филиалом проводятся следующие мероприятия по повышению локализации трафика:

- развитие и продвижение собственного контента;

- ограничение внешней нагрузки (самой безболезненной мерой по ограничению внешней нагрузки является реализация ретрекера с кэшированием наиболее востребованного контента). По статистическим данным трех лет доля внутреннего трафика выросла от 6 до 70%.

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

На рисунке 2 представлены все линии тренда для локализованного филиалом трафика, в таблице указаны их вероятности достоверности.

Выбранные линии тренда для локализованного трафика 1 500 1 300 y = -0,0522x 6 + 5,7343x 5 - 237,02x 4 + 4536,5x 3 - 38977x 2 + 134622x - R2 = 0, 1 100 y = 1608,4e 0,2 1 18 x R = 0, 900 y = -8,9036x 3 + 1084,6x 2 - 2316,2x - R2 = 0, 700 y = 84,43x 2,58 2 R = 0, 500 y = 274537Ln(x) - R2 = 0, 300 000y = 26944x - R2 = 0, 100 -100 - - - - - - - - - - - - - - - - - - Линейная аппроксиммация Логарифмическая аппроксимация Степенная аппроксимация Экспоненциальная аппроксимация Полиноминальная аппроксимация 6 степени Полиномиальная аппроксимация 3 степени Рис. 2. Выбранные линии тренда для прогнозирования локализованного трафика Таблица Методы аппроксимации и их вероятности достоверности Методы Линейная Полиномиальная Логарифми Экспо Степен аппрокси ческая ненци ная 3-й 6-й мации альная степени степени Вероятность достоверности 0,923 0,9619 0,9796 0,6464 0,8257 0, R Л.М. Макшанова, М.С. Содномова. Алгоритм прогнозирования объектов локализуемого трафика в сети Бурятского филиала ОАО «Ростелеком»

Для простоты и большей наглядности данного примера ограничимся выбором трех линий тренда:

полиномиальная аппроксимация 3-й и 6-й степени, а также линейная, так как эти тренды имеют высокую вероятность достоверности (рис. 3).

Выбранные методы аппроксимации 08 08 08 08 09 09 09 09 09 09 00 00 00 00 00 00 01 01 2 0 - 2 0 - 2 0 - 2 0 - 2 0 - 2 0 - 2 0 - 2 0 - 2 0 - 2 0 - 2 1 - 2 1 - 2 1 - 2 1 - 2 1 - 2 1 - 2 1 - 2 1 - - - оды аппроксимации полином 3ст Мет Локализованный т рафик, Гб оды аппроксимации полином 6ст Мет Мет ы аппроксимации линейный од Рис. 3. Выбранные методы аппроксимации Рассчитываем сезонную компоненту для каждого из уравнений тренда. Из фактических данных вычитаем значения линий тренда для каждого из сезонов. В расчетах для того, чтобы довести средние колебания до 0, необходимо итоговую сумму средних разделить на количество периодов в сезоне (в нашем случае – это 12). Полученный результат вычитаем из значений среднего по каждому периоду. В итоге сумма колебаний составит абсолютный 0.

Отклонения сезонных колебаний модели с линейным и полиномиальным трендом 3 и 6 степени от весьма велико и утверждать, что в моделях выявлена сезонность, мы не можем. Но, исходя из экономических соображений и знаний специфики рынка ТКС услуг, предполагаем, что сезонность существует. Соответственно, ошибка модели вырастет. Рассчитанные сезонные компоненты для каждого из уравнений тренда при прогнозировании просто переносятся на соответствующие месяцы прогнозного периода.

Значения трендовых моделей с учетом сезонной компоненты (T+S) 2008- 2008- 2008- 2008- 2009- 2009- 2009- 2009- 2009- 2009- 2010- 2010- 2010- 2010- 2010- 2010- 2011- 2011- - Полиномиальная модель 6ст (S+T). Полиномиальная модель 3 ст (S+T).

Линейная модель (S+T) Рис. 4. Значения трендовых моделей с учетом сезонной компоненты Получив 3 сезонные компоненты (S) с 3 уравнениями тренда (T), мы можем рассчитать ошибки построенных моделей (E). Для этого из исходных значений задачи необходимо отнять сумму S+T, E=F (S+T).

Ошибки моделей (Е) - - - - - - - - - - - - - - - - - - - - - Ошибка полиномиальной мод ели 6 ст Е=А-(S+T).

Ошибка полиномиальной мод ели 3 ст E=F-(S+T).

Ошибка линейной мод ели E=F-(S+T) Рис. 5. Ошибки построенных моделей (Е) На основании рассчитанных ошибок рассчитаем среднеквадратическое отклонение (СКО) для каждого из периодов, СКО моделей, а также их точность (табл. 2).

Находим среднеквадратическую ошибку модели (Е) по формуле:

Е= О2 : (F-(T+S))2, где:

Т – трендовое значение;

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ S – сезонная компонента;

О – отклонения модели от фактических значений.

На основании СКО для периодов рассчитаем точность по формуле:

(точность модели) = [1- (среднее значение СКО)]*100%.

Среднеквадратичное отклонение модели от фактической СКО полиномиальной аппроксимации 6 ст СКО полиномиальной аппроксимации 3 ст СКО линейной аппроксимации Рис. 6. Среднеквадратичное отклонение Таблица Рассчитанные значения ошибок моделей Полиномиальная Полиномиальная Линейная аппроксимация аппроксимация аппроксимация 6-й степ. 3-й степ.

0,5085 0,3314 0, Среднее значение 49,15% 66,86% 69, Точность модели Среднеквадратичная 0,397% 1,369% 6,099% ошибка модели (Е) На основе полученных значений (табл. 2), а также значений вероятности достоверности (табл. 1) оптимальной моделью является полиномиальная аппроксимация 3-й степени. Данная модель отражает тенденции объемов локализованного трафика и может использоваться для прогнозов. Чтобы построить доверительный интервал, воспользуемся данными СКО для модели с полиномиальным трендом 3-й степени (СКО=0,33144). Доверительный интервал примет вид:

(F*[1-СКО];

F*[1+СКО]).

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

Таблица Расчет прогнозных значений модели с полиномиальным трендом 3-й степени Доверительный интервал Прогнозируемые значения объема Месяц локализованного трафика + 2011-05 622060,9877 1238840,911 956 067, 2011-06 658076,1536 1310565,487 973 805, 2011-07 677536,7788 1349321,524 985 168, 2011-08 705378,5331 1404768,667 1 007 729, 2011-09 733241,9059 1460258,863 1 043 789, 2011-10 761091,1818 1515720,985 1 115 461, 2011-11 788890,6452 1571083,904 1 179 992, 2011-12 816604,5807 1626276,495 1 233 200, 2012-01 844197,2728 1681227,627 1 338 717, 2012-02 871633,0061 1735866,175 1 317 667, 2012-03 898876,0651 1790121,009 1 392 831, 2012-04 925890,7343 1843921,003 1 371 293, Л.М. Макшанова, М.С. Содномова. Алгоритм прогнозирования объектов локализуемого трафика в сети Бурятского филиала ОАО «Ростелеком»

Прогнозируемые значе ния объема локализованного трафика 1 600 000, 1 400 000, 1 200 000, 1 000 000, 800 000, 600 000, 400 000, 200 000, 0, 2011- 2011- 2011- 2011- 2011- 2011- 2011- 2011- 2012- 2012- 2012- 2012- Прогнозируемые значения объема локализов анного трафика Рис. 3. Прогноз локализованного трафика на 1 год Таким образом, мы пришли к выводу, что:

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

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

в рассмотренном примере предпочтительна полиномиальная аппроксимация 3-й степени (исходя из рассчитанных значений СКО, R2, ошибок моделей).

по данным прогнозных значений ожидается рост объемов локализованного трафика. Причинами которого являются рост абонентской базы, рост объемов контента (видео, игры, и т.п.);

Для обеспечения данных показателей необходимы:

организация высокоскоростной раздачи файлов внутри сети;

размещение серверов, кэширование на собственных хранилищах торрент трекеров;

организация пиринговых включений;

маркетинговые мероприятия.

Литература Каграманзаде А.Г. Менеджемент и регулирование в Инфокоммуникациях. Баку: Элм, 2006.

1.

Соколов Н.А. Телекоммуникационные сети. М.: Альварес Паблишинг, 2004. Ч. 4.

2.

3. URL: http://www.cfin.ru/finanalysis/sales_forecast.shtml 4. URL: http://www.cfin.ru/finanalysis/math/add_to_kosh.shtml Макшанова Лариса Михайловна, начальник отдела по работе с операторами связи БФ ОАО "Ростелеком", тел.

(3012) Содномова Марина Станиславовна, аспирант Сибирского государственного университета телекоммуникаций и информатики.

Makshanova Larisa Mikhailovna, head of the department on work with operators of communication BB OAO “Rostelekom”, ph.(3012) Sodnomova Marina Stanislavovna, postgraduate student, Siberian State University of Telecommunication and Computer Science ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ УДК Б.С. Малакшинов, С.Д. Данилова ПРИМЕНЕНИЕ МЕТОДА САМОМОДИФИЦИРУЮЩЕГОСЯ КОДА К АВТОМАТИЧЕСКОМУ ПОСТРОЕНИЮ ПРОГРАММНОГО КОДА В ОНТОЛОГИИ С АКТИВНОЙ СЕМАНТИКОЙ Статья посвящена подходу к реализации технологии всепроникающих вычислений. Особенностью подхода является применение метапрограммирования в реализации онтологий с активной семантикой. Обосновываются возможность и необходимость использования самомодифицирующегося кода при реализации.

Ключевые слова: онтология, активная семантика, всепроникающие вычисления, метапрограммирование, самомодифицирующийся код.

B.S. Malakshinov, S.D. Danilova AUTOMATIC CODE GENERATION USING SELF-MODIFYING CODE IN ONTOLOGIES WITH ACTIVE SEMANTICS This article is devoted to the method of ubiquitous computing embodiment. The specific feature of this method is the use of metaprogramming in creation ontology with active semantics. The article justifies the possibility and need of use self-modify code in embedding.

Keywords: ontology, active semantics, ubiquitous computing, metaprogramming, self-modify code.

Введение Развитие ИТ-индустрии требует поиска новых подходов к реализации технологии всепроникающих вычислений. Была выдвинута идея реализации, основанная на применении онтологии с активной семантикой [1]. Для того чтобы знания человечества были понятны компьютерам, был создан язык XML, который является сводом синтаксических правил. Для того чтобы информация в онтологии стала для компьютера руководством к действию, необходимо в онтологии иметь программные коды, сопоставимые статьям онтологии. Тем самым онтология с активной семантикой представляет собой онтологию, в которой понятия могут быть объектами с набором свойств, над этими объектами можно производить действия или они сами могут быть инициаторами действий.

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


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

Самомодифицирующийся код реализуется двумя основными методами:

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

2) интерпретация произвольного кода, представленного в виде строки.

Языки программирования, поддерживающие метапрограммирование Основными языками программирования, поддерживающими метапрограммирова-ние, являются Perl, Ruby, Forth и Lisp. Все они поддерживают самомодифицирующийся код.

В Perl существует понятие «source filters» («фильтров исходного кода») – метод переработки файлов с исходным кодом перед выполнением, позволяющий полностью менять синтаксис и семантику языка.

Одним из известных примеров является модуль Lingua::Romana::Perligata, позволяющий писать код Perl на латыни [3].

Б.С. Малакшинов, С.Д. Данилова. Применение метода самомодифицирующегося кода к автоматическому построению программного кода в онтологии с активной семантикой В Forth программисту предоставляют встроенные в язык возможности по изменению своего синтаксиса и семантики. Это достигается определением архитектуры виртуальной машины и полного доступа к возможностям изменения её составляющих.

Пример программы, использующей самомодифицирующийся код по методу интерпретации произвольного кода на языке Perl:

do { print("\n ");

chop($_ = );

eval($_);

warn() if $@;

} while ($_ ne "exit");

Этот короткий код позволяет выполнять программы «на лету». Как видно из кода, в программе всего одна переменна «$_». Разберем пример, введем в порядке очереди команды:

1. $pi = 3.141592654 – создаем переменную Pi;

2. $n = sin($pi/2) – создаем переменную, равную синусу 90 градусов;

3. $m = $n + 3 – создаем еще одну переменную, значение которой зависит от предыдущей переменной;

4. print $m – печать текущего значения переменной «m».

На экран выведется значение переменной «m» = 4. Даже несмотря на то, что переменная в исходной программе всего одна, введенные новые строки кода во время выполнения самой программы позволили нам создать еще 3 переменные, которые хранят значения и ими можно полноценно оперировать.

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

Такую реализацию можно осуществить следующими основными способами:

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

• программное хранение данных – в хранении откомпилированных исполняемых файлов для элемента онтологии «действие»;

• автоматно-объектная архитектура – в эмуляции одного большого автомата на основе файла онтологии. В этом способе субъект создается с заданными параметрами и подается на вход автомата;

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

• метапрограммирование на основе самомодифицирующегося кода заключается в хранении программного кода интерпретируемого языка программирования на каждую статью онтологии.

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

• из-за незначительного изменения в модуле придется обновлять его полностью, учитывая объем обхвата знаний одного модуля – это будет большой объем данных;

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

Вторая модель решает проблемы первой модели. Минусы второй модели:

• большой объем для хранения файлов онтологии;

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

Модель автоматно-объектной архитектуры имеет много плюсов, такие как обработка нескольких задач сразу, полное видение онтологии, каркас всевозможных исходов, но есть и существенные минусы:

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ для построения действующего автомата необходимо наличие всей онтологии, ресурсоемкое моделирование системы автоматов.

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

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

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

к действию – функция или метод объекта;

к состоянию и свойству – атрибут к описанию объекта;

к событию – обработчик;

к величине – описание типа.

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

1) оператор обращения к онтологии;

2) оператор выполнения – любой другой оператор программного кода.

Алгоритм работы будет следующим:

1. Пользователь ставит задачу перед системой.

2. Оператор обращения ищет необходимую статью.

3. В зависимости от результата поиска:

a) cтатья не найдена – извещение об ошибке, перейти к 1;

b) cтатья найдена – добавление кода из онтологии в выполняемый программный код, перейти к 4.

4. Выполнение следующего оператора:

a) если оператор обращения к онтологии – перейти к 2;

b) если оператор выполнения – выполнение оператора, перейти к 4;

c) если следующего оператора нет – перейти к 1.

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

Возможность существования модели благодаря интерпретируемым языкам включает в себя и минусы интерпретируемых языков – медленная скорость выполнения. На простых задачах разница в скорости не будет существенна, но, к примеру, при итерациях в 10-100 тысяч проходов падения скорости будут довольно существенны – 10-100 раз.

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

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


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

Литература 1. Найханова Л.В., Данилова С.Д. Об онтологии с активной семантикой и ее возможности в технологии всепроникающих вычислений // Информатизация образования и науки. 2010, №2(6). С. 120-136.

2. URL: http://ru.wikipedia.org/wiki/Метапрограммирование.

3. Описание Lingua::Romana::Perligata. URL: http://search.cpan.org/~dconway/Lingua-Romana-Perligata-0.50/ Малакшинов Баир Сергеевич, аспирант кафедры систем информатики ГОУ ВПО ВСГТУ. 670013, Российская Федерация, г. Улан-Удэ, ул. Жердева, 31. Тел.: (3012) 64-44-14, e-mail: bairkoo@gmail.com Данилова Соелма Доржигушаевна, кандидат технических наук, доцент кафедры систем информатики ГОУ ВПО ВСГТУ. 670047, Российская Федерация, г. Улан-Удэ, ул. Павлова, 70-23. Тел.: 89833321026, e-mail:

dsoelma@mail.ru Malakshinov Bair Sergeevich, postgraduate student of East Siberian State University of Technology, 670013, Russian Federation, Ulan-Ude, 31 Zherdev’s st. Tel.No.: (3012) 64-44-14.

Danilova Soelma Dorzhigushaevna, PhD, Associate Prof. of East Siberian State University of Technology. 670047, Russian Federation, Ulan-Ude, 70-23 Pavlov’s st. Tel.No.: 89833321026.

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ УДК 517. Г.А. Матвеев, Е.А. Трушкова МОДЕЛЬ ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В статье описана математическая модель и метод динамического распределения ограниченных ресурсов для системы компьютерных приложений в совокупности, который учитывает потребности и приоритеты каждого из приложений при изменяющейся пользовательской нагрузке на них. Модель построена с использованием матема тической теории оптимального управления, при этом в качестве управления рассматривается количество ресурсов, выделяемых каждому компьютерному приложению.

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

G.A. Matveev, E.A. Trushkova MODEL OF DYNAMIC RESOURCE SHARING This article describes a mathematical model and method of resource sharing to the system of computer applications.

Method takes into account the needs and priorities of each application under the influence of changing user load on applica tions. The model was constructed using the mathematical theory of optimal control. As control is considered the amount of resources allocated to each application.

Keywords: resource sharing, the system computer applications, optimal control.

Введение Рассматривается задача автоматического управления ограниченными аппаратными ресурсами c уче том ценности выделенных компьютерному приложению ресурсов (например, количества виртуальных машин, обеспечивающих работу приложения;

объёма оперативной памяти и процессорного времени, предоставляемых виртуальным машинам или отдельным процессам) при текущей пользовательской на грузке [1, 2]. Это позволит оптимально использовать ресурсы в процессе эксплуатации системы прило жений, а именно, динамически добавлять или убирать количество любого ресурса во время работы с учетом потребностей и приоритетов каждого приложения системы и изменения пользовательской на грузки на каждое приложение.

1. Постановка задачи Построим математическую модель рассматриваемой задачи для системы, состоящей из n приложе ний, использующих один первичный ресурс и m различных категорий вторичных (зависимых от пер вичного) ресурсов.

Пусть vi (t ), i = 1,…, n – количество первичного ресурса, обеспечивающего работу приложения i, в момент времени t. Обозначим через r ij (t ), i = 1,…, n, j = 1,…, m – количество ресурса j, выделенного приложению i в момент времени t. Ограничения на использование ресурсов записываются в виде:

v(t ) V (t ), r i (t ) R i ( t, v i (t ) ), i = 1,…, n, (1) где V (t ), R i (t, v i ) – некоторые компактные множества.

Предполагается, что каждое компьютерное приложение имеет индивидуальный набор k i характери стик, которые однозначно описывают его текущее состояние с точки зрения пользователя (например, время отклика приложения, количество сетевых ошибок). Характеристика зависит от количества пер вичного ресурса, обеспечивающего работу приложения, объема вторичных ресурсов, предоставленных приложению и оказываемой на приложение с течением времени неуправляемой пользовательской на грузки Li (t ), i = 1,…, n. При этом характеристики могут быть составлены либо на испытательном стенде до запуска приложения в эксплуатацию, либо непосредственно в процессе работы приложения – в таб личном виде. Обозначим через p ik = p ik (v i (t ), r i1 (t ), r i 2 (t ),…, r im (t ), Li (t )), i = 1,…, n, k = 1,…, k i – характе ристику k приложения i, через p ik (t ) – целевой уровень соответствующей характеристики (желаемое Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 09 01-170).

Г.А. Матвеев, Е.А. Трушкова. Модель динамического распределения ресурсов значение характеристики, ниже которого она не должна опускаться во время эксплуатации компьютер ного приложения). С помощью функций ki i (t ) = ik p ik ( v i (t ), r i1 (t ),…, r im (t ), Li (t ) ) (2) k = можно получить некоторую суммарную оценку характеристик каждого из приложений в момент време ни t. Здесь через ik обозначены весовые коэффициенты, выбираемые согласно значимости каждой ха рактеристики приложения. Будем называть функции i (t ) уровнями сервиса приложений.

Задача состоит в поддержании значения уровня сервиса (2) не ниже некоторого целевого уровня (поддержание каждой характеристики не ниже ее целевого уровня) в моменты времени T = {t0, t0 + h,…, t0 + qh = t1}. Данная задача равносильна минимизации отклонения уровня сервиса ki q = ik max 0, p ik (t0 + th) p ik ( v i (t0 + th), r i1 (t0 + th),…, r im (t0 + th), Li (t0 + th) ) { } i k =1 t = для системы приложений в совокупности с учетом приоритета каждого из приложений. Обозначим че рез i + максимум i при всех допустимых значениях ресурсов (минимум i, очевидно, равен нулю).

Замечание. Для задачи поддержания характеристики не выше ее целевого уровня на T отклонение можно записать в виде q max {0, p } (t0 + th) + p ik ( v i (t0 + th), r i1 (t0 + th),…, r im (t0 + th), Li (t0 + th) ) ;

ik t = для задачи поддержания положительной характеристики как можно ближе к нулю на T отклонение можно записать так:

q p ( v (t + th), r i1 (t0 + th),…, r im (t0 + th), Li (t0 + th) ).

ik i t = Тогда исходную задачу динамического распределения ресурсов можно поставить в виде дискретной задачи оптимального управления следующего вида:

ki y (t + h) = y (t ) + ik max 0, p ik (t ) p ik ( v i (t ), r i1 (t ),…, r im (t ), Li (t ) ), { } i i k = y i (t0 ) = 0, i = 1,…, n, t T = [t0, t1 ], (3) v(t ) V (t ), r i (t ) R i ( t, vi (t ) ), i = 1,…, n, y i (t1 ) n F ( y (t1 )) = i min, i+ i = i где y (t ) – сумма отклонений уровня сервиса приложения i к моменту времени t (т. е. в моменты времени t0, t0 + h,…, t ), через i обозначены весовые коэффициенты, выбираемые согласно приоритету каждого компьютерного приложения (большее значение весового коэффициента соответствует более v i (t ), высокому приоритету соответствующего приложения). Здесь роль управлений играют функции r ij (t ), i = 1,…, n, j = 1,…, m.

Рассмотрим один из самых подходящих для дальнейшей практической реализации вариантов постав ленной задачи (3), а именно, предположим, что на рассматриваемом промежутке времени управления постоянны, т. е. vi (t ) = v i, r ij (t ) = r ij, i = 1,…, n, j = 1,…, m. Тогда исходная задача может быть сформу лирована в виде последовательности задач поиска минимума функции n (m + 1) переменных F ( y (t1s ) ) = G (vsi, rsij ) при условиях (1), т.е.

F ( y (t1s ) ) = G (vsi, rsij ) min, v(t ) V (t ), r i (t ) R i ( t, vi (t ) ), i = 1,…, n, v,r на множестве конечных временных отрезков T 0 = [t00, t10 ], где t10 = t00 + q 0 h 0, T 1 = [t01, t11 ], где t11 = t01 + q1h1 и т. д.

Спецификой рассматриваемой задачи является зависимость вида динамической системы (3) от неиз вестных функций Li (t ), i = 1,…, n. При этом предполагается, что известны значения этих функций в неко торые предшествующие рассматриваемому отрезку времени моменты t0 s l s h s, t0 s (l s 1)h s, …, ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ t0 s h s. Этот факт позволяет осуществлять прогноз изменения функций Li (t ) на рассматриваемом от резке времени (например, с помощью численных методов аппроксимации функций одной переменной).

Полученное таким образом управление (количество выделяемых ресурсов) будет носить кусочно постоянный характер:

vi (t ) = vs, r ij (t ) = rsij, t T s = [t0 s, t1s ], s = 0,1,.., i что позволит легко реализовать его на практике в процессе эксплуатации системы приложений или ис пользовать его в качестве начального управления в некоторой итерационной процедуре улучшения управления.

2. Алгоритм решения задачи (на примере двух компьютерных приложений) Рассмотрим алгоритм решения задачи динамического управления ресурсами на примере системы двух приложений – картографического сервиса «MapServer» и вычислительного сервиса «X-Com» [1].

Ресурсы, предоставленные приложениям: vi (t ) – количество виртуальных машин (ВМ), обеспечи вающих работу приложения, r i1 – оперативная память ВМ (RAM, Мбайт), r i 2 – доля физического про цессора, предоставляемая ВМ (CAP, %). Ограничения на предоставление ресурсов записываются в виде:

n vi (t ) 1, n vi (t ) v +, r j vi (t ) r ij (t ) r j + vi (t ), i = n r (t ) r j + v +, r j r ij (t ) r j + v + ( n 1) r j, i = 1,…, n, j = 1,…, m, ij i = где n = 2, m = 2, r = 128, r1+ = 512, r 2 = 10, r 2 + = 100, v + = 3.

Для построения уровня сервиса первого приложения на дискретном наборе моментов времени {5,6,7,8,9} используются функции p11 (v1, r11, r12, L1 ) – среднее время отклика приложения, p12 (v1, r11, r12, L1 ) – процент сетевых ошибок и L1 (t ) – пользовательская нагрузка на приложение, а также p11 = 3000 p11 (v1, r11, r12, L1 ) величина желаемого времени отклика миллисекунд. Функции и 12 1 11 12 1 p (v, r, r, L ) заданы таблично своим профилем производительности, функция L (t ) – значениями в моменты времени {0,1, 2,3, 4}. По этим данным были построены аппроксимации функциями p11, p12, L 1 по МНК в виде 70 p1k (v1, r11, r12, L1 ) = max 0, aki (v1 )(r11 ) sk 1i (r12 ) sk 2 i ( L1 ) sk 3 i, i =1 где aki – найденные согласно МНК постоянные действительные числа, а целые показатели степеней skli удовлетворяют условиям 2 skli 2, 1 skli 2 ;

l = L (t ) = b0 ( L (0),…, L1 (4) ) + b1 ( L1 (0),…, L1 (4) ) t, 1 где b0, b1 – найденные согласно МНК постоянные действительные числа.

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

4 1 = max 0, p11 + p11 ( v1, r11, r12, L1 (5 + t ) ) + p12 ( v1, r11, r12, L1 (5 + t ) ).

{ } t =0 t = Можно подсчитать и максимальное отклонение уровня сервиса 1+ = 15070.

Для построения уровня сервиса второго приложения используется функция p 21 (v 2, r 21, r 22 ) – скорость расчета задач, находящихся в очереди, а также момент желаемого окончания расчетов и величина на чальной желаемой скорости расчета задач p 21 (0) = 18 задач/сек, что позволяет рассчитать текущую же 21 лаемую скорость расчета задач p (5) = p (0)( 5) задач/сек.

Функция p 21 (v 2, r 21, r 22 ) задана таблично своим профилем производительности. По этим данным бы ла построена аппроксимация функцией p 21 в виде p 21 (v 2, r 21, r 22 ) = 0.92451 0.00024r 21 + 0.09777 r 22 0.345475v 2 + 0.0002r 21v 2.

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

Г.А. Матвеев, Е.А. Трушкова. Модель динамического распределения ресурсов 2 = max 0, p 21 (5) p 21 ( v 2 (5), r 21 (5), r 22 (5) ).

{ } t = Можно подсчитать и максимальное отклонение уровня сервиса 2+ = 90.

С учетом вышеизложенного, функцию G (v i, r ij ) запишем в виде:

i ( v i, r i1, r i 2 ) G ( v1, v 2, r11, r12, r 21, r 22 ) = i min, (4) i+ i = где 1 = 2 = 1 (это означает равные приоритеты обоих приложений).

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

Ниже приводится пошаговое описание работы программы.

Шаг 1. Полагается s = 1, t0 s = 5 мин.

Шаг 2. Снимаются показания пользовательской нагрузки L1 (t ) в моменты t0 s 5, t0 s 4, t0 s 3, t0 s 2, t0 s 1. Производится расчет прогноза изменения пользовательской нагрузки по МНК в виде L 1 (t ) = b0 + b1 t.

Шаг 3. Решается задача условной минимизации (4) G ( v*, r * ) = min G ( v1, v 2, r11, r12, r 21, r 22 ), ( v, r )W v 1, 2 v1 + v 2 v +, r j r ij (t ) r j + v + r j, i W = (v, r ) 1 j j+ + j i j+ i 2j ij r + r r v, r v (t ) r (t ) r v (t ), i, j = 1, методом покоординатного спуска с постоянным шагом, в качестве начального приближения выбирается случайным образом набор точек в допустимой области.

Шаг 4. Перераспределяются ресурсы приложениям согласно найденным значениям ресурсов ( v*, r * ).

Пересчитывается целевой уровень второго приложения по формуле 21 21 2* 21* 22* p (t0 s )( t0 s ) 5 p (v, r, r ) p 21 =. Полагается s = s + 1, t0 s = t0 s + 5. Осуществляется переход к ша t0 s гу 2.

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

Рис. + Результаты работы программы при v = 3 (не более трех ВМ на оба приложения в сумме) и увеличи вающемся приоритете второго приложения (в зависимости от роста целевого уровня сервиса – желаемой скорости расчета задач) для каждого из вариантов прогноза представлены на рис. 2, 3 (рис. 2 соответст вует первому варианту пользовательской нагрузки, рис. 3 – второму). Изменяющийся во времени целе вой уровень второго приложения имеет смысл ограниченного конечного времени расчета. Из рисунков ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ видно, что при различных пользовательских нагрузках алгоритм дает устойчиво хорошее динамическое перераспределение ресурсов с учетом поддержания изменяющихся характеристик на целевом уровне.

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

Литература 1. Московский А.А., Первин А.Ю., Walker B. Оптимальное управление ресурсами виртуальных инструментов на вычислительном кластере // Параллельные вычисления и задачи управления: тр. IV Междунар. конф. / ИПУ им.

В.А. Трапезникова РАН. – Москва, 2008. – С. 968-978.

2. Матвеев Г.А., Первин А.Ю., Трушкова Е.А. Динамическое распределение ресурсов для приложений // Ма териалы XVI междунар. конф. по вычислительной механике и современным прикладным программным системам.

– М.: Изд-во МАИ-ПРИНТ, 2009. – С. 528-531.

Рис. Г.А. Матвеев, Е.А. Трушкова. Модель динамического распределения ресурсов Рис. Матвеев Герман Анатольевич, ведущий инженер-исследователь Исследовательского центра мультипроцессор ных систем Института программных систем им. А.К. Айламазяна РАН, тел. (48535) 98095, e-mail: gera@prime.botik.ru Трушкова Екатерина Александровна, кандидат физико-математических наук, старший научный сотрудник Ис следовательского центра системного анализа Института программных систем им. А.К. Айламазяна РАН, тел.

(48535) 98094, e-mail: katerina@trushkova.pereslavl.ru Matveev German Anatolievich, Leading research engineer, Research Center for Multiprocessor Systems (RCMS), The Ailamazyan Program Systems Institute of RAS.

Trushkova Ekaterina Aleksandrovna, Candidate of Physics and Mathematics, Senior Researcher, System Analysis Re search Center (SARC), The Ailamazyan Program Systems Institute of RAS.

ВЕСТНИК БУРЯТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011/ УДК 517. А.Д. Мижидон, М.Б. Имыхелова ПРЕДЕЛЬНЫЕ ВОЗМОЖНОСТИ В ЗАДАЧЕ АКТИВНОЙ ВИБРОЗАЩИТЫ В статье рассматривается задача о предельных возможностях активной виброзащиты. Для ее решения развивается методика аналитического конструирования оптимального регулятора на случай функционалов с подынтегральной функцией вида xQx + xPu + u Ru.

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

A.D. Mizhidon, M.B. Imykhelova LIMITING POSSIBILITIES IN THE PROBLEM OF ACTIVE VIBROPROTECTION The paper deals with the problem of limiting capabilities of active vibroprotection. For the solution of the problem procedure of analytical constructing of an optimal controller is developed on a case of functionals with integrand of the form xQx + xPu + u Ru.

Keywords: limiting capabilities, optimal control, analytical designing, optimal controller, matrix equation by Rikkati.

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

1. Постановка задачи Рассмотрим механическую систему, представляющую собой твердое тело (объект защиты), соединенное с жестким недеформируемым основанием упруго-демпфирующими подвесами (УДП).

Источником кинематических возмущений является пространственное колебание основания. Для улучшения качества виброзащиты помимо пассивных УДП система виброзащиты содержит N активных элементов, формирующие силы U1 (t ),U 2 (t ),...,U N (t ), прикладываемые в некоторых N точках объекта защиты [1].

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

Считаем, что неподвижные оси координат совпадают в положении равновесия с подвижными осями.

При этих предположениях уравнения движения объекта защиты можно записать в виде Aq + Bq + Cq = A (t ) + DU (t ), (1) где q – 6-мерный вектор обобщенных координат, характеризующий относительные смещения тела;

(t ) – 6-мерный вектор возмущений (вектор обобщенных ускорений координат, описывающий движение основания);

A – 66-диагональная матрица моментов инерции тела;

B – 66-матрица коэффициентов демпфирования;

C – 66-матрица коэффициентов жесткостей;

D – 6 N -матрица, зависящая от точек приложения и направления действия управляющих сил;

U (t ) – N -мерный вектор управляющих сил (управление).



Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 9 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.