基于標簽分組的動態(tài)幀時隙ALOHA算法

雷隆毓，蔣榮斌，陳子妍，羅雪梅+

(1.貴州大學(xué) 電氣工程學(xué)院，貴州 貴陽 550025；2.六盤水市第二人民醫(yī)院，貴州 六盤水 553400)

0 引 言

無線射頻識別技術(shù)RFID(radio frequency identification)是一種可廣泛應(yīng)用在信息化領(lǐng)域的自動識別技術(shù)[1]。在無線射頻識別系統(tǒng)中，在讀寫器可識別的范圍內(nèi)出現(xiàn)多個標簽發(fā)生信息碰撞。因此如何有效、合理解決上述信息碰撞問題成為多標簽防碰撞中最需要進行研究的問題。無線射頻識別系統(tǒng)通常使用TDMA(時分多址)方式進行數(shù)據(jù)通信。

現(xiàn)使用時分多址訪問接入方式的多標簽防碰撞算法分為兩種，一種是相對隨機性的ALOHA算法，一種是非概率型的二進制樹算法[2]。ALOHA算法常常用于實際中處理多標簽防碰撞算法，是由于具有隨機性的ALOHA算法對標簽的要求相對較低，但同時恰恰因為不確定的隨機性，ALOHA算法會出現(xiàn)部分標簽遺漏識別的問題，即一個標簽一直不被抽取識別，導(dǎo)致系統(tǒng)難以及時的識別。ALOHA算法因為具有隨機性，因此系統(tǒng)識別效率相對比較低，且最大的系統(tǒng)識別效率為36.8%，然而該情況僅出現(xiàn)于待識別標簽數(shù)目和閱讀器給定的時隙數(shù)目相同時。該結(jié)論可在參考文獻中參見。由于存在該情況，如此便對標簽估計算法的精準度有了一定的要求。而標簽識別過程發(fā)生碰撞的主要原因在于標簽分配時隙具有隨機性，無法控制標簽可以均勻分配在幀時隙中，于是本文針對以上兩個原因提出了一種分組算法，減少了對標簽估計算法[3]的精準度并盡量使得標簽可以均勻分配在每個時隙中，降低了時隙內(nèi)標簽的碰撞幾率，提高了系統(tǒng)識別效率。

1 動態(tài)幀時隙ALOHA算法分析

由上文可知，僅當時隙數(shù)和標簽數(shù)相等時，可得到系統(tǒng)的最大吞吐量。而在理想實驗測試中，因為硬件問題，當幀時隙取值為256時系統(tǒng)已經(jīng)達最大吞吐率。脫離理想狀態(tài)后，在實際操作的過程中，在各種因素影響下，例如空氣介質(zhì)、空間條件等等，標簽的吞吐量常常無法達到最大值。因此在FSA算法(幀時隙ALOHA算法)的基礎(chǔ)上提出了動態(tài)幀時隙ALOHA(DFSA)算法[4,12]。常見的動態(tài)幀時隙ALOHA算法中往往包含了標簽估計算法，因為需要對標簽總數(shù)做一個估算，此后再通過標簽安排時隙發(fā)送信息從而進行識別，此間對發(fā)生了碰撞的標簽做某種的方法進行重新識別，關(guān)于DFSA算法的具體實現(xiàn)步驟可以在相關(guān)的參考文獻中參見，因此此處便不多做概述。

在總結(jié)了近年來在DFSA算法基礎(chǔ)上為提高系統(tǒng)識別率改進的多種算法，我們可知若想要提高系統(tǒng)的吞吐率和系統(tǒng)識別效率，可大致分為3個方法：

(1)使得幀長與待識別標簽數(shù)一致。如同上文提及的吞吐率最大值的要求，即：使得幀長與待識別的標簽數(shù)保持一致。由于標簽數(shù)量不能直接提供給閱讀器，因此大家對DFSA算法研究的一個方向在于如何精確估計待識別的標簽數(shù)，即標簽估計算法。標簽估計算法通常是依據(jù)實驗后幾次碰撞情況估計標簽總數(shù)，或者估算下一幀的幀長，依此提高系統(tǒng)的識別效率。而該方法也只能保證系統(tǒng)的吞吐率比較接近于最大吞吐率0.368[5]。比較常用的標簽估計算法有：Schoute標簽估計法、切比雪夫不等式標簽估計法、貝葉斯標簽估計法等。但是改進的標簽估計算法各自有各自的缺點，精確性高但是計算要求高，復(fù)雜度高，或者實用性不強；

