朱林海，李 鴻，陳凌宇

（長沙理工大學 電氣與信息工程學院，湖南 長沙410114）

0 引 言

由于射頻識別 （RFID）系統(tǒng)存在多個標簽處于閱讀器范圍內(nèi)且共用同一個信道，標簽在響應(yīng)閱讀器時會產(chǎn)生碰撞，導(dǎo)致識別失敗、降低傳輸效率的問題，如何有效地處理該問題是提高射頻識別系統(tǒng)性能的關(guān)鍵。

基于時分多路存儲技術(shù)的防碰撞算法有2類：隨機算法和確定性算法。隨機算法包括純ALOHA 算法、時隙ALOHA 算法等，這類算法標簽的響應(yīng)是隨機的，有可能長時間都未能得到識別，會產(chǎn)生 “Tag starvation”問題，導(dǎo)致系統(tǒng)效率也很低，只能適用于少量的標簽的場合。確定性算法典型的是樹型算法，包括后退式二進制樹算法、四元偵測查詢樹算法等，該類型算法只要時間足夠，能成功識別每一個標簽。其中，后退式二進制樹算法每次只能生成2個子集，一旦標簽數(shù)量過大，就會產(chǎn)生大量的碰撞時隙，使得系統(tǒng)的性能大大降低；四元預(yù)先偵測查詢樹算法雖然每次分裂生成4個子集且完全清除了空閑時隙，但是沒有很有效地解決大量標簽情況下的碰撞問題，標簽響應(yīng)閱讀器時，標簽返回的信息含有沒有發(fā)生碰撞的位，即傳輸了沒必要傳輸?shù)臄?shù)據(jù)位，使得通信量沒得到明顯的改善，閱讀器的詢問次數(shù)也沒明顯的減少，系統(tǒng)的吞吐率依舊不高。為了解決這些問題，本文提出了改進的預(yù)先偵測查詢樹防碰撞算法。

1 多標簽防碰撞算法

1.1 BBS算法

文獻 ［1］提出了后退式二進制樹算法 （BBS），該算法在閱讀器成功識別一個標簽后后退到上一層碰撞父節(jié)點開始搜索，閱讀器發(fā)送請求命令即序列號，當標簽的ID 號小于序列號或者等于序列號的標簽都對該請求命令進行響應(yīng)，并且標簽返回自身整個ID 號，如果發(fā)生了碰撞，則把最高碰撞位置 “0”，碰撞位后置 “1”，得到下一次請求命令序列，繼續(xù)上一步驟；如果沒發(fā)生碰撞，則表明閱讀器成功識別了該標簽，閱讀器再發(fā)送命令使其處于睡眠狀態(tài)，并后退到上一碰撞節(jié)點得到下一次請求命令序列，繼續(xù)以上操作。

1.2 PDQT算法

文獻 ［2］中的PDQT 算法在四元查詢樹的基礎(chǔ)上引入了時隙預(yù)先偵測信號技術(shù)，結(jié)合了時隙預(yù)先偵測信號的機制，能夠根據(jù)偵測的情況確定標簽是否有應(yīng)答。射頻識別系統(tǒng)的閱讀器發(fā)現(xiàn)標簽在應(yīng)答的過程中產(chǎn)生了碰撞，會把查詢字符串擴展2位即00、01、10和11，假設(shè)形成新的查詢字串為01 00、01 01、01 10、01 11，利用時隙預(yù)先偵測信號技術(shù)，偵測并判斷標簽的應(yīng)答情況，刪除不需要的擴展后的新查詢字串［2］，如果01 10空閑，就把01 10刪除，需要的擴展后的新查詢字串01 00、01 01和01 11置入等待查詢序列中，然后閱讀器發(fā)送帶有該查詢字串的查詢命令，繼續(xù)以上步驟，直到每個標簽被識別，其中01為上一次查詢的字串。

2 改進的預(yù)先偵測查詢樹防碰撞算法

2.1 算法的優(yōu)化

改進的預(yù)先偵測查詢樹防碰撞算法采用曼切斯特（Manchester）編碼，能準確的判斷標簽的碰撞位。該算法做出了以下改進：

