BỘ GIÁO DỤC VÀ ĐÀO TẠO TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG
VIỆT NAM
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Phạm Quốc Huy NGHIÊN CỨU XÂY DỰNG
THUẬT TOÁN THIẾT KẾ TOPOLOGY MẠNG
ÁP DỤNG CHO MẠNG
THẾ HỆ SAU NGN
Chuyên ngành: Kỹ thuật viễn thông
Mã số: 62 52 70 05

TÓM TẮT LUẬN ÁN TIẾN SỸ KỸ THUẬT


Có thể tìm hiểu luận án tại:
Thư viện Quốc gia
Thư viện Học viện công nghệ Bưu chính Viễn thông MỞ ĐẦU
1. Tính cấp thiết của đề tài
Với nhu cầu phát triển ngày càng mạnh mẽ, đa dạng và phong phú
của các dịch vụ thông tin băng rộng thế hệ mới, bài toán thiết kế
topology mạng NGN (Next Generation Network) cần được xem xét
và mở rộng để đáp ứng với những yêu cầu mới đó là :
- Đảm bảo chất lượng dịch vụ cho các loại hình dịch vụ triển khai
trên mạng.
- Đảm bảo khả năng dự phòng của mạng trong quá trình cung cấp
dịch vụ.
2. Đối tượng, mục đích và phạm vi nghiên cứu
Đối tượng nghiên cứu của luận án này là topology của mạng
backbone cho các mạng đa dịch vụ có hạ tầng IP như mạng NGN do
tính chất quan trọng của mạng backbone đối với chất lượng dịch vụ
trên toàn bộ mạng.

thêm các thuật toán có thể áp dụng cho việc giải các bài toán tương
tự.
Về ý nghĩa thực tiễn
- Các kết quả có thể áp dụng cho việc thiết kế topology mạng
backbone NGN và tính toán các mạng tập hợp lưu lượng NGN.
- Các kết quả nghiên cứu cũng có thể áp dụng phương pháp thiết kế
các mạng truy nhập với công nghệ thuộc thế hệ 3G hoặc 4G.
- Một số kết quả phân tích đã được sử dụng trong quá trình tính toán
lưu lượng, thiết kế cấu hình mạng MAN-E cho các bưu điện tỉnh của
Tập đoàn Bưu chính Viễn thông Việt nam .
5. Bố cục của luận án

2
Bài toán thiết kế topology mạng được xem xét và giải quyết với mức
độ phức tạp tăng dần để thuận tiện cho việc so sánh các đề xuất giải
bài toán được đưa ra ở đây với các kết quả nghiên cứu đã có và phù
hợp với sự phát triển mạng và công nghệ. Bài toán sẽ được đặt ra bắt
đầu với ràng buộc là dung lượng tuyến kết nối là hữu hạn; tiếp theo
những ràng buộc về trễ, khả năng hồi phục lần lượt được bổ sung.
Như vậy, luận án bao gồm phần mở đầu, năm chương nội dung và
phần kết luận, cụ thể như sau:
Chương 1: Trình bày bài toán thiết kế topology mạng backbone với
ràng buộc về dung lượng tuyến kết nối hữu hạn. Trên cơ sở đánh giá,
phân tích một số phương pháp, thuật toán thiết kế trước đây, phương
pháp thiết kế topology mạng bachbone sử dụng thuật toán di truyền
được lựa chọn và sẽ là khuôn khổ chung, thống nhất cho việc giải
quyết bài toán thiết kế đặt ra với các ràng buộc khác nhau.
Chương 2: Trình bày các vấn đề kỹ thuật liên quan đến thuật toán di
truyền. Trên cơ sở đó, chương này đề xuất một phương pháp mã hóa
cùng các toán tử nhằm giải quyết bài toán đặt ra ở chương 1. Các kết

c
ij
và f
ij

tương ứng là băng thông phân bổ và luồng dữ liệu trung bình trên
tuyến kết nối (ij); d
ij
(c
ij
) là chi phí thuê băng thông c
ij
của tuyến kết
nối (ij);
ij
λ
là chi phí cho một đơn vị dung lượng luồng của tuyến
kết nối (ij).
R biểu diễn ma trận các nhu cầu r
pq
,
R
r
pq
∈
∀
được chuyển tải trên
G*(V,A); F
pq
biểu thị luồng tổng cộng của nhu cầu r

