基于回溯的RFID防碰撞算法

董光禎，陳慶奎，2

（1.上海理工大學(xué) 光電信息與計(jì)算機(jī)學(xué)院，上海200093；2.上海理工大學(xué) 上海市現(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，上海200093）

0 引 言

隨著RFID 的應(yīng)用逐漸普及［1－3］，當(dāng)閱讀器的識(shí)別范圍出現(xiàn)多個(gè)標(biāo)簽時(shí)就產(chǎn)生標(biāo)簽爭(zhēng)搶信道的通信碰撞問(wèn)題，嚴(yán)重影響RFID 系統(tǒng)的性能［4］。為了有效改善RFID 系統(tǒng)的通信性能，由通信中的防碰撞算法進(jìn)而產(chǎn)生了標(biāo)簽防碰撞算法?，F(xiàn)行的標(biāo)簽防碰撞算法主要分為確定性的和隨機(jī)性的防碰撞算法［5－7］。確定性的防碰撞算法主要是基于輪詢的思想：借用二叉樹的數(shù)據(jù)結(jié)構(gòu)，將處于碰撞的標(biāo)簽分成左右兩個(gè)子樹（0／1），先查詢左子樹（0），若沒(méi)有碰撞，則正確識(shí)別標(biāo)簽，執(zhí)行相應(yīng)操作，若產(chǎn)生碰撞繼續(xù)劃分左右子樹（00／01），依次類推，直到識(shí)別出左子樹（0）中的所有標(biāo)簽，再依此查詢右子樹（1）。由于二進(jìn)制防碰撞算法的實(shí)用性更好，在這方面的研究相對(duì)較多，不同的研究人員對(duì)此提出各種各樣的改進(jìn)型算法［8－12］，但隨著標(biāo)簽數(shù)量增加，識(shí)別速率都有不同程度下降，文獻(xiàn)［8］中提出了一種基于后退式二進(jìn)制搜索算法的改進(jìn)算法，該算法有效地縮減了閱讀器的查詢次數(shù)，但標(biāo)簽返回信息的數(shù)據(jù)傳輸過(guò)程中仍有一定的數(shù)據(jù)冗余；文獻(xiàn) ［9，10］是基于跳躍式動(dòng)態(tài)樹形反碰撞算法的改進(jìn)，兩種算法都是通過(guò)一次性確定碰撞位然后在此基礎(chǔ)上輪詢檢測(cè)，優(yōu)化了查詢次數(shù)，但其問(wèn)題都是傳輸?shù)拿钗粩?shù)過(guò)多，數(shù)據(jù)冗余量大；文獻(xiàn)［11］中提出的改進(jìn)算法沒(méi)有充分利用已有的信息，標(biāo)簽識(shí)別過(guò)程中回送重復(fù)信息，隨著標(biāo)簽ID 及數(shù)量的增長(zhǎng)，勢(shì)必會(huì)使系統(tǒng)處理過(guò)多的不必要數(shù)據(jù)，從而使系統(tǒng)通信性能下降。文獻(xiàn)［12］提出了借用堆棧以及隊(duì)列的思想優(yōu)化標(biāo)簽識(shí)別過(guò)程，但因?yàn)槠湟肓诉^(guò)多的命令而使多標(biāo)簽識(shí)別過(guò)程隨標(biāo)簽增多性能增加并不是很明顯。本文在分析研究現(xiàn)有的二進(jìn)制防碰撞算法的基礎(chǔ)上，提出一種基于回溯的借助堆棧不間斷輪詢防碰撞算法，該算法通過(guò)減少標(biāo)簽識(shí)別過(guò)程中的迭代次數(shù)和發(fā)送數(shù)據(jù)量來(lái)提高RFID 系統(tǒng)的通信性能。

1 不間斷輪詢防碰撞算法

1.1 算法采用的編碼及交互命令

實(shí)現(xiàn)二進(jìn)制搜索算法的前提是能夠辨別出在閱讀器中數(shù)據(jù)沖突位的準(zhǔn)確位置，為此數(shù)據(jù)編碼采用曼徹斯特編碼［4，13］。閱讀器和應(yīng)答器之間的交互命令除傳統(tǒng)算法中的REQUEST、SELECT、READ／WTITE、UNSELECT 命令外［8，11］，增加POP、PUSH 命令。在動(dòng)態(tài)二進(jìn)制算法中，雖然已經(jīng)減少一些不必要的序列傳輸和數(shù)據(jù)通信量［11］，但不能有效的把數(shù)據(jù)傳輸量減少到最低，同樣，也不能很好的減少不必要的算法迭代。在本算法中將閱讀器的發(fā)送命令修改為當(dāng)前碰撞位，即發(fā)送命令只發(fā)送一位，應(yīng)答器的返回信息是當(dāng)前碰撞位的后面一位，這樣數(shù)據(jù)發(fā)送量將進(jìn)一步優(yōu)化。

