一種新型的混合查詢樹(shù)防碰撞算法

鄧紅衛(wèi)，梁小滿，許 航，廖瑾蕓

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

0 引 言

RFID技術(shù)是RFID系統(tǒng)架構(gòu)中感知層的關(guān)鍵技術(shù)之一。RFID系統(tǒng)主要由閱讀器、電子標(biāo)簽、RFID中間件和應(yīng)用系統(tǒng)軟件四個(gè)部分組成，閱讀器和電子標(biāo)簽通過(guò)一條共用的通信通道進(jìn)行無(wú)線通信完成數(shù)據(jù)傳輸。如果兩個(gè)及以上處于同一閱讀器可讀范圍內(nèi)的標(biāo)簽同時(shí)與閱讀器通信時(shí)，就會(huì)出現(xiàn)數(shù)據(jù)碰撞問(wèn)題，造成閱讀器無(wú)法識(shí)別標(biāo)簽。RFID標(biāo)簽防碰撞算法是RFID系統(tǒng)中的一個(gè)核心問(wèn)題，標(biāo)簽碰撞問(wèn)題的解決對(duì)RFID系統(tǒng)性能的提高至關(guān)重要。

目前標(biāo)簽防碰撞算法有兩種：基于ALOHA的非確定性算法和基于二進(jìn)制樹(shù)型結(jié)構(gòu)的確定性算法［1］。非確定性算法包括：ALOHA 算法、時(shí)隙ALOHA算法、幀時(shí)隙ALOHA算法和動(dòng)態(tài)時(shí)隙ALOHA算法，算法隨機(jī)性大，信道利用率低（理想狀態(tài)為36.8%），而且會(huì)出現(xiàn)個(gè)別標(biāo)簽無(wú)法識(shí)別（即“餓死”現(xiàn)象）；確定性算法包括：二進(jìn)制搜索算法、動(dòng)態(tài)二進(jìn)制搜索算法、后退式二進(jìn)制算法和查詢樹(shù)算法，算法標(biāo)簽識(shí)別率高，但識(shí)別延遲率高。

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

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

1.1 曼徹斯特編碼

曼徹斯特編碼［2］是RFID系統(tǒng)中的一種編碼方式。該編碼約定“0”表示上升沿，“1”表示下降沿。當(dāng)多個(gè)標(biāo)簽同時(shí)向閱讀器發(fā)送不同數(shù)據(jù)時(shí)，則對(duì)應(yīng)曼徹斯特編碼的上升沿和下降沿相互抵消，出現(xiàn)“沒(méi)有變化”的狀態(tài)，閱讀器由此可以確定碰撞的準(zhǔn)確位置。假設(shè)有兩個(gè)標(biāo)簽：10010110和10100011同時(shí)響應(yīng)閱讀器的請(qǐng)求，閱讀器獲得的信息為10XX0X1X，X表示為碰撞。工作原理如圖1所示。

圖1 曼徹斯特編碼

1.2 查詢樹(shù)算法［3］

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

圖2 QT樹(shù)結(jié)構(gòu)

1.3 混合查詢樹(shù)算法［4］

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

圖3 HQT樹(shù)結(jié)構(gòu)

2 新型的混合查詢樹(shù)算法

2.1 算法指令約定

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

