Диссертация (1150593), страница 5
Текст из файла (страница 5)
. , t − d¯. Ïóñòü xi,t ≡ 0, i ∈ N äëÿ −d¯ ≤ t < 0. Îáîçíà÷èìX̄t ∈ Rn̄ , n̄ = n(d¯ + 1), ðàñøèðåííûé âåêòîð ñîñòîÿíèÿ äëÿ t = 0, 1, . . .,ñîñòîÿùèé èç d¯+ 1 (n)-âåêòîðîâ Xt , Xt−1 , . . . , Xt−d¯, òî åñòü âêëþ÷àþùèéâñå êîìïîíåíòû äëÿ çàäåðæåê ëþáîé äëèíû, íå ïðåâûøàþùåé d¯. Ââåäåìðàñøèðåííóþ ìàòðèöó ïðîòîêîëà óïðàâëåíèÿ (1.4) B̄t ðàçìåðà n̄ × n̄, ñîi,j+ndi,jtñòîÿùóþ èç íóëåé íà âñåõ ìåñòàõ, êðîìå |N̄ti | âõîæäåíèé b̄täëÿ âñåõi,i−ni ∈ N, j ∈ N̄ti èç n ïåðâûõ ñòðîê, êîòîðûå ðàâíû bi,j= 1/γ ât è b̄tñëåäóþùèõ nd¯ ñòðîêàõ, i = n + 1, . . . , n̄.Ìîæíî ïåðåïèñàòü óðàâíåíèå äèíàìèêè ñèñòåìû ñîãëàñíî âèäó Ëà-25ïëàñîâîé ìàòðèöû L(B̄t ):(1.6)X̄t+1 = X̄t − γL(B̄t )X̄t +−Rt + Zt + γWt0!.Ïðåäïîëîæåíèÿ.
Ïóñòü âûïîëíåíû ñëåäóþùèå óñëîâèÿ.• A1. Ãðàô GBav ÿâëÿåòñÿ ñèëüíî ñâÿçíûì (äëÿ òîãî, ÷òîáû êîíñåíñóñâ ñèñòåìå áûë äîñòèæèì è êîíñåíñóñíîå çíà÷åíèå ðàâíÿëîñü ñðåäíåìóàðèôìåòè÷åñêîìó ñîñòîÿíèé âñåõ àãåíòîâ â ñèñòåìå).• A2. a) Äëÿ ëþáûõ i ∈ N, j ∈ Nti âåêòîðû ïîìåõ íàáëþäåíèé wti,jöåíòðèðîâàííûå, íåçàâèñèìûå è îäèíàêîâî ðàñïðåäåëåííûå ñëó÷àéíûåi,jâåêòîðû ñ îãðàíè÷åííîé äèñïåðñèåé: E(wt )2 ≤ σw2 .ib) Äëÿ ëþáûõ i ∈ N, j ∈ Nmax= ∪t N̄ti ïîÿâëåíèå ¾èçìåíÿþùåéñÿ âî âðåìåíè¿ äóãè (j, i) â ãðàôå GBt íåçàâèñèìîå ñëó÷àéíîå ñîáûòèå.
Äëÿ âñåõi ∈ N, j ∈ Nti âåñà bi,jt â ïðîòîêîëå óïðàâëåíèÿ íåçàâèñèìûå ñëó÷àéi,jíûå âåëè÷èíû ñ ìàòåìàòè÷åñêèì îæèäàíèåì: Ebt = bi,j è îãðàíè÷åííîéi,jäèñïåðñèåé: E(bt − bi,j )2 ≤ σb2 . Îáîçíà÷èì Bav = EBt ñîîòâåòñòâóþùóþ ìàòðèöó ñìåæíîñòè.c) Äëÿ ëþáûõ i ∈ N, j ∈ N i ñóùåñòâóåò êîíå÷íàÿ öåëàÿ íåîòðèöàòåëüíàÿi,jâåëè÷èíà d¯ ∈ Z+ : dt ≤ d¯ ñ âåðîÿòíîñòüþ 1, è öåëî÷èñëåííûå çàäåðæêèdi,jt ÿâëÿþòñÿ íåçàâèñèìûìè îäèíàêîâî ðàñïðåäåëåííûìè ñëó÷àéíûìèi,jâåëè÷èíàìè, ïðèíèìàþùèìè çíà÷åíèÿ l = 0, .
. . , d¯ ñ âåðîÿòíîñòÿìè Dl .d) Äëÿ ëþáûõ i ∈ N, t = 0, 1, . . . ñëó÷àéíûå âåëè÷èíû z̃ti íåçàâèñèìû èèìåþò îãðàíè÷åííûå ìàòåìàòè÷åñêèå îæèäàíèÿ: Ezti ≤ z̄ , è äèñïåðñèè:E(zti − z̄)2 ≤ σz2 .e) Äëÿ ëþáûõ i ∈ N, t = 0, 1, . . . ñëó÷àéíûå âåêòîðû pit íåçàâèñèìû èñîñòîÿò èç íåçàâèñèìûõ ñëó÷àéíûõ êîìïîíåíò. Ñëó÷àéíûå âåëè÷èíû rtièìåþò ìàòåìàòè÷åñêèå îæèäàíèÿ: Erti = r̄, íå çàâèñÿùèå îò i.Êðîìå òîãî, âñå óïîìÿíóòûå â ïðåäïîëîæåíèÿõ A2.aA2.e íåçàâèñèìûå ñëó÷àéíûå âåëè÷èíû è âåêòîðû íå çàâèñÿò äðóã îò äðóãà.Çàìåòèì, åñëè ïðåäïîëîæåíèÿ A2.b è A2.c âûïîëíÿþòñÿ, òî óñðåä-26íåííàÿ ìàòðèöà B̄av = EB̄t , ñîñòîèò èç ýëåìåíòîâb̄i,jav(1.7)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, èíà÷å.Çäåñü mod îïåðàöèÿ âçÿòèÿ îñòàòêà îò äåëåíèÿ, à ÷ äåëåíèå áåçîñòàòêà. Åñëè d¯ = 0, òî B̄av = Bav .• A3. Ðàçìåð øàãà ïðîòîêîëà óïðàâëåíèÿ γ > 0 óäîâëåòâîðÿåò ñëåäóþùèì óñëîâèÿì:δ = |Re(λ2 (L(B̄av )))| − γRe(λmax (Q)) > 0,10<γ<,max{dmax (Bav ), δ}ãäå Q = ECtT Ct , Ct = L(B̄av ) − L(B̄t ).ñðåäíåâçâåøåííûé âåêòîð íà÷àëüíûõÓñðåäíåííàÿ ìîäåëü. Ïóñòü x?0 Pñîñòîÿíèé ðàçìåðíîñòè m: x?0 =ii gi x0P,i giãäå g T ëåâûé ñîáñòâåííûé âåê-òîð ìàòðèöû Bav [91], è {x?t } òðàåêòîðèè óñðåäíåííûõ ñèñòåìx?t+1 = x?t + z̄ − r̄, z̄ = [z̄], r̄ = [r̄].(1.8)Çàìåòèì, ÷òî â ñëó÷àå ñáàëàíñèðîâàííîé òîïîëîãèè ãðàôà GBav x?0 =1nPnii=1 x0 .Ðàññìîòðèì âåêòîðû X̄t? ∈ Rn̄ , t = 0, 1, .
. ., ñîñòîÿùèå èç 1n ⊗ x?t , 1n ⊗x?t−1 , . . . , 1n ⊗ x?t−d¯.Ò å î ð å ì à 1. î äîñòèæèìîñòè êîíñåíñóñàÅñëè äëÿ ñèñòåì ñ îáðàòíûìè ñâÿçÿìè (1.5) è (1.8) âûïîëíåíûïðåäïîëîæåíèÿ A1A3, òî ñïðàâåäëèâî ñëåäóþùåå íåðàâåíñòâî:(1.9)E||X̄t −X̄t? ||2∆∆t? 2≤+ (1 − γδ) ||X̄0 − X̄0 || −,γδγδ27ãäå2∆ = 2mσw2 γ 2 (n2 σb2 + ||Bav ||2 ) + n(σz,k+ (1 − Pk )2 ),òî åñòü, åñëè E||X̄0 − X̄0? ||2 < ∞, òî àñèìïòîòè÷åñêèé ñðåäíåêâàäðà-òè÷íûé ε-êîíñåíñóñ â (1.5) äîñòèãàåòñÿ ñ ε ≤∆γδ .Äîêàçàòåëüñòâî ïðèâåäåíî â [62].1.4Èñïîëüçîâàíèå ïðîòîêîëà ëîêàëüíîãîãîëîñîâàíèÿ íà ïðàêòèêå õîäå ðåøåíèÿ øèðîêîãî êðóãà ïðàêòè÷åñêèõ çàäà÷, âîçíèêàþùèõïðè ñáîðå èíôîðìàöèè â ñåíñîðíûõ ñåòÿõ [88], ïðè ðàñïðåäåëåííûõ âû÷èñëåíèÿõ [19], óïðàâëåíèè ðîáîòèçèðîâàííûìè ñåòÿìè [67], îáìåíå èíôîðìàöèåé â ìíîãîïðîöåññîðíûõ ñåòÿõ [12], ðàñïðåäåëåíèè çàäàíèé âòðàíñïîðòíûõ ñåòÿõ [79, 102], ðàñïðåäåëåííîì óïðàâëåíèè ïðîöåññàìèîáó÷åíèÿ [35], óïðàâëåíèè ðåñóðñàìè íà ïðåäïðèÿòèÿõ [42, 43] è ìíîãèõ äðóãèõ âñòàåò çàäà÷à äîñòèæåíèÿ êîíñåíñóñà.
Çàäà÷è äîñòèæåíèÿêîíñåíñóñà âîçíèêàþò ïðè ðîåâîì óïðàâëåíèè [108, 111, 114], ãðóïïîâîìóïðàâëåíèè òðàíñïîðòíûìè ñðåäñòâàìè [112]. [30] ðàññìàòðèâàåòñÿ çàäà÷à óïðàâëåíèÿ ðîåì äèíàìè÷åñêèõ îáúåêòîâ íà îñíîâàíèè ñîãëàñîâàíèÿ çíà÷åíèé ïîòåíöèàëîâ äâèæåíèÿ îáúåêòîâ âíóòðè ðîÿ. Ïîä ðîåì ïîíèìàåòñÿ ñîâîêóïíîñòü D äèíàìè÷åñêèõîáúåêòîâ di , (i = 1, . . . , n), ðåøàþùèõ çàäà÷è èç íåêîòîðîãî ìíîæåñòâàïóòåì âçàèìîäåéñòâèÿ. Ïðè ýòîì ââîäÿòñÿ ñëåäóþùèå ïðåäïîëîæåíèÿ:• Âñå äèíàìè÷åñêèå îáúåêòû di , (i = 1, . . .
, n) îäèíàêîâû.• Îáúåêò di ∈ D ìîæåò îñóùåñòâëÿòü îáìåí ñîîáùåíèÿìè ñ íåêîòîðûì ïîäìíîæåñòâîì îáúåêòîâ Di ∈ D, íàõîäÿùèõñÿ â ïðåäåëàõíåêîòîðîé çîíû, îãðàíè÷åííîé ðàäèóñîì R, êîòîðóþ îáû÷íî íàçûâàþò ¾çîíîé âèäèìîñòè¿. Ñ ïîìîùüþ òàêîãî èíôîðìàöèîííîãîîáìåíà îáúåêòó di ìîæåò áûòü äîñòóïíà èíôîðìàöèÿ î ñîñòîÿíèèîáúåêòîâ ïîäìíîæåñòâà Di .28• Îáúåêò di äâèæåòñÿ íà ðàññòîÿíèè ri îò ñâîèõ áëèæàéøèõ ñîñåäåé.• Äëÿ ðåøåíèÿ ïîñòàâëåííûõ çàäà÷ îïåðàòîð ïðåäîñòàâëÿåò êàæäîìó îáúåêòó di êàðòó ïîòåíöèàëîâ, îïðåäåëÿþùóþ ïåðñïåêòèâíîñòüäâèæåíèÿ â îïðåäåëåííîì íàïðàâëåíèè. Îäíàêî, ó îáúåêòîâ íåòñâåäåíèé î íàëè÷èè ïðåãðàä íà ïóòè ñëåäîâàíèÿ.
Ïî ìåðå äâèæåíèÿ ó êàæäîãî îáúåêòà ôîðìèðóåòñÿ ñîáñòâåííàÿ ïîòåíöèàëüíàÿêàðòèíà ìèðà.• Äâèæåíèå êàæäîãî îáúåêòà di õàðàêòåðèçóåòñÿ íàïðàâëåíèåì si èçíà÷åíèåì ïîòåíöèàëà âûáðàííîãî ïóòè wi .Äëÿ ôîðìèðîâàíèÿ óïðàâëåíèÿ êàæäûé îáúåêò ðîÿ di ∈ D â ìîìåíò âðåìåíè t = 0, 1, . . . èìååò çàøóìëåííóþ èíôîðìàöèþ î ñâîåì ñîáñòâåííîìíàïðàâëåíèè äâèæåíèÿ, óñèëåííûì (äîìíîæåííûì) íà òåêóùèé ïîòåíöèàë ñâîåãî ìàðøðóòà:yti,i = gti + vti,i ,gti = wti sit ,è, åñëè Dti 6= 0, çàøóìëåííûå íàáëþäåíèÿ î íàïðàâëåíèÿõ äâèæåíèÿñîñåäåé, òàêæå äîìíîæåííûå íà ïîòåíöèàëû ìàðøðóòîâ ñîñåäåé:ji,jiyti,j = gt−hi,j + vt , j ∈ Dt ,ti,ji,ji,iãäå vt , vt ïîìåõè, à 0 ≤ ht≤ h̄ öåëî÷èñëåííàÿ çàäåðæêà, h̄ i,ji,jìàêñèìàëüíî âîçìîæíàÿ çàäåðæêà. Ïîëîæèì vt = 0 è ht = 0 äëÿâñåõ îñòàëüíûõ ïàð (i, j), äëÿ êîòîðûõ îíè íå áûëè îïðåäåëåíû. Òàêêàê ñèñòåìà íà÷èíàåò ðàáîòó ïðè t = 0, òî íåÿâíîå òðåáîâàíèå ê ìíîi,jæåñòâó ñîñåäåé: j ∈ Dti → t − ht > 0. Êîíñåíñóñíîå ìóëüòèàãåíòíîåóïðàâëåíèå, ôîðìèðóåìîå ïî ïðîòîêîëó ëîêàëüíîãî ãîëîñîâàíèÿ çàäàåòñÿ ñëåäóþùèì ñîîòíîøåíèåì:uit=αXj∈D̄tii,ji,ibi,jt (yt − yt ),29ãäå α - âåëè÷èíà øàãà ïðîòîêîëà óïðàâëåíèÿ, D̄ti ⊂ Dt , bi,j > 0, ∀j ∈ D̄ti .Ïîëîæèì bi,j = 0 äëÿ äðóãèõ ïàð (i, j).
Äèíàìèêà èçìåíåíèÿ íàïðàâëåíèÿ äâèæåíèÿ îáúåêòà îïèñûâàåòñÿ ðàçíîñòíûì óðàâíåíèåì:sit+1 = sit + uit ,ñ óïðàâëåíèåì ui ∈ R.Àëãîðèòì ëîêàëüíîãî ãîëîñîâàíèÿ èìååò ïîòåíöèàëüíîå ïðèìåíåíèåïðè ïîäñ÷åòå ñóìì â çàäà÷å îïîçíàíèÿ ñî ñæàòèåì (compressive sensing) [31]â õîäå ôàçû ñæàòèÿ èñõîäíîãî ñèãíàëà. Çíà÷åíèÿ âåùåñòâåííîãî îäíîìåðíîãî äèñêðåòíîãî ñèãíàëà êîí÷åíîé äëèíû f èç Rn ñîñòàâëÿþò âåêòîð N × 1. Ïóñòü f âûðàæàåòñÿ â íåêîòîðîì îðòîíîðìèðîâàííîì áàçèñå{φj }Nj=1 êàêf = Φx =NXx[j]φi ,j=1ãäå x âåêòîð êîýôôèöèåíòîâ x[j], Φ = (φ1 , φ2 , .
. . φN ) ìàòðèöà, ñîñòàâëåííàÿ èç áàçèñíûõ âåêòîðîâ. Ïóñòü y âåêòîð M × 1, ïîëó÷åííûéâ ðåçóëüòàòå èçìåðåíèÿ f , â ðåçóëüòàòå äåéñòâèÿ îïåðàòîðà èçìåðåíèÿ AM × N íà âåêòîð f :y = Af.Ïðåäïîëîæèì, ÷òî âåêòîð f ïðåäñòàâèì â âèäå ëèíåéíîé êîìáèíàöèè sáàçèñíûõ âåêòîðîâ φj , è ïðè ýòîì s << N (òàêîé âåêòîð íàçûâàåòñÿs-ðàçðåæåííûì). Çàäà÷à îïîçíàíèÿ ñî ñæàòèåì (compressive sensing) ñîñòîèò â ïðîåêòèðîâàíèè òàêîé ìàòðèöû A, ÷òîáû ëþáîé s-ðàçðåæåííûéâåêòîð ðàçìåðà N ìîã áûòü ¾ñæàò¿ äî ðàçìåðà M áåç ñóùåñòâåííîé ïîòåðè èíôîðìàöèè; è â ïðîåêòèðîâàíèè àëãîðèòìà âîññòàíîâëåíèÿ x ïîñæàòîìó ñèãíàëó y [29]. Ïðè ýòîì A âûáèðàåòñÿ ñëó÷àéíî ïî íåêîòîðûìïðàâèëàì. Êîìïîíåíòû âåêòîðà y ïðè ýòîì ìîãóò âû÷èñëÿòüñÿ ïàðàëëåëüíî, íåçàâèñèìî äðóã îò äðóãà. Ïî ñóòè îïåðàöèÿ êîäèðîâàíèÿ f â yïðåäñòàâëÿåò ñîáîé âû÷èñëåíèå ñóììû êîìïîíåíòîâ f ñî ñëó÷àéíûìè âåñàìè.
 ñèëó ïðèðîäû ïîëó÷åíèÿ y , èçìåðåíèÿ ìîæåò áûòü ïðåäñòàâëåíî30âçàèìîäåéñòâèåì àãåíòîâ ïî âû÷èñëåíèþ êîìïîíåíòîâ y .Ïðîòîêîë ëîêàëüíîãî ãîëîñîâàíèÿ ìîæåò ïðèìåíÿòüñÿ ïðè ïîñòðîåíèè RAID-ïîäîáíûõ ðàñïðåäåëåííûõ ñèñòåì õðàíåíèÿ äàííûõ [44]. Ïóñòüâ ñèñòåìå èç n àãåíòîâ, i, i = 1, . . . , n íîìåð àãåíòà, t âðåìÿ, N ={1, . . . , n} ìíîæåñòâî àãåíòîâ, õðàíÿòñÿ äàííûå, ïðåäñòàâëåííûå ÷èñëàìè.
