王超梁 趙成 周鵬
摘 要:物聯(lián)網(wǎng)RFID多標(biāo)簽識別防碰撞算法對系統(tǒng)的識別效率和穩(wěn)定性至關(guān)重要。為了解決多標(biāo)簽識別的碰撞問題,對 ALOHA及其改進(jìn)算法進(jìn)行了仿真分析,給出了不同時隙長度時標(biāo)簽數(shù)目與系統(tǒng)吞吐量的關(guān)系,提出了一種自適應(yīng)動態(tài)調(diào)整幀長的防碰撞算法。仿真結(jié)果表明,隨著標(biāo)簽數(shù)量的增加,自適應(yīng)動態(tài)調(diào)整時隙長度的防碰撞算法吞吐率明顯優(yōu)于固定時隙算法和傳統(tǒng)動態(tài)時隙算法。
關(guān)鍵詞:物聯(lián)網(wǎng);RFID;ALOHA;多標(biāo)簽識別;防碰撞
中圖分類號:TP391 文獻(xiàn)標(biāo)識碼:A 文章編號:2095-1302(2018)01-00-02
0 引 言
射頻識別(Radio Frequency Identification,RFID)依靠非接觸式空間電磁感應(yīng)實現(xiàn)電子標(biāo)簽和讀寫器之間的信息交互,完成標(biāo)簽信息的傳遞,被廣泛應(yīng)用于智慧物流、智能交通等領(lǐng)域。 RFID多目標(biāo)識別系統(tǒng)中的碰撞問題分為讀寫器碰撞和標(biāo)簽碰撞兩種,多標(biāo)簽識別防碰撞算法的研究,解決了多個標(biāo)簽同時與一個讀寫器進(jìn)行通信的碰撞問題。在高頻電子標(biāo)簽識別領(lǐng)域,標(biāo)簽的防碰撞一般采用基于TDMA的ALOHA算法及其改進(jìn)算法,ALOHA算法性能會隨著標(biāo)簽數(shù)量的增加急劇惡化,導(dǎo)致信道利用率偏低;而基于確定性的二進(jìn)制樹搜索算法要遍歷所有標(biāo)簽識別的可能性,故搜索效率較低。本文在分析ALOHA及其改進(jìn)算法的基礎(chǔ)上提出了自適應(yīng)動態(tài)時隙的改進(jìn)算法。
1 基于ALOHA算法的標(biāo)簽防碰撞算法
1.1 ALOHA算法
ALOHA算法是一種非常簡單的TDMA算法,最早用于解決網(wǎng)絡(luò)通信中數(shù)據(jù)包的擁堵問題,通常用于簡單的RFID系統(tǒng)中。采用標(biāo)簽先發(fā)言的方式,自動向讀寫器發(fā)送自身的ID信息,完成身份認(rèn)證后,只要有符合條件的數(shù)據(jù)包需要傳輸,讀寫器和標(biāo)簽就開始通信,直至完成數(shù)據(jù)包交互。因此,這種處理機(jī)制本身與應(yīng)答器控制、隨機(jī)的TDMA算法有關(guān),兩個標(biāo)簽可以在不同的時間發(fā)送請求,從而避免數(shù)據(jù)發(fā)生碰撞,如圖1所示。但該算法在數(shù)據(jù)幀發(fā)送的過程中發(fā)生碰撞的概率很大,而且標(biāo)簽沒有載波監(jiān)聽糾錯能力。ALOHA算法平均交換的數(shù)據(jù)包量在G=0.4時達(dá)到最大,仿真結(jié)果如圖2所示。
平均交換的數(shù)據(jù)包含量G可以表示為:
如果RFID系統(tǒng)吞吐率用平均吞吐率S表示,其值等于1時表示無數(shù)據(jù)包發(fā)生碰撞,其值等于0時表示沒有數(shù)據(jù)包傳輸成功,平均吞吐率S為:
可以得到,純ALOHA算法的最佳信道利用率為18.4%,提高信道利用率和數(shù)據(jù)吞吐量可采用,標(biāo)簽只在規(guī)定的同步時隙內(nèi)才傳輸數(shù)據(jù)包。
1.2 時隙ALOHA算法
時隙ALOHA算法在ALOHA算法的基礎(chǔ)上進(jìn)行了改進(jìn),把標(biāo)簽信息傳輸?shù)臅r間劃分為若干個離散的時隙,數(shù)據(jù)包只能在時隙的起始端傳輸,以有效地將單純ALOHA算法的碰撞周期縮減為原來的一半,同時將信道利用率也提高一倍。當(dāng)標(biāo)簽進(jìn)入讀寫器的識別范圍并開始通信時,標(biāo)簽只在規(guī)定的時間間隙內(nèi)發(fā)送數(shù)據(jù);當(dāng)讀寫器不工作或者標(biāo)簽的時隙結(jié)束時,標(biāo)簽發(fā)送請求命令無效,讀寫器響應(yīng)標(biāo)簽請求。相比ALOHA算法,時隙ALOHA算法在很大程度上避開了請求高峰期,碰撞概率為ALOHA算法的一半。由式(3)、(4)可得當(dāng)G=1時,吞吐率Q的最大值可以達(dá)到36.8%,相比ALOHA算法提高了一倍。
1.3 幀時隙ALOHA算法
幀時隙ALOHA算法是指在規(guī)定的時隙內(nèi),標(biāo)簽可以選擇該時隙內(nèi)的任一數(shù)據(jù)信道發(fā)送數(shù)據(jù),如果選擇的信道只有一個標(biāo)簽或占用信道的時間小于時隙長度,讀寫器可成功接收數(shù)據(jù)。反之,讀寫器接收數(shù)據(jù)失敗,而未完成數(shù)據(jù)傳輸?shù)臉?biāo)簽將進(jìn)入下一循環(huán)重新選擇時隙(通道)。這種算法的優(yōu)點是響應(yīng)速度快,容易實施,但效率不高,而且也解決不了響應(yīng)通道未開啟的問題。由于該算法存在讀寫器無響應(yīng)階段的可能,會造成標(biāo)簽在一定時間段內(nèi)無法識別,所以基于時隙隨機(jī)分配的ALOHA算法只適用于低成本的RFID系統(tǒng)。本文對比了幀時隙L分別取16、32、64、128、256時的標(biāo)簽數(shù)目與吞吐率的關(guān)系,固定幀時隙算法標(biāo)簽數(shù)目與吞吐率的關(guān)系如圖3所示。由此可見,當(dāng)標(biāo)簽數(shù)目和時隙數(shù)相等時,系統(tǒng)效率最高。
2 自適應(yīng)動態(tài)時隙ALOHA算法
動態(tài)時隙ALOHA算法解決了固定時隙算法時隙長度不變引起的標(biāo)簽等待問題,采用動態(tài)改變時隙個數(shù)的方式來提高系統(tǒng)的吞吐率。在多標(biāo)簽識別的過程中,標(biāo)簽數(shù)量的增加需要更多的時隙個數(shù)來完成數(shù)據(jù)傳送。隨著標(biāo)簽數(shù)量的增加,系統(tǒng)的識別效率急劇下降。本文提出了一種自適應(yīng)動態(tài)時隙的防碰撞算法,根據(jù)標(biāo)簽的數(shù)量自適應(yīng)調(diào)整時隙長度,使得在標(biāo)簽數(shù)量較多的情況下仍然可以得到較好的吞吐率。首先,讀寫器初定一個固定的幀長發(fā)送命令,標(biāo)簽根據(jù)自身的條件對是否符合要求作出回應(yīng);然后,讀寫器對發(fā)送數(shù)據(jù)的標(biāo)簽進(jìn)行身份驗證分析后,大致估算已識別和未識別的標(biāo)簽數(shù);最后,依據(jù)未識別的標(biāo)簽數(shù)量,調(diào)整相應(yīng)的幀長和通道數(shù)后,開始識別標(biāo)簽。當(dāng)未識別標(biāo)簽數(shù)量太多時,數(shù)據(jù)通道不夠分配,通常使用分組算法將未識別標(biāo)簽分成多個組,然后根據(jù)分組情況自適應(yīng)調(diào)整時隙長度來完成各組標(biāo)簽的識別。本文采用改進(jìn)演化算法進(jìn)行時隙長度自適應(yīng)調(diào)整,根據(jù)識別標(biāo)簽和未識別標(biāo)簽的個數(shù),調(diào)整時隙長度,選取系統(tǒng)吞吐率作為優(yōu)化函數(shù),采用如下公式調(diào)整時隙長度:
其中:fmax為多標(biāo)簽識別系統(tǒng)最大吞吐率,favg為平均吞吐率,f '為每次選擇的兩個標(biāo)簽中具有較大吞吐率的選擇方式, f為不同標(biāo)簽的適應(yīng)度值,pc1為調(diào)整時隙長度演化計算的最大交叉概率,pm1為演化計算最大變異概率。
自適應(yīng)動態(tài)時隙ALOHA算法和動態(tài)時隙ALOAH算法的性能比較如圖4所示??梢钥闯?,當(dāng)標(biāo)簽數(shù)量在0~400之間時,本文改進(jìn)算法與動態(tài)幀時隙算法的吞吐率相當(dāng);當(dāng)標(biāo)簽數(shù)量超過400時,改進(jìn)算法的吞吐率明顯優(yōu)于傳統(tǒng)動態(tài)時隙算法。
本文改進(jìn)算法與固定時隙算法的性能比較如圖5所示??梢钥闯觯?dāng)標(biāo)簽數(shù)目在0~200之間時,改進(jìn)算法的吞吐率優(yōu)于固定時隙算法;當(dāng)標(biāo)簽數(shù)目在200~300之間時,固定時隙算法的吞吐率優(yōu)于本文改進(jìn)算法;當(dāng)標(biāo)簽數(shù)目在300~400之間時,兩者的吞吐率相當(dāng);當(dāng)標(biāo)簽數(shù)目在400~1 000之間時,本文改進(jìn)算法的吞吐率優(yōu)于固定時隙算法。
3 結(jié) 語
本文在對ALOHA算法及其改進(jìn)算法仿真分析的基礎(chǔ)上,給出了固定幀時隙算法時隙長度與吞吐量的關(guān)系,提出了一種自適應(yīng)動態(tài)調(diào)整幀長的防碰撞算法。仿真結(jié)果表明,系統(tǒng)吞吐率最優(yōu)時,所取的時隙數(shù)和標(biāo)簽數(shù)量基本相等;隨著標(biāo)簽數(shù)量的增加,自適應(yīng)動態(tài)調(diào)整時隙長度的防碰撞算法吞吐率明顯優(yōu)于固定時隙算法和傳統(tǒng)動態(tài)時隙算法。
參考文獻(xiàn)
[1]王鑫.面向RFID系統(tǒng)防碰撞算法及安全機(jī)制研究[D].北京:北京郵電大學(xué),2015.
[2]栗紅果. RFID中標(biāo)簽防碰撞算法的研究與改進(jìn)[D].武漢:華中科技大學(xué),2014.
[3]王必勝,張其善.可并行識別的超高頻RFID系統(tǒng)防碰撞性能研究[J].通信學(xué)報,2009,30(6):108-113.
[4]朱云龍,陳瀚寧,申海.生物啟發(fā)計算:個體、群體、群落演化模型與方法[M].北京:清華大學(xué)出版社,2013.
[5]施衛(wèi)東.一種改進(jìn)的RFID標(biāo)簽防碰撞算法[J].科技通報,2015,31(4):121-123.
[6]劉道微.基于自適應(yīng)搜索機(jī)制的RFID標(biāo)簽防碰撞算法[J].金卡工程,2016(11):34-35.
[7]康維新,吳學(xué)文.一種改進(jìn)的RFID標(biāo)簽防碰撞算法[J].哈爾濱商業(yè)大學(xué)學(xué)報(自然科學(xué)版), 2014 (6):677-681.
[8]王佩瑋.無線射頻識別標(biāo)簽防碰撞算法比較分析[J].物聯(lián)網(wǎng)技術(shù), 2017,7(4):21-24.