متفاوت

 

خوب

 

دارد

 

سیارپیشا

 

 

 

پوشش بسیار مناسب و عدم تعیین تعداد مسیریاب­ها

 

دارد

 

دارد

 

ثابت

 

یکسان

 

خیلی خوب

 

دارد

 

مدل نیروی مجازی

 

 

 

Con (Connrctivity) : نشان دهنده وجود اتصال در شبکه.
RT (Router-Type) : یکسان یا متفاوت بودن نوع مسیریاب را نشان می­دهد.
Cov (Coverage) : میزان پوشش شبکه.
Num (Number of routers) : تعیین یا عدم تعیین تعداد مسیریاب­ها.
EC (Enviroment Constraint) : نشان­ دهنده درنظر گرفتن محدودیت محیطی.
: TC (Traffic Constraint) نشان­ دهنده درنظر گرفتن محدودیت ترافیکی.
Specification: نشان دهنده ویژگی­های هر روش.
فصل سوم:معرفی الگوریتم پیشنهادی بر مبنای الگوریتم ژنتیک
مقدمه
در این فصل ابتدا به معرفی پیش­نیازهای لازم برای تعریف الگوریتم پیشنهادی پرداخته می­ شود و سپس، الگوریتم ژنتیک پیشنهادی با جزئیات شرح داده خواهد شد.
دانلود پایان نامه - مقاله - پروژه
معرفی Packing problem
مسائل برش و جادادن [۸۵] یک کلاس از مسائل بهینه­سازی است که شامل جادادن[۸۶] یک مجموعه از آیتم­ها با ابعاد معلوم تا جایی که امکان­ پذیر است، به درون یک یا چند شی بزرگتر، با هدف مینیمم کردن قسمت­ های بلا استفاده یا هدر رفته شی بزرگتر می­باشد. در مسائل C&P دو نوع شی وجود دارد: Container و goods.Container شیئی است که اشیاء کوچکتر درون آن قرار می­گیرند و goods اشیایی هستند که باید درون Container قرار بگیرند. مسائل C&P جز مسائل چالش برنگیز علمی با محدوده وسیعی از کاربردها و جز مسائل جالب ترکیبی بهینه­سازی NP-Hard می­باشند. در طیف وسیعی از کابردهای دنیای واقعی شامل تولید و جادادن برای اتومبیل، هوافضا و صنایع غذایی، مورد استفاده قرار می­گیرند. اشیا و آیتم­ها می­توانند مستطیلی، مربعی، دایره­ای یا نامنظم باشند یعنی مسئله­هایی مانند جادادن تعدادی مستطیل در یک مستطیل بزرگتر، دایره در مستطیل از این دسته مسائل هستند. یکی از این نمونه­ها، مسئله جادادن مجموعه ­ای از آیتم­های دایره­ای درون کوچک­ترین دایره ممکن می­باشد. از نمونه کاربردهای این مسئله، در ساختمان سیم­­کشی­ اتومبیل است، که سنسورهای اتومبیل را به برد نمایش متصل می­ کنند. سیم­ها بایستی از طریق یک حفره که در بدنه اتومبیل ایجاد شده، عبور داده شوند. حفره بایستی به اندازه کافی برای عبور همه سیم­ها بزرگ باشد و در عین حال، تا حد امکان کوچک باشد تا از ایجاد فضای غیرضروری در بدنه جلوگیری شود. نمونه دیگر، تمایل شرکت­های ارتباطی الکتریکی است که بایستی مجموعه ­ای از کابل­ها با انواع متفاوت را از طریق قالب­های استوانه­ای شکل، در سرتاسر هزاران کیلومتر عبور دهند؛ قطر کوچکتر قالب استوانه­ای، موجب کم­تر شدن هزینه می­ شود [۲۶ و ۲۷ و ۲۸].
مسئله Circle packing
CPP[87] شامل جادادن یک مجموعه از دایره­های با شعاع برابر یا نابرابر بدون همپوشانی، به درون کوچکترین دایره Container ممکن، C است. شعاع هریک از با مشخص می­ شود. هدف، یافتن بهترین الگو جادادن[۸۸] همه دایره­ها به درون C است طوری که با بهترین الگوی جادادن، فضای هرز تا حد ممکن مینیمم شود.
CPP به منزله تعیین مختصات ، مرکز هر دایره ، شعاع دایره Container، r و مختصات مرکز دایره Container، C است طوری که هیچ یک از دایره­ها دو­به­دو با یکدیگر همپوشانی نداشته باشند.
تعریف رسمی مسئله : مسئله می ­تواند به صورت یافتن سطح بهینه برای متغیرهای r و و باشد.
Minimize r
(‏۳‑۱) (CPP)
(‏۳‑۲) , j<I
اولین مجموعه از محدودیت­ها بیان می­ کند که هر یک از ها باید درون C قرار بگیرند. بنابراین تعداد n محدودیت، یکی برای هر وجود دارد. مجموعه دوم، عدم وجود همپوشانی بین هر دو جفت از دایره­های متمایز را بیان می­ کند؛ یعنی فاصله اقلیدسی مرکزهای و بایستی بزرگتر یا مساوی مقدار باشد. تعداد محدودیت­ همپوشانی وجود دارد و در مجموع محدودیت باید ارضا شوند [۲۹ و ۳۰ و ۳۱]. یک نمونه از خروجی مسئله CP در شکل ۳-۱ نشان داده شده است.
شکل ‏۳‑۱ یک نمونه از CP
شکل ‏۳‑۱- یک نمونه از CP
مدل شبکه[۸۹]
مسئله تعیین مکان مسیریاب­ها[۹۰] در شبکه مش بی­سیم، می ­تواند به صورت روشی برای تعیین موقعیت مکانی برای تعدادی MR در محیط شبکه، ضمن ارضای محدودیت­های ترافیکی و محیطی توصیف شود. ناحیه­ای که باید توسط ستون فقرات WMN[91] پوشش داده شود، به صورت دیسک دوبعدی با شعاع R در صفحه مختصات دو بعدی مدل می­ شود. مرکز دیسک در مبدا، یعنی واقع شده است. در ابتدا مجموعه از مسیریاب­ها با نام تعریف می­کنیم، که هر عنصر آن نشان­دهنده یک مسیریاب است. هر یک از مسیریاب­ها، از آنجایی که دارای یک برد دایره­ای شکل هستند، به صورت یک دایره در نظر گرفته می­شوند. برای اینکه که بتوان از این مدل استفاده کرد، از وجود موانع در محیط شبکه که ممکن است موجب شود شکل واقعی برد، از حالت دایره­ای شکل خارج شود، صرف نظر شده است. برد انتقال هر یک از مسیریاب­ها به­عنوان شعاع دایره مربوطه در نظر گرفته شده است. مجموعه برد انتقال مسیریاب­ها به صورت تعریف می­ شود. مجموعه ­ای با عنوان تعریف می­ شود که محدودیت­های جغرافیایی را در نظر می­گیرد؛ به این صورت که هر یک از اعضای مجموعه، یک محیط دایره­ای را نشان می­دهد که مرکز آن است و هیچ یک از MRها نمی ­توانند درون این ناحیه­ها قرار بگیرند. برای هر یک از MRها، نشان دهنده جایی است  که MR در آن قرار گرفته است، که همان مرکز دایره مربوطه می­باشد. در این مدل، یک دروازه اینترنت IGW، در نظر گرفته شده که در مرکز دیسک قرار دارد.
محودیت جغرافیایی گره MR گره IGW
شکل ‏۳‑۲ مدل شبکه
در شکل ۳-۲، مدل شبکه نشان داده شده است. دو گره مش به یکدیگر متصلند اگر فاصله اقلیدسی میان آن­ها، بزرگتر از مجموع برد انتقال آن­ها نباشد، به عبارت دیگر در صورتی که دو مسیریاب با هم همپوشانی داشته باشند، به یکدیگر متصل هستند، یعنی .
در مدل مورد استفاده، مسیریاب­ها می­توانند دارای برد رادیویی (برد انتقال) متفاوتی باشند و مسیریاب­هایی با برد رادیویی بیشتر (برد انتقال بیشتر)، قویتر در نظر گرفته شده است. به عبارت دیگر با توجه به مدل مورد استفاده، از دایره­هایی با شعاع بزرگتر برای نشان دادن مسیریاب­های قوی­تر استفاده شده است.
Rj
dij

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...