0 引言

　　射頻識別 (Radio Frequency Identification, RFID)的主要思想是通過射頻信號自動識別目標對象并獲取相關(guān)數(shù)據(jù)。RFID系統(tǒng)一般由電子標簽( Tag)和閱讀器(Reader)組成。閱讀器負責發(fā)送廣播并接收標簽的標識信息;標簽收到廣播命令后將自身標識信息發(fā)送給閱讀器。在數(shù)據(jù)傳輸?shù)倪^程中從閱讀器到標簽的數(shù)據(jù)傳輸稱作下傳,從標簽到閱讀器的數(shù)據(jù)傳輸稱作上傳。

　　隨著RFID的發(fā)展，其應用也越來越廣泛，當閱讀器識別區(qū)域內(nèi)存在兩個或者兩個以上的標簽在同一時刻向閱讀器發(fā)送標識信息時,將產(chǎn)生碰撞問題。解決碰撞問題的方法主要有空分多址(SDMA)、時分多址(TDMA)、碼分多址(CDMA)、頻分多址(FDMA)四大類。而其中時分多址方法在RFID防碰撞問題上是普遍采用的，它在復雜度和成本等方面都比其它3種方法更具優(yōu)越性。目前存在的基于TDMA 的反碰撞算法主要有兩種: 二進制搜索算法和ALOHA 算法。ALOHA 算法采用無規(guī)則的時分多址，或者叫隨機多址。ALOHA 算法操作簡便，成本低。但在應用中隨著標簽數(shù)量的擴大，性能將會急劇惡化。二進制搜索算法的電路實現(xiàn)要比ALOHA 算法復雜，但算法識別率較高。動態(tài)二進制搜索防碰撞算法以其簡明的思想、穩(wěn)定的系統(tǒng)性能和較少的系統(tǒng)資源需求在ISO/IEC14443A標準中被推薦為抗碰撞算法。本文提出一種二叉樹形搜索防碰撞算法，在平均時延等性能上相比動態(tài)二進制搜索算法有明顯改進,其分別通過識別每個標簽所需傳輸?shù)钠骄忍財?shù)來反映。驗結(jié)果可以證明該算法是一種有效的防碰撞算法。

　　1 二進制搜索算法

　　1.1 二進制搜索防碰撞算法

　　二進制搜索算法由一個讀寫器和多個標簽之間規(guī)定的一組命令和應答規(guī)則構(gòu)成,目的在于從多卡中選出任一個實現(xiàn)數(shù)據(jù)通信。該算法關(guān)鍵在于選用適當?shù)囊子谧R別的基帶編碼(如曼徹斯特碼(Mancherster)編碼)、利用標簽卡序列號唯一的特性和設(shè)計一組有效的指令規(guī)則,高效、迅速地實現(xiàn)選卡。

　　在二進制搜索算法的實現(xiàn)中,起決定作用的是讀寫器所使用的信號編碼必須能夠確定碰撞的準確比特位置。曼徹斯特碼(Mancherster) 可在多卡同時響應時,譯出錯誤碼字,可以按位識別出碰撞。這樣可以根據(jù)碰撞的位置,按一定法則重新搜索標簽。

　　二進制搜索法的實現(xiàn)需要每一個標簽都擁有唯一的一個ID號，算法的工作流程是:

　　(1) 首先讀寫器發(fā)送一個與標簽位數(shù)相同，數(shù)值全為1(即可能出現(xiàn)的最大碼)到標簽，所有標簽均發(fā)回它們的序列號。

　　(2) 對比標簽返回的各序列號相同位置上的位值(0或者1)，如果某一位上同時出現(xiàn)0和1，則譯碼將出現(xiàn)無法判斷的位，即認為該位是碰撞的。

　　(3) 確定有碰撞后,把有不一致位的數(shù)從最高位到次低位依次置0 再輸出序列號,即依次排除序列號大的數(shù),至讀寫器對比標簽響應的序列號的相同位數(shù)上的數(shù)完全一致時,說明無碰撞。這時就選出序列號最小的數(shù)。

　　(4) 選出序列號最小的數(shù)后,對該卡進行數(shù)據(jù)交換,然后使該卡進入“無聲”狀態(tài),則在讀寫器范圍也不再響應(移動該范圍后移入可再次響應)。

　　(5) 重復步驟(1),選出不是無聲狀態(tài)的標簽中序列號最小的標簽進行數(shù)據(jù)交換。

