Một phương pháp xác định chi phí mới nhằm cải thiện chất lượng dịch vụ định tuyến

98 Lương Thái Ngọc, Lê Vũ 
MỘT PHƯƠNG PHÁP XÁC ĐỊNH CHI PHÍ MỚI NHẰM CẢI THIỆN 
CHẤT LƯỢNG DỊCH VỤ ĐỊNH TUYẾN 
A NEW METHOD TO DEFINE THE ROUTING COST FOR IMPROVING QoS 
Lương Thái Ngọc1, Lê Vũ2 
1Trường Đại học Đồng Tháp; ltngoc@dthu.edu.vn 
2Trường Đại học Sư phạm Kỹ thuật - Đại học Đà Nẵng; levuvn@gmail.com 
Tóm tắt - Chi phí định tuyến dựa trên số chặng có ưu điểm là nút 
nguồn khám phá tuyến ngắn nhất đến đích. Tuy nhiên, hạn chế của 
phương pháp này là nút nguồn không thể phát hiện nghẽn mạng 
trong tuyến vừa khám phá, dẫn đến mất gói làm giảm chất lượng 
dịch vụ (QoS) định tuyến. Bài báo trình bày phương pháp xác định 
chi phí mới, thay vì sử dụng số chặng (HC), nhóm tác giả dựa vào 
khả năng tải (LA) của bộ định tuyến là tiêu chí để thiết lập chi phí. 
Phương pháp này cho phép nút nguồn khám phá ra tuyến có khả 
năng tải tốt nhất đến đích nhằm giảm thiểu mất gói do nghẽn mạng, 
ngoài ra nút nguồn có thể phát hiện ra tuyến vừa khám phá bị quá 
tải hoặc không để có phương án định tuyến phù hợp. Sử dụng NS2, 
nhóm tác giả đánh giá hiệu quả của hai phương pháp xác định chi 
phí trong mô hình mạng tải cao sử dụng giao thức AODV. Kết quả 
cho thấy, chi phí định tuyến sử dụng khả năng tải có tỷ lệ gói tin gửi 
thành công đến đích lớn hơn khi sử dụng số chặng. 
Abstract - The routing cost determining method based on hop count 
(HC) has the advantage that it is the source node of the shortest 
route. However, this method has one drawback that it is impossible 
for the root node to detect network congestion in the discovered 
route, which leads to the deterioration of quality of routing service. 
This article proposes a new routing cost determining method in which 
load ability (LA) of the routers is used as metric instead of hop count. 
This method allows source node to discover the route with best 
loading capacity to minimize the number of lost packages due to 
network congestion. Furthermore, root node can also determine 
whether the discovered route is overloaded or not to choose the 
appropriate routing method. Using NS2, we analyze the effectivity of 
the two routing cost determining methods in highly loaded network 
topology using AODV protocol. The results show that LA-based 
method has higher packet delivery ratio than HC-based method. 
Từ khóa - AODV; MANET; HC; LA; QoS Key words - AODV; MANET; HC; LA; QoS 
1. Giới thiệu 
Ngày nay, với sự phát triển bùng nổ của các ứng dụng 
đa phương tiện truyền thông trên mạng Internet trong khi 
hạ tầng mạng vẫn chưa đáp ứng được đã tạo ra tình trạng 
nghẽn mạng làm giảm chất lượng dịch vụ định tuyến. Thời 
gian qua, các nhà khoa học đã không ngừng nghiên cứu 
giải pháp phát hiện, hạn chế nghẽn mạng để quá trình 
truyền thông được thông suốt. Hướng tiếp cận đầu tiên là 
cải tiến giao thức truyền thông tại tầng vận chuyển là TCP, 
một số giao thức cải tiến đã được đề xuất như: TCP 
NewReno [1], Vegas [2], Vegas-W [3]. Hướng tiếp cận 
khác là cải tiến cơ chế quản lý hàng đợi theo hướng tích 
cực tại các nút mạng có thể xuất hiện nghẽn [4], một số cải 
tiến tiêu biểu như: RED [5], ARED [6], FRED [7], REM 
[8], BLUE [9]. Tuy nhiên, cả hai hướng nghiên cứu này 
còn tồn tại hạn chế. Ở hướng tiếp cận đầu tiên có hạn chế 
là tập trung vào việc giải quyết tắc nghẽn mạng khi nó đã 
hoặc sắp xảy ra dựa trên giao thức TCP, trong khi các luồng 
dữ liệu đa phương tiện được truyền thông dựa vào giao thức 
UDP không được quan tâm đến. Ngoài ra, hướng tiếp cận 
thứ hai có hạn chế là dựa trên xác suất hủy gói sớm ngẫu 
nhiên dẫn đến mất gói không cần thiết, và chỉ hiệu quả 
trong mô hình mạng cố định, nơi mà các “nút thắt cổ chai” 
được xác định trước, chúng không hiệu quả trong các mô 
hình mạng di động với công nghệ mới như MANET. 
Nhóm tác giả nhận thấy rằng, ngoài những nguyên nhân 
dẫn đến tình trạng nghẽn mạng như: lưu lượng mạng, băng 
thông và khả năng xử lý của nút. Một nguyên nhân quan 
trọng khác là do các giao thức định tuyến sử dụng cách tính 
chi phí dựa vào số chặng. Thuật toán tìm đường theo số 
chặng chưa phải là thuật toán tốt nhất. Tuyến ngắn nhất có 
xu hướng đi qua tâm của mạng gây tắc nghẽn cục bộ ở các 
nút phân bố gần tâm. Vì vậy, cần cải tiến cơ chế tìm đường 
của các giao thức này nhằm giảm tắc nghẽn bởi các lưu 
lượng bị tập trung tại vùng trung tâm [10, tr. 2]. 
Bài báo này sử dụng một hướng tiếp cận khác để xác 
định chi phí định tuyến, cho phép nút nguồn phát hiện 
nghẽn mạng ngay tại quá trình khám phá tuyến, chi tiết 
được trình bày trong phần tiếp theo. Phần 3 trình bày quá 
trình cài đặt giao thức cải tiến từ AODV sử dụng chi phí 
định tuyến mới. Phần 4 trình bày tham số xây dựng kịch 
bản mô phỏng và đánh giá kết quả mô phỏng trên NS2 và 
cuối cùng là kết luận. 
2. Phương pháp xác định chi phí định tuyến dựa vào 
khả năng tải 
Phần này, trình bày hạn chế của chi phí định tuyến dựa 
trên số chặng và phương pháp xác định chi phí định tuyến 
mới dựa vào khả năng tải của bộ định tuyến. 
2.1. Hạn chế của chi phí dựa vào số chặng 
Hình 1. Mô tả kết quả khám phá tuyến sử dụng số chặng 
Chi phí định tuyến dựa trên số chặng là số lượng nút mạng 
từ nguồn đến đích. Một tuyến được xác định là tốt nhất nếu 
tuyến có số lượng nút đến đích là nhỏ nhất [11]. Hình 1 là ví 
dụ mô tả quá trình khám phá tuyến của giao thức sử dụng số 
chặng (tiêu biểu là AODV [12], DSR [13], DSDV [14]) để 
Nút Láng giềng Tuyến Nút cổ chai 
1 5 
2 
3 
11 
9 10 
4 
6 7 
8 
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 3(124).2018 99 
tính chi phí định tuyến dẫn đến “nút thắt cổ chai”. Giả sử nút 
nguồn N1 khám phá tuyến đến nút đích là N5, tương tự nút 
nguồn N8 cũng khám phá hai tuyến đến đích là N4 và N5. Kết 
quả khám phá tuyến với chi phí dựa vào HC sẽ cho ra ba tuyến 
có chi phí nhỏ nhất là 3, bao gồm: {N1→N6→N7→N5}, 
{N8→N6→N7→N5}, và {N8→N6→N7→N4}. Cả ba tuyến giao 
nhau ở nút cổ chai N6 dẫn đến cho lưu lượng tải tăng cao và 
rớt gói tin tại N6. Khuyết điểm này có thể khắc phục bằng cách 
chuyển hướng tuyến đường của nút nguồn qua các bộ định 
tuyến đang rỗi. Đây chính là vấn đề mà nhóm tác giả phải giải 
quyết trong bài báo này. 
2.2. Chi phí định tuyến dựa vào khả năng tải 
Thay vì sử dụng tham số HC để xác định chi phí, nhóm 
tác giả sử dụng khả năng tải của bộ định tuyến là tiêu chí để 
thiết lập chi phí đến đích. Điều này cho phép nút nguồn phát 
hiện ra tuyến vừa khám phá có bị quá tải hoặc không để có 
phương án định tuyến phù hợp nhằm hạn chế nghẽn mạng. 
a) Định nghĩa 1: Giả sử tất cả bộ định tuyến có kích 
thước hàng đợi (Qmax) là như nhau, khả năng tải (LARi) của 
bộ định tuyến tuyến Ri được xác định như công thức 1. 
( )max max/RiRi usedLA Q Q Q= − (1) 
Trong đó, i
R
usedQ là kích thước hàng đợi đã được sử 
dụng tại bộ định tuyến Ri. 
b) Định nghĩa 2: Giả sử ta có một tuyến gồm các bộ 
định tuyến R1→R2→→Rn-1→Rn. Chi phí định tuyến 
(RC) dựa trên khả năng tải từ nút nguồn NS đến đích ND là 
đại lượng đo khả năng tải tối đa tại tất cả các nút trung gian 
trên tuyến từ R1 đến Rn như công thức 2. 
( )min ; 2.. 1RiRC LA i n=  = − (2) 
Ví dụ 1: Cho giá trị kích thước hàng đợi đã sử dụng của 
tất cả các nút như Hình 2, chi phí định tuyến của tuyến 
{R1→R6→ R7→ R5} là RC = Min (0,67; 0,87) = 0,67. 
Hình 2. Mô tả chi phí định tuyến dựa vào LA 
Hình 3. Mô tả chi phí định tuyến của tuyến không có 
bộ định tuyến trung gian 
Ví dụ 2: Trong trường hợp tuyến gồm hai bộ định tuyến 
là láng giềng với nhau (không có bộ định tuyến trung gian) 
như Hình 3, chi phí định tuyến của tuyến {R7→ R5} là 
RC = 1 vì không có bộ định tuyến trung gian chịu tải giữa 
nút nguồn và đích. 
Ví dụ 3: Giả sử tại thời điểm nút nguồn N1 khám phá tuyến 
đến đích N5 thì khả năng tải của các bộ định tuyến như Hình 
4. Nút nguồn N1 có thể đi đến đích qua các tuyến như sau: 
- Path1: N1→N2→N3→N4→N5; RCPath1=0,33; 
- Path2: N1→N6→N7→N5; RCPath2=0,15; 
- Path3: N1→N8→N9→N10→N11→N5; RCPath3=0,6. 
Hình 4. Mô tả tính chi phí định tuyến dựa vào khả năng tải 
trong mô hình mạng tổng quát 
Như vậy, tuyến được chọn là tuyến {N1→N8→N9→ 
N10→N11→N5} vì Path3 có khả năng tải tốt nhất, tương ứng 
với chi phí tốt nhất là RC=0,6. Trong trường hợp có nhiều 
tuyến đến đích thì tuyến được chọn là tuyến có khả năng tải 
lớn nhất, tương ứng có chi phí RC lớn nhất. Trong trường 
hợp tồn tại hai tuyến đến đích có chi phí tốt nhất bằng nhau 
thì tuyến có số chặng thấp hơn sẽ ưu tiên được chọn. 
Ví dụ 4: Xét lại mô hình mạng như Hình 4, trong 
trường hợp hệ thống bắt đầu vận hành thì tất cả các bộ định 
tuyến đều rỗi (LA=0), dẫn đến tất cả tuyến đường từ N1 đến 
đích N5 đều có chi phí bằng nhau (RC=1). Kết quả là tuyến 
Path2 được chọn vì có số lượng nút đến đích thấp nhất, lúc 
này kết quả khám phá tuyến trùng với cách thức tính chi 
phí dựa trên số chặng. 
3. LA-AODV - Giao thức định tuyến cải tiến sử dụng 
chi phí định tuyến dựa trên khả năng tải 
Phần này trình bày cơ chế khám phá tuyến của giao thức 
AODV sử dụng chi phí dựa trên HC và chi tiết quá trình 
khám phá tuyến của giao thức LA-AODV sử dụng chi phí 
định tuyến mới. 
3.1. Giao thức định tuyến AODV 
AODV thuộc nhóm giao thức định tuyến theo yêu cầu, 
khám phá tuyến thông qua gói yêu cầu tuyến (RREQ) và 
gói trả lời tuyến (RREP). Cấu trúc gói tin điều khiển tuyến 
gồm RREQ và RREP của giao thức AODV sử dụng chi phí 
định tuyến dựa vào HC như Hình 5. 
Khi nút nguồn NS muốn gửi thông tin đến nút đích ND mà 
không có tuyến đến đích trong bảng định tuyến của nó, NS tiến 
hành khám phá tuyến bằng cách phát quảng bá gói RREQ đến 
các nút láng giềng của nó. Nút trung gian Ni lưu tuyến ngược 
RC 
0 
Qmax= 150 
30 
 R1 R6 R7 R5 
