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

Nội dung text: Một thuật toán gen cho thiết kế Topology mạng có khả năng hồi phục

1. Ta. p ch´ıTin ho. c v`a Diˆe` u khiˆe’n ho. c, T.23, S.1 (2007), 59—70 ´ ´ MOˆ. T THUAˆ. T TOAN´ GEN CHO THIEˆTKEˆ TOPOLOGY ’ ` MA. NG CO´ KHA NANG˘ HOˆI PHU. C ˜ ` ´ NGUYEˆN QUY´ MINH HIEˆN, PHA. M QUOˆ C HUY . Viˆe. n Khoa ho. c K˜ythuˆa. t Buu diˆe.n Abstract. Today, telecommunication technologies and services are deploying rapidly in NGN (Next Generation Network) networks. Quality of Service (QoS) problems in NGN networks are addressed in network designing, deploying, maintaining phases. In network designing phase, one of QoS problems is designing survivable networks to assure that services are not disrupted when a failure happens. On an ATM, MPLS, GMPLS based-on network techonologies, there are many approaches for designing survivable networks. This paper introduces a genetic algorithm for topological design of survivable networks by a repetitively-restorable method. . T´om t˘a´t. Hiˆe.n nay, v´oi viˆe.c triˆe’n khai cˆong nghˆe. ma.ng NGN, c´ac di.ch vu. thˆong tin truyˆe` n thˆong . . . . dang duo. c ph´at triˆe’n rˆa´t nhanh ch´ong v´oi nhiˆe` u loa.i h`ınh di.ch vu. . Mˆo.t trong nh˜ung vˆa´n dˆe` d˘a.t ra . . d´ol`acˆa`n pha’i thiˆe´t kˆe´, triˆe’n khai ma.ng c´okha’ n˘ang da’m ba’o chˆa´t luo. ng di.ch vu. cho c´ac loa.i di.ch . . . . vu. triˆe’n khai trˆen d´o. Mˆo.t trong nh˜ung yˆeu cˆa`u vˆe` chˆa´t luo. ng di.ch vu. d˘a.t ra dˆo´i v´oi viˆe.c thiˆe´t kˆe´ . . . . ma.ng, d´ol`ama.ng pha’i c´okha’ n˘ang hˆo`i phu. c dˆe’ da’m ba’o cung cˆa´p di.ch vu. v´oi chˆa´t luo. ng nhu d˜a . . . . . . . . cam kˆe´t v´oi kh´ach h`ang ngay trong nh˜ung tru`ong ho. p ma.ng c´osu. cˆo´. Trˆen co so’ c´ac cˆong nghˆe. . . ma.ng nhu ATM, MPLS, GMPLS, c´onhiˆe` u c´ach th´uc tiˆe´p cˆa.n dˆe’ da’m ba’o kha’ n˘ang hˆo`i phu. c cu’a . . . ma.ng. B`ai b´ao n`ay gi´oi thiˆe.u mˆo.t thuˆa.t to´an thiˆe´t kˆe´ topology v´oi kha’ n˘ang hˆo`i phu. c du. a trˆen . . . . phuong ph´ap hˆo`i phu. c l˘a.p trˆen nhiˆe` u du`ong hˆo`i phu. c. . 1. GIO´ I THIEˆ. U . . . Trˆen ma.ng trong qu´atr`ınh khai th´ac c´othˆe’ xuˆa´t hiˆe.n nh˜ung su. cˆo´ gˆay tro’ nga.i cho qu´a . . . tr`ınh cung cˆa´p di.ch vu. . Nh˜ung su. cˆo´ c´othˆe’ l`a d´ut c´ap, mˆa´t nguˆo`n diˆe.n, ho’ng h´oc thiˆe´t bi., . . . . n˘a`m ngo`ai su. diˆe` u khiˆe’n cu’a ngu`oi vˆa.n h`anh. Mˆo.t sˆo´ su. cˆo´ kh´ac n˘a`m trong diˆe` u h`anh cu’a . . . ngu`oi d´ol`akho’ i dˆo.ng, cˆa´u h`ınh la.i hˆe. thˆo´ng, nˆang cˆa´p hˆe. thˆo´ng, mˆa´t diˆe` u khiˆe’n hˆe. thˆo´ng. . . . . . . . Nh˜ung su. cˆo´ nhu vˆa.y c´othˆe’ quy th`anh hai nh´om: su. cˆo´ tuyˆe´n v`asu. cˆo´ n´ut. Nh˜ung su. cˆo´ . . tuyˆe´n xa’y ra khi su. cˆo´ dˆa˜n dˆe´n tuyˆe´n l`am viˆe.c khˆong ch´ınh x´ac ho˘a.c ng`ung c´ac luˆo`ng thˆong . . . . tin trˆen tuyˆe´n. Nh˜ung su. cˆo´ n´ut xuˆa´t hiˆe.n gˆay nˆen su. ng`ung trˆe. thˆong tin trˆen n´ut d´ov`a . . . cho c´ac tuyˆe´n kˆe´t nˆo´i dˆe´n n´ut n`ay. Thu. c tˆe´ trˆen ma.ng c´othˆe’ xuˆa´t hiˆe.n dˆo`ng th`oi nhiˆe` u su. . . cˆo´, tuy nhiˆen, x´ac suˆa´t xuˆa´t hiˆe.n dˆo`ng th`oi hai su. cˆo´ trˆen ma.ng l`arˆa´t thˆa´p. Ch´ınh v`ıvˆa.y . . . . phˆa`n l´on c´ac nghiˆen c´uu tˆa.p trung v`ao viˆe.c gia’i quyˆe´t su. cˆo´ theo gia’ thiˆe´t ta.i mˆo˜i th`oi diˆe’m . chı’ c´omˆo.t su. cˆo´. . . . . . Mˆo.t chiˆe´n luo. c hˆo`i phu. c c´othˆe’ triˆe’n khai o’ c´ac l´op kh´ac nhau theo quan diˆe’m giao th´uc . . . . ma.ng OSI nhu hˆo`i phu. c ta.i l´op vˆa.t l´y, kˆe´t nˆo´i, ma.ng ho˘a.c dˆo`ng th`oi trˆen nhiˆe` u l´op. Ta.i mˆo˜i . . . . . . . . l´op, c´ac chiˆe´n luo. c hˆo`i phu. c c´onh˜ung d˘a.c t´ınh kh´ac nhau. V´oi l´op vˆa.t l´y, c´ac chiˆe´n luo. c
2. ˜ ` ´ 60 NGUYEˆN QUY´ MINH HIEˆN, PHA. M QUOˆ C HUY . . . . hˆo`i phu. c c´oth`oi gian hˆo`i phu. c nhanh nhˆa´t khoa’ng 50ms. C´ac chiˆe´n luo. c hˆo`i phu. c ta.i l´op . . . . . kˆe´t nˆo´i thu`ong d`ung cho c´ac ma.ng hu´ong kˆe´t nˆo´i nhu ATM v`aMPLS. C´ac kiˆe´n tr´uc ma.ng . . chuyˆe’n ma.ch nh˜an thiˆe´t lˆa.p du`ong dˆa˜n chuyˆe’n ma. ch nh˜an LSP (Label Switch Path) chuyˆe’n . . . . . . . tiˆe´p luu luo. ng gi˜ua n´ut nguˆo`n v`a d´ıch. Mu. c tiˆeu cu’a c´ac chiˆe´n luo. c ta.i l´op n`ay l`ahˆo`i phu. c . . . . . . . . . . phˆa`n luu luo. ng trˆen c´ac LSP m`abi. a’nh huo’ ng bo’ i su. cˆo´. C´ac chiˆe´n luo. c hˆo`i phu. c ta.i l´op . . kˆe´t nˆo´i c´onhiˆe` u diˆe’m linh hoa.t nhu khˆong phˆan nho’ ma.ng th`anh c´ac phˆa`n nho’ hon ho˘a.c khˆong pha’i gia’ thiˆe´t r˘a`ng topology cu’a ma.ng pha’i c´ocˆa´u tr´uc. C´ac tuyˆe´n v`ac´ac n´ut c´othˆe’ . . . . . . . tham gia trong chiˆe´n luo. c hˆo`i phu. c. Su’ du. ng c´ac thuˆa.t to´an hoa.ch di.nh tru´oc, thu`ong d`ung . . . . . . dˆe’ x´ac di.nh c´ach th´uc tˆo´t nhˆa´t di.nh tuyˆe´n luu luo. ng khi c´osu. cˆo´ xa’y ra, v´ıdu. nhu trong . . . . . . . . . . . chiˆe´n luo. c hˆo`i phu. c du`ong, s˜esu’ du. ng mˆo.t du`ong kh´ac dˆe’ chuyˆe’n luu luo. ng khi xa’y ra su. . . . . . . . . . cˆo´ ma.ng. M˘a.c d`uth`oi gian cho viˆe.c di.nh tuyˆe´n la.i luu luo. ng trong tru`ong ho. p th´u nhˆa´t l´on . . . . . . . . . hon tru`ong ho. p th´u hai, nhung c´ac phuong ph´ap trong [2, 5, 8, 12] chı’ ra r˘a`ng hiˆe.u suˆa´t su’ . . . . . du. ng b˘ang thˆong hˆo`i phu. c ta.i l´op kˆe´t nˆo´i l´on hon d´ang kˆe’ so v´oi khi hˆo`i phu. c ta.i l´op vˆa.t l´y. . . . . . . . . . C´ac chiˆe´n luo. c hˆo`i phu. c l´op kˆe´t nˆo´i duo. c du. a trˆen c´ac kiˆe´n tr´uc ma.ng hu´ong kˆe´t nˆo´i nhu . MPLS, ATM ho˘a.c GMPLS nhu d˜achı’ ra trong nhiˆe` u t`ai liˆe.u. Lˆa´y v´ıdu. cho ma.ng MPLS, . . . . . . m˘a.c d`uc´othˆe’ su’ du. ng c´ac ma.ng kh´ac, chiˆe´n luo. c hˆo`i phu. c l´op kˆe´t nˆo´i d´ol`achiˆe´n luo. c . . . . . . . hˆo`i phu. c du`ong dˆa˜n MPLS. Da.ng don gia’n nhˆa´t cu’a hˆo`i phu. c du`ong dˆa˜n l`achiˆe´n luo. c 1+1 . . . . . chuyˆe’n ma. ch du`ong dˆa˜n tu. dˆo. ng APS (Automatic Path Switching). Trong chiˆe´n luo. c n`ay, . . . . . . hai du`ong dˆa˜n v´oi c`ung b˘ang thˆong duo. c thiˆe´t lˆa.p gi˜ua diˆe’m nguˆo`n v`a diˆe’m d´ıch, tuy nhiˆen . . . . . . . trong qu´atr`ınh hoa.t dˆo.ng, chı’ mˆo.t du`ong di.ch vu. l`achuyˆe’n ta’i luu luo. ng v`a du`ong c`on la.i l`a . . . . . . . . . . . du`ong du. ph`ong (m˘a.c d`u du`ong du. ph`ong vˆa˜n chuyˆe’n ta’i ba’n sao cu’a luu luo. ng cu’a du`ong . . . . . di.ch vu. ). Du`ong du. ph`ong ho`an to`an c´ach ly kho’i du`ong di.ch vu. , khi c´omˆo.t tuyˆe´n n`ao d´o . . . . . . . . . . . trˆen du`ong di.ch vu. c´osu. cˆo´, du`ong du. ph`ong s˜e duo. c su’ du. ng thay thˆe´. Mˆo.t chiˆe´n luo. c hˆo`i . . . . . . phu. c kh´ac l`achiˆe´n luo. c 1:1 APS c˜ung su’ du. ng hai du`ong dˆa˜n c´ach ly nhau ho`an to`an nhung . . . . . . . . . . . kh´ac v´oi chiˆe´n luo. c 1+1 APS d´ol`achı’ du`ong di.ch vu. chuyˆe’n ta’i luu luo. ng, du`ong du. ph`ong . . . . khˆong chuyˆe’n ta’i. Chiˆe´n luo. c hˆo`i phu. c 1:1 APS mˆa´t nhiˆe` u th`oi gian dˆe’ hˆo`i phu. c hon chiˆe´n . . . . . . . . luo. c hˆo`i phu. c 1+1 APS. Tuy nhiˆen, chiˆe´n luo. c hˆo`i phu. c n`ay la.i c´ouu diˆe’m l`a du`ong du. . . . . . ph`ong khˆong chuyˆe’n ta’i luu luo. ng do d´otrong diˆe` u kiˆe.n ma.ng hoa.t dˆo.ng b`ınh thu`ong, b˘ang . . thˆong khˆong duo. c tˆa.n du. ng, do vˆa.y l`am gia’m yˆeu cˆa`u vˆe` b˘ang thˆong. . . . . . Mˆo.t chiˆe´n luo. c hˆo`i phu. c kh´ac l`ahˆo`i phu. c theo tuyˆe´n kˆe´t nˆo´i. Khˆong nhu c´ac chiˆe´n luo. c . . . . . . hˆo`i phu. c 1+1 APS v`a 1:1 APS, hˆo`i phu. c trˆen co so’ du`ong dˆa˜n ([2, 4, 5, 8, 12]), c´ac chiˆe´n luo. c . . . . . . . n`ay du. a trˆen co so’ t`ung tuyˆe´n kˆe´t nˆo´i nhu trong [10, 12]. Xem x´et v´ıdu. du´oi dˆay. uuu B C oơ u A D uuu oơ uu E F uuu . . H`ınh 1. Hˆo`i phu. c theo tuyˆe´n v`a du`ong . . . . . . . . . . . . . Trong tru`ong ho. p ma.ng b`ınh thu`ong, luu luo. ng gi˜ua A v`aD duo. c chuyˆe’n theo du`ong
3. ´ ´ MOˆ. T THUAˆ. T TOAN´ GEN CHO THIEˆTKEˆ TOPOLOGY 61 . . . . . . . ABCD. Theo chiˆe´n luo. c hˆo`i phu. c 1+1 APS ho˘a.c 1:1 APS, du`ong AEFD duo. c su’ du. ng l`am . . . . . . . . du`ong hˆo`i phu. c. Khi c´osu. cˆo´, gia’ su’ l`atuyˆe´n AB bi. d´ut, c´ac chiˆe´n luo. c hˆo`i phu. c trˆen s˜esu’ . . . . . . du. ng du`ong hˆo`i phu. c AEFD dˆe’ chuyˆe’n ta’i luu luo. ng gi˜ua A v`aD. Mˆo.t c´ach kh´ac, nˆe´u theo . . . . . . . . . chiˆe´n luo. c hˆo`i phu. c tuyˆe´n, luu luo. ng chuyˆe’n v`ong qua tuyˆe´n bi. d´ut, cu. thˆe’ trong tru`ong ho. p . . . . . . . . . . n`ay du`ong AEBCD s˜e duo. c su’ du. ng. Chiˆe´n luo. c n`ay c˜ung c´othˆe’ su’ du. ng cho c´ac tru`ong . . . . . . ho. p n´ut bi. su. cˆo´, khi d´oc´othˆe’ coi khˆong c´oluu luo. ng chuyˆe’n qua c´ac tuyˆe´n c´okˆe´t nˆo´i t´oi . . . . . . n´ut d´o. C´ac kˆe´t qua’ nghiˆen c´uu t`u [10, 12] cho thˆa´y chiˆe´n luo. c hˆo`i phu. c theo du`ong c´ohiˆe.u . . suˆa´t su’ du. ng b˘ang thˆong cao hon. . . . . . . . . . . . C´ohai phuong ph´ap hˆo`i phu. c du`ong: phuong ph´ap hˆo`i phu. c du`ong theo phuong th´uc . . . . . . . . . . phˆan t´ach phˆa`n luu luo. ng trˆen du`ong bi. a’nh huo’ ng sang mˆo.t sˆo´ du`ong du. ph`ong kh´ac nhau . . . . . . . . . . . v`aphuong th´uc chuyˆe’n ta’i to`an bˆo. phˆa`n luu luo. ng bi. a’nh huo’ ng trˆen mˆo.t du`ong du. ph`ong . . . kh´ac. H`ınh 2 du´oi dˆay minh ho.a c´ach th´uc hˆo`i phu. c n`ay. G H B C uuu u A uuu D u uuu E F . . . . . H`ınh 2. Hˆo`i phu. c du`ong v´oi nhiˆe` u du`ong hˆo`i phu. c kh´ac nhau . . . . . . . . X´et la.i tru`ong ho. p khi nhu cˆa`u luu luo. ng AD di theo du`ong ABCD. Khi tuyˆe´n BC g˘a.p . . . . . . . . . su. cˆo´, nhu cˆa`u luu luo. ng AD duo. c phˆan t´ach l`am hai phˆa`n: phˆa`n th´u nhˆa´t duo. c di.nh tuyˆe´n . . . . . . . la.i di theo du`ong AEFD, phˆa`n th´u hai duo. c di trˆen du`ong AGHD. Diˆe` u n`ay l`aho`an to`an c´o . . . . . . . . . thˆe’ bo’ i trong nhiˆe` u tru`ong ho. p, nhu cˆa`u luu luo. ng AD l´on hon b˘ang thˆong c`on la.i cu’a mˆo.t . . . . . . . trong c´ac tuyˆe´n AE, EF,FD trˆen du`ong AEFD. V`ıvˆa.y chı’ mˆo.t phˆa`n luu luo. ng duo. c phˆan . . . . . bˆo’ trˆen du`ong n`ay. Phˆa`n c`on la.i pha’i di trˆen du`ong kh´ac (AGHD), m˘a.c d`uchi ph´ıcao hon. . . . . . . V´oi phuong th´uc hˆo`i phu. c theo nhiˆe` u du`ong, trong thiˆe´t kˆe´, chi phi tˆo’ng cˆo.ng (bao gˆo`m ca’ . . chi ph´ıdu. ph`ong cho hˆo`i phu. c) gia’m, kha’ n˘ang tˆa.n du. ng b˘ang thˆong cao hon. . . 2. VAˆ´N D`Eˆ VA` PHUONG PHAP´ THIEˆ´TKEˆ´ TOPOLOGY ’ ` MA. NG CO´ KHA NANG˘ HOˆI PHU. C . . . . . Mˆoh`ınh b`ai to´an thiˆe´t kˆe´ topology ma.ng hˆo`i phu. c s˜e duo. c thiˆe´t lˆa.p trˆen co so’ mo’ rˆo.ng . . mˆoh`ınh duo. c tr`ınh b`ay trong [1] dˆe’ t´ınh dˆe´n chi ph´ıb˘ang thˆong hˆo`i phu. c. . . . . . Mˆo.t ma.ng duo. c biˆe’u thi. qua mˆo.t graph vˆohu´ong G(V,E) v´oi V biˆe’u thi. tˆa.p c´ac n´ut . . . . . . ma.ng v´oi n phˆa`n tu’ v`a E biˆe’u thi. tˆa.p c´ac du`ong kˆe´t nˆo´i gi˜ua c´ac n´ut. Mˆo˜i mˆo.t nhu cˆa`u luu . . . . . . . luo. ng (commodity) duo. c di.nh ngh˜ıa l`anh´om luu luo. ng c`ung chung c˘a.p nguˆo`n d´ıch. Go.i D . . . . . . . . l`atˆa.p c´ac nhu cˆa`u luu luo. ng (quy dˆo’i theo don vi. bps), duo. c ta.o nˆen bo’ i c´ac phˆa`n tu’ n˘a`m . . . . . . . trˆen du`ong ch´eo cu’a mˆo.t ma trˆa.n vuˆong nhu cˆa`u luu luo. ng k´ıch thu´oc n. Mˆo˜i mˆo.t nhu cˆa`u . . . . . . . luu luo. ng c´othˆe’ duo. c truyˆe` n ta’i trˆen mˆo.t tˆa.p du`ong dˆa˜n kh´ac nhau. . . . Dˆe’ thuˆa.n tiˆe.n, c´ac k´yhiˆe.u sau duo. c su’ du. ng:
4. ˜ ` ´ 62 NGUYEˆN QUY´ MINH HIEˆN, PHA. M QUOˆ C HUY . . . . lij biˆe’u thi. du`ong kˆe´t nˆo´i gi˜ua hai n´ut i v`an´ut j v´oi nhau; . . . . cij l`adung luo. ng du`ong kˆe´t nˆo´i lij; s . . cij biˆe’u thi. b˘ang thˆong phˆan bˆo’ trˆen dˆe’ truyˆe’n ta’i c´ac nhu cˆa`u lij khi ma.ng chua c´osu. cˆo´; B . . cij biˆe’u thi. b˘ang thˆong phˆan bˆo’ trˆen cho viˆe.c du. ph`ong lij khi ma.ng c´osu. cˆo´; 0 Rkl biˆe’u thi. tˆa.p c´ac tuyˆe´n r truyˆe` n ta’i nhu cˆa`u dkl cu’a hai n´ut k v`a l; 1 Rkl biˆe’u thi. tˆa.p c´ac tuyˆe´n hˆo`i phu. c b d`ung dˆe’ hˆo`i phu. c nhu cˆa`u dkl; . . . . . λij l`achi ph´ıcho mˆo.t don vi. dung luo. ng du`ong lij; r . . . . . f0 l`aphˆa`n luu luo. ng cu’a dkl trˆen tuyˆe´n r khi ma.ng chua bi. su. cˆo´; b . . . . f1 l`aphˆa`n luu luo. ng cu’a dkl cˆa`n hˆo`i phu. c trˆen tuyˆe´n hˆo`i phu. c b khi ma.ng bi. su. cˆo´; r . . . . . . . . . δij b˘a`ng 1 nˆe´u tuyˆe´n r su’ du. ng du`ong kˆe´t nˆo´i lij duo. c su’ du. ng dˆe’ chuyˆe’n ta’i phˆa`n luu luo. ng . . cu’a nhu cˆa`u dkl, nguo. c la.i b˘a`ng 0; r . . . r b . . hij
   1 l`ahˆe. sˆo´ liˆen quan dˆe´n vˆa´n dˆe` trˆe˜ cho phˆa`n luu luo. ng f0 ho˘a.c f1 di qua du`ong kˆe´t nˆo´i lij, hiˆe.n c´ogi´atri. b˘a`ng 1; . . . 0  àkl  1 l`ahˆe. sˆo´ hˆo`i phu. c phˆa`n luu luo. ng cu’a dkl trˆen tuyˆe´n r sang mˆo.t tuyˆe´n kh´ac, hiˆe.n c´ogi´atri. b˘a`ng 1; r . . . . . . σkl c´ogi´atri. 1 khi trˆen tuyˆe´n r, chuyˆe’n ta’i phˆa`n luu luo. ng cu’a dkl, c´och´ua du`ong kˆe´t nˆo´i . . . bi. su. cˆo´. Nguo. c la.i s˜ec´ogi´atri. 0; 0 . . Rkl l`atˆa.p c´ac tuyˆe´n chuyˆe’n ta’i nhu cˆa`u dkl trˆen ma.ng khi chua c´osu. cˆo´; 1 . Rkl l`atˆa.p c´ac tuyˆe´n chuyˆe’n ta’i nhu cˆa`u dkl trˆen ma.ng khi c´osu. cˆo´; . . . . S l`atˆa.p nhu cˆa`u luu luo. ng pha’i hˆo`i phu. c khi c´osu. cˆo´ ma.ng; . F l`atˆa.p su. cˆo´ ma.ng c´othˆe’ xa’y; . . . . . . Ef l`atˆa.p c´ac du`ong kˆe´t nˆo´i c´othˆe’ a’nh huo’ ng bo’ i tˆa.p su. cˆo´ F ; Bf . . . . cij l`ab˘ang thˆong du. ph`ong cˆa`n phˆan bˆo’ cho du`ong lij dˆe’ hˆo`i phu. c ma.ng cho su. cˆo´ f dang x´et; s . . Gij l`achi ph´ıtruyˆe` n ta’i c´ac nhu cˆa`u trˆen ma.ng trong diˆe` u kiˆe.n b`ınh thu`ong; B . Gij l`achi ph´ıcho viˆe.c hˆo`i phu. c c´ac nhu cˆa`u khi c´osu. cˆo´. . . T`u dˆay c´othˆe’ lˆa.p cˆong th´uc cho b`ai to´an thiˆe´t kˆe´ topology ma.ng c´okha’ n˘ang hˆo`i phu. c . nhu sau: n−1 n Tˆo´i thiˆe’u h´oa s B
   
   λij(cij + cij) (1) i=1 i>1 sao cho r dkl =
   f0 , ∀k, l ∈ V (2) ∈ 0 r Rkl s r r r cij =
   
   δijhijf0 , ∀i, j, k, l ∈ V (3) d ∈D ∈ 0 kl r Rkl B b r b cij =
   
   δijàklhijf1, ∀i, j, k, l ∈ V (4) d ∈D ∈ 1 kl b Rkl
