Оценка вероятности пересечения заявок сложной структуры в системах обслуживания
Отримано оцінки для спрощення розрахунків, пов’язаних з перетином випадкових заявок, що складаються з декількох часових інтервалів. Використано аналітичні прийоми та статистичне моделювання. Результати можуть використовуватися при проектуванні комунікаційних систем. Estimates are derived towards sim...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2010 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45208 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оценка вероятности пересечения заявок сложной структуры в системах обслуживания / Е.В. Коба, О.Н. Дышлюк // Кибернетика и системный анализ. — 2010. — № 3. — С. 175-180. — Бібліогр.: 4 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860133606436896768 |
|---|---|
| author | Коба, Е.В. Дышлюк, О.Н. |
| author_facet | Коба, Е.В. Дышлюк, О.Н. |
| citation_txt | Оценка вероятности пересечения заявок сложной структуры в системах обслуживания / Е.В. Коба, О.Н. Дышлюк // Кибернетика и системный анализ. — 2010. — № 3. — С. 175-180. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Отримано оцінки для спрощення розрахунків, пов’язаних з перетином випадкових заявок, що складаються з декількох часових інтервалів. Використано аналітичні прийоми та статистичне моделювання. Результати можуть використовуватися при проектуванні комунікаційних систем.
Estimates are derived towards simplification of accounts related to intersecting random calls consisting of several time intervals. Analytical approach as well as Monte Carlo simulation is applied. The results can be applied while communication systems design.
|
| first_indexed | 2025-12-07T17:46:07Z |
| format | Article |
| fulltext |
ÓÄÊ 519.872
Å.Â. ÊÎÁÀ, Î.Í. ÄÛØËÞÊ
ÎÖÅÍÊÀ ÂÅÐÎßÒÍÎÑÒÈ ÏÅÐÅÑÅ×ÅÍÈß ÇÀßÂÎÊ
ÑËÎÆÍÎÉ ÑÒÐÓÊÒÓÐÛ Â ÑÈÑÒÅÌÀÕ ÎÁÑËÓÆÈÂÀÍÈß
Êëþ÷åâûå ñëîâà: ñèñòåìà ìàññîâîãî îáñëóæèâàíèÿ, ìíîæåñòâåííàÿ çàÿâêà,
èíòåðâàë ïåðåñå÷åíèÿ, àëãîðèòì ïðîòÿæêè, âåðîÿòíîñòü ïåðåñå÷åíèÿ, ñèñòåìû
ìíîæåñòâåííîãî äîñòóïà.
 òåîðèè ñèñòåì îáñëóæèâàíèÿ íàèáîëüøåå ðàñïðîñòðàíåíèå ïîëó÷èëè ïóàññî-
