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

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

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

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

1 二進制防碰撞算法

1.1 基本二進制防碰撞算法

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

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

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

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

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

如果需要被檢測的標簽數目也是為N，則總的查詢次數Qsum為：

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

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

假設該RFID系統標簽長度為L，則閱讀器與標簽之間的交互數據的數量分別為：

由此可得，該RFID系統中，閱讀器和標簽傳輸的總信息量Psum為：

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

1.2 動態二進制防碰撞算法

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

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

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

其中，N為待識別標簽數目，L為標簽序列號的長度。

1.3 后退式二進制算法

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

表2 動態二進制算法的識別過程

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

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

同理，假設RFID系統閱讀器可識別范圍內標簽的數量還是N，則對應的后退式算法的查詢次數Qs和吞吐量S為：

假設標簽序列號長度仍為L，那么系統總傳輸數據量P為：

2 改進的二進制搜索算法

2.1 算法改進分析

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

1.降低交互數據的過度冗余

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

2.有效減少識別時間

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

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

（2）對于閱讀器識別內的應答碰撞信號，在進行識別前進行簡要判斷：

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

②如果碰撞位的識別區域序列為奇數，則繼續采用二叉樹法；

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

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

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

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

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

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

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

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

3 算法性能分析

3.1 改進算法公式推導

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

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

3.2 改進算法模擬仿真對比

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

通過模擬仿真圖2可知，在可識別標簽的數目一致的前提下，改進算法數據傳輸量遠遠低于其他算法，在實際應用場景中，相信改進算法的優勢會更加明顯。

圖2 幾種算法的數據傳輸量比較

圖3 三種算法查詢次數比較

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

4 結束語

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