[發(fā)明專利]一種基于搜索樹的雙時隙RFID防碰撞算法

在審

• 申請?zhí)枺?/td>: 201810191092.4
• 申請日: 2018-03-08
• 公開（公告）號: CN108416241A
• 公開（公告）日: 2018-08-17
• 發(fā)明（設計）人: 莫磊;唐斌
• 申請（專利權）人: 成都航空職業(yè)技術學院
• 主分類號: G06K7/10
• 分類號: G06K7/10
• 代理公司: 成都中亞專利代理有限公司 51126
• 代理人: 王崗

本發(fā)明公開了一種基于搜索樹的雙時隙RFID防碰撞算法；本算法基于搜索樹的雙時隙防碰撞算法。該算法利用閱讀器堆棧形成進一步搜索命令；響應標簽分為兩個子集，并分別在兩個時隙發(fā)送數(shù)據(jù)信息，一次搜索最多可識別4個標簽。理論分析和仿真結果表明：基于搜索樹的雙時隙防碰撞算法綜合了ALOHA算法和搜索樹算法的優(yōu)點，減少了搜索次數(shù)和識別時間，提高了RFID系統(tǒng)的整體性能。因此改進之后，引入了ALOHA算法中的時隙思想，綜合二者的優(yōu)點，減少了閱讀器和標簽間的數(shù)據(jù)通信量，減少了搜索次數(shù)，提高了搜索效率。

技術領域

本發(fā)明涉及RFID防碰撞算法相關領域，具體講是一種基于搜索樹的雙時隙RFID防碰撞算法。

背景技術

RFID技術即無線射頻識別技術，通常由閱讀器、標簽和數(shù)據(jù)系統(tǒng)組成，由于其非接觸、自動識別、穿透性強等優(yōu)點，被廣泛應用于醫(yī)療、交通、物流、電力等各個行業(yè)。閱讀器作用范圍內(nèi)通常有多個標簽，由于所有標簽使用同一信道，當多個標簽同時向閱讀器發(fā)送數(shù)據(jù)時，就會相互干擾，造成閱讀器無法讀取數(shù)據(jù)，這就是RFID的碰撞問題。

現(xiàn)有RFID防碰撞算法

(1)純ALOHA算法：純ALOHA算法是一種比較簡單的隨機時分多址防碰撞算法，標簽在一個周期性的循環(huán)中不斷向閱讀器發(fā)送數(shù)據(jù)，標簽發(fā)送數(shù)據(jù)的時間只是重復時間的一小部分，其發(fā)送數(shù)據(jù)的時間是隨機的，當一個標簽發(fā)送數(shù)據(jù)時，如果另一個標簽也在發(fā)送數(shù)據(jù)，就會發(fā)生碰撞，純ALOHA算法在發(fā)送數(shù)據(jù)的過程中碰撞的概率比較大。

幀時隙ALOHA算法是在純ALOHA算法基礎上的改進算法，在時間上分成多個離散時隙，把多個時隙組成一幀，標簽在每個幀內(nèi)隨機選擇一個時隙發(fā)送數(shù)據(jù)，幀時隙ALOHA算法避免了純ALOHA算法部分數(shù)據(jù)碰撞的情況，吞吐率提高了一倍。

在幀時隙ALOHA算法中，幀的長度是固定的，當標簽數(shù)量遠大于幀長度時，會導致碰撞時隙過多，當標簽數(shù)量遠小于幀長度時，會導致空閑時隙過多，動態(tài)幀時隙ALOHA算法對此作了改進，在標簽的搜索過程中，動態(tài)調整幀的長度，以提高搜索效率。

ALOHA算法是一種概率算法，存在空閑時隙，識別效率不高，在不知道標簽數(shù)量情況下，不能保證所有標簽都能夠被有效識別。

(2)二進制搜索防碰撞算法：

(2.1)基本二進制搜索算法：基本二進制搜索算法需要準確的檢測碰撞位，這需要對標簽數(shù)據(jù)進行特殊的編碼，通常是通過曼徹斯特編碼來實現(xiàn)，同時要確保多個標簽同步向閱讀器發(fā)送數(shù)據(jù)。在基本二進制搜索算法中，閱讀器根據(jù)接收數(shù)據(jù)的碰撞位位置來確定發(fā)送命令序列號，各標簽把自身的ID號和閱讀器發(fā)送的命令序列號進行比較，如果小于或等于序列號，就發(fā)送ID數(shù)據(jù)給閱讀器，否則就不響應閱讀器命令，當識別出一個標簽后，又重頭開始搜索,直到識別出所有標簽。

假設有N個標簽，基本二進制搜索算法識別一個標簽的搜索次數(shù)為

識別所有標簽的搜索次數(shù)為：

(2.2)動態(tài)二進制搜索算法：基本二進制搜索算法在搜索過程中，閱讀器的發(fā)送命令參數(shù)中，最高碰撞位以后的比特位都置‘1’，這部分信息對標簽來說是已知的；標簽總是返回完整的序列號，最高碰撞位以前的比特位對于閱讀器來說也是已知的，標簽和閱讀器都重復發(fā)送了多余信息，動態(tài)二進制對此作了改進，閱讀器只發(fā)送最高碰撞位及以前的比特位，標簽只發(fā)送最高碰撞位以后的比特位，這樣，傳輸?shù)臄?shù)據(jù)量減少了一半，在ISO/IEC1443A標準中，動態(tài)二進制搜索算法為推薦的防碰撞算法。動態(tài)二進制搜索算法的搜索次數(shù)與基本二進制搜索算法相同。