一種新型的RFID的防碰撞算法

于洪濤，王祖良，王少飛，曹闖樂，馬可欣

（西京學院，陜西 西安 710123）

0 引 言

在現代科技不斷快速發展下，自動識別系統越來越受到人們的青睞。射頻識別（Radio Frequency Identification,RFID）是一種近距離無線電通信技術，具有成本低廉、傳輸速度快且可以對多個目標進行響應識別的特點，其作為一種自動識別技術已被廣泛應用在商品識別和數據采集等各個領域[1]。因此，對RFID的防碰撞算法的研究對提高系統的信道利用率具有重要意義。RFID系統由閱讀器、射頻標簽和天線組成。其原理是：閱讀器首先通過自身攜帶或外置的天線源源不斷地發送無線電信號，當標簽放進屬于天線的作業范圍之內時，它通過電感耦合和電磁反向散射耦合產生能量，使標簽獲得能量傳遞本身數據信息，閱讀器攜帶的數據編碼等信息通過內置天線發送出去[2]，接收天線接收標簽發送的載波信號對其進行解調和解碼，然后將其發送回計算機系統進行相關處理[3]。標簽可以說是RFID系統中的重要組成部分之一，原因是它內部存儲著自身的數據信息，但是，在數據識別和傳輸的過程中，它受到很多方面的干擾，導致數據識別和傳輸的質量和效率較低。一般來說，造成這種現象的主要原因是，各種閱讀器和標簽中存在的外部干擾因素是同時存在的，因此很容易在數據信息傳輸通道中發生沖突，導致質量和效率低下。為了解決這個問題，本文提出了防沖突算法。

根據標簽的響應方式，防沖突算法通常分為不確定性算法和確定性算法兩種。

在不確定性算法中主要為ALOHA算法。ALOHA算法的機制是標簽源源不斷地發送自身數據信息給閱讀器，當發生沖突時，閱讀器會下達命令阻止標簽發送信號，此時，標簽進入一個“待命”時間段，這個時間段也是隨機的，“待命”時間結束，標簽繼續發送信號給閱讀器。

確定性算法有二進制樹算法，其機制是閱讀器首先設置限制條件，只有滿足條件的標簽才可以發送信號并被閱讀器識別。譬如有00和01兩個標簽，閱讀器首先發送“0”比特串，然后將比特串“1”放進堆棧中，因為兩個標簽的首位都是0，所以同時響應閱讀器從而產生碰撞。閱讀器繼續發送“00”比特串，并將“01”壓入棧中，此時標簽ID為“00”響應閱讀器的請求，標簽識別成功，接下來堆棧中的“01”標簽被彈出，其作為請求比特串從而被成功識別。

1 ALOHA算法

1.1 純ALOHA算法

當電子標簽被放置到閱讀器作業范圍之中時，會將自身攜帶的數據信息發送給閱讀器，但是此時若有其他標簽也在向閱讀器發送信號就會發生沖突，造成碰撞。在純ALOHA算法中發生碰撞之后，閱讀器會發出命令讓標簽停止發送信號給自身，進入一個不確定的“待命”時間段，標簽只有在過了這個時間段之后才可以重新發送數據信息給閱讀器，這個時間段的時間范圍是不固定的，所以標簽再次發送信號的時間也是隨機的，這樣就大大減小了碰撞的概率。

1.2 時隙ALOHA算法

時隙ALOHA算法與純ALOHA算法不同的是，它將時間段分為多個離散可等幀長也可不等幀長的時隙[4]，這些時隙由閱讀器分配，且每個標簽都必須在所分配時隙的開始處傳遞自己的信息。因此，時隙ALOHA算法是一種隨機查詢驅動的TDMA防沖突算法。因為標簽只能在閱讀器分配的時隙中傳輸數據，即要么標簽成功識別，要么發生碰撞，與純ALOHA算法相比，減小了碰撞周期，標簽被識別的成功率得到了顯著增加。但是，時隙ALOHA算法在標簽發生沖突之后，仍會通過隨機時間延遲進行分發和重新傳輸數據。

1.3 動態幀時隙ALOHA算法

傳統時隙ALOHA算法的幀長是固定的，一幀可以包含多個時隙，也就是說其時隙數也是確定的。那么即使當有大量的標簽待被閱讀器識別時，其時隙數也不會發生改變。這樣就存在一個問題：當標簽的基數很大時，若時隙數設置的很小就可能會造成碰撞；若標簽為數不多，時隙數很大，又會造成時隙的多余，從而造成浪費[5]。動態幀時隙ALOHA算法成功解決了這個問題，它可以根據標簽基數動態更改一個幀內的時隙數，當標簽基數很大時，可以通過增加時隙數避免碰撞的發生。其具體算法推理如下：

假設F是幀長，N是系統要識別的全部標簽數量，OVSF碼長設為d，則在單個時隙中可以在d個OVSF碼中檢測到n個標簽的概率為：

從式（8）可以看出，當設置的幀長與標簽總數近似相等時，系統的信道利用率最高[6]，此時的吞吐量最大值為：

動態幀時隙ALOHA算法較時隙ALOHA算法的優點是：當標簽基數很大時，仍能使信道利用率維持在36%，時隙ALOHA算法因其時隙數固定，所以當標簽數量增大時，其發生碰撞的可能性會增加，信道利用率也會大幅度下降。

2 改進的動態幀時隙ALOHA算法

時隙ALOHA算法是一種隨機查詢驅動的TDMA防沖突算法，本文在運用TDMA技術的基礎上，結合碼分多址（CDMA）技術提出了一種新的幀時隙ALOHA算法，主要推導如下：

由式（3）可得系統的吞吐量，將d設為2，即OVSF碼長為2時，吞吐量可表示為：

對N求導，令式子為零，可得：

當標簽數量趨近于無窮大時，系統吞吐量為：

由式（12）可知，新型幀時隙ALOHA算法的吞吐率達到了將近84%，比原來的幀時隙ALOHA算法提升近2倍，可見這種算法能夠更好地提高系統的信道利用率。

3 實驗結果及分析

因純ALOHA算法和時隙ALOHA算法在當網絡負載即標簽基數很大時，其吞吐量基本為零，所以對這4種算法兩兩進行分析。在圖1中，可以看到純ALOHA算法的吞吐量在16%左右，時隙ALOHA算法吞吐量為36%，吞吐量提高了近一倍。但這兩種算法在標簽基數很大時，吞吐量均急劇減小直至為零。從圖2的實驗結果可看出：動態幀時隙ALOHA算法吞吐量在標簽基數很大時，依然可以維持36%的吞吐量，這是因為較幀時隙ALOHA算法，動態幀時隙ALOHA算法根據標簽的總量實時動態修正更改幀長[7]，這樣就大大減小了碰撞的概率。所以即使當標簽的基數很大時，動態幀時隙算法依然可以保證有足夠的時隙供標簽選擇，因此可以維持吞吐量保持穩定。新型動態幀時隙ALOHA算法在幀時隙算法的基礎上進一步做了修改，將CDMA技術與TDMA技術相結合，從圖2可以看出，吞吐量保持在84%左右，與幀時隙ALOHA算法相比提高了近2.3倍。這是因為新型動態幀時隙ALOHA算法在將時間分為離散的多個時隙后，又結合了CDMA，也就是在同一個時隙中可以識別兩個標簽[8]，擺脫了幀時隙ALOHA算法單個時隙只能識別單個標簽的束縛[9]，大大減小了碰撞的概率，從而提高了系統的信道利用率。

圖1 純ALOHA算法和時隙ALOHA算法吞吐量仿真

圖2 動態幀時隙和新型動態幀時隙ALOHA算法吞吐量仿真

4 結 語

本文在幀時隙ALOHA防碰撞算法的基礎上提出了一種新的基于CDMA和TDMA技術相結合的防碰撞算法，該算法的吞吐量較改進之前的算法提高了近2.3倍，提高了系統的信道利用率[10]。實驗結果證明，如果增加碼長，系統的吞吐量可以不斷增加，但是由于考慮到資源浪費和研發費用問題，不宜增加過多，要根據具體的標簽基數選擇碼長，做到識別效率高且又不會浪費資源。