基于漢明權(quán)重分組的自適應(yīng)查詢樹(shù)算法

侯培國(guó)，張小賀，田昊瑋

(燕山大學(xué) 電氣工程學(xué)院，河北 秦皇島 066004)

0 引 言

射頻識(shí)別(radio frequency identification，RFID)技術(shù)是一種以空間電磁波為傳輸媒介的自動(dòng)識(shí)別技術(shù)[1-3]。但是在RFID系統(tǒng)中，由于所有的標(biāo)簽在傳輸數(shù)據(jù)時(shí)都是通過(guò)同一信道，極易發(fā)生標(biāo)簽之間的碰撞，進(jìn)而導(dǎo)致閱讀器無(wú)法正確地讀取標(biāo)簽信息[4]。因此設(shè)計(jì)一種有效的防碰撞算法，高效、精準(zhǔn)識(shí)別標(biāo)簽是當(dāng)前RFID系統(tǒng)急需解決的問(wèn)題。

目前，主要有基于ALOHA的概率性算法[5,6]和基于二進(jìn)制樹(shù)的確定性算法[7,8]用于解決標(biāo)簽的碰撞問(wèn)題?；诙M(jìn)制樹(shù)的確定性算法，可以很好解決ALOHA算法出現(xiàn)的標(biāo)簽“饑餓”現(xiàn)象，具有100%的識(shí)別率[9]，其中，最典型的方法就是查詢樹(shù)算法及其改進(jìn)算法，如文獻(xiàn)[10]提出的IACT算法結(jié)合了二叉樹(shù)和四叉樹(shù)算法的優(yōu)點(diǎn)，有效減少了查詢過(guò)程中產(chǎn)生的空閑時(shí)隙，但會(huì)增加碰撞時(shí)隙；文獻(xiàn)[11]提出的PACT算法通過(guò)自適應(yīng)方法和并行匹配機(jī)制減少了消耗的總時(shí)隙數(shù)，但對(duì)空閑時(shí)隙沒(méi)有優(yōu)化；文獻(xiàn)[12]提出的BAT算法通過(guò)設(shè)計(jì)基于特征值的分組規(guī)則，提高了系統(tǒng)效率，但仍存在空閑時(shí)隙；文獻(xiàn)[13]在文獻(xiàn)[14]的基礎(chǔ)上，結(jié)合ALOHA算法和查詢樹(shù)算法，提出的CF-AMTS算法是將標(biāo)簽映射到不同的時(shí)隙中，然后根據(jù)不同的碰撞因子調(diào)整搜索方法，從而減少查詢過(guò)程中產(chǎn)生的空閑時(shí)隙，提高系統(tǒng)吞吐量；文獻(xiàn)[15]提出的GMQT算法則是將標(biāo)簽均勻分為4組，然后利用分組后的碰撞信息對(duì)標(biāo)簽前綴進(jìn)行預(yù)測(cè)，從而減少空閑時(shí)隙的產(chǎn)生。

本文在上述算法的基礎(chǔ)上，針對(duì)如何減少空閑時(shí)隙進(jìn)一步研究，提出了基于漢明權(quán)重分組的自適應(yīng)查詢樹(shù)(adaptive query tree based on Hamming weight grouping，HAQT)算法，該算法只關(guān)注3個(gè)連續(xù)比特中的碰撞比特位，首先閱讀器根據(jù)碰撞比特位的個(gè)數(shù)自適應(yīng)地選擇不同的查詢機(jī)制，然后依據(jù)不同查詢機(jī)制中的碰撞位特征推斷標(biāo)簽可能存在的查詢前綴，最后通過(guò)構(gòu)建標(biāo)簽集識(shí)別系統(tǒng)中未被識(shí)別的標(biāo)簽。

1 算法描述

1.1 設(shè)計(jì)思想

為了消除查詢過(guò)程中產(chǎn)生的空閑時(shí)隙，提高系統(tǒng)效率，HAQT算法對(duì)空閑時(shí)隙進(jìn)行了優(yōu)化。整體思路是通過(guò)調(diào)整標(biāo)簽的分組情況，在不增加新查詢命令的基礎(chǔ)上，自適應(yīng)選擇不同的查詢機(jī)制，從而根據(jù)標(biāo)簽的碰撞信息實(shí)現(xiàn)對(duì)標(biāo)簽前綴的準(zhǔn)確預(yù)測(cè)，最后通過(guò)構(gòu)建標(biāo)簽集判斷標(biāo)簽是否全部識(shí)別完成。

在查詢過(guò)程中，閱讀器每次僅關(guān)注3個(gè)連續(xù)比特中的碰撞比特位，然后依據(jù)碰撞比特位的個(gè)數(shù)決定采用何種查詢機(jī)制，并根據(jù)不同查詢機(jī)制中的碰撞位特征實(shí)現(xiàn)對(duì)當(dāng)前標(biāo)簽前綴的準(zhǔn)確預(yù)測(cè)。在該算法中有3種不同的查詢機(jī)制，如下所示：

Type1：當(dāng)從最高碰撞位開(kāi)始只有一個(gè)碰撞比特位時(shí)，閱讀器直接將碰撞位置為0和1，即可得到新的前綴。

Type2：當(dāng)從最高碰撞位開(kāi)始有兩個(gè)碰撞比特位時(shí)，閱讀器將這兩個(gè)碰撞位提取出來(lái)，并執(zhí)行式(1)～式(4)，將碰撞位映射成一個(gè)4位且漢明權(quán)重為1的識(shí)別碼，由于映射后的識(shí)別碼和標(biāo)簽是一一對(duì)應(yīng)的，因此閱讀器只需要根據(jù)映射碼的碰撞位就可以推斷出標(biāo)簽的前綴組合

y1=x1&x2

(1)

(2)

(3)

(4)

Type3：當(dāng)從最高碰撞位開(kāi)始有3個(gè)碰撞比特位時(shí)，即XXX，則閱讀器按照漢明權(quán)重原則對(duì)標(biāo)簽進(jìn)行分組，并根據(jù)標(biāo)簽識(shí)別碼中非0字符的數(shù)目計(jì)算漢明權(quán)重，然后將具有相同漢明權(quán)重的標(biāo)簽分為一組，于是得到標(biāo)簽識(shí)別碼碰撞比特位的分組情況見(jiàn)表1。在標(biāo)簽分組完成后，閱讀器首先判斷標(biāo)簽的二進(jìn)制組號(hào)是否發(fā)生碰撞，若組號(hào)發(fā)生碰撞，則將返回的分組信息進(jìn)行映射，并根據(jù)映射后的碰撞信息確定標(biāo)簽前綴對(duì)應(yīng)的組號(hào)；若組號(hào)沒(méi)有發(fā)生碰撞，則閱讀器可以直接判斷出標(biāo)簽的組號(hào)；當(dāng)組號(hào)確定后，將組號(hào)存入堆棧S。由于在00組和11組中的標(biāo)簽識(shí)別碼只有一個(gè)，所以當(dāng)存在00組和11組的標(biāo)簽時(shí)，閱讀器根據(jù)組號(hào)就可以推斷出存在的標(biāo)簽前綴為000和111；然而在01組和10組中存在多個(gè)標(biāo)簽識(shí)別碼，所以當(dāng)組號(hào)確定后，還需再次進(jìn)行檢測(cè)，在01組中比特1的個(gè)數(shù)只有一個(gè)，而在10組中比特1的個(gè)數(shù)有兩個(gè)，因此閱讀器根據(jù)01組和10組中標(biāo)簽識(shí)別碼的組號(hào)和具體碰撞信息，就可以推斷出相應(yīng)的前綴組合。例如，在RFID系統(tǒng)中存在的標(biāo)簽是001和010,標(biāo)簽向閱讀器發(fā)送自身識(shí)別碼和組號(hào)RGC，閱讀器接收到標(biāo)簽發(fā)送的信息為0XX和RGC=01，由于當(dāng)RGC等于01時(shí)，漢明權(quán)重為1，即該標(biāo)簽的前綴中只有一個(gè)比特1，因此閱讀器只需將碰撞位置為比特0和比特1，就可以推測(cè)出當(dāng)前的標(biāo)簽前綴為001和010。

表1 漢明權(quán)重分組

1.2 相關(guān)指令

