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

張秀艷 吳 丹 顧婉瑩

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

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

張秀艷 吳 丹*顧婉瑩

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

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

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

0 引 言

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

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

圖1 無線射頻識別系統(tǒng)

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

1 研究現(xiàn)狀

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

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

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

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

2.1 曼徹斯特編碼

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

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

圖2 Manchester編碼原理

2.2 算法描述

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

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

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

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

(1)

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

2.3 算法流程

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

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

閱讀器操作步驟：

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

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

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

4) 等待標(biāo)簽響應(yīng)。如果標(biāo)簽沒有回應(yīng)，執(zhí)行步驟7，如果標(biāo)簽有回應(yīng)，判斷是否有碰撞發(fā)生；沒有則執(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) 識別標(biāo)簽。

7) 程序結(jié)束。

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

3.1 性能分析

3.1.1 時間復(fù)雜度

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

證明:由于碰撞位存在三位連續(xù)的情況，因此使用八叉樹查詢優(yōu)于四叉樹和二叉樹查詢。純八叉樹的內(nèi)除根節(jié)點(diǎn)外所有的節(jié)點(diǎn)的分支都是8，葉子節(jié)點(diǎn)的分支為0，將n8定義分支為8的節(jié)點(diǎn)，n0表示度為0的葉子節(jié)點(diǎn)，因此八叉樹的總節(jié)點(diǎn)N=n0+n8，此外度為8的節(jié)點(diǎn)有8個分支，度為0的節(jié)點(diǎn)沒有分支，根節(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表示空閑時隙時:

n+ni=7×n8+1

(3)

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

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

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

(4)

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

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

(5)

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

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

(6)

3.1.2 識別效率

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

(7)

3.1.3 通信復(fù)雜度

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

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

(8)

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

(9)

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

(10)

3.2 仿真結(jié)果

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

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

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

4 結(jié) 語

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

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

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

[3] 王春華, 劉遲時, 徐浩, 等. 一種改進(jìn)的基于二叉樹的防碰撞算法[J]. 湖南大學(xué)學(xué)報(自然科學(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)感知層查詢樹防碰撞算法研究[D]. 長春：吉林大學(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] 王雪, 錢志鴻, 胡正超, 等. 基于二叉樹的RFID防碰撞算法的研究[J]. 通信學(xué)報, 2010, 31(6):49-57.

[10] 郭志濤, 程林林, 周艷聰, 等. 動態(tài)幀時隙ALOHA算法的改進(jìn)[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] 丁治國, 朱學(xué)永, 郭立, 等. 自適應(yīng)多叉樹防碰撞算法研究[J]. 自動化學(xué)報, 2010, 36(2):237-241.

[13] 王必勝, 張其善. 可并行識別的超高頻RFID系統(tǒng)防碰撞性能研究[J]. 通信學(xué)報, 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ī), 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)域： 無線通信技術(shù)。吳丹，碩士生。顧婉瑩，碩士生。

TP301

A

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