基于ALOHA和多叉樹(shù)的混合型RFID防碰撞算法

周偉輝，蔣年德，萬(wàn)心悅，閆成成，郭曉天

(1.東華理工大學(xué) 長(zhǎng)江學(xué)院，江西 撫州 344000；2.東華理工大學(xué) 信息工程學(xué)院，江西 南昌 330013)

射頻識(shí)別(RFID)是一種利用射頻信號(hào)通過(guò)空間電磁耦合實(shí)現(xiàn)無(wú)接觸式自動(dòng)識(shí)別的技術(shù)，是物聯(lián)網(wǎng)的關(guān)鍵支撐技術(shù)(錢(qián)志鴻等, 2012)。目前國(guó)內(nèi)RFID技術(shù)發(fā)展趨近成熟，標(biāo)簽制作成本不斷減少，其應(yīng)用范圍不斷擴(kuò)大，涉及到物流管理、防偽、動(dòng)物管理、門(mén)禁、智能識(shí)別等領(lǐng)域(Myung et al., 2006)。RFID系統(tǒng)構(gòu)成一般有三部分：標(biāo)簽、閱讀器和計(jì)算機(jī)后臺(tái)系統(tǒng)。RFID技術(shù)的三大難題：統(tǒng)一標(biāo)準(zhǔn)、多標(biāo)簽碰撞和信息安全，其中多標(biāo)簽碰撞指的是閱讀器發(fā)送信號(hào)，在信號(hào)范圍內(nèi)有多個(gè)標(biāo)簽同時(shí)響應(yīng)，閱讀器不能同時(shí)識(shí)別多個(gè)標(biāo)簽的現(xiàn)象。因此，提出一種有效且快速解決多標(biāo)簽碰撞問(wèn)題的RFID標(biāo)簽防碰撞算法將具有重要研究意義(王鑫等，2016)。

為解決標(biāo)簽碰撞問(wèn)題，已有兩大類(lèi)防碰撞算法：基于二進(jìn)制樹(shù)的確定性算法和基于ALOHA的隨機(jī)性算法(王雪等, 2010)?；跇?shù)的算法有二進(jìn)制搜索樹(shù)算法(王漢武等, 2018.)、動(dòng)態(tài)二進(jìn)制搜索樹(shù)算法(周偉輝等, 2018)、碰撞樹(shù)算法(Jia et al., 2012)、自適應(yīng)多叉樹(shù)算法(丁治國(guó)等, 2010)、一種改進(jìn)的自適應(yīng)多叉樹(shù)防碰撞算法(王漢武等, 2018)、二進(jìn)制分裂的空閑時(shí)隙消除算法(Su et al.,2017)、自調(diào)整混合樹(shù)(AHT)算法(宋建華等, 2014)等。基于ALOHA算法主要包括時(shí)隙ALOHA算法(Liva, 2011)、幀時(shí)隙ALOHA算法(Wu et al., 2011)、動(dòng)態(tài)幀時(shí)隙ALOHA(DFSA)算法(Deng et al., 2011)等。這兩大類(lèi)算法都能解決多標(biāo)簽碰撞問(wèn)題，但ALOHA算法具有隨機(jī)性，當(dāng)待識(shí)別標(biāo)簽數(shù)目龐大時(shí)，標(biāo)簽碰撞的概率增加，且可能會(huì)出現(xiàn)某些標(biāo)簽經(jīng)過(guò)N次碰撞，仍不能被識(shí)別，出現(xiàn)標(biāo)簽“餓死”現(xiàn)象，而基于樹(shù)的算法雖然可以實(shí)現(xiàn)100%的標(biāo)簽讀取率，但是識(shí)別時(shí)間較長(zhǎng)。

