Thuật toán metaheuristic giải bài toán định tuyến tối ưu trong mạng máy tính.

- 10 BÀI TOÁN ĐỊNH TUYẾN TỐI ƯU TRONG MẠNG MÁY TÍNH.
- Các hàm mục tiêu cần tối ưu hóa.
- Đếm số bước nhảy (Hop.
- 32 1.2.7 Tận dụng tối đa liên kết.
- 34 1.2.8 Hàm số truyền tin đa đích khác.
- 39 1.3.1 Truyền tin đơn đích.
- 39 1.3.2 Truyền tin đa đích.
- 43 3 1.4.1 Truyền tin đơn đích.
- 43 1.4.2 Truyền tin đa đích.
- 47 BÀI TOÁN ĐỊNH TUYẾN TỐI ƯU ĐƠN ĐÍCH VÀ CÁC HƯỚNG TIẾP CẬN PHÁT TRIỂN THUẬT TOÁN GIẢI.
- Truyền tin đơn đích sử dụng hàm đếm bước nhảy và độ trễ.
- Truyền tin đơn đích sử dụng hàm đếm số bước nhảy, hàm trễ và hàm tiêu thụ băng thông.
- Truyền tin đơn đích sử dụng hàm đếm bước nhảy, hàm trễ, hàm tiêu thụ băng thông và hàm tận dụng tối đa liên kết.
- Bài toán định tuyến tối ưu hóa đa mục tiêu đơn đích.
- 81 GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN ĐỊNH TUYẾN ĐƠN ĐÍCH TỐI ƯU VỚI MỤC TIÊU GỘP.
- 106 5 DANH MỤC THUẬT NGỮTIẾNG ANH TT Tiếng Anh Tiếng Việt Trang 1 Unicast case Trường hợp đơn đích 3 2 Multicast case Trường hợp đa đích 4 3 Optimization Function Hàm tối ưu hóa 5 4 Unicast Transmission Truyền tin đơn đích 6 5 Distance Vector Multicast Routing Protocol Giao thức hướng lộ đa đích sử dụng Vec tơ khoảng cách 9 6 Weighted Sum Tổng có trọng số 38 DANH MỤC HÌNH ẢNH Hình 1.
- Tối ưu hóa mạng máy tính trong tuyền tin đơn đích.
- Hàm đếm bước nhảy trong truyền tin đơn đích.
- Hàm đếm bước nhảy trong truyền tin đa đích.
- Giải pháp đầu tiên.
- Giải pháp thứ hai.
- Hàm trễ trong truyền tin đa đích.
- Giải pháp thứ 2.
- Hàm tiêu thụ băng thông trong truyền tin đa đích.
- Hàm số tận dụng tối đa liên kết.
- Kênh truyền tin.
- Ràng buộc truyền tin đơn đích.
- Ràng buộc truyền tin đa đích.
- Giá trị tối ưu trong tối ưu hóa đa mục tiêu.
- 48 Hình 1.25 Ví dụ mạng máy tính.
- Tóm tắt các thông số được sử dụng cho các trường hợp truyền tin đơn đích.
- Tối ưu hóa mạng máy tính trong truyền tin đa đích.
- Các tham số được sử dụng cho trường hợp truyền tin đa đích.
- Giải pháp 1 ràng buộc - ε.
- Giải pháp Benso.
- Giải pháp cho ví dụ 1.
- Giải pháp cho ví dụ 2.
- Giải pháp cho ví dụ 3.
- Giải pháp cho ví dụ 4.
- Quá trình tối ưu cần đưa ra một giải pháp nhằm đáp ứng tốt nhất nhu cầu truyền thông là quá trình chọn lọc các tuyến đường nhằm tìm ra một tuyến đường tối ưu nhất.
- Đối với những mạng lớn thì thuật toán định tuyến tối ưu là một bài toán khó.
- Bài toán định tuyến tối ưu trong mạng máy tính yêu cầu tìm ra một tuyến đường tối ưu nhất từ nút nguồn đến nút đích thỏa mãn một số ràng buộc đưa ra.
- Bài toán định tuyến tối ưu trong mạng máy tínhlà một bài toán con thuộc lớp bài toán NP – khó không thể tìm ra lời giải tối ưu vì vậy thuật toán metaheuristic là một trong các cách tiếp cận để giải quyết vấn đề đặt ra.
- Phương pháp này có nhiều đặc điểm nổi trội như không đòi hỏi tri thức, tránh tối ưu cục bộ, thực hiện tốt với các bài toán có không gian lời giải lớn và có thể áp dụng cho nhiều loại bài toán tối ưu khác nhau.
- Trên thế giới hiện nay, giải thuật di truyền kết hợp với tin học được ứng dụng để giải quyết những bài toán tối ưu một cách rất hiệu quả.
- Mục tiêu của luận văn là trên cơ sở tìm hiểu kiến thức tổng quan thuật toán metaheuristic cũng như giải thuật cơ bản của giải thuật di truyền, tập trung xây dựng giải thuật di truyền để giải bài toán định tuyến tối ưu trong mạng máy tính.
- Chương 1 trình bày một số kiến thức cơ sở liên quan đến các bài toán định tuyến tối ưu trong mạng máy tính.
- Chương 2 giới thiệu các bài toán tối ưu hóa trong việc định tuyến đơn đích và tổng quan về giải thuật di truyền: lịch sử ra đời, các bước của giải thuật và một số chiến lược thực hiện.
- Chương 3 trình bày bài toánđịnh tuyến đơn đích tối ưu với hàm mục tiêugộp và đề 9 xuất, phân tích một số chiến lược thực hiện các phép toán sinh quần thể, lai ghép, đột biến… áp dụng trong giải thuật di truyền giải bài toán đặt ra.Chương 4 mô tả cài đặt và thực nghiệm theo thuật toán đề xuất.
- 10 CHƯƠNG 1 BÀI TOÁN ĐỊNH TUYẾN TỐI ƯU TRONG MẠNG MÁY TÍNH Chương này trình bày về khái niệm mạng truyền tin đơn đích và mạng truyền tin đa đích.
- một sốhàm để tối ưu hóa trong mạng truyền tin: đếm số bước nhảy, độ trễ, chi phí, tiêu thụ băng thông, tỷ lệ mất luồng tin, xác suất chặn, tận dụng tối đa liên kết, một số chức năng truyền tin khác.
- Để các giải pháp tối ưu hóa mạng máy tính có tính khả thi phải có một số ràng buộc và nêu một số ràng buộc của các hàm tối ưu hóa .
- Khái niệm 1.1.1 Trường hợpđơn đích Để giải quyết một vấn đề tối ưu hóa trong các mạng máy tính, cần định nghĩa một biến xác định đường đi mà theo đó thông tin sẽ được truyền tải.
- Định nghĩa biến vec tơ sau: {=tfijX Điều này có nghĩa rằng biến Xijnhận giá trị là 1 nếu liên kết (i, j) được dùng để truyền tảiluồng tin, ngược lại giá trị củaXij là 0.
- Trong hình 4.1 có hai đường đi có thể đi từ nút nguồn 1 đến nút đích 5.
- Đường đi đầu tiên thông qua các liên kết (1,2) và (2,5).
- Đường đi thứ hai là thông qua các liên kết và (4,5).
- Giả sử đường đi đầu tiên đã được chọn là đường đi để truyền tảiluồng tinf1, 112X=1 và 125X=1.
- Do các liên kết và (4,5) không được sử dụng, các giá trị của các biến liên quan đếnnhững liên kết này là bằng 0.
- Tối ưu hóa mạng máy tính trong tuyền tin đơn đích Bảng 1.
- Ký hiệu Định nghĩa G (N, E) Biểu đồ cấu trúc N Tập các nút E Tập các liên kết s Các nút đi vào t Các nút đi ra (i,j) Liên kết từ núti đến nút j F Tập các luồng tin f Luồng tintruyền tinđơn đích bất kỳ.
- Liên kết (i,j) được dùng truyền tảiluồng tinf với đích đến là nút ra t cij Trạng thái của liên kết (i,j) bwf Yêu cầu lưu lượng luồng tinf 1 5 2 3 4 FTP f 1 1 1 12 X 0 1 13 X 0 1 34 X 0 1 45 X 1 1 25 X 12 1.1.2.
- Trường hợp đa đích Đối với trường hợp truyền tinđa đích, phải định nghĩa một biến mà có thể biểu diễn liên kết được sử dụng để truyền tải một luồng tin cụ thể.
- Nếu liên kết không được dùng thì biến tương ứng có giá trị bằng 0.
- Theo hình vẽ 1.2 có 4 đường đi có thể đi từ nút nguồn 1 đến các nút đích 5 và 6.
- Đường đi đầu tiên bao gồm các liên kết và .
- Đường đi thứ hai bao gồm và .
- Đường đi thứ ba bao gồm các liên kết và .
- Cuối cùng, đường đithứ tư gồm các liên kết và Giả sử rằng đường đi thứ hai đã được lựa chọn và .
- là đường truyền tinđa đích của luồng tinf1, thì giá trị của các biến5114X = 1, 6114X = 1, bởi vì cả hai liên kết được sử dụng để truyền tải luồng tinf1 có đích đến là nút 5 và 6.
- Bởi vì các liên kết và (3, 6) không được sử dụng, các giá trị của các liên kết có đích đến là nút 5 và 6 (Hình 1.2) là 0.
- Giá trị của các biến mà từ các liên kết không thể đến được đích sẽ không được hiển thị trong hình 1.2.
- Ví dụ như, giá trị của biến6145X=0 , bởi vì không thể đến 6 nút thông qua liên kết (4, 5).
- Tối ưu hóa mạng máy tính trong truyền tin đa đích Video f 1 0 51 12 X 0 51 25 X 0 61 13 X 0 61 36 X 1 51 14 X 1 61 14 X 1 51 45 X 1 61 46 X 1 nếu dòng tin f đi qua (i,j) 0 nếu dòng tin f không đi qua (i,j) 13 Bảng 2.
- Các tham số được sử dụng cho trường hợp truyền tinđa đích Ký hiệu Định nghĩa G (N, E) Biểu đồ cấu trúc N Tập các nút E Tập các liên kết S Các nút đi vào T Tập các nút đi ra (i,j) Liên kết từ núti đến nútj F Tập các luồng tin f Luồng tintruyền tinđa đích bất kỳ Tf Tập các nút ra của luồng tintruyền tinđa đíchf.
- Liên kết (i,j) được dùng truyền tảiluồng tinf với đích đến là nút ra t cij Trạng thái của liên kết (i,j) Bwf Yêu cầu lưu lượng của luồng tin 1.2.
- Các hàm mục tiêu cần tối ưu hóa Trong phần này, định nghĩa một số hàm thường được sử dụng đểtối ưu hóa.
- Hàm nàyđếm số lượng liên kết mà các luồng tin phải đi qua, bắt đầu từnút nguồnđến nút đích.
- Hình 1.3 có hai đường đi có thể truyền tảiluồngf1 giữa nguồn nút nguồn 1 đến nút đích 5: đường đi đầu tiên được hình thành bởi các liên kết (1, 2) và (2,5)do 14 đó, số lượng các bước nhảy truyền tải gói dữ liệu là 2.
- Đường đi thứ hai được hình thành bởi các liên kết và (4, 5)số bước nhảy là 3.
- Nếu sử dụng hàm đếm bước nhảy như là một hàm tối ưu hóa , đường đi để truyền tải các gói dữ liệu từ nút nguồn 1 đến nút đích 5 sẽ là đường đi đầu tiên.
- Các giao thức định tuyến hoạt động với hàmđếm số bước nhảy để tính toán đường đi ngắn nhất được gọi là Routing Internet Protocol (RIP).
- Ví dụ trong hình 1.3, sửdụng biếnfijXđể biểu diễn các đường đi.
- Nếu muốn biểu diễn các đường đi đã đề cập ở trên theo biến này, số lượng bước nhảy của đường đi đầu tiên sẽ là 112X + 125X.
- Nếu đây là đường đi được sử dụng, giá trị của các biến này sẽ bằng 1 và tổng lại sẽ bằng 2.
- Tương tự như vậy, đối với đường đi thứ hai và đường đi được sử dụng, giá trị của mỗi của các này sẽ là 1, và tổng sẽ bằng 3.
- Khi muốn tìm đường đi ngắn nhất dựa vào hàm đếm bước nhảy thì chỉ có một đường đi được chọn.
- Trong ví dụ ở hình, đường đi ngắn nhất là các liên kết (1, 2) và (2, 5).
- Hình 3.Hàm đếm bước nhảy trong truyền tin đơn đích f FTP 1 1 12 X 0 1 13 X 0 1 34 X 0 1 45 X 1 1 25 X Destination: t = 5 Source: s = 1 15 Hàm tối ưu hóa sẽ giảm tổngđộ dài đường đi, chỉ có các biến thuộcđường điđược sử dụng có giá trị 1.
- Trong các giải pháp truyền tảiluồng tinf, sẽ có một đường đi với số lượng bước nhảy tối thiểu nhất đi từ nút nguồns tới nút đích t.
- Hình 1.4 có bốn đường đi có thểtruyền tải luồng tinf1 giữa nút nguồn 1 và nút đích 5, 6:đường đi đầu tiên (hình 1.5) được hình thành bởi các liên kết và .
- và do đó, tổng số bước nhảy đường đi này sẽ là tổng của số lượng bước nhảy trong mỗi đường đi.
- Bởi vì có 2 bước nhảy trong đường đi đầu tiên và cũng có 2 bước nhảy trong đường đi thứ hai, tổng số bước nhảy trong đường đi này là 4.
- Đường đi thứ hai (Hình 1.6) được hình thành bởi các liên kết và .
- và do đó, tổng số bước nhảy trong đường đi này là 4.
- Đường đi thứ ba (Hình 1.7) được hình thành bởi các liên kết và .
- và do đó, tổng số bước nhảy là 4.
- Đường đi thứ tư (hình 1.8) được hình thành bởi các liên kết và .
- tổng số bước nhảy là 4.
- 16 Nguồn: s = 1 Đích: t1 = 5 và t2 = 6 Hình 4.Hàm đếm bước nhảy trong truyền tin đa đích Hình 5

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt