物聯(lián)網(wǎng)RFID二進制防碰撞算法對比及優(yōu)化

（長春理工大學(xué) 電子信息工程學(xué)院，長春 130022）

互聯(lián)網(wǎng)技術(shù)的出現(xiàn)，帶動了相關(guān)技術(shù)的蓬勃發(fā)展，這其中對世界發(fā)展影響最大的當(dāng)屬物聯(lián)網(wǎng)［1］。物聯(lián)網(wǎng)，顧名思義，就是借助于外部識別技術(shù)將外界的“物”與互聯(lián)網(wǎng)聯(lián)系起來，按照約定好的規(guī)則對其進行區(qū)分管理。物聯(lián)網(wǎng)技術(shù)的核心是RFID技術(shù)，利用RFID技術(shù)閱讀器能夠?qū)?biāo)有不同標(biāo)簽的“物”進行區(qū)分。但是也由此產(chǎn)生了RFID技術(shù)的“致命”缺陷，當(dāng)閱讀器識別范圍內(nèi)存在多個標(biāo)簽，并且這些“物”的標(biāo)簽同時向閱讀器發(fā)送請求識別信號，可想而知，多個信號之間肯定會出現(xiàn)互相干擾現(xiàn)象，該現(xiàn)象在信號傳輸領(lǐng)域被稱作碰撞。碰撞現(xiàn)象的出現(xiàn)直接降低了閱讀器對標(biāo)簽的識別精度。為減少標(biāo)簽碰撞現(xiàn)象對物聯(lián)網(wǎng)系統(tǒng)的影響。國內(nèi)外物聯(lián)網(wǎng)專家開始了長時間的研究。截止到21世紀(jì)為止，應(yīng)對碰撞現(xiàn)象最有效的方法是引入防碰撞機制降低標(biāo)簽的碰撞概率。這些防碰撞機制發(fā)展至今可以總的分為四類：時分多址、頻分多址、空分多址和碼分多址。這其中又以時分多址使用最為普遍［2］。

以時分多址防碰撞機制為基礎(chǔ)，又衍生出了許多行之有效的防碰撞算法，這些算法又可以歸結(jié)為兩大類：ALOHA不確定性防碰撞算法和二進制搜索確定性算法。第一種不確定性算法是通過控制應(yīng)答器間接防止標(biāo)簽碰撞的算法，其優(yōu)點是投入成本低，系統(tǒng)功耗少，操作簡單易實現(xiàn)。缺點是在實際生產(chǎn)環(huán)境下伴隨著標(biāo)簽數(shù)目的增加，應(yīng)答器控制性能會急劇降低，不適用于標(biāo)簽數(shù)目巨大的場合。后一種算法相比于ALOHA算法，缺點是結(jié)構(gòu)復(fù)雜，操作難度大，識別過程復(fù)雜。優(yōu)點是識別效率不會隨標(biāo)簽數(shù)目的急劇增加而降低，非常適合標(biāo)簽數(shù)量巨大的場所。該算法在實際生活中的使用也是最為普遍的。由于二進制算法優(yōu)秀的識別效率，很多專家希望從其他角度可以有效彌補該算法的缺陷，隨后產(chǎn)生了許多改進式二進制算法：動態(tài)二進制算法、后退式二進制算法等。這些改進式算法都能有效降低RFID系統(tǒng)的標(biāo)簽碰撞概率［3］。

雖然以上改進的二進制算法有效降低了標(biāo)簽的碰撞幾率，但改進算法本身還存在各自的缺陷，后續(xù)通過對這些算法中存在的問題進行分析總結(jié)，在其基礎(chǔ)上提出了一個新的改進算法，在接下來的篇幅中會對以上算法進行探討，并對新的改進算法進行詳細(xì)闡述，最后通過模擬仿真軟件對算法的可行性進行測試。

1 二進制防碰撞算法

1.1 基本二進制防碰撞算法