筆者針對(duì)在標(biāo)簽數(shù)量較大情況下，DFSA算法吞吐量降低并可能出現(xiàn)標(biāo)簽不能被100%識(shí)別和多叉樹(shù)算法識(shí)別標(biāo)簽時(shí)間增加的缺點(diǎn)，提出了一種ALOHA和多叉樹(shù)的混合型(HAMT)算法。該算法首先采用DFSA算法進(jìn)行標(biāo)簽識(shí)別，然后根據(jù)未識(shí)別標(biāo)簽數(shù)目動(dòng)態(tài)選擇多叉樹(shù)算法進(jìn)行標(biāo)簽識(shí)別，從而保證了標(biāo)簽100%被識(shí)別，提高吞吐率和縮短了識(shí)別時(shí)間。

1 HAMT算法

1.1 曼徹斯特編碼

曼徹斯特編碼通過(guò)電平的升降變化來(lái)描述邏輯“0”或邏輯“1”。在HAMT算法中，其主要作用是閱讀器可以通過(guò)它準(zhǔn)確地檢測(cè)出標(biāo)簽ID之間的碰撞位。假設(shè)有Tag1和Tag2兩個(gè)標(biāo)簽，它們ID編碼分別為：0010110和0010001，通過(guò)曼徹斯特編碼可以檢測(cè)出碰撞位信息為0x10xxx。

1.2 HAMT算法思想

HAMT算法識(shí)別標(biāo)簽經(jīng)過(guò)兩個(gè)階段：動(dòng)態(tài)幀時(shí)隙階段和多叉樹(shù)階段。動(dòng)態(tài)幀時(shí)隙階段：根據(jù)待識(shí)別標(biāo)簽數(shù)目確定時(shí)隙幀長(zhǎng)，再根據(jù)時(shí)隙選擇規(guī)則，標(biāo)簽選擇其自身所響應(yīng)的時(shí)隙號(hào)，最后判斷時(shí)隙的狀態(tài)，若碰撞則進(jìn)入多叉樹(shù)階段。多叉樹(shù)階段：根據(jù)碰撞標(biāo)簽的數(shù)目，動(dòng)態(tài)選擇多叉樹(shù)的叉數(shù)。閱讀器利用曼徹斯特編碼原則檢測(cè)碰撞位，利用碰撞位獲取查詢前綴。

1.3 HAMT算法流程

在HAMT算法中，用i表示時(shí)隙號(hào)，用Vogt算法(張小紅等, 2018)估計(jì)待識(shí)別標(biāo)簽數(shù)目N的值，并不斷采用DFSA算法和自適應(yīng)多叉樹(shù)算法進(jìn)行標(biāo)簽的識(shí)別，直到待識(shí)別標(biāo)簽數(shù)為0，算法結(jié)束(圖1)。

圖1 HAMT算法流程圖Fig.1 Flow chart of HAMT algorithm

步驟1：利用Vogt算法估算待識(shí)別標(biāo)簽數(shù)目N的值。有文獻(xiàn)(張小紅等, 2018)指出，幀長(zhǎng)L與標(biāo)簽總數(shù)N存在以下關(guān)系：

(1)

由公式(1)可計(jì)算出所需幀長(zhǎng)L；

步驟2：閱讀器發(fā)送Request(N,L)命令給所有標(biāo)簽，所有標(biāo)簽應(yīng)答；

步驟3：標(biāo)簽根據(jù)自身ID號(hào)從(0，L-1)時(shí)隙中選擇其所需時(shí)隙號(hào)i;

步驟4：判斷時(shí)隙i的狀態(tài)，有以下3種情況：

①時(shí)隙i為成功時(shí)隙，即該時(shí)隙中有且僅有1個(gè)標(biāo)簽響應(yīng)，為成功識(shí)別標(biāo)簽。進(jìn)行下一個(gè)時(shí)隙i=i+1;

②時(shí)隙i為空閑時(shí)隙，即該時(shí)隙沒(méi)有標(biāo)簽響應(yīng)，進(jìn)行下一個(gè)時(shí)隙i=i+1;