5. ´ ´ MOˆ. T THUAˆ. T TOAN´ GEN CHO THIEˆTKEˆ TOPOLOGY 63 b r r
   f1 =
   σklf0 , ∀i, j, k, l ∈ V. (5) ∈ 1 ∈ 0 b Rkl r Rkl . . . . . R`ang buˆo.c trong (2) nh˘a`m da’m ba’o mo.i nhu cˆa`u luu luo. ng dˆe` u duo. c chuyˆe’n ta’i trˆen . . . . ma.ng. Biˆe’u th´uc (3) da’m ba’o b˘ang thˆong phˆan bˆo’ trˆen c´ac du`ong kˆe´t nˆo´i l`ab˘a`ng ho˘a.c l´on . . . . . . . . hon luu luo. ng trˆen d´o. Biˆe’u th´uc (4) v`a(5) da’m ba’o b˘ang thˆong phˆa`n bˆo’ cho phˆa`n luu luo. ng . . . . . cˆa`n hˆo`i phu. c khi ma.ng c´osu. cˆo´. Biˆe’u th´uc (6) da’m ba’o phˆa`n luu luo. ng trˆen c´ac tuyˆe´n c´o . . . su. cˆo´ duo. c hˆo`i phu. c trˆen c´ac tuyˆe´n kh´ac. . Trong qu´atr`ınh thiˆe´t kˆe´ ma.ng, c´ac thuˆa.t to´an hˆo`i phu. c trˆen l´op kˆe´t nˆo´i c´othˆe’ chia l`am . . . . hai loa.i, mˆo.t loa.i su’ du. ng phuong ph´ap ILP (Integer Linear Progamming) nhu trong mˆo.t sˆo´ . . . . . t`ai liˆe.u v`aloa.i c`on la.i su’ du. ng phuong ph´ap thu. c nghiˆe.m (heuristic) ([4, 5, 6, 10, 12]). V´oi . . . . . phuong ph´ap ILP, c´ac kˆe´t qua’ da.t duo. c rˆa´t tˆo´t, tuy nhiˆen mˆa´t rˆa´t nhiˆe` u th`oi gian, cho nˆen . . . . . . . . . thu`ong ph`uho. p v´oi nh˜ung ma.ng nho’, c´osˆo´ luo. ng n´ut ´ıt. Nh˜ung thuˆa.t to´an thu. c nghiˆe.m . . . . . . . . mˆa´t ´ıt th`oi gian hon, d`uvˆa.y c´ac kˆe´t qua’ da.t duo. c c˜ung gˆa`n v´oi c´ac kˆe´t qua’ t`u phuong ph´ap . . . . ILP. Trong nh˜ung ma.ng c´osˆo´ luo. ng n´ut nhiˆe` u, lˆen dˆe´n h`ang v`ai chu. c n´ut, th`oi gian cˆa`n thiˆe´t . . . . . . . . . dˆe’ gia’i quyˆe´t b`ai to´an l`arˆa´t l´on, d˘a.c biˆe.t trong nh˜ung tru`ong ho. p sˆo´ du`ong kˆe´t nˆo´i l´on nhu . . . . . . . ma.ng lu´oi dˆa`y du’ (full mesh) cˆa`n su’ du. ng nh˜ung thuˆa.t to´an thu. c nghiˆe.m. C´ac phuong ph´ap . . . thu. c nghiˆe.m nhu ([4, 5, 6, 10, 12]) gia’i quyˆe´t vˆa´n dˆe` hˆo`i phu. c ma.ng du. a theo hai c´ach tiˆe´p . . . . cˆa.n l`a di.nh tuyˆe´n la.i du. a trˆen du`ong ng˘a´n nhˆa´t ([5, 6, 10]) ho˘a.c trˆen nguyˆen t˘a´c luˆo`ng cu. c . . . . . . . da.i ([4]). Tuy nhiˆen, dˆo´i v´oi c´ac phuong ph´ap n`ay dˆe` u thu`ong dua ra gia’ thiˆe´t khi xˆay du. ng . . . thuˆa.t to´an. C´ac thuˆa.t to´an trong [5, 6, 10, 12] di.nh tru´oc mˆo.t tˆa.p c´ac tuyˆe´n hˆo`i phu. c v`asu’ . . . du. ng trong qu´atr`ınh hˆo`i phu. c ma.ng v´oi gia’ thiˆe´t r˘a`ng sˆo´ luo. ng tuyˆe´n hˆo`i phu. c l`anho’. M˘a.c . . . . d`utrong [5] chı’ ra r˘a`ng viˆe.c su’ du. ng tˆa.p tuyˆe´n hˆo`i phu. c n`ay a’nh huo’ ng dˆe´n kˆe´t qua’ v`amo’ . . rˆo.ng hon tˆa.p tuyˆe´n hˆo`i phu. c, ho˘a.c trong [4] cho r˘a`ng c´ac tˆa.p c˘a´t (cut sets) l`anho’ th`ıviˆe.c su’ . . . . du. ng tˆa.p tuyˆe´n hˆo`i phu. c (hay c´ac tˆa.p c˘a´t) duo. c di.nh tru´oc s˜el`am gia’m kha’ n˘ang t`ım kiˆe´m . . . . . . gia’i ph´ap. Nh˜ung gia’ thiˆe´t nhu vˆa.y c´othˆe’ khˆong ph`uho. p cho c´ac ma.ng l´on m`asˆo´ luo. ng c´ac . . . tuyˆe´n hˆo`i phu. c ho˘a.c sˆo´ luo. ng l´at c˘a´t cho c´ac c˘a.p n´ut l`arˆa´t l´on. . . . . V`ıvˆa.y, phuong ph´ap dˆe` xuˆa´t o’ dˆay l`akhˆong su’ du. ng c´ac tˆa.p tuyˆe´n hˆo`i phu. c, hay c´ac . . . . tˆa.p c˘a´t di.nh tru´oc dˆe’ gia’i quyˆe´t b`ai to´an. V´oi mˆo˜i topology ma.ng dua ra, c´ac tuyˆe´n hˆo`i . . . . . . . phu. c duo. c t´ınh to´an trˆen co so’ du`ong ng˘a´n nhˆa´t. Dˆe’ tˆo´i uu viˆe.c thiˆe´t lˆa.p tuyˆe´n hˆo`i phu. c, . . mˆo.t trong nh˜ung vˆa´n dˆe` quan tro.ng cˆa`n gia’i quyˆe´t d´ol`al`am thˆe´ n`ao dˆe’ t˘ang hiˆe.u suˆa´t su’ . . du. ng c´ac kˆenh hˆo`i phu. c, t´uc l`at˘ang tˆo´i da viˆe.c su’ du. ng chung b˘ang thˆong hˆo`i phu. c trong c´ac . . . . . . . tru`ong ho. p ma.ng g˘a.p su. cˆo´. Phuong ´an dˆe` xuˆa´t o’ dˆay l`a, l˘a.p la.i (mˆo.t sˆo´ lˆa`n nhˆa´t di.nh) qu´a . . tr`ınh thiˆe´t lˆa.p v`aphˆan bˆo’ b˘ang thˆong hˆo`i phu. c, v´oi mˆo˜i lˆa`n l˘a.p l`aqu´atr`ınh lu. a cho.n ngˆa˜u . . nhiˆen c´ac su. cˆo´ trˆen ma.ng. Qu´atr`ınh l˘a.p v`alˆa´y ngˆa˜u nhiˆen c´ac su. cˆo´ s˜echo ph´ep t`ım ra c´ac . . gia’i ph´ap c´ohiˆe.u suˆa´t su’ du. ng b˘ang thˆong hˆo`i phu. c hiˆe.u qua’ hon. . . . . . . Phuong ph´ap thiˆe´t kˆe´ duo. c dˆe` xuˆa´t nhu sau: Su’ du. ng thuˆa.t to´an di truyˆe` n dˆe’ t`ım mˆo.t . topology ma.ng da’m ba’o truyˆe` n ta’i tˆa.p D c´ac nhu cˆa`u, sau d´othu. c hiˆe.n qu´atr`ınh di.nh tuyˆe´n . . . . . . . . . la.i c´ac nhu cˆa`u luu luo. ng cˆa`n hˆo`i phu. c theo phuong ph´ap hˆo`i phu. c du`ong trˆen nhiˆe` u du`ong . . . . . hˆo`i phu. c kh´ac nhau. Qu´atr`ınh x´ac di.nh c´ac du`ong hˆo`i phu. c s˜e duo. c l˘a.p v´oi mˆo.t sˆo´ lˆa`n x´ac . . . . di.nh. Chi ph´ıtˆo’ng cˆo.ng cho ca’ hai qu´atr`ınh n`ay l`aco so’ dˆe’ t´ınh m´uc dˆo. ph`uho. p (fitness) trong thuˆa.t to´an gen phu. c vu. cho qu´atr`ınh l˘a.p trong c´ac thˆe´ hˆe. tiˆe´p theo. . . . . . . . . . Thuˆa.t to´an gen [1], v´oi phuong ph´ap m˜ah´oa theo th´u tu. dua nhu cˆa`u luu luo. ng lˆen ma.ng
