鄧紅衛(wèi)，孫艷平，許 航，廖瑾蕓

（衡陽(yáng)師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖南 衡陽(yáng) 421002）

RFID技術(shù)是物聯(lián)網(wǎng)應(yīng)用系統(tǒng)中的核心技術(shù)，RFID標(biāo)簽識(shí)別是制約RFID技術(shù)發(fā)展的一項(xiàng)關(guān)鍵技術(shù)，標(biāo)簽碰撞大大降低了閱讀器對(duì)標(biāo)簽的識(shí)別速度和識(shí)別率。因此，對(duì)防碰撞算法的研究是至關(guān)重要的［1］。

防碰撞算法主要分為不確定性算法和確定性算法兩種類型［2］。不確定性算法隨機(jī)性大，信道利用率低，會(huì)出現(xiàn)“餓死”現(xiàn)象；確定性算法簽識(shí)別率高，但識(shí)別延遲率高。目前，有研究者結(jié)合兩種算法的特點(diǎn)，探索出一些混合性防碰撞算法［3］。

本文在雙向查詢樹算法基礎(chǔ)上，正向根據(jù)最高和次高碰撞位的具體信息，動(dòng)態(tài)生成查詢前綴，逆向引入碰撞模板，減少標(biāo)簽識(shí)別的查詢次數(shù)和通信量。

1 算法相關(guān)理論基礎(chǔ)

1.1 查詢樹算法［4］

查詢樹算法簡(jiǎn)稱為QT算法。閱讀器從查詢隊(duì)列中選擇一個(gè)查詢前綴發(fā)送給標(biāo)簽，具有相同前綴的標(biāo)簽響應(yīng)閱讀器，如果只有一個(gè)標(biāo)簽響應(yīng)，則正確識(shí)別該標(biāo)簽；如果有多于一個(gè)標(biāo)簽響應(yīng)，則發(fā)生了碰撞，閱讀器在查詢前綴后加0和1，生成新的查詢前綴，添加到查詢隊(duì)列中。通過(guò)不斷地增加查詢前綴的長(zhǎng)度，直至所有標(biāo)簽都被正確識(shí)別。如有4個(gè)等待識(shí)別的標(biāo)簽ID號(hào)：0010、0110、1001和1010，其識(shí)別過(guò)程如圖1所示。

圖1 QT算法

1.2 混合查詢樹算法［5］

混合查詢樹算法簡(jiǎn)稱為HQT算法，算法原理與QT算法類似，只是在發(fā)生碰撞時(shí)，閱讀器在查詢前綴后增加2位二進(jìn)制數(shù)位：00、01、10和11，生成新的查詢前綴，添加到查詢隊(duì)列中，通過(guò)不斷地增加查詢前綴的長(zhǎng)度，直至所有標(biāo)簽都被正確識(shí)別。如有4個(gè)等待識(shí)別的標(biāo)簽ID號(hào)：0010、0110、1001和1010，其識(shí)別過(guò)程如圖2所示。

圖2 HQT算法

2 雙向混合查詢樹防碰撞算法

2.1 算法指令約定

為了充分利用已得到的碰撞位信息，減少查詢次數(shù)和通信量，本算法對(duì)原有的算法指令進(jìn)行了如下改進(jìn)：

（1）碰撞距離（d）：發(fā)生碰撞的數(shù)據(jù)位到標(biāo)簽中心位置的相對(duì)距離。dH和dL分別定義為高、低位碰撞距離之和，當(dāng)閱讀器收到發(fā)生碰撞的數(shù)據(jù)后，首先對(duì)碰撞位進(jìn)行判別，即比較dH和dL的大小，然后再確定搜索方式。若dH＞dL，從高位到低位進(jìn)行搜索，直到將所有標(biāo)簽識(shí)別完畢；反之，即從低位到高位進(jìn)行搜索。例如，閱讀器接收到的數(shù)據(jù)為1x01x1x0，則各碰撞位所對(duì)應(yīng)的碰撞距離分別為d1＝3、d3＝1、d6＝3，計(jì)算出dH＝3和dL＝4，即dH＞dL，采用逆向搜索方式。