（1）對需要識別的標簽進行一次預(yù)處理，把各標簽ID的碰撞位提取出來，作為新的ID 與閱讀器通信，并且結(jié)合動態(tài)二進制算法，標簽返回的信息是除去閱讀器發(fā)送查詢字串即前綴的剩余ID 位，這樣大大的減少了系統(tǒng)的傳輸位數(shù)。

（2）采用八叉樹詢問代替原算法的四叉樹詢問，減少了標簽的碰撞數(shù)目，提高了算法的效率。

（3）利用后退式搜索與堆棧存儲的方法以避免重復(fù)搜索和冗余搜索，閱讀器成功識別標簽后直接后退到上一層父節(jié)點搜索，而不是根節(jié)點，減少了詢問次數(shù)。

2.2 算法的原理

本文提出的算法通過提取碰撞位信息來構(gòu)建新的ID號，然后與閱讀器通信，在引入PDQT 算法的時隙預(yù)先偵測信號機制的基礎(chǔ)上，從原算法的4 個偵測時隙增加到8個偵測時隙，分別為dts1、dts2、dts3、dts4、dts5、dts6、dts7、dts8。在預(yù)先偵測機制中，閱讀器發(fā)送查詢的請求命令后，偵測前面8個偵測時隙，根據(jù)偵測時隙中是否含有前偵測信號來判斷標簽是否出現(xiàn)碰撞情況以及空閑狀況。如圖1和圖2 所示，假設(shè)標簽已經(jīng)經(jīng)過提取碰撞位處理，就最后一層的標簽而言，dts2、dts3、dts4、dts5檢測到前偵測信號，分別表示有符合查詢前綴011 001、011 010、011 011、011 100 的標簽存在；dts1、dts6、dts7、dts8 沒有檢測到前偵測信號，分別表示沒有符合查詢前綴011 000、011 101、011 110、011 111的標簽的存在，其中011為上一次的查詢前綴。這樣閱讀器可以知曉在下一次的查詢命令，并且只發(fā)送查詢前綴給存在的標簽，因此閱讀器會選擇新的查詢前綴011 001、011 010、011 011、011 100。閱讀器不會發(fā)送查詢前綴給不存在的標簽，這樣就刪除了空閑時期，減少了閱讀器的查詢次數(shù)。

圖1 改進的四元查詢樹算法實例

圖2 時隙前偵測信號技術(shù)實例

算法還利用了后退式索引與堆棧技術(shù)，把擴展后的查詢前綴置入棧中，閱讀器取棧頂前綴發(fā)送。

2.3 算法約定

本算法需要以下6 種基本基本指令：Request（null）、Request（prefix）、Select（prefix）、Rw－data、Unselect 和Ext－Collision－Bit.

（1）Request（null）—請求命令，作用范圍的每一個標簽都響應(yīng)閱讀器，標簽返回整個ID 號。

（2）Request（prefix）—請求命令，其中prefix為查詢前綴，即擴展后的新的查詢字串，滿足查詢前綴的標簽響應(yīng)。

（3）Select（prefix）—選擇指令，標簽的前綴跟閱讀器發(fā)送的前綴一致，響應(yīng)選擇這個命令請求。

（4）Rw－date—讀取數(shù)據(jù)指令，閱讀器成功識別標簽后，讀取標簽的ID 值。

（5）Unselect—退出選擇命令，被識別的標簽處于退選狀態(tài)，使得標簽處于休眠狀態(tài)，不在響應(yīng)任何指令，要重新激活必須使得標簽重新進入閱讀器范圍。

（6）Extract－Collision－Bit—提取各標簽的碰撞位信息發(fā)至各標簽，標簽返回有碰撞標記的位作為新的ID 與閱讀器通信。

2.4 算法步驟

步驟1 閱讀器發(fā)送Request（null），作用范圍類每一個標簽都響應(yīng)該請求命令，并返回ID 中每一位，閱讀器檢測沖突位，把沖突位標記為 “1”，無沖突位標記 “0”，并初始化查詢棧Q。

步驟2 閱讀器發(fā)送Extract－Collision－Bit指令，沖突信息發(fā)送給標簽，標簽返回有沖突標記的位作為新的ID與閱讀器通信。

步驟3 標簽的應(yīng)答產(chǎn)生碰撞，在上一次查詢前綴的基礎(chǔ)上擴展3位，形成新的查詢前綴，然后利用時隙預(yù)先偵測信號技術(shù)，刪除不需要的前綴，其他需要的前綴置入棧Q。

