RFID系統(tǒng)中預(yù)先偵測查詢樹防碰撞算法的改進(jìn)

朱林海，李 鴻，陳凌宇

（長沙理工大學(xué) 電氣與信息工程學(xué)院，湖南 長沙410114）

0 引 言

由于射頻識(shí)別 （RFID）系統(tǒng)存在多個(gè)標(biāo)簽處于閱讀器范圍內(nèi)且共用同一個(gè)信道，標(biāo)簽在響應(yīng)閱讀器時(shí)會(huì)產(chǎn)生碰撞，導(dǎo)致識(shí)別失敗、降低傳輸效率的問題，如何有效地處理該問題是提高射頻識(shí)別系統(tǒng)性能的關(guān)鍵。

基于時(shí)分多路存儲(chǔ)技術(shù)的防碰撞算法有2類：隨機(jī)算法和確定性算法。隨機(jī)算法包括純ALOHA 算法、時(shí)隙ALOHA 算法等，這類算法標(biāo)簽的響應(yīng)是隨機(jī)的，有可能長時(shí)間都未能得到識(shí)別，會(huì)產(chǎn)生 “Tag starvation”問題，導(dǎo)致系統(tǒng)效率也很低，只能適用于少量的標(biāo)簽的場合。確定性算法典型的是樹型算法，包括后退式二進(jìn)制樹算法、四元偵測查詢樹算法等，該類型算法只要時(shí)間足夠，能成功識(shí)別每一個(gè)標(biāo)簽。其中，后退式二進(jìn)制樹算法每次只能生成2個(gè)子集，一旦標(biāo)簽數(shù)量過大，就會(huì)產(chǎn)生大量的碰撞時(shí)隙，使得系統(tǒng)的性能大大降低；四元預(yù)先偵測查詢樹算法雖然每次分裂生成4個(gè)子集且完全清除了空閑時(shí)隙，但是沒有很有效地解決大量標(biāo)簽情況下的碰撞問題，標(biāo)簽響應(yīng)閱讀器時(shí)，標(biāo)簽返回的信息含有沒有發(fā)生碰撞的位，即傳輸了沒必要傳輸?shù)臄?shù)據(jù)位，使得通信量沒得到明顯的改善，閱讀器的詢問次數(shù)也沒明顯的減少，系統(tǒng)的吞吐率依舊不高。為了解決這些問題，本文提出了改進(jìn)的預(yù)先偵測查詢樹防碰撞算法。

1 多標(biāo)簽防碰撞算法

1.1 BBS算法

文獻(xiàn) ［1］提出了后退式二進(jìn)制樹算法 （BBS），該算法在閱讀器成功識(shí)別一個(gè)標(biāo)簽后后退到上一層碰撞父節(jié)點(diǎn)開始搜索，閱讀器發(fā)送請求命令即序列號(hào)，當(dāng)標(biāo)簽的ID 號(hào)小于序列號(hào)或者等于序列號(hào)的標(biāo)簽都對(duì)該請求命令進(jìn)行響應(yīng)，并且標(biāo)簽返回自身整個(gè)ID 號(hào)，如果發(fā)生了碰撞，則把最高碰撞位置 “0”，碰撞位后置 “1”，得到下一次請求命令序列，繼續(xù)上一步驟；如果沒發(fā)生碰撞，則表明閱讀器成功識(shí)別了該標(biāo)簽，閱讀器再發(fā)送命令使其處于睡眠狀態(tài)，并后退到上一碰撞節(jié)點(diǎn)得到下一次請求命令序列，繼續(xù)以上操作。

1.2 PDQT算法

