一種分布式全類型RFID閱讀器碰撞解決方案

　　0 引言

　　在RFID系統(tǒng)中，如果閱讀器的射頻場作用范圍內(nèi)存在多個(gè)標(biāo)簽，并有兩個(gè)或者兩個(gè)以上的標(biāo)簽同時(shí)響應(yīng)閱讀器時(shí)將會產(chǎn)生碰撞[1]。而閱讀器與標(biāo)簽的不同位置可能導(dǎo)致3種碰撞類型[2]：(1)標(biāo)簽之間的碰撞;(2)閱讀器接口之間的碰撞(RRI);(3)閱讀器與標(biāo)簽接口間的碰撞(RTI)。

　　目前主流的防碰撞算法主要分為兩大類，一種是基于時(shí)隙分配的ALOHA方法[3]，該方法實(shí)現(xiàn)簡單，但可能出現(xiàn)標(biāo)簽餓死現(xiàn)象;另一種方法是搜索樹方法，該方法一般延遲較長[4]。近期一些研究對傳統(tǒng)防碰撞方法進(jìn)行了改進(jìn)，提高了ALOHA與搜索樹方法的性能，但是對于密集RFID網(wǎng)絡(luò)，即碰撞發(fā)生概率極大的情況，其性能并不理想[5-6]。

　　針對上述問題，本文提出一種分布式多信道防碰撞算法，其中引入了一個(gè)多信道通知協(xié)議來使得閱讀器感知網(wǎng)絡(luò)采用的資源，本方法可解決所有3種類型的碰撞。與其他防碰撞協(xié)議比較，本方法減少了標(biāo)簽認(rèn)證所需的平均時(shí)間，并增加了標(biāo)簽詢問的成功率。

　　1 分布式多信道防碰撞算法

　　1.1 背景知識與系統(tǒng)模型

　　本方法在閱讀器之間建立一個(gè)通知機(jī)制，使閱讀器知道網(wǎng)絡(luò)中的資源、信道與時(shí)隙的分配情況，如圖1所示，本方法在閱讀器之間設(shè)置了兩個(gè)控制信道CC1與CC2。在CC1與CC2中分別使用不同頻率(頻分)與時(shí)隙(時(shí)分)防止閱讀器之間的干擾。閱讀器與標(biāo)簽之間的通信則使用多數(shù)據(jù)信道。

　　首先定義以下變量：假設(shè)Ri表示一個(gè)閱讀器i，對于每個(gè)Ri，ri設(shè)為Ri的閱讀范圍，Ii是Ri的干擾范圍，di，j是Ri與Rj之間的距離。假設(shè)所有的閱讀器閱讀范圍相等，則對于兩個(gè)閱讀器Ri與Rj，RTI的發(fā)生條件為：

　　該情況下，兩個(gè)閱讀器必須在不同的頻帶運(yùn)行。本文方法中將控制信道CC1與CC2的傳輸范圍分別設(shè)為r+I與2r。

　　每個(gè)閱讀器R維護(hù)兩個(gè)隊(duì)列Q1與Q2，分別用于閱讀器是否可以開始識別標(biāo)簽以及所使用的數(shù)據(jù)通道。Q1保存一些信息，例如對R干擾的閱讀器ID;Q2保存當(dāng)前正在干擾標(biāo)簽的閱讀器信息。

　　1.2 本文算法的步驟

　　每個(gè)閱讀器R在標(biāo)簽詢問過程中使用數(shù)據(jù)通道時(shí)也可接收控制通道的控制包，將從CC1、CC2接收的控制信息分別保存于Q1、Q2中。圖2所示是控制數(shù)據(jù)包的格式，主要包括3個(gè)域：(1)type：“START”或“END”;(2)閱讀器ID，閱讀器的身份ID;(3)選擇的信道，標(biāo)簽詢問的發(fā)送器所用信道。在CC2的傳輸中，所選通道域是空的，因?yàn)猷従庸?jié)點(diǎn)距離發(fā)送器2r，不需要所選通道的信息，此類鄰居節(jié)點(diǎn)僅需要在同一時(shí)隙認(rèn)證閱讀器。END包中所選信道域也是空的，因?yàn)閺年?duì)列中刪除部分START數(shù)據(jù)包，閱讀器ID足以識別一個(gè)閱讀器。

　　本文算法包括兩個(gè)部分：詢問程序與接收程序，分別如圖3與圖4所示。

