第八章-RFID防碰撞技術(shù)

1、第八章 RFID防碰撞技術(shù) 快速、準(zhǔn)確、有效的防碰撞問題解決方案對快速、準(zhǔn)確、有效的防碰撞問題解決方案對RFIDRFID技術(shù)的發(fā)展有著至關(guān)重要的作用。標(biāo)簽防碰技術(shù)的發(fā)展有著至關(guān)重要的作用。標(biāo)簽防碰撞算法就是要解決在讀寫器的有效通信范圍內(nèi)，撞算法就是要解決在讀寫器的有效通信范圍內(nèi)，多個標(biāo)簽如何同時與讀寫器進(jìn)行通信的問題。在多個標(biāo)簽如何同時與讀寫器進(jìn)行通信的問題。在高頻（高頻（HFHF）頻段，標(biāo)簽的防碰撞算法一般采用）頻段，標(biāo)簽的防碰撞算法一般采用ALOHAALOHA。在超高頻（。在超高頻（UHFUHF）頻段，主要采用二進(jìn)制）頻段，主要采用二進(jìn)制樹型搜索算法。本章將重點介紹這兩類算法及其樹型搜索算

2、法。本章將重點介紹這兩類算法及其擴(kuò)展算法。擴(kuò)展算法。8.1 RFID系統(tǒng)中的碰撞與防碰撞 nRFID系統(tǒng)中的碰撞 RFIDRFID系統(tǒng)經(jīng)常會出現(xiàn)多個讀寫器以及多個標(biāo)簽的應(yīng)用場合，從而系統(tǒng)經(jīng)常會出現(xiàn)多個讀寫器以及多個標(biāo)簽的應(yīng)用場合，從而導(dǎo)致標(biāo)簽之間或讀寫器之間的相互干擾，這種干擾稱為導(dǎo)致標(biāo)簽之間或讀寫器之間的相互干擾，這種干擾稱為碰撞碰撞，也稱，也稱為沖突。為沖突。 RFIDRFID系統(tǒng)存在兩類碰撞問題：系統(tǒng)存在兩類碰撞問題： （1 1）一類稱為）一類稱為多標(biāo)簽碰撞問題多標(biāo)簽碰撞問題，即多個標(biāo)簽與同一個讀寫器同，即多個標(biāo)簽與同一個讀寫器同時通信時產(chǎn)生的碰撞；時通信時產(chǎn)生的碰撞； （2 2）另一類

3、稱為）另一類稱為多讀寫器碰撞問題多讀寫器碰撞問題，即相鄰的讀寫器在其信號，即相鄰的讀寫器在其信號交疊區(qū)域內(nèi)產(chǎn)生干擾，導(dǎo)致讀寫器的閱讀范圍減小，甚至無法讀取交疊區(qū)域內(nèi)產(chǎn)生干擾，導(dǎo)致讀寫器的閱讀范圍減小，甚至無法讀取標(biāo)簽。標(biāo)簽。8.1 RFID系統(tǒng)中的碰撞與防碰撞1.多讀寫器碰撞 當(dāng)相鄰的讀寫器作用范圍有重疊時，多個讀寫器同時讀取同一當(dāng)相鄰的讀寫器作用范圍有重疊時，多個讀寫器同時讀取同一個標(biāo)簽時可能會引起多讀寫器與標(biāo)簽之間的干擾。如圖標(biāo)簽同時收個標(biāo)簽時可能會引起多讀寫器與標(biāo)簽之間的干擾。如圖標(biāo)簽同時收到到3 3個讀寫器的信號，標(biāo)簽無法正確解析讀寫器發(fā)來的查詢信號。個讀寫器的信號，標(biāo)簽無法正確解析讀

4、寫器發(fā)來的查詢信號。 讀寫器自身有能量供應(yīng)，能進(jìn)行較高復(fù)雜度的計算，所以讀寫讀寫器自身有能量供應(yīng)，能進(jìn)行較高復(fù)雜度的計算，所以讀寫器能檢測到碰撞產(chǎn)生，并通過與其他讀寫器之間的交流互通來解決器能檢測到碰撞產(chǎn)生，并通過與其他讀寫器之間的交流互通來解決讀寫器的碰撞問題，如讀寫器調(diào)度算法和功率控制算法。讀寫器的碰撞問題，如讀寫器調(diào)度算法和功率控制算法。8.1 RFID系統(tǒng)中的碰撞與防碰撞2.多標(biāo)簽碰撞 多標(biāo)簽碰撞多標(biāo)簽碰撞是指讀寫器同時收到多個標(biāo)簽信號而導(dǎo)致無法正確是指讀寫器同時收到多個標(biāo)簽信號而導(dǎo)致無法正確讀取標(biāo)簽信息的問題。如圖讀寫器發(fā)出識別命令后，在標(biāo)簽應(yīng)答過讀取標(biāo)簽信息的問題。如圖讀寫器發(fā)出識

5、別命令后，在標(biāo)簽應(yīng)答過程中可能會兩個或者多個標(biāo)簽同一時刻應(yīng)答，或一個標(biāo)簽還沒有完程中可能會兩個或者多個標(biāo)簽同一時刻應(yīng)答，或一個標(biāo)簽還沒有完成應(yīng)答時其他標(biāo)簽就做出應(yīng)答。它會使得標(biāo)簽之間的信號互相干成應(yīng)答時其他標(biāo)簽就做出應(yīng)答。它會使得標(biāo)簽之間的信號互相干擾，從而造成標(biāo)簽無法被正常讀取。本章后續(xù)討論的防碰撞都是針擾，從而造成標(biāo)簽無法被正常讀取。本章后續(xù)討論的防碰撞都是針對多標(biāo)簽防碰撞。對多標(biāo)簽防碰撞。8.1 RFID系統(tǒng)中的碰撞與防碰撞nRFID系統(tǒng)中防碰撞算法分類 電子標(biāo)簽的低功耗、低存儲能力和有限的計算能力等限制，導(dǎo)電子標(biāo)簽的低功耗、低存儲能力和有限的計算能力等限制，導(dǎo)致許多成熟的防碰撞算法（如

6、空分多路法）不能直接在致許多成熟的防碰撞算法（如空分多路法）不能直接在RFIDRFID系統(tǒng)中系統(tǒng)中應(yīng)用。這些限制可以歸納為：應(yīng)用。這些限制可以歸納為： （1 1）無源標(biāo)簽沒有內(nèi)置電源，標(biāo)簽的能量來自于讀寫器，因此算）無源標(biāo)簽沒有內(nèi)置電源，標(biāo)簽的能量來自于讀寫器，因此算法在執(zhí)行的過程中，標(biāo)簽功耗要求盡量低；法在執(zhí)行的過程中，標(biāo)簽功耗要求盡量低； （2 2）RFIDRFID系統(tǒng)的通信帶寬有限，因此防碰撞算法應(yīng)盡量減少讀寫系統(tǒng)的通信帶寬有限，因此防碰撞算法應(yīng)盡量減少讀寫器和標(biāo)簽之間傳輸信息的比特數(shù)目；器和標(biāo)簽之間傳輸信息的比特數(shù)目； （3 3）標(biāo)簽不具備檢測沖突的功能而且標(biāo)簽間不能相互通信，因此）標(biāo)

7、簽不具備檢測沖突的功能而且標(biāo)簽間不能相互通信，因此沖突判決需要讀寫器來實現(xiàn)；沖突判決需要讀寫器來實現(xiàn)； （4 4）標(biāo)簽的存儲和計算能力有限，這就要求防碰撞協(xié)議盡可能簡）標(biāo)簽的存儲和計算能力有限，這就要求防碰撞協(xié)議盡可能簡單，標(biāo)簽端的設(shè)計不能太復(fù)雜。單，標(biāo)簽端的設(shè)計不能太復(fù)雜。8.1 RFID系統(tǒng)中的碰撞與防碰撞1.無線通信中的防碰撞方法 解決防碰撞的方法主要包括空分多路（解決防碰撞的方法主要包括空分多路（SDMASDMA）、頻分多路法）、頻分多路法（FDMAFDMA）、碼分多路法（）、碼分多路法（CDMACDMA）和時分多路法（）和時分多路法（TDMATDMA）。）。 1）空分多路法 空分多路

