朱紀銘，閆 述

（江蘇大學 計算機科學與通信工程學院，江蘇 鎮(zhèn)江 212013）

目前，無線射頻識別技術(shù)的應用仍然存在多標簽碰撞問題［1］，解決的方法主要有基于時隙Aloha的隨機型算法和基于二進制樹的確定型算法.基于Aloha的防碰撞算法［2－3］又包括純Aloha、時隙Aloha［4－8］等.Aloha算法簡單易實現(xiàn)，但存在誤判決問題，識別時間較長，信道利用率最大僅為36%，并存在“標簽饑渴”等問題；二進制算法［9－10］的優(yōu)點在于其識別率可達到100%，理論上只要時間足夠多，二進制算法就能識別出全部的標簽.二進制算法對碰撞的具體數(shù)據(jù)（碰撞的位數(shù)和位置）進行了一定的統(tǒng)計和處理，以此為依據(jù)來確定閱讀器發(fā)出的下一次命令參數(shù)，因此在此基礎上衍生出各種改進的二進制算法，但這些算法的不足在于其標簽中須添加計數(shù)器、計時器、寄存器等，從而增加了標簽的復雜度和功耗.為了解決這個問題，本研究擬從分析標簽編碼規(guī)則和對讀寫器要獲取的標簽種類兩方面入手，對標簽進行智能分組，從而減少標簽碰撞，提高系統(tǒng)效率.

1 標簽編碼規(guī)則

從對標簽編碼系統(tǒng)構(gòu)成的分析中得出一般性規(guī)律，以此規(guī)律作為標簽分組的依據(jù)，現(xiàn)以EPC編碼［11］為例.EPC的目標是為每一物理實體提供唯一標識，它是由一個頭字段和另外3段數(shù)據(jù)（依次為EPC管理者、對象分類、序號）組成的一組數(shù)字，具體結(jié)構(gòu)見表1.

1）頭字段標識EPC的版本號中設計者采用版本號標識了EPC的結(jié)構(gòu)，并給出EPC中編碼的總位數(shù)和其他3部分中每個部分的位數(shù).表1中3個64位的版本各有2位的版本號，96位版本和3個256位的版本則各有8位的版本號.3個64位的EPC的版本號只有2位，即01，10，11.為了與64位的EPC版本區(qū)別，所有長度大于64位的EPC版本號的最高兩位必須為00，這樣就定義了所有96位的EPC版本號開始的位序列是001.同樣，所有長度大于96位的EPC版本號的前2位是000.

2）EPC管理者描述與此EPC相關(guān)的生產(chǎn)廠商的信息，例如“聯(lián)想集團”.以EPC－64type 3為例，管理者編號長度為26，即可表達67 108 864個管理者.

表1 EPC標簽編碼規(guī)則Tab.1 Rule of electronic product code

3）對象分類記錄產(chǎn)品精確類型的信息，例如“廣東惠陽生產(chǎn)的ThinkPad SL410”（聯(lián)想集團生產(chǎn)的一種筆記本電腦）.

4）序號是貨品的唯一標識，它會準確地指明究竟是哪一臺ThinkPad SL410.

由此可見，以EPC－64type 1編碼為例，在64bit中包含著版本號（2bit）、管理者（21bit）、對象分類（17bit）、唯一序號（24bit）等信息.

2 編碼分組理論

在RFID系統(tǒng)識別的過程中，對于讀卡器而言，須識別的標簽的編碼無非是兩種情況：未知或者已知部分編碼（標簽編碼采用EPC－64編碼規(guī)則）.

1）對于標簽編碼信息未知狀態(tài)，分組識別流程如下，如某組中發(fā)生標簽碰撞，則采用后退機制二叉樹算法處理.

步驟1：讀寫器發(fā)出查詢指令，要求標簽返回前兩位，根據(jù)返回信息以版本號分組；

步驟2：讀寫器發(fā)出查詢指令，要求type為n（1～3）的標簽返回X1—X2位數(shù)據(jù)（根據(jù)不同的type，標簽分別返回相應位置的EPC管理者數(shù)據(jù)），對發(fā)生碰撞的標簽進行處理后得到管理者名單，根據(jù)管理者名單進行分組；

步驟3：讀寫器發(fā)出查詢指令，要求type為n，管理者為y的標簽返回X3—X4位數(shù)據(jù)（根據(jù)不同的type，標簽分別返回相應位置的對象分類數(shù)據(jù)），對發(fā)生碰撞的標簽進行處理后得到該管理者的對象分類名單，根據(jù)對象分類名單進行分組；

步驟4：讀寫器發(fā)出查詢指令，要求type為n，管理者為y的標簽，對象分類為k的標簽返回X5－X6位數(shù)據(jù)（根據(jù)不同的type，標簽分別返回相應位置的序列號數(shù)據(jù)），對發(fā)生碰撞的標簽進行處理后得到該分類的所有標簽的數(shù)據(jù)；

