فایل رایگان مسیریابی مبتنی بر ناحیه بندی در شبكه های Ad Hoc

... دانلود ...

بخشی از متن فایل رایگان مسیریابی مبتنی بر ناحیه بندی در شبكه های Ad Hoc :

فایل رایگان مسیریابی مبتنی بر ناحیه بندی در شبكه های Ad Hoc

فایل رایگان مسیریابی مبتنی بر ناحیه بندی در شبكه های Ad Hoc
فهرست مطالب

پیشگفتار.............................................................................................................................................................1

فصل اول ...............................................................................................................................................................2

شبكه‌های Ad Hoc...........................................................................................................................................2

1-1 تقسیم‌بندی شبكه‌های بی‌سیم ..................................................................................................................2

1-2 مروری بر پروتكلهای مسیریابی در شبكه‌های MANET ...........................................................6
1-2-1 الگوریتمهای مسیریابی مسطح.............................................................................................................6

1-2-1-1 پروتكلهای مسیریابی Table Driven...............................................................................................7

1-2-1-1-1 پروتكل مسیریابی DSDV ............................................................................................................8

1-2-1-1-2 پروتكل مسیریابی WRP .................................................................................................................8

1-2-1-2 پروتكلهای مسیریابی on-Demand .................................................................................................9

1-2-1-2-1 پروتكل مسیریابی AODV ..........................................................................................................10

1-2-1-2-2 پروتكل مسیریابی DSR ...............................................................................................................12

1-2-1-2-3 ظرفیت شبكه های بی‌سیم و محدودیت الگوریتمهای On-Demand ........ ....................14

1-2-2 الگوریتمهای مسیریابی سلسله‌مراتبی .........................................................................................15

1-2-2-1 مفهوم خوشه‌یابی ...................................................................................................................................18

1-2-2-2 مزایای استفاده از خوشه‌یابی ..............................................................................................................20

1-2-2-3 الگوریتمهای مسیریابی سلسله‌مراتبی مبتنی بر خوشه‌یابی .........................................................22

فصل دوم ..........................................................................................................................................................25

عناصر مورد استفاده جهت شبیه‌سازی شبكه‌های MANET........................................25

2-1 تكنولوژی بی‌سیم مورد استفاده در شبیه سازی شبكه های Ad Hoc ............................25

2-2 مدلهای تحرك .............................................................................................................................................30

2-2-1 مدل‌های تحرك تصادفی .........................................................................................................................31

2-2-2 مدل تحرك با وابستگی لحظه‌ای ...........................................................................................................32

2-2-3 مدل تحرك با وابستگی فضایی ..............................................................................................................33

2-2-4 مدلهای تحرك با محدودیت جغرافیایی ...............................................................................................35

2-2-5 خصوصیات مدل تحرك Random Waypoint ...........................................................................35

2-3 ابزار شبیه‌سازی ........................................................................................................................................38

فصل سوم .......................................................................................................................................................42

خوشه‌یابی ..........................................................................................................................................................42

3-1 مروری بر الگوریتمهای خوشه‌یابی .....................................................................................................42

3-2 پارامترهای كارایی در روشهای خوشه‌یابی ...................................................................................50

3-3 الگوریتم خوشه‌یابی پیشنهادی ........................................................................................................52

3-3-1 تشخیص گره‌های همسایه .....................................................................................................................54

3-3-2 شکل گیری خوشه‌ها ..............................................................................................................................55

3-3-3 پیکربندی مجدد خوشه‌ها .....................................................................................................................58

3-3-4 ارزیابی کارایی ..........................................................................................................................................65

فصل چهارم.................................................................................................................................................77

نتیجه‌گیری و پیشنهاد برای آینده ....................................................................................................77

ضمیمه 1 ( واژه‌نامه ) ..................................................................................................................................80.

ضمیمه 2 ( عبارتهای اختصاری ) .......................................................................................................82

مراجع ................................................................................................................................................................86

ضمیمه 1

واژه‌نامه

ضمیمه 2

عبارتهای اختصاری

مراجع

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. 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. Piyush Gupta, Robert Gray, and P. R. Kumar, “An Experimental Scaling Law for Ad Hoc Networks"", Technical report, University of Illinois at UrbanaChampaign, black.csl.uiuc.edu/~prkumar, May 16, 2001,
8. 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.
9. 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. J. 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’2001), 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’2003), April 2003, san Francisco, CA, pp.1553-1563.
13. X. 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. 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.
16. 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. T. 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. 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. 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. J. 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’2003), 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’2001), 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, pp. 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. 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.
28. 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.
29. 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.
30. 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.
31. 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.
32. 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.
33. 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.
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’2002), 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.
38. 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, pp.197-204.
39. 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.
40. J. 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.
41. 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, pp. 413-418.
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.
43. 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.

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.

پیشگفتار

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

