ल्यपुनोव अनुकूलन

यह आलेख गतिशील प्रणालियों के लिए ल्यपुनोव अनुकूलन का वर्णन करता है। यह Queueing_theory#Queueing_networks में इष्टतम नियंत्रण के लिए एक उदाहरण अनुप्रयोग देता है।

परिचय

ल्यपुनोव अनुकूलन एक गतिशील प्रणाली को बेहतर ढंग से नियंत्रित करने के लिए ल्यपुनोव समारोह के उपयोग को संदर्भित करता है। सिस्टम स्थिरता के विभिन्न रूपों को सुनिश्चित करने के लिए ल्यपुनोव फ़ंक्शंस का नियंत्रण सिद्धांत में बड़े पैमाने पर उपयोग किया जाता है। किसी विशेष समय में किसी प्रणाली की स्थिति का वर्णन अक्सर बहुआयामी वेक्टर द्वारा किया जाता है। ल्यपुनोव फ़ंक्शन इस बहु-आयामी स्थिति का एक गैर-नकारात्मक अदिश माप है। आमतौर पर, जब सिस्टम अवांछनीय स्थितियों की ओर बढ़ता है तो फ़ंक्शन को बड़े होने के लिए परिभाषित किया जाता है। नियंत्रण क्रियाएं करके सिस्टम स्थिरता प्राप्त की जाती है जो ल्यपुनोव फ़ंक्शन को नकारात्मक दिशा में शून्य की ओर ले जाती है।

कतारबद्ध नेटवर्क में इष्टतम नियंत्रण के अध्ययन के लिए ल्यपुनोव बहाव केंद्रीय है। एक विशिष्ट लक्ष्य कुछ प्रदर्शन उद्देश्यों को अनुकूलित करते हुए सभी नेटवर्क कतारों को स्थिर करना है, जैसे औसत ऊर्जा को कम करना या औसत थ्रूपुट को अधिकतम करना। द्विघात ल्यपुनोव फ़ंक्शन के बहाव को कम करने से होता है नेटवर्क स्थिरता के लिए बैकप्रेशर रूटिंग एल्गोरिदम, जिसे मैक्स-वेट एल्गोरिदम भी कहा जाता है। लायपुनोव ड्रिफ्ट में एक भारित दंड शब्द जोड़ने और राशि को कम करने से संयुक्त नेटवर्क स्थिरता और दंड न्यूनतमकरण के लिए बहाव प्लस जुर्माना |ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम बनता है। ड्रिफ्ट-प्लस-पेनल्टी प्रक्रिया का उपयोग उत्तल अनुकूलन और रैखिक प्रोग्रामिंग के समाधान की गणना करने के लिए भी किया जा सकता है।

कतारबद्ध नेटवर्क के लिए ल्यपुनोव बहाव

एक कतारबद्ध नेटवर्क पर विचार करें जो सामान्यीकृत समय स्लॉट के साथ अलग-अलग समय में विकसित होता है $t\in \{0,1,2,\ldots \}.$ मान लीजिए कि वहाँ हैं $N$ नेटवर्क में कतारें, और समय पर कतार बैकलॉग के वेक्टर को परिभाषित करें $t$ द्वारा:

$Q(t)=(Q_{1}(t),\ldots ,Q_{N}(t))$

द्विघात ल्यपुनोव फ़ंक्शन

प्रत्येक स्लॉट के लिए $t,$ परिभाषित करना:

$L(t)={\frac {1}{2}}\sum _{i=1}^{N}Q_{i}(t)^{2}$

यह फ़ंक्शन नेटवर्क में कुल कतार बैकलॉग का एक अदिश माप है। इसे कतार स्थिति पर द्विघात ल्यपुनोव फ़ंक्शन कहा जाता है। ल्यपुनोव बहाव को इस फ़ंक्शन में एक स्लॉट से दूसरे स्लॉट में परिवर्तन के रूप में परिभाषित करें:

$\Delta L(t)=L(t+1)-L(t)$

लायपुनोव बहाव को बांधना

मान लीजिए कि कतार बैकलॉग निम्नलिखित समीकरण के अनुसार समय के साथ बदलते हैं:

$Q_{i}(t+1)=\max \left\{Q_{i}(t)+a_{i}(t)-b_{i}(t),0\right\}$

कहाँ $a_{i}(t)$ और $b_{i}(t)$ कतार में क्रमशः आगमन और सेवा के अवसर हैं $i$ स्लॉट पर $t.$ इस समीकरण का उपयोग किसी भी स्लॉट टी के लिए ल्यपुनोव बहाव पर एक सीमा की गणना करने के लिए किया जा सकता है:

$Q_{i}(t+1)^{2}=\left(\max \left\{Q_{i}(t)+a_{i}(t)-b_{i}(t),0\right\}\right)^{2}\leqslant \left(Q_{i}(t)+a_{i}(t)-b_{i}(t)\right)^{2}$

इस असमानता को पुनर्व्यवस्थित करते हुए, सभी को संक्षेप में प्रस्तुत करें $i,$ और 2 से विभाजित करने पर प्राप्त होता है:

$\Delta L(t)\leqslant B(t)+\sum _{i=1}^{N}Q_{i}(t)(a_{i}(t)-b_{i}(t))\qquad (Eq.1)$

कहाँ:

$B(t)={\frac {1}{2}}\sum _{i=1}^{N}\left(a_{i}(t)-b_{i}(t)\right)^{2}$

मान लीजिए कि प्रत्येक कतार में आगमन और सेवा के दूसरे क्षण सीमित हैं, ताकि एक सीमित स्थिरांक हो $B>0$ ऐसा कि सभी के लिए $t$ और सभी संभावित कतार वैक्टर $Q(t)$ निम्नलिखित संपत्ति रखती है:

$\mathbb {E} [B(t)|Q(t)]\leqslant B$

(समीकरण 1) की सशर्त अपेक्षाओं को लेने से सशर्त अपेक्षित ल्यपुनोव बहाव पर निम्नलिखित सीमाएँ उत्पन्न होती हैं:

$\mathbb {E} [\Delta L(t)|Q(t)]\leqslant B+\sum _{i=1}^{N}Q_{i}(t)\mathbb {E} [a_{i}(t)-b_{i}(t)|Q(t)]\qquad (Eq.2)$

एक बुनियादी लायपुनोव बहाव प्रमेय

कई मामलों में, नेटवर्क को नियंत्रित किया जा सकता है ताकि प्रत्येक कतार में आगमन और सेवा के बीच का अंतर कुछ वास्तविक संख्या के लिए निम्नलिखित संपत्ति को संतुष्ट कर सके $\varepsilon >0$:

$\mathbb {E} [a_{i}(t)-b_{i}(t)|Q(t)]\leqslant -\varepsilon$

यदि उपरोक्त सभी कतारों के लिए समान ईपीएसलॉन को लागू करता है $i,$ सभी स्लॉट $t,$ और सभी संभावित वैक्टर $Q(t),$ तब (समीकरण 2) निम्नलिखित ल्यपुनोव बहाव प्रमेय में प्रयुक्त बहाव की स्थिति को कम कर देता है। नीचे दिए गए प्रमेय को मार्कोव श्रृंखलाओं के लिए फोस्टर के प्रमेय पर भिन्नता के रूप में देखा जा सकता है। हालाँकि, इसके लिए मार्कोव श्रृंखला संरचना की आवश्यकता नहीं है।

प्रमेय (ल्यपुनोव बहाव)। मान लीजिए कि स्थिरांक हैं $B\geqslant 0,\varepsilon >0$ ऐसा कि सभी के लिए $t$ और सभी संभावित वैक्टर $Q(t)$ सशर्त ल्यपुनोव बहाव संतुष्ट करता है:

$\mathbb {E} [\Delta L(t)|Q(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}Q_{i}(t).$

फिर सभी स्लॉट के लिए $t>0$ नेटवर्क में समय का औसत कतार आकार संतुष्ट करता है:

${\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\leqslant {\frac {B}{\varepsilon }}+{\frac {\mathbb {E} [L(0)]}{\varepsilon t}}.$

सबूत। बहाव असमानता के दोनों पक्षों की अपेक्षाओं को ध्यान में रखते हुए और पुनरावृत्त अपेक्षाओं के नियम का उपयोग करने से परिणाम मिलता है:

$\mathbb {E} [\Delta L(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i}(t)]$

उपरोक्त अभिव्यक्ति को संक्षेप में प्रस्तुत करें $\tau \in \{0,1,\ldots ,t-1\}$ और टेलीस्कोपिंग योग के नियम का उपयोग करने से प्राप्त होता है:

$\mathbb {E} [L(t)]-\mathbb {E} [L(0)]\leqslant Bt-\varepsilon \sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]$

इस तथ्य का उपयोग करते हुए $L(t)$ गैर-नकारात्मक है और उपरोक्त अभिव्यक्ति में शब्दों को पुनर्व्यवस्थित करने से परिणाम सिद्ध होता है।

कतारबद्ध नेटवर्क के लिए ल्यपुनोव अनुकूलन

उपरोक्त अनुभाग के समान कतारबद्ध नेटवर्क पर विचार करें। अब परिभाषित करें $p(t)$ स्लॉट पर लगने वाले नेटवर्क जुर्माने के रूप में $t.$ मान लीजिए कि लक्ष्य समय के औसत को कम करते हुए कतारबद्ध नेटवर्क को स्थिर करना है $p(t).$ उदाहरण के लिए, समय की औसत शक्ति को कम करते हुए नेटवर्क को स्थिर करने के लिए, $p(t)$ इसे स्लॉट टी पर नेटवर्क द्वारा खर्च की गई कुल बिजली के रूप में परिभाषित किया जा सकता है। कुछ वांछनीय पुरस्कार के समय औसत को अधिकतम करने की समस्याओं का इलाज करना $r(t),$ दंड परिभाषित किया जा सकता है $p(t)=-r(t).$ यह स्थिरता के अधीन संपूर्ण उपयोगिता में नेटवर्क को अधिकतम करने के लिए उपयोगी है।

जुर्माने के औसत समय को कम करते हुए नेटवर्क को स्थिर करना $p(t),$ नेटवर्क एल्गोरिदम को नियंत्रण क्रियाएं करने के लिए डिज़ाइन किया जा सकता है जो निम्नलिखित ड्रिफ्ट प्लस पेनल्टी | ड्रिफ्ट-प्लस-पेनल्टी अभिव्यक्ति पर प्रत्येक स्लॉट पर एक सीमा को लालच से कम कर देता है $t$:

$\Delta L(t)+Vp(t)$

कहाँ $V$ एक गैर-नकारात्मक भार है जिसे प्रदर्शन ट्रेडऑफ़ को प्रभावित करने के लिए इच्छानुसार चुना जाता है। इस दृष्टिकोण की एक प्रमुख विशेषता यह है कि इसमें आमतौर पर यादृच्छिक नेटवर्क घटनाओं (जैसे यादृच्छिक नौकरी आगमन या चैनल प्राप्ति) की संभावनाओं के ज्ञान की आवश्यकता नहीं होती है। का चयन $V=0$ प्रत्येक स्लॉट में ड्रिफ्ट पर एक बाउंड को कम करने के लिए और मल्टी-हॉप कतार नेटवर्क में रूटिंग के लिए, टैसीयुलास और एफ़्रेमाइड्स द्वारा विकसित बैकप्रेशर रूटिंग एल्गोरिदम को कम करने के लिए।का उपयोग करते हुए $V>0$ और परिभाषित करना $p(t)$ स्लॉट पर नेटवर्क पावर का उपयोग के रूप में $t$ नीली द्वारा विकसित नेटवर्क स्थिरता के अधीन औसत शक्ति को कम करने के लिए ड्रिफ्ट प्लस पेनल्टी | ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम की ओर जाता है।का उपयोग करते हुए $V>0$ और उपयोग कर रहे हैं $p(t)$ प्रवेश नियंत्रण उपयोगिता मीट्रिक के नकारात्मक होने के कारण नीली, मोदियानो और ली द्वारा विकसित संयुक्त प्रवाह नियंत्रण और नेटवर्क रूटिंग के लिए ड्रिफ्ट-प्लस-पेनल्टी एल्गोरिदम होता है।

इस संदर्भ में पिछले खंड के ल्यपुनोव बहाव प्रमेय का सामान्यीकरण महत्वपूर्ण है। व्याख्या की सरलता के लिए, मान लीजिए $p(t)$ नीचे से घिरा हुआ है:

$p(t)\geqslant p_{\min }\quad \forall t\in \{0,1,2,...\}$

उदाहरण के लिए, उपरोक्त से संतुष्ट हैं $p_{\min }=0$ ऐसे मामलों में जब जुर्माना $p(t)$ सदैव गैर-नकारात्मक होता है। होने देना $p^{*}$ के समय औसत के लिए वांछित लक्ष्य का प्रतिनिधित्व करें $p(t).$ होने देना $V$ लक्ष्य को पूरा करने के महत्व को महत्व देने के लिए उपयोग किया जाने वाला एक पैरामीटर बनें। निम्नलिखित प्रमेय से पता चलता है कि यदि ड्रिफ्ट-प्लस-पेनल्टी की स्थिति पूरी हो जाती है, तो समय औसत जुर्माना वांछित लक्ष्य से अधिकतम O(1/V) ऊपर होता है, जबकि औसत कतार का आकार O(V) होता है। $V$ h> पैरामीटर को संबंधित कतार आकार ट्रेडऑफ़ के साथ वांछित लक्ष्य के करीब (या नीचे) समय औसत जुर्माना बनाने के लिए ट्यून किया जा सकता है।

प्रमेय (ल्यपुनोव अनुकूलन)। मान लीजिए कि स्थिरांक हैं $\varepsilon >0,V,B\geqslant 0,$ और $p^{*}$ ऐसा कि सभी के लिए $t$ और सभी संभावित वैक्टर $Q(t)$ निम्नलिखित ड्रिफ्ट-प्लस-पेनल्टी शर्त रखती है:

$\mathbb {E} [\Delta L(t)+Vp(t)|Q(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}Q_{i}(t)$

फिर सबके लिए $t>0$ समय औसत जुर्माना और समय औसत कतार आकार संतुष्ट करते हैं:

${\frac {1}{t}}\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]\leqslant p^{*}+{\frac {B}{V}}+{\frac {\mathbb {E} [L(0)]}{Vt}}$

${\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\leqslant {\frac {B+V(p^{*}-p_{\min })}{\varepsilon }}+{\frac {\mathbb {E} [L(0)]}{\varepsilon t}}$

सबूत। प्रस्तुत बहाव-प्लस-दंड के दोनों पक्षों की अपेक्षाओं को लेते हुए और हमारे पास पुनरावृत्त अपेक्षाओं के कानून का उपयोग करते हुए:

$\mathbb {E} [\Delta L(t)]+V\mathbb {E} [p(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i}(t)]$

उपरोक्त को पहले के ऊपर सारांशित करें $t$ स्लॉट और टेलीस्कोपिंग योग के नियम का उपयोग करने से मिलता है:

${\begin{aligned}\mathbb {E} [L(t)]-\mathbb {E} [L(0)]+V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant (B+Vp^{*})t-\varepsilon \sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\\-\mathbb {E} [L(0)]+V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant (B+Vp^{*})t&&{\text{Since }}L(t),Q_{i}(t)\geqslant 0\\V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant p^{*}Vt+Bt+\mathbb {E} [L(0)]\end{aligned}}$

द्वारा विभाजित करना $Vt$ और शर्तों को पुनर्व्यवस्थित करने से समयबद्ध औसत दंड सिद्ध होता है। एक समान तर्क समय औसत कतार आकार को बाध्य साबित करता है।

संबंधित लिंक

• बहाव प्लस जुर्माना
• बैकप्रेशर रूटिंग
• ल्यपुनोव समारोह
• फोस्टर का प्रमेय
• नियंत्रण-ल्यपुनोव फ़ंक्शन

प्राथमिक स्रोत

• एम। जे. नीली. संचार और कतारबद्ध प्रणालियों के अनुप्रयोग के साथ स्टोकेस्टिक नेटवर्क अनुकूलन, मॉर्गन और क्लेपूल, 2010।

श्रेणी:नेटवर्किंग एल्गोरिदम श्रेणी:कतारबद्ध सिद्धांत