íîâñêèå, ãðóïïîâûå ïóàññîíîâñêèå, ðåêóððåíòíûå è ãðóïïîâûå ðåêóððåíòíûå ïî-
òîêè çàÿâîê. Ýòè ÷åòûðå òèïà ïîòîêîâ îõâàòûâàþò ìíîãèå ìîäåëè òåõíè÷åñêèõ
è âû÷èñëèòåëüíûõ ñèñòåì. Îäíàêî â ïðàêòèêå ìîäåëèðîâàíèÿ ÷àñòî ïðèõîäèòñÿ
ñòàëêèâàòüñÿ êàê ñ ïîòîêàìè, òàê è ñ çàÿâêàìè áîëåå ñëîæíîé ïðèðîäû, êîòîðûå
ìîæíî íàáëþäàòü â ïðîöåññàõ ôóíêöèîíèðîâàíèÿ êîìïüþòåðíûõ è áåñïðîâîäíûõ
ñåòåé, à òàêæå â ñïóòíèêîâûõ è ñîòîâûõ ñèñòåìàõ ñâÿçè. Íàïðèìåð, â êîìïüþòåð-
íûõ è áåñïðîâîäíûõ ñåòÿõ, ãäå èñïîëüçóåòñÿ ìíîæåñòâåííûé äîñòóï ê ñðåäå ïåðå-
äà÷è äàííûõ, êàê ïðàâèëî, îäíîé ñòàíöèè íå ðàçðåøàåòñÿ äîëãî çàíèìàòü êàíàë
ïåðåäà÷è, çàñòàâëÿÿ òåì ñàìûì æäàòü äðóãèå ñòàíöèè.  ñâÿçè ñ ýòèì îáúåì èí-
ôîðìàöèè îò îäíîé ñòàíöèè ðàçáèâàåòñÿ íà íåêîòîðîå êîëè÷åñòâî êàäðîâ (ôðåé-
ìîâ), êîòîðûå è ïîäëåæàò îáðàáîòêå ïî îïðåäåëåííûì ïðàâèëàì.  ýòîì ñëó÷àå
ìîæíî ãîâîðèòü î çàÿâêå ñëîæíîé ñòðóêòóðû (ìíîæåñòâåííîé çàÿâêå). Ðàññìîò-
ðèì åùå íåñêîëüêî ïðèìåðîâ, ãäå íàáëþäàåòñÿ îáñëóæèâàíèå ìíîæåñòâåííûõ
çàÿâîê.
Óïðàâëåíèå ïåðåäà÷åé äàííûõ â ëîêàëüíîé âû÷èñëèòåëüíîé ñåòè, ñîñòîÿùåé èç N
êîìïüþòåðîâ, îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ïðîòîêîëà ÒÑÐ. Òðàíñïîðòíûé ïðîòîêîë
ÒÑÐ ïðåäñòàâëÿåò èíòåðôåéñ ìåæäó ïðèëîæåíèÿìè è ñåòåâûìè óñòðîéñòâàìè, ïîçâî-
ëÿþùèìè ïðèëîæåíèÿì çàïðàøèâàòü îïðåäåëåííîå êà÷åñòâî îáñëóæèâàíèÿ.  ñëó÷àå
îòêëîíåíèÿ ïàðàìåòðîâ ïåðåäàâàåìûõ äàííûõ îò òðåáóåìîãî ïîðÿäêà ïðîòîêîë ÒÑÐ
ðàçäåëÿåò ñóììàðíûé ïîòîê ïðèêëàäíûõ äàííûõ íà îòäåëüíûå ëîãè÷åñêèå ïîòîêè
è îñóùåñòâëÿåò óïîðÿäî÷åíèå ïàêåòîâ äàííûõ, êîòîðûå ìîãëè ïðèéòè ïî ðàçëè÷íûì
ñåòåâûì òðàåêòîðèÿì èëè èñêàçèòüñÿ ïðè ïåðåäà÷å. Ïîñòóïàþùèå äàííûå â êàæäîì
ïîòîêå îáðàáàòûâàþòñÿ ïðîòîêîëîì ÒÑÐ è çàòåì ïåðåäàþòñÿ íà ñëåäóþùèé óðîâåíü
ïåðåäà÷è äàííûõ [1]. Òàêèì îáðàçîì, èìååòñÿ íàëîæåíèå N ïîòîêîâ, êàæäûé èõ êîòî-
ðûõ ñîñòîèò èç ñëó÷àéíîãî ÷èñëà çàÿâîê ìíîæåñòâåííîé ñòðóêòóðû.
Ïðîèçâîäèòåëüíîñòü ëîêàëüíîé ñåòè âî ìíîãîì çàâèñèò è îò ðàáîòû êîììóòà-
òîðà, ïîçâîëÿþùåãî îäíîâðåìåííî îáðàáàòûâàòü íåñêîëüêî êàäðîâ. Òàê, â õîäå ïå-
ðåäà÷è ñîîáùåíèÿ îíî äåëèòñÿ íà êàäðû, êîòîðûå îò êîìïüþòåðà ïîñòóïàþò íà
ïîðò êîììóòàòîðà äëÿ îáñëóæèâàíèÿ. Ïîñêîëüêó êîììóòàòîð èìååò íåñêîëüêî ïî-
ðòîâ, ýòî ïîçâîëÿåò åìó îáðàáàòûâàòü êàäðû ïàðàëëåëüíî ìåæäó âñåìè ïàðàìè ñâîèõ
ïîðòîâ. Òàêèì îáðàçîì, ïðîèñõîäèò äèñïåò÷åðèçàöèÿ îáñëóæèâàíèÿ ìíîæåñòâåí-
íûõ çàÿâîê â ïðîöåññå ôóíêöèîíèðîâàíèÿ ïðîöåññîðîâ êîììóòàòîðà.
 îòëè÷èå îò êîìïüþòåðíûõ ñåòåé, ãäå â êà÷åñòâå ôèçè÷åñêîé ïåðåäà÷è äàí-
