भौगोलिक रूटिंग: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Routing methodology for wireless networks}} | {{Short description|Routing methodology for wireless networks}} | ||
भौगोलिक रूटिंग | '''भौगोलिक रूटिंग''' जिसे जियोरूटिंग या स्थिति-आधारित [[मार्ग]] भी कहा जाता है,<ref name="Ruehrup"/> यह मुख्य रूप से रूटिंग सिद्धांत है जो [[भौगोलिक स्थिति]] से प्राप्त होने वाली जानकारी पर निर्भर करता है। यह मुख्य रूप से [[ बेतार तंत्र |वायरलेस सिस्टम]] के लिए प्रस्तावित किया गया है, और इस विचार पर आधारित है कि सोर्स नेटवर्क एड्रेस का उपयोग करने के अतिरिक्त गंतव्य के भौगोलिक स्थान पर संदेश भेजता है। इसके आधार पर [[पैकेट रेडियो]] [[नेटवर्क पता]] क्षेत्र में, रूटिंग के लिए स्थिति की जानकारी का उपयोग करने का विचार पहली बार 1980 के दशक में प्रस्तावित किया गया था<ref> | ||
{{cite journal | {{cite journal | ||
|last = Takagi |first = H. | |last = Takagi |first = H. | ||
| Line 12: | Line 12: | ||
|doi = 10.1109/TCOM.1984.1096061|citeseerx = 10.1.1.64.9747 | |doi = 10.1109/TCOM.1984.1096061|citeseerx = 10.1.1.64.9747 | ||
}} | }} | ||
</ref> इंटरकनेक्शन नेटवर्क के लिए | </ref> इसके आधार पर इंटरकनेक्शन नेटवर्क के लिए<ref> | ||
{{Cite document | {{Cite document | ||
|last = Finn |first = Gregory G. | |last = Finn |first = Gregory G. | ||
| Line 20: | Line 20: | ||
|url = http://www.isi.edu/div7/people/finn.home/routing_and_addressing_problems_in_large_metropolitan-scale_internetworks.BW.pdf | |url = http://www.isi.edu/div7/people/finn.home/routing_and_addressing_problems_in_large_metropolitan-scale_internetworks.BW.pdf | ||
}} | }} | ||
</ref> भौगोलिक रूटिंग के लिए आवश्यक है कि प्रत्येक [[नोड (नेटवर्किंग)]] अपना स्थान स्वयं निर्धारित कर सके और | </ref> भौगोलिक रूटिंग के लिए आवश्यक है कि प्रत्येक [[नोड (नेटवर्किंग)]] अपना स्थान स्वयं निर्धारित कर सके और सोर्स को गंतव्य के स्थान के बारे में पता रखते हैं। इस जानकारी के साथ, [[नेटवर्क टोपोलॉजी]] या पूर्व मार्ग खोज के ज्ञान के बिना संदेश को गंतव्य तक भेजा जा सकता है। | ||
==दृष्टिकोण== | ==दृष्टिकोण== | ||
विभिन्न दृष्टिकोण हैं, जैसे एकल-पथ, बहु-पथ और [[बाढ़ एल्गोरिथ्म]] | इसके विभिन्न दृष्टिकोण हैं, सर्वेक्षण के लिए जैसे एकल-पथ, बहु-पथ और [[बाढ़ एल्गोरिथ्म|फ्लडिंग एल्गोरिथ्म]] आधारित रणनीतियाँ देख सकते हैं।<ref> | ||
{{cite journal | {{cite journal | ||
|last = Stojmenovic |first = Ivan | |last = Stojmenovic |first = Ivan | ||
| Line 34: | Line 34: | ||
|year = 2002|citeseerx = 10.1.1.6.6012 | |year = 2002|citeseerx = 10.1.1.6.6012 | ||
}} | }} | ||
</ref> | </ref> अधिकांश एकल-पथ रणनीतियाँ दो तकनीकों पर निर्भर करती हैं: ग्रीडी फाॅर्वडिंग और फेस रूटिंग इसके प्रमुख उदाहरण हैं। ग्रीडी फाॅर्वडिंग प्रत्येक चरण में केवल स्थानीय जानकारी का उपयोग करके संदेश को गंतव्य के समीप लाने का प्रयास करता है। इस प्रकार, प्रत्येक नोड उस संदेश को मुख्यतः इसके समीपस्थ भाग के लिए अग्रेषित करता है, जो स्थानीय दृष्टिकोण से सबसे अधिक उपयुक्त है। सबसे उपयुक्त समीपस्थ वह हो सकता है जो प्रत्येक चरण में गंतव्य की दूरी कम से कम कर दे (ग्रीडी)। वैकल्पिक रूप से, कोई प्रगति की और धारणा पर विचार कर सकता है, अर्थात् सोर्स-गंतव्य-रेखा (एमएफआर, एनएफपी) पर अनुमानित दूरी, या समीपस्थ और गंतव्य (कम्पास रूटिंग) के बीच न्यूनतम कोण हैं। ये सभी रणनीतियाँ लूप-मुक्त नहीं हैं, अर्ताथ संदेश निश्चित समूह में नोड्स के बीच प्रसारित हो सकता है। यह ज्ञात है कि मौलिक रूप से ग्रीडी टैक्नीक और एमएफआर लूप मुक्त हैं, जबकि एनएफपी और कम्पास रूटिंग नहीं हैं।<ref> | ||
{{cite journal | {{cite journal | ||
|last = Stojmenovic |first = Ivan | |last = Stojmenovic |first = Ivan | ||
| Line 51: | Line 51: | ||
| image1 = Georouting greedy variants.svg | | image1 = Georouting greedy variants.svg | ||
| width1 = 300 | | width1 = 300 | ||
| caption1 = | | caption1 = ग्रीडी फाॅर्वडिंग प्रकार: किसी संदेश को गंतव्य (D) तक अग्रेषित करने के लिए रिले नोड खोजने के लिए स्रोत नोड (S) के पास अलग-अलग विकल्प होते हैं। A = अग्रेषण प्रगति के साथ निकटतम (NFP), B = त्रिज्या (NFR) के भीतर सबसे अधिक अग्रेषण प्रगति, C = कम्पास रूटिंग, E = ग्रीडी | ||
| width2 = 336 | | width2 = 336 | ||
| image2 = Georouting face routing.svg | | image2 = Georouting face routing.svg | ||
| caption2 = | | caption2 = फेस रूटिंग: एक संदेश को संचार ग्राफ के फेसेस के आंतरिक भाग के साथ रूट किया जाता है, जिसमें एस-डी-लाइन (लाल) को पार करने वाले किनारों पर फेसेस में परिवर्तित होता है। अंतिम रूटिंग पथ नीले रंग में दिखाया गया है। | ||
}} | }} | ||
ग्रीडी फाॅर्वडिंग मृत अंत की ओर ले जा सकता है, जहाँ गंतव्य के समीप कोई समीपस्थ नहीं है। पुनः फेस रूटिंग उस स्थिति से उबरने और दूसरे नोड के लिए रास्ता खोजने में सहायता करती है, जहाँ ग्रीडी फाॅर्वडिंग फिर से प्रारंभ किया जा सकता है। यह सुनिश्चित करने के लिए कि संदेश को गंतव्य तक पहुंचाया जा सकता है, फेस रूटिंग जैसी पुनर्प्राप्ति रणनीति आवश्यक है। ग्रीडी फाॅर्वडिंग और फेस रूटिंग का संयोजन पहली बार 1999 में GFG (ग्रीडी-फेस-ग्रीडी) नाम से प्रस्तावित किया गया था।<ref> | |||
{{cite conference | {{cite conference | ||
| last = Bose | first = P. | author1-link = Jit Bose | | last = Bose | first = P. | author1-link = Jit Bose | ||
| Line 65: | Line 65: | ||
| pages = 48–55 | | pages = 48–55 | ||
| doi = 10.1145/313239.313282 | doi-access = free }} | | doi = 10.1145/313239.313282 | doi-access = free }} | ||
</ref> यह तथाकथित यूनिट डिस्क ग्राफ़ नेटवर्क मॉडल में डिलीवरी की गारंटी देता है। विभिन्न प्रकार, जिन्हें बाद में प्रस्तावित किया गया था | </ref> यह तथाकथित यूनिट डिस्क ग्राफ़ नेटवर्क मॉडल में डिलीवरी की गारंटी देता है। विभिन्न प्रकार, जिन्हें बाद में प्रस्तावित किया गया था,<ref> | ||
<ref> | |||
{{cite journal | {{cite journal | ||
|last = Djenouri |first = Djamel | |last = Djenouri |first = Djamel | ||
| Line 78: | Line 77: | ||
|year = 2011|s2cid = 11139687 | |year = 2011|s2cid = 11139687 | ||
}} | }} | ||
</ref> | </ref> गैर-यूनिट डिस्क ग्राफ़ के लिए भी, GFG के सिद्धांतों पर आधारित हैं।<ref name="Ruehrup"> | ||
{{Cite book | {{Cite book | ||
|last = Ruehrup |first = Stefan | |last = Ruehrup |first = Stefan | ||
| Line 90: | Line 87: | ||
|url = http://archive.cone.informatik.uni-freiburg.de/people/ruehrup/georouting-chapter-draft.pdf | |url = http://archive.cone.informatik.uni-freiburg.de/people/ruehrup/georouting-chapter-draft.pdf | ||
}} | }} | ||
</ref> | </ref> | ||
फेस रूटिंग सामान्य तौर पर समतल उपग्राफ पर निर्भर करती है | फेस रूटिंग सामान्य तौर पर एक समतल उपग्राफ पर निर्भर करती है, चूंकि वितरित प्लान करने के लिए वास्तविक वायरलेस सेंसर नेटवर्क के अनुसार यह अत्यधिक कठिन है और 3डी वातावरण के लिए अच्छा स्केल नहीं है।<ref> | ||
{{cite conference | |||
{{cite conference | | last = Kim | first = Y | ||
| author2=Ramesh Govindan | |||
| author2-link=Ramesh Govindan | |||
| author3=Karp, Brad. | |||
| author4=Scott Shenker | |||
| author4-link=Scott Shenker | |||
| title = On the Pitfalls of Geographic Face Routing | |||
| book-title = Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing | |||
| year = 2005 | |||
| pages = 34–43 | |||
| doi = 10.1145/1080810.1080818 }} | |||
</ref> | |||
</ref> | ==[[लालची एम्बेडिंग|ग्रीडी एम्बेडिंग]]== | ||
यद्यपि मूल रूप से रूटिंग योजना के रूप में विकसित किया गया था जो प्रत्येक नोड की भौतिक स्थिति का उपयोग करता है, इस प्रकार भौगोलिक रूटिंग एल्गोरिदम को नेटवर्क पर भी लागू किया गया है, जिसमें प्रत्येक नोड वर्चुअल स्पेस में बिंदु से जुड़ा हुआ है, जो इसकी भौतिक स्थिति से असंबंधित है। किसी नेटवर्क के नोड्स के लिए आभासी स्थितियों का सेट खोजने की प्रक्रिया हैं, जिससे कि इन स्थितियों का उपयोग करके भौगोलिक रूटिंग के सफल होने की गारंटी हो, ग्रीडी एम्बेडिंग कहलाती है।<ref>{{citation | |||
==[[लालची एम्बेडिंग]]== | |||
यद्यपि मूल रूप से रूटिंग योजना के रूप में विकसित किया गया था जो प्रत्येक नोड की भौतिक स्थिति का उपयोग करता है, भौगोलिक रूटिंग एल्गोरिदम को नेटवर्क पर भी लागू किया गया है जिसमें प्रत्येक नोड वर्चुअल स्पेस में बिंदु से जुड़ा हुआ है, जो इसकी भौतिक स्थिति से असंबंधित है। किसी नेटवर्क के नोड्स के लिए आभासी स्थितियों का सेट खोजने की प्रक्रिया, | |||
| last1 = Rao | first1 = Ananth | | last1 = Rao | first1 = Ananth | ||
| last2 = Ratnasamy | first2 = Sylvia | | last2 = Ratnasamy | first2 = Sylvia | ||
| Line 119: | Line 113: | ||
| title = Proc. 9th ACM Mobile Computing and Networking (MobiCom) | | title = Proc. 9th ACM Mobile Computing and Networking (MobiCom) | ||
| year = 2003}}.</ref> | | year = 2003}}.</ref> | ||
==यह भी देखें== | ==यह भी देखें== | ||
*[[तदर्थ रूटिंग प्रोटोकॉल की सूची]] | *[[तदर्थ रूटिंग प्रोटोकॉल की सूची|एचओसी रूटिंग प्रोटोकॉल की सूची]] | ||
*[[बैकप्रेशर रूटिंग]] | *[[बैकप्रेशर रूटिंग]] | ||
| Line 128: | Line 120: | ||
{{Reflist}} | {{Reflist}} | ||
{{DEFAULTSORT:Geographic Routing}} | {{DEFAULTSORT:Geographic Routing}} | ||
[[Category: | [[Category:CS1 errors]] | ||
[[Category:Created On 26/07/2023]] | [[Category:Created On 26/07/2023|Geographic Routing]] | ||
[[Category:Lua-based templates|Geographic Routing]] | |||
[[Category:Machine Translated Page|Geographic Routing]] | |||
[[Category:Pages with broken file links|Geographic Routing]] | |||
[[Category:Pages with script errors|Geographic Routing]] | |||
[[Category:Short description with empty Wikidata description|Geographic Routing]] | |||
[[Category:Templates Vigyan Ready|Geographic Routing]] | |||
[[Category:Templates that add a tracking category|Geographic Routing]] | |||
[[Category:Templates that generate short descriptions|Geographic Routing]] | |||
[[Category:Templates using TemplateData|Geographic Routing]] | |||
[[Category:भौगोलिक स्थिति|Geographic Routing]] | |||
[[Category:रूटिंग एल्गोरिदम|Geographic Routing]] | |||
[[Category:रूटिंग प्रोटोकॉल|Geographic Routing]] | |||
[[Category:वायरलेस नेटवर्किंग|Geographic Routing]] | |||
Latest revision as of 12:21, 17 August 2023
भौगोलिक रूटिंग जिसे जियोरूटिंग या स्थिति-आधारित मार्ग भी कहा जाता है,[1] यह मुख्य रूप से रूटिंग सिद्धांत है जो भौगोलिक स्थिति से प्राप्त होने वाली जानकारी पर निर्भर करता है। यह मुख्य रूप से वायरलेस सिस्टम के लिए प्रस्तावित किया गया है, और इस विचार पर आधारित है कि सोर्स नेटवर्क एड्रेस का उपयोग करने के अतिरिक्त गंतव्य के भौगोलिक स्थान पर संदेश भेजता है। इसके आधार पर पैकेट रेडियो नेटवर्क पता क्षेत्र में, रूटिंग के लिए स्थिति की जानकारी का उपयोग करने का विचार पहली बार 1980 के दशक में प्रस्तावित किया गया था[2] इसके आधार पर इंटरकनेक्शन नेटवर्क के लिए[3] भौगोलिक रूटिंग के लिए आवश्यक है कि प्रत्येक नोड (नेटवर्किंग) अपना स्थान स्वयं निर्धारित कर सके और सोर्स को गंतव्य के स्थान के बारे में पता रखते हैं। इस जानकारी के साथ, नेटवर्क टोपोलॉजी या पूर्व मार्ग खोज के ज्ञान के बिना संदेश को गंतव्य तक भेजा जा सकता है।
दृष्टिकोण
इसके विभिन्न दृष्टिकोण हैं, सर्वेक्षण के लिए जैसे एकल-पथ, बहु-पथ और फ्लडिंग एल्गोरिथ्म आधारित रणनीतियाँ देख सकते हैं।[4] अधिकांश एकल-पथ रणनीतियाँ दो तकनीकों पर निर्भर करती हैं: ग्रीडी फाॅर्वडिंग और फेस रूटिंग इसके प्रमुख उदाहरण हैं। ग्रीडी फाॅर्वडिंग प्रत्येक चरण में केवल स्थानीय जानकारी का उपयोग करके संदेश को गंतव्य के समीप लाने का प्रयास करता है। इस प्रकार, प्रत्येक नोड उस संदेश को मुख्यतः इसके समीपस्थ भाग के लिए अग्रेषित करता है, जो स्थानीय दृष्टिकोण से सबसे अधिक उपयुक्त है। सबसे उपयुक्त समीपस्थ वह हो सकता है जो प्रत्येक चरण में गंतव्य की दूरी कम से कम कर दे (ग्रीडी)। वैकल्पिक रूप से, कोई प्रगति की और धारणा पर विचार कर सकता है, अर्थात् सोर्स-गंतव्य-रेखा (एमएफआर, एनएफपी) पर अनुमानित दूरी, या समीपस्थ और गंतव्य (कम्पास रूटिंग) के बीच न्यूनतम कोण हैं। ये सभी रणनीतियाँ लूप-मुक्त नहीं हैं, अर्ताथ संदेश निश्चित समूह में नोड्स के बीच प्रसारित हो सकता है। यह ज्ञात है कि मौलिक रूप से ग्रीडी टैक्नीक और एमएफआर लूप मुक्त हैं, जबकि एनएफपी और कम्पास रूटिंग नहीं हैं।[5]
ग्रीडी फाॅर्वडिंग प्रकार: किसी संदेश को गंतव्य (D) तक अग्रेषित करने के लिए रिले नोड खोजने के लिए स्रोत नोड (S) के पास अलग-अलग विकल्प होते हैं। A = अग्रेषण प्रगति के साथ निकटतम (NFP), B = त्रिज्या (NFR) के भीतर सबसे अधिक अग्रेषण प्रगति, C = कम्पास रूटिंग, E = ग्रीडी
फेस रूटिंग: एक संदेश को संचार ग्राफ के फेसेस के आंतरिक भाग के साथ रूट किया जाता है, जिसमें एस-डी-लाइन (लाल) को पार करने वाले किनारों पर फेसेस में परिवर्तित होता है। अंतिम रूटिंग पथ नीले रंग में दिखाया गया है।
ग्रीडी फाॅर्वडिंग मृत अंत की ओर ले जा सकता है, जहाँ गंतव्य के समीप कोई समीपस्थ नहीं है। पुनः फेस रूटिंग उस स्थिति से उबरने और दूसरे नोड के लिए रास्ता खोजने में सहायता करती है, जहाँ ग्रीडी फाॅर्वडिंग फिर से प्रारंभ किया जा सकता है। यह सुनिश्चित करने के लिए कि संदेश को गंतव्य तक पहुंचाया जा सकता है, फेस रूटिंग जैसी पुनर्प्राप्ति रणनीति आवश्यक है। ग्रीडी फाॅर्वडिंग और फेस रूटिंग का संयोजन पहली बार 1999 में GFG (ग्रीडी-फेस-ग्रीडी) नाम से प्रस्तावित किया गया था।[6] यह तथाकथित यूनिट डिस्क ग्राफ़ नेटवर्क मॉडल में डिलीवरी की गारंटी देता है। विभिन्न प्रकार, जिन्हें बाद में प्रस्तावित किया गया था,[7] गैर-यूनिट डिस्क ग्राफ़ के लिए भी, GFG के सिद्धांतों पर आधारित हैं।[1]
फेस रूटिंग सामान्य तौर पर एक समतल उपग्राफ पर निर्भर करती है, चूंकि वितरित प्लान करने के लिए वास्तविक वायरलेस सेंसर नेटवर्क के अनुसार यह अत्यधिक कठिन है और 3डी वातावरण के लिए अच्छा स्केल नहीं है।[8]
ग्रीडी एम्बेडिंग
यद्यपि मूल रूप से रूटिंग योजना के रूप में विकसित किया गया था जो प्रत्येक नोड की भौतिक स्थिति का उपयोग करता है, इस प्रकार भौगोलिक रूटिंग एल्गोरिदम को नेटवर्क पर भी लागू किया गया है, जिसमें प्रत्येक नोड वर्चुअल स्पेस में बिंदु से जुड़ा हुआ है, जो इसकी भौतिक स्थिति से असंबंधित है। किसी नेटवर्क के नोड्स के लिए आभासी स्थितियों का सेट खोजने की प्रक्रिया हैं, जिससे कि इन स्थितियों का उपयोग करके भौगोलिक रूटिंग के सफल होने की गारंटी हो, ग्रीडी एम्बेडिंग कहलाती है।[9]
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 Ruehrup, Stefan (2009). Liu; Chu; Leung (eds.). Theory and Practice of Geographic Routing (PDF). Ad Hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols. Bentham Science.
- ↑ Takagi, H.; Kleinrock, L. (March 1984). "Optimal transmission ranges for randomly distributed packet radio terminals". IEEE Transactions on Communications. 32 (3): 246–257. CiteSeerX 10.1.1.64.9747. doi:10.1109/TCOM.1984.1096061.
- ↑
Finn, Gregory G. (March 1987). "Routing and Addressing Problems in Large Metropolitan-Scale Internetworks" (PDF). University of Southern California, ISI/RR-87-180.
{{cite journal}}: Cite journal requires|journal=(help) - ↑ Stojmenovic, Ivan (2002). "Position based routing in ad hoc networks". IEEE Communications Magazine. 40 (7): 128–134. CiteSeerX 10.1.1.6.6012. doi:10.1109/MCOM.2002.1018018.
- ↑ Stojmenovic, Ivan; Lin, Xu (2001). "Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks". IEEE Transactions on Parallel and Distributed Systems. 12 (10): 1023–1032. CiteSeerX 10.1.1.67.7527. doi:10.1109/71.963415.
- ↑ Bose, P.; Morin, P.; Stojmenovic, I.; Urrutia, J. (1999). "Routing with guaranteed delivery in ad hoc wireless networks". Proc. of the 3rd international workshop on discrete algorithms and methods for mobile computing and communications (DIALM '99). pp. 48–55. doi:10.1145/313239.313282.
- ↑ Djenouri, Djamel; Balasingham, Ilangko (2011). "Traffic-Differentiation-Based Modular QoS Localized Routing for Wireless Sensor Networks". IEEE Transactions on Mobile Computing. 10 (6): 797–809. doi:10.1109/TMC.2010.212. S2CID 11139687.
- ↑ Kim, Y; Ramesh Govindan; Karp, Brad.; Scott Shenker (2005). "On the Pitfalls of Geographic Face Routing". Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing. pp. 34–43. doi:10.1145/1080810.1080818.
- ↑ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H.; Shenker, Scott; Stoica, Ion (2003), "Geographic routing without location information", Proc. 9th ACM Mobile Computing and Networking (MobiCom), pp. 96–108.
