مقیاس پذیری^[۳۴]: در شبکه ­های بی­سیم ارتباطات چندگامه رایج است. در همه شبکه ­های چندگامه پروتکل­های ارتباطی از مقیاس­پذیری رنج می­برند. وقتی که اندازه شبکه بزرگ می­ شود، کارایی شبکه به میزان قابل­توجهی کاهش می­یابد. با بزرگ­­شدن شبکه، پروتکل­های مسیریابی امکان پیداکردن یک مسیر قابل اعتماد را ندارند، پروتکل­های لایه انتقال اتصال در شبکه را از دست می­ دهند و پروتکل های لایه انتقال کاهش گذردهی زیادی را تجربه می­ کنند. به عنوان مثال پروتکل لایه کنترل دسترسی با استاندارد کنونی IEEE 802.11 وقتی که تعداد گام­ها به ۴ یا بیش­تر می­رسد نمی­تواند گذردهی قابل قبولی ایجاد کند[۴].
اتصال مشی: مزیت­های موجود در شبکه ­های مش بی­سیم ناشی از اتصال مشی موجود در شبکه است که در طراحی پروتکل کنترل دسترسی و مسیر­یابی باید به آن توجه شود. در این شبکه­ ها ویژگی تنظیم خودکار و الگوریتم­های کنترل توپولوژی مورد­نیاز است. پروتکل­های کنترل دسترسی و مسیریابی آگاه از توپولوژی به میزان زیادی کارایی شبکه را بهبود می­ دهند.
کیفیت خدمات^[۳۵]: برخلاف شبکه ­های سیار موردی اکثر کاربردهای شبکه ­های مش، سرویس­های broadband با نیازهای کیفیت خدمات متفاوت هستند. بنابراین علاوه بر تاخیر انتقال انتها به انتها و رعایت اعتدال^[۳۶] پارامترهای دیگری مانند تغییرات تاخیر، گذردهی هر گره و گذردهی کلی و نرخ از دست رفتن بسته­ها باید در نظر گرفته شود.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

