低冗余搜索樹防碰撞算法范文

本站小編為你精心準備了低冗余搜索樹防碰撞算法參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

《通信學報》2014年第六期

1低冗余搜索樹防碰撞算法

基于上文對搜索樹防碰撞算法的分析，本算法從閱讀器詢問次數(shù)、詢問命令長度、響應時隙數(shù)3方面進行改進，進一步減少詢問過程中產(chǎn)生的冗余數(shù)據(jù)。1)“一問兩答”詢問方式：減少閱讀器詢問次數(shù)在目前的搜索樹算法中，當閱讀器檢測到碰撞并發(fā)送詢問命令后，只有ID序列最高碰撞位比特為‘0’的碰撞標簽響應，ID序列最高碰撞位比特為‘1’的碰撞標簽仍需閱讀器再次發(fā)送一個詢問命令進行詢問，這里將其稱為“一問一答”詢問方式。對于所有碰撞標簽，ID序列最高碰撞位之前的高位序列是相同的，只是最高碰撞位比特分別是‘0’或‘1’。本文利用這一特點提出一種“一問兩答”詢問方式。當閱讀器檢測到碰撞并發(fā)送一個詢問命令后，ID序列最高碰撞位比特為‘0’的碰撞標簽首先在第一個時隙響應，ID序列最高碰撞位比特為‘1’的碰撞標簽等待一個時隙后在第二個時隙響應（如圖1所示）。這種“一問兩答”詢問方式不僅可將碰撞標簽分為2組，而且這2組標簽的響應也僅需一次詢問。2)計數(shù)器“觸發(fā)開關”：減少詢問命令中標識參數(shù)的長度在目前的搜索樹算法中，標簽接收到詢問命令后，根據(jù)其ID序列與詢問命令中的前綴是否匹配而確定是否響應，標簽在響應時將ID序列最高碰撞位之后的低位部分發(fā)送給閱讀器。因此，標簽中的前綴匹配只充當了標簽響應的“觸發(fā)開關”，響應標簽只需獲得最高碰撞位。為減少詢問命令中標識參數(shù)的長度，本算法將前綴與最高碰撞位壓入“棧”中，只將最高碰撞位作為詢問命令的標識參數(shù)，用計數(shù)器替代前綴匹配電路作為標簽響應的“觸發(fā)開關”。計數(shù)器初始值為0，計數(shù)器為0的標簽才能響應詢問命令，計數(shù)器不為0的標簽處于等待狀態(tài)。計數(shù)器也為標簽跟蹤前綴在“棧”中的深度，使響應標簽的ID與出“棧”的前綴相匹配，從而使閱讀器接收到標簽發(fā)回的ID序列最高碰撞位之后的低位部分后，加上出“棧”的前綴可組成一個完整的ID序列。識別過程中，當閱讀器檢測到碰撞并發(fā)送詢問命令后，碰撞標簽分別在對應時隙響應。第一個時隙若發(fā)生碰撞，將前綴與最高碰撞位壓入“棧”中，并發(fā)送計數(shù)器命令（counter），所有標簽的計數(shù)器加1（除等待第二個時隙的標簽）。第二個時隙若發(fā)生碰撞，將新的最高碰撞位作為詢問命令的標識參數(shù)繼續(xù)詢問（詢問命令為query）。第二個時隙若成功識別標簽，拋出“棧”頂存放的前綴與最高碰撞位，將最高碰撞位作為詢問命令的標識參數(shù)進行后退式詢問。注意，后退式詢問時發(fā)送的詢問命令為re-query，所有標簽的計數(shù)器先減1，計數(shù)器減1后為0的標簽才能在對應時隙響應。因此，計數(shù)器的變化規(guī)律為：在第一個時隙，若有前綴入“棧”，計數(shù)器加1；在第二個時隙，若有前綴出“棧”，計數(shù)器減1。3)預測識別：減少標簽響應時隙數(shù)閱讀器對接收到的ID信號經(jīng)曼徹斯特譯碼后可逐位識別出碰撞比特。若沒有碰撞比特，則直接識別標簽；若僅有一個碰撞比特，也可直接預測識別2個標簽，可節(jié)省這2個標簽響應所需的時隙。因為僅有一個碰撞比特時，只有2個標簽發(fā)生碰撞，這2個標簽的ID序列該位比特分別為‘0’和‘1’。文獻[7]中的算法，先將ID序列的所有比特進行異或運算，將運算值加在ID序列的最高位組成一個新ID序列。當ID碰撞信號的譯碼結果只有2個碰撞比特時，閱讀器可通過ID序列中所有未碰撞比特的異或值得到這2個碰撞比特。但這2個碰撞比特是由2個標簽造成的，該算法中不會出現(xiàn)只有一個碰撞比特的情況。所以，只能在僅有2個碰撞比特的情況下直接識別2個標簽。因此，該算法增加了復雜度，效果卻與本文算法相同。4)標簽屏蔽機制：避免對已被識別的標簽再次進行識別在移動閱讀器應用中，閱讀器掃描完某一區(qū)域的標簽后，會掃描另一個區(qū)域的標簽。若這2個區(qū)域的重疊部分存在標簽，它仍會掃描已被識別的標簽（如圖2所示）。為避免再次詢問已被識別的標簽，本文引入一種標簽屏蔽機制：標簽預留一個存儲區(qū)，存儲已識別該標簽的閱讀器的序列號（RID）。閱讀器掃描標簽時，首先發(fā)送以該閱讀器RID為參數(shù)的初始化命令（initial）。收到該命令后，標簽將命令中的RID與存儲的RID進行比較。若相同，表明它已被該閱讀器識別，則進入靜默狀態(tài)不再響應；若不同，表明它未被該閱讀器識別，則用接收的RID替換原存儲的RID，在初始化計數(shù)器后進行響應。通過該機制可屏蔽已被識別的標簽，減少對已被識別的標簽再次識別而帶來的通信開銷。為防止在識別過程中到達的標簽不能被識別，本算法在一次掃描后進行二次掃描。因為搜索樹算法的詢問次數(shù)與標簽數(shù)有關，識別過程中的新到標簽又是少量的，所以會瞬間完成第二次掃描。二次掃描后，若沒有標簽響應，便停止掃描；若仍有標簽響應，識別完標簽后，再次掃描，直到不再有標簽響應。

