⚡ electrical engineering

Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks

यह शोध पत्र लॉन्ग-होरिज़ॅन वायरलेस लिंक शेड्यूलिंग के लिए एक नवीन दृष्टिकोण प्रस्तावित करता है जो समय-परिवर्तनीय नीतियों को सीखने के लिए डायनेमिक डुअल वेरिएबल्स के साथ स्टेट-ऑगमेंटेड ग्राफ न्यूरल नेटवर्क्स का उपयोग करता है, जो बड़े पैमाने के नेटवर्क में प्रति-लिंक औसत दर बाधाओं को पूरा करते हुए सम-दरों (sum rates) को प्रभावी ढंग से अधिकतम करता है।

मूल लेखक: Romina Garcia Camargo, Zhiyang Wang, Navid NaderiAlizadeh, Alejandro Ribeiro

प्रकाशित 2026-07-22

📖 4 मिनट में पढ़ें☕ कॉफ़ी ब्रेक में पढ़ें

CC BY 4.0

मूल लेखक: Romina Garcia Camargo, Zhiyang Wang, Navid NaderiAlizadeh, Alejandro Ribeiro

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

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

लंबे समय तक, कंप्यूटरों ने इसे एक विशाल पहेली के रूप में देखकर हल करने का प्रयास किया है। वे उपकरणों को बिंदुओं (dots) के रूप में देखते हैं और उनके बीच के हस्तक्षेप (interference) को उन बिंदुओं को जोड़ने वाली रेखाओं के रूप में देखते हैं, जिससे एक "कॉन्फ्लिक्ट ग्राफ" (conflict graph) बनता है। लक्ष्य उन बिंदुओं के सबसे बड़े समूह को खोजना है जो आपस में जुड़े हुए नहीं हैं (ताकि वे सभी सुरक्षित रूप से बात कर सकें) और उन्हें बोलने देना है। हालाँकि, अधिकांश पुराने तरीकों ने केवल अगले सेकंड की ओर देखा। उन्होंने पूछा, "अभी कौन बोल सकता है?" और सबसे अच्छे समूह को चुन लिया। समस्या यह है कि यह अल्पदृष्टि वाला दृष्टिकोण अक्सर कुछ लोगों को हमेशा के लिए इंतजार करने के लिए छोड़ देता है जबकि अन्य लगातार बात करते रहते हैं। इसे ठीक करने के लिए, हमें एक ऐसी रणनीति की आवश्यकता है जो भविष्य में बहुत आगे तक देख सके, यह सुनिश्चित करते हुए कि एक लंबी अवधि में, हर किसी को हवा का उचित हिस्सा मिले और साथ ही नेटवर्क की कुल गति भी यथासंभव उच्च बनी रहे।

यह शोध पत्र एक ग्राफ न्यूरल नेटवर्क (GNN) नामक आर्टिफिशियल इंटेलिजेंस के प्रकार का उपयोग करके इस दीर्घकालिक पहेली को हल करने का एक चतुर नया तरीका पेश करता है। एक GNN को एक सुपर-स्मार्ट ट्रैफिक कंट्रोलर के रूप में समझें जो शहर (नेटवर्क) के आकार को समझता है और भविष्यवाणी कर सकता है कि यातायात कैसे प्रवाहित होगा। लेकिन यहाँ मोड़ यह है: लेखकों ने महसूस किया कि एक मानक ट्रैफिक कंट्रोलर बार-बार वही गलती करता है क्योंकि वह यह "याद" नहीं रखता कि कौन सबसे लंबे समय से इंतजार कर रहा है। इसे ठीक करने के लिए, उन्होंने एक "स्टेट-ऑगमेंटेड" (state-augmented) प्रणाली का आविष्कार किया। उन्होंने AI को एक जादुई नोटबुक दी जहाँ वह प्रत्येक उपकरण के लिए एक "पेनल्टी स्कोर" (penalty score) लिखता है जिसे अभी तक पर्याप्त एयरटाइम नहीं मिला है।

