沈 虹
哈爾濱鐵道職業(yè)技術(shù)學(xué)院,黑龍江 哈爾濱 150081
現(xiàn)在RFID技術(shù)已經(jīng)在很多領(lǐng)域得到了廣泛的應(yīng)用,但是在某些場(chǎng)合電子標(biāo)簽的分布很過(guò)于密集,如果采用應(yīng)用比較的二進(jìn)制搜索算法,算法的搜索次數(shù)多,傳輸時(shí)延大。這主要因?yàn)樵陔娮訕?biāo)簽的數(shù)量多或位數(shù)長(zhǎng),發(fā)生碰撞的電子標(biāo)簽數(shù)量和比特位數(shù)增加,因此,在二進(jìn)制搜索算法的基礎(chǔ)上提出分集的二進(jìn)制搜索算法。即把電子標(biāo)簽分成若干個(gè)集,每個(gè)集里面的電子標(biāo)簽都可以被閱讀器單獨(dú)地識(shí)別出來(lái),各個(gè)集互不影響,電子標(biāo)簽之間發(fā)生碰撞的次數(shù)就會(huì)減少。由閱讀器發(fā)射的信號(hào)到達(dá)電子標(biāo)簽的功率密度S和閱讀器與電子標(biāo)簽間的距離R表示為:
其中P代表閱讀器的發(fā)射功率,λ代表信號(hào)的波長(zhǎng),σ代表散射的橫截面積,G代表天線的增益,Pback代表閱讀器接收的從電子標(biāo)簽所發(fā)射的信號(hào)的功率。
由公式1、2可知,可以通過(guò)調(diào)節(jié)閱讀器的發(fā)射信號(hào)的功率和發(fā)射天線的增益方式來(lái)改變閱讀器和電子標(biāo)簽之間的距離。
如圖1所示,為這種分集思想的一個(gè)例子,閱讀器工作區(qū)域被分為三個(gè)集:d,d1,d2。首先,閱讀器調(diào)節(jié)天線使集d內(nèi)的所有電子標(biāo)簽運(yùn)行改進(jìn)的二進(jìn)制搜索算法,當(dāng)集d內(nèi)的所有電子標(biāo)簽都被識(shí)別出來(lái)后,閱讀器調(diào)節(jié)天線使作用范圍擴(kuò)大到集d1,當(dāng)集d1內(nèi)的所有電子標(biāo)簽被識(shí)別出來(lái)后,再識(shí)別集d2中的電子標(biāo)簽。各集間是互相獨(dú)立、互不干擾的,在各集內(nèi)運(yùn)用的是改進(jìn)的二進(jìn)制搜索算法。閱讀器對(duì)集的處理的次序是由近及遠(yuǎn),不存在交集,因此避免了集間的沖突。
圖1 電子標(biāo)簽分集示意圖
首先我們來(lái)介紹幾個(gè)命令:
在改進(jìn)的二進(jìn)制搜索算法中用到一個(gè)REQUEST(EPC,NULL)命令,該命令的含義是:在閱讀器發(fā)送REQUEST(11…11)命令后,根據(jù)譯碼結(jié)果發(fā)送REQUEST(EPC,NULL)命令,電子標(biāo)簽只鎖位不回送EPC。
SELECT(EPC):選擇(序列號(hào))命令,用于事先被確定的序列號(hào)作為參數(shù)傳送給電子標(biāo)簽,也就是選中了這個(gè)電子標(biāo)簽。
READ-DATA:數(shù)據(jù)讀取命令,將被選中的電子標(biāo)簽中的數(shù)據(jù)傳送給閱讀器。
UNSELECT:取消命令,取消事先已選中的電子標(biāo)簽,使其進(jìn)入“靜默”狀態(tài)。處于該狀態(tài)下的電子標(biāo)簽是非激活的,對(duì)接收到的REQUEST命令不作應(yīng)答。
算法的工作過(guò)程如下:
1)閱讀器發(fā)送REQUEST(11…11)命令,所有EPC值小于或者等于(11…11)的電子標(biāo)簽作出響應(yīng),然后所有電子標(biāo)簽將自己的EPC碼發(fā)送出去;
2)閱讀器根據(jù)接收到的信號(hào)進(jìn)行判斷,如果為空,表示閱讀器附近不存在電子標(biāo)簽,則轉(zhuǎn)到步驟1,否則轉(zhuǎn)到步驟3;
3)閱讀器對(duì)所有電子標(biāo)簽作出的響應(yīng)信號(hào)進(jìn)行譯碼,根據(jù)譯碼結(jié)果判斷碰撞是否發(fā)生及碰撞發(fā)生的位置。如果沒(méi)有發(fā)生碰撞,閱讀器發(fā)送SELECT和READ-DATA命令,對(duì)標(biāo)簽進(jìn)行讀寫(xiě)操作之后,閱讀器發(fā)出UNSELECT命令,使該電子標(biāo)簽進(jìn)入靜默狀態(tài)。發(fā)送如果有碰撞,則轉(zhuǎn)到步驟4;
4)閱讀器將這幾個(gè)碰撞的比特的值置為1,未發(fā)生碰撞的比特位置0,接著閱讀器發(fā)送REQUEST(EPC,NULL)命令,所有電子標(biāo)簽均對(duì)此命令作出響應(yīng),然后將自身的EPC與閱讀器發(fā)出的序列號(hào)進(jìn)行比較,與閱讀器發(fā)出的EPC位中1對(duì)應(yīng)的數(shù)據(jù)位進(jìn)行鎖定,在接下來(lái)各集內(nèi)的防碰撞處理中,參與數(shù)據(jù)發(fā)送和比較的僅僅是被鎖定的數(shù)據(jù);
5)閱讀器根據(jù)電子標(biāo)簽的數(shù)量來(lái)確定集的數(shù)量,集的數(shù)量的取值范圍在[1,n]之間,根據(jù)實(shí)際情況來(lái)確定具體的取值;
6)閱讀器調(diào)節(jié)天線工作距離,由近及遠(yuǎn)在各個(gè)集內(nèi)執(zhí)行改進(jìn)的二進(jìn)制搜索算法。當(dāng)所有的電子標(biāo)簽都被識(shí)別出來(lái)后跳轉(zhuǎn)到步驟7;
7)識(shí)別過(guò)程結(jié)束。
在采用分集技術(shù)的二進(jìn)制搜索算法中,如果閱讀器作用范圍內(nèi)有n個(gè)標(biāo)簽,并且閱讀器的作用范圍被分為n個(gè)具有相同大小的集,則采用分集技術(shù)的二進(jìn)制搜索算法來(lái)識(shí)別m個(gè)電子標(biāo)簽需要的搜索次數(shù)為:
S代表空集的數(shù)目,即集內(nèi)沒(méi)有電子標(biāo)簽的數(shù)量。
證明:如果空集的數(shù)量為s,則非空集的數(shù)目為n-s,假設(shè)ni代表第i個(gè)非空集內(nèi)的電子標(biāo)簽的個(gè)數(shù),則第i個(gè)非空集內(nèi)執(zhí)行改進(jìn)的二進(jìn)制搜索算法的搜索次數(shù)為S(m,i)=2mi-1,則在所有非空集內(nèi)運(yùn)行改進(jìn)的二進(jìn)制算法所需要的搜索次數(shù)為:
因?yàn)榈谝淮伍喿x器發(fā)出REQUEST(11…11)命令和REQUEST(EPC,NULL)命令,所以得到識(shí)別m個(gè)電子標(biāo)簽需要的搜索次數(shù)為:
選取集的數(shù)量是否合適對(duì)本算法的性能有著重大的影響,對(duì)于選取集的數(shù)目,有下面的結(jié)論:
如果m個(gè)電子標(biāo)簽的EPC是均勻分布的,那么理想的集的數(shù)量n的最優(yōu)取值在區(qū)間[1,m]內(nèi)。
如果在閱讀器的工作區(qū)域存在m個(gè)電子標(biāo)簽。再將這m個(gè)電子標(biāo)簽分為n個(gè)集,則可以得到:
1.第t(1 ≤t≤m)個(gè)集為空集的概率為:
2.第t個(gè)集僅存在1個(gè)電子標(biāo)簽的概率為:
3.第t個(gè)集內(nèi)電子標(biāo)簽數(shù)量為i的概率為:
空集內(nèi)傳輸?shù)目倲?shù)據(jù)為x+10,只有一個(gè)電子標(biāo)簽的集內(nèi)傳輸?shù)目倲?shù)據(jù)為2 x+23,電子標(biāo)簽個(gè)數(shù)超過(guò)1的集內(nèi)傳輸?shù)目倲?shù)據(jù)為3x-2xi-21+(2xi+44)mi,另外閱讀器開(kāi)始有一次搜索需要傳輸?shù)臄?shù)據(jù)量為2k+21,其中為k代表電子標(biāo)簽EPC的長(zhǎng)度,由此可以得到:
1)所有空集傳輸?shù)臄?shù)據(jù)長(zhǎng)度為:
2)電子標(biāo)簽數(shù)量為1的傳輸?shù)臄?shù)據(jù)長(zhǎng)度為:
3)電子標(biāo)簽個(gè)數(shù)為i的傳輸?shù)臄?shù)據(jù)長(zhǎng)度為:
這里xh代表第h個(gè)電子標(biāo)簽個(gè)數(shù)為i的集發(fā)生碰撞的數(shù)據(jù)長(zhǎng)度。
由式(9)、(10)、(11)可以得到,分集的二進(jìn)制搜索算法傳輸這些數(shù)據(jù)的時(shí)延為:
其中v代表數(shù)據(jù)傳輸速率。
本文詳細(xì)研究了分集的二進(jìn)制搜索算法,主要適用于在電子標(biāo)簽分布密集的場(chǎng)合下。分集的二進(jìn)制搜索算法是在二進(jìn)制搜索算法的基礎(chǔ)上進(jìn)行分集處理,將電子標(biāo)簽分成若干個(gè)集,在各個(gè)集內(nèi)繼續(xù)運(yùn)行改進(jìn)的二進(jìn)制算法,同時(shí),對(duì)閱讀器的搜索次數(shù)、傳輸時(shí)延兩個(gè)重要的性能指標(biāo)對(duì)分集的二進(jìn)制搜索算法的性能進(jìn)行了分析,分析表明:在電子標(biāo)簽密集分布的情況下,分集的二進(jìn)制算法優(yōu)越于二進(jìn)制搜索算法,當(dāng)然更優(yōu)越于動(dòng)態(tài)二進(jìn)制搜索算法和返回式二進(jìn)制搜索算法。
[1]劉冬生,鄒雪城,泳生,李孝煌,等.射頻識(shí)別系統(tǒng)中的防碰撞算法[J].華中科技:大然科學(xué)版,2006,34(9).
[2]劉舒棋,牟志剛,等.非接觸式R助的讀寫(xiě)器系統(tǒng)設(shè)計(jì)[J].單片機(jī)與嵌入式系統(tǒng).
[3]陳冬萍.射頻識(shí)別技術(shù)(RFID)應(yīng)用研究[D].華中師范大學(xué)碩士畢業(yè)論文,2006.
[4]王洪菊.RFID的系統(tǒng)設(shè)計(jì)與碰撞算法研究[D].西北工業(yè)大學(xué)碩士畢業(yè)論文,2007.
[5]金允霖.主動(dòng)式RFID在集裝箱應(yīng)用中關(guān)鍵技術(shù)的研究和設(shè)計(jì)[D].上海交通大學(xué),2007.