ĐÁNH GIÁ CÁC GIAO THỨC CÂY TRUY VẤN DỰA TRÊN TRI THỨC VỚI CÁC PHÂN BỐ THẺ RFID KHÁC NHAU

Nguyễn Đức Nhật Quang và CS. Tập 134, Số 2A, 2025 116 8. elseif readable then // Chỉ một thẻ trả lời 9. Retrieve the tag ID 10. end Trên thực tế, HQT mô hình hóa bài toán chống xung đột dựa trên tri thức như một bài toán phân loại dữ liệu. Giao thức sử dụng entropy và thuật toán ID3 để xây dựng cây quyết định, trong đó bit truy vấn ở mỗi nút được chọn dựa trên độ lợi thông tin lớn nhất. Cây truy vấn heuristic được phát triển cho đến khi mỗi nhánh chỉ còn một thẻ. Trong quá trình nhận dạng, đầu đọc luôn chọn bit có entropy lớn nhất để truy vấn và lặp lại cho đến khi nhận dạng hết các thẻ xuất hiện. Giao thức QTKS Giao thức QTKS giả định đầu đọc có cơ sở dữ liệu chứa ID của toàn bộ các thẻ có thể có [13]. Trước tiên, dựa trên tập ID này, đầu đọc xây dựng một cây truy vấn dựa trên tri thức, gọi là k-tree. Đây là cây nhị phân mà mỗi nút luôn có đúng hai nút con, trong đó mỗi nút lá tương ứng với một thẻ tiềm năng nhằm tránh các xung đột không cần thiết và giảm các khe nhàn rỗi. Trong giai đoạn nhận dạng, đầu đọc sử dụng k-tree để sinh ra các truy vấn dạng chuỗi bit thích hợp, từ đó xác định tất cả các thẻ xuất hiện trong vùng đọc. QTKS áp dụng thêm hai kỹ thuật: (i) rút gọn để lược bỏ các truy vấn dư thừa trên k-tree, và (ii) phân giải cặp đôi, cho phép truyền đồng thời hai ID trong cùng một khe và bỏ qua các truy vấn dư thừa khi chỉ còn hai thẻ có thể. Nhờ vậy, QTKS rút ngắn đáng kể thời gian nhận dạng so với KQT và HQT. Thuật toán QTKS được minh họa trong Thuật toán 4; ngoài ra trong phiên bản mở rộng được sử dụng trong nghiên cứu này,

thuật toán QTKS được bổ sung thêm một bước ước lượng số thẻ (Tag Estimation) tại Dòng 7–9 của quá trình nhận dạng. Bước ước lượng số thẻ dựa trên số khe xung đột/nhàn rỗi trong các truy vấn gần nhất để ước lượng nhanh số thẻ đang hoạt động. Thông tin ước lượng này được dùng để điều chỉnh mức phân tách hoặc chiến lược chia nhánh, giúp giảm các truy vấn không cần thiết khi số thẻ thực tế nhỏ hơn tập thẻ tiềm năng. Giao thức QTKS có tích hợp bước ước lượng số thẻ này được ký hiệu là QTKS_TE (QTKS with Tag Estimation). Đây là một cải tiến nhỏ nhưng mang tính thực tiễn, nhằm nâng cao hiệu suất trong các môi trường có số thẻ biến động hoặc phân bố không đồng nhất. Thuật toán 4. QTKS và QTKS_TE Input: Các thẻ có thể trong cơ sở dữ liệu; Các thẻ xuất hiện trong vùng đọc; Output: Cây k-tree T đã được xây dựng; Tập các ID thẻ được nhận dạng trong vùng đọc; reader procedure k-tree construction procedure 1. T = null; dif_t = null