8、法空分多路法（SDMASDMA）是在分離的空間范圍內(nèi)實現(xiàn)多個目標(biāo)識別。）是在分離的空間范圍內(nèi)實現(xiàn)多個目標(biāo)識別。一種實現(xiàn)方法是將讀寫器和天線之間的作用距離按空間區(qū)域進(jìn)行一種實現(xiàn)方法是將讀寫器和天線之間的作用距離按空間區(qū)域進(jìn)行劃分，把讀寫器和天線安置在一個天線陣列中。當(dāng)標(biāo)簽進(jìn)入這個劃分，把讀寫器和天線安置在一個天線陣列中。當(dāng)標(biāo)簽進(jìn)入這個天線陣列的覆蓋范圍后，與其距離最近的讀寫器對該標(biāo)簽進(jìn)行識天線陣列的覆蓋范圍后，與其距離最近的讀寫器對該標(biāo)簽進(jìn)行識別。由于每個天線的覆蓋范圍較小，相鄰的讀寫器識別范圍內(nèi)的別。由于每個天線的覆蓋范圍較小，相鄰的讀寫器識別范圍內(nèi)的標(biāo)簽同樣可以進(jìn)行識別而不受相鄰讀寫器的干擾

9、，如果多個標(biāo)簽標(biāo)簽同樣可以進(jìn)行識別而不受相鄰讀寫器的干擾，如果多個標(biāo)簽根據(jù)在天線陣列中的空間位置的不同，可以同時被識別。根據(jù)在天線陣列中的空間位置的不同，可以同時被識別。 另一種實現(xiàn)方法是讀寫器利用相控陣天線，讓天線的方向性圖另一種實現(xiàn)方法是讀寫器利用相控陣天線，讓天線的方向性圖對準(zhǔn)單獨(dú)的標(biāo)簽，標(biāo)簽根據(jù)其在讀寫器作用范圍內(nèi)的角度位置不對準(zhǔn)單獨(dú)的標(biāo)簽，標(biāo)簽根據(jù)其在讀寫器作用范圍內(nèi)的角度位置不同而區(qū)別開來。同而區(qū)別開來。 空分多路法的空分多路法的缺點缺點是天線系統(tǒng)復(fù)雜，會大幅度提高成本。是天線系統(tǒng)復(fù)雜，會大幅度提高成本。8.1 RFID系統(tǒng)中的碰撞與防碰撞2）頻分多路法 頻分多路法頻分多路法（FD

10、MAFDMA）是把若干個使用不同載波頻率的調(diào)制信號）是把若干個使用不同載波頻率的調(diào)制信號在同時供通信用戶使用的信道上進(jìn)行傳輸?shù)募夹g(shù)。通常情況下，在同時供通信用戶使用的信道上進(jìn)行傳輸?shù)募夹g(shù)。通常情況下，RFIDRFID系統(tǒng)的前向鏈路（從讀寫器到標(biāo)簽）頻率是固定的，用于能量系統(tǒng)的前向鏈路（從讀寫器到標(biāo)簽）頻率是固定的，用于能量的供應(yīng)和數(shù)據(jù)的傳輸。對于反向鏈路，不同標(biāo)簽采用不同頻率的載的供應(yīng)和數(shù)據(jù)的傳輸。對于反向鏈路，不同標(biāo)簽采用不同頻率的載波進(jìn)行數(shù)據(jù)調(diào)制，信號之間不會產(chǎn)生干擾，讀寫器對接收到的不同波進(jìn)行數(shù)據(jù)調(diào)制，信號之間不會產(chǎn)生干擾，讀寫器對接收到的不同頻率的信號進(jìn)行分離，從而實現(xiàn)對不同標(biāo)簽的識別

11、。頻率的信號進(jìn)行分離，從而實現(xiàn)對不同標(biāo)簽的識別。 頻分多路法的缺點是導(dǎo)致讀寫器和標(biāo)簽成本要求較高。因此在頻分多路法的缺點是導(dǎo)致讀寫器和標(biāo)簽成本要求較高。因此在RFIDRFID應(yīng)用中，頻分多路法很少使用。應(yīng)用中，頻分多路法很少使用。8.1 RFID系統(tǒng)中的碰撞與防碰撞3）碼分多路法 碼分多路法（碼分多路法（CDMACDMA）是基于擴(kuò)頻通信技術(shù)發(fā)展起來的。）是基于擴(kuò)頻通信技術(shù)發(fā)展起來的。 擴(kuò)頻技術(shù)擴(kuò)頻技術(shù)包含擴(kuò)頻與多址兩個基本概念。包含擴(kuò)頻與多址兩個基本概念。擴(kuò)頻擴(kuò)頻目的是擴(kuò)展信息目的是擴(kuò)展信息帶寬，即把需發(fā)送的具有一定信號帶寬的信息數(shù)據(jù)，用一個帶寬遠(yuǎn)帶寬，即把需發(fā)送的具有一定信號帶寬的信息數(shù)據(jù)，

12、用一個帶寬遠(yuǎn)大于其信號帶寬的偽隨機(jī)碼進(jìn)行調(diào)制，使原來的信息數(shù)據(jù)的帶寬被大于其信號帶寬的偽隨機(jī)碼進(jìn)行調(diào)制，使原來的信息數(shù)據(jù)的帶寬被擴(kuò)展，最后通過載波調(diào)制發(fā)送出去。解擴(kuò)是指在接收端采用一致的擴(kuò)展，最后通過載波調(diào)制發(fā)送出去。解擴(kuò)是指在接收端采用一致的偽隨機(jī)碼，與接收到的寬帶信號作相關(guān)處理，把寬帶信號轉(zhuǎn)換成原偽隨機(jī)碼，與接收到的寬帶信號作相關(guān)處理，把寬帶信號轉(zhuǎn)換成原來的信息。來的信息。多址多址是給每個用戶分配一個地址碼，碼型互不重疊。是給每個用戶分配一個地址碼，碼型互不重疊。 碼分多路法具有抗干擾性好，保密安全性高，信道利用率高等碼分多路法具有抗干擾性好，保密安全性高，信道利用率高等優(yōu)點。但是該技術(shù)也

13、存在諸多缺點，如頻帶利用率低、信道容量優(yōu)點。但是該技術(shù)也存在諸多缺點，如頻帶利用率低、信道容量小，偽隨機(jī)碼的產(chǎn)生和選擇較難，接收時地址碼捕獲時間長等，所小，偽隨機(jī)碼的產(chǎn)生和選擇較難，接收時地址碼捕獲時間長等，所以該方法很難應(yīng)用于實際的以該方法很難應(yīng)用于實際的RFIDRFID系統(tǒng)中。系統(tǒng)中。8.1 RFID系統(tǒng)中的碰撞與防碰撞4）時分多路法 時分多路法（時分多路法（TDMATDMA）是把整個可供使用的通路容量按時間分配）是把整個可供使用的通路容量按時間分配給多個用戶的技術(shù)。給多個用戶的技術(shù)。 時分多路復(fù)用時分多路復(fù)用是按傳輸信號的時間進(jìn)行分割的，它使不同的信是按傳輸信號的時間進(jìn)行分割的，它使不同

14、的信號在不同的時間內(nèi)傳輸，將整個傳輸時間分為許多時間間隔，每個號在不同的時間內(nèi)傳輸，將整個傳輸時間分為許多時間間隔，每個時間片被一路信號占用。時間片被一路信號占用。 TDMATDMA就是通過在時間上交叉發(fā)送每一路信號的一部分來實現(xiàn)一就是通過在時間上交叉發(fā)送每一路信號的一部分來實現(xiàn)一條電路傳輸多路信號的。電路上每一短暫時刻只有一路信號存在。條電路傳輸多路信號的。電路上每一短暫時刻只有一路信號存在。因為數(shù)字信號是有限個離散值，所以時分多路復(fù)用技術(shù)廣泛應(yīng)用于因為數(shù)字信號是有限個離散值，所以時分多路復(fù)用技術(shù)廣泛應(yīng)用于包括計算機(jī)網(wǎng)絡(luò)在內(nèi)的數(shù)字通信系統(tǒng)。包括計算機(jī)網(wǎng)絡(luò)在內(nèi)的數(shù)字通信系統(tǒng)。8.1 RFID系

