Đánh giá một số giao thức định tuyến đa đường giảm thời gian trễ trong mạng manet

Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 
 51
ĐÁNH GIÁ MỘT SỐ GIAO THỨC ĐỊNH TUYẾN ĐA ĐƯỜNG 
GIẢM THỜI GIAN TRỄ TRONG MẠNG MANET 
Đỗ Đình Cường*, Nguyễn Anh Chuyên 
Trường Đại học Công nghệ Thông tin & Truyền thông – ĐH Thái Nguyên 
TÓM TẮT 
Trong những năm gần đây có một hướng tiếp cận mới cho bài toán định tuyến trong mạng 
MANET là định tuyến đa đường. Bài báo này trình bày một cách tổng quan về các đặc điểm chính 
trong cơ chế hoạt động của một số giao thức định tuyến đa đường mới cho mạng MANET tiếp cận 
theo mục tiêu giảm thời gian trễ, sau đó thực hiện việc phân tích, so sánh và đánh giá chúng theo 
các tiêu chí về hiệu năng hoạt động, đồng thời chỉ ra hướng cần cải tiến của các giao thức này. 
Từ khoá: Mạng MANET, Định tuyến đa đường, Thời gian trễ, Tìm đường, Lựa chọn đường. 
GIỚI THIỆU* 
Mạng không dây di động không cấu trúc 
(MANET) là một mạng bao gồm tập các nút 
di động không có cơ chế quản trị tập trung. 
Mạng MANET có khả năng tự cấu hình, tự tổ 
chức và tự bảo trì hoạt động của mình, có thể 
tương thích với các mạng có hình trạng động. 
Tuy nhiên, mỗi nút di động lại có những hạn 
chế về tài nguyên như năng lượng nguồn, khả 
năng xử lý và bộ nhớ. Cơ chế truyền thông 
giữa các nút di động trong mạng MANET là 
cơ chế đa chặng. Do đó, thời gian tồn tại của 
mỗi nút đi động trong mạng là rất quan trọng. 
Việc thiết kế giao thức định tuyến hiệu quả 
cho mạng MANET là một bài toán được quan 
tâm nhiều trong các nghiên cứu về hệ thống 
mạng di động trong thời gian qua. 
Có nhiều giao thức định tuyến đơn đường cho 
mạng MANET đã được đề xuất và có thể chia 
chúng thành hai nhóm chính là các giao thức 
“tìm đường trước” và các giao thức “tìm 
đường theo yêu cầu”. Các giao thức này đều 
chỉ sử dụng duy nhất một con đường tối ưu để 
truyền dữ liệu giữa một cặp nút nguồn-đích. 
Thông thường đây là con đường ngắn nhất. 
Các nghiên cứu trong [1], [2], [10] và [13] đã 
chỉ ra rằng, thuật toán tìm đường ngắn nhất 
không phải là lựa chọn tốt nhất cho mạng 
MANET. Khi thuật toán này được sử dụng, 
các nút phân bố xung quanh tâm sẽ phải 
truyền lưu lượng dữ liệu định tuyến nhiều hơn 
các nút phân bố gần biên của mạng. Điều này 
*
 Tel: 0982 990908, Email: ddcuong@ictu.edu.vn 
có thể gây ra tình trạng tắc nghẽn khi có nhiều 
kết nối được thiết lập trong mạng làm ảnh 
hưởng tới hiệu năng mạng ở khía cạnh thời 
gian trễ và thông lượng. 
Để giải quyết các hạn chế này, thay vì việc 
tìm ra và sử dụng duy nhất một con đường để 
truyền dữ liệu, sẽ có nhiều hơn một con 
đường được sử dụng đồng thời để truyền dữ 
liệu trong các giao thức định tuyến đa đường. 
Các giao thức định tuyến đa đường được phân 
loại theo mục tiêu tiếp cận của chúng. Trong 
số năm nhóm giao thức định tuyến đa đường 
đã được phân loại trong [12], bài báo này chỉ 
tập trung đánh giá nhóm thứ nhất là nhóm các 
giao thức định tuyến đa đường giảm thời gian 
trễ. Nhóm này bao gồm các giao thức: Định 
tuyến đường dự phòng [8], định tuyến đa 
đường trên cơ sở định tuyến vùng Fresnel 
(FZR) [7], định tuyến AODV đa đường với 
cơ chế chọn đường theo xác suất (AODVM-
PSP) [6], định tuyến đa đường có độ ưu tiên 
(PRIMAR) [5], định tuyến theo góc địa lý 
(BGR) [11] và định tuyến đa đường Split-n-
save [4]. 
Phần còn lại của bài báo được tổ chức như 
sau: Mục 2 trình bày về hoạt động chi tiết, ưu 
điểm, nhược điểm và các hạn chế của các 
giao thức định tuyến đa đường nhằm giảm 
thời gian trễ đã nói đến ở trên. Mục 3 thực 
hiện việc so sánh phân tích các giao thức đã 
đưa ra trên các tham số về hiệu năng. Mục 4 
phân tích các nhược điểm cần cải tiến của các 
giao thức này và Mục 5 là kết luận của bài báo. 
Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 
 52
