چكيدهشبکههای مش بیسیم، شامل مسیریابهای مش و کلاینتهای مش هستند، که مسیریابهای مش با کمترین تحرک، ستون فقرات شبکه مش را شکل میدهند. مسیریابها و کلاینتها در شبکه مش از طریق دروازه به اینترنت دسترسی پیدا میکنند. امروزه شبکههای مش بیسیم، سرویسهای بیسیم را در گستره متنوعی از کاربردها، در سطح شخصی، محلی، محوطههای دانشگاهی و نواحی شهری ارائه میدهد. یکی از اصلیترین چالشهای موجود در طراحی شبکه مش بیسیم، تعیین موقعیت مکانی مسیریابهای مش در شبکه است. در واقع، تعیین مکان مسیریابهای مش در ساختن یک شبکه مشبیسیم، اولین مرحله در تضمین کارایی مطلوب در شبکه است. مسئلهی اساسی در جایگذاری مسیریابهای مش، یافتن تعداد مسیریابهای مورد نیاز مش است به گونهای که معیارهای مورد نیاز این شبکه را برآورده کند. در این پایاننامه یک روش ابتکاری که با استفاده از الگوریتم ژنتیک، برای یافتن تعداد مسیریابها و موقعیت بهینه آنها پیشنهاد شده است. روش پیشنهادی میتواند معیارهای لازم این شبکه را به طور موثری تامین کند. نتایج حاکی از کارایی قابل قبول این روش دارد. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی از لحاظ تعداد مسیریابها و میزان فضای پوششی متناسب با آن، از روشهای مشابه، بهتر است.کلمات کلیدی: شبکه مش بیسیم، تعیین موقعیت مکانی مسیریابها، پوشش، اتصال، الگوریتم ژنتیک. فهرست مطالبفصل اول: مقدمهای بر شبکههای مش بیسیم11-1 شبکه مش بیسیم21-2 معماری شبکه مش51-3 ویژگیهای شبکه مش بیسیم91-4 تفاوت با سایر شبکههای چندگامه111-5 چالشهای موجود در شبکههای مش بیسیم131- 6 اهداف پایاننامه171- 7 ساختارپایان‌نامه18فصل دوم: مروری بر روشهای تعیین مکان مسیریابها در شبکه مش بیسیم192-1 مقدمه202-2 مروری بر کارهای انجام گرفته212-2-1 روشهای مبتنی بر الگوریتمهای ابتکاری212-2-2 روشهای مبتنی بر الگوریتمهای تکاملی272-2-3 روشهای مبتنی بر مدل بهینهسازی282-2-4 سایر روشها312-3 نتیجهگیری34فصل سوم: معرفی الگوریتم پیشنهادی بر مبنای الگوریتم ژنتیک363-1 مقدمه373-2 معرفی Packing Problem373-3 مسئله Circle Packing383-4 مدل شبکه393-5 فرموله سازی مسئله413-6 الگوریتم ژنتیک423-6-1 كروموزوم433-6-2 جمعيت ژنتيكي433-6-3 تابع برازش433-6-4 عمليات ژنتيكي443-6-5 پارامترهای الگوریتم ژنتیکی443-6-6 روشهاي كدگذاري453-6-7 عملگرهاي ژنتيكي463-6-8 ساختار الگوریتم پیشنهادی503-7 مدل ترافیک563-8 تعیین تعداد مسیریابها593-9 نتیجهگیری60فصل چهارم: شبیهسازی و ارزیابی روش پیشنهادی624-1 مقدمه634-2 مقایسه با مرجع [10]634-3 مقایسه با مرجع [12]664-4 تعیین تعداد مسیریابها73فصل پنجم: نتیجهگیری و پیشنهادات765-1 مقدمه775-2 نتیجهگیری775-3 پیشنهادات79واژه‌نامه انگليسي به فارسي81منابع86 فهرست شکلها شکل 1‑1 نمایی از شبکه LAN بیسیم2شکل 1‑2 شبکه سیار موردی3شکل 1‑3 نمای کلی شبکه مش4شکل 1‑4 ستون فقرات ساخت یافته7شکل 1‑5 مدل کاربر8شکل 1‑6 نمایی از مدل ترکیبی8شکل 3‑1 یک نمونه از CP39شکل 3‑2 مدل شبکه40شکل 3‑3 شمای یک کروموزوم با n ژن43شکل 3‑4 کدگذاری دودویی45شکل 3‑5 کدگذاری جابجایی45شکل 3‑6 کدگذاری مقداری46شکل 3‑7 تقاطع تک نقطه‌ای47شکل 3‑8 تقاطع دو نقطه‌ای47شکل 3‑9 تقاطع یکنواخت48شکل 3‑10 ساختار کروموزوم52شکل 3‑11 تعیین نقطه تقاطع53شکل 3‑12 کروموزومها بعد از عمل تقاطع53شکل 3‑13 قسمت اصلی الگوریتم54شکل 3‑14 تابع تولید جمعیت اولیه55شکل 3‑15 تابع تقاطع55شکل 3‑16 تابع انتخاب55شکل 3‑17 تابع جهش55شکل 3‑18 یک خوشه با یک IGW57شکل 3‑19 تابع تعیین تعداد مسیریابها59شکل 4‑1 شبکه اولیه، با محدودیت جغرافیایی63شکل 4‑2 جایگذاری تصادفی64شکل 4‑3 جایگذاری با روش NPR64شکل 4‑4 جایگذاری با روش VFPlace65شکل 4‑5 جایگذاری روشNPR با لحاظ کردن محدودیت محیطی65شکل 4‑6 جابهجایی مسیریابها با نوع قویتر66شکل 4‑7 تعیین نواحی حیاتی در روش NPR66شکل 4‑8 حداکثر تعداد کلاینتهای پوشش داده شده در توزیع یکنواخت70شکل 4‑9 حداکثر تعداد کلاینتهای پوشش داده شده در توزیع نرمال71شکل 4‑10 حداکثر تعداد کلاینتهای پوشش داده شده در توزیع weibull72شکل 4‑11 حداکثر تعداد کلاینتهای پوشش داده شده در توزیع توانی72شکل 4‑12 حداکثر کلاینتهای پوشش داده شده در همه توزیعها در روش NPR73شکل 4‑13 تعداد 28 مسیریاب استفاده شده در شبکه 32×3275شکل 4‑14 شبکه 32×32 با محدودیت محیطی75شکل 4‑15 تعداد 56 مسیریاب استفاده شده در شبکه 64×6475شکل 4‑16شبکه 64×64 با محدودیت محیطی75شکل 4‑17 تعداد 28 مسیریاب استفاده شده در شبکه با اندازه شبکه VFPlace75شکل 4‑18 شبکه VFPlace با محدودیت محیطی75 فهرست جداول جدول 2‑1 مقایسه روش های جایگذاری مسیریابهای مش34جدول 4‑1 متغیرهای مجموعه محک67جدول 4‑2 نتایج مربوط به شبکه 32×32 با 16 مسیریاب و 48 کلاینت68جدول 4‑3 نتایج مربوط به شبکه 64×64 با 32 مسیریاب و 96 کلاینت68جدول 4‑4 نتایج مربوط به شبکه 128×128 با 64 مسیریاب و 192 کلاینت69جدول 4‑5 تعیین تعداد مسیریاب مورد نیاز74 1 فصل اول در این فصل ابتدا مقدمهای راجع به شبکههای مش بیسیم، کاربردها و خصوصیات آنها ارائه خواهد شد، سپس موضوع انتخاب شده در این پایاننامه و اهمیت آن بررسی میشود. در پایان ساختار پایاننامه مشخص میشود.شکل 1‑1 نمایی از شبکه LAN بیسیم [1] پيادهسازيهاي اوليه شبكههاي بيسيم مبتني بر استاندارد IEEE 802.11، متشكل از چندين BSS[2] است. درون هر BSS یک ایستگاه به نام نقطه دسترسی(AP[3]) وجود دارد که برای دسترسی به ساختار سیمی به کار برده میشود، BSSها از طریق LANهاي اترنت (ساختار سیمی) به هم متصل ميشوند یا به اینترنت دسترسی پیدا میکنند. همانطور که در شکل 1-1نشان داده شده است، دو ایستگاه پایه وجود دارد و در هر کدام یک نقطه دسترسی قرار گرفته است. نقاط دسترسی به شبکه سیمی وصل میشوند و از این طریق بین دو BSS ارتباط ایجاد میشود. اين چنين شبكههايي، شبكههاي تكگامه[4] با معماري ثابت هستند كه قابليتانعطافپذيري پايين و هزينه پيادهسازي بالايي دارند. برای تامین تحركپذيري گرهها و چندگامه[5] بودن شبكه، شبكههای سیار موردی[6] بهوجود آمدند كه حالت بدون ساختار را تشکیل میدهند. در اين حالت ايستگاهها بدون هيچ هماهنگكننده مركزي مثل نقطه دسترسی و یا يك سيستم توزيعي (ساختار سیمی) به هم متصل ميشوند و گرهها كاملاً خودگردان هستند (شکل 1-2) [1]. شکل 1‑2 شبکه سیار موردی [1]شبكههاي سیار موردی براي بسياري از كاربردها مناسب نيستند چون همانطور كه تحرك و چندگامه بودن مورد نياز است دسترسي به اينترنت و مجتمع شدن با شبکههای دیگر نیز مورد نياز است. بنابراین حالت دارای ساختار[7] و حالت بدون ساختار با هم تركيب شدهاند و يك نوع جديد از شبكههاي چند گامه به نام مش بیسیم را بهوجود آوردهاند.شبکه بیسیم مش یک شبکه متشکل از چندین گره است که به طور بیسیم با هم ارتباط دارند و همانطور که از نام آن پیدا است بین همه گرهها به طور مستقیم یا غیرمستقیم مسیر ارتباطی وجود دارد. هر گره نه تنها به صورت يك میزبان[8] عمل ميكند بلكه يك مسیریاب نيز عمل مینماید و بستهها را به گرههای ديگر كه ممكن است در محدوده انتقال[9] گره مقصد نيز نباشند، ارسال ميكند. شکل 1-3 نمای کلی از شبکه مش را نشان میدهد شکل 1‑3 نمای کلی شبکه مشيك شبکه مش بیسیم به صورت يك شبكه خودگردان[10] با تنظیم خودکار[11] است که گرههای موجود در آن به طور اتوماتيكي ارتباط را در ميان خودشان راهاندازي و حفظ ميكنند. اين ويژگي مزيتهاي زيادي مثل هزينه پايين، نگهداري آسان شبكه، نيرومندي و ارائه سرويس قابل اعتماد برای شبكههاي بيسيم مش ايجاد كردهاست. گرههايی از قبيل(desktop، laptop، PDA و ...) به كارتهاي شبكه بيسيم مجهز هستند و به طور مستقيم به شبکه مش وصل میشوند [1]. مشتريهاي بدون كارت بيسيم از طريق وصل شدن به مسیریابهاي مش بيسيم مثلاً با اترنت به شبکه مش دسترسي پیدا میکنند. بنابراين شبکههای مش بیسیم به كاربران كمك ميكنند تا در هر زمان و هر مكاني فعال باشند. علاوه بر اين تواناييهاي دروازه[12] در مسیریابهاي مش، امكان مجتمعشدن شبكه مش بیسیم را با شبكههاي بيسيم موجود از قبيل حسگر[13]، Wi-Fi، Wi-MAX، Wi-Media و ... ميدهد. در نتيجه از طريق يك شبکه مش مجتمع، كاربران درون شبکه مش ميتوانند از سرويسهاي موجود در شبكههاي ديگر استفاده كنند. شبكههاي مش بيسيم برای تعداد زیادی از كاربردها مانند، شبکهبندی خانگی ،... استفاده میشوند [1].در قسمتهای بعد به معرفی شبکههای مش بیسیم از جنبههای مختلف پرداخته میشود.شبکه مش بیسیم شامل دو نوع گره است: 1-مسیریاب و 2-کاربر.يك مسیریاب مش بيسيم علاوه بر توانايي مسيريابي همانند شبكههاي بيسيم قبلي، شامل تواناييهاي مسيريابي اضافي براي راهاندازي و تامین شبکهبندی مش است. براي بهبود بيشتر شبكه مش، يك مسیریاب مش معمولا به چندين واسط[14] بيسيم مجهز ميشود كه بر اساس تكنولوژيهاي دسترسي بيسيم مختلف يا يكساني ساخته ميشوند. يك مسیریاب مش در مقايسه بامسیریابهای قبلي، ميتواند به پوشش يكسان با توانايي انتقال كمتر از طريق ارتباطات چندگامه برسد. با وجود اين مسیریابهاي مش بيسيم و مسیریابهاي قبلي براساس يك بستر سختافزاري يكسان ساخته ميشوند. مسیریابهاي مش ميتوانند براساس سيستمهاي كامپيوتري embedded يا براساس سيستمهاي كامپيوتري چند منظوره[15] ساخته شوند.کاربران مش همچنين قابليت كافي براي شبکهبندی مش را دارند و بنابراين ميتوانند به صورت يك مسیریاب كار كنند. اگر چه توابع دروازه يا پل[16] در اين گرهها وجود ندارد. به علاوه كلاينتهاي مش معمولاً تنها يك واسط دارند. بستر سختافزار و نرمافزار برای کاربرهای مش آسانتر از مسیریابها ساخته ميشود. کاربردهای مش تنوع محصول بيشتري نسبت به مسیریابها دارند و ميتوانند desktop ، laptop،PDA و... باشند.