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

УДК 681.3

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

С. И. Макаренко,

канд. техн. наук, преподаватель М. А. Татарков,

инженер

Военно-космическая академия им. А. Ф. Можайского, г. Санкт-Петербург

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

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

Введение

Реальные информационные потоки, передаваемые по информационным вычислительным сетям (ИВС), имеют более сложную структуру (например, обладают свойствами нестационарности, самоподобия и др.), чем используемые в моделях ИВС потоки со стационарными свойствами. Отсутствие учета нестационарности (варьирование в широких пределах интенсивности) входного потока в моделях каналов связи (КС) ведет к существенным погрешностям в определении характеристик качества обслуживания (QoS — Quality of Service) таких ИВС. Это в дальнейшем влияет на качество функционирования автоматизированных систем управления реального времени, в составе которых функционируют данные ИВС [1].

Ранее авторами была предложена обобщенная модель для расчета QoS сети связи (СС), моделируемой системой массового обслуживания (СМО), в случае если на вход системы поступает дважды стохастический поток заявок [2]. Частные решения данной модели были использованы при вычислении QoS проводного канала связи (КС) [3] и спутниковой сети с доступом по типу S-ALOHA

[4]. Результатом применения обобщенного подхода [2] для вычисления параметров сети радиосвязи (СРС) с доступом абонентов по типу CSMA [5] явился вывод о невозможности аналитического

вычисления характеристик QoS. При оценке QoS для СРС со случайным множественным доступом с проверкой несущей частоты (МДПН) целесообразно использовать статистическое или численное моделирование. Таким образом, настоящая работа дополняет аналитическое решение

[5] и позволяет качественно оценить QoS СРС с МДПН при поступлении на вход СРС нестационарного информационного потока.

Моделирование нестационарного информационного потока сложной псевдослучайной тригонометрической функцией

Для моделирования СРС с МДПН предлагается использовать модель СМО, предложенную в работе [6]. СРС имеет синхронизацию по тактам, причем на длительности такта £т ведет информационный обмен один активный абонент. Пусть интенсивность X* реального входного в СРС трафика имеет сложную природу, меняется независимо при переходе от такта к такту, причем заранее неизвестно, какое значение примет данная интенсивность X* в каждый i-й такт, однако заданы границы изменения интенсивности потока от каждого абонента для каждого такта (рис. 1).

Интенсивность потока в этом случае необходимо моделировать аналитической функцией, удовлетворяющей следующим требованиям:

h

0

t0tl ... h •••

Рис. 1. Интенсивность информационного потока X* и потока, задаваемого ПСТФ Xj

— вид функции должен соответствовать реальному изменению интенсивности информационных потоков в СРС;

— вероятностные характеристики должны быть равны вероятностным характеристикам реальных информационных потоков от абонентов СРС;

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

Для описания входного в СМО потока с изменяющейся нестационарной интенсивностью предлагается использовать сложную псевдослучайную тригонометрическую функцию (ПСТФ) интенсивности входного потока у на Ь-м такте от у-го абонента, удовлетворяющую вышеуказанным требованиям:

А Іі = тАІ +-21 sin( it + п Cos(tiWji ))Х in (tiWji)) ,

: cos^t + n sin W. = Q і + sin (kQ t

где т^ — математическое ожидание интенсивности исходящего информационного потока у-го абонента; ст^ — дисперсия интенсивности реального информационного потока у-го абонента; Юу — частота ПСТФ у-го абонента; Оу, ку подбирают эмпирическим путем, исходя из наибольшего соответствия ПСТФ реальному информационному потоку от у-го абонента.

Параметры тХу и ст|у могут быть вычислены априорно по анализу больших реализаций X* на интервале активной передачи абонента Ту:

^^ Е 4; ст2=^ Е

rp Z______У J1 /ЪУ гп

1 ІЄТ 11 ІЄТ

] ]

Если на основании проверки по критерию Колмогорова возможно выдвинуть гипотезу о нор-

мальном распределении случайных флуктуаций

*

интенсивности А*:

тА1 » 2 (^i'rnax, l ^i'min, l); ''

,!(А* -а*

' g \ 1 max, l лі min, l

Параметры Qj, kj в (1) определяют исходя из соответствия ПСТФ j реальному информационному потоку X* от j-го абонента по критерию Пирсона при заданной доверительной вероятности.

Предполагается, что на длительности i-го такта информационного обмена j-й абонент генерирует стационарный пуассоновский поток с интенсивностью Xjj. При переходе к следующему i + 1 такту интенсивность пакетов от j-го абонента меняется в соответствии с ПСТФ на Xj + 1. Это позволяет сгенерировать нестационарный поток пакетов, для которого в общем случае на всем интервале информационного обмена Tj выполняется свойство ординарности и отсутствия последействия. Вероятности поступления m пакетов на i-м такте за время т (t; < т < tt + 1) будут распределены по закону Пуассона [7]:

(Xпт)т -Х..т

Pji(m, т) = ^-'—е - , т е [t.

і, ti+l),

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

В этом случае для известной СМО с у входными потоками, при стационарной интенсивности обслуживания д, вероятности нахождения системы в том или ином состоянии (количество заявок в системе I) длительности каждого такта будут зависеть от суммы интенсивностей ХуЬ и, так как сохраняется свойство отсутствия последействия (свойство марковского процесса), будут определяться системой уравнений Колмогорова [7] с вероятностями р0, ..., р1 нахождения в системе соответственно 0, ..., I заявок:

d^>oг

dt dPli (К

= MPli

= MP2i (t) + ^nst iPOi (t)-

dt

-

dPki

dt

M-pk+l, i

dPli (t

dt

= ^nst iPl-l, i W- MPl, i W

Е Pki (t)=l

k=0

^nst i =Е А1

Данное представление позволяет решить вышеуказанную систему относительно р0, ..., р1 для каждого Ь-го такта, после чего по известным методам [7] вычислить характеристики обслуживания заявок в СМО (время нахождения в очереди, время обслуживания в системе, относительную пропускную способность системы). Предложенный подход существенно упрощает задачу анализа характеристик СМО, так как характеристика интенсивности Хп^ Ь не зависит от времени в течение длительности такта, а задача вычисления характеристик вышеуказанной системы при произвольных законах распределения Ху^) практически не может быть решена в аналитическом виде [7]. Вместе с тем при представлении интенсивности в виде ПСТФ необходимо дополнительно оценить «шумы квантования» для выражений (1) и (2) либо использовать в (1) частоты в соответствии с частотой квантования Котельникова.

Использование при моделировании предложенной ПСТФ для описания нестационарного потока отличает данную работу от аналогов, где для упрощенного описания нестационарного потока требований в СМО используется поток второго порядка стохастичности [2-5], интервальные стационарные функции [8] или аппроксимация интенсивности интервально-линейными функциями [9].

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

При моделировании обслуживания СРС с МДПН входного нестационарного потока нескольких абонентов за основу была взята модель из работы [6]. Пусть в системе имеется у абонентов, каждый из которых на протяжении независимого времени Ту активен и ведет информационный обмен по СРС. Обмен ведется в режиме разделения канала обслуживания во времени, по тактам длительностью ^ (размер окна передачи, соответствующий времени передачи одного абонента). В начале каждого такта абоненты пытаются получить доступ к КС; если КС свободен, то абонент осуществляет передачу длительностью tт. В случае занятости КС абонент откладывает свою передачу до следующего такта в соответствии со случайным распределением задержки повторной передачи. Когда наступает это время, абонент вновь проверяет КС и повторяет описанный алгоритм.

Введем обозначения: С — пропускная способность КС; 5 — относительная пропускная способность СРС; G — число попыток передач пакетов

G(t) за длительность такта ^; Gу — вероятность, что у-й абонент передаст пакет за длительность данного такта ^; Тз — среднее время задержки пакета в системе, за которое пакет будет успешно передан и принят; К — задержка повторной передачи в количестве тактов, равномерно распределенная со средним значением К единиц на такт; с — скорость света; Dmes — объем пакета, бит; йтах — радиус СРС, км.

Ограничения модели [6]: канал является бесшумным; все абоненты находятся в пределах прямой видимости; канал для передачи квитанций отделен от рассматриваемого КС и предполагается, что квитанции о доставке прибывают надежно и без затрат; рассматриваемая модель действительна при наличии большого числа «равномерно интенсивных» пользователей.

Используем модель СРС в виде СМО (рис. 2), для упрощения рассмотрим случай, когда у = 4. Каждый абонент генерирует поток пакетов с интенсивностью ХуЬ, причем интенсивность на Ь-м такте определяется выражением (1). Абоненты вступают в информационный обмен поочередно в моменты времени t1, t2, t3, t4 и завершают его в момент t5 (рис. 3). Суммарная интенсивность пакетов, поступающих в систему, для данной модели определяется суммой

4

Х ^

j=1

Поток с нестационарной интенсивностью \В$Ь) существенно отличается от потока со стационарной интенсивностью ХВ$Ь), который, как