ĐỊNH TUYẾN ĐA ĐƯỜNG NHẰM GIẢM 
THỜI GIAN TRỄ 
Phần lớn các giao thức định tuyến đa đường 
đều được phát triển từ các giao thức định 
tuyến đơn đường truyền thống dành cho mạng 
MANET là giao thức DSR[3] và AODV[9]. 
Tuy nhiên các giao thức DSR và AODV 
không có khả năng tương thích cao với các 
mạng có kích thước thay đổi thường xuyên. 
Vấn đề thay đổi hình trạng mạng dẫn đến tình 
trạng làm tăng các gói tin điều khiển, tăng 
thời gian trễ, mất độ tin cậy khi truyền dữ liệu 
và tốn năng lượng nguồn nuôi các nút di 
động. Thời gian trễ lớn khi truyền gói tin giữa 
hai điểm đầu-cuối là một vấn đề ảnh hưởng 
nhiều tới hiệu năng của các giao thức định 
tuyến theo yêu cầu. Nguyên nhân của vấn đề 
này là việc lựa chọn đường không hiệu quả, 
cân bằng tải không thích hợp và số lượng gói 
tin điều khiển lớn. 
Mục tiêu chính của những giao thức định 
tuyến thuộc nhóm định tuyến đa đường nhằm 
giảm thời gian trễ là đảm bảo cân bằng tải dữ 
liệu giữa các nút di động sao cho không có 
đoạn mạng nào bị tắc nghẽn. Các tác giả 
Pham và Perau trong [10] đã chỉ ra rằng nếu 
sử dụng định tuyến chọn đường ngắn nhất, 
các liên kết gần tâm của mạng phải hoạt động 
nhiều hơn so với các liên kết ở gần biên. Do 
đó không đảm bảo cân bằng tải dữ liệu giữa 
các nút mạng và điều này làm cho thời gian 
trễ của các gói tin phải truyền qua tâm của 
mạng tăng lên. Để giải quyết vấn đề này các 
giao thức định tuyến đa đường giảm thời gian 
trễ dành cho mạng MANET đã được đề xuất. 
Giao thức định tuyến đa đường dự phòng 
Một cơ chế định tuyến có tên gọi là định 
tuyến đa đường dự phòng đã được tác giả Lim 
giới thiệu trong [8] nhằm cải thiện hiệu năng 
của các mạng sử dụng giao thức TCP ở tầng 
Chuyển vận. Tác giả này đã phát biểu rằng 
mặc dù giao thức định tuyến đa đường làm 
việc tốt với các lưu lượng UDP nhưng khi sử 
dụng các lưu lượng TCP, hiệu năng của nó sẽ 
bị giảm. Vấn đề giảm hiệu năng này do một 
trong các nguyên nhân sau gây nên: thứ nhất 
là không ước lượng được một cách chính xác 
thời gian truyền một vòng trung bình (RTT) 
trong định tuyến đa đường bởi vì mỗi một con 
đường có một giá trị RTT khác nhau và thứ 
hai là các gói tin đi theo các con đường khác 
nhau tới đích với thứ tự thay đổi có thể làm 
cho nút đích gửi đúp gói báo nhận dẫn tới 
việc giảm một cách không cần thiết kích 
thước cửa sổ trượt. Để giải quyết vấn đề này, 
chỉ có một con đường được sử dụng tại một 
thời điểm nhưng vẫn cần duy trì các con 
đường dự phòng. Vấn đề quan trọng ở đây 
chính là cơ chế lựa chọn đường chính cũng 
như lựa chọn một tập các đường dự phòng. 
Khác với giao thức DSR, một nút đích chỉ trả 
lời hai gói yêu cầu tìm đường. Một gói trả lời 
đường chứa đường chính và một gói khác 
chứa đường dự phòng. Nút đích sử dụng ba 
điều kiện chính để lựa chọn đường: (1) đường 
ngắn nhất, (2) đường có thời gian trễ nhỏ nhất 
và (3) đường khác biệt nhiều nhất. Đường 
ngắn nhất tương tự như đường do giao thức 
DSR lựa chọn. Sự kết hợp của ba điều kiện 
này sẽ tạo thành nhiều kiểu cơ chế lựa chọn 
đường chính và đường dự phòng khác nhau. 
Cơ chế lựa chọn thứ nhất thực hiện việc chọn 
đường ngắn nhất là đường chính và đường có 
độ trễ nhỏ nhất là đường dự phòng. Cơ chế 
thứ hai chọn đường có độ trễ ngắn nhất làm 
đường chính và đường khác biệt nhiều nhất là 
đường dự phòng. Kết quả mô phỏng của 
nghiên cứu này đã cho thấy rằng hiệu năng 
của mạng đã được tăng lên đối với thông số 
độ trễ định tuyến và lượng thông điệp điều 
khiển khi các nút di chuyển với tốc độ từ 
10m/s tới 20m/s khi áp dụng định tuyến đa 
đường dự phòng so với định tuyến DSR khi 
áp dụng cơ chế thứ nhất. 
Giao thức định tuyến đa đường trên cơ sở 
định tuyến vùng Fresnel 
Định tuyến đa đường trên cơ sở định tuyến 
vùng Fresnel (FZR) được các tác giả Liang và 
Midkiff đề xuất trong [7]. Khái niệm vùng 
Fresnel là khái niệm xuất phát từ lý thuyết 
truyền sóng áp dụng vào kỹ thuật định tuyến 
trong mạng ad-hoc. FZR phân loại các nút 
trung gian theo khả năng và hiệu suất chuyển 
tiếp gói tin của chúng. Giao thức FZR là giao 
thức định tuyến kết hợp giữa kỹ thuật định 
tuyến “tìm đường trước” và kỹ thuật định 
tuyến “theo yêu cầu”. FZR có thể làm giảm 
Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 
 53
bớt tắc nghẽn tại các nút trung gian và đạt 
được thông lượng tốt hơn tại tầng Chuyển 
vận. Nó sử dụng độ đo số chặng trong quá 
trình xây dựng vùng. Xét một nút nguồn S và 
một nút đích D trong mạng. Khoảng cách 
ngắn nhất tính theo số chặng giữa S và D là L. 
Nếu có một con đường ngắn nhất từ S tới D 
qua một nút trung gian có L+n-1 chặng thì nút 
này thuộc vào vùng thứ n và con đường này 
được gọi là con đường thứ n. Trong FZR, mỗi 
một nút phải duy trì một bảng khoảng cách. 
Để xây dựng và duy trì bảng này, nút di động 
sử dụng các gói tin Hello. Khi một nút nhận 
được một gói tin Hello, nó sẽ cập nhật bảng 
khoảng cách của mình. Khi bảng khoảng cách 
được truyền qua mạng, mỗi nút sẽ cập nhật 
bảng khoảng cách của mình và xác định con 
đường thứ nhất. FZR xác định con đường thứ 
hai theo kiểu “tìm đường theo yêu cầu”. Khi 
có một nút nằm trong vùng thứ nhất khởi tạo 
tiến trình tìm đường bằng gói tin yêu cầu 
đường, gói tin này sẽ được quảng bá tới các 
nút láng giềng thuộc vùng thứ hai. Ta gọi nút 
thuộc vùng thứ hai nhận gói tin yêu cầu 
đường đầu tiên là nút láng giềng một chặng. 
Nút một chặng sẽ tiếp tục quảng bá gói tin 
này tới các nút láng giềng của nó. Khi một nút 
tiếp theo nằm trong vùng thứ hai nhận được 
gói tin yêu cầu đường từ nút một chặng, nó sẽ 
là nút hai chặng. Nút hai chặng này sẽ gửi gói 
tin trả lời đường cho nút nguồn qua nút láng 
giềng một chặng. Nút láng giềng một chặng 
sẽ ghi lại con đường chuyển tiếp qua nút 2 
chặng vào bảng định tuyến của mình và 
chuyển tiếp gói tin trả lời đường tới nút 
nguồn. Khi đó nút nguồn sẽ ghi con đường 
này vào bảng định tuyến của mình. Với cơ 
chế này, một nút nguồn có thể tìm ra một 
hoặc nhiều đường thứ hai. Có thể hình thành 
nhiều vùng bằng cách sử dụng phương pháp 
này nhưng để hạn chế nhiễu, định tuyến FZR 
chỉ giới hạn sử dụng con đường thứ nhất và 
đường thứ hai. FZR chấp nhận cách tiếp cận 
đơn giản khi phân phối dữ liệu qua nhiều 
đường. Nếu tồn tại nhiều con đường khác 
nhau, FZR sẽ phân phối dữ liệu từng phần 
qua tất cả các con đường. Quá trình phân phối 
dữ liệu qua nhiều đường có thể điều chỉnh 
động tuỳ theo điều kiện về băng thông và tắc 
nghẽn của mạng. 
Giao thức định tuyến AODV đa đường với 
cơ chế chọn đường theo xác suất 
Giao thức định tuyến đa đường theo yêu cầu 
dạng véc tơ khoảng cách với cơ chế chọn 
đường theo xác suất (AODVM-PSP) do tác 
giả Jing đề xuất trong [6]. Giao thức này là 
giao thức mở rộng của giao thức AODVM 
[15]. Tiến trình tìm đường của AODVM-DSP 
tương tự như AODV [9]. Quá trình thiết lập 
nhiều đường tương tự như giao thức 
AODVM. Sự khác biệt chính giữa AODVM-
DSP và AODVM là AODVM-DSP xem xét 
đến yếu tố độ trễ dọc theo con đường khi đưa 
ra một quyết định chọn đường. Khi một nút 
gửi một gói tin tới đích, gói tin này sẽ chứa 
các thông tin về thời gian bắt đầu được truyền 
đi. Một nút trung gian hoặc một nút nguồn có 
thể ước lượng độ trễ trên cơ sở thông tin này. 
Nút nguồn xác định con đường tốt nhất theo 
xác suất của con đường đó trên cơ sở độ trễ 
khi truyền theo đường này. Xác suất của một 
con đường thứ i giữa nút nguồn S và nút đích D 
ký hiệu là Pi(S, D) được tính bằng công thức: 
trong đó Ti(S, D) là thời gian trễ khi truyền từ 
nút S tới nút D theo con đường thứ i và k là 
số lượng các con đường đi từ nút S tới nút D. 
Khác với giao thức AODVM, giao thức 
AODVM-PSP không tìm kiếm các con đường 
khác biệt. Nó cũng không sử dụng các gói tin 
nhận biết sự tồn tại của các nút như AODVM. 
Vì vậy, tiến trình tìm đường của giao thức 
AODVM-PSP không diễn ra thường xuyên 
như trong giao thức AODVM và điều này làm 
giảm bớt lượng thông tin điều khiển truyền 
trong mạng. 
Giao thức định tuyến đa đường Split-n-Save 
Các tác giả Cha và Lee đã hiệu chỉnh giao 
thức AODVM thành giao thức split-n-save 
[4] nhằm đạt được hai mục tiêu chính: (1) để 
đảm bảo giao thức định tuyến đa đường hoạt 
động tốt qua thời gian hoạt động của các nút 
và (2) để cân bằng giữa định tuyến và chuyển 
tiếp dữ liệu trong mạng. Các tác giả này đã 
đặt tên cho hai mục tiêu trên là khả năng sống 
Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 
 54
