Category Archives: Bkfet

Kỹ thuật điện tử


Electronic Engineering – ET2012


.

.

1

.

2

.

3

.

4

.

5

.

6

.

7

. .

 

Full Here:

http://www.mediafire.com/file/dv7vykleavfblo7/Electronic-Engeneering-ET2012.zip

.


 

 

Query Tree



.

Cấu trúc:

Query Tree:

  • Là một cây nhị phân đầy đủ
  • Mỗi node có 2 hoặc ko có node con nào.
  • Số lượng các node trong QT = số lượng chu kỳ bắt đầu bởi đầu đọc.
  • Đối với node x ko phải là node lá sẽ có 2 node con trái và phải lần lượt: l(x) và r(x)
  • Nếu x là node lá thì: l(x) = r(x) = NIL.

    Đầu chu kỳ, Reader gửi một chuỗi truy vấn thuộc Q, node gốc của QT chính là chuỗi truy vấn . Nếu node x tương ứng với chuỗi truy vấn q thì l(x) và r(x) tương ứng với chuỗi truy vấn q0 và q1. Một node ko phải là lá tương ứng với chuỗi truy vấn tại đó xảy ra xung đột trên kênh truyền. Ngược lại, nếu một node là lá tương ứng với chuỗi truy vấn tại đó ko nhận đc phản hồi nào từ các Tag hoặc chỉ có duy nhất một Tag phản hồi.

aHình 1.          internal node: node xảy ra xung đột

                      white leaf: node ko nhận được phản hồi

                      black leaf: node nhận đc một phản hồi

.

Thuật toán:

    Giống như DBT, thuật toán QT gồm các chu kỳ trong đó Reader truy vấn và các Tag phản hồi. Trong mỗi chu kỳ, Reader truy vấn ID của các Tag với một prefix. Nếu có nhiều hơn 1 Tag phản hồi, ít nhất có 2 Tag có cùng prefix, Reader sẽ thêm 0 hay 1 vào prefix và tiếp tục truy vấn với chuỗi prefix dài hơn. Đến khi chỉ còn 1 Tag phản hồi, ID của Tag đc xác định. Quá trình lặp lại cho đến khi xác định đc tất cả các Tag trong vùng nhận dạng.

capture

capture

hieuunganh-com_589c9ff73b0f7

capture

hieuunganh-com_589ca0f635605

Bảng 1: Quá trình của Query Tree

Ví dụ:

hieuunganh-com_589ca1d0e5314

Hình 2: Query Tree

capture

hieuunganh-com_589ca29b8d8d3

Bảng 2: Ngăn xếp của Bộ đọc

.

.

/sangnx.bkfet


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

.


Enhanced Binary Search (EBS)



.

    Thuật toán BS nâng cao (EBS) hay thuật toán dựa trên Nhảy và tìm kiếm động là một biến thể của BS, điểm khác biệt chính với BS là EBS ko bắt đầu lại quá trình đọc sau khi một Tag đc nhận dạng. Ngoài ra, trong quá trình khởi tạo, Reader truyền ‘1’ thay vì gửi một loạt số gồm tất cả chúng.

Thuật toán này như thuật toán BS nhưng:

  • Sau khi mã code nhận dạng của Tag đc nhận diện, quá trình chống xung đột ko chỉ đc nhắc lại như thuật toán BS. Mã code mà Reader sẽ gửi tiếp theo ko như quá trình trc đã gửi tại lúc bắt đầu. Nó là mã code thứ 2 (counting backwards) mà quá trình trc đã gửi. Sau đó mã code thứ 3 (counting backwards), code thứ 4 (counting backwards).. cho đến khi mã nhận dạng của tất cả các Tag đc nhận diện.
  • Trong lệnh Request đầu tiên, Reader gửi một code “1” thay vì gửi một code tối đa mà chiều dài của nó như mã nhận dạng của Tag và mỗi bit của mã code là logic “1”. Trong lệnh Request tiếp theo, Reader gửi những bit đã biết thay vì gửi tất cả các bit như trong BS. Quá trình tìm kiếm từ bit đỉnh tới bit dưới. Nếu những bit cao hơn của code nhận dạng Tag như các bit đã biết, các Tag tương ứng sẽ gửi code nhận dạng đến Reader.

.

.

/sangnx.bkfet


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

.


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

 

 


 

Thuật toán Tree-based chung



4

Hình  1. Cấu trúc Binary Search với m = 5, k = 4.

    Giả thiết đây là cây nhị phân đầy: tức các nút có 2 con với 2 giá trị 0 và 1 & các nút lá ở cùng mức.

    Cây có chiều cao là k thì số nút của cây là N = 2^(k+1) – 1 ==> k = log2(N+1) – 1.

Thuật toán:

n:  số lượng thẻ có thể có

k:  độ dài của ID của thẻ, cũng là chiều cao của cây nhị phân.

k = log 2 n

m:  số lượng thẻ nằm trong vùng năng lượng của bộ đọc (m <= n)

N xy : node thứ y (tính từ trái qua) có chiều cao x trong cây nhị phân.

T xy : cây con (subtree) mà node gốc của nó là N xy

Thuật toán đc xét như sau:

Bước 1:  Bắt đầu với node gốc của cây N 00 , mọi thẻ thuộc cây con T 00 gửi dữ liệu (ID) tại slot thời gian ứng với N00