50 
10 
LA 
Qused 
20 
RC 
0 
Qmax= 150 
 R7 R5 
10 
LA 
Qused 
20 
1 5 
2 
3 
11 
9 10 
6 
8 
7 
4 
LA=0,36 
 LA=0,15 LA=0,05 
LA=0,33 
LA=0,34 
LA=0,85 LA=0,6 
LA=0,75 LA=0,75 
LA=0,15 LA=0,25 
LA: Khả năng tải Láng giềng Nút 
100 Lương Thái Ngọc, Lê Vũ 
về nguồn và tiếp tục quảng bá gói RREQ đến tất cả láng giềng. 
Quá trình lưu tuyến ngược về nguồn và quảng bá gói RREQ 
tiếp tục cho đến khi nút đích ND nhận được gói yêu cầu tuyến 
hoặc nút đích không tồn tại. Để tránh xử lý trùng lặp, mỗi gói 
RREQ chỉ được nút trung gian xử lý một lần. 
Type J R C Reserved HC 
Broadcast ID 
Destination IP Address 
Destination Sequence Number 
Source IP Address 
Source Sequence Number 
a) RREQ packet 
Type R A Reserved Prefix Sz HC 
Destination IP Address 
Destination Sequence Number 
Source IP Address 
Lifetime 
b) RREP packet 
Hình 5. Gói tin điều khiển tuyến của giao thức AODV 
sử dụng chi phí định tuyến dựa vào HC [12] 
Khi nhận được gói RREQ, nút đích ND trả lời tuyến 
thông qua gói RREP chứa thông tin tuyến về nguồn. Các 
nút trung gian chuyển tiếp gói RREP về nguồn thông qua 
tuyến ngược đã lưu khi nhận gói RREQ trước đó, đồng thời 
lưu tuyến đến đích ND vào bảng định tuyến của nó trước 
khi chuyển tiếp gói RREP về nguồn. Ngoài ra, tại các nút 
trung gian cũng thực hiện quá trình trả lời tuyến RREP nếu 
tồn tại tuyến đủ “tươi” đến đích. 
Hình 6. Khám phá tuyến của giao thức AODV 
Xem mô hình mạng tại Hình 6, nút nguồn N1 khám phá 
tuyến đến nút đích N5 bằng cách phát quảng bá gói RREQ 
đến các láng giềng {N2, N6, N7}, gói RREQ được khởi tạo 
giá trị là [N1, N5, 0]. Khi nhận được gói yêu cầu tuyến, nút 
N2 kiểm tra và thấy rằng nó không là nút đích nên tăng HC 
lên 1 và tiếp tục quảng bá gói RREQ đến tất cả láng giềng 
của nó gồm {N3, N6}, đồng thời lưu tuyến ngược về nguồn 
N1, quá trình tiếp tục tại nút N6, N7 và các nút trung gian 
khác cho đến khi nút N5 nhận được RREQ. 
Khi nhận được gói RREQ từ nút N7, nút đích N5 trả lời 
gói RREP về nguồn thông qua nút trung gian N7, gói RREP 
được khởi tạo giá trị là [N5, N1, 0]. N7 kiểm tra và thấy rằng 
nó không phải đích đến của gói RREP (không phải nút 
nguồn) nên tăng HC lên 1 và tiếp tục chuyển tiếp về nguồn 
thông qua nút trung gian N6. Kết quả là N1 nhận được gói 
RREP thông qua nút trung gian N6 với HC bằng 3. Bảng 1 
mô tả thông tin tuyến đến đích và nguồn tại tất cả các nút 
sau quá trình khám phá tuyến. Kết quả là nút nguồn N1 
khám phá ra tuyến ngắn nhất đến đích N5 theo tuyến 
{N1→N6→N7 →N5} với chi phí HC là 3. 
Bảng 1. Kết quả khám phá tuyến của AODV với 
chi phí định tuyến dựa trên HC; S: Nguồn, D: Đích, 
N: Nút, NH: Nút kế, HC: Chi phí định tuyến 
Bước Nút 
RREQ/ RREP 
[S, D, HC] 
Bảng định tuyến (RT) 
N NH HC 
Q
u
ản
g
 b