（1）查詢指令REQUEST。REQUEST指令中的參數(shù)設(shè)有單參數(shù)、雙參數(shù)和三參數(shù)3種形式，分別有 REQUEST（＃）、REQUEST（Ht，Hr）和 REQUEST（p，Ht，Hr）3個(gè) REQUEST 指 令。REQUEST（＃）為最初查詢指令，要求閱讀器范圍內(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位置之后碰撞位中的最高碰撞位和次高碰撞位。

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

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

美國(guó)在《Mobility 2000》中對(duì)交通管理系統(tǒng)的定義強(qiáng)調(diào)，監(jiān)視、控制和管理交通?！氨O(jiān)視”交通的關(guān)鍵是采集、存儲(chǔ)和傳輸交通信息。隨著科學(xué)技術(shù)的發(fā)展，采集、存儲(chǔ)、傳輸交通信息的方法越來(lái)越智能化，智能交通管理系統(tǒng)應(yīng)運(yùn)而生。智能交通管理系統(tǒng)是利用先進(jìn)的信號(hào)檢測(cè)手段和相關(guān)交通控制模型，通過(guò)檢測(cè)到的交通信息，制定有效的交通控制方案，并將成熟的方案通過(guò)多種方式傳遞給交通參與者和管理者，目標(biāo)是提高交通管理和運(yùn)輸效率。

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

2.2 算法描述

本算法根據(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。算法流程如圖4所示。

圖4 算法流程

（1）假設(shè)閱讀器識(shí)別范圍內(nèi)有N個(gè)等待識(shí)別的標(biāo)簽，閱讀器首先發(fā)送Request（＃），N個(gè)標(biāo)簽都響應(yīng)，根據(jù)曼徹斯特編碼原理解碼生成相應(yīng)的比特流，從中取得最高碰撞位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.3 算法舉例

表1 曼徹斯特編碼

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

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

（2）閱讀器發(fā)送Request（＃），閱讀器識(shí)別范圍內(nèi)的所有標(biāo)簽都響應(yīng)，根據(jù)曼徹斯特編碼原理得到的解碼信息為X0XXXXXX，如表2所示。最高碰撞位為 Ht＝8，次高碰撞位為 Hr＝6，將（Ht，Hr）＝（8，6）存入Q1尾部，統(tǒng)計(jì)Request指令次數(shù)累加器k值為1，閱讀器從Q1取出（8，6），生成新的詢問(wèn)命令Request（8，6），發(fā)送給標(biāo)簽。同時(shí)，k值加1。標(biāo)簽分別計(jì)算其最高和次高碰撞位（第8、6位）的組合XtXr對(duì)應(yīng)的十進(jìn)制值，存放在自身的累加器C中，然后根據(jù)C值在對(duì)應(yīng)的時(shí)隙中響應(yīng)閱讀器。Tag4的XtXr＝00對(duì)應(yīng)C＝0，Tag2的XtXr＝01對(duì)應(yīng)C＝1，分別在時(shí)隙slot0、slot1中響應(yīng)并被識(shí)別；Tag5、Tag6和Tag7的XtXr＝10對(duì)應(yīng)C＝2，在時(shí)隙slot2中響應(yīng)，Tag1、Tag3和Tag8的XtXr＝11對(duì)應(yīng)C＝3，在時(shí)隙slot3中響應(yīng)，都發(fā)生碰撞，如表3所示。

表2 碰撞位信息

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

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

表4 碰撞位信息

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

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

表6 碰撞位信息

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

（5）上述8個(gè)標(biāo)簽的識(shí)別過(guò)程對(duì)應(yīng)的樹(shù)型結(jié)構(gòu)如圖5所示。根據(jù)最高碰撞位和次高碰撞位構(gòu)建成一棵四叉樹(shù)，樹(shù)高為2層，碰撞時(shí)隙為3個(gè)，空閑時(shí)隙為2個(gè)，與QT、HQT算法相比，減少了查詢次數(shù)和系統(tǒng)通信量，算法效率明顯提高。

圖5 NHQT樹(shù)結(jié)構(gòu)

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

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

圖6 三種算法識(shí)別延遲對(duì)比

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

本文提出的算法在混合查詢樹(shù)算法基礎(chǔ)上，算法根據(jù)最高和次高碰撞位的具體信息，動(dòng)態(tài)生成查詢前綴，充分利用已知位的信息，基本采用四叉樹(shù)，加大判斷的收斂性，標(biāo)簽識(shí)別的查詢次數(shù)和通信量明顯減少。仿真結(jié)果表明，該算法與QT、HQT兩種算法相比，識(shí)別延時(shí)性能方面明顯提高。

［1］SCHOUTEFS.DynamicframelengthALOHA ［J］.IEEETransactionsonCommunicationsLetters，1983，31（4）：565－568.

［2］伍繼雄，江岸，黃生葉，等.RFID系統(tǒng)中二叉樹(shù)防碰撞算法性能的提升［J］.湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，37（12）：82－86

［3］程文青，趙夢(mèng)欣，徐晶，等.改進(jìn)的RFID動(dòng)態(tài)幀時(shí)隙ALOHA算法［J］.華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，35（6）：14－16.

［4］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.