Một số thuật toán gen cho thiết kế topology mạng có khả năng hồi phục

ho nhau, v´ı du. K = 2 va`
L = 5.
Ca´ theˆ’ i theˆ´ heˆ. n: 234156
Ca´ theˆ’ i sau khi thu.. c hieˆ.n doˆ.t bieˆ´n: 254136
Ngoa`i ra co´ theˆ’ thu.. c hieˆ.n toa´n tu
.’ doˆ. t bieˆ´n thoˆng qua vieˆ.c quay vo`ng pha’i hoa˘.c vo`ng tra´i
ta. i vi. tr´ı L cu’a chuoˆ˜i N nhu
. sau:
Quay vo`ng pha’i ta. i vi. tri. L = 5 vo´
.i ca´ theˆ’ i: 234156, keˆ´t qua’ ta.o ra ca´ theˆ’: 562341
Quay vo`ng tra´i ta. i vi. tri. L = 3 vo´
.i ca´ theˆ’ i:234156, keˆ´t qua’ ta.o ra ca´ theˆ’: 156234
Ta. i giai doa.n na`y, taˆ.p ca´c du
.`o.ng keˆ´t noˆ´i lij cu`ng vo´.i ba˘ng thoˆng phaˆn boˆ’ c
s
ij va` chi ph´ı
Gsij deˆ’ da’m ba’o truye`ˆn ta’i ca´c nhu ca`ˆu lu
.u lu.o.. ng la` du
.o.. c xa´c di.nh.
Tieˆ´p theo, ta t´ınh ba˘ng thoˆng du.. pho`ng c
B
ij va` chi ph´ı cho vieˆ.c caˆ´p ba˘ng thoˆng du
.
. pho`ng
GBij cho vieˆ.c hoˆ`i phu. c ma.ng khi co´ su
.
. coˆ´. Deˆ’ t´ınh toa´n ba˘ng thoˆng du
.
. pho`ng, xem H`ınh 3
sau.
Tu`. H`ınh 3 cho thaˆ´y, gia’ su.’ taˆ.p su
.
. coˆ´ bao goˆ`m tuyeˆ´n AB va` BC co´ theˆ’ co´ su
.
. coˆ´. Gia’ su
.’ ,
khi tuyeˆ´n keˆ´t noˆ´i BC bi. su
.
. coˆ´, nhu ca`ˆu lu
.u lu.o.. ng DAD va` DED se˜ du
.o.. c chuyeˆ’n tu`
. du.`o.ng
daˆ˜n ABCD va` EBCD sang du.`o.ng daˆ˜n AEFD va` EFD. Vieˆ.c chuyeˆ’n sang ca´c du
.`o.ng daˆ˜n mo´.i
cu˜ng du.o.. c thu
.
. c hieˆ.n theo thuaˆ. t toa´n du
.`o.ng nga˘´n nhaˆ´t. Trong tru.`o.ng ho.. p na`y, gia’ su
.’ nhu
ca`ˆu lu.u lu.o.. ng DAD va` DED na`˘m trong taˆ.p S (taˆ.p ca`ˆn pha’i ba’o veˆ.) th`ı, ba˘ng thoˆng du
.
.
MOˆ. T THUAˆ. T TOA´N GEN CHO THIE´ˆT KEˆ´ TOPOLOGY 65
pho`ng treˆn tuyeˆ´n keˆ´t noˆ´i EF va` FD cho su.. coˆ´ tuyeˆ´n BC du´
.t la`ˆn lu.o.. t la` C
B
EF va` C
B
FD ba`˘ng
toˆ’ng nhu ca`ˆu lu.u lu.o.. ng DAD va` DED. Ba˘ng thoˆng du
.
. pho`ng treˆn tuyeˆ´n keˆ´t noˆ´i AE la` C
B
AE
se˜ ba`˘ng nhu ca`ˆu lu.u lu.o.. ng DAD.
A
B C
D
E F
Đường hồi phục của nhu cầu lưu 
lượng ED khi tuyến kết nối BC bị đứt
Đường hồi phục của nhu cầu lưu 
lượng AD khi tuyến kết nối BC bị đứt
Hướng của nhu cầu lưu lượng AD và
ED khi mạng chưa cú sự cố
Hı`nh 3. Hu.´o.ng nhu ca`ˆu lu.u lu.o.. ng DED va` DAD thay doˆ’i khi ma.ng co´ su
.
. coˆ´
Tieˆ´p tu. c xe´t tieˆ´p tru
.`o.ng ho.. p su
.
. coˆ´ la` tuyeˆ´n keˆ´t noˆ´i AB du´
.t, khi do´ chı’ co´ nhu ca`ˆu lu.u
lu.o.. ng DAD du
.o.. c chuyeˆ’n sang du
.`o.ng daˆ˜n la` AEFD. Trong tru.`o.ng ho.. p na`y, ba˘ng thoˆng du
.
.
pho`ng se˜ du.o.. c phaˆn boˆ’ treˆn ca´c tuyeˆ´n AE, EF, FD la`ˆn lu
.o.. t la` C
B
AE , C
B
EF va` C
B
FD ba`˘ng vo´
.i
nhu ca`ˆu lu.u lu.o.. ng DAD . Tuy nhieˆn, do ba˘ng thoˆng du
.
. pho`ng da˜ du
.o.. c phaˆn boˆ’ tu`
. tru.´o.c cho
tru.`o.ng ho.. p su
.
. coˆ´ tru
.´o.c (BC du´.t) lo´.n ho.n ba˘ng thoˆng du.. pho`ng ca`ˆn cho tru
.`o.ng ho.. p na`y,
neˆn ba˘ng thoˆng du.. pho`ng khoˆng pha’i phaˆn boˆ’ theˆm. Va` nhu
. vaˆ.y, tru
.`o.ng ho.. p sau khoˆng co´
chi ph´ı cho vieˆ.c phaˆn boˆ’ theˆm ba˘ng thoˆng du
.
. pho`ng. Ngu
.o.. c la. i, trong tru
.`o.ng ho.. p su
.
. coˆ´ do`i
ho’ i ba˘ng thoˆng du.. pho`ng lo´
.n ho.n ba˘ng thoˆng du.. pho`ng da˜ caˆ´p, th`ı ba˘ng thoˆng du
.
. pho`ng se˜
ba`˘ng ba˘ng thoˆng du.. pho`ng mo´
.i va` chi ph´ı se˜ ta˘ng theˆm moˆ.t lu
.o.. ng ba`˘ng chi ph´ı cho pha`ˆn
ba˘ng thoˆng ta˘ng theˆm.
Tu`. do´ ta co´:
cBij = c
Bf
ij neˆ´u c
Bf
ij 
 c
