[發明專利]一種基于碰撞因子的自適應分叉查詢樹多標簽防碰撞方法

在審

• 申請號: 201810201561.6
• 申請日: 2018-03-12
• 公開（公告）號: CN108537079A
• 公開（公告）日: 2018-09-14
• 發明（設計）人: 錢志鴻;初明;王雪;楊冰濤
• 申請（專利權）人: 吉林大學
• 主分類號: G06K7/10
• 分類號: G06K7/10
• 代理公司: 北京慕達星云知識產權代理事務所(特殊普通合伙) 11465
• 代理人: 李冉

1.一種基于碰撞因子的自適應分叉查詢樹多標簽防碰撞方法，其特征在于，具體步驟如下：

S1：閱讀器初始化查詢堆棧，將其置空；

S2：閱讀器發送查詢前綴為ε的查詢指令REQUEST，處于該閱讀器工作范圍內全部標簽響應，標簽并將自身ID信息發送給閱讀器；

S3：閱讀器接收相應的標簽ID信息，利用曼徹斯特編碼的特性，對接收到的信息進行解碼，得到所有的碰撞位，確定發生碰撞的比特位數及具體位置，根據碰撞因子σ選擇自適應分叉規則；

S4：閱讀器判斷堆棧是否為空，若不為空，則從棧頂彈出新的查詢前綴，閱讀器發送查詢前綴為PRE的查詢指令REQUEST，查詢過程轉到S3；若為空，則查詢結束。

2.根據權利要求1所述的一種基于碰撞因子的自適應分叉查詢樹多標簽防碰撞方法，其特征在于，所述S3中針對發生碰撞的比特位數不同分為以下情況：

(1)若沒有標簽響應，則證明閱讀器的工作范圍內沒有任何標簽存在，查詢過程轉到S4；

(2)若經過曼徹斯特解碼后沒有碰撞位產生，則證明閱讀器工作范圍內只存在一個標簽，閱讀器分別發送SELECT和READ-DATA指令，對帶有某一ID的標簽進行讀寫操作，然后發送SILENCE指令，將該標簽置于靜默狀態，查詢過程轉到S4；

(3)若經過曼徹斯特解碼后有碰撞位產生，則計算碰撞因子σ，根據σ的大小估計當前分支存在的待識別標簽的數量，然后按照自適應分叉規則產生新的查詢前綴，依次放入堆棧中等待查詢，轉到S4。

3.根據權利要求1所述的一種基于碰撞因子的自適應分叉查詢樹多標簽防碰撞方法，其特征在于，所述查詢過程中的指令包括：

REQUEST：閱讀器請求指令；查詢前綴為PRE時，閱讀器向存在其工作范圍內的標簽發送這個指令，前綴與PRE相同的標簽響應，并將自身除PRE外余下的ID部分發送給閱讀器；算法初始時，閱讀器發送的指令是查詢前綴為ε的REQUEST；

PREQUEST：前綴預測編碼轉換指令；查詢前綴為PRE，當閱讀器發送這條指令時，前綴與PRE相同的標簽將自身PRE后的兩位進行編碼轉換，并返回4位二進制比特串；

PUSH：讀寫指令；將PRE作為新的查詢前綴壓入堆棧；等待閱讀器指令出棧；

SELECT：選擇指令；通過發送該指令選擇符合某一ID的標簽；

READ-DATA：讀取指令；閱讀器向待識別的標簽發送此指令，讀取標簽ID；

SILENCE：靜默指令；當標簽ID被識別后，閱讀器發送此指令，使標簽處于靜默狀態；

||：連接指令；將前后兩組數據連成一個字符串。

4.根據權利要求2所述的一種基于碰撞因子的自適應分叉查詢樹多標簽防碰撞方法，其特征在于，所述碰撞因子σ定義為在一次查詢過程中，做出響應的標簽所回傳的信息中發生碰撞的比特位數與標簽ID比特長度的比值；在一個RFID系統中，存在一個閱讀器，同時在其工作范圍內有N個待識別標簽，每個標簽的ID長度均為M，令N_col為發生碰撞的比特位數，則全部標簽ID的每一個比特位均不發生碰撞的概率為

存在碰撞比特位的概率為

P(N_col≥1)＝1-(1/2)^N-1；

碰撞因子σ表示為

5.根據權利要求4所述的一種基于碰撞因子的自適應分叉查詢樹多標簽防碰撞方法，其特征在于，所述待識別標簽的識別概率，當查詢深度為1時，所述標簽的識別概率為

P(N，1)＝(1-1/L)^N-1

當查詢深度為K時，所述標簽的識別概率為

P(N,K)＝P(N,1)[1-P(N,1)]^K-1

當0<1-P(N,1)<1，整理得搜索深度的均值為

由此得所需的平均時隙數為

T＝E(N，K)L＝L/{(1-1/L)^N-1}，其中L表示L進制為2、4、6、……。

6.根據權利要求1所述的一種基于碰撞因子的自適應分叉查詢樹多標簽防碰撞方法，其特征在于，所述S3中所述自適應分叉規則包括：

(1)當碰撞因子時，閱讀器發送查詢前綴為PRE的前綴編碼轉換指令REQUEST，前綴與PRE相同的標簽將PRE后的兩位進行二-十進制轉換，分別得到相應的十進制數k，同時符合查詢條件的標簽將發送長度為2^2個比特位，即4位二進制比特串，標簽根據所得到的十進制數k，置比特串的第k位為1，其余位為0，并將其發送給閱讀器；4位二進制比特串從右到左依次是第0位到第3位；閱讀器接收到符合查詢條件的全部標簽返回的信息后，經過曼徹斯特解碼后，得到發生碰撞的具體位置，然后進行十-二進制轉換，得到當前查詢發生碰撞的兩個比特位全部的組合方式，然后分別將其與原有查詢前綴組合，將新產生的查詢前綴依次放入堆棧中，等待查詢；

(2)當碰撞因子置碰撞位為0和1，與原有前綴分別結合，新產生的查詢前綴截止到當前查詢的下一個碰撞位的前一位；將新產生的查詢前綴分別放入堆棧，等待查詢。