Диссертация (1150593)
Текст из файла
ÑÀÍÊÒ-ÏÅÒÅÐÁÓÐÃÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉÓÍÈÂÅÐÑÈÒÅÒÍà ïðàâàõ ðóêîïèñèÈâàíñêèé Þðèé Âëàäèìèðîâè÷ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÛÅ ÀËÃÎÐÈÒÌÛ ÇÀÄÀ×ÀÕ ÌÓËÜÒÈÀÃÅÍÒÍÎÃÎÂÇÀÈÌÎÄÅÉÑÒÂÈß01.01.09 Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêàÿ êèáåðíåòèêàÄèññåðòàöèÿíà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÍàó÷íûé ðóêîâîäèòåëü:äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê, ïðîôåññîðÎëåã Íèêîëàåâè÷ Ãðàíè÷èíÑàíêò-Ïåòåðáóðã2016ÎãëàâëåíèåÂâåäåíèå .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 Áàëàíñèðîâêà çàãðóçêè óçëîâ âû÷èñëèòåëüíîé ñåòè ñ ïîìîùüþ ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ151.11.21.31.4Ïðåäâàðèòåëüíûå ñâåäåíèÿ . . . . . . . . . . . . . . . . . .Çàäà÷à áàëàíñèðîâêè çàãðóçêè . . . . . . . . . . . . . . . .Ïðîòîêîë ïåðåðàñïðåäåëåíèÿ çàäàíèé . . . . .
. . . . . . .Èñïîëüçîâàíèå ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ íà ïðàêòèêå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212224282 Îïòèìèçàöèÿ ïðîöåññà áàëàíñèðîâêè çàãðóçêè óçëîâ âû÷èñëèòåëüíîé ñåòè ñ çàäà÷àìè ðàçíûõ ïðèîðèòåòîâ332.12.22.32.4Áàëàíñèðîâêè çàãðóçêè ñåòè, âûïîëíÿþùåé çàäàíèÿ ñ ðàçíûìè ïðèîðèòåòàìè . . .
. . . . . . . . . . . . . . . . . . .Äèôôåðåíöèðîâàííûé êîíñåíñóñ . . . . . . . . . . . . . . .Îöåíêà îïòèìàëüíîãî ðàçìåðà øàãà àëãîðèòìà . . . . . . .Ñòîèìîñòíûå îãðàíè÷åíèÿ íà èñïîëüçîâàíèå ñâÿçåé . . . .2.4.1 Ðàíäîìèçàöèÿ èñïîëüçîâàíèÿ ñâÿçåé . . . . . . . . .2.4.2 Óñëîâèÿ äîñòèæèìîñòè äèôôåðåíöèðîâàííîãî êîíñåíñóñà . . . . . . . . . . . . . . . . .
. . . . . . . . .2.4.3 Îïòèìèçàöèÿ ðàçìåðà øàãà àëãîðèòìà . . . . . . . .333648505051603 Èìèòàöèîííîå ìîäåëèðîâàíèå è àäàïòàöèÿ ðàçìåðà øàãààëãîðèòìà623.13.2Ìîäåëèðîâàíèå ïîâåäåíèÿ ñåòåâîé ñèñòåìû, âûïîëíÿþùåéçàäàíèÿ íåñêîëüêèõ êëàññîâ, ïåðåðàñïðåäåëåííûõ ïî ïðîòîêîëó ëîêàëüíîãî ãîëîñîâàíèÿ (2.4) â óñëîâèÿõ ïîìåõ, çàäåðæåê, èçìåíÿþùåéñÿ ñòðóêòóðû ñâÿçåé ñåòè . . . . .
. .Ìîäåëèðîâàíèå ïîâåäåíèÿ ñåòåâîé ñèñòåìû, âûïîëíÿþùåéçàäàíèÿ íåñêîëüêèõ êëàññîâ ïðèîðèòåòîâ, ïðè íàëè÷èè ðàçíûõ ñòîèìîñòíûõ îãðàíè÷åíèé íà èñïîëüçîâàíèå ñâÿçåé äëÿîáìåíà çàäàíèÿìè êàæäîãî êëàññà . . . . . . . . . . . . . .262653.33.4Èññëåäîâàíèå çàâèñèìîñòè ýôôåêòèâíîñòè äîñòèæåíèÿ êîíñåíñóñà â ñåòåâîé ñèñòåìå îò âûáîðà ðàçìåðà øàãà àëãîðèòìà 68Ïîèñêîâûé àëãîðèòì ñòîõàñòè÷åñêîé àïïðîêñèìàöèè ñ ðàíäîìèçàöèåé íà âõîäå äëÿ àäàïòàöèè ðàçìåðà øàãà ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ .
. . . . . . . . . . . . . . . . 71Çàêëþ÷åíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Ëèòåðàòóðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37880Ââåäåíèå ïîñëåäíåå âðåìÿ âñå áîëüøåå âíèìàíèå óäåëÿåòñÿ çàäà÷àì ðàñïðåäåëåííîãî âçàèìîäåéñòâèÿ â ñåòÿõ è óïðàâëåíèÿ â ñåòåâûõ äèíàìè÷åñêèõñèñòåìàõ. Èíòåðåñ ê òåìàòèêå óïðàâëåíèÿ â äèíàìè÷åñêèõ ñåòÿõ âûçâàíïðèëîæåíèÿìè â ðàçëè÷íûõ îáëàñòÿõ, âêëþ÷àÿ, íàïðèìåð, ìíîãîïðîöåññîðíûå ñåòè, ëîãèñòè÷åñêèå ñåòè, ïðîèçâîäñòâåííûå ñåòè, ñåíñîðû è áåñïðîâîäíûå ñåòè, ñêîîðäèíèðîâàííîå äâèæåíèå ÁÏËÀ, ïîäâîäíûõ îáúåêòîâ è ìîáèëüíûõ ðîáîòîâ, ðàñïðåäåëåííûå ñèñòåìû óïðàâëåíèÿ ýëåêòðè÷åñêèìè ñåòÿìè, ñëîæíûå êðèñòàëëè÷åñêèå ðåøåòêè è íàíîñòðóêòóðíûåîáúåêòû.
 ðàáîòàõ ×. Àáäàëëû (C. Abdallah) [48], Ð. Ï. Àãàåâà [45],Á. Ð. Àíäðèåâñêîãî [50, 75], Ï. Àíòñàêëèñà (P. Antsaklis) [64], Ä. Áàèëëåóëà (J. Baillieul) [64], Ð. Â. Áåðäà (R. W. Beard) [100102], Ô. Áóëëî(F. Bullo) [71], Ò. Âèêñåêà (T. Vicsek) [68, 111], Â. À. Âèòòèõà [21], ×. Âó(C. Wu) [113], Â.
È. Ãîðîäåöêîãî [22, 23], È. À. Êàëÿåâà [34], Ä. Êîðòåñà (J. Cortes) [71], Ô. Ëüþèñà (F. Lewis) [91], À. Ñ. Ìàòâååâà [94],À. Ñ. Ìîðñà (A.S. Morse) [86], Ð. Ì. Ìþððåÿ (R. M. Murray) [95, 96],Ð. Îëôàòè-Ñàáåðà (R. Olfati-Saber) [95, 96], Â. Ðåíà (W. Ren) [100102],Ã. À. Ðæåâñêîãî [63, 104], Ã. Òàííåðà (H. Tanner) [48], À. Ë. Ôðàäêîâà [1517,5457,75], Ì. Õóàíãà (M. Huang) [81,82], Ï. Þ. ×åáîòàðåâà [45]è äðóãèõ çàëîæåíû îñíîâû òåîðåòè÷åñêîãî îïèñàíèÿ ìåòîäîâ àíàëèçàè ñèíòåçà äåöåíòðàëèçîâàííîãî àäàïòèâíîãî ìóëüòèàãåíòíîãî óïðàâëåíèÿ, îáñóæäàþòñÿ ìíîãî÷èñëåííûå ïîòåíöèàëüíûå ïðàêòè÷åñêèå ïðèëîæåíèÿ â óïðàâëåíèè ñëîæíûìè ïðîèçâîäñòâåííûìè, ýíåðãåòè÷åñêèìèñèñòåìàìè.Í. Î. Àìåëèíà [1,317,4962,77,85], Ä.
Àðìáðóñòåð (D. Armbruster) [65],À. Ãëàøåíêî [105], È. Ãðà÷åâ [63,105], Ñ. Èíîçåìöåâ [63,83,105], È. À. Êàëÿåâ [34], À. Ñ. Ìèõàéëîâ [65], Ñ. Ý. Ïàðñåãîâ [3638], À. Â. Ïðîñêóðíèêîâ [94, 98], Ï. Î. Ñêîáåëåâ [21, 42, 43, 63, 79, 104, 105], Ï. Ñ. Ùåðáàêîâ [38, 46, 47] è äð. àêòèâíî èçó÷àëè àëãîðèòìû óïðàâëåíèÿ â ñåòÿõ, óçëû êîòîðûõ âûïîëíÿþò îïðåäåëåííûå äåéñòâèÿ ïàðàëëåëüíî.
Ïîäîáíûåñåòåâûå ñèñòåìû ïðèìåíÿþòñÿ â âû÷èñëèòåëüíûõ, ïðîèçâîäñòâåííûõ ñå4òÿõ, ñåòÿõ îáñëóæèâàíèÿ, òðàíñïîðòíûõ è ëîãèñòè÷åñêèõ ñåòÿõ. Íåñìîòðÿ íà îáúåì ðàáîò ïî òåìàòèêå óïðàâëåíèÿ äåöåíòðàëèçîâàííûìè ñèñòåìàìè, óäîâëåòâîðèòåëüíûå ðåøåíèÿ ïðåäëîæåíû äëÿ îãðàíè÷åííîãîêëàññà çàäà÷. Òàêèå ôàêòîðû, êàê ïåðåêëþ÷åíèÿ òîïîëîãèè ñâÿçåé, ïîìåõè è çàäåðæêè ïðè èçìåðåíèè ñîñòîÿíèé àãåíòîâ çíà÷èòåëüíî ïîâûøàþòñëîæíîñòü ðåøåíèÿ çàäà÷.
Äîñòàòî÷íî ïðîñòûå àäàïòèâíûå àëãîðèòìû÷àñòî äåìîíñòðèðóþò óäîâëåòâîðèòåëüíóþ ïðîèçâîäèòåëüíîñòü, íî îñòàþòñÿ îòêðûòûìè âîïðîñû èõ òåîðåòè÷åñêîãî îáîñíîâàíèÿ è äîñòèæåíèÿîïòèìàëüíîé ïðîèçâîäèòåëüíîñòè. Êàê ïðàâèëî, ïðè ïîñòàíîâêå çàäà÷è ïðåäïîëàãàåòñÿ, ÷òî âñå çàäàíèÿ, âûïîëíÿåìûå ñèñòåìîé, îäèíàêîâîâàæíû äëÿ èñïîëíåíèÿ.Òåõíîëîãèÿ ìóëüòèàãåíòíûõ ñèñòåì (ÌÀÑ) ýòî íîâàÿ ïàðàäèãìàðàçâèòèÿ ÈÒ, îðèåíòèðîâàííàÿ íà ñîâìåñòíîå èñïîëüçîâàíèå òåõíîëîãè÷åñêèõ è òåõíè÷åñêèõ äîñòèæåíèé è ïðåèìóùåñòâ, êîòîðûå ïðåäîñòàâëÿþò âîçìîæíîñòè è ìåòîäû èñêóññòâåííîãî èíòåëëåêòà (ÈÈ), àïïàðàòíûåè ïðîãðàììíûå ñðåäñòâà ïîääåðæêè ðàñïðåäåëåííîñòè è îòêðûòîñòè.
Âñâÿçè ñ ýòèì, â íàñòîÿùåå âðåìÿ àêòèâíî ðàçâèâàþòñÿ ìåòîäû ôîðìèðîâàíèÿ è ïîñòðîåíèÿ ñëîæíûõ àäàïòèâíûõ ñèñòåì íà áàçå ìóëüòèàãåíòíûõìåòîäîâ è òåõíîëîãèé [22, 23, 34, 104]. Òàêèå ñèñòåìû ÷àñòî ïðèìåíÿþòñÿäëÿ óïðàâëåíèÿ àíñàìáëÿìè (ðîÿìè, swarms; ñòàÿìè, ocks) äèíàìè÷åñêèõ îáúåêòîâ [68,92,108], âûïîëíÿþùèõ îáùóþ çàäà÷ó èëè çàäà÷ó ñ ðàçäåëÿþùèìèñÿ öåëÿìè â óñëîâèÿõ íåîïðåäåëåííîñòè [18].  êà÷åñòâå èñïîëíèòåëüíûõ ýëåìåíòîâ òàêèõ ñèñòåì èñïîëüçóþòñÿ ðîáîòîòåõíè÷åñêèåóñòðîéñòâà ðàçëè÷íîãî íàçíà÷åíèÿ, êîòîðûå ìîãóò äåéñòâîâàòü â ðàçëè÷íûõ ñðåäàõ: íà çåìëå (ñòàöèîíàðíûå, êîëåñíûå è ãóñåíè÷íûå óñòðîéñòâà), ïîä âîäîé (ìèíèàòþðíûå áåñïèëîòíûå ïîäâîäíûå ëîäêè, ÁÏÏË) èâ âîçäóõå (áåñïèëîòíûå ëåòàòåëüíûå àïïàðàòû, ÁÏËÀ). Îäèí èç íîâûõïîäõîäîâ ðîåâîå óïðàâëåíèå èçó÷àåò âîçìîæíîñòè ïîñòðîåíèÿ ñèñòåìû èç ñîâîêóïíîñòè àâòîíîìíûõ èíòåëëåêòóàëüíûõ àãåíòîâ (ðîáîòîâ)äëÿ äîñòèæåíèÿ êîëëåêòèâíûõ öåëåé, êîòîðûå íå ìîãóò áûòü äîñòèãíóòû îòäåëüíûì ðîáîòîì èëè äëÿ êîòîðûõ êîëëåêòèâíîå âûïîëíåíèå ïîñòàâëåííîé çàäà÷è áîëåå ýôôåêòèâíî.
Îñíîâîïîëàãàþùåé èäååé ðîåâîãî5óïðàâëåíèÿ ÿâëÿåòñÿ ¾ðîåâîé èíòåëëåêò¿ (ÐÈ, Swarm Intelligence), øèðîêî íàáëþäàåìûé â ïðèðîäíîì ìèðå: â êîëîíèÿõ ï÷åë, ìóðàâüåâ, ïðèäâèæåíèè êîñÿêîâ ðûá, ïòè÷èõ ñòàé è ò. ï. Òåðìèí ¾ðîåâîé èíòåëëåêò¿áûë ââåäåí â 1989 ãîäó â êîíòåêñòå èññëåäîâàíèÿ ñèñòåìû êëåòî÷íûõ¾ðîáîòîâ¿ [67]. Ðîåâîé èíòåëëåêò ñèñòåìà, ðåàëèçóþùàÿ óïðàâëåíèåêîëëåêòèâíûì ïîâåäåíèåì äåöåíòðàëèçîâàííîé ñàìîîðãàíèçóþùåéñÿ ñîâîêóïíîñòüþ îäíîðîäíûõ îáúåêòîâ. Ðîåâîé èíòåëëåêò ðàññìàòðèâàåòñÿâ òåîðèè èñêóññòâåííîãî èíòåëëåêòà êàê ìåòîä ¾íå äî êîíöà ôîðìàëèçóåìîé îïòèìèçàöèè¿.Çàäà÷à ñîãëàñîâàíèÿ (êîíñåíñóñà) íà ãðàôàõ ïðè ïîìåõàõ â èçìåðåíèÿõ ñîñòîÿíèé ñîñåäåé è íåòî÷íûõ ñâÿçÿõ ðàññìàòðèâàëàñü â [82, 99] ñïðèìåíåíèåì àëãîðèòìîâ òèïà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè ñ óáûâàþùèì äî íóëÿ ðàçìåðîì øàãà. Ñõîäèìîñòü ïðè øóìàõ è íåóáûâàþùåìðàçìåðå øàãà èçó÷àëàñü â [112], íî ïðè ýòîì ïàðàìåòðû ðàçìåðà øàãàâûáèðàëèñü ðàçëè÷íûìè äëÿ ðàçíûõ àãåíòîâ è ðàññìàòðèâàëñÿ ñïåöèôè÷åñêèé ñöåíàðèé ïîñòðîåíèÿ ñåòè.
Ìåòîäû ñòîõàñòè÷åñêîãî ãðàäèåíòà(ñòîõàñòè÷åñêîé àïïðîêñèìàöèè, SA) òàêæå èñïîëüçîâàëèñü ïðè íàëè÷èèñòîõàñòè÷åñêèõ íåîïðåäåëåííîñòåé [93, 96, 100, 109].  ëèíåéíîì ñëó÷àåáåç îáðàòíûõ ñâÿçåé â ñòîõàñòè÷åñêîé ñåòè ïðîáëåìû äîñòèæåíèÿ ïðèáëèçèòåëüíîãî êîíñåíñóñà ðàññìàòðèâàëèñü â [66].Íà ïðàêòèêå âî âðåìÿ ðàáîòû ñèñòåìû îäíè çàäàíèÿ ìîãóò èìåòüáîëåå âûñîêóþ âàæíîñòü, ÷åì äðóãèå. Ýòî ìîæåò áûòü âûçâàíî íåîáõîäèìîñòüþ âûïîëíåíèÿ ñèñòåìíûõ çàïðîñîâ äëÿ ïîääåðæàíèÿ ðàáîòûâñåé ñèñòåìû; íåêîòîðûå çàäàíèÿ ìîãóò èìåòü áîëåå âûñîêóþ ñðî÷íîñòü,â òî âðåìÿ êàê äëÿ äðóãèõ çàäàíèé âðåìÿ èõ âûïîëíåíèÿ â ñèñòåìå íåòàê êðèòè÷íî; ó ñèñòåìû ìîãóò áûòü íåñêîëüêî ãðóïï ïîëüçîâàòåëåé, êîòîðûì òðåáóåòñÿ ðàçíûé óðîâåíü îáñëóæèâàíèÿ.
 òàêèõ ñèòóàöèÿõ äëÿäèôôåðåíöèàöèè çàäàíèé ðàçíûõ êëàññîâ ââîäÿò ïðèîðèòåòû, êîòîðûåó÷èòûâàþòñÿ ïðè ïðèíÿòèè ðåøåíèé îá î÷åðåäíîñòè âûáîðà çàäàíèé íàèñïîëíåíèå. ïîñëåäíåå âðåìÿ íàáèðàåò ïîïóëÿðíîñòü êîíöåïöèÿ èíòåðíåòà âåùåé ñîåäèíåíèÿ ðàçëè÷íûõ îáúåêòîâ â ñåòü äëÿ îðãàíèçàöèè èõ âçàè6ìîäåéñòâèÿ, ïðîâîäÿòñÿ ìíîãî÷èñëåííûå ýêñïåðèìåíòû ïî îðãàíèçàöèèâçàèìîäåéñòâèÿ ãðóïï ìîáèëüíûõ ðîáîòîâ, íàáëþäàåòñÿ âñå âîçðàñòàþùåå ïðèìåíåíèå áåñïèëîòíûõ ëåòàòåëüíûõ àïïàðàòîâ, êàê â âîåííûõ, òàêè â ãðàæäàíñêèõ öåëÿõ.