केवल मानचित्र को देखने के बजाय, अब AI मानचित्र और नोटबुक दोनों को देखता है। यदि कोई उपकरण लंबे समय से प्रतीक्षा कर रहा है, तो उसका पेनल्टी स्कोर बढ़ जाता है, और AI इसे प्राथमिकता देने के लिए सीखता है, भले ही वह उस सटीक सेकंड के लिए सबसे अच्छा विकल्प न हो। शोध पत्र दिखाता है कि इस AI को "डुअल ग्रेडिएंट डिसेंट" (dual gradient descent) नामक एक गणितीय प्रक्रिया की नकल करने के लिए प्रशिक्षित करके (जो एक हाइकर द्वारा ढलान को महसूस करके घाटी के सबसे निचले बिंदु को धीरे-धीरे खोजने जैसा है), यह प्रणाली एक ऐसा शेड्यूल तैयार कर सकती है जो एक लंबे क्षितिज (horizon) पर पूरी तरह से काम करता है। उनके कंप्यूटर सिमुलेशन में, इस पद्धति ने सफलतापूर्वक यह सुनिश्चित किया कि लगभग प्रत्येक उपकरण को उसका आवश्यक न्यूनतम बात करने का समय मिला, जबकि नेटवर्क की कुल गति भी बहुत उच्च बनी रही। यह एक कंडक्टर को केवल ताल बनाए रखने के लिए ही नहीं, बल्कि ऑर्केस्ट्रा के हर संगीतकार को सुनने के लिए सिखाने जैसा है ताकि यह सुनिश्चित हो सके कि शांत वाद्ययंत्रों को भी तब सोलो (solo) मिले जब उन्हें इसकी आवश्यकता हो, जिसके परिणामस्वरूप एक ऐसा सिम्फनी (symphony) तैयार होता है जो केवल सबसे तेज़ वाद्ययंत्रों के लिए ही नहीं, बल्कि सभी के लिए शानदार सुनाई देता है।

तकनीकी सारांश: स्टेट-ऑगमेंटेड ग्राफ न्यूरल नेटवर्क के साथ लॉन्ग-होरिज़ोन वायरलेस लिंक शेड्यूलिंग

समस्या का निरूपण (Problem Formulation)
यह शोध पत्र बड़े पैमाने के डिवाइस-टू-डिवाइस वायरलेस नेटवर्क में इष्टतम लिंक शेड्यूलिंग की समस्या को संबोधित करता है। इसका उद्देश्य समय क्षितिज (time horizon) $T$ पर दीर्घकालिक औसत कुल दर (long-term average sum rate) को अधिकतम करना है, जबकि यह सुनिश्चित करना है कि प्रत्येक लिंक $i$ एक न्यूनतम औसत दर आवश्यकता $\Delta_i$ को प्राप्त करे। पारंपरिक दृष्टिकोणों के विपरीत, जो तात्कालिक कुल दरों को अधिकतम करने पर ध्यान केंद्रित करते हैं, इस समस्या के लिए अस्थायी बाधाओं (temporal constraints) को पूरा करने और हस्तक्षेप (interference) से बचने के लिए समय-परिवर्तनीय नीतियों (time-varying policies) की आवश्यकता होती है।

नेटवर्क को एक प्राथमिक हस्तक्षेप मॉडल के तहत मॉडल किया गया है, जहाँ दो लिंक तब हस्तक्षेप करते हैं जब वे एक ही डिवाइस साझा करते हैं। इसे एक संघर्ष ग्राफ (conflict graph) $G(V, E)$ के रूप में दर्शाया गया है जिसका एडजेसेंसी मैट्रिक्स $A$ है। शेड्यूलिंग समस्या को एक निरंतर बाधा वाले कॉम्बिनेटरियल ऑप्टिमाइज़ेशन (constrained combinatorial optimization) के रूप में तैयार किया गया है (समीकरण 3), जहाँ निर्णय चर (decision variables) प्रत्येक टाइम स्लॉट $t$ के लिए बाइनरी वेक्टर $s(t) \in \{0, 1\}^K$ हैं। कुल खोज स्थान (search space) लिंक $K$ और समय क्षितिज $T$ के गुणनफल में कॉम्बिनेटरियल है, जिससे बड़े पैमाने के नेटवर्क के लिए सटीक समाधान गणनात्मक रूप से अव्यवहार्य (intractable) हो जाता है।

कार्यप्रणाली (Methodology)
लेखक लैग्रेंजियन द्वैत (Lagrangian duality) और स्टेट ऑग्मेंटेशन (state augmentation) पर आधारित एक लर्निंग-आधारित दृष्टिकोण प्रस्तावित करते हैं। कार्यप्रणाली तीन मुख्य सैद्धांतिक और व्यावहारिक चरणों में आगे बढ़ती है:

द्वैत डोमेन विश्लेषण और प्रिमल इनफिजिबिलिटी (Dual Domain Analysis and Primal Infeasibility):
लेखक पहले लैग्रेंजियन द्वैत का उपयोग करके समस्या का विश्लेषण करते हैं। वे प्रदर्शित करते हैं कि एक निश्चित द्वैत चर (dual variable) $\lambda$ के लिए लैग्रेंजियन मैक्सिमाइज़र समय-अपरिवर्तनीय (time-invariant) होते हैं (प्रपोजिशन 1)। अर्थात, इष्टतम शेड्यूल $s^\dagger(t, \lambda)$ समय के साथ नहीं बदलता है। फलस्वरूप, एक एकल इष्टतम द्वैत चर $\lambda^\star$ से प्राप्त स्थिर नीति (static policy) सभी लिंक के लिए न्यूनतम दर आवश्यकताओं को एक साथ पूरा करने में विफल रहती है, क्योंकि यह हस्तक्षेप से बचने के लिए ट्रांसमिशन को बदलने (alternate करने) में विफल रहती है। यह एक एकल इष्टतम $\lambda^\star$ और उसके अनुरूप एक स्थिर शेड्यूल खोजने वाले मानक प्रिमल-ड्यूल दृष्टिकोण को लॉन्ग-होरिज़ोन समस्या के लिए अपर्याप्त बनाता है।
ड्यूल ग्रेडिएंट डिसेंट डायनेमिक्स (Dual Gradient Descent Dynamics):
समय-अपरिवर्तनीयता की सीमा को दूर करने के लिए, शोध पत्र ड्यूल ग्रेडिएंट डिसेंट डायनेमिक्स की जांच करता है। बाधा उल्लंघन (subgradients) के आधार पर द्वैत चर $\lambda(u)$ को पुनरावृत्ति से अपडेट करके और प्रत्येक चरण में संगत लैग्रगरेंजियन मैक्सिमाइज़र $s^\ddagger(u)$ की गणना करके, एल्गोरिदम शेड्यूल्स का एक अनुक्रम (sequence) उत्पन्न करता है। सैद्धांतिक विश्लेषण (प्रपोजिशन 3) दिखाता है कि हालांकि इस अनुक्रम में व्यक्तिगत शेड्यूल इष्टतम नहीं हो सकते हैं, लेकिन अनुक्रम $s^\ddagger(1:T)$ की औसत दर $T \to \infty$ होने पर स्पर्शोन्मुख रूप से (asymptotically) इष्टतम और व्यवहार्य होती है। यह सुझाव देता है कि लॉन्ग-होरिज़ोन समस्या के समाधान के लिए ड्यूल ग्रेडिएंट डिसेंट के प्रक्षेपवक्र (trajectory) की नकल करने वाली नीति सीखना आवश्यक है।
स्टेट-ऑगमेंटेड ग्राफ न्यूरल नेटवर्क (SAGNT):
प्रत्येक चरण पर एनपी-हार्ड (NP-hard) लैग्रेंजियन मैक्सिमाइजेशन को हल किए बिना इसे कुशलतापूर्वक लागू करने के लिए, लेखक एक ग्राफ न्यूरल नेटवर्क (GNN) का उपयोग करके एक पैरामेट्रिक पॉलिसी $\Phi(A, \lambda; H)$ प्रस्तावित करते हैं।

स्टेट ऑग्मेंटेशन (State Augmentation): मुख्य नवाचार नेटवर्क टोपोलॉजी $A$ के साथ द्वैत चर $\lambda(t)$ को GNN के एक आंतरिक स्टेट (या इनपुट सिग्नल) के रूप में मानना है। यह नीति को वर्तमान बाधा उल्लंघन के स्तर के आधार पर शेड्यूलिंग निर्णयों को गतिशील रूप से अनुकूलित करने की अनुमति देता है।
प्रशिक्षण (ऑफलाइन - Training): GNN मापदंडों $H$ को विभिन्न नेटवर्क टोपोलॉजी और द्वैत चरों के वितरण पर तात्कालिक लैग्रेंजियन $M(s, \lambda)$ को अधिकतम करने के लिए ऑफलाइन प्रशिक्षित किया जाता है। लॉस फंक्शन (loss function) नमूना लिए गए $\lambda$ द्वारा भारित (weighted) बाधा उल्लंघनों को दंडित करता है।
निष्पादन (ऑनलाइन - Execution): निष्पादन के दौरान, प्रशिक्षित GNN वर्तमान नेटवर्क स्टेट $A$ और वर्तमान द्वैत चर $\lambda(t)$ के आधार पर एक शेड्यूल $s(t)$ उत्पन्न करता है। द्वैत चर को फिर बाधा उल्लंघन के सबग्रेडिएंट (समीकरण 21) का उपयोग करके ऑनलाइन अपडेट किया जाता है, जो ड्यूल ग्रेडिएंट डिसेंट डायनेमिक्स की नकल करने वाला एक क्लोज्ड-लूप सिस्टम बनाता है।

