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

t trên dung lượng của một kênh truyền. 1 Erlang tương ứng với tải
lưu lượng mà nó chiếm hoàn toàn một kênh trong mạng MANET. Ví dụ, giả sử tốc độ
dữ liệu của một kênh là 54 Mbit/s, 1 Erlang tương đương mỗi nút phát sinh lưu lượng
54 Mbit/s. Hay nói cách khác, nếu kích thước gói dữ liệu trung bình là 1472 bytes, 1
Erlang tương đương với mỗi nút phát trung bình (54e+6)/(1472*8) = 4585.6 gói/s.
 Các đồ thị trên Hình 2.19 cho thấy rằng, BPD tăng dần theo tải lưu lượng. Khi tải
lưu lượng đạt ở mức cao nhất (1 Erlang) thì BPD trên toàn mạng là 0.042. Sở dĩ BPD
trên toàn mạng không tăng cao khi tải lưu lượng phát sinh ở mỗi nút đạt đến 1 Erlang
là vì trong các kịch bản mô phỏng để thu được kết quả ở Hình 2.19, tổng số nút mạng
là 50 trong vùng diện tích 1000 x 1000 m, vùng phủ sóng là 250 m nên thông thường
thì mỗi nút có nhiều cổng ra được kết nối đến nhiều nút khác tạo thành tô-pô mắt lưới
(mesh). Trong lúc đó, tải lưu lượng phát sinh được tính dựa trên Erlang, tương đương
như “tải chuẩn hóa trên 1 kênh”, vì vậy, mặc dù tải lưu lượng tiến đến 1 Erlang nhưng
với tô-pô mạng mắt lưới thì chưa tiến đến năng lực vận chuyển của đường truyền. Do
vậy, BPD trên toàn mạng không tăng cao.
 Vấn đề cần quan tâm trong kết quả ở Hình 2.19 là thành phần BPD do không thỏa
mãn điều kiện ràng buộc của QoT. Xét trường hợp hệ thống mạng sử dụng kênh có
băng thông 40 MHz (kết quả trên Hình 2.19a), khi tải lưu lượng tăng từ 0.6 Erlang
đến 1 Erlang, BPD tăng từ 0.023 đến 0.041. Trong đó, BPD do không thỏa mãn điều
kiện ràng buộc của QoT từ 0.011 đến 0.013. Ta thấy rằng, giá trị BPD chiếm gần 50%
 57
trong tổng số BPD của toàn mạng khi tải lưu lượng thấp, nhỏ hơn 0.75 Erlang. Khi tải
lưu lượng tăng cao, BPD do QoT gần như ổn định. BPD toàn mạng tăng là do nghẽn
lưu lượng.
 Trong trường hợp hệ thống mạng sử dụng kênh có băng thông 80 MHz (kết quả
trên Hình 2.19b), BPD toàn mạng tăng lên rất lớn so với trường hợp sử dụng kênh
có băng thông 80 MHz, trong đó thành phần BPD do không thỏa mãn điều kiện ràng
buộc của QoT chiếm thành phần chủ yếu. Nguyên nhân của BPD tăng là do khi hệ
thống mạng sử dụng kênh có băng thông lớn, nhiễu phát sinh trên các kênh truyền dữ
liệu tăng lên, làm cho QoT giảm.
 0.08 0.16
 BPD toàn phần BPD toàn phần
 0.07 0.14
 BPD do QoT BPD do QoT
 0.06 0.12
 0.05 0.10
 0.04 0.08
 BPD
 BPD
 0.03 0.06
 0.02 0.04
 0.01 0.02
 0.00 0.00
 51015205 101520
 Tốc độ di chuyển (m/s) Tốc độ di chuyển (m/s)
 (a) (b)
Hình 2.20. Sự thay đổi của BPD theo tốc độ di chuyển sử dụng giao thức DSR khi tổng số nút
 mạng là 50, tải lưu lượng 0.6 Erlang, băng thông kênh (a) 40 MHz và (b) 80 MHz
 Tiếp theo, tác giả phân tích sự đổi của BPD theo tốc độ di chuyển và theo tổng số
