一種基于隨機生成樹的多維Q選擇算法

靳曉芳，黃祥林，朱允

(中國傳媒大學 信息工程學院，北京 100024)

1 引言

隨著射頻識別技術的發展以及應用規模的擴大，讀寫器需要在短時間內識別多個標簽。當識別區域有多個標簽到達時，標簽信號的混疊造成碰撞。為了避免此情況發生，提高系統識別效率，需要高效的防碰撞技術來解決系統中的標簽競爭問題[1]。超高頻(Ultra High Frequency，UHF)射頻產品適合遠距離識別，并且對環境影響較小，成為了目前國際上RFID產品發展的熱點[2]。

在UHF段，ISO/IEC 18000-6 Type A和Type B是世界標準組織早先提出的兩種技術標準。2005年，全球產品電子代碼中心(EPC global)的Class-1 Gen-2[3](Q算法)標準被修改為了ISO/IEC 18000-6 Type C標準[4]。其中，Type A與Type C是基于隨機性算法的協議標準；Type B是基于確定性算法的協議標準[5]。

本文提出了一種基于隨機生成樹的多維Q選擇算法，是一種確定性算法與隨機性算法的混合算法。本文第二部分針對ISO/IEC 18000-6 Type C(以下簡稱ISO 18000-6C)標準所應用的Q算法進行了介紹；在第三部分對該創新算法進行介紹；第四部分 對該算法進行了性能仿真；第五部分給出了相關結論。

2 EPC Global Class-1 Gen-2和ISO 18000-6C標準下的防碰撞算法

EPC Global Class-1Gen-2即Q算法，它本質上接近動態幀時隙ALOHA算法，系統內標簽的狀況如圖1所示：

圖1 基于Q參數的隨機性算法碰撞情況示意圖

在Q算法中，參數Q是[0，15]之間的整數。由圖1中第一幀可見，各標簽通過在[0，2Q-1]內選擇不同隨機數使自身落在了對應的時隙中，這樣的隨機選擇產生了有限規模的若干空時隙、成功時隙和碰撞時隙。后續幀的情況與之類似。在動態幀時隙ALOHA算法中，系統根據標簽規模決定幀長；而在如上的Q算法中，系統根據實時碰撞情況決定幀長和時隙的分配，并可以隨時結束當前幀。值得注意的是，Q算法只關注選擇0的標簽，而落在其他時隙內的標簽，無論該時隙內有無碰撞，讀寫器并不和它們建立通信。

Q值將系統實時碰撞情況反饋到算法前端，通過不斷的自我刷新決定當前幀的時隙數分配和退出，從而改變系統的碰撞情況。Q值的參與既是對碰撞的檢測，也是對標簽規模的一種估計，更是對碰撞約束和控制的過程。

在參數Q的計算中，偶爾一次的碰撞或無標簽并不代表Q值過小或過大。且系統每一次調整Q都會造成一定的系統延時與設備損耗[6]。為了避免這種不穩定，降低算法成本，ISO 18000-6C標準提出了一種帶有參數C的Q算法流程。C是一個在[0.1，0.5]之間動態調整的小數[7-8]。

另外，標簽碰撞情況的改變并不隨即反映在Q值上，而是依靠參數C將這個變化縮小保留其趨勢，累計在內部數據Qfp上，Qfp是Q值得浮點數表現形式。當Qfp的變化積累到一定程度，其值再向Q彈出。但是，這使得Q值對系統的碰撞情況變得不敏感，時隙數的調整不能很好地適應碰撞情況，系統效率會降低。

帶參數C的Q算法流程圖如圖2：

圖2 帶參數C的Q算法偽程序流程圖

3 基于隨機生成樹的多維Q選擇算法

3.1 算法原理

為了減少Q的調整次數，進一步提高系統效率，本文提出一種改進算法：基于隨機生成樹的多維Q選擇算法(Multiple Dimensional Q-Selection with Random Tree，MDQRT)。該算法引入一個新的參數 ：入口容量(IC：Ingress Capacity)，定義為Q算法的選擇維數，可以取任意正整數。。當系統中選擇0的標簽數大于IC時，系統調整Q值使其有增大的趨勢；當系統中選擇0的標簽數小于等于IC且不為0時，這些標簽將離開Q選擇周期，被接入后續基于隨機生成樹的二進制樹算法[9]。在該算法中，這些標簽重新選擇0和1，每次選擇0的標簽繼續選擇0和1直至無碰撞識別，而每次選擇1的標簽掛起等待；當系統中選擇0的標簽數等于0時，系統調整Q值使其有減小的趨勢。顯然，Q算法中的IC=1。