của mạng và khả năng đáp ứng của nút. Khả 
năng sống của mạng được định nghĩa là số 
lượng nút đang hoạt động qua một khoảng 
thời gian cho trước. Khả năng đáp ứng của 
mạng được định nghĩa là tỷ lệ giữa số lượng 
gói tin do nút sinh ra trên số lượng gói tin do 
nút chuyển tiếp tới các nút khác. Các tác giả 
đã đề xuất một cơ chế phân kênh đơn giản 
dành cho việc chuyển đổi lưu lượng giữa các 
con đường. Theo cơ chế này, một nút nguồn 
sẽ chuyển đường truyền dữ liệu sau khi truyền 
k gói tin trên một con đường. Khi k=1, giao 
thức sẽ chuyển đường truyền dữ liệu sau mỗi 
gói tin được gửi. Khi k=0, nó sẽ sử dụng duy 
nhất một con đường cho đến khi đường này bị 
lỗi. Các kết quả mô phỏng trên cơ sở các giá 
trị k khác nhau đã chỉ ra rằng thời gian trễ cho 
từng gói tin cao hơn khi k=0 hoặc k=1 so với 
các trường hợp k lớn hơn 1. Đối với trường 
hợp k=0 hoặc k=1, giá trị thời gian trễ biến 
động tương đối rộng còn đối với các trường 
hợp k nhận giá trị khác, giá trị thời gian trễ 
biến động không nhiều. Từ các kết quả này, 
các tác giả đã kết luận rằng với trường hợp 
k=0 hoặc k=1, một số ít nút trong mạng phải 
đóng vai trò là nút trung tâm giữa các kết nối 
khác nhau do đó rất dễ xảy ra hiện tượng tắc 
nghẽn dữ liệu tại các nút này. Khi lựa chọn 
các giá trị k lớn hơn, xác xuất xảy ra hiện 
tượng tắc nghẽn này sẽ giảm đi. 
Giao thức định tuyến đa đường có độ ưu tiên 
Giao thức định tuyến đa đường có độ ưu tiên 
(PRIMAR) được đề xuất bởi Huang và Fang 
năm 2005 [5]. Trong giao thức này, nhiều con 
đường được lựa chọn giữa nút nguồn và nút 
đích phụ thuộc vào loại lưu lượng. Giao thức 
này giả định rằng nút nguồn nhận biết được 
độ quan trọng của một gói tin khi gửi nó tới 
nút đích. Nút nguồn sử dụng một giá trị để 
phân loại các gói tin dựa vào độ quan trọng 
của nó. Quá trình quyết định đường đi được 
tạo ra trên cơ sở sử dụng độ ưu tiên của giá trị 
này. Các gói tin có độ ưu tiên thấp hơn sẽ 
được truyền trên các con đường dài hơn so 
với các gói tin có độ ưu tiên cao. Độ ưu tiên 
được gán các giá trị từ 1 tới M với M là độ ưu 
tiên cao nhất. Gói tin có độ ưu tiên cao nhất 
sẽ được truyền trên con đường tối ưu trong số 
M con đường. Đường tối ưu được định nghĩa 
là đường có độ trễ nhỏ nhất. Mặc dù có M giá 
trị độ ưu tiên đã được thiết lập nhưng có thể 
có trường hợp số lượng các con đường đầu ra 
nhỏ hơn M. Trong trường hợp này độ ưu tiên 
cao nhất được thiết lập là m = min(M, K) với 
K là tổng số con đường giữa nút nguồn và nút 
đích đã tìm được. Sau khi nhận được một gói 
tin, một nút sẽ kiểm tra độ ưu tiên của gói tin 
và chuyển tiếp gói này tới chặng kế tiếp thích 
hợp. Độ trễ đầu-cuối luôn biến đổi trong 
mạng không dây vì vậy độ trễ trung bình 
được sử dụng để cập nhật bảng định tuyến. 
Các nút sẽ cập nhật độ trễ trung bình bằng 
cách sử dụng cơ chế báo nhận thuộc tầng 
MAC. Tiến trình duy trì đường của giao thức 
PRIMAR tương tự như giao thức DSR nhưng 
thủ tục duy trì đường của PRIMAR chỉ được 
kích hoạt khi có một con đường bị lỗi hoặc có 
một con đường không đáp ứng điều kiện về 
độ trễ của gói tin. Sự thay đổi này trong tiến 
trình duy trì đường cho phép giao thức 
PRIMAR đáp ứng được yêu cầu truyền dữ 
liệu có độ ưu tiên cao. 
Giao thức định tuyến theo góc địa lý 
Giao thức định tuyến theo góc địa lý (BGR) 
[11] được Popa và các cộng sự giới thiệu 
nhằm cải thiện thông số thời gian trễ của hiệu 
năng mạng bằng cách sử dụng thông tin về sự 
tắc nghẽn trong mạng. Ý tưởng chính của 
giao thức BGR là chèn vào mỗi gói tin một 
giá trị góc nghiêng bias. Giá trị này xác định 
quỹ đạo của con đường tiến về phía đích. Hai 
thuật toán điều khiển tắc nghẽnđược sử dụng 
trong giao thức BGR là thuật toán thuật toán 
tách gói trong mạng IPS và thuật toán tách 
gói đầu cuối EPS. Thuật toán IPS phân tách 
dòng lưu lượng truyền dữ liệu để tránh khỏi 
hiện tượng tắc nghẽn tức thời. Hiện tượng này 
xảy ra khi có quá nhiều kết nối cùng được 
thiết lập trên một đoạn mạng nào đó. Để tránh 
khỏi hiện tượng này, thuật toán IPS phân tách 
dòng lưu lượng dữ liệu ngay trước các điểm 
tắc nghẽn. Thuật toán này yêu cầu thông tin 
về tắc nghẽn phải được định kỳ trao đổi giữa 
các nút láng giềng. Nếu thuật toán IPS không 
đạt được hiệu quả về giảm tắc nghẽn, thuật 
Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 
 55
