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

（電子科技大學(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ī)范的高頻讀寫器運用的防碰撞方法所基于的二進制搜索算法進行了介紹。并對實際所運用到的比特防碰撞方法進行了詳細的研究，對在防碰撞過程中讀寫器與標(biāo)簽的通信方法進行了分析，詳細說明了比特幀防沖突的具體流程。

1 二進制搜索算法

1.1 二進制搜索算法簡介

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

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

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

1.2 二進制搜索算法原理

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

能使得讀寫器能判斷數(shù)據(jù)沖突位的準(zhǔ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編碼可以實現(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é)點處繼續(xù)發(fā)送“請求”指令。不斷地循環(huán)，直到識別出所有的標(biāo)簽[5]。

下面通過實際例子來說明二進制搜索算法的原理：

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

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

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

2 比特幀防沖突

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

在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)，提倡增施有機肥，堅持配方施肥，推行節(jié)氮減排，做到適氮增磷鉀，實現(xiàn)化肥減量增效?！疤K麥188”全生育期純氮總用量為16 kg/畝左右，其中N：P2O5：K2O為1：0.6：0.6，其中氮肥運籌為基苗肥：平衡肥：拔節(jié)孕穗肥為5：1.0-1.5：3.5-4.0，磷鉀肥分基肥和拔節(jié)肥施用。

PCD接受到ATQA應(yīng)答后，PICC和PCD進入防沖突循環(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é)計數(shù)，指定所有有效數(shù)據(jù)位（包括被PCD發(fā)送的NVB和SEL）的數(shù)目被8除后所得的整數(shù)。這樣，字節(jié)計數(shù)的最小值是2而最大值是7。

較低4位稱為比特計數(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所確認。

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)有沖突則進入第5步，若無則進入第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校驗碼。發(fā)送選擇指令SELLECT；

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

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

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

4 結(jié)束語

基于二進制搜索算法的比特幀防沖突能高效率的解決當(dāng)高頻讀寫器讀到多個標(biāo)簽時的沖突問題，通過對比特幀防沖突的研究，我們能設(shè)計出更高效，更低功耗的讀卡器。對我國在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]徐麗香，藍運維.RFID二進制搜索法方碰撞的研究[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.