🔢 mathematics

Joint Service Placement and Resource Optimization in Hierarchical Edge-Cloud Networks

यह शोध पत्र पदानुक्रमित एज-क्लाउड IoT नेटवर्क के लिए एक संयुक्त अनुकूलन ढांचे का प्रस्ताव करता है जो एंड-टू-एंड विलंबता और सिस्टम लागत को कम करने के लिए सर्विस प्लेसमेंट, एज-क्लाउड सहयोग, टास्क ऑफलोडिंग और बैंडविड्थ आवंटन को एक साथ संबोधित करता है, जिसमें परिणामी गैर-उत्तल मिश्रित-पूर्णांक गैर-रैखिक प्रोग्रामिंग समस्या को हल करने के लिए रिलैक्सेशन और सक्सीविव कॉनवेक्स एप्रोक्सिमेशन तकनीकों का उपयोग किया गया है।

मूल लेखक: Vo Phi Son, Van-Dinh Nguyen, Minh-Tuong Nguyen, Tuan-Vu Truong, Toan D. Gian, Dinh Thai Hoang, Diep N. Nguyen, Symeon Chatzinotas

प्रकाशित 2026-05-26

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Vo Phi Son, Van-Dinh Nguyen, Minh-Tuong Nguyen, Tuan-Vu Truong, Toan D. Gian, Dinh Thai Hoang, Diep N. Nguyen, Symeon Chatzinotas

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

एक हलचल भरे शहर की कल्पना करें जहाँ लाखों लोग (IoT डिवाइस) अपने काम तुरंत निपटाना चाहते हैं—जैसे खाना ऑर्डर करना, गेम खेलना, या अपने स्वास्थ्य की निगरानी करना। इस शहर में दो प्रकार की रसोई (kitchens) हैं: स्थानीय पड़ोस के कैफे (एज सर्वर) और एक विशाल केंद्रीय औद्योगिक रसोई (क्लाउड)।

यह लेख इस बारे में है कि इस शहर के "रसोई नेटवर्क" को कैसे चलाया जाए ताकि हर किसी को उनका ऑर्डर तेजी से मिले, बिना सिस्टम के क्रैश हुए या शहर का पैसा खत्म हुए।

यहाँ समस्या और समाधान का विवरण, सरल उपमाओं (analogies) के साथ दिया गया है:

समस्या: एक अराजक रसोई

एक पदानुक्रमित (Hierarchical) एज-क्लाउड नेटवर्क में, चीजें बहुत जल्दी गड़बड़ा जाती हैं:

मेन्यू की समस्या (सर्विस प्लेसमेंट): स्थानीय कैफे के पास शेल्फ की सीमित जगह होती है। वे हर संभव व्यंजन (सर्विस) के लिए हर एक सामग्री (इंक्रीडिएंट) स्टॉक नहीं कर सकते। यदि किसी ग्राहक को ऐसा व्यंजन चाहिए जो कैफे के पास नहीं है, तो उन्हें केंद्रीय रसोई से सामग्री मंगवाने के लिए या पड़ोसी कैफे से पूछने के लिए इंतजार करना पड़ता है। यह तय करना कि शेल्फ पर कौन सी सामग्री रखनी है, बहुत कठिन काम है।
डिलीवरी की समस्या (टास्क ऑफलोडिंग): जब कोई ऑर्डर आता है, तो उसे कौन बनाता है? ग्राहक का अपना माइक्रोवेव (लोकल डिवाइस)? स्थानीय कैफे? पड़ोसी का कैफे? या बड़ी केंद्रीय रसोई? यदि सभी अपने ऑर्डर केंद्रीय रसोई को भेजते हैं, तो डिलीवरी ट्रक ट्रैफिक में फंस जाते हैं (लेटेंसी)। यदि वे सभी एक ही छोटे कैफे के पास जाते हैं, तो वह कैफे थक कर चूर हो जाएगा।
लागत की समस्या: कैफे चलाने, सामग्री स्टॉक करने और डिलीवरी ट्रक भुगतान करने में पैसा खर्च होता है। यदि आप मेन्यू को बहुत बार बदलते हैं (लगातार सेवाओं को इंस्टॉल और अनइंस्टॉल करना), तो सेटअप फीस में बहुत पैसा बर्बाद होता है।

