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

靳曉芳，黃祥林，朱允

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

1 引言

隨著射頻識(shí)別技術(shù)的發(fā)展以及應(yīng)用規(guī)模的擴(kuò)大，讀寫器需要在短時(shí)間內(nèi)識(shí)別多個(gè)標(biāo)簽。當(dāng)識(shí)別區(qū)域有多個(gè)標(biāo)簽到達(dá)時(shí)，標(biāo)簽信號(hào)的混疊造成碰撞。為了避免此情況發(fā)生，提高系統(tǒng)識(shí)別效率，需要高效的防碰撞技術(shù)來解決系統(tǒng)中的標(biāo)簽競(jìng)爭(zhēng)問題[1]。超高頻(Ultra High Frequency，UHF)射頻產(chǎn)品適合遠(yuǎn)距離識(shí)別，并且對(duì)環(huán)境影響較小，成為了目前國(guó)際上RFID產(chǎn)品發(fā)展的熱點(diǎn)[2]。

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

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

2 EPC Global Class-1 Gen-2和ISO 18000-6C標(biāo)準(zhǔn)下的防碰撞算法

EPC Global Class-1Gen-2即Q算法，它本質(zhì)上接近動(dòng)態(tài)幀時(shí)隙ALOHA算法，系統(tǒng)內(nèi)標(biāo)簽的狀況如圖1所示：

圖1 基于Q參數(shù)的隨機(jī)性算法碰撞情況示意圖

在Q算法中，參數(shù)Q是[0，15]之間的整數(shù)。由圖1中第一幀可見，各標(biāo)簽通過在[0，2Q-1]內(nèi)選擇不同隨機(jī)數(shù)使自身落在了對(duì)應(yīng)的時(shí)隙中，這樣的隨機(jī)選擇產(chǎn)生了有限規(guī)模的若干空時(shí)隙、成功時(shí)隙和碰撞時(shí)隙。后續(xù)幀的情況與之類似。在動(dòng)態(tài)幀時(shí)隙ALOHA算法中，系統(tǒng)根據(jù)標(biāo)簽規(guī)模決定幀長(zhǎng)；而在如上的Q算法中，系統(tǒng)根據(jù)實(shí)時(shí)碰撞情況決定幀長(zhǎng)和時(shí)隙的分配，并可以隨時(shí)結(jié)束當(dāng)前幀。值得注意的是，Q算法只關(guān)注選擇0的標(biāo)簽，而落在其他時(shí)隙內(nèi)的標(biāo)簽，無(wú)論該時(shí)隙內(nèi)有無(wú)碰撞，讀寫器并不和它們建立通信。

Q值將系統(tǒng)實(shí)時(shí)碰撞情況反饋到算法前端，通過不斷的自我刷新決定當(dāng)前幀的時(shí)隙數(shù)分配和退出，從而改變系統(tǒng)的碰撞情況。Q值的參與既是對(duì)碰撞的檢測(cè)，也是對(duì)標(biāo)簽規(guī)模的一種估計(jì)，更是對(duì)碰撞約束和控制的過程。

在參數(shù)Q的計(jì)算中，偶爾一次的碰撞或無(wú)標(biāo)簽并不代表Q值過小或過大。且系統(tǒng)每一次調(diào)整Q都會(huì)造成一定的系統(tǒng)延時(shí)與設(shè)備損耗[6]。為了避免這種不穩(wěn)定，降低算法成本，ISO 18000-6C標(biāo)準(zhǔn)提出了一種帶有參數(shù)C的Q算法流程。C是一個(gè)在[0.1，0.5]之間動(dòng)態(tài)調(diào)整的小數(shù)[7-8]。

另外，標(biāo)簽碰撞情況的改變并不隨即反映在Q值上，而是依靠參數(shù)C將這個(gè)變化縮小保留其趨勢(shì)，累計(jì)在內(nèi)部數(shù)據(jù)Qfp上，Qfp是Q值得浮點(diǎn)數(shù)表現(xiàn)形式。當(dāng)Qfp的變化積累到一定程度，其值再向Q彈出。但是，這使得Q值對(duì)系統(tǒng)的碰撞情況變得不敏感，時(shí)隙數(shù)的調(diào)整不能很好地適應(yīng)碰撞情況，系統(tǒng)效率會(huì)降低。

