一種基于標簽分布距離的RFID碰撞避免算法

蔣毅，張若南，程偉，李彬

(西北工業大學電子信息學院，陜西西安 710072)

一種基于標簽分布距離的RFID碰撞避免算法

蔣毅，張若南，程偉，李彬

(西北工業大學電子信息學院，陜西西安 710072)

由于實際應用對標簽數量的需求日益增大，導致標簽碰撞問題成為嚴重影響RFID系統識別效率的重要因素。提出了一種基于標簽分布距離的碰撞避免算法（DBCA），該算法可很好地解決大規模RFID環境下的標簽碰撞問題。根據標簽與閱讀器的分布距離，建立新型的標簽分組結構，確保組內標簽的高效識別；利用組內標簽不同屬性，給出以不同頻率在相應幀時隙通信的方法，縮減識別時間和碰撞發生概率。算法分析及仿真結果表明，相比已有算法，該算法可有效提高系統的識別效率，減少識別時間。

RFID；碰撞避免；分布距離，分組

射頻識別(radio frequency identification，RFID)是一種利用無線射頻來自動識別目標的物聯網關鍵技術，在產品供應鏈、安全、交通、目標跟蹤等眾多領域都有廣泛應用。RFID系統由閱讀器和標簽組成，閱讀器負責讀取標簽信息；標簽由于受到制作工藝和成本的限制，一般采用無源結構，由閱讀器的能量激活，負責承載目標信息。隨著應用場景所需標簽數目的增多，出現了多個標簽同時響應閱讀器請求的情況，此時信息發生了沖突，閱讀器將無法正常讀取標簽信息，這種情況被稱為標簽碰撞，該問題的產生將直接影響RFID系統的正常工作，從而降低系統識別效率，延長識別時間，是急需解決的關鍵問題。

目前標簽防碰撞算法主要分為兩類：確定性樹型算法及概率性Aloha算法。樹型算法復雜度較高，識別時間較長，本文將把低復雜度的Aloha型算法作為主要的研究方向。幀時隙Aloha算法［1］由基本幀時隙算法(basic framed slotted aloha，BFSA)和動態幀時隙算法(dynamic framed slotted aloha， DFSA)組成，整個識別過程分為多個幀，標簽選擇幀內時隙來響應閱讀器請求，BFSA算法采用固定幀長，而DFSA算法的幀長可根據標簽數目動態調整，因而識別效率較高，隨著標簽數目的增多，受限幀長使其性能迅速下降。文獻［2］提出了一種增強型動態幀時隙算法(enhanced DFSA，EDFSA)，通過標簽分組來減少標簽數目增多對算法性能的影響；文獻［3］提出了一種基于組的DFSA算法，證明了當幀長與標簽數目相比擬時，標簽數目越少，系統效率越高的原則，以上2種算法均沒有對如何分組做相應說明。文獻［4］提出了一種基于幀內分組和精確標簽估計的標簽防碰撞算法(collision group algorithm， CGA)，在受限幀長情況下，隨著標簽數目的增多，依然不能有效解決碰撞問題。文獻［5］提出了一種基于距離分簇的防碰撞算法，并在文獻［6］中給出了最優簇數目的計算方法，這2種算法采用固定的分簇步長，制約了分簇的合理性，文獻［7-8］通過合并或縮減多個簇的方法來改進以上算法，其步長調整具有一定局限性。

本文提出一種基于標簽分布距離的碰撞避免算法(tag distribution distance based collision avoidance algorithm，DBCA)，該算法適用于大規模RFID應用場景。根據標簽分布距離，優化分組步長調整，建立新型的標簽分組結構，保持組內待識別標簽數目一致，并匹配初始幀長，確保識別時的最佳系統效率；為了提高單位時間內識別標簽的數目，減少碰撞概率，采用不同屬性的標簽參與識別工作，將限定工作頻率引入動態幀時隙算法，給出以不同頻率在相應幀時隙通信的方法；利用基于距離的分組方法，設計閱讀器與標簽端詳細的標簽識別過程。仿真結果和性能分析表明，相比于已有算法，本算法在提高系統識別效率和縮減識別時間方面具有較優的性能。

