RFID中解決無線信道爭用問題的防碰撞算法研究
加入技術交流群
3 查詢樹算法(QT)
“QT(Query Tree)查詢樹算法基于標簽ID號來分裂一組發生碰撞的標簽。”在每一輪傳輸中，讀寫器向標簽發送一個比特串的查詢信息。讀寫器的一系列查詢比特串記錄在隊列Q中。初始化隊列Q為兩個1位比特比特串0和1，讀寫器從Q中取出一個比特串，用以查詢信息。若此查詢信息與某標簽的序列號ID的前綴信息相同，則此標簽響應讀寫器的命令，傳輸自己的ID給讀寫器。如果讀寫器發送的查詢比特串X1X2 X3…Xt(Xi∈{0，1}，t小于標簽序列號ID的長度)，有多個標簽同時響應讀寫器的查詢信息，即發生了碰撞，則在此查詢比特串后面增加一位，將X1X2X3…Xt0和X1X2X3…Xt1壓入隊列Q中。讀寫器下次將分別用這兩個比特串作為查詢信息，前面發生碰撞的標簽將分為兩個部分。一部分將響應查詢比特串X1X2X3…Xt0，另一部分將響應查詢比特串X1X2X3…Xt1。依此方法不斷地增加比特串位數，直至收到響應但沒有碰撞情況發生或無響應的情況，這樣讀寫器就能夠識別出所有的標簽。本文引用地址：http://www.j9360.com/article/153511.htm
查詢樹算法用隊列Q存儲查詢信息，標簽不必存儲序列號ID以外的無關信息，這樣，標簽就具有更簡單的功能，可降低標簽成本，因此，QT算法是無記憶的算法。圖2所示是QT算法的一個示意圖。系統中的標簽ID號為0010、1110和1101。
4 改進型算法
4．1 改進型算法思想
讀寫器引入一個堆棧S來存儲二又樹發生碰撞時右子樹節點信息，一個隊列Q來存儲無碰撞發生時的查詢前綴。
設標簽序列號ID是長為L的二進制數，讀寫器查詢前綴是長度不大于L的二進制數。那么，讀寫器發送查詢前綴，使其作用范圍內標簽將自己的序列號ID與查詢前綴相比較。如果查詢前綴與標簽自最高位開始的部分比特串相同，則標簽回復序列號ID剩余的部分比特串給讀寫器。初始時，二叉樹只有根節點，讀寫器的堆棧為空，隊列Q為空。
4．2 改進型算法流程
第一步，由讀寫器在初始時發送查詢前綴(1位的二進制數“0”)，此時有以下幾種情況：
(1)如果只有一個標簽響應，即無碰撞發生，此時可為根節點添加左子節點(表示二進制數0)，將此查詢前綴“0”送入隊列Q，跳轉到第四步。
(2)如果有多于一個的標簽響應，即發生了碰撞，此時可為根節點添加左子節點(表示二進制數0)，并把0送入堆棧S；然后為節點0添加左子節點00和右子節點01。將01送入堆棧S，再跳轉到第三步，以00為查詢前綴。
(3)如果無標簽響應，跳轉到第二步。
第二步，讀寫器發送查詢前綴(1位的二進制數“1”)，此時也有如下幾種情況：
(1)若有標簽響應且無碰撞發生，則為根節點添加右子節點(表示二進制數1)，將查詢前綴“1”送入隊列Q中，跳轉到第四步。
(2)若有碰撞發生，則為根節點添加右子節點(表示二進制數1)，并把1送人堆棧S；然后為節點1添加左子節點10和右子節點11。將11送入堆棧S，以10為查詢前綴。
(3)若無標簽響應，說明讀寫器作用范圍內無標簽存在或者系統可能出現故障，識別流程結束。
第三步，讀寫器發送查詢前綴。若收到響應且無碰撞發生，則將此查詢前綴送入Q；若有碰撞發生，則分別添加左子樹和右子樹，右子樹壓入堆棧S，左子樹作為新的查詢前綴，重復步驟第三步；如無標簽響應，則從堆棧S中彈出一個元素作為查詢前綴，重復第三步。
第四步，當讀寫器成功識別某標簽，先與讀寫器進行通信，然后使標簽進入“無聲”狀態，即此標簽不再響應讀寫器的查詢。從堆棧S中彈出一個元素作為查詢前綴，重復第三步，直至所有的標簽被識別出來。
4．3 改進型算法實例
假設系統內有四個待識別的標簽，其序列號ID分別為0010、0100、1010、1101。其首次識別過程如表1所列。
首先，讀寫器發送查詢前綴0，標簽0010和0100響應，發生碰撞，將0送入堆棧S；添加左子節電00和右子節點01，將01送入堆棧S，以00作為新的查詢前綴。讀寫器發送查詢前綴00，此時只有標簽0010響應，將查詢前綴00送入隊列Q；此標簽被成功識別，與讀寫器通信完畢后，進入“無聲”狀態。從堆棧S中彈出01，作為新的查詢前綴，此時只有標簽0100響應，將查詢前綴01送入隊列Q；此標簽被成功識別。
然后再從堆棧S中彈出0，作為新的查詢前綴，此時無標簽響應，因此讀寫器以1為查詢前綴。標簽1010和1101響應，發生了碰撞，將1送入堆棧S；添加左子節點10和右子節點11，將11送入堆棧S，以10作為新的查詢前綴。讀寫器發送查詢前綴10，此時只有標簽1010響應，將查詢前綴10送入隊列Q；此標簽被成功識別。從堆棧S中彈出11，作為新的查詢前綴，此時只有標簽1101響應，將查詢前綴11送入隊列Q；此標簽被成功識別。
評論