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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、作區(qū)內的標簽后，進入到休眠狀態(tài)，直到讀寫器識別出所有在其工作區(qū)內的標簽后，算法過程才結束。算法過程才結束。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之間的關系為之間的關系為 當當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為為 電子標簽數(shù)量越多，幀時越長，則電子標簽數(shù)量越多，幀時越長，則G G越大，發(fā)送成功的概率越低。越大，發(fā)送成功的概率越低。 純純ALOHAALOHA算法雖然算法簡單，易于實現(xiàn)。但對于同一個標簽，算法雖然算法簡單，易于實現(xiàn)。但對于同一個標簽，如果連續(xù)多次發(fā)生碰撞，這將導致讀寫器出現(xiàn)錯誤判斷認為這個標如果連續(xù)多次發(fā)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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