toán EPS sẽ được kích hoạt. Trong trường 
hợp của thuật toán EPS, nút nguồn sẽ chia lưu 
lượng dữ liệu theo nhiều con đường khác 
nhau và do đó giảm được tắc nghẽn. Các kết 
quả mô phỏng cho thấy rằng việc kết hợp 
giữa thuật toán IPS và thuật toán EPS cải 
thiện khá tốt thời gian phân phối gói tin giữa 
các nút và do đó làm cho thông lượng của 
mạng tăng lên. 
ĐÁNH GIÁ HIỆU NĂNG CÁC GIAO 
THỨC ĐỊNH TUYẾN ĐA ĐƯỜNG GIẢM 
THỜI GIAN TRỄ 
Trên cơ sở mô phỏng các giao thức định 
tuyến đa đường và so sánh cơ chế hoạt động 
của các giao thức [12], bảng sau đây trong 
đưa ra các so sánh về hiệu năng của các giao 
thức định tuyến đa đường giảm thời gian trễ: 
Nhìn vào bảng trên có thể kết luận rằng 
không có giao thức nào là tối ưu đối với mọi 
tham số về hiệu năng ngoài tham số về thời 
gian trễ. Tuy nhiên với từng trường hợp cụ 
thể ta có thể lựa chọn được giao thức phù hợp 
nhất. Đối với các mạng có tần suất di chuyển 
của các nút mạng và tần suất thay đổi hình 
trạng mạng là lớn, nếu chấp nhận được mức 
độ tiêu tốn nhiều năng lượng nguồn của các 
nút mạng và lượng thông tin điều khiển nhiều 
thì giao thức PRIMAR là giao thức tốt nhất. 
Đối với các mạng cần dành nhiều băng thông 
cho dữ liệu và tần suất di chuyển của các nút 
không nhiều đồng thời không yêu cầu quá cao 
về độ tin cậy tại tầng mạng thì giao thức định 
tuyến đa đường dự phòng là giao thức tối ưu. 
Đối với các mạng sử dụng các ứng dụng cần 
thời gian hoạt động dài của các nút mạng 
trong khi các nút mạng di chuyển nhiều và 
chấp nhận được tỷ lệ cao giữa số lượng gói 
tin điều khiển/ số lượng gói tin dữ liệu thì 
giao thức định tuyến Split-N-Save lại là sự 
lựa chọn hàng đầu. 
MỘT SỐ VẤN ĐỀ CẦN CẢI TIẾN TRONG 
CÁC GIAO THỨC ĐỊNH TUYẾN ĐA 
ĐƯỜNG 
Mặc dù các giao thức định tuyến đa đường cải 
thiện được kỹ thuật phân luồng dữ liệu, độ tin 
cậy, độ trễ và khả năng sử dụng hiệu quả 
năng lượng nhưng chúng vẫn gặp phải các 
vấn đề kỹ thuật sau: 
Chọn đường dài hơn: Trong một giao thức 
định tuyến đa đường, thông thường các gói 
tin di chuyển qua số chặng nhiều hơn so với 
giao thức định tuyến chọn đường ngắn nhất. 
Do đó, thời gian trễ khi truyền các gói tin sẽ 
lớn hơn. Vẫn cần có các thử nghiệm về các kỹ 
thuật lựa chọn các con đường truyền dữ liệu 
trong các giao thức định tuyến đa đường đã 
đề cập để hạn chế việc các giao thức sử dụng 
các con đường quá dài. 
Gói tin điều khiển đặc biệt: Ngoài các gói 
tin điều khiển sử dụng trong cơ chế tìm 
đường và duy trì đường, một giao thức định 
tuyến đa đường còn sử dụng thêm các gói tin 
điều khiển khác. Các gói tin điều khiển này 
được nút di động sử dụng để tập hợp các 
thông tin về các nút láng giềng để tìm ra các 
con đường khác. Chúng có thể chiếm một 
phần băng thông quan trọng trong mạng đặc 
biệt là đối với các mạng lớn và do đó làm ảnh 
hưởng tới hiệu năng của mạng. Vì vậy cần có 
những kỹ thuật làm hạn chế số lượng và kích 
thước gói tin điều khiển. 
Bảng 1: So sánh các thông số về hiệu năng của các giao thức định tuyến đa đường giảm thời gian trễ 
Giao thức Thông tin 
điều khiển Độ tin cậy 
Độ hiệu quả sử 
dụng năng 
lượng 
Hỗ trợ tính 
di động 
Định tuyến đường dự phòng [8] Ít Trung bình Trung bình Thấp 
Định tuyến đa đường Fresnel [7] Nhiều Thấp Thấp Cao 
Định tuyến AODVM-PSP [6] Nhiều Thấp Thấp Thấp 
Định tuyến PRIMAR [5] Nhiều Cao Thấp Cao 
Định tuyến BGR [11] Nhiều Thấp Trung bình Thấp 
Định tuyến Spit-n-Save [4] Nhiều Trung bình Cao Thấp 
Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 
 56
