[發明專利]一種基于布隆過濾器的未知射頻標簽檢測方法

有效

• 申請號: 201410103177.4
• 申請日: 2014-03-19
• 公開（公告）號: CN103870781B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 李克秋;劉秀龍;齊恒;謝鑫;劉春龍;曲雯毓
• 申請（專利權）人: 大連理工大學
• 主分類號: G06K7/00
• 分類號: G06K7/00
• 代理公司: 大連理工大學專利中心21200
• 代理人: 李寶元,梅洪玉

技術領域

本發明涉及一種基于布隆過濾器的未知射頻標簽檢測方法，屬于無線通信技術領域。

背景技術

隨著現代科學技術的發展，射頻識別（RFID,Radio?Frequency?Identification）技術被越來越廣泛的應用于物聯網、倉庫管理、物體跟蹤等多個領域。相比傳統的條形碼技術，射頻識別技術具備很多優良特性，包括：遠距離讀寫，具備一定計算能力，更大的數據存儲空間，能夠為管理者帶來更多的便利。在射頻識別技術領域中，標簽數量估計、標簽定位、丟失標簽的識別等問題被廣泛研究。

一個RFID系統通常包括一個后臺服務器（back-end），一個或多個閱讀器（reader），和數量龐大的射頻標簽（tag）。射頻標簽通常被附著在被監控的貨物或商品上，并且有一個小的存儲芯片來存儲一個全球統一的序列號（ID）以及一些其他信息，如：商品價格、保質期和個人信息等。標簽通常被分為兩種：有源標簽和無源標簽。有源標簽自身具備電池供電；而無源標簽本身不具備電池，只能從閱讀器輻射的電磁場中獲取電能工作。在物流管理或者倉庫監控中，管理人員的疏忽大意有可能導致貨物被錯誤地擺放在其他位置。這有可能引發嚴重的后果，比如：冷凍食品如果被錯誤地放置在了沒有制冷設備的區域，就會融化變質，從而造成經濟損失；另外，有毒物質和食品不能夠放在一起，相互之間容易發生反應的易燃易爆物也不能夠放置在一起。可見，如何快速發現、找到這些被錯誤擺放的貨物是一個有意義的問題。在一個放置了成千上萬貨物的倉庫中，人工檢查浪費人力、時間，且準確度不高。RFID技術可以被用來解決錯位貨物的識別問題。具體來講，每個貨物都配備了一個射頻標簽，位置正確的貨物上的標簽序列號存儲在該區域閱讀器所連接的后臺服務器上。而錯誤擺放的貨物的標簽序列號是不會存儲在后臺中的，因此被稱為未知標簽。在RFID研究的初期，大量的研究工作集中在標簽識別（tag?identification）問題，即識別所有的射頻標簽的序列號（ID）。實際上，采用標簽識別算法可以解決未知標簽識別問題。具體來講，閱讀器搜集到所有標簽的序列號以后，跟數據庫中的已知標簽序列號對比，即可知道哪些是未知標簽。但該方法收集了大量的已知標簽的序列號，而這些序列號已經存儲在數據庫中了，因此浪費了大量的時間。如何把已知標簽靜默，然后單獨收集未知標簽成為了提升效率的關鍵。現有的技術提供了一種識別未知標簽的方法，旨在找到所有的未知標簽。可是在現實應用中，未知標簽的出現具有兩個特性：（1）隨機性，即我們無法預測未知標簽何時會出現；（2）稀疏性，即未知標簽只是偶爾出現。因此現有技術提出的方法大多數時間處于空跑狀態，即無法找到未知標簽，卻浪費了大量的時間和能量。

發明內容

為了克服上述的不足，本發明提供了一種基于布隆過濾器的未知射頻標簽檢測方法。

本發明要解決的技術問題是未知標簽檢測，旨在快速判斷在射頻識別系統中是否存在未知標簽。我們把該問題進一步定義為：假設系統中有N個已知標簽，當有M個或更多未知標簽出現時，閱讀器要至少以概率α檢測到有未知標簽出現。

一種基于布隆過濾器的未知射頻標簽檢測方法，包括如下步驟：

（1）使用采樣方法檢測系統中的部分標簽

閱讀器廣播一個二元請求<R₁,ⅹ>；每個射頻標簽接收到該二元請求后使用參數R₁來計算表達式H(ID,R₁)mod?Y；如果計算結果小于ⅹ，那么該標簽成為樣本標簽，將參與后續的檢測步驟；否則將不參與后續步驟；其中，在二元請求<R₁,ⅹ>中，R₁為隨機數，ⅹ=p×Y，p是抽樣概率，Y是在制造標簽時燒在芯片中的常數；

（2）利用布隆過濾器中每位的狀態來檢測未知標簽

閱讀器把步驟（1）中產生的樣本標簽的ID映射到布隆過濾器上，用K個獨立同分布的哈希函數將一個樣本標簽的ID映射到布隆過濾器的f個位置；K代表生成布隆過濾器時使用哈希函數的個數；f代表布隆過濾器的長度；

閱讀器將構造的布隆過濾器以及所采用的參數廣播給所有的樣本標簽，樣本標簽收到該布隆過濾器后，每個樣本標簽用同樣的哈希函數和參數計算并檢查各自的代表位；對于一個標簽，如果K個代表位均為1，即通過了本次檢測，并被認為是一個已知標簽；否則，該標簽為未知標簽。