íûõ ïðèìåíÿþòñÿ ðàçëè÷íûå âèäû êàáåëåé, â áåñïðîâîäíûõ ñåòÿõ èñïîëüçóþòñÿ
ðàäèîêàíàëû, êîòîðûå îáðàçóþòñÿ ñ ïîìîùüþ ïåðåäàò÷èêà è ïðèåìíèêà ðàäèî-
âîëí. Ñëåäîâàòåëüíî, ðàäèî÷àñòîòíûå ñèãíàëû ïîäâåðæåíû èñêàæåíèÿì, îáóñëîâ-
ëåííûì ïîìåõàìè, âîçíèêàþùèìè ïðè îäíîâðåìåííîì ïîñòóïëåíèè äâóõ ñèãíàëîâ
ê îäíîé ïðèåìíîé ñòàíöèè. Âíóòðåííèå ïîìåõè âîçíèêàþò òîãäà, êîãäà âíåøíèå
ñèãíàëû ìåøàþò ðàñïðîñòðàíåíèþ ðàäèîñèãíàëîâ áåñïðîâîäíîé ñåòè. Ïðèåìíèê
îáíàðóæèâàåò îøèáêè, â ðåçóëüòàòå ÷åãî îñóùåñòâëÿåòñÿ ïîâòîðíàÿ ïåðåäà÷à, à ïîëü-
çîâàòåëü, âîçìîæíî, çàìå÷àåò çàäåðæêó ñâÿçè. Ïðèìåðîì ìîãóò ñëóæèòü äâå áåñïðî-
âîäíûå ëîêàëüíûå ñåòè, ðàáîòàþùèå â îäíèõ è òåõ æå íåëèöåíçèðóåìûõ äèàïàçîíàõ è
ðàçâåðíóòûå íåäàëåêî îäíà îò äðóãîé. Òàêæå èñòî÷íèêàìè âíóòðåííèõ ïîìåõ ìîãóò
áûòü ìîáèëüíûå òåëåôîíû, ìèêðîâîëíîâûå ïå÷è è óñòðîéñòâà ñòàíäàðòà Bluetooth [2].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 175
© Å.Â. Êîáà, Î.Í. Äûøëþê, 2010
Ïðîïóñêíàÿ ñïîñîáíîñòü áåñïðîâîäíîé ñåòè ìîæåò ñóùåñòâåííî ñíèçèòüñÿ âñëåäñòâèå
ïîâòîðíûõ ïåðåäà÷ è âîçðàñòàíèÿ â ñåòè êîíêóðåíöèè çà ïðàâî äîñòóïà ê ñðåäå. Òàêèì
îáðàçîì, ðàññìàòðèâàåòñÿ âîïðîñ î ìíîæåñòâåííîé çàÿâêå.
Îòìåòèì, ÷òî ìíîæåñòâåííîñòü çàÿâîê â êàíàëàõ áåñïðîâîäíîé ñâÿçè ìîæåò
áûòü ñâÿçàíà ñî âñïîìîãàòåëüíûìè îïåðàöèÿìè, íåîáõîäèìûìè äëÿ óñòàíîâëåíèÿ
ñâÿçè (íàñòðîéêà ÷àñòîòû, ñèíõðîíèçàöèÿ, ïðîâåðêà àäðåñíûõ êîäîâ, òåñòîâûå
ôðåéìû è ò.ï.). Ïðè äîñòàòî÷íî âûñîêîì óðîâíå ïîìåõ â ñèñòåìàõ áåñïðîâîäíîé
ñâÿçè äàííûå îáû÷íî èìåþò çàäåðæêó, ñâÿçàííóþ ñ ïîäòâåðæäåíèåì ïðèåìà.
Ñ óâåëè÷åíèåì îáúåìà äàííûõ ðàñòåò âåðîÿòíîñòü ïîÿâëåíèÿ îøèáêè ïðè èõ ïåðå-
äà÷å, ò.å. âîçìîæíà ïîâòîðíàÿ ïåðåäà÷à äàííûõ.  öåëÿõ èñêëþ÷åíèÿ âîçäåéñòâèÿ
âîçìîæíûõ äëèòåëüíûõ ïîìåõ ïåðåäà÷à äàííûõ îñóùåñòâëÿåòñÿ ñ ïåðåðûâîì.
Ñëåäîâàòåëüíî, ñíîâà âîçíèêàåò çàäà÷à î ìíîæåñòâåííîé çàÿâêå.
Ïðèâåäåííûå ïðèìåðû ïîêàçûâàþò ïðàêòè÷åñêóþ àêòóàëüíîñòü ñèñòåì ìàññî-
âîãî îáñëóæèâàíèÿ ñ ìíîæåñòâåííûìè çàÿâêàìè. Íà îñíîâàíèè èçó÷åíèÿ ðàçëè÷-
íûõ ñèñòåì îáñëóæèâàíèÿ ìîæíî ñäåëàòü âûâîä î íåîáõîäèìîñòè èñïîëüçîâàíèÿ
èìåþùèõñÿ è ðàçðàáîòêå íîâûõ ìåòîäîâ èññëåäîâàíèÿ òèïè÷íûõ ñèñòåì ñ íåòðàäè-
öèîííûìè, ò.å. íå ïóàññîíîâñêèìè è íå ðåêóððåíòíûìè, ïîòîêàìè çàÿâîê. ×àñòíûé
ñëó÷àé ïîäîáíîé ñèñòåìû ðàññìîòðåí â [3].
Ñôîðìóëèðóåì îäíó èç âîçìîæíûõ ïîñòàíîâîê çàäà÷è. Èìååòñÿ ïóàññîíîâñêèé
ïîòîê îäíîðîäíûõ ñîáûòèé — ïåðâîíà÷àëüíûõ çàÿâîê. Ñ êàæäîé çàÿâêîé âîçíèêàåò ñëó-
÷àéíîå ìíîæåñòâî èìïóëüñîâ (÷èñëî èìïóëüñîâ è èõ ïðîäîëæèòåëüíîñòè — ïðîèçâîëü-
íî ñâÿçàííûå ñëó÷àéíûå âåëè÷èíû). Òåðìèíîì «ñëîæíàÿ çàÿâêà» áóäåì íàçûâàòü ñëó-
÷àéíîå ìíîæåñòâî èìïóëüñîâ, ïîðîæäåííûõ íåêîòîðîé ïåðâîíà÷àëüíîé çàÿâêîé. Ìíî-
æåñòâà èìïóëüñîâ ðàçëè÷íûõ ñëîæíûõ çàÿâîê íåçàâèñèìû; íå çàâèñÿò îíè è îò
ðàñïîëîæåíèÿ ìîìåíòà ïåðâîíà÷àëüíîé çàÿâêè íà ïðÿìîé âðåìåíè. Âñëåäñòâèå ïåðå-
êðûòèÿ ñëîæíûõ çàÿâîê âîçìîæíû íåêîòîðûå èíôîðìàöèîííûå ïîòåðè. Ñòàâèòñÿ çàäà÷à
îöåíèòü âåðîÿòíîñòü ïåðåñå÷åíèÿ ýòèõ çàÿâîê.
Îòìåòèì, ÷òî ñóùåñòâóåò àëãîðèòì ñòàòèñòè÷åñêîé ðåàëèçàöèè ñëó÷àéíîãî èì-
ïóëüñíîãî ìíîæåñòâà, ïîðîæäàåìîãî îòäåëüíîé çàÿâêîé. ×åðåç õàðàêòåðèñòèêè ýòîãî
ìíîæåñòâà (åñëè íåîáõîäèìî, åùå îäíîãî èëè äâóõ ðåàëèçîâàííûõ ìíîæåñòâ òàêî-
ãî æå âèäà) âûðàæàþòñÿ íåêîòîðûå ïðàêòè÷åñêè èíòåðåñíûå ñëó÷àéíûå âåëè÷èíû,
àëãîðèòì âû÷èñëåíèÿ êîòîðûõ ïðèâîäèòñÿ.
Îäíèì èç ðåçóëüòàòîâ ÿâëÿåòñÿ àâòîìàòèçàöèÿ ðàñ÷åòà «èíòåðâàëà ïåðåñå÷å-
íèÿ» äâóõ ìíîæåñòâ (ìíîæåñòâà ñäâèãîâ, ïðè êîòîðûõ èìååò ìåñòî ïåðåñå÷åíèå).
ÀËÃÎÐÈÒÌ ÍÀÕÎÆÄÅÍÈß ÄËÈÍÛ «ÈÍÒÅÐÂÀËÀ ÏÅÐÅÑÅ×ÅÍÈß» ÄÂÓÕ ÌÍÎÆÅÑÒÂ
Ïóñòü çàäàíû äâà ÷èñëîâûõ ìíîæåñòâà
U a b V c di i
i
k k
k
� �
� �
( , ), ( , )
1 1
� �
� � ,
ãäå 0 01 1 2 1 1 2� � � � � � � � � �a b a b c d c d� �� �, , � �, — íàòóðàëüíûå ÷èñëà.
«Èíòåðâàëîì ïåðåñå÷åíèÿ» (è.ï.) ìíîæåñòâ U è V íàçîâåì ìíîæåñòâî òåõ ÷è-
ñåë � ëþáîãî çíàêà, äëÿ êîòîðûõ ìíîæåñòâî U èìååò õîòÿ áû îäíó òî÷êó ïåðåñå÷å-
íèÿ ñ ìíîæåñòâîì V c dk k
k
� � � �
�
� � �
�
( , )
1
� .
Ïðåäëàãàåòñÿ àëãîðèòì âû÷èñëåíèÿ ëåáåãîâîé ìåðû TUV «èíòåðâàëà ïåðåñå÷å-
íèÿ». Ïðîùå ãîâîðÿ, åñëè ýòîò «èíòåðâàë» ñîñòîèò èç íåñêîëüêèõ íåïåðåñåêàþùèõ-
ñÿ èíòåðâàëîâ, òî TUV áóäåò èõ ñóììàðíîé äëèíîé, ò.å.
È.ï. { }� � � � � �
��
���
�
��
� � �: ( , ) ( , )a b c di i k k
ki 11
.
Ðàññìîòðèì êàêèå-ëèáî çàäàííûå i è k. Èññëåäóåì, äëÿ êàêèõ �
( , ) ( , ) .a b c di i k k� � � � �� �
Íàèìåíüøåå äîïóñòèìîå çíà÷åíèå � — òàêîå, ïðè êîòîðîì ( , )c dk k� �� � ïðè-
ìûêàåò ê ( , )a bi i ñëåâà, íàèáîëüøåå — êîãäà ñïðàâà.
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Ñîîòâåòñòâåííî d ak i� �� è c bk i� �� .
Òàêèì îáðàçîì, � äîëæíî âõîäèòü â èíòåðâàë
W a d b cik i k i k� � �( , ) .
Äëèíà òàêîãî èíòåðâàëà äëÿ � ñîñòàâëÿåò
T b a d cik i i k k� � � �( ) ( ) . (1)
Ñóììèðóÿ (1) ïî âñåì i è k, ïîëó÷àåì
T b a d c b a dUV i i k k
i k i
i i
k
k � � � � � � �
� �
[( ) ( )] ( ) (
,
� �
� �
1 1
ck ) . (2)
Åñëè ëåáåãîâó ìåðó ìíîæåñòâà îáîçíà÷èòü | |� , òî (2) ìîæíî ïåðåïèñàòü ñëåäó-
þùèì îáðàçîì:
T U VUV �� �| | | | . (3)
Âî ìíîãèõ ñëó÷àÿõ îöåíêà (3) ëèáî àáñîëþòíî òî÷íà, ëèáî èìååò ìàëóþ îòíî-
ñèòåëüíóþ ïîãðåøíîñòü. Òåì íå ìåíåå, ïîñêîëüêó ýòî íå âñåãäà òàê, ïðèâîäèì àë-
ãîðèòì òî÷íîãî ïîäñ÷åòà âåëè÷èíû TUV .
Ïîëîæèì
� �ik i k ik i ka d b c� � � � �, . (4)
Ðàññìîòðèì ìíîæåñòâî
S ik ik
ki
� �
��
{ }� �
��
,
11
��
è óïîðÿäî÷èì ýòè ÷èñëà, ïåðåîáîçíà÷èâ èõ êàê x x x1 2 2 � ��. (Î÷åâèäíî, x1 —
ýòî íåêîòîðîå � ik , x2�� — íåêîòîðîå ��
ik
). Åñëè x j ik
{ }� , ïîëîæèì � j � 1, åñëè
x j ik
�{ }� , òî � j � �1. Òàê êàê a b c di i k k� �, , äëÿ ëþáîãî j ëèáî � j � 1, ëèáî
� j � �1. Òîãäà èñêîìîå TUV ìîæíî âû÷èñëèòü ïî ôîðìóëå
T x xUV j j i
i
j
j
� �
�
�
�
�
�
�
�
��
��
�
( )1
11
2 1
sgn �
��
, (5)
ãäå
sgn
åñëè
åñëè
åñëè
a
a
a
a
�
�
�
� �
�
�
�
��
1 0
0 0
1 0
, ,
, ,
, .
Îáúÿñíèòü (5) ìîæíî ñëåäóþùèì îáðàçîì. Äî ìîìåíòà x j âêëþ÷èòåëüíî íà÷à-
ëîñü ñòîëüêî èíòåðâàëîâ ( , )� �ik ik� , ñêîëüêî åäèíèö â ðÿäó � �1� �� j , è çàêîí÷è-
ëîñü ñòîëüêî, ñêîëüêî ìèíóñ åäèíèö. Ñëåäîâàòåëüíî, x j ïðèíàäëåæèò íåêîòîðîìó
èç ýòèõ èíòåðâàëîâ òîãäà è òîëüêî òîãäà, êîãäà �i
i
j
�
�
1
0, ò.å. sgn �i
i
j
�
�
�
�
�
�
�
�
�
�
1
1. Íî,
çíà÷èò, äëèíó èíòåðâàëà ( , )x xj j�1 íóæíî âêëþ÷àòü â ñóììó, ÷òî è ïðåäñòàâëåíî â ôîð-
ìóëå (5).  ïðîòèâíîì ñëó÷àå ôóíêöèÿ sgn ( )� � 0 , a «–1» â äàííîì ñëó÷àå áûòü íå
ìîæåò. Àëãîðèòì îáîñíîâàí.
ÌÎÄÈÔÈÊÀÖÈÈ ÀËÃÎÐÈÒÌÀ ÍÀÕÎÆÄÅÍÈß ÄËÈÍÛ
«ÈÍÒÅÐÂÀËÀ ÏÅÐÅÑÅ×ÅÍÈß» ÄÂÓÕ ÌÍÎÆÅÑÒÂ
1. Äëÿ êðàòêîñòè íàçîâåì ( , )a bi i U-èìïóëüñàìè, ( , )c dk k — V-èìïóëüñàìè.
Íà ïðàêòèêå ÷àñòî íóæíî ðàçëè÷àòü ñëó÷àè, êîãäà U-èìïóëüñ íà÷èíàåòñÿ âíóòðè
V-èìïóëüñà, ò.å. c a dk i k� � � �� �, ëèáî íàîáîðîò, ò.å. a c bi k i� � �� .  ïåðâîì
ñëó÷àå ìåðó «èíòåðâàëà ïåðåñå÷åíèÿ» îáîçíà÷èì TU V/ , âî âòîðîì — TV U/ . Âû-
÷èñëåíèå îáåèõ ýòèõ âåëè÷èí äàåòñÿ òåì æå àëãîðèòìîì, ÷òî è âûøå, òîëüêî
ñ òåì èçìåíåíèåì, ÷òî � �ik ik, � íóæíî çàäàâàòü íå ôîðìóëîé (4), à äðóãèì ñïîñî-
áîì.  ïåðâîì ñëó÷àå, ò.å. äëÿ âû÷èñëåíèÿ TU V/ , èìååì
� �ik i k ik i ka d a c� � � � �, ,
âî âòîðîì, àíàëîãè÷íî,
� �ik i k ik i ka c b c� � � � �, .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 177
 ýòîì ñîñòîèò èçìåíåíèå àëãîðèòìà.