步驟4 閱讀器取棧頂Q 中的前綴并發(fā)送，如果在應(yīng)答的時候沒有標簽產(chǎn)生碰撞，閱讀器發(fā)送指令使其休眠，則識別成功；如果標簽在應(yīng)答時產(chǎn)生了碰撞，返回步驟3。

步驟5 判斷棧Q 是否為空，如果不為空，返回步驟4；如果為空，則算法結(jié)束。

2.5 算法舉例

下面通過一個實例來詳細說明算法的實現(xiàn)過程，假設(shè)有5 個10 位的標簽待識別，分別為tag1：1000011011；tag2：1100101011；tag3：1100111010；tag4：1100111110；tag5：1101111010。算法的執(zhí)行過程如下：

（1）閱讀器發(fā)送Request（null），，閱讀器作用范圍的標簽響應(yīng)，ID 的每一位都都返回來，閱讀器檢測碰撞位信息，把有沖突位標記為 “1”，無沖突位標記為 “0”。

（2）閱讀器發(fā)送Extract－Collision－Bit指令，tag1、tag2、tag3、tag4、tag5 形 成 新 的ID，分 別 為000101、101001、101100、101110、111100，并與閱讀器通信。

（3）查詢前綴擴展3位，利用預(yù)先偵測技術(shù)，刪除不需要的前綴001、010、011、100、110，需要的前綴000、101、111壓入棧Q 中。閱讀器讀取棧Q 中查詢前綴000，生成請求命令Request（000）。

（4）閱讀器發(fā)送Request（000），此時僅有tag1應(yīng)答，tag1被正確識別，閱讀器發(fā)送Unselect指令，讓其處于休眠狀態(tài)。閱讀器讀取棧Q 中101，生成新的請求命令Request（101）。

（5）閱 讀 器 發(fā) 送Request （101），此 時tag2、tag3、tag4應(yīng)答，產(chǎn)生了碰撞，在上一次查詢前綴的基礎(chǔ)上，擴展3 位，得到新的查詢前綴101000、101001、101010、101011、101100、101101、101110、101111，利用預(yù)先偵測技術(shù)，刪除101000、101010、101011、101101、101111這些不需要的查詢前綴，需要的查詢前綴101001、101100、101110壓入棧Q 中。閱讀器取棧Q 中的101001，生成新的請求命令Request（101001）。

（6）閱讀器發(fā)送Request（101001），此時僅有tag2成功識別，閱讀器發(fā)送指令使其休眠。閱讀器讀取棧Q 中查詢前綴101100，生成命令Request（101100）。

（7）閱讀器發(fā)送Request（101100），此時僅有tag3成功識別，閱讀器讀取其數(shù)據(jù)，并發(fā)送指令使其休眠。閱讀器讀取棧Q 中101110，生成命令Request（101110）。

（8）閱讀器發(fā)送Request（101110），此時只有tag4響應(yīng)，成功識別，閱讀器讀取數(shù)據(jù)，發(fā)送指令使其休眠。閱讀器讀取棧Q 中查詢前綴111，生成命令Request（111）。

（9）閱讀器發(fā)送Request（111），此時只有tag5響應(yīng)，成功識別，閱讀器讀取其數(shù)據(jù)，發(fā)送指令使其休眠。棧Q為空，識別結(jié)束。

3 實驗分析與仿真

通過時隙數(shù)和吞吐率的計算，對本文的算法的性能進行分析。但是一般情況下很難得到一個精確的公式來計算。

本文算法利用了預(yù)先偵測查詢樹的方法，刪除了空閑時隙，因此算法的總時隙為

系統(tǒng)的吞吐率為

本文的算法是基于PDQT 算法的基礎(chǔ)提出來的，并且BBS算法又是比較經(jīng)典的二進制樹型算法，因此把本文提出的算法和這2種算法進行了相互之間的比較。利用Matlab仿真軟件對以上3種算法進行理想情況下的仿真實驗。仿真過程中系統(tǒng)的標簽假設(shè)分布是均勻的，并且系統(tǒng)采用32位EPC編碼的電子標簽。在相同的仿真環(huán)境下，仿真結(jié)果取20次的實驗平均值，分別比較了PDQT、BBS、本文的算法的查詢次數(shù)、吞吐率和通信量，如圖3、圖4、圖5所示。仿真結(jié)果可以看到，本文改進的算法，有效的減少了詢問次數(shù)、總的傳輸位數(shù)，系統(tǒng)的效率也就是吞吐率也有了很大的改善，實驗結(jié)果表明，本文改進的算法提升了整個RFID 系統(tǒng)的性能。

