基于能量優化的射頻識別標簽防碰撞算法研究

,苗長勝,魯恩

(1.國網四川省電力公司計量中心，成都 610000;2.北京智芯微電子科技有限公司，北京 100192)

0 引言

在研究基于云平臺和RFID實現閉環模式下智能表全壽命周期管理系統工程的過程中，射頻識別標簽防碰撞算法是其中關鍵的研發重點，如何實現射頻識別標簽防碰撞算法性能高的同時又能盡量的節能，成為基于云平臺和RFID實現閉環模式下智能表全壽命周期管理系統中重點研究以及實現的問題。

射頻識別(radio frequency identification，RFID)是一種利用無線射頻信號實現無接觸信息的傳遞，再利用這些信息達到識別對象的技術[1-2]。這種射頻識別的硬件系統一般由閱讀器與電子標簽構成，而在一些復雜的系統中，會使用到計算機系統。在射頻識別系統中，閱讀器是對電子標簽進行讀寫的儀器，在整個系統中起著至關重要的作用；系統中的電子標簽則是對所要識別對象信息的載體設備，一般會被安置在所要識別的物體之上，所得到的數據由計算機系統進行處理[3-4]。

無線射頻、芯片以及計算機等技術的發展為RFID系統提供了快速發展的前提[5]。當前RFID系統發展迅速，其生產成本、體積以及能耗都得到了改進，而且功能也非常豐富。RFID系統在發達國家較為成熟，在各種領域都有著深入的應用，如商品管理、生產控制等[6]。國內雖然RFID系統應用出現的時間較晚，但是實際應的領域在不斷擴大，發展異常迅速，如停車收費系統、火車車號識別系統等都已經在市場中廣泛使用。RFID對人類生產、生活的幫助使得它的應用涉及到了各行各業，但是RFID技術在對多目標識別時仍然存在著一定的問題，這也成為制約RFID技術進一步發展的瓶頸所在[7-8]。

Jacomet在1999年提出一種查詢樹算法，但是他的算法計算時耗時太長，因此無法滿足射頻識別標簽防碰撞快速識別的需求[9]。2003年，Claus Finkenzeller提出一種射頻識別標簽防碰撞算法，這種算法是一種二進制搜索算法，隨后一些研究者依據他的算法提出一些改進的算法[10]。余松森在2004年提出了返回式二進制搜索算法,鞠偉成在2005年提出了動態二進制搜索算法，從不同的角度對二進制算法進行了改進，提高了射頻識別標簽防碰撞算法的性能[11]。返回式二進制搜索算法對減少了閱讀器的查詢次數，而動態二進制算法則減少了查詢時單次標簽與閱讀器之間信息處理的數量。在此之后王雪等人在2010年提出了鎖位后退式算法、馮娜、潘偉杰等人于2012年提出了跳躍式動態搜索算算法等等[12]。

截至目前，針對射頻識別標簽防碰撞算法的研究成為了物聯網技術的一個重要的研究方向。在防碰撞研究領域，雖然有著很多的研究工作，但是如何使得算法具有低復雜度、效率高仍然具有很大的挑戰難度。本文提出一種基于功率控制的分組算法，以達到提高防碰撞算法性能的目標。另一方面，由于功率控制的使用，使系統中的閱讀器可以利用不同的發射功率來實現與不同距離的標簽進行通信，所以該種方案可以在提高了系統性能的同時實現節能。

1 RFID基本原理以及基礎知識

電磁波在空間中散射時，會遇到各種不同的目標，在電磁波到達目標后，一部分會被吸收到，一部分則會繼續向外散射。反射的能量中的一部分會回到天線中，這部分被稱為回波。在雷達中，該原理常用于目標距離的測量和定位。

圖1 RFID的原理結構圖

1.1 閱讀器到標簽能量傳輸

在距離為R的電子標簽處的功率密度計算方式如公式(1)所示：

(1)

在公式(1)中，PTx是系統讀寫器的發射功率，GTx則是代表發射天線的增益，R是標簽到讀寫器之間的距離。在理論上，標簽可以吸到的功率計算方式如公式(2)所示：

(2)

在公式(2)中，GTag代表的是標簽天線的增益。在RFID系統中，由于標簽的能量來自于閱讀器的天線所發射出的電磁場，所寫標簽的功耗與讀寫距離是負相關的，功耗越小距離就會越大，反之則越小。標簽的功能能能否正常發揮功能由標簽的電壓決定，這也對系統識別的距離有著決定性的作用。當前在技術不斷成熟的情況下，標簽芯片的能耗已經降至幾微瓦，因此，即使閱讀器的功率受到限制，RFID的識別距離也得到極大的提升。

1.2 標簽閱讀器的能量傳輸

標簽所反射回去的能量與雷達散射的截面是正比關系。標簽會將一部分電磁波吸收用于自身的工作，另一部分則會發射回閱讀器中，在閱讀器中所接收到的標簽信號總功率計算方式如式(3)所示：

(3)

GRx代表的就是系統中閱讀器的天線增益，λ是標簽發射能量的效率，依據公式(3)，如果將閱讀器所接收到的標簽發送能量為標準，則可以認定反向散射工作模式的RFID系統的識別距離的四次方與系統閱讀器的發射功率成正比。