nút mạng. Kết quả thu được như ở Hình 2.20 và Hình 2.21. Khi tốc độ di chuyển trung
bình của mỗi nút tăng dần, BPD cũng tăng dần như cho thấy ở Hình 2.20. Xét trường
hợp tải lưu lượng là 0.6 Erlang và băng thông kênh 40 MHz (Hình 2.20a), BPD tăng
từ 0.025 đến 0.05 khi tốc độ di chuyển tăng từ 5 m/s đến 20 m/s. Trong đó, thành phần
PBD do không đảm bảo QoT chiếm từ 44% đến 47% trong tổng số BPD của toàn
mạng. Trong trường hợp sử dụng kênh với băng thông 80 MHz (Hình 2.20b), BPD
toàn phần tăng lên đến giá trị từ 0.08 đến 0.13, trong đó chủ yếu là BPD do không
thỏa mãn điều kiện ràng buộc của QoT.
 Khi tổng số nút mạng tăng thì BPD cũng tăng như cho thấy ở Hình 2.21. Nguyên
 58
 0.05 0.05
 BPD toàn phần BPD toàn phần
 BPD do QoT BPD do QoT
 0.04 0.04
 0.03 0.03
 BPD
 BPD
 0.02 0.02
 0.01 0.01
 0.00 0.00
 30 35 40 45 50 30 35 40 45 50
 Tổng số nút mạng Tổng số nút mạng
 Hình 2.21. Sự thay đổi của BPD theo tổng số nút của giao thức DSR khi tốc độ di
 chuyển trung bình 10 m/s, tải lưu lượng 0.6 Erlang, băng thông kênh 40 MHz
nhân là do khi tổng số nút mạng tăng thì ảnh hưởng của các hiệu ứng cũng tăng lên,
làm cho thành phần BPD do không đảm bảo QoT tăng lên. Các đồ thị trên Hình 2.21
cho thấy BPD do QoT chiếm gần 50% trong tổng số BBP của toàn mạng.
2.5.3. Trường hợp sử dụng giao thức AODV
 Trong phần này, tác giả tiếp tục phân tích QoT trên các lộ trình truyền dữ liệu và
ảnh hưởng của nó đến hiệu năng mạng MANET khi sử dụng giao thức định tuyến
AODV. Kết qủa thu được ở Hình 2.22 cho ta thấy giá trị SNR tại đầu thu của nút đích
 Hình 2.22. SNR trên các lộ trình truyền dữ liệu trong mạng MANET khi sử dụng
 giao thức định tuyến AODV
 59
 Hình 2.23. Tỷ lệ kênh đảm bảo QoT khi sử dụng giao thức định tuyến AODV
của các lộ trình truyền dữ liệu. Kết quả này được thực thi trên tô-pô 50 nút, tốc độ di
chuyển trung bình của mỗi nút là 10 m/s và băng thông kênh 40 MHz. Biểu đồ trên
Hình 2.22 cho thấy rằng, giá trị SNR nhỏ nhất của tất cả các lộ trình truyền dữ liệu là
22.3 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ốt thiểu (23.5 dB). Ngoài ra, có nhiều lộ trình mà SNR của nó không thỏa
mãn điều kiện ràng buộc của QoT. Để thấy rõ hơn điều này, tác giả phân tích tỷ lệ kênh
đảm bảo QoT qua thời gian mô phỏng. Kết quả thu được như cho thấy trên Hình 2.23.
Ta thấy rằng, có trung bình 98.07% số kênh đảm bảo QoT, nghĩa là còn lại 1.93% số
kênh không đảm bảo QoT theo yêu cầu.
 Hình 2.24. BER trên các lộ trình truyền dữ liệu trong mạng MANET khi sử dụng
 giao thức định tuyến AODV
 60
 Vì có nhiều lộ trình mà SNR của nó nhỏ hơn giá trị yêu cầu tối thiểu như đã phân
 tích ở Hình 2.22, nên tồn tại nhiều lộ trình mà BER lớn hơn giới hạn cho phép (10−6).
 Kết quả mô phỏng trên Hình 2.24 thể hiện rõ điều này. Giá trị BER lớn nhất là 10−5,
 ngoài ra còn có nhiều lộ trình mà giá trị BER lớn hơn giới hạn cho phép.
 0.06 0.12
 BPD toàn phần BPD toàn phần
 0.05 BPD do QoT 0.10 BPD do QoT
 0.04 0.08
 0.03 0.06
 BPD
 BPD
 0.02 0.04
 0.01 0.02
 0.00 0.00
 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1
 Tải lưu lượng (Erlang) Tải lưu lượng (Erlang)
 (a) (b)
 Hình 2.25. Sự thay đổi của BPD theo tải lưu lượng của giao thức AODV khi tổng số nút là
 50, tốc độ di chuyển trung bình 5 m/s, băng thông kênh (a) 40 MHz và (b) 80 MHz
 SNR và BER của một số lộ trình không thỏa mãn điều kiện ràng buộc về QoT theo
 yêu cầu là một trong những nguyên nhân làm tăng BPD trên toàn mạng. Kết quả mô
 phỏng trên các Hình 2.25, 2.26 và 2.27 thể hiện rõ điều này. Hình 2.25 cho ta thấy sự