(2)對碰撞時隙和空閑時隙的重新安排和利用。在識別的過程中，最重要的是成功時隙，而空閑時隙和碰撞時隙都屬于浪費的時隙，對浪費的時隙重新安排或者減少浪費時隙的產(chǎn)生會使得一個幀長中成功識別的標簽數(shù)增加，而這是提高吞吐率和系統(tǒng)識別效率的另一個研究方向。在此方向的例子有：增加隨機數(shù)，增加第二次標簽分配的機會，保證碰撞時隙時依然還有標簽可以識別，減少碰撞時隙的浪費，從而提高了系統(tǒng)識別效率和系統(tǒng)吞吐率；使用碼分多址方法處理碰撞時隙中的標簽，同樣是減少碰撞時隙的浪費，碰撞標簽后閱讀器驗證標簽擴展碼，識別相應(yīng)的標簽[6]；使用自適應(yīng)預(yù)約時隙的方法增加時隙利用率，直接閱讀成功時隙，對空閑時隙和碰撞時隙進行忽略不識別等方法[7]。該類方法具有可行性，系統(tǒng)識別效率低原因在于產(chǎn)生了過多空閑時隙和碰撞時隙，因此對空閑時隙和碰撞時隙進行控制可以有效避免時隙的浪費；

(3)由于讀寫器硬件的原因，ALOHA算法的最大幀長時隙數(shù)為256個。隨著標簽數(shù)量的增加，幀長度不能增加，導(dǎo)致標簽之間的碰撞越來越嚴重，碰撞時隙的數(shù)量越來越多，空閑時隙和成功時隙的數(shù)量越來越少，導(dǎo)致在識別整個標簽組時，總時隙的數(shù)量大大增加，這導(dǎo)致系統(tǒng)吞吐量下降，識別效率低[8]。于是面對大量的標簽數(shù)據(jù)，可將大量標簽進行分組，保證分組后組內(nèi)標簽數(shù)量較少，使發(fā)生碰撞的幾率不會因為標簽數(shù)量的增加而增加。因此分組方法也成為了另一個研究主流方向，最經(jīng)典的分組方法為分組動態(tài)幀時隙算法(GDFSA)。此后也有許多的分組方法，比如Q算法及MQ算法[9]、基于哈希函數(shù)分組算法[10]、復(fù)雜度較高的PIGDFSA算法[11]等。分組算法適用于標簽數(shù)量較大的場景下。

2 改進的DFSA算法

2.1 標簽分組的提出

標簽發(fā)生碰撞是因為DFSA算法中多個標簽產(chǎn)生的隨機數(shù)一致，而當標簽數(shù)量較大，進行時隙分配時越發(fā)容易出現(xiàn)多個標簽選擇了同個時隙。

為確定系統(tǒng)識別效率降低趨勢，在使得幀長與標簽一致的情況下，進行DFSA仿真實驗[10]。標簽總數(shù)取值為1到256，實驗結(jié)果為系統(tǒng)識別效率隨著標簽總數(shù)的增加最后趨近于0.368，圖1為局部放大圖，更加直觀地觀察到系統(tǒng)識別效率隨著標簽總數(shù)增加的降低速率。

圖1 DFSA算法隨標簽增多的系統(tǒng)識別效率變化

由圖1可知，系統(tǒng)識別效率隨著標簽數(shù)量的增多而逐漸降低，在10個標簽以內(nèi)時，標簽的降低速率達到最快，此后系統(tǒng)識別效率的降低速率趨于緩慢，最后保持在0.368左右。若將每組標簽數(shù)量控制在較少數(shù)額時，系統(tǒng)的識別效率較高，控制在系統(tǒng)識別效率最高處，即標簽數(shù)量為1到2個，那么組別會變多，并不實際，然而控制每組標簽數(shù)量大于10則系統(tǒng)效率較低，控制每組標簽數(shù)量的意義不大，因而取8，可被256整除，同時當每組標簽為8個以內(nèi)時，可以更好提高系統(tǒng)識別效率。

