RFID系統(tǒng),研究趨勢和挑戰(zhàn)_第八章

1、Tree-Based Anti-Collision Protocols for RFID Tags8.1 Introduction8.2 Principles of Tree-Based Anti-Collision Protocols8.3 Tree Protocols in the Existing RFID Specifications8.4 Practical Issues and Transmission Errors8.5 Cooperative Readers and Generalized Arbitration Spaces8.6 ConclusionRFID中基于樹型的防碰

2、撞協(xié)議8.1 整體介紹8.2 基于樹型的防碰撞協(xié)議的原則8.3 在現(xiàn)存FRID規(guī)范中的樹型協(xié)議8.4 實際中的問題和發(fā)送中的錯誤8.5合作的閱讀器和通常的仲裁空間8.6 總結RFID系統(tǒng)主要由系統(tǒng)主要由閱讀器閱讀器和和標簽標簽組成組成系統(tǒng)構建閱讀器（閱讀器（Reader）標簽（標簽（Tag）被動式標簽（被動式標簽（Passive Tag）：因內部沒有電源設備又被稱為無源標簽無源標簽。內部的集成電路通過接收由閱讀器發(fā)出的電磁波進行驅動，向閱讀器發(fā)送數(shù)據(jù)。主動標簽（主動標簽（Active Tag）:因標簽內部攜帶電源又被稱為有源標簽有源標簽（電池供（電池供電的具有非常低的功耗標記）電的具有非常低的

3、功耗標記）。也被稱為詢問器，收發(fā)器，是能夠與標簽通信，能從標簽讀出信息或將信息寫入其中。半主動標簽（半主動標簽（Semi-active Tag）:使用電池，用于感測/加工，但不用于通信標簽分類 讀寫器發(fā)送一個探測幀，根據(jù)探測幀的內容，標簽決定是否回應。如果多個回復同時到達讀寫器，這時就發(fā)生標簽碰撞，導致閱讀器無法讀取。注意，標簽碰撞問題發(fā)生在閱讀器處。如果一個標簽在多個閱讀器的范圍內，兩個或多個閱讀器同時發(fā)送信息，導致這個標簽無法正確收到任何一個閱讀器的信息，就發(fā)生閱讀器碰撞。通信模式標簽碰撞閱讀器碰撞兩種碰撞 標簽碰撞通過防碰撞協(xié)議來解決。仲裁協(xié)議的目的是劃分每個標簽的發(fā)送時間(也就是進行時

4、間調度)，使得最終每個標簽能成功發(fā)送回復。另外，仲裁協(xié)議并不徹底解決碰撞，而是解決可能需要的部分沖突。 閱讀器碰撞成為一個在閱讀器密度較高時的重要問題，主要在于要合理分配通信資源（時間，頻率），以減少它們之間的干擾。解決辦法 本章將介紹一類基于二進制樹的防碰撞協(xié)議。這種協(xié)議用在多址接入的單信道中，一個閱讀器收到來自多個標簽的回復。本質上，在遇到碰撞時該協(xié)議遞歸地解決碰撞，直到所有的標簽成功發(fā)送回復給閱讀器。 碰撞樹型協(xié)議 我們假設一個標簽在距離一個閱讀器為D的范圍內，那它將無差錯地收到來自閱讀器的請求幀。它的數(shù)據(jù)包也將成功地被閱讀器接收。多址接入的信道模型，就意味著如果多個標簽同時在閱讀器的接

5、受范圍內傳送信息，那閱讀器將不會正確收到任何傳輸來數(shù)據(jù)包。 K個標簽在同一時隙發(fā)送數(shù)據(jù)，閱讀器在該時隙感受到的信道為：閑置（I） 如果K=0 沒響應成功響應（S） 如果K=1沖突（C） 如果K1 系統(tǒng)模型系統(tǒng)模型時隙1：標簽 同時發(fā)送，發(fā)生碰撞時隙2：標簽 同時發(fā)送，發(fā)生碰撞時隙3：沒有標簽發(fā)送，空閑時隙4：標簽 發(fā)送，成功 如圖，一個標簽只有在閱讀器發(fā)送請求幀時才會發(fā)送應答幀，在接收到請求幀1后，標簽 發(fā)送應答幀。如果兩個標簽同時發(fā)送數(shù)據(jù)，那他們的數(shù)據(jù)將發(fā)生碰撞，然后閱讀器將在下一請求幀中向標簽做出反饋。閱讀器發(fā)出請求幀2時，便攜帶了上一時隙結果（此處為沖突）的反饋信息給標簽。1231112