B
ij va` c
Bf
ij  cij − c
s
ij , (6)
cBij = c
B
ij neˆ´u c
Bf
ij  c
B
ij , (7)
khi do´ chi ph´ı GBij cho vieˆ.c caˆ´p ba˘ng thoˆng hoˆ`i phu. c se˜ du
.o.. c t´ınh treˆn co
. so.’ cho ca´c tru.`o.ng
ho.. p (6) va` (7).
Thuaˆ. t toa´n t´ınh toa´n ba˘ng thoˆng va` chi ph´ı cho vieˆ.c hoˆ`i phu. c ma.ng du
.o.. c moˆ ta’ nhu
. sau:
Procedure Resilent Cost()
CBij = 0;
for N = 1 to N = Nmax do
for |F | su.. coˆ´ trong taˆ.p F do
Lu.. a cho.n ngaˆ˜u nhieˆn moˆ.t su
.
. coˆ´ Fi;
Xa´c di.nh taˆ.p ca´c du
.`o.ng keˆ´t noˆ´i Ef bi. a’nh hu
.o.’ ng bo.’ i su.. coˆ´;
Xa´c di.nh ca´c nhu ca`ˆu lu
.u lu.o.. ng Sij ca`ˆn phu. c hoˆ`i su
.’ du.ng ca´c du
.`o.ng keˆ´t noˆ´i Ef ;
Caˆ.p nhaˆ. t la. i G(V,E) treˆn co
. so.’ loa. i bo’ ca´c du
.`o.ng keˆ´t noˆ´i Ef ;
Di.nh tuyeˆ´n la. i ca´c nhu ca`ˆu lu
.o.. ng Sij treˆn G(V,E) theo du
.`o.ng nga˘´n nhaˆ´t;
Xa´c di.nh ba˘ng thoˆng hoˆ`i phu. c;
Xa´c di.nh chi ph´ı cho ba˘ng thoˆng hoˆ`i phu. c;
Tra’ la. i ca´c du
.`o.ng keˆ´t noˆ´i Ef trong G(V,E);
end
Xa´c di.nh chi ph´ı ba˘ng thoˆng hoˆ`i phu. c toˆ´i thieˆ’u;
end
66 NGUYE˜ˆN QUY´ MINH HIE`ˆN, PHA. M QUO´ˆC HUY
Qua´ tr`ınh t`ım kieˆ´m ca´c du.`o.ng daˆ˜n mo´.i se˜ loa. i bo’ ca´c du
.`o.ng keˆ´t noˆ´i ma` khoˆng co`n ba˘ng
thoˆng cho vieˆ.c hoˆ`i phu. c.
Ca´c keˆ´t qua’ t´ınh toa´n chi ph´ı ba˘ng thoˆng GSij , G
B
ij du
.o.. c su
.’ du. ng deˆ’ t´ınh mu´
.c doˆ. phu` ho
.
. p
cu’a ca´c ca´ theˆ’. Nhu. vaˆ.y, toa`n boˆ. thuaˆ. t toa´n thieˆ´t keˆ´ du
.o.. c moˆ ta’ nhu
. sau:
Procedure Algorithm Resilent Network()
Kho.’ i ta.o theˆ´ heˆ. da`ˆu P vo´
.i soˆ´ lu.o.. ng N ;
for gen =1 to maxGen do
for j = 1 to N/2 do
Lu.. a cho.n ngaˆ˜u nhieˆn ca´ theˆ’ baˆ´t ky` trong P ;
Cho.n hai ca´ theˆ’ co´ mu´
.c doˆ. phu` ho
.
. p cao nhaˆ´t trong ba ca´ theˆ’;
Lai ghe´p hai ca´ theˆ’;
end
Ta.o ca´c ca´ theˆ’ doˆ. t bieˆ´n tu`
. P vo´.i moˆ. t soˆ´ lu
.o.. ng xa´c di.nh;
Kho.’ i ta.o moˆ.t soˆ´ ca´ theˆ’ mo´
.i vo´.i soˆ´ lu.o.. ng xa´c di.nh;
T´ınh toa´n mu´.c doˆ. phu` ho
.
. p cu’a ca´c ca´ theˆ’ mo´
.i; // t´ınh ca’ chi ph´ı hoˆ`i phu. c
Lu.. a cho.n N ca´ theˆ’ mo´
.i co´ mu´.c doˆ. phu` ho
.
. p cao nhaˆ´t trong toa`n boˆ. taˆ.p ca´ theˆ’;
Du.a ra ca´c keˆ´t qua’;
End
Moˆ.t ca´ch tieˆ´p caˆ.n kha´c du
.
. a treˆn moˆ.t ca´ch tieˆ´p caˆ.n da˜ du
.o.. c de`ˆ xuaˆ´t do´ la` su
.’ du. ng thuaˆ. t
toa´n di truye`ˆn t`ım moˆ.t topology ma.ng vo´
.i chi ph´ı thaˆ´p nhaˆ´t (chu.a co´ kha’ na˘ng phu. c hoˆ`i)
trong vieˆ.c da’m ba’o truye`ˆn ta’ i taˆ.p D ca´c nhu ca`ˆu lu
.u lu.o.. ng. Mu´
.c doˆ. phu` ho
.
. p (fitness) trong
thuaˆ. t toa´n di truye`ˆn chı’ du
.o.. c t´ınh cho giai doa.n da`ˆu. O
.’ giai doa.n sau se˜ di.nh tuyeˆ´n la. i ca´c
nhu ca`ˆu lu.u lu.o.. ng ca`ˆn phu. c hoˆ`i va` chi ph´ı cuoˆ´i cu`ng la` toˆ’ng cu’a hai giai doa.n. Vieˆ.c so sa´nh
hai ca´ch tieˆ´p caˆ.n na`y se˜ du
.o.. c theˆ’ hieˆ.n qua moˆ.t soˆ´ keˆ´t qua’ t´ınh toa´n du
.´o.i daˆy.
3. MOˆ. T SOˆ´ KE´ˆT QUA
’ TI´NH TOA´N THU
.
. C NGHIEˆ.M
Moˆ.t soˆ´ keˆ´t qua’ thu du
.o.. c trong qua´ tr`ınh thu
.
. c hieˆ.n hai phu
.o.ng pha´p tieˆ´p caˆ.n treˆn du
.o.. c
du.a ra o.’ daˆy. Taˆ´t ca’ ca´c keˆ´t qua’ du.o.. c thu
.
. c hieˆ.n treˆn co
. so.’ la˘.p la. i moˆ. t soˆ´ la`ˆn. Deˆ’ so sa´nh
t´ınh hieˆ.u qua’ giu˜
.a vieˆ.c su
.’ du.ng chi ph´ı thieˆ´t laˆ.p ma.ng chu
.a co´ du.. pho`ng va` chi ph´ı toˆ’ng coˆ.ng
(goˆ`m ca’ chi ph´ı du.. pho`ng) deˆ’ t´ınh mu´
.c doˆ. phu` ho
.
. p cho thuaˆ. t toa´n gen, moˆ.t ma.ng 20 nu´t
du.o.. c su
.’ du.ng. Ca´c ma traˆ.n nhu ca`ˆu lu
.u lu.o.. ng, dung lu
.o.. ng ca´c du
.`o.ng keˆ´t noˆ´i, chi ph´ı dung
lu.o.. ng du
.`o.ng keˆ´t noˆ´i,...du.o.. c sinh ngaˆ˜u nhieˆn bo
.’ i chu.o.ng tr`ınh. Ca´c nhu ca`ˆu lu.u lu.o.. ng du
.o.. c
quy doˆ’i co´ gia´ tri. tu`
. 0.5Mbps deˆ´n 2.5Mbps; dung lu.o.. ng du
.`o.ng keˆ´t noˆ´i co´ gia´ tri. tu`
. 3Mbps
deˆ´n 5Mbps; chi ph´ı cho moˆ.t do
.n vi. dung lu
.o.. ng keˆnh keˆ´t noˆ´i tu`
. 5000 deˆ´n 35000 cho 1Kbps;
k´ıch thu.´o.c daˆn soˆ´ du.o.. c da˘. t vo´
.i gia´ tri. 25, soˆ´ theˆ´ heˆ. la` 50, ty’ leˆ. lai ghe´p la` 45%, ty’ leˆ. doˆ. t bieˆ´n
la` 30%, ty’ leˆ. ta.o ca´ theˆ’ mo´
.i la` 55%.
Treˆn ca´c H`ınh 3a va` H`ınh 3b tr`ınh ba`y ca´c keˆ´t qua’ t´ınh toa´n. Chi ph´ı G1 va` G1′ u´.ng vo´.i
tru.`o.ng ho.. p thieˆ´t keˆ´ topology ma.ng vo´
.i mu´.c doˆ. phu` ho
.
. p trong thuaˆ.t toa´n gen du
.o.. c du
.
. a treˆn
co. so.’ chi ph´ı G1 ma` khoˆng t´ınh deˆ´n G1′. Ngu.o.. c la. i, chi ph´ı G2 va` G2
′ la` cho tru.`o.ng ho.. p
mu´.c doˆ. phu` ho
.
. p du
.
. a treˆn chi ph´ı toˆ’ng coˆ.ng G2 +G2
′. Ca´c chi ph´ı G1 va` G2 la` chi ph´ı thieˆ´t
laˆ.p ma.ng chu
.a co´ du.. pho`ng. Ca´c chi ph´ı G1
′ va` G2′ la` ca´c chi ph´ı cho vieˆ.c hoˆ`i phu. c ma.ng.
MOˆ. T THUAˆ. T TOA´N GEN CHO THIE´ˆT KEˆ´ TOPOLOGY 67
0
500000000
1000000000
1500000000
2000000000
2500000000
3000000000
3500000000
0 10 20 30 40 50 60
Thế hệ
C
h
i 
p
h
ớ
G1
G2
G1'
G2'
G1 + G1'
G2 + G2'
0
500000000
1000000000
1500000000
2000000000
2500000000
3000000000
3500000000
0 10 20 30 40 50 60
Thế hệ
C
h
i p
h
ớ
G1
G2
G1'
G2'
G1 + G1'
G2 + G2'
C
h
i 
p
h
ớ
C
h
i p
h
ớ
Hı`nh 3a. Hı`nh 3b.
Hoˆ`i phu. c du
.`o.ng treˆn moˆ.t du
.`o.ng hoˆ`i phu. c Hoˆ`i phu. c du
.`o.ng treˆn nhie`ˆu du.`o.ng hoˆ`i phu. c
Ca´c keˆ´t qua’ t´ınh toa´n cho hai tru.`o.ng ho.. p hoˆ`i phu. c du
.`o.ng cho thaˆ´y ra`˘ng vieˆ.c su
.’ du.ng
chi ph´ı toˆ’ng coˆ.ng la`m co
. so.’ t´ınh mu´.c doˆ. phu` ho
.
. p cu’a thuaˆ. t toa´n gen se˜ cho keˆ´t qua’ toˆ´t ho
.n.
Treˆn co. so.’ na`y, ca´c t´ınh toa´n tieˆ´p theo du.o.. c thu
.
. c hieˆ.n nha`˘m so sa´nh ba phu
.o.ng thu´.c: hoˆ`i
phu. c du
.`o.ng treˆn moˆ.t du
.`o.ng hoˆ`i phu. c (non-bifurcation) - phu
.o.ng thu´.c 1, hoˆ`i phu. c du
.`o.ng
treˆn nhie`ˆu du.`o.ng hoˆ`i phu. c (bifurcation) - phu
.o.ng thu´.c 2 va` phu. c hoˆ`i la˘.p la` phu
.o.ng thu´.c
du.o.. c de`ˆ xuaˆ´t o
.’ daˆy du.. a treˆn co
. so.’ la˘.p la. i moˆ. t soˆ´ la`ˆn qua´ tr`ınh phu. c hoˆ`i du
.`o.ng treˆn nhie`ˆu
du.`o.ng hoˆ`i phu. c - phu
.o.ng thu´.c 3.
2600000000
2650000000
2700000000
2750000000
2800000000
2850000000
2900000000
0 20 40 60
T hế hệ
Phương thức 1
Phương thức 2
Phương thức 3
Phương thức MCR
4600000000
4700000000
4800000000
4900000000
5000000000
5100000000
5200000000
0 20 40 60
T hế hệ
Phương thức 1
Phương thức 2
Phương thức 3
Phương thức MCR
7600000000
7800000000
8000000000
8200000000
8400000000
8600000000
8800000000
9000000000
0 20 40 60
T hế hệ
Phương thức 1
Phương thức 2
Phương thức 3
Phương thức MCR
Hỡnh 4c. 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
Hỡnh 4b. Trường hợp nhu cầu 
lưu lượng cần hồi phục chiếm 
40% lưu lượng toàn bộ mạng
Hỡnh 4a. Trường hợp nhu cầu 
lưu lượng cần hồi phục chiếm 
12% lưu lượng toàn bộ mạng
C
h
i 
ph
í
C
h
i 
ph
í
C
h
i 
ph
í
C
h
i 
ph
í
C
h
i 
ph
í
C
h
i 
ph
í
Trong [12] du.a ra thuaˆ. t toa´n hoˆ`i phu. c MCR (Minimum Cost Restoration) vo´
.i na˘m bu.´o.c
thu.. c hieˆ.n. Hai bu
.´o.c da`ˆu ve`ˆ noˆ. i dung tu
.o.ng tu.. nhu
. phu.o.ng thu´.c 1 tr`ınh ba`y o.’ treˆn. Ba bu.´o.c
sau thu.. c chaˆ´t la` qua´ tr`ınh toˆ´i u
.u tieˆ´p du.. a treˆn qua´ tr`ınh t`ım kieˆ´m cu. c boˆ. tu`
. keˆ´t qua’ cu’a hai
bu.´o.c da`ˆu. Phu.o.ng thu´.c hoˆ`i phu. c theo thuaˆ.t toa´n MCR du
.o.. c xaˆy du
.
. ng nha`˘m la`m co
. so.’ so
sa´nh vo´.i thuaˆ.t toa´n hoˆ`i phu. c la˘.p du
.o.. c de`ˆ xuaˆ´t ta. i daˆy. Treˆn H`ınh 4a, 4b va` 4c theˆ’ hieˆ.n ca´c
keˆ´t qua’ du.o.. c thu
.
. c hieˆ.n trong die`ˆu kieˆ.n kha´c nhau ve`ˆ yeˆu ca`ˆu mu´
.c doˆ. phu. c hoˆ`i ta. i ca´c mu´
.c
doˆ. 12%, 40% va` 60%.
Keˆ´t qua’ cho thaˆ´y vieˆ.c thu
.
. c hieˆ.n phu. c hoˆ`i theo phu
.o.ng thu´.c la˘.p cho keˆ´t qua’ toˆ´t nhaˆ´t.
68 NGUYE˜ˆN QUY´ MINH HIE`ˆN, PHA. M QUO´ˆC HUY
Nhu˜.ng tru.`o.ng ho.. p mu´
.c doˆ. yeˆu ca`ˆu phu. c hoˆ`i cu’a ma.ng la` cao tu`
. khoa’ng 40% tro.’ leˆn, ca´c
phu.o.ng thu´.c hoˆ`i phu. c 2 va` 3 dang xem xe´t cho keˆ´t qua’ toˆ´t ho
.n doˆi chu´t so vo´.i thuaˆ. t toa´n
MCR o.’ [12]. Nguyeˆn nhaˆn la` do trong nhu˜.ng tru.`o.ng ho.. p ma` yeˆu ca`ˆu mu´
.c doˆ. hoˆ`i phu. c cao,
vieˆ.c su
.’ du.ng phu
.o.ng pha´p hoˆ`i phu. c nhie`ˆu du
.`o.ng cho keˆ´t qua’ toˆ´t ho.n phu.o.ng pha´p hoˆ`i phu. c
khoˆng treˆn nhie`ˆu du.`o.ng ma` thuaˆ. t toa´n MCR a´p du.ng. Vo´
.i tru.`o.ng ho.. p mu´
.c doˆ. nhu ca`ˆu hoˆ`i
phu. c thaˆ´p khoa’ng treˆn du
.´o.i 10% hoa˘.c tu
.o.ng du.o.ng vo´.i ca´c tru.`o.ng ho.. p ma` dung lu
.o.. ng ca´c
du.`o.ng keˆ´t noˆ´i co`n du. thu`.a nhie`ˆu khi so sa´nh tu.o.ng doˆ´i vo´.i nhu ca`ˆu ca`ˆn hoˆ`i phu. c, th`ı thuaˆ. t
toa´n MCR cho keˆ´t qua’ troˆ. i ho
.n doˆi chu´t (H`ınh 4a). Keˆ´t qua’ na`y do khi ma.ng co`n du
. thu`.a
ba˘ng thoˆng, phu.o.ng pha´p hoˆ`i phu. c treˆn nhie`ˆu du
.`o.ng ma` phu.o.ng thu´.c 2 va` 3 a´p du.ng khoˆng
vu.o.. t troˆ. i so vo´
.i phu.o.ng thu´.c MCR a´p du.ng. Ma˘.t kha´c, ve`ˆ ba’n chaˆ´t, thuaˆ. t toa´n MCR cu˜ng
a´p du.ng moˆ.t qua´ tr`ınh t`ım kieˆ´m toˆ´i u
.u deˆ’ ca’i tieˆ´n chaˆ´t lu.o.. ng cu’a gia’ i pha´p da.t du
.o.. c. Tuy
nhieˆn, cu˜ng ca`ˆn lu.u y´ ra`˘ng, kha´c vo´.i thuaˆ.t toa´n de`ˆ xuaˆ´t o
.’ daˆy thu.. c hieˆ.n theo bieˆn da thu´
.c
tho`.i gian (polynomial-time bound), thuaˆ. t toa´n MCR la` thuaˆ. t toa´n thu
.
. c hieˆ.n khoˆng theo bieˆn
da thu´.c tho`.i gian. Do vaˆ.y tho`
.i gian chi ph´ı cho vieˆ.c thu
.
. c hieˆ.n thuaˆ. t toa´n MCR raˆ´t lo´
.n, gaˆ´p
nhie`ˆu la`ˆn thuaˆ. t toa´n de`ˆ xuaˆ´t o
.’ daˆy.
Go.i chi ph´ı cho vieˆ.c thieˆ´t keˆ´ topology ma.ng co´ kha’ na˘ng hoˆ`i phu. c cho tru
.`o.ng ho.. p 1 la`
C1, tu.o.ng tu.. cho phu
.o.ng thu´.c 2 va` 3 la` C2, C3. Trong H`ınh 5 du.´o.i daˆy, tru. c tung du
.o.. c
t´ınh tu`. ty’ soˆ´ cu’a (C1 − C2)/C1 va` (C1 − C3)/C1 tu.o.ng u´.ng vo´.i phu.o.ng thu´.c 2 va` 3 nha`˘m
so sa´nh mu´.c doˆ. t´ıch kieˆ.m chi ph´ı cu’a ca´c phu
.o.ng thu´.c hoˆ`i phu. c ta. i ca´c mu´
.c doˆ. yeˆu ca`ˆu hoˆ`i
phu. c kha´c nhau. Tu`
. H`ınh 5 co´ theˆ’ thaˆ´y ro˜ vieˆ.c su
.’ du.ng phu
.o.ng thu´.c la˘.p - phu
.o.ng thu´.c 3
co´ mu´.c doˆ. t´ıch kieˆ.m chi ph´ı ho
.n ha˘’ n phu.o.ng thu´.c 2 khi mu´.c doˆ. yeˆu ca`ˆu hoˆ`i phu. c ta˘ng tu`
.
khoa’ng 40% tro.’ leˆn. Phu.o.ng thu´.c hoˆ`i phu. c treˆn nhie`ˆu du
.`o.ng - phu.o.ng thu´.c 2 co´ nhie`ˆu hieˆ.u
qua’ ho.n so vo´.i phu.o.ng thu´.c hoˆ`i phu. c treˆn moˆ.t du
.`o.ng - phu.o.ng thu´.c 1, tu`y thuoˆ.c va`o tu`
.ng
ma.ng, mu´
.c doˆ. hieˆ.u qua’ ta˘ng da`ˆn theo mu´
.c doˆ. ta˘ng cu’a nhu ca`ˆu lu
.u lu.o.. ng ca`ˆn hoˆ`i phu. c va`
da.t deˆ´n moˆ.t gia´ tri. na`o do´. Sau do´, mu´
.c doˆ. hieˆ.u qua’ la. i gia’m khi ta˘ng mu´
.c doˆ. nhu ca`ˆu lu
.u
lu.o.. ng ca`ˆn hoˆ`i phu. c. Die`ˆu na`y la` do khi ta˘ng qua´ mu´
.c doˆ. nhu ca`ˆu lu
.u lu.o.. ng ca`ˆn phu. c hoˆ`i,
ca`ˆn thieˆ´t laˆ.p ca´c tuyeˆ´n mo´
.i, doˆ´i vo´.i ca´c phu.o.ng thu´.c de`ˆu khoˆng t´ıch kieˆ.m du
.o.. c chi ph´ı.
0
1
2
3
4
5
6
12 25 40 60
Mức độ nhu cầu l−u l−ợng
cần phục hồi (%)
Ph−ơng thức 2
Ph−ơng thức 3
Hı`nh 5. Cheˆnh leˆ.ch chi ph´ı thieˆ´t keˆ´ khi su
.’ du. ng phu
.o.ng thu´.c hoˆ`i phu. c 1 vo´
.i 2 va` 3
Vo´.i ca´c keˆ´t qua’ t´ınh toa´n na`y, chu´ng toˆi thu.. c hieˆ.n thieˆ´t keˆ´ topology ma.ng co´ kha’ na˘ng
hoˆ`i phu. c cho tru
.`o.ng ho.. p ma.ng 35 nu´t va` ma.ng 50 nu´t vo´
.i mu´.c doˆ. nhu ca`ˆu lu
.u lu.o.. ng ca`ˆn
hoˆ`i phu. c la` 12% cho hai phu
.o.ng thu´.c: phu. c hoˆ`i treˆn nhie`ˆu du
.`o.ng va` phu. c hoˆ`i la˘.p. Ca´c keˆ´t
MOˆ. T THUAˆ. T TOA´N GEN CHO THIE´ˆT KEˆ´ TOPOLOGY 69
qua’ du.o.. c theˆ’ hieˆ.n ta. i H`ınh 6a va` 6b du
.´o.i daˆy.
Tu`. keˆ´t qua’ t´ınh toa´n so. boˆ. cho thaˆ´y, trong moˆ.t soˆ´ tru
.`o.ng ho.. p thu
.
. c nghieˆ.m nhu
. treˆn,
phu.o.ng pha´p hoˆ`i phu. c la˘.p cho keˆ´t qua’ kha’ quan.
7500000000
7550000000
7600000000
7650000000
7700000000
7750000000
0 20 40 60
Phương thức 2
Phương thức 3
14980000000
15000000000
15020000000
15040000000
15060000000
15080000000
15100000000
15120000000
0 20 40 60
Phương thức 2
Phương thức 3
Hỡnh 6b Trường hợp mạng lưới đầy đủ 50 nỳtHỡnh 6a Trường hợp mạng lưới đầy đủ 35 nỳt
4. KE´ˆT LUAˆ. N
Qua ca´c keˆ´t qua’ t´ınh toa´n o.’ treˆn co´ theˆ’ thaˆ´y, thuaˆ. t toa´n hoˆ`i phu. c la˘.p du
.o.. c de`ˆ xuaˆ´t o
.’
daˆy cho keˆ´t qua’ t´ınh toa´n toˆ´t ho.n so vo´.i moˆ. t soˆ´ thuaˆ. t toa´n kha´c da˜ du
.o.. c de`ˆ caˆ.p tru
.´o.c daˆy.
Mu´.c doˆ. t´ıch kieˆ.m chi ph´ı cu’a thuaˆ. t toa´n ca`ng lo´
.n khi mu´.c doˆ. yeˆu ca`ˆu phu. c hoˆ`i lu
.u lu.o.. ng
ma.ng ca`ng lo´
.n. Ma˘.t kha´c, qua´ tr`ınh thieˆ´t keˆ´ ma.ng vo´
.i vieˆ.c keˆ´t ho
.
. p giu˜
.a qua´ tr`ınh thieˆ´t keˆ´
ma.ng trong die`ˆu kieˆ.n b`ınh thu
.`o.ng va` qua´ tr`ınh t´ınh toa´n phaˆn boˆ’ ba˘ng thoˆng hoˆ`i phu. c da.t
keˆ´t qua’ toˆ´t ho.n vieˆ.c phaˆn ta´ch hai qua´ tr`ınh t´ınh toa´n thieˆ´t keˆ´ rieˆng bieˆ.t. Qua´ tr`ınh t´ınh
toa´n cu˜ng cho thaˆ´y, vieˆ.c su
.’ du.ng ca´c phu
.o.ng pha´p hoˆ`i phu. c du
.`o.ng treˆn nhie`ˆu du.`o.ng hoˆ`i
phu. c cho phe´p su
.’ du.ng ba˘ng thoˆng hieˆ.u qua’ ho
.n, t´ıch kieˆ.m chi ph´ı, kha’ na˘ng thieˆ´t keˆ´ ma.ng
linh hoa.t ho
.n. Thuaˆ. t toa´n thieˆ´t keˆ´ topology ma.ng hoˆ`i phu. c nhu
. treˆn co´ kha’ na˘ng thieˆ´t keˆ´
cho ca´c ma.ng lu
.´o.i da`ˆy du’, dung lu.o.. ng hu˜
.u ha.n vo´
.i soˆ´ lu.o.. ng nu´t lo´
.n, da´p u´.ng nhu ca`ˆu thieˆ´t
keˆ´ ca´c ma.ng lo´
.n trong thu.. c teˆ´.
Gio´.i thieˆ. u chu
.o.ng tr`ınh:
Thuaˆ. t toa´n du
.o.. c thu
.
. c hieˆ.n qua chu
.o.ng tr`ınh xaˆy du.. ng treˆn ngoˆn ngu˜
. laˆ.p laˆ.p tr`ınh C
++.
Chu.o.ng tr`ınh cho phe´p nhaˆ.p hoa˘.c tu
.
. sinh ca´c du˜
. lieˆ.u da`ˆu va`o nhu
. ma traˆ.n nhu ca`ˆu, ma traˆ.n
keˆ´t noˆ´i, dung lu.o.. ng du
.`o.ng keˆ´t noˆ´i, gia´ do.n vi. cho ca´c du
.`o.ng keˆ´t noˆ´i, taˆ.p ca´c du
.`o.ng keˆ´t noˆ´i
co´ theˆ’ bi. su
.
. coˆ´, taˆ.p ca´c nhu ca`ˆu ca`ˆn ba’o veˆ.. Ca´c tu`y cho.n kha´c du
.o.. c hoˆ˜ tro
.
. nha`˘m ta˘ng kha’
na˘ng t`ım kieˆ´m trong pha`ˆn thuaˆ.t toa´n gen cu’a chu
.o.ng tr`ınh nhu. da˘.t k´ıch thu
.´o.c daˆn soˆ´, ty’ leˆ.
lai ghe´p, ty’ leˆ. doˆ. t bieˆ´n, ty’ leˆ. ta.o ca´ theˆ’ mo´
.i.
TA`I LIEˆ. U THAM KHA
’O
[1] L. Berry, B. Murtagh, G. McMahon, S. Sugden, and M. Randall, Fast Network Design
for Telecommunications, 1999.
70 NGUYE˜ˆN QUY´ MINH HIE`ˆN, PHA. M QUO´ˆC HUY
[2] G. Li, D. Wang, C. Kalmanek, and R. Doverspike, Efficient distributed restoration path
selection for shared mesh restoration, IEEE/ACM Transactions on Networking 11 (5)
(October 2003).
[3] D. E. Golberg, Genetic Algorithms in Search, Optimization, and Machine Learning,
Addison-Wesley, 1989.
[4] H. Sakauchi, Y. Nishimura, and S. Hasegawa, A self-healing network with an economical
spare-channel assignment, Proceedings of IEEE GLOBE-COM, San Diego, USA (Decem-
ber 1990).
[5] R. Iraschko, M. MacGregor, and W. Grover, Optimal capacity placement for path restora-
tion in mesh survivable networks, Proceedings of IEEE ICC, Dallas, USA (June 1996).
[6] K. Murakami and H. Kim, Joint optimization of capacity and flow assignment for self-
healing ATM networks, Proceedings of IEEE ICC, Seattle, USA (June 1995).
[7] A. Konak, and A. Smith, A hybrid genetic algorithm approach for backbone design of
communication networks, Conf. Proc. CEC 99, IEEE press, Piscataway, N.J., S. (1999)
1817—1823.
[8] M. Kodialam, and T.V. Lakshman, Dynamic routing of restorable bandwidth guaranteed
tunnels using aggregated network resource usage information, IEEE/ACM Transactions
on Networking 11 (3)(June 2003).
[9] C.C. Palmer, “An Approach to a Problem in Network Design Using Genetic Algorithms”
PhD Thesis, Polytechnic University, Computer Scientic Departement, Brookly, NewYork,
1994.
[10] M. Herzberg, S. Bye, and A. Utano, The hop-limit approach for spare-capacity assignment
in survivable networks, IEEE/ACM Transactions on Networking 3 (6) (1995) 775—784.
[11] G.R. Raidl, and B.A. Julstrom, Edge-sets: An effective evolutionary coding of spanning
trees, IEEE Transactions on Evolutionary Computation 7 (3) (2003) 225—239.
[12] Y. Xiong and L. Mason, Restoration strategies and spare capacity requirements in self-
healing ATM networks, IEEE/ACM Transactions on Networking 7 (1) (1999) 98—110.
Nhaˆ. n ba`i nga`y 5 - 9 - 2006
Nhaˆ. n la. i sau su
.’ a nga`y 15 - 1 -2007