1　分組結構及組內標簽通信方法

1.1基于標簽分布距離的分組結構

根據幀長與待識別標簽數目相比擬時，標簽數目越小，系統識別效率越高的原則［3］，將閱讀器讀寫范圍內的標簽進行分組，并依次識別，以保證較高的系統識別效率。通過改變閱讀器發射功率的大小，來調整其可覆蓋的識別區域，達到對標簽進行分組識別的目的。在當前分組的確認過程中，標簽不屬于當前分組的情況可分為2種：1)標簽與閱讀器的距離超過了閱讀器讀寫半徑，不能激活標簽；2)標簽雖然可以接收閱讀器讀寫命令，但由于信號強度過弱，導致標簽反射信息不能成功到達閱讀器。

假設已知組內最優標簽數目ni，標簽均勻分布在讀寫區域，已知其密度Di。閱讀器調整發射功率改變讀寫半徑，來劃分標簽在各組中的歸屬，并依次完成組內標簽的識別，半徑可由小到大逐步增加，直至最大讀寫范圍，所有標簽識別完畢。發射功率與讀寫半徑的關系式由文獻［9］獲得。圖1為分組結構的示意圖。

圖1　基于標簽分布距離的分組結構示意圖

標簽均勻分布時，分組讀寫范圍將保持一致，以確保組里初始標簽數目一致，由公式(1)表示：

若讀寫范圍Sir和前一組讀寫半徑ri－1已知，由stepi＝ri－ri－1帶入(1)式，可得步長的表達(2)式：

步長stepi隨著標簽分布情況及分組所屬讀寫范圍的變化而動態改變，需保持組內標簽數目與初始幀長相匹配，不會因讀寫半徑的增大，組內標簽數目的迅速增長，而導致碰撞的概率急劇增加。

1.2基于屬性的組內標簽通信

確定分組后，在組內可使用DFSA算法［1］來完成閱讀器與標簽的識別工作，在每幀的識別過程中，依然會出現多個標簽在相同時隙響應閱讀器請求而發生碰撞的情況，為了進一步減少這種情況，假設應用于不同場景的標簽具有不同的屬性，在響應閱讀器請求的上行通路中使用不同的工作頻率，即攜帶不同的副載波，對其信號進行調制。但不同屬性標簽的使用，受到閱讀器成本的限制，需限定屬性個數，并在特定頻率上取值，因而此方法適用于組內標簽的識別，因為分組后的組內待識別標簽數目將顯著減少，不適用于大規模標簽的識別壞境。

由于無源標簽受到其成本、尺寸、內存等方面的限制，本身無法識別閱讀器識別請求的頻率，因而閱讀器與不同屬性標簽通信的下行通路可使用同一頻率，而傳輸標簽響應的上行通路中信號頻率的識別由閱讀器完成。當多個標簽在同一時隙內響應，閱讀器可識別屬性不同的標簽，對于同一屬性的多個標簽且在同一時隙內響應才會導致信息碰撞，因此利用基于屬性的組內標簽通信方法可大大提高識別效率和系統吞吐量。

2　DBCA算法識別過程

DBCA算法識別過程的詳細描述如下：

1)閱讀器根據已知的最佳分組讀寫范圍Sir，及上一輪讀寫半徑ri－1，根據(2)式，調整步長stepi，求得當前讀寫半徑ri，并以對應發射功率向外發送識別請求信息(request)。

2)當標簽與閱讀器的距離d滿足ri－1＜d＜ri時，標簽才具備發送應答信息(response)響應閱讀器請求的能力。并在隨后組內通信的每個幀內選擇時隙通信，若在某時隙內被成功識別，則標簽轉為休眠狀態，不再參與識別過程。

