Định tuyến đảm bảo chất lượng dịch vụ trong mạng hình lưới không dây

HE VIEN THONG<br /> <br /> <br /> <br /> <br /> OINH TUYEN DAM BAO CHAT LU'ONG<br /> DICH VU TRONG MANG HINH LliOl<br /> KHONG DAY Hoang Trpng Minh<br /> <br /> <br /> Cac cong nghe mang hinh lUdi khong day WMN (Wireless Mesh Network) dang du'dc<br /> coi la cong nghe mau chdt cho mang khong day the he ke tiep. Tuy nhien, de phat trien<br /> WMN thanh cong trong thUc t e , rat nhieu cac thach thiifc can phai viTdt qua va chat<br /> iiTdng dich vu la mot trong so do. Hdn nuTa, cac giai phap djnh tuyen QoS trong mang<br /> WMN nham cung cap QoS cho cac dich vu hien nay van chUa dat dUdc cac ket qua mong<br /> muon. Bai bao tong hdp va phan tich cac hxidng tiep can trong ITnh vifc d[nh tuyen QoS.<br /> <br /> <br /> <br /> <br /> G I O I THIEU thuong mal v i chuyen dung nhu: Mang bang rbng lai<br /> Trong thbi gian gin day, mang hinh lubi khbng diy nha, mang epng ddng, cac mang db thi, cic he thdng<br /> WMN dang nhan dupc su quan lam rat Ibn ta cae nha giao thbng, he thdng tu dbng hba ttong tba nha, eae<br /> nghien dm vi trien khai. WMN cb mbt sd cae uu diem he thdng y te v i chiia benh, cic he thdng an ninh v i<br /> r5 ret so vbi cie loai mang khae xuat phit ta khi nang cic trayen thbng mang ngang hang va khan cap [2].<br /> trien khai, eiu hinh v i ttr cau hinh nhanh. Cau tnic Moi mpt mbi trabng iing dung deu dat ra cac yeu<br /> mang WMN dien hinh gdm eac bb dinh tayen bd tri cau nhat dinh ve loai hinh dich vu vi chat lupng dich<br /> tinh vi eie thiet bi diu cudi di dbng dupc ket ndi theo vu ddi vbi ha ling mang. Van de cung cap chat lupng<br /> hinh lubi tao thinh cae node mang (Hinh 1). Dua tten dich vu (QoS) dupc coi la dieu kien mau chdt de cac<br /> chiic nang ciia eae node, cie mang WMN dupc phan he thdng mang dupe trien khai ttong mbi trabng thuc.<br /> tiiinh 3 loai: WMN phing, WMN phan cap v i WMN lai Tren thuc le, cie yeu eiu chat lupng dich vu to phia<br /> ghep [1]. Node mang cb the dbng vai ttb nhu bp dinh khach hang rat da dang da dat van de eung cap QoS<br /> tayen hoae thiet bi diu cudi va su dung chuyen tiep thinh bii toin phiie lap vbi nhieu khia canh Uen<br /> da bube qua eau tnic hinh lubi de trayen thbng. quan. Trong db, he thdng dinh tayen dbng vai trb tam<br /> Nhb ket hpp dupc cic uu diem cua mang tray rihap diem dia mang trayen thbng v i dupc coi la yeu td<br /> cue bp v i mang tay bien, cac mang WMN hiia hen dua quyet dinh vbi vin de chat lupng dich vu dubi gbc dp<br /> ra mpl ha tang hap dan cho hing loat cac ung dung hieu nang mang.<br /> <br /> <br /> <br /> <br /> TAP CHI CNTT&TT KY 1 (7.2010) 19<br />  CONG NGHE VIEN THONG<br /> <br /> <br /> Mbt dubng din ihba man tat ci m dieu<br /> kien rang bube dupc coi la mbt dubng din khi<br /> Client<br /> thi. Trong dd thi cb the cb rat nhieu dubng<br /> Client dan khi thi va MCP cin tim dupe dubng dan<br /> ngin nhat l(P) ttong tip eae dubng din kha<br /> Ciie Rolner Client thi. Him !{P) thda man mipl sd tieu chuan<br /> <br /> B- ttong cie dieu kien ring bube dupc gpi li bii<br /> toin dubng din ldi uu da rang buoc MCOP<br /> (Multi-Consttamed Qptimal Path). De thda<br /> man phuong trinh (1), bii loin MCOP tdi<br /> thieu tieu ehuan dp dii giiia cap node ngudn-<br /> dich (cbn gpi li him ldi thieu gia) nhu sau:<br /> Lien ket huu tuyen /(P) < I{P') vbi P' la tat ca cic dubng din<br /> l.ien k6[ vi> liiven<br /> Cateuav giiia cap node ngudn-dieh. Vin de khb nhat<br /> Hinh 1: Kien tnic dien hinh cua mang WMN cua MCOP chinh li dp phiic tap cua bii toin.<br /> Khi bii loan MCOP thupc vio Ibp bai loan NP-<br /> Comlete, thbi gian yeu eau de giai khbng dupe<br /> De thuc hien dupc cac ky thuit dinh tayen dam xic dinh chinh xac vi dubng bien tten trong trabng<br /> bao QoS, cic quyet dinh chpn dubng din phai thda hpp xau nhat li mpl him thai gian da thiic.<br /> man cic dieu kien rang bube vi tdi uu vbi ttang thai a. Khia canh thuat toan<br /> mang, dieu nay dae biet khb vbi cac loai mang cb tinh Nhu tten da trinh biy, vbi tiep can su dung thuat<br /> bat dn dinh nhu WMN. Vi vay, rat nhieu nghien cim loan tinh loan chinh xic cho bii loin MCOP, thbi gian<br /> ve giii phap dinh tayen QoS vin dang tiep tuc dupc yeu ciu tinh loan cb the rat Ibn vi khbng ung dung<br /> cii thien de vupt qua mbt loat oac thach Ihiic cd hiiu cho mbi trabng thuc. Vbi m>2, Wang & Crowroft da<br /> cua WMN. chimg minh bii loan MCOP li bii loan NP-eomplele.<br /> Vi vay cb rit il cic de xuat theo hubng tiep can niy<br /> CAC KHIA CANH CUA DINH TUYEN QoS cho cic mang thuc tien. Mpl each tiep can thdng dung<br /> vbi cic bii toin MCOP la su dung tham sd tich hpp<br /> Mpt each tdng quat, vin de dinh tayen QoS dupc<br /> ket hop vbi thuat loan heuristic. Trong db, mpt tip<br /> bieu dien qua bii toin dubng din da rang buoc MCP<br /> cac tham sd QoS se the hien qua mpl tham sd don v i<br /> (Multi consttained Path) nhu sau [3]:<br /> dupe tinh loan qua cic thuat loin trayen thdng nhu<br /> Cau hinh mang dupc mb hinh hba bbi dd thi G(N, E),<br /> BelUnan Ford hoac Dijkstta.<br /> (N: lap cac node; E: tap cac lien ket). Cac tham sd do<br /> QoS dupc ky kieu la m va moi Uen ket dupc die trung b. Khia canh dong<br /> <br /> bai mpt vector ttpng sdw(» ^ v ) = [u'|, ii'^,.. w^] Trang thai, cau hinh mang v i cae ehi tieu QoS la eic<br /> vbi m>0 vi cic thanh phan M\{ii,v)>0, cac die linh phai dupc phan inh ttong cae tham sd dinh<br /> tham sd do QoS cb the mang tinh ebng, tinh nhan, tayen, db li nhiing dieu kien diu vio cho eae quyet<br /> tinh 16m. Bii loin MCP lim kiem dubng din P ta mbt dinh chpn dubng din. Vi viy, lira chpn cac tham sd<br /> node ngudn tbi mpt node dich thoa man phuong trinh dinh tayen la mpt van de quan ttpng nhat ttong cic<br /> (1), vbi \