一種新型的RFID的防碰撞算法

于洪濤，王祖良，王少飛，曹闖樂(lè)，馬可欣

（西京學(xué)院，陜西 西安 710123）

0 引 言

在現(xiàn)代科技不斷快速發(fā)展下，自動(dòng)識(shí)別系統(tǒng)越來(lái)越受到人們的青睞。射頻識(shí)別（Radio Frequency Identification,RFID）是一種近距離無(wú)線電通信技術(shù)，具有成本低廉、傳輸速度快且可以對(duì)多個(gè)目標(biāo)進(jìn)行響應(yīng)識(shí)別的特點(diǎn)，其作為一種自動(dòng)識(shí)別技術(shù)已被廣泛應(yīng)用在商品識(shí)別和數(shù)據(jù)采集等各個(gè)領(lǐng)域[1]。因此，對(duì)RFID的防碰撞算法的研究對(duì)提高系統(tǒng)的信道利用率具有重要意義。RFID系統(tǒng)由閱讀器、射頻標(biāo)簽和天線組成。其原理是：閱讀器首先通過(guò)自身攜帶或外置的天線源源不斷地發(fā)送無(wú)線電信號(hào)，當(dāng)標(biāo)簽放進(jìn)屬于天線的作業(yè)范圍之內(nèi)時(shí)，它通過(guò)電感耦合和電磁反向散射耦合產(chǎn)生能量，使標(biāo)簽獲得能量傳遞本身數(shù)據(jù)信息，閱讀器攜帶的數(shù)據(jù)編碼等信息通過(guò)內(nèi)置天線發(fā)送出去[2]，接收天線接收標(biāo)簽發(fā)送的載波信號(hào)對(duì)其進(jìn)行解調(diào)和解碼，然后將其發(fā)送回計(jì)算機(jī)系統(tǒng)進(jìn)行相關(guān)處理[3]。標(biāo)簽可以說(shuō)是RFID系統(tǒng)中的重要組成部分之一，原因是它內(nèi)部存儲(chǔ)著自身的數(shù)據(jù)信息，但是，在數(shù)據(jù)識(shí)別和傳輸?shù)倪^(guò)程中，它受到很多方面的干擾，導(dǎo)致數(shù)據(jù)識(shí)別和傳輸?shù)馁|(zhì)量和效率較低。一般來(lái)說(shuō)，造成這種現(xiàn)象的主要原因是，各種閱讀器和標(biāo)簽中存在的外部干擾因素是同時(shí)存在的，因此很容易在數(shù)據(jù)信息傳輸通道中發(fā)生沖突，導(dǎo)致質(zhì)量和效率低下。為了解決這個(gè)問(wèn)題，本文提出了防沖突算法。

根據(jù)標(biāo)簽的響應(yīng)方式，防沖突算法通常分為不確定性算法和確定性算法兩種。

在不確定性算法中主要為ALOHA算法。ALOHA算法的機(jī)制是標(biāo)簽源源不斷地發(fā)送自身數(shù)據(jù)信息給閱讀器，當(dāng)發(fā)生沖突時(shí)，閱讀器會(huì)下達(dá)命令阻止標(biāo)簽發(fā)送信號(hào)，此時(shí)，標(biāo)簽進(jìn)入一個(gè)“待命”時(shí)間段，這個(gè)時(shí)間段也是隨機(jī)的，“待命”時(shí)間結(jié)束，標(biāo)簽繼續(xù)發(fā)送信號(hào)給閱讀器。

確定性算法有二進(jìn)制樹(shù)算法，其機(jī)制是閱讀器首先設(shè)置限制條件，只有滿足條件的標(biāo)簽才可以發(fā)送信號(hào)并被閱讀器識(shí)別。譬如有00和01兩個(gè)標(biāo)簽，閱讀器首先發(fā)送“0”比特串，然后將比特串“1”放進(jìn)堆棧中，因?yàn)閮蓚€(gè)標(biāo)簽的首位都是0，所以同時(shí)響應(yīng)閱讀器從而產(chǎn)生碰撞。閱讀器繼續(xù)發(fā)送“00”比特串，并將“01”壓入棧中，此時(shí)標(biāo)簽ID為“00”響應(yīng)閱讀器的請(qǐng)求，標(biāo)簽識(shí)別成功，接下來(lái)堆棧中的“01”標(biāo)簽被彈出，其作為請(qǐng)求比特串從而被成功識(shí)別。

1 ALOHA算法

1.1 純ALOHA算法

