Қалааралық телефон желісіндегі тікелей буманың тураланған моделімен маршруттау алгоритмін моделденуі

 

 

 

мұндағы   

 

3. Бір кезеңді қызмет көрсету параметрі келесі түрге ие:

 

 

(3.6) анық емес теңдеуі тізбектелген жуықтау әдісі арқылы шешіледі.

Әр аралық қадамды  анықтау үшін жүйені (3.5) жоғарыда келтірілген  формула бойынша келесі есептеулері  бар декомпозиция (3.4) әдісімен есептеу  керек.х-ты анықтағаннан кейін бастапқы модельдің ықтималдық сипаттамларының бағасы анықталады.

 

 және с.с.

 

Бұл модельді қызмет көрсетілімінде бас тартуға ие болған  абоненттерді басқару арқылы қолжеткізетін эффекті  зерттеу кезінде қолданған. Басқару  деп телефон желісі арқылы абонентке  көрсетілетін сервистік қызметтің кеңеюін айтамыз. Бұларға мысал ретінде шақырып жатқан абонентке  шақырылып жатқан абоненттің бос еместігі туралы хабарлама, шақырылып жатқан абоненттің болмауына байланысты автоматты жауап бергішті қолдану және с.с. жатқызуға болады [17].

 

 

 

 

 

 

 

3.2 Маршруттау алгоритмін моделі

3.2.1 Байланыс желісінің  моделі

N тораптан және М  арнаға ие коммутациялық хабарламасы  бар байланыс желісінің моделін  қарастырамыз. Бұл модельде М  арнасы абсолютті сенімді болып  келеді, ал өткізгіштік қабілеті i-ші арна C_i-ге (бит секундына) тең. 

      Орталық хабарламалар коммутациясымен (дестелер) сәйкес келетін  барлық N тораптары абсолютті сенімді және хабарламалар коммутациясы бойынша операцияларды орындайды. Мысалы, хабарламаларды декомпондау, маршрутты таңдау,буферді сақтау және хабарлау т.с.с операцияларды орындайды. Торапта өңдеу кезеңі  К-ға тең және тұрақты (К шамасы әдетте кіші, бірақ К ағынын ізду алгоритмін жүзеге асыру кезінде нөлге тең)  деп қарастырады. Сонымен қатар модельде арналарға кезектер және тарату кезінде кідіріс болады. Ішкі көзден желіге түскен трафик (мысалы, хостан түскен)  j  торапында пайда болған және k торапына арналған хабарламалар үшін  jk (хабар секундына) орташа санымен пуассоновтық процес туғызады [18].

Желіге түскен және (ізіндегі,тастап кеткен) толықтай ішкі трафикті төмендегідей табамыз:

 

(3.8)

 

i  шамасының түрлері  бар екенін ескере кетейік

 

(3.9)

Барлық хабарламар ұзақтығы  болжам бойынша тәуілсіз. Хабарламаларды желі торабына кірістіру үшін шексіз сыйымдылық жадына орналастырамыз.

Желідегі әр арна жеке қызмет көрсету құрылғысы ретінде  қарастырылса, i-ші арна бойынша өтетін хабарламаның орташа санын секундына  i арқылы белгілейміз.

Ішкі трафикті анықтағандай желідегі толық трафикті келесі түрде  анықтаймыз:

 

(3.10)

Жоғарыда хабарлама  кідірісі желідегі хабарламаларды  толық уақыты ретінде анықталды. Желінің басты сипаттамасы ретінде қабылданған T = M [хабарлар кідірісі] хабарлардың орташа кідірісін көрсетуі көп қызығушылық тудырады. Z_jk орташа шамасын анықтаймыз.

Z_jk = M [ j-да пайда болған хабарлар кідірісі  k-да бір орынға  ие]. Бұл екі орташа шама теңдікпен байланысты

 

(3.11)

 

Jk толық кіріс хабарламаларының  трафигінің  орташа үлесі Z_jk орташа кідіріске тең.  (3.11) формула теңдігі желіде  адресат көзін жұп бойынша жіктеуін қарастыратынын ескере кеткен жөн. Осылай жалпы қызмет көрсететін ашық желі аламыз. Енді ағындардың үлестіру есебін анықтаймыз. Есепте jk ішкі тұрақты трафикке тораптар жағдайы берілген.

 

 

3.2.2 Ағынды үлестіру  есебі және ауытқу әдісі

 

Т-ны сипаттау үшін төмендегі формуланы қолданамыз:

 

(3.12)

 

Бұл желіде өтіп жатқан хабарламаның орташа  кідірісін есептейді. Барлық жалпы қызмет көрсету байланысы туралы сұрақтар осы теңдікпен  көрсетіледі; тек қана желіде ағын теориясына жататын ағындардың оптимизациясы есебі ғана қалады. Максимал ағын  және  минимал қиылысу теоремасың негізі арнадағы ағын өткізгішітік қабілетін максималға дейін жоғарлата алмайтынын туралы айттады, осыған сәйкес бұл теорема құрылған.

