牛 愛 民
(山東英才學院計算機電子信息工程學院 山東 濟南 250104)
?
無空閑時隙的動態多叉查詢樹RFID防碰撞算法
牛 愛 民
(山東英才學院計算機電子信息工程學院山東 濟南 250104)
摘要為了提高RFID系統識別標簽的效率,提出一種無空閑時隙的動態多叉查詢樹RFID防碰撞算法DMQT。該算法根據碰撞位的特征動態調整樹分裂的叉數,能夠有效地減少碰撞時隙。通過跟蹤標簽的碰撞位來避免不存在標簽的分支,從而可以消除空閑時隙。理論和仿真分析可以看到,該算法具有很小的識別時隙和較大的吞吐率,算法性能優于目前存在的RFID防碰撞算法。
關鍵詞射頻識別防碰撞算法多叉查詢樹
0引言
RFID由于具有非接觸性、方便快速、可靠性好等優點,已經廣泛地應用于自動識別領域。一個典型的RFID系統包括閱讀器、標簽和后臺服務器。后臺服務器與閱讀器進行可靠連接,它主要負責管理和處理數據;標簽與物品綁定,記錄物品的一些信息,每個標簽具有唯一的ID號;閱讀器通過無線方式讀寫標簽中的信息,當多個標簽同時響應閱讀器的查詢時將發生碰撞,這是由于標簽都使用同一無線信道。發生碰撞時閱讀器將不能正常讀取標簽中信息。目前主要存在兩類防碰撞算法:基于aloha防碰撞算法[1,2]和基于樹防碰撞算法[3-5]。基于aloha防碰撞算法在發生碰撞時,標簽隨機選擇一個時隙進行響應,這類防碰撞算法的識別效率普遍偏低。當存在大量標簽時,有些標簽可能很長時間不能被識別,這種現象稱為“標簽餓死”現象。目前這類算法提高識別效率的方法是從估計待識別標簽數量出發,采用某種合適的方式讓標簽選擇不同的時隙,以減少再次發生碰撞的概率[6,7]。基于樹防碰撞算法是一種確定性的防碰撞算法,不存在“標簽餓死”現象?;跇浞琅鲎菜惴ǖ幕舅悸肥遣粩嗟貙撕灧殖刹煌M,直到一個組中只有一個標簽或者沒有標簽。查詢樹防碰撞算法[8-10]是一類非常優秀的基于樹防碰撞算法。在查詢樹算法中,閱讀器發送一個查詢前綴,標簽檢測自己的ID號是否包含該查詢前綴,如果包含則傳送自己的ID,閱讀器隨后不斷更新和發送新的查詢前綴,直到識別所有標簽。基本查詢樹防碰撞算法的識別效率不高,但許多研究者在此基礎上提出了效率非常高的查詢樹算法。CT算法[11]是非常優秀的二叉查詢樹防碰撞算法。CT算法與基本查詢樹算法的分裂點不同,基本查詢樹算法是逐位分裂二叉樹,CT算法是在最高碰撞位分裂二叉樹,并且標簽響應不包含前綴的ID剩余位,CT算法的識別效率達到了50%。I4QTA算法[12]是一個基于四叉查詢樹防碰撞算法,當發生兩位連續碰撞時,標簽采用位變換的方式來減少空閑時隙,大大提高了識別效率。A4PQT算法[13]也是一個基于四叉查詢樹防碰撞算法,已經證明三叉樹是最優的識別樹,但不存在三叉樹分裂方式。A4PQT算法就是利用三叉樹最優分裂原理,剪去四叉樹中的某些分支,使之接近一個三叉樹,A4PQT算法也達到了非常高的識別效率。OQTT算法[14]也是一種二叉查詢樹防碰撞算法,該算法由三個部分組成:位估計、最優分裂和查詢跟蹤樹。在識別開始將標簽分成比較小的組,避免在識別開始出現過多的碰撞位,在每個組中再采用二叉樹分裂方式,由于采用最優的分組方式,該算法的識別效率高于CT算法。
從上面的分析可以看到,目前一些基于查詢樹防碰撞算法采用了不同叉數的樹分裂方式,有效率地提高了識別效率。但是在識別過程中會存在不同的連續碰撞位,這些算法都采用固定的分裂叉數,采用某種固定叉數的樹分裂方法可能會增加一些碰撞時隙?;诖?,本文提出一個無空閑時隙的動態多叉樹防碰撞算法(DMQT)。DMQT算法根據最高碰撞位特征動態調整樹分裂叉樹,并且采用位跟蹤的方式探知標簽對應的碰撞位,在下一輪查詢中能夠避免所有的空閑時隙。從仿真結果可以看到,DMQT算法性能明顯優于現有的查詢樹算法。
1多叉樹防碰撞算法的時隙
RFID系統將識別多個標簽的時間用時隙來表示,閱讀器在查詢識別過程中可能存在三種情形:一個標簽響應(直接讀取標簽信息)、多個標簽響(發生碰撞,閱讀器不能讀取標簽信息)和無標簽響應。對應于識別過程中三種情形,時隙可以分為可讀時隙、碰撞時隙和空閑時隙?;跇涞姆琅鲎菜惴ㄊ怯脴涞墓濣c來表示時隙,樹的中間節點都是碰撞時隙,葉節點可能是可讀時隙,也可能是空閑時隙。減少碰撞時隙和空閑時隙可以提高RFID系統的識別效率。圖1顯示了采用二叉樹、四叉樹和八叉樹識別5個標簽的識別過程。在圖1的實例中,識別同樣數量的標簽,采用二叉樹分裂方法會產生3個碰撞時隙、1個空閑時隙;采用四叉樹分裂方法會產生2個碰撞時隙、5個空閑時隙;采用八叉樹分裂方法會產生1個碰撞時隙、10個空閑時隙??梢钥闯?,增加樹分裂的叉數能夠減少碰撞時隙,但增加了空閑時隙。因此增加樹的叉數也不一定能夠減少識別的總時隙,在圖1中完全采用二叉樹分裂方式總時隙為10,完全采用四叉樹分裂方式所需的總時隙為13,完全采用8叉樹分裂方式所需的總時隙為17。

