Đề tài Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong Manet

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Văn Tứ KHẢO SÁT ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN TRONG MANET KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Văn Tứ KHẢO SÁT ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN TRONG MANET KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: PGS.TS. Nguyễn Đình Việt Cán bộ đồng hướng dẫn: Ths. Đoàn Minh Phương HÀ NỘI - 2010 TÓM TẮT Ngày nay, cùng với sự bùng nổ, phát triển mạnh mẽ của các thiết bị di động cá nhân như: laptop, smartphone, tablet,…, thì nhu cầu kết nối giữa các thiết bị này cũng ngày càng đòi hỏi cao hơn về tốc độ và khả năng di chuyển trong khi kết nối. Mạng di động đặc biệt – MANET (Mobile Ad-hoc Network) là một trong những công nghệ vượt trội đáp ứng nhu cầu kết nối đó nhờ khả năng hoạt động không phụ thuộc vào cơ sở hạ tầng mạng cố định, với chi phí hoạt động thấp, triển khai nhanh và có tính di động cao. Tuy nhiên, hiện nay mạng MANET vẫn chưa được ứng dụng rộng rãi và đang được thúc đẩy nghiên cứu nhằm cải tiến hơn nữa các giao thức định tuyến để mạng đạt được hiệu quả hoạt động tốt hơn. Khóa luận nghiên cứu ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong mạng MANET. Bằng những kiểm chứng thông qua mô phỏng, khóa luận đưa ra các nhận xét, đánh giá về hiệu suất mạng đối với từng giao thức định tuyến cụ thể khi các nút mạng chuyển động với tốc độ và hướng đi thay đổi. MỤC LỤC TÓM TẮT ............................................................................................................................... DANH MỤC HÌNH VẼ ........................................................................................................... DANH MỤC BẢNG................................................................................................................ BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT ............................................................................... LỜI CẢM ƠN.......................................................................................................................... Chương 1. GIỚI THIỆU ........................................................................................................ 1 1.1. Sự ra đời và phát triển của các mạng không dây .......................................................... 1 1.2. Mục tiêu nghiên cứu của khóa luận.............................................................................. 4 1.3. Công cụ nghiên cứu chính – NS-2 ............................................................................... 5 1.3.1. Giới thiệu về NS-2................................................................................................ 5 1.3.2. Khả năng mô phỏng của NS-2 .............................................................................. 7 1.4. Tổ chức của KLTN...................................................................................................... 8 Chương 2. GIAO THỨC MAC CỦA MẠNG LAN VÀ WLAN ............................................ 9 2.1. Mạng LAN và mạng WLAN ....................................................................................... 9 2.2. Chuẩn 802.3 và giao thức CSMA/CD........................................................................ 10 2.3. Chuẩn 802.11 và giao thức CSMA/CA ...................................................................... 12 Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN .............................................. 15 3.1. Mạng MANET .......................................................................................................... 15 3.1.1. Lịch sử phát triển và các ứng dụng...................................................................... 15 3.1.2. Các đặc điểm chính của mạng MANET .............................................................. 16 3.2. Vấn đề định tuyến trong mạng MANET .................................................................... 17 3.2.1 Các thuật toán định tuyến truyền thống ................................................................ 17 3.2.2. Các yêu cầu chính đối với việc định tuyến trong mạng MANET ......................... 18 3.2.3. Phân loại các kỹ thuật định tuyến........................................................................ 19 3.2.3.1. Link state và Distance Vector....................................................................... 19 3.2.3.2. Định tuyến chủ ứng và phản ứng.................................................................. 20 3.2.3.3. Định tuyến nguồn và định tuyến theo chặng ................................................. 21 3.3. Các giao thức định tuyến chính trong mạng MANET ................................................ 22 3.3.1. DSDV................................................................................................................. 22 3.3.2 OLSR [8]............................................................................................................. 23 3.3.3. AODV [12]......................................................................................................... 25 3.3.4. DSR [7] .............................................................................................................. 27 3.3.5. TORA [11] ......................................................................................................... 28 Chương 4. ĐÁNH GIÁ BẰNG MÔ PHỎNG ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG CỦA CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN 30 4.1. Xác định các tham số hiệu suất cần đánh giá và cách thức phân tích kết quả mô phỏng ........................................................................................................................................ 30 4.1.1. Các tham số hiệu suất cần đánh giá ..................................................................... 30 4.1.2. Cách thức phân tích kết quả mô phỏng của NS-2 ................................................ 30 4.1.2.1. Cấu trúc tệp vết ............................................................................................ 30 4.1.2. Công cụ để phân tích và biểu diễn kết quả mô phỏng .......................................... 33 4.1.2.1. Perl .............................................................................................................. 33 4.1.2.2. GNUPLOT .................................................................................................. 33 4.2. Thiết lập mạng mô phỏng MANET ........................................................................... 35 4.2.1. Thiết lập tô-pô mạng........................................................................................... 35 4.2.2. Thiết lập mô hình chuyển động của các nút mạng và thời gian mô phỏng ........... 36 4.2.2.1. Mô hình Random Waypoint ......................................................................... 37 4.2.2.2. Mô hình Random Walk................................................................................ 38 4.2.3 Thiết lập các nguồn sinh lưu lượng đưa vào mạng ............................................... 39 4.2.4. Lựa chọn thời gian mô phỏng ............................................................................. 40 4.3. Thực hiện mô phỏng các giao thức định tuyến ........................................................... 40 4.3.1. Phân tích kết quả bằng công cụ perl .................................................................... 40 4.3.2. Sử dụng gnuplot để vẽ đồ thị .............................................................................. 44 4.4. Đánh giá ảnh hưởng của sự chuyển động của nút mạng đến hiệu suất của các giao thức định tuyến ........................................................................................................................ 47 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................................ 49 TÀI LIỆU THAM KHẢO .................................................................................................... 51 PHỤ LỤC ............................................................................................................................ 53 1. Bảng các trường phụ thêm vào trong cấu trúc tệp vết phụ thuộc vào kiểu gói tin .......... 53 2. Mô phỏng mạng MANET............................................................................................. 56 3. Tỷ lệ phân phát gói tin thành công................................................................................ 58 4. Thời gian thiết lập kết nối............................................................................................. 59 DANH MỤC HÌNH VẼ Hình 1: Sự phát triển của mạng không dây và di động............................................................ 1 Hình 2: Cấu trúc của NS-2 ..................................................................................................... 5 Hình 3: Luồng các sự kiện cho file Tcl chạy trong NS-2 ........................................................ 6 Hình 4: Chu trình hoạt động của giao thức CSMA/CD (bên gửi) .......................................... 11 Hình 5: Chu trình hoạt động của giao thức CSMA/CA (bên gửi) .......................................... 13 Hình 6: Hoạt động lắng nghe kênh truyền của giao thức CSMA/CA .................................... 14 Hình 7: Phân loại các giao thức định tuyến trong mạng MANET ......................................... 22 Hình 8: Tô-pô mạng thay đổi ............................................................................................... 23 Hình 9: Quy trình chuyển tiếp gói tin khi sử dụng kíp đa điểm – MPR................................. 24 Hình 10: OLSR ngăn chặn vòng lặp bằng việc sử dụng MPR để chuyển phát gói tin. ........... 25 Hình 11: quá trình khám phá tuyến trong AODV ................................................................. 25 Hình 12: Định tuyến nguồn động (DSR) .............................................................................. 27 Hình 13: Diện tích mạng mô phỏng và các nút mạng............................................................ 35 Hình 14: Di chuyển một nút theo mô hình Random Waypoint.............................................. 37 Hình 15: Di chuyển của 8 nút theo mô hình Random Walk .................................................. 38 Hình 16: Đồ thị tỷ lệ phân phát gói thành công – Random Waypoint.................................... 44 Hình 18: Đồ thị tỷ lệ phân phát gói tin thành công – Random Walk ..................................... 45 Hình 19: Đồ thị thời gian thiết lập kết nối trung bình_Random-Waypoint ............................ 46 Hình 20: Đồ thị thời gian thiết lập kết nối trung bình_Random-Walk ................................... 46 DANH MỤC BẢNG Bảng 1: Sự phát triển của chuẩn 802.3 ................................................................................. 10 Bảng 2: Sự phát triển của chuẩn 802.11 ............................................................................... 12 Bảng 3: Cấu trúc tệp vết ....................................................................................................... 31 Bảng 4: Các trường thêm vào trong cấu trúc tệp vết phụ thuộc vào kiểu gói tin .................... 32 Bảng 5: Cấu hình mạng mô phỏng ....................................................................................... 36 Bảng 6: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Waypoint ................ 41 Bảng 7: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Walk ....................... 42 Bảng 8: Thời gian thiết lập kết nối trung bình-Random_Waypoint ....................................... 43 Bảng 9: Thời gian thiết lập kết nối trung bình-Random_Walk.............................................. 43 Bảng 10: Tỷ lệ phân phát gói tin thành công - Random Waypoint ........................................ 44 Bảng 11: Tỷ lệ phân phát gói tin thành công – Random Walk .............................................. 45 BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT AODV Adhoc On-demand Distance Vector MANET Mobile Adhoc NETwork CSMA/CA Carrier sense multiple access with collision avoidance MPR Multi-Point Relays CSMA/CD Carrier Sense Multiple Access with Collision Detection NS-2 Network Simulator 2 DARPA Defense Advanced Research Projects Agency OLSR Optimized Link State Routing Protocol DSDV Destination-Sequenced Distance Vector PRnet Packet Radio Network DSR Dynamic Source Routing RREP Route Reply IEEE Institute of Electrical and Electronics Engineers RREQ Route Request LAN Local Area Network TORA Temporally-Ordered Routing Algorithm MAC Media Access Control WLAN Wireless LAN LỜI CẢM ƠN Trước tiên, tôi xin gửi lời cảm ơn chân thành tới PGS.TS.Nguyễn Đình Việt, người thầy đã tận tình giúp đỡ tôi trong suốt quá trình làm khóa luận. Tôi cũng xin gửi lời cảm ơn tới Ths. Đoàn Minh Phương, người đã hướng dẫn tôi trong giai đoạn chuẩn bị nhận đề tài. Tôi xin gửi lời biết ơn sâu sắc tới thầy, cô trong trường Đại Học Công Nghệ, Đại Học Quốc Gia Hà Nội. Thầy, cô đã dìu dắt, truyền lại cho chúng tôi không chỉ những kiến thức chuyên ngành mà còn dạy bảo chúng tôi đạo làm người, rèn luyện cho chúng tôi nghị lực, khát vọng vươn lên, phát huy khả năng tư duy sáng tạo trong mọi lĩnh vực. Cuối cùng, tôi xin được cảm ơn gia đình, bạn bè, những người thân yêu nhất của tôi. Mọi người luôn ở bên cạnh tôi, động viên, khuyến khích tôi vươn lên trong cuộc sống. Hà nội, tháng 5 năm 2010 Phạm Văn Tứ Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong MANET Phạm Văn Tứ 1 K51MMT Chương 1. GIỚI THIỆU 1.1 . Sự ra đời và phát triển của các mạng không dây Mạng không dây được đánh dấu mốc hình thành từ những năm 1887 khi Heinrich Rudolf Hertz chứng minh được thuyết điện từ Maxwell thông qua thực nghiệm. Từ đó đến nay các nhà nghiên cứu đã cho ra đời hàng loạt phát minh sáng chế góp phần đưa công nghệ mạng không dây không ngừng cải tiến vượt trội về tốc độ truyền nhận dữ liệu. Những năm gần đây nền công nghiệp không dây và di động tăng trưởng mạnh mẽ cả về mặt công nghệ lẫn sự bùng nổ ngày càng nhiều các thiết bị di động, hứa hẹn một kỷ nguyên truyền thông số nở rộ trên nền các mạng không dây và di động. Sự phát triển này được minh họa trên Hình 1 dưới đây. Hình 1: Sự phát triển của mạng không dây và di động Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong MANET Phạm Văn Tứ 2 K51MMT Các mốc hình thành và phát triển của mạng không dây: Nikola Tesla truyền thành công sóng radio. Heinrich Rudolf Hertz đã tạo ra được sóng điện từ. Ông đã chứng minh được thuyết Maxwell thông qua thực nghiệm. 1887 1893 1895 1915 1931 1982 , 1991 Guglielmo Marconi: Lần đầu tiên trong lịch sử, 3 dấu chấm (tức chữ S trong bảng ký tự Morse) đã được truyền qua không gian với khoảng cách 3km bằng sóng điện từ. Truyền thành công sóng vô tuyến vượt Đại Tây Dương từ Arlington Virginia tới Pháp. Tháp Eiffel đã được sử dụng để đặt anten thu tín hiệu. Sóng FM đã được phát triển bởi Edwin H. Armstrong và được sử dụng rộng rãi để truyền thông tin qua sóng vô tuyến. -1982: Hội nghị CEPT đã thống nhất chọn GSM để phát triển thành tiêu chuẩn cho hệ thống điện thoại di động có thể được sử dụng trên khắp châu Âu. - 1991: Các mạng GSM đầu tiên đã được đưa ra bởi Radiolinja ở Phần Lan với kỹ thuật bảo dưỡng cơ sở hạ tầng chung từ Ericsson. Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong MANET Phạm Văn Tứ 3 K51MMT -1998: Công nghệ Bluetooth đầu tiên được phát triển bởi Ericsson, sau đó được chuẩn hoá bởi Bluetooth Special Interest Group (SIG). - 1999: Chuẩn 802.11b được phát hành cho tốc độ tối đa lên 11Mb/s. -20/5/1999: Chính thức phát hành chuẩn Bluetooth 1.0 Chuẩn IEEE 802.11 (WiFi) đã được tạo ra, với tốc độ tối đa là 2Mb/s. 1997 1998, 1999 2001 2003 2004, 2009 2010 Chuẩn IEEE 802.16 được phát hành. Chuẩn này được biết đến dưới cái tên WIMAX. - Chuẩn 802.11g được phát hành với tốc độ tối đa lên tới 54 Mb/s. - Bluetooth 1.2 được công bố. *2004: - Phiên bản mới của chuẩn 802.16 được bổ sung, hoàn thiện chuẩn WIMAX. - Phát hành chuẩn Bluetooth 2.0 *2009: - Chuẩn 802.11n được phát hành cho phép tốc độ truyên thông tối đa lên tới 150 Mb/s. Liên minh Wi-Fi và Gigabit không dây đã đạt được thỏa thuận cho phép Wi-Fi hoạt động ở dải tần 60 Ghz nhằm cải thiện tốc độ truyền dữ liệu. Các chuẩn Wi-Fi hiện đang hoạt động ở dải tần từ 2.4 GHz đến 5 GHz.  Tốc độ Wi-Fi sẽ tăng hơn 10 lần so với tốc độ hiện tại Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong MANET Phạm Văn Tứ 4 K51MMT 1.2 . Mục tiêu nghiên cứu của khóa luận Với đặc tính có thể hoạt động không phụ thuộc vào cơ sở hạ tầng mạng, triển khai nhanh, linh hoạt ở mọi vị trí địa hình khác nhau, mạng MANET đang là tâm điểm nghiên cứu đầy triển vọng, sẽ là công nghệ đột phá trong tương lai với nhiều ứng dụng hữu ích vào cuộc sống, thí dụ kết nối mạng truyền thông cho các các vùng mới xảy ra thiên tai hoặc ứng dụng cho lĩnh vực quân sự. Khóa luận tập trung đi sâu nghiên cứu về mạng MANET, kết hợp phân tích trên lý thuyết cùng thực nghiệm mô phỏng để tìm ra và đánh giá ảnh hưởng sự di động của các nút mạng ở các mức độ khác nhau đến hiệu suất của một số giao thức định tuyến. Nội dung cụ thể gồm:  Tìm hiểu sâu về mạng MANET, trong đó chủ yếu xem xét tới các giao thức định tuyến.  Tìm hiểu sâu về các mô hình chuyển động của nút mạng trong MANET.  Xây dựng môi trường mô phỏng, đưa các giao thức định tuyến trong mạng MANET vào mô phỏng thông qua NS-2.  Đánh giá ảnh hưởng sự chuyển động của các nút mạng đến hiệu suất của các giao thức định tuyến DSDV, AODV và DSR bằng bộ mô phỏng mạng NS-2. Từ đó đưa ra các nhận xét so sánh giữa ba giao thức. Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong MANET Phạm Văn Tứ 5 K51MMT 1.3 . Công cụ nghiên cứu chính – NS-2 1.3.1. Giới thiệu về NS-2 NS-2 là phần mềm mô phỏng mạng, hoạt động của nó được điều khiển bởi các sự kiện rời rạc. NS-2 được thiết kế và phát triển theo kiểu hướng đối tượng, được phát triển tại đại học California, Berkely. Bộ phần mềm này được viết bằng ngôn ngữ C++ và OTcl. Hình 2: Cấu trúc của NS-2 Cấu trúc của NS-2 bao gồm các thành phần được chỉ ra trên Hình 2, chức năng của chúng được mô tả như sau:  OTcl Script Kịch bản OTcl  Simulation Program Chương trình Mô phòng  OTcl Bộ biên dịch Tcl mở rộng hướng đối tượng  NS Simulation Library Thư viện Mô phỏng NS  Event Scheduler Objects Các đối tượng Bộ lập lịch Sự kiện  Network Component Objects Các đối tượng Thành phần Mạng  Network Setup Helping Modules Các mô đun Trợ giúp Thiết lập Mạng  Plumbling Modules Các mô đun Plumbling  Simulation Results Các kết quả Mô phỏng  Analysis Phân tích  NAM Network Animator Minh họa Mạng NAM Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong MANET Phạm Văn Tứ 6 K51MMT Trong hình 2 trên, NS là Bộ biên dịch Tcl mở rộng hướng đối tượng; bao gồm các đối tượng: Bộ lập lịch sự kiện, các đối tượng thành phần mạng và các mô đun trợ giúp thiết lập mạng. Để sử dụng NS-2, người dùng lập trình bằng ngôn ngữ kịch bản OTcl. Người dùng có thể thêm các mã nguồn Otcl