0.08 0.08
 BPD toàn phần BPD toàn phần
0.07 0.07
 BPD do QoT BPD do QoT
0.06 0.06
0.05 0.05
0.04 0.04
BPD
 BPD
0.03 0.03
0.02 0.02
0.01 0.01
0.00 0.00
51015205101520
 Tốc độ di chuyển (m/s) Tốc độ di chuyển (m/s)
 Hình 2.26. Sự thay đổi của BPD theo tốc độ di chuyển của giao thức AODV khi tổng số
 nút mạng là 50, tải lưu lượng 0.6 Erlang, băng thông kênh 40 MHz
 61
 thay đổi của BPD theo tải lưu lượng trong trường hợp tổng số nút mạng là 50, tốc độ di
 chuyển trung bình 5 m/s và băng thông kênh 40 MHz và 80 MHz. Ta thấy rằng, BPD
 tăng dần theo tải lưu lượng. Trong đó, thành phần BPD do không đảm bảo QoT chiếm
 tỷ lệ khá cao trong tổng số BPD của toàn mạng, đặc biệt là trường hợp sử dụng kênh
 có băng thông 80 MHz (Hình 2.25b).
 Khi thay đổi tốc độ di chuyển của các nút mạng, kết quả thu được như ở Hình 2.26.
 Ta thấy rằng, PDB càng tăng khi tốc độ di chuyển càng cao. Ngoài sự phụ thuộc vào
 tốc độ di chuyển, BPD còn phụ thuộc vào tổng số nút mạng. Điều này thể hiện rõ qua
 kết quả ở Hình 2.27. Khi tổng số nút mạng tăng thì ảnh hưởng của các hiệu ứng vật lý
 tăng lên, làm tăng BPD do không đảm bảo QoT, dẫn đến tăng BPD toàn mạng.
0.05 0.05
 BPD toàn phần BPD toàn phần
 BPD do QoT BPD do QoT
0.04 0.04
0.03 0.03
BPD
 BPD
0.02 0.02
0.01 0.01
0.00 0.00
30 35 40 45 50 30 35 40 45 50
 Tổng số nút mạng Tổng số nút mạng
 Hình 2.27. Sự thay đổi của BPD theo tổng số nút của giao thức AODV khi tốc độ di
 chuyển trung bình 10 m/s, tải lưu lượng 0.6 Erlang, băng thông kênh 40 MHz
 Qua các kết quả mô phỏng ở trên ta có thể kết luận rằng, trong trường hợp hệ thống
 mạng MANET có vùng diện tích rộng, mật độ nút cao, sử dụng kênh có băng thông
 lớn, ảnh hưởng của các hiệu ứng vật lý làm tăng BPD trên toàn mạng. Điều này làm
 suy giảm hiệu năng mạng. Vì vậy, việc xem xét các điều kiện ràng buộc về QoT trong
 các thuật toán định tuyến là điều cần thiết, nhằm đảm bảo QoT của hệ thống mạng.
 2.6. Kết luận chương
 Để nâng cao chất lượng tín hiệu truyền dẫn trong mạng MANET có vùng diện tích
 rộng, sử dụng kênh có băng thông cao, việc nghiên cứu ảnh hưởng của các hiệu ứng
 vật lý đến hiệu năng mạng là điều cần thiết. Trong chương này, tác giả đã tập trung
 nghiên cứu các hiệu ứng vật lý xảy ra trên lộ trình truyền truyền dữ liệu, tập trung
 62