2低冗余搜索樹算法具體實現(xiàn)

圖3為低冗余搜索樹算法的工作流程，該流程分為3個小流程：閱讀器發(fā)送initial(RID)初始化命令，上次被成功識別的標簽進入靜默狀態(tài)，未被識別的標簽初始化計數(shù)器并響應；閱讀器開始迭代詢問過程，直到“棧”為空；當“棧”為空時，再次掃描，直到無標簽響應，結束識別。算法主要步驟如下。1)閱讀器發(fā)送initial(RID)初始化命令，若標簽存儲的RID與命令中的RID相同，則標簽進入靜默狀態(tài)；若不相同，則標簽將計數(shù)器初始化為0，并發(fā)送完整ID序列作為響應。2)閱讀器檢測是否有標簽響應，若無標簽響應，結束識別過程；若存在標簽響應，則對接收到的ID信號經(jīng)曼徹斯特譯碼后，確定最高碰撞位(χ)，發(fā)送以最高碰撞位為標識參數(shù)的query(χ)詢問命令。3)標簽檢查計數(shù)器是否為0，計數(shù)器不為0的標簽進入等待狀態(tài)，不做出任何響應；計數(shù)器為0的標簽檢查ID序列的第χ位比特。若為比特‘0’，標簽在第一個時隙發(fā)送ID序列的第χ位之后的低位部分；若為比特‘1’，等待第一個時隙結束后在第二個時隙發(fā)送ID序列的第χ位之后的低位部分。4)在第一個時隙，若接收到的ID序列中多于1個碰撞比特，則將ID序列最高碰撞位之前的高位部分作為前綴與最高碰撞位壓入“棧”中，并發(fā)送counter命令；否則直接識別標簽。在第二個時隙，若接收到的ID序列中多于一個碰撞比特，確定最高碰撞位(χ)后，繼續(xù)發(fā)送query(χ)進行迭代詢問(即轉到步驟2))；否則直接識別標簽。5)若在第二個時隙成功識別標簽，閱讀器檢查“棧”是否為空。若不為空，拋出“棧”頂存放的前綴與最高碰撞位(χ)，發(fā)送re-query(χ)進行后退式詢問，所有標簽的計數(shù)器減1后進入步驟3)；若為空，進行二次掃描(即轉到步驟1))，直到無標簽響應，結束識別。