á 
R
R
E
Q
N1 Khởi tạo gói RREQ [N1, N5, 0] 
N2 [N1, N5, 1] N1 N1 1 
N3 [N1, N5, 2] N1 N2 2 
N4 [N1, N5, 3] N1 N3 3 
N5 [N1, N5, 3] N1 N7 3 
N6 [N1, N5, 1] N1 N1 1 
N7 [N1, N5, 2] N1 N6 2 
N8 [N1, N5, 1] N1 N1 1 
N9 [N1, N5, 2] N1 N8 2 
N10 [N1, N5, 3] N1 N9 3 
N11 [N1, N5, 3] N1 N7 3 
G
ử
i 
g
ó
i 
R
R
E
P
 N5 Khởi tạo gói RREP [N5, N1, 0] 
N7 [N5, N1, 1] N5 N5 1 
N6 [N5, N1, 2] N5 N7 2 
N1 [N5, N1, 3] N5 N6 3 * 
(*) Tuyến vừa khám phá 
Tương tự, kết quả khám phá tuyến của nút nguồn N8 
đến hai nút đích N4 và N5 cũng thông qua NH là N6 với chi 
phí là 3. Ta thấy rằng trong 3 tuyến vừa khám phá giao 
nhau ở “nút thắt cổ chai” là N6. 
3.2. Giao thức cải tiến LA-AODV 
Hình 7. Thuật toán yêu cầu tuyến 
Để cài đặt giao thức LA-AODV, nhóm tác giả thực hiện 
như sau: Đầu tiên, nhóm tác giả thay thế trường HC thành 
tên mới là RC trong hai gói tin điều khiển tuyến RREQ và 
RREP để lưu chi phí định tuyến dựa trên khả năng tải; Tiếp 
theo, thay thế thuộc tính HC thành thuộc tính RC của thông 
tin định tuyến (Entry) trong bảng định tuyến (Routing Table) 
RREQ RREP Tuyến Gói bị hủy 
5 
2 
3 
11 
9 10 
6 
8 
7 
4 
1 
(Đã nhận RREQ rồi) 
và (không phải nút đích)? 
y 
n 
n 
n 
y 
Thiết lập tuyến về nguồn; 
LA = khả năng tải của nút; 
RREQ.RC = min(RREQ.RC, LA); 
Quảng bá gói RREQ; 
y 
Nút nhận gói RREQ 
Hủy gói RREQ 
Kết thúc 
Bắt đầu 
(Nút là đích)? 
(Có đường đi) 
và (Đủ mới)? 
Thêm vào cache 
Tạo gói RREQ; RREQ.RC = 1; 
Quảng bá gói RREQ; 
Tạo gói RREP; 
RREP.RC = 1; 
Gửi RREP về nguồn; 
Tạo gói RREP; 
RREP.RC = entry.RC; 
Gửi RREP về nguồn; 
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 3(124).2018 101 
để phù hợp với chi phí định tuyến dựa trên khả năng tải; Cuối 
cùng, cải tiến thuật toán khám phá tuyến của giao thức 
AODV thành LA-AODV, cho phép nút nguồn khám phá 
tuyến dựa vào khả năng tải. Hình 7 và 8 trình bày lưu đồ 
thuật toán của giao thức cải tiến LA-AODV. 
Hình 8. Thuật toán trả lời tuyến 
Ví dụ minh họa: Giả sử tại thời điểm khám phá tuyến 
thì khả năng tải của các bộ định tuyến như Hình 9. Nút 
nguồn N1 khám phá tuyến đến nút đích N5 với chi phí dựa 
vào khả năng tải. Gói yêu cầu tuyến được quảng bá đến 
đích N5 theo ba hướng gồm {N1→N2→N3→ N4→N5}, 
{N1→N6→N7→N5}, và {N1→N8→N9→N10→N11→ N5}. 
Nút trung gian chỉ xử lý gói RREQ đầu tiên nhận được và 
lưu thông tin tuyến ngược về nguồn vào bảng định tuyến. 
Hình 9. Khám phá tuyến của giao thức AODV sử dụng gói 
RREQ và RREP, chi phí dựa trên RC 
Khi nhận gói tin yêu cầu tuyến, nút đích N5 trả lời ba 
gói RREP về nguồn trên ba tuyến theo các hướng gồm 
{N5→N4→N3→N2→N1}, {N5→N7→N6→N1}, và 
{N5→ N11→N10→N9→N8→ N1}. Do vậy, nút nguồn nhận 
được ba gói RREP lần lượt đến từ các nút N6, N2 và N8. Gói 
RREP đầu tiên nhận được từ N2 được sử dụng để thêm 
tuyến mới đến đích N5 thông qua NH là N6 với chi phí 
RC = min(0,15; 0,25) = 0,15. Gói RREP thứ hai đến từ N2 
có chi phí RC = min(0,36; 0,33; 0,34) = 0,33. Vì vậy, N1 
cập nhật lại tuyến đến đích thông qua NH là N2 vì có chi 
phí tốt hơn tuyến hiện tại (tuyến đã lưu khi nhận gói RREP 
đầu tiên). Cuối cùng, N1 nhận được gói RREP thứ ba đến 
từ N8 có chi phí RC = min(0,75; 0,85; 0,6; 0,75) = 0,6. Đây 
là tuyến tốt nhất nên N1 tiếp tục cập nhật lại thông tin tuyến 
đến đích thông qua NH là N8 với chi phí là 0,6. 
Bảng 2 cho thấy thông tin gói RREQ, RREP và chi tiết 
thông tin tuyến được thiết lập tại mỗi nút. Ngoài ra, kết quả 
khám phá tuyến được ghi nhận cho thấy rằng nút nguồn N1 
và nút đích N5 đã phát hiện ra tuyến {N5→N7→N6→N1} có 
khả năng bị nghẽn mạng, do khả năng tải lớn nhất của tuyến 
chỉ đạt 0,15, tương ứng với hàng đợi của nút cổ chai chỉ 
còn trống 15%. 
Bảng 2. Kết quả khám phá tuyến của AODV với 
chi phí định tuyến dựa trên RC; S: Nguồn, D: Đích, 
N: Nút, NH: Nút kế, RC: Chi phí định tuyến 
Bước Nút 
RREQ/ RREP 
[S, D, RC] 
Bảng định tuyến (RT) 
N NH RC 
Q
u
ản
g
 b
á 
R
R
E
Q
N1 Khởi tạo gói RREQ [N1, N5, 1] 
N2 [N1, N5, 0,36] N1 N1 1 
N3 [N1, N5, 0,33] N1 N2 0,36 
N4 [N1, N5, 0,33] N1 N3 0,33 
N5 [N1, N5, 0,33] N1 N7 0,33 
N6 [N1, N5, 0,15] N1 N1 1 
N7 [N1, N5, 0,15] N1 N6 0,15 * 
N5 [N1, N5, 0,05] N1 N7 0,15 * 
N8 [N1, N5, 0,75] N1 N1 1 
N9 [N1, N5, 0,75] N1 N8 0,75 
N10 [N1, N5, 0,6] N1 N9 0,75 
N11 [N1, N5, 0,6] N1 N7 0,6 
N5 [N1, N5, 0,05] N1 N11 0,6 
T
rả
 l
ờ
i 
g
ó
i 
R
R
E
P
N5 Khởi tạo gói RREP [N5, N1, 1] thứ nhất 
N7 [N5, N1, 0,25] N5 N5 1 
N6 [N5, N1, 0,15] N5 N7 0,25 
N1 [N5, N1, 0,15] N5 N6 0,15 * 
N5 Khởi tạo gói RREP [N5, N1, 1] thứ hai 
N4 [N5, N1, 0.34] N5 N5 1 
N3 [N5, N1, 0.33] N5 N4 0,34 
N2 [N5, N1, 0.33] N5 N3 0,33 
N1 [N5, N1, 0.15] N5 N2 0,33 
N5 Khởi tạo gói RREP [N5, N1, 1] thứ ba 
N11 [N5, N1, 0,75] N5 N5 1 
N10 [N5, N1, 0,6] N5 N11 0,75 
N9 [N5, N1, 0,6] N5 N10 0,6 
N8 [N5, N1, 0,6] N5 N9 0,6 
N1 [N5, N1, 0,15] N5 N8 0,6 
3.3. So sánh AODV và LA-AODV 
Đặc điểm của giao thức cải tiến được nhóm tác giả đánh 
giá so với giao thức gốc dựa trên một số tiêu chí như Bảng 
3. Giao thức LA-AODV khám phá ra tuyến có khả năng 
thông qua lớn để hạn chế nghẽn. Trong quá trình khám phá 
tuyến, LA-AODV có khả năng phát hiện nghẽn mạng nên 
hoạt động hiệu quả trong môi trường mạng tải cao. 
(Nút là nguồn)? 
y 
n 
n 
y 
Thiết lập tuyến đến đích; 
LA = khả năng tải của nút; 
RREP.RC = min(RREP.RC, LA); 
Chuyển tiếp gói RREP; 
Nút nhận gói RREP 
Chấp nhận gói RREP 
Kết thúc 
Bắt đầu 
(Tìm thấy)? 
Tìm entry về nguồn 
Tạo gói RREP; RREP.RC = 1; 
Trả lời gói RREP về nguồn; 
Hủy gói RREP 
LA=0,36 
 LA=0,15 LA=0,05 
LA=0,33 
LA=0,34 
LA=0,85 LA=0,6 
LA=0,75 LA=0,75 
 LA=0,15 LA=0,25 
RREQ RREP Tuyến được chọn Hủy gói 
5 
2 
3 
11 
9 10 
6 
8 
7 
4 
1 
102 Lương Thái Ngọc, Lê Vũ 
Bảng 3. So sánh hai giao thức AODV và LA-AODV 
Tiêu chí AODV LA-AODV 
Chi phí định tuyến dựa vào HC LA 
Tuyến tốt nhất là tuyến chi phí Nhỏ Lớn 
Khả năng xuất hiện nút cổ chai Cao Thấp 
Phát hiện nghẽn mạng Không Có 
Nút đích xử lý gói RREQ Đầu tiên Tất cả 
Hiệu quả khi lưu lượng tải cao Không Tốt 
4. Mô phỏng đánh giá kết quả 
Nhóm tác giả sử dụng hệ mô phỏng NS2 phiên bản 2.35 
để đánh giá hiệu quả của chi phí định tuyến dựa vào LA so 
với chi phí định tuyến dựa vào HC. Mô hình mạng có 11 
nút hoạt động trong phạm vi 2.000m x 2.000m, các nút 
mạng bố trí cố định như Hình 9, giao diện mô phỏng trên 
NS2 như Hình 10. 
Hình 10. Giao diện mô phỏng trên NS2 
Bảng 4 mô tả chi tiết thông số mô phỏng, nhóm tác giả 
sử dụng ba luồng dữ liệu CBR như mô tả tại Hình 7, luồng 
đầu tiên từ nút nguồn N0 đến đích N4 bắt đầu phát từ giây 
thứ 0, luồng thứ hai từ nút nguồn N7 đến đích N3 bắt đầu 
phát từ giây thứ 10, luồng cuối cùng từ nút nguồn N7 đến 
đích N4 bắt đầu phát từ giây thứ 20. Tốc độ phát lần lượt là 
10 gói/giây hoặc 20 gói/giây. 
Bảng 4. Thông số mô phỏng 
Thông số Giá trị 
Khu vực địa lý 2.000 m x 2000 m 
Vùng thu phát sóng 250 m 
Thời gian mô phỏng 1.000 s 
Tổng số nút mạng 11 
Dạng truyền thông CBR (Constant Bit Rate) 
Số kết nối 3 UDP 
Tốc độ phát 10 gói/giây; 20 gói/giây 
Kích thước gói tin 512(bytes) 
Hàng đợi FIFO (DropTail) 
Giao thức định tuyến AODV và LA-AODV 
Kết quả mô phỏng tại Hình 11 cho thấy rằng tỷ lệ gửi gói 
thành công (PDR) của LA-AODV tương đương với giao 
thức gốc. Tuy nhiên, trong môi trường tải cao 20 gói/s thì tỷ 
lệ gửi gói thành công của LA-AODV hiệu quả hơn giao thức 
gốc. Kết thúc 500s mô phỏng thì PDR của LA-AODV đạt 
92,59%, cao hơn 16,7% so với AODV (đạt 75,87%). 
Hình 11. Tỷ lệ gửi gói thành công 
a) Tải cao 
 b) Tải thấp 
Hình 12. Thời gian trễ trung bình 
Thời gian trễ trung bình tại Hình 12 cho thấy rằng giao 
thức AODV trong môi trường tải thấp thì thời gian trễ trung 
bình (ETE) của LA-AODV thấp hơn AODV. Tuy nhiên, 
trong môi trường tải cao thì ETE của LA-AODV cao hơn 
AODV do tuyến đường khám phá dài hơn (dựa trên hop) 
AODV. Kết thúc 500s mô phỏng thì ETE của LAAODV là 
2,64s và AODV là 2,15s trong môi trường tải cao; tương 
ứng là 0,046s và 0,049s trong môi trường tải thấp. 
5. Kết luận 
Như vậy, nhóm tác giả đã đề xuất một cơ chế xác định 
chi phí định tuyến mới cho giao thức AODV trên mạng 
MANET. Việc thiết lập chi phí định tuyến dựa trên khả 
năng tải cho phép khám phá ra tuyến đường với khả năng 
tải cao, hạn chế tắc nghẽn. Kết quả mô phỏng trên NS2 đã 
cho thấy hiệu quả của giải pháp đề xuất. Tương lai, nhóm 
tác giả sẽ tiếp tục nghiên cứu, cải tiến và mô phỏng trong 
nhiều môi trường mạng khác nhau để đánh giá hiệu quả. 
Cảm ơn: Bài báo được sự hỗ trợ tài chính của Quỹ Phát 
triển Khoa học và Công nghệ, Đại học Đà Nẵng, mã số 
B2016-DNA-46-TT. 
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 3(124).2018 103 
Phụ lục 
Giao thức LA-AODV được cải tiến từ AODV nên 
nhóm tác giả sử dụng mã lệnh của giao thức AODV có sẵn 
trên NS2 (\ns-allinone-2.35\ns-2.35\aodv) để cài đặt. Sau 
đây là một số hiệu chỉnh cơ bản để cài đặt: 
Đầu tiên, thay đổi cấu trúc của gói RREQ tập tin 
laaodv_packet.h bằng cách loại bỏ thuộc tính 
rq_hop_count và bổ sung vào thuộc tính rq_la. 
Ngoài ra, thông tin định tuyến của giao thức mới chứa 
RC nên cấu trúc của gói RREP bị loại bỏ thuộc tính 
rp_hop_count và bổ sung vào thuộc tính rp_la. 
Tiếp theo, thay đổi cấu trúc của bảng định tuyến để lưu 
trữ chi phí định tuyến LA. Mở tập tin laaodv_rtable.h, loại 
bỏ thuộc tính rt_hops, thay bằng thuộc tính rt_la. 
Tiếp theo, khi gửi gói RREQ thuộc tính rq_la của gói 
RREQ được thiết lập là 1, thực hiện tương tự cho thuộc tính 
rp_la gói RREP. 
Tiếp theo, khi nhận gói RREQ nút chỉ loại bỏ gói tin đã 
xử lý rồi nếu nút hiện tại không phải đích. 
Cuối cùng, trước khi chuyển tiếp gói RREQ, nút cập 
nhật lại chi phí định tuyến trong gói RREQ. 
TÀI LIỆU THAM KHẢO 
[1] N. Parvez, A. Mahanti, and C. Williamson, “An analytic throughput 
model for TCP NewReno”, IEEE/ACM Transactions on 
Networking, Vol. 18, No. 2, 2010, pp. 448-461. 
[2] M. Podlesny and C. Williamson, Providing fairness between TCP 
NewReno and TCP Vegas with RD network services, in IEEE 
International Workshop on Quality of Service, IWQoS, 2010. 
[3] L. Ding, X. Wang, Y. Xu, W. Zhang, and W. Chen, Vegas-W: An 
enhanced TCP-Vegas for wireless ad hoc networks, in IEEE 
International Conference on Communications, 2008, pp. 2383-2387. 
[4] R. Adams, “Active Queue Management: A Survey”, IEEE 
Communications Surveys & Tutorials, Vol. 15, No. 3, 2013, pp. 
1425-1476. 
[5] S. Patel, Performance analysis of RED for stabilized queue, in 2014 
7th International Conference on Contemporary Computing, IC3 
2014, 2014, pp. 306-311. 
[6] J. Chen, C. Hu, and Z. Ji, “An improved ARED algorithm for 
congestion control of network transmission”, Mathematical 
Problems in Engineering, Vol. 2010, 2010. 
[7] N. Glombitza, M. Lipphardt, H. Hellbruck, and S. Fischer, FRED - 
An Application for a Real-Life Large Scale Multihop Ad Hoc 
Network, in 2008 Fifth Annual Conference on Wireless on Demand 
Network Systems and Services, 2008, pp. 73-76. 
[8] S. Athuraliya, S. H. Low, and V. H. Li, “REM: Active queue 
management”, IEEE Network, Vol. 15, No. 3, 2001, pp. 48-53. 
[9] W. Feng, D. D. Kandlur, D. Saha, and K. G. Shin, BLUE: A new class 
of active queue management algorithms, Ann Arbor, 1999, pp. 1-27. 
[10] Đ. Đ. Cường, N. V. Tam, and N. G. Hiểu, Nghiên cải tiến hiệu năng 
giao thức định tuyến AODV và AOMDV trong mạng MANET, Luận 
án tiến sĩ, Học viện Khoa học và Công nghệ, 2017. 
[11] E. Alotaibi and B. Mukherjee, “A survey on routing algorithms for 
Wireless Ad-hoc and Mesh networks”, Computer Networks, Vol. 56, 
No. 2, 2012, pp. 940-965. 
[12] C. E. Perkins, M. Park, and E. M. Royer, Ad-hoc On-Demand 
Distance Vector Routing, in Proceedings of Second IEEE Workshop 
on Mobile Computing Systems and Applications (WMCSA), 1999, 
pp. 90-100. 
[13] D. B. Johnson and D. A. Maltz, Dynamic Source Routing in Ad Hoc 
Wireless Networks, Mobile Computing, The Kluwer International 
Series in Engineering and Computer Science, Vol. 353, Springer, 
1996, pp. 153-181. 
[14] C. E. Perkins and P. Bhagwat, Highly Dynamic Destination 
Sequence Distance Vector (DSDV) for Moblie Computers, in 
Proceedings of the SIGCOMM 1994 Conference on 
Communications Architectures, Protocols and Applications, 1994, 
pp. 234-244.
(BBT nhận bài: 09/01/2018, hoàn tất thủ tục phản biện: 13/3/2018)