15、統(tǒng)中的碰撞與防碰撞2.RFID中防碰撞算法分類 8.1 RFID系統(tǒng)中的碰撞與防碰撞n標(biāo)簽防碰撞算法 RFIDRFID系統(tǒng)的標(biāo)簽防碰撞算法大多采用時分多路法，該方法可分系統(tǒng)的標(biāo)簽防碰撞算法大多采用時分多路法，該方法可分為非確定性算法和確定性算法。為非確定性算法和確定性算法。 非確定性算法非確定性算法也稱標(biāo)簽控制法，在該方法中，讀寫器沒有對數(shù)也稱標(biāo)簽控制法，在該方法中，讀寫器沒有對數(shù)據(jù)傳輸進(jìn)行控制，標(biāo)簽的工作是非同步的，標(biāo)簽獲得處理的時間不據(jù)傳輸進(jìn)行控制，標(biāo)簽的工作是非同步的，標(biāo)簽獲得處理的時間不確定，因此標(biāo)簽存在確定，因此標(biāo)簽存在“饑餓饑餓”問題。問題。ALOHAALOHA算法算法是一種典型的

16、非確定是一種典型的非確定性性算法，實現(xiàn)簡單，廣泛用于解決標(biāo)簽的碰撞問題。算法，實現(xiàn)簡單，廣泛用于解決標(biāo)簽的碰撞問題。 確定性算法確定性算法也稱讀寫器控制法，由讀寫器觀察控制所有標(biāo)簽。也稱讀寫器控制法，由讀寫器觀察控制所有標(biāo)簽。按照規(guī)定算法，在讀寫器作用范圍內(nèi)，首先選中一個標(biāo)簽，在同一按照規(guī)定算法，在讀寫器作用范圍內(nèi)，首先選中一個標(biāo)簽，在同一時間內(nèi)讀寫器與一個標(biāo)簽建立通信關(guān)系。時間內(nèi)讀寫器與一個標(biāo)簽建立通信關(guān)系。二進(jìn)制樹型搜索算法二進(jìn)制樹型搜索算法是典是典型確定性算法，該類算法比較復(fù)雜，識別時間較長，但無標(biāo)簽饑餓型確定性算法，該類算法比較復(fù)雜，識別時間較長，但無標(biāo)簽饑餓問題。問題。8.2 ALO

17、HA算法 ALOHAALOHA算法算法是一種隨機(jī)接入方法，其基本思想是采取標(biāo)簽先發(fā)言是一種隨機(jī)接入方法，其基本思想是采取標(biāo)簽先發(fā)言的方式，當(dāng)標(biāo)簽進(jìn)入讀寫器的識別區(qū)域內(nèi)時就自動向讀寫器發(fā)送其的方式，當(dāng)標(biāo)簽進(jìn)入讀寫器的識別區(qū)域內(nèi)時就自動向讀寫器發(fā)送其自身的自身的IDID號，在標(biāo)簽發(fā)送數(shù)據(jù)的過程中，若有其他標(biāo)簽也在發(fā)送數(shù)號，在標(biāo)簽發(fā)送數(shù)據(jù)的過程中，若有其他標(biāo)簽也在發(fā)送數(shù)據(jù)，將會發(fā)生信號重疊，從而導(dǎo)致沖突。讀寫器檢測接收到的信號據(jù)，將會發(fā)生信號重疊，從而導(dǎo)致沖突。讀寫器檢測接收到的信號有無沖突，一旦發(fā)生沖突，讀寫器就發(fā)送命令讓標(biāo)簽停止發(fā)送，隨有無沖突，一旦發(fā)生沖突，讀寫器就發(fā)送命令讓標(biāo)簽停止發(fā)送，隨機(jī)

18、等待一段時間后再重新發(fā)送以減少沖突。機(jī)等待一段時間后再重新發(fā)送以減少沖突。8.2 ALOHA算法n純ALOHA算法 在純在純ALOHAALOHA算法中，若讀寫器檢測出信號存在相互干擾，讀寫器算法中，若讀寫器檢測出信號存在相互干擾，讀寫器就會以向電子標(biāo)簽發(fā)出命令，令其停止向讀寫器傳輸信號；電子標(biāo)就會以向電子標(biāo)簽發(fā)出命令，令其停止向讀寫器傳輸信號；電子標(biāo)簽在接收到命令信號之后，就會停止發(fā)送信息，并會在接下來的一簽在接收到命令信號之后，就會停止發(fā)送信息，并會在接下來的一個隨機(jī)時間段內(nèi)進(jìn)入到待命狀態(tài)，只有當(dāng)該時間段過去后，才會重個隨機(jī)時間段內(nèi)進(jìn)入到待命狀態(tài)，只有當(dāng)該時間段過去后，才會重新向讀寫器發(fā)送信

19、息。各個電子標(biāo)簽待命時間片段長度是隨機(jī)的，新向讀寫器發(fā)送信息。各個電子標(biāo)簽待命時間片段長度是隨機(jī)的，再次向讀寫器發(fā)送信號的時間也不相同，這樣減少碰撞的可能性。再次向讀寫器發(fā)送信號的時間也不相同，這樣減少碰撞的可能性。 當(dāng)讀寫器成功識別某一個標(biāo)簽后，就會立即對該標(biāo)簽下達(dá)命令當(dāng)讀寫器成功識別某一個標(biāo)簽后，就會立即對該標(biāo)簽下達(dá)命令使之進(jìn)入到休眠的狀態(tài)。而其他標(biāo)簽則會一直對讀寫器所發(fā)出命令使之進(jìn)入到休眠的狀態(tài)。而其他標(biāo)簽則會一直對讀寫器所發(fā)出命令進(jìn)行響應(yīng)，并重復(fù)發(fā)送信息給讀寫器，當(dāng)標(biāo)簽被識別后，就會一一進(jìn)行響應(yīng)，并重復(fù)發(fā)送信息給讀寫器，當(dāng)標(biāo)簽被識別后，就會一一進(jìn)入到休眠狀態(tài)，直到讀寫器識別出所有在其工

20、作區(qū)內(nèi)的標(biāo)簽后，進(jìn)入到休眠狀態(tài)，直到讀寫器識別出所有在其工作區(qū)內(nèi)的標(biāo)簽后，算法過程才結(jié)束。算法過程才結(jié)束。8.2 ALOHA算法n純ALOHA算法 純純ALOHAALOHA算法中的信號碰撞分兩種情況：算法中的信號碰撞分兩種情況： （1 1）一種是信號部分碰撞，即信號的一部分發(fā)生了沖突；）一種是信號部分碰撞，即信號的一部分發(fā)生了沖突； （2 2）一種則是信號的完全碰撞，是指數(shù)據(jù)完全發(fā)生了沖突。）一種則是信號的完全碰撞，是指數(shù)據(jù)完全發(fā)生了沖突。如圖所示，如圖所示，發(fā)生沖突的數(shù)據(jù)都無法被讀寫器所識別。發(fā)生沖突的數(shù)據(jù)都無法被讀寫器所識別。8.2 ALOHA算法n純ALOHA算法 純純ALOHAALOH

21、A算法的信道吞吐率算法的信道吞吐率S S與幀產(chǎn)生率與幀產(chǎn)生率G G之間的關(guān)系為之間的關(guān)系為 當(dāng)當(dāng)G G=0.5=0.5時，最大吞吐率時，最大吞吐率S S=1/(2e)18.4%=1/(2e)18.4%。發(fā)送幀不會產(chǎn)生碰撞。發(fā)送幀不會產(chǎn)生碰撞（即發(fā)送成功）的概率（即發(fā)送成功）的概率P P為為 電子標(biāo)簽數(shù)量越多，幀時越長，則電子標(biāo)簽數(shù)量越多，幀時越長，則G G越大，發(fā)送成功的概率越低。越大，發(fā)送成功的概率越低。 純純ALOHAALOHA算法雖然算法簡單，易于實現(xiàn)。但對于同一個標(biāo)簽，算法雖然算法簡單，易于實現(xiàn)。但對于同一個標(biāo)簽，如果連續(xù)多次發(fā)生碰撞，這將導(dǎo)致讀寫器出現(xiàn)錯誤判斷認(rèn)為這個標(biāo)如果連續(xù)多次發(fā)

22、生碰撞，這將導(dǎo)致讀寫器出現(xiàn)錯誤判斷認(rèn)為這個標(biāo)簽不在自己的作用范圍內(nèi)。同時其沖突概率很大。簽不在自己的作用范圍內(nèi)。同時其沖突概率很大。假設(shè)其數(shù)據(jù)幀長假設(shè)其數(shù)據(jù)幀長度為度為F，則沖突周期為，則沖突周期為2F。2eGSG2eGSPG8.2 ALOHA算法n時隙ALOHA算法 時隙時隙ALOHAALOHA算法把時間分成多個離散的時隙，每個時隙長度等于算法把時間分成多個離散的時隙，每個時隙長度等于或稍大于一個幀，標(biāo)簽只能在每個時隙的開始處發(fā)送數(shù)據(jù)。這樣標(biāo)或稍大于一個幀，標(biāo)簽只能在每個時隙的開始處發(fā)送數(shù)據(jù)。這樣標(biāo)簽要么成功發(fā)送，要么完全碰撞，避免了純簽要么成功發(fā)送，要么完全碰撞，避免了純ALOHAALOH

23、A算法中的部分碰撞算法中的部分碰撞沖突，碰撞周期減半，提高了信道利用率。時隙沖突，碰撞周期減半，提高了信道利用率。時隙ALOHAALOHA算法需要讀寫算法需要讀寫器對其識別區(qū)域內(nèi)的標(biāo)簽校準(zhǔn)時間。時隙器對其識別區(qū)域內(nèi)的標(biāo)簽校準(zhǔn)時間。時隙ALOHAALOHA算法是隨機(jī)詢問驅(qū)動算法是隨機(jī)詢問驅(qū)動的的TDMATDMA防沖撞算法，工作過程如圖所示。防沖撞算法，工作過程如圖所示。8.2 ALOHA算法n時隙ALOHA算法時隙時隙ALOHAALOHA算法的信道吞吐率算法的信道吞吐率S S和幀產(chǎn)生率和幀產(chǎn)生率G G的關(guān)系為的關(guān)系為 當(dāng)當(dāng)G G=1=1時，吞吐量時，吞吐量S S為最大值為最大值1/e1/e，約為

24、，約為0.3680.368，是純，是純ALOHAALOHA算法的算法的兩倍。兩倍。 因為標(biāo)簽僅僅在確定的時隙中傳輸數(shù)據(jù)，所以該算法的沖撞發(fā)因為標(biāo)簽僅僅在確定的時隙中傳輸數(shù)據(jù)，所以該算法的沖撞發(fā)生頻率僅僅是純生頻率僅僅是純ALOHAALOHA算法的一半，但其系統(tǒng)的數(shù)據(jù)吞吐性能卻會增算法的一半，但其系統(tǒng)的數(shù)據(jù)吞吐性能卻會增加一倍。加一倍。eGSG8.2 ALOHA算法n幀時隙ALOHA算法 幀時隙算法中，時間被分成多個離散時隙，電子標(biāo)簽必須在時幀時隙算法中，時間被分成多個離散時隙，電子標(biāo)簽必須在時隙開始處才可以開始傳輸信息。讀寫器以一個幀為周期發(fā)送查詢命隙開始處才可以開始傳輸信息。讀寫器以一個幀為

25、周期發(fā)送查詢命令。當(dāng)電子標(biāo)簽接收到讀寫器的請求命令時，每個標(biāo)簽通過隨機(jī)挑令。當(dāng)電子標(biāo)簽接收到讀寫器的請求命令時，每個標(biāo)簽通過隨機(jī)挑選一個時隙發(fā)送信息給讀寫器。如果一個時隙只被唯一標(biāo)簽選中，選一個時隙發(fā)送信息給讀寫器。如果一個時隙只被唯一標(biāo)簽選中，則此時隙中標(biāo)簽傳輸?shù)男畔⒈蛔x寫器成功接收，標(biāo)簽被正確識別。則此時隙中標(biāo)簽傳輸?shù)男畔⒈蛔x寫器成功接收，標(biāo)簽被正確識別。如果有兩個或兩個以上的標(biāo)簽選擇了同一時隙發(fā)送，則就會產(chǎn)生沖如果有兩個或兩個以上的標(biāo)簽選擇了同一時隙發(fā)送，則就會產(chǎn)生沖突，這些同時發(fā)送信息的標(biāo)簽就不能被讀寫器成功識別。整個算法突，這些同時發(fā)送信息的標(biāo)簽就不能被讀寫器成功識別。整個算法的識別

26、過程都會如此循環(huán)，一直到所有標(biāo)簽都被識別完成。的識別過程都會如此循環(huán)，一直到所有標(biāo)簽都被識別完成。8.2 ALOHA算法n幀時隙ALOHA算法 幀時隙幀時隙ALOHAALOHA算法工作過程如圖所示。算法工作過程如圖所示。 該算法的缺點是當(dāng)標(biāo)簽數(shù)量遠(yuǎn)大于時隙個數(shù)時，讀取標(biāo)簽的時該算法的缺點是當(dāng)標(biāo)簽數(shù)量遠(yuǎn)大于時隙個數(shù)時，讀取標(biāo)簽的時間會大大增加；當(dāng)標(biāo)簽個數(shù)遠(yuǎn)小于時隙個數(shù)時，會造成時隙浪費(fèi)。間會大大增加；當(dāng)標(biāo)簽個數(shù)遠(yuǎn)小于時隙個數(shù)時，會造成時隙浪費(fèi)。8.2 ALOHA算法n幀時隙ALOHA算法 一個典型的幀時隙一個典型的幀時隙ALOHAALOHA算法過程如圖所示。算法過程如圖所示。 在每一幀初始時刻，

27、讀寫器發(fā)出請求指令，向標(biāo)簽提供幀長等在每一幀初始時刻，讀寫器發(fā)出請求指令，向標(biāo)簽提供幀長等信息。每個標(biāo)簽根據(jù)信息隨機(jī)選擇一個時隙向讀寫器發(fā)送信息。假信息。每個標(biāo)簽根據(jù)信息隨機(jī)選擇一個時隙向讀寫器發(fā)送信息。假設(shè)標(biāo)簽的序列號為設(shè)標(biāo)簽的序列號為4 4比特，在第一幀中，標(biāo)簽比特，在第一幀中，標(biāo)簽1 1和標(biāo)簽和標(biāo)簽3 3選擇了時隙選擇了時隙1 1與讀寫器通信，標(biāo)簽與讀寫器通信，標(biāo)簽2 2和標(biāo)簽和標(biāo)簽4 4選擇了時隙選擇了時隙2 2。時隙。時隙1 1和時隙和時隙2 2都發(fā)生了都發(fā)生了碰撞，而標(biāo)簽碰撞，而標(biāo)簽5 5在時隙在時隙3 3中被讀寫器成功識別。第二幀中標(biāo)簽中被讀寫器成功識別。第二幀中標(biāo)簽3 3和標(biāo)簽

