RFID高頻讀寫器防碰撞算法研究

鄧一文，張紅雨，張鵬程，向 舸

（電子科技大學(xué) 電子工程學(xué)院，四川 成都 611731）

RFID技術(shù)是一種非接觸式的自動識別技術(shù)。在RFID系統(tǒng)工作時，當(dāng)有多個標(biāo)簽同時向讀寫器發(fā)送數(shù)據(jù)時，由于傳輸信號的相互干擾，會造成數(shù)據(jù)無法讀取。這就必須通過一定的方法，以使讀寫器能夠正確的完成與所有標(biāo)簽的通信，這些方法就叫做防碰撞算法。隨著物聯(lián)網(wǎng)的應(yīng)用領(lǐng)域越來越廣泛，能適用于各種基于ISO/IEC 14443 A標(biāo)準(zhǔn)、低成本、小尺寸、高性能的非接觸式高頻通信的應(yīng)用場合也越來越多，所使用到的標(biāo)簽數(shù)量也越來越大。因此提高高頻讀寫器的防碰撞能力成為提高讀卡器性能關(guān)鍵[1]。

文中便對符合ISO/IEC 14443 A規(guī)范的高頻讀寫器運(yùn)用的防碰撞方法所基于的二進(jìn)制搜索算法進(jìn)行了介紹。并對實(shí)際所運(yùn)用到的比特防碰撞方法進(jìn)行了詳細(xì)的研究，對在防碰撞過程中讀寫器與標(biāo)簽的通信方法進(jìn)行了分析，詳細(xì)說明了比特幀防沖突的具體流程。

1 二進(jìn)制搜索算法

1.1 二進(jìn)制搜索算法簡介

RFID沖突問題與計(jì)算機(jī)網(wǎng)絡(luò)、無線電通信沖突問題都有相似之處。在無線電通信系統(tǒng)中，常用的多路存取方法一般有：空分多路法（SDMA）、頻分多路法（FDMA）、碼分多路法（CDMA）及時分多路法（TDMA），這些方法都可以被借鑒，但在RFID這個特殊系統(tǒng)中，空分多路法、頻分多路法、碼分多路法在技術(shù)實(shí)施上比較困難[2]，對讀寫器和標(biāo)簽的要求很高，需要支付的成本也相當(dāng)高，只限制在少數(shù)的特殊應(yīng)用場合。在諸多防沖突算法中，只有TDMA應(yīng)用得非常廣泛。

TDMA是把整個可供使用的通路容量按時問分配給多個標(biāo)簽的技術(shù)，讀寫器與各個標(biāo)簽分別在不同的時間里通信。盡管是在不同的時間通信，但由于整個時間很短，以致用戶感覺不到時間浪費(fèi)，從而可以被認(rèn)為讀寫器對各個標(biāo)簽的讀寫是“同時”進(jìn)行的。

在ISO/IEC 14443 A規(guī)范中，便采用了TMDA防沖突算法中的二進(jìn)制搜索算法。

1.2 二進(jìn)制搜索算法原理

二進(jìn)制搜索算法是以標(biāo)簽的唯一序列號為基礎(chǔ)來實(shí)現(xiàn)防沖突的。當(dāng)多個標(biāo)簽同時向讀寫器發(fā)送序列號時，讀寫器能判斷出數(shù)據(jù)沖突位的準(zhǔn)確位置，由于沖突位只能是“1”和“0”，然后強(qiáng)迫是“1”或“0”的標(biāo)簽暫時退出，以此類推。 在判斷完整個序列號之后，將得到唯一的序列號[3]。

能使得讀寫器能判斷數(shù)據(jù)沖突位的準(zhǔn)確位置的編碼是二進(jìn)制搜索算法的必要前提。Manchester編碼就具有這種性質(zhì)。圖1是NRZ編碼和Manchester編碼發(fā)生沖突時的比較。

圖1 NRZ和Manchester碼發(fā)生沖突時的差異Fig.1 The difference between NRZ and Mancherster

