基于二叉樹的RFID防碰撞算法的研究

1、王雪,錢志鴻,胡正超,李奕男(吉林大學通信工程學院,吉林長春130025摘要:在二叉樹算法的基礎上提出了鎖位后退防碰撞(BLBO算法,增加了鎖位尋呼指令,閱讀器根據(jù)譯碼結(jié)果判斷發(fā)生碰撞的比特,發(fā)送鎖位尋呼指令鎖定發(fā)生碰撞的比特,尋呼過程采用后退策略,每次識別一個標簽之后返回到上一個發(fā)生碰撞的節(jié)點。算法充分考慮了閱讀器尋呼次數(shù)、傳輸時延、標簽能耗以及吞吐量4個重要性能指標,仿真結(jié)果表明,BLBO防碰撞算法較其他二叉樹算法性能有明顯提高,更適用于RFID防碰撞協(xié)議。關鍵詞:RFID;鎖位;二叉樹;防碰撞中圖分類號:TN92 文獻標識碼:A 文章編號:1000-436X(201006-0049-09

2、Research on RFID anti-collision algorithmsbased on binary treeWANG Xue, QIAN Zhi-hong, HU Zheng-chao, LI Yi-nan(College of Communication Engineering, Jilin University, Changchun 130025, ChinaAbstract: The bit-locking backoff (BLBO anti-collision algorithm was proposed on the basis of binary algorith

3、m, which puts forward the concept and orders of bit-locking. A reader recognizes the bits where there are collisions according to the results of decoding. Then the orders of bit-locking are transmitted to lock the bit collided, after which backoff strategy is adopted. When the reader recognizes one

4、tag, it returns to the previous collided tag. The proposed algorithm fully takes the time of request into account, as well as transmission delay, power consumption and throughput of the system. The analysis on simulation result indicates that BLBO performs significantly better than the existing bina

5、ry tree algorithms. It is suitable for the RFID anti-collision protocol in a greater deal.Key words: RFID; bit-locking; binary tree; anti-collision1引言RFID(radio frequency identification利用射頻信號通過空間耦合(交變磁場或電磁場實現(xiàn)無接觸信息傳遞并通過所傳遞的信息達到識別目的。RFID 技術是20世紀90年代興起的自動識別技術,較其他技術明顯的優(yōu)點是電子標簽和閱讀器無需接觸便可完成識別1。射頻識別技術的一個主要優(yōu)

6、點就是多目標識別。在系統(tǒng)工作的時候,閱讀器周圍可能會有多個標簽同時存在,當多個標簽同時向閱讀器傳送數(shù)據(jù)的時候就產(chǎn)生了沖突問題。目前存在的RFID防碰撞算法主要有2種:一種是基于ALOHA的不確定性算法,另一種是基于二叉樹2(BT, binary tree的確定性算法。基于ALOHA的不確定性算法有個致命的缺點是標簽容易出現(xiàn)“餓死”情況(即標簽存收稿日期:2009-11-16;修回日期:2010-04-12基金項目:國家自然科學基金資助項目(60940010;吉林省科技發(fā)展計劃項目基礎研究基金資助項目(20080524 Foundation Items: The National Natural

7、 Science Foundation of China (60940010; The Basic Research of Science and Technology Development Program of Jilin Province (2008052450通信學報第31卷在不能被識別的可能,基于二叉樹的確定性算法雖然解決了這種“餓死”情況,但也存在著識別周期長、標簽能耗大的問題。文獻3提出了基于動態(tài)幀時隙ALOHA(DFSA協(xié)議與正交可變擴頻因子(OVSF碼作為擴頻碼的碼分多址技術相結(jié)合的超高頻RFID系統(tǒng)。文獻4通過增加校驗位來增強系統(tǒng)的防碰撞性能。BONUCCELLI M A等

8、人提出了時隙ALOHA算法5,電子標簽只能在規(guī)定的同步時隙內(nèi)傳輸數(shù)據(jù)包,對所有電子標簽的同步由閱讀器控制,時隙ALOHA 算法較ALOHA算法可能出現(xiàn)的碰撞時間只有一半。CHA J R等人提出了動態(tài)幀時隙ALOHA算法6,該算法根據(jù)閱讀器周圍標簽數(shù)目動態(tài)調(diào)整幀的大小。PENG Q S等人提出了增強型動態(tài)幀時隙ALOHA算法7,這種算法是把標簽分成多個簇,每次只有一個簇與閱讀器進行動態(tài)幀時隙防碰撞算法,該算法較動態(tài)幀時隙算法性能上有較大提高。FINKENZELLER K在RFID手冊中提出二叉搜索樹(BS, binary search算法8,標簽根據(jù)碰撞信號的譯碼結(jié)果發(fā)出尋呼,每識別出一個標簽就

9、返回到起始點,這是二叉樹算法中的經(jīng)典算法之一。YU S S等人在二叉搜索樹算法的基礎上提出了動態(tài)二叉搜索樹(DBS, dynamic binary search算法9,在二叉搜索樹算法的基礎上將閱讀器尋呼和標簽響應所發(fā)送的比特數(shù)減少一半,大大減少了傳輸時延。文獻1013分別也是在二叉搜索樹算法基礎上的改進算法,它們在算法性能上各有利弊。LAW C提出了無記憶尋呼樹(QT, query tree14算法,標簽除了記憶自己的ID信息外不需要記憶其他任何信息。ZHOU F等人在文獻14的基礎上通過減少發(fā)生碰撞標簽的響應次數(shù)來對尋呼樹算法進行改進15,改進的算法減少了標簽的能耗。針對目前二叉樹算法中存

10、在著識別周期長、標簽能耗大的問題,本文提出了鎖位的概念,通過鎖位尋呼指令鎖定碰撞發(fā)生比特位置,在鎖定的碰撞位上進行防碰撞運算,采用后退策略識別碰撞節(jié)點下一個分支內(nèi)的所有標簽。本文組織結(jié)構(gòu)如下:第2節(jié)介紹鎖位后退防碰撞算法的原理、指令與算法步驟;第3節(jié)從閱讀器尋呼次數(shù)、傳輸時延、標簽能量以及吞吐量4個性能指標分析算法性能;第4節(jié)對鎖位后退算法進行了仿真及分析;第5節(jié)為本文的結(jié)束語。2鎖位后退防碰撞算法 圖1 二叉搜索樹算法識別過程 圖2 動態(tài)二叉搜索樹算法識別過程鎖位后退防碰撞算法在以下2個方面進行改進。1 減少數(shù)據(jù)冗余位閱讀器在發(fā)送尋呼指令之后,閱讀器工作區(qū)域范圍內(nèi)的所有電子標簽對此尋呼做出應

11、答,如果閱讀器譯碼得到有h個位發(fā)生沖突,顯然只有這h個第6期王雪等:基于二叉樹的RFID防碰撞算法的研究51比特對于閱讀器來說是未知的,其他的比特對于標簽是已知的。由圖1所示的BS算法中,閱讀器和電子標簽每次發(fā)出的尋呼是整個序列號,含有的冗余信息太大,DBS算法在BS算法的基礎上減除了一半的冗余信息,但也沒有達到最優(yōu)化。BLBO算法就是在此基礎上繼續(xù)減除尋呼中信息冗余位,以減少傳輸時延和能耗。例如上述所舉的例子中,閱讀器得到譯碼結(jié)果為1X1X01010101,顯然只有這2個X比特對于閱讀器來說是未知的,其他的比特都是已知的,鎖位后退防碰撞算法就是將防碰撞處理限制在這2個X比特上,不傳輸其他的比

12、特,這樣就在動態(tài)二叉搜索樹算法的基礎上進一步減少了數(shù)據(jù)冗余位。2 減少碰撞發(fā)生次數(shù)如圖3所示,假若閱讀器識別電子標簽4后,二叉搜索樹和動態(tài)二叉搜索樹算法都要返回到根節(jié)點去發(fā)送尋呼識別其他的電子標簽,本算法采取的是后退策略,即識別標簽4之后,返回到上一次發(fā)生碰撞的節(jié)點3去產(chǎn)生新的尋呼識別標簽5,這樣就大大減少了碰撞發(fā)生的次數(shù)。 圖3 二叉樹算法構(gòu)成的樹結(jié)構(gòu)2.1鎖位后退防碰撞算法的相關指令為了實現(xiàn)這個算法,需要一組指令,這組指令由電子標簽處理。此外,每個電子標簽擁有一個唯一的序列號8。具體指令如下:REQUEST(UID請求(序列號;SELECT(UID選擇(序列號;READ-DATA讀出數(shù)據(jù);

13、UNSELECT去選擇;下面介紹BLBO算法需要新加的指令。REQUEST(UID,0鎖位尋呼,UID代表閱讀器在第一次尋呼之后,根據(jù)譯碼結(jié)果所得到的下一次尋呼的序列號,UID的取值約定為:閱讀器在判斷出數(shù)據(jù)發(fā)生碰撞的準確比特位置之后,將碰撞發(fā)生的幾個位置提取出來,并將幾個碰撞比特置“1”,未發(fā)生碰撞的比特置“0”,組成新的鎖定尋呼指令的序列號。閱讀器在發(fā)送這個尋呼指令之后,電子標簽的響應為:標簽在接到這個鎖位命令之后,將自己ID中的數(shù)據(jù)位與接收到的閱讀器發(fā)出的序列號進行比較,與閱讀器發(fā)出的UID比特中值為“1”所對應的比特進行鎖定,在接下來的防碰撞處理中,參與數(shù)據(jù)發(fā)送和比較的僅僅是這幾個被鎖

14、定的比特。只有電子標簽鎖定的所有比特中最高比特的值為0的回送自己的ID給閱讀器,并且返回鎖定的比特中除最高位的其他幾比特,最高比特與X值相同的不響應。2.2 鎖位后退防碰撞算法的工作流程圖4為BLBO算法的防碰撞處理流程,該流程分為3個小流程:閱讀器發(fā)送REQUEST(11111111命令時標簽無碰撞發(fā)生時的流程、有碰撞發(fā)生時“0”分支處理流程和有碰撞發(fā)生時“1”分支處理流程(鎖定的比特中最高比特為“0”的所有標簽處在“0”分支,鎖定的比特中最高比特為“1”的所有標簽處在“1”分支。BLBO算法的主要步驟如下。1 閱讀器發(fā)送REQUEST(11111111命令,所有ID碼值小于或者等于(111

15、11111的電子標簽對此命令做出應答,然后所有應答標簽將自己的ID碼發(fā)送出去。2 閱讀器檢測收到的信號,如果沒有信號,表示閱讀器周圍沒有電子標簽,則轉(zhuǎn)到步驟1,否則轉(zhuǎn)到步驟3。3 閱讀器對所有電子標簽做出的應答信號進行譯碼,根據(jù)譯碼結(jié)果判斷是否有碰撞發(fā)生,如果沒有碰撞發(fā)生,閱讀器發(fā)送SELECT和READ- DATE指令,對標簽進行讀寫操作之后,閱讀器發(fā)出UNSELECT命令,使該標簽進入無聲狀態(tài);如果譯碼結(jié)果判斷出有碰撞,則轉(zhuǎn)到步驟4。4 閱讀器根據(jù)步驟3中的譯碼結(jié)果判斷碰撞發(fā)生在哪幾個比特上,閱讀器將這幾個碰撞的比特置“1”,未發(fā)生碰撞的比特置“0”,接著閱讀器發(fā)送REQUEST(UID,

16、0指令,標簽在接到此命令之后將UID與自己的ID進行比較,將發(fā)生碰撞的比特鎖定,鎖定比特中最高比特為“0”的標簽對此命令做出應答,將自己鎖定比特中剩下的幾比特發(fā)送給閱讀器。閱讀器判斷是否有碰撞發(fā)生,如果沒有碰撞發(fā)生,閱讀器發(fā)送SELECT和READ- DATE指令,對標簽進行讀寫操作之后,閱讀器發(fā)出UNSELECT命令,使該標簽進入無聲狀態(tài)。如52通信學報第31卷果有碰撞發(fā)生,閱讀器對接收到的信號再進行譯碼,判斷出發(fā)生碰撞的準確比特,將碰撞發(fā)生的最高比特置“0”,高于該比特的值不變,低于該比特的值舍去,在發(fā)生碰撞的這些標簽中再次執(zhí)行REQUEST(UID命令。每次順利讀取某個標簽之后,采取后退

17、策略,返回到上一次發(fā)生碰撞的節(jié)點,識別此節(jié)點的另外一個分支,這樣不斷重復操作,直到把鎖定的比特中最高比特為“0”這個分支內(nèi)產(chǎn)生碰撞的所有標簽識別完以后,轉(zhuǎn)到步驟5。5 閱讀器發(fā)送REQUEST(1這個指令,鎖定比特中最高比特為“1”的標簽對此命令做出應答,將自己鎖定比特中剩下的幾比特發(fā)送給閱讀器。閱讀器判斷是否有碰撞發(fā)生,如果沒有碰撞發(fā)生,閱讀器發(fā)送SELECT和READ-DATE指令,對標簽進行讀寫操作之后,閱讀器發(fā)出UNSELECT 命令,使該標簽進入無聲狀態(tài)。如果有碰撞發(fā)生,閱讀器對接收到的信號再進行譯碼,判斷出發(fā)生碰撞的準確比特,將碰撞發(fā)生的最高比特置“0”,高于該比特的值不變,低于該

18、比特的值舍去,在發(fā)生碰撞的這些標簽中再次進行REQUEST(UID命令。每次順利讀取某個標簽之后,返回到上一次發(fā)生碰撞的節(jié)點,識別此節(jié)點的另外一個分支,這樣不斷重復操作,直到把鎖定比特中最高比特為“1”的這個分支內(nèi)產(chǎn)生碰撞的所有標簽識別完以后,轉(zhuǎn)到步驟6。6 待所有電子標簽都被識別出來,識別過程結(jié)束。3算法性能分析3.1閱讀器的尋呼次數(shù)若有n個電子標簽在閱讀器的工作區(qū)域內(nèi),為了識別n個電子標簽閱讀器所要發(fā)出的尋呼次數(shù)設為(Q n,識別過程中發(fā)生數(shù)據(jù)碰撞的次數(shù)設為(C n,則可以得到: 圖4 鎖位后退防碰撞算法的工作流程第6期 王雪等:基于二叉樹的RFID 防碰撞算法的研究 53(Q n C n

19、 n =+ (1 (21Q n n = (2 下面證明式(1和式(2。證明 BLBO 算法所形成的二叉樹中所有節(jié)點的數(shù)量代表的是尋呼的總數(shù)(Q n ,非葉子節(jié)點的總數(shù)代表數(shù)據(jù)碰撞的次數(shù)(C n ,葉子節(jié)點的數(shù)量即為標簽的個數(shù)n ,所以有(Q n C n n =+,即式(1成立。下面證明式(2,這里采用數(shù)學歸納法來證明。 1 當n =1時,表示閱讀器工作區(qū)域內(nèi)只有一個電子標簽,所以不會產(chǎn)生碰撞,很顯然(11Q =成立。 2 當n =2時,表示閱讀器工作區(qū)域內(nèi)有2個電子標簽,此時標簽至少有1個比特發(fā)生碰撞。無論有幾個比特發(fā)生碰撞,由此算法得到,在發(fā)生碰撞的第一個比特分別置“0”和“1”就可以把2個

20、電子標簽區(qū)別開來,因此(2C =1,則(2(223Q C =+=,滿足公式。3 假設有n 個電子標簽時結(jié)論成立,即1(2n Q n =,那么當閱讀器工作范圍內(nèi)有n +1個電子標簽時,有如下結(jié)論:當?shù)趎 +1個電子標簽進入到閱讀器的工作范圍時,在本算法的二叉樹上將增加一個分支,即多增加一個碰撞節(jié)點,也就是說碰撞的次數(shù)為(1(1C n C n +=+,于是可以得到:(1(1122212(11(Q n C n n C n Q n n n n +=+=+=+=+=+(3由此得到有n +1個電子標簽結(jié)論也成立,即式(2成立。 3.2 傳輸時延假設有n 個電子標簽的UID 的長度為k bit ,且沖突的比

21、特數(shù)為x ,x 為閱讀器第一次接收到來自電子標簽的信號所譯碼判斷出的碰撞的比特數(shù),取值范圍為Integ(lb ,n k 16。BLBO 算法中Type1型節(jié)點個數(shù)為n 1個,Type2型節(jié)點個數(shù)為n 個。對樹的搜索過程中,當2n 時,閱讀器第一次發(fā)出的尋呼為k bit ,電子標簽第一次回送的也是k bit ,以后的尋呼中閱讀器和電子標簽發(fā)送的比特數(shù)為0,x bit ,閱讀器的第一次尋呼需要處于Type1型標簽去經(jīng)歷221k +個時鐘周期,第二次鎖位指令需要處于Type1型標簽經(jīng)歷21k x +個時鐘周期,剩下的尋呼需要處于Type1型標簽經(jīng)歷21x +個時鐘周期。如果通信順利未出現(xiàn)碰撞,閱讀器

22、額外需要2bit 周期來登記電子標簽ID 信息,因此Type2的節(jié)點需要經(jīng)歷(23x +bit 周期。BLBO 算法在防碰撞處理過程中標簽和閱讀器需要傳輸?shù)乃斜忍亻L度之和NEW L 為 (NEW (221(21(23(21(33221244L k k x x n x n k x x n=+=+ (4當1n =時,BLBO 算法在防碰撞處理過程中標簽和閱讀器需要傳輸?shù)乃斜忍亻L度之和NEW L = 323k +。傳輸時延取決于閱讀器發(fā)出尋呼的次數(shù)和每次發(fā)出尋呼的UID 長度。BLBO 算法中要識別n 個電子標簽所需要的尋呼次數(shù)為NEW 21Q n =,假設數(shù)據(jù)傳輸速率為v bit/s ,則二叉

23、搜索樹算法識別n 個電子標簽的傳輸時延為NEW NEW 3221(244L k x x nv v+=(2n (5NEW NEW 323L k v v+=(1n = (6 式(5對x 求導可以得到:NEW22n v= (7 由式(7得出總的傳輸時延NEW 對于變量x 是增函數(shù)。3.3 標簽能耗在文獻15中,作者將等效電路的整流電路稱為“Shottky 探測電路”。假設T 為系統(tǒng)的時鐘周期,對于任何一個21(k k T 過程內(nèi),1k 和2k 分別代表這個過程的開始和結(jié)束經(jīng)歷的時鐘周期數(shù),可以得到消耗的功率為(212drop dd load 2121load dd ,k i i k V V C C

24、P k k A k k T C V = (8其中,i A 代表電路中第i 時鐘周期內(nèi)“0”和“1”傳輸,load C 為電路的平均負載電容,dd V 為剩余功率,drop V 為最大電壓降。為了公平比較,設時間周期INQ T ,定義INQ T T Cyc =,Cyc 代表完成一次整體事件所需要的全部時鐘周期,式(8改寫為54 通 信 2 CycVdd Cload k2 C Vdrop Ai Cload Vdd ( k2 k1 TINQ i = k1 Cyc k2 C Vdrop Ai Cload Vdd ( k2 k1 i = k1 學 報 第 31 卷 P ( k2 , k1 = (9 與

25、3.2 節(jié)所述的搜索過程類似，可得本算法的 整個識別過程共需要的時鐘周期為 CycNEW = ( 2k + 3 + ( k + x + 3 + ( x + 3( n 3 + ( x + 5 n = 3k + 8n 3 + ( 2n 2 x k2 k1 = 3k + 6 + mx + 4m (10 (11 下進行仿真。 標簽 ID 均勻分布， 長度固定為 64bit， 標簽數(shù)量在 090 間動態(tài)變化，比特率為 100kbit/s， 30 次仿真取均值， 對閱讀器的尋呼次數(shù)、 傳輸時延、 與 標簽能耗以及吞吐量 4 個性能指標進行分析， BS 算法和 DBS 算法進行了比較。 圖 5 為 BLBO

26、 算法與 BS 算法和 DBS 算法的閱 讀器尋呼次數(shù)比較， 由圖可以看出 BLBO 算法的閱 隨著 讀器尋呼次數(shù)明顯小于 BS 算法和 DBS 算法， n 值的增大，BLBO 算法較 BS 算法和 DBS 算法的 優(yōu)勢越明顯。 在本算法中，每個“接收”和“發(fā)送”操作分 別產(chǎn)生 7 次和 8 次傳輸，2 個“ NULL”操作需要 產(chǎn)生 14 次和 9 次傳輸，譯碼操作產(chǎn)生 7 次傳輸， 因此可以得到： A = (14 + 9 + 8k + 7k + ( 7k + 1 + i 14 + 9 + 7i + 8 ( x i + 7 + 14 + 9 + 7 ( m 1 i =1 m 1 73 = m

27、 2 + + 8 x m + 40 + 22k 2 2 (12 圖 5 BLBO 算法與 BS 和 DBS 算法的閱讀器尋呼次數(shù)比較 由此可以得到當 n 2 時，BLBO 算法的標簽 能耗為 PNEW = CycNEW k2 C Vdrop Ai Cload Vdd ( k2 k1 i = k1 3k + 8n 3 + ( 2n 2 x 1 2 = m + 3k + 6 + mx + 4m 2 C Vdrop 73 + 8 x m + 40 + 22k Cload Vdd 2 (13 由此得到下面的結(jié)論：識別 n 個電子標簽，在 閱讀器的尋呼次數(shù)方面 BLBO 算法少于 BS 算法， 而 BS

28、 算法的尋呼次數(shù)與 DBS 算法相當。 在數(shù)據(jù)傳輸速率為 100kbit/s， 標簽 ID 的長度 k 取值為 64bit 的條件下， 碰撞發(fā)生的比特數(shù) x 的取值 Integ(lbn + k 、k 時得到這 3 種 分別為 Integ(lbn 、 2 算法的傳輸時延隨標簽個數(shù) n 的變化關系如圖 6 所 示。從圖中可以看到無論 x 取區(qū)間 Integ(lbn, k 中 的何值，即使取最大值 k ，BLBO 算法的時延都要 小于 BS 算法和 DBS 算法。由此得到下面的結(jié)論： 在傳輸時延方面，BLBO 算法小于 DBS 算法，而 BS 算法時延最大。 文獻15中給出了 2 種防碰撞算法的標簽

29、能耗， 下面將本算法與這 2 種算法進行比較。假設 C Vdrop 值為 1，發(fā)生沖突的比特數(shù) x 的取值分別 Cload Vdd Integ(lbn + k 、 k 時得到 BLBO 算 2 法和 BS 算法以及 DBS 算法的標簽能耗隨標簽個 從圖 7 中可以 數(shù) n 的變化關系的比較如圖 7 所示。 看出隨著 n 值的增大，圖 7 （ a ）和圖 7 （ b ）中 BLBO 算法的標簽能耗小于二叉樹 BT 算法和尋呼 對式 13） （ 兩邊對變量 x 求導得到： n 2 時， 當 BLBO 算法的能耗 PNEW 對于變量 x 是增函數(shù)。當 n = 1 時，標簽的能耗為 C Vdrop P

30、NEW = 23 + 15k Cload Vdd 3.4 吞吐量 (14 BLBO 算法的吞吐量為 n S NEW = 100% 2n 1 (15 為 Integ(lbn 、 4 仿真及分析 本文參考 ISO18000-6 標準，不計控制、前后 綴、校驗冗余等開銷，在理想信道(error-free條件 第6期 王雪等：基于二叉樹的 RFID 防碰撞算法的研究 55 法， 因此由文獻15可以得到下面的結(jié)論： 識別 n 個 電子標簽的標簽能耗，BLBO 算法小于動態(tài)二叉搜 索樹算法，二叉搜索樹算法能耗最高。 由此得到下面結(jié)論：識別 n 個電子標簽，在標 簽能耗方面，BLBO 算法的能耗最小，BT

31、算法能 耗高于 QT 算法，BS 算法能耗高于 DBS 算法。 圖 6 BLBO 算法和 BS、DBS 算法的時延比較 樹 QT 算法。 x 的值增大到 k 時， 7 c） BLBO 當 圖（ 中 算法的標簽能耗隨著 n 值的增大逐漸趨近于 QT 算 法，但仍優(yōu)越于 BT 算法，一般情況下，發(fā)生沖突 的比特數(shù)是小于 k 的， x 取 k 是極限值。 標簽能耗的大小主要取決于閱讀器的尋呼次 數(shù)以及標簽接收和發(fā)送的比特長度，由于 BS 算法 和 DBS 算法閱讀器的尋呼次數(shù)和標簽每次接收和 發(fā)送的比特長度都大于 BLBO 算法，又由于 BS 算 法和 DBS 算法的尋呼次數(shù)都是一樣的，而 DBS

32、算 法中標簽每次接收和發(fā)送的比特長度小于 BS 算 圖 7 BLBO 算法與 BT、QT 算法的標簽能耗比較 圖 8(a為 BLBO 算法和 BS 算法以及 DBS 算法 的吞吐量比較， 從圖中可以看出 BLBO 算法的吞吐 隨著 n 的增大， 量明顯優(yōu)越于 BS 算法和 DBS 算法， BLBO 算法的吞吐量趨近于 50%。 8(b為 ALOHA 圖 算法和 Frame-Slotted ALOHA 算法的吞吐量的比 較，從圖中可以看到在 G =0.5 時，ALOHA 算法的 第6期 2006. 374-383. 王雪等：基于二叉樹的 RFID 防碰撞算法的研究 57 14 LAW C, LEE K, SIU K Y. Efficient memoryless protocol for tag identificationA. Proceedings of the 4th International Workshop on Discrete Algorithms and Me