1.2 算法過(guò)程描述

（1）閱讀器指令：二進(jìn)制防碰撞算法中，可有效識(shí)別碰撞位，而數(shù)據(jù)相同的非碰撞位在傳輸指令中是沒(méi)有實(shí)際意義的，因此，可以將動(dòng)態(tài)二進(jìn)制中的發(fā)送指令精簡(jiǎn)為一位（碰撞位），即每次發(fā)生碰撞閱讀器發(fā)送搜索指令時(shí)，只發(fā)送當(dāng)前碰撞位的搜索值0 或者1。首次搜索還是以REQUEST（NULL，8）作為當(dāng)前區(qū)域所有標(biāo)簽的激活指令，此時(shí)所有標(biāo)簽應(yīng)答，閱讀器標(biāo)記所有碰撞位，繼續(xù)最高碰撞位ID（XH）為0的標(biāo)簽響應(yīng)，將（XH）壓棧，暫時(shí)靜默最高碰撞位為1的標(biāo)簽。如此重復(fù)，直到閱讀器正確識(shí)別出一個(gè)標(biāo)簽。再回溯到發(fā)生碰撞的最低位，閱讀器將命令REQUEST（ID（XL），1）出棧發(fā)送，重復(fù)此過(guò)程直到區(qū)域內(nèi)的所有標(biāo)簽正確識(shí)別。閱讀器和標(biāo)簽的狀態(tài)轉(zhuǎn)移和工作流程圖如圖1、圖2所示。

（2）算法描述：設(shè)待識(shí)別標(biāo)簽序列號(hào)SN 位數(shù)為n，若第i位發(fā)生碰撞則標(biāo)記碰撞位為Xi，最高碰撞位為XH，最低碰撞位為XL，首先閱讀器發(fā)送req（null，n），所有靜默計(jì)數(shù)器為0 的標(biāo)簽響應(yīng)，閱讀器檢測(cè)并標(biāo)記碰撞位，將［ID（XH），1］壓棧，此位置為1的標(biāo)簽靜默計(jì)數(shù)器加1，繼續(xù)響應(yīng)碰撞位值為0的標(biāo)簽，如此進(jìn)行直到?jīng)]有碰撞發(fā)生正確識(shí)別出標(biāo)簽，然后查詢堆棧將［ID（XL），1］出棧，每出棧一次所有靜默標(biāo)簽的靜默計(jì)數(shù)器減1，如此循環(huán)直至閱讀器范圍內(nèi)的標(biāo)簽被正確識(shí)別，如上所述，發(fā)送一次命令之后肯定會(huì)有一個(gè)標(biāo)簽被識(shí)別并處理，如此發(fā)送的命令數(shù)即為所有標(biāo)簽SN 的碰撞位數(shù)k＋1，數(shù)據(jù)傳輸量為SN 的長(zhǎng)度n。

圖1 標(biāo)簽狀態(tài)轉(zhuǎn)移圖、工作流程

圖2 閱讀器工作流程

（3）識(shí)別過(guò)程：假設(shè)在活動(dòng)區(qū)域內(nèi)有8個(gè)8位的標(biāo)簽，下面以這8個(gè)標(biāo)簽的識(shí)別過(guò)程來(lái)簡(jiǎn)要說(shuō)明這個(gè)算法的原理和過(guò)程：A：10110100；B：10110101；C：10100101；D：10100100；E：11010101；F：11010100；G：11000100；H：11000101。在這個(gè)算法中，需要一塊存儲(chǔ)空間來(lái)對(duì)未碰撞的位和當(dāng)前閱讀器已發(fā)送的指令進(jìn)行存儲(chǔ)。其具體執(zhí)行過(guò)程如下：

1）Reader發(fā)送request（null，8）命令，激活區(qū)域內(nèi)所有標(biāo)簽（靜默計(jì)數(shù)器q＝0），并且標(biāo)簽應(yīng)答。Reader解碼得到的ID 為1？？？010？，對(duì)未碰撞位進(jìn)行存儲(chǔ)（1xxx010x）。碰撞位為6、5、4、0，碰撞位數(shù)為4位；

