射頻識別RFID （RadioFrequencyIdentification） 技術(shù)相對于傳統(tǒng)的磁卡及IC 卡技術(shù)具有非接觸、閱讀速度快、無磨損等特點(diǎn)， 在最近幾年里得到快速發(fā)展。RFID 系統(tǒng)主要由三部分組成， 即電子標(biāo)簽（tag）、讀寫器（reader） 以及天線（antenna）， 是一種非接觸式的自動(dòng)識別系統(tǒng)。隨著RFID系統(tǒng)的不斷增多， 多個(gè)電子標(biāo)簽同時(shí)將信號送入一個(gè)讀寫器的讀寫通道必然會(huì)產(chǎn)生信道爭用問題， 如何減少數(shù)據(jù)碰撞從而快速有效的在規(guī)定時(shí)間內(nèi)讀取出所有電子標(biāo)簽的信息成為一個(gè)難點(diǎn)。
解決碰撞問題的算法有ALOHA算法、分隙ALOHA算法和二進(jìn)制樹形搜索算法， 但這幾種算法都有一個(gè)共同的缺陷： 信道利用率比較低。本文提出了一種新的反碰撞算法， 這種算法是在傳統(tǒng)的二進(jìn)制樹算法基礎(chǔ)上， 通過迂回式反碰撞算法， 利用二進(jìn)制位取值的互異（即非0 即1）的特性， 以及連續(xù)兩位發(fā)生沖突（即00， 01， 10， 11）， 可同時(shí)識別出1~4 個(gè)標(biāo)簽， 進(jìn)而提高閱讀器識別標(biāo)簽的效率， 在信道利用率上遠(yuǎn)遠(yuǎn)優(yōu)于其它算法。
1 射頻識別系統(tǒng)的工作原理
射頻識別系統(tǒng)的工作頻段有低頻， 中頻， 高頻， 超高頻及微波之分， 而在工業(yè)中通常采用13.56MHz 的頻率。對于從閱讀器與電子標(biāo)簽間數(shù)據(jù)傳遞， 通常采用振幅鍵控ASK （AmplitudeShiftKeying）、頻移鍵控FSK(FrequencyShiftKeying)和相移鍵控PSK
（PHASEShiftKeying）。ASK 和PSK 常被使用， 因?yàn)樗鼈兲貏e容易解調(diào)， 其原理參見圖1。由圖1 中可知， 當(dāng)有多于1個(gè)的標(biāo)簽在閱讀器的作用范圍內(nèi)時(shí)， 且傳遞的數(shù)據(jù)0/1 交錯(cuò)時(shí)， 將會(huì)出現(xiàn)1個(gè)標(biāo)簽諧振，
1個(gè)標(biāo)簽失諧的情況。這時(shí)就閱讀器則很難通過判斷輸出端的高低電位來讀出標(biāo)簽的內(nèi)部信息， 這就是我們要解決的碰撞問題。
2 二進(jìn)制搜索算法原理
二進(jìn)制搜索算法， 是以一個(gè)獨(dú)特的序列號(UID)來識別標(biāo)簽為基礎(chǔ)的， 為了能辨認(rèn)出閱讀器中數(shù)據(jù)碰撞比特位的準(zhǔn)確位置， 傳統(tǒng)采用曼徹斯特編碼。該編碼采用電平的上升沿和下降沿來表示數(shù)值位。本文中假設(shè)上升沿編碼為邏輯“0”， 下降沿編碼為邏輯“1”， 若狀態(tài)跳變， 視為無效數(shù)據(jù)且作為錯(cuò)誤碼被識別。如在多標(biāo)簽的環(huán)境中當(dāng)同時(shí)有上升沿和下降沿同時(shí)存在是， 則會(huì)互相抵消從而無狀態(tài)跳變， 以此閱讀器判斷發(fā)生碰撞的準(zhǔn)確位數(shù)而再次搜索。假設(shè)有6 個(gè)RFID 標(biāo)簽， 其相應(yīng)EPC代碼為8 位， 利用曼徹斯特編碼能準(zhǔn)確識別出碰撞位的示意圖如圖2 所示， 圖中用紅色部分為碰撞位。
從圖中可知， 閱讀器檢測出D2， D3， D4， D6， D7 位出現(xiàn)碰撞，從而可以判斷出在同一區(qū)域內(nèi)存在多個(gè)RFID標(biāo)簽。
本文約定在閱讀器作用范圍內(nèi)的所有標(biāo)簽?zāi)茉谕粫r(shí)刻同步傳送響應(yīng)數(shù)據(jù)， 以便準(zhǔn)確地監(jiān)測碰撞位的發(fā)生。為了便于表述算法， 還需要引入4 種命令：
1） REQUEST： 表示閱讀器發(fā)送一個(gè)呼叫參數(shù)給區(qū)域內(nèi)標(biāo)簽， 所有標(biāo)簽的EPC 與之進(jìn)行“與運(yùn)算”， 結(jié)果全為0
的標(biāo)簽將各自的EPC返回至閱讀器。在第1 次詢問時(shí)， 呼叫參數(shù)應(yīng)全為0， 即Request 命令為： Request(00000000)，
這樣區(qū)域內(nèi)所有標(biāo)簽都會(huì)應(yīng)答。
2） SELECT： 用某個(gè)（事先確定的） EPC 作為參數(shù)發(fā)送給標(biāo)簽。具有相同EPC
的標(biāo)簽將以此作為執(zhí)行其他命令（例如讀出和寫入數(shù)據(jù)）的切入開關(guān)， 即選擇這個(gè)標(biāo)簽。
3） READ/DATA： 選中的標(biāo)簽將存儲的數(shù)據(jù)發(fā)送給閱讀器）。
4） UNSELECT： 取消一個(gè)事先選中的標(biāo)簽， 標(biāo)簽進(jìn)入“休眠”狀態(tài)。在該狀態(tài)下標(biāo)簽對收到的REQUEST 命令不作應(yīng)答。為了重新激活標(biāo)簽，
須將標(biāo)簽移出閱讀器的作用范圍再進(jìn)入， 以實(shí)行復(fù)位。
3 算法原理
假設(shè)閱讀器作用范圍內(nèi)有6 個(gè)標(biāo)簽， 閱讀器在本文約定的環(huán)境中識別這些標(biāo)簽， 最初閱讀器對區(qū)域內(nèi)標(biāo)簽處于未知狀態(tài)，
發(fā)送Request（00000000） 命令， 此時(shí)閱讀器周邊區(qū)域內(nèi)所有的標(biāo)簽則同步應(yīng)答。詳細(xì)數(shù)據(jù)處理過程如下：
Step1： 閱讀器發(fā)送Request （00000000） 命令。區(qū)域內(nèi)所有標(biāo)簽的與運(yùn)算結(jié)果全為0， 即所有的標(biāo)簽返回自身8 位的EPC
代碼應(yīng)答。根據(jù)曼徹斯特編碼原理， 可解碼得EPC 數(shù)據(jù)為： “$$1$$$10”， 即D2， D3， D4， D6， D7
位發(fā)生碰撞。算法作以下的處理： 從5 個(gè)碰撞位隨機(jī)選擇一位， 如D7； 然后將上一次Request命令中的參數(shù)00000000 的D7 位取反，
得下一次Request 命令所需的參數(shù)： 10000000。
Step2： 閱讀器發(fā)送Request （10000000） 命令。則此時(shí)區(qū)域內(nèi)D7位是0 的標(biāo)簽應(yīng)答， 即標(biāo)簽1 不相應(yīng)， 標(biāo)簽2~ 標(biāo)簽6
應(yīng)答， 同理可解碼得EPC 數(shù)據(jù)為： “0$1$$$10”， 碰撞位有： D2， D3， D4， D6， 位。算法作以下的處理： 從4
個(gè)碰撞位隨機(jī)選擇一個(gè)， 如D3； 然后將上一次Request 命令中的參數(shù)10000000 的D3 位取反， 得下一次Request命令所需的參數(shù)：
10001000。
Step3： 閱讀器發(fā)送Request （10001000） 命令。區(qū)域內(nèi)的D3 和D7 都是0 的標(biāo)簽應(yīng)答， 此時(shí)只有標(biāo)簽4 應(yīng)答，
其他標(biāo)簽不響應(yīng)， 在這種情況下沒有碰撞位， 閱讀器可以直接將收到的EPC 值用SELECT 命令發(fā)給標(biāo)簽4 并進(jìn)行讀寫操作，
處理完成后執(zhí)行Unselect 命令， 屏蔽掉標(biāo)簽4， 使它處于“休閑” 狀態(tài)。算法再采用回溯策略， 從該節(jié)點(diǎn)的父節(jié)點(diǎn)獲得下一次Request
命令所需的參數(shù)： 10000000。
Step4： 閱讀器發(fā)送Request ( 1000 0000) 命令。區(qū)域內(nèi)D7 位是0 的標(biāo)簽應(yīng)答， 即標(biāo)簽2， 標(biāo)簽3， 標(biāo)簽5， 標(biāo)簽6
應(yīng)答， 同理可解碼得EPC 數(shù)據(jù)為： 0$101$10， 碰撞位有： D2， D6， 位， 此時(shí)只有兩個(gè)碰撞位， 則讀寫器可依次通過SELECT
命令發(fā)送“00101010”，“00101110”， “01101010”， “01101110”， 從而完成標(biāo)簽5， 標(biāo)簽2， 標(biāo)簽6
的讀寫操作， 最后通過UNSELECT 命令將些三個(gè)標(biāo)簽置于“休閑” 狀態(tài)。算法再采用回溯策略， 從該節(jié)點(diǎn)的父節(jié)點(diǎn)獲得下一次Request
命令所需的參數(shù)： 00000000。
Step5： 閱讀器發(fā)送Request(00000000)命令。區(qū)域內(nèi)所有處于非“啞吧” 狀態(tài)的標(biāo)簽應(yīng)答， 即標(biāo)簽1 與標(biāo)簽3 應(yīng)答，
同理可解碼得EPC數(shù)據(jù)為： $0101010， 此時(shí)碰撞位只有D7 位。則讀寫器可依次通過SELECT命令發(fā)送00101010， 10101010，
從而完成標(biāo)簽3 和標(biāo)簽1 的讀寫操作， 最后通過UNSELECT 命令將標(biāo)簽3 和標(biāo)簽1 置于“休閑” 狀態(tài)。算法再采用回溯策略，
從該節(jié)點(diǎn)的父節(jié)點(diǎn)獲得下一次Request 命令所需的參數(shù)， 由于已到樹根無父節(jié)點(diǎn)， 因此識別過程結(jié)束。圖3 為識別讀寫全部標(biāo)簽的流程圖：
通過該實(shí)例， 可歸納該算法要點(diǎn)如下：
1） 閱讀器發(fā)Request （00000000） 命令， 要求區(qū)域內(nèi)所有標(biāo)簽應(yīng)答。
2） 檢測有無碰撞發(fā)生。若無碰撞時(shí)， 可識別出一個(gè)單獨(dú)的標(biāo)簽。標(biāo)簽值為應(yīng)答時(shí)返回的EPC 值。處理完后， 再屏蔽掉它。
3） 若有碰撞， 可分兩種情況， 如碰撞位>2， 則可從碰撞位中隨機(jī)選擇一位， 并由選中的那一位和上一次REQUEST 中的參數(shù)共同決定下一次Request 命令所需的參數(shù)， 具體如下： 在上一次REQUEST 命令中參數(shù)的基礎(chǔ)上再對所選中的那一位取反， 即可得下一次REQUEST命令的參數(shù)。
4） 若碰撞位<=2 時(shí)， 可通過改變相應(yīng)兩位的數(shù)值即00， 01， 10， 11 的值以同時(shí)識別出4 個(gè)標(biāo)簽， 另外下一次Request 命令所需參數(shù)， 采用回溯策略， 從其父節(jié)點(diǎn)獲得， 通過迂回方式直到執(zhí)行Request(00000000)命令返回值碰撞位小于2 時(shí)讀寫結(jié)束。
4 系統(tǒng)的軟件實(shí)現(xiàn)
以下程序?yàn)閷?shí)現(xiàn)讀寫過程的子程序：
Push(EPC)： 將EPC 值入棧；
Pop()： 將棧頂元素彈出；
GetTop()： 返回棧頂元素；
StackEmpty()： ?？辗祷豻rue， 不空返回false；
Request(EPC)： 閱讀器將EPC 發(fā)送給標(biāo)簽；
GetCollisionBitsCount_(EPC)： 返回EPC 值中碰撞位的數(shù)目；
RandomSelectCollisionBit(EPC)： 返回從EPC 中隨機(jī)選擇的一個(gè)碰撞位的下標(biāo)；
ReverseBit(EPC， n)： 將EPC 的第n 位取反， 并返回取反后的EPC 值；
SetCollision(EPC， bit)： 將EPC 的碰撞位置bit 值， 而其他位不變， 并返回。
閱讀器算法描述：
Push(00000000);
while(!stackEmpty())
{
Request(GetTop()); // 獲得返回的EPC 值;
if(GetCollisionBitsCount(EPC)>2)
Push(ReverseBit(GetTop()， RandomSelectCollisionBit(EPC)));
else
{
pop();
Switch(GetCollisionBitsCount(EPC))
Case0:
Select(EPC);
ReadData(EPC);
Unselect(EPC);
break;
Case1:
EPC0=SetCollision(EPC， 0);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
EPC0=SetCollision(EPC,1);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
break;
Case2:
for(i=0;i<4， i++)
{
EPC0=SetCollision(EPC,i);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
}
break;
}
}
5 算法復(fù)雜度和通信信道分析
本文這種迂回式算法受到標(biāo)簽數(shù)量以及碰撞對數(shù)的限制， 假設(shè)n 個(gè)標(biāo)簽中這樣無重疊的理想碰撞標(biāo)簽對(任意兩組標(biāo)簽對中無相同的標(biāo)簽)有m （m≤n/2） 組， 則在最理想的情況下(這個(gè)要由好的隨機(jī)算法提供)算法的總的詢問次數(shù)為： R （n， m） =2 （n-m） -3。在本文基于迂回式的算法發(fā)送REQUEST 命令的次數(shù)為5 次（R （6， 2））， 而參考文獻(xiàn)[5]中提出的算法的詢問次數(shù)為7 次， 讀寫速度提高28%， 對于標(biāo)簽較多的環(huán)境中將會(huì)高效完成讀寫動(dòng)作。
6 結(jié)語
通過本文對標(biāo)簽的處理過程可以看出讀寫過程實(shí)際上是請求與檢測的過程重復(fù)進(jìn)行， 當(dāng)碰撞位小于等于2 時(shí)可以快速高效的識別出標(biāo)簽， 而當(dāng)碰撞位大于2 時(shí)則通過屏蔽位的方式繼續(xù)發(fā)送請求命令直到碰撞位小于等于2， 正是通過反復(fù)迂回的方式從而大大減小了請求次數(shù)，提高了讀寫的速度， 從而實(shí)現(xiàn)了高效率的控制。