3)閱讀器在某時隙內收到標簽響應信息后，進行識別工作，并判斷時隙是否產生碰撞，根據判斷的結果記錄一幀內的成功時隙個數ssu、空閑時隙個數so、碰撞時隙個數sc，用于對下一幀的幀長進行動態調整。時隙內不產生碰撞的情況如下：

·一個時隙內只有一個標簽響應閱讀器請求；

·一個時隙內有多個標簽響應閱讀器請求，但其全部或部分的屬性不同，不同屬性的標簽響應不產生碰撞。

4)閱讀器向已成功識別的標簽發送確認信息(confirmation)，對應標簽收到該信息后，進入休眠狀態。

5)閱讀器判斷當前組內標簽是否全部識別完畢，若沒有則采用步驟3)中記錄的結果動態調整幀長，進行下一幀的識別；否則進入步驟1)進行下一分組的識別工作。在下一分組標簽識別之前的各組內標簽均已進入休眠狀態，不會參與下一組的識別工作。

6)分組識別繼續進行，直到閱讀器讀寫半徑達到最大值，即已包含可讀寫范圍內的所有標簽，則識別過程結束。

圖2為DBCA算法的流程圖。

圖2　DBCA算法流程圖

3　DBCA算法分析及優化

3.1同一工作頻率時標簽數目與幀長的關系

假設幀長為L，標簽數目為n，則在第i組內給定時隙中只有一個標簽響應的概率為：

當前幀內可被成功識別的時隙數目為：

由上述分析可知，在組內只有當幀長與組內標簽數目保持一致時，系統識別效率最高，此時在相同的幀長下，能使更多標簽被識別。系統效率的定義為公式(6)：

3.2不同工作頻率時系統效率與標簽數目的關系

組內標簽的數目將直接影響識別效率和系統吞吐量，若標簽數目過大將會增大時隙內的碰撞概率；若標簽數目過小又會增加空閑時隙數。因而需在給定條件下，尋找能夠維持最大系統效率所對應的最佳組內標簽數目。

假設幀長為L，標簽數目為n，則在第i組內給定時隙中有α個標簽同時響應的概率為：

在一個時隙中，如果存在多個不同屬性的標簽同時響應的情況，其中只要有標簽能被識別，即將此時隙認作成功時隙，由此成功時隙Sse由(8)式表示：

式中，Sα為有α個標簽同時響應同一時隙并且能成功識別標簽的時隙數，t為可選標簽屬性個數，經實驗驗證，在一個時隙內存在多個標簽同時響應的概率隨響應標簽數目的增大而迅速減少，為了簡化計算結果，本算法將忽略大于t個以上標簽同時在特定時隙內響應的情況。根據以上分析，系統效率為：

由于閱讀器對不同屬性標簽的響應需采用不同頻率的接收器，因此t值將受到閱讀器成本的限制，不能過大。假設t＝3，圖3將給出在不同幀長的條件下，系統識別效率隨組內標簽數目變化的關系圖。從圖中可知，對應最佳組內標簽數目，本算法系統效率的最大值可達到51.5%，這將大大優于已有相關算法。

圖3　系統識別效率與標簽數目的關系圖(隨L變化)

圖4為在不同t值的條件下，系統識別效率隨組內標簽數目變化的關系圖。

圖4　系統識別效率與標簽數目的關系圖(隨t變化)

從圖中可以看出，在幀長L＝128的情況下，t值越大，相同組內標簽數目能達到的系統效率越高，但t值受到閱讀器成本及讀取復雜度的限制，不能過大。

圖5為在不同C值的條件下，系統識別效率隨讀寫區域內全部標簽數目變化的關系圖，此時L＝128，t＝3。

圖5　系統識別效率與標簽數目的關系圖(隨C變化)

從圖中可以看出，隨著分組數目的增加，可以達到系統最大效率的標簽數目也在不斷增加，這意味著在相同系統效率下，通過分組可以識別更多的標簽。觀察幾條曲線的交點，利用公式(8)還可以得到，用于區分分組個數的臨界標簽數目。

