王超梁 趙成 周鵬

摘 要：物聯(lián)網(wǎng)RFID多標(biāo)簽識(shí)別防碰撞算法對(duì)系統(tǒng)的識(shí)別效率和穩(wěn)定性至關(guān)重要。為了解決多標(biāo)簽識(shí)別的碰撞問(wèn)題，對(duì) ALOHA及其改進(jìn)算法進(jìn)行了仿真分析，給出了不同時(shí)隙長(zhǎng)度時(shí)標(biāo)簽數(shù)目與系統(tǒng)吞吐量的關(guān)系，提出了一種自適應(yīng)動(dòng)態(tài)調(diào)整幀長(zhǎng)的防碰撞算法。仿真結(jié)果表明，隨著標(biāo)簽數(shù)量的增加，自適應(yīng)動(dòng)態(tài)調(diào)整時(shí)隙長(zhǎng)度的防碰撞算法吞吐率明顯優(yōu)于固定時(shí)隙算法和傳統(tǒng)動(dòng)態(tài)時(shí)隙算法。

關(guān)鍵詞：物聯(lián)網(wǎng)；RFID；ALOHA；多標(biāo)簽識(shí)別；防碰撞

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2018）01-00-02

0 引 言

射頻識(shí)別（Radio Frequency Identification，RFID）依靠非接觸式空間電磁感應(yīng)實(shí)現(xiàn)電子標(biāo)簽和讀寫器之間的信息交互，完成標(biāo)簽信息的傳遞，被廣泛應(yīng)用于智慧物流、智能交通等領(lǐng)域。 RFID多目標(biāo)識(shí)別系統(tǒng)中的碰撞問(wèn)題分為讀寫器碰撞和標(biāo)簽碰撞兩種，多標(biāo)簽識(shí)別防碰撞算法的研究，解決了多個(gè)標(biāo)簽同時(shí)與一個(gè)讀寫器進(jìn)行通信的碰撞問(wèn)題。在高頻電子標(biāo)簽識(shí)別領(lǐng)域，標(biāo)簽的防碰撞一般采用基于TDMA的ALOHA算法及其改進(jìn)算法，ALOHA算法性能會(huì)隨著標(biāo)簽數(shù)量的增加急劇惡化，導(dǎo)致信道利用率偏低；而基于確定性的二進(jìn)制樹(shù)搜索算法要遍歷所有標(biāo)簽識(shí)別的可能性，故搜索效率較低。本文在分析ALOHA及其改進(jìn)算法的基礎(chǔ)上提出了自適應(yīng)動(dòng)態(tài)時(shí)隙的改進(jìn)算法。

1 基于ALOHA算法的標(biāo)簽防碰撞算法

1.1 ALOHA算法

ALOHA算法是一種非常簡(jiǎn)單的TDMA算法，最早用于解決網(wǎng)絡(luò)通信中數(shù)據(jù)包的擁堵問(wèn)題，通常用于簡(jiǎn)單的RFID系統(tǒng)中。采用標(biāo)簽先發(fā)言的方式，自動(dòng)向讀寫器發(fā)送自身的ID信息，完成身份認(rèn)證后，只要有符合條件的數(shù)據(jù)包需要傳輸，讀寫器和標(biāo)簽就開(kāi)始通信，直至完成數(shù)據(jù)包交互。因此，這種處理機(jī)制本身與應(yīng)答器控制、隨機(jī)的TDMA算法有關(guān)，兩個(gè)標(biāo)簽可以在不同的時(shí)間發(fā)送請(qǐng)求，從而避免數(shù)據(jù)發(fā)生碰撞，如圖1所示。但該算法在數(shù)據(jù)幀發(fā)送的過(guò)程中發(fā)生碰撞的概率很大，而且標(biāo)簽沒(méi)有載波監(jiān)聽(tīng)糾錯(cuò)能力。ALOHA算法平均交換的數(shù)據(jù)包量在G=0.4時(shí)達(dá)到最大，仿真結(jié)果如圖2所示。

平均交換的數(shù)據(jù)包含量G可以表示為：

如果RFID系統(tǒng)吞吐率用平均吞吐率S表示，其值等于1時(shí)表示無(wú)數(shù)據(jù)包發(fā)生碰撞，其值等于0時(shí)表示沒(méi)有數(shù)據(jù)包傳輸成功，平均吞吐率S為：

可以得到，純ALOHA算法的最佳信道利用率為18.4%，提高信道利用率和數(shù)據(jù)吞吐量可采用，標(biāo)簽只在規(guī)定的同步時(shí)隙內(nèi)才傳輸數(shù)據(jù)包。

1.2 時(shí)隙ALOHA算法

