Ứng dụng giải thuật di truyền mờ cho bài toán quản lý hàng đợi tích cực (AQM) trong viễn thông

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC THÁI NGUYÊN. TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP  LUẬN VĂN THẠC SỸ KỸ THUẬT NGÀNH KỸ THUẬT ĐIỆN TỬ ỨNG DỤNG GIẢI THUẬT DI TRUYỀN MỜ CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC (AQM) TRONG VIỄN THÔNG LÊ HOÀNG Thái Nguyên, 2010 BỘ GIÁO DỤC VÀ ĐÀO TẠO Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP  LUẬN VĂN THẠC SỸ KỸ THUẬT ỨNG DỤNG GIẢI THUẬT DI TRUYỀN MỜ CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC (AQM) TRONG VIỄN THÔNG Ngành: Kỹ thuật điện tử Mã số: 605270 Học viên: Lê Hoàng Ngƣời HD khoa học: PGS. Lê Bá Dũng Thái Nguyên, 2010 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang i ĐẠI HỌC THÁI NGUYÊN CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC Độc lập - Tự do - Hạnh phúc KỸ THUẬT CÔNG NGHIỆP THUYẾT MINH LUẬN VĂN THẠC SỸ KỸ THUẬT Học viên: Lê Hoàng Lớp: Cao học - K11 Chuyên ngành: Kỹ thuật Điện tử Người hướng dẫn khoa học: PGS.TS Lê Bá Dũng Ngày giao đề tài: 20 tháng 01 năm 2010. Ngày hoàn thành: 5 tháng 9 năm 2010.

CÁN BỘ HƢỚNG DẪN KHOA HỌC HỌC VIÊN PGS.TS Lê Bá Dũng Lê Hoàng BAN GIÁM HIỆU KHOA SAU ĐẠI HỌC Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang ii LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, các số liệu, kết quả nêu trong luận văn này là trung thực và là công trình nghiên cứu của riêng tôi, luận văn này không giống hoàn toàn bất cứ luận văn hoặc các công trình đã có trước đó. Thái Nguyên, ngày 23 tháng 8 năm 2010 Tác giả luận văn Lê Hoàng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang iii LỜI CẢM ƠN Trong suốt quá trình học tập và tốt nghiệp, tôi đã nhận được sự giúp đỡ tận tình của các thầy cô giáo và tôi đặc biệt muốn cảm ơn: Thầy giáo PGS. Lê Bá Dũng, Viện công nghệ thông tin, Viện khoa học và công nghệ Việt Nam. Thầy giáo ThS.

Nguyễn Phương Huy, 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 Thái Nguyên. đã tận tình giúp đỡ, hướng dẫn tôi trong thời gian thực hiện đề tài, cảm ơn sự giúp đỡ của gia đình, bạn bè và các đồng nghiệp trong thời gian qua. Vì đề tài liên quan tới nhiều lĩnh vực mới với kiến thức rất rộng, bản thân tôi phải tham khảo rất nhiều tài liệu và các bài báo quốc tế. Mặc dù đã cố gắng, song do điều kiện về thời gian và kinh nghiệm thực tế còn nhiều hạn chế nên không thể tránh khỏi thiếu sót (nhất là trong quá trình biên tập và dịch tài liệu thành tiếng Việt).

Vì vậy, tôi rất mong nhận được sự đóng góp ý kiến của các thầy cô cũng như của các bạn bè, đồng nghiệp. Một lần nữa tôi xin chân thành cảm ơn! Tác giả luận văn Lê Hoàng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang iv LỜI NÓI ĐẦU Ngành Điện tử viễn thông luôn phải đáp ứng một nhiệm vụ quan trọng là cung cấp các dịch vụ truyền thông tin xa một cách mềm dẻo, nhanh chóng và chính xác nhất. Để đáp ứng nhiệm vụ trên, vấn đề quản lý hàng đợi tích cực luôn được đặt lên hàng đầu. Tuy nhiên việc quản lý hàng đợi tích cực luôn là vấn đề phức tạp.

