本站小編為你精心準(zhǔn)備了低冗余搜索樹(shù)防碰撞算法參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。
《通信學(xué)報(bào)》2014年第六期
基于上文對(duì)搜索樹(shù)防碰撞算法的分析，本算法從閱讀器詢問(wèn)次數(shù)、詢問(wèn)命令長(zhǎng)度、響應(yīng)時(shí)隙數(shù)3方面進(jìn)行改進(jìn)，進(jìn)一步減少詢問(wèn)過(guò)程中產(chǎn)生的冗余數(shù)據(jù)。1)“一問(wèn)兩答”詢問(wèn)方式：減少閱讀器詢問(wèn)次數(shù)在目前的搜索樹(shù)算法中，當(dāng)閱讀器檢測(cè)到碰撞并發(fā)送詢問(wèn)命令后，只有ID序列最高碰撞位比特為‘0’的碰撞標(biāo)簽響應(yīng)，ID序列最高碰撞位比特為‘1’的碰撞標(biāo)簽仍需閱讀器再次發(fā)送一個(gè)詢問(wèn)命令進(jìn)行詢問(wèn)，這里將其稱為“一問(wèn)一答”詢問(wèn)方式。對(duì)于所有碰撞標(biāo)簽，ID序列最高碰撞位之前的高位序列是相同的，只是最高碰撞位比特分別是‘0’或‘1’。本文利用這一特點(diǎn)提出一種“一問(wèn)兩答”詢問(wèn)方式。當(dāng)閱讀器檢測(cè)到碰撞并發(fā)送一個(gè)詢問(wèn)命令后，ID序列最高碰撞位比特為‘0’的碰撞標(biāo)簽首先在第一個(gè)時(shí)隙響應(yīng)，ID序列最高碰撞位比特為‘1’的碰撞標(biāo)簽等待一個(gè)時(shí)隙后在第二個(gè)時(shí)隙響應(yīng)（如圖1所示）。這種“一問(wèn)兩答”詢問(wèn)方式不僅可將碰撞標(biāo)簽分為2組，而且這2組標(biāo)簽的響應(yīng)也僅需一次詢問(wèn)。2)計(jì)數(shù)器“觸發(fā)開(kāi)關(guān)”：減少詢問(wèn)命令中標(biāo)識(shí)參數(shù)的長(zhǎng)度在目前的搜索樹(shù)算法中，標(biāo)簽接收到詢問(wèn)命令后，根據(jù)其ID序列與詢問(wèn)命令中的前綴是否匹配而確定是否響應(yīng)，標(biāo)簽在響應(yīng)時(shí)將ID序列最高碰撞位之后的低位部分發(fā)送給閱讀器。因此，標(biāo)簽中的前綴匹配只充當(dāng)了標(biāo)簽響應(yīng)的“觸發(fā)開(kāi)關(guān)”，響應(yīng)標(biāo)簽只需獲得最高碰撞位。為減少詢問(wèn)命令中標(biāo)識(shí)參數(shù)的長(zhǎng)度，本算法將前綴與最高碰撞位壓入“棧”中，只將最高碰撞位作為詢問(wèn)命令的標(biāo)識(shí)參數(shù)，用計(jì)數(shù)器替代前綴匹配電路作為標(biāo)簽響應(yīng)的“觸發(fā)開(kāi)關(guān)”。計(jì)數(shù)器初始值為0，計(jì)數(shù)器為0的標(biāo)簽才能響應(yīng)詢問(wèn)命令，計(jì)數(shù)器不為0的標(biāo)簽處于等待狀態(tài)。計(jì)數(shù)器也為標(biāo)簽跟蹤前綴在“棧”中的深度，使響應(yīng)標(biāo)簽的ID與出“棧”的前綴相匹配，從而使閱讀器接收到標(biāo)簽發(fā)回的ID序列最高碰撞位之后的低位部分后，加上出“棧”的前綴可組成一個(gè)完整的ID序列。識(shí)別過(guò)程中，當(dāng)閱讀器檢測(cè)到碰撞并發(fā)送詢問(wèn)命令后，碰撞標(biāo)簽分別在對(duì)應(yīng)時(shí)隙響應(yīng)。第一個(gè)時(shí)隙若發(fā)生碰撞，將前綴與最高碰撞位壓入“棧”中，并發(fā)送計(jì)數(shù)器命令（counter），所有標(biāo)簽的計(jì)數(shù)器加1（除等待第二個(gè)時(shí)隙的標(biāo)簽）。第二個(gè)時(shí)隙若發(fā)生碰撞，將新的最高碰撞位作為詢問(wèn)命令的標(biāo)識(shí)參數(shù)繼續(xù)詢問(wèn)（詢問(wèn)命令為query）。第二個(gè)時(shí)隙若成功識(shí)別標(biāo)簽，拋出“棧”頂存放的前綴與最高碰撞位，將最高碰撞位作為詢問(wèn)命令的標(biāo)識(shí)參數(shù)進(jìn)行后退式詢問(wèn)。注意，后退式詢問(wèn)時(shí)發(fā)送的詢問(wèn)命令為re-query，所有標(biāo)簽的計(jì)數(shù)器先減1，計(jì)數(shù)器減1后為0的標(biāo)簽才能在對(duì)應(yīng)時(shí)隙響應(yīng)。因此，計(jì)數(shù)器的變化規(guī)律為：在第一個(gè)時(shí)隙，若有前綴入“棧”，計(jì)數(shù)器加1；在第二個(gè)時(shí)隙，若有前綴出“棧”，計(jì)數(shù)器減1。3)預(yù)測(cè)識(shí)別：減少標(biāo)簽響應(yīng)時(shí)隙數(shù)閱讀器對(duì)接收到的ID信號(hào)經(jīng)曼徹斯特譯碼后可逐位識(shí)別出碰撞比特。若沒(méi)有碰撞比特，則直接識(shí)別標(biāo)簽；若僅有一個(gè)碰撞比特，也可直接預(yù)測(cè)識(shí)別2個(gè)標(biāo)簽，可節(jié)省這2個(gè)標(biāo)簽響應(yīng)所需的時(shí)隙。因?yàn)閮H有一個(gè)碰撞比特時(shí)，只有2個(gè)標(biāo)簽發(fā)生碰撞，這2個(gè)標(biāo)簽的ID序列該位比特分別為‘0’和‘1’。文獻(xiàn)[7]中的算法，先將ID序列的所有比特進(jìn)行異或運(yùn)算，將運(yùn)算值加在ID序列的最高位組成一個(gè)新ID序列。當(dāng)ID碰撞信號(hào)的譯碼結(jié)果只有2個(gè)碰撞比特時(shí)，閱讀器可通過(guò)ID序列中所有未碰撞比特的異或值得到這2個(gè)碰撞比特。但這2個(gè)碰撞比特是由2個(gè)標(biāo)簽造成的，該算法中不會(huì)出現(xiàn)只有一個(gè)碰撞比特的情況。所以，只能在僅有2個(gè)碰撞比特的情況下直接識(shí)別2個(gè)標(biāo)簽。因此，該算法增加了復(fù)雜度，效果卻與本文算法相同。4)標(biāo)簽屏蔽機(jī)制：避免對(duì)已被識(shí)別的標(biāo)簽再次進(jìn)行識(shí)別在移動(dòng)閱讀器應(yīng)用中，閱讀器掃描完某一區(qū)域的標(biāo)簽后，會(huì)掃描另一個(gè)區(qū)域的標(biāo)簽。若這2個(gè)區(qū)域的重疊部分存在標(biāo)簽，它仍會(huì)掃描已被識(shí)別的標(biāo)簽（如圖2所示）。為避免再次詢問(wèn)已被識(shí)別的標(biāo)簽，本文引入一種標(biāo)簽屏蔽機(jī)制：標(biāo)簽預(yù)留一個(gè)存儲(chǔ)區(qū)，存儲(chǔ)已識(shí)別該標(biāo)簽的閱讀器的序列號(hào)（RID）。閱讀器掃描標(biāo)簽時(shí)，首先發(fā)送以該閱讀器RID為參數(shù)的初始化命令（initial）。收到該命令后，標(biāo)簽將命令中的RID與存儲(chǔ)的RID進(jìn)行比較。若相同，表明它已被該閱讀器識(shí)別，則進(jìn)入靜默狀態(tài)不再響應(yīng)；若不同，表明它未被該閱讀器識(shí)別，則用接收的RID替換原存儲(chǔ)的RID，在初始化計(jì)數(shù)器后進(jìn)行響應(yīng)。通過(guò)該機(jī)制可屏蔽已被識(shí)別的標(biāo)簽，減少對(duì)已被識(shí)別的標(biāo)簽再次識(shí)別而帶來(lái)的通信開(kāi)銷。為防止在識(shí)別過(guò)程中到達(dá)的標(biāo)簽不能被識(shí)別，本算法在一次掃描后進(jìn)行二次掃描。因?yàn)樗阉鳂?shù)算法的詢問(wèn)次數(shù)與標(biāo)簽數(shù)有關(guān)，識(shí)別過(guò)程中的新到標(biāo)簽又是少量的，所以會(huì)瞬間完成第二次掃描。二次掃描后，若沒(méi)有標(biāo)簽響應(yīng)，便停止掃描；若仍有標(biāo)簽響應(yīng)，識(shí)別完標(biāo)簽后，再次掃描，直到不再有標(biāo)簽響應(yīng)。
2低冗余搜索樹(shù)算法具體實(shí)現(xiàn)
圖3為低冗余搜索樹(shù)算法的工作流程，該流程分為3個(gè)小流程：閱讀器發(fā)送initial(RID)初始化命令，上次被成功識(shí)別的標(biāo)簽進(jìn)入靜默狀態(tài)，未被識(shí)別的標(biāo)簽初始化計(jì)數(shù)器并響應(yīng)；閱讀器開(kāi)始迭代詢問(wèn)過(guò)程，直到“棧”為空；當(dāng)“棧”為空時(shí)，再次掃描，直到無(wú)標(biāo)簽響應(yīng)，結(jié)束識(shí)別。算法主要步驟如下。1)閱讀器發(fā)送initial(RID)初始化命令，若標(biāo)簽存儲(chǔ)的RID與命令中的RID相同，則標(biāo)簽進(jìn)入靜默狀態(tài)；若不相同，則標(biāo)簽將計(jì)數(shù)器初始化為0，并發(fā)送完整ID序列作為響應(yīng)。2)閱讀器檢測(cè)是否有標(biāo)簽響應(yīng)，若無(wú)標(biāo)簽響應(yīng)，結(jié)束識(shí)別過(guò)程；若存在標(biāo)簽響應(yīng)，則對(duì)接收到的ID信號(hào)經(jīng)曼徹斯特譯碼后，確定最高碰撞位(χ)，發(fā)送以最高碰撞位為標(biāo)識(shí)參數(shù)的query(χ)詢問(wèn)命令。3)標(biāo)簽檢查計(jì)數(shù)器是否為0，計(jì)數(shù)器不為0的標(biāo)簽進(jìn)入等待狀態(tài)，不做出任何響應(yīng)；計(jì)數(shù)器為0的標(biāo)簽檢查ID序列的第χ位比特。若為比特‘0’，標(biāo)簽在第一個(gè)時(shí)隙發(fā)送ID序列的第χ位之后的低位部分；若為比特‘1’，等待第一個(gè)時(shí)隙結(jié)束后在第二個(gè)時(shí)隙發(fā)送ID序列的第χ位之后的低位部分。4)在第一個(gè)時(shí)隙，若接收到的ID序列中多于1個(gè)碰撞比特，則將ID序列最高碰撞位之前的高位部分作為前綴與最高碰撞位壓入“棧”中，并發(fā)送counter命令；否則直接識(shí)別標(biāo)簽。在第二個(gè)時(shí)隙，若接收到的ID序列中多于一個(gè)碰撞比特，確定最高碰撞位(χ)后，繼續(xù)發(fā)送query(χ)進(jìn)行迭代詢問(wèn)(即轉(zhuǎn)到步驟2))；否則直接識(shí)別標(biāo)簽。5)若在第二個(gè)時(shí)隙成功識(shí)別標(biāo)簽，閱讀器檢查“棧”是否為空。若不為空，拋出“棧”頂存放的前綴與最高碰撞位(χ)，發(fā)送re-query(χ)進(jìn)行后退式詢問(wèn)，所有標(biāo)簽的計(jì)數(shù)器減1后進(jìn)入步驟3)；若為空，進(jìn)行二次掃描(即轉(zhuǎn)到步驟1))，直到無(wú)標(biāo)簽響應(yīng)，結(jié)束識(shí)別。
3算法性能分析
1)標(biāo)簽復(fù)雜度標(biāo)簽中計(jì)數(shù)器的最大值為構(gòu)建的二叉樹(shù)深度（即標(biāo)簽ID的長(zhǎng)度），因此僅需lbk位的計(jì)數(shù)器（設(shè)標(biāo)簽ID長(zhǎng)度為k）。標(biāo)簽中的計(jì)數(shù)器替代前綴匹配電路充當(dāng)標(biāo)簽響應(yīng)詢問(wèn)命令的“觸發(fā)開(kāi)關(guān)”，相比k位前綴匹配電路，降低了標(biāo)簽復(fù)雜度。2)閱讀器的詢問(wèn)次數(shù)若有n個(gè)標(biāo)簽在閱讀器的識(shí)別區(qū)域內(nèi)，在返回式動(dòng)態(tài)搜索樹(shù)算法構(gòu)建的二叉樹(shù)中（如圖4所示），葉子節(jié)點(diǎn)（圖4中方形）的數(shù)量即為標(biāo)簽的個(gè)數(shù)n，非葉子節(jié)點(diǎn)（圖4中圓形）的總數(shù)代表碰撞的次數(shù)C(n)，所有節(jié)點(diǎn)的數(shù)量則代表閱讀器詢問(wèn)總數(shù)Q，且有如下公式本算法采用了“一問(wèn)兩答”的詢問(wèn)方式，遇到碰撞時(shí)，只需詢問(wèn)一次。因此，詢問(wèn)總數(shù)即為碰撞次數(shù)（非葉子節(jié)點(diǎn)）加第一次初始化詢問(wèn)，且本算法采用了預(yù)測(cè)識(shí)別，在只有一個(gè)碰撞比特的碰撞節(jié)點(diǎn)（圖4中陰影圓形），不必再進(jìn)行詢問(wèn)即可識(shí)別2個(gè)標(biāo)簽(圖4中陰影方形)。因此，詢問(wèn)總數(shù)再減去只有一個(gè)碰撞比特的碰撞節(jié)點(diǎn)數(shù)。若只有一個(gè)碰撞比特的碰撞節(jié)點(diǎn)數(shù)為m(m≤floor(n/2)，floor為向下取整)，則本算法的詢問(wèn)總數(shù)為3)詢問(wèn)命令中標(biāo)識(shí)參數(shù)的長(zhǎng)度當(dāng)前的算法采用前綴作為詢問(wèn)命令的標(biāo)識(shí)參數(shù)，若標(biāo)簽的ID序列為k位，則詢問(wèn)命令中標(biāo)識(shí)參數(shù)的平均長(zhǎng)度為從式(4)和式(5)可看出L明顯小于L，且隨著k的增加，它們的差距也隨之增大。4)通信開(kāi)銷為公平對(duì)比，不考慮在移動(dòng)閱讀器應(yīng)用中，標(biāo)簽屏蔽機(jī)制帶來(lái)的明顯收益。假設(shè)除標(biāo)識(shí)參數(shù)外詢問(wèn)命令的其他字段為sbit，標(biāo)簽響應(yīng)時(shí)附加的前導(dǎo)碼等信息為tbit。因標(biāo)簽在響應(yīng)時(shí)只發(fā)送ID序列最高碰撞位之后的低位部分，所以每個(gè)響應(yīng)標(biāo)簽平均發(fā)送的ID序列為L(zhǎng)bit(式(4))，則返回式動(dòng)態(tài)搜索樹(shù)算法識(shí)別n個(gè)標(biāo)簽所需的通信開(kāi)銷為比對(duì)式(6)和式(7)，可看出S小于S，且隨n、k的增加，它們的差距也隨之增大。因此本算法明顯降低了識(shí)別標(biāo)簽所需的通信開(kāi)銷。
4算法仿真與分析
本文從詢問(wèn)次數(shù)、詢問(wèn)命令長(zhǎng)度、吞吐率與通信開(kāi)銷4個(gè)方面，將LRST算法與RDBST算法[6]和FST算法[7]進(jìn)行性能比較。為簡(jiǎn)單起見(jiàn)，仿真中不考慮控制、前后綴和校驗(yàn)冗余等帶來(lái)的通信開(kāi)銷，而主要將詢問(wèn)命令中的標(biāo)識(shí)參數(shù)與標(biāo)簽發(fā)送的ID序列作為識(shí)別標(biāo)簽所需的通信開(kāi)銷，并定義吞吐率為標(biāo)簽總數(shù)與識(shí)別標(biāo)簽所需的總時(shí)隙數(shù)之比。因識(shí)別過(guò)程與標(biāo)簽群的ID分布有關(guān)，分別對(duì)16位ID隨機(jī)分布、連續(xù)分布2種情況進(jìn)行仿真。從圖5和圖6可看出，標(biāo)簽群的ID無(wú)論是隨機(jī)分布還是連續(xù)分布，LRST算法的詢問(wèn)次數(shù)都少于其他2種算法，且僅為FST算法的一半。這表明本算法提出的“一問(wèn)兩答”詢問(wèn)方式可使整個(gè)詢問(wèn)過(guò)程的詢問(wèn)次數(shù)減少一半。圖7為前綴、最高碰撞位分別作為詢問(wèn)命令標(biāo)識(shí)參數(shù)的情況下，標(biāo)識(shí)參數(shù)長(zhǎng)度的變化曲線。LRST算法采用計(jì)數(shù)器作為標(biāo)簽響應(yīng)的“觸發(fā)開(kāi)關(guān)”，詢問(wèn)命令的標(biāo)識(shí)參數(shù)為最高碰撞位。從圖7可看出，當(dāng)ID序列的長(zhǎng)度翻倍時(shí)，詢問(wèn)命令的標(biāo)識(shí)參數(shù)僅需增加一個(gè)比特；而其他2種算法采用前綴匹配電路作為標(biāo)簽響應(yīng)的“觸發(fā)開(kāi)關(guān)”，則需將前綴作為詢問(wèn)命令的標(biāo)識(shí)參數(shù)，當(dāng)ID序列的長(zhǎng)度翻倍時(shí)，詢問(wèn)命令的平均標(biāo)識(shí)參數(shù)也隨之翻倍。當(dāng)ID序列為16bit時(shí)，LRST算法采用最高碰撞位作為詢問(wèn)命令的標(biāo)識(shí)參數(shù)僅需4bit，而其他2種算法采用前綴作為標(biāo)識(shí)參數(shù)平均需9bit。這表明采用最高碰撞位替代前綴作為詢問(wèn)命令的標(biāo)識(shí)參數(shù)可大大減小詢問(wèn)命令的長(zhǎng)度。從圖8可看出，RDBST算法的吞吐率(u)接近50%，符合理論公式：u=n/(2n−1)。FST算法與LRST算法的吞吐率明顯高于RDBST算法的吞吐率,由吞吐率定義可知，預(yù)測(cè)識(shí)別明顯減少了時(shí)隙數(shù)。從圖9可看出，RDBST算法的吞吐率仍為50%，LRST算法與FST算法的吞吐率接近1。這說(shuō)明預(yù)測(cè)識(shí)別可利用標(biāo)簽群ID的分布特性，提高吞吐率。從圖8和圖9可看出，LRST算法與FST算法的吞吐率曲線基本重合。這表明2種預(yù)測(cè)識(shí)別在減少時(shí)隙數(shù)方面基本相同，因此，LRST算法中的簡(jiǎn)單預(yù)測(cè)識(shí)別可替代FST算法中的復(fù)雜預(yù)測(cè)識(shí)別。圖10和圖11為系統(tǒng)識(shí)別標(biāo)簽所需的通信開(kāi)銷，通信開(kāi)銷可反映時(shí)延與功耗[8,9]。從圖10可看出LRST算法的通信開(kāi)銷明顯低于其他2種算法。LRST算法的通信開(kāi)銷比RDBST算法降低了約42%，比FST算法降低了約38%。標(biāo)簽群的ID續(xù)分布時(shí)，LRST算法達(dá)到最優(yōu)。從圖11可看出，LRST算法的通信開(kāi)銷比RDBST算法降低了約69%，比FST算法降低了約39%。這表明標(biāo)簽群的ID無(wú)論是隨機(jī)分布還是連續(xù)分布，LRST算法都明顯降低了通信開(kāi)銷。由仿真可看出，當(dāng)標(biāo)簽群的ID連續(xù)分布時(shí)，LRST算法表現(xiàn)出更好的優(yōu)越性。在很多應(yīng)用中，標(biāo)簽群的ID是連續(xù)分布的，例如倉(cāng)庫(kù)管理、生產(chǎn)線等。有些算法加入預(yù)處理機(jī)制[10]或者鎖定發(fā)生碰撞的比特后再執(zhí)行搜索樹(shù)算法[11]，每次詢問(wèn)后將ID序列中未識(shí)別的部分組成一個(gè)新ID，以達(dá)到減少傳輸比特的目的。它只能在識(shí)別少量標(biāo)簽時(shí)，節(jié)省某些比特。在識(shí)別大量同類商品的標(biāo)簽時(shí)，節(jié)省的仍是ID序列高位部分的比特。因此，這種機(jī)制增加了標(biāo)簽復(fù)雜度，卻得不到很好的效果。
5結(jié)束語(yǔ)
本文研究了RFID系統(tǒng)中的標(biāo)簽防碰撞算法，對(duì)搜索樹(shù)算法及其改進(jìn)算法進(jìn)行了分析，并在此基礎(chǔ)上提出了一種低冗余搜索樹(shù)防碰撞算法。該算法能大幅度減少閱讀器的詢問(wèn)次數(shù)和詢問(wèn)命令中標(biāo)識(shí)參數(shù)的長(zhǎng)度，從而降低了系統(tǒng)的通信開(kāi)銷，減小了時(shí)延，降低了功耗。當(dāng)接收到的ID序列中只有一個(gè)碰撞比特時(shí)，可直接識(shí)別2個(gè)標(biāo)簽，進(jìn)一步減少了時(shí)隙總數(shù)，提高了吞吐率。仿真結(jié)果表明，標(biāo)簽群的ID無(wú)論隨機(jī)分布還是連續(xù)分布，本算法都提高了吞吐率，且明顯降低了通信開(kāi)銷。因此，本算法能夠迅速有效地識(shí)別標(biāo)簽。
作者：黃瓊凌江濤張敏陽(yáng)小龍單位：重慶郵電大學(xué)移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室北京科技大學(xué)先進(jìn)網(wǎng)絡(luò)技術(shù)與新業(yè)務(wù)研究所