一種快速獲取同頻數(shù)據(jù)的防碰撞算法

鄭 凱,李 冰,劉 勇,趙 霞,張 林

（東南大學(xué)集成電路學(xué)院，江蘇 無錫 214035）

1 引言

433 MHz頻段下的標(biāo)簽識(shí)別是一種使用標(biāo)簽進(jìn)行無線數(shù)據(jù)存儲(chǔ)和檢索的自動(dòng)識(shí)別技術(shù)。一旦無線信號(hào)在接收范圍之內(nèi)，處在433 MHz頻段下的標(biāo)簽?zāi)軌蝽憫?yīng)來自于閱讀器特定頻段的序列。與早期的二進(jìn)制編碼技術(shù)不同，433 MHz頻段下的標(biāo)簽識(shí)別不需要近距離的接觸。由于該技術(shù)相比二進(jìn)制編碼技術(shù)能夠提供絕對(duì)的靈活度，該靈活度可以很好地對(duì)各類土地的地形分布數(shù)量等特征進(jìn)行測量，因此該技術(shù)被廣泛應(yīng)用于土地測量領(lǐng)域。

在一個(gè)433 MHz的系統(tǒng)中，閱讀器識(shí)別區(qū)域內(nèi)可能存在多個(gè)標(biāo)簽，為了識(shí)別所有的標(biāo)簽，該系統(tǒng)需要一個(gè)通訊協(xié)議。因?yàn)樵陂喿x器和標(biāo)簽之間的數(shù)據(jù)傳輸都是在一個(gè)共享的無線頻段上的，所以當(dāng)不止一個(gè)標(biāo)簽與閱讀器進(jìn)行通訊時(shí)就產(chǎn)生了沖突。這些通訊協(xié)議被統(tǒng)稱為防碰撞算法。目前存在兩種防碰撞算法：確定性算法和隨機(jī)性算法。確定性算法都是基于二叉樹的算法，例如質(zhì)詢二叉樹算法（QT）和防碰撞二叉樹算法（CT）?；诙鏄涞乃惴ㄍǔ６际菍⒄麄€(gè)標(biāo)簽分成兩個(gè)子類別，以此類推，直到把所有的標(biāo)簽都識(shí)別出來。而隨機(jī)算法則是基于時(shí)分復(fù)用的算法的，其主要的思想是強(qiáng)制設(shè)定不同標(biāo)簽的響應(yīng)時(shí)間從而避免了碰撞的發(fā)生。以上這兩種算法都存在著自身的優(yōu)點(diǎn)和缺陷。

由于433 MHz系統(tǒng)的整體性能絕大部分取決于系統(tǒng)中所使用的特定的防碰撞算法，因此對(duì)于433 MHz系統(tǒng)來說，一個(gè)好的碰撞算法是十分重要的。通常來說，判斷一個(gè)防碰撞算法好壞的標(biāo)準(zhǔn)包括這個(gè)算法需要多少個(gè)周期將所有的標(biāo)簽都識(shí)別出來，算法的復(fù)雜程度以及傳輸?shù)臄?shù)據(jù)量的大小。因此，一個(gè)較好的防碰撞算法應(yīng)具備以下特征：較少的識(shí)別周期，計(jì)算簡單，資源消耗少，能耗低，識(shí)別速率快。

本文采用改進(jìn)型碰撞二叉樹（ICT）的快速防碰撞算法。在標(biāo)簽識(shí)別中，ICT算法在每一個(gè)標(biāo)簽中引入了一個(gè)計(jì)數(shù)器和指針，用于記錄閱讀器之前發(fā)送的序列差異。由于存在了計(jì)數(shù)器和指針，因此閱讀器不需要傳輸整個(gè)序列，閱讀器只需要傳輸上次已經(jīng)識(shí)別的后一個(gè)bit位，這樣便大大減少了閱讀器和標(biāo)簽之間的數(shù)據(jù)傳輸量。

2 改進(jìn)型碰撞二叉樹算法

2.1 改進(jìn)型碰撞二叉樹算法簡介

