公安巡檢數據采集終端中防碰撞算法的研究與應用

賈巖巖 陸華 桂林大

【摘要】 主要闡述了RFID系統中電子標簽的防碰撞問題，分析了常用的防碰撞技術ALOHA算法。結合公安巡檢數據采集終端的實際情況，給出了改進型ALOHA算法的實現過程，該算法簡單有效，實用性強，提高了系統數據的吞吐率。

【關鍵詞】 RFID標簽 防碰撞 ALOHA算法 改進型一、引言

當前社會發展與經濟建設進入全面提速階段，國民的生活水平得到進一步的提高，社會公共安全越來越收到廣泛的關注，尤其是近幾年來我國發生的暴力恐怖事件， 因此提高對巡警和巡防隊員的有效管理，對于降低犯罪，保障公共安全越來越重要。

無線射頻識別技術[1] （Radio Frequency Identification， RFID），或稱射頻識別技術。作為一種快速、準確、實時采集與處理信息的高新技術[2]，RFID被列為本世紀十大重要技術之一[3]，其在公安巡檢領域也得到了廣泛的應用。無線電技術中，多路存取的問題是眾所周知的。如果有多個RFID標簽接收到電磁波并同時發送反饋信息，則標簽閱讀器接收到的信號就會相互干擾，發生數據碰撞[4]。因此，如何解決數據碰撞問題成為了RFID系統的關鍵技術之一[5]。

目前，應用于射頻識別系統中的防碰撞技術主要有空分多址（SDMA）、頻分多址（FDMA）、碼分多址（CDMA）和時分多址（TDMA）等。由于時分多址法的成本較低，易于實現，所以是目前最為常用的防碰撞技術。本文主要描述基于TDMA的RFID ALOHA隨機延時防碰撞算法。

二、ALOHA防碰撞算法

ALOHA算法是一種不確定性算法，其檢測時間和延遲時間都是隨機分布的，主要應用于主動式標簽，包括純ALOHA算法、時隙ALOHA算法和自適應時隙ALOHA算法。它的基本原理為，當信息源標簽發送的數據包發生碰撞時，標簽就會產生一個隨機延時，然后再次嘗試數據包的發送，重復此操作，直到發送成功。

2.1純ALOHA算法

純ALOHA算法是一種最簡單最基本的防碰撞算法，它不具有碰撞檢測及恢復機制，只是在概率上保證標簽發送的數據被閱讀器準確接收。它采用的是“標簽先發言”（TTF， Tag Talk First）方式。即當標簽處于閱讀器的作用范圍時，標簽就會主動發送自身的信息數據包，當多個標簽的數據同時到達閱讀器就會造成數據幀的破壞，各個標簽將隨機延長一段時間后進行重新發送。標簽1產生了數據并立即發送，接著標簽3也開始發送數據，這樣標簽1和標簽3就發生了部分碰撞，而如果兩個標簽恰巧在同一時刻發送數據，就將發送完全碰撞。

該算法的優點是，無需同步，各標簽發送時間完全隨機，比較容易實現，尤其是當標簽較少時能夠進行很好的工作，但缺點是延時時間選擇困難，如果設置過大，則閱讀器的識別時間就會變長，若設置過小，系統發生重復碰撞的幾率就會大增，需要退避的次數也會過多。

性能分析：公共信道上在單位時間T內平均發送的數據幀數G和傳輸通路的吞吐率S的計算公式見式（1）和式（2）。

（1）

（2）

式中，n為系統中標簽的數量，rn是T時間內由標簽n發送的數據幀數。

由以上公式可以得出S的極大值，即當G=0.5時，吞吐率S的最大值Smax=1/2e（約為0.184），說明純ALOHA的最大信道利用率是18.4%。

2.2時隙ALOHA算法

