張秀艷 吳 丹 顧婉瑩

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

一種基于混合樹防碰撞算法的改進算法

張秀艷 吳 丹*顧婉瑩

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

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

防碰撞算法 混合樹 射頻識別技術

0 引 言

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

2.1 曼徹斯特編碼

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

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

圖2 Manchester編碼原理

2.2 算法描述

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

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

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

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

(1)

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

2.3 算法流程

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

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

閱讀器操作步驟：

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

2) 檢查棧內，為空跳至步驟7。

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

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

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

最高碰撞位位次高位碰撞位連續(xù)發(fā)生碰撞，且下一位未發(fā)生碰撞：將q00、q01、q11、q10壓入棧內，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) 重復步驟2-步驟4。

6) 識別標簽。

7) 程序結束。

3 性能分析與仿真結果

3.1 性能分析

3.1.1 時間復雜度

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

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

n0=7×n8+1

(2)

當n表示標簽數(shù)量，ni表示空閑時隙時:

n+ni=7×n8+1

(3)

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

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

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

(4)

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

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

(5)

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

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

(6)

3.1.2 識別效率

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

(7)

3.1.3 通信復雜度

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

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

(8)

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

(9)

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

(10)

3.2 仿真結果

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

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

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

4 結 語

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

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

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

[3] 王春華, 劉遲時, 徐浩, 等. 一種改進的基于二叉樹的防碰撞算法[J]. 湖南大學學報(自然科學版), 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]. 長春：吉林大學, 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]. 通信學報, 2010, 31(6):49-57.

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

[13] 王必勝, 張其善. 可并行識別的超高頻RFID系統(tǒng)防碰撞性能研究[J]. 通信學報, 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]. 微電子學與計算機, 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。張秀艷，教授，主研領域： 無線通信技術。吳丹，碩士生。顧婉瑩，碩士生。

TP301

A

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