　　(6) 多次循環(huán)后可完成所有標簽的讀取。

　　1.2 動態(tài)二進制搜索算法

　　考慮到RFID標簽中的序列號長度標簽的序列號可能很長，如EPC 編碼的3 個版本中的編碼長度分別為64 位、96 位和256位，而UID(Ubiquitous Identifications) 編碼長度128 位，隨著今后的發(fā)展可能需要擴展到更長的長度。如此看來，若每次讀寫器發(fā)送的命令請求和標簽的回復均以全部序列號進行，會造成傳輸?shù)臄?shù)據(jù)量太大，降低了防碰撞算法的效率。動態(tài)二進制搜索算法提出的主要思想在于減少在識別過程中傳輸?shù)臄?shù)據(jù)量，其每一次讀寫器發(fā)送和標簽回復總共發(fā)送的位數(shù)是ID的總長度。這在一次收發(fā)中使傳輸?shù)臄?shù)據(jù)量相比基本二進制搜索算法減少了50%。

　　下面介紹動態(tài)二進制搜索算法及其工作過程。設(shè)有M個標簽，每個標簽中ID碼的長度為N。

　　(1) 首先讀寫器發(fā)送一個完整的N位ID碼 ,每個位上的碼全為1,讓所有標簽都發(fā)回響應。

　　(2) 讀寫器判斷所有返回的標簽序列號，并把最高的碰撞位X找出并置0。然后傳輸N～X位的數(shù)據(jù)后即中斷傳輸。標簽接到這段數(shù)據(jù)與自己的標簽從高到低比較,若相同則回傳該標簽ID的X-1～0，可看出一次收發(fā)以最高碰撞位為界，傳輸數(shù)據(jù)量減少一半。

　　(3) 讀寫器檢測返回的序列號，若無碰撞則直接跳入步驟(4);若仍有碰撞，檢測出最高碰撞位X\-1并置其為0，把上次發(fā)送的N～X位前綴加上這一次的N\-1～X\-1位數(shù)據(jù)發(fā)送后中斷傳輸。標簽把收到的碼與其自身的N～X\-1位比較，若相同則返回其X\-1～0位，不同則不響應。重復步驟(3)。

　　(4) 若無沖突位則可以通過發(fā)送READ-DATA命令讀取數(shù)據(jù)，并把該標簽置“無聲”狀態(tài)，以后不再響應。

　　(5) 重復步驟(1),直到所有標簽識別出來。

　　1.3 標簽預處理算法

　　在RFID系統(tǒng)的實際應用中，標簽的ID號中的碰撞位是不一定緊鄰的，也就是說在兩個相鄰的碰撞位中，很可能存在著若干位不沖突的位值。顯然這些位在防碰撞算法中是無關(guān)緊要的，所以如果在開始防碰撞算法前把所有標簽中不沖突的位排除出去，之后不再傳輸這些位置上的數(shù)值，對ID號進行了壓縮，這將減少防碰撞算法所需傳輸?shù)臄?shù)據(jù)量，提高防碰撞算法的效率。

　　標簽預處理算法的過程如下：

　　(1) 讀寫器發(fā)送查詢信號

　　(2) 所有標簽均發(fā)回它們的完整ID號。

　　(3) 讀寫器檢測這些ID號中的碰撞位，產(chǎn)生一個與ID號同等長度的序列記錄碰撞的位置，0代表該位無沖突，1則代表該位有沖突。

　　(4) 讀寫器發(fā)送產(chǎn)生的沖突位置序列到標簽， 標簽中的存儲器記錄沖突的位置，之后標簽的ID被壓縮，只有沖突的位被保留在ID中。

　　2 二叉樹形搜索防碰撞算法

　　在動態(tài)二進制搜索防碰撞算法中，每一次讀寫器與標簽之間的通信所傳輸?shù)臄?shù)據(jù)是以一個碰撞位為界，讀寫器發(fā)送ID的前綴部分，標簽發(fā)送ID的后續(xù)部分。由于標簽ID一般比較長，希望能更進一步減少在標簽識別過程中傳輸?shù)臄?shù)據(jù)量。本文提出一種二叉樹形搜索防碰撞算法，因其搜索路徑類似數(shù)據(jù)結(jié)構(gòu)中二叉樹而命此名。其最大的特點是每次讀寫器與標簽的通信，兩者均只需發(fā)送一比特有效數(shù)據(jù)。這極大程度的減少了平均最小時延和平均功率消耗，大大提高了防碰撞算法的識別效率。下面詳細介紹該算法。