(1)Query(PRE)表示查詢指令，PRE是標(biāo)簽前綴，閱讀器發(fā)送Query(PRE)指令后，前綴與PRE相同的標(biāo)簽開(kāi)始響應(yīng)閱讀器，并返回除前綴外的其余識(shí)別碼信息；

(2)Query(PRE，RGC)表示查詢指令，PRE是標(biāo)簽前綴，RGC是前綴組號(hào)，閱讀器發(fā)送Query(PRE，RGC)指令后，前綴與PRE相同且屬于RGC組的標(biāo)簽開(kāi)始響應(yīng)閱讀器；

(3)PUSH(PRE)表示讀寫(xiě)指令，發(fā)出此指令后閱讀器將前綴PRE存入堆棧Q中；

(4)POP(PRE)表示讀寫(xiě)指令，發(fā)出此指令后閱讀器將前綴PRE從堆棧Q中彈出；

(5)‖表示位串聯(lián)指令，將兩組數(shù)據(jù)連接。

1.3 算法流程

HAQT算法的具體流程如圖1所示。

圖1 HAQT算法流程

(1)初始化，將閱讀器內(nèi)部的堆棧Q和堆棧S置為空；

(2)閱讀器發(fā)送Query(PRE)指令，標(biāo)簽接收該指令后，開(kāi)始響應(yīng)閱讀器，由靜默狀態(tài)轉(zhuǎn)向活躍狀態(tài)，同時(shí)將自身的識(shí)別碼發(fā)送給閱讀器；

(3)閱讀器判斷標(biāo)簽是否發(fā)生碰撞，若發(fā)生碰撞，則執(zhí)行步驟(4)；若未發(fā)生碰撞，則說(shuō)明標(biāo)簽識(shí)別成功，于是執(zhí)行步驟(5)；

(4)閱讀器根據(jù)碰撞比特位的個(gè)數(shù)選擇相應(yīng)的查詢機(jī)制推測(cè)標(biāo)簽的前綴pipi+1pi+2， 并發(fā)送PUSH(PRE‖pipi+1pi+2) 指令,將新產(chǎn)生的前綴PRE‖pipi+1pi+2存入堆棧Q，并跳至步驟(6)；

(5)閱讀器對(duì)標(biāo)簽的識(shí)別碼進(jìn)行讀取，并將該標(biāo)簽置為靜默狀態(tài)，然后執(zhí)行步驟(6)；

(6)閱讀器確定堆棧Q是否為空，若不為空，則閱讀器發(fā)送POP(PRE)指令，將堆棧Q中的新前綴PRE出棧，并跳至步驟(2)；若為空，則執(zhí)行步驟(7)；

(7)閱讀器發(fā)送Query(null)指令，此時(shí)，若有標(biāo)簽響應(yīng)，說(shuō)明存在標(biāo)簽還沒(méi)有被識(shí)別，于是重建標(biāo)簽集，并跳至步驟(2)，繼續(xù)識(shí)別未被識(shí)別的標(biāo)簽；若無(wú)標(biāo)簽響應(yīng)，說(shuō)明標(biāo)簽已經(jīng)全部識(shí)別完成，則查詢結(jié)束。

1.4 算法實(shí)例分析

下面分別通過(guò)一個(gè)實(shí)例來(lái)介紹3種不同的查詢機(jī)制，如圖2所示。

圖2 HAQT算法不同查詢機(jī)制流程

2 算法性能分析

在防碰撞算法中，時(shí)間復(fù)雜度(即消耗的總時(shí)隙數(shù))和吞吐量是評(píng)判算法性能優(yōu)劣的關(guān)鍵指標(biāo)。因此下面分析了隨著標(biāo)簽數(shù)目變化時(shí)，多叉樹(shù)算法消耗的時(shí)隙數(shù)目與吞吐量的變化情況。假設(shè)RFID系統(tǒng)中存在m個(gè)標(biāo)簽，通過(guò)文獻(xiàn)[16]可以得到一個(gè)B叉樹(shù)消耗的總時(shí)隙數(shù)為

(5)

碰撞時(shí)隙數(shù)為

(6)

空閑時(shí)隙數(shù)為

(7)

在標(biāo)簽的查詢過(guò)程中，主要存在以下情況：

