.:رویال آی تی:.

پایان نامه مسيريابي مبتني بر ناحيه بندي در شبكه هاي Ad Hoc

فهرست مطالب

پيشگفتار۱

فصل اول ۲

شبكه‌هاي Ad Hoc2

۱-۱ تقسيم‌بندي شبكه‌هاي بي‌سيم ۲

۱-۲ مروري بر پروتكلهاي مسيريابي در شبكه‌هاي MANET 6
۱-۲-۱ الگوريتمهاي مسيريابي مسطح۶

۱-۲-۱-۱ پروتكلهاي مسيريابي Table Driven7

۱-۲-۱-۱-۱  پروتكل مسيريابي DSDV 8

۱-۲-۱-۱-۲ پروتكل مسيريابي WRP 8

۱-۲-۱-۲ پروتكلهاي مسيريابي on-Demand 9

۱-۲-۱-۲-۱ پروتكل مسيريابي AODV 10

۱-۲-۱-۲-۲ پروتكل مسيريابي DSR 12

۱-۲-۱-۲-۳ ظرفيت شبكه هاي بي‌سيم و محدوديت الگوريتمهاي On-Demand  ۱۴

۱-۲-۲ الگوريتمهاي مسيريابي سلسله‌مراتبي ۱۵

۱-۲-۲-۱ مفهوم خوشه‌يابي ۱۸

۱-۲-۲-۲ مزاياي استفاده از خوشه‌يابي ۲۰

۱-۲-۲-۳ الگوريتمهاي مسيريابي سلسله‌مراتبي مبتني بر خوشه‌يابي ۲۲

فصل دوم ۲۵

عناصر مورد استفاده جهت شبيه‌سازي شبكه‌هاي MANET25

۲-۱ تكنولوژي بي‌سيم مورد استفاده در شبيه سازي شبكه هاي  Ad Hoc 25

۲-۲ مدلهاي تحرك ۳۰

۲-۲-۱ مدل‌هاي تحرك تصادفي ۳۱

۲-۲-۲ مدل تحرك با وابستگي لحظه‌اي ۳۲

۲-۲-۳ مدل تحرك با وابستگي فضايي ۳۳

۲-۲-۴ مدلهاي تحرك با محدوديت جغرافيايي ۳۵

۲-۲-۵ خصوصيات مدل تحرك Random Waypoint 35

۲-۳ ابزار شبيه‌سازي ۳۸

فصل سوم ۴۲

خوشه‌يابي ۴۲

۳-۱ مروري بر الگوريتمهاي خوشه‌يابي ۴۲

۳-۲ پارامترهاي كارايي در روشهاي خوشه‌يابي ۵۰

۳-۳ الگوريتم خوشه‌يابي پيشنهادی ۵۲

۳-۳-۱ تشخيص گره‌های همسايه ۵۴

۳-۳-۲ شکل گيری خوشه‌ها ۵۵

۳-۳-۳ پيکربندی مجدد خوشه‌ها ۵۸

۳-۳-۴ ارزيابی کارايی ۶۵

فصل چهارم۷۷

نتيجه‌گيري و پيشنهاد براي آينده ۷۷

ضميمه ۱ ( واژه‌نامه ) ۸۰

ضميمه ۲ ( عبارتهاي اختصاري ) ۸۲

مراجع ۸۶

مقاله خلاصه پايان نامه۸۹

مراجع

