于洪濤，王祖良，王少飛，曹闖樂，馬可欣

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

0 引 言

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

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

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

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

1 ALOHA算法

1.1 純ALOHA算法

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

1.2 時隙ALOHA算法

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

1.3 動態(tài)幀時隙ALOHA算法

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

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

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

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

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

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

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

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

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

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

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

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

圖1 純ALOHA算法和時隙ALOHA算法吞吐量仿真

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

4 結(jié) 語

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