(1)當(dāng)沒(méi)有碰撞位時(shí),消耗的總時(shí)隙數(shù)為

TType0(m)=m

(8)

(2)當(dāng)只有一個(gè)碰撞比特位時(shí)，不會(huì)產(chǎn)生空閑時(shí)隙，消耗的總時(shí)隙數(shù)為

TType1(m)=T2(m)

(9)

(3)當(dāng)有兩個(gè)碰撞比特位時(shí)，通過(guò)映射可以有效的消除空閑時(shí)隙，消耗的總時(shí)隙數(shù)為

(10)

(4)當(dāng)有3個(gè)碰撞比特位時(shí)，通過(guò)對(duì)其進(jìn)行分組，可以消除空閑時(shí)隙，分組后消耗的時(shí)隙數(shù)為

(11)

然而當(dāng)組號(hào)發(fā)生碰撞的時(shí)候，需要二次發(fā)送命令才能確定相應(yīng)的前綴，為了更加準(zhǔn)確進(jìn)行理論分析，于是對(duì)二次發(fā)送命令消耗的時(shí)隙數(shù)進(jìn)行擬合，如圖3所示。

圖3 仿真擬合

經(jīng)過(guò)對(duì)二次發(fā)送命令消耗的時(shí)隙數(shù)進(jìn)行擬合，得到二次發(fā)送命令消耗的時(shí)隙數(shù)F(m)為

F(m)=0.2052m+15.066

(12)

整理后得到在Type3查詢方式下消耗的總時(shí)隙數(shù)為

(13)

下面針對(duì)在不同查詢方式中標(biāo)簽發(fā)生碰撞的概率進(jìn)行計(jì)算，假設(shè)當(dāng)RFID系統(tǒng)中存在i個(gè)標(biāo)簽時(shí)，其中任意一個(gè)比特不發(fā)生碰撞的概率為

(14)

任意一個(gè)比特發(fā)生碰撞的概率為

(15)

在連續(xù)的3個(gè)比特中，沒(méi)有發(fā)生碰撞的概率為

(16)

在連續(xù)的3個(gè)比特中，從最高碰撞位開(kāi)始，有一個(gè)碰撞比特位的概率為

(17)

在連續(xù)的3個(gè)比特中，從最高碰撞位開(kāi)始，有兩個(gè)碰撞比特位的概率為

(18)

在連續(xù)的3個(gè)比特中，從最高碰撞位開(kāi)始，有3個(gè)碰撞比特位的概率為

(19)

由于HAQT算法是根據(jù)每3個(gè)比特中碰撞比特位的個(gè)數(shù)自適應(yīng)地選擇不同的查詢機(jī)制，因此得到HAQT算法消耗的總時(shí)隙數(shù)為

THAQT(m)=P0TType0(m)+P1TType1(m)+
P2TType2(m)+P3TType3(m)

(20)

得到吞吐量為

(21)

3 仿真結(jié)果與分析

在本文中，利用Matlab2014b平臺(tái)對(duì)RFID系統(tǒng)的通信過(guò)程進(jìn)行了模擬仿真。假設(shè)該系統(tǒng)為理想信道，標(biāo)簽在閱讀器范圍內(nèi)均勻分布，并且參考EPC C1G2標(biāo)準(zhǔn)，隨機(jī)生成數(shù)量從100到1000變化，長(zhǎng)度為96位的唯一標(biāo)簽識(shí)別碼，最后結(jié)果取50次仿真的平均值。下面通過(guò)仿真定量分析了HAQT算法、BAT算法、CF-AMTS算法和PACT算法消耗的總時(shí)隙數(shù)、吞吐量和通信復(fù)雜度的變化情況。

為了驗(yàn)證理論分析的正確性，首先對(duì)HAQT算法的理論分析和仿真實(shí)驗(yàn)進(jìn)行了比較，如圖4(a)和圖4(b)所示。通過(guò)圖4(a)和圖4(b)可以看到，在查詢過(guò)程中，該算法消耗的總時(shí)隙數(shù)和吞吐量的理論值和仿真值基本吻合，其吞吐量的最大相對(duì)誤差不超2.8%，在誤差允許的范圍內(nèi)，所以可以認(rèn)為該理論分析和仿真實(shí)驗(yàn)是一致的。