　　詢問程序：將可用數(shù)據(jù)信道AV的數(shù)量設(shè)為n，初始化時(shí)，AV={c1，…，cn}的所有數(shù)據(jù)信道均是可用的。當(dāng)一個(gè)閱讀器開始一次詢問，首先等待一個(gè)偽隨機(jī)時(shí)間，然后檢查該閱讀器的Q1與Q2兩個(gè)隊(duì)列，如果Q1集合的大小不等于n，Q2是空的，則選擇一個(gè)可用的數(shù)據(jù)通道，在CC1與CC2上發(fā)送一個(gè)START數(shù)據(jù)包，并開始標(biāo)簽詢問過程。如果兩個(gè)條件沒有同時(shí)滿足，則閱讀器需等待一個(gè)偽隨機(jī)時(shí)間，重新開始上述過程。

　　接收程序：如果閱讀器收到一個(gè)START控制包，則提取關(guān)于閱讀器與數(shù)據(jù)通道的信息，依賴該包的控制信道將其排列在對應(yīng)的隊(duì)列中，如圖4所示。將CC1通道上閱讀器R的傳輸范圍設(shè)為r+I，由此通知鄰居閱讀器引發(fā)RRI或者RTI型的碰撞。因此，如果有其他可用的通道，則可選擇其他通道，如圖3所示。另外，將CC2的傳輸范圍設(shè)為2r，通知引起R閱讀器RTI碰撞的鄰居閱讀器，使這兩個(gè)閱讀器不同時(shí)操作。上述設(shè)置可防止終端隱藏與暴露問題，互相干擾的閱讀器之間可使用控制信道通信。當(dāng)一個(gè)閱讀器結(jié)束標(biāo)簽詢問過程，則在CC1與CC2通道中發(fā)送END包通知其結(jié)束狀態(tài)，收到該消息的閱讀器從其隊(duì)列中刪除對應(yīng)的START數(shù)據(jù)包。

　　1.3 干擾范圍的計(jì)算

　　使用路徑衰減模型計(jì)算干擾范圍，如式(3)所示：

其中d是檢驗(yàn)與閱讀器的距離，分母1為無線通信參考距離。假設(shè)閱讀器與標(biāo)簽的位置如圖5所示，此外，因?yàn)殚喿x器的覆蓋范圍依賴閱讀器的輸出能力，考慮閱讀器操作的輸出功率為2 W[7]，因此對應(yīng)閱讀器的傳輸范圍是10 m。然后，使用式(3)計(jì)算從閱讀器A到標(biāo)簽的路徑衰減，假設(shè)閱讀器與標(biāo)簽的距離為10 m，有：

　　根據(jù)文獻(xiàn)[8]，需要13 dB的輸入功率來激活一個(gè)被動標(biāo)簽，因此總衰減為：58+58+13=129 dB。為了在A中成功接收標(biāo)簽的反向散射信號，從閱讀器B到A干擾信號的路徑衰減必須大于129 dB。因此為了防止閱讀器碰撞，A與B的距離應(yīng)該為：

　　由此證明本文對閱讀器干擾范圍的選擇是合理的，即當(dāng)閱讀范圍是10 m時(shí)，干擾范圍是1 000 m。

　　2 仿真實(shí)驗(yàn)與結(jié)果分析

　　將本方法與文獻(xiàn)[9]的DSAC和文獻(xiàn)[10]的AAC進(jìn)行比較，DSAC與AAC均是近期性能較好的防碰撞算法?；诰W(wǎng)絡(luò)仿真器NS3進(jìn)行實(shí)驗(yàn)，使用RangePropagationLoss-Model與NS3的802.11 Wife模型(http：//www.nsnam.org)。實(shí)驗(yàn)中使用MAC層的CSMA處理控制包的碰撞，本算法檢測閱讀器碰撞，假設(shè)每個(gè)閱讀器必須驗(yàn)證100個(gè)標(biāo)簽，閱讀100個(gè)標(biāo)簽所需的時(shí)間為0.46 s，閱讀器可能同時(shí)閱讀不同的標(biāo)簽。

　　本實(shí)驗(yàn)設(shè)計(jì)了稀疏與密集的兩種閱讀器分布場景。稀疏場景：在3 km3的三維空間中手動地放置5、10、15、20、25個(gè)閱讀器，因此會頻繁地發(fā)生不同類型的碰撞;密集場景：在2 km2的三維空間(高20 m)中隨機(jī)地分布25、70、150、250、350、1 000與2 000個(gè)閱讀器。假設(shè)閱讀器的傳輸范圍是10 m，干擾范圍是1 000 m。閱讀器天線類型為全向天線，數(shù)據(jù)速度為1 Mb/s，CC1傳輸范圍r+I=1 010 m，CC2傳輸范圍2r=20 m;每組實(shí)驗(yàn)重復(fù)運(yùn)行次數(shù)是10，稀疏場景數(shù)據(jù)通道數(shù)量是6，密集場景數(shù)據(jù)通道數(shù)量是10。

　　2.1 閱讀器詢問操作失敗的次數(shù)

　　如果網(wǎng)絡(luò)中不同閱讀器的隊(duì)列之間發(fā)生碰撞，則認(rèn)為是詢問失敗。圖6所示是稀疏、密集兩種場景的詢問失敗次數(shù)，稀疏場景下，DSAC失敗詢問次數(shù)隨著閱讀器數(shù)量增加而增加，主要原因是DSAC僅解決了RTI，而本文方法的閱讀器沒有出現(xiàn)失敗情況，本方法與AAC可解決RTI與RRI。在密集場景下，本方法與AAC仍然沒有出現(xiàn)失敗的情況，可解決RRI與RTI兩種碰撞。

　　2.2 閱讀器詢問總延遲

　　不同數(shù)量閱讀器的總識別延遲定義為所有閱讀器結(jié)束標(biāo)簽詢問過程所需的時(shí)間，圖7所示是實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)。稀疏場景下，DSAC比AAC的總延遲低，原因是DSAC并未解決所有的碰撞，所以用時(shí)較少。而本方法的延遲最低，受益于本方法的分布式處理方案，因此在閱讀器數(shù)量增加之后，本方法的總詢問延遲上升幅度減小。而對于密集場景，因?yàn)楸痉椒ㄊ欠植际綑z測方法，所以本方法的延遲依然最低。

　　3 結(jié)論

　　本文針對已有RFID閱讀器防碰撞算法一般僅可解決部分類型的閱讀器碰撞或者由于采用中心控制設(shè)備導(dǎo)致延遲較高的問題，提出一種分布式的全類型RIFD閱讀器碰撞解決方案。本方法可解決所有3種類型的碰撞。與其他防碰撞協(xié)議比較，本方法減少了標(biāo)簽認(rèn)證所需的平均時(shí)間，并增加了標(biāo)簽詢問的成功率。

　　參考文獻(xiàn)

　　[1] 余松森，詹宜巨，蔡慶玲，等.融合安全與反碰撞的RFID處理機(jī)制[J].計(jì)算機(jī)工程，2011，37(10)：26-28.

　　[2] KLAIR D K，CHIN K W，RAAD R.A survey and tutorial of RFID anti-collision protocols[J].IEEE Communications Surveys & Tutorials，2010，12(3)：400-421.

　　[3] 單劍鋒，謝建兵，莊琴清.基于分組的動態(tài)幀時(shí)隙ALOHA防碰撞算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012，21(11)：39-41.

　　[4] 黃瓊，凌江濤，張敏，等.LRST：低冗余搜索樹防碰撞算法[J].通信學(xué)報(bào)，2014(6)：110-116.

　　[5] 劉國柱，王騰，王華東.基于幀分組與二進(jìn)制搜索樹識別的RFID防碰撞算法的研究[J].海南大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，32(4)：320-326.

　　[6] LAI Y C，HSIAO L Y，LIN B S.An RFID anti-collision algorithm with dynamic condensation and ordering binary tree[J].Computer Communications，2013，36(s17-18)：1754-1767.

　　[7] BUENO-DELGADO M V，VALES-ALONSO J，ANGERER C，et al.A comparative study of RFID schedulers in dense reader environments[C].IEEE International Conference on Industrial Technology，2010：1373-1378.

　　[8] LEHPAMER H.RFID design principles，second edition[M].Automatic Vehicle Identification，2012.

　　[9] SAADI H，TOUHAMI R，YAGOUB M C E.Design and simulation of anti-collision RFID system based on SDMA-OFDM[C].Multimedia Computing and Systems(ICMCS)，2014 International Conference on.IEEE，2014：1510-1515.

　　[10] 徐海峰，姜暉，劉振.一種改進(jìn)的RFID自適應(yīng)防碰撞算法[J].計(jì)算機(jī)工程，2012，38(17)：290-292.