vào các tham số cơ bản phản ảnh chất lượng truyền dẫn của một lộ trình, đó là suy
hao công suất qua môi trường truyền dẫn, tỷ lệ tín hiệu trên nhiễu, tỷ lệ bit lỗi. Thông
qua việc phân tích một lộ trình cụ thể, tác giả đã cho thấy rằng, tùy theo chuẩn truyền
thông không dây, kỹ thuật điều chế và độ rộng của băng thông kênh được sử dụng, mà
các điều kiện ràng buộc về chất lượng truyền dẫn cần phải được xác định phù hợp để
đảm bảo chất lượng tín hiệu truyền dẫn, nhằm đảm bảo hiệu năng của hệ thống mạng.
Ngoài ra, ảnh hưởng của các hiệu ứng vật lý đến hiệu năng mạng khi sử dụng các giao
thức định tuyến DSR và AODV cũng đã được phân tích trong chương này. Kết quả mô
phỏng đã chứng minh rằng, ảnh hưởng của các hiệu ứng vật lý làm tăng BPD, dẫn đến
suy giảm hiệu năng của hệ thống mạng. Vì vậy, để đảm bảo hiệu năng mạng, cần phải
xem xét đến các điều kiện ràng buộc về QoT trong các thuật toán định tuyến. Đồng
thời, việc nghiên cứu cải tiến các thuật toán định tuyến nhằm giảm thiểu ảnh hưởng
của các hiệu ứng vật lý, nâng cao hiệu năng mạng là điều hết sức cần thiết. Các kết
quả nghiên cứu về vấn đề này được trình bày chi tiết trong chương tiếp theo.
 Các kết quả nghiên cứu trong chương này đã được công bố trong 03 bài báo khoa
học chuyên ngành. Trong đó, có 02 bài báo công bố trong Kỷ yếu Hội thảo Nghiên
cứu cơ bản và ứng dụng công nghệ thông tin - FAIR 2015 [B8] và FAIR 2017 [B6],
01 bài báo công bố trong Kỷ yếu Hội thảo Một số vấn đề chọn lọc trong Công nghệ
thông tin và Truyền thông - @ 2018 [B3].
 63
 CHƯƠNG 3
 ĐỊNH TUYẾN CÂN BẰNG TẢI ĐẢM BẢO CHẤT LƯỢNG
TRUYỀN DẪN DỰA TRÊN TẢI LƯU LƯỢNG QUA MỖI LỘ TRÌNH
 Nội dung chương này trình bày thuật toán định tuyến cân bằng tải đảm bảo QoT
 được đề xuất cho mạng MANET nhằm cải thiện QoT của các kênh truyền dữ liệu,
 nâng cao hiệu năng mạng MANET. Các kết quả nghiên cứu cụ thể được trình bày với
 bố cục như sau: Phần 3.1 phân tích vấn đề nghiên cứu. Phần 3.2 trình bày các cơ sở lý
 thuyết liên quan được sử dụng trong việc đề xuất thuật toán. Phần 3.3 đi sâu phân tích
 ý tưởng và phát biểu thành mô hình giải tích của thuật toán được đề xuất. Phần 3.4
 trình bày nguyên lý hoạt động của thuật toán. Phần 3.5 và 3.6 trình bày việc áp dụng
 thuật toán định tuyến được đề xuất để cải tiến cơ chế khám phá lộ trình của các giao
 thức DSR và AODV. Các kết quả mô phỏng thử nghiệm được trình bày chi tiết trong
 Phần 3.7. Cuối cùng là kết luận chương, được trình bày chi tiết trong Phần 3.8.
 3.1. Đặt vấn đề
 Các kết quả nghiên cứu về hiệu năng của mạng MANET khi sử dụng các giao thức
 định tuyến cân bằng tải ở Chương 2 đã chứng minh rằng, định tuyến cân bằng tải cho
 phép giảm tình trạng nghẽn cục bộ tại các nút trung gian nhờ tải lưu lượng phân phối
 đồng đều qua các kết nối. Tuy nhiên, kỹ thuật định tuyến này cũng làm giảm QoT do
 các lộ trình truyền dữ liệu có thể đi qua nhiều nút trung gian, nhiều bước truyền. Để
 thấy rõ điều này, chúng tôi phân tích QoT trên các lộ trình truyền dữ liệu khi sử dụng
 thuật toán định tuyến cân bằng tải FMLB [70] cho tô-pô mạng MANET có 15 nút như
 ở Hình 3.1. Các tham số kỹ thuật của hệ thống mạng được thiết lập như ở Bảng 2.5
 của Phần 2.5.1 (kịch bản mô phỏng ở Chương 2). SNR (dB) của tất cả các lộ trình
 trong mạng được biểu diễn bởi ma trận Q như cho thấy ở phương trình (3.1). Ta thấy
 rằng, có nhiều lộ trình với SNR rất thấp. Ví dụ, SNR của lộ trình từ nút 6 đến nút 11
 chỉ 21.0 dB, từ nút 13 đến nút 7 cũng chỉ 21.4 dB. Giả sử hệ thống mạng sử dụng giao
 thức MAC 802.11 với dạng điều chế 256-QAM, ngưỡng BER yêu cầu là 10−6. Theo
 lý thuyết về sự phụ thuộc giữa BER và SNR, giá trị SNR yêu cầu tối thiểu phải là 23.5
 64
