Luận án tiến sĩ Kỹ thuật viễn thông: Đị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

Chia sẻ: Tỉ Thành | Ngày: | Loại File: PDF | Số trang:155

Thêm vào BST

Báo xấu

24
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 họa kết quả các thuật toán định tuyến đề xuất nâng cao thông lượng mạng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sĩ Kỹ thuật viễn thông: Đị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

BË GIO DÖC V O TO TR×ÍNG I HÅC BCH KHOA H NËI NGUYN QUANG KHNH ÀNH TUYN NNG 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 NNG 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 th¡ng n«m 2019 Gi¡o vi¶n h÷îng d¨n khoa håc T¡c gi£ PGS.TS Nguy¹n V«n ùc 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 n«m 2019 T¡c gi£ 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 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 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 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 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 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 Sü kh¡c nhau giúa ph÷ìng thùc m¢ m¤ng v ph÷ìng thùc "store and for- ward" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 DSA Decentralized Dynamic Thuªt to¡n c§p ph¡t Sub Channel Assignment k¶nh ëng DSDV Destination Sequenced Giao thùc 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 OFDMA Orthogonal frequency a truy cªp ph¥n chia division multiple access t¦n sè trüc giao OSI model Open Systems Mæ h¼nh OSI 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 Time Division Duplexing Ph¥n k¶nh theo khe 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 Dijk- stra, 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 Dijk- stra, 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 Dijk- stra, 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