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

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

परिचय

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

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

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

पंक्तिबद्ध नेटवर्क पर विचार करें जो सामान्यीकृत समय स्लॉट के साथ अलग-अलग समय में विकसित होता है $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।

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