Luận văn Nghiên cứu ứng dụng thuật toán aco cho việc định tuyến mạng IP

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG NGUYỄN THỊ MAI PHƯƠNG NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN ACO CHO VIỆC ĐỊNH TUYẾN MẠNG IP Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng – Năm 2013 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: TS. Nguyễn Tấn Khôi Phản biện 1: TS. Nguyễn Văn Hiệu Phản biện 2: GS. TS. Nguyễn Thanh Thủy Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ Kỹ thuật họp tại Đại học Đà Nẵng vào ngày 16 tháng 11 năm 2013. Có thể tìm hiểu luận văn tại: - Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng - Trung tâm Học liệu, Đại học Đà Nẵng 1 MỞ ĐẦU 1. Lí do chọn đề tài Chỉ trong vòng hơn một thập niên qua, Internet đã phát triển rất nhanh chóng với nhiều mục đích sử dụng khác nhau: từ khoa học kỹ thuật, kinh tế, giáo dục cho đến những hoạt động xã hội. Để đáp ứng nhu cầu hết sức phong phú và đa dạng của những người sử dụng đầu cuối, các nhà cung cấp dịch vụ truyền thông qua Internet đứng trước những thách thức không chỉ đòi hỏi phải nâng cấp thêm các thiết bị mạng mà còn phải cải tiến nhằm tận dụng tối đa các cơ sở hạ tầng mạng hiện có để có thể cung cấp các dịch vụ với chất lượng cao và chi phí hợp lý.Bài toán định tuyến cần được quan tâm nghiên cứu để nhằm tối ưu hóa hiệu suất sử dụng tài nguyên mạng.Trên thế giới đã có nhiều nghiên cứu về các phương pháp định tuyến, với mục đích chủ yếu là tìm ra những phương pháp định tuyến thích hợp để áp dụng vào thực tế mạng lưới [9]. Bài toán tìm kiếm luôn được nhiều người quan tâm, đặc biệt là tìm kiếm tối ưu toàn cục. Một thuật toán được xem là lý thuyết vững chắc trong việc giải các bài toán tìm kiếm tối ưu toàn cục đã có nhiều ứng dụng thực tế như: tìm kiếm các trang web cần tìm trên mạng, kế hoạch sắp xếp thời khóa biểu cho các y tá trong bệnh viện, tìm kiếm đường đi tối ưu cho những người lái xe hơi, định hướng trong mạng truyền thông đấy là thuật toán kiến (ACS – Ant Colony Search hoặc ACO - Ant Colony Optimization). Xuất phát từ tính cấp thiết của vấn đề và nhu cầu thực tiễn, tôi chọn đề tài luận văn cao học: Nghiên cứu ứng dụng thuật toán ACO cho việc tối ưu hóa quá trình định tuyến trên mạng IP.Nhằm nghiên cứu giải quyết các vấn đề đặt ra. 2 2. Mục đích nghiên cứu - Tìm hiểu và so sánh phương pháp tối ưu hóa - Triển khai thuật toán định tuyến cho định tuyến mạng sử dụng kỹ thuật cập nhật nguồn. - Xây dựng ứng dụng mô phỏng quá trình định tuyến trên mạng sử dụng thuật toán đàn kiến đã triển khai 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu - Các giao thức cơ sở của mạng máy tính - Giải thuật định tuyến trên mạng IP - Giải thuật tối ưu hóa đàn kiến ACO Phạm vi nghiên cứu - Tìm hiểu lý thuyết và xây dựng mô hình mô phỏng 4. Phương pháp nghiên cứu Nghiên cứu lý thuyết - Tìm hiểu các phương pháp định tuyến hiện nay - Tìm hiểu cơ sở lý thuyết về thuật toán tối ưu hóa đàn kiến - Tìm hiểu khả năng thích nghi của thuật toán tối ưu hóa đàn kiến với các giao thức định tuyến Nghiên cứu thực nghiệm - Xây dựng ứng dụng mô phỏng sự hoạt động của thuật toán tối ưu hóa đàn kiến trong định tuyến mạng 5. Ý nghĩa khoa học và thực tiễn của đề tài Ý nghĩa khoa học - Ứng dụng thuật toán đàn kiến để giải các bài toán tối ưu tổ hợp như bài toán chào hàng, bài toán gán, bài toán tô màu đồ thị, bài toán lập lịch, bài toán tìm đường đi ngắn nhất 3 - Ứng dụng thuật toán đàn kiến để giải các bài toán định tuyến cho các mạng IP Ý nghĩa thực tiễn - Ứng dụng thuật toán đàn kiến trong tối ưu định tuyến mạng tìm đường đi tối ưu cho các gói tin trên mạng - Giảm thiểu chi phí định tuyến bằng cách truyền đi những con kiến với kích thước nhỏ thay vì phải truyền đi bảng định tuyến - Những con kiến khi định tuyến thực hiện cập nhật thông tin định tuyến chỉ cần cập nhật một mục trong bảng pheromone độc lập thay vì phải cập nhật toàn bộ bảng định tuyến - Những con kiến có thể gắn vào các gói dữ liệu để truyền đi trên mạng - Thuật toán đàn kiến rất phù hợp cho các mạng năng động 6. Cấu trúc luận văn Nội dung chính của luận văn này được chia thành ba chương với nội dung như sau: Chương 1 - Tổng quan định tuyến mạng: chương này trình bày lý thuyết đồ thị, định tuyến mạng và các giao thức định tuyến Chương 2 - Thuật toán tối ưu đàn kiến ACO: chương này nói về thuật toán đàn kiến ACO, các bài toán tối ưu hóa tổ hợp và tối ưu hóa đàn kiến (ACO), nêu ra thuật toán đàn kiến (ACO) Chương 3 - Ứng dụng thuật toán đàn kiến ACO vào định tuyến mạng IP: chương này trình bày kết quả thử nghiệm về việc định tuyến mạng IP bằng thuật toán ACO 4 CHƯƠNG 1 TỔNG QUAN ĐỊNH TUYẾN MẠNG 1.1. GIỚI THIỆU 1.1.1. Lý thuyết đồ thị a. Định nghĩa đồ thị b. Phân loại đồ thị Có thể phân loại đồ thị theo đặc tính, số lượng của tập các cạnh E. Cho đồ thị G = (V,E) - G được gọi là đơn đồ thị nếu giữa hai đỉnh u và v của V có nhiều nhất là một cạnh trong E nối từ u tới v - G được gọi là đa đồ thị nếu giữa hai đỉnh u và v của V có thể có nhiều hơn một cạnh trong E nối từ u tới v - G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kì cũng là cạnh nối hai đỉnh u, v - G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới đỉnh u c. Chu trình trong đồ thị d. Cây khung và cây khung nhỏ nhất 1.1.2. Định tuyến Định tuyến là quá trình tìm đường đi để truyền tải thông tin trong liên mạng từ nguồn đến đích.Định tuyến là khái niệm cốt lõi của mạng IP và nhiều loại mạng khác nhau. 1.1.3. Phân loại định tuyến a. Định tuyến tĩnh b. Định tuyến động 5 1.1.4. Bảng định tuyến Bảng định tuyến có rất nhiều dạng là: - Địa chỉ đích của mạng, mạng con và hệ thống độc lập - Địa chỉ IP giao diện router kế tiếp phải đến - Giao tiếp vật lý trên router phải sử dụng để đến chặn kế tiếp - Mặt nạ mạng của địa chỉ đích - Khoảng cách quản trị - Thời gian (tính theo giây) từ khi router cập nhật lần cuối 1.2. CÁC THUẬT TOÁN ĐỊNH TUYẾN 1.2.1. Thuật toán định tuyến theo vectơ khoảng cách 1.2.2. Thuật toán định tuyến theo trạng thái đường liên kết 1.3. CÁC GIAO THỨC ĐỊNH TUYẾN Hình 1.10. Các giao thức định tuyến 1.3.1. Giao thức định tuyến RIP 1.3.2. Giao thức định tuyến OSPF 1.3.3. Giao thức định tuyến EIGRP 1.4. KẾT LUẬN CHƯƠNG 1 Trong chương này trình bày tổng quan một số cơ sở lý thuyết về định tuyến mạng, các thuật toán và các giao thức định tuyến để từ đó đưa ra hướng giải quyết đề tài và sau này ứng dụng vào việc giải quyết cho bài toán định tuyến mạng IP. 6 CHƯƠNG 2 THUẬT TOÁN TỐI ƯU ĐÀN KIẾN ACO 2.1. GIỚI THIỆU 2.1.1. Bài toán tối ưu hóa tổng hợp Bài toán tối ưu hóa tổ hợp (Combinatorial optimization) liên quan tới việc tìm giá trị cho các biến số rời rạc như lời giải tối ưu mà có lưu ý tới hàm đánh giá cho trước. Bài toán có thể là bài toán tìm cực đại hoặc tìm cực tiểu. Một cách thông thường, bài toán tối ưu hoá tổ hợp được cho dưới dạng bộ 3 (S, f, Ω). Trong đó S là tập các lời giải ứng cử viên, f là hàm đánh giá (hàm này gán giá trị f(s) cho mỗi lời giải ứng cử viên sÎ S), và Ω là tập các ràng buộc của bài toán. Các lời giải thuộc tập S* Í S thỏa mãn tập các ràng buộc Ω gọi là lời giải khả thi. Mục tiêu bài toán là tìm ra một lời giải khả thi tối ưu toàn cục s*. Với các bài toán tối ưu hóa cực tiểu là tìm lời giải s* với giá nhỏ nhất, nghĩa là f(s*) ≤ f(s) với mọi lời giải s Í S. Ngược lại bài toán tối ưu hóa cực đại là tìm lời giải s* với giá lớn nhất, nghĩa là f(s*) ≥ f(s) với mọi lời giải s Í S. Bài toán tối ưu hóa tổ hợp có thể chia 2 loại: Bài toán tĩnh và bài toán động. 2.1.2. Bài toán tối ưu hóa đàn kiến ACO (Ant Colony optimization – Tối ưu đàn kiến) là một phương pháp nghiên cứu lấy ý tưởng từ việc mô phỏng hành vi của đàn kiến trong tự nhiên nhằm mục tiêu giải quyết các bài toán tối ưu phức tạp. Được giới thiệu lần đầu tiên vào năm 1991 bởi A. Colorni và M. Dorigo, giải thuật kiến đã nhận được sự chú ý rộng lớn nhờ vào khả năng tối ưu của nó trong nhiều lĩnh vực khác nhau. Khái niệm ACO lấy ý tưởng từ việc quan sát hành vi của đàn kiến trong quá trình chúng tìm kiếm nguồn thức ăn. Người ta đã khám phá ra rằng, 7 đàn kiến luôn tìm được đường đi ngắn nhất từ tổ của chúng đến nguồn thức ăn. Phương tiện truyền đạt tín hiệu được kiến sử dụng để thông báo cho những con khác trong việc tìm đường đi hiệu quả nhất chính là mùi của chúng (Pheromone). Kiến để lại vệt mùi trên mặt đất khi chúng di chuyển với mục đích đánh dấu đường đi cho các con theo sau. Vệt mùi này sẽ bay hơi dần và mất đi theo thời gian, nhưng nó cũng có thể được củng cố nếu những con kiến khác tiếp tục đi trên con đường đó lần nữa. Dần dần, các con kiến theo sau sẽ lựa chọn đường đi với lượng mùi dày đặc hơn, và chúng sẽ làm gia tăng hơn nữa nồng độ mùi trên những đường đi được yêu thích hơn. Các đường đi với nồng độ mùi ít hơn sẽ bị loại bỏ và cuối cùng, tất cả các đàn kiến sẽ cùng kéo về một đường đi ngắn nhất từ tổ đến nguồn thức ăn của chúng (Dorigo và Gambardella 1996) Để mô phỏng hành vi của các con kiến thực, Dorigo xây dựng các con kiến nhân tạo (artificial ants) cũng có đặc trưng sản sinh ra vết mùi để lại trên đường đi và khả năng lần vết theo nồng độ mùi để lựa chọn con đường có nồng độ mùi cao hơn để đi. Gắn với mỗi cạnh (i,j) nồng độ vết mùi t ijvà thông số heuristic h ij trên cạnh đó [6][7]. Ban đầu, nồng độ mùi trên mỗi cạnh (i,j) được khởi tạo bằng một hằng số c, hoặc được xác định theo công thức: t ij= t 0 = nnC m , " (i,j) (2.1) Trong đó: t ij: nồng độ vệt mùi trên cạnh i, j m: số lượng kiến Cnn: chiều dài hành trình cho bởi phương pháp tìm kiếm gần nhất. 8 Tại đỉnh i, một con kiến k sẽ chọn đỉnh j chưa được đi qua trong tập láng giềng của I theo một quy luật phân bố xác suất được xác định theo công thức sau: ij ij ij [ ] [ ] , [ ] [ ]k i k il ill N p a b a b t h t h Î = å jÎ kiN (2.2) Trong đó: ij kp : xác suất con kiến k lựa chọn cạnh i,j a : hệ số điều chỉnh ảnh hưởng của t ij ijn : thông tin heuristic giúp đánh giá chính xác sự lựa chọn của con kiến khi quyết định đi từ đỉnh i qua đỉnh j; được xác định theo công thức: ijn = ij 1 d (2.3) dij :khoảng cách giữa đỉnh i và đỉnh j b : hệ số điều chỉnh ảnh hưởng của ijn k iN : tập các đỉnh láng giềng của i mà con kiến k chưa đi qua Quy luật này mô phỏng hoạt động của một vòng quay xổ số nên được gọi là kỹ thuật bánh xe xổ số. Cho một hằng số 0n 0 nq 1 và một số 0n qn 1 được tạo ra một cách ngẫu nhiên. Con kiến k ở đỉnh i sẽ lựa chọn đỉnh j kế tiếp để đi theo một quy tắc lựa chọn được mô tả bởi công thức sau: = ∈ [ ] , ế ≤ , ế ượ ạ (2.4) 2.1.3. Một số thuật toán ACO Thuật toán Ant System (AS) là thuật toán đầu tiên trong lớp 9 các thuật toán ACO được đề xuất bởi Dorigo trong luận án tiến sĩ của ông năm 1992. AS là kết quả của việc nghiên cứu trên hướng tiếp cận trí tuệ máy tính nhằm tối ưu tổ hợp, hướng đến giải quyết bài toán tìm đường đi tối ưu trong đồ thị. AS ban đầu được áp dụng cho bài toán người du lịch (TSP). Mặc dù thuật toán AS vẫn còn thua kém các thuật toán tốt nhất trong việc giải quyết bài toán trên, tuy nhiên ý tưởng của nó thực sự là mới mẻ và tỏ ra có triển vọng. Về sau đã có rất nhiều cải tiến của thuật toán này do chính Dorigo đề xuất, cũng như rất nhiều các thuật toán ACO khác đều dựa trên ý tưởng của thuật toán AS song đã khắc phục được một số nhược điểm của thuật toán này. Có thể kể tên 2 cải tiến nổi trội nhất của thuật toán AS là thuật toán ACS và thuật toán MMAS [8] [13]. Cũng vào năm 1992, tại hội nghị sự sống nhân tạo lần đầu tiên ở châu Âu, Dorigo và các cộng sự đã công bố bài: sự tối ưu được phân bố bởi đàn kiến. Tiếp theo tại hội nghị quốc tế thứ hai về giải quyết các vấn đề song song trong tự nhiên ở Hà Lan (1992), ông và các cộng sự đã công bố bài: nghiên cứu về các đặc tính của một giải thuật kiến [6]. Kể từ năm 1995 Dorigo, Gambardella và Stützle đã phát triển các sơ đồ AS khác nhau. Dorigo và Gambardella đã đề xuất hệ thống đàn kiến (Ant Colony System, hay ACS) trong khi Stützle and Hoos đề xuất MAX-MIN Ant System (MMAS). Tất cả đều áp dụng cho bài toán người du lịch đối xứng hay không đối xứng và cho kết quả mỹ mãn. Hệ thống Max-Min Ant System là một hệ thống cải tiến hệ thống Ant System ban đầu và được đánh giá là hệ thống tính toán trong tương lai. Dorigo, Gambardella and Stützle cũng đề xuất những phiên bản lai của ACO với tìm kiếm địa phương [7]. 10 Vào năm 1995, L.M. Gambardella và M. Dorigo đã đề xuất hệ thống Ant-Q, là một cách tiếp cận học tăng cường cho bài toán TSP và nó được áp dụng trong Học Máy. Tiếp đó, vào năm 1996, trong bài báo công nghệ của mình tại Bruxelles, M. Dorigo và L.M. Gambardella đã công bố hệ thống Ant Conoly System. Đây là hệ thống đề cập đến cách học phối hợp áp dụng cho bài toán TSP. Sau đó, vào năm 1997, G. Di Caro và M. Dorigo đã đề xuất hệ thống AntNet. Đây là cách tiếp cận về định hướng sự thích nghi. Và phiên bản cuối cùng của hệ thống AntNet về điều khiển mạng truyền thông đã được công bố vào năm 1998 [7]. Cũng trong năm 1997, hệ thống Rank-based Ant System, một hệ thống cải tiến hệ thống kiến ban đầu về nghiên cứu hệ thống tính toán đã được đề xuất bởi B. Bullnheimer, R. F. Hartl và C. Strauss. Phiên bản cuối cùng của hệ thống này được công bố năm 1999 [6]. Vào năm 2001, C. Blum, A. Roli, và M. Dorigo đã cho công bố về hệ thống kiến mới là Hyper Cube – ACO. Phiên bản mở rộng tiếp đó đã được công bố vào năm 2004. [8] [12] Hầu hết các nghiên cứu gần đây về ACO tập trung vào việc phát triển các thuật toán biến thể để làm tăng hiệu năng tính toán của thuật toán Ant System ban đầu. - ACO algorithms [6][7]. - Ant System [6] - Elitist AS [7] - Ant-Q [6] - Ant Colony System [7] - Max-Min AS [7] - Rank-based AS [6] 11 - ANTS [6] - Hyper-cube AS [6] 2.2. CÁC NGUYÊN TẮC KHI ÁP DỤNG TỐI ƯU ĐÀN KIẾN 2.2.1 Số lượng kiến 2.2.2 Khám phá hành vi của đàn kiến và sự tối ưu hóa Hành vi đàn kiến Kiến như một cá thể riêng rẽ có các hiệu quả rất hạn chế.Tuy nhiên, mỗi con kiến như là một phần của một đàn có tổ chức tốt, nó trở thành một tác nhân mạnh mẽ, làm việc cho sự phát triển của đàn.Kiến sống cho đàn và tồn tại chỉ như một phần trong đó.Đàn kiến đôi khi được miêu tả như là một siêu tổ chức (superorganism) bởi vì nó dường như hoạt động như một thực thể thống nhất [12]. Mỗi con kiến có khả năng giao tiếp, học tập, hợp tác, và tất cả chúng cùng với nhau có khả năng tự phát triển và xâm chiếm hay định cư một vùng rộng lớn. Chúng quản lý thành công tuyệt vời như vậy bởi tăng số lượng các cá thể và đặc biệt được tổ chức rất tốt. Các nguyên tắc tự tổ chức mà chúng đang sử dụng cho thấy một hành vi phối hợp rất cao của đàn, hơn nữa còn đưa chúng đến thực hiện các nhiệm vụ phức tạp, khó khăn mà vượt xa khả năng cá nhân của một con kiến duy nhất. Pierre Paul Grassé, một nhà côn trùng học người Pháp, là một trong những nhà nghiên cứu đầu tiên nghiên cứu tỉ mỉ về hành vi xã hội của những côn trùng. Ông đã khám phá ra rằng những côn trùng này có khả năng phản ứng lại với những gì mà ông gọi là “tác nhân kích thích đáng kể” (significant stimuli).Những tác nhân kích thích đó làm khởi động một phản ứng đã được mã hóa về mặt di truyền học. Ông quan sát và nhận thấy rằng kết quả của các phản ứng này có thể sinh ra một tác nhân kích thích mới (new significant stimuli) 12 cho chính côn trùng đã sinh ra tác nhân này và những côn trùng khác trong đàn. Grassé đã sử dụng thuật ngữ “stigmergy” để miêu tả cho kiểu thông báo gián tiếp đặc biệt này. Stigmergy được định nghĩa như là một phương pháp thông báo gián tiếp bên trong một hệ thống độc lập tự tổ chức ở đó mỗi cá thể giao tiếp với mỗi cá thể khác bằng cách điều chỉnh môi trường cục bộ xung quanh chúng. Các con kiến thông báo cho các con kiến khác bằng cách để lại các vết mùi hóa chất dọc theo đường đi của nó, như vậy nơi mà các con kiến đi bên trong và xung quanh đàn được gọi là hệ thống stigmergic. Những hiện tượng tương tự đã được tiến hành quan sát cho một vài động vật, chẳng hạn như các con mối, đã sử dụng các vệt hóa chất tiết ra để xây dựng các tổ của chúng rất phức tạp bởi một tập các quy tắc phân quyền đơn giản [2]. Trong nhiều loài kiến, những con kiến trong khi đi tìm thức ăn, nó đặt xuống đất một vết hóa chất gọi là “pheromone”. Những con kiến khác có khả năng ngửi thấy vết hóa chất pheromone này, và nó nhanh chóng bị chi phối đến lựa chọn đường đi cho nó, đó là nó hướng tới đi theo con đường nào mà lượng mùi pheromone tập trung đậm đặc hơn (chứa nhiều pheromone). Hóa chất pheromone được đặt xuống đất tạo thành một vệt pheromone, cho phép các con kiến có thể tìm thấy nhanh nguồn thức ăn đã được nhận biết bởi những con kiến khác. Bằng cách sử dụng các hướng đi ngẫu nhiên và các pheromone trên vùng đất ở đó có chứa một tổ kiến và một nguồn thức ăn, những con kiến sẽ rời tổ, đi tìm kiếm thức ăn và mang trở về tổ. Sau một thời gian, con đường mà được sử dụng bởi những con kiến sẽ hội tụ về đường đi ngắn nhất. 13 a. Thí nghiệm cầu đôi Hình 2.3. Chiếc cầu đôi Hình 2.4. Những con kiến đang khám phá chiếc cầu đôi Hình 2.5. Kiến trở về tổ 2.2.3 Xác định các vệt mùi 2.2.4 Các thông tin heuristic 2.2.5 Điều chỉnh sự học tăng cường và sự khám phá 2.2.6 Sử dụng giới hạn danh sách láng giềng 14 2.2.7 Sơ đồ tổng quát của thuật toán đàn kiến Hình 2.6.Sơ đồ tổng quát của thuật toán đàn kiến 2.3. CÁC ỨNG DỤNG CỦA THUẬT TOÁN ACO Một số bài toán tối ưu NP-khó như: - Các bài toán lập lịch (job shop, flow shop, project scheduling) [6] - Bài toán phân chia sản phẩm (The generalized Assignment Problem GAP) [7] - Bài toán phủ tập hợp (The set covering problem – SCP) [6] - Các bài toán trong học máy: bài toán phân lớp, mạng Bayes [7] 2.4. KẾT LUẬN CHƯƠNG 2 Chương này giới thiệu tổng quan về thuật toán đàn kiến ACO, và một số nguyên tắc khi áp dụng thuật toán vào bài toán. Trong chương tiếp theo ta sẽ đi vào nghiên cứu phân tích, thiết kế xây dựng và triển khai hệ thống. 15 CHƯƠNG 3 ỨNG DỤNG THUẬT TOÁN ĐÀN KIẾN VÀO ĐỊNH TUYẾN MẠNG IP 3.1. MÔ TẢ BÀI TOÁN 3.1.1. Sơ đồ quá trình xử lý tại một nút giả lập Hình 3.1.Sơ đồ hoạt động của một nút giả lập Hoàn thành cập nhật bảng định tuyến 16 Hình 3.2.Sơ đồ sử lý kiến và cập nhật bảng định tuyến 17 3.1.2. Danh sách các đối tượng thiết kế trong hệ thống a. Mối quan hệ giữa các đối tượng b. Thiết kế các lớp chính 18 3.2. KẾT QUẢ TRIỂN KHAI 3.2.1. Giao diện và chức năng ứng dụng Hình 3.4. Giao diện chính của chương trình 3.2.2. Các chức năng Chức năng 1: Nhập xuất dữ liệu - Mở tập tin sơ đồ mạng: chức năng dùng để mở tập tin dữ liệu sơ đồ mạng đã xây dựng trước đó. - Lưu sơ đồ mạng: chức năng dùng để lưu dữ liệu sơ đồ mạng đang biên tập trên giao diện chương trình xuống tập tin. Chức năng 2: Mô hình hóa hệ thống mạng Vùng bên trái của phần mô phỏng mạng chứa các chức năng biên tập đồ thị mạng. 19 Vùng này gồm có các chức năng cơ bản sau: - Biên tập nút: nếu chức năng này được bật thì có thể thêm hoặc xóa nút, hoặc di chuyển nút trong giao hiện đồ thị mạng. - Biên tập cạnh: nếu chức năng này được bật thì có thể tạo các cạnh liên kết giữa các nút, có thể đặt trọng số cho các cạnh, hoặc xóa cạnh. - Xem bảng định tuyến: nếu lựa chọn chức năng này ta có thể xem bảng định tuyến của từng nút trong đồ thị. - Xóa sơ đồ mạng: chức năng này dùng để xóa toàn bộ sơ đồ mạng và các dữ liệu liên quan. Vùng bên phải của phần mô phỏng mạng chứa các chức năng cấu hình định tuyến. Vùng này bao gồm các chức năng cơ bản sau: - Kiểu định tuyến: là một comboBox dùng để lựa chọn một kiểu loại định tuyến. Có ba kiểu định tuyến chính đó là cập nhập nguồn (source update), không cập nhập nguồn (none source update) và định tuyến bằng thuật toán Dijkstra. - Hiển thị kiến: là một checkBox để xác định có hiển thị (đồ họa) kiến trong quá trình định tuyến hay không. - Số lượng kiến: số lượng kiến muốn sử dụng để thực hiện định tuyến trong mạng. - Hiển thị kiến của các nút: là một danh sách để lựa chọn các nút mà muốn những con kiến của nó hiển thị trên đồ thị khi thực hiện định tuyến. - Kết quả định tuyến của nút: là một comboBox để lựa chọn một nút muốn xem kết quả định tuyến của nó. - Tạo mới dữ liệu: chức năng này dùng để tạo dữ liệu từ đồ thị để thực hiện chạy chương trình định tuyến. 20 - Xóa bảng định tuyến: chức năng này dùng để xóa (reset) bảng định tuyến trên tất cả các nút trên mạng. - Bắt đầu/dừng: chức năng dùng để chạy dừng quá trình định tuyến Hình 3.5. Giao diện cấu hình định tuyến Chức năng 3: Hiển thị biểu đồ hệ thống Phần biểu đồ trình bày sự so sánh giữa các thời gian định tuyến khác nhau khi số lượng kiến thay đổi và biểu thị sự tăng tốc của thuật toán khi số lượng kiến thay đổi. Biểu đồ so sánh dưới đây Hình 3.6.của một mạng 30 nút cho ta thấy rằng, số lượng kiến càng lớn thì thời gian định tuyến càng nhỏ và độ tăng tốc của thuật toán càng lớn 21 Hình 3.6. So sánh thời gian thực thi với số lượng kiến mạng 30 nút 3.2.3. Kết quả thực hiện Kịch bản 1: Cho mạng đồi thị với 8 nút mạng và số lượng kiến cần cho định tuyến là 100 con kiến. Hình 3.7. Đồ thị với 8 nút mạng 22 Hình 3.8. Kết quả định tuyến nút N1, N2 đến các nút khác của mạng Kịch bản 2:Sơ đồ mạng gồm 30 nút, đây là một cấu trúc liênquan thực tế SDH của bộ truyền thông Anh Quốc. Hình 3.18.Sơ đồ mạng thực tế SDH của bộ truyền thông Anh Quốc Hình 3.19. Biểu đồ so sánh hiệu suất định tuyến trong đồ thị SDH 23 3.2.4. Nhận xét và đánh giá Qua quá trình tìm hiểu phương pháp mới cho việc giải các bài toán tối ưu tổ hợp, đó là thuật toán tối ưu hóa đàn kiến, và ứng dụng nó để giải các bài toán định tuyến mạng.Đã thực hiện xây dựng ứng dụng mô phỏng định tuyến mạng sử dụng thuật toán tối ưu hóa đàn kiến và đạt được nhiều kết quả khả quan.Ứng dụng thực hiện định tuyến cho tất cả các cặp nút và trình diễn quá trình định tuyến, quá trình di chuyển và tìm đường của những con kiến. 3.3. KẾT LUẬN CHƯƠNG 3 Chương này phân tích các chức năng của hệ thống, biểu đồ lớp và mối quan hệ giữa các đối tượng trong chương trình mô phỏng.Nêu ra sơ đồ hoạt động của một nút mạng giả lập, sơ đồ xử lý kiến và cập nhật bảng định tuyến.Bên cạnh đó còn đưa ra hận xét và đánh giá kết quả đạt được của thuật toán định tuyến mạng ACO. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. Kết luận Về lý thuyết - Tìm hiểu và nghiên cứu các cơ sở lý thuyết đồ thị, định tuyến mạng và các giao thức định tuyến. - Tìm hiểu và phân tích khả năng ứng dụng của thuật toán đàn kiến vào việc định tuyến mạng IP. - Đánh giá được hiện trạng của hệ thống mạng Internet hiện nay, qua đó phân tích được các ưu nhược điểm của việc định tuyến mạng hiện nay và có thể đề xuất giải pháp ứng dụng thuật toán đàn kiến vào việc định tuyến mạng. 24 - Nghiên cứu và ứng dụng các bài toán tối ưu hóa việc định tuyến mạng, qua đó còn đánh giá, so sánh giữa thuật toán đàn kiến với các thuật toán định tuyến truyền thống. Về thực nghiệm - Xây dựng ứng dụng mô phỏng định tuyến mạng sử dụng thuật toán tối ưu hóa đàn kiến và đạt được nhiều kết quả khả quan. - Ứng dụng thực hiện định tuyến cho tất cả các nút và trình diễn quá trình định tuyến, quá trình di chuyển và tìm đường của những con kiến. - Ứng dụng thực hiện định tuyến khá nhanh, có thể trình diễn đồ họa quá trình tìm đường của những con kiến. - Có thể biên tập đồ thị mạng bằng chuột và có thể lưu đồ thị mạng vào tập tin. - Ngoài ra, ứng dụng còn mô phỏng định tuyến bằng thuật toán Dijkstra. - Ứng dụng rất thực tế và có thể triển khai thành các giao thức định tuyến mạng. 2. Hướng phát triển - Xây dựng ứng dụng có thể thao tác với nhiều kiểu loại mạng khác nhau. Cải thiện hiệu suất trình diễn đồ họa với đồ thị mạng lớn và số lượng kiến lớn. - Triển khai ứng dụng có thể chạy trên môi trường Web - Triển khai thuật toán trên môi trường lập trình song song.