由圖1可知，對于NRZ碼，混合信號不能反映出異常的狀態(tài)。而當(dāng)Manchester編碼有不同的值時，接受到的整個位都是高電平，這種狀態(tài)未作規(guī)定，導(dǎo)致一種錯誤，讀寫器可根據(jù)錯誤判斷出沖突發(fā)生在第幾位。因此，Manchester編碼可以實(shí)現(xiàn)按位跟蹤沖突[4]。

假設(shè)標(biāo)簽序列號為n位，并且標(biāo)簽在接到讀寫器的指令后能在同一時刻將序列號傳送給讀寫器，以準(zhǔn)確的檢測到?jīng)_突位的位置。下面是算法執(zhí)行過程：

1） 讀寫器發(fā)送“請求”指令，參數(shù)為 11…1（n個 1），這時所有標(biāo)簽將應(yīng)答。讀寫器檢測收到的信號，若沒有標(biāo)簽，繼續(xù)發(fā)送“請求”指令；若只有一個標(biāo)簽應(yīng)答，選擇該標(biāo)簽，并與其完成讀寫操作，操作后令其退出，接著繼續(xù)發(fā)送“請求”指令。

2）若有不止一個標(biāo)簽，標(biāo)簽向讀寫器傳送的序列號將發(fā)生沖突，這時讀寫器利用Manchester編碼的特性識別出序列號發(fā)生沖突的位置，并將接收到的序列號的最高沖突位置“0”，高于該位的值不變，低于該位的值將全部設(shè)為“1”，得到下一步請求命令的參數(shù)。

3）在上一步的基礎(chǔ)上發(fā)送請求命令，這是由于請求命令的參數(shù)限制了一部分標(biāo)簽的應(yīng)答，有可能只有一個標(biāo)簽應(yīng)答，若不止一個，則重復(fù)第2）步，這樣不斷地縮小待選擇的標(biāo)簽，直到成功識別出一個標(biāo)簽。選擇該標(biāo)簽，并與其完成讀寫操作，操作后令其退出。

4）回到上一個結(jié)點(diǎn)處繼續(xù)發(fā)送“請求”指令。不斷地循環(huán)，直到識別出所有的標(biāo)簽[5]。

下面通過實(shí)際例子來說明二進(jìn)制搜索算法的原理：

設(shè)有4個標(biāo)簽，它們的序列號分別為l100 1100、1000 0100、1000 0110和1000 1100。當(dāng)讀寫器發(fā)送請求指令（參數(shù)1111 1111）時，4個標(biāo)簽將同時向讀寫器發(fā)送序列號，這時在第l位、第3位、第6位產(chǎn)生沖突，讀寫器接收到的序列號為1X00 X1X0，X為發(fā)生沖突的未知位，從而判斷有沖突產(chǎn)生。下一次請求指令的參數(shù)將最高沖突位置“0”，高于該位的值不變，低于該位的值將全部設(shè)為“1”，得到“101l 1111”，以此為參數(shù)繼續(xù)發(fā)送“請求”指令，以此類推，

直到識別出一個標(biāo)簽。具體過程見表1（X表示沖突位）

完成一個標(biāo)簽之后，會繼續(xù)請求下一個標(biāo)簽。這時讀寫器不是從最開始搜索，而是根據(jù)已有的信息，從上一級的沖突位開始搜索即讀寫器發(fā)送的請求指令參數(shù)不是“1111 1111”而是“1000 0111”。表2是搜索第二個標(biāo)簽的執(zhí)行過程。

在讀寫器輪詢過程中，返回的序列號并非全部的序列號，而是序列號中未知的其他bit值，這樣就可以減少二進(jìn)制搜索法在防沖突運(yùn)算中所要傳輸?shù)臄?shù)據(jù)量和所需的時間。在RFID系統(tǒng)中，當(dāng)射頻場內(nèi)出現(xiàn)沖突時，根據(jù)智能卡內(nèi)標(biāo)簽芯片UID序列號從高到低一次次篩選出某一射頻卡，進(jìn)行后續(xù)的操作。二進(jìn)制搜索法的特點(diǎn)在于穩(wěn)定性好，準(zhǔn)確度高，但是硬件實(shí)現(xiàn)比較麻煩。隨著沖突標(biāo)簽的越多、標(biāo)簽序列號越長，總的防碰撞執(zhí)行時問也越長。二進(jìn)制搜索算法為了從N個標(biāo)簽中找出唯一一個標(biāo)簽，需要進(jìn)行多次請求。其平均次數(shù)為：L=1og2N+1由公式可知，找出一個標(biāo)簽的請求次數(shù)將會隨著N的增加而迅速增加[6]。

