Диссертация (1150593), страница 6
Текст из файла (страница 6)
. . , xntk ).ëåíèè yti |N | äî áëèæàéøåãî öåëîãî ïîëó÷àåòñÿ òî÷íîå çíà÷åíèå31Pj∈NÇíà÷åíèÿ êîíòðîëüíûõ ñóìì S1 . . . Sm ðàâíû S1 =< h1 , xtk >, . . . , Sm =<hm , xtk >.  ñëó÷àå ëèíåéíîé íåçàâèñèìîñòè âåêòîðîâ h1 , . .
. , hm , âîçìîæíî âîññòàíîâëåíèå çíà÷åíèé m ÷èñåë íà ðàçëè÷íûõ àãåíòàõ.32Ãëàâà 2Îïòèìèçàöèÿ ïðîöåññàáàëàíñèðîâêè çàãðóçêèóçëîâ âû÷èñëèòåëüíîéñåòè ñ çàäà÷àìè ðàçíûõïðèîðèòåòîâ2.1Áàëàíñèðîâêè çàãðóçêè ñåòè,âûïîëíÿþùåé çàäàíèÿ ñ ðàçíûìèïðèîðèòåòàìèÏóñòü ñèñòåìà îáðàçîâàíà n àãåíòàìè, ñîòðóäíè÷àþùèìè äðóã ñ äðóãîì, è ìíîæåñòâîì çàäàíèé ðàçëè÷íûõ êëàññîâ, êîòîðûå äîëæíû áûòüâûïîëíåíû ñèñòåìîé. Çàäàíèÿ ïîñòóïèëè â ñèñòåìó íà ðàçíûõ àãåíòîâ âðàçëè÷íûå äèñêðåòíûå ìîìåíòû âðåìåíè t = 0, 1, .
. .. Àãåíòû âûïîëíÿþòïðèõîäÿùèå çàäàíèÿ ïàðàëëåëüíî. Çàäàíèÿ ìîãóò áûòü ïåðåðàñïðåäåëåíû ñðåäè àãåíòîâ çà ñ÷åò èñïîëüçîâàíèÿ îáðàòíîé ñâÿçè. Çàìåòèì, ÷òîâûïîëíåíèå çàäàíèÿ íå ìîæåò áûòü ïðåðâàíî ïîñëå òîãî, êàê îíî áûëîíàçíà÷åíî àãåíòó.Ïðåäïîëîæèì, ÷òî çàäà÷è (çàäàíèÿ) îòíîñÿòñÿ ê ðàçëè÷íûì êëàññàì(ïðèîðèòåòàì) k = 1, . .
. , m è ó êàæäîãî àãåíòà åñòü m î÷åðåäåé ïî33îäíîé íà çàäàíèÿ êàæäîãî êëàññà.Ïóñòü ïîâåäåíèå àãåíòà i ∈ N çàäàþò äâå õàðàêòåðèñòèêè:• äëèíû î÷åðåäåé çàäàíèé qti,k êàæäîãî êëàññà k â ìîìåíò âðåìåíè t,k = 1, . . . , m;• ñðåäíÿÿ ïðîèçâîäèòåëüíîñòü piav èëè ÷èñëî çàäàíèé, â ñðåäíåì âûïîëíÿåìîå àãåíòîì i â òå÷åíèå åäèíè÷íîãî âðåìåííîãî èíòåðâàëà.Àãåíòû, èìåþùèå êàæäûé ñâîþ ïðîèçâîäèòåëüíîñòü äîëæíû ðàñïðåäåëèòü åå ñðåäè âñåõ êëàññîâ çàäàíèé òàêèì îáðàçîì, ÷òîáû, ñ îäíîé ñòîðîíû, îáåñïå÷èòü î÷åðåäíîñòü âûïîëíåíèÿ çàäàíèé ñîãëàñíî èõïðèîðèòåòàì, a ñ äðóãîé ñòîðîíû (ïðèíèìàÿ âî âíèìàíèå ¾ïðîáëåìó ãîëîäàíèÿ¿) ÷òîáû çàäàíèÿ ñ íèçêèì ïðèîðèòåòîì íå ïðîñòàèâàëè ¾áåñêîíå÷íî¿, äîæèäàÿñü ñâîåé î÷åðåäè íà èñïîëíåíèå.
Òàêîãî ïîâåäåíèÿìîæíî äîáèòüñÿ çà ñ÷åò ââåäåíèÿ âåðîÿòíîñòíûõ ïðèîðèòåòîâ. Êàæäîìó êëàññó çàäàíèé ïîñòàâèì â ñîîòâåòñòâèå äîëþ ïðîèçâîäèòåëüíîñòèPk , k = 1, . . . , m, îäèíàêîâóþ äëÿ êîíêðåòíîãî êëàññà k äëÿ âñåõ àãåíòîâ. Íà êàæäîì àãåíòå çàäàíèÿ èç î÷åðåäåé áóäåì âûáèðàòü ñëó÷àéíî ñâåðîÿòíîñòüþ, çàäàâàåìîé ñëåäóþùåé ôîðìóëîé: P Pk , åñëè qti,k > 0;Pli,li,kqt >0p̃t = 0,èíà÷å.i,kÇäåñü p̃t âåðîÿòíîñòü âûáîðà íà èñïîëíåíèå àãåíòîì i çàäàíèÿ êëàññà k â ìîìåíò âðåìåíè t. Òàêèì îáðàçîì, ÷åì áîëüøå Pk , òåì âûøå âåðîÿòíîñòü âûáðàòü íà èñïîëíåíèå çàäàíèå êëàññà k .
Îòñþäà, ïðîèçâîäèòåëüíîñòü àãåíòà ðàñïðåäåëÿåòñÿ ìåæäó âñåìè êëàññàìè çàäàíèé ñëåäóþùèì îáðàçîì:(2.1)i,k ipi,kav = p̃t pav .Çäåñü pi,kav îáîçíà÷àåò ÷èñëî çàäàíèé êëàññà k , â ñðåäíåì âûïîëíÿåìîåíà àãåíòå i â òå÷åíèå åäèíè÷íîãî âðåìåííîãî èíòåðâàëà. Çàìåòèì, ÷òî34i,kïî îïðåäåëåíèþ p̃t , åñëè â ìîìåíò âðåìåíè t0 î÷åðåäü èç çàäàíèé êëàññà k 0 íà àãåíòå i0 îêàçàëàñü ïóñòà, òî âû÷èñëèòåëüíûå ðåñóðñû àãåíòà i0 ,i0 ,k 0òðåáóþùèåñÿ äëÿ âûïîëíåíèÿ pt0çàäàíèé, áóäóò ðàñïðåäåëåíû ìåæäóäðóãèìè êëàññàìè çàäàíèé ñ âåðîÿòíîñòÿìè, îòíîøåíèå êîòîðûõ ðàâíîîòíîøåíèþ äîëåé ïðîèçâîäèòåëüíîñòè Pk , k 6= k 0 äëÿ ñîîòâåòñòâóþùèõêëàññîâ çàäàíèé.Äëÿ âñåõ k = 1 . .
. m, t = 0, 1, . . . äèíàìèêà ñåòåâîé ñèñòåìû îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:qkt+1 = qkt − pkt + zkt + ukt ,(2.2)i,ki,ki,kãäå pkt = [pt ], è zkt = [zt ] âåêòîðû ðàçìåðíîñòè n, ptîáîçíà÷à-åò êîëè÷åñòâî çàäàíèé ïðèîðèòåòà k , âûïîëíåííûõ àãåíòîì i â ìîìåíòi,kâðåìåíè t, i-é ýëåìåíò zt îáîçíà÷àåò ÷èñëî íîâûõ çàäàíèé êëàññà k , ïîñòóïèâøèõ â ñèñòåìó íà àãåíòà i â ìîìåíò âðåìåíè t; ukt ∈ Rn ÿâëÿåòñÿâåêòîðîì óïðàâëÿþùèõ âîçäåéñòâèé ðàçìåðíîñòè n (ñîñòîèò èç ïåðåðàñïðåäåëåííûõ íà àãåíòîâ çàäàíèé êëàññà k â ìîìåíò âðåìåíè t), êîòîðûéñëåäóåò âûáèðàòü îñíîâûâàÿñü íà èíôîðìàöèè î äëèíàõ î÷åðåäåé íà ñîj,ki,jñåäíèõ àãåíòàõ qt , j ∈ Nti , ãäå Nti ìíîæåñòâî {j ∈ N : at > 0}.Ïîëîæèì piav 6= 0, ∀i ∈ N è Pk 6= 0, k = 1, . . .
, m.  [17] áûëîäîêàçàíî, ÷òî ìèíèìàëüíîå âðåìÿ ðàáîòû ñèñòåìû äîñòèãàåòñÿ òîãäà,êîãäà çàãðóçêà àãåíòîâ, îïðåäåëÿåìàÿ êàê îòíîøåíèå äëèíû î÷åðåäè êïðîèçâîäèòåëüíîñòè, ðàâíà íà âñåõ àãåíòàõ â ñåòè. Ñëåäîâàòåëüíî, âàæíîäîñòè÷ü ñëåäóþùåé öåëè.Öåëü óïðàâëåíèÿ ñîñòîèò â òîì, ÷òîáû ïîääåðæèâàòü ñáàëàíñèðîâàííóþ (ðàâíóþ) çàãðóçêó ïî âñåé ñåòè äëÿ âñåõ óðîâíåé ïðèîðèòåòà,óäîâëåòâîðÿÿ ïðè ýòîì òðåáîâàíèå íà îãðàíè÷åíèå ñòîèìîñòè. òàêîé ïîñòàíîâêå ìîæíî ðåøàòü çàäà÷ó äîñòèæåíèÿ êîíñåíñóñà äëÿi,kñîñòîÿíèé àãåíòîâ xt ïî êàæäîìó óðîâíþ ïðèîðèòåòà k , ãäåxi,kt=35qti,kpi,kav.Äëÿ áàëàíñèðîâêè çàãðóçêè ñåòè (÷òîáû ïîâûñèòü îáùóþ ïðîèçâîäèòåëüíîñòü ñåòè è óìåíüøèòü òàêèì îáðàçîì âðåìÿ çàâåðøåíèÿ âûïîëíåíèÿ âñåõ çàäàíèé) åñòåñòâåííî èñïîëüçîâàòü ïðîòîêîë ïåðåðàñïðåäåëåíèÿ çàäàíèé âî âðåìÿ ðàáîòû ñåòè.Ïðåäïîëîæèì, ÷òî äëÿ ôîðìèðîâàíèÿ óïðàâëÿþùåé ñòðàòåãèè uitêàæäûé àãåíò i ∈ N îïèðàåòñÿ íà çàøóìëåííûå äàííûå î ñîñòîÿíèÿõñîñåäåé, êîòîðûå òàêæå ìîãóò ïðèõîäèòü ñ çàäåðæêîé:yti,j,k = xj,k+ wti,j,k , j ∈ Nti ,t−di,j(2.3)ti,j,ki,j≤ d¯ öåëî÷èñëåííûå çàäåðæêè, à d¯ ìàêñèìàëüíî âîçìîæíàÿ çàäåðæêà.ãäå wt2.2 ïîìåõà, 0 ≤ dtÄèôôåðåíöèðîâàííûé êîíñåíñóñ [17, 62] èññëåäóþòñÿ ñâîéñòâà àëãîðèòìà óïðàâëåíèÿ, íàçûâàåìîãîïðîòîêîëîì ëîêàëüíîãî ãîëîñîâàíèÿ, äëÿ çàäà÷è áàëàíñèðîâêè çàãðóçêèâ ñòîõàñòè÷åñêîé ñåòè.
Âåëè÷èíà óïðàâëÿþùåãî âîçäåéñòâèÿ ïðîòîêîëàëîêàëüíîãî ãîëîñîâàíèÿ äëÿ êàæäîãî àãåíòà îïðåäåëÿëàñü âçâåøåííîéñóììîé ðàçíîñòåé ìåæäó èíôîðìàöèåé î ñîñòîÿíèè ñàìîãî àãåíòà è èíôîðìàöèåé î ñîñòîÿíèè åãî ñîñåäåé.Ðàññìîòðèì ñëåäóþùåå ñåìåéñòâî ïðîòîêîëîâ. Îïðåäåëèì äëÿ êàæäîãî k = 1, .
. . , m(2.4)i,kui,kt = γpavXj∈N̄tii,j,k− xi,kbi,jt ),t (ytãäå γ > 0 øàã ïðîòîêîëà óïðàâëåíèÿ, à N̄ti ⊂ Nti ìíîæåñòâî ñîñåäåé óçëà i (çàìåòèì, ÷òî ìîæíî èñïîëüçîâàòü íå âñå äîñòóïíûå ñâÿçè,i,jà ëèøü íåêîòîðîå èõ ïîäìíîæåñòâî), bt êîýôôèöèåíòû ïðîòîêîëà.Èñïîëüçóÿ ïðîòîêîë (2.4), ñèñòåìà ðàáîòàåò òàêèì îáðàçîì, ÷òî çàäàíèÿîäíîãî ïðèîðèòåòà ðàñïðåäåëÿþòñÿ ìåæäó àãåíòàìè ðàâíîìåðíî. ÏóñòüBt = [bi,jt ] ìàòðèöà ïðîòîêîëà ïåðåðàñïðåäåëåíèÿ çàäàíèé â ìîìåíò36i,ji,jâðåìåíè t. (Ïîëîæèì bt = 0, êîãäà at = 0 èëè j ∈/ N̄ti .)Ïî ïîñòðîåíèþ ìàòðèöû Bt , ñîîòâåòñòâóþùèé ãðàô GBt áîëüøóþ÷àñòü âðåìåíè áóäåò èìåòü òàêóþ æå òîïîëîãèþ, êàê ãðàô GAt , çàäà-âàåìûé ìàòðèöåé At , èëè áîëåå ðàçðåæåííóþ.Ïðåäïîëîæèì, ÷òî d¯ = 0. Òîãäà äèíàìèêà ñèñòåìû ñ îáðàòíûìè ñâÿçÿìè, ôóíêöèîíèðóþùåé ïî ïðîòîêîëó (2.4), áóäåò èìåòü ñëåäóþùèéâèä:xi,kt+1=(2.5)xi,kt−=xi,ktrti,k+−xi,ktrti,kz̃ti,k−rti,k+z̃ti,k+z̃ti,k+γj=1+γnXj=1+γnXnXjbi,jt xtj=1i,j,kbi,j− xi,kt (ytt ) =j,ki,j,kbi,j− xi,kt (xt + wtt ) =−γindegi (Bt )xi,kt+γnXi,j,kbi,j,t wtj=1i ∈ N, k = 1 .
. . m,ãäårti,k=pi,ktpi,kav,z̃ti,k=zti,kpi,kav.i,kÏåðåïèøåì (2.5) â âåêòîðíîì âèäå. Îïðåäåëèì âåêòîðû Xtk = [xt ]i=1...n ,Rtk = [rti,k ]i=1...n , Z̃tk = [z̃ti,k ]i=1...n èç ïðîñòðàíñòâà Rn , è ìàòðèöó n × nWtk = [wti,j,k ]i,j=1...n . Äèíàìèêà ñèñòåìû ñ îáðàòíûìè ñâÿçÿìè, îïåðèðóþùåé ïî ïðîòîêîëó (2.4), ìîæåò áûòü ïðåäñòàâëåíà k âåêòîðàìè è èìååòâèä:k(2.6) Xt+1= Xtk + γBt Xtk − γD(Bt )Xtk − Rtk + Ztk + γ indeg(Bt ◦ Wtk ) =k= Xt+1= Xtk − γL(Bt )Xtk − Rtk + Ztk + γ indeg(Bt ◦ Wtk ). ñëó÷àå, åñëè d¯ > 0 ìû ¾èñêóññòâåííî¿ äîáàâëÿåì nd¯ íîâûõ àãåíòîâ â èìåþùóþñÿ òîïîëîãèþ ñåòè.
 êàæäûé ìîìåíò âðåìåíè t íîâûå¾ìíèìûå¿ àãåíòû îáëàäàþò ñîñòîÿíèÿìè, ðàâíûìè ñîîòâåòñòâóþùèì ñî37ñòîÿíèÿì ¾íàñòîÿùèõ¿ àãåíòîâ äëÿ êàæäîãî êëàññà k = 1 . . . m â ïðåäûi,käóùèå ìîìåíòû âðåìåíè t − 1, t − 2, . . . , t − d¯. Ïóñòü xt≡ 0, , i ∈ Näëÿ −d¯ ≤ t < 0. Îáîçíà÷èì çà X̄tk ∈ Rn̄ , n̄ = n(d¯ + 1), ðàñøèðåííûé âåêòîð ñîñòîÿíèÿ äëÿ t = 0, 1, .
. ., ñîñòîÿùèé èç d¯ + 1 (n)-âåêòîðîâkkXtk , Xt−1, . . . , Xt−, òî åñòü âêëþ÷àþùèé âñå êîìïîíåíòû äëÿ çàäåðæåêd¯ëþáîé äëèíû, íå ïðåâûøàþùåé d¯. Ââåäåì ðàñøèðåííóþ ìàòðèöó ïðîòîêîëà óïðàâëåíèÿ (2.4) B̄t ðàçìåðà n̄ × n̄, ñîñòîÿùóþ èç íóëåé íà âñåõi,j+ndi,jtìåñòàõ, êðîìå |N̄ti | âõîæäåíèé b̄täëÿ âñåõ i ∈ N, j ∈ N̄ti èç n ïåði,ji,i−nâûõ ñòðîê, êîòîðûå ðàâíû bt è b̄t= 1/γ â ñëåäóþùèõ nd¯ ñòðîêàõ,i = n + 1, . . . , n̄.Ìîæíî ïåðåïèñàòü óðàâíåíèå äèíàìèêè ñèñòåìû ñîãëàñíî âèäó Ëàïëàñîâîé ìàòðèöû L(B̄t ):(2.7)kX̄t+1= X̄tk − γL(B̄t )X̄tk +Z̃tk−Rtk+ γ indeg(Bt ◦0nd×1¯!Wtk ).ÏðåäïîëîæåíèÿÏóñòü çàäàíî âåðîÿòíîñòíîå ïðîñòðàíñòâî (Ω, F, P ) íà ïðîñòðàíñòâåýëåìåíòàðíûõ ñîáûòèé, ìíîæåñòâå âñåõ ñîáûòèé è âåðîÿòíîñòíîé ìåðåñîîòâåòñòâåííî, à E ñèìâîë ìàòåìàòè÷åñêîãî îæèäàíèÿ.Ïðåäïîëîæèì, ÷òî ãðàôû GBt , t = 0, 1, . .
. ñëó÷àéíûå íåçàâèñèìûåè îäèíàêîâî ðàñïðåäåëåííûå, òî åñòü ñëó÷àéíûå ñîáûòèÿ íàëè÷èÿ äóãè(j, i) â ìîìåíò âðåìåíè t íåçàâèñèìû è ñëó÷àéíûå âåëè÷èíû Bti,j îäèíàêîâî ðàñïðåäåëåíû äëÿ ôèêñèðîâàííîé äóãè (j, i). Îáîçíà÷èì çà bi,javi,jñðåäíèå àðèôìåòè÷åñêèå (ìàòåìàòè÷åñêèå îæèäàíèÿ) bt , à çà Bav ñîîòâåòñòâóþùóþ ìàòðèöó ñìåæíîñòè.Ïðåäïîëîæèì, ÷òî âûïîëíåíû ñëåäóþùèå óñëîâèÿ.• A1. Ãðàô GBav ÿâëÿåòñÿ ñèëüíî ñâÿçíûì (äëÿ òîãî, ÷òîáû êîíñåíñóñâ ñèñòåìå áûë äîñòèæèì).• A2.
a) Äëÿ ëþáûõ i ∈ N, j ∈ Nti ïîìåõè íàáëþäåíèé wti,j,k öåíòðèðîâàííûå, íåçàâèñèìûå è îäèíàêîâî ðàñïðåäåëåííûå ñëó÷àéíûåi,j,k2âåëè÷èíû ñ îãðàíè÷åííîé äèñïåðñèåé: E(wt )2 ≤ σw,k.38i= ∪t N̄ti ïîÿâëåíèå ¾èçìåíÿþùåéñÿb) Äëÿ ëþáûõ i ∈ N, j ∈ Nmaxâî âðåìåíè¿ äóãè (j, i) â ãðàôå GBt íåçàâèñèìîå ñëó÷àéíîå ñîáûi,jòèå. Äëÿ âñåõ i ∈ N, j ∈ Nti âåñà bt â ïðîòîêîëå óïðàâëåíèÿ íåçàâèñèìûå ñëó÷àéíûå âåëè÷èíû ñ ìàòåìàòè÷åñêèì îæèäàíèåì:i,ji,jEbi,jè îãðàíè÷åííîé äèñïåðñèåé: E(bt − bi,j )2 ≤ σb2 .t =bc) Äëÿ ëþáûõ i ∈ N, j ∈ N i ñóùåñòâóåò êîíå÷íàÿ öåëàÿ íåîòðèi,j≤ d¯ ñ âåðîÿòíîñòüþ 1, è öåëîi,j÷èñëåííûå çàäåðæêè dt ÿâëÿþòñÿ íåçàâèñèìûìè îäèíàêîâî ðàñïðåäåëåííûìè ñëó÷àéíûìè âåëè÷èíàìè, ïðèíèìàþùèìè çíà÷åíèÿl = 0, .
. . , d¯ ñ âåðîÿòíîñòÿìè Dli,j .öàòåëüíàÿ âåëè÷èíà d¯ ∈ Z+ : dtd) Äëÿ ëþáûõ k = 1, . . . , m, i ∈ N, t = 0, 1, . . . ñëó÷àéíûå âåëè÷èi,kíû z̃t íåçàâèñèìû è èìåþò îãðàíè÷åííûå ìàòåìàòè÷åñêèå îæèäài,ki,k2íèÿ Ez̃t ≤ z̄ k è äèñïåðñèè: E(z̃t − z̄ k )2 ≤ σz,k.e) Äëÿ ëþáûõ i ∈ N, t = 0, 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
