Tóm tắt luận văn Thạc sĩ Kỹ thuật: 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<br /> ĐẠI HỌC ĐÀ NẴNG<br /> <br /> NGUYỄN THỊ MAI PHƯƠNG<br /> <br /> NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN ACO<br /> CHO VIỆC ĐỊNH TUYẾN MẠNG IP<br /> <br /> Chuyên ngành: Khoa học máy tính<br /> Mã số: 60.48.01<br /> <br /> TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT<br /> <br /> Đà Nẵng – Năm 2013<br /> <br /> Công trình được hoàn thành tại<br /> ĐẠI HỌC ĐÀ NẴNG<br /> <br /> Người hướng dẫn khoa học: TS. Nguyễn Tấn Khôi<br /> <br /> Phản biện 1: TS. Nguyễn Văn Hiệu<br /> Phản biện 2: GS. TS. Nguyễn Thanh Thủy<br /> <br /> Luận văn đã được bảo vệ trước Hội đồng chấm Luận<br /> văn tốt nghiệp thạc sĩ Kỹ thuật họp tại Đại học Đà Nẵng vào<br /> ngày 16 tháng 11 năm 2013.<br /> <br /> Có thể tìm hiểu luận văn tại:<br /> - Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng<br /> - Trung tâm Học liệu, Đại học Đà Nẵng<br /> <br /> 1<br /> <br /> MỞ ĐẦU<br /> 1. Lí do chọn đề tài<br /> Chỉ trong vòng hơn một thập niên qua, Internet đã phát triển<br /> rất nhanh chóng với nhiều mục đích sử dụng khác nhau: từ khoa học<br /> kỹ thuật, kinh tế, giáo dục… cho đến những hoạt động xã hội. Để<br /> đáp ứng nhu cầu hết sức phong phú và đa dạng của những người sử<br /> dụng đầu cuối, các nhà cung cấp dịch vụ truyền thông qua Internet<br /> đứng trước những thách thức không chỉ đòi hỏi phải nâng cấp thêm<br /> 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ở<br /> hạ tầng mạng hiện có để có thể cung cấp các dịch vụ với chất lượng<br /> cao và chi phí hợp lý.Bài toán định tuyến cần được quan tâm nghiên<br /> 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ế<br /> giới đã có nhiều nghiên cứu về các phương pháp định tuyến, với mục<br /> đích chủ yếu là tìm ra những phương pháp định tuyến thích hợp để<br /> áp dụng vào thực tế mạng lưới [9].<br /> Bài toán tìm kiếm luôn được nhiều người quan tâm, đặc biệt là<br /> 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<br /> 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<br /> ứng dụng thực tế như: tìm kiếm các trang web cần tìm trên mạng, kế<br /> 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<br /> đường đi tối ưu cho những người lái xe hơi, định hướng trong mạng<br /> truyền thông… đấy là thuật toán kiến (ACS – Ant Colony Search<br /> hoặc ACO - Ant Colony Optimization).<br /> 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<br /> chọn đề tài luận văn cao học: Nghiên cứu ứng dụng thuật toán ACO<br /> cho việc tối ưu hóa quá trình định tuyến trên mạng IP.Nhằm nghiên<br /> cứu giải quyết các vấn đề đặt ra.<br /> <br /> 2<br /> <br /> 2. Mục đích nghiên cứu<br /> - Tìm hiểu và so sánh phương pháp tối ưu hóa<br /> - Triển khai thuật toán định tuyến cho định tuyến mạng sử<br /> dụng kỹ thuật cập nhật nguồn.<br /> - Xây dựng ứng dụng mô phỏng quá trình định tuyến trên<br /> mạng sử dụng thuật toán đàn kiến đã triển khai<br /> 3. Đối tượng và phạm vi nghiên cứu<br /> Đối tượng nghiên cứu<br /> - Các giao thức cơ sở của mạng máy tính<br /> - Giải thuật định tuyến trên mạng IP<br /> - Giải thuật tối ưu hóa đàn kiến ACO<br /> Phạm vi nghiên cứu<br /> - Tìm hiểu lý thuyết và xây dựng mô hình mô phỏng<br /> 4. Phương pháp nghiên cứu<br /> Nghiên cứu lý thuyết<br /> - Tìm hiểu các phương pháp định tuyến hiện nay<br /> - Tìm hiểu cơ sở lý thuyết về thuật toán tối ưu hóa đàn kiến<br /> - Tìm hiểu khả năng thích nghi của thuật toán tối ưu hóa đàn<br /> kiến với các giao thức định tuyến<br /> Nghiên cứu thực nghiệm<br /> - Xây dựng ứng dụng mô phỏng sự hoạt động của thuật toán<br /> tối ưu hóa đàn kiến trong định tuyến mạng<br /> 5. Ý nghĩa khoa học và thực tiễn của đề tài<br /> Ý nghĩa khoa học<br /> - Ứng dụng thuật toán đàn kiến để giải các bài toán tối ưu tổ<br /> 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<br /> toán lập lịch, bài toán tìm đường đi ngắn nhất<br /> <br /> 3<br /> <br /> - Ứng dụng thuật toán đàn kiến để giải các bài toán định tuyến<br /> cho các mạng IP<br /> Ý nghĩa thực tiễn<br /> - Ứng dụng thuật toán đàn kiến trong tối ưu định tuyến mạng<br /> tìm đường đi tối ưu cho các gói tin trên mạng<br /> - Giảm thiểu chi phí định tuyến bằng cách truyền đi những<br /> con kiến với kích thước nhỏ thay vì phải truyền đi bảng định tuyến<br /> - Những con kiến khi định tuyến thực hiện cập nhật thông tin<br /> định tuyến chỉ cần cập nhật một mục trong bảng pheromone độc lập<br /> thay vì phải cập nhật toàn bộ bảng định tuyến<br /> - Những con kiến có thể gắn vào các gói dữ liệu để truyền đi<br /> trên mạng<br /> - Thuật toán đàn kiến rất phù hợp cho các mạng năng động<br /> 6. Cấu trúc luận văn<br /> Nội dung chính của luận văn này được chia thành ba chương<br /> với nội dung như sau:<br /> Chương 1 - Tổng quan định tuyến mạng: chương này trình<br /> bày lý thuyết đồ thị, định tuyến mạng và các giao thức định tuyến<br /> Chương 2 - Thuật toán tối ưu đàn kiến ACO: chương này nói<br /> 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<br /> hóa đàn kiến (ACO), nêu ra thuật toán đàn kiến (ACO)<br /> Chương 3 - Ứng dụng thuật toán đàn kiến ACO vào định<br /> tuyến mạng IP: chương này trình bày kết quả thử nghiệm về việc<br /> định tuyến mạng IP bằng thuật toán ACO<br /> <br />