Trang 1 Lời cảm ơn
Đầu tiên, tôi xin gởi lời cảm ơn sâu sắc đến PGS.TS. Dương Anh Đức, thầy đã hỗ
trợ rất nhiệt tình giúp tôi có hướng đi đúng đắn trong quá trình thực hiện đề tài.
Đồng thời, tôi xin gởi lời cảm ơn chân thành đến ThS. Trương Thiên Đỉnh, thầy đã
tạo điều kiện rất nhiều cũng như những ý kiến đóng góp, tranh luận giúp tôi hiểu rõ
thêm vấn đề. Tôi cũng muốn gởi lời cảm ơn chân thành đến ThS. Dương Huỳnh
Bảo, anh đã bỏ công sức thiết kế, hoàn thiện bộ đọc và hỗ trợ về mặt phần cứng
trong suốt thời gian tôi thực hiện đề tài.
Cuối cùng, con xin tỏ lòng biết ơn sâu sắc đến mẹ và gia đình đã luôn động viên, lo
lắng và chăm sóc con chu đáo trong thời gian qua, nhất là trong thời gian con làm
luận văn.
Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng có thể nhưng
khóa luận chắc chắn không tránh khỏi những thiếu sót nhất định. Tôi rất mong nhận
được sự góp ý và tận tình chỉ bảo của quý Thầy, Cô và các bạn.
Kính chúc sức khỏe đến tất cả.
TP. Hồ Chí Minh, tháng 8 năm 2012
Trang 2 Mục lục
Danh mục hình ảnh 6
3.3.1 Ý tưởng 40
3.3.2 Thuật toán 41
3.3.3 Phân tích 42
3.4 Dynamic Frame Slotted ALOHA (DFS-ALOHA) 45
3.4.1 Ý tưởng 46
3.4.2 Thuật toán 46
3.4.3 Phương pháp Schoute 47
3.4.4 Phương pháp Vogt 50
Chương 4 Các thuật toán giải quyết xung đột thẻ Tree-based 56
4.1 Tổng quan 56
4.1.1 Mã hóa NRZ 57
4.1.2 Mã hóa Manchester 58
4.2 Binary Tree (BT) 59
4.2.1 Thuật toán 59
4.2.2 Ví dụ 60
4.2.3 Phân tích 63
4.3 Dynamic Binary Tree (DBT) 65
4.3.1 Thuật toán 65
4.3.2 Ví dụ 66
4.3.3 Phân tích 68
4.4 Phương pháp cải tiến DBT 69
4.4.1 Consecutive DBT (CDBT) 69
4.4.2 Position DBT (PDBT) 72
4.5 Query Tree (QT) 75
4.5.1 Khái niệm 75
4.5.2 Thuật toán 76
4.5.3 Ví dụ 77
4.5.4 Phân tích 79
4.6 Bit collision detection Based Query Tree (BQT) 82
4.6.1 Thuật toán 82
6.3.4 Tiến trình xác định UID của các thẻ 118
6.3.5 Thuật toán giải quyết xung đột thẻ 119
6.4 Xây dựng hệ thống minh họa thuật toán 123
6.4.1 Firmware 123
6.4.2 Ứng dụng 130
Trang 5 6.4.3 Đánh giá thực nghiệm 132
Chương 7 Kết luận 137
7.1 Một số kết quả đạt được 137
7.2 Hướng phát triển 138
Tài liệu tham khảo 140
Trang 6 Danh mục hình ảnh
Hình 2.1 Phương pháp ASDMA với một ăng-ten điều hướng điện tử 21
Hình 2.2 Đa truy cập phân chia theo tần số 23
Hình 2.3 Sử dụng kênh truyền trong FDMA 24
Hình 2.4 Đa truy cập phân chia theo mã 25
Hình 2.5 Sử dụng kênh truyền trong CDMA 26
Hình 2.6 Đa truy cập phân chia theo thời gian 28
Hình 2.7 Sử dụng kênh truyền trong TDMA 29
Hình 3.1 Sơ đồ thuật toán Pure ALOHA theo thời gian 32
Hình 3.2 Xung đột gói tin trong thuật toán Pure ALOHA 34
Hình 3.3 Đồ thị thể hiện mối tương quan giữa S và G trong thuật toán Pure ALOHA 35
Hình 3.4 Sơ đồ thuật toán Slotted ALOHA theo thời gian 37
Hình 3.5 Xung đột gói tin trong thuật toán Slotted ALOHA 38
Hình 4.15 Cấu trúc Query Tree trong ví dụ 75
Hình 4.16 Sơ đồ thuật toán BQT 83
Hình 4.17 Cây BQT với n=4, k=2 87
Hình 4.18 Cây BQT với n=2, k=2 trường hợp tốt nhất 87
Hình 4.19 Cây BQT với n=2, k=2 trường hợp xấu nhất 87
Hình 5.1 Nguyên lý giao tiếp MIFARE 90
Hình 5.2 Mô hình truyền năng lượng 92
Hình 5.3 Tín hiệu điển hình truyền từ bộ đọc tới thẻ 92
Hình 5.4 Mã Miller khi truyền dữ liệu từ bộ đọc đến thẻ 93
Hình 5.5 Nguyên lý điều chế sóng mang phụ 94
Hình 5.6 Hệ số ghép đôi và đường kính ăngten 96
Hình 5.7 Sơ đồ khối chip MF1S503x/MF1S703x 98
Hình 5.8 Quá trình chứng thực 3 bước 100
Hình 5.9 Cấu trúc vùng nhớ MIFARE Classic 1K 101
Hình 5.10 Cấu trúc manufacturer block 102
Hình 5.11 Cấu trúc sector trailer 102
Hình 5.12 Cấu trúc điều kiện truy xuất vùng nhớ 103
Hình 6.1 Sơ đồ thành phần phần cứng bộ đọc SM 107
Hình 6.2 Cấu trúc frame chuẩn 109
Hình 6.3 Truyền dữ liệu dùng frame định hướng bit trường hợp full byte 111
Hình 6.4 Truyền dữ liệu dùng frame định hướng bit trường hợp split byte 111
Hình 6.5 Sơ đồ trạng thái thẻ trước và sau giải quyết xung đột 113
Hình 6.6 Tiến trình bộ đọc xác định UID của các thẻ 118
Hình 6.7 Sơ đồ thuật toán giải quyết xung đột thẻ DBT 120
Hình 6.8 Sơ đồ thuật toán giải quyết xung đột thẻ CDBT 122
Trang 8 Hình 6.9 Các khối xử lý chính trong firmware 123
Hình 6.10 Sơ đồ xử lý hàm ssp_send 124
Bảng 5-1 Tóm tắt MIFARE ISO/IEC 14443A 91
Bảng 5-2 Điều kiện truy xuất tới sector trailer 104
Bảng 5-3 Điều kiện truy xuất tới data block 105
Bảng 5-4 Tập lệnh hỗ trợ bởi MIFARE Classic 105
Bảng 6-1 Cấu trúc frame ngắn 109
Bảng 6-2 Mã lệnh REQA và WUPA 115
Bảng 6-3 Ý nghĩa của ATQA 116
Bảng 6-4 Kích thước UID trong ATQA 116
Bảng 6-5 Ý nghĩa của trường SEL 116
Trang 10 Bảng 6-6 Ý nghĩa của trường NVB 117
Bảng 6-7 Lệnh HLTA chứa trong frame chuẩn 118
Bảng 6-8 Kết quả thuật toán DBT theo lý thuyết với tối đa 6 thẻ 134
Bảng 6-9 Kết quả thuật toán DBT cài đặt thực tế với tối đa 6 thẻ 135
Bảng 6-10 So sánh độ phức tạp tính toán trong cài đặt giữa DBT và CDBT
worst-case
136
Trang 11 Chương 1
Mở đầu
1.1 Giới thiệu về công nghệ RFID
Vô tuyến Frequency Identification (RFID) là một công nghệ sử dụng sóng vô tuyến
hoạt động ở một tần số thích hợp để truyền dữ liệu giữa thẻ điện tử (hay còn gọi là
thẻ RFID hoặc nhãn RFID) với thiết bị nhận (hay còn gọi là bộ đọc RFID). Do đó,
người ta sẽ gắn thẻ RFID vào các đối tượng nhằm mục đích xác định và truy vết các
được những thành tựu rực rỡ.
Mặc dù những nguyên lý cơ bản của kỹ thuật RFID đã tồn tại từ thời Marconi
nhưng chúng ta chỉ mới bắt đầu bàn đến những tiềm năng to lớn của nó từ cuối thế
kỷ 20. Những năm đầu của thế kỷ 21 đã đánh dấu những điểm mốc chuyển biến
quan trọng của RFID. Kỹ thuật RFID hiện nay đang được sử dụng trong cả khu vực
kinh tế tư nhân lẫn chính phủ, từ việc theo dõi sách trong thư viện đến việc xác
nhận một chiếc chìa khóa khởi động xe. Cùng với những tiến bộ kỹ thuật và chi phí
sản xuất giảm đã và đang thúc đẩy sự phát triển của RFID.
1.1.2 Các loại thẻ RFID
Một hệ thống sử dụng công nghệ RFID gồm hai thành phần chính, đó là: bộ đọc
RFID và thẻ RFID. Hiện nay, có rất nhiều thẻ RFID được sản xuất nhưng xét ở mức
độ tổng quan nhất, chúng tôi phân loại thành hai loại thẻ: chủ động và thụ động.
a) Thẻ RFID chủ động được tạo thành bằng vi chip có gắn ăng-ten, thêm vào đó,
thẻ còn có nguồn cấp bên trong dùng để cấp điện thế cho vi chip hoạt động tạo
thành tín hiệu đầu ra. Các thẻ chủ động thường hoạt động ổn định hơn các thẻ thụ
động do khả năng kết nối “phiên” với bộ đọc. Nhờ có nguồn cấp bên trong nên các
thẻ chủ động có thể phát với công suất cao hơn các thẻ thụ động, cho phép chúng
hoạt động hiệu quả hơn trong các môi trường có tần số vô tuyến thay đổi như người,
Trang 13 gia súc, nước, kim loại nặng hoặc ở các khoảng cách xa hơn. Một số thẻ chủ động
còn tích hợp các bộ cảm biến như cảm biến nhiệt độ dùng để giám sát độ chín hay
giám sát nhiệt độ của các sản phẩm dễ hư hỏng. Các cảm biến khác cũng được gắn
với thẻ chủ động như: độ ẩm, biến động, ánh sáng, phóng xạ, nhiệt độ… Các thẻ
chủ động cũng thường có bộ nhớ lớn hơn các thẻ thụ động nên có thể lưu trữ thêm
thông tin từ bộ đọc RFID. Tuy nhiên, thời gian “sống” của thẻ chủ động lại phụ
thuộc vào nguồn cấp bên trong, thời gian này tỉ lệ nghịch với số lần đọc, ghi mà thẻ
chủ động trải qua. Hơn nữa, chính nguồn cấp bên trong đã làm cho chi phí và kích
thước của thẻ chủ động tăng lên đáng kể so với thẻ thụ động. Nhược điểm này khiến
Bộ đọc RFID cần phải phát ra một vùng năng lượng, đối với thẻ RFID thụ động,
vùng năng lượng này cần thiết cho mọi hoạt động của thẻ (cấp nguồn và truyền dữ
liệu), còn đối với thẻ RFID chủ động, nó chỉ cần cho việc truyền dữ liệu. Để phát ra
năng lượng, nguyên lý hoạt động bên trong bộ đọc RFID được thiết kế theo hai
hướng tiếp cận khác nhau: cảm ứng từ (magnetic induction) và sóng điện từ
(electromagnetic wave) ứng với hai vùng năng lượng khác nhau: near-field và far-
field. Cả hai đều có thể cung cấp đủ năng lượng cho mọi hoạt động của thẻ, còn tùy
thuộc vào từng loại thẻ nhưng thông thường nằm trong khoảng 10uW – 1mW (vi xử
lý Intel Pentium 4 cần tiêu thụ đến 50W khi hoạt động!).
a) Near-field RFID, vùng năng lượng này được tạo ra tuân theo định luật Faraday
về cảm ứng từ. Dòng điện biến thiên được truyền qua ăng-ten (đây chính là cuộn
cảm) trong bộ đọc RFID làm phát sinh vùng từ trường biến thiên xung quanh ăng-
ten. Nếu đặt thẻ RFID mà cấu tạo ăng-ten của nó là cuộn cảm vào vùng từ trường
này thì dòng điện sẽ xuất hiện trên ăng-ten của thẻ và được tích lũy trong tụ điện
dùng để cấp nguồn cho vi chip hoạt động. Thẻ RFID trong vùng năng lượng này
truyền dữ liệu ngược lại bộ đọc RFID bằng cách sử dụng công nghệ điều chế tải
(load modulation): ăng-ten của thẻ RFID sẽ tiêu thụ một lượng năng lượng biến đổi
trong vùng từ trường làm thay đổi dòng điện trên ăng-ten của bộ đọc RFID, sự thay
đổi này chính là dữ liệu truyền đi của thẻ RFID và sẽ được giải điều chế
(demodulation) ở phía bộ đọc RFID. Đây là hướng tiếp cận được sử dụng hầu hết
trong mọi bộ đọc RFID dùng với thẻ RFID thụ động. Tuy nhiên, near-field RFID có
Trang 15 giới hạn về mặt vật lý: bán kính bao phủ của vùng từ trường xấp xỉ theo công thức
c/2πf, trong đó, c là hằng số ánh sáng, f là tần số dao động, do đó, nếu f càng lớn thì
vùng từ trường càng nhỏ lại, hơn nữa, năng lượng càng xa tâm từ trường càng yếu
và nếu nhỏ hơn một ngưỡng cho phép thì cũng không thể giao tiếp, điều này dẫn
đến một hướng tiếp cận khác: Far-field RFID.
b) Far-field RFID, vùng năng lượng này được tạo ra tuân theo lý thuyết điện từ của
High-frequency: băng tần 13,56MHz. Tần số cao cho phép độ chính xác cao hơn
với phạm vi 1m, vì thế giảm rủi ro đọc sai thẻ. Các thẻ thụ động high-frequency
được đọc ở tốc độ 10 đến 100 thẻ trên giây và ở phạm vi 1m. Các thẻ high-
frequency được dùng trong việc theo dõi các hạng mục trong các thư viện và
kiểm soát hiệu sách, truy cập, theo dõi hành lý vận chuyển bằng máy bay và theo
dõi các món đồ trang sức.
Ultrahigh-frequency: các thẻ hoạt động ở băng tần 900MHz và có thể được đọc ở
khoảng cách dài hơn các thẻ high-frequency, phạm vi từ ≈ 0.9m đến ≈ 4.5m. Tuy
nhiên các thẻ này dễ bị ảnh hưởng bởi các nhân tố môi trường hơn các thẻ hoạt
động ở các tần số khác. Băng tần 900MHz thực sự phù hợp cho các ứng dụng
quản lý dây chuyền cung cấp vì tốc độ và phạm vi của nó. Các thẻ thụ động
ultrahigh-frequency có thể được đọc ở tốc độ 100 đến 1000 thẻ trên giây. Các thẻ
này thường được sử dụng trong việc kiểm tra pallet và container, xe chở hàng và
toa trong vận chuyển tàu biển.
Microwave frequency: băng tần 2,45GHz và 5,8GHz, có nhiều sóng vô tuyến
bức xạ từ các vật thể ở gần có thể cản trở khả năng truyền thông giữa bộ đọc và
thẻ. Các thẻ microwave RFID thường được dùng trong quản lý dây chuyền cung
cấp.
1.2 Tình hình nghiên cứu công nghệ RFID
Harry Stockman chính là người đầu tiên đặt cột mốc cho RFID khi công bố bài báo
"Communication by Means of Reflected Power" vào 10/1948. Stockman tuyên bố
sau đó rằng "Rõ ràng, việc nghiên cứu và phát triển đã được xem xét và hoàn thành
Trang 17 trước khi các vấn đề cơ bản còn lại trong giao tiếp tán xạ năng lượng được giải
quyết, và trước khi các lĩnh vực ứng dụng hữu ích được khám phá."
Thật vậy, những năm 1950 là một kỷ nguyên khám phá các công nghệ của RFID
dựa trên nền tảng phát triển kỹ thuật vô tuyến và radar trong những năm 1930 và
1940. Tiêu biểu là công trình của F. L. Vernon, "Application of the microwave
các nước tiên tiến.
Hiện nay nhiều doanh nghiệp, hiệp hội và tổ chức chính phủ đang xem xét để áp
dụng rộng rãi công nghệ RFID trong nhiều ứng dụng ở nước ta. Điều này mở ra một
thị trường vô cùng tiềm năng nhưng cũng nhiều thách thức cho các nhà nghiên cứu
và các nhà sản xuất. Vì thế để có thể vận dụng và phát triển công nghệ RFID, chúng
ta cần phải có sự tìm hiểu, nghiên cứu nghiêm túc về chúng.
1.4 Mục tiêu của luận văn
Trong một hệ thống RFID, bộ đọc có thể giao tiếp với nhiều thẻ trong phạm vi phủ
sóng của nó. Tuy nhiên, quá trình nhận dạng thẻ có thể thất bại khi nhiều thẻ gửi dữ
liệu cùng một lúc. Các tín hiệu từ các thẻ có thể can thiệp lẫn nhau và do đó bộ đọc
không thể nhận được bất kỳ dữ liệu chính xác tại tất cả các thẻ. Nếu điều này xảy ra,
các thẻ sẽ cố truyền lại dữ liệu của chúng, điều này làm lãng phí thời gian đọc thẻ
và dẫn đến làm giảm hiệu suất hệ thống đáng kể. Vấn đề như vậy thường được gọi
là "xung đột thẻ" (tag collision). Đối diện vấn đề này, các nhà nghiên cứu vẫn đang
tìm kiếm phương pháp giải quyết xung đột thẻ (tag anti-collision) hiệu quả nhất để
nhận được UID của thẻ với tốc độ nhận dạng nhanh và độ chính xác của dữ liệu
phải gần 100%.
Giải quyết xung đột thẻ có phạm vi nghiên cứu rất rộng. Do đó, mục tiêu của luận
văn nhằm tập trung làm sáng tỏ một số vấn đề sau:
Tìm hiểu các hướng tiếp cận giải quyết xung đột thẻ được áp dụng hiện nay.
Khảo sát, phân tích, so sánh các thuật toán tiêu biểu giải quyết xung đột thẻ
theo hướng ALOHA-based.
Trang 19 Khảo sát, phân tích, so sánh các thuật toán tiêu biểu giải quyết xung đột thẻ
theo hướng Tree-based. Từ đó đề xuất phương pháp cải tiến theo hướng này.
Tìm hiểu công nghệ MIFARE và thẻ RFID sử dụng công nghệ này. Đây là
công nghệ được lựa chọn cho hầu hết các hệ thống RFID trên toàn thế giới,
trở thành nền tảng thành công nhất trong ngành công nghiệp kiểm vé tự động.
thống truyền thông hiện đại so với ba cơ chế đa truy cập còn lại. Thông thường,
kiến trúc SDMA cung cấp khả năng truy cập không xung đột trong kênh truyền vô
tuyến và các ứng dụng nhạy cảm với độ trễ trong thời gian thực. Bởi vì SDMA phân
chia các kênh truyền có sẵn trong phạm vi không gian, nên hệ thống có thể làm tăng
đáng kể dung lượng kênh truyền của cùng một tần số và cùng một khe thời gian.
Các phương pháp chống xung đột thẻ được đề xuất dựa trên cơ chế SDMA là:
a) Minimum distance constellation: phương pháp này làm giảm đáng kể vùng năng
lượng của một đầu đọc, chỉ tập trung năng lượng vào một khu vực và giảm năng
lượng ở các khu vực khác, nhưng bù đắp lại bằng cách ghép một số lượng lớn các
bộ đọc để tạo thành một mảng nhằm phủ toàn bộ năng lượng khu vực xung quanh.
Phương pháp này đã được sử dụng thành công trong các sự kiện marathon quy mô
lớn để xác định thời gian chạy của các vận động viên. Mảng các bộ đọc được bố trí
bên dưới vạch kết thúc, vận động viên khi di chuyển về đích sẽ mang thẻ của mình
(được đính kèm trong gót giày) vào trong vùng năng lượng của một bộ đọc. Do đó,
một số lượng lớn các vận động viên có thể được đọc xác định đồng thời trong sự
phân bố không gian chạy.
b) Adaptive SDMA: phương pháp này sử dụng một ăng-ten điều hướng điện tử
trên bộ đọc, chùm định hướng có thể được trỏ trực tiếp đến một thẻ. Vì vậy, các thẻ
khác nhau có thể được phân biệt bởi vị trí góc của tín hiệu phản hồi của thẻ trong
Trang 21 vùng năng lượng của bộ đọc. Ăng-ten điều hướng điện tử trên bộ đọc là mảng các
ăng-ten lưỡng cực theo pha, do kích thước ăng-ten, phương pháp này chỉ có thể
được sử dụng cho các ứng dụng RFID với tần số trên 850MHz (điển hình là 2.45
GHz). Mỗi ăng-ten lưỡng cực điều khiển tín hiệu theo một hướng và độc lập với vị
trí pha. Các vùng năng lượng riêng biệt của các ăng-ten lưỡng cực theo các hướng
mong muốn chồng lên nhau trong pha, làm cho vùng năng lượng này được khuếch
đại đáng kể. Còn theo các hướng khác, toàn bộ hoặc một phần các sóng sẽ triệt tiêu
lẫn nhau. Để xác định một thẻ, không gian xung quanh bộ đọc sẽ được quét bởi ăng-
FDMA (Frequency Division Multiple Access) là hướng tiếp cận giải quyết xung đột
theo ý tưởng 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. Trong một hệ thống RFID
thụ động, tín hiệu từ bộ đọc thường được phát sóng ở một số tần số hoạt động để
cung cấp năng lượng và lệnh đến thẻ thụ động. Thẻ không chỉ nhận được năng
lượng mà còn sử dụng sóng mang từ bộ đọc để điều chế tín hiệu tán xạ của nó. Thật
vậy, một thẻ có thể nhận được bất kỳ tín hiệu nào trong dải tần số hoạt động của nó
và sử dụng các tín hiệu nhận được như là sóng mang để điều chế tín hiệu tán xạ của
nó. Vì vậy, hoàn toàn có thể lợi dụng đặc trưng này để áp dụng FDMA vào hệ thống
RFID thụ động.
FDMA đã được ứng dụng trong hệ thống RFID HF theo chuẩn ISO/IEC 18000-3,
trong đó gồm có 8 kênh phản hồi giao tiếp đồng thời với 8 thẻ RFID khác nhau, tuy
nhiên FDMA vẫn chưa được tích hợp trong bất kỳ chuẩn thẻ UHF thụ động nào.
Vào năm 2007, trong bài báo “A Frequency Diverse Gen2 RFID System with
Isolated Continuous Wave Emitters”, Liu đã đề xuất một phương pháp cho phép
Trang 23 một phản hồi của thẻ có thể xảy ra trong dãy tần số khác, được gọi là tán xạ ngược
đa sóng mang.
Thẻ 1
Thẻ 2
Thẻ 4
Bộ đọc
Thẻ 3
Thẻ 5
Thẻ 6
fa
f1
f2
CDMA (Code Division Multiple Access) đã được sử dụng rộng rãi trong các hệ
thống truyền thông hiện đại. Không giống như FDMA – các thẻ được phân chia vào
các tần số khác nhau hay TDMA – các thẻ được phân chia vào các thời điểm khác
nhau, hướng tiếp cận CDMA 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ố. Nó hoạt động dựa trên kỹ thuật điều chế trải phổ, các thẻ
sử dụng chung tần số và thời gian và được phân biệt nhau bằng một mã duy nhất
gọi là mã trải phổ. Do vậy chỉ những thẻ có mã tương quan phù hợp mới có khả
năng giải điều chế và thu được tín hiệu thông tin cần thiết từ phía bộ đọc. CDMA
thường được phân loại thành hai loại: trải phổ nhảy tần CDMA (FH-CDMA) và trải
phổ dãy trực tiếp CDMA (DS-CDMA). Bởi vì một thẻ thụ động thì không thể chủ
Copyright: Tài liệu đại học ©