一種標簽防沖突算法設計

周 曉，曹美玲，李 杰，邊裕挺

（1.浙江工業(yè)大學 信息工程學院，浙江 杭州 310032；2.浙江工業(yè)大學 計算機科學與技術(shù)學院，浙江 杭州 310032）

一種標簽防沖突算法設計

周 曉1，曹美玲2，李 杰1，邊裕挺1

（1.浙江工業(yè)大學 信息工程學院，浙江 杭州 310032；2.浙江工業(yè)大學 計算機科學與技術(shù)學院，浙江 杭州 310032）

針對RFID系統(tǒng)中，多個標簽使用共享信道與讀寫器通信引起的標簽信號沖突問題，提出了具有捎帶檢測技術(shù)的標簽防沖突算法SRPD-ABS，能夠?qū)崿F(xiàn)多標簽信號的讀取，完成多目標識別.SRPD-ABS算法基于ABS算法思想，采用捎帶檢測技術(shù)，不但能夠避免滯留標簽之間的沖突，還能避免新到標簽和滯留標簽的沖突，減少空閑時隙的產(chǎn)生，從而縮短識別延遲.通過仿真，和ABS算法對比發(fā)現(xiàn)，SRPD-ABS算法具有更好的識別性能.

防沖突算法；RFID；智能交通；離開率；到達率

射頻識別（Radio frequency identification，RFID）技術(shù)是一種自動識別技術(shù)，廣泛應用在智能交通、物流、零售及醫(yī)療等領域，是物聯(lián)網(wǎng)發(fā)展的重要技術(shù)之一.典型的RFID系統(tǒng)，通常包括一個讀寫器和若干個有唯一ID的標簽.讀寫器和標簽采用無線射頻的方式通信，通過讀取標簽ID，獲得標簽數(shù)據(jù)信息［1］.通信時，在上行鏈路，多個標簽共享同一條通信信道，可能會造成信道訪問沖突，因此在通信過程中，需要有高效的防沖突算法，減少沖突，降低誤讀率和漏讀率，提高系統(tǒng)的性能.

現(xiàn)有的標簽防沖突算法采用時分多址（Time division multiple access，TDMA）思想，分為兩大類，分別是基于Aloha的防沖突算法和基于二進制樹的防沖突算法.基于Aloha的防沖突算法有純Aloha［2］、時 隙 Aloha（Slotted aloha，SA）［2－3］、幀 時 隙Aloha（Frame slotted aloha，F(xiàn)SA）［3］和動態(tài)幀時隙Aloha（Dynamic framed slotted aloha，DFSA）［3］.基于 Aloha算法能夠避免部分沖突，提高讀寫器的工作效率，但是隨著標簽數(shù)量的增加，該算法存在不穩(wěn)定性，容易引起標簽饑餓等問題，因此以二進制樹為基礎的算法獲取了更好的應用.典型基于二進制樹的算法有基本二進制樹算法（Binary tree，BT）［4］、查詢二進制樹算法（Query tree，QT）［5］、動態(tài)二進制樹分裂算法（Adaptive binary splitting，ABS）［6－7］.

在RFID技術(shù)的應用中，通常讀寫器需要重復識別標簽，并且讀寫器可讀范圍內(nèi)標簽的數(shù)量是變化的.在讀寫過程中，有些標簽存在于當前讀寫周期，但不存在于下個讀寫周期，被稱為離開標簽；有些標簽既存在于當前讀寫周期又存在于下個讀寫周期，叫做滯留標簽；只存在于下個讀寫周期的標簽被稱為新到標簽.Jihoon Myung和 Wonjun Lee提出的ABS算法能夠完全避免滯留標簽之間的沖突，但是不能避免滯留標簽和新到標簽的沖突，當離開標簽較多時，會造成很多空閑時隙.因此筆者基于ABS算法思想，提出了具有捎帶檢測功能的標簽防沖突算法（Self regulation piggyback detect ABS，SRPD-ABS），不但能夠避免滯留標簽的沖突，而且能夠避免滯留標簽和新到標簽的沖突，還能夠利用捎帶檢測技術(shù)，提前對下個時隙進行調(diào)整，在不增加沖突時隙的同時，能夠更多的減少空閑時隙，縮短識別延遲，提高識別效率.

1 SRPD-ABS算法設計

ABS算法在基于二進制樹的算法中，有較好的防沖突性能，但是該算法只能避免滯留標簽之間的沖突，不能避免滯留標簽和新到標簽的沖突，并且離開標簽過多時，會造成更多空閑時隙.筆者提出的SRPD-ABS算法不但能夠避免滯留標簽和新到標簽的沖突，而且能夠利用捎帶檢測技術(shù)，檢測下個時隙是不是有標簽響應.所謂捎帶檢測指在當前時隙，讀寫器除讀取本時隙要讀取的標簽的ID外，還能根據(jù)是否收到下個時隙要發(fā)送ID的標簽的“存在”信號，向標簽發(fā)送一個指令，標簽看到指令，如果下個時隙沒有標簽發(fā)送ID，新到達的標簽自動進行調(diào)整，滿足條件的標簽發(fā)送ID，這樣能夠避免部分空閑時隙，提高信道的利用率.算法具體思想如下：第一個周期，SRPD-ABS和ABS執(zhí)行過程相同.在Ci（i＝2，…，n）周期，每個標簽有三個變量 PSC，ASC和TSCi－1，PSC表示在當前周期已經(jīng)識別的標簽的個數(shù)；ASC指示標簽在哪個時隙發(fā)送自己的ID，TSCi－1標識上個周期識別結(jié)束時的TSC值.讀寫器有三個變量PSC，TSC和TSCi－1.讀寫器的PSC和TSCi－1變量定義同標簽，并且有相同的值，TSC用來標識最大的ASC值.按照文獻［8］的標簽估計策略，估計新到標簽的個數(shù)，新到標簽的個數(shù)用New-count表示，新到標簽的ASC為1～New-count中一個隨機數(shù)加TSC值.滯留標簽保留上個周期的ASC值.

對讀寫器回饋信號作如下定義［9］：

I，0：空閑時隙，且沒有未被識別的新到標簽.

I，1：空閑時隙，且有未被識別的新到標簽.

C：沖突時隙，有兩個或兩個以上的標簽響應.

R，0：當前時隙可讀，下個時隙沒有標簽響應.

R，1：當前時隙可讀，下個時隙有標簽響應.

識別過程中ASC＝PSC的標簽發(fā)送ID，ASC＝PSC＋1的標簽發(fā)送“存在”信號.讀寫器檢測到標簽的信號，根據(jù)標簽信號發(fā)出回饋信號，標簽根據(jù)回饋信號，調(diào)整PSC和ASC的過程如下：

I，0：如果標簽的ASC＞PSC，ASC＝ASC－1.

I，1：如果標簽的 ASC＝TSCi－1＋1，ASC＝PSC；如果標簽的ASC＞TSCi－1＋1，ASC＝ASC－1.

C：標簽隨機選擇0或1，如果標簽選擇1，當PSC≤TSCi－1時，陷入沖突的標簽 ASC＝TSCi－1＋1，沒有陷入沖突且ASC＞TSCi－1＋1的標簽，ASC＝ASC＋1；當PSC＞TSCi－1時，如果標簽 ASC≥PSC，標簽 ASC＝ASC＋1.如果標簽選擇0，ASC不變.

R，0：標簽的識別個數(shù)計數(shù)器PSC＝PSC＋1，當PSC≤TSC時，如果 ASC＝TSCi－1＋1，ASC＝PSC，如果ASC＞TSCi－1＋1，ASC＝ASC－1.

R，1：標簽的識別個數(shù)計數(shù)器PSC＝PSC＋1.