dB. Như vậy, hai lộ trình trên không đảm bảo QoT do giá trị SNR của nó nhỏ hơn SNR
yêu cầu tối thiểu.
 11
 1 7
 3
 12 5
 2
 13 8 9
 4
 14
 15 10
 6
 Hình 3.1. Một ví dụ về mạng MANET có 15 nút.
 2 3
 − 22:5 25:7 22:4 23:9 22:1 23:5 25:1 24:8 23:4 27:6 28:6 25:6 21:5 23:8
 6 7
 622:5 − 25:4 27:7 28:3 23:3 25:7 25:4 25:9 25:2 24:1 23:4 22:3 28:1 22:07
 6 7
 6 7
 625:7 25:4 − 25:2 28:6 22:2 27:5 23:8 24:1 23:6 30:0 23:9 22:6 23:6 21:27
 6 7
 6 7
 622:4 27:7 25:2 − 27:9 25:3 25:5 29:4 30:6 28:8 24:0 25:5 23:8 33:6 23:47
 6 7
 6 7
 623:9 28:3 28:6 27:9 − 23:4 29:1 25:6 26:0 25:3 26:3 22:6 21:6 25:2 22:17
 6 7
 6 7
 622:1 23:3 22:2 25:3 23:4 − 22:3 25:0 25:5 27:8 21.0 23:2 25:3 24:7 28:07
 6 7
 6 7
 623:5 25:7 27:5 25:5 29:1 22:3 − 24:0 24:3 23:8 25:6 22:3 21:4 23:7 21:37
 6 7
 6 7
 Q = 625:1 25:4 23:8 29:4 25:6 25:0 24:0 − 35:6 28:3 23:2 27:8 25:1 28:0 23:37 (3.1)
 6 7
 6 7
 624:8 25:9 24:1 30:6 26:0 25:5 24:3 35:6 − 29:4 23:0 27:1 24:8 28:8 23:67
 6 7
 6 7
 623:4 25:2 23:6 28:8 25:3 27:8 23:8 28:3 29:4 − 22:0 25:0 23:4 27:6 24:97
 6 7
 6 7
 627:6 24:1 30:0 24:0 26:3 21:6 25:6 23:2 23:1 22:7 − 25:1 23:5 22:7 22:37
 6 7
 6 7
 628:6 23:4 23:9 25:5 22:6 23:2 22:3 27:8 27:1 25:0 25:1 − 28:6 24:9 25:67
 6 7
 6 7
 625:6 22:3 22:6 23:8 21:6 25:3 21.4 25:1 24:8 23:3 23:5 28:6 − 23:3 28:67
 6 7
 6 7
 621:5 28:1 23:6 33:6 25:2 24:7 23:7 28:0 28:8 27:6 22:7 24:9 23:3 − 23:07
 4 5
 23:8 22:0 21:2 23:4 22:1 28:0 21:3 23:3 23:6 24:9 22:3 25:6 28:6 23:0 −
 Để đảm bảo QoT trên các lộ trình truyền dữ liệu, một số công trình nghiên cứu đã
công bố trong thời gian gần đây đã đề xuất các thuật toán định tuyến có xét đến các
điều kiện ràng buộc của QoT [24, 46, 58,5]. Mục tiêu của các thuật toán định tuyến
ràng buộc QoT đã được đề xuất là lựa chọn lộ trình có QoT tốt nhất để truyền dữ liệu.
 65