6、23系統(tǒng)模型 如果沒有發(fā)生錯誤，仲裁協(xié)議的效率將用發(fā)送時間和信息量來衡量。如果這里有n個標簽，我們關心識別所有標簽的平均時間 。定義為一個隨機變量 ，它代表執(zhí)行仲裁算法的一個特定實例所消耗的時間，包含兩個部分， 1.用來發(fā)送請求幀， 2.用于標簽發(fā)送數(shù)據(jù)。 我們假設閱讀器發(fā)送請求幀的時間為零，而只關注標簽發(fā)送數(shù)據(jù)的時隙。由于請求幀不消耗時間，則一個仲裁協(xié)議的執(zhí)行效率被定義為效率： nTnTnnTn基本樹型協(xié)議 基于樹型的協(xié)議已成為一個解決共享媒介多址接入問題的方法。一個閱讀器發(fā)送一個請求幀給標簽并要求標簽做出回復。由于閱讀器并不知道標簽的ID，于是它在請求幀中要求標簽做出回復，但未指定具體是哪

7、個標簽。因此多個標簽都有資格發(fā)送回復。檢測到?jīng)_突后，閱讀器知道至少有兩個標簽發(fā)送了回復。由于閱讀器仍不知道這些標簽的數(shù)量和ID，于是就采用隨機選擇的方法。沖突之后，每個標簽都要投擲一枚硬幣來產(chǎn)生一個0或1，閱讀器在下一幀時只要求產(chǎn)生只為0（或者為1）的標簽發(fā)送回復。這個過程將持續(xù)直到兩個標簽產(chǎn)生不同的隨機數(shù)。 我們定義碰撞重合度為檢測到?jīng)_突時發(fā)送數(shù)據(jù)的標簽數(shù)量；節(jié)點的深度代表節(jié)點離根節(jié)點的距離；每一個節(jié)點都有唯一的一個與之相關聯(lián)的字符串，稱為地址。如果屬于某個時隙 的標簽被允許發(fā)送數(shù)據(jù)，就表明在這個時隙 一個地址 （節(jié)點）被啟用（使能）。isis 基本樹型協(xié)議 在時隙 ，根節(jié)點（深度為0）啟用

8、，所有8個標簽都發(fā)送數(shù)據(jù)，閱讀器檢測到碰撞。根節(jié)點的地址為空，用表示。每個標簽投擲一枚硬幣，在此情況下， 得到0。在時隙 ，根節(jié)點的左側子節(jié)點被啟用， 被允許發(fā)送數(shù)據(jù)。注意此時在時隙 啟用的節(jié)點的深度為1且地址為0。標簽 - 在 時隙 投擲出1，屬于深度為1的另一個節(jié)點（地址為1）。在時隙 發(fā)生沖突后，標簽 再一次投擲硬幣，只有 得到0， 得到1。因此當?shù)刂窞?0的節(jié)點被啟用，只有 發(fā)送數(shù)據(jù)且被閱讀器正確接收。在一次正確傳輸之后，在時隙 同深度的另一個地址為01的節(jié)點被啟用。1S2s4812s3214s 基本樹型協(xié)議閱讀器端算法標簽端算法基本樹型協(xié)議 該算法的一個好處

9、是自組織為每個標簽分配地址。也就是說，通過這次沖突解決，閱讀器以后可以實現(xiàn)和特定的標簽進行通信。閱讀器可以通過分配給標簽一個短地址代替完整的地址，這個短地址是標簽被成功識別時所在的樹節(jié)點的地址。例如圖中標簽 的自組織短地址是011.3改進的樹型協(xié)議（1） 如果一些節(jié)點對應兩個以上的標簽，那么這個節(jié)點被啟用時必然導致沖突，所以這些節(jié)點應當在樹遍歷時被跳過。如，在經(jīng)歷過一個沖突時隙和一個空閑時隙 之后，地址為111的節(jié)點將產(chǎn)生沖突，因此在空閑幀 之后，標簽應該立即投擲一枚硬幣，時隙 應該從地址1110開始。這個算法被稱為修正二叉樹（MBT）。12s13s11S12s改進的樹型協(xié)議（2） 在早期，研

10、究者認為知道沖突重合度可以加速解決沖突。Capetanakis在研究中發(fā)現(xiàn)二進制樹型算法在解決小沖突重合度非常有效，應用這個發(fā)現(xiàn)，他設計了 一種針對響應的標簽數(shù)量呈泊松分布的動態(tài)樹型協(xié)議。第一步致力于估計沖突重合度。在得到?jīng)_突重合度后開始第二步，將未識別的標簽隨機分為若干組，然后在每組中使用基本樹型協(xié)議。附：這個分布是泊松研究二項分布的漸近公式是時提出來的。泊松分布P ()中只有一個參數(shù) ，它既是泊松分布的均值，也是泊松分布的方差。在實際事例中，當一個隨機事件，例如某電話交換臺收到的呼叫、來到某公共汽車站的乘客、某放射性物質發(fā)射出的粒子等，以固定的平均瞬時速率 (或稱密度)隨機且獨立地出現(xiàn)時，

11、那么這個事件在單位時間（面積或體積）內出現(xiàn)的次數(shù)或個數(shù)就近似地服從泊松分布。因此泊松分布在管理科學，運籌學以及自然科學的某些問題中都占有重要的地位。改進的樹型協(xié)議（3） 考慮到隨機接入的標簽發(fā)送時呈泊松分布，于是每當有一個沖突和連續(xù)兩次成功傳輸發(fā)生時，樹就裁剪，因此稱為裁剪樹型協(xié)議（CBT）。例如，在CBT算法中，開始于時隙 終止于 ，導致三個標簽被識別。閱讀器注意到三個標簽選擇了0，因此最初選擇1的標簽的數(shù)量的預估值為3。這意味著啟動地址為1的節(jié)點 （深度為1的節(jié)點）很有可能產(chǎn)生沖突，因此應該啟用一個更深的節(jié)點，如啟動地址為10（深度為2）的節(jié)點，于是就跳過了深度為1的節(jié)點，一個時隙就被省了

12、下來。1s6s樹型仲裁算法的框架假設在發(fā)送初始化幀時，每一個標簽隨機生成一個實數(shù)，均勻分布在0,1)之間，這個隨機數(shù)被認為是一種標識，用 表示標簽 生成的標識。用 =（ .）來表示 分數(shù)部分的二進制形式，那么每一個 都是一個無限長的二進制串并且： 可以被理解為一個無限長的隨機二進制串，來存儲每一個以0.5的概率生成的 （0或1）。iriix321iiixxxiririjxir 例如，在一開始的碰撞之后，地址為0的結點被激活，因此所有節(jié)點中只有生成隨機數(shù)在0,0.5)之間的結點才能做出響應。依此類推。在圖中，用一個確定的地址來激活樹結點，相當于使生成隨機數(shù)在0,1)的某個子區(qū)間的標簽使能。例如：

13、當?shù)刂窞?0時，在時隙 把生成隨機數(shù)位于0.5,0.75)區(qū)間的節(jié)點激活，讓其傳輸。一般地，如果節(jié)點的地址為： ，當它被激活時，相當于使能生成隨機數(shù)位于b,c)區(qū)間的結點。其中：8skaaaa.21一個長方形標示對應時隙的使能區(qū)間，陰影部分表示沖突，長方形被標記為 表示在對應的使能區(qū)間僅包含標簽 。ii 樹型仲裁算法的框架 在一次CBT算法的實例終止之后，我們可以得到標簽數(shù)量n對應的估計值 ，我們可以通過這個值來得出還有多少個標簽需要處理。 如：在前六個時隙中，第一次CBT實例結束之后，閱讀器在使能區(qū)間0,0.5)發(fā)現(xiàn)了三個標簽，如果n是在使能區(qū)間0,1)的標簽個數(shù)，在0,0.5)區(qū)間的標簽的

14、期望數(shù)為k = 0.5n，由于k=3，我們可以估計 = k/0.5=6，因此在未處理區(qū)間0.5,1)的標簽期望個數(shù)為3。第二次CBT算法在標簽 被處理后結束，這時,閱讀器發(fā)現(xiàn)有5個標識位于區(qū)間0,0.75)，這樣就可以得出初始的標簽總數(shù)為： =5/0.75=6.67，然而其他待識別的位于0.75, 1）標簽個數(shù)的估計值為(5/0.75)*0.25=1.67。 n n n 5 樹型仲裁算法的框架 通常，假設k個已處理的標簽，并且其標識位于區(qū)間0,p)，然后有n-k個未處理標簽，其標識位于區(qū)間p,1)?？紤]到標識的生成過程,閱讀器可以預測：在n（n為未知數(shù)）個均勻分布在0,1)區(qū)間的標識中，有k個

15、標識位于0,p)，那么出現(xiàn)以上事件的概率為 ： 對于給定的k，p，我們可以得到最大似然估計值：它不一定是整數(shù)，但這個估計值是準確的，因為E |n = n，然而它的誤差為： 在仲裁程序執(zhí)行過程中，p的值會逐漸增大，這會使得方差Var |n減小，因此得到的估計值會越來越精確。n n 樹型仲裁算法的框架 利用基于生成標識的架構，研究員制定了幾套仲裁協(xié)議，每一個協(xié)議處理沖突都比傳統(tǒng)的二叉樹協(xié)議快，特別是區(qū)間估計解決沖突(IECR)被認為是最快的沖突解決方案。讓我們假設在一次CBT實例終止時，觀察k個標志在0,p)解析?；趯ε鲎仓睾隙鹊墓烙?，下一個啟用區(qū)間為p,p+ p)。如果檢測到?jīng)_突，啟動一個新

16、的CBT實例并重復該過程。如果在p,p+ p)只有一個標記或無標記，那么把下一個時隙為作為這次CBT的終止時隙，并且重新估計/啟用新的區(qū)間。 IECR的速度相關于CBT實例終止后對使能區(qū)間長度的優(yōu)化選擇。IECR解決碰撞的速度漸進等價于對用于對泊松分布的先到先得（FCFS）樹型算法。當n很大時，第二啟用區(qū)間的長度應該是： ，其中k是一個CBT實例終止后的在區(qū)間0,p)上識別標簽數(shù)量。其時間效率為： kp26. 1樹型仲裁算法的框架 由于一般區(qū)間a,b)限制為實數(shù)以及每一個實數(shù)都由無限長的二進制編碼來表示，使得RFID中的IECR算法不是直接實現(xiàn)的。如果沒有有限整數(shù)i,使得對于所有ji，有 =0

17、，那么一個 X 0,1)實數(shù)的二進制表示為X= .就為無限長。由于區(qū)間被描述成無限長的二進制數(shù)字，優(yōu)化選擇的長度p可能導致一些使能區(qū)間不能有效的包含在閱讀器發(fā)送的探測幀中。 另一種被稱為估計二叉樹(EBT)的算法更適用于RFID標簽。在EBT中，啟用的區(qū)間長度等于 ，其中L是一個整數(shù)。這樣選擇的好處是每個啟用的區(qū)間對應于在演化的二進制樹中的單一的結點，這樣可以使區(qū)間比較緊湊，使樹中的地址和實際區(qū)間相對應。一個CBT實例終止后，只需要決定如何選擇 L。最直接的方法，就是使獲取單一回復的可能性最大： 最后，一個關于標簽數(shù)量規(guī)模的先驗信息可以提高算法的效率。例如，如果已知標簽的數(shù)量 大于1，那么最初

18、的探測幀不需要啟用整個0,1)區(qū)間，可以從在區(qū)間0,1.26/ )開始。這種方法可以在初始階段避免發(fā)生碰撞，直到第一次CBT實例終止，并且產(chǎn)生第一個估計值 。 lxxx. 021minnminnjxn 數(shù)據(jù)說明 在IECR中，如果n先被告知，每個CBT實例終止后，就可以準確知道留在區(qū)間p,1)未解析的標簽數(shù)量?？梢钥闯鯡BT優(yōu)于MBT，MBT優(yōu)于基本的二進制樹算法。如果先不知道標簽數(shù)量規(guī)模，那么EBT和IECR的效率隨標簽數(shù)量的增加而提高。也可以看出EBT換取時間效率所付出的代價是和IECR相關的。有部分或全部關于n的信息，可以提高性能，當n為先驗已知的，效率隨n的增加而減少。這是因為標簽數(shù)量

19、較少時，先知道標簽數(shù)n比對剩于區(qū)間未解析的標簽數(shù)的估計更有價值。但先驗信息的優(yōu)勢會隨著n的增加而減少。 RFID規(guī)范中的樹型協(xié)議 兩種基于樹型的協(xié)議，用在EPCglobal第一代標簽中：Class 0和Class 1。 在許多應用中，第一代標簽和相關的協(xié)議已經(jīng)被第二代Class 1標簽所取代。除了這兩種協(xié)議，其他標準的樹型協(xié)議是ISO 18000-6AEPCglobal Class 0 協(xié)議 原來我們假設標簽能夠產(chǎn)生隨機數(shù)，當作標記用在防碰撞協(xié)議中。EPCglobal 0類標簽不用隨機數(shù)，而是依賴于每個標簽唯一的ID號。如果標簽的ID有L位比特，則ID 在【0，1）區(qū)間用二進制表示為 。 例如

20、，由于標簽 第一位比特都是0，在時隙 允許發(fā)送，而其他的標簽 的第一位為1.因此，我們可以推出 的ID是00.， 的ID 是1110.。lxxx.21lxxx.0212s8416321 EPCglobal Class 0 協(xié)議Class 0 協(xié)議用一位接一位的比特詢問應答：（1）閱讀器開始發(fā)送一個特殊的空序列，收到序列的標簽回復自己ID的第一位比特。（2）如果回復的比特都是0或者1，那么閱讀器接受到的就是0或者1。然后，閱讀器再發(fā)送下一位。（3）如果一些標簽發(fā)送的是0其他的標簽發(fā)送的是1，則閱讀檢測器同時能到0和1。接著它會隨機決定發(fā)送0或者1。（4）如果第一位和閱讀器發(fā)送的比特相同的標簽就發(fā)

