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

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

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

 òîì ñëó÷àå, êîãäà âàæíî, ÷òîáû àãåíòû áûñòðåå îá49ìåíèâàëèñü çàäàíèÿìè â ñèñòåìå, ìîæíî óâåëè÷èòü ðàçìåð øàãà γ ,íî ïðè ýòîì ïîìåõè áóäóò îêàçûâàòü áîëüøåå âëèÿíèå íà ïîâåäåíèåñèñòåìû. Òàêèì îáðàçîì, èìååòñÿ êîìïðîìèññ ìåæäó ÷óâñòâèòåëüíîñòüþ ñèñòåìû ê ïîìåõàì è ñêîðîñòüþ îáìåíà çàäàíèÿìè â ñèñòåìå.2.4Ñòîèìîñòíûå îãðàíè÷åíèÿ íàèñïîëüçîâàíèå ñâÿçåé2.4.1Ðàíäîìèçàöèÿ èñïîëüçîâàíèÿ ñâÿçåéÏóñòü (Ω, F, P ) âåðîÿòíîñòíîå ïðîñòðàíñòâî, îáðàçîâàííîå ïðî-ñòðàíñòâîì ýëåìåíòàðíûõ ñîáûòèé, íàáîðîì âñåõ âîçìîæíûõ ñîáûòèé, èâåðîÿòíîñòíîé ìåðîé ñîîòâåòñòâåííî, E ñèìâîë ìàòåìàòè÷åñêîãî îæèäàíèÿ.Ïðåäïîëîæèì, ÷òî ãðàôû GAt , t = 0, 1, .

. . íåçàâèñèìû è îäèíàêîâîðàñïðåäåëåíû, òî åñòü ñëó÷àéíûå ñîáûòèÿ ïîÿâëåíèÿ ðåáðà (j, i) íåçàâèi,jñèìû è ñëó÷àéíûå âåëè÷èíû atîäèíàêîâî ðàñïðåäåëåíû äëÿ êàæäîéäóãè (j, i). Îáîçíà÷èì ai,jav ñðåäíèå çíà÷åíèÿ (ìàòåìàòè÷åñêèå îæèäài,jíèÿ) at , Aav ñîîòâåòñòâóþùóþ ìàòðèöó ñìåæíîñòè.

Ïðåäïîëîæèì,÷òî ãðàô GAav ÿâëÿåòñÿ ñèëüíî ñâÿçíûì.Çàäàíèÿ îáëàäàþò ðàçëè÷íûìè ïðèîðèòåòàìè è äëÿ êàæäîãî ïðèî-ðèòåòà îïðåäåëåíà ìàêñèìàëüíàÿ ðàçðåøåííàÿ ñòîèìîñòü ñåòåâîãî ãðàôà.  êàæäûé ìîìåíò âðåìåíè t áóäåì ðàññìàòðèâàòü m ñïîñîáîâ (êîòîðûå ìîãóò ðàçëè÷àòüñÿ è êàæäûé èç êîòîðûõ ñîîòâåòñòâóåò îäíîìóGtm ⊆ Gtm−1 ⊆ .

. . ⊆ Gt1ãðàôà GAt , ïîçâîëÿþùèé èñïîëüçîâàòü ïðîòîêîë äëÿ ïåðåðàñïðåäåëåíèÿçàäàíèé ïðèîðèòåòà k, k = 1, . . . , m. Îáîçíà÷èì Btk ñîîòâåòñòâóþùèåìàòðèöû ñìåæíîñòè.Ïóñòü ck , k = 1, . . . , m, ìàêñèìàëüíàÿ ñðåäíÿÿ ñòîèìîñòü ñåòåâûõñâÿçåé äëÿ çàäàíèé ñ ïðèîðèòåòîì k . Ïîëîæèì, c1 ≥ c2 ≥ . . .

cm > 0.óðîâíþ ïðèîðèòåòà) âûáðàòü ïîäãðàô Gtk :Î ï ð å ä å ë å í è å 1. Áóäåì ãîâîðèòü, ÷òî äåêîìïîçèöèÿ òîïîëîãèè50ñåòè {Gtk } óäîâëåòâîðÿåò îãðàíè÷åíèÿì íà ñðåäíþþ ñòîèìîñòü {ck },åñëè äëÿ êàæäîãî êëàññà ïðèîðèòåòà k âûïîëíåíî:(2.16)Xkindegmax (Bav) = E indegmax (Btk ) = E maxi∈Nj∈Nti,kbi,j,k≤ ck ,tãäå Nti,k ìíîæåñòâî ñîñåäåé àãåíòà i â ìîìåíò âðåìåíè t, îáðàçîâàííîå â ñîîòâåòñòâèè ñ òîïîëîãèåé Gtk .Ò å î ð å ì à 4. Åñëè ãðàô GAav ÿâëÿåòñÿ ñèëüíî ñâÿçíûì, òî äëÿëþáûõ îãðàíè÷åíèé íà ñðåäíþþ ñòîèìîñòü {ck }, ck > 0, ñóùåñòâóåòäåêîìïîçèöèÿ òîïîëîãèè ñåòè {Gtk }, óäîâëåòâîðÿþùàÿ îãðàíè÷åíèÿìkíà ñðåäíþþ ñòîèìîñòü {ck } è äëÿ êîòîðîé âñå óñðåäíåííûå ãðàôû Gavÿâëÿþòñÿ ñèëüíî ñâÿçíûìè.Äîêàçàòåëüñòâî ïðèâåäåíî â [61].2.4.2Óñëîâèÿ äîñòèæèìîñòè äèôôåðåíöèðîâàííîãîêîíñåíñóñàÐàññìîòðèì ñëåäóþùåå ñåìåéñòâî ïðîòîêîëîâ.

