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

王　宇，甘健侯

(1.云南經濟管理學院，云南 昆明 650106；2.云南師范大學，云南 昆明 650092)

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

王宇1，甘健侯2

(1.云南經濟管理學院，云南 昆明 650106；2.云南師范大學，云南 昆明 650092)

已有的RFID閱讀器防碰撞算法一般僅可解決部分類型的閱讀器碰撞，或者由于采用中心控制設備導致延遲較高，對此提出一種分布式的全類型RIFD閱讀器碰撞解決方案。設計了一種分布式多信道通知協議，主要包括詢問與接收兩部分，從而合理地分布閱讀器間的網絡資源，在考慮全部閱讀器碰撞類型的前提下，降低所有標簽的平均詢問延遲。仿真實驗結果表明，本算法可解決全部類型的RFID碰撞，同時具有較低的延遲。

防碰撞；RFID系統；物聯網；網絡安全；分布式協議；通知協議

0　引言

在RFID系統中，如果閱讀器的射頻場作用范圍內存在多個標簽，并有兩個或者兩個以上的標簽同時響應閱讀器時將會產生碰撞［1］。而閱讀器與標簽的不同位置可能導致 3種碰撞類型［2］：(1)標簽之間的碰撞；(2)閱讀器接口之間的碰撞(RRI)；(3)閱讀器與標簽接口間的碰撞(RTI)。

目前主流的防碰撞算法主要分為兩大類，一種是基于時隙分配的ALOHA方法［3］，該方法實現簡單，但可能出現標簽餓死現象；另一種方法是搜索樹方法，該方法一般延遲較長［4］。近期一些研究對傳統防碰撞方法進行了改進，提高了ALOHA與搜索樹方法的性能，但是對于密集RFID網絡，即碰撞發生概率極大的情況，其性能并不理想［5-6］。

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

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

1.1背景知識與系統模型

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

圖1　本文RFID系統的架構

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

該情況下，兩個閱讀器必須在不同的時隙運行，RRI與RTI同時發生的條件為；

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

每個閱讀器R維護兩個隊列Q1與Q2，分別用于閱讀器是否可以開始識別標簽以及所使用的數據通道。Q1保存一些信息，例如對R干擾的閱讀器ID；Q2保存當前正在干擾標簽的閱讀器信息。

1.2本文算法的步驟

每個閱讀器R在標簽詢問過程中使用數據通道時也可接收控制通道的控制包，將從 CC1、CC2接收的控制信息分別保存于 Q1、Q2中。圖2所示是控制數據包的格式，主要包括3個域：(1)type：“START”或“END”；(2)閱讀器 ID，閱讀器的身份ID；(3)選擇的信道，標簽詢問的發送器所用信道。在CC2的傳輸中，所選通道域是空的，因為鄰居節點距離發送器 2r，不需要所選通道的信息，此類鄰居節點僅需要在同一時隙認證閱讀器。END包中所選信道域也是空的，因為從隊列中刪除部分START數據包，閱讀器ID足以識別一個閱讀器。

圖2　數據包格式

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

圖3　本文方法的詢問程序

圖4　本文方法的接收程序

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

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

1.3干擾范圍的計算

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

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

圖5　B對A產生的干擾

根據文獻［8］，需要 13 dB的輸入功率來激活一個被動標簽，因此總衰減為：58+58+13=129 dB。為了在A中成功接收標簽的反向散射信號，從閱讀器B到A干擾信號的路徑衰減必須大于129 dB。因此為了防止閱讀器碰撞，A與B的距離應該為：

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

2　仿真實驗與結果分析

將本方法與文獻［9］的DSAC和文獻［10］的AAC進行比較，DSAC與AAC均是近期性能較好的防碰撞算法?；诰W絡仿真器NS3進行實驗，使用RangePropagationLoss-Model與NS3的802.11 Wife模型(http://www.nsnam.org)。實驗中使用MAC層的CSMA處理控制包的碰撞，本算法檢測閱讀器碰撞，假設每個閱讀器必須驗證100個標簽，閱讀100個標簽所需的時間為0.46 s，閱讀器可能同時閱讀不同的標簽。

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

2.1閱讀器詢問操作失敗的次數

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

圖6　閱讀器詢問操作失敗的次數

2.2閱讀器詢問總延遲

不同數量閱讀器的總識別延遲定義為所有閱讀器結束標簽詢問過程所需的時間，圖7所示是實驗結果的統計。稀疏場景下，DSAC比AAC的總延遲低，原因是DSAC并未解決所有的碰撞，所以用時較少。而本方法的延遲最低，受益于本方法的分布式處理方案，因此在閱讀器數量增加之后，本方法的總詢問延遲上升幅度減小。而對于密集場景，因為本方法是分布式檢測方法，所以本方法的延遲依然最低。

圖7　閱讀器詢問總延遲

3　結論

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

［1］余松森，詹宜巨，蔡慶玲，等.融合安全與反碰撞的RFID處理機制［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］單劍鋒，謝建兵，莊琴清.基于分組的動態幀時隙ALOHA防碰撞算法研究［J］.計算機技術與發展，2012，21(11)：39-41.

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

［5］劉國柱，王騰，王華東.基于幀分組與二進制搜索樹識別的 RFID防碰撞算法的研究［J］.海南大學學報：自然科學版，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 SDMAOFDM［C］.Multimedia Computing and Systems(ICMCS)，2014 International Conference on.IEEE，2014：1510-1515.

［10］徐海峰，姜暉，劉振.一種改進的 RFID自適應防碰撞算法［J］.計算機工程，2012，38(17)：290-292.

A distributed anti algorithm for all types of RFID reader collision

Wang Yu1，Gan Jianhou2
(1.Yunnan College of Business Management，Kunming 650106，China；2.Yunnan Normal University，Kunming 650092，China)

The existing anti-collision algorithms for RFID reader can only resolve some types of reader collisions,or it has high delay due to adopting centralized control hardware,a distributed anti method for all types of RFID reader collision is proposed for that problem.A distributed multi-channel notification protocol is designed,which includes two parts of interrogation and receive, and the network resource for the readers is distributed reasonably.All types of collisions are considered by the proposal and the average tag interrogation delay of all tags are reduced.Simulation experiments results show that the proposal can handle all types of collisions and realize a lower delay.

anti-collision；RFID system；Internet of Things；network security；distributed protocol；notification protocol

TN911

A

10.16157/j.issn.0258-7998.2016.04.026

2015-12-21)

王宇（1982-），男，碩士，講師，主要研究方向：數據庫技術、面向對象技術、移動互聯網。

甘健侯(1976-)，男，教授，主要研究方向：數據挖掘、民族教育信息化。

中文引用格式：王宇，甘健侯.一種分布式全類型RFID閱讀器碰撞解決方案［J］.電子技術應用，2016，42(4)：92-94，98.

英文引用格式：Wang Yu，Gan Jianhou.A distributed anti algorithm for all types of RFID reader collision［J］.Application of Electronic Technique，2016，42(4)：92-94，98.