一種基于混合樹(shù)防碰撞算法的改進(jìn)算法

張秀艷 吳 丹 顧婉瑩

(東北石油大學(xué)電氣信息工程學(xué)院 黑龍江 大慶 163318)

一種基于混合樹(shù)防碰撞算法的改進(jìn)算法

張秀艷 吳 丹*顧婉瑩

(東北石油大學(xué)電氣信息工程學(xué)院 黑龍江 大慶 163318)

由于無(wú)線射頻識(shí)別技術(shù)RFID(Radio Frequency Identification)現(xiàn)廣泛應(yīng)用于各個(gè)領(lǐng)域中，標(biāo)簽的碰撞問(wèn)題也成為一個(gè)待解決的重要問(wèn)題。根據(jù)現(xiàn)有多叉樹(shù)防碰撞算法提出一種動(dòng)態(tài)自適應(yīng)多叉樹(shù)防碰撞算法(DIHQT)。該算法根據(jù)碰撞位最高三位的連續(xù)性自行調(diào)節(jié)算法的搜索叉數(shù)，在沒(méi)有附加查詢的條件下，動(dòng)態(tài)自適應(yīng)地選擇二叉樹(shù)、四叉樹(shù)或八叉樹(shù)來(lái)查詢標(biāo)簽ID編碼。通過(guò)對(duì)算法性能分析和仿真實(shí)驗(yàn)結(jié)果可以表明，DIHQT算法在時(shí)間復(fù)雜度上有約200次的減少，以及識(shí)別效率上較其他算法都有約5%提高。

防碰撞算法 混合樹(shù) 射頻識(shí)別技術(shù)

0 引 言

射頻識(shí)別技術(shù)(RFID)，作為現(xiàn)今物聯(lián)網(wǎng)的核心技術(shù)之一，有效地利用射頻信號(hào)及空間耦合的雙向傳輸特性，對(duì)靜止或動(dòng)態(tài)對(duì)象實(shí)現(xiàn)非接觸式的自動(dòng)識(shí)別[1]。該技術(shù)的讀寫(xiě)速度快，對(duì)于多個(gè)移動(dòng)非可視物體的識(shí)別準(zhǔn)確性高，標(biāo)簽信息覆蓋量大等特點(diǎn)。

射頻識(shí)別系統(tǒng)共分三個(gè)部分:閱讀器、應(yīng)用系統(tǒng)以及電子標(biāo)簽，其中應(yīng)用系統(tǒng)主要包括中間件和應(yīng)用系統(tǒng)軟件，如圖1所示[2]。

圖1 無(wú)線射頻識(shí)別系統(tǒng)

在一個(gè)RFID射頻識(shí)別系統(tǒng)中，當(dāng)多個(gè)標(biāo)簽同時(shí)出現(xiàn)在一個(gè)閱讀器的工作范圍內(nèi)時(shí)，兩個(gè)或兩個(gè)以上標(biāo)簽同一時(shí)隙向閱讀器發(fā)送信息，造成閱讀器識(shí)別錯(cuò)誤，即發(fā)生了碰撞。為了提高系統(tǒng)識(shí)別效率，減少碰撞的發(fā)生，防碰撞算法的研究也就成為無(wú)線射頻識(shí)別領(lǐng)域的關(guān)鍵技術(shù)之一。防碰撞算法主要分為兩個(gè)分支，非確定性ALOHA算法以及確定性搜索樹(shù)算法。ALOHA算法采用隨機(jī)的時(shí)分多址方法，操作簡(jiǎn)單且便于實(shí)際應(yīng)用，但標(biāo)簽“餓死”的情況也十分明顯。樹(shù)形搜索算法是由二叉樹(shù)搜索算法演變而來(lái)，逐步縮小搜索范圍，直到找到有且僅有的滿足指定條件的標(biāo)簽。樹(shù)形搜索算法可以將所以標(biāo)簽無(wú)差別識(shí)別出來(lái)，但它也具有識(shí)別時(shí)延長(zhǎng)以及傳輸數(shù)據(jù)量大等缺點(diǎn)。

1 研究現(xiàn)狀

現(xiàn)階段使用頻率大且成熟度較高的防碰撞算法主要包括DFSA算法和樹(shù)形搜索算法。DFSA算法程序簡(jiǎn)單，操作簡(jiǎn)便，但存在標(biāo)簽漏讀以及吞吐率低等問(wèn)題。樹(shù)形算法通過(guò)Manchester編碼方式給每一個(gè)標(biāo)簽匹配唯一的ID號(hào)，解決了標(biāo)簽“餓死”現(xiàn)象，但同時(shí)也降低了系統(tǒng)工作效率。

文獻(xiàn)[3]分別提到通過(guò)動(dòng)態(tài)二叉樹(shù)算法DBS、四叉樹(shù)算法DFS、查詢樹(shù)算法QT來(lái)處理標(biāo)簽防碰撞問(wèn)題。文獻(xiàn)[4]中提及在傳統(tǒng)二叉樹(shù)的基礎(chǔ)上增加了鎖位后退功能的鎖位后退防碰撞算法BLBO，閱讀器譯碼后，根據(jù)結(jié)果鎖定碰撞位來(lái)解決標(biāo)簽碰撞的產(chǎn)生。文獻(xiàn)[7]中Shakiba采用生日悖論的算法，即在23人中兩人的生日是同日同時(shí)的概率大于50%這一概念，來(lái)計(jì)算空閑時(shí)隙、碰撞時(shí)隙以及成功時(shí)隙的發(fā)生概率。文獻(xiàn)[6]綜合了碼分多址CDMA與DFSA算法的特點(diǎn)更大程度上減小了標(biāo)簽發(fā)生碰撞的情況。文獻(xiàn)[10]通過(guò)調(diào)整盤(pán)存幀長(zhǎng)的方法同時(shí)跳過(guò)空閑時(shí)隙以增加系統(tǒng)的防碰撞機(jī)能。

本文針對(duì)現(xiàn)有DFSA、優(yōu)化的樹(shù)型防碰撞算法中，提出一種基于RFID系統(tǒng)的動(dòng)態(tài)自適應(yīng)混合樹(shù)算法。該算法有效地增加有效時(shí)隙、減少空閑時(shí)隙，合理有效利用時(shí)隙。

2 動(dòng)態(tài)自適應(yīng)混合樹(shù)算法

2.1 曼徹斯特編碼

在QT算法和HQT算法中，主要通過(guò)標(biāo)簽的ID來(lái)確定碰撞發(fā)生的位置，從而產(chǎn)生新的查詢前綴，在這里我們引入了曼徹斯特編碼的方式。由編碼中的“0”、“1”來(lái)判斷脈沖的變化。在編碼的譯制過(guò)程中，如果信號(hào)沒(méi)有發(fā)生跳變，則表示發(fā)生碰撞。閱讀器通過(guò)這種“無(wú)變化”確定碰撞發(fā)生的位置。

假設(shè)有兩個(gè)標(biāo)簽的ID是10110010與10101010，根據(jù)圖2可識(shí)別出第四和第五位為碰撞位[8]。

圖2 Manchester編碼原理

2.2 算法描述

算法的執(zhí)行分為兩個(gè)部分完成：確定碰撞位以及處理碰撞位。

查詢階段：閱讀器先發(fā)聲，同一時(shí)刻向有效識(shí)別范圍內(nèi)的標(biāo)簽發(fā)送問(wèn)詢命令(Req)，標(biāo)簽接收到命令信號(hào)后向閱讀器回送自身的ID號(hào)。

防碰撞階段：閱讀器根據(jù)Manchester編碼原理計(jì)算出發(fā)生碰撞的準(zhǔn)確位置，參照碰撞發(fā)生的連續(xù)性來(lái)自適應(yīng)決定搜索叉數(shù)。

在樹(shù)形算法中一般會(huì)產(chǎn)生三種類型的時(shí)隙：碰撞時(shí)隙、成功時(shí)隙和空閑時(shí)隙[9]。文獻(xiàn)[9]中提出多叉樹(shù)搜索需要的總時(shí)隙數(shù)為：

(1)

