Tài liệu Nghiên cứu cải tiến hiệu năng giao thức định tuyến aodv và aomdv trong mạng manet

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- ĐỖ ĐÌNH CƯỜNG NGHIÊN CỨU CẢI TIẾN HIỆU NĂNG GIAO THỨC ĐỊNH TUYẾN AODV VÀ AOMDV TRONG MẠNG MANET LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2017 VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ……..….***………… ĐỖ ĐÌNH CƯỜNG NGHIÊN CỨU CẢI TIẾN HIỆU NĂNG GIAO THỨC ĐỊNH TUYẾN AODV VÀ AOMDV TRONG MẠNG MANET LUẬN ÁN TIẾN SĨ TOÁN HỌC Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 Người hướng dẫn khoa học: 1. PGS. TS. Nguyễn Văn Tam 2. PGS. TS. Nguyễn Gia Hiểu Hà Nội – 2017 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi. Những nội dung, số liệu và kết quả trình bày trong luận án là hoàn toàn trung thực và chưa có tác giả nào công bố trong bất kỳ một công trình nào khác. Tác giả luận án Đỗ Đình Cường LỜI CẢM ƠN Luận án này được thực hiện tại Viện Công nghệ thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Lời đầu tiên, NCS xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Nguyễn Văn Tam và PGS. TS. Nguyễn Gia Hiểu, những người thầy đã tận tình định hướng nghiên cứu, đào tạo và hướng dẫn NCS trong suốt quá trình học tập và nghiên cứu để hoàn thành luận án này. NCS xin được cảm ơn Viện Công nghệ Thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam, đặc biệt là các cán bộ Phòng Tin học Viễn thông đã nhiệt tình đóng góp ý kiến vào luận án và giúp đỡ NCS trong quá trình nghiên cứu. NCS xin được cảm ơn ban lãnh đạo và các cán bộ của Học viện Khoa học và Công nghệ, đặc biệt là PGS. TS. Đặng Văn Đức và TS. Nguyễn Long Giang đã tạo mọi điều kiện thuận lợi cho NCS trong suốt quá trình học tập và nghiên cứu tại Học viện trong suốt thời gian nghiên cứu đề tài. NCS xin được bày tỏ lòng biết ơn chân thành tới các Thầy, Cô, các nhà khoa học trong và ngoài Viện đã chân thành góp ý và giúp đỡ cho NCS hoàn thành luận án này. Cuối cùng, NCS cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn hỗ trợ, động viên, chia sẻ và giúp NCS có thêm quyết tâm và động lực vượt qua những khó khăn để quyết tâm hoàn thành luận án này. Xin trân trọng cảm ơn! MỤC LỤC MỤC LỤC ......................................................................................................... i DANH MỤC CÁC TỪ VIẾT TẮT ................................................................ iii DANH MỤC CÁC HÌNH VẼ ......................................................................... vi DANH MỤC CÁC BẢNG BIỂU ................................................................. viii MỞ ĐẦU .......................................................................................................... 1 CHƯƠNG 1. TỔNG QUAN VỀ MẠNG MANET VÀ VẤN ĐỀ ĐỊNH TUYẾN TRONG MẠNG MANET .................................................................. 7 1.1. Giới thiệu về mạng MANET ................................................................. 8 1.1.1. Khái niệm mạng MANET ............................................................... 8 1.1.2. Đặc điểm của mạng MANET ......................................................... 9 1.1.3. Ứng dụng của mạng MANET ....................................................... 10 1.1.4. Dung lượng truyền tải của mạng MANET ................................... 12 1.2. Định tuyến trong mạng MANET ......................................................... 14 1.2.1. Những yêu cầu cơ bản của giao thức định tuyến trong mạng MANET .................................................................................................. 14 1.2.2. Một số chiến lược định tuyến trong mạng MANET ..................... 15 1.2.3. Một số hướng nghiên cứu cải tiến giao thức định tuyến trong mạng MANET .................................................................................................. 21 1.3. Định tuyến dạng véc tơ khoảng cách, định tuyến đa đường trong mạng MANET và những nghiên cứu cải tiến ....................................................... 25 1.3.1. Vấn đề giảm tắc nghẽn và đảm bảo QoS trong mạng MANET sử dụng giao thức định tuyến véc tơ khoảng cách ....................................... 25 1.3.2. Giao thức định tuyến AODV ........................................................ 28 1.3.3. Giao thức định tuyến AOMDV..................................................... 38 1.3.4. Một số nghiên cứu cải tiến giao thức định tuyến AODV và AOMDV ................................................................................................. 41 1.4. Đánh giá hiệu năng mạng .................................................................... 51 1.5. Mục tiêu và hướng tiếp cận của luận án .............................................. 53 1.6. Kết luận Chương 1 ............................................................................... 54 CHƯƠNG 2. CẢI TIẾN GIAO THỨC AODV NHẰM GIẢM TẮC NGHẼN TRONG MẠNG MANET .............................................................................. 56 2.1. Đề xuất ý tưởng cải tiến cho giao thức AODV .................................... 56 2.2. Phương pháp ước lượng trễ của liên kết .............................................. 57 2.2.1. Phân tích độ trễ của liên kết theo cơ chế DCF .............................. 57 2.2.2. Ước lượng thời gian trễ theo thời gian phục vụ ............................ 59 2.3. Cải tiến giao thức AODV .................................................................... 65 i 2.3.1. Đề xuất mô hình định tuyến theo hướng tiếp cận xuyên tầng ...... 65 2.3.2. Mô đun đo mức độ sử dụng kênh truyền ...................................... 66 2.3.3. Mô đun ước lượng tỉ lệ lỗi frame của liên kết .............................. 69 2.3.4. Mô đun định tuyến ........................................................................ 74 2.4. Kiểm nghiệm và đánh giá kết quả........................................................ 77 2.4.1. Các độ đo đánh giá hiệu năng ....................................................... 77 2.4.2. Kịch bản mô phỏng ....................................................................... 77 2.4.3. Các kết quả và đánh giá ................................................................ 79 2.5. Kết luận Chương 2 ............................................................................... 90 CHƯƠNG 3. CẢI TIẾN GIAO THỨC AOMDV NHẰM ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ CHO MẠNG MANET ................................................... 91 3.1. Đề xuất ý tưởng cải tiến cho giao thức AOMDV ................................ 91 3.2. Xây dựng hàm lượng giá đường theo QoS .......................................... 93 3.2.1. Phân lớp các ứng dụng theo yêu cầu QoS .................................... 93 3.2.2. Phương pháp ra quyết định chọn đường ....................................... 93 3.2.3. Xác định trọng số của các tiêu chuẩn QoS ................................... 96 3.3. Dự đoán chất lượng liên kết tại tầng MAC ........................................ 100 3.4. Cải tiến giao thức AOMDV ............................................................... 100 3.4.1. Xây dựng hàm lượng giá đường ................................................. 100 3.4.2. Đề xuất cơ chế định tuyến QoS cho giao thức QCLR ................ 102 3.5. Kiểm nghiệm và đánh giá kết quả...................................................... 104 3.5.1. Kịch bản mô phỏng ..................................................................... 104 3.5.2. Các độ đo đánh giá hiệu năng ..................................................... 106 3.5.3. Các kết quả và đánh giá .............................................................. 107 3.6. Kết luận Chương 3 ............................................................................. 114 KẾT LUẬN ................................................................................................... 116 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN ........ 118 TÀI LIỆU THAM KHẢO ............................................................................ 119 ii DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Nghĩa tiếng Việt ACK Acknowledgement Gói báo nhận AODV Ad hoc On-Demand Distance Vector Giao thức định tuyến theo yêu cầu dạng véc tơ khoảng cách AODV-DM Ad hoc On-demand Distance Vector with Delay Metric Giao thức định tuyến theo yêu cầu dạng véc tơ khoảng cách có độ đo định tuyến thời gian trễ AOMDV Giao thức định tuyến đa đường Ad hoc On-demand theo yêu cầu dạng véc tơ Multipath Distance Vector khoảng cách CGSR Cluster-head Gateway Switch Routing Protocol Giao thức định tuyến chuyển tiếp giữa các vùng có nút quản lý CNU Channel Utilization Mức độ sử dụng kênh truyền CSMA/CA Carrier Sense Multiple Access with Collision Avoidance Cơ chế đa truy cập bằng cách cảm nhận kênh truyền với kỹ thuật phòng tránh xung đột CW Contention Window Cửa sổ tương tranh DCF Distributed Coordination Function Hàm điều phối phân tán DIFS Distributed Inter Frame Space Khoảng cách phân bố giữa các frame DSDV Destination Sequence Distance Vector Routing Protocol Giao thức định tuyến dạng véc tơ khoảng cách sử dụng số thứ tự đích DSR Dynamic Source Routing Protocol Giao thức định tuyến nguồn động ETX Expected Transmission Count Đếm số gói nhận được theo kỳ vọng iii FER Frame Error Rate Tỉ lệ lỗi frame HSR Hierarchical State Routing Giao thức định tuyến theo cơ Protocol chế phân cấp MAC Media Access Control Điều khiển truy cập môi trường truyền MANET Mobile Ad hoc Network Mạng di động không dây kiểu không cấu trúc MPDU MAC Protocol Data Unit Đơn vị dữ liệu giao thức tầng MAC OLSR Optimized Link State Routing Protocol Giao thức định tuyến tối ưu theo trạng thái liên kết PLCP Physical Layer Convergence Protocol Giao thức hội tụ tầng Vật lý PNS Passed Node Set Tập các nút frame đã đi qua PPDU PLCP Protocol Data Unit Đơn vị dữ liệu giao thức tầng PLCP PSDU PLCP Service Data Unit Đơn vị dữ liệu dịch vụ tầng PLCP QCLR QoS Cross-Layer Routing Giao thức định tuyến xuyên tầng đảm bảo chất lượng dịch vụ QoS Quality of Service Chất lượng dịch vụ RMV Routing Metric Value Giá trị độ đo định tuyến RREP Route Reply Gói trả lời đường RREQ Route Request Gói truy vấn đường RRER Route Error Gói báo lỗi đường SIFS Short Inter Frame Space Khoảng cách ngắn giữa các frame SNS Source Node Set Tập các nút nguồn ST Slot Time Khe thời gian iv TDMA Time Division Multiple Access Đa truy cập trên cơ sở phân chia thời gian TORA Temporally Ordered Routing Algorithm Protocol Giao thức định tuyến theo thuật toán đánh số thứ tự tạm thời ZRP Zone Routing Protocol Giao thức định tuyến theo vùng WSN Wireless Sensor Network Mạng cảm biến không dây v DANH MỤC CÁC HÌNH VẼ Hình 1.1. Một ví dụ của mạng MANET ........................................................... 8 Hình 1.2. Đường truyền dữ liệu theo chiến lược định tuyến phẳng ............... 17 Hình 1.3. Đường truyền dữ liệu theo chiến lược định tuyến phân cấp ........... 18 Hình 1.4. Truyền dữ liệu theo chiến lược định tuyến nguồn .......................... 19 Hình 1.5. Truyền dữ liệu theo chiến lược định tuyến từng chặng .................. 20 Hình 1.6. Cấu trúc gói RREQ ......................................................................... 31 Hình 1.7. Cấu trúc gói RREP .......................................................................... 33 Hình 1.8. Cấu trúc gói RRER ......................................................................... 35 Hình 1.9. Quá trình truyền yêu cầu tìm đường bằng gói RREQ..................... 36 Hình 1.10. Quá trình truyền trả lời đường bằng gói RREP ............................ 37 Hình 1.11. Ví dụ về định tuyến lặp khi vi phạm quy tắc quảng bá đường ..... 39 Hình 1.12. Ví dụ về định tuyến lặp khi vi phạm quy tắc chấp nhận đường ... 40 Hình 2.1. CSMA/CA ở chế độ cơ bản ............................................................ 57 Hình 2.2. CSMA/CA với kỹ thuật cảm nhận sóng mang ảo........................... 58 Hình 2.3. Kiến trúc tầng con MAC và tầng Vật lý ......................................... 60 Hình 2.4. Cấu trúc của PPDU dài ................................................................... 60 Hình 2.5. Cấu trúc của PPDU ngắn ................................................................ 61 Hình 2.6. Các mô đun của giao thức AODV-DM .......................................... 65 Hình 2.7. Cấu trúc gói tin FER_PROBE ........................................................ 70 Hình 2.8. Mô hình kịch bản mô phỏng ........................................................... 78 Hình 2.9. Thông lượng trung bình của giao thức trong Kịch bản 1................ 80 Hình 2.10. Thông lượng trung bình của giao thức trong Kịch bản 2.............. 82 Hình 2.11. Tỷ lệ truyền gói thành công của giao thức trong Kịch bản 1 ........ 83 Hình 2.12. Tỷ lệ truyền gói thành công của giao thức trong Kịch bản 2 ........ 84 Hình 2.13. Trễ truyền gói trung bình của trong thức trong Kịch bản 1 .......... 86 Hình 2.14. Trễ truyền gói trung bình của giao thức trong Kịch bản 2............ 87 Hình 2.15. Tải định tuyến của giao thức trong Kịch bản 1 ............................. 87 Hình 2.16. Tải định tuyến của giao thức trong Kịch bản 2 ............................. 89 vi Hình 3.1. Cây AHP cho bài toán chọn đường đa tiêu chuẩn .......................... 96 Hình 3.2. Trễ truyền gói trung bình của giao thức QCLR & AOMDV ........ 108 Hình 3.3. Thông lượng trung bình của giao thức QCLR & AOMDV .......... 109 Hình 3.4. Tỉ lệ truyền thành công của giao thức QCLR & AOMDV ........... 111 Hình 3.5. Tải định tuyến của giao thức QCLR & AOMDV ......................... 112 Hình 3.6. Độ biến thiên trễ truyền gói của giao thức QCLR & AOMDV .... 114 vii DANH MỤC CÁC BẢNG BIỂU Bảng 1.1. Phân loại các chiến lược định tuyến của mạng MANET ............... 15 Bảng 2.1. Thông lượng hiệu dụng của liên kết IEEE 802.11b ....................... 63 Bảng 2.2. Giá trị của tham số FER trong các chu kỳ liên tiếp ........................ 73 Bảng 2.3. Thông lượng trung bình của giao thức trong Kịch bản 1 ............... 80 Bảng 2.4. Thông lượng trung bình của giao thức trong Kịch bản 2 ............... 81 Bảng 2.5. Tỷ lệ truyền gói thành công của giao thức trong Kịch bản 1 ......... 83 Bảng 2.6. Tỷ lệ truyền gói thành công của giao thức trong Kịch bản 2 ......... 84 Bảng 2.7. Trễ truyền gói trung bình của giao thức trong Kịch bản 1 ............. 85 Bảng 2.8. Trễ truyền gói trung bình của giao thức trong Kịch bản 2 ............. 86 Bảng 2.9. Tải định tuyến của giao thức trong Kịch bản 1 .............................. 88 Bảng 2.10. Tải định tuyến của giao thức trong Kịch bản 2 ............................ 89 Bảng 3.1. Các ngưỡng QoS theo các lớp lưu lượng ....................................... 93 Bảng 3.2. Lượng hoá độ quan trọng của các tiêu chuẩn QoS Lớp 1 .............. 97 Bảng 3.3. Lượng hoá độ quan trọng của các tiêu chuẩn QoS Lớp 2 .............. 97 Bảng 3.4. Lượng hoá độ quan trọng của các tiêu chuẩn QoS Lớp 3 .............. 98 Bảng 3.5. Quan hệ giữa chỉ số n và RI ........................................................... 99 Bảng 3.6. Trọng số của các tiêu chuẩn QoS theo các lớp lưu lượng ............ 100 Bảng 3.7. Trọng số của các tiêu chuẩn QoS trong hàm lượng giá đường .... 102 Bảng 3.8. Các tham số chung của mô phỏng ................................................ 106 Bảng 3.9. Các tham số riêng của mô phỏng ................................................. 106 Bảng 3.10. Trễ truyền gói trung bình của giao thức QCLR và AOMDV..... 107 Bảng 3.11. Thông lượng trung bình của giao thức QCLR và AOMDV....... 109 Bảng 3.12. Tỉ lệ truyền thành công của giao thức QCLR và AOMDV ........ 110 Bảng 3.13. Tải định tuyến của giao thức QCLR và AOMDV ...................... 112 Bảng 3.14. Độ biến thiên trễ trung bình của giao thức QCLR và AOMDV 113 viii MỞ ĐẦU Ngày nay, mạng truyền thông đóng một vai trò vô cùng quan trọng trong đời sống, kinh tế, xã hội của con người. Nhu cầu truyền thông trên một hệ thống mạng đa dữ liệu, tích hợp các loại mạng có dây và không dây khác nhau với hệ thống mạng lõi Internet, hỗ trợ các dịch vụ đa phương tiện ở tốc độ cao cho nhiều loại dữ liệu khác nhau, hỗ trợ khả năng di chuyển của các thiết bị di động thông minh một cách nhanh chóng, thuận lợi, linh hoạt trên phạm vi toàn cầu đã và đang là xu hướng phát triển của hệ thống mạng truyền thông hiện đại. Mô hình mạng thế hệ 4 (4G) ra đời nhằm mục đích đáp ứng cho nhu cầu này. Trong mô hình mạng 4G [10], xoay quanh hệ thống mạng lõi Internet, cùng với mạng viễn thông tế bào, mạng viễn thông vệ tinh, mạng không dây diện rộng, mạng không dây cục bộ, đã có sự xuất hiện của mạng không dây kiểu không cấu trúc (MANET). Sự xuất hiện này cho thấy tầm quan trọng của mạng MANET trong công nghệ mạng truyền thông hiện đại và khả năng ứng dụng rộng rãi của nó vào nhiều lĩnh vực khác nhau từ hỗ trợ tác chiến trong quân đội; dự báo và cảnh báo thiên tai, thảm họa; ứng dụng thương mại, gia đình, văn phòng, giáo dục và giải trí; theo dõi và điều hành giao thông tới các dịch vụ theo dõi và chăm sóc sức khỏe cho con người. Được hình thành bởi các kết nối tạm thời giữa các nút mạng di động không có sự hỗ trợ của cơ sở hạ tầng mạng cố định, mạng MANET có nhiều những đặc điểm khác biệt so với mạng không dây và có dây truyền thống [33] làm nảy sinh nhiều thách thức và các hướng nghiên cứu khác nhau [68]: vấn đề định tuyến hiệu quả khi topo mạng thay đổi, đảm bảo chất lượng dịch vụ theo yêu cầu từ chương trình ứng dụng, đảm bảo an ninh mạng, tiết kiệm năng lượng, khả năng tự tổ chức, chuyển đổi các dịch vụ từ mô hình client-server và đảm bảo hiệu năng khi kích thước mạng thay đổi. Kết quả nghiên cứu phân loại và đánh giá về số lượng các nghiên cứu theo các hướng khác nhau đối với mạng MANET trong thời gian gần đây [81] cho thấy, hướng nghiên cứu về định tuyến 1 trong mạng MANET đứng đầu về số lượng các nghiên cứu đã được công bố. Như vậy, có thể khẳng định, định tuyến trong mạng MANET đã và đang là một vấn đề rất cần được quan tâm giải quyết trong những nghiên cứu cải tiến hiệu năng mạng MANET. Đã có nhiều cải tiến nghiên cứu được đề xuất nhằm cải tiến các giao thức định tuyến cho mạng MANET. Có thể phân nhóm các nghiên cứu này theo mục tiêu của chúng bao gồm: Tăng độ bền vững của đường được chọn [105, 48, 59]; Nâng cao hiệu quả định tuyến [82, 80, 45, 29, 8, 85, 65]; Đảm bảo an ninh trong định tuyến [42, 107, 97, 104]; Định tuyến hỗ trợ QoS [18, 94, 83, 41]; Định tuyến với cơ chế tiết kiệm năng lượng [90, 58, 88, 12]. Tuy nhiên, mỗi đề xuất cải tiến chỉ áp dụng cho một giao thức định tuyến hoặc một nhóm các giao thức có chung một chiến lược định tuyến nhất định. Các so sánh đánh giá về hiệu năng của các giao thức đã cải tiến so với các giao thức ban đầu cũng chỉ tập trung vào một số mô hình toán học và kịch bản mô phỏng nhất định. Vì vậy, trong từng ngữ cảnh triển khai mạng MANET với các yêu cầu cụ thể, cần lựa chọn, cải tiến và sử dụng giao thức định tuyến một cách phù hợp. Đối với các giao thức định tuyến véc tơ khoảng cách sử dụng thuật toán tìm đường ngắn nhất theo số chặng, các nghiên cứu trong [6, 13, 73, 87] đã chỉ ra rằng, thuật toán tìm đường ngắn nhất theo số chặng chưa phải là thuật toán tối ưu dành cho mạng MANET. Đường ngắn nhất có xu hướng đi qua tâm của mạng gây tắc nghẽn cục bộ ở các nút phân bố gần tâm của mạng. Vì vậy, cần cải tiến cơ chế tìm đường của các giao thức định tuyến này nhằm giảm tắc nghẽn gây ra bởi các lưu lượng bị tập trung tại vùng trung tâm của mạng. AODV [69] là một trong các giao thức định tuyến tiêu biểu trong nhóm các giao thức định tuyến đơn đường có cơ chế định tuyến kết hợp giữa chiến lược định tuyến tìm đường theo yêu cầu với các chiến lược định tuyến cập nhật theo sự kiện, định tuyến phẳng, định tuyến từng chặng và định tuyến phân tán. Từ khi được giới thiệu lần đầu vào năm 2001 cho tới nay, đã có nhiều đề xuất 2 cải tiến giao thức AODV theo các mục tiêu: Đảm bảo tính sẵn sàng chuyển tiếp dữ liệu [9, 46, 44, 23], tiết kiệm năng lượng [30, 3, 77], hỗ trợ QoS [19] và đảm bảo an ninh định tuyến [56, 27, 91, 11]. Trong số các đề xuất cải tiến này, có nhiều đề xuất đã sử dụng phương pháp khai thác thông tin định tuyến theo cách tiếp cận xuyên tầng để xây dựng cơ chế định tuyến với độ đo định tuyến mới thay cho độ đo số chặng của giao thức AODV nhưng không hướng tới mục tiêu giảm tắc nghẽn gây ra bởi thuật toán tìm đường ngắn nhất theo số chặng đã đề cập ở trên. Đối với vấn đề định tuyến QoS, các giao thức định tuyến phải có khả năng chọn đường phù hợp theo yêu cầu QoS của dữ liệu cần truyền. Tại mỗi nút mạng, các luồng dữ liệu có yêu cầu QoS khác nhau cần được truyền theo các con đường khác nhau. Do các giao thức định tuyến đơn đường chỉ hỗ trợ tìm một đường duy nhất sau tiến trình định tuyến nên không thể chọn được các đường khác nhau theo các luồng dữ liệu có yêu cầu QoS khác nhau. Do đó, các giao thức định tuyến đa đường là lựa chọn thích hợp để tích hợp cơ chế định tuyến QoS. Các giao thức định tuyến đa đường có khả năng tìm và sử dụng nhiều đường đồng thời từ một nút nguồn tới một nút đích. Trong thời gian qua, đã có nhiều giao thức định tuyến đa đường được đề xuất [86]. Đa phần những đề xuất này được thực hiện trên cơ sở cải tiến hoạt động của các giao thức định tuyến tìm đường theo yêu cầu. Theo mục tiêu thiết kế, có thể phân loại các giao thức định tuyến đa đường theo các nhóm: giảm thời gian trễ [20, 34, 37, 51, 52], tăng độ tin cậy [17, 49, 55, 87, 89, 93, 98, 100], giảm phụ tải cho các gói điều khiển [5, 47, 60, 62, 96, 101, 106], tiết kiệm năng lượng [28, 50] và định tuyến lai [92, 95]. Tuy nhiên trong các giao thức đã được đề xuất này, vấn đề định tuyến theo yêu cầu QoS của các lớp chương trình ứng dụng phân loại theo chuẩn ITU-T G.1010 [36] vẫn chưa được giải quyết. 3 Với những lý do được phân tích ở trên, luận án này tập trung vào giải quyết vào hai vấn đề chính: 1) Cải tiến giao thức định tuyến AODV nhằm nâng cao hiệu năng mạng MANET có các vùng tắc nghẽn; 2) Cải tiến giao thức định tuyến AOMDV nhằm hỗ trợ cơ chế định tuyến QoS cho mạng MANET. Đối tượng, phạm vi và mục tiêu nghiên cứu Trong khuôn khổ giới hạn điều kiện và thời gian nghiên cứu, luận án này lựa chọn các giao thức định tuyến trong mạng MANET là đối tượng nghiên cứu với phạm vi nghiên cứu được giới hạn trong vấn đề xây dựng các độ đo định tuyến thích hợp và cải tiến cơ chế định tuyến theo hướng tiếp cận xuyên tầng của giao thức định tuyến AODV và AOMDV nhằm đảm bảo mục tiêu nghiên cứu là tăng cường hiệu năng định tuyến của giao thức AODV trong mạng MANET có các vùng tắc nghẽn và cung cấp khả năng định tuyến theo chất lượng dịch vụ cho giao thức AOMDV trong mạng MANET. Phương pháp nghiên cứu Phương pháp nghiên cứu được sử dụng trong luận án là phương pháp kết hợp giữa nghiên cứu lý thuyết và thử nghiệm để đánh giá kết quả. Trên cơ sở phân tích, đánh giá hoạt động của một số giao thức định tuyến, luận án sẽ rút ra những điểm cần cải tiến. Sau đó, sử dụng toán học làm công cụ để ước lượng và tính các tham số cần thiết cho các thuật toán định tuyến được đề xuất. Luận án sử dụng phương pháp thử nghiệm bằng mô phỏng để so sánh, đánh giá kết quả về hiệu năng của các giao thức đã được cải tiến. Nội dung nghiên cứu và kết quả cần đạt được Luận án tập trung vào ba nội dung chính sau: 1) Nghiên cứu, phân tích và đánh giá hoạt động của giao thức định tuyến AODV và AOMDV để tìm ra những điểm cần cải tiến; 2) Cải tiến giao thức AODV để nâng cao hiệu năng của mạng MANET có các vùng tắc nghẽn; 3) Cải tiến giao thức AOMDV nhằm đảm bảo yêu cầu chất lượng dịch vụ của các ứng dụng trong mạng MANET. 4 Trên cơ sở các nội dung nghiên cứu này, các kết quả cần đạt được của luận án bao gồm: 1) Đưa ra được những yêu cầu cần cải tiến đối với giao thức AODV trong mạng có tắc nghẽn và giao thức AOMDV trong mạng có nhu cầu đảm bảo chất lượng dịch vụ; 2) Ước lượng được chất lượng liên kết ở tầng MAC theo hai thông số là tỉ lệ mất gói tin và độ trễ; 3) Xây dựng được độ đo định tuyến theo độ trễ đầu cuối với giao thức AODV và hàm lượng giá đường theo yêu cầu QoS với giao thức AOMDV; 4) Xây dựng được mô hình và thuật toán định tuyến theo cách tiếp cận xuyên tầng cho hai giao thức; 5) Kiểm nghiệm, đánh giá được hiệu năng của các giao thức sau khi cải tiến là ưu việt hơn so với các giao thức gốc trên phần mềm mô phỏng NS2. Ý nghĩa khoa học và thực tiễn của luận án Các đề xuất cải tiến giao thức định tuyến AODV và AOMDV trong mạng MANET có ý nghĩa khoa học trong lĩnh vực nghiên cứu về mạng MANET nói chung và hướng nghiên cứu về định tuyến nói riêng. Với những kết quả đã đạt được về việc nâng cao hiệu năng định tuyến, các đề xuất này có thể được sử dụng trong các nghiên cứu tiếp theo để cải tiến các giao thức định tuyến khác trong mạng MANET. Về mặt thực tiễn, những kết quả của luận án có thể được sử dụng khi triển khai giao thức định tuyến cho các mạng MANET có tần suất tắc nghẽn cao và cần đảm bảo yêu cầu hỗ trợ QoS cho các chương trình ứng dụng. Bố cục của luận án Luận án được bố cục thành 3 chương. Chương 1 trình bày tổng quan về mạng MANET, các chiến lược định tuyến được sử dụng trong các giao thức định tuyến dành cho mạng MANET, các nghiên cứu cải tiến giao thức định tuyến dùng cho mạng MANET, định tuyến dạng véc tơ khoảng cách, định tuyến đa đường và những nghiên cứu cải tiến. Nội dung chính của chương là cơ chế hoạt động của hai giao thức AODV, AOMDV và các nghiên cứu cải tiến đã đề xuất đối với hai giao thức này; Các 5 lập luận, phân tích để rút ra vấn đề trọng tâm cần cải tiến đối với hai giao thức, xây dựng các luận điểm chính làm cơ sở cho các nghiên cứu toán học và thử nghiệm trong các chương tiếp theo. Chương 2 đề xuất ý tưởng cải tiến giao thức AODV và trình bày về các vấn đề: phương pháp ước lượng độ trễ của liên kết trên cơ sở nguyên lý hoạt động của công nghệ IEEE 802.11; những đề xuất cải tiến giao thức AODV theo mô hình định tuyến xuyên tầng với mô đun đo mức độ sử dụng kênh truyền, mô đun ước lượng tỉ lệ lỗi frame của liên kết và mô đun định tuyến xuyên tầng; kiểm nghiệm và đánh giá kết quả của các cải tiến đã đề xuất bằng phương pháp mô phỏng và đánh giá hiệu năng của hai giao thức AODV-DM và AODV trên phần mềm NS2. Chương 3 trình bày ý tưởng cải tiến cho giao thức AOMDV; đề xuất phương pháp phân lớp các ứng dụng theo yêu cầu chất lượng dịch vụ theo chuẩn ITU-T G1010 và phương pháp tính trọng số cho các tiêu chuẩn QoS; đề xuất kỹ thuật dự đoán chất lượng liên kết tại tầng MAC theo hai tham số là trễ và tỉ lệ mất gói; đề xuất cải tiến giao thức AOMDV theo yêu cầu QoS sử dụng cách tiếp cận xuyên tầng; kiểm nghiệm và đánh giá kết quả của các cải tiến đã đề xuất trên cơ sở mô phỏng và so sánh hiệu năng của hai giao thức QCLR và AOMDV bằng phần mềm NS2. Cuối cùng là phần kết luận, tóm tắt những đóng góp chính, các hướng nghiên cứu phát triển tiếp theo của luận án và những vấn đề được tác giả quan tâm. 6 CHƯƠNG 1. TỔNG QUAN VỀ MẠNG MANET VÀ VẤN ĐỀ ĐỊNH TUYẾN TRONG MẠNG MANET Trong xu thế phát triển của mạng Internet kết nối vạn vật hiện nay, bên cạnh các kết quả nghiên cứu đã tương đối hoàn thiện nhằm phát triển hệ thống mạng lõi, các nghiên cứu phát triển các công nghệ mạng không dây cho phép kết nối các thiết bị thông minh để triển khai nhiều ứng dụng hữu ích phục vụ cho cuộc sống của con người ngày càng được chú trọng. Công nghệ mạng không dây nói chung và mạng MANET nói riêng được ứng dụng ngày càng rộng rãi trong nhiều lĩnh vực như phòng chống thiên tai, thảm họa, hỗ trợ giám sát giao thông, môi trường, sản xuất, phục vụ quốc phòng, an ninh, hỗ trợ các công việc trong lĩnh vực kinh doanh, văn phòng, giáo dục, giải trí … Với đặc điểm là một hệ thống mạng được triển khai mà không cần sự hỗ trợ của hạ tầng mạng cố định, một trong những vấn đề quan trọng ảnh hưởng tới hiệu năng mạng MANET là giao thức định tuyến được sử dụng trong mạng. Vì vậy, định tuyến trong mạng MANET là một vấn đề lớn được quan tâm nghiên cứu ngay từ ngày đầu công nghệ mạng này ra đời và vẫn đang tiếp tục được quan tâm nghiên cứu nhằm cải thiện hiệu năng trong các mô hình mạng MANET cụ thể. Trong chương này, phần thứ nhất sẽ trình bày một cách tổng quan về mạng MANET bao gồm khái niệm, các đặc điểm và giới thiệu một số ứng dụng của mạng MANET. Vấn đề định tuyến mạng MANET được trình bày chi tiết trong phần thứ hai với nội dung tập trung vào một số chiến lược định tuyến trong mạng MANET và một số hướng nghiên cứu cải tiến giao thức định tuyến trong mạng MANET. Phần thứ ba của chương trình bày sâu hơn về đặc điểm và cơ chế hoạt động của lớp các giao thức định tuyến dạng véc tơ khoảng cách, định tuyến đa đường trong mạng MANET mà điển hình là hai giao thức AODV, AOMDV và các nghiên cứu cải tiến đã đề xuất cho hai giao thức này. Phần cuối cùng trình bày về mục tiêu và hướng tiếp cận của luận án. 7 1.1. Giới thiệu về mạng MANET 1.1.1. Khái niệm mạng MANET Một mạng MANET (Mobile Ad hoc Network) [68] là một tập các nút không dây di động có thể trao đổi dữ liệu một cách linh động mà không cần sự hỗ trợ của trạm cơ sở cố định hoặc mạng có dây. Mỗi nút di động có một phạm vi truyền giới hạn, do đó chúng cần sự trợ giúp của các nút lân cận để chuyển tiếp các gói dữ liệu. Hình 1.1 minh họa một ví dụ về một mạng MANET. Trong ví dụ này, các gói tin từ nút nguồn là một máy tính cần chuyển tới một nút đích là một điện thoại thông minh không nằm trong phạm vi truyền của nút nguồn. Vì vậy, cần có sự trợ giúp của các nút trung gian để chuyển tiếp gói tin. Để thực hiện được công việc này, các nút mạng phải sử dụng giao thức định tuyến phù hợp. Hình 1.1. Một ví dụ của mạng MANET Thuật ngữ “Ad hoc” mô tả một mạng không có cơ sở hạ tầng cố định, trong đó hình trạng mạng được tạo thành bởi chính các nút mạng. Chế độ “Ad hoc” của chuẩn IEEE 802.11 [35] hoạt động theo mô hình này, mặc dù nó chỉ hỗ trợ để thiết lập một mạng đơn chặng. Các mạng di động không dây kiểu không cấu trúc (MANET) đã mở rộng khái niệm “Ad hoc” đa chặng [68] theo 8