讀寫器操作部分，當PSC≤TSC時，讀寫器收到標簽的信號，判斷當前狀態(tài).如果有兩個或兩個以上標簽發(fā)送ID，發(fā)生沖突，讀寫器發(fā)送回饋信號“C”；如果只有一個標簽發(fā)送ID，讀寫器接收標簽ID，PSC＝PSC＋1，如果PSC＞TSCi－1＋1，TSC＝TSC＋1，讀寫器再檢測有沒有標簽發(fā)送“存在”信號，如果有，讀寫器發(fā)送回饋“R，1”；否則，發(fā)送“R，0”.如果沒有標簽發(fā)送ID，當空閑時，如果有新到?jīng)]被識別的標簽，讀寫器發(fā)送“I，1”，如果新到標簽都已識別完，讀寫器發(fā)送“I，0”，并令TSC－1.

2 算法性能分析

為了進一步研究SRPD-ABS算法性能，本節(jié)對ABS算法和SRPD-ABS算法識別延遲進行分析［9］.

2.1 ABS算法

假設在C1識別周期，有n個標簽，DABS（C1）為C1周期的總的識別延遲，這個周期的識別延遲和BT算法相同，有

式中：DC，DR，DI分別為沖突時隙、可讀時隙和空閑時隙數(shù)，并且DR＝n，有

標簽的識別過程是一個馬爾可夫過程［10］，因此在Ci（i＝2，…，n）周期，需要有上個周期的識別結(jié)果作為依據(jù).在Ci（i＝2，…，n）周期，所有要識別的標簽分為兩類，滯留標簽和新到標簽，這兩類標簽的個數(shù)是影響識別延遲的重要參數(shù)，Ci周期的識別延遲不能簡單用公式（2）來表示.文獻［6－7］中，假設DABS（Ci｜Ci－1）為Ci周期總的識別延遲，離開的標簽為β個，新到的標簽為α個，則有

2.2 SRPD-ABS算法

在C1周期，SRPD-ABS算法和ABS算法具有相同的識別延遲，下面對Ci（i＝2，…，n）周期進行分析.

在Ci周期，假設DSRPD－ABS（Ci｜Ci－1）為Ci周期總的識別延遲，離開標簽為β個，新到標簽為α個，有

證明：Ci－1周期識別結(jié)束，因為有β離開標簽，那么就會有n－β滯留標簽，因此首先需要n－β可讀時隙.當α＞β時，新到標簽中，有β個填補離開標簽所致的空閑時隙，剩下的α－β個新到標簽的識別延遲等于采用ABS算法的識別延遲.當α＜β時，所有新到標簽都在離開標簽形成的空閑時隙完成，另外還會有β－α個空閑時隙.兩種情況下，標簽選擇識別時隙均服從二項分布，因此得到公式（4）.

2.3 仿真結(jié)果分析

下面通過算法仿真，對SRPD-ABS算法和ABS算法進行分析比較.RFID標簽防碰撞算法通常把碰撞時隙、空閑時隙和可讀時隙作為重要的衡量指標.在標簽的識別過程中，到達率和離開率是影響識別時隙重要參數(shù).

圖1以離開率和到達率作為變量，模擬兩個變量對SRPD-ABS算法和ABS算法的識別延遲的影響.圖1中曲面2表示SRPD-ABS算法的識別延遲，曲面1表示ABS算法的識別延遲.假設上個周期識別500個標簽，由圖1可以知，離開率在0.64～1之間時，ABS在部分區(qū)域略勝一籌，離開率在0～0.64之間時，SRPDABS遠遠好于ABS.到達率和識別延遲之間呈線性關(guān)系，隨著到達率的增加，識別延遲也在增加.

圖1 離開率和到達率對識別延遲的影響（n＝500）Fig.1 The effection on identification delay of leaving ratio and arriving ratio（n＝500）

3 結(jié) 論

