1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG TIÊU VĂN GIANG

NGHIÊN CỨU ĐỊNH TUYẾN VÀ GÁN BƯỚC SÓNG
TRONG MẠNG WDM SỬ DỤNG PHƯƠNG PHÁP
TÍNH TOÁN TIẾN HÓA LAI 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Ĩ
HÀ NỘI - 2012LỜI NÓI ĐẦU
Sự bùng nổ của mạng Internet, sự phát triển số lượng người
sử dùng, sự phát triển của các ứng dụng và dịch vụ mới trên nền IP,
đó là những gì mà chúng ta đã chứng kiến trong vòng gần một thập
kỉ qua [7]. Mạng truyền dẫn quang đã đáp ứng được rất nhiều yêu
cầu về dung lượng, chi phí xây dựng và tính bảo mật thông tin. Hai

sau đại học đã giúp đỡ rất nhiều cho tôi để hoàn thiện luận văn này.
Tuy nhiên, do thời gian và trình độ còn giới hạn, tôi kính mong
được các thầy cô tiếp tục đóng góp, giúp đỡ để luận văn được hoàn
thiện tốt hơn và được ứng dụng vào thực tế.
Tôi xin trân trọng cảm ơn!

TÁC GIẢ
TIÊU VĂN GIANG
CHƯƠNG 1: TỔNG QUAN
Hệ thống thông tin của con người có lịch sử phát triển từ rất
lâu. Cho tới nay, đã có rất nhiều các hệ thống thông tin dưới các
hình thức đa dạng. Các hệt hống thông tin này được gán cho các
tên gọi nhất định theo môi trường truyền dẫn và đôi khi theo cả tính
chất dịch vụ của hệ thống. So với hệ thống thông tin hiện đại đầu
tiên là thông tin điện báo (đưa vào khai thác năm 1844) thì hệ
thống thông tin quang (mới được khai thác từ những năm 1980) là
hệ thống có tuổi đời còn khá trẻ. Tuy vậy cùng với sự phát triển của
các dịch vụ mạng và đòi hỏi ngày càng cao về dung lượng và băng
thông, hệ thống thông tin quang cũng đã phát triển rất mạnh mẽ về
công nghệ trong gần 3 thập niên qua. Do có ưu điểm như vậy nên
các hệ thống thông tin quang nhanh chóng được áp dụng rộng rãi
trên mạng lưới. Chúng còn tiềm tàng những khả năng rất lớn trong
việc hiện đại hoá các mạng lưới viễn thông trên thế giới.
1.1. Mạng WDM.
1.1.1. Định nghĩa:
WDM (Wavelength Division Multiplexing – Ghép kênh theo
bước sóng) là công nghệ “trong một sợi quang truyền dẫn đồng

2,5 Gbps = 10 Gbps.
Nguyên tắc này được minh họa trong hình 1.2. Hình 1.2 : Nguyên tắc ghép kênh trong mạng SONET

SONET cung cấp các chuẩn cho một số lượng lớn các tốc độ
truyền (tốc độ truyền thực tế vào khoảng 20 Gbps).
1.1.2.3. Gigabit Ethernet:
Công nghệ Ethernet 10 Gigabit được xây dựng trên nghi thức
Ethernet, nhưng có tốc độ nhanh gấp 10 lần Ethernet (1000 Mbps).
Ethernet Gigabit được triển khai như một công nghệ xương sống
cho các mạng đô thị. Đối với mạng diện rộng WAN, Ethernet 10
Gigabit cho phép các ISP (Internet Service Provider) và NSP
(Network Service Provider) tạo ra các liên kết tốc độ rất cao với giá
thành thấp từ các bộ chuyển mạch và các bộ định tuyến trong phạm
vi công ty cho đến thiết bị quang gán trực tiếp vào SONET/SDH.
Công nghệ Ethernet Gigabit hỗ trợ cả cáp sợi quang đơn mode và
đa mode. Tuy vậy, các khoảng cách được hỗ trợ tùy vào các kiểu
cáp sợi quang và bước sóng được thực thi trong ứng dụng.
1.1.3. Hệ thống thông tin quang nhiều kênh
Trên thực tế, sự ra đời của các hệ thống quang đa kênh đã giải
quyết được những hạn chế của hệ thống đơn kênh, đồng thời cũng
tận dụng được những công nghệ hiện có để phát triển mạnh mẽ. Cụ
thể là :
Thứ nhất, đối với hệ thống đơn kênh, khi tốc độ đạt tới mức
khoảng vài chục Gbit/s thì khoảng cách tuyến truyền dẫn sẽ bị rút
ngắn lại, các thiết bị điện tử sẽ đạt đến giới hạn của nó và không
đáp ứng được các xung tín hiệu cực kì hẹp; thêm vào đó chi phí
dành cho các giải pháp trên tuyến truyền dẫn trở nên tốn kém vì


Hình 1.5: Hệ thống WDM song hướng
1.2. Định tuyến và gán bước sóng trong mạng WDM.
1.2.1. Định tuyến (Routing)
1.2.1.1. Giới thiệu
Định tuyến được coi là thành phần cốt yếu của kiến trúc
mạng, thiết kế mạng và điều hành mạng của mọi mạng thông tin, là
thành phần không thể thiếu trong mạng viễn thông.
1.2.1.2. Phân loại định tuyến
Có nhiều cách phân loại định tuyến, có thể đưa ra một số
loại định tuyến như sau:
 Dựa vào chức năng thích nghi với trạng thái hiện thời của
mạng để phân loại thành: định tuyến tĩnh và định tuyến động
+ Định tuyến tĩnh: với định tuyến tĩnh, đường dẫn được
chọn trước cho mỗi cặp nguồn – đích của các node trong mạng.
+ Định tuyến động: định tuyến động lựa chọn tuyến dựa trên
thông tin trạng thái hiện thời của mạng.
 Dựa vào phạm vi định tuyến, ta phân loại thành: định tuyến
trong và định tuyến ngoài.
Định tuyến trong: định tuyến xảy ra bên trong một hệ thống
độc lập (AS – Autonomous System), các giao thức thường dùng là
RIP (Router Information Protocol), IGRP (Interior Gateway
Routing Protocol), OSPF (Open Shortest Path First), EIGRP
(Enhanced IGRP),…
Định tuyến ngoài: định tuyến xảy ra giữa các hệ thống độc
lập (AS), liên quan tới dịch vụ của nhà cung cấp mạng sử dụng
giao thức định tuyến ngoài rộng và phức tạp. Giao thức thường
dùng là BGP (Border Gateway Protocol).
5



và tổng trọng số. Tuy nhiên các gần đúng đơn mục tiêu
có một nhược điểm là rất khó tìm được các nghiệm tối ưu. Do vậy
mà các thuật toán tiến hóa đa mục tiêu được áp dụng để giải các bài
toán thiết kế đa mục tiêu này.
1.3.2. Mục tiêu nghiên cứu

Nghiên cứu giải quyết bài toán định tuyến và gán bước sóng
đa mục tiêu trong mạng WDM bao gồm:
+ Xây dựng bài toán RWA như là một bài toán tối ưu đa
mục tiêu.
6

+ Giải bài toán RWA được xây dựng ở trên bằng thuật toán
di truyền để tối ưu hóa các tham số mạng khác nhau.
1.4. Nội dung và đóng góp của luận văn.
1.4.1. Nội dung của luận văn
Nội dung của luận văn dự kiến sẽ được chia thành 4 chương
với những nội dung cụ thể như sau:
Chương 1: Trình bày tổng quan về mạng WDM, các vấn đề
cơ bản về định tuyến và gán bước sóng trong mạng WDM, nhiệm
vụ, hướng nghiên cứu và những đóng góp của luận văn.
Chương 2: Giới thiệu bài toán RWA, các mục tiêu thiết kế,
các phương pháp tiếp cận bài toán RWA: heuristic và meta-
heuristic.
Chương 3: Trình bày bài toán tối ưu hóa đa mục tiêu, các
giải thuật tiến hóa trong tối ưu hóa đa mục tiêu, các giải thuật di
truyền trong RWA đa mục tiêu.
Chương 4: Trình bày mô hình mô phỏng RWA đa mục tiêu,
cách thức giải bài toán RWA đa mục tiêu bằng phương pháp tính

cùng bước sóng trên tất cả các sợi liên kết mà qua đó nó đi qua.
(ii) Ràng buộc bước sóng riêng biệt: Hai lightpaths phải
không được chỉ định cùng một bước sóng trên một liên kết nào.
7

2.2. Cách tiếp cận heuristic đối với bài toán RWA.
Chlamtac[8] đề xuất khái niệm về Lightnet kiến trúc để đối
phó với các vấn đề không phù hợp giữa tốc độ xử lý điện tử và
truyền dẫn quang băng thông trong WDM dựa trên các mạng diện
rộng.
Zhang và Acampora[26] đã đề xuất một thuật toán hiệu quả
để gán một số giới hạn các bước sóng giữa các trạm truy cập của
mạng trong đó các phương tiện vật lý bao gồm các phân đoạn sợi
quang được kết nối qua các thiết bị chuyển mạch bước sóng quang
chọn lọc.
Banerjee [4] đã xem xét các vấn đề thiết kế một cấu trúc liên
kết mạng quang học hợp lý cho một mô hình vật lý và một ma trận
nhu cầu giao thông giữa những người sử dụng cuối cùng.
Banerjee và Mukherjee[2] đã trình bày một công thức lập
trình tuyến tính số nguyên để đưa ra một giải pháp tối thiểu khoảng
cách bước nhảy đến các vấn đề thiết kế cấu trúc liên kết ảo trong
một mạng bước sóng định tuyến quang học, trong trường hợp
không có ràng buộc bước sóng liên tục.
2.3. Cách tiếp cận meta-heuristic đối với bài toán RWA.
Các giải pháp meta Heuristic thiết kế các cấu trúc liên kết
trong khu vực mạng mesh diện rộng để giảm thiểu chi phí mạng.
Các thuật toán di truyền đã được sử dụng để giải quyết bài toán
RWA theo giả định khác nhau. Các tác giả đã xây dựng các vấn đề
RWA tĩnh trong các mạng quang học là một vấn đề tối ưu hóa mục
tiêu duy nhất và giải quyết nó bằng cách sử dụng một thuật toán


8

3.1. Xây dựng bài toán đa mục tiêu.
Bài toán RWA là một bài toán tối ưu hóa tổ hợp và một loạt
các phương pháp tối ưu đã được sử dụng để giải quyết bài toán này.
Các bài toán RWA có thể được mô hình hóa như một bài toán lập
trình số nguyên tuyến tính (ILP) và giải quyết ILP được đảm bảo
để cung cấp cho các tối ưu toàn phần
3.1.1.
ký hiệu sử dụng.
Ký hiệu được sử dụng trong việc xây dựng ILP được quy
định như sau:
+ V = Thiết lập các nút trong mạng.
+ E = Thiết lập các liên kết sợi hai chiều trong mạng.
+ W = Thiết lập các kênh bước sóng không nhiễu hỗ trợ bởi
tất cả các liên kết sợi trong mạng.
+ (i,j) Là cặp nút nguồn-đich; {i,j}  V.
+ D = Ma trận nhu cầu của các yêu cầu kết nối, nơi D
ij
dùng
để chỉ một giá trị đầy đủ ghi rõ nhu cầu tối đa giữa các cặp nút (i, j)
và D
ij
= D
ji
.
+ 
-
(v) = Thiết lập các liên kết sợi được sử dụng bởi


 

Vi Vj
ij
D
K

jiij
DDijKjiK  ),(),(
3.1
Các hàm mục tiêu mà chúng ta muốn tối ưu hóa được quy định như
sau:
+ Giảm thiểu ách tắc của nhiều nhất liên kết tắc nghẽn trong
mạng:




  

0:),( ),(
,
),(max
ij
DVVji jiKk Ww
ew
k
Ee
jibMinimize

+ Giảm thiểu sự khác biệt giữa tắc nghẽn nhiều nhất và tắc
nghẽn ít nhất liên kết trong mạng:







    




0:),( ),( 0:),( ),(
,,
}),(min),(max{
ij ij
DVVji jiKk DVVji jiKk Ww
ew
k
Ee
Ww
ew
k
Ee
jibjibMin
(3.5)
+ Giảm thiểu sự khác biệt giữa các liên kết tắc nghẽn nhiều
nhất và ùn tắc trung bình của tất cả các liên kết trong mạng:



 


Ee Ww
ew
k
jiKk
jibMinimize
ij
Dji
),(max
,
),(
0:),(

(3.7)
+ Giảm thiểu số lượng các liên kết sợi được sử dụng để cho
tất cả các lightpaths:

  
  

0:),( ),(
,
}0),(|{
ij
Dji jiKk Ww
ew




   

0:),( ),(
,
)0),(|(
ij
Dji jiKk Ee Ww
ew
ke
jibdMinimize
(3.10)
3.2. Các giải thuật tiến hóa trong tối ưu hóa đa mục tiêu.
3.2.1. Thuật toán đáp ứng tiến hóa.
EA là một thủ tục lặp ngẫu nhiên để tạo ra các nghiệm thăm dò
cho một bài toán P nào đó. Thuật toán điều khiển một bộ sưu tập P
của các cá nhân (quần thể), một trong số đó bao gồm một hoặc
nhiều nhiễm sắc thể. Các nhiễm sắc thể này cho phép mỗi cá nhân
đại diện cho một nghiệm tiềm năng cho các bài toán đang được
xem xét.
Toàn bộ quá trình được phác thảo trong hình 3.1.

Hình 3.1: Tác giả của phương pháp tiến hóa để tối ưu hóa.
Thuật toán tiến hóa như sau:
1. P ← áp dụng ι trên G để có được các cá nhân μ (quản thể
ban đầu);
10


t
P
.
4. Xếp hạng cá nhân theo giá trị sức mạnh của họ và k-
khoảng cách hàng xóm gần nhất nơi
NNk 
(3.26)
5. Môi trường lựa chọn
a.Nếu kích thước của
1t
P
vượt quá thì loại bỏ các
cá nhân có tối thiểu k- khoảng cách hàng xóm gần nhất trong
1t
P

cho đến khi
1t
P
=
N

b.Nếu kích thước của
1t
P
là ít hơn so với
N
thì Điền
1t
P


b. GA trọng số ngẫu nhiên (RWGA).
2. So sánh trực tiếp của độ chi phối Pareto.
a. GA đánh giá vector (VEGA).
b. Niched Pareto GA (NPGA).
3. Tiếp cận xếp hạng cụ thể.
a. GA Đa mục tiêu (MOGA).
b. GA xếp loại không bị chi phối (NSGA) và GA xếp
loại nhanh không bị chi phối (NSGA-II).
c. Thuật toán tiến hóa đầy đủ Pareto (SPEA) và bản
cải thiện SPEA là (SPEA2).
4. Phương pháp tiếp cận dựa trên không dân cư.
a. Chiến lược tiến hóa Pareto lưu trữ (PAES).
CHƯƠNG 4: MÔ PHỎNG VÀ ĐÁNH GIÁ KẾT
QUẢ
4.1. Mô hình mô phỏng.
Trong phần này, bài toán thiết kế RWA đa mục tiêu và mô
hình thiết kế sẽ được trình bày. Bài toán RWA trong thiết kế mạng
quang WDM được xem xét để hỗ trợ nhiều yêu cầu liên lạc đồng
thời (bài toán luồng đa yêu cầu kết nối) Mỗi yêu cầu kết nối có rất
nhiều tuyến có thể và mỗi tuyến có một số lựa chọn gán kênh bước
sóng. Bài toán thiết kế mạng trong chương này là để tối đa hóa số
yêu cầu được chấp nhận từ một tập các yêu cầu đã định sẵn và để
giảm thiểu số lượng bước sóng yêu cầu. Điều này cho phép một số
yêu cầu liên lạc nhất định bị chặn để tiết kiệm một số kênh bước
sóng. Yêu cầu liên lạc đã được gán thành công với một bước sóng
được gọi là "yêu cầu được chấp nhận". Hàm mục tiêu của bài toán
bao gồm:
1. Mục tiêu thiết kế đầu tiên là để tối đa hóa số lượng yêu
cầu kết nối được chấp nhận. Một số lượng lớn các yêu cầu chắc

-
max
K
K
f
A
w

(4.3)
Tùy theo:

NiQq
otherwise
Desti
sourcei
qq
qq
iEe Kk
ke
q
iEe Kk
ke
q








Kk
k
q
Qq;1

(4.6)

EeQq
Kk
q
ke
q



,;
,

(4.7)




Qq
qA
Q

(4.8)



Ee
ke
q
KkQqH ,;
,

(4.12)

KkQqLD
Ee
ke
qe



,;).(
,

(4.13)

Qq
q
 };1,0{

(4.14)

Kk
k
 };1,0{


Thuật toán di truyền phân loại nhanh không bị chi phối
(NSGA-II) được biết như là một kỹ thuật hiệu quả để tìm kiếm tập
hợp tối ưu Pareto trong bài toán tối ưu hóa đa mục tiêu chung.
NSGA-II là một thuật toán rất nhanh để có thể hội tụ nhanh chóng
về mặt trước Pareto. NSGA-II đã được đề xuất bởi Deb[11] và
được mô tả như sau.
Gọi R
t
là đại diện cho tổng số quần thể, P
t
là quần thể được
bảo tồn, Q
t
là quần thể được tái tổ hợp của thế hệ t. F
i
là mặt trước
i, trong đó i là một số nguyên dương. Lưu ý rằng các nghiệm trong
mặt trước F
1
là tốt hơn so với những nghiệm trong mặt trước của
F
2
, và cứ như vậy tiếp tục.
1. Kết hợp P
t
và Q
t
để R
t
.

6. Chọn lựa chỉ có một nửa đầu tiên của quần thể R
t
và gán
cho P
t+1
.
7. Tái kết hợp (qua lai tạo và đột biến) quần thể P
t +1
và gán
cho Q
t+1
.
8. Tăng vòng lặp (t = t + 1).
9. Lặp lại bước 1-8, cho đến quá trình lặp được thỏa mãn
bởi số lần lặp tối đa.
Từ thuật toán NSGA-II, hai thủ tục quan trọng của NSGA-II
bao gồm thủ tục gán độ hợp (xếp loại không bị chi phối nhanh và
gán khoảng cách tạo đám) và thủ tục lựa chọn. Quần thể xem xét
bao gồm nhiều cá thể. Mỗi cá thể trong quần thể sẽ luôn được gán
một thứ hạng hoặc bậc vì lý do đó mà các cá thể ưu tú được duy trì
cho thế hệ sau. Các cá thể ưu tú sẽ có một thứ hạng thấp hơn hoặc
tốt hơn so với những cá thể khác. Thứ hạng của các nghiệm được
tính toán từ sắp xếp không bị chi phối nhanh trước. Sau đó, các
nghiệm trong cùng một mặt trước được sắp xếp bằng việc sử dụng
thuật tóan gán khoảng cách tạo đám Việc phân hạng được thể hiện
trong thủ tục 1 và 2 trong hình 4.2.

Hình 4.2: Thủ tục NSGA-II

4.2.1.1. Gán độ hợp (Fitness assignment)

i
là mặt trước i trong đó i là số nguyên dương, D
i
là
khoảng cách tạo đám của nghiệm i trong mặt trước F
i
, N là số
lượng nghiệm trong mặt trước F
i
,
max
m
f
và
min
m
f
là các giá trị cực đại
và cực tiểu của mục tiêu m.
1. Thiết lập khoảng cách tạo đám của cá thể i (D
i
) = 0, cho
tất cả các cá thể trong F
i
.
2. Đối với mỗi mục tiêu m
a. Sắp xếp theo thứ tự tăng dần các cá thể i theo giá
trị mục tiêu f
m
.

4.2.1.2. Thủ tục lựa chọn
Ban đầu, cá thể có một bậc mặt trước thấp hơn sẽ được
chọn. Nếu không gian có sẵn của quần thể trong thế hệ tiếp theo
không thể hỗ trợ toàn bộ các cá thể trong mặt trước F
i
, cá thể trong
cùng một mặt trước có khoảng cách tạo đám lớn hơn sẽ được lựa
chọn trước tiên như thể hiện trong thủ tục 3 hình. 4.2.
Thủ tục lựa chọn
1.Đối với mỗi cá thể i
a. Chọn toàn bộ các cá thể có bậc mặt trước thấp hơn
trước tiên.
b. Nếu toàn bộ các cá thể trong mặt trước F
i
không
thể được lấp đầy trong không gian có sẵn trong các thế hệ tiếp theo,
thì chọn các cá thể có số khoảng cách tạo đám lớn hơn trước tiên.
4.2.2.Thuật toán di truyền cho việc định tuyến và gán bước sóng
theo bậc tối thiểu trước tiên (GA-MDF)
Thuật toán này là một thuật toán heuristic gọi là thuật toán
di truyền cho việc định tuyến với việc gán bước sóng bậc tối thiểu
trước tiên (GA-MDF). GA-MDF có hai phần là định tuyến bằng
thuật toán di truyền và gán bước sóng theo bậc tối thiểu trước tiên.
4.2.2.1. Thuật toán di truyền cho định tuyến
Trước đây, thuật toán di truyền được sử dụng để giải quyết
bài toán định tuyến trong mạng quang WDM [3]. Banerjee và
Sharan đã đề xuất một thuật toán di truyền dựa trên tiếp cận định
tuyến luân phiên cố định.
Mã hóa chuỗi: Mã hóa chuỗi là một quá trình mã hóa bài
toán tổ hợp thành một tập hợp các gen hoặc nhiễm sắc thể. Mã hóa

Thuật toán MDF có thể được trình bày như sau:
1.Sắp xếp tất cả các yêu cầu theo số lượng các mức độ từ
mức độ nhỏ nhất đến mức độ lớn nhất.
2. Tại hạng đầu tiên (số lượng mức độ ít nhất, hoặc bị chồng
lấn ít nhất bởi yêu cầu khác), gán bước sóng đầu tiên.
3. Tại yêu cầu tiếp theo, nếu yêu cầu không bị chồng lấn với
các yêu cầu trước đó, gán cùng kênh bước sóng tương tự như yêu
cầu trước đó, nếu không thì gán bước sóng tiếp theo.
4. Lặp lại bước 3, cho đến khi tất cả các yêu cầu được xem
xét.
Ví dụ MDF
Yêu cầu 2 (
2
): từ nút 2 đến nút 4  kênh bước sóng 1.
Yêu cầu 3 (
3
): từ nút 3 nút 4  kênh bước sóng 1.
Bởi vì nó không chồng chéo với yêu cầu kết nối trước
đó.
Yêu cầu 1 (
1
): từ nút 1 đến nút 3  kênh bước sóng2.
Bởi vì nó bị chồng chéo với 
2
và 
3Hình 4.8: Một đồ thị phụ trợ cho thuật toán mức độ tối thiểu trước
tiên (MDF)

Thuật toán K-means cơ bản được thể hiện như sau:
1. Chọn K điểm như là trọng tâm ban đầu.
2. Repeat (Lặp lại)
a. Hình thành K cụm bằng cách gán mỗi điểm cho
trọng tâm gần nhất với nó.
b. Tính toán lại trọng tâm của mỗi cụm
3. Until (Cho đến khi) các trọng tâm không thay đổi.
Độ gần của các nghiệm so với trọng tâm của nó chính là
khoảng cách Euclide. Vấn đề chính trong thuật toán K-means là để
tìm giá trị thích hợp của K.
4.3 Kết quả mô phỏng.
Thiết kế mạng RWA đa mục tiêu với một cấu hình mạng và
một tập các yêu cầu đã cho sẽ được xem xét trong một số thí
nghiệm. Một số lượng giới hạn các kênh bước sóng trong mỗi cạnh
hoặc liên kết của mạng sẽ được áp đặt và ít nhất 80% các yêu cầu
phải được chấp nhận. Một tập hợp các bài toán kiểm tra với số
lượng các yêu cầu khác nhau sẽ được tạo ngẫu nhiên theo phân bố
đều trong mỗi bài kiểm tra. Các mạng ví dụ khác nhau được chọn
trong các thí nghiệm như cho thấy trong các hình 4.10, 4.11 và 4.12
bao gồm mạng NFSNET với 14 nút và 42 cạnh định hướng, mạng
CHNNET với 15 nút và 54 cạnh định hướng và mạng ARPANET
với 20 nút và 64 cạnh hướng [30]. Đối với mỗi kích thước bài toán,
một tập hợp các nhu cầu thông tin liên lạc được khảo sát bằng một
tập hợp các kênh bước sóng. Ở đây giả định rằng tất cả các cạnh có
cùng một số khả năng bước sóng. Hình 4.11: Mạng lưới Quốc gia Trung Quốc (CHNNET) với 15 nút
và 54 cạnh hướng S
ố kênh b
ư
ớc sóng

S
ố yêu cầu
đư
ợc chấp nhậ
n

S
ố kênh b
ư
ớc sóng

S
ố yêu cầu
đư
ợc chấp nhận

S
ố kênh b
ư
ớc sóng

Số yêu cầu được chấp nhận

NPSNET 21 14 15 42 3 2 4 GA-MDF
FAR-FF
14,806.3
11,986.7
44,419.0
35,960.0
CHN 27 15 18 54 3.6 3 5 GA-MDF
FAR-FF
16,512.7
12,344.7
49,538.0
37,034.0
ARPANET

32 20 1.6 64 3.2 3 4 GA-MDF
FAR-FF
29,435.0
21,540.3
88,305.0
64,621.0
Bảng 4.2 cho thấy các kết quả thu được với tổng số 150 yêu cầu sử dụng tiếp cận Weighted-Sum, trong đó 11 trường hợp giá trị trọng số
được xem xét. Những kết quả này (được hiển thị là "○" ) được so sánh với kết quả thu được từ NSGA-II (hiển thị là "×") trong hình 4.16.
Hình 4.16: Kết quả từ phương pháp tiếp cận Weighted-Sum trong các trường hợp khác nhau của trọng số và NSGA-II.

Bảng 4.2: Kết quả từ cách tiếp Weighted-Sum với các trường hợp khác nhau của các thông số trọng số (150 mặt hàng).
{W
0

{0.8,0.2}
{0.7,0.3}
{0.6,0.4}
{0.5,0.5}
123.0
121.0
122.0
122.0
123.0
9.0
9.0
9.0
9.0
9.0
{0.3,0.7}
{0.2,0.8}
{0.1,0.9}
{0.0,1.0}

127.0
127.0
140.0
150.0
10.0
11.0
13.0
17.0
Như được thấy trong Bảng 4.3, thuật toán NSGA-II đòi hỏi nhiều tính toán, với thời gian CPU tính toán trung bình là 14806,3 s đối
với trường hợp của 150 yêu cầu thu được từ thuật toán NSGA-II, trong khi thời gian tính toán thu được từ cách tiếp cận Weighted-Sum (với
11 trường hợp trọng số) chỉ là 349,0 x 11 = 3839 s.

6.503
1617.7
6403.3
14806.3
Total 10
30
50
100
150
1090.0
1293.0
1656.0
1684.0
1921.0
33.0
300.0
1077.0
4363.0
11518.0
7200.0
7200.0
7200.0
7200.0
7200.0
255.0
1816.0
4853.0
19210.0
44419.0
Đối với các cơ chế xén tỉa, phân nhóm dữ liệu bằng K-means được

15
17
19
21
23
3.23
9.68
16.13
22.58
29.03
35.48
41.94
48.39
54.84
61.29
67.74
74.19
2612.19
301.25
107.50
54.62
32.92
24.58
17.33
15.67
8.50
6.50
5.00
4.00
2612.19

87.10
93.55
100.00
3.00
2.00
1.00
0.00
3.00
2.00
1.00
0.00
0.11
0.08
0.04
0.00
Từ hình 4.18 cho thấy, SSE giảm nhanh khi K được thay
đổi từ 1 đến 3 và 5. Đồ thị hình chiếu cho thấy SSE thay đổi nhẹ từ
K = 7 tới 31. Đối với bài toán RWA đa mục tiêu đã được xét này,
K = 5 hoặc 7 là tối ưu bởi vì những giá trị này không phải mất
nhiều thời gian để đưa ra một sự lựa chọn và các SSE có thể chấp
nhận được. Với K = 5, đó là khoảng 16% trong những nghiệm thu
được, trong khi nó là khoảng 23% trong những nghiệm được cho
K = 7. Hình 4.18: Mối quan hệ giữa SSE và số lượng trọng tâm.
% Kết quả thu được

tốt nghiệp của sinh viên đại học và cho các nghiên cứu chuyên sâu
tiếp theo đối với sinh viên cao học.
5.2. Hướng nghiên cứu, phát triển
Nghiên cứu trong đề tài có một số đóng góp như sau: (1)
Phương pháp GA-MDF hiệu quả được đề xuất cho bài toán RWA.
(2) NSGA-II cùng với thuật toán GA-MDF là có hiệu quả được áp
dụng để giải quyết bài toán RWA đa mục tiêu thiết kế mạng. (3)
Cơ chế được xén tỉa được áp dụng để lọc một số lượng lớn các
nghiệm chủ yếu để giúp người ra quyết định trong việc lựa chọn
nghiệm cuối cùng trong tối ưu hóa bài toán RWA đa mục tiêu
thiết kế mạng.
Đề tài có thể được mở rộng để giải quyết bài toán RWA
động nhận biết được suy giảm chất lượng truyền dẫn hoặc/và có sử
dụng các bộ chuyển đổi bước sóng ở trên mạng.