Диссертация (1150593), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Ïóñòü νtk =Pnk ki=1 ηi ei ðàçëîæåíèå νtk ïî îðòîíîðìèðîâàííîìóTkkáàçèñó ñîáñòâåííûõ âåêòîðîâ L(B̄av). Òîãäà èìååì νtk L(B̄av)νtk =PPPkk)ei =)( ni=1 ηik eki ) = ni=1 ηi2 eTi L(B̄av= ( ni=1 ηik eki )T L(B̄avPn 2 Tkk))ei . Ïîñêîëüêó λ1 (L(B̄av)) = 0 (ïóñòü, íå óìàëÿÿ= i=1 ηi ei λi (L(B̄avPn 2 TPkkîáùíîñòè, λ1 ≤ . . . ≤ λn ), i=1 ηi ei λi (L(B̄av))ei = ni=2 ηi2 eTi λi (L(B̄av))eiPn 2 Tkkk 2≤i=2 ηi ei λ2 (L(B̄av ))ei = λ2 (L(B̄av ))kνt k . Ïîýòîìó ìîæíî îöåíèòükλmin L(B̄av) äåéñòâèòåëüíîé ÷àñòüþ âòîðîãî ïî âåëè÷èíå ñîáñòâåííîãîk÷èñëà ëàïëàñèàíà Re(λ2 L(B̄av)). k2k TkkE In(d+1)) )−γk Re(λ2 L(B̄av))+− γk L(B̄t ) νt ≤ (1−γk Re(λ2 L(B̄av¯+ γk2 Eλmax (L(B̄tk )T L(B̄tk )))kνtk k2 .58T˜2=˜ 2 ≤ γ 2 E λmax (B˜k B̃ k ) kdkÎöåíèì âûðàæåíèå Ekγk B̃tk dkttkT¯ T ⊗ (Z̄ k − R̄k )k2 == γk2 E λmax (B˜tk B̃tk ) k(0, 1, .

. . d) Xnd¯XTk22˜kl(z̄ k − r̄k )2  == γk E λmax (Bt B̃t )l=1i=1 ¯ ¯¯ + 1)d(d+1)(2d= γk2 E λmax (B˜tk B̃tk )n(z̄ k − r̄k )2 .6Tkk2 .Ïîñ÷èòàåì ìàòåìàòè÷åñêîå îæèäàíèå Ekνt+1kk Tk) ) − γk Re(λ2 L(B̄av))+Ekνt+1k2 ≤ 2(1 − γk Re(λ2 L(B̄av+ γk2 Eλmax (L(B̄tk )T L(B̄tk )))kνtk k2 ++2γk2 E ¯ ¯¯ + 1)Td(d+1)(2dkkk2λmax (B˜tk B̃t )n(z̄ − r̄ ) +6222+nσz,k+ nσr,k+ γk2 indeg(Btk )T indeg(Btk )σw,k.Îáîçíà÷èìk TkQk = 2(1 − γk Re(λ2 L(B̄av) ) − γk Re(λ2 L(B̄av))++ γk2 Eλmax (L(B̄tk )T L(B̄tk ))),∆k =2γk2 E ¯ ¯Td(d + 1)(2d¯ + 1)kk 2k˜kλmax (Bt B̃t )n(z̄ − r̄ ) +6222+ nσz,k+ nσr,k+ γk2 indeg(Btk )T indeg(Btk )σw,k.Ïðîâîäÿ ðàññóæäåíèÿ àíàëîãè÷íî Ëåììå 1 èç âòîðîé ãëàâû [39], ïîëó÷àåìkkEkνt+1k2 ≤ Qk kνtk k2 + ∆k ≤ Qk (Qk kνt−1k2 + ∆k ) + ∆k ≤ .

. .59≤k 2Qt+1k kν0 k+ ∆ k + ∆ k Qk +. . . ∆k Qtk=k 2Qt+1k kν0 k1 − Qt+1k.+ ∆k1 − QkÏî ïðåäïîëîæåíèþ A3 |Qk | < 1. Ïðè t → ∞ ïîëó÷àåìkEkνt+1k2 ≤2.4.3∆k.1 − QkÎïòèìèçàöèÿ ðàçìåðà øàãà àëãîðèòìàÒ å î ð å ì à 6. Åñëè âûïîëíåíû ïðåäïîëîæåíèÿ A1A3 è ñòîèìîñòíûå îãðàíè÷åíèÿ (2.16), òî îïòèìàëüíûå çíà÷åíèÿ øàãîâ γk? ,k = 1, . . . , m, äëÿ êàæäîãî ïðîòîêîëà èç (2.17) ìîãóò áûòü ïîëó÷åíûèç ñëåäóþùèõ ôîðìóë:(2.21)KS − Jγk? = −+JVsKS − JJV2+K,Jãäå ¯ ¯¯ + 1)Td(d+1)(2dkk2kn(z̄ − r̄ ) +J = 2E λmax (B˜tk B̃t )62+ indeg(Btk )T indeg(Btk )σw,k,k T22) )+K = nσz,k+ nσr,k, S = 2Eλmax L(B̄tk )T L(B̄tk ) , V = 4(Re(λ2 L(B̄avkRe(λ2 L(B̄av))).Äîêàçàòåëüñòâî.

Äîêàçàòåëüñòâî ïîâòîðÿåò äîêàçàòåëüñòâî Òåîðåìû 3,ñ òî÷íîñòüþ äî çàìåíû ðàçìåðà øàãà γ íà γk , ðàçëè÷àþùåãîñÿ äëÿ îáìåíà çàäàíèÿìè ðàçëè÷íûõ ïðèîðèòåòîâ; çàìåíû ìàòðèöû ïðîòîêîëà Btíà îòäåëüíûå ìàòðèöû ïðîòîêîëà Btk äëÿ îáìåíà çàäàíèÿìè êàæäîãîêëàññà k . Ïîñêîëüêó ïðè äîêàçàòåëüñòâå Òåîðåìû 3 ðàññóæäåíèÿ ïðîâîäèëèñü äëÿ êàæäîãî êëàññà çàäàíèé k îòäåëüíî, ïîäñòàíîâêà γk âìåñòî γè Btk âìåñòî Bt êîððåêòíà.60 âûáðàííûõ îáîçíà÷åíèÿõ∆k=1 − QkJγk2 + K.1 − (Sγk2 − V γk + 2)Íàéäåì íàèìåíüøèå âîçìîæíûå âåðõíèå ãðàíèöû äëÿ ε. Äëÿ ïðîèçâîäíîé∆k1−Qkïî γk èìååì:Jγk2 + K−Sγk2 + V γk − 1=02Jγk (−Sγk2 + V γk − 1) − (−2Sγk + V )(Jγk2 + K)=(−Sγk2 + V γk − 1)2−2JSγk3 + 2JV γk2 − 2Jγk + 2JSγk3 − JV γk2 + 2KSγk − KV=(−Sγk2 + V γk − 1)2JV γk2 + (2KS − 2J)γk − KV.=(−Sγk2 + V γk − 1)2Ïðèðàâíÿåì ÷èñëèòåëü íóëþ è ðåøèì êâàäðàòíîå óðàâíåíèå:JV γk2 + (2KS − 2J)γk − KV = 0.2KS − 2J±γk = −2JVs2KS − 2J2JV2+4JKV 2(2JV )2Ó÷èòûâàÿ, ÷òî ðàçìåð øàãà γk ïîëîæèòåëüíàÿ âåëè÷èíà, â ðåçóëüòàòåïîëó÷àåì îïòèìàëüíîå çíà÷åíèå äëÿγk?KS − J=−+JVsKS − JJV2+K.JÇ à ì å ÷ à í è å 3.

Ïî ôîðìóëå (2.15) ìîæíî âûáðàòü ðàçìåðøàãà äëÿ êàæäîãî ïðîòîêîëà â (2.17), äëÿ êàæäîãî êëàññà çàäàíèé kâ îòäåëüíîñòè, ÷òî ïîçâîëÿåò áîëåå ãèáêî íàñòðàèâàòü ïîâåäåíèå ñèñòåìû.61Ãëàâà 3Èìèòàöèîííîåìîäåëèðîâàíèå èàäàïòàöèÿ ðàçìåðà øàãààëãîðèòìà3.1Ìîäåëèðîâàíèå ïîâåäåíèÿ ñåòåâîéñèñòåìû, âûïîëíÿþùåé çàäàíèÿíåñêîëüêèõ êëàññîâ, ïåðåðàñïðåäåëåííûõïî ïðîòîêîëó ëîêàëüíîãî ãîëîñîâàíèÿ (2.4)â óñëîâèÿõ ïîìåõ, çàäåðæåê,èçìåíÿþùåéñÿ ñòðóêòóðû ñâÿçåé ñåòèÐàññìîòðèì ïðèìåð ñåòè èç ïÿòè àãåíòîâ, ñîåäèíåííûõ â êîëüöî.Ïðåäïîëîæèì, ÷òî ñâÿçè ìåæäó àãåíòàìè ïðîïàäàþò ñ âåðîÿòíîñòüþ 15 , à¾äèàãîíàëüíûå¿ ñâÿçè ìîãóò ïîÿâëÿòüñÿ ñ òàêîé æå âåðîÿòíîñòüþ.

Ìàêñèìàëüíàÿ çàäåðæêà ïðè èíôîðìàöèîííîì îáìåíå d¯ ðàâíà 1, âåðîÿòíîñòüïîÿâëåíèÿ çàäåðæêè ðàâíà13è îäèíàêîâà äëÿ âñåõ ðåáåð. Ïóñòü â ñèñòåìåïðèñóòñòâóþò òðè ðàçëè÷íûõ êëàññà çàäàíèé. Äîëè ïðîèçâîäèòåëüíîñòèðàâíû 4 : 2 : 1, òî åñòü ïðè óñëîâèè, ÷òî âñå î÷åðåäè íåïóñòû, ïðîèçâîäè62òåëüíîñòü àãåíòîâ áóäåò ðàçäåëåíà ìåæäó êëàññàìè ñëåäóþùèì îáðàçîì:= 47 p, 27 p è 17 p ñîîòâåòñòâåííî. ýòîì ñëó÷àå Bav èìååò âèä:44+2+1 pBav015=451515150451515151515151504515045151515450Çàìåòèì, ÷òî â íàøåì ñëó÷àå òîïîëîãèÿ ãðàôà ñâÿçåé GBav ñáàëàíñèðîâàííàÿ.Âûáåðåì γ = 1/2.

Äëÿ Bav èìååì indegmax (Bav ) = 7/5.Ìàòðèöà B̄av âûãëÿäèò ñëåäóþùèì îáðàçîì:B̄av=021581521521521508152152158152158152000002000002000002021521502152152150815215215215000002011511511541511511511504151151154151154150000000000000000000001151151150415115115115000000.i,kÍà Ðèñ.

3.1 ïîêàçàíà çàâèñèìîñòü äëèí î÷åðåäåé çàäàíèé qtâñåõïðèîðèòåòîâ íà àãåíòàõ îò âðåìåíè â ñèñòåìå, ðàáîòàþùåé ïî îïèñàííîìó ïðîòîêîëó.  ïðèìåðå íà àãåíòîâ ïîñòóïàþò çàäàíèÿ ñî ñëîæíîñòüþâ 1 óñëîâíóþ îïåðàöèþ, à ïðîèçâîäèòåëüíîñòè àãåíòîâ ðàâíû 1 óñëîâíîéîïåðàöèè çà òàêò.Íà Ðèñ. 3.1 ïîêàçàíî òèïè÷íîå ïîâåäåíèå äëèí î÷åðåäåé àãåíòîâ äëÿðàçíûõ êëàññîâ çàäàíèé. Äëèíû î÷åðåäåé ïÿòè àãåíòîâ äëÿ êàæäîãî èç63500450400350300qi,t k250200150100500020406080100120140160180200tÐèñ.

3.1: Äëèíû î÷åðåäåé àãåíòîâ â ïðèìåðå äëÿ òðåõ êëàññîâ çàäàíèé.òðåõ êëàññîâ çàäàíèé ñõîäÿòñÿ ê îäíîìó çíà÷åíèþ, âñëåäñòâèå ïåðåðàñïðåäåëåíèÿ çàäàíèé, è óìåíüøàþòñÿ, ïîñêîëüêó ïðîèñõîäèò âûïîëíåíèåçàäàíèé è î÷åðåäè ñîêðàùàþòñÿ. ×åì áîëüøå äîëÿ ïðîèçâîäèòåëüíîñòèäëÿ êëàññà çàäàíèé, òåì áûñòðåå óìåíüøàþòñÿ ñîîòâåòñòâóþùèå ýòîìóêëàññó ñîñòîÿíèÿ àãåíòîâ, ÷òî îòðàæàåòñÿ íà ãðàôèêå â âèäå óãëà íàêëîíà òðàåêòîðèè, ê êîòîðîé ñõîäÿòñÿ äëèíû î÷åðåäåé. ¾Âñïëåñêè¿ òðàåêòîðèé âîçíèêàþò âñëåäñòâèå îêîí÷àíèÿ âûïîëíåíèÿ ñèñòåìîé çàäàíèéîäíîãî èç ïðèîðèòåòîâ.

Êàê òîëüêî íà îäíîì àãåíòå êàêàÿ-òî èç äëèíî÷åðåäåé ñòàíîâèòñÿ ðàâíà íóëþ, ïðîèçâîäèòåëüíîñòü àãåíòà, âûäåëåííàÿ ïîä ýòó î÷åðåäü, ïåðåðàñïðåäåëÿåòñÿ ìåæäó îñòàëüíûìè íåïóñòûìèî÷åðåäÿìè àãåíòà, è, êàê ñëåäñòâèå, óìåíüøàåòñÿ åãî çàãðóçêà ïî äðóãèìïðèîðèòåòàì. Ïîëó÷èâ èíôîðìàöèþ î íîâîì ñîñòîÿíèè àãåíòà, åãî ñîñåäèíà÷èíàþò ïåðåñûëàòü åìó áîëüøå çàäàíèé ñîîòâåòñòâóþùèõ ïðèîðèòåòîâ, ïî êîòîðûì çàãðóçêà àãåíòà óìåíüøèëàñü. Íî ïîñêîëüêó ïî çàãðóçêåáûë äîñòèãíóò êîíñåíñóñ (ñ çàäàííîé òî÷íîñòüþ), çàäàíèÿ ñîîòâåòñòâóþùåãî ïðèîðèòåòà âñêîðå çàêîí÷àòñÿ è íà ñîñåäÿõ, è óæå àãåíò, â ñâîþî÷åðåäü, îòäàñò ÷àñòü ïîëó÷åííûõ îò ñîñåäåé çàäàíèé, ïîñêîëüêó èõ çà64ãðóçêè âûðîâíÿþòñÿ.

Ñî âðåìåíåì àãåíòû ñíîâà ïðèäóò ê êîíñåíñóñó ïîäëèíàì î÷åðåäåé çàäàíèé îñòàëüíûõ ïðèîðèòåòîâ.3.2Ìîäåëèðîâàíèå ïîâåäåíèÿ ñåòåâîéñèñòåìû, âûïîëíÿþùåé çàäàíèÿíåñêîëüêèõ êëàññîâ ïðèîðèòåòîâ, ïðèíàëè÷èè ðàçíûõ ñòîèìîñòíûõîãðàíè÷åíèé íà èñïîëüçîâàíèå ñâÿçåé äëÿîáìåíà çàäàíèÿìè êàæäîãî êëàññàÐèñ. 3.2: Òîïîëîãèÿ ñåòåâîé ñèñòåìû.Ðàññìîòðèì ñåòü èç ïÿòè àãåíòîâ, îáëàäàþùóþ òîïîëîãèåé, èçîáðàæåííîé íà Ðèñ.

3.2. Àãåíòû îáðàçóþò äâå ãðóïïû {1, 2} è {3, 4, 5}. Ïðåäïîëîæèì, ÷òî ñâÿçü ìåæäó àãåíòàìè ïðîïàäàåò ñ âåðîÿòíîñòüþ110 .Ïóñòüñòîèìîñòü ñâÿçåé ìåæäó àãåíòàìè âíóòðè ãðóïï ñðàâíèòåëüíî íèçêàÿ èðàâíà 1, à ñòîèìîñòü ñâÿçè ìåæäó ãðóïïàìè ñðàâíèòåëüíî âûñîêà è ðàâíà 5. Íàèáîëüøàÿ çàäåðæêà ïðè ïåðåäà÷å èíôîðìàöèè ïî êàíàëàì d¯ðàâíà 1, à âåðîÿòíîñòü ïîÿâëåíèÿ çàäåðæêè îäèíàêîâà äëÿ âñåõ ñâÿçåéè ðàâíà 13 . Ïîìåõè ïðè ïåðåäà÷å äàííûõ ïî êàíàëàì ñâÿçè èìåþò íîðìàëüíîå ðàñïðåäåëåíèå ñ íóëåâûì ñðåäíèì è äèñïåðñèåé σw = 3. Ïðîèçâîäèòåëüíîñòè àãåíòîâ ðàâíû 8, 2, 1, 4 è 10 óñëîâíûõ âû÷èñëèòåëüíûõèíñòðóêöèé â åäèíèöó âðåìåíè.

Êîëè÷åñòâî çàäàíèé ïîä÷èíÿåòñÿ çàêîíóðàñïðåäåëåíèÿ Ïóàññîíà ñ ïàðàìåòðîì λ = 3. Ïóñòü â ñèñòåìó ïîñòóïàþò çàäàíèÿ äâóõ êëàññîâ. Äîëè ïðîèçâîäèòåëüíîñòè çàäàíû 2 : 1, òî åñòü65íà àãåíòå ñ íåïóñòûìè î÷åðåäÿìè ïðîèçâîäèòåëüíîñòü àãåíòîâ áóäåò ðàñïðåäåëåíà ìåæäó êëàññàìè êàê 23 p è 31 p ñîîòâåòñòâåííî.Ìàòðèöà ñåòåâîé òîïîëîãèè A èìååò ñëåäóþùèé âèä:A=0100010050000100500100100.Çàìåòèì, ÷òî ãðàô, çàäàâàåìûé òàêîé ìàòðèöåé ñáàëàíñèðîâàí. Ïóñòüíà ñèñòåìó íàëîæåíû ñëåäóþùèå ñòîèìîñòíûå îãðàíè÷åíèÿ: {ck }k=1,2 ={6, 1.5}. Ñòîèìîñòíûå îãðàíè÷åíèÿ äëÿ êëàññà 1 âûïîëíåíû, åñëè ìàò1âûáðàíà ðàâíîé A. ×òîáû óäîâëåðèöà óïðàâëÿþùåãî ïðîòîêîëà Bavòâîðèòü îãðàíè÷åíèÿì íà çàäàíèÿ êëàññà 2, íóæíî óìåíüøèòü èíòåíñèâíîñòü èñïîëüçîâàíèÿ ¾äîðîãèõ¿ ñâÿçåé 2 − 4 è 4 − 2.

Ýòîãî ìîæíî1äîñòè÷ü çà ñ÷åò ñëó÷àéíîãî èñïîëüçîâàíèÿ ñâÿçåé ñ âåðîÿòíîñòüþ 10.Ñó÷åòîì çàäåðæåê, ðàñøèðåííàÿ ìàòðèöà óïðàâëÿþùåãî ïðîòîêîëà äëÿïðèîðèòåòà 2 èìååò ñëåäóþùèé âèä:2B̄av=00 0 1 31 0000 1 23 01 211 11 23 00 5 100100503310 321 0000 13 0000 13 1 221 110 5 1000 0 5 1000 3 133 13000 1 23 0 000 1 13 0 .1000000000γ21000000000γ21000000000γ210000 00000 γ21000000000γ2Ðàñøèðåííàÿ ìàòðèöà óïðàâëÿþùåãî ïðîòîêîëà äëÿ ïðèîðèòåòà 166âûãëÿäèò ñëåäóþùèì îáðàçîì:1B̄av=0 1 23 0 0 0 0 1 13 0 0 01 23 0 0 5 23 0 1 13 0 0 5 13 0 21 0 0 0 0 13 0 0 0 0 13 0 5 23 1 23 0 0 0 5 31 1 13 0 0 210 0 0 13 0 0 0 0 13 0 .1000000000γ20 γ12 0 0 0 0 0 0 0 0 10 0 γ2 0 0 0 0 0 0 0 0 0 0 γ12 0 0 0 0 0 0 10 0 0 0 γ2 0 0 0 0 0250200150100500050100150200250Ðèñ.

3.3: Ñõîäèìîñòü ê êîíñåíñóñíûì çíà÷åíèÿì çàãðóçîê àãåíòîâ â ïðèìåðå äëÿ òðåõ êëàññîâ çàäàíèé.Íà ðèñ. 3.3 ïîêàçàíî ïîâåäåíèå çàãðóçîê àãåíòîâ â îïèñàííîé ñèñòåìå.Çàãðóçêè â íèæíåé ÷àñòè ãðàôèêà ñîîòâåòñòâóþò ïðèîðèòåòó 1, è, ïîñêîëüêó äëÿ ýòîãî ïðèîðèòåòà ðàçðåøåíî èñïîëüçîâàòü âñå ñâÿçè â ëþáîéìîìåíò âðåìåíè, çàãðóçêè àãåíòîâ âûðàâíèâàþòñÿ áûñòðåå. Êàê òîëüêîàãåíòû çàâåðøàþò âûïîëíåíèå âñåõ çàäàíèé ïðèîðèòåòà 1, îñâîáîäèâøàÿñÿ ïðîèçâîäèòåëüíîñòü íàïðàâëÿåòñÿ íà çàäàíèÿ ïðèîðèòåòà 2 è çàãðóçêà àãåíòîâ ïî ýòîìó ïðèîðèòåòó íà÷èíàåò ñîêðàùàòüñÿ áûñòðåå. Çàãðóç67êå àãåíòîâ ïî ïðèîðèòåòó 2 ñîîòâåòñòâóþò âåðõíèå ãðàôèêè. Ïîñêîëüêóèñïîëüçîâàíèå ñâÿçåé 2 − 4 è 4 − 2 äëÿ îáìåíà çàäàíèÿìè ìåæäó ãðóïïà-ìè {1, 2} è {3, 4, 5} îãðàíè÷åíî, çàãðóçêà âûðàâíèâàåòñÿ ñíà÷àëà âíóòðèãðóïï, à çàòåì, ïî ìåðå îáìåíà çàäàíèÿìè ìåæäó ãðóïïàìè, çàãðóçêàâûðàâíèâàåòñÿ âî âñåé ñèñòåìå.3.3Èññëåäîâàíèå çàâèñèìîñòèýôôåêòèâíîñòè äîñòèæåíèÿ êîíñåíñóñàâ ñåòåâîé ñèñòåìå îò âûáîðà ðàçìåðàøàãà àëãîðèòìàÏðè âûïîëíåíèè îãðàíè÷åíèé A3 íà ðàçìåð øàãà ñîñòîÿíèÿ àãåíòîââ ñèñòåìå áóäóò ñõîäèòüñÿ ê êîíñåíñóñíîìó çíà÷åíèþ.

Характеристики

Список файлов диссертации