帶參數(shù)C的Q算法流程圖如圖2：

圖2 帶參數(shù)C的Q算法偽程序流程圖

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

3.1 算法原理

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

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

圖3 MDQRT算法流程圖

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

Step1：讀寫器向若干標(biāo)簽發(fā)送一個(gè)包含參數(shù)Q的Query命令。Q為時(shí)隙數(shù)參數(shù)，每幀共2Q個(gè)時(shí)隙；

Step2：電子標(biāo)簽在[0，2Q-1]之間選擇一個(gè)隨機(jī)數(shù)進(jìn)入對(duì)應(yīng)時(shí)隙，標(biāo)簽同時(shí)產(chǎn)生一個(gè)16位的隨機(jī)數(shù)RN16。當(dāng)標(biāo)簽所選隨機(jī)數(shù)不為0時(shí)，不對(duì)讀寫器響應(yīng)；僅當(dāng)標(biāo)簽選擇0時(shí)，標(biāo)簽才允許對(duì)讀寫器進(jìn)行響應(yīng)。

標(biāo)簽響應(yīng)可能出現(xiàn)以下三種情況：

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

(2)無(wú)標(biāo)簽選擇0：即無(wú)標(biāo)簽響應(yīng)讀寫器，Q值將通過參數(shù)C的調(diào)整進(jìn)行適當(dāng)縮小，讀寫器發(fā)送Query Adjust命令，開始下一Q選擇周期；

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

3.2 MDQRT算法實(shí)例

設(shè)在一RFID系統(tǒng)中，系統(tǒng)某一時(shí)刻參數(shù)狀態(tài)如下：

1.標(biāo)簽數(shù)=200；

2.Q=8；

3.IC=6。

算法識(shí)別過程如下：

a.這批標(biāo)簽收到帶有參數(shù)Q的Query命令，則每一個(gè)標(biāo)簽產(chǎn)生一位[0，28-1]內(nèi)的隨機(jī)數(shù)響應(yīng)該命令；

b.在這一個(gè)隨機(jī)過程中沒有標(biāo)簽選擇隨機(jī)數(shù)0，即沒有標(biāo)簽?zāi)軌驊?yīng)答讀寫器，如圖4(a)中所示；

c.系統(tǒng)重新向標(biāo)簽發(fā)送Query命令，每一個(gè)標(biāo)簽重新產(chǎn)生一位隨機(jī)數(shù)響應(yīng)Query命令；

d.此次系統(tǒng)中有7個(gè)標(biāo)簽以0響應(yīng)讀寫器，如圖4(b)中所示；

e.由于IC<7，系統(tǒng)再次向標(biāo)簽發(fā)送Query命令，則每一個(gè)標(biāo)簽再次產(chǎn)生一位隨機(jī)數(shù)響應(yīng)Query命令；

f.此次系統(tǒng)中有5個(gè)標(biāo)簽以0響應(yīng)讀寫器，如圖4(c)中所示；

(a) (b) (c) 圖4 Q標(biāo)簽選擇隨機(jī)數(shù)過程

g.由于IC>5，這5個(gè)標(biāo)簽被接入二進(jìn)制樹流程；

h.基于隨機(jī)生成樹的二進(jìn)制樹流程中，標(biāo)簽隨機(jī)選擇0或1。其中2個(gè)選1的標(biāo)簽被掛起，3個(gè)選0的標(biāo)簽進(jìn)入下一分支；

i.這3個(gè)標(biāo)簽繼續(xù)選擇0與1。其中1個(gè)選1的標(biāo)簽掛起，2個(gè)選0的標(biāo)簽進(jìn)入下一分支；

j.這2個(gè)標(biāo)簽繼續(xù)選擇0與1。其中1個(gè)選1的標(biāo)簽掛起，1個(gè)選0的標(biāo)簽被讀??；上述過程如圖5所示：

圖5 隨機(jī)樹的生成與標(biāo)簽的讀取

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

