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