Диссертация (1150610)
Текст из файла
ÑÀÍÊÒ-ÏÅÒÅÐÁÓÐÃÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉÓÍÈÂÅÐÑÈÒÅÒÍà ïðàâàõ ðóêîïèñèÌàëüêîâñêèé Íèêîëàé Âëàäèìèðîâè÷ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÛÅ ÀËÃÎÐÈÒÌÛÐÀÑÏÐÅÄÅËÅÍÈß ÐÅÑÓÐÑΠÂÀÄÀÏÒÈÂÍÛÕ ÌÓËÜÒÈÀÃÅÍÒÍÛÕÑÈÑÒÅÌÀÕ01.01.09 Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêàÿ êèáåðíåòèêàÄèññåðòàöèÿíà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÍàó÷íûé ðóêîâîäèòåëü:äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê, ïðîôåññîðÎëåã Íèêîëàåâè÷ Ãðàíè÷èíÑàíêò-Ïåòåðáóðã2017ÎãëàâëåíèåÂâåäåíèå1Ïîòîêîâûå ïðîöåññû è èõ ïðèëîæåíèå â çàäà÷àõ ìóëüòèàãåíòíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ121.1121519231.21.324Ïîòîêîâûå ïðîöåññû .
. . . . . . . . . . . . . . . . . . . . .1.1.1 Îïòèìàëüíûå äèíàìè÷åñêèå ïðîöåññû . . . . . . . .1.1.2 Äèíàìè÷åñêèå ïîòîêîâûå ïðîöåññû . . . . . . . . . .1.1.3 Ñòîõàñòè÷åñêèå ïîòîêîâûå ïðîöåññû . . . . . . . . .Ìåòîä ïðîòàëêèâàíèÿ ïðåäïîòîêà äëÿïîòîêîâûõ çàäà÷ ëèíåéíîãîïðîãðàììèðîâàíèÿ . . . . . . . . . . . . . . . . . .
. . . . .1.2.1 Çàäà÷à î ìàêñèìàëüíîì ïîòîêå . . . . . . . . . . . .1.2.2 Çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå . . . . . . . . . .Äâå ïîòîêîâûõ çàäà÷è ìóëüòèàãåíòíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.1 Çàäà÷à áàëàíñèðîâàíèÿ çàãðóçêè â ñåòè . . . . . . .1.3.2 Ñáîð èíôîðìàöèè ãðóïïîé ÁÏËÀ . . . . .
. . . . .252632373740Äâà ìåòîäà ïîñòðîåíèÿ îïòèìàëüíûõ ïîòîêîâûõ ïðîöåññîâ â íåñòàöèîíàðíîì ñëó÷àå2.12.2Ìåòîä íà îñíîâå óñðåäíÿåìûõ ôóíêöèé . . . . .2.1.1 Êëàññ óñðåäíÿåìûõ ôóíêöèé . . . . . . .2.1.2 Äèíàìè÷åñêèå ïîòîêîâûå ïðîöåññû ñìåíÿþùèìèñÿ âî âðåìåíè ïðîïóñêíûìèñïîñîáíîñòÿìè . . . . . . . . . . .
. . . .2.1.3 Ïîäáîð ïàðàìåòðîâ àëãîðèòìà âñòîõàñòè÷åñêîì ñëó÷àå . . . . . . . . . . .Àäàïòèâíûé ìåòîä îñíîâàííûé íàðàíäîìèçèðîâàííîé ñòîõàñòè÷åñêîéàïïðîêñèìàöèè . . . . . . . . . . . . . . . . . . .2.2.1 Îáùàÿ ñõåìà ìåòîäà áàëàíñèðîâàíèÿ äóã246. . . . . .. . . . . .4646. .
. . . .48. . . . . .56. . . . . .. . . . . .59612.2.22.2.32.2.42.2.52.2.63Ñõîäèìîñòü ìåòîäîâ . . . . . . . . . . . . . .Ñõîäèìîñòü ñèíõðîííîãî àëãîðèòìà . . . . .Ñõîäèìîñòü ðàíäîìèçèðîâàííîãî àëãîðèòìàÈçâëå÷åíèå ðåøåíèÿ çàäà÷è îìàêñèìàëüíîì ïîòîêå . . . . . . . . . . . . .Ðåàëèçàöèÿ àëãîðèòìîâ â ìóëüòèàãåíòíûõñèñòåìàõ . . .
. . . . . . . . . . . . . . . . . .. . . .. . . .. . . .636773. . . .77. . . .79Ýêñïåðèìåíòàëüíûå ðåçóëüòàòû3.13.23.3Ïàêåò ïðèêëàäíûõ ïðîãðàììäëÿ ñèìóëÿöèè ïðîöåññàðàñïðåäåëåíèÿ çàãðóçêè . . . . . . . . . . . . . . . . . . . .Ýôôåêòèâíîå ðåøåíèå çàäà÷è îïàðàìåòðè÷åñêîì ïîòîêå . . . . . .
. . . . . . . . . . . . . .Òåñòèðîâàíèå àëãîðèòìîâáàëàíñèðîâàíèÿ çàãðóçêè . . . . . . . . . . . . . . . . . . .83838585Çàêëþ÷åíèå91Ëèòåðàòóðà92Ñïèñîê èëëþñòðàöèé102Ñïèñîê òàáëèö1033ÂâåäåíèåÀêòóàëüíîñòü òåìû.Ñåòåâûå òåõíîëîãèè íà÷àëè ðàçâèâàòüñÿ áî-ëåå ïîëóâåêà íàçàä, à â ïîñëåäíèå äåñÿòèëåòèÿ ýòà ñôåðà ïîäâåðãëàñüçíà÷èòåëüíîìó ðàñøèðåíèþ. Ðàçâèòèå Èíòåðíåòà è ëîãèñòèêè, çàìåäëåíèå ñêîðîñòè ðîñòà âû÷èñëèòåëüíûõ ìîùíîñòåé ýòè è äðóãèå ôàêòîðûïîâëèÿëè íà óâåëè÷åíèå èíòåðåñà ê ðàñïðåäåëåííûì âû÷èñëåíèÿì, ñåòåâûì òåõíîëîãèÿì è ñìåæíûì îáëàñòÿì.
 ñâîþ î÷åðåäü ìóëüòèàãåíòíûå òåõíîëîãèè ñòàëè ïîïóëÿðíûìè òîëüêî â ïîñëåäíèå 10-20 ëåò, íîïðè ýòîì çàíÿëè ñâîþ íèøó â îáëàñòè ðàñïðåäåëåííûõ âû÷èñëåíèé. Îñíîâíûì íàïðàâëåíèåì ýòîé ðàáîòû ÿâëÿåòñÿ èçó÷åíèå ñâîéñòâ íåñêîëüêèõ ìîäåëåé çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ ñóïîðîì íà ñåòåâûå ïîòîêîâûå çàäà÷è.
Îñíîâíîå òåîðåòè÷åñêîå íàïðàâëåíèå èññëåäîâàíèå ñòîõàñòè÷åñêèõ ïîòîêîâûõ ïðîöåññîâ, ïðàêòè÷åñêîå ðàñïðåäåëåíèå çàãðóçêè â âû÷èñëèòåëüíûõ ñåòÿõ è ïåðåäà÷à äàííûõâ ãðóïïàõ ìîáèëüíûõ ðîáîòîâ.Âñå ðàññìàòðèâàåìûå â ðàáîòå ìîäåëè ïîäðàçóìåâàþò îòûñêàíèå íåêîòîðîãî îïòèìàëüíîãî ïî âðåìåíè ïðîöåññà (âûïîëíåíèå ãðóïïû çàäàíèéçà íàèìåíüøåå âðåìÿ, ïåðåäà÷à íàáîðà ñîîáùåíèé â ãðóïïå ìîáèëüíûõðîáîòîâ çà íàèìåíüøåå âðåìÿ).
 òåîðèè óïðàâëåíèÿ, îñíîâíàÿ ìàññàðàáîò ïî ïîñòðîåíèþ îïòèìàëüíûõ äèíàìè÷åñêèõ ïðîöåññîâ îñíîâàíà íàïðèíöèïå äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ [46] è ïðèíöèïå ìàêñèìóìàÏîíòðÿãèíà [30].  ñëó÷àå îòñóòñòâèÿ íåîïðåäåëåííîñòåé è èçìåíåíèéïàðàìåòðîâ ñèñòåìû âî âðåìåíè, ðàññìàòðèâàåìûå çàäà÷è âûðîæäàþòñÿâ çàäà÷è ìàòåìàòè÷åñêîé îïòèìèçàöèè.  îáùåì âèäå òàêèå çàäà÷è ðàññìàòðèâàëèñü Êàíòîðîâè÷åì [19] (îáùàÿ òåîðèÿ ëèíåéíîãî ïðîãðàììèðîâàíèÿ), Õà÷èÿíîì [33] (ìåòîä ýëëèïñîèäîâ), Ïîëÿêîì [29] (îáùàÿ òåîðèÿ âûïóêëîé îïòèìèçàöèè), Êàðìàðêàðîì [77] (ïîëèíîìèàëüíûé ìåòîäâíóòðåííåé òî÷êè äëÿ çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ), Íåñòåðîâûìè Íåìèðîâñêèì [90] (ïîëèíîìèàëüíûå ìåòîäû äëÿ çàäà÷ íåëèíåéíîé âûïóêëîé îïòèìèçàöèè), Áîéäîì è Âàíäåíáåðãå [52] (ñîâðåìåííàÿ òåîðèÿîïòèìèçàöèè) è ìíîãèìè äðóãèìè.4Äëÿ äèññåðòàöèîííîé ðàáîòû îñîáóþ ðîëü èãðàþò ñâîéñòâà çàäà÷ ïîòîêîâîãî òèïà, áîëüøîå çíà÷åíèå èìååò çàäà÷à î ìàêñèìàëüíîì ïîòîêåè çàäà÷à î ïîòîêå ìèíèìàëüíîé ñòîèìîñòè (Ôîðä è Ôàëêåðñîí, [64]),çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå (Ãàëëî, Ãðèãîðèàäèñ è Òàðüÿí [65]).Ýòè çàäà÷è ÿâëÿþòñÿ áàçîâûìè ñòàòè÷åñêèìè ïîòîêîâûìè çàäà÷àìè.
