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

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

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

3、稱為）另一類稱為多讀寫器碰撞問題多讀寫器碰撞問題，即相鄰的讀寫器在其信號(hào)，即相鄰的讀寫器在其信號(hào)交疊區(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)相鄰的讀寫器作用范圍有重疊時(shí)，多個(gè)讀寫器同時(shí)讀取同一當(dāng)相鄰的讀寫器作用范圍有重疊時(shí)，多個(gè)讀寫器同時(shí)讀取同一個(gè)標(biāo)簽時(shí)可能會(huì)引起多讀寫器與標(biāo)簽之間的干擾。如圖標(biāo)簽同時(shí)收個(gè)標(biāo)簽時(shí)可能會(huì)引起多讀寫器與標(biāo)簽之間的干擾。如圖標(biāo)簽同時(shí)收到到3 3個(gè)讀寫器的信號(hào)，標(biāo)簽無法正確解析讀寫器發(fā)來的查詢信號(hào)。個(gè)讀寫器的信號(hào)，標(biāo)簽無法正確解析讀

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

5、別命令后，在標(biāo)簽應(yīng)答過程中可能會(huì)兩個(gè)或者多個(gè)標(biāo)簽同一時(shí)刻應(yīng)答，或一個(gè)標(biāo)簽還沒有完程中可能會(huì)兩個(gè)或者多個(gè)標(biāo)簽同一時(shí)刻應(yīng)答，或一個(gè)標(biāo)簽還沒有完成應(yīng)答時(shí)其他標(biāo)簽就做出應(yīng)答。它會(huì)使得標(biāo)簽之間的信號(hào)互相干成應(yīng)答時(shí)其他標(biāo)簽就做出應(yīng)答。它會(huì)使得標(biāo)簽之間的信號(hào)互相干擾，從而造成標(biāo)簽無法被正常讀取。本章后續(xù)討論的防碰撞都是針擾，從而造成標(biāo)簽無法被正常讀取。本章后續(xù)討論的防碰撞都是針對(duì)多標(biāo)簽防碰撞。對(duì)多標(biāo)簽防碰撞。8.1 RFID系統(tǒng)中的碰撞與防碰撞nRFID系統(tǒng)中防碰撞算法分類 電子標(biāo)簽的低功耗、低存儲(chǔ)能力和有限的計(jì)算能力等限制，導(dǎo)電子標(biāo)簽的低功耗、低存儲(chǔ)能力和有限的計(jì)算能力等限制，導(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)簽之間傳輸信息的比特?cái)?shù)目；器和標(biāo)簽之間傳輸信息的比特?cái)?shù)目； （3 3）標(biāo)簽不具備檢測(cè)沖突的功能而且標(biāo)簽間不能相互通信，因此）標(biāo)

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

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

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

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

11、。頻率的信號(hào)進(jìn)行分離，從而實(shí)現(xiàn)對(duì)不同標(biāo)簽的識(shí)別。 頻分多路法的缺點(diǎn)是導(dǎo)致讀寫器和標(biāo)簽成本要求較高。因此在頻分多路法的缺點(diǎn)是導(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ò)頻與多址兩個(gè)基本概念。包含擴(kuò)頻與多址兩個(gè)基本概念。擴(kuò)頻擴(kuò)頻目的是擴(kuò)展信息目的是擴(kuò)展信息帶寬，即把需發(fā)送的具有一定信號(hào)帶寬的信息數(shù)據(jù)，用一個(gè)帶寬遠(yuǎn)帶寬，即把需發(fā)送的具有一定信號(hào)帶寬的信息數(shù)據(jù)，

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

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