2）將最高碰撞位ID（6）壓棧，將最高碰撞位值為1的標(biāo)簽靜默，即靜默EFGH 標(biāo)簽；此時(shí)靜默計(jì)數(shù)器數(shù)值為1；

3）ABCD 響應(yīng)，第五位發(fā)生碰撞，（ID（5），0）響應(yīng)，靜默AB；其靜默計(jì)數(shù)器為1，將EFGH 靜默計(jì)數(shù)器的值加1；

4）CD 響應(yīng)，第四位發(fā)生碰撞，（ID（4），0）響應(yīng)，靜默C；同時(shí)之前的靜默標(biāo)簽靜默計(jì)數(shù)器加1；

5）D 響應(yīng)，無(wú)碰撞發(fā)生，正確識(shí)別，回溯至（ID（0），1）；同時(shí)發(fā)送一次激活命令，所有靜默標(biāo)簽的靜默計(jì)數(shù)器減1；

6）C響應(yīng)，無(wú)碰撞，正確識(shí)別，回溯至（ID（4），1）；同時(shí)所有靜默標(biāo)簽的靜默計(jì)數(shù)器減1；

圖3 標(biāo)簽識(shí)別過(guò)程

7）AB響應(yīng)，重復(fù)過(guò)程3）～6），AB正確識(shí)別；

8）重復(fù)過(guò)程2）～7），EFGH 正確識(shí)別；

圖3所示為標(biāo)簽識(shí)別的過(guò)程圖。在圖3 中，描述了標(biāo)簽識(shí)別及算法的回溯過(guò)程。根據(jù)算法搜索過(guò)程，在閱讀器發(fā)出當(dāng)前搜索指令后，該圖反映了標(biāo)簽響應(yīng)情況，體現(xiàn)了標(biāo)簽被識(shí)別時(shí)所接受的搜索指令，還能夠直觀的得出搜索全部標(biāo)簽時(shí)，閱讀器所需要發(fā)送指令的次數(shù)。通過(guò)識(shí)別過(guò)程所發(fā)送指令，能夠得到閱讀器搜索迭代數(shù)，進(jìn)一步的計(jì)算數(shù)據(jù)通信量。

1.3 算法性能分析

（1）迭代數(shù)分析：假設(shè)閱讀器區(qū)域內(nèi)有N 個(gè)ID 為M位待識(shí)別標(biāo)簽，其中碰撞位為x位。通過(guò)圖3所示的標(biāo)簽識(shí)別過(guò)程可知，不間斷輪詢的標(biāo)簽防碰撞算法識(shí)別全部標(biāo)簽需要的輪詢次數(shù)見表1（當(dāng)有一個(gè)碰撞位時(shí)，閱讀器可以同時(shí)識(shí)別兩個(gè)標(biāo)簽）。

表1 標(biāo)簽數(shù)量與迭代數(shù)的關(guān)系

即使在最不理想的情況下，標(biāo)簽數(shù)目N＝2x，最大迭代數(shù)為2X－1。如果由于在實(shí)際運(yùn)用中，N 的值可能會(huì)小于2x，查詢迭代數(shù)也會(huì)相應(yīng)減少。在這里，假設(shè)標(biāo)簽數(shù)目為最大。所以，識(shí)別單個(gè)標(biāo)簽所需的查詢次數(shù)為

（2）數(shù)據(jù)通信量分析：

數(shù)據(jù)的傳輸時(shí)間取決于ID 的長(zhǎng)度和搜索次數(shù)。在動(dòng)態(tài)二進(jìn)制搜索算法中，閱讀器平均每次傳送ID 的平均長(zhǎng)度為V，其中M 為標(biāo)簽長(zhǎng)度

閱讀器識(shí)別全部標(biāo)簽的總傳輸數(shù)據(jù)量為S

在本算法中，閱讀器只發(fā)送一位，因?yàn)榻栌昧硕褩?，命令發(fā)送次數(shù)減半，因此，閱讀器識(shí)別全部標(biāo)簽總傳輸量為

當(dāng)標(biāo)簽ID 位較長(zhǎng)時(shí)，在動(dòng)態(tài)二進(jìn)制算法中，所需要傳送的通信數(shù)量會(huì)隨著ID 的長(zhǎng)度而相應(yīng)增大，同時(shí)也不能避免某些位重復(fù)傳送，大大影響了系統(tǒng)的識(shí)別速度；在本算法中，閱讀器發(fā)送指令只發(fā)送一位碰撞位的值，即使在ID較長(zhǎng)的情況下，利用堆?？梢杂行p少發(fā)送次數(shù)，因而也不會(huì)影響系統(tǒng)的傳送速率。