Tuy nhiên, với các mô hình mạng có tô-pô mắt lưới như MANET, kỹ thuật định tuyến
theo QoT tốt nhất có thể làm tăng tình trạng nghẽn cục bộ do tải lưu lượng phân bố
không đồng đều trong mạng. Điều này cho ta thấy rõ từ ma trận lưu lượng T như ở
phương trình (3.2), trong đó T (Erlang) là ma trận biểu diễn tải lưu lượng được phân
phối qua tất cả các kết nối trong mạng MANET có cấu trúc như ở Hình 3.1, sử dụng
thuật toán định tuyến DSR-SNR [24]. Ta thấy rằng, tải lưu lượng phân phối không
đồng đều cho tất cả các kết nối. Một số kết nối chịu tải lưu lượng lớn hơn 1.3 Erlang
như các kết nối 3 ! 5, 5 ! 4 và 10 ! 6, nhưng cũng có một số kết nối chỉ chịu tải lưu
lượng khoảng 0.32 Erlang như các kết nối 3 ! 7 và 15 ! 13. Điều này cho thấy rằng,
tài nguyên mạng được khai thác không hiệu quả.
 2 − − − − − − − − − − 1:26 1:07 − − − 3
 6 7
 6 − − − 0:50 0:63 − − − − − − − − 0:38 − 7
 6 7
 6 − − − − 1.39 − 0.32 − − − 1:13 − − − − 7
 6 7
 6 7
 6 − 0:50 − − 1:26 − − − 1:20 1:26 − − − 0:50 − 7
 6 7
 6 − : : − − : − − − − − − − − 7
 6 0 63 1 20 1.45 0 57 7
 6 7
 6 − − − − − − − − − 1:39 − − − − 0:697
 6 7
 6 7
 6 − − 0:32 − 0:57 − − − − − − − − − − 7
 6 7
T = 6 − − − − − − − − 1:01 0:44 − 1:32 − − − 7 (3.2)
 6 7
 6 7
 6 − − − 1:13 − − − 1:07 − 0:19 − − − − − 7
 6 7
 6 − − − 1:13 − 1.32 − 0:63 0:19 − − − − − − 7
 6 7
 6 7
 61:07 − 1:32 − − − −−−−−−−−− 7
 6 7
 61:26 − − − − − − 1:07 − − − − 0:95 − − 7
 6 7
 6 7
 6 −−−− − − −−−−− 0:88 − − 0:387
 6 7
 6 − : − : − − −−−−−−−−− 7
 4 0 38 0 50 5
 − − − − − 0:76 − − − − − − 0.32 − −
 Từ các kết quả phân tích ở trên ta thấy rằng, một vấn đề đặt ra là làm thế nào để
kết hợp hài hòa giữa kỹ thuật định tuyến cân bằng tải và kỹ thuật định tuyến đảm bảo
QoT, để tìm ra tập lộ trình mà tải lưu lượng phân phối đồng đều cho tất cả các kết
 Định tuyến Tải lưu lượng 
 “đường ngắn nhất” phân bố không Nghẽn cục bộ 
 hoặc QoT tốt nhất đồng đều 
 Định tuyến cân 
 bằng tải đảm 
 bảo QoT 
 Định tuyến cân Tồn tại các QoT suy giảm 
 bằng tải “lộ trình dài” 
 Hình 3.2. Mô hình đề xuất ý tưởng định tuyến cân bằng tải đảm bảo QoT
 66
nối trong mạng, đồng thời thỏa mãn các điều kiện ràng buộc của QoT như minh họa
ở Hình 3.2. Với ý tưởng này, tác giả đề xuất một thuật toán định tuyến cân bằng tải,
đồng thời đảm bảo QoT của các lộ trình truyền dữ liệu. Giải pháp đề xuất được cải
tiến từ thuật toán khám phá lộ trình của giao thức định tuyến theo yêu cầu trong mạng
MANET. Lộ trình cân bằng tải được lựa chọn dựa trên thông tin về xác suất chặn gói
dữ liệu từ nguồn đến đích. Thuật toán đề xuất được đặt tên LBRQT (Load Balancing
Routing ensuring Quality of Transmission).
3.2. Cơ sở lý thuyết liên quan
 Để có cơ sở xác định mục tiêu và các điều kiện ràng buộc trong quá trình khám