Trên mạng viễn thông, kỹ thuật định tuyến cũng hỗ trợ cho quá trình định tuyến mạng, điều khiển công suất đầu cuối di dộng, quản lý tài nguyên mạng, quản lý chất lượng mạng, điều khiển lưu lượng mạng, tạo điều kiện xây dựng một mạng viễn thông thông minh. Việc kết hợp Giải thuật di truyền và Logic mờ tạo ra các thiết bị có độ thích nghi cao và thông minh như con người đáp ứng các bài toán phức tạp trong điều kiện thiếu thông tin. Xuất phát từ các vấn đề trên, tác giả chọn đề tài: “Ứng dụng giải thuật di truyền mờ cho bài toán quản lý hàng đợi tích cực (AQM) trong viễn thông”. Nội dung chính của luận văn này tập trung vào nghiên cứu việc xây dựng nên phương pháp để giải quyết các bài toán điều khiển lưu lượng thông minh trên mạng viễn thông hiện tại.

Nhằm giải quyết được vấn đề tránh tắc nghẽn và tối ưu hoá thời gian truyền nhận các gói dữ liệu thông qua các router trên mạng. Nội dung chính của luận văn là ứng dụng giải thuật di truyền mờ vào bài toán AQM trên mạng hiện nay, cấu trúc luận văn bao gồm các chương sau: Chƣơng 1: Các kiến thức tổng quan. Chƣơng 2: Bài toán quản lý hàng đợi tích cực trong viễn thông. Chƣơng 3: Ứng dụng giải thuật di truyền mờ cho bài toán quản lý hàng đợi tích cực trong viễn thông.

Cuối cùng là kết luận và hướng phát triển của đề tài. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang v MỤC LỤC Trang Thuyết minh luận văn thạc sỹ kỹ thuật. i Lời cam đoan. ii Lời cảm ơn.

iii Lời nói đầu. iv Mục lục. v Danh mục các bảng biểu. viii Danh mục các hình vẽ.

ix Các thuật ngữ viết tắt. xi CHƢƠNG 1: CÁC KIẾN THỨC TỔNG QUAN 1.1 Điều khiển tắc nghẽn trên mạng internet .2 Chất lượng dịch vụ trên internet .3 Cấu trúc luận văn .2 Tổng quan về AQM và TCP .1 TCP và quản lý hàng đợi tích cực (AQM).2 Các dịch vụ tích hợp và phân biệt.3 Giải thuật di truyền.2 Giải thuật di truyền và tìm kiếm tối ưu .3 Cấu trúc một giải thuật di truyền .1 Cấu trúc một giải thuật di truyền đơn giản .2 Các phép toán của giải thuật di truyền .4 Ứng dụng của giải thuật di truyền .4 Giải thuật di truyền mờ .2 Giải thuật di truyền kết hợp với logic mờ .1 Phân loại kỹ thuật kết hợp. 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang vi 1.2 Một số ví dụ về kỹ thuật kết hợp di truyền mờ .1 Hệ thống ghép cặp di truyền mờ .2 Thiết kế hệ thống di truyền mờ bằng giải thuật di truyền .3 Điều khiển mờ tự động của hệ thống giải thuật di truyền .3 Tóm tắt một số ứng dụng thực tế của hệ kết hợp di truyền mờ.3 Tổng kết và kết luận. 23 CHƢƠNG 2: BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC (AQM) TRONG VIỄN THÔNG 2.2 Kỹ thuật chống mất gói trong các mạng TCP/IP tắc nghẽn .2 Quản lý hàng đợi tích cực (AQM) .1 Lưu lượng tải và phát hiện sớm .2 Tránh thông báo tắc nghẽn xác định .3 RED thích nghi (ARED) .5 Sự đánh giá .6 Sử dụng gói mất để thông báo tắc nghẽn .3 Điều khiển tắc nghẽn máy chủ cuối .1 Điều chỉnh tốc độ truyền tối thiểu .2 Điều chỉnh tăng tuyến tính .4 Điều chỉnh hiệu suất tối ưu .5 Kết luận và công việc tương lai .3 BLUE phương pháp mới cho AQM .2 Sự hạn chế của RED .1 Thuật toán Blue .3 Tìm hiểu về Blue .4 Hiệu quả của ECN timeouts .5 Sự đánh giá .4 Blue cân bằng ngẫu nhiên (SFB) .1 Thuật toán SFB .2 Sự đánh giá .3 Sự hạn chế của SFB .4 SFB với hàm hash động.