14、的信號(hào)在不同的時(shí)間內(nèi)傳輸，將整個(gè)傳輸時(shí)間分為許多時(shí)間間隔，每個(gè)號(hào)在不同的時(shí)間內(nèi)傳輸，將整個(gè)傳輸時(shí)間分為許多時(shí)間間隔，每個(gè)時(shí)間片被一路信號(hào)占用。時(shí)間片被一路信號(hào)占用。 TDMATDMA就是通過在時(shí)間上交叉發(fā)送每一路信號(hào)的一部分來實(shí)現(xiàn)一就是通過在時(shí)間上交叉發(fā)送每一路信號(hào)的一部分來實(shí)現(xiàn)一條電路傳輸多路信號(hào)的。電路上每一短暫時(shí)刻只有一路信號(hào)存在。條電路傳輸多路信號(hào)的。電路上每一短暫時(shí)刻只有一路信號(hào)存在。因?yàn)閿?shù)字信號(hào)是有限個(gè)離散值，所以時(shí)分多路復(fù)用技術(shù)廣泛應(yīng)用于因?yàn)閿?shù)字信號(hào)是有限個(gè)離散值，所以時(shí)分多路復(fù)用技術(shù)廣泛應(yīng)用于包括計(jì)算機(jī)網(wǎng)絡(luò)在內(nèi)的數(shù)字通信系統(tǒng)。包括計(jì)算機(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)簽防碰撞算法大多采用時(shí)分多路法，該方法可分系統(tǒng)的標(biāo)簽防碰撞算法大多采用時(shí)分多路法，該方法可分為非確定性算法和確定性算法。為非確定性算法和確定性算法。 非確定性算法非確定性算法也稱標(biāo)簽控制法，在該方法中，讀寫器沒有對(duì)數(shù)也稱標(biāo)簽控制法，在該方法中，讀寫器沒有對(duì)數(shù)據(jù)傳輸進(jìn)行控制，標(biāo)簽的工作是非同步的，標(biāo)簽獲得處理的時(shí)間不據(jù)傳輸進(jìn)行控制，標(biāo)簽的工作是非同步的，標(biāo)簽獲得處理的時(shí)間不確定，因此標(biāo)簽存在確定，因此標(biāo)簽存在“饑餓饑餓”問題。問題。ALOHAALOHA算法算法是一種典型的

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

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

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

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

20、作區(qū)內(nèi)的標(biāo)簽后，進(jìn)入到休眠狀態(tài)，直到讀寫器識(shí)別出所有在其工作區(qū)內(nèi)的標(biāo)簽后，算法過程才結(jié)束。算法過程才結(jié)束。8.2 ALOHA算法n純ALOHA算法 純純ALOHAALOHA算法中的信號(hào)碰撞分兩種情況：算法中的信號(hào)碰撞分兩種情況： （1 1）一種是信號(hào)部分碰撞，即信號(hào)的一部分發(fā)生了沖突；）一種是信號(hào)部分碰撞，即信號(hào)的一部分發(fā)生了沖突； （2 2）一種則是信號(hào)的完全碰撞，是指數(shù)據(jù)完全發(fā)生了沖突。）一種則是信號(hào)的完全碰撞，是指數(shù)據(jù)完全發(fā)生了沖突。如圖所示，如圖所示，發(fā)生沖突的數(shù)據(jù)都無法被讀寫器所識(shí)別。發(fā)生沖突的數(shù)據(jù)都無法被讀寫器所識(shí)別。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時(shí)，最大吞吐率時(shí)，最大吞吐率S S=1/(2e)18.4%=1/(2e)18.4%。發(fā)送幀不會(huì)產(chǎn)生碰撞。發(fā)送幀不會(huì)產(chǎn)生碰撞（即發(fā)送成功）的概率（即發(fā)送成功）的概率P P為為 電子標(biāo)簽數(shù)量越多，幀時(shí)越長(zhǎng)，則電子標(biāo)簽數(shù)量越多，幀時(shí)越長(zhǎng)，則G G越大，發(fā)送成功的概率越低。越大，發(fā)送成功的概率越低。 純純ALOHAALOHA算法雖然算法簡(jiǎn)單，易于實(shí)現(xiàn)。但對(duì)于同一個(gè)標(biāo)簽，算法雖然算法簡(jiǎn)單，易于實(shí)現(xiàn)。但對(duì)于同一個(gè)標(biāo)簽，如果連續(xù)多次發(fā)生碰撞，這將導(dǎo)致讀寫器出現(xiàn)錯(cuò)誤判斷認(rèn)為這個(gè)標(biāo)如果連續(xù)多次發(fā)

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

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

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

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

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

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

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

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

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

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

32、的次數(shù)（空閑時(shí)隙數(shù)）來估計(jì)當(dāng)前未被正確識(shí)別的電子標(biāo)簽據(jù)信息的次數(shù)（空閑時(shí)隙數(shù)）來估計(jì)當(dāng)前未被正確識(shí)別的電子標(biāo)簽數(shù)目，然后選擇最佳的下一幀的長(zhǎng)度，把它的幀長(zhǎng)度作為下一輪識(shí)數(shù)目，然后選擇最佳的下一幀的長(zhǎng)度，把它的幀長(zhǎng)度作為下一輪識(shí)別的幀長(zhǎng)，直到讀寫器工作范圍內(nèi)的電子標(biāo)簽全部識(shí)別完畢。別的幀長(zhǎng)，直到讀寫器工作范圍內(nèi)的電子標(biāo)簽全部識(shí)別完畢。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ù)量，直到只有一個(gè)電子標(biāo)簽進(jìn)

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

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

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

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

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

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

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

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

