خلاصه پایان نامه بهینه سازی تعداد و مکان مسیریاب ها در شبکه های مش بی سیم
پایان نامه
برای دریافت درجه کارشناسی ارشد
مهندسی فناوری اطلاعات- شبکه های کامپیوتری
چکیده
شبکه های مش بیسیم، شامل مسیریابهای مش و کلاینتهای مش هستند، که مسیریابهای مش با کمترین تحرک، ستون فقرات شبکه مش را شکل میدهند. مسیریابها و کلاینتها در شبکه مش از طریق دروازه به اینترنت دسترسی پیدا میکنند. امروزه شبکههای مش بیسیم، سرویسهای بیسیم را در گستره متنوعی از کاربردها، در سطح شخصی، محلی، محوطههای دانشگاهی و نواحی شهری ارائه میدهد. یکی از اصلیترین چالشهای موجود در طراحی شبکه مش بیسیم، تعیین موقعیت مکانی مسیریابهای مش در شبکه است. در واقع، تعیین مکان مسیریابهای مش در ساختن یک شبکه مش بیسیم، اولین مرحله در تضمین کارایی مطلوب در شبکه است. مسئلهی اساسی در جایگذاری مسیریابهای مش، یافتن تعداد مسیریابهای مورد نیاز مش است به گونهای که معیارهای مورد نیاز این شبکه را برآورده کند. در این پایاننامه یک روش ابتکاری که با استفاده از الگوریتم ژنتیک، برای یافتن تعداد مسیریابها و موقعیت بهینه آنها پیشنهاد شده است. روش پیشنهادی میتواند معیارهای لازم این شبکه را به طور موثری تامین کند. نتایج حاکی از کارایی قابل قبول این روش دارد. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی از لحاظ تعداد مسیریابها و میزان فضای پوششی متناسب با آن، از روشهای مشابه، بهتر است.
کلمات کلیدی: شبکه مش بیسیم، تعیین موقعیت مکانی مسیریابها، پوشش، اتصال، الگوریتم ژنتیک.
1 فصل اول
مقدمهای بر شبکه های مش بیسیم
در این فصل ابتدا مقدمهای راجع به شبکههای مش بیسیم، کاربردها و خصوصیات آنها ارائه خواهد شد، سپس موضوع انتخاب شده در این پایاننامه و اهمیت آن بررسی میشود. در پایان ساختار پایاننامه مشخص میشود.
(تصاویر در فایل اصلی موجود است)
پیادهسازیهای اولیه شبکههای بیسیم مبتنی بر استاندارد IEEE 802.11، متشکل از چندین BSS[2] است. درون هر BSS یک ایستگاه به نام نقطه دسترسی(AP[3]) وجود دارد که برای دسترسی به ساختار سیمی به کار برده میشود، BSSها از طریق LANهای اترنت (ساختار سیمی) به هم متصل میشوند یا به اینترنت دسترسی پیدا میکنند. همانطور که در شکل 1-1نشان داده شده است، دو ایستگاه پایه وجود دارد و در هر کدام یک نقطه دسترسی قرار گرفته است.
نقاط دسترسی به شبکه سیمی وصل میشوند و از این طریق بین دو BSS ارتباط ایجاد میشود. این چنین شبکههایی، شبکههای تکگامه[4] با معماری ثابت هستند که قابلیت انعطافپذیری پایین و هزینه پیادهسازی بالایی دارند. برای تامین تحرکپذیری گرهها و چندگامه[5] بودن شبکه، شبکههای سیار موردی[6] بهوجود آمدند که حالت بدون ساختار را تشکیل میدهند. در این حالت ایستگاهها بدون هیچ هماهنگکننده مرکزی مثل نقطه دسترسی و یا یک سیستم توزیعی (ساختار سیمی) به هم متصل میشوند و گرهها کاملاً خودگردان هستند (شکل 1-2) [1].
(تصاویر در فایل اصلی موجود است)
شبکه های سیار موردی برای بسیاری از کاربردها مناسب نیستند چون همانطور که تحرک و چندگامه بودن مورد نیاز است دسترسی به اینترنت و مجتمع شدن با شبکههای دیگر نیز مورد نیاز است. بنابراین حالت دارای ساختار[7] و حالت بدون ساختار با هم ترکیب شدهاند و یک نوع جدید از شبکههای چند گامه به نام مش بیسیم را بهوجود آوردهاند.
شبکه بیسیم مش یک شبکه متشکل از چندین گره است که به طور بیسیم با هم ارتباط دارند و همانطور که از نام آن پیدا است بین همه گرهها به طور مستقیم یا غیرمستقیم مسیر ارتباطی وجود دارد. هر گره نه تنها به صورت یک میزبان[8] عمل میکند بلکه یک مسیریاب نیز عمل مینماید و بستهها را به گرههای دیگر که ممکن است در محدوده انتقال[9] گره مقصد نیز نباشند، ارسال میکند. شکل 1-3 نمای کلی از شبکه مش را نشان میدهد
(تصاویر در فایل اصلی موجود است)
یک شبکه مش بیسیم به صورت یک شبکه خودگردان[10] با تنظیم خودکار[11] است که گرههای موجود در آن به طور اتوماتیکی ارتباط را در میان خودشان راهاندازی و حفظ میکنند. این ویژگی مزیتهای زیادی مثل هزینه پایین، نگهداری آسان شبکه، نیرومندی و ارائه سرویس قابل اعتماد برای شبکههای بیسیم مش ایجاد کردهاست. گرههایی از قبیل(desktop، laptop، PDA و ...) به کارتهای شبکه بیسیم مجهز هستند و به طور مستقیم به شبکه مش وصل میشوند [1]. مشتریهای بدون کارت بیسیم از طریق وصل شدن به مسیریابهای مش بیسیم مثلاً با اترنت به شبکه مش دسترسی پیدا میکنند. بنابراین شبکههای مش بیسیم به کاربران کمک میکنند تا در هر زمان و هر مکانی فعال باشند. علاوه بر این تواناییهای دروازه[12] در مسیریابهای مش، امکان مجتمعشدن شبکه مش بیسیم را با شبکههای بیسیم موجود از قبیل حسگر[13]، Wi-Fi، Wi-MAX، Wi-Media و ... میدهد. در نتیجه از طریق یک شبکه مش مجتمع، کاربران درون شبکه مش میتوانند از سرویسهای موجود در شبکههای دیگر استفاده کنند. شبکههای مش بیسیم برای تعداد زیادی از کاربردها مانند، شبکهبندی خانگی ،... استفاده میشوند [1].
در قسمتهای بعد به معرفی شبکههای مش بیسیم از جنبههای مختلف پرداخته میشود.
1-2 معماری شبکه مش
شبکه مش بیسیم شامل دو نوع گره است: 1-مسیریاب و 2-کاربر.
یک مسیریاب مش بیسیم علاوه بر توانایی مسیریابی همانند شبکههای بیسیم قبلی، شامل تواناییهای مسیریابی اضافی برای راهاندازی و تامین شبکهبندی مش است. برای بهبود بیشتر شبکه مش، یک مسیریاب مش معمولا به چندین واسط[14] بیسیم مجهز میشود که بر اساس تکنولوژیهای دسترسی بیسیم مختلف یا یکسانی ساخته میشوند. یک مسیریاب مش در مقایسه با مسیریابهای قبلی، میتواند به پوشش یکسان با توانایی انتقال کمتر از طریق ارتباطات چندگامه برسد. با وجود این مسیریابهای مش بیسیم و مسیریابهای قبلی براساس یک بستر سختافزاری یکسان ساخته میشوند. مسیریابهای مش میتوانند براساس سیستمهای کامپیوتری embedded یا براساس سیستمهای کامپیوتری چند منظوره[15] ساخته شوند.
کاربران مش همچنین قابلیت کافی برای شبکهبندی مش را دارند و بنابراین میتوانند به صورت یک مسیریاب کار کنند. اگر چه توابع دروازه یا پل[16] در این گرهها وجود ندارد. به علاوه کلاینتهای مش معمولاً تنها یک واسط دارند. بستر سختافزار و نرمافزار برای کاربرهای مش آسانتر از مسیریابها ساخته میشود. کاربردهای مش تنوع محصول بیشتری نسبت به مسیریابها دارند و میتوانند desktop ، laptop،PDA و... باشند.
معماری شبکه مش بیسیم به سه گروه اصلی دستهبندی میشود:
شبکه ستون فقرات[17] ساختیافته: این نوع از شبکه مش بیسیم شامل مسیریابهای مش است و یک زیر ساختار را برای کاربران ایجاد میکند که به آنها متصل شوند. این مدل میتواند از چندین نوع تکنولوژی رادیویی استفاده کند که در بیشتر موارد از IEEE 802.11 استفاده میکنند. مسیریابهای مش لینکهای خودگردان و خودشفا[18] را بین خودشان ایجاد میکنند. با توانایی دروازه بودن، مسیریابهای مش میتوانند به اینترنت متصل شوند. این کاربرد یک ستون فقرات را برای کلاینتهای سنتی ایجاد میکند و امکان مجتمعشدن شبکه مش بیسیم را با شبکههای بیسیم موجود، میدهد. از طریق قابلیت دروازه در مسیریابهای مش، کلاینتهای سنتی با واسطهای اترنت میتوانند به مسیریابهای مش از طریق لینکهای اترنت وصل شوند. برای کلاینتهای با تکنولوژیهای رادیویی مشابه آنها میتوانند به طور مستقیم با مسیریابهای مش ارتباط برقرار کنند (شکل 1-4). این دسته رایجترین نوع استفاده از شبکههای مش هستند. برای مثال شبکههای ارتباط همسایهای[19] میتوانند از این مدل استفاده کنند. مسیریابهای مش در سقف خانهها قرار میگیرند و به صورت یک نقطه دسترسی برای کاربران درون خانه به کار میروند. معمولاً دو نوع رادیو در مسیریابها استفاده میشود: 1-برای ارتباطات ستون فقرات و 2- برای ارتباطات کاربر.
ارتباطات ستون فقرات مش میتوانند با استفاده از تکنیکهای ارتباطی محدوه زیاد، از قبیل آنتنهای جهتدار برقرار شوند [2].
(تصاویر در فایل اصلی موجود است)
شبکه کاربری: این روش ارتباط را در میان وسیلههای کاربر ایجاد میکند. در این نوع معماری، گرههای کلاینت یک شبکه واقعی را برای انجام مسیریابی و پیکربندی قابلیتهایی مانند ایجادکردن برنامههای کاربردی برای مشتریها تشکیل میدهند، در نتیجه مسیریاب مش برای این نوع کاربرد ندارد (شکل1-5). در این معماری یک بسته برای رسیدن به گره مقصد از چندین گام (چندین گره) عبور میکند. این روش معمولاً از یک نوع رادیو برای وسیلهها استفاده میکند. علاوه بر آن ملزومات برای کاربران انتهایی در مقایسه با مدل اول افزایش پیدا میکند زیرا در برخی از کابردها، کاربران انتهایی باید توابع اضافی از قبیل مسیریابی و تنظیم خودکار را نیز، انجام دهند.
(تصاویر در فایل اصلی موجود است)
شبکه ترکیبی[20]: این معماری ترکیبی از دو روش قبلی است، همانطور که در شکل 1-6 دیده میشود کاربران مش از طریق مسیریابهای مش به شبکه ارتباط و اتصال دارند. علاوه بر آن با دیگر کاربرهای مش به طور مستقیم ارتباط دارند. در عین حال که شبکه زیر ساختار اتصال به دیگر شبکهها مثل Wi-Fi، Wi-MAX، سلولی[21] و ... را ایجاد میکند، تواناییهای مسیریابی کلاینتها، اتصال و میزان پوشش را نیز در شبکه بهبود میبخشد. این مدل نسبت به دو مدل قبلی کاربردیتر است[2].
1-3 ویژگیهای شبکه مش بیسیم
ویژگیهای شبکههای مش بیسیم به شرح زیر میباشد:
چندگامه بودن: یک هدف برای گسترش شبکههای مش، گسترش محدوده تحت پوشش شبکه مش بدون قربانیکردن و هدردادن ظرفیت کانال است. هدف دیگر ایجاد کردن اتصال خارج از محدوده دید مستقیم در میان کاربران، بدون لینکهای مستقیم است. برای برآوردن این نیازها، شبکهبندی مش چندگامه ضروری است. در این شبکه میتوان با استفاده از فاصله لینک کمتر، تداخل[22] کمتر بین گرهها و بهره بردن از استفاده دوباره فرکانس[23] به گذردهی بالاتر بدون هدر دادن محدوده رادیویی مفید رسید.
حمایت از شبکهبندی سیار موردی و توانایی تنظیم خودکار، خودشفایی و خودگردانی: شبکههای مش بیسیم به خاطر معماری قابلانعطاف شبکه، توسعهپذیری، پیکربندی آسان و تحمل خطا کارایی شبکه را بالا میبرند. به خاطر این ویژگیها، این شبکهها هزینه پایینی دارند و شبکه میتواند هر وقت که نیاز باشد، بهتدریج رشد کند.
تحرکپذیری وابسته به نوع گره: مسیریابهای مش معمولاً کمترین تحرک را دارند در حالی که کاربران مش میتوانند ساکن یا متحرک باشند.
چندین روش دسترسی به شبکه: در شبکههای مش بیسیم هم دسترسی چندگامه به اینترنت و هم ارتباطات همتا به همتا[24] میان کاربران وجود دارد. علاوه بر آن شبکههای مش بیسیم میتوانند با دیگر شبکههای بیسیم مجتمع شوند و سرویسهایی به کاربران انتهایی این شبکهها ارائه دهند.
محدودیت انرژی وابسته به نوع گره: مسیریابهای مش معمولاً محدودیت خاصی روی مصرف توان ندارند، اما کلاینتهای مش ممکن است نیاز به پروتکلهای کارائی توانی[25] داشته باشند. به عنوان یک مثال، یک حسگر با قابلیت مش برای اینکه کارائی توانی داشته باشد نیاز به پروتکلهای ارتباطی خاص خودش دارد. بنابراین پروتکلهای لایه شبکه و لایه انتقال که برای مسیریابهای مش بهینه میشوند، ممکن است برای کاربران مش مثل حسگرها مناسب نباشند، چون کارائی توانی یک نگرانی اصلی برای شبکههای حسگر بیسیم است.
(تصاویر در فایل اصلی موجود است)
Abstract
فهرست پایان نامه بهینه سازی تعداد و مکان مسیریاب ها در شبکه های مش بی سیم
فهرست:
فصل اول: مقدمهای بر شبکههای مش بیسیم- 1
1-1 شبکه مش بیسیم- 2
1-2 معماری شبکه مش-- 5
1-3 ویژگیهای شبکه مش بیسیم- 9
1-4 تفاوت با سایر شبکههای چندگامه 11
1-5 چالشهای موجود در شبکههای مش بیسیم- 13
1- 6 اهداف پایاننامه 17
1- 7 ساختارپایان‌نامه 18
فصل دوم: مروری بر روشهای تعیین مکان مسیریابها در شبکه مش بیسیم- 19
2-1 مقدمه 20
2-2 مروری بر کارهای انجام گرفته 21
2-2-1 روشهای مبتنی بر الگوریتمهای ابتکاری- 21
2-2-2 روشهای مبتنی بر الگوریتمهای تکاملی- 27
2-2-3 روشهای مبتنی بر مدل بهینهسازی- 28
2-2-4 سایر روشها 31
2-3 نتیجهگیری- 34
فصل سوم: معرفی الگوریتم پیشنهادی بر مبنای الگوریتم ژنتیک-- 36
3-1 مقدمه 37
3-2 معرفی Packing Problem- 37
3-3 مسئله Circle Packing 38
3-4 مدل شبکه 39
3-5 فرموله سازی مسئله 41
3-6 الگوریتم ژنتیک-- 42
3-6-1 کروموزوم 43
3-6-2 جمعیت ژنتیکی- 43
3-6-3 تابع برازش-- 43
3-6-4 عملیات ژنتیکی- 44
3-6-5 پارامترهای الگوریتم ژنتیکی- 44
3-6-6 روشهای کدگذاری- 45
3-6-7 عملگرهای ژنتیکی- 46
3-6-8 ساختار الگوریتم پیشنهادی- 50
3-7 مدل ترافیک-- 56
3-8 تعیین تعداد مسیریابها 59
3-9 نتیجهگیری- 60
فصل چهارم: شبیهسازی و ارزیابی روش پیشنهادی- 62
4-1 مقدمه 63
4-2 مقایسه با مرجع [10] 63
4-3 مقایسه با مرجع [12] 66
4-4 تعیین تعداد مسیریابها 73
فصل پنجم: نتیجهگیری و پیشنهادات- 76
5-1 مقدمه 77
5-2 نتیجهگیری- 77
5-3 پیشنهادات- 79
واژه‌نامه انگلیسی به فارسی- 81
منابع- 86
منبع:
1
[1] A.O.L. Xudong Wang, wireless mesh networks: Framework and challenges, Ad Hoc Networks 6 (2008) 970-984.
[2] I.F. Akyildiz, X. Wang, W. Wang, Wireless mesh networks: a survey, Computer Networks 47 (2005) 445–487.
[3] Y. Zhang, J. Luo, H. Hu, Wireless Mesh Networking, architecture,protocols and standards, ISBN: 978-0-8493-7399-2,2007.
[4] M. Sichitiu, wirelessmeshnetworks: opportunities and challenges, Technical Report, 2005.
[5] J. Wang, B. Xie, K. Cai, D.P. Agrawal, Efficient Mesh Router Placement in Wireless Mesh Networks, in Mobile Adhoc and Sensor Systems, IEEE Internatonal Conference on 2007 pp. 1-9.
[6] F. Xhafa, Admir Barolli, Christian Sánchez, L. Barolli, A simulated annealing algorithm for router nodes placement problem in Wireless Mesh Networks. Simulation Modelling Practice and Theory, In Press, Corrected Proof (2010).
[7] F. Xhafa, C. Sanchez, L. Barolli, Ad Hoc and Neighborhood Search Methods for Placement of Mesh Routers in Wireless Mesh Networks, in Distributed Computing Systems Workshops, IEEE International Conference on 2009, pp. 400 - 405.
[8] F. Xhafa, C. Sanchez, L. Barolli, Locals Search Algorithms for Efficient Router Nodes Placement in Wireless Mesh Networks in Network-Based Information Systems, International Conference on 2009, pp. 572 – 579.
[9] A.A. Franklin, C.S.R. Murthy, Node Placement Algorithm for Deployment of Two-Tier Wireless Mesh Networks in Global Telecommunications Conference,GLOBECOM '07, IEEE 2007, pp. 4823 – 4827.
[10] J. Wang, W. Fu, D.P. Agrawal, An Adaptive Router Placement Scheme for Wireless Mesh Networks, in GLOBECOM Workshops, IEEE 2008, pp. 1-5.
[11] J. Wang, K. Cai, D.R. Agrawal, A Multi-Rate Based Router Placement Scheme for Wireless Mesh Networks, in Mobile Adhoc and Sensor Systems, IEEE 6th International Conference on 2009, pp. 100 – 109.
[12] F. Xhafa, C. Sánchez, L. Barolli, Genetic Algorithms for Efficient Placement of Router Nodes in Wireless Mesh Networks, in Advanced Information Networking and Applications, IEEE International Conference 2010, pp. 465 - 472.
[13] G. De Marco, MOGAMESH: A multi-objective algorithm for node placement in wireless mesh networks based on genetic algorithms in Wireless Communication Systems, International Symposium 2009, pp. 388 – 392.
[14] D. Benyamina, N. Hallam, Multi-criteria Optimization Approach for the Deploymen Planning Problem of Multi-hop Wireless Networks in CIS'09 Proceedings of the international conference on Computational and information science, 2009, pp. 1-7.
[15] S.M. Allen, R.M. Whitaker, S. Hurley, Seed node deployment for wireless mesh networks with uncertain subscription, in Wireless Telecommunications Symposium 2007, pp. 1-7.
[16] A.C. E. Amaldi, M. Cesana, I. Filippini, F. Malucelli, Optimization models and methods for planning wireless mesh networks Computer Networks 52 (2008) 2159-2171.
[17] J. Robinson, M. Singh, R. Swaminathan, E. Knightly, Deploying Mesh Nodes under Non-Uniform Propagation, in INFOCOM, Proceedings IEEE 2010, pp. 1-9.
[18] X. Wang, L. Guan, C. Xuefen, G. Xin, Investigation of Relaying Node Placement in Wireless Mesh Networks, in Computer Modeling and Simulation, 2010, pp. 467 – 471.
[19] R. R., S. Iyer, Designing Multi-Tier Wireless Mesh Networks: Capacity-Constrained Placement of Mesh Backbone Nodes, in INFOCOM. 25th IEEE International Conference on Computer Communications. Proceedings 2006, pp. 1-6.
[20] A. So, B. Liang, Optimal Placement of Relay Infrastructure in Heterogeneous Wireless Mesh Networks by Bender’s Decomposition, in QShine '06 Proceedings of the 3rd international conference on Quality of service in heterogeneous wired/wireless networks, 2006, pp. 1-4.
[21] Genetic Algorithms for the Antenna Placement Problem. Mobile Networks and Applications 10 (2005) 79–88.
[22] P. Calégari, F. Guidec, P. Kuonen, F. Nielsen, Combinatorial Optimization Algorithms for Radio Network Planning. Theoretical Computer Science (2001) 235–245.
[23] A. Beljadid, A.S. Hafid, M. Gendreau, Optimal Design of Wireless Mesh Networks, in IEEE Global Telecommunications Conference, 2007, pp. 4840–4845.
[24] J. Robinson, E.W. Knightly, A Performance Study of Deployment Factors in Wireless Mesh Networks, in INFOCOM. 26th IEEE International Conference on Computer Communications, 2007, pp. 2054 – 2062.
[25] T. Vanhatupa, M. Hännikäinen, T.D. Hämäläinen, Performance model for IEEE 802.11s wireless mesh network deployment design. Parallel and Distributed Computing 68 (2008) 291-305.
[26] P.Y. Wang, G. Wa ¨scher, Cutting and packing, European Journal of Operational Research 141 (2002) 239–240.
[27] K.A. Dowsland, Palletisation of cylinders in cases, OR Spektrum 13 (1991) 171–172.
[28] G. Wa ¨scher, H. Haussner, H. Schumann, An improved topology of cutting and packing problems, European Journal of Operational Research 183 (2007) 1109–1130.
[29] E. Bischoff, G. Wa¨scher, Cutting and packing, European Journal of Operational Research 84 (1995) 503–505.
[30] A. Lodi, S. Martello, M. Monaci, Two dimensional packing problems: A survey, European Journal of Operational Research 141(2002) 241–252.
[31] Y.-C. Xu, R.-B. Xiao, M. Amos, A Novel Genetic Algorithm for the Layout Optimization Problem, in Evolutionary Computation, IEEE Congress, 2007, pp. 3938 – 3943.
[32] C. L. Karr, L.M. Freeman, Industrial Applications of genetic Algorithms, CRC Press, 1999.
[33] C. David, An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific, 1999.