Khi đưa ra một graph vô hướng với các giá trị |V| , |E| và một ma
trận nhu cầu R. Hãy xác định sao cho tối
thiểu hóa hàm mục tiêu định nghĩa dưới đây.
),(),(
*
EVGAVG ⊆
∑∑
−
=>
=
1
1
n
i
n
ij
ijij
cD
λ
(1.1)
Với giả thiết:

∑
=
r
pq
r
pq
fF
PrVqp

Biểu thức (1.2) nhằm đảm bảo mọi nhu cầu lưu lượng đều được
chuyển tải đầy đủ trên mạng và mỗi nhu cầu có thể đi trên một số
đường dịch vụ r khác nhau. Biểu thức (1.3) đảm bảo băng thông
phân bổ trên mỗi tuyến kết nối (ij) để thiết lập các đường dịch vụ r là
bằng tổng các luồng lưu lượng chuyển trên đó. Biểu thức (1.4) thể
hiện ràng buộc về dung lượng tuyến kết nối hữu hạn.
1.2 So sánh và lựa chọn phương pháp
Một số phương pháp tiếp cận cho việc giải quyết vấn đề trên đã được
khảo sát và có thể chia ra thành hai nhóm chính, bao gồm: phương
pháp quy hoạch toán học và phương pháp theo thực nghiệm.

5
Từ những nhận xét và phân tích về mỗi phương pháp tiếp cận,
phương pháp giải quyết bài toán được xác định sử dụng phương
pháp tiếp cận theo thực nghiệm với thuật toán di truyền để giải quyết
vấn đề.
Cùng với việc xác định phương pháp tiếp cận, vấn đề đặt ra tiếp theo
là làm thế nào để áp dụng hiệu quả thuật toán di truyền cho bài toán
đặt ra. Do vậy, chương sau sẽ khảo sát một số vấn đề liên quan đến
thuật toán di truyền.
CHƯƠNG 2. THUẬT TOÁN DI TRUYỀN VÀ ĐỀ XUẤT
PHƯƠNG PHÁP MÃ HÓA CÙNG CÁC TOÁN TỬ KHI
THIẾT KẾ TOPOLOGY MẠNG BACKBONE
2.1 Thuật toán di truyền
Để có thể áp dụng hiệu quả thuật toán di truyền cho vấn đề đang xét,
các vấn đề lý thuyết và kỹ thuật liên quan đến thuật toán di truyền
được xem xét như: lý thuyết sơ đồ, mã hóa, kế hoạch tái tạo, hàm
phù hợp, các toán tử lai tạo và đột biến, hội tụ của thuật toán…
2.2 So sánh một số phương pháp mã hóa đã được sử dụng
Các phương pháp mã hóa áp dụng cho một số bài toán thiết kế


2480000000
2500000000
2520000000
2540000000
2560000000
2580000000
2600000000
2620000000
2640000000
2660000000
2680000000
0 102030405060
Số thế hệ
Chi phí trung bìn
h
Edge-Set
Ad- GA
B-GA
Hình 2.5 Chi phí trung bình ứng với các thuật toán khác nhau
cho mạng lưới đầy đủ 20 nút sau 50 thế hệ.

7


Một số ký hiệu
Các ký hiệu như ở bài toán thiết kế ở chương 1 được sử dụng lại,
ngoài ra bổ sung thêm một số ký hiệu, bao gồm:
γ
là lưu lượng tổng cộng đi vào mạng;
L là chiều dài trung bình của gói tin tính theo bits;
ave
T là trễ trung bình trên toàn mạng;
pq
ee
T
−
là trễ đầu cuối – đầu cuối.
Phát biểu bài toán
Khi đưa ra một graph vô hướng với các giá trị |V| , |E| và một ma
trận nhu cầu R. Hãy xác định sao cho tối
thiểu hóa hàm mục tiêu định nghĩa dưới đây.
),(),(
*
EVGAVG ⊆
∑∑
−
=>
=
1
1
n
i
n
ij

∈
∀
,,
(3.7)
max
ijij
cc ≤

Vqpji
∈
∀
,,,
(3.8)
∑∑
=>
=
1p pq
pq
F
γ
−1n n

Vqp
∈
∀
,
(3.9)
∑
=
≤

pq
ee
T
fc
f
aT
max,, −
∈
−
≤
−
=
∑
Vqpji
∈
∀
,,,
,
P
r
∈
∀
(3.10b)
Các biểu thức từ (3.6) đến (3.8) có ý nghĩa tương tự các biểu thức từ
(1.2) đến (1.4) trong chương 1.
Biểu thức (3.9) dùng để xác định tổng lưu lượng đi vào mạng.
Với trường hợp thiết kế topology mạng cho các dịch vụ dữ liệu sẽ sử
dụng các biểu thức từ (3.5) đến (3.9) và biểu thức (3.10a) – ràng
buộc về trễ trung bình. Còn với trường hợp thiết kế topology mạng
cho các dịch vụ thời gian thực sẽ sử dụng các biểu thức từ (3.5) đến

ee
ijij
T
L
fc
λ
ij
λ
∑
∈
−
+= *
max,
(3.17)
3.4 Một số kết quả tính toán số
Các kết quả tính toán số thực hiện với hai thuật toán thiết kế
topology với ràng buộc trễ trung bình. Thuật toán thứ nhất là thuật
toán đề xuất ở đây – thuật toán GA-DR. Thuật toán thứ hai – thuật
toán FD-A [25]. Việc so sánh hiệu quả của thuật toán dựa trên một
số khía cạnh: Chi phí, Thăng giáng trễ, Số tuyến kết nối sử dụng.

2400000000
2600000000
2800000000
3000000000
3200000000
3400000000
3600000000
3800000000
0 500 1000 1500 2000 2500

0.018
0 50 100 150 200
Số lượng đường kết nối
Độ trễ trên đường kết nối
FD-A
GA-DR
Hình 3.5 Số lượng và độ trễ trên các tuyến kết nối
Hình 3.5 cho thấy số lượng tuyến kết nối sử dụng trong các giải pháp
tìm được theo thuật toán GA-DR nhỏ hơn khoảng 1/3 so với thuật
toán FD-A. Trễ trên các tuyến kết nối khoảng từ 6,2ms đến 6,5 ms
đối với giải pháp tìm được theo thuật toán GA-DR so với khoảng từ
2,2 ms đến 16,5ms của thuật toán FD-A. Điều này cho thấy giải pháp
tìm được theo FD-A có khả năng gây nghẽn cục bộ nhiều hơn so
với GA-DR.
3.5 Một số nhận xét
Các giải pháp tìm được theo thuật toán đề xuất GA-DR có chi phí
thấp hơn. Mặt khác, số lượng tuyến kết nối sử dụng trong thuật toán
đề xuất cũng ít hơn nhiều (khoảng gần 1/3 so với thuật toán trước
đây).
Mức độ thăng giáng trễ trên các tuyến kết nối của thuật toán đề xuất
cũng ít hơn so với thuật toán trước.

r
f
pq
b
f
bs
ij
c
băng thông phân bổ cho đường dự phòng trên tuyến kết nối
(ij) khi đang xét sự cố
0
sSs
−
∈
.
PD là tập nhu cầu lưu lượng cần bảo vệ khi có sự cố mạng,

RPD ⊆

13
pq
bij,
δ
có giá trị bằng 1 nếu đường dự phòng b có chứa tuyến kết
nối (ij) chuyển tải một phần lưu lượng bị ảnh hưởng
bởi sự cố
pq
r
f
0

1
1
)(
n
i
n
ij
b
ijijij
ccD
λ
(4.1)
Với giả thiết:
∑
=
r
pq
r
pq
fF
PrVqp
∈
∈
∀ ,,
(4.2)
∑∑∑
=>
==
1
,

(4.4)
pq
n n
pqbs
−1
b
p pqb
bijij
fc
∑∑∑
=>
=
1
,
δ

0
,,,, sSsVqpji
−
∈
∀
∈
∀
(4.5)
)max(
bs
ij
b
ij
cc =

0
sSs
−
∈
. Biểu thức (4.6)
để tính băng thông phân bổ trên mỗi tuyến kết nối để thiết lập các
đường dự phòng là bằng phần lưu lượng hồi phục lớn nhất ứng với
mạng ở trạng thái
0
sSs
−
∈
nào đó. Biểu thức (4.7) đảm bảo tổng
băng thông phân bổ để tạo nên các đường dịch vụ và đường dự
phòng là không vượt quá dung lượng cực đại của tuyến kết nối.
4.2 Đề xuất thuật toán thiết kế topology mạng có khả năng hồi
phục
Căn cứ vào những ưu điểm của mỗi chiến lược hồi phục, thuật toán
đề xuất sẽ sử dụng theo chiến lược hồi phục đường kết hợp chiến
lược hồi phục phụ thuộc trạng thái và mỗi nhu cầu có thể dự phòng
trên nhiều đường dự phòng khác nhau. Phương pháp thiết kế
topology mạng có khả năng hồi phục được đề xuất gồm hai bước
như sau:
Bước một, sử dụng thuật toán di truyền để thực hiện quá trình tìm
một topology mạng đảm bảo truyền tải tập R các nhu cầu lưu lượng.
Bước hai, thực hiện quá trình định tuyến lại các nhu cầu lưu lượng
cần hồi phục theo “chiến lược hồi phục lặp”.
Thuật toán đề xuất sẽ thực hiện quá trình xác định các đường dự
phòng cho mỗi nhu cầu cần hồi phục với một số lần lặp xác định
nhằm tìm ra tập các đường dự phòng hiệu quả nhất cho mỗi nhu cầu.

Phương thức 2
Phương thức 3
Phương thức MCR

Hình 4.7 Trường hợp nhu cầu lưu lượng cần dự phòng chiếm 60%
lưu lượng toàn bộ mạng.
Tuy nhiên, với trường hợp mức độ nhu cầu hồi phục thấp khoảng
trên dưới 10% hoặc tương đương với các trường hợp mà dung lượng
các đường kết nối còn dư thừa nhiều khi so sánh tương đối với nhu
cầu cần hồi phục, thì thuật toán MCR cho kết quả trội hơn đôi chút
(xem chi tiết trên hình 4.5 của luận án).

16
Các tính toán được thực hiện nhằm so sánh mức độ tiết kiệm chi phí
băng thông dự phòng của phương thức hồi phục lặp 3 (MPR-R) và
phương thức hồi phục 2 (MPR) với phương thức hồi phục 1 (SPR).
Kết quả được trình bày trên hình 4.8 dưới đây.

0
1
2


17
CHƯƠNG 5. XÂY DỰNG THUẬT TOÁN THIẾT KẾ
TOPOLOGY MẠNG VỚI MỤC TIÊU TỐI THIỂU HÓA CHI
PHÍ, THỎA MÃN RÀNG BUỘC VỀ TRỄ VÀ KHẢ NĂNG HỒI
PHỤC
Nhằm đáp ứng yêu cầu thực tế của mạng NGN, trong chương này sẽ
mở rộng bài toán thiết kế ở chương một với đồng thời cả hai ràng
buộc về trễ và khả năng hồi phục.
5.1 Bài toán thiết kế topology mạng với ràng buộc về trễ và khả
năng hồi phục
Một số ký hiệu
Các ký hiệu như ở bài toán thiết kế ở chương 1 được sử dụng lại,
ngoài ra bổ sung thêm một số ký hiệu, bao gồm:
pq
rij
d
,
liên quan đến ràng buộc về trễ trên các đường dịch vụ, có giá
trị ≥ 1.
pq
bij
d
,
liên quan đến ràng buộc về trễ trên các đường dự phòng, có
giá trị ≥ 1, hiện lấy giá trị = 1.
Phát biểu bài toán
Bài toán thiết kế topology mạng với ràng buộc về trễ và khả năng hồi
phục được phát biểu như sau:
Khi đưa ra một graph vô hướng với các giá trị |V| , |E| và một ma

fF
PrVqp
∈
∈
∀
,,
(5.2)

18
∑∑∑
=>
=
1
,
p pqr
pq
r
pq
rijij
faf
−1n n

PrVji
∈
∈
∀
,,
(5.3)
∑∑
=

0
,,,, ssVqpji
∈
∀
∈
∀
(5.5)
pq
n n
pqpqbs
−1
b
p pqb
bijbijij
fdc
∑∑∑
=>
=
1
,,
δ

0
,,,,, sSsPDpqVqpji
−
∈
∀
∈
∀
∈

∑∑
−
=>
=
1
1
n
p
n
pq
pq
F
γ

Vqp
∈
∀
,
(5.9)
∑
=
≤
−
=
ij
ave
ijij
ave
T
fc

−
≤
−
=
∑

Vqpji
∈
∀
,,,
,
P
r
∈
∀
(5.10b)
Ý nghĩa của các biểu thức có thể xem chi tiết ở các chương 1, 3 và 4.
Phần tiếp sau đây sẽ trình bày phương pháp giải quyết bài toán này.
5.2 Đề xuất thuật toán thiết kế topology mạng
Thuật toán thiết kế topology được đề xuất với các bước sau:
Thiết lập topology.
Bước thiết lập topology nhằm tạo ra topology từ nhiễm sắc thể.
Topology nhận được tại bước này chỉ thỏa mãn ràng buộc dung
lượng tuyến kết nối hữu hạn mà chưa thỏa mãn các điều kiện ràng
buộc về trễ và khả năng hồi phục.
Biến đổi topology

19
Topology tiếp tục được biến đổi để thỏa mãn điều kiện ràng buộc về
trễ trung bình hoặc trễ đầu cuối – đầu cuối. Kết thúc bước này, các

c
5.3 Một số kết quả tính toán số
Các tính toán số cho trường hợp trễ trung bình 10ms. Hình 5.3 trình
bày kết quả tính toán các chi phí khởi đầu, chi phí bổ sung để thỏa
mãn ràng buộc về hồi phục mạng, chi phí bổ sung để thỏa mãn ràng
buộc về trễ trung bình trong tổng chi phí.
0
500000000
1000000000
1500000000
2000000000
2500000000
3000000000
3500000000
0 10203040 5060
Số thế hệ
Chi phí
Chi phí khởi đầu
Chi phí bổ sung để thỏa mãn ràng buộc về trễ
t rung bình
Chi phí bổ sung để thỏa mãn ràng buộc về khả

0 102030405060
S
ố
th
ế
h
ệ
(x100)
T
ổ
ng chi phí Hình 5.9 Mức độ thay đổi về tổng chi phí bổ sung qua 5000 thế hệ
của mạng 50 nút

21

Kết quả trên cho thấy, với số lượng nút khá lớn (50nút) và số thế hệ
là 5000, thuật toán đề xuất và chương trình thực hiện có thể áp dụng
cho việc tính toán thiết kế các mạng theo yêu cầu thực tế hiện nay.
5.4 Một số nhận xét
Từ những kết quả tính toán ở trên, có thể thấy việc xem xét các
phương pháp tiếp cận nhằm nâng cao hơn nữa chất lượng tìm kiếm

phí thấp hơn đến 5% so với giải pháp cũ.
3. Đề xuất mới thuật toán thiết kế topology mạng có khả năng hồi
phục MPR-R cho phép tìm được các giải pháp với chi phí thấp
nhất, đặc biệt khi yêu cầu hồi phục mạng trên 40%. Thuật toán
nhằm giải quyết vấn đề đảm bảo tính liên tục khi cung cấp dịch vụ
trong môi trường mạng NGN.
4. Đề xuất mới thuật toán thiết kế topololgy mạng thỏa mãn các
ràng buộc về khả năng hồi phục mạng và độ trễ, làm cho hiệu quả
sử dụng băng thông tốt hơn, tiết kiệm chi phí, khả năng thiết kế
mạng linh hoạt hơn, đáp ứng yêu cầu thực tiễn mạng NGN hiện
nay.
Các kết quả nghiên cứu, đề xuất và tính toán của luận án này phù
hợp với mục đích nghiên cứu đề ra ban đầu. Những kết quả nghiên
cứu có thể áp dụng trong việc xây dựng những công cụ thiết kế
topology cho các mạng đa dịch vụ với hạ tầng mạng IP mà điển hình
là mạng NGN.
KIẾN NGHỊ VỀ NHỮNG NGHIÊN CỨU TIẾP THEO
Từ những kết quả nghiên cứu mà luận án đã đạt được, chúng tôi
cũng đề xuất những hướng nghiên cứu có thể triển khai tiếp theo:
* Nghiên cứu ứng dụng phương pháp thích nghi trong quá trình
thiết kế topology mạng.23