物聯網RFID多標簽識別防碰撞算法研究與實現

王超梁 趙成 周鵬

摘 要：物聯網RFID多標簽識別防碰撞算法對系統的識別效率和穩定性至關重要。為了解決多標簽識別的碰撞問題，對 ALOHA及其改進算法進行了仿真分析，給出了不同時隙長度時標簽數目與系統吞吐量的關系，提出了一種自適應動態調整幀長的防碰撞算法。仿真結果表明，隨著標簽數量的增加，自適應動態調整時隙長度的防碰撞算法吞吐率明顯優于固定時隙算法和傳統動態時隙算法。

關鍵詞：物聯網；RFID；ALOHA；多標簽識別；防碰撞

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2018）01-00-02

0 引 言

射頻識別（Radio Frequency Identification，RFID）依靠非接觸式空間電磁感應實現電子標簽和讀寫器之間的信息交互，完成標簽信息的傳遞，被廣泛應用于智慧物流、智能交通等領域。 RFID多目標識別系統中的碰撞問題分為讀寫器碰撞和標簽碰撞兩種，多標簽識別防碰撞算法的研究，解決了多個標簽同時與一個讀寫器進行通信的碰撞問題。在高頻電子標簽識別領域，標簽的防碰撞一般采用基于TDMA的ALOHA算法及其改進算法，ALOHA算法性能會隨著標簽數量的增加急劇惡化，導致信道利用率偏低；而基于確定性的二進制樹搜索算法要遍歷所有標簽識別的可能性，故搜索效率較低。本文在分析ALOHA及其改進算法的基礎上提出了自適應動態時隙的改進算法。

1 基于ALOHA算法的標簽防碰撞算法

1.1 ALOHA算法

ALOHA算法是一種非常簡單的TDMA算法，最早用于解決網絡通信中數據包的擁堵問題，通常用于簡單的RFID系統中。采用標簽先發言的方式，自動向讀寫器發送自身的ID信息，完成身份認證后，只要有符合條件的數據包需要傳輸，讀寫器和標簽就開始通信，直至完成數據包交互。因此，這種處理機制本身與應答器控制、隨機的TDMA算法有關，兩個標簽可以在不同的時間發送請求，從而避免數據發生碰撞，如圖1所示。但該算法在數據幀發送的過程中發生碰撞的概率很大，而且標簽沒有載波監聽糾錯能力。ALOHA算法平均交換的數據包量在G=0.4時達到最大，仿真結果如圖2所示。

平均交換的數據包含量G可以表示為：

如果RFID系統吞吐率用平均吞吐率S表示，其值等于1時表示無數據包發生碰撞，其值等于0時表示沒有數據包傳輸成功，平均吞吐率S為：

可以得到，純ALOHA算法的最佳信道利用率為18.4%，提高信道利用率和數據吞吐量可采用，標簽只在規定的同步時隙內才傳輸數據包。

1.2 時隙ALOHA算法

時隙ALOHA算法在ALOHA算法的基礎上進行了改進，把標簽信息傳輸的時間劃分為若干個離散的時隙，數據包只能在時隙的起始端傳輸，以有效地將單純ALOHA算法的碰撞周期縮減為原來的一半，同時將信道利用率也提高一倍。當標簽進入讀寫器的識別范圍并開始通信時，標簽只在規定的時間間隙內發送數據；當讀寫器不工作或者標簽的時隙結束時，標簽發送請求命令無效，讀寫器響應標簽請求。相比ALOHA算法，時隙ALOHA算法在很大程度上避開了請求高峰期，碰撞概率為ALOHA算法的一半。由式（3）、（4）可得當G=1時，吞吐率Q的最大值可以達到36.8%，相比ALOHA算法提高了一倍。

1.3 幀時隙ALOHA算法

幀時隙ALOHA算法是指在規定的時隙內，標簽可以選擇該時隙內的任一數據信道發送數據，如果選擇的信道只有一個標簽或占用信道的時間小于時隙長度，讀寫器可成功接收數據。反之，讀寫器接收數據失敗，而未完成數據傳輸的標簽將進入下一循環重新選擇時隙（通道）。這種算法的優點是響應速度快，容易實施，但效率不高，而且也解決不了響應通道未開啟的問題。由于該算法存在讀寫器無響應階段的可能，會造成標簽在一定時間段內無法識別，所以基于時隙隨機分配的ALOHA算法只適用于低成本的RFID系統。本文對比了幀時隙L分別取16、32、64、128、256時的標簽數目與吞吐率的關系，固定幀時隙算法標簽數目與吞吐率的關系如圖3所示。由此可見，當標簽數目和時隙數相等時，系統效率最高。