6. ˜ ` ´ 64 NGUYEˆN QUY´ MINH HIEˆN, PHA. M QUOˆ C HUY . . . . . . . . . cho nh˜ung ma.ng m`adung luo. ng du`ong kˆe´t nˆo´i l`ah˜uu ha.n, da.t hiˆe.u qua’ hon c´ac phuong . . ph´ap m˜ah´oa kh´ac trong c´ac t`ai liˆe.u [7, 9, 11]. Mˆo˜i nhu cˆa`u s˜e duo. c g´an mˆo.t sˆo´ x´ac di.nh. . . . . . . Chuˆo˜i c´ac sˆo´ n`ay s˜eta.o nˆen mˆo.t trˆa.t tu. dua c´ac nhu cˆa`u luu luo. ng trˆen ma.ng. V´ıdu. , gia’ su’ . . . . . . mˆo.t ma.ng gˆo`m 4 n´ut v´oi c´ac nhu cˆa`u luu luo. ng l`a D12,D13,D14,D23,D24,D34 v`a duo. c g´an . . . . sˆo´ lˆa`n luo. t l`a1, 2, 3, 4, 5, 6. Nhu vˆa.y nˆe´u theo mˆo.t chuˆo˜i trˆa.t tu. v´ıdu. 234516 s˜eta.o ra mˆo.t . . . . . topology ma.ng khi lˆa`n luo. t s˘a´p xˆe´p c´ac nhu cˆa`u luu luo. ng D13,D14,D23,D24,D12,D34 lˆen . . . . . . . . . ma.ng. C´ac nhu cˆa`u luu luo. ng duo. c s˘a´p xˆe´p trˆen ma.ng trˆen co so’ thuˆa.t to´an du`ong ng˘a´n . . . . . . . nhˆa´t. Trong nh˜ung ma.ng c´odung luo. ng du`ong kˆe´t nˆo´i vˆoha.n ho˘a.c rˆa´t l´on so v´oi nhu cˆa`u . . . . . . . . . . luu luo. ng th`ıtrˆa.t tu. dua c´ac nhu cˆa`u luu luo. ng lˆen ma.ng khˆong l`am a’nh huo’ ng dˆe´n chi ph´ı . . . . . . . . . . tˆo’ng cˆo.ng. Tuy nhiˆen, o’ nh˜ung ma.ng c´odung luo. ng h˜uu ha.n, trˆa.t tu. dua nhu cˆa`u luu luo. ng t´ac dˆo.ng rˆa´t nhiˆe` u dˆe´n chi ph´ıtˆo’ng cˆo.ng. . . . . . . . Kho’ i ta.o thˆe´ hˆe. kho’ i dˆa`u duo. c thu. c hiˆe.n b˘a`ng c´ach sinh ra c´ac chuˆo˜i v´oi trˆa.t tu. ngˆa˜u . . . . nhiˆen cu’a c´ac sˆo´ g´an cho c´ac nhu cˆa`u luu luo. ng. V´ıdu. nhu c´ac chuˆo˜i 234165, 623415, 342165 s˜eta.o nˆen c´ac topology ma.ng kh´ac nhau. . . . . . . . . To´an tu’ lai gh´ep, du. a trˆen co so’ su’ du. ng chuˆo˜i trˆa.t tu. nhu trˆen, gi˜ua hai c´athˆe’ c´ok´ıch . . . . . . thu´oc chuˆo˜i N, lai gh´ep ta.i vi. tr´ı L (L < N) bˆa´t k`y, v´ıdu. L = 3, s˜e duo. c thu. c hiˆe.n nhu sau: C´athˆe’ 1 thˆe´ hˆe. n: 136425 C´athˆe’ 2 thˆe´ hˆe. n: 234156 C´athˆe’ thˆe´ hˆe. n + 1: 136245 . . . . Nhu vˆa.y nguyˆen t˘a´c lai gh´ep l`at`u hai c´athˆe’ thˆe´ hˆe. dˆa`u k´ıch thu´oc N, lai gh´ep ta.i vi. . . . . . . . . tr´ı L(L < N), thˆe´ hˆe. sau duo. c ta.o ra v´oi k´ıch thu´oc N v`achuˆo˜i duo. c thiˆe´t lˆa.p v´oi L phˆa`n tu’. dˆa`u l`a L phˆa`n tu’. cu’a chuˆo˜i th´u. nhˆa´t v`a N − L phˆa`n tu’. tiˆe´p theo lˆa´y t`u. chuˆo˜i th´u. hai, . . . . . . b˘a`ng c´ach duyˆe.t theo trˆa.t tu. cu’a chuˆo˜i th´u hai, phˆa`n tu’ duo. c lˆa´y l`aphˆa`n tu’ khˆong xuˆa´t . hiˆe.n trong L phˆa`n tu’ dˆa`u. . . To´an tu’ dˆo.t biˆe´n, thu. c hiˆe.n trˆen mˆo.t c´athˆe’ n`ao d´o, ta.i hai vi. tr´ı K v`a L(K < N v`a . . . L < N), duo. c thu. c hiˆe.n b˘a`ng c´ach ho´an dˆo’i hai vi. tr´ı K v`a L cho nhau, v´ıdu. K = 2 v`a L = 5. C´athˆe’ i thˆe´ hˆe. n: 234156 . C´athˆe’ i sau khi thu. c hiˆe.n dˆo.t biˆe´n: 254136 . . Ngo`ai ra c´othˆe’ thu. c hiˆe.n to´an tu’ dˆo.t biˆe´n thˆong qua viˆe.c quay v`ong pha’i ho˘a.c v`ong tr´ai . ta.i vi. tr´ı L cu’a chuˆo˜i N nhu sau: . Quay v`ong pha’i ta.i vi. tri. L = 5 v´oi c´athˆe’ i: 234156, kˆe´t qua’ ta.o ra c´athˆe’: 562341 . Quay v`ong tr´ai ta.i vi. tri. L = 3 v´oi c´athˆe’ i:234156, kˆe´t qua’ ta.o ra c´athˆe’: 156234 . . . s Ta.i giai doa.n n`ay, tˆa.p c´ac du`ong kˆe´t nˆo´i lij c`ung v´oi b˘ang thˆong phˆan bˆo’ cij v`achi ph´ı s . . . . . Gij dˆe’ da’m ba’o truyˆe` n ta’i c´ac nhu cˆa`u luu luo. ng l`a duo. c x´ac di.nh. . B . Tiˆe´p theo, ta t´ınh b˘ang thˆong du. ph`ong cij v`achi ph´ıcho viˆe.c cˆa´p b˘ang thˆong du. ph`ong B . . Gij cho viˆe.c hˆo`i phu. c ma.ng khi c´osu. cˆo´. Dˆe’ t´ınh to´an b˘ang thˆong du. ph`ong, xem H`ınh 3 sau. . . . . . T`u H`ınh 3 cho thˆa´y, gia’ su’ tˆa.p su. cˆo´ bao gˆo`m tuyˆe´n AB v`aBC c´othˆe’ c´osu. cˆo´. Gia’ su’ , . . . . . . . . . khi tuyˆe´n kˆe´t nˆo´i BC bi. su. cˆo´, nhu cˆa`u luu luo. ng DAD v`a DED s˜e duo. c chuyˆe’n t`u du`ong . . . . . dˆa˜n ABCD v`aEBCD sang du`ong dˆa˜n AEFD v`aEFD. Viˆe.c chuyˆe’n sang c´ac du`ong dˆa˜n m´oi . . . . . . . . . c˜ung duo. c thu. c hiˆe.n theo thuˆa.t to´an du`ong ng˘a´n nhˆa´t. Trong tru`ong ho. p n`ay, gia’ su’ nhu . . . . cˆa`u luu luo. ng DAD v`a DED n˘a`m trong tˆa.p S (tˆa.p cˆa`n pha’i ba’o vˆe.) th`ı, b˘ang thˆong du.
7. ´ ´ MOˆ. T THUAˆ. T TOAN´ GEN CHO THIEˆTKEˆ TOPOLOGY 65 . . . . B B ph`ong trˆen tuyˆe´n kˆe´t nˆo´i EF v`aFD cho su. cˆo´ tuyˆe´n BC d´ut lˆa`n luo. t l`a CEF v`a CFD b˘a`ng . . . . B tˆo’ng nhu cˆa`u luu luo. ng DAD v`a DED. B˘ang thˆong du. ph`ong trˆen tuyˆe´n kˆe´t nˆo´i AE l`a CAE . . . s˜eb˘a`ng nhu cˆa`u luu luo. ng DAD. B C uuu u A uuu D u uuu E F . . . . . . H`ınh 3. Hu´ong nhu cˆa`u luu luo. ng DED v`a DAD thay dˆo’i khi ma.ng c´osu. cˆo´ . . . . . . Tiˆe´p tu. c x´et tiˆe´p tru`ong ho. p su. cˆo´ l`atuyˆe´n kˆe´t nˆo´i AB d´ut, khi d´ochı’ c´onhu cˆa`u luu . . . . . . . . . . luo. ng DAD duo. c chuyˆe’n sang du`ong dˆa˜n l`aAEFD. Trong tru`ong ho. p n`ay, b˘ang thˆong du. . . . . B B B . ph`ong s˜e duo. c phˆan bˆo’ trˆen c´ac tuyˆe´n AE, EF, FD lˆa`n luo. t l`a CAE , CEF v`a CFD b˘a`ng v´oi . . . . . . . . . nhu cˆa`u luu luo. ng DAD . Tuy nhiˆen, do b˘ang thˆong du. ph`ong d˜a duo. c phˆan bˆo’ t`u tru´oc cho . . . . . . . . . . . . . tru`ong ho. p su. cˆo´ tru´oc (BC d´ut) l´on hon b˘ang thˆong du. ph`ong cˆa`n cho tru`ong ho. p n`ay, . . . . . nˆen b˘ang thˆong du. ph`ong khˆong pha’i phˆan bˆo’ thˆem. V`anhu vˆa.y, tru`ong ho. p sau khˆong c´o . . . . . . . chi ph´ıcho viˆe.c phˆan bˆo’ thˆem b˘ang thˆong du. ph`ong. Nguo. c la.i, trong tru`ong ho. p su. cˆo´ d`oi . . . . . ho’i b˘ang thˆong du. ph`ong l´on hon b˘ang thˆong du. ph`ong d˜acˆa´p, th`ıb˘ang thˆong du. ph`ong s˜e . . . . b˘a`ng b˘ang thˆong du. ph`ong m´oi v`achi ph´ıs˜et˘ang thˆem mˆo.t luo. ng b˘a`ng chi ph´ıcho phˆa`n b˘ang thˆong t˘ang thˆem. T`u. d´ota c´o: B Bf Bf B Bf s cij = cij nˆe´u cij
   cij v`a cij  cij − cij, (6) B B Bf B cij = cij nˆe´u cij  cij, (7) B . . . . . . khi d´ochi ph´ı Gij cho viˆe.c cˆa´p b˘ang thˆong hˆo`i phu. c s˜e duo. c t´ınh trˆen co so’ cho c´ac tru`ong . ho. p (6) v`a(7). . . . Thuˆa.t to´an t´ınh to´an b˘ang thˆong v`achi ph´ıcho viˆe.c hˆo`i phu. c ma.ng duo. c mˆota’ nhu sau: Procedure Resilent Cost() B Cij = 0; for N = 1 to N = Nmax do . for |F | su. cˆo´ trong tˆa.p F do . . Lu. a cho.n ngˆa˜u nhiˆen mˆo.t su. cˆo´ Fi; . . . . . . X´ac di.nh tˆa.p c´ac du`ong kˆe´t nˆo´i Ef bi. a’nh huo’ ng bo’ i su. cˆo´; . . . . . . X´ac di.nh c´ac nhu cˆa`u luu luo. ng Sij cˆa`n phu. c hˆo`i su’ du. ng c´ac du`ong kˆe´t nˆo´i Ef ; . . . . Cˆa.p nhˆa.t la.i G(V, E) trˆen co so’ loa.i bo’ c´ac du`ong kˆe´t nˆo´i Ef ; . . . . Di.nh tuyˆe´n la.i c´ac nhu cˆa`u luo. ng Sij trˆen G(V, E) theo du`ong ng˘a´n nhˆa´t; X´ac di.nh b˘ang thˆong hˆo`i phu. c; X´ac di.nh chi ph´ıcho b˘ang thˆong hˆo`i phu. c; . . Tra’ la.i c´ac du`ong kˆe´t nˆo´i Ef trong G(V, E); end X´ac di.nh chi ph´ıb˘ang thˆong hˆo`i phu. c tˆo´i thiˆe’u; end
8. ˜ ` ´ 66 NGUYEˆN QUY´ MINH HIEˆN, PHA. M QUOˆ C HUY . . . . . Qu´atr`ınh t`ım kiˆe´m c´ac du`ong dˆa˜n m´oi s˜eloa.i bo’ c´ac du`ong kˆe´t nˆo´i m`akhˆong c`on b˘ang thˆong cho viˆe.c hˆo`i phu. c. S B . . . . . C´ac kˆe´t qua’ t´ınh to´an chi ph´ıb˘ang thˆong Gij,Gij duo. c su’ du. ng dˆe’ t´ınh m´uc dˆo. ph`uho. p . . . . cu’a c´ac c´athˆe’. Nhu vˆa.y, to`an bˆo. thuˆa.t to´an thiˆe´t kˆe´ duo. c mˆota’ nhu sau: Procedure Algorithm Resilent Network() . . . . Kho’ i ta.o thˆe´ hˆe. dˆa`u P v´oi sˆo´ luo. ng N; for gen =1 to maxGen do for j = 1 to N/2 do . Lu. a cho.n ngˆa˜u nhiˆen c´athˆe’ bˆa´t k`ytrong P ; . . Cho.n hai c´athˆe’ c´om´uc dˆo. ph`uho. p cao nhˆa´t trong ba c´athˆe’; Lai gh´ep hai c´athˆe’; end . . . . Ta.o c´ac c´athˆe’ dˆo.t biˆe´n t`u P v´oi mˆo.t sˆo´ luo. ng x´ac di.nh; . . . . . Kho’ i ta.o mˆo.t sˆo´ c´athˆe’ m´oi v´oi sˆo´ luo. ng x´ac di.nh; . . . T´ınh to´an m´uc dˆo. ph`uho. p cu’a c´ac c´athˆe’ m´oi; // t´ınh ca’ chi ph´ıhˆo`i phu. c . . . . Lu. a cho.n N c´athˆe’ m´oi c´om´uc dˆo. ph`uho. p cao nhˆa´t trong to`an bˆo. tˆa.p c´athˆe’; Du.a ra c´ac kˆe´t qua’; End . . . . Mˆo.t c´ach tiˆe´p cˆa.n kh´ac du. a trˆen mˆo.t c´ach tiˆe´p cˆa.n d˜a duo. c dˆe` xuˆa´t d´ol`asu’ du. ng thuˆa.t . . to´an di truyˆe` n t`ım mˆo.t topology ma.ng v´oi chi ph´ıthˆa´p nhˆa´t (chua c´okha’ n˘ang phu. c hˆo`i) . . . . . trong viˆe.c da’m ba’o truyˆe` n ta’i tˆa.p D c´ac nhu cˆa`u luu luo. ng. M´uc dˆo. ph`uho. p (fitness) trong . . ’. thuˆa.t to´an di truyˆe` n chı’ duo. c t´ınh cho giai doa.n dˆa`u. O giai doa.n sau s˜e di.nh tuyˆe´n la.i c´ac . . . nhu cˆa`u luu luo. ng cˆa`n phu. c hˆo`i v`achi ph´ıcuˆo´i c`ung l`atˆo’ng cu’a hai giai doa.n. Viˆe.c so s´anh . . . . hai c´ach tiˆe´p cˆa.n n`ay s˜e duo. c thˆe’ hiˆe.n qua mˆo.t sˆo´ kˆe´t qua’ t´ınh to´an du´oi dˆay. ´ ´ ’ . 3. MOˆ. TSOˆ KEˆT QUA T´INH TOAN´ THU. C NGHIEˆ. M . . . . . . . Mˆo.t sˆo´ kˆe´t qua’ thu duo. c trong qu´atr`ınh thu. c hiˆe.n hai phuong ph´ap tiˆe´p cˆa.n trˆen duo. c . . . . . . . dua ra o’ dˆay. Tˆa´t ca’ c´ac kˆe´t qua’ duo. c thu. c hiˆe.n trˆen co so’ l˘a.p la.i mˆo.t sˆo´ lˆa`n. Dˆe’ so s´anh . . . . t´ınh hiˆe.u qua’ gi˜ua viˆe.c su’ du. ng chi ph´ıthiˆe´t lˆa.p ma.ng chua c´odu. ph`ong v`achi ph´ıtˆo’ng cˆo.ng . . . (gˆo`m ca’ chi ph´ıdu. ph`ong) dˆe’ t´ınh m´uc dˆo. ph`uho. p cho thuˆa.t to´an gen, mˆo.t ma.ng 20 n´ut . . . . . . . . . . duo. c su’ du. ng. C´ac ma trˆa.n nhu cˆa`u luu luo. ng, dung luo. ng c´ac du`ong kˆe´t nˆo´i, chi ph´ıdung . . . . . . . . . . . . . . luo. ng du`ong kˆe´t nˆo´i, duo. c sinh ngˆa˜u nhiˆen bo’ i chuong tr`ınh. C´ac nhu cˆa`u luu luo. ng duo. c . . . . . . quy dˆo’i c´ogi´atri. t`u 0.5Mbps dˆe´n 2.5Mbps; dung luo. ng du`ong kˆe´t nˆo´i c´ogi´atri. t`u 3Mbps . . . . dˆe´n 5Mbps; chi ph´ıcho mˆo.t don vi. dung luo. ng kˆenh kˆe´t nˆo´i t`u 5000 dˆe´n 35000 cho 1Kbps; . . . . . k´ıch thu´oc dˆan sˆo´ duo. c d˘a.t v´oi gi´atri. 25, sˆo´ thˆe´ hˆe. l`a50, ty’ lˆe. lai gh´ep l`a45%, ty’ lˆe. dˆo.t biˆe´n . l`a30%, ty’ lˆe. ta.o c´athˆe’ m´oi l`a55%. Trˆen c´ac H`ınh 3a v`aH`ınh 3b tr`ınh b`ay c´ac kˆe´t qua’ t´ınh to´an. Chi ph´ı G1 v`a G1 ´u.ng v´o.i . . . . . . . . . tru`ong ho. p thiˆe´t kˆe´ topology ma.ng v´oi m´uc dˆo. ph`uho. p trong thuˆa.t to´an gen duo. c du. a trˆen . .  . .  . . . co so’ chi ph´ı G1 m`akhˆong t´ınh dˆe´n G1 . Nguo. c la.i, chi ph´ı G2 v`a G2 l`acho tru`ong ho. p . . .  m´uc dˆo. ph`uho. p du. a trˆen chi ph´ıtˆo’ng cˆo.ng G2 + G2 . C´ac chi ph´ı G1 v`a G2 l`achi ph´ıthiˆe´t . .   lˆa.p ma.ng chua c´odu. ph`ong. C´ac chi ph´ı G1 v`a G2 l`ac´ac chi ph´ıcho viˆe.c hˆo`i phu. c ma.ng.
9. ´ ´ MOˆ. T THUAˆ. T TOAN´ GEN CHO THIEˆTKEˆ TOPOLOGY 67 Chi phớ Chi Chi phớ Chi Thế hệ Thế hệ H`ınh 3a. H`ınh 3b. . . . . . . . . Hˆo`i phu. c du`ong trˆen mˆo.t du`ong hˆo`i phu. c Hˆo`i phu. c du`ong trˆen nhiˆe` u du`ong hˆo`i phu. c . . . . . . C´ac kˆe´t qua’ t´ınh to´an cho hai tru`ong ho. p hˆo`i phu. c du`ong cho thˆa´y r˘a`ng viˆe.c su’ du. ng . . . . . chi ph´ıtˆo’ng cˆo.ng l`am co so’ t´ınh m´uc dˆo. ph`uho. p cu’a thuˆa.t to´an gen s˜echo kˆe´t qua’ tˆo´t hon. . . . . . . . . Trˆen co so’ n`ay, c´ac t´ınh to´an tiˆe´p theo duo. c thu. c hiˆe.n nh˘a`m so s´anh ba phuong th´uc: hˆo`i . . . . . . . . . phu. c du`ong trˆen mˆo.t du`ong hˆo`i phu. c (non-bifurcation) - phuong th´uc 1, hˆo`i phu. c du`ong . . . . . . . . trˆen nhiˆe` u du`ong hˆo`i phu. c (bifurcation) - phuong th´uc 2 v`aphu. c hˆo`i l˘a.p l`aphuong th´uc . . . . . . . . duo. c dˆe` xuˆa´t o’ dˆay du. a trˆen co so’ l˘a.p la.i mˆo.t sˆo´ lˆa`n qu´atr`ınh phu. c hˆo`i du`ong trˆen nhiˆe` u . . . . . du`ong hˆo`i phu. c - phuong th´uc 3. Chi phí Chi phí Chi phí T hế hệ T hế hệ T hế hệ Hỡnh 4a uu Hỡnh 4b u uHỡnh 4c uuu u u uo uo uo . . . . Trong [12] dua ra thuˆa.t to´an hˆo`i phu. c MCR (Minimum Cost Restoration) v´oi n˘am bu´oc . . . . . . . . . . . . . thu. c hiˆe.n. Hai bu´oc dˆa`u vˆe` nˆo.i dung tuong tu. nhu phuong th´uc 1 tr`ınh b`ay o’ trˆen. Ba bu´oc . . . . sau thu. c chˆa´t l`aqu´atr`ınh tˆo´i uu tiˆe´p du. a trˆen qu´atr`ınh t`ım kiˆe´m cu. c bˆo. t`u kˆe´t qua’ cu’a hai . . . . . . . . . . bu´oc dˆa`u. Phuong th´uc hˆo`i phu. c theo thuˆa.t to´an MCR duo. c xˆay du. ng nh˘a`m l`am co so’ so . . . s´anh v´oi thuˆa.t to´an hˆo`i phu. c l˘a.p duo. c dˆe` xuˆa´t ta.i dˆay. Trˆen H`ınh 4a, 4b v`a4c thˆe’ hiˆe.n c´ac . . . . . kˆe´t qua’ duo. c thu. c hiˆe.n trong diˆe` u kiˆe.n kh´ac nhau vˆe` yˆeu cˆa`u m´uc dˆo. phu. c hˆo`i ta.i c´ac m´uc dˆo. 12%, 40% v`a60%. . . . . Kˆe´t qua’ cho thˆa´y viˆe.c thu. c hiˆe.n phu. c hˆo`i theo phuong th´uc l˘a.p cho kˆe´t qua’ tˆo´t nhˆa´t.
10. ˜ ` ´ 68 NGUYEˆN QUY´ MINH HIEˆN, PHA. M QUOˆ C HUY . . . . . . . Nh˜ung tru`ong ho. p m´uc dˆo. yˆeu cˆa`u phu. c hˆo`i cu’a ma.ng l`acao t`u khoa’ng 40% tro’ lˆen, c´ac . . . . . phuong th´uc hˆo`i phu. c 2 v`a3 dang xem x´et cho kˆe´t qua’ tˆo´t hon dˆoi ch´ut so v´oi thuˆa.t to´an . . . . . . MCR o’ [12]. Nguyˆen nhˆan l`ado trong nh˜ung tru`ong ho. p m`ayˆeu cˆa`u m´uc dˆo. hˆo`i phu. c cao, . . . . . . . . viˆe.c su’ du. ng phuong ph´ap hˆo`i phu. c nhiˆe` u du`ong cho kˆe´t qua’ tˆo´t hon phuong ph´ap hˆo`i phu. c . . . . . . . khˆong trˆen nhiˆe` u du`ong m`athuˆa.t to´an MCR ´ap du. ng. V´oi tru`ong ho. p m´uc dˆo. nhu cˆa`u hˆo`i . . . . . . . . . . . . phu. c thˆa´p khoa’ng trˆen du´oi 10% ho˘a.c tuong duong v´oi c´ac tru`ong ho. p m`adung luo. ng c´ac . . . . . . . du`ong kˆe´t nˆo´i c`on du th`ua nhiˆe` u khi so s´anh tuong dˆo´i v´oi nhu cˆa`u cˆa`n hˆo`i phu. c, th`ıthuˆa.t . . . to´an MCR cho kˆe´t qua’ trˆo.i hon dˆoi ch´ut (H`ınh 4a). Kˆe´t qua’ n`ay do khi ma.ng c`on du th`ua . . . . . . . b˘ang thˆong, phuong ph´ap hˆo`i phu. c trˆen nhiˆe` u du`ong m`aphuong th´uc 2 v`a3 ´ap du. ng khˆong . . . . . . vuo. t trˆo.i so v´oi phuong th´uc MCR ´ap du. ng. M˘a.t kh´ac, vˆe` ba’n chˆa´t, thuˆa.t to´an MCR c˜ung . . . . . ´ap du. ng mˆo.t qu´atr`ınh t`ım kiˆe´m tˆo´i uu dˆe’ ca’i tiˆe´n chˆa´t luo. ng cu’a gia’i ph´ap da.t duo. c. Tuy . . . . . nhiˆen, c˜ung cˆa`n luu ´yr˘a`ng, kh´ac v´oi thuˆa.t to´an dˆe` xuˆa´t o’ dˆay thu. c hiˆe.n theo biˆen da th´uc . . th`oi gian (polynomial-time bound), thuˆa.t to´an MCR l`athuˆa.t to´an thu. c hiˆe.n khˆong theo biˆen . . . . . da th´uc th`oi gian. Do vˆa.y th`oi gian chi ph´ıcho viˆe.c thu. c hiˆe.n thuˆa.t to´an MCR rˆa´t l´on, gˆa´p . nhiˆe` u lˆa`n thuˆa.t to´an dˆe` xuˆa´t o’ dˆay. . . . Go.i chi ph´ıcho viˆe.c thiˆe´t kˆe´ topology ma.ng c´okha’ n˘ang hˆo`i phu. c cho tru`ong ho. p 1 l`a 1 . . . . . . 2 3 . . . . C , tuong tu. cho phuong th´uc 2 v`a3 l`a C ,C . Trong H`ınh 5 du´oi dˆay, tru. c tung duo. c t´ınh t`u. ty’ sˆo´ cu’a (C1 − C2)/C1 v`a (C1 − C3)/C1 tu.o.ng ´u.ng v´o.i phu.o.ng th´u.c 2 v`a3 nh˘a`m . . . . . so s´anh m´uc dˆo. t´ıch kiˆe.m chi ph´ıcu’a c´ac phuong th´uc hˆo`i phu. c ta.i c´ac m´uc dˆo. yˆeu cˆa`u hˆo`i . . . . . . . . phu. c kh´ac nhau. T`u H`ınh 5 c´othˆe’ thˆa´y r˜oviˆe.c su’ du. ng phuong th´uc l˘a.p - phuong th´uc 3 . . . . . . . c´om´uc dˆo. t´ıch kiˆe.m chi ph´ıhon h˘a’ n phuong th´uc 2 khi m´uc dˆo. yˆeu cˆa`u hˆo`i phu. c t˘ang t`u . . . . . . . . . khoa’ng 40% tro’ lˆen. Phuong th´uc hˆo`i phu. c trˆen nhiˆe` u du`ong - phuong th´uc 2 c´onhiˆe` u hiˆe.u . . . . . . . . . . . qua’ hon so v´oi phuong th´uc hˆo`i phu. c trˆen mˆo.t du`ong - phuong th´uc 1, t`uy thuˆo.c v`ao t`ung . . . . . ma.ng, m´uc dˆo. hiˆe.u qua’ t˘ang dˆa`n theo m´uc dˆo. t˘ang cu’a nhu cˆa`u luu luo. ng cˆa`n hˆo`i phu. c v`a . . . da.t dˆe´n mˆo.t gi´atri. n`ao d´o. Sau d´o, m´uc dˆo. hiˆe.u qua’ la.i gia’m khi t˘ang m´uc dˆo. nhu cˆa`u luu . . . . . . luo. ng cˆa`n hˆo`i phu. c. Diˆe` u n`ay l`ado khi t˘ang qu´am´uc dˆo. nhu cˆa`u luu luo. ng cˆa`n phu. c hˆo`i, . . . . . . . cˆa`n thiˆe´t lˆa.p c´ac tuyˆe´n m´oi, dˆo´i v´oi c´ac phuong th´uc dˆe` u khˆong t´ıch kiˆe.m duo. c chi ph´ı. Ph−ơng thức 2 Ph−ơng thức 3 Mức độ nhu cầu l−u l−ợng cần phục hồi (%) . . . . . H`ınh 5. Chˆenh lˆe.ch chi ph´ıthiˆe´t kˆe´ khi su’ du. ng phuong th´uc hˆo`i phu. c 1 v´oi 2 v`a3 . . V´oi c´ac kˆe´t qua’ t´ınh to´an n`ay, ch´ung tˆoi thu. c hiˆe.n thiˆe´t kˆe´ topology ma.ng c´okha’ n˘ang . . . . . . . . hˆo`i phu. c cho tru`ong ho. p ma.ng 35 n´ut v`ama.ng 50 n´ut v´oi m´uc dˆo. nhu cˆa`u luu luo. ng cˆa`n . . . . . hˆo`i phu. c l`a12% cho hai phuong th´uc: phu. c hˆo`i trˆen nhiˆe` u du`ong v`aphu. c hˆo`i l˘a.p. C´ac kˆe´t
11. ´ ´ MOˆ. T THUAˆ. T TOAN´ GEN CHO THIEˆTKEˆ TOPOLOGY 69 . . . . qua’ duo. c thˆe’ hiˆe.n ta.i H`ınh 6a v`a6b du´oi dˆay. . . . . . . . T`u kˆe´t qua’ t´ınh to´an so bˆo. cho thˆa´y, trong mˆo.t sˆo´ tru`ong ho. p thu. c nghiˆe.m nhu trˆen, . . phuong ph´ap hˆo`i phu. c l˘a.p cho kˆe´t qua’ kha’ quan. ´ 4. KEˆT LUAˆ. N . . . . Qua c´ac kˆe´t qua’ t´ınh to´an o’ trˆen c´othˆe’ thˆa´y, thuˆa.t to´an hˆo`i phu. c l˘a.p duo. c dˆe` xuˆa´t o’ . . . . . . dˆay cho kˆe´t qua’ t´ınh to´an tˆo´t hon so v´oi mˆo.t sˆo´ thuˆa.t to´an kh´ac d˜a duo. c dˆe` cˆa.p tru´oc dˆay. . . . . . . M´uc dˆo. t´ıch kiˆe.m chi ph´ıcu’a thuˆa.t to´an c`ang l´on khi m´uc dˆo. yˆeu cˆa`u phu. c hˆo`i luu luo. ng . . . . ma.ng c`ang l´on. M˘a.t kh´ac, qu´atr`ınh thiˆe´t kˆe´ ma.ng v´oi viˆe.c kˆe´t ho. p gi˜ua qu´atr`ınh thiˆe´t kˆe´ . . ma.ng trong diˆe` u kiˆe.n b`ınh thu`ong v`aqu´atr`ınh t´ınh to´an phˆan bˆo’ b˘ang thˆong hˆo`i phu. c da.t . kˆe´t qua’ tˆo´t hon viˆe.c phˆan t´ach hai qu´atr`ınh t´ınh to´an thiˆe´t kˆe´ riˆeng biˆe.t. Qu´atr`ınh t´ınh . . . . . . . to´an c˜ung cho thˆa´y, viˆe.c su’ du. ng c´ac phuong ph´ap hˆo`i phu. c du`ong trˆen nhiˆe` u du`ong hˆo`i . . phu. c cho ph´ep su’ du. ng b˘ang thˆong hiˆe.u qua’ hon, t´ıch kiˆe.m chi ph´ı, kha’ n˘ang thiˆe´t kˆe´ ma.ng . . linh hoa.t hon. Thuˆa.t to´an thiˆe´t kˆe´ topology ma.ng hˆo`i phu. c nhu trˆen c´okha’ n˘ang thiˆe´t kˆe´ . . . . . . . . . . cho c´ac ma.ng lu´oi dˆa`y du’, dung luo. ng h˜uu ha.n v´oi sˆo´ luo. ng n´ut l´on, d´ap ´ung nhu cˆa`u thiˆe´t . . kˆe´ c´ac ma.ng l´on trong thu. c tˆe´. . . . Gi´oi thiˆe.u chuong tr`ınh: . . . . . . . ++ Thuˆa.t to´an duo. c thu. c hiˆe.n qua chuong tr`ınh xˆay du. ng trˆen ngˆon ng˜u lˆa.p lˆa.p tr`ınh C . . . . . . Chuong tr`ınh cho ph´ep nhˆa.p ho˘a.c tu. sinh c´ac d˜u liˆe.u dˆa`u v`ao nhu ma trˆa.n nhu cˆa`u, ma trˆa.n . . . . . . . . . kˆe´t nˆo´i, dung luo. ng du`ong kˆe´t nˆo´i, gi´a don vi. cho c´ac du`ong kˆe´t nˆo´i, tˆa.p c´ac du`ong kˆe´t nˆo´i . . . . c´othˆe’ bi. su. cˆo´, tˆa.p c´ac nhu cˆa`u cˆa`n ba’o vˆe C´ac t`uy cho.n kh´ac duo. c hˆo˜ tro. nh˘a`m t˘ang kha’ . . . . . n˘ang t`ım kiˆe´m trong phˆa`n thuˆa.t to´an gen cu’a chuong tr`ınh nhu d˘a.t k´ıch thu´oc dˆan sˆo´, ty’ lˆe. . lai gh´ep, ty’ lˆe. dˆo.t biˆe´n, ty’ lˆe. ta.o c´athˆe’ m´oi. ’ TAI` LIEˆ. U THAM KHAO [1] L. Berry, B. Murtagh, G. McMahon, S. Sugden, and M. Randall, Fast Network Design for Telecommunications, 1999.
12. ˜ ` ´ 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. Nhˆa. n b`ai ng`ay 5 - 9 - 2006 . Nhˆa. n la. i sau su’ a ng`ay 15 - 1 -2007