表1 二進(jìn)制搜索算法執(zhí)行過程Tab.1 The process of binary search algorithm

表2 二進(jìn)制搜索算法執(zhí)行過程（第二步）Tab.2 The process of binary search algorithm（Step 2）

2 比特幀防沖突

ISO/IEC 14443A中提出的比特幀防沖突便是基于二進(jìn)制搜索算法所提出的一種有效實(shí)用的防沖突方法。

在ISO/IEC 14443 A中指定了以下幾個指令來管理PICC（標(biāo)簽）與 PCD（讀寫器）的通信：REQA請求命令，ATQA應(yīng)答，ANTICOLLISION，SELECT，SAK 應(yīng)答。

PCD設(shè)備（讀寫器）發(fā)送REQA請求命令，REQA命令數(shù)據(jù)組成如表3所示。

表3 REQA數(shù)據(jù)Tab.3 Data of REQA

REQA幀包括以下內(nèi)容：

1）通信起始位S

3）通信結(jié)束位E

PICC接收到REQA命令后，在PCD能量場內(nèi)所有PICC同時發(fā)出ATQA應(yīng)答，ATQA應(yīng)答數(shù)據(jù)組成如表4所示。

表4 ATQA數(shù)據(jù)Tab.4 Data of ATQA

ATQA幀包括以下內(nèi)容：

1）b8、b7表示UID比特幀的大小，如表5所示。

表5 b8 b7數(shù)據(jù)Tab.5 Data of b8 b7

2）b1～b5示采用的是比特幀防沖突方式，如表6所示。

表6 b1～b5 數(shù)據(jù)Tab.6 Data of b1～b5

3）RFU為保留位，均置為0。

應(yīng)立足綠色生產(chǎn)，提倡增施有機(jī)肥，堅(jiān)持配方施肥，推行節(jié)氮減排，做到適氮增磷鉀，實(shí)現(xiàn)化肥減量增效。“蘇麥188”全生育期純氮總用量為16 kg/畝左右，其中N：P2O5：K2O為1：0.6：0.6，其中氮肥運(yùn)籌為基苗肥：平衡肥：拔節(jié)孕穗肥為5：1.0-1.5：3.5-4.0，磷鉀肥分基肥和拔節(jié)肥施用。

PCD接受到ATQA應(yīng)答后，PICC和PCD進(jìn)入防沖突循環(huán)，PCD的ANTICOLLISION和SELECT命令用于防沖突循環(huán)。命令數(shù)據(jù)組成如表7所示。

表7 ANTICOLLISION和SELECT命令數(shù)據(jù)Tab.7Data of ANTICOLLISION and SELECT

命令幀包括以下內(nèi)容：

1）SEL表示選擇的串聯(lián)級別，定義如表8所示。

表8 SEL數(shù)據(jù)內(nèi)容Tab.8 Data of SEL

2）NVB表示有效比特的數(shù)，定義如表9所示。

較高4位稱為字節(jié)計(jì)數(shù)，指定所有有效數(shù)據(jù)位（包括被PCD發(fā)送的NVB和SEL）的數(shù)目被8除后所得的整數(shù)。這樣，字節(jié)計(jì)數(shù)的最小值是2而最大值是7。

較低4位稱為比特計(jì)數(shù)，指定所有有效數(shù)據(jù)位（包括被PCD發(fā)送的NVB和SEL）的數(shù)目被8除后所得的余數(shù)。

3）BCC在UID CLn為40 bit才有，是前5個字節(jié)的異或，此時為 SELECT 命令（NVB=‘70’），不足 40 個 bit時，則為ANTICOLISION命令。

表9 NVB數(shù)據(jù)內(nèi)容Tab.9 Data of NVB