二進制防碰撞算法的理論核心是二叉樹的深度優(yōu)先遍歷理論，具體工作流程如下：RFID系統(tǒng)運行過程中，出現(xiàn)碰撞現(xiàn)象，系統(tǒng)根據(jù)反饋信號將碰撞標(biāo)簽劃分為兩個結(jié)點，并分別標(biāo)記為0和1.然后繼續(xù)進行識別，如果標(biāo)記為1的節(jié)點中繼續(xù)出現(xiàn)碰撞現(xiàn)象［4］，再根據(jù)反饋信號增加新的結(jié)點，以此類推，直到所有標(biāo)簽全部識別為止。具體過程如圖1所示.

圖1 基本二進制防碰撞算法模型

基本二進制算法是基于二叉樹理論最基礎(chǔ)算法，它是利用RFID系統(tǒng)中的閱讀器在同一時刻發(fā)射出的不同的命令字符與被識別標(biāo)簽進行匹配從而確定標(biāo)簽是否出現(xiàn)碰撞現(xiàn)象。為了更好的解釋基本二進制算法的工作原理，以實際識別過程為例：

首先設(shè)定RFID系統(tǒng)所處環(huán)境，射頻識別系統(tǒng)閱讀器識別范圍內(nèi)存在四個不同的電子標(biāo)簽，分別為：標(biāo)簽A、B、C、D；這些標(biāo)簽內(nèi)分別存儲以下數(shù)據(jù)：0110101，0010011，0011010，0110110.接下來開始進行識別，閱讀器向區(qū)域內(nèi)標(biāo)簽發(fā)射請求命令，四個標(biāo)簽同時響應(yīng)。此時可能出現(xiàn)碰撞現(xiàn)象，啟動基本二進制防碰撞算法，直到所有標(biāo)簽準(zhǔn)確無誤識別為止。具體識別過程如表1所示。

假設(shè)基本二進制算法查詢次數(shù)的均值為Q，該參數(shù)的大小需要通過RFID系統(tǒng)中閱讀器的識別范圍內(nèi)的標(biāo)簽的數(shù)目N決定，由此可得計算公式：

如果需要被檢測的標(biāo)簽數(shù)目也是為N，則總的查詢次數(shù)Qsum為：

表1 基本二進制算法的識別過程

綜合公式（1）和公式（2）可得：并由此可得基本二進制算法的系統(tǒng)吞吐量S為：

假設(shè)該RFID系統(tǒng)標(biāo)簽長度為L，則閱讀器與標(biāo)簽之間的交互數(shù)據(jù)的數(shù)量分別為：

由此可得，該RFID系統(tǒng)中，閱讀器和標(biāo)簽傳輸?shù)目傂畔⒘縋sum為：

根據(jù)以上公式可知，基本二進制防碰撞算法能夠完全準(zhǔn)確識別N個標(biāo)簽，識別一個標(biāo)簽需要log2N+1次發(fā)布命令［5］。并且該算法在識別出一個標(biāo)簽后，會從初始點開始識別并發(fā)布命令，此時在系統(tǒng)內(nèi)部會產(chǎn)生大量的數(shù)據(jù)冗余。解決基本二進制算法的數(shù)據(jù)冗余問題，也是后續(xù)改進二進制算法的主要研究方向。

1.2 動態(tài)二進制防碰撞算法

動態(tài)二進制防碰撞算法是通過降低傳輸命令的長度減少通信數(shù)據(jù)量的。動態(tài)二進制算法工作流程與基本二進制算法完全相同，差別在于動態(tài)二進制算法中標(biāo)簽反饋回的序列號，只截取了可以識別的部分。具體識別過程如下表2所示。

通過比較表1，表2可以明顯看出，相同條件下，兩種算法的查詢次數(shù)相等。動態(tài)二進制通過降低反饋信息長度可以有效降低數(shù)據(jù)通訊數(shù)量，降低通訊時間。

假定以上算法的數(shù)據(jù)交互過程，只交互序列號信息，基本二進制算法需要傳輸完整序列號，動態(tài)二進制算法只需傳輸可識別位［6］，很明顯可以看出，在數(shù)據(jù)傳輸量方面動態(tài)二進制遠(yuǎn)低于基本二進制算法。由此可得，動態(tài)二進制算法的通信數(shù)據(jù)總量P為。

