Диссертация (1150610), страница 7
Текст из файла (страница 7)
Äîïîëíèìýòîò ãðàô ôèêòèâíîé âåðøèíîé t è äóãàìè (v, t), v ∈ V ñ ïðîïóñêíîé ñïîñîáíîñòüþ pi . Ýòîò òðþê ïîçâîëÿåò òðàêòîâàòü ïðîöåññ âûïîëíåíèÿ çàäà÷è êàê ïåðåäà÷ó ýòîãî çàäàíèÿ íà óçåë t. Ïîëàãàÿ, ÷òî V = {1, . . . , n},t = n+1 ïîëó÷àåì, ÷òî íàøà çàäà÷à çàêëþ÷àåòñÿ â ïåðåäà÷å ïîòîêà ñ óçëîâ v ∈ V íà óçåë t, ÷òî ÿâëÿåòñÿ çàäà÷åé (1.10) ñ íà÷àëüíûì è êîíå÷íûìñîñòîÿíèÿìèx− = (q1 , .
. . , qn , 0)T ,+x = (0, . . . , 0,nXqi )T .i=1Äëÿ ïîëó÷åíèÿ çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå â ïîëó÷åííûé ãðàôäîáàâëÿåòñÿ ôèêòèâíûé èñòîê. Èòîãîâûé ãðàô èçîáðàæåí íà ðèñ. 1.639aaτp aabqτcvabqsbτcτp btbvqvτcvvНачальнаяПередачазагрузказадач посетиÐèñ. 1.6:τpВыполнениезадачÃðàô äëÿ çàäà÷è áàëàíñèðîâàíèÿ íàãðóçêèãðàô. Äàííàÿ ìîäåëü â ïîäðîáíîñòÿõ îïèñàíà â [22, 23, 87].Äëÿ ìîäåëèðîâàíèÿ ïîâåäåíèÿ òàêîé ñèñòåìû ïî ññûëêå [38] äîñòóïåíñèìóëÿòîð. Îäèí èç ïðèìåðîâ, äîñòóïíûõ íà ýòîì ñèìóëÿòîðå, èçîáðàæåí íà ðèñ. 1.7.1.3.2Ñáîð èíôîðìàöèè ãðóïïîé ÁÏËÀÁåñïèëîòíûå ëåòàòåëüíûå àïïàðàòû (ÁÏËÀ) íàáðàëè áîëüøóþ ïîïóëÿðíîñòü è óæå ñåé÷àñ ïîâñåìåñòíî èñïîëüçóþòñÿ íà ïðàêòèêå.
 êà÷åñòâå ïðèìåðà, ãäå âîçíèêàåò íåîáõîäèìîñòü ðåøåíèÿ ïîòîêîâûõ çàäà÷,ìîæíî ïðèâåñòè çàäà÷ó ìîíèòîðèíãà îáëàñòè: ãðóïïå ÁÏËÀ òðåáóåòñÿïåðèîäè÷åñêè ïðîëåòàòü íàä íåêîòîðîé îáëàñòüþ è äåëàòü ñíèìêè / âèäåîçàïèñü (êàê ïðèìåð, ïðèìåíåíèå ÁÏËÀ äëÿ ìîíèòîðèíãà çàïîâåäíèêîâ, [1]). Òåõíîëîãèè óïðàâëåíèÿ ãðóïï ÁÏËÀ â òàêèõ óñëîâèÿõ èçó÷åíû401Пропускнаяспособность21(2, 20)3(5, 0)11111(1, 50)61(3, 10)1(Производительность,загрузка)415(1, 40)(1, 30)0Задач передано(всего)2Необходимоевремя=2404432402401Задач выполнено(всего)24624342041824Ðèñ. 1.7:524Ïðèìåð áàëàíñèðîâàíèÿ íàãðóçêè41â [3, 4, 43]. Îäíà èç ñëóæåáíûõ çàäà÷, êîòîðàÿ âîçíèêàåò â òàêèõ ïðèëîæåíèÿõ, ñáîð èíôîðìàöèè íà îäíîì ÁÏËÀ. Íàïðèìåð, òàêàÿ íåîáõîäèìîñòü ìîæåò âîçíèêíóòü, åñëè íóæíî ðåãóëÿðíî ñîáèðàòü ñíèìêèòåððèòîðèè äëÿ âíåøíåé îáðàáîòêè.