लक्ष्य: लेखक यह पता लगाना चाहते हैं कि एक आदर्श संतुलन कैसे बनाया जाए जिससे दो चीजें एक साथ हो सकें:

गति (Speed): ग्राहक तक "खाना" जितनी जल्दी हो सके पहुँचाया जाए।
बचत (Savings): नेटवर्क चलाने की कुल लागत कम रहे।

समाधान: एक दो-चरणीय प्रबंधन योजना

लेखकों ने महसूस किया कि सब कुछ एक साथ हल करने की कोशिश करना ऐसा है जैसे एक ही समय में पूरे साल का मेन्यू प्लान करना और साथ ही एक भोजन बनाना। यह बहुत जटिल है। इसलिए, उन्होंने इसे दो अलग-अलग समय-सीमाओं (time scales) में विभाजित किया:

1. दीर्घकालिक योजना (द "मेन्यू स्ट्रैटेजी")

समय-सीमा: यह बहुत कम होता है (जैसे, दिन में या सप्ताह में एक बार)।
कार्य: सिस्टम यह तय करता है कि किन सेवाओं को किस सर्वर पर इंस्टॉल करना है।
उपमा: इसे एक कैफे मैनेजर के रूप में सोचें जो अगले सप्ताह के लिए शेल्फ पर कौन सी सामग्री रखनी है, इसका निर्णय लेता है। वे पड़ोस की आदतों को देखते हैं और तय करते हैं, "हमें यहाँ पिज्जा ओवन रखने की जरूरत है, लेकिन हमें सुशी स्टेशन की जरूरत नहीं है।" वे यह भी तय करते हैं कि किन कैफे को एक-दूसरे की मदद करनी चाहिए (एज-टू-एज सहयोग) और किन्हें बड़ी रसोई पर निर्भर रहना चाहिए (एज-टू-क्लाउड सहयोग)।
क्यों? यह सुनिश्चित करता है कि नेटवर्क स्थिर रहे। आप नहीं चाहेंगे कि हर बार जब कोई ग्राहक आए, तो पूरा मेन्यू बदल दिया जाए।

2. अल्पकालिक योजना (द "ऑर्डर टेकर")

समय-सीमा: यह लगातार होता है (हर कुछ सेकंड में)।
कार्य: एक बार मेन्यू सेट हो जाने के बाद, सिस्टम यह तय करता है कि वर्तमान ऑर्डर्स को कैसे संभालना है।
उपमा: एक ग्राहक आता है। मैनेजर वर्तमान ट्रैफिक, डिलीवरी ट्रकों की गति और स्टाफ की ऊर्जा को देखता है। वे तय करते हैं: "ठीक है, चूंकि पिज्जा ओवन व्यस्त है, तो चलिए यह विशिष्ट ऑर्डर पड़ोसी कैफे को भेज देते हैं," या "आइए इस ऑर्डर को विभाजित करें: आटा यहाँ पकाएं, और सॉस क्लाउड से मंगवाएं।" वे यह भी तय करते हैं कि प्रत्येक ग्राहक को कितनी बैंडविड्थ (डिलीवरी ट्रक स्पेस) दी जाए।
क्यों? यह वास्तविक समय की अराजकता, जैसे ग्राहकों की अचानक भीड़ या सड़क पर ट्रैफिक जाम के अनुकूल ढल जाता है।

उन्होंने गणित को कैसे हल किया

