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

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

परिचय

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

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

पंक्तिबद्ध नेटवर्क के लिए ल्यपुनोव ड्रिफ्ट

एक पंक्तिबद्ध नेटवर्क पर विचार करें जो सामान्यीकृत समय स्लॉट $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\}$

जहां स्लॉट $t$ पर पंक्ति $i$ में $a_{i}(t)$ और $b_{i}(t)$ क्रमशः आगमन और सेवा के अवसर हैं। इस समीकरण का उपयोग किसी भी स्लॉट 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)$ को स्लॉट t पर नेटवर्क द्वारा खर्च की गई कुल विद्युत के रूप में परिभाषित किया जा सकता है। कुछ वांछनीय पुरस्कार $r(t),$ के औसत समय को अधिकतम करने की समस्याओं का समाधान करने के लिए, पेनल्टी को $p(t)=-r(t)$परिभाषित किया जा सकता है। यह स्थिरता के अधीन संपूर्ण उपयोगिता में नेटवर्क को अधिकतम करने के लिए उपयोगी है।

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

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

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

प्रमेय (ल्यपुनोव अनुकूलन)- मान लीजिए कि स्थिरांक $\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।

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