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

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

《通信學報》2014年第六期

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

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

2低冗余搜索樹算法具體實現

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

3算法性能分析

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

4算法仿真與分析

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

5結束語

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

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