式中B代表樹(shù)結(jié)構(gòu)的分叉數(shù)，m代表標(biāo)簽總量，L為目前層數(shù)?？梢钥闯鰐(m)與B的取值成正相關(guān)。由式(1)可以看出，為使系統(tǒng)效率最高即總時(shí)隙數(shù)t(m)最小，應(yīng)采用三叉樹(shù)查詢，而Manchester編碼由二進(jìn)制數(shù)構(gòu)成，因此只能選用樹(shù)形的幾種搜索方式。本文提出的算法的主要思想是：在不增加新的查詢的基礎(chǔ)上，閱讀器根據(jù)碰撞位的連續(xù)性，自適應(yīng)地調(diào)整搜索叉數(shù)。當(dāng)碰撞位為獨(dú)立一位時(shí)，使用二叉樹(shù)查詢，如碰撞比特發(fā)生在連續(xù)兩位時(shí)，使用四叉樹(shù)查詢，當(dāng)碰撞發(fā)生在連續(xù)三位時(shí)，才用八叉樹(shù)查詢。由此可見(jiàn)，產(chǎn)生一個(gè)碰撞比特的位置，使用二叉樹(shù)查詢，能減少空閑時(shí)隙；在連續(xù)兩位碰撞位置使用四叉樹(shù)，能夠降低碰撞發(fā)生的概率[10]；在連續(xù)三位碰撞位的發(fā)生位置使用八叉樹(shù)查詢，能夠減少查詢深度，提高系統(tǒng)效率。

2.3 算法流程

加強(qiáng)型自適應(yīng)混合樹(shù)算法的主要特征是通過(guò)碰撞位的連續(xù)性對(duì)待識(shí)別標(biāo)簽采取成二叉樹(shù)查詢，四叉樹(shù)查詢或八叉樹(shù)查詢。在每一輪詢問(wèn)過(guò)程中，閱讀器先發(fā)送查詢前綴，標(biāo)簽進(jìn)行自查，如果含有發(fā)送的前綴，標(biāo)簽對(duì)閱讀器的查詢進(jìn)行回應(yīng)。當(dāng)只有一個(gè)標(biāo)簽響應(yīng)時(shí)，識(shí)別成功；如有兩個(gè)或兩個(gè)以上標(biāo)簽同時(shí)響應(yīng)，產(chǎn)生碰撞，識(shí)別失敗。根據(jù)Manchester編碼檢測(cè)對(duì)應(yīng)的碰撞位的連續(xù)特征，重新設(shè)置查詢前綴。對(duì)于閱讀器發(fā)出的查詢q1q2…qk和標(biāo)簽對(duì)應(yīng)的r1r2…rn-1rnrn+1，如果最高碰撞位是rn-1同時(shí)rn并未發(fā)生碰撞，則使用二叉樹(shù)查詢；當(dāng)最高碰撞位rn-1與次高位rn都是碰撞位且rn+1為未發(fā)生碰撞，則采用四叉樹(shù)查詢方法；如r1r2…rn-1rnrn+1皆為碰撞位，則采用八叉樹(shù)查詢方法。

算法執(zhí)行中，將前綴保存在堆棧中，在下一次查詢時(shí)使用。首先將一個(gè)空字符串壓入棧，之后，閱讀器每次查詢后將新的前綴壓入棧中，直到堆棧內(nèi)無(wú)內(nèi)容，則標(biāo)簽完成識(shí)別。

閱讀器操作步驟：

1) 空字符串存入初始化后堆棧。

2) 檢查棧內(nèi)，為空跳至步驟7。

3) 將查詢前綴q廣播給各個(gè)標(biāo)簽。

4) 等待標(biāo)簽響應(yīng)。如果標(biāo)簽沒(méi)有回應(yīng)，執(zhí)行步驟7，如果標(biāo)簽有回應(yīng)，判斷是否有碰撞發(fā)生；沒(méi)有則執(zhí)行步驟6，如果有碰撞發(fā)生，判斷最高三位碰撞位是否連續(xù)不間斷：

最高位與次高位碰撞發(fā)生不連續(xù)：q0、q1壓入棧，PUSH(q0,q1);

最高碰撞位位次高位碰撞位連續(xù)發(fā)生碰撞，且下一位未發(fā)生碰撞：將q00、q01、q11、q10壓入棧內(nèi)，PUSH(q00,q01,q11,q10);

