沈 虹

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

1 問題的提出與改進思路

現(xiàn)在RFID技術(shù)已經(jīng)在很多領(lǐng)域得到了廣泛的應(yīng)用，但是在某些場合電子標簽的分布很過于密集，如果采用應(yīng)用比較的二進制搜索算法，算法的搜索次數(shù)多，傳輸時延大。這主要因為在電子標簽的數(shù)量多或位數(shù)長，發(fā)生碰撞的電子標簽數(shù)量和比特位數(shù)增加，因此，在二進制搜索算法的基礎(chǔ)上提出分集的二進制搜索算法。即把電子標簽分成若干個集，每個集里面的電子標簽都可以被閱讀器單獨地識別出來，各個集互不影響，電子標簽之間發(fā)生碰撞的次數(shù)就會減少。由閱讀器發(fā)射的信號到達電子標簽的功率密度S和閱讀器與電子標簽間的距離R表示為：

其中P代表閱讀器的發(fā)射功率，λ代表信號的波長，σ代表散射的橫截面積，G代表天線的增益，Pback代表閱讀器接收的從電子標簽所發(fā)射的信號的功率。

由公式1、2可知，可以通過調(diào)節(jié)閱讀器的發(fā)射信號的功率和發(fā)射天線的增益方式來改變閱讀器和電子標簽之間的距離。

如圖1所示，為這種分集思想的一個例子，閱讀器工作區(qū)域被分為三個集：d，d1，d2。首先，閱讀器調(diào)節(jié)天線使集d內(nèi)的所有電子標簽運行改進的二進制搜索算法，當(dāng)集d內(nèi)的所有電子標簽都被識別出來后，閱讀器調(diào)節(jié)天線使作用范圍擴大到集d1，當(dāng)集d1內(nèi)的所有電子標簽被識別出來后，再識別集d2中的電子標簽。各集間是互相獨立、互不干擾的，在各集內(nèi)運用的是改進的二進制搜索算法。閱讀器對集的處理的次序是由近及遠，不存在交集，因此避免了集間的沖突。

圖1 電子標簽分集示意圖

2 改進的二進制搜索算法的描述

首先我們來介紹幾個命令：

在改進的二進制搜索算法中用到一個REQUEST（EPC，NULL）命令，該命令的含義是：在閱讀器發(fā)送REQUEST（11…11）命令后，根據(jù)譯碼結(jié)果發(fā)送REQUEST（EPC，NULL）命令，電子標簽只鎖位不回送EPC。

SELECT（EPC）：選擇（序列號）命令，用于事先被確定的序列號作為參數(shù)傳送給電子標簽，也就是選中了這個電子標簽。

READ-DATA：數(shù)據(jù)讀取命令，將被選中的電子標簽中的數(shù)據(jù)傳送給閱讀器。

UNSELECT：取消命令，取消事先已選中的電子標簽，使其進入“靜默”狀態(tài)。處于該狀態(tài)下的電子標簽是非激活的，對接收到的REQUEST命令不作應(yīng)答。

算法的工作過程如下：

1）閱讀器發(fā)送REQUEST（11…11）命令，所有EPC值小于或者等于（11…11）的電子標簽作出響應(yīng)，然后所有電子標簽將自己的EPC碼發(fā)送出去；

2）閱讀器根據(jù)接收到的信號進行判斷，如果為空，表示閱讀器附近不存在電子標簽，則轉(zhuǎn)到步驟1，否則轉(zhuǎn)到步驟3；

3）閱讀器對所有電子標簽作出的響應(yīng)信號進行譯碼，根據(jù)譯碼結(jié)果判斷碰撞是否發(fā)生及碰撞發(fā)生的位置。如果沒有發(fā)生碰撞，閱讀器發(fā)送SELECT和READ-DATA命令，對標簽進行讀寫操作之后，閱讀器發(fā)出UNSELECT命令，使該電子標簽進入靜默狀態(tài)。發(fā)送如果有碰撞，則轉(zhuǎn)到步驟4；

4）閱讀器將這幾個碰撞的比特的值置為1，未發(fā)生碰撞的比特位置0，接著閱讀器發(fā)送REQUEST（EPC，NULL）命令，所有電子標簽均對此命令作出響應(yīng)，然后將自身的EPC與閱讀器發(fā)出的序列號進行比較，與閱讀器發(fā)出的EPC位中1對應(yīng)的數(shù)據(jù)位進行鎖定，在接下來各集內(nèi)的防碰撞處理中，參與數(shù)據(jù)發(fā)送和比較的僅僅是被鎖定的數(shù)據(jù)；

5）閱讀器根據(jù)電子標簽的數(shù)量來確定集的數(shù)量，集的數(shù)量的取值范圍在[1，n]之間，根據(jù)實際情況來確定具體的取值；