Cơn bão gói tin tìm đường: Giao thức định 
tuyến đa đường có thể sinh ra một số lượng 
lớn các gói tin tìm đường trong mạng 
MANET trong tiến trình tìm đường. Cần có 
những kỹ thuật và thuật toán hạn chế chuyển 
tiếp các gói tin tìm đường không cần thiết 
nhằm làm giảm hiệu ứng của cơn bão gói tin 
tìm đường. 
Tìm đường không hiệu quả: Tiến trình tìm 
đường của một giao thức định tuyến đa đường 
có thể không hiệu quả bằng các giao thức 
DSR và AODV. Trong tiến trình tìm đường 
của DSR và AODV, một nút trung gian được 
cho phép gửi gói tin trả lời từ bộ nhớ đường 
của chúng nếu chúng tìm thấy một con đường 
phù hợp trong bộ nhớ đường của mình. Điều 
này làm giảm thời gian tìm đường từ nút 
nguồn bởi vì nút nguồn có thể không phải đợi 
cho đến khi gói tin tìm đường đến được nút 
đích. Tuy nhiên, trong các giao thức định 
tuyến đa đường sử dụng các con đường khác 
biệt theo nút hoặc khác biệt theo liên kết, 
không cho phép các nút trung gian gửi gói tin 
trả lời từ bộ nhớ đường của mình. Do đó, nút 
nguồn phải đợi cho đến khi gói tin tìm đường 
tới được nút đích. Vì vậy, thông thường thời 
gian tìm đường của các giao thức định tuyến 
đa đường thường dài hơn so với giao thức 
DSR hoặc AODV. Do đó, cần có những cải 
tiến tiếp theo làm giảm thời gian tìm đường 
trong giao thức định tuyến đường dự phòng 
[8] khi sử dụng đường khác biệt. 
Xử lý các gói tin đúp: Để đảm bảo khả năng 
truyền dữ liệu một cách tin cậy, các giao thức 
định tuyến đa đường của Tsirigos [13] và 
Wang [14] đề xuất sử dụng các đường đi khác 
nhau để gửi các bản sao của cùng một gói tin. 
Các gói tin nhân bản chính là các gói tin dư 
thừa và đương nhiên là chúng sẽ chiếm giữ 
băng thông của hệ thống mạng. Thêm vào đó, 
các giao thức này cũng yêu cầu kỹ thuật nhân 
bản gói tin tại nút nguồn và lọc gói tin nhân 
bản tại nút đích. Các kỹ thuật xử lý gói tin 
đúp này vẫn cần được cải tiến để đạt được 
hiệu quả cao hơn. 
KẾT LUẬN 
Trong những năm gần đây đã có rất nhiều 
nghiên cứu tập trung vào mạng không dây 
kiểu không cấu trúc. Một trong những hướng 
nghiên cứu quan trọng là thiết kế các giao 
thức định tuyến đảm bảo thời gian truyền dữ 
liệu nhanh, độ tin cậy cao và có cơ chế đảm 
bảo chất lượng dịch vụ. Nhằm cải tiến các 
nhược điểm của các giao thức định tuyến đơn 
đường truyền thống trong mạng không dây 
kiểu không cấu trúc, đã có một số giao thức 
định tuyến đa đường tiếp cận theo mục tiêu 
giảm thời gian trễ khi truyền dữ liệu được đề 
xuất. Với những cải tiến đã đưa ra của các 
giao thức này, hiệu năng của chúng đã được 
cải thiện so với các giao thức đơn đường 
truyền thống nhưng rất khó để có thể lựa chọn 
một giao thức định tuyến đa đường giảm thời 
gian trễ là giao thức tối ưu đối với mọi tham 
số về hiệu năng. Việc lựa chọn một giao thức 
định tuyến đa đường giảm thời gian trễ còn 
phải phụ thuộc vào các tham số cụ thể của mô 
hình mạng cụ thể. Ngoài ra, các giao thức 
định tuyến này vẫn cần phải cải tiến về cơ 
chế tìm đường, cơ chế lựa chọn đường và 
cơ chế cân bằng tải để có thể đạt được hiệu 
năng tốt hơn. 
TÀI LIỆU THAM KHẢO 
[1]. Anurag K, Manjunath D, Kuri J. 
Communication networking: an analytical 
approach, Los Altos, CA: Morgan Kaufmann 
Publishers; 2004. P.715-720 
[2]. Bertsekas D, Gallager R. Data networks, 2nd 
ed. Englewood Cliffs, NJ: Prentice-Hall; 1992 
p.162-170 
[3]. Broch J, Johnson DB, Maltz DA. The 
dynamic source routing for mobile ad hoc 
networks. IETF Internet-draft, draft-ietf-manet-
dsr-00.txt; 1998. 
[4]. Cha M, Lee DK. Split-n-save multiplexing in 
wireless ad hoc routing. In: Proceedings of the 
24th annual joint conference of the IEEE computer 
and communications societies (INFOCOM), 
Miami, March 2005. 
[5]. Huang X, Fang Y. End-to-end delay 
differentiation by prioritized multipath routing in 
wireless sensor networks. In: Military 
communications conference, MILCOM 2005, vol. 
2, p. 1277-1283. 
[6]. Jing F, Bhuvaneswaran RS, Katayama Y, 
Takahashi N. A multipath on-demand routing with 
path selection probabilities for mobile ad hoc 
networks. In: Proceedings of the international 
Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 
 57