（2）查詢指令REQUEST。REQUEST指令中的參數(shù)設(shè)有單參數(shù)、雙參數(shù)和三參數(shù)3種形式，分別有 REQUEST（＃）、REQUEST（Ht，Hr）和 REQUEST（p，Ht，Hr）3 個(gè) REQUEST 指 令。RE－QUEST（＃）為最初查詢指令，要求閱讀器范圍內(nèi)的所有標(biāo)簽都得響應(yīng)；REQUEST（Ht，Hr）中的 Ht和Hr是標(biāo)簽響應(yīng)REQUEST（＃）發(fā)生碰撞所得到最高碰撞位和次高碰撞位，REQUEST（Ht，Hr）要求標(biāo)簽計(jì)算組合HtHr的十進(jìn)制值并存入自己的累加器C中；REQUEST（p，Ht，Hr）中的p為已知的前綴，Ht和Hr是以p為前綴的標(biāo)簽，p位置之后碰撞位中的最高碰撞位和次高碰撞位。

（3）選擇指令SELECT。SELECT（ID）選擇編號(hào)為ID標(biāo)簽，為讀出或?qū)懭霐?shù)據(jù)作準(zhǔn)備。

（4）讀取指令 READ。READ（ID）讀出編號(hào)為ID標(biāo)簽中的數(shù)據(jù)。

（5）屏蔽指令 UNSELECT。UNSELECT（ID）讓編號(hào)為ID標(biāo)簽處于非激活狀態(tài)，對(duì)收到的REQUEST指令不作應(yīng)答。

（6）碰撞模板CID。與標(biāo)簽ID位數(shù)相同，對(duì)應(yīng)碰撞位均置0，其他位置不變。

2.2 算法描述

本算法根據(jù)雙向混合查詢樹算法，先計(jì)算比較Dh和Dl的大小。若Dh＜Dl根據(jù)最高碰撞位Ht和次高碰撞位Hr的組合XtXr值，決定標(biāo)簽推遲C個(gè)時(shí)隙響應(yīng)閱讀器，閱讀器端設(shè)有兩個(gè)查詢隊(duì)列Q0和Q1，Q0存放由最高碰撞位Ht和次高碰撞位Hr之間的Xt…Xr值構(gòu)成新的查詢前綴p，Q1存放新的最高碰撞位和次高碰撞位的組合（Ht，Hr），初始值都為空；一個(gè)統(tǒng)計(jì)Request指令發(fā)送次數(shù)的累加器k，初始值都為1，直到標(biāo)簽識(shí)別結(jié)束。若Dh＞Dl根據(jù)逆向二進(jìn)制算法碰撞位置0，其余位不變，request根據(jù)碰撞模板依次增加1，直到標(biāo)簽識(shí)別結(jié)束。算法流程如圖3所示。

圖3 算法流程圖

假設(shè)閱讀器識(shí)別范圍內(nèi)有N個(gè)等待識(shí)別的標(biāo)簽，閱讀器首先發(fā)送Request（＃），N個(gè)標(biāo)簽都響應(yīng)，根據(jù)曼徹斯特編碼原理解碼生成相應(yīng)的比特流。計(jì)算比較Dh和Dl的大小。

1）Dh＜Dl

（1）從中取得最高碰撞位Ht，次高碰撞位Hr，構(gòu)成一個(gè)新查詢組合參數(shù)（Ht，Hr），插入到Q1隊(duì)列的尾部。閱讀器從Q1隊(duì)列取出（Ht，Hr）生成查詢命令Request（Ht，Hr），發(fā)送給標(biāo)簽。標(biāo)簽分別計(jì)算其第Ht、Hr碰撞位的組合XtXr對(duì)應(yīng)的十進(jìn)制值，存放在自身的累加器C中，然后根據(jù)自己的C值在對(duì)應(yīng)的時(shí)隙中進(jìn)行響應(yīng)。

（2）某一個(gè)時(shí)隙中如果只有一個(gè)標(biāo)簽響應(yīng)，則直接識(shí)別該標(biāo)簽，使用READ指令讀出該標(biāo)簽中的數(shù)據(jù)，并使用UNSELECT指令屏蔽該標(biāo)簽。否則，進(jìn)入第（3）步。

（3）某一個(gè)時(shí)隙中如果存在多個(gè)標(biāo)簽響應(yīng)，可以推知最高碰撞位Ht和次高碰撞位Hr之間的Xt…Xr值，將它作為一個(gè)新的查詢前綴p，按時(shí)隙順序依次插入到Q0隊(duì)列的尾部。同時(shí)，同一個(gè)時(shí)隙內(nèi)響應(yīng)的多個(gè)標(biāo)簽也會(huì)發(fā)生碰撞，碰撞位處在原來(lái)Hr位之后，從中取得最高碰撞位Ht，次高碰撞位Hr，構(gòu)成一個(gè)新查詢組合參數(shù)（Ht，Hr），按時(shí)隙順序依次插入到Q1隊(duì)列的尾部。

