ترجمه مقاله تعیین مکان بهینه گره در شبکه های مسیریابی فرصت طلب بی سیم
چکیده-در سال های اخیر، توجه روز افزونی به مسیریابی فرصت طلب به عنوان روشی برای افزایش ظرفیت شبکه های بی سیم با بکارگیری طبیعت انتشاری آن پرداخته شده است. برخلاف مسیریابی تک مسیره قدیمی، در مسیریابی فرصت طلب گره هایی که ارسال های همسایه را می توانند استراق سمع[1] بکنند می توانند کاندیدهای فرستنده بسته به سمت مقصد شوند. در این مقاله به این سوال خواهیم پرداخت: حداکثر کارایی که می توان با استفاده از مسیریابی فرصت طلب به دست آورد چقدر است؟ برای پاسخ به این سوال، از یک مدل تحلیلی استفاده می کنیم که اجازه می دهد تا موقعیت بهینه گره ها را محاسبه کنیم، به طوری که حرکت به سمت مقصد به حداکثر برسد. از این مدل برای محاسبه کران های مینیمم استفاده می شود که می تواند تعداد ارسال ها در یک شبکه را با استفاده از مسیریابی فرصت طلب به دست آورد.
کلیدواژگان: شبکه های بی سیم، مسیریابی فرصت طلب، عملکرد ماکزیمم، مدل تحلیلی.
1. مقدمه
شبکه های بی سیم چند هاپ[2] (MWN) تبدیل به یک حوزه پژوهشی بسیار فعال در سال های گذشته شده اند. به دلیل دو تفاوت اساسی، مسیریابی در MWN پر چالش تر از شبکه های سیمی است، تفاوت اول در ویژگی های ناهمگن لینکهای بی سیم است. در نتیجه، تفاوت های قابل توجهی در احتمالات تحویل بسته می تواند در سراسر لینک یک شبکه MWN وجود داشته باشد. تفاوت دوم به ماهیت انتشار ارسال های بی سیم بر می گردد[3]. بر خلاف شبکه های سیمی، که در آن ها لینک ها به طور معمول نقطه به نقطه هستند، در شبکه بی سیم هنگامی که یک گره بسته ای ارسال می کند، همسایه های گره مقصد مورد نظر می توانند آن را استراق سمع کنند.
پروتکل های مسیریابی در MWN بطور مرسوم با استفاده از پروتکل های توزیعی که در هر گره بهترین لینک را برای هر مقصد (هاپ بعدی) اتتخاب می کنند به مدیریت مشخصه های ناهمگن لینک های بی سیم می پردازد. هنگامی که تمام گره های بعدی انتخاب شدند، تمامی بسته ها بین مبدا و مقصد همان مسیر را دنبال می کند. که چنین پروتکلهایی، مسیر یابی تک مسیره[3] نام دارند.
مسیریابی فرصت طلب (OR) [4-7] برای افزایش عملکرد MWNها با استفاده از طبیعت پخش رسانه های بی سیم پیش بینی شده است. در OR، به جای اینکه یک گره تکی از قبل به عنوان فرستنده بسته انتخاب شود تا هاپ بعدی شود، یک مجموعه گره های سفارشی (یعنی کاندیدها) به عنوان فرستنده های ممکن هاپ بعدی انتخاب می شوند. بنابراین، مبدا می تواند مسیرهای بالقوه متعددی را برای تحویل بسته ها به مقصد استفاده نماید. پس از ارسال
یک بسته، تمام کاندیدها که با موفقیت آن را دریافت می کنند در میان خود برای تعیین اینکه کدام یک از آن ها این بسته را ارسال خواهد کرد هماهنگ می شوند؛ بقیه نیز بسته را کنار خواهند گذاشت.
تحقیق قبلی در این زمینه عمدتا در ارائه و ارزیابی مکانیزم های انتخاب کاندیدهای مختلف و پروتکل های مسیریابی تمرکز داشته است. فلذا، عملکرد مکانیزم پیشنهادی، با عملکرد سناریو پایه مسیریابی سنتی تک مسیره و یا با عملکرد مکانیزم های OR دیگر مقایسه می شود. این عملکرد به طور کلی از نظر تعداد ارسال های مورد انتظار از مبدا به مقصد (که، همانند [8]، به آن ارسال هر مسیره انتظاری[4]، EAX می گوییم) اندازه گیری می شود. از نظر ما تمامی مطالعات فرض می کنند که توپولوژی شبکه مشخص است و ارزیابی های و مقایسه ها روی آن توپولوژی، و یا انواع آنها انجام می شود. در این مقاله رویکرد متفاوتی را دنبال می کنیم. در اینجا، به بررسی حداکثر بهره ای که می توان با استفاده از OR به دست آورد می پردازیم. برای این منظور، به مطالعه موقعیت بهینه گره های کاندید می پردازیم. لذا بینش به دست آمده برای پیشنهاد قوانین طراحی عملی برای شبکه های بی سیم چند هاپ اعمال می گردد.
در بخش اول این مقاله، در مورد این سوال صحبت خواهیم کرد: حداکثر بهره که می توان با استفاده از OR به دست آورد چقدر است؟ منظور از بهره، تفاوت نسبی تعداد مورد انتظار ارسال های لازم بین OR و سناریو مسیر یابی پایه تک مسیره است. به طور خاص، بر روی یک سناریو تمرکز می کنیم که در آن حداکثر تعداد کاندیدها به ازای هر گره محدود است. برای پاسخ به سوال قبلی، از یک شبکه که در آن گره ها بطور بهینه قرار گرفته اند استفاده می کنیم به طوری که در هر ارسال حرکت به سمت مقصد ماکزیمم شود. برای این کار، باید فرض کنیم که یک فرمول برای احتمال تحویل، p(d)، بین گره ها در فاصله d داریم. برای سادگی، باید همان تابع ، p(d)، را برای هر جفت از گره ها در نظر بگیریم. با این حال، این مدل را می توان با فرض یک تابع متفاوت برای هر لینک تعمیم داد. در تجزیه و تحلیل ما p(d) با استفاده از مدل انتشار رادیویی داده خواهد شد. رابطه محاسبه تعداد ارسال های مورد انتظار OR توسط نویسندگان مختلف (به عنوان مثال [8-10]) بدست آمده است. که آن رابطه بازگشتی بوده و وابستگی غیر خطی به احتمال تحویل بین گره ها دارد. از این فرمول برای اهداف مقایسه ای استفاده خواهیم کرد، و در بقیه مقاله، از آن به عنوان فرمول بازگشتی[5] EAX یاد خواهیم کرد.
[1] Overhearing
[2] Multi-hop
[3] Uni-path
[4] Any-path transmission
[5] Recursive formula