Рис. 2. Модель обслуживания СРС с МДПН нестационарных информационных потоков

правило, используется при моделировании СРС с МДПН и в данной модели определяется как

4

^

j=1

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

ДХ

АХ^ < АХ2 < АХ3 < АХ4.

Дисперсионная характеристика нестационарного потока Хпз1-(^) существенно возрастает при росте количества абонентов. Так как качество обслуживания СРС с МДПН зависит от характеристик входного потока, возникает систематическая ошибка между результатами по качеству обслуживания СРС потока с интенсивностью Х^^), представляемой ПСТФ, и моделью, в которой качество обслуживания рассчитывается как функция от стационарной интенсивности Х^^.

Произведем расчет значений показателей качества обслуживания для модели СРС с МДПН

[6] с учетом того, что на вход системы с пропускной способностью С поступает поток с интенсивностью, определяемой выражениями (1) и (5). Рассмотрим число попыток передач пакетов G(t) за длительность такта ^. В соответствии с [6] данный параметр определяется как

ЧгХ^

в (п )=

Dm

Результаты аналитического моделирования (рис. 4) показывают, что при использовании потока с интенсивностью, представленной ПСТФ, существенно возрастает максимально необходимое число попыток передач пакета Gnst тах^). При сравнении с результатами Gst(t) для модели стационарного пуассоновского потока с ростом количества абонентов, участвующих в информационном обмене, на ДG(t) возрастает число попыток передач пакета. Проведенный анализ показывает, что рост ДG(t) пропорционален росту дисперсионной характеристики Хпз1_(^) и количеству абонентов у. При этом снижается минимальная вероятность передачи пакета с первой попытки Р1 nst max(t) на АР^) по сравнению со стационарным потоком, что ведет к увеличению пакетов, требующих повторной передачи, и, соответственно, росту загруженности СРС.

Рис. 3. Частные и суммарная интенсивности стационарного Ха1.(^) и нестационарного Хпа1.(^) потоков пакетов в систему

о

р^)

0 і

І2

Із

і4

І5

Рис. 4. Моделирование числа попыток передач пакета 0{Ь) и вероятности передачи пакета Р](0 при входных стационарном и нестационарном потоках

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

Се

S(ti) =

— dmaxXnst

^ п )е

•

Xnst

1 + 2

^тахС

cDm

— dmaxXnst

+ Се cDmes

Время задержки Тз при передаче пакета в СРС с МДПН определяется выражением [6]

Т ___ Dmes

X Xnst (Пі ) 1 2 <ахС + 1 + к Н С І і | Чтах0

& о cDmes сВ ^'"tymes .

•

Результаты аналитического моделирования по выражениям (9) и (10) с учетом (1) и (4), представленные на рис. 5, показывают, что при ис-

Се

0 и

и

и

и

-—>

и

Рис. 5. Моделирование эффективной пропускной способности СРС Се(?) и времени задержки передачи пакета Тз(Ь) при входных стационарном и нестационарном потоках