2 一種新的基于能量優化的射頻識別標簽防碰撞算法

2.1 RFID系統中的能量傳輸以及閱讀器的范圍分析

首先對RFID系統中的能量傳輸以及閱讀器的范圍進行分析，進而使得問題得以簡化。首先分析單閱讀器、單標簽模型下的情況。

閱讀器給定的輸出功率為Pt,此時標簽所得到的閱讀器所發送的功率計算方式如公式(4)所示。

(4)

在式(4)中，Gt,Gr分別代表閱讀器與標簽天線，λ1,λ2代表閱讀器與標簽之間的通信前后與后向鏈路的工作波長，η則是代表標簽能量反射效率，ri代表閱讀器與標簽i之間相應的距離，Pr-i就是指標簽返射回閱讀器的功率。

在實際的應用中，由于信息傳遞環境以及信道情況帶來的影響，式(4)可以變更成為：

(5)

在式(5)中，q代表的就是環境因子，其值由實際的應用場景決定。

閱讀器的詢問范圍是一個非常重要的指標，設定閱讀器的接收功率的檢測閾值為Prequired，此時可以得出：

Rinterrogation_range=sufriPr-i≥Prequired

(6)

將式(6)代入式(5)可得：

(7)

本文算法在防碰撞性能上達到了50%以上，對系統的有效服務率有著很大的提升。

2.2 算法的實現

前文分析的是單閱讀器、單標簽模型。但是在實際的應用中，存在著多閱讀器多標簽模型的情況，因此可以對這種單閱讀器、單標簽模型進行擴展。

參照公式(7)可以得出Rinterrogation_range是Pt的函數，因此只要對閱讀器的輸出功率進行控制，就可以對閱讀器的詢問范圍進行調整。通過對閱讀器的輸出功率逐步提升，步距為Pstepped，此時就能夠獲得一組Rinterrogation_range。這一組輸出功率可以把所要識別的區域進行劃分，可以得到N個子區域，即Zone1，Zone2…ZoneN。此時，每次在與閱讀器通信時，只選定其中一部分指定的區域進行通信，這樣一來就可以實現閱讀器與不同距離標簽通信的功能。利用這種方案即能夠使得標簽的防碰撞性能得到提升，也可以使得系統的能量消耗得到減少，因此實用價值較高。

本文的算法主要涉及到所識別標簽三個不同的狀態，即“準備”、“待命”以及“靜默”三個狀態。算法的具體步驟如下。

步驟一：閱讀器使用功率和標簽通信，這樣一來使得一部分的標簽能夠進入“準備”的狀態。

步驟二：對處于“準備”狀態的標簽進行初始化，把它們的的狀態改變，變成“待命”狀態。處于“待命”狀態的標簽，會對閱讀器的命令響應，反饋自己的數據信息。

IfPr

---Pt←Pt+Pstepped

---回到步驟一

ElseifPr≥Prequired

---對Zone i 區域中的標簽數量估算

IfN≤1

---Zone I 的標簽被識別。由于N是一個估算出來的值，此時其值仍可能大于1，所以仍然可能出現碰撞的情況，因此這里可以使用傳統的標簽沖突算法來解決，如Framed Slotted ALOHA。此處所使用的傳統算法標記為Subroutine2。

--- 使用Subroutine2來解決碰撞問題

步驟三：

IfPt=Pmax

---退出算法

ElseifPt

---Pt←Pt+Pstepped

---回到步驟一

2.3 算法有效服務率分析

(8)

對于處于同一個碰撞時隙內的標簽有兩個及以上時，這些簽在這個時隙內就會出現碰撞，此時我們使用p來代表硬幣拋出0的概率，這就意味著在n個信息包中i個拋0的概率計算方式為：

(9)

CRI的長度由上式(9)得出計算方式如下：

(10)

K0=K1=1

(11)

Kn|i=E[Kn|i～]=1+Ki+Ki+1n≥2

(12)

因此，可以得到：

(13)

依據上式，n≥2時，利用遞歸可得：

(14)

依據式(9)以及(11)就可以把式(14)變換成為：

(15)

在后退式無線密碼引的二進制算法中：

K1=1

(16)

在識別區域內有兩個標簽時，閱讀器問詢后標簽信息包應答時就會出現碰撞。因為標簽的EPC代碼是唯一的，因此在運算后M1相同并且在同一個區域內的幾率非常小，在兩個不同的標簽中，有著不同的二進制位數，這樣一來就可以避免兩個標簽發出沖突的Request命令。因為在算法中，標簽識別的前行與后退有著相對應的關系，因此：

K2=3

(17)

設定：Kn=2n-1n>2

(18)

在識別區域有n+1個標簽時，新增加的標簽信息包與原有M1的值是不同的，為保證把它與匹配度最高的標簽落區別開，就需要在原有的二進制搜索樹中添加一個節點，該節點間只有父子關系，并且有兩邊相連，因此：

Kn+1=(2n-1)+2=2(2n+1)-1

(19)

