射頻識(shí)別RFID (RadioFrequencyIdentification) 技術(shù)相對(duì)于傳統(tǒng)的磁卡及IC 卡技術(shù)具有非接觸,、閱讀速度快、無磨損等特點(diǎn),, 在最近幾年里得到快速發(fā)展,。RFID 系統(tǒng)主要由三部分組成, 即電子標(biāo)簽(tag),、讀寫器(reader) 以及天線(antenna),, 是一種非接觸式的自動(dòng)識(shí)別系統(tǒng)。隨著RFID系統(tǒng)的不斷增多,, 多個(gè)電子標(biāo)簽同時(shí)將信號(hào)送入一個(gè)讀寫器的讀寫通道必然會(huì)產(chǎn)生信道爭(zhēng)用問題,, 如何減少數(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í)識(shí)別出1~4 個(gè)標(biāo)簽,, 進(jìn)而提高閱讀器識(shí)別標(biāo)簽的效率,, 在信道利用率上遠(yuǎn)遠(yuǎn)優(yōu)于其它算法。
1 射頻識(shí)別系統(tǒng)的工作原理
射頻識(shí)別系統(tǒng)的工作頻段有低頻,, 中頻,, 高頻, 超高頻及微波之分,, 而在工業(yè)中通常采用13.56MHz 的頻率,。對(duì)于從閱讀器與電子標(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ú)特的序列號(hào)(UID)來識(shí)別標(biāo)簽為基礎(chǔ)的,, 為了能辨認(rèn)出閱讀器中數(shù)據(jù)碰撞比特位的準(zhǔn)確位置,, 傳統(tǒng)采用曼徹斯特編碼。該編碼采用電平的上升沿和下降沿來表示數(shù)值位,。本文中假設(shè)上升沿編碼為邏輯“0”,, 下降沿編碼為邏輯“1”, 若狀態(tài)跳變,, 視為無效數(shù)據(jù)且作為錯(cuò)誤碼被識(shí)別,。如在多標(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)確識(shí)別出碰撞位的示意圖如圖2 所示,, 圖中用紅色部分為碰撞位。
從圖中可知,, 閱讀器檢測(cè)出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)測(cè)碰撞位的發(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)簽將存儲(chǔ)的數(shù)據(jù)發(fā)送給閱讀器),。
4) UNSELECT: 取消一個(gè)事先選中的標(biāo)簽, 標(biāo)簽進(jìn)入“休眠”狀態(tài),。在該狀態(tài)下標(biāo)簽對(duì)收到的REQUEST 命令不作應(yīng)答,。為了重新激活標(biāo)簽,
須將標(biāo)簽移出閱讀器的作用范圍再進(jìn)入,, 以實(shí)行復(fù)位,。
3 算法原理
假設(shè)閱讀器作用范圍內(nèi)有6 個(gè)標(biāo)簽,, 閱讀器在本文約定的環(huán)境中識(shí)別這些標(biāo)簽,, 最初閱讀器對(duì)區(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), 因此識(shí)別過程結(jié)束,。圖3 為識(shí)別讀寫全部標(biāo)簽的流程圖:
通過該實(shí)例,, 可歸納該算法要點(diǎn)如下:
1) 閱讀器發(fā)Request (00000000) 命令, 要求區(qū)域內(nèi)所有標(biāo)簽應(yīng)答,。
2) 檢測(cè)有無碰撞發(fā)生,。若無碰撞時(shí), 可識(shí)別出一個(gè)單獨(dú)的標(biāo)簽,。標(biāo)簽值為應(yīng)答時(shí)返回的EPC 值,。處理完后, 再屏蔽掉它,。
3) 若有碰撞,, 可分兩種情況, 如碰撞位>2,, 則可從碰撞位中隨機(jī)選擇一位,, 并由選中的那一位和上一次REQUEST 中的參數(shù)共同決定下一次Request 命令所需的參數(shù), 具體如下: 在上一次REQUEST 命令中參數(shù)的基礎(chǔ)上再對(duì)所選中的那一位取反,, 即可得下一次REQUEST命令的參數(shù),。
4) 若碰撞位<=2 時(shí), 可通過改變相應(yīng)兩位的數(shù)值即00,, 01, 10,, 11 的值以同時(shí)識(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(): 棧空返回true,, 不空返回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ù)量以及碰撞對(duì)數(shù)的限制,, 假設(shè)n 個(gè)標(biāo)簽中這樣無重疊的理想碰撞標(biāo)簽對(duì)(任意兩組標(biāo)簽對(duì)中無相同的標(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%,, 對(duì)于標(biāo)簽較多的環(huán)境中將會(huì)高效完成讀寫動(dòng)作。
6 結(jié)語(yǔ)
通過本文對(duì)標(biāo)簽的處理過程可以看出讀寫過程實(shí)際上是請(qǐng)求與檢測(cè)的過程重復(fù)進(jìn)行,, 當(dāng)碰撞位小于等于2 時(shí)可以快速高效的識(shí)別出標(biāo)簽,, 而當(dāng)碰撞位大于2 時(shí)則通過屏蔽位的方式繼續(xù)發(fā)送請(qǐng)求命令直到碰撞位小于等于2, 正是通過反復(fù)迂回的方式從而大大減小了請(qǐng)求次數(shù),,提高了讀寫的速度,, 從而實(shí)現(xiàn)了高效率的控制。