بخشی از مقاله
*** اين فايل شامل تعدادي فرمول مي باشد و در سايت قابل نمايش نيست ***
پروتکل مسیریابی چند پخشی برای شبکه های موردی سیار
چکیده:
در این مقاله بر روی یک موضوع مهم در شبکه های موردی ستار، که مسیریابی چندپخشی است، متمرکز شده و یک پروتکل مسیریابی چندپخشی بنا به درخواست توری را پیشنهاد داده ایم که کیفیت سرویس را نیز از لحاظ رزرو پهنای باند و کاهش تأخیر بسته ها پشتیبانی می کند. طرح پیشنهادی دارای چهار ویژگی زیر است: الف)۔ مبتنی بر گروه جلوبرنده است ( بدین معنی که تنها زیر مجموعه ای از گره ها مسئول جلو راندن بسته های چندپخشی هستند)؛ ب)- اعضای گروه جلوبرنده بصورت پویا و بکمک روالی مشابه مسیریابی بنابه درخواست، تجدید می شوند؛ ج)- پروتکل پیشنهادی بطور قابل توجهی سربار کنترلی را کاهش داده و از طریق ادغام بسته های کنترلی منجربه توسعه پذیری پروتکل مسیریابی چندپخشی می شود؛ د)- با تخمین تقریبی پهنای باند مورد نیاز و پهنای باند موجود در مسیرهای فعال انتها به انتها، از مسیریابی کیفیت سرویس نیز پشتیبانی می کند.
واژه های کلیدی: مسیریابی چندپخشی، پهنای باند، کیفیت سرویس.
1- مقدمه
شبکه های موردی سیار مجموعه ای از میزبانهای سیار هستند که بدون استفاده از زیرساخت از پیش برپا شده ای عمل می کنند. ارتباطات میان میزبانهای سیار از طریق اتصالهای بی سیم و بواسطه آنتنهای آنها صورت می پذیرد. بعلت مسائلی چون محدودیت توان رادیویی، ممکن است یک میزبان سیار قادر به ارتباط مستقیم و تک گامه با سایر میزبانها نباشد. در این شرایط بسته های ارسالی توسط میزبان مبدأ، قبل از رسیدن به میزبان مقصد، توسط چند میزبان میانی تقویت می شوند. از اینرو در یک شبکه موردی می بایست هر میزبان سيار بعنوان یک مسیریاب نیز فعالیت کند [1]. هدف شبکه های سیار موردی، توسعه قابلیت حرکت در حوزه های بی سیم سیار خودمختار است، که مجموعه ای از گرهها بصورت آنی، زیرساخت ارتباطی شبکه را شکل می دهند. اکثر کاربردهای مربوط به فن آوری شبکه های موردی سیار، در حوزه هایی است که نیازمند برپایی سریع و پیکربندی مجدد پویا بوده، همچنین شبکه های سیمی در دسترس نباشند [2]. این کاربردها شامل میادین جنگ، عملیات امداد و نجات، کلاسهای درس و انجمنهایی که شرکت کنندگان اطلاعاتشان را بوسیله دستگاههای سیارشان بصورت پویا به اشتراک می گذارند.
بعلاوه در رسانه های بی سیم کاهش سربار ارسال و توان مصرفی بسیار حایز اهمیت است. چندپخشی قادر است کارایی اتصال بی سیم را هنگام ارسال چندین رونوشت از پیغامها، با بهره گیری از ویژگی همه پخشی انتقال بی سیم، بهبود دهد. با اینحال چند پخشی در شبکه های سیار بی سیم با چالشهای متعددی مواجه است [3]. چند پخشی عبارت است از ارسال بسته های داده به گروهی متشکل از صفر یا چند میزبان که با آدرس مقصد یکسان شناسایی می شوند. معمولا قابلیت اطمینان تحویل یک بسته داده ای چندپخشی به گره مقصد، با بسته داده ای تک پخشی، یکسان است [4]. بعنوان مثال در مورد IP تحویل بی نقص بسته های داده ای و با همان ترتیب ارسال هرگز تضمین نمی شود.
چندپخشی در راستای نیل به محاسبات گروه گرا گام بر می دارد. کاربردهای بسیار زیادی وجود دارند که مستلزم ارسال یک به چند هستند. سرویس چند پخشی در کاربردهایی که همکاری نزدیک تیمی را می طلبند بسیار مهم است [3]. مسیریابی کیفیت سرویس از جمله موضوعات مهم دیگری است که در شبکه های موردی بی سیم مطرح است. کیفیت سرویس معرف مشخصه های غیر تابعی یک سیستم است که در کیفیت نتایج حاصله موثر هستند. در کاربردهای چندرسانه ای این مشخصه ها ممکن است شامل کیفیت تصویر، تأخیر و سرعت پاسخ باشند. از دیدگاه فنی مشخصه های کیفیت سرویس می تواند شامل خطوط زمانی ( مانند تأخیر و زمان پاسخ) پهنای باند ( مانند پهنای باند مورد نیاز و پهنای باند موجود و قابلیت اطمینان ( مانند زمان کارکرد عادی بین زمانهای خرابی، از زمان خرابی تا شروع مجدد فعالیت عادی) باشد [5] | هدف از تضمین کیفیت سرویس یافتن مسیری است که قیدهای کیفیت سرویس مورد نیاز برنامه های کاربردی را برآورده سازد. فراهم کردن کیفیت سرویس در یک شبکه موردی سیار، بعلت ذات پویا و همه پخشی بودن شبکه دشوار است. اول اینکه بر خلاف شبکه های سیمی ممکن است پهنای باند یک اتصال بی سیم تحت تأثیر ارسال گره های همسایه اش واقع شود. دوم اینکه برخلاف شبکه های سلولی، که تنها لازم است کیفیت سرویس برای یک گام تضمین شود، در شبکه های موردی سیار باید برای چندین گام در طول مسیر تضمین شود. سوم اینکه ممکن است با حرکت گره های بسیار، گره های جدیدی در هر زمان و هر مکانی عضو گروه شوند، گروه را ترک کنند، مجددا عضو گروه شوند، اتصالهای موجود از بین بروند و اتصالهای جدید شکل بگیرند. ادامه مقاله بشکل زیر سازماندهی شده؛
بخش 2 در باره کارهای مرتبط است،
بخش 3 کنترل پذیرش و تخمین پهنای باند آزاد و مصرفی را مورد بررسی قرار می دهد. انگیزه کار و طرح پیشنهادی در
بخش 4 ارائه شده، در این بخش طرح جدیدمان که در باره طراحی یک پروتکل مسیریابی چندپخشی آگاه به کیفیت سرویس است، بررسی می شود.
نتایج شبیه سازی در بخش 5
و نتیجه گیری در بخش 6 ارائه شده اند.
2- کارهای مرتبط پروتکلهای مسیریابی چندپخشی متعددی برای شبکه های موردی بی سیم طراحی شده اند مانند CAMP ،[10] ODMRP ،[4] MAODV [11] و COMP [7]. با اینحال این پروتکلها به جنبه فراهم کردن کیفیت سرویس در ارتباطات شبکه موردی نپرداخته اند. تنها پروتکلهای اندکی از قبیل QAMNET ،[12] LR-ODMRP [13] و -Lantern tree [14] کیفیت سرویس در چندپخشی را حمایت می کنند. LR-ODMRP بمنظور جلوگیری از افزایش بار گره های میانی و در نتیجه رد درخواستهای ارسال کننده گان جدید، بعلت نبودن پهنای باند آزاد، از کنترل پذیرش استفاده می کند. وقتی یک گره میانی درخواست مسیر کیفیت سرویس را دریافت می کند، درحالی که پهنای باند آزاد کافی دارد، آن درخواست را پذیرفته و پهنای باند معینی را به آن جریان تخصیص می دهد. وقتی همان گره میانی پس از مدتی بسته پاسخ همان درخواست را دریافت کرد وضعیت پهنای باندی را که قبلا کشف شده درج شده بود به ثبت شده تغییر می دهد. پهنای باند تخصیص داده شده برای مدت زمان مشخصی در وضعیت ثبت شده باقی می ماند و در صورت عدم دریافت بسته های داده، حذف می شود. اگر گره میانی درخواست مسیر کیفیت سرویس دریافت کند در حالی که پهنای باند موجود کافی ندارد، درخواست را رد می کند. با اینحال پروتکل -LR ODMRP توجه کافی به این حقیقت نداشته که هنگام کنترل پذیرش نه تنها باید گره میانی منابع محلی را در نظر بگیرد، بلکه منابعی را که تمامی گره های موجود در حوزه ارسال او بوده و در حال رقابتند نیز باید در محاسبه پهنای باند آزاد در نظر گرفت. پروتکل QAMNET نسخه توسعه یافته پروتکل ODMRP بوده و بمنظور فراهم کردن کیفیت سرویس موارد زیر را به پروتکل ODMRP افزوده است؛
الف) اولویت دهی ترافیک
ب) کاوش منابع توزیع شده
ج) مکانیزم کنترل پذیرش.
این پروتکل برای تخمین پهنای باند آزاد از روش مشابه روش استفاده شده در پروتکل SWAN [17] بهره می گیرد که در آن نرخ آستانه جریانهای بلادرنگ، محاسبه شده و پهنای باند آزاد بعنوان مقداری بین نرخ آستانه ترافیک بلادرنگ و نرخ فعلی ترافیک بلادرنگ تخمین زده می شود. از آنجایی که ممکن است بسته به الگوی ترافیک نرخ آستانه بطور پویا تغییر کند تخمین دقیق آن دشوار است
[17]. مقدار نرخ آستانه باید بصورت معقول انتخاب شود زیرا انتخاب یک مقدار بسیار بزرگ باشد منجر به کارایی ضعیف جریانهای بلادرنگ شده و انتخاب یک مقدار کوچک منجر به عدم پذیرش جریانهایی می شود که منابع موجود برای آنها کافی بودند.
توپولوژی Lantern-tree [14] بمنظور فراهم کردن مسیریابی چندپخشی کیفیت سرویس استفاده می شود. این پروتکل در لایه کنترل دسترسی به رسانه خود از پروتکل CDMA over TDMA برای به اشتراک گذاری واحدهای زمانی بهره می گیرد. در این مدل پهنای باند موجود برحسب تعداد واحدهای زمانی آزاد سنجیده می شود. -Lantern tree از زمان شروع برای پیدا کردن تمامی مسیرها، به اشتراک گذاری واحدهای زمانی بین تمامی گره های همسایه و یافتن زمانبندی مناسب واحدهای زمانی آزاد، زمان زیادی تلف می کند. مدل CDMA/TDMA بیشتر در شبکه هایی استفاده می شود که تغییرات مکرر توپولوژی ندارند.
3- کنترل پذیرش و تخمین پهنای باند لایه MAC مربوط به استاندارد 802.11 IEEE مبتنی بر رسانه مشترک و رقابت گره هاست. بنابراین پذیرش جریان(های) ترافیکی در یک گره خاص در پهنای باند موجود تمامی گره های مجاورش موثر خواهد بود. بعلاوه از آنجا که گره ها ارسال و دریافت DATA را روی یک کانال منفرد انجام می دهند، تحویل یک جریان ترافیکی تکی مستلزم رقابت برای کانال در بین گره ها خواهد بود. در نتیجه گره های مختلف ( گره مبدأ یا ارسال کننده، گره مقصد یا دریافت کننده، گره های میانی و گره های مجاور گره های موجود در مسیر انتها به انتها ) ممکن است مقدار متفاوتی از پهنای باند را برای ارسال یک جریان ترافیکی مشخص مصرف کنند. در پروتکلهای مسیریابی پشتیبانی کننده از کیفیت سرویس برای شبکه های موردی سیار، از قبیل WMP ،[19] AQOR [20] و QoS ODMRP [21] پهنای باند خام در لایه فیزیکی بعنوان حداکثر پهنای باند در محاسبات مربوط به پهنای باند موجود هر گره استفاده شده که روش دقیقی برای محاسبه پهنای باند موجود نخواهد بود[18]. همانطور که اشاره شد بعلت استفاده از رسانه مشترک گره ها نمی توانند بصورت همزمان ارسال و دریافت داده داشته باشند. بنابراین هر دو عملیات ارسال و دریافت، پهنای باند گره ها را مصرف خواهد کرد. بعبارت دیگر برای ارسال هر بسته در یک گام، پهنای باند یکسانی در ارسال کننده و دریافت کننده مصرف خواهد شد. بعلاوه پهنای باند یکسانی در تمامی گره های مجاور گره ارسال کننده مصرف خواهد شد هر چند که آنها گره های مقصد بسته نباشند زیرا نباید قادر به استفاده از دوره زمانی دریافت یا ارسال سایر گره ها باشند. اگر همان بسته در طول چندین گام ارسال می شد، برای زوج ارسال کننده دریافت کننده در هر گام، مقدار پهنای باند یکسانی مصرف می شد. بعلاوه، گره های تبعیت کننده از استاندارد 802.11 قادر به ارسال و دریافت بسته در یک زمان نیستند. بنابراین مصرف پهنای باند در هر گره میانی، جمع شونده است، زیرا آن گره باید بعنوان دریافت کننده در گام بسمت گره مبدأ، و ارسال کننده در گام بسمت گره مقصد و در صورت وجود گره بعدی، بعنوان گره مجاور در گام بعدی بسمت گره مقصد باشد.
ترافیک یکطرفه بین دو گره را نشان می دهد. برای برقراری یک جریان بین دو گره، تنها نیاز ما پهنای باند گره های موجود در مسیر انتها به انتها نخواهد بود بلکه به پهنای باند تمامی گره های همسایه در طول مسیر نیز نیاز خواهیم داشت. هر چند از دیدگاه تئوری گره های موجود در شبکه که چندین گام از مسیر فاصله دارند، بصورت زنجیره ای تحت تاثیر واقع شده و این موضوع مساله کنترل پذیرش را به یک مساله NP-hard تبدیل می کند [18].
علائم استفاده شده در این بخش عبارتنداز:
گره مبدأ
گره های میانی، به استثنای گره ای که در گام آخر قرار دارد.
گره میانی واقع در گام آخر مسير .
D گره مقصد
N گره های مجاور هر گره واقع در مسیر انتها به انتها (یعنی آن گره ای که تحت پوشش حوزه همه پخشی گره های I ،1 ،S و D قرار دارند). گره ای که خود جزو مسیر است شامل نماد N نخواهد شد.
KN: با فرض یک گره مجاور N از یک مسیر انتها به انتها، تعداد همسایه ها در مسیر را KN در نظر می گیریم. Breq.j: پهنای باند در خواستی توسط جریان.
j Bres,i: پهنای باند رزرو شده کلی در گره
i Bava,i: پهنای باند موجود تخمینی در گره
در صد زمانی که صف لایه MAC در گره I( صف غیر تهی یا کانال اشغال ) در یک دوره ارزیابی اشغال است.
PL: طول payload لايه MAC ( طول بسته لایه بالایی ) در دوره ارزیابی
در استاندارد نمی توان پهنای باند موجود را بطور مستقیم از توان کلی حاصل شده تخمین زد، زیرا؛
الف)- حداکثر توان ( یا گذردهی اشباع ) برای یک نرخ داده مفروض ثابت نیست. گذردهی اشباع تحت تاثیر طول متوسط بسته ها و گره هاییست که بطور فعال در حال رقابت هستند.
ب) - نرخ داده پیوندها نیز بدلیل پشتیبانی از چند نرخی، یکسان نیست. مرجع [18] گذردهی اشباع و پهنای باند موجود در هر گره را بصورتی که در ادامه بیان می کنیم تخمین می زند. تخمین گذردهی اشباع در گره I بصورت حداکثر گذردهی تجمعی که می تواند توسط گره 1 تحت شرایط فعلی شبکه حاصل شود تعریف می شود. Bsat, I در هر دوره زمانی Thello به روز می شود. فرمول (1) قادر است بر اساس شرایط فعلی غیر اشباع شبکه، گذردهی اشباع را تخمین بزند، و این امر برای کنترل پذیرش در شبکه ای که نباید اشباع در آن رخ بدهد بسیار مفید خواهد بود [18].
مدت زمان در واقع شامل زمان انتظار یک گره برای دسترسی به کانال، زمان ، زمان ارسال بسته های RTS/CTS و زمان ارسال DATA/ACK می باشد. اگر برخوردی رخ دهد افزایش می یابد، زیرا باید زمانی اضافی برای چندین ارسال مجدد قبل از تحویل موفقیت آمیز بسته انجام شود. Bsat, I تحت تاثیر چندین عامل است، از قبیل اندازه بسته، میزان رقابت ترافیک و نرخ تلفات کانال در نهایت، Bsat, I بصورت میانگین تمامی بسته ها در مدت زمان Thello محاسبه می شود که اثر آن متوسط شدن گذردهی های همه واسطهای شبکه به عدد بسته های ارسالی بر روی این پیوندهاست. اگر در آخرین ثانیه هیچ بسته ای ارسال نشده باشد، از آخرین Bsat,I استفاده می کنیم. Thello و مقدار آغازین Bsat, I درست پس از راه اندازی مجدد می تواند توسط اپراتور شبکه برای گره های شبکه بصورت دسته جمعی ویا تکی تنظیم شود. با این وجود برای جلوگیری از نوسان مکرر یا غیر دقیق بودن Bsat, I شرایط فعلی، باید مقدار Thello با دقت بیشتری انتخاب شود.
ما می توانیم پهنای باند موجود کانال ( Bava,I ) را بر اساس Bsat, I و با در نظر گرفتن زمان اشغال بودن کانال بدست آوریم. بعبارت دیگر باید Bava, I پهنای باند قابل تخصیص باقیمانده برای یک گره باشد. GI را درصد زمانی در نظر می گیریم که گره ا در وضعیت اشغال است. GI منعکس کننده بخشی از زمان است که یک گره در آن زمان کاری برای انجام دادن دارد. از طرف دیگر( ai-1) بیانگر بخشی زمان است که طی آن گره کاملا بی کار است و همچنین نشان می دهد که توان بالقوه آن گره برای پذیرش درخواستهای ترافیکی جدید چقدر است. برای تصمیم گیری در مورد مقدار واقعی Bava,J از ترکیب ( ai-1) و Bsat, I در قالب فرمول زیر استفاده می کنیم:
QI و Bsat, I هر دو پارامترهای گذرا بوده و ممکن است نوسانی در مقادیر آنها رخ دهد. برای کاهش احتمال افزایش بار سنگین در شبکه بعلت پذیرش تصادفی ترافیک جدید با مقدار بالای گذرای Bsat, I × ( di-1 )، معيار اضافی ( Bsat, I - Bres,I ) در فرمول لحاظ کرده ایم. بر اساس فرمول (2)، پهنای باند موجود برای پذیرش درخواست ترافیکی جدید، Bava,I حداقل مقدار بین ai ) Bsat, I-1) و ( Bsat, I - Bres,I ) است. فقط در صورتی که پهنای باند مورد نیاز جریان جدید ز، Breq,j ، کمتر از Bava,J باشد ورود جریان ترافیکی جدید به شبکه پذیرفته خواهد شد.
4- طرح پیشنهادی
1-4 انگیزه طرح ODMRP
حتی در تحرک بالا، نرخ تحویل بسته بالایی فراهم می کند، اما به قیمت سربار کنترلی سنگین. این پروتکل نمی تواند به نسبت افزایش تعداد ارسال کننده گان در شبکه و افزایش بار ترافیکی، توسعه و گسترش یابد. از آنجا که هر گره بصورت دوره ای بسته های اعلان RREQ را بصورت سیل آسا در کل شبکه منتشر می کنند، در صورتی که تعداد ارسال کننده گان زیاد باشد، احتمال وقوع ازدحام بالا است [7] بنابر این سربار کنترلی یکی از نقاط ضعف پروتکل ODMRP تحت حضور چندین گره مبدأ است. پروتکل پیشنهادی علاوه بر کاهش سربار بسته های کنترلی، مکانیزم کنترل پذیرش و رزرو پهنای باند در گره های فعال موجود در مسير قادر است تا حدی کیفیت سرویس را از لحاظ تأخیر و پهنای باند برآورده سازد. بمنظور کاهش سربار ناشی از بسته های کنترلی طی کشف مسیر و اعمال کنترل پذیرش به ترافیک شبکه، طرح پیشنهادی دو مکانیزم بهینه سازی کارآمد را استفاده می کند. اولی در گره هایی اعمال می شود که قادر به فراهم کردن نیازهای کیفیت سرویس نیستند، از اینرو بسته RREQ دریافتی را نادیده می گیرند و دیگری در مورد تمامی گره های میانیست و بر اساس مقايسه پهنای باند آزاد آن گره و پهنای باند مورد نیاز با توجه به موقعیت گره و نقش گره های همسایه ( ارسال کننده، میانی، دریافت کننده و ...) انجام می شود. برای کاهش سربار بسته های کنترلی از ایده ای مشابه ایده طرح موسوم به COMP استفاده کرده ایم به این ترتیب که تحت شرایطی چندین بسته RREQ را در قالب یک بسته RREQ ادغام کرده و ارسال می کنیم. در بخشهای آتی به جزئیات این موضوع خواهیم پرداخت.
2-4 کنترل پذیرش و تخمین پهنای باند در پروتکل
پیشنهادی در پروتکلهای تک پخشی هر گره تنها یک گره پایین دست و یک گره بالادست دارد، بنابراین رابطه ای که در شکل 2 به نمایش درآمد نمی تواند رابطه ای دقیق در پروتکلهای چندپخشی باشد، زیرا در این پروتکلها بر خلاف پرتکلهای تک پخشی، ممکن است هر گره بیش از یک همسایه جلو راننده داشته باشد. در اینجا برای محاسبه پهنای باند مورد نیاز در یک گره میانی فرمول زیر را برای پروتکلهای چند پخشی پیشنهاد می کنیم
در رابطه 3، K بیانگر تعداد گره های همسایه گره ۱ بوده و بعنوان گره ارسال کننده فعالیت می کنند اما عضو هیچ گروه جلوبرنده ای نیستند. هر گره ای که در مسیر بین ارسال کننده و دریافت کننده (گان) است می بایست پهنای باندی به اندازه Required BW برای هر جلسه خاص رزرو کند. از آنجا که گره فعلی نباید هنگام ارسال گره های ارسال کننده یا جلوراننده مجاور ارسال کند و علاوه بر این خود گره فعلی برای ارسال نیازمند حداقل پهنای باند Breq است، ما ضریب (1+n) را به حداقل پهنای باند در خواستی جریان، برای محاسبه پهنای باند مورد نیاز تقریبی در گره میانی اعمال می کنیم. هنگام اتخاذ تصمیم کنترل پذیرش در یک گره میانی نه تنها پهنای باند مورد نیاز در آن گره بلکه پهنای باند آزاد گره های مجاور آن گره نیز باید مد نظر قرار گیرد زیرا همانگونه که اشاره کردیم پذیرش ترافیک در گره های همسایه گره میانی در کاهش پهنای باند آزاد گره میانی موثر خواهد بود. بنابراین یک مرحله از کنترل پذیرش در گره فعال موجود در مسیر طی فرآیند مسیریابی، بررسی پهنای باند آزاد همسایگان موجود در یک گامی آن گره است