6）閱讀器調(diào)節(jié)天線工作距離，由近及遠在各個集內(nèi)執(zhí)行改進的二進制搜索算法。當(dāng)所有的電子標簽都被識別出來后跳轉(zhuǎn)到步驟7；

7）識別過程結(jié)束。

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

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

在采用分集技術(shù)的二進制搜索算法中，如果閱讀器作用范圍內(nèi)有n個標簽，并且閱讀器的作用范圍被分為n個具有相同大小的集，則采用分集技術(shù)的二進制搜索算法來識別m個電子標簽需要的搜索次數(shù)為：

S代表空集的數(shù)目，即集內(nèi)沒有電子標簽的數(shù)量。

證明：如果空集的數(shù)量為s，則非空集的數(shù)目為n-s，假設(shè)ni代表第i個非空集內(nèi)的電子標簽的個數(shù)，則第i個非空集內(nèi)執(zhí)行改進的二進制搜索算法的搜索次數(shù)為S（m，i）=2mi-1，則在所有非空集內(nèi)運行改進的二進制算法所需要的搜索次數(shù)為：

因為第一次閱讀器發(fā)出REQUEST（11…11）命令和REQUEST（EPC，NULL）命令，所以得到識別m個電子標簽需要的搜索次數(shù)為：

選取集的數(shù)量是否合適對本算法的性能有著重大的影響，對于選取集的數(shù)目，有下面的結(jié)論：

如果m個電子標簽的EPC是均勻分布的，那么理想的集的數(shù)量n的最優(yōu)取值在區(qū)間[1，m]內(nèi)。

3.2 傳輸時延分析

如果在閱讀器的工作區(qū)域存在m個電子標簽。再將這m個電子標簽分為n個集，則可以得到：

1.第t（1 ≤t≤m）個集為空集的概率為：

2.第t個集僅存在1個電子標簽的概率為：

3.第t個集內(nèi)電子標簽數(shù)量為i的概率為：

空集內(nèi)傳輸?shù)目倲?shù)據(jù)為x+10，只有一個電子標簽的集內(nèi)傳輸?shù)目倲?shù)據(jù)為2 x+23，電子標簽個數(shù)超過1的集內(nèi)傳輸?shù)目倲?shù)據(jù)為3x-2xi-21+（2xi+44）mi，另外閱讀器開始有一次搜索需要傳輸?shù)臄?shù)據(jù)量為2k+21，其中為k代表電子標簽EPC的長度，由此可以得到：

1）所有空集傳輸?shù)臄?shù)據(jù)長度為：

2）電子標簽數(shù)量為1的傳輸?shù)臄?shù)據(jù)長度為：

3）電子標簽個數(shù)為i的傳輸?shù)臄?shù)據(jù)長度為：

這里xh代表第h個電子標簽個數(shù)為i的集發(fā)生碰撞的數(shù)據(jù)長度。

由式（9）、（10）、（11）可以得到，分集的二進制搜索算法傳輸這些數(shù)據(jù)的時延為：

其中v代表數(shù)據(jù)傳輸速率。

4 結(jié)論

本文詳細研究了分集的二進制搜索算法，主要適用于在電子標簽分布密集的場合下。分集的二進制搜索算法是在二進制搜索算法的基礎(chǔ)上進行分集處理，將電子標簽分成若干個集，在各個集內(nèi)繼續(xù)運行改進的二進制算法，同時，對閱讀器的搜索次數(shù)、傳輸時延兩個重要的性能指標對分集的二進制搜索算法的性能進行了分析，分析表明：在電子標簽密集分布的情況下，分集的二進制算法優(yōu)越于二進制搜索算法，當(dāng)然更優(yōu)越于動態(tài)二進制搜索算法和返回式二進制搜索算法。

[1]劉冬生，鄒雪城，泳生，李孝煌，等.射頻識別系統(tǒng)中的防碰撞算法[J].華中科技：大然科學(xué)版，2006，34(9).

[2]劉舒棋，牟志剛，等.非接觸式R助的讀寫器系統(tǒng)設(shè)計[J].單片機與嵌入式系統(tǒng).

[3]陳冬萍.射頻識別技術(shù)(RFID)應(yīng)用研究[D].華中師范大學(xué)碩士畢業(yè)論文，2006.

[4]王洪菊.RFID的系統(tǒng)設(shè)計與碰撞算法研究[D].西北工業(yè)大學(xué)碩士畢業(yè)論文，2007.

[5]金允霖.主動式RFID在集裝箱應(yīng)用中關(guān)鍵技術(shù)的研究和設(shè)計[D].上海交通大學(xué)，2007.