0 引言

    無線射頻識別(Radio Frequency Identification,，RFID)是一種利用射頻識別方式進行無線非接觸雙向通信的自動識別技術,。隨著物聯(lián)網技術的日益成熟，RFID技術得到了快速的發(fā)展,，但其存在的問題也越來越凸顯出來,。目前RFID技術的主要問題包括：標準不統(tǒng)一問題、數據安全問題,、電磁干擾問題,、標簽碰撞問題等，其中標簽碰撞問題嚴重制約著RFID的發(fā)展,，如何有效解決標簽碰撞問題是RFID技術研究的重點和難點,。目前解決標簽碰撞問題的防碰撞算法主要分為兩類^[1]：基于樹類的確定性算法和基于ALOHA類的隨機性防碰撞算法。

    基于樹類的確定性算法分為二進制樹(Binary Search Tree,，BT)類和查詢樹(Query Tree,，QT)類算法。在BT類算法中,，讀寫器逐時隙生成隨機數0和1,，進而形成新的路徑來識別標簽,。在QT類算法中，讀寫器根據標簽ID的二進制樹狀結構特點,，形成唯一響應路徑的策略來識別標簽,。學者們根據樹類算法的特點，提出大量改進的防碰撞算法^[2-6],，但仍產生大量的空閑和碰撞時隙,。基于ALOHA的隨機性算法^[7-11]采用時隙隨機分配的工作方式,，執(zhí)行過程相對簡單,，易于實現(xiàn)。當前該類算法又主要分為動態(tài)幀時隙算法(Dynamic Frame Slot Aloha,，DFSA）和Q算法,。前者通過將幀長設定為估計標簽數量的近似值，使系統(tǒng)以最高的效率識別標簽,，標簽數量估算精度和幀長的動態(tài)調整是制約DFSA算法識別效率的主要原因,。后者避免了待識別標簽數量的估計，同時解決了DFSA算法在識別幀中不能動態(tài)調整幀長的問題,，但其使用單一的調整因子不能單獨考慮空閑時隙和碰撞時隙,。

    本文針對DFSA類算法對幀長調整的不靈敏性以及Q算法中Q值調整的高計算復雜度，提出了基于連續(xù)時隙探測的RFID防碰撞算法(Continuous Slot Detection,，CSD),。CSD算法引入了時隙探測的概念，通過判斷識別幀中連續(xù)時隙的應答情況,，動態(tài)調整幀長,。仿真結果顯示，與其他防碰撞算法相比,，CSD算法具有較低的識別時延和較快的識別速度,，并且在較多標簽存在的環(huán)境下有明顯優(yōu)勢。

1 連續(xù)時隙探測的防碰撞算法

1.1 CSD算法思想

    針對DFSA類算法對幀長調整的不靈敏性以及Q算法中Q值調整的高計算復雜度,，本文提出的CSD算法主要有以下兩個方面的改進：

    (1)緩解標簽識別初始階段的標簽與幀長不匹配問題,。對于DFSA算法，無論當前時隙是空閑還是碰撞,，讀寫器都要查閱完整個時隙才能調整幀長,，因此在標簽與幀長不匹配的初始階段，DFSA無法迅速根據標簽數量調整幀長,。CSD算法結合理論分析和實驗推導,，在大規(guī)模標簽群下，通過判斷初始條件下待識別幀起始3個連續(xù)時隙的應答狀況,，迅速調整幀長,，使系統(tǒng)工作在最優(yōu)狀態(tài)。

    (2)降低浮點數運算的計算復雜度,。計算機中所有的數據均以二進制形式表示,，浮點數也不例外。當在大規(guī)模標簽群時,，讀寫器多次對浮點參數進行近似計算,，不僅造成誤差累加，而且降低系統(tǒng)的識別效率,。CSD算法利用判斷幀中連續(xù)3個時隙的狀態(tài)替代浮點參數c調整幀長,，降低了運算量，加快了識別速度,。

1.2 CSD算法關鍵參數的確定

    為了詳細描述CSD算法,，現(xiàn)定義以下概念：

    定義1 標簽幀長比α為待識別標簽數量n與識別幀長F的比值：

    定義2 單位碰撞標簽量β_k為連續(xù)碰撞時隙內的每個時隙的標簽量，k為連續(xù)狀態(tài)相同的時隙個數,。

    定義3 η_k表示連續(xù)k個空閑時隙發(fā)生的概率,。

    定義4 γ_k表示連續(xù)k個碰撞時隙發(fā)生的概率。

    定義5 連續(xù)碰撞時隙計數器(Continuous Collision Slot Count,，CCSC)用于統(tǒng)計連續(xù)碰撞時隙的數量,；連續(xù)空閑時隙計數器(Continuous Idle Slot Count，CISC)用于統(tǒng)計連續(xù)空閑時隙的數量,。

1.2.1 連續(xù)空閑時隙數量的確定

    標簽的碰撞問題從數學的角度上說是一個多重伯努利實驗問題,。理論條件下一個時隙內出現(xiàn)r個標簽可以記為：

    因此，對于幀長中k個連續(xù)時隙全部為空閑的概率為：

    采用Python 2.7對式(5)進行描點,，得到了在不同k值下標簽幀長比α與連續(xù)個空閑時隙發(fā)生的概率η_k之間的關系,，如圖1所示。

    從圖1中可以看出,，α與η_k成反比關系,，α值越大，η_k值越小,，這是因為當標簽的數量大于幀長時,，每一個時隙內平均存在的標簽數量不少于1個，因此出現(xiàn)連續(xù)空閑時隙的概率是不斷減小的,；同時,，在相同α值下，k與η_k也成反比關系,。

    當α>0.75,，k≥3時，有：

    即當α≤0.75時,，結合式(6),、式(8)和式(9),，k=η_min(i)，i≥3,，即k=3,。因此，可認定當幀中出現(xiàn)連續(xù)3個空閑時隙時,，此時的幀長與待識別標簽數量不匹配,，需要重新調整幀長識別。

    文獻[9]中已證明,，當待識別的幀長F與標簽數量n近似相等時,，系統(tǒng)會得到最大的識別效率。結合式(8)和式(9),，以F/2的標簽估計誤差小于F時的誤差,，即標簽的數量近似于F/2，則調整當前幀長為F/2,，得到最佳的系統(tǒng)效率,。

1.2.2 連續(xù)碰撞時隙數量的確定

    根據式(2)，對于幀長中出現(xiàn)連續(xù)k個碰撞時隙的概率γ_k可計算為：

    為了便于描述β的取值范圍,，同時考慮到β₁,，β₂，…,，β_k的值遠小于待識別標簽的數量,，現(xiàn)令β₁，β₂,，…,，β_k∈[2，t],，t<<n,，對式(12)進行描點，得到了在不同k值下α與γ_k成反比關系,，如圖2所示,。

    從圖2(a)中可以看出，當k=2,，α→2時,，無論t取何值，γ₂的值都近似為1,，即標簽的數量為幀長兩倍的條件下,，識別幀中一定出現(xiàn)兩個連續(xù)碰撞時隙；從圖2(c)中可以看出，當k=4時,，在無論t取何值,，γ的值都很小趨近于0，這是因為當有α值較小時,，發(fā)生連續(xù)碰撞的概率本來就是小概率事件,，而當α值較大時，其值又受限于β的取值,。

    對于k=3，當α>1.5,，t≥10時,，有：

    當幀中出現(xiàn)連續(xù)3個碰撞時隙時，以2·F的標簽估計誤差小于F時的誤差,，即標簽的數量接近2·F,，則調整當前幀長為2·F，得到最佳的系統(tǒng)效率,。

2 仿真實驗與分析

    本節(jié)利用計算機仿真的實驗結果驗證本文提出的算法,。標簽數目分別為100，200,，…,，1000。每設置1次標簽數目,，實驗重復100次取平均值,。本文主要從識別時延、最優(yōu)幀平均查詢次數和識別速度3個方面分析CSD算法,。

2.1 識別時延

    在常規(guī)標簽群下(標簽數量從100～1 000遞增變化),，將CSD算法與傳統(tǒng)的DFSA算法和Q算法的識別時延進行比較，對比結果如圖3所示,。因為CSD算法通過對連續(xù)時隙的探測,，利用幀長調整規(guī)則，迅速調整到最優(yōu)幀長,。在標簽數量為1 000時,，CSD算法的總時隙數為2 911個，比LB,、Schoute,、Vgot和QA分別降低了12%、10%,、9%和4%,。

2.2 最優(yōu)幀平均查詢次數

    在常規(guī)標簽群下(標簽數量從100～1 000遞增變化)，將CSD算法與傳統(tǒng)的DFSA算法和Q算法的最優(yōu)幀平均查詢次數進行對比，最優(yōu)幀平均查詢次數定義為系統(tǒng)從初始幀長調整到最優(yōu)幀長下讀寫器重發(fā)布幀長調整命令的次數,，對比結果如圖4所示,。可以看出,，CSD算法要優(yōu)于其他算法,。在標簽量為1 000時，CSD算法比QA算法和Vgot算法分別減少了6%和22%的查詢次數,。

2.3 識別速度

    在常規(guī)標簽群下(標簽數量從100～1 000遞增變化),，將CSD算法與傳統(tǒng)的DFSA算法和Q算法的識別速度進行對比，對比結果如圖5所示,。LB算法和Schoute算法的讀取速度分別約為250和260,，QA算法的讀取速度約為290，而CSD算法的讀取速度最快,，約為310,，比LB算法、Schoute算法,、QA算法分別提高了24%,、19%、6%,。

3 結論

    本文提出了基于連續(xù)時隙探測的RFID防碰撞算法CSD,。該算法利用數學模型及描點方式得出通過判斷3個連續(xù)時隙的狀況，動態(tài)調整幀長,，解決了DFSA類算法對幀長調整的不靈敏性以及Q算法中Q值調整高計算復雜度的缺點,。仿真結果顯示，在標簽數量為1 000的條件下,，CSD算法比QA算法減少了4%的識別時延,、降低了6%的查詢次數以及提升了6%的標簽識別速度。

    本文通過數學模型推導出了識別幀中出現(xiàn)不同數量連續(xù)時隙的概率,，對于求值都采用數據描點的方式,，因此下一步的工作是優(yōu)化數學模型的求值方法，進而能夠通過理論方式求出其解,。

參考文獻

[1] FINKENZELLER K.RFID Handbook：Radio-frequency identification fundamentals and applications(Second Edition)[M].England：John Wiley and Sons,，2003.

[2] JIA X，F(xiàn)ENG Q,，YU L.Stability analysis of an efficient anti-collision protocol for RFID tag identification[J].IEEE Transactions on Communications,，2012，60(8)：2285-2294.

[3] SHIN J,，JEON B,，YANG D.Multiple RFID tags identification with M-ary query tree scheme[J].IEEE Communications Letters,，2013，17(3)：604-607.

[4] 吳躍前,，辜大光,，范振粵，等.RFID系統(tǒng)防碰撞算法比較分析及其改進算法[J].計算機工程與應用,，2009(3)：210-213.

[5] 黃瓊,，凌江濤，張敏,，等.LRST：低冗余搜索樹防碰撞算法[J].通信學報,，2014，35(6)：110-116.

[6] LAI Y C,，HSIAO L Y,，CHEN H J，et al.A novel query tree protocol with bit tracking in RFID tag identification[J].IEEE Transactions on Mobile Computing,，2013,，12(10)：2063-2075.

[7] 任守綱,，楊帆,，徐煥良.一種雙權重參數的RFID防碰撞Q值算法研究[J].計算機科學，2014,，41(4)：256-259.

[8] 吳海鋒,，曾玉.RFID動態(tài)幀時隙ALOHA防沖突中的標簽估計和幀長確定[J].自動化學報，2010,，36(4)：620-624.

[9] 任守綱,，楊帆，王浩云,，等.基于判決門限的RFID防碰撞Q值算法[J].計算機科學,，2014，41(8)：154-157.

[10] 張小紅,，張留洋.RFID防碰撞時隙應變協(xié)處理算法研究[J].電子學報,，2014，42(6)：1139-1146.

[11] 楊帆,，徐煥良,，謝俊，等.基于雙空閑因子的RFID防碰撞算法研究[J].計算機工程與科學,，2016,，38(7)：1440-1446.

作者信息:

楊  帆1，任守綱2,，郝水俠1,，周  俊3，袁培森2

(1.江蘇師范大學 數學與統(tǒng)計學院，江蘇 徐州221116,；

2.南京農業(yè)大學 信息科學技術學院,，江蘇 南京210095；

3.南京農業(yè)大學 江蘇省智能農業(yè)裝備重點實驗室,，江蘇 南京210031)