在ICT算法中，曼徹斯特編碼用于查找沖突的比特位。為了能夠精確查找沖突的比特位，假設(shè)所有識(shí)別區(qū)域內(nèi)的標(biāo)簽?zāi)軌蛲瑫r(shí)響應(yīng)閱讀器序列中的質(zhì)詢位。這里所講的序列中的質(zhì)詢位指的是上次已經(jīng)查詢過的前綴的后一個(gè)bit，閱讀器可以通過這一個(gè)質(zhì)詢位來將所有的標(biāo)簽區(qū)別開來，而不需要前面的前綴序列。閱讀器中有一個(gè)用于存儲(chǔ)前綴序列的堆棧，并且在每一個(gè)標(biāo)簽中都有狀態(tài)寄存器（SC）和指針寄存器（Pointer），狀態(tài)寄存器用于分類標(biāo)簽，只有當(dāng)狀態(tài)寄存器為0時(shí)標(biāo)簽才會(huì)響應(yīng)；指針用于指向與當(dāng)前bit對(duì)比的那個(gè)標(biāo)簽bit位，只有當(dāng)標(biāo)簽比對(duì)正確的時(shí)候才向閱讀器發(fā)出響應(yīng)信號(hào)。也就是說，標(biāo)簽的響應(yīng)是從當(dāng)前bit位的后一位一直持續(xù)到序列結(jié)束的最后一位為止。當(dāng)閱讀器接收到了標(biāo)簽的響應(yīng)信號(hào)后，會(huì)發(fā)出一個(gè)反饋信號(hào)，并且所有的標(biāo)簽根據(jù)這個(gè)反饋信號(hào)自行調(diào)整標(biāo)簽中的狀態(tài)寄存器和指針。

2.2 改進(jìn)型防碰撞二叉樹算法的實(shí)現(xiàn)

在初始化階段中，堆棧中是空的，不存在任何內(nèi)容，而標(biāo)簽中的指針指向了標(biāo)簽ID的最高位，隨著不斷地識(shí)別操作，指針逐漸向后面的bit位移動(dòng)；狀態(tài)寄存器中的值為0，即說明所有的ID當(dāng)前bit匹配的標(biāo)簽都應(yīng)當(dāng)響應(yīng)閱讀器的序列。由于在等待周期中不會(huì)有任何的標(biāo)簽響應(yīng)閱讀器，因此ICT可以省略掉等待的周期，所以只存在兩種處理周期：識(shí)別和碰撞周期。

關(guān)于這兩個(gè)周期的定義如下：

（1）識(shí)別周期是指有且只有一個(gè)標(biāo)簽的狀態(tài)寄存器值為0，并且當(dāng)前的bit位與閱讀器序列中的匹配；

（2）碰撞周期是指有不止一個(gè)標(biāo)簽的狀態(tài)寄存器的值為0，并且當(dāng)前的bit位與閱讀器序列中的匹配。

在ICT中，閱讀器需要通過傳輸目前前綴序列的后一個(gè)bit位（當(dāng)前序列的后一個(gè)bit）來區(qū)分所有的標(biāo)簽，只有那些狀態(tài)寄存器為0并且與ID中的前綴序列相同的標(biāo)簽才響應(yīng)閱讀器。當(dāng)那些滿足狀態(tài)寄存器為0并且當(dāng)前指針指向的bit位與前綴序列中的bit相同時(shí)則將ID中余下的bits發(fā)送給閱讀器。而閱讀器則根據(jù)接收到的信號(hào)來判決該返回信號(hào)對(duì)應(yīng)的正確操作。當(dāng)發(fā)生碰撞時(shí)，閱讀器則根據(jù)沖突的那個(gè)bit位產(chǎn)生兩個(gè)新的前綴序列并且將其壓入堆棧中。與此同時(shí)，閱讀器從堆棧中獲取新的前綴并且反饋相應(yīng)信號(hào)。如果沒有碰撞時(shí)，閱讀器則能夠識(shí)別出當(dāng)前的序列對(duì)應(yīng)的標(biāo)簽，其對(duì)應(yīng)的ID就是當(dāng)前的前綴序列和閱讀器收到的剩余ID的bits。在后面時(shí)間里，閱讀器則可以通過這個(gè)ID號(hào)進(jìn)一步和已經(jīng)識(shí)別的標(biāo)簽進(jìn)行數(shù)據(jù)的交換傳輸，在此之后，同樣的，閱讀器從堆棧中獲取新的前綴并且反饋相應(yīng)的信號(hào)。而那些不對(duì)閱讀器進(jìn)行響應(yīng)的標(biāo)簽則相應(yīng)地改動(dòng)內(nèi)部的狀態(tài)寄存器。在這個(gè)過程中，簡單的對(duì)狀態(tài)寄存器進(jìn)行+1操作是遠(yuǎn)遠(yuǎn)不夠的，因?yàn)檫@可能會(huì)導(dǎo)致在處理過程中插入較多的等待周期。為了有效避免等待周期，在每一個(gè)標(biāo)簽中都設(shè)置了一個(gè)Flag標(biāo)記符。Flag用于標(biāo)注上一個(gè)判別周期的狀態(tài)，F(xiàn)lag=1意味著上一個(gè)判別周期是識(shí)別周期。如果Flag=1，那么在當(dāng)前的判別狀態(tài)下，狀態(tài)寄存器不變；反之，當(dāng)Flag=0，則將狀態(tài)寄存器中的值加1。當(dāng)標(biāo)簽收到閱讀器的反饋信號(hào)的時(shí)候，則將Flag重新置位。