使得分組后每組標簽數(shù)量較少的思想確定了，那么如何讓每組中的這些標簽均勻分布在各個時隙中，于是考慮到標簽的ID信息。因標簽中存儲數(shù)據(jù)的寄存器占8位，標簽ID號可通過取模運算分到1到256之間(十進制)，因此可以將標簽以ID信息進行分組，可分為256個組。

256組中每個組相互之間是可以區(qū)別開的。因此考慮是否可以構(gòu)造出單組內(nèi)標簽數(shù)為8且標簽為連續(xù)ID或者有一定大小順序。那么需要在由標簽ID分組的256組內(nèi)連續(xù)選擇8組，并在每組內(nèi)抽取一個標簽構(gòu)成新的組。而抽取的過程使用的方法和DFSA算法相似，通過使用隨機數(shù)的方法。然而通過隨機數(shù)，具有一定隨機性，因此不一定能夠保證每個組里能夠抽取一個標簽，因此新的一組內(nèi)的標簽ID不一定連續(xù)，但是卻一定是保持著從小到大的順序，而其中含有空閑時隙在內(nèi)。

大致算法路線為：閱讀器挑選長度為8的連續(xù)組號，發(fā)出查詢組號和一個隨機數(shù)命令(閱讀器的隨機數(shù)不是隨機產(chǎn)生，而是從1開始，一直到標簽產(chǎn)生隨機數(shù)的最大值)，當標簽組號與閱讀器提供的組號一致時，標簽才能進行響應(yīng)閱讀器，否則處于睡眠狀態(tài)。每組標簽在存儲組號的同時存儲一個隨機數(shù)，當組號一致時，識別隨機數(shù)，當標簽的隨機數(shù)與閱讀器提供的隨機數(shù)一致時，才能響應(yīng)閱讀器，并向閱讀器發(fā)送識別請求。此時標簽需要有能夠產(chǎn)生隨機數(shù)的能力，同時需要具有一個寄存器、存儲組號和一個隨機數(shù)。

但是該算法容易出現(xiàn)兩個問題：一個問題是因為本算法和DFSA算法都使用了隨機數(shù)，因此也會出現(xiàn)標簽產(chǎn)生的隨機數(shù)相同情況，即當閱讀器和標簽比對隨機數(shù)的時候，可能會出現(xiàn)多個標簽隨機數(shù)相同的情況，會發(fā)生多個相同ID號(這里指的是電子標簽根據(jù)ID信息分的組號，為了方便我們直接說ID號)的標簽發(fā)送識別請求。該情況發(fā)生后，無法保證該幀里的標簽個數(shù)較少，會影響系統(tǒng)識別效率,使得本文分組方法毫無意義。而產(chǎn)生該情況很大的一方面是由于隨機數(shù)的范圍較小，標簽?zāi)軌虍a(chǎn)生隨機數(shù)比較單一。另一個問題是因為隨機數(shù)的范圍無法確定，或者范圍過大，因此標簽產(chǎn)生的隨機數(shù)與閱讀器產(chǎn)生的隨機數(shù)總是不一致，如此需要閱讀器反復(fù)產(chǎn)生隨機數(shù)并發(fā)送，如此會產(chǎn)生大量的空閑時隙，增加了算法的復(fù)雜度，降低了系統(tǒng)識別效率。因此隨機數(shù)的取值范圍不應(yīng)該太大或者太小。因此可以考慮每組的標簽平均數(shù)，如此便需要估計標簽總數(shù)，以確定隨機數(shù)的確定范圍，即總數(shù)N除256。但此處的估算的標簽總數(shù)對準確性并沒有嚴格要求，只需要大致的估算范圍即可。

因為標簽ID號逐漸增加，標簽使用哈希函數(shù)設(shè)定發(fā)送信息的時隙，H=id%L，其中L=8，標簽根據(jù)自身的ID號，通過哈希函數(shù)計算，確定了一幀長內(nèi)發(fā)送信息的時隙，并將信息設(shè)置為時隙時間發(fā)送。這里若使用DFSA算法，使標簽產(chǎn)生隨機時隙，相對隨機化，那么將標簽事前由ID信息分組為256組便無意義，因為無法保證新組內(nèi)標簽為連續(xù)ID，因此使用哈希函數(shù)分配時隙，減少了碰撞可能性。

