در توسینسو تدریس کنید

و

با دانش خود درآمد کسب کنید

الگوریتم مسیریابی شایعه ای چیست ؟ معرفی Rumor Routing قسمت 1

Rumor Routing Algorithm For Sensor Networks

مسیر یابیِ شایعه‌ای

الگوریتم مسیر یابیِ شایعه‌ای  قسمت اول

همانطور که میدانید الگوریتمهای مسیریابی مختلفی وجود داردند در بین الگوریتمهای با محوریت داده روشی موجود هست به نام الگوریتم مسیر یابی شایعه‌ای . حال در این مقاله به تفصیل این پروتکل را بررسی خواهیم کرد.

کیفیت مسیر در بسیاری از کاربردهایِ مسیریابی از اهمیت بالایی برخوردار نمی باشد، چرا که اطلاعاتی که قرار است بین مقصد و مبداً رد و بدل شود دارای حجم کمی است. برای همین منظور وجود یک مسیر حتی غیر بهینه در شبکه بین مبدا و مقصد می‌تواند از اتلاف انرژی که در زمان پخش سیل‌آسای بسته‌ها صورت می‌گیرد جلوگیری کند.

در شبکه‌هایی که تعداد رویدادهای رخ داده شده در شبکه کمتر از تعداد پرس‌وجوها باشد بهتر است که وقوع رویداد را به صورت سیل آسا به اطلاع دیگران برسانیم. ولی در شبکه‌هایی که تعداد پرس و جوها کمتر باشد، پخش سیل آسای پرس وجو به صرفه‌تر است.

مسیریابی شایعه‌ای حد وسطی میان این دو روش ارائه می‌دهد.

الگوریتم مسیر یابیِ شایعه‌ای  قسمت اول

ایده روش ارائه شده در این قسمت بر این اساس قرار گرفته که مسیرهایی در شبکه ایجاد کنیم که ما را به سمت رویداد هدایت کند. به محض اینکه پرس و جوها بتوانند یکی از این مسیرها را کشف کنند می‌توانند با دنبال کردن آنها به محل رویداد مورد جستجوی خود برسند. در صورتی که پرسجوها نتوانند این مسیرها را پیدا کنند، اقدام به پخش سیل آسای خود در شبکه می‌کنند.

تعداد مسیرهای منتهی به رویداد و تعداد پرس وجوهایی که به ازای هر رویداد ارسال می‌شوند، همگی فاکتورهایی هستند که با تنظیم آنها در این نوع مسیریابی، می‌توان کاربردها و نیازمندیهای مختلفی را در شبکه پوشش داد.

در این الگوریتم نودهایی که شاهد وقوع یک رویداد در شبکه هستند اقدام به ارسال تعدادی عامل با طول عمر بالا در شبکه می‌کنند. این عاملها که حاوی اطلاعات رویدادِ به وقوع پیوسته می‌باشد، در شبکه شروع به حرکت تصادفی کرده و مسیرهای منتهی به یک رویدادِ خاص را به وجود می‌آورند. زمانی که عامل در سر راه خود به مسیری که یک عامل دیگر ایجاد کرده برخورد کند اطلاعاتِ رویداد مربوط به به آنرا نیز همراه با خود به همراه می‌برد. به این ترتیب مسیری ایجاد می‌شود که منتهی به هر دو رویداد می‌باشد.

در شکل زیر زمانی که عاملی که در حال ایجاد مسیر منتهی به رویداد 2 است از روی مسیر منتهی به رویداد 1 عبور می‌کند، مسیری ایجاد می‌کند که منتهی به هر دو رویداد 1و2 می‌شود.

الگوریتم مسیر یابیِ شایعه‌ای  قسمت اول

درواقع تصویر فوق زمانی که عاملی که در حال پخش مسیری به سمت رویداد2 است از روی مسیر منتهی به رویداد 1 می‌گذرد، شروع به ایجاد مسیری می کند که منتهی به هر دو رویداد است.

عاملها همچنین مسیرهای بوجود آمده در شبکه را در صورتی که مسیر کوتاهتری پیدا کنند بهینه می‌کنند.

الگوریتم مسیر یابیِ شایعه‌ای  قسمت اول

