Khảo sát thuật toán định tuyến nguồn trong mạng tùy biến di động sử dụng mô hình giải tích

Tóm tắt – Để có cơ sở cho việc đánh giá hiệu quả thực thi của các giao thức định

tuyến trong mạng tùy biến di động, việc nghiên cứu các mô hình phân tích nguyên lý hoạt

động của các thuật toán định tuyến là điều cần thiết. Trong bài báo này, tác giả đề xuất

một mô hình giải tích toán học sử dụng lý thuyết ma trận để khảo sát giao thức định tuyến

nguồn trong mạng tùy biến di động. Mô hình được đề xuất cho phép xác định tập lộ trình

truyền dữ liệu khi biết tôpô mạng.

pdf 6 trang yennguyen 3860
Bạn đang xem tài liệu "Khảo sát thuật toán định tuyến nguồn trong mạng tùy biến di động sử dụng mô hình giải tích", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Khảo sát thuật toán định tuyến nguồn trong mạng tùy biến di động sử dụng mô hình giải tích

Khảo sát thuật toán định tuyến nguồn trong mạng tùy biến di động sử dụng mô hình giải tích
12 TẠP CHÍ KHOA HỌC
QUẢN LÝ VÀ CÔNG NGHỆ
KHẢO SÁT THUẬT TOÁN ĐỊNH 
TUYẾN NGUỒN TRONG MẠNG TÙY 
BIẾN DI ĐỘNG SỬ DỤNG MÔ HÌNH 
GIẢI TÍCH
1. Lê Hữu Bình
Khoa Công nghệ thông tin - Truyền thông, Trường Cao đẳng Công nghiệp Huế
70 Nguyễn Huệ, Phường Vĩnh Ninh, Thành phố Huế
Email: lhbinh@hueic.edu.vn;
2. Lê Đức Huy
Trường Đại học Công nghệ và Quản lý Hữu Nghị
Email: leduchuy2307@gmail.com;
Tóm tắt – Để có cơ sở cho việc đánh giá hiệu quả thực thi của các giao thức định 
tuyến trong mạng tùy biến di động, việc nghiên cứu các mô hình phân tích nguyên lý hoạt 
động của các thuật toán định tuyến là điều cần thiết. Trong bài báo này, tác giả đề xuất 
một mô hình giải tích toán học sử dụng lý thuyết ma trận để khảo sát giao thức định tuyến 
nguồn trong mạng tùy biến di động. Mô hình được đề xuất cho phép xác định tập lộ trình 
truyền dữ liệu khi biết tôpô mạng.
Từ khóa: Mạng tùy biến, Định tuyến nguồn, mô hình giải tích.
I. GIỚI THIỆU
Ngày nay, các ứng dụng trên các thiết bị 
di động ngày một gia tăng. Để đáp ứng nhu 
cầu này, việc nghiên cứu nâng cao hiệu năng 
mạng tùy biến di động là điều hết sức cần 
thiết. Điều này cũng đã được nhiều nhóm 
nghiên cứu trong nước cũng như trên thế giới 
quan tâm thực hiện trong thời gian gần đây. 
Các hướng nghiên cứu đã được triển khai 
phổ biến như cải tiến các giao thức định tuyến 
trong mạng tùy biến di động [1], [2], nâng cao 
chất lượng truyền dẫn trên các lộ trình truyền 
dữ liệu [3], cải tiến mô hình mạng sử dụng các 
công nghệ mới [6].
Để đánh giá hiệu quả thực thi của các 
giao thức điều khiển được đề xuất, chúng ta 
có thể sử dụng mô hình mô phỏng, mô hình 
giải tích toán học hoặc thực nghiệm trên các 
mô hình mạng thực. Trong các phương pháp 
đó, phương pháp mô phỏng đang được sử 
dụng phổ biến hiện nay. Với phương pháp 
này, chúng ta có thể sử dụng các phần mềm 
13TẠP CHÍ KHOA HỌC
QUẢN LÝ VÀ CÔNG NGHỆ
mô phỏng đang được sử dụng phổ biến hiện 
nay như OMNeT++ [7], NS-2 [8], OPNET và 
một số phần mềm mô phỏng mạng khác. 
Phương pháp mô phỏng đã được các nhóm 
tác giả trong [1], [3] sử dụng để đánh giá hiệu 
quả thực thi của các giao thức được đề xuất. 
Ưu điểm của phương pháp này là chỉ thực 
thi trên máy tính và hệ thống phần mềm, nên 
việc triển khai tương đối thuận lợi. Tuy nhiên, 
phương pháp này cũng có nhược điểm là kết 
quả mô phỏng thường có sai số so với thực 
tế. Ngoài phương pháp mô phỏng, phương 
pháp sử dụng mô hình giải tích toán học cũng 
đã được nhiều nhóm nghiên cứu triển khai. 
Phương pháp này thường được thực hiện 
bằng cách sử dụng lý thuyết hàng đợi, lý 
thuyết xác suất thống kê, mô hình phát sinh 
lưu lượng trong mạng viễn thông để mô hình 
hóa một hệ thống mạng. Trong [4], mô hình 
mạng hàng đợi đã được sử dụng để phân tích 
mạng không dây tùy biến. Nhóm tác giả trong 
[5] đã sử dụng nguyên lý hàng đợi M/M/1/K để 
phân tích hiệu năng của giao thức định tuyến 
AODV trong mạng tùy biến di động. 
Trong bài báo này, chúng tôi trình bày một 
mô hình giải tích được đề xuất cho việc tìm 
tập lộ trình của giao thức định tuyến nguồn 
động (Dynamic Source Routing - DSR) trong 
mạng tùy biến di động. Dựa trên nguyên lý 
khám phá lộ trình của giao thức DSR, chúng 
tôi sử dụng các ma trận nhị phân để biểu diễn 
quá trình phát quảng bá gói RREQ. Từ giá trị 
thu được của ma trận nhị phân, chúng ta xác 
định được lộ trình truyền dữ liệu được khám 
phá bởi giao thức DSR. Các phần tiếp theo 
của bài báo được bố cục như sau: Phần II 
trình bày nguyên lý cơ bản của giao thức định 
tuyến DSR. Phần III là mô hình giải tích được 
đề xuất. Phần IV là kết luận và hướng phát 
triển tiếp theo.
II. NGUYÊN LÝ CƠ BẢN CỦA GIAO 
THỨC ĐỊNH TUYẾN NGUỒN
Định tuyến nguồn động (DSR) là một giao 
thức thuộc nhóm định tuyến theo yêu cầu 
(On-Demand Routing Protocol). Theo nguyên 
lý hoạt động của lớp giao thức định tuyến này, 
các lộ trình truyền dữ liệu sẽ được tạo ra khi 
có yêu cầu. Khi một nút yêu cầu một lộ trình 
mới để đến đích, nút đó phải khởi đầu một 
quá trình khám phá lộ trình (Route Discovery). 
Quá trình này sẽ kết thúc với một trong hai 
trường hợp. Một là tìm ra một lộ trình thỏa 
mãn các yêu cầu đề ra trước đó. Hai là quá 
thời gian cho phép nhưng không tìm được 
một lộ trình nào. 
Việc khám phá lộ trình mới bởi giao thức 
định tuyến DSR được khởi đầu bằng việc 
phát quảng bá gói yêu cầu lộ trình (RREQ) từ 
nút nguồn đến tất cả các nút láng giềng của 
nó. Tại các nút trung gian khi nhận được gói 
RREQ, nếu như trước đó gói RREQ này đã 
được nhận rồi thì nút đang xét hủy bỏ nó và 
không xử lý gì thêm. Ngược lại, lưu lộ trình 
ngược về nút nguồn vào bộ nhớ đệm của nút 
đang xét, sau đó kiểm tra xem trong bộ nhớ 
đệm của nó có đang tồn tại lộ trình khả thi đến 
nút đích hay không. Nếu có, nối lộ trình từ nút 
nguồn đến nút hiện tại với lộ trình từ nút hiện 
tại đến nút đích. Sau đó, tạo gói phản hồi lộ 
trình (RREP) để gửi thông tin về nút nguồn 
theo đường ngược. Trong trường hợp bộ nhớ 
đệm của nút trung gian đang xét không có lộ 
trình khả thi đến nút đích, nút đó tiếp tục phát 
quảng bá gói RREQ đến tất cả các nút láng 
giềng, ngoại trừ nút đã phát gói RREQ cho nó 
để tiếp tục quá trình khám phá lộ trình mới. 
Quá trình lặp lại cho đến khi tất cả các nút 
trong mạng đều nhận được gói RREQ, hoặc 
quá thời gian chờ cho phép. 
Trong trường hợp gói RREQ đến được 
nút đích, nghĩa là một lộ trình khả thi đã được 
tìm thấy, nút đích sẽ tạo gói phản hồi lộ trình 
(RREP) để gửi về nút nguồn theo đường 
ngược. Khi nút nguồn nhận được gói RREP, 
nó sẽ cập nhật thông tin lộ trình mới vào bộ 
nhớ đệm của nó. Lộ trình này được sử dụng 
cho việc truyền dữ liệu theo yêu cầu.
14 TẠP CHÍ KHOA HỌC
QUẢN LÝ VÀ CÔNG NGHỆ
trình này được sử dụng cho việc truyền 
dữ liệu theo yêu cầu. 
Hình 1. Sơ đồ khối chức năng của mô 
hình 
Để thấy rõ nguyên lý khám phá lộ trình 
mới theo giao thức DSR, tác giả xét một 
ví dụ như ở Hình 1Hình 1. Giả sử ở thời 
điểm hiện tại, bảng định tuyến của tất cả 
các nút đều rỗng. Xét trường hợp nút 6 
muốn khám phá một lộ trình mới đến nút 
9. Quá trình khám phá lộ trình được thức 
hiện theo các bước sau: 
 Bước 1: Nút nguồn (nút 6) tạo gói 
