Автореферат (1150592), страница 3
Текст из файла (страница 3)
. . m, t = 0, 1, . . ., äèíàìèêà ñåòåâîé ñèñòåìû îïðåäåëÿåòñÿâûïîëíÿåìîå íà àãåíòåÄëÿ âñåõñëå-äóþùèì îáðàçîì:qkt+1 = qkt − pkt + zkt + ukt ,9(1)zkt = [zti,k ] âåêòîðû ðàçìåðíîñòè n, pi,kîáîçíà÷àåò êîëè÷åñòâîti,kçàäàíèé ïðèîðèòåòà k , âûïîëíåííûõ àãåíòîì i â ìîìåíò âðåìåíè t, i-é ýëåìåíò ztîáîçíà÷àåò ÷èñëî íîâûõ çàäàíèé êëàññà k , ïîñòóïèâøèõ â ñèñòåìó íà àãåíòà i â ìînkìåíò âðåìåíè t; ut ∈ R ÿâëÿåòñÿ âåêòîðîì óïðàâëÿþùèõ âîçäåéñòâèé ðàçìåðíîñòèn (ñîñòîèò èç ïåðåðàñïðåäåëåííûõ íà àãåíòîâ çàäàíèé êëàññà k â ìîìåíò âðåìåíèt), êîòîðûé ñëåäóåò âûáèðàòü îñíîâûâàÿñü íà èíôîðìàöèè î äëèíàõ î÷åðåäåé íài,jj,kiiñîñåäíèõ àãåíòàõ qt , j ∈ Nt , ãäå Nt ìíîæåñòâî {j ∈ N : at > 0}.ãäåpkt = [pi,kt ],è òàêîé ïîñòàíîâêå ìîæíî ðåøàòü çàäà÷ó äîñòèæåíèÿ êîíñåíñóñà äëÿ ñîñòîÿíèéàãåíòîâxi,ktïî êàæäîìó óðîâíþ ïðèîðèòåòàk,ãäåi,ki,kxi,kt = qt /pavÄëÿ áàëàíñèðîâêè çàãðóçêè ñåòè (÷òîáû ïîâûñèòü îáùóþ ïðîèçâîäèòåëüíîñòüñåòè è óìåíüøèòü òàêèì îáðàçîì âðåìÿ çàâåðøåíèÿ âûïîëíåíèÿ âñåõ çàäàíèé) åñòåñòâåííî èñïîëüçîâàòü ïðîòîêîë ïåðåðàñïðåäåëåíèÿ çàäàíèé âî âðåìÿ ðàáîòû ñåòè.Ïðåäïîëîæèì, ÷òî äëÿ ôîðìèðîâàíèÿ óïðàâëÿþùåé ñòðàòåãèèi ∈ Nuit êàæäûé àãåíòîïèðàåòñÿ íà çàøóìëåííûå äàííûå î ñîñòîÿíèÿõ ñîñåäåé, êîòîðûå òàêæåyti,j,k = xj,k+ wti,j,k , j ∈ Nti , ãäå wti,j,k âåêòîðt−di,jt¯ ìàêñèìàëüíî âîçìîæíàÿöåëî÷èñëåííûå çàäåðæêè, à dìîãóò ïðèõîäèòü ñ çàäåðæêîé:ïîìåõ,0 ≤ di,j≤ d¯ tçàäåðæêà.(Ω, F, P) âåðîÿòíîñòíîå ïðîñòðàíñòâî, îáðàçîâàííîå ïðîñòðàíñòâîì ýëåìåíòàðíûõ ñîáûòèé Ω, íàáîðîì âñåõ âîçìîæíûõ ñîáûòèé F , è âåðîÿòíîñòíîé ìåðîéP ñîîòâåòñòâåííî, E ñèìâîë ìàòåìàòè÷åñêîãî îæèäàíèÿ.Ðàññìîòðèì ñëåäóþùåå ñåìåéñòâî ïðîòîêîëîâ.
Äëÿ êàæäîãî k = 1, . . . , m äëÿkäåêîìïîçèöèè òîïîëîãèè {Gt } äëÿ ñòîèìîñòíûõ îãðàíè÷åíèé {ck }, ck > 0Ïóñòüi,kui,kt = γpavXi,j,kbi,j− xi,kt (ytt ),(2)j∈N̄tiãäåiγ>0 ýòî øàã ïðîòîêîëà óïðàâëåíèÿ, àN̄ti ⊂ Nti ìíîæåñòâî ñîñåäåé óçëà(çàìåòèì, ÷òî ìîæíî èñïîëüçîâàòü íå âñå äîñòóïíûå ñâÿçè, à ëèøü íåêîòîðîå èõïîäìíîæåñòâî),bi,jt êîýôôèöèåíòû ïðîòîêîëà. Èñïîëüçóÿ ïðîòîêîë (2), ñèñòåìàðàáîòàåò òàêèì îáðàçîì, ÷òî çàäàíèÿ îäíîãî ïðèîðèòåòà ðàñïðåäåëÿþòñÿ ìåæäóàãåíòàìè ðàâíîìåðíî.
ÏóñòüBt = [bi,jt ] ìàòðèöà ïðîòîêîëà ïåðåðàñïðåäåëåíèÿi,jbi,j/ N̄ti .) Ïît = 0, êîãäà at = 0 èëè j ∈ïîñòðîåíèþ ìàòðèöû Bt , ñîîòâåòñòâóþùèé ãðàô GBt áîëüøóþ ÷àñòü âðåìåíè áóäåòèìåòü òàêóþ æå òîïîëîãèþ, êàê ãðàô GAt , çàäàâàåìûé ìàòðèöåé At , èëè áîëååçàäàíèé â ìîìåíò âðåìåíèt.(Ïîëîæèìðàçðåæåííóþ.10Äèíàìèêà ñèñòåìû ñ îáðàòíûìè ñâÿçÿìè, ôóíêöèîíèðóþùåé ïî ïðîòîêîëó (2),áóäåò èìåòü ñëåäóþùèé âèä:i,ki,kxi,kt − rt + z̃t + γnXji,kbi,jt xt − γindegi (Bt )xt + γj=1ãäånXi,j,kbi,j, i ∈ N, k = 1 . . . m,t wt(3)j=1i,ki,ki,ki,krti,k = pi,kt /pav , z̃t = zt /pav .Âîâòîðîé ãëàâå çàäà÷à áàëàíñèðîâêè çàãðóçêè óçëîâ âû÷èñëèòåëüíîé ñåòè ñçàäà÷àìè ðàçíûõ ïðèîðèòåòîâ ôîðìóëèðóåòñÿ â âèäå çàäà÷è äîñòèæåíèÿ äèôôåðåíöèðîâàííîãî êîíñåíñóñà, ïðèâîäÿòñÿ îñíîâíûå òåîðåòè÷åñêèå ðåçóëüòàòû.Ïðåäïîëîæèì, ÷òî âûïîëíåíû ñëåäóþùèå óñëîâèÿ.•A1.
Ãðàô GBavÿâëÿåòñÿ ñèëüíî ñâÿçíûì (äëÿ òîãî, ÷òîáû êîíñåíñóñ â ñèñòåìåáûë äîñòèæèì è êîíñåíñóñíîå çíà÷åíèå ðàâíÿëîñü ñðåäíåìó àðèôìåòè÷åñêîìó ñîñòîÿíèé âñåõ àãåíòîâ â ñèñòåìå).•A2. a) Äëÿ ëþáûõ i ∈ N,j ∈ Ntiâåêòîðû ïîìåõ íàáëþäåíèéwti,j,köåíòðè-ðîâàííûå, íåçàâèñèìûå è îäèíàêîâî ðàñïðåäåëåííûå ñëó÷àéíûå âåêòîðû ñîãðàíè÷åííîé äèñïåðñèåé:2E(wti,j,k )2 ≤ σw,k.i= ∪t N̄ti ïîÿâëåíèå ¾èçìåíÿþùåãîñÿ âî âðåìåíè¿b) Äëÿ ëþáûõ i ∈ N, j ∈ Nmax(j, i) â ãðàôå GBt íåçàâèñèìîå ñëó÷àéíîå ñîáûòèå.
Äëÿ âñåõ i ∈ N, j ∈Nti âåñà bi,jt â ïðîòîêîëå óïðàâëåíèÿ íåçàâèñèìûå ñëó÷àéíûå âåëè÷èíû ñi,ji,ji,jìàòåìàòè÷åñêèì îæèäàíèåì: Ebt = bè îãðàíè÷åííîé äèñïåðñèåé: E(bt −bi,j )2 ≤ σb2 .ðåáðàc)i ∈ N, j ∈ N i ñóùåñòâóåò êîíå÷íàÿ öåëàÿ íåîòðèöàòåëüíàÿi,j¯d¯ ∈ Z+ : di,jt ≤ d ñ âåðîÿòíîñòüþ 1, è öåëî÷èñëåííûå çàäåðæêè dtÄëÿ ëþáûõâåëè÷èíàÿâëÿþòñÿ íåçàâèñèìûìè îäèíàêîâî ðàñïðåäåëåííûìè ñëó÷àéíûìè âåëè÷èíàìè, ïðèíèìàþùèìè çíà÷åíèÿd)Äëÿ ëþáûõl = 0, . . . , d¯ ñâåðîÿòíîñòüþk = 1, . . . , m, i ∈ N, t = 0, 1, . . .Dli,j .ñëó÷àéíûå âåëè÷èíûíåçàâèñèìû è èìåþò îãðàíè÷åííûå ìàòåìàòè÷åñêèå îæèäàíèÿi,käèñïåðñèè: E(z̃te)k 2− z̄ ) ≤z̃ti,kEz̃ti,k ≤ z̄ kè2σz,k.i ∈ N, t = 0, 1, .
. . ñëó÷àéíûå âåëè÷èíû rti,k íåçàâèñèìû äëÿi,kîäíîãî çíà÷åíèÿ k . Ñëó÷àéíûå âåëè÷èíû r̃t , k = 1, . . . , m, èìåþò ìàòåìàòèi,kk2÷åñêèå îæèäàíèÿ: Er̃t = r̄ è äèñïåðñèè σr,k .Äëÿ ëþáûõ11Çàìåòèì, åñëè ïðåäïîëîæåíèÿìàòðèöàB̄av = EB̄t ,b̄i,javÇäåñüÅñëè•A3.A2.bèA2.câûïîëíÿþòñÿ, òî óñðåäíåííàÿñîñòîèò èç ýëåìåíòîâi,j mod n i,j mod nDj÷nb, åñëè i ∈ N, j mod n 6= 0 Di,n bi,n , åñëè i ∈ N, j mod n = 0j÷n=1/γ, åñëè i = n + 1, . . . , n̄, j = i − n, 0, èíà÷å.(4)mod îïåðàöèÿ âçÿòèÿ îñòàòêà îò äåëåíèÿ, à ÷ äåëåíèå áåç îñòàòêà.d¯ = 0, òî B̄av = Bav .γ > 0Ðàçìåð øàãà ïðîòîêîëà óïðàâëåíèÿóäîâëåòâîðÿåò ñëåäóþùèìóñëîâèÿì:E 2(1 − γλ2 (L(B̄t )))2 < 1èγ≤1indegmax (B̄av ).(5)Óñðåäíåííàÿ ìîäåëü.Ïóñòü{Xt?,k }, k = 1 . .
. m òðàåêòîðèè óñðåäíåííûõ ñèñòåì?,kXt+1= Xt?,k + Z̄ k − R̄k ,ãäån-ìåðíûåâåêòîðûZ̄ k = [z̄ k ]çàäàííûõ â ïðåäïîëîæåíèÿõèR̄k = [r̄k ](6)ñîñòîÿò èç ìàòåìàòè÷åñêèõ îæèäàíèé,A2.d, A2.e.Äèôôåðåíöèðîâàííûé êîíñåíñóñ.TÒ å î ð å ì à 1. ÅñëèïðåäïîëîæåíèÿTT?,k?,kX̄t?,k = 1d+1⊗ (Xt?,k , Xt−1.
. . Xt−)T ∈ Rn̄ , t = 0, 1, . . ..¯d¯Ðàññìîòðèì âåêòîðûäëÿ ñèñòåì ñ îáðàòíûìè ñâÿçÿìè (3) è (6) âûïîëíåíûA1A3, òîñïðàâåäëèâî ñëåäóþùåå íåðàâåíñòâî:EkX̄tk − X̄t?,k k2 ≤ Qt+1 kX̄0k − X̄0?,k k2 + ∆ãäå1 − Qt+1,1−QQ = 2 1 − γRe(λ2 L(B̄av )T ) − γRe(λ2 L(B̄av )) + γ 2 Eλmax L(B̄t )T L(B̄t )2∆ = 2γ E d(¯ d¯ + 1)(2d¯ + 1)λmax (B̃tT B̃t )6kk 2n(z̄ − r̄ )(7),+222+ nσz,k+ nσr,k+ γ 2 indeg(Bt )T indeg(Bt )σw,k.òî åñòü, åñëèEkX̄0k − X̄0?,k k2 < ∞,òî àñèìïòîòè÷åñêèé ñðåäíåêâàäðàòè÷íûé12ε-êîíñåíñóñâ (3) äîñòèãàåòñÿ ñε≤∆äëÿ êàæäîãî ïðèîðèòåòà1−Qk.Ò å î ð å ì à 2. Åñëè âûïîëíåíû ïðåäïîëîæåíèÿ A1A3 òî îïòèìàëüíîå çíà÷åíèå øàãàγ ?,äëÿ ïðîòîêîëà èç (2) ìîæåò áûòü ïîëó÷åíî èç ñëåäóþùåé ôîðìóëû:KS − Jγ? = −+JVsKS − JJV2+K,J(8)ãäåJ = 2E d(¯ d¯ + 1)(2d¯ + 1)λmax (B̃tT B̃t )6kk 2n(z̄ − r̄ )2+ indeg(Bt )T indeg(Bt )σw,k,22K = nσz,k+nσr,k, S = 2Eλmax L(B̄t )T L(B̄t ) , V = 4(Re(λ2 L(B̄av )T )+Re(λ2 L(B̄av ))).Îïðåäåëèì òåïåðü ñòîèìîñòü âûáðàííîé òîïîëîãèèiðàçîì: C({Nt , i∈ N }) = maxi∈N{Nti , i ∈ N }ñëåäóþùèì îá-i,jj∈Nti at .PÇàäàíèÿ îáëàäàþò ðàçëè÷íûìè ïðèîðèòåòàìè è äëÿ êàæäîãî ïðèîðèòåòà îïðåäåëåíà ìàêñèìàëüíàÿ ðàçðåøåííàÿ ñòîèìîñòü ñåòåâîãî ãðàôà.
 êàæäûé ìîìåíòt áóäåì ðàññìàòðèâàòü m ñïîñîáîâ (êîòîðûå ìîãóò ðàçëè÷àòüñÿ, è êàæäûémkèç êîòîðûõ ñîîòâåòñòâóåò îäíîìó óðîâíþ ïðèîðèòåòà) âûáðàòü ïîäãðàô Gt : Gt ⊂Gtm−1 ⊂ . . . ⊂ Gt1 ãðàôà GAt , ïîçâîëÿþùèé èñïîëüçîâàòü ïðîòîêîë äëÿ ïåðåðàñkïðåäåëåíèÿ çàäàíèé ïðèîðèòåòà k, k = 1, . . . , m. Îáîçíà÷èì Bt ñîîòâåòñòâóþùèåkìàòðèöû ñìåæíîñòè. Çàìåòèì, ÷òî îäèí èç âîçìîæíûõ ñïîñîáîâ âûáîðà Gt èñïîëüçîâàòü GAt äëÿ âñåõ k .Ïóñòü ck , k = 1, . . .
, m, ìàêñèìàëüíàÿ ñðåäíÿÿ ñòîèìîñòü ñåòåâûõ ñâÿçåé äëÿçàäàíèé ñ ïðèîðèòåòîì k . Ïîëîæèì, c1 ≥ c2 ≥ . . . cm > 0.Îïðåäåëåíèå Áóäåì ãîâîðèòü, ÷òî äåêîìïîçèöèÿ òîïîëîãèè ñåòè {Gtk } óäîâëåòâîðÿåò îãðàíè÷åíèÿì íà ñðåäíþþ ñòîèìîñòü {ck }, åñëè äëÿ êàæäîãî êëàññàPi,j,kkkïðèîðèòåòà k âûïîëíåíî: dmax (Bav ) = Edmax (Bt ) = E maxi∈N≤ ck , ãäåj∈Nti,k bti,kNt ìíîæåñòâî ñîñåäåé àãåíòà i â ìîìåíò âðåìåíè t, îáðàçîâàííîå â ñîîòâåòñòâèèkñ òîïîëîãèåé Gt .âðåìåíèÁóäåì ðàññìàòðèâàòü ïðîòîêîëû óïðàâëåíèÿ, óäîâëåòâîðÿþùèå îïðåäåëåííîìóîãðàíè÷åíèþ íà ñòîèìîñòü òîïîëîãèè äëÿ êàæäîãî îòäåëüíîãî óðîâíÿ ïðèîðèòåòà.Ò å î ð å ì à 3. Åñëè âûïîëíåíû ïðåäïîëîæåíèÿ A1A3 è ñòîèìîñòíûå îãðàíè÷åíèÿ,òî äëÿ ñðåäíåêâàäðàòè÷åñêîé ðàçíîñòè νtk = EkX̄tk − X̄t?,k k2òðàåêòîðèéñèñòåì ñ îáðàòíûìè ñâÿçÿìè (3) è (6) ñïðàâåäëèâî ñëåäóþùåå íåðàâåíñòâî:13k 2Ekνtk k2 ≤ Qt+1k kν0 k + ∆kãäå1 − Qt+1k,1 − Qk(9)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 ))),∆k =2γk2 E d(¯ d¯ + 1)(2d¯ + 1)Tkk 2k˜kλmax (Bt B̃t )n(z̄ − r̄ ) +6T222+ nσz,k+ nσr,k+ γk2 indeg(Btk ) indeg(Btk )σw,k.EkX̄0k − X̄0?,k k2 < ∞,(3) äîñòèãàåòñÿ ñ ε ≤òî åñòü, åñëèòî àñèìïòîòè÷åñêèé ñðåäíåêâàäðàòè÷åñêèéε-êîíñåíñóñ∆käëÿ êàæäîãî ïðèîðèòåòà1−Qkâk.Ò å î ð å ì à 4.
Åñëè âûïîëíåíû ïðåäïîëîæåíèÿ A1A3 è ñòîèìîñòíûå îãðàíè÷åíèÿòîèç (2), ãäåîïòèìàëüíûå çíà÷åíèÿ øàãîâγçàìåíåíî íàγkèBtíàBtk ,γk? , k = 1, . . . , m,äëÿ êàæäîãî ïðîòîêîëàíàõîäÿòñÿ ïî ôîðìóëå:s2KS−JKS − JK?γk = −++(10)JVJVJ ¯ ¯T¯d(d+1)(2d+1)2kk 2,K=+ indeg(Btk )T indeg(Btk )σw,kãäå J = 2E λmax (B˜tk B̃tk )n(z̄−r̄)6kk T22))).) ) + Re(λ2 L(B̄avnσz,k+ nσr,k, S = 2Eλmax L(B̄tk )T L(B̄tk ) , V = 4(Re(λ2 L(B̄avÂòðåòüåé ãëàâåïðèâîäÿòñÿ ðåçóëüòàòû èìèòàöèîííîãî ìîäåëèðîâàíèÿ, èë-ëþñòðèðóþùèå ïîëó÷åííûå ðåçóëüòàòû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