在RFID系統(tǒng)中，由于多個標簽同時與讀寫器通信引起沖突，導致更大的識別延遲，筆者基于ABS算法的基本思想，提出其改進算法SRPD-ABS算法，利用捎帶檢測技術(shù)，根據(jù)前一個周期的識別結(jié)果，提前一個時隙檢測下個時隙標簽的響應情況，如果發(fā)現(xiàn)空閑，可以提前做出調(diào)整，避免更多空閑時隙的產(chǎn)生.根據(jù)仿真結(jié)果，模擬實際應用環(huán)境，SRPDABS算法產(chǎn)生比ABS算法少的沖突時隙和空閑時隙，有效減少識別延遲，提高識別效率.

［1］FINKENZELLER K.射頻識別（RFID）技術(shù)［M］.陳大才，譯.北京：電子工業(yè)出版社，2001.

［2］TAO Cheng，LI Jin.Analysis and simulation of RFID anti-collision algorithms［C］／／International Conference on Advanced Communication Technology.New York：IEEE Press，2007：697-701.

［3］SHIH D H，SUN P L，YEN D C.Taxonomy and survey of RFID anti-collision protocols［J］.Computer Communications，2006，29（11）：2150-2166.

［4］CHEN W C，HORNG S J，F(xiàn)AN Ping-zhi.An enhanced anticollision algorithm in RFID based on counter and stack［C］／／Second International Conference on Systems and Networks Communications.New York：IEEE Press，2007：21-24.

［5］WANG T P.Enhanced binary search with cut-through operation for anti-collision in RFID systems［J］.IEEE Communication Letters，2006，10（4）：236-238.

［6］MYUNG J，LEE W J.Adaptive binary splitting for efficient RFID tag anti-collision［J］.IEEE Communication Letters，2006，10（3）：144-146.

［7］LAI Y C，LIN C C.Two blocking algorithms on adaptive binary splitting：single and pair resolutions for RFID tag identi？cation［J］.IEEE／ACM Transactions on Networking，2009，17（3）：962-975.

［8］EOM J，LEE T J.Frame-slotted Aloha with estimation by pilot frame and identification by binary selection for RFID anti-collision［C］／／International Symposium on Communications and Information Technologies.New York：IEEE Press，2007：1027-1031.

［9］CAO Mei-ling，ZHOU Xiao，ZHU Yi-hua.An anti-collision algorithm for RFID tags based on adaptive binary splitting［C］／／International Conference on Computer and Electrical Engineering.New York：IEEE Press，2010：307-311.

［10］VOGT H.Efficient object identification with passive RFID tags［C］／／International Conference on Systems，Man and Cybernetics.New York：IEEE Press，2002：98-113.

A design of tag anti-collision algorithm

ZHOU Xiao1，CAO Mei-ling2，LI Jie1，BIAN Yu-ting1
（1.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310032，China；2.College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310032，China）

To solve the problem of signal collision，which is caused by multiple labels using a shared channel with the tag reader communication signal，in RFID （Radio Frequency Identification）system，a new tag anti-collision algorithm—SRPD-ABS（Self Regulation Piggyback Detect ABS）is proposed.It can read multi-tag signal and identify multi targets from them.SRPD-ABS algorithm is proposed based on ABS （Adaptive Binary Splitting）.The piggyback detect technique is used in it.It can not only avoid conflict between the staying tags，but also avoid collision between the new arriving tags and the staying tags.It can also reduce the idle time slot and shorten the identification delay.Through simulation，SRPD-ABS has a better performance than ABS.

anti-collision algorithm；RFID；intelligent transportation；leaving ratio；arriving ratio

TN911

A

1006-4303（2011）06-0679-04

2010-09-25

浙江省自然科學基金資助項目（Y107618）；浙江省科技廳資助項目（2008C21144）

周 曉（1971—），男，浙江永康人，副教授，博士，研究方向為自組織網(wǎng)絡與智能交通，E-mail：zx＠zjut.edu.cn.

（

陳石平）