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
LUN N TIN S Kß THUT VIN THÆNG
H NËI - 2019
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
LUN N TIN S Kß THUT VIN THÆNG
Ng nh: Kß THUT VIN THÆNG
M¢ sè: 9520208
GIO VIN H×ÎNG DN KHOA HÅC:
PGS.TS NGUYN VN ÙC
H NËI - 2019
LÍI CAM OAN
Tæi xin cam oan c¡c k¸t qu£ tr¼nh b y trong luªn ¡n "ành tuy¸n n¥ng
cao thæng l÷ñng m¤ng düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp cho m¤ng adhoc"
l cæng tr¼nh nghi¶n cùu cõa tæi d÷îi sü h÷îng d¨n cõa c¡n bë h÷îng d¨n.
Tæi xin cam k¸t r¬ng:
• C¡c k¸t qu£ trong luªn ¡n ÷ñc thüc hi»n trong thíi gian nghi¶n cùu v
thüc hi»n luªn ¡n ti¸n sÿ t¤i ¤i håc B¡ch khoa H Nëi.
• C¡c sè li»u, k¸t qu£ tr¼nh b y trong luªn ¡n l ho n to n trung thüc v
ch÷a ÷ñc cæng bè trong b§t ký cæng tr¼nh n o tr÷îc ¥y. C¡c k¸t qu£ sû
döng tham kh£o ·u ¢ ÷ñc tr½ch d¨n ¦y õ v theo óng quy ành.
H Nëi, ng y
Gi¡o vi¶n h÷îng d¨n khoa håc
PGS.TS Nguy¹n V«n ùc
th¡ng
n«m 2019
T¡c gi£
Nguy¹n Quang Kh¡nh
LÍI CM ÌN
Luªn ¡n ti¸n sÿ n y ÷ñc nghi¶n cùu sinh thüc hi»n t¤i Bë mæn Kÿ thuªt
thæng tin, Vi»n i»n tû vi¹n thæng, ¤i håc B¡ch khoa H Nëi d÷îi sü h÷îng
d¨n khoa håc cõa PGS.TS Nguy¹n V«n ùc. Nghi¶n cùu sinh xin ÷ñc b y tä
láng bi¸t ìn s¥u sc èi vîi th¦y v· ành h÷îng khoa håc, ch¿ d¨n thüc hi»n
nhúng nhi»m vö c¦n thi¸t công nh÷ t¤o måi i·u ki»n thuªn lñi · cæng tr¼nh
nghi¶n cùu n y ÷ñc ho n th nh.
Nghi¶n cùu sinh công xin tr¥n trång c£m ìn L¢nh ¤o tr÷íng ¤i håc B¡ch
Khoa H Nëi, Vi»n o t¤o Sau ¤i håc, Vi»n i»n tû vi¹n thæng, Bë mæn Kÿ
thuªt thæng tin ¢ t¤o i·u ki»n thuªn lñi º tëi ho n th nh nhi»m vö cõa m¼nh
trong suèt qu¡ tr¼nh håc tªp v nghi¶n cùu.
Nghi¶n cùu sinh công xin tr¥n trång c£m ìn th¦y H Duy¶n Trung, Nguy¹n
Ti¸n Háa, Vi»n i»n tû vi¹n thæng ¢ hé trñ qu¡ tr¼nh ch¿nh sûa luªn ¡n.
Cuèi còng, tæi công b y láng bi¸t ìn ¸n gia ¼nh, b¤n b± ¢ õng hë v ëng
vi»n gióp ï tæi trong thíi gian l m luªn ¡n.
H Nëi, ng y
th¡ng
T¡c gi£
n«m 2019
Nguy¹n Quang Kh¡nh
Möc löc
MÖC LÖC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
DANH MÖC CC TØ VIT TT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
DANH MÖC HNH V. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
DANH MÖC BNG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
DANH MÖC CC KÞ HIU TON HÅC. . . . . . . . . . . . . . . . . . . . xiv
GIÎI THIU LUN N. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Ch÷ìng 1. NGHIN CÙU MNG ADHOC V THIT K XUYN
LÎP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1. Têng quan m¤ng adhoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.1.1. Kh¡i ni»m m¤ng adhoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.1.2. °c iºm m¤ng adhoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.1.3. Ùng döng cõa m¤ng adhoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.1.4. ¡nh gi¡ c¡c v§n · hi»n t¤i cõa m¤ng adhoc . . . . . . . . . . . . . . . . . .
15
1.2. Thi¸t k¸ ph¥n lîp v xuy¶n lîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
1.2.1. Thi¸t k¸ ph¥n lîp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Mæ h¼nh OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Mæ h¼nh TCP/IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
1.2.2. Thi¸t k¸ xuy¶n lîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
Têng quan thi¸t k¸ xuy¶n lîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
°c iºm thi¸t k¸ xuy¶n lîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
1.3. K¸t luªn ch÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
i
ii
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 . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1. Thuªt to¡n c§p ph¡t k¶nh ëng DSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.1.1. V§n · nót ©n, nót hi»n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
V§n · nót ©n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
V§n · nót hi»n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Ph÷ìng ¡n khc phöc v§n · nót ©n/nót hi»n . . . . . . . . . . . . . . . . . . . . . . . .
27
2.1.2. Thuªt to¡n c§p ph¡t k¶nh ëng DSA . . . . . . . . . . . . . . . . . . . . . . . . . .
28
V§n · nhi¹u çng k¶nh (CCI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
Cì ch¸ c§p ph¡t k¶nh düa tr¶n t½n hi»u b¡o bªn . . . . . . . . . . . . . . . . . . . . .
29
Thuªt to¡n c§p ph¡t k¶nh ëng DSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.2. · xu§t 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 . . . .
35
2.2.1. Ma trªn k¸t nèi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.2.2. Thuªt to¡n ành tuy¸n ph¥n lîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
2.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
DSA tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp MAC+NET . . . . . .
37
ành ngh¾a c¡c tham sè cõa thuªt to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
Mæ h¼nh cõa thuªt to¡n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
Kàch b£n mæ phäng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
2.2.4. ¡nh gi¡ k¸t qu£ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
2.3. · xu§t 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. . . . .
48
2.3.1. 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 . .
48
ành ngh¾a c¡c tham sè cõa thuªt to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
Mæ h¼nh cõa thuªt to¡n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
Kàch b£n mæ phäng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
2.3.2. ¡nh gi¡ k¸t qu£ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
iii
2.4. · xu§t 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 c¡c lîp PHY+MAC+NET . .
55
2.4.1. 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 c¡c lîp PHY+MAC+NET
55
ành ngh¾a c¡c tham sè cõa thuªt to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
Mæ h¼nh cõa thuªt to¡n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
Kàch b£n mæ phäng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
2.4.2. ¡nh gi¡ k¸t qu£ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
2.5. K¸t luªn ch÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
3.1. nh h÷ðng cõa cæng su§t ph¡t, tèc ë truy·n ¸n thæng l÷ñng m¤ng
72
3.1.1. Mèi quan h» giúa tèc ë truy·n v thæng l÷ñng m¤ng . . . . . . . . . .
72
3.1.2. Mèi quan h» giúa cæng su§t ph¡t v thæng l÷ñng m¤ng . . . . . . . . .
73
Mèi quan h» giúa cæng su§t ph¡t, nhi¹u v thæng l÷ñng l÷ñng . . . . . . . .
73
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 72
Mèi quan h» giúa cæng su§t ph¡t, t l» léi trong m¤ng v thæng l÷ñng m¤ng
73
3.1.3. K¸t luªn mèi quan h» giúa cæng su§t ph¡t, tèc ë truy·n v thæng
l÷ñng m¤ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
3.2. · 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
74
3.2.1. Ph÷ìng thùc x¡c ành nót l¥n cªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
3.2.2. · xu§t mæ h¼nh ¡nh gi¡ ch¿ sè nhi¹u IndexI . . . . . . . . . . . . . . . . .
75
3.2.3. · xu§t mæ h¼nh ¡nh gi¡ ch¿ sè léi IndexF . . . . . . . . . . . . . . . . . . . .
76
3.2.4. Thuªt to¡n tèi ÷u cæng su§t ph¡t v tèc ë truy·n . . . . . . . . . . . . .
77
· xu§t t½nh ch¿ sè thæng l÷ñng hai nót li¶n k¸t trüc ti¸p . . . . . . . . . . . .
77
· xu§t thuªt to¡n tèi ÷u ch¿ sè thæng l÷ñng hai nót li¶n k¸t trüc ti¸p
78
· xu§t t½nh ch¿ sè thæng l÷ñng ÷íng truy·n . . . . . . . . . . . . . . . . . . . . . . . .
80
iv
3.3. · 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 xuy¶n lîp giúa hai lîp PHY+NET . . .
81
3.3.1. Ma trªn giúa c¡c nót . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
Ma trªn li¶n k¸t giúa c¡c nót . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
Ma trªn gi¡ trà tèi ÷u ch¿ sè thæng l÷ñng giúa c¡c nót . . . . . . . . . . . . . . . .
81
3.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 düa tr¶n n·n t£ng thi¸t k¸ xuy¶n lîp giúa hai lîp PHY+NET
82
ành ngh¾a c¡c tham sè cõa thuªt to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
Mæ h¼nh cõa thuªt to¡n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
Kich b£n mæ phäng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
3.3.3. ¡nh gi¡ k¸t qu£ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
¡nh gi¡ hi»u qu£ thuªt to¡n ành tuy¸n · xu§t vîi thuªt to¡n ành tuy¸n
DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
¡nh gi¡ hi»u qu£ thuªt to¡n ành tuy¸n · xu§t vîi thuªt to¡n ành tuy¸n
DSDV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
¡nh gi¡ hi»u qu£ thuªt to¡n ành tuy¸n · xu§t vîi thuªt to¡n ành tuy¸n
Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
Têng hñp ¡nh gi¡ hi»u qu£ thuªt to¡n ành tuy¸n · xu§t vîi thuªt to¡n
ành tuy¸n DSR, DSDV, Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
3.4. K¸t luªn ch÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
4.1. Têng quan ph÷ìng thùc m¢ m¤ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
4.1.1. Kh¡i ni»m ph÷ìng thùc m¢ m¤ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
Ch÷ìng 4. XUT THUT TON ÀNH TUYN KT HÑP VÎI
PH×ÌNG THÙC M MNG, THUT TON CP PHT KNH
ËNG DSA DÜA TRN NN TNG THIT K XUYN LÎP . .
91
Sü kh¡c nhau giúa ph÷ìng thùc m¢ m¤ng v ph÷ìng thùc "store and forward" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
×u iºm cõa ph÷ìng thùc m¢ m¤ng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
Nh÷ñc iºm cõa ph÷ìng thùc m¢ m¤ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
v
4.1.2. M¢ m¤ng tuy¸n t½nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
4.1.3. Gi£i ph¡p x¥y düng ph÷ìng thùc m¢ m¤ng ¡p döng thüc t¸. . .
100
M¢ m¤ng tuy¸n t½nh ng¨u nhi¶n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101
ành d¤ng gâi tin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101
Mæ h¼nh Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103
4.2. · 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 . . .
108
4.2.1. 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 . . . . . .
108
ành ngh¾a c¡c tham sè cõa thuªt to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
Mæ h¼nh cõa thuªt to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
109
Kich b£n mæ phäng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
111
4.2.2. ¡nh gi¡ k¸t qu£ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
116
4.3. K¸t luªn ch÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
120
KT LUN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
DANH MÖC CC CÆNG TRNH CÆNG BÈ . . . . . . . . . . . 126
DANH MÖC CC TØ VIT TT
Vi¸t tt
T¶n ti¸ng Anh
T¶n ti¸ng Vi»t
ACC
Access layer
Lîp truy cªp
ADHOC
Adhoc network
M¤ng tòy bi¸n khæng d¥y
AODV
Ad hoc On Demand
Giao thùc AODV
Distance Vector
APP
Application layer
Lîp ùng döng
CCI
Co channel Interference
Nhi¹u çng k¶nh
CSMA/CA
Carrier Sense Multiple Access
Cì ch¸ chèng xung ët
with Collision Avoidance
k¶nh
Decentralized Dynamic
Thuªt to¡n c§p ph¡t
Sub Channel Assignment
k¶nh ëng
Destination Sequenced
Giao thùc DSDV
DSA
DSDV
Distance Vector
IEEE
Institute of Electrical
Vi»n cæng ngh» Kÿ s÷
and Electronics Engineers
i»n v i»n tû
INT
Internet layer
Lîp Internet
OFDM
Orthogonal frequency
Gh²p k¶nh ph¥n chia
division multiplexing
t¦n sè trüc giao
Orthogonal frequency
a truy cªp ph¥n chia
division multiple access
t¦n sè trüc giao
Open Systems
Mæ h¼nh OSI
OFDMA
OSI model
Interconnection model
PHY
Physical layer
Lîp vªt lþ
PRE
Presentation layer
Lîp tr¼nh di¹n
QoS
Quality of Service
Ch§t l÷ñng dàch vö
MAC
MAC layer
Lîp li¶n k¸t dú li»u
MS
Mobile Station
Nót truy·n nhªn
vi
vii
NET
Network layer
Lîp m¤ng
RTS/CTS
Request to Send and
Cì ch¸ t¼m k¶nh
Clear to Send
truy·n
Rx
Reception
H÷îng nhªn
SES
Session layer
Lîp phi¶n
SINR
Signal to interference
T sè t½n hi»u tr¶n
plus noise ratio
t¤p ¥m cëng nhi¹u
TCP/IP model TCP/IP model
Mæ h¼nh TCP/IP
TDD
Ph¥n k¶nh theo khe
Time Division Duplexing
thíi gian
TDMA
Time Division Multiple Access a truy cªp ph¥n
chia thíi gian
TRA
Transport layer
Lîp vªn chuyºn
Tx
Transmission
H÷îng truy·n
WIFI
Wireless Fidelity
M¤ng khæng d¥y
WiMAX
Worldwide Interoperability
M¤ng Wimax
for Microwave Acess
Danh s¡ch h¼nh v³
1.1
Mæ h¼nh m¤ng t¸ b o. . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2
Mæ h¼nh m¤ng adhoc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3
Mæ h¼nh OSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4
Mæ h¼nh TCP/IP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5
So s¡nh giúa thi¸t k¸ ph¥n lîp v xuy¶n lîp. . . . . . . . . . . . . . . 22
2.1
V§n · nót ©n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2
V§n · nót hi»n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3
Nhi¹u çng k¶nh (CCI) trong h» thèng OFDMA/TDD [99]. . . . . . 28
2.4
Cæng su§t ¥m bªn thu ÷ñc t¤i nót truy·n v nót nhªn [99]. . . . . . 29
2.5
Cì ch¸ truy·n dú li»u t¤i nót truy·n [99]. . . . . . . . . . . . . . . . . 30
2.6
Cì ch¸ nhªn dú li»u t¤i nót nhªn [99]. . . . . . . . . . . . . . . . . . . 31
2.7
Thuªt to¡n c§p ph¡t k¶nh ëng DSA [99]. . . . . . . . . . . . . . . . . 32
2.8
Ma trªn k¸t nèi trong m¤ng. . . . . . . . . . . . . . . . . . . . . . . . . 37
2.9
Luçng xû lþ cõa thuªt to¡n ành tuy¸n t¼m ÷íng ngn nh§t Dijkstra.38
2.10 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. . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.11 C¡c ÷íng k¸t nèi trong kàch b£n mæ phäng MAC+NET (06 nót). . 42
2.12 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 (06 nót). . . . . . . . . . . . 43
2.13 C¡c ÷íng k¸t nèi trong kàch b£n mæ phäng MAC+NET (10 nót). . 44
2.14 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 (10 nót). . . . . . . . . . . . 45
2.15 ë 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 (06 nót). . . . . . . 46
2.16 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 (06 nót). . . . . . . . . . . . . . 46
viii
ix
2.17 ë 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 (10 nót). . . . . . . 47
2.18 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 (10 nót). . . . . . . . . . . . . . 48
2.19 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. . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.20 C¡c ÷íng k¸t nèi trong kàch b£n mæ phäng PHY+NET. . . . . . . . 52
2.21 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.22 ë 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. . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.23 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. . . . . . . . . . . . . . . . . . 55
2.24 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. . . . . . . . . . . . . . . . . . . . . . . 58
2.25 C¡c ÷íng k¸t nèi kàch b£n mæ phäng PHY+MAC+NET. . . . . . . 60
2.26 C¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði bèn thuªt to¡n Dijkstra, MAC+NET, PHY+NET v PHY+MAC+NET. . . . . . . . . . 61
2.27 C¡c ÷íng k¸t nèi trong kàch b£n mæ phäng MAC+PHY+NET
(30 nót). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.28 C¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði bèn thuªt to¡n Dijkstra, MAC+NET, PHY+NET v PHY+MAC+NET (30 nót). . . . . 63
2.29 ë d i c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði bèn thuªt to¡n
Dijkstra, MAC+NET, PHY+NET v PHY+MAC+NET. . . . . . . . 66
2.30 Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði bèn
thuªt to¡n Dijkstra, MAC+NET, PHY+NET v PHY+MAC+NET. 66
2.31 ë d i c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði bèn thuªt to¡n
Dijkstra, MAC+NET, PHY+NET v PHY+MAC+NET (30 nót). . 69
2.32 Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði bèn
thuªt to¡n Dijkstra, MAC+NET, PHY+NET v PHY+MAC+NET
(30 nót). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
x
3.1
Thuªt to¡n tèi ÷u cæng su§t ph¡t v tèc ë truy·n. . . . . . . . . . . 79
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. . . . . . . . . . . . . . . . . . . . . 83
3.3
Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði
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 v thuªt to¡n ành tuy¸n DSR. . . . . . . . . . . 86
3.4
Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði
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 v thuªt to¡n ành tuy¸n DSDV. . . . . . . . . . 87
3.5
Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði
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 v thuªt to¡n ành tuy¸n Dijkstra. . . . . . . . . 88
3.6
Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån 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 v thuªt to¡n ành tuy¸n DSR, DSDV, Dijkstra vîi
sè nót tø 30-120 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.7
Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån 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 v thuªt to¡n ành tuy¸n DSR, DSDV, Dijkstra vîi
sè nót tø 30-250 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.1
Mæ h¼nh truy·n dú li»u theo ph÷ìng thùc "store and forward" vîi
hai k¸t nèi tø nót W ¸n nót X. . . . . . . . . . . . . . . . . . . . . . . 93
4.2
Mæ h¼nh truy·n dú li»u theo ph÷ìng thùc "store and forward" vîi
mët k¸t nèi tø nót W ¸n nót X trong ìn và thíi gian ¦u ti¶n. . . 94
4.3
Mæ h¼nh truy·n dú li»u theo ph÷ìng thùc "store and forward" vîi
mët k¸t nèi tø nót W ¸n nót X trong ìn và thíi gian ti¸p theo. . . 94
xi
4.4
Mæ h¼nh truy·n dú li»u theo ph÷ìng thùc m¢ m¤ng vîi mët k¸t
nèi tø nót W ¸n nót X. . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.5
Mæ h¼nh truy·n dú li»u theo ph÷ìng thùc "store and forward" vîi
hai k¸t nèi tø nót W ¸n nót X tr÷íng hñp hai nguçn. . . . . . . . . 96
4.6
Mæ h¼nh truy·n dú li»u theo ph÷ìng thùc "store and forward" vîi
mët k¸t nèi tø nót W ¸n nót X trong ìn và thíi gian ¦u ti¶n
tr÷íng hñp hai nguçn. . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.7
Mæ h¼nh truy·n dú li»u theo ph÷ìng thùc "store and forward" vîi
mët k¸t nèi tø nót W ¸n nót X trong ìn và thíi gian ti¸p theo
tr÷íng hñp hai nguçn. . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.8
Mæ h¼nh truy·n dú li»u theo ph÷ìng thùc m¢ m¤ng vîi mët k¸t
nèi tø nót W ¸n nót X trong tr÷íng hñp hai nguçn. . . . . . . . . . 97
4.9
Mæ h¼nh m¢ m¤ng tuy¸n t½nh. . . . . . . . . . . . . . . . . . . . . . . . 99
4.10 C§u tróc b£n tin m¢ hâa. . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.11 Mæ h¼nh Acyclic network. . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.12 Mæ h¼nh Cyclic network. . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.13 C¡c ÷íng kh¡c nhau s³ câ ë tr¹ kh¡c nhau. . . . . . . . . . . . . . . 107
4.14 Sü £nh h÷ðng cõa ë tr¹ ¸n mæ h¼nh buffer. . . . . . . . . . . . . . . 107
4.15 Luçng xû lþ 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 giúa hai lîp MAC+NET. . . . . . . . . . . . . . . . 110
4.16 C¡c k¸t nèi trong kàch b£n mæ phäng MAC+NET+NETWORK
CODING. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.17 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 v MAC+NET+NETWORK CODING trong kàch
b£n mæ phäng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.18 C¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði n«m thuªt to¡n Dijkstra, MAC+NET, PHY+NET, PHY+MAC+NET v MAC+NET+NETWORK
CODING trong kàch b£n mæ phäng . . . . . . . . . . . . . . . . . . . . 117
4.19 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 v MAC+NET+NETWORK
CODING. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
xii
4.20 Thæng l÷ñng m¤ng c¡c ÷íng k¸t nèi tèi ÷u ÷ñc lüa chån bði n«m
thuªt to¡n Dijkstra, MAC+NET, PHY+NET, PHY+MAC+NET
v MAC+NET+NETWORK CODING. . . . . . . . . . . . . . . . . . 120
Danh s¡ch b£ng
2.1
C¡c tham sè trong kàch b£n mæ phäng 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: . . . . . . . . . . . . . . . 40
2.2
C¡c tham sè trong kàch b£n mæ phäng 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: . . . . . . . . . . . . . . . 50
2.3
C¡c tham sè trong kàch b£n mæ phäng 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: . . . . . . . . . . . 59
3.1
C¡c tham sè card m¤ng trong kàch b£n mæ phäng 802.11 . . . . . . . 84
3.2
C¡c tham sè thæng tin m¤ng trong kàch b£n mæ phä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 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: 85
3.3
C¡c tham sè thæng tin m¤ng trong kàch b£n mæ phä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 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: 85
4.1
C¡c tham sè trong kàch b£n mæ phäng 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 giúa hai lîp MAC+NET . 112
xiii
DANH MÖC CC KÞ HIU TON HÅC
Kþ hi»u
Þ ngh¾a
a
Bi¸n sè
|a|
Gi¡ trà tuy»t èi cõa bi¸n a
ai,j
Ph¦n tû h ng thù i cët thù j cõa ma
trªn A
A
Ma trªn A
Average SIN R
Trung b¼nh c¡c SINR c¡c k¶nh tr¶n ÷íng k¸t
nèi ngn nh§t tø nót nguçn ¸n nót ½ch tr¶n
m¤ng b¬ng c¡ch sû döng thuªt to¡n Dijkstra
B
B«ng thæng k¶nh truy·n
channel_thr
Gi¡ trà mùc ng÷ïng cho tr÷îc thº hi»n sè
l÷ñng k¶nh tèi ÷u khi thüc hi»n truy·n c¡c
khung dú li»u
d
Nót ½ch
d(i, j)
Kho£ng c¡ch giúa h¤i nót i v nót j câ thº
truy·n dú li»u cho nhau
i(r)
Ch¿ sè nh¤y c£m vîi tèc ë truy·n i
IndexI (i, j)
Ch¿ sè nhi¹u giúa hai nót i v nót j
IndexF (i, j)
Ch¿ sè léi giúa hai nót i v nót j
I _th
Gi¡ trà nùc ng÷ïng nhi¹u
N _ch
Sè l÷ñng k¶nh ÷ñc c§p ph¡t tr¶n ÷íng k¸t
xiv
xv
nèi ngn nh§t tø nót nguçn ¸n nót ½ch
b¬ng c¡ch sû döng thuªt to¡n Dijkstra
N _root
Sè l÷ñng c¡c ÷íng k¸t nèi tø nót nguçn
¸n nót ½ch tr¶n m¤ng b¬ng c¡ch sû döng
ma trªn k¸t nèi M
min(a, b)
Gi¡ trà nhä nh§t giúa hai tham sè a, b
Opt_Indexthr (i, j)
Ch¿ sè tèi ÷u thæng l÷ñng giúa nót i, nót j
PT
Tªp c¡c danh s¡ch c¡c mùc cæng su§t ph¡t
pt
Gi¡ trà mùc cæng su§t ph¡t
pti,j
Cæng su§t ph¡t tø nót i ¸n nót j
ptmax
Cæng su§t ph¡t lîn nh§t tø nót i ¸n nót j
r
Tèc ë truy·n cõa nót nguçn
R
Tªp c¡c danh s¡ch mùc tèc ë truy·n
Ri
Ph¤m vi ho¤t ëng cõa nót i
ri,j
Tèc ë truy·n tø nót i ¸n nót j
rmax
Tèc ë truy·n lîn nh§t tø nót i ¸n nót j
root_loop
Tham sè i·u khiºn váng l°p thuªt to¡n
s
Nót nguçn
SIN R_thr
Gi¡ trà mùc ng÷ïng cho tr÷îc thº hi»n ch§t
SumF
Têng sè l÷ñng gâi tin léi cõa nót truy·n
SumS
Têng sè l÷ñng gâi tin gûi cõa nót truy·n
l÷ñng k¶nh truy·n t¤i lîp PHY
S(pt, r)
Tªp c¡c nót h ng xâm t¤i cæng su§t ph¡t
pt v tèc ë truy·n r
⊕
Ph²p cëng logic
GIÎI THIU LUN N
1.T½nh c§p thi¸t cõa luªn ¡n
T¤i Vi»t Nam v tr¶n th¸ giîi, c¡c àa iºm cæng cëng nh÷ nh h ng, qu¡n
cafe ... ·u phõ sâng m¤ng khæng d¥y nâi chung v m¤ng adhoc nâi ri¶ng.
Còng vîi sü ph¡t triºn m¤nh m³ cõa c¡c m¤ng m¡y t½nh, y¶u c¦u c£i ti¸n
mæ h¼nh gi£i ph¡p truy·n thæng, ph¡t triºn c¡c mæ h¼nh gi£i ph¡p mîi nh¬m
n¥ng cao thæng l÷ñng m¤ng l th¡ch thùc trong l¾nh vüc nghi¶n cùu m¤ng
khæng d¥y. So vîi m¤ng câ d¥y th¼ m¤ng khæng d¥y vîi °c thò khæng c¦n
h¤ t¦ng k¸t nèi, triºn khai lp °t nhanh hé trñ ph¡t triºn c¡c k¸t nèi m¤ng
trong c¡c i·u ki»n h¤n ch¸ v· àa lþ, t i nguy¶n h¤ t¦ng, chi ph½ h¤n hµp
[33], [105]. B¶n c¤nh c¡c ÷u iºm th¼ so vîi m¤ng câ d¥y, do °c iºm mæi
tr÷íng truy·n d¨n, m¤ng khæng d¥y g°p c¡c v§n · v· t½nh ên ành, an to n
thæng tin ..., ¥y l v§n · nghi¶n cùu ÷ñc r§t quan t¥m nh¬m möc ½ch
n¥ng cao thæng l÷ñng m¤ng.
Hi»n nay, m¤ng truy·n dú li»u phê bi¸n bao gçm m¤ng câ d¥y v m¤ng
khæng d¥y ·u ¡p döng mët trong c¡c mæ h¼nh thi¸t k¸ ph¥n lîp l : Mæ h¼nh
OSI, TCP/IP. Mæ h¼nh OSI, TCP/IP ÷ñc x¥y düng tr¶n nguy¶n tc ph¥n
lîp rã r ng, méi lîp thüc hi¶n mët nhi»m vö, chùc n«ng ëc lªp, c¡c tham
sè ð c¡c lîp khæng tham gia v o qu¡ tr¼nh thüc hi»n chùc n«ng cõa lîp kh¡c.
Theo nguy¶n tc n y, méi lîp thüc hi»n c¡c chùc n«ng ri¶ng bi»t khæng phö
thuëc v o c¡c lîp kh¡c. Khi mët lîp cªp nhªt chùc n«ng, thay êi c¡c giao
thùc t¤i lîp â th¼ c¡c lîp cán l¤i khæng c¦n thay êi m v¨n £m b£o ho¤t
ëng cõa mæ h¼nh thi¸t k¸. Theo nguy¶n tc tr¶n, mæ h¼nh OSI, TCP/IP ¢
bä qua c¡c t¡c ëng qua l¤i cõa c¡c lîp. Vîi thi¸t k¸ ph¥n lîp s³ hé trñ qu¡
tr¼nh ph¡t triºn, thay êi giao thùc tøng lîp m khæng £nh h÷ðng ¸n c¡c
lîp cán l¤i. Tuy nhi¶n, thi¸t k¸ n y s³ khæng phò hñp vîi c¡c lo¤i m¤ng m
c¡c chùc n«ng trong c¡c lîp kh¡c bà £nh h÷ðng tham sè cõa nhau. °c thò
trong m¤ng câ d¥y, mæi tr÷íng truy·n dú li»u ri¶ng bi»t khæng câ nhi¹u, n¶n
mæ h¼nh OSI, TCP/IP ÷ñc ¡p döng r§t hi»u qu£, tuy nhi¶n trong m¤ng
1
- Xem thêm -