最高三位為連續(xù)碰撞位：將q000、q001、q011、q111、q010、q011、q100、q111壓入棧PUSH(q000,q001,q011,q111,q010,q011,q100,q101,q111)。

5) 重復(fù)步驟2-步驟4。

6) 識(shí)別標(biāo)簽。

7) 程序結(jié)束。

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

3.1 性能分析

3.1.1 時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是指在所有標(biāo)簽成功識(shí)別過(guò)程中所用到的所有時(shí)隙的總數(shù)，相對(duì)應(yīng)于混合樹(shù)中所有葉子的節(jié)點(diǎn)的總數(shù)。在純二叉樹(shù)搜索算法中，如果待識(shí)別標(biāo)簽的總量為n，時(shí)間復(fù)雜度即總時(shí)隙數(shù)為2n-1;在純四叉樹(shù)中時(shí)間復(fù)雜度在[(4n-1)/3,2n-3][9]內(nèi)；在八叉樹(shù)中，時(shí)間復(fù)雜度[(8n-1)/7,8n-7]之間。

證明:由于碰撞位存在三位連續(xù)的情況，因此使用八叉樹(shù)查詢優(yōu)于四叉樹(shù)和二叉樹(shù)查詢。純八叉樹(shù)的內(nèi)除根節(jié)點(diǎn)外所有的節(jié)點(diǎn)的分支都是8，葉子節(jié)點(diǎn)的分支為0，將n8定義分支為8的節(jié)點(diǎn)，n0表示度為0的葉子節(jié)點(diǎn)，因此八叉樹(shù)的總節(jié)點(diǎn)N=n0+n8，此外度為8的節(jié)點(diǎn)有8個(gè)分支，度為0的節(jié)點(diǎn)沒(méi)有分支，根節(jié)點(diǎn)上方?jīng)]有根，N=0×n0+8×n8+1，則8×n8+1=n0+n8，因此推出葉子的節(jié)點(diǎn)總數(shù)為:

n0=7×n8+1

(2)

當(dāng)n表示標(biāo)簽數(shù)量，ni表示空閑時(shí)隙時(shí):

n+ni=7×n8+1

(3)

在八叉樹(shù)搜索算法中，用葉子節(jié)點(diǎn)n0表示所有的可讀時(shí)隙和空閑時(shí)隙，在八叉樹(shù)中產(chǎn)生三位連續(xù)碰撞位，對(duì)于一個(gè)發(fā)生碰撞的時(shí)隙中，最多的情況會(huì)出現(xiàn)6個(gè)空閑時(shí)隙，最少的情況不會(huì)產(chǎn)生空閑時(shí)隙[6]。

當(dāng)一個(gè)碰撞時(shí)隙產(chǎn)生6個(gè)空閑時(shí)隙時(shí)，ni=6n8，代入式(3)可得n8=n-1，因此，八叉樹(shù)的最大時(shí)間復(fù)雜度為：

N=n+ni+n8=8n-7

(4)

當(dāng)一個(gè)碰撞發(fā)生的同時(shí)并不產(chǎn)生空閑時(shí)隙，葉子節(jié)點(diǎn)數(shù)n0等于標(biāo)簽數(shù)量n，由式(2)得n=7×n8+1，n8=(n-1)/7所以八叉樹(shù)的最小時(shí)間復(fù)雜度：

N=n+n8=(8n-1)/7

(5)

因此，八叉樹(shù)的時(shí)間復(fù)雜度在(8n-1)/7與8n-7之間。

為了便于分析，這里對(duì)DIHAT算法的時(shí)間復(fù)雜度取均值為(32n-25)/7，再參考二叉樹(shù)與四叉樹(shù)的時(shí)間復(fù)雜度[8]，得出DIHQT算法的平均時(shí)間復(fù)雜度為：

(6)

3.1.2 識(shí)別效率

識(shí)別效率為有效時(shí)隙與總時(shí)隙的比值，對(duì)于n個(gè)待識(shí)別標(biāo)簽，則有效時(shí)隙為n，因此該算法的系統(tǒng)識(shí)別效率為[12]：

(7)

3.1.3 通信復(fù)雜度

