Improved Enhanced Binary Search (I-EBS)



.

    Thuật toán EBS cải tiến hơn bằng cách xác định hai Tag đồng thời khi chỉ có một bit xung đột đơn.

    So với BS và EBS, mục tiêu của nó là nâng cao tốc độ nhận dạng Tag khi xung đột xảy ra. Thuật toán này như BS nhưng có một số quy định sau:

  • Loại mã hóa ở đây phải là Manchester. Chỉ sử dụng mã Manchester có thể 1 Reader tìm bit xung đột dễ dàng và nhận ra tất cả các Tag trong vùng nhận dạng của nó.
  • Một vài lệnh đc sử dụng.

        +  Đầu tiên là lệnh Request. Lúc bắt đầu, Reader gửi một lệnh Request. Các Tag trả lời nếu chúng nhận đc một điiều kiện chắc chắn.

        +  Thứ hai là lệnh Select. Nếu Reader nhận đc một mã nhận dạng và ko có xung đột, Tag đc nhận dạng sẽ đc chọn bởi Reader. Sau đó các lệnh khác đc thực hiện như lệnh Read/Write data.

        +  Thứ ba là lệnh Read/Write data. Dữ liệu đã lưu trong thẻ Tag đã chọn sẽ đc đọc và thay đổi theo lệnh Read/Write data.

        +  Lệnh cuối là Unselect. Nếu một Tag hoạt động trên lệnh này, nó sẽ đi vào trạng thái ngủ “sleeping”, trong đó Tag sẽ ko trả lời bất kỳ lệnh nào bởi Reader trừ phi nó dời vùng nhận dạng của Reader và đi vào lại.

  • Điểm chính của Thuật toán này là tất cả các Tag phải trả lời Reader tại cùng thời điểm để các Tag có thể gửi mã nhận dạng của chúng tới Reader đồng bộ. Chỉ khi điều kiện như vậy thì thuật toán mới làm việc tốt.

    Tất cả những điều trên là như thuật toán BS và EBS nhưng Improved-EBS có sự khác biệt chính với chúng:

  • Do giá trị bit nhị phân riêng biệt lẫn nhau, nếu chỉ có một bit xung đột cho dù nó ở đâu, Reader ko cần gửi lệnh Request lại và có thể tự động nhận dạng hai Tag một lần.
  • Thuật toán tìm kiếm khác sẽ đc sử dụng nếu xung đột xảy ra. Sau khi xung đột kế tiếp đc dò, mỗi bit tương tự nhưng cuối rong lệnh Request sẽ đặt là 0. Sau đó hai Tag mà xung đột tại bit cuối của trình tự xung đột sẽ đc nhận dạng đồng bộ. Đối lập với các thuật toán đã đề cập ở trên, lệnh Request tiếp theo trực tiếp bằng cái cũ cộng với một. Duy trì gửi lệnh Request sau khi thêm, cho đến khi tất cả các Tag trong vùng nhận dạng đc nhận dạng hết.

Ví dụ:  Có 8 Tag với mã nhận dạng là:

a

    Reader ban đầu gửi một lệnh Request (1), và tất cả các Tag đều trả lời. Theo nguyên tắc của mã Manchester Utd, Reader nhận mã 10xxx001, vì vậy Reader có thể biết đc xung đột xảy ra ở bit D5, D4, và D3. Các bit cao hơn nơi xung đột xảy ra là D5 và D4. Theo thuật toán này D5 và D4 đặt về 0. Các bit mà cao hơn D5 sẽ ko đc thay đổi nên D7D6=10.

    Sau đó Reader gửi lệnh Request (1000). Reader nhận mã 1000×001. Vì chỉ có một bit mà xung đột xảy ra nên ko cần gửi lệnh Request lại nữa. Reader có thể có đc mã nhận dạng của Tag 1 và Tag 2. Cuối cùng, Reader chạy lệnh Unselect để chuyển Tag 1 và Tag 2 vào trạng thái “sleep”.

    Tiếp theo, Reader gửi lệnh Request (1001). Reader nhận mã 1001×001. Bây giờ, D3 là bit duy nhất xung đột. Tương tự, Reader có thể có đc mã nhận dạng của Tag 3 và Tag4 và chuyển chúng vào trạng thái “sleep”  sau cùng.

    Nữa, Reader gửi lệnh Request (1010). Reader nhận mã 1010×001. D3 là bit duy nhất xung đột nên Reader có đc mã nhận dạng của Tag 5 và tag 6. Sau đó Reader cho Tag 5 và Tag 6 vào trạng thái “sleep”.

    Cuối cùng, Reader gửi lệnh Request (1011) và nhận mã 1011×001. D3 là bit duy nhất xung đột nên Reader có đc mã nhận dạng của Tag 7 và Tag 8.

    Tất cả Tag đã đc nhận dạng, bảng sau mô tả quá trình này.

a

Hình 1:    Quá trình tìm kiếm của I-EBS

    Từ bảng ta có thể biết đc tổng số chu kỳ của I-EBS là 5. Với thuật toán EBS sẽ là 15, còn BS sẽ lớn hơn. So với BS và EBS, số chu kỳ giảm đáng kể.

.

.

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