RREQ, phát quảng bá gói RREQ đến 
tất cả các nút láng giềng của nó là 3, 8 
và 8. 
 Bước 2: Xử lý gói RREQ tại các nút 
nhận được gói này ở bước 1 (các nút 3, 
5 và 8): Tại nút 3, do chưa nhận được 
gói RREQ này trước đó, đồng thời do 
trong bảng định tuyến hiện tại của nút 
3 không có lộ trình khả thi đến đích 
(nút 9), nên nút 3 sẽ lưu trữ lộ trình 
ngược về nút nguồn (nút 6) vào bảng 
định tuyến của nó. Sau đó, tiếp tục 
phát quảng bá gói RREQ đến tất cả 
các nút láng giềng của nó, ngoại trừ 
nút 6 là nút đã gửi RREQ cho nút 3. 
Như vậy, nút 3 sẽ quảng bá gói RREQ 
đến các nút 1 và 7. Quá trình xảy ra 
hoàn toàn tương tự đối với nút 5 và nút 
8. 
 Bước 3: Xử lý gói RREQ tại các nút 
nhận được gói này ở bước 2 (các nút 1, 
2 và 7): Tại nút 1, khi nhận được gói 
RREQ từ nút 3, do chưa nhận được 
gói RREQ này trước đó, đồng thời do 
trong bảng định tuyến hiện tại của nút 
1 không có lộ trình khả thi đến đích 
Hình 1. Sơ đồ khối chứ năng của mô hình
Để thấy rõ nguyên lý khám phá lộ trình 
mới theo giao thức DSR, tác giả xét một ví 
dụ như ở Hình 1. Giả sử ở thời điểm hiện tại, 
bảng định tuyến của tất cả các nút đều rỗng. 
Xét trường hợp nút 6 muốn khám phá một lộ 
trình mới đến nút 9. Quá trình khám phá lộ 
trình được thức hiện theo các bước sau:
• Bước 1: Nút nguồn (nút 6) tạo gói 
RREQ, phát quảng bá gói RREQ đến tất cả 
các nút láng giềng của nó là 3, 8 và 8. 
• Bước 2: Xử lý gói RREQ tại các nút 
nhận được gói này ở bước 1 (các nút 3, 5 và 
8): Tại nút 3, do chưa nhận được gói RREQ 
này trước đó, đồng thời do trong bảng định 
tuyến hiện tại của nút 3 không có lộ trình khả 
thi đến đích (nút 9), nên nút 3 sẽ lưu trữ lộ 
trình ngược về nút nguồn (nút 6) vào bảng 
định tuyến của nó. Sau đó, tiếp tục phát quảng 
bá gói RREQ đến tất cả các nút láng giềng 
của nó, ngoại trừ nút 6 là nút đã gửi RREQ 
cho nút 3. Như vậy, nút 3 sẽ quảng bá gói 
RREQ đến các nút 1 và 7. Quá trình xảy ra 
hoàn toàn tương tự đối với nút 5 và nút 8. 
• Bước 3: Xử lý gói RREQ tại các nút 
nhận được gói này ở bước 2 (các nút 1, 2 và 
7): Tại nút 1, khi nhận được gói RREQ từ nút 
3, do chưa nhận được gói RREQ này trước 
đó, đồng thời do rong bảng đị tuyến hiện 
tại của nút 1 không có lộ trình khả thi đến đích 
(nút 9), nên nút 1 sẽ lưu trữ lộ trình ngược về 
nút nguồn (nút 6: 1 → 3 →6) vào bảng định 
tuyến của nó. Sau đó, tiếp tục phát quảng bá 
gói RREQ đến tất cả các nút láng giềng của 
nó, ngoại trừ nút 3 là nút đã gửi RREQ này 
cho nút 1. Như vậy, nút 1 sẽ quảng bá gói 
RREQ đến các nút 4 và 7. Sau đó, nút 1 cũng 
nhận được gói RREQ này từ nút 5 gửi đến (từ 
bước 2). Lúc này, do nút 1 đã nhận được gói 
RREQ này trước đó (từ nút 3 gửi đến), nên 
nút 1 sẽ xóa gói RREQ này. uá trình xảy ra 
hoàn toàn tương tự đối với nút 2 và nút 7.
• Bước 4: Xử lý gói RREQ tại các nút 
nhận được gói này ở bước 3 (nút 4 và nút 9): 
Quá trình xử lý gói RREQ nhận được tại nút 4 
hoàn toàn tương tự như đã mô tả ở các bước 
trên. Tại nút 9, vì đây là nút đích, ên khi nhận 
được gói RREQ, nút 9 sẽ tạo gói RREP và gửi 
phản hồi về nút nguồn theo đường ngược. 
Như vậy, thuật toán DSR đã tìm được lộ 
trình từ nút 6 đến nút 9 là 6 → 3 → 7 → 9. Lộ 
trình này đi qua ba bước truyền (hop). Trong 
trường hợp tìm thấy nhiều lộ trình, thuật toán 
DSR sẽ lựa chọn lộ trình có số bước truyền 
nhỏ nhất để sử dụng cho việc truyền dữ liệu.
III. MÔ HÌNH GIẢI TÍCH XÁC ĐỊNH LỘ 
TRÌNH CỦA THUẬT TOÁN DSR
Trong phần này, chúng tôi trình bày một 
mô hình giải tích được đề xuất cho việc tìm 
tập lộ trình của giao thức định tuyến DSR 
trong mạng tùy biến di động. Để phát biểu 
thuật toán DSR thành mô hình giải tích, chúng 
tôi định nghĩa các ký hiệu toán học như sau:
Gọi n là tổng số nút mạng, 
(nút 9), nên nút 1 sẽ lưu trữ lộ trình 
ngược về nút nguồn (nút 6: 1 3 
6) vào bảng định tuyến của nó. Sau đó, 
tiếp tục phát quảng bá gói RREQ đến 
tất cả các nút láng giềng của nó, ngoại 
trừ nút 3 là nút đã gửi RREQ này cho 
út 1. Như vậy, nút 1 sẽ quảng bá gói 
RREQ đến các nút 4 và 7. Sau đó, nút 
1 cũng nhận được gói RREQ này từ 
nút 5 gửi đến (từ bước 2). Lúc này, do 
nút 1 đã nhận được gói RREQ này 
trước đó (từ nút 3 gửi đến), nên nút 1 
sẽ xóa gói RREQ này. Quá trình xảy 
ra hoàn toàn tương tự đối với nút 2 và 
nút 7. 
 Bước 4: Xử lý gói RREQ tại các nút 
nhận được gói này ở bước 3 (nút 4 và 
nút 9): Quá trình xử lý gói RREQ nhận 
được tại nút 4 hoàn toàn tương tự như 
đã mô tả ở các bước trên. Tại nút 9, vì 
đây là nút đích, nên khi nhận được gói 
RREQ, nút 9 sẽ tạo gói RREP và gửi 
phản hồi về nút nguồn theo đường 
ngược. 
Như vậy, thuật toán DSR đã tìm được 
lộ trình từ nút 6 đến nút 9 là 6 3 7 
 9. Lộ trình này i qua ba bước truyền 
(hop). Trong trường hợp tìm thấy nhiều lộ 
trình, thuật toán DSR sẽ lựa chọn lộ trình 
có số bước truyền nhỏ nhất để sử dụng 
cho việc truyền dữ liệu. 
III. MÔ HÌNH GIẢI TÍCH XÁC 
ĐỊNH LỘ TRÌNH CỦA THUẬT 
TOÁN DSR 
Trong phần này, chúng tôi trình bày 
một mô hình giải tích được đề xuất ho 
việc tìm tập lộ trình của giao thức định 
tuyến DSR trong mạng tùy biến di động. 
Để phát biểu thuật toán DSR thành mô 
hình giải tích, chúng tôi địn nghĩa các ký 
hiệu toán học như sau: 
Gọi n là tổng số nút ạng, nnijaA ][ là 
ma trận biểu diễn các nút láng giềng của 
nhau trong mạng, trong đó các phần tử aij 
được xác định như sau: 
1 neáu nuùt laø laùng gieàng cuûa nuùt
0 trong tröôøng hôïp ngöôïc laïiij
j i
a (1) 
 là ma 
trận biểu diễn các nút láng giềng của nhau 
15TẠP CHÍ KHOA HỌC
QUẢN LÝ VÀ CÔNG NGHỆ
trong mạng, trong đó các phần tử 
(nút 9), nên nút 1 sẽ lưu trữ lộ trình 
ngược về nút nguồn (nút 6: 1 3 
6) vào bảng định tuyến của nó. Sau đó, 
tiếp tục phát quảng bá gói RREQ đến 
tất cả các nút láng giềng của nó, ngoại 
trừ nút 3 là nút đã gửi RREQ này cho 
nút 1. Như vậy, nút 1 sẽ quảng bá gói 
RREQ đến các nút 4 và 7. Sau đó, nút 
1 cũng nhận được gói RREQ này từ 
nút 5 gửi đến (từ bước 2). Lúc này, do 
nút 1 đã nhận được gói RREQ này 
trước đó (từ nút 3 gửi đến), nên nút 1 
sẽ xóa gói RREQ này. Quá trình xảy 
ra hoàn toàn tương tự đối với nút 2 và 
nút 7. 
 Bước 4: Xử lý gói RREQ tại các nút 
nhận được gói này ở bước 3 (nút 4 và 
nút 9): Quá trình xử lý gói RREQ nhận 
được tại nút 4 hoàn toàn tương tự như 
đã mô tả ở các bước trên. Tại nút 9, vì 
đây là nút đích, nên khi nhận được gói 
RREQ, nút 9 sẽ tạo gói RREP và gửi 
phản hồi về nút nguồn theo đường 
ngược. 
Như vậy, thuật toán DSR đã tìm được 
lộ trình từ nút 6 đến nút 9 là 6 3 7 
 9. Lộ trình này đi qua ba bước truyền 
(hop). Trong trường hợp tìm thấy nhiều lộ 
trình, thuật toán DSR sẽ lựa chọn lộ trình 
có số bước truyền nhỏ nhất để sử dụng 
cho việc truyền dữ liệu. 
III. MÔ HÌNH GIẢI TÍCH XÁC 
ĐỊNH LỘ TRÌNH CỦA THUẬT 
TOÁN DSR 
Trong phần này, chúng tôi trình bày 
một mô hình giải tích được đề xuất cho 
việc tìm tập lộ trình của giao thức định 
tuyến DSR trong mạng tùy biến di động. 
Để phát biểu thuật toán DSR thành mô 
hình giải tích, chúng tôi định nghĩa các ký 
hiệu toán học như sau: 
Gọi n là tổng số nút mạng, nnijaA ][ là 
ma trận biểu diễn các nút láng giềng của 
nhau r ng ạng, trong đó các phần tử aij 
được xác định như sau: 
1 neáu nuùt laø laùng gieàng cuûa nuùt
0 trong tröôøng hôïp ngöôïc laïiij
j i
a (1) 
 được 
xác định như sau:
Ví dụ, xét trường hợp tôpô mạng ở Hình 
1, ma trận biểu diễn các nút láng giềng của 
nhau trong tôpô này được xác định như sau:
Để xác định thứ tự xử lý gói RREQ, chúng 
tôi định nghĩa ma trận 
Ví dụ, xét trường hợp tôpô mạng ở 
Hình 1Hình 1, ma trận biểu diễn các nút 
láng giềng của nhau trong tôpô này được 
xác định như sau: 
 
001001000
000100010
100000101
010010100
000100011
100000011
001100001
010011000
001011100
99ij
aA (2) 
Để xác định thứ tự xử lý gói RREQ, 
chúng ịnh nghĩa a trậ M = [mi]1 (n-
1), trong đó các phần tử mi được xác định 
như sau: mi = u nghĩa là nút u xử lý gói 
RREQ ở lần thứ i đối với yêu cầu khám 
phá lộ trình từ nút s đến nút d. Ví dụ, xét 
trường hợp tôpô mạng ở Hình 1Hình 1 
với yêu cầu khám phá lộ trình từ nút 6 
đến nút 9. Khi đó, ma trận M được xác 
định như sau: 
M = [6 3 5 8 1 7 2 4 9] (3) 
Để biểu diễn quá trình xử lý gói RREQ 
trong mạng, chúng tôi định nghĩa ma trận 
 ( ) ( )[ ]k kij n nX x với các phần tử ( )kijx được xác 
định bởi: 
- Khi k = 0: X(k) = [0]. 
- Khi k > 0: các phần tử ( )kijx được xác 
định như sau: 
  

( 1)
( ) ( 1)
1
neáu
neáu
0 neáu
k
ij k
n
k k
ij ij ij zj k
z
x i m
x a a x i m
j s
 (4) 
trong đó, aij là các phần tử của ma trận 
biễu diễn các nút láng giềng của nhau (ma 
trận A). Phép toán  trong công thức 
(4(4) là phép toán cộng modulo trong hệ 
nhị phân. Biểu thức này cho phép xác 
định điều kiện ràng buộc trong mỗi cột j 
của ma trận X(k) luôn luôn chỉ có một phần 
tử có giá trị bằng 1, có nghĩa là mỗi nút j 
tr ... neáu 6
0 neáu 6
0 neáu 6
ij ij ij
z
i
x a a i
j
 (6) 
vì theo (3(3) m1 = 6 và X(0) = [0]. Từ (6(6) 
và (2(2) ta có: 
 (1)6 6[ ] [ ] [0 0 1 0 1 0 0 1 0]j jx a (7) 
Từ (6(6) và (7(7) ta có: 
(1)
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (8) 
 Ở lần xử lý gói R EQ thứ 2, nút 3 
phát quảng bá gói R EQ đến tất cả các 
nút láng giềng của nó, điều này được biểu 
diễn bởi ma trận
 (2) (2)
9 9
[ ]ijX x với các phần 
tử (2)ijx được xác định theo (4(4) như sau: 
  

(1)
9
(2) (1)
1
neáu 3
neáu 3
0 neáu 6
ij
ij ij ij zj
z
x i
x a a x i
j
 (9) 
vì theo (3(3) m2 = 3. Từ (9(9) ta xác định 
được các phần tử của ma trận X(2) như 
sau: 
- Khi j = 6, )2(ijx = 0. 
- Khi i ≠ m2 i ≠ 3, )2(ijx = )1(ijx . 
- Khi i = m2 i = 3: 
   

9
(2) (1)
31 31 31 1
1
1(1 0) 1z
z
x a a x (10) 
   

9
(2) (1)
32 32 32 2
1
0(0 0) 0z
z
x a a x (11) 
 (2)
33
0x (12) 
   

9
(2) (1)
34 34 34 4
1
0(0 0) 0z
z
x a a x (13) 
   

9
(2) (1)
35 35 35 5
1
0(0 1) 0z
z
x a a x (14) 
 Lần xử lý gói RREQ đầu tiên: Nút 6 
phát quảng bá gói RREQ đến tất cả các 
nút láng giềng của nó, điều này được biểu 
diễn bởi ma trận
 (1) (1) 9 9[ ]ijX x với các phần 
tử ( )kijx được xác định theo (4(4) như sau: 
  

(0)
1
9
(1) (0)
1
1
neáu
neáu
0 neáu
ij
ij ij ij zj
z
x i m
x a a x i m
j s
 (5) 
  

9
(1)
1
0 neáu 6
0 neáu 6
0 neáu 6
ij ij ij
z
i
x a a i
j
 (6) 
vì theo (3(3) m1 = 6 và X(0) = [0]. Từ (6(6) 
và (2(2) ta có: 
 (1)6 6[ ] [ ] [0 0 1 0 1 0 0 1 0]j jx a (7) 
Từ (6(6) và (7(7) ta có: 
(1)
0
0
0
0 0 0 0
0
0 1 1 1
0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (8) 
 Ở lần xử lý gói RREQ thứ 2, nút 3 
phát quảng bá gói RREQ đến tất cả các 
nút láng giềng của nó, điều này được biểu 
diễn bởi ma trận
 (2) (2)
9 9
[ ]ijX x với các phần 
tử (2)ijx được xác định theo (4(4) như sau: 
  

(1)
9
(2) (1)
1
neáu 3
neáu 3
0 neáu 6
ij
ij ij ij zj
z
x i
x a a x i
j
 (9) 
vì theo (3(3) m2 = 3. Từ (9(9) ta xác định 
được các phần tử của ma trận X(2) như 
sau: 
- Khi j = 6, )2(ijx = 0. 
- Khi i ≠ m2 i ≠ 3, )2(ijx = )1(ijx . 
- Khi i = m2 i = 3: 
   

9
(2) (1)
31 31 31 1
1
1(1 0) 1z
z
x a a x (10) 
   

9
(2) (1)
32 32 32 2
1
0(0 0) 0z
z
x a a x (11) 
 (2)
33
0x (12) 
   

9
(2) (1)
34 34 34 4
1
0(0 0) 0z
z
x a a x (13) 
   

9
(2) (1)
35 35 35 5
1
0(0 1) 0z
z
x a a x (14) 
 (2)
36
0x (15) 
   

9
(2) (1)
37 37 37 7
1
1(1 0) 1z
z
x a a x (16) 
   

9
(2) (1)
38 38 38 8
1
0(0 1) 0z
z
x a a x (17) 
   

9
(2) (1)
39 39 39 9
1
0(0 0) 0z
z
x a a x (18) 
Từ đó ta có: 
(2)
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (19) 
Hoàn toàn tương tự, ta xác định được ma 
trận biểu diễn quá trình xử lý gói RREQ 
của tất cả các nút (sau 8 lần chuyển tiếp 
gói RREQ) như sau: 
(8)
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (20) 
Kết quả của ma trận X(k) ở (20(20) cho 
thấy rằng, nút 9 nhận được gói RREQ từ 
nút 7 (x79 = 1), gói RREQ này nút 7 nhận 
được từ nút 3 (x37 = 1), nút 3 nhận gói 
RREQ này từ nút 6 (x63 = 1). Như vậy, lộ 
trình từ 6 đến 9 được xác định là 6 3 
 7 9. Kết quả này trùng hợp vơi kết 
quả khám phá lộ trình theo nguyên lý của 
thuật toán định tuyến DSR, đã được trình 
bày ở ví dụ Hình 1 của phần II. Như vậy, 
mô hình giải tích sử dụng phương pháp 
ma trận nhị phân như mô tả ở trên có thể 
sử dụng cho việc xác định lộ trình theo 
nguyên lý của giao thức định tuyến DSR. 
IV. KẾT LUẬN 
Trong bài báo này, tác giả đề xuất một 
mô hình giải tích toán học sử dụng lý 
 (2)
36
0x (15) 
   

9
(2) (1)
37 37 37 7
1
1(1 0) 1z
z
x a a x (16) 
   

9
(2) (1)
38 38 38 8
1
0(0 1) 0z
z
x a a x (17) 
   

9
(2) (1)
39 39 39 9
1
0(0 0) 0z
z
x a a x (18) 
Từ đó ta có: 
(2)
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (19) 
Hoàn toàn tương tự, ta xác định được ma 
trận biểu diễn quá trình xử lý gói RREQ 
của tất cả các nút (sau 8 lần chuyển tiếp 
gói RREQ) như sau: 
(8)
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (20) 
Kết quả của ma trận X(k) ở (20(20) cho 
thấy rằng, nút 9 nhận được gói RREQ từ 
nút 7 (x79 = 1), gói RREQ này nút 7 nhận 
được từ nút 3 (x37 = 1), nút 3 nhận gói 
RREQ này từ nút 6 (x63 = 1). Như vậy, lộ 
trình từ 6 đến 9 được xác định là 6 3 
 7 9. Kết quả này trùng hợp vơi kết 
quả khám phá lộ trình theo nguyên lý của 
thuật toán định tuyến DSR, đã được trình 
bày ở ví dụ Hình 1 của phần II. Như vậy, 
mô hình giải tích sử dụng phương pháp 
ma trận nhị phân như mô tả ở trên có thể 
sử dụng cho việc xác định lộ trình theo 
nguyên lý của giao thức định tuyến DSR. 
IV. KẾT LUẬN 
Trong bài báo này, tác giả đề xuất một 
mô hình giải tích toán học sử dụng lý 
17TẠP CHÍ KHOA HỌC
QUẢN LÝ VÀ CÔNG NGHỆ
Hoàn toàn tương tự, ta xác định được 
ma trận biểu diễn quá trình xử lý gói RREQ 
của tất cả các nút (sau 8 lần chuyển tiếp gói 
RREQ) như sau:
Kết quả của ma trận 
 (2)
36
0x (15) 
   

9
(2) (1)
37 37 37 7
1
1(1 0) 1z
z
x a a x (16) 
   

9
(2) (1)
38 38 38 8
1
0(0 1) 0z
z
x a a x (17) 
   

9
(2) (1)
39 39 39 9
1
0(0 0) 0z
z
x a a x (18) 
Từ đó ta có: 
(2)
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (19) 
Hoàn toàn tương tự, ta xác định được ma 
trận biểu diễn quá trình xử lý gói RREQ 
của tất cả các nút (sau 8 lần chuyển tiếp 
gói RREQ) như sau: 
(8)
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (20) 
Kết q X(k) ở (20(20) cho 
thấy rằng, nút 9 nhận được gói RREQ từ 
nút 7 (x79 = 1), gói RREQ này nút 7 nhận 
được từ nút 3 (x37 = 1), nút 3 nhận gói 
RREQ này từ nút 6 (x63 = 1). Như vậy, lộ 
trình từ 6 đến 9 được xác định là 6 3 
 7 9. Kết quả này trùng hợp vơi kết 
quả khám phá lộ trình theo nguyên lý của 
thuật toán định tuyến DSR, đã được trình 
bày ở ví dụ Hình 1 của phần II. Như vậy, 
mô hình giải tích sử dụng phương pháp 
ma trận nhị phân như mô tả ở trên có thể 
sử dụng cho việc xác định lộ trình theo 
nguyên lý của giao thức định tuyến DSR. 
IV. KẾT LUẬN 
Trong bài báo này, tác giả đề xuất một 
mô hình giải tích toán học sử dụng lý 
 ) cho t ấy 
rằng, nút 9 nhận được gói RREQ từ nút 7 
 (2)
36
0x (15) 
   

9
(2) (1)
37 37 37 7
1
1(1 0) 1z
z
x a a x (16) 
   

9
(2) (1)
38 38 38 8
1
0(0 1) 0z
z
x a a x (17) 
   

9
(2) (1)
39 39 39 9
1
0(0 0) 0z
z
x a a x (18) 
Từ đó ta có: 
(2)
0 0 0 0 0 0 0 0 0
0 0
1 0 1
0 0 0 0
0 0
0 0 1 1 1
0 0 0 0
0 0
0 0
X (19) 
Hoàn toàn tương tự, ta xác định được ma 
trận biểu diễn quá trình xử lý gói RREQ 
của tất cả các nút (sau 8 lần chuyển tiếp 
gói RREQ) như sau: 
(8)
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1
0 1 0 0 0
0 0 0 0 0
X (20) 
Kết quả của ma trận X(k) ở (20(20) cho 
thấy rằng, nút 9 nhận được gói RREQ từ 
nút 7 (x79 = 1), gói RREQ này nút 7 nhận 
được từ nút 3 (x37 = 1), nút 3 nhận gói 
RREQ này từ nút 6 (x63 = 1). Như vậy, lộ 
trình từ 6 đến 9 được xác định là 6 3 
 7 9. Kết quả này trùng hợp vơi kết 
quả khám phá lộ trình theo nguyên lý của 
thuật toán định tuyến DSR, đã được trình 
bày ở ví dụ Hình 1 của phần II. Như vậy, 
mô hình giải tích sử dụng phương pháp 
ma trận nhị phân như mô tả ở trên có thể 
sử dụng cho việc xác định lộ trình theo 
nguyên lý của giao thức định tuyến DSR. 
IV. KẾT LUẬN 
Trong bài báo này, tác giả đề xuất một 
mô hình giải tích toán học sử dụng lý 
, i REQ này nút 7 nhận được từ 
t 3 
 (2)
36
0x (15) 
   

9
(2) (1)
37 37 37 7
1
(1 0) 1z
z
x a a x (16) 
   

9
(2) (1)
38 38 38 8
1
0(0 1) 0z
z
x a a x (17) 
   

9
(2) (1)
39 39 39 9
1
0(0 0) 0z
z
x a a x (18) 
Từ đó ta có: 
(2)
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (19) 
Hoàn toàn tương tự, ta xác định được ma 
trận biểu diễn quá trình xử lý gói RREQ 
của tất cả các nút (sau 8 lần chuyển tiếp 
gói RREQ) như sau: 
(8)
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (20) 
Kết quả của ma trận X(k) ở (20(20) cho 
thấy rằng, nút 9 nhận được gói RREQ từ 
nút 7 (x79 = 1), gói RREQ ày út 7 nhận
được từ nút 3 (x3 nút 3 nhận gói 
RREQ này từ nút 6 (x63 = 1). Như vậy, lộ 
trình từ 6 đến 9 được xác định là 6 3 
 7 9. Kết quả này trùng hợp vơi kết 
quả khám phá lộ trình theo nguyên lý của 
thuật toán định tuyến DSR, đã được trình 
bày ở ví dụ Hình 1 của phần II. Như vậy, 
mô hình giải tích sử dụ g phương pháp 
ma trận nhị phân như mô tả ở trên có thể 
sử dụng cho việc xác định lộ trình theo 
nguyên lý của giao thức định tuyến DSR. 
IV. KẾT LUẬN 
Trong bài báo này, tác giả đề xuất một 
mô hình giải tích toán học sử dụng lý 
, út 3 nhận gói RREQ ày từ 
nút 6 
 (2)
36
0x (15) 
   

9
(2) (1)
37 37 37 7
1
1(1 0) 1z
z
x a a x (16) 
   

9
(2) (1)
38 38 38 8
1
0(0 1) 0z
z
x a a x (17) 
   

9
(2) (1)
39 39 39 9
1
0(0 0) 0z
z
x a a x (18) 
Từ đó ta có: 
(2)
0 0 0 0 0 0 0 0 0
0 0 0
1 0 0 1
0 0 0 0
0 0 0
0 0 1 1 1
0 0 0
0 0 0
0 0 0
X (19) 
Hoàn toàn tương tự, ta xác định được ma 
trận biểu diễn quá trình xử lý gói RREQ 
của tất cả các nút (sau 8 lần chuyển tiếp 
gói RREQ) như sau: 
(8)
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0
0 0 0 0 0 0 0
X (20) 
Kết quả của ma trận X(k) ở (2 (20) cho 
thấy rằng, nút 9 nhận được gói RREQ từ 
nút 7 (x79 = 1), gói RREQ này nút 7 nhận 
được từ nút 3 (x37 = 1), nút 3 nhận gói 
RREQ này từ (x63 = 1). Như vậy, lộ 
trình từ 6 đến 9 được xác định là 6 3 
 7 9. Kết quả này trùng hợp vơi kết 
quả khám phá lộ trình theo nguyên lý của 
thuật toán định tuyến DSR, đã được trình 
bày ở ví dụ Hình 1 của phần II. Như vậy, 
mô hình giải tích sử dụng phương pháp 
ma trận nhị phân như mô tả ở trên có thể 
sử dụng cho việc xác định lộ trình theo 
nguyên lý của giao thức định tuyến DSR. 
IV. KẾT LUẬN 
Trong bài báo này, tác giả đề xuất một 
mô hình giải tích toán học sử dụng lý 
, lộ trình từ 6 đến 9 
được xác định là → 3 → 7 → 9. Kết quả này 
trùng hợp vơi kết quả khám phá lộ trình theo 
nguyên lý của thuật toán định tuyến DSR, đã 
được trình bày ở ví dụ Hình 1 của phần II. 
Như vậy, mô hình giải tích sử dụng phương 
pháp ma trận nhị phân như mô tả ở trên có 
thể sử dụng cho việc xác định lộ trình theo 
nguyên lý của giao thức định tuyến DSR.
IV. KẾT LUẬN
Trong bài báo này, tác giả đề xuất một mô 
hình giải tích toán học sử dụng lý thuyết ma 
trận để khảo sát giao thức định tuyến nguồn 
tr ng mạ g tùy biến di động. Mô hình được 
đề xuất ho p ép xác định tập lộ trình truyền 
dữ liệu khi biết tôpô mạng, điều này cho phép 
đánh giá hiệu năng của mạng tùy biến di động 
khi sử dụng giao thức định tuyến DSR. Trong 
hướng nghiên cứu tiếp theo, tác giả tiếp tục 
phát triển mô hình để phân tích một số tham 
số hiệu năng khác như xác s t hủy bỏ gói 
dữ liệu, độ trễ, thông lượng mạng khi sử dụng 
giao thức định tuyến nguồn động.
 (2)
36
0x (15) 
   

9
(2) (1)
37 37 37 7
1
1(1 0) 1z
z
x a a x (16) 
   

9
(2) (1)
38 38 38 8
1
0(0 1) 0z
z
x a a x (17) 
   

9
(2) (1)
39 39 39 9
1
0(0 0) 0z
z
x a a x (18) 
Từ đó ta có: 
(2)
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
X (19) 
Hoàn toàn tương tự, ta xác định được ma 
trận biểu diễn quá trình xử lý gói RREQ 
của tất cả các nút (sau 8 lần chuyển tiếp 
gói RREQ) như sau: 
(8)
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0
0 0 0 0 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
X (20) 
Kết quả của ma trận X(k) ở (20(20) cho 
thấy rằng nút 9 nhận được gói RREQ từ 
nút 7 (x79 = 1), gói RREQ này nút 7 nhận 
được từ nút 3 37 = 1), nút 3 nhận gói 
RREQ này từ nút 6 (x63 = 1). Như vậy, lộ 
trình từ 6 đến 9 được xác định là 6 3 
 7 9. Kết quả này trùng hợp vơi kết 
quả khám phá lộ trình theo nguyên lý của 
thuật toán định tuyến DSR, đã được trình 
bày ở ví dụ Hình 1 của ần II. Như vậy, 
mô hình giải tích sử dụng phương pháp 
ma trận nhị phân như mô tả ở trên có thể 
sử dụng cho việc xác định lộ trình theo 
nguyên lý của giao thức định tuyến DSR. 
IV. KẾT LUẬN 
Trong bài bá này, tác giả đề xuất một 
mô hình giải tích toán học sử dụng lý 
TÀI LIỆU THAM KHẢO:
[1] C. T. Cuong, V. T. Tu, and N. T. Hai, 
“MAR-AODV: Innovative Routing Algorithm 
in MANET Based on Mobile Agent,” in 
International Conference on Advanced 
Information Networking and Applications 
Workshops, (Barcelona, Spain), 2013.
[2] H. Naanani, H. Mouncif, and M. 
Rachik, “Improved AODV Routing Protocol for 
MANETs,” International Journal of Engineering 
Research & Technology (IJERT), vol. 3, no. 7, 
pp. 1698–1701, 2014.
[3] Le Huu Binh, Vo Thanh Tu, “QTA-
AODV: An Improved Routing Algorithm to 
Guarantee Quality of Transmission for Mobile 
Ad Hoc Networks using Cross-Layer Model”, 
Journal of Communications, Vol 13, No. 7, 
2018, pp.338-349.
[4] A. Lee and I. Ra, “A Queuing Network 
Model Based on Ad Hoc Routing Networks 
for Multimedia Communications,” Applied 
Mathematics & Information Sciences, vol. 6, 
no. 1, pp. 271S-283S, 2012.
[5] S. B. Ch., K. G. Rao, B. B. Rao, and K. 
Chandan, “An AnalyticalModel for Evaluating 
Routing Performance of AODV Protocol 
for MANETs with Finite Buffer Capacity,” 
International Journal of Applied Engineering 
Research, vol. 10, no. 17, pp. 37960–37972, 
2015.
[6] S. Mora and J. Vera, "RDSNET: A 
proposal for control architecture for software 
defined MANETs," International Journal of 
Engineering and Technology (IJET), vol. 10, 
no. 3, pp.816-827, 2018.
[7] A. Varga, OMNeT++ Discrete Event 
Simulation System, Release 4.6. 2015. 
[Online]. Available: 
[8] DARPA, The Network Simulator NS2. 
[Online]. Available:  

File đính kèm:

  • pdfkhao_sat_thuat_toan_dinh_tuyen_nguon_trong_mang_tuy_bien_di.pdf