任柏翰，張圣杰，石浩森，宮 婧

(南京郵電大學(xué)，江蘇 南京 210023)

0 引 言

射頻識(shí)別(radio frequency identification，RFID)技術(shù)可以通過無線電訊號(hào)實(shí)現(xiàn)無接觸式自動(dòng)識(shí)別，由于其具有閱讀速度快，可適應(yīng)于各種惡劣環(huán)境，讀寫能力快等優(yōu)點(diǎn)，現(xiàn)已廣泛應(yīng)用于交通物流、食品管理、圖書館書刊借閱、門禁等各個(gè)領(lǐng)域[1]。但當(dāng)多個(gè)標(biāo)簽同時(shí)與讀寫器進(jìn)行信息傳輸時(shí)，會(huì)出現(xiàn)“碰撞”現(xiàn)象，使閱讀器無法正常工作，嚴(yán)重影響系統(tǒng)正常運(yùn)行。為解決這一問題，現(xiàn)已提出了多種RFID防碰撞的算法[2]。

1 當(dāng)前防碰撞算法

常用的防碰撞算法一般可以分為兩類：確定算法和非確定算法[3]。非確定算法主要是基于ALOHA算法，包括時(shí)隙ALHOA算法、分群時(shí)隙ALOHA算法等。確定性算法主要是基于二進(jìn)制樹搜索的算法，包括二叉樹搜索算法、動(dòng)態(tài)二叉樹搜索算法、自適應(yīng)樹搜索算法等[4]。

純ALOHA算法[5]就是當(dāng)需要發(fā)送數(shù)據(jù)時(shí)，標(biāo)簽以循環(huán)序列形式發(fā)送數(shù)據(jù)，在第一次發(fā)送之后，需要等待相對(duì)較長(zhǎng)的時(shí)間再次發(fā)送數(shù)據(jù)，直到所有標(biāo)簽都完成了數(shù)據(jù)的發(fā)送。時(shí)隙ALOHA算法[6]把時(shí)間以幀為單位分成時(shí)間段，每個(gè)時(shí)間段由若干個(gè)時(shí)隙組成，標(biāo)簽發(fā)送數(shù)據(jù)幀只能在時(shí)隙開始時(shí)發(fā)送，按照這種方法，可以大大減少因?yàn)閹貜?fù)引起的沖突。

二叉樹搜索[7]的基本思想是將處于沖突的標(biāo)簽分成左右兩個(gè)子集0和1，先查詢子集0，若沒有沖突，則正確識(shí)別標(biāo)簽結(jié)束。若仍有沖突則再繼續(xù)分裂，把子集0分成00和01兩個(gè)子集，依次類推，直到識(shí)別出子集0中所有標(biāo)簽，再按此步驟查詢子集1。

四叉樹搜索的基本思想是將處于沖突的標(biāo)簽分成四個(gè)子集00、01、10和11，先查詢子集00，若沒有沖突，則正確識(shí)別標(biāo)簽結(jié)束。若仍有沖突則再繼續(xù)分裂，依次類推，直到識(shí)別出子集00中所有標(biāo)簽，再按此步驟依次查詢子集01、10、11。

2 改進(jìn)防碰撞算法

ALOHA算法當(dāng)標(biāo)簽達(dá)到一定數(shù)量的時(shí)候，容易發(fā)生某些標(biāo)簽多次碰撞無法識(shí)別的狀況，也就是“標(biāo)簽饑餓”現(xiàn)象[8]。二進(jìn)制樹形轉(zhuǎn)化法則不存在這一現(xiàn)象。目前已經(jīng)存在的算法有動(dòng)態(tài)二叉樹搜索算法、動(dòng)態(tài)的四叉樹搜索算法、自適應(yīng)的二四叉樹防碰撞算法[9]。

二叉樹搜索時(shí)，不存在空閑時(shí)隙，但是碰撞時(shí)隙的數(shù)量非常多；四叉樹搜索時(shí)，可大幅度減少碰撞時(shí)隙，不過增加了空閑時(shí)隙的數(shù)量。自適應(yīng)的二四叉樹，引入碰撞因子的概念，根據(jù)當(dāng)前集合碰撞因子的大小，自適應(yīng)地選擇采用搜索樹的類型，從而大幅提高效率。

不過之前的文章由于考慮到引入八叉樹系統(tǒng)設(shè)計(jì)算法更加復(fù)雜，因此沒有對(duì)八叉樹進(jìn)行進(jìn)一步的分析，而是僅分析二四叉樹。當(dāng)標(biāo)簽數(shù)目較多時(shí)，為進(jìn)一步優(yōu)化算法，文中提出一種自適應(yīng)的二四八叉樹算法，以進(jìn)一步優(yōu)化標(biāo)簽碰撞識(shí)別過程。

動(dòng)態(tài)八四二叉樹搜索流程如圖1所示。

圖1 動(dòng)態(tài)八-四-二叉樹搜索流程

通常來講，當(dāng)系統(tǒng)內(nèi)的標(biāo)簽數(shù)量越多，則出現(xiàn)碰撞的位數(shù)也就越多，從而碰撞位占標(biāo)簽總比特位的比例也就越大。為了更好地決定采用幾叉樹進(jìn)行搜索，定義了碰撞因子μ來計(jì)算這個(gè)比例，以便有效地利用碰撞信息，提高算法效率。

定義：假設(shè)每個(gè)標(biāo)簽的ID碼長(zhǎng)度為n比特，其中碰撞間隙內(nèi)產(chǎn)生碰撞的比特位為nc，則

(1)

其中，碰撞因子μ包含了待識(shí)別的標(biāo)簽的數(shù)量的信息。

假設(shè)系統(tǒng)內(nèi)有M個(gè)待識(shí)別的標(biāo)簽，每個(gè)標(biāo)簽的ID碼長(zhǎng)度為n比特，其中任意一位不發(fā)生碰撞的概率為(1/2)M-1,由此可得：

(2)

式2表明，系統(tǒng)中標(biāo)簽的個(gè)數(shù)越大，碰撞因子值越高；反之，碰撞因子值越低。由此說明碰撞因子的大小可以用來估計(jì)待識(shí)別標(biāo)簽的數(shù)量。

在文獻(xiàn)[10]中給出了計(jì)算碰撞因子值的方法，即碰撞因子與叉樹的關(guān)系。假設(shè)系統(tǒng)內(nèi)有M個(gè)待識(shí)別的標(biāo)簽，自適應(yīng)多叉樹的叉數(shù)為L(zhǎng)，當(dāng)搜索的深度為1時(shí)，標(biāo)簽的識(shí)別概率為P(1)=(1-1/L)M-1；當(dāng)搜索深度為2時(shí)，識(shí)別概率為P(2)=P(1)[1-P(1)]；以此類推，當(dāng)搜索的深度為k時(shí)，得到標(biāo)簽的識(shí)別概率為P(k)=P(1)[1-P(1)]k-1。

所以，需要搜索的深度均值為：

(3)

所需的平均時(shí)隙為：

(4)

根據(jù)計(jì)算可知，當(dāng)L=M時(shí)，所需的平均時(shí)隙最少。理論上來講，待識(shí)別的標(biāo)簽越多，多叉樹的叉數(shù)越多，但實(shí)際上只考慮二叉樹、四叉樹和八叉樹。

通過比較得知：當(dāng)M<3時(shí)，T為T2；當(dāng)3≤M≤5時(shí)，T為T4；當(dāng)M>5,時(shí)，T為T8。其中，M=3為二叉樹和四叉樹的臨界值，此時(shí)計(jì)算得μ=0.75；M=5為四叉樹和八叉樹的臨界值，此時(shí)μ=0.937 5。因此得出，當(dāng)μ<0.75時(shí)，選擇使用二叉樹搜索；當(dāng)0.75≤μ≤0.937 5時(shí)，選擇四叉樹搜索；當(dāng)μ>0.937 5時(shí)，選擇使用八叉樹搜索。

EIAMS算法流程如圖2所示。

Step1：讀寫器初始化查詢堆棧，發(fā)出查詢命令。

Step2：與閱讀器前綴相符合的標(biāo)簽響應(yīng)。

Step3：若標(biāo)簽響應(yīng)數(shù)為1，識(shí)別成功，為成功時(shí)隙；若無標(biāo)簽響應(yīng)，識(shí)別失敗，為失敗時(shí)隙；若有多個(gè)標(biāo)簽響應(yīng)，則進(jìn)入碰撞時(shí)隙。