步驟5：返回管理者層，對管理者為y的未處理的對象分類數(shù)據(jù)依據(jù)步驟4進行處理，從而獲得管理者為y的所有標簽的數(shù)據(jù)；

步驟6：返回type層，對未處理的管理者數(shù)據(jù)依據(jù)步驟2，3，4，5進行處理，得到采用該版本所有標簽的數(shù)據(jù)；

步驟7：重復以上步驟，處理剩余標簽.

2）很多情況下，標簽編碼信息是部分可知的，包括以下幾種可能：①全部EPC管理者信息集合；②全部對象分類集合（對每個EPC管理者而言，其對象分類是有限的）；③特定對象分類以及子分類的編碼（如不同公司生產(chǎn)的MP3電子產(chǎn)品，電子產(chǎn)品屬于一個特定的對象分類，而MP3又屬于電子產(chǎn)品類中的一個特定子分類，在同一種編碼系統(tǒng)中，其編碼結(jié)構(gòu)應該是相同的）；④ 特定場合中的EPC管理者信息以及對象分類信息；⑤ 讀寫器要查詢的標簽種類信息.

通過以上分析，在讀寫器查詢標簽時就可以讓包含著特定信息（編碼）的標簽響應查詢指令，而不符合條件的標簽保持沉默狀態(tài)，從而大大減少查詢的次數(shù)，也減少標簽的碰撞.例如要統(tǒng)計某大型超市倉庫中諾基亞品牌的N97還有多少臺，讀寫器發(fā)出查詢指令，命令編碼中符合EPC管理者（諾基亞，編碼已知）、對象分類（電子產(chǎn)品類，手機，型號N97）的標簽傳回序列號（24bit）.

3 模擬仿真分析

現(xiàn)有10個碼長為16bit的標簽，分別為①1000 0001 0100 0001，②1000 0001 0100 1000，③1000 0001 1001 0010，④1001 0001 0100 1000，⑤1001 0001 1001 0001，⑥1001 0001 1001 0011，⑦0100 0101 0010 0100，⑧0100 0101 0010 1011，⑨0100 0101 0011 1000，⑩0011 1000 1011 0101.編碼符合以下規(guī)則（模仿EPC－64編碼規(guī)則，精簡碼位）：

1）1～4位編碼為管理者代碼，其中聯(lián)想集團代碼為1000，海爾公司代碼為1001，東方木業(yè)代碼為0100，耐克公司代碼為0011；

2）5～12位編碼為對象分類代碼，5～8位為對象代碼，9～12位為分類代碼，其中對象代碼中電子類代碼為0001，組合家具類代碼為0101，鞋類代碼為1000；分類代碼中手機類代碼為0100，筆記本類代碼為1001，休閑類代碼為1011，檀木類家具代碼為0010，楠木類家具代碼為0011；

3）13～16位編碼為序列號代碼，各公司自定義（相對于本公司，該序列號唯一）.根據(jù)編碼規(guī)則可知，10個標簽分別表示聯(lián)想公司生產(chǎn)的手機2部、筆記本1臺，海爾公司生產(chǎn)的手機1部、筆記本2臺，東方實業(yè)生產(chǎn)的檀木組合家具2套、楠木組合家具1套，耐克公司生產(chǎn)的休閑鞋1雙.

標簽識別流程（發(fā)生標簽碰撞均采用后退機制二叉樹算法處理）如下：

3.1 無初始條件（識別所有標簽）

第1步：讀寫器發(fā)出“Active”命令，所有標簽激活；

第2步：讀寫器發(fā)出“Request”命令，要求每個標簽傳回1～4位數(shù)據(jù)（管理者代碼），處理碰撞后得到管理者名單（1000，1001，0100，0011）；

第3步：讀寫器發(fā)出“Request”命令，要求1～4位編碼為1000的標簽傳回5～12位數(shù)據(jù)（對象分類代碼），標簽①，②，③響應，處理碰撞后得到對象分類名單（0001 0100，0001 1001）；

第4步：讀寫器發(fā)出“Request”命令，要求5～12位編碼為0001 0100的標簽傳回13～16位數(shù)據(jù)（序列號），標簽①，②響應，處理碰撞后識別標簽①，②；

第5步：讀寫器發(fā)出“Request”命令，要求5～12位編碼為0001 1001的標簽傳回13～16位數(shù)據(jù)（序列號），標簽③響應，無碰撞，直接識別；

第6步：重復步驟3～5，識別剩余管理組的所有標簽.

3.2 有初始條件（有選擇地識別標簽）

情況一：查詢聯(lián)想集團的所有產(chǎn)品.

分析：聯(lián)想集團的代碼為1000，那么只須命令1～4位編碼為1000的標簽響應即可.

第1步：讀寫器發(fā)出“Active”命令，所有標簽激活；