Âîìíîãèõ ñëó÷àÿõ èçó÷åíèå ïðîòåêàþùèõ âî âðåìåíè ïîòîêîâûõ ïðîöåññîâ ìîæåò áûòü ñâåäåíî ê ðàññìîòðåíèþ ñòàöèîíàðíûõ ïîòîêîâûõ çàäà÷.Òàê, íàïðèìåð, â ðàáîòàõ Òåîäîðîâè÷à è Âóêàäèíîâè÷à [103], Õîëëà [39],Êàññåòà [55], Ãàñíèêîâà [37] ðàññìîòðåíû ñòàòè÷åñêèå ìåòîäû ìîäåëèðîâàíèÿ òðàíñïîðòíûõ ïîòîêîâ, â ðàáîòàõ Ôîðäà è Ôàëêåðñîíà [62], Ñêóòåëëû [99] ðàññìîòðåíû äèíàìè÷åñêèå ïîòîêîâûå ïðîöåññû, çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî ïðîöåññà ñî ñòàòè÷åñêèìè ïðîïóñêíûìè ñïîñîáíîñòÿìè è âðåìåíàìè ïåðåõîäà ñâåäåíû ê ñòàòè÷åñêèì ïîòîêîâûì çàäà÷àì. Íåñìîòðÿ íà áîëåå ïîëóâåêà ñ ìîìåíòà ïîÿâëåíèÿ, ïîñòàíîâêè ýòèõçàäà÷, äîïóñêàþùèå íåîïðåäåëåííîñòè íåêîòîðûõ õàðàêòåðèñòèê, ïîÿâèëèñü îòíîñèòåëüíî íåäàâíî â ðàáîòàõ Ãëîêíåðà è Íåìõàóçåðà [67], Õàíà,Ïåíãà è Âàíãà [72], Øåíãà è Ãàî [98]. Ïðè ýòîì, íà äàííûé ìîìåíò îòñóòñòâóþò ðàáîòû, èçó÷àþùèå ïîòîêîâûå çàäà÷è â óñëîâèÿõ äèíàìè÷åñêèèçìåíÿþùèõñÿ ïàðàìåòðîâ è âíåøíèõ íåêîíòðîëèðóåìûõ âîçìóùåíèé.Çàäà÷è, ðàññìàòðèâàåìûå â äèññåðòàöèîííîé ðàáîòå, ìîòèâèðîâàííûèçìåí÷èâîñòüþ è ñòîõàñòè÷åñêîé ïðèðîäîé ðåàëüíûõ ôèçè÷åñêèõ ïðîöåññîâ.
Çàäà÷è ìàòåìàòè÷åñêîé îïòèìèçàöèè â óñëîâèÿõ ðàçëè÷íîãî ðîäà íåîïðåäåëåííîñòåé èçó÷àëèñü â ðàáîòàõ ðàáîòàõ Ðîááèíñà è Ìîíðî [96] (îáùèé ìåòîä ñòîõàñòè÷åñêîé àïïðîêñèìàöèè), Êèôåðà è Âîëüôîâèöà [79] (ìåòîä êîíå÷íûõ ðàçíîñòåé), Êàëìàíà è Áüþñè [75](ôèëüòð Êàëìàíà-Áüþñè), Âèíåðà è Êîëìîãîðîâà [104] (ôèëüòð ÂèíåðàÊîëìîãîðîâà), Ãðàíè÷èíà [12, 14] (ðåøåíèå îïòèìèçàöèîííûõ çàäà÷ ñíåñòàòèñòè÷åñêèìè ïîìåõàìè), Êàìïè è Êàëàôèîðå [54] (ñöåíàðíûé ïîäõîä), Õëåáíèêîâà, Ïîëÿêà è Êóíöåâè÷à [34].  ðàáîòàõ Áåíâåíèñòå, Ìåòèâüå è Ïðèîðî [48], Áîäñîíà è Äóãëàñà [50], Àíòàë, Ãðàíè÷èíà è Ëåâè [44]èçó÷àþòñÿ àäàïòèâíûå àëãîðèòìû, â ðàáîòàõ Ïàðôåíîâà è Òåðåõîâà [27],Êîïåòöà [82], Ìåëüíèêîâà è Ìåëüíèêîâîé [26] èçó÷àþòñÿ ñìåæíûå âîïðî5ñû î ñèñòåìàõ ðåàëüíîãî âðåìåíè.Ñëåäóþùèå ðàáîòû ðàññìàòðèâàþò ñõîæèå ñ ïîñòàâëåííûìè â äèññåðòàöèîííîé ðàáîòå ïðèêëàäíûìè çàäà÷àìè: â ðàáîòàõ Òàíòàâè è Òàóñëè [101], Êèìà è Êàìåäû [80], ×îãóóíà è Êàìåäû [57] ðàññìàòðèâàþòñÿàëãîðèòìû îïòèìàëüíîãî ñòàòè÷åñêîãî áàëàíñèðîâàíèÿ çàãðóçêè äëÿ òèïîâûõ ñåòåé (çâåçäà, êîëüöî è ò.ï.) ñ äîñòàòî÷íî îáùèìè ïðåäïîëîæåíèÿìè î ïðîïóñêíîé ñïîñîáíîñòè ñåòè.
 ðàáîòå Ãðîñó è Õðîíîïóëîñà [70]ðàññìàòðèâàþòñÿ èãðîâûå ìîäåëè çàäà÷è ðàñïðåäåëåíèÿ íàãðóçêè. Ñòîõàñòè÷åñêèå ïîñòàíîâêè çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ ïîÿâèëèñü îòíîñèòåëüíî íåäàâíî è áûëè ïðåäëîæåíû â ðàáîòàõ Àìåëèíîé [5], Àìåëèíîéè Ôðàäêîâà [6], Ãðàíè÷èíà è Àìåëèíîé è äð. [42].Áîëüøèíñòâî èç ïåðå÷èñëåííûõ ðàáîò ñîñòàâëÿþò îáùèé ìàòåìàòè÷åñêèé ôóíäàìåíò çàäà÷è ðàñïðåäåëåíèÿ ðåñóðñîâ, ëèøü íåáîëüøàÿ ÷àñòüðàáîò èçó÷àåò îñîáåííîñòè ðåàëèçàöèè ìàòåìàòè÷åñêèõ ìåòîäîâ â ìóëüòèàãåíòíûõ ñèñòåìàõ. Îñíîâíîé ñëîæíîñòüþ òàêîé ðåàëèçàöèè ÿâëÿåòñÿäåöåíòðàëèçîâàííîñòü. Òðàäèöèîííàÿ ïàðàäèãìà ïàðàëëåëüíûõ âû÷èñëåíèé ïîäðàçóìåâàåò íàëè÷èå öåíòðàëüíîãî óçëà, èìåþùåãî èíôîðìàöèþ î âñåì âû÷èñëèòåëüíîì ïðîöåññå.  ìóëüòèàãåíòíûõ ñèñòåìàõ òàêèå óçëû îáû÷íî îòñóòñòâóþò, ÷òî çíà÷èòåëüíî óïðîùàåò ïîñòðîåíèåñèñòåìû è å¼ ìàñøòàáèðóåìîñòü, îäíàêî âî ìíîãèõ ñëó÷àÿõ çàòðóäíÿåòâû÷èñëèòåëüíûé ïðîöåññ.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
