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.
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 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](https://s1.tailieuvn.net/xb70nb5jd4llaq8g/thumb/2021/11/22/khao-sat-thuat-toan-dinh-tuyen-nguon-trong-mang-tuy-bien-di_o9SP5uCxVo.jpg)
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 ... ừ (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:
khao_sat_thuat_toan_dinh_tuyen_nguon_trong_mang_tuy_bien_di.pdf