प्रमुख योगदान (Key Contributions)

सैद्धांतिक अंतर्दृष्टि: यह शोध पत्र स्थापित करता है कि जबकि इष्टतम लैग्रेंजियन मैक्सिमाइज़र समय-अपरिवर्तनीय हैं और इस प्रकार बाधा वाले लॉन्ग-होरिज़ोन समस्या के लिए अपर्याप्त हैं, ड्यूल ग्रेडिएंट डिसेंट द्वारा उत्पन्न मैक्सिमाइजर्स का अनुक्रम स्पर्शोन्मुख रूप से इष्टतम औसत दरें प्रदान करता है।
एल्गोरिदम डिज़ाइन: लेखक एक स्टेट-ऑगमेंटेड GNN (SAGNN) पेश करते हैं जो लैग्रेंजियन मैक्सिमाइजर्स का अनुमान लगाने के लिए सीखता है। द्वैत चरों को गतिशील इनपुट के रूप में शामिल करके, नीति समय के साथ शेड्यूलिंग निर्णयों को बदलना सीखती है, जो प्रभावी रूप से बाधा संतुष्टि और प्रदर्शन अधिकतमकरण के बीच संतुलन बनाती है।
स्केलेबिलिटी (Scalability): यह दृष्टिकोण लर्निंग पैरामीट्राइजेशन को समय क्षितिज $T$ की जटिलता से अलग करता है। GNN एक एकल टाइम स्टेप के लिए मैपिंग सीखता है, जिससे सीधे $T$ लंबाई के अनुक्रम को सीखने की आवश्यकता नहीं होती, जो गणनात्मक रूप से अत्यधिक महंगी होती।

परिणाम (Results)
लगभग 500 लिंक वाले रैंडम जियोमेट्रिक ग्राफ्स (RGGs) पर व्यापक संख्यात्मक सिमुलेशन किए गए।

बाधा संतुष्टि (Constraint Satisfaction): प्रस्तावित एल्गोरिदम अधिकांश लिंक के लिए न्यूनतम दर बाधाओं को सफलतापूर्वक पूरा करता है। कुछ कम-शेड्यूल किए गए लिंक के लिए, बाधा उल्लंघन मामूली हैं।
प्रदर्शन: विधि औसत कुल दर के मामले में कई बेसलाइन ह्यूरिस्टिक्स (heuristics) से बेहतर प्रदर्शन करती है और तेज़ रनटाइम प्राप्त करती है।
सामान्यीकरण (Generalization): सीखा गया नीति विभिन्न ट्रांसमिशन आवश्यकताओं के बीच सामान्यीकरण करने में मजबूती प्रदर्शित करता है और समय के साथ प्रभावी ढंग से अनुकूलित होता है। नीति सफलतापूर्वक गैर-हस्तक्षेप वाले लिंक के बीच बारी-बारी से काम करती है, और उन लिंक को प्राथमिकता देती है जिनका द्वैत चर विकसित होने के साथ बाधा उल्लंघन का स्तर अधिक होता है।

महत्व और दावे (Significance and Claims)
यह शोध पत्र दावा करता है कि इसका प्राथमिक महत्व ड्यूल ग्रेडिएंट डिसेंट की सैद्धांतिक इष्टतमता और कुशल, लर्निंग-आधारित शेड्यूलिंग नीतियों की व्यावहारिक आवश्यकता के बीच के अंतर को पाटने में निहित है। यह तर्क देता है कि स्टेट ऑग्मेंटेशन एक आवश्यक तकनीक है जो GNN को लॉन्ग-होरिज़ोन बाधाओं के लिए आवश्यक समय-परिवर्तनीय नीतियों को सीखने में सक्षम बनाती है, एक ऐसा कार्य जिसे मानक समय-अपरिवर्तनीय नीतियां या प्रत्यक्ष अनुक्रम सीखना (जो बहुत महंगा है) प्रभावी ढंग से हल नहीं कर सकते हैं। यह कार्य प्रमाणित करता है कि ड्यूल डायनेमिक्स की नकल करना सीखने से वायरलेस नेटवर्क में उच्च-आयामी, बाधा वाले कॉम्बिनेटरियल समस्याओं को गणनात्मक दक्षता के साथ हल किया जा सकता है।

इसी तरह के और पेपर