（4）閱讀器分別從隊(duì)列Q0和Q1的首部取出查詢前綴p和組合參數(shù)（Ht，Hr），生成新的查詢命令Request（p，Ht，Hr），發(fā)送給標(biāo)簽，要求前綴為p的標(biāo)簽響應(yīng)。前綴為p的標(biāo)簽計(jì)算第Ht、Hr碰撞位組合XtXr對(duì)應(yīng)的十進(jìn)制值，并存入自身的累加器C中，然后根據(jù)C值在對(duì)應(yīng)的時(shí)隙中進(jìn)行響應(yīng)。

（5）當(dāng)隊(duì)列Q0和Q1的值為空時(shí)，表明N個(gè)標(biāo)簽全部識(shí)別，算法結(jié)束。否則，返回到第（2）步。

2）Dh＞Dl

（1）閱讀器初始化指令序列號(hào)CID為全0。

（2）閱讀器接收標(biāo)簽的反饋信息，要么沒(méi)有碰撞，要么只有一位碰撞，這時(shí)，可直接識(shí)別。被識(shí)別出的標(biāo)簽，閱讀器將繼續(xù)依次發(fā)送選擇指令、讀取指令和去屏蔽指令。

（3）閱讀器發(fā)送request請(qǐng)求指令之后，指令序列號(hào)CID自動(dòng)累加1，并將作為下次發(fā)送request指令的序列號(hào)。

（4）當(dāng)CID重新為全0時(shí)，識(shí)別結(jié)束；否則返回到（2）繼續(xù)執(zhí)行。

2.3 算法舉例

假設(shè)閱讀器識(shí)別范圍內(nèi)有8個(gè)等待識(shí)別的標(biāo)簽，標(biāo)簽的ID號(hào)為8位，如表1所示。

表1 曼徹斯特編碼

算法的實(shí)現(xiàn)過(guò)程如下：

（1）閱讀器初始化查詢隊(duì)列Q0和Q1，初值為空；初始化k＝1。

（2）閱讀器發(fā)送Request（＃），閱讀器識(shí)別范圍內(nèi)的所有標(biāo)簽都響應(yīng)，根據(jù)曼徹斯特編碼原理得到的解碼信息為XX0XXX1X，如表2所示。根據(jù)碰撞距離計(jì)算Dh、Dl，Dh＞Dl即逆向搜索標(biāo)簽。根據(jù)CID得到Request（00000010），標(biāo)簽7被識(shí)別。碰撞不變，Rwquest（00000011），標(biāo)簽2被識(shí)別。碰撞不變Request（00000110），標(biāo)簽1被識(shí)別。碰撞不變Request（00000111），標(biāo)簽8被識(shí)別。

表2 碰撞位信息

（3）碰撞發(fā)生改變，剩余標(biāo)簽3、4、5、6碰撞為X10XXX0X，如表3所示。根據(jù)碰撞距離計(jì)算Dh、Dl，Dh＜Dl即正向搜索標(biāo)簽。最高碰撞位為Ht＝8，次高碰撞位為 Hr＝5，將（Ht，Hr）＝（8，5）存入Q1尾部，統(tǒng)計(jì)Request指令次數(shù)累加器k值為1，閱讀器從Q1取出（8，5），生成新的詢問(wèn)命令Request（8，5），發(fā)送給標(biāo)簽。同時(shí)，k值加1。標(biāo)簽分別計(jì)算其最高和次高碰撞位（第8、5位）的組合XtXr對(duì)應(yīng)的十進(jìn)制值，存放在自身的累加器C中，然后根據(jù)C值在對(duì)應(yīng)的時(shí)隙中響應(yīng)閱讀器。Tag3、Tag6的XtXr＝10對(duì)應(yīng)C＝2，Tag4、Tag5的XtXr＝01對(duì)應(yīng)C＝1，分別在時(shí)隙slot2、slot1中響應(yīng)，都發(fā)生碰撞，如表4、5所示。

表3 碰撞位信息

表4 標(biāo)簽響應(yīng)時(shí)隙