反饋信號(hào)用于通知所有標(biāo)簽當(dāng)前閱讀器的識(shí)別狀態(tài)，由于識(shí)別過程中存在兩種周期，因此閱讀器發(fā)送兩種類型的反饋。根據(jù)不同類型的反饋信號(hào)，標(biāo)簽做出如下的響應(yīng)：

識(shí)別：所有的標(biāo)簽都將狀態(tài)寄存器中的值-1并且將Flag設(shè)置為1，直到再次將狀態(tài)寄存器-1時(shí)其值變?yōu)?1，則表明，當(dāng)前的標(biāo)簽處于靜默狀態(tài)，并且不再繼續(xù)響應(yīng)閱讀器的序列。

碰撞：這一種類型的反饋信號(hào)中包括了一個(gè)參數(shù)k，表明當(dāng)前接收的新的前綴長度（bit）。當(dāng)標(biāo)簽接收到這種類型的反饋信號(hào)時(shí)則設(shè)置狀態(tài)寄存器為0，并且將指針設(shè)置為k-1個(gè)bit的位置，將Flag設(shè)置為0。

圖1所示的是ICT算法流程圖。表1中列舉了一個(gè)使用ICT識(shí)別4個(gè)標(biāo)簽的過程，四個(gè)標(biāo)簽分別為0001、0010、1100和1111。

表1 采用ICT識(shí)別4個(gè)標(biāo)簽

圖1 ICT算法流程

3 性能對(duì)比

將ICT算法和參考文獻(xiàn)[4]中的CT算法就通信開銷和識(shí)別速度兩個(gè)方面進(jìn)行對(duì)比，ICT中的一些性能參數(shù)，例如識(shí)別一個(gè)標(biāo)簽消耗的時(shí)間和識(shí)別效率與參考文獻(xiàn)[4]中是一樣的。

通信開銷被定義為單位時(shí)間內(nèi)通過閱讀器的平均bit的數(shù)量和識(shí)別一個(gè)標(biāo)簽耗費(fèi)的時(shí)間，識(shí)別速度定義為識(shí)別標(biāo)簽的平均數(shù)量/s。數(shù)據(jù)信道的數(shù)據(jù)傳輸速率設(shè)置為96 kbps。并且使用一個(gè)bit定義了兩種不同類型的反饋信號(hào)（1表示識(shí)別，0表示沖突），在沖突周期中，變量k的長度不能大于7 bits。

主要從以下三個(gè)不同方面對(duì)提出的算法進(jìn)行了仿真和性能評(píng)估。