شبكه‌های 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 [:

- توپولوژی شبكه به دلیل حركت گره‌ها و همچنین مشكل توان در گره‌ها، می‌تواند به شدت متغیر باشد.

- به دلیل محدودیت در توان پراكنشی گره‌ها، اطلاعات ارسالی ممكن است از چند گره میانی عبور كند.

- منابع در شبكه‌های ad-hoc كاملاً محدود هستند؛ این منابع عبارتند از: پهنای باند كانال، منابع گره مانند توان محاسباتی[11]، ظرفیت ذخیره سازی[12] و توان باتری.

- به دلیل حركت گره‌ها، توپولوژی شبكه دائماً در حال تغییر است و پروتكل مسیریابی
باید از این تغییرات آگاه باشد. بحث اصلی، یافتن پروتكلهای مسیریابی دینامیكی است كه در چنین محیطی، قادر به یافتن مسیر مناسب جهت برقراری ارتباط و تبادل اطلاعات بین دو گره باشند.

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-2-1-1-2 پروتكل مسیریابی WRP

دراین روش هدف نگهداری اطلاعات مسیریابی در كلیه گره‌های شبكه است. هر گره باید 4 جدول در حافظه خود نگهداری كند: جدول فاصله[19]، جدول مسیریابی[20]، جدول هزینه اتصال[21] و جدول ارسال مجدد پیام[22] .

در جدول ارسال مجدد پیام، بخشهایی از تغییرات كه باید مجدداً ارسال شوند و همچنین آدرس گره‌هایی كه باید به این ارسال مجدد پاسخ دهند ثبت میشوند. پیام بهنگام‌سازی[23]، فقط بین گره‌های مجاور ارسال میشود و حاوی تغییرات و همچنین فایل رایگان مسیریابی مبتنی بر ناحیه بندی در شبكه های Ad Hoc
فهرست آدرسهایی از گره‌های شبكه است كه باید نتیجه دریافت این پیام را به فرستنده منعكس نمایند. پیام تصحیح زمانی توسط یك گره ارسال میشود كه این گره یك پیام تصحیح از همسایه خود دریافت كند و یا تغییری در یك اتصال با یكی از همسایگان خود مشاهده كند.

گره‌ها با ردو بدل شدن acknowledgement و همچنین دیگر پیامها، از حضور همسایگان خود مطلع میشوند. زمانیكه یك گره اطلاعاتی برای ارسال ندارد، باید بصورت دوره‎ای پیام Hello ارسال كند تا از درستی اتصالات خود اطمینان حاصل نماید.

همچنین با دریافت این پیام از یك گره جدید، گره‌های دیگر آدرس این گره را در جدول مسیریابی خود قرار می‎دهند. در روش WRP، از آنجائیكه سازگاری اطلاعات هر گره با اطلاعات ارسالی از گره‌های همسایه دائماً برقرار میشود، مسأله Count–to–infinity رخ نخواهد داد و این امر نهایتاً از بروز حلقه جلوگیری خواهد كرد. همچنین، در صورت بروز خرابی در یك اتصال، همگرایی مسیر سریعا صورت خواهد پذیرفت.

1-2-1-2 پروتكلهای مسیریابی on-Demand

الگوریتمهای مسیریابی مانند AODV ،DSR ABR ، TORA ،RDMAR و WAR در این گروه قرار می‌گیرند. در این دسته از پروتكلها، یك مسیر جدید فقط در صورتی ایجاد خواهد شد كه گره مبدا بدان نیاز داشته باشد. هدف اصلی از ارائه این دسته از پروتكلها، كاهش بار ترافیك كنترلی ناشی از مسیریابی در شبكه است. بار زیاد ترافیك مسیریابی در شبكه‌های با پهنای باند كم، می تواند اثرات منفی زیادی بر روی كارائی این دسته از شبكه‌ها داشته باشد. زمانیكه یك گره، مسیری به گره مقصد نیاز داشته باشد، فرایند پیدا كردن مسیر[24] را شروع خواهد كرد. این فرایند زمانی به انتها می رسد كه یك مسیر جدید پیدا شود و یا اینكه كلیه مسیرهای ممكن امتحان شده باشند. اگر در این فرایند، مسیر جدیدی پیدا شد، فرایند نگهداری مسیر[25] باید این مسیر را نگهداری نماید. این نگهداری تا زمانی انجام خواهد شد كه گره مقصد دیگر قابل دستیابی نباشد و یا اینكه مسیر دیگر مورد نیاز نباشد ]3[. در این قسمت به بیان برخی پروتكلهای on-Demand موجود می پردازیم:

1-2-1-2-1 پروتكل مسیریابی AODV

AODV ]7و8[ مشابه با DSDV طراحی شده‌ است. تفاوت اصلی AODV با DSDV در این است كه بر خلاف DSDV، فایل رایگان مسیریابی مبتنی بر ناحیه بندی در شبكه های Ad Hoc
فهرست كامل مسیرها نگهداری نمیشود ]3[. در این الگوریتم، در هر گره فرایند یافتن مسیر مطابق شكل 3 با پراكنش كردن یك درخواست مسیر RREQ به گره‌های همسایه آغاز میشود. گره‌های همسایه نیز پس از ذخیره كردن مشخصات فرستنده RREQ , این بسته را به دیگر گره‌های همسایه خود ارسال مینمایند. این عمل تا آنجا ادامه می‎یابد كه گره مقصد و یا یكی از گره های میانی كه مسیر نسبتاً جدیدی به گره مقصد دارد، بسته را دریافت نماید. مسیر نسبتا جدید[26]، مسیری است كه عدد شمارشی آن، بزرگتر یا مساوی عدد موجود در RREQ باشد. در اینجا، گره مقصد یا گره میانی حاوی مسیر مطابق شكل 1-4، با ارسال یك تقاضای پاسخ RREP به گره همسایه‌ای كه RREQ را از آن دریافت كرده است، به این درخواست پاسخ می دهد.

جهت دریافت فایل کامل لطفا آن را خریداری نمایید