圖1 不用叉數的防碰撞算法識別過程

(1)


表1 一個完全多叉樹分裂所產生的時隙
當樹的叉數增加,碰撞時隙減少,空閑時隙增加,這也給我們一個啟示:采用多叉樹的優點是可以減少碰撞時隙,不足是增加了空閑時隙。如果能夠采用某種方式消除多叉樹所產生的空閑時隙,那么將大大減少多叉樹識別的總時隙。從表1也可以看到,當沒有空閑時隙時,采用二叉樹識別m個標簽的總時隙為2.443m,采用三叉樹識別m個標簽的總時隙為1.913m,采用四叉樹識別m個標簽的總時隙為1.720m,采用五叉樹識別m個標簽的總時隙為1.622m。理論上講,如果沒有空閑時隙,樹的叉數越多,總時隙越小,識別效率越高?;谶@個思想,本文提出的RFID防碰撞算法在識別過程中,根據碰撞位探知發生碰撞的標簽ID信息,在下一輪查詢時閱讀器可以避開多叉樹產生的空閑時隙,從而可以消除空閑時隙,提高RFID系統的識別效率。
2動態多叉樹防碰撞算法
2.1算法設計思路
動態多叉樹防碰撞算法用曼徹斯特編碼跟蹤碰撞位,當發生碰撞時,多個標簽ID對應位的曼徹斯特編碼將不出現跳變,因此曼徹斯特編碼可以準確判斷哪些位發生了碰撞。根據是否出現連續碰撞位以及連續碰撞位的數量,該算法動態地調整樹分裂的叉數。基本分裂原則如下:如果只存在一位最高碰撞位,采用二叉樹分裂方式;如果存在最高兩個連續碰撞位,則采用四叉樹分裂方式;如果存在最高三個連續碰撞位,則采用八叉樹分裂方式。同理,如果存在最高n個連續碰撞位,則采用2n叉樹分裂方式。從第1節的分析可以看到,如果能夠完全消除空閑時隙,樹的分裂叉數越多,系統的識別效率越高。由于不可能事先知道所有需要識別標簽的ID,所以只能在發生碰撞時用某種方式跟蹤標簽部分ID分布情況,這樣閱讀器在下一次查詢時可以避免空閑時隙。
2.2算法原理及流程
閱讀器在識別過程中使用兩類查詢,一類是識別標簽查詢,另一類是當發生碰撞時的位跟蹤查詢。閱讀器用一位標識符來表示這兩類查詢,在查詢的最低位用標志“0”表示識別查詢,用標志“1”表示位跟蹤查詢。標簽在接收到閱讀器的查詢時,首先判斷查詢的最低位,如果為“0”,表示為識別查詢,標簽檢查自己ID是否包含閱讀器的查詢前綴(不包括最低標志位),如果包含,標簽用不包括查詢前綴的ID剩余位響應,否則不響應。如果標簽檢查到最低查詢位為“1”,表示為位跟蹤查詢,標簽將按照下面方式進行響應。
(1) 當只存在一位最高碰撞,閱讀器可以知道這些標簽在該碰撞位肯定為0和1。采用二叉樹分裂方式,在下一次查詢時分別增加兩個查詢前綴,閱讀器完全可以避免空閑時隙此時,閱讀器不需要額外的位跟蹤查詢。
(2) 當存在最高n(n≥2)個連續碰撞位時,采用2n叉樹分裂方式。閱讀器跟蹤2n個分支中是否存在標簽,位跟蹤查詢格式為:0…0+1…1+1,其中0…0表示比最高連續碰撞位高的所有位串,連續碰撞的位數用1…1表示,n個連續碰撞位用n個1表示,最后的1位表示探知標志符。標簽將與位跟蹤查詢中1…1對應的ID位轉換成十進制數s,標簽生成2n長的位串傳給閱讀器,其中將位串的第smod2n位設置為1,其他位都設置為0。例如當n=2時,采用四叉樹分裂方式,一個完全四叉樹分裂為00,01,10和11等4個分支。有些分支可能不存在標簽,此時閱讀器用位跟蹤查詢:0…0+11+1。假設有兩個標簽為tag1(10010011)和tag2(10100001),當這兩個標簽響應閱讀器的識別查詢時會發生碰撞,閱讀器用曼徹斯特編碼識別為10xx00x1,其中x表示碰撞位。由于存在的最高兩連續碰撞位,閱讀器發送位跟蹤查詢00111,最后“1”表示位跟蹤查詢標志。標簽在接收到位跟蹤查詢后,不考慮最后的標志號1和前面的00,位跟蹤查詢中的11對應標簽tag1(10010011)中的ID位是01。如圖2所示,轉換十進制數為1,標簽生成22位響應消息,將第1mod22位設置為1,其他位設置為0,結果為0010。同樣tag2(10100001)與位跟蹤查詢00111所對應的ID位是10,轉換十進制數為2,標簽將第2mod22設置為1,其他位設置為0,結果為0100。閱讀器接收到2個標簽的響應后,用曼徹斯特編碼可以判斷為0xx0,閱讀器很容易判斷出在4叉樹中只存在01和10兩分分支,在下一輪查詢中閱讀器就能避免空閑時隙。