Ñóììèðóÿ ïî i k, , èìååì
T d cU V ik ik
i k
k k
i k
/
, ,
( ) ( ) � � � �
� � ,
èëè
T VU V/ | | � . (6)
Àíàëîãè÷íî
T UV U/ | | � . (7)
Òàê êàê T T TUV V U U V �/ / , èç (6) è (7) ñíîâà ìîæåì ïîëó÷èòü îöåíêó (3).
2. Ïðèâåäåì àëãîðèòì äëÿ ó÷åòà «ìåðòâîãî âðåìåíè». Îáîçíà÷èì T
U V/
( )� ìåðó
ìíîæåñòâà òàêèõ �, ïðè êîòîðûõ õîòÿ áû äëÿ îäíîé ïàðû ( , )i k íà÷àëî i-ãî U-èì-
ïóëüñà ïîïàäàåò ëèáî íà k-é V-èìïóëüñ, ëèáî íà ðàññòîÿíèå, ìåíüøåå � ñëåâà îò
íåãî íà îñè âðåìåíè.
Ïðèíèìàÿ ïðàêòè÷åñêè íàèáîëåå èíòåðåñíîå óñëîâèå, ÷òî âñåãäà
d ck k� �� 1,
äëÿ T
U V/
( )� èìååì òîò æå àëãîðèòì, ÷òî è âûøå, äëÿ TU V/ , òîëüêî â èñõîäíûõ
äàííûõ íåîáõîäèìî çàìåíèòü âñå ck íà ck � � .
Âåðõíèå îöåíêè î÷åâèäíû:
T V
U V/
( ) (| | )� � �� � , T U
V U/
( ) (| | )� � �� � .
Ìîæíî ïîêàçàòü, ÷òî èìåþò ìåñòî òàêèå îöåíêè:
T T
U V U V/
( )
/
� � � �� , T T
V U V U/
( )
/
� � � �� .
Îíè ñëåäóþò èç ïîëóàääèòèâíîñòè ôóíêöèîíàëà Ò,
T T TU V V U V U V/ / /1 2 1 2� � ,
êîòîðàÿ âûòåêàåò èç ôîðìóëû (2).
Ïðèâåäåì àëãîðèòì ìîäåëèðîâàíèÿ «èíòåðâàëà ïåðåñå÷åíèÿ» äëÿ äâóõ ìíî-
æåñòâ.
Èìååì äâà ìíîæåñòâà:
{ }, { }( , ),... , ( , ) ( , ),... , ( , )a b a b a b a bn n m m1 1 1 1� � � � ,
à òàêæå îãðàíè÷åíèå { }� 0 .
Óïîðÿäî÷èì ïàðû ( , ),i j
1 i n,1 j m , òàêèì îáðàçîì,
êàê ïîêàçàíî íà ðèñ. 1.
Îáîçíà÷èì k íîìåð ïàðû
â ýòîì óïîðÿäî÷åíèè ( )1 k nm ,
a ( , )i jk k — êîîðäèíàòû k-é
ïàðû. Òàê, äëÿ ðèñ. 1, íàïðèìåð,
i j1 1 1� � , in� �1 1, jn� �1 2 .
Îáîçíà÷èì dk ÷èñëî íåïåðåñå-
êàþùèõñÿ �-èíòåðâàëîâ ïî ïà-
ðàì äî k-é âêëþ÷èòåëüíî,
( , ), ...A Bk k1 1 , ( , ), ,A Bk d k dk k
—
ýòè èíòåðâàëû â ïîðÿäêå âîçðàñ-
òàíèÿ, ò.å. B Ak k1 2� , è ò.ä. Òîã-
äà èìååì
T B AUV nm t nm t
t
dnm
� �
�
( ), ,
1
.
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
n1 2
Âõîä
i
1
2
j
m Êîíåö
0
Ðèñ. 1
Íà÷àëüíûå äàííûå: d0 0� ;
( , )A Bt t0 0 íå îïðåäåëÿþòñÿ (èõ
ìíîæåñòâî ïóñòî).
Íà k-ì øàãå ( )1 k nm :
â ïàìÿòè d A Bk k t k t� � �1 1 1; ( , ),, ,
1 1 �t dk .
Ïîñòóïàåò íîâûé èíòåðâàë
( , )C Dk k , ãäå C a bk i jk k
� � � ,
D b ak i jk k
� � � .
Îïðåäåëèì ïîäàëãîðèòì îò-
ñå÷åíèÿ ïî ñõåìå, ïðèâåäåííîé
íà ðèñ. 2.
Äàëåå îïðåäåëèì ïîäàëãî-
ðèòì ïîïîëíåíèÿ ìíîæåñòâà.
Îáîçíà÷èì
� kt
k k
k t k t
C D
A B
�
� �
1
1 1
, [ , ]
[ , ] ,
* *
, ,
åñëè
ïåðåñåêàåòñÿ
ñ
0
�
�
�
�
�
Äëÿ âû÷èñëåíèÿ èìååì ôîðìóëó
� kt
k k t k k tD A C B� � ��
�
�
� �0
1
1 1, ,*
,
*
,åñëè ;
Âû÷èñëÿåì � �k ktt� �min :{ }1, � �k ktt� �max :{ }1 è ïîëàãàåì
d dk k k k� � ��1 � � ;
A Akt k t� �1, ïðè 1 1 �t k� ; B Bkt k t� �1, ïðè 1 1 �t k� ;
A C Ak k kk k� �� �min ( , )*
,1 ; B D Bk k kk k� �� �max ( , )*
,1 ;
A A t dkt k t k kk k
� � � � �1 1, � � �ïðè ;
B B t dkt k t k kk k
� � � � �1 1, � � �ïðè .
ÂÅÐÕÍßß ÎÖÅÍÊÀ ÂÅÐÎßÒÍÎÑÒÈ ÏÅÐÅÊÐÛÒÈß ÑËÎÆÍÛÕ ÑËÓ×ÀÉÍÛÕ ÇÀßÂÎÊ
Ðàññìîòðèì ïóàññîíîâñêèé ïîòîê ñëîæíûõ çàÿâîê ñ ïàðàìåòðîì �. Ñ êàæäîé çàÿâêîé
àññîöèèðóåòñÿ ñëó÷àéíîå ìíîæåñòâî U a bi i
i
�
�
( , )
1
�
� , ãäå 0 1 1 2� � � � �a b a b� � , âå-
ëè÷èíû �, ,a bi i — ñëó÷àéíûå: îíè îïðåäåëÿþòñÿ îáùèì ýëåìåíòàðíûì ñîáûòè-
åì �
�, ãäå � — ïðîñòðàíñòâî ýëåìåíòàðíûõ ñîáûòèé. Ýëåìåíò � ðåàëèçóåòñÿ
ïî ìåðå P A( ) íà íåêîòîðîé �-àëãåáðå ñîáûòèé F. Áóäåì ñ÷èòàòü, ÷òî èìååòñÿ
àëãîðèòì, ïîçâîëÿþùèé íàõîäèòü ðåàëèçàöèè ìíîæåñòâà U. Åñëè t — ìîìåíò
ïîñòóïëåíèÿ ñëîæíîé çàÿâêè, òî ìíîæåñòâî U ðàñïîëîæèì íà îñè âðåìåíè ñ íà-
÷àëîì â ìîìåíòå t. Öåëüþ ÿâëÿåòñÿ âû÷èñëåíèå ìåòîäîì Ìîíòå-Êàðëî âåðîÿò-
íîñòè q ïåðåêðûòèÿ ìåæäó äàííûì è äðóãèì íåêîòîðûì èìïóëüñîì. Ñëîâî «ïå-
ðåêðûòèå» ìîæíî ïîíèìàòü â ëþáîì ñìûñëå, óêàçàííîì âûøå. Ãèïîòåòè÷åñêèé
«ìåøàþùèé» èìïóëüñ îáîçíà÷èì V. Òîãäà
q q q q q q q q q qUV U V V U U V V U
� � � � �, , , ,/ / /
( )
/
( )� � ,
ãäå qUV
— âåðîÿòíîñòü ïåðåêðûòèÿ õîòÿ áû îäíîãî U-èìïóëüñà ñ îäíèì V-èìïóëü-
ñîì, qU V/
— âåðîÿòíîñòü íà÷àëà õîòÿ áû îäíîãî U-èìïóëüñà âî âðåìÿ V-èìïóëüñà,
qV U/
— íàîáîðîò, q
V U/
( )� è q
U V/
( )� — òî æå ñ ó÷åòîì ïðîäëåíèÿ íà âðåìÿ � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 179
â ïðîòèâíîì ñëó÷àå.
â ïðîòèâíîì ñëó÷àå.
Øàã k + 1
Ïîäàëãîðèòì
ïîïîëíåíèÿ
ìíîæåñòâà
Äà
Äà
Íåò
Íåò
Ðèñ. 2
Ck � 0
d dk k:� �1
A Akt k t: ,� �1
B Bkt k t: ,� �1
C Ck k
* :�
Dk
* :� 0 D Dk k
* :�
C Ck k
* :�
Dk � 0
Îáîçíà÷èì �* èíòåíñèâíîñòü ïîòîêà çàáèòûõ çàÿâîê. Òîãäà èç òåîðèè Õèí÷èíà
ïîòîêîâ îäíîðîäíûõ ñîáûòèé [4] èìååì q �
�
�
*
.
Ñîáûòèå ïîÿâëåíèÿ â èíòåðâàëå äëèíû dt çàÿâêè, êîòîðàÿ äîëæíà áûòü çàáè-
òîé, ðàâíà ïåðåñå÷åíèþ ñëåäóþùèõ äâóõ ñîáûòèé:
1) ïîÿâëåíèå â èíòåðâàëå ( , )t t dt0 0 � çàÿâêè ñî ñëó÷àéíûì ìíîæåñòâîìU;
2) ïîÿâëåíèå â èíòåðâàëå ( , )t t d0 0� � �� � � çàÿâêè ñî ñëó÷àéíûì ìíîæåñòâîì V.
Çäåñü U è V íåçàâèñèìûå, ïðè÷åì U è V � � ïåðåñåêàþòñÿ. Åñëè U è V ôèêñèðî-
âàòü, òî âåðîÿòíîñòü ïåðåñå÷åíèÿ óêàçàííûõ äâóõ ñîáûòèé ðàâíà � � �dt d� ïðè ïåðå-
ñå÷åíèè U ñ V � � è ðàâíà íóëþ â ïðîòèâíîì ñëó÷àå.
Èíòåãðèðóÿ ïî âñåì �, ïîëó÷àåì �2T dtUV . Óñðåäíÿÿ ïî V è U (èìè îïðåäåëÿåò-
ñÿ T), âûâîäèì ôîðìóëó
� �* 2 MTUV ,
îòêóäà
q MT
UV UV � . (8)
Àíàëîãè÷íûå îöåíêè ïîëó÷èì è ïðè äðóãèõ îïðåäåëåíèÿõ ïåðåêðûòèé èì-
ïóëüñîâ:
q MT
U V U V/ / � , (9)
q MT
V U V U/ / � , (10)
q MT
U V U V/
( )
/
( )� � � , (11)
q MT
V U V U/
( )
/
( )� � � . (12)
Ïîä÷åðêíåì, ÷òî V è U äîëæíû áûòü íåçàâèñèìû, ò.å. ãåíåðèðîâàòüñÿ íà îñíî-
âàíèè íåçàâèñèìûõ ýëåìåíòîâ �1 è �2 ñ ðàñïðåäåëåíèåì P A( ) .
Èìåÿ àëãîðèòì ïîñòðîåíèÿ ñëó÷àéíîãî ìíîæåñòâàU (òîò æå äëÿV) è ïðèìåíÿÿ
àëãîðèòì íàõîæäåíèÿ äëèíû «èíòåðâàëà ïåðåñå÷åíèÿ» äâóõ ìíîæåñòâ, íàõîäèì ðå-
àëèçàöèþ ñëó÷àéíîé âåëè÷èíû TUV èëè àíàëîãè÷íûõ åé. Çàòåì ïóòåì óñðåäíåíèÿ
íàõîäèì ñîñòîÿòåëüíóþ îöåíêó TUV , à ïî íåé è ôîðìóëàì (8)–(12) — âåðõíþþ
îöåíêó q q q q qUV U V V U U V V U
, , , ,/ / /
( )
/
( )� � .
Ïðåäëîæåííûå àëãîðèòìû ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ íå îòíîñÿòñÿ ê î÷å-
âèäíûì, òàê êàê îñíîâàíû íå íà ðàñ÷åòå âîçìîæíîãî ïåðåñå÷åíèÿ ñëó÷àéíûõ ìíî-
æåñòâ, ÷òî ïðàêòè÷åñêè ìàëîâåðîÿòíî, à íà îïðåäåëåííîì àëãîðèòìå «ïðîòÿæêè»
îäíîãî ìíîæåñòâà ÷åðåç äðóãîå (ïåðåìåííûé ñäâèã ïî âðåìåíè îäíîãî èç íèõ).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ ï î ð ò à ê Ì . Êîìïüþòåðíûå ñåòè è ñåòåâûå òåõíîëîãèè. — ÑÏá.: ÎÎÎ «ÄèàÑîôòÞÏ», 2005. —
720 ñ.
2. Ñ ò î ë ë è í ã ñ Â . Áåñïðîâîäíûå ëèíèè ñâÿçè è ñåòè. — ÑÏá.: Ïèòåð, 2003. — 640 ñ.
3. Ê î á à Å . Â . Ñèñòåìà îáñëóæèâàíèÿ ïóàññîíîâñêîãî ïîòîêà ñäâîåííûõ çàÿâîê // Äîï. ÍÀÍ Óêðà¿íè.
— 1995. — ¹ 3. — Ñ. 9–11.
4. Á î ÷ à ð î â Ï . Ï . , Ï å ÷ è í ê è í À . Â . Òåîðèÿ ìàññîâîãî îáñëóæèâàíèÿ. — Ì.: ÐÓÄÍ, 1995. —
529 ñ.
Ïîñòóïèëà 19.05.2009
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
|
| id | nasplib_isofts_kiev_ua-123456789-45208 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:46:07Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Коба, Е.В. Дышлюк, О.Н. 2013-06-08T18:35:43Z 2013-06-08T18:35:43Z 2010 Оценка вероятности пересечения заявок сложной структуры в системах обслуживания / Е.В. Коба, О.Н. Дышлюк // Кибернетика и системный анализ. — 2010. — № 3. — С. 175-180. — Бібліогр.: 4 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45208 519.872 Отримано оцінки для спрощення розрахунків, пов’язаних з перетином випадкових заявок, що складаються з декількох часових інтервалів. Використано аналітичні прийоми та статистичне моделювання. Результати можуть використовуватися при проектуванні комунікаційних систем. Estimates are derived towards simplification of accounts related to intersecting random calls consisting of several time intervals. Analytical approach as well as Monte Carlo simulation is applied. The results can be applied while communication systems design. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Оценка вероятности пересечения заявок сложной структуры в системах обслуживания Оцінка ймовірності перетину заявок складної структури в системах обслуговування Estimates for probabilities and means related to intersections of complex random calls in queueing systems Article published earlier |
| spellingShingle | Оценка вероятности пересечения заявок сложной структуры в системах обслуживания Коба, Е.В. Дышлюк, О.Н. Системный анализ |
| title | Оценка вероятности пересечения заявок сложной структуры в системах обслуживания |
| title_alt | Оцінка ймовірності перетину заявок складної структури в системах обслуговування Estimates for probabilities and means related to intersections of complex random calls in queueing systems |
| title_full | Оценка вероятности пересечения заявок сложной структуры в системах обслуживания |
| title_fullStr | Оценка вероятности пересечения заявок сложной структуры в системах обслуживания |
| title_full_unstemmed | Оценка вероятности пересечения заявок сложной структуры в системах обслуживания |
| title_short | Оценка вероятности пересечения заявок сложной структуры в системах обслуживания |
| title_sort | оценка вероятности пересечения заявок сложной структуры в системах обслуживания |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45208 |
| work_keys_str_mv | AT kobaev ocenkaveroâtnostiperesečeniâzaâvoksložnoistrukturyvsistemahobsluživaniâ AT dyšlûkon ocenkaveroâtnostiperesečeniâzaâvoksložnoistrukturyvsistemahobsluživaniâ AT kobaev ocínkaimovírnostíperetinuzaâvokskladnoístrukturivsistemahobslugovuvannâ AT dyšlûkon ocínkaimovírnostíperetinuzaâvokskladnoístrukturivsistemahobslugovuvannâ AT kobaev estimatesforprobabilitiesandmeansrelatedtointersectionsofcomplexrandomcallsinqueueingsystems AT dyšlûkon estimatesforprobabilitiesandmeansrelatedtointersectionsofcomplexrandomcallsinqueueingsystems |