李欣怡 李曉武 游進(jìn)國(guó) 賈連印 丁家滿 李潤(rùn)鑫

（昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院）

隨著社會(huì)的發(fā)展，物聯(lián)網(wǎng)技術(shù)已逐步滲透到人們的生活中，它使物體和機(jī)械能夠互聯(lián)并共享收集到的信息［1］。 射頻識(shí)別技術(shù)（RFID）作為物聯(lián)網(wǎng)技術(shù)的感知層，發(fā)揮著重要的作用。在RFID 識(shí)別過程中，閱讀器識(shí)別區(qū)域內(nèi)有若干標(biāo)簽隨機(jī)分布， 當(dāng)一個(gè)以上的標(biāo)簽同時(shí)與閱讀器進(jìn)行通信時(shí)，它們的反向散射信號(hào)相互抵消，導(dǎo)致閱讀器不能獲取任何信息，這被稱為碰撞。 在沒有任何機(jī)制或措施協(xié)調(diào)閱讀器和標(biāo)簽之間通信過程的情況下，閱讀器將無法正確讀取標(biāo)簽ID 號(hào)，那么此次識(shí)別過程失敗，進(jìn)入再次識(shí)別過程，一直重復(fù)以上步驟，直到閱讀器識(shí)別范圍內(nèi)的所有標(biāo)簽都被成功識(shí)別為止［2］。

目前常用的標(biāo)簽防碰撞算法主要分為兩類，分別是基于樹的確定性防碰撞算法和基于ALOHA 的隨機(jī)性防碰撞算法［3］。基于樹的確定性防碰撞算法識(shí)別效率較高，但由于要遍歷所有標(biāo)簽，所花時(shí)間較長(zhǎng)；基于ALOHA 的隨機(jī)性防碰撞算法雖然簡(jiǎn)單，但是容易產(chǎn)生“標(biāo)簽饑餓”現(xiàn)象，隨著標(biāo)簽數(shù)量的增多，系統(tǒng)吞吐率也逐步下降。

筆者提出一種將兩類算法相結(jié)合的方法，整合了兩類算法各自的優(yōu)勢(shì)，同時(shí)使用尾碼應(yīng)答機(jī)制減少傳輸所需的時(shí)間成本，將該方法應(yīng)用于單閱讀器移動(dòng)RFID 系統(tǒng)中， 通過理論分析和MATLAB 仿真實(shí)驗(yàn)驗(yàn)證，改進(jìn)后的算法能降低時(shí)間成本，使系統(tǒng)性能有一定提高。

1 單閱讀器移動(dòng)RFID 系統(tǒng)

單閱讀器移動(dòng)RFID 系統(tǒng)是單個(gè)閱讀器采用移動(dòng)方法去識(shí)別一個(gè)區(qū)域內(nèi)標(biāo)簽的系統(tǒng)［4］。 這種單閱讀器移動(dòng)RFID 系統(tǒng)只適用于中小型區(qū)域的標(biāo)簽識(shí)別，因?yàn)槿绻R(shí)別區(qū)域過大，那么通過移動(dòng)閱讀器讓大區(qū)域內(nèi)的標(biāo)簽都能進(jìn)入閱讀器信號(hào)區(qū)并被識(shí)別需要花費(fèi)較多的時(shí)間［5］。 該系統(tǒng)的模型如圖1 所示，待識(shí)別區(qū)域A 內(nèi)隨機(jī)分布著若干待識(shí)別的標(biāo)簽，閱讀器識(shí)別區(qū)域?yàn)镻，使用者手持單閱讀器沿固定路徑移動(dòng)識(shí)別標(biāo)簽。

圖1 單閱讀器移動(dòng)RFID 系統(tǒng)場(chǎng)景

在本文的識(shí)別過程中，采用尾碼應(yīng)答機(jī)制可以減少傳輸時(shí)間成本，標(biāo)簽不需要發(fā)送完整的ID號(hào)給閱讀器，只需要發(fā)送小長(zhǎng)度尾碼即可。

2 RFID 系統(tǒng)中傳統(tǒng)的標(biāo)簽防碰撞算法

2.1 幀時(shí)隙ALOHA（FSA）算法

幀時(shí)隙ALOHA 算法在時(shí)隙ALOHA 算法的基礎(chǔ)上引入了幀的概念，其主要思想是：將若干個(gè)時(shí)隙組成一個(gè)幀，幀指的是閱讀器兩次請(qǐng)求操作之間的時(shí)間間隔， 標(biāo)簽只能隨機(jī)在0-L-1 內(nèi)選擇一個(gè)時(shí)隙和閱讀器進(jìn)行通信。 該協(xié)議的時(shí)隙存在3 種情況：空閑時(shí)隙,即沒有標(biāo)簽進(jìn)行響應(yīng)；碰撞時(shí)隙， 在某個(gè)時(shí)隙有大于一個(gè)的標(biāo)簽同時(shí)對(duì)閱讀器進(jìn)行響應(yīng)，就會(huì)產(chǎn)生標(biāo)簽信息的碰撞［6］；成功時(shí)隙，有且僅有一個(gè)標(biāo)簽響應(yīng)，閱讀器能成功讀取到標(biāo)簽信息。 未被成功識(shí)別的標(biāo)簽，需要在下一輪中重新進(jìn)行識(shí)別。

下面舉例對(duì)該算法進(jìn)行說明，設(shè)幀長(zhǎng)L 為3，待識(shí)別區(qū)域內(nèi)有5 個(gè)標(biāo)簽。 表1 是幀時(shí)隙ALOHA 算法的工作過程。

表1 幀時(shí)隙ALOHA 算法工作過程

2.2 動(dòng)態(tài)幀時(shí)隙ALOHA（DFSA）算法

動(dòng)態(tài)幀時(shí)隙ALOHA 算法是在幀時(shí)隙ALOHA 算法上改進(jìn)得來的，幀時(shí)隙ALOHA 算法中，由于幀長(zhǎng)固定不變，當(dāng)標(biāo)簽數(shù)量和幀長(zhǎng)相差較大時(shí)，系統(tǒng)性能很差。動(dòng)態(tài)幀時(shí)隙ALOHA 算法中，如果使幀長(zhǎng)和標(biāo)簽數(shù)量近似相等，系統(tǒng)吞吐率能維持在最大值。 具體解決辦法是根據(jù)預(yù)估標(biāo)簽數(shù)量動(dòng)態(tài)調(diào)整下一幀幀長(zhǎng)，如果該幀中碰撞時(shí)隙較多，那么增加下一幀的幀長(zhǎng)，反之減小下一幀的幀長(zhǎng)。

2.3 二進(jìn)制搜索（BS）算法

二進(jìn)制搜索算法采用比特沖突檢測(cè)協(xié)議作為防碰撞方案［7］。 閱讀器以二進(jìn)制序號(hào)為參數(shù)向標(biāo)簽發(fā)送請(qǐng)求命令，收到命令的標(biāo)簽將自己的序號(hào)與閱讀器發(fā)送的序號(hào)作比較，如果自己的序號(hào)小于等于閱讀器發(fā)送的序號(hào)，就將自己的編碼發(fā)送給閱讀器，閱讀器逐位識(shí)別相應(yīng)的標(biāo)簽［8］。如果標(biāo)簽之間發(fā)生碰撞，閱讀器根據(jù)碰撞位減小序號(hào)繼續(xù)搜索；如果標(biāo)簽之間沒發(fā)生碰撞，則成功識(shí)別到一個(gè)標(biāo)簽，閱讀器以初始序號(hào)為參數(shù)重新開始搜索，直至所有標(biāo)簽搜索完畢。

2.4 后退式二進(jìn)制搜索（BBS）算法

后退式二進(jìn)制搜索算法是二進(jìn)制搜索算法的一種改進(jìn)。 改進(jìn)的思路是：當(dāng)一個(gè)標(biāo)簽成功被識(shí)別后，閱讀器不會(huì)返回到原始的碰撞節(jié)點(diǎn)繼續(xù)搜索，它將退回到節(jié)點(diǎn)的上層，即父節(jié)點(diǎn)［9］。

假 設(shè) 有 4 個(gè) 標(biāo) 簽:Tag1 10110010，Tag2 10100011，Tag3 10110011，Tag4 11100011。后退式二進(jìn)制搜索算法識(shí)別流程如圖2 所示。

圖2 后退式二進(jìn)制搜索算法識(shí)別流程

3 單閱讀器移動(dòng)RFID 系統(tǒng)下FSA 和BBS 結(jié)合的標(biāo)簽防碰撞算法

3.1 算法流程

工作原理為：在待識(shí)別區(qū)域內(nèi)，手持單閱讀器沿固定路徑對(duì)標(biāo)簽進(jìn)行識(shí)別。 閱讀器發(fā)送讀取標(biāo)簽尾碼指令，在應(yīng)答區(qū)域內(nèi)的標(biāo)簽生成一個(gè)小于等于幀大小的隨機(jī)數(shù)，隨機(jī)時(shí)隙數(shù)為0 的標(biāo)簽將自己的尾碼發(fā)給閱讀器。

RFID 閱讀器以幀時(shí)隙ALOHA 算法接收標(biāo)簽發(fā)送過來的尾碼，閱讀器有3 種響應(yīng)情況：

a. 空閑時(shí)隙（slot_idle）。 信號(hào)區(qū)內(nèi)沒有標(biāo)簽尾碼選擇該時(shí)隙與閱讀器進(jìn)行通信，閱讀器讀取不到任何信息。

b. 成功時(shí)隙（slot_succ）。 信號(hào)區(qū)內(nèi)只有一個(gè)標(biāo)簽尾碼選擇該時(shí)隙與閱讀器進(jìn)行通信，閱讀器能成功讀取到該標(biāo)簽尾碼信息。 閱讀器將該尾碼與尾碼表進(jìn)行比較， 如果該尾碼未在尾碼表中，則該標(biāo)簽為全新標(biāo)簽，閱讀器發(fā)送讀取剩余信息的指令， 收到剩余信息后進(jìn)行整合并置靜默；若該尾碼已出現(xiàn)在尾碼表中，則將該標(biāo)簽判定為已識(shí)別標(biāo)簽，不作任何處理。

c. 碰撞時(shí)隙（slot_coll）。 信號(hào)區(qū)內(nèi)多個(gè)標(biāo)簽尾碼選擇該時(shí)隙與閱讀器進(jìn)行通信，標(biāo)簽尾碼之間發(fā)生碰撞，此時(shí)閱讀器采用BBS 算法對(duì)碰撞時(shí)隙的各個(gè)標(biāo)簽進(jìn)行處理，閱讀器通過對(duì)尾碼的編號(hào)進(jìn)行按位搜索，收到命令的標(biāo)簽尾碼將自己的序號(hào)與閱讀器發(fā)送的序號(hào)進(jìn)行對(duì)比，如果小于等于閱讀器發(fā)送的序號(hào)，則將自己的尾碼序號(hào)發(fā)給閱讀器，若繼續(xù)發(fā)生碰撞，閱讀器減小序號(hào)繼續(xù)搜索；若沒發(fā)生碰撞，閱讀器成功識(shí)別一個(gè)標(biāo)簽尾碼，對(duì)成功識(shí)別的標(biāo)簽尾碼處理步驟和成功時(shí)隙一樣， 直至碰撞時(shí)隙的所有標(biāo)簽處理完畢，進(jìn)入下一個(gè)時(shí)隙，碰撞時(shí)隙處理流程如圖3 所示。

圖3 改進(jìn)算法碰撞時(shí)隙處理流程

3.2 系統(tǒng)性能分析

3.2.1 幀時(shí)隙ALOHA 算法性能分析

在幀長(zhǎng)為64 的一幀中，各時(shí)隙的概率如圖4所示。

圖4 各時(shí)隙概率圖

系統(tǒng)效率為：

系統(tǒng)所需時(shí)隙數(shù)為：

對(duì)式（5）求導(dǎo)可得，當(dāng)待識(shí)別標(biāo)簽n 與幀長(zhǎng)N 近似相等時(shí)，系統(tǒng)獲得最大吞吐率。 這意味著可以通過設(shè)置幀長(zhǎng)來優(yōu)化瞬時(shí)吞吐率［10］。

3.2.2 后退式二進(jìn)制搜索算法性能分析

在BBS 算法中，假設(shè)待識(shí)別區(qū)域內(nèi)有n 個(gè)標(biāo)簽，算法完成對(duì)n 個(gè)標(biāo)簽的搜索需要的次數(shù)為S（n），計(jì)算如下：

成功識(shí)別所有標(biāo)簽的系統(tǒng)效率為：

3.2.3 改進(jìn)算法性能分析

