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

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

đị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ó


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
*

Í

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
ij
và 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

k
i
k
ilil
lN
p
ab
ab
th
th
Î
=
å
j
Î
k
i
N
(2.2)
Trong đó:
ij
k
p
: 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

ij

1 và một số 0
n
q
n
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:
=
!
"#$%&'
()*
+
,
-
.
/0
[
1
23
]
4
5
, 6789 :;
<
=, >7?@AưBCDEF
(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


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]

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

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

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

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.