Автореферат (1150608)
Текст из файла
Íà ïðàâàõ ðóêîïèñèÌàëüêîâñêèé Íèêîëàé Âëàäèìèðîâè÷ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÛÅ ÀËÃÎÐÈÒÌÛ ÐÀÑÏÐÅÄÅËÅÍÈßÐÅÑÓÐÑΠÂÀÄÀÏÒÈÂÍÛÕ ÌÓËÜÒÈÀÃÅÍÒÍÛÕ ÑÈÑÒÅÌÀÕ01.01.09 Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêàÿ êèáåðíåòèêàÀÂÒÎÐÅÔÅÐÀÒäèññåðòàöèè íà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÑàíêò-Ïåòåðáóðã2017Ðàáîòà âûïîëíåíà â Ñàíêò-Ïåòåðáóðãñêîì ãîñóäàðñòâåííîì óíèâåðñèòåòå.Íàó÷íûé ðóêîâîäèòåëü:äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîð Ãðàíè÷èí Îëåã Íèêîëàåâè÷Îôèöèàëüíûå îïïîíåíòû:ÕËÅÁÍÈÊΠÌèõàèë Âëàäèìèðîâè÷,äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîð ÐÀÍ, ÔÃÁÓÍ ¾Èíñòèòóò ïðîáëåìóïðàâëåíèÿ èì. Â.À. Òðàïåçíèêîâà Ðîññèéñêîéàêàäåìèè íàóê¿, çàâåäóþùèéëàáîðàòîðèåé àäàïòèâíûõ è ðîáàñòíûõñèñòåì èì.
ß.Ç. ÖûïêèíàÓÑÈÊ Åãîð Âëàäèìèðîâè÷,êàíäèäàò ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ÇÀÎ Ïðîåêòíî-êîíñòðóêòîðñêîå áþðî ¾ÐÈο,âåäóùèé èíæåíåð-ïðîãðàììèñòÂåäóùàÿ îðãàíèçàöèÿ:Ôåäåðàëüíîå ãîñóäàðñòâåííîå áþäæåòíîåîáðàçîâàòåëüíîå ó÷ðåæäåíèå âûñøåãî îáðàçîâàíèÿ¾Ìîñêîâñêèé ôèçèêî-òåõíè÷åñêèé èíñòèòóò(ãîñóäàðñòâåííûé óíèâåðñèòåò)¿Çàùèòà ñîñòîèòñÿ 2017 ãîäà â÷àñîâ íà çàñåäàíèè äèññåðòà-öèîííîãî ñîâåòà Ä 212.232.29 íà áàçå Ñàíêò-Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïî àäðåñó: 198178, Ñàíêò-Ïåòåðáóðã, 10 ëèíèÿ Â.Î., ä. 33/35, àóä. 74.Ñ äèññåðòàöèåé ìîæíî îçíàêîìèòüñÿ â Íàó÷íîé áèáëèîòåêå èì.
Ì. Ãîðüêîãî ÑàíêòÏåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïî àäðåñó: 199034, Ñàíêò-Ïåòåðáóðã,Óíèâåðñèòåòñêàÿ íàá., ä. 7/9 è íà ñàéòådisser/h7ytZqrhBk.pdfÀâòîðåôåðàò ðàçîñëàí https://disser.spbu.ru/files/disser2/2017 ã.Ó÷åíûé ñåêðåòàðüäèññåðòàöèîííîãî ñîâåòà Ä 212.232.29,äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîðÂ.
Ì. ÍåæèíñêèéÎáùàÿ õàðàêòåðèñòèêà ðàáîòûÀêòóàëüíîñòü òåìû. Ñåòåâûå òåõíîëîãèè íà÷àëè ðàçâèâàòüñÿ áîëåå ïîëóâåêà íàçàä, à â ïîñëåäíèå äåñÿòèëåòèÿ ýòà ñôåðà ïîäâåðãëàñü çíà÷èòåëüíîìó ðàñøèðåíèþ.Ðàçâèòèå Èíòåðíåòà è ëîãèñòèêè, çàìåäëåíèå ñêîðîñòè ðîñòà âû÷èñëèòåëüíûõ ìîùíîñòåé ýòè è äðóãèå ôàêòîðû ïîâëèÿëè íà óâåëè÷åíèå èíòåðåñà ê ðàñïðåäåëåííûìâû÷èñëåíèÿì, ñåòåâûì òåõíîëîãèÿì è ñìåæíûì îáëàñòÿì.  ñâîþ î÷åðåäü ìóëüòèàãåíòíûå òåõíîëîãèè ñòàëè ïîïóëÿðíûìè òîëüêî â ïîñëåäíèå 10-20 ëåò, íî ïðè ýòîìçàíÿëè ñâîþ íèøó â îáëàñòè ðàñïðåäåëåííûõ âû÷èñëåíèé. Îñíîâíûì íàïðàâëåíèåìýòîé ðàáîòû ÿâëÿåòñÿ èçó÷åíèå ñâîéñòâ íåñêîëüêèõ ìîäåëåé çàäà÷ ðàñïðåäåëåíèÿðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ ñ óïîðîì íà ñåòåâûå ïîòîêîâûå çàäà÷è. Îñíîâíîåòåîðåòè÷åñêîå íàïðàâëåíèå èññëåäîâàíèå ñòîõàñòè÷åñêèõ ïîòîêîâûõ ïðîöåññîâ,ïðàêòè÷åñêîå ðàñïðåäåëåíèå çàãðóçêè â âû÷èñëèòåëüíûõ ñåòÿõ è ïåðåäà÷à äàííûõ â ãðóïïàõ ìîáèëüíûõ ðîáîòîâ.Âñå ðàññìàòðèâàåìûå â ðàáîòå ìîäåëè ïîäðàçóìåâàþò îòûñêàíèå íåêîòîðîãîîïòèìàëüíîãî ïî âðåìåíè ïðîöåññà (âûïîëíåíèå ãðóïïû çàäàíèé çà íàèìåíüøååâðåìÿ, ïåðåäà÷à íàáîðà ñîîáùåíèé â ãðóïïå ìîáèëüíûõ ðîáîòîâ çà íàèìåíüøååâðåìÿ).
 òåîðèè óïðàâëåíèÿ, îñíîâíàÿ ìàññà ðàáîò ïî ïîñòðîåíèþ îïòèìàëüíûõäèíàìè÷åñêèõ ïðîöåññîâ îñíîâàíà íà ïðèíöèïå äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿè ïðèíöèïå ìàêñèìóìà Ïîíòðÿãèíà.  ñëó÷àå îòñóòñòâèÿ íåîïðåäåëåííîñòåé è èçìåíåíèé ïàðàìåòðîâ ñèñòåìû âî âðåìåíè, ðàññìàòðèâàåìûå çàäà÷è âûðîæäàþòñÿ âçàäà÷è ìàòåìàòè÷åñêîé îïòèìèçàöèè.  îáùåì âèäå òàêèå çàäà÷è ðàññìàòðèâàëèñüÊàíòîðîâè÷åì (îáùàÿ òåîðèÿ ëèíåéíîãî ïðîãðàììèðîâàíèÿ), Õà÷èÿíîì (ìåòîä ýëëèïñîèäîâ), Ïîëÿêîì (îáùàÿ òåîðèÿ âûïóêëîé îïòèìèçàöèè), Êàðìàðêàðîì (ïîëèíîìèàëüíûé ìåòîä âíóòðåííåé òî÷êè äëÿ çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ),Íåñòåðîâûì è Íåìèðîâñêèì (ïîëèíîìèàëüíûå ìåòîäû äëÿ çàäà÷ íåëèíåéíîé âûïóêëîé îïòèìèçàöèè), Áîéäîì è Âàíäåíáåðãå (ñîâðåìåííàÿ òåîðèÿ îïòèìèçàöèè) èìíîãèìè äðóãèìè.Äëÿ äèññåðòàöèîííîé ðàáîòû îñîáóþ ðîëü èãðàþò ñâîéñòâà çàäà÷ ïîòîêîâîãîòèïà, áîëüøîå çíà÷åíèå èìååò çàäà÷à î ìàêñèìàëüíîì ïîòîêå è çàäà÷à î ïîòîêåìèíèìàëüíîé ñòîèìîñòè (Ôîðä è Ôàëêåðñîí), çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå(Ãàëëî, Ãðèãîðèàäèñ è Òàðüÿí).