इसके पीछे का गणित अविश्वसनीय रूप से कठिन है (जिसे "नॉन-कॉन्वेक्स मिक्स्ड-इंटिजर नॉनलीनियर प्रोग्रामिंग" के रूप में वर्णित किया गया है)। सरल शब्दों में, यह एक पहेली है जहाँ आपको "हाँ/नहीं" विकल्पों (इस सेवा को इंस्टॉल करें या नहीं?) और "कितना" विकल्पों (कितनी बैंडविड्थ?) के बीच एक साथ चुनाव करना होता है, और नियम बदलते रहते हैं।

इसे हल करने के लिए, लेखकों ने सक्सेसिव कॉनवेक्स एप्रोक्सिमेशन (SCA) नामक एक चतुर ट्रिक का उपयोग किया:

उपमा: कल्पना करें कि आप अंधेरे में एक खड़ी, ऊबड़-खाबड़ पहाड़ी राह पर चलने की कोशिश कर रहे हैं। यह खतरनाक है और नीचे उतरना कठिन है।
ट्रिक: पूरी ऊबड़-खाबड़ राह देखने के बजाय, वे मान लेते हैं कि रास्ता कुछ कदमों के लिए एक चिकना, हल्का ढलान है। वे उस चिकने ढलान पर नीचे उतरते हैं, फिर रुकते हैं, वास्तविक राह को फिर से देखते हैं, और मान लेते हैं कि यह एक नया चिकना ढलान है। वे इस प्रक्रिया को दोहराते हैं, छोटे, सुरक्षित कदम उठाते हैं जब तक कि वे नीचे (इष्टतम समाधान) तक न पहुँच जाएँ।
दंड (Penalty): उन्होंने एक "पेनल्टी" सिस्टम भी जोड़ा। यदि गणित सुझाव देता है कि कोई अजीब "आधा-इंस्टॉल" किया गया सर्विस (जैसे 0.5 पिज्जा ओवन) है, तो सिस्टम एक भारी जुर्माना लगाता है ताकि निर्णय एक स्पष्ट "हाँ" (1) या "नहीं" (0) बन जाए।

परिणाम: यह बेहतर क्यों काम करता है

लेखकों ने अपने तरीके का परीक्षण अन्य सामान्य रणनीतियों (जैसे ग्राहकों को रैंडमली कैफे में असाइन करना या हमेशा क्लाउड को सब कुछ भेजना) के मुकाबले किया।

गति: उनके तरीके ने परिणाम मिलने में लगने वाले समय (लेटेंसी) को काफी कम कर दिया। यह केवल क्लाउड को सब कुछ भेजने या रैंडम असाइनमेंट की तुलना में बहुत तेज़ था।
लागत: इसने अनावश्यक सर्विस इंस्टॉलेशन से बचकर और महंगे क्लाउड डेटा ट्रांसफर की आवश्यकता को कम करके पैसे बचाए।
स्थिरता: दीर्घकालिक "मेन्यू" निर्णयों को अल्पकालिक "ऑर्डर" निर्णयों से अलग करके, सिस्टम निरंतर बदलावों से अभिभूत नहीं हुआ।

सारांश

यह पेपर IoT नेटवर्क के लिए एक स्मार्ट, दो-स्तरीय प्रबंधन प्रणाली प्रस्तुत करता है। यह रणनीतिक निर्णयों (कौन सी सेवाएं कहाँ रखी जाएं) को सामरिक निर्णयों (अभी डेटा को कैसे रूट किया जाए) से अलग करता है। एक जटिल भूलभुलैया के माध्यम से सबसे अच्छे रास्ते का अनुमान लगाने के लिए उन्नत गणित का उपयोग करके, लेखकों ने एक ऐसा सिस्टम बनाया है जो पिछले तरीकों की तुलना में तेज़, सस्ता और अधिक विश्वसनीय है, जिससे यह सुनिश्चित होता है कि हमारे जुड़े हुए उपकरणों को कम-लेटेंसी वाली सेवाएं मिलें बिना बजट बिगाड़े।