其中，N為待識別標(biāo)簽數(shù)目，L為標(biāo)簽序列號的長度。

1.3 后退式二進制算法

后退式二進制防碰撞算法也是以基本二進制算法為基礎(chǔ)，通過引入退避理論對基本二進制算法進行了優(yōu)化。后退式二進制算法在閱讀器完成一次識別任務(wù)后，直接返回上一個父節(jié)點，并轉(zhuǎn)向臨近分支繼續(xù)進行識別。具體識別過程如下表3所示.

表2 動態(tài)二進制算法的識別過程

表3 后退式二進制算法的識別過程

通過比較表1和表3可知，兩個算法的工作流程前三步是完全一致的，第4步開始發(fā)生變化，基本二進制算法直接返回到第一步重新開始，后退式僅返回至上一層父節(jié)點處，隨后又從臨近節(jié)點開始進行識別，最終實現(xiàn)了所有標(biāo)簽的識別。實驗結(jié)果表明，后退式僅僅比基本式二進制算法減少了一次查詢，沒有大幅度提升算法效率，但在大數(shù)目標(biāo)簽場合，后退式的提升效果會更加明顯。

同理，假設(shè)RFID系統(tǒng)閱讀器可識別范圍內(nèi)標(biāo)簽的數(shù)量還是N，則對應(yīng)的后退式算法的查詢次數(shù)Qs和吞吐量S為：

假設(shè)標(biāo)簽序列號長度仍為L，那么系統(tǒng)總傳輸數(shù)據(jù)量P為：

2 改進的二進制搜索算法

2.1 算法改進分析

由上一節(jié)的分析可知，當(dāng)識別長序列ID的標(biāo)簽時，基本二進制算法會產(chǎn)生大量的數(shù)據(jù)冗余，由于查詢順序的固化，該算法每次識別完成新標(biāo)簽后都要重新識別，增加了大量識別時間［7］。通過對比動態(tài)二進制和后退式算法的改進機制結(jié)合它們存在的缺陷提出了新的改進算法，改進角度從以下兩方面入手：

1.降低交互數(shù)據(jù)的過度冗余

一般情況下，RFID系統(tǒng)發(fā)布查詢命令后，閱讀器識別范圍內(nèi)的標(biāo)簽都會反饋，基礎(chǔ)二進制算法反饋全部信息，產(chǎn)生大量信息冗余，動態(tài)二進制算法將發(fā)生碰撞的標(biāo)簽數(shù)據(jù)分為兩部分［8］，前半部分為碰撞標(biāo)簽信息一致部分不進行傳輸，后半部分為碰撞標(biāo)簽區(qū)分位，最后只反饋區(qū)分位的序列信息，有效降低了交互信息的重復(fù)傳遞，在改進算法中繼續(xù)沿用該模式。

2.有效減少識別時間

根據(jù)基本二進制防碰撞算法的工作原理可知，當(dāng)RFID系統(tǒng)識別完成一個算法后，在進行下一部分識別前，會返回至初始節(jié)點，然后重新開始進行識別，增加了太多重復(fù)識別路程，浪費了識別時間。后退式算法是返回至上一層的父節(jié)點，在一定程度上增加了識別效率［9］。

（1）新改進算法除了返回上一父節(jié)點之前，會對上層節(jié)點進行判斷，選擇與現(xiàn)有節(jié)點判別序列號接近的節(jié)點進行返回，有效減少無用功。

（2）對于閱讀器識別內(nèi)的應(yīng)答碰撞信號，在進行識別前進行簡要判斷：

①如果碰撞位的識別區(qū)域序列為偶數(shù)，則采用四叉樹法；

②如果碰撞位的識別區(qū)域序列為奇數(shù)，則繼續(xù)采用二叉樹法；

③如果碰撞位的識別區(qū)域僅有一位特殊數(shù)字，則可以直接判斷，不進入防碰撞算法功能［10］。

通過以上措施能夠有效提升識別效率，降低識別時間。

2.2 改進式二進制防碰撞算法描述

