Binary Search (BS)



 

    Mô tả ví dụ thuật toán BS trong giải quyết xung đột:

    Xét 4 thẻ trong vùng năng lượng của bộ đọc với độ dài ID của mỗi thẻ là 8 bit (do đó ID của mỗi thẻ nằm trong dãy  0000 0000 – 1111 1111) và giá trị như hình.

    Giả sử bộ đọc hỗ trợ lệnh REQUEST(?x), 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, ở đây các thẻ phải hỗ trợ một phép toán đơn giản là so sánh để khi nhận được lệnh REQUEST, nếu ? là dấu:

  • ≤: ID của thẻ nào ≤ x thì thẻ đó sẽ trả lời lại bộ đọc với ID của mình.
  • ≥: ID của thẻ nào ≥ x thì thẻ đó sẽ trả lời lại bộ đọc với ID của mình.

untitled

Hình 1: ID của 4-Tag

    Ban đầu, bộ đọc gửi lệnh REQUEST (≤1111 1111). Do (1111  1111)  là giá trị lớn nhất trong miền giá trị ID, nên kết quả của lệnh này là tất cả các thẻ đều phúc đáp lại cho bộ đọc.

    Ở chu kỳ 1, dữ liệu nhận tại bộ đọc bị xung đột tại các bit 0, bit 4, bit 6. Trong đó bit 6 là bit có giá trị lớn nhất, tức có ít nhất một thẻ mà ID ≤ (1011 1111)b và cũng có ít nhất một thẻ mà ID ≥  (1100  0000)b.  Từ đó, ta có quy tắc hình thành tham số của lệnh cho chu kỳ tiếp theo:

  • REQUEST (≤ X…) với bit (X) = 0, bit (0 đến X-1) = 1
  • REQUEST (≥ X…) với bit (X) = 1, bit (0 đến X-1) = 0

Trong đó, X là bit xung đột mang giá trị lớn nhất trong chu kỳ hiện tại.

1

Hình 2: Các chu kỳ

    Đầu chu kỳ 2, bộ đọc gửi lệnh REQUEST (≤1011  1111) (theo quy tắc trên), 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 0 và 4.

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

untitled

Hình 3: Chu kỳ 4

 

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

3

Hình 4: Mô tả các chu kỳ qua Binary Search Tree

    Đầu chu kỳ 7, bộ đọc gửi lệnh REQUEST (≥1100  0000) (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à ID của thẻ 4: (1110 0011)b.

untitled

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

Ví dụ:

2

Hình 6: Lưu đồ thuật toán

Đây là sơ đồ khối biểu diễn thuật toán.

Ở đây ta có 4 Tag với độ dài ID của mỗi Tag là 3bits :

capture

 

Bước 1: Khởi tạo ID = 111, so sánh ID của Tag với ID vừa khởi tạo và tất cả các thẻ đều trả lời lại do ID đều <=111

Bước 2: Cả 3bit đều xung đột trong đó bit 2 có trọng số lớn nhất. Theo quy tắc ở VD trên ta gán ID mới ID = 011 và so sánh ID của các thẻ với ID này ta đc ID của Tag 1 và Tag 2

Bước 3: 2 Tag này lại xung đột tại bit 0, gán ID = 010, so sánh, nhận đc Tag 1.

Bước 4: Ta lặp lại thuật toán từ B1 với 3 Tag còn lại cho đến khi nhận dạng đc hết.

.

/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: