Tài liệu Mô hình kết hợp logic mờ và giải thuật di truyền cho bài toán quán lý hàng đợi tích cực trên mạng tcp ip

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN PHƢƠNG HUY MÔ HÌNH KẾT HỢP LOGIC MỜ VÀ GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRÊN MẠNG TCP/IP LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG Hà Nội – Năm 2014 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN PHƢƠNG HUY MÔ HÌNH KẾT HỢP LOGIC MỜ VÀ GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRÊN MẠNG TCP/IP Chuyên ngành: Kỹ thuật viễn thông Mã số: 62.52.02.08 LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG NGƢỜI HƢỚNG DẪN KHOA HỌC: 1. PGS. TS. Lê Bá Dũng 2. PGS. TS. Nguyễn Chấn Hùng Hà Nội – Năm 2014 1. LỜI CAM ĐOAN Tôi xin cam đoan: Luận án “Mô hình kết hợp logic mờ và giải thuật di truyền cho bài toán quản lý hàng đợi tích cực trên mạng TCP/IP” là công trình nghiên cứu của riêng tôi. Các số liệu trong luận án đƣợc sử dụng là trung thực, một phần đã đƣợc công bố trên các tạp chí khoa học chuyên ngành với sự đồng ý và cho phép của các đồng tác giả. Phần còn lại chƣa đƣợc ai công bố trong bất kỳ công trình nào khác. Hà nội, ngày 14 tháng 1 năm 2014 Tác giả luận án Nguyễn Phƣơng Huy i 2. LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS. Lê Bá Dũng - Viện công nghệ thông tin và PGS.TS. Nguyễn Chấn Hùng - Bộ môn Hệ thống viễn thông - Viện Điện tử Viễn thông - Đại học Bách Khoa Hà Nội đã tận tình hƣớng dẫn, tạo mọi điều kiện thuận lợi, giúp tôi thực hiện và hoàn thành luận án này. Tôi xin trân trọng cảm ơn PGS.TS. Vũ Văn Yêm cùng các thầy cô giáo trong bộ môn Hệ thống viễn thông - Viện Điện tử Viễn thông - Đại học Bách khoa Hà nội đã tạo điều kiện và giúp đỡ tôi trong thời gian tôi tham gia sinh hoạt khoa học tại bộ môn. Xin đƣợc gửi lời cảm ơn chân thành nhất tới Ban giám hiệu Trƣờng Đại học Kỹ thuật công nghiệp - Đại học Thái nguyên, các anh chị, bạn bè và đồng nghiệp bộ môn Điện tử viễn thông, Khoa Điện tử, Trƣờng Đại học Kỹ thuật công nghiệp đã chia sẻ và động viên giúp tôi vƣợt qua mọi khó khăn để hoàn thành tốt công việc nghiên cứu của mình. Tôi biết ơn những ngƣời thân trong gia đình đã luôn bên tôi, quan tâm, động viên, tạo điều kiện thuận lợi nhất để tôi có thể hoàn thành bản luận án. Hà nội, ngày 14 tháng 01 năm 2014 Tác giả luận án Nguyễn Phƣơng Huy ii 3. MỤC LỤC LỜI CAM ĐOAN ...................................................................................................... i LỜI CẢM ƠN ........................................................................................................... ii MỤC LỤC ............................................................................................................... iii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .............................................. viii DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ ................................................................ xi DANH MỤC CÁC BẢNG BIỂU ............................................................................xiv MỞ ĐẦU ...................................................................................................................1 CHƢƠNG 1 BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRÊN MẠNG TCP/IP… .................................................................................................................. 7 1.1. Giới thiệu chƣơng ............................................................................................. 7 1.2. Mạng TCP/IP và bài toán điều khiển tắc nghẽn ................................................ 7 1.2.1. Truyền số liệu trên mạng TCP/IP ................................................................. 7 1.2.2. Các giải thuật điều khiển tắc nghẽn theo giao thức TCP ............................... 8 1.2.2.1. Giao thức TCP.............................................................................................. 8 1.2.2.2. Một số thuật ngữ .......................................................................................... 9 1.2.2.3. Các giải thuật tránh tắc nghẽn trên mạng TCP/IP ........................................10 1.3. Quản lý hàng đợi theo phƣơng pháp truyền thống (thụ động) ..........................12 1.4. Quản lý hàng đợi tích cực ................................................................................12 1.4.1. Khái niệm quản lý hàng đợi tích cực ...........................................................12 1.4.2. Phân loại các phƣơng pháp quản lý hàng đợi tích cực ..................................13 1.5. Hiện trạng nghiên cứu và các phƣơng pháp tiếp cận bài toán AQM trong các nghiên cứu trƣớc đây................................................................................................14 1.5.1. Các phƣơng pháp AQM dựa trên chiều dài hàng đợi ...................................14 1.5.1.1. Phƣơng pháp thông báo tắc nghẽn rõ ECN ..................................................14 1.5.1.2. Cơ chế hủy bỏ sớm ngẫu nhiên RED ...........................................................15 1.5.1.3. Cơ chế huỷ bỏ sớm ngẫu nhiên theo trọng số WRED ..................................16 1.5.1.4. Giải thuật loại bỏ ngẫu nhiên sớm thích nghi ...............................................17 1.5.1.5. Giải thuật loại bỏ ngẫu nhiên sớm động - Dynamic RED.............................18 iii 1.5.1.6. Giải thuật loại bỏ ngẫu nhiên sớm ổn định hóa ............................................18 1.5.1.7. Phát hiện sớm ngẫu nhiên cân bằng FRED ..................................................19 1.5.2. Quản lý hàng đợi tích cực dựa trên tốc độ lƣu lƣợng đến .............................20 1.5.2.1. Giải thuật BLUE .........................................................................................21 1.5.2.2. Giải thuật SFB .............................................................................................21 1.5.2.3. Giải thuật phát hiện sớm dựa trên cân bằng chọn lọc SFED .........................22 1.5.2.4. Giải thuật hàng đợi ảo thích nghi AVQ........................................................23 1.5.2.5. Giải thuật hàng đợi ảo thích nghi nâng cao ..................................................24 1.5.2.6. Giải thuật Yellow ........................................................................................24 1.5.2.7. Bộ điều khiển tích phân tỷ lệ (Proportional Integral-PI) ...............................24 1.5.3. Các giải thuật AQM dựa trên sự kết hợp giữa độ dài hàng đợi và kiểm soát lƣu lƣợng đến ...........................................................................................................25 1.5.3.1. Đánh dấu ngẫu nhiên theo hàm mũ (REM) .................................................25 1.5.3.2. Giải thuật bộ đệm ảo ổn định hóa (SVB) .....................................................26 1.5.3.3. Giải thuật AQM dựa trên hàng đợi và trạng thái tải ....................................27 1.5.3.4. Giải thuật Raq .............................................................................................27 1.5.4. Một số giải thuật AQM ứng dụng logic mờ .................................................27 1.6. Một số vấn đề lớn còn tồn tại đối với bài toán AQM........................................29 1.7. Lựa chọn phƣơng pháp tiếp cận bài toán trong luận án ....................................31 1.8. Tổng kết chƣơng..............................................................................................32 CHƢƠNG 2 MÔ HÌNH KẾT HỢP DI TRUYỀN MỜ VÀ ỨNG DỤNG ...............33 2.1. Giới thiệu chƣơng ............................................................................................33 2.2. Tổng quan về tính toán mềm............................................................................33 2.3. Cơ sở toán học của logic mờ ............................................................................34 2.3.1. Tập mờ ........................................................................................................34 2.3.2. Các phép toán trên tập mờ ...........................................................................35 2.3.3. Luật nếu –thì mờ .........................................................................................37 2.3.4. Suy diễn mờ ................................................................................................38 2.3.5. Một số mô hình suy luận mờ .......................................................................41 2.4. Giải thuật di truyền ..........................................................................................43 iv 2.4.1. Giới thiệu ....................................................................................................43 2.4.2. Các bƣớc quan trọng trong việc áp dụng giải thuật di truyền .......................44 2.4.3. Các phép toán của giải thuật SGA ..............................................................45 2.4.4. Cơ sở toán học của GA................................................................................46 2.4.4.1. Các khái niệm và ký hiệu ............................................................................46 2.4.4.2. Định lý giản đồ ............................................................................................46 2.4.5. Đề xuất giải thuật di truyền cải tiến MGA ...................................................48 2.4.5.1. Mã hoá ........................................................................................................49 2.4.5.2. Hàm thích nghi ............................................................................................50 2.4.5.3. Lai tạo .........................................................................................................51 2.4.5.4. Đột biến ......................................................................................................51 2.4.5.5. Đánh giá ......................................................................................................52 2.5. Hiện trạng nghiên cứu các phƣơng pháp kết hợp GA với FL ..........................53 2.5.1. Nền tảng của việc kết hợp............................................................................53 2.5.2. Phân loại kỹ thuật kết hợp ...........................................................................54 2.6. Đề xuất mô hình kết hợp di truyền mờ cho các bài toán AQM .........................56 2.6.1. Hệ điều khiển di truyền mờ cho bài toán AQM .............................................56 2.6.2. Xây dựng bộ điều khiển mờ cho bài toán AQM ...........................................57 2.6.3. Chỉnh định bộ điều khiển mờ cho bài toán AQM bằng MGA ......................59 2.7. Tổng kết chƣơng..............................................................................................61 CHƢƠNG 3 MÔ HÌNH DI TRUYỀN MỜ CHO BÀI TOÁN CẢI TIẾN GIẢI THUẬT RED_AQM ................................................................................................63 3.1. Giới thiệu chƣơng ............................................................................................63 3.2. Xây dựng hệ mờ cho bài toán RED_AQM .......................................................64 3.2.1. Xác định các yếu tố đầu vào và ra của bộ điều khiển mờ AQM ...................64 3.2.2. Tạo mức độ các hàm liên thuộc mờ cho mỗi đầu vào và đầu ra ...................66 3.2.2.1. Mô tả các biến ngôn ngữ .............................................................................66 3.2.2.2. Lựa chọn hàm liên thuộc .............................................................................67 3.2.3. Xây dựng các cơ sở quy tắc suy diễn mờ mà hệ thống sẽ hoạt động theo .....68 3.2.4. Quyết định các hành động sẽ đƣợc thực hiện cho mỗi luật ...........................70 v 3.2.5. Kết hợp các luật và giải mờ hóa để thu đƣợc đầu ra. ....................................70 3.2.6. Ví dụ minh họa tính toán đầu ra điều khiển .................................................72 3.3. Giải thuật di truyền mờ cho AQM ...................................................................73 3.3.1. Sơ đồ hệ thống di truyền mờ RED – AQM ..................................................73 3.3.2. Cài đặt các phép toán di truyền ....................................................................73 3.3.3. Xây dựng phần mềm mô phỏng ...................................................................75 3.4. Đánh giá tính ổn định của các giải thuật AQM trên mạng TCP/IP ...................80 3.4.1. Mô hình động học lƣu lƣợng về hành vi của TCP ........................................80 3.4.2. Hệ thống điều khiển AQM ..........................................................................81 3.4.3. Phân tích sự ổn định của giải thuật AQM ....................................................83 3.4.4. Ổn định hóa luật điều khiển AQM ...............................................................85 3.4.5. Kiểm chứng tính ổn định của giải thuật AQM qua mô phỏng Matlab ..........85 3.5. Đánh giá hoạt động của giải thuật FUZZGA ...................................................89 3.6. Tổng kết chƣơng..............................................................................................95 CHƢƠNG 4 MÔ HÌNH DI TRUYỀN MỜ CHO BÀI TOÁN CẢI TIẾN GIẢI THUẬT REM_AQM ...............................................................................................97 4.1. Giới thiệu chƣơng ............................................................................................97 4.2. Nhắc lại giải thuật REM ..................................................................................97 4.3. Hệ mờ cho bài toán cải tiến giải thuật REM.....................................................98 4.4. Giải thuật di truyền cải tiến MGA cho chỉnh định hệ mờ REM ......................101 4.5. Mô phỏng đánh giá giải thuật FGREM trên mạng đơn tắc nghẽn ...................106 4.5.1. Lựa chọn các tham số mô phỏng ...............................................................106 4.5.2. Kích thƣớc hàng đợi của các phƣơng pháp AQM ......................................107 4.5.3. Tốc độ đáp ứng của các phƣơng pháp AQM ..............................................110 4.5.4. Ảnh hƣởng của trễ đến các phƣơng pháp AQM .........................................111 4.5.5. Ảnh hƣởng của thông số tải đến các phƣơng pháp AQM ..........................113 4.6. Mô phỏng và đánh giá giải thuật FGREM với mạng đa tắc nghẽn ..................114 4.6.1. Cấu trúc mạng mô phỏng...........................................................................114 4.6.2. Ảnh hƣởng của lƣu lƣợng tải và tốc độ đáp ứng .........................................115 4.6.3. Ảnh hƣởng của trễ đến các phƣơng pháp AQM .........................................119 vi 4.7. Tổng kết chƣơng............................................................................................120 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .............................................................. 122 DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA LUẬN ÁN .......................... 124 TÀI LIỆU THAM KHẢO ...................................................................................... 125 PHỤ LỤC A .......................................................................................................... 131 PHỤ LỤC B .......................................................................................................... 132 4. vii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Ký hiệu Tiếng Anh Tiếng Việt ACK Acknowledgement Bản tin báo nhận AI Artificial Intelligence Trí tuệ nhân tạo AIMD Additive– Increase MultiplicativeDecrease Tăng cộng giảm nhân AQM Active Queue Management Quản lý hàng đợi tích cực ARED Adaptive Random Early Detection Phát hiện sớm ngẫu nhiên thích nghi AVQ Adaptive Virtual Queue Giải thuật hàng đợi ảo thích nghi CE Congestion Experienced Chỉ thị tắc nghẽn CWND Congestion Window Cửa sổ tắc nghẽn DRED Dynamic Random Early Detection Giải thuật loại bỏ ngẫu nhiên sớm động DT Drop Tail Cơ chế loại bỏ cuối hàng DVP Droping Probability Xác suất loại bỏ gói EAVQ Enhanced Adaptive Virtual Queue ECN Explicit Congestion Notification Thông báo tắc nghẽn rõ ràng ES Expert System Hệ chuyên gia FGREM Fuzzy Genetic Random Exponential Marking Giải thuật đánh dấu ngẫu nhiên theo hàm mũ ứng dụng hệ di truyền mờ FIFO First In First Out FIS Fuzzy Inference System Giải thuật hàng đợi ảo thích nghi nâng cao Hàng đợi phục vụ theo kiểu vào trƣớc ra trƣớc Hệ suy luận mờ viii FL Fuzzy Logic Logic mờ FLC Fuzzy Logic Controller Bộ điều khiển logic mờ FRED Fairness Random Early Discard Loại bỏ sớm ngẫu nhiên cân bằng FS Fuzzy system Hệ mờ GA Genetic Algorithm Giải thuật di truyền IP Internet Protocol Giao thức Internet MATLAB MATrix LABtory Thí nghiệm ma trận MF Membership Function Hàm liên thuộc MGA Modified Genetic Algorithm Giải thuật di truyền cải tiến MPD Mark Probability Denominator Mẫu số xác suất đánh dấu NS2 Network Simulator 2 Phần mềm mô phỏng mạng Network Simulator 2 PI Proportional Integral Bộ điều khiển tích phân tỷ lệ PH Packet Header Mào đầu gói tin QL Queue Limit Giới hạn hàng đợi QoS Quality of Service Chất lƣợng dịch vụ RED Random Early Discard Loại bỏ ngẫu nhiên sớm REM Random Exponential Marking Đánh dấu ngẫu nhiên theo hàm mũ RTP Realtime Protocol Giao thức thời gian thực RTT Round Trip Time SC Soft computing SFED Selective Fair Early Detection SGA Simple Genetic Algorithm Thời gian cho một chu trình của gói tin Kỹ thuật tính toán mềm ix Phát hiện sớm dựa trên cân bằng chọn lọc Giải thuật di truyền đơn giản SRED Stabilized Random Early Discard Phƣơng pháp loại bỏ ngẫu nhiên sớm ổn định hóa SVB Stabilized Virtual Buffer Bộ đệm ảo ổn định hóa TCP Transport Control Protocol Giao thức điều khiển truyền tải TOS Type Of Service Loại dịch vụ TQL Target Queue Length Chiều dài hàng đợi tham chiếu UDP User Data Protocol WRED Weighted Random Early Detection Giao thức dữ liệu ngƣời sử dụng 5. x Phƣơng pháp loại bỏ sớm ngẫu nhiên có trọng số 6. DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ Hình 1.1. Kiến trúc mạng đơn giản........................................................................... 7 Hình 1.2. Hiện tƣợng Time out ................................................................................. 9 Hình 1.3. Nguyên lý cửa sổ tắc nghẽn ......................................................................10 Hình 1.4. Nguyên lý của việc lặp lại ba bản tin báo nhận .........................................10 Hình 1.5. Thuật toán khởi đầu chậm, truyền lại nhanh và khôi phục nhanh [55] ......11 Hình 1.6. Phân loại các phƣơng pháp quản lý hàng đợi tích cực [64] .......................14 Hình 1.7. Giải thuật RED truyền thống [19] .............................................................15 Hình 1.8. Giải thuật RED với “gentle option” ..........................................................16 Hình 1.9. Cơ chế loại bỏ gói tin của WRED [62] .....................................................17 Hình 1.10. Ví dụ về SFB[64]....................................................................................22 Hình 1.11. Thực hiện bộ điều khiển PI [12],[13] ......................................................25 Hình 2.1. Các kỹ thuật tính toán mềm hình thành nên tính toán thông minh .............33 Hình 2.2. Một số dạng hàm liên thuộc cơ bản..........................................................35 Hình 2.3. Hàm liên thuộc của biến ngôn ngữ T(tuổi) ................................................37 Hình 2.4. Mô hình suy luận mờ với một luật-một tiền đề .......................................39 Hình 2.5. Mô hình suy luận mờ một luật-nhiều tiền đề ............................................40 Hình 2.6. Mô hình suy luận mờ hai luật hai tiền đề ..................................................40 Hình 2.7. Mô hình suy diễn mờ Mamdani ................................................................42 Hình 2.8. Mô hình mờ Sugeno ................................................................................42 Hình 2.9. Mô hình suy luận mờ Tsukamoto .............................................................43 Hình 2.10. Cấu trúc MGA tổng quát ........................................................................49 Hình 2.11. Quá trình lai tạo .....................................................................................51 Hình 2.12. Hoạt động của giải thuật MGA và SGA ..................................................52 Hình 2.13. Sử dụng GA để cải tiến hiệu suất hệ thống Mờ .......................................54 Hình 2.14. Kiến trúc của hệ thống điều khiển tự động giải thuật di truyền................55 Hình 2.15. Mô hình chỉnh định mô hình mờ bằng MGA ........................................56 Hình 2.16. Cấu trúc hệ suy luận mờ tổng quát tổng quát [37] ...................................58 Hình 2.17. Ví dụ minh họa ảnh hƣởng của lai tạo đến dạng hàm liên thuộc [66] ......60 xi Hình 2.18. Ví dụ minh họa ảnh hƣởng của đột biến đến dạng hàm liên thuộc [66] ...61 Hình 3.1. Mô hình hệ thống điều khiển mờ cho AQM ..............................................65 Hình 3.2. Các đầu vào bộ điều khiển mờ ..................................................................68 Hình 3.3. Đầu ra bộ điều khiển mờ ...........................................................................68 Hình 3.4. Mặt suy diễn của bộ điều khiển mờ ..........................................................70 Hình 3.5. Hệ luật của bộ điều khiển mờ ...................................................................71 Hình 3.6. Ví dụ minh họa tính toán đầu ra điều khiển[9] .........................................72 Hình 3.7. Sơ đồ hệ thống điều khiển AQM tổng quát ..............................................73 Hình 3.8. Một nhiễm sắc thể cho chuỗi mã hoá ........................................................74 Hình 3.9. Hệ mờ, đƣợc xây dựng từ hệ luật trƣớc khi dùng MGA ............................79 Hình 3.10. Hệ mờ sau khi đã chỉnh các biến đầu vào và ra (dùng MGA) ..................80 Hình 3.11. Mô hình hệ thống mạng TCP/IP .............................................................81 Hình 3.12. Mô hình phân tách tuyến tính cho bài toán AQM [13] ............................83 Hình 3.13. Sơ đồ khối hệ thống điều khiển AQM tuyến tính [13] .............................84 Hình 3.14. Sơ đồ khối hệ thống điều khiển phản hồi AQM [13] ...............................84 Hình 3.15. Biểu diễn nút cổ chai từ A sang B ...........................................................85 Hình 3.16. Gói dữ liệu đầu ra tiệm cận vói gói dữ liệu yêu cầu TQL=200 ..............88 Hình 3.17. Tín hiệu điều khiên mờ và tín hiệu sai số ..............................................88 Hình 3.18. Gói tín hiệu đầu ra bám tín hiệu yêu cầu (dùng MGA) ............................89 Hình 3.19. Tín hiệu điều khiển và tín hiệu sai số (dùng MGA) .................................89 Hình 3.20. Tình trạng hàng đợi đối với luật điều khiển mờ cho RED và FUZZGA .90 Hình 3.21. Tỉ lệ mất gói của RED và FUZZGA-AQM ...........................................91 Hình 3.22. Hiệu suất quản lí hàng đợi của RED và FUZZGA ................................91 Hình 3.23. Cấu hình mạng cho mô phỏng [21] .......................................................93 Hình 3.24. Tình trạng hàng đợi của FPI và PI [21] .................................................94 Hình 3.25. Tình trạng hàng đợi của FUZZGA và PI ...............................................94 Hình 4.1. Hệ mờ cho bài toán REM AQM ...............................................................98 Hình 4.2. Các hàm liên thuộc cho đầu vào mờ Pr (kT ) ..........................................100 Hình 4.3. Các hàm liên thuộc cho đầu vào mờ Pr (kT  T ) ....................................100 Hình 4.4. Mặt suy diễn thể hiện các luật suy luận mờ .............................................101 xii Hình 4.5. Giá trị các hàm liên thuộc đầu vào Pr (kT ) sau khi luyện mạng ..............105 Hình 4.6. Giá trị các hàm liên thuộc đầu vào Pr (kT  T ) sau khi luyện mạng.........105 Hình 4.7. Mặt suy diễn thể hiện các luật suy luận mờ sau khi luyện mạng .............105 Hình 4.8. Cấu trúc mạng đơn tắc nghẽn cho mô phỏng ..........................................107 Hình 4.9. Kích thƣớc hàng đợi của các phƣơng pháp AQM ...................................108 Hình 4.10. Kích thƣớc hàng đợi của các phƣơng pháp AQM khi lƣu lƣợng thay đổi ...............................................................................................................................110 Hình 4.11. Kích thƣớc hàng đợi của các phƣơng pháp AQM khi RTT=120 ms ......112 Hình 4.12. Hiệu suất sử dụng tuyến theo trễ hàng đợi trung bình của phƣơng pháp AQM......................................................................................................................113 Hình 4.13. Hiệu suất sử dụng tuyến theo biến thiên độ trễ của phƣơng pháp AQM 113 Hình 4.14. Tỷ lệ mất gói của các phƣơng pháp AQM theo thông số tải ..................114 Hình 4.15. Hiệu suất sử dụng tuyến so với trễ khi thông số tải thay đổi..................114 Hình 4.16. Cấu trúc mạng đa tắc nghẽn ..................................................................115 Hình 4.17. Kích thƣớc hàng đợi của các phƣơng pháp AQM khi N=800 luồng.......116 Hình 4.18. Tỷ lệ mất gói của các giải thuật AQM khi lƣu lƣợng tải từ 250-800 ......117 Hình 4.19. Hiệu suất sử dụng tuyến so với trễ trung bình và biến thiên độ trễ khi tăng lƣu lƣợng từ 250-800 .............................................................................................118 Hình 4.20. Tỷ lệ mất gói, trễ và biến thiên trễ khi RTT=200 ms .............................118 Hình 4.21. Kích thƣớc hàng đợi của các phƣơng pháp AQM khi RTT=200 ms ......119 7. xiii DANH MỤC CÁC BẢNG BIỂU Bảng 1.1. Tổng kết một số phƣơng pháp AQM sử dụng logic mờ ............................28 Bảng 2.1.So sánh đặc điểm giữa FL và GA (-:Yếu, V:Mạnh) ...................................53 Bảng 2.2.Phân loại việc kết hợp giữa các hệ thống Di truyền và Mờ [41] ................54 Bảng 3.1. Cơ sở luật – các luật ngôn ngữ [9] ............................................................68 Bảng 3.2. Một số thủ tục chính đƣợc khai báo trong mga.h ......................................76 Bảng 3.3. Một số thủ tục chính đƣợc khai báo trong mga.cc ....................................77 Bảng 3.4. Một số thủ tục chính đƣợc khai báo trong fuzzga.h ..................................77 Bảng 3.5. Một số thủ tục chính đƣợc khai báo trong fuzzga.cc .................................78 Bảng 3.6. Kết quả đo lƣờng các tham số của mạng với hai thuật toán AQM ............90 Bảng 3.7. Một số đặc điểm của hai thuật toán FUZZGA và FPI ...............................92 Bảng 3.8. Kết quả đo lƣờng các tham số của mạng với FUZZGA và PI ..................95 Bảng 4.1: Các tham số của REM ..............................................................................98 Bảng 4.2. Hệ luật mờ cho bài toán REM AQM [24] ...............................................101 Bảng 4.3. Các giá trị tham số điều khiển của các phƣơng pháp AQM ....................106 xiv 8. MỞ ĐẦU 1. Tính khoa học và cấp thiết của luận án Sự bùng nổ nhu cầu thông tin của khách hàng viễn thông cùng với xu hƣớng hội nhập trên một nền mạng chung duy nhất đã và đang đặt ra những thách thức to lớn cho mạng viễn thông hiện tại. Khách hàng viễn thông ngày càng đòi hỏi sự đa dạng về số lƣợng dịch vụ cũng nhƣ sự hoàn thiện trong chất lƣợng dịch vụ. Do đó, trên mạng lõi, các bài toán quản lý mạng viễn thông nhƣ định tuyến, quản lý tài nguyên, quản lý chất lƣợng, điều khiển lƣu lƣợng mạng…cho các loại hình dịch vụ khác nhau cũng cần phải đƣợc đáp ứng một cách tức thời, đồng bộ, hiệu quả và thông minh. Một trong các bài toán kể trên chính là quản lý hàng đợi tích cực (Active Queue Management – AQM) tại các bộ định tuyến trên mạng TCP/IP. Mục đích của bài toán này là căn cứ vào tình trạng hiện tại của hàng đợi hoặc/và tốc độ của các nguồn lƣu lƣợng đến để đƣa ra cơ chế ch ộng loại bỏ gói tin của các luồng lƣu lƣợng đến theo một cách thức phù hợp sao cho luôn duy trì chiều dài trung bình (hoặc tức thời) c a hàng ợi ở một mức ặt trước phù hợp. Việc ổn định chiều dài của hàng đợi sẽ làm cho một số thông số hoạt động của mạng TCP/IP nhƣ tỷ lệ mất gói, hiệu suất sử dụng tuyến, trễ trung bình và biến thiên độ trễ dao động trong một phạm vi hợp lý. Điều này sẽ vừa đảm bảo không gây tắc nghẽn trên mạng, vừa tạo điều kiện cung cấp và duy trì một cách tốt nhất chất lƣợng dịch vụ (Quality of Service –QoS) của các luồng lƣu lƣợng đến khác nhau [5],[51]. Để giải quyết bài toán AQM, ba phƣơng pháp truyền thống đƣợc biết đến là quản lý hàng đợi dựa trên chiều dài hàng đợi (đại diện tiêu biểu là giải thuật loại bỏ gói ngẫu nhiên sớm - Random Early Discard - RED), quản lý hàng đợi dựa trên tốc độ lƣu lƣợng đến (mà đại diện là giải thuật Blue) và quản lý hàng đợi dựa trên sự kết hợp cả chiều dài và tốc độ lƣu lƣợng đến (điển hình là giải thuật đánh dấu ngẫu nhiên theo hàm mũ - Random Exponential Marking - REM) [64]. Gần đây, nhằm nâng cao hiệu quả của bài toán AQM, ngoài ba thuật toán tiêu biểu kể trên, đã có rất nhiều phƣơng pháp khác đƣợc công bố [51],[59], [64]. Các công trình này xoay quanh việc sửa đổi RED, Blue, REM hoặc kết hợp các phƣơng pháp. Các kết quả thu đƣợc đã phần nào đáp ứng đƣợc yêu cầu của bài toán AQM. Tuy nhiên, các phƣơng pháp này vẫn cần đƣợc cải tiến sao cho vừa đơn giản hóa khi thực hiện, vừa nâng cao tính thông minh trong việc duy trì độ dài hàng đợi trung bình trong điều kiện động học của mạng luôn thay đổi, vừa đảm bảo tính công bằng trong việc loại bỏ gói đối với các luồng lƣu lƣợng đến. Các nhƣợc điểm cố hữu trên của các bài toán AQM truyền thống sẽ đƣợc khắc phục khi áp dụng các thành tựu đạt đƣợc của l nh vực khoa học máy tính mà cụ thể là trí tuệ nhân tạo 1 nhằm bổ sung khả năng học, khả năng ra quyết định thông minh của hệ thống. Đặc biệt trong các bài toán phức tạp, khi thiếu dữ liệu đầu vào cho quá trình ra quyết định. Trong l nh vực khoa học máy tính, kỹ thuật tính toán mềm (Soft computing - SC) với mục tiêu giải quyết các bài toán xấp xỉ, gần đúng đang là một xu hƣớng mới, bƣớc đầu đem lại một số thành tựu nổi bật. Kỹ thuật SC cho ph p một bài toán cụ thể sẽ đƣợc khai thác với mục tiêu sao cho hệ thống dễ thiết kế, giá thành thấp nhƣng vẫn ảm bảo tính úng ắn và thông minh trong quá trình thực hiện với một ngƣỡng chấp nhận sai số. Về cơ bản, mô hình mẫu cho kỹ thuật tính toán mềm là tƣ duy con ngƣời. Nó khai thác khả năng đặc biệt trong tƣ duy của con ngƣời khi giải quyết hiệu quả các vấn đề trong những môi trƣờng không chắc chắn và không chính xác, dựa trên những phƣơng pháp tính toán và lập luận logic truyền thống [30],[37]. Kỹ thuật tính toán mềm không phải là phƣơng pháp đơn lẻ. Nó là sự kết hợp qua lại của nhiều phƣơng pháp trong đó 2 công cụ quan trọng nhất phải kể đến là: Giải thuật di truyền (Genetic Algorithm - GA) và logic mờ (Fuzzy logic - FL). Trong đó GA là phƣơng pháp tìm kiếm giúp cho việc giải các bài toán tối ưu còn FL tập trung vào việc xử lý các tính toán gần úng và không chính xác. Các phƣơng pháp này sẽ hỗ trợ và bổ sung cho nhau thay vì cạnh tranh nhau. Chính vì vậy, việc xây dựng nên các mô hình tính toán có sự kết hợp qua lại của hai phƣơng pháp nêu trên nhằm phát huy ƣu điểm, khắc phục nhƣợc điểm của các phƣơng pháp đơn lẻ trong một số ứng dụng thực tế đƣợc rất nhiều các nhà khoa học trong và ngoài nƣớc quan tâm. Các cơ sở lý luận trên cho thấy rõ khả năng ứng dụng của các mô hình tính toán có sự kết hợp các thành phần của SC nhƣ GA, FL cho các bài toán viễn thông phức tạp nói chung cũng nhƣ bài toán AQM nói riêng. Căn cứ vào các tập mẫu vào/ra đã đƣợc thống kê, mô hình tính toán kết hợp này sẽ tự ộng tìm ra các quy luật, các tham số ặc trưng cơ bản của các hệ thống trong thời gian hoạt động. Kết quả thu đƣợc này sẽ giúp chỉnh định lại cấu trúc cũng nhƣ thông số hoạt động của hệ thống sao cho phù hợp nhất (thể hiện ở sai số giữa đầu ra lý thuyết và thực tế là chấp nhận đƣợc). Trên thực tế, đã có rất nhiều công trình đƣợc công bố trong đó sử dụng mô hình kết hợp GA và FL cho các bài toán ra quyết định. Tuy nhiên, các công trình này vẫn sử dụng giải thuật di truyền đơn giản (Simple Genetic Algorithm - SGA) đƣợc đề xuất bởi Holland [22]. Giải thuật SGA vẫn cần đƣợc cải tiến nhằm giảm thiểu hơn nữa thời gian tính toán sao cho có thể phù hợp với các ứng dụng thực tế. Xuất phát từ phân tích trên, luận án đƣa ra mô hình kết hợp giải thuật di truyền cải tiến (Modified Genetic Algorithm – MGA) với FL. Mô hình kết hợp này sẽ đƣợc áp dụng để giải quyết hai bài toán AQM nhằm chứng minh khả năng áp dụng ý tƣởng của tính toán mềm trong các bài toán viễn thông trong thực tế sao cho vừa đơn giản trong thiết kế trong khi vẫn duy trì đƣợc tính hiệu quả. Cụ thể là trong bối cảnh động học của mạng TCP/IP thay đổi (số 2 lƣợng nguồn TCP ra/vào mạng liên tục, trễ truyền dẫn thay đổi), mô hình kết hợp đƣợc đề xuất sẽ đƣa ra quyết định loại bỏ gói tin một cách thông minh (dựa trên việc học về hoạt động của hệ thống thông qua các tập mẫu vào ra) nhằm duy trì ổn định chiều dài của hàng đợi ở một mức đặt trƣớc (TQL) phù hợp và từ đó gián tiếp giữ cho một số tham số của mạng TCP nhƣ tỷ lệ mất gói, hiệu suất sử dụng tuyến, trễ trung bình, biến thiên độ trễ ở một giá trị tốt hơn so với các phƣơng pháp AQM truyền thống trong cả hai trƣờng hợp mạng đơn tắc nghẽn và đa tắc nghẽn. Kết quả nghiên cứu này sẽ củng cố hƣớng phát triển tiếp trong tƣơng lai trong việc cung cấp các công cụ cho ph p ph p giải quyết phần lớn các bài toán phức tạp trong thực tế của ngành viễn thông nói chung cũng nhƣ các l nh vực khoa học kỹ thuật hay đời sống xã hội khác. 2. Đối tƣợng và phạm vi nghiên cứu Ngoài hai công cụ là FL và GA, SC còn bao gồm rất nhiều công cụ hữu ích khác nhƣ mạng nơron, máy học sử dụng vectơ hỗ trợ, thuật toán tối ƣu bầy đàn…[30][37]. Các công cụ này có thể đƣợc khai thác một cách riêng rẽ hoặc kết hợp lẫn nhau nhằm đạt đƣợc hiệu quả hoạt động tốt hơn. Chính vì vậy, hoàn toàn có thể chứng minh hiệu quả việc kết hợp MGA hay FL với các công cụ khác của tính toán mềm trong rất nhiều bài toán l nh vực viễn thông. Tuy nhiên, do hạn chế về mặt thời gian, luận án chỉ tập trung vào bài toán kết hợp MGA và FL trong hệ di truyền mờ ứng dụng cho cải tiến hoạt động của giải thuật RED cũng nhƣ cải tiến hoạt động của giải thuật REM. Việc lựa chọn phƣơng thức kết hợp MGA và FL trong luận án nhằm làm giảm thời gian hoạt động của hệ thống trong khi vẫn đạt đƣợc độ chính xác nhất định. Để giảm thời gian hoạt động thì hệ ra quyết định phải đơn giản, do đó hệ suy luận mờ đƣợc lựa chọn áp dụng trong bài toán AQM đề xuất. Tuy nhiên, hệ thống hoạt động càng chính xác đồng ngh a với yêu cầu sai số hoạt động của hệ thống càng nhỏ. Do vậy, cần thiết phải có sự hỗ trợ của giải thuật tìm cực trị toàn cục trong quá trình tối thiểu hóa sai số. Đây chính là ƣu điểm nổi bật nhất của GA. Chính vì vậy, hƣớng tiếp cận của luận án sẽ là sử dụng GA để chỉnh định hệ FL sao cho đạt đƣợc độ chính xác mong muốn. Tuy nhiên, nhƣ đã đề cập ở trên, nhằm rút ngắn hơn nữa thời gian hội tụ, luận án cũng đƣa ra một số thay đổi trong giải thuật di truyền đơn giản SGA thành giải thuật di truyền cải tiến MGA và lấy đó làm trung tâm của sự kết hợp. Luận án sẽ chứng minh giải thuật MGA sẽ cho thời gian hội tụ nhanh hơn SGA. Bài toán xây dựng mô hình di truyền mờ nhằm cải tiến các giải thuật AQM có vai trò đặc biệt quan trọng trong xu thế hội nhập các dịch vụ viễn thông trên nền mạng TCP/IP nhằm quản lý các luồng lƣu lƣợng khác nhau sao cho vừa đảm bảo QoS vừa hạn chế hiện tƣợng tắc nghẽn. Trong mô hình này, FL hỗ trợ cho quá trình ra quyết định, MGA thực hiện việc chỉnh tham số của hàm liên thuộc mờ vào ra. Mô hình này sẽ đƣợc chứng minh là ổn định và cho kết quả tốt hơn khi sử dụng các phƣơng pháp AQM kinh điển. Bằng phân tích 3 toán học kết hợp với công cụ mô phỏng trên hai bài toán AQM, luận án cho thấy khả năng ứng dụng các công cụ của SC cho bài toán hỗ trợ ra quyết định với sự dung hòa các yêu cầu là tính đơn giản trong thiết kế, độ chính xác và thời gian thực hiện. 3. Mục tiêu của luận án Mục tiêu của luận án là chứng minh khả năng ứng dụng các mô hình tính toán có sử dụng kết hợp hai công cụ quan trọng của tính toán mềm nhƣ GA, FL cho bài toán AQM trên mạng TCP/IP. Mục đích cụ thể của luận án là sử dụng mô hình kết hợp di truyền mờ nhằm giải quyết hai bài toán AQM khác nhau: - Kết hợp MGA với FL ứng dụng cho bài toán AQM dựa trên chiều dài hàng đợi (cải tiến thuật toán RED) - Kết hợp MGA và FL ứng dụng cho bài toán AQM dựa trên sự kết hợp chiều dài hàng đợi và tốc độ lƣu lƣợng đến (cải tiến thuật toán REM). Phƣơng pháp sử dụng mô hình kết hợp kể trên sẽ đƣợc chứng minh là ổn định thông qua mô phỏng trên phần mềm hỗ trợ chuyên dụng Matlab. Ngoài ra, thông qua mô phỏng bằng phần mềm NS2, phƣơng pháp mới này cũng đƣợc so sánh với các phƣơng pháp truyền thống trên cùng một cấu hình mạng (từ đơn giản đến phức tạp) ở các tiêu chí ảnh hƣởng đến hoạt động của mạng TCP/IP nhƣ tỷ lệ mất gói, hiệu suất sử dụng tuyến, trễ và biến thiên độ trễ nhằm chứng minh rõ hiệu quả thực hiện. 4. Phƣơng pháp luận nghiên cứu Phƣơng pháp nghiên cứu trong luận án đƣợc kết hợp logic giữa phân tích lý thuyết với tiến hành mô phỏng kiểm chứng. Luận án sẽ phân tích, so sánh các ƣu nhƣợc điểm, tính hiệu quả của các giải pháp trƣớc đây trong việc giải quyết các mục tiêu của bài toán AQM để trên cơ sở đó tìm ra hƣớng giải quyết thích hợp hơn, khắc phục đƣợc các nhƣợc điểm, đạt đƣợc hiệu quả tốt hơn một cách tƣơng đối so với các giải pháp trƣớc đây. 5. Nội dung và bố cục của luận án  Nội dung của luận án bao gồm các kết quả nghiên cứu sau: 1- Giới thiệu bài toán AQM trên mạng TCP/IP; cập nhật các kết quả nghiên cứu về các phƣơng pháp AQM; chỉ ra những tồn tại của các phƣơng pháp AQM truyền thống, từ đó đề xuất mô hình kết hợp các công cụ của tính toán mềm cho bài toán AQM. 2- Phân tích cơ sở toán học của hai công cụ quan trọng trong tính toán mềm là FL, GA; cập nhật các ứng dụng kết hợp FL và GA trong và ngoài nƣớc trong các l nh vực, đặc biệt là trong l nh vực điện tử viễn thông (Cụ thể luận án tổng kết đƣợc tính cần thiết của việc kết hợp, các phƣơng thức kết hợp, tóm tắt một số ví dụ minh họa và đƣa ra lớp bài toán thích ứng đối với từng mô hình kết hợp). 4