Tóm tắt luận án Tiến sĩ Công nghệ thông tin: Nâng cao hiệu năng mạng MANET sử dụng kỹ thuật định tuyến cân bằng tải đảm bảo chất lượng truyền dẫn

Chia sẻ: Gaocaolon6 Gaocaolon6 | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

24
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án phân tích, đánh giá QoT trên các lộ trình truyền dữ liệu và ảnh hưởng của nó đến hiệu năng mạng MANET theo các thuật toán định tuyến khác nhau. Từ đó, đề xuất các thuật toán định tuyến cải tiến nhằm cân bằng tải lưu lượng, đồng thời đảm bảo QoT trên các lộ trình truyền dữ liệu, nâng cao hiệu năng mạng MANET.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận án Tiến sĩ Công nghệ thông tin: Nâng cao hiệu năng mạng MANET sử dụng kỹ thuật định tuyến cân bằng tải đảm bảo chất lượng truyền dẫn

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Ệ ———————————- LÊ HỮU BÌNH NÂNG CAO HIỆU NĂNG MẠNG MANET SỬ DỤNG KỸ THUẬT ĐỊNH TUYẾN CÂN BẰNG TẢI ĐẢM BẢO CHẤT LƯỢNG TRUYỀN DẪN Chuyên ngành: Hệ thống thông tin Mã số: 9480104 TÓM TẮT LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2019
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. Võ Thanh Tú Người hướng dẫn khoa học 2: PGS.TS. Nguyễn Văn Tam Phản biện 1: Phản biện 2: Phản biện 3: Luận án đượ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 20. . . . 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
MỞ ĐẦU 1. Tính cấp thiết của đề tài nghiên cứu Trong xu thế phát triển của công nghệ mạng, truyền thông không dây là giải pháp chủ đạo cho công nghệ mạng viễn thông nói chung, mạng truyền dữ liệu và mạng máy tính nói riêng. Trong thời đại của công nghệ mạng thế hệ thứ 5 (5G) và Internet vạn vật (IoT), đã xuất hiện một số mô hình mạng không dây để cung cấp các ứng dụng trong thực tế. Cơ bản như mạng cảm biến không dây, mạng không dây hình lưới, mạng tùy biến di động (MANET). Trong đó, MANET đang ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực [66]. Để mở rộng phạm vi ứng dụng của mạng MANET, cần phải nâng cao tốc độ truyền dẫn, tăng phạm vi phủ sóng, mở rộng vùng diện tích sử dụng. Tuy nhiên, điều này sẽ gặp phải một số khó khăn về mặt kỹ thuật. Vì việc tăng tốc độ truyền dẫn, phạm vi phủ sóng và vùng diện tích sử dụng thì các hiệu ứng vật lý xảy ra trên các lộ trình cũng tăng lên, làm ảnh hưởng đến hiệu năng mạng [26, 29, 30, 61, 65]. Để đảm bảo hiệu năng mạng, cần phải tìm ra các giải pháp nhằm giảm đảm bảo QoT trong mạng. QoT của các kênh truyền phụ thuộc vào lộ trình, mà lộ trình được quyết định bởi thuật toán định tuyến. Vì vậy, việc nghiên cứu các thuật toán định tuyến ràng buộc QoT trong mạng MANET có ý nghĩa đặc biệt quan trọng. Vấn đề này đã và đang được nhiều nhóm nghiên cứu quan tâm trong thời gian gần đây [5, 24, 33, 35, 46, 51, 53]. Các công trình nghiên cứu này đã đề xuất các thuật toán định tuyến với mục tiêu lựa chọn lộ trình có QoT tốt nhất để truyền dữ liệu. Tuy nhiên, một vấn đề đặt ra với kỹ thuật định tuyến theo QoT tốt nhất là tăng tình trạng nghẽn cục bộ do tải lưu lượng phân bố không đồng đều trên các kết nối trong toàn mạng. Nghẽn cục bộ là một vấn đề ảnh hưởng lớn đến hiệu năng mạng. Vấn đề này thường được giải quyết bằng kỹ thuật định tuyến cân bằng tải. Trong MANET, định tuyến cân bằng tải cũng đã được nhiều nhóm nghiên cứu triển khai [34, 39, 41, 44, 67, 70]. Các công trình nghiên cứu này đã đề xuất được các thuật toán định tuyến cân bằng tải lưu lượng qua các kết nối trong mạng, giảm thiểu tình trạng nghẽn cục bộ. Tuy nhiên, do đặc trưng cơ bản của kỹ thuật định tuyến cân bằng tải là thuật toán định tuyến có thể chọn "lộ trình dài". Điều này có thể làm giảm QoT của hệ thống mạng. Các công trình nghiên cứu về kỹ thuật định tuyến cân bằng tải trong mạng MANET đã được đề cập ở trên chưa xét đến vấn đề này. Thông qua việc phân tích tình hình nghiên cứu về kỹ thuật định tuyến QoT và định tuyến cân bằng tải ở trên, tác giả nhận thấy rằng, việc kết hợp hài hòa giữa định tuyến cân bằng tải và định tuyến đảm bảo QoT là điều cần thiết. Đặc biệt là 1
trong hệ thống mạng MANET có vùng diện tích rộng, mật độ nút cao, sử dụng kênh có băng thông lớn. Vì vậy, trong đề tài luận án này, tác giả tập trung nghiên cứu các kỹ thuật định tuyến cân bằng tải, đồng thời đảm bảo QoT của các lộ trình truyền dữ liệu nhằm nâng cao hiệu năng mạng MANET. 2. Mục tiêu nghiên cứu Phân tích, đánh giá QoT trên các lộ trình truyền dữ liệu và ảnh hưởng của nó đến hiệu năng mạng MANET theo các thuật toán định tuyến khác nhau. Từ đó, đề xuất các thuật toán định tuyến cải tiến nhằm cân bằng tải lưu lượng, đồng thời đảm bảo QoT trên các lộ trình truyền dữ liệu, nâng cao hiệu năng mạng MANET. 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của đề tài luận án tập trung vào các thuật toán định tuyến cân bằng tải và định tuyến đảm bảo QoT trong MANET. Phạm vi nghiên cứu của đề tài tập trung vào nhóm giao thức định tuyến DSR và AODV. 4. Nội dung nghiên cứu Luận án tập trung nghiên cứu các nội dung sau: (i) Xây dựng và phát triển các điều kiện ràng buộc QoT theo các thuật toán định tuyến khác nhau. (ii) Phân tích, đánh giá QoT trên mạng MANET đối với các giao thức định tuyến DSR, AODV và định tuyến cân bằng tải. (iii) Đề xuất các thuật toán định tuyến cải tiến của giao thức DSR và AODV, nhằm cân bằng tải lưu lượng trong toàn mạng, đồng thời đảm bảo QoT trên các lộ trình, nâng cao hiệu năng mạng MANET. 5. Bố cục của luận án: Luận án được trình bày theo bố cục như sau: Phần mở đầu tập trung phân tích tính cấp thiết của đề tài nghiên cứu, từ đó xác định mục tiêu nghiên cứu, đối tượng và phạm vi nghiên cứu cũng như các phương pháp nghiên cứu của đề tài luận án. Chương 1 trình bày tổng quan về MANET và các yếu tố ảnh hưởng đến hiệu năng mạng. Chương 2 tập trung đánh giá chất lượng truyền dẫn của mạng MANET khi sử dụng giao thức định tuyến theo yêu cầu và cân bằng tải. Chương 3 đề xuất thuật toán định tuyến cân bằng tải đảm bảo chất lượng truyền dẫn dựa trên tải lưu lượng qua mỗi lộ trình. Chương 4 đề xuất thuật toán định tuyến cân bằng tải đảm bảo chất lượng truyền dẫn dựa trên thông tin định tuyến của nút nguồn. Phần kết luận trình bày những kết quả đóng góp của luận án, đồng thời đề ra những vấn đề cần tiếp tục nghiên cứu trong tương lai. Cuối cùng là các phụ lục, trình bày chi tiết các số liệu tính toán cho các ví dụ minh họa trong Luận án (Phụ lục A), trình bày mã nguồn của một số mô đun chính trong phần mềm mô phỏng được tác giả triển khai trên OMNeT++ (Phụ Lục B). 2
CHƯƠNG 1 TỔNG QUAN VỀ MANET VÀ CÁC YẾU TỐ ẢNH HƯỞNG ĐẾN HIỆU NĂNG MẠNG 1.1. Những vấn đề cơ bản về mạng MANET Nội dung phần này trình bày nguyên lý, đặc điểm của mạng MANET và các yếu tốt ảnh hưởng đến hiệu năng mạng. 1.2. Định tuyến trong mạng MANET Định tuyến trong mạng MANET cần phải thực hiện hai nhiệm vụ, Một là tạo thông tin định tuyến, nghĩa là tìm lộ trình từ nguồn đến đích để cập nhật vào bảng định tuyến. Hai là duy trì thông tin định tuyến đã được cập nhật để xác định các thông tin lộ trình trong bảng định tuyến có còn khả thi hay không. 1.3. Tình hình nghiên cứu về định tuyến trong mạng MANET 1.3.1. Định tuyến QoS Định tuyến QoS là kỹ thuật định tuyến mà trong đó các tham số về QoS như xác suất lỗi gói, độ trễ, thông lượng được xem xét trong quá trình khám phá lộ trình, nhằm đảm bảo QoS của hệ thống mạng [1, 14, 62]. 1.3.2. Định tuyến QoT Định tuyến QoT là kỹ thuật định tuyến mà trong đó các tham số về QoT được xem xét trong quá trình khám phá lộ trình. Trong thời gian gần đây, kỹ thuật định tuyến QoT đã được một số nhóm nghiên cứu triển khai. Có hai phương pháp hiện đang được các nhóm nghiên cứu sử dụng để đưa các ràng buộc về QoT vào các thuật toán định tuyến. Một là, ràng buộc QoT thông qua hàm trọng số, được thực hiện bằng cách xây dựng các hàm trọng số có chứa các tham số về QoT, thuật toán định tuyến dựa trên hàm trọng số này để lựa chọn lộ trình [46, 35, 29]. Hai là, ràng buộc QoT thông qua các gói điều khiển, được thực hiện bằng cách sử dụng các gói điều khiển như RREQ và RREP để trao đổi các thông tin về QoT giữa nút mạng, từ đó xác định các ràng buộc của QoT cho việc lựa chọn lộ trình [5, 24, 51, 58]. 1.3.3. Định tuyến cân bằng tải Trong mạng MANET, kỹ thuật định tuyến cân bằng tải cũng đã được nhiều nhóm nghiên cứu đặc biệt quan tâm. Trong [44], các tác giả đã đề xuất một giao thức định tuyến cân bằng tải cho mạng tùy biến có tên LMP-DSR. Giao thức LMP- DSR được cải tiến từ giao thức DSR bằng cách sử dụng kỹ thuật định tuyến đa đường thay cho định tuyến đơn đường. Trong [39], thuật toán định tuyến đa mức (MRA) được đề xuất để cân bằng tải lưu lượng trong mạng tùy biến. Thuật toán 3
MRA sử dụng phương pháp lựa chọn các nút trung gian mà nó có đủ tài nguyên và dung lượng để đến nút đích. Trong [34], các tác giả đã đề xuất giao thức định tuyến có tên LBCAR. Giao thức LBCAR sử dụng hai độ đo, đó là mật độ tải lưu lượng và chi phí kết nối kết hợp với lộ trình định tuyến để xác định trạng thái tắc nghẽn. Lộ trình có mật độ tải lưu lượng thấp và thời gian tồn tại cao nhất sẽ được lựa chọn cho việc truyền dữ liệu. 1.3.4. Một số nhận xét và đánh giá • Việc đề xuất các thuật toán định tuyến có xét đến QoT đã được triển khai. Tuy nhiên, hầu hết các thuật toán được đề xuất là kiểm tra ràng buộc QoT sau khi tập lộ trình đã tìm được.Vì vậy, có một số trường hợp lộ trình tìm thấy chưa phải là lộ trình có QoT tốt nhất, thậm chí không thỏa mãn ràng buộc của QoT. • Về các mô hình mạng được sử dụng cho việc đánh giá hiệu năng, hầu hết các công trình chỉ đánh giá trên các mô hình mạng tốc độ thấp, chủ yếu là kênh có băng thông 20 MHz. Trong trường hợp hệ thống mạng sử dụng kênh băng thông rộng, ảnh hưởng của các hiệu ứng vật lý cần phải được quan tâm, vì băng thông càng rộng thì nhiễu tác động lên kênh truyền càng lớn. • Kỹ thuật định tuyến cân bằng tải trong mạng MANET cũng đã được triển khai. Các kết quả nghiên cứu đã chứng minh hiệu năng mạng cải thiện về mặt xác suất nghẽn đối với định tuyến cân bằng. Tuy nhiên, các điều kiện ràng buộc về QoT chưa được xem xét trong các thuật toán định tuyến cân bằng. 1.4. Những đóng góp của luận án (i) Đề xuất phương pháp xác định các điều kiện ràng buộc của QoT dựa trên mô hình xuyên lớp, sử dụng cho chế khám phá lộ trình của các giao thức định tuyến theo yêu cầu trong mạng MANET. (ii) Đề xuất thuật toán định tuyến cân bằng tải đảm bảo QoT dựa trên tải lưu lượng phân phối đến mỗi lộ trình (LBRQT) cho mạng MANET. (iii) Đề xuất thuật toán định tuyến cân bằng tải đảm bảo QoT cho mạng MANET dựa trên thông tin định tuyến của nút nguồn (SLBQT-DSR). 1.5. Kết luận chương Chương 1 đã trình bày những vấn đề cơ bản về mạng MANET và các yếu tố ảnh hưởng đến hiệu năng mạng, trong đó các kỹ thuật định tuyến được đi sâu phân tích. Tác giả cũng đã phân tích kỹ tình hình nghiên cứu trong nước và trên thế giới liên quan đến các kỹ thuật định tuyến trong mạng MANET. Từ đó tác giả xác định vấn đề nghiên cứu và những đóng góp của luận án. 4
CHƯƠNG 2 ĐÁNH GIÁ CHẤT LƯỢNG TRUYỀN DẪN CỦA MẠNG MANET KHI SỬ DỤNG CÁC GIAO THỨC ĐỊNH TUYẾN THEO YÊU CẦU VÀ CÂN BẰNG TẢI 2.1. Các hiệu ứng vật lý xảy ra trên lộ trình truyền dữ liệu 2.1.1. Các yếu tố kỹ thuật liên quan Các hiệu ứng vật lý xảy ra các trên lộ trình phụ thuộc vào các giải pháp kỹ thuật được sử dụng tại lớp vật lý và lớp liên kết dữ liệu, cơ bản như các kỹ thuật điều chế tín hiệu, các chuẩn truyền thông không dây. 2.1.2. Suy hao công suất qua môi trường dẫn [20] 4πd 2 4π f d 2 c Lf = = (2.2) λ c trong đó, fc là tần số sóng mang, c là vận tốc của ánh sáng và d là khoảng cách. 2.1.3. Nhiễu tích lũy trên đường truyền Có bốn thành phần nhiễu phát sinh trong quá trình truyền dữ liệu. Đó là nhiễu nhiệt, nhiễu tạp âm, nhiễu xuyên âm và nhiễu xung [3]. Với MANET, thành phần nhiễu ảnh hưởng lớn nhất đến QoT là nhiễu nhiệt với công suất được xác định bởi: Pn = K × T × B (2.5) với K là hằng số Boltzmann, T là nhiệt độ và B là băng thông kênh. 2.2. Hiệu năng mạng MANET Theo nghĩa chung, hiệu năng mạng là hiệu quả, năng lực và chất lượng hoạt động của một hệ thống mạng. Đánh giá hiệu năng mạng là việc xác định các độ đo phản ánh hiệu quả, năng lực và chất lượng của một hệ thống mạng bằng các phương pháp mô phỏng, mô hình giải tích hoặc thực nghiệm. Trong MANET, các độ đo thường được sử dụng để đánh giá hiệu năng bao gồm xác suất chặn gói dữ liệu, thời gian trễ, thông lượng, tỷ lệ tín hiệu trên nhiễu và tỷ lệ bit lỗi. 2.2.1. Xác suất chặn gói dữ liệu (BPD) BPD = Nb /Ng (2.6) trong đó, Ng là tổng số gói dữ liệu phát sinh trên toàn mạng, Nb là tổng số gói dữ liệu bị chặn, bao gồm chặn do lưu lượng bị nghẽn và chặn do QoT không đảm bảo. 2.2.2. Thời gian trễ Thời gian trễ của một gói dữ liệu là tổng thời gian cần thiết để gói dữ liệu đó truyền thành công từ nguồn đến đích. 5
2.2.3. Tỷ lệ tín hiệu trên nhiễu (SNR) Trong MANET, SNR phụ thuộc vào dạng chuyển tiếp dữ liệu tại các nút. Có 2 dạng chuyển tiếp là khuếch đại và chuyển tiếp (AF) và giải mã và chuyển tiếp (DF). Từ đó, SNR tại đầu thu của một lộ trình được xác định bởi [9, 65]:    min(βh1 , βh2 , .., βhn−1 ) Nếu sử dụng DF (2.8)  !−1 βn = n−1 1    ∑ βh Ngược lại (2.20) i=1 i với βn là SNR tại nút đích và βhi là SNR của bước truyền thứ i. 2.2.4. Tỷ lệ lỗi bit (BER) BER được xác định bằng tổng số bit lỗi trên tổng số bit truyền. Sự phụ thuộc của BER theo SNR đối với các kỹ thuật điều chế được xác định theo [11]. 2.3. QoT của lộ trình khi sử dụng giao thức định tuyến theo yêu cầu 2.3.1. Nguyên lý cơ bản của các giao thức định tuyến theo yêu cầu Nguyên lý của giao thức định tuyến theo yêu cầu là các lộ trình sẽ được tạo ra khi có yêu cầu [3]. Khi một nút yêu cầu lộ trình mới để đến đích, nút đó phải khởi đầu một quá trình khám phá lộ trình. Quá trình này chỉ hoàn tất khi tìm ra một lộ trình hoặc tất cả các lộ trình khả thi đều đã được kiểm tra. Có hai giao thức định tuyến theo yêu cầu đang được nghiên cứu phổ biến, đó là DSR [22] và AODV [16]. 2.3.2. Chất lượng truyền dẫn của các lộ trình Node Next Hops Theo nguyên lý của các giao A A 1 Node Next Hops A B 2 B thức định tuyến theo yêu cầu, có Node Next Hops 24 D H E 3 một số trường hợp, lộ trình tìm 28 được không thỏa mãn ràng buộc A 32 Node Next Hops 35 A A 1 24 của QoT. Xét ví dụ ở Hình 2.16 với 29 H C 2 C giao thức AODV được sử dụng. Giả 31 E 32 28 Node Next Hops 29 sử A muốn khám phá lộ trình đến A H E H 2 1 H F 29 H. Theo nguyên lý của AODV, lộ 32 Node Next Hops Node Next Hops 32 trình được tìm thấy là A → E → C I A C 3 A A 1 G 31 → H. Giả sử nguyên lý hoạt động RREQ RREP Node Next Hops A E 2 Node A Next G Hops 3 của các nút là AF. Theo (??), SNR Hình 2.16. Một ví dụ khám phá lộ trình sử dụng của lộ trình A → E → C → H là giao thức định tuyến AODV 23.87 dB. Xét trường hợp SNR yêu cầu tối thiểu phải là 24 dB, lộ trình này không thỏa mãn ràng buộc của QoT. Với tôpô ở Hình 2.16, từ A đến H có thể sử dụng lộ trình 32 A32 → E → G → I → H. Mặc 32 32 6 10 32
dù số bước truyền là 4, nhưng SNR là 24.1 dB. Giá trị này thỏa mãn ràng buộc QoT, đồng thời tốt hơn lộ trình A → E → C → H mà giao thức AODV đã tìm thấy. 2.4. QoT của lộ trình khi sử dụng giao thức định tuyến cân bằng tải 2.4.1. Nguyên lý cơ bản của kỹ thuật định tuyến cân bằng tải Định tuyến cân bằng tải là kỹ thuật B định tuyến mà trong đó tiêu chí lựa chọn 24 D lộ trình là phân phối tải lưu lượng đồng đều 28 giữa tất cả các kết nối. A 32 35 24 2.4.2. QoT của các lộ trình 29 C 31 E 32 28 Xét một ví dụ khám phá lộ trình như 29 H ở Hình 2.17 với thuật toán định tuyến cân F 29 32 bằng tải FMLB [70] được sử dụng, K bằng 32 I G 31 3. Xét trường hợp A muốn truyền dữ liệu đến H. Theo nguyên lý khám phá lộ trình Gói RREQ được tiếp tục quảng bá Gói RREQ bị loại bỏ bằng cách phát quảng bá gói RREQ, 3 lộ Gói RREP phản hồi về nút nguồn trình khả dụng được tìm thấy là A → E → C → H, A → E → G → I → H và A → Hình 2.17. Một ví dụ về định tuyến cân bằng tải trong mạng MANET B → D → H. SNR của các lộ trình này lần lượt là 23.86, 24.04 và 20.2 dB. Như vậy, chỉ có lộ trình thứ hai thỏa mãn ràng buộc QoT. Trong khi đó, cả 3 lộ trình đều được sử dụng. Điều này dẫn đến các gói dữ liệu được truyền trên lộ trình thứ nhất và lộ trình thứ ba có QoT không đảm bảo. 2.5. Đánh giá QoT và hiệu năng mạng thông qua mô phỏng 2.5.1. Kịch bản mô phỏng Để đánh giá QoT của các lộ trình truyền dữ liệu và ảnh hưởng của nó đến hiệu năng mạng MANET, tác giả đã tiến hành mô phỏng trên OMNeT++ [10]. Bảng 2.5. Các tham số mô phỏng Tham số Thiết lập Tham số Thiết lập Vùng mô phỏng 1000 × 1000m Vùng phủ sóng 250 m Giao thức MAC 802.11ac Dạng điều chế 256-QAM Công suất phát 19.5 dBm Độ nhạy thu -68 dBm Ngưỡng BER 10−6 SNR yêu cầu 23.5 dB Mô hình nhiễu Nhiễu nhiệt Nhiệt độ 3000 K Tốc độ di chuyển 0 - 20 m/s Tổng số nút 10 - 50 2.5.2. Trường hợp sử dụng giao thức DSR Kết qủa ở Hình 2.19 cho ta thấy SNR tại đầu thu của nút đích. Có nhiều lộ trình mà SNR của nó không thỏa mãn điều kiện ràng buộc QoT (nhỏ hơn 23.5 dB). Đây là nguyên nhân làm tăng xác suất gói chặn gói dữ liệu do QoT không đảm bảo. 7
26.00 26.00 Giá trị yêu cầu DSR 25.00 25.00 SNR nhỏ nhất (dB) SNR nhỏ nhất (dB) 24.00 24.00 23.00 23.00 22.00 22.00 21.00 21.00 20 25 30 35 40 45 50 20 Tổng số nút mạng Hình 2.19. SNR của các lộ trình khi sử dụng Hình 2.21. SNR nhỏ nhất khi sử giao thức DSR dụng giao thức DSR Việc tồn tại nhiều lộ trình không thỏa mãn 0.06 BPD toàn phần 0.06 ràng buộc QoT đã làm tăng BPD như cho thấy 0.05 BPD do QoT 0.05 ở Hình 2.24. BPD do QoT không đảm bảo 0.04 0.04 chiếm gần 50% tổng số BPD toàn mạng. BPD BPD 0.03 0.03 2.5.3. Trường hợp sử dụng AODV 0.02 0.02 0.01 0.01 Với giao thức AODV, SNR trên các lộ trình như cho thấy ở Hình 2.29. Có nhiều lộ 0.00 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 0.00 0.6 trình mà SNR của nó không thỏa mãn ràng Tải lưu lượng (Erlang) buộc của QoT (nhỏ hơn 23.5 dB). Đây là Hình 2.24. BPD theo tải lưu lượng sử nguyên nhân làm tăng BPD, điều này thể hiện dụng giao thức DSR rõ trên Hình 2.31. 0.08 0.08 BPD toàn phần BPD toàn phần 0.07 0.07 BPD do QoT BPD do QoT 0.06 0.06 0.05 0.05 BPD 0.04 BPD 0.04 0.03 0.03 0.02 0.02 0.01 0.01 0.00 0.00 5 10 15 20 5 10 15 20 Tốc độ di chuyển (m/s) Tốc độ di chuyển (m/s) Hình 2.29. SNR của các lộ trình khi sử dụng Hình 2.31. BPD theo tốc độ di chuyển giao thức AODV của giao thức AODV 2.6. Kết luận chương Chương 2 đã trình bày các kết quả nghiên cứu về các hiệu ứng vật lý xảy ra trên lộ và ảnh hưởng của nó đến hiệu năng mạng MANET. Kết quả mô phỏng đã chứng minh rằng, ảnh hưởng của các hiệu ứng làm tăng BPD, dẫn đến suy giảm hiệu năng của hệ thống mạng. Vì vậy, việc nghiên cứu cải tiến các thuật toán định tuyến nhằm đảm bảo QoT, nâng cao hiệu năng mạng là điều cần thiết. 8
CHƯƠNG 3 ĐỊNH TUYẾN CÂN BẰNG TẢI ĐẢM BẢO CHẤT LƯỢNG TRUYỀN DẪN DỰA TRÊN TẢI LƯU LƯỢNG QUA MỖI LỘ TRÌNH 3.1. Đặt vấn đề Các kết quả nghiên cứu ở Chương 2 đã chứng minh rằng, định tuyến cân bằng tải cho phép giảm tình trạng nghẽn cục bộ nhờ tải lưu lượng phân phối đồng đều qua các kết nối. Tuy nhiên, nó cũng làm giảm QoT do các lộ trình có thể đi qua nhiều nút trung gian, nhiều bước truyền. Để đảm bảo QoT trong mạng, một số công trình nghiên cứu đã đề xuất các thuật toán định tuyến ràng buộc QoT với lựa chọn lộ trình có QoT tốt nhất để truyền dữ liệu [24, 46, 58, 5]. Tuy nhiên, với các mô hình mạng có tô-pô mắt lưới như MANET, định tuyến theo QoT tốt nhất có thể làm tăng tình trạng nghẽn cục bộ do tải lưu lượng phân bố không đều trong mạng. Như vậy, một vấn đề đặt ra là làm thế nào để kết hợp hài hòa giữa định tuyến QoT và định tuyến cân bằng tải, để tìm ra tập lộ trình mà tải lưu lượng phân phối đồng đều, đồng thời thỏa mãn các điều kiện ràng buộc của QoT như minh họa ở Hình 3.2. Với ý tưởng này, tác giả đề xuất một thuật toán định tuyến cân bằng tải, đồng thời đảm bảo QoT của các lộ trình truyền dữ liệu. Lộ trình cân bằng tải được lựa chọn dựa trên thông tin về xác suất chặn gói dữ liệu từ nguồn đến đích. Thuật toán đề xuất được đặt tên LBRQT (Load Balancing Routing ensuring QoT). Định tuyến Tải lưu lượng “đường ngắn nhất” phân bố không Nghẽn cục bộ hoặc QoT tốt nhất đồng đều Định tuyến cân bằng ràng buộc QoT Định tuyến cân Tồn tại các QoT suy giảm bằng tải “lộ trình dài” Hình 3.2. Mô hình đề xuất ý tưởng định tuyến cân bằng ràng buộc QoT 3.2. Cơ sở lý thuyết liên quan 3.2.1. Phân tích xác suất hủy bỏ gói dữ liệu sử dụng lý thuyết hàng đợi Xét một bước truyền hi j , trong trường hợp lưu lượng phân phối đến hi j theo quy trình Poisson, thời gian truyền gói trên hi j theo phân phối hàm mũ, khi đó hi j tương đương với hàng đợi M/M/1/L [6, 63]. Bằng cách giải phương trình cân bằng trạng thái, ta xác định được BPD trên hi j như sau:  L  ρi j (1 − ρi j ) nếu ρi j 6= 1  (h) Bi j = 1 − ρiL+1 j (3.4)  1  nếu ρi j = 1 L+1 9
với λi j và µi j là tốc độ đến và tốc độ phục vụ các gói dữ liệu, ρi j = λi j /µi j là mật (r) độ lưu lượng phân phối đến hi j . Gọi Bsd là BPD trên lộ trình rsd . Khi đó: (r) (h) Bsd = 1 − ∏ (1 − Bi j ) (3.7) ∀hi j ∈rsd 3.2.2. Phân tích thời gian trễ dựa trên lý thuyết hàng đợi Thời gian trễ từ nguồn đến đích (EED) của một lộ trình được xác định bởi: (r) (h) τsd = ∑ τi j (3.9) ∀hi j ∈rsd (h) (i) trong đó, τi j là thời gian trễ trên hi j , gồm 4 thành phần: trễ xử lý tại I (τ p ), trễ (i) (i j) hàng đợi tại I (τq ), trễ truyền dẫn từ I đến J (τt ) và trể truyền tải qua môi trường (i j) (i) (i j) (i j) vô tuyến từ I đến J (τr ) [18]. Vì τp và τr rất nhỏ nên có thể bỏ qua, τt được (i) xác định dựa trên băng thông kênh và kích thước gói dữ liệu, được xác định τq dựa trên cơ chế hàng đợi được sử dụng tại mỗi nút. Như đã phân tích ở Phần ??, cơ (i) chế hàng đợi M/M/1/L được sử dụng, do vậy, τq được xác định bởi [19]: (i) L 1 τq = (h) + (3.11) λi j (1 − Bi j ) µi j với L là tổng số gói dữ liệu trung bình trong hàng đợi, được xác theo [19]. 3.3. Ý tưởng đề xuất giải pháp 3.3.1. Mô hình giải tích của giải pháp Ý tưởng đề xuất thuật toán LBRQT là kết hợp kỹ thuật định tuyến cân bằng tải và định tuyến ràng buộc QoT. Để thực hiện điều này, hàm mục tiêu được xây dựng là cực tiểu hóa BPD trên mỗi lộ trình. Các điều kiện ràng buộc được xác định là QoT và EED phải nằm trong giới hạn cho phép. Để phát biểu thuật toán định tuyến LBRQT thành mô hình giải tích, tác giả (sd) định nghĩa một ma trận Xsd = xi j n×n biểu diễn các kết nối được chọn cho lộ (sd) trình rsd , trong đó, mỗi phần tử xi j được xác định bởi: ( (sd) 1 Nếu lộ trình rsd đi qua kết nối ci j xi j = (3.12) 0 Ngược lại (sd) khi đó, phương trình (3.7) được biểu diễn theo xi j như sau: n n (r) (sd) (h) Bsd = 1 − ∏ ∏ (1 − xi j Bi j ) (3.13) i=1 j=1 10
Khi đó, thuật toán LBRQT được mô hình hóa thành bài toán quy hoạch phi tuyến: (r) Miniminze (Bsd ) (3.19) với các điều kiện ràng buộc:  −1  Nếu j = s (sd) (sd) ∑ xi j − ∑ x jk =  1 Nếu j = d (3.20) i∈N k∈N  0 Ngược lại N N (sd) (h) ∑∑ xi j τi j ≤ τth (3.21) i=1 j=1  N N 1 1 ≤  ∑ ∑   (h) (sd) Nếu sử dụng AF i=1 j=1 βi j xi j  βreq (3.22) (h)  min ≥ βreq Ngược lại   β x(sd) =1 i j   ij (sd) (sd) (xi j − 1)xi j =0 (3.23) Phương trình (3.20) là ràng buộc luồng dữ liệu, (3.21) là ràng buộc về độ trễ, (3.22) là ràng buộc QoT và (3.23) là ràng buộc nhị phân. 3.3.2. Ý tưởng thực thi thuật toán trên mô hình xuyên lớp 3.3.2.1. Cải tiến cấu trúc nút mạng sử dụng mô hình xuyên lớp Để có thể sử dụng các thông tin Lớp truyền tải về QoT làm điều kiện ràng buộc định Cập nhật cơ sở Dự đoán QoT, tuyến, lớp mạng phải truy cập trực dữ liệu mật độ EED và BPD lưu lượng tiếp được các thông tin từ lớp vật lý. Lớp mạng Điều này chỉ có thể thực hiện thông qua mô hình xuyên lớp [5, 26, 2]. Lớp liên kết dữ liệu Với thuật toán LBRQT, tác giả đề SA Data xuất một mô hình xuyên lớp với cấu Lớp vật lý RREQ trúc như ở Hình 3.6, trong đó, một Nút mạng MANET tác tử tĩnh (Stationary Agent - SA) được sử dụng để trao đổi và xử lý Hình 3.6. Cấu trúc mô hình xuyên lớp sử dụng thông tin xuyên lớp giữa lớp vật lý tác tử cho mạng MANET và lớp mạng. Trong quá trình truyền dữ liệu, nhiệm vụ của SA là cập nhật tải lưu lượng phân phối cho các kết nối. Trong quá trình khám phá lộ trình, SA thu thập, xử lý và dự đoán các thông tin về QoT, EED và BPD để chuyển cho lớp mạng. Các thông tin về QoT và EED được sử dụng 11
cho các ràng buộc định tuyến theo (3.21) và (3.22). Thông tin về BPD sử dụng cho nút nguồn làm tiêu chí lựa chọn lộ trình cân bằng tải theo hàm mục tiêu (3.19). 3.3.2.2. Cải tiến cơ chế xử lý gói RREQ và RREP tại mỗi nút mạng (i) Trường hợp RC của nút trung gian không có lộ trình đến nút đích Ý tưởng này được minh họa S SA tại I dự đoán trước QoT, EED và K như Hình 3.7. Khi nút I nhận được BPD từ S đến mỗi nút láng giềng của I một gói RREQ của yêu cầu khám phá lộ trình từ S đến D, SA tại I dự RREQ RREQ L … I . đoán các độ đo QoT và EED từ S . . Data Packet . . . đến mỗi nút láng giềng của I. Từ RREQ M SA tại I thống kê lưu lượng phân phối đó, SA xác định tập Qi là tập các đến kết nối từ I đến nút tiếp theo nút láng giềng của I thỏa mãn điều Tập tất cả các nút láng giềng của I P kiện ràng buộc QoT. Sau đó, I chỉ Tập các nút láng giềng của I thỏa mãn ràng buộc QoT và EED (Tập Q )i phát quảng bá gói RREQ đến các nút thuộc tập Qi . Ngoài ra, sau khi Hình 3.7. Nguyên lý chuyển tiếp gói RREQ khi RC của nút I không có lộ trình đến đích xác định được tập Qi , SA tại I cũng dự đoán BPD từ S đến mỗi nút thuộc tập Qi . Thông tin BPD này được sử dụng cho nút nguồn lựa chọn lộ trình cân bằng tải. Tập Qi được xác định bởi Thuật toán 3.1. Thuật toán 3.1: Xác định các nút láng giềng của I thỏa mãn ràng buộc QoT (Tập Qi ) (r) (r) (1) Đọc thông tin QoT và EED từ S đến I (βsi và τsi ) trong gói RREQ; (2) Qi ← 0/ ; (3) for (Mỗi nút J là láng giềng của I) do (h) (4) Thu thập thông tin SNR từ I đến J (βi j ) tại lớp vật lý; (h) (5) Dự đoán thời gian trể từ I đến J (τi j ) theo (3.9); (r) (r) (h) (6) τs j ← τsi + τi j ; (7) if (Nguyên lý hoạt động của các nút mạng là DF) then (r) (r) (h) (8) βs j ← min(βsi , βi j ); (9) else (h) −1 (r) (r) (10) βs j ← 1/βsi + 1/βi j ; (11) end (h) (h) (12) if ((τs j ≤ τth ) and (βs j ≥ βreq )) then (r) (13) Đọc thông tin BPD từ S đến I (Bsi ) trong gói RREQ; (h) (14) Dự đoán BPD trên bước truyền từ I đến J (Bi j ) theo (3.7); (r) (r) (h) (15) Bs j = 1 − (1 − Bsi )(1 − Bi j ); Qi ← Qi ∪ J; (16) end (17) end 12
(ii) Trường hợp RC của nút trung gian có lộ trình khả dụng đến nút đích Hình 3.8 minh họa ý tưởng cải tiến QoT và EED từ S đến D QoT và EED từ S đến D thỏa mãn điều kiện ràng không thỏa mãn điều kiện cơ chế xử lý gói RREQ tại mỗi nút khi S buộc cho trước ràng buộc cho trước D RC của nút trung gian có lộ trình khả dụng đến nút đích. Giả sử nút đang xét RREQ …. là nút I, trong trường hợp này, nút I …. RREP I RREQ RREQ không tạo ngay gói RREP và phản hồi L RREQ SA tại I dự đoán trước QoT, EED và BPD từ S về S như giao thức định tuyến theo yêu đến D dọc theo lộ trình S  I nối với I  D M cầu. Thay vào đó, SA tại I dự đoán QoT và EED từ S đến D theo lộ trình S → Hình 3.8. Xử lý gói RREQ khi nút trung gian I nối với I → D. Nếu QoT và EED dự có lộ trình đến đích đoán được thỏa mãn ràng buộc cho trước, gói RREP mới được tạo và gửi phản hồi về nút nguồn. Ngược lại, nút I xử lý gói RREQ như trường hợp (i). Thuật toán 3.2: Dự đoán QoT và BPD bởi SA khi RC của I có lộ trình đến D. (r) (r) (1) Đọc thông tin QoT và EED từ S đến I (βsi và τsi ) trong gói RREQ; (r) (r) (2) Đọc thông tin QoT và EED từ I đến D (βid và τid ) trong RC của I; (r) (r) (r) (3) τsd ← τsi + τid ; (4) if (Nguyên lý hoạt động của các nút mạng là DF) then (r) (r) (r) (5) βsd ← min(βsi , βid ); (6) else (r) −1 (r) (r) (7) βsd ← 1/βsi + 1/βid ; (8) end (h) (h) (9) if ((τs j ≤ τth ) and (βs j ≥ βreq )) then (r) (10) Đọc thông tin BPD từ S đến I (Bsi ) trong gói RREQ; (r) (11) Đọc thông tin BPD từ I đến D (Bid ) trong RC của I; (r) (r) (r) (r) (12) Bsd = 1 − (1 − Bsi )(1 − Bid ); Tạo gói RREP, lưu Bsd vào gói RREP; (13) else (14) Tìm tập Qi theo Thuật toán 3.1; (15) end 3.3.2.3. Cải tiến cơ chế lựa chọn lộ trình tại nút nguồn Với cơ chế xử lý gói RREQ và RREP được cải tiến ở Phần 3.3.2.2, khi một lộ trình được tìm thấy thì lộ trình này luôn thỏa mãn ràng buộc của QoT. Vấn đề còn lại của thuật toán LBRQT là chọn lộ trình cân bằng tải. Điều này được thực hiện tại nút nguồn. Theo nguyên lý của thuật toán LBRQT, tiêu chí để lựa chọn lộ trình là cực tiểu hóa BPD theo hàm mục tiêu (3.19). Vì vậy, khi nhận được gói RREP, nút nguồn lựa chọn lộ trình có giá trị BPD trong gói RREP nhỏ nhất. 13
3.4. Nguyên lý hoạt động của thuật toán LBRQT Nút nguồn Nút trung gian Nút đích S tạo gói Xác định tập Với mỗi nút J  Qi Bắt đầu I=S Qi theo Thuật RREQ toán 3.1 I=J Sai Qi  Đúng Đúng I là nút đích (D) I phát quảng bá gói RREQ đến tất cả Sai các nút J  Qi Loại Sai I chưa nhận D Tạo gói bỏ gói gói RREQ này RREP NRREP = 0; RREQ Twait = 0; Đúng Sai RC của I có lộ Đúng Tăng Twait theo Gửi gói đồng hồ thời gian trình đến D RREP về S Từ chối yêu cầu do không tìm được lộ trình Xác định tập Qi Dự đoán các độ đo Sai theo Thuật QoT và hiệu năng Đúng (NRREP = K) OR Sai toán 3.1 theo Thuật toán 3.2 NRREP > 0 (Twait > Timeout) Đúng Sai Sai S chọn lộ trình có Qi  Gói RREP BPD nhỏ nhất Đúng được tạo NRREP = NRREP + 1 I phát quảng bá gói Đúng RREQ đến tất cả Gửi gói Kết thúc S nhận gói RREP các nút J  Qi RREQ về S Hình 3.9. Lưu đồ thuật toán định tuyến LBRQT 3.5. Áp dụng cho giao thức AODV 3.5.1. Đặt vấn đề Kết quả nghiên cứu ở Chương 2 đã cho thấy rằng, với nguyên lý khám phá lộ trình của giao thức AODV, tồn tại một số trường hợp mà lộ trình tìm được không không thỏa mãn ràng buộc QoT. Để giải quyết vấn đề này, tác giả áp dụng giải thuật toán LBRQT để cải tiến cơ chế khám phá lộ trình của giao thức AODV [16], nhằm tìm ra lộ trình cân bằng tải, đồng thời thỏa mãn ràng buộc QoT. Thuật toán cải tiến được đặt tên LBRQT-AODV. Đề xuất này của tác giả đã được công bố trong [B2]1 . 3.5.2. Chỉnh sửa khuôn dạng gói RREQ và RREP 32 bits 32 bits (1) (2) (3) (4) (5) (6) (7) (8) (9) Type J R G D U Reversed CF Hop Count (1) (2) (3) (4) (5) (6) (10) RREQ ID Type J R Reversed Prefix Hop Count (a) (11) Destination IP Address (b) (7) Destination IP Address (12) Destination Sequence Number (8) Destination Sequence Number (13) Source IP Address (9) Originator IP Address (14) Source Sequence Number (10) Lifetime Reversed (15) BP (16) QoT (17) EED Reversed (11) BP Hình 3.11. Các gói (a) RREQ và (b) RREP trong thuật toán LBRQT-AODV 1 Journal of Communications, Vol.13, No.7, 2018, pp. 338-349 (SCOPUS). 14
3.5.3. Thuật toán định tuyến LBRQT-AODV Thuật toán 3.3: Thuật toán định tuyến LBRQT-AODV tại nút nguồn (1) S tạo gói RREQ; (2) SA xác định tập Qs theo Thuật toán 3.1; (3) if (Qi 6= 0) / then (4) Phát gói quảng bá gói RREQ đến các nút thuộc tập Qs ; (5) Chờ đến khi nhận được K gói RREP hoặc hết thời gian chờ cho phép; (6) if (Số gói RREP nhận được > 0) then (7) Chọn lộ trình có giá trị trong trường BP của gói RREP nhỏ nhất để cập nhật vào RC của S; (8) else (9) Từ chối yêu cầu khám phá lộ trình; (10) end (11) else (12) Từ chối yêu cầu khám phá lộ trình; (13) end Thuật toán 3.4: Thuật toán LBQT-AODV tại nút trung gian hoặc nút đích (1) Nút I nhận gói RREQ; (2) if (I là nút trung gian) then (3) if (I chưa nhận gói RREQ này trước đó) then (4) Cập nhật đường ngược về S vào RC của I; (5) if (RC của I không có lộ trình khả dụng đến D) then (6) SA xác định tập Qi theo Thuật toán 3.1; (7) if (Qi 6= 0) / then (8) Phát quảng bá gói RREQ đến các nút thuộc tập Qs ; (9) else (10) Loại bỏ gói RREQ, kết thúc xử lý gói RREQ vừa nhận; (11) end (12) else (13) if (DSN của lộ trình I → D lớn hơn DSN trong gói RREQ) then (14) SA dự đoán QoT, EED và BPD theo lộ trình S → I nối với I → D theo Thuật toán 3.2; (15) if (Gói RREP được tạo) then (16) Gửi gói RREP về S theo đường ngược; (17) else (18) Thực hiện các bước 6 đến 11; (19) end (20) else (21) Thực hiện các bước 6 đến 11; (22) end (23) end (24) else (25) Loại bỏ gói RREQ, kết thúc tiến trình xử lý gói RREQ vừa nhận; (26) end (27) else (28) Cập nhật đường ngược về S vào RC của I; (29) Tạo gói RREP, gửi gói RREP về S theo đường ngược; (30) end 15
3.6. Áp dụng cho giao thức DSR 3.6.1. Đặt vấn đề Theo kết quả nghiên cứu ở Chương 2, việc khám phá lộ trình theo giao thức DSR sẽ tồn tại một số trường hợp lộ trình tìm được không đảm bảo QoT. Để giải quyết vấn đề này, tác giả áp dụng thuật toán LBRQT để cải tiến cơ chế khám phá lộ trình của giao thức DSR. Thuật toán cải tiến được đặt tên là LBRQT-DSR. 3.6.2. Chỉnh sửa khuôn dạng gói RREQ và RREP Gói RREQ và RREP của thuật toán LBRQT-DSR được chỉnh sửa ở Hình 3.12. 3.6.3. Thuật toán định tuyến LBRQT-DSR Thuật toán 3.5: Thuật toán LBRQT-DSR (1) S tạo gói RREQ; I ← S; NRREP = 0; (2) repeat (3) Xác định tập Qi theo Thuật toán 3.1 (Chương 2); (4) Phát gói quảng bá gói RREQ đến các nút J thuộc tập Qi ; (5) if (Trước đó J chưa nhận gói RREQ này) then (6) Thêm một bản ghi vào RC của J chứa lộ trình ngược về S; (7) if (J chưa phải là nút đích (nút D)) then (8) if (RC của J không có lộ trình đến D) then (9) Cập nhật đường ngược về S vào RC của J; (10) Cập nhật lộ trình từ S đến J trong gói RREQ; (11) I ← J; (12) else (13) SA tại J dự đoán QoT, EED và BPD theo lộ trình S → I nối với I → D theo Thuật toán 3.2 (Chương 2); (14) if (Gói RREP được tạo) then (15) Nối lộ trình S → J với lộ trình J → D; (16) NRREP ← NRREP + 1; Gửi RREP về S theo đường ngược; (17) else (18) Cập nhật đường ngược về S trong RC của J; (19) Cập nhật lộ trình từ S đến J trong gói RREQ; (20) I ← J; (21) end (22) end (23) else (24) Tạo gói RREP; Cập nhật lộ trình S → D vào gói RREP; (25) NRREP ← NRREP + 1; Gửi gói RREP về S theo đường ngược; (26) end (27) else (28) Xóa gói RREQ; Kết thúc tiến trình xử lý gói RREQ vừa nhận; (29) end (30) until (NRREP = K) or (Quá thời gian chờ); (31) if (NRREP > 0) then (32) Nút S chọn một lộ trình có giá trị BPD trong gói RREP nhỏ nhất; (33) else (34) Từ chối yêu cầu khám phá lộ trình mới từ S đến D; (35) end 16
Opt. type (*) Opt. Data Length (*) Identification (*) Opt. type (*) Opt. Data Len (*) Last Hop Ext. (*) Reserved (*) Target Address (*) Address [1] (*) Address [1] (*) Address [2] (*) (a) Address [2] (*) (b) Address [3] (*) … (*) … (*) Address [n] (*) Address [n] (*) Reserved BP (**) QoT (**) E2E (**) Reserved BP (**) Hình 3.12. Các gói (a) RREQ và (b) RRREP trong thuật toán LBRQT-DSR 3.7. Mô phỏng và phân tích kết quả 3.7.1. Xây dựng kịch bản mô phỏng Thuật toán LBRQT-AODV và LBRQT-DSR được đánh giá bằng mô phỏng trên OMNeT++ [10], so sánh với các thuật toán AODV [16], DSR [22] và DSR- SNR trong [24]. Kịch bản mô phỏng được thiết lập như Phần 2.5.1, chương 2. 3.7.2. Kết quả mô phỏng thuật toán LBRQT-AODV Hình 3.13 so sánh SNR trên các lộ trình khi sử dụng thuật toán AODV và LBRQT- AODV trong trường hợp tô-pô 50 nút, tốc độ di chuyển trung bình là 10 m/s. Ta thấy rằng, có nhiều lộ trình không thỏa Hình 3.13. So sánh SNR của thuật toán (a) AODV và mãn ràng buộc QoT. Với thuật (b) LBRQT-AODV toán LBRQT-AODV, SNR đã 0.05 AODV LBRQT-AODV được cải thiện. Hầu hết SNR 0.04 lớn hơn ngưỡng yêu cầu tối thiểu (23.5 dB). 0.03 BPD 0.02 Vì SNR của thuật toán LBRQT-AODV 0.01 được cải thiện, nên BPD giảm như cho thấy trên 0.00 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Hình 3.17. Kết quả này được mô phỏng trên tô- Tải lưu lượng (Erlang) pô 40 nút, tốc độ di chuyển trung bình của mỗi Hình 3.17. So sánh BPD của thuật nút là 5 m/s. Khi tải lưu lượng là 0.6 Erlang, toán AODV và LBRQT-AODV BPD của thuật toán AODV là 0.0136. Trong khi 76E+6 đó, giá trị này của thuật toán LBRQT-AODV chỉ 74E+6 72E+6 Thông lượng (bit/s) là 0.0091. Như vậy, BPD của LBRQT-AODV 70E+6 giảm 33.21% so với AODV. 68E+6 66E+6 Về mặt thông lượng, thuật toán LBRQT- 64E+6 LBRQT-AODV AODV 62E+6 AODV cũng mang lại hiệu quả cao hơn thuật 0 50 100 150 200 250 300 Thời gian mô phỏng (s) 350 400 450 toán AODV. Điều này được thể hiện rõ trên Hình Hình 3.18. Thông lượng của thuật 3.18, tương ứng với trường hợp tổng số nút là toán AODV và LBRQT-AODV 17
40, tốc độ di chuyển 5 m/s. Thông lượng trung bình của các thuật toán AODV và LBRQT-AODV tương ứng là 69.85 và 71.55 Mbit/s. Như vậy, so với thuật toán AODV, thông lượng của thuật toán LBRQT-AODV tăng 1.7 Mbit/s. 3.7.3. Kết quả mô phỏng thuật toán LBRQT-DSR Hình 3.20 cho thấy SNR nhỏ nhất của các 26.00 lộ trình trong toàn mạng. Với thuật toán DSR, Giá trị yêu cầu DSR SNR lớn hơn SNR yêu cầu khi tổng số nút mạng 25.00 LBRQT-DSR SNR nhỏ nhất (dB) nhỏ hơn 30. Tuy nhiên, nếu tổng số nút mạng lớn 24.00 hơn 30 thì SNR nhỏ hơn SNR yêu cầu. Với thuật 23.00 toán LBRQT-DSR, SNR đã được cải thiện, luôn 22.00 lớn hơn SNR yêu cầu dù tổng số nút mạng lớn. Về BPD, khi sử dụng thuật toán LBRQT-DSR, 21.00 20 25 30 35 40 45 50 BPD cũng được cải thiện so với thuật toán DSR Tổng số nút mạng (Hình 3.23). BPD của thuật toán LBRQT-DSR Hình 3.20. SNR nhỏ nhất của các giảm trung bình 51.79% so với DSR. thuật toán LBRQT-DSR và DSR 0.07 72E+6 Về mặt thông lượng, DSR 0.06 LBRQT-DSR 70E+6 thuật toán LBRQT-DSR 0.05 68E+6 Thông lượng (bit/s) luôn đạt được thông 0.04 BPD 66E+6 lượng cao hơn thuật 0.03 toán DSR (Hình 3.26). 0.02 64E+6 thuật toán LBRQT-DSR 0.01 62E+6 LBRQT-DSR DSR mang lại thông lượng 0.00 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 60E+6 0 50 100 150 200 250 300 cao hơn thuật toán DSR Tải lưu lượng (Erlang) Thời gian mô phỏng (s) trung bình 2.99 Mbit/s. Hình 3.23. BPD của thuật Hình 3.26. Thông lượng của toán LBRQT-DSR và DSR thuật toán LBRQT-DSR và DSR 3.8. Kết luận chương Chương 3 đã trình bày thuật toán định tuyến cân bằng tải đảm bảo chất lượng truyền dẫn (LBRQT), được đề xuất cho mạng MANET. Thuật toán LBRQT cho phép tìm được lộ trình thỏa mãn ràng buộc QoT, đồng thời cân bằng tải lưu lượng trên tất cả các kết nối trong mạng. Thuật toán LBRQT đã được áp dụng để cải tiến các giao thức định tuyến AODV (LBRQT-AODV) và DSR (LBRQT-DSR). Kết quả mô phỏng trên OMNeT++ đã cho thấy rằng, các thuật toán LBRQT-AODV và LBRQT-DSR đã tìm được các lộ trình thỏa mãn ràng buộc của QoT, nên QoT trên các lộ trình truyền dữ liệu luôn đảm bảo. Ngoài ra, các lộ trình cũng được chọn theo tiêu chí cân bằng tải. Vì vậy, giảm thiểu tình trạng nghẽn cục bộ trong mạng. Vì vậy, hiệu năng mạng được cải thiện so với các thuật toán DSR và AODV, đặc biệt là trong trường hợp hệ thống mạng có vùng diện tích rộng, mật độ nút cao. 18