當(dāng)電子標(biāo)簽被放置到閱讀器作業(yè)范圍之中時(shí)，會(huì)將自身攜帶的數(shù)據(jù)信息發(fā)送給閱讀器，但是此時(shí)若有其他標(biāo)簽也在向閱讀器發(fā)送信號(hào)就會(huì)發(fā)生沖突，造成碰撞。在純ALOHA算法中發(fā)生碰撞之后，閱讀器會(huì)發(fā)出命令讓標(biāo)簽停止發(fā)送信號(hào)給自身，進(jìn)入一個(gè)不確定的“待命”時(shí)間段，標(biāo)簽只有在過(guò)了這個(gè)時(shí)間段之后才可以重新發(fā)送數(shù)據(jù)信息給閱讀器，這個(gè)時(shí)間段的時(shí)間范圍是不固定的，所以標(biāo)簽再次發(fā)送信號(hào)的時(shí)間也是隨機(jī)的，這樣就大大減小了碰撞的概率。

1.2 時(shí)隙ALOHA算法

時(shí)隙ALOHA算法與純ALOHA算法不同的是，它將時(shí)間段分為多個(gè)離散可等幀長(zhǎng)也可不等幀長(zhǎng)的時(shí)隙[4]，這些時(shí)隙由閱讀器分配，且每個(gè)標(biāo)簽都必須在所分配時(shí)隙的開(kāi)始處傳遞自己的信息。因此，時(shí)隙ALOHA算法是一種隨機(jī)查詢驅(qū)動(dòng)的TDMA防沖突算法。因?yàn)闃?biāo)簽只能在閱讀器分配的時(shí)隙中傳輸數(shù)據(jù)，即要么標(biāo)簽成功識(shí)別，要么發(fā)生碰撞，與純ALOHA算法相比，減小了碰撞周期，標(biāo)簽被識(shí)別的成功率得到了顯著增加。但是，時(shí)隙ALOHA算法在標(biāo)簽發(fā)生沖突之后，仍會(huì)通過(guò)隨機(jī)時(shí)間延遲進(jìn)行分發(fā)和重新傳輸數(shù)據(jù)。

1.3 動(dòng)態(tài)幀時(shí)隙ALOHA算法

傳統(tǒng)時(shí)隙ALOHA算法的幀長(zhǎng)是固定的，一幀可以包含多個(gè)時(shí)隙，也就是說(shuō)其時(shí)隙數(shù)也是確定的。那么即使當(dāng)有大量的標(biāo)簽待被閱讀器識(shí)別時(shí)，其時(shí)隙數(shù)也不會(huì)發(fā)生改變。這樣就存在一個(gè)問(wèn)題：當(dāng)標(biāo)簽的基數(shù)很大時(shí)，若時(shí)隙數(shù)設(shè)置的很小就可能會(huì)造成碰撞；若標(biāo)簽為數(shù)不多，時(shí)隙數(shù)很大，又會(huì)造成時(shí)隙的多余，從而造成浪費(fèi)[5]。動(dòng)態(tài)幀時(shí)隙ALOHA算法成功解決了這個(gè)問(wèn)題，它可以根據(jù)標(biāo)簽基數(shù)動(dòng)態(tài)更改一個(gè)幀內(nèi)的時(shí)隙數(shù)，當(dāng)標(biāo)簽基數(shù)很大時(shí)，可以通過(guò)增加時(shí)隙數(shù)避免碰撞的發(fā)生。其具體算法推理如下：

假設(shè)F是幀長(zhǎng)，N是系統(tǒng)要識(shí)別的全部標(biāo)簽數(shù)量，OVSF碼長(zhǎng)設(shè)為d，則在單個(gè)時(shí)隙中可以在d個(gè)OVSF碼中檢測(cè)到n個(gè)標(biāo)簽的概率為：

從式（8）可以看出，當(dāng)設(shè)置的幀長(zhǎng)與標(biāo)簽總數(shù)近似相等時(shí)，系統(tǒng)的信道利用率最高[6]，此時(shí)的吞吐量最大值為：

動(dòng)態(tài)幀時(shí)隙ALOHA算法較時(shí)隙ALOHA算法的優(yōu)點(diǎn)是：當(dāng)標(biāo)簽基數(shù)很大時(shí)，仍能使信道利用率維持在36%，時(shí)隙ALOHA算法因其時(shí)隙數(shù)固定，所以當(dāng)標(biāo)簽數(shù)量增大時(shí)，其發(fā)生碰撞的可能性會(huì)增加，信道利用率也會(huì)大幅度下降。

