《電子技術應用》
您所在的位置:首頁 > 通信與網絡 > 設計應用 > 基于連續(xù)時隙探測的防碰撞算法研究
基于連續(xù)時隙探測的防碰撞算法研究
2018年電子技術應用第10期
楊 帆1,任守綱2,郝水俠1,周 俊3,袁培森2
1.江蘇師范大學 數(shù)學與統(tǒng)計學院,江蘇 徐州221116; 2.南京農業(yè)大學 信息科學技術學院,江蘇 南京210095; 3.南京農業(yè)大學 江蘇省智能農業(yè)裝備重點實驗室,江蘇 南京210031
摘要: 為進一步提高標簽的識別速度,針對動態(tài)幀時隙類算法對幀長調整的不靈敏性以及Q算法中Q值調整的高計算復雜度,提出了一種基于連續(xù)時隙探測的RFID防碰撞算法,詳細闡述了該算法的思想和運算流程。該算法通過探測識別幀中連續(xù)時隙的應答狀況,利用設定的規(guī)則調整幀長,使系統(tǒng)工作在最佳狀態(tài)。仿真結果表明,與標準QA算法相比,改進的算法縮短了系統(tǒng)4%的識別時延,提高了系統(tǒng)6%的識別速度。
中圖分類號: TP301.6;TP309
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.180393
中文引用格式: 楊帆,任守綱,郝水俠,等. 基于連續(xù)時隙探測的防碰撞算法研究[J].電子技術應用,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.
An anti-collision algorithm based on continuous slot detection
Yang Fan1,Ren Shougang2,Hao Shuixia1,Zhou Jun3,Yuan Peisen2
1.School of Mathematics and Statistics,Jiangsu Normal University,Xuzhou 221116,China; 2.School of Information Sciences and Technology,Nanjing Agricultural University,Nanjing 210095,China; 3.Jiangsu Key Laboratory for Intelligent Agricultural Equipments,Nanjing Agricultural University,Nanjing 210031,China
Abstract: In order to further increase the speed of tag identification, for solving the insensitivity of the frame adjustment in dynamic frame slot aloha algorithm and the high computing complexity of the Q value adjustment in Q algorithm, a new anti-collision algorithm, called continuous slot detection(CSD), is proposed. The idea of algorithm and the process of operation are introduced. In this algorithm, the optimal efficient is obtained by detecting the status of consecutive slots in frame and setting frame length by rules. The simulation results show that compared with other anti-collision algorithm, the proposed algorithm can decrease identification delay by 4% and increase identification speed by 6%.
Key words : RFID;anti-collision algorithm;Q value;slot detection

0 引言

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

    基于樹類的確定性算法分為二進制樹(Binary Search Tree,BT)類和查詢樹(Query Tree,QT)類算法。在BT類算法中,讀寫器逐時隙生成隨機數(shù)0和1,進而形成新的路徑來識別標簽。在QT類算法中,讀寫器根據(jù)標簽ID的二進制樹狀結構特點,形成唯一響應路徑的策略來識別標簽。學者們根據(jù)樹類算法的特點,提出大量改進的防碰撞算法[2-6],但仍產生大量的空閑和碰撞時隙。基于ALOHA的隨機性算法[7-11]采用時隙隨機分配的工作方式,執(zhí)行過程相對簡單,易于實現(xiàn)。當前該類算法又主要分為動態(tài)幀時隙算法(Dynamic Frame Slot Aloha,DFSA)和Q算法。前者通過將幀長設定為估計標簽數(shù)量的近似值,使系統(tǒng)以最高的效率識別標簽,標簽數(shù)量估算精度和幀長的動態(tài)調整是制約DFSA算法識別效率的主要原因。后者避免了待識別標簽數(shù)量的估計,同時解決了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無法迅速根據(jù)標簽數(shù)量調整幀長。CSD算法結合理論分析和實驗推導,在大規(guī)模標簽群下,通過判斷初始條件下待識別幀起始3個連續(xù)時隙的應答狀況,迅速調整幀長,使系統(tǒng)工作在最優(yōu)狀態(tài)。

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

1.2 CSD算法關鍵參數(shù)的確定

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

    定義1 標簽幀長比α為待識別標簽數(shù)量n與識別幀長F的比值:

    tx1-gs1.gif

    定義2 單位碰撞標簽量βk為連續(xù)碰撞時隙內的每個時隙的標簽量,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ù)學的角度上說是一個多重伯努利實驗問題。理論條件下一個時隙內出現(xiàn)r個標簽可以記為:

    tx1-gs2.gif

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

     tx1-gs3-5.gif

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

tx1-t1.gif

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

    當α>0.75,k≥3時,有:

tx1-gs6-8.gif

    tx1-gs9.gif

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

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

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

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

     tx1-gs10-12.gif

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

tx1-t2.gif

    從圖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時,有:

tx1-gs13-14.gif

    tx1-gs15.gif

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

2 仿真實驗與分析

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

2.1 識別時延

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

tx1-t3.gif

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

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

tx1-t4.gif

2.3 識別速度

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

tx1-t5.gif

3 結論

    本文提出了基于連續(xù)時隙探測的RFID防碰撞算法CSD。該算法利用數(shù)學模型及描點方式得出通過判斷3個連續(xù)時隙的狀況,動態(tài)調整幀長,解決了DFSA類算法對幀長調整的不靈敏性以及Q算法中Q值調整高計算復雜度的缺點。仿真結果顯示,在標簽數(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] 任守綱,楊帆,徐煥良.一種雙權重參數(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.南京農業(yè)大學 信息科學技術學院,江蘇 南京210095;

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

此內容為AET網站原創(chuàng),未經授權禁止轉載。
主站蜘蛛池模板: 黄色片免费网站 | 一级特黄色大片 | 日韩日韩精品无砖专区2020 | 日韩免费视频一区 | 亚洲欧美另类一区 | 521a成v视频网站在线入口 | 在线观看91精品国产不卡免费 | 成人免费视频网址 | 亚洲无卡视频 | 91娱乐 | 成人污视频在线观看 | 狠狠综合 | 亚洲综合无码一区二区 | 成年美女黄网色大观看全 | 亚洲最新地址 | 成人男女网免费 | 成年美女黄网站色大免费观看软件 | 日韩成人黄色片 | 午夜私人影院在线观看 | 国产毛片在线看 | 成人动漫视频在线 | 中国国产高清一级毛片 | 黄色一级欧美 | 视频在线观看网站免费 | 成人福利在线看 | 国产男女 爽爽爽爽视频 | 精品中文字幕一区在线 | 日本一区二区成人教育 | 午夜96影视| 成人网网址 | 免费观看毛片视频 | 91抖音成人 | 中国一级做a爰片久久毛片 中国一级做a爱片免费 | 欧美色图欧美色图 | 欧美在线一区二区 | 国产视频一二 | 5060午夜网| 欧美乱人伦中文字幕在线不卡 | 97视频精品全国在线观看 | 午夜视频在线观看视频 | 免费在线观看成年人视频 |