तकनीकी सारांश: पदानुक्रमित एज-क्लाउड नेटवर्क में संयुक्त सेवा प्लेसमेंट और संसाधन अनुकूलन

समस्या विवरण
पदानुक्रमित एज-क्लाउड कंप्यूटिंग (HECC) आधारित इंटरनेट ऑफ थिंग्स (IoT) नेटवर्क कम-विलंबता (low-latency) आवश्यकताओं और सिस्टम लागत के बीच संतुलन बनाने में महत्वपूर्ण चुनौतियों का सामना करते हैं। मुख्य कठिनाई सेवा प्लेसमेंट (सेवाओं को कहाँ तैनात किया जाए), उपयोगकर्ता जुड़ाव (user association), एज-एज और एज-क्लाउड सहयोग, कार्य ऑफलोडिंग रणनीतियों और बैंडविड्थ आवंटन के संयुक्त अनुकूलन में निहित है। ये निर्णय विषम कम्प्यूटेशनल संसाधनों, एज सर्वरों (ESs) पर सीमित भंडारण, गतिशील उपयोगकर्ता गतिशीलता और अस्थिर वायरलेस चैनल स्थितियों के कारण जटिल हो जाते हैं।

इस समस्या को एक गैर-उत्तल (non-convex) मिश्रित-पूर्णांक गैररेखीय प्रोग्रामिंग (MINLP) समस्या के रूप में तैयार किया गया है। इसका उद्देश्य समग्र एंड-टू-एंड (e2e) विलंबता और कुल सिस्टम मौद्रिक लागत (जिसमें सेवा इंस्टॉलेशन, अनइंस्टॉलेशन, संचालन और क्लाउड अनुरोध शुल्क शामिल हैं) के भारित योग (weighted sum) को न्यूनतम करना है। बाइनरी निर्णय चरों (सेवा प्लेसमेंट, ऑफलोडिंग पथ) और निरंतर चरों (बैंडविड्थ आवंटन, टास्क विभाजन) के बीच मजबूत जुड़ाव के कारण यह समस्या NP-hard की श्रेणी में आती है, जिससे एक व्यवहार्य समाधान खोजना भी कठिन हो जाता है।

कार्यप्रणाली
MINLP फॉर्मूलेशन की जटिलता को संबोधित करने के लिए, लेखक एक पदानुक्रमित अनुकूलन ढांचे का प्रस्ताव करते हैं जो समस्या को दो उप-समस्याओं में विभाजित करता है जो अलग-अलग समय-पैमानों (timescales) पर कार्य करती हैं:

दीर्घकालिक अनुकूलन (सेवा प्लेसमेंट और सहयोग): दीर्घकालिक समय स्लॉट के दौरान निष्पादित, यह उप-समस्या सेवा प्लेसमेंट ( $g_s^k$ ), उपयोगकर्ता जुड़ाव ( $\sigma_{m,s}^k$ ), और एज-एज/एज-क्लाउड सहयोग पथों से संबंधित बाइनरी निर्णयों को अनुकूलित करती है। बाइनरी बाधाओं को संभालने के लिए, लेखक एक सक्सेसिव कॉनवेक्स एप्रोक्सिमेशन (SCA) विधि का उपयोग करते हैं जो एक पेनल्टी फंक्शन के साथ मिलकर काम करती है। बाइनरी चरों को $[0, 1]$ में निरंतर मानों के रूप में शिथिल (relax) किया जाता है, और बाइनरी मानों (0 या 1) की ओर अभिसरण (convergence) सुनिश्चित करने के लिए ऑब्जेक्टिव फंक्शन में एक पेनल्टी टर्म जोड़ा जाता है। गैर-उत्तल पेनल्टी फंक्शन को पुनरावृत्ति (iteratively) के माध्यम से एक उत्तल सरोगेट (convex surrogate) द्वारा अनुमानित किया जाता है।
अल्पकालिक अनुकूलन (टास्क ऑफलोडिंग और संसाधन आवंटन): दीर्घकालिक फ्रेम के भीतर अल्पकालिक समय स्लॉट में निष्पादित, यह उप-समस्या निरंतर चरों को अनुकूलित करती है: स्थानीय रूप से संसाधित कार्यों का हिस्सा बनाम ऑफलोडेड हिस्सा ( $\phi$ ) और बैंडविड्थ आवंटन ( $b$ )। दीर्घकालिक चरण में निर्धारित बाइनरी चरों को स्थिर मापदंडों के रूप में माना जाता है। विलंबता, ऊर्जा और डेटा दरों से संबंधित गैर-उत्तल बाधाओं को SCA तकनीकों का उपयोग करके उत्तल बनाया जाता है, विशेष रूप से दर और ऊर्जा कार्यों के लिए निचले-स्तर के अवतल अनुमानों (lower-bound concave approximations) का निर्माण करके।