2 自適應動態時隙ALOHA算法

動態時隙ALOHA算法解決了固定時隙算法時隙長度不變引起的標簽等待問題，采用動態改變時隙個數的方式來提高系統的吞吐率。在多標簽識別的過程中，標簽數量的增加需要更多的時隙個數來完成數據傳送。隨著標簽數量的增加，系統的識別效率急劇下降。本文提出了一種自適應動態時隙的防碰撞算法，根據標簽的數量自適應調整時隙長度，使得在標簽數量較多的情況下仍然可以得到較好的吞吐率。首先，讀寫器初定一個固定的幀長發送命令，標簽根據自身的條件對是否符合要求作出回應；然后，讀寫器對發送數據的標簽進行身份驗證分析后，大致估算已識別和未識別的標簽數；最后，依據未識別的標簽數量，調整相應的幀長和通道數后，開始識別標簽。當未識別標簽數量太多時，數據通道不夠分配，通常使用分組算法將未識別標簽分成多個組，然后根據分組情況自適應調整時隙長度來完成各組標簽的識別。本文采用改進演化算法進行時隙長度自適應調整，根據識別標簽和未識別標簽的個數，調整時隙長度，選取系統吞吐率作為優化函數，采用如下公式調整時隙長度：

其中：fmax為多標簽識別系統最大吞吐率，favg為平均吞吐率，f '為每次選擇的兩個標簽中具有較大吞吐率的選擇方式， f為不同標簽的適應度值，pc1為調整時隙長度演化計算的最大交叉概率，pm1為演化計算最大變異概率。

自適應動態時隙ALOHA算法和動態時隙ALOAH算法的性能比較如圖4所示。可以看出，當標簽數量在0～400之間時，本文改進算法與動態幀時隙算法的吞吐率相當；當標簽數量超過400時，改進算法的吞吐率明顯優于傳統動態時隙算法。

本文改進算法與固定時隙算法的性能比較如圖5所示。可以看出，當標簽數目在0～200之間時，改進算法的吞吐率優于固定時隙算法；當標簽數目在200～300之間時，固定時隙算法的吞吐率優于本文改進算法；當標簽數目在300～400之間時，兩者的吞吐率相當；當標簽數目在400～1 000之間時，本文改進算法的吞吐率優于固定時隙算法。

3 結 語

本文在對ALOHA算法及其改進算法仿真分析的基礎上，給出了固定幀時隙算法時隙長度與吞吐量的關系，提出了一種自適應動態調整幀長的防碰撞算法。仿真結果表明，系統吞吐率最優時，所取的時隙數和標簽數量基本相等；隨著標簽數量的增加，自適應動態調整時隙長度的防碰撞算法吞吐率明顯優于固定時隙算法和傳統動態時隙算法。

參考文獻

[1]王鑫.面向RFID系統防碰撞算法及安全機制研究[D].北京：北京郵電大學，2015.

[2]栗紅果. RFID中標簽防碰撞算法的研究與改進[D].武漢：華中科技大學，2014.

[3]王必勝，張其善.可并行識別的超高頻RFID系統防碰撞性能研究[J].通信學報，2009，30（6）：108-113.

[4]朱云龍，陳瀚寧，申海.生物啟發計算：個體、群體、群落演化模型與方法[M].北京：清華大學出版社，2013.

[5]施衛東.一種改進的RFID標簽防碰撞算法[J].科技通報，2015，31（4）：121-123.

[6]劉道微.基于自適應搜索機制的RFID標簽防碰撞算法[J].金卡工程，2016（11）：34-35.

[7]康維新，吳學文.一種改進的RFID標簽防碰撞算法[J].哈爾濱商業大學學報（自然科學版）， 2014 （6）：677-681.

[8]王佩瑋.無線射頻識別標簽防碰撞算法比較分析[J].物聯網技術， 2017，7（4）：21-24.