تا 60% تخفیف
برای 3 نفر
به همراه صدور مدرک
مانده تا پایان تخفیف ها
الگوریتم مسیریابی شایعه ای چیست ؟ Rumor Routing به زبان ساده
مسیر یابیِ شایعه‌ای چیست؟ همانطور که میدانید الگوریتمهای مسیریابی مختلفی وجود داردند در بین الگوریتمهای با محوریت داده روشی موجود هست به نام الگوریتم مسیر یابی شایعه‌ای . حال در این مقاله به تفصیل این پروتکل را بررسی خواهیم کرد.کیفیت مسیر در بسیاری از کاربردهایِ مسیریابی از اهمیت بالایی برخوردار نمی باشد، چرا که اطلاعاتی که قرار است بین مقصد و مبداً رد و بدل شود دارای حجم کمی است.
دوره های شبکه، برنامه نویسی، مجازی سازی، امنیت، نفوذ و ... با برترین های ایران
سرفصل های این مطلب
برای همین منظور وجود یک مسیر حتی غیر بهینه در شبکه بین مبدا و مقصد می‌تواند از اتلاف انرژی که در زمان پخش سیل‌آسای بسته‌ها صورت میگیرد جلوگیری کند.در شبکه‌هایی که تعداد رویدادهای رخ داده شده در شبکه کمتر از تعداد پرس‌وجوها باشد بهتر است که وقوع رویداد را به صورت سیل آسا به اطلاع دیگران برسانیم. ولی در شبکه‌هایی که تعداد پرس و جوها کمتر باشد، پخش سیل آسای پرس وجو به صرفه‌تر است.مسیریابی شایعه‌ای حد وسطی میان این دو روش ارائه میدهد.
ایده روش ارائه شده در این قسمت بر این اساس قرار گرفته که مسیرهایی در شبکه ایجاد کنیم که ما را به سمت رویداد هدایت کند. به محض اینکه پرس و جوها بتوانند یکی از این مسیرها را کشف کنند می‌توانند با دنبال کردن آنها به محل رویداد مورد جستجوی خود برسند. در صورتی که پرسجوها نتوانند این مسیرها را پیدا کنند، اقدام به پخش سیل آسای خود در شبکه می‌کنند.
تعداد مسیرهای منتهی به رویداد و تعداد پرس وجوهایی که به ازای هر رویداد ارسال می‌شوند، همگی فاکتورهایی هستند که با تنظیم آنها در این نوع مسیریابی، می‌توان کاربردها و نیازمندیهای مختلفی را در شبکه پوشش داد. در این الگوریتم نودهایی که شاهد وقوع یک رویداد در شبکه هستند اقدام به ارسال تعدادی عامل با طول عمر بالا در شبکه می‌کنند.
این عاملها که حاوی اطلاعات رویدادِ به وقوع پیوسته می‌باشد، در شبکه شروع به حرکت تصادفی کرده و مسیرهای منتهی به یک رویدادِ خاص را به وجود می‌آورند. زمانی که عامل در سر راه خود به مسیری که یک عامل دیگر ایجاد کرده برخورد کند اطلاعاتِ رویداد مربوط به به آنرا نیز همراه با خود به همراه می‌برد.
به این ترتیب مسیری ایجاد می‌شود که منتهی به هر دو رویداد می‌باشد.در شکل زیر زمانی که عاملی که در حال ایجاد مسیر منتهی به رویداد 2 است از روی مسیر منتهی به رویداد 1 عبور می‌کند، مسیری ایجاد می‌کند که منتهی به هر دو رویداد 1و2 می‌شود.
درواقع تصویر فوق زمانی که عاملی که در حال پخش مسیری به سمت رویداد2 است از روی مسیر منتهی به رویداد 1 می‌گذرد، شروع به ایجاد مسیری می کند که منتهی به هر دو رویداد است. عاملها همچنین مسیرهای بوجود آمده در شبکه را در صورتی که مسیر کوتاهتری پیدا کنند بهینه می‌کنند.
در شکل بالا به صورت مطلوب تر عامل تغییر مسیر وجود دارد ، زمانی که یک عامل نودی را پیدا می‌کند که طول مسیر منتهی به یک رویداد خاص در آن بزرگتر از چیزی باشد که در داخل عامل باشد جدول مسیریابی نود را با اطلاعات جدید خود بروز می‌کند.
در ادامه به تشریح بیشتر این الگوریتم با جزئیات بیشتر خواهیم پرداخت. زمانی که تعداد پرس و جوها در مقایسه با تعداد رویدادها کم باشد می‌توانیم برای پخش سریع ولی پر هزینه پرس‌وجوی خود در شبکه اقدام به پخش سیل‌آسای آن بکنیم. اگر N نود و Q عدد پرس‌وجو در شبکه داشته باشیم به تعداد N*Q ارسال در شبکه خواهیم داشت. این در حالی است که فرض کنیم هیچ تصادمی اتفاق نمی‌افتد. انرژی مصرف شده در این حالت مستقل از تعداد رویدادهای به وقوع پیوسته در شبکه است.
پخش سیل آسای اطلاعات رویدادها
زمانی که یک نود شاهد به وقوع پیوستن یک رویداد در شبکه است می‌تواند اطلاعات آنرا در شبکه به صورت سیل آسا منتشر کند. پخش سیل آسای هر رویداد حداقل به اندازه N ارسال بدنبال دارد. زمانی که پخش سیل آسای رویداد به اتمام رسید، پرس وجوها می‌توانند از کوتاهترین و قابل اطمینانترین مسیر به رویداد مورد نظر برسند.
بنابراین می توان از میزان مصرف انرژی توسط پرس‌وجوها برای رسیدن به رویداد از طریق این مسیر کوتاهِ ایجاد شده صرفنظر کرد و کل انرژی مصرف شده در حالت پخش سیل آسای E تعداد رویداد را برابر N*E در نظر گرفت.این میزان مصرف انرژی مستقل از تعداد پرس‌وجوها می‌باشد. بنابراین زمانی که تعداد رویدادها در شبکه در مقایسه با تعداد پرس‌وجوها کمتر باشد پخش سیل آسای رویداد بهینه تر است.در ادامه این پخش سعی می‌شود که حد آستانه‌ای برای روش مسیریابیِ شایعه‌ای در مقایسه با این دو مدل یافت شود.
تصویر بالا نیز مقایسه پخش سیل آسای رویداد و پرس‌وجو با مسیریابی شایعه‌ای را نشان میدهد.در قسمت قبلی مقاله الگوریتم مسیر یابی شایعه ای در مورد مقدمات فهم الگوریتم و مسیر یابی و همچنین پخش سیل آسای اطلاعات رویدادها صحبت شد در این قسمت می پردازیم به شرح الگوریتم عاملهای رویداد و عاملهای پرس‌وجو ، و در نهایت شبیه سازی با توسینسو همراه ما باشید.
شرح الگوریتم
شرح مختصر الگوریتم و در انتها به صورت شبه کد آمده است. هر نود در ابتدای کار شبکه لیستی از همسایگان خود را در خود ذخیره و نگهداری می‌کند. این کار به روشهای گوناگونی می‌تواند انجام شود. به عنوان مثال هر نو می تواند بسته‌ای را به همه همسایگان خود ارسال کرده و وجود خود را به آنها اعلام کند.همچنین نودها می‌توانند با گوش دادن به پیامهای رسیده از وجود همسایگان خود مطلع شوند.
زمانی که یک نود شاهد وقوع یک رویداد در شبکه است، با یک احتمالی (میزان این احتمال جزو پارامترهای شبکه است که باید در ابتدا تعیین شود) یک عامل به نام عاملِ رویداد ایجاد می‌کند. همچنین رویداد مشاهده شده را در جدول رویدادهای خود با فاصله صفر (میزان فاصله با آن رویداد) درج می‌کند. نود دارنده عامل یکی از همسایگان خود را به طور تصادفی برای گام بعدی انتخاب و عامل را به آن ارسال می‌کند.
یک عامل بسته‌ای با طول عمر بالا است که در شبکه حرکت کرده و اطلاعات رویدادِ خاصی را در شبکه منتشر می‌کند. عاملها شامل یک جدول رویداد مشابه نودها در خود می‌باشند. این جدول در زمانی که عامل به یک نود جدید می‌رسد، خود را با جدول موجود در داخل نود همگام و یکسان می‌کنند. طول عمر عاملهای رویداد را با La در اشکال نشان می‌دهیم.
هر نودی می‌تواند برای اطلاع از وقوع یک رویدادِ خاص، اقدام به ایجاد عاملهای پرس‌وجو کند. اگر نود حاوی یک مسیر منتهی به رویداد در جدول خود باشد، عاملِ پرس‌وجو را به همان سمت ارسال می‌کند. در غیر این صورت نود عامل پرس‌وجو را به یک نودِ تصادفی ارسال می‌کند.
این عمل تا زمانی که طول عمر پرس‌وجو (Lq) تمام شود یا اینکه پرس‌وجو به نودِ مشاهده کننده رویداد برسد ادامه خواهد داشت.اگر نودی که پرس‌وجو را ایجاد کرده و در شبکه پخش کرده است تشخیص دهد که عامل پرس‌وجو موفق به یافتن نود مقصد نشده است، می‌تواند آنرا دوباره ارسال کرده و یا اقدام به پخش سیل آسای ان بکند.
عاملهای رویداد
هر عامل، نودِ خود را از رویدادهایی که در مسیر حرکت خود مشاهده کرده مطلع می‌سازد. برای این منظور عامل لیستی از رویدادهایی که در مسیر خود با آنها مواجه شده را به همراه تعداد گام برای رسیدن به آنها را با خود حمل می‌کند. زمانی که عامل از نود B به نود A می‌رود، جدول خود را با جدول موجود در نود A همگام می‌سازد.
در شکل مسیر منتهی به رویداد E1 در نود A طولانی‌تر از مسیر منتهی به رویداد E1 در عامل می‌باشد. در عین حال عامل اطلاعاتی درباره رویداد E2 را در خود ندارد.بعد از همگام سازی جدول نود و عامل با یکدیگر، جدول رویدادِ عامل از E2 مطلع شده و همچنین جدول رویدادِ موجود در نود A نیز از نظر طول مسیر منتهی به E1 بهینه می‌شود.
در زمان ارسال بسته‌ها در شبکه نودهای همسایه می‌توانند به عامل در حال حرکت گوش کرده و جداول رویداد خود را بروز کند. به این معنی که عامل در زمان حرکت مسیرِ ضخیمی را در پشت خود ایجاد می‌کند. در بخشهای آینده این مطلب را با جزئیات بیشتری ارزیابی خواهیم کرد.
عامل از سمت چپ گره B که شامل یک مسیر به طول3 می باشد به E1 راه دارد هنگامی که به گره می رسد یک جدول همگام سازی انجام می شود و آن را در مورد مسیر E2 یاد میگیرد و ضمناً بهینه سازی مسیر را به E1 انجام میدهد
شکل بالا: همگام سازی جداول عاملها و نودها با یکدیگر
زمانی که نود در حال حرکت در شبکه است، لیستی از نودهایی که اخیرا مشاده کرده را با خود حمل می‌کند. زمانی که عامل به نودی می‌رسد تمام هسایگان آن نود را نیز به لیست خود اضافه می‌کند. در زمان انتخاب گام بعدی برای ارسال، سعی می‌شود تا نودی انتخاب شود که در داخل این لیست نباشد.
بدین وسیله از بوجود آمدن حلقه در مسیر حرکت جلوگیری شده و سعی می‌شود عاملها در گستره بیشتری در شبکه حرکت کنند.جداول رویدادها در داخل نودها دارای یک فیلدی به نام زمان اعتبار برای رویداد می‌باشند که نشان می‌دهند اطلاعات یک رویداد را تا چه زمانی در خود نگهداری کند.
تعداد عاملهای رویداد ایجاد شده توسط نودها به عوامل مختلفی بستگی دارد.هر نودی که شاهد وقوع یک رویداد در شبکه است با یک احتمالِ ثابتی اقدام به ایجاد و پخش اطلاعاتِ رویداد توسط عاملهای رویداد می کند. تعداد عاملهای ایجاد شده در شبکه به تعداد رویدادها، اندازه و وسعت رویداد در شبکه و چگالی نودها بستگی دارد.
عاملهای پرس و جو
یک پرس‌وجو می‌تواند توسط هر کدام از نودهای موجود در شبکه و برای هر رویدادی در هر زمانی ایجاد شود. اگر یک نود مسیری به سمت آن رویداد داشته باشد، عامل پرس‌وجو را به آن سمت ارسال می‌کند. در غیر این صورت عامل پرس‌وجو را در صورتی که طول عمر آن به اتمام نرسیده باشد به یکی از همسایگان خود به صورت تصادفی ارسال می‌کند.
روش ارسال عاملِ پرس‌وجو مشابهِ ارسال عامل رویداد است و همانند آن روشهایی استفاده می‌کند که تا اندازه ممکن از بوجود آمدن حلقه جلوگیری شود. پرس‌وجو ها همگی دارای یک مشخصه تصادفی هستند.در صورتی که نود، عاملِ پرس‌وجو را به سمت مسیر منتهی به رویداد ارسال کند
مشخصه پرس‌وجو را موقتا در خود ذخیره کرده تا در صورتی که این عامل دوباره به دست نود رسید، به جای اینکه به سمت مسیر منتهی به رویداد ارسال شود اینبار به یکی از همسایگانِ تصادفی ارسال شود. بدین صورت از بوجود آمدن حلقه های بی مورد جلوگیری شود.در صورتی که پرس و جو نتواند به رویداد مورد نظر خود برسد، ساده ترین روش ارسال، پخش سیل آسایِ پرس‌وجو در شبکه است. البته این مورد کمتر در شبکه اتفاق می‌افتد.
شبیه سازی
شبیه سازی این الگوریتم در محیطی به نام LecsSim[16] انجام شده است. تعداد نودهای در نظر گرفته شده 3000، 4000 و 5000 نود می‌باشد که با توزیع یکنواخت تصادفی در محیطی به ابعداد 200*200 متر مربع پراکنده شده اند. شعاع ارسال هر نود 5 متر در نظر گرفته شده است.
رویدادها به صورت تصادفی در شبکه به تعداد10,50،100 تا ایجاد می‌شود شکلی دایره‌ای به شعاع 5 متر دارند. الگوی تولید پرس‌وجو ها نیز تصادفی بوده و در تعداد 1000 در شبکه، که هر کدام از یک نود تصادفی برای یک رویداد تصادفی ارسال می‌شوند.در ابتدا نودها در شبکه اقدام به ارسال عاملهای رویداد و ارسال آنها می‌کنند. پس از آن که مسیرهای منتهی به رویدادها در شبکه ایجاد شد، پرس‌وجوها شروع به ساخته شدن و ارسال می‌کنند.در نهایت تعداد پرس‌وجوهای موفق ثبت می‌شوند
مطابق شکل : مقایسه پخش سیل آسای رویداد و پرس‌وجو با مسیریابی شایعه‌ای با پارمترهای
مختلف.A تعداد عاملهای پرس‌وجو می باشد.
شکل بالا مسیریابی شایعه‌ای با 10 رویداد در شبکه.