時隙ALOHA算法和純ALOHA算法的區別在于，將時間分割成了一個個等長離散的時隙，時隙Tslot等于或者略大于一個數據包的長度T0，并且只有當時隙開始時每個標簽才被允許發送數據幀，這樣一來，一旦發生了數據碰撞，就是完全碰撞，不會發生部分碰撞的情況，見圖2。

時隙ALOHA算法中，S與G的關系為：

S=Ge-G

2.3動態時隙ALOHA算法

在時隙ALOHA算法中，時間軸被劃分的時隙數N是固定不變的，且容易實現，但是在公安巡檢數據采集終端的實際應用環境中，進入閱讀器作用范圍的電子標簽的數量是動態改變的，閱讀器不能主動根據電子標簽的數量調整時隙數的大小，這將導致公安巡檢數據采集終端性能不穩，甚至造成電子標簽的信息漏讀。動態時隙ALOHA算法能夠根據標簽發生碰撞的數量動態地改變時隙數N的大小。當時隙數小于標簽數量時，閱讀器根據發生碰撞的標簽數適當增加時隙數，反之，當時隙數大于標簽數量時，閱讀器能適當地減少數據幀的時隙數。動態ALOHA算法能保證數據幀的時隙數與標簽數量基本一致，使系統效率達到最佳。

2.4 改進型ALOHA算法

RFID系統中的標簽只能通過接收閱讀器的指令來判斷是否發生了數據碰撞，導致系統信道利用率很低。若標簽能夠自主判斷是否會發生數據碰撞，再選擇發送數據，就可以大大降低數據發生碰撞的概率，進而使信道利用率增加。改進型ALOHA算法是在時隙ALOHA算法的基礎上增加了數據碰撞避免機制[6]，各標簽首先進行標簽同步，當信道被其他標簽占用時繼續監聽，直到信道空閑將自身數據立即發送出去，若發生數據碰撞，則隨機延遲一段時隙后重新監聽。由于改進型ALOHA算法采用了實時信道監聽，這就要求標簽具有主動發送信息的能力，所以改進型ALOHA算法僅適用于有源電子標簽的防碰撞。公安巡檢數據采集終端采用的正是有源電子標簽，有源電子標簽增加了閱讀器的讀取距離，不僅縮短了閱讀器的讀取時間，而且提高了讀取效率[7]。

三、公安巡檢數據采集終端中防碰撞算法的實現

公安巡檢數據采集終端中閱讀器與標簽通信運用握手協議進行數據交換[8]，標簽進入閱讀器搜索范圍時被激活，當標簽監聽到信道空閑時發送自身數據，發送成功后進行滅活處理。

具體實現步驟如下：

（1）閱讀器發送廣播信息幀；

（2）處于閱讀器作用范圍內的所有標簽將接收廣播信息幀，未被識別的標簽（即處于休眠狀態）自主喚醒，同時監聽信道狀態，等待發送自身數據；

（3）當標簽監聽到信道空閑時，將自身數據發送出去，并繼續偵聽閱讀器返回的數據幀；

（4）若標簽成功占用了信道，閱讀器接收后會返回應答，標簽收到應答后進入休眠模式（即滅活）。若未能成功占用信道，標簽即隨機延時一段時隙，繼續監聽信道等待重新發送。

（5）閱讀器再次發送廣播信息進行下一次通信。

四、結語

改進的ALOHA數據防碰撞算法，即在標簽發送數據之前先監聽信道是否被占用，再決定是否發送數據。仿真結果表明：改進型ALOHA算法優于動態ALOHA和時隙ALOHA算法，最大數據吞吐率達到53%。在公安巡檢數據采集終端的實際應用中，改進型ALOHA算法完全能夠滿足要求，且易于實現，成本較低，達到了比較好的效果。

陳業龍（1973-），男，本科，工程師，主要研究方向：通信技術及物聯網應用開發

賈巖巖（1987-），通信作者，男，碩士研究生，助理工程師，主要研究方向：無線通信系統中的信號處理技術

陸華（1985-），男，碩士研究生，助理工程師，主要研究方向：信號處理和傳輸技術