整個(gè)標(biāo)簽的產(chǎn)品電子代碼 （EPC 碼） 為64位，傳輸識(shí)別整個(gè)標(biāo)簽需要1 時(shí)隙，文中取16 位的尾碼，則傳輸識(shí)別標(biāo)簽尾碼只需0.25 個(gè)時(shí)隙。

設(shè)待識(shí)別區(qū)域內(nèi)的標(biāo)簽數(shù)量為n，幀長(zhǎng)為N，尾碼長(zhǎng)為L(zhǎng)_suffix，尾碼重復(fù)出現(xiàn)的概率為：

計(jì)算可得， 當(dāng)尾碼長(zhǎng)16 位、 標(biāo)簽數(shù)為100時(shí)，尾碼重復(fù)出現(xiàn)的概率僅0.072 78%。 在本文中一個(gè)尾碼傳輸并識(shí)別只需要花費(fèi)0.25 個(gè)時(shí)隙，為了更直觀地比較系統(tǒng)性能，在改進(jìn)算法中由于重復(fù)識(shí)別而浪費(fèi)的時(shí)間忽略不計(jì)。 而重復(fù)出現(xiàn)的尾碼中為不同標(biāo)簽的概率更低，因此在文中重復(fù)出現(xiàn)的標(biāo)簽判定為已識(shí)別標(biāo)簽。

每次成功時(shí)隙識(shí)別一個(gè)標(biāo)簽，則碰撞時(shí)隙處理的標(biāo)簽數(shù)為：

其中，n_coll 為碰撞時(shí)隙處理的標(biāo)簽數(shù)，n_succ 為成功時(shí)隙處理的標(biāo)簽數(shù)。

碰撞時(shí)隙的標(biāo)簽用后退式二進(jìn)制搜索算法進(jìn)行處理， 處理所有碰撞時(shí)隙標(biāo)簽所需的時(shí)間為：

則改進(jìn)算法所需要的時(shí)間成本為：

改進(jìn)算法的系統(tǒng)效率為：

3.3 改進(jìn)算法仿真結(jié)果分析

采用MATLAB 進(jìn)行仿真實(shí)驗(yàn)， 標(biāo)簽數(shù)為500，標(biāo)簽EPC 碼為64 位，每次傳輸識(shí)別一個(gè)標(biāo)簽需要1 個(gè)時(shí)隙。 DFSA 算法中初始幀長(zhǎng)為256，用Schoute 估算法預(yù)估標(biāo)簽數(shù)量； 改進(jìn)算法中采用固定幀時(shí)隙幀長(zhǎng)為256，尾碼為16 位，每次傳輸識(shí)別一個(gè)標(biāo)簽尾碼需0.25 個(gè)時(shí)隙。

不同算法時(shí)間成本對(duì)比如圖5 所示。

圖5 不同算法時(shí)間成本對(duì)比

由圖5 可以看出， 識(shí)別相同數(shù)量的標(biāo)簽，改進(jìn)算法所需的時(shí)間成本比傳統(tǒng)單一算法低很多。

不同算法系統(tǒng)效率對(duì)比如圖6 所示。

圖6 不同算法系統(tǒng)效率對(duì)比

由圖6 可以看出， 識(shí)別相同數(shù)量的標(biāo)簽，動(dòng)態(tài)幀時(shí)隙ALOHA 算法的系統(tǒng)效率僅為30%左右， 后退式二進(jìn)制搜索算法的系統(tǒng)效率保持為50%左右， 而改進(jìn)算法的系統(tǒng)效率最高可達(dá)60%，且一直保持在50%以上。

4 結(jié)束語(yǔ)

在分析幀時(shí)隙ALOHA 算法和后退式二進(jìn)制搜索算法的基礎(chǔ)上，將兩類算法結(jié)合在單閱讀器移動(dòng)RFID 系統(tǒng)中使用。 改進(jìn)算法吸取了幀時(shí)隙ALOHA 算法識(shí)別時(shí)間較短和后退式二進(jìn)制搜索算法標(biāo)簽識(shí)別率高的優(yōu)勢(shì)，使用尾碼應(yīng)答機(jī)制減少時(shí)間成本。 通過對(duì)改進(jìn)算法的仿真，單閱讀器移動(dòng)RFID 系統(tǒng)所花費(fèi)的時(shí)間成本有所下降，而系統(tǒng)效率有一定提升。