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

Chia sẻ: ViNeji2711 ViNeji2711 | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

36
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong bài viết 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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 ]nn 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ô ]nn là 1, mạng ở ma  (trận biểu diễn 1X( k1k) )  0[x(ijk( k)0) ]nn0 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  0aijcủa ở củatoán   1 1 trong   X DSR -định Khi [xij ]nthà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 99 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 00   k 0 này nhau ở trong láng bước trong giềng 3mạng, mạng, (nútcủa  trong4trong 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   1nhau 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 1X0 mạng ở   Ví (2) ( k ) dụ,  0( -  [x k )]n1n 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  z1tử 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 99  [ 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 00số 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 99 trận u0nuù 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 nnk[xij ma0A0 > ]n0: trận 0[các a 1]với n ij các nphầ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 0110đị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) 0aijmạng, 0nà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 a0ijláng [m (2)các ] phần neá i 1 (n-  u i tử (4(4)  m củacủ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 9giềng 9 của biễu diễntrong 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:1diễ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ử aijm  ij được k xác  ui (4) xác gói A Để a xác định định RREP như   và 1 1 thứ A  aij0ij99909  11 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). 0ijk1Phép 0aPhép i ij 1  phần 00: nút 1z toán x tử 1 ( kzj 110zj 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 0toá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 000đường110 11110 10001 00ma 1 1101trận 0 1 000010M 1neá=u 0[m  0ti j1laø nuù (n-định laù n g (4(4) gieà 0 0sau: như ( k định n g 1) là cuû  01thứcnhư phép nuù t i sau: toán cộng uxá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  001định 0 0 000 1phần 0 1nghĩa 1 0 01ma 1 aij011trậ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  100đó 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được00 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 01)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 000 001 000 000 100 1010 0101001 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ử00m1i1Để đượ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 999 111 10 001 001 010 00 00 0001 (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) xzjnútlà 0 1)láng ( krà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  aRREQijĐể như 0 asau:  0 11 m 0i 1=011u 00nghĩa 00 010làchúng 01nút 0trườ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ácz 1 bá a ở 1M 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 99 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ầuA). 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 1cá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 0chỉmột có một lần phần đốij đó, với phá lộ chúng chúngtôi 0tôi 1trình 1 định định 0 0 từ 101nghĩ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 1trong  (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 010từ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á 00đó 0 1các 0 0mạng 000ở 0i như 0100sau: 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ợp0tô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]1khá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 9bá 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 99mỗ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 im 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 đó,ijmỗilộ 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 ) ] nn 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 ]]nchú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. đượcsau: 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ìnhphá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  ( kij1) k và (2(2) ta có:  [ x (1) ]  xx ( k 1) ( k )  ijij n  neá neáuuiimmkk 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) )   aaijijaaijij 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) zz 11
 x  9     aij0ijaij ij z01 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) .  xij   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)  a31a31a31  a31   9  z  xz(1) 1 (1) xz1  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)  a32  a32 z 1  xz(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)x32 a a32a a 32  32  xz(1)2xz2  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)x34 a a34a a  xz(1)4xz 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 x35 (2) a a35a a  xz(1)5xz5 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ứzz2, 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ó,99điều này(2) được biểu ij 99   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 ]99ij với (2) tử ] x với 99(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 z1 (9)  K 19    z 1 Từđó Từ ta đócó: ij ij ij )(2)  z1 xij(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    ijuneá zj  a a jijuijszi   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 zjz1  0   z1 z1    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  ]  [0x0(2)1 0a91 0a(1) 01 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  31xz1z13131 1(1 xz131aa  1(1 (2)  a 3131z10) z   0) x 1(1)1(1 1 (1) x   (10) 1(10)  10)  1 (10) (10) 7) (7)       z1 z1 (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)a320x 32  (2)  x 0 a  (1)   9x 32 a 0  0(0 0 a  (1) 9 NGHỆ z 2   (1)  0)  z132 xz2   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    z2a3232 z 1   0(0  0) 0  32 (11) 0 0 0 z01 z02  0 0 0z1 z1  (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 000 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 00 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) 00 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 0X (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 00 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 00 00  0 1  0 0 0 0 0 00 0 0010 00 0 000 00 0 0 00 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Ệ