пользовании потока с нестационарной интенсивностью, представленной ПСТФ, расчетная эффективная пропускная способность Се nst(t) существенно снижается с ростом количества участников информационного обмена (на значение ДСе(^) по сравнению со значением пропускной способности, рассчитанным для стационарного пуассонов-ского потока. Соответственно, со снижением пропускной способности возрастает задержка в доставке пакетов по СРС с Тз в1ДО до Тз nSt(t). Увеличение АCe(t) и АТз(t) пропорционально дисперсионной характеристике Хпз1_(^) и увеличению количества абонентов у. Проведенный анализ показал, что при моделировании стандартных информационных потоков сетей специального назначения отклонение эффективной пропускной способности АСе^) достигает относительных значений порядка 10-30 % от Се з1^), а АТз(?) — до 50-80 % от Тз gt(t). Порядок данных величин позволяет сделать вывод о необходимости учета нестационар-ности информационных потоков в системах связи специального назначения и систем управления реального времени.

Предложения по обработке нестационарных информационных потоков в системах связи

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

Таким образом, снижение QoS в результате обслуживания нестационарного потока требует введения новых способов обработки и передачи пакетов в СРС. В работе [9] автором было предложено динамически перераспределять пропускную способность логических соединений в пользу абонентов с высокими требованиями по QoS. Однако такое перераспределение невозможно в случае, если требования по QoS превышают общие возможности СРС по пропускной способности. Для компенсации данного недостатка предлагается для системы связи, состоящей из нескольких высоконагруженных СРС, ввести дополнительную СРС, функционирующую в режиме «горячего резерва» и параллельно включаемую для тех СРС, в которых обслуживание общей интенсивности нестационарных потоков приведет к снижению QoS ниже заданного (рис. 6).

Рис. 6. Использование дополнительной СРС для обслуживания нестационарных информационных потоков

Заключение

В данной работе рассмотрено обслуживание нестационарных потоков в СРС с CSMA методом доступа абонентов. Полученные результаты дополняют работы автора [2-5], в частности позволяют методами статистического моделирования оценить качество обслуживания для СМО, аналитическое решение для которых невозможно

[5]. Предложенное представление нестационарного информационного потока в виде дискретного пуассоновского потока с интенсивностью, представленной ПСТФ, и выполненный расчет качества обслуживания ИВС отличаются от существующих подходов. В современных работах по расчету ИВС с нестационарными информационными потоками сложной структуры большое распространение получили методы диффузной аппроксимации [10-13]. Так, в работе Н. И. Головко [11] для учета нестационарности предложено использовать аппроксимацию нестационарного потока дважды стохастическим потоком с диффузионной интенсивностью. В работах Н. Ф. Ба-харевой [12] и К. И. Сычева [13] предложена аппроксимация интервалов времени между пакетами для непуассоновских потоков и оценка предельных границ характеристик качества обслуживания ИВС в условиях предложенной аппроксимации. Вместе с тем, как отмечается в работе Ю. И. Рыжикова [14], при такой аппроксимации ошибки в аналитическом расчете качества обслуживания растут пропорционально усложнению структуры аппроксимируемого потока. Существенные погрешности имеют место при расчете качества обслуживания многоканальных приоритетных [15] систем обслуживания или систем со сложной процедурой обработки информационных потоков (например, при групповом [16] или случайном [17] обслуживании пакетов). Предложенный способ учета нестационарности информационных потоков может быть сравним с аппроксимацией информационных потоков гипер-экспоненциальным [18] или Кокса [19] распределениями, однако в сравнении с указанными распределениями может иметь ПСТФ параметра распределения и невысокую вычислительную сложность расчета качества обслуживания. Методом имитационно-аналитического моделирования в работе получены качественные результаты оценки QoS при обслуживании СРС с МДПН потока предлагаемого вида. Кроме того, предложены рекомендации по обслуживанию нестационарных потоков в интересах повышения надежности (по показателю отказ в обслуживании) и пропускной способности системы связи, отличающиеся от аналога [9] тем, что используется СРС «горячего резерва».