MDQRT算法流程圖如圖3所示：

圖3 MDQRT算法流程圖

在MDQRT算法中，讀寫器與標簽之間的通信過程如下：

Step1：讀寫器向若干標簽發送一個包含參數Q的Query命令。Q為時隙數參數，每幀共2Q個時隙；

Step2：電子標簽在[0，2Q-1]之間選擇一個隨機數進入對應時隙，標簽同時產生一個16位的隨機數RN16。當標簽所選隨機數不為0時，不對讀寫器響應；僅當標簽選擇0時，標簽才允許對讀寫器進行響應。

標簽響應可能出現以下三種情況：

(1)小于等于IC個標簽選擇0：讀寫器將響應的標簽接入隨機生成二進制樹算法，通過不斷生成子樹遍歷各個標簽建立通信并讀取。對于每個可通信的標簽，其RN16到達讀寫器，讀寫器返回ACK命令，請求標簽的EPC。若成功讀取，讀寫器將標簽滅活。Q值不變，進入下一Q選擇周期；

(2)無標簽選擇0：即無標簽響應讀寫器，Q值將通過參數C的調整進行適當縮小，讀寫器發送Query Adjust命令，開始下一Q選擇周期；

(3)大于IC個標簽選擇0：多于IC個標簽選擇同一時隙時，超過了入口容量的值，因此會發生碰撞，Q值將通過參數C的調整適當加大，讀寫器發送Query Adjust命令，開始下一Q選擇周期。

3.2 MDQRT算法實例

設在一RFID系統中，系統某一時刻參數狀態如下：

1.標簽數=200；

2.Q=8；

3.IC=6。

算法識別過程如下：

a.這批標簽收到帶有參數Q的Query命令，則每一個標簽產生一位[0，28-1]內的隨機數響應該命令；

b.在這一個隨機過程中沒有標簽選擇隨機數0，即沒有標簽能夠應答讀寫器，如圖4(a)中所示；

c.系統重新向標簽發送Query命令，每一個標簽重新產生一位隨機數響應Query命令；

d.此次系統中有7個標簽以0響應讀寫器，如圖4(b)中所示；

e.由于IC<7，系統再次向標簽發送Query命令，則每一個標簽再次產生一位隨機數響應Query命令；

f.此次系統中有5個標簽以0響應讀寫器，如圖4(c)中所示；

(a) (b) (c) 圖4 Q標簽選擇隨機數過程

g.由于IC>5，這5個標簽被接入二進制樹流程；

h.基于隨機生成樹的二進制樹流程中，標簽隨機選擇0或1。其中2個選1的標簽被掛起，3個選0的標簽進入下一分支；

i.這3個標簽繼續選擇0與1。其中1個選1的標簽掛起，2個選0的標簽進入下一分支；

j.這2個標簽繼續選擇0與1。其中1個選1的標簽掛起，1個選0的標簽被讀取；上述過程如圖5所示：

圖5 隨機樹的生成與標簽的讀取

k.被掛起的標簽重復類似f，g的步驟，直至剩余所有標簽均被讀取。

由算法實例可以看出，在Q選擇過程中，若選擇0的標簽數量小于等于IC，系統將以隨機生成樹的形式快速將其識別，避免了參數Q的過多調整，同時也提高了系統效率。

4 MDQRT算法仿真與性能分析

參數C的提出，使得Q算法在Q參數的調整頻率上大大降低，降低了設備的損耗。而在算法的效率上，卻并未顯出優勢。本文將在MATLAB環境下對Q算法、帶有參數C的改進算法及MDQRT算法進行仿真，對其性能進行比較和分析。

4.1 Q參數的改變情況

在RFID系統中，Q值每調整一次，標簽的動態功耗量便會增加約0.8μw。因而在標簽較多的情況下，減少Q參數改變的頻率，是優化系統性能的重要目標之一。圖6是在一次識別過程中，Q算法、帶有參數C的Q算法及MDQRT算法中Q值改變情況的仿真結果：