Ағындарды үлестіру есебінің берілісі әр түрлі жүктердің аңындарын  үлестіру есебі тәрізді. Мұның міндеті jk ағынының ішкі міндетін қанағаттандыру үшін Т сызықты емес функциясын {_i} ағыны бойынша минимизациялау болып табылады. Минимизациялау өткізгіш қабілеттілігі берілген деп болжам бойынша жүргізіледі. Сонымен қатар ағындарды сақтаудың қарапайым заңын бұзбау керек. Бұл заңға сәйкес n торабына түсетін

Jk қосылғыш трафигі  n тораптан шығатын n=j (n торабы  торап көзі болып табылады) кездейсоғының немесе n=k кездейсоғының ( n торабы  тораб атауы) шығуымен jk қосылғаш трафигіне тең болады [1].

0 λ_i < C өткізгіштік қабілетілігінен кіші және λ_i ағыны i арнасында теріс мәнді болмау үшін  әр арнаның өткізгіштік қабілетілігіне шектеу қойылады.

Бұл шектеу Т сипаттамасының  қандай да бір ағынның сәйкес арнаға ұмтылуы (желідегі бірнеше ағынның  жоғарғы шекараға  ұмтылуына қткізгіштік  қабілеттілігіне белгілі шектеу қойылған) өткізгіштік қабілеттілігінің шексіз өсуін көрсетеді. Бұл Т сипаттамасы өткізгіштік қабілеттілігіне штраф функциясы тәрізді қосымша шектеуге ие. Бұл негізгі қасиет «көп емес қадамның» тізбегі түрінде берілуін және бастапқы қадамда жүзеге асқан шешімді операциялануы кез келген минимизация әдісін қолданған кезде жүзеге асуды қамтамасыз етеді.

Осыдан егер жүзеге асқан  шешімнен бастайтын болсақ, онда осы  есептің жалғасынша шектеулі оптимизация  есебі тәрізді көрінентін  өткізгіштік  қабілеттігінің шектелуін сақтап қалуға болады. Деректер бойынша  әр түрлі  жүктегі ағындарды оптимизациялауы бойынша шектеусіз  есеп ретінде көрсетіледі [22].

Төменде сандық есептеу  жүргізуге ыңғайлы ағындардың оптималды  есептелуі кезінде нақты есеп жүргізетін әдіс қарастырылады. Т үшін төмендегі теңдеуді қарастырамыз (3.13 теңдеу).

Бұл сипаттама бір арнадағы ағынға тәуілді қарапайым қосынды соммасы ретінде қарастырылатынын ескере кеткен жөн. Сонымен қатар (4.5) теңдіктен төмендегі шығады:

 

,   i = 1, 2, …, M.		(3.13)

Бұл жерден барлық i-де  T/(λ_i) > 0 екені; аналогтық қарастыруларда       T/(λ_i)² > 0 екенін көрініп тұр (бұл екі теңсіздікте өткізгіштік қабілетті шектеуге қанағаттардыруға сәйкес келеді)  .

Осыған байланысты Т  дөңес ағын функциясы деп қорытындылауға болады.

Сонымен қатар көптеген іске асырылған ағындардың өзі дөңес көп шекті болып табылады. Егер есеп  нақты шешімге ие болса, онда кез келген локальді минимум Т үшін глобальді минимум болып табылады. Сәйкесінше локальдік минимумның іздеу әдісі глобальді минимумды іздеу есебінде қолданылады.

Ағынның ауытқу әдісі. Осы жерде қолданылатын әдіс глобальді минимумды іздеу үшін арналған ағынның ауытқу әдісі деп аталады. Мұның  бастысы қысқа жол бойынша ағынның таралуы болып табылады. Мысалы біз бір желіні қарастырайық, ол әр арнаның l_i ұзындығы ие деп аламыз. Мұндай желіде әрине j торап көзі және k торап атауы арасынан қысқа жолды тауып керекті jk ағынын осы қысқа жол арқылы жіберуге болады.  Егер  (j,k)-дың барлық ағындарымен осылай жіберсек, онда нәтижесінде ағындардың қысқа жол бойынша таратылуы деп аталады. Сонымен қатар бірнеше  jk қысқа жолдарды іздеудің  жақсы танымал және тиімді алгоритмдері бар [18].

3.2.3 Бірнеше қысқа жолды іздеудің  Флойд алгоритмі

 

Желіні N торбымен қарастырамыз. D₀=(d_jk) - N*N матрица реті болсын делік, мұндағы d_jk арнаның j торабының k торабымен тікелей жалғану ұзындығын беретін элемент (бұл есептеуде берілген деп есептейік), егер мұндай арна болмаса онда бұл элемент шексіздікке (сонымен қатар d_jj=0) тең болады.

