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

1、王雪,錢志鴻,胡正超,李奕男(吉林大學(xué)通信工程學(xué)院,吉林長(zhǎng)春130025摘要:在二叉樹算法的基礎(chǔ)上提出了鎖位后退防碰撞(BLBO算法,增加了鎖位尋呼指令,閱讀器根據(jù)譯碼結(jié)果判斷發(fā)生碰撞的比特,發(fā)送鎖位尋呼指令鎖定發(fā)生碰撞的比特,尋呼過程采用后退策略,每次識(shí)別一個(gè)標(biāo)簽之后返回到上一個(gè)發(fā)生碰撞的節(jié)點(diǎn)。算法充分考慮了閱讀器尋呼次數(shù)、傳輸時(shí)延、標(biāo)簽?zāi)芎囊约巴掏铝?個(gè)重要性能指標(biāo),仿真結(jié)果表明,BLBO防碰撞算法較其他二叉樹算法性能有明顯提高,更適用于RFID防碰撞協(xié)議。關(guān)鍵詞:RFID;鎖位;二叉樹;防碰撞中圖分類號(hào):TN92 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):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利用射頻信號(hào)通過空間耦合(交變磁場(chǎng)或電磁場(chǎng)實(shí)現(xiàn)無接觸信息傳遞并通過所傳遞的信息達(dá)到識(shí)別目的。RFID 技術(shù)是20世紀(jì)90年代興起的自動(dòng)識(shí)別技術(shù),較其他技術(shù)明顯的優(yōu)點(diǎn)是電子標(biāo)簽和閱讀器無需接觸便可完成識(shí)別1。射頻識(shí)別技術(shù)的一個(gè)主要優(yōu)

6、點(diǎn)就是多目標(biāo)識(shí)別。在系統(tǒng)工作的時(shí)候,閱讀器周圍可能會(huì)有多個(gè)標(biāo)簽同時(shí)存在,當(dāng)多個(gè)標(biāo)簽同時(shí)向閱讀器傳送數(shù)據(jù)的時(shí)候就產(chǎn)生了沖突問題。目前存在的RFID防碰撞算法主要有2種:一種是基于ALOHA的不確定性算法,另一種是基于二叉樹2(BT, binary tree的確定性算法?；贏LOHA的不確定性算法有個(gè)致命的缺點(diǎn)是標(biāo)簽容易出現(xiàn)“餓死”情況(即標(biāo)簽存收稿日期:2009-11-16;修回日期:2010-04-12基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(60940010;吉林省科技發(fā)展計(jì)劃項(xiàng)目基礎(chǔ)研究基金資助項(xiàng)目(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通信學(xué)報(bào)第31卷在不能被識(shí)別的可能,基于二叉樹的確定性算法雖然解決了這種“餓死”情況,但也存在著識(shí)別周期長(zhǎng)、標(biāo)簽?zāi)芎拇蟮膯栴}。文獻(xiàn)3提出了基于動(dòng)態(tài)幀時(shí)隙ALOHA(DFSA協(xié)議與正交可變擴(kuò)頻因子(OVSF碼作為擴(kuò)頻碼的碼分多址技術(shù)相結(jié)合的超高頻RFID系統(tǒng)。文獻(xiàn)4通過增加校驗(yàn)位來增強(qiáng)系統(tǒng)的防碰撞性能。BONUCCELLI M A等

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、搜索樹算法識(shí)別n 個(gè)電子標(biāo)簽的傳輸時(shí)延為NEW NEW 3221(244L k x x nv v+=(2n (5NEW NEW 323L k v v+=(1n = (6 式(5對(duì)x 求導(dǎo)可以得到:NEW22n v= (7 由式(7得出總的傳輸時(shí)延NEW 對(duì)于變量x 是增函數(shù)。3.3 標(biāo)簽?zāi)芎脑谖墨I(xiàn)15中,作者將等效電路的整流電路稱為“Shottky 探測(cè)電路”。假設(shè)T 為系統(tǒng)的時(shí)鐘周期,對(duì)于任何一個(gè)21(k k T 過程內(nèi),1k 和2k 分別代表這個(gè)過程的開始和結(jié)束經(jīng)歷的時(shí)鐘周期數(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 時(shí)鐘周期內(nèi)“0”和“1”傳輸,load C 為電路的平均負(fù)載電容,dd V 為剩余功率,drop V 為最大電壓降。為了公平比較,設(shè)時(shí)間周期INQ T ,定義INQ T T Cyc =,Cyc 代表完成一次整體事件所需要的全部時(shí)鐘周期,式(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 學(xué) 報(bào) 第 31 卷 P ( k2 , k1 = (9 與

25、3.2 節(jié)所述的搜索過程類似，可得本算法的 整個(gè)識(shí)別過程共需要的時(shí)鐘周期為 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 下進(jìn)行仿真。 標(biāo)簽 ID 均勻分布， 長(zhǎng)度固定為 64bit， 標(biāo)簽數(shù)量在 090 間動(dòng)態(tài)變化，比特率為 100kbit/s， 30 次仿真取均值， 對(duì)閱讀器的尋呼次數(shù)、 傳輸時(shí)延、 與 標(biāo)簽?zāi)芎囊约巴掏铝?4 個(gè)性能指標(biāo)進(jìn)行分析， BS 算法和 DBS 算法進(jìn)行了比較。 圖 5 為 BLBO

26、 算法與 BS 算法和 DBS 算法的閱 讀器尋呼次數(shù)比較， 由圖可以看出 BLBO 算法的閱 隨著 讀器尋呼次數(shù)明顯小于 BS 算法和 DBS 算法， n 值的增大，BLBO 算法較 BS 算法和 DBS 算法的 優(yōu)勢(shì)越明顯。 在本算法中，每個(gè)“接收”和“發(fā)送”操作分 別產(chǎn)生 7 次和 8 次傳輸，2 個(gè)“ 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ù)比較 由此可以得到當(dāng) n 2 時(shí)，BLBO 算法的標(biāo)簽 能耗為 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é)論：識(shí)別 n 個(gè)電子標(biāo)簽，在 閱讀器的尋呼次數(shù)方面 BLBO 算法少于 BS 算法， 而 BS

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

29、能耗， 下面將本算法與這 2 種算法進(jìn)行比較。假設(shè) C Vdrop 值為 1，發(fā)生沖突的比特?cái)?shù) x 的取值分別 Cload Vdd Integ(lbn + k 、 k 時(shí)得到 BLBO 算 2 法和 BS 算法以及 DBS 算法的標(biāo)簽?zāi)芎碾S標(biāo)簽個(gè) 從圖 7 中可以 數(shù) n 的變化關(guān)系的比較如圖 7 所示。 看出隨著 n 值的增大，圖 7 （ a ）和圖 7 （ b ）中 BLBO 算法的標(biāo)簽?zāi)芎男∮诙鏄?BT 算法和尋呼 對(duì)式 13） （ 兩邊對(duì)變量 x 求導(dǎo)得到： n 2 時(shí)， 當(dāng) BLBO 算法的能耗 PNEW 對(duì)于變量 x 是增函數(shù)。當(dāng) n = 1 時(shí)，標(biāo)簽的能耗為 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 標(biāo)準(zhǔn)，不計(jì)控制、前后 綴、校驗(yàn)冗余等開銷，在理想信道(error-free條件 第6期 王雪等：基于二叉樹的 RFID 防碰撞算法的研究 55 法， 因此由文獻(xiàn)15可以得到下面的結(jié)論： 識(shí)別 n 個(gè) 電子標(biāo)簽的標(biāo)簽?zāi)芎?，BLBO 算法小于動(dòng)態(tài)二叉搜 索樹算法，二叉搜索樹算法能耗最高。 由此得到下面結(jié)論：識(shí)別 n 個(gè)電子標(biāo)簽，在標(biāo) 簽?zāi)芎姆矫?，BLBO 算法的能耗最小，BT

31、算法能 耗高于 QT 算法，BS 算法能耗高于 DBS 算法。 圖 6 BLBO 算法和 BS、DBS 算法的時(shí)延比較 樹 QT 算法。 x 的值增大到 k 時(shí)， 7 c） BLBO 當(dāng) 圖（ 中 算法的標(biāo)簽?zāi)芎碾S著 n 值的增大逐漸趨近于 QT 算 法，但仍優(yōu)越于 BT 算法，一般情況下，發(fā)生沖突 的比特?cái)?shù)是小于 k 的， x 取 k 是極限值。 標(biāo)簽?zāi)芎牡拇笮≈饕Q于閱讀器的尋呼次 數(shù)以及標(biāo)簽接收和發(fā)送的比特長(zhǎng)度，由于 BS 算法 和 DBS 算法閱讀器的尋呼次數(shù)和標(biāo)簽每次接收和 發(fā)送的比特長(zhǎng)度都大于 BLBO 算法，又由于 BS 算 法和 DBS 算法的尋呼次數(shù)都是一樣的，而 DBS

32、算 法中標(biāo)簽每次接收和發(fā)送的比特長(zhǎng)度小于 BS 算 圖 7 BLBO 算法與 BT、QT 算法的標(biāo)簽?zāi)芎谋容^ 圖 8(a為 BLBO 算法和 BS 算法以及 DBS 算法 的吞吐量比較， 從圖中可以看出 BLBO 算法的吞吐 隨著 n 的增大， 量明顯優(yōu)越于 BS 算法和 DBS 算法， BLBO 算法的吞吐量趨近于 50%。 8(b為 ALOHA 圖 算法和 Frame-Slotted ALOHA 算法的吞吐量的比 較，從圖中可以看到在 G =0.5 時(shí)，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