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

12 TẠP CHÍ KHOA HỌC QUẢN LÝ VÀ CÔNG NGHỆ KHẢO SÁT THUẬT TOÁN ĐỊNH TUYẾN NGUỒN TRONG MẠNG TÙY BIẾN DI ĐỘNG SỬ DỤNG MÔ HÌNH GIẢI TÍCH 1. Lê Hữu Bình Khoa Công nghệ thông tin - Truyền thông, Trường Cao đẳng Công nghiệp Huế 70 Nguyễn Huệ, Phường Vĩnh Ninh, Thành phố Huế Email: lhbinh@hueic.edu.vn; 2. Lê Đức Huy Trường Đại học Công nghệ và Quản lý Hữu Nghị Email: leduchuy2307@gmail.com; Tóm tắt – Để có cơ sở cho việc đánh giá hiệu quả thực thi của các giao thức định tuyến trong mạng tùy biến di động, việc nghiên cứu các mô hình phân tích nguyên lý hoạt động của các thuật toán định tuyến là điều cần thiết. Trong bài báo này, tác giả đề xuất một mô hình giải tích toán học sử dụng lý thuyết ma trận để khảo sát giao thức định tuyến nguồn trong mạng tùy biến di động. Mô hình được đề xuất cho phép xác định tập lộ trình truyền dữ liệu khi biết tôpô mạng. Từ khóa: Mạng tùy biến, Định tuyến nguồn, mô hình giải tích. I. GIỚI THIỆU Ngày nay, các ứng dụng trên các thiết bị di động ngày một gia tăng. Để đáp ứng nhu cầu này, việc nghiên cứu nâng cao hiệu năng mạng tùy biến di động là điều hết sức cần thiết. Điều này cũng đã được nhiều nhóm nghiên cứu trong nước cũng như trên thế giới quan tâm thực hiện trong thời gian gần đây. Các hướng nghiên cứu đã được triển khai phổ biến như cải tiến các giao thức định tuyến trong mạng tùy biến di động [1], [2], nâng cao chất lượng truyền dẫn trên các lộ trình truyền dữ liệu [3], cải tiến mô hình mạng sử dụng các công nghệ mới [6]. Để đánh giá hiệu quả thực thi của các giao thức điều khiển được đề xuất, chúng ta có thể sử dụng mô hình mô phỏng, mô hình giải tích toán học hoặc thực nghiệm trên các mô hình mạng thực. Trong các phương pháp đó, phương pháp mô phỏng đang được sử dụng phổ biến hiện nay. Với phương pháp này, chúng ta có thể sử dụng các phần mềm 13TẠP CHÍ KHOA HỌC QUẢN LÝ VÀ CÔNG NGHỆ mô phỏng đang được sử dụng phổ biến hiện nay như OMNeT++ [7], NS-2 [8], OPNET và một số phần mềm mô phỏng mạng khác. Phương pháp mô phỏng đã được các nhóm tác giả trong [1], [3] sử dụng để đánh giá hiệu quả thực thi của các giao thức được đề xuất. Ưu điểm của phương pháp này là chỉ thực thi trên máy tính và hệ thống phần mềm, nên việc triển khai tương đối thuận lợi. Tuy nhiên, phương pháp này cũng có nhược điểm là kết quả mô phỏng thường có sai số so với thực tế. Ngoài phương pháp mô phỏng, phương pháp sử dụng mô hình giải tích toán học cũng đã được nhiều nhóm nghiên cứu triển khai. Phương pháp này thường được thực hiện bằng cách sử dụng lý thuyết hàng đợi, lý thuyết xác suất thống kê, mô hình phát sinh lưu lượng trong mạng viễn thông để mô hình hóa một hệ thống mạng. Trong [4], mô hình mạng hàng đợi đã được sử dụng để phân tích mạng không dây tùy biến. Nhóm tác giả trong [5] đã sử dụng nguyên lý hàng đợi M/M/1/K để phân tích hiệu năng của giao thức định tuyến AODV trong mạng tùy biến di động. Trong bài báo này, chúng tôi trình bày một mô hình giải tích được đề xuất cho việc tìm tập lộ trình của giao thức định tuyến nguồn động (Dynamic Source Routing - DSR) trong mạng tùy biến di động. Dựa trên nguyên lý khám phá lộ trình của giao thức DSR, chúng tôi sử dụng các ma trận nhị phân để biểu diễn quá trình phát quảng bá gói RREQ. Từ giá trị thu được của ma trận nhị phân, chúng ta xác định được lộ trình truyền dữ liệu được khám phá bởi giao thức DSR. Các phần tiếp theo của bài báo được bố cục như sau: Phần II trình bày nguyên lý cơ bản của giao thức định tuyến DSR. Phần III là mô hình giải tích được đề xuất. Phần IV là kết luận và hướng phát triển tiếp theo. II. NGUYÊN LÝ CƠ BẢN CỦA GIAO THỨC ĐỊNH TUYẾN NGUỒN Định tuyến nguồn động (DSR) là một giao thức thuộc nhóm định tuyến theo yêu cầu (On-Demand Routing Protocol). Theo nguyên lý hoạt động của lớp giao thức định tuyến này, các lộ trình truyền dữ liệu sẽ được tạo ra khi có yêu cầu. Khi một nút yêu cầu một lộ trình mới để đến đích, nút đó phải khởi đầu một quá trình khám phá lộ trình (Route Discovery). Quá trình này sẽ kết thúc với một trong hai trường hợp. Một là tìm ra một lộ trình thỏa mãn các yêu cầu đề ra trước đó. Hai là quá thời gian cho phép nhưng không tìm được một lộ trình nào. Việc khám phá lộ trình mới bởi giao thức định tuyến DSR được khởi đầu bằng việc phát quảng bá gói yêu cầu lộ trình (RREQ) từ nút nguồn đến tất cả các nút láng giềng của nó. Tại các nút trung gian khi nhận được gói RREQ, nếu như trước đó gói RREQ này đã được nhận rồi thì nút đang xét hủy bỏ nó và không xử lý gì thêm. Ngược lại, lưu lộ trình ngược về nút nguồn vào bộ nhớ đệm của nút đang xét, sau đó kiểm tra xem trong bộ nhớ đệm của nó có đang tồn tại lộ trình khả thi đến nút đích hay không. Nếu có, nối lộ trình từ nút nguồn đến nút hiện tại với lộ trình từ nút hiện tại đến nút đích. Sau đó, tạo gói phản hồi lộ trình (RREP) để gửi thông tin về nút nguồn theo đường ngược. Trong trường hợp bộ nhớ đệm của nút trung gian đang xét không có lộ trình khả thi đến nút đích, nút đó tiếp tục phát quảng bá gói RREQ đến tất cả các nút láng giềng, ngoại trừ nút đã phát gói RREQ cho nó để tiếp tục quá trình khám phá lộ trình mới. Quá trình lặp lại cho đến khi tất cả các nút trong mạng đều nhận được gói RREQ, hoặc quá thời gian chờ cho phép. Trong trường hợp gói RREQ đến được nút đích, nghĩa là một lộ trình khả thi đã được tìm thấy, nút đích sẽ tạo gói phản hồi lộ trình (RREP) để gửi về nút nguồn theo đường ngược. Khi nút nguồn nhận được gói RREP, nó sẽ cập nhật thông tin lộ trình mới vào bộ nhớ đệm của nó. Lộ trình này được sử dụng cho việc truyền dữ liệu theo yêu cầu. 14 TẠP CHÍ KHOA HỌC QUẢN LÝ VÀ CÔNG NGHỆ trình này được sử dụng cho việc truyền dữ liệu theo yêu cầu. Hình 1. Sơ đồ khối chức năng của mô hình Để thấy rõ nguyên lý khám phá lộ trình mới theo giao thức DSR, tác giả xét một ví dụ như ở Hình 1Hình 1. Giả sử ở thời điểm hiện tại, bảng định tuyến của tất cả các nút đều rỗng. Xét trường hợp nút 6 muốn khám phá một lộ trình mới đến nút 9. Quá trình khám phá lộ trình được thức hiện theo các bước sau:  Bước 1: Nút nguồn (nút 6) tạo gói RREQ, phát quảng bá gói RREQ đến tất cả các nút láng giềng của nó là 3, 8 và 8.  Bước 2: Xử lý gói RREQ tại các nút nhận được gói này ở bước 1 (các nút 3, 5 và 8): Tại nút 3, do chưa nhận được gói RREQ này trước đó, đồng thời do trong bảng định tuyến hiện tại của nút 3 không có lộ trình khả thi đến đích (nút 9), nên nút 3 sẽ lưu trữ lộ trình ngược về nút nguồn (nút 6) vào bảng định tuyến của nó. Sau đó, tiếp tục phát quảng bá gói RREQ đến tất cả các nút láng giềng của nó, ngoại trừ nút 6 là nút đã gửi RREQ cho nút 3. Như vậy, nút 3 sẽ quảng bá gói RREQ đến các nút 1 và 7. Quá trình xảy ra hoàn toàn tương tự đối với nút 5 và nút 8.  Bước 3: Xử lý gói RREQ tại các nút nhận được gói này ở bước 2 (các nút 1, 2 và 7): Tại nút 1, khi nhận được gói RREQ từ nút 3, do chưa nhận được gói RREQ này trước đó, đồng thời do trong bảng định tuyến hiện tại của nút 1 không có lộ trình khả thi đến đích Hình 1. Sơ đồ khối chứ năng của mô hình Để thấy rõ nguyên lý khám phá lộ trình mới theo giao thức DSR, tác giả xét một ví dụ như ở Hình 1. Giả sử ở thời điểm hiện tại, bảng định tuyến của tất cả các nút đều rỗng. Xét trường hợp nút 6 muốn khám phá một lộ trình mới đến nút 9. Quá trình khám phá lộ trình được thức hiện theo các bước sau: • Bước 1: Nút nguồn (nút 6) tạo gói RREQ, phát quảng bá gói RREQ đến tất cả các nút láng giềng của nó là 3, 8 và 8. • Bước 2: Xử lý gói RREQ tại các nút nhận được gói này ở bước 1 (các nút 3, 5 và 8): Tại nút 3, do chưa nhận được gói RREQ này trước đó, đồng thời do trong bảng định tuyến hiện tại của nút 3 không có lộ trình khả thi đến đích (nút 9), nên nút 3 sẽ lưu trữ lộ trình ngược về nút nguồn (nút 6) vào bảng định tuyến của nó. Sau đó, tiếp tục phát quảng bá gói RREQ đến tất cả các nút láng giềng của nó, ngoại trừ nút 6 là nút đã gửi RREQ cho nút 3. Như vậy, nút 3 sẽ quảng bá gói RREQ đến các nút 1 và 7. Quá trình xảy ra hoàn toàn tương tự đối với nút 5 và nút 8. • Bước 3: Xử lý gói RREQ tại các nút nhận được gói này ở bước 2 (các nút 1, 2 và 7): Tại nút 1, khi nhận được gói RREQ từ nút 3, do chưa nhận được gói RREQ này trước đó, đồng thời do rong bảng đị tuyến hiện tại của nút 1 không có lộ trình khả thi đến đích (nút 9), nên nút 1 sẽ lưu trữ lộ trình ngược về nút nguồn (nút 6: 1 → 3 →6) vào bảng định tuyến của nó. Sau đó, tiếp tục phát quảng bá gói RREQ đến tất cả các nút láng giềng của nó, ngoại trừ nút 3 là nút đã gửi RREQ này cho nút 1. Như vậy, nút 1 sẽ quảng bá gói RREQ đến các nút 4 và 7. Sau đó, nút 1 cũng nhận được gói RREQ này từ nút 5 gửi đến (từ bước 2). Lúc này, do nút 1 đã nhận được gói RREQ này trước đó (từ nút 3 gửi đến), nên nút 1 sẽ xóa gói RREQ này. uá trình xảy ra hoàn toàn tương tự đối với nút 2 và nút 7. • Bước 4: Xử lý gói RREQ tại các nút nhận được gói này ở bước 3 (nút 4 và nút 9): Quá trình xử lý gói RREQ nhận được tại nút 4 hoàn toàn tương tự như đã mô tả ở các bước trên. Tại nút 9, vì đây là nút đích, ên khi nhận được gói RREQ, nút 9 sẽ tạo gói RREP và gửi phản hồi về nút nguồn theo đường ngược. Như vậy, thuật toán DSR đã tìm được lộ trình từ nút 6 đến nút 9 là 6 → 3 → 7 → 9. Lộ trình này đi qua ba bước truyền (hop). Trong trường hợp tìm thấy nhiều lộ trình, thuật toán DSR sẽ lựa chọn lộ trình có số bước truyền nhỏ nhất để sử dụng cho việc truyền dữ liệu. III. MÔ HÌNH GIẢI TÍCH XÁC ĐỊNH LỘ TRÌNH CỦA THUẬT TOÁN DSR Trong phần này, chúng tôi trình bày một mô hình giải tích được đề xuất cho việc tìm tập lộ trình của giao thức định tuyến DSR trong mạng tùy biến di động. Để phát biểu thuật toán DSR thành mô hình giải tích, chúng tôi định nghĩa các ký hiệu toán học như sau: Gọi n là tổng số nút mạng, (nút 9), nên nút 1 sẽ lưu trữ lộ trình ngược về nút nguồn (nút 6: 1  3  6) vào bảng định tuyến của nó. Sau đó, tiếp tục phát quảng bá gói RREQ đến tất cả các nút láng giềng của nó, ngoại trừ nút 3 là nút đã gửi RREQ này cho út 1. Như vậy, nút 1 sẽ quảng bá gói RREQ đến các nút 4 và 7. Sau đó, nút 1 cũng nhận được gói RREQ này từ nút 5 gửi đến (từ bước 2). Lúc này, do nút 1 đã nhận được gói RREQ này trước đó (từ nút 3 gửi đến), nên nút 1 sẽ xóa gói RREQ này. Quá trình xảy ra hoàn toàn tương tự đối với nút 2 và nút 7.  Bước 4: Xử lý gói RREQ tại các nút nhận được gói này ở bước 3 (nút 4 và nút 9): Quá trình xử lý gói RREQ nhận được tại nút 4 hoàn toàn tương tự như đã mô tả ở các bước trên. Tại nút 9, vì đây là nút đích, nên khi nhận được gói RREQ, nút 9 sẽ tạo gói RREP và gửi phản hồi về nút nguồn theo đường ngược. Như vậy, thuật toán DSR đã tìm được lộ trình từ nút 6 đến nút 9 là 6  3  7  9. Lộ trình này i qua ba bước truyền (hop). Trong trường hợp tìm thấy nhiều lộ trình, thuật toán DSR sẽ lựa chọn lộ trình có số bước truyền nhỏ nhất để sử dụng cho việc truyền dữ liệu. III. MÔ HÌNH GIẢI TÍCH XÁC ĐỊNH LỘ TRÌNH CỦA THUẬT TOÁN DSR Trong phần này, chúng tôi trình bày một mô hình giải tích được đề xuất ho việc tìm tập lộ trình của giao thức định tuyến DSR trong mạng tùy biến di động. Để phát biểu thuật toán DSR thành mô hình giải tích, chúng tôi địn nghĩa các ký hiệu toán học như sau: Gọi n là tổng số nút ạng, nnijaA  ][ là ma trận biểu diễn các nút láng giềng của nhau trong mạng, trong đó các phần tử aij được xác định như sau:     1 neáu nuùt laø laùng gieàng cuûa nuùt 0 trong tröôøng hôïp ngöôïc laïiij j i a (1) là ma trận biểu diễn các nút láng giềng của nhau 15TẠP CHÍ KHOA HỌC QUẢN LÝ VÀ CÔNG NGHỆ trong mạng, trong đó các phần tử (nút 9), nên nút 1 sẽ lưu trữ lộ trình ngược về nút nguồn (nút 6: 1  3  6) vào bảng định tuyến của nó. Sau đó, tiếp tục phát quảng bá gói RREQ đến tất cả các nút láng giềng của nó, ngoại trừ nút 3 là nút đã gửi RREQ này cho nút 1. Như vậy, nút 1 sẽ quảng bá gói RREQ đến các nút 4 và 7. Sau đó, nút 1 cũng nhận được gói RREQ này từ nút 5 gửi đến (từ bước 2). Lúc này, do nút 1 đã nhận được gói RREQ này trước đó (từ nút 3 gửi đến), nên nút 1 sẽ xóa gói RREQ này. Quá trình xảy ra hoàn toàn tương tự đối với nút 2 và nút 7.  Bước 4: Xử lý gói RREQ tại các nút nhận được gói này ở bước 3 (nút 4 và nút 9): Quá trình xử lý gói RREQ nhận được tại nút 4 hoàn toàn tương tự như đã mô tả ở các bước trên. Tại nút 9, vì đây là nút đích, nên khi nhận được gói RREQ, nút 9 sẽ tạo gói RREP và gửi phản hồi về nút nguồn theo đường ngược. Như vậy, thuật toán DSR đã tìm được lộ trình từ nút 6 đến nút 9 là 6  3  7  9. Lộ trình này đi qua ba bước truyền (hop). Trong trường hợp tìm thấy nhiều lộ trình, thuật toán DSR sẽ lựa chọn lộ trình có số bước truyền nhỏ nhất để sử dụng cho việc truyền dữ liệu. III. MÔ HÌNH GIẢI TÍCH XÁC ĐỊNH LỘ TRÌNH CỦA THUẬT TOÁN DSR Trong phần này, chúng tôi trình bày một mô hình giải tích được đề xuất cho việc tìm tập lộ trình của giao thức định tuyến DSR trong mạng tùy biến di động. Để phát biểu thuật toán DSR thành mô hình giải tích, chúng tôi định nghĩa các ký hiệu toán học như sau: Gọi n là tổng số nút mạng, nnijaA  ][ là ma trận biểu diễn các nút láng giềng của nhau r ng ạng, trong đó các phần tử aij được xác định như sau:     1 neáu nuùt laø laùng gieàng cuûa nuùt 0 trong tröôøng hôïp ngöôïc laïiij j i a (1) được xác định như sau: Ví dụ, xét trường hợp tôpô mạng ở Hình 1, ma trận biểu diễn các nút láng giềng của nhau trong tôpô này được xác định như sau: Để xác định thứ tự xử lý gói RREQ, chúng tôi định nghĩa ma trận Ví dụ, xét trường hợp tôpô mạng ở Hình 1Hình 1, ma trận biểu diễn các nút láng giềng của nhau trong tôpô này được xác định như sau:                                 001001000 000100010 100000101 010010100 000100011 100000011 001100001 010011000 001011100 99ij aA (2) Để xác định thứ tự xử lý gói RREQ, chúng ịnh nghĩa a trậ M = [mi]1(n- 1), trong đó các phần tử mi được xác định như sau: mi = u nghĩa là nút u xử lý gói RREQ ở lần thứ i đối với yêu cầu khám phá lộ trình từ nút s đến nút d. Ví dụ, xét trường hợp tôpô mạng ở Hình 1Hình 1 với yêu cầu khám phá lộ trình từ nút 6 đến nút 9. Khi đó, ma trận M được xác định như sau: M = [6 3 5 8 1 7 2 4 9] (3) Để biểu diễn quá trình xử lý gói RREQ trong mạng, chúng tôi định nghĩa ma trận  ( ) ( )[ ]k kij n nX x với các phần tử ( )kijx được xác định bởi: - Khi k = 0: X(k) = [0]. - Khi k > 0: các phần tử ( )kijx được xác định như sau:                      ( 1) ( ) ( 1) 1 neáu neáu 0 neáu k ij k n k k ij ij ij zj k z x i m x a a x i m j s (4) trong đó, aij là các phần tử của ma trận biễu diễn các nút láng giềng của nhau (ma trận A). Phép toán  trong công thức (4(4) là phép toán cộng modulo trong hệ nhị phân. Biểu thức này cho phép xác định điều kiện ràng buộc trong mỗi cột j của ma trận X(k) luôn luôn chỉ có một phần tử có giá trị bằng 1, có nghĩa là mỗi nút j trong mạng chỉ phát quảng bá gói RREQ một lần đối với mỗi yêu cầu khám phá lộ trình. Trở lại với ví dụ ở Hình 1, xét yêu cầu khám phá lộ trình mới từ nút 6 đến nút 9. Quá trình phát quảng bá gói RREQ để khám phá lộ trình này được biểu diễn bởi ma trân X(k) như sau: 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 tôi định nghĩa ma trận M = [mi]1(n- 1), trong đó các phần tử mi được xác định như sau: mi = u nghĩa là nút u xử lý gói RREQ ở lần thứ i đối với yêu cầu khám phá lộ trình từ nút s đến nút d. Ví dụ, xét trường hợp tôpô mạng ở Hình 1Hình 1 với yêu cầu khám phá lộ trình từ nút 6 đến nút 9. Khi đó, ma trận M được xác định như sau: M = [6 3 5 8 1 7 2 4 9] (3) Để biểu diễn quá trình xử lý gói RREQ trong mạng, chúng tôi định nghĩa ma trận  ( ) ( )[ ]k kij n nX x với các phần tử ( )kijx được xác định bởi: - Khi k = 0: X(k) = [0]. - Khi k > 0: các phần tử ( )kijx được xác định như sau:                      ( 1) ( ) ( 1) 1 neáu neáu 0 neáu k ij k n k k ij ij ij zj k z x i m x a a x i m j s (4) trong đó, aij là các phần tử của ma trận biễu diễn các nút láng giềng của nhau (ma trận A). Phép toán  trong công thức (4(4) là phép toán cộng modulo trong hệ nhị phân. Biểu thức này cho phép xác định điều kiện ràng buộc trong mỗi cột j của ma trận X(k) luôn luôn chỉ có một phần tử có giá trị bằng 1, có nghĩa là mỗi nút j trong mạng chỉ phát quảng bá gói RREQ một lần đối với mỗi yêu cầu khám phá lộ trình. Trở lại với ví dụ ở Hình 1, xét yêu cầu khám phá lộ trình mới từ nút 6 đến nút 9. Quá trình phát quảng bá gói RREQ để khám phá lộ trình này được biểu diễn bởi ma trân X(k) như sau: đó các phần tử 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 tôi định nghĩa ma trận M = [mi]1(n- 1), trong t mi được xác định như sau: mi = u nghĩa là nút u xử lý gói RREQ ở lần thứ i đối với yêu cầu khám phá lộ trình từ nút s đến nút d. Ví dụ, xét trường hợp tôpô mạng ở Hình 1Hình 1 với yêu cầu khám phá lộ trình từ nút 6 đến nút 9. Khi đó, ma trận M được xác định như sau: M = [6 3 5 8 1 7 2 4 9] (3) Để biểu diễn quá trình xử lý gói RREQ trong mạng, chúng tôi định nghĩa ma trận  ( ) ( )[ ]k kij n nX x với các phần tử ( )kijx được xác định bởi: - Khi k = 0: X(k) = [0]. - Khi k > 0: các phần tử ( )kijx được xác định như sau:                      ( 1) ( ) ( 1) 1 neáu neáu 0 neáu k ij k n k k ij ij ij zj k z x i m x a a x i m j s (4) trong đó, aij là các phần tử của ma trận biễu diễn các nút láng giềng của nhau (ma trận A). Phép toán  trong công thức (4(4) là phép toán cộng modulo trong hệ nhị phân. Biểu thức này cho phép xác định điều kiện ràng buộc trong mỗi cột j của ma trận X(k) luôn luôn chỉ có một phần tử có giá trị bằng 1, có nghĩa là mỗi nút j trong mạng chỉ phát quảng bá gói RREQ một lần đối với mỗi yêu cầu khám phá lộ trình. Trở lại với ví dụ ở Hình 1, xét yêu cầu khám phá lộ trình mới từ nút 6 đến nút 9. Quá trình phát quảng bá gói RREQ để khám phá lộ trình này được biểu diễn bởi ma trân X(k) như sau: c x ị như sau: 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 tôi định nghĩa ma trận 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