BË GIO DÖC V O TO
TR×ÍNG I HÅC BCH KHOA H NËI
NGUYN QUANG KHNH
ÀNH TUYN N
NG CAO THÆNG L×ÑNG MNG
DÜA TRN NN TNG THIT K XUYN LÎP
CHO MNG ADHOC
Ng nh: Kÿ thuªt Vi¹n thæng
M¢ sè: 9520208
TÂM TT LUN N TIN S Kß THUT VIN THÆNG
H NËI - 2019
Cæng tr¼nh n y ÷ñc ho n th nh t¤i
Tr÷íng ¤i håc B¡ch khoa H Nëi
Gi¡o vi¶n h÷îng d¨n khoa håc:
PGS.TS Nguy¹n V«n ùc
Ph£n bi»n 1:
Ph£n bi»n 2:
Ph£n bi»n 3:
Luªn ¡n ÷ñc b£o v» tr÷îc Hëi çng ¡nh gi¡ luªn ¡n ti¸n s¾ c§p tr÷íng
håp t¤i Tr÷íng ¤i håc B¡ch khoa H Nëi
v o hçi . . . gií, ng y . . . th¡ng . . . n«m . . .
Câ thº t¼m hiºu luªn ¡n t¤i:
1. Th÷ vi»n T¤ Quang Bûu, Tr÷íng HBK H Nëi
2. Th÷ vi»n Quèc gia Vi»t Nam
GIÎI THIU
1. Lþ do chån · t i
Trong m¤ng khæng d¥y nâi chung v m¤ng adhoc ri¶ng nhúng v§n ·
t¤i c¡c lîp d÷îi £nh h÷ðng chùc n«ng cõa c¡c lîp tr¶n th÷íng xuy¶n x£y
ra nh÷: c¡c xung ët k¶nh truy·n t¤i lîp MAC l nguy¶n nh¥n d¨n tîi c¡c
giao thùc ành tuy¸n t¤i lîp NET c¦n thüc hi»n cªp nhªt v t¼m l¤i ÷íng
k¸t nèi mîi hay c¡c giao thùc ành tuy¸n t¤i lîp NET l m £nh h÷ðng ¸n
vi»c truy·n l¤i dú li»u t¤i lîp TRA. èi vîi m¤ng khæng d¥y, thi¸t k¸ ph¥n
lîp nh÷ mæ h¼nh OSI, TCP/IP trð n¶n khæng cán phò hñp v y¶u c¦u x¥y
düng mët cì ch¸ trao êi thæng tin giúa c¡c lîp hay thi¸t k¸ xuy¶n lîp l
r§t c¦n thi¸t. Trong luªn ¡n tªp trung v o möc ti¶u n¥ng cao thæng l÷ñng
m¤ng b¬ng c¡ch x¥y düng c¡c thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng
thi¸t k¸ xuy¶n lîp cho m¤ng adhoc v sû döng c¡c mæ h¼nh mæ phäng minh
håa k¸t qu£ c¡c thuªt to¡n ành tuy¸n · xu§t.
2. T¼nh h¼nh nghi¶n cùu trong v ngo i n÷îc
T¤i Vi»t Nam, m°c dò sü ph¡t triºn m¤ng khæng d¥y công nh÷ m¤ng
adhoc l r§t lîn v v§n · n¥ng cao thæng l÷ñng m¤ng công ÷ñc r§t quan
t¥m, t¡c gi£ trong [59] ¢ thüc hi»n ph¥n t½ch mæ h¼nh OSI vîi c¡c lîp
ho¤t ëng ëc lªp, câ nhi·u h¤n ch¸, º khc phöc v§n · tr¶n, thi¸t k¸
xuy¶n lîp ÷ñc · cªp nh÷ mët gi£i ph¡p. Trong b i b¡o, t¡c gi£ ¢ n¶u ra
mët sè tham sè câ thº tham gia trong c¡c thuªt to¡n ành tuy¸n xuy¶n lîp
trong m¤ng khæng d¥y, tuy nhi¶n t¡c gi£ ch÷a câ c¡c · xu§t mët thuªt
to¡n ành tuy¸n xuy¶n lîp cö thº. Trong nghi¶n cùu [41], t¡c gi£ ¢ câ n¶u
mët sè k¸t hñp giúa c¡c lîp (NET, MAC v PHY), tuy nhi¶n t¡c gi£ công
ch÷a · xu§t ÷ñc thuªt to¡n ành tuy¸n mîi tr¶n c¡c k¸t hñp â. Tr¶n th¸
giîi, thi¸t k¸ xuy¶n lîp ¢ câ mët sè nghi¶n cùu, trong [57], nhâm t¡c gi£
¢ · xu§t thuªt to¡n ành tuy¸n xuy¶n lîp tèi ÷u n«ng l÷ñng. Thuªt to¡n
ành tuy¸n xuy¶n lîp · xu§t l sü k¸t hñp giúa lîp MAC v lîp NET.
B¬ng c¡ch sû döng mæ h¼nh mæ phäng, nhâm t¡c gi£ ¢ minh håa thuªt
1
to¡n ành tuy¸n · xu§t gi£m t l» ành tuy¸n léi, qua â gi£m ÷ñc t l»
t¼m l¤i ÷íng, n¥ng cao hi»u qu£ sû döng n«ng l÷ñng cõa c¡c nót. Trong
[108], nhâm t¡c gi£ ¢ · xu§t thuªt to¡n ành tuy¸n xuy¶n lîp giúa hai
lîp MAC v lîp NET. Thuªt to¡n · xu§t sû döng tr¤ng th¡i cõa nót trong
m¤ng t¤i lîp MAC tham gia ành tuy¸n lîp NET, x¥y düng · xu§t c¡c
ti¸n tr¼nh truy·n dú li»u, chi¸n l÷ñc duy tr¼ c¡c ÷íng k¸t nèi. Nhâm t¡c
gi£ ¢ chùng minh thuªt to¡n · xu§t hé trñ ti¸t ki»m n«ng l÷ñng t¤i c¡c
nót v n¥ng cao ch§t l÷ñng m¤ng.
º gi£i quy¸t c¡c v§n · n y t¤i lîp PHY, lîp MAC nh¬m n¥ng cao
thæng l÷ñng m¤ng, [99] ¢ · xu§t v chùng minh thuªt to¡n c§p ph¡t k¶nh
ëng DSA [99] khc phöc v§n · nót ©n/nót hi»n trong m¤ng khæng d¥y.
Thuªt to¡n c§p ph¡t k¶nh ëng DSA ¢ khc phöc tri»t º v§n · nhi¹u
çng k¶nh (CCI) v c¡c nh÷ñc iºm cõa c¡c thuªt to¡n cô nh÷ CSMA/CD
ch¿ khc phöc ÷ñc v§n · nót ©n nh÷ng l¤i l m xu§t hi»n v§n · nót hi»n.
Trong lîp PHY, cæng su§t ph¡t v tèc ë truy·n l công hai tham sè £nh
h÷ðng ¸n thæng l÷ñng m¤ng, vi»c tèi ÷u hai tham sè n y công hé trñ n¥ng
cao thæng l÷ñng m¤ng. Tuy nhi¶n, thuªt to¡n c§p ph¡t k¶nh ëng DSA [99]
công ch÷a · xu§t c¡c gi£i ph¡p tèi ÷u cæng su§t ph¡t v tèc ë truy·n hé
trñ n¥ng cao thæng l÷ñng m¤ng. K¸t luªn, theo c¡c ¡nh gi¡ h÷îng nghi¶n
cùu tr¶n, º hé trñ n¥ng cao thæng l÷ñng m¤ng adhoc, nghi¶n cùu sinh câ
thº nghi¶n cùu ¤t ÷ñc c¡c k¸t qu£ mîi câ âng gâp gi¡ trà khoa håc v
thüc ti¹n trong cëng çng nghi¶n cùu còng l¾nh vüc.
3. Möc ti¶u cõa luªn ¡n
Möc ti¶u cõa luªn ¡n â l n¥ng cao thæng l÷ñng m¤ng adhoc b¬ng c¡ch
x¥y düng, · xu§t c¡c thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng thi¸t k¸
xuy¶n lîp. Sû döng mæ h¼nh mæ phäng minh håa c¡c thuªt to¡n ành tuy¸n
· xu§t n¥ng cao thæng l÷ñng m¤ng.
4. ëng lüc nghi¶n cùu
Trong m¤ng truy·n dú li»u nâi chung, m¤ng adhoc nâi ri¶ng th¼ thæng
l÷ñng m¤ng l mët trong nhúng ti¶u ch½ quan trång º ¡nh gi¡ ch§t l÷ñng
m¤ng, trong luªn ¡n tªp trung nghi¶n cùu n¥ng cao ti¶u ch½ n y. Do °c
iºm m¤ng khæng d¥y, mæi tr÷íng truy·n dú li»u l qu£ng b¡, khæng câ
k¶nh truy·n ri¶ng bi»t, xu§t hi»n c¡c v§n · v· nhi¹u çng k¶nh (CCI),
nót ©n, nót hi»n t¤i lîp PHY. º gi£i quy¸t c¡c v§n · t¤i lîp PHY, hé trñ
n¥ng cao ch§t l÷ñng m¤ng, Trong nghi¶n cùu [99], ¢ · xu§t thuªt to¡n
c§p ph¡t k¶nh ëng DSA. Thuªt to¡n c§p ph¡t k¶nh ëng DSA ¢ khc
phöc tri»t º v§n · nót ©n/nót hi»n v c¡c nh÷ñc iºm cõa c¡c thuªt to¡n
2
cô nh÷ CSMA/CD ch¿ khc phöc ÷ñc v§n · nót ©n nh÷ng l¤i l m xu§t
hi»n v§n · nót hi»n hay v§n · v· nhi¹u çng k¶nh (CCI). Tuy nhi¶n,
trong nghi¶n cùu [97] v¨n ch÷a ¡nh gi¡ £nh h÷ðng c¡c tham sè ÷ñc ·
xu§t bði thuªt to¡n c§p ph¡t k»nh ëng DSA t¤i c¡c lîp PHY, lîp MAC
câ thº tham gia v o c¡c thuªt to¡n ành tuy¸n t¤i lîp NET. ¥y l mët
h÷îng nghi¶n cùu, x¥y düng c¡c thuªt to¡n ành tuy¸n k¸t hñp thuªt to¡n
c§p ph¡t k¶nh ëng DSA düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp n¥ng cao
thæng l÷ñng m¤ng adhoc.
Ngo i ra, trong m¤ng adhoc, c¡c nót vøa âng vai trá l nót, vøa l
router do â v§n · cæng su§t ph¡t, tèc ë truy·n công £nh h÷ðng trüc
ti¸p ¸n thæng l÷ñng m¤ng. Vi»c tèi ÷u cæng su§t ph¡t v tèc ë truy·n
giúa c¡c nót công âng vai trá hé trñ n¥ng cao thæng l÷ñng m¤ng. Trong
nghi¶n cùu [97] công khæng · cªp ¸n tèi ÷u tham sè n y. ¥y công l
mët h÷îng nghi¶n cùu, x¥y düng thuªt to¡n tèi ÷u cæng su§t ph¡t, tèc ë
truy·n, qua â x¥y düng thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n tèi
÷u cæng su§t ph¡t, vªn tèc truy·n n y düa tr¶n n·n t£ng thi¸t k¸ xuy¶n
lîp n¥ng cao thæng l÷ñng m¤ng adhoc.
Ph÷ìng thùc m¢ m¤ng ÷ñc ¡nh gi¡ hé trñ n¥ng cao thæng l÷ñng
m¤ng truy·n qu£ng b¡ v m¤ng khæng d¥y (do °c iºm mæi tr÷íng truy·n
m¤ng khæng d¥y l qu£ng b¡). Vi»c ¡p döng ph÷ìng thùc m¢ m¤ng v o
qu¡ tr¼nh truy·n dú li»u trong m¤ng adhoc hé trñ n¥ng cao thæng l÷ñng
m¤ng. ¥y l mët h÷îng nghi¶n cùu, x¥y düng c¡c thuªt to¡n ành tuy¸n
k¸t hñp ph÷ìng thùc m¢ m¤ng düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp n¥ng
cao thæng l÷ñng m¤ng adhoc.
5. âng gâp cõa luªn ¡n
Luªn ¡n ¢ ¤t ÷ñc c¡c k¸t qu£ nghi¶n cùu v âng gâp ch½nh nh÷ sau:
1.· xu§t ba thuªt to¡n ành tuy¸n mîi k¸t hñp vîi thuªt to¡n
c§p ph¡t k¶nh ëng DSA düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp:
• Thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n c§p ph¡t k¶nh ëng DSA
düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp MAC+NET: X¥y
düng ÷ñc thuªt to¡n ành tuy¸n sû döng tham sè sè l÷ñng k¶nh c§p
ph¡t t¤i lîp MAC ÷ñc cung c§p bði thuªt to¡n c§p ph¡t k¶nh ëng
DSA.
• Thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n c§p ph¡t k¶nh ëng DSA
düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp PHY+NET: X¥y
düng ÷ñc thuªt to¡n ành tuy¸n sû döng tham sè SINR t¤i lîp PHY
÷ñc cung c§p bði thuªt to¡n c§p ph¡t k¶nh ëng DSA.
3
• Thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n c§p ph¡t k¶nh ëng DSA
düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa ba lîp PHY+MAC+NET:
X¥y düng ÷ñc thuªt to¡n ành tuy¸n sû döng tham sè SINR t¤i lîp
PHY v sè l÷ñng k¶nh c§p ph¡t t¤i lîp MAC ÷ñc cung c§p bði thuªt
to¡n c§p ph¡t k¶nh ëng DSA.
K¸t qu£ ÷ñc cæng bè tr¶n cæng tr¼nh trong [C1], [J1], [J2], [J4].
2.· xu§t thuªt to¡n tèi ÷u cæng su§t ph¡t, tèc ë truy·n v
thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n tèi ÷u cæng su§t
ph¡t v tèc ë truy·n düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp:
• Mæ h¼nh ¡nh gi¡ c¡c ch¿ sè thæng l÷ñng: X¥y düng c¡c mæ h¼nh ¡nh
gi¡ ch¿ sè nhi¹u, ch¿ sè léi v ch¿ sè thæng l÷ñng düa tr¶n ph¥n t½ch
mèi quan h» giúa cæng su§t ph¡t, tèc ë truy·n v thæng l÷ñng m¤ng.
• Thuªt to¡n tèi ÷u cæng su§t ph¡t, tèc ë truy·n: Düa v o c¡c mæ h¼nh
¡nh gi¡ ch¿ sè, mët thuªt to¡n tèi ÷u cæng su§t ph¡t, tèc ë truy·n
÷ñc · xu§t º n¥ng cao thæng l÷ñng m¤ng giúa hai nót li¶n k¸t trüc
ti¸p.
• Thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n tèi ÷u cæng su§t ph¡t
v tèc ë truy·n düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp
PHY+NET: K¸t hñp thuªt to¡n tèi ÷u cæng su§t ph¡t, tèc ë truy·n
· xu§t thuªt to¡n ành tuy¸n.
3.· xu§t thuªt to¡n ành tuy¸n k¸t hñp vîi ph÷ìng thùc m¢
m¤ng, thuªt to¡n c§p ph¡t k¶nh ëng DSA düa tr¶n n·n t£ng
thi¸t k¸ xuy¶n lîp: X¥y düng thuªt to¡n ành tuy¸n k¸t hñp ph÷ìng
thùc m¢ m¤ng v sè l÷ñng k¶nh c§p ph¡t ÷ñc cung c§p bði thuªt to¡n
c§p ph¡t k¶nh ëng DSA.
K¸t qu£ ÷ñc cæng bè tr¶n cæng tr¼nh trong [J3].
6. Bè cöc cõa luªn ¡n
Luªn ¡n gçm 4 ch÷ìng. Ch÷ìng 1 tªp trung nghi¶n cùu m¤ng adhoc a
ch°ng, mæ h¼nh thi¸t k¸ ph¥n lîp v thi¸t k¸ xuy¶n lîp. Ch÷ìng 2 · xu§t
c¡c thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n c§p ph¡t k¶nh ëng DSA
düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp. Ch÷ìng 3 · xu§t thuªt to¡n tèi ÷u
cæng su§t ph¡t, tèc ë truy·n v · xu§t thuªt to¡n ành tuy¸n k¸t hñp vîi
thuªt to¡n tèi ÷u cæng su§t ph¡t, tèc ë truy·n düa tr¶n n·n t£ng thi¸t k¸
xuy¶n lîp. Cuèi còng, ch÷ìng 4 · xu§t thuªt to¡n ành tuy¸n k¸t hñp vîi
ph÷ìng thùc m¢ m¤ng düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp.
4
Ch֓ng 1
NGHIN CÙU MNG ADHOC A CHNG V THIT
K XUYN LÎP
Ch÷ìng n y ph¥n t½ch nghi¶n cùu m¤ng adhoc a ch°ng, ph¥n t½ch
÷u/nh÷ñc iºm thi¸t k¸ ph¥n lîp v thi¸t k¸ xuy¶n lîp hi»n t¤i kh£ n«ng
¡p döng trong m¤ng adhoc. çng thíi công ph¥n t½ch sü phò hñp ¡p döng
mæ h¼nh thi¸t k¸ xuy¶n lîp trong m¤ng adhoc º n¥ng cao thæng l÷ñng
m¤ng adhoc.
1.1. Têng quan m¤ng adhoc
Hi»n t¤i, gi£i ph¡p truy·n dú li»u ÷ñc chia th nh hai nhâm ch½nh l
m¤ng h¤ t¦ng v m¤ng ngang h ng. Trong â, m¤ng h¤ t¦ng th÷íng ÷ñc
gåi m¤ng t¸ b o v m¤ng ngang h ng th÷íng ÷ñc gåi l m¤ng adhoc. N¸u
nh÷ m¤ng t¸ b o iºn h¼nh l m¤ng ph£i düa tr¶n mët cì sð h¤ t¦ng cõa
dàch vö ¢ ÷ñc x¥y düng y¶u c¦u tr÷îc â nh÷ c¡c nót, router th¼ m¤ng
adhoc l m¤ng bao gçm c¡c nót truy·n dú li»u trüc ti¸p vîi nhau sû döng
bë thu ph¡t khæng d¥y m khæng c¦n b§t cù mët cì sð h¤ t¦ng cè ành
n o. ¥y l xu h÷îng ph¡t triºn gi£i ph¡p truy·n dú li»u hi»n t¤i.
1.2. Thi¸t k¸ ph¥n lîp v xuy¶n lîp
So vîi c¡c m¤ng kh¡c th¼ m¤ng adhoc câ hai °c iºm nêi bªt ti¶u biºu
l "Tü c§u h¼nh" v "Chàu léi". Trong thi¸t k¸ ph¥n lîp th¼ c¡c lîp thüc
hi»n c¡c chùc n«ng ri¶ng bi»t, do c¡c nót trong m¤ng adhoc thay êi li»n
tuc, c¡c ÷íng k¸t nèi thay êi li¶n töc, c¡c tham sè t¤i c¡c lîp £nh h÷ðng
trüc ti¸p ¸n c¡c chùc n«ng ð c¡c lîp kh¡c. Do â, trong m¤ng adhoc, mæ
5
h¼nh thi¸t k¸ ph¥n lîp hi»n t¤i khæng cán phò hñp, y¶u c¦u mæ h¼nh mîi
c¡c lîp câ thº trao êi dú li»u vîi nhau º thüc hi»n c¡c chùc n«ng. º
khc phöc c¡c v§n · tr¶n nh÷ sü thay êi li¶n k¸t, mæ h¼nh m¤ng (do t¡c
ëng cõa sü di ëng) v i·u kiºn nguçn n¥ng cao hi»u n«ng m¤ng, trong
c¡c lîp trong mæ h¼nh mîi c¦n hé trñ c¡c °c iºm nh÷ sau:
•
Chia s´ thæng tin: méi lîp trong mæ h¼nh OSI truy·n thèng hi»n
t¤i c¦n chia s´, cung c§p thæng tin tr¤ng th¡i m¤ng cho c¡c lîp kh¡c.
•
Sü li¶n k¸t giao thùc: c¡c lîp s³ sû döng thæng tin tr¤ng th¡i ÷ñc
cung c§p bði lîp kh¡c º thüc hi»n c¡c chùc n«ng ri¶ng bi»t cõa m¼nh.
C¡c thuªt to¡n düa tr¶n c¡c lîp trong mæ h¼nh OSI câ thº trao êi dú
li»u vîi nhau ÷ñc nghi¶n cùu trong luªn ¡n n y:
• Lîp MAC + lîp NET
• Lîp PHY + lîp NET
• Lîp PHY + lîp MAC + lîp NET
6
Ch֓ng 2
XUT THUT TON ÀNH TUYN KT HÑP
VÎI THUT TON CP PHT KNH ËNG DSA
DÜA TRN NN TNG THIT K XUYN LÎP
Ch÷ìng n y tr¼nh b y möc ½ch v cì ch¸ ho¤t ëng cõa thuªt to¡n
c§p ph¡t k¶nh ëng DSA v · xu§t c¡c thuªt to¡n ành tuy¸n k¸t hñp vîi
thuªt to¡n c§p ph¡t k¶nh ëng DSA düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp.
Luªn ¡n · xu§t ba thuªt to¡n ành tuy¸n bao gçm thuªt to¡n ành tuy¸n
düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp MAC+NET, thuªt to¡n
ành tuy¸n düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp PHY+NET,
thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa ba lîp
PHY+MAC+NET. B¬ng c¡ch sû döng mæ h¼nh mæ phäng minh håa c¡c
thuªt to¡n ành tuy¸n · xu§t n¥ng cao thæng l÷ñng m¤ng.
2.1. Thuªt to¡n c§p ph¡t k¶nh ëng DSA
Thuªt to¡n c§p ph¡t k¶nh ëng DSA sû döng cì ch¸ c§p ph¡t k¶nh düa
tr¶n t½n hi»u b¡o bªn ÷ñc nhªn t¤i nót gûi [68], ngo i ra sû döng ph÷ìng
ph¡p chån k¶nh tèi ÷u £m b£o n¥ng cao hi»u n«ng m¤ng [32], [96], [97],
[98]. Thuªt to¡n ÷ñc chia th nh hai giai o¤n bao gçm:
•
Giai o¤n khði t¤o li¶n k¸t: thüc hi»n thi¸t lªp c¡c k¸t nèi düa
tr¶n tªp c¡c sâng mang con ¢ chån.
•
Giai o¤n c§p ph¡t k¶nh th½ch ùng: tèi ÷u c¡c k¸t nèi düa tr¶n
tªp c¡c sâng mang cån ¢ chån.
7
2.2. Kàch b£n mæ phäng
Kàch b£n mæ phäng, c¡c tham sè s³ ÷ñc lüa chån nh÷ trong b£ng 2.1
chi ti¸t b¶n d÷îi theo chu©n Wimax:
B£ng 2.1: C¡c tham sè trong kàch b£n mæ phäng c¡c thuªt to¡n ành tuy¸n
· xu§t tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa c¡c lîp MAC+NET, PHY+NET,
PHY+MAC+NET
Tham sè
B«ng thæng (B)
Kho£ng thíi gian l§y m¨u
(ta=1/B)
ë d i FFT (NFFT)
Kho£ng Guard (TG)
T¦n sè (fc )
Ph÷ìng ph¡p i·u ch¸
SINR y¶u c¦u tèi thiºu (γreq )
channel_thr
SINR_thr
Gi¡ trà
20 MHz
50 ns
12.8µs
2µs
1.9 GHz
16-QAM
16 dB
42
24 dB
2.3. Thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n
c§p ph¡t k¶nh ëng düa tr¶n n·n t£ng thi¸t k¸
xuy¶n lîp giúa hai lîp MAC+NET
2.3.1. Mæ h¼nh thuªt to¡n
2.3.2. ¡nh gi¡ k¸t qu£
Trong kàch b£n mæ phäng 10 nót, h¼nh 2.2 mæ t£ ë d i cõa c¡c ÷íng
k¸t nèi tèi ÷u ÷ñc lüa chån bði hai thuªt to¡n ành tuy¸n theo tøng b÷îc
di chuyºn, ti¸n tr¼nh mæ phäng ÷ñc chia th nh 3 nhâm A, B v C. Trong
nhâm A, khi m nót nguçn v nót ½ch c¡ch nhau xa, sè l÷ñng nót trung
gian lîn. Do â, vi»c truy·n dú li»u bà £nh h÷ðng lîn bði c¡c nhi¹u çng
k¶nh (CCI) công nh÷ c¡c v§n · v· nót ©n, nót hi»n. K¸t qu£ l sè l÷ñng
k¶nh ÷ñc c§p ph¡t cõa c¡c ÷íng k¸t nèi tø nót nguçn ¸n nót ½ch ·u
nhä hìn gi¡ trà ng÷ïng channel_thr. V¼ vªy, ÷íng k¸t nèi ngn nh§t công
l ÷íng k¸t nèi tèi ÷u. Trong nhâm C, khi m nót nguçn v nót ½ch r§t
8
H¼nh 2.1: Luçng xû lþ cõa thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n c§p ph¡t
k¶nh ëng DSA düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp MAC+NET.
320
310
300
290
280
270
260
250
240
A
230
C
B
220
210
200
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
H¼nh 2.2: ë d i c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði hai thuªt to¡n Dijkstra
v MAC+NET trong kàch b£n mæ phäng.
9
140
135
130
125
120
115
110
105
100
95
90
85
80
75
70
65
C
B
A
60
55
50
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
H¼nh 2.3: Thæng l÷ñng m¤ng ÷ñc lüa chån bði hai thuªt to¡n Dijkstra v
MAC+NET trong kàch b£n mæ phäng.
g¦n nhau, nót nguçn câ thº truy·n dú li»u trüc ti¸p ¸n nót ½ch ho°c qua
mët v i nót trung gian. Sü £nh h÷ðng cõa c¡c v§n · nhi¹u çng k¶nh
(CCI) công nh÷ nót ©n, nót hi»n r§t nhä, do â khæng £nh h÷ðng ¸n sè
l÷ñng k¶nh ÷ñc c§p ph¡t. Sè l÷ñng c¡c k¶nh c§p ph¡t cõa c¡c ÷íng k¸t
nèi ·u lîn hìn gi¡ trà ng÷ïng channel_thr. V¼ vªy, ÷íng k¸t nèi ngn
nh§t công l ÷íng k¸t nèi tèi ÷u. Trong nhâm B, mët v i ÷íng k¸t nèi câ
sè l÷ñng k¶nh c§p ph¡t lîn hìn gi¡ trà ng÷ïng channel_thr, trong khi â
c¡c ÷íng k¸t nèi kh¡c câ sè l÷ñng k¶nh c§p ph¡t nhä hìn gi¡ trà ng÷ïng
channel_thr. Khi â c¡c ÷íng k¸t nèi câ sè l÷ñng k¶nh lîn hìn gi¡ trà
ng÷ïng channel_thr s³ ÷ñc lüa chån l ÷íng k¸t nèi tèi ÷u. Trong nhâm
B c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði thuªt to¡n ành tuy¸n ·
xu§t câ ë d i lîn hìn so vîi ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði thuªt
to¡n ành tuy¸n t¼m ÷íng ngn nh§t Dijkstra, trong khi â thæng l÷ñng
cõa m¤ng sû döng thuªt to¡n ành tuy¸n · xu§t ÷ñc n¥ng cao hìn nhi·u.
2.4. Thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n
c§p ph¡t k¶nh ëng DSA düa tr¶n n·n t£ng
xuy¶n lîp giúa hai lîp PHY+NET
2.4.1. Mæ h¼nh thuªt to¡n
2.4.2. ¡nh gi¡ k¸t qu£
H¼nh 2.5 mæ t£ ë d i cõa ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði hai
thuªt to¡n ành tuy¸n theo tøng b÷îc di chuyºn, ti¸n tr¼nh mæ phäng ÷ñc
10
H¼nh 2.4: Luçng xû lþ cõa thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n c§p ph¡t
k¶nh ëng DSA düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp PHY+NET.
320
310
300
290
280
270
260
250
240
230
C
B
A
220
210
200
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
H¼nh 2.5: ë d i c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði hai thuªt to¡n Dijkstra
v PHY+NET.
11
chia th nh 3 nhâm A, B v C. Trong nhâm A, khi m nót nguçn v nót
½ch c¡ch nhau xa, sè l÷ñng nót trung gian lîn. Do â, vi»c truy·n dú li»u
bà £nh h÷ðng lîn bði c¡c nhi¹u çng k¶nh (CCI) công nh÷ c¡c v§n · v·
nót ©n v nót hi»n. K¸t qu£ l gi¡ trà Average SINR cõa c¡c ÷íng k¸t nèi
tø nót nguçn ¸n nót ½ch ·u nhä hìn gi¡ trà ng÷ïng SINR_thr. V¼ vªy,
÷íng k¸t nèi ngn nh§t công l ÷íng k¸t nèi tèi ÷u. Trong nhâm C, khi
m nót nguçn v nót ½ch r§t g¦n nhau, nót nguçn câ thº truy·n dú li»u
trüc ti¸p ¸n nót ½ch ho°c qua mët v i nót trung gian. Sü £nh h÷ðng cõa
c¡c v§n · nhi¹u çng k¶nh (CCI) công nh÷ nót ©n, nót hi»n r§t nhä, do â
khæng £nh h÷ðng ¸n sè l÷ñng k¶nh c§p ph¡t. Tham sè Average SINR cõa
c¡c ÷íng k¸t nèi ·u lîn hìn gi¡ trà ng÷ïng SINR_thr. V¼ vªy, ÷íng k¸t
nèi ngn nh§t công l ÷íng k¸t nèi tèi ÷u. Trong nhâm B, mët v i ÷íng
k¸t nèi câ sè tham sè Average SINR lîn hìn gi¡ trà ng÷ïng SINR_thr,
trong khi â c¡c ÷íng k¸t nèi kh¡c câ tham sè Average SINR nhä hìn
gi¡ trà ng÷ïng SINR_thr. Trong nhâm B c¡c ÷íng k¸t nèi tèi ÷u ÷ñc
lüa chån bði thuªt to¡n ành tuy¸n · xu§t câ ë d i lîn hìn so vîi ÷íng
k¸t nèi tèi ÷u ÷ñc lüa chån bði thuªt to¡n ành tuy¸n t¼m ÷íng ngn
nh§t Dijkstra, trong khi â thæng l÷ñng cõa m¤ng sû döng thuªt to¡n ành
tuy¸n · xu§t ÷ñc n¥ng cao hìn nhi·u.
140
135
130
125
120
115
110
105
100
95
90
85
80
75
70
65
C
B
A
60
55
50
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
H¼nh 2.6: Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði hai thuªt
to¡n Dijkstra v PHY+NET.
dcd
12
2.5. Thuªt to¡n xuy¶n lîp PHY+MAC+NET
2.5.1. Mæ h¼nh thuªt to¡n
2.5.2. ¡nh gi¡ k¸t qu£
H¼nh 2.7: Luçng xû lþ cõa thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n
c§p ph¡t k¶nh ëng DSA düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa ba lîp
PHY+MAC+NET.
H¼nh 2.8 mæ t£ ë d i cõa ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði bèn
thuªt to¡n ành tuy¸n theo tøng b÷îc di chuyºn, ti¸n tr¼nh mæ phäng ÷ñc
chia th nh 4 nhâm A, B, C, D v E. Trong nhâm A, khi m nót nguçn v
½ch c¡ch nhau xa, sè l÷ñng nót trung gian lîn. Do â, vi»c truy·n dú li»u
bà £nh h÷ðng lîn bði c¡c nhi¹u çng k¶nh (CCI) công nh÷ c¡c v§n · v·
nót ©n, nót hi»n. K¸t qu£ l gi¡ trà Average SINR cõa c¡c ÷íng k¸t nèi
tø nót nguçn ¸n nót ½ch ·u nhä hìn gi¡ trà ng÷ïng SINR_thr v çng
thíi gi¡ trà N_ch sè l÷ñng k¶nh ÷ñc c§p ph¡t cõa c¡c ÷íng k¸t nèi tø
13
320
310
300
290
280
270
260
250
240
230
C
B
D
A
220
E
210
200
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
H¼nh 2.8: ë d i c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði ba thuªt to¡n Dijkstra,
MAC+NET, PHY+NET v PHY+MAC+NET.
nót nguçn ¸n nót ½ch ·u nhä hìn gi¡ trà ng÷ïng channel_thr. V¼ vªy,
÷íng k¸t nèi ngn nh§t công l ÷íng k¸t nèi tèi ÷u. Trong nhâm C, khi
m nót nguçn v nót ½ch r§t g¦n nhau, nót nguçn câ thº truy·n dú li»u
trüc ti¸p ¸n nót ½ch ho°c qua mët v i nót trung gian. Sü £nh h÷ðng cõa
c¡c v§n · nhi¹u çng k¶nh (CCI) công nh÷ nót ©n, nót hi»n r§t nhä, do
â khæng £nh h÷ðng ¸n sè l÷ñng k¶nh c§p ph¡t. Gi¡ trà Average SINR cõa
c¡c ÷íng k¸t nèi ·u lîn hìn gi¡ trà ng÷ïng SINR_thr v gi¡ trà N_ch sè
l÷ñng k¶nh ÷ñc c§p ph¡t cõa c¡c ÷íng k¸t nèi tø nót nguçn ¸n nót ½ch
·u lîn hìn gi¡ trà ng÷ïng channel_thr. V¼ vªy, ÷íng k¸t nèi ngn nh§t
công l ÷íng k¸t nèi tèi ÷u. Trong nhâm B, mët v i ÷íng k¸t nèi câ gi¡
trà Average SINR lîn hìn gi¡ trà ng÷ïng SINR_thr, trong khi â c¡c ÷íng
k¸t nèi kh¡c câ gi¡ trà SINR nhä hìn gi¡ trà ng÷ïng SINR_thr v mët v i
÷íng k¸t nèi câ gi¡ trà N_ch sè l÷ñng k¶nh ÷ñc c§p ph¡t tø nót nguçn
¸n nót ½ch lîn hìn gi¡ trà ng÷ïng channel_thr, trong khi â c¡c ÷íng
k¸t nèi kh¡c câ gi¡ trà N_ch sè l÷ñng k¶nh c§p ph¡t nhä hìn gi¡ trà ng÷ïng
channel_thr. Trong nhâm D, E câ mët v i ÷íng k¸t nèi câ gi¡ trà Average
SINR lîn hìn gi¡ trà ng÷ïng SINR_thr, trong khi â c¡c ÷íng k¸t nèi
kh¡c câ tham sè Average SINR nhä hìn gi¡ trà ng÷ïng SINR_th tuy nhi¶n
t§t c£ c¡c ÷íng k¸t nèi ·u câ gi¡ trà N_ch sè l÷ñng k¶nh ÷ñc c§p ph¡t
tø nót nguçn ¸n nót ½ch ·u nhä hìn gi¡ trà ng÷ïng channel_thr. Trong
nhâm D, E câ thº th§y ë d i ÷íng k¸t nèi ÷ñc lüa chån bði thuªt to¡n
ành tuy¸n t¼m ÷íng ngn nh§t Dijkstra tròng vîi thuªt to¡n ành tuy¸n
düa tr¶n n·n t£ng thi¸t xuy¶n lîp giúa hai lîp MAC+NET v nhä hìn ë
d i ÷íng k¸t nèi ÷ñc lüa chån bði thuªt to¡n ành tuy¸n düa tr¶n n·n
t£ng xuy¶n lîp giúa hai lîp PHY+NET.
14
140
135
130
125
120
115
110
105
100
95
90
85
80
75
70
65
A
60
E
B
D
C
55
50
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
H¼nh 2.9: Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði ba thuªt
to¡n Dijkstra, MAC+NET, PHY+NET v PHY+MAC+NET.
Theo c¡c h¼nh 2.8, 2.9 câ thº nhªn th§y trong nhâm B, c¡c ÷íng k¸t
nèi tèi ÷u ÷ñc lüa chån bði c¡c thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng
thi¸t k¸ xuy¶n lîp · xu§t câ ë d i lîn hìn so vîi ÷íng k¸t nèi tèi ÷u
÷ñc lüa chån bði thuªt to¡n ành tuy¸n t¼m ÷íng ngn nh§t Dijkstra,
trong khi â thæng l÷ñng cõa m¤ng sû döng thuªt to¡n ành tuy¸n düa
tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp º xu§t ÷ñc n¥ng cao hìn, k¸t qu£ mæ
phäng minh håa r¬ng thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng thi¸t k¸
xuy¶n lîp giúa ba lîp PHY+MAC+NET n¥ng cao thæng l÷ñng m¤ng cao
nh§t so vîi hai thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng thi¸t k¸ xuy¶n
lîp giúa hai lîp PHY+NET v lîp MAC+NET, thuªt to¡n ành tuy¸n t¼m
÷íng ngn nh§t Dijkstra. C¡c thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng
thi¸t k¸ xuy¶n lîp giúa hai lîp PHY+NET v lîp MAC+NET câ k¸t qu£
thæng l÷ñng t÷ìng tü nhau nh÷ng công ¢ n¥ng cao thæng l÷ñng m¤ng so
vîi thuªt to¡n ành tuy¸n t¼m ÷íng ngn nh§t Dijkstra. Trong nhâm A,
C th¼ do ÷íng tèi ÷u ÷ñc lüa chån công l ÷íng ngn nh§t do â thæng
l÷ñng cõa c¡c thuªt to¡n ành tuy¸n b¬ng nhau. Trong nhâm D, E, thæng
l÷ñng cõa thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa
hai lîp PHY+NET cao hìn so vîi thuªt to¡n ành tuy¸n t¼m ÷íng ngn
nh§t Dijkstra. Do â, k¸t luªn thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng
thi¸t k¸ xuy¶n lîp giúa ba lîp PHY+MAC+NET n¥ng cao thæng l÷ñng
nh§t so vîi c¡c thuªt to¡n ành tuy¸n düa tr¶n n·n t£ng thi¸t k¸ xuy¶n
lîp giúa hai lîp PHY+NET, lîp MAC+NET v thuªt to¡n ành tuy¸n t¼m
÷íng ngn nh§t Dijkstra.
15
Ch֓ng 3
XUT THUT TON ÀNH TUYN KT HÑP
VÎI THUT TON TÈI ×U CÆNG SUT PHT V
TÈC Ë TRUYN DÜA TRN NN TNG THIT
K XUYN LÎP
Ch÷ìng n y ph¥n t½ch £nh h÷ðng v · xu§t thuªt to¡n tèi ÷u cæng
su§t ph¡t v tèc ë truy·n t¤i lîp PHY v thuªt to¡n ành tuy¸n k¸t hñp
vîi thuªt to¡n tèi ÷u cæng su§t ph¡t v tèc ë truy·n düa tr¶n n·n t£ng
thi¸t k¸ xuy¶n lîp
3.1. · xu§t thuªt to¡n tèi ÷u cæng su§t v tèc ë
truy·n t¤i lîp PHY
Ch¿ sè thæng l÷ñng ÷íng truy·n Indexthr l mët h m phö thuëc v o
hai tham sè cæng su§t ph¡t pt v tèc ë truy·n r. Luªn ¡n · xu§t thuªt
to¡n tèi ÷u cæng su§t ph¡t pt v tèc ë truy·n r sao cho Indexthr l lîn
nh§t cö thº nh÷ sau:
16
H¼nh 3.1: Thuªt to¡n tèi ÷u cæng su§t ph¡t v tèc ë truy·n.
17
3.2. Thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n
tèi ÷u cæng su§t ph¡t v tèc ë truy·n tr¶n n·n
t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp PHY+NET
3.2.1. Mæ h¼nh thuªt to¡n
3.2.2. Kàch b£n mæ phäng
H¼nh 3.2: Luçng xû lþ cõa thuªt to¡n ành tuy¸n k¸t hñp vîi thuªt to¡n tèi ÷u
cæng su§t ph¡t v tèc ë truy·n düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp
PHY+NET.
Trong kàch b£n mæ phäng, luªn ¡n sû döng cæng cö mæ phäng l NS2 º
thüc hi»n minh håa c¡c k¸t qu£ c¡c · xu§t. Kàch b£n mæ phäng, luªn ¡n
sû döng cæng cö NS2 v lîp PHY, lîp MAC theo chu©n 802.11b ÷ñc ph¡t
triºn bði CMU group [42], [61] mæ phäng mæ h¼nh ph¡t Ricean v Rayleigh
[76]. Trong mæ h¼nh mæ phäng, lo¤i card m¤ng vîi c¡c tham sè mùc n«ng
18
- Xem thêm -