[發明專利]一種基于并行樹分裂的標簽防碰撞算法

在審

• 申請號: 202110273558.7
• 申請日: 2021-03-06
• 公開（公告）號: CN112949336A
• 公開（公告）日: 2021-06-11
• 發明（設計）人: 張莉涓;趙楠;袁代數;王玉;范兼睿;宋曉勤;雷磊
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06K7/10
• 分類號: G06K7/10
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種基于并行樹分裂的標簽防碰撞算法，該方法通過利用在前面碰撞時隙中獲取的碰撞信息來直接對后面未識別的標簽直接進行快速分組，從而減少了后面時隙發生碰撞的概率，同時使用緊縮進制避免了快速分裂過程中引入了過多的空閑時隙，通過這兩種機制，提出的方法可以加快標簽的識別速率。MATLAB模擬仿真證明了該方法具有更好的標簽識別能力，相較于同類協議平均識別時間縮短至少16.7％。

技術領域

本發明屬于射頻識別技術領域，特別涉及一種基于并行樹分裂的標簽防碰撞算法。

背景技術

射頻識別(RFID)技術作為物聯網中連接物理世界和信息世界的基礎和關鍵技術，被應用于各行各業中，如醫療、制造業、零售以及旅游業等。在RFID系統中，由于標簽之間共享無線信道，當多個標簽同時向閱讀器回復數據時會引起標簽碰撞問題，降低系統識別效率。因此，設計合理的標簽防碰撞協議具有非常重要的意義。

對于標簽防碰撞協議的研究，目前研究者們主要將RFID標簽碰撞問題的解決方法分為兩大類：一類是基于Aloha算法，如：純Aloha(PA)、時隙Aloha(SA)、幀時隙Aloha(FSA)、動態幀時隙Aloha(DFSA)及其改進算法，這類Aloha算法由于通過隨機數隨機選擇等待一段時間重新回復，部分標簽可能因為一直發生碰撞而導致不能被閱讀器識別，這就是“標簽饑餓”問題；另一類是基于分支樹算法，如查詢樹(QT)、二進制搜索樹(BS)和樹分裂(TS)，分支樹類的標簽防碰撞算法主要通過不同的劃分方式，將碰撞的標簽劃分方式劃分到不同的子集中。

在這些經典算法的基礎上，大量研究者們提出了許多高效的標簽識別算法來減少識別過程中產生碰撞次數，以提升RFID系統的識別性能。基于Aloha的算法也被叫做不確定性算法，它的本質是當標簽發生碰撞時，閱讀器要求發生碰撞的標簽隨機等待一段時間后在重新參與下一次回復。由于隨機選擇延遲，標簽可能會出現“標簽饑餓”問題。目前基于Aloha算法的研究方法主要側重于動態幀時隙Aloha(DFSA)算法，DFSA算法通過動態調整數據幀的方式實現最優的系統效率。例如，復旦大學王俊宇博士提出了一種降低空時隙開銷的RFID標簽防碰撞算法，該算法設置閱讀器在每一幀執行開始前，首先發送detect命令檢測并標記空時隙的位置，從而在之后的的識別過程中能夠避免所標記空時隙的無效操作，進而減少空時隙時間對整個識別時間的影響。基于DFSA算法，chen等提出了一種早調整的防碰撞算法，該算法允許在任意時隙內提前結束當前回合，并且重新選擇一個幀長以開啟新的識別回合。

關于分支樹算法，學者們也提出了大量新算法。當前基于查詢樹(QT)類的標簽防碰撞算法大多采用了基于曼徹斯特編碼的碰撞位檢測方法來提高系統效率。例如碰撞樹(CT)、多前綴查詢樹(DPPS)、碰撞窗口(CWT)和M分組碰撞樹(MCT)等。CT算法使用曼徹斯特編碼碰撞位檢測方法，閱讀器根據標簽的最高碰撞位位置情況將碰撞的標簽劃分到兩個子組，盡管CT極大的減少了空時隙，但它依然會產生許多碰撞時隙，這會增加識別時間。CWT算法使用二進制碰撞樹和啟發式位窗策略，減少了標簽端傳輸的信息位。相比CT，CWT可以減少識別時間和標簽端傳輸的信息位。然而CWT仍然需要多個時隙和查詢命令，而這會浪費大量查詢命令中的頭部信息。DPPS和MCT算法則是通過使用更多的碰撞位信息將沖突的標簽劃分到更多的分組中，它們有更高的時間效率且需要傳輸更少的信息比特。基于BS算法，王雪分別提出了改進的二進制搜索算法和鎖位后退防碰撞算法。改進的二進制搜索算法針對大規模標簽識別系統先增加前綴確定階段，之后在分支中查詢。而鎖位后退算法則是通過尋呼指令鎖定碰撞發生比特位數，通過將其后退到碰撞節點下一個分支內，隨后讀取這個分支中的所有標簽。近幾年，由于樹分裂(TS)算法具有高度的擴展性和可行性，因此大量的學者們也開始研究TS類標簽防碰撞算法。例如，Su等提出了一個基于連續時隙檢測信息的快速分裂(FSA-CSS)算法。該算法使用快速分裂的方法降低了碰撞時隙數，提高了TS類防碰撞算法的識別效率。

發明內容