無(wú)空閑時(shí)隙的動(dòng)態(tài)多叉查詢樹RFID防碰撞算法

牛 愛 民

(山東英才學(xué)院計(jì)算機(jī)電子信息工程學(xué)院　山東 濟(jì)南 250104)

?

無(wú)空閑時(shí)隙的動(dòng)態(tài)多叉查詢樹RFID防碰撞算法

牛 愛 民

(山東英才學(xué)院計(jì)算機(jī)電子信息工程學(xué)院山東 濟(jì)南 250104)

摘要為了提高RFID系統(tǒng)識(shí)別標(biāo)簽的效率，提出一種無(wú)空閑時(shí)隙的動(dòng)態(tài)多叉查詢樹RFID防碰撞算法DMQT。該算法根據(jù)碰撞位的特征動(dòng)態(tài)調(diào)整樹分裂的叉數(shù)，能夠有效地減少碰撞時(shí)隙。通過跟蹤標(biāo)簽的碰撞位來避免不存在標(biāo)簽的分支，從而可以消除空閑時(shí)隙。理論和仿真分析可以看到，該算法具有很小的識(shí)別時(shí)隙和較大的吞吐率，算法性能優(yōu)于目前存在的RFID防碰撞算法。

關(guān)鍵詞射頻識(shí)別防碰撞算法多叉查詢樹

0引言

RFID由于具有非接觸性、方便快速、可靠性好等優(yōu)點(diǎn)，已經(jīng)廣泛地應(yīng)用于自動(dòng)識(shí)別領(lǐng)域。一個(gè)典型的RFID系統(tǒng)包括閱讀器、標(biāo)簽和后臺(tái)服務(wù)器。后臺(tái)服務(wù)器與閱讀器進(jìn)行可靠連接，它主要負(fù)責(zé)管理和處理數(shù)據(jù)；標(biāo)簽與物品綁定，記錄物品的一些信息，每個(gè)標(biāo)簽具有唯一的ID號(hào)；閱讀器通過無(wú)線方式讀寫標(biāo)簽中的信息，當(dāng)多個(gè)標(biāo)簽同時(shí)響應(yīng)閱讀器的查詢時(shí)將發(fā)生碰撞，這是由于標(biāo)簽都使用同一無(wú)線信道。發(fā)生碰撞時(shí)閱讀器將不能正常讀取標(biāo)簽中信息。目前主要存在兩類防碰撞算法：基于aloha防碰撞算法[1,2]和基于樹防碰撞算法[3-5]。基于aloha防碰撞算法在發(fā)生碰撞時(shí)，標(biāo)簽隨機(jī)選擇一個(gè)時(shí)隙進(jìn)行響應(yīng)，這類防碰撞算法的識(shí)別效率普遍偏低。當(dāng)存在大量標(biāo)簽時(shí)，有些標(biāo)簽可能很長(zhǎng)時(shí)間不能被識(shí)別，這種現(xiàn)象稱為“標(biāo)簽餓死”現(xiàn)象。目前這類算法提高識(shí)別效率的方法是從估計(jì)待識(shí)別標(biāo)簽數(shù)量出發(fā)，采用某種合適的方式讓標(biāo)簽選擇不同的時(shí)隙，以減少再次發(fā)生碰撞的概率[6,7]?；跇浞琅鲎菜惴ㄊ且环N確定性的防碰撞算法，不存在“標(biāo)簽餓死”現(xiàn)象?；跇浞琅鲎菜惴ǖ幕舅悸肥遣粩嗟貙?biāo)簽分成不同組，直到一個(gè)組中只有一個(gè)標(biāo)簽或者沒有標(biāo)簽。查詢樹防碰撞算法[8-10]是一類非常優(yōu)秀的基于樹防碰撞算法。在查詢樹算法中，閱讀器發(fā)送一個(gè)查詢前綴，標(biāo)簽檢測(cè)自己的ID號(hào)是否包含該查詢前綴，如果包含則傳送自己的ID，閱讀器隨后不斷更新和發(fā)送新的查詢前綴，直到識(shí)別所有標(biāo)簽?；静樵儤浞琅鲎菜惴ǖ淖R(shí)別效率不高，但許多研究者在此基礎(chǔ)上提出了效率非常高的查詢樹算法。CT算法[11]是非常優(yōu)秀的二叉查詢樹防碰撞算法。CT算法與基本查詢樹算法的分裂點(diǎn)不同，基本查詢樹算法是逐位分裂二叉樹，CT算法是在最高碰撞位分裂二叉樹，并且標(biāo)簽響應(yīng)不包含前綴的ID剩余位，CT算法的識(shí)別效率達(dá)到了50%。I4QTA算法[12]是一個(gè)基于四叉查詢樹防碰撞算法，當(dāng)發(fā)生兩位連續(xù)碰撞時(shí)，標(biāo)簽采用位變換的方式來減少空閑時(shí)隙，大大提高了識(shí)別效率。A4PQT算法[13]也是一個(gè)基于四叉查詢樹防碰撞算法，已經(jīng)證明三叉樹是最優(yōu)的識(shí)別樹，但不存在三叉樹分裂方式。A4PQT算法就是利用三叉樹最優(yōu)分裂原理，剪去四叉樹中的某些分支，使之接近一個(gè)三叉樹，A4PQT算法也達(dá)到了非常高的識(shí)別效率。OQTT算法[14]也是一種二叉查詢樹防碰撞算法，該算法由三個(gè)部分組成：位估計(jì)、最優(yōu)分裂和查詢跟蹤樹。在識(shí)別開始將標(biāo)簽分成比較小的組，避免在識(shí)別開始出現(xiàn)過多的碰撞位，在每個(gè)組中再采用二叉樹分裂方式，由于采用最優(yōu)的分組方式，該算法的識(shí)別效率高于CT算法。

從上面的分析可以看到，目前一些基于查詢樹防碰撞算法采用了不同叉數(shù)的樹分裂方式，有效率地提高了識(shí)別效率。但是在識(shí)別過程中會(huì)存在不同的連續(xù)碰撞位，這些算法都采用固定的分裂叉數(shù)，采用某種固定叉數(shù)的樹分裂方法可能會(huì)增加一些碰撞時(shí)隙?；诖?，本文提出一個(gè)無(wú)空閑時(shí)隙的動(dòng)態(tài)多叉樹防碰撞算法(DMQT)。DMQT算法根據(jù)最高碰撞位特征動(dòng)態(tài)調(diào)整樹分裂叉樹，并且采用位跟蹤的方式探知標(biāo)簽對(duì)應(yīng)的碰撞位，在下一輪查詢中能夠避免所有的空閑時(shí)隙。從仿真結(jié)果可以看到，DMQT算法性能明顯優(yōu)于現(xiàn)有的查詢樹算法。

1多叉樹防碰撞算法的時(shí)隙

RFID系統(tǒng)將識(shí)別多個(gè)標(biāo)簽的時(shí)間用時(shí)隙來表示，閱讀器在查詢識(shí)別過程中可能存在三種情形：一個(gè)標(biāo)簽響應(yīng)(直接讀取標(biāo)簽信息)、多個(gè)標(biāo)簽響(發(fā)生碰撞，閱讀器不能讀取標(biāo)簽信息)和無(wú)標(biāo)簽響應(yīng)。對(duì)應(yīng)于識(shí)別過程中三種情形，時(shí)隙可以分為可讀時(shí)隙、碰撞時(shí)隙和空閑時(shí)隙?；跇涞姆琅鲎菜惴ㄊ怯脴涞墓?jié)點(diǎn)來表示時(shí)隙，樹的中間節(jié)點(diǎn)都是碰撞時(shí)隙，葉節(jié)點(diǎn)可能是可讀時(shí)隙，也可能是空閑時(shí)隙。減少碰撞時(shí)隙和空閑時(shí)隙可以提高RFID系統(tǒng)的識(shí)別效率。圖1顯示了采用二叉樹、四叉樹和八叉樹識(shí)別5個(gè)標(biāo)簽的識(shí)別過程。在圖1的實(shí)例中，識(shí)別同樣數(shù)量的標(biāo)簽，采用二叉樹分裂方法會(huì)產(chǎn)生3個(gè)碰撞時(shí)隙、1個(gè)空閑時(shí)隙；采用四叉樹分裂方法會(huì)產(chǎn)生2個(gè)碰撞時(shí)隙、5個(gè)空閑時(shí)隙；采用八叉樹分裂方法會(huì)產(chǎn)生1個(gè)碰撞時(shí)隙、10個(gè)空閑時(shí)隙。可以看出，增加樹分裂的叉數(shù)能夠減少碰撞時(shí)隙，但增加了空閑時(shí)隙。因此增加樹的叉數(shù)也不一定能夠減少識(shí)別的總時(shí)隙，在圖1中完全采用二叉樹分裂方式總時(shí)隙為10，完全采用四叉樹分裂方式所需的總時(shí)隙為13，完全采用8叉樹分裂方式所需的總時(shí)隙為17。

圖1　不用叉數(shù)的防碰撞算法識(shí)別過程

(1)

表1　 一個(gè)完全多叉樹分裂所產(chǎn)生的時(shí)隙

當(dāng)樹的叉數(shù)增加，碰撞時(shí)隙減少，空閑時(shí)隙增加，這也給我們一個(gè)啟示：采用多叉樹的優(yōu)點(diǎn)是可以減少碰撞時(shí)隙，不足是增加了空閑時(shí)隙。如果能夠采用某種方式消除多叉樹所產(chǎn)生的空閑時(shí)隙，那么將大大減少多叉樹識(shí)別的總時(shí)隙。從表1也可以看到，當(dāng)沒有空閑時(shí)隙時(shí)，采用二叉樹識(shí)別m個(gè)標(biāo)簽的總時(shí)隙為2.443m，采用三叉樹識(shí)別m個(gè)標(biāo)簽的總時(shí)隙為1.913m，采用四叉樹識(shí)別m個(gè)標(biāo)簽的總時(shí)隙為1.720m，采用五叉樹識(shí)別m個(gè)標(biāo)簽的總時(shí)隙為1.622m。理論上講，如果沒有空閑時(shí)隙，樹的叉數(shù)越多，總時(shí)隙越小，識(shí)別效率越高?；谶@個(gè)思想，本文提出的RFID防碰撞算法在識(shí)別過程中，根據(jù)碰撞位探知發(fā)生碰撞的標(biāo)簽ID信息，在下一輪查詢時(shí)閱讀器可以避開多叉樹產(chǎn)生的空閑時(shí)隙，從而可以消除空閑時(shí)隙，提高RFID系統(tǒng)的識(shí)別效率。

2動(dòng)態(tài)多叉樹防碰撞算法

2.1算法設(shè)計(jì)思路

動(dòng)態(tài)多叉樹防碰撞算法用曼徹斯特編碼跟蹤碰撞位，當(dāng)發(fā)生碰撞時(shí)，多個(gè)標(biāo)簽ID對(duì)應(yīng)位的曼徹斯特編碼將不出現(xiàn)跳變，因此曼徹斯特編碼可以準(zhǔn)確判斷哪些位發(fā)生了碰撞。根據(jù)是否出現(xiàn)連續(xù)碰撞位以及連續(xù)碰撞位的數(shù)量，該算法動(dòng)態(tài)地調(diào)整樹分裂的叉數(shù)。基本分裂原則如下：如果只存在一位最高碰撞位，采用二叉樹分裂方式；如果存在最高兩個(gè)連續(xù)碰撞位，則采用四叉樹分裂方式；如果存在最高三個(gè)連續(xù)碰撞位，則采用八叉樹分裂方式。同理，如果存在最高n個(gè)連續(xù)碰撞位，則采用2n叉樹分裂方式。從第1節(jié)的分析可以看到，如果能夠完全消除空閑時(shí)隙，樹的分裂叉數(shù)越多，系統(tǒng)的識(shí)別效率越高。由于不可能事先知道所有需要識(shí)別標(biāo)簽的ID，所以只能在發(fā)生碰撞時(shí)用某種方式跟蹤標(biāo)簽部分ID分布情況，這樣閱讀器在下一次查詢時(shí)可以避免空閑時(shí)隙。

2.2算法原理及流程

閱讀器在識(shí)別過程中使用兩類查詢，一類是識(shí)別標(biāo)簽查詢，另一類是當(dāng)發(fā)生碰撞時(shí)的位跟蹤查詢。閱讀器用一位標(biāo)識(shí)符來表示這兩類查詢，在查詢的最低位用標(biāo)志“0”表示識(shí)別查詢，用標(biāo)志“1”表示位跟蹤查詢。標(biāo)簽在接收到閱讀器的查詢時(shí)，首先判斷查詢的最低位，如果為“0”，表示為識(shí)別查詢，標(biāo)簽檢查自己ID是否包含閱讀器的查詢前綴(不包括最低標(biāo)志位)，如果包含，標(biāo)簽用不包括查詢前綴的ID剩余位響應(yīng)，否則不響應(yīng)。如果標(biāo)簽檢查到最低查詢位為“1”，表示為位跟蹤查詢，標(biāo)簽將按照下面方式進(jìn)行響應(yīng)。

(1) 當(dāng)只存在一位最高碰撞，閱讀器可以知道這些標(biāo)簽在該碰撞位肯定為0和1。采用二叉樹分裂方式，在下一次查詢時(shí)分別增加兩個(gè)查詢前綴，閱讀器完全可以避免空閑時(shí)隙此時(shí)，閱讀器不需要額外的位跟蹤查詢。

(2) 當(dāng)存在最高n(n≥2)個(gè)連續(xù)碰撞位時(shí)，采用2n叉樹分裂方式。閱讀器跟蹤2n個(gè)分支中是否存在標(biāo)簽，位跟蹤查詢格式為：0…0+1…1+1，其中0…0表示比最高連續(xù)碰撞位高的所有位串，連續(xù)碰撞的位數(shù)用1…1表示，n個(gè)連續(xù)碰撞位用n個(gè)1表示，最后的1位表示探知標(biāo)志符。標(biāo)簽將與位跟蹤查詢中1…1對(duì)應(yīng)的ID位轉(zhuǎn)換成十進(jìn)制數(shù)s，標(biāo)簽生成2n長(zhǎng)的位串傳給閱讀器，其中將位串的第smod2n位設(shè)置為1，其他位都設(shè)置為0。例如當(dāng)n=2時(shí)，采用四叉樹分裂方式，一個(gè)完全四叉樹分裂為00，01，10和11等4個(gè)分支。有些分支可能不存在標(biāo)簽，此時(shí)閱讀器用位跟蹤查詢：0…0+11+1。假設(shè)有兩個(gè)標(biāo)簽為tag1(10010011)和tag2(10100001)，當(dāng)這兩個(gè)標(biāo)簽響應(yīng)閱讀器的識(shí)別查詢時(shí)會(huì)發(fā)生碰撞，閱讀器用曼徹斯特編碼識(shí)別為10xx00x1，其中x表示碰撞位。由于存在的最高兩連續(xù)碰撞位，閱讀器發(fā)送位跟蹤查詢00111，最后“1”表示位跟蹤查詢標(biāo)志。標(biāo)簽在接收到位跟蹤查詢后，不考慮最后的標(biāo)志號(hào)1和前面的00，位跟蹤查詢中的11對(duì)應(yīng)標(biāo)簽tag1(10010011)中的ID位是01。如圖2所示，轉(zhuǎn)換十進(jìn)制數(shù)為1，標(biāo)簽生成22位響應(yīng)消息，將第1mod22位設(shè)置為1，其他位設(shè)置為0，結(jié)果為0010。同樣tag2(10100001)與位跟蹤查詢00111所對(duì)應(yīng)的ID位是10，轉(zhuǎn)換十進(jìn)制數(shù)為2，標(biāo)簽將第2mod22設(shè)置為1，其他位設(shè)置為0，結(jié)果為0100。閱讀器接收到2個(gè)標(biāo)簽的響應(yīng)后，用曼徹斯特編碼可以判斷為0xx0，閱讀器很容易判斷出在4叉樹中只存在01和10兩分分支，在下一輪查詢中閱讀器就能避免空閑時(shí)隙。

圖2　位跟蹤查詢中連續(xù)碰撞位與標(biāo)簽ID的對(duì)應(yīng)位

為了減輕標(biāo)簽對(duì)位跟蹤查詢響應(yīng)的代價(jià)，DMQT算法規(guī)定標(biāo)簽響應(yīng)位長(zhǎng)不超過ID位長(zhǎng)，假設(shè)標(biāo)簽ID位長(zhǎng)為l，那么閱讀器選取的最大連續(xù)碰撞位n應(yīng)滿足：2n≤ l。例如有兩個(gè)標(biāo)簽0110和1001，同時(shí)響應(yīng)閱讀器的識(shí)別查詢，結(jié)果為xxxx，存在最高連續(xù)4個(gè)碰撞位。由于標(biāo)簽的ID位長(zhǎng)為4，所以閱讀器位跟蹤查詢時(shí)只能按照2個(gè)最高連續(xù)位進(jìn)行查詢，標(biāo)簽響應(yīng)位長(zhǎng)為4位(小于或者等于l)。若閱讀器的位跟蹤查詢按照4個(gè)最高連續(xù)位進(jìn)行查詢，標(biāo)簽則產(chǎn)生16位長(zhǎng)的響應(yīng)消息，這種方式顯然增加了標(biāo)簽的通信量。

DMQT算法用堆棧保存閱讀器的查詢前綴，最初將一個(gè)空字符串ε進(jìn)棧，隨后根據(jù)碰撞位特征重復(fù)地壓進(jìn)新的前綴和推出新的查詢前綴。當(dāng)不存在連續(xù)最高碰撞位時(shí)，新的前綴在原前綴(qt)的基礎(chǔ)上擴(kuò)展為qt+0和qt+1。如果存在n位連續(xù)最高碰撞位，閱讀器發(fā)送位跟蹤查詢，閱讀器根據(jù)標(biāo)簽的響應(yīng)擴(kuò)展查詢前綴，擴(kuò)展后的查詢前綴包含響應(yīng)標(biāo)簽所在的分支。在上面的例子中，tag1(10010011)和tag2(10100001)的對(duì)閱讀器位跟蹤查詢后的響應(yīng)分別為0010和0100，那么閱讀器在原前綴(qt)的基礎(chǔ)上擴(kuò)展為qt+01和qt+10；不需要按照完全四叉數(shù)的方式擴(kuò)展為qt+00、qt+01、qt+10和qt+11，可見DMQT算法完全消除了空閑時(shí)隙。算法的流程如圖3所示。

圖3　閱讀器和標(biāo)簽的操作流程

閱讀器操作步驟如下：

① 閱讀器初始化查詢前綴堆棧，并將空字符串ε壓入堆棧；

② 判斷查詢前綴堆棧是否為空，如果為空，轉(zhuǎn)步驟⑨；

③ 前綴q出棧操作，并廣播查詢前綴q+0，其中最后的“0”位表示識(shí)別查詢標(biāo)志；

④ 等待標(biāo)簽響應(yīng)，若無(wú)標(biāo)簽響應(yīng)，轉(zhuǎn)步驟⑨；若有標(biāo)簽響應(yīng)，判斷是否發(fā)送碰撞，如果沒有發(fā)生碰撞，轉(zhuǎn)步驟⑧；如果發(fā)送碰撞，判斷是否存在連續(xù)最高碰撞位，如果不存在連續(xù)最高碰撞位，閱讀器產(chǎn)生新前綴q0,q1，并壓入堆棧；若存在n(n≥2)個(gè)連續(xù)最高碰撞位，轉(zhuǎn)步驟⑤。

⑤ 發(fā)送位跟蹤查詢0…0+1…1+1，其中，0…0表示比最高連續(xù)碰撞位高的所有位， 1…1表示n個(gè)連續(xù)碰撞位，最后的“1”位表示位跟蹤查詢標(biāo)志；

⑥ 接收到標(biāo)簽響應(yīng)，用曼徹斯特編碼判斷哪些分支存在標(biāo)簽，根據(jù)有標(biāo)簽響應(yīng)的分支產(chǎn)生新的查詢前綴，新前綴=原前綴+分支位串，并壓入堆棧；

⑦ 重復(fù)上面步驟②-步驟⑥；

⑧ 識(shí)別一個(gè)標(biāo)簽；

⑨ 結(jié)束。

標(biāo)簽操作步驟如下：

① 等待查詢；

② 根據(jù)最后標(biāo)志位判斷閱讀器的查詢類型，若標(biāo)志位為“1”，轉(zhuǎn)步驟④；若標(biāo)志位為“0”，轉(zhuǎn)步驟③；

③ 檢測(cè)查詢前綴是否匹配自己的ID，如果不匹配，轉(zhuǎn)步驟①；如果匹配，傳送不包括前綴后的ID剩余位；

④ 標(biāo)簽根據(jù)位跟蹤查詢0…0+1…1+1，找出1…1與ID中的對(duì)應(yīng)位，并轉(zhuǎn)換成十進(jìn)制數(shù)s，生成2n長(zhǎng)的位串，將smod2n,位設(shè)置為1，其他位設(shè)置為0，并傳送給閱讀器。

2.3DMQT算法舉例

現(xiàn)舉例說明動(dòng)態(tài)多叉樹防碰撞算法的識(shí)別過程，假設(shè)存在6個(gè)標(biāo)簽分別是：t1(11000001)、t2(11100011)、t3(10110101)、t4(11010001)、t5(11110010)和t6(10010010)。當(dāng)閱讀器用空字符串ε查詢時(shí)，所有標(biāo)簽響應(yīng)，閱讀器用曼特斯特編碼判斷結(jié)果為1xxx0xxx，其中x表示碰撞位。由于存在3位最高連續(xù)位，閱讀器發(fā)送位跟蹤查詢01111，最后一位“1”表示位跟蹤查詢的標(biāo)志位。標(biāo)簽接收到探知查詢后，去掉探知查詢標(biāo)志位后選取與“111”對(duì)應(yīng)的ID位，t1對(duì)應(yīng)的ID位為100(十進(jìn)制數(shù)4)，將4 mod 23設(shè)置為1，其他位設(shè)置為0，結(jié)果為00010000。同樣，t2轉(zhuǎn)換為01000000，t3轉(zhuǎn)換為00001000，t4轉(zhuǎn)換為00100000，t5轉(zhuǎn)換為10000000，t6轉(zhuǎn)換為00000010。閱讀器在接收到標(biāo)簽響應(yīng)后，生成新的查詢前綴，如此繼續(xù)，直到識(shí)別所有標(biāo)簽。識(shí)別過程如表2所示，對(duì)應(yīng)的識(shí)別樹如圖4所示。

表2　DMQT算法識(shí)別標(biāo)簽過程

圖4　DMQT算法的識(shí)別樹

3DMQT算法性能分析

RFID防碰撞算法的性能指標(biāo)主要包括總時(shí)隙和吞吐率。DMQT算法識(shí)別標(biāo)簽過程中采取的分裂叉數(shù)是動(dòng)態(tài)的，這里首先分析算法最小總時(shí)隙和最大總時(shí)隙。假設(shè)標(biāo)簽數(shù)量為m，標(biāo)簽ID長(zhǎng)l=96位，可以發(fā)現(xiàn)最大分裂的連續(xù)碰撞位數(shù)n滿足2n≤l，可得n=6，由于動(dòng)態(tài)多叉樹RFID防碰撞算法能夠避免所有空隙時(shí)隙，并且n當(dāng)越大時(shí)，碰撞時(shí)隙越少，顯然當(dāng)n=6時(shí)所需要的總時(shí)隙最小。當(dāng)n=6時(shí)，算法按照26=64叉樹分裂，算法的滿64叉樹的內(nèi)部節(jié)點(diǎn)度為64，葉節(jié)點(diǎn)度為0，用m1表示度為64的節(jié)點(diǎn)。由于不存在空閑時(shí)隙，葉節(jié)點(diǎn)數(shù)與待識(shí)別標(biāo)簽數(shù)m相等。因此滿64叉樹的總節(jié)點(diǎn)數(shù)為：M=m1+m。另外，度為64的節(jié)點(diǎn)有64個(gè)孩子，加上一個(gè)根節(jié)點(diǎn)，那么滿64叉樹的總節(jié)點(diǎn)數(shù)也可以表示為：M= 64m1+1。因此有：m1+m=64m1+1，m1=(m-1)/63。

由于不存在空閑時(shí)隙，中間節(jié)點(diǎn)數(shù)m1等于碰撞時(shí)隙數(shù)。當(dāng)存在最高連續(xù)碰撞位時(shí)，DMQT算法增加了一次位跟蹤查詢，因此，總的位跟蹤查詢次數(shù)等于碰撞時(shí)隙數(shù)。可以得到滿64叉樹的總時(shí)隙為：碰撞時(shí)隙+可讀時(shí)隙+位跟蹤查詢時(shí)隙，即為：

(2)

最小連續(xù)碰撞位是2位，當(dāng)只存在最高兩位連續(xù)碰撞位時(shí)，DMQT算法采用4叉樹分裂方式。這時(shí)也需要采用位跟蹤查詢，與滿64叉樹分析類似，可以得到滿4叉樹的總時(shí)隙為：碰撞時(shí)隙+可讀時(shí)隙+位跟蹤查詢時(shí)隙，即為：

(3)

當(dāng)只存在一位最高碰撞位時(shí)，DMQT算法采用二叉樹分裂方式，閱讀器不需要額外的位跟蹤查詢。這時(shí)內(nèi)部節(jié)點(diǎn)度為2，葉節(jié)點(diǎn)度為0，總節(jié)點(diǎn)數(shù)為：M=m1+m。其中m1表示度為2的節(jié)點(diǎn)，m表示葉節(jié)點(diǎn)，也是待識(shí)別標(biāo)簽數(shù)。度為2的節(jié)點(diǎn)有2個(gè)孩子，加上一個(gè)根節(jié)點(diǎn)，總節(jié)點(diǎn)數(shù)也表示為：M= 2m1+1。可以得到中間節(jié)點(diǎn)數(shù)m1=m-1，因此算法所需要的總時(shí)隙為：碰撞時(shí)隙+可讀時(shí)隙，即為：T2=m-1+m=2m-1。

吞吐率表示單位時(shí)隙內(nèi)識(shí)別標(biāo)簽數(shù)，DMQT算法的吞吐率表示為：S=m/T。

下面通過實(shí)驗(yàn)仿真比較幾個(gè)算法的識(shí)別性能，隨機(jī)生成96位長(zhǎng)的標(biāo)簽，標(biāo)簽數(shù)量范圍為100～1000，比較DMQT算法與CT、A4PQT和OQTT等算法的總時(shí)隙和吞吐率。仿真結(jié)果如圖5、圖6所示。

圖5　DMQT算法與CT、A4PQT和OQTT等算法的總時(shí)隙

圖6　DMQT算法與CT、A4PQT和OQTT等算法的吞吐率

從圖5中可以看到，DMQT算法識(shí)別相同的標(biāo)簽所需要的總時(shí)隙少于CT、A4PQT和OQTT等算法的總時(shí)隙。當(dāng)識(shí)別1000個(gè)標(biāo)簽時(shí)，DMQT算法所需要的總時(shí)隙約為1510，CT算法的總時(shí)隙約為2000，A4PQT算法所需要的總時(shí)隙約為1590，OQTT算法所需要的總時(shí)隙約為1630。究其原因可以發(fā)現(xiàn)，CT算法是一個(gè)二叉樹防碰撞算法，當(dāng)發(fā)生碰撞時(shí)，在最高碰撞位將標(biāo)簽分裂成2組，CT算法的最大優(yōu)點(diǎn)是能夠消除所有的空閑時(shí)隙，但由于采用二叉樹分裂方式，所以存在較多的碰撞時(shí)隙。OQTT算法為了減少過多的碰撞位，對(duì)待識(shí)別標(biāo)簽進(jìn)行最優(yōu)分組，其識(shí)別總時(shí)隙小于CT算法，但由于OQTT算法還是基于二叉樹分裂方式，因此存在過多的碰撞時(shí)隙。A4PQT是基于四叉樹防碰撞算法，基于四叉樹防碰撞算法比基于二叉樹防碰撞算法具有較少的碰撞時(shí)隙，但增加了空閑時(shí)隙，A4PQT算法采用剪枝的方式消除部分空閑時(shí)隙，因而其總時(shí)隙少于CT和OQTT算法的總時(shí)隙。DMQT算法則動(dòng)態(tài)調(diào)整分裂樹叉樹，采用跟蹤標(biāo)簽碰撞位的方法消除空閑時(shí)隙，因此DMQT算法的總時(shí)隙小于其他3個(gè)算法。從圖6也可以看到，DMQT算法吞吐率也明顯高于其他3個(gè)算法，DMQT算法吞吐率約為0.66，CT、A4PQT和OQTT等算法的吞吐率分別約為0.5,0.63和0.61。

4結(jié)語(yǔ)

在RFID系統(tǒng)中，設(shè)計(jì)一個(gè)有效的防碰撞算法能夠提高對(duì)標(biāo)簽識(shí)別的效率。本文提出了一個(gè)無(wú)空閑時(shí)隙的動(dòng)態(tài)多叉樹防碰撞算法，DMQT算法在識(shí)別過程中根據(jù)碰撞位特征動(dòng)態(tài)調(diào)整查詢樹分裂叉數(shù)，能夠有效地減少了碰撞時(shí)隙。在碰撞發(fā)生時(shí)，跟蹤標(biāo)簽對(duì)應(yīng)的碰撞位，這樣閱讀器在下次查詢時(shí)能夠避免不存在的分支搜索，從而消除了空閑時(shí)隙。從理論分析和仿真實(shí)驗(yàn)可以看到，DMQT算法具有較小的總時(shí)隙和較大的吞吐率，性能優(yōu)于其他防碰撞算法。

參考文獻(xiàn)

[1]ZhuL,YumTP.Optimalframedalohabasedanti-collisionalgorithmsforRFIDsystems[J].IEEETransactionsonCommunications,2010,58(12):3583-3592.

[2]EomJB,LeeTJ,RietmanR,etal.Anefficientframed-slottedALOHAalgorithmwithpilotframeandbinaryselectionforanti-collisionofRFIDtags[J].IEEECommunicationsLetters,2008,12(11):861-863.

[3]LaiYC,HsiaoLY,LinBS.AnRFIDanti-collisionalgorithmwithdynamiccondensationandorderingbinarytree[J].ComputerCommunications,2013,36(17):1754-1767.

[4]LaiYC,LinCC.Twoblockingalgorithmsonadaptivebinarysplitting:singleandpairresolutionsforRFIDtagidentification[J].IEEE/ACMTransactionsonNetworking(TON),2009,17(3):962-975.

[5]LandaluceH,PerallosA,AnguloI.ManagingtheNumberofTagBitsTransmittedinaBit-TrackingRFIDCollisionResolutionProtocol[J].Sensors,2014,14(1):1010-1027.

[6]EomJB,LeeTJ.Accuratetagestimationfordynamicframed-slottedALOHAinRFIDsystems[J].IEEECommunicationsLetters,2010,14(1):60-62.

[7]MotaRPB,BatistaDM.AdynamicframeslottedALOHAanti-collisionalgorithmfortheinternetofthings[C]//Proceedingsofthe29thAnnualACMSymposiumonAppliedComputing.ACM,2014:686-691.

[8]ChoiJH,LeeD,LeeH.Querytree-basedreservationforefficientRFIDtaganti-collision[J].IEEECommunicationsLetters,2007,11(1):85-87.

[9]LiuX,QianZ,ZhaoY,etal.Anadaptivetaganti-collisionprotocolinRFIDwirelesssystems[J].ChinaCommunications,2014,11(7):117-127.

[10]YehMK,JiangJR.ANovelQueryTreeProtocolBasedonPartialResponsesforRFIDTagAnti-Collision[C]//ProceedingsoftheInternationalConferenceonParallelandDistributedSystems(ICPADS).IEEE,2013:617-622.

[11]JiaX,FengQ,YuL.Stabilityanalysisofanefficientanti-collisionprotocolforRFIDtagidentification[J].IEEETransactionsonCommunications,2012,60(8):2285-2294.

[12]KimY,KimS,LeeS,etal.Improved4-aryquerytreealgorithmforanti-collisioninRFIDsystem[C]//ProceedingsoftheInternationalConferenceonAdvancedInformationNetworkingandApplications.IEEE,2009:699-704.

[13]ZhangW,GuoY,TangX,etal.AnEfficientAdaptiveAnticollisionAlgorithmBasedon4-AryPruningQueryTree[J].InternationalJournalofDistributedSensorNetworks,2013,11(12):1-7.

[14]LaiYC,HsiaoLY,ChenHJ,etal.AnovelquerytreeprotocolwithbittrackinginRFIDtagidentification[J].IEEETransactionsonMobileComputing,2013,12(10):2063-2075.

[15]HushDR,WoodC.AnalysisoftreealgorithmsforRFIDarbitration[C]//ProceedingsoftheIEEEInternationalSymposiumonInformationTheory,1998,107-116.

DYNAMIC N-ARY QUERY TREE RFID ANTI-COLLISIONALGORITHMWITHOUTIDLETIMESLOTS

Niu Aimin

(School of Computer Electronics and Information Engineering,Shandong Yingcai University,Jinan 250104,Shandong,China)

AbstractIn order to improve the efficiency of RFID system in identifying tags,this paper presents a dynamic n-ary query tree RFID anticollision algorithm without idle timeslots (DMQT).DMQT adjusts dynamically the number of branches of the tree according to the characteristics of collision bits,and is able to reduce effectively the collision timeslots.DMQT avoids some branch that tags do not exist by tracking the tag collision bits,so that it can eliminate all the idle timeslots.It can be seen from theoretical and simulation analyses that DMQT has a small total timeslots and larger throughput,its performance outperforms existing RFID anti-collision algorithms.

KeywordsRFIDAnti-collision algorithmN-ary query tree

收稿日期：2014-11-11。山東省高等學(xué)?？萍加?jì)劃項(xiàng)目(J13LN55)。牛愛民，講師，主研領(lǐng)域：物聯(lián)網(wǎng)，人工智能。

中圖分類號(hào)TP309

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.06.066