初次實(shí)驗(yàn)中，使用ICT和CT算法分別識(shí)別一些標(biāo)簽，標(biāo)簽的數(shù)量從2個(gè)至512個(gè)之間變化，ID的長度設(shè)置為96 bits，并且這些標(biāo)簽的ID都是隨機(jī)產(chǎn)生的，盡管在ICT算法中使用一些技術(shù)避免傳輸不必要的bits，但是其性能并非如同之前所期望的那樣好，ICT只能夠取得與CT算法等同的性能。通過對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)由于標(biāo)簽ID是完全隨機(jī)離散的，因此每一個(gè)標(biāo)簽都有一個(gè)十分獨(dú)特互不相關(guān)的ID，幾乎所有標(biāo)簽的開始8個(gè)bits都是不一樣的，因此在使用CT算法的時(shí)候并不需要大量傳輸標(biāo)簽的ID。故此，在本次的測試中，并不能完全體現(xiàn)出ICT的優(yōu)越性。

經(jīng)由上述的試驗(yàn)分析，可以看出盡管ICT算法在算法的層面上對(duì)CT進(jìn)行了大量的改進(jìn)，但取得的性能卻并不能達(dá)到我們預(yù)期的效果。而導(dǎo)致這一現(xiàn)象主要的原因是隨機(jī)生成的ID在最開始的幾個(gè)bits是高度離散不相關(guān)的，因此ICT算法并沒有得到很高的發(fā)揮。

在接下來的實(shí)驗(yàn)中，每一個(gè)標(biāo)簽都有一個(gè)高度相關(guān)的識(shí)別前綴。在本次實(shí)驗(yàn)中，仍然使用ICT和CT兩種算法識(shí)別256個(gè)標(biāo)簽，每個(gè)標(biāo)簽ID的長度都是96 bits，并且每一個(gè)標(biāo)簽都有一個(gè)彼此相關(guān)的識(shí)別前綴，這個(gè)前綴的長度在4～80 bits之間不等，而ID中其余剩下的bits都是隨機(jī)產(chǎn)生的。如圖2所示是本次實(shí)驗(yàn)的結(jié)果。從圖2（a）我們可以清楚看到ICT的優(yōu)越性，并且隨著識(shí)別前綴的長度的不斷增加，相比CT算法其性能愈加明顯。這是由于在CT算法中閱讀器需要傳輸整個(gè)識(shí)別序列，而在使用ICT算法的時(shí)候，閱讀器只需要傳輸當(dāng)前的bit。圖2（b）所示是兩種算法的識(shí)別速度，ICT能夠明顯獲得快于CT算法的速度，試驗(yàn)說明ICT算法比CT算法更適合前綴相關(guān)的序列的標(biāo)簽識(shí)別。

4 結(jié)論

本文提出了一種用于土地地形分布特征測量的ICT快速獲取同頻數(shù)據(jù)的防碰撞算法。這種算法是從CT算法中衍生而來，通過某些技術(shù)方式避免了傳輸不必要的數(shù)據(jù)。本文的創(chuàng)新點(diǎn)是根據(jù)碰撞原理找到碰撞的具體位置之后，在這些碰撞的位置后面加上一位或者多位比特來增加質(zhì)詢前綴，減少質(zhì)詢位數(shù)而增加質(zhì)詢效率。實(shí)驗(yàn)結(jié)果表明ICT能夠在ID前綴序列相關(guān)的情況下獲得比CT算法更好的性能。ICT算法可以被應(yīng)用到433 MHz土地測量系統(tǒng)中來解決碰撞問題，同時(shí)可以獲得優(yōu)于CT算法的性能。

圖2 前綴序列的仿真結(jié)果

[1]L Zhu,T S P Yum.IEEE Communications Magazine[J].2011,49:214.

[2]M A Bonuccelli,F Lonetti,F Martelli.Ad Hoc Networks[J].2007,5:1220.

[3]J H Choi,D Lee,H Lee.IEEE Communications Letters[J].2007,11:85.

[4]X Jia,Q Feng,C Ma.IEEE Communications Letters[J].2010,14:1014.

[5]J Myung,W Lee,J Srivastava.IEEE Communications Letters[J].2006,10:144.

[6]K Finkenzeller.RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification,Second Edition[M].John Wiley & Sons,2003.Chapter 7.

[7]F Schoute.IEEE Transactions on Communications[J].1983,31: 565.

[8]K C Shin,S B Park,G S Jo.Sensors[J].2009,9: 845.