28、和標(biāo)簽2 2被成功識別。如此循環(huán)直到所有標(biāo)簽被成功識別為止。被成功識別。如此循環(huán)直到所有標(biāo)簽被成功識別為止。8.2 ALOHA算法n動態(tài)幀時隙ALOHA算法 動態(tài)幀時隙動態(tài)幀時隙ALOHAALOHA算法中一個幀內(nèi)的時隙數(shù)目隨著區(qū)域內(nèi)標(biāo)簽算法中一個幀內(nèi)的時隙數(shù)目隨著區(qū)域內(nèi)標(biāo)簽數(shù)目動態(tài)改變，或增加時隙數(shù)以減少幀中的碰撞數(shù)目。步驟如下：數(shù)目動態(tài)改變，或增加時隙數(shù)以減少幀中的碰撞數(shù)目。步驟如下： （1 1）進(jìn)入識別狀態(tài)，開始識別命令中包含了初始的時隙數(shù)）進(jìn)入識別狀態(tài)，開始識別命令中包含了初始的時隙數(shù)N N。 （2 2）由電子標(biāo)簽隨機(jī)選擇一個時隙，同時將自己的時隙計數(shù)器）由電子標(biāo)簽隨機(jī)選擇一個時隙，同時

29、將自己的時隙計數(shù)器復(fù)位為復(fù)位為1 1。 （3 3）當(dāng)電子標(biāo)簽隨機(jī)選擇的時隙數(shù)與時隙計數(shù)器對應(yīng)時，標(biāo)簽）當(dāng)電子標(biāo)簽隨機(jī)選擇的時隙數(shù)與時隙計數(shù)器對應(yīng)時，標(biāo)簽向讀寫器發(fā)送數(shù)據(jù)；若不相等，標(biāo)簽將保留自己的時隙數(shù)并等待下向讀寫器發(fā)送數(shù)據(jù)；若不相等，標(biāo)簽將保留自己的時隙數(shù)并等待下一個命令。一個命令。 （4 4）當(dāng)讀寫器檢測到的時隙數(shù)量等于命令中規(guī)定的循環(huán)長度）當(dāng)讀寫器檢測到的時隙數(shù)量等于命令中規(guī)定的循環(huán)長度N N時，本次循環(huán)結(jié)束，讀寫器轉(zhuǎn)入步驟（時，本次循環(huán)結(jié)束，讀寫器轉(zhuǎn)入步驟（2 2），開始新的循環(huán)。），開始新的循環(huán)。 該算法每幀的時隙個數(shù)該算法每幀的時隙個數(shù)N N都是動態(tài)產(chǎn)生的，解決了幀時隙都是動態(tài)產(chǎn)

30、生的，解決了幀時隙ALOHAALOHA算法中的時隙浪費(fèi)的問題，適應(yīng)標(biāo)簽數(shù)量動態(tài)變化的情形。算法中的時隙浪費(fèi)的問題，適應(yīng)標(biāo)簽數(shù)量動態(tài)變化的情形。8.2 ALOHA算法n動態(tài)幀時隙ALOHA算法 動態(tài)幀時隙動態(tài)幀時隙ALOHAALOHA算法允許根據(jù)系統(tǒng)的需要動態(tài)地調(diào)整幀長度，算法允許根據(jù)系統(tǒng)的需要動態(tài)地調(diào)整幀長度，由于讀寫器作用范圍內(nèi)的標(biāo)簽數(shù)量是未知的，而且在識別的過程中由于讀寫器作用范圍內(nèi)的標(biāo)簽數(shù)量是未知的，而且在識別的過程中未被識別的標(biāo)簽數(shù)目是改變的，因此，如何估算標(biāo)簽數(shù)量以及合理未被識別的標(biāo)簽數(shù)目是改變的，因此，如何估算標(biāo)簽數(shù)量以及合理地調(diào)整幀長度成為動態(tài)幀時隙地調(diào)整幀長度成為動態(tài)幀時隙AL

31、OHAALOHA算法的關(guān)鍵。由理論推導(dǎo)可知，算法的關(guān)鍵。由理論推導(dǎo)可知，在標(biāo)簽數(shù)目和幀長度接近的情況下，系統(tǒng)的識別效率最高，也就是在標(biāo)簽數(shù)目和幀長度接近的情況下，系統(tǒng)的識別效率最高，也就是說標(biāo)簽的值就是幀長度的最佳選擇。說標(biāo)簽的值就是幀長度的最佳選擇。 在實際應(yīng)用中，動態(tài)幀時隙算法是在每幀結(jié)束后，根據(jù)上一幀在實際應(yīng)用中，動態(tài)幀時隙算法是在每幀結(jié)束后，根據(jù)上一幀的反饋情況檢測標(biāo)簽發(fā)生碰撞的次數(shù)（碰撞時隙數(shù)），電子標(biāo)簽被的反饋情況檢測標(biāo)簽發(fā)生碰撞的次數(shù)（碰撞時隙數(shù)），電子標(biāo)簽被成功識別的次數(shù)（成功時隙數(shù)）和電子標(biāo)簽在某個時隙沒有返回數(shù)成功識別的次數(shù)（成功時隙數(shù)）和電子標(biāo)簽在某個時隙沒有返回數(shù)據(jù)信息

32、的次數(shù)（空閑時隙數(shù)）來估計當(dāng)前未被正確識別的電子標(biāo)簽據(jù)信息的次數(shù)（空閑時隙數(shù)）來估計當(dāng)前未被正確識別的電子標(biāo)簽數(shù)目，然后選擇最佳的下一幀的長度，把它的幀長度作為下一輪識數(shù)目，然后選擇最佳的下一幀的長度，把它的幀長度作為下一輪識別的幀長，直到讀寫器工作范圍內(nèi)的電子標(biāo)簽全部識別完畢。別的幀長，直到讀寫器工作范圍內(nèi)的電子標(biāo)簽全部識別完畢。8.3 二進(jìn)制樹型搜索算法 二進(jìn)制樹型搜索算法二進(jìn)制樹型搜索算法由讀寫器控制由讀寫器控制，基本思想是不斷的將導(dǎo)致，基本思想是不斷的將導(dǎo)致碰撞的電子標(biāo)簽進(jìn)行劃分，縮小下一步搜索的標(biāo)簽數(shù)量，直到只有碰撞的電子標(biāo)簽進(jìn)行劃分，縮小下一步搜索的標(biāo)簽數(shù)量，直到只有一個電子標(biāo)簽進(jìn)

33、行回應(yīng)。一個電子標(biāo)簽進(jìn)行回應(yīng)。1沖突位檢測 實現(xiàn)該算法系統(tǒng)的必要前提是能夠辨認(rèn)出在讀寫器中數(shù)據(jù)沖突實現(xiàn)該算法系統(tǒng)的必要前提是能夠辨認(rèn)出在讀寫器中數(shù)據(jù)沖突位的準(zhǔn)確位置。為此，必須有合適的位編碼法。如圖對位的準(zhǔn)確位置。為此，必須有合適的位編碼法。如圖對NRZNRZ編碼和曼編碼和曼徹斯特編碼的沖突狀況作一比較。徹斯特編碼的沖突狀況作一比較。8.3 二進(jìn)制樹型搜索算法1）NRZ編碼 某位之值是在一個位窗（某位之值是在一個位窗（t tBITBIT）內(nèi)由傳輸通路的靜態(tài)電平表）內(nèi)由傳輸通路的靜態(tài)電平表示，這種邏輯示，這種邏輯“1” 1” 為為 “ “高高”電平，邏輯電平，邏輯“0” 0” 為為 “ “低低”

34、電平。電平。如果兩個如果兩個電子標(biāo)簽之一發(fā)送了副載波信號，那么，這個信號由讀寫器譯碼為電子標(biāo)簽之一發(fā)送了副載波信號，那么，這個信號由讀寫器譯碼為“高高”電平，就被認(rèn)定為邏輯電平，就被認(rèn)定為邏輯“1”1”。但讀寫器不能確定讀入的某位。但讀寫器不能確定讀入的某位究竟究竟是若干個電子標(biāo)簽發(fā)送的數(shù)據(jù)相互重疊的結(jié)果，還是某個電子標(biāo)簽是若干個電子標(biāo)簽發(fā)送的數(shù)據(jù)相互重疊的結(jié)果，還是某個電子標(biāo)簽單獨(dú)發(fā)送的信號，見下頁中圖（單獨(dú)發(fā)送的信號，見下頁中圖（a a）。）。2）曼徹斯特編碼 某位之值是在一個位窗（某位之值是在一個位窗（tBITtBIT）內(nèi)由電平的改變（上升）內(nèi)由電平的改變（上升/ /下降沿）下降沿）表示

