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

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

«ISSN 2306-1561 №4.2(7) Автоматизация и управление в технических системах Научно-методический сборник трудов кафедры «Автоматизированные ...»

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

Ситуационное управление целесообразно только применительно к объектам с неопределенной или недостаточно изученной структурой и набором свойств, таким объектам и процессам, для которых можно единожды создать и в дальнейшем ~ 114 ~ наращивать некоторую базу знаний – решений, принимаемых в той или иной конкретной ситуации.

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

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

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

Полная ситуация S дает представление о том, как из текущей ситуации S1 с помощью доступных механизмов (способов воздействия на объект управления) U перейти к ситуации S2. Таким образом, полную ситуацию можно представить элементарным соотношением:

S : S1 U S 2.

Такое правило преобразования носит название логико-трансформационного или корреляционного правила.

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

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

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

В действительности ДСС рассматривается как определённый сценарий: вершинам соответствуют факты, а дугам – связи. Связи могут служить отношением типа: причина – следствие, часть – подчасть, цель – подцель и т. п. В таком контексте ДСС больше относится к классу экспертных систем, чем способу представления развития ситуации – это скорее набор правил, база знаний, чем описания типа «ситуация – переход – ~ 115 ~ ситуация». К однотипным ситуациям могут быть применены несколько альтернативных решений. Иными словами, текущая ситуация порождает несколько полных ситуаций, каждый экземпляр которой определяет одно одношаговое решение.

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

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

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

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

Иными словами, имеет место двухуровневая классификация:

классификация текущих ситуаций;

классификация полных ситуаций (возможных решений в контексте текущей ситуации).

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

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

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

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

При таком подходе принципиальное значение имеют следующие понятия (рисунок 2):

обстановка – это все внутренние и внешние явления, которые нельзя отнести к управлению;

~ 116 ~ событие – любое изменение обстановки. Изменение обстановки предполагает переход от одного ее класса к другому. Определяющим фактором такого изменения является необходимость принятия решения. Так, если при переходе обстановки от А к B или обратно требуется принимать решение о дальнейшем управлении, то А и В относятся к различным классам обстановок. Событие можно позиционировать как процесс принятия решения;

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

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

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

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

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

~ 117 ~ В рамках уфимской школы ситуационного управления предложена несколько иная трактовка понятия ситуации [5 - 8]. Специфика данного подхода состоит в рассмотрении ситуации на двух уровнях:

на макроуровне: данная конкретная ситуация рассматривается не обособленно, а в ряду всех возможных ситуаций;

на микроуровне: ситуация рассматривается автономно, с точки зрения ее «инфраструктуры», внутренней сущности.

Пусть известна динамическая система, заданная в общепринятой форме «вход состояние-выход». В ней рассматривается совокупность текущих характеристик, представленная элементами: текущий момент времени;

текущее состояние;

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

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

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

Иными словами, при наличии некоторого фиксированного момента времени рассмотрение ситуации возможно в двух аспектах – ситуация до наступления заданного момента времени и ситуация после него.

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

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

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

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

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

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

Список информационных источников Ильясов Б. Г., Миронов В. В., Юсупова Н. И. Модели критических ситуаций при [1] управлении техническими объектами: Препринт. Уфа: УНЦ РАН, 1996.

Клыков Ю. И. Ситуационное управление большими системами. М.: Энергия, 1974.

[2] Поспелов Д. А. Ситуационное управление. Теория и практика. М. Наука, 1986. [3] с.

Коренев Г. В. Цель и приспособляемость движения. М.: Наука, 1974.

[4] Ильясов Б. Г., Миронов В. В., Юсупова Н. И. Модели предупреждения критических [5] режимов управляемых объектов в условиях неопределенности: Препринт. Уфа:

УНЦ РАН, 1994.

Ильясов Б. Г., Миронов В. В., Юсупова Н. И. Модели критических ситуаций при [6] управлении техническими объектами: Препринт. Уфа: УНЦ РАН, 1996.

Миронов В.В., Юсупова Н.И., Шакирова Г.Р. Ситуационно-ориентированные базы [7] данных: концепция, архитектура, xml-реализация // Вестник УГАТУ. Серия «Управление, вычислительная техника и информатика». 2010. T. 14, № 2. С. 233– 244.

Юсупова Н. И. Критические ситуации и принятие решений при управлении в [8] условиях помех. Уфа: Гилем, 1997.

Куликов Г.Г., Конев К.А., Суворова В.А. Теория систем и системный анализ: учеб.

[9] пособие. Уфа: УГАТУ, 2012. 159 с.

~ 119 ~ РАЗДЕЛ V. ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ, СИСТЕМЫ, КОМПЛЕКСЫ И КОМПЬЮТЕРНЫЕ СЕТИ DOI: 10.12731/2306-1561-2013-4- MULTI-CHANNEL CUSTOMER COMMUNICATION SPECIALIZED ITEM PROGRAMMABLE ITEM SPECIALIZED SERVICE CONNECTION Matyukhina E.N., Chistyakova M.A.

Abstract Discusses the construction of hardware and software for customer point of contact for special purposes, the operator node interaction dialog box in the mode of sending and receiving messages, direct two-way negotiations. Describes the functionality of the site, its hardware and a list of the main data structures. Provides a formal description model of subscriber terminal in the notations of extended Petri nets. Are fragments of concrete datalogical implementations of individual program of formal language templates subscription protocol document exchange.

Keywords: post office, telegraph device, communication facilities, documentary exchange.

УДК 004. МНОГОКАНАЛЬНЫЙ АБОНЕНТСКИЙ ПУНКТ СПЕЦИАЛИЗИРОВАННОЙ СВЯЗИ Матюхина Е.Н., Чистякова М.А.

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

абонентский пункт, телеграфное устройство, Ключевые слова:

коммуникационные комплексы, документальный обмен.

~ 120 ~ Введение В настоящее время одной из наиболее острых проблем в обеспечении документального обмена (ДО) на специализированных узлах связи (УС) является крайняя изношенность обширного парка электромеханических телеграфных аппаратов, не говоря уж об их морально устаревших характеристиках, возможностях и низкой надежности [1, 2, 3]. Основу этого парка в подавляющем случае составляют устройства типа РТА-7М, сопрягаемые по высоковольтному стыку. Несколько в меньшем количестве используются аппараты П-115 и П-116, сопрягаемые по низковольтному стыку.

