文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.180393
中文引用格式: 楊帆,任守綱,,郝水俠,等. 基于連續(xù)時隙探測的防碰撞算法研究[J].電子技術(shù)應用,,2018,,44(10):109-113.
英文引用格式: Yang Fan,Ren Shougang,,Hao Shuixia,,et al. An anti-collision algorithm based on continuous slot detection[J]. Application of Electronic Technique,2018,,44(10):109-113.
0 引言
無線射頻識別(Radio Frequency Identification,,RFID)是一種利用射頻識別方式進行無線非接觸雙向通信的自動識別技術(shù),。隨著物聯(lián)網(wǎng)技術(shù)的日益成熟,RFID技術(shù)得到了快速的發(fā)展,,但其存在的問題也越來越凸顯出來,。目前RFID技術(shù)的主要問題包括:標準不統(tǒng)一問題、數(shù)據(jù)安全問題,、電磁干擾問題,、標簽碰撞問題等,其中標簽碰撞問題嚴重制約著RFID的發(fā)展,,如何有效解決標簽碰撞問題是RFID技術(shù)研究的重點和難點,。目前解決標簽碰撞問題的防碰撞算法主要分為兩類[1]:基于樹類的確定性算法和基于ALOHA類的隨機性防碰撞算法。
基于樹類的確定性算法分為二進制樹(Binary Search Tree,,BT)類和查詢樹(Query Tree,,QT)類算法。在BT類算法中,,讀寫器逐時隙生成隨機數(shù)0和1,,進而形成新的路徑來識別標簽。在QT類算法中,,讀寫器根據(jù)標簽ID的二進制樹狀結(jié)構(gòu)特點,,形成唯一響應路徑的策略來識別標簽。學者們根據(jù)樹類算法的特點,,提出大量改進的防碰撞算法[2-6],,但仍產(chǎn)生大量的空閑和碰撞時隙?;贏LOHA的隨機性算法[7-11]采用時隙隨機分配的工作方式,,執(zhí)行過程相對簡單,易于實現(xiàn),。當前該類算法又主要分為動態(tài)幀時隙算法(Dynamic Frame Slot Aloha,,DFSA)和Q算法。前者通過將幀長設(shè)定為估計標簽數(shù)量的近似值,,使系統(tǒng)以最高的效率識別標簽,,標簽數(shù)量估算精度和幀長的動態(tài)調(diào)整是制約DFSA算法識別效率的主要原因,。后者避免了待識別標簽數(shù)量的估計,同時解決了DFSA算法在識別幀中不能動態(tài)調(diào)整幀長的問題,,但其使用單一的調(diào)整因子不能單獨考慮空閑時隙和碰撞時隙,。
本文針對DFSA類算法對幀長調(diào)整的不靈敏性以及Q算法中Q值調(diào)整的高計算復雜度,提出了基于連續(xù)時隙探測的RFID防碰撞算法(Continuous Slot Detection,,CSD),。CSD算法引入了時隙探測的概念,通過判斷識別幀中連續(xù)時隙的應答情況,,動態(tài)調(diào)整幀長,。仿真結(jié)果顯示,與其他防碰撞算法相比,,CSD算法具有較低的識別時延和較快的識別速度,,并且在較多標簽存在的環(huán)境下有明顯優(yōu)勢。
1 連續(xù)時隙探測的防碰撞算法
1.1 CSD算法思想
針對DFSA類算法對幀長調(diào)整的不靈敏性以及Q算法中Q值調(diào)整的高計算復雜度,,本文提出的CSD算法主要有以下兩個方面的改進:
(1)緩解標簽識別初始階段的標簽與幀長不匹配問題,。對于DFSA算法,無論當前時隙是空閑還是碰撞,,讀寫器都要查閱完整個時隙才能調(diào)整幀長,,因此在標簽與幀長不匹配的初始階段,DFSA無法迅速根據(jù)標簽數(shù)量調(diào)整幀長,。CSD算法結(jié)合理論分析和實驗推導,,在大規(guī)模標簽群下,通過判斷初始條件下待識別幀起始3個連續(xù)時隙的應答狀況,,迅速調(diào)整幀長,,使系統(tǒng)工作在最優(yōu)狀態(tài)。
(2)降低浮點數(shù)運算的計算復雜度,。計算機中所有的數(shù)據(jù)均以二進制形式表示,浮點數(shù)也不例外,。當在大規(guī)模標簽群時,,讀寫器多次對浮點參數(shù)進行近似計算,不僅造成誤差累加,,而且降低系統(tǒng)的識別效率,。CSD算法利用判斷幀中連續(xù)3個時隙的狀態(tài)替代浮點參數(shù)c調(diào)整幀長,降低了運算量,,加快了識別速度,。
1.2 CSD算法關(guān)鍵參數(shù)的確定
為了詳細描述CSD算法,現(xiàn)定義以下概念:
定義1 標簽幀長比α為待識別標簽數(shù)量n與識別幀長F的比值:
定義2 單位碰撞標簽量βk為連續(xù)碰撞時隙內(nèi)的每個時隙的標簽量,,k為連續(xù)狀態(tài)相同的時隙個數(shù),。
定義3 ηk表示連續(xù)k個空閑時隙發(fā)生的概率,。
定義4 γk表示連續(xù)k個碰撞時隙發(fā)生的概率。
定義5 連續(xù)碰撞時隙計數(shù)器(Continuous Collision Slot Count,,CCSC)用于統(tǒng)計連續(xù)碰撞時隙的數(shù)量,;連續(xù)空閑時隙計數(shù)器(Continuous Idle Slot Count,CISC)用于統(tǒng)計連續(xù)空閑時隙的數(shù)量,。
1.2.1 連續(xù)空閑時隙數(shù)量的確定
標簽的碰撞問題從數(shù)學的角度上說是一個多重伯努利實驗問題,。理論條件下一個時隙內(nèi)出現(xiàn)r個標簽可以記為:
因此,對于幀長中k個連續(xù)時隙全部為空閑的概率為:
采用Python 2.7對式(5)進行描點,,得到了在不同k值下標簽幀長比α與連續(xù)個空閑時隙發(fā)生的概率ηk之間的關(guān)系,,如圖1所示。
從圖1中可以看出,,α與ηk成反比關(guān)系,,α值越大,ηk值越小,,這是因為當標簽的數(shù)量大于幀長時,,每一個時隙內(nèi)平均存在的標簽數(shù)量不少于1個,因此出現(xiàn)連續(xù)空閑時隙的概率是不斷減小的,;同時,,在相同α值下,k與ηk也成反比關(guān)系,。
當α>0.75,,k≥3時,有:
即當α≤0.75時,,結(jié)合式(6),、式(8)和式(9),k=ηmin(i),,i≥3,,即k=3。因此,,可認定當幀中出現(xiàn)連續(xù)3個空閑時隙時,,此時的幀長與待識別標簽數(shù)量不匹配,需要重新調(diào)整幀長識別,。
文獻[9]中已證明,,當待識別的幀長F與標簽數(shù)量n近似相等時,系統(tǒng)會得到最大的識別效率,。結(jié)合式(8)和式(9),,以F/2的標簽估計誤差小于F時的誤差,即標簽的數(shù)量近似于F/2,,則調(diào)整當前幀長為F/2,,得到最佳的系統(tǒng)效率,。
1.2.2 連續(xù)碰撞時隙數(shù)量的確定
根據(jù)式(2),對于幀長中出現(xiàn)連續(xù)k個碰撞時隙的概率γk可計算為:
為了便于描述β的取值范圍,,同時考慮到β1,,β2,…,,βk的值遠小于待識別標簽的數(shù)量,,現(xiàn)令β1,β2,,…,,βk∈[2,t],,t<<n,,對式(12)進行描點,得到了在不同k值下α與γk成反比關(guān)系,,如圖2所示,。
從圖2(a)中可以看出,當k=2,,α→2時,,無論t取何值,γ2的值都近似為1,,即標簽的數(shù)量為幀長兩倍的條件下,,識別幀中一定出現(xiàn)兩個連續(xù)碰撞時隙;從圖2(c)中可以看出,,當k=4時,,在無論t取何值,γ的值都很小趨近于0,,這是因為當有α值較小時,,發(fā)生連續(xù)碰撞的概率本來就是小概率事件,而當α值較大時,,其值又受限于β的取值,。
對于k=3,當α>1.5,,t≥10時,有:
當幀中出現(xiàn)連續(xù)3個碰撞時隙時,,以2·F的標簽估計誤差小于F時的誤差,,即標簽的數(shù)量接近2·F,則調(diào)整當前幀長為2·F,,得到最佳的系統(tǒng)效率,。
2 仿真實驗與分析
本節(jié)利用計算機仿真的實驗結(jié)果驗證本文提出的算法,。標簽數(shù)目分別為100,200,,…,,1000。每設(shè)置1次標簽數(shù)目,,實驗重復100次取平均值,。本文主要從識別時延、最優(yōu)幀平均查詢次數(shù)和識別速度3個方面分析CSD算法,。
2.1 識別時延
在常規(guī)標簽群下(標簽數(shù)量從100~1 000遞增變化),,將CSD算法與傳統(tǒng)的DFSA算法和Q算法的識別時延進行比較,對比結(jié)果如圖3所示,。因為CSD算法通過對連續(xù)時隙的探測,,利用幀長調(diào)整規(guī)則,迅速調(diào)整到最優(yōu)幀長,。在標簽數(shù)量為1 000時,,CSD算法的總時隙數(shù)為2 911個,比LB,、Schoute,、Vgot和QA分別降低了12%、10%,、9%和4%,。
2.2 最優(yōu)幀平均查詢次數(shù)
在常規(guī)標簽群下(標簽數(shù)量從100~1 000遞增變化),將CSD算法與傳統(tǒng)的DFSA算法和Q算法的最優(yōu)幀平均查詢次數(shù)進行對比,,最優(yōu)幀平均查詢次數(shù)定義為系統(tǒng)從初始幀長調(diào)整到最優(yōu)幀長下讀寫器重發(fā)布幀長調(diào)整命令的次數(shù),,對比結(jié)果如圖4所示??梢钥闯?,CSD算法要優(yōu)于其他算法。在標簽量為1 000時,,CSD算法比QA算法和Vgot算法分別減少了6%和22%的查詢次數(shù),。
2.3 識別速度
在常規(guī)標簽群下(標簽數(shù)量從100~1 000遞增變化),將CSD算法與傳統(tǒng)的DFSA算法和Q算法的識別速度進行對比,,對比結(jié)果如圖5所示,。LB算法和Schoute算法的讀取速度分別約為250和260,QA算法的讀取速度約為290,,而CSD算法的讀取速度最快,,約為310,比LB算法,、Schoute算法,、QA算法分別提高了24%,、19%、6%,。
3 結(jié)論
本文提出了基于連續(xù)時隙探測的RFID防碰撞算法CSD,。該算法利用數(shù)學模型及描點方式得出通過判斷3個連續(xù)時隙的狀況,動態(tài)調(diào)整幀長,,解決了DFSA類算法對幀長調(diào)整的不靈敏性以及Q算法中Q值調(diào)整高計算復雜度的缺點,。仿真結(jié)果顯示,在標簽數(shù)量為1 000的條件下,,CSD算法比QA算法減少了4%的識別時延,、降低了6%的查詢次數(shù)以及提升了6%的標簽識別速度。
本文通過數(shù)學模型推導出了識別幀中出現(xiàn)不同數(shù)量連續(xù)時隙的概率,,對于求值都采用數(shù)據(jù)描點的方式,,因此下一步的工作是優(yōu)化數(shù)學模型的求值方法,進而能夠通過理論方式求出其解,。
參考文獻
[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] 任守綱,楊帆,,徐煥良.一種雙權(quán)重參數(shù)的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.江蘇師范大學 數(shù)學與統(tǒng)計學院,,江蘇 徐州221116,;
2.南京農(nóng)業(yè)大學 信息科學技術(shù)學院,江蘇 南京210095,;
3.南京農(nóng)業(yè)大學 江蘇省智能農(nóng)業(yè)裝備重點實驗室,,江蘇 南京210031)