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