21、送第二位比特，如果和閱讀器發(fā)送的比特不同的標簽就沉默，直到下一個特殊的空序列再開始發(fā)送。 例如：假設每個標簽有5位比特的地址，分別是X( ) = 00100, X( )=01010, X( ) = 01100. 代表 的地址，假設在時隙 后，閱讀器選擇發(fā)送一個0，在 后發(fā)送0，則標簽 發(fā)送 =1，同樣的方式發(fā)送 =0， =0。 在第五位被讀后， 就近入沉默。于是閱讀器再次發(fā)送空序列，之后收到了0和1，接著在下一時隙發(fā)送0，然后接收到1，于是再發(fā)送1，接著又接受0和1，再發(fā)送0，這樣就最后得到 的最后兩位。對剩下標簽的解析也用同樣的方式。123)(ixi11s2s4x5x123x EPCglob

22、al Class 0 協(xié)議注意：（1）沒有空閑時隙。因為這里沒有發(fā)生碰撞，而只是0和1的組合，閱讀器每次回傳的是在現(xiàn)在標簽里有的比特值。（2）實際上，每一個標簽默認處于睡眠狀態(tài)，閱讀器發(fā)送復位信號來喚醒它們。在復位信號以后，閱讀器發(fā)送一個標志序列使標簽標準化，只有標準化后，一個標簽才能接受到閱讀器的命令。（3）除了0和1，空序列以外，規(guī)范還定義了閱讀器發(fā)送的其他命令。注意，在復位/標準命令發(fā)送后才到達的標簽不能加入正在實行的樹型協(xié)議，需要等待下一組復位/標準命令。因此，為了能夠讀到后到達的標簽，閱讀器應該頻繁地發(fā)布標準化命令，這也影響了防碰撞協(xié)議的速度。（4）閱讀器用的短的命令（0，1，和空信

23、號）確保每一個標簽被解析后重新從樹的根開始遍歷。一般來說，短的閱讀器命令減少了樹形協(xié)議的靈活性。 EPCglobal Class 1 協(xié)議 Class 0 標簽的一個嚴重缺點是：他們是廠家寫的，因此這個協(xié)議不會預先考慮到在標簽里寫新數(shù)據(jù)。這也是引入Class 1 標簽主要原因之一。和Class 0 標簽不同，在Class 1中閱讀器發(fā)送命令數(shù)據(jù)包以及標簽回復整個數(shù)據(jù)包。每個讀取命令有一個同步序列。因此，在原則上，遲到的標簽可以加入仲裁協(xié)議。閱讀器命令里含更多內容使遍歷樹更加靈活，但代價是協(xié)議的單個時隙持續(xù)時間（含閱讀器命令和標簽應答）比Class 0長得多。 Class 1規(guī)范用提供的命令來支

24、持基于樹的協(xié)議，但不具體指定遍歷樹的方式。閱讀器可以使用PingID命令，這命令包括：一個指針【PTR】 ，它指向標簽標識符的一個位置（或位索引）和一個長度的位掩碼值【VALUE】。如果標簽ID中由【PTR】指示位置值和VALUE匹配，則有權回復請求幀。 EPCglobal Class 1 協(xié)議 例如，如果PTR = 1和位掩碼為“11 ”，那么ID是x11 的標簽（其中x可以是0或1） 就可以發(fā)送。但是，不是所有具和位掩碼匹配的標簽立刻發(fā)送一個應答。閱讀器在探測幀終止時構造8個容器，分別標記為000 ， 001 ， 010 ， 111 ?？梢院臀谎诖a匹配的標簽，使用其ID的下三位來決定是否發(fā)

25、送答復。 如，在一個位掩碼為X11探測幀發(fā)送后，地址x11010的標簽將在第三個容器發(fā)送回復。在這樣仲裁框架里，一個探測幀同時使能8個區(qū)間。此外，位掩碼集合適用于多重估計，如在EBT，也加快了標簽解析。 這兩個EPCglobal第一代的Class 0和Class 1類標簽，以及相關的仲裁協(xié)議，逐漸被第二代Class 1標簽取代，它使用ALOHA協(xié)議的一個變形。放棄這些樹型協(xié)議的一個主要原因是他們很難處理后來到達的標簽。令牌（標志）生成 上面描述的兩個實行樹協(xié)議的RFID，在標簽中不依賴產(chǎn)生的隨機數(shù)。但隨機比特位用于無源標簽不成問題，并已被用于基于ALOHA協(xié)議的第2代Class1 標簽中。因此

26、，基于樹的RFID協(xié)議的未來版本可以依靠隨機生成的比特而不是ID。從安全的角度來看也是重要的。如果ID標識位用于仲裁，則與標簽ID對應的令牌（標志）可能不均勻的分配在0,1）之間。當令牌均勻地分布在0，1）之間時，EBT比BT提供了更好的平均性能。否則，使用統(tǒng)計估計是無效的，且EBT可能比基本二進制樹協(xié)議更慢。 如：有五個標簽并且他們的ID在0.25，0.5）之間。如果用二進制樹的基本算法，那么當所有的標簽被解析了，下一個啟用的區(qū)間為0.5，1），這將導致一個空閑的響應，該算法將終止。相反，如果應用EBT，標簽被解析后，該算法繼續(xù)估計標簽的基數(shù)并使能比0. 5，1）小的區(qū)間，所以，它需要更多的

27、時間來終止仲裁協(xié)議。一個隨機化標簽標志的方法是閱讀器使用一個預先定義的隨機的比特位排列。這種排列可以用來在EBT算法開始之前打亂地址，從而隨機化在沖突解決中所用的前綴。傳輸錯誤 之前所描述的協(xié)議假設運行在沒有信道錯誤的情況下，但信道的錯誤以不同方式影響這些協(xié)議。可以將錯誤劃分為發(fā)生在標簽處和閱讀器處的錯誤。發(fā)生在標簽處的錯誤 在標簽處的錯誤導致標簽不能回復閱讀器。我們將MAC協(xié)議層上的錯誤分為兩種類型：靜態(tài)的錯誤和動態(tài)的錯誤。靜態(tài)錯誤發(fā)生在整個沖突解決期間，標簽處在一個“盲點”（盲點就是該標簽在閱讀器的范圍以外），所以在整個會話中標簽沒有收到請求幀。設 表示發(fā)生靜態(tài)誤差的概率。另一方面，由于動

28、態(tài)錯誤，使得由閱讀器發(fā)送的每個請求幀以概率（1- ）被標簽正確接收，以概率 不能正確接收。從物理層角度來看，靜態(tài)錯誤由信號深度失真造成，而動態(tài)誤差是由噪聲引起的。標簽 靜態(tài)（動態(tài)）誤差的概率表示為 ( )。通常當i j時，每個 并且 。 spdpdpidipsipsjpdjpsipdip發(fā)生在標簽處的錯誤 靜態(tài)錯誤對協(xié)議的影響是簡單的，標簽不參與閱讀器的會話。有人可能會認為，出現(xiàn)靜態(tài)錯誤時，標簽處于“盲點“-距離閱讀器近但鏈路質量卻很差。如果一個標簽在一個會話中的盲點并不一定意味著該標簽處于另一個會話的盲點，并且標簽可以移動。 在圖中，標簽 不在閱讀器 的范圍中，而在閱讀器 的范圍中。4ARB

29、R發(fā)生在標簽處的錯誤 動態(tài)錯誤對樹型協(xié)議的影響較為復雜。假設閱讀器實行基本樹型協(xié)議，沒有任何由MBT引進的估計或優(yōu)化。如圖，假設標簽 在時隙 中沒有正確地收到探測幀，而是在時隙 正確收到了探測幀。因此，閱讀器觀察到一個空閑時隙 ?？梢则炞C，沖突解決會話結束，這個標簽不會收到一個請求幀可以使它有資格發(fā)送一個回復。閱讀器認為區(qū)間0，0.5）為已解決，然而處于該區(qū)間的的標簽 卻未解析。注意，在無差錯的情況下一個未解決的標簽是不可能收到一個請求幀通知它其所屬的區(qū)間已被解析。336s6s7s發(fā)生在標簽處的錯誤 有兩種方法可以來減小動態(tài)錯誤的影響。 第一種方法：即使區(qū)間0，p）已認為被解決，閱讀器仍然啟用

30、這個區(qū)間或詢問它的一些子區(qū)間是否有剩下的標簽。 第二個方法：如果令牌在0，p）區(qū)間的標簽還沒有被解析，而閱讀器發(fā)出信號認為已經(jīng)解決了區(qū)間0，p），那么這個標簽就再次生成令牌，均勻分布在P，1）區(qū)間。 第二個方法表明在帶有啟動區(qū)間的框架（如IECR或EBT）中的估計需要改變，由于未解決的區(qū)間在統(tǒng)計學上不同于已解決的區(qū)間。另外，如果只是的基于標志不同，則重新生成的標志可能導致無法解決的沖突。例如， 為 .， 為 .，也就是說，它們僅在第一位不同。如果標簽 在區(qū)間0,0.5）錯過了，可在0. 5，1）再生成令牌，忽略第一位。然而，這樣做意味著它在碰撞解析過程中不能與 區(qū)分。因此，閱讀器重新啟用一些先

31、前已被解決的區(qū)間會更加合適。 1321 xx2320 xx12發(fā)生在標簽處的錯誤 基本二進制樹算法對標簽處的錯誤是健壯的，然而標簽處的錯誤對改進的二叉樹來說是很嚴重的。如，有兩個標簽 ，令牌分別為 = 0.1和 = 0.2。假設第一個使能0,1）區(qū)間的請求幀被 和 正確接收，隨后閱讀器檢測到碰撞。接下來，產(chǎn)生第二個使能0,0.5）區(qū)間的請求幀，其中一個標簽沒有收到。一種情況：MBT算法將進入無盡的會話，閱讀器從0.25,0.5) 開始使能越來越小的子區(qū)間,但只得到空閑回答。另一種情況：如果一個有估計的樹型算法被應用，例如EBT（不使用MBT），算法對錯誤也表現(xiàn)健壯,但估計不會那么精確。1122