圖2 位跟蹤查詢中連續碰撞位與標簽ID的對應位
為了減輕標簽對位跟蹤查詢響應的代價,DMQT算法規定標簽響應位長不超過ID位長,假設標簽ID位長為l,那么閱讀器選取的最大連續碰撞位n應滿足:2n≤ l。例如有兩個標簽0110和1001,同時響應閱讀器的識別查詢,結果為xxxx,存在最高連續4個碰撞位。由于標簽的ID位長為4,所以閱讀器位跟蹤查詢時只能按照2個最高連續位進行查詢,標簽響應位長為4位(小于或者等于l)。若閱讀器的位跟蹤查詢按照4個最高連續位進行查詢,標簽則產生16位長的響應消息,這種方式顯然增加了標簽的通信量。
DMQT算法用堆棧保存閱讀器的查詢前綴,最初將一個空字符串ε進棧,隨后根據碰撞位特征重復地壓進新的前綴和推出新的查詢前綴。當不存在連續最高碰撞位時,新的前綴在原前綴(qt)的基礎上擴展為qt+0和qt+1。如果存在n位連續最高碰撞位,閱讀器發送位跟蹤查詢,閱讀器根據標簽的響應擴展查詢前綴,擴展后的查詢前綴包含響應標簽所在的分支。在上面的例子中,tag1(10010011)和tag2(10100001)的對閱讀器位跟蹤查詢后的響應分別為0010和0100,那么閱讀器在原前綴(qt)的基礎上擴展為qt+01和qt+10;不需要按照完全四叉數的方式擴展為qt+00、qt+01、qt+10和qt+11,可見DMQT算法完全消除了空閑時隙。算法的流程如圖3所示。

