Luận án Nâng cao hiệu năng mạng manet sử dụng kỹ thuật định tuyến cân bằng tải đảm bảo chất lượng truyền dẫn

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM
KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
———————————-
LÊ HỮU BÌNH
NÂNG CAO HIỆU NĂNGMẠNGMANET
SỬ DỤNG KỸ THUẬT ĐỊNH TUYẾN CÂN BẰNG TẢI
ĐẢM BẢO CHẤT LƯỢNG TRUYỀN DẪN
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
HÀ NỘI - 2019
VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIÊN KHOA HỌC VÀ CÔNG NGHỆ
............***............
LÊ HỮU BÌNH
NÂNG CAO HIỆU NĂNGMẠNGMANET
SỬ DỤNG KỸ THUẬT ĐỊNH TUYẾN CÂN BẰNG TẢI
ĐẢM BẢO CHẤT LƯỢNG TRUYỀN DẪN
LUẬN ÁN TIẾN SỸ CÔNG NGHỆ THÔNG TIN
Chuyên ngành: Hệ thống thông tin
Mã số: 9 48 01 04
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. PGS.TS. Võ Thanh Tú
2. PGS.TS. Nguyễn Văn Tam
HÀ NỘI - 2019
i
LỜI CAM ĐOAN
Tôi xin cam đoan Luận án Tiến sĩ với tiêu đề "Nâng cao hiệu năng mạng
MANET sử dụng kỹ thuật định tuyến cân bằng tải đảm bảo chất lượng truyền
dẫn" là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của PGS.TS. Võ
Thanh Tú và PGS.TS. Nguyễn Văn Tam, trừ những kiến thức tham khảo từ các tài
liệu đã được chỉ rõ.
Các kết quả, số liệu được trình bày trong luận án là trung thực, một phần đã
được công bố trên các Tạp chí và Kỷ yếu Hội thảo khoa học chuyên ngành (danh
mục các công trình đã công bố của tác giả được trình bày ở cuối Luận án), phần
còn lại chưa từng được công bố trong bất kỳ công trình nào khác.
Hà Nội, ngày 17 tháng 11 năm 2019
Tác giả
Lê Hữu Bình
ii
LỜI CẢM ƠN
Luận án này được thực hiện tại Viện Công nghệ thông tin, Học viện Khoa học và
Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Nghiên cứu sinh (NCS)
xin tỏ lòng biết ơn sâu sắc đến PGS.TS. Võ Thanh Tú, người đã tận tình hướng dẫn,
định hướng cho quá trình nghiên cứu thực hiện luận án, cung cấp những kiến thức quý
báu cả về chuyên môn lẫn phương pháp nghiên cứu, phương pháp viết bài báo, báo
cáo kỹ thuật, giúp cho NCS có đủ điều kiện hoàn thành quá trình học tập, nghiên cứu
thực hiện luận án.
NCS xin tỏ lòng biết ơn sâu sắc đến PGS.TS. Nguyễn Văn Tam, người đã tận tình
hướng dẫn, tạo mọi điều kiện thuận lợi cho Nghiên cứu sinh trong suốt quá trình học
tập, nghiên cứu, thực hiện Luận án tại Viện Công nghệ thông tin, Học viện Khoa học
và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam.
NCS xin chân thành cảm ơn các ý kiến đóng góp quý báu qua các buổi seminar
định kỳ hàng tháng của quý Thầy Cô, các chuyên gia, các NCS trong nhóm nghiên
cứu về Công nghệ mạng và Truyền thông tại Viện Công nghệ thông tin.
NCS xin chân thành cảm ơn các ý kiến đóng góp quý báu của quý Thầy Cô trong
Hội đồng đánh giá luận án cấp cơ sở, những ý kiến góp ý của các Phản biện, các Thành
viên hội đồng cho việc chỉnh sửa, hoàn thiện luận án sau khi bảo vệ cấp cơ sở.
NCS xin chân thành cảm ơn Lãnh đạo Học viện Khoa học và Công nghệ, Viện
Công nghệ thông tin, Phòng Tin học Viễn thông đã tạo những điều kiện thuận lợi cho
việc nghiên cứu thực hiện Luận án.
NCS xin chân thành Cảm ơn Ban giám hiệu và các Phòng ban liên quan của Trường
Cao đẳng công nghiệp Huế, cũng như các đồng nghiệp đã tạo điều kiện và giúp đỡ tôi
hoàn thành được đề tài nghiên cứu của mình.
Cuối cùng là sự biết ơn sâu sắc tới gia đình đã luôn chia sẻ, cảm thông cho tôi
trong những chuỗi ngày dài miệt mài học tập, nghiên cứu để có được kết quả như ngày
hôm nay.
iii
iv
MỤC LỤC
Trang phụ bìa.......................................................................................... i
Lời cam đoan ......................................................................................... ii
Lời cảm ơn .............................................................................................iii
Danh mục các cụm từ viết tắt ................................................................. viii
Danh mục hình ........................................................................................x
Danh mục bảng ..................................................................................... xv
MỞ ĐẦU ................................................................................................1
1. Tính cấp thiết của đề tài nghiên cứu ........................................................1
2. Mục tiêu nghiên cứu .............................................................................3
3. Đối tượng và phạm vi nghiên cứu ............................................................3
4. Nội dung và phương pháp nghiên cứu ......................................................4
5. Các kết quả nghiên cứu cần đạt được.......................................................5
6. Bố cục của luận án ................................................................................5
CHƯƠNG 1. TỔNGQUANVỀMANETVÀCÁCYẾUTỐẢNHHƯỞNG
ĐẾN HIỆU NĂNGMẠNG ....................................................8
1.1. Những vấn đề cơ bản về mạng MANET.................................................8
1.1.1. Nguyên lý..................................................................................8
1.1.2. Đặc điểm ................................................................................ 10
1.1.3. Các yếu tố ảnh hưởng đến hiệu năng mạng MANET ......................... 11
1.2. Định tuyến trong mạng MANET ........................................................ 12
1.2.1. Tổng quan ............................................................................... 12
1.2.2. Phân loại ................................................................................. 13
1.3. Tình hình nghiên cứu về định tuyến trong mạng MANET ...................... 15
1.3.1. Định tuyến đảm bảo chất lượng dịch vụ (QoS)................................. 16
1.3.2. Định tuyến đảm bảo chất lượng truyền dẫn (QoT)............................. 16
1.3.3. Định tuyến cân bằng tải .............................................................. 19
1.3.4. Một số nhận xét và đánh giá ........................................................ 21
1.4. Những đóng góp của luận án ............................................................. 22
1.5. Kết luận chương .............................................................................. 23
CHƯƠNG 2. ĐÁNH GIÁ CHẤT LƯỢNG TRUYỀN DẪN CỦA MẠNG
MANET KHI SỬ DỤNG CÁC GIAO THỨC ĐỊNH TUYẾN
THEO YÊU CẦU VÀ CÂN BẰNG TẢI ................................. 24
2.1. Các hiệu ứng vật lý xảy ra trên lộ trình truyền dữ liệu ........................... 24
2.1.1. Các yếu tố kỹ thuật liên quan ....................................................... 24
2.1.2. Suy hao công suất qua môi trường dẫn ........................................... 25
2.1.3. Nhiễu tích lũy trên đường truyền .................................................. 27
2.2. Hiệu năng mạng MANET.................................................................. 29
2.2.1. Xác suất chặn gói dữ liệu ............................................................ 29
2.2.2. Thời gian trễ ............................................................................ 29
2.2.3. Tỷ lệ tín hiệu trên nhiễu.............................................................. 30
2.2.4. Tỷ lệ lỗi bit .............................................................................. 33
2.2.5. Một số kết quả tính toán và thảo luận............................................. 34
2.3. Chất lượng truyền dẫn của các lộ trình khi sử dụng các giao thức định
tuyến theo yêu cầu ............................................................................ 39
2.3.1. Nguyên lý cơ bản của các giao thức định tuyến theo yêu cầu ............... 40
2.3.2. Chất lượng truyền dẫn của các lộ trình ........................................... 44
2.4. Chất lượng truyền dẫn của các lộ trình khi sử dụng các giao thức định
tuyến cân bằng tải ............................................................................ 46
2.4.1. Nguyên lý cơ bản của kỹ thuật định tuyến cân bằng tải ...................... 46
2.4.2. Các phương pháp định tuyến cân bằng ........................................... 46
2.4.3. Chất lượng truyền dẫn của các lộ trình ........................................... 48
2.5. Đánh giá chất lượng truyền dẫn và hiệu năng mạng thông qua mô phỏng. 49
2.5.1. Kịch bản mô phỏng ................................................................... 49
2.5.2. Trường hợp sử dụng giao thức DSR............................................... 53
2.5.3. Trường hợp sử dụng giao thức AODV ............................................ 59
v
2.6. Kết luận chương .............................................................................. 62
CHƯƠNG 3. ĐỊNH TUYẾN CÂN BẰNG TẢI ĐẢMBẢOCHẤT LƯỢNG
TRUYỀN DẪN DỰA TRÊN TẢI LƯU LƯỢNG QUA MỖI
LỘ TRÌNH ....................................................................... 64
3.1. Đặt vấn đề....................................................................................... 64
3.2. Cơ sở lý thuyết liên quan ................................................................... 67
3.2.1. Phân tích xác suất chặn gói dữ liệu dựa trên lý thuyết hàng đợi ............ 67
3.2.2. Phân tích thời gian trễ dựa trên lý thuyết hàng đợi ............................ 69
3.3. Ý tưởng đề xuất thuật toán ................................................................ 70
3.3.1. Mô hình giải tích của thuật toán ................................................... 70
3.3.2. Ý tưởng thực thi thuật toán trên mô hình xuyên lớp........................... 73
3.4. Nguyên lý hoạt động của thuật toán .................................................... 79
3.5. Áp dụng cho giao thức AODV ............................................................ 84
3.5.1. Đặt vấn đề ............................................................................... 84
3.5.2. Chỉnh sửa khuôn dạng gói RREQ và RREP .................................... 85
3.5.3. Thuật toán định tuyến LBRQT-AODV ........................................... 86
3.6. Áp dụng cho giao thức DSR ............................................................... 88
3.6.1. Đặt vấn đề ............................................................................... 88
3.6.2. Chỉnh sửa khuôn dạng gói RREQ và RREP .................................... 89
3.6.3. Thuật toán định tuyến LBRQT-DSR.............................................. 90
3.7. Mô phỏng và phân tích kết quả .......................................................... 92
3.7.1. Xây dựng kịch bản mô phỏng ...................................................... 92
3.7.2. Kết quả mô phỏng thuật toán LBRQT-AODV.................................. 92
3.7.3. Kết quả mô phỏng thuật toán LBRQT-DSR .................................... 97
3.7.4. So sánh các thuật toán được đề xuất với các công trình nghiên cứu
liên quan ............................................................................... 105
3.8. Kết luận chương ............................................................................ 107
vi
CHƯƠNG 4. ĐỊNH TUYẾN CÂN BẰNG TẢI ĐẢMBẢOCHẤT LƯỢNG
TRUYỀN DẪN DỰA TRÊN THÔNG TIN ĐỊNH TUYẾN
CỦA NÚT NGUỒN .......................................................... 109
4.1. Ý tưởng đề xuất thuật toán .............................................................. 109
4.1.1. Chọn lộ trình cân bằng tải ......................................................... 109
4.1.2. Xác định điều kiện ràng buộc QoT .............................................. 110
4.2. Mô hình giải tích của thuật toán ....................................................... 111
4.2.1. Xây dựng hàm mục tiêu và các điều kiện ràng buộc ........................ 111
4.2.2. Ví dụ minh họa....................................................................... 112
4.3. Thực thi thuật toán SLBQT-DSR ..................................................... 116
4.3.1. Chỉnh sửa khuôn dạng gói RREQ ............................................... 116
4.3.2. Lưu đồ thuật toán SLBQT-DSR ................................................. 116
4.4. Mô phỏng và phân tích kết quả ........................................................ 118
4.4.1. Kịch bản mô phỏng ................................................................. 118
4.4.2. Kết quả mô phỏng ................................................................... 119
4.4.3. So sánh thuật toán được đề xuất với các công trình nghiên cứu liên
quan ..................................................................................... 125
4.5. Đánh giá ưu nhược điểm của thuật toán được đề xuất ......................... 128
4.5.1. Ưu điểm................................................................................ 128
4.5.2. Nhược điểm ........................................................................... 128
4.6. Kết luận chương ............................................................................ 129
KẾT LUẬN VÀ NHỮNG ĐÓNG GÓP CỦA LUẬN ÁN ............................. 130
HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI LUẬN ÁN ..................................... 132
CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN ĐỀ TÀI LUẬN ÁN . 133
TÀI LIỆU THAM KHẢO ..................................................................... 134
PHỤ LỤC A. TÍNH TOÁN CHI TIẾT VÍ DỤ MINH HỌA NGUYÊN LÝ
HOẠT ĐỘNG CỦA THUẬT TOÁN LBRQT..........................P1
PHỤ LỤC B. MÃ NGUỒN CỦA MỘT SỐ MODULE CƠ BẢN TRONG
CHƯƠNG TRÌNH MÔ PHỎNG TRÊN OMNET++ ............. P14
vii
DANHMỤC CÁC CỤM TỪ VIẾT TẮT
Viết tắt Nghĩa tiếng anh Nghĩa tiếng việt 
AF Amplify and Forward Khuếch đại và chuyển tiếp 
AODV 
Ad hoc On-Demand Distance 
Vector 
Định tuyến vector khoảng cách 
theo yêu cầu 
ARA 
Ant colony based Routing 
Algorithm 
Định tuyến dựa trên thuật toán tối 
ưu đàn kiến 
ASK Amplitude Shift Keying Điều chế khóa dịch biên độ 
BER Bit Error Rate Tỷ lệ bit lỗi 
BPD 
Blocking Probability of Data 
packets 
Xác suất chặn gói dữ liệu 
BPSK Binary Phase Shift Keying Điều chế khóa dịch pha hai mức 
CBRP Cluster-Based Routing Protocol Định tuyến dựa trên cụm 
CCK Complementary Code Keying Điều chế khóa mã bù 
DDR Distributed Dynamic Routing Định tuyến động phân tán 
DF Decode and Forward Kỹ thuật giải mã và chuyển tiếp 
DPSK Differential Phase Shift Keying Điều chế khóa dịch pha vi sai 
DSDV 
Destination Sequenced Distance 
Vector 
Giao thức vector khoảng cách 
theo thứ tự đến đích 
DSN Destination Sequence Number Số thứ tự đích 
DSR Dynamic Source Routing Định tuyến nguồn động 
EED End to End Delay Thời gian trễ từ nguồn đến đích 
ERPN 
Efficient Routing Protocol under 
Noisy Environment 
Giao thức định tuyến hiệu quả 
dưới môi trường nhiễu 
FEC Forward Error Correction Kỹ thuật sửa lỗi ở phía trước 
FMLB 
Fibonacci Multipath Load 
Balancing 
Cân bằng tải đa đường dựa trên 
dãy Fibonacci 
FSK Frequency Shift Keying Điều chế khóa dịch tần số 
FSR Fisheye State Routing 
Giao thức định tuyến trạng thái 
Fisheye 
HSR Hierarchical State Routing Định tuyến trạng thái phân cấp 
IARM 
Interference Aware Routing 
Metric 
Độ đo định tuyến phản ánh nhiễu 
IoT Internet of Things Internet vạn vật 
LAR Location Aided Routing Định tuyến được hỗ trợ bởi vị trí 
LBRQT 
Load Balancing Routing ensuring 
Qualit ... là L = 20 gói. Do vậy, thay ρ12 và L vào (A.5) ta có:
L=
0.72
1−0.72 −
0.72× (20×0.7220+1)
1−0.7220+1 = 1.8305 (A.6)
Theo phương trình (3.4) ta xác định được B(h)12 như sau:
P3
B(h)12 =

ρL12(1−ρ12)
1−ρL+112
nếu ρ12 6= 1
1
L+1 nếu ρ12 = 1
(A.7)
=
0.7220(1−0.72)
1−0.7220+1 (A.8)
= 0.000392868 (A.9)
Theo giả thiết của ví dụ, kích thước gói dữ liệu trung bình là 1472 bytes, tốc độ dữ liệu
của m kênh là 54 Mbit/s, do đó:
µ12 =
54×106
1472
= 4585.5978 (gói/giây) (A.10)
Mặt khác ta có:
ρ12 =
λ12
µ12
⇒ λ12 = ρ12×µ12 (A.11)
= 0.72×4585.5978 (A.12)
= 3301.630435 (gói/giây) (A.13)
Thay (A.6), (A.7), (A.10) và (A.11) vào (A.4) ta có:
τ(1)q =
L
λ12(1−B(h)12 )
+
1
µ12
(A.14)
=
1.830497
3301.630435× (1−0.00039287) +
1
4585.5978
(A.15)
= 0.000772714 (s) (A.16)
Thay (A.14) vào (A.3) ta có:
τ(h)12 = τ
(1)
q + τ
(12)
t (A.17)
= 0.000772714+
1472×8
54×106 (A.18)
= 0.000990788 (s) (A.19)
• Bước 1.3.3: Xác định thời gian trễ (EED) trên lộ trình từ nút 1 đến nút 2 (τ(r)12 )
P4
(Bước 6 của Thuật toán 3.1). Ta có:
τ(r)12 = τ
(r)
11 + τ
(h)
12 (A.20)
= 0+0.000990788 = 0.000990788 (s) (A.21)
• Bước 1.3.4: Xác định SNR của lộ trình từ nút 1 đến nút 2 (τ(r)12 ) (Bước 7 đến 11
của Thuật toán 3.1). Vì nguyên lý chuyển tiếp dữ liệu tại các nút mạng là AF, nên theo
phương trình xác định SNR của một lộ trình (Phương trình (2.19) ở Chương 2) ta có:
β (r)12 =
( 1
β (r)11
+
1
β (h)12
)−1
(A.22)
Vì phương trình (A.22) được sử dụng cho giá trị tuyến tính. Vì vậy, giá trị của các
thành phần trong (A.22) cần phải đổi sang giá trị tuyến tính trước khi tính toán. Đổi
β (r)12 sang giá trị tuyến tính ta được:
β (h)12 = 10
β (h)12 (dB)
10 = 10
30
10 = 1000 (A.23)
Thay (A.23) vào (A.22) ta có:
β (r)12 =
( 1
+∞
+
1
1000
)−1
= 1000 (A.24)
Đổi giá trị β (r)12 sang dB ta có:
β (r)12 (dB)= 10∗ log10(β (r)12 ) = 10∗ log10(1000) = 30 (dB) (A.25)
• Bước 1.3.5: Xác định các điều kiện ràng buộc của QoT, EED và dự đoán xác
suất chặn gói dữ liệu trên lộ trình từ nút 1 đến nút 2 (B(r)12 ) (Bước 12 đến 17 của Thuật
toán 3.1). Từ (A.22) và (A.20) ta có:β
(r)
12 ≥ βreq
τ(r)12 ≤ τth
⇔
30≥ 23.50.000990788≤ 0.01 (A.26)
Từ (A.26) ta thấy điều kiện ràng buộc của QoT và EED được thỏa mãn. Do vậy,
nút 1 được đưa vào tập Q1. Để có cơ sở lựa chọn lộ trình cân bằng tải, SA tiếp tục dự
đoán xác suất chặn gói dữ liệu trên lộ trình từ nút 1 đến nút 2 (B(r)12 ). Theo (3.7) ta có:
B(r)12 = 1− (1−B(r)11 )(1−B(h)12 ) (A.27)
= 1− (1−0)(1−0.000392868) = 0.000392868 (A.28)
P5
Từ (A.20), (A.25) và (A.27) ta có các độ đo QoT, EED và BPD mà SA tại nút 1
xác định được đối với nút 2 là:
β (r)12 = 30
τ(r)12 = 0.000990788
B(r)12 = 0.000392868
(A.29)
Lặp lại các bước từ 1.1 đến 1.3 đối với các nút láng giềng còn lại của nút 1, (nút 2
và nút 3), ta xác định được các độ đo QoT, EED và BPD từ nút 1 đến các nút này như
sau: 
β (r)13 = 29
τ(r)13 = 0.0009189274
B(r)13 = 0.0001855764
(A.30)