本次測試實驗標(biāo)簽為八個，分別為：標(biāo)簽A：0110101；標(biāo)簽B：0010011；標(biāo)簽C：0011010；標(biāo)簽D：0110110；標(biāo)簽E：1001010；標(biāo)簽F：1110101；標(biāo)簽G：1001000；標(biāo)簽H：1110001；識別過程如表4所示。

表4 改進式二進制防碰撞算法的識別過程

接下來對以上識別過程進行簡要分析：

首先，第1步的標(biāo)簽信息一致部分為：null，表示沒有一致的標(biāo)簽序列，此時，所有標(biāo)簽都會反饋閱讀器發(fā)布的命令，由于標(biāo)簽碰撞節(jié)點位數(shù)為八位，所以使用四叉樹理論進行識別［11］。第2步發(fā)送00命令，反饋參數(shù)序列為001X01X，首先將高位碰撞位置0，繼續(xù)進行識別，識別結(jié)束后，返回臨近父節(jié)點0011繼續(xù)識別，識別結(jié)束返回臨近上一級的父節(jié)點01，此時反饋序列參數(shù)為：01101XX，繼續(xù)高位置0，發(fā)布命令011010X，識別標(biāo)簽返回臨近節(jié)點，發(fā)布命令011011X，識別并返回臨近節(jié)點10，得到反饋序列10010X0，由于此時僅有一個特殊碰撞位，直接識別即可，分別置0、1。識別出最后的兩個標(biāo)簽，識別過程結(jié)束。

根據(jù)上一節(jié)關(guān)于其他算法的公式可知，使用其他算法解決相同問題，基本二進制算法和動態(tài)二進制算法需要最少進行24次命令發(fā)布；后退式算法至少需要15次命令發(fā)布。而改進算法只用了9次。運算效率高下立判。此外，還使用了動態(tài)二進制算法的僅發(fā)送識別序列信息的方式，極大的降低了數(shù)據(jù)冗余量。

3 算法性能分析

3.1 改進算法公式推導(dǎo)

假設(shè)改進算法與其他算法處于相同環(huán)境下，可識別標(biāo)簽數(shù)為N，由于改進算法存在多種判定情況，此時以不出現(xiàn)單個碰撞位情況作為討論對象，此時該改進算法的查詢次數(shù)為：2N-1，如果出現(xiàn)單個碰撞位情況，并設(shè)其次數(shù)為x，此時總的查詢次數(shù)Qs為：

并且由此可得，同等條件下，改進算法識別全部標(biāo)簽的數(shù)據(jù)交互總量P為：

3.2 改進算法模擬仿真對比

通過使用MATALAB仿真軟件對上述二進制算法在數(shù)據(jù)傳輸量、查詢次數(shù)兩個方面進行仿真得到如圖5、圖6所示的比較結(jié)果［12］。

通過模擬仿真圖2可知，在可識別標(biāo)簽的數(shù)目一致的前提下，改進算法數(shù)據(jù)傳輸量遠(yuǎn)遠(yuǎn)低于其他算法，在實際應(yīng)用場景中，相信改進算法的優(yōu)勢會更加明顯。

圖2 幾種算法的數(shù)據(jù)傳輸量比較

圖3 三種算法查詢次數(shù)比較

改進算法不僅在傳輸數(shù)據(jù)冗余上遠(yuǎn)低于其他算法，在查詢次數(shù)上也遠(yuǎn)低于基本二進制算法，由圖3可知，改進算法的識別效率遠(yuǎn)高于其他算法，具有實際可行［13］。

4 結(jié)束語

通過對現(xiàn)有的基本二進制算法的運行情況進行了研究，以及對改進型的二進制算法進行了對比，沿用其優(yōu)秀部分，避免其有弊部分，提出了新的改進二進制算法，該算法從多個角度出發(fā)降低了傳輸數(shù)據(jù)數(shù)量，減少了傳輸時間，有效解決了傳輸過程數(shù)據(jù)冗余。最后通過實際模擬實驗進行了驗證，改進算法同比與其他傳統(tǒng)算法具有很高的優(yōu)勢，具有實際推廣的可行性，對于物聯(lián)網(wǎng)背景下的RFID大數(shù)目標(biāo)簽場景具有借鑒意義。