j торабының k торабымен  жалғайтын jk кез келген жолын ұзындығын (арна ұзындығының қосындысын) l(_jk) арқылы белгілейміз. Есеп N*N реті бойынша Н=(h_jk) матрицасын есептеу болып табылады. Мұндағы h_jk - j торабының k торабымен жалғайтын қысқа жол ұзындығы; H- бізге қызығушылық тудыртатын  қысқа жол матрицасы;

Флойдтың қысқа жол  алгоритмі D₀ матрицасының арақаштығынан басталып және N матрициясынан (n-м қадамында матрица D_n арқылы белгіленеді) тізбектей өткен кезде интеративті өзгертеді; соңында D_N=H қысқа жол матрицасына өтеді [19].

Егер n=0 және d_jk(0)=d_jk бастасақ D_n интерация көмегімен D_n+1 матрицасын аламыз:

 

		(3.14)

D₁ тапқаннан кейін d_jk (1) (j, k элементі  D₁ матрицасында) екенін байқаймыз j торабынан k торабына қысқа жол ұзындығын деп алынады, ол тек қана  1 торабы бар аралық жолы алынады.

n-ші итерациядан D_n-ді іздегеннен кейін аралық тораптар көптеген {1, 2, ..., n}  жататындықтан d_jk(n) - j торабынан k торабына жолы бойынша қысқа арақашықтық деп аламыз.

Осылайша N-ші итерацияға жеткенде d_jk (N) = h_jk қажетті нәтижеге ие боламыз. Толықтай алгоритм N³ қосындысын және оқылуын және  N³ салыстыруын қажет етеді [20].

Әдістің мәні i-ші ребро  арқылы ағынды анықтап «ұзындықты»  салғастыру болып табылады. Оның шамасы теңдікте берілген:

 

(3.15)

 

Егер арнадағы ағын  λ_i тең болса, онда i-ші арнадағы ағынның шексіз өсуі Т-ның сызықты жылдамдығының өсуі екені анық. Мұндай «ұзындықты» немесе  « коэффициент құнын» келесіде  қысқа маршрут бойынша ағынды іздеу есебін тұжырымдауға болады. Ал алынған  жолдардың кейбір ағын бөліктері ауытқыған болса онда ондай жол  ең арзан жол ретінде көрініс табады. Жол анықталғаннан кейін ауытқыған ағын бөлігін анықтап, қысқа маршрут бойынша ағындарды іздеудің жаңа есебін шығарып, жаңартылған ағындардың негізінде жаңа ұзындықты қайта іздеп процессті қайталауға болады.

Бұл идеяларды қолдана  отырып нақты алгоритмді қарастырайық. Бұл үшін n-ші итерация алгоритмінде ағын векторын еңгіземіз:

 

(3.16)

 

N- итерациясында i  арнасы  бойынша  i –ші компоненттің толық ағынын көрсетеді. f⁽⁰⁾ бастапқы ағыны жүзеге асты деп есептейік.

 

 

3.2.4 Маршрутты таңдау  үшін ағынды  іздеудің оптимальды  алгоритмі

 

3.1 кесте - Ағынды іздеудің оптималды алгоритм қадамы

Қадам №	Анықтамасы
1-қадам	n=0 деп аламыз.
2-қадам	Әр бір i=1, 2,..., М үшін іздеу:
3-қадам	Үстеме коэффициент  құнын n – ағын үшін табу керек:
4-қадам	li  ұзындығын пайдалана отырып ағынды  қысқа маршрут бойынша іздеу есебін шешу. i – егер барлық ағын қысқа маршрут бойынша бағытталатын болса, онда i арнасы бойынша ағын нәтижесі болсын. Ағын векторын i = (1,2, ..., M) деп белгілейміз.
5-қадам	Үстеме коэффициент  құнын bn – ағын үшін қысқа маршрут bn = li i бойынша табу керек.
6-қадам	(Аялдау ережесі). Егер n - bn < , мұнда >0 болса,онда таңдалатын қолжетім түрі   STOP болады. Кері жағдайда 7-ші қадамға көшкен жөн болады.
7-қадам	(1 - a) f(n)+a ағыны Т-ны минимизациялайтын 0a1интервалынан а мәнін табу керек. Бұл оптималды мән a арқылы белгіленсін. А оптималды мәнін кез келген сәйкес әдістер көмегімен табуға болады.
8-қадам	(Ағынның ауытқуын ) f(n+1) = (l - a) f(n) + a қою керек.
9-қадам	n = n + 1 қойып, 2-ші қадамға көшу керек.

f⁽⁰⁾ іске асатын бастапқы ағынды іздеудің сұрағын қарастырамыз. Тағыда ішкі ағын берілсін деп қарастырайық:

(3.17)

h қарқындылық ағынға сәйкес келу үшін h берілген мәнге қатысы бар масштабты коэффициент h-ты еңгіземіз. Енді құрылған басатын бастапқы ағынды іздеу алгоритмі туралы сипаттаймыз. Берілген алгоритм маршрутты таңдауда бекітілген тәсілмен бағытталған ағындарды іздеу алгоритмінде қолданылғанын ескере кетейік.