تطبیق­پذیری: یک ویژگی ضروری برای شبکه ­های بی­سیم مش، ایجاد امکان دسترسی هم برای کاربران مش و هم برای کاربران قدیمی است. بنابراین شبکه ­های مش بی­سیم باید قابل تطبیق با کاربران سنتی باشند. به عبارت دیگر، اهداف گسترش شبکه مش باید توافقی باشد. مجتمع شدن شبکه ­های مش بی­سیم با دیگر شبکه ­های بی­سیم نیاز به مسیریاب­های مش خاص دارد که توانایی کارکردن با شبکه ­های بی­سیم نامتجانس^[۳۷] را داشته باشد.
امنیت: بدون در نظر گرفتن راه­ حل­های قانع کننده برای امنیت در شبکه ­های مش این شبکه­ ها نمی ­توانند موفق باشند. اگرچه طرح­های امنیتی زیادی برای شبکه ­های بی­سیم در نظر گرفته شده است اما قابل کاربرد برای شبکه ­های مش بی­سیم نیستند. به عنوان مثال به خاطر معماری توزیع شده این شبکه هیچ واحد اعتباردهی مطمئن و متمرکز که کلیدهای عمومی را در شبکه توزیع کند، وجود ندارد. طرح­های امنیتی به کاربرده شده برای شبکه ­های سیار موردی قابل کاربرد برای شبکه ­های مش بی­سیم هستند اما چندین نکته باید در نظر گرفته شوند[۴]:
راه­ حل­های به کار برده شده برای شبکه ­های سیار موردی در حال حاضر قابل پیاده­سازی به طور عملی نیستند.
معماری شبکه مش متفاوت از شبکه ­های سیار موردی است که باعث ایجاد نیازهای امنیتی متفاوت می­شوند.
در نتیجه طرح­های امنیتی زیادی شامل الگوریتم­های رمزنگاری، کلیدهای امنیتی توزیع شده، پروتکل­های مسیریابی امن، تشخیص خطا و نظارت امنیتی باید گسترش داده شوند.
سادگی استفاده: پروتکل­های شبکه مش باید طوری طراحی شوند که شبکه را برای مدیریت توان، تنظیم خودکار، کنترل توپولوژی پویا، مقاومت در برابر خطای لینک و تابع تصدیق کاربر به طور خودکار توانا کند. علاوه ­بر آن، ابزارهای مدیریت شبکه برای نظارت بر کارایی شبکه، سودمندی عملیات و پیکربندی پارامترهای شبکه مش بی­سیم مورد نیاز است. این ابزارها به علاوه مکانیزم­ های خودکار در پروتکل­ها باعث گسترش سریع شبکه مش بی­سیم می­ شود [۴].
جایگذاری گره­ها در شبکه مش: محل قرار گرفتن گره­های شبکه مش شامل مسیریاب­ها و دروازه اینترنت، باید به صورت هدفمند صورت بگیرد. یک مسئله مهم که در گذردهی شبکه هم تاثیرگذار است، تعیین محل مسیریاب­ها در شبکه مش به صورت هدفمند است، چرا که جایگذاری MRها بدون برنامه­ ریزی^[۳۸] و طرح هدفمند، خود می ­تواند موجب بروز مشکلات زیر ­شود [۵]:
تداخل ذاتی^[۳۹]: تداخل در شبکه ­های بی­سیم، گذردهی قابل دستیابی لینک­ها و گره­ها را کاهش می­دهد. در بدترین حالت، می ­تواند موجب از کار افتادگی تعدادی از لینک­ها، بخشی یا حتی تمام شبکه شود. جایگذاری MRها بدون در نظر گرفتن اطلاعات کلی شبکه و همسایه­ها، می ­تواند توپولوژی متداخلی را ایجاد کند که غلبه بر آن، به­ دلیل اتصال با زیربنای شبکه (اتصال سیمی با اینترنت) کار دشواری است و این مسئله در WMN با مقیاس بزرگ، نمی­تواند قابل پذیرش باشد.
هات­اسپات­های پیش ­بینی­نشده^[۴۰]: هات­اسپات به MRهای سرریزشده^[۴۱] می­گویند. ازدحام در هات­اسپات­ها منجر به ارسال مجدد بیشتر، حذف بسته­ها و سوئیچ به نرخ انتقال پایین­تر می­ شود. همه این موارد می ­تواند به میزان قابل­توجهی، گذردهی و کارایی شبکه را کاهش دهد. جایگذاری MRها بدون برنامه­ ریزی و مستقل از تقاضاهای ترافیک، ممکن است موجب شود تعداد MRهای کمتری نسبت به آنچه که در برخی نواحی با ترافیک سنگین مورد نیاز است، استفاده شود. MRها در این نواحی، به این دلیل هات­اسپات­ می­شوند که باید سربار ترافیکی که از کلاینت­های متصل به خود یا دیگر MRها تجمیع شده است را تحمل کنند. اگر چه، یک WMN تمام خودگردان^[۴۲]، قادر است تاحدی وجود این هات­اسپات­ها را با هدایت کردن ترافیک از طریق چند­مسیری^[۴۳] به سمت اینترنت، برطرف کند، اما کارایی شبکه هم­چنان با محدودیت­های ذاتی که روی منابع شبکه وجود دارد، محدود شده است. این مسئله می ­تواند از طریق طراحی مناسب شبکه، به میزان قابل­توجهی قابل اجتناب باشد.
معماری غیرقابل اطمینان^[۴۴]: یک شبکه قابل­قبول، باید با درجه­ مناسبی از تحمل خطا، قابل­اطمینان باشد. خرابی بخشی از شبکه نباید موجب متوقف شدن تمام شبکه شود. جایگذاری MRها بدون برنامه­ ریزی، نمی­تواند تضمینی برای قابلیت اطمینان شبکه باشد زیرا این معماری قادر نیست افزونگی لازم را داشته باشد و در مقابل خرابی لینک یا گره، بسیار آسیب­پذیر خواهد بود. به­عنوان نمونه، اگر WMN فقط یک دروازه داشته باشد و فقط به یک MR متصل باشد، خرابی MR یا دروازه، موجب از کار افتادن شبکه می­ شود
اهداف پایان نامه
با توجه به چالش­های ذکر شده در مورد جایگذاری گره­ها، و مشکلات ناشی از آن، جایگذاری MRها بدون برنامه­ ریزی، برای توسعه یک WMN با مقیاس بزرگ نامناسب است و بنابراین جایگذاری هدفمند مسیریاب­ها در شبکه، اولین و جز مهمترین قدم­ها در طراحی کارامد شبکه مش بی­سیم است. تحلیل­ها نشان می­دهد زمانی که MRها در موقعیت بهینه قرار گرفته باشند، حداکثر ظرفیت WMN قابل دستیابی است. دلیل آن هم این است که ظرفیت شبکه، به میزان زیادی، تحت تاثیر ظرفیت گره و ارتباطات چندگامه است.
هدف یک استراتژی جایگذاری کارامد و موثر، با حداقل کردن هزینه (یعنی تعداد MRها) برای سرویس­دهی به منطقه موردنظر است، ضمن اینکه محدودیت­های گوناگونی را مانند پوشش، اتصال، محیطی و تقاضای ترافیک^[۴۵] در نظر می­گیرد. این استراژی بخصوص، باید به سوالات زیر پاسخ دهد:
در یک WMN چه تعداد MR نیاز است؟
این MRها کجا باید قرار بگیرند تا در WMN، پوشش کامل و اتصال کامل قابل دستیابی باشد؟
ساختارپایان‌نامه
در این پایان نامه در فصل دوم به بررسی و مرور روش­هایی که تا کنون، برای تعیین مکان مسیریاب­ها در شبکه مش بکار برده شده، پرداخته می­ شود. در فصل سوم الگوریتم پیشنهادی و ویژگی­های آن معرفی می­ شود. در فصل چهارم ارزیابی روش­های به کاربرده شده به­ صورت مقایسه الگوریتمی و پیاده­سازی در محیط شبیه­سازی انجام می­گیرد. در نهایت در فصل پنجم به نتیجه ­گیری کارهای انجام شده در پایان نامه و ارائه‌ پیشنهادهایی برای انجام کارهای آینده که در این زمینه قابل انجام است، پرداخته می‌شود.
فصل دوم :
مروری بر روش­های جایگذاری مسیریاب­ها در شبکه مش بی­سیم
مقدمه
برای مساله تعیین مکان مسیریاب­ها^[۴۶] در شبکه ­های مش تا کنون راه­ حل­های متفاوتی ارائه شده­است که هر کدام تا اندازه­ای معیارهای مورد نیاز را تامین کرده ­اند. در این فصل تعدادی از روش­های به کار برده شده قبلی معرفی می­شوند.
در سال­های اخیر، محبوبیت شبکه ­های مش بی­سیم بر پایه تکنولوژی Wi-Fi به دو دلیل اصلی به رشد خود ادامه داده است: اول اینکه WMNها^[۴۷] با بهره گرفتن از تکنولوژی موثر چند واسط رادیویی و چندکاناله، توانسته ­اند پهنای باند بالایی، جهت دسترسی به اینترنت برای کاربران متحرک، در هر زمان و در هر مکانی فراهم می­ کنند. دلیل اصلی دیگر، ستون فقرات تامین­شده توسط WMN است که موجب می­ شود یک طراحی و توسعه مقرون به صرفه در مقایسه با شبکه ­های سنتی مانند WLANها، به علت عدم وابستگی به اتصالات سیمی بدست آید. از طرف دیگر، این افزایش محبوبیت، یک سئوال چالش­­برانگیز را مطرح کرده است: چگونه یک اتصال WMN مقرون به صرفه تعریف شود که بتواند سطح مطلوبی را برای گذردهی اینترنت در یک اجتماع بزرگ، فراهم کند.
در اکثر پژوهش­ها، در روش­هایی که برای بهبود عملکرد WLANها پیشنهاد شده است، فرض شده است که WMN موجود، قبلا ساخته شده است، یعنی هر یک از مسیریاب­های مش در موقعیت داده شده­، قرار گرفته­اند و به صورت کارایی پیکربندی شده ­اند. تعیین مکان موثر MRها^[۴۸]، به عنوان اولین گام مهم در تضمین کارایی رضایت­بخش یک WMN، به میزان زیادی نادیده گرفته شده است. یک توسعه نامناسب MRها، نه تنها موجب ایجاد تداخل زیادی می­ شود که در غیر این صورت قابل اجتناب بود، بلکه هات­اسپات­های^[۴۹] نامطلوبی را ایجاد می­ کند که موجب تحمیل بار اضافی به برخی مسیریاب­ها می­ شود در حالی که، سایر MRها با بهره­وری پایین منابع، کار می­ کنند [۵].
کارایی و عملکرد خوب WMN به میزان زیادی به محل قرارگیری مسیریاب­های مش در ناحیه جغرافیایی بستگی دارد تا اتصال و پایداری شبکه بدست آید. بنابراین یافتن مکان بهینه یا نزدیک به بهینه برای گره­های مسیریاب مش، در این شبکه­ ها امری حیاتی و ضروری است.
یک طرح عملی تعیین موقعیت مکانی MRها، مصالحه­ای بین دو محدودیت کلیدی در طراحی است: هزینه و ترافیک درخواستی که باید پاسخ داده شود. مسئله تعیین موقعیت مکان مسیریاب­ها باید بتواند تعیین کند که چه تعداد MR مورد­نیاز است و این MRها، با توجه به محدودیت­های شبکه، کجا باید قرار داده شوند. محدودیت­هایی که شامل محدودیت­های جغرافیایی، ترافیکی می­ شود.
از آنجایی که مسئله تعیین مکان، جز مسئله­های NP-Hard می­باشد، از روش­های ابتکاری برای حل مسئله استفاده می­ شود. در ادامه روش­هایی که برای حل مسئله تا کنون به­کار برده شده، همراه با بررسی و تحلیل ویژگی­های هر یک آورده می­ شود.
مروری بر کارهای انجام گرفته
روش­های مبتنی بر الگوریتم­های ابتکاری
در این قسمت، روش­هایی که در آن­ها از الگوریتم­های ابتکاری برای مسئله جایگذاری مسیریاب­ها استفاده شده است، توضیح داده خواهند شد.
در [۵] مسیریاب­ها، در موقعیت­های کاندید از پیش تعیین­­شده­ قرار می­گیرند. در این پژوهش، ترافیک درخواستی برای اینترنت در نظر گرفته شده است و از ترافیک نظیر به نظیر^[۵۰] صرف­­نظر شده است. برای تخمین ترافیک هر مسیریاب، از یک تابع چگالی استفاده شده است که در آن ترافیک درخواستی هر گره برابر است با مجموع بار ترافیک کلاینت­های خود و بار ترافیکی که باید رله کند.
سه گام برای رسیدن به راه حل موردنظر طی می­ شود. در گام اول، ترافیک شبکه بررسی شده و یک تابع چگالی ترافیک جهت تخمین ترافیک تعیین و مشخص می­ شود. در گام دوم، موقعیت مکانی دروازه اینترنت^[۵۱] تعیین می­ شود که فرض شده است تنها یک دروازه اینترنت در شبکه موجود است. این گام به صورت زیر انجام می­ شود:
در ابتدا، فرض شده است که IGW در مختصات (x0, y0) قرار داده شده است و شعاع محیط شبکه برابر با R است. برای یک ناحیه بسیار کوچک a که مرکز آن نقطه (x, y) است، a با dx×dy اندازه ­گیری می­ شود. تابع چگالی ترافیک μ (a) در a با μ (x, y) محاسبه می­ شود. بنابراین ترافیک درخواستی در a، برابر با μ (x, y) dxdy می­ شود. فرض شده است که پروتکل مسیریابی کوتاه­ترین مسیر بکار می­رود، بنابراین طول مسیر از a تا IGW می ­تواند با فاصله اقلیدسی میان a و IGW تقریب زده شود که برابر است با . بنابراین حجم ترافیکی ناحیه a به صورت μ (x, y) dxdy ×d تعریف شود. حجم ترافیک کلی دیسک شبکه، برابر با جمع حجم ترافیکی از همه ناحیه­های دیسک به IGW است، یعنی. در نتیجه برای حداقل­کردن حجم ترافیک کل،باید عبارت زیر مینیمم شود:

(‏۲‑۱)

اگر IGW در هر موقعیت دیگری قرار بگیرد، طول مسیر ارتباطی کلی افزایش می­یابد. در نتیجه تعداد MRها باید افزایش یابد، زیرا برای انتقال همان مقدار داده، تلاش ترافیکی بیشتری نیاز است. با داشتن μ (x, y)، یافتن مکان (x0, y0) که در آن مینیمم تلاش ترافیکی در مدل ترافیک ناهمگن بدست می ­آید، آسان است. در صورتی که هیچ یک از گره­های کاندید V، مختصات (x0, y0) را ندارند، نزدیک­ترین گره کاندید به (x0, y0) درV انتخاب شده و به عنوان (x0, y0) در نظر گرفته شده است.
در گام دوم، موقعیت مسیریاب­ها از میان موقعیت­های کاندید طوری انتخاب می­شوند که بتوانند با IGW، دیسک شبکه را پوشش دهند. در این روش، تعیین موقعیت مسیریاب­ها به صورت مسئله پوشش با سلول­های شش­ضلعی^[۵۲] مدل شده است. در نتیجه استفاده از این مدل، راه­حلی با ویژگیهای زیر حاصل می­ شود:
فاصله میان هر دو گره­ی MR همسایه (شش ضلعی)، برابر با برد انتقال مسیریاب است، طوری که اتصال شبکه تضمین شود. برد همه مسیریاب­ها در این روش، یکسان فرض شده است.
اگر MR ها بتوانند در هر جایی از دیسک قرار گیرند، تعداد MR نیاز است (در صورتی که اثر مرز دیسک، نادیده گرفته شود).