Диссертация (Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах)

ÑÀÍÊÒ-ÏÅÒÅÐÁÓÐÃÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉÓÍÈÂÅÐÑÈÒÅÒÍà ïðàâàõ ðóêîïèñèÌàëüêîâñêèé Íèêîëàé Âëàäèìèðîâè÷ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÛÅ ÀËÃÎÐÈÒÌÛÐÀÑÏÐÅÄÅËÅÍÈß ÐÅÑÓÐÑΠÂÀÄÀÏÒÈÂÍÛÕ ÌÓËÜÒÈÀÃÅÍÒÍÛÕÑÈÑÒÅÌÀÕ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].Áîëüøèíñòâî èç ïåðå÷èñëåííûõ ðàáîò ñîñòàâëÿþò îáùèé ìàòåìàòè÷åñêèé ôóíäàìåíò çàäà÷è ðàñïðåäåëåíèÿ ðåñóðñîâ, ëèøü íåáîëüøàÿ ÷àñòüðàáîò èçó÷àåò îñîáåííîñòè ðåàëèçàöèè ìàòåìàòè÷åñêèõ ìåòîäîâ â ìóëüòèàãåíòíûõ ñèñòåìàõ. Îñíîâíîé ñëîæíîñòüþ òàêîé ðåàëèçàöèè ÿâëÿåòñÿäåöåíòðàëèçîâàííîñòü. Òðàäèöèîííàÿ ïàðàäèãìà ïàðàëëåëüíûõ âû÷èñëåíèé ïîäðàçóìåâàåò íàëè÷èå öåíòðàëüíîãî óçëà, èìåþùåãî èíôîðìàöèþ î âñåì âû÷èñëèòåëüíîì ïðîöåññå.  ìóëüòèàãåíòíûõ ñèñòåìàõ òàêèå óçëû îáû÷íî îòñóòñòâóþò, ÷òî çíà÷èòåëüíî óïðîùàåò ïîñòðîåíèåñèñòåìû è å¼ ìàñøòàáèðóåìîñòü, îäíàêî âî ìíîãèõ ñëó÷àÿõ çàòðóäíÿåòâû÷èñëèòåëüíûé ïðîöåññ.