第2步：讀寫器發(fā)出“Request”命令，要求1～4位編碼為1000的標簽傳回第5～12位數(shù)據(jù)（對象分類代碼），標簽①，②，③響應，處理碰撞后得到對象分類名單（0001 0100，0001 1001）；

第3步：讀寫器發(fā)出“Request”命令，要求5～12位編碼為0001 0100的標簽傳回13～16位數(shù)據(jù)（序列號），標簽①，②響應，處理碰撞后識別標簽①，②；

第4步：讀寫器發(fā)出“Request”命令，要求5～12位編碼為0001 1001的標簽傳回13～16位數(shù)據(jù)（序列號），標簽③響應，無碰撞，直接識別.

情況二：查詢手機類的所有產(chǎn)品.

分析：手機類的代碼為0100，那么只須命令9～12位編碼為0100的標簽響應即可.

第1步：讀寫器發(fā)出“Active”命令，所有標簽激活；

第2步：讀寫器發(fā)出“Request”命令，要求9～12位編碼為0100的標簽返回1～4位數(shù)據(jù)，標簽①，②，④ 響應，處理碰撞后得到管理者名單（1000，1001）；

第3步：讀寫器發(fā)出“Request”命令，要求1～4位編碼為1000的標簽返回9～12位數(shù)據(jù)，標簽①，②響應，處理碰撞后識別標簽①，②；

第4步：讀寫器發(fā)出“Request”命令，要求1～4位編碼為1001的標簽返回9～12位數(shù)據(jù)，標簽④響應，直接識別.

分析情況一、二的處理流程及處理結(jié)果，可以看出在有初始條件的情況下，符合初始條件的標簽才響應讀寫器的查詢命令.由此可知，基于編碼分組的RFID防碰撞算法具有以下幾個優(yōu)點：①分組的依據(jù)是編碼的標準，編碼越精細，分組越精細；②根據(jù)編碼的分組，每次標簽傳送數(shù)據(jù)時僅須傳輸數(shù)據(jù)的一部分，也就意味著每次處理碰撞時僅須處理傳輸?shù)倪@部分數(shù)據(jù)，這不僅減少了數(shù)據(jù)的傳輸量，而且減少了碰撞的位數(shù)和次數(shù)，從而提高了處理的速度；③在有初始條件的情況下，查詢前就已淘汰了不符合初始條件的標簽，大大減少了通信量，降低了碰撞的可能，而且初始條件越苛刻，符合條件的標簽就越少，識別的速度和效率就越高.

［1］FINKENZELLER K.Fundamentals and applications in contactless smart cards and identification［M］.England：RFID Handbook，2003：1－38.

［2］LEE S R，JOO S D，LEE Cw.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification［C］／／Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems：Networking and Services.Washington，DC，USA：IEEE，2005：166－172.

［3］WIESELTHIER J E，EPHREMIDES A，MICHAELS L A.An exact analysis and performance evaluation of framed ALOHA with capture［J］.IEEE Trans Commun，1989，37（2）：125－137.

［4］CHA J R，KIM J H.Novel anti－collision algorithms for fast object identification in RFID system ［C］／／Proceedings of the 11th International Conference on Parallel and Distributed Systems.Fukuoka：IEEE，2005：63－67.

［5］VOGT H.Multiple object identification with passive RFID tags［C］／／Proceedings of the IEEE International Conference on Systems，Man and Cybernetics.Tunisia：IEEE，2002，3：6－13.

［6］PANICHPAPIBOON S.Adaptive frame length selection scheme for RFID object identification［C］／／Proceedings of the IEEE 18th International Symposium on Personal，Indoor and Mobile Radio Communications.Athens：IEEE，2007：1－5.

［7］WANG Liu－chun，LIU Hai－cai.A novel anti－collision algorithm for EPC Gen2RFID systems［C］／／Proceedings of the 3rd International Symposium onwireless Communication Systems.Piscataway，NJ，USA：IEEE，2006：761－765.

［8］WALDROP J，ENGELS Dw，SARMA S E.Colorwave：an anticollision algorithm for the reader collision problem ［C］／／IEEE International Conference on Communications（ICC′03）.Piscataway，NJ，USA：IEEE，2003：1206－1210.

［9］CHOI H S，CHA J R，KIM J H.Fastwireless anti－collision algorithm in ubiquitous ID system ［C］／／Proceedings of the 60th Vehicular Technology Conference.Piscataway，NJ，USA：IEEE，2004，6：4589－4592.

［10］MYUNG J，LEEw，SRIVASTAVA J.Adaptive binary splitting for efficient RFID tag anti－collision ［J］.IEEE Commun Lett，2006，10（3）：144－146.

［11］EPC global.Tag data standards version 1.3 ［EB／OL］.（2006－03－08）［2011－02－24］.http：／／www.epcglobalinc.org／standards／tds／tds－1－3－standard－20060308.pdf.