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
NGUYỄN QUỐC THÀNH NGHIÊN CỨU PHƯƠNG PHÁP VÀ
XÂY DỰNG PHẦN MỀM QUY HOẠCH
MẠNG TRUYỀN DẪN THẾ HỆ MỚI
CHUYEN NGÀNH: TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH
MÃ SỐ: 60.48.15

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS NGUYỄN QUANG HOAN TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT

HÀ NỘI - 2010
Quy hoạch mạng truyền dẫn thế hệ sau

gán theo từng bước sóng này vào
trong sợi quang để truyền đi.
2. Phương pháp quy hoạch mạng truyền dẫn DWDM
Cũng giống như các bài toán quy hoạch mạng khác, bài toán quy hoạch mạng truyền
dẫn quang cũng được chia thành các bước: quy hoạch chiến lược và quy hoạch cơ sở.
Quy hoạch mạng truyền dẫn thế hệ sau
[Type text]

2.1. Quy trình quy hoạch tổng quát cho mạng tuyền dẫn
.
 Quy hoạch chiến lược: kết quả của pha này sẽ đưa ra một số giải pháp về công
nghệ và kiến trúc mạng thích hợp. Thực hiện công việc này bằng phương pháp
chuyên gia, tức là thông qua việc nghiên cứu xu hướng công nghệ, so sánh phân
tích các công nghệ và kiến trúc mạng khác nhau.
 Quy hoạch cơ sở: pha này xác định cấu trúc và định cỡ mạng mục tiêu tương
ứng với mỗi giải pháp về công nghệ đã đưa ra trong pha đầu. Cấu trúc và kích
cỡ mạng đưa ra phải đảm bảo đáp ứng đủ nhu cầu dịch vụ đã được dự báo theo
từng thời kì và cấu trúc mạng phải tối ưu để giá thành đầu tư thêm cho cơ sở hạ
tầng mạng là nhỏ nhất. Với mỗi giải pháp về công nghệ và kiến trúc mạng được
đề xuất, pha này được chia làm 3 bài toán nhỏ: Xác định vị trí đặt nút mạng, xác
định cấu trúc mạng và định cỡ mạng.
QUY HOẠCH CHIẾN LƯỢC
 Xu hướng công nghệ
 So sánh phân tích công nghệ
 Ý kiến chuyên gia
- Nhu cầu dịch vụ
- Nhu cầu lưu lượng
XÂY DỰNG CẤU TRÚC MẠNG MỤC TIÊU
Xác định cấu trúc mạng
Định cỡ mạng

Phương pháp sử dụng GA ở đây có kết hợp với phương pháp 2-opt trong quá trình đột
biến. Việc kết hợp giữa hai phương pháp này nhằm đem lại kết quả cao trong tối ưu.

 Khởi tạo dân số: Sinh M chuỗi gien ngẫu nhiên.
 Lựa chọn tự nhiên: Tiến hành loại bỏ p
e
% dân số, tức là loại trừ đi M*p
e
/100 số
chuỗi gien trong dân số hiện tại.
 Sinh sản: Lựa chọn M*p
e
/100 cặp cha mẹ ngẫu nhiên để sinh ra M*p
e
/100 phần
tử thế hệ con, mỗi cặp cha mẹ sẽ sinh ra một phần tử con. Như vậy, dân số sẽ sẽ
được khôi phục lại như lúc ban đầu chưa tiến hành loại bỏ.
 Đột biến: Lựa chọn ngẫu nhiên theo tỷ lệ p