PCD發(fā)送SELECT命令之后，與40位UID CLn匹配的PICC，以SAK作為應(yīng)答。SAK應(yīng)答的數(shù)據(jù)組成如表10所示。

表10 SAK應(yīng)答數(shù)據(jù)Tab.10 Data of SAK

1）b3表示UID是否完整，0表示完整，即PICC的UID已被PCD所確認(rèn)。

2）b6表示當(dāng) UID完整時，PICC是否遵循 ISO/IEC 14443－4，1 表示遵循。

3 比特幀防沖突流程

PCD初始化和防沖突流程如圖2所示。包括以下步驟：

1）PCD接收到ATQA，防沖突循環(huán)開始；

2）PCD指定 NVB的值為 ‘20’， 此值表示 PCD不發(fā)出UID CLn的任一部分，而迫使所有在場的PICC發(fā)回完整的UID CLn作為應(yīng)答，發(fā)送防沖突指令A(yù)NTICOLLISION；

3）PCD接收到所有在場的PICC發(fā)回完整的UIDCLn應(yīng)答；

4）如果發(fā)現(xiàn)有沖突則進(jìn)入第5步，若無則進(jìn)入第7步；

5）PCD記錄第一個沖突的位置；

6）PCD指示NVB值說明UID CLn的有效位數(shù)目，這些有效位是接收到的UID CLn發(fā)生沖；

突之前的部分，后面再由PCD加一位‘1’。發(fā)送防沖突指令A(yù)NTICOLLISION；

7）只有這樣的PICC，它們的UID CLn部分與PCD發(fā)送的有效數(shù)據(jù)位內(nèi)容相等，才發(fā)送出UID CLn的其余位；

8）假如還有沖突發(fā)生，重復(fù)5－7。最大循環(huán)次數(shù)為32；

9）假如沒有再發(fā)生沖突，PCD指定 NVB為‘70’，此值表示PCD將發(fā)送完整的UID CLn，接著發(fā)送40位UID CLn，后面是CRC校驗(yàn)碼。發(fā)送選擇指令SELLECT；

10）與40位UID CLn匹配的PICC，以SAK做為應(yīng)答；

11）檢驗(yàn)SAK中疊層位，若疊層位為‘0’，則UID是完整的，PICC從準(zhǔn)備狀態(tài)轉(zhuǎn)換到活動狀態(tài)，防沖突循環(huán)結(jié)束；如果層疊位為‘1’的SAK，將CL加1，并再次進(jìn)入防沖突循環(huán)。

圖2 比特幀防沖突流程Fig.2 The process of Bite frame anti-collision

4 結(jié)束語

基于二進(jìn)制搜索算法的比特幀防沖突能高效率的解決當(dāng)高頻讀寫器讀到多個標(biāo)簽時的沖突問題，通過對比特幀防沖突的研究，我們能設(shè)計(jì)出更高效，更低功耗的讀卡器。對我國在RFID產(chǎn)業(yè)的發(fā)展有著積極的推廣意義。

[1]紀(jì)震，李慧慧，姜來.電子標(biāo)簽與應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2006.

[2]Finkenzeller K. RFID Handbook：Fundamentals and applications in contactless smart card and identification[M].Second Edition，John Wiley&Sons，2002.

[3]（美）A.J.維特比，J.K小村.數(shù)字通信和編碼原理[M].西安：西安交通大學(xué)出版社，1990.

[4]游戰(zhàn)清，李蘇劍，無線射頻識別技術(shù)[M].北京：電子工業(yè)出版社，2004.

[5]徐麗香，藍(lán)運(yùn)維.RFID二進(jìn)制搜索法方碰撞的研究[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2006（5）：33-35.XU Li-xiang，LAN Yun-wei.Research of RFID binary search algorithm[J].Microcontrollers&Embedded Systems.2006（5）:33-35.

[6]陳香，薛小平，張思東.標(biāo)簽防沖突算法的研究[J].現(xiàn)代電子技術(shù)，2006（5）:13-15 CHEN Xiang， XUE Xiao-ping， ZHANG Si-dong.Research of anti-collision algorithm of tags[J].Modern Electronics Technique，2006（5）:13-15.