Tiến Sĩ 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 TC

LUẬN ÁN TIẾN SĨ
NĂM 2014

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 iv
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 v
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 vi
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
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. 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 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ấpnhư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ố 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 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).