Диссертация (1150593), страница 3
Текст из файла (страница 3)
Ïðèâîäèòñÿ îöåíêà ñðåäíåêâàäðàòè÷åñêîãî îòêëîíåíèÿ ñîñòîÿíèé àãåíòîâ â ñèñòåìå îò êîíñåíñóñíîãî çíà÷åíèÿ.  ïóíêòå 2.4.3ôîðìóëèðóåòñÿ Òåîðåìà 6 îá îöåíêå îïòèìàëüíîãî ðàçìåðà øàãà ïðåäëîæåííîé ðàíäîìèçèðîâàííîé ìîäèôèêàöèè ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ äîñòèæåíèÿ äèôôåðåíöèðîâàííîãî êîíñåíñóñà â ñèñòåìåïðè íàëè÷èè óñðåäíåííûõ ñòîèìîñòíûõ îãðàíè÷åíèé íà èñïîëüçîâàíèå13ñâÿçåé äëÿ ïåðåñûëêè çàäàíèé âíóòðè ñèñòåìû. òðåòüåé ãëàâå ïðèâîäÿòñÿ ðåçóëüòàòû èìèòàöèîííîãî ìîäåëèðîâàíèÿ, èëëþñòðèðóþùèå ïîëó÷åííûå ðåçóëüòàòû.
Ãëàâà ñîäåðæèò ÷åòûðå ÷àñòè.  ïåðâîé ÷àñòè ïðèâîäèòñÿ èëëþñòðàöèÿ òèïè÷íîãî ïîâåäåíèÿñèñòåìû, âûïîëíÿþùåé çàäàíèÿ íåñêîëüêèõ êëàññîâ, ôóíêöèîíèðóþùåéïî ïðåäëîæåííîé ðàíäîìèçèðîâàííîé ìîäèôèêàöèè ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ â óñëîâèÿõ ïîìåõ, çàäåðæåê, èçìåíÿþùåéñÿ ñòðóêòóðû ñâÿçåé ñåòè. Âî âòîðîé ÷àñòè ïðèâîäÿòñÿ ðåçóëüòàòû ìîäåëèðîâàíèÿïîâåäåíèÿ ñèñòåìû, âûïîëíÿþùåé çàäàíèÿ íåñêîëüêèõ êëàññîâ, ïðè íàëè÷èè ðàçíûõ ñòîèìîñòíûõ îãðàíè÷åíèé íà èñïîëüçîâàíèå ñâÿçåé äëÿîáìåíà çàäàíèÿìè êàæäîãî êëàññà, ïðè áàëàíñèðîâêå ïî óïðàâëÿþùåìóïðîòîêîëó, ñôîðìèðîâàííîìó ñ ó÷åòîì çàäàííûõ ñòîèìîñòíûõ îãðàíè÷åíèé.
Âî òðåòüåé ÷àñòè ïðîèëëþñòðèðîâàíà çàâèñèìîñòü ñòåïåíè äîñòèæèìîñòè êîíñåíñóñà â ñèñòåìå îò ðàçìåðà øàãà ïðåäëîæåííîãî ïðîòîêîëà. ×åòâåðòàÿ ÷àñòü ñîäåðæèò ðåçóëüòàòû èìèòàöèîííûõ ýêñïåðèìåíòîâñ èñïîëüçîâàíèåì ïîèñêîâîãî àëãîðèòìà ñòîõàñòè÷åñêîé àïïðîêñèìàöèèñ ðàíäîìèçàöèåé íà âõîäå äëÿ ïîäñòðîéêè ðàçìåðà øàãà óïðàâëÿþùåãîïðîòîêîëà âî âðåìÿ ðàáîòû âû÷èñëèòåëüíîé ñèñòåìû.  ÷åòâåðòîé ÷àñòèïðèâåäåí àëãîðèòì, èñïîëüçóåìûé äëÿ àäàïòàöèè ðàçìåðà øàãà ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ. çàêëþ÷åíèè ôîðìóëèðóþòñÿ îñíîâíûå ðåçóëüòàòû äèññåðòàöèè.14Ãëàâà 1Áàëàíñèðîâêà çàãðóçêèóçëîâ âû÷èñëèòåëüíîéñåòè ñ ïîìîùüþ ïðîòîêîëàëîêàëüíîãî ãîëîñîâàíèÿÈññëåäîâàòåëè îáû÷íî ðàññìàòðèâàþò ñåòè, îáðàçîâàííûå èç àãåíòîâ,êîîïåðèðóþùèõñÿ äëÿ âûïîëíåíèÿ îïðåäåëåííûõ çàäà÷. Àãåíòû, âçàèìîäåéñòâóþùèå âíóòðè îäíîé ñèñòåìû, íå îáÿçàòåëüíî ÿâëÿþòñÿ èäåíòè÷íûìè, òî åñòü îíè ìîãóò îáëàäàòü ðàçëè÷íîé ìîùíîñòüþ èëè ïðîèçâîäèòåëüíîñòüþ.
Çàäà÷à ïðè ýòîì çàêëþ÷àåòñÿ â ðàñïðåäåëåíèè çàäàíèéñðåäè àãåíòîâ òàêèì îáðàçîì, ÷òîáû ñèñòåìà â öåëîì ðàáîòàëà áîëåå ýôôåêòèâíî.Âîîáùå ãîâîðÿ, ìîæíî èñïîëüçîâàòü ðàçëè÷íûå ïîäõîäû äëÿ ðàñïðåäåëåíèÿ çàäàíèé â ìóëüòèàãåíòíîé ñåòè.  [57] áûëî ïîêàçàíî, ÷òî çàäà÷à îïòèìàëüíîãî (èëè ñóáîïòèìàëüíîãî) ðàñïðåäåëåíèÿ çàäàíèé â ñåòèñðåäè àãåíòîâ ìîæåò áûòü ïåðåôîðìóëèðîâàíà êàê çàäà÷à äîñòèæåíèÿêîíñåíñóñà â ñåòè. Ïîýòîìó îäíèì èç âîçìîæíûõ ïîäõîäîâ ÿâëÿåòñÿ ðàñïðåäåëåíèå çàäàíèé âíóòðè ñèñòåìû ñ ó÷åòîì òåêóùèõ çàãðóçîê è ïðîèçâîäèòåëüíîñòåé àãåíòîâ [77]. Îãðàíè÷åíèåì òàêîãî ïîäõîäà ÿâëÿåòñÿîòñóòñòâèå ó÷åòà ñïåöèôèêè çàäàíèé.
Îäíàêî íà ïðàêòèêå íåêîòîðûåçàäàíèÿ â ñèñòåìå ìîãóò èìåòü áîëåå âûñîêóþ âàæíîñòü èëè ñðî÷íîñòü,÷åì îñòàëüíûå, è â óïðàâëÿþùåé ñòðàòåãèè ñëåäóåò ïðåäóñìîòðåòü äëÿ15íèõ ðàçëè÷íûå ïðèîðèòåòû [58, 61].  ÷àñòíîñòè, âî ìíîãèõ ñåòåâûõ ñèñòåìàõ åñòü äèôôåðåíöèàöèÿ êàòåãîðèè îáñëóæèâàíèÿ. ×òîáû ðåàëèçîâàòü åå íà ïðàêòèêå, ïðåäëàãàåòñÿ ââåñòè ïîíÿòèå äèôôåðåíöèðîâàííîãîêîíñåíñóñà, ïîä êîòîðûì ïîíèìàåòñÿ äîñòèæåíèå êîíñåíñóñà â ñèñòåìàõñ íåñêîëüêèìè êëàññàìè çàäàíèé, ãäå öåëü äîñòèæåíèÿ êîíñåíñóñà ñòàâèòñÿ äëÿ êàæäîãî êëàññà è ìîæåò áûòü ðàçëè÷íîé äëÿ ðàçíûõ êëàññîâ. êîíå÷íîì ñ÷åòå, öåëü óïðàâëåíèÿ â ñåòè çàêëþ÷àåòñÿ â äîñòèæåíèèêîíñåíñóñà âíóòðè êàæäîãî êëàññà ïî îòäåëüíîñòè. [61] ðàññìàòðèâàåòñÿ ñåòü ñî ñòîèìîñòíûìè îãðàíè÷åíèÿìè íà òîïîëîãèþ ñåòè, ñî ñòðîãîé ïðèîðèòèçàöèåé çàäàíèé, òî åñòü ïðè íàëè÷èèíåñêîëüêèõ çàäàíèé íà àãåíòå â ïåðâóþ î÷åðåäü âûïîëíÿþòñÿ çàäàíèÿâûñøåãî ïðèîðèòåòà.
 ðàáîòå ïðåäëàãàåòñÿ ðàñïðåäåëÿòü çàäàíèÿ ñðåäè àãåíòîâ â ñîîòâåòñòâèè ñ ïðîèçâîäèòåëüíîñòÿìè è òåêóùèìè çàãðóçêàìè àãåíòîâ ïî êàæäîìó ïðèîðèòåòó. Íåîáõîäèìîñòü ó÷åòà ñòîèìîñòíûõ îãðàíè÷åíèÿ íà ïðàêòèêå ìîæåò âîçíèêàòü ïðè âûáîðå êàíàëîâ äëÿïåðåäà÷è äàííûõ.  [61] îïèñàíà ñòðàòåãèÿ, ïðåäóñìàòðèâàþùàÿ ïîî÷åðåäíîå âûïîëíåíèå çàäàíèé íà êàæäîì àãåíòå, èìåþùèõ ñòðîãóþ ïðèîðèòèçàöèþ.