2.2 組內(nèi)識別方法

同上述第一個問題，當標簽產(chǎn)生隨機數(shù)時相同ID號的多個標簽產(chǎn)生了相同隨機數(shù)，同時和閱讀器產(chǎn)生的隨機數(shù)一致時會導(dǎo)致新組一組內(nèi)出現(xiàn)多個相同的ID標簽，這里的哈希函數(shù)并沒有發(fā)揮使得標簽可以分散分布的作用，反而使得相同ID號的標簽分布在同一個時隙中，因此該類標簽在使用哈希函數(shù)分配時隙時，必定會發(fā)生碰撞，碰撞時隙增加，從而降低了系統(tǒng)識別效率。

系統(tǒng)識別效率是成功時隙除以總時隙，而總時隙包含了成功時隙、空閑時隙和碰撞時隙。若可以減少空閑時隙和碰撞時隙的浪費，便可以減少總時隙的時隙數(shù)，從而提高了系統(tǒng)識別效率。因此如何減少空閑時隙和碰撞時隙的浪費，這里考慮了將碰撞時隙進行重新分配，將碰撞的標簽在碰撞時隙和空閑時隙中進行重新安排，增加了空閑時隙和碰撞時隙的利用。那么便產(chǎn)生了問題，如何確定空閑時隙和碰撞時隙，這里便考慮了可以在組內(nèi)使用預(yù)分配方法，標簽對時隙進行預(yù)約并反饋給閱讀器，閱讀器反饋空閑時隙和碰撞時隙的記錄，標簽重新確定發(fā)送信息的時隙，使得碰撞時隙和空白時隙可以重新利用。同時也可以盡可能減少上述相同ID號的多個標簽產(chǎn)生相同隨機數(shù)時必定進行碰撞的幾率。

具體實現(xiàn)方法：在標簽識別之前，標簽發(fā)出預(yù)約時隙的申請，閱讀器接收申請后，對空白時隙和碰撞時隙進行記錄，同時向標簽返回空白時隙和碰撞時隙的記錄，標簽比對閱讀器返回的時隙記錄，若預(yù)約的時隙與閱讀器返回的時隙數(shù)一致，則重新在該時隙范圍內(nèi)重新選擇時隙進行信息發(fā)送，若標簽預(yù)約的時隙與閱讀器返回的時隙數(shù)不一致，表示標簽預(yù)約的時隙不屬于空閑時隙和碰撞時隙，而屬于成功時隙，則該標簽依照預(yù)約情況在該時隙發(fā)送信息。重新分配空閑時隙和碰撞時隙可以減少空白時隙和碰撞時隙的浪費，提高了時隙的利用率。

2.3 算法識別過程

算法識別過程具體步驟描述如下：

(1)標簽總數(shù)的估計：閱讀器第一次發(fā)送查詢指令和初始幀長度，閱讀器初始化計數(shù)值w，標簽返回自己的數(shù)據(jù)信息，閱讀器記錄空閑時隙、成功時隙和碰撞時隙，并使用標簽估計算法對標簽總數(shù)N進行大致估計，計算出隨機數(shù)的范圍[1:N/256]，并返回給標簽N值；

(2)標簽分組：電子標簽確定自身的組別，一共分成256組。同時，每個標簽隨機產(chǎn)生一個隨機數(shù)R,范圍為[1∶N/256]，存儲在標簽寄存器中；

(3)閱讀器發(fā)送組號命令：閱讀器生成連續(xù)的8個組號Gr(第一次的組號為1到8，此后組號為第一次組號加上計數(shù)值w*8，即首次組號為1到8，下一次為9到16，幾次類推)和一個隨機數(shù)V(此后每幀識別結(jié)束后V自增，直到V值到達隨機數(shù)的最大值)，閱讀器向標簽發(fā)出查詢組號和隨機數(shù)V命令；