1. 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.
2. Xiaoyan Hong,Kaixin Xu, and Mario Gerla, “Scalable Routing Protocols for Mobile Ad Hoc Networks”, IEEE Network Magazine,July-Aug, 2002, pp.11-21.
3. 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.
4. “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
5. “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
6. 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. Piyush Gupta, Robert Gray, and P. R. Kumar, “An Experimental Scaling Law for Ad Hoc Networks”, Technical report, University of Illinois at UrbanaChampaign, csl.uiuc.edu/~prkumar, May 16, 2001,
8. 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.
9. 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. Li, C. Blake, D.S.J. De Couto, H. Lee, R. Morris, “Capacity of Ad Hoc wireless networks”, in Proceedings of the 7th annual international conference on Mobile computing and networking (MOBICOM’۲۰۰۱), Rome, Italy, 2001, pp.61-69.
11. Matthias Grossglauser, David Tse, “Mobility increases the capacity of ad hoc wireless networks”, IEEE/ACM Transactions on Networking (TON), Aug 2002, vol.10, pp.477-486.
12. Nikhil Bansal, Zhen Liu, “capacity delay and mobility in wireless ad hoc networks”, In Proceedings of the 22nd Conference of the IEEE Computer and Communications Society(INFOCOM’۲۰۰۳), April 2003, san Francisco, CA, pp.1553-1563.
13. Lin and N.B. Shroff, “Towards Achieving the Maximum Capacity in Large Mobile Wireless Networks under Delay Constraints”, Journal Of Communication and Networks (JCN), Dec 2004, vol.6, no.4, pp.352-361.
14. 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.
15. 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.
16. 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 ’۹۸, Oct. 1998, pp. 85–۹۷٫
17. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models for Ad Hoc Network Research”, Wireless Communication & Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, vol.2, no.5, 2002, pp. 483-502.
18. 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. Christian Bettstetter, Hannes Hartenstein, and Xavier Perez-Costa, “Stochastic Properties of the Random Waypoint Mobility Model”, in ACM/Kluwer Wireless Networks, Special Issue on Modeling and Analysis of Mobile Networks, vol. 10, no. 5, Sept 2004, pp.555-567.
20. Yoon, M. Liu and B. Noble, “Random Waypoint Considered Harmful“, In Proceedings of the 22^nd Conference of the IEEE Computer and Communications Society(INFOCOM’۲۰۰۳), April 2003, San Francisco, CA, pp.1312-1321.
21. 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.
22. 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’۲۰۰۱), Helsinki, Finland, June 2001.
23. Amit Jardosh, Elizabeth M. Belding-Royer, Kevin C. Almeroth, Subhash Suri, “Towards realistic mobility models for mobile ad hoc networks“, in Proceedings of the 9th annual international conference on Mobile computing and networking (MOBICOM 2003), San Diego, CA, USA, Sept 2003, 217-229.
24. Lee Breslau, Deborah Estrin, Kevin Fall, Sally Floyd, John Heidemann, Ahmed Helmy, Polly Huang, Steven McCanne, Kannan Varadhan, Ya Xu, and Haobo Yu, “Advances in Network Simulation”, in IEEE Computer, 33 May, 2000, (5 ), pp.59-67.
25. “The Network Simulator – NS2”, http://www.isi.edu/nam/ns/.
26. 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.
27. 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.
28. 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.
29. -J. Lee, M. Gerla, “Dynamic Load-Aware Routing in Ad hoc Networks” in Proceedings of IEEE International Conference on Communications (ICC’۲۰۰۱), Helsinki, Finland, June 2001, pp. ۳۲۰۶-۳۲۱۰٫
30. 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’۲۰۰۰), Chicago, IL, Sept 2000, pp.1317-1322.
31. -J. Lee and M. Gerla, “AODV-BR: Backup Routing in Ad hoc Networks” in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC’۲۰۰۰), Chicago, IL, Sep. 2000, pp.1311-1316.
32. 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’۲۰۰۱), Helsinki, Finland, June 2001, pp.3201-3205.
33. 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.
34. Elizabeth M. Belding-Royer. “Hierarchical Routing in Ad hoc Mobile Networks”, Wireless Communication & Mobile Computing, 2(5), pp. 515-532, 2002.
35. 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.
36. 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’۲۰۰۲), Paris, France, November 2002.
37. 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.

۳۸٫       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. Rituparna Ghosh, Stefano Basagni, “Limiting the impact of mobility on ad hoc clustering,” in Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks (PE-WASUN 2005), Oct 2005, Montréal, Quebec, Canada, 197-204.
40. Mohammed S. Al-kahtani, Hussein T. Mouftah, “Enhancements for clustering stability in mobile ad hoc networks,” in Proceedings of the 1st ACM international workshop on Quality of service & security in wireless and mobile networks (Q2SWinet’2005), Montreal, Quebec, Canada, Oct 2005, pp.112-121.
41. Y. YU and P. H. J. CHONG, “A Survey of Clustering Schemes for Mobile Ad Hoc Networks,” IEEE Communications Surveys and Tutorials, First Quarter 2005, Vol.7, No.1, pp.32-48.
42. Prithwish Basu, Naved Khan, and Thomas D.C. Little, “A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks”, in Proc. of IEEE ICDCS 2001 Workshop on Wireless Networks and Mobile Computing, Phoenix, AZ, April 2001, 413-418.
43. 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.
44. 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.

پیشگفتار