由數學歸納法可知假設成立，所以本文在解決碰撞時，Kn以及有效服務率n/Kn為：

Kn=2n-1n≥1

(20)

(21)

本文算法在防碰撞性能上達到了50%以上，對系統的有效服務率有著很大的提升。

3 實驗結果與分析

在進行仿真前，首先對防碰撞算法的原理進行闡述。防碰撞算法的核心是要對在識別范圍內的的多個電子標簽進行有續訪問。因此，系統中采用的算法能夠使得在一個時間內只讓一個標簽與讀寫器建立通信，通信結束后即進入休眠，待下一個通信建立，如此循環只到所有的標簽被識別完為止。這種方案是以狀態機的形式實現。多標簽防碰撞算法依據標準協議的要求嵌入到RFID系統的芯片中，提高讀寫器能夠同時閱讀標簽的數量。防讀寫器會推送一個周期指令用于清點標簽，在一個清點周期內，可能有一個或者多個標簽參與，標簽接收到指令后會在 (O，2Q.1)(Q為指令的參數)內產生一個隨機數并將該數放入到計數器中。如果這個隨機數是0的時候，該標簽就會回復一個十六位的隨機數，不是0則進入arbitrate狀態，等待下一步的指令即QueryRep和 QueryAdjust指令。如果此時只有一個標簽回復了信息，那么讀寫器就會確認該標簽再由讀寫器發送QueryRep指令繼續識別工作。如果沒有回復或者有多個標簽回復，那么讀寫器就會發送QueryAjust或者QueryRep指令。QueryAdjust指令用于改變參數Q的值，但不改變其它參數，這樣就會使得標簽依據新參數產生隨機數；QueryRep指令則令計數器自減1。

仿真參數的設置流程如下：

1)使用subsystem對50個標簽進行封裝，再與閱讀器連接；

2)將參數Q的值設為3，Qfp=3，時隙計數器值na=2Q=8，碰撞計數器nf=0，正確識別標簽計數器nr=0；

3)系統的閱讀器會依據下一個時隙內的回復信息的處理結果處理計數器，即回復信息有效時，保留標簽信息并讓接收器自增1，若回復信息無效則讓碰撞計數器自增1；

4)把時隙計數器的值減1，并對此時的值進入判斷，如果為0時，對碰撞發生器的值進行判斷，若為0，這個清點周期結可，若不為零，依據算法對Q值進行調節并進入步驟1；若時隙計數器不為0時，閱讀器利用算法對Q參數的值進行調節，并對系統發送Queryrep或 QueryAjust指令此時進入步驟2。

下面本文從算法的防碰撞性以及節能性能來對算法的性能進行分析。算法的防碰撞性分析由吞吐率分析進行，算法的節能性能分析由本文算法與傳統算法的能耗相比得出。

依據相關的協議以及實際中的應用場景，算法的仿真設置參數為：Gr=2 dBi,Gt=6 dBi,f=900 MHz,q=1.5,Prequired=-60 dBm，閱讀器設定的最大輸出功率為Pmax=32 dBm,閱讀器的最小輸出功率Pmin=0 dBm,Pstepped=3 dBm。仿真分析依據蒙特卡羅方法進行，針對不同的應用場景的仿真結果見下文。

1)當標簽在詢問區內隨機分布時，算法的性能對比如圖2～4所示。

圖2 標簽隨機分布下TAPC的標簽防碰撞性能

從圖2中可以看到，在識別標簽片是隨機分布在閱讀器的詢問題區域內，并且標簽的數量在10到50之間時，TAPC的算法在防碰撞性能表現與Basic Framed Slotted ALOHA(BFSA)算法以及Dynamic Framed Slotted ALOHA(DFSA)算法相比要優秀的多。從圖中可以看到TAPC算法在吞吐量小于60以下時，保持在0.45以上，與傳統的算法相比，有著較大的優勢。

圖3 標簽高斯分布下TAPC的防碰撞性能(標簽數10～60)

2)傳統的標簽防碰撞算法有著能耗較高的不足之處，本文為了解決這一問題，提出了以功率控制為基礎的標簽防碰撞算法，即TAPC。依據仿真結果，可知TAPC算法使得RFID系統的能耗降低，并且提高了系統的防碰撞性能，在實際的應用中有著較大的價值。本文在復雜度沒有提高的情況下改進了傳統標簽防碰撞算法中存在的不足之處，使得算法更加完善。所以本文的算法在實際應用的價值較大，另一方面，本文的研究成果也為RFID的防碰撞研究領域提供了新的參考，在理論研究上也具有一定的意義。

4 總結

針對射頻識別標簽防碰撞算法的研究成為了物聯網技術的一個重要的研究方向。在射頻識別標簽防碰撞算法研究領域，雖然專家們有著很多的研究工作，但是如何使得算法具有低復雜度、效率高仍然具有很大的挑戰難度。本文提出一種基于功率控制的分組算法，以達到提高防碰撞算法性能的目標。另一方面，由于功率控制的使用，使系統中的閱讀器可以利用不同的發射功率來實現與不同距離的標簽進行通信，所以該種方案可以在提高了系統性能的同時實現節能。