پایان نامه مقطع کارشناسی
سال 1385
پيشگفتار
امروزه شبكه‌هاي بي‌سيم به دليل كاربردهايي كه دارد و همچنين سرويسهايي كه ارائه مي‌دهد، رشد چشمگيري داشته است. اين شبكه‌ها در حال توسعه سريعي هستند و سرويسهاي ارائه شده هم مرتباً بيشتر و بهتر میشود، در آينده‌اي نه چندان دور، تكنولوژي اطلاعات بر پايه مخابرات بي‌سيم خواهد بود. از آنجاييكه ايجاد شبكه با زيرساخت باعث محدوديت در شبكه‌هاي موبايل و سلولی معمولي خواهد كرد؛ لذا شبكه‌هاي بدون زير ساخت مي‌تواند ايده خوبي براي ادامه مخابرات بي‌سيم باشد. شبكه‌هاي ادهاك، بدليل عدم نياز به زيرساختار، محدوديت شبكه‌هاي موبايل را مرتفع خواهد كرد.
شبكه‌هاي Ad–hoc براي اولين بار توسط وزارت دفاع آمريكا در سيستم‌هاي نظامي و عملياتي خود مورد استفاده قرار گرفته است. ليكن از سال 1970 بطور عمومي مورد استفاده ميباشد.
در اين پروژه هدف ارائه الگوريتم مسيريابي پيشنهادي مبتني بر خوشه يابي مي باشد.
در اين راستا ابتدا در فصل اول به تقسيم بندي و توضيح شبكه هاي ادهاك و مروري بر پروتكلهاي مسيريابي آن خواهيم پرداخت و سپس در فصل دوم عناصر مورد استفاده جهت شبيه سازي شبكه هاي MANET كه شامل مدل هاي حركت و ابزار شبيه سازي مي باشد مورد بررسي قرار مي گيرد و نيز فصل آخر را به بررسي الگوريتم هاي خوشه يابي و ارائه يك الگوريتم پيشنهادي و همچنين ارزيابي كارائي آن نسبت به ساير روش هاي خوشه يابي اختصاص داده ايم و فصل چهارم ننتيجه گيري و پيشنهاد براي آينده و در پايان نيز به طرح يك مقاله شخصي كه شامل خلاصه اين رساله مي باشد پرداخته ايم، با اميد به ايجاد انگيزه اي دو چندان در جهت پيشرفت هاي علمي، عزت و سلامت همه عزيزان را از درگاه ايزدمنان خواستارم.
فصل اول
شبكه‌هاي Ad Hoc
1-1 تقسيم‌بندي شبكه‌هاي بي‌سيم[1]
شبكه هاي بي‌سيم را از نظر معماري مي توان به دو گروه اصلي تقسيم بندي نمود:
الف) شبكه هاي داراي زيرساخت[2]
مسيريابهايي كه در اين نوع شبكه‌ها مورد استفاده قرار مي‌گيرند، اصطلاحاً به ايستگاههاي ثابت شهرت دارند. اين ايستگاههاي پايه‌اي قابليت حركت ندارند، با روشهاي مختلف و با امكانات سرعت بالا به يكديگر متصل هستند. هر واحد متحرك در زمان برقراري ارتباط و نيز ردو بدل كردن اطلاعات، به نزديكترين ايستگاه پايه‌اي متصل مي شود. در نتيجه ارتباطات بي‌سيم در اين نوع شبكه‌ها، بر اساس ارتباط سيمي[3] بين ايستگاه هاي پايه‌اي صورت مي پذيرد. اين شبكه‌ها همچنين به شبكه‌هاي بي‌سيم يك‌گامي[4] نيز شهرت دارند. شبكه‌هاي مخابرات سلولي و شبكه‌هاي PCS[5] مثالهايي از اين نوع شبكه‌هاي بي‌سيم هستند. در شبكه‌هاي يك‌گامي گره‌هاي متحرك همواره تحت پوشش ايستگاههاي پايه قرار دارند و در نتيجه ارتباط پيوسته‌اي با ايستگاههاي پايه دارند.
شكل 1-1 مثالي از شبكه‌هاي داراي زيرساخت
ب) شبكه هاي فاقد زيرساخت[6]
در اين شبكه ها كه به شبكه هاي MANET[7] نيز شهرت دارند، هيچ زير ساخت از پيش تعريف شده اي براي برقراري ارتباط بين گره ها وجود ندارد. هر گره قابليت مسيريابي را داراست در عين حال، قادر است در هر جهتي حركت كند و همچنين به گره هاي ديگر نيز متصل شود. به همين دليل، اطلاعات ارسالي از يك گره به گره ديگر بدليل فاصله دو گره مزبور ممكن است در صورت نياز از چند گره ديگر عبور كند. درنتيجه، اين شبكه ها را شبكه هاي بي‌سيم چندگامي[8] نيز مي‌نامند. در اين پروژه، اين دسته از شبكه‌هاي بي‌سيم مورد بحث و بررسي قرار مي گيرند.
شكل 1-2 نمونه‌اي از شبكه‌هاي فاقد زير ساخت
باتوجه به اينكه هيچ زيرساخت ارتباطي ويا ادوات سخت افزاري جانبي جهت راه‌اندازي و مديريت شبكه مورد نياز نيست، با روشن شدن و فعال شدن گرهها، شبكه تشكيل ميشود. بدين ترتيب سادگي و سرعت راه‌اندازي شبكه از خصوصيات شبكه‌هاي MANET ميباشد.
اينگونه شبكه‌ها در مواردي مورد استفاده قرار مي‌گيرند كه هيچ ساختار ارتباطي ديگري موجود نباشد. با وجود اينكه انتظار مي رود كاربردهاي اين نوع شبكه‌ها جنبه اقتصادي داشته باشند ولي بيشتر كاربردهاي مطرح شده تاكنون جنبه نظامي داشته‌اند. اين امر نيز طبيعي به نظر مي رسد و در ميدان جنگ و يا موارد كمك رساني و امداد در مناطقي كه امكانات مخابراتي در دسترس نمي باشند، اين شبكه ها تنها راه عملي براي ارسال داده به شمار مي روند.
شبكه‌هاي موسوم به PRNET[9] كه در سال 1973 توسط DARPA[10] طراحي و مورد استفاده قرارگرفته‌اند ]1[ ، اولين شبكه‌هاي پيشنهادي از نوع MANET به شمار مي‌روند. هدف از طراحي اين شبكه، فراهم آوردن ارتباط كامپيوتري بين ترمينالهاي متحرك بود. اين شبكه درحقيقت به يك محيط براي تحقيقات و همچنين توسعه پروتكلهاي مسيريابي شبكه‌هاي MANET تبديل شد. شبكه‌هاي HF ITF نمونه ديگري از شبكه‌هاي MANET هستند كه با ارائه يك الگوريتم مسيريابي توزيعي و سلسله‌مراتبي طراحي شدند. اكنون با ارائه فناوريهاي مختلف بي‌سيم و وفور كاربرد آنها، شبكه‌هاي MANET، بيشتر مورد توجه محققين قرارگرفته‌اند. با گسترش تحقيقات در مورد شبكه‌هاي MANET ، IETF گروه كاري MANET را مسؤل تدوين استاندارد هاي مربوط به اين شبكه‌ها نموده‌است.
خصوصيات مهم شبكه هاي ad-hoc را مي توان به صورت زير برشمرد ]3 [:
-
-
-
-
1-2 مروري بر پروتكلهاي مسيريابي در شبكه‌هاي MANET
دراين قسمت مروري خواهيم داشت بر الگوريتمهاي مسيريابي كه تاكنون جهت شبكه‌هاي MANET ارائهشدهاند. شكل 1-3 نشان‌دهنده تقسيم‌بندي الگوريتمهاي ارائه شده ميباشد ]2[.
شكل 1-3 تقسيم‌بندي پروتكلهاي مسيريابي شبكه‌هاي MANET
1-2-1 الگوريتمهاي مسيريابي مسطح[13]
در اين دسته از پروتكلهاي مسيريابي، نقش كليه گرهها درامر مسيريابي يكسان است و كليه گرهها به لحاظ سخت‌افزاري و نرم‌افزاري و همچنين عملكرد در امر مسيريابي، با يكديگر يكسان هستند و هيچ دسته‌بندي بين گرهها صورت نمي‌پذيرد. تخصيص آدرس به گرهها نيز در اين الگوريتمها، بر هيچ قانوني استوار نيست و مي‌تواند كاملا تصادفي صورت پذيرد. پروتكلهاي مسيريابي مسطح را مي توان به صورت كلي به دو گروه تقسيم بندي كرد:
- پروتكلهاي مسيريابي Table-driven (Proactive)
- پروتكلهاي مسيريابي On-Demand (Reactive)
1-2-1-1 پروتكلهاي مسيريابي Table Driven
اين دسته از پروتكلهاي مسيريابي كه در ابتداي مطرح شدن شبكه‌هاي MANET ارائهشدهاند، بر روشهاي مسيريابي معمول در شبكه‌هاي ثابت، مانند روشهاي DV[14] و LS[15] تكيه مي‌كنند. در نتيجه مشابه الگوريتمهاي مزبور، در هر گره جداولي از اطلاعات مربوط به مسيريابي نگهداري ميشوند. با توجه به تحرك گرهها و تغيير توپولوژي شبكه، كه مهمترين تفاوت شبكه‌هاي MANET و شبكه‌هاي ثابت ميباشد، اطلاعات موجود در اين جداول با هر تغيير در شبكه بايد اصلاح شوند تا از هماهنگي[16] جداول در گره‌هاي مختلف اطمينان حاصل شود. عموماً در اين دسته از پروتكلهاي مسيريابي، اطلاعات مسيريابي توسط هر گره بصورت دورهاي و در زمانهاي مشخص به ديگر گرهها بصورت بسته‌هاي حاوي اطلاعات كنترلي ارسال ميشود. پروتكلهاي مسيريابي كه در اين گروه قرار مي‌گيرند، بر حسب تعداد جداول و اطلاعاتي كه در اين جداول قرار مي گيرند و همچنين از لحاظ روش ارسال اطلاعات مسيريابي به ديگر گرهها، تقسيم بندي مي شوند.
كليه پروتكلهاي مسيريابي كه بر اساس الگوريتمهاي DV عمل مي كنند، از نوع پروتكلهاي Table-Driven محسوب مي شوند. نقطه ضعف عمده اين الگوريتمها اين است كه سرعت همگرايي نسبت به تغييرات شبكه كه از تحرك گرهها ناشي ميشود پايين است.
در ادامه به شرح برخي از پروتكلهاي Table – Driven مي پردازيم.
1-2-1-1-1 پروتكل مسيريابي DSDV
DSDV يك نسخه بهبود يافته از DBF است. درDSDV، هيچگاه حلقه رخ نخواهد داد. اطلاعاتي كه در هر گره نگهداري ميشود، شامل آدرس گرهها و همچنين تعداد گره‌هاي مياني جهت دسترسي به آن گره است. هر سطر اين جدول با يك عدد شمارشي[17] علامت گذاري ميشود. اين اعداد جهت تشخيص مسيرهاي جديد از مسيرهاي قديمي و خارج از رده[18] مورد استفاده قرار مي‌گيرند تا از تشكيل حلقه جلوگيري به عمل آيد. جداول مسيريابي به صورت دورهاي و جهت ايجاد سازگاري بين گره‌هاي شبكه به ديگر گرهها ارسال مي شوند. اين امر باعث ايجاد ترافيك نسبتاً زيادي در شبكه مي شود. جهت تعديل و كاهش اثرات اين ترافيك، دو نوع بسته كنترلي، جهت ارسال تغييرات اين جداول به ديگر گره‌هاي شبكه مورد استفاده قرار مي گيرند:
الف) Full Dump : اين بسته ها حاوي كليه اطلاعات مسيريابي هستند.
ب)Incremental Packets : اين بسته ها صرفاً اطلاعاتي را حمل مي كنند كه از زمان ارسال آخرين بسته Full Dump، تغيير كرده‌اند. در نتيجه هر گره بايد جدولي نيز داشته باشد تا اطلاعات Incremental را نگهداري نمايد.
[1] - Wireless Networks
[2] - Infra Structured Networks
[3] - Wired
[4] - Single Hop
[5] - Personal Communication System
[6] - Infra Structure-less Networks
[7] - Mobile Ad Hoc Networks
[8] - Multi Hop
[9] - Packet Radio Network
[10] - Defense Advanced Research Projects Agency
[11] - Computational Power
[12] - Storage Capacity
[13] - Flat Routing Algorithms
[14] - Distance Vector
[15] - Link State
[16] - Consistency
[17] - Sequence Number
[18] - Stale Routes
مراجع
Jubin and Tornow, “The DARPA Packet Radio Network Protocols”, in the Proceedings of the IEEE, Special Issue on Packet Radio Networks, Jan 1987, vol.75, pp.21-32.
Xiaoyan Hong,Kaixin Xu, and Mario Gerla, “Scalable Routing Protocols for Mobile Ad Hoc Networks”, IEEE Network Magazine,July-Aug, 2002, pp.11-21.
Tomochika Ozaki, Jaime Bae Kim and Tatsuya Suda, “Bandwidth-Efficient Multicast Routing for Multihop, Ad-Hoc Wireless Networks”, in Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, USA, April 2001, pp.1182-1191.
“Ad hoc On-Demand Distance Vector (AODV) Routing”, http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-10.txt, IETF Internet draft, Jan 2002
“The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)”, http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-07.txt, IETF Internet draft, Feb 2002
P. Gupta and P.R. Kumar, “The Capacity of Wireless Networks”, in IEEE Transactions on Information Theory, vol. IT-46, no. 2, March 2000, pp.388-404.
7.
C. E. Perkins, E. M. Royer, S. R. Das, and M. K. Marina, "Performance comparison of two on-demand routing protocols for ad hoc networks," IEEE Personal Communications, Feb 2001, vol. 8, pp. 16 - 28.
I. Aron and S. K. S. Gupta, “On the scalability of on-demand routing protocols for mobile ad hoc networks: an analytical study”, in Journal of Interconnection Networks (JOIN), Vol. 2, No.1, March 2001, pp.5-29.
10.
11.
12.(INFOCOM’2003)
13.
Kaixin Xu, Xiaoyan Hong, and Mario Gerla, "An Ad Hoc Network with Mobile Backbones", in Proceedings of IEEE ICC'02, New York, NY, Apr 2002, pp.3138-3143.
Z.J. Haas and M.R. Pearlman “The Performance of Query Control Schemes for the Zone Routing Protocol," ACM/IEEE Transactions on Networking, vol.9, no.4, August 2001, pp.11-18.
J. Broch, D. Maltz, D. Johnson, Y.-C. Hu, and J. Jetcheva, “A Performance Comparison of Multihop Wireless Ad Hoc Network Routing Protocols“, in Proceedings of the IEEE/ACM MOBICOM ’98, Oct. 1998, pp. 85–97.
17.
F. Bai, A. Helmy, "A Survey of Mobility Modeling and Analysis in Wireless Adhoc Networks", Book Chapter in the book on "Wireless Ad Hoc and Sensor Networks", Kluwer Academic Publishers, June 2004.
19.
J. Yoon, M. Liu and B. Noble, "Random Waypoint Considered Harmful", In Proceedings of the 22nd Conference of the IEEE Computer and Communications Society(INFOCOM’2003), April 2003, San Francisco, CA, pp.1312-1321.
Qunwei Zheng, Xiaoyan Hong, and Sibabrata Ray, "Recent advances in mobility modeling for mobile ad hoc network research", In Proceedings of the 42nd annual Southeast regional conference, Alabama, USA, April 2004, pp.70-75.
Elizabeth M. Royer, P. Michael Melliar-Smith, and Louise E. Moser. "An Analysis of the Optimum Node Density for Ad hoc Mobile Networks", in Proceedings of the IEEE International Conference on Communications(ICC’2001), Helsinki, Finland, June 2001.
23.
24.
25.
Mineo Takai, Jay Martin and Rajive Bagrodia, "Effects of Wireless Physical Layer Modeling in Mobile Ad Hoc Networks", Proceedings of the 2001 ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc 2001), October 2001, pp.87-94.
M. Gerla, G. Pei, and S.-J. Lee, "Wireless, Mobile Ad-Hoc Network Routing" in Proceedings of IEEE/ACM WINLAB/Berkeley FOCUS, New Brunswick, NJ, May 1999.
G. Pei, M. Gerla, and T.-W. Chen, “Fisheye State Routing in Mobile Ad Hoc Networks,” in Proceedings of ICDCS Workshop on Wireless Networks and Mobile Computing, Taipei, Taiwan, Apr.2000, pp.D71-D78.
S.-J. Lee, M. Gerla, “Dynamic Load-Aware Routing in Ad hoc Networks” in Proceedings of IEEE International Conference on Communications (ICC’2001), Helsinki, Finland, June 2001, pp. 3206-3210.
S. Lee, W. Su, and M. Gerla, "Exploiting the unicast functionality of the on-demand multicast routing protocol," in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC’2000), Chicago, IL, Sept 2000, pp.1317-1322.
S.-J. Lee and M. Gerla, “AODV-BR: Backup Routing in Ad hoc Networks” in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC’2000), Chicago, IL, Sep. 2000, pp.1311-1316.
S.J. Lee and M. Gerla, “Split Multipath Routing with Maximally Disjoint Paths in Ad hoc Networks” in Proceedings of IEEE International Conference on Communications (ICC’2001), Helsinki, Finland, June 2001, pp.3201-3205.
E. M. Royer and C. E. Perkins, “Multicast Ad hoc On-Demand Distance Vector (MAODV) Routing”, draft-ietf.manet-maodv-00.txt, IETF Internet draft, July 2000.
Elizabeth M. Belding-Royer. "Hierarchical Routing in Ad hoc Mobile Networks", Wireless Communication & Mobile Computing, 2(5), pp. 515-532, 2002.
Ian D. Chakeres and Elizabeth M. Belding-Royer. "The Utility of Hello Messages for Determining Link Connectivity." Proceedings of the 5th International Symposium on Wireless Personal Multimedia Communications (WPMC) 2002, Honolulu, Hawaii, October 2002.
Kimaya Sanzgiri, Bridget Dahill, Brian N. Levine, Clay Shields, and Elizabeth M. Belding-Royer. "A Secure Routing Protocol for Ad hoc Networks", in Proceedings of the International Conference on Network Protocols (ICNP’2002), Paris, France, November 2002.
Elizabeth M. Belding-Royer and Charles E. Perkins. "Transmission Range Effects on AODV Multicast Communication", in ACM/Kluwer Mobile Networks and Applications special issue on Multipoint Communication in Wireless Mobile Networks, 2002, 7(6), pp. 455-470.
38. Kaixin Xu,Mario Gerla, “A Heterogeneous Routing Protocol Based on a New Stable Clustering Scheme”, in Proceedings of IEEE MILCOM 2002, Anaheim, CA, Oct. 2002, pp.838-843.
39.
40.Q2SWinet'2005
41.
42.
F. Garcia, J. Solano and I. Stojmenovic, “Connectivity based k-hop clustering in wireless networks”, in Telecommunication Systems, vol.22, 1-4, pp. 205-220, 2003.
A.D. Amis, R. Prakash, T.H.P. Vuong and D.T. Huynh. “Max-Min D-Cluster Formation in Wireless Ad Hoc Networks”, in Proceedings of IEEE INFOCOM'2000, Tel Aviv, March 2000, pp.32-41.