時(shí)隙ALOHA算法在ALOHA算法的基礎(chǔ)上進(jìn)行了改進(jìn)，把標(biāo)簽信息傳輸?shù)臅r(shí)間劃分為若干個(gè)離散的時(shí)隙，數(shù)據(jù)包只能在時(shí)隙的起始端傳輸，以有效地將單純ALOHA算法的碰撞周期縮減為原來(lái)的一半，同時(shí)將信道利用率也提高一倍。當(dāng)標(biāo)簽進(jìn)入讀寫器的識(shí)別范圍并開(kāi)始通信時(shí)，標(biāo)簽只在規(guī)定的時(shí)間間隙內(nèi)發(fā)送數(shù)據(jù)；當(dāng)讀寫器不工作或者標(biāo)簽的時(shí)隙結(jié)束時(shí)，標(biāo)簽發(fā)送請(qǐng)求命令無(wú)效，讀寫器響應(yīng)標(biāo)簽請(qǐng)求。相比ALOHA算法，時(shí)隙ALOHA算法在很大程度上避開(kāi)了請(qǐng)求高峰期，碰撞概率為ALOHA算法的一半。由式（3）、（4）可得當(dāng)G=1時(shí)，吞吐率Q的最大值可以達(dá)到36.8%，相比ALOHA算法提高了一倍。

1.3 幀時(shí)隙ALOHA算法

幀時(shí)隙ALOHA算法是指在規(guī)定的時(shí)隙內(nèi)，標(biāo)簽可以選擇該時(shí)隙內(nèi)的任一數(shù)據(jù)信道發(fā)送數(shù)據(jù)，如果選擇的信道只有一個(gè)標(biāo)簽或占用信道的時(shí)間小于時(shí)隙長(zhǎng)度，讀寫器可成功接收數(shù)據(jù)。反之，讀寫器接收數(shù)據(jù)失敗，而未完成數(shù)據(jù)傳輸?shù)臉?biāo)簽將進(jìn)入下一循環(huán)重新選擇時(shí)隙（通道）。這種算法的優(yōu)點(diǎn)是響應(yīng)速度快，容易實(shí)施，但效率不高，而且也解決不了響應(yīng)通道未開(kāi)啟的問(wèn)題。由于該算法存在讀寫器無(wú)響應(yīng)階段的可能，會(huì)造成標(biāo)簽在一定時(shí)間段內(nèi)無(wú)法識(shí)別，所以基于時(shí)隙隨機(jī)分配的ALOHA算法只適用于低成本的RFID系統(tǒng)。本文對(duì)比了幀時(shí)隙L分別取16、32、64、128、256時(shí)的標(biāo)簽數(shù)目與吞吐率的關(guān)系，固定幀時(shí)隙算法標(biāo)簽數(shù)目與吞吐率的關(guān)系如圖3所示。由此可見(jiàn)，當(dāng)標(biāo)簽數(shù)目和時(shí)隙數(shù)相等時(shí)，系統(tǒng)效率最高。

2 自適應(yīng)動(dòng)態(tài)時(shí)隙ALOHA算法

動(dòng)態(tài)時(shí)隙ALOHA算法解決了固定時(shí)隙算法時(shí)隙長(zhǎng)度不變引起的標(biāo)簽等待問(wèn)題，采用動(dòng)態(tài)改變時(shí)隙個(gè)數(shù)的方式來(lái)提高系統(tǒng)的吞吐率。在多標(biāo)簽識(shí)別的過(guò)程中，標(biāo)簽數(shù)量的增加需要更多的時(shí)隙個(gè)數(shù)來(lái)完成數(shù)據(jù)傳送。隨著標(biāo)簽數(shù)量的增加，系統(tǒng)的識(shí)別效率急劇下降。本文提出了一種自適應(yīng)動(dòng)態(tài)時(shí)隙的防碰撞算法，根據(jù)標(biāo)簽的數(shù)量自適應(yīng)調(diào)整時(shí)隙長(zhǎng)度，使得在標(biāo)簽數(shù)量較多的情況下仍然可以得到較好的吞吐率。首先，讀寫器初定一個(gè)固定的幀長(zhǎng)發(fā)送命令，標(biāo)簽根據(jù)自身的條件對(duì)是否符合要求作出回應(yīng)；然后，讀寫器對(duì)發(fā)送數(shù)據(jù)的標(biāo)簽進(jìn)行身份驗(yàn)證分析后，大致估算已識(shí)別和未識(shí)別的標(biāo)簽數(shù)；最后，依據(jù)未識(shí)別的標(biāo)簽數(shù)量，調(diào)整相應(yīng)的幀長(zhǎng)和通道數(shù)后，開(kāi)始識(shí)別標(biāo)簽。當(dāng)未識(shí)別標(biāo)簽數(shù)量太多時(shí)，數(shù)據(jù)通道不夠分配，通常使用分組算法將未識(shí)別標(biāo)簽分成多個(gè)組，然后根據(jù)分組情況自適應(yīng)調(diào)整時(shí)隙長(zhǎng)度來(lái)完成各組標(biāo)簽的識(shí)別。本文采用改進(jìn)演化算法進(jìn)行時(shí)隙長(zhǎng)度自適應(yīng)調(diào)整，根據(jù)識(shí)別標(biāo)簽和未識(shí)別標(biāo)簽的個(gè)數(shù)，調(diào)整時(shí)隙長(zhǎng)度，選取系統(tǒng)吞吐率作為優(yōu)化函數(shù)，采用如下公式調(diào)整時(shí)隙長(zhǎng)度：