2 改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA算法

時(shí)隙ALOHA算法是一種隨機(jī)查詢驅(qū)動(dòng)的TDMA防沖突算法，本文在運(yùn)用TDMA技術(shù)的基礎(chǔ)上，結(jié)合碼分多址（CDMA）技術(shù)提出了一種新的幀時(shí)隙ALOHA算法，主要推導(dǎo)如下：

由式（3）可得系統(tǒng)的吞吐量，將d設(shè)為2，即OVSF碼長(zhǎng)為2時(shí)，吞吐量可表示為：

對(duì)N求導(dǎo)，令式子為零，可得：

當(dāng)標(biāo)簽數(shù)量趨近于無(wú)窮大時(shí)，系統(tǒng)吞吐量為：

由式（12）可知，新型幀時(shí)隙ALOHA算法的吞吐率達(dá)到了將近84%，比原來(lái)的幀時(shí)隙ALOHA算法提升近2倍，可見(jiàn)這種算法能夠更好地提高系統(tǒng)的信道利用率。

3 實(shí)驗(yàn)結(jié)果及分析

因純ALOHA算法和時(shí)隙ALOHA算法在當(dāng)網(wǎng)絡(luò)負(fù)載即標(biāo)簽基數(shù)很大時(shí)，其吞吐量基本為零，所以對(duì)這4種算法兩兩進(jìn)行分析。在圖1中，可以看到純ALOHA算法的吞吐量在16%左右，時(shí)隙ALOHA算法吞吐量為36%，吞吐量提高了近一倍。但這兩種算法在標(biāo)簽基數(shù)很大時(shí)，吞吐量均急劇減小直至為零。從圖2的實(shí)驗(yàn)結(jié)果可看出：動(dòng)態(tài)幀時(shí)隙ALOHA算法吞吐量在標(biāo)簽基數(shù)很大時(shí)，依然可以維持36%的吞吐量，這是因?yàn)檩^幀時(shí)隙ALOHA算法，動(dòng)態(tài)幀時(shí)隙ALOHA算法根據(jù)標(biāo)簽的總量實(shí)時(shí)動(dòng)態(tài)修正更改幀長(zhǎng)[7]，這樣就大大減小了碰撞的概率。所以即使當(dāng)標(biāo)簽的基數(shù)很大時(shí)，動(dòng)態(tài)幀時(shí)隙算法依然可以保證有足夠的時(shí)隙供標(biāo)簽選擇，因此可以維持吞吐量保持穩(wěn)定。新型動(dòng)態(tài)幀時(shí)隙ALOHA算法在幀時(shí)隙算法的基礎(chǔ)上進(jìn)一步做了修改，將CDMA技術(shù)與TDMA技術(shù)相結(jié)合，從圖2可以看出，吞吐量保持在84%左右，與幀時(shí)隙ALOHA算法相比提高了近2.3倍。這是因?yàn)樾滦蛣?dòng)態(tài)幀時(shí)隙ALOHA算法在將時(shí)間分為離散的多個(gè)時(shí)隙后，又結(jié)合了CDMA，也就是在同一個(gè)時(shí)隙中可以識(shí)別兩個(gè)標(biāo)簽[8]，擺脫了幀時(shí)隙ALOHA算法單個(gè)時(shí)隙只能識(shí)別單個(gè)標(biāo)簽的束縛[9]，大大減小了碰撞的概率，從而提高了系統(tǒng)的信道利用率。

圖1 純ALOHA算法和時(shí)隙ALOHA算法吞吐量仿真

圖2 動(dòng)態(tài)幀時(shí)隙和新型動(dòng)態(tài)幀時(shí)隙ALOHA算法吞吐量仿真

4 結(jié) 語(yǔ)

本文在幀時(shí)隙ALOHA防碰撞算法的基礎(chǔ)上提出了一種新的基于CDMA和TDMA技術(shù)相結(jié)合的防碰撞算法，該算法的吞吐量較改進(jìn)之前的算法提高了近2.3倍，提高了系統(tǒng)的信道利用率[10]。實(shí)驗(yàn)結(jié)果證明，如果增加碼長(zhǎng)，系統(tǒng)的吞吐量可以不斷增加，但是由于考慮到資源浪費(fèi)和研發(fā)費(fèi)用問(wèn)題，不宜增加過(guò)多，要根據(jù)具體的標(biāo)簽基數(shù)選擇碼長(zhǎng)，做到識(shí)別效率高且又不會(huì)浪費(fèi)資源。