圖3 閱讀器和標簽的操作流程
閱讀器操作步驟如下:
① 閱讀器初始化查詢前綴堆棧,并將空字符串ε壓入堆棧;
② 判斷查詢前綴堆棧是否為空,如果為空,轉步驟⑨;
③ 前綴q出棧操作,并廣播查詢前綴q+0,其中最后的“0”位表示識別查詢標志;
④ 等待標簽響應,若無標簽響應,轉步驟⑨;若有標簽響應,判斷是否發送碰撞,如果沒有發生碰撞,轉步驟⑧;如果發送碰撞,判斷是否存在連續最高碰撞位,如果不存在連續最高碰撞位,閱讀器產生新前綴q0,q1,并壓入堆棧;若存在n(n≥2)個連續最高碰撞位,轉步驟⑤。
⑤ 發送位跟蹤查詢0…0+1…1+1,其中,0…0表示比最高連續碰撞位高的所有位, 1…1表示n個連續碰撞位,最后的“1”位表示位跟蹤查詢標志;
⑥ 接收到標簽響應,用曼徹斯特編碼判斷哪些分支存在標簽,根據有標簽響應的分支產生新的查詢前綴,新前綴=原前綴+分支位串,并壓入堆棧;
⑦ 重復上面步驟②-步驟⑥;
⑧ 識別一個標簽;
⑨ 結束。
標簽操作步驟如下:
① 等待查詢;
② 根據最后標志位判斷閱讀器的查詢類型,若標志位為“1”,轉步驟④;若標志位為“0”,轉步驟③;
③ 檢測查詢前綴是否匹配自己的ID,如果不匹配,轉步驟①;如果匹配,傳送不包括前綴后的ID剩余位;
④ 標簽根據位跟蹤查詢0…0+1…1+1,找出1…1與ID中的對應位,并轉換成十進制數s,生成2n長的位串,將smod2n,位設置為1,其他位設置為0,并傳送給閱讀器。
2.3DMQT算法舉例
現舉例說明動態多叉樹防碰撞算法的識別過程,假設存在6個標簽分別是:t1(11000001)、t2(11100011)、t3(10110101)、t4(11010001)、t5(11110010)和t6(10010010)。當閱讀器用空字符串ε查詢時,所有標簽響應,閱讀器用曼特斯特編碼判斷結果為1xxx0xxx,其中x表示碰撞位。由于存在3位最高連續位,閱讀器發送位跟蹤查詢01111,最后一位“1”表示位跟蹤查詢的標志位。標簽接收到探知查詢后,去掉探知查詢標志位后選取與“111”對應的ID位,t1對應的ID位為100(十進制數4),將4 mod 23設置為1,其他位設置為0,結果為00010000。同樣,t2轉換為01000000,t3轉換為00001000,t4轉換為00100000,t5轉換為10000000,t6轉換為00000010。閱讀器在接收到標簽響應后,生成新的查詢前綴,如此繼續,直到識別所有標簽。識別過程如表2所示,對應的識別樹如圖4所示。

表2 DMQT算法識別標簽過程