文獻(xiàn) ［2］中的PDQT 算法在四元查詢樹的基礎(chǔ)上引入了時(shí)隙預(yù)先偵測信號(hào)技術(shù)，結(jié)合了時(shí)隙預(yù)先偵測信號(hào)的機(jī)制，能夠根據(jù)偵測的情況確定標(biāo)簽是否有應(yīng)答。射頻識(shí)別系統(tǒng)的閱讀器發(fā)現(xiàn)標(biāo)簽在應(yīng)答的過程中產(chǎn)生了碰撞，會(huì)把查詢字符串?dāng)U展2位即00、01、10和11，假設(shè)形成新的查詢字串為01 00、01 01、01 10、01 11，利用時(shí)隙預(yù)先偵測信號(hào)技術(shù)，偵測并判斷標(biāo)簽的應(yīng)答情況，刪除不需要的擴(kuò)展后的新查詢字串［2］，如果01 10空閑，就把01 10刪除，需要的擴(kuò)展后的新查詢字串01 00、01 01和01 11置入等待查詢序列中，然后閱讀器發(fā)送帶有該查詢字串的查詢命令，繼續(xù)以上步驟，直到每個(gè)標(biāo)簽被識(shí)別，其中01為上一次查詢的字串。

2 改進(jìn)的預(yù)先偵測查詢樹防碰撞算法

2.1 算法的優(yōu)化

改進(jìn)的預(yù)先偵測查詢樹防碰撞算法采用曼切斯特（Manchester）編碼，能準(zhǔn)確的判斷標(biāo)簽的碰撞位。該算法做出了以下改進(jìn)：

（1）對(duì)需要識(shí)別的標(biāo)簽進(jìn)行一次預(yù)處理，把各標(biāo)簽ID的碰撞位提取出來，作為新的ID 與閱讀器通信，并且結(jié)合動(dòng)態(tài)二進(jìn)制算法，標(biāo)簽返回的信息是除去閱讀器發(fā)送查詢字串即前綴的剩余ID 位，這樣大大的減少了系統(tǒng)的傳輸位數(shù)。

（2）采用八叉樹詢問代替原算法的四叉樹詢問，減少了標(biāo)簽的碰撞數(shù)目，提高了算法的效率。

（3）利用后退式搜索與堆棧存儲(chǔ)的方法以避免重復(fù)搜索和冗余搜索，閱讀器成功識(shí)別標(biāo)簽后直接后退到上一層父節(jié)點(diǎn)搜索，而不是根節(jié)點(diǎn)，減少了詢問次數(shù)。

2.2 算法的原理

本文提出的算法通過提取碰撞位信息來構(gòu)建新的ID號(hào)，然后與閱讀器通信，在引入PDQT 算法的時(shí)隙預(yù)先偵測信號(hào)機(jī)制的基礎(chǔ)上，從原算法的4 個(gè)偵測時(shí)隙增加到8個(gè)偵測時(shí)隙，分別為dts1、dts2、dts3、dts4、dts5、dts6、dts7、dts8。在預(yù)先偵測機(jī)制中，閱讀器發(fā)送查詢的請求命令后，偵測前面8個(gè)偵測時(shí)隙，根據(jù)偵測時(shí)隙中是否含有前偵測信號(hào)來判斷標(biāo)簽是否出現(xiàn)碰撞情況以及空閑狀況。如圖1和圖2 所示，假設(shè)標(biāo)簽已經(jīng)經(jīng)過提取碰撞位處理，就最后一層的標(biāo)簽而言，dts2、dts3、dts4、dts5檢測到前偵測信號(hào)，分別表示有符合查詢前綴011 001、011 010、011 011、011 100 的標(biāo)簽存在；dts1、dts6、dts7、dts8 沒有檢測到前偵測信號(hào)，分別表示沒有符合查詢前綴011 000、011 101、011 110、011 111的標(biāo)簽的存在，其中011為上一次的查詢前綴。這樣閱讀器可以知曉在下一次的查詢命令，并且只發(fā)送查詢前綴給存在的標(biāo)簽，因此閱讀器會(huì)選擇新的查詢前綴011 001、011 010、011 011、011 100。閱讀器不會(huì)發(fā)送查詢前綴給不存在的標(biāo)簽，這樣就刪除了空閑時(shí)期，減少了閱讀器的查詢次數(shù)。