i
% độc lập các gien để thực hiện đột
biến theo phương pháp 2-opt.
b, Cấu trúc liên kết dạng lưới
Xây dựng cấu trúc liên kết dạng lưới
Mục đích:
+ Xây dựng cấu trúc liên cho mạng con
Đầu vào:
+ Tập các nút: V
S
= {v
i

nếu có kết nối từ i → j và e
ij
= 0 nếu không có kết nối từ i → j.
Ràng buộc:
+ Điều kiện địa lý thực tế, có một số cặp nút không thể có kết nối trực tiếp
+ Cấu trúc liên kết của mạng hiện tại
Thuật toán: Như trình bày trên đây [6], [7].
Quy hoạch mạng truyền dẫn thế hệ sau
[Type text] 2.4. Phương pháp định cỡ mạng và phân chia tài nguyên
a, Định cỡ cho mạng dạng vòng
Cấu trúc vòng được xem xét ở đây gồm có n nút (và n cạnh). Các nút được đánh số
theo chiều kim đồng hồ và cung giữa nút i và i+1 được gọi là a
i
. Cung giữa nút n và
nút 1 gọi là a
n
. Mỗi yêu cầu là đối xứng và theo hai hướng. Thuật toán được đề xuất
cho định tuyến các yêu cầu truyền dẫn trên mạng có cấu trúc vòng ở đây là thuật toán
của Lee và Cheng [5].
Thuật toán của Lee và Cheng
Mục đích:
+ Định tuyến cho các yêu cầu truyền dẫn của các cặp nút trên cấu trúc liên kết
dạng vòng
Đầu vào:
+ d = (d
1
, d

s-1
, a
s-2
, …, a
1
, a
n
, a
n-1
, …, a
t+1
, a
t
} là tập hợp các cung ngược chiều
kim đồng hồ mà yêu cầu truyền dẫn thứ j (từ nút s đến nút t, t  n) sẽ đi qua;
+ Ma trận P = [n  2m] được xác định như sau:
Khoảng cách, ma
trận lưu lượng
Khởi tạo mạng lưới đầy đủ và
tính trọng liên kết
Liên kết là cầu
nối?
Tìm liên kết chứa được duyệt
có trọng liên kết lớn nhất
Loại bỏ liên kết này
Thỏa mãn điều kiện
bảo vệ về liên kết?
Đánh dấu liên kết
đã được duyệt
Kết quả

jiP
0
1
)12,(










jj
jj
Pa
Pa
jiP
0
1
)2,(
+ x = (

1
x ,

1
x ,


+ y = (y
1
, y
2
, …, y
n
) là vector biểu diễn dung lượng trên các cung a
1
, a
2
,
, a
n
, với y
i
=

j
jiR ),( ;
+ z(x) = max
i
{y
i
} cung có dung lượng đặt trên nó là lớn nhất;
+ A = {a
i
y
i
 z(x) - 1} tập hợp các cung có dung lượng lớn.
Mục tiêu:

j
x  0,

j
x  0 j.
Thuật toán:
begin
gán x := (d
1
, 0, d
2
, 0, …, d
m
, 0);
thực hiện tính toán y, z(x), A;
gán i := 1;
while i

n do
begin
tạo một danh sách của các yêu cầu được bắt đầu tại nút thứ i và xắp
xếp theo thứ tự giảm dần của

j
P
;
gán yêu cầu j := giá trị đầu tiên trong danh sách tại nút thứ i;
while
AP
j

2
)(min
,min:
k
Pk
jjj
yz
xxx
j
x
;
Quy hoạch mạng truyền dẫn thế hệ sau
[Type text]

gán
















các yêu cầu lưu lượng giữa các cặp nút trong cùng một vòng và những yêu cầu lưu
lượng giữa các cặp nút không nằm trong cùng một vòng. Trong đó, lưu lượng giữa hai
nút mạng nằm trên hai vòng khác nhau sẽ được định tuyến theo nguyên tắc sau:
 Bước 1: Yêu cầu được định tuyến từ nút nguồn đến nút Hub của mạng con
 Bước 2: Định tuyến yêu cầu từ nút Hub đến nút đích.
Dựa trên nguyên tắc đã được này, thì việc định cỡ cho một mạng gồm có nhiều vòng
được giải quyết bằng 2 bước sau:
Bước 1: Cập nhật ma trận lưu lượng
Giả sử N
i
và N
j
là hai nút mạng thuộc 2 vòng khác nhau, N
k
là nút Hub của mạng. Yêu
cầu lưu lượng giữa các nút lần lượt là: d
ij
, d
ji
, d
ik
, d
ki
, d
jk
, d
kj
. Việc cập nhật được thực
hiện như sau:
d

i … k … j i … k … j
i
0 d
ik
d
ij

i
0 d
ik
+ d
ij
0
…

…k
d
ki
0 d
kj

k
d
ki
+ d
ji



Phương pháp định tuyến cho mạng dạng lưới là sự kết hợp của giải thuật di truyền
(GA) và định tuyến K shortest loopless paths của Yen để xác định các đường định
tuyến tối ưu cho các yêu cầu truyền dẫn của các cặp nút mạng [11]. Việc áp dụng thuật
toán của Yen sẽ cho ta kết quả là K đường định tuyến ngắn nhất cho mỗi yêu cầu dựa
trên bản đồ kết nối và độ dài của mỗi liên kết trong mạng [12]. Kết quả này sẽ được sử
dụng để xây dựng chuỗi gien trong giải thuật di truyền. Giải thuật di truyền áp dụng
cho bài toán định tuyến tối ưu trên mạng dạng lưới sẽ được trình bày dưới đây.
Giải thuật di truyền sử dụng cho định tuyến tối ưu
Khởi tạo dân số và mã hóa
Chuỗi gien được sử dụng là một chuỗi số nguyên dạng nhị phân 0 và 1, chuỗi gien
dùng để biểu diễn cho một giải pháp định tuyến được lựa chọn cho tất cả các yêu cầu
trong mạng. Mỗi chuỗi gien bao gồm nhiều chuỗi gien con. Trong đó, mỗi chuỗi gien
con sẽ biểu thị sự lựa chọn một đường định tuyến trong số K đường định tuyến có thể
của một yêu cầu (được xác định từ việc áp dụng thuật toán của Yen). Như vậy, nếu có
n cặp nút nguồn và đích, mỗi cặp tìm được K đường ngắn nhất thì độ dài của chuỗi
gien sẽ là log
2
k.n bít. Ví dụ như hình dưới đây.

Dân số được khởi tạo là lựa chọn ngẫu nhiên cho mỗi cặp nguồn và đích một đường
truyền được lựa chọn trong K đã được xác định bởi thuật toán của Yen với số dân ban
đầu là N phù hợp.
Hàm mục tiêu
Mục tiêu của việc định cỡ mạng là tối ưu giá thành và tối thiểu số bước sóng cần sử
dụng. Chính vì thế hàm mục tiêu được sử dụng trong GA cần biểu diễn được hai thành
phần này trong đó để có thể tối ưu trong GA.
+ Tối thiểu giá thành đầu tư:
Min(
∑

Sau quá trình lai tạo là quá trình đột biến. Đột biến được thực hiện một cách ngẫu
nhiên trên mỗi gien của chuỗi với xác xuất đột biến ở đây là 1/L, với L là chiều dài của
chuỗi gien. Đột biến sẽ biến đổi gien từ giá trị 0 thành giá trị 1 và ngược lại.
Lựa chọn dân số thế hệ kế tiếp
Việc lựa chọn dân số thế hệ kế tiếp trong quá trình tiến hóa của GA là quá trình lựa
chọn ngẫu nhiên theo tỷ lệ dựa trên nguyên lý bánh xe Rulet.
d, Định cỡ cho mạng kết nối liên khu vực
Với cấu trúc mạng phân cấp thì các yêu cầu của hai nút mạng thuộc hai mạng con khác
nhau sẽ được định tuyến theo nguyên tắc sau:
 Bước 1: Yêu cầu được định tuyến từ nút nguồn đến nút Hub của mạng con
 Bước 2: Định tuyến yêu cầu nút mạng Hub này đến nút mạng Hub của
mạng con chứa nút đích dựa trên cấu trúc mạng liên kết liên kết nối đã được
xác định
 Bước 3: Định tuyến yêu cầu từ nút Hub đến nút đích.
3. Phát triển phần mềm
Quy hoạch mạng truyền dẫn thế hệ sau
[Type text]

3.1. Thiết kế hệ thống phần mềm
Chức năng của phần mềm quy hoạch mạng truyền dẫn quang DWDM như cây chức
năng trong hình bên dưới:

I.3. Kiến trúc hệ thống phần mềm

NetPlan 2.0

D
ự báo
Dịch vụ
Mô hình


Xác định dung lượng bảo vệ
Phân chia tài nguyên
Xử lý dữ liệu đầu vào
C
ập nhật dữ liệu trong
các bước quy hoạch
Báo cáo kết quả
Dữ liệu
đầu vào
Lõi phần mềm
Báo cáo
Các kết quả
quy hoạch
Bản đồ
(MapInfo/MapBasic) Công cụ quy hoạch mạng
truyền dẫn thế hệ sau
Cơ sở dữ liệu
Quy hoạch mạng truyền dẫn thế hệ sau
[Type text]

I.3. Thiết kế hệ thống phần mềm

4. Phát triển mô-đun phần mềm
Phần mềm được xây dựng dựa trên phương pháp và thiết kế hệ thống như đã được
trình bày trong các phần trên. Phần mềm bao gồm những tính năng sau:
 Nhập dữ liệu đầu vào bao gồm: bản đồ, vị trí các nút mạng, ma trận lưu lượng

P709, 1998.
[5] EURESCOM, Dimensioning methods for optical network long-term planning,
Vol 5 of 9, Deliverable 3, EURESCOM Project P709, 1998.
[6] WUT, Description of NGI core network models and related optimization
problems, D.JRA.3.1.1, Design and Engineering of the Next Generation Internet,
towards convergent multi-service networks, 2004.
[7] WUT, Description of the selected methods and algorithms for solving the
problems specified in Deliverable D.JRA.3.1.1. Initial report on the effectiveness
of the methods, D.JRA.3.1.2, Design and Engineering of the Next Generation
Internet, towards convergent multi-service networks, 2004.
[8] Ernesto Q. Vieira Martins, Marta Margarida B. Pascoal and José Luis E. Santos,
An Algorithm for Ranking Loopless Paths, Department de Matemática,
Universidade de Coimbra, Portugal, July 1998.
[9] William M. Spears, Adapting Crossover in a Genetic Algorithm, Naval Research
Laboratory Washington, D.C. 20375 USA, 1995.
[10] Xiaoyu Yao and Chao Chen, Simulation Study of Diverse Routing and Protection
Algorithm in Mesh WDM Network, Department of Computer Science and
Engineering, University of Nebraska –Lincoln, Spring 2004.
[11] Nilanjan Banerjee, Vaibhav Mehta and Sugam Pandey, A Genetic Algorithm
Approach for Solving the Routing and Wavelength Assignment Problem in WDM
Networks, Department of Computer Science an Engineering, Indian Institute of
Technology, 2002.
[12] Andrew W. Moore, K-means and Hierarchical Clustering, School of Computer
Science Carnegie Mellon University, 2001.