　　2.1 算法約定

　　(1) 每個標簽中的ID都是唯一的。

　　(2) 每個標簽中包含一個位置計數(shù)器P(用于記錄當前響應讀寫器的是哪一位)。

　　(3) 每個標簽中包含一個睡眠程度計數(shù)器S(用于記錄該標簽的睡眠程度)。

　　(4) 每個標簽中包含一個已讀標志位R(用于記錄標簽是否已經(jīng)被讀)。

　　2.2 指令規(guī)則

　　(1) REQ_0 ：0請求，該命令無參數(shù)，標簽接收該命令后先檢查S，若S>0則S加1，P不變;若S=0則檢測ID(P)(ID中第P位數(shù)值)，若ID(P)=1則把S加1;若為ID(P)=0則把該標簽的P增加1且發(fā)回P增加后所指的那位數(shù)值到讀寫器，特殊的是當P增加后已經(jīng)指向ID的最后一位，則發(fā)回P所指的最后位再加上一位1表示P已經(jīng)指在最后位。

　　(2) REQ_LONG：長請求，該命令無參數(shù)，設(shè)標簽總長度為N，標簽收到命令后發(fā)回其ID的P～N位。

　　(3) READ_X:讀數(shù)據(jù)，帶一位參數(shù)，X為參數(shù)(0或1)。標簽收到命令將第P位與X比較，相等則將存儲的數(shù)據(jù)發(fā)送給讀寫器，并把標簽中的R置1,表示該標簽已被讀取,之后不再響應任何命令;不相等則不做反應。

　　(4) REQ_1 ：1請求，該命令無參數(shù)，所有R=0、S>0的標簽收到命令都把S減1。如果R=0、S=0，則該標簽的P增加1且發(fā)回位置P+1上的那位數(shù)值到讀寫器。特殊的是當標簽是發(fā)送最后一位時，再加上一位1表示P已經(jīng)指在最后位。

　　(5) CHG_POS：更改位置，該命令帶一個位數(shù)為|log2 N|+1(表示不小于log2 N的最小整數(shù)，N為標簽ID長度)的二進制數(shù)P'，表示響應的標簽中P需要增加的數(shù)值。響應命令的標簽把P改為P+P'-1 ，發(fā)回此時的第P位的值，特殊的是如果此時P為最后位，則發(fā)回最后位上的值再加上一位1表示已是最后。

　　2.3 算法流程說明

　　算法的流程圖如圖2所示。結(jié)合流程圖對算法的流程說明如下：

　　首先，只有R=0的標簽才對上述指令規(guī)則中的命令響應;其中只有S=0且R=0的標簽才對REQ_LONG、READ_X、CHG_POS命令響應。識別過程開始前先進行初始化，使所有標簽中的S=0,R=0,P=1。表示均處于非睡眠未讀狀態(tài)，且當前P指向ID中的第1位。

　　其次，對流程圖中5個分支判斷過程說明如下：

　　(1) 是否有停止位? 該判斷分支的輸入是標簽發(fā)送給讀寫器的回復，如果有停止位，說明發(fā)回信息的標簽中P已經(jīng)指向最后一位;沒有停止位則說明發(fā)回信息的標簽中的P還沒有指向最后位。

　　(2) 是否碰撞?該判斷分支的輸入是判斷(1)的N分支，也就是無停止位的情況。此時僅判斷收到的這位數(shù)值信息是否有碰撞發(fā)生，如果有碰撞則使用REQ_0命令繼續(xù)分離碰撞的標簽;如果無碰撞，說明發(fā)回信息的標簽中P所指的數(shù)值是相同的，但不能斷定P以后的位置上的數(shù)值不發(fā)生碰撞，所以使用REQ_LONG命令來使標簽發(fā)回ID的P~N位，用于獲取P以后的最近碰撞位。

　　(3) 是否碰撞?REQ_LONG命令后，響應命令的標簽發(fā)回ID的P~N位。如果無碰撞出現(xiàn)，根據(jù)ID的唯一性，可以斷定此時僅一個標簽響應，接下來便可使用READ_X命令讀取數(shù)據(jù)，參數(shù)X顯然就是發(fā)回的信息中的首位數(shù)值信息;如果有碰撞出現(xiàn)，則計算到最早出現(xiàn)的碰撞位，使用CHG_POS命令把這些標簽中的P增加到最早出現(xiàn)碰撞的位置，標簽發(fā)回新的P所指的位置上的數(shù)值信息，并根據(jù)P是否指向最后位來決定是否加停止位。