圖4 理論值和仿真值比較

圖5為HAQT算法、BAT算法、CF-AMTS算法和PACT算法的總時(shí)隙數(shù)比較。由圖5(a)可知，在識(shí)別相同數(shù)量的標(biāo)簽時(shí)，BAT算法、CF-AMTS算法和PACT算法消耗的總時(shí)隙數(shù)均大于HAQT算法消耗的總時(shí)隙數(shù)，且隨著標(biāo)簽數(shù)量的增加，HAQT算法的優(yōu)勢(shì)會(huì)更加明顯。在標(biāo)簽數(shù)量等于1000時(shí)，該算法消耗的總時(shí)隙數(shù)目?jī)H為1678，這主要是由于HAQT算法通過(guò)采用自適應(yīng)的查詢方法，實(shí)現(xiàn)了對(duì)標(biāo)簽前綴的準(zhǔn)確預(yù)測(cè)，通過(guò)減少空閑時(shí)隙降低了消耗的總時(shí)隙數(shù)。空閑時(shí)隙的變化情況如圖5(b)所示，可以看出HAQT算法完全避免了空閑時(shí)隙的產(chǎn)生。

圖5 各種算法消耗的時(shí)隙數(shù)比較

圖6為HAQT算法、BAT算法、CF-AMTS算法和PACT算法的吞吐量比較。由圖6可以看出，HAQT算法的吞吐量維持在0.60左右，相比于 PACT算法提升了1.7%，相比于BAT算法提升了11.1%，相比于CF-AMTS算法提升了17.6%。

圖6 各種算法吞吐量比較

圖7為HAQT算法、BAT算法、CF-AMTS算法和PACT算法的通信復(fù)雜度比較。從圖7可以看到HAQT算法的通信復(fù)雜度最低，當(dāng)待識(shí)別標(biāo)簽數(shù)量為1000時(shí)，該算法的通信復(fù)雜度為2.26×105，這是由于HAQT算法通過(guò)調(diào)整標(biāo)簽的分組方法，減少了無(wú)效數(shù)據(jù)傳輸。

圖7 各種算法通信復(fù)雜度比較

表2顯示了不同算法的性能比較。從中可以看到，HAQT算法通過(guò)根據(jù)碰撞比特位的個(gè)數(shù)自適應(yīng)的選擇不同的查詢機(jī)制，并采用漢明權(quán)重方法對(duì)標(biāo)簽前綴進(jìn)行分組，實(shí)現(xiàn)了對(duì)標(biāo)簽前綴的準(zhǔn)確預(yù)測(cè)，減少了查詢過(guò)程中產(chǎn)生的空閑時(shí)隙，從而使該算法性能明顯的優(yōu)于其它算法。另外，該算法通過(guò)重建標(biāo)簽集的方式識(shí)別上一個(gè)階段中未被識(shí)別的標(biāo)簽，因此還具有一定的抗捕獲作用[17]。

表2 不同算法整體性能比較

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

在本文中結(jié)合分組思想和查詢樹(shù)算法，提出一種基于漢明權(quán)重分組的自適應(yīng)查詢樹(shù)算法，首先根據(jù)每3個(gè)比特中碰撞比特位的個(gè)數(shù)自適應(yīng)地選擇不同的查詢機(jī)制，然后依據(jù)不同查詢機(jī)制中的碰撞位特征推斷標(biāo)簽可能存在的查詢前綴，從而降低查詢過(guò)程中產(chǎn)生的空閑時(shí)隙，最后通過(guò)構(gòu)建標(biāo)簽集，判斷標(biāo)簽是否全部識(shí)別。仿真結(jié)果顯示，HAQT算法能夠消除查詢過(guò)程中產(chǎn)生的空閑時(shí)隙，且消耗的總時(shí)隙數(shù)、吞吐量和通信復(fù)雜度均優(yōu)于PACT、BAT和CF-AMTS算法，吞吐量最高可以達(dá)到0.60，且具有一定的抗捕獲作用，適合在大規(guī)模標(biāo)簽的RFID系統(tǒng)中應(yīng)用。下一步的工作是對(duì)該算法的抗捕獲功能進(jìn)一步改進(jìn)，并進(jìn)行定量分析。