[發(fā)明專利]一種基于碰撞因子的自適應(yīng)分叉查詢樹多標(biāo)簽防碰撞方法

在審

• 申請?zhí)枺?/td>: 201810201561.6
• 申請日: 2018-03-12
• 公開（公告）號: CN108537079A
• 公開（公告）日: 2018-09-14
• 發(fā)明（設(shè)計）人: 錢志鴻;初明;王雪;楊冰濤
• 申請（專利權(quán)）人: 吉林大學(xué)
• 主分類號: G06K7/10
• 分類號: G06K7/10
• 代理公司: 北京慕達星云知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 11465
• 代理人: 李冉

本發(fā)明公開了一種基于碰撞因子的自適應(yīng)分叉查詢樹多標(biāo)簽防碰撞方法，首先，在每一次查詢過程中，通過計算碰撞因子來對當(dāng)前查詢樹的一個分支里標(biāo)簽數(shù)量進行估計；然后，依據(jù)所估計的標(biāo)簽數(shù)量，選擇合適的分叉規(guī)則，對查詢樹的節(jié)點進行自適應(yīng)的分叉。若標(biāo)簽數(shù)量較多，則采用碰撞前綴編碼轉(zhuǎn)換的無空閑時隙的四叉樹搜索方式進行查詢，反之，則采用二叉樹搜索方式進行查詢。本發(fā)明提供了一種基于碰撞因子的自適應(yīng)分叉查詢樹多標(biāo)簽防碰撞方法，依據(jù)每次查詢中的碰撞因子的大小自適應(yīng)選擇分叉機制進行下一步的查詢，完全避免了空閑時隙的產(chǎn)生，同時也減少了總的查詢時隙數(shù)，提高了系統(tǒng)吞吐量。

技術(shù)領(lǐng)域

本發(fā)明涉及通信技術(shù)領(lǐng)域，更具體的說是涉及一種基于碰撞因子的自適應(yīng)分叉查詢樹多標(biāo)簽防碰撞方法。

背景技術(shù)

隨著信息技術(shù)的高速發(fā)展，人們的生活也在不斷地被改變著，物聯(lián)網(wǎng)的興起堪稱信息領(lǐng)域的一次新革命。在物聯(lián)網(wǎng)中，其通信終端可以是我們身邊的任何一個物體，能夠?qū)崿F(xiàn)物物互聯(lián)。而射頻識別技術(shù)作為物聯(lián)網(wǎng)的關(guān)鍵技術(shù)之一，發(fā)揮著不可替代的作用，其所具有的無接觸式自動識別、低成本和低功耗等優(yōu)點，在國內(nèi)外具有著廣泛的應(yīng)用。但同時，RFID技術(shù)也面臨著很多的挑戰(zhàn)，比如在一個RFID系統(tǒng)中，多個標(biāo)簽存在于同一個閱讀器工作范圍內(nèi)，當(dāng)它們同時向閱讀器傳輸數(shù)據(jù)時，便會發(fā)生標(biāo)簽碰撞。尤其是未來物聯(lián)網(wǎng)中的RFID系統(tǒng)必然會存在海量標(biāo)簽，碰撞問題會變得愈加嚴(yán)重，因此，提出有效的防碰撞策略對提高RFID系統(tǒng)的性能至關(guān)重要。

關(guān)于RFID系統(tǒng)中多標(biāo)簽防碰撞算法主要分為兩類，分別為：基于ALOHA的不確定性防碰撞算法和基于二進制樹的確定性防碰撞算法。但由于基于ALOHA的防碰撞算法存在標(biāo)簽饑餓的問題，而基于二進制數(shù)的確定性算法可以對標(biāo)簽進行逐一識別，有效的避免了標(biāo)簽饑餓現(xiàn)象的發(fā)生，但同時也造成了識別總時隙數(shù)量的增多，因而如何減少標(biāo)簽識別的總時隙數(shù)，提高系統(tǒng)的吞吐量是首要解決的問題。對此，許多相關(guān)領(lǐng)域的學(xué)者對該問題進行了研究與改進，提出了許多優(yōu)秀的基于樹的防碰撞協(xié)議。查詢樹算法(Query Tree，QT)，是最經(jīng)典的基于樹的防碰撞算法，首次引入堆棧，用以存儲新生成的查詢前綴，是一種標(biāo)簽無記憶算法，許多優(yōu)秀的協(xié)議都是基于其來改進的，它采用逐位識別，直至堆棧為空；碰撞樹算法(Collision Tree，CT)是在QT算法的基礎(chǔ)上改進的，在每次查詢中，只關(guān)注首碰撞位，將原有查詢前綴分別加0和1，然后將它們壓入堆棧，該算法相比于QT算法，可以減少總查詢時隙的數(shù)量，提高系統(tǒng)吞吐量；自適應(yīng)多叉樹防碰撞算法(Adaptive Anti-collisionAlgorithm Based on Multi-tree，AMS)，引入了碰撞因子的概念，當(dāng)碰撞因子大于或等于0.75時，采用四叉查詢樹的方法進行查詢，當(dāng)碰撞因子小于0.75時，采用二叉查詢樹的方法進行查詢，在一定程度上提高了系統(tǒng)的吞吐量，但同時也存在很多空閑時隙，且隨著標(biāo)簽數(shù)量的增多，系統(tǒng)吞吐量并不能保持很好的穩(wěn)定性；自適應(yīng)四叉修剪查詢樹算法(Adaptive4-ary Pruning Query Tree,A4PQT)，在每次查詢過程中，僅關(guān)注最高碰撞位及其后一個比特位，根據(jù)后一個比特位的特征，對四叉查詢樹進行有效的修剪，從而減少部分空閑時隙，但當(dāng)兩個標(biāo)簽ID為00和11時，閱讀器經(jīng)曼徹斯特解碼得到XX，仍然要產(chǎn)生兩個空閑時隙；位仲裁樹協(xié)議(Bit Arbitration Tree，BAT)，首次提出了兩個規(guī)則，分別為基于特征值的分組規(guī)則和碰撞比特位規(guī)則，進一步減少了空閑時隙的數(shù)量，在一定程度上提高了系統(tǒng)吞吐量，但同時由于分組查詢指令的發(fā)送，也引入了許多碰撞時隙。

因此，如何提供一種依據(jù)每次查詢中的碰撞因子的大小自適應(yīng)選擇分叉機制進行下一步的查詢，完全避免空閑時隙的產(chǎn)生，并可減少總的查詢時隙數(shù)，提高系統(tǒng)吞吐量的基于碰撞因子的自適應(yīng)分叉查詢樹多標(biāo)簽防碰撞方法是本領(lǐng)域技術(shù)人員亟需解決的問題。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明提供了一種基于碰撞因子的自適應(yīng)分叉查詢樹多標(biāo)簽防碰撞方法，依據(jù)每次查詢中的碰撞因子的大小自適應(yīng)選擇分叉機制進行下一步的查詢，完全避免了空閑時隙的產(chǎn)生，同時也減少了總的查詢時隙數(shù)，提高了系統(tǒng)吞吐量。