3算法性能分析

1)標簽復雜度標簽中計數(shù)器的最大值為構建的二叉樹深度（即標簽ID的長度），因此僅需lbk位的計數(shù)器（設標簽ID長度為k）。標簽中的計數(shù)器替代前綴匹配電路充當標簽響應詢問命令的“觸發(fā)開關”，相比k位前綴匹配電路，降低了標簽復雜度。2)閱讀器的詢問次數(shù)若有n個標簽在閱讀器的識別區(qū)域內(nèi)，在返回式動態(tài)搜索樹算法構建的二叉樹中（如圖4所示），葉子節(jié)點（圖4中方形）的數(shù)量即為標簽的個數(shù)n，非葉子節(jié)點（圖4中圓形）的總數(shù)代表碰撞的次數(shù)C(n)，所有節(jié)點的數(shù)量則代表閱讀器詢問總數(shù)Q，且有如下公式本算法采用了“一問兩答”的詢問方式，遇到碰撞時，只需詢問一次。因此，詢問總數(shù)即為碰撞次數(shù)（非葉子節(jié)點）加第一次初始化詢問，且本算法采用了預測識別，在只有一個碰撞比特的碰撞節(jié)點（圖4中陰影圓形），不必再進行詢問即可識別2個標簽(圖4中陰影方形)。因此，詢問總數(shù)再減去只有一個碰撞比特的碰撞節(jié)點數(shù)。若只有一個碰撞比特的碰撞節(jié)點數(shù)為m(m≤floor(n/2)，floor為向下取整)，則本算法的詢問總數(shù)為3)詢問命令中標識參數(shù)的長度當前的算法采用前綴作為詢問命令的標識參數(shù)，若標簽的ID序列為k位，則詢問命令中標識參數(shù)的平均長度為從式(4)和式(5)可看出L明顯小于L，且隨著k的增加，它們的差距也隨之增大。4)通信開銷為公平對比，不考慮在移動閱讀器應用中，標簽屏蔽機制帶來的明顯收益。假設除標識參數(shù)外詢問命令的其他字段為sbit，標簽響應時附加的前導碼等信息為tbit。因標簽在響應時只發(fā)送ID序列最高碰撞位之后的低位部分，所以每個響應標簽平均發(fā)送的ID序列為Lbit(式(4))，則返回式動態(tài)搜索樹算法識別n個標簽所需的通信開銷為比對式(6)和式(7)，可看出S小于S，且隨n、k的增加，它們的差距也隨之增大。因此本算法明顯降低了識別標簽所需的通信開銷。

4算法仿真與分析