Îïðåäåëèì äëÿ êàæäîãî k = 1, . . . , m äëÿ äåêîìïîçèöèè òîïîëîãèè {Gtk } äëÿ ñòîèìîñòíûõîãðàíè÷åíèé {ck }, ck > 0(2.17)ui,kt=γk pi,kavXj∈N̄tibi,j,k(yti,j,k − xi,ktt ),i,k⊂ Nti,k ìíîæåñòâîñîñåäåé óçëà i, äîñòóïíûõ äëÿ îáìåíà çàäàíèÿìè ïðèîðèòåòà k â ìîìåíò âðåìåíè t (çàìåòèì, ÷òî ìîæíî èñïîëüçîâàòü íå âñå äîñòóïíûå ñâÿi,j,kçè, à ëèøü íåêîòîðîå èõ ïîäìíîæåñòâî), bt êîýôôèöèåíòû ïðîòîêîëà. Èñïîëüçóÿ ïðîòîêîë (2.17), ñèñòåìà ðàáîòàåò òàêèì îáðàçîì, ÷òîçàäàíèÿ îäíîãî ïðèîðèòåòà ðàñïðåäåëÿþòñÿ ìåæäó àãåíòàìè ðàâíîìåði,j,kíî. Ïóñòü Btk = [bt ] ìàòðèöà ïðîòîêîëà ïåðåðàñïðåäåëåíèÿ çàäàíèéãäå γk > 0 øàã ïðîòîêîëà óïðàâëåíèÿ, à N̄t51â ìîìåíò âðåìåíè t, ñôîðìèðîâàííàÿ ñ ó÷åòîì îãðàíè÷åíèé íà ñðåäíþþi,j,k= 0, êîãäà ai,j/ N̄ti .) Ãðàô GBtk , ñîîòâåòt = 0 èëè j ∈ñòâóþùèé ìàòðèöå Btk , áóäåò èìåòü òàêóþ æå òîïîëîãèþ, êàê ãðàô GAt ,çàäàâàåìûé ìàòðèöåé At , èëè áîëåå ðàçðåæåííóþ ïî ïîñòðîåíèþ ìàòðèöû Btk .ñòîèìîñòü ck .