圖4 DMQT算法的識別樹
3DMQT算法性能分析
RFID防碰撞算法的性能指標主要包括總時隙和吞吐率。DMQT算法識別標簽過程中采取的分裂叉數是動態的,這里首先分析算法最小總時隙和最大總時隙。假設標簽數量為m,標簽ID長l=96位,可以發現最大分裂的連續碰撞位數n滿足2n≤l,可得n=6,由于動態多叉樹RFID防碰撞算法能夠避免所有空隙時隙,并且n當越大時,碰撞時隙越少,顯然當n=6時所需要的總時隙最小。當n=6時,算法按照26=64叉樹分裂,算法的滿64叉樹的內部節點度為64,葉節點度為0,用m1表示度為64的節點。由于不存在空閑時隙,葉節點數與待識別標簽數m相等。因此滿64叉樹的總節點數為:M=m1+m。另外,度為64的節點有64個孩子,加上一個根節點,那么滿64叉樹的總節點數也可以表示為:M= 64m1+1。因此有:m1+m=64m1+1,m1=(m-1)/63。
由于不存在空閑時隙,中間節點數m1等于碰撞時隙數。當存在最高連續碰撞位時,DMQT算法增加了一次位跟蹤查詢,因此,總的位跟蹤查詢次數等于碰撞時隙數。可以得到滿64叉樹的總時隙為:碰撞時隙+可讀時隙+位跟蹤查詢時隙,即為:
(2)
最小連續碰撞位是2位,當只存在最高兩位連續碰撞位時,DMQT算法采用4叉樹分裂方式。這時也需要采用位跟蹤查詢,與滿64叉樹分析類似,可以得到滿4叉樹的總時隙為:碰撞時隙+可讀時隙+位跟蹤查詢時隙,即為:
(3)
當只存在一位最高碰撞位時,DMQT算法采用二叉樹分裂方式,閱讀器不需要額外的位跟蹤查詢。這時內部節點度為2,葉節點度為0,總節點數為:M=m1+m。其中m1表示度為2的節點,m表示葉節點,也是待識別標簽數。度為2的節點有2個孩子,加上一個根節點,總節點數也表示為:M= 2m1+1??梢缘玫街虚g節點數m1=m-1,因此算法所需要的總時隙為:碰撞時隙+可讀時隙,即為:T2=m-1+m=2m-1。
吞吐率表示單位時隙內識別標簽數,DMQT算法的吞吐率表示為:S=m/T。
下面通過實驗仿真比較幾個算法的識別性能,隨機生成96位長的標簽,標簽數量范圍為100~1000,比較DMQT算法與CT、A4PQT和OQTT等算法的總時隙和吞吐率。仿真結果如圖5、圖6所示。

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

圖6 DMQT算法與CT、A4PQT和OQTT等算法的吞吐率
從圖5中可以看到,DMQT算法識別相同的標簽所需要的總時隙少于CT、A4PQT和OQTT等算法的總時隙。當識別1000個標簽時,DMQT算法所需要的總時隙約為1510,CT算法的總時隙約為2000,A4PQT算法所需要的總時隙約為1590,OQTT算法所需要的總時隙約為1630。究其原因可以發現,CT算法是一個二叉樹防碰撞算法,當發生碰撞時,在最高碰撞位將標簽分裂成2組,CT算法的最大優點是能夠消除所有的空閑時隙,但由于采用二叉樹分裂方式,所以存在較多的碰撞時隙。OQTT算法為了減少過多的碰撞位,對待識別標簽進行最優分組,其識別總時隙小于CT算法,但由于OQTT算法還是基于二叉樹分裂方式,因此存在過多的碰撞時隙。A4PQT是基于四叉樹防碰撞算法,基于四叉樹防碰撞算法比基于二叉樹防碰撞算法具有較少的碰撞時隙,但增加了空閑時隙,A4PQT算法采用剪枝的方式消除部分空閑時隙,因而其總時隙少于CT和OQTT算法的總時隙。DMQT算法則動態調整分裂樹叉樹,采用跟蹤標簽碰撞位的方法消除空閑時隙,因此DMQT算法的總時隙小于其他3個算法。從圖6也可以看到,DMQT算法吞吐率也明顯高于其他3個算法,DMQT算法吞吐率約為0.66,CT、A4PQT和OQTT等算法的吞吐率分別約為0.5,0.63和0.61。
4結語
在RFID系統中,設計一個有效的防碰撞算法能夠提高對標簽識別的效率。本文提出了一個無空閑時隙的動態多叉樹防碰撞算法,DMQT算法在識別過程中根據碰撞位特征動態調整查詢樹分裂叉數,能夠有效地減少了碰撞時隙。在碰撞發生時,跟蹤標簽對應的碰撞位,這樣閱讀器在下次查詢時能夠避免不存在的分支搜索,從而消除了空閑時隙。從理論分析和仿真實驗可以看到,DMQT算法具有較小的總時隙和較大的吞吐率,性能優于其他防碰撞算法。
參考文獻
[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。山東省高等學??萍加媱濏椖?J13LN55)。牛愛民,講師,主研領域:物聯網,人工智能。
中圖分類號TP309
文獻標識碼A
DOI:10.3969/j.issn.1000-386x.2016.06.066