(4)標簽響應(yīng)判定：當標簽組號與查詢的組號Gr一致時，標簽才能進行響應(yīng)閱讀器，否則處于睡眠狀態(tài)。當組號一致時，識別隨機數(shù)，當標簽的隨機數(shù)R與閱讀器提供的隨機數(shù)V一致時，才能響應(yīng)閱讀器，并向閱讀器發(fā)送識別請求；

(5)標簽預(yù)約時隙：標簽根據(jù)L=8使用哈希函數(shù)(H=id%L)確定發(fā)送信息的時隙，并向閱讀器預(yù)約；

(6)閱讀器記錄預(yù)約情況并返回：閱讀器記錄標簽預(yù)約時隙，返回碰撞時隙Sn、空白時隙S0，標簽比對閱讀器返回的時隙，若標簽預(yù)約的時隙不屬于閱讀器返回的時隙數(shù)內(nèi)時，則標簽將信息設(shè)置為該時隙進行信息發(fā)送。若標簽預(yù)約的時隙屬于閱讀器返回的時隙數(shù)內(nèi)時，則標簽在空白時隙S0和碰撞時隙Sn中重新選擇時隙進行信息發(fā)送，并設(shè)置該時隙發(fā)送信息；

(7)閱讀器進行一幀內(nèi)的標簽識別；

(8)判斷是否存在待識別標簽：閱讀器根據(jù)標簽預(yù)約情況及V值大小判斷組內(nèi)是否還有數(shù)據(jù)，有則進行第(3)步，發(fā)送同一個組號Gr，但產(chǎn)生下一個隨機數(shù)V，重新進行一組的標簽分配。若組內(nèi)無數(shù)據(jù)且V值已達最大值，則判斷計數(shù)值w是否為32，若小于32則計數(shù)值w自增一次并進行第(3)步，進行新的一組的標簽安排；若計數(shù)大于32則識別結(jié)束。

為了直觀地理解本文算法，圖2展示了本文算法的流程。

圖2 本文算法流程

3 仿真結(jié)果與分析

將本文算法與DFSA算法、哈希分組算法[10]在MATLAB平臺環(huán)境下分別進行模擬仿真，并對仿真的結(jié)果進行分析。使用的MATLAB軟件為R2014b，硬件環(huán)境是8核Intel i5處理器，底層操作系統(tǒng)為Windows 10。

此處為了方便對比，這里設(shè)置4種算法都已知標簽個數(shù)，且?guī)L與待識別的標簽數(shù)相等，當標簽總數(shù)大于256，初始查詢幀長設(shè)定長度為256。仿真的標簽總數(shù)設(shè)置為從50開始，間隔50個，一直到2000個。為保證數(shù)據(jù)的準確，實驗程序運行了100次取平均值。

3.1 系統(tǒng)識別效率對比分析

仿真時系統(tǒng)識別效率計算方法為：成功時隙/(成功時隙+碰撞時隙+空白時隙)，圖3為4種算法系統(tǒng)識別效率對比圖。

圖3 系統(tǒng)識別效率對比

DFSA算法和本文預(yù)約時隙算法都需要設(shè)定初始幀長為256，因此在標簽小于256時，空閑時隙浪費較多，因而系統(tǒng)識別效率較低。而哈希函數(shù)算法與本文算法都利用了標簽ID進行分組，沒有設(shè)定初始幀長為256，因而在標簽總數(shù)小于256時，避免了大量空閑時隙的浪費。因此出現(xiàn)在圖3中，當標簽數(shù)小于256時，4種算法出現(xiàn)了兩種方向的情況。

隨著標簽數(shù)量的增加，本文算法系統(tǒng)的識別效率在已知標簽總數(shù)的情況下，基本穩(wěn)定在0.6以上，而DFSA算法基本穩(wěn)定在0.36左右，明顯可知本文算法識別效率遠遠高于DFSA算法。對比本文算法和哈希函數(shù)分組算法，在標簽小于500之前，哈希函數(shù)算法的系統(tǒng)效率大致分布于0.45到0.6之間，而大于500之后，系統(tǒng)識別效率保持在0.4以上。而前500個標簽，哈希函數(shù)算法的系統(tǒng)效率較高，隨著標簽增加，系統(tǒng)效率變低的原因是標簽增加，在哈希函數(shù)分組后，組內(nèi)的標簽數(shù)也隨之增加，碰撞幾率增加，系統(tǒng)識別效率變低。而本算法由標簽ID信息不同分組成256個組，再按由小到大依次選取8組作為新的組，保證了新組內(nèi)的標簽數(shù)量較少。

而本文算法出現(xiàn)圖3中的階梯式的情況,特別是1到256之間，出現(xiàn)該現(xiàn)象是因為隨機數(shù)的選擇范圍，當由標簽ID信息分組的組內(nèi)標簽數(shù)普遍多于隨機數(shù)的范圍，標簽的碰撞幾率將增加，因此當標簽數(shù)為256的倍數(shù)時，系統(tǒng)效率相對較高，而當標簽數(shù)為256的倍數(shù)前一個數(shù)時，隨機數(shù)的范圍并不適合用于該標簽總數(shù)，組內(nèi)標簽數(shù)大于隨機數(shù)的最大值，因而容易產(chǎn)生碰撞，導(dǎo)致系統(tǒng)效率處于最低的狀態(tài)。

3.2 時隙開銷對比分析

圖4～圖6分別是4種算法的空白時隙、碰撞時隙、總時隙的對比圖。

圖4 空閑時隙對比

圖5 碰撞時隙對比

圖6 總時隙對比

由圖5可以看出本文算法產(chǎn)生的碰撞時隙和空閑時隙相對其它算法較少，而本文出現(xiàn)碰撞的原因主要是隨機數(shù)的重復(fù)，雖然使用了預(yù)約時隙的方法，使碰撞時隙重新得到安排，減少了碰撞幾率，但是還是會出現(xiàn)碰撞問題。其中本文預(yù)約時隙與DFSA算法都有初始幀長256的設(shè)定，因此在小于256時如圖4出現(xiàn)大量的空閑時隙浪費情況。

通過對比可以看出減少了碰撞的幾率和空閑時隙浪費的原因有兩種：一個是將標簽進行分組，對比本文算法和本文預(yù)約時隙時隙算法可看出，當標簽基數(shù)較大的時候，利用預(yù)約時隙的方法能夠減少碰撞時隙的產(chǎn)生，但這種減少的程度不夠大。而使用分組后，單組標簽較少，且按照標簽ID號的由小到大的順序安排時隙，使得碰撞幾率降低。因為限制了組內(nèi)標簽的數(shù)量，所以隨著標簽增加，哈希函數(shù)分組算法碰撞時隙和空閑時隙增加速度較快，而本文算法兩種時隙的增加速度較為緩慢。二是因為使用了預(yù)約時隙的方法。這點對比本文預(yù)約時隙算法和DFSA算法可以看出，預(yù)約時隙算法減少了碰撞時隙和空閑時隙的產(chǎn)生。

通過圖6可以看出隨著標簽數(shù)量的增加，雖然4種算法需要的總時隙時間都在增加，但因為本文算法的碰撞時隙和空白時隙的大大減少，本文算法所需要的總時隙的增加速度明顯緩慢。

4 結(jié)束語

本文算法進行了兩次分組，第一次將標簽由ID信息分組成256個組，第二次是按順序在8組內(nèi)隨機抽取每組的標簽，形成新的一組，如此限制了識別組內(nèi)標簽數(shù)量，保持著較少數(shù)量，后由標簽ID信息使用哈希函數(shù)分配時隙，使得標簽可以相對均勻分布于時隙中，減少碰撞幾率。而在該組內(nèi)實行預(yù)約時隙算法，盡可能減少標簽生成的隨機數(shù)發(fā)生重復(fù)所帶來的碰撞。從適用性上看，本文算法的分組方法適合于標簽數(shù)量較大且標簽ID不完全一致的場景。本文算法在總時隙數(shù)、碰撞時隙數(shù)、空閑時隙數(shù)上都有明顯的較少，在系統(tǒng)識別效率上有著明顯的提高，可使得系統(tǒng)識別效率維持在0.6以上。優(yōu)勢相對明顯，具有研究意義和應(yīng)用意義。如何更好確定隨機數(shù)的取值范圍和是否可以不使用預(yù)約時隙方法是本文算法尚未解決的問題。