由算法實(shí)例可以看出，在Q選擇過程中，若選擇0的標(biāo)簽數(shù)量小于等于IC，系統(tǒng)將以隨機(jī)生成樹的形式快速將其識(shí)別，避免了參數(shù)Q的過多調(diào)整，同時(shí)也提高了系統(tǒng)效率。

4 MDQRT算法仿真與性能分析

參數(shù)C的提出，使得Q算法在Q參數(shù)的調(diào)整頻率上大大降低，降低了設(shè)備的損耗。而在算法的效率上，卻并未顯出優(yōu)勢(shì)。本文將在MATLAB環(huán)境下對(duì)Q算法、帶有參數(shù)C的改進(jìn)算法及MDQRT算法進(jìn)行仿真，對(duì)其性能進(jìn)行比較和分析。

4.1 Q參數(shù)的改變情況

在RFID系統(tǒng)中，Q值每調(diào)整一次，標(biāo)簽的動(dòng)態(tài)功耗量便會(huì)增加約0.8μw。因而在標(biāo)簽較多的情況下，減少Q(mào)參數(shù)改變的頻率，是優(yōu)化系統(tǒng)性能的重要目標(biāo)之一。圖6是在一次識(shí)別過程中，Q算法、帶有參數(shù)C的Q算法及MDQRT算法中Q值改變情況的仿真結(jié)果：

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

由圖6可看出，MDQRT算法在參數(shù)Q的波動(dòng)上均明顯優(yōu)于其他兩種算法。經(jīng)過100次的獨(dú)立重復(fù)的識(shí)別過程，統(tǒng)計(jì)結(jié)果如圖7所示：

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

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

4.2 系統(tǒng)效率情況

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

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

圖8(a)為三種算法的實(shí)時(shí)系統(tǒng)效率圖。對(duì)其進(jìn)行平滑后，得出如圖8(b)所示的平滑效率曲線。顯然，MDQRT在系統(tǒng)效率上遠(yuǎn)遠(yuǎn)領(lǐng)先與帶有參數(shù)C的Q算法和EPC C1G2標(biāo)準(zhǔn)下基于Q選擇的防碰撞算法。本文通過仿真計(jì)算得出參數(shù)為IC=6時(shí)的MDQRT算法系統(tǒng)效率值：

(1)

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

4.3 IC取值分析

IC的取值影響標(biāo)簽的識(shí)別效率，對(duì)此本文進(jìn)行了仿真，如圖9所示：

圖9 入口容量IC取值與系統(tǒng)效率關(guān)系圖

圖中系統(tǒng)效率是不同規(guī)模標(biāo)簽下效率的平均值。隨著標(biāo)簽數(shù)量的改變，IC的取值并不呈現(xiàn)單調(diào)遞增或遞減的情況，而是在IC=10的時(shí)候，系統(tǒng)效率取得極值：

ηMDQRT≈0.5195

(2)

5 結(jié)論

防碰撞技術(shù)已成為RFID系統(tǒng)大規(guī)模應(yīng)用的關(guān)鍵技術(shù)之一，本文在ISO18000-6C標(biāo)準(zhǔn)防碰撞算法的基礎(chǔ)上，結(jié)合二進(jìn)制樹確定性算法，提出了一種帶有入口容量的多維Q選擇算法。仿真結(jié)果顯示，該算法相比現(xiàn)有的Q算法及其改進(jìn)算法，有效減少了設(shè)備的損耗，提高了系統(tǒng)效率，性能上更具穩(wěn)定性。今后，在Q選擇與確定性算法的對(duì)接上，將實(shí)現(xiàn)更深入的討論和研究。

[1]童喬玲.RFID閱讀器芯片設(shè)計(jì)及通訊算法研究[D].華中科技大學(xué)，2013.

[2]馬倩，石良平，周立宏.ISO18000_6C標(biāo)準(zhǔn)的防碰撞算法研究[J].計(jì)算機(jī)應(yīng)用，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]韓振偉，宋克非.射頻識(shí)別防碰撞Q算法的分析與改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32(7)：2314-2318.

[7]王曉東，戎蒙恬.基于Q-選擇的RFID防碰撞算法的研究[J].計(jì)算機(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]李瑾.無(wú)線射頻識(shí)別(RFID)防碰撞算法的研究和仿真[D].北京交通大學(xué)，2007：30-53.