phá lộ trình của giải pháp định tuyến LBRQT, nội dung phần này trình bày các cơ sở
lý thuyết liên quan đến việc phân tích, tính toán các độ đo hiệu năng dựa trên lý thuyết
hàng đợi và lý thuyết xác suất thống kê, bao gồm xác suất chặn gói dữ liệu và thời gian
trễ từ nguồn đến đích.
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
3.2.1.1. Xác suất chặn gói dữ liệu trên một bước truyền
 Xét một kết nối không dây từ nút I đến nút J trong mạng không dây tùy biến (ci j),
trong trường hợp lưu lượng yêu cầu đến kết nối ci j tuân theo phân bố Poisson [12, 23,
52], thời gian truyền gói trên kênh truyền theo phân phối hàm mũ, khi đó một kết nối
ci j trong mạng không dây tùy biến tương đương với một mô hình hàng đợi M/M/1/L
[6, 63, 68] như cho thấy trong Hình 3.3, với L là tổng số gói dữ liệu tối đa trong hệ
thống, bao gồm tổng số gói trong bộ đệm và gói đang truyền trên kênh truyền.
 Node i Node j 
 ij (Poisson) ij 
 Buffer 
 L packets 
 Hình 3.3. Mô hình một cổng ra của nút mạng không dây tùy biến
 Gọi li j là tốc độ đến trung bình của các gói dữ liệu muốn truyền qua kênh ci j, thời
gian phục vụ các gói dữ liệu theo phân phối hàm mũ với tốc độ trung bình là mi j. Từ đó
 67
 ij ij ij ij ij 
 0 1 2 .. L -1 L
 ij ij ij ij ij 
 Hình 3.4. Lược đồ chuyển đổi trạng thái một cổng ra của nút mạng tùy biến theo mô
 hình hàng đợi M/M/1/L
ta có lược đồ chuyển đổi trạng thái của hệ thống được minh họa như ở Hình 3.4[15].
 (n)
Gọi Pi j là xác suất hệ thống ở trạng thái n, nghĩa là xác suất có n gói dữ liệu trong hệ
thống, ta có hệ phương trình cân bằng trạng thái sau đây [54]: 
 8 (0) (1)
 >li jP = mi jP n = 0
 > i j i j
 < (n) (n−1) (n+1)
 (li j + mi j)Pi j = li jPi j + mi jPi j n 2 [1;K − 1] (3.3)
 >
 > (K−1) (K)
 :li jPi j = mi jPi j n = K
 (n)
 Bằng cách giải hệ phương trình trạng thái (3.3) ta xác định được Pi j . Đối với các
gói dữ liệu muốn truyền từ nút i đến nút j, gói dữ liệu sẽ bị chặn trong trường hợp gói
đến tại thời điểm bộ đệm đầy và kênh truyền ci j đang ở trạng thái bận, nghĩa là trong
hệ thống đang có L gói dữ liệu. Vì vậy, xác suất gói dữ liệu bị chặn (BPD) được xác
định như sau:
 8 L
 ri j(1 − ri j)
 nếu ri j 6= 1
 (h) (L) 1 − rL+1
 Bi j ≡ Pi j = i j (3.4)
 :> 1 =
 L + 1 nếu ri j 1
trong đó, ri j = li j=mi j là mật độ lưu lượng phân phối đến kết nối từ nút I đến nút J.
3.2.1.2. Xác suất chặn gói dữ liệu trên một lộ trình
 (r) (r)
 Gọi Bsd là xác suất gói dữ liệu bị chặn (BPD) trên lộ trình rsd, Bsd là xác suất gói
dữ liệu được truyền thành công (không bị chặn) qua lộ trình rsd. Theo lý thuyết xác
suất thông kê ta có:
 (r) (r)
 Bsd = 1 − Bsd (3.5)
 Khi dữ liệu truyền trên lộ trình rsd, một gói dữ liệu được truyền thành công từ nút
nguồn S đến nút đích D khi và chỉ khi gói dữ liệu này truyền thành công qua tất cả các
 68
bước truyền mà lộ trình rsd đi qua. Do vậy ta có:
 (r) (h) (h)
 Bsd = ∏ Bi j = ∏ (1 − Bi j ) (3