Замена телеграфных аппаратов на автоматизированные рабочие места (АРМ), построенных на базе ПЭВМ, является насущной потребностью на многих УС. Наличие программируемого интеллекта ПЭВМ делает несопоставимыми возможности компьютерной техники с примитивными по современным меркам характеристиками телеграфного устройства (ТГУ) [4].

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

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

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

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

~ 121 ~ Важным аспектом является также экономическая составляющая рассматриваемой проблемы. Так стоимость любой электромеханической ТГУ существенно (едва ли не на порядок!) превосходит цену самого совершенного современного персонального компьютера.

Функциональное назначение абонентского пункта связи Многоканальный абонентский пункт связи (АПС) предназначен для упрощения работы и повышения производительности труда оператора. Функции АПС включают в себя реализацию таких основных задач как:

подготовка и редактирование текстовых сообщений;

обеспечение привязки к средствам коммуникационной системы для обмена сообщениями и проведения прямых телеграфных переговоров с абонентами автоматизированной системы документального обмена (АСДО) в соответствии с правилами формального языка оператора Lапто (Gапто);

обмен телеграммами (передача/прием) по прямым каналам связи при взаимодействии с несколькими ТГУ или аналогичными АПС на формальном языке оператора Lсэс (Gсэс) по правилам, регламентированным руководством существующей эксплуатационной службы;

сохранение и распечатка полученных сообщений;

ввод-вывод строго учитываемых электронных копий сообщений на носитель информации;

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

формирование аппаратных журналов, справок, отчетов и т.п. статистической информации за работы, произведенные на АПС;

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

создание и использования шаблонов (бланков) типовых телеграфных сообщений и т.п.

Функциональные возможности и конструктивное исполнение образцов АПС соответствовали заданным требованиям эксплуатации техники специального применения.

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

~ 122 ~ Аппаратные средства абонентского пункта связи Техническое оснащение АПС реализовано на базе СУЭВМ «РАМЭК ПК 19-1», в составе которой предусмотрено наличие [5]:

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

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

многоканального интеллектуального микропроцессорного контроллера на базе терминального электронного модуля (ТЭМ), обеспечивающего сопряжение АПС с несколькими старт-стопными линиями связи;

полносимвольной клавиатуры и графического манипулятора типа «мышь»;

дополнительной приставки с аналогом клавиатуры телеграфного аппарата;

перфоленточного устройства ввода-вывода;

устройств вывода информации (цветной монитор, принтер);

оборудование ЛВС.

На крупных УС в целях экономии единственные экземпляры перфоустройства и печати, сопряженные с одним из АПС, могут использоваться как коммунальные средства для нескольких АРМ, объединенных, например, ЛВС, или путем ручного переноса информации на портативном носителе (флеш-память).

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

В зависимости от характера использования АПС (организация взаимодействия с коммуникационной системой или обмена по прямым направлениям связи с аналогичными АПС или ТГУ), в нем, соответственно, предусматривается инсталляция одного из двух вариантов диалогового обеспечения, эмулирующего формальный язык телеграфиста Lапто (Gапто) или правила языка службы эксплуатации связи Lсэс (Gсэс).

При взаимодействии АПС с коммутатором в процессе диалога предусмотрено выполнение следующих технологических операций клиентского приложения:

запуск и настройка АПС [9];

идентификация пользователя для доступа к техническим средствам АПС и логическое соединение с коммуникационной системой путем ввода оператором текущего пароля в ответ на запрос коммутатора [10,11,12];

выбор режима работы в главном меню (подготовка сообщения, передача, прием, переговоры, получение справок, просмотр текстов и т.п.);

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

~ 123 ~ визуализация и распечатка сообщений;

составление таблиц соответствия позывных условным адресам абонентов;

получение статистической справочной информации и отчетов по итогам работы АПС по запросу оператора с учетом заданных критериев отбора;

тестирование и контроль аппаратных средств [13,14,15];

завершение работы и выход из системы.

В режиме передачи сообщений оператору предоставляется возможность:

выбора варианта передачи сообщения (одноадресный, многоадресный, по списку);

указать атрибуты сообщения (категория срочности, гриф сообщения, адресная информация в условных адресах или позывных и т.п.);

производить непосредственно набор текста сообщения, используя диалоговый редактор;

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

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

Режим приема сообщений характеризуется перманентным анализом информации, поступающей в АПС из коммутатора. При этом производится автоматическая селекция данных на входные команды, тексты принимаемых сообщений, служебные посылки или квитанции в соответствии с формальным языком Lвывапто Lапто(Gапто). Наличие или отсутствие входной информации автоматически отображается в всплывающем окне на экране монитора в виде мерцающего оповещения.

В режиме приема оператор может:

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

просмотреть принятое сообщение на экране монитора;

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

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

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

Режим переговора обеспечивает:

установку прямого логического соединения с любым абонентом АСДО с указанием атрибутов переговоров;

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

~ 124 ~ вывод принимаемого сообщения на экран монитора, перфоленту или сохранения в файле;

завершение прямых переговоров.

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

Услуги в справочном режиме состоят в формировании по критериям, задаваемым оператором:

итогового отчета о работе АПС за текущие сутки или иной календарный период времени;

аппаратных журналов за переданные, принятые сообщения, переданные и принятые подтверждения, за проведенные переговоры и т.п.

Тип журнала задается в всплывающем окне при подведении курсора к соответствующей «иконке».

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

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

Режим настройки является средством установки различных опций АПС, структурно-адресных таблиц, таблиц позывных абонентов и т.п.

Модель обработки данных Формально программная организация обработки ТЛГ-сообщений в АПС может быть представлена Е-сетью (рисунок 1) E = (P, T, I, O), где P = {p1, арм, тэм, бф1, бф2, прд, прм, тмр, r1, клв, экр}, где p1 – семафор, интерпретирующий занятость обработчика данных;

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

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

бф1, бф2 – позиции, отображающие состояние входного и выходного буферов данных;

прд, прм – позиции, отображающие наличие заявок на передачу и прием в программно-аппаратные «окна» межпроцессорной связи;

~ 125 ~ тмр – макропозиция таймеров;

r1 – решающая позиция выбора направления пересылки результатов программной обработки в выходной буфер для отправки в ТЭМ, на экран дисплея или управление таймерами тмрP;

клв, экр – периферийные макропозиции ввода команд и данных с клавиатуры (мыши) и вывода на экран дисплея.

Рисунок 1 – Е-сеть функционирования АПС T = {t1,…, t7} – множество переходов, где t1 – переход, срабатывающий при поступлении данных на обработку из входного буфера бф1 в позицию армP;

t2 – переход управляющего типа, срабатывающий при распределении передаваемых данных на экран;

t3, t4 – переходы передачи и приема данных при взаимодействии с межпроцессорным «окном»;

t5 – переход, срабатывающий при передаче данных в макропозицию тэм;

t6 – переход, срабатывающий при получении данных из макропозиции тэм на отправку в позицию прмP;

~ 126 ~ t7 – переход, преодолеваемый при срабатывании таймеров макропозиции трмP для направления этих сигналов на последующую обработку во входной буфер бф1P.

I = I(t1) … I(t7) и O = O(t1) … O(t7) – множество входных и выходных позиций, инцидентных переходам t1,…,t7Т.

Процедура смены разметок при срабатывании макроперехода t2Т, управляемого решающей позицией r1, описывается следующим соотношением:

(t2): (µ(r1) = r (i, j, k) µ(арм) = 1, µ(p1) = 0, µ(бф2), µ(тмр), µ(экр)) (µ(r1):= 0, µ(арм) := 0, µ(p1):= 1, µ(бф2) += i, µ(тмр) += j, µ(экр) += k);

{0, 1,…,n} интерпретируют соответственно команды, тексты где метки i, j, k сообщений, таймеры, и данные, выводимые на экран макропозицией армР.

Динамика обработки информации, поступающей от оператора АПС, прослеживается следующей циклической последовательностью срабатывающих переходов …t1, t2, t3, t5, t6, t4,…, t2, t7, t1… Разметка входного буфера µ(бф1) 0 интерпретирует наличие данных на обработку, которые могут поступать из трех источников – от приемника «окна», от таймеров, от устройств ввода (клавиатура, мышь). Аналогично, после их обработки, отображаемой срабатыванием перехода t2, рассылка меток под управлением решающей позиции r1 в общем случае может производиться одновременно по нескольким направлениям – в выходной буфер бф2P для передатчика «окна», на управление таймерами тмрP, на вывод на экран дисплея. Причем число передаваемых меток по разным направлениям может варьировать, например, в зависимости от количества управляемых программных таймеров.

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

Команды взаимодействия с коммутатором В АПС взаимодействие между ЦП и ТЭМ осуществляется через межмашинное «окно» служебными посылками (СП).

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

~ 127 ~ В программах АПС тип tkod служебной посылки определен конечным множеством внутренних управляющих команд Kod = {kod1,…, kods}, идентифицированных типом перечисления [6, 7, 8]. На этом множестве команд произведено разбиение на подмножество команд, отсылаемых из ЦП в ТЭМ в процессе интерпретации команд диалогового меню и экранных форм, которые заполняются телеграфистом, и на подмножество команд, индуцированных выводом коммутатором различных оповещений согласно лексемам языка телеграфиста Lвывапто, распознаваемых анализатором АПС.

Перечень управляющих команд в АПС представлен для иллюстрации в сокращенном виде в нотациях языка программирования МОДУЛА-2:

komanda = ((*--- распознанные СП языка Lвывапто трансформируются в запросы к ЦП ----*) ZaprosGotov, (* запрос готовности *) OpenSv, (* открой связь *) Rabota, (* работа *) PodtverdiSoob, (* подтверди сообщение *) AbortPrioritet, (* прервано по приоритету *) (*---- и т. д. ----*) (* команды, инициирующие лексемы (шаблоны) языка Lввапто, отсылаемые в коммутатор*) CloseSv, (* закрыть связь ЗКР *) PodtverGotov, (*подтверждение готовности ГТВ *) ZaprosPovtor, (*запрос повтора вывода сообщения ЗПР *) (*---- и т. д. ----*) );

Шаблоны выходных лексем Счетное множество выходных лексем Кв = (кв1, …, квq, …), КвD, передаваемых по старт-стопному каналу из АПС в коммутатор, динамически создается и оформляется при поступлении соответствующих служебных посылок из ЦП в процесс вывода интеллектуального контроллера ТЭМ.

Типы шаблонов лексем формального языка телеграфиста определены конечным множеством Тш={tш1,…, tшh}, Тш Tн. Шаблон tшТш состоит из констант знаков телеграфных кодов МТК-2 и необязательных позиций, обозначенных точками ".", которые используются для замены их фактическими параметрами, указанными в служебных посылках.

Упрощенный пример оформления ряда шаблонов Тш, эмулируемых в АПС по запросу оператора или автоматически для отправки лексем квi Lввапто в коммутатор, представлен в следующем виде с использованием телеграфного кода МТК-2:

(* ------------------------------------------------------*) TYPE t6 = ARRAY [0..5] OF CHAR;

t14 = ARRAY [0..13] OF CHAR;

~ 128 ~ t20 = ARRAY [0..19] OF CHAR;

t26 = ARRAY [0..25] OF CHAR;

(* ------------------------------------------------------*) CONST (* ------------------------------------------------------*) (* ПОДТВЕРЖДЕНИЕ ГОТОВНОСТИ *) Tab10 = t6 (0C,32C,20C,23C,4C,"*","*");