समग्र एल्गोरिदम (एल्गोरिदम 1) इन दोनों समय-पैमानों के बीच पुनरावृत्ति करता है। यदि अल्पकालिक अनुकूलन विलंबता आवश्यकताओं को पूरा करने में विफल रहता है या नए सेवा अनुरोध आते हैं, तो सिस्टम दीर्घकालिक कॉन्फ़िगरेशन के पुन: अनुकूलन को ट्रिगर करता है।

प्रमुख योगदान

एकीकृत अनुकूलन ढांचा: यह शोध पत्र एक व्यापक ढांचे को प्रस्तुत करता है जो सेवा प्लेसमेंट, उपयोगकर्ता जुड़ाव, एज-एज/एज-क्लाउड सहयोग, टास्क ऑफलोडिंग और बैंडविड्थ आवंटन को संयुक्त रूप से अनुकूलित करता है। पूर्ववर्ती कार्यों के विपरीत, जो अक्सर पूर्व-स्थापित सेवाओं को मानते हैं या एकल-समयSCALE अनुकूलन पर ध्यान केंद्रित करते हैं, यह दृष्टिकोण दीर्घकालिक स्थिरता के साथ अल्पकालिक अनुकूलन क्षमता को एकीकृत करता है।
नवीन समस्या रूपांतरण: लेखक सेवा उपलब्धता, कनेक्टिविटी और टास्क ट्रांसफर स्थितियों के बीच जटिल जुड़ाव को सरल बनाने के लिए तीन लेम्मा (lemmas) पेश करते हैं। ये लेम्मा मूल गैर-उत्तल MINLP को अधिक सुलभ रूप में पुनर्गठित करने की अनुमति देते हैं।
कुशल पुनरावृत्ति एल्गोरिदम: SCA और पेनल्टी-आधारित तकनीकों को मिलाकर, यह शोध पत्र ऐसे एल्गोरिदम (दीर्घकालिक के लिए एल्गोरिदम 2 और अल्पकालिक के लिए एल्गोरिदम 3) विकसित करता है जो कम से कम एक स्थानीय इष्टतम (local optimum) तक अभिसरण की गारंटी देते हैं। जटिलता का विश्लेषण किया गया है, जो प्रति पुनरावृत्ति बहुपद समय जटिलता (polynomial time complexity) दर्शाता है।
लागत-जागरूक मॉडलिंग: ऑब्जेक्टिव फंक्शन विलंबता न्यूनीकरण के साथ-साथ सेवा परिनियोजन (इंस्टॉलेशन/अनइंस्टॉलेशन) और परिचालन व्यय के लिए मौद्रिक लागत को स्पष्ट रूप से शामिल करता है, जो एक अधिक वास्तविक सिस्टम लागत मीट्रिक प्रदान करता है।

संख्यात्मक परिणाम
प्रस्तावित ढांचे का मूल्यांकन करने के लिए कई बेंचमार्क स्कीमों के विरुद्ध व्यापक सिमुलेशन किए गए, जिनमें ब्रांच-एंड-बाउंड (BnB), फिक्स्ड/रैंडम यूजर एसोसिएशन, बिना एज-एज या एज-क्लाउड सहयोग वाले स्कीम्स, और फिक्स्ड ऑफलोडिंग रेट्स शामिल हैं।