Step4：碰撞時(shí)隙：計(jì)算碰撞因子μ，若μ>0.937 5,采用八叉樹，根據(jù)碰撞首位，重新確立八個(gè)查詢代碼，并進(jìn)入棧記錄；若0.75<μ<0.937 5,則采用四叉樹，根據(jù)碰撞首位，重新確立四個(gè)標(biāo)簽查詢，并進(jìn)入棧記錄；若μ<0.75，則采用四叉樹，根據(jù)碰撞首位，重新確立八個(gè)標(biāo)簽查詢，并進(jìn)入棧記錄。

Step5：判斷棧，如果?？?，則結(jié)束，如果不為空，跳轉(zhuǎn)到Step2。

圖2 EIAMS算法流程

3 算法性能分析

標(biāo)簽在識(shí)別過程中的時(shí)隙總數(shù)即為時(shí)間復(fù)雜度。假設(shè)待識(shí)別的標(biāo)簽數(shù)為n，在純二叉樹搜索算法中，總時(shí)隙數(shù)為2n-1[11];在純四叉樹搜索時(shí)，有如下推導(dǎo)的過程：

在純四叉樹中，葉子節(jié)點(diǎn)的度為0，記葉子節(jié)點(diǎn)個(gè)數(shù)為n0；其他節(jié)點(diǎn)的度為4，記其他節(jié)點(diǎn)的個(gè)數(shù)為n4；此總節(jié)點(diǎn)數(shù)為N,有：

N=n0+n4

(5)

除根節(jié)點(diǎn)，其他所有節(jié)點(diǎn)都有一個(gè)根，考慮根的個(gè)數(shù)為：

N=0×n0+4×n4+1

(6)

聯(lián)立式1和式2可得：

n0=3×n4+1

(7)

由于n0=n+nk，nk為空閑時(shí)隙，因此

n+nk=3×n4+1

(8)

對(duì)于一個(gè)發(fā)生碰撞的時(shí)隙，其空閑時(shí)隙最大數(shù)量為2，最小數(shù)量為0。

當(dāng)一個(gè)碰撞產(chǎn)生2個(gè)空閑時(shí)隙時(shí)，nk=2×n4，代入式8可得n=n4+1，時(shí)隙總數(shù)為N=n+nk+n4=4n-3；當(dāng)一個(gè)碰撞不產(chǎn)生空閑時(shí)隙時(shí)，nk=0，代入式8可得n=3×n4+1，時(shí)隙總數(shù)N=n+n4=(4n-1)/3。

因此，在純四叉樹中識(shí)別的時(shí)隙總數(shù)取值范圍為：[(4n-1)/3,4n-3]。

同理可得，在純八叉樹中識(shí)別的時(shí)隙總數(shù)取值范圍為：[(8n-1)/7,8n-7][12]。

由此可見，改進(jìn)后的算法與之前的算法相比，在時(shí)間復(fù)雜度上沒有量的提高，在識(shí)別的時(shí)隙總數(shù)上有較為明顯的減少。因此，改進(jìn)算法近一步優(yōu)化了RFID防碰撞算法。

在實(shí)際應(yīng)用中，由于二叉樹、四叉樹、八叉樹在搜索流程中所占比例不同，因此在總時(shí)隙處理上不能簡(jiǎn)單地進(jìn)行平均，而是應(yīng)該進(jìn)行加權(quán)平均。采用平均方法與實(shí)際狀況盡管會(huì)存在一定差距，不過在總體趨勢(shì)上，基本是相同的。

4 實(shí)驗(yàn)仿真分析

根據(jù)上面的算法描述，采用MATLAB_R2017a對(duì)改進(jìn)算法與之前常見的二叉樹、四叉樹、二四叉樹等算法進(jìn)行仿真對(duì)比分析。

仿真過程中，四種算法統(tǒng)一采用隨機(jī)生成的16位RFID標(biāo)簽。對(duì)不同算法在標(biāo)簽總數(shù)從10到300以步長(zhǎng)為10變化，每種算法重復(fù)進(jìn)行1 000次進(jìn)行仿真，記錄下參數(shù)后最后取平均值。圖3為四種算法所需要的總時(shí)隙數(shù)、吞吐率的比較。

圖3 總時(shí)隙數(shù)變化仿真圖

為了更好地衡量算法的優(yōu)化程度，定義算法提升度的概念，根據(jù)時(shí)隙多少來衡量算法的優(yōu)化程度，算法提升度公式為：

(9)

將二-四叉樹算法與二四八叉樹算法選擇部分標(biāo)簽數(shù)量，列出算法提升度表格，如表1所示。

