РАЗДЕЛ 2
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПОВЕДЕНИЯ ДИНАМИЧЕСКИХ ПРОЦЕССОВ С БОЛЬШИМ КОЛИЧЕСТВОМ БИНАРНО СВЯЗАННЫХ ОБЪЕКТОВ
2.1. Событийная модель динамического процесса с большим количеством бинарно связанных объектов
Введем в рассмотрение конечный автомат [72]:
,
где X - входные сигналы;
Y - выходные сигналы;
Q - множество внутренних состояний;
? - функция выходов Q x X --> Y;
? - функция переходов Q x X --> Q;
q0 - начальное состояние.
Будем рассматривать такие конечные автоматы, у которых , т.е. конечные автоматы Мура [70].
Традиционно конечные автоматы объединяются в систему М с помощью представления в виде прямого произведения n конечных автоматов с одинаковым входным алфавитом [22]:
(2.1) Иными словами, если конечный автомат M есть прямое произведение n конечных автоматов L1...Ln, то:
- состояниями автомата M являются комбинации состояний исходных автоматов L1...Ln;
- начальное состояние автомата M есть множество, состоящее из начальных состояний автоматов L1...Ln;
- выходной алфавит автомата M есть множество комбинаций выходных символов автоматов L1...Ln;
- функции переходов и выходов автомата M определены покомпонентно, т.е. матрицами ? и ?.
Далее все элементарные объекты моделируемого процесса будем рассматривать в виде одинаковых конечных автоматов. Под связью автоматов будем понимать [19] подачу сигналов с выходов одного конечного автомата на входы другого конечного автомата. Очевидно, что с течением времени и появлением новых событий в системе эти связи будут перестраиваться.
В данной работе при моделировании приняты следующие допущения:
1) Длительность взаимодействия объектов равна нулю.
2) В каждом взаимодействии участвуют только два объекта (взаимодействия бинарные, направленные).
Таким образом, n конечных автоматов объединяются в систему ? только бинарными связями:
.(2.2) Связь является однонаправленной, т.е., если Li связан с Lj, то это не означает, что Lj связан с Li:
.(2.3) Согласно определению конечного автомата [73], конечный автомат - это автомат, который обрабатывает входную цепочку и в любой момент времени находится в каком-то состоянии. Для моделирования поведения этого автомата необходимо определить этот момент времени.
Для описания эволюции динамической системы в фазовом пространстве M необходимо задать множество моментов времени T. Для этого введем дополнительный скаляр tai каждого автомата Li.
Примечание. Введение дополнительного скаляра tai и генератора T в БА-модель является вспомогательным приемом. На практике в качестве ведущего параметра - параметра, который в БА-модели принимается за скаляр T, удобно выбрать какой-либо из параметров, присущих системе. Поэтому далее при исследовании течения газа за ведущий параметр примем время. Однако это не является правилом, так, например, при построении клиент-серверных систем за ведущий параметр принят приоритет потока идентифицирующего соединение [24].
Изменение tai будем осуществлять, используя дополнительный вход tвхi. Данные Tk на вход tвхi поступают от общего генератора T:
.(2.4) Графическая интерпретация предлагаемой модели показана на рис. 2.1.
Каждый из рассматриваемых объектов связан с другими объектами зависимостью, которую можно представить в виде ориентированного графа. От каждого автомата можно провести связывающий луч к другому, который становится известным после установления времени до ближайшего события для рассматриваемого объекта. В момент взаимодействия происходит изменение состояний обоих автоматов с помощью функции перехода, построенной на уравнениях, характерных для моделируемой системы, например, уравнениях механики для дискретно-событийного моделирования течения газа. При этом перестраивается структура всего потока моментов времени взаимодействий.
На рис. 2.1 автоматы объединены в систему, что показано синими стрелками. Каждый из автоматов имеет свой дополнительный вход, на который подаются данные с генератора времени, что показано красными стрелками.
Рис. 2.1. Графическая интерпретация БА-модели Каждый шаг моделирования контроллер системы выбирает из всего набора автоматов те, которые соответствуют текущему событию, выбираемому из очереди событий. После этого рассчитываются новые внутренние состояния. При этом перестраиваются связи для выбранных автоматов, осуществляется расчет их ближайших событий, которые помещаются в свое место в очереди согласно времени их наступления. На следующем шаге моделирования выбираются следующие автоматы.
Принимая во внимание новое внутреннее состояние и новый вход, наложим на функции ? и ? дополнительное ограничение.
Ограничение 1. Автомат Li осуществляет переход в новое состояние тогда и только тогда, когда tаi = Tk.
Утверждение 1. Состояния Qi и выходные параметры Yi системы автоматов ? не зависят от введения параметра tai, и ограничения 1.
Доказательство. Покажем, что введение нового параметра tai никак не отразится на выходе конечного автомата Li:
а) ? - функция, зависящая от q, x;
б) ? - функция, зависящая от q, x.
При этом q, x не зависят от tai. Следовательно, ? и ? не зависят от tai. Таким образом, состояние qk, в которое перейдет автомат Li в момент времени tai , не зависит от tai .
При моделировании поведения системы на цифровых устройствах невозможно добиться непрерывности изменения сигнала T [74]. Всегда существует минимальное изменение сигнала (h), которое является характеристикой точности вычислений на конкретно взятой цифровой вычислительной системе. Следовательно:
Tk = Tk-1 + h .(2.5) Очевидно, что могут существовать такие T, при которых не будет осуществляться переход ни одного из автоматов Li системы ? из одного состояния в другое, так как не найдется ни одного Li, для которого выполнялось бы условие перехода (2.4):
.(2.6) Таким образом, при моделировании возникает проблема синхронизатора. Для
- Київ+380960830922