③時(shí)隙i為碰撞時(shí)隙，即該時(shí)隙有2個(gè)以上標(biāo)簽響應(yīng)，為碰撞標(biāo)簽，這些標(biāo)簽進(jìn)入下一步進(jìn)行處理；

步驟5：估算出碰撞標(biāo)簽數(shù)目n的值，判斷n是否大于等于4：

若n≥4，閱讀器檢測(cè)最高和次高碰撞位的值，根據(jù)這兩位的值，采用三叉樹(shù)算法或四叉樹(shù)算法進(jìn)行識(shí)別；

若n<4，閱讀器只檢測(cè)最高碰撞位的值，采用二叉樹(shù)算法進(jìn)行識(shí)別；

步驟6：判斷標(biāo)簽是否全部識(shí)別成功；

步驟7：若待識(shí)別標(biāo)簽還未全部識(shí)別成功，則跳轉(zhuǎn)到步驟1；

步驟8：若待識(shí)別標(biāo)簽全部被識(shí)別，則算法結(jié)束。

1.4 HAMT算法實(shí)例演示

假設(shè)閱讀器讀取范圍內(nèi)共有10個(gè)待識(shí)別標(biāo)簽，其ID編碼長(zhǎng)度為8位，分別為T(mén)agA:10000110，TagB:11010010，TagC:01000010，TagD:01001010，TagE:10010010，TagF:00001010，TagG:10110011，TagH:01010101，TagI:01101100，TagJ:00110011。采用HAMT算法識(shí)別過(guò)程如下：

(1)由于待識(shí)別標(biāo)簽數(shù)目N=10，可計(jì)算出幀長(zhǎng)L=8；

(2)檢測(cè)最高碰撞位，得到最高碰撞位以后3位的信息，根據(jù)這3位信息選擇響應(yīng)的時(shí)隙號(hào)，如(100)A=(100)E=4，所以TagA和TagE響應(yīng)在時(shí)隙4中，可依次分別計(jì)算出TagF響應(yīng)在時(shí)隙0中，TagJ響應(yīng)在時(shí)隙1中，TagC、D和H響應(yīng)在時(shí)隙2中，TagI響應(yīng)在時(shí)隙3中，TagG響應(yīng)在時(shí)隙5中，TagB響應(yīng)在時(shí)隙6中，成功識(shí)別了TagB、F、G、I和J；

(3) 根據(jù)上一步可以得到時(shí)隙2中有3個(gè)碰撞標(biāo)簽，分別是TagC、TagD和TagH，時(shí)隙4中有2個(gè)碰撞標(biāo)簽，分別是TagA和E；

(4)由于時(shí)隙2中有3個(gè)碰撞標(biāo)簽，所以閱讀器再檢測(cè)最高個(gè)次高碰撞位，得到碰撞信息為：“00”、“01”和“10”，采用三叉樹(shù)算法進(jìn)行識(shí)別，成功識(shí)別TagC、D和H。

(5)由于時(shí)隙4中有2個(gè)碰撞標(biāo)簽，分別為T(mén)agA和TagE，閱讀器檢測(cè)最高碰撞位，得到碰撞信息為：“0”和“1”，采用二叉樹(shù)算法進(jìn)行識(shí)別，成功識(shí)別TagA和TagE；

(6)所有標(biāo)簽全部識(shí)別完成，算法結(jié)束。

識(shí)別10個(gè)待識(shí)別標(biāo)簽數(shù)，所耗總時(shí)隙數(shù)為13個(gè)，只有1個(gè)空閑時(shí)隙和2個(gè)碰撞時(shí)隙，并且在多叉樹(shù)階段完全沒(méi)有碰撞時(shí)隙和空閑時(shí)隙的產(chǎn)生。所以HAMT算法可以大大減少碰撞時(shí)隙數(shù)和總時(shí)隙數(shù)，從而提高系統(tǒng)的吞吐率。

2 實(shí)驗(yàn)仿真

