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

و

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

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

در قسمت قبلی مقاله الگوریتم مسیر یابی شایعه ای در مورد مقدمات فهم الگوریتم و مسیر یابی و همچنین پخش سیل آسای اطلاعات رویدادها صحبت شد

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

شرح الگوریتم

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

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

با Itpro همراه ما باشید.

Rumor Routing Algorithm For Sensor Networks

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

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

شرح الگوریتم

شرح مختصر الگوریتم و در انتها به صورت شبه کد آمده است. هر نود در ابتدای کار شبکه لیستی از همسایگان خود را در خود ذخیره و نگهداری می‌کند. این کار به روشهای گوناگونی می‌تواند انجام شود. به عنوان مثال هر نو می تواند بسته‌ای را به همه همسایگان خود ارسال کرده و وجود خود را به آنها اعلام کند.

همچنین نودها می‌توانند با گوش دادن به پیامهای رسیده از وجود همسایگان خود مطلع شوند.

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

یک عامل بسته‌ای با طول عمر بالا است که در شبکه حرکت کرده و اطلاعات رویدادِ خاصی را در شبکه منتشر می‌کند. عاملها شامل یک جدول رویداد مشابه نودها در خود می‌باشند. این جدول در زمانی که عامل به یک نود جدید می‌رسد، خود را با جدول موجود در داخل نود همگام و یکسان می‌کنند. طول عمر عاملهای رویداد را با 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 رویداد در شبکه.


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

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

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

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

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

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

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