(btÒ å î ð å ì à 5. Åñëè âûïîëíåíû ïðåäïîëîæåíèÿ A1A3 è ñòîèìîñòíûå îãðàíè÷åíèÿ (2.16), òî äëÿ ñðåäíåêâàäðàòè÷åñêîé ðàçíîñòèEkνtk k2 = EkX̄tk −X̄t?,k k2 òðàåêòîðèé ñèñòåì ñ îáðàòíûìè ñâÿçÿìè (2.5)è (2.11) ñïðàâåäëèâî ñëåäóþùåå íåðàâåíñòâî:(2.18)Ekνtk k2≤k 2Qt+1k kν0 k1 − Qt+1k+ ∆k,1 − QkãäåTkkQk = 2(1 − γk Re(λ2 L(B̄av) ) − γk Re(λ2 L(B̄av))++ γk2 Eλmax (L(B̄tk )T L(B̄tk ))), ¯ ¯¯ + 1)Td(d+1)(2dn(z̄ k − r̄k )2 +∆k = 2γk2 E λmax (B˜tk B̃tk )6T222+ nσz,k+ nσr,k+ γk2 indeg(Btk ) indeg(Btk )σw,k.òî åñòü, åñëè EkX̄0k − X̄0?,k k2 < ∞, òî àñèìïòîòè÷åñêèé ñðåäíåêâàäðà-òè÷åñêèé ε-êîíñåíñóñ â (2.5) äîñòèãàåòñÿ ñ(2.19)ε≤∆k1 − Qkäëÿ êàæäîãî ïðèîðèòåòà k .Äîêàçàòåëüñòâî.

Äîêàçàòåëüñòâî ìîæíî ïðîâåñòè àíàëîãè÷íî äîêàçàòåëüñòâó Òåîðåìû 2. Çàìåíèâ ðàçìåð øàãà γ íà γk , ðàçëè÷àþùèéñÿ äëÿîáìåíà çàäàíèÿìè ðàçëè÷íûõ ïðèîðèòåòîâ; çàìåíèâ ìàòðèöû ïðîòîêîëà52Bt íà îòäåëüíûå ìàòðèöû ïðîòîêîëà Btk äëÿ îáìåíà çàäàíèÿìè êàæäîãîêëàññà k , ïîëó÷àåì êîððåêòíûå ðàññóæäåíèÿ, ïîñêîëüêó ïðè äîêàçàòåëüñòâå Òåîðåìû 2 ðàññóæäåíèÿ ïðîâîäèëèñü äëÿ êàæäîãî êëàññà çàäàíèék îòäåëüíî.?,kÐàññìîòðèì âåêòîðû X̄t ∈ Rn̄ , t = 0, 1, . .

., óäîâëåòâîðÿþùèå óðàâíåíèþ:!kkZ̄−R̄?,k(2.20)X̄t+1= U X̄t?,k +0ãäå U ìàòðèöà ðàçìåðà n̄ × n̄:U =In 0 . . .In 0 . . .0 In . . ... ..... ..0 0 ...0 00 00 0... .. . . In 0Îáîçíà÷èì Ftk = Z̃tk − Rtk , F̄ k = Z̄ k − R̄k .Äëÿ ðàçíîñòè òðàåêòîðèé òðàåêòîðèé ñèñòåì (2.7) è (2.20) èìååì?,kkkνt+1= X̄t+1− X̄t+1= X̄tk − U Xt?,k − γk L(B̄tk )X̄tk ++Ftkk− F̄ + γk indeg0nd×1¯Btk◦Wtk!?,kÄîáàâëÿÿ è âû÷èòàÿ γk L(B̄tk )X̄t , ïîëó÷àåì   Xt?,kγk (D(Btk ) − B̃tk )X̄t?,kXtkγk (D(Btk ) − B̃tk )X̄tk k   ?,k   ?,kkXt−1   Xt   −Xtk + Xt−1  −Xt?,k + Xt−1 . − .

−−+.... ..   ..  ..   ?,k?,k?,kkkkXt−d+1−Xt−d+1Xt−d¯−Xt+d+1¯ + Xt−d¯¯¯ + Xt−d¯53γk (D(Btk ) −Xt?,k−− B̃tk )X̄t?,k?,k+ Xt−1Ftk+...?,k?,k−Xt−¯ + Xt−d¯d+1k− F̄ + γkindeg(Btk0nd×1¯◦!Wtk ),¯ãäå B̃tk ìàòðèöà n×n(d+1), ñîñòîÿùàÿ èç n ïåðâûõ ñòðîê ìàòðèöû B̄tk .?,kíà νtk :kγk indeg(BtkÇàìåíèì â ïîëó÷èâøåìñÿ âûðàæåíèè X̄tk − X̄tνtk − γk L(B̄tk )νtk −γk (D(Btk )−B̃tk )X̄t?,k!+0nd×1¯+Ftk− F̄ +0nd×1¯◦!Wtk )?,k?,kÐàññìîòðèì âûðàæåíèå γk (D(Btk ) − B̃tk )X̄t . γk (D(Btk ) − B̃tk )X̄tγk (D(Btk ) −Xt?,k ?,k k Xt−1 B̃t )  . . .

?,kXt−d¯= γk (D(Btk ) −=?,kXt−+ d¯F̄ kd¯ ?,kk¯k Xt−d¯ + (d − 1)F̄ B̃t ) ....?,kXt−d¯=?,kó÷èòûâàÿ, ÷òî (D(Btk ) − B̃tk ) · 1n(d+1)xt−d¯ = 0, ïîñêîëüêó (D(Btk ) − B̃tk )¯ åãî ñîáñòâåííûé ïåðâûå n ñòðîê ëàïëàñèàíà L(B̄tk ) è ÷òî 1n(d+1)¯âåêòîð, ñîîòâåòñòâóþùèé íóëåâîìó ñîáñòâåííîìó çíà÷åíèþ, ïîëó÷àåì ¯d0 ¯  kk d − 1 kk  1 k= γk (D(Bt ) − B̃t )  .  ⊗ F̄  = γk B̃t  .  ⊗ F̄  . ..  .. 0d¯¯ T ⊗ F̄ k .Îáîçíà÷èì d˜ âåêòîð (0, 1, . . . d)kÐàññìîòðèì óñëîâíîå ìàòåìàòè÷åñêîå îæèäàíèå êâàäðàòà íîðìû νt+1îòíîñèòåëüíî σ -àëãåáðû âåðîÿòíîñòíûõ ñîáûòèé F̃t−1 , ïîðîæäåííîé ñëó54i,ki,j,ki,j,ki,ki,ji,k, .

. . , wt−1, z0i,k , . . . , zt−1, di,j0 , . . . , dt−1 , r0 ,i, j ∈ N.÷àéíûìè âåëè÷èíàìè x0 , w0i,ki,ji,j. . . , rt−1, bi,j0 , . . . , bt−1 , btkEF̃t−1 ||νt+1||2 =EF̃t−1 νtk − γk L(B̄tk )νtk −!γk B̃tk d˜Ftk+0nd×1¯k− F̄ +γk indeg(Btk0nd×1¯◦!2Wtk )γ B̃ k d˜22 k t = EF̃t−1 In(d+1)− γk L(B̄tk ) νtk + EF̃t−1 +¯ 0nd×1¯F k − F̄ k + γ indeg(B k ◦ W k )2ktt +EF̃t−1 t +0nd×1¯!k˜γk B̃t dTT−2EF̃t−1 νtk In(d+1)+− γk L(B̄tk )¯0nd×1¯+2EF̃t−1 νtkTk TIn(d+1)−γL(B̄)¯kt!T−2EF̃t−1γk B̃tk d˜Ftk0nd×1¯Ftkkk− F̄ +− F̄ +γk indeg(Btk0nd×1¯γk indeg(Btk0nd×1¯◦◦!Wtk )+!Wtk )=ïîñêîëüêó νtk , B̄tk èçìåðèìû îòíîñèòåëüíî F̃t−1 , è Z̃tk , Rtk , Wtk íåçàâèñèìûîòíîñèòåëüíî F̃t−12k˜ k 2 γk B̃t dk= In(d+1)− γk L(B̄t ) νt + +¯ 0nd×1¯F k − F̄ k + γ indeg(B k ◦ W k )2ktt +E t +0nd×1¯−2νtkT+2νtkTTIn(d+1)− γk L(B̄tk )¯TIn(d+1)− γk L(B̄tk ) E¯!γk B̃tk d˜0nd×1¯+!Ftk − F̄ k + γk indeg(Btk ◦ Wtk )+0nd×1¯55!Tγk B̃tk d˜−2E0nd×1¯!Ftk − F̄ k + γk indeg(Btk ◦ Wtk ).0nd×1¯Â ñèëó íåçàâèñèìîñòè Z̃tk , Rtk , Wtk , B̄tk ìåæäó ñîáîéEFtkk− F̄ +γk indeg(Btk0nd×1¯◦!Wtk )=Ftk=E− F̄0nd×1¯k!+γk indeg(Btk◦!EWtk )0nd×1¯.E(Ftk − F̄ k ) = 0, E(γk indeg(Btk ◦ EWtk )) = 0.F k − F̄ k + γ indeg(B k ◦ W k )2kt tE t = EkFtk − F̄ k +γk indeg(Btk ◦Wtk )k2 =0nd×1¯= EkFtk −F̄ k k2 +2E(Ftk −F̄ k )T γk indeg(Btk ◦EWtk )+Ekγk indeg(Btk ◦Wtk )k22= EkZ̃tk − Rtk − (Z̄ k − R̄k )k2 + 0 + γk2 indeg(Btk )T indeg(Btk )σw,k=2= Ek(Z̃tk − Z̄ k ) − (Rtk − R̄k )k2 + γk2 indeg(Btk )T indeg(Btk )σw,k≤222≤ nσz,k+ nσr,k+ γk2 indeg(Btk )T indeg(Btk )σw,k.kEF̃t−1 kνt+1k2 k2k˜ 2 + nσ 2 + nσ 2 +≤ In(d+1)− γk L(B̄t ) νt + kγk B̃tk dk¯z,kr,k2+γk2 indeg(Btk )T indeg(Btk )σw,k− 2νtkTTIn(d+1)− γk L(B̄tk )¯!γk B̃tk d˜.0nd×1¯Ðàññìîòðèì óñëîâíîå ìàòåìàòè÷åñêîå îæèäàíèå ïîëó÷åííîãî âûðàæåíèÿ îòíîñèòåëüíî σ -àëãåáðû âåðîÿòíîñòíûõ ñîáûòèé Ft−1 , ïîðîæäåííîéi,ki,j,kñëó÷àéíûìè âåëè÷èíàìè x0 , w0i,j,ki,ki,j, .

. . , wt−1, z0i,k , . . . , zt−1, di,j0 , . . . , dt−1 ,i,ki,jr0i,k , . . . , rt−1, bi,j0 , . . . , bt−1 , i, j ∈ N.kEFt−1 kνt+1k2 k2k˜ 2 + nσ 2 +≤ EFt−1 In(d+1)− γk L(B̄t ) νt + EFt−1 kγk B̃tk dk¯z,k56 22+nσr,k+ γk2 EFt−1 indeg(Btk )T indeg(Btk ) σw,k+!!k˜T γk B̃t dT−2EFt−1 νtk In(d+1)− γk L(B̄tk )=¯0nd×1¯ïîñêîëüêó B̄tk íå çàâèñèò îò Ft−1 k2k˜ 2 + nσ 2 + nσ 2 += E In(d+1)− γk L(B̄t ) νt + Ekγk B̃tk dk¯z,kr,k 2+ γk2 E indeg(Btk )T indeg(Btk ) σw,k+− 2EνtkTTIn(d+1)− γk L(B̄tk )¯!!γk B̃tk d˜0nd×1¯.Ñîãëàñíî íåðàâåíñòâó Êîøè-Áóíÿêîâñêîãî2EνtkTTIn(d+1)− γk L(B̄tk )¯!!γk B̃tk d˜≤0nd×1¯! γ B̃ k d˜ k t 2E In(d+1)− γk L(B̄tk ) νtk .¯ 0nd×1¯Â òî æå âðåìÿ2E! γ B̃ k d˜ k t − γk L(B̄tk ) νtk ≤ In(d+1)¯ 0nd×1¯2γ B̃ k d˜2 k t E In(d+1)− γk L(B̄tk ) νtk + E .¯ 0nd×1¯kÏîäñòàâèì â âûðàæåíèå äëÿ EFt−1 kνt+1k2 :kEFt−1 kνt+1k2 k2k˜ 2 + nσ 2 + nσ 2 +≤ E In(d+1)− γk L(B̄t ) νt + Ekγk B̃tk dk¯z,kr,k57+γk2 Eindeg(Btk )T indeg(Btk )2σw,k k2k+ E In(d+1)− γk L(B̄t ) νt +¯˜ 2.+ Ekγk B̃tk dk k2kÇàìåòèì, ÷òî E In(d+1)− γk L(B̄t ) νt =¯TνtkTγk L(B̄tk )γk L(B̄tk )νtk=EIn(d+1)−In(d+1)−=¯¯ T kkk Tk2k Tk= E νt In(d+1)− γk L(B̄t ) − γk L(B̄t ) + γk L(B̄t ) L(B̄t ) νt =¯ïîñêîëüêó νtk èçìåðèìî îòíîñèòåëüíî Ft−1TTTT= νtk νtk −γk νtk EL(B̄tk )T νtk −γk νtk EL(B̄tk )νtk +γk2 νtk E L(B̄tk )T L(B̄tk ) νtk =ïîñêîëüêó B̄tk íå çàâèñèò îò Ft−1TTTTk T kk= νtk νtk −γk νtk L(B̄av) νt −γk νtk L(B̄av)νtk +γk2 νtk E L(B̄tk )T L(B̄tk ) νtk ≤k Tk≤ 1 − γk λmin L(B̄av) − γk λmin L(B̄av) + γk2 Eλmax L(B̄tk )T L(B̄tk ) kνtk k2 .Tk)νtk ôàêòè÷åñêè ðàññìàòðèâàåòñÿ ïðîåêÏðè îöåíêå âûðàæåíèÿ νtk L(B̄avTköèÿ νtk L(B̄av)νtk íà ïîäïðîñòðàíñòâî, îðòîãîíàëüíîå ñîáñòâåííîìó âåê-k), êîòîðûé ñîîòâåòñòâóåò íóëåâîìó ñîáñòâåííîìó ÷èñëó ëàïëàòîðó L(B̄avñèàíà.

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

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