الگوریتم مسیر یابیِ شایعه‌ای  قسمت اول

در شکل بالا به صورت مطلوب تر عامل تغییر مسیر وجود دارد ، زمانی که یک عامل نودی را پیدا می‌کند که طول مسیر منتهی به یک رویداد خاص در آن بزرگتر از چیزی باشد که در داخل عامل باشد جدول مسیریابی نود را با اطلاعات جدید خود بروز می‌کند. در ادامه به تشریح بیشتر این الگوریتم با جزئیات بیشتر خواهیم پرداخت.

زمانی که تعداد پرس و جوها در مقایسه با تعداد رویدادها کم باشد می‌توانیم برای پخش سریع ولی پر هزینه پرس‌وجوی خود در شبکه اقدام به پخش سیل‌آسای آن بکنیم. اگر N نود و Q عدد پرس‌وجو در شبکه داشته باشیم به تعداد N*Q ارسال در شبکه خواهیم داشت. این در حالی است که فرض کنیم هیچ تصادمی اتفاق نمی‌افتد. انرژی مصرف شده در این حالت مستقل از تعداد رویدادهای به وقوع پیوسته در شبکه است.

پخش سیل آسای اطلاعات رویدادها

زمانی که یک نود شاهد به وقوع پیوستن یک رویداد در شبکه است می‌تواند اطلاعات آنرا در شبکه به صورت سیل آسا منتشر کند. پخش سیل آسای هر رویداد حداقل به اندازه N ارسال بدنبال دارد. زمانی که پخش سیل آسای رویداد به اتمام رسید، پرس وجوها می‌توانند از کوتاهترین و قابل اطمینانترین مسیر به رویداد مورد نظر برسند.

بنابراین می توان از میزان مصرف انرژی توسط پرس‌وجوها برای رسیدن به رویداد از طریق این مسیر کوتاهِ ایجاد شده صرفنظر کرد و کل انرژی مصرف شده در حالت پخش سیل آسای E تعداد رویداد را برابر N*E در نظر گرفت.

این میزان مصرف انرژی مستقل از تعداد پرس‌وجوها می‌باشد. بنابراین زمانی که تعداد رویدادها در شبکه در مقایسه با تعداد پرس‌وجوها کمتر باشد پخش سیل آسای رویداد بهینه تر است.

در ادامه این پخش سعی می‌شود که حد آستانه‌ای برای روش مسیریابیِ شایعه‌ای در مقایسه با این دو مدل یافت شود.

الگوریتم مسیر یابیِ شایعه‌ای  قسمت اول

تصویر بالا نیز مقایسه پخش سیل آسای رویداد و پرس‌وجو با مسیریابی شایعه‌ای را نشان میدهد.

در بخش بعدی مقاله می پردازیم به :

پخش سیل آسای اطلاعات رویدادها

شرح الگوریتم

عاملهای رویداد و عامل‌های پرس‌وجو

و در نهایت شبیه سازی را مورد بررسی قرار می دهیم


نویسنده : فرهاد خانلری

منبع : انجمن تخصصی فناوری اطلاعات ایران

هرگونه نشر و کپی برداری بدون ذکر منبع و نام نویسنده دارای اشکال اخلاقی می باشد

#مسیر_یابی_شایعه‌ای #مسیر_یابی #الگوریتم_مسیر_یابیِ
عنوان
1 الگوریتم مسیریابی شایعه ای چیست ؟ معرفی Rumor Routing قسمت 1 رایگان
2 الگوریتم مسیریابی شایعه ای چیست ؟ معرفی Rumor Routing قسمت 2 رایگان
زمان و قیمت کل 0″ 0
0 نظر

هیچ نظری ارسال نشده است! اولین نظر برای این مطلب را شما ارسال کنید...

نظر شما
برای ارسال نظر باید وارد شوید.
از سرتاسر توسینسو
تنظیمات حریم خصوصی
تائید صرفنظر
×

تو می تونی بهترین نتیجه رو تضمینی با بهترین های ایران بدست بیاری ، پس مقایسه کن و بعد خرید کن : فقط توی جشنواره پاییزه می تونی امروز ارزونتر از فردا خرید کنی ....