Tối ưu hoá gán kênh cố định cho các mạng di động tế bào

sù miªu t¶ ®Çy ®ñ viÖc sö dông GA cho bµi to¸n g¸n kªnh cã thÓ t×m thÊy trong [10]. ViÖc sö dông GA cho g¸n kªnh trong c¸c hÖ thèng tÕ bµo ®−îc miªu t¶ trong [20], [23]. Gièng nh− SA, GA cung cÊp mét c¸ch cã hÖ thèng viÖc dù ®o¸n ®Ó ®¹t ®−îc d©n sè thÝch nghi tèt t¨ng lªn lµm cho sù thùc hiÖn c«ng viÖc tèt h¬n cña viÖc ®¹t ®−îc c¸c môc tiªu m¹ng. Nã còng t¹o ra sù miÔn gi¶m hîp lý khái bÕ t¾c trong cùc tiÓu ho¸ côc bé; nh−ng còng nh− víi SA, nã cã thÓ cÇn tÝnh to¸n chuyªn s©u cho c¸c m¹ng lín. 2.3.4 G¸n kªnh trong c¸c hÖ thèng W- CDMA §èi víi c¸c hÖ thèng W- CDMA, kü thuËt ®a truy nhËp ®−îc thiÕt kÕ ®Ó phï hîp víi m«i tr−êng nhiÒu xuyªn nhiÔu trong ®ã mçi kªnh tÇn sè ®−îc sö dông trªn mçi sector. Sù ph©n biÖt gi÷a c¸c tÝn hiÖu ®−êng xuèng vµ ®−êng lªn ®¹t ®−îc qua viÖc sö dông c¸c m· kh¸c nhau. ViÖc g¸n c¸c m· cho c¸c tÝn hiÖu kªnh ®−êng lªn vµ ®−êng xuèng ®−îc thùc hiÖn trong thêi gian thùc bëi phÇn cøng m¹ng v× c¸c ®−êng truyÒn gi÷a c¸c BS vµ c¸c MS lµ cÇn thiÕt cho liªn l¹c. V× lý do nµy, kÕ ho¹ch g¸n kªnh lµ kh«ng cÇn thiÕt. Tuy nhiªn, cã c¸c m· t¹p ©m gi¶ ngÉu nhiªn (PN) ®−îc sö dông ®Ó ph©n biÖt c¸c m· tr¶i sö dông trªn mét sector víi c¸c m· tr¶i trªn mét sector kh¸c. §«i khi, xung ®ét trong c¸c m· PN cã thÓ n¶y sinh ra t¹i c¸c vÞ trÝ trong vïng phôc vô mµ tû sè møc tÝn hiÖu vµ c¸c trÔ thêi gian gi÷a hai BS cã cïng mét xung ®ét m· PN. Ph−¬ng tr×nh liªn quan víi viÖc tÝnh to¸n c¸c vïng xung ®ét PN tiÒm tµng cho c¸c hÖ thèng IS - 95 CDMA cã thÓ t×m thÊy trong [29]. C¸c ph−¬ng ph¸p t−¬ng tù cã thÓ quy ho¹ch m· x¸o trén trong dÞch vô viÔn th«ng di ®éng toµn cÇu (UMTS) W - CDMA. C¸c ph−¬ng ph¸p m· x¸o trén W - CDMA kh¸c ®−îc th¶o luËn trong [17]. §èi víi TD - CDMA sö dông trong UTRA - TDD, cã kh¶ n¨ng cho xuyªn nhiÔu tõ sector ®Õn sector kh¸c vµ tõ MS ®Õn MS kh¸c, ®iÒu ®ã ®−îc chØ ra trong h×nh 2.7. Phô thuéc vµo viÖc ®ång bé khung gi÷a c¸c tÕ bµo l©n cËn vµ sù chØ ®Þnh c¸c khe thêi gian gi÷a ®−êng lªn vµ ®−êng xuèng, xuyªn nhiÔu gi÷a c¸c tÕ bµo cã thÓ xuÊt hiÖn víi UTRA - TDD, ®Æc biÖt khi ph©n bè l−u l−îng lµ kh«ng ®ång ®Òu cao. §iÒu nµy ®−îc xö lý c¬ b¶n b»ng sö dông c¸c DCA chø kh«ng ph¶i quy ho¹ch m¹ng. Sö dông DCA cho viÖc truy nhËp v« tuyÕn mÆt ®Êt UMTS (UTRA)TDD ®· ®−îc th¶o luËn trong môc 2.2.5. 2.4 Dung l−îng m¹ng tÕ bµo vµ c¸c ph−¬ng ph¸p n©ng cao dung l−îng Mét ph−¬ng ph¸p ®¸nh gi¸ dung l−îng m¹ng lµ tÝnh to¸n d÷ liÖu kh¶ dông bps/Hz cña ®é réng b¨ng tÇn trªn km2 cña vïng phôc vô. Trong vÝ dô trªn, 6 MHz b¨ng th«ng ®−îc dïng cho mçi sector phôc vô. NÕu hiÖu qu¶ cña ®iÒu chÕ vµ m· ho¸ lµ 3.2 bps/Hz, vÝ dô (tiªu biÓu lµ 16- QAM m· ho¸), vµ b¸n kÝnh phôc vô cña mçi tÕ bµo lµ 10 km (104 km2/sector), th× dung l−îng cì kho¶ng 183kbps/km2. B¸n kÝnh phôc vô cho hÖ thèng tÕ bµo ®−îc thiÕt lËp ®Ó ®¹t ®−îc ®é s½n sµng tuyÕn thÝch hîp víi c¸c møc c«ng suÊt sector tiªu biÓu. Tuy nhiªn, mÉu sö dông l¹i tÇn sè ®−îc dùa trªn tû sè gi÷a b¸n kÝnh phôc vô tÕ bµo R vµ kho¶ng c¸ch gi÷a c¸c tÕ bµo D. NÕu c«ng suÊt BS ®−îc gi¶m ®i, sao cho b¸n kÝnh phôc vô chØ lµ 5 km, vïng phôc vô sector gi¶m xuèng cßn 26.2 km2 vµ dung l−îng t¨ng lªn cì 733kbps/km2. TÊt nhiªn, viÖc c©n b»ng nhiÒu tÕ bµo vµ BS lµ cÇn thiÕt ®Ó bao phñ cïng mét vïng phôc vô, do vËy chi phÝ h¹ tÇng m¹ng t¨ng lªn mét c¸ch tû lÖ ®Ó ®¹t ®−îc dung l−îng cao h¬n. §é kh¶ dông dung l−îng sö dông mét trong c¸c chiÕn l−îc g¸n kªnh ®−îc miªu t¶ trong c¸c môc tr−íc bÞ h¹n chÕ bëi xuyªn nhiÔu gi÷a c¸c tÕ bµo quyÕt ®Þnh c¸c tÇn sè cã thÓ t¸i sö dông ë møc ®é nµo. ViÖc tiÕp cËn ®· sö dông ®Ó c¶i thiÖn t×nh huèng: (1) t×m c¸ch ®Ó khö hay lo¹i bá xuyªn nhiÔu trªn kªnh ®−îc chän, (2) ®èi víi SINR kªnh cho tr−íc, lµm thÝch nghi c¸c ph−¬ng ph¸p ®iÒu chÕ vµ m· ho¸ ®Ó ®¹t ®−îc tû lÖ lçi thÊp h¬n t¹i tèc ®é d÷ liÖu cao nhÊt cã thÓ. Mét vµi kü thuËt nµy sÏ ®−îc th¶o luËn trong c¸c môc sau. An ten thÝch nghi, ph¸t hiÖn ®ång thêi vµ thÝch nghi ®−êng truyÒn lµ ba c¸ch tiÕp cËn cã thÓ ®−îc sö dông ®Ó triÖt xuyªn nhiÔu. 2.4.1 An ten thÝch nghi NÕu anten thÝch nghi ®−îc sö dông ®Ó triÖt xuyªn nhiÔu, kho¶ng c¸ch tÕ bµo cho viÖc sö dông l¹i tÇn sè cã thÓ gi¶m ®i vµ dung l−îng cña m¹ng ®−îc t¨ng lªn. Sù triÖt xuyªn nhiÔu th«ng qua viÖc sö dông anten MS cã h−íng tÝnh cao trong c¸c m¹ng LOS lµ lý do c¨n b¶n dung l−îng cña c¸c m¹ng nµy lín h¬n c¸c hÖ thèng tÕ bµo. ¶nh h−ëng nµy cã thÓ ®−îc tÝnh mét c¸ch xÊp xØ bëi viÖc thõa nhËn tû sè môc tiªu ®−îc sö dông trong (2.11) ®Ó x¸c ®Þnh c¸c tÝn hiÖu sector nµo sÏ xung ®ét víi sector kh¸c bÞ gi¶m bëi mét l−îng ph¶n ¸nh kh¶ n¨ng cña anten triÖt xuyªn nhiÔu tõ c¸c tÕ bµo kh¸c. Khi t¨ng gi¸ trÞ triÖt nhiÔu nµy, viÖc sö dông l¹i tÇn sè cã thÓ xÕp chÆt h¬n vµ theo ®ã dung l−îng cña hÖ thèng ®−îc t¨ng lªn.VÝ dô, nÕu mét an ten thÝch nghi lµm gi¶m sù ®ãng gãp xuyªn nhiÔu ®−îc biÓu diÔn qua NI trong (2.11) bëi mét hÖ sè c¶i thiÖn anten thÝch nghi lµ α = 1/4 (khö xuyªn nhiÔu 6 dB), sù t¨ng dung l−îng tõ C ®Õn C’ lµ: NÕu sè mò suy gi¶m ®−êng truyÒn ë môc tr−íc ®−îc sö dông lµ n = 4.38, dung l−îng m¹ng ®−îc t¨ng lªn mét hÖ sè lµ 1.88. §èi víi c¸c gi¸ trÞ nhá h¬n n, nh− víi hÖ thèng LOS cã thÓ mong ®îi sù c¶i thiÖn lín h¬n, bëi giíi h¹n dung l−îng lµ phô thuéc nhiÒu vµo xuyªn nhiÔu khi tæn thÊt ®−êng truyÒn gi÷a m¸y thu vµ c¸c m¸y ph¸t xuyªn nhiÔu trong m¹ng lµ thÊp h¬n. KÕt qu¶ m« pháng trong [9] gåm cã ¶nh h−ëng cña viÖc t¹o chïm tia t¹i sector vµ sù triÖt xuyªn nhiÔu tõ mét anten thÝch nghi t¹i MS. Sö dông c¸c kü thuËt nµy, tû lÖ truyÒn l¹i gãi gi¶m xuèng mét c¸ch ®¸ng kÓ khi c¸c kü thuËt n©ng cao bæ sung nµy ®−îc sö dông, cho biÕt sù c¶i thiÖn vÒ QoS khi sö dông anten thÝch nghi. §iÒu nµy lµ hÖ qu¶ trùc tiÕp cña viÖc triÖt xuyªn nhiÔu. 2.4.2 Ph¸t hiÖn ®ång thêi Ph¸t hiÖn ®ång thêi ®−îc sö dông trong c¸c kªnh ®−êng lªn trong hÖ thèng CDMA. Trong vai trß nµy, nã cã kh¶ n¨ng triÖt tÊt c¶ c¸c xuyªn nhiÔu trong tÕ bµo vµ cã kh¶ n¨ng t¨ng dung l−îng bëi hÖ sè lµ 2.8. Nã còng gi¶m nhÑ t¶i thùc hiÖn ®iÒu khiÓn c«ng suÊt nhanh vµ chÝnh x¸c. Kh¸i niÖm ph¸t hiÖn ®ång thêi hay ph¸t hiÖn ®a ng−êi sö dông cã thÓ ®−îc sö dông réng r·i h¬n ®Ó triÖt xuyªn nhiÔu tõ mäi nguån bªn ngoµi nÕu ®· biÕt vÒ tÝn hiÖu xuyªn nhiÔu vµ th«ng tin tr¹ng th¸i kªnh (CSI) gi÷a m¸y xuyªn nhiÔu vµ m¸y thu n¹n nh©n (bÞ nhiÔu). ThËm chÝ viÖc lo¹i trõ xuyªn nhiÔu kh«ng ®Çy ®ñ còng cã thÓ cung cÊp ®é lîi dung l−îng tû lÖ víi møc ®é triÖt nhiÔu. HiÖn nay, UMTS TDD n CC /2 ' α= (2.14) W- CDMA lµ c«ng nghÖ duy nhÊt cã thÓ øng dông cho m¹ng b¨ng réng cè ®Þnh tÕ bµo bao gåm ph¸t hiÖn ®ång thêi lµ mét phÇn ®Æc ®iÓm kü thuËt cña nã. 2.4.3 ThÝch nghi ®−êng truyÒn ThÝch nghi ®−êng truyÒn (LA) lµ mét kü thuËt söa ®æi ®Æc ®iÓm cña tÝn hiÖu (®iÒu chÕ vµ m· ho¸), møc c«ng suÊt ph¸t, hay tham sè cña mét anten thÝch nghi (nÕu ®−îc sö dông), ®Ó duy tr× chÊt l−îng ®−êng truyÒn khi ®Æc tÝnh cña c¸c kªnh thay ®æi hay gi¶m ®i so víi c¸c ®iÒu kiÖn danh ®Þnh cña chóng. C¸c kü thuËt nh− thÕ cã thÓ ®−îc øng dông cho c¸c ®−êng truyÒn riªng biÖt ®¬n lÎ sao cho chóng cã thÓ ®¸p øng viÖc thay ®æi c¸c ®iÒu kiÖn m«i tr−êng ®−êng truyÒn nh− m−a mï, pha- ®inh ®a ®−êng... LA còng cã thÓ ®−îc øng dông cho c¸c ®−êng truyÒn trong c¸c m¹ng LOS vµ m¹ng tÕ bµo trong ®ã xuyªn nhiÔu lµ yÕu tè h¹n chÕ. §èi víi mét ®−êng truyÒn ®· cho trong m¹ng, LA cã thÓ cho phÐp CSI hiÖn thêi vµ SINR ®−îc khai th¸c ë møc ®é lín nhÊt. NÕu SINR cao ®· ®¹t ®−îc cho mét phÇn cña viÖc truyÒn dÉn, c¸ch thøc cã thÓ ®−îc thay ®æi ®Ó sö dông hiÖu qu¶ h¬n bé tÝn hiÖu ®iÒu chÕ cã sù chiÕm dông phæ tÇn thÊp h¬n. Kh¶ n¨ng nµy cã thÓ ®¹t ®−îc dung l−îng cao h¬n khi sö dông ®éc lËp DCA. 2.5 KÕt luËn G¸n kªnh lµ mét qu¸ tr×nh lùa chän c¸ch sö dông tèt nhÊt nguån tµi nguyªn m¹ng v« tuyÕn ë d¹ng tÇn sè, c¸c khe thêi gian, vµ m· ho¸ ®Ó mang l−u l−îng d÷ liÖu gi÷a c¸c nót m¹ng. Trong khi phÇn cøng cña m¹ng (c¸c m¸y ph¸t, c¸c m¸y thu, c¸c anten...) lµ c«ng nghÖ cã thÓ, gi¸ trÞ th«ng tin thªm vµo m¹ng xuÊt ph¸t tõ viÖc sö dông hiÖu qu¶ nguån tµi nguyªn th«ng qua c¸c chiÕn l−îc g¸n kªnh th«ng minh vµ linh ho¹t. §èi víi c¸c hÖ thèng LOS sö dông c¸c anten t¨ng Ých cao cè ®Þnh t¹i MS vµ c¸c møc ®é hîp lý cña viÖc sector ho¸ t¹i c¸c BS víi sù ph©n cùc lu©n phiªn, cã thÓ ®¹t ®−îc hÖ sè sö dông l¹i tÇn sè b»ng mét (mçi tÇn sè cã thÓ ®−îc sö dông trªn mét sector). Anten thÝch nghi sö dông trong c¸c hÖ thèng LOS cã thÓ c¶i thiÖn ®é dù tr÷ ®−êng truyÒn b»ng c¸ch ®Þnh h−íng ®é khuÕch ®¹i tíi c¸c MS liªn l¹c vµ cung cÊp sù linh ho¹t ®Ó ®Þnh h×nh l¹i m¹ng khi cã thªm ng−êi dïng vµ BS. C¸c hÖ thèng tÕ bµo cã thÓ dïng c¸c chiÕn l−îc g¸n kªnh, nh− ph−¬ng ph¸p FCA vµ DCA sö dông nguån tµi nguyªn m¹ng ®Ó mang l−u l−îng ®Õn ®Þa ®iÓm vµ thêi gian nã cÇn. Vµi ph−¬ng ph¸p DCA ®· ®−îc ®Ò xuÊt víi sù tho¶ hiÖp chÊt l−îng kh¸c nhau chñ yÕu lµ víi c¸c hÖ thèng chuyÓn m¹ch- kªnh. §èi víi c¸c m¹ng sè liÖu chuyÓn m¹ch gãi hiÖn t¹i vµ t−¬ng lai, DPA cã thÓ ®¹t ®−îc viÖc sö dông phæ tÇn rÊt hiÖu qu¶ trªn c¬ së viÖc m« pháng míi. V× dung l−îng m¹ng v« tuyÕn mËt ®é cao bÞ h¹n chÕ bëi xuyªn nhiÔu, dung l−îng ®¹t ®−îc víi chiÕn l−îc g¸n kªnh bÊt kú cã thÓ ®−îc t¨ng lªn th«ng qua nhiÒu ph−¬ng ph¸p triÖt xuyªn nhiÔu. Anten thÝch nghi, ph¸t hiÖn ®ång thêi, thÝch nghi ®−êng truyÒn lµ c¸c ph−¬ng ph¸p triÖt xuyªn nhiÔu vµ c¶i thiÖn chÊt l−îng ®−êng truyÒn riªng lÎ trong sù gi¶m cÊp t¹m thêi do pha-®inh hay c¸c côm xuyªn nhiÔu. ChiÕn l−îc g¸n kªnh thùc chÊt lµ mét phÇn cña môc tiªu lín h¬n lµ t¹o vµ qu¶n lý phæ tÇn v« tuyÕn nh− thÕ nµo. Trªn thùc tÕ, nguån phæ tÇn tù nhiªn lµ h¹n chÕ, phæ tÇn kh¶ dông chØ bÞ h¹n chÕ bëi tr¹ng th¸i hiÖn thêi cña c«ng nghÖ ®−îc øng dông vµ c¸c ph−¬ng ph¸p cho viÖc sö dông nã. Khi c«ng nghÖ ph¸t triÓn vµ mËt ®é cña c¸c ®iÓm truy nhËp v« tuyÕn cè ®Þnh ®· triÓn khai t¨ng c−êng, phæ tÇn míi ®−îc t¹o ra. §©y lµ quan ®iÓm chÝnh x¸c vµ cã tÝnh x©y dùng h¬n vÒ viÖc phæ tÇn ®−îc ph¸t triÓn vµ sö dông nh− thÕ nµo so víi quan ®iÓm mµ c¸c nhµ qu¶n lý sö dông ®èi víi tµi nguyªn phæ tÇn hiÖn thêi. Ch−¬ng 3 Tèi −u ho¸ g¸n kªnh cè ®Þnh trong m¹ng di ®éng tÕ bµo ViÖc tèi −u ho¸ g¸n kªnh cè ®Þnh trong m¹ng di ®éng tÕ bµo lµ bµi to¸n tèi −u NP. §èi víi m¹ng bÊt kú cã kÝch th−íc hîp lý chØ cã thÓ nhËn ®−îc c¸c gi¶i ph¸p gåm tèi −u b»ng c¸c thuËt to¸n kinh nghiÖm. Trong ch−¬ng nµy s¸u thuËt to¸n g¸n kªnh ®−îc xem xÐt vµ ®−îc ®¸nh gi¸. §ã lµ tæ hîp cña ba chiÕn l−îc g¸n kªnh vµ hai ph−¬ng ph¸p xÕp thø tù tÕ bµo. KÕt qu¶ mµ chóng ta t×m thÊy lµ (i) thø tù mµu nót cña tÕ bµo lµ ph−¬ng ph¸p xÕp thø tù hiÖu qu¶ h¬n thø tù cÊp ®é nót; (ii) chiÕn l−îc vÐt c¹n tÇn sè lµ phï hîp h¬n cho hÖ thèng víi l−u l−îng ®−îc ph©n bè cã tÝnh ®ång ®Òu kh«ng cao; vµ (iii) kÕt hîp tÇn sè vµ chiÕn l−îc vÐt c¹n yªu cÇu víi viÖc thø tù l¹i mµu nót lµ thuËt to¸n hiÖu qu¶ nhÊt. Ph¹m vi tÇn sè ®¹t ®−îc qua viÖc sö dông thuËt to¸n ®· ®Ò xuÊt lµ thÊp h¬n, ®iÒu ®ã ®−îc tr×nh bµy trong ch−¬ng nµy vµ trong nhiÒu tr−êng hîp lµ b×nh ®¼ng cho c¸c cËn d−íi cã tÝnh lý thuyÕt. 3.1 Giíi thiÖu VÊn ®Ò g¸n mét tËp kªnh cho mçi tÕ bµo sao cho hiÖu qu¶ nhÊt vÒ phæ ®−îc gäi lµ vÊn ®Ò g¸n kªnh. G¸n kªnh lµ ®iÒu rÊt quan träng trong quy ho¹ch m¹ng di ®éng tÕ bµo bëi viÖc g¸n kªnh hiÖu qu¶ sÏ t¹o ra hiÖu qu¶ sö dông phæ tÇn cã s½n [6], [12], [13]. Tuy nhiªn, vÊn ®Ò g¸n kªnh l¹i thuéc vµo líp c¸c bµi to¸n tèi −u tæ hîp [15]. Nãi chung, ®èi víi c¸c m¹ng di ®éng cã kÝch th−íc hîp lý viÖc gi¶i quyÕt bµi to¸n nµy gÇn nh− lµ kh«ng thÓ. Mét sè c¸ch tiÕp cËn cã tÝnh thùc tÕ ®èi víi vÊn ®Ò nµy ®−îc ®−a ra trong s¸ch b¸o. §ã lµ viÖc sö dông c¸ch tiÕp cËn mang tÝnh lý thuyÕt cña graph truyÒn thèng [26]; c¸ch tiÕp cËn b»ng kü thuËt ñ m« pháng [11], c¸ch tiÕp cËn m¹ng n¬ron. Mçi c¸ch tiÕp cËn ®· ®−a ra ®Òu cã nh÷ng ®iÓm h¹n chÕ riªng. C¸ch tiÕp cËn m¹ng n¬ron [18], [19] tá ra kh«ng thÝch hîp cho viÖc g¸n kªnh trong v× nã t¹o ra nh÷ng gi¶i ph¸p nghÌo nµn, ngay c¶ trong c¸c tr−êng hîp ®¬n gi¶n. ViÖc sö dông kü thuËt ñ m« pháng [11] cã thÓ tr¸nh ®−îc c¸c gi¶i ph¸p tèi thiÓu côc bé nh−ng chi phÝ thêi gian ho¹t ®éng lµ tèn kÐm. MÆt kh¸c, chÊt l−îng gi¶i ph¸p lµ rÊt khã kiÓm so¸t. ViÖc nghiªn cøu tiÕp theo h−íng nµy lµ cÇn thiÕt. H−íng tiÕp cËn theo lý thuyÕt graph ®· ®−îc nghiªn cøu mét c¸ch réng r·i vµ cã rÊt nhiÒu kÕt qu¶ nghiªn cøu ®· ®−îc b¸o c¸o. Sau ®©y, nh÷ng kÕt qu¶ quan träng nhÊt sÏ ®−îc tæng kÕt. Dùa trªn kinh nghiÖm cña viÖc g¸n kªnh tr−íc tiªn cho tÕ bµo cã ®é khã g¸n cao nhÊt. Trong [6] ®· ®Ò xuÊt mét thuËt to¸n lÆp víi mét nhãm ban ®Çu cña c¸c con sè ®−îc t¹o ra mét c¸ch ngÉu nhiªn ®Ó biÓu diÔn nh÷ng khã kh¨n trong viÖc g¸n kªnh cña c¸c tÕ bµo riªng lÎ. ThuËt to¸n nµy cã mét tèc ®é héi tô chËm vµ thêi gian cho viÖc ch¹y thö cao ®Æc biÖt khi kÝch th−íc hÖ thèng lín. Trong [12] chØ tiªu theo kinh nghiÖm vÒ ®é khã g¸n kªnh ®· ®−îc ®Ò xuÊt vµ c¸c tÕ bµo ®−îc s¾p xÕp thµnh danh s¸ch theo thø tù mµu nót hoÆc thø tù cÊp ®é nót. Dùa trªn danh s¸ch ®ã, c¸c kªnh ®· ®−îc g¸n bëi hoÆc chiÕn l−îc vÐt c¹n tÇn sè (F) hay chiÕn l−îc vÐt c¹n yªu cÇu (R). TiÕp theo, trong [26], chØ tiªu kinh nghiÖm c¶i tiÕn vÒ ®é khã kh¨n trong viÖc g¸n kªnh ®· ®−îc ®Ò cËp vµ ph−¬ng ph¸p s¾p xÕp tÕ bµo míi ®−îc gäi lµ s¾p xÕp tÕ bµo theo cét ®· ®−îc giíi thiÖu. Ng−êi ta chøng minh r»ng c¸c thuËt to¸n ®· ®Ò xuÊt trong [26] cho chÊt l−îng tèt nhÊt so víi tÊt c¶ thuËt to¸n hiÖn cã trªn c¸c vÝ dô thö nghiÖm 21 tÕ bµo. V× thuËt to¸n kinh nghiÖm kh«ng ®−a ra th«ng tin vÒ chÊt l−îng cña gi¶i ph¸p, c¸c cËn d−íi trong vÊn ®Ò g¸n kªnh ®· nhËn ®−îc trong [13] b»ng xem xÐt m¹ng nhá ®−îc t¸ch riªng ra khái hÖ thèng nguyªn thuû. GÇn ®©y, cËn d−íi chÆt h¬n trong mét sè ®iÒu kiÖn nhÊt ®Þnh ®· ®−îc ®−a ra ë [27], [28]. Hai thuËt to¸n dùa trªn viÖc tiÕp cËn t« mµu graph còng ®· ®−îc ®Ò xuÊt. Trong ch−¬ng nµy, chóng ta quan t©m tíi ý t−ëng c¬ b¶n cña viÖc s¾p xÕp c¸c tÕ bµo thµnh danh s¸ch cã thø tù, sau ®ã thùc hiÖn g¸n kªnh. Kh«ng gièng c¸ch tiÕp cËn th«ng th−êng, c¸c tÕ bµo ®−îc s¾p xÕp l¹i sau mçi g¸n kªnh theo ®é phøc t¹p s¾p xÕp ®−îc chØnh söa cña chóng. Tæng céng cã 6 thuËt to¸n g¸n kªnh míi, cô thÓ lµ c¸c thuËt to¸n F/CR, F/DR, R/CR, R/DR, FR/CR vµ FR/DR ®· ®−îc ®Ò xuÊt. HiÖu qu¶ cña c¸c thuËt to¸n nµy ®· ®−îc nghiªn cøu vµ so s¸nh víi c¸c kÕt qu¶ ®· ®−îc xem xÐt ë phÇn tr−íc còng nh− cËn d−íi lý thuyÕt còng ®−îc ®¸nh gi¸. Chóng ta nhËn thÊy r»ng (i) thø tù mµu nót lµ mét ph−¬ng ph¸p s¾p xÕp cã hiÖu qu¶ h¬n lµ thø tù cÊp ®é nót; (ii) chiÕn l−îc vÐt c¹n tÇn sè thÝch hîp h¬n cho c¸c hÖ thèng víi l−u l−îng ®−îc ph©n bè cã tÝnh ®ång ®Òu kh«ng cao, vµ chiÕn l−îc vÐt c¹n yªu cÇu lµ phï hîp h¬n cho hÖ thèng víi l−u l−îng ®−îc ph©n bè ®ång ®Òu h¬n vµ (iii) chiÕn l−îc FR víi thø tù l¹i mµu nót hay lµ c¸c thuËt to¸n FR/CR lµ thuËt to¸n hiÖu qu¶ nhÊt. Ph¹m vi tÇn sè t×m ®−îc b»ng c¸c thuËt to¸n cña chóng ta lµ nhá h¬n ®¸ng kÓ ph¹m vi t×m ®−îc bëi c¸c thuËt to¸n trong [26] vµ b»ng hoÆc rÊt gÇn c¸c cËn d−íi lý thuyÕt. Trong môc sau, vÊn ®Ò g¸n kªnh sÏ ®−îc tr×nh bµy chi tiÕt vµ môc ®Ých cña chóng ta sÏ ®−îc lµm râ. Trong môc 3.3, chóng ta nh×n l¹i vµi kinh nghiÖm c¬ b¶n trong viÖc g¸n kªnh. Trong môc 3.4 c¸c thuËt to¸n F/CR, F/DR, R/CR, R/DR sÏ ®−îc tr×nh bµy. ChiÕn l−îc FR lµ sù kÕt hîp gi÷a chiÕn l−îc vÐt c¹n yªu cÇu vµ chiÕn l−îc vÐt c¹n tÇn sè, sau ®ã sÏ ®−îc nghiªn cøu trong môc 3.5. Trong môc 3.6, chÊt l−îng 6 thuËt to¸n g¸n kªnh ®−îc ®Ò xuÊt sÏ ®−îc ®¸nh gi¸ vµ so s¸nh víi c¸c thuËt to¸n ®· ®−îc ®Ò cËp trong [26]. Cuèi cïng, kÕt luËn sÏ ®−îc rót ra ë môc 3.7. 3.2 X©y dùng bµi to¸n Ba ®iÒu kiÖn b¾t buéc th−êng xuyªn ®−îc l−u ý trong vÊn ®Ò g¸n kªnh: - H¹n chÕ xuyªn nhiÔu ®ång kªnh: mét kªnh ®−îc g¸n cho mét tÕ bµo kh«ng thÓ t¸i sö dông trong c¸c tÕ bµo l©n cËn. Nh÷ng tÕ bµo nµy n»m trong ph¹m vi xuyªn nhiÔu ®ång kªnh. - H¹n chÕ xuyªn nhiÔu kªnh l©n cËn: c¸c kªnh ®−îc g¸n cho c¸c tÕ bµo l©n cËn ph¶i duy tr× mét sù ph©n c¸ch cùc tiÓu lµ a kªnh. - H¹n chÕ xuyªn nhiÔu kªnh cïng tÕ bµo: c¸c kªnh ®−îc g¸n cho cïng mét tÕ bµo ph¶i duy tr× sù ph©n c¸ch cùc tiÓu lµ s kªnh. Víi hÖ thèng tÕ bµo N tÕ bµo vµ ma trËn t−¬ng thÝch kªnh N x N, C = [cij] cã thÓ ®−îc sö dông ®Ó biÓu diÔn 3 lo¹i rµng buéc, cij biÓu thÞ cña sù ph©n c¸ch kªnh tèi thiÓu gi÷a c¸c kªnh ®−îc g¸n cho tÕ bµo i vµ tÕ bµo j. RÊt dÔ nhËn thÊy r»ng cij= 0 cã nghÜa lµ mét kªnh ®−îc g¸n cho tÕ bµo i cã thÓ ®−îc t¸i sö dông t¹i tÕ bµo j. cij = s cã nghÜa lµ h¹n chÕ xuyªn nhiÔu kªnh cïng tr¹m lµ s kªnh. cij = a cã nghÜa lµ h¹n chÕ xuyªn nhiÔu kªnh l©n cËn b»ng a kªnh. Trªn thùc tÕ, ma trËn t−¬ng thÝch th−êng nhËn ®−îc b»ng viÖc ®o hÖ thèng thùc kh«ng cã mét cÊu tróc lôc gi¸c ®Òu lý t−ëng. ? H×nh 3.1 G¸n kªnh cè ®Þnh trong hÖ thèng di ®éng tÕ bµo Gi¶ sö vector M = (m1, m2… mN) biÓu thÞ c¸c yªu cÇu kªnh cña m¹ng N tÕ bµo. Gi¶ sö mét tæ hîp kªnh tÇn sè ®−îc xÕp h¹ng bëi mét tËp sè nguyªn d−¬ng {1, Kªnh 1 2 3 4 5 x Mhz y Mhz Phæ tÇn 2, 3…} theo tÇn sè sãng mang cña chóng (h×nh 3.1). Gi¶ sö fik lµ kªnh ®−îc g¸n cho cuéc gäi thø k trong tÕ bµo i. ViÖc g¸n kªnh cã thÓ nhËn ®−îc trong [12] lµ sù tËp hîp cña c¸c sè nguyªn F = (fik), víi i = 1, 2, …, N vµ k = 1, 2,… mi, sao cho: |fik - fjl| ≥ cij víi mäi i, j, k vµ l (ngo¹i trõ i = j vµ k = l). Mét thuËt to¸n g¸n kªnh hiÖu qu¶ sÏ cho g¸n kªnh F* víi N(F*) = max i, k, fik cµng nhá cµng tèt. N(F *) ®−îc hiÓu nh− lµ ph¹m vi tÇn sè cña viÖc g¸n kªnh. Tèc ®é l−u l−îng trong mét m¹ng tÕ bµo biÕn ®æi tõ tÕ bµo nµy tíi tÕ bµo kh¸c. C¸c vïng víi tû lÖ l−u l−îng cao h¬n ®¸ng kÓ ®−îc gäi lµ ®iÓm nãng. Th«ng th−êng, mét ®iÓm nãng bao gåm mét vµi tÕ bµo g©y xuyªn nhiÔu víi mçi tÕ bµo cã mét ®ßi hái kªnh cao. C¸c tÕ bµo bªn trong ®iÓm nãng ®−îc gäi lµ c¸c tÕ bµo ®iÓm nãng. Ph¹m vi tÇn sè cña hÖ thèng th−êng quyÕt ®Þnh ®−îc bëi ph¹m vi ®iÓm nãng “nãng nhÊt”. Ph¹m vi ®iÓm nãng phô thuéc vµo kªnh ®−îc g¸n cho c¸c tÕ bµo ®iÓm nãng cña nã nh− thÕ nµo. Nãi c¸ch kh¸c, nÕu c¸c kªnh ®−îc g¸n cho c¸c tÕ bµo ®iÓm nãng (thuéc cïng ®iÓm nãng) ®−îc ®ãng gãi mét c¸ch hiÖu qu¶, mét ph¹m vi tÇn sè nhá cho tÊt c¶ c¸c hÖ thèng còng cã thÓ ®¹t ®−îc. Do ®ã, thuËt to¸n g¸n kªnh hiÖu qu¶ sÏ tËp trung vµo viÖc tho¶ m·n nh÷ng yªu cÇu cña mçi nhãm tÕ bµo ®iÓm nãng. NhiÒu nghiªn cøu tr−íc ®ã [12], [26], [30] tËp trung tr−íc tiªn vµo viÖc g¸n kªnh cho tÕ bµo cã ®é khã g¸n kªnh cao nhÊt. C¸c chØ tiªu kinh nghiÖm vÒ nh÷ng khã kh¨n trong viÖc g¸n kªnh ®· ®−îc x¸c ®Þnh vµ sau ®ã c¸c tÕ bµo ®· ®−îc s¾p xÕp vµo mét danh s¸ch. C¸c kªnh ®−îc g¸n dùa trªn danh s¸ch. Chóng ta t×m ra hai vÊn ®Ò ®èi víi viÖc tiÕp cËn nµy. VÊn ®Ò ®Çu tiªn liªn quan ®Õn trËt tù cña tÕ bµo. Khi c¸c kªnh ®−îc g¸n cho tÕ bµo, ®é khã cña s¾p xÕp tÕ bµo riªng lÎ thay ®æi. Do ®ã cÇn s¾p xÕp l¹i c¸c tÕ bµo sau mçi lÇn g¸n kªnh. VÊn ®Ò thø hai lµ trong c¸ch tiÕp cËn nµy chØ tËp trung vµo viÖc g¸n kªnh cho c¸c tÕ bµo cã ®é khã g¸n kªnh cao nhÊt. Cã thÓ kh«ng nhËn d¹ng ®−îc c¸c khu vùc ®iÓm nãng vµ bëi vËy cã thÓ dÉn ®Õn viÖc chØ ®Þnh kªnh kh«ng hiÖu qu¶ khi mµ c¸c tÕ bµo liªn tiÕp trong danh s¸ch ®· ®−îc s¾p xÕp kh«ng thuéc cïng mét ®iÓm nãng. 3.3 Nh÷ng quy t¾c kinh nghiÖm c¬ b¶n 3.3.1 Hai ph−¬ng ph¸p s¾p xÕp tÕ bµo Gäi di lµ mét sè ®o ®é khã g¸n kªnh cho tÕ bµo i. Trong [26], di ®−îc ®Þnh nghÜa: nÕu mi ≠ 0; ngoµi ra, di = 0. V× sè h¹ng cii ë vÕ ph¶i cña ph−¬ng tr×nh (3.1) lµ nh− nhau ®èi víi tÊt c¶ c¸c tÕ bµo, ta cã thÓ bá nã ®Ó cã d¹ng ®¬n gi¶n h¬n: Sö dông thø tù cÊp ®é nót [30], c¸c tÕ bµo ®−îc s¾p xÕp theo trËt tù gi¶m dÇn gi¸ trÞ di. Bëi vËy, tÕ bµo ®Çu tiªn cã −u tiªn cao nhÊt cho viÖc ®¹t ®−îc mét kªnh ®Çu tiªn. Sö dông thø tù mµu nót [30], c¸c tÕ bµo ®Çu tiªn ®−îc s¾p xÕp bëi thø tù cÊp ®é nót. TÕ bµo cuèi cïng trong danh s¸ch ®−îc di chuyÓn ®Õn danh s¸ch rçng vÝ dô danh s¸ch A. BËc cña (N-1) tÕ bµo cßn l¹i ®−îc tÝnh to¸n l¹i víi yªu cÇu kªnh cña tÕ bµo cuèi cïng bÞ lo¹i trõ. (N-1) tÕ bµo cßn l¹i sau ®ã ®−îc thø tù l¹i bëi cÊp ®é nót cña chóng ®· ®−îc söa. Sau ®ã, di chuyÓn tÕ bµo cuèi cïng trong danh s¸ch rót gän ®Õn danh s¸ch A vµ ®Æt nã ngay tr−íc c¸c tÕ bµo ®· liÖt kª. Thñ tôc nµy tiÕp tôc cho ®Õn khi tÊt c¶ N tÕ bµo ®−îc di chuyÓn ®Õn danh s¸ch A. §iÒu nµy ®−îc biÕt ®Õn nh− lµ thø tù mµu nót. Hai ph−¬ng ph¸p s¾p xÕp tÕ bµo ë trªn ®· ®−îc sö dông réng r·i khi thiÕt kÕ c¸c thuËt to¸n kinh nghiÖm. Tuy nhiªn ch−a biÕt râ ph−¬ng Niccmd N j iiijji ≤≤−= ∑ = 1 1 (3.1) Nicmd N j ijji ≤≤= ∑ = 1 1 (3.2) ph¸p nµo cã chÊt l−îng tèt h¬n. Trong môc 3.6, hiÖu qu¶ cña hai ph−¬ng ph¸p s¾p xÕp tÕ bµo sÏ ®−îc nghiªn cøu. 3.3.2 Hai chiÕn l−îc g¸n kªnh Cho danh s¸ch theo thø tù cña c¸c tÕ bµo (®· nhËn ®−îc bëi thø tù cÊp ®é nót hoÆc thø tù mµu nót), hai chiÕn l−îc g¸n kªnh: ChiÕn l−îc vÐt c¹n tÇn sè (F) vµ chiÕn l−îc vÐt c¹n yªu cÇu (R) [30] cã thÓ sö dông ®Ó s¾p xÕp c¸c kªnh cho c¸c tÕ bµo. Trong chiÕn l−îc vÐt c¹n tÇn sè, b¾t ®Çu víi tÕ bµo ®Çu tiªn trong trËt tù danh s¸ch, mçi tÕ bµo víi yªu cÇu kªnh kh«ng phï hîp nµo ®ã ®−îc g¸n mét kªnh víi h¹ng thÊp nhÊt (tÊt c¶ c¸c kªnh ®−îc xÕp h¹ng theo c¸c tÇn sè sãng mang cña chóng) vµ phï hîp víi tÊt c¶ viÖc g¸n kªnh tr−íc. Trong chiÕn l−îc vÐt c¹n yªu cÇu, kªnh 1 ®−îc g¸n cho tÕ bµo ®Çu tiªn trong trËt tù danh s¸ch víi yªu cÇu kªnh kh«ng phï hîp nµo ®ã. Sau ®ã thö kªnh nh− vËy cho tÕ bµo kÕ tiÕp trong danh s¸ch cã yªu cÇu kªnh kh«ng phï hîp. TiÕp tôc viÖc thö nµy cho ®Õn khi kªnh nµy kh«ng thÓ ®−îc chÊp nhËn bëi tÕ bµo nµo n÷a. TiÕp sau ®ã lµm thñ tôc t−¬ng tù ®Ó g¸n kªnh 2. LÆp l¹i thñ tôc nµy cho ®Õn khi tÊt c¶ yªu cÇu kªnh ®−îc tho¶ m·n (®−îc vÐt c¹n). 3.4 G¸n kªnh víi viÖc s¾p xÕp l¹i tÕ bµo 3.4.1 Bèn thuËt to¸n g¸n kªnh Môc ®Ých cña s¾p xÕp c¸c tÕ bµo lµ nhËn d¹ng c¸c tÕ bµo khã g¸n kªnh nhÊt. Khi c¸c kªnh ®−îc g¸n cho tÕ bµo, yªu cÇu kªnh cña tÕ bµo gi¶m ®i vµ ®é khã g¸n kªnh cña nã còng nh− cña c¸c tÕ bµo l©n cËn nã còng gi¶m. §Ó ph¶n ¸nh thùc chÊt ®é khã viÖc g¸n kªnh tøc thêi, danh s¸ch s¾p xÕp nªn ®−îc s¾p xÕp l¹i tr−íc khi g¸n kªnh kÕ tiÕp. Dùa trªn hai nguyªn lý s¾p xÕp tÕ bµo c¬ b¶n, 2 ph−¬ng ph¸p s¾p xÕp l¹i tÕ bµo, cô thÓ lµ s¾p xÕp l¹i mµu nót (CR) vµ s¾p xÕp l¹i cÊp ®é nót (DR) ®−îc thiÕt kÕ. KÕt hîp mçi ph−¬ng ph¸p nµy víi chiÕn l−îc vÐt c¹n tÇn sè vµ chiÕn l−îc vÐt c¹n yªu cÇu, ta cã bèn thuËt to¸n cô thÓ lµ F/CR, F/DR, R/CR vµ R/DR. Chóng ®−îc miªu t¶ theo m· gi¶ ngÉu nhiªn. * ThuËt to¸n F/CR hay F/DR Input: C = [ cij] vµ M = (m1, m2, …, mN) Output: N(F*) 1. For i = 1 to N do m’i = mi; 2. For i = 1 to N do if m’i = 0, di = 0 else di = ∑Nj=1 m’j cij ; 3. S¾p xÕp tÕ bµo thµnh danh s¸ch cã trËt tù sö dông thø tù mµu nót hay thø tù cÊp ®é nót; 4. NÕu bËc cña tÕ bµo ®Çu tiªn trong danh s¸ch di ≠ 0 t×m kªnh g víi h¹ng thÊp nhÊt sao cho viÖc g¸n kªnh g cho tÕ bµo i lµ phï hîp víi tÊt c¶ viÖc g¸n kªnh tr−íc. m’i = m’i – 1 , k = mi – m’i vµ fik = g; nh¶y ®Õn b−íc 2; 5. Ng−îc l¹i N(F*) = maxi,kfik vµ EXIT; * ThuËt to¸n R/CR hay R/DR Input: C = [ cij] vµ M = (m1, m2, …, mN) Output: N(F*) 1. For i = 1 to N do m’i = mi; 2. f = 1; 3. For i = 1 to N do if m’i = 0, di = 0 else di = ∑Nj=1 m’j cij ; 4. S¾p xÕp c¸c tÕ bµo thµnh danh s¸ch thø tù sö dông ph−¬ng ph¸p thø tù mµu nót hay ph−¬ng ph¸p thø tù cÊp ®é nót. 5. T×m i tÕ bµo thø nhÊt trong danh s¸ch sao cho g¸n kªnh f cho tÕ bµo i lµ phï hîp víi tÊt c¶ viÖc g¸n tr−íc. 6. NÕu tÕ bµo i t×m ®−îc nÕu di ≠ 0 m’i = m’i – 1, k = mi – m’i vµ fik = f; nh¶y ®Õn b−íc 3; ng−îc l¹i N(F*) = maxi,kfik vµ EXIT; 7. Ng−îc l¹i f = f + 1; nh¶y ®Õn b−íc 4. 3.4.2 §é phøc t¹p Gi¶ sö tæng sè yªu cÇu kªnh lµ M = ∑Ni=1 mi. Víi c¸c thuËt to¸n F/CR hay F/DR, b−íc 2 bao gåm N thao t¸c cho viÖc t×m di. Gi¶ thiÕt sù ph©n lo¹i ¶o ®−îc sö dông, sè thao t¸c trong b−íc 3 ®èi víi s¾p xÕp mµu nót lµ O(N3) vµ cho s¾p xÕp cÊp ®é nót lµ O(N2). B−íc 2 ®Õn 4 t¹o thµnh mét chu tr×nh vµ sÏ thùc hiÖn M lÇn. Tæng sè sù so s¸nh cho thùc hiÖn M lÇn cña b−íc 4 lµ 1+2+…+M-1, hay O(M2). Do ®ã, sù phøc t¹p thêi gian toµn bé cña thuËt to¸n F/CR lµ MO(N3) + O(M2) = O(MN3+M2). Sù phøc t¹p thêi gian toµn bé cña thuËt to¸n F/DR lµ O(MN2 + M2). Víi c¸c thuËt to¸n R/CR hay R/DR, b−íc 3 ®Õn 7 thùc hiÖn M lÇn ®Ó g¸n M kªnh. T−¬ng tù víi thuËt to¸n F/CR vµ F/DR, sù phøc t¹p thêi gian cña b−íc 4 lµ O(N3) nÕu thø tù mµu nót ®−îc sö dông vµ O(N2) nÕu thø tù cÊp ®é nót ®−îc sö dông. Tæng sè sù so s¸nh cho thùc hiÖn M lÇn cña b−íc 5 lµ O(M2). Sù phøc t¹p thêi gian tæng céng t×m ®−îc lµ O(MN3+M2) cho R/CR vµ O(MN2+M2) cho R/DR. 3.4.3 VÝ dô §Ó chøng minh cho hiÖu qu¶ sö dông s¾p xÕp l¹i tÕ bµo, xem xÐt hÖ thèng 3 tÕ bµo ®¬n gi¶n chØ ra trong h×nh 3.2(a). TÕ bµo A, B vµ C cã yªu cÇu kªnh 4, 3 vµ 1 t−¬ng øng. Gi¶ sö h¹n chÕ xuyªn nhiÔu kªnh l©n cËn vµ h¹n chÕ xuyªn nhiÔu kªnh cïng tr¹m lµ a = 2 vµ s = 3. BËc cña c¸c tÕ bµo A, B vµ C ®−îc t×m thÊy lµ 20, 19 vµ 14 tõ ph−¬ng tr×nh (3.2). Víi vÝ dô cô thÓ nµy, ®iÒu ®ã chøng tá r»ng 4 thuËt to¸n ®· ®Ò xuÊt trong phÇn tr−íc thùc hiÖn nh− nhau. Do ®ã, ®Ó thuËn tiÖn chóng ta sÏ sö dông “s¾p xÕp l¹i tÕ bµo” vµ “kh«ng s¾p xÕp l¹i tÕ bµo” ®Ó ph©n biÖt hai lo¹i g¸n kªnh nµy. 4 3 1 A B C (a) HÖ thèng 3 tÕ bµo A, B, C Thø tù 1 2 3 4 5 6 7 8 A A A A B B B C TÕ bµo Kªnh 1 3 5 7 9 11 13 15 17 19 21 Ph¹m vi (b) Kh«ng s¾p xÕp l¹i tÕ bµo Thø tù 1 2 3 4 5 6 7 8 A A B B A A B C TÕ bµo Kªnh 1 3 5 7 9 11 13 15 17 19 21 Ph¹m vi (c) Cã s¾p xÕp l¹i tÕ bµo vµ ph−¬ng ph¸p quyÕt ®Þnh thø nhÊt Thø tù 1 2 3 4 5 6 7 8 A B A B A C B A TÕ bµo Kªnh 1 3 5 7 9 11 13 15 17 19 21 Ph¹m vi (d) Cã s¾p xÕp l¹i tÕ bµo vµ ph−¬ng ph¸p quyÕt ®Þnh thø hai H×nh 3.2 KÕ ho¹ch g¸n kªnh cho hÖ thèng 3 tÕ bµo §èi víi viÖc g¸n kªnh kh«ng s¾p xÕp l¹i, danh s¸ch tÕ bµo ®· ®−îc s¾p xÕp ban ®Çu (A, B, C) ®−îc sö dông cho ®Õn khi tÊt c¶ c¸c yªu cÇu kªnh ®−îc tho¶ m·n. KÕt qu¶ kÕ ho¹ch g¸n kªnh ®−îc chØ ra trong h×nh 3.2(b). TrËt tù g¸n kªnh còng ®−îc chØ ra trong h×nh. Ph¹m vi tÇn sè ®−îc t×m thÊy lµ 20. Khi viÖc g¸n kªnh víi s¾p xÕp l¹i tÕ bµo ®−îc sö dông, danh s¸ch ®· ®−îc s¾p xÕp l¹i cña tÕ bµo ®−îc cËp nhËt mçi khi 1 kªnh ®−îc g¸n. Trong tr−êng hîp cã h¬n 1 tÕ bµo cã cïng ®é khã g¸n kªnh, 2 ph−¬ng ph¸p quyÕt ®Þnh ®−îc sö dông: (1) Lùa chän tÕ bµo mµ mét kªnh ®−îc g¸n sím nhÊt hoÆc (2) ng−îc l¹i. (Chó ý r»ng bÊt kú ph−¬ng ph¸p quyÕt ®Þnh nµo còng cã thÓ ®−îc sö dông). Khi sö dông ph−¬ng ph¸p quyÕt ®Þnh thø nhÊt, kÕt qu¶ kÕ ho¹ch g¸n kªnh ®−îc chØ ra trong h×nh 3.2(c) vµ chuçi danh s¸ch s¾p xÕp ®−îc sö dông lµ (A, B, C) → (A, B, C) → (B, A, C) → (B, A, C) → (A, B, C) → (A, B, C) → ( B, C, A) → (C, B, A). Ph¹m vi tÇn sè lµ 18. Sö dông ph−¬ng ph¸p quyÕt ®Þnh thø 2, chuçi trËt tù danh s¸ch ®−îc sö dông lµ: (A, B, C) → (B, A, C) → (A, B,C) → (B, A, C) → (A, C, B) → (C, B, A) → (B, A, C) → (A, B, C) vµ ph¹m vi tÇn sè lµ 15 nh− ®−îc biÓu diÔn ë h×nh 3.2(d). Cã thÓ thÊy ph¹m vi tÇn sè 15 lµ tèi −u cho vÝ dô nµy. Tãm l¹i, ph¹m vi tÇn sè gi¶m tõ 20 ®Õn 15 víi viÖc sö dông s¾p xÕp l¹i tÕ bµo. 3.5 Tèi −u viÖc g¸n kªnh t¹i c¸c ®iÓm nãng Nh− ®· ®Ò cËp ë phÇn giíi thiÖu, ph−¬ng ph¸p g¸n kªnh theo kinh nghiÖm cã hai vÊn ®Ò. Trong môc tr−íc, chóng ta ®· gi¶i quyÕt vÊn ®Ò thø nhÊt b»ng sù s¾p xÕp l¹i c¸c tÕ bµo tr−íc khi g¸n kªnh kÕ tiÕp. Trong môc nµy, chóng ta tËp trung vµo vÊn ®Ò thø 2: hiÖu qu¶ viÖc g¸n kªnh cho ®iÓm nãng. Th«ng th−êng, mét ®iÓm nãng bao gåm mét sè tÕ bµo ®iÓm nãng vµ ph¹m vi tÇn sè ®iÓm nãng phô thuéc vµo c¸c kªnh ®−îc g¸n cho tÕ bµo ®iÓm nãng cña chóng nh− thÕ nµo. TËp trung vµo tèi −u viÖc g¸n kªnh t¹i ®iÓm nãng, mét chiÕn l−îc míi ®−îc gäi lµ vÐt c¹n tÇn sè kÕt hîp vµ chiÕn l−îc vÐt c¹n yªu cÇu (FR) ®· ®−îc ®Ò xuÊt. ChiÕn l−îc FR cã thÓ kÕt hîp víi 2 ph−¬ng ph¸p s¾p xÕp l¹i tÕ bµo ®Ó t¹o ra hai thuËt to¸n g¸n kªnh FR/CR vµ FR/DR. Tr−íc khi tiÕp tôc, ta xÐt kÜ h¬n chiÕn l−îc vÐt c¹n tÇn sè (F) vµ chiÕn l−îc vÐt c¹n yªu cÇu (R). 3.5.1 ChiÕn l−îc F vµ chiÕn l−îc R - NhËn xÐt ®Çu tiªn cña chóng ta lµ khi sö dông chiÕn l−îc R ®Ó g¸n kªnh, sè c¸c tÕ bµo ®ång kªnh cña kªnh ®−îc g¸n cã xu h−íng lín h¬n so víi viÖc sö dông chiÕn l−îc F. Kh«ng mÊt tÝnh tæng qu¸t, gi¶ sö h¹n chÕ xuyªn nhiÔu kªnh cïng tr¹m gi¸ trÞ lín h¬n hay b»ng tæn hao cña viÖc h¹n chÕ xuyªn nhiÔu kªnh l©n cËn, tøc lµ s ≥ a. Khi g¸n kªnh f cho mét tÕ bµo sö dông chiÕn l−îc R, viÖc g¸n kªnh sÏ thµnh c«ng nÕu viÖc h¹n chÕ xuyªn nhiÔu ®· nªu ra bëi viÖc g¸n kªnh ®ã tr−íc tõ (f – s + 1) ®Õn f kh«ng bÞ vi ph¹m. Chó ý r»ng kªnh cã h¹ng cao nhÊt ®−îc g¸n lµ kªnh hiÖn thêi ®−îc g¸n, tøc lµ kªnh f. NÕu chiÕn l−îc F ®−îc sö dông, g¸n kªnh f cho tÕ bµo cÇn ph¶i kiÓm tra c¸c rµng buéc ®· g©y bëi viÖc g¸n kªnh tõ (f-s+1) ®Õn (f+s-1). Sè kªnh ®−îc kiÓm tra gÇn nh− hai lÇn so víi trong chiÕn l−îc R. KÕt qu¶ lµ, kªnh f cã x¸c suÊt bÞ tõ chèi bëi mét tÕ bµo lµ cao h¬n. KÕt qu¶ nµy kh«ng chÆt trong mèi quan hÖ tÕ bµo ®ång kªnh cña kªnh f. - NhËn xÐt thø hai lµ kh«ng nh− chiÕn l−îc F, khi sö dông chiÕn l−îc R kªnh ®−îc g¸n kh«ng b¸m chÝnh x¸c theo ®é khã cña viÖc g¸n c¸c tÕ bµo riªng lÎ. Gi¶ thiÕt chiÕn l−îc R ®−îc sö dông ®Ó g¸n kªnh f cho hÖ thèng. NÕu kh«ng cã rµng buéc nµo bÞ vi ph¹m, tÕ bµo ®Çu tiªn trong danh s¸ch ®−îc s¾p xÕp sÏ nhËn kªnh f. Sau ®ã kªnh f ®−îc g¸n cho tÊt c¶ c¸c tÕ bµo cã thÓ (ch¼ng h¹n c¸c tÕ bµo víi c¸c yªu cÇu kh«ng tho¶ m·n vµ kh«ng vi ph¹m bÊt kú sù rµng buéc g¸n kªnh nµo), trong danh s¸ch tr−íc khi xem xÐt kªnh f + 1. Tuy nhiªn, viÖc g¸n tiÕp kªnh f cho c¸c tÕ bµo cßn l¹i kh«ng b¸m chÝnh x¸c theo ®é khã cña viÖc g¸n. XÐt mét vÝ dô ®¬n gi¶n, gi¶ sö khi kªnh 1 ®−îc g¸n cho tÕ bµo ®Çu tiªn trong danh s¸ch ®· ®−îc s¾p xÕp, tÕ bµo ®Çu tiªn vÉn lµ tÕ bµo khã kh¨n g¸n kªnh nhÊt sau khi s¾p xÕp l¹i tÕ bµo. V× cïng mét kªnh, ch¼ng h¹n kªnh 1, kh«ng thÓ ®−îc g¸n hai lÇn cho cïng mét tÕ bµo. Do ®ã viÖc g¸n kªnh kÕ tiÕp lµ g¸n kªnh 1 cho tÕ bµo kh¸c, tÕ bµo nµy kh«ng ph¶i lµ khã nhÊt cho viÖc g¸n kªnh. Tr¸i l¹i, chiÕn l−îc F kh«ng cã vÊn ®Ò nµy. Tõ hai nhËn xÐt trªn, chóng ta cã thÓ thÊy r»ng c¸c hÖ thèng víi nh÷ng thay ®æi nhá trong nh÷ng yªu cÇu kªnh tõ tÕ bµo nµy ®Õn tÕ bµo kh¸c (hoÆc nh÷ng yªu cÇu kªnh ph©n bè kh«ng ®ång ®Òu Ýt h¬n), tèi ®a ho¸ sè tÕ bµo ®ång kªnh lµ quan träng h¬n. Bëi vËy, chiÕn l−îc R h−íng tíi cho mét chÊt l−îng tèt h¬n. C¸c hÖ thèng víi nh÷ng yªu cÇu kªnh ph©n bè kh«ng ®ång ®Òu cao, ®iÒu ®ã lµ rÊt quan träng ®Ó tho¶ m·n c¸c yªu cÇu kªnh cña c¸c tÕ bµo ®Çu tiªn khã kh¨n nhÊt cho viÖc g¸n kªnh. Do ®ã, chiÕn l−îc F h−íng tíi ho¹t ®éng tèt h¬n. 3.5.2 ChiÕn l−îc FR §Ó kÕt hîp nh÷ng −u ®iÓm cña chiÕn l−îc R vµ F, chiÕn l−îc FR ®· ®−îc ®Ò xuÊt. §ã lµ mét chiÕn l−îc g¸n kªnh 2 møc bao gåm g¸n kªnh toµn bé sö dông sö dông chiÕn l−îc R vµ g¸n kªnh côc bé sö dông chiÕn l−îc F. ViÖc g¸n kªnh toµn bé sÏ nhËn d¹ng c¸c ®iÓm nãng vµ sÏ sö dông chiÕn l−îc R ®Ó tèi ®a ho¸ c¸c tÕ bµo ®ång kªnh. ViÖc g¸n côc bé tËp trung g¸n c¸c kªnh cho ®iÓm nãng ®· ®−îc x¸c nhËn vµ ®Ó s¾p xÕp c¸c kªnh nµy mét c¸ch chÆt chÏ sö dông chiÕn l−îc F. Khi kªnh f ®−îc g¸n cho tÕ bµo i (tÕ bµo ®Çu tiªn trong danh s¸ch ®· ®−îc s¾p xÕp) bëi g¸n toµn bé, mét ®iÓm nãng cã t©m lµ tÕ bµo i (hoÆc ®iÓm nãng i) ®−îc x¸c nhËn. RÊt khã kh¨n ®Ó cã mét quy t¾c vÒ ng−ìng ®Ó x¸c ®Þnh tÕ bµo xuyªn nhiÔu nµo cña tÕ bµo i thuéc vµo cïng ®iÓm nãng vµ tÕ bµo xuyªn nhiÔu nµo kh«ng thuéc cïng ®iÓm nãng. Chóng ta dïng ph−¬ng ph¸p kinh nghiÖm b»ng c¸ch x¸c ®Þnh r»ng ®iÓm nãng i chøa c¸c tÕ bµo n»m trong ph¹m vi nhiÔu cña tÕ bµo i vµ cã yªu cÇu kªnh t−¬ng ®èi cao. §Ó ®¬n gi¶n ho¸ tiÕn tr×nh cña viÖc x¸c ®Þnh c¸c tÕ bµo víi c¸c yªu cÇu kªnh t−¬ng ®èi cao, chóng ta ®Þnh nghÜa mét tham sè Y. Gi¶ sö tÊt c¶ c¸c tÕ bµo xuyªn nhiÔu cña tÕ bµo i t¹o thµnh mét danh s¸ch ®−îc s¾p xÕp víi ®é khã g¸n kªnh gi¶m dÇn. Y tÕ bµo ®Çu tiªn trong danh s¸ch ®−îc s¾p xÕp, hay tÕ bµo ®iÓm nãng, ®−îc chän ra ®Ó tham gia g¸n côc bé tiÕp sau. Gi¸ trÞ cña Y cã thÓ ®−îc thay ®æi ®Ó ®¹t ®−îc nh÷ng chÊt l−îng kh¸c nhau. Chó ý r»ng ®©y chØ lµ mét ph−¬ng ph¸p kinh nghiÖm ®Ó nhËn d¹ng ®iÓm nãng. Ph−¬ng ph¸p nµy thËt ®¬n gi¶n nh−ng kh«ng tèi −u, ngoµi ra cßn cã nhiÒu ph−¬ng ph¸p kh¸c n÷a. Ngay khi ®iÓm nãng ë tÕ bµo i ®−îc nhËn d¹ng sö dông ph−¬ng ph¸p trªn, g¸n kªnh toµn bé më réng ®Ó thùc hiÖn g¸n côc bé. G¸n côc bé sö dông chiÕn l−îc F ®Ó g¸n c¸c kªnh cho tÕ bµo ®iÓm nãng cña ®iÓm nãng i (nh−ng kh«ng bao gåm tÕ bµo i). Trong g¸n kªnh côc bé, mçi tÕ bµo ®iÓm nãng ®−îc phÐp nhËn nhiÒu nhÊt lµ mét kªnh vµ h¹ng cña kªnh ®ã ph¶i nhá h¬n hoÆc b»ng f + X , víi X lµ tham sè nguyªn kh¸c ®−îc t¹o ra/ ®iÒu chØnh. Trong thùc tÕ, kh«ng thÓ t×m ®−îc kªnh víi h¹ng nhá h¬n hay b»ng f (v× g¸n kªnh toµn bé sö dông chiÕn l−îc R) vµ do vËy, mét kªnh chØ cã thÓ ®−îc chän tõ d·y f + 1 ®Õn f + X trong g¸n côc bé. Môc ®Ých cña viÖc thiÕt lËp giíi h¹n f + X lµ ®Ó cùc tiÓu ho¸ xuyªn nhiÔu sÏ ®−îc t¹o ra bëi c¸c kªnh ®−îc g¸n mét c¸ch côc bé ®èi víi viÖc g¸n kªnh tiÕp theo. Khi viÖc g¸n kªnh côc bé ®−îc hoµn thµnh, viÖc g¸n kªnh toµn bé ®−îc b¾t ®Çu l¹i ®Ó g¸n kªnh f ®èi víi tÕ bµo cã thÓ tiÕp theo trong danh s¸ch ®· s¾p xÕp (sö dông chiÕn l−îc R). NÕu kh«ng cã mét tÕ bµo nµo n÷a cã thÓ chÊp nhËn kªnh f, th× tiÕp tôc víi kªnh f + 1. TiÕp tôc thñ tôc nµy cho ®Õn khi tÊt c¶ c¸c yªu cÇu kªnh ®−îc tho¶ m·n. ViÖc kÕt hîp chiÕn l−îc FR víi 2 ph−¬ng ph¸p s¾p xÕp l¹i tÕ bµo, cã hai thuËt to¸n g¸n kªnh FR/CR vµ FR/DR ®· ®¹t ®−îc. L−u ý r»ng khi s¾p xÕp l¹i tÕ bµo ®−îc sö dông, c¸c tÕ bµo ®−îc s¾p xÕp l¹i sau mçi lÇn g¸n kªnh bÊt chÊp ®ã lµ g¸n kªnh toµn bé hay g¸n kªnh côc bé. TiÕp theo, chóng ta sÏ tãm t¾t c¸c thuËt to¸n FR/CR vµ FR/DR nh− sau: G¸n toµn bé Input: C = [ cij] vµ M = (m1, m2, …, mN) Output: N(F*) 1. For i = 1 to N do m’i = mi; f = 1; 2. For i = 1 to N do if m’i = 0, di = 0 else di = ∑Nj=1 m’j cij ; 3. S¾p xÕp c¸c tÕ bµo thµnh danh s¸ch cã trËt tù sö dông thø tù mµu nót hoÆc thø tù cÊp ®é nót. 4. T×m tÕ bµo thø nhÊt i trong danh s¸ch, sao cho viÖc g¸n kªnh f cho tÕ bµo i lµ phï hîp víi tÊt c¶ viÖc g¸n tr−íc. 5. NÕu tÕ bµo i t×m ®−îc nÕu di ≠ 0 m’i = m’i – 1, k = mi – m’i vµ fik = f; nh¶y ®Õn b−íc 1 cña g¸n côc bé; ng−îc l¹i N(F*) = maxi,kfik vµ EXIT; 6. Ng−îc l¹i f = f + 1 vµ nh¶y ®Õn b−íc 4 G¸n côc bé 1. counter = 1 2. Khi counter ≤ Y thùc hiÖn cho mçi tÕ bµo j víi cij ≥ 1 thùc hiÖn nÕu m’j = 0, dj = 0 ; ng−îc l¹i dj = ∑Nk=1 m’k cjk ; s¾p xÕp c¸c tÕ bµo víi cij ≥ 1 trong danh s¸ch cã thø tù sö dông thø tù mµu nót hoÆc thø tù cÊp ®é nót; nÕu bËc cña tÕ bµo thø nhÊt trong danh s¸ch dj ≠ 0, t×m kªnh g víi h¹ng nhá nhÊt sao cho g¸n g cho tÕ bµo j lµ phï hîp víi tÊt c¶ viÖc g¸n tr−íc ®ã vµ f < g ≤ f + X nÕu g t×m ®−îc m’j = m’j – 1, k = mj - m’j vµ fik = g counter = counter + 1 ng−îc l¹i nh¶y ®Õn b−íc 2 cña viÖc g¸n toµn bé. 3. Nh¶y ®Õn b−íc 4 cña g¸n toµn bé. C¸c gi¸ trÞ tèi −u cña X vµ Y sao cho ph¹m vi tÇn sè cña hÖ thèng lµ cùc tiÓu ho¸ rÊt khã kh¨n ®Ó ®¹t ®−îc. Thùc tÕ, c¸c gi¸ trÞ tèi −u nªn ®−îc ®iÒu chØnh sau mçi viÖc g¸n kªnh ngay khi thùc hiÖn s¾p xÕp l¹i tÕ bµo. §Ó ®¬n gi¶n, ta gi¶ thiÕt gi¸ trÞ cña X vµ Y trong luËn v¨n nµy lµ cè ®Þnh. Gi¶ sö kªnh f ®−îc g¸n cho tÕ bµo k bëi viÖc g¸n toµn bé. X¸c ®Þnh gi¸ trÞ X vµ Y thÝch hîp ®−îc tãm t¾t ë d−íi ®©y. • NÕu X = 0, g¸n côc bé ®−îc bá qua. • NÕu X = 1, chØ c¸c tÕ bµo víi ckj = 1 cã thÓ tham gia vµo viÖc g¸n côc bé. • NÕu X ≤ s – a, viÖc g¸n kªnh f tiÕp theo ®Õn phÇn cßn l¹i hÖ thèng sÏ kh«ng bÞ ¶nh h−ëng bëi xuyªn nhiÔu ®−îc g©y ra cho g¸n kªnh côc bé hiÖn thêi. • NÕu X ≤ s + 1, mäi xuyªn nhiÔu cña tÕ bµo k cã thÓ ®¹t t¹i mét kªnh trong g¸n côc bé. • 0 ≤ Y ≤ tæng sè c¸c kªnh xuyªn nhiÔu cña tÕ bµo k • NÕu Y = 0, viÖc g¸n côc bé ®−îc bá qua. • Y cÇn nhËn gi¸ trÞ mµ cã thÓ so s¸nh ®−îc víi sè tÕ bµo ®iÓm nãng trong ®iÓm nãng ®−îc tËp trung t¹i tÕ bµo k. Cã thÓ thÊy r»ng c¸c thuËt to¸n FR/CR vµ FR/DR cã cïng sù phøc t¹p vÒ thêi gian nh− cña F/CR vµ F/DR, nghÜa lµ O (MN3 + M2) cho FR/CR vµ O(MN2+ M2) cho FR/DR. §ã lµ v× viÖc g¸n côc bé chØ cã ®é phøc t¹p O(M + N). 3.6 §¸nh gi¸ chÊt l−îng Ta sö dông c¸c vÝ dô dïng 21 tÕ bµo nh− trong [13], [26] cho viÖc ®¸nh gi¸ chÊt l−îng. §Ó dÔ so s¸nh, c¸c cËn d−íi g¸n kªnh lý thuyÕt cho hÖ thèng nµy ®· ®−îc ®−a ra [13], [27]. H×nh 3.3 chØ ra 2 tr−êng hîp yªu cÇu kªnh. Sè kªnh biÓu diÔn trong mçi tÕ bµo lµ yªu cÇu kªnh cña tÕ bµo ®ã. C¸c tÕ bµo ®−îc ®¸nh sè tõ 1 ÷ 21 theo trËt tù tõ tr¸i sang ph¶i vµ tõ trªn xuèng d−íi. Trong ch−¬ng tr×nh cña chóng ta, khi thø tù cÊp ®é nót ®−îc sö dông, tÕ bµo víi sè tÕ bµo nhá nhÊt ®−îc lùa chän ®Çu tiªn. Khi thø tù mµu nót ®−îc sö dông, tÕ bµo víi sè tÕ bµo lín nhÊt ®−îc lùa chän ®Çu tiªn. Gi¶ sö bé ba cã thø tù (Nc, a, s) biÓu thÞ hÖ thèng víi nhãm kÝch th−íc Nc, rµng buéc kªnh l©n cËn a vµ rµng buéc kªnh ®ång site s. KÕt qu¶ g¸n kªnh ®−îc tãm t¾t trong c¸c b¶ng 3.1, 3.2, 3.3. 8 25 8 28 8 18 77 52 8 13 15 57 15 15 813 10 31 36 28 8 (a) Yªu cÇu kªnh tr−êng hîp I 5 5 5 40 12 30 3025 8 40 45 15 30 25 252020 20 25 15 30 (b) Yªu cÇu kªnh tr−êng hîp II H×nh 3.3 M¹ng 21 tÕ bµo víi 2 tr−êng hîp yªu cÇu kªnh Cét SMK t−¬ng øng víi kÝch th−íc ph¹m vi tÇn sè ®¹t ®−îc tõ 8 thuËt to¸n trong [26]. Cét LB t−¬ng øng víi cËn d−íi cã tÝnh lý thuyÕt trong [13], [27]. Nh÷ng cËn d−íi nµy ®· cã ®−îc bëi sù xem xÐt t¸ch riªng ra m¹ng con cña hÖ thèng nguyªn thuû. CÇn chó ý r»ng ta kh«ng biÕt ®−êng biªn xÕp khÝt nhau nh− thÕ nµo. B¶ng 3.1 Ph¹m vi tÇn sè nhËn ®−îc bëi F/CR, F/DR, R/CR vµ R/DR Tr−êng hîp CÊu h×nh m¹ng LB F/CR F/DR R/CR R/DR SMK I I I I I I (12,2,3) (7,2,3) (12,2,5) (7,2,5) (12,2,7) (7,2,7) 427 427 427 427 533 533 435 433 431 432 533 533 472 475 448 476 533 533 427 442 489 468 568 557 431 439 481 496 568 557 436-554 442-554 460-543 447-543 536-565 533-566 II II II II II II (12,2,3) (7,2,3) (12,2,5) (7,2,5) (12,2,7) (7,2,7) 258 253 258 258 309 309 286 265 293 264 309 309 339 309 289 269 315 315 262 263 267 264 318 325 278 271 291 277 321 337 272-327 265-340 283-360 269-347 310-384 310-358 B¶ng 3.2 Ph¹m vi tÇn sè nhËn ®−îc bëi FR/CR vµ FR/DR víi (7,2,5) vµ yªu cÇu kªnh tr−êng hîp I ThuËt to¸n Y X = 1 X =2 X =3 X = 4 X = 5 FR/CR Y = 1 Y = 2 Y = 3 488 485 487 450 459 466 446 428 445 445 437 438 446 433 437 FR/DR Y = 1 Y = 2 Y = 3 508 491 493 451 462 472 457 438 446 456 453 448 458 441 444 B¶ng 3.3 Ph¹m vi tÇn sè nhËn ®−îc bëi FR/CR vµ FR/DR víi 0 ≤ X ≤ 5 vµ1 ≤ Y ≤ 3 Tr−êng hîp CÊu h×nh m¹ng LB FR/CR FR/DR SMK I I I I I I (12,2,3) (7,2,3) (12,2,5) (7,2,5) (12,2,7) (7,2,7) 427 427 427 427 533 533 427 (0,Y) (1,1)-(1,3) 430 (1,3) 428 (3,2) (4,2) (5,3) 428 (3,2) 533 (3,1)-(5,1) (3,2) (5,2) (3,3) 533 (3,1)-(5,1) 427 (1,2) (1,3) 428 (1,3) 431 (5,2) (3,3) 438 (3,2) 533 (2,1)-(5,1) 533 (3,1)-(5,1) 436-554 442-554 460-543 447-543 536-565 533-566 II II II II II II (12,2,3) (7,2,3) (12,2,5) (7,2,5) (12,2,7) (7,2,7) 258 253 258 258 309 309 262 (0,Y) 257 (1,3) 263 (1,2) 263 (2,2) (4,3) 310 (4,1) (5,1) 309 (5,2) 278 (0,Y) 265 (1,2) 272 (2,3) 262 (1,3) 316 (1,1) (4,3) 320 (3,1) 272-327 265-340 283-360 269-347 310-384 310-358 3.6.1 ChÊt l−îng cña thuËt to¸n F/CR, F/DR, R/CR vµ R/DR §èi víi cÊu h×nh m¹ng kh¸c nhau, b¶ng 3.1 tãm t¾t ph¹m vi tÇn sè cã ®−îc nhê sö dông c¸c thuËt to¸n F/CR, F/DR, R/CR vµ R/DR. Ph¹m vi tèi thiÓu t×m thÊy trong mçi hµng ®−îc g¹ch ch©n. Tõ b¶ng nµy chóng ta cã thÓ thÊy c¸c thuËt to¸n F/CR lu«n thùc hiÖn tèt h¬n F/DR. §iÒu nµy chØ ra thø tù tÕ bµo mµu nót lµ hiÖu qu¶ h¬n so víi thø tù cÊp ®é nót. Tuy nhiªn, khuynh h−íng nh− vËy kh«ng thÓ hiÖn râ ®èi víi c¸c thuËt to¸n R/CR vµ R/DR. §iÒu nµy cã nguyªn nh©n lµ c¸c kªnh ®−îc g¸n kh«ng theo chÝnh x¸c ®é khã g¸n kªnh khi sö dông chiÕn l−îc R (xem phÇn 3.5.1). Nh− chóng ta ®· dù ®o¸n trong phÇn 3.5.1, thuËt to¸n F/CR thùc hiÖn tèt h¬n trong tr−êng hîp I víi nh÷ng yªu cÇu kªnh (thuËt to¸n ®−îc ph©n bè mét c¸ch kh«ng ®ång ®Òu) vµ thuËt to¸n R/CR thùc hiÖn tèt h¬n trong tr−êng hîp II víi nh÷ng yªu cÇu kªnh (thuËt to¸n ®−îc ph©n bè kh¸ ®ång ®Òu). §èi víi mçi tr−êng hîp nghiªn cøu, ph¹m vi tèi thiÓu t×m thÊy bëi c¸c thuËt to¸n lµ thÊp h¬n nhiÒu ®iÒu t×m ®−îc bëi thuËt to¸n trong [26]. VÝ dô, ®èi víi yªu cÇu kªnh tr−êng hîp I vµ cÊu h×nh m¹ng (12, 2, 5), ph¹m vi tèi thiÓu chóng ta t×m ®−îc lµ 431 vµ bëi thuËt to¸n trong [26] lµ 460. 3.6.2 ¶nh h−ëng cña X vµ Y ®èi víi chÊt l−îng cña c¸c thuËt to¸n FR/CR vµ FR/DR TiÕp theo chóng ta nghiªn cøu chÊt l−îng cña c¸c thuËt to¸n FR/CR vµ FR/DR víi nh÷ng gi¸ trÞ kh¸c cña X vµ Y. XÐt hÖ thèng víi cÊu h×nh (7, 2, 5) vµ c¸c yªu cÇu kªnh tr−êng hîp I. B¶ng 3.2 chØ ra kÕt qu¶ ph¹m vi tÇn sè trong kho¶ng 1 ≤ X ≤ 5 vµ 1 ≤ Y ≤ 3. Khi X = 3 vµ Y = 2, c¶ hai thuËt to¸n ®Òu cho ph¹m vi tÇn sè tèi thiÓu lµ 428 vµ 438. KÕt qu¶ tèt nhÊt ®¹t ®−îc bëi c¸c thuËt to¸n trong [26] chØ lµ 447 vµ trong [7] chØ lµ 446. 3.6.3 ChÊt l−îng cña c¸c thuËt to¸n FR/CR vµ FR/DR Víi 0 ≤ X ≤ 5 vµ 1 ≤ Y ≤ 3. B¶ng 3.3 tãm t¾t ph¹m vi tèi thiÓu t×m ®−îc bëi c¸c thuËt to¸n FR/CR vµ FR/DR. CÆp thø tù (X, Y) ®· chØ ra trong b¶ng biÓu thÞ gi¸ trÞ tõ ®ã t×m ra ph¹m vi tÇn sè. (0, Y) cã nghÜa Y cã thÓ lµ bÊt kú gi¸ trÞ nµo. Ph¹m vi tèi thiÓu cña mçi hµng trong b¶ng ®−îc g¹ch ch©n, ph¹m vi cã thÓ thÊy r»ng thuËt to¸n FR/CR lu«n lu«n tèt h¬n c¸c thuËt to¸n trong [26]. Bªn c¹nh ®ã, nã t¹o ra mét ph¹m vi nhá h¬n thuËt to¸n FR/DR ngo¹i trõ ®èi víi tr−êng hîp I víi (7, 2, 3) vµ tr−êng hîp II víi (7, 2, 5). So s¸nh thuËt to¸n FR/CR víi c¸c thuËt to¸n F/CR vµ R/CR trong b¶ng 3.1, FR/CR cho gi¸ trÞ ph¹m vi nhá nhÊt trong c¸c tr−êng hîp, ngo¹i trõ ®èi víi tr−êng hîp II víi (12, 2, 7) nh−ng sù kh¸c nhau nµy chØ lµ mét kªnh. Tãm l¹i, ®èi víi c¸c yªu cÇu cña chóng ta kªnh tr−êng hîp I nh÷ng ph¹m vi thÊp nhÊt t×m ®−îc bëi c¸c thuËt to¸n chØ cao h¬n cËn d−íi lý thuyÕt nhiÒu nhÊt lµ mét kªnh. §èi víi yªu cÇu kªnh tr−êng hîp II, ph¹m vi thÊp nhÊt t×m ra b»ng c¸c thuËt to¸n cña chóng ta cao h¬n cËn d−íi lý thuyÕt nhiÒu nhÊt lµ 5 kªnh. 3.7 KÕt luËn Hai vÊn ®Ò víi c¸c thuËt to¸n g¸n kªnh kinh nghiÖm th«ng th−êng ®· ®−îc x¸c ®Þnh trong luËn v¨n nµy. S¾p xÕp l¹i tÕ bµo vµ chiÕn l−îc g¸n kªnh tËp trung vµo c¸c ®iÓm nãng ®−îc ®Ò xuÊt sau ®ã ®Ó gi¶i quyÕt c¶ hai vÊn ®Ò. KÕt qu¶ lµ s¸u thuËt to¸n g¸n kªnh míi lµ nh÷ng sù kÕt hîp cña ba chiÕn l−îc g¸n kªnh vµ hai ph−¬ng ph¸p s¾p xÕp l¹i tÕ bµo ®· ®−îc ®Ò cËp vµ nghiªn cøu. VÊn ®Ò chóng ta ®· t×m ra lµ: (i) thø tù mµu nót cña c¸c tÕ bµo lµ mét ph−¬ng ph¸p thø tù hiÖu qu¶ h¬n thø tù cÊp ®é nót; (ii) chiÕn l−îc R phï hîp h¬n cho hÖ thèng víi l−u l−îng ph©n bè kh«ng ®ång ®Òu cao vµ chiÕn l−îc F th× phï hîp h¬n cho hÖ thèng víi l−u l−îng ph©n bè kh«ng ®ång ®Òu thÊp h¬n vµ (iii) thuËt to¸n FR/CR lµ thuËt to¸n hiÖu qu¶ nhÊt cho gi¸ trÞ ph¹m vi tÇn sè thÊp nhÊt trong hÇu hÕt c¸c tr−êng hîp. Bªn c¹nh ®ã, ph¹m vi thÊp nhÊt t×m ra bëi c¸c thuËt to¸n cña chóng ta th× thÊp h¬n nhiÒu bëi c¸c thuËt to¸n ®· ®−îc b¸o c¸o trong s¸ch b¸o vµ trong nhiÒu tr−êng hîp b»ng víi c¸c cËn d−íi lý thuyÕt. X¸c ®Þnh gi¸ trÞ tèi −u cho c¸c tham sè X vµ Y trong c¸c thuËt to¸n FR/CR vµ FR/DR lµ rÊt quan träng. Trong luËn v¨n nµy, chóng ta chØ nghiªn cøu tr−êng hîp X vµ Y lµ cè ®Þnh. CÇn ph¶i nghiªn cøu s©u h¬n n÷a viÖc lµm thÕ nµo ®Ó c¶i thiÖn chÊt l−îng bëi ®iÒu chØnh linh ho¹t gi¸ trÞ X vµ Y trong viÖc ®¸p øng nh÷ng yªu cÇu kªnh cßn l¹i cña c¸c tÕ bµo riªng rÏ. KÕt luËn Sau mét thêi gian t×m hiÓu, nghiªn cøu víi sù h−íng dÉn gióp ®ì tËn t×nh cña ThÇy gi¸o - T.S §ç Quèc Trinh, cïng víi sù cè g¾ng nç lùc cña b¶n th©n, luËn v¨n ®· hoµn thµnh ®óng thêi gian qui ®Þnh vµ ®¹t ®−îc môc tiªu nghiªn cøu ®Æt ra. LuËn v¨n ®· tr×nh bµy ®−îc nh÷ng vÊn ®Ò c¬ b¶n vÒ m¹ng di ®éng tÕ bµo, c¸c chiÕn l−îc g¸n kªnh vµ bµi to¸n tèi −u ho¸ g¸n kªnh cè ®Þnh trong m¹ng di ®éng tÕ bµo. Víi môc ®Ých x©y dùng mét c¸ch nh×n tæng thÓ, s©u s¾c cho bµi to¸n g¸n kªnh trong c¸c m¹ng di ®éng tÕ bµo, t«i ®· cè g¾ng tËp hîp nh÷ng kiÕn thøc cã ®−îc tõ sù h−íng dÉn cña gi¸o viªn, tõ c¸c nguån tµi liÖu ®−îc cung cÊp mét c¸ch ng¾n gän, ®Çy ®ñ nhÊt. Nh−ng do h¹n chÕ vÒ thêi gian vµ kh¶ n¨ng cña b¶n th©n, ch¾c ch¾n luËn v¨n kh«ng tr¸nh khái nh÷ng sai sãt. T«i rÊt mong tiÕp tôc ®−îc sù chØ b¶o, gãp ý cho luËn v¨n nµy. T«i xin bµy tá lßng biÕt ¬n s©u s¾c ®èi víi thÇy gi¸o trùc tiÕp h−íng dÉn - TS. §ç Quèc Trinh vµ c¸c thÇy gi¸o trong Khoa V« tuyÕn ®iÖn tö - Häc viÖn KTQS ®· gióp ®ì t«i trong qu¸ tr×nh thùc hiÖn luËn v¨n nµy. Tµi liÖu tham kh¶o TiÕng ViÖt 1. TrÇn Anh TÊn, §ç Quèc Trinh (2005), “Tèi −u ho¸ g¸n kªnh cè ®Þnh trong m¹ng di ®éng tÕ bµo”, T¹p chÝ B−u chÝnh ViÔn th«ng vµ C«ng nghÖ th«ng tin, sè 1 th¸ng 5-2005. TiÕng Anh 2. E. Aarts and J. Korst (1989), Simulated Annealing and Boltzmann Machines, John Wiley& Sons, New York. 3. Y. Akaiwa and H. Andoh (1993), “Channel segregation – a self-organized dynamic channel allocation method: application to TDMA/FDMA microcellular system,” IEEE Journal on Selected Areas in Communications, vol. 11, no. 6, pp. 949–954. 4. H.R. Anderson, et al (1994), “Optimizing microcell base station locations using simulating annealing techniques,” Proceedings of the 44 th Vehicular Technology Society Conference, Stockholm, pp. 858–862. 5. J. A. Bondy and U.S.R. Murty (1976), Graph Theory with Applications. Macmillan Press. 6. F.Box (1978), “A heuristic technique for assingning frequencies to mobile radio nets”, IEEE Trans. Veh. Technol, vol VT-27, pp.57-64. 7. X.R Cao and J.C.I. Chuang (1994), “A set theory approach to the channel assignment problem”, Proc, IEEE Globecom, pp. 1647-1651, San Francisco. 8. J.C.-I. Chuang and N.R. Sollenberger (1998), “Spectrum resource allocation for wireless packet access with application to advanced cellular internet service,” IEEE Journal on Selected Areas in Communications, vol. 16, no. 6, pp. 820– 829. 9. J.C.-I. Chuang and N.R. Sollenberger (2000), “Beyond 3G: wideband wireless data access based on OFDM and dynamic packet assignment”, IEEE Communications Magazine, vol. 38, no. 7, pp. 78–87. 10. M. Cuppini (1996), “A genetic algorithm for channel assignment problems,” European Transactions On Telecommunications and Related Technologies, vol. 5, no. 2, pp. 285–294. 11. M. Duque-Anton, D. Kunz, and B. Ruber (1993), “Channel assignment for cellular radio using simulated annealing,” IEEE Transactions on Vehicular Technology, vol. VT-42, no. 1, pp 14–21. 12. A. Gamst and W. Rave (1982), “On frequency assignment in mobile automatic telephone systems,” IEEE Proc. GLOBECOM ’82, pp .309 –315. 13. A. Gamst (1986), “Some lower bounds for a class of frequency assignment problems”, IEEE Trans.Veh, Technol,vol.VT-35, no 1, pp .8-14. 14. M. Haardt, et al (2000), “The TD-CDMA based UTRA TDD Mode,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 8, pp. 1375–1385. 15. W.K. Hale (1980), “Frequency assignment: Theory and applications”, Proc.IEEE, vol.68, pp 1497- 1514. 16. H. Holma, S. Heikkinen, O.-A. Lehtinen, and A. Toskala (2000), “Interference considerations for the time division duplex mode of the UMTS terrestrial radio access,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 8, pp. 1386–1393. 17. Young-Ho Jung, Y.H. Lee (2001), “Scrambling code planning for 3GPP W- CDMA systems,” Pro-ceedings of the 51 st Vehicular Technology Society Conference, Athens, pp. 2431–2434. 18. D.Kunz (1991), “Channel assigment for cellular radio using neural networks”, IEEE Trans. Veh. Technol, vol.40, pp 188-193. 19. D.Kunz (1991), “Suboptimum solutions obtained by the hopfieldtank neural network algorithm”. Biol. Cybern , vol.65, pp .129-133. 20. W.K. Lai and G.G. Coghill (1996), “Channel assignment through evolutionary optimization,” IEEE Transactions on Vehicular Technology, vol. 45, no. 1, pp. 91–96. 21. V. H. MacDonald (1979), Advanced mobile phone service: The cellular concept. Bell Systems Technical Journal, 58(1). 22. N. Metropolis, A. Rosenbaum, M. Rosenbluth, A. Teller, and E. Teller (1953), “Equation of state calculations by fast computing machines,” J.Chem. Phys. vol. 21, pp. 1087-1092. 23. C.Y. Ngo and V.O.K. Li, “Fixed channel assignment in cellular radio networks using a modified genetic algorithm,” IEEE Transactions on Vehicular Technology, vol. 47, no. 1, pp. 163–172, February, 1998. 24. G.J. Pottie (1995), “System design choices in personal communications,” IEEE Personal Communi-cations, vol. 2, pp. 50–67. 25. T.S. Rappaport (1997), Wireless Communications Principles and Practice, McGraw-Hill, New York. 26. K.N. Sivarajan, R.J. McEliece, and J.W. Ketchum (1989), “Channel assigment in cellular radio”, IEEE Veh. Tech. Conf, VTC’ 89, pp .846-850. 27. C.W .Sung and W.S. Wong (1995), “A graph theoretic approach to the channel assignment problem in cellular systems” , IEEE Veh. Tech. conf. VTC’95 , Chicago. 28. C.W.Sung and W.S. Wong (1997), “Sequential packing algorithm for channel assignment under co-channel and adjacent channel interference constraint”, IEEE Trans. Veh. Technol, vol.46, no 3, pp. 676-686. 29. Samuel C. Yang (1998), CDMA RF System Engineering. Boston: Artech House Publishers, pp. 165–174. 30. J.A Zoellner and C.A. Beall (1997), “A breakthrough in spectrum conserving frequency assignment technology”, IEEE Trans. Electromagn. Comput, vol.EMC-19, pp. 313-319.