32、1r2r發(fā)生在標簽處的錯誤 對于靜態(tài)錯誤,閱讀器錯過一個標簽的概率是 動態(tài)錯誤以概率 發(fā)生,錯過一個標簽的可能性與 沒有直接的關系。如：有兩個標簽，令牌分別是 在【0，0.5)， 在【0.5，1）。用 表示標簽 沒有在會話中被閱讀器讀到。假設兩個標簽發(fā)生動態(tài)錯誤的概率是相同的。 表示 被錯過， 被成功讀取的概率。 兩個標簽都被錯過的概率由 給出: spdpdp12ii21rp1221rP 第一個 是兩個標簽的都沒有收到使能【0,1)區(qū)間的探測幀。第二個式子表示兩個標簽都收到了第一個探測幀，但 沒有收到使能【0，0.5)區(qū)間的探測幀， 沒有收到使能【0.5，1）區(qū)間的探測幀。用類似的方式,可以得

33、到以下的概率：2dP12發(fā)生在標簽處的錯誤 錯過的邊緣概率為： 1在 錯過條件下 錯過的概率：12 這與 顯然是不相同的。從中可以看出，如果遍歷樹的層次越深,也就是使能區(qū)間越小，那么標簽被錯過的幾率會越小。這是因為對于一個深度較大的樹, 更多的請求幀會到達標簽，因此標簽回應的機會也較高。以此我們可以預測，樹型協(xié)議處理發(fā)生在簽處的錯誤比較可靠，因為這些協(xié)議使用請求幀較多,正好與ALOHA協(xié)議發(fā)送相對較少的請求幀的方式相反。1rP發(fā)生在閱讀器處的錯誤 閱讀器不理想的接收會導致在閱讀器處對信道狀態(tài)產(chǎn)生錯誤的解釋。如，如果只有一個標簽發(fā)送, 閱讀器沒有收到正確的包，它可能被解釋為空閑(不夠接收功率)或

