RFID中解決無線信道爭(zhēng)用問題的防碰撞算法研究
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://butianyuan.cn/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í)別。
然后再從堆棧S中彈出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)論