अभिसरण (Convergence): प्रस्तावित एल्गोरिदम तीव्र अभिसरण प्रदर्शित करते हैं। एल्गोरिदम 2 (दीर्घकालिक) आमतौर पर 4-5 पुनरावृत्तियों के भीतर अभिसरित होता है, जबकि एल्गोरिदम 3 (अल्पकालिक) नेटवर्क के आकार में वृद्धि के बावजूद स्थिर अभिसरण दिखाता है।
बेंचमार्क के विरुद्ध प्रदर्शन: प्रस्तावित दृष्टिकोण इष्टतम BnB समाधान के 1-2% के भीतर प्रदर्शन प्राप्त करता है, लेकिन काफी कम कम्प्यूटेशनल जटिलता के साथ।
सहयोग का प्रभाव: परिणाम दर्शाते हैं कि एज-एज या एज-क्लाउड सहयोग को अक्षम करने से सिस्टम लागत में 200-250% की वृद्धि होती है और एंड-टू-एंड विलंबता काफी बढ़ जाती है।
संयुक्त अनुकूलन के लाभ: वे स्कीम्स जो ऑफलोडिंग दरों को स्थिर रखते हैं या समान बैंडविड्थ आवंटित करते हैं, उप-इष्टतम (sub-optimal) प्रदर्शन करते हैं। ऑफलोडिंग और बैंडविड्थ आवंटन का प्रस्तावित संयुक्त अनुकूलन लगातार सबसे कम e2e विलंबता प्रदान करता है।
संसाधन संवेदनशीलता: एज सर्वरों की प्रोसेसिंग दर बढ़ाने से अधिक स्थानीय प्रसंस्करण सक्षम होने के कारण विलंबता और सिस्टम लागत कम हो जाती है, हालांकि प्रस्तावित ढांचा फिक्स्ड एसोसिएशन स्कीमों की तुलना में परिवर्तनशील उपयोगकर्ता लोड के तहत भी स्थिर लागत बनाए रखता है।

महत्व और दावे
यह शोध पत्र दावा करता है कि इसका प्राथमिक महत्व HECC-सहायता प्राप्त IoT नेटवर्क में सिस्टम प्रदर्शन और दक्षता को बढ़ाने के लिए संयुक्त सेवा प्लेसमेंट और संसाधन आवंटन की आवश्यकता को प्रदर्शित करने में निहित है। यह तर्क देता है कि इन घटकों को अलग-अलग अनुकूलित करना या दीर्घकालिक सेवा कॉन्फ़िगरेशन और अल्पकालिक संसाधन गतिशीलता के बीच के अंतर्संबंध को अनदेखा करना उप-इष्टतम QoS और बढ़ी हुई लागतों की ओर ले जाता है।

लेखक इस बात पर जोर देते हैं कि उनका पदानुक्रमित दृष्टिकोण सिस्टम स्थिरता और वास्तविक समय की मांगों के प्रति अनुकूलन क्षमता के बीच प्रभावी ढंग से संतुलन बनाता है, जो मौजूदा दो-समयSCALE दृष्टिकोणों की सीमाओं को संबोधित करता है जो अक्सर विरल (infrequent) सेवा प्लेसमेंट अपडेट को मानते हैं। परिणाम बताते हैं कि प्रस्तावित ढांचा गतिशील, संसाधन-बाधित IoT वातावरण के लिए एक स्केलेबल और लागत प्रभावी समाधान है, जो जटिल अनुकूलतम सॉल्वर जैसे BnB के मुकाबले एक मजबूत विकल्प प्रदान करता है और हीयुरिस्टिक या स्टेटिक बेंचमार्क स्कीमों से बेहतर प्रदर्शन करता है।