　　(4) 是否碰撞?該判斷分支的輸入是判斷(1)的Y分支，也就是確定標簽的回復中包含停止位的情況。此時對數(shù)值位檢測碰撞發(fā)生情況：如果有碰撞，可以確定此時發(fā)回信息的標簽只有兩個，且它們的ID的最后一位不同，即可連續(xù)使用READ_0、READ_1讀取這兩個標簽的數(shù)據(jù);如果無碰撞，則可斷定只有一個標簽發(fā)回信息，直接使用READ_X命令讀取該標簽的數(shù)據(jù)，參數(shù)X顯然是兩位回復信息中的第一位(數(shù)值位)。

　　(5) 有回復?該判斷分支在REQ_1命令之后，該命令會喚醒睡眠程度S=1的標簽，并使這些被喚醒的標簽發(fā)回P+1所指位置上的數(shù)值信息，轉(zhuǎn)到判斷分支(1)對標簽進行分離識別。如果在命令REQ_1后沒有任何回復，則識別過程結(jié)束。

　　算法流程如圖2所示。

　　 2.4 算法舉例

　　假設(shè)有4個標簽，分別是：Tag1：011000；Tag2：110011；Tag3：001011；Tag4：11001；

　　所有標簽在剛進入讀寫器射頻覆蓋范圍時都進行初始化，所有的S=0，P=1，R=0,。識別過程如表1所示。

　　3 算法性能分析與比較

　　本文提出的算法，其最大特點在于，相比二進制動態(tài)搜索算法而言，極大程度上減少了每次讀寫器與標簽的通信過程中所需的數(shù)據(jù)量，讀寫器所發(fā)送的命令基本上已經(jīng)無需攜帶額外的參數(shù)，標簽的回復信息一般縮短到只需1~2位數(shù)值信息，有一種例外的情況是當標簽在收到REQ_LONG命令后會回復標簽中P～N位置的一串碼。但不難看出，出現(xiàn)這種命令的機率會隨著標簽數(shù)目的增加而減少。因為標簽數(shù)越多，在REQ_LONG命令之前收到的返回碼發(fā)生沖突的可能性越大，由流程圖可看出識別過程轉(zhuǎn)向下一個REQ_0的機率也就越大，這就降低了出現(xiàn)REQ_LONG命令的出現(xiàn)概率。也就是說，改進算法在識別過程中的所需收發(fā)的平均比特數(shù)對于標簽總數(shù)N的增大是收斂的。所以該算法在標簽識別的平均最小時延方面得到了很大的改進。

　　為了更清晰的反映本文提出的算法在RFID的平均最小時延方面的高效性，對標簽識別過程進行實驗仿真，并與ISO/IEC14443A標準中推薦的動態(tài)二進制搜索防碰撞算法在相同的實驗條件下進行結(jié)果比較。

　　EPC編碼的3個版本中的編碼長度分別為64 位、96 位和256位，在下述實驗中編碼長度采用96位，讀寫器的命令長度根據(jù)ISO/IEC14443A標準采用9比特。

　　其編碼格式為：

　　由于標簽識別中的平均最小時延是通過識別每個標簽所需的平均比特數(shù)來反映，實驗中定義一個稱為平均比特數(shù)(AverageBit)的比較量，來衡量算法的性能。

　　平均比特數(shù)(AverageBit)=

　　如果讀寫器命令帶參數(shù)的把附加參數(shù)長度加在命令長度上。

　　考慮到標簽識別應用中可能出現(xiàn)一批相同種類的商品，也可能出現(xiàn)不同種類的商品。這些不同情況下標簽中隨機位數(shù)是不同的。使用均勻分布隨機函數(shù)產(chǎn)生隨機位數(shù)為36、60、88的3種情況，分別進行仿真。