其中：fmax為多標(biāo)簽識(shí)別系統(tǒng)最大吞吐率，favg為平均吞吐率，f '為每次選擇的兩個(gè)標(biāo)簽中具有較大吞吐率的選擇方式， f為不同標(biāo)簽的適應(yīng)度值，pc1為調(diào)整時(shí)隙長(zhǎng)度演化計(jì)算的最大交叉概率，pm1為演化計(jì)算最大變異概率。

自適應(yīng)動(dòng)態(tài)時(shí)隙ALOHA算法和動(dòng)態(tài)時(shí)隙ALOAH算法的性能比較如圖4所示。可以看出，當(dāng)標(biāo)簽數(shù)量在0～400之間時(shí)，本文改進(jìn)算法與動(dòng)態(tài)幀時(shí)隙算法的吞吐率相當(dāng)；當(dāng)標(biāo)簽數(shù)量超過(guò)400時(shí)，改進(jìn)算法的吞吐率明顯優(yōu)于傳統(tǒng)動(dòng)態(tài)時(shí)隙算法。

本文改進(jìn)算法與固定時(shí)隙算法的性能比較如圖5所示?？梢钥闯?，當(dāng)標(biāo)簽數(shù)目在0～200之間時(shí)，改進(jìn)算法的吞吐率優(yōu)于固定時(shí)隙算法；當(dāng)標(biāo)簽數(shù)目在200～300之間時(shí)，固定時(shí)隙算法的吞吐率優(yōu)于本文改進(jìn)算法；當(dāng)標(biāo)簽數(shù)目在300～400之間時(shí)，兩者的吞吐率相當(dāng)；當(dāng)標(biāo)簽數(shù)目在400～1 000之間時(shí)，本文改進(jìn)算法的吞吐率優(yōu)于固定時(shí)隙算法。

3 結(jié) 語(yǔ)

本文在對(duì)ALOHA算法及其改進(jìn)算法仿真分析的基礎(chǔ)上，給出了固定幀時(shí)隙算法時(shí)隙長(zhǎng)度與吞吐量的關(guān)系，提出了一種自適應(yīng)動(dòng)態(tài)調(diào)整幀長(zhǎng)的防碰撞算法。仿真結(jié)果表明，系統(tǒng)吞吐率最優(yōu)時(shí)，所取的時(shí)隙數(shù)和標(biāo)簽數(shù)量基本相等；隨著標(biāo)簽數(shù)量的增加，自適應(yīng)動(dòng)態(tài)調(diào)整時(shí)隙長(zhǎng)度的防碰撞算法吞吐率明顯優(yōu)于固定時(shí)隙算法和傳統(tǒng)動(dòng)態(tài)時(shí)隙算法。

參考文獻(xiàn)

[1]王鑫.面向RFID系統(tǒng)防碰撞算法及安全機(jī)制研究[D].北京：北京郵電大學(xué)，2015.

[2]栗紅果. RFID中標(biāo)簽防碰撞算法的研究與改進(jìn)[D].武漢：華中科技大學(xué)，2014.

[3]王必勝，張其善.可并行識(shí)別的超高頻RFID系統(tǒng)防碰撞性能研究[J].通信學(xué)報(bào)，2009，30（6）：108-113.

[4]朱云龍，陳瀚寧，申海.生物啟發(fā)計(jì)算：個(gè)體、群體、群落演化模型與方法[M].北京：清華大學(xué)出版社，2013.

[5]施衛(wèi)東.一種改進(jìn)的RFID標(biāo)簽防碰撞算法[J].科技通報(bào)，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é)報(bào)（自然科學(xué)版）， 2014 （6）：677-681.

[8]王佩瑋.無(wú)線射頻識(shí)別標(biāo)簽防碰撞算法比較分析[J].物聯(lián)網(wǎng)技術(shù)， 2017，7（4）：21-24.