采用分集技術(shù)的改進(jìn)型二進(jìn)制搜索算法的研究

沈 虹

哈爾濱鐵道職業(yè)技術(shù)學(xué)院，黑龍江 哈爾濱 150081

1 問(wèn)題的提出與改進(jìn)思路

現(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)簽分集示意圖

2 改進(jìn)的二進(jìn)制搜索算法的描述

首先我們來(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é)束。

3 采用分集技術(shù)的二進(jìn)制搜索算法的性能分析

3.1 閱讀器搜索次數(shù)分析

在采用分集技術(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)。

3.2 傳輸時(shí)延分析

如果在閱讀器的工作區(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ù)傳輸速率。

4 結(jié)論

本文詳細(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.