Đề tài 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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Công Đức 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 KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Công Đức 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 KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Nguyễn Minh Hằng HÀ NỘI - 2010 Lời cảm ơn! Trước tiên tôi xin gửi lời cảm ơn sâu sắc nhất đến Tiến sĩ Nguyễn Minh Hằng, người đã tận tình chỉ bảo hướng dẫn tôi trong suốt quá trình thực hiện khóa luận. Tôi xin chân thành cảm ơn các thầy cô trong trường đại học Công Nghệ nói chung và các thầy cô trong bộ môn mạng máy tính và truyền thông nói riêng đã tạo điều kiện thuận lợi để tôi học tập, nghiên cứu, tích lũy kiến thức làm hành trang bước vào cuộc sống. Cuối cùng tôi muốn gửi lời cảm ơn đến gia đình, bạn bè, những người luôn ở bên cạnh động viên tôi trong quá trình thực hiện khóa luận. Vũ Công Đức 1 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ể c hệ hống ạ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 : ạng u ng D .............................................................................................. 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 : Thuậ án g n ...................................................................................................... 19 3.1. Giới thiệu ....................................................................................................................... 19 3.2. Thuật toán gen trên máy tính ...................................................................................... 19 3 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 : Thuậ án g n r ng bài án định u ến và ph n bước ng ạng quang ............................................................................................................................................ 25 4.1. Giới thiệu chung ............................................................................................................ 25 4.2. Sơ lược lý thuyế đồ thị và thuậ á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 : Thực hiện ô 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 4 Lời mở đầu Ngày nay, nhu cầu b ng thông rộng ngày t ng đ c biệt là sự bùng n c a các loại hình d ch v thông tin như Internet và orld ide eb Điều này đòi hỏi phải xây dựng và phát triển các mô hình mạng quang với b ng thông cao. Công nghệ ghép kênh phân bước sóng WDM ra đời như một giải pháp hoàn hảo, cho phép tận d ng tốt b ng thông rộng lớn c a sợi quang. WDM cho phép sử d ng hiệu quả hơn công suất c a các sợi quang, nó cho phép truyền đồng thời nhiều kênh khác nhau theo một sợi quang bằng cách mỗi kênh đó sẽ sử d ng một bước sóng khác nhau. Đ nh tuyến và phân bước sóng RWA ( Routing and Wavelength Asignment ) là một trong những vấn đề quan trong nhất c a mạng WDM. Trong mạng quang một lightpath được đ nh nghĩa là một kết nối giữa hai node trong mạng (có thể qua những node trung gian). Trong mạng WDM hai lightpath có thể sử d ng chung một bước sóng miễn là chúng không sử d ng cùng một sợi quang nào trên đường đi Số bước sóng khác nhau sử d ng có liên quan rất lớn đến chi phí xây dựng cũng như quản lí mạng Do đó vấn đề đ t ra là làm thế nào để giảm thiểu số bước sóng khác nhau được sử d ng Phương pháp được đưa ra và nghiên cứu trong khóa luận này là sử d ng thuật toán gen (Genetic Algorithm) để giảm thiểu số lượng bước sóng khác nhau được sử d ng. Khóa luận gồm 6 chương với nội dung được mô tả sơ bộ dưới đây: Chương 1: Hệ thống mạng quang. Chương này sẽ giới thiệu t ng quan về một hệ thống mạng quang bao gồm l ch sử đ c điểm c a mạng quang và cấu trúc c a sợi quang. Chương 2: Mạng quang WDM Chương này sẽ giới thiệu về mạng WDM về nguyên lý hoạt động và các khái niệm chung về đ nh tuyến và gán bước sóng trong mạng WDM Chương : Thuật toán gen Chương này sẽ giới giới thiệu t ng quan về sử d ng thuật toán di truyền trên máy tính và các phép toán trong thuật toán di truyền Chương : Thuật toán gen trong bài toán định tuyến và phân bước sóng mạng quang Chương này sẽ mô tả chi tiết việc áp d ng thuật toán gen trong bài toán đ nh tuyến và phân bước sóng mạng WDM 5 Chương : Thực hiện mô phỏng. Mô phỏng lại thuật toán trong một số mô hình mạng ví d . Chương 6: Kết luận 6 Bảng kí hiệu – chữ viết tắt BFD Best Fit Decreasing BFS Breadth-First Search GA Genetic Algorithm RWA Routing and Wavelength Asignment SDM Space Devision Multiplexing TDM Time Devision Multiplexing WDM Wavelength Division Multipexing 7 Chương 1: Hệ thống mạng quang 1.1. Giới thiệu chung Hệ thống mạng quang là hệ thống truyền thông tin qua sợi quang. Thông tin được biến đ i thành ánh sáng và được truyền trong sợi quang. Tại thiết b nhận nó biến đ i thành thông tin ban đầu. Lượng thông tin trao đ i trên các hệ thống mạng ngày càng t ng lên rất nhanh. Số lượng truy cập t ng cao mà Internet là một ví d điển hình: số lượng người sử d ng Internet ngày càng t ng nhu cầu về b ng thông cũng ngày càng lớn. Chẳng hạn khi download những dữ liệu hàng GB chúng ta phải chờ đợi hàng ngày mới có được dữ liệu cần thiết ho c với nhu cầu giải tr cao như em video HD nghe nhạc lossless trực tuyến khó có thể thực hiện được với mạng cáp đồng tr c hiện nay. Hình 1.1 Hệ thống mạng sử d ng sóng điện t Hình 1.2 Hệ thống mạng quang Hệ thống mạng quang ra đời ch nh là để giải quyết vấn đề trên Với những ưu điểm như b ng thông lớn có thể tới 5 Tbps độ suy giảm t n hiệu thấp n ng lượng đòi hỏi thấp không b nhiễm sóng điện t khả n ng bảo mật cao V vậy mạng quang được coi 8 như kĩ thuật c a hệ thống mạng b ng thông rộng Do đó ây dựng và phát triển hệ thống mạng quang rất cần thiết cho nhu cầu phát triển thông tin trong tương lai 1.2. Lịch sử và sự phát triển Các phương tiện sơ khai c a thông tin quang là khả n ng nhận biết c a con người về chuyển động, hình dáng và màu sắc c a sự vật thông qua đôi mắt. Tiếp đó một hệ thống thông tin điều chế đơn giản xuất hiện là các ngọn đèn hải đ ng Sau đó n m 1791 VC Chape phát minh ra máy điện báo quang. Thiết b này sử d ng khí quyển làm môi trường truyền dẫn, do đó ch u ảnh hưởng c a các điều kiện thời tiết Để giải quyết hạn chế này Marconi đã sáng chế ra máy điện báo vô tuyến có khả n ng thực hiện trao đ i thông tin giữa những người gửi và người nhận ở xa nhau. Đầu n m 198 A G Bell – người phát minh ra hệ thống điện thoại – đã nghĩ ra một thiết b quang thoại có khả n ng biến đ i dao động c a máy hát thành ánh sáng. Tuy nhiên, sự phát triển tiếp theo c a hệ thống này đã b bỏ rơi do sự ra đời c a hệ thống vô tuyến. Những nghiên cứu hiện đại về thông tin quang được bắt đầu bằng sự phát minh thành công c a Laser n m 196 và bằng khuyến ngh c a Kao và Hockham n m 1966 về việc chế tạo sợi quang có độ t n thất thấp N m 197 Kapron đã chế tạo ra các sợi quang trong suốt có độ suy hao truyền dẫn khoảng 2 dB/km Được c vũ bởi thành công này, các nhà khoa học và kĩ sư trên toàn thế giới đã bắt đầu tiến hành các hoạt động nghiên cứu, phát triển, và kết quả là các công nghệ mới về giảm suy hao truyền dẫn, t ng b ng thông … đã được phát triển thành công trong những n m 7 Hơn nữa, trong những n m 70, Laser bán dẫn có khả n ng thực hiện dao động liên t c ở nhiệt độ cao đã được chế tạo. Tu i thọ c a nó ước lượng hơn 1 n m Dựa trên các công nghệ sợi quang và Laser bán dẫn giờ đây có thể gửi một khối lượng lớn các tín hiệu âm thanh/dữ liệu đến các đ a điểm cách xa hàng 100 km bằng một sợi quang có độ dày như một sợi tóc 1.3. Đặc điểm c hệ hống ạng quang 9 1.3.1. Ưu điểm  B ng thông lớn đầy tiềm n ng: tần số sóng mạng quang trong khoảng 1 13 đến 10 16 H cung cấp b ng thông lớn hơn nhiều so với hệ thống cáp đồng tr c khoảng 5 Mh Do đó dung lượng mạng c a hệ thống mạng quang lớn hơn nhiều so với hệ thống mạng cáp đồng tr c  Sợi quang k ch thước nhỏ và nh : sợi quang có bán k nh rất nhỏ thường chỉ bằng sợi tóc V thế cho d được ph thêm những lớp bảo vệ th vẫn nhỏ và nh hơn nhiều so với cáp đồng Điều đó giúp sợi quang có khả n ng linh hoạt trong việc lưu trữ lắp đ t, vận chuyển  Cách li điện, nhiễu: sợi quang được chế tạo t th y tinh ho c chất d o Đó là những vật liệu cách điện, không b ảnh hưởng bới nhiễu điện t và các tần số vô tuyến. Vì thế hệ thống mạng quang có thể truyền tốt dữ liệu qua những môi trường nhiều sóng điện t  Nguyên liệu r : chất d o và th y tinh là những nguyên liệu rất r so với nguyên liệu c a cáp đồng Do đó khi bài toán về công nghệ chế tạo được giải thì hệ thống quang sẽ có tính kinh tế hơn hệ thống cáp đồng rất nhiều.  Tính bảo mật: một đ c điểm rất quan trọng c a sợi quang là có độ an toàn, bảo mật cao, tu i thọ dài và có khả n ng đề kháng môi trường lớn, dễ bảo dưỡng. Nhờ những ưu điểm này, sợi quang được sử d ng cho các mạng lưới điện thoại, máy tính, phát thanh truyền h nh b ng thông rộng đ c biệt là những ứng d ng cần tính bảo mật cao như trong quân đội, ngân hàng và các ứng d ng truyền dữ liệu.  Suy hao thấp: đ c tính này giúp cho việc lắp đ t hệ thống quang dễ bớt phức tạp hơn và chi ph t hơn cho các bộ khuyến đại đường truyền 1.3.2. Nhược điểm Tuy có nhiều ưu điểm vượi trội nhưng hệ thống mạng quang cũng có một vài nhược điểm: 10  Khó đấu nối  Giá thành cao: m c dù giá nguyên liệu r nhưng do công nghệ chế tạo vẫn còn hạn chế. 1.4. Sợi quang Sợi quang là những dây nhỏ và d o truyền các ánh sánh nhìn thấy được và các tia hồng ngoại. Chúng có lõi (Core) ở giữa, phần bao bọc xung quanh lõi gọi là áo (Cladding) và vỏ bọc ngoài cùng (Buffer Coating) Để ánh sáng có thể phản xạ một cách hoàn toàn trong lõi thì chiết suất c a lõi phải lớn hơn chiết suất c a áo. Hình 1.3 Sợi quang Vỏ bọc ở phía ngoài bảo vệ sợi quang khỏi b ẩm và n mòn Lõi và áo được làm bằng th y tinh hay chất d o (silicast, chất d o, sợi quang kết tinh) có chiết suất khác nhau. Khi truyền trong sợi quang, sóng ánh sáng b chi phối bởi một số hiện tượng sau:  Suy giảm (Attenuation): suy giảm trong sợi quang do hai nguyên nhân chính là sự hấp th c a vật liệu và tán xạ ReyLeng. Hấp th vật liệu khá nhỏ lên có thể bỏ qua. Tán xạ ReyLeng là loại tán xạ làm lệch hướng mạnh các ánh sáng có bước sóng ngắn Do đó có thể làm giảm tán xạ ReyLeng bằng cách t ng độ dài bước sóng.  Tán sắc (Dispersion): là hiện tượng các thành phần khác nhau c a tín hiệu cần truyền đi với tốc độ khác nhau trong sợi quang. Tán sắc gây ra hiện tượng giãn 11 xung ánh sáng ở đầu ra, gây nhiễu chồng ph và là nguyên nhân chính dẫn đến hạn chế c a khoảng cách truyền trong sợi quang ngày nay.  Các hiệu ứng phi tuyến: Khi truyền nhiều mode trong sợi quang, hiện tượng phi tuyến gây ra hiện tượng nhiễu tại đầu thu và giảm công suất tín hiệu truyền. 12 Chương : ạng u ng D 2.1. Giới thiệu chung Sự phát triển nhanh chóng c a các mô hình truyền số liệu đ c biệt là Internet đã làm bùng n nhu cầu t ng b ng thông Nhu cầu b ng thông t ng đột biến với nhiều ứng d ng mới phong phú như thương mại điện tử, video yêu cầu, truyền hình qua Internet (IPTV),...T đó cho thấy nhu cầu sử d ng b ng thông rộng đang rất bức thiết. Trong bối cảnh Internet Protocol IP đang n i lên như là nền tảng chung c a mọi loại hình d ch v trong tương lai các nhà cung cấp d ch v truyền dẫn bắt buộc phải xem xét lại phương thức truyền dẫn nhằm tối ưu hơn cho việc tận d ng b ng thông Để thích ứng với sự phát triển không ng ng đó và thỏa mãn yêu cầu tính linh hoạt về thay đ i mạng, các công nghệ truyền dẫn khác nhau đã được nguyên cứu, triển khai và thử nghiệm và đưa vào ứng d ng như:  Truyền dẫn ghép kênh phân không gian SDM (Space Devision Multiplexing): đây là một phương pháp rất đơn giản, chỉ đơn thuần là t ng số lượng sợi quang, tốc độ đường truyền vẫn giữ nguyên. Ta có thể chọn SDM nếu tuyến đường cần t ng b ng thông đã có sẵn số lượng các sợi quang chưa d ng và khoảng cách truyền đ ngắn để không cần dùng các bộ l p, bộ khuyếch đại.  Truyền dẫn ghép kênh phân thời gian TDM (Time Devision Multiplexing): ở phương pháp này thời gian sử d ng, tức là thời gian sử d ng đường truyền được chia thành nhiều khung. Mỗi khung được chia thành nhiều khe thời gian và mỗi người sẽ sử d ng một khe thời gian dành riêng cho m nh để ph c v việc truyền tin Hình 2.1 Hệ thống TDM 13  Truyền dẫn gh p kênh phân bước sóng WDM (Wavelength Devision Multiple ing : đây là phương pháp gh p nhiều bước sóng để có thể truyền trên một sợi quang, không cần t ng tốc độ truyền dẫn trên một bước sóng. Hình 2.2 Hệ thống WDM Trong những phương pháp trên công nghệ gh p kênh phân bước sóng DM được ưa chuộng hơn cả Điều này là 2 công nghệ SDM và TDM điều bộc lộ những khuyết điểm đáng kể:  Với SDM khi khoảng cách truyền xa cần phải lắp thêm các bộ l p và bộ khuyếch đại Điều này sẽ làm cho chi ph t ng lên rất lớn do mỗi sợi quang được lắp thêm điều cần một số lượng bộ l p, bộ khuyếch đại như nhau  Với TDM cũng có chi ph nắp đ t hệ thống tương đối cao đ c biệt TDM gây lãng phí một số kênh thông tin khi mỗi khe thời gian được dự trữ ngay cả khi không có dữ liệu để gửi và ph a thi khó kh n khi phân biệt các khe thời gian thuộc kênh nào để giải ghép kênh tín hiệu. WDM chính là tiến bộ lớn nhất trong công nghệ truyền thông quang, nó cho phép t ng dung lượng c a kênh mà không cần t ng tốc độ đường truyền hay dùng thêm các sợi quang. 2.2. Nguyên lý hoạ động 2.2.1. Tổng quan 14 Nguyên lý cơ bản c a gh p kênh phân bước sóng là công nghệ truyền đồng thời nhiều bước sóng tín hiệu quang trong một sợi quang. Ở đầu phát, nhiều tín hiệu quang có bước sóng khác nhau được t hợp lại gh p kênh được truyền đi trên một sợi quang. Ở đầu thu, tín hiệu t hợp đó được phân giản ra (tách kênh), khôi ph c lại các tín hiệu gốc rồi chia vào các thiết b đầu cuối khác nhau. 2.2.2. Sơ đồ hoạ động Như minh họa trên hình 2.3 để đảm bảo việc truyền nhận nhiều bước sóng trên một sợi quang, hệ thống WDM phải hoạt động dựa các chức n ng sau: Hình 2.3 Nguyên lý hoạt động c a hệ thống  Phát tín hiệu: trong hệ thống WDM, nguồn phát quang dùng là laser. Yêu cầu đối với nguồn phát laser là phải có độ rộng ph h p bước sóng phát n đ nh, mức công suất phát bước sóng trung tâm độ rộng ph phải nằm trong giới hạn cho phép  Ghép/tách tín hiệu: ghép tín hiệu WDM là sự kết hợp một số nguồn sáng khác nhau thành một luồng tín hiệu ánh sáng