Ýòè çàäà÷è ÿâëÿþòñÿ áàçîâûìè ñòàòè÷åñêèìè ïîòîêîâûìè çàäà÷àìè. Âî ìíîãèõ ñëó÷àÿõ èçó÷åíèå ïðîòåêàþùèõ âî âðåìåíè ïîòîêîâûõ ïðîöåññîâ ìîæåò áûòü ñâåäåíî ê ðàññìîòðåíèþ ñòàöèîíàðíûõ ïîòîêîâûõ çàäà÷.3Òàê, íàïðèìåð, â ðàáîòàõ Òåîäîðîâè÷à è Âóêàäèíîâè÷à, Õîëëà, Êàññåòà, Ãàñíèêîâàðàññìîòðåíû ñòàòè÷åñêèå ìåòîäû ìîäåëèðîâàíèÿ òðàíñïîðòíûõ ïîòîêîâ, â ðàáîòàõÔîðäà è Ôàëêåðñîíà, Ñêóòåëëû ðàññìîòðåíû äèíàìè÷åñêèå ïîòîêîâûå ïðîöåññû,çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî ïðîöåññà ñî ñòàòè÷åñêèìè ïðîïóñêíûìè ñïîñîáíîñòÿìè è âðåìåíàìè ïåðåõîäà ñâåäåíû ê ñòàòè÷åñêèì ïîòîêîâûì çàäà÷àì. Íåñìîòðÿ íà áîëåå ïîëóâåêà ñ ìîìåíòà ïîÿâëåíèÿ, ïîñòàíîâêè ýòèõ çàäà÷, äîïóñêàþùèåíåîïðåäåëåííîñòè íåêîòîðûõ õàðàêòåðèñòèê, ïîÿâèëèñü îòíîñèòåëüíî íåäàâíî â ðàáîòàõ Ãëîêíåðà è Íåìõàóçåðà, Õàíà, Ïåíãà è Âàíãà, Øåíãà è Ãàî. Ïðè ýòîì, íàäàííûé ìîìåíò îòñóòñòâóþò ðàáîòû, èçó÷àþùèå ïîòîêîâûå çàäà÷è â óñëîâèÿõ äèíàìè÷åñêè èçìåíÿþùèõñÿ ïàðàìåòðîâ è âíåøíèõ íåêîíòðîëèðóåìûõ âîçìóùåíèé.Çàäà÷è, ðàññìàòðèâàåìûå â äèññåðòàöèîííîé ðàáîòå, ìîòèâèðîâàííû èçìåí÷èâîñòüþ è ñòîõàñòè÷åñêîé ïðèðîäîé ðåàëüíûõ ôèçè÷åñêèõ ïðîöåññîâ.
Çàäà÷è ìàòåìàòè÷åñêîé îïòèìèçàöèè â óñëîâèÿõ ðàçëè÷íîãî ðîäà íåîïðåäåëåííîñòåé èçó÷àëèñüâ ðàáîòàõ ðàáîòàõ Ðîááèíñà è Ìîíðî (îáùèé ìåòîä ñòîõàñòè÷åñêîé àïïðîêñèìàöèè),Êèôåðà è Âîëüôîâèöà (ìåòîä êîíå÷íûõ ðàçíîñòåé), Êàëìàíà è Áüþñè(ôèëüòð Êàëìàíà-Áüþñè), Âèíåðà è Êîëìîãîðîâà (ôèëüòð Âèíåðà-Êîëìîãîðîâà),Ãðàíè÷èíà (ðåøåíèå îïòèìèçàöèîííûõ çàäà÷ ñ íåñòàòèñòè÷åñêèìè ïîìåõàìè), Êàìïè è Êàëàôèîðå (ñöåíàðíûé ïîäõîä), Õëåáíèêîâà, Ïîëÿêà è Êóíöåâè÷à.  ðàáîòàõÁåíâåíèñòå, Ìåòèâüå è Ïðèîðî, Áîäñîíà è Äóãëàñà, Àíòàë, Ãðàíè÷èíà è Ëåâè èçó÷àþòñÿ àäàïòèâíûå àëãîðèòìû, â ðàáîòàõ Ïàðôåíîâà è Òåðåõîâà, Êîïåòöà, Ìåëüíèêîâà è Ìåëüíèêîâîé èçó÷àþòñÿ ñìåæíûå âîïðîñû î ñèñòåìàõ ðåàëüíîãî âðåìåíè.Ñëåäóþùèå ðàáîòû ðàññìàòðèâàþò ñõîæèå ñ ïîñòàâëåííûìè â äèññåðòàöèîííîé ðàáîòå ïðèêëàäíûìè çàäà÷àìè: â ðàáîòàõ Òàíòàâè è Òàóñëè, Êèìà è Êàìåäû,×îãóóíà è Êàìåäû ðàññìàòðèâàþòñÿ àëãîðèòìû îïòèìàëüíîãî ñòàòè÷åñêîãî áàëàíñèðîâàíèÿ çàãðóçêè äëÿ òèïîâûõ ñåòåé (çâåçäà, êîëüöî è ò.ï.) ñ äîñòàòî÷íî îáùèìèïðåäïîëîæåíèÿìè î ïðîïóñêíîé ñïîñîáíîñòè ñåòè.
 ðàáîòå Ãðîñó è Õðîíîïóëîñàðàññìàòðèâàþòñÿ èãðîâûå ìîäåëè çàäà÷è ðàñïðåäåëåíèÿ íàãðóçêè. Ñòîõàñòè÷åñêèåïîñòàíîâêè çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ ïîÿâèëèñü îòíîñèòåëüíî íåäàâíî è áûëèïðåäëîæåíû â ðàáîòàõ Àìåëèíîé, Àìåëèíîé è Ôðàäêîâà, Ãðàíè÷èíûì è Àìåëèíîéè äð.Áîëüøèíñòâî èç ïåðå÷èñëåííûõ ðàáîò ñîñòàâëÿþò îáùèé ìàòåìàòè÷åñêèé ôóíäàìåíò çàäà÷è ðàñïðåäåëåíèÿ ðåñóðñîâ, ëèøü íåáîëüøàÿ ÷àñòü ðàáîò èçó÷àåò îñîáåííîñòè ðåàëèçàöèè ìàòåìàòè÷åñêèõ ìåòîäîâ â ìóëüòèàãåíòíûõ ñèñòåìàõ. Îñíîâíîé ñëîæíîñòüþ òàêîé ðåàëèçàöèè ÿâëÿåòñÿ äåöåíòðàëèçîâàííîñòü. Òðàäèöèîííàÿ4ïàðàäèãìà ïàðàëëåëüíûõ âû÷èñëåíèé ïîäðàçóìåâàåò íàëè÷èå öåíòðàëüíîãî óçëà,èìåþùåãî èíôîðìàöèþ î âñåì âû÷èñëèòåëüíîì ïðîöåññå.
 ìóëüòèàãåíòíûõ ñèñòåìàõ òàêèå óçëû îáû÷íî îòñóòñòâóþò, ÷òî çíà÷èòåëüíî óïðîùàåò ïîñòðîåíèå ñèñòåìû è å¼ ìàñøòàáèðóåìîñòü, îäíàêî âî ìíîãèõ ñëó÷àÿõ çàòðóäíÿåò âû÷èñëèòåëüíûéâîçìîæíà ëè ýôôåêòèâíàÿ ðåàëèçàöèÿ êëàññè÷åñêèõ ìåòîäîâ îïòèìàëüíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñèñòåìàõ?  ðàáîòå ïîëó÷åí ïîëîæèòåëüíûéïðîöåññ. Îäèí èç îáùèõ âîïðîñîâ, èçó÷åíèþ êîòîðîãî íàïðàâëåíà ýòà ðàáîòà, îòâåò äëÿ íåñêîëüêèõ êîíêðåòíûõ çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ, îñíîâàííûõ íà ðåøåíèè ïîòîêîâûõ çàäà÷ îïòèìèçàöèè.
Àëãîðèòìû òàêîãî ðîäà îáû÷íî íàçûâàþòñÿðàñïðåäåëåííûìèèëèìóëüòèàãåíòíûìèè øèðîêî èñïîëüçóþòñÿ íà ïðàêòèêå: âðàáîòàõ Áîéäà è äð., Øàõà, Êåìïå è äð. èçó÷àþòñÿ ïðèìåíåíèå ðàñïðåäåëåííûõàëãîðèòìîâ, íàçûâàåìûõ ñïëåòíÿìè, â ðàáîòàõ Ìàããñà è äð., Õå è äð. èçó÷àþòñÿàëãîðèòìû ñèíõðîíèçàöèè âðåìåíè â ðàñïðåäåëåííûõ ñåòÿõ, â ðàáîòàõ Ìàíôðåäè,Æó è äð. èçó÷àþòñÿ àëãîðèòìû ñîãëàñîâàíèÿ ïîêàçàíèé ñåíñîðíûõ ñåòåé, â ðàáîòàõÎëôàòè-ñàáåðà è Ìþððåÿ, Ôàêñà è Ìþððåÿ, Ðåíà è äð., Ðèêîñà è äð., Àìåëèíîé,Àìåëèíîé è Ôðàäêîâà, Ïàðñåãîâà, Ïîëÿêîâà è Ùåðáàêîâà èçó÷àþòñÿ ïðîòîêîëûêîíñåíñóñà è èõ ïðèëîæåíèÿ, â ðàáîòàõ Êàëÿåâà, Ãàéäóêà è Êàïóñòÿíà, Ôàêñà èÌþððåÿ ðàññìàòðèâàþòñÿ çàäà÷è êîëëåêòèâíîãî âçàèìîäåéñòâèÿ ãðóïï ìîáèëüíûõðîáîòîâ.Êàê óæå áûëî îòìå÷åíî, îáùåå ïðåèìóùåñòâî ìóëüòèàãåíòíîãî ïîäõîäà çàêëþ÷àåòñÿ â ïðîñòîòå îðãàíèçàöèè è ìàñøòàáèðóåìîñòè ñèñòåìû. Äåòàëüíî îñîáåííîñòèòàêèõ ñèñòåì áûëè èçó÷åíû â ðàáîòàõ Âèòòèõà è Ñêîáåëåâà, Ñêîáåëåâà, Ñîëëîãóáà,Èâàùåíêî è äð., Ðæåâñêîãî, Ãîðîäåöêîãî, Ãîðîäåöêîãî, Ãðóøèíñêîãî è Õàáàëîâà.Öåëüþ äèññåðòàöèîííîé ðàáîòûÿâëÿåòñÿ ðàçðàáîòêà è îáîñíîâàíèå àëãî-ðèòìîâ ýôôåêòèâíîãî óïðàâëåíèÿ ðåñóðñàìè â ìóëüòèàãåíòíûõ ñåòÿõ â óñëîâèÿõíåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåì ïàðàìåòðîâ ñåòè è îêðóæàþùåéñðåäû.
Äëÿ äîñòèæåíèÿ öåëè áûëè ïîñòàâëåíû ñëåäóþùèå çàäà÷è:1. Èññëåäîâàòü âîçìîæíîñòü ïðèìåíåíèÿ ìåòîäîâ îïòèìèçàöèè äèíàìè÷åñêèõïðîöåññîâ ïîòîêîâîãî òèïà äëÿ ýôôåêòèâíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ.2. Ðàçðàáîòàòü è îáîñíîâàòü íîâûå àëãîðèòìû ýôôåêòèâíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ.3. Èññëåäîâàòü ðàáîòîñïîñîáíîñòü ðàçðàáîòàííûõ íîâûõ àëãîðèòìîâ ýôôåêòèâ-5íîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ â óñëîâèÿõ íåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåì ïàðàìåòðîâ ñåòè è îêðóæàþùåé ñðåäû,ðàçðàáîòàòü è îáîñíîâàòü ñîîòâåòñòâóþùèå àäàïòèâíûå ìîäèôèêàöèè, èññëåäîâàòü âîçìîæíîñòè ðàíäîìèçàöèè äëÿ óñêîðåíèÿ ïðîöåññà ðåøåíèÿ çàäà÷.4.
Ðåàëèçîâàòü èññëåäîâàííûå ìåòîäû è ïðîâåñòè èõ àïðîáàöèþ äëÿ ðåøåíèÿçàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ â óñëîâèÿõ íåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåì ïàðàìåòðîâ ñåòè è îêðóæàþùåéñðåäû.Ìåòîäû èññëåäîâàíèÿ.  äèññåðòàöèîííîé ðàáîòå ïðèìåíÿþòñÿ ìåòîäû ìàòåìàòè÷åñêîé îïòèìèçàöèè, òåîðèè âåðîÿòíîñòåé è ìàòåìàòè÷åñêîé ñòàòèñòèêè, òåîðèè ãðàôîâ, òåîðèè äèíàìè÷åñêèõ ñèñòåì, èìèòàöèîííîãî ìîäåëèðîâàíèÿ, ìóëüòèàãåíòíûõ òåõíîëîãèé.Îñíîâíûå ïîëîæåíèÿ, âûíîñèìûå íà çàùèòó.1. Ïðåäëîæåíà ôîðìóëèðîâêà êëàññà çàäà÷ ìóëüòèàãåíòíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â âèäå çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïðîöåññà ïîòîêîâîãî òèïà.2.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