圖1 改進(jìn)的四元查詢樹算法實(shí)例

圖2 時(shí)隙前偵測信號(hào)技術(shù)實(shí)例

算法還利用了后退式索引與堆棧技術(shù)，把擴(kuò)展后的查詢前綴置入棧中，閱讀器取棧頂前綴發(fā)送。

2.3 算法約定

本算法需要以下6 種基本基本指令：Request（null）、Request（prefix）、Select（prefix）、Rw－data、Unselect 和Ext－Collision－Bit.

（1）Request（null）—請求命令，作用范圍的每一個(gè)標(biāo)簽都響應(yīng)閱讀器，標(biāo)簽返回整個(gè)ID 號(hào)。

（2）Request（prefix）—請求命令，其中prefix為查詢前綴，即擴(kuò)展后的新的查詢字串，滿足查詢前綴的標(biāo)簽響應(yīng)。

（3）Select（prefix）—選擇指令，標(biāo)簽的前綴跟閱讀器發(fā)送的前綴一致，響應(yīng)選擇這個(gè)命令請求。

（4）Rw－date—讀取數(shù)據(jù)指令，閱讀器成功識(shí)別標(biāo)簽后，讀取標(biāo)簽的ID 值。

（5）Unselect—退出選擇命令，被識(shí)別的標(biāo)簽處于退選狀態(tài)，使得標(biāo)簽處于休眠狀態(tài)，不在響應(yīng)任何指令，要重新激活必須使得標(biāo)簽重新進(jìn)入閱讀器范圍。

（6）Extract－Collision－Bit—提取各標(biāo)簽的碰撞位信息發(fā)至各標(biāo)簽，標(biāo)簽返回有碰撞標(biāo)記的位作為新的ID 與閱讀器通信。

2.4 算法步驟

步驟1 閱讀器發(fā)送Request（null），作用范圍類每一個(gè)標(biāo)簽都響應(yīng)該請求命令，并返回ID 中每一位，閱讀器檢測沖突位，把沖突位標(biāo)記為 “1”，無沖突位標(biāo)記 “0”，并初始化查詢棧Q。

步驟2 閱讀器發(fā)送Extract－Collision－Bit指令，沖突信息發(fā)送給標(biāo)簽，標(biāo)簽返回有沖突標(biāo)記的位作為新的ID與閱讀器通信。

步驟3 標(biāo)簽的應(yīng)答產(chǎn)生碰撞，在上一次查詢前綴的基礎(chǔ)上擴(kuò)展3位，形成新的查詢前綴，然后利用時(shí)隙預(yù)先偵測信號(hào)技術(shù)，刪除不需要的前綴，其他需要的前綴置入棧Q。

步驟4 閱讀器取棧頂Q 中的前綴并發(fā)送，如果在應(yīng)答的時(shí)候沒有標(biāo)簽產(chǎn)生碰撞，閱讀器發(fā)送指令使其休眠，則識(shí)別成功；如果標(biāo)簽在應(yīng)答時(shí)產(chǎn)生了碰撞，返回步驟3。

步驟5 判斷棧Q 是否為空，如果不為空，返回步驟4；如果為空，則算法結(jié)束。

2.5 算法舉例

下面通過一個(gè)實(shí)例來詳細(xì)說明算法的實(shí)現(xiàn)過程，假設(shè)有5 個(gè)10 位的標(biāo)簽待識(shí)別，分別為tag1：1000011011；tag2：1100101011；tag3：1100111010；tag4：1100111110；tag5：1101111010。算法的執(zhí)行過程如下：

（1）閱讀器發(fā)送Request（null），，閱讀器作用范圍的標(biāo)簽響應(yīng)，ID 的每一位都都返回來，閱讀器檢測碰撞位信息，把有沖突位標(biāo)記為 “1”，無沖突位標(biāo)記為 “0”。

（2）閱讀器發(fā)送Extract－Collision－Bit指令，tag1、tag2、tag3、tag4、tag5 形 成 新 的ID，分 別 為000101、101001、101100、101110、111100，并與閱讀器通信。

