بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه یک سیاست مدیریت بافر مبتنی بر اولویت برای شبکه های بیسیم تحمل پذیر تأخیر
خلاصه
در این مقاله ما بر روی مسئله بهینهسازی مدیریت بافرگرهها در زمان پر بودن بافر، در شبکههای مقاوم به تاخیر(( DTN [1]، تمرکز میکنیم. الگوریتم استفاده شده در این تحقیق، الگوریتم Prophet میباشد. سیاست مورد استفاده در این الگوریتم برای کنار گذاشتن بستهها از بافر، تکنیک droptail است. روش پیشنهادی ما در این مقاله، دارای یک تابع اولویت با استفاده از پارامترهای مهم و تاثیرگذار هر بسته میباشد. با استفاده از این تابع اولویت برای هر بسته یک درجه اولویت تعیین میگردد. به هنگام پر بودن بافر، بستههایی با کمترین درجه اولویت از بافر حذف میشوند و فضا برای دریافت بستههای جدید فراهم میشود. پس از شبیهسازی روش پیشنهادی، معیارهای کارایی (نرخ تحویل بستهها و میزان drop بستهها) آن را با روشهای قبلی[2] مقایسه کردیم. نتایج حاصل از این شبیهسازی نشان داد که معیارهای کارایی روش پیشنهادی نسبت به روشهای قبلی بهبود یافته است.
کلمات کلیدی : شبکههای بیسیم، شبکههای تحملپذیر تاخیر، مدیریت بهینه بافر گره، نرخ تحویل بسته
.1مقدمه
در شبکههای DTN هر گره شامل تعدادی بسته میباشد. زمانی که دو گره با یکدیگر رویارو میشوند بستههای خود را با یکدیگر تبادل میکنند. هر بسته در گره شامل لیستی از ID گرههایی است که در طول مسیرش مشاهده کرده است. اگر بدانیم که یک بسته تا به الان از چند گره عبور کرده است، آنگاه میتوان به کمک آن برای هر بسته درجه اولویت تعیین کرد و همچنین تشخیص داد که آیا این بسته، با ارزش است و از شانس بالایی برای رسیدن به مقصد برخوردار است و یا اینکه بسته کم ارزش است و به جز پر کردن بافر، کار دیگری انجام نمیدهد.
حال سئوال این جاست که چگونه می توان در این میان، فضای بافر را به صورت بهینه مدیریت کنیم؟ بصورتی که در زمان اشباع و پر بودن بافر، زمانی که ما مجبور هستیم بستهای را از بافر حذف کنیم، این حذف بسته بر اساس ارزش و درجه اولویت بسته باشد و نه اینکه تنها به صرف پر بودن بافر بصورت تصادفی، تصمیم به حذف یک بسته بگیریم و بستهای را پاک کنیم که شاید همین گره بعدی مقصد او باشد ! آیا میتوان برای مدیریت بافر که در حقیقت جواب این پرسش است که "در صورت پر بودن بافر یک گره، کدام بسته موجود در بافر باید حذف شود تا فضا برای بستههای جدید باز شود؟" ، روشی نو ارائه کرد که معیارهای کارایی را نیز افزایش داد!
هدف ارائه یک الگوریتم مدیریت بافر میباشد که بر اساس اولویت، بستهها را Drop مینماید و سپس شبیهسازی آن با استفاده از نرمافزار شبیهساز Ns2.34 است. از آنجایی که الگوریتم Prophet کارایی قابل قبولی در میان الگوریتمهای مسیریابی DTN از خود نشان داده است به عنوان بستر ارزیابی، راهکار پیشنهادی انتخاب شده است و با توجه به اینکه سیاست مدیریت بافر الگوریتم Prophet مبتنی بر Drop Tail میباشد، پیشبینی میشود ارائه یک سیاست جدید بتواند به نرخ Drop کمتر بستهها کمک کرده و باعث افزایش در بهبود نرخ تحویل بستهها به مقصد گردد.
.2راهکار پیشنهادی
در این مقاله یک سیاست مدیریت بافر مبتنی بر تابع اولویت با استفاده از اطلاعات کنترلی بستهها، پیشنهاد میگردد. بستهها این اطلاعات کنترلی را از زمان تولید به همراه دارند و در هر لحظه بروزرسانی میکنند. بر این اساس در زمان پر بودن بافر گره، با توجه به تابع اولویت، بستههایی که تابع اولویتشان پایین میباشد را از بافر حذف میکند. همچنین در طرح پیشنهادی ما علاوه بر اینکه از اطلاعات کنترلی هر بسته استفاده کردهایم، بستهها را نیز در سه سطح Level 1، Level 2 و Level 3 قرار میدهیم. سطح Level 1 شامل بستههایی با اهمیت بسیار بالا، جهت انتقال به گرهی دیگر و همچنین ماندگاری در بافر را دارا میباشد و به تبع آن سطحهای Level 2 و Level 3 کم و کمترین درجه اهمیت را برخوردارند. برای ما مهم است که بستههای با اهمیت زود از بافر کنار گذاشته نشوند و تا رسیدن به مقصد در بافر نگهداری شوند.
1-2 اطلاعات کنترلی موجود در بستهها
اطلاعات کنترلی موجود در بستهها پارامترهای منحصر به فردی هستند که هر بسته آنها را همیشه همراه خود دارد و به هنگام رویارویی با گرهای دیگر این پارامترها را بروز میکند.
Pi TC RT TTL Seq# DA SA
شکل((1 قالب بسته داخل گرهها
این پارامترها عبارتند از : ( SA( Source Address آدرس گره مبدا، ( DA( Destination Address آدرس گره مقصد بسته، Seq# شماره منحصربفرد هر،( TTL ( Time To Live for message کل زمان از عمر بسته، ) ET Elapsed Time for message ) زمان سپری شده از عمر بسته،( RT ( Remaining Time-to-live for message
: زمان باقی مانده از عمر بسته، TC تعداد کپیهای هر بسته در طول شبکه و آیتم P نشانگر سطح اولویت بسته میباشد که شامل یکی از سه سطح 1-Level1 2-Level2 3-Level3 است. که در حالت کلی این رابطه همیشه برقرار است :
2-2 تابع اولویت پیشنهادی
تابع اولویت پیشنهادی ما ترکیبی از پارامترهای منحصر به فردی است که هر بسته آنها را همیشه همراه خود دارد و به هنگام رویارویی با گرهای دیگر این پارامترها را بروز میکند.
PC = 3 and Pi = 1 or 2 or 3. (2)
در فرمول پیشنهادی N تعداد کل گرههای موجود در شبکه را نشان میدهد. با توجه به تابع اولویت پیشنهادی، مشاهده می شود که ET در زیر کسر واقع شده است و هر چه مقدار آن، یعنی زمان سپری شده از عمر بسته افزایش یابد و همچنین هر چه مقدار TC (تعداد گرههایی که بسته در طول مسیرش مشاهده کرده است یا بعبارتی دیگر تعداد کپیهای هر بسته در طول شبکه) افزایش یابد، درجه اولویت بسته را پایین خواهد آورد. زیرا روشن است که با توجه به اینکه بسته زمان زیادی در شبکه در حال گردش بوده و در گرههای فراوانی کپی شده ست ولی با این وجود باز به مقصد نرسیده است، بنابراین احتمال به مقصد رسیدن این بسته بسیار کم خواهد بود و شاید اصلا گره مقصد این بسته از بین رفته باشد. بنابراین مقدار ET و TC با درجه اولویت بسته P(t) رابطه معکوس دارند.
همچنین باید توجه داشت رابطه PC - Pi در بالای کسر تابع واقع شده است و در تعیین مقدار درجه اولویت هر بسته نقش دارد. برای مثال بستهها در سه سطح تقسیم بندی می شود و مقدار PC برابر با 3 است ودرجه اهمیت بستههای سطح یک Pi=1 است. بر اساس رابطه زیر داریم :
PC - Pi = 3 - 1 = 2 (3)
که عدد 2 با درجه اولویت بسته P(t) جمع میشود و این درجه اولویت بسته را بالا خواهد برد.
3-2 چگونگی ورود و کنار گذاشتن بسته از بافر گره
در فلوچارت زیر چگونگی ورود بسته به گره و تصمیمگیری در مورد drop شدن کدامین بسته از بافر( هنگام پر بودن بافر گره ) نمایش داده شده است.
شکل((2 فلوچارت چگونگی ورود و کنار گذاشتن بسته از بافر گره
4-2 نقش صف اولویت در مدیریت بافر
در سیاست پیشنهادی، یک صف اولویت در کنار بافر هر گره تشکیل میشود. تعداد خانه های این صف برابر تعداد خانه های بافر است. محتوای خانههای این صف شامل شمارههای منحصربهفرد هر بسته میباشد که بر حسب تابع اولویت مرتب شدهاند و به خانههای بافر اشاره میکنند . به هنگام پر بودن بافر، بر حسب ترتیب خانههای این صف اولویت، خانهای در بافر حذف میشود که آخرین خانه صف به آن اشاره کند.
شکل (3) ارتباط بافر و صف اولویت