本文從詢問次數(shù)、詢問命令長度、吞吐率與通信開銷4個方面，將LRST算法與RDBST算法[6]和FST算法[7]進行性能比較。為簡單起見，仿真中不考慮控制、前后綴和校驗冗余等帶來的通信開銷，而主要將詢問命令中的標識參數(shù)與標簽發(fā)送的ID序列作為識別標簽所需的通信開銷，并定義吞吐率為標簽總數(shù)與識別標簽所需的總時隙數(shù)之比。因識別過程與標簽群的ID分布有關，分別對16位ID隨機分布、連續(xù)分布2種情況進行仿真。從圖5和圖6可看出，標簽群的ID無論是隨機分布還是連續(xù)分布，LRST算法的詢問次數(shù)都少于其他2種算法，且僅為FST算法的一半。這表明本算法提出的“一問兩答”詢問方式可使整個詢問過程的詢問次數(shù)減少一半。圖7為前綴、最高碰撞位分別作為詢問命令標識參數(shù)的情況下，標識參數(shù)長度的變化曲線。LRST算法采用計數(shù)器作為標簽響應的“觸發(fā)開關”，詢問命令的標識參數(shù)為最高碰撞位。從圖7可看出，當ID序列的長度翻倍時，詢問命令的標識參數(shù)僅需增加一個比特；而其他2種算法采用前綴匹配電路作為標簽響應的“觸發(fā)開關”，則需將前綴作為詢問命令的標識參數(shù)，當ID序列的長度翻倍時，詢問命令的平均標識參數(shù)也隨之翻倍。當ID序列為16bit時，LRST算法采用最高碰撞位作為詢問命令的標識參數(shù)僅需4bit，而其他2種算法采用前綴作為標識參數(shù)平均需9bit。這表明采用最高碰撞位替代前綴作為詢問命令的標識參數(shù)可大大減小詢問命令的長度。從圖8可看出，RDBST算法的吞吐率(u)接近50%，符合理論公式：u=n/(2n−1)。FST算法與LRST算法的吞吐率明顯高于RDBST算法的吞吐率,由吞吐率定義可知，預測識別明顯減少了時隙數(shù)。從圖9可看出，RDBST算法的吞吐率仍為50%，LRST算法與FST算法的吞吐率接近1。這說明預測識別可利用標簽群ID的分布特性，提高吞吐率。從圖8和圖9可看出，LRST算法與FST算法的吞吐率曲線基本重合。這表明2種預測識別在減少時隙數(shù)方面基本相同，因此，LRST算法中的簡單預測識別可替代FST算法中的復雜預測識別。圖10和圖11為系統(tǒng)識別標簽所需的通信開銷，通信開銷可反映時延與功耗[8,9]。從圖10可看出LRST算法的通信開銷明顯低于其他2種算法。LRST算法的通信開銷比RDBST算法降低了約42%，比FST算法降低了約38%。標簽群的ID續(xù)分布時，LRST算法達到最優(yōu)。從圖11可看出，LRST算法的通信開銷比RDBST算法降低了約69%，比FST算法降低了約39%。這表明標簽群的ID無論是隨機分布還是連續(xù)分布，LRST算法都明顯降低了通信開銷。由仿真可看出，當標簽群的ID連續(xù)分布時，LRST算法表現(xiàn)出更好的優(yōu)越性。在很多應用中，標簽群的ID是連續(xù)分布的，例如倉庫管理、生產(chǎn)線等。有些算法加入預處理機制[10]或者鎖定發(fā)生碰撞的比特后再執(zhí)行搜索樹算法[11]，每次詢問后將ID序列中未識別的部分組成一個新ID，以達到減少傳輸比特的目的。它只能在識別少量標簽時，節(jié)省某些比特。在識別大量同類商品的標簽時，節(jié)省的仍是ID序列高位部分的比特。因此，這種機制增加了標簽復雜度，卻得不到很好的效果。

5結束語

本文研究了RFID系統(tǒng)中的標簽防碰撞算法，對搜索樹算法及其改進算法進行了分析，并在此基礎上提出了一種低冗余搜索樹防碰撞算法。該算法能大幅度減少閱讀器的詢問次數(shù)和詢問命令中標識參數(shù)的長度，從而降低了系統(tǒng)的通信開銷，減小了時延，降低了功耗。當接收到的ID序列中只有一個碰撞比特時，可直接識別2個標簽，進一步減少了時隙總數(shù)，提高了吞吐率。仿真結果表明，標簽群的ID無論隨機分布還是連續(xù)分布，本算法都提高了吞吐率，且明顯降低了通信開銷。因此，本算法能夠迅速有效地識別標簽。

作者：黃瓊凌江濤張敏陽小龍單位：重慶郵電大學移動通信技術重點實驗室北京科技大學先進網(wǎng)絡技術與新業(yè)務研究所