從以上分析可知本算法的系統識別效率最高可達50%以上，遠高于純ALOHA算法(18.4%)、DFSA算法(36.8%)及EDFSA算法(34.6%～36.8%)的最高系統效率。

3.3優化步長調整

由以上分析可得，在給定條件下，能夠達到最大系統效率時的最佳組內標簽數目nopt，并根據標簽分布密度Di來計算最優化組內讀寫范圍Sir，已知前一組讀寫半徑ri－1，則可利用公式(2)來計算最優步長stepopt，從而達到合理劃分分組的目的。

4　DBCA算法的性能分析

在這一節中，我們將所提算法與其他已有算法DFSA［1］、EDFSA［2］及CGA［4］進行性能比較，并對仿真結果進行分析。以完成標簽識別所需的總時隙數來衡量算法性能，若所需總時隙數較少則表明識別延時較小，系統吞吐量高，反之亦然。本文將采用Matlab進行仿真，為了得到更精確的仿真結果，將對1 000次的仿真結果取平均值作為最終的結果。假設：1)標簽均勻分布在20 m×20 m的區域，閱讀器位于整個讀寫區域的中心，其最大讀寫半徑rmax＝10m。2)標簽數目最大可達1 000，為了準確分析性能，將分為2種工作情景：小規模場景，標簽數目0～200；大規模場景，標簽數目0～1 000。3)DFSA算法的幀長可隨標簽數目的變化而動態改變，其初始幀長設為16，最大幀長可達256。4)EDFSA、CGA算法的初始幀長設為128，所有算法的最大幀長均設為256。5)DBCA算法可根據組內標簽數目確定起始幀長，并隨未識別標簽數目的減少而遞減幀長。

圖6為在小規模標簽的工作場景下所需總時隙數目與標簽數目的關系圖。從圖中可知，標簽數目小于120時，EDFSA算法所需的時隙數目大于DFSA算法，這是因為DFSA算法在標簽數目較少時，幀長也較小，初始值僅為16，幀長隨標簽數目的增加而成倍增加，因而存在較少的空閑時隙；而EDFSA算法初始幀長為128，在標簽數目較少時，出現了較多的空閑時隙，性能較差，而當標簽數目超過120時，幀長可以跟上標簽數目的變化，此時其性能將優于DFSA算法。由于CGA算法具有幀內分組的功能，相對于前兩種算法，所需時隙數目較少。本算法相比于其他3種算法所需時隙數目最少，這是因為其分組步長和幀長都可以根據最佳組內標簽數目進行動態調整，使其系統效率達到最優，所以性能最好，由于標簽總數過小，此處未使用多屬性標簽。

圖6　總時隙數與標簽數目的關系圖(小規模場景)

圖7為在大規模標簽的工作場景下所需總時隙數目與標簽數目的關系圖。從圖中可知，DFSA算法所需的時隙數將隨標簽數目的增加成指數增長，這是因為幀長只能增長到其最大值256，而隨著標簽數目的持續增加，碰撞時隙將顯著增多，所以系統性能將迅速下降。EDFSA算法性能將優于DFSA算法，所需的時隙數將隨標簽數目的增加而線性增長，這是因為該算法具有標簽分組功能，通過分組來減少待識別的標簽數目，并可以在組內調節幀長，可保持系統效率達到較高水平。CGA算法在標簽數目小于700時，其所需總時隙數小于EDFSA算法，而大于700后，將超過EDFSA算法的增長量，這是因為該算法以幀內分組來提高標簽識別效率，但在幀長最大值有限、標簽數目迅速增加的情況下，將不能很好的處理碰撞問題，算法性能下降。本算法所需的總時隙數最少，這是因為其利用優化步長進行合理分組，幀長隨組內標簽數目動態調整，保證組內有較高的系統識別效率，同時采用多屬性標簽參與識別，可以在相同幀長下，識別更多的標簽，減少了碰撞時隙，性能最優。

圖7　總時隙數與標簽數目的關系圖(大規模場景)

5　結 論

