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

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

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

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

1 二進(jìn)制防碰撞算法

1.1 基本二進(jìn)制防碰撞算法

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

圖1 基本二進(jìn)制防碰撞算法模型

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

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

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

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

表1 基本二進(jìn)制算法的識(shí)別過程

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

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

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

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

1.2 動(dòng)態(tài)二進(jìn)制防碰撞算法

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

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

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

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

1.3 后退式二進(jìn)制算法

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

表2 動(dòng)態(tài)二進(jìn)制算法的識(shí)別過程

表3 后退式二進(jìn)制算法的識(shí)別過程

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

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

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

2 改進(jìn)的二進(jìn)制搜索算法

2.1 算法改進(jìn)分析

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

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

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

2.有效減少識(shí)別時(shí)間

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

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

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

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

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

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

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

2.2 改進(jìn)式二進(jìn)制防碰撞算法描述

本次測試實(shí)驗(yàn)標(biāo)簽為八個(gè)，分別為：標(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；識(shí)別過程如表4所示。

表4 改進(jìn)式二進(jìn)制防碰撞算法的識(shí)別過程

接下來對(duì)以上識(shí)別過程進(jìn)行簡要分析：

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

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

3 算法性能分析

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

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

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

3.2 改進(jìn)算法模擬仿真對(duì)比

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

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

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

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

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

4 結(jié)束語

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