根據(jù)上述實(shí)驗(yàn)仿真結(jié)果可知，從總時(shí)隙上看，當(dāng)標(biāo)簽在數(shù)量較少時(shí)，二四八叉樹算法明顯優(yōu)于二四叉樹；而當(dāng)大于100時(shí)，二四八叉樹卻不如二四叉樹，不過兩種算法相差依然較小。根據(jù)算法提升度表格可以看出，隨著標(biāo)簽數(shù)量的提高，與二四叉樹相比改進(jìn)后的算法提升度在降低。因此，改進(jìn)后的算法更加適用于中小型系統(tǒng)[13]。

表1 算法提升度

吞吐率變化仿真如圖4所示。

圖4 吞吐率變化仿真圖

從吞吐率看，當(dāng)標(biāo)簽在100之內(nèi)時(shí)，二四八叉樹顯然優(yōu)于二四叉樹，當(dāng)標(biāo)簽大于100時(shí)，二四叉樹優(yōu)于二四八叉樹。不過對(duì)比單一的二叉樹和四叉樹，二四八叉樹無論在總時(shí)隙還是吞吐率上，都有明顯的優(yōu)化。

可見，在標(biāo)簽數(shù)目比較多，即碰撞率高時(shí)，引入八叉樹反而會(huì)減弱算法。以4位標(biāo)簽為例，分析樹形即可發(fā)現(xiàn)原因。當(dāng)采用二四八叉樹時(shí)，樹第一層為八叉樹，將前3位標(biāo)簽分開，由于標(biāo)簽長(zhǎng)度總為偶數(shù)，這時(shí)必定會(huì)有1層需要用二叉樹；如果采用二四叉樹，第一層對(duì)應(yīng)前兩位，第二層對(duì)應(yīng)后兩位，總時(shí)隙數(shù)比改進(jìn)后的算法反而要優(yōu)化。

5 結(jié) 論

為解決射頻識(shí)別過程中多個(gè)標(biāo)簽同時(shí)存在引發(fā)的碰撞問題，在自適應(yīng)二四叉樹防碰撞算法的基礎(chǔ)上，將八叉樹引入，提出了一種改進(jìn)的自適應(yīng)的二四八叉樹算法。算法通過計(jì)算標(biāo)簽的碰撞因子，自適應(yīng)地選擇最優(yōu)樹的叉樹，然后進(jìn)行搜索，從而大大減少了空閑時(shí)隙。對(duì)改進(jìn)算法進(jìn)行復(fù)雜度分析后，發(fā)現(xiàn)改進(jìn)算法的復(fù)雜度與標(biāo)簽數(shù)量近似呈線性關(guān)系。

針對(duì)不同標(biāo)簽數(shù)量的搜索過程，在總時(shí)隙數(shù)和吞吐率兩個(gè)方面對(duì)算法進(jìn)行仿真。結(jié)果表明：當(dāng)標(biāo)簽數(shù)目較少時(shí)，采用二四八叉樹相結(jié)合的算法優(yōu)化效果十分明顯，可以大幅度提高系統(tǒng)吞吐率；不過當(dāng)標(biāo)簽數(shù)目較多時(shí)，二四八叉樹在總時(shí)隙數(shù)上不如二四叉樹。與單純的二叉樹或者四叉樹相比，不論總時(shí)隙數(shù)多少，改進(jìn)后算法都具有明顯的提高。

在實(shí)際應(yīng)用中，如果標(biāo)簽長(zhǎng)度為奇數(shù)，或者標(biāo)簽中有奇數(shù)位數(shù)未使用，讀卡器不需要識(shí)別。這時(shí)候采用二四八叉樹將會(huì)有較優(yōu)的結(jié)果。

6 結(jié)束語

提出了一種改進(jìn)的自適應(yīng)的二四八叉樹算法，根據(jù)碰撞因子自適應(yīng)選擇搜索樹的叉數(shù)，仿真結(jié)果表明，在標(biāo)簽一定的數(shù)量?jī)?nèi)，算法大幅度減少了總時(shí)隙，提高了吞吐率，不過超過一定數(shù)量算法性能會(huì)降低，適用于小型的射頻識(shí)別系統(tǒng)。目前，算法僅僅研究了基于多叉樹二進(jìn)制防碰撞算法，今后可以在此基礎(chǔ)上，著重研究多種防碰撞算法的混合使用。