在MATLAB環(huán)境下進(jìn)行編程對(duì)HAMT算法進(jìn)行仿真分析與對(duì)比，對(duì)比的算法包括DFSA算法、ACT算法和AHT算法。待識(shí)別標(biāo)簽數(shù)N的取值范圍為[10,1 000]，仿真實(shí)驗(yàn)100次取其平均值，分別進(jìn)行了4組仿真實(shí)驗(yàn)對(duì)比：總時(shí)隙數(shù)對(duì)比、碰撞時(shí)隙數(shù)對(duì)比、通信開(kāi)銷(xiāo)對(duì)比和吞吐率對(duì)比。

圖2所示為4種不同算法所需的總時(shí)隙數(shù)。從圖2可以得出，HAMT算法所需總時(shí)隙數(shù)最少。當(dāng)待識(shí)別標(biāo)簽數(shù)為1 000時(shí)，HAMT、AHT、ACT和DFSA算法所需總時(shí)隙數(shù)分別約為1 400、1 810、2 100和5 500個(gè)，因此HAMT算法在總時(shí)隙數(shù)上有所優(yōu)化，特別是標(biāo)簽數(shù)量較大時(shí)，優(yōu)化更明顯。

圖2 不同算法的總時(shí)隙數(shù)Fig.2 Total number of slots with different algorithm

圖3表示的是4種算法的碰撞時(shí)隙數(shù)。從圖3中可以看出，HAMT算法所產(chǎn)生的碰撞時(shí)隙數(shù)明顯少于其他3種算法，是因?yàn)镠AMT算法只會(huì)在DFSA算法階段產(chǎn)生碰撞時(shí)隙，在多叉樹(shù)算法識(shí)別過(guò)程中可完全避免碰撞時(shí)隙的產(chǎn)生。

圖3 不同算法的碰撞時(shí)隙數(shù)Fig.3 Collision time slots of different algorithm

圖4為4種不同算法的吞吐率比較。吞吐率S指的是待識(shí)別標(biāo)簽總數(shù)N與在標(biāo)簽識(shí)別過(guò)程中所需總時(shí)隙數(shù)m之比，計(jì)算公式如下：

S=N/m

(2)

從圖4可以看出，HAMT算法的吞吐率始終能夠保持在0.72左右，明顯優(yōu)于其他3種算法。

圖4 不同算法吞吐率Fig.4 Throughput rate of different algorithm

圖5為4種不同算法在系統(tǒng)通信開(kāi)銷(xiāo)中的對(duì)比。通信開(kāi)銷(xiāo)包括閱讀器開(kāi)銷(xiāo)和標(biāo)簽開(kāi)銷(xiāo)，具體是指在標(biāo)簽識(shí)別過(guò)程中所要傳送命令的總長(zhǎng)度。從圖5可以看出，HAMT的通信開(kāi)銷(xiāo)最低。當(dāng)待識(shí)別標(biāo)簽總數(shù)位為1 000時(shí)，HAMT算法的通信開(kāi)銷(xiāo)為 1.0×10-5bit，明顯低于其他3種算法。

圖5 不同算法通信開(kāi)銷(xiāo)Fig.5 Communication costs of different algorithms

3 結(jié)論

針對(duì)二進(jìn)樹(shù)算法和ALOHA算法的不足，提出了一種ALOHA和多叉樹(shù)的混合型(HAMT)算法。該算法融合了二進(jìn)制算法和ALOHA算法的優(yōu)點(diǎn)，實(shí)現(xiàn)標(biāo)簽100%識(shí)別，并且識(shí)別速度快。仿真實(shí)驗(yàn)表明，HAMT算法減少了所需總時(shí)隙數(shù)，減少了系統(tǒng)通信開(kāi)銷(xiāo)，提高了吞吐率，使吞吐率能夠保持在0.72左右。因此HAMT算法可以解決RFID系統(tǒng)中多標(biāo)簽碰撞問(wèn)題，可在物聯(lián)網(wǎng)系統(tǒng)中推廣使用。