35、。邏輯表示。邏輯“0”0”編碼為上升沿，邏輯編碼為上升沿，邏輯“”編碼為下降沿。如果兩編碼為下降沿。如果兩個或個或多個電子標(biāo)簽同時發(fā)送的數(shù)位有不同值，則接收的上升沿和下降沿多個電子標(biāo)簽同時發(fā)送的數(shù)位有不同值，則接收的上升沿和下降沿互相抵消，互相抵消，“沒有變化沒有變化”的狀態(tài)是不允許的，將作為錯誤被識別。的狀態(tài)是不允許的，將作為錯誤被識別。用用這種方法可以按位追溯跟蹤沖突的出現(xiàn)，見下頁中圖（這種方法可以按位追溯跟蹤沖突的出現(xiàn)，見下頁中圖（b b）。）。 8.3 二進(jìn)制樹型搜索算法 采用采用NRZNRZ編碼和曼徹斯特編碼的沖突狀況（曼徹斯特編碼能夠按編碼和曼徹斯特編碼的沖突狀況（曼徹斯特編碼能夠

36、按位識別出沖突）示意圖。因此，選用曼徹斯特編碼可實現(xiàn)位識別出沖突）示意圖。因此，選用曼徹斯特編碼可實現(xiàn)“二進(jìn)制二進(jìn)制樹樹型搜索型搜索”算法。算法。8.3 二進(jìn)制樹型搜索算法2.二進(jìn)制樹型搜索算法過程 二進(jìn)制樹型搜索算法的模型如圖所示，其基本思想是將處于沖二進(jìn)制樹型搜索算法的模型如圖所示，其基本思想是將處于沖突的標(biāo)簽分成左右兩個子集突的標(biāo)簽分成左右兩個子集0 0和和1 1，先查詢子集，先查詢子集0 0，若沒有沖突，則正，若沒有沖突，則正確識別標(biāo)簽，若仍有沖突則再分裂，把子集確識別標(biāo)簽，若仍有沖突則再分裂，把子集0 0分成分成0000和和0101兩個子集，兩個子集，依次類推，直到識別出子集依次類推

37、，直到識別出子集0 0中所有標(biāo)簽，再按此步驟查詢子集中所有標(biāo)簽，再按此步驟查詢子集1 1。可見，標(biāo)簽的序列號是處理碰撞的基礎(chǔ)?？梢?，標(biāo)簽的序列號是處理碰撞的基礎(chǔ)。8.3 二進(jìn)制樹型搜索算法二進(jìn)制樹型搜索算法的實現(xiàn)步驟如下：二進(jìn)制樹型搜索算法的實現(xiàn)步驟如下： （1 1）讀寫器廣播發(fā)送最大序列號查詢條件）讀寫器廣播發(fā)送最大序列號查詢條件Q Q，其作用范圍內(nèi)的標(biāo)，其作用范圍內(nèi)的標(biāo)簽在同一時刻傳輸它們的序列號至讀寫器。簽在同一時刻傳輸它們的序列號至讀寫器。 （2 2）讀寫器對收到的標(biāo)簽進(jìn)行響應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即）讀寫器對收到的標(biāo)簽進(jìn)行響應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號該位為有的序列號該位

38、為0 0，而有的序列號該位為，而有的序列號該位為1 1），則可判斷有碰撞。），則可判斷有碰撞。 （3 3）確定有碰撞后，把有不一致位的數(shù)最高位置）確定有碰撞后，把有不一致位的數(shù)最高位置0 0再輸出查詢條再輸出查詢條件件Q Q，依次排除序列號大于，依次排除序列號大于Q Q的標(biāo)簽。的標(biāo)簽。 （4 4）識別出序列號最小的標(biāo)簽后，對其進(jìn)行數(shù)據(jù)操作，然后使其）識別出序列號最小的標(biāo)簽后，對其進(jìn)行數(shù)據(jù)操作，然后使其進(jìn)入進(jìn)入“無聲無聲”狀態(tài)，則對讀寫器發(fā)送的查詢命令不進(jìn)行響應(yīng)。狀態(tài)，則對讀寫器發(fā)送的查詢命令不進(jìn)行響應(yīng)。 （5 5）重復(fù)步驟）重復(fù)步驟1 1，選出序列號倒數(shù)第二的標(biāo)簽。，選出序列號倒數(shù)第二的標(biāo)簽。

39、 （6 6）多次循環(huán)完后完成所有標(biāo)簽的識別。）多次循環(huán)完后完成所有標(biāo)簽的識別。8.3 二進(jìn)制樹型搜索算法 為了實現(xiàn)這種算法需要一組命令。這組命令可由電子標(biāo)簽進(jìn)為了實現(xiàn)這種算法需要一組命令。這組命令可由電子標(biāo)簽進(jìn)行處理（見下表），每個電子標(biāo)簽擁有一個唯一的序列號（行處理（見下表），每個電子標(biāo)簽擁有一個唯一的序列號（SNRSNR）。）。REQUEST（SNR）請求（序列號） 此命令發(fā)送一序列號作為參數(shù)給電子標(biāo)簽。電子標(biāo)簽把自己的序列號與接收的序列號進(jìn)行比較，如果小于或相等，則此電子標(biāo)簽回送其序列號給讀寫器。這樣就可以縮小預(yù)選的電子標(biāo)簽的范圍SELECT（SNR）選擇（序列號） 用某個（事先確定的）

40、序列號作為參數(shù)發(fā)送給電子標(biāo)簽，具有相同序列號的電子標(biāo)簽將以此作為執(zhí)行其他命令（如讀出和寫入數(shù)據(jù)）的切入開關(guān)，即選擇這個電子標(biāo)簽，具有其他序列號的電子標(biāo)簽只對REQUEST命令應(yīng)答READ-DATA讀出數(shù)據(jù) 選中的電子標(biāo)簽將存儲的數(shù)據(jù)發(fā)送給讀寫器（在實際的系統(tǒng)中，還有鑒別或?qū)懭氲让畹龋︰NSELECT退出選擇 取消一個事先選中的電子標(biāo)簽，電子標(biāo)簽進(jìn)入“無聲”狀態(tài)。在這種狀態(tài)下，電子標(biāo)簽完全是非激活的，對收到的REQUEST命令不作應(yīng)答。為了重新激活電子標(biāo)簽，必須暫時離開讀寫器的作用范圍（等于沒有供應(yīng)電壓），以執(zhí)行復(fù)位8.3 二進(jìn)制樹型搜索算法3二進(jìn)制樹型搜索算法實例 下面以一個實例來說明二進(jìn)制

41、樹型搜索算法?，F(xiàn)以讀寫器作用下面以一個實例來說明二進(jìn)制樹型搜索算法?，F(xiàn)以讀寫器作用范圍內(nèi)的四個電子標(biāo)簽為例說明搜索的過程。這四個電子標(biāo)簽的序范圍內(nèi)的四個電子標(biāo)簽為例說明搜索的過程。這四個電子標(biāo)簽的序列號（這里用列號（這里用8 8位的序列號舉例）分別為：位的序列號舉例）分別為： 電子標(biāo)簽電子標(biāo)簽1: 101100101: 10110010 電子標(biāo)簽電子標(biāo)簽2: 101000112: 10100011 電子標(biāo)簽電子標(biāo)簽3: 101100113: 10110011 電子標(biāo)簽電子標(biāo)簽4: 111000114: 11100011 二進(jìn)制樹型搜索算法算法在重復(fù)操作的第一次中由讀寫器發(fā)送二進(jìn)制樹型搜索算法算