Äëÿ ýòîãî, ÷òîáû íå îòâëåêàòü âñþãðóïïó ÁÏËÀ îò ìîíèòîðèíãà, âñå äàííûå ìîãóò áûòü ïåðåäàíû íà îäèíÁÏËÀ, ïîñëå ÷åãî îí ëåòèò íà áàçîâóþ ñòàíöèþ äëÿ ïåðåäà÷è äàííûõ.Íà ïðàêòèêå â áîëüøèõ ìíîãîôóíêöèîíàëüíûõ ñèñòåìàõ çàäà÷è ìàðøðóòèçàöèè ïàêåòîâ èíôîðìàöèè ïðèâîäÿò ê ñëîæíûì çàäà÷àì îïòèìèçàöèè, òàêèì êàê çàäà÷à î ìíîãîòèïíûõ ïîòîêàõ [83].  íåêîîïåðàòèâíûõñèñòåìàõ (ò.å. ñèñòåìàõ, â êîòîðûõ ðàçëè÷íûå êîìïîíåíòû ñèñòåìû èìåþò êîíôëèêòóþùèå çàäà÷è è ïðè ýòîì ïðèîðèòåò çàäà÷ ðàçíûõ êîìïîíåíò îäèíàêîâûé) ïðèíÿòî ìîäåëèðîâàíèå ñ èñïîëüçîâàíèåì òåîðèè èãð,÷òî îáû÷íî ïðèâîäèò ê íåëèíåéíûì çàäà÷àì îïòèìèçàöèè, êàê íàïðèìåðâ [37]. Òåì íå ìåíåå, â òàêîé ÷àñòíîé çàäà÷å êàê ñáîð èíôîðìàöèè íà îäíîì ÁÏËÀ, â êîòîðîé öåëü îäíà äëÿ âñåõ ÁÏËÀ, ïðèìåíèìû ìåòîäû,îïèñàííûå ðàíåå â ýòîé ðàáîòå, ÷òî ïîçâîëÿåò íàõîäèòü îïòèìàëüíóþìàðøðóòèçàöèþ íàìíîãî áûñòðåå.Ïðåäïîëîæèì, ÷òî â öåëÿõ ìîíèòîðèíãà ìåñòíîñòè, êàæäûé ÁÏËÀëåòàåò ïî ñâîåé ïðåäîïðåäåëåííîé òðàåêòîðèè.
Îáîçíà÷èì çà ϕi (t) òðàåêòîðèþ ïîëåòà i-îãî ÁÏËÀ. Äàëåå ïîëàãàåì, ÷òî äëÿ êîììóíèêàöèèèñïîëüçóåòñÿ áåñïðîâîäíàÿ ïåðåäà÷à äàííûõ, ôóíêöèÿ K : R+ → R+îïðåäåëÿåò çàâèñèìîñòü ïðîïóñêíîé ñïîñîáíîñòè îò ðàññòîÿíèÿ ìåæäóäâóìÿ ÁÏËÀ. Òàêèì îáðàçîì, ôóíêöèÿ ïðîïóñêíîé ñïîñîáíîñòè ìåæäóÁÏËÀ i è j åñòücij (t) = K(||ϕi (t) − ϕj (t)||2 ).Íà ïðàêòèêå ÁÏËÀ äàëåêî íå âñåãäà ìîãóò ïåðåäàâàòü èíôîðìàöèþäðóã äðóãó.
Ìîæíî äàæå ñêàçàòü, ÷òî áîëüøèíñòâî âðåìåíè îíè íàõîäÿòñÿ íà áîëüøîì ðàññòîÿíèè äðóã îò äðóãà, à âñÿ êîììóíèêàöèÿ ïðîèñõîäèòâ íåáîëüøèå ïðîìåæóòêè âðåìåíè, êîãäà îíè ñáëèæàþòñÿ, êàê ïîêàçàíîíà ðèñ. 1.8. Òàêèì îáðàçîì, ïðîïóñêíàÿ ñïîñîáíîñòü áóäåò èìåòü âèä êàêíà ðèñ. 1.9.Òàêèì îáðàçîì, ïîâåäåíèå cij (t) ïîëíîñòüþ çàâèñèò îò ïîâåäåíèÿ ϕi (t)42Ðèñ. 1.8:Ïðèìåð òðàåêòîðèé ÁÏËÀ è çîí âçàèìîäåéñòâèÿ.0.50.450.40.350.30.250.20.150.10.050050100150200250300350400450500Îáùèé âèä ôóíêöèè ïðîïóñêíûõ ñïîñîáíîñòåé. Îñíîâíóþ ÷àñòü âðåìåíè ïðîïóñêíàÿ ñïîñîáíîñòü ðàâíà íóëþ.
Åñëè òðàåêòîðèè ïîëåòà ïåðèîäè÷íû, òî èïðîïóñêíàÿ ñïîñîáíîñòü ïåðèîäè÷íà.Ðèñ. 1.9:43è ϕj (t). Çíà÷èò, äîñòàòî÷íî, ÷òîáû ϕi (t) áûëè ïåðèîäè÷åñêèì ôóíêöèÿìè, äëÿ òîãî, ÷òîáû ôóíêöèÿ cij (t) áûëà óñðåäíÿåìîé. Ñòîèò îòìåòèòü,÷òî íà ïðàêòèêå îáû÷íî íà òðàåêòîðèþ ïîëåòà âëèÿþò íåêîòîðûå âíåøíèå íåêîíòðîëèðóåìûå âîçäåéñòâèÿ (â îñíîâíîì, ïîãîäíûå óñëîâèÿ). Åñëè ñ÷èòàòü ýòè ôàêòîðû ñòàòèñòè÷åñêèì øóìîì, òî cij (t) âñå åùå ÿâëÿåòñÿ óñðåäíÿåìîé è ïîäïàäàåò ïîä ïåðâûé ñòàòèñòè÷åñêèé ñëó÷àé, ðàçîáðàííûé â ïðåäûäóùåì ðàçäåëå.44Minimum breakpoint GGT(G, a, b, λl , λr )f ← Maximum ow(G, c(λl ));Sl ← Minimum cut (G, c(λl ), f );La ← 0;Lb ← 0;Functionfore = (i, j), i ∈ Sl , j ∈ V \ SlLa ← La + ae ;Lb ← Lb + be ;doInitialize(GR , c(λr ), f , h);while true do∃i ∈ V, i 6= s, t : excess(i) > 0 doApply push(GR , i, e, c, f , h) or relabel(GR , i, c, f , h) whicheveris applicable;whileSr ← Minimum cut (G, c(λr ), f );Ra ← 0;Rb ← 0;for e = (i, j), i ∈ SR , j ∈ V \ SR doRa ← Ra + ae ;Rb ← Rb + be ;ifLa = Ra and Lb = Rbreturn λr ;thenelseλr ←forforLa −RaLb −Rb ;e = (s, i) ∈ E, hi < nfe ← max(ce (λr ), fe );doe = (i, v) ∈ E dofe ← min(ce (λr ), fe );45Ãëàâà 2Äâà ìåòîäà ïîñòðîåíèÿîïòèìàëüíûõ ïîòîêîâûõïðîöåññîâ âíåñòàöèîíàðíîì ñëó÷àå2.12.1.1Ìåòîä íà îñíîâå óñðåäíÿåìûõ ôóíêöèéÊëàññ óñðåäíÿåìûõ ôóíêöèéÂñå äàëüíåéøèå ðàññóæäåíèÿ è îáîñíîâàíèÿ áóäóò ïðèâîäèòüñÿ äëÿñëåäóþùåãî êëàññà ðåãóëÿðíûõ ôóíêöèé.Î ï ð å ä å ë å í è å1.Ëîêàëüíî èíòåãðèðóåìàÿ ïî Ëåáåãó ôóíêöèÿf ∈ L1loc ([0; +∞)) íàçûâàåòñÿ óñðåäíÿåìîé, åñëè ñóùåñòâóåò ñëåäóþùèé ïðåäåëZ1 τavg(f ) = limf dµ < +∞.τ →+∞ τ 0 êà÷åñòâå ïðèìåðîâ ìîæíî ïðèâåñòè ñëåäóþùèå âèäû ôóíêöèé.• Ëþáàÿ ïåðèîäè÷åñêàÿ ôóíêöèÿ óñðåäíÿåìà.t→+∞• Åñëè f (t) −−−−→ f¯ ïî÷òè âñþäó íà [0, +∞), òî f óñðåäíÿåìà ñîñðåäíèì çíà÷åíèåì f¯.46• Åñëè ξ1 , ξ2 , .
. . ïîñëåäîâàòåëüíîñòü ñëó÷àéíûõ âåëè÷èí, óäîâëåòâîðÿþùàÿ óñèëåííîìó çàêîíó áîëüøèõ ÷èñåë, ñ ìàò. îæèäàíèåìEξi = ξ , òî ôóíêöèÿ f (t) = ξ[t] óñðåäíÿåìà ñ âåðîÿòíîñòüþ 1 ñîñðåäíåé âåëè÷èíîé ξ :n Z n1f µ → ξ = PrPrn 01Xξi → ξn i=1!= 1. äàëüíåéøåì ïîíàäîáÿòñÿ äâå ïðîñòûå ëåììû îá óñðåäíÿåìûõ ôóíêöèÿõ.Ë å ì ì à2.1.Åñëè f óñðåäíÿåìàÿ íåîòðèöàòåëüíàÿ ôóíêöèÿ, òîäëÿ ëþáûõ T > 0 è 0 < < 1 ñóùåñòâóåò −∞ < σ ≤ 0 òàêîå, ÷òî∀τ ≥ 0T +τZf dµ ≥ avg(f )(1 − )(τ + σ).TÄîêàçàòåëüñòâî. Èç îïðåäåëåíèÿ1τR T +τT0 ñóùåñòâóåò τ 0 òàêîå, ÷òî1∀τ > τ :τ0f → avg(f ) äëÿ ëþáîãî >T +τZTf dµ > avg(f )(1 − )òàêèì îáðàçîì, åñëè σ ≤ 0, òî0∀τ > τ :ZTT +τf dµ > avg(f )(1 − )(τ + σ).Ñëåäîâàòåëüíî, ìîæíî âçÿòü σ ñëåäóþùèì îáðàçîì1σ := inf 0τ ∈[0,τ ] avg(f )(1 − )ZTT +τf dµ − τ.Òàê êàê ïðè τ = 0 ìèíèìèçèðóåìîå âûðàæåíèå èìååò çíà÷åíèå 0, òîσ ≤ 0, ÷òî ãàðàíòèðóåò ñîîòâåòñòâóþùåå íåðàâåíñòâî äëÿ τ > τ 0 .Ë å ì ì à2.2.Åñëè f óñðåäíÿåìàÿ íåîòðèöàòåëüíàÿ ôóíêöèÿ, òî47äëÿ ëþáûõ T > 0 è > 0 ñóùåñòâóåò 0 ≤ σ < +∞ òàêîå, ÷òî∀τ ≥ 0T +σ+τZf dµ ≤ avg(f )(1 + )(τ + σ).T +σÄîêàçàòåëüñòâî.
Èç îïðåäåëåíèÿ1τR T +τT0 ñóùåñòâóåò τ 0 òàêîå, ÷òî0∀τ ≥ τ :f → avg(f ) äëÿ ëþáîãî >T +τZf dµ < avg(f )(1 + )τ.TÂçÿâ σ = τ 0 ïîëó÷àåì∀τ ≥ 0ZT +σ+τT +σf dµ ≤T +σ+τZf dµT≤ avg(f )(1 + )(τ + σ).2.1.2Äèíàìè÷åñêèå ïîòîêîâûå ïðîöåññû ñìåíÿþùèìèñÿ âî âðåìåíè ïðîïóñêíûìèñïîñîáíîñòÿìèÐàññìîòðèì ñëåäóþùåå îáîáùåíèå çàäà÷è (1.10) è (1.12)ìèíèìèçèðîâàòü(2.1)ïðè óñëîâèèτ,ẋ = B(σ)u, x(0) = x− ; x(τ ) = x+ ,x(t) ≥ 0n , 0 ≤ u (t) ≤ c (t).ijij48ãäå ce ∈ L1loc ([0; +∞)), σ = (σ1 , . .
. , σm )T , σi âðåìÿ ïåðåõîäà ïî äóãå i,B(σ) îáîçíà÷àåò ñëåäóþùèé îïåðàòîð:(2.2)[B(σ)u]i (t) =Xe∈in(i)ue (t − σe ) −Xue (t).e∈out(i)Çàìåòèì, ÷òî â ñëó÷àå íóëåâûõ âðåìåíàõ ïåðåõîäà çàäà÷à âûðîæäàåòñÿ (1.12), ïðè ïîñòîÿííûõ ïðîïóñêíûõ ñïîñîáíîñòÿõ â (1.10). Îáîçíà÷èì÷åðåç τ ∗ (x− , x+ , σ, c) îïòèìàëüíîå âðåìÿ (2.1) ñ âõîäíûìè ïàðàìåòðàìèx− , x+ , σ, c.Ë å ì ì àÐàññìîòðèì (1.10) ñ ïàðàìåòðàìè x− , x+ è c̄.
Ñó-2.3.ùåñòâóåò ñòàòè÷åñêîå îïòèìàëüíîå óïðàâëåíèå u(t) ≡ ū òàêîå, ÷òîïîäãðàô G0 = hV, E 0 i ñ ìíîæåñòâîì äóã E 0 = {(i, j) ∈ E | ūij > 0} íåñîäåðæèò öèêëîâ.Äîêàçàòåëüñòâî. Ñóùåñòâîâàíèå îïòèìàëüíîãî ñòàòè÷åñêîãîóïðàâëåíèÿ ïîêàçàíî â Ëåììå 2.1. Äîêàæåì ñóùåñòâîâàíèå àöèêëè÷åñêîãî óïðàâëåíèÿ.Ïóñòü ū òàêîå îïòèìàëüíîå ñòàòè÷åñêîå óïðàâëåíèå, êîòîðîå ìèíèìèçèðóåò êâàäðàòè÷íóþ ôîðìónXū2ij .i,j=1Åñëè òàêîå óïðàâëåíèå ñîäåðæèò öèêë, òî çà ñ÷åò óìåíüøåíèÿ ue âäîëüýòîãî öèêëà ìîæíî óìåíüøèòü çíà÷åíèå êâàäðàòè÷íîé ôîðìû.
À çíà÷èòóïðàâëåíèå, ìèíèìèçèðóþùåå ýòó ôîðìó, íå ñîäåðæèò öèêëîâ. Ò å î ð å ì à2.1.Ðàññìîòðèì (2.1) ñ ôèêñèðîâàííûìè óñðåäíÿå-ìûìè íåîòðèöàòåëüíûìè ôóíêöèÿìè ïðîïóñêíûõ ñïîñîáíîñòåé ce (t)è íåêîòîðûì íåîòðèöàòåëüíûì âåêòîðîì σ . Äëÿ ëþáîãî 0 < < 1ñóùåñòâóåò T () > 0 òàêîå, ÷òî äëÿ ëþáûõ x− , x+ âûïîëíÿåòñÿτ ∗ (x− , x+ , σ, c) ≤1+1−n−1τ ∗ (x− , x+ , 0m , avg(c)) + T ().49Äîêàçàòåëüñòâî. Çàôèêñèðóåì 0 < < 1, x− è x+ . Ïóñòü u∗ îïòèìàëüíîå ñòàòè÷åñêîå àöèêëè÷åñêîå óïðàâëåíèå, ñîîòâåòñòâóþùåå τ̃ =τ ∗ (x− , x+ , 0m , avg(c)).
Ââåäåì âñïîìîãàòåëüíûå âåëè÷èíû èíäóêòèâíî ïîñòðóêòóðå óïðàâëåíèÿ (ñ÷èòàåì, ÷òî ìàêñèìóì äëÿ ïóñòîãî ìíîæåñòâîåñòü 0 â îïðåäåëåíèè Ti () è 1 â îïðåäåëåíèè τi ())Ti () + σij+ () + σij − σij− (),Tj () = max∗uij >0σij+ () è σij− () âåëè÷èíû, óäîâëåòâîðÿþùèå∀τ ≥ 0∀τ ≥ 0è íàêîíåö+Ti ()+σij+τZ+Ti ()+σijZ+Ti ()+σij+τ+Ti ()+σijcij dµ ≤ avg(cij )(1 + )(τ + σij+ ()),cij dµ ≥ avg(cij )(1 − )(τ + σij− ())1+τi ().uij >0 1 − τj () = max∗Äëÿ ïðîñòîòû çàïèñè âåëè÷èíû, ñâÿçàííûå ñ äóãàìè, ïðîèíäåêñèðîâàíûíà÷àëîì è êîíöîì äóãè ñîîòâåòñòâåííî. Îòìåòèì, ÷òî ýòè îïðåäåëåíèÿîñìûñëåííû òîëüêî åñëè u∗ íå ñîäåðæèò öèêëîâ. Ñóùåñòâîâàíèå σ + è σ −ãàðàíòèðóåòñÿ Ëåììàìè 2.1 è 2.2. Ñ ïîìîùüþ ýòèõ âåëè÷èí ìîæíî ïîñòðîèòü ñóáîïòèìàëüíîå óïðàâëåíèå ñëåäóþùèì îáðàçîì: Ti () åñòü íà÷àëüíîå âðåìÿ ðàáîòû âåðøèíû i; äàëåå, êàæäàÿ âûõîäÿùàÿ äóãà (i, j)+æäåò åùå σij() è íà÷èíàåò ïåðåäàâàòü ïîòîê, ïðè ýòîì ìîæíî ãàðàí-òèðîâàòü ïîñòîÿííûé îòòîê ïîòîêà (ñ êîýôôèöèåíòîì avg(cij )(1 − ))−ïî ýòîé äóãå ñ çàäåðæêîé σij() íà ñòîðîíå j ; i ïåðåñûëàåò ïîòîê äî òåõïîð, ïîêà ñóììàðíûé îáúåì ïåðåäàííîãî ïîòîêà íå ñòàíîâèòñÿ òàêèì æå,êàê è â óñðåäíåííîì ñëó÷àå.
Áîëåå ôîðìàëüíî, óïðàâëåíèå îïèñûâàåòñÿ50ñëåäóþùèì îáðàçîì(2.3)Ti () + σij+ (), 0, Rt <t0, Ti ()+σ+ () uij dµ = τ̃ u∗ij ,uij (t, ) =iju∗ij1â îñòàëüíûõ ñëó÷àÿõ.τi ()(1+) avg(cij ) cij (t)Íàçîâåì èíòåðâàë âðåìåíè, ñîîòâåòñòâóþùèé òðåòüåìó ïðàâèëó â ýòîìîïðåäåëåíèè, àêòèâíîé ñòàäèåé äóãè. Âòîðîå ïðàâèëî ñëåäóåò âîñïðèíèìàòü ñëåäóþùèì îáðàçîì: åñëè ñóììàðíîå îáúåì ïîòîêà, êîòîðûé áûëïåðåäàí ïî äóãå, äîñòèã óðîâíÿ τ̃ u∗ij , òî ñëåäóåò îñòàíîâèòüñÿ è áîëüøåíå ïåðåäàâàòü ïîòîê (ñ ôîðìàëüíîé òî÷êè çðåíèÿ ýòî âîçìîæíî, òàê êàêôóíêöèÿRτcij dµ íåïðåðûâíà ïî τ ). Òàê êàê óïðàâëåíèå, ñîîòâåòñòâóþùåå àêòèâíîé ñòàäèè, åñòü ïðîïóñêíàÿ ñïîñîáíîñòü ñ êîýôôèöèåíòîììåíüøèì åäèíèöû, òî òàêîå óïðàâëåíèå íå íàðóøàåò îãðàíè÷åíèÿ ïðîïóñêíûõ ñïîñîáíîñòåé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