امروزه شبكه‌هاي بي‌سيم به دليل كاربردهايي كه دارد و همچنين سرويسهايي كه ارائه مي‌دهد، رشد چشمگيري داشته است. اين شبكه‌ها در حال توسعه سريعي هستند و سرويسهاي ارائه شده هم مرتباً بيشتر و بهتر می‌شود، در آينده‌اي نه چندان دور، تكنولوژي اطلاعات بر پايه مخابرات بي‌سيم خواهد بود. از آنجاييكه ايجاد شبكه با زيرساخت باعث محدوديت در شبكه‌هاي موبايل و سلولی معمولي خواهد كرد؛ لذا شبكه‌هاي بدون زير ساخت مي‌تواند ايدة خوبي براي ادامه مخابرات بي‌سيم باشد. شبكه‌هاي ادهاك، بدليل عدم نياز به زيرساختار، محدوديت شبكه‌هاي موبايل را مرتفع خواهد كرد.

شبكه‌هاي Ad–hoc براي اولين بار توسط وزارت دفاع آمريكا در سيستم‌هاي نظامي و عملياتي خود مورد استفاده قرار گرفته است. ليكن از سال ۱۹۷۰ بطور عمومي مورد استفاده ميباشد.

در اين پروژه هدف ارائه الگوريتم مسيريابي پيشنهادي مبتني بر خوشه يابي مي باشد.

در اين راستا  ابتدا در فصل اول  به تقسيم بندي و توضيح شبكه هاي ادهاك و مروري بر پروتكلهاي مسيريابي آن خواهيم پرداخت و سپس در فصل دوم  عناصر مورد استفاده جهت شبيه سازي شبكه هاي MANET كه شامل مدل هاي حركت و ابزار شبيه سازي مي باشد مورد بررسي قرار مي گيرد و نيز  فصل آخر را به بررسي الگوريتم هاي خوشه يابي و ارائه يك الگوريتم پيشنهادي و همچنين ارزيابي كارائي آن نسبت به ساير روش هاي خوشه يابي اختصاص داده ايم و فصل چهارم  ننتيجه گيري و پيشنهاد براي آينده و در پايان نيز به طرح يك مقاله شخصي كه شامل خلاصه  اين رساله مي باشد پرداخته ايم، با اميد به ايجاد انگيزه اي دو چندان در جهت پيشرفت هاي علمي، عزت و سلامت همه عزيزان را از درگاه ايزدمنان خواستارم.

۱-۱ تقسيم‌بندي شبكه‌هاي بي‌سيم[۱]

شبكه هاي بي‎سيم را از نظر معماري مي توان به دو گروه اصلي تقسيم بندي نمود:

الف) شبكه هاي داراي زيرساخت[۲]

مسيريابهايي كه در اين نوع شبكه‌ها مورد استفاده قرار مي‌گيرند، اصطلاحاً به ايستگاه‌هاي ثابت شهرت دارند. اين ايستگاههاي پايه‌اي قابليت حركت ندارند، با روشهاي مختلف و با امكانات سرعت بالا به يكديگر متصل هستند. هر واحد متحرك در زمان برقراري ارتباط و نيز ردو بدل كردن اطلاعات، به نزديكترين ايستگاه پايه‌اي متصل مي شود. در نتيجه ارتباطات بي‎سيم در اين نوع شبكه‌ها، بر اساس ارتباط سيمي[۳] بين ايستگاه هاي پايه‌اي صورت مي پذيرد. اين شبكه‌ها همچنين به شبكه‌هاي بي‎سيم يك‌گامي[۴] نيز شهرت دارند. شبكه‌هاي مخابرات سلولي و شبكه‌هاي PCS[5] مثالهايي از اين نوع شبكه‌هاي بي‌سيم هستند. در شبكه‌هاي يك‌گامي گره‌هاي متحرك همواره تحت پوشش ايستگاههاي پايه قرار دارند و در نتيجه ارتباط پيوسته‌اي با ايستگاههاي پايه دارند.

ب) شبكه هاي فاقد زيرساخت[۶]

در اين شبكه ها كه به شبكه هاي MANET[7] نيز شهرت دارند، هيچ زير ساخت از پيش تعريف شده اي براي برقراري ارتباط بين گره ها وجود ندارد. هر گره قابليت مسيريابي را داراست در عين حال، قادر است در هر جهتي حركت كند و همچنين به گره هاي ديگر نيز متصل شود. به همين دليل، اطلاعات ارسالي از يك گره به گره ديگر بدليل فاصله دو گره مزبور ممكن است در صورت نياز از چند گره ديگر عبور كند. درنتيجه، اين شبكه ها را شبكه هاي بي‎سيم چندگامي[۸] نيز مي‌نامند. در اين پروژه، اين دسته از شبكه‌هاي بي‌سيم مورد بحث و بررسي قرار مي گيرند.