(* -----------------------------------------------------*) (* ПОДТВЕРЖДЕНИЕ ПРИНЯТОГО СООБЩЕНИЯ *) Tab16 = t26 (0C,26C,12C,14C,4C, 33С,".",".",".",".",4С, (*.... _ * *) рус К П К П ".",".",".",".",".",".",".","., 4С,0С,17С,26С,17С,26С,"*");

(* ------------------------------------------------------*) (* ЗАПРОС ПОВТОРА СООБЩЕНИЯ *) Tab17 = t20 (0C,21C,26C,12C,4C, 33С,".",".",".",".",4С, ".",".",".",".",".",".",".","., "*");

Шаблоны входных лексем Шаблоны входных лексем языка Lапто (Gапто), поступающих в АПС из коммутатора, а также лексем языка Lсэс (Gсэс), используются анализатором ТЭМ для распознавания оповещений, квитанций и команд и последующей их трансформации в СП и запросы, направляемые через «окно» на обработку в ЦП в позицию армР (см.

рисунок 1). Перечень шаблонов включает в себя весь репертуар структур правильных цепочек символов, генерируемых коммутатором.

Перечень даталогических форматов шаблонов квитанций и служебных посылок lex Lвывапто, распознаваемых анализатором АПС, аналогичен сокращенному списку, приведенному выше. Шаблоны, в частности, предназначены для распознания команд и оповещений типа:

СБРОС ПО ВРЕМЕНИ;

ОШИБКА КС;

ОШИБКА В АДРЕСЕ;

РАБОТА;

ПОДТВЕРДИ СООБЩЕНИЕ;

ПРЕРВАНО ПО ПРИОРИТЕТУ;

СООБЩЕНЕ ПОДТВЕРЖДЕНО;

ЗАПРОС ГОТОВНОСТИ;

ОТКРОЙ СВЯЗЬ и т.п.

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

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

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

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

Заключение Поставленные задачи по созданию автоматизированного абонентского комплекса были реализованы и успешно прошли соответствующие испытания и проверки.

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

Предоставление пользовательских услуг для абонентов, участвующих в документальном обмене, обеспечивается функционально полным набором возможностей контроля и управления и имеет потенциальные тенденции к дальнейшему развитию. Многоканальные возможности АПС позволили повысить надежность привязи либо одновременно к нескольким коммутаторам автоматизированной системы документального обмена, либо созданию минирегиональной автономной корпоративной подсети [17 - 20].

Список информационных источников Матюхина Е.Н., Морозов И.А, Чистякова М.А. Расширение сервисных услуг [1] специализированной связи АСУ ТП // Приборы и системы. Управление, контроль, диагностика. М. 2013. № 4, С. 18–21.

Соловьев Г.А., Соловьев Д.Г. Организация доступа должностных лиц пунктов [2] управления к информационным ресурсам // Труды VIII Российской НТК «Новые информационные технологии в системах связи и управления». - Калуга, 2009. С.

18–21.

Шабанов А.К. Задачи, проблемы и пути внедрения инновационных технологий в [3] разработках предприятия// Труды IХ Российской НТК «Новые информационные технологии в системах связи и управления», Калуга 2010 г. С. 9–15.

Огошкин А.Я., Пиотровский Г.Б., Тимофеев В.М. Создание абонентских пунктов [4] на базе вычислительной техники // Сб. «Повышение эффективности и качества передачи дискретной информации», М.: «Электросвязь», 1979 г., выпуск № 5, С 11– 14.

Применение микропроцессорных средств в системах передачи информации/ [5] Советов Б.Я. и др. – М.: Высшая школа, 1987 г. 253 с.

Поликарпова Н.И., Шалыто А.А. Автоматное программирование // Питер, 2010, [6] 176 с.

~ 130 ~ Иванова Г.С. Технология программирования//изд. МГТУ им. Баумана, М. 2006, [7] с.

Гагарина Л.Г., Кокарева Е.В., Виснадул Б.Д. Технология разработки программного [8] обеспечения//ИД «ФОРУМ»-ИНФА-М, М.2009, 399 с.

Бурлаченко Т.Б., Морозова Т.Ю. Нейросетевая оптимизация абдуктивных [9] выводов в задачах диагностики технических систем. // Мехатроника, автоматизация, управление. 2008. № 8. С. 19–-23.

Сумкин К.С., Морозова Т.Ю., Никонов В.В. Методы управления доступом к [10] информационным ресурсам автоматизированных систем управления на основе канонической модели // Приборы и системы. Управление, контроль, диагностика.

2008. № 10. С. 21.

Сумкин К.С., Морозова Т.Ю. Об использовании нечетких множеств для [11] разграничения прав доступа информационной сети // Наукоемкие технологии.

2008. Т. 9. № 7. С. 12.

Морозова Т.Ю., Никонов В.В., Королев А.А. Нейросетевая концепция безопасной [12] передачи данных в беспроводных компьютерных сетях //Сборник научных трудов Sworld. 2008. Т. 2. № 1. С. 29-34.

Морозова Т.Ю., Ремонтов А.П., Скворцова Т.И., Чистякова М.А. О возможности [13] компенсации дополнительного шума, вводимого в канал передачи для защиты информации // Инженерная физика. 2009. № 6. С. 22-25.

Морозова Т.Ю., Петров О.М. Вероятностно-статистические методы и средства [14] повышения эффективности защиты и обработки информации в беспроводных сетях. Москва, 2008.

Морозова Т.Ю. Аналитическое выражение и оценка показателя устойчивости [15] защитного шума к компенсации. Часть 2 // Системы управления и информационные технологии. 2008. № 1 (31). С. 16–20.

Морозова Т.Ю., Сумкин К.С. Модели контроля доступа пользователя к ресурсам [16] системы // Сборник научных трудов Sworld. 2007. Т. 2. № 1. С. 11–14.

Матюхина Е.Н., Морозов И.А. Компьютерная сеть специального назначения для [17] систем экологического мониторинга // Промышленные АСУ и контроллеры.

2010. № 1. С. 7-9.

Остроух А.В. Системы искусственного интеллекта в промышленности, [18] робототехнике и транспортном комплексе: монография / А.В. Остроух Красноярск: Научно-инновационный центр, 2013. – 326 с. - ISBN 978-5-906314-10 9.

Пермяков А.А. Модуль управления дебиторской задолженностью для [19] телекоммуникационной компании на базе решений SAP FOR TELECOMMUNICATIONS / А.В. Будихин, А.Б. Маврин, А.В. Остроух, А.А.

Пермяков // Приборы и системы. Управление, контроль, диагностика. - М.:

«Научтехлитиздат», 2007. - №10. - С. 12-16.

Пермяков А.А. Опыт внедрения решений SAP FOR TELECOMMUNICATIONS для [20] управления дебиторской задолженностью на ОАО МГТС / А.В. Остроух, А.А.

Пермяков // Вестник Российского нового университета. Серия естествознание, математика, информатика. – М.: РосНОУ, 2007. - Вып. 2. - С. 108-111.

~ 131 ~ DOI: 10.12731/2306-1561-2013-4- ACCESS RIGHTS IN COMPUTER NETWORKS Sumkin K.S.

Abstract The article describes the research, development model differentiation of access rights users to improve administrative efficiency in computer networks. The methods of fuzzy giperrezolyutsii, orthogonal Latin squares to solve the problem of determining the parameters of access to each specific situation. The methods of fuzzy inference to determine access rights.

Keywords: access rights, fuzzy logic.

УДК 004. РАЗГРАНИЧЕНИЕ ПРАВ ДОСТУПА В КОМПЬЮТЕРНЫХ СЕТЯХ Сумкин К.С.

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

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

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

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

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

Для достижения поставленной цели решены следующие основные задачи:

проведен анализ современных моделей, методов, алгоритмов и программных средств РПД пользователей в компьютерных сетях, выявлены основные проблемы и осуществлен выбор путей их решения;

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

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

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

Обзор существующих подходов РПД пользователей в компьютерных сетях Рассмотрены отечественные и зарубежные программные и аппаратные средства, с помощью которых осуществляется РПД пользователей в современных операционных системах. В частности, рассмотрены следующие программные средства: продукты фирмы Microsoft (операционные системы Windows Server NT/2000/2003, Windows XP/Vista), ОС Novell Netware и LINUX (RedHat, Ubuntu). В качестве рассмотренных аппаратных средств выступают системы разграничения доступа «КРИПТОН Щит», а также Secret Net. Отмечены положительные и отрицательные стороны средств [1].

Исследованы модели РПД пользователей в компьютерных сетях. К ним относятся каноническая модель, а также базовые модели доступа: модель Take – Grant и её основные расширения, модель Белла – ЛаПадула и её интерпретации, модель систем военных сообщений, модель ролевого разграничения доступа [3]. В качестве типового решения, характерного для рассмотренных программных и аппаратных средств РПД пользователей компьютерных сетей, является использование модели ролевого разграничения доступа, функционирование которой проиллюстрировано на рисунке [1].

~ 133 ~ Рисунок 1 - РПД пользователей компьютерных сетях Значительное внимание при РПД уделено эффективности администрирования в компьютерных сетях, то есть комплексу мер, проводимых при РПД пользователей с целью обеспечения санкционированного доступа к ресурсам сети. Эффективность определяется следующими показателями: отказоустойчивость, возможность получения НСД, скорость работы системы, получение санкционированного доступа.

Показано, что классические модели по РПД пользователей не позволяют учитывать различные уровни иерархии субъектов, коэффициенты важности и доверия, а также параметры доступа пользователей к ресурсам [9 – 12].

Анализ возможных путей решений задачи РПД, способных учесть различные уровни иерархии субъектов, коэффициенты важности и доверия, а также параметры доступа пользователей к ресурсам показал, что для решения подобной задачи могут быть использованы подходы на основе использования нейросетевой технологии, нечеткого логического вывода (Мамдани, Ларсена, Цукамото, Сугэно 0 порядка, Такаги – Сугэно), ортогонально–латинских квадратов.

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

~ 134 ~ Теоретические вопросы разработки модели РПД пользователей компьютерных сетей Под объектом понимается любой элемент компьютерных сетей O = {O1, O2,...., O k }.

В качестве объекта доступа i (i = 1, k ) рассматривается как отдельный объект, так O и группа объектов, характеризуемых одинаковыми для них правами доступа [2].

Под субъектом понимается любая сущность, способная инициировать выполнение S = {S 1, S 2,....., S k } операций над объектами [2].

Под доступом понимается выполняемая операция, определенная для некоторого объекта.

Сформулируем утверждение о возможности доступа субъекта к объекту, в соответствии с которым субъект S i может получить доступ к объекту Oi, если d существует субъект S i +1, имеющий доступ ij, к элементу Oi такой, что субъекты S i и S i +1 связаны бинарным отношением, содержащим хотя бы одно из возможных прав.

Рассмотрены и доказаны все возможные случаи исходных условий доступа.

Для идентификации прав субъекта на определенный объект, а также для автоматизации процесса РПД пользователей введены рабочие определения специальных матриц «доверия» и «важности».

Определение 1. Матрица важности объектов - это квадратная матрица, состоящая из коэффициентов шкалы ценности [0,1], которые определяются субъектами (пользователями) и соответствуют степени важности обрабатываемой информации на объекте.

Определение 2. Матрица доверия субъекту - это вектор, коэффициенты которого определяются экспертом (в соответствии со шкалой [0,1]) и показывающие возможность субъекта изменять или добавлять информацию на объекте.

Представим базовую модель ролевого разграничения доступа, описывающую права работы субъекта с объектом (внесение информации на объект, права обработки субъектом информации, изменения информации). Как развитие данной модели за счет введенных матриц доверия и важности была предложена и исследована модель РПД вида R = A C, где R - вектор, состоящий из кандидатов субъектов на получение права доступа, A - матрица важности, имеющая размерность n n, C - вектор-столбец доверия размерностью n. Выбор максимума из элементов вектора R, происходит путем перебора всех его элементов, что позволяет определить право субъекта на объект.

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

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


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

Определение 3. Параметры доступа (ПД) - это переменные, с помощью которых S, S,..., S n O, O,..., Om определяется доступ субъектов 1 2 к объектам 1 2.

В таблице 1 представлен пример возможных значений ПД (где sec степень важности обрабатываемой информации, nei - степень необходимости в конкретной информации для субъекта, dng степень возможной опасности исходящей от каждого субъекта).

Таблица 1 – Пример значений ПД Переменная 1 2 Параметр Не важная Важная Очень важная sec Не нужная Нужная Жизненно nei необходимая Минимальная Средняя Максимальная dng Субъект получает доступ к объекту при наличии соответствующих значений ПД.

С этой целью введено определение существенных параметров доступа.

Определение 4. Существенные параметры доступа - это значения ПД, которые необходимы для получения доступа субъектов к объектам.

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

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

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

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

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

~ 136 ~ sec( S i ) nei ( S i ) ¬dng ( S i ) ur _ d ( S i ), (1) (S i ) субъект, а ur _ d количественный показатель для оценки где возможности доступа субъекта к объекту.

2. В случае, если в семантической процедуре лингвистической переменной не sec( S i ), nei ( S i ), ¬dng ( S i ) описано преобразование, то эксперт определяет для данного субъекта.

(S i ) 3. Определяется значения ur _ d для субъекта, которое сравнивается с некоторой нижней границей и делается вывод о соответствии существенных ПД для (S ) субъекта i.

Данный метод определения существенных ПД не позволяет в полной мере автоматизировать процесс РПД пользователей в компьютерных сетях из–за необходимости постоянного привлечения эксперта для определения sec( S i ), nei ( S i ), ¬dng ( S i ). С целью повышения степени автоматизации процессов взаимодействия с экспертом (соответственно снижение нагрузки на администраторов) введено понятие о функциональных матричных блоках, удобных для моделирования РПД по существенным ПД.

X Суть предложенного подхода заключается в следующем пусть i множество векторов переменной длины от 1 до (ni ), где i = {1, N }, N – количество значений ПД, X Zj L(Wi, wi, X i ) «латинское преобразование» и i.

Z = NX i Тогда, приняв j, выражение для «одноканальной» инверсии многозначной логики будет иметь вид:

NX i = L(Wi, wi, X i ). (2) При умножении базовой матрицы и построенных ортогонально – латинских квадратов вычисляются значения результирующей матрицы. Элементы результирующей матрицы соответствуют рекомендациям о том, какими существенными ПД обладает субъект. Детальное описание алгоритма, реализующего данный метод, и результаты эксперимента приведены в разделе 3.

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

O = {µ O ( x) / x}, (3) где x элемент множества объектов, а µ O (x) характеристическая функция принадлежности;

S = {µ S ( y ) / y}, (4) ~ 137 ~ µ ( y ) характеристическая функция где y элемент множества субъектов, а S µ O (x) и µ S ( y ) принимают принадлежности, причем функции принадлежности собственные значения в некотором упорядоченном множестве [0,1]. Каждый элемент множеств субъектов и объектов рассматривается как собственное нечеткое подмножество. В этом случае можно рассматривать не отдельные элементы субъектов и объектов, а принадлежность элементов нечетким подмножествам.

Предложим формализм представления нечетких продукционных правил и алгоритм нечеткого логического вывода (НЛВ). Главное отличие разработанного алгоритма от традиционных методов НЛВ (в частности, Мамдани, Цукамото, Сугэно порядка и других) заключается в том, что в правилах используется не только нечеткая импликация Мамдами, но и любые вычисления, необходимые для получения доступа.

Нечеткие продукционные правила, строятся следующим образом [4]:

П i : ЕСЛИ y есть µ S ( y) i И x есть µ O ( x) i И(ИЛИ) sec есть L И(ИЛИ) nei есть M И(ИЛИ) dng есть N ТО d i =, (5) где i правило доступа субъекта к объекту i = {1, n}, где n количество П правил.

Опишем этапы разработанного алгоритма НЛВ [7].

Этап 1. Фазификация.

Этап 2. Вычисление степеней срабатывания предпосылок по каждому из правил i (по методу, выбранному экспертом).

i, i i = f i ( i ) Этап 3. Активизация заключений по каждому из правил, где f i ( i ) функция доступа субъекта к объекту с параметром i, вычисляемым на втором этапе.

Этап 4. Дефазификация.

n d i i D= i = n i i =1, (6) где D значение доступа i го субъекта к i му объекту.

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

Если построить обратную функцию доступа нельзя или её определение в ряде случаев невозможно, то тогда применяется алгоритм нечеткого логического вывода Сугэно 0 порядка. В этом случае значение доступа присваивается в виде константы.

Тогда база нечетких продукционных правил формируется следующим образом [8, 9, 11, 12]:

~ 138 ~ µ S ( y) i И x есть µ O ( x) i И(ИЛИ) sec есть L И(ИЛИ) nei есть Пi : y ЕСЛИ есть M И(ИЛИ) dng есть N ТО d i = const i. (7) Этапы разработанного алгоритма НЛВ аналогичны предыдущему, за исключением второго этапа, который имеет следующий вид.

Этап 2. Вычисление степеней срабатывания предпосылок по каждому из правил const i.

Таким образом, построена модель РПД в компьютерных сетях, основанная на формализме нечетких продукционных правил (5), (7), которые описывают доступ субъектов к объектам, что обеспечивает учет параметров доступа, а также различные уровни иерархии пользователей.

Кроме того, разработаем модель создания информационных потоков по памяти и по времени. С этой целью введено значение порогового значения (Dpor ), при котором доступ для субъекта разрешен и создается информационный поток по времени. Если значение доступа D, определяемое по формуле (6), больше или равно пороговому значению Dpor, при котором доступ к объекту разрешен, то создается информационный поток по времени. В этом случае, модель создания информационных потоков по времени представляется в виде [8]:

1, если D Dpor can _(права ) _ time = 0, если D Dpor. (8) Таким образом, получено решение актуальной задачи разграничения прав доступа пользователей к ресурсам компьютерных сетей, которое позволяет учитывать существенные ПД.

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

Шаг 1. Определение существенных ПД по формулам (1), (2).

Шаг 2. Если новых значений ПД не было, или их количество не превышает 18, тогда применение метода многозначной логики, иначе использование смешанного метода многозначной логики и гиперрезолюционного вывода.

Шаг 3. Замена всех множеств субъектов и объектов соответствующими нечеткими множествами по формулам (3), (4).

Шаг 4. Построение функции принадлежности для объекта и субъекта.

Шаг 5. Формирование базы нечетких продукционных правил по формулам (5) или (5), (7).

Шаг 6. Выбор механизма НЛВ. Определение этапов нечеткого логического вывода для каждого алгоритма по формуле (6).

~ 139 ~ Шаг 7. Если значение, вычисленное по формуле (6), не превышает порогового значения, то создание информационного потока по времени по формуле (8).

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

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

подсистема определения ПД (в которую входит средство определения существенных ПД);

подсистема определения доступа (в которую входит нечеткий решатель, а также средство создания информационных потоков);

подсистема ведения журналов событий.

Заключение Таким образом, проведен анализ современных моделей, методов, алгоритмов и программных средств РПД пользователей в компьютерных сетях, выявлены основные проблемы и осуществлен выбор путей их решения;

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


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

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

Список информационных источников Сумкин К.С., Морозова Т.Ю., Никонов В.В. Методы управления доступом к [1] информационным ресурсам автоматизированных систем управления на основе канонической модели.// Приборы и системы. Управление. Контроль. Диагностика, 2008, № 10, с. 21 – 23.

Сумкин К.С., Морозова Т.Ю. Об использовании нечетких множеств для [2] разграничения прав доступа информационной сети. // Наукоемкие технологии, 2008, №7, т.9, с. 12–14.

Сумкин К.С., Морозова Т.Ю. Использование канонической модели для [3] разграничения прав пользователей локальной вычислительной сети. Сборник трудов X научной Всероссийской научной – технической конференции “Новые информационные технологии». – М.: МГУПИ, 2007, с. 113– 118.

Сумкин К.С., Морозова Т.Ю. Модели контроля доступа к ресурсам системы.

[4] Сборник трудов Международной научно – практической конференции ~ 140 ~ «Современные направления теоретических и прикладных исследований». – Одесса: Черноморье, 2007, с. 11 – 15.

[5] Сумкин К.С., Морозова Т.Ю. Использование нечетких множеств для управления доступом пользователей к ресурсам системы в условиях неопределенности.

Сборник трудов Международной научно – практической конференции «Современные направления теоретических и прикладных исследований». Том 5 – Одесса: Черноморье, 2008. С. 48– 52.

[6] Сумкин К.С. Об использовании теней нечетких множеств для разграничения прав доступа пользователей. Сборник научных трудов по материалам международной научно - практической конференции «Перспективные инновации в науке, образовании, производстве и транспорте». Одесса, 2008, с. 31–35.

[7] Сумкин К.С., Никонов В.В. О некоторых методах защиты средств вычислительной техники. Новые информационные технологии: Сборник трудов 10 Всероссийской научно - технической конференции (Москва, 19 - 20 апреля 2007 г.) / Под ред. А.П.

Хныкина, А.Ю. Выжигина. – М.: МГУПИ, 2007, с. 45–51.

[8] Сумкин К.С. Методы нечеткой логики для обеспечения безопасной работы пользователей сети. Современные технологии в задачах управления, автоматики и обработки информации // Труды 17 международного научно – технического семинара. Алушта, сентябрь 2008 г, с. 60 – 61.

[9] Остроух А.В. Исследование начального периода моделирования на точность среднеинтегральной оценки имитационных моделей / А.В. Остроух, А.А. Солнцев, Н.В. Солдатов, К.А. Новицкий, П.С. Якунин // Вестник МАДИ. – 2010. - Вып. 2(21).

- С. 61-65.

[10] Антонов П.Д. User Is A Great Obstacle For Security Systems / П.Д. Антонов, А.В.

Остроух // Молодой ученый. - 2011. - №4. Т.3. - С. 62-63.

[11] Остроух А.В. Основы построения систем искусственного интеллекта для промышленных и строительных предприятий: монография / А.В. Остроух. – М.:

ООО «Техполиграфцентр», 2008. - 280 с. - ISBN 978-5-94385-033-2.

[12] Остроух А.В. Системы искусственного интеллекта в промышленности, робототехнике и транспортном комплексе: монография / А.В. Остроух Красноярск: Научно-инновационный центр, 2013. – 326 с. - ISBN 978-5-906314-10 9.

DOI: 10.12731/2306-1561-2013-4- CONSTRUCTING A TREE OF DATA TRANSMISSION IN WIRELESS SENSOR NETWORKS Ivanova I.A., Shestakov A.A.

Abstract This article examines the wireless sensor networks (WSN), provides a brief description of the structure of the sensor network and sensor node. Discusses graphs as models used to describe wireless sensor networks. Lists the types of network topology, which can be described by graphs. It is shown that the topology of the WSN can best be described in a random graph.

Proposed to increase the duration of the network life to use a tree of data transmission, built ~ 141 ~ on a limited selection of sensors of WSN. This article discusses the use of Prfer code for organization of data transmission routes in wireless sensor networks. Algorithm of constructing the code, including supporting algorithms (for example, the algorithm of finding the leaves) is presented. Using of Prfer code in models of wireless networks for various purposes can help in the development of the schedule of work of the WSN and to increase the overall energy efficiency of the network.

Keywords: wireless sensor networks, sensor node, random graph, tree of data transmission, Prfer code.

УДК 004. ПОСТРОЕНИЕ ДЕРЕВА ПЕРЕДАЧИ ДАННЫХ В БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ Иванова И.А., Шестаков А.А.

Аннотация В настоящей статье рассматриваются беспроводные сенсорные сети (БСС), дается краткое описание структуры сенсорной сети и сенсорного узла.

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

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

Введение Беспроводные сенсорные сети (БСС) предназначены для регистрации параметров окружающей среды в заданной области исследований. БСС построены на основе сети сенсорных узлов (СУ), каждый из которых оснащён одним или несколькими датчиками, контроллером, приемопередатчиком и источником питания [1 – 4, 14]. При этом сенсорные узлы могут быть размещены как по заранее разработанному плану, так и случайным образом, их количество может быть переменным.

~ 142 ~ СУ могут осуществлять временное хранение и предварительную обработку данных, полученных как от собственных датчиков, так и по сети от других узлов [5, 14].

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

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

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

В качестве математической модели для описания БСС используется теория графов.

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

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

При описании связей узлов-вершин будем пользоваться следующими понятиями [7].

Дуга – ориентированное ребро, соединяющее упорядоченную пару вершин (i, j), то есть направленное от i к j, но не наоборот.

Сильный путь, цепь – последовательность разных вершин, соединенная дугами.

Например, для множества вершин {i, j, k} цепью является последовательность дуг (i, j), (j, k).

~ 143 ~ Слабый путь – последовательность из двух и более разных вершин, соединенных дугами с одной конечной вершиной. Например, для множества вершин {i, j, k} слабый путь является совокупностью дуг (i, k), (j, k).

Связность графа, представляющего БСС, описывается такими понятиями, как:

сильно связный граф – если любая упорядоченная пара вершин может быть связана дугами;

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

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

Граф может быть разделен на подграфы. Подграф Gs – граф, множества вершин и ребер которого являются подмножествами вершин и ребер графа G соответственно.

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

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

Применительно к БСС будем различать:

дерево передачи данных – дерево, в котором существует только одна вершина, не имеющая выходящей дуги;

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

Если в составе БСС две и более БС, граф сети может быть представлен как лес, если состоит из двух и более несвязанных деревьев.

Топология сети (графа) При исследовании БСС могут рассматриваться следующие топологии графов.

Решетка. Топология, имеющая форму двумерной сетки, на пересечении линий сетки располагаются вершины. Внутренние вершины имеют связь с четырьмя соседями, внешние вершины (пограничные узлы) имеют связь с тремя или двумя соседями.

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

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

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

~ 144 ~ Модель передачи данных в БСС Существуют различные модели описания графов, такие как матрица Кирхгофа, матрица смежности и другие. В тех случаях, когда речь идёт о передаче данных в БСС, то интерес могут представлять модели на основе теории перколяции [8, 9] и кода Прюфера.

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

Все датчики имеют одинаковую возможность отправлять собранные данные с некоторой периодичностью, так что вся исследуемая площадь покрывается с фиксированной задержкой [10, 11].

Процесс сбора данных со всей исследуемой области осуществляется циклически.

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

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

Рисунок 1 - Сбор данных Закрашенные черные точки с маленьким кружком вокруг (s1...s6) на обоих рисунках (рисунки 1(а) и 1(б)) обозначают выбранные в настоящий момент сенсоры, обеспечивающие заданную зону покрытия (ЗЗП), указанную пользователем или приложением, а не закрашенные точки (рисунок 1(б)) обозначают сенсоры, которые ~ 145 ~ были активными в предыдущей сессии. Большая окружность обозначает зону чувствительности выбранного в данный момент сенсора. Допустим, что первое множество из шести сенсоров на рисунке 1(а) покрывает заданную часть исследуемой области, но не всю область. К примеру, закрашенная серым область на рисунке 1(а) покрывается вторым множеством датчиков, как показано на рисунке 1(б). То есть полностью исследуемая область будет покрыта после выполнения двух сессий, то есть после определенной фиксированной задержки. При такой системе сбора данных проблема заключается в том, чтобы подобрать минимально необходимое число сенсоров, удовлетворяющих ЗЗП при каждой сессии, а 100% покрытие всей исследуемой области должно быть осуществлено за некоторое заданное время.

Рассмотрим множество сенсоров N, расположенных на исследуемой площади Q в произвольном порядке, при этом каждый сенсор si имеет зону чувствительности SRi. В ходе текущей сессии из множества N выбирается минимальное число сенсоров k такое, что (( SRi)Q)ЗЗП для каждой сессии.

При выборе k сенсоров для каждой сессии вся исследуемая область Q будет покрыта с фиксированной задержкой T. Пусть tj – продолжительность передачи данных в ходе j-й сессии при общей площади покрытия SCj=(( SRi)Q)ЗЗП. Из этого следует, что потребуется последовательных сессий, таких, что (( SRjQ)=Q).

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

Рассмотрим БСС как связанный граф G=(V,E), где V – множество вершин, обозначающих сенсоры и базовые станции, служащие точками сбора данных и управляющими центрами;

E – множество ребер, обозначающих двунаправленные линии беспроводной связи между сенсорами (или сенсорами и базовыми станциями) с учетом радиуса связи. Большое количество однотипных сенсоров распределено с высокой плотностью по ограниченной площади. Они устанавливают местные связи в момент развертывания сети, а также адаптируются к изменениям топологии при выходе сенсоров из строя [12].

Рассмотрим случайные узлы, занумерованные от 1 до m, динамические, занумерованные от 1 до d, и стационарные, занумерованные от 1 до q.

Известно, что узел Si из m случайных узлов, появляющихся последовательно, имеет предпочтение установить связь с соседним узлом, номер которого Sj.

Каждый способ распределения узлов определяется преобразованием из множества схем связи узлов X={1,2, …, m}.

Если (i)=Si, i=1,2, …,m, то вектор (S1,S2, …,Sm), именуемый вектором предпочтения, однозначно определяет распределения узлов предпочтения.

Рассмотрим совокупность отображений вида ~ 146 ~ : XY, где X={1,2,…,m}, Y={1,2,…,(m+1)}.

Каждое отображение определяется производным вектором (S1,S2,…,Sm), Si=(i), i=1,2,…,m.

При использовании вектора предпочтения (S1,S2,…,Sm) считается, что если Si=m+1, то при занятом (m+1) динамическом узле i-й случайный узел устанавливает связь с динамическим узлом, который имеет наименьший вес.

Каждый произвольный вектор определяет расположение узлов, при котором один из узлов оказывается свободным. Общее число производных векторов равно (m+1)m.

Число возможных способов установления связи между узлами определяется следующим образом [14-17]:

(m + 1) m Vm= m + 1 = (m+1)m-1.

Дано отображение, которое каждому свободному дереву с (m+1) вершиной ставит во взаимно однозначное соответствие вектор предпочтения. Вектору (S1,S2, …, Sm) ставится в соответствие вектор (1, 2, …, m-1), где i=(Si+1-Si)mod(m+1).

Далее вектору (1, 2, …, m-1), соответствующему коду Прюфера [18-24], ставилось в соответствие дерево с (m+1) вершинами.

Установлено, что существует взаимно однозначное соответствие между вектором (1, 2, …, m-1) и нумерованным деревом.

Определим матрицу размером 2(n-1) x1 x2... xn, y y2... yn 1 в которой (xi,yi) – i-ое ребро, удаленное в процессе конструирования кода Прюфера, и xi – это лист, который был удален. Последний столбец (xn-1,yn-1), где xn 1yn-1 будет представлять последнее оставшееся ребро. Эта матрица называется расширенным кодом Прюфера для дерева. Расширенный код Прюфера позволяет восстановить дерево передачи данных в случае потери узлов.

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

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

Возьмем множество (y1, y2, …,yn-2). Зададим yn-1. Затем для каждого i=1,2,…,n- найдем xi с наименьшим номером, не принадлежащим набору {x1,…, xi-1}{yi, …,yn 1}.

Например, ~ 147 ~ 2 3 5 4 6 1 4 4 6 1 1 4 4 6 1 7.

Если наша изначальная последовательность действительно является кодом Прюфера для некоторого дерева, то можно заметить, что числа, не принадлежащие множеству {x1,…, xi-1}{yi, …,yn-1}, в действительности являются листьями этого дерева после i удалений. Так как при кодировании выбирается наименьший текущий лист, то матрица, сгенерированная выше описанным процессом, на самом деле является расширенным кодом Прюфера исходного дерева.

Теперь, взяв матрицу размера 2(n-1) с вхождениями из {1,2,…,n} определим граф, чьи ребра являются столбцами матрицы. Если начать с произвольной последовательности длины n-2 из алфавита {1,2, …,n} и преобразовать ее в расширенный код с помощью описанного способа, то можно утверждать, что полученный граф является деревом, более того, код Прюфера этого дерева – та самая последовательность, с которой все началось.

Для существующего кода столбцы матрицы соответствующего расширенного кода являются деревом, для которого код Прюфера является исходным кодом.



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |
 





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

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