34、碰撞(傳輸存在,但不是可解碼)。下圖顯示了發(fā)生在閱讀器處的錯誤模型。 代表通道u被視為通道v的概率。在理想情況中我們認為 = 1 且 = 0 ，如果 。假設沒有發(fā)送時卻產(chǎn)生有效的單一的輸出的概率 為0。 的實際值取決于底層物理環(huán)境，如噪聲和衰落。 uuPuuPuvPuvPispu發(fā)生在閱讀器處的錯誤 可以驗證，基本二進制樹算法在考慮閱讀器錯誤時也依舊健壯，但對于MBT則是嚴重的。同錯誤發(fā)生在標簽處一樣,發(fā)生在閱讀器處的錯誤也影響了在EBT中進行估計的正確性。如果使用基本的二進制樹，當 0 0，所其他的 = 0的時候，則不會有錯過的標簽。如果 三個有一個為正數(shù)，則標簽可以被錯過。實際中，錯誤既會

35、發(fā)生在標簽處和也會發(fā)生在閱讀器處。為了緩解標簽錯過的問題，應該結合上述兩種方法。協(xié)議制定者可能更喜歡使用閱讀器重新啟用已經(jīng)被使能過的區(qū)間，因為這種方式對標簽的智能化要求最小。scPicPuvPsiPciPcsP移動標簽的處理 RFID標簽的一個特別重要的場景是對于一個給定的讀寫器，標簽進入/走出閱讀器覆蓋的區(qū)域，如有標簽的物品放在傳送帶上時。這也使得協(xié)議操作不理想，但在某種程度上，它與靜態(tài)/動態(tài)錯誤對協(xié)議的影響又不相同。圖(a)中閱讀器覆蓋的傳送帶總長度為L，并且標簽在傳送帶上移動。另一個有用的表示方法圖(b)，一個給定的區(qū)間被使能，則一個條紋長度為L的二維仲裁空間被啟用。如果標簽均勻分布在傳

36、送帶上，不管傳送帶是否移動，一個條紋總是包含相同數(shù)量的標簽。移動標簽的處理 基本二進制樹算法在標簽進入/走出閱讀器范圍的情況中是健壯的，因為這相當于在標簽處的閱讀錯誤。如圖，在 時，讀寫器檢測到由 和 發(fā)送產(chǎn)生的碰撞，并且開始去解決這一沖突。 的令牌在0，0.5)，而 和 的令牌在(0.5，1)。在 時就解決了 。但是，在 時， 當閱讀器使能 所在的區(qū)間時，標簽 已經(jīng)不在它的范圍內了。另外，一個新的標簽 卻已經(jīng)到來。 2t1t3t111222332移動標簽的處理 與算法性能相關的一個重要參數(shù)是標簽密度，即單位時間進入讀寫器范圍內的標簽數(shù)量。同樣，這個密度也等于單位時間內走出閱讀器范圍的標簽數(shù)量

37、.當標簽密度小時，碰撞會很快地解決并且標簽被錯過的概率很低。隨著密度的增加，未解析的標簽的平均百分比會增加。 在一些情況中, 平均數(shù)據(jù)包到達率代表了給定算法的最大穩(wěn)定吞吐量。在傳送帶上，如果數(shù)據(jù)包直到給定的期限(即標簽離開讀寫器覆蓋的區(qū)域)才發(fā)送，它就會被丟掉。數(shù)據(jù)包的期限 為 =L/v，v代表傳送帶的速度。數(shù)據(jù)包丟掉率是標簽的密度和期限 的函數(shù)。 通過這樣分析得到的最重要參數(shù)也許是走出閱讀器的范圍但未被解析的標簽密度。也就是說,丟失標簽問題應該通過在傳送帶上部署多個讀寫器來解決。從閱讀器 范圍走出的未解析標簽的密度就是進入閱讀器 范圍的待解析標簽密度。因此，在傳送帶上單位時間的標簽數(shù)量，可以

