ĐÁ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 122 (a) (b) Hình 2. So sánh số khe nhàn rỗi của các thuật toán QT, KQT, HQT, QTKS và QTKS_TE: (a) phân bố đồng nhất; (b) phân bố không đồng nhất Đối với QTKS và QTKS_TE, khi số thẻ xuất hiện trong vùng đọc tăng, số khe nhàn rỗi giảm. Nguyên nhân là cây truy vấn được xây dựng sẵn từ cơ sở dữ liệu thẻ đã biết; nếu số thẻ cần truy vấn ít, quá trình duyệt cây có thể đi qua nhiều nút mà không gặp thẻ, tạo ra khe nhàn rỗi. Khi số thẻ xuất hiện tăng lên (tiệm cận số thẻ trong cơ sở dữ liệu dùng để xây cây), xác suất mỗi nhánh dẫn tới một thẻ được nhận dạng thành công cao hơn, do đó số khe nhàn rỗi giảm, như trong Hình 2. Trong trường hợp phân bố thẻ không đồng nhất, QTKS và QTKS_TE cho số khe nhàn rỗi xấp xỉ nhau. Việc QTKS_TE ước lượng được số thẻ thực tế không giúp giảm đáng kể số khe nhàn rỗi, bởi với dạng phân bố không đồng nhất được xem xét, thuật toán vẫn phải duyệt gần như toàn bộ cây để truy vấn hết toàn bộ thẻ. 3.3 So sánh hiệu suất truy vấn Hiệu suất truy vấn được xác định theo (1), tức là tỉ số giữa số khe thành công và tổng số khe cần thiết để truy vấn hết các thẻ trong vùng đọc. Hình 3 trình bày so sánh hiệu suất của các thuật toán QT, KQT, HQT, QTKS và QTKS_TE đối với hai dạng phân bố thẻ: đồng nhất (Hình 3(a)) và không đồng nhất (Hình 3(b)). Đối với QT, KQT và HQT, hiệu suất hầu như không thay đổi đáng kể khi số thẻ xuất hiện trong vùng đọc tăng. Nguyên nhân là KQT về bản chất chỉ thực hiện QT trên từng khoảng đã chia, nên hiệu suất của KQT chủ yếu phụ thuộc vào độ chính xác của việc chia khoảng, ít bị ảnh

hưởng bởi số thẻ cần truy vấn; do đó, hiệu suất của QT và KQT gần như không biến động khi số thẻ tăng. Với HQT, số khe nhàn rỗi gần như bằng 0, nên theo (1), việc số khe thành công và số khe xung đột cùng tăng khi số thẻ xuất hiện tăng cũng không làm cải thiện đáng kể hiệu suất truy vấn.