β (r)14 = 31
τ(r)14 = 0.0007916460
B(r)14 = 0.0000267693
(A.31)
Từ các kết quả thu được ở (A.29), (A.30) và (A.31) ta có kết quả dự đoán các độ đo
SNR, EED và BPD đối với các nút láng giềng của nút 1 như Bảng A.1. Ta thấy rằng,
các giá trị SNR và EED từ nút 1 đến các nút 2, 3, và 4 đều thỏa mãn điều kiện ràng
buộc của QoT và EED (βs j > βreq và τs j < τth,s= 1, j = 2,3,4), nên tập Q1 = {2, 3,
4}. Sau khi xác định được tập Q1, nút 1 phát quảng bá gói RREQ đến tất cả các nút
thuộc tập này, cụ thể là các nút 2, 3 và 4.
Bảng A.1. Kết quả dự đoán SNR, EED và BPD tại nút 1 bởi SA
Bước 1: 
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 2 3 4 
)(h
sj (dB) 30.00 29.00 31.00 
)(h
sj (s) 0.00099079 0.00091893 0.00079165
)(h
sjB 0.00039287 0.00018558 0.00002677
- 1 
Tập Q1    
P6
- Bước 2: Các nút nhận gói RREQ ở bước 1 tiếp tục xử lý gói RREQ:
Các nút nhận được gói RREQ ở bước 1 bao gồm nút 2, 3 và 4 tiếp tục xử lý gói
RREQ. SA tại các nút này dự đoán các độ đo SNR, EED và BPD theo Thuật toán 3.1.
Cụ thể, SA tại nút 2 dự đoán SNR, EED và BPD từ nút 1 đến tất cả các nút láng giềng
của nó là 3 và 6. Xét nút láng giềng đầu tiên của nút 2, đó là nút 3, việc dự đoán các
độ đo SNR, EED và BPD từ nút 1 đến nút 3 được thực hiện như sau:
+ Bước 2.1: Đọc các thông tin về QoT và EED từ nút S đến nút I (β (r)si , τ
(r)
si và
B(r)si ) được lưu trữ trong gói RREQ (Bước 1 của Thuật toán 3.1). S là nút nguồn (nút
1), I hiện tại là nút 2. Kết quả đọc được từ gói RREQ là:
β (r)12 = 30
τ(r)12 = 0.000990788
B(r)12 = 0.000392868
(A.32)
+ Bước 2.2: Khởi tạo giá trị ban đầu là rỗng cho tập Q2: Q2 = /0 (Bước 2 của Thuật
toán 3.1).
+ Bước 2.3: Dự đoán các độ đo QoT, EED và BPD từ nút nguồn (nút 1) đến mỗi
nút J là láng giềng của nút đang xét (hiện đang là nút 2) , các độ đo này bao gồm:
(β (r)1 j ), (τ
(r)
1 j ) và (B
(r)
1 j ). Công việc này được thực hiện bằng vòng lặp For (từ bước 3
đến bước 18 của thuật toán 3.1).
Theo tô-pô ở Hình A.1, nút 2 đang có 2 nút láng giềng là 3 và 6. Xét nút láng giềng
đầu tiên của nút 2, là nút 3. Việc dự đoán các độ đo (β (r)13 ), (τ
(r)
13 ) và (B
(r)
13 ) được thực
hiện như sau:
• Bước 2.3.1: Thu thập thông tin SNR từ 2 đến 3 (β (h)23 ) tại lớp vật lý (Bước 4 của
Thuật toán 3.1): Theo trạng thái mạng hiện tại ở tô-pô Hình A.1, SA tại nút 2 thua
thập thông tin SNR từ 2 đến 3 như sau:
β (h)23 = 32 (dB). (A.33)
• Bước 2.3.2: Dự đoán thời gian trễ trên bước truyền từ nút 2 đến nút 3 (τ(h)23 )
(Bước 5 của Thuật toán 3.1). Theo phương trình (3.8) ta có:
τ(h)23 = τ
(2)
p + τ
(2)
q + τ
(23)
t + τ
(23)
r (A.34)
P7
Như đã lập luận ở Phần 3.2.2, τ(2)p và τ
(23)
r là đủ nhỏ nên có thể bỏ qua. Do vậy, phương
trình (A.2) trở thành:
τ(h)23 = τ
(2)
q + τ
(23)
t (A.35)
Theo phương trình (3.9) ta có:
τ(2)q =
L
λ23(1−B(h)23 )
+
1
µ23
(A.36)
trong đó, L được xác định theo phương trình (3.10)
L=

ρ23
1−ρ23 −
ρ23(LρL23+1)
1−ρL+123
nếu ρ23 6= 1
L(L−1)
2(L+1)
ngược lại
(A.37)
Theo giả thiết được thiết lập ở tô-pô mạng Hình A.1, ở thời điểm hiện tại, ρ23 = 0.61,
kích thước hàng đợi tại mỗi nút là L = 20 gói. Do vậy, thay ρ23 và L vào (A.37) ta có:
L=
0.61
1−0.61 −
0.61× (20×0.6120+1)
1−0.6120+1 = 0.9535 (A.38)
Theo phương trình (3.4) ta xác định được B(h)23 như sau:
B(h)23 =

ρL23(1−ρ23)
1−ρL+123
nếu ρ23 6= 1
1
L+1 nếu ρ23 = 1
(A.39)
=
0.6120(1−0.61)
1−0.6120+1 (A.40)
= 0.0000198461 (A.41)
Theo giả thiết của ví dụ, kích thước gói dữ liệu trung bình là 1472 bytes, tốc độ dữ liệu
của m kênh là 54 Mbit/s, do đó:
µ23 =
54×106
1472
= 4585.5978 (gói/giây) (A.42)
Mặt khác ta có:
ρ23 =
λ23
µ23
⇒ λ23 = ρ23×µ23 (A.43)
= 0.61×4585.5978 (A.44)
= 2797.21467 (gói/giây) (A.45)
P8
Thay (A.38), (A.39), (A.42) và (A.43) vào (A.36) ta có:
τ(2)q =
L
λ23(1−B(h)23 )
+
1
µ23
(A.46)
=
0.9535
2797.21467× (1−0.0000198461) +
1
4585.5978
(A.47)
= 0.0005589423 (s) (A.48)
Thay (A.46) vào (A.35) ta có:
τ(h)23 = τ
(2)
q + τ
(23)
t (A.49)
= 0.0005589423+
1472×8
54×106 (A.50)
= 0.0007770164 (s) (A.51)
• Bước 2.3.3: Xác định thời gian trễ (EED) trên lộ trình từ nút 1 đến nút 3 (τ(r)13 )
(Bước 6 của Thuật toán 3.1). Ta có:
τ(r)13 = τ
(r)
12 + τ
(h)
23 (A.52)
= 0.000990788+0.0007770164 = 0.0017678044 (s) (A.53)
• Bước 2.3.4: Xác định SNR của lộ trình từ nút 1 đến nút 3 (τ(r)13 ) (Bước 7 đến 11
của Thuật toán 3.1). Vì nguyên lý chuyển tiếp dữ liệu tại các nút mạng là AF, nên theo
phương trình xác định SNR của một lộ trình (Phương trình (2.19) ở Chương 2) ta có:
β (r)13 =
( 1
β (r)12
+
1
β (h)23
)−1
(A.54)
Vì phương trình (A.54) được sử dụng cho giá trị tuyến tính. Vì vậy, giá trị của các
thành phần trong (A.54) cần phải đổi sang giá trị tuyến tính trước khi tính toán. Theo
(A.25) và (A.33) ta có β (r)12 = 30 dB và β
(h)
23 = 32 dB. Đổi các giá trị này sang giá trị
tuyến tính ta được:
β (r)12 = 10
β (h)12 (dB)
10 = 10
30
10 = 1000 (A.55)
β (h)23 = 10
β (h)23 (dB)
10 = 10
32
10 = 1584.893 (A.56)
P9
Thay (A.55) và (A.56) vào (A.54) ta có:
β (r)13 =
( 1
1000
+
1
1584.893
)−1
= 613.137 (A.57)
Đổi giá trị β (r)13 sang dB ta có:
β (r)12 (dB)= 10∗ log10(β (r)12 ) = 10∗ log10(613.137) = 27.876 (dB) (A.58)
• Bước 2.3.5: Xác định các điều kiện ràng buộc của QoT, EED và dự đoán xác
suất chặn gói dữ liệu trên lộ trình từ nút 1 đến nút 3 (B(r)13 ) (Bước 12 đến 17 của Thuật
toán 3.1). Từ (A.58) và (A.52) ta có:β
(r)
13 ≥ βreq
τ(r)13 ≤ τth
⇔
27.876≥ 23.50.0017678044≤ 0.01 (A.59)
Từ (A.59) ta thấy điều kiện ràng buộc của QoT và EED được thỏa mãn. Do vậy, nút 3
được đưa vào tập Q2. Để có cơ sở lựa chọn lộ trình cân bằng tải, SA tiếp tục dự đoán
xác suất chặn gói dữ liệu trên lộ trình từ nút 1 đến nút 3 (B(r)13 ). Theo (3.7) ta có:
B(r)13 = 1− (1−B(r)12 )(1−B(h)23 ) (A.60)
= 1− (1−0.000392868)(1−0.0000198461) = 0.0004127063 (A.61)
Từ (A.52), (A.58) và (A.60) ta có các độ đo QoT, EED và BPD mà SA tại nút 2 xác
định được đối với nút 3 là: 
β (r)13 = 27.876
τ(r)13 = 0.0017678044
B(r)13 = 0.0004127063
(A.62)
Lặp lại các bước từ 2.1 đến 2.3 đối với các nút láng giềng còn lại của nút 2, (nút
6), ta xác định được các độ đo QoT, EED và BPD từ nút 1 đến nút 6 như sau:
β (r)16 = 25.236
τ(r)16 = 0.0029203967
B(r)16 = 0.0186521816
(A.63)
P10
Lặp lại bước 2 cho các nút láng giềng còn lại của nút 2 (nút 3 và nút 4). Kết quả
dự đoán như ở Bảng A.2. Từ kết quả này, SA tại các nút 2, 3, và 4 xác định được tập
các nút láng giềng của nó thỏa mãn các điều kiện ràng buộc của QoT và EED tương
ứng là: Q2 = {3, 6}, Q2 = {2, 5, 7} và Q4 = {5}. Các nút 2, 3 và 4 tiếp tục quảng bá
gói RREQ đến các nút trong tập Q j tương ứng của nó.
Bảng A.2. Kết quả dự đoán SNR, EED và BPD tại nút nhận được gói RREQ ở bước 1
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 3 6 
)(h
sj (dB) 27.88 25.24 
)(h
sj (s) 0.00176780 0.00292039
)(h
sjB 0.00041271 0.01865218
1 2 
Tập Q2   
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 2 5 7 
)(h
sj (dB) 27.24 25.99 24.88 
)(h
sj (s) 0.00172597 0.00175928 0.00172597
)(h
sjB 0.00022147 0.00024901 0.00022147
1 3 
Tập Q3    
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 5 
)(h
sj (dB) 28.46 
)(h
sj (s) 0.00156866
)(h
sjB 0.00004662
1 4 
Tập Q4  
(a)
(b)
(c)
- Bước 3: Các nút nhận gói RREQ ở bước 2 tiếp tục xử lý gói RREQ:
Các nút nhận được gói RREQ ở bước 2 bao gồm: (i) các nút 3, 6 nhận được từ nút
2, (ii) các nút 2, 5, 7 nhận được từ nút 3 và (iii) nút 5 nhận được từ nút 4. Khi nút 3
nhận được gói RREQ từ nút 2, gói RREQ này sẽ bị hủy bỏ do nút 3 đã nhận gói RREQ
này trước đó từ nút 1 (ở bước 1), tương tự như vậy cho các nút khác. Các nút tiếp tục
xử lý gói RREQ ở bước này bao gồm 5, 6 và 7. Kết quả dự đoán các độ đo SNR, EED
và BPD như ở Bảng A.3. Với kết quả này, trường hợp nút 7 dự đoán SNR từ nút nguồn
(nút 1) đến nút 9 (Bảng A.3c), giá trị dự đoán được là 23.15 dB. Giá trị này không
thỏa mãn điều kiện ràng buộc của QoT, do nhỏ hơn SNR yêu cầu tối thiểu là 23.5 dB.
Vì vậy, nút 9 không được đưa vào tập Q7, mặc dù nút 9 là láng giềng của nút 7. Từ
kết quả này, SA tại các nút 5, 6, và 7 xác định được tập các nút láng giềng của nó thỏa
P11
mãn các điều kiện ràng buộc của QoT và EED tương ứng là: Q5 = {4, 8}, Q6 = {7, 9}
và Q7 = {6}. Các nút 5, 6 và 7 tiếp tục quảng bá gói RREQ đến các nút trong tập Q j
tương ứng của nó.
Bảng A.3. Kết quả dự đoán SNR, EED và BPD tại nút nhận được gói RREQ ở bước 2Bước 3: 
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 4 8 
)(h
sj (dB) 25.01 24.80 
)(h
sj (s) 0.00270078 0.00263673
)(h
sjB 0.00048846 0.00035866
1 3 5 
Tập Q5   
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 7 9 
)(h
sj (dB) 23.98 23.71 
)(h
sj (s) 0.00358350 0.00372743
)(h
sjB 0.01865286 0.01868741
1 2 6 
Tập Q6   
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 6 9 
)(h
sj (dB) 23.71 23.15 
)(h
sj (s) 0.00271675 0.00239835
)(h
sjB 0.00061425 0.00022247
1 3 7 
Tập Q7  X 
Bước 4: 
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 9 
)(h
sj (dB) 23.65 
)(h
sj (s) 0.00174477
)(h
sjB 0.00054417
1 3 5 8 
Tập Q8  
(a)
(b)
(c)
- Bước 4: Các nút nhận gói RREQ ở bước 3 tiếp tục xử lý gói RREQ:
Các nút nhận được gói RREQ ở bước 3 bao gồm: (i) các nút 4, 8 nhận được từ nút
5, (ii) các nút 7, 9 nhận được từ nút 6 và (iii) nút 6 nhận được từ nút 7. Trong đó, các
gói RREQ nhận được tại các nút 4, 6 và 7 sẽ bị loại bỏ, do trước đó các nút này đã
nhận được gói RREQ này. Chỉ còn lại các nút 8 và 9 tiếp tục xử lý gói RREQ.
Tại nút 8, gói RREQ được tiếp tục xử lý tương tự như các nút trên. Kết quả dự đoán
các độ đo SNR, EED và BPD như ở Bảng A.4. Tập Q8 được xác định là: Q8 = {9}.
Tại nút 9, khi nhận được gói RREQ từ nút từ nút 6, vì 9 là nút đích, nên nút 9 tạo gói
RREP và gửi phản hồi về nút 1. Kết quả là lộ trình đầu tiên được tìm thấy: 1→ 2→ 6
→ 9.
- Bước 5: Các nút nhận gói RREQ ở bước 4 tiếp tục xử lý gói RREQ:
P12
Bảng A.4. Kết quả dự đoán SNR, EED và BPD tại nút nhận được gói RREQ ở bước 3
Nút láng giềng của I (nút J) Các nút 
phía trước 
Nút xử lý 
RREQ (I) 
Các độ đo từ S đến 
láng giềng của I (J) 9 
)(h
sj (dB) 23.65 
)(h
sj (s) 0.00355565
)(h
sjB 0.00054417
1 3 5 8 
Tập Q8  
Tại bước này, chỉ còn lại nút 9 nhận được gói RREQ từ nút 8. Vì 9 là nút đích, nên
nút 9 tạo gói RREP và gửi phản hồi về nút 1. Kết quả là lộ trình thứ 2 được tìm thấy:
1→ 3→ 5→ 8→ 9.
- Bước 6: Xử lý gói RREP tại nút nguồn:
Qua quá trình phát quảng bá gói RREQ, nút nguồn nhận được 2 gói phản hồi
RREP, tương ứng với 2 lộ trình thỏa mãn các điều kiện ràng buộc của QoT và EED
được tìm thấy là 1→ 2→ 6→ 9 và 1→ 3→ 5→ 8→ 9. Dựa trên kết quả dự đoán
BPD của SA trong quá trình khám phá lộ trình, BPD của lộ trình 1→ 2→ 6→ 9 là
0.01868741 (kết quả ở các Bảng A.3b), BPD của các lộ trình 1→ 3→ 5→ 8→ 9 là
0.00054417 (kết quả ở Bảng A.4). Như vậy, theo nguyên lý của giải pháp định tuyến
LBQT-R, lộ trình có giá trị BPD nhỏ nhất sẽ được chọn, đó là 1→ 3→ 5→ 8→ 9.
Bằng việc chọn lộ trình 1→ 3→ 5→ 8→ 9, thuật toán định tuyến LBRQT đã
tránh được các bước truyền đang có tải lưu lượng lớn (các bước truyền 1→ 2 và 2→
6 ở tô-pô Hình A.1). Kết qủa này cho thấy rằng, giải pháp định tuyến LBQT-R đã tìm
được lộ trình thỏa mãn các điều kiện ràng buộc của QoT và EED, đồng thời cân bằng
tải lưu lượng trên các kết nối.
P13