引 言

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

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

1.1 ALOHA算法

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

交換的數(shù)據(jù)包量在 G=0.4 時達到最大，仿真結(jié)果如圖 2 所示。

如果 RFID 系統(tǒng)吞吐率用平均吞吐率 S 表示，其值等于1 時表示無數(shù)據(jù)包發(fā)生碰撞，其值等于 0 時表示沒有數(shù)據(jù)包傳輸成功，平均吞吐率 S 為：

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

1.2 時隙ALOHA算法

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

1.3 幀時隙ALOHA算法

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

圖 3 固定幀時隙算法標簽數(shù)目和吞吐率關系

2 自適應動態(tài)時隙 ALOHA算法

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

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

自適應動態(tài)時隙 ALOHA 算法和動態(tài)時隙 ALOAH 算法的性能比較如圖 4 所示?？梢钥闯?，當標簽數(shù)量在 0 ～400 之間時，本文改進算法與動態(tài)幀時隙算法的吞吐率相當；當標簽數(shù)量超過 400 時，改進算法的吞吐率明顯優(yōu)于傳統(tǒng)動態(tài)時隙算法。

圖 4 本文改進算法和動態(tài)時隙算法吞吐率比較

本文改進算法與固定時隙算法的性能比較如圖 5 所示?？梢钥闯?，當標簽數(shù)目在 0～200之間時，改進算法的吞吐率優(yōu)于固定時隙算法；當標簽數(shù)目在 200～300之間時，固定時隙算法的吞吐率優(yōu)于本文改進算法；當標簽數(shù)目在 300～400之間時，兩者的吞吐率相當；當標簽數(shù)目在 400 ～1 000 之間時， 本文改進算法的吞吐率優(yōu)于固定時隙算法。

圖 5 固定時隙算法和本文改進算法吞吐率比較

3 結(jié) 語

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