71 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang vii 2.4 Kết luận và công việc tương lai. 74 CHƢƠNG 3: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN MỜ CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC (AQM) TRONG VIỄN THÔNG 3.2 AQM sử dụng giải thuật di truyền .1 Sơ đồ tổng quát giả sử có một cấu hình mạng như hình 3.2 Thiết kế thuật toán di truyền mờ .1 Bộ điều khiển mờ .2 Giải thuật di truyền mờ cho tìm kiếm tối ưu các dạng hàm thuộc .6 Hàm thích nghi .3 Mô hình hệ thống .3 Quá trình thực nghiệm .1 Xác định đối tượng .2 Kết quả thực nghiệm thể hiện qua mô phỏng .3 Đánh giá tỷ lệ mất gói dùng RED, BLUE, và Fuzz-GA-AQM. 95 PHẦN PHỤ LỤC. 97 Tài liệu tham khảo.

98 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang viii DANH MỤC CÁC BẢNG BIỂU Bảng 1.1 Kết quả tính toán cho các nhiễm sắc thể .2 Quần thể mới .3 So sánh đặc điểm giữa logic mờ và giải thuật di truyền .4 Phân loại việc kết hợp giữa các hệ thống di truyền mờ .5 Các ứng dụng kỹ thuật FL-GA cho hệ thống điều khiển.6 Ví dụ về hệ thống FL-GA ứng dụng giải bài toán phân tích dữ liệu .7 Những ứng dụng của hệ thống kết hợp di truyền mờ .1 Tỷ lệ mất gói của SFB theo Mbs (1 luồng không đáp ứng) .2 Tỷ lệ mất của SFB (một luồng không đáp ứng, một luồng dao động) .1 Cơ sở luật – các luật ngôn ngữ .80 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Trang ix DANH MỤC CÁC HÌNH VẼ Hình 1.1 Ví dụ về hành vi cửa sổ tắc nghẽn TCP .2 Tiêu đề gói tin TCP/IP .3 Các hành vi mất gói/đánh dấu gói của Red .4 Kiến trúc mạng dịch vụ phân biệt DiffServ .5 Bánh xe roulette .6 Cơ chế lai ghép giữa 2 nhiễm sắc thể.7 Sử dụng giải thuật di truyền để cải tiến hiệu suất của hệ thống mờ .8 Kiến trúc của hệ thống điều khiển tự động giải thuật di truyền .1 Sự phát triển của các thuật toán AQM theo thời gian .2 Mô hình (topo) mạng .3 phát hiện sớm tích cực (maxp = 0.4 Phát hiện sớm tiêu cực (maxp = 0,016) .5 Tác động của AED trên RED-ECN .6 Tác động của maxth và kích thước hàng đợi .7 Thuật toán ARED .8 Các hành vi mất gói/đánh dấu của ARED .9 Phát hiện ngẫu nhiên sớm tĩnh (SRED) .10 RED thích nghi .11 Topo mạng với sự biến đổi RTT .12 RED tĩnh thông qua sự thay đổi RTT .13 RED thích nghi thông qua sự thay đổi RTT .14 Kết quả đã kiểm tra .15 Hiệu suất quản lý hàng đợi.16 Tác động của phát hiện sớm quá tích cực trong RED.18 Thuật toán SUBTCP .20 Tốc độ gửi tối thiểu và hiệu suất của TCP .21 Đồ thị hàng đợi để giảm kích thước segment và tăng kích thước cửa sổ 44 Hình 2.22 Thuật toán SUBTCP dựa trên băng thông .23 Thuật toán dựa trên băng thông SUBTCP .24 Hiệu suất của thuật toán tăng tuyến tính đã sửa đổi.25 Hiệu suất tuyến tính phụ SUBTCP .26 Hiệu suất thông qua lưu lượng lải .27 So sánh hiệu suất .28 Sự mở rộng cho ARED .29 Ví dụ về RED .30 Thuật toán Blue .32 Đồ thị chiều dài hàng đợi của RED và BLUE .33 Hành vi đánh dấu của RED .