- Trang Chủ
- Quản trị mạng
- 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
Xem mẫ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
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ị dữ liệu [3], cải tiến mô hình mạng sử dụng các
di động ngày một gia tăng. Để đáp ứng nhu công nghệ mới [6].
cầu này, việc nghiên cứu nâng cao hiệu năng
Để đánh giá hiệu quả thực thi của các
mạng tùy biến di động là điều hết sức cần
giao thức điều khiển được đề xuất, chúng ta
thiết. Điều này cũng đã được nhiều nhóm
có thể sử dụng mô hình mô phỏng, mô hình
nghiên cứu trong nước cũng như trên thế giới
giải tích toán học hoặc thực nghiệm trên các
quan tâm thực hiện trong thời gian gần đây.
mô hình mạng thực. Trong các phương pháp
Các hướng nghiên cứu đã được triển khai
đó, phương pháp mô phỏng đang được sử
phổ biến như cải tiến các giao thức định tuyến
dụng phổ biến hiện nay. Với phương pháp
trong mạng tùy biến di động [1], [2], nâng cao này, chúng ta có thể sử dụng các phần mềm
chất lượng truyền dẫn trên các lộ trình truyền
12 TẠ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 thức thuộc nhóm định tuyến theo yêu cầu
nay như OMNeT++ [7], NS-2 [8], OPNET và (On-Demand Routing Protocol). Theo nguyên
một số phần mềm mô phỏng mạng khác. lý hoạt động của lớp giao thức định tuyến này,
Phương pháp mô phỏng đã được các nhóm các lộ trình truyền dữ liệu sẽ được tạo ra khi
tác giả trong [1], [3] sử dụng để đánh giá hiệu có yêu cầu. Khi một nút yêu cầu một lộ trình
quả thực thi của các giao thức được đề xuất. mới để đến đích, nút đó phải khởi đầu một
Ưu điểm của phương pháp này là chỉ thực quá trình khám phá lộ trình (Route Discovery).
thi trên máy tính và hệ thống phần mềm, nên Quá trình này sẽ kết thúc với một trong hai
việc triển khai tương đối thuận lợi. Tuy nhiên, trường hợp. Một là tìm ra một lộ trình thỏa
phương pháp này cũng có nhược điểm là kết mãn các yêu cầu đề ra trước đó. Hai là quá
quả mô phỏng thường có sai số so với thực thời gian cho phép nhưng không tìm được
tế. Ngoài phương pháp mô phỏng, phương một lộ trình nào.
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. Việc khám phá lộ trình mới bởi giao thức
Phương pháp này thường được thực hiện định tuyến DSR được khởi đầu bằng việc
bằng cách sử dụng lý thuyết hàng đợi, lý phát quảng bá gói yêu cầu lộ trình (RREQ) từ
thuyết xác suất thống kê, mô hình phát sinh nút nguồn đến tất cả các nút láng giềng của
lưu lượng trong mạng viễn thông để mô hình nó. Tại các nút trung gian khi nhận được gói
hóa một hệ thống mạng. Trong [4], mô hình RREQ, nếu như trước đó gói RREQ này đã
mạng hàng đợi đã được sử dụng để phân tích được nhận rồi thì nút đang xét hủy bỏ nó và
mạng không dây tùy biến. Nhóm tác giả trong không xử lý gì thêm. Ngược lại, lưu lộ trình
[5] đã sử dụng nguyên lý hàng đợi M/M/1/K để ngược về nút nguồn vào bộ nhớ đệm của nút
phân tích hiệu năng của giao thức định tuyến đang xét, sau đó kiểm tra xem trong bộ nhớ
AODV trong mạng tùy biến di động. đệ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
Trong bài báo này, chúng tôi trình bày một nguồn đến nút hiện tại với lộ trình từ nút hiện
mô hình giải tích được đề xuất cho việc tìm tại đến nút đích. Sau đó, tạo gói phản hồi lộ
tập lộ trình của giao thức định tuyến nguồn trình (RREP) để gửi thông tin về nút nguồn
động (Dynamic Source Routing - DSR) trong theo đường ngược. Trong trường hợp bộ nhớ
mạng tùy biến di động. Dựa trên nguyên lý đệm của nút trung gian đang xét không có lộ
khám phá lộ trình của giao thức DSR, chúng trình khả thi đến nút đích, nút đó tiếp tục phát
tôi sử dụng các ma trận nhị phân để biểu diễn quảng bá gói RREQ đến tất cả các nút láng
quá trình phát quảng bá gói RREQ. Từ giá trị giềng, ngoại trừ nút đã phát gói RREQ cho nó
thu được của ma trận nhị phân, chúng ta xác để tiếp tục quá trình khám phá lộ trình mới.
định được lộ trình truyền dữ liệu được khám Quá trình lặp lại cho đến khi tất cả các nút
phá bởi giao thức DSR. Các phần tiếp theo trong mạng đều nhận được gói RREQ, hoặc
của bài báo được bố cục như sau: Phần II quá thời gian chờ cho phép.
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 Trong trường hợp gói RREQ đến được
đề xuất. Phần IV là kết luận và hướng phát nút đích, nghĩa là một lộ trình khả thi đã được
triển tiếp theo. 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
II. NGUYÊN LÝ CƠ BẢN CỦA GIAO ngược. Khi nút nguồn nhận được gói RREP,
THỨC ĐỊNH TUYẾN NGUỒN 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
Định tuyến nguồn động (DSR) là một giao cho việc truyền dữ liệu theo yêu cầu.
TẠP CHÍ KHOA HỌC 13
QUẢN LÝ VÀ CÔNG NGHỆ
- trình này được sử dụng cho việc truyền tất cả các nút láng giềng của nó là 3, 8
dữ liệu theo yêu cầu. và 8.
• Bước 3: Xử lý gói RREQ tại các nút
Bước
nhận 2: gói
được Xử này
lý gói RREQ
ở bước tại nút
2 (các các1,nút
2 và
7):nhận
Tại nút
được1, khi
góinhận
này ởđược
bướcgói RREQ
1 (các núttừ3,nút
3, do chưa nhận được gói RREQ này trước
đó,5 đồng
và 8):thời
Tạidonúttrong
3, dobảngchưađịnhnhận được
tuyến hiện
tại của nút 1 không có lộ trình khả thi đến đích
gói9),RREQ
(nút nên nút này
1 sẽtrước đó,lộđồng
lưu trữ trình thời
ngượcdo về
nút nguồn (nút 6: 1 → 3 →6) vào bảng định
trong bảng định tuyến hiện tại của nút
tuyến của nó. Sau đó, tiếp tục phát quảng bá
gói3 RREQ
không đến có lộ
tất trình
cả cáckhả nútthi
láng đến đíchcủa
giềng
nó, ngoại trừ nút 3 là nút đã gửi RREQ này
cho(nút
nút9),1. nên
Như nútvậy,3 nút
sẽ 1lưusẽtrữ lộ trình
quảng bá gói
(nút 9), nên nút 1 sẽ lưu trữ lộ trình Như vậy, thuật toán DSR đã
RREQ đến các nút 4 và 7. Sau đó, nút 1 cũng
tìm được
ngược về nút nguồn (nút 6) vào bảng
ngược về nút nguồn (nút 6: 1 3 lộ nhận
trình được
từ nútgói6 RREQ
đến nútnày 9 từ
là nút
6 5 gửi3 đến 7 (từ
định tuyến của nó. Sau đó, tiếp tụcgói
bước 2). Lúc này, do nút 1 đã nhận được
6) vào bảng định tuyến của nó. Sau đó, 9. Lộ này
RREQ trìnhtrước
này điđóqua ba bước
(từ nút 3 gửi truyền
đến), nên
nútphát
1 sẽquảng
xóa góibáRREQgói RREQnày. Quá đến tấtxảy
trình cả ra
tiếp tục phát quảng bá gói RREQ đến (hop). Trong trường hợp tìm thấy
hoàn toàn tương tự đối với nút 2 và nút 7. nhiều lộ
HìnhHình1. Sơ1.đồ Sơ các nút láng giềng của nó, ngoại trừ
nútđồ
khốikhối
chứcchức
năng năng
củacủa
mô môhình
tất cả các láng giềng của nó, ngoại trình, thuật
• Bước toán4:DSRXử lýsẽgói
lựaRREQ
chọn lộtạitrình
các nút
hình nút 6 là nút đã gửi RREQ cho
nhận được gói này ở bước 3 (nút 4 và nút 9):
nút 3.
Đểnút
trừ thấy3 rõ nguyên
là nút lý khám
đã gửi RREQphá nàylộcho
trình có Quá
số bước truyền nhỏ nhất để sử dụng
mớiĐể theo Nhưtrình xửnút
vậy, lý gói RREQ
3 sẽ nhận
quảng bá được tại nút 4
gói RREQ
thấy rõ nguyên lý khám phá lộ trìnhví
giao thức DSR, tác giả xét một
dụ nút
như1.ở Như
Hình vậy,
1. Giảnút
sử1ởsẽ thờiquảng
điểmbá góitại,
hiện chohoàn
việctoàn tương
truyền dữ tự như đã mô tả ở các bước
liệu.
mới định
bảng theo tuyến
giao thức DSR,
của tất tác nút
cả các giảđều
xét rỗng.
một đếnTạicác
trên. nútnút
9, vì1đây
và là
7.nút
Quá trình
đích, nênxảy ra
khi nhận
XétRREQ
trườngđến hợpcácnútnút 4 và khám
6 muốn 7. Saupháđó,một
nút lộ được gói RREQ, nút 9 sẽ tạo gói RREP và gửi
ví dụmớinhư ở Hình hoàn
III.phản
MÔhồitoàn
HÌNHtương tự đối
GIẢItheovới
TÍCHnút 5ngược.
và nút
XÁC
trình
1 cũngđến nhận 9.1Hình
nútđược Quá 1. Giả
góitrình
RREQ
sử ởphá
khám thời
này từ lộ về nút nguồn đường
trình
điểmđượchiệnthứctại, hiện
bảngtheođịnhcác bướccủa
tuyến sau:tất cả 8.Như
ĐỊNH LỘvậy,TRÌNH
thuật toán CỦA
DSR đãTHUẬT
tìm được lộ
nút 5 gửi đến (từ bước 2). Lúc này, do trình từ nút 6 đến nút 9 là 6 → 3 → 7 → 9. Lộ
• Bước 1: Nút nguồn (nút 6) tạo gói TOÁN DSRđi Xử
các nút đều rỗng. Xét trường hợp nút 6 Bước
trình này 3: qua lý
ba gói
bướcRREQ
truyềntại(hop).
các nút
Trong
nút 1phát
RREQ, đã quảng
nhận đượcbá góigói
RREQ RREQ nàycả
đến tất
các nút láng giềng của nó là 3,
muốn khám phá một lộ trình mới đến nút 8 và 8. trường hợp tìm thấy nhiều lộ trình, thuật toán
trước đó (từ nút 3 gửi đến), nên nút 1 DSRnhận
Trong được
sẽphần gói
này,này
lựa chọn ở bước
lộchúng
trình 2 trình
tôisố
có (các
bướcnút
bày 1,
truyền
• Bước
9. Quá trình2:khám
Xử lýphágóilộRREQ tại cácthức
trình được nút nhỏ nhất
sẽ xóa gói RREQ này. Quá
nhận được gói này ở bước 1 (các nút 3, 5 và trình xảy một 2mô
và 7):đểTại
hình sử dụng
giải tích1,cho
nút khiviệc
được đềtruyền
nhận được
xuất dữ
choliệu.
gói
hiện
8): Tạitheo
nút các
3, dobướcchưasau:
nhận được gói RREQ III. MÔ HÌNH GIẢI TÍCH XÁC ĐỊNH LỘ
việc RREQ
tìm tậptừlộnút 3, của
trình do chưa nhận định
giao thức được
ra hoàn toàn tương tự đối với nút 2 và
này trước đó, đồng thời do trong bảng định TRÌNH CỦA THUẬT TOÁN DSR
tuyến
nút hiện
7. tại
Bước 1: của
Nútnút 3 không
nguồn (nútcó6)
lộ trình khả
tạo gói tuyếngói RREQ
DSR này
trong trướctùy
mạng đó,biến
đồng
di thời
động.do
Trong phần này, chúng tôi trình bày một
thi đến đích (nút 9), nên nút 3 sẽ lưu trữ lộ
trìnhRREQ,
ngược phát quảng
về nút nguồnbá(nút
gói 6)
RREQ đến
vào bảng Đểmô hình
trong
phát giải thuật
bảng
biểu tích
địnhđược
tuyếnđề
toán DSRxuấtthành
hiện cho
tại củaviệc
núttìm
mô
Bước 4: Xử lý gói RREQ tại các nút tập lộ trình của giao thức định tuyến DSR
định tuyến của nó. Sau đó, tiếp tục phát quảng 1giải
không
tích, có
hình
trong mạng tùylộbiến
chúng trình khả
tôidiđịnh thiĐểđến
nghĩa
động. các đích
kýbiểu
phát
bá nhận
gói RREQ
được góiđến này
tất cả các nút
ở bước láng4giềng
3 (nút và thuật toán DSR thành mô hình giải tích, chúng
của nó, ngoại trừ nút 6 là nút đã gửi RREQ hiệu
tôi toán
định học
nghĩanhưcácsau:
ký hiệu toán học như sau:
chonútnút9):3.Quá
Nhưtrình
vậy,xử
nútlý3gói
sẽ RREQ
quảng nhận
bá gói
RREQ đến các nút 1 và 7. Quá trình xảy ra n là
GọiGọi
được tại nút 4 hoàn toàn tương tự như n làtổng
tổngsố
số nút mạng, A [aij ]nn là
nút mạng, là ma
hoàn toàn tương tự đối với nút 5 và nút 8.
trận biểu diễn các nút láng giềng của nhau
đã mô tả ở các bước trên. Tại nút 9, vì ma trận biểu diễn các nút láng giềng của
đây
14 là nút đích, nên khi nhận được gói
TẠP CHÍ KHOA HỌC nhau trong mạng, trong đó các phần tử aij
QUẢN LÝ VÀ CÔNG NGHỆ
RREQ, nút 9 sẽ tạo gói RREP và gửi được xác định như sau:
phản hồi về nút nguồn theo đường
- GọiVín dụ, là tổng xét số trường nút mạng, hợp HìnhA [aij1Hình
tôpô ]nn là 1,
mạng ở ma (trận biểu diễn
1X( k1k) ) 0[x(ijk( k)0) ]nn0 với 0 0các0 phần
các nút
tử
ij
được ( k ) xác
1 định x(ijk( k) ) bởi:
xác n
vì ma Ví trận dụ, biểu xét 0trường diễn cácĐểnútphát
0 1 hợp
1 1 tôpô
0lángbiểu 1 mạng
giềng
0 0
thuật
0aijcủa
ở
củatoán
1 1 trong
X DSR -định Khi
[xij ]nthành như n
k với > sau: 0:các
mô các phần
0 (2)
phần tử tử
x ij
xij( k ) xđược
được ij xác
a
ij ij
a xzj( k
góiHình
ma RREQ
trận biểu
1Hình tạidiễn các 1,0 nút
các
ma
0 0 0trận 0nút 1 1 láng 1 1láng
1biểu 0giềng0 0 1giềng
diễn A
1các 0của 99 nhau
0nút 0 0 tôpô
định 0như 1 này
sau:0 0được
z 1
ói Hình 1Hình
nhau trong mạng, 1, ma
trậntrong hìnhbiểu đó giải diễn
các phần
tích, các nút
tử
chúng a ij tôi 0 định định
0 bởi:
1 nghĩa
0 x
1
( k 1)
các
0 0 ký 1 0 neá- u Khii m k = 0: X (k)
= [0].
sau:định bởi: ij
1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 00 k 0
này
nhau ở trong
láng bước
trong giềng 3mạng,
mạng, (nútcủa trong4trong
nhauvà đó đó
trong các cáctôpô xácphần
phần định này tửtử như ađược
ij được 1 0 1 0 0 x ( k 1)
0 0 0 1 neá u i m
ửi láng giềng xác của
1nhau trong 0 0 tôpô 0 1 0 này 1 0 0 1được
được định 1như
1 0 0sau: n
0 0hiệu 0toán học 0 sau:
như - Khi ) ij (k) ( k 1) - uKhi mkk > (0:
k
các phần
hđược
Ví xửdụ,lý
xácxác
xác định như
gói
xét
Ađịnh định a như
RREQ
trường như
sau:
nhận
sau:
1 1sau: hợp tôpô
1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1X0 mạng ở Ví
(2)
( k ) dụ,
0(
-
[x k )]n1n với
k ) 1
Khi xét x0ij( k k
k
0=
=
trường
các
a00:
0: 1 phần
ij 1X
X
a(k)
ij
hợp
0 =
= 0[0].
[0].
xtôpô
0
z1tử x( kij(k1))được
n zj ( k) mạng
neá i ở
trong
xácnhư sau: đó,
X k(4)
)
a [xij là
(k )
] các vớip
ngVí xác dụ, định xét ijnhư trường hợp tôpô mạng ở X
sau: ( k ) 0 ij(1 1x ( k )0
với các a 0a 0
phần tử x zjx được neáđịnh u xác
i m (4)
ij n n
adụ, 1ij trường
99
[ x ]
0ij-0 (0Khi 0 1 (k>)0 0:0 các
1] ) 1 kvới
1 0phần 0 ij tử (kcác
xđược xácxác
( k )
1t0trường 00số
ij ij ij
x(uijk )nút k
nh
hoàn Ví
1Hình dụ,aAVí
toàn xét
1,
tương ma neáxét
99 trận
u0nuù
tự như j hợp
biểu1laø1 laù0 0ngtôpô
diễn 0gieà
Gọi
1hợp 0n0gmạng
các 1n
cuû0 alà
tôpô 0nuù
nút 0t ở
1 tổng 0i Hình
mạng X(2)( k1Hình
0)nút
ở -[xKhi kn)(nk 1,
mạng,
ijX nnk[xij
ma0A0
> ]n0: trận
0[các
a 1]với
n ij các nphầnnbiểu
0là cácz 1 diễn
phần tửphần xtử )neá
được
tử ( ksxác
jđược
biễu )
đượcdiễnxác các nút láng
nh 1Hình 1ij neá
1,u0ma t0jtrận
nuùtrong
1laø00tröôø 0nbiểu
laù 10gn1ggieà
11hôï 0ndiễn 0cuû01a0các
p1g0 ngöôï c10laï
nuù 0t i00nút 0 0110định
(1) bởi: định như sau: ij x ij ij
x 1) bởi:
định
( k
định
1 định 0bởi: 0 định 0 0như 1 xử 0
1 lý 0 gói 0 neá u j s
sau:
ij
Hình
gbước aij 1Hình
giềng Hình củaTại
trên. 1,
1Hình
nhau 0 0trận
ma
nút 1,
trong
9,
1ma
vì
1 trận
biểu
tôpô ma
1 diễn 0biểu
này trận
1 các
được
0diễn
biểu Để
0(1)
nút các
diễn xác
láng
địnhnút
các giềng nút thứcủa láng tựnhau giềng trong của tôpô RREQ, này được trận
A). Phép toán (
0
của nhau trong tröôø
0
0trong 0 n 0
g
1 1hôï00 p 0 1
ngöôï
1 0 1 0c 0 laï0
0i 1 00 0 10 0 0
0 1 1 0trong
0 1 bởi: định 0 0 đó, bởi: 0 ( k 0a1)ij 0là 1các phần tử của (k )
ma trận n
g giềng Ví dụ,0xét 0 1tôpô 1 0 này
0 0 0 0 1 1 0 0 - Khi k = 0: X (ijk=1)[0].
trường hợp tôpô 0 được 1 mạng 0 ở Hình (k) x neá u i m
xij k aij aij xzj X
- Khi k = ( k0:
1)
0aijmạng, 0này
áng giềng
địnhkhi
nên láng
như nhận của
sau: giềng nhau
được 1 của
0 0
0 gói trong
0
0nhau
1 0 0
0 nhau
1tôpô
0trong
0 0 0 này
0
1Atôpô
trong 1 1
láng chúng
được
0 0 0 0 0tôi
xác
được
-1trong định
định
Khi 1 k 0 đónghĩa
như=trong
0 0: các sau:
0X max
(k)đó,
ij =
1phần trận
0 [0]. a0tửij là M =
các
a0ijláng [m
(2)các ]
phần neá
i 1 (n- u i tử (4(4)
m củacủa malà(ma trận
phép z 1 toán cộ
c định1,như ma trận 1biểu diễn các 1nút 9giềng
9 của biễu diễntrong các đó, nút là giềng phần củaktửnhau ma trận
sau: 1 10 00 00 01 00 00 01 10 0-0Khi k = X =0:[0].
n(k)
- Khi
0các k1 phần -
>biễu
x0(biễu
( Khi
) 0:
0:1diễn cáck
0diễn
(k)
=0acác phần 1
các X n 0 nút
xtử = ( [0].
1)láng( k
x (định )
được
neágiềng xác
mcủa -
0 nhau Khi (ma k > 0:
ẽáctạo định nhau như trongsau: 1tôpô này
0 0 được 0 0 xác 0 định 01), 1trong như sau: đó k)
k
tử aijm
ij được
k
xác
ui (4)
xác
gói
A Để a xác định
định
RREP như
và
1 1 thứ
A aij0ij99909 11 11 10 00 10 01 00 0 0 (2)
1sau:
gửi 0 0tự0 xử được xác
1 lý 0 gói định
0 0RREQ, như -1định
(2) sau:
Khi 0Khi
ktrận
1như
x> ij
0
sau:
0ijtrận
0:
0A).
acác
0A). 0ijk1Phép 0aPhép
i
ij 1
phần
00:
nút
1z toán x tử 1
( kzj
110zj tử
1) ij
láng
x neák )giềng
ij 0x ( trong
được
k)
0u i
của
mnhị
xác k
(công
công
kk )
nhau
phân. (4)
thức
(ma
định
thức (4)Biểu là thức
như sau
Để
0 0xác định thứ tự xử lý gói
RREQ, -
định như k
- >
Khisau: 0: các > phần
z 1các phần
được
tử
x xác
được xác
1 0 1 0 1 1 0 0 1 1 0 0 0 0 như
1 0 sau: m = u nghĩa
phép là
toán nút cộng u xử modulo lý gói
ij
trong hệ nhị phân.
aA).
ij
út nguồn 1 nghĩa ]0 1i 0 trận 0 0 0 0Phép 0 1 0 0toán neá
1 0 0 1 0 trong
neátrong
u j định s đó, công aij thức
chúng 00theo tôi
000 0định 000đường110 11110 10001 00ma 1 1101trận
0 1 000010M 1neá=u 0[m 0ti j1laø
nuù
(n-định
laù n g (4(4)
gieà
0 0sau:
như
( k định
n g 1) là
cuû
01thứcnhư
phép
nuù t i sau: toán cộng uxác
modulo j s định trongđiều hệkiện
là các xràng(phần
k 1)
1 0 1 0 0 0 0 0 1 x Biểu
1
0 0 0 này 0 cho
neá
1 u 1 i phépm0 0 điều kiện ij
chúng 1 0 tôi
001định
0 0
000 1phần 0 1nghĩa 1 0 01ma 1 aij011trận
0 0
0 0 0RREQ M1= 0[mởi]1lần
0 0
(n- thứ 0 x(4(4) 1
ij ( 0
i c(đối
k 1) 0 với 1 0
yêu (1) 0 cầuneámỗi ucộng ikhám
m
k
100đó 000 110 0tử 10 0m i là phép toán modulo của matrong trận hệXláng luôn
j của (k)
1), trong 0 các 1 01i 0được00 0trong xác
0 tröôøđịnh ng hôïptrong ngöôï
nhị
ijràng
x 1 klaï
đó,
phân. 1) 1 buộc
na 0 x ( klà
Biểu 01)trongcác
0 thức
0 phần0
neá u này
0i
cột
k biễu
tửm1 neá của
cho u i
diễn
ma
phép
m
ma các trận
trận xác nút
giề
1 11 000 001 000 000 100 1010 0101001 0 0 x ( k ) trong ijđó, an ijlà ij ( k 1)các phần tử kcủa ma k trậnx
( k )
a aij
aij 9như
, trong
1 1 đó 00 0các 0 00phần 01 00tử00m1i1Để được phá
0 xác0 xác
lộ trình
định định ) nút
từ
ija( kthứ
a
ij
tự
nhị
luôn a
1sxử ij đến
phân.
luôn 0 nút
lý ij x
gói chỉ
(Biểu d. có
RREQ, Víneá một
u
thứcdụ, i phần
m xét
nàyk 0
tử
cho(2)(4) phép xác
có giá trị ijbằng ij
1)
1sau: 1 m
00i = 00 u00nghĩa
aij 999 111 10 001 001 010 00 00 0001 (2) 1
11 00 là 00 nút 01 u
0(2) xử
0 lý gói A xij biễu
ij 9
( k
9 a
)định
ij1,
ađiều
diễn
1
ijk )znghĩa
(có
các
1 kiện
n
zj0 k 1)
xzjnútlà 0 1)láng
( kràng
1
nneáubuộc
mỗi
0 i
(giềng
nút
0
mtrận
k 1) j ktrong củatử
trong (4)
A).
nhau cóPhép
mỗi
mạng giá
(ma chỉtrịjphát
cột bằng
toán 1, t
A aRREQijĐể
như 0 asau:
0 11 m 0i 1=011u 00nghĩa 00 010làchúng 01nút 0trường u tôi
(2)xử lý
định
hợp gói
(2) nghĩa
x biễu
tôpô
ij
0
ma
định
diễn
a
quảng 0
x
mạng
ij
ij
a
0
trận
ij
điều
cácz 1
bá
a
ở
1M
nút
0
ij gói
x a
Hình
kiện =
1 láng
ij RREQ
zj
[m 0
neá
ràng
x
1Hình
] ugiềng
neá
0zj j
u 1
một
buộc
i
s
0
1
mcủa
neá
lần
k
trong
u nhau
i
đối
(4)
m
với
k
mỗi
(ma mỗi (4)
cột yêu
j
0
A
99 xác
1
0 ijở09định lần
9 1 0
0 thứ thứ1 i 0đối 0 1
tự 0xử với 0
1 lý0yêu gói 0
cầu
0RREQ, 0khám trận 0 z 1 (k) z neá
của ma
1A). trận
Phép 1 X 0 luôn
toán
i 1 1
(n-
0uluôn j 0 s 1(4(4)
trong chỉ có trong
công làmột phép mạng
phần
thức toán chỉ cộng phát m
Để 1xác 00 định
0 1 10 0 thứ00 0 1 0tự
1 0 0 xử
0 0 0 1 lý11 gói
0 0 0 RREQ,
1 0
trận
cầuA).
0
0khám
Phép
0phá
toán lộ 0 trình.
trong công thức
RREQ 1 0 ở 1lần 0 thứ 0 0i đối 0 0với 1)0,M
yêu
1 trong với cầu yêu
đó khám
1các
cầuphần khám tử
của 0 phá mma 1i được trận 0
0lộ 0trình Xxác0(k) 1luôn từneá
định 0 nút
u j 6sneáu j s
luôn 0chỉmột có một lần phần
đốij đó, với
phá lộ
chúng
chúngtôi
0tôi 1trình
1 định
định 0 0 từ 101nghĩa
nghĩa 000 01s1ma
nút
ma
đến
0 00 0trận
trận
00nút 0 0
M
d.
1 0=Ví
=
[m
0
[m
dụ,
i1]trong
]
xét
(n- đó,
(4(4) tử
a có ij làlà giá
các
phép
Trởtrị phần
bằng
toán
lại với tử
1,
cộng ví có củadụ
0 nhị
nghĩa
modulo ở ma Hình
làphân.
trận mỗi
trong
1, xét
trong
Biểu
nút
hệ
yêu cầuthứcamỗi là
ijnày
phá
0 1 0 0 0 1 0 0 0
00 1s10đến d. 0Vínút
i 1trong
(n- đó,
(4(4) a 0là là phép
0 các 0 1 phần
toán 0 cộng
0 tử 1 của modulo
0 0ma trận
trong hệ
0 lộ 0 trình 0 010từ001nút 00nút đến dụ, 9. xét Khi đó, làma trận M được xác
ij 6 đến nút 9. Quá
00đó 0 1các 0 0mạng 000ở 0i như 0100sau: m i = 1udiễn
trong nghĩa đó, tửkhám
trong có
anút nút
giá
là
đó, phá các utrị
achỉ ijxử
lộ bằng
là trình
phần lý
các gói
1,
mới
tử cócủa
phần từ nghĩa
núttửma của là
trình.
trận mỗi
ma biễu nút
trận diễn j các nú
1),trường hợp 0 tôpô Hình 1Hình
trong 1 phần 0 tử1 m được xác 0định
biễu các láng giềng của nhau định (ma điều kiện ràng buộc
, trong đó các phần tử m được xác định
nhị trong phân. ijmạng
Biểu phát
thức quảng
này cho bá gói
phép RREQ xác Lần xử
1)
trường 0
hợp0tôpô 0 0 1 0
0 0mạng 0 1 i
1 0 ở0 Hình 0 0 1 0 1Hình
định biễu
0 Để diễn
nhị định
1xác các
trình
phân.thứ nút phát Biểuláng quảng giềng
thứclý này bá củagói nhau
RREQ
cho (mađể
phép xác(k) khám phá lộ
Để xác nhưvớiđịnh sau: yêu m thứcầu i =tự khám
u xử
nghĩa lýphá góilộ
là nútRREQ
RREQ,trình
u xử ởlýnhư
từ lần
nút
gói sau:
thứ
biễu6 A). idiễn đối trong
biễu với
các
Lần diễn nútyêu
mạng xử các tựlý
láng cầu chỉxử
nút gói khám
phát
giềng láng
RREQ gói quảng
củagiềng RREQ,
nhau
đầu bá
của gói
(ma
tiên: nhau RREQ
trận
Nút X(ma A). Phép
Để như xác sau: địnhmthứ i = u tựnghĩa xử lýlàgói nútRREQ, u xử lý gói trận một
địnhLần Phép trình lần
điều xử
toán
nàyđối kiện lý
được
với
gói
ràng trong
mỗi biểu
RREQ yêu
buộcđầu diễn công cầucủa
trongbởi
tiên:
ma
thức
khám mỗi trận
trân
Trở
Nút phá
cột lại
6 lộ6với
jphát luôn
như quảng
ví luôn
Ở dụ Ởở
lầ
với yêu cầu khám phá lộ trình từ trận
nút A).
định
6tôi Phépsau:điều toán
kiệnma
ràng trong buộc côngtrong thức
mỗi cột j
ngĐểtôi
RREQ xác
đến định Để
Để
định
nút ở xác
nghĩa
xác 9.
lần thứ định
Khithứ ma tự itrận
đó, xử
thứ
đối ma M lý
tự
với = gói
xử
trận phá
[m
yêu RREQ,
lý
i]M 1 lộ
cầu
gói(n- trình
được RREQ,
khámchúng
M(4(4) từ
xáctrận
= [6làcủa nút s
A).
3trình. định
đến
một
trận
phát
phép5ma Phép
8 toán nghĩa
nút
lần
A).
quảng
1 7 Xcộng
trận
d.
đối
toán
Phép Ví
bá
2(k) 4luôn
(k) với trận
dụ,
gói
9] toánmỗi
modulo
xét
trong M
RREQ
luôn(3) yêu=
chỉ
[m
công cầu
trong
tử có
trong
i]1khám
đến cókhám (n-
hệthức
công
tất
giá trị
một cả phá
(4(4)
phần thức
các
bằng lộ
là phép
phát
1, cógiề to
ng q
úngRREQ tôi định ở nghĩa lần định thứmaithứ trận
đối tựvới xử=lý
M yêu gói]cầu
[m RREQ,
i 1(n- khám
chúng
phát quảng báXLần gói RREQ đến tất cả phá
các nútlộ phátláng
trình mớ
quả
húng tôiđến
chúng định nút tôi 9.
nghĩa định Khi mamsđó,
nghĩa trận ma M trận
=d.[m MM i]1 được (4(4)
1),xét trongxáccủa làđó phép ma các trậntoán
phần cộng tử luôn xửmodulo
m i được
luôn
lý gói chỉ RREQ
xác trong có định một hệ phần
đầu tiên: Nút 6
rong phá tôi
đó
định định
lộcác như trình phầnnghĩa
sau: từ tử nútma đếnma
trận
i được nút trận
trường
xác định Ví =dụ,
(n-[m
hợp
nhị i]tôpô
1(n- mạng
(4(4) phân. tử quálà
nút trình.
(4(4)
có phép
Biểu
phát láng
giá
ởlà Hình
toángiềng
thức
trị xử
quảng phép bằng
1Hình
cộng
này
bá của
toán 1, có
gói modulo
nó,
chocộng 1 điều
RREQ nghĩa phép modulo
trong trong
này
đếnlàđược xác được
mạng
mỗibiểu
Quá tấthệtrongnhị
nút
trình
cả biểu
chỉ
các phân.
hệ
jdiễn phát
phátnútbởi nút Biểu
quản
quản lán
trong
,
pháđó
trong
đólộcác
địnhđó
cáctrình
như
các
phần
phần từ nút
phầnsau:
tử m
tử
tử
s iđến
m
được
được
được
nútxác xácd. Ví
xác
định
định
định
dụ,như
Để xét
biểu
nhưnhị sau: diễn
sau:
nút
phân.tử m láng
cóláng Trở
=
trình
giáu giềng
Biểu giềng
lại
trị
nghĩa thức với
bằng của lýví
là này gói
nó,
dụ
1,nút có ở RREQ
điều
cho u
Hình
nghĩa xử
này
phép lý
1,
làgói xét
mỗi
xác yêunút j diễn ma
cầu nút láng
ư) sau: trường ,
mi = hợp trong u nghĩa đó tôpô các là phần
làmạng núti uuxử
nút tử ở7xửHìnhmvới
lýilý được
góiyêu gói 1Hình
RREQ xác
cầu định
1khám
ởnhị lần phân. phá
nhị
diễn i lộràng
Biểu
phân.
bởi trình ma thức Biểu từ này
của
trận
nó,
Xthức (1) 6 điều
(1)cho
này
(1) phép xác định điều kiện
này ]một cho được
lần phép
đối biểu
vớixác mỗi yêu
9 với jcác phần diễn nàb
1)
định điều trong kiện Trở
mạng lại chỉ buộc
với phát (1) trong
ví dụ quảng ở[]xtrận mỗi
ijHình 9bá cột
1, xét yêu cầu
ư sau:trường thứ m i i = Mhợp
đối u = với
[6tôpô
nghĩa yêu
3 5
mạng
là cầu
8
nút 1
khám u ở xử 2
Hình
phá
4
lý 9]
lộ1Hình
gói
trong trình mạng,
định
từ
(3)
1 nút chúng
diễn
trong
điều khám bởi
kiện
bởi mạngtôi ma
phá
ma định
ràng trận
lộ
chỉ
trậnbuộc nghĩa
trìnhphátX mớima
quảng
trong
[ x từ
ij 99mỗi với
nút
bá
với 6gói
gói
cột
khám
các
các đến j
RREQ
phần
RREQ
phần
phá
nút 9.lộdiễn
tử
trình
xij( k ) được bởi
hư với
EQ sau:
ở snhư lần mthứ isau:=M ui=mđối nghĩa
i = với 3u là 5nghĩa
yêu8nút ulà7đến
cầu xử
nút2khám lý
4nút utừ gói
xử9. RREQ
lýKhi 6gói
định đó, ởđiều lần
ma thứ trận i ràng M đối đượcvới yêuxác cầutrình. khám jcủa ma j trậnsau: X(2)(k)
yêu cầu [6
khám phá 1lộ trình 9] nút của (3)
ma trận định X(kiện
k ) điều luôn kiện luôn buộc ràngchỉ trongbuộc
có một mỗitrong phần cột mỗi cột
được (k) xác định theo (4) như sau:
REQvới ở lần đến
yêu nút
thứcầui diễn d. Ví
đối với
khám dụ, pháxétyêu trường
lộcầu trình hợp
khám từ tôpô
nút mạng
6 ma một tử khám lần
x đối
được phá với lộ
xác trình
mỗi định mới
yêu theo cầu từ(4(4) nút
khám ma 6
như đến
phá
trân sau: nút
Xlộ (k) 9.như tử
RREQ ở Để lần biểu thứ i đối quá với trình yêu xử
cầu lý gói
khám RREQ
phácủa lộ một
tử
trình
Quá
trận
x ) ijX
( klần
được
từ
trình
đối
(k)
nút luônxác với
s
phát
đến luôn
địnhmỗi quảng
nút chỉ
yêu
theo d. có cầubámột
(4(4)
Ví dụ,
gói
khám nhưphần
xét
RREQ phá lộđể tử x (2) xđư
sau: ij
lộ đến RREQ
ở
trìnhnút Hình từ nút 1 ở với lần
s đếnyêu thứ cầu
nút i đốikhám
d. Ví với phá
định
dụ, yêu lộ
như
xét cầu
trình sau:khám
từ của nút ma trận Xtrình luôn X luôn chỉ có tử có giá trị
ij bằn
bámột phần
(k)
9. Khi đó, ma trận M được tử xác có giátrình. của
ij
trị
Quá ma
bằng trận 1, có
phát
(k)
nghĩa luôn quảng luôn
là mỗi chỉgói nút có một phần
jRREQ đểdụ ở Hìn xij(0
á lộđến trình
6 đến nút Đểtừ 9.nút
nút biểu 9.sKhi
Khi diễnđến đó, đó, quá
nút ma mad. trình
trận
trậnVí M
xử
dụ, lýxétgóixác
được RREQ
xác
tử định
có trình. khám
giá trịtôpô phá
bằngmạng lộ
1, trình
có ởnghĩa này được
là1Hình mỗi nút1 j Trở
biểu lại
diễn với bởi ví
há lộ trongtrình
phá lộ mạng,
từtrình nút chúng
stừđến nút tôi
nút
s đến định
d.1Hình Ví
nút nghĩa
dụ,d. 1Ví xét ma dụ, trận
trường xétcóhợp Hình
ờng hợp
định như tôpô
như sau: sau: mạng ở Hình M1= ma trong
[6 3trận tử mạng
5 8 khám giátử trị
có
1 7 2xpháchỉ bằng
giá xtrị
phát 4(k) 9]
(0)
1, bằng
quảng có
lộ trình (3) nghĩa
1, bá
này có gói là neámỗi
nghĩa
được uRREQ im nút
là
biểu mỗi j trong
diễn nút mạng
j
bởi xmới chỉ
ờngđịnh hợp trongnhư tôpô mạng,
sau: mạng chúng ở Hình tôi định 1Hình nghĩa (0)
ij
neá u khám
i m
1
phá lộ trình (1)
từ
aij
maTrở trân lạiX như sau:
trong mạng chỉ phátvới ví
quảng dụ 9 ở bá Hình 1,nút xét6yêu cầu
gói RREQ
ij 1 ij
rường hợpkhám tôpô mạng 1với yêu cầu khám phá lộ trình từ
yêu cầu trường hợpphá tôpô lộ ởmạng trình Hình từở 1Hình Hình6 1Hình
nút trong 1 Trở
mạng
trong lại chỉ
mạng
với phát ví
chỉ dụ
quảng phát ở Hình bá
quảng 1,
gói xét RREQ
bá yêu
gói cầu
một
RREQ lần đối với
i yêu cầuMkhám = [6 3phá5 lộ 8 1trình 7 2từ4 Để nút9] biểu 6 diễn một
(3) lần đối ma với
x (1)
trân
mỗi
X
a (k)yêu
a như 9
cầusau: x (0)
khám neá
Quá phá
u i m lộ
trình phát (5) quảng x
(2) bá
(2)
ớinútyêu vớicầu
9. M
Khi yêu = khám [6
đó, 3
cầumaphá 5
khám 8
trận 1
lộ phá M 7trình 2
được 4
lộtừtrình 9] nút từ
xác đến
6 nút một
(3)
một nút quá
lần
6 khám
khám 9.
lầnmột
trình
đối
x (1)
ijKhi
đối
phá
với
phá
ij
xử
a
đó,ijmỗilộ
lộmỗi
lý a
ij
ij
trình
ma gói
trình
yêu
ij
RREQ
trận xmới
cầu
(0)
mớicầu
z
zj 1
zj
M từ
từ neánút
khám
được u
nútcầu
i 6
phám
6 phá xác đến
đến
1 lộ1
nút
nút (5) 9.
9. lộ
trình.
x ij
0
ij
trình. với
lần đối với z yêu
1 mỗi yêu khám khám lộ phá
n nút 9. Khi đó, ma trận M được trong xác mạng, chúng
trình. Quá tôi định
trình 0
nghĩa
phát ma
quảng trận bá khám
neáu j phá
gói RREQ s lộ trình này đư
để
hếnnhư nút Để
đến 9. biểu Khi
nút diễn
9.đó,Khi quá
mađó, trình
trận ma M xửđược lý gói Mlý( kxác RREQ định như sau: 0 neáu j s
g ở Để sau: Để
( kbiểu
biểu
( kdiễn
diễnquá
với
quá
trình
các phần xửtrận
trình lýxử
tử gói được
gói
)RREQ
được
RREQ xác
trình.
xác
Quá trình. trình phát quảng bá gói RREQ(k) để
nh nhưtrong sau: mạng,
X )
[ x )
] nn chúng tôi định nghĩa
x ma Trở trậnkhám lại với phá ví dụ
lộ ở
trình Hình này 1, xét
được ma
yêu biểu trân
cầu diễn X như
bởi Trở sau:lại với v
ịnh trong
như định mạng,
( k( k)sau: như
ij
( k( k) ) sau:
chúng tôi định nghĩa( k( k) )ma trận Trởkhám ij
lại với phá ví lộ dụ trình ở Hình này 1, được xét biểu
yêu cầudiễn bởi vì theo
ởở trong X[6mạng, [[xxij ]]nchúng tôi
M =Xđịnh vớivới 7 các 2 4định
các phần
phần9] nghĩa tử tử x(3) xijij ma được
được trậnxác xác MTrở = [6 3với5(k) 8 dụ 1 ở 7víHình 2dụ4 ở9] (3)xét vì theo (
)
nút 3bởi: ij5 n8 nn 1 với các phần tử được xác lại Trở ví
lại với 1, Hình xét yêu 1, cầu yêukhám cầu phá lộ trì
M= [6 bởi: 3 5 8 1 7 2 4 9] (3) khám phá
ma trân lộ trình X(k) như mới từ nút 6 đếnneánút
sau: 9. được
nút
nút
định khám maphá trân lộ X
trình như mới 0 sau: từ nút 6 đến unút i 69. đượcsau: x (1)các
ược Mđịnh =
định bởi: [6 bởi:M 3 = 5 [6 8 31 57 8 2 1 4 7 9] 2 4 9] (3)
Quá Để
(3)
khám biểu
trình phá
khám diễnphát lộ quá trình
phá
quảng
0 lộmới
trình trình
bá xử từgói nút
mới
lý 9 gói
neá u
6từđến
RREQ
i
nút nút
RREQ
6 6đểđến 9.Quá nút 9. trình
sau: phát
ij
Để biểu-diễn quá trình xử lý gói RREQ
ợc
Để biểu diễn
ược Khi kquá = 0: trình X(k)xử = [0]. lý gói RREQ Quá trìnhphát (1) x (1)
ij quảng aij abá 9 0
neáRREQ
gói neáu i để 6 (6) - Kh
ngĐể mạng, biểu--- Khi Để
Khi diễn
chúng kkk==quá
biểu 0:
tôidiễn
0: Xtrình
X
(k)
định
(k)quá==xử [0].
nghĩatrình
[0]. lý gói xử RREQ
ma lý
trận gói trong RREQ Quá
khámmạng, trình
phá lộchúngQuá x phát
ij trình
trình này a quảng
ij phát
tôi định
a ijđược
ij
bá
quảng 0z 1gói
nghĩa
biểu
bá uRREQ
ma i gói
diễntrận 6 RREQ
bởi để (6)
khám đểphá - Khi lộ trì j
Khi
ng mạng, chúng tôi định nghĩa ma trận > 0: các phần tử x (k )
được khám xác phá lộ trình này 0 được z 1
biểu diễn
neáu j 6 bởi
rong mạng, trong định chúng
mạng, như tôi
chúng
sau: định tôi nghĩa định ma
nghĩa
ij
( k( k)trận ma ma khám
trận trân Xphá(k) lộ phá
khám như trình 0 lộnày
sau:
trình được này biểu
neáđược u jdiễn 6biểu bởi diễn ma bởi trân
vì theo
- X-(k)Khi
Kh
như
(3(3 i
-- Khi Khi kk >> 0: 0: các các phần phần tử tử xxijij được )
đượcma xác
xác trân X (k) (k)
như sau:
địnhđịnhnhư như sau: ma trân vìma Xtheo trân như (3(3) Xsau: (k) m = 6 và X
như 1 sau: (0)
(0)
= [0]. Từ (6(6) và (2(2) - ta Khc
x ( k sau: 1)
neá u i m vì theo (3(3) m 1 = 6 và X = [0]. Từ (6(6) - Khi i
( kij1) k
và (2(2) ta có: [ x (1)
]
xx ( k 1)
( k ) ijij
n neá neáuuiimmkk và (2(2) ta có: TẠP CHÍ KHOA HỌC 15 6 j (2
x
xij aij aij xzj neáu i ( k 1)
mk (4) (1)[x6(1)j ] [a6 j ] [0 0 1 0 1 0 0 1 0]
QUẢN LÝ VÀ CÔNG NGHỆ
x31 (2) 31
a
(2)
nn (7)
( k( k) )
aaijijaaijij
z 1 1)1) [ x ] [ a ] [0 0 1 0 1 0 0 1 0] (7) Từ (6(6) và
( k( k
xxij xxzj neá
neá
uuii mmk (4)
(4) 6j 6j
2) 0 neáu j s
ij zj k
(2) zz 11
- x 9
aij0ijaij ij z01 neáuneá
ij(1) ij
i 6
u 6j 6 (6)(6) - --Khi Khi j =j i= 6,≠6,m ==
( 2)
xij( 22x) ij 0.i ≠ 0. 3, x (2) = x (1) .
xij
a
ij ij
a z 1 0
neá u
i (6) - Khi
Khi j = 6, xij = 0. ( 2) ij ij
0 0 z 1 neá
neá(0) u
u j 6j 6 --Khi Khi i ≠i i≠ m=2mm 2 i ≠i i≠ 3,=3,x3: x = x .
( 2) (1)
X u j= 6[0]. Từ (6(6) -- ij ij= xij .ij
Khi
( 2 ) (1 )
vì theo (3(3) 0 m1 = 6 và neá Khi i ≠ m2 2 i ≠ 3, xij(2) = xij(1) .
vìvì vàtheo
theo vì(2(2)
theo
(3(3) (3(3) ta(3) mcó: 1m= 1= 6 và 6 và X(0) X(0) == [0].[0]. Từ Từ
. Từ (6(6)
(6)
(6(6) và - - Khi Khi i(2)=i = m2m 2 i =i9 = 3:(1)3:
319
vì(2)
theo
và ta
(2(2) (3(3)
có: ta m1 = 6 và X = [0]. Từ (6(6)
có:
(0) - Khi x i = m
a 312
a i = 3:xz1 1(1 0) 1 (10)
và (2(2) ta [x6(1) có: ] [a ] [0 0 1 0 1 0 0 1 0] (7)
31
9
và (2(2) ta(1)có: j 6j (2)x31(2)
a31a31a31 a31
9
z
xz(1)
1 (1)
xz1 1(1 1(1 0) 1 (10) (10)
x31
1 0) 1
[x
(1)
[x6 j ]6 j [a6 j ]6 ] [ a ] [0 0 1
j [0 0 1 0 1 0 0 1 0]
0 1 0 0 1 0] (7) (7) x31 a31 a31
(2)
z 1 x z1
z 1(1)
1(1 0) 1 (10)
Từ [(6(6) x6(1)j ] và [a6 j(7(7) ] [0 ta 0 1có: 9
0 1 0 0 1 0] (7) x32(2)
a32 a32 z 1
xz(1)2 0(0 0) 0 (11)
Từ
Từ (6(6) (6(6) vàvà và (7(7) (7(7) ta
ta có: có: 9 9z 1
9
32 (11)
(2) (1)
Từ (6(6) Từ (6) và (7(7) 0 (7) 0 ta0 có:
ta có: 0 0 0 0 0 0 x32(2)x32 a a32a a
32 32
xz(1)2xz2 0(00(0 0) 0)0 0 (11)
1(1)
0 000 000 000 000 000 000 000 000 00
x (2)
32
a
32 32
a z 1 zx z2
z 1 x33 0
(2)
0(0 0) 0 (11)
(12)
0 00 00 00 00 00 00 00 00 00
0 0 0 0 0 0 0 0 0 x33 x33
(2) (2)
9 0 0 (12)
(12)
0 0 0 0
0 00 00 00 00 00 00 00 00 0 0 0 0 0 0 0 x (2)
0 (12)
9 (13)
(2)
x34 a34 a34 33 xz(1)4 0(0 0) 0
X (1) 0 00 00 00 00 00 00 00 00 00 (8) 9
0 0 0 0 0 0 0 0 0 z 1
9
34 (13)
(2) (1)
x34(2)x34 a a34a a xz(1)4xz 4 0(00(0 0) 0)0 0 (13)
X (1)X 0 0 000 000 010 0 000 010 0 000 000 010 0 00 (8)(8)
(1)
34 34
1(1)
34 34 z94 (13)
(2)
x a
a zx
0(0 0) 0
X 0 00 00 10 00 10 00 00 10 00 (8)
(1) 34 z 1
0 0 1 0 1 0 0 1 0
00
00 001 00 001 00 00 001 00 00
0 0 0 0 0 0 0 0
x (2)
35
a35 a35z
9 9
1
x (1) 0(0 1) 0
z 5
(14)
9
z 1
35 (14)
(2) (1)
x35 x35
(2) a a35a a xz(1)5xz5 0(00(0 1)0 0 (14)
1)
00 000 000 000 000 000 000 000 000 00 35 35
35 (14)
(2) (1)
0 tiên: x a 35
a x
1 z5
z 1 0(0 1)
0
lý gói RREQ 00đầu 0 0 Nút 0 06 0 0 0Ở lần xử lý gói 35RREQ thứzz2, nút 3
00 00 00 00 00 00 00 00 0
(2)
1 x36 0 (15)
6Ở lần xử Ở lần lý Ở 0
gói xử 0 lý
RREQ 0 gói
0 0RREQ 0 0 thứ
0 0 2, nút 3
tlần Nút
6 xử 6 RREQ lần xửgói lýthứ gói 2,RREQ nút 3 thứ 2, bá nút 3 RREQ đến tất xcả
bá gói lý Ở góilần đến xử lý
tất cả RREQ
các nút phát 3 thứ quảng 2, nút 3 gói 369 các (15)
(2)
0
RREQ thứ 2,
átcng
các cảquảng
phát bá
cácphát
của nó,
quảng
phát góiquảng
quảng
điều
bá gói RREQ
RREQ
này bá được báđến
gói gói
RREQ
biểu tất
RREQ
đến
cảđến
nút
tất cả các
cácđến
tất
láng tất
cả cả của
các
giềng các nó, điều x37(2)
anày37
ađược37
biểu xz(1)7 1(1 0) 1
(16)
uảng bá gói Ở lần RREQ xử lý đến góinó, tất
RREQ cả các
thứ 2, nút biểu
3 phát 9
z 1
ulángnút giềngláng của giềng nó, của
điều này điềuđược nàybiểu được x37(2)
a37 a37 xz(1)7 1(1 0) 1 (16)
ợc ểu
ag trận biểu (1) nút
nút
quảng
X láng
[ x bá
(1)
] láng
giềng
gói với giềng
RREQ của
các của
nó,
phần
đến nó,
điều tất điều
này
diễn
cả này
được
các bởi được
nútmabiểu biểu
trận
láng X (2)
[ x (2)
] với các phần X
giềng của ijnó,99điều này(2) được biểu ij 99
z
9
1
n giềng
diễn bởi của ma nó,
(2) trận điều (2)X này được
(2) biểu
với diễnphần
các bởi ma
cnầnphần
ởi xác
bởi diễn
mađịnh
ma diễn
trậntheo
trận
bởi [ma
X (2) (4(4)
X bởi
xij(2) ]9như
[ ma
x
trận ij 9X
]
với
trận
(2)
9 [x
sau:
[
vớix
các
Xij(2) ]
các
(2)9
ijphần
[
9
x phần
]99ij với
(2)
tử
]
x
với
99(2)các phần
được
các
xác
phần
định theo
x (2)
38
(4(4)
a 38
a
như
38
9sau:
x z
(1)
8 0(0 1) 0 (17) X
trận với các phần tử được xác z 1 (1)
9 ij
x38 a38 a38 xz8 0(0 1) 0
(2)
(17)
(2)
xsau: tửđịnh
được xij(2)
xác được
theo định (2)(4) xác theonhư định sau:
(4(4) theo như (4(4) sau: như sau:
tử xijtửđược
(2) xij được xác xác định
định theo theo
(4(4) (4(4)
như như
sau: sau: z 1
ij
ược xác định theo (4(4) như sau: 9
)
neáu i m1 x (1)
ij
x (2)
39
neá ua i
39
3a 39
x
z 1 (1)
9
(1)
z 9 0(0 0) 0 (18)
(1)
(1) 9xij(1)(0) xijx (1) x (1)neáu i 3 neáneá u i 3 x39 a39 a39 xz9 0(0 0) 0 (18)
(2)
u ineá
3uxi(2) 3
9
aijx ij zj 9
x neá u ij ineá um ij
i 3 (5) a a xzj(1) neáu i 3 z1 (9) K
19
z 1 Từđó Từ ta đócó:
ij ij ij
)(2) z1 xij(2)9(2)
a(2)
x a(1)ij 9x (1) 9 neá 3
(1)u i
(9) ta có:
x
5)
ij
(5)
aij a
x
x
ij x(1)ijneá
aij aij
ij
ij
a
ijuneá
zj a a
jijuijszi
1 ij3 zj
neá
a u
zj
xi
(1) 3
x
zj (9) neá
u ineá
(9)
u
3 i 3 0 (9) (9) Từ đó taneácó: u j 6
K
thấy
zjz1
0 z1 z1
0 0 0 0 0 0 0 0 0
0 z 1
0
neáu j 6
0 neáu j 6 neáu jneá
thấy
nút
0
neáu j 6 6u j 6 00 00 00 00 00 00 00 00 00
vì theo (3(3) m2 = 3. Từ (9(9) 1 ta0 xác
0 0 0(2) 0 00định
00 00 01 00 00 nút
đượ
vì theom2(3(3) m2 =(9(9) 3. Từta (9(9) được ta xác các địnhphần tử của ma trận X như
heo
0 (3(3) vì theo
vìvìtheo =neá3.
theo
(3(3) (3) i Từ
u (3(3) m 62 =m3. 2. = Từ
Từ xác
3.(9) Từta
(9(9) định
(9(9)
xácta (2) xác
định ta xácđịnh
được định 10 00 00 00 00 00 10 00 00
(3(3) được m = 3. Từ
2 các phần tử của ma(2)trận (9(9) ta xác định Xsau: (2) như
đượ
RRE
ợc
các phần
các
được được
9 phần các tửtửcác của
phần củaphần mama
tử trận
tử(2) của
trận
của X sau:
ma ma như
như
trận trận
X Xnhư
(2)
như X (2) 00 00 00 00 00 00 00 00 00 (19)
ác phần
:aij asau: tử0 của
ij sau: sau:
neáuma i 6trận X(6) như 0 0 1 0 1 0 0 1 0 RRE
) z 1
- Khi j = 6, xij = 0. X 0 0 0 0 0 0 0 0 0 (19)
( 2 ) (2)
trìn
0 (6) j- = Khi (j2)= 6, xij = 0. 00 (10)0 10 00 10 00 00 10 00
( 2)
Khi
6) 6, - x =
neá
Khi 0.
u j j = 6(6,
2) x ( 2) = 0. trình
j = 6, -xij(2)Khi = 0.j = 6, xij =ij0. (2) - (1) Khi i ≠ m2 i ≠ 3, xij =00xij 00. 00 00 00 00 00 00 00 7
ij ( 2)
i-=≠ Khi
mvà i (0)
≠i m ≠=m 23,x (i2) ≠=3,x (1x)ij. ( 2)= x(ij2) (1.)
)Khi - 2- Khi
Khi i ≠ i ≠ m
ij 2i(1≠ 3,i
ij ≠ 3, = = . . 0 00 00 00 00 00 00 00 00 quả7
(1)
m 6 X
i ≠ 1m2 i ≠ 3, xij = xij . ([0].
2 2
) Từ ) (6(6) x ij -
x ij x ijKhi x ij i = m 2 i = 3: 0
6)
có:
Khi i- = Khi
m i = i m
= 2 3: i = 3: 0 0 0 0 0 0 0 0 0
quả
- Khi i 2= m2i i = 3:
ừi =
(6) (6(6)m2- Khi i =i3: =m = 3: Hoàn toàn tương tự, ta xác định được ma thuậ
2 9
] [0x0(2)1 0a91 0a(1) 01 0]9x (1) 9(7)
9
(2)
x31
a31 a31 xz(1)
z 1 Hoàn
1
1(1 0) 1
toàn tương
(10)
tự, ta xác thuậ
[a(2)
1(1
0) 1 (10) trận biểu diễn quá trình xửđịnh được
lý gói ma
RREQ bày
6j
x31 a31 a3131 x (1)
9 (2)
x
31
a
) a31 a31 31xz1z13131 1(1
xz131aa 1(1
(2)
a
3131z10)
z
0) x 1(1)1(1
1 (1)
x (10)
1(10) 10) 1 (10) (10)
7) (7)
z1 z1 (10)
31 z1
1 z1
9 trận của biểutất cảdiễn các quá nút trình
(sau 8xửlần
lý chuyển
gói RREQ
tiếp bày
mô
(7(7) ta có:
z 1
16 TẠP CHÍ KHOA
9
9 HỌC
x (2)
32
a a
32 32
x (1)
z2 0(0 0) 0 (11)
x (2) a QUẢN LÝ VÀ CÔNG z 1 của tất cả các nhưnút (sau 8 lần chuyển tiếp mô
(2)
x032 0a320 a32 3290
(2)
x32x(1)a320x
32
(2)
x
0
a
(1) 9x
32 a 0 0(0
0
a
(1) 9 NGHỆ
z
2
(1)
0)
z132 xz2 z20(0x
0(0
0
(1)
0) 0
(11)
0(0
0) 0 0)
(11)
0
(11)(11)
gói RREQ) sau: ma
a32 a32 z2a3232
z 1 0(0 0) 0
32
(11)
0 0 0 z01 z02 0 0 0z1 z1 (2) gói RREQ) như sau: ma
sử td
x33 0 (12)
- Hoàn toàn tương tự, ta xác định được TÀI LIỆU THAM KHẢO:
ma trận biểu diễn quá trình xử lý gói RREQ
0 0 0 1tất0 cả0 các
của 0 0 (sau
0 [1] C. T. Cuong, V. T. Tu, and N. T. Hai,
0 0 0 1 0 0 nút 0 0 08 lần chuyển tiếp gói “MAR-AODV: Innovative Routing Algorithm
0 0 0 00 00 như
RREQ) 0 1sau:
0 00 00 0 0 0
0 0 0 0 0 0 0 0 0 in MANET Based on Mobile Agent,” in
15) 0 0 00 00 0 00 0001 000 1010 0 0 000 000 00 00
5) 1 0 0 0 0 0 1 0 0 International Conference on Advanced
0 0 0 10 00 0 00 0 00 0 000 0000 0 01 0 00 0 00 0 0 0 0 Information Networking and Applications
0 0 0 0 0 0 0 0 0
08)6) 0 0 00 00 10 00 00 00 0 (20) 00 10 0 0 Workshops, (Barcelona, Spain), 2013.
0 1 0 0 00 00 0 1 (20)
(8) 0 0 0 0 0
0 0
6) 0 00 0 (20)
0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0
X 0 0 0 0
0 0 0 0 0
[2] H. Naanani, H. Mouncif, and M.
0 0X (8)1 0 0 1 0 0 0 0 0 1 0 00 0 0 0
0 0 0 X 0(8) (20)
0 00 0 10 0 00 0 10 001 0 0 0 1 0 0 0 0 (20) Rachik, “Improved AODV Routing Protocol for
0 0 0 0 0 0 0 0 1
07) 1 0 00 00 00 00 100 000 10 00 01 1 0 MANETs,” International Journal of Engineering
7) 0 1 0 00 00 01 00 01 00 0 1 0 Research & Technology (IJERT), vol. 3, no. 7,
0 0 0 00 10 00 00 00 00 0 00 00 0 1
0 0 0 0 0 00 0 0010 00 0 000 00 0 0 00 0 00 0 0 1 0 pp. 1698–1701, 2014.
0 1(k) 0 0 0 0 0 0 0
uả8)quảcủa ma trận X 0 ở0(k)
0 0trận
(20(20)
0 0 0cho 0 0 0 [3] Le Huu Binh, Vo Thanh Tu, “QTA-
ết
8) Kết của quả macủa
ma X 0ở
0 0trận X0(20(20)
(k) 0 0 cho
ở (20(20)0 0cho
AODV: An Improved Routing Algorithm to
g, nút 9 nhận Kết được gói
quả RREQ Xtừ
rằng,rằng,
nút 9nút
Kết quả của
nhận được
của ma
magói trận
trận RREQ (k)
ở từ(20(20)
(20) cho cho
thấy Kết quả 9của nhận ma đượctrận gói ởở(20(20)
X(k) RREQ từ cho thấy Guarantee Quality of Transmission for Mobile
= 1), gói RREQ này nút 7 nhận
rằng, nút 9 nhận được gói RREQ từ nút 7 Ad Hoc Networks using Cross-Layer Model”,
79nút
(x797 =thấy
1), rằng,
(x79 rằng,gói RREQ
= 1),, góigói
nút 9 này
RREQ
nhậnnút
này
được7 nhận
nútgói
gói RREQ từ
thấy nút RREQ9 nhậnnày được nút 7 7nhận
nhận
RREQ được từ từ Journal of Communications, Vol 13, No. 7,
nút 3nút (x377 =(x 1),= nút 3 nhận gói 2018, pp.338-349.
cđượctừ nútnút 33 (x3779 = 1),, gói nút
nút 3RREQ
3nút nhận
nhận này
gói gói nút 7 này
RREQ nhận
từ 7nút
nút (x793 =(x1), 37 = gói 1),RREQ 3nàynhận nútgói 7 nhận từ
ày từ nút 6 (x63 = 1).. Như vậy, vậy, lộlộ trình từ 6 đến 9 [4] A. Lee and I. Ra, “A Queuing Network
Q nàyđượcđược
từ từ nút (x6363là = (x = 1),vậy, nút lộ3 nhận gói
RREQ đượcnàynút từtừ 6nút
xác nút
định 3 (x663
1).
37
37 Như
→ == 31).→Như
1), → vậy,
7nút 3 Kết
9. lộquả
nhận góinày Model Based on Ad Hoc Routing Networks
6 đến trùng9
RREQđược hợp xác
nàyvơi định
kết
từxác là
quả
nútđịnh 6
6 (xkhám 3 pháNhư lộ trình
vậy,theo
9)từ 6RREQ
trình đến6 9đến
từ được
này 9 từ
đượcnút 6
xác (x là==61).
63
định
1).
là 3
Như
6 vậy,
3
lộ
lộ
for Multimedia Communications,” Applied
9)
9. Kếtđược
nguyên lý của thuật toán định tuyến DSR, đã
quả này trùng
63 Mathematics & Information Sciences, vol. 6,
9. trình
Kết từ
quả 6này
trình đến
bàytrùng 9ởhợpđược
ví hợp
vơi
dụ xác
kếtđịnh
vơi
Hình kết
1 của là 6phần
3
7 trình
9. từKết6 đếnquả 9này được trùng xáchợp định vơi 6 3 II.
làkết no. 1, pp. 271S-283S, 2012.
m phá Như lộ trình
7lộ
vậy,theomô hình
9.trậnKết nguyênquả
giảilýtích
nàynhư của sử dụng phương
trùng hợpởvơi kết
khám phá
pháp
7
quả khám ma trình
phá9.lộKết theo
nhị
trình nguyên
phân
quảtheo nàynguyên lý
trùngmô của lýtảcủa
hợp vơitrên
kếtcó
[5] S. B. Ch., K. G. Rao, B. B. Rao, and K.
n địnhthể tuyến DSR, đã Chandan, “An AnalyticalModel for Evaluating
tthuật
toánquảquả
định sử
khám dụng
tuyến phá cho
DSR, lộ được
việc
trình
đã được
trình
xác
theođịnh nguyên
trình lộ trình theo
lý của Routing Performance of AODV Protocol
toán khámđịnh tuyến
phá lộ DSR,
trình
nguyên lý của giao thức định tuyến DSR. đã
theo được
nguyên trìnhlý của
dụ Hình 1 của phần II. Như vậy, for MANETs with Finite Buffer Capacity,”
ma
ởbàyví ởdụthuật
víHình
dụ
toán1 của
Hình
định
1 phần
của
tuyến II. DSR,
phần NhưII. Như
đã được trình
vậy, vậy, trình
ma thuật toán
IV. KẾT định
LUẬN tuyến DSR, đã được International Journal of Applied Engineering
giải tích
bàyTrongsử dụng
ở ví sử dụ Hìnhphương 1phương pháp
của phần II.xuất
Như vậy,
EQ
hình giải tích dụng giảpháp
Research, vol. 10, no. 17, pp. 37960–37972,
Qmô hìnhbày ởgiảiví dụtích
bài Hìnhsử dụng
báo 1này,củatác phương
phần II. pháp
đề Nhưmột vậy,mô 2015.
nhị phân hình như mô
giảinhưtích tảtoánở trênhọc có sử thể
dụng lý thuyết ma
ếp nhị
rận môphân hình giảimô tích
tảmô ởsửtrên dụng có phương
thể pháp
ma
p trận môtrậnnhị đểphân
hình giảinhư
khảo tíchgiao
sát sử tảthức
dụngở trên cótuyến
phương
định thểpháp
nguồn [6] S. Mora and J. Vera, "RDSNET: A
cho việcma việc xác nhị
trận địnhphân lộ trình
như theotả ở trên có thể
mô
ụngdụng
sử cho
trong
cho mạng xác
việc
ma trận nhị phân như mô
tùyđịnh
xác biến lộ
định ditrình
động. theo
lộ tảtrình Mô hình được
ở trên theocó thể proposal for control architecture for software
ý của giao thức định tuyến DSR. lộ trình truyền
đề xuất cho phép xác định tập defined MANETs," International Journal of
yên sử
lý dữ dụng
củaliệu giao cho
thức việc
định xác định
tuyến DSR. lộnày trình theo
nguyên sử lýdụng củakhi giao
cho biếtviệc tôpôxác
thức mạng,
định điều
tuyến
định lộDSR.
trình cho phép
theo Engineering and Technology (IJET), vol. 10,
đánh
nguyên giálýhiệu củanăng giaocủa thức mạngđịnhtùy tuyếnbiếnDSR.
di động no. 3, pp.816-827, 2018.
T LUẬN nguyên
khi sử lý
dụng của giao
giao thứcthức định định tuyến
tuyến DSR.DSR.Trong
KẾTKẾT
IV. LUẬN LUẬN
hướng nghiên cứu tiếp theo, tác giả tiếp tục [7] A. Varga, OMNeT++ Discrete Event
bài báo IV.này,
phát KẾT
triểntácmô LUẬN
giảhình đề để xuất phân mộttích một số tham Simulation System, Release 4.6. 2015.
rong IV.
bài báoKẾT này, LUẬN tác giả đề xuất một [Online]. Available: http://www.omnetpp.org.
Trong bài báo
số hiệu năngnày, khác tácnhư giả xác đề xuấtsuất một hủy bỏ gói
giải dữ tíchliệu,toán học sử dụng lý
hình
mô hình giảiTronggiải
bài
tíchđộtích trễ,báo
toán họcnày,
thông
toán sử tác
lượng dụng giả
mạng đềkhi
lý xuất
sử một
dụng [8] DARPA, The Network Simulator NS2.
Trong
giao thứcbài định báo tuyếnnày,học tác sử
nguồn giả dụng
đề xuất
động.
lý một
mô hình giải tích toán học sử dụng lý [Online]. Available: http://www.isi.edu.
mô hình giải tích toán học sử dụng lý
TẠP CHÍ KHOA HỌC 17
QUẢN LÝ VÀ CÔNG NGHỆ
nguon tai.lieu . vn