（4）表4表明Tag4、Tag5在時(shí)隙slot1中響應(yīng)，Tag3、Tag6在時(shí)隙slot2中響應(yīng)。Tag4、Tag5在時(shí)隙slot1中響應(yīng)第3位置發(fā)生碰撞，碰撞位信息如表5所示。閱讀器生成新的詢問(wèn)命令Request（01010，3），并發(fā)送給標(biāo)簽，標(biāo)簽4、5分別被識(shí)別。Tag3和Tag6在時(shí)隙slot2中響應(yīng)，在第4和3位置發(fā)生碰撞，碰撞位信息如表5所示。

表5 標(biāo)簽碰撞信息

表6 標(biāo)簽碰撞位信息

（5）最高碰撞位為Ht＝4，次高碰撞位為Hr＝3，閱讀器生成新的詢問(wèn)命令 Request（1100，4，3），并發(fā)送給標(biāo)簽，要求前四位（第8、7、6、5位）為1100的標(biāo)簽響應(yīng)。Tag3和Tag6分別計(jì)算第4、3碰撞位組合XtXr對(duì)應(yīng)的十進(jìn)制值存放在自身的累加器C中，標(biāo)簽根據(jù)C值在對(duì)應(yīng)的時(shí)隙中進(jìn)行響應(yīng)。Tag3的XtXr＝00對(duì)應(yīng)C＝0，Tag6的XtXr＝01對(duì)應(yīng)C＝1，分別在時(shí)隙slot0和slot1中響應(yīng)并被識(shí)別，識(shí)別過(guò)程如表7所示。

表7 標(biāo)簽響應(yīng)時(shí)隙

上述8個(gè)標(biāo)簽的識(shí)別過(guò)程與QT算法、HQT算法相比，減少了查詢次數(shù)和系統(tǒng)通信量，算法效率明顯提高。

3 算法仿真驗(yàn)證

本文使用Matlab仿真工具對(duì)該算法進(jìn)行仿真驗(yàn)證。仿真結(jié)果在相同實(shí)驗(yàn)條件下，在識(shí)別次數(shù)和傳輸數(shù)據(jù)量等方面，將此算法與QT算法、HQT算法相比，在識(shí)別次數(shù)和傳輸數(shù)據(jù)量等性能有明顯改善。如圖4所示。

圖4 BHQT、QT和HQT算法比較

4 結(jié)束語(yǔ)

本文在混合查詢樹防碰撞算法的基礎(chǔ)上，提出了一種改進(jìn)的算法，該算法比較碰撞距離之和的大小，正向根據(jù)最高和次高碰撞位的具體信息，動(dòng)態(tài)生成查詢前綴，充分利用已知位的信息，基本采用四叉樹，逆向搜索方式利用基本二進(jìn)制算法減少交互次數(shù)，標(biāo)簽識(shí)別的查詢次數(shù)和通信量明顯減少。仿真結(jié)果表明，該算法與基本二進(jìn)制算法、動(dòng)態(tài)二進(jìn)制數(shù)算法、基本查詢樹算法、混合查詢樹算法相比，性能方面明顯提高。

［1］楊曉嬌，閆斌，謝光斌.一種改進(jìn)的二進(jìn)制防碰撞算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2013，30（10）：312－316.

［2］米志強(qiáng).射頻識(shí)別（RFID）技術(shù)與應(yīng)用［M］.北京：電子工業(yè)出版社，2011.

［3］王春華，許靜，彭關(guān)超，等.改進(jìn)的RFID標(biāo)簽識(shí)別防沖突算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（31）：104－107.

［4］Choi J H，Lee D，Lee H.Bi－Slotted tree based anti－collision protocols for fast tag identification inRFID systems［C］.IEEE Communications Letters，2006：861－863.AND Feng Bo，Li Jintao，Guo Junbo，etal.ID－Binary tree stack anti－collision algorithm for RFID［C］.Proceedings of the 11th IEEE Symposium on Computers and Communications（2006ISCC’06），2006：207－212.

［5］李秉璋，景征駿，羅燁.基于后退式二進(jìn)制的RFID防碰撞搜索算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2009，26（12）：96－98.

［6］Myung J，Lee W.An adaptive memory less tag anti－collision protocol for RFID networks［C］.IEEEICC，2005：32－26.

［7］Hsu C H，Chia－Hao Yu，Yi Pin Huang，etal.An enhanced query tree（EQT）protocol for memorylesstag anti－collision in RFID systems ［J］.Second International Conference on Future Generation Communication and Networking FGCN ’08，2008：427－432.

［8］Ryu J，Lee Hojin，Seok Y，et al.A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID System［C］／／Proceedings of the IEEE international conference on communications.Glasgow：IEEE，2007：5981－5986.