42、法在重復(fù)操作的第一次中由讀寫器發(fā)送REQUESTREQUEST（1111111111111111）命令。序列號）命令。序列號1111111111111111，是本例中系統(tǒng)最大，是本例中系統(tǒng)最大可能的可能的8 8位序列號。讀寫器作用范圍內(nèi)的所有電子標(biāo)簽的序列號都應(yīng)位序列號。讀寫器作用范圍內(nèi)的所有電子標(biāo)簽的序列號都應(yīng)小于或等于小于或等于1111111111111111，因此，處于讀寫器作用范圍內(nèi)的所有電子標(biāo)，因此，處于讀寫器作用范圍內(nèi)的所有電子標(biāo)簽都應(yīng)對該命令作出應(yīng)答。簽都應(yīng)對該命令作出應(yīng)答。8.3 二進(jìn)制樹型搜索算法3二進(jìn)制樹型搜索算法實例 二進(jìn)制樹型搜索算法選擇電子標(biāo)簽的迭代過程如圖。二進(jìn)制樹

43、型搜索算法選擇電子標(biāo)簽的迭代過程如圖。8.3 二進(jìn)制樹型搜索算法 如上表所示如上表所示, ,對于所接收的序列號的對于所接收的序列號的0 0位、位、4 4位和位和6 6位，由于重位，由于重疊著響應(yīng)的電子標(biāo)簽對這些位的不同內(nèi)容而造成了沖突（疊著響應(yīng)的電子標(biāo)簽對這些位的不同內(nèi)容而造成了沖突（x x）。因）。因此，可以推斷在讀寫器作用范圍內(nèi)存在兩個或多個電子標(biāo)簽。仔細(xì)此，可以推斷在讀寫器作用范圍內(nèi)存在兩個或多個電子標(biāo)簽。仔細(xì)觀察表明：由于接收的位順序為觀察表明：由于接收的位順序為1x1x001x1x1x001x，從而可以得出所接收的，從而可以得出所接收的序列號的八種可能性。序列號的八種可能性。 第第6

44、 6位是最高的位是最高的x x位，此位在第一次迭代中上出現(xiàn)了沖突。這意位，此位在第一次迭代中上出現(xiàn)了沖突。這意味著：不僅在序列號（味著：不僅在序列號（SNRSNR）11000000b11000000b的范圍內(nèi)，而且在序列號的范圍內(nèi)，而且在序列號（SNRSNR）1 10 0111111b111111b的范圍內(nèi)，至少各有一個電子標(biāo)簽存在。為了的范圍內(nèi)，至少各有一個電子標(biāo)簽存在。為了能選擇到一個單獨(dú)的電子標(biāo)簽，必須根據(jù)已有的信息來限制下一次能選擇到一個單獨(dú)的電子標(biāo)簽，必須根據(jù)已有的信息來限制下一次迭代的搜索范圍。例如，用迭代的搜索范圍。例如，用1 10 0111111b111111b的范圍內(nèi)進(jìn)一步搜

45、索。為的范圍內(nèi)進(jìn)一步搜索。為此，將第此，將第6 6位置位置“0”0”（有沖突的最高值位），將所有低位置（有沖突的最高值位），將所有低位置“1”1”，從而從而暫時對所有的低值位置不予處理。暫時對所有的低值位置不予處理。8.3 二進(jìn)制樹型搜索算法二進(jìn)制樹型搜索樹通過地址參數(shù)限制搜索范圍的一般規(guī)則：二進(jìn)制樹型搜索樹通過地址參數(shù)限制搜索范圍的一般規(guī)則： 讀寫器發(fā)命令讀寫器發(fā)命令REQUESTREQUEST（1011111110111111）后，所有滿足此條件的）后，所有滿足此條件的電子標(biāo)簽都要做出應(yīng)答，并將它們自己的序列號傳輸給讀寫器。本電子標(biāo)簽都要做出應(yīng)答，并將它們自己的序列號傳輸給讀寫器。本例中，

46、做出應(yīng)答的是電子標(biāo)簽例中，做出應(yīng)答的是電子標(biāo)簽1 1、2 2和和3 3（見第二次迭代）。（見第二次迭代）?，F(xiàn)在接收的序列號的第現(xiàn)在接收的序列號的第0 0位和第位和第4 4位上出現(xiàn)了碰撞（位上出現(xiàn)了碰撞（x x）。由此得出）。由此得出結(jié)論：在第二次迭代的搜索范圍內(nèi)，至少還存在有兩個電子標(biāo)簽。結(jié)論：在第二次迭代的搜索范圍內(nèi)，至少還存在有兩個電子標(biāo)簽。需要進(jìn)一步確定的序列號有四種可能性。需要進(jìn)一步確定的序列號有四種可能性。 檢 索 命 令 第一次迭代：范圍= 第n次迭代：范圍= 請求（REQUEST）范圍 0 位（x）=1，位（0 x1）=0請求（REQUEST）范圍 序列號（SNR）Max 位（x

47、）=0，位（0 x1）=18.3 二進(jìn)制樹型搜索算法 如果第二次迭代仍然出現(xiàn)沖突，則要求第三次迭代進(jìn)一步限制如果第二次迭代仍然出現(xiàn)沖突，則要求第三次迭代進(jìn)一步限制搜索范圍。使用表格形成的規(guī)則，其搜索范圍搜索范圍。使用表格形成的規(guī)則，其搜索范圍1010111110101111。讀寫器。讀寫器將命令將命令REQUESTREQUEST（1010111110101111）發(fā)送給電子標(biāo)簽。只有電子標(biāo)簽）發(fā)送給電子標(biāo)簽。只有電子標(biāo)簽2 2（“10100011”10100011”）能滿足此條件，該電子標(biāo)簽即單獨(dú)對命令作出應(yīng)）能滿足此條件，該電子標(biāo)簽即單獨(dú)對命令作出應(yīng)答答（見第三次迭代）。（見第三次迭代）。

48、然后，讀寫器用然后，讀寫器用SELECTSELECT命令選中電子標(biāo)簽命令選中電子標(biāo)簽2 2，對該選中的電子標(biāo)，對該選中的電子標(biāo)簽進(jìn)行簽進(jìn)行READ-DATAREAD-DATA操作。此時其他電子標(biāo)簽則處于靜止?fàn)顟B(tài)。在完成操作。此時其他電子標(biāo)簽則處于靜止?fàn)顟B(tài)。在完成READ-DATAREAD-DATA操作后，讀寫器用操作后，讀寫器用UNSELECTUNSELECT命令使電子標(biāo)簽命令使電子標(biāo)簽2 2進(jìn)入進(jìn)入“無聲無聲”狀態(tài)，這樣電子標(biāo)簽狀態(tài)，這樣電子標(biāo)簽2 2對后繼的請求命令將不再做出應(yīng)答。對后繼的請求命令將不再做出應(yīng)答。8.3 二進(jìn)制樹型搜索算法 如圖形象地描述了上述例子的搜索過程，三次迭代需要不

49、斷地如圖形象地描述了上述例子的搜索過程，三次迭代需要不斷地搜索空間，直到第三次搜索定位到唯一的一個電子標(biāo)簽。搜索空間，直到第三次搜索定位到唯一的一個電子標(biāo)簽。二進(jìn)制樹型搜索樹：隨著搜索范圍的依次變小，最終可以選擇一個唯一的電子標(biāo)簽8.3 二進(jìn)制樹型搜索算法 為了從較大量的電子標(biāo)簽中搜索出某個唯一的電子標(biāo)簽，需要為了從較大量的電子標(biāo)簽中搜索出某個唯一的電子標(biāo)簽，需要多次迭代。其平均次數(shù)多次迭代。其平均次數(shù)L L取決于讀寫器作用范圍內(nèi)的電子標(biāo)簽總數(shù)取決于讀寫器作用范圍內(nèi)的電子標(biāo)簽總數(shù)N N，即，即 可以看出，利用二進(jìn)制樹型搜索算法可以快速簡單地解決碰撞可以看出，利用二進(jìn)制樹型搜索算法可以快速簡單地