通信復(fù)雜度即系統(tǒng)識(shí)別過(guò)程中傳輸?shù)目偙忍財(cái)?shù)[13]。DIHQT算法的通信復(fù)雜度為閱讀器的通信復(fù)雜度與標(biāo)簽的通信復(fù)雜度之和，即待標(biāo)簽識(shí)別過(guò)程中總的傳輸比特?cái)?shù)[11]。DIHQT算法的通信復(fù)雜度用B(n)來(lái)表示，閱讀器的通信復(fù)雜度用BR(n)表示，標(biāo)簽的通信復(fù)雜度用BT(n)表示：

B(n)=BR(n)+BT(n)

(8)

在DIHQT算法執(zhí)行過(guò)程中，閱讀器的查詢前綴的長(zhǎng)度隨著標(biāo)簽相應(yīng)的位長(zhǎng)減少而逐步增加，閱讀器第i次查詢的前綴長(zhǎng)度用L1(i)表示，L為標(biāo)簽長(zhǎng)度，用L2(i)來(lái)表示第i次標(biāo)簽應(yīng)答時(shí)的前綴長(zhǎng)度[14]。則式(8)也可以表示為：

(9)

由于L=L1(i)+L2(i)，根據(jù)式(6)，式(9)可以表示為：

(10)

3.2 仿真結(jié)果

本實(shí)驗(yàn)通過(guò)軟件進(jìn)行仿真，選擇理想信道，隨機(jī)生成96bit的標(biāo)簽ID，通信速率為100bit/s[15]。在相同實(shí)驗(yàn)條件下采用10次實(shí)驗(yàn)平均值，標(biāo)簽數(shù)量從0逐步增加到1000。如圖分別對(duì)查詢樹(shù)算法QT、碰撞樹(shù)算法CT、與本算法性能進(jìn)行比較，DIHQT算法在時(shí)間復(fù)雜度與三者相比有所減少；通信復(fù)雜度由查詢前綴長(zhǎng)度決定，前綴數(shù)越少，閱讀器與標(biāo)簽之間的信息交互就越少，傳輸?shù)臄?shù)據(jù)量也相應(yīng)減少。如圖3-圖5所示。

圖5 CT算法、QT算法以及DIHQT算法通信復(fù)雜度的比較

從圖中能看出，當(dāng)標(biāo)簽數(shù)量逐步增加時(shí)，DIHQT算法在時(shí)間復(fù)雜度上一直優(yōu)于QT、CT算法，當(dāng)標(biāo)簽數(shù)量達(dá)到最大時(shí)，DIHQT算法相較于其余兩種算法在總的查詢次數(shù)上減少約200次。而DIHQT算法在系統(tǒng)效率上有約5%的提高。通過(guò)在三種算法的通信復(fù)雜度、系統(tǒng)效率以及時(shí)間復(fù)雜度三個(gè)方面比較，DIHQT算法優(yōu)于其余兩種算法。

4 結(jié) 語(yǔ)

基于樹(shù)形搜索算法的標(biāo)簽無(wú)“餓死”現(xiàn)象的優(yōu)勢(shì)，在原有二叉樹(shù)算法的基礎(chǔ)上，通過(guò)改進(jìn)，以及四叉樹(shù)，八叉樹(shù)優(yōu)勢(shì)的結(jié)合，提出了加強(qiáng)型自調(diào)整混合樹(shù)算法。該算法根據(jù)碰撞發(fā)生的特征自行選擇搜索叉數(shù)，當(dāng)最高碰撞的三位為連續(xù)不間斷時(shí)，采用八叉樹(shù)查詢以增加有效時(shí)隙；當(dāng)最高碰撞發(fā)生在連續(xù)兩位時(shí)，改為四叉樹(shù)的搜索方式來(lái)減少碰撞的發(fā)生；當(dāng)最高碰撞發(fā)生在單獨(dú)一位時(shí)，采用二叉樹(shù)搜索方式以減少空閑時(shí)隙的產(chǎn)生。對(duì)算法性能的分析以及仿真實(shí)驗(yàn)的結(jié)果表明，該算法在通信復(fù)雜度、系統(tǒng)效率和時(shí)間復(fù)雜度上有明顯優(yōu)勢(shì)。

