مقاله در مورد مسيريابي مبتني بر ناحيه بندي در شبكه هاي Ad Hoc

دانشگاه آزاد اسلامي
(واحد قزوين)
دانشكده برق، رايانه و فناوري اطلاعات
پايان نامه كارشناسي
موضوع :
مسيريابي مبتني بر ناحيه بندي در شبكه هاي Ad Hoc
استاد راهنما :
آقاي دكتر افتخاري مقدم
دانشجو :
مسعود پيركندي
زمستان 85
بزرگترين كشف نسل ما، آن است كه بشر مي تواند با تغيير دادن افكار خويش، زندگي خود را تغيير دهد.
بر خود ميدانم كه از استاد گرامي جناب آقاي دكتر افتخاري مقدم وهمين طور آقاي مهرداد مهدوي و ساير دوستان كه مرا در اين راستا راهنمائي و همايت نمودند
فهرست مطالب
پيشگفتار………………………………………………………………………………………………………………………………………….1
فصل اول ……………………………………………………………………………………………………………………………………………2
شبكه‌هاي Ad Hoc………………………………………………………………………………………………………………………….2
1-1 تقسيم‌بندي شبكه‌هاي بي‌سيم ……………………………………………………………………………………………………2
1-2 مروري بر پروتكلهاي مسيريابي در شبكه‌هاي MANET …………………………………………………..61-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
مقاله خلاصه پايان نامه…………………………………………………………………………………………………..89
ضميمه 1
واژه‌نامه
ضميمه 2
عبارتهاي اختصاري
مراجع
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.
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,
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
“The Network Simulator – NS2”, http://www.isi.edu/nam/ns/.
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.
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.
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

فایل : 93 صفحه

فرمت : Word