Îïèñàííàÿ ñòðàòåãèÿ ìîæåò ïðèâåñòè ê ñíèæåíèþ ïðîèçâîäèòåëüíîñòè ñåòè, ïîñêîëüêó âëå÷åò ¾ïðîáëåìó ãîëîäàíèÿ¿ äëÿ çàäàíèéíèçêîãî ïðèîðèòåòà [73, 74, 87].  ðàáîòå [87] ïðåäëàãàåòñÿ óïðàâëÿþùàÿñòðàòåãèÿ, èñïîëüçóþùàÿ âåðîÿòíîñòíûå ïðèîðèòåòû.
Òàêàÿ ñòðàòåãèÿïîçâîëÿåò â îïðåäåëåííîé ìåðå èçáàâèòüñÿ îò ¾ïðîáëåìû ãîëîäàíèÿ¿,ïîñêîëüêó ïîçâîëÿåò ðàñïðåäåëÿòü ðåñóðñû ìåæäó ðàçíûìè êëàññàìèçàäàíèé áîëåå ãèáêî. Ñòðàòåãèÿ ïðåäïîëàãàåò ââåäåíèå âåðîÿòíîñòè âûáîðà êàæäîãî êëàññà çàäàíèé íà èñïîëíåíèå. Áîëåå îïðåäåëåííî, çàäàíèÿâûñîêîãî ïðèîðèòåòà âûïîëíÿþòñÿ ñ âûñîêîé âåðîÿòíîñòüþ, íî â òî æåâðåìÿ âåðîÿòíîñòü âûáîðà íà èñïîëíåíèå çàäàíèé íèçêîãî ïðèîðèòåòàíå ðàâíà íóëþ. Òàêèì îáðàçîì, â çàâèñèìîñòè îò ïðèîðèòåòà çàäàíèé,áóäåò âûäåëåí ðàçëè÷íûé îáúåì ðåñóðñîâ ñåòè íà èõ âûïîëíåíèå. [3] ðàññìàòðèâàåòñÿ çàäà÷à äîñòèæåíèÿ êîíñåíñóñà äëÿ àâòîíîìíîéãðóïïû ÁÏËÀ ñ ïîìîùüþ ôîðìèðîâàíèÿ ñòðàòåãèè óïðàâëåíèÿ íà îñíîâå âèðòóàëüíîé ñòðóêòóðû.  [5] ðàññìàòðèâàþòñÿ ïðèìåðû ñàìîîðãàíè16çàöèè è àäàïòàöèè â ìóëüòèàãåíòíîé ñèñòåìå îðãàíèçàöèè òðàíñïîðòíûõïåðåâîçîê è ïðè ðåøåíèè çàäà÷è áàëàíñèðîâêè çàãðóçêè óçëîâ äåöåíòðàëèçîâàííîé âû÷èñëèòåëüíîé ñåòè â óñëîâèÿõ íåïîëíîé èíôîðìàöèè î òåêóùèõ ñîñòîÿíèÿõ óçëîâ è ïåðåìåííîé ñòðóêòóðû ñâÿçåé.
 [4] äëÿ ðåøåíèÿ çàäà÷è áàëàíñèðîâêè çàãðóçêè, ïåðåôîðìóëèðîâàííîé êàê ïðîáëåìàäîñòèæåíèÿ êîíñåíñóñà â óñëîâèÿõ ïåðåìåííîé òîïîëîãèè, ïðåäëàãàåòñÿèñïîëüçîâàòü àëãîðèòì òèïà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè.  [15] äëÿèññëåäîâàíèÿ äèíàìèêè ìóëüòèàãåíòíîé ñèñòåìû ïðè ðåøåíèè çàäà÷èäîñòèæåíèÿ êîíñåíñóñà ñ èñïîëüçîâàíèåì àëãîðèòìà òèïà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè ïðåäëàãàåòñÿ èñïîëüçîâàòü ìåòîä íåïðåðûâíûõ ìîäåëåé ñõåìó Äåðåâèöêîãî-Ôðàäêîâà-Ëüþíãà.
 ñòàòüå [16] äëÿ èññëåäîâàíèÿ ïîâåäåíèÿ ñèñòåìû ïðè êîíñåíñóñíîì ìóëüòèàãåíòíîì óïðàâëåíèè,ôîðìèðóåìîì ïî ïðîòîêîëó ëîêàëüíîãî ãîëîñîâàíèÿ ñ íåóáûâàþùèì äîíóëÿ ðàçìåðîì øàãà ïðè ñëó÷àéíî èçìåíÿþùåéñÿ ñòðóêòóðå ñâÿçåé âñåòè è íàáëþäåíèÿõ ñî ñëó÷àéíûìè çàäåðæêàìè è ïîìåõàìè äëÿ àãåíòîâ ñ íåëèíåéíîé äèíàìèêîé ñîñòîÿíèé, èñïîëüçóåòñÿ ìåòîä óñðåäíåííûõ ìîäåëåé.  ñòàòüå [6] ðàññìîòðåíà çàäà÷à äèñïåò÷åðèçàöèè ñåòè ñïåðåìåííîé òîïîëîãèåé ïðè ïîìåõàõ è çàäåðæêàõ â èçìåðåíèÿõ.
 ðàáîòå [1] ïðîâåäåíî ñðàâíåíèå äèíàìèêè ðàáîòû äåöåíòðàëèçîâàííîé ñåòèèíòåëëåêòóàëüíûõ àãåíòîâ ïðè äîñòèæåíèè êîíñåíñóñà ïðè ñòîõàñòè÷åñêîé ïîñòàíîâêå çàäà÷è â óñëîâèÿõ ïåðåìåííîé òîïîëîãèè ñåòè, íàáëþäåíèé ñ çàäåðæêàìè è ïîìåõàìè, îïåðèðóþùåé ïî ïðîòîêîëó ëîêàëüíîãîãîëîñîâàíèÿ; è òðàåêòîðèè ñîîòâåòñòâóþùåé äåòåðìèíèðîâàííîé íåïðåðûâíîé ìîäåëè.  [17] ìåòîä óñðåäíåííûõ ìîäåëåé èñïîëüçóåòñÿ äëÿ àíàëèçà äèíàìèêè äåöåíòðàëèçîâàííîé ñòîõàñòè÷åñêîé äèíàìè÷åñêîé ñåòèïðè íåïîëíîé èíôîðìàöèè î òåêóùèõ ñîñòîÿíèÿõ óçëîâ, çàäåðæêàõ âèçìåðåíèÿõ è ïåðåìåííîé ñòðóêòóðå ñâÿçåé ïðè äîñòèæåíèè ïðèáëèæåííîãî êîíñåíñóñà; è ðàñïðîñòðàíÿåòñÿ íà ñèñòåìû ñ çàäåðæêàìè â èçìåðåíèÿõ.
 ðàáîòå [56] ñ ïîìîùüþ ñõåìû Äåðåâèöêîãî-Ôðàäêîâà-Ëüþíãàèññëåäóåòñÿ ñòîõàñòè÷åñêàÿ ìóëüòèàãåíòíàÿ ñèñòåìà àãåíòîâ ñ íåëèíåéíîé äèíàìèêîé, îïåðèðóþùàÿ ïî ïðîòîêîëó ëîêàëüíîãî ãîëîñîâàíèÿ ñíåóáûâàþùèì äî íóëÿ øàãîì.  ñòàòüå òàêæå ðàññìàòðèâàåòñÿ ïðèëî17æåíèå ïîëó÷åííûõ ðåçóëüòàòîâ ê çàäà÷å áàëàíñèðîâêè äåöåíòðàëèçîâàííîé ñòîõàñòè÷åñêîé ñåòè ñ íåïîëíîé èíôîðìàöèåé î òåêóùèõ ñîñòîÿíèÿõàãåíòîâ è èçìåíÿþùåéñÿ òîïîëîãèåé.  ñòàòüå [49] ïðîòîêîë ëîêàëüíîãîãîëîñîâàíèÿ (òèïà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè) äëÿ äîñòèæåíèÿ êîíñåíñóñà â ìóëüòèàãåíòíîé ñòîõàñòè÷åñêîé ñåòè ñ èçìåíÿþùåéñÿ òîïîëîãèåé è çàøóìëåííîé èíôîðìàöèåé î ñîñòîÿíèÿõ àãåíòîâ ïðèìåíÿåòñÿ äëÿçàäà÷è áàëàíñèðîâêè çàãðóçêè ðàñïðåäåëåííîé âû÷èñëèòåëüíîé ñèñòåìûè äëÿ óïðàâëåíèÿ ãðóïïîé àâòîíîìíûõ ÁÏËÀ.
 ðàáîòå [12] ïðåäëàãàåòñÿ èñïîëüçîâàíèå ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ áàëàíñèðîâêè çàãðóçêè â ìíîãîÿäåðíûõ ïðîöåññîðàõ.  êàíäèäàòñêîé äèññåðòàöèèÀìåëèíîé [7] ïîñòðîåíû îöåíêè ñðåäíåêâàäðàòè÷åñêîé áëèçîñòè òðàåêòîðèé äèñêðåòíîé ñòîõàñòè÷åñêîé ñèñòåìû, îïèñûâàþùåé ïîâåäåíèå ñîñòîÿíèé àãåíòîâ ñ íåëèíåéíîé äèíàìèêîé ïðè êîíñåíñóñíîì óïðàâëåíèè,ïåðåìåííîé ñòðóêòóðå ñâÿçåé è ïîìåõàõ â íàáëþäåíèÿõ, ê òðàåêòîðèÿìåå íåïðåðûâíîé äåòåðìèíèðîâàííîé ìîäåëè ïðè îòñóòñòâèè çàäåðæåê âèçìåðåíèÿõ; ñôîðìóëèðîâàíû óñëîâèÿ äîñòèæåíèÿ ñðåäíåêâàäðàòè÷íîãî ïðèáëèæåííîãî êîíñåíñóñà â ìóëüòèàãåíòíîé ñèñòåìå ñ ïîìåõàìè èïåðåìåííîé ñòðóêòóðîé ñâÿçåé â ñåòè ïðè îòñóòñòâèè è ïðè íàëè÷èè çàäåðæåê â èçìåðåíèÿõ; ïîëó÷åíû îöåíêè ñðåäíåêâàäðàòè÷åñêîé áëèçîñòèòðàåêòîðèé äèñêðåòíîé ñòîõàñòè÷åñêîé ñèñòåìû, îïèñûâàþùåé ïîâåäåíèå ñîñòîÿíèé àãåíòîâ ñ íåëèíåéíîé äèíàìèêîé ïðè êîíñåíñóñíîì óïðàâëåíèè, ïåðåìåííîé ñòðóêòóðå ñâÿçåé, ïîìåõàõ è çàäåðæêàõ â íàáëþäåíèÿõ, ê òðàåêòîðèÿì åå äèñêðåòíîé óñðåäíåííîé ìîäåëè; îïèñàíû óñëîâèÿäîñòèæåíèÿ îïòèìàëüíîãî óðîâíÿ çàãðóçêè óçëîâ (áàëàíñèðîâêè çàãðóçêè) äåöåíòðàëèçîâàííîé ñåòè ñ ïåðåìåííîé ñòðóêòóðîé ñâÿçåé, ñëó÷àéíûìè ïîìåõàìè è çàäåðæêàìè â èçìåðåíèÿõ, ïîëó÷åííûå ïðè ïåðåôîðìóëèðîâàíèè çàäà÷è î áàëàíñèðîâêå çàãðóçêè â òåðìèíàõ äîñòèæåíèÿêîíñåíñóñà.
 ñòàòüå [11] çàäà÷à ïëàíèðîâàíèÿ ïåðåäà÷è èíôîðìàöèè âñòîõàñòè÷åñêîé áåñïðîâîäíîé ñåòè ñ ðåòðàíñëÿòîðàìè, ñîñòîÿùåé èç óçëîâ ñ íåëèíåéíîé äèíàìèêîé, â óñëîâèÿõ ïåðåìåííîé òîïîëîãèè, ïîìåõ èçàäåðæåê â èçìåðåíèÿõ ñìîäåëèðîâàíà êàê çàäà÷à áàëàíñèðîâêè çàãðóçêè, äëÿ ðåøåíèÿ êîòîðîé ïðåäëîæåí êîíñåíñóñíûé ïðîòîêîë.  ðàáî18òå [8] èññëåäóþòñÿ ñâîéñòâà àëãîðèòìà òèïà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè ïðè ìàëîì ïîñòîÿííîì èëè íåóìåíüøàþùèìñÿ äî íóëÿ ðàçìåðå øàãàïðè íåëèíåéíîé ïîñòàíîâêå çàäà÷è â óñëîâèÿõ ñëó÷àéíî èçìåíÿþùåéñÿñòðóêòóðû ñâÿçåé â ñåòè è íàáëþäåíèÿõ ñî ñëó÷àéíûìè çàäåðæêàìè èïîìåõàìè.
 ðàáîòå [9] èññëåäóåòñÿ ïðèìåíèìîñòü ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ äåöåíòðàëèçîâàííîé áàëàíñèðîâêè çàãðóçêè ñåòè ñïåðåìåííîé òîïîëîãèåé è ïîìåõàìè â èçìåðåíèÿõ ïðè íåñòàöèîíàðíîéïîñòàíîâêå çàäà÷è.  ñòàòüå [62] èññëåäóåòñÿ ïðèìåíèìîñòü ïðîòîêîëàëîêàëüíîãî ãîëîñîâàíèÿ ñ íåóáûâàþùèì ðàçìåðîì øàãà äëÿ ðåøåíèÿ çàäà÷è áàëàíñèðîâêè çàãðóçêè äåöåíòðàëèçîâàííîé ñòîõàñòè÷åñêîé ñåòè âíåñòàöèîíàðíîé ïîñòàíîâêå. Óñòàíîâëåíû óñëîâèÿ äîñòèæèìîñòè ñóáîïòèìàëüíîãî óðîâíÿ çàãðóçêè àãåíòîâ, ïîëó÷åíû îöåíêè ñîîòâåòñòâóþùåãî óðîâíÿ ñóáîïòèìàëüíîñòè â çàâèñèìîñòè îò ðàçìåðà øàãà àëãîðèòìàóïðàâëåíèÿ, ñòðóêòóðû óñðåäíåííîé ñåòè è ñòàòèñòè÷åñêèõ ñâîéñòâ ïîìåõ è çàäåðæåê â èçìåðåíèÿõ.  ðàáîòå [50] ðàññìàòðèâàåòñÿ çàäà÷à îïòèìèçàöèè ïîëåòà ëåãêèõ ÁÏËÀ çà ñ÷åò îáíàðóæåíèÿ öåíòðîâ âîñõîäÿùèõòåïëîâûõ ïîòîêîâ ñ ïîìîùüþ àëãîðèòìà SPSA.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
