ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG Nơng Thị Hồng KỸ THUẬT ĐỊNH TUYẾN ĐA ĐƢỜNG TRONG MẠNG KHÔNG DÂY PHI CẤU TRÚC LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2019 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THƠNG TIN VÀ TRUYỀN THƠNG Nơng Thị Hồng KỸ THUẬT ĐỊNH TUYẾN ĐA ĐƢỜNG TRONG MẠNG KHÔNG DÂY PHI CẤU TRÚC Ngành: Khoa học máy tính Mã số: 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC TS NGUYỄN ĐÌNH DŨNG Thái Nguyên - 2019 LỜI CẢM ƠN Sau thời gian học tập nghiên cứu trƣờng Đại học Công nghệ thông tin Truyền thông – Đại học Thái Nguyên, em hoàn thành luận văn tốt nghiệp thạc sĩ ngành Khoa học máy tính Để có đƣợc kết này, em xin bày tỏ kính trọng lịng biết ơn sâu sắc tới: – TS Nguyễn Đình Dũng, Trƣờng ĐH CNTT & TT – ĐHTN: cán hƣớng dẫn khoa học ln tận tình giúp đỡ bảo em suốt trình làm luận văn – Các cán bộ, giảng viên Khoa Công nghệ thơng tin Phịng Đào tạo tồn thể thầy, cô giáo trƣờng Trƣờng Đại học CNTT & TT - ĐHTN tận tình bảo, hƣớng dẫn giúp đỡ em suốt trình em thực đề tài luận văn – Bên cạnh giúp đỡ gia đình, bạn bè ngƣời thân ủng hộ tạo điều kiện tốt để em tập trung nghiên cứu hồn thành luận văn Do mặt kiến thức thời gian hạn chế, luận văn nhiều khiếm khuyết Tơi mong đƣợc đóng góp ý kiến thầy, ngƣời để luận văn hồn thiện Xin trân trọng cảm ơn! Thái Nguyên, ngày … tháng … năm 2019 Học viên Nông Thị Hồng MỤC LỤC MỞ ĐẦU CHƢƠNG MẠNG KHÔNG DÂY DI ĐỘNG PHI CẤU TRÚC VÀ VẤN ĐỀ ĐỊNH TUYẾN 1.1 Tổng quan mạng không dây phi cấu trúc 1.1.1 Khái niệm mạng không dây phi cấu trúc 1.1.2 Đặc điểm mạng không dây phi cấu trúc 1.1.3 Ứng dụng mạng không dây phi cấu trúc 1.2 Một số chiến lƣợc định tuyến mạng không dây phi cấu trúc 1.2.1 Phân loại chiến lƣợc định tuyến 1.2.2 Mô tả chiến lƣợc định tuyến mạng ad hoc 1.3 Giao thức định tuyến theo yêu cầu dạng vectơ khoảng cách AODV 15 1.3.1 Giới thiệu giao thức AODV 15 1.3.2 Cơ chế hoạt động giao thức AODV 16 1.4 Tổng kết Chƣơng 25 CHƢƠNG GIAO THỨC ĐỊNH TUYẾN ĐA ĐƢỜNG AOMDV 28 2.1 Tổng quan giao thức AOMDV 28 2.1.1 Vấn đề chống định tuyến lặp 29 2.1.2 Các đƣờng tách biệt 32 2.2 Hoạt động chi tiết giao thức AOMDV 39 2.2.1 Bảng định tuyến 39 2.2.2 Thuật toán cập nhật đƣờng 40 2.2.3 Tiến trình khám phá đƣờng 42 2.2.4 Cơ chế bảo trì đƣờng 45 2.2.4 Cơ chế chuyển tiếp liệu 46 2.3 Các tính chất giao thức 47 2.3.1 Loại bỏ tính lặp vịng 48 2.3.2 Tính tách biệt đƣờng 49 2.4 Tổng kết Chƣơng 52 CHƢƠNG MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU NĂNG GIAO THỨC AOMDV 54 3.1 Mục tiêu việc đánh giá giao thức AOMDV 54 3.2 Môi trƣờng mô 54 3.3 Các độ đo hiệu 57 3.4 Kết mơ phân tích đánh giá hiệu 57 3.4.1 Thay đổi tốc độ di chuyển 57 3.4.2 Thay đổi số lƣợng kết nối 65 3.4.3 Thay đổi tốc độ liệu 68 3.4.4 Số lƣợng đƣờng 70 3.5 Tổng kết Chƣơng 72 KẾT LUẬN 74 TÀI LIỆU THAM KHẢO 76 MỞ ĐẦU Mạng khơng dây phi cấu trúc đƣợc hình thành kết nối tạm thời nút mạng Đây công nghệ mạng tảng để phát triển công nghệ mạng đƣợc ứng dụng rộng rãi ngày nhƣ mạng cảm biến, mạng giao thông, mạng tác chiến,… Trong mạng không dây phi cấu trúc, nút mạng vừa đóng vai trị thiết bị đầu cuối, vừa đóng vai trị định tuyến Do tính chất di động nút mạng nên tốn định tuyến mạng khơng dây phi cấu trúc có nhiều điểm khác biệt so với tốn định tuyến mạng truyền thống Từ góc nhìn số lƣợng đƣờng định tuyến sử dụng, phân chia giao thức định tuyến mạng không dây phi cấu trúc theo hai nhóm định tuyến đơn đƣờng định tuyến đa đƣờng Đối với giao thức định tuyến đơn đƣờng, có tối đa đƣờng tối ƣu theo độ đo định tuyến chúng đƣợc cài đặt vào bảng định tuyến sau tiến trình tìm đƣờng chúng nhận đƣợc thông tin nhiều đƣờng tới đích tiến trình tìm đƣờng Tại nút mạng, gói tin liệu đƣợc chuyển đƣờng thích hợp có bảng định tuyến Khi liên kết đƣờng bị lỗi, nút mạng phải khởi tạo lại tiến trình tìm đƣờng Để tiết kiệm tài nguyên hệ thống mạng tiến trình tìm đƣờng, giao thức định tuyến đa đƣờng cho phép tìm cài đặt nhiều đƣờng không giao tới đích vào bảng định tuyến chúng Tại nút, có yêu cầu chuyển tiếp liệu tới nút đích, đƣờng tốt đƣợc sử dụng đƣờng cịn lại đóng vai trị đƣờng dự phịng Khi đƣờng bị lỗi, đƣờng dự phòng đƣợc sử dụng để chuyển tiếp gói tin liệu chúng trạng thái cịn hoạt động đƣợc Thêm vào đó, chế cân tải đƣợc sử dụng, phân lƣu lƣợng liệu cần truyền thành nhiều luồng đƣợc truyền song song đƣờng tới đích Mục đích đề tài nghiên cứu chiến lƣợc định tuyến chế hoạt động giao thức định tuyến AODV – giao thức định tuyến đơn đƣờng điển hình mạng khơng dây phi cấu trúc Sau đó, nghiên cứu đề xuất cải tiến giao thức AODV thành giao thức AOMDV với mục tiêu nâng cao hiệu mạng không dây phi cấu trúc Hiệu giao thức định tuyến đơn đƣờng AODV giao thức định tuyến đa đƣờng AOMDV đƣợc so sánh, phân tích đánh giá thơng qua phần mềm mô NS2 với nhiều kịch mô khác Luận văn bao gồm phần đƣợc bố cục nhƣ sau: Phần mở đầu trình bày mục tiêu, ý nghĩa bố cục luận văn Tiếp theo, vấn đề tổng quan mạng không dây phi cấu trúc, vấn đề định tuyến chế hoạt động chi tiết giao thức định tuyến AODV đƣợc trình bày Chƣơng Đề xuất cải tiến thiết kế triển khai giao thức định tuyến đa đƣờng AOMDV đƣợc trình bày Chƣơng Hiệu giao thức đƣợc cải tiến AOMDV đƣợc so sánh, phân tích đánh giá với giao thức gốc AODV Chƣơng thông qua nhiều kịch mô đƣợc thực NS-2 Cuối phần kết luận đƣa tổng kết hƣớng phát triển luận văn CHƢƠNG MẠNG KHÔNG DÂY DI ĐỘNG PHI CẤU TRÚC VÀ VẤN ĐỀ ĐỊNH TUYẾN 1.1 Tổng quan mạng không dây phi cấu trúc 1.1.1 Khái niệm mạng không dây phi cấu trúc Mạng không dây phi cấu trúc (Mobile Ad hoc Network – MANET) [10] mạng di động không dây hoạt động không cần dựa vào hạ tầng mạng cố định, hình trạng mạng đƣợc tạo thành nút mạng Chế độ “Ad hoc” chuẩn IEEE 802.11 hoạt động theo mơ hình này, hỗ trợ để thiết lập mạng đơn chặng Các mạng di động không dây kiểu không cấu trúc mở rộng khái niệm “Ad hoc” đa chặng theo nghĩa: nút mạng định tuyến chuyển tiếp gói tin nhận đƣợc từ nút mạng khác Nói cách khác, đƣờng chuyển tiếp gói tin từ nút nguồn tới nút đích chứa nút trung gian khác Các nút trung gian đọc thông tin phần header gói tin liệu chuyển tiếp chúng tới chặng đƣờng đƣợc hình thành Có thể hiểu mạng khơng dây phi cấu trúc tập nút khơng dây di động trao đổi liệu cách linh động mà không cần hỗ trợ trạm sở cố định mạng có dây Mỗi nút di động có phạm vi truyền giới hạn, chúng cần trợ giúp nút lân cận để chuyển tiếp gói liệu Khi gói tin liệu từ nút nguồn cần gửi tới nút đích mà nút đích khơng nằm phạm vi truyền nút nguồn, cần có trợ giúp nút trung gian để chuyển tiếp gói tin từ nút nguồn tới nút đích Để thực đƣợc cơng việc này, nút mạng phải sử dụng giao thức định tuyến phù hợp Hình 1.1 Minh họa mạng khơng dây phi cấu trúc Hình ví dụ mạng khơng dây phi cấu trúc Trong nút mạng kết nối với khoảng thời gian để trao đổi thông tin Trong trao đổi thơng tin, nút di chuyển, đó, mạng phải đáp ứng đƣợc yêu cầu truyền liệu hình trạng mạng thay đổi liên tục Các nút mạng phải có chế tự tổ chức thành mạng để thiết lập đƣờng truyền liệu mà không cần hỗ trợ từ bên ngồi Trong mơ hình này, nút mạng đóng vai trị nút đầu cuối để chạy chƣơng trình ứng dụng ngƣời sử dụng định tuyến để chuyển tiếp gói tin cho nút mạng khác 1.1.2 Đặc điểm mạng không dây phi cấu trúc Do mạng không dây phi cấu trúc mạng không dây hoạt động không cần hỗ trợ hạ tầng mạng sở sở truyền thông đa chặng thiết bị di động vừa đóng vai trị thiết bị đầu cuối, vừa đóng vai trị định tuyến nên mạng khơng dây phi cấu trúc có số đặc điểm bật sau [3]:  Cấu trúc động: Do tính chất di chuyển ngẫu nhiên nút mạng nên cấu trúc loại mạng thƣờng xuyên thay đổi cách ngẫu nhiên thời điểm không xác định trƣớc Trong thay đổi, cấu trúc mạng khơng dây phi cấu trúc có thêm kết nối hai chiều kết nối chiều  Chất lƣợng liên kết hạn chế: Các liên kết khơng dây thƣờng có băng thơng nhỏ so với liên kết có dây Ngồi ra, ảnh hƣởng chế đa truy cập, vấn đề suy giảm tín hiệu, nhiễu yếu tố khác, băng thơng thực liên kết không dây thƣờng thấp nhiều so với tốc độ truyền tối đa theo lý thuyết môi trƣờng truyền không dây  Các nút mạng có tài nguyên hạn chế: Mỗi nút di động mạng cảm biến, điện thoại thơng minh máy tính xách tay Thơng thƣờng thiết bị có tài ngun hạn chế so với máy tính mạng có dây không dây truyền thống tốc độ xử lý, dung lƣợng nhớ lƣợng nguồn pin nuôi sống hoạt động nút  Độ bảo mật thấp mức độ vật lý: Mạng không dây di động thƣờng chịu tác động mặt vật lý từ nguồn gây nguy hại an ninh nhiều so với mạng có dây Về khía cạnh vật lý, kỹ thuật gây an ninh bảo mật mạng nhƣ nghe lén, giả mạo công từ chối dịch vụ thƣờng dễ triển khai mạng không dây phi cấu trúc mạng có dây truyền thống Có thể thấy đặc điểm yếu tố ảnh hƣởng nhiều đến hiệu mạng khơng dây phi cấu trúc Để triển khai đƣợc mạng không dây phi cấu trúc thực tế, thiết kế mạng phải giải đƣợc 63 AOMDV AODV 1400 Chi phí bảo trì đường (gói/s) Chi phí khám phá đường (gói/s) AODV 1200 1000 800 600 400 200 1,0 2,5 5,0 7,5 10,0 AOMDV 160 150 140 130 120 110 100 1,0 2,5 5,0 7,5 10,0 Tốc độ di chuyển (m/s) Tốc độ di chuyển (m/s) (d) Chi phí bảo trì đƣờng (c) Chi phí khám phá đƣờng Hình 3.3 Biểu đồ Chi phí định tuyến thay đổi Tốc độ di chuyển Mặc dù chi phí định tuyến cho lần khám phá đƣờng cho cao chút nhƣng tổng chi phí định tuyến khám phá đƣờng chi phí định tuyến tổng thể giao thức AOMDV lại thấp nhiều (ít 30%) so với giao thức AODV (Bảng 3.4 Hình 3.3) Cần lƣu ý chi phí định tuyến khám phá đƣờng chiếm tỷ trọng lớn chi phí định tuyến tổng thể chi phí định tuyến bảo trì đƣờng gồm thơng điệp RERR HELLO lại chiếm tỷ trọng nhỏ Chi phí định tuyến (gói/s) Chi phí khám phá đƣờng (gói/s) AODV AOMDV AODV AOMDV AODV AOMDV 1.0 622.6 429.1 518.2 317.9 119.0 114.0 2.5 800.2 522.9 691.7 409.4 125.1 118.6 5.0 1120.4 701.5 1004.8 580.0 139.6 131.8 7.5 1217.9 782.2 1100.1 658.3 147.7 138.0 10.0 1287.7 874.8 1164.8 744.1 152.1 145.1 Tốc độ di chuyển (m/s) Chi phí bảo trì đƣờng (gói/s) Bảng 3.4 Giá trị tham số Chi phí định tuyến theo Tốc độ di chuyển 64 Tốc độ di chuyển (m/s) Chi phí định tuyến (Kbyte/s) AODV AOMDV 1.0 26.95 19.76 2.5 34.59 24.25 5.0 48.50 32.65 7.5 52.70 36.55 10.0 55.62 40.85 Bảng 3.5 Giá trị tổng chi phí định tuyến thay đổi tốc độ di chuyển Bảng 3.5 Hình 3.4 cho thấy tổng chi phí định tuyến tính theo đơn vị kbs Cải thiện định tuyến tổng thể tính theo đơn vị byte giao thức AOMDV thấp chút so với cách tính theo đơn vị gói tin nhƣng cao đáng kể (hơn 25%) so với giao thức AODV Hiệu chi phí định tuyến theo byte thấp so với chi phí định tuyến theo gói tin gói tin định tuyến giao thức AOMDV lớn so với gói tin định tuyến giao thức AODV gói RREQ RREP giao thức AOMDV đƣợc bổ sung thêm số trƣờng, chẳng hạn nhƣ ID chặng cuối 65 AODV AOMDV Chi phí định tuyến (kbyte/s) 60 50 40 30 20 10 1,0 2,5 5,0 7,5 10,0 Tốc độ di chuyển (m/s) Hình 3.4 Biểu đồ tổng chi phí định tuyến thay đổi tốc độ di chuyển 3.4.2 Thay đổi số lượng kết nối Trong thử nghiệm tiếp theo, số lƣợng kết nối CBR / UDP đƣợc thay đổi, tốc độ di chuyển trung bình nút mạng đƣợc thiết lập mức m/s tải liệu đƣợc thiết lập mức 200 kbs Khi cố định tỷ lệ lỗi liên kết (vì tốc độ di chuyển trung bình khơng đổi) tải liệu, kết nối truyền lƣu lƣợng liệu Khi đó, giao thức định tuyến cần trì nhiều tuyến đƣờng truyền liệu cặp nguồn-đích Điều thử nghiệm độ mạnh giao thức vấn đề phân phối liệu Hơn nữa, việc khám phá đƣờng trở nên khó khăn thơng lƣợng cần thiết để phục vụ cho việc truyền liệu toàn mạng tăng lên Số lƣợng kết nối Tỉ lệ gói (%) Tần suất khám phá đƣờng (lần/s) AODV AOMDV AODV AOMDV 3.64 3.10 0.12 0.08 66 20 2.15 1.74 1.23 0.78 30 3.82 3.18 2.64 1.63 40 6.08 5.18 4.36 2.72 50 9.45 6.87 6.53 3.69 60 16.41 9.84 9.42 5.07 70 29.31 18.55 12.77 7.36 Bảng 3.6 Tỉ lệ gói Tần suất khám phá đường theo Số lượng kết nối Số lƣợng kết nối Trễ truyền gói trung bình (ms) Trễ khám phá đƣờng trung bình (ms) AODV AOMDV AODV AOMDV 13.67 10.03 110.62 102.36 10 33.79 28.15 225.06 189.64 20 41.16 29.83 383.33 293.44 30 70.43 45.05 572.36 426.04 40 122.52 62.46 813.08 543.38 50 257.44 103.58 1140.46 711.57 60 567.32 306.12 1511.55 988.59 Bảng 3.7 Tỉ lệ gói Tần suất khám phá đường theo Số lượng kết nối Số liệu giá trị trung bình độ đo hiệu sau 10 lần chạy mô biểu đồ tƣơng quan thay đổi giá trị độ đo hiệu theo số lƣợng kết nối liệu đƣợc biểu diễn Bảng 3.6 - 3.7 Hình 3.5 67 AOMDV AODV Tỉ lệ gói (%) 30 25 20 15 10 10 20 30 40 50 60 Tần suất khám phá đường (lần/s) AODV 14 12 10 10 20 AODV Chi phí định tuyến (gói/s) Trễ truyền gói trung bình (ms) AOMDV 600 500 400 300 200 100 10 20 30 40 40 50 60 (b) Tần suất khám phá đƣờng (a) Tỉ lệ gói 30 Số lượng kết nối Số lượng kết nối AODV AOMDV 50 Số lượng kết nối (c) Trễ truyền gói trung bình 60 AOMDV 1600 1400 1200 1000 800 600 400 200 10 20 30 40 50 60 Số lượng kết nối (d) Trễ khám phá đƣờng trung bình Hình 3.5 Biểu đồ hiệu mạng theo số lượng kết nối Hiệu hai giao thức giảm mạnh số lƣợng kết nối tăng lên Khi số lƣợng kết nối nhỏ, khác biệt hiệu giao thức AODV giao thức AOMDV không đáng kể Tuy nhiên, số lƣợng kết nối tăng lên, giao thức AOMDV có hiệu đạt đƣợc tốt hẳn so với giao thức AODV Điều cho thấy giao thức AOMDV có khả xử lý tốt việc định tuyến với số lƣợng lớn kết nối nhờ chế tìm kiếm đa đƣờng 68 3.4.3 Thay đổi tốc độ liệu Các thử nghiệm đƣợc thực để nghiên cứu ảnh hƣởng tốc độ liệu (và tải đƣợc cung cấp) đến hiệu tƣơng đối giao thức AODV AOMDV Trong thử nghiệm này, tốc độ di chuyển trung bình nút mạng số lƣợng kết nối liệu đƣợc thiết lập giá trị tƣơng ứng mức m/s 50 kết nối Tốc độ tạo gói liệu kết nối đƣợc thay đổi khoảng từ 0,25 đến 1,25 gói giây Giá trị tham số hiệu giá trị trung bình đƣợc tính tốn từ 10 lần chạy mô với topo mạng sinh ngẫu nhiên Bảng 3.8 – 3.9 tổng hợp giá trị hiệu Hình 3.6 đƣa biểu đồ tƣơng quan thay đổi giá trị hiệu so với tốc độ sinh liệu Tần suất khám phá đƣờng (lần/s) Tốc độ sinh liệu (gói/s) AODV AOMDV AODV AOMDV 0.1 7.96 7.34 6.16 4.59 0.5 9.32 8.30 4.65 3.19 0.8 9.19 7.71 6.24 3.82 1.0 16.73 9.96 9.60 5.13 1.25 37.84 29.68 13.25 8.50 Tỉ lệ gói (%) Bảng 3.8 Tỉ lệ gói Tần suất khám phá đường theo Tốc độ sinh liệu Tốc độ sinh liệu (gói/s) Trễ truyền gói trung bình (ms) AODV AOMDV Trễ khám phá đƣờng trung bình (ms) AODV AOMDV 69 0.1 83.91 59.15 772.05 641.96 0.5 49.90 35.66 609.45 483.26 0.8 81.43 47.88 779.27 557.97 1.0 257.17 104.51 1141.34 713.21 1.25 790.64 609.58 1532.92 1101.64 Bảng 3.9 Tỉ lệ gói Tần suất khám phá đường theo Tốc độ sinh liệu Kết cho thấy hiệu hai giao thức thay đổi tốc độ sinh gói liệu Cả hai giao thức bị giảm hiệu tốc độ tạo gói tăng hiệu giao thức AOMDV luôn tốt so với giao thức AODV Với tốc độ tạo gói thấp, gần nhƣ cần đƣờng cho hầu hết gói liệu đƣợc tạo đƣờng đƣợc phát trƣớc có khả bị phá vỡ vào thời điểm nút nguồn sinh gói liệu Điều đƣợc thể rõ tốc độ tạo gói thấp 0,25 gói/s, số lần khám phá đƣờng chi phí định tuyến cao Có thể thấy rằng, giao thức AOMDV không đạt hiệu tốt tình nhƣ khơng có đủ số lƣợng gói tin để tận dụng đƣờng dẫn dự phịng trƣớc chúng bị phá vỡ Vì vậy, tốc độ sinh gói tăng dần, hiệu giao thức AOMDV đạt đƣợc tốt (từ 0,75 đến gói/s) Với tốc độ sinh gói liệu cao, hiệu tƣơng đối giao thức AOMDV giảm xuống khơng có chế để giảm thiểu tắc nghẽn tải liệu mức độ cao 70 AOMDV AODV 40 35 30 25 20 15 10 0,10 0,50 0,75 1,00 1,25 Tốc độ sinh liệu (gói/s) Tần suất khám phá đường (lần/s) Tỉ lệ gói (%) AODV 0,75 0,50 0,75 1,00 1,25 Tốc độ sinh liệu (gói/s) AODV Chi phí định tuyến (gói/s) Trễ truyền gói trung bình (ms) 0,50 0,10 AOMDV 800 700 600 500 400 300 200 100 0,10 14 12 10 (b) Tần suất khám phá đƣờng (a) Tỉ lệ gói AODV AOMDV 1,00 1,25 Tốc độ sinh liệu (gói/s) (c) Trễ truyền gói trung bình AOMDV 1600 1400 1200 1000 800 600 400 0,10 0,50 0,75 1,00 1,25 Tốc độ sinh liệu (gói/s) (d) Trễ khám phá đƣờng trung bình Hình 3.6 Biểu đồ hiệu mạng theo tốc độ sinh liệu 3.4.4 Số lượng đường Thực nghiệm mô để nghiên cứu số lƣợng đƣờng dự phịng trung bình mà giao thức AOMDV tìm thấy đƣợc thực với kết đƣợc thể Bảng 3.10 Hình 3.7 Theo đó, số lƣợng trung bình đƣờng tách biệt theo liên kết nút đƣợc xem xét nhƣ hàm độ dài đƣờng ngắn nguồn đích Đây kết kịch mơ gồm có 50 kết nối CBR/UDP với tốc độ gói/s kết nối tốc độ di chuyển trung bình nút mạng m/s 71 Số lƣợng đƣờng tách biệt trung bình Độ dài đƣờng ngắn (số chặng) AODV AOMDV 5.04 4.75 2.88 1.94 2.10 1.40 1.48 1.18 1.17 1.11 Bảng 3.10 Số lượng đường tách biệt trung bình theo Độ dài đường ngắn AODV AOMDV Số lượng đường tách biệt trung bình 5,5 5,0 4,5 4,0 3,5 3,0 2,5 2,0 1,5 1,0 Độ dài đường ngắn (số chặng) Hình 3.7 Số lượng đường tách biệt Kết cho thấy cách rõ ràng giao thức AOMDV tìm đƣợc số đƣờng tách biệt theo liên kết nhiều số đƣờng tách biệt theo nút Tuy nhiên, số lƣợng đƣờng tìm thấy bị sụt giảm độ dài đƣờng ngắn tăng lên Điều vấn đề “cắt tuyến” đề cập trƣớc Mối quan hệ khơng 72 làm giảm đáng kể hiệu giao thức AOMDV mạng di động Khi đƣờng có độ dài tăng lên, khả đƣờng bị phá vỡ chuyển động nút tăng lên Điều tƣơng tự xảy đƣờng dự phịng Do đó, mức độ hiệu đƣờng dự phòng giảm độ dài đƣờng tăng lên Đây kết luận đƣợc rút từ nghiên cứu định tuyến đa đƣờng theo yêu cầu [8] Tuy nhiên, việc giảm số lƣợng đƣờng dẫn với tách biệt nguồn đích đƣợc tăng lên mối quan tâm định tuyến đa đƣờng đƣợc sử dụng cho mục đích khác nhƣ cân tải 3.5 Tổng kết Chƣơng Để thấy rõ đƣợc mức độ hiệu giao thức AOMDV với thiết kế đƣợc trình bày Chƣơng 2, kịch mơ khác đƣợc thiết kế Chƣơng nhằm so sánh đánh giá hiệu giao thức AOMDV so với giao thức AODV Hiệu hai giao thức đƣợc đánh giá chƣơng theo độ đo hiệu bao gồm: tỷ lệ gói tin, trễ đầu cuối, tần suất khám phá đƣờng chi phí định tuyến sở kịch gồm: thay đổi tốc độ di chuyển nút mạng, thay đổi số lƣợng nút mạng thay đổi số lƣợng kết nối thay đổi tốc độ phát liệu Khi phân tích hiệu theo biến đổi tốc độ di chuyển nút mạng, giao thức AOMDV đạt đƣợc hiệu tốt so với giao thức AODV mạng có nút mạng di chuyển với tốc độ cao Điều đƣợc thể tỷ lệ gói tin tần suất khám phá đƣờng nhỏ xấp xỉ 40%, trễ đầu cuối giảm khoảng từ 30%-50%, chi phí định tuyến tổng thể giảm xấp xỉ 30% 73 Khi thay đổi số lƣợng kết nối, hiệu hai giao thức giảm số lƣợng kết nối tăng lên nhƣng giao thức AOMDV đạt đƣợc hiệu tốt so với giao thức AODV Sự chênh lệch hiệu hai giao thức rõ số lƣợng kết nối tăng Trong mơ để phân tích hiệu hai giao thức theo tốc độ tạo gói liệu từ nút nguồn, giao thức AOMDV đạt đƣợc hiệu tổng thể tốt so với giao thức AODV Đối với tải liệu thấp, khác biệt hiệu hai giao thức không lớn Hiệu giao thức AOMDV có xu hƣớng đạt cao tải liệu nằm khoảng từ 0,75 đến gói/s kết nối số 50 kết nối liệu hoạt động đồng thời tốc độ di chuyển trung bình nút mạng m/s Khi lƣu lƣợng liệu có tốc độ phát đƣợc đẩy lên cao, khác biệt hiệu hai giao thức thể rõ ràng Thử nghiệm cuối đƣợc thực mô để so sánh số lƣợng đƣờng tách biệt theo nút với số lƣợng đƣờng tách biệt theo liên kết mà giao thức AOMDV tìm đƣợc theo độ dài đƣờng ngắn Kết cho thấy cách rõ ràng giao thức AOMDV tìm đƣợc số đƣờng tách biệt theo liên kết nhiều số đƣờng tách biệt theo nút Tuy nhiên, số lƣợng đƣờng tìm thấy bị sụt giảm độ dài đƣờng ngắn tăng lên Tóm lại, kết luận rằng, xét mặt tổng thể, giao thức AOMDV đạt đƣợc hiệu tốt giao thức AODV áp dụng mạng không dây di động phi cấu trúc 74 KẾT LUẬN Các giao thức định tuyến đa đƣờng theo yêu cầu xử lý hiệu lỗi đƣờng gây vấn đề di động mạng không dây di động phi cấu trúc so sánh với phiên giao thức đơn đƣờng tƣớng ứng chúng Nội dung luận văn trình bày tổng quan mạng không dây di động phi cấu trúc, vấn đề định tuyến mạng không dây phi cấu trúc hoạt động chi tiết giao thức định tuyến điển hình mạng giao thức AODV Trên sở nghiên cứu đề xuất cải tiến giao thức AODV, luận văn trình bày chi tiết kỹ thuật định tuyến đa đƣờng đƣợc thiết kế triển khai giao thức định tuyến đa đƣờng theo yêu cầu có tên AOMDV Đây giao thức đƣợc cải tiến từ giao thức AODV đơn đƣờng nhằm mục đích tìm nhiều đƣờng hiệu Giao thức AOMDV đảm bảo tìm đƣợc tập hợp nhiều đƣờng khơng lặp vòng tách biệt theo liên kết theo nút Các tính khác giao thức AOMDV bao gồm: chi phí điều khiển tƣơng tác nút thấp, khả khám phá đƣờng dẫn tách biệt mà không cần sử dụng chế định tuyến nguồn, chi phí bổ sung tải điều khiển tối thiểu so với giao thức AODV để có đƣợc đƣờng dự phòng Hiệu giao thức AOMDV giao thức AODV đƣợc phân tích đánh giá thơng qua kết mô phần mềm mô NS-2 kịch khác thay đổi tốc độ di chuyển nút mạng lƣu lƣợng liệu Kết hiệu đạt đƣợc giao thức AOMDV khả quan so với giao thức AODV giúp giao thức đa đƣờng đƣợc đề xuất giúp làm giảm độ gói liêu lên tới 40% giảm đáng kể độ trễ (giảm lớn ½) Giao thức cải thiện khoảng 30% chi phí định tuyến cách giảm tần suất khám phá đƣờng Mặc dù công việc đề xuất đƣợc đƣa chƣơng chủ yếu tập trung vào việc phát triển mở rộng tính 75 đa đƣờng cho giao thức AODV nhƣng số ý tƣởng đƣợc đề xuất dễ dàng áp dụng cho giao thức định tuyến khác mạng ad hoc Chẳng hạn, dễ dàng sửa đổi giao thức DSDV để trì nhiều đƣờng khơng lặp vòng cách sử dụng khái niệm khái niệm “số chặng đƣợc quảng bá” Tuy nhiên cần thấy rằng, có số vấn đề bổ sung liên quan đến thiết kế đánh giá giao thức AOMDV nên đƣợc nghiên cứu cách kỹ lƣỡng Thứ nhất, giao thức đƣợc cải tiến để giải vấn đề cắt tuyến tìm đƣợc nhiều đƣờng tách biệt cặp nguồn-đích cách xa Thứ hai, cần nghiên cứu sâu ảnh hƣởng việc thiết lập giá trị thời gian timeout đến hiệu giao thức AOMDV Thứ ba, việc áp dụng giao thức AOMDV cho mục đích khác nhƣ cân tải hƣớng nghiên cứu cần xem xét Cuối cùng, đánh giá, so sánh giao thức AOMDV với giao thức AODV đƣợc thực sở sử dụng mơ hình điểm di động ngẫu nhiêu lƣu lƣợng CBR/UDP Cần đánh giá cách tổng quát giao thức AOMDV sử dụng mơ hình di động khác nhƣ với loại lƣu lƣợng khác nhƣ TCP Ngoài việc so sánh đánh giá hiệu giao thức AOMDV với giao thức đa đƣờng khác cần đƣợc thực 76 TÀI LIỆU THAM KHẢO Tiếng Anh [1] Biradar R., Patil V (2006), “Classification and Comparison of routing Techniques in Wireless Ad-hoc Networks”, Proceedings of International Symposium on Ad-hoc Ubiquitous Computing (ISHUC‟06), pp 7-12 [2] Broch J, Maltz D, Johnson D, Hu Y-C, Jetcheva J (1998), Aperformance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of IEEE/ACM MobiCom [3] Corson S., Macker J (1999), “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations”, RFC 2501, Available at: https://tools.ietf.org/html/rfc2501 [4] Fall K, Varadhan K (2002) The http://www.isi.edu/nsnam/ns/ns-documentation.html ns Manual, [5] IEEE Std 802.11 (1999), Wireless LAN medium access control (MAC) and physical layer (PHY) specifications [6] Jain N (2001), Multichannel CSMA protocols for ad hoc net- works, Master‟s thesis, University of Cincinnati, http://www.ohiolink.edu/etd/view.cgi?ucin995471534 [7] Marinal M., Das S (2006), “Ad hoc on-demand multipath distance vector routing”, Wireless Communications and Mobile Computing, (1), pp 96988 [8] Nasipuri A, Castaneda R, Das SR (2001), Performance of multipath routing for on-demand protocols in mobile ad hoc networks ACM/Kluwer Mobile Networks and Applications (MONET), 6(4): 339–349 [9] Pearlman MR, Haas ZJ, Sholander P, Tabrizi SS (2000), On the impact of alternate path routing for load balancing in mobile ad hoc networks, In Proceedings of ACM MobiHoc, 2000 [10] Perkins C (2001), Ad Hoc Networking, Addison-Wesley, USA [11] Perkins C., Belding-Royer E., Das S (2003), “Ad hoc On-Demand Distance Vector (AODV) Routing”, RFC 3561, Available at: https://www.ietf.org/rfc-/rfc3561.txt 77 [12] Perkins CE, Royer EM, Das SR, Marina MK (2001), Performance comparison of two on-demand routing protocols for ad hoc networks IEEE Personal Communications 2001; 8(1): 16–28 [13] Roy S, Saha D, Bandyopadhyay S, Ueda T, Tanaka S (2003), A networkaware MAC and routing protocol for effective load balancing in ad hoc wireless networks with directional antenna In Proceedings of ACM MobiHoc [14] Tsirigos A, Haas ZJ (2001), Multipath routing in the presence of frequent topological changes IEEE Communications Magazine; 39(11): 132–138 ... văn 3 CHƢƠNG MẠNG KHÔNG DÂY DI ĐỘNG PHI CẤU TRÚC VÀ VẤN ĐỀ ĐỊNH TUYẾN 1.1 Tổng quan mạng không dây phi cấu trúc 1.1.1 Khái niệm mạng không dây phi cấu trúc Mạng không dây phi cấu trúc (Mobile... CHƢƠNG MẠNG KHÔNG DÂY DI ĐỘNG PHI CẤU TRÚC VÀ VẤN ĐỀ ĐỊNH TUYẾN 1.1 Tổng quan mạng không dây phi cấu trúc 1.1.1 Khái niệm mạng không dây phi cấu trúc 1.1.2 Đặc điểm mạng không. .. điểm mạng không dây phi cấu trúc 1.1.3 Ứng dụng mạng không dây phi cấu trúc 1.2 Một số chiến lƣợc định tuyến mạng không dây phi cấu trúc 1.2.1 Phân loại chiến lƣợc định tuyến 1.2.2