Bước 2:  Nếu có từ 2 thẻ trở lên trong cây con T00 thì xung đột xảy ra tại node N00 , qua bc 3.

Bước 3:           T x = T 10

T y = T 11

5

.                Chiều cao

Hình  2. Cấu trúc Binary Tree ( với k = 3, m = 4 )

Bước 4:

Mọi thẻ thuộc cây con Tx gửi dữ liệu tại slot thời gian ứng với N10 .

Sau đó mọi thẻ thuộc cây con Ty gửi dữ liệu tại slot thời gian ứng với N11 .

Bước 5:  Nếu có bất kỳ xung đột nào xảy ra ở Bước 4:

  • Cho đến khi xung đột này được giải quyết, ko có thẻ nào được phép gửi dữ liệu mới.
  • Giải quyết xung đột ở Tx trước khi giải quyết xung đột ở Ty .

    Một xung đột trong Tx (hay Ty) đc giải quyết bằng cách chia Tx (hay Ty) thành 2 cây con A và B, gán Tx = A và Ty = B rồi lặp lại Bước 4 và Bước 5.

/sangnx.bkfet


Khái quát các thuật toán Tree-based và giao thức Aloha-based



  • Sơ đồ tổng quan các thuật toán Tree-based

6

  • Sơ đồ tổng quan các giao thức Aloha-based

7

.

/sangnx.bkfet


Các phương thức chống xung đột trong hệ thống RFID



    Có thể phân chia các giao thức chống xung đột tín hiệu trong hệ thống RFID như một trong các sơ đồ bên dưới.

8

9

Hình 1: Các kỹ thuật đa truy nhập và phương thức chống xung đột.

Các kỹ thuật đa truy nhập đc ứng dụng vào giải quyết xung đột Thẻ trong hệ thống RFID.

  • FDMA

10

Hình  2. Đa truy nhập phân chia theo Tần số.

Hướng giải quyết xung đột cho phép một số kênh truyền dẫn làm việc đồng thời tại cùng một thời gian bằng cách sử dụng các tần số hoạt động khác nhau.

  • CDMA

11

Hình  3. Đa truy nhập phân chia theo Mã

    Hướng tiếp cận cho phép các Thẻ có thể liên lạc với Bộ đọc trong cùng một thời điểm và tần số. Các Tag sử dụng chung tần số và thời gian phân biệt với nhau bằng mã duy nhất và chỉ những Tag có mã tương quan phù hợp mới giải điều chế và thu đc tín hiệu từ phía Reader.

  • TDMA

12

Hình  4. Đa truy nhập phân chia theo Thời gian

    Bộ đọc và thẻ có thể sử dụng cùng một tần số trong cùng một vùng năng lượng để giao tiếp với nhau, trong đó mỗi phản hồi của thẻ có thể được phân biệt với thẻ khác bằng khoảng thời gian mà nó được phép sử dụng.

    TDMA là nhóm lớn nhất, chủ yếu của các phương thức chống xung đột trong hệ thống RFID. Vì vậy sẽ tìm hiểu sâu hơn về các giao thức, thuật toán trong nhóm này.

  • SDMA

13

Hình  5. Đa truy nhập phân chia theo Ko gian

    Đây là công nghệ mới. Hướng tiếp cận giải quyết xung đột bằng tái sử dụng lại dung lượng kênh truyền trong các ko gian riêng biệt xung quanh Bộ đọc.

.

/sangnx.bkfet

Phân loại xung đột RFID



      Hệ thống RFID có các thao tác đọc ghi liên tục nên một thiết bị đọc có thể trao đổi dữ liệu với nhiều thẻ RFID cùng lúc do đó dễ xảy ra xung đột.

    Collision xảy ra khi nhiều RFID Tag hoặc nhiều RFID Reader đồng thời nhận dạng dữ liệu cùng nhau.

1.  Xung đột thẻ Tag

Diễn ra khi một bộ đọc Reader đọc đồng thời nhiều thẻ Tag tại cùng thời điểm với cùng tần số.

untitled untitled

Hình  1. Can thiệp Tag-to-Tag

2. Xung đột bộ đọc Reader

Các Reader can nhiễu lẫn nhau.

  • Reader-to-Tag Collision:

Xảy ra khi hai hay nhiều bộ đọc cùng nhận đồng thời dữ liệu một thẻ Tag tại cùng thời điểm, Tag này nằm trong vùng đọc của 2 hay nhiều Reader, nghĩa là tín hiệu từ một bộ đọc có thể nhiễu với tín hiệu từ bộ đọc khác ở nơi vùng phủ sóng chồng lấn lên nhau.

14

Hình  2. Can thiệp Reader-to-Tag

  • Reader-to-Reader Collision:

Xảy ra khi một Reader truyền một tín hiệu gây nhiễu với sự hoạt động của một Reader khác (Interference range). Do vậy ngăn bộ đọc thứ 2 giao tiếp với Tag khác trong vùng đọc của nó. Tín hiệu ở đây đc truyền bởi bộ đọc Reader đủ mạnh và nhận đc tại bộ Reader thứ 2.

15

Hình  3. Can thiệp Reader-to-Reader

Do vậy, cần thiết một giao thức trao đổi dữ liệu giữa Tag và Reader để tránh nhiễu, xung đột..

.

/sangnx.bkfet

%d bloggers like this: