一種新型去除空閑和減少碰撞的幀時隙ALOHA防碰撞算法

鄧紅衛(wèi)，林紫玉，姚銘，李民

(1.衡陽師范學院 計算機科學與技術學院，湖南 衡陽 421002；2.智能信息處理與應用湖南省重點實驗室，湖南 衡陽 421002)

在動態(tài)RFID系統(tǒng)中，標簽經(jīng)過長度有限的識別區(qū)域，識別時間受限，標簽碰撞及丟失問題不可避免。文獻[1]提出一種基于比特查詢的查詢方法，通過用比特串取代標簽的ID序列，充分利用碰撞比特信息，提高標簽識別效率，但由于標簽估計數(shù)的不確定性，仍然存在浪費空閑時隙和標簽碰撞問題。文獻[2]提出去空閑時隙ALOHA算法(CIFSA)，在預約思想的基礎上，根據(jù)預約序列，標簽修改自身預定義時隙，屏蔽該幀中的空閑時隙，只有成功和碰撞兩種時隙，縮短每一幀的幀長，提高標簽識別效率，但還是沒有解決多標簽間的碰撞問題，標簽識別效率仍然比較低。

針對動態(tài)RFID系統(tǒng)中標簽防碰撞問題，本文提出一種新型去除空閑和減少碰撞的幀時隙ALOHA防碰撞算法。算法在去空閑時隙算法基礎上，通過碰撞調(diào)整機制增加成功時隙數(shù)。核心思想就是區(qū)分碰撞時隙存在的兩種情況，將碰撞時隙向前移動、空閑時隙向后移動，并標記第一個多標簽選中時隙與第一個空閑時隙，通過碰撞調(diào)整機制將碰撞時隙轉化為成功時隙，將空閑時隙轉化為成功時隙，提高每幀的標簽識別效率。

圖2 標簽移動原理

圖3 算法流程

1 算法原理

1.1 去空閑時隙原理

如圖1所示，去空閑時隙原理具體步驟：首先標簽選擇隨機自己通信時隙i，閱讀器接收到標簽預定義時隙后，對每一個比特位進行比較，被一個或多個標簽選中的比特位記為X；未被標簽選中的比特位記為0，生成預約序列。標簽根據(jù)閱讀器返回的預約序列重新調(diào)整自身的通信時隙，若預約位在預約序列中對應的時隙前有m個0，標簽向前移動m位，并修改自身的i值，得到去空閑后序列。當標簽數(shù)≥時隙數(shù)時，以256為單位進行分組；否則，按上述方法去空閑時隙。

1.2 碰撞區(qū)分原理

改進算法在閱讀器端以4比特為一個檢測單元進行標簽的響應，在當前檢測單元出現(xiàn)碰撞時，開啟一個多比特時隙，區(qū)分開始時，閱讀器發(fā)送“查詢前綴+1”，處于閱讀器識別范圍內(nèi)的標簽收到查詢請求后，利用ID匹配“查詢前綴+1”。如果匹配，就響應閱讀器請求命令，若顯示無碰撞，表明只有一個標簽選中該比特位；否則，表明多個標簽選中該比特位。一個檢測單元區(qū)分完畢之后，繼續(xù)下一個檢測單元。

1.3 空閑移動原理

碰撞區(qū)分后，將所有空閑比特位向后移動，標記第一個多標簽選中的比特位和第一個空閑比特位。多標簽選中的比特位隨機選取一個標簽保留本位，其余標簽移動至后方空閑比特位，依次填充空閑比特位，使空閑比特位轉化為單個標簽選中比特位，空閑比特位標記依次向后移動。

2 算法具體分析

2.1 算法步驟

算法流程如圖3所示。具體步驟如下：步驟一：閱讀器發(fā)出一條Init(L)初始命令。

步驟二：處在識別區(qū)的標簽在L個時隙中隨機選擇一個時隙，將其對應預約位置為1，其余置為0，生成一個長度為L的預約序列，發(fā)送給閱讀器。同時將預約位存儲在自身的計數(shù)器S_C中。

步驟三：閱讀器比較所有響應標簽返回的預約序列，生成碰撞信息：如果同一個比特位被N(N≥1)個標簽選中，記為X；否則，記為0。

步驟四：閱讀器發(fā)送Adjust命令，標簽根據(jù)閱讀器返回的碰撞信息，修改預約數(shù)：

1)將L個比特以4比特為單位劃分檢測單元，在當前檢測單元出現(xiàn)多標簽響應時，閱讀器發(fā)送“查詢前綴+1”，處于閱讀器識別范圍內(nèi)的標簽收到查詢請求時，利用ID匹配“查詢前綴+1”。如果匹配，就響應閱讀器請求命令，若顯示無碰撞，表明只有一個標簽選中該比特位；否則，表明多個標簽選中該比特位。

2)區(qū)分好選中位的標簽數(shù)后，將所有空閑比特位向后移動，標記第一個多標簽選中的比特位為Xcoll，標記第一個空閑比特位為Lidle。多標簽選中的比特位隨機選擇一個標簽保留本位，其余標簽依次從第一個空閑比特位開始填充，Lidle標記依次向后移動，Xcoll標記也依次向后移動，以此類推。

步驟五：標簽根據(jù)閱讀器命令進行調(diào)整，修改計數(shù)器S_C中的值，得到新的比特序列。

步驟六：閱讀器開始識別，在一幀中與所有標簽通信。完成后查看是否有標簽碰撞的時隙，若有，返回步驟一，直至所有標簽識別；否則，識別結束。

2.2 算法分析

假設識別范圍類共有N個標簽，L為幀時隙的大小，根據(jù)二項式分布定理可以推知：

同一幀同一個時隙被M個標簽選中的概率：

該時隙為空閑時隙的概率：

該時隙為成功時隙的概率：

該時隙為碰撞時隙的概率：

由以上公式可知它們的期望分別是：

空閑時隙：

成功時隙：

碰撞時隙：

吞吐率S為：

吞吐率LL為：

吞吐率P為：

3 算法仿真

為驗證NCIRC_FSA算法的有效性，假設在相同的識別長度范圍內(nèi)，標簽均勻分布，待識別標簽數(shù)量介于100~1 500之間。在Windows10的操作環(huán)境下，利用MATLAB 2018b對幀長為256時隙的FSA算法、DFSA算法[3]、GDFSA算法[4]、CIFSA算法[5]以及NCIRC_FSA算法進行仿真，以100次實驗的均值作為仿真結果，對以上五種算法的標簽吞吐率、時隙開銷及標簽丟失率情況進行對比分析。

3.1 吞吐率分析

在MTALAB上對FSA、DFSA、GDFSA、CIFSA和NCIRC_FSA這五種算法進行仿真得到吞吐率曲線為圖4所示。

圖4 吞吐率分析

由圖4可見FSA、DFSA、GDFSA三種算法吞吐率曲線峰值基本重合，其峰值吞吐率為0.36，而FSA吞吐率曲線在到達峰值后呈現(xiàn)出急速下降的趨勢，當標簽數(shù)N=1 500時，DFSA算法吞吐率幾乎為零。DFSA算法雖然采用了動態(tài)幀時隙策略但吞吐率曲線仍避免不了下降的趨勢，而GDFSA算法則在此基礎上采取標簽分組以及先來先服務策略可有效避免這一趨勢并使吞吐率穩(wěn)定在0.36左右；CIFSA算法則在GDFSA算法的基礎上采用預約改進思想去除了空閑時隙的影響，使吞吐率穩(wěn)定在0.75左右；NCIRC_FSA算法采用標簽分組、先來先服務策略以及標簽移位策略和去空閑策略，去除空閑時隙以及碰撞時隙的影響使標簽吞吐率能穩(wěn)定在1.00左右，避免了FSA算法和DFSA算法在標簽數(shù)快速增多的情況下吞吐率急速下降的趨勢，相比GDFSA算法以及CIFSA算法，NCIRC_FSA算法的吞吐率穩(wěn)定性更強。

3.2 時隙總數(shù)分析

如圖5所示，當待識別標簽數(shù)量由100遞增至1 500的過程中，F(xiàn)SA算法和DFAS算法所消耗的時隙總數(shù)隨待識別標簽數(shù)量的遞增呈指數(shù)級增長,而GDFSA算法、CIFSA算法和NCIRC_FSA隨待識別標簽數(shù)量的遞增則呈線性增長，其中NCIRC_FSA算法增長速度最慢，優(yōu)勢明顯。

圖5 時隙總數(shù)分析

3.3 丟失率分析

標簽識別簡化動態(tài)RFID模型如圖6所示。標簽停留時長為T=350(slot)，信號區(qū)內(nèi)標簽數(shù)目初值為100；通過調(diào)整信號區(qū)內(nèi)標簽的數(shù)目改變標簽密度，分析標簽密度變化對移動RFID系統(tǒng)性能(TLR)所產(chǎn)生的影響。

圖6 簡化動態(tài)RFID模型

圖7 標簽丟失率分析

如圖7所示：(1)初始時DFSA與GDFSA丟失率曲線重合，并且兩種算法丟失率均低于FSA算法，原因是DFSA和GDFSA兩種算法采用動態(tài)幀時隙策略降低了其標簽丟失率；當標簽數(shù)目N>354時，F(xiàn)SA、DFSA丟失率曲線重合，而GDFSA丟失率低于這兩者算法，是因為FSA、DFSA算法均以最大幀進行識別，系統(tǒng)識別效率已經(jīng)達到最大，而GDFSA采用標簽分組及先來先服務思想增大了系統(tǒng)識別率減少標簽的丟失。(2)CIFSA算法丟失率小于GDFSA算法，原因是CIFSA在其基礎上采用預約思想去除空閑時隙的影響，大大提高系統(tǒng)識別率，減少標簽丟失。(3)NCIRC_FSA算法的標簽丟失率遠遠小于FSA、DFSA、GDFSA、CIFSA這四種算法，原因是NCIRC_FSA算法將碰撞時隙和空閑時隙通過預約思想和標簽移位思想轉換為成功時隙，消除了空閑時隙和碰撞時隙所產(chǎn)生的影響，降低了標簽丟失率。

4 結語

本文提出一種新型去除空閑和去除碰撞的幀時隙ALOHA防碰撞算法(NCIRC_FSA)，算法首先預估識別區(qū)域內(nèi)標簽數(shù)量，當標簽數(shù)N≤256時采用動態(tài)幀時隙策略。否則，采用標簽分組及先來先服務策略。然后根據(jù)預約思想將時隙重新進行排列，采用標簽移位思想將碰撞位標簽依次移至空閑時隙。最后去除多余的空閑時隙，實現(xiàn)標簽快速識別。通過仿真分析表明隨著待識別標簽數(shù)的增加，與其他算法相比，NCIRC_FSA算法系統(tǒng)的時隙開銷最小，吞吐率最高且穩(wěn)定性最佳，有效地提高了系統(tǒng)的識別效率。