Luận Văn Thuật toán gen trong bài toán định tuyến và phân bước sóng mạng cáp quang

Tóm tắt
Trong thời đại công nghệ thông tin CNTT ngày nay sự b ng n c a các d ch v
thông tin đ c biệt là sự phát triển nhanh chóng c a Internet làm gia t ng không ng ng
nhu cầu về dung lượng mạng Trong t nh cảnh đó hệ thống mạng quang ra đời như một
giải pháp tối ưu để giải quyết v ấn đề trên. N i bật là sự ra đời c a mạng gh p kênh phân
bước sóng DM Wavelength Division Multipexing).
Một trong những v ấn đề quan trọng c a mạng quang WDM là v ấn đề đ nh tuyến và
phân bước sóng RWA ( Routing and Wavelength Asignment ) t ức là đ nh tuyến đường đi
cho một bộ các đường quang (lightpath) và phân một bước sóng cho mỗi đường quang
đó. Một trong những phương pháp đưa ra và sẽ được nghiên cứu ở trong khóa luận này là
sử d ng thuật toán gen (Genetic Algorithm) hay còn gọi là thuật toán di truyền để giải bài
toán RWA cho mạng WDM.
2
Mục lục
Tóm t ắt 1
Lời mở đầu . 4
Bảng kí hiệu – chữ viết tắt 6
Chương 1: Hệ thống m ạng quang . 7
1.1. Giới thiệu chung 7
1.2. Lịch sử và sự phát triể n 8
1.3. Đặc điểm của hệ thống mạng quang . 8
1.3.1. Ưu điể m .9
1.3.2. Nhược điểm .9
1.4. Sợi quang . 10
Chương : Mạng quang WDM 12
2.1. Giới thiệ u chung 12
2.2. Nguyên lý hoạ đ ộ ng . 13
2.2.1. Tổng quan . 13
2.2.2. Sơ đồ hoạ đ ộng . 14
2.2.3. Ưu điể m, vấn đ ề t ồn tại và hướng giải quy ế ương l i c a h ệ th ống WDM . 15
2.3. Định tuyế n và gán bước sóng 16
2.3.1. Giới thiệ u chung 16
2.3.2. Tổng quan về định tuy ế n và gán bước sóng (RWA) . 16
Chương 3 : Thuật toán gen 19
3.1. Giới thiệ u . 19
3.2. Thuậ t toán gen trê n máy tính 19
3.3. Các uá rình cơ bả n c a thu ật toán gen 22
3.3.1. Quá trình lai ghép (phép lai) 22
3.3.2. Quá rình đột bi ế n (phép đột bi ế n) 24
3.3.3. Quá trình sinh s ản và ch ọn l ọc (phép tái sinh và phép chọn) . 24
Chương 4 : Thuật toán gen trong bài toán định tuyến và phân bước sóng mạng quang . 25
4.1. Giới thiệ u chung 25
4.2. Sơ lược lý thuyế đồ thị và thu ậm án BFS ch bài án ì đư ờ ng đi ngắ n nh ấ t. 25
4.2.1. Lý thuyế đồ thị . 25
4.2.2. Thuật toán BFS . 26
4.3. Các nghiên cứ u ch bài án định tuyế n và ph n bước sóng m ạ ng WDM . 29
4.4. Thuậ t toán BFD -RWA . 30
4.4.1. Mô tả thuật toán 30
4.4.2. Chứng minh thuật toán . 36
4.5. Thuậ án g n r ng bài án đ ị nh tuyế n và ph n bước sóng (GA – RWA) . 37
4.5.1. Đặt v ấn đ ề . 37
4.5.2. Thuật toán gen trong bài toán RWA 38
4.5.3. Chứng minh thuật toán . 41
Chương 5 : Thực hiện mô phỏng 42
5.1. Công cụ th ực hiệ n . 42
5.3. Kế t qu ả . 45
Chương 6: Kết luận 54
Tài li ệu tham khảo 55