Dynamic Binary Search (DBS)



.

Thuật toán:

     Trong thuật toán BT mô tả ở trên, mỗi lần bộ đọc gửi điều kiện tìm kiếm cho thẻ và mỗi lần thẻ trả lời ID lại cho bộ đọc, đều phải truyền đủ n bit của ID. Trong VD trên là 8 bit, thực tế có những hệ thống mà ID của thẻ lên đến 10 Bytes do đó cần một số lượng lớn dữ liệu đc truyền nhận trong suốt quá trình giải quyết xung đột thẻ.

     X: là vị trí của bit xung đột mang giá trị lớn nhất ở chu kỳ trước, ở chu kỳ hiện tại ta có nhận xét:

untitled

Hình 1: Dữ liệu dư thừa khi độ dài ID lớn <32 bits>

.

  • Bộ đọc gửi REQUEST với tham số 10110  111…1111, trong đó bit X đc thay bởi giá trị 0, các bit từ  (X-1)…0 đc thay bởi dãy giá trị 1 tương ứng. Khi nhận đc tham số này, các thẻ chỉ cần so khớp 5 bit 10110 với 5 bit tương ứng trong ID của mình, dãy bit  111…1111  là dư thừa.

                  = >  dãy bit (X-1)…0 là dư thừa trong REQUEST.

  • Nếu kết quả so khớp thành công, các thẻ sẽ trả lời toàn bộ ID của mình cho bộ đọc. Bộ đọc lúc này chỉ quan tâm đến dãy bit 011…1011, 5 bit 10110 bộ đọc đã biết.

                  = >  dãy bit N…X là dư thừa trong trả lời của các thẻ.

Do đó, thuật toán DBT đc đề xuất để tối ưu hóa lượng dữ liệu truyền nhận trên kênh truyền so với thuật toán BT, chỉ dữ liệu cần thiết mới đc gửi.

Ví dụ:

Xét 4 Tag như trong thuật toán BS:

untitled

.

Bộ đọc hỗ trợ lệnh REQUEST với 2 tham số:

  • NVB <number of valid bits> : số lượng bit prefix theo sau
  • Prefix: dữ liệu trước khi xảy ra xung đột kết hợp với bit lựa chọn: 0 hoặc 1

Tại đầu mỗi chu kỳ, bộ đọc sẽ phát lệnh này đến các thẻ tồn tại trong vùng năng lượng, các thẻ  phải hỗ trợ phép so sánh để khi nhận đc lệnh REQUEST:  nếu một thẻ so khớp NVB bit prefix với  ID của mình thành công, phần còn lại của ID sẽ đc trả lời lại cho bộ đọc.

Ban đầu, bộ đọc gửi lệnh REQUEST với NVB=0, kết quả của lệnh này là tất cả các thẻ đều hồi đáp lại cho bộ đọc. Dữ liệu nhận ở chu kỳ 1 bị xung đột tại bit lớn nhất là 6.

hieuunganh-com_584abf8d345dd

Hình 2: Chu kỳ 1 Dynamic BT

.

     Đầu chu kỳ 2, bộ đọc gửi lệnh REQUEST với NVB=2 và prefix=10, các thẻ 1, 2 và 3 trả lời với kết quả nhận tại bộ đọc xung đột tại bit lớn nhất là 4.

hieuunganh-com_584ac09a4c228

Hình 3: Chu kỳ 2

.

     Đầu chu kỳ 3, bộ đọc gửi lệnh REQUEST với NVB=4 và prefix=1010, lúc này dữ liệu nhận tại bộ đọc ko bị xung đột và đó chính là phần còn lại của ID của thẻ 2: 0011b.

untitled

Hình 4: Chu kỳ 3

.

untitled

Hình 5: Cấu trúc Dynamic Binary Tree

.

    Đầu chu kỳ 4, bộ đọc gửi lệnh REQUEST với NVB=4 và prefix=1011  (lựa chọn còn lại so với chu kỳ 3), các thẻ 1 và 3 trả lời với kết quả nhận tại bộ đọc xung đột tại bit 0. Do đây là bit cuối cùng trong ID nên chắc chắn có 2 thẻ với ID lần lượt là 1011 0010b, 1011 0011b sẽ được xác định ở chu kỳ 5 và 6.

    Đầu chu kỳ 7, bộ đọc gửi lệnh REQUEST với NVB=2 và prefix=11  (lựa chọn còn lại so với chu kỳ  2), lúc này dữ liệu nhận tại bộ đọc ko bị xung đột và đó là phần còn lại của ID của thẻ 4: 10 0011b.

.

/sangnx.bkfet

.


Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: