Ứ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

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.lrc-tnu.edu.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. TS. Lê Bá Dũng

Thái Nguyên, 2010

Trang i

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC

KỸ THUẬT CÔNG NGHIỆP

CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM

Độc lập - Tự do - Hạnh phúc

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

PGS.TS Lê Bá Dũng

HỌC VIÊN

Lê Hoàng

BAN GIÁM HIỆU KHOA SAU ĐẠI HỌC

Trang ii

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

Trang iii

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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. TS. Lê Bá Dũng, Viện công nghệ thông tin, Viện khoa học và

công nghệ Việt Nam. [email protected].

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.

[email protected].

đã 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

Trang iv

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

Trang v

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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 Giới thiệu............................................................................................................... 1

1.1.1 Điều khiển tắc nghẽn trên mạng internet....................................................... 1

1.1.2 Chất lượng dịch vụ trên internet .................................................................... 2

1.1.3 Cấu trúc luận văn ........................................................................................... 3

1.2 Tổng quan về AQM và TCP ................................................................................. 4

1.2.1 TCP và quản lý hàng đợi tích cực (AQM)..................................................... 4

1.2.2 Các dịch vụ tích hợp và phân biệt................................................................ 11

1.3 Giải thuật di truyền.............................................................................................. 12

1.3.1 Giới thiệu ..................................................................................................... 12

1.3.2 Giải thuật di truyền và tìm kiếm tối ưu........................................................ 13

1.3.3 Cấu trúc một giải thuật di truyền ................................................................. 14

1.3.3.1 Cấu trúc một giải thuật di truyền đơn giản........................................... 14

1.3.3.2 Các phép toán của giải thuật di truyền ................................................. 14

1.3.3.2.1 Sinh sản (Reproduction)................................................................ 14

1.3.3.2.2 Lai ghép (Crossover)..................................................................... 16

1.3.3.2.3 Đột biến (Mutation)....................................................................... 17

1.3.4 Ứng dụng của giải thuật di truyền ............................................................... 18

1.4 Giải thuật di truyền mờ ....................................................................................... 18

1.4.1 Giới thiệu ..................................................................................................... 18

1.4.2 Giải thuật di truyền kết hợp với logic mờ.................................................... 19

1.4.2.1 Phân loại kỹ thuật kết hợp .................................................................... 20

Trang vi

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1.4.2.2 Một số ví dụ về kỹ thuật kết hợp di truyền mờ .................................... 20

1.4.2.2.1 Hệ thống ghép cặp di truyền mờ ................................................... 20

1.4.2.2.2 Thiết kế hệ thống di truyền mờ bằng giải thuật di truyền............. 21

1.4.2.2.3 Điều khiển mờ tự động của hệ thống giải thuật di truyền............. 22

1.4.2.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ờ............ 23

1.4.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.1 Giới thiệu............................................................................................................. 25

2.2 Kỹ thuật chống mất gói trong các mạng TCP/IP tắc nghẽn................................ 26

2.2.1 Giới thiệu ..................................................................................................... 26

2.2.2 Quản lý hàng đợi tích cực (AQM)............................................................... 26

2.2.2.1 Lưu lượng tải và phát hiện sớm............................................................ 27

2.2.2.2 Tránh thông báo tắc nghẽn xác định .................................................... 30

2.2.2.3 RED thích nghi (ARED) ...................................................................... 31

2.2.2.4 Độ nhạy RTT........................................................................................ 34

2.2.2.5 Sự đánh giá ........................................................................................... 36

2.2.2.6 Sử dụng gói mất để thông báo tắc nghẽn ............................................. 38

2.2.3 Điều khiển tắc nghẽn máy chủ cuối............................................................. 41

2.2.3.1 Điều chỉnh tốc độ truyền tối thiểu ........................................................ 41

2.2.3.2 Điều chỉnh tăng tuyến tính ................................................................... 44

2.2.4 Điều chỉnh hiệu suất tối ưu .......................................................................... 48

2.2.5 Kết luận và công việc tương lai ................................................................... 50

2.3 BLUE phương pháp mới cho AQM.................................................................... 51

2.3.1 Giới thiệu ..................................................................................................... 51

2.3.2 Sự hạn chế của RED .................................................................................... 52

2.3.3 Blue .............................................................................................................. 54

2.3.3.1 Thuật toán Blue .................................................................................... 55

2.3.3.3 Tìm hiểu về Blue .................................................................................. 56

2.3.3.4 Hiệu quả của ECN timeouts................................................................. 59

2.3.3.5 Sự đánh giá ........................................................................................... 61

2.3.4 Blue cân bằng ngẫu nhiên (SFB)................................................................. 63

2.3.4.1 Thuật toán SFB..................................................................................... 63

2.3.4.2 Sự đánh giá ........................................................................................... 66

2.3.4.3 Sự hạn chế của SFB.............................................................................. 68

2.3.4.4 SFB với hàm hash động........................................................................ 71

Trang vii

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

2.3.4.5 Độ nhạy RTT........................................................................................ 74

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.1 Mở đầu ................................................................................................................ 76

3.2 AQM sử dụng giải thuật di truyền ...................................................................... 77

3.2.1 Sơ đồ tổng quát giả sử có một cấu hình mạng như hình 3.1 ....................... 77

3.2.2 Thiết kế thuật toán di truyền mờ.................................................................. 78

3.2.2.1 Bộ điều khiển mờ ................................................................................. 78

3.2.2.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 ....... 80

3.2.3.1 Mã hoá .................................................................................................. 81

3.2.2.4 Lai tạo................................................................................................... 84

3.2.2.5 Đột biến ................................................................................................ 84

3.2.2.6 Hàm thích nghi ..................................................................................... 84

3.2.3 Mô hình hệ thống......................................................................................... 85

3.3 Quá trình thực nghiệm ........................................................................................ 85

3.3.1 Xác định đối tượng ...................................................................................... 85

3.3.2 Kết quả thực nghiệm thể hiện qua mô phỏng .............................................. 87

3.3.3 Đánh giá tỷ lệ mất gói dùng RED, BLUE, và Fuzz-GA-AQM................... 91

KẾT LUẬN ............................................................................................................. 95

PHẦN PHỤ LỤC...................................................................................................... 97

Tài liệu tham khảo..................................................................................................... 98

Trang viii

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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ể ...................................................15

Bảng 1.2 Quần thể mới .............................................................................................16

Bảng 1.3 So sánh đặc điểm giữa logic mờ và giải thuật di truyền............................19

Bảng 1.4 Phân loại việc kết hợp giữa các hệ thống di truyền mờ.............................20

Bảng 1.5 Các ứng dụng kỹ thuật FL-GA cho hệ thống điều khiển...........................21

Bảng 1.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.........21

Bảng 1.7 Những ứng dụng của hệ thống kết hợp di truyền mờ................................23

Bảng 2.1 Tỷ lệ mất gói của SFB theo Mbs (1 luồng không đáp ứng) ......................66

Bảng 2.2 Tỷ lệ mất của SFB (một luồng không đáp ứng, một luồng dao động)......73

Bảng 3.1 Cơ sở luật – các luật ngôn ngữ ..................................................................80

Trang ix

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.......................................................7

Hình 1.2 Tiêu đề gói tin TCP/IP .................................................................................9

Hình 1.3 Các hành vi mất gói/đánh dấu gói của Red................................................10

Hình 1.4 Kiến trúc mạng dịch vụ phân biệt DiffServ ...............................................12

Hình 1.5 Bánh xe roulette .........................................................................................16

Hình 1.6 Cơ chế lai ghép giữa 2 nhiễm sắc thể.........................................................17

Hình 1.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ờ ..........21

Hình 1.8 Kiến trúc của hệ thống điều khiển tự động giải thuật di truyền.................22

Hình 2.1 Sự phát triển của các thuật toán AQM theo thời gian................................25

Hình 2.2 Mô hình (topo) mạng .................................................................................28

Hình 2.3 phát hiện sớm tích cực (maxp = 0.250)......................................................28

Hình 2.4 Phát hiện sớm tiêu cực (maxp = 0,016) .....................................................29

Hình 2.5 Tác động của AED trên RED-ECN ...........................................................30

Hình 2.6 Tác động của maxth và kích thước hàng đợi ..............................................31

Hình 2.7 Thuật toán ARED.......................................................................................32

Hình 2.8 Các hành vi mất gói/đánh dấu của ARED .................................................32

Hình 2.9 Phát hiện ngẫu nhiên sớm tĩnh (SRED).....................................................33

Hình 2.10 RED thích nghi.........................................................................................34

Hình 2.11 Topo mạng với sự biến đổi RTT..............................................................34

Hình 2.12 RED tĩnh thông qua sự thay đổi RTT ......................................................35

Hình 2.13 RED thích nghi thông qua sự thay đổi RTT ............................................35

Hình 2.14 Kết quả đã kiểm tra ..................................................................................36

Hình 2.15 Hiệu suất quản lý hàng đợi.......................................................................37

Hình 2.16 Tác động của phát hiện sớm quá tích cực trong RED..............................38

Hình 2.17 Mạng ví dụ ...............................................................................................40

Hình 2.18 Thuật toán SUBTCP ................................................................................42

Hình 2.19 Topo mạng ...............................................................................................42

Hình 2.20 Tốc độ gửi tối thiểu và hiệu suất của TCP...............................................43

Hình 2.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 ..............................................46

Hình 2.23 Thuật toán dựa trên băng thông SUBTCP ...............................................46

Hình 2.24 Hiệu suất của thuật toán tăng tuyến tính đã sửa đổi.................................47

Hình 2.25 Hiệu suất tuyến tính phụ SUBTCP ..........................................................48

Hình 2.26 Hiệu suất thông qua lưu lượng lải............................................................49

Hình 2.27 So sánh hiệu suất......................................................................................50

Hình 2.28 Sự mở rộng cho ARED ............................................................................51

Hình 2.29 Ví dụ về RED...........................................................................................53

Hình 2.30 Thuật toán Blue ........................................................................................55

Hình 2.31 Topo mạng ...............................................................................................56

Hình 2.32 Đồ thị chiều dài hàng đợi của RED và BLUE .........................................57

Hình 2.33 Hành vi đánh dấu của RED......................................................................58

Hình 2.34 Hành vi đánh dấu của BLUE (pm)............................................................59