[1] 張學(xué)軍, 蔡文琦, 王鎖萍. 改進(jìn)型自適應(yīng)多叉樹(shù)防碰撞算法研究[J]. 電子學(xué)報(bào), 2012, 40(1):193-198.

[2] 周艷聰, 孫曉晨, 顧軍華. 一種改進(jìn)二進(jìn)制防碰撞算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(1):256-259,262.

[3] 王春華, 劉遲時(shí), 徐浩, 等. 一種改進(jìn)的基于二叉樹(shù)的防碰撞算法[J]. 湖南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 40(8):97-101.

[4]SunY,HawrylakPJ,MickleMH.ApplicationofICAincollisionresolutionforpassiveRFIDcommunication[C]//Proceedingsofthe2009WorldCongressonEngineeringandComputerScience,2009: 1292-1297.

[5]YangX,WuH,ZengY,etal.Capture-awareestimationforthenumberofRFIDtagswithlowercomplexity[J].IEEECommunicationsLetters, 2013, 17 (10):1873-1876.

[6] 劉森. 基于RFID的物聯(lián)網(wǎng)感知層查詢樹(shù)防碰撞算法研究[D]. 長(zhǎng)春：吉林大學(xué), 2013.

[7] Shakiba M, Singh M J, Sundararajan E, et al. Extending Birthday Paradox Theory to Estimate the Number of Tags in RFID Systems[J]. PLoS One, 2014, 9(4):e95425.

[8] Yeh M K, Jiang J R. Parallel splitting for RFID tag anti-collision[J]. International Journal of Ad Hoc and Ubiquitous Computing, 2011, 8(4):249-260.

[9] 王雪, 錢(qián)志鴻, 胡正超, 等. 基于二叉樹(shù)的RFID防碰撞算法的研究[J]. 通信學(xué)報(bào), 2010, 31(6):49-57.

[10] 郭志濤, 程林林, 周艷聰, 等. 動(dòng)態(tài)幀時(shí)隙ALOHA算法的改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用研究, 2012,29(3):907-909.

[11] Zhang W, Guo Y, Tang X, et al. An efficient adaptivez anti-collision algorithm based on 4-ary pruning query tree[J]. International Journal of Distributed Sensor Networks, 2013, 2013:848746.

[12] 丁治國(guó), 朱學(xué)永, 郭立, 等. 自適應(yīng)多叉樹(shù)防碰撞算法研究[J]. 自動(dòng)化學(xué)報(bào), 2010, 36(2):237-241.

[13] 王必勝, 張其善. 可并行識(shí)別的超高頻RFID系統(tǒng)防碰撞性能研究[J]. 通信學(xué)報(bào), 2009, 30(6):108-113.

[14] Shin J, Jeon B, Yang D. Multiple RFID tags identification with Mary query tree scheme[J]. IEEE Communications Letters, 2013，17(3):604-607.

[15] 吳博, 周銅, 王棟. RFID防碰撞算法分析與研究[J]. 微電子學(xué)與計(jì)算機(jī), 2009, 26(8):237-239,242.

AN IMPROVED ANTI-COLLISION ALGORITHM BASED ON HYBRID QUERY TREE

Zhang Xiuyan Wu Dan*Gu Wanying

(SchoolofElectricalEngineeringandInformation，NortheastPetroleumUniversity，Daqing163318,Heilongjiang,China)

The Radio Frequency Identification system,which is widely used in various fields nowadays,leads that the tags collision problem an important problem to be solved.A new dynamic adaptive anti-collision algorithm(DIHQT) is proposed based on the existing multi-tree search anti-collision algorithm.According to the features of the highest three collision bit,this algorithm self-adjusts the search tree branches in the absence of additional query,and chooses binary tree, quad tree or octree to query the label codeautomatically.Experimental results of the performance analysis and simulation show that the DIHQT algorithm has 200 times decrease in complexity communication complexity and a 5% increase in recognition efficiency than those of other multi-tree algorithms.

Anti-collision algorithm Hybrid tree Radio frequency identification

2015-10-09。張秀艷，教授，主研領(lǐng)域： 無(wú)線通信技術(shù)。吳丹，碩士生。顧婉瑩，碩士生。

TP301

A

10.3969/j.issn.1000-386x.2017.02.053