Диссертация (1150610), страница 2
Текст из файла (страница 2)
Îäèí èç îáùèõ âîïðîñîâ, èçó÷åíèþ êîòîðîãîíàïðàâëåíà ýòà ðàáîòà, âîçìîæíà ëè ýôôåêòèâíàÿ ðåàëèçàöèÿ êëàññè-÷åñêèõ ìåòîäîâ îïòèìàëüíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñèñòåìàõ?  ðàáîòå ïîëó÷åí ïîëîæèòåëüíûé îòâåò äëÿ íåñêîëüêèõêîíêðåòíûõ çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ, îñíîâàííûõ íà ðåøåíèè ïîòîêîâûõ çàäà÷ îïòèìèçàöèè. Àëãîðèòìû òàêîãî ðîäà îáû÷íî íàçûâàþòñÿ ðàñïðåäåëåííûìè èëè ìóëüòèàãåíòíûìè è øèðîêî èñïîëüçóþòñÿ íàïðàêòèêå: â ðàáîòàõ Áîéäà è äð.
[51], Øàõà [97], Êåìïå è äð. [78] èçó÷àþòñÿ ïðèìåíåíèå ðàñïðåäåëåííûõ àëãîðèòìîâ, íàçûâàåìûõ ñïëåòíÿìè,â ðàáîòàõ Ìàããñà è äð. [85], Õå è äð. [73] èçó÷àþòñÿ àëãîðèòìû ñèíõðîíèçàöèè âðåìåíè â ðàñïðåäåëåííûõ ñåòÿõ, â ðàáîòàõ Ìàíôðåäè [88], Æó èäð. [105] èçó÷àþòñÿ àëãîðèòìû ñîãëàñîâàíèÿ ïîêàçàíèé ñåíñîðíûõ ñåòåé,6â ðàáîòàõ Îëôàòè-ñàáåðà è Ìþððåÿ [91], Ôàêñà è Ìþððåÿ [59], Ðåíà èäð. [94], Ðèêîñà è äð. [95], Àìåëèíîé [5], Àìåëèíîé è Ôðàäêîâà [6], Ïàðñåãîâà, Ïîëÿêîâà è Ùåðáàêîâà [93] èçó÷àþòñÿ ïðîòîêîëû êîíñåíñóñà èèõ ïðèëîæåíèÿ, â ðàáîòàõ Êàëÿåâà, Ãàéäóêà è Êàïóñòÿíà [17, 18], Ôàêñàè Ìþððåÿ [59] ðàññìàòðèâàþòñÿ çàäà÷è êîëëåêòèâíîãî âçàèìîäåéñòâèÿãðóïï ìîáèëüíûõ ðîáîòîâ.Êàê óæå áûëî îòìå÷åíî, îáùåå ïðåèìóùåñòâî ìóëüòèàãåíòíîãî ïîäõîäà çàêëþ÷àåòñÿ â ïðîñòîòå îðãàíèçàöèè è ìàñøòàáèðóåìîñòè ñèñòåìû.Äåòàëüíî îñîáåííîñòè òàêèõ ñèñòåì áûëè èçó÷åíû â ðàáîòàõ Âèòòèõà èÑêîáåëåâà [9], Ñêîáåëåâà, Ñîëëîãóáà, Èâàùåíêî è äð.
[32], Ðæåâñêîãî [31],Ãîðîäåöêîãî [10], Ãîðîäåöêîãî, Ãðóøèíñêîãî è Õàáàëîâà [11].Öåëüþ äèññåðòàöèîííîé ðàáîòûÿâëÿåòñÿ ðàçðàáîòêà è îáîñíî-âàíèå àëãîðèòìîâ ýôôåêòèâíîãî óïðàâëåíèÿ ðåñóðñàìè â ìóëüòèàãåíòíûõ ñåòÿõ â óñëîâèÿõ íåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåìïàðàìåòðîâ ñåòè è îêðóæàþùåé ñðåäû. Äëÿ äîñòèæåíèÿ öåëè áûëè ïîñòàâëåíû ñëåäóþùèå çàäà÷è:1. Èññëåäîâàòü âîçìîæíîñòü ïðèìåíåíèÿ ìåòîäîâ îïòèìèçàöèè äèíàìè÷åñêèõ ïðîöåññîâ ïîòîêîâîãî òèïà äëÿ ýôôåêòèâíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ.2.
Ðàçðàáîòàòü è îáîñíîâàòü íîâûå àëãîðèòìû ýôôåêòèâíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ.3. Èññëåäîâàòü ðàáîòîñïîñîáíîñòü ðàçðàáîòàííûõ íîâûõ àëãîðèòìîâýôôåêòèâíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ âóñëîâèÿõ íåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåì ïàðàìåòðîâ ñåòè è îêðóæàþùåé ñðåäû, ðàçðàáîòàòü è îáîñíîâàòü ñîîòâåòñòâóþùèå àäàïòèâíûå ìîäèôèêàöèè, èññëåäîâàòü âîçìîæíîñòèðàíäîìèçàöèè äëÿ óñêîðåíèÿ ïðîöåññà ðåøåíèÿ çàäà÷.4. Ðåàëèçîâàòü èññëåäîâàííûå ìåòîäû è ïðîâåñòè èõ àïðîáàöèþ äëÿðåøåíèÿ çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ â7óñëîâèÿõ íåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåì ïàðàìåòðîâ ñåòè è îêðóæàþùåé ñðåäû.Ìåòîäû èññëåäîâàíèÿ. äèññåðòàöèîííîé ðàáîòå ïðèìåíÿþòñÿìåòîäû ìàòåìàòè÷åñêîé îïòèìèçàöèè, òåîðèè âåðîÿòíîñòåé è ìàòåìàòè÷åñêîé ñòàòèñòèêè, òåîðèè ãðàôîâ, òåîðèè äèíàìè÷åñêèõ ñèñòåì, èìèòàöèîííîãî ìîäåëèðîâàíèÿ, ìóëüòèàãåíòíûõ òåõíîëîãèé.Îñíîâíûå ïîëîæåíèÿ, âûíîñèìûå íà çàùèòó.1.
Ïðåäëîæåíà ôîðìóëèðîâêà êëàññà çàäà÷ ìóëüòèàãåíòíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â âèäå çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïðîöåññà ïîòîêîâîãî òèïà.2. Ðàçðàáîòàíû äâà ìåòîäà íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãîïîòîêîâîãî ïðîöåññà: íåàäàïòèâíûé íà îñíîâå ðåøåíèÿ ñòàòè÷åñêîéïîòîêîâîé çàäà÷è îïòèìèçàöèè è àäàïòèâíûé íà îñíîâå ïðèìåíåíèÿ ðàíäîìèçèðîâàííîé ñòîõàñòè÷åñêîé àïïðîêñèìàöèè. Ïðåäëîæåíû ñïîñîáû ìóëüòèàãåíòíîé ðåàëèçàöèè ýòèõ ìåòîäîâ.3.
Äîêàçàíà àñèìïòîòè÷åñêàÿ îïòèìàëüíîñòü ïåðâîãî ðàçðàáîòàííîãîìåòîäà â ñëó÷àå óñðåäíÿåìûõ ïðîïóñêíûõ ñïîñîáíîñòåé (òåîðåìû2.1 è 2.2) è ïîëó÷åíû îöåíêè ñêîðîñòè ñõîäèìîñòè äëÿ âòîðîãî ìåòîäà (òåîðåìà 2.6).4. Ðàçðàáîòàíà ïðîãðàììíàÿ ðåàëèçàöèÿ ïðåäëîæåííûõ ìåòîäîâ.Îáîñíîâàííîñòü ïîëó÷åííûõ ðåçóëüòàòîâîáåñïå÷èâàåòñÿ ìàòå-ìàòè÷åñêèìè òåîðåìàìè è ýêñïåðèìåíòàëüíûì ñðàâíåíèåì ìåòîäîâ, îïèñàííûõ â ýòîé ðàáîòå, ñ ìåòîäàìè, ïðèìåíÿåìûìè â ñõîæèõ çàäà÷àõ.Íàó÷íàÿ íîâèçíà.Âñå îñíîâíûå íàó÷íûå ðåçóëüòàòû äèññåðòàöèèÿâëÿþòñÿ íîâûìè.Òåîðåòè÷åñêàÿ öåííîñòü è ïðàêòè÷åñêàÿ çíà÷èìîñòü.Òåîðå-òè÷åñêàÿ öåííîñòü ðàáîòû ñîñòîèò â îïèñàíèè è ðåøåíèè îáùåé çàäà÷èñòîõàñòè÷åñêîãî ïîòîêîâîãî ïðîöåññà è ïîñòàíîâêó çàäà÷ áàëàíñèðîâàíèÿ íàãðóçêè â ñåòè è ñáîðà èíôîðìàöèè â ãðóïïå ìîáèëüíûõ ðîáîòîâ8â âèäå çàäà÷ íàõîæäåíèÿ îïòèìàëüíîãî ïîòîêîâîãî ïðîöåññà.
Ïðåäëîæåíû äâà ìåòîäà ïîñòðîåíèÿ îïòèìàëüíîãî ïðîöåññà: ìåòîä íà îñíîâåóñðåäíåííîé ìîäåëè è àäàïòèâíûé ðàíäîìèçèðîâàííûé ìåòîä.Àïïðîáàöèÿ ðàáîòû.Ìàòåðèàëû äèññåðòàöèè äîêëàäûâàëèñü íàñåìèíàðàõ êàôåäðû ñèñòåìíîãî ïðîãðàììèðîâàíèÿ, êàôåäðû òåîðåòè÷åñêîé êèáåðíåòèêè ÑÏáÃÓ, íà ðîññèéñêèõ è ìåæäóíàðîäíûõ êîíôåðåíöèÿõ ïî ïðîãðàììèðîâàíèþ, èíôîðìàòèêå, îïòèìèçàöèè è òåîðèèóïðàâëåíèÿ: âñåðîññèéñêîå ñîâåùàíèå ïî ïðîáëåìàì óïðàâëåíèÿ ÂÑÏÓ2014, VI, VII, VIII òðàäèöèîííûõ âñåðîññèéñêèõ ìîëîäåæíûõ ëåòíèõøêîëàõ Óïðàâëåíèå, èíôîðìàöèÿ è îïòèìèçàöèÿ (2014, 2015, 2016), 1stConference on Modelling, Identication and Control of Nonlinear Systems(MICNON, 2015), 12th IFAC International Workshop on Adaptation andLearning in Control and Signal Processing (ALCOSP, 2016).
Ïî ðåçóëüòàòàìðàáîòû áûëà çàðåãèñòðèðîâàíà ïðîãðàììà äëÿ ðàçðàáîòêè è òåñòèðîâàíèÿ àëãîðèòìîâ ðàñïðåäåëåíèÿ çàãðóçêè âû÷èñëèòåëüíîé ñåòè 2016661548[38].Ïóáëèêàöèè.Îñíîâíûå ðåçóëüòàòû ðàáîòû îïóáëèêîâàíû â [2, 16,2225, 41, 86, 87] èç íèõ äâå ïóáëèêàöèè â æóðíàëàõ, âõîäÿùèõ â ïåðå÷åíü ðåöåíçèðóåìûõ íàó÷íûõ æóðíàëîâ, â êîòîðûõ äîæíû áûòü îïóáëèêîâàíû îñíîâíûå íàó÷íûå ðåçóëüòàòû äèññåðòàöèé íà ñîèñêàíèå ó÷åíîéñòåïåíè êàíäèäàòà íàóê, [23, 25], òðè ïóáëèêàöèè â ïåðèîäè÷åñêèõ èçäàíèÿõ, âõîäÿùèõ â áàçó SCOPUS [41, 86, 87]. Ðàáîòû [2, 16, 41] íàïèñàíû âñîàâòîðñòâå.
 [2, 16] àâòîðó ïðèíàäëåæèò îáùåå ìàòåìàòè÷åñêîå îïèñàíèå çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ.  [41] àâòîðó ïðèíàäëåæèò îïèñàíèåñâÿçè ñïëåòåí, çàäà÷è êîíñåíñóñà è Simultaneous Perturbation StochasticApproximation (SPSA) ìåòîäà.Ñòðóêòóðà è îáúåì äèññåðòàöèè.Äèññåðòàöèÿ ñîñòîèò èç ââåäå-íèÿ, òðåõ ãëàâ, çàêëþ÷åíèÿ, ñïèñêà ëèòåðàòóðû, âêëþ÷àþùåãî 105 èñòî÷íèêîâ. Òåêñò çàíèìàåò 103 ñòðàíèöû, ñîäåðæèò 12 ðèñóíêîâ è îäíóòàáëèöó.Ñîäåðæàíèå ðàáîòû9Âîââåäåíèèîáîñíîâûâàåòñÿ àêòóàëüíîñòü èññëåäîâàíèé, ïðîâîäè-ìûõ â ðàìêàõ ýòîé äèññåðòàöèîííîé ðàáîòû, ïðèâîäèòñÿ îáçîð íàó÷íîéëèòåðàòóðû ïî èçó÷àåìîé ïðîáëåìå, ôîðìóëèðóåòñÿ öåëü, ñòàâÿòñÿ çàäà÷è ðàáîòû, ñôîðìóëèðîâàíû íàó÷íàÿ íîâèçíà è ïðàêòè÷åñêàÿ çíà÷èìîñòü ïðåäñòàâëÿåìîé ðàáîòû.Âïåðâîé ãëàâåïðèâîäÿòñÿ îáùèå ñâåäåíèÿ î ïîòîêîâûõ çàäà÷àõëèíåéíîãî ïðîãðàììèðîâàíèÿ: ìàêñèìàëüíîãî ïîòîêà, ïàðàìåòðè÷åñêîãîïîòîêà; ñôîðìóëèðîâàíà îáùàÿ çàäà÷à îïòèìàëüíîãî ïîòîêîâîãî äèíàìè÷åñêîãî ïðîöåññà è åãî ñòîõàñòè÷åñêàÿ âàðèàöèÿ, îïèñàíû äâå çàäà÷èìóëüòèàãåíòíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ. ïóíêòå 1.1 ïðåäñòàâëåíà îáùàÿ ñïåöèôèêà ïîòîêîâûõ ïðîöåññîâ,îïèñàíî, êàê ýòà ñïåöèôèêà èíòåðïðåòèðóåòñÿ â ðàçëè÷íûõ ïðàêòè÷åñêèõ ñèòóàöèÿõ, ïåðå÷èñëåíû îñíîâíûå ìàòåìàòè÷åñêèå ìîäåëè è çàäà÷è, ñõîæèå ñ òåìè, êîòîðûå ðàññìàòðèâàþòñÿ â äèññåðòàöèîííîé ðàáîòå. ïóíêòå 1.1.1 îïèñàíà îáùàÿ çàäà÷à íàõîæäåíèÿ îïòèìàëüíîãî ïðîöåññà(çàäà÷à áûñòðîäåéñòâèÿ) è îïèñàíî ñâåäåíèå ýòîé çàäà÷è ê ìàòåìàòè÷åñêîé îïòèìèçàöèè.
 ïóíêòå 1.1.2 îïèñàíà ñïåöèôèêà çàäà÷ íàõîæäåíèÿîïòèìàëüíûõ ïîòîêîâûõ ïðîöåññîâ.  ïóíêòå 1.2 ïîäðîáíî îïèñàíû çàäà÷è î ìàêñèìàëüíîì ïîòîêå, çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå è ýôôåêòèâíûå àëãîðèòìû ðåøåíèÿ ýòèõ çàäà÷.  ïóíêòå 1.3 îïèñàíû äâåïðàêòè÷åñêèå çàäà÷è ìóëüòèàãåíòíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ.Âîâòîðîé ãëàâåîïèñàíû äâà ìåòîäà ïîñòðîåíèÿ ïîòîêîâûõ ïðî-öåññîâ.  ïóíêòå 2.1.1 îïèñàí êëàññ óñðåäíÿåìûõ ôóíêöèé è ïðèâåäåíûîñíîâíûå ñâîéñòâà òàêèå ôóíêöèé.
 ïóíêòå 2.1.2 ïîêàçàíî, ÷òî äëÿ ïîòîêîâûõ ïðîöåññîâ ñ óñðåäíÿåìûìè ïðîïóñêíûìè ñïîñîáíîñòÿìè äîïóñòèìî ïîñòðîåíèå ñóáîïòèìàëüíîãî ïðîöåññà ÷åðåç óñðåäíåííóþ ìîäåëü,äîêàçàíà àñèìïòîòè÷åñêàÿ îïòèìàëüíîñòü òàêîãî ïîäõîäà.  ïóíêòå 2.1.3ïðèâåäåí ïðèìåð ïîñòðîåíèÿ îöåíîê çàäåðæêè äëÿ ñëó÷àÿ ñëó÷àéíûõïðîöåññîâ.  ïóíêòå 2.2.1 îïèñàíà îáùàÿ ñõåìà ìåòîäà áàëàíñèðîâàíèÿäóã äëÿ âñïîìîãàòåëüíîé çàäà÷è, â ïóíêòàõ 2.2.2-2.2.4 ïðîàíàëèçèðîâàíà ñêîðîñòü ñõîäèìîñòè ìåòîäîâ, â ïóíêòå 2.2.5 îïèñàí ñïîñîá ïîëó÷åíèÿðåøåíèÿ çàäà÷è î ìàêñèìàëüíîì ïîòîêå èç ðåøåíèÿ âñïîìîãàòåëüíîé çà10äà÷è, â ïóíêòå 2.2.6 îïèñàíû ðåàëèçàöèè ìåòîäîâ â ìóëüòèàãåíòíûõ èëèðàñïðåäåëåííûõ ñèñòåìàõ.Âòðåòüåé ãëàâåîïèñàíû ðåçóëüòàòû ýêñïåðèìåíòîâ, ïðîâåäåííûõäëÿ ðàçðàáîòàííûõ àëãîðèòìîâ. ïóíêòå 3.1 ïðèâåäåíî îïèñàíèå ïàêåòà ïðèêëàäíûõ ïðîãðàìì, ðàçðàáîòàííîãî äëÿ ñèìóëÿöèè ïðîöåññà ðàñïðåäåëåíèÿ çàãðóçêè â ñåòè, âïóíêòå 3.2 îïèñàíà ðåàëèçàöèÿ ýôôåêòèâíîãî àëãîðèòìà äëÿ ðåøåíèÿçàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå è ïðèâåäåíû ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî ñðàâíåíèÿ ñ áèáëèîòåêîé À.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