解決大規模標簽場景下的信息碰撞問題，提高系統的識別效率，是RFID技術發展所需關注的關鍵問題之一。本文提出了一種基于標簽分布距離的碰撞避免算法(DBCA)，適用于大規模RFID應用場景。利用動態步長調整，給出了一種對待識別標簽的合理分組方法；根據標簽的不同屬性，建立了分組內的幀時隙通信方法，可在一個時隙內識別多屬性標簽，提高了標簽的識別速度；設計了新的標簽識別過程，并對算法進行了優化。仿真結果及性能分析表明，本算法在提高系統識別效率和減少標簽識別時間方面，相比于已有算法，具有更優的性能。

［1］ Klair D K，Chin K W，Raad R.A Survey and Tutorial of RFID Anti-Collision Protocols［J］.IEEE Commun Surv Tutor，2010， 12(3)：400-421

［2］ Lee S R，Joo S D，Lee C W.An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification［C］//Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems：Networking and Services，2005：166-174

［3］ Wang C Y，Lee C C.A Grouping-Based Dynamic Framed Slotted ALOHA Anti-Collision Method with Fine Groups in RFID Systems［C］//5th International Conference on Future Information Technology，2010：1-5

［4］ Lin Chunfu，Frank Yeongsung Lin.Efficient Estimation and Collision-Group-Based Anticollision Algorithms for Dynamic Frame-Slotted ALOHA in RFID Networks［J］.IEEE Trans on Automation Science and Engineering，2010，7(4)：840-848

［5］ Ali K，Hassanein H，Taha A M.RFID Anti-Collision Protocol for Dense Passive Tag Environments［C］//The Proceedings of the 32nd IEEE Conference on Local Computer Networks，2007：819-824

［6］ Alsalih W，Ali K，Hassanein H.Optimal Distance-Based Clustering for Tag Anti-Collision in RFID［C］//The Proceedings of the 33rd IEEE Conference on Local Computer Networks，2008，266-273

［7］ Waleed Alsalih，Discrete Power-Based Distance Clustering for Anti-Collision Schemes in RFID Systems［C］//13th Annual IEEE Workshop on Wireless Local Networks，2013：868-873

［8］ Alsalih W，Ali K，Hassanein H.A Power Control Technique for Anti-Collision Schemes in RFID Systems［J］.Journal of Computer Networks，2013，57：1991-2003

［9］ Zhou F，Chen C，Jin D，et al.Evaluating and Optimizing Power Consumption of Anti-Collision Protocols for Applications in Rfid Systems［C］//ISLPED′04 NY，USA，2004：357-362

A Tag Distribution Distance Based Collision Avoidance Algorithm in RFID Systems

Jiang Yi，Zhang Ruonan，Cheng Wei，Li Bin
(Department of Electronics Engineering，Northwestern Polytechnical University，Xi′an 710072，China)

A large number of tags are needed in many applications；this fact causes the tag collision problem which affects the system efficiency of identification.We propose a DBCA(tag distribution Distance Based Collision Avoidance)algorithm，which can effectively solve the tag collision problem for a large scale RFID environment.To identify tags with the best system efficiency，a new grouping structure，based on distribution distance，is presented.To reduce the identification time，we give a communication method for the reader and tags in the corresponding frame， based on the different frequencies belonging to the different tag properties.The simulation results and their analysis show preliminarily that our algorithm has better performance than the existing algorithms with respect to system efficiency and identification time.

algorithms，clustering algorithms，collision avoidance，computer network performance evaluation，computer simulation，constrained optimization，efficiency，electric power utilization，flowcharting，identification(control systems)，MATLAB，network performance，network protocols，optimization，probability，radio frequency identification(RFID)，schematic diagrams，stochastic models，time delay， wavelength，distribution distance，grouping

TP393

A

1000-2758(2016)02-0250-06

2015-10-20基金項目：國家自然科學基金(61301092、61571370、61401360)與中央高校基金(3102015ZY093)資助

蔣毅(1980—)，女，西北工業大學副教授，主要從事無線傳感器網絡、RFID技術、網絡安全的研究。