Литература

1. Макаренко С. И. Обоснование актуальности исследования вопросов передачи нестационарных информационных потоков по сетям связи, находящихся под воздействием средств радиоэлектронной борьбы // Инновации в авиационных комплексах и системах военного назначения: сб. докл. Всерос. НТК / ВАИУ. Воронеж, 2009. Т. 10. С. 117-122.

2. Макаренко С. И. Методика вероятностной оценки показателей качества обслуживания сети связи при передаче нестационарных информационных потоков // Успехи современной радиоэлектроники. 2010. № 11. С. 78-81.

3. Макаренко С. И. Методика оценки времени задержки пакета в канале связи в условиях нестабильности входного трафика // Инфокоммуника-ционные технологии. 2007. Т. 5. № 3. С. 94-96.

4. Макаренко С. И., Кихтенко А. В. Методика оценки времени задержки пакета в спутниковой сети связи в условиях нестабильности входного трафика // Системы управления и информационные технологии. 2007. № 1.3 (27). С. 344-348.

5. Макаренко С. И., Сидорчук В. П., Краснокут-ский А. В. Методика оценки времени задержки пакета в сети воздушной радиосвязи в условиях нестабильности входного трафика // Физика волновых процессов и радиотехнические системы. 2007. Т. 10. № 6. С. 70-74.

6. Клейнрок Л. Вычислительные сети с очередями: пер с англ. — М.: Мир, 1979. — 600 с.

7. Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988. — 208 с.

8. Баканов М. И., Степанов В. Г. Информационные технологии контроля качества функционирования систем обслуживания в торговле // Аудит и финансовый анализ. 2000. № 4. http://www.cfin. ru/press/afa/2000-4/52_bak.shtml. (дата обращения: 19.12.2011).

9. Макаренко С. И. Адаптивное управление скоростями логических соединений в канале радиосвязи

множественного доступа // Информационно-управ-ляющие системы. 2008. № 6. С. 54-58.

10. Ададуров С. Е., Мальцев Г. Н., Моторин Н. М., Ада-дуров А. С. Диффузионная аппроксимация процессов информационного обмена в низкоорбитальных спутниковых радиосетях // Информационно-управ-ляющие системы. 2006. № 4. С. 40-44.

11. Головко Н. И. Исследование моделей систем массового обслуживания в информационных сетях: дисс. ... д-ра техн. наук: 05.13.18. — Владивосток: Тихоокеанский ГЭУ, 2007. — 404 с.

12. Бахарева Н. Ф. Аппроксимативные методы и модели массового обслуживания для исследования компьютерных сетей: дисс. ... д-ра техн. наук: 05.13.15. — Пенза: Поволжский ГУТИ, 2011. — 360 с.

13. Назаров А. Н., Сычев К. И. Модели и методы расчета показателей качества функционирования узлового оборудования и структурно-сетевых параметров сетей связи следующего поколения. — Красноярск: Поликом,2010. — 389 с.

14. Рыжиков Ю. И., Уланов А. В. Опыт расчета сложных систем массового обслуживания // Информа-ционно-управляющие системы. 2009. № 2. С. 56-62.

15. Рыжиков Ю. И. Средние времена ожидания и пребывания в многоканальных приоритетных системах // Информационно-управляющие системы. 2006. № 6. С. 43-49.

16. Рыжиков Ю. И. Расчет систем обслуживания с групповым поступлением заявок // Информаци-онно-управляющие системы. 2007. № 2. С. 39-49.

17. Рыжиков Ю. И. Расчет систем со случайным выбором на обслуживание // Информационно-управля-ющие системы. 2007. № 3. С. 56-59.

18. Алиев Т. И. Основы моделирования дискретных систем. — СПб.: СПб ГИТМО (ТУ), 2009. — 363 с.

19. Рыжиков Ю. И. Полный расчет системы обслуживания с распределениями Кокса // Информацион-но-управляющие системы. 2006. № 2. С. 38-46.