باتوجه به اينكه هيچ زيرساخت ارتباطي ويا ادوات سخت افزاري جانبي جهت راه‌اندازي و مديريت شبكه مورد نياز نيست، با روشن شدن و فعال شدن گره‌ها، شبكه تشكيل مي‌شود. بدين ترتيب سادگي و سرعت راه‌اندازي شبكه از خصوصيات شبكه‌هاي MANET مي‌باشد.

اينگونه شبكه‌ها در مواردي مورد استفاده قرار مي‌گيرند كه هيچ ساختار ارتباطي ديگري موجود نباشد. با وجود اينكه انتظار مي رود كاربردهاي اين نوع شبكه‌ها جنبه اقتصادي داشته باشند ولي بيشتر كاربردهاي مطرح شده تاكنون جنبه نظامي داشته‌اند. اين امر نيز طبيعي به نظر مي رسد و در ميدان جنگ و يا موارد كمك رساني و امداد در مناطقي كه امكانات مخابراتي در دسترس نمي باشند، اين شبكه ها تنها راه عملي براي ارسال داده به شمار مي روند.

شبكه‌هاي موسوم به PRNET[9] كه در سال ۱۹۷۳ توسط DARPA[10] طراحي و مورد استفاده قرارگرفته‌اند ]۱[ ، اولين شبكه‌هاي پيشنهادي از نوع MANET به شمار مي‌روند. هدف از طراحي اين شبكه، فراهم آوردن ارتباط كامپيوتري بين ترمينالهاي متحرك بود. اين شبكه درحقيقت به يك محيط براي تحقيقات و همچنين توسعه پروتكلهاي مسيريابي شبكه‌هاي MANET تبديل شد. شبكه‌هاي HF ITF نمونه ديگري از شبكه‌هاي MANET هستند كه با ارائه يك الگوريتم مسيريابي توزيعي و سلسله‌مراتبي طراحي شدند. اكنون با ارائه فناوريهاي مختلف بي‌سيم و وفور كاربرد آنها، شبكه‌هاي MANET، بيشتر مورد توجه محققين قرارگرفته‌اند. با گسترش تحقيقات در مورد شبكه‌هاي MANET ، IETF گروه كاري MANET را مسؤل تدوين استاندارد هاي مربوط به اين شبكه‌ها نموده‌است.

خصوصيات مهم شبكه هاي ad-hoc را مي توان به صورت زير برشمرد ]۳ [:

• توپولوژي شبكه به دليل حركت گره‌ها و همچنين مشكل توان در گره‌ها، مي‌تواند به شدت متغير باشد.
• به دليل محدوديت در توان پراكنشي گره‌ها، اطلاعات ارسالي ممكن است از چند گره مياني عبور كند.
• منابع در شبكه‌هاي ad-hoc كاملاً محدود هستند؛ اين منابع عبارتند از: پهناي باند كانال، منابع گره مانند توان محاسباتي[۱۱]، ظرفيت ذخيره سازي[۱۲] و توان باتري.
• به دليل حركت گره‌ها، توپولوژي شبكه دائماً در حال تغيير است و پروتكل مسيريابي
  بايد از اين تغييرات آگاه باشد. بحث اصلي، يافتن پروتكلهاي مسيريابي ديناميكي است كه در چنين محيطي، قادر به يافتن مسير مناسب جهت برقراري ارتباط و تبادل اطلاعات بين دو گره باشند.

[۱] – Wireless Networks

[۲] – Infra Structured Networks

[۳] – Wired

[۴] – Single Hop

[۵] – Personal Communication System

[۶] – Infra Structure-less Networks

[۷] – Mobile Ad Hoc Networks

[۸] – Multi Hop

[۹] – Packet Radio Network

[۱۰] – Defense Advanced Research Projects Agency

[۱۱] – Computational Power

[۱۲] – Storage Capacity

۹۳ صفحه Word

شما هم اکنون با داشتن رمز دوم کارت عابر خود و پرداخت اینترنتی می توانید بلافاصله پس از پرداخت این فایل را دریافت کنید و مطالعه این محصول با ارزش را شروع کنید .