50、解決碰撞問題。如果只有一個電子標(biāo)簽在讀寫器作用范圍內(nèi)，在這種情況下問題。如果只有一個電子標(biāo)簽在讀寫器作用范圍內(nèi)，在這種情況下不會出現(xiàn)沖突，只需要一次迭代就可發(fā)現(xiàn)電子標(biāo)簽的序列號。如果不會出現(xiàn)沖突，只需要一次迭代就可發(fā)現(xiàn)電子標(biāo)簽的序列號。如果有一個以上的電子標(biāo)簽處在讀寫器作用范圍內(nèi)，那么迭代的平均數(shù)有一個以上的電子標(biāo)簽處在讀寫器作用范圍內(nèi)，那么迭代的平均數(shù)增加很快。增加很快。2()log1L NN8.3 二進(jìn)制樹型搜索算法n動態(tài)二進(jìn)制樹型搜索 二進(jìn)制樹型搜索算法為了選擇一個電子標(biāo)簽傳輸大量多余的數(shù)據(jù)。如圖用X表示最高沖突位的位置，在前述的迭代的最高沖突位上出現(xiàn)了位沖突，即可得出： 命令中（X1）

51、0各位不包含給電子標(biāo)簽的補(bǔ)充信息，因為（X1）0各位總是被置為“1”的。 電子標(biāo)簽序列號的NX各位不包含給讀寫器的補(bǔ)充信息，因為NX這些位是已知且給定的。在搜索一個4字節(jié)序列號時，讀寫器的命令（第n次迭代）和電子標(biāo)簽的應(yīng)答8.3 二進(jìn)制樹型搜索算法動態(tài)二進(jìn)制樹型搜索算法的工作步驟如下：動態(tài)二進(jìn)制樹型搜索算法的工作步驟如下： （1 1）讀寫器第一次發(fā)出一個完整的查詢條件）讀寫器第一次發(fā)出一個完整的查詢條件Q Q，長度為，長度為N N，每個位，每個位上的碼全為上的碼全為1 1，讓所有標(biāo)簽都返回各自的序列號。，讓所有標(biāo)簽都返回各自的序列號。 （2 2）讀寫器判斷有碰撞的最高位）讀寫器判斷有碰撞的最高

52、位X X，將該位置，將該位置0 0。然后傳輸。然后傳輸N NX X位位的數(shù)據(jù)。標(biāo)簽接到這個查詢信號后檢查自己的序列號是否匹配，如的數(shù)據(jù)。標(biāo)簽接到這個查詢信號后檢查自己的序列號是否匹配，如果匹配則回傳自己序列號的果匹配則回傳自己序列號的X X1 10 0位。位。 （3 3）讀寫器檢測第二次返回的最高碰撞位數(shù)）讀寫器檢測第二次返回的最高碰撞位數(shù)XX是否小于前一次是否小于前一次檢檢測回傳的次高碰撞位數(shù)，若不是，則直接把該位置測回傳的次高碰撞位數(shù)，若不是，則直接把該位置“0”0”；若是，則；若是，則要要把前一次檢測的次高位也置為把前一次檢測的次高位也置為“0”0”。然后廣播新的查詢信息。發(fā)出。然后廣播

53、新的查詢信息。發(fā)出查查詢條件的位數(shù)為詢條件的位數(shù)為N NXX，滿足查詢條件的電子標(biāo)簽回傳的信號只是，滿足查詢條件的電子標(biāo)簽回傳的信號只是序序列號中最高碰撞位后的數(shù)，即列號中最高碰撞位后的數(shù)，即XX1 10 0位。若標(biāo)簽返回信號沒有發(fā)位。若標(biāo)簽返回信號沒有發(fā)生生碰撞，則對該序列號標(biāo)簽進(jìn)行讀碰撞，則對該序列號標(biāo)簽進(jìn)行讀/ /寫，然后使其進(jìn)入寫，然后使其進(jìn)入“無聲無聲”狀態(tài)。狀態(tài)。 （4 4）重復(fù)步驟（）重復(fù)步驟（3 3），多次重復(fù)后可完成電子標(biāo)簽交換數(shù)據(jù)工作。），多次重復(fù)后可完成電子標(biāo)簽交換數(shù)據(jù)工作。8.3 二進(jìn)制樹型搜索算法 如圖為動態(tài)的二進(jìn)制樹型搜索算法過程。如圖為動態(tài)的二進(jìn)制樹型搜索算法過程

54、。 NVB NVB表明請求命表明請求命令的有效位數(shù)。電子令的有效位數(shù)。電子標(biāo)簽返回的序列號只標(biāo)簽返回的序列號只是除了這些有效位之是除了這些有效位之后的部分，避免序列后的部分，避免序列號中多余部分的傳輸，號中多余部分的傳輸，要傳輸?shù)臄?shù)據(jù)數(shù)量和要傳輸?shù)臄?shù)據(jù)數(shù)量和所需時間的減少可達(dá)所需時間的減少可達(dá)50%50%。8.3 二進(jìn)制樹型搜索算法n基于隨機(jī)數(shù)和時隙的二進(jìn)制樹搜索 該算法采用遞歸的工作方式，遇到碰撞就進(jìn)行分支，成為兩個該算法采用遞歸的工作方式，遇到碰撞就進(jìn)行分支，成為兩個子集。這些分支越來越小，直到最后分支下面只有一個信息包或者子集。這些分支越來越小，直到最后分支下面只有一個信息包或者為空。分

55、支的方法就如同拋一枚硬幣一樣，將這些信息包隨機(jī)地分為空。分支的方法就如同拋一枚硬幣一樣，將這些信息包隨機(jī)地分為兩個分支，在第一個分支里，是為兩個分支，在第一個分支里，是“拋正面拋正面”（取值為（取值為0 0）的信息包。）的信息包。在接下來的時隙內(nèi)，主要解決這些信息包所發(fā)生的碰撞。如果再次在接下來的時隙內(nèi)，主要解決這些信息包所發(fā)生的碰撞。如果再次發(fā)生碰撞，則繼續(xù)再隨機(jī)地分為兩個分支。該過程不斷重復(fù)，直到發(fā)生碰撞，則繼續(xù)再隨機(jī)地分為兩個分支。該過程不斷重復(fù)，直到某個時隙為空或者成功完成一次數(shù)據(jù)傳輸，然后返回上一個分支。某個時隙為空或者成功完成一次數(shù)據(jù)傳輸，然后返回上一個分支。這個過程遵循這個過程遵

56、循“先入后出先入后出” ” 的原則，等到所有第一個分支的信息包都的原則，等到所有第一個分支的信息包都成功傳輸后，再來傳輸?shù)诙€分支，也就是成功傳輸后，再來傳輸?shù)诙€分支，也就是“拋反面拋反面”（取值為（取值為1 1）的）的信息包。此算法不要求電子標(biāo)簽需準(zhǔn)確同步。信息包。此算法不要求電子標(biāo)簽需準(zhǔn)確同步。 這種算法稱為這種算法稱為樹型搜索算法樹型搜索算法，每次分割使搜索樹增加一層分支。，每次分割使搜索樹增加一層分支。8.3 二進(jìn)制樹型搜索算法 如圖所示為四層（如圖所示為四層（m m=4=4）樹算法的原理示意圖。每個頂點表示一）樹算法的原理示意圖。每個頂點表示一個時隙，每個頂點為后面接著的過程產(chǎn)生子集。如果該頂點包含的個時隙，每個頂點為后面接著的過程產(chǎn)生子集。如果該頂點包含的信息包個數(shù)大于或等于信息包個數(shù)大于或等于2 2，那么就產(chǎn)生碰撞，于是就產(chǎn)生了兩個新的，那么就產(chǎn)生碰撞，于是就產(chǎn)生了兩個新的分支。算法從樹的根部開始，在解決這些碰撞的過程中，假設(shè)沒有分支。算法從樹的根部開始，在解決這