圖3 查詢次數(shù)的比較

圖4 吞吐率的比較

圖5 總傳輸位數(shù)的比較

4 結(jié)束語

本文提出了一種改進的預(yù)先偵測查詢樹防碰撞算法，創(chuàng)造性地結(jié)合了多種方法，包括八元查詢樹、提取碰撞位、預(yù)先偵測查詢樹、后退式索引、堆棧。這些方法的綜合，無論是閱讀器的詢問次數(shù)、通信量，還是系統(tǒng)的吞吐率都達到了理想的效果，比改進前的算法，具有優(yōu)越性。當電子標簽的長度和數(shù)量逐漸增加時，本文提出的算法的性能的優(yōu)勢就更明顯。因此，該算法具有一定的實用性和創(chuàng)新性。

［1］YU Songsen，ZHAN Yiju，PENG Weidong，et al.An anticollision based on binary tree searching of regressive index and its practice［J］.Computer Engineering and Application，2004，40 （16）：26－28 （in Chinese）. ［余 松 森，詹 宜 巨，彭 衛(wèi) 東，等.基于后退索引的二進制樹形搜索防碰撞算法及其實現(xiàn)［J］.計算機工程與應(yīng)用，2004，40 （16）：26－28.］

［2］WANG Quan，HUA Nan.A new anticollision algorithm based on the quaternary query tree a algorithm ［J］.Journal of Air Force Engineering University （Natural Science Edition），2012，13 （6）：75－79 （in Chinese）.［王荃，滑楠.基于四元查詢樹算法的改進防碰撞算法 ［J］.空軍工程大學學報 （自然科版），2012，13 （6）：75－79.］

［3］ZHOU Qing，CAI Ming.Improved hybrid query tree anticollision algorithm in RFID system ［J］.Computer Engineering and Design，2012，33 （1）：209－212 （in Chinese）.［周清，蔡明.改進的RFID 混合查詢樹防碰撞算法 ［J］.計算機工程與設(shè)計，2012，33 （1）：209－212.］

［4］XIANG Chuiyi，HE Yigang，LI Bing，et al.Improvement of dynamic binary system tree search algorithm ［J］.Computer Engineering，2010，36 （2）：260－264 （in Chinese）.［向垂益，何怡剛，李兵，等.動態(tài)二進制樹搜搜算法的改進 ［J］.計算機工程，2010，36 （2）：260－264.］

［5］SUN Wensheng，LIU Ting.Improved anticollision algorithm based on binary－tree search ［J］.Computer Engineering，2011，37 （10）：257－259 （in Chinese）.［孫文勝，劉婷.一種改進的基于二叉樹搜索樹的防碰撞算法 ［J］.計算機工程，2011，37 （10）：257－259.］

［6］Jiho Ryu，Hojin Lee，Yongho Seok.et al.A hybrid query tree protocol for tag collision algorithm in RFID system ［C］／／IEEE International Conference on Communication，2007：5981－5986.

［7］Sung Hyun Kin，Poo Gyeon.Park an efficient tree based tag anticollision protocol for RFID system ［J］.IEEE Communication Letters，2007，11 （5）：449－451

［8］DING Zhiguo，ZHU Xueyong，GUO Li.An adaptive anti－collision algorithm based on multi－tree search ［J］.Acta Automatic Sinica，2010，36 （2）：237－241 （in Chinese）. ［丁治國，朱學永，郭立.自適應(yīng)多叉樹防碰撞算法研究 ［J］.自動化學報，2010，36 （2）：237－241.］

［9］CHOI JH，LEE D，LEE H.Query tree based reservation for efficient RFID tag anticollision ［J］.IEEE Communications Letters，2007，11 （1）：85－87.

［10］Klair DK，Read R.An investigation into the energy efficiency of pure and slotted aloha based RFID anticollision protocols［C］／／Proc of IEEE International Symposium on World of Wireless Mobile and Multimedia Networks，2007：1－4.