2 實(shí)驗(yàn)分析

實(shí)驗(yàn)環(huán)境：根據(jù)動(dòng)態(tài)二進(jìn)制算法和基于回溯的不間斷輪詢防碰撞算法原理，在NS2環(huán)境［14］下仿真比較了相關(guān)算法的特性。設(shè)定標(biāo)簽ID 為8 位、16 位、64 位。因?yàn)樘S式動(dòng)態(tài)二進(jìn)制的性能明顯好于動(dòng)態(tài)二進(jìn)制防碰撞算法［8］，以下仿真分析只是比較跳躍式動(dòng)態(tài)二進(jìn)制與不間斷輪詢算法。以下為實(shí)驗(yàn)分析結(jié)果：

實(shí)驗(yàn)1：迭代次數(shù)比較

二進(jìn)制搜索算法識(shí)別率較高，沒(méi)有錯(cuò)誤判決的問(wèn)題，然而其時(shí)延比較長(zhǎng)，泄露信息較多，安全性較差，其信道利用率可達(dá)43%，當(dāng)待識(shí)別標(biāo)簽數(shù)目為n時(shí)，二進(jìn)制識(shí)別算法和動(dòng)態(tài)搜索算法平均識(shí)別一個(gè)標(biāo)簽需查詢log2n＋1次。而不間斷輪詢的回溯搜索算法識(shí)別n個(gè)標(biāo)簽的查詢次數(shù)是2n－1次。除激活命令外本算法每次查詢閱讀器發(fā)送和接受的命令都是1bit。當(dāng)標(biāo)簽數(shù)量較多時(shí)，本算法的有效性是明顯的。算法性能比較見表2。

表2 算法性能比較

仿真結(jié)果如圖4所示，圖4（a）為識(shí)別所有標(biāo)簽的總的迭代次數(shù)，圖4（b）為平均識(shí)別單個(gè)標(biāo)簽所需迭代次數(shù)。通過(guò)對(duì)比可以看出，不間斷輪詢的防碰撞算法明顯優(yōu)于跳躍式二進(jìn)制搜索算法，尤其在標(biāo)簽數(shù)目較多的情況下。

圖4 算法性能仿真比較

實(shí)驗(yàn)2：數(shù)據(jù)傳輸量分析

由圖5可見，跳躍式動(dòng)態(tài)二進(jìn)制防碰撞算法隨著標(biāo)簽ID 的增長(zhǎng)，其所需的數(shù)據(jù)傳輸量急劇增長(zhǎng)，而不間斷輪詢的防碰撞算法發(fā)送的數(shù)據(jù)量不受標(biāo)簽ID 位數(shù)的影響。

實(shí)驗(yàn)3：系統(tǒng)吞吐量分析

圖5 傳輸數(shù)據(jù)量比較

因?yàn)楦倪M(jìn)后的算法在數(shù)據(jù)傳輸量和迭代次數(shù)上有一定的優(yōu)化，所以系統(tǒng)吞吐率有明顯提升，仿真結(jié)果如圖6所示。

圖6 系統(tǒng)吞吐率比較

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

本文在動(dòng)態(tài)二進(jìn)制搜索算法的基礎(chǔ)上，對(duì)閱讀器和標(biāo)簽的交互命令以及搜索算法進(jìn)行了相應(yīng)改進(jìn)，進(jìn)而提出了利用堆棧進(jìn)行回溯的不間斷輪詢防碰撞算法。該算法優(yōu)化了閱讀器和標(biāo)簽之間的數(shù)據(jù)傳輸量，減少了閱讀器識(shí)別區(qū)域內(nèi)標(biāo)簽所需的迭代次數(shù)，提高了標(biāo)簽的識(shí)別速度。仿真驗(yàn)證表明，該算法性能明顯優(yōu)于傳統(tǒng)跳躍式動(dòng)態(tài)二進(jìn)制算法。本算法需要在標(biāo)簽序列號(hào)一端占用一定的數(shù)據(jù)空間以標(biāo)記標(biāo)簽的靜默程度，接下來(lái)的工作是將本算法應(yīng)用于不同頻段的RFID 融合識(shí)別系統(tǒng)。