41、樹型搜索算法?，F(xiàn)以讀寫器作用下面以一個(gè)實(shí)例來說明二進(jìn)制樹型搜索算法。現(xiàn)以讀寫器作用范圍內(nèi)的四個(gè)電子標(biāo)簽為例說明搜索的過程。這四個(gè)電子標(biāo)簽的序范圍內(nèi)的四個(gè)電子標(biāo)簽為例說明搜索的過程。這四個(gè)電子標(biāo)簽的序列號(hào)（這里用列號(hào)（這里用8 8位的序列號(hào)舉例）分別為：位的序列號(hào)舉例）分別為： 電子標(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）命令。序列號(hào)）命令。序列號(hào)1111111111111111，是本例中系統(tǒng)最大，是本例中系統(tǒng)最大可能的可能的8 8位序列號(hào)。讀寫器作用范圍內(nèi)的所有電子標(biāo)簽的序列號(hào)都應(yīng)位序列號(hào)。讀寫器作用范圍內(nèi)的所有電子標(biāo)簽的序列號(hào)都應(yīng)小于或等于小于或等于1111111111111111，因此，處于讀寫器作用范圍內(nèi)的所有電子標(biāo)，因此，處于讀寫器作用范圍內(nèi)的所有電子標(biāo)簽都應(yīng)對(duì)該命令作出應(yīng)答。簽都應(yīng)對(duì)該命令作出應(yīng)答。8.3 二進(jìn)制樹型搜索算法3二進(jìn)制樹型搜索算法實(shí)例 二進(jìn)制樹型搜索算法選擇電子標(biāo)簽的迭代過程如圖。二進(jìn)制樹

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

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

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

46、做出應(yīng)答的是電子標(biāo)簽例中，做出應(yīng)答的是電子標(biāo)簽1 1、2 2和和3 3（見第二次迭代）。（見第二次迭代）。現(xiàn)在接收的序列號(hào)的第現(xiàn)在接收的序列號(hào)的第0 0位和第位和第4 4位上出現(xiàn)了碰撞（位上出現(xiàn)了碰撞（x x）。由此得出）。由此得出結(jié)論：在第二次迭代的搜索范圍內(nèi)，至少還存在有兩個(gè)電子標(biāo)簽。結(jié)論：在第二次迭代的搜索范圍內(nèi)，至少還存在有兩個(gè)電子標(biāo)簽。需要進(jìn)一步確定的序列號(hào)有四種可能性。需要進(jìn)一步確定的序列號(hào)有四種可能性。 檢 索 命 令 第一次迭代：范圍= 第n次迭代：范圍= 請(qǐng)求（REQUEST）范圍 0 位（x）=1，位（0 x1）=0請(qǐng)求（REQUEST）范圍 序列號(hào)（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ú)對(duì)命令作出應(yīng)）能滿足此條件，該電子標(biāo)簽即單獨(dú)對(duì)命令作出應(yīng)答答（見第三次迭代）。（見第三次迭代）。

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

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

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

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

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

53、新的查詢信息。發(fā)出查查詢條件的位數(shù)為詢條件的位數(shù)為N NXX，滿足查詢條件的電子標(biāo)簽回傳的信號(hào)只是，滿足查詢條件的電子標(biāo)簽回傳的信號(hào)只是序序列號(hào)中最高碰撞位后的數(shù)，即列號(hào)中最高碰撞位后的數(shù)，即XX1 10 0位。若標(biāo)簽返回信號(hào)沒有發(fā)位。若標(biāo)簽返回信號(hào)沒有發(fā)生生碰撞，則對(duì)該序列號(hào)標(biāo)簽進(jìn)行讀碰撞，則對(duì)該序列號(hào)標(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)制樹型搜索算法 如圖為動(dòng)態(tài)的二進(jìn)制樹型搜索算法過程。如圖為動(dòng)態(tài)的二進(jìn)制樹型搜索算法過程

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

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

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