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 Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2017 Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ Viện Hàn lâm Khoa học và Công nghệ Việt Nam Người hướng dẫn khoa học 1: PGS.TS. Nguyễn Văn Tam Người hướng dẫn khoa học 2: PGS. TS. Nguyễn Gia Hiểu Phản biện 1: PGS. TS. Lương Thế Dũng Phản biện 2: PGS. TS. Ngô Quỳnh Thu Phản biện 3: TS. Nguyễn Hoài Sơn Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi … giờ ..’, ngày … tháng … năm 2017 Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam 1 MỞ ĐẦU Sự khác biệt về tính chất, đặc điểm của mạng MANET so với các mạng truyền thống làm nảy sinh nhiều thách thức và các hướng nghiên cứu khác nhau. Trong các hướng nghiên cứu này, vấn đề định tuyến đã và đang là một vấn đề rất cần được quan tâm giải quyết. Đã 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 theo nhiều hướng khác nhau. 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 chiến lược định tuyến nhất định. Các đánh giá về hiệu năng của các giao thức đã cải tiến thường được giới hạn trong các điều kiện cụ thể. 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 đã công bố của các tác giả Anurag K. (2004), Bertsekas D. (1996), Pham P. (2003) và Tsirigos A. (2001) đã chỉ ra rằng thuật toán này không phải là thuật toán tìm đường tối ưu cho mạng MANET vì chúng gây ra hiện tượng phân phối tải lưu lượng không đều trong mạng dẫn đến các vùng tắc nghẽn cục bộ. 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 sự tập trung lưu lượng tại vùng trung tâm của mạng. AODV là một trong các giao thức định tuyến tiêu biểu sử dụng chiến lược định tuyến theo yêu cầu dạng vec tơ khoảng cách. Đã có nhiều đề xuất cải tiến giao thức AODV. 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 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. Đố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 với yêu cầu QoS của dữ liệu. 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ó thể truyền theo các con đường khác nhau. 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. AOMDV là một giao thức định tuyến đa đường điển hình của mạng MANET. Trong thời gian qua, đã có nhiều đề xuất cải tiến giao thức này. Tuy nhiên, 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 vẫn chưa được giải quyết. 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 2 thức định tuyến AOMDV nhằm hỗ trợ khả năng định tuyến QoS cho mạng MANET. Đối tượng, phạm vi và mục tiêu 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 phạm vi 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 cho giao thức định tuyến AODV trong mạng MANET 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 trên 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. Các kết quả cần đạt được của luận án 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ó yêu 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 các kết quả cải tiến 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 có ý nghĩa khoa học trong hướng nghiên cứu về vấn đề định tuyến trong mạng MANET. Với những kết quả đã đạt được về việc nâng cao hiệu năng định 3 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 tính năng hỗ trợ yêu cầu QoS từ 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. Trong đó, tập trung vào trình bày 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. Thông qua các 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 hoạt động định tuyến xuyên tầng với hoạt động chi tiết của 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 trên cơ sở mô phỏng và so sánh hiệu năng của hai giao thức AODV-DM và AODV bằng 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 QoS của chuẩn ITU-T G1010 và phương pháp tính trọng số cho các tiêu chuẩn chất lượng dịch vụ, đề 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 hướng khai thác thông tin định tuyến xuyên tầng và yêu cầu QoS, kiểm nghiệm và đánh giá kết quả của các cải tiến đã đề xuất bằng 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. 4 CHƯƠNG 1. TỔNG QUAN VỀ MẠNG MANET VÀ VẤN ĐỀ ĐỊNH TUYẾN TRONG MẠNG MANET Mạng MANET có những khác biệt rõ ràng so với mạng không dây truyền thống và đã có nhiều ứng dụng trong đời sống, kinh tế, xã hội của con người. Giao thức định tuyến trong mạng MANET cần đảm bảo được những yêu cầu về tối thiếu hoá tải điều khiển và tải xử lý, hỗ trợ định tuyến đa chặng, đáp ứng những thay đổi về topo mạng và ngăn chặn định tuyến lặp. Đã 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. 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 chiến lược định tuyến nhất định. 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. AODV là giao thức định tuyến theo yêu cầu. Các luồng dữ liệu được định tuyến bởi AODV có xu hướng đi qua tâm của mạng. Vì vậy, có thể xảy ra hiện tượng tắc nghẽn tại trung tâm mạng. Đã có nhiều đề xuất cải tiến giao thức AODV. Tuy nhiên, vẫn chưa có các đề xuất để lấy thông tin về độ trễ của liên kết được ước lượng theo khái niệm “thời gian phục vụ” của CSMA/CA theo cách tiếp cận xuyên tầng làm cơ sở cho cơ chế định tuyến hướng tới mục tiêu giảm tắc nghẽn trong mạng MANET. AOMDV là giao thức định tuyến đa đường được phát triển từ giao thức AODV. Đã có những đề xuất cải tiến giao thức AOMDV theo cách tiếp cận xuyên tầng nhằm hỗ trợ yêu cầu QoS của dữ liệu. Tuy nhiên, trong những cải tiến này, việc phân lớp các lưu lượng dữ liệu của tầng Ứng dụng theo yêu cầu QoS của chuẩn ITU-T G.1010 vẫn chưa được thực hiện. Điều này dẫn đến mức độ hỗ trợ của thuật toán định tuyến theo yêu cầu QoS chưa thực sự hiệu quả. Với những lý do trên, những nội dung nghiên cứu tiếp theo của luận án được xác định là: (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 và (2) Cải tiến giao thức định tuyến AOMDV nhằm hỗ trợ cơ chế định tuyến theo chất lượng dịch vụ cho mạng MANET. Một phần nội dung của chương này được công bố trong công trình [A1]. 5 CHƯƠNG 2. CẢI TIẾN GIAO THỨC AODV NHẰM GIẢM TẮC NGHẼN TRONG MẠNG MANET 2.1. Đề xuất ý tưởng cải tiến cho giao thức AODV Để xác định được độ trễ của một con đường đầu cuối, kỹ thuật ước lượng trễ dịch vụ của liên kết trên cơ sở nguyên lý hoạt động của cơ chế DCF tại tầng MAC sử dụng công nghệ IEEE 802.11 được đề xuất. Giá trị trễ này được truyền ngược lên tầng Mạng để tính trễ đầu-cuối của các con đường tìm được. Giao thức AODV-DM được cải tiến từ giao thức AODV sử dụng độ đo định tuyến là trễ đầu-cuối của đường nhằm tìm đường tránh khỏi các vùng mạng bị tắc nghẽn. 2.2. Phương pháp ước lượng trễ của liên kết Thời gian trễ để truyền thành công một frame qua một liên kết là thời gian phục vụ của nút nguồn của liên kết khi nút này muốn truyền một frame qua liên kết. Nó được định nghĩa là thời gian cần thiết để truyền thành công một frame hoặc huỷ bỏ frame khi số lần truyền lại vượt quá ngưỡng cho phép tại tầng MAC hoạt động theo cơ chế DCF. Gọi Ts, Td, Tb, và Tt tương ứng là thời gian phục vụ, thời gian tạm dừng, thời gian back-off và thời gian truyền của tiến trình truyền một frame qua một liên kết, giá trị của Ts được xác định theo (4) !" = !$ + !& + !' (4) Thời gian truyền được ước lượng theo (10); !' = 1 +," )" !ℎ./0 (10) Trong đó, Thrue là thông lượng hiệu dụng của liên kết. Awerbuch (2006) đã công bố kết quả tính giá trị này cho từng tốc độ hoạt động của công nghệ IEEE ở tầng MAC theo Bảng 2.1 Bảng 2.1. Thông lượng hiệu dụng của liên kết 802.11b Tốc độ hoạt động của liên kết (Mbps) 1.0 2.0 5.5 11.0 Thông lượng hiệu dụng (Mbps) Không Có RTS/CTS RTS/CTS 0.89 0.94 1.64 1.8 3.52 4.34 5.17 7.15 Thời gian back-off được ước lượng theo (13); 6 34567 !& = !"12' 2 2(1 − +" ) 1 − 2+" 7 −1 2 1 − +" − 1 1 − +" 7 (13) với CWmin là giá trị cửa sổ xung đột ban đầu, Fs là xác suất truyền hỏng frame, n là số trạng thái back-off. Gọi CNU là tỷ lệ sử dụng kênh truyền được đo tại nút phát của liên kết. Mối quan hệ giữa Td với Tb và Tt được biểu diễn bởi (16) !$ = 3<= ! + !' 1 − 3<= & (16) Từ (4), (10), (13) và (16) ta có (18) để ước lượng thời gian phục vụ; 2(1 − +" ) 1 − 2+" 7 −1 2(1 − +" ) − 1 1 − +" 7 +," 1 + !ℎ./0 (1 − +" ) 1 − 3<= 34567 !" = !"12' 2 (18) 2.3. Cải tiến giao thức AODV 2.3.1. Đề xuất mô hình định tuyến theo hướng tiếp cận xuyên tầng Giao thức AODV được cải tiến thành giao thức AODV-DM với cơ chế định tuyến theo hướng tiếp cận xuyên tầng minh họa trong Hình 2.6. Hình 2.6. Các mô đun của giao thức AODV-DM 2.3.2. Mô đun đo mức độ sử dụng kênh truyền Thuật toán 2.1 được sử dụng để tính ước lượng giá trị mức độ sử dụng kênh tryền (CNU) tại một nút mạng. 7 Thuật toán 2.1. Ước lượng CNU của kênh truyền tại một nút mạng tại tầng MAC Đầu vào: Chu kỳ ước lượng CNU, chu kỳ cảm nhận kênh truyền Đầu ra: Giá trị CNU của kênh truyền Hoạt động của thuật toán: Bước 1: Gửi frame tại tầng MAC Kiểm tra địa chỉ nút gửi frame có thuộc trường PNS hay không. Nếu có thì chèn địa chỉ này vào đầu trường PNS. Bước 2: Nhận frame tại tầng MAC Bước 2.1: Kiểm tra địa chỉ nút hiện tại có bằng địa chỉ đích của frame nhận được hay không. Nếu có thì chuyển sang Bước 2.2. Nếu không có thì chuyển sang Bước 2.3. Bước 2.2: Cập nhật danh sách SNS của nút hiện tại. Duyệt qua từng địa chỉ trong trường PNS. Nếu địa chỉ đang duyệt chưa có trong danh sách SNS của nút thì bổ sung vào danh sách SNS. Bước 2.3: Cập nhật giá trị biến belong_flow Thiết lập biến belong_flow = true nếu địa chỉ nút hiện tại thuộc trường PNS của frame hoặc địa chỉ nguồn của frame thuộc danh sách SNS của nút. Bước 2.4: Thiết lập biến belong_flow = false tại cuối thủ tục nhận frame. Bước 3: Cập nhật bộ đếm busy_counter sau mỗi chu kỳ cảm nhận kênh truyền Bước 3.1: Cập nhật bộ đếm kênh truyền bận nếu biến belong_flow bằng false và kênh truyền hiện tại đang ở trạng thái bận busy_counter = busy_counter + 1 Bước 3.2: Cập nhật bộ đếm số lần cảm nhận: total_counter = total_counter + 1 Bước 4: Cập nhật giá trị CNU sau mỗi chu kỳ ước lượng CNU CNU = busy_counter / total_counter; Gửi gói Link_Quality chứa giá trị CNU lên tầng Routing; busy_counter = 0; total_counter = 0; 2.3.3. Mô đun ước lượng tỷ lệ lỗi frame của liên kết Phương pháp “đếm số lần truyền kỳ vọng” (ETX) do Couto D. (2003) đề xuất được sử dụng để ước lượng giá trị FER của liên kết: +>? = 1 − @A ∙ @C (19) Trong đó, df và dr là tỷ lệ truyền gói thành công theo mỗi chiều. Trong một chu kỳ gửi n gói mẫu, mỗi nút thuộc liên kết nhận được i và j gói mẫu. FER có thể được ước lượng theo (20); 8 +>? = 1 − (D/F) ∙ (G/F) (20) Giao thức AODV-DM sử dụng thêm gói FER_PROBE (Hình 2.7) để tính FER của liên kết và mang thông tin về giá trị CNU của liên kết đã đo được ở tầng MAC từ nút gửi tới nút nhận của liên kết. Hình 2.7. Cấu trúc gói tin FER_PROBE Thuật toán 2.2 minh họa phương pháp sử dụng gói FER_PROBE để tính và cập nhật các giá trị FER, CNU và thời gian phục vụ của liên kết. Thuật toán 2.2. Cập nhật trễ thời gian phục vụ của liên kết Đầu vào: Chu kỳ gửi gói FER_PROBE Đầu ra: Thời gian phục vụ của liên kết Hoạt động của thuật toán: Bước 1: Gửi gói FER_PROBE khi thời gian hiện tại > thời gian gửi gói + chu kỳ gửi gói Bước 1.1: Cập nhật chu kỳ ước lượng FER: WND_ID += 1. Bước 1.2: Duyệt danh sách các các entry trong bảng Neighbor Table. Với mỗi entry, thêm một phần tử mới vào trường links của gói FER_PROBE (nb_ID = nb_ID của entry; n_recv = r_last_recv của entry). Bước 1.3: Thiết lập trường nNB của FER_PROBE = số entry trong bảng Neighbor_Table của nút hiện tại. Bước 1.4: Thiết lập trường CNU của FER_PROBE = CNU của nút gửi FER_PROBE. Bước 1.5: Cập nhật thời gian gửi gói = Thời gian hiện tại. Bước 2: Nhận và xử lý gói FER_PROBE Bước 2.1: Tìm entry trong bảng Neighbor Table có nb_ID = địa chỉ IP nút gửi gói FER_PROBE. - Nếu không tìm thấy thì thêm một entry mới vào bảng Neighbor Table với (Neighbor ID = địa chỉ IP nút gửi gói FER_PROBE; r_recv = 1; r_last_recv = 0; f_last_recv = 0; CNU = CNU của gói FER_PROBE). Bước 2.2: So sánh WND_ID của gói FER_PROBE và WND_ID của nút. - Nếu WND_ID của gói FER_PROBE > WND_ID của nút thì cập nhật (WND_ID của nút = WND_ID của gói FER_PROBE; r_last_recv = r_recv; r_recv = 1) và chuyển sang Bước 3. - Cập nhật r_recv của entry (r_recv + =1). - Cập nhật CNU của entry = CNU của gói FER_RPOBE. - Tìm phần tử trong trường links của FER_PROBE có nb_ID = địa chỉ nút hiện tại. Nếu tìm thấy thì cập nhật f_last_recv của entry = n_recv của phần tử tìm thấy. Bước 3: Cập nhật các giá trị FER và service_time của liên kết df = f_last_recv / fer_probe_wnd_size; 9 dr = r_last_recv / fer_probe_wnd_size; fer = 1 – df * dr; nb_fer = 0.7 * fer + 0.3 *nb_fer; Tính service_time theo công thức (18); nb_service_time = 0.7 * service_time + 0.3 * nb_service_time; 2.3.4. Mô đun định tuyến xuyên tầng Mô đun định tuyến xuyên tầng của giao thức AODV-DM được triển khai bằng cơ chế tìm đường được minh hoạ trong Thuật toán 2.3. Thuật toán 2.3. Cơ chế tìm đường của giao thức AODV-DM Đầu vào: <địa chỉ nút nguồn>, <địa chỉ nút đích> Đầu ra: đường đi tới nút đích được cài đặt vào bảng định tuyến Hoạt động của thuật toán: Bước 1: Gửi gói yêu cầu tìm đường RREQ tại nút có địa chỉ = <địa chỉ nút nguồn> với RQ_DELAY = 0, hop_count = 0, Destination Address = <địa chỉ nút đích>, Broadcast_ID = Broadcast_ID +1 Bước 2: Nhận và xử lý gói RREQ Bước 2.1: Đọc Broadcast_ID của gói RREQ, kiểm tra trong bộ nhớ Broadcast_ID xem đã nhận gói RREQ hay chưa. Nếu đã nhận thì bỏ qua, nếu chưa nhận thì thêm Broadcast_ID vào bộ nhớ Broadcast_ID. Bước 2.2: Cập nhật giá trị RQ_DELAY và hop_count trong gói RREQ - Tìm entry trong Neighbor Table có địa chỉ = IP nút gửi gói FER_PROBE. - Nếu không tìm thấy thì thêm một entry mới vào bảng Neighbor Table với Neighbor ID = địa chỉ IP nút gửi/chuyển tiếp gói RREQ và LINK_DELAY = MAX_LINK_DELAY. - Nếu tìm thấy thì đọc giá trị LINK_DELAY của entry tìm được. - Cập nhật RQ_DELAY = RQ_DELAY + LINK_DELAY. - Cập nhật hop_count = hop_count + 1. Bước 2.3: Cập nhật đường nghịch (reverse path) - Tìm entry trong bảng định tuyến có địa chỉ đích = <địa chỉ nút nguồn> - Nếu không tìm thấy thì bổ sung entry mới (IP đích = <địa chỉ nút nguồn>; hop count = hop count gói RREQ; PATH_DELAY = RQ_DELAY; next_hop = < IP nút gửi gói RREQ>) vào bảng định tuyến. - Nếu tìm thấy thì cập nhật entry (next hop = <địa chỉ IP nút nguồn gửi/chuyển tiếp gói RREQ>) khi một trong các điều kiện sau thoả mãn: (1) Số thứ tự đích của gói RREQ lớn hơn số thứ tự đích của entry; (2) Số thứ tự đích của gói RREQ bằng số thứ tự đích của entry, hop_count của entry lớn hơn hoặc bằng hop_count của gói RREQ và PATH_DELAY của entry lớn hơn RQ_DELAY của gói RREQ. Bước 2.4: Tạo gói trả lời đường nếu có thông tin về đường tới đích - Tìm entry trong bảng định tuyến có địa chỉ đích = <địa chỉ nút đích>. 10 - Nếu tìm thấy thì tạo gói RREP (hop_count = hop_count của entry + 1; RP_DELAY = PATH_DELAY + RQ_DELAY) và hủy gói RREQ. Bước 2.5: Tạo gói trả lời đường nếu nút hiện tại là nút đích - Kiểm tra địa chỉ IP nút hiện tại có bằng <địa chỉ IP nút đích> hay không? - Nếu địa chỉ IP của nút hiện tại = <địa chỉ IP nút đích> thì tạo gói RREP để trả lời đường (hop_count = 0; RP_DELAY = 0) và hủy gói RREQ. Bước 2.6: Chuyển tiếp gói RREQ kiểu broadcast. Bước 3: Nhận và xử lý gói RREP Bước 3.1: Cập nhật giá trị RQ_DELAY và hop_count trong gói RREP - Tìm entry trong Neighbor Table có địa chỉ = IP nút gửi gói RREP. - Nếu không tìm thấy thì thêm một entry mới vào bảng Neighbor Table với Neighbor ID = địa chỉ IP nút gửi/chuyển tiếp gói RREP và LINK_DELAY = MAX_LINK_DELAY. - Nếu tìm thấy thì đọc giá trị LINK_DELAY của entry tìm được. - Cập nhật RP_DELAY = RP_DELAY + LINK_DELAY. - Cập nhật hop_count = hop_count + 1. Bước 3.2: Cập nhật đường thuận (forward path) - Tìm entry trong bảng định tuyến có địa chỉ đích = <địa chỉ nút đích> - Nếu không tìm thấy thì bổ sung entry mới (IP đích = <địa chỉ nút đích>; hop count = hop count gói RREP; PATH_DELAY = RP_DELAY; next_hop = <địa chỉ IP nút gửi gói RREP>) vào bảng định tuyến - Nếu tìm thấy thì cập nhật entry (next hop = <địa chỉ IP nút nguồn gửi/chuyển tiếp gói RREP>) khi một trong các điều kiện sau thoả mãn: (1) Số thứ tự đích của gói RREP lớn hơn số thứ tự đích của entry; (2) Số thứ tự đích của gói RREP bằng số thứ tự đích của entry, hop_count của entry lớn hơn hoặc bằng hop_count của gói RREP và PATH_DELAY của entry lớn hơn RP_DELAY của gói RREP. Bước 3.3: Chuyển tiếp/ huỷ bỏ gói RREP - Nếu địa chỉ IP nút hiện tại = thì huỷ bỏ gói RREP. - Nếu địa chỉ IP nút hiện tại khác <địa chỉ IP nút nguồn> thì tìm entry trong bảng định tuyến có địa chỉ đích bằng <địa chỉ IP nút nguồn> và chuyển tiếp gói RREP kiểu unicast tới nút có địa chỉ = next_hop của entry tìm được. 2.4. Kiểm nghiệm và đánh giá kết quả 2.4.1. Kịch bản mô phỏng * Kịch bản mô phỏng 1 Kịch bản mô phỏng thứ nhất được minh họa trong Hình 2.8. Khoảng cách giữa các hàng và các cột của các nút là 40 mét. Công nghệ tầng MAC là IEEE 802.11b, tốc độ truyền tối đa là 11 Mbps, khoảng cách truyền dữ liệu tối đa là 50 mét và khoảng cách cảm nhận kênh truyền là 110 mét. 11 Hình 2.8. Mô hình kịch bản mô phỏng Có hai luồng dữ liệu CBR với cặp nút nguồn-đích là 0-16 và 24-8. Tốc độ các luồng dữ liệu thay đổi từ 50kbps tới 100 kbps, 150 kbps, 200 kbps và 250 kbps. Bốn luồng CBR ở tâm được sử dụng để mô phỏng các luồng gây nhiễu. Tốc độ của các luồng gây nhiễu cũng thay đổi từ 0.1 Mpbs tới 0.2 Mpbs, 0.4 Mpbs, 0.6 Mbps, 0.8 Mpbs và 1.0 Mpbs. Từ nút 32 tới nút 55 di chuyển liên tục theo vòng với tốc độ di chuyển 5 m/s tạo tiến trình tìm đường mới. Thời gian mô phỏng là 1000 giây. Với mỗi bộ tham số mô phỏng, NS2 được chạy 10 lần với các giá trị bộ sinh số ngẫu nhiên khác nhau cho mỗi giao thức cần đánh giá. Kết quả được tính trung bình của 10 lần mô phỏng. * Kịch bản mô phỏng 2 Tô-pô mạng ban đầu trong được khởi tạo bằng với các nút phân bố theo ma trận vuông có kích thước 12x12 (144 nút). Khoảng cách theo hàng hoặc cột giữa hai nút liên tiếp là 40 mét. Thời gian mô phỏng là 1000 giây. Số lượng nút di chuyển, danh sách nút di chuyển được thiết lập ngẫu nhiên trong khoảng từ 1 tới 144 nút và thời điểm bắt đầu di chuyển của mỗi nút được thiết lập ngẫu nhiên trong khoảng từ giây thứ 10 đến giây thứ 50. Tốc độ di chuyển của các nút trong danh sách các nút di chuyển là 10 m/s. Với các luồng dữ liệu, các nút nguồn và đích được thiết lập ngẫu nhiên trong các tập các nút tương ứng là 0-71 và 72-143. Thời gian bắt đầu phát lưu lượng được thiết lập ngẫu nhiên trong khoảng từ giây thứ 8 đến giây thứ 108. Tốc độ của mỗi luồng dữ liệu được thay đổi từ 10 kpbs tới 90 kbps. Các độ đo đánh giá hiệu năng của mỗi giao thức được tính trung bình trên cơ sở kết quả 10 lần chạy mô phỏng. 2.4.2. Các kết quả và đánh giá 2.4.2.1. Thông lượng trung bình Kết quả mô phỏng về thông lượng trung bình đo tại các nút đích của Kịch bản 1 và Kịch bản 2 được biểu diễn tương ứng trong Hình 2.9 và Hình 2.10. 12 Hình 2.9. Thông lượng trung bình Hình 2.10. Thông lượng trung bình trong Kịch bản 1 trong Kịch bản 2 Với kịch bản 1 có các luồng gây nhiễu, giao thức AODV-DM đạt được thông lượng lớn hơn so với giao thức AODV tại cả hai tốc độ truyền của các luồng dữ liệu. Thông lượng trung bình của giao thức AODV-DM cao hơn so với giao thức AODV tại tốc độ luồng dữ liệu 50 kbps và 200 kbps tương ứng là xấp xỉ 23% và 28%. Với kịch bản 2 sử dụng mô hình mô phỏng ngẫu nhiên, giao thức AODV-DM vẫn đạt được thông lượng trung bình lớn hơn so với giao thức AODV. 2.4.2.2. Tỷ lệ truyền gói thành công Kết quả mô phỏng về tỷ lệ truyền gói tin thành công của Kịch bản 1 và Kịch bản 2 được biểu diễn tương ứng trong Hình 2.11 và Hình 2.12. Hình 2.11. Tỷ lệ truyền gói thành Hình 2.12. Tỷ lệ truyền gói thành công trong Kịch bản 2 công trong Kịch bản 1 Với Kịch bản 1, tính trung bình, tỷ lệ truyền gói thành công của giao thức AODV-DM đạt được cao hơn 28% so với giao thức AODV. Với kịch bản 2 sử dụng mô hình mô phỏng ngẫu nhiên, giao thức AODV-DM vẫn đạt được tỷ lệ truyền gói thành công lớn hơn so với giao thức AODV. 2.4.2.3. Trễ truyền gói trung bình Kết quả mô phỏng về trễ truyền gói tin trung bình của Kịch bản 1 và Kịch bản 2 được biểu diễn tương ứng trong Hình 2.13 và Hình 2.14. 13 Hình 2.14. Trễ truyền gói trung Hình 2.13. Trễ truyền gói trung bình trong Kịch bản 2 bình trong Kịch bản 1 Với Kịch bản 1, khi sử dụng giao thức AODV-DM thay thế cho giao thức AODV, thời gian trễ truyền gói trung bình giảm được xấp xỉ 16% và 34% tương ứng với tốc độ luồng dữ liệu 50 kbps và 100kbps. Với kịch bản 2 sử dụng mô hình mô phỏng ngẫu nhiên, giao thức AODV-DM vẫn đạt được trễ truyền gói tin trung bình nhỏ hơn so với giao thức AODV. 2.4.2.4. Tải định tuyến Kết quả mô phỏng về tải định tuyến của Kịch bản 1 và Kịch bản 2 được biểu diễn tương ứng trong Hình 2.15 và Hình 2.16. Hình 2.16. Tải định tuyến trong Hình 2.15. Tải định tuyến trong Kịch bản 2 Kịch bản 1 Với Kịch bản 1, độ giảm của tải định tuyến trung bình khi sử dụng giao thức AODV-DM thay thế cho giao thức AODV là xấp xỉ 58% và 42% tương ứng với tốc độ dữ liệu 100 kbps và 150 kbps. Với kịch bản 2 sử dụng mô hình mô phỏng ngẫu nhiên không có các luồng gây nhiễu, giao thức AODV-DM vẫn đạt được tải định tuyến nhỏ hơn so với giao thức AODV. 14 2.5. Kết luận Chương 2 Nội dung Chương 2 đã đề xuất các cải tiến đối với giao thức AODV trong mạng MANET đa chặng có các vùng tắc nghẽn trên cơ sở cải tiến cơ chế chọn đường của giao thức AODV theo số chặng thành cơ chế chọn đường theo trễ đầu-cuối. Phương pháp khai thác thông tin định tuyến xuyên tầng để lấy thông tin về độ trễ của các liên kết tại tầng MAC đã được sử dụng làm cơ sở để tính độ trễ đầu cuối của các con đường tại tầng Mạng. Độ trễ của mỗi liên kết tại tầng MAC được ước lượng theo mức độ sử dụng kênh truyền của nút nguồn và tỷ lệ lỗi frame của liên kết. Kỹ thuật đo giá trị của mức độ sử dụng kênh truyền của một nút mạng và ước lượng tỷ lệ lỗi của liên kết cũng đã được đề xuất trong luận án này. Việc bổ sung, điều chỉnh về cấu trúc gói tin, cơ chế định tuyến trên giao thức AODV đã được đề xuất trong giao thức mới có tên gọi AODV-DM. Kết quả của việc đánh giá hiệu năng cho thấy, giao thức AODV-DM đạt được hiệu năng cao hơn so với giao thức AODV về thông lượng (cao hơn xấp xỉ 24%), tỷ lệ truyền gói thành công (cao hơn xấp xỉ 28%), độ trễ truyền gói trung bình (thấp hơn xấp xỉ 20%) và tải định tuyến (thấp hơn xấp xỉ 50%) trong trường hợp mạng có các vùng tắc nghẽn. Với kịch bản mô phỏng ngẫu nhiên không có các luồng gây nhiễu tạo vùng tắc nghẽn, kết quả mô phỏng cho thấy, độ chênh lệch về các giá trị đo hiệu năng của giao thức AODV-DM so với giao thức AODV tuy không đạt được như kịch bản 1 nhưng giao thức AODV-DM vẫn có hiệu năng cao hơn giao thức AODV ở các độ đo hiệu năng được đánh giá. Mặc dù giao thức AODV đã được cải tiến theo hướng chọn đường đi tránh khỏi các vùng tắc nghẽn nhưng để hỗ trợ tốt hơn cho các lớp chương trình ứng dụng khác nhau, giao thức này cần tiếp tục cải tiến để cung cấp khả năng định tuyến ưu tiên theo yêu cầu QoS từ tầng Ứng dụng. Các kết quả chính của chương này được công bố trong [A4]. 15 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 3.1. Đề xuất ý tưởng cải tiến cho giao thức AOMDV Ý tưởng cải tiến giao thức AOMDV được đề xuất là xây dựng một cơ chế định tuyến động theo từng lớp chương trình ứng dụng có yêu cầu QoS khác nhau trên cơ sở xây dựng một hàm lượng giá đường theo từng lớp lưu lượng QoS với bộ thông số đầu vào bao gồm: ngưỡng chấp nhận được của các tiêu chuẩn QoS, trọng số của các tiêu chuẩn QoS và các thông số về chất lượng đường đầu cuối theo các tiêu chuẩn QoS. Với cùng giá trị các thông số của chất lượng đường đầu cuối, giá trị của hàm sẽ thay đổi theo từng lớp lưu lượng QoS cho phép ưu tiên chọn đường có thông số chất lượng phù hợp với yêu cầu QoS từ lớp lưu lượng ở tầng Ứng dụng. 3.2. Xây dựng hàm lượng giá đường theo QoS 3.2.1. Phân lớp các ứng dụng theo yêu cầu QoS Chuẩn ITU-T G.1010 được sử dụng làm cơ sở để phân lớp lưu lượng yêu cầu QoS. Theo đó, các ứng dụng có thể chia thành 3 lớp: Lớp 1: Các ứng dụng chấp nhận lỗi nhưng nhạy cảm với trễ dữ liệu; Lớp 2: Các ứng dụng chấp nhận lỗi và trễ dữ liệu và Lớp 3: Các ứng dụng cho phép có độ trễ nhưng không chấp nhận lỗi. 3.2.2. Phương pháp ra quyết định chọn đường Theo chuẩn ITU-T G.1010, các ứng dụng được phân loại theo yêu cầu QoS trên cơ sở 4 tiêu chuẩn QoS bao gồm: độ trễ (delay), độ biến thiên trễ (jitter), tỷ lệ mất gói (packet loss rate) và tốc độ dữ liệu (data rate). Bài toán đặt ra ở đây là bài toán chọn đường đa tiêu chuẩn. Trong số các đường tìm được, đường nào sẽ là đường tốt nhất theo tiêu chuẩn QoS? Để giải quyết bài toán này, phương pháp Tổng có trọng số (SAW – Simple Additive Weighting) của Savitha K. (2011) đã được đề xuất sử dụng. Gọi HIJ là giá trị chuẩn hoá của tiêu chuẩn x của đường thứ k. Giá trị chuẩn hoá này được xác định như sau: KLM HIJ = KM KM KLM , Fế/ P Qà SDê/ Uℎ/ẩF SíUℎ UựU , Fế/ P Qà SDê/ Uℎ/ẩF SDê/ UựU (24) trong đó, HJ là ngưỡng của tiêu chuẩn QoS x đối với lớp QoS thứ i. HJ là ngưỡng lớn nhất với tiêu chuẩn tích cực và là ngưỡng nhỏ nhất với tiêu chuẩn tiêu cực. Các tiêu chuẩn tiêu cực bao gồm độ trễ, độ biến thiên trễ và tỷ lệ mất gói. Tiêu chuẩn tích cực là băng thông còn lại. Ma trận ngữ cảnh chuẩn hoá của lớp QoS thứ i xác định như sau: 16 HZ$ HZ[ HZ1 HZ& Y<6 = ⋯ ⋯ ⋯ ⋯ H7$ H7[ H71 H7& (25) Véc tơ trọng số của lớp QoS thứ i được định nghĩa theo (26); 4,6 4]6 46 = 4^6 4_6 (26) trong đó, WDi, WJi, WLi và WBi là trọng số tương ứng của độ trễ, độ biến thiên trễ, tỉ lệ mất gói và băng thông còn lại của lớp QoS thứ i. Hàm lượng giá đường theo lớp QoS thứ i cho đường thứ k được định nghĩa theo (27); )`6,I = Y<6,I ∙ 46 = a@I ∙ 4,6 + abI ∙ 4]6 + aQI ∙ 4^6 + acI ∙ 4_6 (27) Từ (24) và (27), ta có công thức lượng giá đường (28); )`6,I = !,6 !]6 !^6 _I . 4,6 + . 4]6 + . 4^6 + . 4_6 ,I ]I ^I !_6 (28) Trong đó, TDi, TJi, TLi và TBi là các ngưỡng yêu cầu tương ứng của độ trễ, độ biến thiên trễ, tỉ lệ mất gói và băng thông còn lại theo lớp QoS thứ i; Dk, Jk, Lk và Bk là các giá trị tương ứng của độ trễ, độ biến thiên trễ, tỉ lệ mất gói và băng thông còn lại của con đường thứ k; 3.2.3. Xác định trọng số của các tiêu chuẩn QoS Để xác định trọng số cho các tiêu chuẩn QoS, phương pháp Phân tích thứ bậc AHP do Saaty T. (2008) đề xuất được sử dụng cho bài toán chọn đường theo các tiêu chuẩn QoS bao gồm độ trễ, độ biến thiên trễ, tỷ lệ mất gói và tốc độ dữ liệu. Theo phương pháp AHP, đối với từng lớp ứng dụng các yêu cầu QoS khác nhau, cần thiết lập ma trận so sánh theo cặp cho từng lớp lưu lượng dữ liệu, sau đó tính véc tơ ưu tiên. Giá trị của các thành phần trong véc tơ ưu tiên chính là trọng số của các tham số QoS theo lớp lưu lượng dữ liệu. Mối quan hệ về độ quan trọng giữa các tiêu chuẩn theo cặp của từng lớp QoS được biểu diễn tương ứng các ma trận CM1, CM2 và CM3. Thứ tự các hàng và cột trong các ma trận này là: độ trễ, độ biến thiên trễ, tỷ lệ mất gói và tốc độ dữ liệu. 1 2 6 8 1/2 1 4 6 3YZ = 1/6 1/4 1 3 1/8 1/6 1/3 1 17 Từ ma trận CM1, áp dụng phương pháp của Kunz J. (2010), ta tính được véc tơ trọng số W1 và độ nhất quán CR1 cho Lớp 1 như sau: 0,533 0,317 4Z = và CR1= 0,026 0,101 0,049 Thực hiện tương tự với Lớp 2 và Lớp 3, ta có các kết quả sau: 1 1/3 1/5 1/2 0,078 3 1 1/4 2 0,202 3Ym = => 4m = và CR2=0,044 0,604 5 4 1 6 0,116 2 1/2 1/6 1 1 3 1/6 1/3 0,104 1/3 1 1/9 1/5 0,048 3Yn = => 4n = và CR3= 0,049 0,623 6 9 1 4 0,226 3 5 1/4 1 Kết quả tính véc tơ trọng số của 3 lớp được tổng hợp trong Bảng 3.6. 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 Tiêu chuẩn QoS Lớp 1 Lớp 2 Lớp 3 Độ trễ (delay) 0,533 0,078 0,104 Độ xáo trộn gói (jitter) 0,317 0,202 0,048 Tỷ lệ mất gói (packet loss rate) 0,101 0,604 0,623 Tốc độ dữ liệu (data rate) 0,049 0,116 0,226 3.3. Dự đoán chất lượng liên kết tại tầng MAC Để xây dựng hàm lượng giá cho độ đo định tuyến và cơ chế định tuyến phù hợp với yêu cầu QoS của tầng Ứng dụng, cần ước lượng các giá trị độ trễ và tỷ lệ mất gói của mỗi liên kết thành phần tại tầng MAC. Phương pháp ước lượng trễ và tỷ lệ mất gói của liên kết đã được trình bày trong của Chương 2 trong luận án. 3.4. Cải tiến giao thức AOMDV 3.4.1. Xây dựng hàm lượng giá đường Giao thức định tuyến đa đường AOMDV được lựa chọn để cải tiến thành giao thức QCLR trên cơ sở xây dựng một độ đo định tuyến phù hợp với yêu cầu QoS của các lớp lưu lượng thuộc tầng Ứng dụng. 18 Công thức (29) được sử dụng để tính tỷ lệ mất gói và công thức (30) được sử dụng để tính độ trễ của một con đường đầu cuối. ^C = 1 − 1∈C(1 − +>?1 ) (29) ,C = 1∈C !p1 (30) Trong đó, Lr và Dr tương ứng là tỉ lệ mất gói và độ trễ của con đường r, FERl và TSl tương ứng là là tỉ lệ mất gói và trễ dịch vụ của liên kết l thuộc con đường r. Trong các tiêu chuẩn QoS của chuẩn ITU-T G.1010, độ trễ có tầm quan trọng lớn nhất đối với các lưu lượng dữ liệu thuộc Lớp 1 và tỷ lệ mất gói có tầm ảnh hưởng lớn nhất tới các lưu lượng dữ liệu thuộc Lớp 2 và 3. Vì vậy, độ đo định tuyến của giao thức QCLR sẽ được xây dựng trên cơ sở hàm lượng giá đường theo độ trễ và tỷ lệ mất gói của đường đầu cuối. Hàm lượng giá đường RMV được đề xuất theo (31); ?Y`6,C = 4,6 !,6 !^6 + 4^6 ,C ^C (31) Trong đó, ?Y`6,C là giá trị của đường r thuộc lớp QoS thứ i; ^C và ,C tương ứng là tỉ lệ mất gói và độ trễ của con đường r; !^6 và !,6 tương ứng là ngưỡng của tỉ lệ mất gói và độ trễ của lớp thứ i; 4,6 và 4^6 tương ứng là trọng số độ trễ và tỉ lệ mất gói của lớp QoS thứ i. 3.4.2. Đề xuất cơ chế định tuyến cho giao thức QCLR Các điều chỉnh sau đã thực hiện trong giao thức AOMDV khi cải tiến thành giao thức QCLR: (1)Bổ sung trường PKT_DELAY và PKT_PLR vào các gói RREQ và RREP; (2) Bổ sung trường PATH_DELAY, PATH_PLR và PATH_STABILITY vào mỗi con đường trong bảng định tuyến; (3) Bổ sung hai trường: LINK_DELAY and LINK_PLR vào mỗi entry trong bảng láng giềng của mỗi nút. Hoạt động của giao thức QCLR được mô tả như sau: - Khi một nút nhận được một gói RREQ hoặc RREP, nó sẽ cập nhật lại giá trị trường PATH_DELAY và PATH_PLR của đường tương ứng theo (32) và (33). )q!r_,>^qt = ^u^qt + )v!_,>^qt (32) )q!r_)^? = 1 − (1 − ^u - Xem thêm -