Ïåðå÷èñëåííûå òåíäåíöèè àêòóàëèçèðóþò ðàçðàáîòêó è ïðèìåíåíèå ìóëüòèàãåíòíîãî ïîäõîäà â óïðàâëåíèè ãðóïïîéîáúåêòîâ, ïîñêîëüêó, ñ îäíîé ñòîðîíû, ïîäîáíûìè ãðóïïàìè çà÷àñòóþíåýôôåêòèâíî óïðàâëÿòü öåíòðàëèçîâàííî, ñ äðóãîé îáúåêòû â òàêèõ ãðóïïàõ ñïîñîáíû ñàìîñòîÿòåëüíî îðãàíèçîâûâàòü è ïîääåðæèâàòüâçàèìîäåéñòâèå âíóòðè ãðóïïû è â ýòîì ñìûñëå îáëàäàþò îïðåäåëåííîéñòåïåíüþ èíòåëëåêòóàëüíîñòè. ïîäîáíûõ ñèñòåìàõ óñòðîéñòâà, êàê ïðàâèëî, îáëàäàþò îãðàíè÷åííûì çàïàñîì ýíåðãèè, â ñâÿçè ñ ÷åì âñòàåò ïðîáëåìà îðãàíèçàöèè âçàèìîäåéñòâèÿ àãåíòîâ â ñèñòåìå, ó÷èòûâàþùåãî ðàñõîäû íà îáìåí äàííûìèïî ñåòè.Îáîçíà÷åííûå ïðîáëåìû è òåíäåíöèè ïîäòâåðæäàþò àêòóàëüíîñòüòåìû äèññåðòàöèîííîãî èññëåäîâàíèÿ.Öåëüþ ðàáîòû ÿâëÿåòñÿ ðàçðàáîòêà è èññëåäîâàíèå àëãîðèòìîâ ïîâûøåíèÿ ýôôåêòèâíîñòè äåöåíòðàëèçîâàííîãî ïåðåðàñïðåäåëåíèÿ î÷åðåäåé çàäà÷ ñ ðàçíûìè óðîâíÿìè ïðèîðèòåòîâ ìåæäó óçëàìè âû÷èñëèòåëüíîé ñåòè â óñëîâèÿõ ïåðåìåííîé ñòðóêòóðû ñâÿçåé, ïîìåõ è çàäåðæåêïðè ïåðåäà÷å èíôîðìàöèè.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