　　前面提及的標簽預處理算法對本文提出的二叉樹形搜索防碰撞算法也是有效的，因為改預處理可以使得標簽在識別過程中跳過那些數(shù)值相同的位數(shù)，相當于使標簽ID的有效長度縮短，沖突位更加緊湊，這大大減少了二叉樹形搜索算法中出現(xiàn)REQ_LONG命令的次數(shù)，會使得平均比特數(shù)更少，使算法性能提高。實驗中也增加了與預處理后的二叉樹形搜索算法的比較。實驗結(jié)果如圖3、4、5所示。

　　由圖示實驗結(jié)果可以得出：

　　(1) 二叉樹形搜索防碰撞算法是收斂的，算法性能曲線隨著標簽總數(shù)的增加最終趨于平緩。標簽總數(shù)足夠大時，識別標簽的平均比特數(shù)趨于一個穩(wěn)定的值，這個值隨著標簽ID中隨機位數(shù)的減少有變小的趨勢，原因在于對于相同的標簽總數(shù)，隨機位數(shù)越少則會使標簽ID的沖突位更加緊湊，可以更大的體現(xiàn)出二叉樹形搜索算法的有效性能。

　　(2) 二叉樹形搜索防碰撞算法的性能相比動態(tài)二進制搜索防碰撞算法有了很大的改進，在標簽總數(shù)N大于10時可以很明顯看出兩算法的性能差距。由于二叉樹形搜索算法中一次收發(fā)中所需傳送的比特數(shù)相比動態(tài)二進制搜索算法急驟減少，從而使二叉樹形搜索算法識別過程的平均比特數(shù)大大減少，算法性能提高。

　　(3) 標簽預處理算法對于二叉樹形搜索算法是有效的。它能在真正開始標簽識別過程前去除ID中不沖突的位置，這會使沖突的位置緊湊，有利于二叉樹形搜索算法中少出現(xiàn)REQ_LONG問答，更好地發(fā)揮算法優(yōu)勢。由以上各圖可看出使用預處理的二叉樹形搜索算法平均比特數(shù)有了更進一步的減少，表現(xiàn)出更佳的性能。

　　4 結(jié)束語

　　本文的二叉樹形搜索防碰撞算法相比ISO/IEC14443A標準中的動態(tài)二進制搜索算法大大減少了識別每個標簽的平均比特數(shù)，也即是在最小時延和平均功耗方面比標準算法有了明顯的改進。尤其是在結(jié)合標簽預處理算法后，該算法的性能更得到了進一步的提高。標簽ID沖突位的分布對該算法性能有著一定的影響，沖突位分布越緊湊，算法在識別過程中的平均比特數(shù)越少，性能越好。該算法采用二叉樹型的搜索路徑對識別范圍內(nèi)的標簽進行快速識別，把平均每次標簽與讀寫器的數(shù)據(jù)傳輸所需比特數(shù)降低到了最少，且不隨標簽ID的長度變化而影響。因此，該算法對于RFID防碰撞技術(shù)有著極其重要的意義。

　　參考文獻：

　　[1\] 余松森，詹宜巨，彭衛(wèi)東.返回式索引的二進制樹形搜索反碰撞算法及其實現(xiàn)\[J\].計算機工程與應用,2004(16).

　　[2\] DONG-HER SHIH,PO-LING SUN,DAVID C. YEN. Taxonomy and survey of RFID anti-collision protocols\[J\].Computer Coummunications，2006(11).

　　[3\] FINKENZELLER K, RFID-HANDBOOK, Fundamentals and applications in contactless smart cards identification(Sencend Edition)\[M\].Wiley & Sons LTD,2003.

　　[4\] 姜麗芬，盧桂章，辛運帷.射頻識別系統(tǒng)中的防碰撞算法研究\[J\].計算機工程與應用,2007(15).

　　[5\] ISO/IEC 14443-3 Identification cards contactless integrated circuit(s) cards-proximity cards part 3: initialization and anti-collision\[S\].2003.

　　[6\] JI HWAN CHOI,DONGWOOK LEE,YOUNGWOO YOUN.Scanning-based pre-processing for enhanced RFID tag anti-collision protocols\[C\].ISCIT，2006.

　　[7\] F ZHOU,D JING,C HUANG ，et al.Optimize the Power Consumption of Passive Electronic Tags for Anti-collision Schemes\[C\].The 5th ASICON, Oct,2003 Beijing, China.

　　[7\] FENG ZHOU,DAWEI JIN,CHENLING HUANG,MIN HAO.Optimize the power consumption of passive electronic tags for anti-collision schemes\[C\].Beijing, China: ASIC, 2003(2).