Îáîçíà÷èì xitk , ytik ÷èñëà íà àãåíòå ïîä íîìåðîì i â ìîìåíòâðåìåíè tk . Ïðè âû÷èñëåíèè è õðàíåíèè m âèäîâ êîíòðîëüíûõ ñóìì îòäàííûõ íà àãåíòàõ öåëîñòíîñòü äàííûõ áóäåò ñîõðàíÿòüñÿ, åñëè â ñèñòåìå äàííûå íàõîäÿòñÿ íà (n − m) àãåíòàõ.Ïóñòü äàííûå ïåðåäàþòñÿ áåç ïîìåõ, çàäåðæåê, è íà àãåíòàõ õðàíèòñÿ ïî îäíîìó ÷èñëó. Ðàñ÷åò êîíòðîëüíûõ ñóìì ïðîõîäèò â çàäàííûåèíòåðâàëû âðåìåíè.
 íà÷àëå èíòåðâàëà ïðîèñõîäèò âû÷èñëåíèå çíà÷åíèÿ öåëî÷èñëåííîé ôóíêöèè f îò ÷èñëà íà àãåíòå è ïîëó÷åííîå çíà÷åíèåñîõðàíÿåòñÿ â çàðàíåå çàðåçåðâèðîâàííîé îáëàñòè ïàìÿòè:y0i = f (xitk ), i ∈ N.Äàëåå ïðîèçâîäèòñÿ ïåðåñ÷åò çíà÷åíèé yti ïî àëãîðèòìó ëîêàëüíîãîãîëîñîâàíèÿ:iyti = yt−1+ uit , i ∈ N,X i,j i,jiut = αbt (yt − yti,i ), i ∈ N.j∈NtiPlim yti =t→∞Ïî îïðåäåëåíèþ ïðåäåëà:j∈Ny0j|N |= y ? , i ∈ N.X j iyt |N | −y0 < ε|N |, i ∈ N, t < t0 .j∈Nj ñëó÷àå âûáîðà ε|N | < 0, 5 â ñèëó öåëî÷èñëåííîñòè y0 , ïðè îêðóã-y0j .Ïóñòü f (xitk ) = ±xitk , i ∈ N , m ≤ |N |. Îáîçíà÷èì xtk = (x1tk , x2tk , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