conference on wireless communications, 
networking and mobile computing, 2005, vol. 2, p. 
1145-1151. 
[7]. Liang Y, Midkiff SF. Multipath Fresnel zone 
routing for wireless ad hoc networks. In: 
Proceedings of the IEEE wireless communications 
and networking conference, vol. 4, March 2005, 
p. 1958–1963. 
[8]. Lim H, Xu K, Gerla M. TCP performance 
over multipath routing in mobile ad hoc networks. 
In: IEEE international conference on 
communication (ICC), vol. 2, 2003, p. 1064–1070. 
[9]. Perkins CE. Ad hoc on-demand distance 
vector (AODV) routing. IETF Internet-draft, draft-
ietf-manet-aodv-00.txt; 1997. 
[10]. Pham PP, Perrau S. Performance analysis of 
reactive shortest path and multipath routing 
mechanism with load balance. In: Proceedings of 
the IEEE INFOCOM, San Francisco, California, 
USA, April 2003, p. 251-259. 
[11]. Popa L, Raiciu C, Stoica I, Rosenblum DS. 
Reducing congestion effects in wireless networks 
by multipath routing. In: Proceeding of the 14th 
IEEE international conference on network 
protocols, Santa Barbara, California, USA, 
November 2006, p. 96-104. 
[12]. Tarique M, Kelnal E. Tepe, Sasan Adibi, 
Shervin Erfani. Survey of multipath routing 
protocols for mobile ad hoc networks. In: Journal 
of Network and Computer Applications 32, 2009, 
p. 1125-1143. 
[13]. Tsirigos A, Haas ZJ, Tabrizi SS. Multipath 
routing in mobile ad hoc networks or how to route 
in the presence of frequent topology changes In: 
Proceedings of themilitary communications 
conference, vol. 2, Vienna, Virginia, October 
2001, p. 878–883. 
[14]. Wang L, Jang S, Lee T-Y. Redundant source 
routing for real-time services in ad hoc networks. 
In: Proceedings of IEEE international conference 
on mobile ad hoc and sensor systems conference, 
Washington, DC, November, 2005. 
[15]. Ye Z, Krishnamurthy SV, Tripathi SK. A 
framework for reliable routing in mobile ad hoc 
networks. In: Proceedings of the 22nd annual joint 
conference of the IEEE computer and 
communications societies (INFOCOM), vol. 1, 
2003, p. 270-280. 
SUMMARY 
EVALUATING DELAY-AWARE MULTIPATH ROUTING PROTOCOLS 
IN MANET 
Do Dinh Cuong*, Nguyen Anh Chuyen 
College of Information Technology and Communication - TNU 
Recently, multipath routing has become a new approach for routing in MANET. In this paper, we 
introduces a fundamental overview about operation mechanism of several new delay-aware 
multipath routing protocols. Later, we do more action in analyzing, comparing, and evaluating 
these protocols based on target and performance. Furthermore, this paper also points out future 
works that these protocols need to do. 
Keywords: Mobile Adhoc Network, Multipath Routing, Delay, Route Finding, Route Selecting 
Ngày nhận bài:30/1/2013, ngày phản biện: 19/2/2013, ngày duyệt đăng:26/3/2013 
*
 Tel: 0982 990908, Email: ddcuong@ictu.edu.vn