Luận văn Đánh giá ảnh hưởng của sự di động của nút mạng đến hiệu quả của các thuật toán định tuyến trong mạng manet

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHAN HỮU DŨNG ĐÁNH GIÁ ẢNH HƯỞNG CỦA SỰ DI ĐỘNG CỦA NÚT MẠNG ĐẾN HIỆU QUẢ CỦA CÁC THUẬT TOÁN ĐỊNH TUYẾN TRONG MẠNG MANET LUẬN VĂN THẠC SĨ Hà Nội - 2011 2 Lời cảm ơn Đầu tiên tôi xin gửi lời cảm ơn tới các thầy cô giáo trong Trường Đại học Công nghệ - Đại Học Quốc Gia Hà Nội, Viện Khoa học kỹ thuật Bưu điện và Viện Công nghệ Thông tin - Viện Khoa học và Công nghệ Việt Nam đã tận tình chỉ bảo tôi trong suốt khóa học; cảm ơn tập thể lớp K15T1, tập thể lớp K15 chuyên ngành Mạng và Truyền thông máy tính. Cảm ơn các thành viên trong nhóm nghiên cứu với những ý kiến góp ý quý báu trong quá trình tôi thực hiện đề tài, và đặc biệt tôi chân thành cảm ơn thầy hướng dẫn - PGS.TS Nguyễn Đình Việt, người đã tận tình hướng dẫn, chỉ bảo tôi trong học tập và nghiên cứu. Cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè của tôi, những người đã luôn ở bên động viên và khích lệ tôi trong suốt khóa học. Do thời gian và điều kiện có hạn nên luận văn không tránh khỏi có những thiếu sót, tôi rất mong nhận được sự góp ý từ bạn bè, thầy cô và những người quan tâm đến đề tài này. Let’s start at the very beginning, a very nice place to start, when you sing, you begin with A, B, C, when you simulate, you begin with the topology - The ns Manual 3 Lời cam đoan Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 01 tháng 05 năm 2011 Phan Hữu Dũng 4 Mục lục Lời cảm ơn ..................................................................................................................1 Lời cam đoan ...............................................................................................................3 Danh mục hình vẽ........................................................................................................7 Danh mục bảng............................................................................................................9 Bảng ký hiệu các chữ viết tắt .....................................................................................10 Chương 1: GIỚI THIỆU ............................................................................................12 1.1. Đặt vấn đề.......................................................................................................12 1.2. Mục tiêu nghiên cứu........................................................................................12 1.3. Tổ chức của luận văn ......................................................................................13 Chương 2: MẠNG WLAN VÀ MẠNG MANET ......................................................14 2.1. Mạng không dây .............................................................................................14 2.1.1. Mạng cục bộ WLAN ................................................................................14 2.1.1.1. Lịch sử ra đời mạng WLAN ..............................................................15 2.1.1.2. Phân loại mạng WLAN .....................................................................15 2.1.1.3. Các chuẩn đối với mạng WLAN........................................................17 2.1.2. Một số mạng không dây phổ biến khác.....................................................18 2.1.2.1. Mạng cá nhân WPAN theo chuẩn 802.15.1, 802.15.3 và 802.15.4.....18 2.1.2.2. Mạng đô thị WMAN theo chuẩn 802.16 ............................................18 2.1.2.3. Mạng diện rộng WWAN theo chuẩn 802.20 ......................................19 2.2. Mạng di động không dây đặc biệt MANET.....................................................19 2.2.1. Giới thiệu mạng MANET.........................................................................19 2.2.2. Các đặc điểm của mạng MANET .............................................................22 2.2.3. Phân loại ..................................................................................................22 2.2.3.1. Phân loại mạng MANET theo cách thức định tuyến ..........................22 2.2.3.2. Phân loại mạng MANET theo chức năng của Nút..............................23 Chương 3: CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET ................26 3.1. Các giao thức định tuyến phổ biến trong mạng có dây truyền thống................26 3.1.1. Distance Vector........................................................................................26 3.1.2. Link State.................................................................................................26 3.1.3. Source Routing.........................................................................................27 3.1.4. Kỹ thuật Flooding ....................................................................................27 3.2. Các yêu cầu đối với thuật toán định tuyến trong mạng MANET......................27 3.2.1. Mục tiêu thiết kế các giao thức định tuyến cho mạng MANET.................27 5 3.2.2. Áp dụng các thuật toán định tuyến truyền thống trong mạng MANET......28 3.3. Phân loại các giao thức định tuyến cho MANET [16]........................................29 3.3.1. Các khái niệm liên quan ...........................................................................30 3.3.1.1. Định tuyến chủ ứng và định tuyến phản ứng......................................30 3.3.1.2. Cập nhật định kỳ và cập nhật theo sự kiện .........................................30 3.3.1.3. Tính toán phi tập trung và tính toán phân tán .....................................31 3.3.1.4. Đơn đường và đa đường ....................................................................31 3.3.2. Phân loại các giao thức định tuyến ...........................................................31 3.3.2.1. Destination-Sequence Distance Vector (DSDV) ................................32 3.3.2.2. Optimized Link State Routing Protocol (OLSR)................................33 3.3.2.3. Ad hoc On-demand Distance Vector Routing (AODV) .....................35 3.3.2.4. Dynamic Source Routing (DSR) [12] ..................................................36 3.3.2.5. So sánh các giao thức định tuyến cho MANET..................................38 Chương 4: NGHIÊN CỨU VIỆC SỬ DỤNG CÔNG CỤ MÔ PHỎNG VÀ PHÂN TÍCH KẾT QUẢ .......................................................................................................41 4.1. Lựa chọn phương pháp và công cụ đánh giá hiệu năng mạng [1] ......................41 4.1.1. Lựa chọn phương pháp .............................................................................41 4.1.1.1. Mô hình Giải tích ..............................................................................42 4.1.1.2. Mô phỏng mạng bằng chương trình máy tính ....................................42 4.1.1.3. Đo trên mạng thực .............................................................................42 4.1.1.4. Lý do sử dụng phương pháp mô phỏng để đánh giá hiệu năng mạng .43 4.1.2. Công cụ mô phỏng NS-2 [1, 12, 15]...............................................................43 4.1.2.1. Các chức năng mô phỏng chính của NS.............................................45 4.1.2.2 Cấu trúc phần mềm của NS ................................................................46 4.1.2.3. Lập trình mô phỏng bằng NS.............................................................46 4.1.3 Công cụ hỗ trợ phân tích kết quả mô phỏng...............................................46 4.1.3.1 Cấu trúc tệp vết chứa kết quả mô phỏng mạng không dây ..................46 4.1.3.2 Một số công cụ hỗ trợ việc phân tích và hiển thị kết quả mô phỏng ....47 4.1.4. Công cụ hiển thị trực quan mạng MANET trong quá trình hoạt động iNSPECT ...........................................................................................................48 4.2. Thiết lập mô phỏng mạng MANET trong NS..................................................53 4.2.1. Tạo các nút mạng trong MANET .............................................................53 4.2.1.1 Nút di động.........................................................................................53 4.4.1.2 Mô hình phương tiện chia sẻ trong NS2..............................................54 4.4.1.3 Hoạt động của nút di động..................................................................55 4.4.1.4 Cấu hình nút di động trong NS ...........................................................56 6 4.4.1.5 Tạo sự di chuyển của nút trong NS .....................................................57 4.4.2. Tạo các đường truyền không dây (air interface) trong MANET................58 4.4.2.1 Mô hình FreeSpace.............................................................................58 4.4.2.2 Mô hình Two Ray Ground..................................................................58 4.4.2.3 Mô hình Shadowing ...........................................................................59 4.4.3. Tạo ngữ cảnh chuyển động.......................................................................59 4.4.3.1 Tạo diện tích mô phỏng ......................................................................60 4.4.3.2. Tạo các thực thể giao thức và các nguồn sinh lưu lượng ....................60 4.4.3.3. Tạo các dạng chuyển động theo mẫu .................................................61 4.4.4. Sơ đồ khái quát quá trình mô phỏng .........................................................64 4.5 Các tham số hoạt động của các giao thức định tuyến trong NS-2......................65 4.5.1 Giao thức định tuyến DSDV......................................................................65 4.5.2 Giao thức định tuyến OLSR ......................................................................66 4.5.3 Giao thức định tuyến AODV .....................................................................66 4.5.4 Giao thức định tuyến DSR.........................................................................67 Chương 5: ĐÁNH GIÁ HIỆU NĂNG CÁC GIAO THỨC ĐỊNH TUYẾN THEO MỨC ĐỘ LINH ĐỘNG CỦA CÁC NÚT MẠNG.....................................................68 5.1. Thực nghiệm mô phỏng ..................................................................................68 5.1.1 Các thông số mô phỏng .............................................................................68 5.1.2 Chương trình mô phỏng ............................................................................69 5.2. Các độ đo hiệu năng được dùng trong luận văn ...............................................70 5.3. Kết quả mô phỏng...........................................................................................70 5.3.1 Mô phỏng sử dụng mô hình Random Waypoint.........................................70 5.3.1.1 Thiết lập thông số mô phỏng ..............................................................70 5.3.2.2 Kết quả và nhận xét ............................................................................72 5.3.3 Mô phỏng sử dụng mô hình Random Walk ...............................................75 5.3.3.1 Thiết lập thông số mô phỏng ..............................................................75 5.3.3.2 Kết quả và nhận xét ............................................................................77 5.3.4 Đánh giá hiệu quả của các giao thức định tuyến ........................................79 Chương 6: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU...............................................81 6.1. Kết quả đạt được của luận văn.........................................................................81 6.2. Hướng nghiên cứu...........................................................................................82 TÀI LIỆU THAM KHẢO..........................................................................................83 PHỤ LỤC..................................................................................................................84 7 Danh mục hình vẽ Hình 1. Phân loại các mạng không dây dựa trên quy mô. ..........................................14 Hình 2. Mạng WLAN có cơ sở hạ tầng .....................................................................16 Hình 3. Mạng WLAN không có cơ sở hạ tầng [10] ...................................................17 Hình 4. Mạng MANET và Sensor không dây [14].....................................................21 Hình 5. Định tuyến Single-hop..................................................................................23 Hình 6. Định tuyến Multi-hop ...................................................................................23 Hình 7. Mạng MANET phân cấp ..............................................................................24 Hình 8. Mạng MANET kết hợp.................................................................................24 Hình 9. Phân loại các giao thức định tuyến trong mạng MANET [13].......................32 Hình 10. Tập chuyển tiếp đa điểm MPRs ..................................................................34 Hình 11. Định tuyến Link State và định tuyến cải tiến trong OLSR............................34 Hình 12. AODV tìm kiếm và duy trì tuyến đường .....................................................36 Hình 13. Ví dụ về Route discovery: nút A là nút nguồn, nút E là nút đích. ................37 Hình 14. Ví dụ về Route maintenance: ......................................................................38 Hình 15. Kiến trúc NS-2 ...........................................................................................44 Hình 16. Ba giai đoạn của một phiên truyền từ nút nguồn 1 đến nút đích 48 .............49 Hình 17. Hình tròn bao phủ biểu diễn khu vực tắc nghẽn ..........................................50 Hình 18. Hình tròn bao phủ biểu diễn khu vực nguy hiểm.........................................51 Hình 19. iNSpect hiển thị tọa độ (x, y) của các nút ....................................................52 Hình 20. Nút di động mô phỏng trong NS2 ...............................................................53 Hình 21. Mô hình phương tiện chia sẻ trong NS2......................................................55 Hình 22. Sơ đồ của một mobilenode dưới chuẩn wireless của Monarch CMU mở rộng ra NS [12] ..................................................................................................................57 Hình 23. Các mô hình truyền thông trong NS2..........................................................60 Hình 24. Di chuyển của một nút theo mô hình Random Waypoint ............................62 Hình 25. Di chuyển của một nút theo mô hình Random Walk ...................................63 Hình 26. Sơ đồ tổng quan quá trình mô phỏng ..........................................................64 Hình 27. Đánh giá kết quả phân phát gói tin trong mô hình Random Waypoint.........72 Hình 28. Đánh giá kết quả trễ đầu cuối trong mô hình Random Waypoint ................72 Hình 29. Đánh giá kết quả thông lượng trong mô hình Random Waypoint................73 Hình 30. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Waypoint ..............73 Hình 31. Đánh giá kết quả phân phát gói tin trong mô hình Random Walk ...............77 Hình 32. Đánh giá kết quả trễ đầu cuối trong mô hình Random Walk .......................77 Hình 33. Đánh giá kết quả thông lượng trong mô hình Random Walk.......................78 8 Hình 34. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Walk.....................78 9 Danh mục bảng Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2] ................................................17 Bảng 2. Tổng quan về họ các chuẩn ETSI HIPERLAN [2]........................................17 Bảng 3. Tổng quan về họ các chuẩn IEEE 802.15 .....................................................18 Bảng 4: So sánh độ phức tạp của các giao thức định tuyến ........................................39 Bảng 5: So sánh các đặc điểm của các giao thức định tuyến ......................................39 Bảng 6: So sánh các đặc điểm của các giao thức định tuyến ......................................40 Bảng 7. Các tham số của mô hình Random Waypoint ..............................................62 Bảng 8. Các tham số của mô hình Random Walk ......................................................63 Bảng 9. Các tham số hoạt động của DSDV trong NS2...............................................65 Bảng 10. Các tham số hoạt động của OLSR trong NS2 .............................................66 Bảng 11. Các tham số hoạt động của AODV trong NS2 ............................................66 Bảng 12. Các tham số hoạt động của DSR trong NS2................................................67 Bảng 13. Cấu hình các mạng mô phỏng trong mô hình Random Waypoint ...............71 Bảng 14. Cấu hình các mạng mô phỏng theo mô hình Random Walk........................76 10 Bảng ký hiệu các chữ viết tắt AODV Ad hoc On-demand Distance Vector CSMA/CA Carrier Sense Multiple Access with Collision Avoidance DARPA Defense Advanced Research Projects Agency DSDV Destination-Sequenced Distance Vector DSR Dynamic Source Routing DV Distance Vector ETSI European Telecommunications Standards Institute FCC US Federal Communications Commission FIFO First In First Out GPRS General Packet Radio Service GSM Global System for Mobile communication HiperLAN High Performance European Radio LAN IEEE Institute of Electrical and Electronic Engineering IETF Internet Engineering Task Force iNSpect interactive NS-2 protocol and environment confirmation tool ISM Industrial, Scientific and Medical bands LAN Local Area Network LS Link State MAC Media Access Control MANET Mobile Wireless Adhoc Network NEST Network Simulation Testbed NS2 Network Simulator 2 OLSF Open Shortest Path First OLSR Optimized Link State Routing Protocol 11 PDA Personal Digital Assistant PRnet Packet Radio Network QoS Quality of Service REAL Realistic and Large RIP Routing Information Protocol RREP Route Reply RREQ Route Request RTS Request To Send SURAN Survivable Radio Network TDMA/TDD Time Division Multiple Access/ Time Division Duplex TORA Temporally-Ordered Routing Algorithm UMTS Universal Mobile Telecommunications Systems VINT Virtual InterNetwork Testbed WIFI Wireless Fidelity WiMAX World Interoperability for MicroAccess WLAN Wireless Local Area Network WMAN Wireless Metropolitan Area Networks WPAN Wireless Personal Area Networks WRP Wireless Routing Protocol WWAN Wireless Wide Area Networks ZRP Zone Routing Protocol 12 Chương 1: GIỚI THIỆU 1.1. Đặt vấn đề Mạng di động không dây đặc biệt MANET (Mobile Wireless Adhoc Network) cho phép các máy tính di động thực hiện kết nối và truyền thông với nhau không cần dựa trên cơ sở hạ tầng mạng có dây. Trong MANET mọi nút mạng đều có thể thực hiện chức năng của một router, chúng cộng tác với nhau, thực hiện chuyển tiếp các gói tin hộ các nút mạng khác nếu các nút mạng này không thể truyền trực tiếp với nút nhận. Định tuyến là bài toán quan trọng nhất đối với việc nghiên cứu MANET. Cho đến nay, đã có nhiều thuật toán định tuyến được đề xuất, mỗi thuật toán đều có các ưu và nhược điểm riêng. Điều đặc biệt là mức độ của các ưu nhược điểm phụ thuộc rất nhiều vào mức độ di động của các nút mạng. Một số thuật toán là ưu việt hơn các thuật toán khác trong điều kiện các nút mạng di động ở mức độ thấp nhưng lại kém hơn hẳn khi mức độ di động của các nút mạng tăng cao. Đề tài