همانطور که در فصلهای پیش ذکر شد، مسیریابی چند مسیره به عنوان یک راهکار برای افزایش قابلیت اطمینان در شبکه های حسگر بیسیم استفاده می شود. با بهره گرفتن از مسیریابی چند مسیره، چندین کپی از یک بسته روی مسیرهای مختلف ارسال می شود. در صورتی که یک بسته در گرههای میانی حذف شود بسته در مقصد از مسیرهای دیگر قابل بازیابی است. تعیین تعداد مسیرها برای این راهکار خیلی مهم و حیاتی است، زیرا استفاده از مسیرهای بیشتر سربار زیادی را به شبکه تحمیل می کند و مصرف انرژی و طول عمر شبکه را نیز تحت تأثیر قرار میدهد. همچنین استفاده از مسیرهای کمتر ممکن است قابلیت اطمینان مورد انتظار را ارضا[۱۸۰] نکند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
معمولاً در فاز طراحی شبکه با توجه به قابلیت اطمینان مورد انتظار از شبکه، تعداد مسیرهایی که باید بستهها روی آن ارسال شوند تعیین میگردد. در شبکه های بیسیم احتمال موفقیت لینک در تحویل بستهها به گام بعدی به عوامل زیادی بستگی دارد که سبب می شود در زمانهای مختلف این مقدار تغییر کند. احتمال موفقیت لینک بر روی قابلیت اطمینان مسیرهایی که از این لینک استفاده می کنند. در نتیجه روی قابلیت اطمینان کل شبکه تأثیر می گذارد. کم یا زیاد شدن احتمال موفقیت لینکها، تعداد مسیرهای استفاده شده را تحت تأثیر قرار میدهد. تعداد مسیرهایی که استفاده می شود بر روی کارایی شبکه نیز موثر است. با کم شدن احتمال موفقیت لینک مسیرهای موجود ممکن است قابلیت اطمینان مورد انتظار را ارضا نکند و با زیاد شدن احتمال موفقیت لینک استفاده از مسیرهای موجود ممکن است سربار زیادی را به شبکه تحمیل کند.
همچنین در بعضی کاربردها قابلیت اطمینان مورد انتظار در زمانهای مختلف متفاوت است. در این مورد نیز با افزایش قابلیت اطمینان مورد انتظار، استفاده از مسیرهای موجود ممکن است قابلیت اطمینان مورد انتظار ارضا نشود یا با کاهش این مقدار، استفاده از مسیرهای موجود سربار زیادی را به شبکه تحمیل کند.
به طور مثال شبکه یک منبع و یک چاهک دارد که سه مسیر مستقل از منبع به چاهک برقرار است. قابلیت اطمینان این شبکه برای احتمالات متفاوت از موفقیت لینکها (احتمال همه لینکها برابر است) با توجه به تعداد مسیرهایی که استفاده می شود در شکل ۶-۲ نشان داده
شکل ۶‑۱: شبکه با سه مسیر مستقل از منبع به چاهک
شکل ۶‑۲ : قابلیت اطمینان مسیرهای مختلف برای توپولوژی شکل ۶-۱
شده است. محاسبات با بهره گرفتن از قوانین محاسبه قابلیت اطمینان با بهره گرفتن از فرمولهای سری و موازی بدست آمده است.
در شکل ۶-۲ مشخص است که برای قابلیت های اطمینان متفاوت، تعداد مسیر بهینه انتخاب شده متفاوت است. با توجه به شکل ۶-۲ فرض می شود قابلیت اطمینان مورد انتظار برابر ۹۰ درصد باشد و احتمال موفقیت لینکها نیز برابر ۹۰ درصد باشد. در اینجا مقدار بهینه برای تعداد مسیرهای استفاده شده ۲ میباشد. اگر از یک مسیر استفاده شود قابلیت اطمینان بدست آمده در حدود ۷۰ درصد است که قابلیت اطمینان مورد انتظار را ارضا نمیکند. همچنین اگر از ۳ مسیر استفاده شود قابلیت اطمینان بدست آمده در حدود ۹۸ درصد است. استفاده از ۳ مسیر قابلیت اطمینان را ارضا می کند ولی سربار بیشتری را به شبکه تحمیل می کند. نتایج بدست آمده در شکل ۶-۲ برای مسیرهایی با ۳ لینک با توجه به فرمولهای زیر بدست آمده است:
) ( ۶-۱
) ( ۶-۲
کهqi بیانگر قابلیت اطمینان لینک iام روی مسیر l میباشد، Rl بیانگر قابلیت اطمینان مسیر lام میباشد، p تعداد مسیرهای استفاده شده و R قابلیت اطمینان کل را نمایش میدهد؛ لذا یک مصالحه[۱۸۱] بین احتمال موفقیت لینکها و تعداد مسیرهای استفاده شده وجود دارد.
پروتکل چند مسیره تطبیقی پیشنهادی برای اقناع قابلیت اطمینان
همانطور که در بخش قبل توضیح داده شد وجود یک پروتکل که به صورت دینامیک مسیرها را برای منابع تعیین کند تا محدودیتهای لازم در شبکه اقناع شود امری ضروری است؛ لذا در این فصل یک پروتکل برای بر آورده کردن این نیازها پیشنهاد شده است که پروتکل چند مسیره تطبیقی برای اقناع قابلیت اطمینان[۱۸۲] (AMPRS) نامیده شده است. پروتکل AMPRSیک پروتکل تخصیص مسیر دینامیک در شبکه های حسگر بیسیم است که جهت تعیین تعداد مسیرهای استفاده شده توسط هر یک از منابع برای ارضای قابلیت اطمینان طراحی شده است.
در پروتکل AMPRS راهکارهایی به کار برده شده است که هم قابلیت اطمینان مورد انتظار برای شبکه ارضا شود و هم سربار ارسال بستهها زیاد نشود. همچنین مصرف انرژی کاهش و طول عمر شبکه افزایش یابد. در پروتکل AMPRS چاهک تصمیم میگیرد. هر منبع از چند مسیر و کدام مسیرها استفاده کند تا کارایی شبکه بالا رود. در پروتکل AMPRS با به کار بردن راهکار پیشنهاد شده در فصل قبل قابلیت اطمینان شبکه در چاهک تخمین زده می شود. چاهک بر اساس اطلاعاتی که در مورد گرهها، لینکها و مسیرهای در دسترس از شبکه دریافت می کند تصمیم گیریهای لازم را انجام میدهد. این اطلاعات شامل تعداد گام مسیرها، قابلیت اطمینان مسیرها، انرژی مسیرها، قابلیت اطمینان لینکها و پارامترهای دیگر میباشند. چاهک تعیین می کند که هر منبع از چند مسیر و چه مسیرهایی داده های خود را ارسال کند تا قابلیت اطمینان شبکه در یک دامنه حول و حوش قابلیت اطمینان مورد انتظار نگه داشته شود، همچنین سربار شبکه کم و طول عمر شبکه نیز ماکزیمم شود.
برای تخمین قابلیت اطمینان در چاهک از راهکار پیشنهاد شده در فصل قبل استفاده می شود. ساختار مسیریابی پروتکل پیشنهاد شده AMPRS مبتنی بر پروتکل پیشنهادی LOMDD است که در فصل ۴ تشریح شد. در LOMDD از یک مسیر به عنوان مسیر اصلی استفاده میشد و سایر مسیرها به عنوان جایگزین انتخاب میشوند. پروتکل AMPRS به منظور تعیین تعداد مسیرها برای هر یک از منابع طراحی می شود. چاهک بر اساس اطلاعاتی که در دوره های زمانی از شبکه بدست می آورد تصمیم میگیرد که هر یک از منابع از چه مسیرهایی و چند مسیر برای ارسال اطلاعات استفاده کنند. در ادامه ابتدا یکسری از ویژگیهای و پیش فرضها را برای AMPRS بیان میکنیم سپس نحوه عملکرد آن را تشریح میکنیم.
تنظیمات اولیه
بعد از مسیریابی که مبتنی بر پروتکل پیشنهاد شده LOMDD است برای هر یک از منابع یک مسیر تنظیم می شود که منبع داده های خود را بر روی آن ارسال می کند. چاهک از حضور هر یک از منابعی که داده ارسال می کند با خبر است و اطلاعات هر منبع را در یک جدول به نام Info-Source در حافظه خود نگهداری می کند. با تشکیل هر مسیر اطلاعات مربوط به این مسیر در جدول ذخیره می شود. به طور کل میتوان گفت چاهک یک دید کلی نسبت به منابع و مسیرهای تنظیم شده برای آنها و همچنین ویژگیهای این مسیرها دارد. این اطلاعات برای تصمیم گیری چاهک در مورد انتخاب مسیرها و نحوه توزیع بار در شبکه لازم میباشد.
برای هر منبع یک مدخل در جدول Info-Source ایجاد میگردد که اطلاعاتی از قبیل:
شماره شناسایی[۱۸۳] منبع
مسیرهای موجود برای منبع
تعداد گامها از منبع تا چاهک برای هر مسیر
مینیمم انرژی باقی مانده روی هر مسیر
لینکهای روی هر مسیر
احتمال موفقیت لینکها
قابلیت اطمینان هر یک از مسیرها
تعداد بستههای ارسالی از منبع تا زمان جاری
تعداد بستههای دریافتی از منبع تا زمان جاری توسط چاهک
وضعیت هر یک از مسیرها که آیا فعال است یا غیر فعال (داده روی آن انتقال داده می شود یا خیر)
و دیگر پارامترها
در آنها وجود دارد. همچنین برای آزمایش زنده بودن مسیرها از روش انتها به انتها که در فصل ۴ تشریح شد استفاده میشود.
تعاریف
همانطور که در بخشهای قبل گفته شد در ابتدا هر منبع تنها از یک مسیر استفاده می کند. مدت زمان اولیهای که منابع از همین یک مسیر استفاده می کنند تا شبکه به پایداری لازم برسد و اطلاعات منابع، مسیرها و لینکها در چاهک ایجاد و بروز رسانی شود، دوره پایداری شبکه نامیده می شود. بعد از اتمام این دوره چاهک در مورد مسیرها تصمیم گیری لازم را انجام میدهد و دستورات لازم را به شبکه القا می کند. بعد از این دوره چاهک وضعیت شبکه را در فواصل زمانی منظم بر طبق الگوریتمی که در ادامه تشریح می شود بررسی می کند و تصمیم گیریهای لازم را برای ارضا شدن محدودیتها میگیرد. به این دوره های منظم دوره تصمیم گیری چاهک میگوییم.
اطلاعاتی که در بالا ذکر شد میتواند از طریق بستههای داده و بستههای چک کردن مسیر برای چاهک ارسال شوند. در واقع این اطلاعات بر روی این بستهها سواری مجانی[۱۸۴] می کنند. همچنین یک نوع دیگری از بسته به نام Info-link نیز برای انتقال این اطلاعات طراحی شده است که می تواند استفاده شود. این بسته در یک دوره زمانی خاص اطلاعات را به چاهک ارسال می کند. چاهک با دریافت این بسته اطلاعات مربوط به هر یک از منبعها، مسیرها و لینکها را بروز رسانی می کند. همانطور که گفته شد در این پروتکل از سواری مجانی استفاده می شود.
این پروتکل برای محاسبه انرژی مسیرها از عبور لایهای[۱۸۵] استفاده می کند. در واقع از اطلاعاتی که از لایه پایین بازخورد[۱۸۶] می شود، استفاده می کند. لایه MAC اطلاعات انرژی را برای لایه های بالاتر فراهم می کند. گرههای میانی با دریافت هر بسته، در لایه MAC قبل از اینکه بسته را ارسال کنند، مقدار فیلد انرژی را در بسته مورد نظر بررسی می کنند. در صورتی که مقدار این فیلد بیشتر از مقدار انرژی باقی مانده این گره باشد، مقدار این فیلد با مقدار انرژی باقیمانده این گره بروز رسانی می شود. در غیر این صورت بدون تغییر باقی میماند. در نتیجه هنگامی که چاهک این بسته را دریافت می کند مقدار فیلد انرژی برابر حداقل انرژی باقیمانده روی مسیر میباشد که در معادله ۶-۳ نشان داده شده است.
= min () ) ( 6-3
Ei بیانگر انرژی مسیر iام است و ERn,i بیانگر مقدار انرژی باقیمانده از گره nام روی مسیر iام میباشد.
در منبع مقدار فیلد قابلیت اطمینان با مقدار احتمال موفقیت لینکهایی که بسته بر روی آن ارسال می شود تنظیم میگردد. با دریافت بسته در گرههای میانی مقدار فیلد قابلیت اطمینان در احتمال موفقیت لینک جاری ضرب می شود و حاصل در فیلد مورد انتظار قرار میگیرد. هنگامی که چاهک بسته را دریافت می کند مقدار فیلد قابلیت اطمینان برابر حاصل ضرب احتمال موفقیت لینکهای روی مسیر میباشد. نحوه محاسبه قابلیت اطمینان در معادله ۶-۴ نشان داده شده است.
) ( ۶-۴
بیانگر قابلیت اطمینان مسیر i ام است و بیانگر احتمال موفقیت لینک jام میباشد.
نحوه تصمیم گیری چاهک
در هر دوره تصمیم گیری چاهک، چاهک قابلیت اطمینان کل شبکه را بررسی میکند. در صورتی که قابلیت اطمینان بدست آمده در محدوده قابلیت اطمینان مورد انتظار نباشد، با اضافه و یا کم کردن مسیرها قابلیت اطمینان مورد نظر را با بهره گرفتن از الگوریتمی که در بخش قبل پیشنهاد شد تخمین میزند و تعیین می کند که چه مسیرهایی به هر یک از منابع اضافه یا کم شود تا قابلیت اطمینان مورد انتظار ارضاء شود. با این کار چاهک هم محدودیتهای لازم را ارضا می کند و هم باعث می شود سربار تحمیل شده به شبکه کم شود. در این پروتکل همواره سعی بر این است که قابلیت اطمینان همواره در حول و حوش قابلیت اطمینان مورد انتظار نگه داشته شود. برای این منظور از یک کران استفاده میکنیم که آن را مینامیم. اگر قابلیت اطمینان مورد انتظار را بنامیم و قابلیت اطمینان بدست آمده از شبکه را R بنامیم همواره سعی می شود نامعادله ۶-۵ حفظ شود.
+ (۶-۵)
هنگامی که چاهک تعیین کرد که چه مسیرهایی باید به جریان انتقال اضافه و یا کم شوند این اطلاعات از طریق یک بسته Ack-live-path در طول مسیر عقبگرد برای منبع مورد نظر ارسال می شود و اطلاعات مربوط به این مسیر در جدول Info-Source بروز رسانی می شود. قابل ذکر است که بستههای از نوع Ack–live-path برای تصدیق زنده ماندن مسیرها توسط چاهک در پاسخ به درخواست منابع ارسال می شود که جزئیات آن در فصل ۴ تشریح شد. اطلاعات لازم برای اضافه یا حذف مسیر مورد نظر روی این بستهها سواری مجانی می شود. این عملیات در هر دوره تصمیم گیری تکرار می شود. مراحل الگوریتم تصمیم گیری چاهک در زیر گام به گام بیان می شود:
گام ۱. در ابتدا برای هر یک از منابع یک مسیر تنظیم می شود، و یک تایمر t برای آن برابر با مدت زمان دوره پایداری شبکه تنظیم می شود.
گام ۲. چاهک منتظر می شود تا t=0 شود. هرگاه t=0 شد به گام بعد میرود.
گام ۳. چاهک قابلیت اطمینان شبکه در دوره قبلی تصمیم گیری چاهک را محاسبه می کند. قابلیت اطمینان به صورت نسبت بستههای دریافتی به ارسالی که توسط همه منابع ارسال می شود محاسبه میگردد، سپس به گام ۵ میرود.
گام ۴. قابلیت اطمینان با بهره گرفتن از راهکار پیشنهاد شده در فصل قبل برای مسیرهای فعال تخمین زده می شود سپس به گام بعد میرود.
گام ۵. اگر قابلیت اطمینان بدست آمده کوچکتر از باشد چاهک در میان مسیرهایی که غیر فعال هستند جستجو می کند و بهترین مسیر را انتخاب می کند (نحوه انتخاب بهترین مسیر در ادامه بیان می شود). یک بسته از نوع Ack-live-path که فیلد مربوط به فعال بودن مسیر برای آن ۱ تنظیم –شود؛ در مسیر عقبگرد برای منبع مورد نظر ارسال می کند. منبع با دریافت این بسته مسیر مورد نظر را فعال می کند و از این به بعد یک نسخه از بستهها را روی این مسیر نیز ارسال می کند. سپس به گام ۴ میرود. در این مرحله اگر هیچ مسیری پیدا نشود نشان دهنده این است که همه مسیرهای موجود فعال هستند و با وجود این مسیرها قابلیت اطمینان مورد انتظار نمیتواند ارضا شود؛ در این حالت به گام ۸ میرود.
گام ۶. اگر قابلیت اطمینان بدست آمده بزرگتر از مقدار + باشد چاهک در میان مسیرهایی که فعال هستند مسیری که کمترین تأثیر را در قابلیت اطمینان دارد انتخاب می کند در واقع بدترین مسیر را انتخاب می کند. مسیر انتخاب شده را به صورت موقت غیرفعال در نظر گرفته می شود. قابلیت اطمینان با توجه به راهکار پیشنهاد شده در بخش قبل برای مسیرهای فعال موجود تخمین زده می شود، که در اینجا دو حالت پیش می آید:
اگر مقدار بدست آمده از کوچکتر باشد، مسیر مجدداً فعال می شود و به گام ۸ میرود. این امر نشان دهنده این است که با شرایط موجود حداقل قابلیت اطمینانی که بدست آمده نمیتواند کمتر از این مقدار باشد.
در غیر این صورت یک بسته از نوع Ack- live-path برای منبع مربوطه در مسیر عقبگرد ارسال می شود که در فیلد مربوط به فعال بودن مسیر مقدار ۱ تنظیم می شود. منبع با دریافت این بسته و بررسی آن متوجه می شود که باید بستههای داده را روی این مسیر ارسال نکند و چاهک نیز جدول Info-Source خود را بروزرسانی می کند. سپس به گام ۴ میرود.
در این مرحله اگر هیچ مسیری بدست نیاید نشان دهنده این است که قابلیت اطمینان از این کمتر نمیتواند باشد و به گام ۸ میرود.
گام ۷. اگر قابلیت اطمینان محاسبه شده کوچکتر از و بزرگتر از + باشد، بیانگر این که قابلیت اطمینان شبکه در دامنه مورد نظر است و نیاز به هیچگونه تغییری نیست. به گام ۸ می رود.
[پنجشنبه 1400-09-11] [ 03:49:00 ب.ظ ]
|