38、確定為了保持丟失的標簽數(shù)低于一定值所需的讀寫器的數(shù)量。 ARBR合作讀寫器和廣義仲裁空間 1.二維仲裁空間2. 進一步的說明與多維仲裁二維仲裁空間 如圖所示，讀寫器 和 能夠通過專用連接線分享信息，它使用有線或射頻接口而不同于與標簽通信。另外，也可以認為這兩個讀寫器是一個常見的分布式天線控制器。這些讀寫器通過下列方法與彼此相互合作：（a）他們協(xié)調傳輸為了避免讀者碰撞（b）他們交換閱讀過程中標簽的相關信息。ARBR二維仲裁空間 讓Tu表示的一組標記讀寫器的范圍是u = A, B 。一般來說，設置的TA和TB是不同的。我們假設密集的標簽同一區(qū)域內覆蓋這兩個讀寫器，這種假設下的RFID系統(tǒng)是非常強大

39、的，標記的密度顯著依賴于使用場景和物理設備，就像一個倉庫或者商店。二維仲裁空間 仲裁算法： (1） 發(fā)出一個最初的請求幀（記為A），標簽從Ta開始回復。 （2）接下來 發(fā)送另一個請求幀（記為B），標簽從Tb回復。我們定義接下來的集合：S1=Ta/Tab，S2=Tab，S3=Tb/Tab。 這兩個最初的請求幀是用來讓每個標簽清楚Sj屬于集。例如，一個標簽收到從 發(fā)送的請求幀，而不是 ，這樣他就屬于S1。 在這兩個最初的請求幀之后，這個仲裁將變?yōu)槿齻€獨立的碰撞解析過程繼續(xù)進行，分別地對應每個Si的集。ARBRARBR二維仲裁空間 對S2集合的仲裁可以由兩個讀寫器中任意一個執(zhí)行，仲裁協(xié)議在一個會話集

40、Si的不間斷的時間內只運行Si集。每組可以有多個會話，例如表示i-th集的會話j-th。例如,讀寫器可以協(xié)調運行的會話序列如下: ，T3.1，T2.2，1.用 表示集 的基數(shù)， 表示在會話 解決標簽數(shù)量。ininiSji,Kji,二維仲裁空間 據(jù)每個讀寫器不同的覆蓋范圍引入空間劃分，有助于碰撞的解決，因為它本質上把標簽分成了更小的組。如此一個分割界定提出了以下簡單的解決方案：運行三個會話1,1，2,1，3,1 ，在每個會話中所有的標簽從一個給定的集開始解決，也就是說，Ki1=ni ，這樣的一個解決方案功非常限制讀寫器間的合作，而且n1，n2，是獨立完成的。 二維空間仲裁的關鍵思想是，除了維度隨

41、機生成令牌的位置，另一個維度用來解決標簽之間的碰撞。作為Si類似的符號，讓S1只覆蓋 ，S2覆蓋Ra和Rb，S3只覆蓋Rb。因為標簽均勻分布在兩個讀寫器覆蓋面積內，一個標簽屬于Si的概率是=Si/S，S=S1+S2+S3?？紤]讀寫器是不移動的，他們在運行一個特定的初始化過程期間已經(jīng)估計了重疊的范圍，從而估計出 。ARBRBRAR二維仲裁空間 復合隨機過程表示:標簽是隨機分布的，在一個二維空間中令牌是隨機分布在區(qū)間0,1)。對于一個給定的標簽,隨機的令牌代表它的x坐標和y坐標是隨機放置。二維仲裁空間 橫坐標代表隨機標記的尺寸，而縱坐標代表空間位置的標記。如果兩個標簽是在同一空間集Si中,然后他們

42、的唯一可以區(qū)分的途徑是在仲裁過程中通過使用隨機的令牌。在另一方面,如果標簽 Si, Sj和ij,那么這兩個標簽不需要使用隨機的令牌來區(qū)別。二維仲裁空間 取代單獨的估計 ，可以使用下面的方法。考慮到標簽均勻分布在總覆蓋面積的兩個讀寫器，讀寫器可以分享他們在觀察時間內的信息，可以獲得以下總數(shù)的估計標簽n=n1+n2+n3 。 使用這個總數(shù)的估計,估計基數(shù)可以獲得每個標簽集的 如下：二維仲裁空間 估計(使用上標)將被稱為合作估計的。為了評估其正確性,它的方差可以估計如下：另一種選擇是使用非合作估計,每組Si分別計算：和方差的估計決定如下：二維仲裁空間 估計方差的數(shù)值例子如圖所示。目前解決間隔的值觀察的 = 0.1， = 0.25， = 0.3。讀寫器之間的距離d由讀寫器之間重疊的覆蓋區(qū)域控制，從而得到概率