圖6 三種算法Q值改變情況仿真

由圖6可看出，MDQRT算法在參數Q的波動上均明顯優于其他兩種算法。經過100次的獨立重復的識別過程，統計結果如圖7所示：

(a) (b)圖7 通信周期與Q改變次數積累圖

由圖7(a)可以看出，三種算法中的參數Q改變的累積過程各聚攏為一簇直線；(b)圖是(a)圖的平均效果。首先可以看出，Q算法與帶有參數C的Q算法相比，前者效率較高但Q值改變過于頻繁；后者Q值改變次數減少但是其效率降低。其次，MDQRT相較于另外兩種算法，參數Q的改變次數非常少，而所消耗通信周期也非常短。同時，由各直線簇的離散程度可看出各算法的穩定性差異，MDQRT的直線簇相比其他兩種算法的更加集中，反映出其更加優越的穩定性。

4.2 系統效率情況

MDQRT算法的效率如圖8所示：

(a) (b)圖8 三種算法系統效率圖

圖8(a)為三種算法的實時系統效率圖。對其進行平滑后，得出如圖8(b)所示的平滑效率曲線。顯然，MDQRT在系統效率上遠遠領先與帶有參數C的Q算法和EPC C1G2標準下基于Q選擇的防碰撞算法。本文通過仿真計算得出參數為IC=6時的MDQRT算法系統效率值：

(1)

從圖中還可知，EPC global C1G2協議下的Q算法效率約為0.41，ISO 18000-6C協議下帶有參數C的Q算法效率約為0.35。

4.3 IC取值分析

IC的取值影響標簽的識別效率，對此本文進行了仿真，如圖9所示：

圖9 入口容量IC取值與系統效率關系圖

圖中系統效率是不同規模標簽下效率的平均值。隨著標簽數量的改變，IC的取值并不呈現單調遞增或遞減的情況，而是在IC=10的時候，系統效率取得極值：

ηMDQRT≈0.5195

(2)

5 結論

防碰撞技術已成為RFID系統大規模應用的關鍵技術之一，本文在ISO18000-6C標準防碰撞算法的基礎上，結合二進制樹確定性算法，提出了一種帶有入口容量的多維Q選擇算法。仿真結果顯示，該算法相比現有的Q算法及其改進算法，有效減少了設備的損耗，提高了系統效率，性能上更具穩定性。今后，在Q選擇與確定性算法的對接上，將實現更深入的討論和研究。

[1]童喬玲.RFID閱讀器芯片設計及通訊算法研究[D].華中科技大學，2013.

[2]馬倩，石良平，周立宏.ISO18000_6C標準的防碰撞算法研究[J].計算機應用，2008，28(12)：341-343.

[3]EPC global Inc.EPCTM radio-frequency identity protocols class-1 gen-2 UHF RFID protocol for communications at 860MHz-960 MHz Version 1.2.0[S].Lawrenceville：EPC global Inc，2008.

[4]Huiyang Wang，Xiangdong You，Yinghua Cui.A Stack-Like Optimal Q-Algorithm For The ISO 18000-6C in RFID Systems[C].Proceedings of IC-NIDC，2012：164-168.

[5]Wong C P，Quanyuan Feng.Grouping Based Bit-Slot ALOHA Protocol for Tag Anti-Collision in RFID Systems[J].IEEE Communications Letters，2007，111(12).

[6]韓振偉，宋克非.射頻識別防碰撞Q算法的分析與改進[J].計算機工程與設計，2011，32(7)：2314-2318.

[7]王曉東，戎蒙恬.基于Q-選擇的RFID防碰撞算法的研究[J].計算機仿真，2008，26(5)：124-126.

[8]Muhammad Umer Farooq，Muddassar Asif，Syed Waqar Nabi，M Adnan Qureshi.Optimal Adjustment Parameters for EPC Global RFID Anti-Collision Q-Algorithm in Different Traffic Scenarios[C].10th International Conference on Frontiers of Information Technology，2012.

[9]李瑾.無線射頻識別(RFID)防碰撞算法的研究和仿真[D].北京交通大學，2007：30-53.