Министерствообразования Республики Беларусь
Учреждениеобразования
«Гомельскийгосударственный университет им. Ф. Скорины»
Математическийфакультет
КафедраТВ и мат статистики
Курсоваяработа
ОТКРЫТЫЕСЕТИ С МНОГОРЕЖИМНЫМИ СТРАТЕГИЯМИ ОБСЛУЖИВАНИЯ И ИНФОРМАЦИОННЫМИ СИГНАЛАМИ
Исполнитель:
Студентгруппы М-32 Левашов А.Ю.
Научныйруководитель:
Канд.физ-мат. наук, доцент
МалинковскийМ.Т.
Гомель2007
СОДЕРЖАНИЕ
ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ
ВВЕДЕНИЕ
1. ОТКРЫТЫЕ СЕТИ С МНОГОРЕЖИМНЫМИСТРАТЕГИЯМИ ОБСЛУЖИВАНИЯ И ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ
2. ОТКРЫТЫЕ СЕТИ С МНОГОРЕЖИМНЫМИСТРАТЕГИЯМИ ОБСЛУЖИВАНИЯ И ИНФОРМАЦИОННЫМИ СИГНАЛАМИ ДВУХ ТИПОВ
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ
/> - число узлов всети массового обслуживания, размерность вектора состояний марковскогопроцесса, описывающего сеть;
/> - число заявок,циркулирующих в замкнутой сети;
/> - матрицамаршрутизации для открытой сети;
/> - матрицамаршрутизации для замкнутой сети;
/> - состояние />-го узла;
/> - число заявокв />-ом узле (/> для открытой сети, /> для замкнутой сети);
/> - номер режимаработы прибора в />-м узле />;
/> - состояние />-го узла в момент времени />;
/> - число заявокв />-м узле в момент времени />;
/> - номер режимаработы прибора в />-м узле в моментвремени />;
/> - состояниесети массового обслуживания;
/> - марковскийпроцесс, описывающий состояние сети массового обслуживания в момент времени />;
/> - марковскийпроцесс, описывающий состояние изолированного узла в фиктивной окружающейсреде;
/> - пространствосостояний случайного процесса /> имарковского процесса /> в случаеоткрытой сети;
/> - пространствосостояний случайного процесса /> имарковского процесса /> в случаезамкнутой сети;
/> - пространствосостояний марковского процесса /> дляоткрытой сети и /> для замкнутойсети);
/> - интенсивностьперехода марковского процесса с непрерывным временем и не более чем счетнымпространством состояний из состояния /> всостояние />;
/> - интенсивностьвыхода марковского процесса из состояния />;
/> - стационарноераспределение марковского процесса />.
/> - стационарноераспределение марковского процесса /> вслучае открытой сети;
/> - стационарноераспределение марковского процесса /> вслучае замкнутой сети;
/> - интенсивностьпуассоновского потока, поступающего в открытую сеть;
/> - интенсивностьпуассоновского потока положительных заявок;
/> - интенсивностьпуассоновского потока отрицательных заявок (сигналов);
/> - интенсивностьпуассоновского потока сигналов, увеличивающих номер режима;
/> - интенсивностьпуассоновского потока сигналов, уменьшающих номер режима;
/> - интенсивностьобслуживания прибором />-го узла,находящегося в состоянии />;
/> - интенсивностьперехода прибора />-го узла с режима/> на режим />;
/> - интенсивностьперехода прибора />-го узла с режима/> на режим />;
/> - интенсивностипотоков положительных заявок, отрицательных сигналов, сигналов увеличенияномера режима, сигналов уменьшения номера режима соответственно в />-й узел открытой сети;
/> - вероятностинаправления в />-й узел поступающих воткрытую сеть положительных заявок, отрицательных сигналов, сигналов уменьшенияномера режима, сигналов увеличения номера режима соответственно;
/> - вероятностидля заявки, обслуженной в />-м узле,перейти в />-й узел с превращением ее вположительную заявку, отрицательный сигнал, сигнал уменьшения номера режима,сигнал увеличения номера режима соответственно;
/> - индикаторсобытия />, равный 1, если /> происходит, и равный 0,если /> не происходит.
ВВЕДЕНИЕ
Важнымизадачами для развития современного общества являются сбор, обработка, хранениеи распространение информации. Передача информации представляет собой основу длярешения этих задач и потому требует тщательного изучения. Адекватное описаниепроцесса передачи информации с помощью математических моделей может бытьосуществлено в рамках теории массового обслуживания. При этом для многихреальных систем такой процесс моделируется посредством сетей массовогообслуживания. Например, к указанному результату приводит математическоемоделирование мультипрограммных вычислительных систем и анализ ихпроизводительности, проектирование и анализ сетей передачи данных и сетей ЭВМ.
Вначале XX века датский ученый А.К.Эрланг, работавший на копенгагенскойтелефонной станции, поставил и решил ряд новых математическтх задач,позволивших оценивать характеристики телефонных и телеграфных линий связи. Этоспособствовало возникновению нового направления в теории вероятностей — теориимассового обслуживания. На начальной стадии своего развития теория массовогообслуживания имела дело с системами массового обслуживания, которые описываютсяпотоками однородных заявок, поступающих в систему, процедурами обслуживания спомощью одного или нескольких каналов, процедурами формирования очередей испособами организации процесса ожидания заявок. Строгое научное описаниеслучайных процессов в теории массового обслуживания и их всестороннее исследованиевпервые было осуществлено А.Я.Хинчиным. Он исследовал одноканальную систему сожиданием, простейшим входным потоком и рекуррентным обслуживанием, установивдля нее так называемый основной закон стационарной очереди: стационарноераспределение числа заявок в системе совпадает с их стационарным распределениемв случайные моменты ухода заявок из системы. Большой вклад в развитие теориимассового обслуживания внесли Ю.К.Беляев, А.А.Боровков, Б.В.Гнеденко,Н.Джейсуолл, Дж.Р.Джексон, Ф.П.Келли, Дж.Кендалл, Дж.Ф.С.Кингмэн, Л.Клейнрок,Г.П.Климов, И.Н.Коваленко, С.Пальм, Ф.Поллачек, Ю.В.Прохоров, Дж.Риордан,Т.Саати, В.Л.Смит и др.
В1957г. Дж.Р.Джексон впервые ввел в рассмотрение понятие открытой сети массовогообслуживания ([99]), а в 1967г. Гордон и Ньюэлл ввели аналогичное понятиезамкнутой сети ([91]). В отличие от системы массового обслуживания сетьпредставляет собой более сложное образование, состоящее из систем массовогообслуживания, называемых узлами сети, которые взаимодействуют между собой спомощью некоторого вероятностного механизма. В открытых сетях заявки могутпоступать извне, а также уходить из сети. В замкнутых сетях сохраняетсяпостоянное число заявок, которые с помощью случайной маршрутизации могутперемещаться между узлами сети; при этом поступление заявок в сеть и уходзаявок из сети невозможны.
РезультатыДжексона и Гордона-Ньюэлла не использовались до тех пор, пока в 1971г. Ф.Р.Мур[115] не обнаружил, что замкнутые сети адекватно описывают вычислительныесистемы со многими ресурсами. С этого момента теория сетей обслуживания сталабыстро развиваться благодаря задачам, связанным с математическим моделированиеммультипрограммных вычислительных систем и анализом их производительности, спроектированием и анализом сетей передачи данных и сетей ЭВМ. Дополнительныйтолчок к дальнейшему развитию теории дала разработка и использование вповсеместной практике различных глобальных и локальных сетей таких, например,как EZERNET, INTERNET и т.д. Значительный вклад в развитие теории сетей внеслиГ.П.Башарин, А.А.Боровков, Э.Геленбе, Дж.Джексон, В.А.Ивницкий, Ф.П.Келли,Д.Кениг, Л.Клейнрок, Ю.В.Малинковский, М.Миязава, Б.Меламед, Р.Мюнтц,С.Е.М.Перс, П.К.Поллетт, А.Н.Рыбко, Р.Серфозо, Ю.М.Сухов, П.Тейлор,А.Л.Толмачев, Д.Тоусли, П.Уиттли, Дж.Уолрэнд, Г.И.Фалин, В.Хендерсон, Х.Чао,К.Ченди, Р.Шассбергер и многие другие.
Состояниесети массового обслуживания обычно характеризуется вектором, координатыкоторого описывают состояния отдельных узлов сети. В силу многомерностислучайного процесса состояний и статистической зависимости между координатамиисследование сетей массового обслуживания на порядок сложнее, чем исследованиесистем массового обслуживания. Даже в случае экспоненциальных сетей, когдаслучайный процесс состояний является марковским, его эргодическое стационарноераспределение удовлетворяет настолько сложной системе уравнений, что решить ееудается в основном только тогда, когда решение имеет форму произведеня.Множители в этом произведении зависят только от свойств индивидуальных узлов. Вимеющейся литературе по стационарному распределению экспоненциальных сетейпрактически не рассматриваются сети с ненадежными или частично ненадежнымиприборами. В считанных работах рассмотрены только очень частные вырожденныеслучаи и то для сетей, состоящих из двух узлов. В то же время в практическихситуациях оборудование может частично или полностью выходить из строя.Например, при работе на персональном компьютере очень часто нарушаютсяфункциональные связи между некоторыми файлами, программами или другими элементами,хотя компьютер продолжает работать. Налицо частичная потеря работоспособности,а значит, уменьшение интенсивности обслуживания.
Поэтомув данной работе предпринята попытка построения моделей, адекватно описывающихтакую ситуацию. Рассмотрены экспоненциальные сети с многорежимными стратегиямиобслуживания, в которых обслуживающие устройства в узлах частично ненадежны и вразличных режимах функционирования работают с разными интенсивностями. Длятаких сетей находится инвариантная вероятностная мера в мультипликативнойформе.
1. ОТКРЫТЫЕ СЕТИ С МНОГОРЕЖИМНЫМИСТРАТЕГИЯМИ ОБСЛУЖИВАНИЯ И ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ
Рассматриваетсяоткрытая сеть массового обслуживания с экспоненциальным обслуживанием в узлах имарковской маршрутизацией, в которую поступают два независимых между собойпуассоновских стационарных потока: обычных (положительных) заявок, требующихобслуживания в узлах, и так называемых отрицательных заявок, которые необслуживаются и могут удалять из узлов заявки (/>-сеть).Положительная заявка после обслуживания может с некоторой вероятностьютрансформироваться в отрицательную. Однолинейные узлы могут работать внескольких режимах, время переключения с одного режима на другой имеетпоказательное распределение с параметром, зависящим от состояния узла.Переключение происходит только на соседние режимы. Устанавливается условиеэргодичности и находится стационарное распределение состояний сети вмультипликативной форме.
Постановказадачи.
Вглаве 2 рассматривалась открытая сеть с многорежимными стратегиямиобслуживания, в которой приборы могут частично выходить из строя, работая приэтом в «щадящем» режиме. В 4.1 рассматривается аналогичная сеть приупрощающем предположении, состоящем в том, что интенсивности обслуживания вузле не зависят от его состояния. Однако добавляется возможность поступления всеть так называемых отрицательных заявок и возможность трансформированияобычных (положительных) заявок в отрицательные, что существенно усложняетзадачу, превращая, в частности, линейные уравнения трафика в нелинейные.
Всеть, состоящую из /> однолинейныхузлов, поступают два независимых стационарных пуассоновских потока:положительных заявок с параметром /> иотрицательных заявок с параметром />.Отрицательные заявки в отличие от обычных (положительных) заявок не требуютобслуживания, а поступление отрицательной заявки в узел уменьшает число заявокв нем на единицу, если число заявок в узле больше нуля, и не производит никакихизменений, если в узле нет заявок. После указанных операций отрицательныезаявки исчезают и в дальнейшем не оказывают влияния на сеть. Каждая заявкавходного потока положительных заявок независимо от других заявок с вероятностью/> направляется в />-й узел, а каждая заявкавходного потока отрицательных заявок независимо от других заявок с вероятностью/> направляется в />-й узел />. Положительная заявка,обслуженная в />-м узле, мгновеннонаправляется в />-й узел, свероятностью /> оставаясь положительной ис вероятностью /> превращаясь вотрицательную, или покидает сеть с вероятностью /> В/>-м узле находитсяединственный прибор, который может работать в /> режимах.Состояние />-го узла характеризуетсяпарой чисел />, где /> - число положительныхзаявок в />-м узле, /> - номер режима, в которомработает прибор в />-м узле />. Длительность обслуживанияприбором />-го узла положительныхзаявок имеет показательное распределение с параметром />. Назовем 0 основнымрежимом работы. Время пребывания в основном режиме работы имеет показательноераспределение с параметром />, послечего прибор переходит в режим 1. Для состояний />,у которых />, время пребывания в режиме/> также имеет показательноераспределение, при этом с интенсивностью /> прибор/>-го узла переходит в режим />, а с интенсивностью /> - в режим />. Время пребывания впоследнем />-м режиме имеетпоказательное распределение с параметром />,после чего прибор переходит в />-йрежим. Во время переключения прибора с одного режима работы на другой числозаявок в узле не меняется.
Состояниесети в момент времени /> будемхарактеризовать вектором />, где /> - состояние />-го узла в момент времени />. В соответствии свышесказанным здесь /> - числоположительных заявок в />-м узле в момент />, /> - номер режима работы />-го узла в момент />. Основная цель даннойработы — нахождение стационарного распределения марковского процесса />.
Предположим,что все величины /> строгоположительны. Обозначим через /> среднююинтенсивность поступления положительных заявок в />-йузел, а через /> среднююинтенсивность поступления отрицательных заявок в />-йузел. Эти интенсивности удовлетворяют следующей системе нелинейных уравненийтрафика:
/>
/>
Лемма1.1 [54, C.91]. Система уравнений (4.1.1), (4.1.2)имеет решение
/>.
Доказательство.Так как /> - непрерывная функция от /> и />, то доказательство следуетиз результата [90], полученного в этой работе с помощью теоремы Брауэра онеподвижной точке.
Вдальнейшем будем предполагать, что существует решение (4.1.1),(4.1.2), длякоторого все />. Для того, чтобыэто выполнялось, надо наложить некоторые условия на маршрутизацию заявок всети. Например, такое решение будет заведомо существовать, если при каждом /> выполняется условие />. На самом деле можноналожить гораздо менее жесткие условия. Всюду в дальнейшем под словами решение(4.1.1),(4.1.2) будет пониматься именно такое решение. Это предположениегарантирует неприводимость марковского процесса /> нафазовом пространстве />, где />.
Изолированныйузел в фиктивной окружающей среде.
Рассмотримизолированный />-й узел в фиктивнойокружающей среде, считая, что в него поступают два независимых пуассоновскихпотока: положительных заявок с параметром /> иотрицательных заявок с параметром />, где /> и /> найдены из системыуравнений трафика (4.1.1),(4.1.2). Окружающая среда является фиктивной потому,что в самой сети потоки заявок на ее узлы не являются простейшими. Необходимыми достаточным условием обратимости, а, значит, и квазиобратимостиизолированного узла является условие
/>
Действительно,модифицируя доказательство леммы 2.2, получаем, что при его выполнениипроизведение интенсивностей, ведущих из любого состояния в это же самоесостояние по ребрам элементарного квадрата по и против часовой стрелки совпадаютдля марковского процесса, описывающего такой изолированный узел. Условия(4.1.3) выполняются, в частности, если интенсивности переходов из одного режимав другой не зависят от состояния узла. Обозначая через /> финальные стационарныевероятности его состояний, запишем уравнения обратимости для изолированногоузла:
/>
/>
Изэтих уравнений легко определяются стационарные вероятности состоянийизолированного узла в фиктивной окружающей среде:
/>
где/>
и,как всегда, предполагается, что произведение, в котором нижний индекс большеверхнего, равно 1.
Согласноэргодической теореме Фостера [82] для эргодичности марковского процесса,описывающего изолированный узел в фиктивной окружающей среде, достаточносуществования нетривиального неотрицательного решения системы уравненийравновесия такого, что
/>
Если
/>
тов силу (4.1.6) ряд /> сходится каксумма геометрической прогрессии со знаменателем, меньшим единицы. Привыполнении условия
/>
интенсивностьвыхода из состояния /> ограничена:
/>
Поэтомупри выполнении условий
/>
сходитсяряд /> и по эргодической теоремеФостера марковский процесс, описывающий изолированный узел в фиктивнойокружающей среде эргодичен.
Основнойрезультат. Пусть /> - интенсивность переходапроцесса /> из состояния /> в состояние />, /> - интенсивность его выходаиз состояния />, /> - вектор />, у которого все /> кроме /> равны 0, а />, и все />, /> - вектор />, у которого все /> и все /> кроме /> равны 0, а />. Очевидно, интенсивности переходапроцесса /> имеют следующий вид:
/>
/>
/>
/>
/>
/>
длявсех иных состояний /> выполняется />.
Интенсивностьвыхода получается сложением этих интенсивностей:
/>
Основнойрезультат 4.1 состоит в следующем.
Теорема1.1. [54, C.92], [55, C.180] Если для всех /> выполняются условия(4.1.3) и неравенства (4.1.7), то марковский процесс /> эргодичен, а его финальноестационарное распределение имеет форму произведения
/>
где/> - стационарноераспределение изолированного />-го узлав фиктивной окружающей среде, определяемое с помощью соотношений (4.1.6).
Доказательство.Для доказательства того, что />,определенные в (4.1.15), образуют стационарное распределение марковскогопроцесса />, достаточно [94,97,103]подобрать функцию
/>
котораяудовлетворяла бы соотношениям
/>
и
/>
Еслитакие /> удастся найти (см.[94,97,103]), то окажется, что /> будутявляться инфинитезимальными интенсивностями перехода для обращенной во временицепи Маркова />, а /> - стационарнымивероятностями для /> и />. Положим
/>
/>
/>
/>
/>
/>
длявсех остальных состояний /> положим/>. Для функции /> соотношение (4.1.16)действительно выполняется, что легко проверяется подстановкой в него равенств(4.1.8)-(4.1.13), (4.1.18)-(4.1.23) и использования (4.1.4),(4.1.5). Остаетсядоказать (4.1.17). Складывая (4.1.18)-(4.1.23), получим, что
/>
/>
/>
/>
Используя(4.1.1)-(4.1.2), имеем
/>
/>
/>
Применяяснова (4.1.1)-(4.1.2), а также свойства индикаторов, получим
/>
/>
/>
/>
Сравниваяполученный результат с (4.1.14), делаем вывод, что /> длялюбого состояния />. Докажем, чтопри выполнении условий (4.1.7) марковский процесс /> эргодичен.Согласно эргодической теореме Фостера [82], для этого достаточно доказать, чтосуществует нетривиальное неотрицательное решение уравнений глобальногоравновесия
/>
такое,что ряд /> сходится. Складывая(4.1.16) по всем />, убеждаемся, что/> является решением(4.1.24). Из (4.1.14) следует, что
/>
Посколькуряд
/>
распадаетсяв произведение /> рядов, каждый изкоторых сходится в силу условия (4.1.7) как сумма бесконечной геометрическойпрогрессии со знаменателем, меньшим единицы, то и сам он сходится. В силу(4.1.25) будет сходиться ряд
/>
Поэргодической теореме Фостера это означает, что марковский процесс /> эргодичен. Таким образом,теорема доказана полностью.
Замечание4.1.Если условия (4.1.3) и (4.1.7) выполнены во всех узлах, то получается простойалгоритм для нахождения стационарных вероятностей:
1.Проверяется выполнение условий (4.1.3).
2.Решается система нелинейных уравнений (4.1.1)-(4.1.2).
3.Проверяется выполнение (4.1.7).
4.Определяются /> с помощью соотношений(4.1.6).
5.Находится стационарное распределение состояний сети /> спомощью формулы (4.1.15).
Этоталгоритм может быть дополнен алгоритмом расчета совместного стационарногораспределения чисел заявок в узлах и совместного стационарного распределенияномеров режимов работы узлов, а также расчета моментов этих распределений. Если/> - состояние сети, где />, то через /> обозначим вектор,характеризующий числа положитнльных заявок в узлах, а через /> - вектор, характеризующийрежимы работы в узлах. Стационарные распределения этих двух векторов обозначимсоответственно /> и />.
Нетрудноубедиться, складывая (4.1.15) по всем возможным значениям />, что совместноестационарное распределение чисел положительных заявок в узлах имеет следующуюформу:
/>
гдекаждый множитель имеет геометрическое распределение
/>
Производящаяфункция стационарного распределения числа заявок в />-музле имеет вид
/>
а/>-й факториальный моментесть
/>
Каки следовало ожидать, в стационарном режиме среднее число положительных заявок идисперсия числа положительных заявок в каждом узле,
/>
стремятсяк нулю, когда загрузка этого узла
/>
Точнотак же, складывая (4.1.15) по всем возможным значениям />, определим совместноестационарное распределение режимов в узлах сети:
/>
где/>
Среднийномер режима работы />-го узла встационарной сети находится как
/>
Анализхарактера выходящих потоков из сети провести крайне трудно, так как эти потокиявляются сложными благодаря воздействию отрицательных заявок и из-занелинейности уравнений трафика. 2. ОТКРЫТЫЕ СЕТИ С МНОГОРЕЖИМНЫМИСТРАТЕГИЯМИ ОБСЛУЖИВАНИЯ И ИНФОРМАЦИОННЫМИ СИГНАЛАМИ ДВУХ ТИПОВ
В1 исследовалось стационарное распределение марковского процесса, описывающегооткрытую сеть с многорежимными стратегиями обслуживания и отрицательнымизаявками. Здесь мы рассмотрим открытую сеть массового обслуживания, в которуюнаряду с отрицательными заявками, называемыми в дальнейшем отрицательнымисигналами, поступает еще один вид информационных сигналов, изменяющих режимфункционирования обслуживающих устройств в узлах.
Нафазовом пространстве /> заданмногомерный марковский процесс />, где />, своими инфинитезимальнымиинтенсивностями перехода: для />
/>
/>
/>
/>
/>
/>
длявсех других состояний /> предполагается,что />. Интенсивность выходаполучается сложением этих интенсивностей:
/>
/>
Этотпроцесс описывает сеть, состоящую из /> однолинейныхузлов, в которую поступают четыре независимых стационарных пуассоновскихпотока: положительных заявок с параметром />,отрицательных сигналов с параметром />,сигналов уменьшения режима с параметром />,сигналов увеличения режима с параметром />.Поступление отрицательного сигнала в узел уменьшает число заявок в нем наединицу, если число заявок в узле больше нуля, и не производит никаких изменений,если в узле нет заявок. Сигнал уменьшения режима при поступлении в />-й узел с режимом /> переводит его в режимработы />, не изменяя числа заявок вузле, и не производит никаких изменений, если узел находится в режиме работы 0;сигнал увеличения режима при поступлении в />-йузел с режимом /> переводит его врежим работы />, не изменяя числа заявок вузле, и не производит никаких изменений, если узел находится в режиме работы />. После этих операцийинформационные сигналы пропадают, не оказывая более влияния на сеть.Поступающие положительная заявка, отрицательный сигнал, сигнал уменьшения исигнал увеличения режима направляются в />-йузел соответственно с вероятностями />.Положительная заявка, обслуженная в />-м узле,мгновенно направляется в />-й узел,с вероятностью /> оставаясьположительной, с вероятностью /> превращаясьв отрицательный сигнал, с вероятностью /> -в сигнал понижения режима, с вероятностью /> -в сигнал повышения режима, или с вероятностью /> покидаетсеть />. Длительность обслуживанияприбором />-го узла положительныхзаявок имеет показательное распределение с параметром />. Режимы работы иинтенсивности перехода с режима на режим определяются как в предыдущем разделе.Состояние сети в момент времени /> описываетсятак же, только теперь /> - числоположительных заявок в />-м узле в момент />.
Предположим,что все величины /> положительны.Пусть /> - средние интенсивностипоступления в />-й узел положительныхзаявок, отрицательных сигналов, сигналов понижения и повышения режимовсоответственно, удовлетворяющие системе нелинейных уравнений трафика:
/>
/>
/>
/>
Уравнения(4.2.3) имеют решение. Действительно, первые два уравнения в (4.2.3) совпадаютс уравнениями трафика (4.1.1),(1.1.2), которые имеют решение />. Очевидно, по найденным /> из третьего и четвертогоуравнений (4.2.3) однозначно определятся />.
Рассмотримизолированный />-й узел в фиктивнойокружающей среде, считая, что в него поступают четыре независимых пуассоновскихпотока: положительных заявок с параметром />,отрицательных сигналов с параметром />,сигналов уменьшения режима с параметром /> исигналов увеличения режима с параметром />.Необходимым и достаточным условием обратимости, а, значит, и квазиобратимостиизолированного узла является условие
/>
чтопроверяется с помощью простой модификации доказательства леммы 2.2. Заметим,что это условие заведомо выполняется, когда интенсивности переходов с режима нарежим /> не зависят от состоянияузла. Уравнения обратимости для изолированного узла имеют вид:
/>
/>
/>
Изуравнений (4.2.5) находим
/>
Полагаяв (4.2.6) /> и заменяя /> на />, получим:
/>
откуда
/>
Подставляяэто в (4.2.7), имеем:
/>
Изусловия нормировки находим, что
/>
/>
Всилу теоремы Фостера [82] для эргодичности изолированного узла достаточновыполнения неравенств
/>
Доказательстводословно повторяет то, которое использовалось при доказательстве аналогичногоутверждения в 4.1.2, с заменой оценки для /> следующейоценкой:
/>
Отметимто обстоятельство, что вторая часть (4.2.10) заведомо имеет место, когдаинтенсивности переходов с режима на режим не зависят от состояния узла. Заметимтакже, что второе неравенство в (4.2.10) гарантирует регулярность марковскогопроцесса, описывающего изолированный узел в фиктивной окружающей среде. Этоозначает, что за конечное время процесс не может сделать бесконечное числопереходов из одного состояния в другое (моменты скачков процесса не могут иметьконечной предельной точки).
Теорема2.2. [45, C.186]/> Еслидля всех /> выполняются условия(4.2.4) и (4.2.10), то марковский процесс /> эргодичен,а его стационарное распределение имеет форму произведения (4.1.15), где /> определяются с помощьюсоотношений (4.2.8),(4.2.9).
Доказательство.Для доказательства того, что />,определенные в (4.1.15),(4.2.5),(4.2.6), образуют стационарное распределениемарковского процесса />, достаточно[94,97,103] подобрать функцию /> котораяудовлетворяла бы соотношениям
/>
/>
Еслитакие /> удастся найти (см.[94,97,103]), то окажется, что /> будутявляться инфинитезимальными интенсивностями перехода для обращенной во временицепи Маркова />, а /> - стационарнымивероятностями для /> и />. Положим
/>
/>
/>
/>
/>
/>
/>
/>
/>
длявсех остальных состояний /> положим/>. Для функции /> (4.2.11) действительновыполняется, что легко проверяется подстановкой в него равенств(4.2.1),(4.2.13) и использования (4.2.8),(4.2.9). Остается доказать (4.2.12).Складывая (4.2.13), получим, что
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
Используя(4.2.3), имеем
/>
/>
/>
/>
Применяяснова (4.2.3), свойства индикаторов и тот факт, что />,получим
/>
/>
/>
/>
/>
/>
/>
Сравниваяполученный результат с (4.2.2), делаем вывод, что /> длялюбого состояния />.
Докажем,что при выполнении условий (4.2.10) марковский процесс /> эргодичен. Согласноэргодической теореме Фостера [82], для этого достаточно доказать, чтосуществует нетривиальное неотрицательное решение уравнений глобальногоравновесия
/>
такое,что ряд /> сходится. Складывая(4.2.11) по всем />, убеждаемся, что/> является решением(4.2.14). Из (4.2.2) следует, что
/>
Посколькуряд
/>
распадаетсяв произведение /> рядов, каждый изкоторых сходится в силу условия (4.2.10) как сумма бесконечной геометрическойпрогрессии со знаменателем, меньшим единицы, то и сам он сходится. В силу (4.2.15)будет сходиться ряд
/>
Поэргодической теореме Фостера это означает, что марковский процесс /> эргодичен. Таким образом,теорема доказана полностью.
Замечание4.2.Если условия (4.2.4) и (4.2.10) выполнены во всех узлах, то получаетсяследующий алгоритм для нахождения стационарных вероятностей:
1.Проверяется выполнение условий (4.2.4).
2.Решается система нелинейных уравнений (4.2.3).
3.Проверяется выполнение (4.2.10).
4.Определяются /> с помощью соотношений(4.2.8), (4.2.9).
5.Находится стационарное распределение состояний сети /> спомощью формулы (4.1.15).
Этоталгоритм также может быть дополнен алгоритмом расчета совместного стационарногораспределения чисел заявок в узлах и совместного стационарного распределенияномеров режимов работы узлов, а также расчета моментов этих распределений.
Если/> - состояние сети, где />, то через /> обозначим вектор,характеризующий числа положитнльных заявок в узлах, а через /> - вектор, характеризующийрежимы работы в узлах. Стационарные распределения этих двух векторов обозначимсоответственно /> и />.
Нетрудноубедиться, складывая (4.1.15) по всем возможным значениям />, что совместноестационарное распределение чисел положительных заявок в узлах имеет следующую форму:
/>
гдекаждый множитель имеет геометрическое распределение
/>
Производящаяфункция стационарного распределения числа заявок в />-музле имеет вид
/>
а/>-й факториальный моментесть
/>
Каки следовало ожидать, в стационарном режиме среднее число положительных заявок идисперсия числа положительных заявок в каждом узле,
/>
стремятсяк нулю, когда загрузка этого узла
/>
Точнотак же, складывая (4.1.15) по всем возможным значениям />, определим совместноестационарное распределение режимов в узлах сети:
/>
где/>
Среднийномер режима работы />-го узла встационарной сети находится как
/>
Анализвыходящих из сети потоков положительных заявок не проводился, поскольку, как ив предыдущем подразделе, такие потоки носят сложный характер из-за нелинейностиуравнений трафика.
ЗАКЛЮЧЕНИЕ
Вработе рассмотрена открытая сеть массового обслуживания с многорежимнымистратегиями обслуживания, в которую наряду с обычными, положительными заявкамипоступают пуассоновские потоки информационных сигналов, оказывающих разовоевоздействие на соответствующий узел сети. Интенсивность обслуживания приборомузла зависит от номера узла, но не зависит от его состояния. Предполагалось,что при помещении изолированного узла в фиктивную окружающую среду,характеризующуюся поступлением в него пуассоновских независимых потоковположительных заявок и информационных сигналов каждого типа, узел описываетсяобратимым марковским процессом с непрерывным временем и счетным пространствомсостояний. Положительная заявка после обслуживания в некотором узле можетостаться положительной, а может превратиться в информационный сигнал любого израссматриваемых типов. Рассмотрены два случая: а)кроме положительных заявок всеть могут поступать отрицательные заявки; б)кроме положительных заявок в сетьмогут поступать отрицательные сигналы, сигналы умньшения и сигналы увеличенияномера режима на единицу.
Дляобоих случаев составлены нелинейные уравнения трафика и доказано существованиеих решения, установлены достаточные условия эргодичности марковского процесса,характеризующего состояния рассматриваемых открытых сетей, и в аналитическойформе найдено финальное стационарное распределение состояний этого процесса.Построен алгоритм для расчета стационарных вероятностей состояний сети.
СПИСОК ИСПОЛЬЗОВАННЫХИСТОЧНИКОВ
1.Анисимов B.B., Лебедев Е.А. Стохастические сети обслуживания. Марковские модели.- Киев: Лыбидь, 1992. — 205 с.
2.Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях.- М.: Наука. — 1989. — 336с.
3.Башарин Г.П., Толмачев А.Л. Некоторые результаты теории сетей массовогообслуживания // Методы развития теории телетрафика. — М. — 1970. — С.52-65.
4.Башарин Г.П., Толмачев А.Л. Теория сетей массового обслуживания и ее приложенияк анализу информационно-вычислительных систем // Итоги науки и техники. — М.,1983. — Т.21. — С.3-119. — (Сер. Теория вероятностей. Матем. статистика. Теор.кибернетика / ВИНИТИ).
5.Бочаров П.П., Печинкин А.В. Теория массового обслуживания: Учебник. — М.: РУДН,1995. — 529с.
6.Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. — М.: Наука,1977. — 568с.
7.Горцев А.М., Назаров А.А., Терпугов А.Ф. Управление и адаптация в системахмассового обслуживания. — Томск: ТГУ, 1978. — 208с.
8.Добрушин Р.Л., Кельберт М.Я., Рыбко А.Н., Сухов Ю.М. Качественные методы теориисетей с очередями // Препринт. -М., 1986. — 50с. — (ИППИ АН СССР).
9.Евдокимович В.Е., Малинковский Ю.В. Сети массового обслуживания с динамическоймаршрутизацией и динамическими вероятностными обходами узлов заявками //Проблемы передачи информации. — 2001. — Том 37, вып.3. — С.55-66.
10.Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория иприменение к сетям ЭВМ. — М.: Радио и связь. — 1988. — 192с.
11.Ивницкий В.А. Сети массового обслуживания и их применение в ЭВМ // Зарубежнаярадиоэлектроника. — 1977. — №7. — С.33-70.
12.Ивницкий В.А. Об условии независимости стационарных вероятностей состоянийразомкнутой сети однолинейных систем с потерями от вида распределенийдлительностей обслуживания // Известия АН СССР. Техническая кибернетика. — 1981. — №4. — С.136-140.
13.Ивницкий В.А. Об условии инвариантности стационарных вероятностей для сетеймассового обслуживания // Теория вероятностей и ее применения. — 1982. — Т. 27,№ 1. — С.188-192.
14.Ивницкий В.А. Об инвариантности стационарных вероятностей состояний длязамкнутых сетей однолинейных СМО // ДАН УССР. А. — 1989. — №7. — С.8-11.
15.Ивницкий В.А. Об условии инвариантности стационарных вероятностей состояний длясетей однолинейных СМО // Теория вероятностей и ее применения. — 1989. — Т. 34,№ 3. — С.576-580.
16.Ивницкий В.А. Об инвариантности стационарных вероятностей состояний для сетеймноголинейных систем массового обслуживания с абсолютным приоритетомпоступающего требования и дообслуживанием // Исследование систем и сетеймассового обслуживания: Тез. докл. 12-й Бел. зимней школы-семинара по ТМО,Гродно, янв.-февр. 1996 г. / Бел. гос. унив. — Минск, 1996. — С.36-37.
17.Кельберт М.Я., Сухов Ю.М. Математические вопросы теории сетей с очередями //Итоги науки и техники. — М., 1988. — Т.26. — С.3-96. — (Сер. Теориявероятностей. Матем. статистика. Теор. кибернетика / ВИНИТИ).
18.Кениг Д., Рыков В.В., Шмидт Ф. Стационарные системы массового обслуживания сзависимостями // Итоги науки и техники. — М., 1981. — Т.18. — С.95-186. — (Сер.Теория вероятностей. Матем. статистика. Теор. кибернетика / ВИНИТИ).
19.Клейнрок Л. Коммуникационные сети. — М.: Наука, 1970. — 255с.
20.Клейнрок Л. Вычислительные системы с очередями. — М.: Мир, 1979. — 600с.
21.Климов Г.П. Стохастические системы обслуживания. — М.: Наука, 1966. — 243с.
22.Ковалев Е.А. Сети с ненадежными каналами и резервом//Математические методыисследования сетей связи и сетей ЭВМ. Тезисы докладов VI Белорусскойшколы-семинара по ТМО. — Минск,1990. — С.70-71.