RFID中解決無線信道爭用問題的防碰撞算法研究

查詢樹算法用隊列Q存儲查詢信息，標簽不必存儲序列號ID以外的無關(guān)信息，這樣，標簽就具有更簡單的功能，可降低標簽成本，因此，QT算法是無記憶的算法。圖2所示是QT算法的一個示意圖。系統(tǒng)中的標簽ID號為0010、1110和1101。

4 改進型算法
4．1 改進型算法思想
讀寫器引入一個堆棧S來存儲二又樹發(fā)生碰撞時右子樹節(jié)點信息，一個隊列Q來存儲無碰撞發(fā)生時的查詢前綴。
設(shè)標簽序列號ID是長為L的二進制數(shù)，讀寫器查詢前綴是長度不大于L的二進制數(shù)。那么，讀寫器發(fā)送查詢前綴，使其作用范圍內(nèi)標簽將自己的序列號ID與查詢前綴相比較。如果查詢前綴與標簽自最高位開始的部分比特串相同，則標簽回復(fù)序列號ID剩余的部分比特串給讀寫器。初始時，二叉樹只有根節(jié)點，讀寫器的堆棧為空，隊列Q為空。
4．2 改進型算法流程
第一步，由讀寫器在初始時發(fā)送查詢前綴(1位的二進制數(shù)“0”)，此時有以下幾種情況：
(1)如果只有一個標簽響應(yīng)，即無碰撞發(fā)生，此時可為根節(jié)點添加左子節(jié)點(表示二進制數(shù)0)，將此查詢前綴“0”送入隊列Q，跳轉(zhuǎn)到第四步。
(2)如果有多于一個的標簽響應(yīng)，即發(fā)生了碰撞，此時可為根節(jié)點添加左子節(jié)點(表示二進制數(shù)0)，并把0送入堆棧S；然后為節(jié)點0添加左子節(jié)點00和右子節(jié)點01。將01送入堆棧S，再跳轉(zhuǎn)到第三步，以00為查詢前綴。
(3)如果無標簽響應(yīng)，跳轉(zhuǎn)到第二步。
第二步，讀寫器發(fā)送查詢前綴(1位的二進制數(shù)“1”)，此時也有如下幾種情況：
(1)若有標簽響應(yīng)且無碰撞發(fā)生，則為根節(jié)點添加右子節(jié)點(表示二進制數(shù)1)，將查詢前綴“1”送入隊列Q中，跳轉(zhuǎn)到第四步。
(2)若有碰撞發(fā)生，則為根節(jié)點添加右子節(jié)點(表示二進制數(shù)1)，并把1送人堆棧S；然后為節(jié)點1添加左子節(jié)點10和右子節(jié)點11。將11送入堆棧S，以10為查詢前綴。
(3)若無標簽響應(yīng)，說明讀寫器作用范圍內(nèi)無標簽存在或者系統(tǒng)可能出現(xiàn)故障，識別流程結(jié)束。
第三步，讀寫器發(fā)送查詢前綴。若收到響應(yīng)且無碰撞發(fā)生，則將此查詢前綴送入Q；若有碰撞發(fā)生，則分別添加左子樹和右子樹，右子樹壓入堆棧S，左子樹作為新的查詢前綴，重復(fù)步驟第三步；如無標簽響應(yīng)，則從堆棧S中彈出一個元素作為查詢前綴，重復(fù)第三步。
第四步，當讀寫器成功識別某標簽，先與讀寫器進行通信，然后使標簽進入“無聲”狀態(tài)，即此標簽不再響應(yīng)讀寫器的查詢。從堆棧S中彈出一個元素作為查詢前綴，重復(fù)第三步，直至所有的標簽被識別出來。
4．3 改進型算法實例
假設(shè)系統(tǒng)內(nèi)有四個待識別的標簽，其序列號ID分別為0010、0100、1010、1101。其首次識別過程如表1所列。

首先，讀寫器發(fā)送查詢前綴0，標簽0010和0100響應(yīng)，發(fā)生碰撞，將0送入堆棧S；添加左子節(jié)電00和右子節(jié)點01，將01送入堆棧S，以00作為新的查詢前綴。讀寫器發(fā)送查詢前綴00，此時只有標簽0010響應(yīng)，將查詢前綴00送入隊列Q；此標簽被成功識別，與讀寫器通信完畢后，進入“無聲”狀態(tài)。從堆棧S中彈出01，作為新的查詢前綴，此時只有標簽0100響應(yīng)，將查詢前綴01送入隊列Q；此標簽被成功識別。
然后再從堆棧S中彈出0，作為新的查詢前綴，此時無標簽響應(yīng)，因此讀寫器以1為查詢前綴。標簽1010和1101響應(yīng)，發(fā)生了碰撞，將1送入堆棧S；添加左子節(jié)點10和右子節(jié)點11，將11送入堆棧S，以10作為新的查詢前綴。讀寫器發(fā)送查詢前綴10，此時只有標簽1010響應(yīng)，將查詢前綴10送入隊列Q；此標簽被成功識別。從堆棧S中彈出11，作為新的查詢前綴，此時只有標簽1101響應(yīng)，將查詢前綴11送入隊列Q；此標簽被成功識別。