［1］SUN Qibo，LIU Jie.Internet of things：Summarize on concepts，architecture and key technology problem ［J］.Journal of Beijing University of Posts and Telecommunications，2010，33（3）：1－9 （in Chinese）.［孫琪博，劉杰.物聯(lián)網(wǎng)：概念、架構(gòu)與關(guān)鍵技術(shù)研究綜述 ［J］.北京郵電大學(xué)學(xué)報(bào)，2010，33（3）：1－9.］

［2］Ngai EWT，Karen KL Moon，F(xiàn)rederick J Riggins，et al.RFID research：An academic literature review（1995－2005）and future research directions ［J］.Int J Production Economics，2008，112 （2）：510－520.

［3］Kang dong，Shi Xiqin.RFID core technology and typical application development case ［M］.Beijing：Posts ＆ Telecom Press，2008.

［4］Jia Xiaolin，F(xiàn)eng Quanyuan，Ma Chengzhen.An efficient anti－collision protocol for RFID tag identification ［J］.IEEE Communications Letters，November2010，14 （11）：1014－1016.

［5］Dheeraj K Klair，Chin Kwan－Wu，RaadRaad.A survey and tutorial of rfid anti－collision protocols ［J］.IEEE Communications Surveys ＆Tutorials，2010，12 （3）：400－421.

［6］KANG Dong，SHI Xiqin，LI Yongpeng.The core technology and case of typical applications of radio frequency identification（RFID） ［M］.Beijing：Post＆Telecom Press，2008 （in Chinese）.［康東，石喜勤，李勇鵬.射頻識(shí)別 （RFID）核心技術(shù)與典型應(yīng)用開發(fā)案例 ［M］.北京：人民郵電出版社.2008］.

［7］Mohammed Al－Medhwahi.AbdulsalamAlkholidi.A new hybrid frame ALOHA and binary splitting algorithm for anti－collision in RFID systems software ［C］／／International Conference on Telecommunications and Computer Networks，2010：219－224.

［8］FAN Wenjing，ZHANG Shanshan，TIAN Zhihui.Research on RFID anti－collision algorithm based on regressive－style binary search ［J］.Computer Applications and Software，2012，29（5）：191－194 （in Chinese）.［樊文靜，張姍姍，田智慧.基于后退式二進(jìn)制搜索的RFID防碰撞算法的研究 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2012，29 （5）：191－194.］

［9］GUO Hongyi，LI Sudan.An improved anti－collision algorithm based on binary－tree searing of jumping and dynamic ［J］.Computer＆Telecommunication，2009 （3）：57－59 （in Chinese）.［郭洪役，酈蘇丹.一種基于跳躍式動(dòng)態(tài)樹的二進(jìn)制搜索改進(jìn)算法 ［J］.電腦與電信，2009 （3）：57－59］

［10］WANG Yaqi.An improved anti－collision algorithm of RFID system ［J］. Microcontroller＆Embedded Systems，2007（9）：15－17 （in Chinese）.［王亞奇.一種改進(jìn)的RFID 系統(tǒng)反碰撞算法 ［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2007 （9）：15－17.］

［11］JIANG Lifen，LU Guizhang，XIN Yunwei.Research on anticollision algorithm in Radio frequency identification system［J］.Computer Engineering and Applications，2007，43（15）：29－32 （in Chinese）. ［姜麗芬，盧桂章，辛運(yùn)幃.射頻識(shí)別系統(tǒng)中的防碰撞算法研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43 （15）：29－32.］

［12］HUO Hua，WANG Yongjie.RFID anti－collision algorithm based on parallel processing ［J］.Computer Engineering，2011，37 （6）：263－265 （in Chinese）. ［霍華，王永杰.基于并行處理的RFID 防沖突算法 ［J］.計(jì)算機(jī)工程，2011，37 （6）：263－265.］

［13］DENG Yiwen，ZHANG Hongyu.Study on the anti－collision algorithm of the RFID read／write device ［J］.Electronic Design Engineering，2011，19 （19）：31－34 （in Chinese）. ［鄧一文，張紅雨.RFID高頻讀寫器防碰撞算法研究 ［J］.電子設(shè)計(jì)工程，2011，19 （19）：31－34.］

［14］ZHANG Hongbin，RONG Mengtian，DENG Xiaodong.Research on RFID system simulation tool based on NS ［J］.Computer Simulation，2008，25 （2）：127－135 （in Chinese）.［張宏斌，戎蒙恬，鄧曉東.基于NS的RFID 系統(tǒng)仿真工具研究 ［J］.計(jì)算機(jī)仿真，2008，25 （2）：127－135.］