Nâng cao hiệu năng mang 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

Nội dung tài liệu: Nâng cao hiệu năng mang 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

1. 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
2. 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 i
3. 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
4. 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ương1 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ương2 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ương3 đề 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ương4 đề 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
5. 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
6. 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
7. 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]  4pd 2  4p f d 2 L = = c (2.2) f l 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
8. 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]: 8 min(bh ;bh ;::;bh ) Nếu sử dụng DF(2.8) > 1 2 n−1 ∑ Ngược lại(2.20) : i=1 bhi với bn là SNR tại nút đích và bhi 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 A A 1 Node Next Hops Theo nguyên lý của các giao A B 2 B 24 thức định tuyến theo yêu cầu, có Node Next Hops D một số trường hợp, lộ trình tìm H E 3 28 A 32 35 được không thỏa mãn ràng buộc Node Next Hops A A 1 24 H C 2 của QoT. Xét ví dụ ở Hình 2.16 với 29 C 31 giao thức AODV được sử dụng. Giả E 2832 Node Next Hops 29 sử A muốn khám phá lộ trình đến A E 2 H 29 H H 1 F 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 RREQ Node Next Hops ! H. Giả sử nguyên lý hoạt động Node Next Hops RREP A E 2 A G 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ình32 A ! E ! G ! I ! H. Mặc 32 32 32 6 10 32
9. 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 A 32 35 giữa tất cả các kết nối. 24 2.4.2. QoT của các lộ trình 29 C 31 E 2832 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 29 F 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 độ 3000K 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
10. 26.00 26.00 Giá trị yêu cầu Giá trị yêu cầu DSR DSR 25.00 25.00 QTA-DSR 24.00 24.00 23.00 23.00 SNR nhỏ nhất (dB) SNR nhỏ nhất (dB) 22.00 22.00 21.00 21.00 20 25 30 35 40 45 50 20 25 30 35 40 45 50 Tổng số nút mạng 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 0.06 BPD toàn phần BPD toàn phần ràng buộc QoT đã làm tăng BPD như cho thấy 0.05 BPD do QoT 0.05 BPD do QoT ở 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. 0.03 0.03 BPD BPD 2.5.3. Trường hợp sử dụng AODV 0.02 0.02 Với giao thức AODV, SNR trên các lộ 0.01 0.01 trình như cho thấy ở Hình 2.29. Có nhiều lộ 0.00 0.00 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 trình mà SNR của nó không thỏa mãn ràng Tải lưu lượng (Erlang) 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 0.04 0.04 BPD BPD 0.03 0.03 0.02 0.02 0.01 0.01 0.00 0.00 51015205101520 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ương2 đã 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
11. 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: 8 L ri j(1 − ri j) 1 = L + 1 nếu ri j 1 9
12. với li j và mi j là tốc độ đến và tốc độ phục vụ các gói dữ liệu, ri j = li j=mi 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) 8hi j2rsd 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) tsd = ∑ ti j (3.9) 8hi j2rsd (h) (i) trong đó, ti j là thời gian trễ trên hi j, gồm 4 thành phần: trễ xử lý tại I (tp ), trễ (i) (i j) hàng đợi tại I (tq ), trễ truyền dẫn từ I đến J (tt ) 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 (tr )[18]. Vì tp và tr rất nhỏ nên có thể bỏ qua, tt đượ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, tq được xác định 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, tq được xác định bởi [19]: L 1 (i) = + (3.11) tq (h) mi j li j(1 − Bi 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
13. 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: 8 >−1 Nếu j = s (sd) (sd) 0 Ngược lại N N (sd) (h)
    ∑ ∑ xi j ti j ≤ tth (3.21) i=1 j=1 8 N N  1  1 > ≤ Nếu sử dụng AF >∑ ∑ (h) (sd) > breq (h) > min bi j ≥ breq Ngược lại > (sd) :xi j =1 (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 EED và BPD dữ liệu mật độ 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 xuất một mô hình xuyên lớp với cấu Data 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
14. 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 L RREQ 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 phát quảng bá gói RREQ đến các buộc QoT và EED (Tập Qi) Hình 3.7. Nguyên lý chuyển tiếp gói RREQ khi nút thuộc tập Qi. Ngoài ra, sau 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 (bsi và tsi ) 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 (bi j ) tại lớp vật lý; (h) (5) Dự đoán thời gian trể từ I đến J (ti j ) theo (3.9); (r) (r) (h) (6) ts j tsi + ti j ; (7) if (Nguyên lý hoạt động của các nút mạng là DF) then (r) (r) (h) (8) bs j min(bsi ;bi j ); (9) else (r)  (r) (h)−1 (10) bs j 1=bsi + 1=bi j ; (11) end (h) (h) (12) if ((ts j ≤ tth) and (bs j ≥ breq)) 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
15. (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 D buộc cho trước ràng buộc cho trước 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 . . RREP I là nút I, trong trường hợp này, nút 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 (bsi và tsi ) trong gói RREQ; (r) (r) (2) Đọc thông tin QoT và EED từ I đến D (bid và tid ) trong RC của I; (r) (r) (r) (3) tsd tsi + tid ; (4) if (Nguyên lý hoạt động của các nút mạng là DF) then (r) (r) (r) (5) bsd min(bsi ;bid ); (6) else (r)  (r) (r)−1 (7) bsd 1=bsi + 1=bid ; (8) end (h) (h) (9) if ((ts j ≤ tth) and (bs j ≥ breq)) 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
16. 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 RREQ Qi theo Thuật 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 RREQ NRREP = 0; Twait = 0; Đúng Sai Đúng Tăng T theo RC của I có lộ Gửi gói wait đồ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 theo Thuật QoT và hiệu năng Sai Đúng (N = K) OR Sai toán 3.1 theo Thuật toán 3.2 RREP NRREP > 0 (T > Timeout) wait Đúng Sai Sai Gói RREP S chọn lộ trình có Qi  được tạo BPD nhỏ nhất Đúng 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 Q i 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ương2 đã 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 1Journal of Communications, Vol.13, No.7, 2018, pp. 338-349 (SCOPUS). 14
17. 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ước6 đến 11; (19) end (20) else (21) Thực hiện các bước6 đế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
18. 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ương2, 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ương2); (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ương2); (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
19. 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ương2. 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 0.05 toán LBRQT-AODV, SNR đã 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 là 0.0091. Như vậy, BPD của LBRQT-AODV 70E+6 giảm 33.21% so với AODV. 68E+6 Thông lượng (bit/s) 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 350 400 450 Thời gian mô phỏng (s) 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
20. 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 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 SNR nhỏ nhất (dB) lớn hơn SNR yêu cầu dù tổng số nút mạng lớn. 22.00 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 thuật toán LBRQT-DSR LBRQT-DSR 70E+6 0.05 luôn đạt được thông 68E+6 0.04 66E+6 lượng cao hơn thuật BPD 0.03 64E+6 toán DSR (Hình 3.26). 0.02 Thông lượng (bit/s) 0.01 62E+6 thuật toán LBRQT-DSR LBRQT-DSR 0.00 DSR 60E+6 mang lại thông lượng 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 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 3.8. Kết luận chương toán LBRQT-DSR và DSR thuật toán LBRQT-DSR và DSR Chương3 đã 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
21. CHƯƠNG 4 ĐỊ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 Nội dung chương này trình thuật toán định tuyến cân bằng tải đảm bảo QoT được đề xuất cho mạng MANET. Lộ trình cân bằng tải được chọn dựa trên thông tin định tuyến được lưu trữ trong bộ nhớ của nút nguồn. Thuật toán đề xuất được đặt tên là SLBQT-DSR (Source-based Load Balancing ensuring QoT based on DSR). 4.1. Ý tưởng đề xuất thuật toán 4.1.1. Chọn lộ trình cân bằng tải Đặc trưng cơ bản của giao thức định tuyến DSR là RC của mỗi nút lưu trữ đầy đủ thông tin lộ trình từ nguồn đến đích. Vì vậy, mỗi nút mạng có thể xác định được tải lưu lượng từ nó phân phối đến tất cả các kết nối trong mạng dựa trên thông tin lộ trình trong RC của nó. Vì vậy, khi nhận được các gói RREP, dựa trên thông tin định tuyến trong RC ở thời điểm đang xét, nút nguồn có thể lựa chọn lộ trình sao cho tải lưu lượng phân phối đến tất cả các kết nối là cân bằng nhất. Đây chính là ý tưởng lựa chọn lộ trình cân bằng tải của thuật toán định tuyến SLBQT-DSR. 4.1.2. Xác định điều kiện ràng buộc QoT Để đảm bảo QoT của các Dự đoán SNR và EED lộ trình tìm được bởi thuật từ S mỗi nút J NI toán định tuyến SLBQT-DSR, N các điều kiện ràng buộc về S QoT phải được xác định trong RC của I không có lộ trình đến D L quá trình khám phá lộ trình. Ý RREQ A I M tưởng xác định các điều kiện ràng buộc của QoT trong thuật RC của nút I có lộ trình đến D toán SLBQT-DSR được minh K Tập Q họa như ở Hình 4.1. Khi một I Tập NI D Dự đoán SNR và EED từ S đến D nút trung gian (nút I) nhận theo lộ trình S I nối với I D được một gói RREQ về yêu cầu khám phá lộ trình mới từ Hình 4.1. Mô hình xác định điều kiện ràng buộc QoT nút nguồn (S) đến nút đích của thuật toán SLBQT-DSR (D). Trong trường hợp thông tin định tuyến trong bộ nhớ của I không có lộ trình đến D, SA tại I dự đoán các thông tin về QoT từ S đến tất cả các nút láng giềng của I (các nút trong tập NI ). Sau đó, gói RREQ chỉ được phát quảng bá đến các nút láng giềng của I thỏa mãn 19
22. điều kiện ràng buộc của QoT cho trước (các nút trong tập QI ). Trong trường hợp thông tin định tuyến trong bộ nhớ của nút I có lộ trình đến D, thay vì gửi ngay gói phản hồi RREP về nút nguồn như thuật toán DSR, SA tại I dự đoán các thông tin về QoT từ nút S đến nút D dọc theo lộ trình S ! I nối với I ! D. Nếu ràng buộc QoT cho trước được thỏa mãn, nút I mới gửi phản hồi gói RREP về nguồn. Ngược lại, quá trình khám phá lộ trình được tiếp tục thực hiện như trường hợp thông tin định tuyến trong bộ nhớ của nút I không có lộ trình đến D. Với nguyên lý này, các lộ trình được tìm thấy luôn luôn thỏa mãn các điều kiện ràng buộc của QoT. Nguyên lý dự đoán các tham số QoT tại nút I bởi SA được thực hiện dựa trên mô hình xuyên lớp như đã trình bày ở Phần 3.3.2.1 của Chương3. 4.2. Mô hình giải tích của thuật toán SLBQT-DSR Để mô hình hóa thuật toán SLBQT-DSR thành mô hình giải tích, tác giả định nghĩa một số ký hiệu toán học như sau:  (sx) Gọi Nsx = ni j n×n là ma trận biểu diễn các kết nối được chọn cho lộ trình (sx) từ nút S đến nút X (rsd ), trong đó, mỗi phần tử ni j được xác định bởi: ( (sx) 1 Nếu lộ trình rsx đi qua kết nối ci j ni j = (4.1) 0 Ngược lại  (s) Gọi rsx là tải lưu lượng yêu cầu từ S đến X, Fs = fi j n×n là ma trận biểu diễn tải lưu lượng từ S phân phối đến tất cả kết nối. Khi đó, Fs được xác định bởi: mjx6=s  (s) Fs = fi j n×n = ∑ rsxNsx (4.2) x=1 Xét trường hợp nút S cần khám phá một lộ trình đến nút D. Thuật toán SLBQT-DSR sẽ phát quảng bá gói RREQ để tìm K lộ trình thỏa mãn các điều kiện ràng buộc của QoT và EED. K lộ trình này được biểu diễn bởi ma trận (k)  (sdk) (sdk) Nsd = ni j n×n, trong đó, mỗi phần tử ni j được xác định theo (4.1). Để biểu diễn lộ trình cân bằng tải được chọn trong số K lộ trình khả dụng, tác (k) giả định nghĩa biến xsd như sau: ( 1 Nếu lộ trình thứ k được chọn x(k) = (4.3) sd 0 Ngược lại khi đó, ma trận biểu diễn tải lưu lượng từ nút S phân phối đến tất cả các kết nối 20
23. trong mạng được thay đổi thành: K 0  0(s) (k) (k) Fs = fi j n×n = Fs + rsd ∑ xsd Nsd (4.4) k=1 0(s) 0 Từ (4.4) ta có các phần tử fi j của ma trận Fs được xác định bởi: K 0(s) (s) (k) (k) fi j = fi j + rsd ∑ xsd nsd (4.5) k=1 0 Sau khi xác định được ma trận Fs , thuật toán định tuyến SLBQT-DSR được mô hình hóa thành bài toán quy hoạch tuyến tính nguyên (ILP) sau đây: 0(s)
    min max fi j (4.6) 0(s) 0 8 fi j 2Fs với các điều kiện ràng buộc: K (k) (k) (k) xsd (xsd − 1) = 0 (4.7) ∑ xsd = 1 (4.8) k=1 trong đó, (4.7) là ràng buộc nhị phân theo định nghĩa của biến x(k) ở (4.3). (4.8) là sd ràng buộc lựa chọn lộ trình. 4.3. Thực thi thuật toán SLBQT-DSR Opt. type Opt. Data Length Identification Opt. type (*) Opt. Data Len (*) Last Hop Ext. (*) Reserved (*) Target Address Address [1] (*) 4.3.1. Chỉnh sửa khuôn dạng gói RREQ (*) Address [1] Address [2] Trong thuật toán SLBQT-DSR, tác Address [2] Address [3] (*) (*) giả sử dụng gói RREQ để trao đổi các (*) Address [n] Address [n] thông tin về QoT và EED giữa các nút. Reserved QoT EED N/A BP ( ) Cấu trúc gói RREQ như cho thấy ở Hình Hình 4.3 . Cấu trúc (a) gói RREQ của thuật (b) 4.4. Gói RREQ này được chỉnh sửa từ gói toán SLBQT-DSR RREQ của giao thức DSR bằng cách thêm vào các trường QoT và EED để lưu trữ các giá trị về chất lượng truyền dẫn và thời gian trễ, dùng cho việc xác định các ràng buộc trong quá trình khám phá lộ trình. 4.3.2. Lưu đồ thuật toán SLBQT-DSR Nguyên lý khám phá lộ trình của thuật toán định tuyến SLBQT-DSR được thực hiện theo lưu đồ Hình 4.4. Các ràng buộc QoT được xác định tại các bước (3) đến (5) đối với nút nguồn, các bước (11) đến (16) đối với nút trung gian, trong đó, việc xác định tập Qi là tập các nút láng giềng của nút I thỏa mãn điều kiện ràng buộc của QoT được thực hiện theo Thuật toán 3.1 của Chương3. Khi nút nguồn đã nhận được K gói RREP về kết quả khám phá lộ trình, nghĩa là thuật toán SLBQT-DSR đã tìm được K lộ trình thỏa mãn điều kiện ràng buộc QoT, thuật toán SLBQT-DSR lựa chọn một trong số K lộ trình khả dụng sao cho tải lưu lượng được 21
24. phân bố cân bằng đến tất cả các kết nối trong mạng. Công việc này được thực hiện tại bước (27) của nút nguồn, theo Thuật toán 4.1. (1) (2) (30) Cập nhật lộ trình (28) S lựa chọn lộ trình S tạo gói Kết thúc vào bảng định cân bằng tải theo (27) Bắt đầu RREQ tuyến của S Thuật toán 4.1 Đúng (29) Từ chối yêu cầu do Sai Xác định tập tập Qs N > 0 (26) (3) không tìm được lộ trình rrep theo Thuật toán 3.1 Sai Nút nguồn Sai (4) Q #  (25) i Đúng Tăng Twait theo (N = K) OR (24) rrep Đúng đồng hồ thời gian (Twait > Timeout) (21) S phát quảng bá gói RREQ Nrrep = 0; S nhận (5) (23) (22) Nrrep = Nrrep+1 đến tất cả các nút I Qs Twait = 0; gói RREP (6) Nút I nhận gói RREQ Nút trung gian Sai (7) I là nút trung gian? Đúng (19) (8) Cập nhận thông tin Sai I chưa nhận gói đường ngược về S RREQ này trước đó? vào RC của I (20) Đúng Tạo gói RREP và (9) Cập nhận thông tin đường gửi phản hồi về S ngược về S vào RC của I theo lộ trình ngược (15) Đúng SA tại I dự đoán SNR và Nút đích (10) RC của I có lộ EED t ừ S đến D theo lộ trình đến D? trình S → I nối với I → D Sai (16) Xác định tập tập Q Sai SNR và EED thỏa (11) i theo Thuật toán 3.1 mãn điều kiện ràng buộc QoT? (12) Sai Loại bỏ Đúng Qi #  (13) gói RREQ Đúng (17) I phát quảng bá gói RREQ Tạo gói RREP và gửi phản (14) đến tất cả các nút J Qi hồi về S theo lộ trình ngược Kết thúc tiến trình xử lý (18) gói RREQ vừa nhận Hình 4.4. Lưu đồ thuật toán định tuyến SLBQT-DSR 22
25. Thuật toán 4.1: Chọn một lộ trình cân bằng tải tại nút nguồn (1) Dựa trên thông tin bảng định tuyến của nút S, xây dựng ma trận phân phối lưu lượng  (s) Fs = fi j n×n theo (4.2); (2) Dựa trên thông tin của K lộ trình khả dụng, xây dựng ma trận phân phối lưu lượng 0  0(s) Fs = fi j n×n theo (4.4); (3) Xây dựng bài toán ILP theo hàm mục tiêu (4.6) với các ràng buộc (4.7) và (4.8); (4) Giải bài toán ILP; (5) Chọn lộ trình cân bằng tải dựa trên kết quả giải bài toán ILP; (6) Cập nhật thông tin lộ trình vào bảng định tuyến của S; 4.4. Mô phỏng và phân tích kết quả 4.4.1. Kịch bản mô phỏng Hiệu quả thực thi của thuật toán SLBQT-DSR được đánh giá bằng mô phỏng trên OMNeT++ [10]. Thuật toán SLBQT-DSR được so sánh với thuật toán khám phá lộ trình của giao thức DSR [22]. Mô phỏng được thực hiện nhiều kịch bản khác nhau với các tham số kỹ thuật được thiết lập như Bảng 2.5 của Chương2. 26.00 4.4.2. Kết quả mô phỏng Giá trị yêu cầu DSR Kết quả trên Hình 4.5 cho thấy SNR 25.00 SLBQT-DSR nhỏ nhất của thuật toán SLBQT-DSR và 24.00 DSR. Với thuật toán DSR, SNR chỉ lớn hơn SNR yêu cầu khi tổng số nút nhỏ hơn 30. 23.00 SNR nhỏ nhất (dB) Với thuật toán RLBQT-DSR, SNR luôn lớn 22.00 hơn SNR yêu cầu cho dù tổng số nút mạng 21.00 lớn. Vì SNR tăng, nên BPD trên toàn mạng 20 25 30 35 40 45 50 giảm như cho thấy ở Hình 4.8. Với thuật Tổng số nút mạng toán SLBQT-DSR, BPD giảm trung bình Hình 4.5. So sánh SNR của thuật toán SLBQT-DSR và DSR 46.77% so với thuật toán DSR. 0.07 74.0E+6 DSR 72.0E+6 0.06 SLBQT-DSR 70.0E+6 0.05 68.0E+6 0.04 66.0E+6 BPD 64.0E+6 0.03 62.0E+6 0.02 Thông lượng (bit/s) 60.0E+6 SLBQT-DSR 0.01 58.0E+6 DSR 0.00 56.0E+6 0 50 100 150 200 250 300 350 400 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Tải lưu lượng (Erlang) Thời gian mô phỏng (s) Hình 4.8. So sánh BPD của thuật toán Hình 4.11. So sánh thông lượng của thuật SLBQT-DSR và DSR toán SLBQT-DSR và DSR 23
26. Về mặt thông lượng, vì PBD của thuật toán SLBQT-DSR giảm so với thuật toán DSR, nên thông lượng tăng lên. Điều này được thể hiện trên Hình 4.11. Với thuật toán DSR, thông lượng trung bình là 65.482 Mbit/s, trong khi đó thông lượng trung bình của thuật toán SLBQT-DSR là 67.385 Mbit/s. Như vậy, so với thuật toán DSR, thông lượng của thuật toán SLBQT-DSR tăng trung bình gần 1.903 Mbit/s. 4.5. Kết luận chương Trong chương này, tác giả đã trình bày thuật toán định tuyến cân bằng tải đảm bảo QoT (SLBQT-DSR) được đề xuất cho mạng MANET. Thuật toán SLBQT- DSR cho phép tìm được lộ trình thỏa mãn các ràng buộc của QoT và EED, đồ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 toàn mạng. Kết quả mô phỏng đã chứng minh rằng, thuật toán SLBQT-DSR mang lại hiệu năng mạng tốt hơn so với thuật toán DSR. Kết luận và những đóng góp của luận án Luận án có một số đóng góp chính như sau: 1. Đề 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. 2. Đề 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. 3. Đề xuất thuật toán định tuyến cân bằng tải đảm bảo QoT dựa trên thông tin định tuyến được lưu trữ trong bộ nhớ của nút nguồn (SLBQT-DSR) cho mạng MANET. Hướng phát triển của đề tài luận án 1. Nghiên cứu mặt phẳng điều khiển tích hợp giữa lớp vật lý và lớp mạng để thực thi các giao thức định tuyến ràng buộc QoT, sử dụng công nghệ SDN. 2. Nghiên cứu các giao thức định tuyến trong mạng MANET đa kênh, đa sóng mang có xét đến ràng buộc ảnh hưởng của các hiệu ứng vật lý. 3. Nghiên cứu để đánh giá thêm các độ đo về độ trễ định tuyến, chi phí định tuyến và một số độ đo khác đối với các thuật toán được đề xuất trong luận án. 4. Nghiên cứu và áp dụng các mô hình sinh lưu lượng mới, theo xu hướng lưu lượng của dịch vụ đa phương tiện, lưu lượng trong thời đại IoT để đánh giá hiệu quả cân bằng tải của các thuật toán định tuyến được đề xuất. 24
27. Các công trình đã công bố liên quan đến đề tài luận án [B1] Le Huu Binh, Vo Thanh Tu and Nguyen Van Tam, “SLBQT-DSR: Source- based Load Balancing Routing Algorithm under Constraints of Quality of Transmision for MANET”, Journal of Computer Science and Cybernet- ics, Vol.34, No.3, 2018, pp. 265-282. [B2] Le Huu Binh, Vo Thanh Tu, “QTA-AODV: An Improved Routing Algo- rithm to Guarantee Quality of Transmission for Mobile Ad Hoc Networks using Cross-Layer Model”, Journal of Communications, Vol 13, No. 7, 2018, pp.338-349. (SCOPUS). [B3] Lê Hữu Bình, Võ Thanh Tú, Nguyễn Văn Tam, “Khảo sát ảnh hưởng của các hiệu ứng vật lý và kỹ thuật định tuyến QoT trong mạng MANET”, Kỷ yếu Hội thảo quốc gia lần thứ XXI: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Thanh Hóa, 27-28/7/2018, NXB Khoa học Tự nhiên và Công nghệ, 2018, trang 162-169. [B4] Le Huu Binh, Vo Thanh Tu, Nguyen Van Tam, “Quality of Transmission Aware Routing in Adhoc networks based on Cross-Layer Model com- bined with the Static Agent”, Journal of Computer Science and Cyber- netics, Vol.32, No.4, 2016, pp. 351-366. [B5] Lê Hữu Bình, Võ Thanh Tú, Nguyễn Văn Tam, “Một phương pháp phân tích hiệu năng mạng Adhoc sử dụng mô hình giải tích”, Kỷ yếu Hội thảo Khoa học Quốc gia lần thứ X về Nghiên cứu cơ bản và ứng dụng công nghệ thông tin - FAIR’10, Đà Nẵng, 17-18/08/2017, NXB Khoa học Tự nhiên và Công nghệ, 2017, trang 577-584. [B6] Lê Hữu Bình, Nguyễn Đăng Khoa, Nguyễn Đình Hoàng Phương, “Thiết kế tôpô mạng không dây hình lưới: Một phương pháp mới sử dụng bài toán quy hoạch tuyến tính nguyên”, Tạp chí Công nghệ Thông tin và Truyền thông - Chuyên san các Công trình Nghiên cứu, Phát triển và Ứng dụng Công nghệ thông tin và Truyền thông, Tập V-3, Số 18 (38), 2017, trang 58-66. [B7] Lê Hữu Bình, Võ Thanh Tú, Nguyễn Văn Tam, “Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng MANET”, Kỷ yếu Hội thảo Khoa học Quốc gia lần thứ IX về Nghiên cứu cơ bản và ứng dụng công nghệ thông tin - FAIR’9, Cần Thơ, 04-05/08/2016, NXB Khoa học Tự nhiên và Công nghệ, 2016, trang 480-487. [B8] Lê Hữu Bình, Võ Thanh Tú, “Đánh giá ảnh hưởng của nhiễu truyền dẫn trong mạng MANET dựa trên giao thức định tuyến theo yêu cầu”, Kỷ yếu Hội nghị FAIR’8, NXB Khoa học Tự nhiên và Công nghệ, 2015, trang 111-118.