（3）查詢前綴擴(kuò)展3位，利用預(yù)先偵測技術(shù)，刪除不需要的前綴001、010、011、100、110，需要的前綴000、101、111壓入棧Q 中。閱讀器讀取棧Q 中查詢前綴000，生成請求命令Request（000）。

（4）閱讀器發(fā)送Request（000），此時(shí)僅有tag1應(yīng)答，tag1被正確識(shí)別，閱讀器發(fā)送Unselect指令，讓其處于休眠狀態(tài)。閱讀器讀取棧Q 中101，生成新的請求命令Request（101）。

（5）閱 讀 器 發(fā) 送Request （101），此 時(shí)tag2、tag3、tag4應(yīng)答，產(chǎn)生了碰撞，在上一次查詢前綴的基礎(chǔ)上，擴(kuò)展3 位，得到新的查詢前綴101000、101001、101010、101011、101100、101101、101110、101111，利用預(yù)先偵測技術(shù)，刪除101000、101010、101011、101101、101111這些不需要的查詢前綴，需要的查詢前綴101001、101100、101110壓入棧Q 中。閱讀器取棧Q 中的101001，生成新的請求命令Request（101001）。

（6）閱讀器發(fā)送Request（101001），此時(shí)僅有tag2成功識(shí)別，閱讀器發(fā)送指令使其休眠。閱讀器讀取棧Q 中查詢前綴101100，生成命令Request（101100）。

（7）閱讀器發(fā)送Request（101100），此時(shí)僅有tag3成功識(shí)別，閱讀器讀取其數(shù)據(jù)，并發(fā)送指令使其休眠。閱讀器讀取棧Q 中101110，生成命令Request（101110）。

（8）閱讀器發(fā)送Request（101110），此時(shí)只有tag4響應(yīng)，成功識(shí)別，閱讀器讀取數(shù)據(jù)，發(fā)送指令使其休眠。閱讀器讀取棧Q 中查詢前綴111，生成命令Request（111）。

（9）閱讀器發(fā)送Request（111），此時(shí)只有tag5響應(yīng)，成功識(shí)別，閱讀器讀取其數(shù)據(jù)，發(fā)送指令使其休眠。棧Q為空，識(shí)別結(jié)束。

3 實(shí)驗(yàn)分析與仿真

通過時(shí)隙數(shù)和吞吐率的計(jì)算，對(duì)本文的算法的性能進(jìn)行分析。但是一般情況下很難得到一個(gè)精確的公式來計(jì)算。

本文算法利用了預(yù)先偵測查詢樹的方法，刪除了空閑時(shí)隙，因此算法的總時(shí)隙為

系統(tǒng)的吞吐率為

本文的算法是基于PDQT 算法的基礎(chǔ)提出來的，并且BBS算法又是比較經(jīng)典的二進(jìn)制樹型算法，因此把本文提出的算法和這2種算法進(jìn)行了相互之間的比較。利用Matlab仿真軟件對(duì)以上3種算法進(jìn)行理想情況下的仿真實(shí)驗(yàn)。仿真過程中系統(tǒng)的標(biāo)簽假設(shè)分布是均勻的，并且系統(tǒng)采用32位EPC編碼的電子標(biāo)簽。在相同的仿真環(huán)境下，仿真結(jié)果取20次的實(shí)驗(yàn)平均值，分別比較了PDQT、BBS、本文的算法的查詢次數(shù)、吞吐率和通信量，如圖3、圖4、圖5所示。仿真結(jié)果可以看到，本文改進(jìn)的算法，有效的減少了詢問次數(shù)、總的傳輸位數(shù)，系統(tǒng)的效率也就是吞吐率也有了很大的改善，實(shí)驗(yàn)結(jié)果表明，本文改進(jìn)的算法提升了整個(gè)RFID 系統(tǒng)的性能。

圖3 查詢次數(shù)的比較

圖4 吞吐率的比較

圖5 總傳輸位數(shù)的比較

4 結(jié)束語

本文提出了一種改進(jìn)的預(yù)先偵測查詢樹防碰撞算法，創(chuàng)造性地結(jié)合了多種方法，包括八元查詢樹、提取碰撞位、預(yù)先偵測查詢樹、后退式索引、堆棧。這些方法的綜合，無論是閱讀器的詢問次數(shù)、通信量，還是系統(tǒng)的吞吐率都達(dá)到了理想的效果，比改進(jìn)前的算法，具有優(yōu)越性。當(dāng)電子標(biāo)簽的長度和數(shù)量逐漸增加時(shí)，本文提出的算法的性能的優(yōu)勢就更明顯。因此，該算法具有一定的實(shí)用性和創(chuàng)新性。

［1］YU Songsen，ZHAN Yiju，PENG Weidong，et al.An anticollision based on binary tree searching of regressive index and its practice［J］.Computer Engineering and Application，2004，40 （16）：26－28 （in Chinese）. ［余 松 森，詹 宜 巨，彭 衛(wèi) 東，等.基于后退索引的二進(jìn)制樹形搜索防碰撞算法及其實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40 （16）：26－28.］

［2］WANG Quan，HUA Nan.A new anticollision algorithm based on the quaternary query tree a algorithm ［J］.Journal of Air Force Engineering University （Natural Science Edition），2012，13 （6）：75－79 （in Chinese）.［王荃，滑楠.基于四元查詢樹算法的改進(jìn)防碰撞算法 ［J］.空軍工程大學(xué)學(xué)報(bào) （自然科版），2012，13 （6）：75－79.］

［3］ZHOU Qing，CAI Ming.Improved hybrid query tree anticollision algorithm in RFID system ［J］.Computer Engineering and Design，2012，33 （1）：209－212 （in Chinese）.［周清，蔡明.改進(jìn)的RFID 混合查詢樹防碰撞算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33 （1）：209－212.］

［4］XIANG Chuiyi，HE Yigang，LI Bing，et al.Improvement of dynamic binary system tree search algorithm ［J］.Computer Engineering，2010，36 （2）：260－264 （in Chinese）.［向垂益，何怡剛，李兵，等.動(dòng)態(tài)二進(jìn)制樹搜搜算法的改進(jìn) ［J］.計(jì)算機(jī)工程，2010，36 （2）：260－264.］

［5］SUN Wensheng，LIU Ting.Improved anticollision algorithm based on binary－tree search ［J］.Computer Engineering，2011，37 （10）：257－259 （in Chinese）.［孫文勝，劉婷.一種改進(jìn)的基于二叉樹搜索樹的防碰撞算法 ［J］.計(jì)算機(jī)工程，2011，37 （10）：257－259.］

［6］Jiho Ryu，Hojin Lee，Yongho Seok.et al.A hybrid query tree protocol for tag collision algorithm in RFID system ［C］／／IEEE International Conference on Communication，2007：5981－5986.

［7］Sung Hyun Kin，Poo Gyeon.Park an efficient tree based tag anticollision protocol for RFID system ［J］.IEEE Communication Letters，2007，11 （5）：449－451

［8］DING Zhiguo，ZHU Xueyong，GUO Li.An adaptive anti－collision algorithm based on multi－tree search ［J］.Acta Automatic Sinica，2010，36 （2）：237－241 （in Chinese）. ［丁治國，朱學(xué)永，郭立.自適應(yīng)多叉樹防碰撞算法研究 ［J］.自動(dòng)化學(xué)報(bào)，2010，36 （2）：237－241.］

［9］CHOI JH，LEE D，LEE H.Query tree based reservation for efficient RFID tag anticollision ［J］.IEEE Communications Letters，2007，11 （1）：85－87.

［10］Klair DK，Read R.An investigation into the energy efficiency of pure and slotted aloha based RFID anticollision protocols［C］／／Proc of IEEE International Symposium on World of Wireless Mobile and Multimedia Networks，2007：1－4.